Big-O für verschachtelte Schleife

8

Ich lese diesen Beitrag auf Big-O.
Es heißt, dass der folgende Code O (n ^ 2) ist: 

bool ContainsDuplicates(String[] strings)
{
    for(int i = 0; i < strings.Length; i++)
    {
        for(int j = 0; j < strings.Length; j++)
        {
            if(i == j) // Don't compare with self
            {
                continue;
            }

            if(strings[i] == strings[j])
            {
                return true;
            }
        }
    }
    return false;
}

Aber ich kann nicht verstehen warum.
Die innere Schleife macht etwas Konstantes.
Es ist also die Summe von 1 .... N einer Konstanten. dh konstante Zahl O (1).
Die äußere Schleife ist eine Summation über dem O (1).
Ich würde mir also vorstellen, dass es n * O (1) ist.

Ich glaube, ich verstehe hier etwas falsch.
Ich glaube nicht, dass alle verschachtelten Schleifen O (n ^ 2) bedeuten, oder?

algorithms performance complexity big-o user10326
quelle
3
Woher kommt die Idee, dass die innere Schleife "etwas Konstantes tut"? Es ist eine Schleife. Das ist dein erster Hinweis darauf, dass es O (N) braucht.
Paul Tomblin
2
Dies kann auf O (N ^ 2/2) reduziert werden, indem die innere Schleife bei i+1statt beginnt 0. Wie geschrieben, sind im schlimmsten Fall (keine Dupes) 1/2 die Vergleiche redundant.
Peter Rowell
1
O (N ^ 2/2) = O (N ^ 2) (In beiden Fällen bedeutet eine Verdoppelung von N, wenn N gegen unendlich geht, eine Vervierfachung der Laufzeit. Das ist alles, was O (N ^ 2) bedeutet.)
David Schwartz
5
Bemerkenswert ist, dass in einer Sprache wie C, in der ein Zeichenfolgenvergleich stattfindet O(N), dieser Code tatsächlich O(N^2 * M)dort ist , wo M die Länge der Zeichenfolgen ist.
Isak Savo
2
Der Vergleich (der Zeichenfolge konstanter Länge) ist O (1). N Vergleiche sind O (N). N ^ 2 Vergleiche sind O (N ^ 2).
SF.

Antworten:

18

Ihr Fehler liegt in der inneren Schleife. Es macht n- mal etwas Konstantes , also ist es O ( n ). Die äußere Schleife führt die innere Schleife n- mal durch, also ist es O ( n × n ) oder O ( n 2  ).

Wenn die Anzahl der Iterationen, die eine Schleife durchführt, von der Größe der Eingabe abhängt, ist sie im Allgemeinen O ( n ). Und wenn k solche Schleifen verschachtelt sind, ist es O ( n k  ).

KeithB
quelle
1
Vielleicht wäre eine leichter verständliche Notation zu sagen, dass der Algorithmus in O (i * j) läuft. Hier iterieren beide Schleifen über die Länge f String, also i = j = n, wobei n string.length ist
Newtopian
1
@Newtopian: Normalerweise nehmen Sie an, dass die Zeichenfolgen ungefähr konstant lang sind. Das ist in der Praxis eigentlich eine ziemlich gute Annäherung.
Donal Fellows
@Donal können wir zwar mit dem richtigen Datensatzwissen solche Annahmen treffen, aber wie immer gibt es Ausnahmen, bei denen die DNA-Analyse in den Sinn kommt, bei der die Stringlänge für ein Codon einige Zeichen bis zu mehreren Megabyte für ein vollständiges Chromosom betragen kann. Das heißt, in diesem Fall ist insbesondere die Zeichenfolgenlänge ohne Bedeutung, da wir die Zeichenfolgen selbst und nicht die Zeichen iterieren. Das heißt, es sei denn, der Gleichheitsoperator wurde abhängig von der Länge der Operanden mit einer funky Logik überladen. Ich bezweifle jedoch, dass das OP in seiner Analyse so weit gehen wollte.
Newtopian
@Newtopian: Um fair zu sein, wird die ContainsDuplicatesFunktion / Methode aus der Frage wahrscheinlich nicht mit vollen Chromosomen verwendet.
Donal Fellows
@Donal: wahrscheinlich nicht nein :-)
Newtopian
4

Wenn die Länge der Zeichenfolge gleich ist n, wird der Test if i == jn ^ 2 Mal ausgeführt. Die Reihenfolge eines Algorithmus ist die Reihenfolge des Teils, der die höchste Ordnung hat. Da 'i' zweimal mit 'j' n ^ 2 verglichen wird, kann die Reihenfolge des Algorithmus unmöglich kleiner sein als O(n^2).

Bei einem sehr großen 'n' vervierfacht das Verdoppeln von 'n' die Laufzeit.

