对于无向图，为什么邻接表表示的内存要求是θ（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

回答