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

答案：登入後查看
統計： A(8), B(16), C(51), D(12), E(0) #3233461

詳解 (共 2 筆)

#6096316
廣度優先搜索 (Breadth-firs...
(共 113 字，隱藏中）
前往觀看
6
0
#6420147

廣度優先搜尋 (Breadth-first search, BFS) 演算法的時間複雜度取決於圖的表示方式。

  1. 使用鄰接列表 (Adjacency List) 表示圖形時：

    • 每個節點會被訪問（進入佇列和從佇列取出）最多一次。訪問所有節點的時間複雜度與節點數 ∣V∣ 成正比，約為 O(∣V∣)。
    • 檢查每個節點的鄰居時，會遍歷其鄰接列表。每個邊在整個演算法執行過程中會被遍歷（檢查）最多兩次（對於無向圖），或一次（對於有向圖）。遍歷所有邊的時間複雜度與邊數 ∣E∣ 成正比，約為 O(∣E∣)。
    • 總體時間複雜度是節點和邊的處理時間總和，即 O(∣V∣+∣E∣)。

  2. 使用鄰接矩陣 (Adjacency Matrix) 表示圖形時：

    • 訪問每個節點後，需要檢查其所有 ∣V∣ 個可能的鄰居（對應矩陣中的一行）。這需要 O(∣V∣) 的時間。
    • 共有 ∣V∣ 個節點，所以總體時間複雜度為 O(∣V∣×∣V∣) = O(∣V∣2)。

在討論圖形演算法的時間複雜度時，如果沒有特別指明表示方法，通常會假設使用鄰接列表，因為它對於大多數圖形（尤其是稀疏圖）來說更有效率。題目詢問的是平均時間複雜度，但對於 BFS 使用鄰接列表而言，其時間複雜度無論在最好、最壞或平均情況下都是 O(∣V∣+∣E∣)。

比較選項： (A) O(∣V∣) - 未考慮邊的遍歷。 (B) O(∣V∣2) - 這是使用鄰接矩陣時的時間複雜度，或在最壞情況下（稠密圖使用鄰接矩陣）。 (C) O(∣V∣+∣E∣) - 這是使用鄰接列表時的標準時間複雜度。 (D) O(∣V∣log∣E∣) - 這不是 BFS 的時間複雜度。

因此，廣度優先搜尋 (BFS) 演算法在普遍使用的鄰接列表表示法下的時間複雜度是 O(∣V∣+∣E∣)。

答案是 (C) O(|V| + |E|)。

1
0

私人筆記 (共 1 筆)

私人筆記#7773319
未解鎖
廣度優先搜尋 (Breadth-firs...
(共 133 字，隱藏中）
前往觀看
1
0