为什么for(int i=1;i<n;i*=2) for(int j=0;j<i;j++) sum++ 时间复杂度是O(n)
时间: 2023-09-26 19:06:39 浏览: 64
### 回答1:
这段代码中,i 的值每次翻倍,j 的值每次增加1,因此内层循环的次数总共为:
1 + 2 + 4 + ... + 2^(k-1)
其中,2^k 是小于 n 的最大的 2 的幂次方,也就是说,k = log2(n)。
上述等比数列的和可以用求和公式来计算:
sum = 2^k - 1 = 2^(log2(n)) - 1 = n - 1
因此,外层循环总共执行 log2(n) 次,内层循环总共执行 n - 1 次,时间复杂度为 O(n log n)。
### 回答2:
在这段代码中,我们可以看到一个嵌套的循环结构。外层循环的迭代次数为log(n)次,内层循环的迭代次数为2^0、2^1、2^2直到2^(log(n)-1)次,其总和为 2^0 + 2^1 + 2^2 + ... + 2^(log(n)-1) = 2^log(n) - 1 = n - 1。所以总的时间复杂度可以近似看作是 O(n)。
### 回答3:
这个程序通过两个嵌套的循环对sum进行累加。外层循环的控制变量是i,初始值为1,每次乘以2,直到i大于等于n。内层循环的控制变量是j,初始值为0,每次增加1,直到j大于等于i。我们可以将内层循环的循环次数表示为log(i)。
对于外层循环的时间复杂度,当i<n时,i的值始终小于n的2的幂次方,即i≤2^⌈log₂n⌉。外层循环的迭代次数为log₂i,而i的最大值为2^⌈log₂n⌉,所以外层循环的迭代次数约为log₂(2^⌈log₂n⌉) = ⌈log₂n⌉。
内层循环的时间复杂度是O(i),由于最坏情况下内层循环迭代次数为i,所以内层循环的迭代次数可以表示为2^k,其中k=log(i)。
综上所述,内外层循环的总迭代次数约为log₂(n) + log₂(n/2) + log₂(n/4) + ... + log₂(2) = log₂(n) + log₂(n/2) + log₂(n/4) + ... + 1 = log₂(n*(n/2)*(n/4)*...*2) = log₂(n*(n/2)*(n/4)*...*2) = log₂(n^log₂(n/2)) = log₂(n^log₂(n)-1) = log₂(n^(log₂(n)/log₂(2))-1) = log₂(n^(log₂(n))-1) = log₂(n)-1。因此,整个程序的时间复杂度为O(n)。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)