函数复杂度分析

Question

如何获取此功能的费用？我知道它是 O(√n)，但除了尝试很多 n 个值并获得一个模式外，我不知道如何找到它。

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

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.

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 次迭代后循环停止。

Answer 3

让我们看看 y 在 i 次迭代后的值：

y = 2+...+i 循环在 y > n 时结束，所以您真正要问的是在第 i 次迭代时此条件变为真？

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) 成正比。

注意2+..+i = (n(n+1))/2 -1因为著名的闭合公式sum(1,2,3,...,k) = 1+2+3+...+k = (k(k+1))/2

函数复杂度分析

Function Complexity Analysis

c++

complexity-theory