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