[理工] 演算法複雜度

看板Grad-ProbAsk作者 (瘋狂阿笨狗)時間6年前 (2019/03/25 15:54), 編輯推噓2(2推 0噓 6→)
留言8則, 2人參與, 6年前最新討論串1/3 (看更多)
https://i.imgur.com/0zTctmP.jpg
想請問一下第二題後面那串可以直接 看成n^2然後代master theorem嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.214.167.167 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1553500453.A.0FA.html
推
03/25 15:56, 6年前 , 1F
可以但題目應該是想要你用subtitution
03/25 15:56, 1F
→
03/25 15:57, 6年前 , 2F
選擇題可以直接省略用master看，但證明用subtitution比
03/25 15:57, 2F
→
03/25 15:57, 6年前 , 3F
較好
03/25 15:57, 3F
→
03/25 16:25, 6年前 , 4F
那想請問這題要怎麼用substitution 找theta
03/25 16:25, 4F
→
03/25 16:25, 6年前 , 5F
Substitution只做過O的
03/25 16:25, 5F
→
03/25 16:29, 6年前 , 6F
這題我試了n^2跟n^2+nlogn
03/25 16:29, 6F
推
03/25 19:31, 6年前 , 7F
證O再用一樣的方法證Omega就是theta了
03/25 19:31, 7F
→
03/25 20:47, 6年前 , 8F
了解謝謝sky大
03/25 20:47, 8F
‣ 更多 gz9548171 的文章
文章代碼(AID): #1Sc8ab3w (Grad-ProbAsk)
‣ 更多 gz9548171 的文章
文章代碼(AID): #1Sc8ab3w (Grad-ProbAsk)