Computer Science Distilled, Kapitel 2: Komplexität

Bei fast jeder Berechnung sind eine Vielzahl von Anordnungen für die Prozesse möglich. Es ist unerlässlich, diejenige Anordnung zu wählen, die dazu neigt, die für die Berechnung notwendige Zeit zu minimieren.

— Ada Lovelace

Wie lange dauert es, 26 gemischte Karten zu sortieren? Würde es doppelt so lange dauern, wenn Sie stattdessen 52 Karten hätten? Wie viel länger würde es für tausend Kartendecks dauern? Die Antwort liegt in der Methode, die zum Sortieren der Karten verwendet wird.

Eine Methode ist eine Liste eindeutiger Anweisungen zur Erreichung eines Ziels. Eine Methode, die immer eine endliche Reihe von Operationen erfordert, wird als Algorithmus bezeichnet. Beispielsweise ist ein Kartensortieralgorithmus eine Methode, die immer einige Operationen zur Sortierung eines Decks von 26 Karten pro Farbe und Rang angibt.

Weniger Operationen benötigen weniger Rechenleistung. Wir mögen schnelle Lösungen, also beobachten wir die Anzahl der Operationen in unseren Algorithmen. Viele Algorithmen erfordern eine schnell wachsende Anzahl von Operationen, wenn die Eingabe größer wird. Zum Beispiel könnte unser Kartensortieralgorithmus wenige Operationen zum Sortieren von 26 Karten benötigen, aber viermal mehr Operationen zum Sortieren von 52 Karten!

Um böse Überraschungen zu vermeiden, wenn unsere Problemgröße wächst, ermitteln wir die Zeitkomplexität des Algorithmus. In diesem Kapitel lernen Sie, wie Sie

• Zeitkomplexitäten zählen und interpretieren
• ihre Wachstumsrate mit schicken Big-O-Notationen ausdrücken
• sich von exponentiellen Algorithmen davonlaufen
• sicherstellen, dass Sie genügend Computerspeicher haben.

Aber zuerst: Wie definieren wir Zeitkomplexität?

Zeitkomplexität wird geschrieben als$T(n)$. Sie gibt die Anzahl der Operationen an, die der Algorithmus bei der Verarbeitung einer Eingabe der Größe$n$durchführt. Wir bezeichnen die$T(n)$eines Algorithmus auch als seine Laufkosten. Wenn unser Kartensortieralgorithmus$T(n)=n^2$folgt, können wir vorhersagen, wie viel länger es dauert, ein Deck zu sortieren, sobald wir seine Größe verdoppeln.$\frac{T(2n)}{T(n)}=4$.

Hoffen auf das Beste, Vorbereiten auf das Schlimmste

Ist es nicht schneller, einen Stapel Karten zu sortieren, der bereits fast sortiert ist?

Die Eingabegröße ist nicht die einzige Eigenschaft, die die Anzahl der von einem Algorithmus benötigten Operationen beeinflusst. Wenn ein Algorithmus für denselben Wert von$T(n)$unterschiedliche Werte von$n$haben kann, greifen wir auf Fälle zurück

• Best Case (Bester Fall): Wenn die Eingabe die minimale Anzahl von Operationen für jede Eingabe dieser Größe erfordert. Beim Sortieren tritt dies ein, wenn die Eingabe bereits sortiert ist.
• Worst Case (Schlechtester Fall): Wenn die Eingabe die maximale Anzahl von Operationen für jede Eingabe dieser Größe erfordert. Bei vielen Sortieralgorithmen ist dies der Fall, wenn die Eingabe in umgekehrter Reihenfolge vorliegt.
• Average Case (Durchschnittlicher Fall): Bezieht sich auf die durchschnittliche Anzahl von Operationen, die für typische Eingaben dieser Größe erforderlich sind. Für das Sortieren wird normalerweise eine Eingabe in zufälliger Reihenfolge betrachtet.

