如何分析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时间复杂性？

回答

相关问题