無向グラフの場合、隣接リスト表現のメモリ要件はなぜθ（V + E）ではなくθ（V + 2E）ではないのですか？

無向グラフの場合、隣接リスト表現に2Eのエッジが存在するため、有向グラフと同じメモリ要件が必要なのはなぜですか？無向グラフの場合、隣接リスト表現のメモリ要件はなぜθ（V + E）ではなくθ（V + 2E）ではないのですか？

各エッジを一度保存するだけで済みます。エッジが「i、j」であり、「i

シータ（V + E）=シータ（V + 2E）2は定数であり、big-O notationには差がないためです。

2017-05-07 16:13:53 gue

それは大きなOに違いはありませんが、シータはタイトな境界なので、どうですか？ –

定義を見てください。シータ（V + E）はビッグオー（V + E）とオメガ（V + E）にあることを意味します。だから、与えられた固定n0と定数はBig-Oにあり、私たちの場合定数は2です。もう一つの定数は1にしてください、それはOmegaにあります。 – gue

答えて