algorithm - 如何在 Omega(nt+nlogn) 中对长度为 t 的 n 个字符串进行排序？

Question

您可以访问 O(1) 中的每个字符.你只能要求比较两个结果为 1,-1,0 的字符。意思是，a<b, a>b, a=b .

显然，对数组进行排序的范围是Omega(nlogn)。 .因为对于两个字符串，我们需要在最坏的情况下比较 t 个字符，它不应该是 Omega(t*nlogn) ？

Answer 1

认为您需要比较字符串对的每个字符来对列表进行排序是错误的(因为如果字符串在一个地方不同，您就不需要在后面的地方比较它们)。唯一的诀窍是弄清楚如何有效地做到这一点。这是一种方法。

首先，在 O(nt) 中构建一个无序的 trie(即，每个节点存储一个 child 的哈希表，而不是一个列表)。

不能有超过 n 个节点有超过 1 个直接子节点，并且这些节点中的子节点总数不能超过 2n(对于 1 以上的每个子节点至少添加一个字符串到 trie) .因此，对所有节点的所有直接子节点进行排序最坏情况下是 O(n log n)(因为如果有 k_1、k_2、...、k_m 和 sum(k_i) = 2n，则 sum(k_i log k_i) <= 2n日志(2n)。

对每个节点进行排序后，您可以遍历 trie 并在时间 O(nt) 内构造字符串的排序列表。