Big O-Notation für Geschachtelte Schleife

Ich versuche Zeit zu finden, die Komplexität für diesen Code.

for (int i = 0; i <= n - 1; i++)
  for (int j = i + 1; j <= n - 1; j++)
    for (int k = j + 1; k <= n - 1; k++)

Mein Versuch:
Wir können schreiben Sie diese Schleife in der form:

for (int i = 1; i <= n; i++)
  for (int j = 1; j <= n; j++)
    for (int k = 1; k <= n; k++)

Nun Groß Oh von dieser Schleife ist O(n^5). Bin ich richtig oder mache ein paar Fehler???

  • Wo bekommt man die ‚5‘ aus? Auch, verwenden Sie korrekte Einrückung zu zeigen, dass Sie verschachtelt sind.
  • beide sind in O(n**3)
  • erste Schleife ausführen, n mal.. 2. Schleife läuft n^2 mal… 3. Schleife läuft n^3 mal, weil Sie alle Ineinander verschachtelt werden. Aber manchmal denke ich, dass seine Big-O-notation 1+2+3=6 d.h. O(n^6)
  • Sehen trincot die Lösung unten. Auch, denken Sie es so: Der inneren Schleife Ihrer zweiten Inkarnation für die Schleife benötigt O(n) Schritte, richtig? Sicher, es ist aufgerufen, viele Male, aber die innerste Schleife, wenn du dort bist, dauert nur n Schritte. Die Mitte-loop-dann ruft der inneren Schleife n-mal. Ich muss n-mal die erforderlichen Schritte, die von der inneren Schleife, die in O(n), so dass die zweite Schleife benötigt O(n^2). Endlich, die äußere Schleife ruft einen O(n^2) Vorgang n-mal, so ist die Summe O(n^3).
InformationsquelleAutor Knowledge 32 | 2016-10-30



