特定のdouble forループのBig O

Question

public void f7(int N) { 
    for (int i = N/2; i > 0; i--) { 
     if (i % 2 == 0) { 
      for (int j = 0; j < N; j += 2) { 
       System.out.println("Hey"); 
      } 
     } else { 
      for (int j = 1; j < N; j *= 2) { 
       System.out.println("You"); 
      } 
     } 
    } 
} 

私はこの特定のコードブロックの漸近複雑度（Big O）を見つけようとしています。

私の考え方：最初のforループはO（N）であり、時間の半分が奇数であり、残りの半分が偶数であるため、forループのO（N） if文の中では、そして、else文の中のforループのためのO（Log N）は、j * = 2のためです。したがって、私の最終的な答えはO（N^2（Log N））です。ちょうどO（N^2）。誰かが私の考えでどこが間違っているのかを説明できるかどうか疑問に思っていましたか？ありがとう！

Answer 1

これはO（N ）です。理由は、iが偶数であり、jループがO（N）であり、O（N）回発生するからです。 N * NはN である。

jが2増分することは重要ではありません。 O（N/2）== O（N）である。

私が奇妙なときには、jループがO（log N）であることは重要ではありません。これは遅いループでノイズになるだけです。

Answer 2

O(Log N)内部ループの実行時間は、奇数の値がi（可能な値の半分はi）のみです。 iの偶数の値の場合、jは各繰り返しで2ずつ増加するため、内部ループの実行時間はO(N)になります。

（漸近的に速く成長している用語である）第1項は漸近的であるN /8、ですので、それではあなたが持っていることは、O（N ）である

(N/4 * N/2) + (N/4 * log(N)) 
    even i   odd i 

ですO（N ）である。