所有 O(n) 算法也是 O(n²) 吗？
Are all O(n) algorithms O(n²) too?
Big O 表示法的正式定义是，如果我们有一个函数 f(n)（用于算法的时间和 space）和另一个函数 g(x)，并且有常量 c 和 no 使得所有 n > no 的 c*g(n) > f(x)，然后 f(n) = O(g(n))。但是使用这个定义和增长的二次函数总是会在某个点超过线性函数的事实，所有 O(n) 函数也是 O(n²) 是真的吗？或者更好地说，是 n = O(n²)?
是的，所有 O(n) 算法也是 O(n²)。当涉及到 Big-O 时，人们对符号非常草率。明确地说，我认为最好将 O(f) 概念化为返回 set 函数。使用集合表示法：
n ∈ O(n) ⊂ O(n²)
当然可以。将您的定义应用到 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 是关于提供渐近 上限。没有要求这个上限是 sharp；这就是大 Theta 的用途。
Big O 表示法的正式定义是，如果我们有一个函数 f(n)（用于算法的时间和 space）和另一个函数 g(x)，并且有常量 c 和 no 使得所有 n > no 的 c*g(n) > f(x)，然后 f(n) = O(g(n))。但是使用这个定义和增长的二次函数总是会在某个点超过线性函数的事实，所有 O(n) 函数也是 O(n²) 是真的吗？或者更好地说，是 n = O(n²)?
是的，所有 O(n) 算法也是 O(n²)。当涉及到 Big-O 时，人们对符号非常草率。明确地说，我认为最好将 O(f) 概念化为返回 set 函数。使用集合表示法：
n ∈ O(n) ⊂ O(n²)
当然可以。将您的定义应用到 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 是关于提供渐近 上限。没有要求这个上限是 sharp；这就是大 Theta 的用途。