邻接列表表示的时间复杂度？

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 |术语。