David Schwartz
quelle
Aber ist der Test nicht i==jein O (1)?
user10326
5
Der Test selbst ist O (1). Die innere Schleife führt den Test 'n' mal aus, also ist es O (n * 1). Die äußere Schleife führt die innere Schleife 'n' mal aus, also ist es O (n * n * 1). Der Code ist also insgesamt O (n ^ 2). Wenn Sie einen O (1) -Schritt n ^ 2 Mal ausführen, ist das O (n ^ 2).
David Schwartz
1
Minor nit: Tatsächlich wird die Laufzeit für jeden Wert von N verdoppelt - es ist nur so, dass es für kleine N nicht so wichtig ist.
Peter Rowell
@ Peter: Das stimmt nicht. Wenn Sie beispielsweise von n = 2 auf n = 4 wechseln, wird die Laufzeit möglicherweise nicht verdoppelt, da eine 32-Bit-Maschine möglicherweise dieselbe Anzahl von Speicherabrufen verwendet, um 2 Bytes wie 4 zu lesen. In ähnlicher Weise ist für kleine n der Aufwand für die Eingabe der Funktion kann signifikant sein, und das ist konstant. Ein größeres n kann im Durchschnitt eine bessere Verzweigungsvorhersage haben. Und so weiter.
David Schwartz
5
In diesem Zusammenhang bedeutet "sehr groß 'n'", da 'n' gegen unendlich tendiert, jedoch alle Ineffizienzen ignoriert werden, die aufgrund großer 'n' auftreten können (z. B. nicht in eine 32-Bit- oder 64-Bit-Ganzzahl passen). Der Punkt der Big-O-Notation besteht darin, zu analysieren, wie sich die Leistung eines Algorithmus mit zunehmendem 'n' ändert, solange er innerhalb der Fähigkeiten der Maschine bleibt. (Dies mag in diesem Zusammenhang ein Streitpunkt sein, aber im Allgemeinen ist es wichtig zu verstehen, was Big-O-Notation beinhaltet und ignoriert, um zu verstehen, was es bedeutet.)
David Schwartz
2

Sie interpretieren falsch, was eine konstante Operation bedeutet.

Eine konstante Operation ist eine Operation, die unabhängig von der empfangenen Eingabe immer in fester Zeit ausgeführt wird.

i == j ist eine konstante Operation, da diese Anweisung in fester Zeit ausgeführt wird. Nehmen wir an, es dauert 1 Zeiteinheit.

Diese konstante Operation wird jedoch mal ausgeführt (Anzahl der Werte von i) * (Anzahl der Werte von j). Nehmen wir an, i und j werden jeweils zehnmal ausgeführt. Dann dauert es nach Berechnung 100 Zeiteinheiten, bis i == j in einer verschachtelten Schleife abgeschlossen ist. Es wird also variieren, wenn die Werte von i und j variieren.

Wir können sicher sein, dass i == j in 1 Zeiteinheit ausgeführt wird, aber wir können nicht wissen, wie oft i == j ausgeführt wird.

Wenn es n-mal ausgeführt wird, dauert es n Zeiteinheiten. Die äußere Schleife führt die innere Schleife n-mal aus. Im Wesentlichen werden i == j-Operationen n ^ 2 Mal ausgeführt.

Alle verschachtelten Schleifen bedeuten O (n ^ (Anzahl der verschachtelten Schleifen)). Hier bedeutet O die Obergrenze, was bedeutet, dass Code kleiner oder gleich dem Wert von O () ausgeführt wird. Dies ist die Garantie, dass es nicht länger dauert, aber es kann weniger Zeit dauern, nicht größer.

Codecool
quelle
0

Verschachtelte Schleifen führen O ( i 1 * i 2 * ... * i n ) aus, wobei n die Anzahl der verschachtelten Schleifen und i x die Anzahl der Iterationen in der Schleife x ist . (Oder anders ausgedrückt, es ist das Produkt der Anzahl der Iterationen in jeder der Schleifen.)

Ihr Schleifenpaar iteriert zweimal über dasselbe Array, was zufällig O (n * n) oder O (n 2 ) ist.

Was in der innersten Schleife passiert, wird als konstant behandelt, da es jedes Mal passieren wird. Bei der Big-O-Notation geht es nicht wirklich darum, die Leistung von linearem Code zu messen, sondern vielmehr darum, relative Vergleiche des Verhaltens iterativer Algorithmen anzustellen, wenn n Eingabeelemente zur Behandlung gegeben werden. Bestimmte Operationen, die keine Iteration ausführen (z. B. Push oder Pop auf einem Stapel), werden als O (1) bezeichnet, da sie ein Element der Daten verarbeiten.

Blrfl
quelle
1
Nicht wahr, wenn i_k nicht konstant ist: Denken Sie an Sweepline-Algen Problem. Auch Quicksort ohne Rekursion implementiert ist eine verschachtelte Schleife, aber es ist immer noch O (n * log n)
Ratschenfreak
Quicksort mit zufälliger Pivot-Auswahl ist nicht deterministisch, was bedeutet, dass die O (n log n) -Zahl ein Durchschnitt ist. Es passt immer noch zu dem, was ich gesagt habe: i1 = n und i2 = log n .
Blrfl