如何分析DAG時間複雜性？

我正在學習拓撲排序和一般圖形。我使用DFS實現了一個版本，但我無法理解爲什麼維基百科頁面顯示這是O（| V | + | E |）並分析它的時間複雜度，以及| V | + | E |和一般n^2。首先，我有兩個for循環，邏輯表示它會是（n^2），但是在任何DAG（或樹）中都有n-1個邊和n個頂點？這與n^2有什麼不同，如果我們可以刪除「-1」爲非顯着值？如何分析DAG時間複雜性？

graph = { 
1:[4, 5, 7], 
2:[3,5,6], 
3:[4], 
4:[5], 
5:[6,7], 
6:[7], 
7:[] 
} 



from collections import defaultdict 

def topological_sort(graph): 
    ordered, marked = [], defaultdict(int) 

    while len(ordered) < len(graph): 
     for vertex in graph: 
      if marked[vertex]==0: 
       visit(graph, vertex, ordered, marked) 

return ordered 

def visit(graph, n, ordered, marked): 
    if marked[n] == 1: 
     raise 'Not a DAG' 

    marked[n] = 1 

    for neighbor in graph.get(n): 
     if marked[neighbor]!=2: 
      visit(graph, neighbor, ordered, marked) 

    marked[n] = 2 

    ordered.insert(0, n) 


def main(): 
print(topological_sort(graph)) 

main()

來源

2016-12-16 driftdrift

對於其他人沒有注意到它們的初始化：https：//en.wikipedia.org/wiki/Directed_acyclic_graph –

它是'O（| V | + | E |）'，因爲每個節點都被訪問過一次，每個邊都被訪問一旦。如果一個節點被訪問兩次，它不會是一個DAG，因爲會有一個循環 –

正確執行工作在O(|V| + |E|)時間，因爲它通過每一個角落和每一個頂點最多一次。對於完整的（或幾乎完整的圖），它與O(|V|^2)是一樣的。但是，當圖很稀疏的時候會好得多。

您執行的是O(|V|^2)而不是O(|V| + |E|)。這兩個嵌套的循環：

while len(ordered) < len(graph): 
    for vertex in graph: 
     if marked[vertex]==0: 
       visit(graph, vertex, ordered, marked)

做了最壞的1 + 2 ... + |V| = O(|V|^2)迭代（例如，對於空圖）。你可以通過擺脫外部循環來輕鬆修復（這很簡單：只需刪除while循環，不需要它）。

來源

2016-12-16 20:28:05 kraskevich

噢好吧，我最初將wikipedia psuedocode轉換爲代碼，並且它有一個while循環。 – driftdrift

@driftdrift維基百科代碼略有不同。他們在去之前去掉頂點。沒有頂點被認爲是兩次，所以它們的時間複雜度是'O（V + E）'。它看起來像一個小細節，但事實證明這很重要。 – kraskevich

如何分析DAG時間複雜性？

回答

相關問題