大 O 表示法示例表明 N^2 不是 O(n)

Question

证明 n^2 不是 O(n)

f(n)=n^2
g(n) = n
c = 1
n_0=2

n^2 <= 1*n for all n_0 >= 2
4 <= 2 
4 is not less than or equal to 2. Therefore, n^2 is not O(n). 

我需要证明没有 c 可以使用此方法，但是 2 的 c 和 2 的 n 也可以。n^2 怎么不是n？

Answer 1

我们假设n\xc2\xb2 的时间复杂度为O(n)。

\n\n

那么必须有一个c和一个n\xe2\x82\x80，使得对于所有n \xe2\x89\xa5 n\xe2\x82\x80，n\xc2\xb2 \xe2\x89\xa4 c*n（通过O 符号的定义）。

\n\n

令k = max(c, n\xe2\x82\x80) + 1。根据上述属性，我们有k\xc2\xb2 \xe2\x89\xa4 c*k（因为k > n\xe2\x82\x80），由此得出k \xe2\x89\xa4 c。

\n\n

然而，通过构造k > c 。这是一个矛盾。

\n\n

因此我们的假设是错误的，n\xc2\xb2不能在O(n)中。

\n