O(V+E)与O(V²)是否等价？算法时间复杂度等价性问询

Great question—let’s break this down clearly because it’s easy to mix up what "linear time" refers to here, and how asymptotic notation applies to graph problems.

First, let’s clarify two key points:

• What defines "linear time": Linear time means the runtime scales linearly with the total input size (let’s call this input size n). For graphs, n is typically the total number of elements in the input—so for an adjacency list representation, that’s V + E (vertices plus edges).
• Asymptotic equivalence depends on the graph type: O(V+E) and O(V²) are not universally equivalent; it depends on how many edges the graph has.

Let’s walk through the two extreme cases: #

1. Dense graphs (including complete graphs)
   In a complete graph, every pair of vertices has an edge, so E = V(V-1)/2 ≈ V² for large V. Here, V + E ≈ V + V² = O(V²), so yes—O(V+E) simplifies to O(V²) in this case.
   But wait, is O(V²) "linear time" here? Only if you consider the total input size n = V + E ≈ V². In that scenario, O(n) (linear time relative to input size) is the same as O(V²). But if you’re measuring relative to the number of vertices V, this is quadratic time, not linear.

2. Sparse graphs
   For sparse graphs (like trees, where E = V-1 = O(V)), V + E ≈ V + V = O(V). Here, O(V+E) is O(V), which is not equivalent to O(V²)—since V² grows much faster than V as the number of vertices increases.

The core takeaway: #

• O(V+E) is a way to express runtime that adapts to the graph’s density: it’s linear relative to the input size n = V+E regardless of whether the graph is sparse or dense.
• O(V²) is only equivalent to O(V+E) when the graph is dense (i.e., when E = O(V²)). For sparse graphs, they’re completely different complexity classes.

So your observation about complete graphs is correct for that specific case, but it doesn’t hold for all graphs. The key is remembering that asymptotic notation depends on what you’re measuring the complexity against (input size vs. vertex count) and the structure of the graph itself.

内容的提问来源于stack exchange，提问作者Young Scooter