邻接表表示法的时间复杂度是多少？

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

---

不确定理解上有什么问题。需要一些帮助。

- Garrick

---

假设该图没有边。算法需要多长时间？ - user2357112

@user2357112 我们需要检查或扫描每个顶点一次，对吧？但这是一个嵌套循环，所以时间复杂度不应该是这样的吗？ - Garrick

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| 项。

- Tobias Ribizel

---

如果有一个n次迭代的外部循环，那么时间复杂度应该是O(V * E)，对吗？我错过了什么？ - Midhunraj R Pillai

边的总数E只是循环单次迭代中所需工作量的非常悲观的上限。您可以通过注意到我们仅查看每个顶点v的“度数（degree(v))”出边以及一些额外的常数工作（读取v的头指针）来做得更好。所有度数之和是边数的两倍。因此，总体而言，我们每个顶点和每条边只需要恒定的工作量（如最后一个要点所总结的）。 - Tobias Ribizel

@MidhunrajRPillai 这不是一个外部循环遍历所有的V和内部循环遍历所有的E。内部循环是针对每个边缘的度数，这不是一个常数。 - CraigDavid