算法时间复杂度的例子
我最近明白了大哦的表示法。 我最近遇到了书中给出的例子。
void Function(int n)
{
int i=1 ;
int s=1 ;
while( s <= n)
{
i++ ;
s= s+i ;
print(*");
}
}
我不知道作者作为O（√n）是如何到达上述算法的时间复杂度的。 我只是想了解达成这个结论的过程？
可以很容易地看出，随着s is growing quadratic in terms of number of iteration ， s is growing quadratic in terms of number of iteration 。
s = 1 // set as 1 initially现在我们加入S = s + i // Where i increasing linearly by one unit in each iteration
//So it's just a addition ie s = 1 + 2 + 3 +4 ....+i, which will sum up to s = i(i+1)/2因此s = i(i+1)/2 = (i^2+i)/2其中i是迭代次数。
现在，在i迭代我们得到s = (i^2+i)/2为了得到s >=n ，我们只需要√n迭代。 因此，给定程序的时间复杂度将为O(√n) 。