[問題] Big O running time

[triumphant10 (Look-three-small)]

sum = 0

for (i = 0; i < n; i++){

    for (j = 1; j < i*i; j++){

        if (j%i == 0){

            for (k = 0; k < j; k++){

                sum++

            }

        }

    }

}

大家好

我計算出來的 running time 是 O(N^4)，不曉得對不對

以及

如果if條件句是False的話，也必須計算它的次數

那麼正確的寫法應該是甚麼?

因為我只有計算他正確執行時所耗的時間!

麻煩各位了!

謝謝!

--

      當年我每回翻開課本，腦袋裡就先告訴自己

  這是戰場，我是來拼命的 !



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.106
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1552900261.A.1B8.html
推 OhYiDay: 這是不是台聯大轉學考某年考題啊？！
→ triumphant10: 是喔XD 我不知道耶
→ sarafciel: 你走錯版了 C跟C++的程式碼是要宣告明確形態跟分號的
推 IhateOGC: N^2 ....
推 CoNsTaR: O(n^4) 是怎麼算的...
推 CoNsTaR: 你在 prob_solve 也有問，如果是學校要的答案的話會是 O(
→ CoNsTaR: n^2) 不是那邊講的 O(1)
推 CoNsTaR: 那個版在討論的是問題的複雜度，不是你程式本身的複雜度
推 OhYiDay: 這題跟台聯大106計概轉學考14題 一模一樣 如果我沒看錯的
→ OhYiDay: 話  可是答案的確是O(N^4）耶
→ triumphant10: 抱歉，我發錯版。可以問一下Co大 O(N^2)是如何計算
→ triumphant10: 的嗎？
→ loveme00835: 到第 2 層 for 已經是 N^3, N^2 到底怎麼算的?
推 CoNsTaR: 抱歉 是我沒有認真看題目 orz
→ triumphant10: 沒4沒4
推 IhateOGC: 我數學好爛@@