这里是使用特里对字符串进行排序的算法的描述:
[算法首先在O(n)
时间内将所有项插入到trie中,其中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)
排序算法都要快?
O(nlogn)下界是针对comparison sorts的,即可以将数组中的元素进行相互比较,以检查一个元素应该在另一个元素之前还是之后,或者它们是否相等。对于general