为何这段代码的时间复杂度是O(√n)？求数学推导方法

先把你给出的代码整理成代码块：

i:=1
p:=0
for (p < n) do 
   p = p+i
   i+=1

要推导它的时间复杂度，核心是计算循环执行的次数k：

1. 分析每次循环的p值变化
   每次循环里，p会累加当前的i，然后i自增1。循环执行k次后，p的值是从1到k的等差数列求和：
   p = 1 + 2 + 3 + ... + k
   根据等差数列求和公式，这个和等于 k*(k+1)/2。

2. 确定循环停止的条件
   循环在p ≥ n时退出，也就是当k*(k+1)/2 ≥ n时，循环不再执行。我们需要找到满足这个不等式的最小k值。

3. 推导k和n的量级关系
   因为k是正整数，k和k+1的数值非常接近，我们可以近似把k*(k+1)看成k²，那么不等式可以简化为：
   k²/2 ≥ n
   变形后得到：
   k² ≥ 2n → k ≥ √(2n)

从这个结果能看出，k的增长速度和√n是一个量级的，所以这段代码的时间复杂度是O(√n)。

为什么不是O(n)？因为每次循环p的增量是越来越大的（从1开始每次加1），不是固定累加某个常数，所以循环次数不会跟着n线性增长，而是跟着n的平方根增长。比如n=100时，循环只需要执行14次就会停止，远小于100次，这也能验证推导的结论。

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