如果排序需要 O(n) 时间，我们为什么不使用尝试进行排序？

Question

以下是使用特里树对字符串进行排序的算法的描述：

该算法首先O(n)及时插入trie中的所有项目，其中n是要排序的单词列表中的字符总数。

然后它按顺序遍历树，当遇到is_end设置了标志的节点时，打印出一个以它的前缀开头的节点。这需要对特里树进行完整的遍历，这需要O(m)时间，其中 m 是特里树中的节点数。这以 为界n，因此这一步也以 为界O(n)。

整个算法由两个子程序组成，每个子程序以 为界O(n)。例如，如果我们说平均单词包含c字符，那么 ifm是单词数，cm == n，并且总运行时间受O(n) == O(cm) == O(m)（我将其更改为的原因m是因为这是要排序的列表长度的传统度量，不是字符总数）。

因此，我的问题是，如果这个运行时分析是正确的，为什么这不是字符串排序的默认方法，因为它比任何O(nlogn)排序算法都快？

Answer 1

O(n log n) 下限用于比较排序，即数组中的元素只能相互比较以检查一个元素应该在另一个之前还是之后，或者它们是否相等。这是通用排序算法的一个很好的模型，因为它几乎适用于您可能想要排序的任何类型的数据；数字、字符串、用户定义类的实例等。它甚至可以只是一种可以通过键函数映射到支持比较的其他数据类型的数据类型；或者你可以接受一个比较器函数来进行比较。

请注意，这里的 O(n log n) 是比较次数的下限，而不是运行时间。如果每次比较花费的时间超过 O(1)，比如说因为您正在比较具有长公共前缀的长字符串，那么运行时间将类似于 O(cn log n)，其中比较在 O(c) 时间内完成. 例如，在最坏的情况下，比较长度为 w 的字符串需要 O(w) 时间。

如果您只需要针对特定​​类型数据的排序算法，那么您可能会做得更好，因为可以对元素执行特定于该数据类型的其他操作。例如，在对整数进行排序时，您可以使用数组元素来索引另一个数组，给出在 O(n + r) 时间内运行的计数排序算法，其中 r 是数组元素的范围。

如果排序键就像字符串，从某种意义上说它们是（或可以映射到）序列，这样比较键就相当于按字典顺序比较这些序列，那么您确实可以使用 trie 对包含该数据类型的数组进行排序。恭喜：你已经独立地重新发明了基数排序算法，可以使用 try来实现。它的运行时间是 O(wn)，而不是 O(n)，因为将长度为 w 的字符串插入到 trie 中需要 O(w) 时间，并且您必须这样做 n 次。

因此，如果元素不是字符串，或者上述意义上的“类字符串”，则基数排序根本不适用。如果元素是字符串或“类似字符串”，则基数排序有效，但需要 O(wn) 时间而不是 O(cn log n)。

这意味着基数排序并不是严格意义上的更好，并且在字符串的公共前缀相对于字符串本身较短时可能更糟，这通常是这种情况。对于随机字符串，常规字符串比较平均花费 O(1) 时间，在这种情况下，对于长度超过 O(log n) 的字符串，O(n log n) 渐近优于基数排序。

在实际应用中，还应考虑渐近分析中的隐藏常数。像Timsort这样的比较排序具有较低的隐藏常量，因为它们按顺序访问数组元素，与遍历节点在内存中不连续的树相比，这会导致更少的缓存未命中。