2 m0 37676512 m0_37676512 于 2017.08.27 16:22 提问

下面这个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
cao_yanjie   2017.08.27 17: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

YellowsuN_A
YellowsuN_A   2017.08.27 17:51

不知道这么说您能不能理解.

图片说明

这是由i 的值变化而 k 的值变化的规律, 比如 i=2 时 j,k都要到2 才能结束本次循环然后i++进入下一个循环(如果i+1<=n).

由于 i = 2 也是从 i=1 开始的,所以要加上前面的循环次数.那么我们先看 i=n

这里我们得出一个规律 i 的值为n时 循环(∑(1)+∑(2)+∑(3)+....+∑(n-1)+ ∑(n)) = n^2次。

那i 的值为n-1时 循环(∑(1)+∑(2)+∑(3)+....+∑(n-1)+ ∑(n-1)) = (n-1)^2次

而 i 是从 1→n的, 所以总共循环(1^2+2^2+3^2+...+n^2)次

Csdn user default icon
上传中...
上传图片
插入图片