complexity-theory - 与えられたコードの最悪のケースでの時間計算量を決定します

Question

最悪の場合の時間計算量を決定します。(計算を表示)

  int i = 1;
  int j = 4;
  while (i<(n*n)&& j<(n*n*n*n)){
    if (i%3 == 0) i+=3; 
    else i+=4;

    if (j%2 == 0) j*=4;
    else j*=2;          
 }

Answer 1

最悪の場合、これは i が n^2 に到達するか j が n^4 に到達するのが最も早い方で実行されます。変数 i は直線的に増加し、j は反復ごとに指数関数的に増加します。j は、反復ごとに異なる 4 の累乗になっています。

O(n^2) である n^2/3 回の繰り返しの後、i は n^2 に到達します。j は、log_4 n^4 回の反復後に n^4 に到達します (ここで、log_4 は底が 4 の対数です)。

したがって、n^2 と log(n^4) のどちらが大きいかという問題があり、答えは圧倒的な n^2 です。

したがって、このアルゴリズムは O(n^2)