複雑さと検索のトライ

Question

単語のリストのtrieの作成の複雑さと、そのトライの他の単語セットの検索の複雑さは何ですか？ ハッシュテーブルがある場合、文字列検索にトライを使用する必要がありますか？

Answer 1

トライを作成するための複雑さはWは、単語の数であり、Lは、単語の平均長さで、O(W*L)です：あなたはセットでWの単語ごとに平均でLルックアップを実行する必要があります。

同じことを後で検索する場合は、W単語ごとにLステップを実行します。

ハッシュの挿入と参照には同じ複雑さがあります。つまり、各単語に対して、O(L)の均等性をチェックする必要があります。全体の複雑度はO(W*L)です。

単語全体を検索する必要がある場合は、ハッシュテーブルが簡単です。ただし、ハッシュテーブルを使用して接頭辞で単語を検索することはできません。接頭辞ベースの検索に興味がない場合は、ハッシュテーブルを使用します。それ以外の場合は、トライを使用します。