big-o - O(n) 的算法怎么可能也是 O(n^2)、O(n^1000000)、O(2^n)？

Question

所以这个问题的答案What is the difference between Θ(n) and O(n)?

指出“基本上，当我们说算法是 O(n) 时，它也是 O(n2)、O(n1000000)、O(2n)，...但 Θ(n) 算法不是 Θ(n2)。 ”

我理解大 O 代表上限或最坏的情况，我不明白 O(n) 也是 O(n2) 以及其他比 O(n) 更糟糕的情况。

也许我有一些根本的误解。请帮助我理解这一点，因为我已经挣扎了一段时间。

谢谢。

Answer 1

想想 big-Oh 的含义是有帮助的:如果一个函数是 O(n)，那么 c*n ，其中 c 是某个正数，是上限。如 c*n是一个上限，很明显，对于整数，c*n^2也将是一个上限。还有c*n^3 , c*n^4 , c*n^1000 ， 等等。

下图显示了函数的增长，它是函数“右侧”的上限；即，它在较小的 n 上增长得更快.