功能复杂度分析

Question

我该如何获取这个函数的成本？我知道它是O(√n)，但除了尝试很多n值并获得模式之外，我不知道如何找到它。

void foo(int n) {
    int x = 2;
    int y = 1;
    while(y <= n) {
        y += x;
        ++x;
    }
}

- polmonroig

Answer 1

sum(1,2,3,4,...,t)的结果是什么？它等于：

sum(1,2,3,4,...,t)=(t*(t+1))/2

因此，循环中的x会按照O(t^2)增加。因此，while循环的次数将被摊销为O(sqrt(n))，因为y会增加x直到达到n。

- Afshin

Answer 2

观察y值，在x次迭代后，y的值将为:

step   1 2 3 4     x
y=     1+2+3+4+...+x

(1) 当y>n时循环停止，这意味着当1+2+...+x>n时。在此时（当y>n），我们已经迭代了x次（是的，与之前的方程中的相同的x！）

(2) 我们还知道1+2+...+x = x(x+1)/2 = O(x^2) (1)+(2): 当x^2>n或经过√n次迭代后，循环停止。

- Emadpres

Answer 3

让我们看看在第i次迭代后，y的值是多少：

y = 2+...+i 当y > n时，循环结束，所以你真正要问的是在哪一次迭代中这个条件变为真？

y > n实际上是2+..+i > n。我们知道2+..+i = (n(n+1))/2 -1，因此y>n变成(i(i+1))/2 > n+1，解得i^2 +i > 2n+2。从这里很容易看出i是O(sqrt(n))。 第一次不等式y > n成立的值与sqrt(2n+2)成比例。

请注意，由于著名的闭合公式sum(1,2,3,...,k) = 1+2+3+...+k = (k(k+1))/2，所以2+..+i = (n(n+1))/2 -1。

- Davide Spataro