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

Question

以下是使用 trie 对字符串进行排序的算法的描述:

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

然后它按顺序遍历树，当涉及到具有 is_end 的节点时，打印出其前缀前面的节点。标志设置。这需要完整遍历trie，需要O(m)时间，其中 m 是 trie 中的节点数。这以 n 为界, 所以这一步以 O(n) 为界也是。

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

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

Answer 1

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

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

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

如果排序键类似于字符串，从某种意义上说它们是(或可以映射到)序列，因此比较键等效于 lexicographically comparing这些序列，那么您确实可以使用 trie 对包含该数据类型的数组进行排序。恭喜:您已经独立改造了 radix sort算法，可实现using tries .它的运行时间是 O(wn)，而不是 O(n)，因为将长度为 w 的字符串插入到 trie 中需要 O(w) 时间，并且您必须这样做 n 次。

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

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

在实际应用中，还应考虑渐近分析中的隐常数。比较类似于 Timsort具有较低的隐藏常数，因为它们按顺序访问数组元素，这导致更少的 cache misses与行走一棵其节点在内存中不连续的树相比。