大歐米茄符號證明

Question

要顯示3N^2 - 25N =Ω（N^2）

For n ≥ n/2   for n ≥ 0 
    n – 25/3 ≥ 3n/(2 x 25) for n ≥ 9 
    3n^2 - 25n ≥ 9n^2/50  for n ≥ 9 

    3n2 - 25n ≥ c·n2 for n ≥ n0 where c=9/50 and n0 = 9 
Therefore, by definition 
     3n2 - 25n = Ω(n2). 

以上就是證明3N^2 - 25N =Ω（N^2）。爲什麼用n≥n/2？

n - 25/3≥3n /（2 x 25）如何導出？

Answer 1

我不知道爲什麼我們需要n> = n/2。我們做的需要的是n> = 0 => n * 3> = 0，所以我們可以在兩邊乘以第一個不等式3 * n。

（1）n - 25/3≥3n /（2 x 25）是一個簡單的線性不等式。通過做一些改造，我們得到：

（1）< =>（47/50）* N - 25/3> = 0 < =>（47/50）N> = 25/3 < =>ñ > =（25/3）（50/47）< => N> =一百四十一分之一千二百五十< => N> = 8 +141分之122

而且從我們得到這個不等式的所有成立上述n> = 9> 8 + 122/141。這只是你可以用來證明這個大歐米茄符號的不平等之一。希望我的回答有幫助。