拓扑排序Kahn算法时间复杂度疑问：为何是O(V+E)而非O(V*E)

复杂度计算逻辑说明 #

你对嵌套循环的时间复杂度计算存在误区，这部分统计入度的代码时间复杂度确实为 O(V+E)，而非你认为的 O(VE)*，核心原因如下：

• 外层循环遍历全图所有顶点，执行总次数恰好等于顶点总数 V，这部分的固定开销为 O(V)
• 内层循环仅遍历当前顶点对应的所有出边，所有顶点的出边数量求和后正好等于全图的总边数 E，也就是说所有内层循环的执行总次数为 E，这部分总开销为 O(E)

常见误解纠正 #

你会算出 O(VE)* 的核心原因是默认内层循环每次都需要遍历全图所有 E 条边，但实际场景中每个内层循环只会处理当前顶点关联的出边，不会重复遍历其他顶点的边。

举个简单的例子：假设全图有3个顶点，顶点A有2条出边，顶点B有3条出边，顶点C没有出边，总边数E=5，内层循环的总执行次数为2+3+0=5，恰好等于E，远小于V*E=15。

对应到你写的Python代码：

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

注释中# O(V) * O(E) = O(V * E). ??的推导不成立，因为单轮内层循环的复杂度是O(当前顶点出度)而非O(E)，所有内层循环的总复杂度求和后为O(E)，和外层的O(V)相加后最终总复杂度就是O(V+E)。

内容的提问来源于stack exchange，提问作者Factral