作者:
oao521 (台灣金正日)
2020-02-16 11:18:46https://i.imgur.com/S9mOpVV.jpg
https://i.imgur.com/h5ghXCj.jpg
請問這一題D選項
只寫 a, b are real constants
那...請問
若b為負數時，要怎麼證呢？
答案給D is correct
作者:
maple205 (艾瑞克)
2020-02-16 11:21:00時間複雜度不會是負的 沒有演算法會因為output越大做得時間反而變少
作者:
oao521 (台灣金正日)
2020-02-16 11:30:00所以這一題雖然題目只說b是實數但是我們要自動假設其實題目只考慮正實數的情況？也就是說我們寫題目的時候 就先假設前提：題目不考慮b為負數這樣理解對嗎？
作者:
DLHZ ( )
2020-02-16 11:35:00在b為負數的情況下 theta內的n^b乘上任一常數在n趨近於無趣大的情況下依然是0 無法得出大於左方函數的部分 我認為要正確應該改成omega或者for some positive constant b修正一下 兩者在n夠大後都是0 應該是沒問題才對基於上面解釋的 我認為對啦 至於考試到底怎樣就看個人吧用極限說明我是覺得蠻好用的 好像有其他方法 不過我沒去讀
作者: hit5180214 (hit5180214) 2020-02-16 12:21:00
負的也會成立，當b是正的會被限制在某個範圍間，取倒數之後也當然會被bound 住b由正轉負，係數取倒數就出來了啊
作者:
zuchang (chang)
2020-02-16 23:59:00直接用BigO定義,找出存在一個c來證就好,用極限也很好