线性时间的拓扑排序复杂度？

Question

我正在尝试计算 python 中实现的 Kahn 算法的算法复杂度，我看到了这篇文章：https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/ 在计算所有节点度的代码部分有这个

for each node in Nodes
    If (list[node].size()!=0) then
        for each dest in list
            indegree[dest]++;

文中说复杂度为O(V+E)，为什么呢？有两个嵌套的for，不应该是O(V*E)吗？

我在 python 中写了一个这样的实现：

for vertex in graph:                    # O(V) * O(E) = O(V * E). ??
    for edge in graph[vertex]:          # O(E)+O(1) => O(E)
        indegree[dege] += 1             # O(1)

V = 图的顶点数

E = 边数

Answer 1

具体而言，复杂度将更准确地表述为 V + 2E（总体复杂度为 class O(V + E)。我们对每个顶点迭代一次，对每个边迭代两次（对于它所连接的每个顶点一次） - 假设 graph[vertex] returns 只有连接到该顶点的边，这似乎是算法的意图。

嵌套循环确实通常表示*而不是+，其中涉及复杂性。然而，如果内循环迭代的对象与外循环不同，我们有时会遇到这样的情况——在 all 内循环中有特定且恒定数量的事物，以某种方式分布在外循环的每个元素。

在这种情况下，我们确实可以将复杂度写为 O(V + E)，因为我们迭代的 E 的数量与 [=17= 的数量没有任何关系] 我们迭代 - 只是我们这样做的顺序，复杂性并不真正关心。

Answer 2

这是图形算法中经常使用的表示法，用于指定算法对图形密度的依赖程度。 E 始终是 O(V^2)，但该界限可能并不紧密。假设没有很多边（例如，一棵树，正好有 V - 1 条边）。然后O(V + E) = O(V + V) = O(2V) = O(V).

现在考虑一个稠密图（例如，一个完整的图，其中至少有 V(V-1) 个边，如果允许自边则更多）。现在 O(V+E) = O(V + V^2 - V) = O(V^2).

在 O(...) 中，+ 的行为有点像 max：总体复杂度由两个加数中较大的一个决定。这基本上为您提供了一种 shorthand 来显示复杂性如何沿两个轴增长：一个是顶点的数量，两个是边的密度。

线性时间的拓扑排序复杂度？

Topological sort complexity in linear time?

python-3.x

time-complexity

complexity-theory

topological-sort