algorithm - 为什么基数排序是 O(nd) 而归并排序不是 O(d*nlogn)？

Question

通常当人们谈论排序算法的复杂性时，我看到这样的解释:

The complexity of Radix Sort is O(nd), where n is the length of the list and d is the number of digits

和

The complexity of Merge Sort is O(n log n), where n is the length of the list

这几乎就好像是在证明基数排序在某种程度上通常比归并排序慢，尽管它没有任何意义。

有两种情况:

案例 1:我们正在对具有四个字节的普通整数进行排序。 在这里，比较需要常数时间，所以 O(n log n) 描述归并排序是有意义的。但是，在对普通整数进行排序时，O(nd) 中的 d 是一个常量(对于 16 进制，可能是 4 — 或者，对于 2 进制，可能是 16。无论哪种方式，它都是一个常量，以及由基数排序调用的 bin 排序中的 bin 数量以补偿该数量)。那么，说基数排序的复杂度为 O(n) 而归并排序的复杂度在 O(nlogn) 时不是更有意义吗？

案例 2:我们正在对字符串进行排序，可以将其视为基本 ASCII 中具有任意位数的数字。 在这里，比较需要 O(d) 时间，因为最坏的情况是将 AAAAAAAAB 与 AAAAAAAAC 进行比较，这可能需要很长时间。 在这种情况下，说基数排序具有 O(nd) 的复杂度是完全合理的，因为 d 随输入而变化。 但是，在这种情况下，合并排序是否也应该被视为 O(d*nlogn)，因为比较时间不再恒定？

在我看来，人们不相信基数排序的速度足够快，可以使用，他们通过模棱两可地描述复杂性使其看起来比基于比较的排序更糟糕，以此来证明基数排序的时间常数很大。

我为糟糕的格式道歉，我不确定如何让它在 stackoverflow 上看起来更好

Answer 1

逐个字符(或逐个数字)比较时的合并排序将是 O(d n log n) 操作。但是您可以对任何类型的对象进行排序，并且比较可以是这些对象上的任何函数，因此这样的表示会过于具体 - 您需要一些其他的复杂性来使用不同的比较方法来表示相同的归并排序算法。

用比较的数量来表示复杂性更有意义，所以你可以说合并排序总是O(n log n)比较。

比较通常也被认为是一个非常快速的操作，即恒定时间(即使这不是一般规则)。另一方面，基数排序需要对每个数字的输入进行循环——你不能说有多少循环并不重要。

比较归并排序和基数排序的复杂度，某种程度上就是比较苹果和橘子。