ループ複雑

for(k = 1; k <= n; ++k){ 
    for(j = 1; j * j <= k; ++j){ 
     //O(1) operations 
    } 
}

私は外側のループがn回反復し、内側のループは、外側のループからすべてのk番目の反復のためにfloor(sqrt(k))を繰り返すことを知っています。

Therforeは、時間の複雑さを決定するために、我々は、のような

\sum_{k=1}^{n} \floor{\sqrt{k}}

進むとnの面で閉じた形の時間の複雑さを取得する方法がわからないの合計が何かを持っています。

2016-04-07 hello

[google検索]（http://mathforum.org/library/drmath/view/65309.html）が役立つ可能性があります。 – anukul

sqrt（n）=> n ^（1/2）を積分する必要があると言います。結果はn ^（3/2）です。床機能については忘れてください。

2016-04-07 15:10:45 marom

@ciamejあなたが正しいです。私はそれを訂正した。 – marom

外側ループが反復されますn回、内側ループが繰り返されますsqrt(n)回。 1つのループが別のループの内部にある場合、その複雑さは増します。したがって、それは実行するO(n^1.5)

2016-04-07 16:38:11 smttsp

"あるループが別のループの内側にある場合、それらの複雑さは増します。 - それほど単純ではありません。 –

@ KarolyHorvath：これはどうですか？「あるループが別のループの内部にあり、相互に排他的である場合、その複雑さは増しますか？ – smttsp

この場合、そうではありません。 –

答えて