三重循环算法复杂度及探究
原题
求如下一个三重循环程序的算法复杂度
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
m++；
二重循环
我们先来看一下一个标准的二重循环程序的复杂度是如何求的
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
m++;
这个算法与冒泡排序的复杂度一样是\(O(n^2)\)
计算过程如下:
\[\sum_{j=1}^{i}\sum_{i=1}^{n}1=\sum_{j=1}^{i}(1+1+...+1)=\sum_{j=1}^{n}j=1+2+3+...+n=\frac{n*(n+1)}{2}
\]
三重循环
重新回到题目，可以得出以下计算步骤:
\[\sum_{k=1}^{j}\sum_{j=1}^{i}\sum_{i=1}^{n}1=\sum_{k=1}^{n}(\frac{k*(k+1)}{2})=\frac{1}{2}[\sum_{k=1}^{n}(k^2)+\sum_{k=1}^{n}k]
\]
此时需要用到另外一个求和公式:\(S(n)=1+2^2+...+n^2=\frac{n*(n+1)*(2n+1)}{6}\)
推导步骤如下:
\[\begin{aligned}
n^3-(n-1)^3&=3n^2-3n+1 \(n-1)^3-(n-2)^3&=3n^2-9n+7=3(n-1)^2-3(n-1)+1\&...\2^3-1^3&=7=3*2^2-3*2+1\\end{aligned}
\]
将上述式子相加，即:
\[\begin{aligned}
\sum_{i=1}^{n}[i^3-(i-1)^3]&=n^3-1=3[n^2+(n-1)^2+...2^2]-3(n+n-1+...+2)+n-1\n^3&=3[n^2+(n-1)^2+...1^2]-3(n+n-1+...+1)+n\&=3S(n)-3\frac{n*(n+1)}{2}+n\S(n)&=[n^3-n+3\frac{n(n+1)}{2}]/3=\frac{n(n+1)(2n+1)}{6}
\end{aligned}
\]
则原式可得:
\[\frac{1}{2}[\sum_{k=1}^{n}(k^2)+\sum_{k=1}^{n}k]=\frac{S(n)+\frac{n(n+1)}{2}}{2}=\frac{n(n+1)(n+2)}{6}
\]
编写程序验证，完全吻合结果:
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
void f1(int n){
ll cnt=0;
for(ll i=1;i<=n;i++)
for(ll j=1;j<=i;j++)
for(ll k=1;k<=j;k++)
cnt++;
cout<<cnt<<" ";
ll res=(ll)n*(n+1)*(n+2)/6;//公式法
cout<<res<<" ";
cout<<((ld)1.0*cnt/res?"true":"false")<<endl;
}
int main()
{
for(int i=1;i<=100;i++)
f1(i);
return 0;
}
进一步探究
- 若修改\(k\)的范围为\([1 - mj]\),则易知复杂度应为原式乘以\(m\)
- 若修改\(i\)的范围为\(mn\)，则易知复杂度为原式用\(mn\)带入
- 若修改\(j\)的范围为\([1-mi]\),则复杂度为原式\(*(2^2)^{log_{x}{m}}+C\),使用极限计算可得
\[ans=\frac{n(n+1)((2^2)^{log_{2}{m}})*n+2+C)}{6} \quad C为常数
\]
三重循环算法复杂度及探究
原文：https://www.cnblogs.com/tltr/p/13387241.html
