Warum ist der schlechteste Fall für diese Funktion O (n ^ 2)?

44

Ich versuche mir selbst beizubringen, wie man die BigO-Notation für eine beliebige Funktion berechnet. Ich habe diese Funktion in einem Lehrbuch gefunden. Das Buch behauptet, dass die Funktion O (n 2 ) ist. Es gibt eine Erklärung, warum dies so ist, aber ich habe Mühe, dem zu folgen. Ich frage mich, ob jemand in der Lage sein könnte, mir die Mathematik dahinter zu zeigen, warum das so ist. Grundsätzlich verstehe ich, dass es etwas weniger als O (n 3 ) ist, aber ich konnte nicht unabhängig auf O (n 2 ) landen

Angenommen, wir erhalten drei Folgen von Zahlen, A, B und C. Wir gehen davon aus, dass keine einzelne Folge doppelte Werte enthält, sondern dass einige Zahlen in zwei oder drei Folgen vorkommen können. Das Dreiwegesatz-Disjunktitätsproblem besteht darin, zu bestimmen, ob der Schnittpunkt der drei Sequenzen leer ist, nämlich dass es kein Element x gibt, so dass x ≤ A, x ≤ B und x ≤ C.

Übrigens, das ist für mich kein Problem mit den Hausaufgaben - das Schiff ist vor Jahren gesegelt:), nur ich versuche schlauer zu werden.

def disjoint(A, B, C):
        """Return True if there is no element common to all three lists."""  
        for a in A:
            for b in B:
                if a == b: # only check C if we found match from A and B
                   for c in C:
                       if a == c # (and thus a == b == c)
                           return False # we found a common value
        return True # if we reach this, sets are disjoint

[Bearbeiten] Nach dem Lehrbuch:

In der verbesserten Version sparen wir nicht nur Zeit, wenn wir Glück haben. Wir behaupten, dass die schlechteste Laufzeit für Disjunkte O (n 2 ) ist.

Die Erklärung des Buches, der ich nur schwer folgen kann, lautet:

Um die Gesamtlaufzeit zu berücksichtigen, untersuchen wir die Zeit, die für die Ausführung jeder Codezeile aufgewendet wurde. Die Verwaltung der for-Schleife über A erfordert O (n) Zeit. Die Verwaltung der for-Schleife über B macht insgesamt 0 (n 2 ) Zeit aus, da diese Schleife zu n verschiedenen Zeiten ausgeführt wird. Der Test a == b wird O (n 2 ) mal ausgewertet . Der Rest der aufgewendeten Zeit hängt davon ab, wie viele übereinstimmende (a, b) Paare existieren. Wie wir bemerkt haben, gibt es höchstens n solche Paare, und so verwenden die Verwaltung der Schleife über C und die Befehle innerhalb des Körpers dieser Schleife höchstens die Zeit O (n 2 ). Die Gesamtzeit beträgt O (n 2 ).

(Und um das richtig anzuerkennen ...) Das Buch ist: Datenstrukturen und Algorithmen in Python von Michael T. Goodrich et. alle, Wiley Publishing, pg. 135

[Bearbeiten] Eine Begründung; Unten ist der Code vor der Optimierung:

def disjoint1(A, B, C):
    """Return True if there is no element common to all three lists."""
       for a in A:
           for b in B:
               for c in C:
                   if a == b == c:
                        return False # we found a common value
return True # if we reach this, sets are disjoint

Oben sehen Sie deutlich, dass dies O (n 3 ) ist, da jede Schleife in vollem Umfang ausgeführt werden muss. Das Buch würde behaupten, dass in dem vereinfachten Beispiel (als erstes gegeben) die dritte Schleife nur eine Komplexität von O (n 2 ) ist, daher lautet die Komplexitätsgleichung k + O (n 2 ) + O (n 2 ), was letztendlich ergibt O (n 2 ).

