14
単語のリストのtrieの作成の複雑さと、そのトライの他の単語セットの検索の複雑さは何ですか? ハッシュテーブルがある場合、文字列検索にトライを使用する必要がありますか?複雑さと検索のトライ
単語のリストのtrieの作成の複雑さと、そのトライの他の単語セットの検索の複雑さは何ですか? ハッシュテーブルがある場合、文字列検索にトライを使用する必要がありますか?複雑さと検索のトライ
トライを作成するための複雑さはW
は、単語の数であり、L
は、単語の平均長さで、O(W*L)
です:あなたはセットでW
の単語ごとに平均でL
ルックアップを実行する必要があります。
同じことを後で検索する場合は、W
単語ごとにL
ステップを実行します。
ハッシュの挿入と参照には同じ複雑さがあります。つまり、各単語に対して、O(L)
の均等性をチェックする必要があります。全体の複雑度はO(W*L)
です。
単語全体を検索する必要がある場合は、ハッシュテーブルが簡単です。ただし、ハッシュテーブルを使用して接頭辞で単語を検索することはできません。接頭辞ベースの検索に興味がない場合は、ハッシュテーブルを使用します。それ以外の場合は、トライを使用します。
ハッシュテーブル内の単語全体を検索している場合は、良いハッシュ関数が必要です。ハッシュ関数を定義するときには注意が必要です。私が間違っていると私を訂正してください... – Varun
@var文字列をハッシュテーブルのキーとして広く使用しているため、文字列に対する非常に優れたハッシュ関数が考案されました。インターネット上で簡単に検索すると、6つの素晴らしい提案が得られます。マイクロソフトが使用するもの、またはJava文字列に組み込まれたものには、多くのものが最適化されているため、使用します。 – dasblinkenlight