Im Allgemeinen ist der schlimmste Fall am wichtigsten. Von dort erhalten Sie eine garantierte Basislinie, auf die Sie sich immer verlassen können. Wenn nichts über das Szenario gesagt wird, wird der schlimmste Fall angenommen. Als Nächstes sehen wir, wie man einen Worst-Case-Fall praktisch analysiert.

2.1 Zeit messen

Wir ermitteln die Zeitkomplexität eines Algorithmus, indem wir die Anzahl der grundlegenden Operationen zählen, die er für eine hypothetische Eingabe der Größe$n$benötigt. Wir demonstrieren dies mit Selection Sort, einem Sortieralgorithmus, der verschachtelte Schleifen verwendet. Eine äußere for-Schleife aktualisiert die aktuell zu sortierende Position, und eine innere for-Schleife wählt das Element aus, das an die aktuelle Position kommt¹

function selection_sort(list)
    for current ← 1 … list.length - 1
        smallest ← current
        for i ← current + 1 … list.length
            if list[i] < list[smallest]
                smallest ← i
        list.swap_items(current, smallest)

Sehen wir uns an, was mit einer Liste von$n$Elementen geschieht, unter Annahme des schlimmsten Falls. Die äußere Schleife läuft$n-1$mal und führt pro Durchlauf zwei Operationen durch (eine Zuweisung und ein Tausch), was insgesamt$2n-2$Operationen ergibt. Die innere Schleife läuft zuerst$n-1$mal, dann$n-2$mal,$n-3$mal und so weiter. Wir wissen, wie man solche Sequenzen summiert²

Im schlimmsten Fall ist die if-Bedingung immer erfüllt. Das bedeutet, die innere Schleife führt$(n^2-n)/2$mal einen Vergleich und eine Zuweisung durch, also$n^2-n$Operationen. Insgesamt kostet der Algorithmus$2n-2$Operationen für die äußere Schleife plus$n^2-n$Operationen für die innere Schleife. Wir erhalten also die Zeitkomplexität

Und nun? Wenn unsere Listenlänge$n=8$war und wir sie verdoppeln, wird die Sortierzeit mit

Wenn wir sie wieder verdoppeln, multiplizieren wir die Zeit mit$3.90$. Verdoppeln Sie sie immer wieder und finden Sie$3.94$, $3.97$, $3.98$. Beachten Sie, wie sich dies 4 nähert? Das bedeutet, es würde viermal so lange dauern, zwei Millionen Elemente zu sortieren als eine Million Elemente.

2.1.1 Wachstum verstehen

Sagen wir, die Eingabegröße eines Algorithmus ist sehr groß und wir erhöhen sie noch weiter. Um vorherzusagen, wie sich die Ausführungszeit entwickeln wird, müssen wir nicht alle Terme von$T(n)$kennen. Wir können$T(n)$durch seinen am schnellsten wachsenden Term, den sogenannten dominanten Term, annähern.

Das Karteikartenproblem: Gestern ist Ihnen eine Kiste mit Karteikarten umgefallen. Es hat zwei Stunden gedauert, bis Sie sie mit Selection Sort wieder sortiert hatten. Heute sind zehn Kisten umgefallen. Wie viel Zeit werden Sie brauchen, um die Karten wieder in Ordnung zu bringen?

Wir haben gesehen, dass Selection Sort$T(n)=n^2+n-2$folgt. Der am schnellsten wachsende Term ist$n^2$, daher können wir schreiben$T(n)\approx \; multipliziert.n^2$. Angenommen, es gibt$n$Karten pro Kiste, finden wir

Sie brauchen ungefähr$(100\times 2)\text{Stunden}=200$Stunden! Was wäre, wenn wir eine andere Sortiermethode verwendet hätten? Es gibt zum Beispiel eine namens "Bubble Sort", deren Zeitkomplexität$T(n)=0.5n^2+0.5n$ist. Der am schnellsten wachsende Term ergibt dann$T(n)\approx \; multipliziert.0.5n^2$, daher

