21

CLRS物品税22.1-8で（私は独学であり、どの大学にも所属していません）

リンクされたリストの代わりに、各配列エントリ Adj[u] が (u,v) ∈ E である頂点 v を含むハッシュ テーブルであると仮定します。エッジはグラフにありますか? このスキームにはどのような欠点がありますか? これらの問題を解決する各エッジ リストの代替データ構造を提案します。ハッシュテーブルと比較して、代替案には欠点がありますか?

したがって、各リンク リストをハッシュ テーブルに置き換えると、次のような疑問が生じます。

  1. エッジがグラフにあるかどうかを判断するのに予想される時間は?
  2. 短所は何ですか？
  3. これらの問題を解決する各エッジ リストの代替データ構造を提案する
  4. ハッシュテーブルと比較して、代替案には欠点がありますか?

次の部分的な回答があります。

  1. Hashtable t = Adj[u] を実行してから t.get(v); を返すだけなので、予想される時間は O(1) だと思います。
  2. 欠点は、Hashtable がリンクされたリストよりも多くのスペースを取ることだと思います。

他の 2 つの質問については、手がかりが得られません。

誰でも私に手がかりを与えることができますか？

4

3 に答える 3

14

質問 3 の答えは、二分探索木である可能性があります。

隣接行列では、各頂点の後に V 要素の配列が続きます。この O(V) スペース コストは、エッジの高速 (O(1) 時間) 検索につながります。

隣接リストでは、各頂点の後に、隣接する n 個の頂点のみを含むリストが続きます。このスペース効率の良い方法では、検索が遅くなります (O(n))。

ハッシュ テーブルは、配列とリストの間の妥協点です。V よりも少ないスペースを使用しますが、検索時に衝突のハンドルが必要です。

二分探索木も別の妥協案です。スペース コストはリストの場合と同様に最小であり、検索の平均時間コストは O(lg n) です。

于 2012-12-16T06:41:34.923 に答える
11

これは、ハッシュ テーブルと衝突の処理方法に依存します。たとえば、ハッシュ テーブルで、各エントリが同じキーを持つ要素のリストを指しているとします。

要素の分布が十分に均一である場合、ルックアップの平均コストは、各リスト (負荷係数) ごとの要素の平均数のみに依存します。したがって、各リストの平均要素数は n/m で、m はハッシュ テーブルのサイズです。

  1. エッジがグラフにあるかどうかを判断する予想時間は O(n/m) です。
  2. リンクされたリストよりも多くのスペースと、隣接行列よりも多くのクエリ時間。ハッシュテーブルが動的なサイズ変更をサポートしている場合、古いハッシュテーブルと新しいハッシュテーブルの間で要素を移動するために余分な時間が必要になります. O(n^2) スペースになります。また、予想されるクエリ時間を確認しました。最悪の場合、linked list(O(degree(u))) のようにクエリ時間が発生する可能性があるため、決定論的な O(1) クエリ時間を得るために隣接行列を使用することをお勧めします。および O(n^2) スペース。
  3. 上記参照
  4. はい、たとえば、グラフのすべての頂点に最大で d 個の隣接頂点があり、d 個が n 未満であることがわかっている場合、ハッシュ テーブルを使用すると、O(n^2) ではなく O(nd) スペースが必要になり、O( 1) クエリ時間。
于 2012-03-17T16:26:33.283 に答える