证明还是反驳 n^2 - n + 2 ？在）

Question

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

\n\n

为了反驳它，我需要证明否定：

\n\n

\xe2\x88\x80M > 0, \xe2\x88\x80N > 0, \xe2\x88\x83n > N s.t. n^2 - n + 1 < M\xc2\xb7n\n

\n\n

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

\n\n

\xe2\x88\x83M > 0, \xe2\x88\x83N > 0 s.t. \xe2\x88\x80n > N, n^2 - n + 1 \xe2\x89\xa5 M\xc2\xb7n\n

\n\n

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

\n

Answer 1

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

\n\n

f(n) \xe2\x88\x88 O(g(n) <--> (\xe2\x88\x83c,m>0) | (\xe2\x88\x80n>m) 0 < f(n) <= cg(n)\n\nlet f(n) = n^2 - n + 2\nlet g(n) = n\n\n(\xe2\x88\x83c,m>0) | (\xe2\x88\x80n>m) 0 < n^2 - n + 2 <= cn\n(\xe2\x88\x83c,m>0) | (\xe2\x88\x80n>m) 0 < n^2 - n <= cn\n(\xe2\x88\x83c,m>0) | (\xe2\x88\x80n>m) 0 < n^2 <= cn + n\n(\xe2\x88\x83c,m>0) | (\xe2\x88\x80n>m) 0 < n^2 <= 2cn + n\n(\xe2\x88\x83c,m>0) | (\xe2\x88\x80n>m) 0 < n^2 <= (2c+1)n\n\nlet C = 2c+1\n\n(\xe2\x88\x83C,m>0) | (\xe2\x88\x80n>m) 0 < n^2 <= Cn\n(\xe2\x88\x83C,m>0) | (\xe2\x88\x80n>m) 0 < n <= C\n\n(\xe2\x88\x83C,m>0) | (\xe2\x88\x80n>m) 0 < n <= C\n\nThere is no constant C s.t. 0 < n <= C for all sufficiently large n.\nTherefore, n^2 - n + 2 is not O(n)\n

\n