我该如何获取这个函数的成本?我知道它是O(√n),但除了尝试很多n值并获得模式之外,我不知道如何找到它。
void foo(int n) {
int x = 2;
int y = 1;
while(y <= n) {
y += x;
++x;
}
}
我该如何获取这个函数的成本?我知道它是O(√n),但除了尝试很多n值并获得模式之外,我不知道如何找到它。
void foo(int n) {
int x = 2;
int y = 1;
while(y <= n) {
y += x;
++x;
}
}
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
。
观察y
值,在x
次迭代后,y
的值将为:
step 1 2 3 4 x
y= 1+2+3+4+...+x
y>n
时循环停止,这意味着当1+2+...+x>n
时。在此时(当y>n
),我们已经迭代了x
次(是的,与之前的方程中的相同的x
!)1+2+...+x = x(x+1)/2 = O(x^2)
(1)+(2): 当x^2>n
或经过√n
次迭代后,循环停止。