[理工] 演算法複雜度

[gz9548171 (瘋狂阿笨狗)]

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
推 skyHuan: 可以但題目應該是想要你用subtitution
→ skyHuan: 選擇題可以直接省略用master看，但證明用subtitution比
→ skyHuan: 較好
→ gz9548171: 那想請問這題要怎麼用substitution 找theta
→ gz9548171: Substitution只做過O的
→ gz9548171: 這題我試了n^2跟n^2+nlogn
推 skyHuan: 證O再用一樣的方法證Omega就是theta了
→ gz9548171: 了解謝謝sky大