[理工] 101 台大電機 資結

[gcobs226484 (胖喵)]

https://i.imgur.com/8yo3lUO.jpg

想請問這題C選項錯的原因？
謝謝
-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.102.179 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1573186442.A.CFD.html
推 b10007034: n^4才對
→ b10007034: 應該不只n^4, 展開來發現O(n^4)+O((n-1)^4)+O((n-2)^4
→ b10007034: +O((n-3)^4)+...
推 realmanKG: 應是四次方以上等級的時間複雜度
→ realmanKG: 雖然foo函數單純是平方級，但你要把迴圈內容拆開來看
→ realmanKG: 就如樓上b大 會得出級數和i^4, i=1, 2, ....n
推 andy831020: 小陷阱題而已XD foo是 代入m 複雜度是m方 XD
推 andy831020: 所以是1到n的四次方和=五次方
→ gcobs226484: 謝謝樓上幾位的大大 懂問題在哪了