Big O für spezifische Doppel für Schleife

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"); 
      } 
     } 
    } 
} 

So versuche ich die asymptotische Komplexität (Big O) für diesen spezifischen Codeblock zu finden.

Mein Denken: die erste für Schleife ist O (N), und weil die Hälfte der Zeit ungerade und die andere Hälfte der Zeit ist es gerade, ist es immer noch O (N) für die for-Schleife innerhalb der if-Anweisung und O (Log N) für die for-Schleife innerhalb der else-Anweisung wegen j * = 2. Also für meine letzte Antwort habe ich O (N^2 (Log N)), aber anscheinend ist die Antwort nur O (N^2). Ich habe mich gefragt, ob irgendjemand mir erklären könnte, wo ich falsch liege? Vielen Dank!

Answer 1

Es ist O (N). Der Grund ist, wenn ich gerade ist, ist die j-Schleife O (N), und das passiert O (N) mal; N * N ist N .

Es ist nicht wichtig, dass j um 2 erhöht wird; O (N/2) == O (N).

Es ist auch nicht wichtig, dass wenn i ungerade ist, dass die j-Schleife O (log N) ist - das wird nur Rauschen auf der langsameren Schleife.

Answer 2

Die O(Log N) Laufzeit der inneren Schleife ist nur für ungerade Werte von i (die die Hälfte der möglichen Werte von i sind) korrekt. Für gerade Werte von i wird die innere Schleife eine Laufzeit von O(N) haben, da j in jeder Iteration um 2 inkrementiert wird.

Also, was Sie haben, ist

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

die O (N), da der erste Term (die sich asymptotisch der schneller wachsenden Begriff ist) wird N /8, die asymptotisch heißt O (N).