Trieデータ構造のBest/Worst/Average Case Big-Oランタイムとは何ですか？

Question

挿入と検索のためのトライデータ構造の最良/最悪/平均ケース複雑度（Big-O表記法）はどれくらいですか？

すべての場合、O(K)と思う。ここで、Kは、挿入または検索されている任意の文字列の長さです。誰かがこれを確認するのだろうか？

Answer 1

はWikipediaとthis source、トライの挿入および検索のための最悪の場合の複雑さによるMは、キーの長さO(M)あります。私は、挿入と検索の最高または平均の複雑さを記述する情報源を見つけることに失敗しています。しかし、Big-Oは複雑さの上限を記述しているだけなので、が最良で平均的なケースの複雑さはMがキーの長さであると安全に言うことができます。

Answer 2

ウィキペディアでこれについての素晴らしい情報があります。 http://en.wikipedia.org/wiki/Trie

Answer 3

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）を見たことがあり、それはあなたを混乱させるかもしれませんが、O（k）の操作をN回行う必要があるときに話しています。