[理工] 資結 Asymtoptic Notation

看板Grad-ProbAsk作者 (蜜蜂P助)時間7年前 (2018/10/03 00:07), 7年前編輯推噓8(8推 0噓 20→)
留言28則, 4人參與, 7年前最新討論串1/1
請問一題問題，看了板友討論還不是很懂 https://i.imgur.com/oTueIxe.jpg
第一個方法 用定義來推 https://i.imgur.com/8UtqweC.jpg
得出結論是 disprove 其中我覺得比較有問題的是我 assume 那邊 C1 > C3 第二個方法 用極限來推 (直接抄板友寫的) https://i.imgur.com/Q1qlzaa.jpg
得出結論是 pro 原命題 想問這樣兩個方法都OK嗎？不知道有沒有問題的地方？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.105.90.47 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1538496446.A.2EC.html ※ 編輯: befdawn (106.105.90.47), 10/03/2018 00:07:59
推
10/03 03:17, 7年前 , 1F
我覺得2才對欸，1不能確保c1和c3的關係吧？
10/03 03:17, 1F
→
10/03 03:17, 7年前 , 2F
small oh是對於所有c3,但是theta 只是至少存在一個c1而
10/03 03:17, 2F
→
10/03 03:17, 7年前 , 3F
已，所以應該不能確定c1-c3一定都大於0，因此不符合定義
10/03 03:17, 3F
推
10/03 03:51, 7年前 , 4F
覺得2
10/03 03:51, 4F
推
10/03 12:42, 7年前 , 5F
覺得都可以
10/03 12:42, 5F
→
10/03 12:42, 7年前 , 6F
10/03 12:42, 6F
→
10/03 12:42, 7年前 , 7F
法一寫到這裡應該就可以直接寫在theta裡了吧(? 小o的定
10/03 12:42, 7F
→
10/03 12:42, 7年前 , 8F
義是h永遠不會到F等級裡面，c取到很大好像也沒什麼意義，
10/03 12:42, 8F
→
10/03 12:42, 7年前 , 9F
如果用想的g就是在F等級裡面，h再怎麼大也不到F，拿g-h也
10/03 12:42, 9F
→
10/03 12:42, 7年前 , 10F
還是在F裡面
10/03 12:42, 10F
推
10/03 12:46, 7年前 , 11F
用法二好像比較嚴謹，不過意義應該是差不多的，小o/小ome
10/03 12:46, 11F
→
10/03 12:46, 7年前 , 12F
ga是大O/大omega的子集，極限定義好像也是把兩者視為一
10/03 12:46, 12F
→
10/03 12:46, 7年前 , 13F
樣的(沒有很熟極限法不知道有沒有說錯)
10/03 12:46, 13F
→
10/03 14:33, 7年前 , 14F
想問sky大大為什麼你的那張圖可以直接寫theta，可是
10/03 14:33, 14F
→
10/03 14:33, 7年前 , 15F
左邊是小於沒有等號(？ 雖然白話文的解釋還蠻合理
10/03 14:33, 15F
→
10/03 14:33, 7年前 , 16F
的但數學部分我還看不懂QQ
10/03 14:33, 16F
推
10/03 15:01, 7年前 , 17F
有點原po說的assume c1>c的感覺吧，因為以小o的定義c取
10/03 15:01, 17F
→
10/03 15:01, 7年前 , 18F
太大好像也沒意義，但直接寫出assume那句感覺就怪怪的
10/03 15:01, 18F
→
10/03 15:02, 7年前 , 19F
如果用法一我可能會寫是theta，然後補上白話文說明，如果
10/03 15:02, 19F
→
10/03 15:02, 7年前 , 20F
數學式要嚴謹的話感覺法二好一點
10/03 15:02, 20F
推
10/03 15:13, 7年前 , 21F
突然想到一個寫法，因為小o是for any c，所以取c=c1-1也
10/03 15:13, 21F
→
10/03 15:13, 7年前 , 22F
要對，這樣減下來f就在1F跟c2F之間，就是theta了，不知道
10/03 15:13, 22F
→
10/03 15:13, 7年前 , 23F
這樣寫可不可以
10/03 15:13, 23F
推
10/05 16:09, 7年前 , 24F
小o是for any c的話，應該是無論c的值為何，嚴格小
10/05 16:09, 24F
→
10/05 16:09, 7年前 , 25F
於都要成立，如果取c=c1-1這樣好像不太合理耶
10/05 16:09, 25F
推
10/05 20:44, 7年前 , 26F
應該不會不合理(吧? for any就是代什麼都要對，應該希
10/05 20:44, 26F
→
10/05 20:44, 7年前 , 27F
望範圍能夾越小越好，不會故意去取很大，有問題的應該是c
10/05 20:44, 27F
→
10/05 20:44, 7年前 , 28F
1如果<1取c1-1就變負的了
10/05 20:44, 28F
‣ 更多 befdawn 的文章
文章代碼(AID): #1RivU-Bi (Grad-ProbAsk)