證明或反駁n^2 - n + 2∈O（n）

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

什麼用反證法證明。建立你的一般情況，以便你試圖表明它是真實的，然後通過在每種情況下都必須是假的陳述，那麼整個證明必定是假的。

Answer 3

假定有一些C> 0和M> 0，使得對於所有N> M，

N^2 - N + 1 < = CN對於所有N> M

除n

N - 1 + 1/n的< = C爲所有N> M

等

n-1個< =對於所有的n> M.

ç

這是不可能的。