作者Lizstlin (Lizst)
看板CSSE
標題[問題] 幾題BigO證明還有觀念疑問
時間Tue Oct 5 01:24:12 2010
(因為是第一次在這邊PO文, 不大確定能否問這樣的問題, 如果不行就麻煩版主刪了,
不好意思喔 ^^")
因為老師上課沒講什麼證明範例, 書上也寫得少
自己找題目寫遇到不少瓶頸, 我知道基本觀念是
f(n) = O(n) iff there exist positive constants c and n0 s.t
f(n) <= c*g(n) for all n which n >= n0
那個c 在證明過程中可以隨便假設嗎?
因為總覺得要有一定範圍才可以, 像下面的證明我設1就不知道怎麼繼續下去
證明題如下:
show that n! = O(n^n)
show that n^(2^n) + 6*2(^n) = θ(2^(2^n))
show that n^2 * logn = θ(n^2) is incorrect
希望有大大不吝指教, 大致上提點我該如何下手, 謝謝 (拜)
如果不懂我再來問各位大大 ^^"
方才自己試了一下第一題, 不知道這樣對不對?
n! <= c*(n^n)
移項得 c* n[n^(n-1) - (n-1)!] >= 0
由 [n^(n-1) - (n-1)!] 得 n >= 1, 而 c >= 1
所以 n! = O(n^n) for all n which n>=1, and c>=1
這樣的感覺還是很像c 還有 n0 是推敲出來的 ~"~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.202.53
1F：→ hilorrk:exist和for all不一樣...你隨便帶一個進去當然不一定對 10/05 01:27
2F：→ hilorrk:也許你可以從"找出一個c"符合條件的方向去想 10/05 01:28
3F：→ hilorrk:像是第一題 1*2*...*n和n*n*...*n 你找不找的到c? 10/05 01:29
4F：推 nowar100:是拿來證明到最後，我們可以得到結論存在這個c 10/05 07:27
5F：→ nowar100:而不是先假設一個c去證吧 10/05 07:27
6F：→ Lizstlin:那麼, 可以提示(或是從中解一題當範例)講解給我嗎? 謝謝 10/05 10:12
7F：→ Lizstlin:比方第一題, 我試過左右除以n, 但是c 還是無法獨立求出 10/05 10:29
※ 編輯: Lizstlin 來自: 140.115.189.100 (10/05 11:12)
※ 編輯: Lizstlin 來自: 140.115.189.100 (10/05 11:19)
8F：推 cooper6334:不是就隨便湊一個c跟n0，只要有合就ok了嗎? 10/07 23:55