Ich kann zwar nicht beweisen, dass dies der Fall ist (daher die Frage), aber der Leser kann zustimmen, dass die Komplexität des vereinfachten Algorithmus mindestens geringer ist als die des Originals.

[Bearbeiten] Und um zu beweisen, dass die vereinfachte Version quadratisch ist:

if __name__ == '__main__':
    for c in [100, 200, 300, 400, 500]:
        l1, l2, l3 = get_random(c), get_random(c), get_random(c)
        start = time.time()
        disjoint1(l1, l2, l3)
        print(time.time() - start)
        start = time.time()
        disjoint2(l1, l2, l3)
        print(time.time() - start)

Erträge:

0.02684807777404785
0.00019478797912597656
0.19134306907653809
0.0007600784301757812
0.6405444145202637
0.0018095970153808594
1.4873297214508057
0.003167390823364258
2.953308343887329
0.004908084869384766

Da die zweite Differenz gleich ist, ist die vereinfachte Funktion in der Tat quadratisch:

Bildbeschreibung hier eingeben

[Bearbeiten] Und noch ein Beweis:

Wenn ich den schlechtesten Fall annehme (A = B! = C),

if __name__ == '__main__':
    for c in [10, 20, 30, 40, 50]:
        l1, l2, l3 = range(0, c), range(0,c), range(5*c, 6*c)
        its1 = disjoint1(l1, l2, l3)
        its2 = disjoint2(l1, l2, l3)
        print(f"iterations1 = {its1}")
        print(f"iterations2 = {its2}")
        disjoint2(l1, l2, l3)

ergibt:

iterations1 = 1000
iterations2 = 100
iterations1 = 8000
iterations2 = 400
iterations1 = 27000
iterations2 = 900
iterations1 = 64000
iterations2 = 1600
iterations1 = 125000
iterations2 = 2500

Beim zweiten Differenztest ist das Worst-Case-Ergebnis genau quadratisch.

Bildbeschreibung hier eingeben

SteveJ
quelle
6
Entweder ist das Buch falsch oder Ihre Transkription ist.
candied_orange
6
Nee. Falsch ist falsch, egal wie gut zitiert. Erklären Sie entweder, warum wir nicht einfach davon ausgehen können, dass dies der schlechteste Weg ist, wenn Sie eine Big-O-Analyse durchführen, oder akzeptieren Sie die Ergebnisse, die Sie erhalten.
candied_orange
8
@candied_orange; Ich habe nach besten Kräften eine weitere Rechtfertigung hinzugefügt - nicht meine Stärke. Ich würde Sie bitten, noch einmal die Möglichkeit in Betracht zu ziehen, dass Sie tatsächlich falsch liegen. Sie haben Ihren Standpunkt richtig dargelegt.
SteveJ
8
Zufallszahlen sind nicht Ihr schlimmster Fall. Das beweist nichts.
Telastyn
7
ahh. in Ordnung. Die "Keine Sequenz hat doppelte Werte" ändert den schlimmsten Fall, da C nur einmal pro A auslösen kann. Entschuldigung für die Frustration - das bekomme ich, wenn ich am späten Samstag auf dem Stack-Exchange bin: D
Telastyn

Antworten:

63

Das Buch ist in der Tat richtig und liefert ein gutes Argument. Beachten Sie, dass Timings kein zuverlässiger Indikator für die algorithmische Komplexität sind. Bei den Timings wird möglicherweise nur eine bestimmte Datenverteilung berücksichtigt, oder die Testfälle sind möglicherweise zu klein: Die algorithmische Komplexität beschreibt nur, wie die Ressourcennutzung oder die Laufzeit über eine ausreichend große Eingabegröße hinaus skaliert.

Das Buch argumentiert, dass Komplexität O (n²) ist, da der if a == bZweig höchstens n- mal eingegeben wird . Dies ist nicht offensichtlich, da die Schleifen immer noch als verschachtelt geschrieben sind. Es ist offensichtlicher, wenn wir es extrahieren:

