java - 我如何根据大 O 符号找到这个函数的增长率？

Question

如何找到基于大 O 表示法的增长率函数？

for(i=1; i*i<n; i=i+1)
    for(j=1; j<=i; j=j+1)

Answer 1

见下文

当i=1时，innerloop运行1次

外循环 i=2,innerloop运行2次

外循环 i=3,innerloop运行3次

外循环 i=4,innerloop运行4次

....

outloop i=sqrt(n)-1,innerloop 运行 sqrt(n)-1 次，循环在这里终止

以免假设n 是一个完美的正方形

==> f(n) = 1 + 2 + 3 + 4 + ... + sqrt(n) - 1 = (sqrt(n) - 1 )/2 x ( sqrt(n) - 1 + 1)

==> f(n) = ( (sqrt(n)^2)/2 - sqrt(n)/2 

==> O( sqrt(n)^2)/2 - sqrt(n)/2 ) = O( n - sqrt(n) )

==> O( n - sqrt(n) )
==> O( n )

所以它大约需要 O(n)