問題詳情

15. 下列何者是廣度優先搜尋 (Breadth-first search) 演算法的平均時間複雜度? (其中|V| 是圖形的節點數，|E|是圖形的邊數)
(A) O(|V|)
(B) O(|V|2)
(C) O(|V| + |E|)
(D) O(|V| log|E|)

參考答案

答案：C

統計：A:2,B:4,C:19,D:4,E:0

難度：計算中

用户評論

【不叫賭俠的陳小刀】評論

廣度優先搜索 (Breadth-first search) 演算法的平均時間複雜度是 (C) O(|V| + |E|)。在最壞情況下，該演算法需要訪問圖中的每個節點和每條邊，因此時間複雜度為線性時間，與節點數和邊數成正比。