1

考虑两个 k 位数（二进制表示）：

$$A = A_1 A_2 A_3 A_4 ... A_k $$

$$B = B_1 B_2 B_3 B_4 ... B_k $$

为了比较，我们从左到右扫描寻找 a 的出现0并检查相反的数字，如果该数字也是 a 0（对于两个数字），请注意如果找到这样的情况，则 the 的来源0小于 the 的来源1. 但如果数字是：

111111111111
111111111110

显然，这将需要扫描整个数字，如果我们事先没有被告知数字并简单地给出它们，那么：

比较需要$O(k)$时间。

因此，当我们查看诸如高性能快速排序之类的排序方法的代码时：

HPQuicksort(list): T(n)
  check if list is sorted: if so return list
  compute median: O(n) time (or technically: O(nk))

  Create empty list $L_1$, $L_2$, and $L_3$ O(1) time

  Scan through list  O(n)

  if element is less place into $L_1$ O(k)

  if element is more place into $L_2$ O(k)

  if element is equal place into $L_3$ O(k)

  return concatenation of HP sorted $L_1$, $L_3$, $L_2$  2 T(n/2)

因此：T(n) = O(n) + O(nk) + 2*T(n/2) ---> T(n) = O(nklog(n))

这意味着快速排序比基数排序慢。

那我们为什么还要使用它呢？

4

1 回答 1

2

这里似乎有两个独立的问题：

  1. 为什么我们声称在分析排序算法时比较需要时间 O(1)，而实际上可能不需要？

  2. 为什么我们要对大整数使用快速排序而不是基数排序？

对于（1），通常，排序算法的运行时分析是根据进行的比较次数而不是根据执行的操作总数来衡量的。例如，著名的排序下界给出了比较次数的下限，快速排序、堆排序、选择排序等的分析都是通过计数比较来工作的。出于几个原因，这很有用。首先，通常，排序算法将通过给定一个数组和一些用于比较它们的比较函数来实现（例如，Cqsort或 JavaArrays.sort）。从排序算法的角度来看，这是一个黑盒子。因此，通过尽量减少对黑盒的调用次数来分析算法是有意义的。其次，如果我们确实通过计算比较来执行排序算法的分析，那么通过将比较的数量乘以比较的成本就很容易确定整体运行时间。例如，您正确地确定使用快速排序对 n k 位整数进行排序将花费预期时间 O(kn log n)，因为您只需将比较次数乘以比较的成本即可。

对于您的第二个问题 - 为什么我们要对大整数使用快速排序而不是基数排序？- 通常，由于您指出的特定原因，您实际上会在这种情况下使用基数排序，而不是快速排序。快速排序是一种很好的排序算法，用于对可以相互比较的对象进行排序并且具有出色的性能，但基数排序在大字符串或整数的大型数组上经常优于它。

希望这可以帮助！

于 2014-05-22T15:47:45.467 回答