algorithm - 从邻接表计算入度图

Question

我遇到了这个问题，其中需要从邻接表表示中计算图的每个节点的入度。

for each u
   for each Adj[i] where i!=u
     if (i,u) ∈ E
         in-degree[u]+=1

现在根据我的说法，它的时间复杂度应该是 O(|V||E|+|V|^2) 但我提到的解决方案却将其描述为等于 O (|V||E|)。

请帮忙告诉我哪一个是正确的。

Answer 1

计算入度的复杂度不是 O(|V||E|)，而是 O(|E|)。让我们考虑以下计算每个节点入度的伪代码:

for each u
  indegree[u] = 0;

for each u
  for each v \in Adj[u]
    indegree[v]++;

第一个循环的线性复杂度为 O(|V|)。对于第二部分:对于每个v，最内层的循环至多执行|E|次，而最外层的循环执行 |V|次。因此，第二部分似乎具有复杂性 O(|V||E|)。事实上，代码对每条边执行一次操作，因此更准确的复杂度是 O(|E|)。