带乘法自增的嵌套循环及单独外层循环时间复杂度求解

一、无内层的单外层循环复杂度 #

对应代码：

for (int i=0; i<n; i++){
    i*=2;
}

推导过程：

• 先明确for循环的执行逻辑：初始化i=0 → 判断i < n是否成立 → 成立则执行循环体的i *= 2 → 执行循环迭代表达式i++ → 回到条件判断环节。
• 逐次跟踪i的取值变化（时间复杂度分析默认n为足够大的正整数，仅关注n增长时的执行次数量级）：
  • 第1次进入循环时i=0，执行i *=2后i仍为0，执行i++后i=1
  • 第2次进入循环时i=1，执行i *=2后i=2，执行i++后i=3
  • 第3次进入循环时i=3，执行i *=2后i=6，执行i++后i=7
  • 第4次进入循环时i=7，执行i *=2后i=14，执行i++后i=15
  • 归纳可得：第k次进入循环时，i的初始值为2^k -1，执行完本轮循环体和迭代后i变为2^{k+1} -1
• 循环终止条件为判断时i >=n，即2^k -1 <n，可得k的最大值约为log₂n，循环总执行次数为对数级。

最终时间复杂度：O(log n)

注：该循环不会出现i卡在0的死循环，第一次循环结束后i会通过i++变为1，后续i呈指数级增长，很快达到终止条件。

二、双层嵌套循环复杂度 #

对应代码：

for (int i=0; i<n; i++){
    i*=2;
    for (int j=0; j<i; j++){
    }
}

推导过程：

• 内层循环每轮的执行次数，等于外层循环当轮执行完i *=2后的i值。
• 逐次统计内层循环执行次数：
  • 第1次外层循环：执行i *=2后i=0，内层循环执行0次
  • 第2次外层循环：执行i *=2后i=2，内层循环执行2次
  • 第3次外层循环：执行i *=2后i=6，内层循环执行6次
  • 第4次外层循环：执行i *=2后i=14，内层循环执行14次
  • 归纳可得：第k次外层循环中，执行完i *=2后的i值为2*(2^k -1) = 2^{k+1} -2，即内层循环当轮执行2^{k+1} -2次
• 总执行次数为所有外层轮次的内层执行次数之和，本质是公比为2的等比数列求和：
  总次数 = 0 + 2 + 6 + 14 + ... + (2^{m+1} -2)，其中m为外层循环最大执行次数，约为log₂n。
  根据等比数列性质，公比为2的数列总和小于2倍的数列最大项，此处最后一轮的内层执行次数约为2n，因此总和约为4n，属于线性级；求和式中附带的对数级次项、常数项在n足够大时可忽略。

最终时间复杂度：O(n)

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