[理工] 資結 Asymtoptic Notation

作者: befdawn (橙花雨露)   2018-10-03 00:07:23
請問一題問題,看了板友討論還不是很懂
https://i.imgur.com/oTueIxe.jpg
第一個方法 用定義來推
https://i.imgur.com/8UtqweC.jpg
得出結論是 disprove
其中我覺得比較有問題的是我 assume 那邊 C1 > C3
第二個方法 用極限來推 (直接抄板友寫的)
https://i.imgur.com/Q1qlzaa.jpg
得出結論是 pro 原命題
想問這樣兩個方法都OK嗎?不知道有沒有問題的地方?
作者: kyrie77 (NTU KI)   2018-10-03 03:17:00
我覺得2才對欸,1不能確保c1和c3的關係吧?small oh是對於所有c3,但是theta 只是至少存在一個c1而已,所以應該不能確定c1-c3一定都大於0,因此不符合定義
作者: eggy1018 (羅密歐與豬過夜)   2018-10-03 03:51:00
覺得2
作者: skyHuan (Huan)   2018-10-03 12:42:00
覺得都可以https://imgur.com/KoVxFOc.jpg法一寫到這裡應該就可以直接寫在theta裡了吧(? 小o的定義是h永遠不會到F等級裡面,c取到很大好像也沒什麼意義,如果用想的g就是在F等級裡面,h再怎麼大也不到F,拿g-h也還是在F裡面用法二好像比較嚴謹,不過意義應該是差不多的,小o/小omega是大O/大omega的子集,極限定義好像也是把兩者視為一樣的(沒有很熟極限法不知道有沒有說錯)
作者: kcilao110779 (kcilao)   2018-10-03 14:33:00
想問sky大大為什麼你的那張圖可以直接寫theta,可是左邊是小於沒有等號(? 雖然白話文的解釋還蠻合理的但數學部分我還看不懂QQ
作者: skyHuan (Huan)   2018-10-03 15:01:00
有點原po說的assume c1>c的感覺吧,因為以小o的定義c取太大好像也沒意義,但直接寫出assume那句感覺就怪怪的如果用法一我可能會寫是theta,然後補上白話文說明,如果數學式要嚴謹的話感覺法二好一點突然想到一個寫法,因為小o是for any c,所以取c=c1-1也要對,這樣減下來f就在1F跟c2F之間,就是theta了,不知道這樣寫可不可以
作者: kcilao110779 (kcilao)   2018-10-05 16:09:00
小o是for any c的話,應該是無論c的值為何,嚴格小於都要成立,如果取c=c1-1這樣好像不太合理耶
作者: skyHuan (Huan)   2018-10-05 20:44:00
應該不會不合理(吧? for any就是代什麼都要對,應該希望範圍能夾越小越好,不會故意去取很大,有問題的應該是c1如果<1取c1-1就變負的了

Links booklink

Contact Us: admin [ a t ] ucptt.com