グラフの隣接リストのBigOが（V + E）で、（V^2）でないのはなぜですか？

Question

私の考えが間違っている場合は、私を訂正してください。私はBigO（V + E）= BigO（V^2）だと思います。

私の考えは以下の通りです。
完全なグラフのエッジ= n *（n-1）/ 2。

EとVからnへの切り替えは、私がそのように思う方が簡単だからです。

E = N *（N-1）/ 2
V = N

ビーゴ（V + E）=>ビーゴ（N + N *（N-1）/ 2）=>ビーゴ（ N^2）

バックV.

に切り替えnは

=>ビーゴ（V^2）

私は何かが足りないのですか？ BigO（V + E）を使う理由BigO（V^2）を使わないのはなぜですか？

Answer 1

入力サイズに基づいてどれくらい使用するかを見積もるのにBigOが使用されます。

隣接リストを作成しているときは、頂点の数はV、辺の数はEです。今度は、必要なメモリ量を見積もりたい。

O(V+E)は、V > E ? O(V) : O(E)と解釈できます。つまり、それはmax(V,E)に線形に複雑になります。

各vのリストを作成するので、メモリにO(V)のメモリを使用します。 各辺に印を付け、O(E)のメモリを使用します。 O(V+E)はそれを正確に意味します。複雑さがO(V^2)だと言うなら、2*nの頂点を持つ空のグラフでは、約を使うべきです。 4空のグラフよりも時間が多く、nの頂点があります。

あなたは別のアプローチをテストすることができます複雑にいくつかの研究を行って

：

• 最悪のケースを、
• 平均場合、
• ベストケース。

さらに詳しい情報が必要な場合は、トピックとコメントのさまざまなアプローチについてお読みください。

EDIT

正式な定義によると、O(V+E)、O(V^2)、O(V^3)とO(V^V^V)はまだ正しいです。 BigOでは、私たちは最も遅く成長する機能を見つけようとしますが、あなたの複雑さは依然としてBigOです。

Answer 2

どちらの文も正しいです。彼らは矛盾していません。

任意のグラフに対して、リソース使用量はO（V ）です。しかし、疎なグラフが存在する可能性のある問題のあるドメインでは、リソース使用量はO（V + E）です。それはより多くの情報を提供します。

隣接リストは、一般的に、グラフがまばらになる可能性がある問題のあるドメインで使用されます。密なグラフの場合、通常は配列がより良い解決法です。グラフの問題を解決するための2つの可能なアルゴリズムを検討している場合、グラフについて知っていることを考慮する必要があります。アウトディグリーは制約されていますか？その場合、隣接リスト表現および関連するアルゴリズムがよりよい解決策であり得る。

複雑さの分析は単なる理論的なゲームではありません。これは実際のプログラミング問題に対する実用的な解決策についてあなたの考えを整理する方法です。

Answer 3

隣接リストのメモリ使用量は、ノード数とエッジ数の合計に正比例します。これは、各ノードに関連するエッジのリストが残され、各エッジが最大で2回表示されるためです（無向グラフではノードごとに1回、有向グラフでは1回）。つまり、スペース使用量はΘ（V + E）です。

O（V + E）とO（V ）という2つの異なる漸近的な境界をメモリ使用量に指定しました。これらの境界は両方とも正しいですが、一方は他方よりも厳しいです。 O（V + E）境界は、より正確には、空間使用、ノード数およびエッジ数に入る2つの半独立した量があり、より正確であることを示しています。 O（V ）のバウンドはそれほど正確ではありませんが、Vの観点からEの最大可能値を考慮することによって、ワーストケースバウンドを合計メモリ使用量に与えます。言い換えると、O（V + E）メモリー使用量を正確にピン止めしようとしている場合には、はるかに役立ちますが、ワーストケースのメモリー使用が心配な場合は、O（V ）の方が良いでしょう。

（「隣接リストはO（V + E）」という文は意味のある文ではありません）big-Oは関数の成長率を数値化するので、「隣接リストは95,201 " - オブジェクトを数値と比較しているので意味がありませんが、隣接リストの領域使用量は実際の数値であるため、「隣接リストの領域使用量はO（V + E）です」と言うことができます）