算法時間複雜度算例

Question

我最近明白了大哦的表示法。我最近遇到了書中給出的例子。

void Function(int n) 
{ 
int i=1 ; 
int s=1 ; 
while(s <= n) 
{ 
i++ ; 
s= s+i ; 
print(\*"); 
} 
} 

我不知道作者如何到達上述算法的時間複雜度爲O（√n）。我只是想了解達成這個結論的過程？

Answer 1

它可以很容易地被視爲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 i.e. 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)。