どちらに時間がかかりますか？
バイナリ検索ツリーに格納されているすべてのアイテムを並べ替えられた順序で印刷するか、ハッシュテーブルに格納されているすべてのアイテムを並べ替えられた順序で印刷します。
ハッシュテーブルが正しくソートされないため、ハッシュテーブルのアイテムをソートされた順序で出力するのに時間がかかりますか？そしてBSTは？
質問する
21866 次
6 に答える
13
あなたは正しいです。ハッシュテーブルは、自然の並べ替え順序ではなく、ハッシュ関数によって並べ替えられるため、すべてのエントリO（N）を抽出してO（NlogN）に並べ替える必要がありますが、O（で二分探索木を自然順序でトラバースできます。 N）。
ただし、たとえばJavaには、LinkedHashSetとLinkedHashMapがあり、Hashの利点のいくつかを提供しますが、追加された順序でトラバースできるため、ソートしてその中でトラバースできることに注意してください。並べ替えられた順序と、ハッシュによるアイテムの抽出。
于 2009-05-13T19:08:19.757 に答える
3
正解です。ハッシュテーブルは、おそらく希望する方法で「ソート」されていません。ハッシュテーブルの要素は、通常、完全にソートされていませんが、配置はソートの近くにあることがよくあります。しかし、それらはハッシュ関数に従って配置されます。ハッシュ関数は通常、類似したフレーズでは大きく異なります。これは、人間が使用するメトリックによる並べ替えではありません。
コレクションで行っている主なことがソートされた順序で印刷することである場合は、ある種のBSTを使用するのが最善です。
于 2009-05-13T19:08:38.803 に答える
2
二分探索木は、深さ優先探索を実行すると、並べ替えられた順序でアイテムが見つかるように格納されます（一貫した比較機能があると仮定します）。すでにツリーにあるアイテムを単に返すというBigOは、ツリーをトラバースするというBigOになります。
あなたはハッシュテーブルについて正しいです、それらはソートされていません。実際、プレーンハッシュテーブル内のすべてを列挙するには、すべてのバケットをチェックしてそこにあるものを確認し、それを引き出してから、取得したものを並べ替える必要があります。そこからソートされたリストを取得するための多くの作業。
于 2009-05-13T19:10:11.313 に答える
1
正解です。ハッシュテーブルはソートされたデータではないため、ハッシュテーブルに格納されているソートされたデータの印刷は遅くなります。特定のアイテムをすばやく見つける方法を提供します。「BigONotation」では、アイテムは一定時間、つまりO（1）時間で見つかると言われています。
一方、データはすでにソートされているため、「対数時間」（O（log n））の二分探索木でアイテムを見つけることができます。
したがって、ソートされたリストを印刷することが目標である場合は、データをソートされた順序（つまり、バイナリツリー）で保存する方がはるかに優れています。
于 2009-05-13T19:11:12.293 に答える
0
これにより、いくつかの興味深い質問が発生します。次のことを考慮すると、検索ツリーはさらに高速ですか？
- ハッシュテーブルとBSTの両方のセットアップ時間を組み込みますか？
- ハッシュアルゴリズムが単語のソートされたリストを生成する場合。技術的には、そうするアルゴリズムを使用するハッシュテーブルを作成できます。この場合、BSTとハッシュテーブルの速度は、ソートされた順序でハッシュテーブルを埋めるのにかかる時間まで下げる必要があります。
于 2009-05-13T20:15:53.017 に答える
0
スキップリストとバイナリツリーの関連する考慮事項も確認してください：スキップリストとバイナリツリー
于 2009-05-13T20:21:58.777 に答える