x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;
为什么
循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3次
这个1^2+2^2+3^2是怎么得出来的
下面这个3层循环的时间复杂度为什么是O(n^3)
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- cao_yanjie 2017-08-27 09:32关注
首先,我们考虑这么一种情况,当i取值为N的时候,那么我们上面那个三层循环就变成了
for(j=1;j<=N;j++)
for(k=1;k<=j;k++)
x++;
这样看来,是不是一目了然了。
N的取值为 1 2 3 4 5 ...... N-1 N
相应的,我们可以把上面那个二层for循环改写为一层循环
for(k=1;k<=[1 2 3 4 5 ......N-1 N];k++)
x++;
那么,我们这个for循环运行的总的时间复杂度就是 (1+n)n/2
当然,这不是最终的时间复杂度,因为我们只是讨论了i取a的情况
所以,总的时间复杂度为 Σ(对i求和 i从1到n)i+i^2/2一次循环: 运行为N次;
二次循环:运行为N-1+N-2+N-3+...+1=1+2+3+...+N-1=N(N-1)/2
三次循环:N(N+1)/2+(N-1)*N/2+...+2*3/2+1*2/2=N(N+1)(N+2)/6补充数学公式
1*2/2+2*3/2+3*4/2+……+n(n+1)/2=n(n+1)(n+2)/6
1^2+2^2+3^2+……+n^2=n(n+1)(2n+1)/6
1^3+2^3+3^3+……+n^3=[n(n+1)/2]^2
等比数列求和公式
Sn=a1(q^n-1)/(q-1) (q不等于1)
等差数列求和公式
Sn=na1+n(n-1)d/2本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 5无用
悬赏问题
- ¥15 安卓adb backup备份应用数据失败
- ¥15 eclipse运行项目时遇到的问题
- ¥15 关于#c##的问题:最近需要用CAT工具Trados进行一些开发
- ¥15 南大pa1 小游戏没有界面,并且报了如下错误,尝试过换显卡驱动,但是好像不行
- ¥15 没有证书,nginx怎么反向代理到只能接受https的公网网站
- ¥50 成都蓉城足球俱乐部小程序抢票
- ¥15 yolov7训练自己的数据集
- ¥15 esp8266与51单片机连接问题(标签-单片机|关键词-串口)(相关搜索:51单片机|单片机|测试代码)
- ¥15 电力市场出清matlab yalmip kkt 双层优化问题
- ¥30 ros小车路径规划实现不了,如何解决?(操作系统-ubuntu)