龙猫12138 2017-08-27 08:22 采纳率: 0%
浏览 4122
已采纳

下面这个3层循环的时间复杂度为什么是O(n^3)

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是怎么得出来的

  • 写回答

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