为何两段循环的时间复杂度是O(log(logn))而非O(logn)？

先看这段代码的实际执行逻辑：

p = 0
for( i=1; i<n; i=i*2 ) { 
    p++ // 循环次数为 log₂n，最终 p 的值等于 log₂n
} 

for( j=1; j<p; j=j*2 ) { 
    some_statement // 循环次数为 log₂(p) = log₂(log₂n)
}

为什么变量p会影响第二个循环的复杂度？ #

第一个循环结束后，p不是固定值，而是和n直接绑定的——p的最终值就是第一个循环的执行次数，也就是log₂n（n足够大时的近似值）。第二个循环的终止条件是j < p，相当于j < log₂n，它的循环次数是基于log₂n计算的，自然复杂度就变成了O(log log n)，而不是基于n的O(logn)。

为什么总复杂度不是O(logn)？ #

其实总复杂度就是O(logn)。因为O(logn + loglogn)等价于O(logn)——当n趋向无穷大时，loglogn的增长速度远慢于logn，会被logn“覆盖”，整体复杂度由第一个循环主导。你看到的注释写的O(loglogn)应该是指第二个循环单独的复杂度，不是整个代码的总复杂度。

举个实际例子：当n=2^1024时，第一个循环执行1024次，第二个循环只执行10次。显然第二个循环的次数和第一个比可以忽略不计，总复杂度还是O(logn)。

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