def disjoint(A, B, C):
  AB = (a
        for a in A
        for b in B
        if a == b)
  ABC = (a
         for a in AB
         for c in C
         if a == c)
  for a in ABC:
    return False
  return True

Diese Variante verwendet Generatoren zur Darstellung von Zwischenergebnissen.

  • Im Generator ABhaben wir höchstens n Elemente (wegen der Garantie, dass Eingabelisten keine Duplikate enthalten), und die Erzeugung des Generators erfordert O (n²) Komplexität.
  • Die Erzeugung des Generators ABCbeinhaltet eine Schleife über den Generator ABder Länge n und Cder Länge n , so dass dessen algorithmische Komplexität ebenfalls 0 (n²) beträgt.
  • Diese Operationen sind nicht verschachtelt, sondern finden unabhängig voneinander statt, sodass die Gesamtkomplexität O (n² + n²) = O (n²) ist.

Da Paare von Eingabelisten nacheinander überprüft werden können, kann in O (n²) ermittelt werden, ob eine beliebige Anzahl von Listen nicht zusammenhängend ist.

Diese Analyse ist ungenau, da davon ausgegangen wird, dass alle Listen dieselbe Länge haben. Wir können genauer sagen, dass ABdas höchstens die Länge min (| A |, | B |) hat und dass das Produzieren davon die Komplexität O (| A | • | B |) hat. Das Produzieren ABChat die Komplexität O (min (| A |, | B |) • | C |). Die Gesamtkomplexität hängt dann von der Reihenfolge der Eingabelisten ab. Mit | A | ≤ | B | ≤ | C | Wir erhalten die gesamte Worst-Case-Komplexität von O (| A | • | C |).

Beachten Sie, dass Effizienzgewinne möglich sind, wenn die Eingabecontainer schnelle Mitgliedschaftstests ermöglichen, anstatt über alle Elemente iterieren zu müssen. Dies kann der Fall sein, wenn sie so sortiert sind, dass eine binäre Suche durchgeführt werden kann, oder wenn es sich um Hash-Mengen handelt. Ohne explizite verschachtelte Schleifen würde dies so aussehen:

for a in A:
  if a in B:  # might implicitly loop
    if a in C:  # might implicitly loop
      return False
return True

oder in der generatorbasierten Version:

AB = (a for a in A if a in B)
ABC = (a for a in AB if a in C)
for a in ABC:
  return False
return True
amon
quelle
4
Dies wäre viel klarer, wenn wir diese magische nVariable einfach abschaffen und über die tatsächlichen Variablen sprechen würden.
Alexander
15
@code_dredd Nein, es gibt keine direkte Verbindung zum Code. Es ist eine Abstraktion, die sich das vorstellt len(a) == len(b) == len(c), was, obwohl es im Kontext der Zeitkomplexitätsanalyse wahr ist, dazu neigt, das Gespräch zu verwirren.
Alexander
10
Vielleicht reicht die Aussage, dass der OP-Code die Worst-Case-Komplexität O (| A | • | B | + min (| A |, | B |) • | C |) hat, um Verständnis auszulösen?
Pablo H
3
Eine andere Sache über Timing-Tests: Wie Sie herausfanden, haben sie Ihnen nicht geholfen, zu verstehen, was vor sich ging. Auf der anderen Seite haben sie Ihnen offenbar zusätzliches Vertrauen in die Behauptung gegeben, dass das Buch offensichtlich falsch war. Das ist also eine gute Sache, und in diesem Fall haben Ihre Tests das intuitive Winken von Hand geschlagen. Zum besseren Verständnis wäre es eine effektivere Methode, das Programm in einem Debugger mit Haltepunkten (oder Ausdrucken der Variablenwerte) am Eingang jeder Schleife auszuführen.
Sdenham
4
"Beachten Sie, dass Timings kein nützlicher Indikator für die algorithmische Komplexität sind." Ich denke, dies wäre genauer, wenn "rigoros" oder "zuverlässig" statt "nützlich" gesagt würde.
Akkumulation
7

