嵌套循环时间复杂度分析疑问：外层为log₂n，内层复杂度如何？

这个嵌套循环的时间复杂度是O(n)，并非你猜测的**(log₂n)²**，具体推导如下：

1. 明确外层循环的迭代规律：
   外层循环中i从1开始，每次乘以2，直到i <= n，所以外层循环的次数是⌊log₂n⌋ + 1，属于**O(logn)**量级，但这不能直接和内层循环的复杂度相乘——因为内层循环的迭代次数是随i变化的，不是固定值。

2. 计算内层循环的总执行次数：
   内层循环每次的迭代次数等于当前i的值，所以总次数是一个等比数列的和：

   • 当i=1时，内层循环执行1次
   • 当i=2时，内层循环执行2次
   • 当i=4时，内层循环执行4次
   • ...
   • 最后一次i是不超过n的最大2的幂，设为2^k（满足2^k <= n < 2^(k+1)），此时内层循环执行2^k次

   这个等比数列的和为：1 + 2 + 4 + ... + 2^k，根据等比数列求和公式，结果是2^(k+1) - 1。

3. 推导时间复杂度：
   因为2^k <= n，所以2^(k+1) <= 2n，因此2^(k+1)-1 <= 2n -1，这意味着总执行次数是**O(n)**量级。

举个实际例子验证：

• 当n=8时，总执行次数是1+2+4+8=15，接近2*8=16
• 当n=5时，总执行次数是1+2+4=7，小于2*5=10

显然总次数和n是线性关系，而非平方对数关系。

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