c++ - 功能复杂度分析

Question

我怎样才能得到这个功能的成本？我知道它是 O(√n) 但除了尝试很多 n 值并获得一个模式之外，我不知道如何找到它。

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

标签： c++complexity-theory

Answer 1

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

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

所以xin 循环增加了O(t^2). 所以while循环的次数将被摊销到O(sqrt(n))，因为y增加x直到达到n。