下列函数的时间复杂度是（ ）。

int func(int n) {
    int i = 0, sum = 0;
    while(sum < n)
        sum += ++i;
    return i;
}

复杂度分析

A. (O(n)) B. (O(\sqrt{n})) C. (O(\log_2 n)) D. (O(n\log_2 n))

[tag_link]

正确答案：B

sum += ++i;相当于++i; sum = sum + i;进行到第 k 趟循环，sum = (1+k)*k/2。显然需要进行O(n1/2)趟循环，因此这也是该函数的时间复杂度。