算法分析：三类嵌套循环代码片段的时间方程构建疑问

你已经确认了外层循环的轮次都是log₂n量级、sum++是常数时间操作，所以只需要统计sum++的总执行次数，就能得到对应的时间复杂度，核心入手方法就是枚举外层循环每一轮的内层执行次数，累加求和即可，三个代码的差异完全来自内层循环边界和外层变量的关联关系：

第一段代码 #

int sum = 0;
for (int k = n; k > 0; k /= 2)
   for (int i = 0; i < k; i++)  
       sum++;

• 外层循环的k取值序列为：n、n/2、n/4、……、1，总共有⌈log₂n⌉轮
• 每一轮内层循环的执行次数等于当前轮次的k值，总执行次数就是所有k值的和：n + n/2 + n/4 + … + 1，对等比数列求和即可得到结果。

第二段代码 #

int sum = 0;
for (int i = 1; i < n; i *=2)
   for (int j = 0; j < i; j++) 
       sum++;

• 外层循环的i取值序列为：1、2、4、……、小于n的最大2的幂，总轮次也是⌈log₂n⌉
• 每一轮内层循环的执行次数等于当前轮次的i值，总执行次数就是所有i值的和：1 + 2 + 4 + … + 2^m（其中2^m < n ≤ 2^{m+1}），对等比数列求和即可得到结果。

第三段代码 #

int sum = 0;
for (int i = 1; i < n; i *=2)
   for (int j = 0; j < n; j++) 
       sum++;

• 外层循环轮次还是⌈log₂n⌉
• 内层循环的边界是固定值n，和外层的i没有关联，所以每一轮内层都固定执行n次，总执行次数直接是外层轮次乘以n即可。

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