[問題] Big Oh running time

[triumphant10 (Look-three-small)]

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://www.ptt.cc/bbs/Prob_Solve/M.1552920807.A.4B6.html
推 fatcat8127: 你的程式碼可以以if的判斷式是否成立分兩部分簡化
→ fatcat8127: 外圈的兩個for迴圈只有當j是i的倍數時才會進到if判斷
→ fatcat8127: 判斷式內的k每次只會讓sum+1
→ fatcat8127: https://www.codepile.net/pile/oGA3Lq73
→ fatcat8127: 1x2+(1+2)x3+(1+2+3)x4+(1+2+3+4)x5...的累加
→ fatcat8127: 每項都是n*(n-1)/2，可以再化減成算式即可O(1)求值
※ 編輯: triumphant10 (111.241.21.71), 03/19/2019 02:15:16
→ triumphant10: 謝謝你！我看懂了！
→ fatcat8127: 我看到你在C++版的文發現好像誤會你的意思惹0.0
→ triumphant10: 我有懂你想表達的，雖然不是我想問的XD 嘻嘻