algs里分析ThreeSum算法的执行时间时用到了三层循环的执行次数,文章里只给了结论没有计算过程。不知道原理,只知道结果,不符合我的学习习惯,所以我用自己的方法尝试计算。下面是示例代码:
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
for (int k = j + 1 ; k < N; ++k) {
}
}
}
显而易见,最外层的循环的执行次数是N次,第二层循环次数是个等差数列:N−1,N−2,N−3,...,3,2,1,0,所以第二层循环的执行次数是2N(N−1)。第三层循环次数就不是那么直观了,可以先把i和j的值带入具体的值来分别计算第三层的循环次数,然后再分析下规律。
当i=0,j∈[1,N−1]时
i |
j |
第三层的循环次数 |
0 |
1 |
N-2 |
0 |
2 |
N-3 |
0 |
3 |
N-4 |
0 |
N-3 |
2 |
0 |
N-2 |
1 |
0 |
N-1 |
0 |
当i=1,j∈[2,N−1]时
i |
j |
第三层的循环次数 |
1 |
2 |
N-3 |
1 |
3 |
N-4 |
1 |
4 |
N-5 |
1 |
N-3 |
2 |
1 |
N-2 |
1 |
1 |
N-1 |
0 |
当i=2,j∈[3,N−1]时
i |
j |
第三层的循环次数 |
2 |
3 |
N-4 |
2 |
4 |
N-5 |
2 |
5 |
N-6 |
2 |
N-3 |
2 |
2 |
N-2 |
1 |
2 |
N-1 |
0 |
当i=N−4,j∈[N−3,N−1]时
i |
j |
第三层的循环次数 |
N-4 |
N-3 |
2 |
N-4 |
N-2 |
1 |
N-4 |
N-1 |
0 |
当i=N−3,j∈[N−2,N−1]时
i |
j |
第三层的循环次数 |
N-3 |
N-2 |
1 |
N-3 |
N-1 |
0 |
当i=N−2,j∈[N−1,N−1]时
可以得出第三层循环的循环次数是与i相关的等差数列。
i |
第三层的循环次数等差数列 |
第三层循环的循环次数和 |
0 |
N-2, N-3, N-4, N-5, N-6, N-7, …, 2, 1, 0 |
2(N−2)(N−1) |
1 |
N-3, N-4, N-5, N-6, N-7, …, 2, 1, 0 |
2(N−3)(N−2) |
2 |
N-4, N-5, N-6, N-7, …, 2, 1, 0 |
2(N−4)(N−3) |
… |
… |
… |
N-4 |
2, 1, 0 |
3 |
N-3 |
1, 0 |
1 |
N-2 |
0 |
0 |
由等差数列求和公式f(n)=2n2+n可得第三层循环的循环次数和sum(i)=2(N−2−i)2+(N−2−i),i∈[0,N−2],于是第三层循环的循环次数总和i=0∑N−2sum(i)
=i=0∑N−22(N−2−i)2+(N−2−i)
=2(N−2)2+(N−2)+2(N−3)2+(N−3)+2(N−4)2+(N−4)+...+2(2)2+(2)+2(1)2+(1)+2(0)2+(0)
=2(N−2)2+(N−3)2+(N−4)2+...+(2)2+(1)2+(0)2+(N−2)+(N−3)+(N−4)+...+2+1+0
平方和公式k=1∑nk2=6n(n+1)(2n+1)和等差数列求和公式f(n)=2n2+n,所以
2(N−2)2+(N−3)2+(N−4)2+...+(2)2+(1)2+(0)2+(N−2)+(N−3)+(N−4)+...+2+1+0
=26(N−2)(N−2+1)(2(N−2)+1)+2(N−2)2+(N−2)
为了方便计算,代入N-2=a
26(N−2)(N−2+1)(2(N−2)+1)+2(N−2)2+(N−2)
=26a(a+1)(2a+1)+2a2+a
=26a(a+1)(2a+1)+3a(a+1)
=26(a+1)(2a2+a+3a)
=6a(a+1)(a+2)
再代入a=N-2
=6a(a+1)(a+2)
=6(N−2)(N−1)N
所以
第三层循环的循环次数总和i=0∑N−2sum(i)=6(N−2)(N−1)N