2

给定 n 个单词,是否可以以 o(n) 时间复杂度按字典顺序对它们进行排序?好吧,我发现了一种方法,例如创建 trie 数据结构和 trie 的中序遍历会导致时间复杂度接近 O(kn),其中 k 是任意字符串长度,但这里的问题是空间复杂度。构造 BST 和中序遍历也是一个不错的选择,但时间复杂度为 O(nlogn) 。因此,鉴于两者的限制,谁能建议我哪个会更好 BST 或 trie。也欢迎任何其他算法或建议。

4

1 回答 1

3

使用桶排序基数排序很容易对单词进行O(nL)及时排序。这里是字长。不可能做得更好,因为您必须至少查看所有键一次。 L

你的三分法想法是一个古老的想法。

于 2013-07-10T02:49:44.360 回答