アルゴリズム時間複雑度：ループ内のi/= 2

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（nlogn）になりますが、答えはO（n）です。アルゴリズム時間複雑度：ループ内のi/= 2

私のロジックは、外側ループが指数関数的な低下を示し、log_base2_（N）回発生します。内部ループは幾何学的な合計（最初の反復はN/2回、次にN/4、N/8 ...）になると合計N回実行されます。これらをまとめて、入れ子になったループの結果としてそれらを掛け合わせると、それがO（NlogN）を思いついています。明白なものがありませんか？

出典

2017-09-13 user6142489

外部ループは合計log（n）回実行されます。今、あなたはそれをそれが実行n回、次のn/2倍というように、それはシリーズ

n(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)

はこれの合計が（2 * n）でになります初めて内側のループを観察する場合には、つまり、O（n）

外部ループはO（logn）回、内部ループはO（n）回実行されるため、時間の複雑さはO（n）です。

内側ループは、各時間がかかるN手順ないので、それは実際に撮影したすべてのステップの合計はO（N）

出典

2017-09-13 11:03:03 marvel308

これは有用であるだろう、O（nlogn）ではありません。私は、操作の総数を実行時間と混同していたと思います。あなたのポイントを正しく理解すれば、時間の複雑さは2つのループの悪いものになります。この場合、O（n）です。 – user6142489

@ user6142489一般に、2つのループの中で最悪ではありませんが、最も内側のループの繰り返しの合計数です。したがって、この答えで指摘したように、O（n）の合計を与えるそれぞれの合計を実行する必要があります。ただし、通常の手順では、各ループの複雑さの_product_（つまり、_max_ではない）を取ることになっていますが、ここではあまりにも緩やかな境界になります。最も内側のループの反復回数は、現在の値_私_。 – qwertyman

興味深い。ありがとうございました。 – user6142489

アルゴリズム時間複雑度：ループ内のi/= 2

答えて

関連する問題