對於無向圖，爲什麼鄰接表表示的內存要求是θ（V + E）而不是θ（V + 2E）？

在無向圖的情況下，由於鄰接列表表示中有2E個邊，那麼爲什麼內存需求與有向圖相同？對於無向圖，爲什麼鄰接表表示的內存要求是θ（V + E）而不是θ（V + 2E）？

你只需要存儲每個邊緣一次。用'i

Theta（V + E）= Theta（V + 2E）因爲2是一個常數並且在big-O notation中沒有差別。

2017-05-07 16:13:53 gue

它在大O方面沒有什麼區別，但是theta自從theta是一個更緊的約束呢？ –

看看定義。 Theta（V + E）表示它在Big-O（V + E）和Omega（V + E）中。所以對於給定的但固定的n0和常數，它在Big-O中，在我們的例子中，常數是2.對於另一個常數，讓它爲1，它在Ω中。 – gue

回答