对于无向图,为什么邻接表表示的内存要求是θ(V + E)而不是θ(V + 2E)?
答
Theta(V + E)= Theta(V + 2E)因为2是一个常数并且在big-O notation中没有差别。
+0
它在大O方面没有什么区别,但是theta自从theta是一个更紧的约束呢? –
+0
看看定义。 Theta(V + E)表示它在Big-O(V + E)和Omega(V + E)中。所以对于给定的但固定的n0和常数,它在Big-O中,在我们的例子中,常数是2.对于另一个常数,让它为1,它在Ω中。 – gue
你只需要存储每个边缘一次。用'i