Die$0.5$Koeffizient hebt sich selbst auf! Die Vorstellung, dass$n^2-n-2$und$0.5n^2+0.5n$beide wachsen wie$n^2$nicht leicht zu verstehen ist. Wie ignoriert der am schnellsten wachsende Term einer Funktion alle anderen Zahlen und dominiert das Wachstum? Versuchen wir, dies visuell zu verstehen.

In Abbildung 2.2 werden die beiden Zeitkomplexitäten, die wir gesehen haben, mit$n^2$bei verschiedenen Zoomstufen verglichen. Wenn wir sie für immer größere Werte von$n$plotten, scheinen ihre Kurven sich immer mehr anzunähern. Tatsächlich können Sie jede beliebige Zahl in die Punkte von$T(n)=\mathrm{\bullet \; einsetzen,\; und\; es\; wird\; immer\; noch\; wie}{n}^2+\mathrm{\bullet \; einsetzen,\; und\; es\; wird\; immer\; noch\; wie}n+\mathrm{\bullet \; einsetzen,\; und\; es\; wird\; immer\; noch\; wie}$wachsen. Denken Sie daran, dass dieser Effekt der sich annähernden Kurven funktioniert, wenn der am schnellsten wachsende Term derselbe ist. Die Darstellung einer Funktion mit linearem Wachstum ($n^2$.

) kommt niemals einer mit quadratischem Wachstum ($n$) immer näher, die wiederum niemals einer mit kubischem Wachstum ($n^2$) immer näher kommt. Deshalb schneiden Algorithmen mit quadratisch wachsenden Kosten bei sehr großen Eingaben weitaus schlechter ab als Algorithmen mit linearen Kosten. Sie schneiden jedoch weitaus besser ab als solche mit kubischen Kosten. Wenn Sie dies verstanden haben, ist der nächste Abschnitt einfach: Wir lernen einfach die schicke Notation, die Programmierer verwenden, um dies auszudrücken.$n^3$).

2.2 Die Big-O-Notation

Es gibt eine spezielle Notation, um Wachstumsklassen zu bezeichnen: die Big-O-Notation. Eine Funktion mit einem am schnellsten wachsenden Term von

oder schwächer ist$2^n$ ; eine mit einem quadratischen oder schwächeren Wachstum ist$O(2^n)$; linear wachsend oder weniger,$O(n^2)$,$O(n)$und so weiter. Die Notation wird verwendet, um den dominanten Term der Kostenfunktionen von Algorithmen im schlimmsten Fall auszudrücken – das ist die Standardmethode zur Angabe der Zeitkomplexität³.

vorkommen.$O(n^2)$Sowohl Selection Sort als auch Bubble Sort sind$O(n,n)$aber wir werden bald$O(n^2)$log$\times$Algorithmen entdecken, die die gleiche Arbeit verrichten. Mit unseren$\times$Algorithmen führte eine Verzehnfachung der Eingabegröße zu einer Verhundertfachung der Laufkosten. Mit einem$O(n,n)$Algorithmus führt eine Verzehnfachung der Eingabegröße zu nur$\times$der Laufkosten.$10,10\approx \; multipliziert.34\mathrm{\times }$Wenn

eine Million ist, ist$n$eine Billion, während$n^2$nur wenige Millionen sind. Jahre, die mit einem quadratischen Algorithmus für eine große Eingabe laufen, könnten mit Minuten gleichgesetzt werden, wenn ein$n,n$Algorithmus verwendet würde. Deshalb benötigen Sie eine Analyse der Zeitkomplexität, wenn Sie Systeme entwerfen, die sehr große Eingaben verarbeiten.$O(n,n)$Beim Entwurf eines rechnerischen Systems ist es wichtig, die häufigsten Operationen vorherzusehen. Dann können Sie die Big-O-Kosten verschiedener Algorithmen vergleichen, die diese Operationen ausführen⁴. Außerdem funktionieren die meisten Algorithmen nur mit spezifischen Eingabestrukturen. Wenn Sie Ihre Algorithmen im Voraus auswählen, können Sie Ihre Eingabedaten entsprechend strukturieren.

