[解決済み] グラフの隣接リスト表現の空間複雑性

質問

読む こちら 無向グラフの場合、空間の複雑さは O(V + E) を隣接リストとして表現した場合 V と E はそれぞれ頂点と辺の数である。

私の分析では、完全連結グラフの場合、リストの各エントリには |V|-1 ノードがある場合、合計で |V| の頂点を含むので、空間の複雑さは O(|V|*|V-1|) と思われますが O(|V|^2) 何が足りないのでしょうか？

どのように解決するのですか？

あなたの分析は正しい 完全連結グラフの場合 . しかし，完全連結グラフの場合，辺の数 E は O(V^2) そのものなので、表記は O(V+E) の空間の複雑さについても、やはり正しい。

しかし、隣接リストの本当の利点は、あまり密に接続されていないグラフのスペースを節約できることです。もし、辺の数が V^2 の場合、隣接リストには O(V+E) そして ない O(V^2) のスペースが必要です。

について話すとき、注意してください。 O -ノテーションは、通常、3種類の変数（あるいは一般的な入力データ）を持っています。1つ目は、研究対象である変数の依存性、2つ目は、定数とみなされる変数、3つ目は、自由変数の一種で、通常 最悪の場合 の値です。例えば、配列のソートが N 整数の場合、通常、ソート時間の N ということで N は第1種である。通常，整数の大きさは一定であると考えます（つまり，比較は O(1) また、通常、特定の配列要素を"free"と考え、つまり特定の配列要素の最悪の組み合わせに対する実行時間を研究します。しかし、同じアルゴリズムを別の視点から研究したいと思うかもしれませんし、それは異なる複雑さの表現につながります。

グラフのアルゴリズムでは、もちろん頂点の数を考慮することができます。 V を第一種、辺の数を第三種とし、与えられた V と、最悪の場合のエッジの数についてです。すると、確かに O(V^2) . しかし V と E を最初の型の変数とすると、複雑な式は次のようになります。 O(V+E) .