algorithm - グラフ データ構造の最悪の場合のメモリ

Question

多くの本で、グラフの最悪の場合のメモリ要件は O(V) であることがわかりました。しかし、私が間違っていなければ、グラフは通常、ノードの作成ではなく、隣接行列として表されます (リンクされたリスト/ツリーのように)。したがって、5 つの頂点を含むグラフの場合、O(V^2) である 5x5 行列が必要です。彼らはなぜそれを O(V) と言うのですか?

私はどこかで何かを逃していますか？質問が素朴すぎる場合は申し訳ありません。

Answer 1

あなたの言うことが本当なら、隣接行列を使用する以外に、グラフを表す他の方法を参照している可能性があり、エッジ密度の仮定を行っている可能性があります。1 つの方法は、頂点ごとに、隣接する頂点へのポインター/参照のリスト (隣接リストと呼ばれます) を格納するだけです。これはO(|V| + |E|). を仮定すると、これ|E| ~ |V|は時々見られる仮定ですが、O(|V|)スペースがあります。ただし、最悪の場合、グラフ|E| ~ |V|^2を表現するこのアプローチでさえ最悪の場合であることに注意してください。O(|V|^2)

ほら、とても簡単です。最悪の場合は避けられない|E| ~ |V|^2。一般にE、最悪の場合に ではない の表現はあり得ません O(|V|^2)。

ただし、正確な見積もりを使用できると便利です。これは重要です。私たちは、正しい発言に対するあなたの誤解を引き裂くようなことはしたくありません。