为什么 BFS/DFS 的时间复杂度不是 O(E) 而不是 O(E+V)? [英] Why is time complexity for BFS/DFS not simply O(E) instead of O(E+V)?

问题描述

我知道在堆栈溢出中有一个类似的问题，有人问过，为什么 BFS/DFS 的时间复杂度不是简单的 O(V).

I know there's a similar question in stack overflow, where one person has asked, why time complexity of BFS/DFS is not simply O(V).

给出的适当答案是，在完整图的情况下，E 可以与 V^2 一样大，因此在时间复杂度中包含 E 是有效的.

The appropriate answer given was that E can be as large as V^2 in case of complete graph, and hence it is valid to include E in time complexity.

但是，如果 V 不能大于 E+1.那么，在这种情况下，时间复杂度中没有 V，应该可行吗?

But, if V cannot be greater than E+1. So, in that case not having V in the time complexity, should work?

推荐答案

如果给定 E = kV + c，对于一些实常数 k 和 >c 那么，
O(E + V) = O(kV + c + V) = O(V) = O(E) 你的论点是正确的.

If it is given that E = kV + c, for some real constants k and c then,
O(E + V) = O(kV + c + V) = O(V) = O(E) and your argument is correct.

这方面的一个例子是树木.

An example of this is trees.

一般来说(即没有任何先验信息)，然而，E = O(V^2)，因此我们不能比O做得更好(V^2).

In general (i.e., without any prior information), however, E = O(V^2), and thus we cannot do better than O(V^2).

为什么不总是只写 O(E)?

总是写 O(E + V) 的主要原因是为了避免歧义.

The primary reason for always writing O(E + V) is to avoid ambiguity.

例如，可能存在图中根本没有边的情况(即O(E) ~ O(1)).即使对于这种情况，我们也必须遍历每个顶点(O(V))，我们无法在O(1) 时间内完成.

For example, there might be cases when there are no edges in the graph at all (i.e. O(E) ~ O(1)). Even for such cases, we'll have to go to each of the vertex (O(V)), we cannot finish in O(1) time.

因此，一般只写O(E)是不行的.

Thus, only writing O(E) won't do in general.

这篇关于为什么 BFS/DFS 的时间复杂度不是 O(E) 而不是 O(E+V)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！