資結

[csuperk (CS)]

http://i.imgur.com/VURxMjU.jpg

請問 這個foo(i*i) 中的i*i不是應該為「一個」整數嗎？
Big-O為什麼不是 n^2 *n ?
洪逸老師給的答案是 n^2 * n^2 *n = O(n^5)
-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.126.230
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543338250.A.5D3.html
推 cossetannie: (i*i)^2 = i^2*i^2?
搞不懂 :<
所以foo要n^2 跑n次 為什麼答案不是n^3
我的想法是 這個程式跑了n次foo. 其中參數i*i=O(1). foo需要O(n^2)
※ 編輯: csuperk (111.82.126.230), 11/28/2018 01:38:20
※ 編輯: csuperk (111.82.126.230), 11/28/2018 01:39:17
※ 編輯: csuperk (111.82.126.230), 11/28/2018 01:40:17
推 skyHuan: 題目說input放多大複雜度就是他的平方，迴圈裡面input是k
→ skyHuan: =i^2複雜度就是k^2=i^4，整個迴圈的複雜度就是1^4+2^4+..
→ skyHuan: .+n^4=O(n^5)
→ skyHuan: foo函式接收一個int的參數，這個函式的複雜度會是接收的
看懂了！謝謝你們
→ skyHuan: 這個int參數的平方
※ 編輯: csuperk (111.82.126.230), 11/28/2018 07:00:25
→ magic83v: 輸入是n^2 但是處理的數字是1^2、2^2...n^2
→ magic83v: 所以還是只有n筆資料 進去做這個迴圈
→ magic83v: 感覺不太合理 又不是輸入1～n^2
推 skyHuan: https://i.imgur.com/S1mu5pR.jpg
推 Fanchien: 樓上清楚明白 推