[理工] [資結]big-oh基本證明

作者: shownlin (哈哈阿喔)   2017-04-03 15:03:48
想請教此題證明
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囉?
作者: mloop (mloop)   2017-04-03 15:46:00
定義要for all n大於等於n0都要成立
作者: jerry900287 (滷蛋)   2017-04-04 01:59:00
配方法或許是一個好選擇http://i.imgur.com/31RSQHk.jpg
作者: hank292 (hank292)   2017-04-04 11:15:00
使f(n)>0公式解解兩根也解得出來
作者: mloop (mloop)   2017-04-04 22:21:00
這種證明其實你就可以直接找一個很大很大很大的數因為他只要證存在
作者: shownlin (哈哈阿喔)   2017-04-04 23:06:00
感謝各位回答我大概知道怎麼做了

Links booklink

Contact Us: admin [ a t ] ucptt.com