从邻接列表中的图形程度计算

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 |),计算indegrees的复杂性是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 |).