PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Big Oh running time

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (0x1.b860bde023111p-111)時間5年前 (2019/03/19 08:36)推噓2(2推 0噓 0→)

留言2則, 1人參與討論串2/2 (看更多)

※ 引述《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)，不曉得對不對? : 以及 : 想問一下各位都是如何去思考這種題目的? : 如果要嚴謹一點的寫法該如何是好? : 想問各位的思路 : 謝謝! 有一個比較容易理解的方式是直接把 for 迴圈寫成 Σ 不過要注意 Σ 只有 +1, 所以碰到像這裡有條件的就要做點變換這裡的 j 有條件是 i 的倍數所以如果令 j = j'*i 那就可以有一個一直 +1 的變數 j', 由 0 到 i-1 同時 k 的上限也要從 j-1 改成 j'*i-1 這樣整個迴圈就能寫成 n-1 i-1 j'*i-1 Σ Σ Σ O(1) i=0 j'=0 k=0 那麼 j'*i-1 i-1 i-1 Σ O(1) = O(j'*i), Σ O(j'*i) = O(i)* Σ O(j) = O(i)*O(i^2) = O(i^3) k=0 j'=0 j'=0 n-1 Σ O(i^3) = O(n^4) ←即是答案了 i=0 如果你要精確算出例如 sum 是多少那也可以把 O(1) 就寫 1 然後做數學求和 -- ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄ ▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄ ▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌ ▏ζ(▏●‵◥′●▊)Ψ ▏　　　　　　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄ █/|▊ 〃、〃▋ |\ ▎　　　　　　　ハルヒ主義　　　　　█▄▄▄█▄▄ ◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.192.32 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1552955780.A.1A1.html