這是我的偽代碼片段，用于在給定圖形 G 的情況下查找每個強連接組件 (SCC) 的 MST：
Number of SCC, K <- apply Kosaraju's algorithm on Graph G O(V E)
Loop through K components:
each K components <- apply Kruskal's algorithm
根據我所了解的，Kruskal 的演算法在 O(E log V) 時間內運行。
但是，我不確定回圈的最壞情況時間復雜度。我的想法是當 K = 1 時會發生最壞的情況。因此，大 O 時間復雜度只是 O(E log V)。
我不知道我的想法是否正確，或者它們是否正確，其理由是什么。
uj5u.com熱心網友回復：
是的，從直覺上講，您節省了將一個組件中的邊與另一個組件中的邊進行比較的成本。形式上，f(V, E) ? E log V 是一個凸函式，所以 f(V 1 , E 1 ) f(V 2 , E 2 ) ≤ f(V 1 V 2 , E 1 E 2 ) ，這意味著單獨處理多個組件的成本永遠不會超過一起處理它們。當然，正如您所觀察到的，可能只有一個組件，在這種情況下沒有任何節省。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335907.html
上一篇：無法訪問裝飾函式內的函式屬性