forループをネストした3のBig O？

Question

public int Loop(int[] array1) { 
     int result = 0; 
     for (int i = 0; i < array1.length; i++) { 
      for (int j = 0; j < array1.length; j++) { 
       for (int k = 1; k < array1.length; k = k * 2) { 
        result += j * j * array1[k] + array1[i] + array1[j]; 
       } 
      } 
     } 
     return result; 
    } 

私はここで算術演算の数を数える複雑さ関数を見つけようとしています。私は複雑さのクラスがO（n^3）であることを知っていますが、私はステップを数えるのに苦労しています。

これまで私が推論してきたのは、算術演算の数を8と数えるため、複雑さ関数はちょうど8n^3になりますか？

正しい方向のガイダンスは大変ありがとうございます。ありがとうございます！

Answer 1

第3のループが実行されますが、第二のループはn回実行されますlog(n)回（ベース2）。逆の操作でログを取ることになるたびに、kに2を掛けているためです。乗算済みO(n^2 log(n))

Answer 2

我々は以下が一つの大きなステップであることに同意することができた場合： result += j * j * array1[k] + array1[i] + array1[j] が、その後のは、そのincrementResult呼ぶことにしましょう。

incrementResultここでは何回ですか？ （ログn）

for (int k = 1; k < array1.length; k = k * 2) { 
    // incrementResult 
} 

はLOOP3ことを呼び出すことができます。それでは何度、loop3と呼んでいますか？ （n）は

for (int j = 0; j < array1.length; j++) { 
    // loop 3 
} 

のは、LOOP2ことを呼ぶことにしましょう。次に、loop2を何回呼んでいますか？ （n）は

for (int i = 0; i < array1.length; i++) { 
    // loop 2 
} 

乗算最初のループがn回実行されますそれらとあなたがあなたの答えを得るでしょう、すべての:)

Answer 3

これはループによって異なります。例えば、

for (int i = 0; i < 10; i++) { 
    for (int j = 0; j < 10; j++) { 
     for (int k = 0; k < 10; k++) { 
      sum += i * j * k; 
     } 
    } 
} 

は、反復回数が入力に全く依存しないため、複雑さO（1）を有する。

またはこの：

for (int i = 0; i < n*n*n*n*n*n; i++) { 
    sum += i; 
} 

は、単一のループが存在するにもかかわらず、O（N^6）です。

本当に重要なことは、ループが何回繰り返されるかです。

あなたの場合、最も内側のループの各繰り返しがO（1）であることは容易にわかります。何回繰り返しますか？あなたがnに達するまで、何回何倍に番号を付ける必要がありますか？ xが反復回数であれば、k = 2^x> nとなる最初のxでループを終了します。あなたはxのためにこれを解決できますか？

2番目のループの各反復でこれが行われるため、2番目のループのコストは、（この時間を数えるのが簡単な）反復の回数と内側ループのコストの時間です。

最初のループの各反復でこれが行われるため、最初のループのコストは2番目のループのコストに反復回数（簡単に数えられる）です。

全体的にランタイムは、3つの数値の積です。あなたはそれらを見つけることができますか？