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

Question

大O记法的正式定义是，如果我们有一个函数f(n)（时间和算法的空间）和其他功能g(x)，并有常数c，并no使得c*g(n) > f(x)所有n > no的话f(n) = O(g(n))。但是使用这个定义以及不断增长的二次函数总是会在某个时候超过线性函数的事实，所有O(n)函数都是真的O(n²)吗？或者更好地说，是n = O(n²)？

Answer 1

是的，所有 O(n) 算法也是 O(n²)。当谈到 Big-O 时，人们对符号非常草率。明确地说，我认为最好将 O(f) 概念化为返回一组函数。并使用集合符号：

n ? O(n) ? O(n²)