私はインタビューを受けていて、ハッシュテーブルについて尋ねられ、構造連鎖について説明しなければなりませんでした。
O(1) の複雑さでリンクされたリスト内の要素を検索する方法を尋ねられました。
O(1)で実際に見つけることができますか?
ありがとう
2929 次
3 に答える
9
いいえ、絶対に違います。リンクされたリストには、アイテムをすばやく見つける狡猾な方法はありません。それは O(n) です。
十分なハッシュコードがあれば、ハッシュテーブルでの検索は O(1) しかありません。すべてのキーが同じハッシュ コードを持っている場合、使用するアドレス指定スキームが何であれ、それは O(n) です。
于 2013-02-19T19:17:09.470 に答える
6
リンク リスト内のノードへの参照を他の構造に保持していない限り、O(1) 内のリンク リスト内の要素にアクセスすることはできません。これは、リンクされたリストがリストの先頭への参照を保持し、要求されたものを見つけるために次の各要素を反復処理する必要があるためです。これは O(n) になります。
于 2013-02-19T19:17:15.727 に答える
0
いいえ、O(1) 複雑度内でリンク リストを検索することはできません。
Hashtable は、同じハッシュ値を持つ要素の構造連鎖または連結リストを作成します。
ハッシュが均一に分散されている場合 (適切なハッシュ)、ハッシュ テーブルは要素を検索するための複雑さが O(1) になります。ハッシュテーブルにはバケットがあり、各バケットにはハッシュ値からアクセスでき、各バケットには同じハッシュ値を持つ要素のリンクリストが含まれています。
于 2013-02-19T19:20:16.880 に答える