Beachten Sie, dass Sie C nur einmal für jedes Element in A wiederholen können, wenn alle Elemente in jeder der angenommenen Listen unterschiedlich sind (wenn es in B ein Element gibt, das gleich ist). Die innere Schleife ist also O (n ^ 2) total

RiaD
quelle
3

Wir gehen davon aus, dass keine einzelne Sequenz Duplikate enthält.

ist eine sehr wichtige Information.

Andernfalls wäre der schlechteste Fall der optimierten Version immer noch O (n³), wenn A und B gleich sind und ein Element enthalten, das n-mal dupliziert wurde:

i = 0
def disjoint(A, B, C):
    global i
    for a in A:
        for b in B:
            if a == b:
                for c in C:
                    i+=1
                    print(i)
                    if a == c:
                        return False 
    return True 

print(disjoint([1] * 10, [1] * 10, [2] * 10))

welche Ausgänge:

...
...
...
993
994
995
996
997
998
999
1000
True

Die Autoren gehen also grundsätzlich davon aus, dass der O (n³) Worst-Case nicht auftreten sollte (warum?), Und "beweisen", dass der Worst-Case jetzt O (n²) ist.

Die eigentliche Optimierung wäre die Verwendung von Mengen oder Dikten, um die Einbeziehung in O (1) zu testen. In diesem Fall disjointwäre O (n) für jede Eingabe.

Eric Duminil
quelle
Ihr letzter Kommentar ist ziemlich interessant, daran habe ich nicht gedacht. Schlagen Sie vor, dass dies darauf zurückzuführen ist, dass Sie drei O (n) -Operationen hintereinander ausführen können?
SteveJ
2
Wenn Sie keinen perfekten Hash mit mindestens einem Bucket pro Eingabeelement erhalten, können Sie die Aufnahme in O (1) nicht testen. Eine sortierte Menge hat normalerweise die Suche nach O (log n). Es sei denn, Sie sprechen über Durchschnittskosten, aber darum geht es nicht. Trotzdem ist es trivial, eine ausgeglichene Binärmenge zu haben, die hart wird O (n log n).
Jan Dorniak,
@ JanDorniak: Hervorragender Kommentar, danke. Jetzt ist es etwas umständlich: Ich habe den Worst-Case ignoriert key in dict, genau wie die Autoren. : - / Zu meiner Verteidigung finde ich es viel schwieriger, ein Diktat mit nSchlüsseln und nHash-Kollisionen zu finden, als nur eine Liste mit ndoppelten Werten zu erstellen . Und mit einer Menge oder einem Diktat kann es auch wirklich keinen doppelten Wert geben. Der Worst-Worst-Case ist also in der Tat O (n²). Ich werde meine Antwort aktualisieren.
Eric Duminil
2
@ JanDorniak Ich denke, Sets und Dicts sind Hash-Tabellen in Python im Gegensatz zu den rot-schwarzen Bäumen in C ++. Der absolut schlechteste Fall ist also schlechter, bis zu 0 (n) für eine Suche, aber der Durchschnittsfall ist O (1). Im Gegensatz zu O (log n) für C ++ wiki.python.org/moin/TimeComplexity . Angesichts der Tatsache, dass es sich um eine Python-Frage handelt und die Domäne des Problems mit hoher Wahrscheinlichkeit zu einer durchschnittlichen Fallleistung führt, halte ich die Behauptung von O (1) nicht für schlecht.
Baldrickk
3
Ich denke, ich sehe das Problem hier: Wenn die Autoren sagen "Wir gehen davon aus, dass keine einzelne Sequenz doppelte Werte enthält", ist dies kein Schritt bei der Beantwortung der Frage. es ist vielmehr eine Voraussetzung, unter der die Frage behandelt werden soll. Aus pädagogischen Gründen verwandelt sich ein uninteressantes Problem in ein Problem, das die Intuition der Menschen in Bezug auf Big-O in Frage stellt - und dies scheint erfolgreich gewesen zu sein, gemessen an der Anzahl der Menschen, die nachdrücklich darauf bestanden haben, dass O (n²) falsch sein muss. Auch während es hier umstritten ist, ist das Zählen der Anzahl von Schritten in einem Beispiel keine Erklärung.
Sdenham
3

