Tutorial zur Raumkomplexität von Algorithmen [Duplikat

Question

Mögliches Duplikat:
Einfache englische Erklärung von Big o

Ich hatte immer Mühe, die Big-O-Zeit und die Raumkomplexität der Algorithmen, die ich schreibe, zu berechnen.

Kann jemand bitte auf eine gute Ressource verweisen, um mehr über die Raumkomplexität von Algorithmen zu lernen?

BEARBEITEN: Ich hatte nach dem Posten hier nach Tutorials gesucht. Leider konzentrieren sich alle Tutorials auf die Komplexität der Laufzeit und schreiben kaum mehr als ein paar Zeilen über die Raumkomplexität.

Answer 1

Abhängig davon, wo Sie hineinspringen möchten, Dies Kann ein guter Zehen-Tipper sein. Das Wiki Page ist auch hochwertig und geht etwas ausführlicher. Dies ist ein guter Student oder Intro-Graduiertentext der oberen Ebene und wird in die gehen linearer Geschwindigkeitssatz, Ein großer Grund, warum Informatiker bei der Diskussion über Algorithmus-Laufzeiten überhaupt eine Big-O-Notation verwenden. Kurz gesagt, Sie können immer einen linearen Faktor in der Geschwindigkeitsverbesserung erhalten, indem Sie eine exponentielle Menge Geld auf Hardware werfen.

Die Gnade der Big-O-Notation ist, dass wir den "losen Wandel" von den Enden unserer Kostenformeln wegwerfen können. Dies ist durch die implizite Annahme gerechtfertigt, dass wir uns nur um den begrenzenden Fall kümmern, in dem die Größe unserer Input in Unendlichkeit geht und die größten Bedingungen unserer Kosten die anderen dominieren.

Wenn Sie eine Komplexitätsanalyse durchführen, müssen Sie zuerst eine Maßnahme für Ihre Eingabe auswählen, dann entscheiden, welche Ressource, deren Verbrauch Sie messen möchten, und dann die vom Algorithmus genommene Menge bei der Eingabe einer bestimmten Größe zu zählen. Durch Konvention wird die Eingangsgröße benannt N. Typische Ressourcen sind die Anzahl der ausgeführten "Schritte" oder Elemente, die in allen Containern gespeichert sind. Dies sind jedoch nur (beliebte) Beispiele. Im Gegensatz dazu konzentrieren sich vergleichsbasierte Sortieralgorithmen häufig ausschließlich auf die Anzahl der hergestellten Swaps.

Die Größe des Eingangs ist im Allgemeinen nicht die einzig bestimmende Tatsache, wie lange der Algorithmus zum Laufen benötigt oder wie viel Platz er benötigt. Beispielsweise unterscheidet sich die Laufzeit von Insertion-Sortieren zwischen Eingaben gleicher Länge, die in bereits sortierter und umgekehrter Reihenfolge präsentiert sind, dramatisch. Deshalb reden wir darüber Schlimmsten Fall vs. Durchschnittsfall Komplexität (oder Best-Case usw.), indem wir z. "Was ist das schlechteste, was passieren könnte?"

Die durchschnittlichen Case-Komplexitäten sind schwierig, da sie Kenntnis der Kenntnisse erfordern Verteilung möglicher Eingaben. Die schlimmsten Fallkomplexitäten sind unabhängig von Eingabeverteilungen und bieten uns harte Obergrenzen, was in der Praxis oft alles ist, was wir brauchen.

Zum Beispiel, wenn ein Algorithmus wie z. Blasenart Nimmt ein Array von Elementen als Eingang an, ein typisches Maß ist die Länge des Arrays. Angenommen, wir möchten die Anzahl der Swaps zählen, die es im schlimmsten Fall macht. Hier ist Pseudo -Code dafür, entnommen aus Wikipedia:

procedure bubbleSort( A : list of sortable items )
  repeat
    swapped = false
    for i = 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  until not swapped
end procedure

Beachten Sie, dass es im Wesentlichen zwei sind for Loops, ein inneres, der ineinander verschachtelt ist. Die innere Schleife zählt von 1 zu length(A) - 1, und macht das Maximum N - 1 Swaps genau dann, wenn sich das größte Element des Arrays vorne befindet. Die äußere Schleife wiederholt diesen Vorgang, solange jeder Austausch der letzte Pass aufgetreten ist. Unter der Annahme eines früheren Durchgangs der schlimmsten Fall wird am Ende der Liste das bisher größte, ungewöhnliche Element vorhanden sein, was den Abstand effektiv schrumpft, können wir das nächstgrößte, ungewöhnliche Element um eins bewegen. Also macht jeder aufeinanderfolgende Pass einen Tausch weniger, und wir haben am Ende mit

N + (N-1) + (N-2) + ... + 2 + 1 = N * (N + 1) / 2 = 1/2 * N^2 + N/2

In der Big-O-Notation wird dies

O(1/2 * N^2 + N/2) = O(1/2 * N^2) = O(N^2)

Hier fallen wir linear (N/2) Begriff, da er von dem quadratischen als dominiert wird N -> inf. Dann fallen wir fallen 1/2 Führender konstanter Faktor, da es sich im Wesentlichen um ein Hardware -Detail handelt. Beachten Sie, dass dies eine menschliche Motivation ist: Die Klugheit von Big-o 'ist seine Definition bietet einen strengen Rahmen für die Unterbringung unserer Motivationen. Es stellt sich heraus, dass wir die führenden konstanten Faktoren fallen lassen.

Das Erstellen eines strengen Beweises der Komplexität ist eine Fähigkeit für sich, und das Wissen nur Definitionen hilft Ihnen nicht viel dabei. Beweis durch Induktion ist normalerweise anwendbar, wenn man festlegt Voraussetzungen und Post-Konditionen um jeden Durchgang einer Schleife. Beachten Sie in meinem informellen Argument, dass ich die vorherige Iteration berücksichtigt habe, wenn ich über das aktuelle Argumentation argumentiere: Dies ist ein induktives Denken. "Discrete Mathematics", "Proof by Induktion", "Kombinatorik" und "Zählen" sind alles gute Schlüsselwörter. (Ja, "Zählen" ist selbst ein Zweig der Mathematik und es ist schwer.)

Sobald Sie eine Formel bewiesen haben, ist es eine andere Fähigkeit, sie in Big-O zu "reduzieren" und erfordert im Wesentlichen ein wenig Kalkül (Grenzen). Schließlich können Sie in Ihren Beweisen nervige Zweige abschneiden, indem Sie feststellen, dass die Begriffe sie festlegen Die Einführung wird von einem anderen, bekannten bekannten dominiert.