推 maple205: 時間複雜度不會是負的 沒有演算法會因為output越大 02/16 11:21
我是指b<0的情況
→ maple205: 做得時間反而變少 02/16 11:21
→ oao521: 所以這一題 02/16 11:30
→ oao521: 雖然題目只說b是實數 02/16 11:30
→ oao521: 但是我們要自動假設其實題目只考慮正實數的情況？ 02/16 11:30
→ oao521: 也就是說我們寫題目的時候 就先假設前提：題目不考慮b為負 02/16 11:32
→ oao521: 數 02/16 11:32
→ oao521: 這樣理解對嗎？ 02/16 11:33
→ DLHZ: 在b為負數的情況下 theta內的n^b乘上任一常數在n趨近於無趣 02/16 11:35
→ DLHZ: 大的情況下依然是0 無法得出大於左方函數的部分 我認為要正 02/16 11:35
→ DLHZ: 確應該改成omega或者for some positive constant b 02/16 11:35
→ DLHZ: 修正一下 兩者在n夠大後都是0 應該是沒問題才對 02/16 11:38
考試時需要考慮b<0的情況嗎？
那這樣也可以說b<0時
(n+a)^b=theta(n^b)亦成立？
證明是用極限limit來證明嗎？
※ 編輯: oao521 (1.200.210.32 臺灣), 02/16/2020 11:45:14
※ 編輯: oao521 (1.200.210.32 臺灣), 02/16/2020 11:46:26
※ 編輯: oao521 (1.200.210.32 臺灣), 02/16/2020 11:54:17
→ DLHZ: 基於上面解釋的 我認為對啦 至於考試到底怎樣就看個人吧 02/16 11:56
→ DLHZ: 用極限說明我是覺得蠻好用的 好像有其他方法 不過我沒去讀 02/16 11:57
感謝大大的解釋：)
※ 編輯: oao521 (1.200.210.32 臺灣), 02/16/2020 12:10:30
推 hit5180214: 負的也會成立，當b是正的會被限制在某個範圍間，取倒 02/16 12:21
→ hit5180214: 數之後也當然會被bound 住 02/16 12:21
→ hit5180214: b由正轉負，係數取倒數就出來了啊 02/16 12:22
推 zuchang: 直接用BigO定義,找出存在一個c來證就好,用極限也很好 02/16 23:59