I know this might be a silly question but suppose an algorithm sorts 100,000 integers in 5 seconds. Will the same algorithm sort 100,000 strings in 5 seconds as well or will their sorting times be different?
问问题
207 次
5 回答
2
比较字符串比比较整数更昂贵。整数比较是通常发生在 CPU 中的操作。另一方面，字符串的比较需要在软件中实现。因此，字符串的比较可以采用与字符串中的字符一样多的操作。
--dmg
于 2013-05-18T02:43:57.183 回答
1
问：算法对整数和字符串的排序是否具有相同的时间一致性？
答：如果您的意思是“渐近”/“大 O 表示法”：是的。字符串显然需要更长的时间......但比例更长。
于 2013-05-18T02:56:20.997 回答
0
假设您按字典顺序对它们进行排序，并使用快速排序。您编写自己的比较函数来比较字符串和整数。
整数比较容易比较，它的值是它的索引，而对于字符串，你需要通过它的内容来比较。We do know that quick sort runs at an average time complexity of O(nlogn), with worst being O(n^2), and that happens when the pivot chosen is the minimum or maximum of the current partition. 我们假设一切顺利，现在我们得到了平均情况。
时间复杂度的变量是您的比较函数，整数一个非常快 O(1)，而比较字符串归结为 O(min(len(a), len(b)) 的最坏情况，O( 1），当第一个字符不同时。
所以是的，它更慢，但考虑到它们是字符串，这还不错，最坏的情况是那些很少发生的情况。（就像 Barney Goven 提到的，比较两个相似的字符串。）
在谈论算法的时间复杂度时，我们通常谈论的是当数据集变大时它的增长。所以就像 paulsm4 所说的那样，它相应地更长。
于 2013-05-18T05:31:13.430 回答
0
简单回答是不。通常，对字符串进行排序要比对整数进行排序花费更长的时间。
考虑对“paper”和“papa”进行排序——您需要通过比较前 4 个字符来发现“paper”大于“papa”。对于较大的字符串，尤其是短语，这可能会变得更长。
相反，整数比较只需要一条指令。
要进行排序，您需要反复进行此类比较；所以排序字符串几乎总是需要更长的时间。
于 2013-05-18T02:49:27.130 回答
0
字符串将花费更多时间。整数作为一组按位操作进行比较。当涉及到字符串时，每个字节或字符都将与整数所需的相等操作进行比较。
实际上，对一组字符串进行排序将涉及比较所有字符串中的字符总数，在最坏的情况下。最坏的情况是所有字符串都相同。每个字符串都必须遍历到最后以确保它相等（strcmp() 比较这种方式）
于 2013-05-18T02:50:13.680 回答