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

Question

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

基数排序的复杂度是O(nd)，其中n是列表的长度，d是位数

和

归并排序的复杂度是O(n log n)，其中n是列表的长度

这几乎好像是为了证明基数排序通常比合并排序慢，即使它没有任何意义。

有两种情况：

案例 1：我们正在对具有四个字节的普通整数进行排序。在这里，比较需要恒定的时间，因此O(n log n)描述归并排序是有意义的。但是，在对普通整数进行排序时，dinO(nd)是一个常数（对于基数 16 或 16，对于基数 2，可能是 4。无论哪种方式，它都是一个常数，并且由基数排序调用的 bin 排序中的 bin 数量可以进行调整以弥补这一点）。那么，说基数排序O(n)和归并排序在客观上具有更差的复杂性不是更有意义O(nlogn)吗？

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

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

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

标签： algorithmsortingmergemergesortradix-sort

Answer 1

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

用比较次数来表示复杂性更有意义，因此您可以说合并排序始终是O(n log n)比较。

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

比较归并排序和基数排序的复杂度在一定程度上是比较苹果和橘子。