嵌套循环时间复杂度求解：几何级数计算结果存疑

给定代码：

i = n;
while (i >= 1)
{ 
    for (k = 1; k <= i; k++) 
    {
       S;
    }
    i = i / 2;
}

其中S是不修改i、k或n的O(1)操作，求解这段代码的时间复杂度。

你的推导过程 #

• 外层第一次迭代，内层循环执行n次
• 第二次迭代，内层执行n/2次
• 第三次迭代，内层执行n/4次
• ...
• 最后一次迭代，内层执行1次

你将求和式写为：$1+...+\frac{n}{8}+\frac{n}{4}+\frac{n}{2}+n$，并使用首项1、公比2、项数$\log n$的几何级数公式计算得到$S_n = n-1$，但对ChatGPT给出的约2n的结果存疑。

错误分析与正确推导 #

你的求和顺序不影响结果，但公式应用有误：

• 正确的几何级数求和应该以首项n、公比1/2来计算，求和式为$n + \frac{n}{2} + \frac{n}{4} + ... + 1$
• 根据几何级数求和公式$S = a_1 \cdot \frac{1 - r^m}{1 - r}$（其中$a_1$为首项，$r$为公比，$m$为项数）：
  • 这里$a_1 = n$，$r = 1/2$，项数$m = \log_2 n + 1$（因为i从n降到1，每次除以2，共$\log_2 n +1$次迭代）
  • 代入公式得：$S = n \cdot \frac{1 - (1/2)^{\log_2 n +1}}{1 - 1/2} = n \cdot \frac{1 - 1/(2n)}{1/2} = 2n -1$
• 忽略常数项后，时间复杂度为O(n)，而ChatGPT给出的“约2n”是精确求和的结果，本质上和O(n)等价（时间复杂度只关注阶数，常数系数不影响）。

你之前误用了项数：如果以1为首项、2为公比求和，公式为$S = \frac{2^m -1}{2-1}$，其中$m = \log_2 n +1$，代入得$2^{\log_2 n +1} -1 = 2n -1$，和正确结果一致。你之前错误地将项数写成$\log n$，少算了一次迭代，导致结果偏差为$n-1$。

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