图和树遍历运行时
Graph and Tree Traversal Runtime
我对遍历树和遍历图的 运行 时间有点困惑。通常遍历一棵树的 运行 时间是 O(V) ，其中 v 是树中的节点数（即后序、中序或前序遍历），但对于图，它通常是 O(V+E) 给我们遍历每个顶点和边。
但是如果 O(V+E) 对于图是正确的，为什么 O(V+E) 对于树也不正确，因为我们在进行树遍历时也遍历了树的边缘。反之亦然，如果 O(V) 对于树是正确的，为什么对于图不是正确的，而且我们也访问每个节点一次？
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(+).
我对遍历树和遍历图的 运行 时间有点困惑。通常遍历一棵树的 运行 时间是 O(V) ，其中 v 是树中的节点数（即后序、中序或前序遍历），但对于图，它通常是 O(V+E) 给我们遍历每个顶点和边。 但是如果 O(V+E) 对于图是正确的，为什么 O(V+E) 对于树也不正确，因为我们在进行树遍历时也遍历了树的边缘。反之亦然，如果 O(V) 对于树是正确的，为什么对于图不是正确的，而且我们也访问每个节点一次？
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(+).