[解決済み] 隣接リスト表現の時間複雑性？

質問

隣接リストの表現について、このリンク先を調べています。

http://www.geeksforgeeks.org/graph-and-its-representations/

以下のようなコードの一部に、簡単な疑問があります。

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->V; ++v)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl)
        {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

というのは、ここではすべての V というループが実行されます。 d 回である。ここで、dは各頂点の次数である。

だから、時間的な複雑さは、まるで

d0 + d1 + d2 + d3 ....... +dV where di is the degree of each vertex.

これらすべての合計はO(E)ですが、リンク先では時間の複雑さはO(|V|+|E|)とあります。

何が問題で理解できていないのかがわからない。何かお手伝いできることはないでしょうか。

どのように解決するのですか？

ここで重要なのは、時間の複雑さが成立するためには、あらゆる可能な状況をカバーする必要があるということです。

• 外周ループはグラフ構造に関係なくO(|V|)実行される。
  • 仮にエッジが全くなかったとしても、外周ループを1回繰り返すごとに、一定数の演算（O(1)）をしなければならない
  • 内部ループは各エッジに対して1回ずつ実行されるため、O(deg(v))回となる（deg(v)は現在のノードの次数を表す）。
  • したがって、外側ループの1回の反復の実行時間はO(1 + deg(v))である。なぜなら、deg(v) が 0 であっても、その繰り返しで何らかの作業をする必要があるからです。
• これらをまとめると、実行時間はO(|V| * 1 + deg(v1) + deg(v2) + ...) = O(|V| + |E|)となります。

前述したように、｜E｜はむしろ小さくすることが可能で、その場合でも は、外側のループだけで行われる仕事を考慮する必要があります。従って、単純に｜V｜項を削除することはできない。