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

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");
    }
}

---

因为,这里执行每个Vwhile循环,比如说dd是每个顶点的度数.

所以,我认为时间的复杂性就像

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