tree - 图和树遍历运行时

Question

我对遍历树和遍历图的运行时间有点困惑。通常，遍历一棵树的运行时间是 O(V)，其中 v 是树中节点的数量(即后序、中序或先序遍历)，但对于图来说，它通常是 O(V+E)，因为我们要遍历每个顶点和边缘。 但是，如果 O(V+E) 对于图来说是正确的，为什么 O(V+E) 对于树来说不正确，因为我们在进行树遍历时也在遍历树的边。反之亦然，如果 O(V) 对于树来说是正确的，为什么对于图来说不正确，而且我们也访问每个节点一次？

Answer 1

why is O(V+E) not true for tree as well...?

实际上 O(𝑉+𝐸) 对于树遍历来说也是成立的，但是这个表达式在树的情况下可以简化，因为对于树我们有这样的等式:

      𝐸 = 𝑉 - 1

换句话说，一棵树的边比它的节点少一个。所以这意味着以下表达式是等效的:

      O(𝑉+𝐸) = O(2𝑉-1)

在描述渐近复杂度的大 O 表示法中，我们只需考虑最高阶的项，其系数不相关。所以这相当于 O(𝑉)。我们也可以用类似的推理来表示 O(𝐸)。

Or vice versa, if O(V) is true for tree why is it not true for graph as well...?

因为一般来说，𝐸 和 𝑉 之间没有关系。

例如，密集图的边数将多于顶点数。遍历图时，您通常会访问一个顶点，然后检查与该顶点连接的每条边，以查看连接的相邻顶点是否仍然需要访问。因此，要做的工作与边数成线性关系。

另一方面，一个断开图(可能是一个森林)的顶点可能比边多得多。在遍历图形时，您将再次需要检查作为其邻居的每个顶点。在这种情况下，您可能会发现根本没有邻居的顶点，但需要完成工作。所以你至少有与顶点数量成线性关系的工作。

为了涵盖两个极端，我们可以说复杂度为 O(𝑋)，其中 𝑋 是 𝑉 或 𝐸 中最大​​的一个。所以我们有:O(max(𝑉, 𝐸))。请注意，这相当于 O(𝑉+𝐸)。