证明 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 可以使用此方法，但是，c 为 2，n 为 2 将起作用。n^2 怎么不是 n？
让我们假设n²在O(n) 中。
那么必须有一个c和一个n₀使得对于所有的n ≥ n₀，n² ≤ c*n（根据 O 符号的定义）。
设k = max(c, n₀) + 1。根据上述性质，我们有k² ≤ c*k（因为k > n₀），由此得出k ≤ c。
然而，通过构造k > c。这是一个矛盾。
因此我们的假设是错误的并且n²不能在O(n) 中。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句