Trie数据结构的最佳/最差/平均案例Big-O运行时是什么时候？

Question

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

我认为这适用O(K)于所有情况,其中K是插入或搜索的任意字符串的长度.有人会证实吗？

Answer 1

根据维基百科和这个源,以插入和寻求线索最坏情况的复杂性是O(M)其中M一个关键的长度.我没有找到任何描述插入和搜索的最佳或平均案例复杂性的来源.但是,我们可以肯定地说,最好和平均情况复杂度是O(M)其中M一个关键的长度,因为大O只描述了复杂的上限.

Answer 2

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)操作.