下面这段代码的算法的时间复杂度是多少，最好能解释下思路

Question

下面这段代码的算法的时间复杂度是多少，最好能解释下思路

i= s = 0;
while (s<n)
{
    i++;
    s+=i;
}

Answer 1

暴力法(因为我脑子懒但手勤快)

$ cat complex.groovy

def doit(int n){ 
    int i= s = 0;
    int count=0;
    while (s<n)
    {
        i++;
        s+=i;
        count ++;
    }
    println Math.sqrt(n)+" "+count;
}


doit(1);
doit(10);
doit(100);
doit(1000);
doit(10000);
doit(100000);
doit(1000000);

$ groovy complex.groovy

1.0 1
3.1622776601683795 4
10.0 14
31.622776601683793 45
100.0 141
316.22776601683796 447
1000.0 1414

所以算法复杂度是根号(2n): (2n)^1/2, 一般忽略常数系数, O(n^(1/2))
把 s 打印出来,很容易发现规律的.

1
3
6
10
15
21
28
36
45
55
66
78
91
105
...

PS: 根号2的新求法 ;)

Answer 2

设 i 刚好终止，由求和公式得到 (0 + i) * (i + 1) / 2 >= n，保留最高阶 i^2，得到 O(sqrt(n)) 时间复杂度。

Answer 3

O(n^1/2)