使用Merge Sort进行字符串排序

Question

排序每个n字符串的最差复杂性是n什么？这是n它的平均时间吗？案件O(n log n)或别的什么......？

Answer 1

当你O用两种不同长度的东西来谈论符号时,通常你想要使用不同的变量,比如M和N.

所以,如果您的合并排序是O(N log N),这里N是一个字符串的数量...并比较两个字符串时O(M),其中M有字符串的长度尺度,那么你会留下:

O(N log N) * O(M)

要么

O(M N log N)

M字符串长度在哪里,是字符串N的数量.你想使用不同的标签,因为它们并不意味着相同的东西.

在奇怪的情况下,平均字符串长度与字符串数量成比例,就像你有一个矩阵存储在字符串或类似的东西,你可以争辩M = N,然后你有O(N^2 log N)

Answer 2

作为@orangeoctopus，对n大小字符串的集合使用标准排名算法n将导致O(n^2 * logn)计算。

但请注意，您可以使用基数排序O(n^2)的变体来完成此操作。

[在我看来]最简单的方法是

1. 构建一个trie，并用所有字符串填充它。输入每个字符串的O(n)次数n- 总计O(n^2)
2. 在 trie 上执行DFS，每次遇到字符串结束标记时 - 将其添加到已排序的集合中。以这种方式添加的字符串的顺序是按字典顺序排列的，因此完成后您的列表将按字典顺序排序。

很容易看出你不能做得更好O(n^2)，因为只读取数据就是O(n^2)，因此这个解决方案就时间复杂度的大 O 表示法而言是最佳的。