求解这段嵌套循环代码的时间复杂度及推导过程

待分析代码 #

int c = 0;
for (int i = 1; i < n; i += i)
{
    for (int j = 0; j < i; j++)
    {
        c++;
    }
}

问题描述 #

我尝试通过分析循环运行次数推导时间复杂度：外层循环中i每次翻倍，直到i < n；内层循环每次运行i次。我最初推测复杂度为O(n log n)，但困惑于如何对各次外层循环的内层操作数求和（该求和为几何级数），恳请告知正确的时间复杂度及推理逻辑。

正确时间复杂度：O(n) #

推理逻辑 #

1. 外层循环执行次数
   外层循环中i的取值是1, 2, 4, 8, ...，每次翻倍直到i < n。设循环执行k次，第k次的i值为2^(k-1)，当2(k-1) < n时停止，可得k ≈ log₂n，即外层循环次数为O(log n)级。

2. 内层循环总操作次数求和
   每次外层循环对应内层循环执行i次，总操作次数是所有i的和：
   S = 1 + 2 + 4 + 8 + ... + 2^(k-1)
   这是首项为1、公比为2的几何级数，求和公式为S = 2^k - 1。
   根据外层循环停止条件，2^(k-1) < n ≤ 2^k，代入求和公式得：
   S = 2^k - 1 < 2n - 1
   显然2n-1与n是同阶的，所以总操作次数是O(n)级。

3. 结论
   总操作次数的上限是线性的，因此这段代码的时间复杂度为O(n)，而非你最初推测的O(n log n)。错误的根源是误判了几何级数的求和结果——该等比数列的和趋近于2n，并非n与log n的乘积。

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