作者shownlin (哈哈阿喔)
看板Grad-ProbAsk
標題[理工] [資結]big-oh基本證明
時間Mon Apr 3 15:03:48 2017
想請教此題證明
f(n)=5n^2+8n-9 → f(n)=O(n^2)
答案給的是取c=6
→ 5n^2+8n-9 ≦ 6n^2
→ n^2-8n+9 ≧ Φ
→ n ≧ 7 = n0 得證
想請問此題取c=6時，n若代1
5+8-9 ≦ 6
也是成立
那為何n0要取7呢？
因為n= 2～6都不成立的關係嗎？
所以找到一個能使關係式成立的n外
還要驗證比這個n更大的數也能成立才能取其為n0囉？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.217.226.89
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1491203030.A.946.html
※ 編輯: shownlin (49.217.226.89), 04/03/2017 15:20:31
推 mloop: 定義要for all n大於等於n004/03 15:46
→ mloop: 都要成立04/03 15:46
知道了，感恩
想在請問一下
找出若要使函式f(n)≧0
n的最小值有什麼方法嗎
還是單純看到n^2-8n就猜n0最小會是7
※ 編輯: shownlin (49.217.226.89), 04/03/2017 17:36:09
推 jerry900287: 配方法或許是一個好選擇 04/04 01:59
推 hank292: 使f(n)>0公式解解兩根也解得出來 04/04 11:15
推 mloop: 這種證明其實你就可以直接找一個很大很大很大的數 04/04 22:21
→ mloop: 因為他只要證存在 04/04 22:22
→ shownlin: 感謝各位回答 04/04 23:06
→ shownlin: 我大概知道怎麼做了 04/04 23:08