如果它们花O(n)的时间来排序列表,为什么不使用try进行排序?

问题描述 投票:2回答:1

这里是使用特里对字符串进行排序的算法的描述:

[算法首先在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)排序算法都要快?

algorithm sorting data-structures time-complexity trie
1个回答
2
投票

O(nlogn)下界是针对comparison sorts的,即可以将数组中的元素进行相互比较,以检查一个元素应该在另一个元素之前还是之后,或者它们是否相等。对于general

© www.soinside.com 2019 - 2024. All rights reserved.