algorithm - 複雑さと検索を試す

Question

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

Answer 1

トライを作成する複雑さは ですO(W*L)。ここWで、 は単語の数で、 は単語の平均の長さです。セット内の各単語の平均でルックアップLを実行する必要があります。LW

後で単語を検索する場合も同様です。単語Lごとに手順を実行しWます。

ハッシュの挿入とルックアップの複雑さは同じです。単語ごとに等しいかどうかをチェックする必要がありO(L)ますO(W*L)。

単語全体を調べる必要がある場合は、ハッシュ テーブルの方が簡単です。ただし、ハッシュ テーブルを使用してプレフィックスで単語を検索することはできません。接頭辞ベースのルックアップに関心がない場合は、ハッシュ テーブルを使用してください。それ以外の場合は、トライを使用してください。