So fügen Sie Begriffe in die Begriffe ein, die in Ihrem Buch verwendet werden:

Ich denke, Sie haben kein Problem damit, zu verstehen, dass der Check für den a == bungünstigsten Fall O (n 2 ) ist.

Jetzt im schlimmsten Fall für die dritte Schleife, jede ain Ahat ein Spiel in B, so wird die dritte Schleife jedes Mal aufgerufen werden. Für den Fall, dass in anicht vorhanden ist C, wird es durch den gesamten CSatz ausgeführt.

Mit anderen Worten, es ist 1 Mal für jeden aund 1 Mal für jeden coder n * n. O (n 2 )

Es gibt also das O (n 2 ) + O (n 2 ), auf das Ihr Buch hinweist.

Mars
quelle
0

Der Trick der optimierten Methode ist das Schneiden von Ecken. Nur wenn a und b übereinstimmen, ist c einen Blick wert. Nun können Sie sich vorstellen, dass Sie im schlimmsten Fall noch jedes c auswerten müssten. Das ist nicht wahr.

Sie denken wahrscheinlich, dass der schlimmste Fall darin besteht, dass jede Prüfung auf a == b zu einem Durchlauf über C führt, da jede Prüfung auf a == b eine Übereinstimmung zurückgibt. Dies ist jedoch nicht möglich, da die Bedingungen dafür widersprüchlich sind. Damit dies funktioniert, benötigen Sie ein A und ein B, die dieselben Werte enthalten. Sie können unterschiedlich angeordnet sein, aber jeder Wert in A müsste einen übereinstimmenden Wert in B haben.

Hier ist der Kicker. Es gibt keine Möglichkeit, diese Werte so zu organisieren, dass Sie für jedes a alle b auswerten müssen, bevor Sie Ihre Übereinstimmung finden.

A: 1 2 3 4 5
B: 1 2 3 4 5

Dies würde sofort geschehen, da die passenden Einsen das erste Element in beiden Reihen sind. Wie wäre es mit

A: 1 2 3 4 5
B: 5 4 3 2 1

Das würde beim ersten Lauf über A funktionieren: Nur das letzte Element in B würde einen Treffer ergeben. Die nächste Iteration über A müsste aber schon schneller sein, da der letzte Platz in B bereits mit 1 belegt ist. Und dies würde diesmal in der Tat nur vier Iterationen dauern. Und das wird mit jeder nächsten Iteration ein bisschen besser.

Jetzt bin ich kein Mathematiker und kann nicht beweisen, dass dies in O (n2) enden wird, aber ich kann es auf meinen Clogs fühlen.

Martin Maat
quelle
1
Die Reihenfolge der Elemente spielt hier keine Rolle. Die wesentliche Anforderung ist, dass keine Duplikate vorhanden sind. das Argument ist dann, dass die Schleifen in zwei getrennte O(n^2)Schleifen umgewandelt werden können; das gibt insgesamt O(n^2)(Konstanten werden ignoriert).
9.
@AnoE In der Tat spielt die Reihenfolge der Elemente keine Rolle. Welches ist genau das, was ich demonstriere.
Martin Maat
Ich sehe, was Sie versuchen, und was Sie schreiben, ist nicht falsch, aber aus der Sicht von OP zeigt Ihre Antwort hauptsächlich, warum ein bestimmter Gedankengang irrelevant ist; Es wird nicht erklärt, wie man zu der tatsächlichen Lösung kommt. OP scheint keinen Hinweis darauf zu geben, dass er tatsächlich denkt, dass dies mit der Ordnung zusammenhängt. Daher ist mir unklar, wie diese Antwort dem OP helfen würde.
9.
-1

