如何详细计算这段图算法代码的时间复杂度（大O表示法）

嘿，我来帮你理清这段代码的时间复杂度问题——你纠结的点很典型：不能只看嵌套循环的层数，得结合每个循环实际处理的元素和操作成本来拆解，咱们一步步来：

先明确代码的核心逻辑（顺便揪个小问题） #

这段代码是想计算每个顶点的接近中心性（closeness centrality），但先提个明显的逻辑bug：你的size = adj.length * adj.length，然后visited数组设为size长度，但外层循环的vertex是遍历adj.length个顶点——这说明你把顶点数和邻接矩阵的元素数搞混了！正常邻接矩阵是V*V的，其中V是顶点总数，所以visited数组长度应该是V（也就是adj.length），而不是V²。另外，pq.add(adj[u][i]+1)这行也有问题：你入队的是边权+1，不是顶点编号，后续从队列取出的u会是非法的顶点索引，应该改成pq.add(i)才对。

咱们先基于修正后的逻辑（顶点数为V=adj.length）来分析时间复杂度。

逐段拆解时间成本 #

1. 外层循环：遍历所有V个顶点，这部分是O(V)的时间。
2. 内层的优先队列遍历（类似Dijkstra算法）：
   • 每个顶点最多被加入队列一次（因为标记visited[u]后就不会再处理），所以队列的总入队/出队操作是O(V)次，每次优先队列的操作是O(log V)，这部分成本是O(V log V)。
   • 关键是嵌套在里面的for (int i = 0; i < V; i++)循环：每次处理一个顶点u时，都要遍历整个邻接矩阵的一行（V个元素），判断是否有边且未访问。每个顶点只会被处理一次，所以每次外层循环里，这个for循环的总执行次数是O(V²)（因为总共处理V个顶点，每个对应V次遍历）。

最终的时间复杂度 #

把外层和内层的成本加起来：
每次外层循环的时间是O(V log V + V²)，外层循环跑V次，所以总时间复杂度是O(V*(V² + V log V)) = O(V³)——因为V³是主导项，V² log V可以忽略。

回到你的原始困惑：

• 不能只看“两层循环”就判定为O(n²)，因为内层还有嵌套的O(V)循环，实际是三层嵌套的量级。
• 也不能因为第二个循环（while队列循环）不是全量执行就认为是O(n)，因为每次处理顶点时都会触发大量的邻接矩阵遍历操作，成本远高于线性级。

额外的优化建议 #

如果你的图是无权图，计算接近中心性完全没必要用优先队列，换成普通队列的BFS算法就行，这样每次外层循环的时间会降到O(V+E)（E是边数）：

• 稀疏图（E≈V）时，总时间复杂度会降到O(V²)，比现在的O(V³)快很多。
• 稠密图（E≈V²）时，还是O(V³)，但代码逻辑会更简洁。

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