奇妙に入れ子になったループの時間複雑度

for(i=1;i<n*n;i++) 
    for(k=1,l=1;l<n;k=k+2,l=l+k) 
     foo;

このような構造の時間の複雑さはどのように推定できますか？ループによって、このループを見て奇妙に入れ子になったループの時間複雑度

2011-12-30 mrjames

：

外側のループは1からnまでの二乗され、従ってO(n^2)
インナーループは1からnまでであるが、手順は、1、4、9、16であります.. 。代わりに、1、2、3、4の...、それゆえO(sqrt(n))

ネストされたループは、複雑さを掛けるので、私たちは一般的にO(sqrt(n)*n^2)またはO(n^2.5)

2011-12-30 03:02:06 ridecar2

：

for (i = 1; i < n * n; i ++) for (l = 1 ; l * l < n ; l = l ++) foo;

したがって、あなたは以下のように、正式に成長複雑さの正確な順序を推測するためにシグマ表記を使用して、それを表現することができます。以下のような内側のループでは一定の割合でインクリメントしていません - 内側の方がO（sqrt（n））に近いと思います。 –

公正なポイント、編集の回答が今すぐです。 – ridecar2

のために行くridecar2正しいですが、時にはあなたが得ることができるので、注意してくださいトリック質問どこにあなたのアルゴリズムを簡略化することができ

for(int i=0; i<n; i++) 
for(int j=0; j<n; j++) 
    doStuff();

2011-12-30 03:10:37 Mr1159pm

私はそのすべてを 'O（n^2）'と書いていますが、私は正しいでしょうか？ – ridecar2

あなたは私のことを言っているのですか？私の例は間違いなくO（n）ですが、彼のケースでは必ずしもデータのサイズである必要はありませんので、慎重にお勧めします。 – Mr1159pm

あなたのものは、 'O（n^2）'を与えるn回実行する別のループの中でn回実行するループです。 – ridecar2

：あなたのデータのサイズは、その配列の反復は同じように見えるという事実にもかかわらず、O（n）がないはO（n^2）であることを意味し、n個の* nの配列であり、 lはあるものの

enter image description here

2014-03-30 15:44:38

答えて