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

Question

我正在通过这个 link 来表示邻接表。

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 while 循环执行 d 次，其中 d 是每个顶点的度数。

所以，我认为时间复杂度就像

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

所有这些总和为 O(E)，但是 link 表示时间复杂度为 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|任期。