设S为C语言的语句, 计算机执行下面算法时，算法的时间复杂度

[单选题]

设S为C语言的语句, 计算机执行下面算法时，算法的时间复杂度为（ ）。

for(i=n-1 ； i>=0 ； i--)

for(j=0 ； j<i ； j++) S ；

```
n2
```
```
O(nlgn)
```
```
O(n)
```
```
O(n2)
```

查看答案及解析

y20180322105368

1、i>=0、i--执行 n-1 次
2、j<i、j++ 执行 (n-1) + (n-2) + ... + 1 ≈ (n^2) / 2
3、最后取变化最大的，所以是n^2

发表于 2018-03-26 10:47:10 回复(0)

贡丸。

eg:

(1)   for(i=1;i<=n;i++) //循环了n*n次，当然是O(n^2) for(j=1;j<=n;j++)
                 s++;
(2)   for(i=1;i<=n;i++)//循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2) for(j=i;j<=n;j++)
                 s++;
(3)   for(i=1;i<=n;i++)//循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2) for(j=1;j<=i;j++)
                 s++;
(4)   i=1;k=0;
      while(i<=n-1){
           k+=10*i;
i++;      }



(5)   for(i=1;i<=n;i++)
 for(j=1;j<=i;j++)
 for(k=1;k<=j;k++)
 x=x+1;
//
循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(这个公式要记住哦)≈(n^3)/3，不考虑系数，自然是O(n^3)