求含递增变量累加操作的while循环的时间复杂度

首先给出待分析的代码：

int i=1,s=1;
while (s<=n)
    i++
    s+=i;
    print("*")

当n=10时，循环运行4次，手动验证过程如下：

• 初始状态：i=1，s=1
• 第1次循环：i变为2，s=1+2=3，打印*（s=3≤10，继续）
• 第2次循环：i变为3，s=3+3=6，打印*（s=6≤10，继续）
• 第3次循环：i变为4，s=6+4=10，打印*（s=10≤10，继续）
• 第4次循环：i变为5，s=10+5=15，打印*（s=15>10，循环终止）

推导过程 #

我们需要找到循环运行次数k与n的数学关系：

1. 观察s的变化规律：每次循环中i递增1，s累加当前i值。初始s=1，第k次循环执行前，s的值是1+2+3+...+k（第1次循环前s=1，第2次前s=1+2，以此类推）。
2. 循环终止条件是s > n，因此循环运行k次的核心条件为：

   1+2+...+k ≤ n < 1+2+...+(k+1)

3. 代入等差数列求和公式1+2+...+k = k(k+1)/2，得到不等式：
   $$\frac{k(k+1)}{2} \leq n < \frac{(k+1)(k+2)}{2}$$
4. 当n趋近于无穷大时，低阶项和常数项可忽略，不等式近似为：
   $$\frac{k^2}{2} \approx n$$
   解得：
   $$k \approx \sqrt{2n}$$

结论 #

该循环的时间复杂度为O(√n)（平方根阶），而非推测的O(log₂n)。循环运行次数与n的平方根成正比，增长速度慢于线性阶，但快于对数阶。

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