鄰接列表表示的時間複雜度？

Question

我正在通過此鏈接查看鄰接列表表示。

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

我有一個代碼中的一些部分簡單的疑問如下：在執行循環說d倍，其中d是

// 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每個頂點的度數。

所以，我覺得時間複雜度爲像

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

這一切都總結了O（E），但鏈接說，時間複雜度爲O（| V | + | E |）

---

不知道理解有什麼問題。一些幫助這裏

Answer 1

這裏最重要的是，時間複雜度是有效的，我們需要涵蓋所有可能的情況，需要：

• 執行外環O（| V |）不管圖結構。
  • 即使我們有沒有棱角可言，對於外部循環的每次迭代，我們必須做的操作的常數（O（1））
  • 內環爲每條邊執行一次，因此O（deg（v））次，其中deg（v）是當前節點的度數。
  • 因此，外循環的單次迭代的運行時間是O（1 + deg（v））。請注意，我們不能忽略1，因爲deg（v）可能爲0，但我們仍然需要在該迭代中做一些工作
• 總結一下，我們得到一個運行時間爲O（| V | * 1 + deg（v1）+ deg（v2）+ ...）= O（| V | + | E |）。

如前所述，| E |可能相當小，因此我們仍然需要 來解釋僅在外部循環中完成的工作。因此，我們不能簡單地刪除| V |術語。