辞書を使用する代わりにソートしてから、私はハッシュテーブルとの考えを勉強していた

Question

を探しに来た：

要素を検索する代わりに、最初のバイナリ検索をやって、リストをソートするための辞書を使用しないのはなぜ？我々はすべての要素を通過する必要があるため

1. 我々はO(n)（と思う）の時間で辞書にリストを変換することができます（私は複数回検索すると仮定）。
2. 私たちは辞書にこれらすべての要素を追加し、この辞書の準備ができたら、私たちはその後、O(1)時間（平均）とO(n)で任意の要素を検索することができます
3. O(1)時間がかかりますが今、最悪の場合

です私たちが平均的なケースについて話したら、O(n)は、他のソートアルゴリズムよりも優れているのは、たぶん彼らがO(nlogn)を取るからです。私が言ったことのすべてについて正しいのであれば、どうしてこのようにしませんか？

ソートされていない辞書や配列では行えないソートされた要素では、さまざまなことができることは知っていますが、検索にのみ固執すれば、他のソートアルゴリズム？

Answer 1

正しく、うまく設計されたハッシュテーブルはソートと検索に勝る可能性があります。

インプレース要件、データセットのダイナミズム、検索回数対挿入/削除、効果的なハッシュ関数を構築するのが簡単など、多くの要因があります。

Answer 2

バイナリ検索はkeyが検索されるべきkey Sのリストがすでにソートされ、それはその最悪のケースの検索を行うこと、並べ替えた後、検索する必要がないという事実を利用した検索技術であります時間O(log n)。

あなたがkey秒のソートされたリストを持っているとkeyを検索したくない場合は、最悪の場合にはO(n)複雑で実行されます線形検索のために行く必要があります、その後、並べ替えた後、どの検索する必要はありません最もよく知られているソートの藻類はO(n log n)の時間でしか動かないので間違いなく遅くなります。

listkeyのsからdictionaryを構築して、検索を実行すると、線形検索はパフォーマンス向上のために同じことをもたらすともdictionaryの場合に必要とされる補助記憶装置が必要となりますので、ここでノー有利です。 複数のルックアップがあり、キースペースが小さい場合dictionaryを使用すると、辞書を作成することがO(n)の1回の作業であり、その後の検索はO(1)によって実行できます。これは、dictionary 。