分析下列程序段的时间复杂度: s=0; for i=0; i<n; i++) for(j=0; j<n; j++) s+=B[i][j]; sum=s;
时间: 2023-12-05 07:05:57 浏览: 646
这段程序的时间复杂度为 $O(n^2)$。
原因如下:
该程序段中有两个嵌套的循环,外层循环的次数为 n,内层循环的次数也为 n,因此总共的循环次数为 $n\times n=n^2$。
在循环体内部,只有一条语句,即 s+=B[i][j],该语句的时间复杂度为 $O(1)$,因此总时间复杂度为 $O(n^2)$。
最后,程序将 s 的值赋给了 sum,这一步不会影响时间复杂度。
相关问题
分析下列程序段的时间复杂度: x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++;
这段程序的时间复杂度为 $O(n^2)$。
原因如下:
该程序段中有两个嵌套的循环,外层循环的次数为 $n-1$,内层循环的次数为 $n-i$,因此总共的循环次数为:
$$
\sum\limits_{i=1}^{n-1}{(n-i)}=\sum\limits_{j=1}^{n-1}j=\frac{(n-1)\times n}{2}=O(n^2)
$$
在循环体内部,只有一条语句,即 x++,该语句的时间复杂度为 $O(1)$,因此总时间复杂度为 $O(n^2)$。
最后,程序将 x 的值赋给了某个变量,这一步不会影响时间复杂度。
下面程序段的时间复杂度是( )。 i=s=0; while(s<n){ i++;s+=i; }
这段程序的时间复杂度是 O(√n)。
分析:在循环体内,每次都会将i加1,同时将s加上i。因此,循环次数与i的关系为i的增量,即i的增量为1,2,3,4,5,6...,最后的i值为循环次数。又因为s的增量为1+2+3+4+...+i,即等差数列求和公式,s=n时循环结束。那么,可以得到以下关系:
```
s = 1 + 2 + 3 + ... + i <= 1 + 2 + 3 + ... + i-1 + i
s < n
```
将等差数列求和公式带入可得:
```
i(i+1)/2 <= n
```
该式左边是一个关于i的二次方多项式,右边是一个常数n。因此,可以得到以下关系:
```
i^2 + i - 2n <= 0
```
根据二次方程求根公式,可以得到:
```
i <= (-1 + sqrt(1 + 8n)) / 2
```
因此,循环次数i的上限是O(√n)。所以,这段程序的时间复杂度是O(√n)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)