所有 O(n) 的算法也都是 O(n²) 的吗？

Question

Big O符号的正式定义是，如果我们有一个函数f(n)（用于算法的时间和空间）和另一个函数g(x)，并且有常数c和n0，使得对于所有的n > n0，都有c*g(n) > f(x)，那么f(n) = O(g(n))。但使用这个定义和一个增长二次方程总是会在某一点超过线性函数的事实，是否所有的O(n)函数也是O(n²)？或更准确地说，n = O(n²)吗？

- vacih86456

---

如果0*x^2 + B*x + C是二次方程，那么O(n)函数也是O(n²)，但通常被视为线性。 - chux - Reinstate Monica

确实，这就是为什么我们有大O符号的原因。 - David Eisenstat

Answer 1

是的，所有O(n)算法也是O(n²)。当涉及到大O符号时，人们通常很马虎。为了清楚起见，我认为最好将O(f)概念化为返回一组函数。使用集合符号表示：

n ∈ O(n) ⊂ O(n²)

- John Kugelman

Answer 2

当然。用 f(n)=n, g(n)=n^2, c=1, 和 n0=1，运用你的定义，可以看出 f 是 O(n^2)。你需要注意的是，当 n > n0 = 1 时，我们有：

n = 1*n = n0*n < n*n = n^2

类似的论点表明每个 O(n) 函数都是 O(n^2)。

本质上，大O符号提供了一个渐近上界。这个上界不一定要是紧确的；这就是大Theta符号存在的原因。

- Nate Eldredge