python - 如何分析DAG时间复杂度？

Question

我正在学习拓扑排序和一般图形。我在下面使用 DFS 实现了一个版本，但我无法理解为什么维基百科页面说这是 O(|V|+|E|) 并分析它的时间复杂度，以及 |V|+|E| 之间的区别和一般的 n^2。

首先，我有两个 for 循环，逻辑上说它是 (n^2)，但在任何 DAG(或树)中，是否都有 n-1 条边和 n 个顶点？如果我们可以删除非显着值的“-1”，这与 n^2 有什么不同？

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()

Answer 1

正确的实现在 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 循环即可。您不需要它)。