在無向圖的情況下,由於鄰接列表表示中有2E個邊,那麼爲什麼內存需求與有向圖相同?對於無向圖,爲什麼鄰接表表示的內存要求是θ(V + E)而不是θ(V + 2E)?
0
A
回答
0
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
相關問題
- 1. 在正規化,爲什麼我們θ^ 2使用,而不是θ?
- 2. 'v!== v'表達式檢查是什麼?
- 3. void * v []; v [i] = v [j];爲什麼這是正確的?
- 4. 諧波系列的大θ表示法
- 5. 什麼是ALT + v
- 6. WPF:爲什麼它是VisualTreeHelper.GetDrawing(Visual v)而不是Visual.GetDrawing()?
- 7. VueJS v-對於不想要的行爲
- 8. 瞭解cos(θ)和正弦(θ)
- 9. foreach中的$ k => $ v是什麼($ ex爲$ k => $ v)是什麼意思?
- 10. vtable中的'v'是什麼?
- 11. 關於n階乘的θ表示的漸近分析
- 12. 如果klgk =Θ(n),那麼k =Θ(n/lgn)
- 13. 緊(Θ)綁定
- 14. f(n)=Θ(f(n))是真的嗎?
- 15. 爲什麼我們要包含(Object o)而不是Containers(E e)?
- 16. 證明圖G =(V,E)至少有| v | - | E |部件
- 17. 什麼是「grep -v'^ $'file.txt」在做什麼?
- 18. 如果圖形存儲爲Adajacency List,爲什麼DFS在O(V + E)中運行?
- 19. 爲什麼你需要一個Hyper-V?
- 20. 如何使用求和符號證明算法是Θ(log n)?
- 21. 「文件系統輸出」對於時間-v是什麼意思?
- 22. 基於Θ(nlogn)的計算性能
- 23. 爲什麼內部類是TreeMap.Entry <K,V>通用?
- 24. vpath中的V代表什麼?
- 25. 如何將列表轉換爲地圖<K,V>但不是列表<V>
- 26. 寫有Θ(nlogn)的算法
- 27. 從鄰接表中創建無向圖
- 28. 什麼是用於燒烤的類型參數V用於
- 29. 「D:,H :, V:」是什麼意思在fbset?
- 30. 什麼是LinkedHashMap <k, v>?
你只需要存儲每個邊緣一次。用'i