※ 引述《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 然后做数学求和