作者csuperk (CS)
看板Grad-ProbAsk
標題資結
時間Wed Nov 28 01:04:08 2018
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1543338250.A.5D3.html
1F：推 cossetannie: (i*i)^2 = i^2*i^2? 11/28 01:26
搞不懂 :<
所以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
2F：推 skyHuan: 題目說input放多大複雜度就是他的平方，迴圈裡面input是k 11/28 01:43
3F：→ skyHuan: =i^2複雜度就是k^2=i^4，整個迴圈的複雜度就是1^4+2^4+.. 11/28 01:43
4F：→ skyHuan: .+n^4=O(n^5) 11/28 01:43
5F：→ skyHuan: foo函式接收一個int的參數，這個函式的複雜度會是接收的 11/28 01:46
看懂了！謝謝你們
6F：→ skyHuan: 這個int參數的平方 11/28 01:46
※ 編輯: csuperk (111.82.126.230), 11/28/2018 07:00:25
7F：→ magic83v: 輸入是n^2 但是處理的數字是1^2、2^2...n^2 11/28 12:36
8F：→ magic83v: 所以還是只有n筆資料 進去做這個迴圈 11/28 12:36
9F：→ magic83v: 感覺不太合理 又不是輸入1～n^2 11/28 12:37
11F：推 Fanchien: 樓上清楚明白 推 11/28 14:59