作者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/cn.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