作者triumphant10 (Look-three-small)
看板Prob_Solve
标题[问题] Big Oh running time
时间Mon Mar 18 22:53:22 2019
sum = 0;
for (i = 0; i < n; i++){
for (j = 0; j < i*i; j++){
if (j % i == 0){
for (k = 0; k < j; k++){
sum++;
}
}
}
}
大家好
这题的Big O 我算出来得到的是 O(n^4)，不晓得对不对?
以及
想问一下各位都是如何去思考这种题目的?
如果要严谨一点的写法该如何是好?
想问各位的思路
谢谢!
--
当年我每回翻开课本，脑袋里就先告诉自己
这是战场，我是来拼命的 !
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.241.21.71
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1552920807.A.4B6.html
1F：推 fatcat8127: 你的程式码可以以if的判断式是否成立分两部分简化03/19 01:49
2F：→ fatcat8127: 外圈的两个for回圈只有当j是i的倍数时才会进到if判断03/19 01:50
3F：→ fatcat8127: 判断式内的k每次只会让sum+103/19 01:51
5F：→ fatcat8127: 1x2+(1+2)x3+(1+2+3)x4+(1+2+3+4)x5...的累加03/19 01:59
6F：→ fatcat8127: 每项都是n*(n-1)/2，可以再化减成算式即可O(1)求值03/19 02:04
※ 编辑: triumphant10 (111.241.21.71), 03/19/2019 02:15:16
7F：→ triumphant10: 谢谢你！我看懂了！ 03/19 02:21
8F：→ fatcat8127: 我看到你在C++版的文发现好像误会你的意思惹0.0 03/19 10:04
9F：→ triumphant10: 我有懂你想表达的，虽然不是我想问的XD 嘻嘻 03/19 14:31