[理工] 時間複雜度

看板Grad-ProbAsk作者 (一樣的午後時光)時間4年前 (2020/02/16 11:18), 4年前編輯推噓3(3推 0噓 15→)
留言18則, 5人參與, 4年前最新討論串12/12 (看更多)
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1581823128.A.A11.html
推
02/16 11:21, 4年前 , 1F
時間複雜度不會是負的 沒有演算法會因為output越大
02/16 11:21, 1F
我是指b<0的情況
→
02/16 11:21, 4年前 , 2F
做得時間反而變少
02/16 11:21, 2F
→
02/16 11:30, 4年前 , 3F
所以這一題
02/16 11:30, 3F
→
02/16 11:30, 4年前 , 4F
雖然題目只說b是實數
02/16 11:30, 4F
→
02/16 11:30, 4年前 , 5F
但是我們要自動假設其實題目只考慮正實數的情況？
02/16 11:30, 5F
→
02/16 11:32, 4年前 , 6F
也就是說我們寫題目的時候 就先假設前提：題目不考慮b為負
02/16 11:32, 6F
→
02/16 11:32, 4年前 , 7F
數
02/16 11:32, 7F
→
02/16 11:33, 4年前 , 8F
這樣理解對嗎？
02/16 11:33, 8F
→
02/16 11:35, 4年前 , 9F
在b為負數的情況下 theta內的n^b乘上任一常數在n趨近於無趣
02/16 11:35, 9F
→
02/16 11:35, 4年前 , 10F
大的情況下依然是0 無法得出大於左方函數的部分 我認為要正
02/16 11:35, 10F
→
02/16 11:35, 4年前 , 11F
確應該改成omega或者for some positive constant b
02/16 11:35, 11F
→
02/16 11:38, 4年前 , 12F
修正一下 兩者在n夠大後都是0 應該是沒問題才對
02/16 11:38, 12F
考試時需要考慮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
→
02/16 11:56, 4年前 , 13F
基於上面解釋的 我認為對啦 至於考試到底怎樣就看個人吧
02/16 11:56, 13F
→
02/16 11:57, 4年前 , 14F
用極限說明我是覺得蠻好用的 好像有其他方法 不過我沒去讀
02/16 11:57, 14F
感謝大大的解釋：) ※ 編輯: oao521 (1.200.210.32 臺灣), 02/16/2020 12:10:30
推
02/16 12:21, 4年前 , 15F
負的也會成立，當b是正的會被限制在某個範圍間，取倒
02/16 12:21, 15F
→
02/16 12:21, 4年前 , 16F
數之後也當然會被bound 住
02/16 12:21, 16F
→
02/16 12:22, 4年前 , 17F
b由正轉負，係數取倒數就出來了啊
02/16 12:22, 17F
推
02/16 23:59, 4年前 , 18F
直接用BigO定義,找出存在一個c來證就好,用極限也很好
02/16 23:59, 18F
‣ 更多 oao521 的文章
文章代碼(AID): #1UIBIOeH (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 12 之 12 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 oao521 的文章
文章代碼(AID): #1UIBIOeH (Grad-ProbAsk)