4 Replies
  1. 4

    Die erste Variante des Codes mit einem Zähler Hinzugefügt:

    int count = 0
    for (int i = 0; i <= n - 1; i++)
        for (int j = i + 1; j <= n - 1; j++)
            for (int k = j + 1; k <= n - 1; k++)
                count++;
    

    Dieser zählt jede Kombination von (i, j, k) mit 0 <= i < j < k < n. Dies entspricht der Anzahl der Möglichkeiten, Sie können wählen 3 Elemente aus n Elemente, ohne Berücksichtigung der Reihenfolge der Ihnen zu berücksichtigen. Es ist eine Formel für diese Nummer:

            n(n-1)(n-2) /3! = n3/6 – n2/2 – n/2

    Die zweite Variante:

    int count = 0
    for (int i = 0; i <= n - 1; i++)
        for (int j = 0; j <= n - 1; j++)
            for (int k = 0; k <= n - 1; k++)
                count++;
    

    … zählt die Anzahl der Möglichkeiten, die Sie können wählen Sie 3 aus n Elemente, wobei die Reihenfolge wichtig ist, und Wiederholungen in den 3 Auswahlen erlaubt sind. Die Nummer ist ganz einfach zu leiten, wie i, j, k sind unabhängig und jeder kann Sie bekommen n unterschiedliche Werte, so dass die Gesamtzahl ist:

            n3

    Nun stellen Sie die gleiche Zeit, Komplexität:

            O(n3/6 – n2/2 – n/2) = O(n3)

    Dies ist aufgrund der Eigenschaften von big O:

    wenn eine Funktion kann begrenzt werden, indem ein Polynom in n, dann als n gegen unendlich gehen, kann man ignorieren lower-order terms des Polynoms.

    Und:

    Multiplikation mit einer Konstanten

    Lassen Sie k konstant sein. Dann:

    O(kg) = O(g) wenn k ungleich null ist.

    • Das war die Formel, die ich suchte. +1 aber ich m Angst, dass alles, was Sie bekommen, weil die OP ist davon überzeugt, dass O(n**5)
  2. 1

    Nun Groß Oh von dieser Schleife ist O(n^5). Bin ich richtig oder mache ein paar Fehler???

    Nein, das ist nicht korrekt. Die Komplexität ist O(n^3).

    In einfachen Worten, Sie können denken, es ab wie diese:

    Maximale Schritte in jede for-Schleife beginnend bei 0 und erreichen n-1 die Schritte 1 n. Also, wenn Sie zwei Schleifen, eine verschachtelte, in die andere dann für jeden Schritt, den Sie machen in der äußeren Schleife, die Sie machen n Schritte in der geschachtelten Schleife. Angesichts der Schritte, die Sie in der äußeren Schleife ist n, es ist ziemlich offensichtlich, dass am Ende machen Sie n^2 Schritte.

    Basierend auf den oben, können Sie leicht ziehen, dass in dem folgenden Fall:

    for(int i=0; i<=n-1; i++)
    {
        for(int j=0; j<=n-1; j++)
        {
            for(int k=0; k<=n-1; k++)
            {
    
            }
        }
    }
    

    machen Sie n^3 Schritte. So ist die Komplexität der Reihenfolge der O(n^3).

    • erste Schleife ausführen, n mal.. 2. Schleife läuft n^2 mal… 3. Schleife läuft n^3 mal, weil Sie alle Ineinander verschachtelt werden. Aber manchmal denke ich, dass seine Big-O-notation 1+2+3=6 d.h. O(n^6)
    • Lassen Sie uns darüber nachdenken, es basiert auf dem Beispiel, das ich oben vorgestellt. Wir isolieren die beiden inneren Schleifen. Wie oft würde diese laufen? Offenbar n^2. Wenn wir ein Stück code, dessen Komplexität ist n^2 innerhalb einer for-Anweisung, deren Komplexität ist O(n) dann ist die gesamte Komplexität wäre O(n^3). Warum? Wie wir bereits sahen, Sie würden n-Stufen, da in jedem Schritt, den Sie machen würde n^2 dann am Ende würden Sie machen n* n^2. So n^3 Schritte.
    • Also, wenn deine innere Schleife hat 10 Aussagen die Komplexität ist O(n^16) ? Kommen auf. Jeder sagt Ihnen, O(n^3) von Anfang an. @Knowledge32
  3. 1

    Sind diese Schleifen verschachtelt? Wenn ja, sind Sie auf dem richtigen Weg mit dem umschreiben der Schleife wie, die Dinge einfacher zu machen, zu Grunde geht. Obwohl, ich würde jede Schleife einen anderen iterator Namen als ich, um Verwirrung zu vermeiden:

    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            for (int c = 1; c <= n; c++) {
                ...
            }
        }
    }
    

    In der Tat können Sie benennen Sie diese Variablen, um was auch immer Sie möchten, die Dinge einfacher zu machen, zu Grunde geht. Wie wäre es mit:

    for (int street = 1; street <= n; street++) {
        for (int house = 1; house <= n; house++) {
            for (int room = 1; room <= n; room++) {
                ...
            }
        }
    }
    

    Nun wird das problem, wenn ich zu Besuch n Zimmer in n-Häuser in den n Städten, wie viele Zimmer muss ich besuchen?

    Hoffentlich können Sie sehen, dass die Antwort n * n * n , also n^3.

    Die Verknüpfung Weg, um die Antwort zu sehen, haben Sie 3 verschachtelte for-Schleifen von 1 bis n, also die Antwort ist n^3.

  4. 0

    wenn Sie haben Zweifel, und Sie wollen, überzeugen Sie sich einfach selbst führen einen kleinen test:

    #include <stdio.h>
    
    int main()
    {
    int count1=0,count2=0;
    int n=100;
    
    for (int i = 0; i <= n - 1; i++)
    
    for (int j = i + 1; j <= n - 1; j++)
    
    for (int k = j + 1; k <= n - 1; k++)
      count1++;
    
    for (int i = 1; i <= n; i++)
    
    for (int j = 1; j <= n; j++)
    
    for (int k = 1; k <= n; k++)
      count2++;
    
    printf("count1 %d count2 %d n %d\n",count1,count2,n);
    return 0;
    }
    

    Ergebnis:

    count1 161700 count2 1000000 n 100
    
    • klar, der 2. Schleife läuft 100**3 mal => O(n**3)

    • erste Schleife läuft weniger, weil die Grenzen, aber es ist immer noch linear (keine dividieren Operationen auf die Grenzen) => O(n**3), auch wenn es schneller ist.

    • erste Schleife ausführen, n mal.. 2. Schleife läuft n^2 mal… 3. Schleife läuft n^3 mal, weil Sie alle Ineinander verschachtelt werden. Aber manchmal denke ich, dass seine Big-O-notation 1+2+3=6 d.h. O(n^6)
    • das ist deine eigene definition von Komplexität, obwohl.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.