证明或反驳 n^2 - n + 2 ∈在）

Question

在我的算法分析课程中，我从算法中导出了函数 f(n) = n^2 - n + 2。现在我需要证明或反证 f(n) ∈ O(n)。显然不是，所以我几个小时以来一直试图反驳这一点，但不知道该怎么做。

为了反驳它，我需要证明消极的一面：

∀M > 0, ∀N > 0, ∃n > N s.t. n^2 - n + 1 < M·n

我已经尝试过前后工作，但似乎无济于事。我还试图证明，与我的判断相反，f(n) ∈ O(n):

∃M > 0, ∃N > 0 s.t. ∀n > N, n^2 - n + 1 ≥ M·n

...但没有成功。我到底做错了什么？

Answer 1

已经有一段时间了，但至少不是大θ......

f(n) ∈ O(g(n) <--> (∃c,m>0) | (∀n>m) 0 < f(n) <= cg(n)

let f(n) = n^2 - n + 2
let g(n) = n

(∃c,m>0) | (∀n>m) 0 < n^2 - n + 2 <= cn
(∃c,m>0) | (∀n>m) 0 < n^2 - n <= cn
(∃c,m>0) | (∀n>m) 0 < n^2 <= cn + n
(∃c,m>0) | (∀n>m) 0 < n^2 <= 2cn + n
(∃c,m>0) | (∀n>m) 0 < n^2 <= (2c+1)n

let C = 2c+1

(∃C,m>0) | (∀n>m) 0 < n^2 <= Cn
(∃C,m>0) | (∀n>m) 0 < n <= C

(∃C,m>0) | (∀n>m) 0 < n <= C

There is no constant C s.t. 0 < n <= C for all sufficiently large n.
Therefore, n^2 - n + 2 is not O(n)

Answer 2

假设有一些C> 0且M＞ 0 使得对于所有 n > 0 M,

n^2 - n + 1 <= Cn 对于所有 n > M

除以 n

n - 1 + 1/n <= C，对于所有 n > M

且因此

对于所有 n > n-1 <= C M.

这是不可能的。

Answer 3

反证法又如何呢？设置你的一般情况，以便你试图证明它是正确的，然后通过在每种情况下都必须是错误的陈述，那么整个证明必须是错误的。