隣接リスト表現の時間の複雑さ？

Question

私はこのリンクを経由して隣接リストの表現を行っています。

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 |）

---

理解の問題は何か分かりません。いくつかの助けがここ

Answer 1

ここで重要なのは、時間の複雑さが有効であるために、私たちはあらゆる状況カバーする必要があるということです必要：

• 外側のループが実行されたOを（| V |）にかかわらず、グラフ構造。
  • 我々はまったく縁を有していなかった場合でも、外側ループの各反復のために、我々は動作の一定数（O（1））を実行しなければならないであろうが、
  • 内側ループは、すべてのエッジに対して一度実行されますしたがって、deg（v）は現在のノードの次数であり、O（deg（v））回である。
  • したがって、外側ループの1回の実行の実行時間はO（1 + deg（v））です。 deg（v）は0になる可能性があるので、私たちは1を省略できないことに注意してください。しかし、まだその反復でいくつかの作業をする必要があります。
• 合計を集計すると、 1 + deg（v1）+ deg（v2）+ ...）= O（| V | + | E |）である。

前述のように、| E |外ループ内で排他的に行われる作業を説明するためには依然として が必要なように、かなり小さくなる可能性があります。したがって、| V |を削除することはできません。期間。