该算法的时间复杂度分析过程

Question

void func(int n) {
int i=0,s=0;
while (s<=n) { s=s+i; i++; }}

Answer 1

i=0,s=0, i=1,s=1
i=1,s=1, i=2,s=1+2
i=2,s=1+2, i=3,s=1+2+3
如果循环执行m次，则有:1+2+3.......+m+k=n(其中k为常数，用作不缺),1+2+3+....m的递推式为s=m(m+1)/2.
求递推式要用到：等差数列求和：s=na+dn(n-1)/2,其中a为首项，d为公差
求n公式：△=b^2-4ac
最后解得：T(n)=O(√n) ，要把n的系数变为1
因此时间复杂度o(根号n)