※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1552955780.A.1A1.html