fun（）の時間の複雑さ？

Question

私は時間の複雑さを計算するためにこの質問を行っていました。

int fun(int n) 
{ 
    int count = 0; 
    for (int i = n; i > 0; i /= 2) 
    for (int j = 0; j < i; j++) 
     count += 1; 
    return count; 
} 

私の第一印象はOた（N Nをログ）が、答えはO（N）です。なぜそれがO（n）であるのか理解してください。

Answer 1

内側ループは、内側ループの反復の総数であるので等次いでn反復、n/2、次いでn/4を行います。したがって

n + n/2 + n/4 + n/8 + ... + 1 
<= n * (1 + 1/2 + 1/4 + 1/8 + ...) 
= 2n 

（Geometric seriesを参照）、およびO（N）です。