15

用于插入和搜索的 trie 数据结构的最佳/最差/平均情况复杂度（Big-O 表示法）是多少？

我认为O(K)适用于所有情况，K插入或搜索的任意字符串的长度在哪里。有人会证实这一点吗？

4

3 回答 3

19

根据Wikipedia和这个来源，插入和搜索 trie 的最坏情况复杂性是密钥的长度O(M)在哪里。M我找不到任何描述插入和搜索的最佳或平均案例复杂性的来源。但是，我们可以肯定地说，最佳和平均情况复杂度是O(M)密钥M的长度，因为 Big-O 仅描述了复杂度的上限。

于 2013-07-26T21:56:58.493 回答
7

k：您搜索或插入的字符串的长度。

For Search

Worst: O(26*k) = O(k)
Average: O(k)          # In this case, k is an average length of the string
Best: O(1)             # Your string is just 'a'.

Trie 的复杂性不会随着您搜索的字符串数量而变化，只会随着搜索字符串的长度而变化。这就是为什么在要搜索的字符串数量很大时使用 Trie 的原因，例如在英语词典中搜索整个词汇表。

For Insertion

Worst: O(26*k) = O(k)
Average: O(k) 
Best: O(1)

所以，是的，你是对的。您可能已经看过 O(MN) 并且可能会让您感到困惑，但这只是在谈论您何时需要进行 N 次以上 O(k) 操作。

于 2017-07-31T21:34:20.003 回答
0

维基百科上有一些很棒的信息。http://en.wikipedia.org/wiki/Trie

于 2013-07-26T21:43:08.803 回答