Großes O für 3 verschachtelte For-Loops?

-1

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

Ich versuche, die Komplexitätsfunktion zu finden, die die Anzahl der arithmetischen Operationen hier zählt. Ich weiß, dass die Komplexitätsklasse O (n^3) sein würde, aber ich habe ein bisschen Mühe, die Schritte zu zählen.Großes O für 3 verschachtelte For-Loops?

Meine bisherige Argumentation ist, dass ich die Anzahl der arithmetischen Operationen, die 8 ist, zählen, also wäre die Komplexitätsfunktion einfach 8n^3?

Jede Führung in die richtige Richtung würde sehr geschätzt werden, danke!

Quelle

2017-09-13 ellaaur

Sind Sie sicher, dass die Komplexität "O (n^3)" ist? Ich meine, sicher, es wäre in "O (n^3)", genauso wie es in "O (n!)" Ist, aber das ist nicht die engste Grenze. –

Hm Ich meine, die Art, wie wir in der Klasse unterrichtet wurden, bestand darin, die Anzahl der Schritte (arithmetische Operationen) zu zählen und dann zu zählen, wie oft jede Operation gemacht werden musste. So kam ich zu O (n^3). Ich kann aber definitiv falsch liegen. Ich folgte auch der Logik, dass 2 verschachtelte For-Loops normalerweise 0 (n^2) von dem waren, was ich bisher gemacht habe. – ellaaur

Denken Sie sorgfältig über das 'k = k * 2' im innersten' ForUpdate' nach. –

Die erste Schleife n Mal ausgeführt wird, wird die zweite Schleife n mal laufen jedoch die dritte Schleife laufen log(n) mal (Basis 2). Da Sie k mit zwei Mal multiplizieren, würde die umgekehrte Operation sein, das Protokoll zu nehmen. Multiplizieren wir haben O(n^2 log(n))

Quelle

2017-09-13 22:36:11 Mitchel0022

Ah okay! Dies ist für die Komplexitätsklasse sinnvoll. Zum Zählen der genauen Operationen ist die Funktion einfach nur f (n) = 8n^2 log (n) oder? – ellaaur

Wenn wir zustimmen, dass die folgende ist ein großer Schritt: result += j * j * array1[k] + array1[i] + array1[j] dann nennen wir das incrementResult. Wie oft ist incrementResult hier genannt? (log n)

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

Lets Anruf, dass LOOP3. Dann wie oft ist loop3 hier genannt? (n)

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

ist, dass loop2 Lassen nennen. Dann, wie oft ist loop2 hier genannt? (n)

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

Multiply von allen und Sie Ihre Antwort bekommen :)

Quelle

2017-09-13 22:34:25 Jon

Das hängt von den Schleifen ab. Zum Beispiel:

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

hat Komplexität O (1), da die Anzahl der Iterationen nicht bei allen auf den Eingang ab.

Oder diese:

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

ist O (n^6), auch wenn es eine einzige Schleife ist.

Was wirklich zählt, ist, wie viele Wiederholungen jede Schleife macht.

In Ihrem Fall ist es einfach zu sehen, dass jede Iteration der innersten Schleife O (1) ist. Wie viele Iterationen gibt es? Wie oft müssen Sie eine Zahl verdoppeln, bis Sie n erreichen? Wenn x die Anzahl der Iterationen ist, würden wir die Schleife am ersten x beenden, so dass k = 2^x> n ist. Kannst du das für x lösen?

Jede Iteration der zweiten Schleife wird dies tun, so dass die Kosten der zweiten Schleife die Anzahl der Iterationen (die diesmal einfacher zu zählen sind) multipliziert mit den Kosten der inneren Schleife.

Und jede Iteration der ersten Schleife wird dies tun, so dass die Kosten der ersten Schleife die Anzahl der Iterationen (die auch einfach zu zählen ist) multipliziert mit den Kosten der zweiten Schleife.

Insgesamt ist die Laufzeit das Produkt von 3 Zahlen. Kannst du sie finden?

Quelle

2017-09-13 22:43:56 meriton

Großes O für 3 verschachtelte For-Loops?

Antwort

Verwandte Themen