使用合并排序的字符串排序
对每个n
具有n
字符的字符串进行排序最复杂的情况是什么?它会只是n
其平均值的两倍吗?情况O(n log n)
还是其他…?
回答:
与@orangeoctopus一样,n
对大小字符串的集合使用标准排名算法n
将导致O(n^2 * logn)
计算。
然而-注意,你
做到这一点的O(n^2)
,对变异基数排序。
[我认为]最简单的方法是
- 构建一个trie,并用所有字符串填充它。输入的每个字符串是
O(n)
,您输入的n
时间为-总计O(n^2)
- 每次遇到字符串结尾标记时,请在trie上执行DFS-将其添加到排序的集合中。以这种方式添加的字符串的顺序按字典顺序排列,因此完成后,将按字典顺序对列表进行排序。
很容易看到您不能再做得更好O(n^2)
,因为只能读取数据O(n^2)
,因此从时间复杂度的大O标记来看,此解决方案是最佳的。
以上是 使用合并排序的字符串排序 的全部内容, 来源链接: utcz.com/qa/404977.html