C语言嵌套循环时间复杂度计算问题（附两段代码实例）

第一段代码分析 #

c = 0;
for (i = 0; i < n*n; i++) 
for (j = 0; j < i; j++) 
 c = c + 1; 

• 外层循环执行总次数为n²次，i的取值范围是0到n²-1
• 内层循环的执行次数和当前外层循环的i值一致，每次外层迭代对应i次内层操作
• 总执行次数为等差数列求和：$\sum_{i=0}^{n²-1}i = \frac{(n²-1)n²}{2}$，忽略低阶项和常数系数后，总时间复杂度为O(n⁴)*

第二段代码分析 #

j = 1; c = 0;
for(i = 1; i <= n; i = i + 1) { 
 for(k = 1; k <= j; k = k + 1) { 
 c = c + 1; 
 } 
j = j * 2; 
}

• 你之前得出的n*2ⁿ结论是错误的，错误原因是直接将单次内层循环的最大执行次数乘外层循环次数，没有按实际总执行次数求和计算
• 外层循环共执行n次，j的取值随外层迭代每次翻倍：第1次外层迭代j=1，第2次j=2，第3次j=4，第n次j=2ⁿ⁻¹
• 总执行次数为等比数列求和：$\sum_{k=0}^{n-1}2k = 2^n -1$，忽略常数项后总时间复杂度为O(2ⁿ)

内容的提问来源于stack exchange，提问作者ekfqlc