War zuerst ratlos, aber Amons Antwort ist wirklich hilfreich. Ich möchte sehen, ob ich eine wirklich prägnante Version machen kann:

Für einen bestimmten Wert von ain Awird die Funktion amit jedem möglichen bin verglichen Bund nur einmal ausgeführt. Also für eine gegebene aes führt a == bgenau nmal.

Benthält keine Duplikate (keine der Listen zu tun), so dass für ein gegebenes aes wird höchstens ein Spiel. (Das ist der Schlüssel). Wo es eine Übereinstimmung gibt, awird mit jedem möglichen verglichen c, was bedeutet, dass a == cgenau n-mal ausgeführt wird. Wo es keine Übereinstimmung a == cgibt, passiert überhaupt nicht.

Für eine bestimmte Situation agibt es also entweder nVergleiche oder 2nVergleiche. Dies passiert für jeden a, der bestmögliche Fall ist also (n²) und der schlechteste ist (2n²).

TLDR: Jeder Wert von awird mit jedem Wert von bund mit jedem Wert von verglichen c, jedoch nicht mit jeder Kombination von bund c. Die beiden Probleme addieren sich, aber sie multiplizieren sich nicht.

Douglas Winship
quelle
-3

Stellen Sie sich dies so vor, dass einige Zahlen in zwei oder drei der Sequenzen vorkommen können. Der Durchschnittsfall ist jedoch, dass für jedes Element in Satz A eine umfassende Suche in b durchgeführt wird. Es ist garantiert, dass jedes Element in Satz A durchlaufen wird, impliziert jedoch, dass weniger als die Hälfte der Elemente in Satz b durchlaufen wird.

Wenn die Elemente in Satz b durchlaufen werden, erfolgt eine Iteration, wenn eine Übereinstimmung vorliegt. Dies bedeutet, dass der Durchschnittsfall für diese disjunkte Funktion O (n2) ist, der absolut schlechteste Fall dafür jedoch O (n3) sein könnte. Wenn das Buch nicht ins Detail gehen würde, gäbe es wahrscheinlich einen Durchschnittsfall als Antwort.

Eddie Ekpo
quelle
4
Dem Buch ist klar, dass O (n2) der schlechteste und nicht der durchschnittliche Fall ist.
SteveJ
Eine Beschreibung einer Funktion in Form einer großen O-Notation liefert normalerweise nur eine Obergrenze für die Wachstumsrate der Funktion. Mit der großen O-Notation sind mehrere verwandte Notationen verbunden, die die Symbole o, Ω, ω und Θ verwenden, um andere Arten von Grenzen für asymptotische Wachstumsraten zu beschreiben. Wikipedia - Big O
candied_orange
5
"Wenn das Buch nicht ins Detail gehen würde, gäbe es wahrscheinlich einen Durchschnittsfall als Antwort." - Ähm, nein. Ohne explizite Einschränkung sprechen wir normalerweise von der Worst-Case-Step-Komplexität im RAM-Modell. Wenn von Operationen an Datenstrukturen die Rede ist und dies aus dem Kontext hervorgeht, handelt es sich möglicherweise um die amortisierte Worst-Case-Schrittkomplexität im RAM-Modell. Ohne ausdrückliche Einschränkung werden wir im Allgemeinen nicht über den besten Fall, den durchschnittlichen Fall, den erwarteten Fall, die zeitliche Komplexität oder ein anderes Modell mit Ausnahme von RAM sprechen.
Jörg W Mittag