c++ - 函数复杂度分析

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。