请求对给定程序代码进行渐近分析，本人分析过程中遇阻

先看这段代码的执行逻辑：

i = 1;
k = 1;

while(k<n){
    k = k+ i;
    i = i + 1;
}

我们通过推导循环执行次数来确定时间复杂度：

• 初始状态：k=1，i=1
• 第1次循环后：k=1+1=2，i=2
• 第2次循环后：k=2+2=4，i=3
• 第3次循环后：k=4+3=7，i=4
• ...
• 第t次循环后：k = 1 + (1+2+3+...+t)

根据等差数列求和公式，1+2+...+t = t(t+1)/2，因此t次循环后k = 1 + t(t+1)/2。

循环终止条件是k >= n，代入后可得：

1 + t(t+1)/2 >= n

忽略常数项1，近似得到t(t+1)/2 ≈ n。当t足够大时，t和t+1的差异可忽略，进一步简化为t²/2 ≈ n，解得t ≈ √(2n)。

因此，这段代码的时间复杂度是O(√n)。

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