근접도 목록에서 그래프 속도 계산

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 |)입니다.