26考研408数据结构真题:关于邻接表存储的时间复杂度的分析

大家好，我是「阑梦清川」

今天我们来看一下26考研408真题里面，数据结构第六题关于邻接表存储的时间复杂度问题的相关分析

这个问题主要讨论的是「在有向图中使用邻接表存储时，计算某个顶点入度的时间复杂度」。

首先，我们需要回顾一下核心概念。「在邻接表存储结构中」：

1. 「每个顶点都有一个单链表，存储的是从该顶点出发的所有边。」
2. 「出度与入度」：(a) 「出度表示从该顶点出去的边的个数」，我们只需查看该顶点的链表长度即可。(b) 「入度表示指向该顶点的边的个数。」

为了找出一个特定顶点 V 的入度，我们需要知道有哪些顶点指向了 V。「在标准的邻接表中，关于"谁指向了 V"的信息散落在所有顶点的出边链表里面。因此，我们需要遍历每一个顶点的链表，才能找全所有指向 V 的信息。」

关于操作的总数：

1. 「我们需要访问 V 个顶点的头指针。」
2. 「我们需要遍历图中所有的边（E），检查每条边的终点是否指向我们想要找的这个顶点 V。」

因此，「总的时间开销（即总的时间复杂度）是 O(V + E)。」

但题目中给出了一个等价的表达式 O(max(V, E))。**在渐进时间复杂度分析中，O(V + E) 和 O(max(V, E)) 是等价的。**下面解释一下原因：

**在大 O 渐进表示法中，我们关注的是增长最快的那一项。**假设有两个变量 A 和 B：

1. 如果 A ≥ B，那么 A + B ≤ 2A。根据定义，此时的时间复杂度就是 O(A)。
2. 如果 A < B，那么 A + B < 2B。此时的时间复杂度就是 O(B)。

由此可见，「无论谁大，结果总是取决于两者中最大的那一个。所以我们说 O(V + E) 等价于 O(max(V, E))。这代表算法运行时间的上界是由任务中最沉重的部分决定的。」

这也就是题目对应的答案。

我是「阑梦清川」，希望得到您的关注