作者oao521 (一樣的午後時光)
看板Grad-ProbAsk
標題[理工] 時間複雜度
時間Sun Feb 16 11:18:46 2020
https://i.imgur.com/S9mOpVV.jpg
https://i.imgur.com/h5ghXCj.jpg
請問這一題D選項
只寫 a, b are real constants
那...請問
若b為負數時，要怎麼證呢？
答案給D is correct
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.210.32 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1581823128.A.A11.html
1F：推 maple205: 時間複雜度不會是負的 沒有演算法會因為output越大 02/16 11:21
我是指b<0的情況
2F：→ maple205: 做得時間反而變少 02/16 11:21
3F：→ oao521: 所以這一題 02/16 11:30
4F：→ oao521: 雖然題目只說b是實數 02/16 11:30
5F：→ oao521: 但是我們要自動假設其實題目只考慮正實數的情況？ 02/16 11:30
6F：→ oao521: 也就是說我們寫題目的時候 就先假設前提：題目不考慮b為負 02/16 11:32
7F：→ oao521: 數 02/16 11:32
8F：→ oao521: 這樣理解對嗎？ 02/16 11:33
9F：→ DLHZ: 在b為負數的情況下 theta內的n^b乘上任一常數在n趨近於無趣 02/16 11:35
10F：→ DLHZ: 大的情況下依然是0 無法得出大於左方函數的部分 我認為要正 02/16 11:35
11F：→ DLHZ: 確應該改成omega或者for some positive constant b 02/16 11:35
12F：→ 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
13F：→ DLHZ: 基於上面解釋的 我認為對啦 至於考試到底怎樣就看個人吧 02/16 11:56
14F：→ DLHZ: 用極限說明我是覺得蠻好用的 好像有其他方法 不過我沒去讀 02/16 11:57
感謝大大的解釋：)
※ 編輯: oao521 (1.200.210.32 臺灣), 02/16/2020 12:10:30
15F：推 hit5180214: 負的也會成立，當b是正的會被限制在某個範圍間，取倒 02/16 12:21
16F：→ hit5180214: 數之後也當然會被bound 住 02/16 12:21
17F：→ hit5180214: b由正轉負，係數取倒數就出來了啊 02/16 12:22
18F：推 zuchang: 直接用BigO定義,找出存在一個c來證就好,用極限也很好 02/16 23:59