Big-O-Analyse für eine Schleife

Question

Ich muss diese Schleife unter anderem analysieren und ihre Laufzeit mit Big-O-Notation bestimmen.

for (int i = 0; i < n; i += 4) 
    for (int j = 0; j < n; j++) 
     for (int k = 1; k < j*j; k *= 2)` 

Hier ist, was ich bisher:

for (int i = 0; i < n; i += 4) = n 

---

for (int j = 0; j < n; j++) = n 

---

for (int k = 1; k < j*j; k *= 2) = log^2 n 

Jetzt das Problem, das ich kommen werde, um die endgültige Laufzeit der Schleife ist. Meine beste Schätzung ist O (n^2), aber ich bin unsicher, ob das korrekt ist. Kann jemand helfen?

Edit: sorry über die Oh -> O Sache. Mein Lehrbuch verwendet „Big-Oh“

Answer 1

Zunächst ist zu beachten, dass die äußere Schleife von dem verbleibenden zwei unabhängige - sie fügt einfach einen (n/4)* Multiplikator. Wir werden das später berücksichtigen.

Nun wollen wir die Komplexität der

for (int j = 0; j < n; j++) 
    for (int k = 1; k < j*j; k *= 2) 

Wir betrachten die folgende Summe:

0 + log (1) + log (2 * 2) + ... + lügen (n * n)

Es ist gut, dass (n^2) = 2 *beachten lügen lügen2 (n). So neu Faktor wir die Summe an:

2 * (0 + (1) log + (2) log + ... + log (n))

Es ist nicht sehr einfach, diese Summe zu analysieren, aber werfen Sie einen Blick auf this post. Mit der Approximation von Sterling kann man sagen, dass es zu O(n*log(n)) gehört. So ist die Gesamtkomplexität ist O((n/4)*2*n*log(n))= O(n^2*log(n))

Answer 2

Zeitkomplexität einer Schleife als betrachtet wird O (n), wenn die Schleifenvariablen erhöht/um einen konstanten Betrag verringert (die c in den Beispielen unten ist):

for (int i = 1; i <= n; i += c) { 
     // some O(1) expressions 
    } 

    for (int i = n; i > 0; i -= c) { 
     // some O(1) expressions 
    } 

Die Zeitkomplexität verschachtelter Schleifen entspricht der Anzahl der Ausführungen der innersten Anweisung. Zum Beispiel können die folgenden Beispiel Schleifen haben O (n²) Zeitkomplexität:

for (int i = 1; i <=n; i += c) { 
     for (int j = 1; j <=n; j += c) { 
      // some O(1) expressions 
     } 
    } 

    for (int i = n; i > 0; i += c) { 
     for (int j = i+1; j <=n; j += c) { 
      // some O(1) expressions 
    } 

Zeitkomplexität einer Schleife als O (logn) betrachtet wird, wenn die Schleifenvariablen unterteilt ist/um einen konstanten Betrag multipliziert: Jetzt

for (int i = 1; i <=n; i *= c) { 
     // some O(1) expressions 
    } 
    for (int i = n; i > 0; i /= c) { 
     // some O(1) expressions 
    } 

haben wir:

for (int i = 0; i < n; i += 4) <----- runs n times 
    for (int j = 0; j < n; j++) <----- for every i again runs n times 
     for (int k = 1; k < j*j; k *= 2)` <--- now for every j it runs logarithmic times. 

So Komplexität ist O (n²logm) wobei m ist n², das vereinfacht werden kann zu O (n²logn) weil n²logm = n²logn² = n² * 2logn ~ n²logn.

Answer 3

• In Bezug auf j ist die innere Schleife O(log_2(j^2)) Zeit, aber sine log_2(j^2)=2log(j), es ist tatsächlich O(log(j)).

• Für jede Iteration der mittleren Schleife dauert es O (log (j)) Zeit (die inneren Schleife zu tun), so müssen wir es zusammenzufassen:

  Summe {log (j) | j = 1, ..., n-1} log (1) + log (2) + ... + log (n-1) = log ((n-1)!)

Und seit log((n-1)!) ist in O((n-1)log(n-1)) = O(nlogn), können wir schließen, mittleren mittleren Schleife dauert O(nlogn) Operationen.

• Beachten Sie, dass die beiden mittleren und inneren Schleife von i unabhängig sind, so zu die Gesamtkomplexität erhalten, können wir nur n/4 (Anzahl der Wiederholungen von äußeren Schleife) multiplizieren mit Komplexität der mittleren Schleife, und erhalten:

  O (n/4 * nlogn) = O (n^2logn)

So Gesamtkomplexität dieses Codes ist O(n^2 * log(n))