for-loop - ネストされた for ループの複雑さを計算する

Question

このネストされた for ループの複雑さを計算したい:

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

このコードの大きな複雑さを見つけるには、どのような戦略を使用しますか?

Answer 1

外側のループは1、2、4、8、... nを通過します。これは、 nに到達するまでO（lg n）回だけ2倍にできるため、O（lg n ）ステップを実行します。

内側のループも同じです。それはiまでしか上がりませんが、外側のループの最後の反復で、iは再びnである最大値に達するので、これもO（lg n）です。

これをまとめると、O（（lg n ）²）の上限が得られます。これは一般にO（lg²n）と省略されます。

Answer 2

自分で答えを導き出すための戦略

n のさまざまな値を式に代入し、ループの最も内側の部分が実行される回数のグラフを作成します。

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

このようなもの：

n     num_times_inner_loop_part_runs
1     1
2     3
3     3
4     6
5     6
6     6
7     6
8     10
9     10
...
15    10
16    15
...
31    15
32    21

これらのデータ ポイントは、次のようなプログラムで取得できます。

int n = 9;  //change this n
int counter = 0;
for(i=1; i<=n; i*=2){
  for(j=1; j<=i; j*=2){
    s++;
    counter++;
  }
}
cout << "counter is: " <<  counter << endl;

実行を X/Y 座標平面にプロットするnum_times_inner_loop_partと、曲線が表示されます。

最も近い曲線に名前を付けます。この場合、X = (log(Y)^2)

データ と をプロットするとX = (log(Y)^2)、それらが互いに重なり合う必要があることがわかります。

したがって、この関数の複雑さは次のとおりですO((log(n))^2)。O(n)

Answer 3

このコードの時間分析:

Answer 4

アルゴリズムの時間の複雑さは、次のように正式に表すことができます。

このドキュメント(最後のスライド) は、あなたにとって非常に役立つかもしれません。