time - 以下的时间复杂度

Question

int i=1,s=1;
while(s<=n)
{
i++;
s=s+i;
}

时间复杂度为 O(root(n))。我不明白它是怎么回事。因为这个系列就像 1+2+...+k 。请帮忙。

score 2 · Accepted Answer

让循环执行x次数。现在，只要s小于，循环就会执行n。

我们有：

第 1 次迭代
s = s + 1
后：第 2 次迭代后：
s = s + 1 + 2

随着它进行 x 次迭代，最后我们将有

1 + 2 ... + x <= n

=>(x * (x + 1)) / 2 <= n

=> O(x^2)<= n

=> x= O (root(n))

score 1 · Accepted Answer

s(k) = 1 + 2 + 3 + ... k = (k + 1) * k / 2

因为s(k) >= n你至少需要 k 步。n = (k + 1) * k / 2，因此k = -1/2 +- sqrt(1 + 4 * n)/2；

你忽略了常数和系数O(-1/2 + sqrt(1+4n)/2) = O(sqrt(n))

score 0 · Accepted Answer

这计算总和s(k)=1+2+...+k并在时停止s(k) > n。

因为，需要超过s(k)=k*(k+1)/2的迭代次数是。s(k)nO(sqrt(n))

3 回答 3