为什么这段代码的Big O时间复杂度不是log(log(n))

给出的代码如下：

for(int i =1; i<n;i=i*2)
{
   for(int j=1; j<i; j = j*2)
   {
     cout << "hello";
   }
}

正确推导逻辑 #

• 先分析外层循环：i初始值为1，每次迭代乘2，直到i >=n时停止，外层的总迭代次数约为log₂n次，i的取值依次为2⁰、2¹、2²……2ᵏ，其中2ᵏ < n。
• 再分析内层循环：对于每一个外层给定的i值，j初始值为1，每次迭代乘2，直到j >=i时停止，单次外层循环对应的内层迭代次数为log₂i次。
• 总操作次数为所有外层循环对应的内层次数之和：
  总次数S = 0（i=1时j<1不执行） + 1（i=2时） + 2（i=4时） + 3（i=8时） + …… + (log₂n -1)
  这是首项为0、末项为log₂n-1的等差数列求和，结果为S = (log₂n) * (log₂n - 1) / 2，省略常数和低阶项后，时间复杂度为O(log²n)（也可写作O((log n)²)）。

原推测错误原因 #

你最初推测的O(log(log n))错误，核心问题是没有对每轮内层的执行次数做累加，错误认为内层固定只有log(log n)次执行。实际内层的执行次数会随着外层i的增大逐步增长到log n量级，所有轮次累加后是对数的平方量级，而非嵌套对数量级。

内容的提问来源于stack exchange，提问作者Musa B.