内层长度可变的嵌套循环时间复杂度求解及代码分析

先看你给出的代码：

while (n > 0) {
   for (let i = 0; i < n; i++) {
      /* O(1) code */
   }
   n = n / 2;
}

外层循环次数 #

外层循环每次把n减半，直到n不大于0，所以循环次数是O(log n)（准确说是以2为底的对数次数，大O表示里底数不影响，统一写O(log n)）。

内层循环的总执行次数 #

你疑惑内层循环的复杂度，但这里不能单独看单次内层，要算所有内层循环的总执行次数：

• 第一次外层循环：内层跑n次
• 第二次：跑n/2次
• 第三次：跑n/4次
• ...
• 最后一次：跑1次（当n变为1时，内层执行1次，之后n变成0.5，外层循环结束）

这是一个首项为n、公比为1/2的等比数列求和，总和是：
n + n/2 + n/4 + ... + 1 = 2n - 1（当项数足够多时，和趋近于2n）

所以总执行次数是O(n)，大O表示会忽略常数项。

整个算法的时间复杂度 #

整个算法的总操作数是O(n)，不是你猜测的O(n log n)。核心原因是内层循环的执行次数是递减的，加起来是线性的，不是每次都跑n次再乘log n次外层。

举个实际例子：当n=8时，总执行次数是8+4+2+1=15，约等于2*8=16，和n成正比，是线性复杂度。

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