Einige Algorithmen laufen immer mit konstanter Dauer, unabhängig von der Eingabegröße – sie sind

konstant.$O(1)$Zum Beispiel, um zu prüfen, ob eine Zahl gerade oder ungerade ist: Wir sehen, ob ihre letzte Ziffer ungerade ist und *boom*, Problem gelöst. Egal wie groß die Zahl ist. Wir werden mehr$O(1)$Algorithmen in den nächsten Kapiteln sehen. Sie sind erstaunlich, aber zuerst sehen wir, welche Algorithmen *nicht* erstaunlich sind.

2.3 Exponentials

Wir sagen$O(2^n)$Algorithmen sind exponentielle Zeit. Aus der Grafik der Wachstumsklassen (Abbildung 2.3) scheint es nicht, dass das quadratische$n^2$und das exponentielle$2^n$sich viel unterscheiden. Wenn man die Grafik herauszoomt, ist offensichtlich, dass das exponentielle Wachstum das quadratische brutal dominiert.

Exponentielle Zeit wächst so stark, dass wir diese Algorithmen als „nicht ausführbar“ betrachten. Sie laufen für sehr wenige Eingabetypen und benötigen enorme Mengen an Rechenleistung, wenn die Eingaben nicht winzig sind. Die Optimierung jedes Aspekts des Codes oder die Verwendung von Supercomputern hilft nicht. Das vernichtende exponentielle Wachstum dominiert immer und hält diese Algorithmen unrentabel.

Um die Explosivität des exponentiellen Wachstums zu veranschaulichen, zoomen wir die Grafik noch weiter heraus und ändern die Zahlen (Abbildung 2.5). Der Exponent wurde reduziert (von$2$zu$1.5$) und sein Wachstum wurde durch tausend geteilt. Das Polynom hatte seinen Exponenten erhöht (von$2$zu$3$) und sein Wachstum mit tausend multipliziert.

Einige Algorithmen sind sogar noch schlimmer als exponentielle Zeitalgorithmen. Dies ist der Fall bei faktoriellen Zeitalgorithmen, deren Zeitkomplexitäten$O(n!)$sind. Exponentielle und faktorielle Zeitalgorithmen sind schrecklich, aber wir brauchen sie für die schwierigsten rechnerischen Probleme: die berühmten NP-vollständigen Probleme. Wir werden wichtige Beispiele für NP-vollständige Probleme im nächsten Kapitel behandeln. Vorerst denken Sie daran: Die erste Person, die einen nicht-exponentiellen Algorithmus für ein NP-vollständiges Problem findet, erhält eine Million Dollar⁵ vom Clay Mathematics Institute.

Es ist wichtig, die Art des Problems, mit dem Sie es zu tun haben, zu erkennen. Wenn bekannt ist, dass es NP-vollständig ist, ist der Versuch, eine optimale Lösung zu finden, ein Kampf gegen das Unmögliche. Es sei denn, Sie zielen auf diese Million Dollar ab.

2.4 Speicher zählen

Selbst wenn wir Operationen unendlich schnell durchführen könnten, gäbe es immer noch eine Grenze für unsere Rechenleistung. Während der Ausführung benötigen Algorithmen Arbeitsspeicher, um ihre laufenden Berechnungen zu verfolgen. Dies verbraucht Computerspeicher, der nicht unendlich ist.

Das Maß für den Arbeitsspeicher, den ein Algorithmus benötigt, wird als Speicherkomplexität bezeichnet. Die Analyse der Speicherkomplexität ähnelt der Analyse der Zeitkomplexität. Der Unterschied besteht darin, dass wir den Computerspeicher und nicht die Rechenoperationen zählen. Wir beobachten, wie sich die Speicherkomplexität entwickelt, wenn die Eingabegröße des Algorithmus wächst, genau wie bei der Zeitkomplexität.

