algorithm - 所有 O(n) 算法也是 O(n²) 吗？

Question

Big O 符号的正式定义是，如果我们有一个函数 f(n)(表示算法的时间和空间)和另一个函数 g(x)，并且有常量 c 和 no 使得 c*g(n) > f(x) 对于所有 n > 没有，然后 f(n) = O(g(n))。但是使用这个定义以及不断增长的二次函数总是会在某个点超过线性函数的事实，是否所有 O(n) 函数也是 O(n²)?或者更好地说，是 n = O(n²)?

Answer 1

是的，所有 O(n) 算法也是 O(n²)。当谈到 Big-O 时，人们对符号非常草率。为了清楚起见，我认为最好将 O(f) 概念化为返回一个 set 函数。使用集合表示法:

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