Zum Beispiel benötigt Selection Sort lediglich Arbeitsspeicher für eine feste Menge von Variablen. Die Anzahl der Variablen hängt nicht von der Eingabegröße ab. Daher sagen wir, dass die Speicherkomplexität von Selection Sort$O(1)$ist: Unabhängig von der Eingabegröße benötigt er die gleiche Menge an Computerspeicher für den Arbeitsspeicher.

Viele andere Algorithmen benötigen jedoch Arbeitsspeicher, der mit der Eingabegröße wächst. Manchmal ist es unmöglich, die Speicheranforderungen eines Algorithmus zu erfüllen. Sie werden keinen geeigneten Sortieralgorithmus mit$O(n,n)$Zeitkomplexität und$O(1)$Speicherkomplexität finden. Computer-Speicherbeschränkungen erzwingen manchmal einen Kompromiss. Bei wenig Speicher benötigen Sie wahrscheinlich einen Algorithmus mit langsamer$O(n^2)$Zeitkomplexität, da er$O(1)$Speicherkomplexität hat.

Fazit

In diesem Kapitel haben wir gelernt, dass Algorithmen unterschiedliche Arten der Gier nach der Verbrauchszeit und des Computerspeichers haben können. Wir haben gesehen, wie wir dies mit Zeit- und Speicherkomplexitätsanalysen bewerten können. Wir haben gelernt, die Zeitkomplexität durch Ermittlung der exakten$T(n)$Funktion zu berechnen, der Anzahl der von einem Algorithmus durchgeführten Operationen.

Wir haben gesehen, wie die Zeitkomplexität mit der Big-O-Notation ($O$) ausgedrückt wird. Im gesamten Buch werden wir einfache Zeitkomplexitätsanalysen von Algorithmen mit dieser Notation durchführen. Oft ist die Berechnung von$T(n)$nicht notwendig, um die Big-O-Komplexität eines Algorithmus abzuleiten.

Wir haben gesehen, dass die Kosten für die Ausführung exponentieller Algorithmen so explodieren, dass diese Algorithmen bei großen Eingaben nicht ausführbar sind. Und wir haben gelernt, diese Fragen zu beantworten:

• Haben verschiedene Algorithmen einen signifikanten Unterschied in Bezug auf die benötigten Operationen?
• Wenn die Eingabegröße mit einer Konstanten multipliziert wird, was passiert dann mit der Zeit, die ein Algorithmus zum Ausführen benötigt?
• Würde ein Algorithmus eine vernünftige Anzahl von Operationen durchführen, sobald die Größe der Eingabe wächst?
• Wenn ein Algorithmus zu langsam für die Ausführung auf einer Eingabe einer bestimmten Größe ist, würde die Optimierung des Algorithmus oder die Verwendung eines Supercomputers helfen?

¹: Um einen neuen Algorithmus zu verstehen, führen Sie ihn mit einer kleinen Beispiel-Eingabe auf Papier aus.

²: Im vorherigen Kapitel haben wir gezeigt${\sum }_{i=1}^{n}i=n(n+1)/2$.

: Wir sagen „Oh“, z. B. „Dieser Sortieralgorithmus ist Oh-N-Quadrat„.

: Für die Big-O-Komplexitäten der meisten Algorithmen, die gängige Aufgaben ausführen, siehe http://code.energy/bigo

: Es wurde bewiesen, dass ein nicht-exponentieller Algorithmus für *irgendein* NP-vollständiges Problem auf *alle* NP-vollständigen Probleme verallgemeinert werden könnte. Da wir nicht wissen, ob ein solcher Algorithmus existiert, erhalten Sie auch eine Million Dollar, wenn Sie beweisen, dass ein NP-vollständiges Problem nicht mit nicht-exponentiellen Algorithmen gelöst werden kann!

Computer Science Distilled: Learn the Art of Solving Computational Problems von Wladston Viana Ferreira Filho ist jetzt auf Amazon erhältlich.