1.1.1  Performance

Die gute Nachricht ist, dass Implementierungen der Algorithmen, die in diesem Buch beschrieben werden, sehr wahrscheinlich in deiner Lieblingsprogrammiersprache verfügbar sind. Du musst die Algorithmen also nicht alle selbst schreiben! Allerdings sind diese Implementierungen nutzlos, wenn du deren Vor- und Nachteile nicht verstehst. In diesem Buch lernst du, die Vor- und Nachteile verschiedener Algorithmen miteinander zu vergleichen: Solltest du für eine bestimmte Aufgabe Mergesort oder lieber Quicksort verwenden? Ist ein Array oder eine Liste besser geeignet? Die Verwendung einer anderen Datenstruktur kann einen sehr großen Unterschied ausmachen.

1.1.2  Problemlösungen

Du wirst zudem Verfahren zur Problemlösung für Aufgaben kennenlernen, an die du dich bislang vielleicht nicht herangetraut hast. Einige Beispiele:

• Falls du Videospiele magst, kannst du ein System für die Künstliche Intelligenz (KI) programmieren, das Graphenalgorithmen verwendet und das den User im Spiel verfolgt.

• Du wirst erfahren, wie du mit dem k-Nächste-Nachbarn-Algorithmus (k-Nearest-Neighbors-Algorithmus) ein Empfehlungssystem entwickeln kannst.

• Manche Aufgaben lassen sich nicht in angemessen kurzer Zeit lösen. Der Abschnitt des Buchs über NP-vollständige Probleme beschreibt, wie du solche Probleme erkennen kannst und stellt einen Algorithmus vor, der dir eine Näherungslösung liefert.

Allgemeiner formuliert: Nach der Lektüre dieses Buchs werden dir einige der meisten verbreiteten und für sehr viele Fälle anwendbaren Algorithmen vertraut sein. Mit dem Wissen aus diesem Buch kannst du dich spezielleren Algorithmen für die KI, für Datenbanken usw. zuwenden oder dich noch größeren Herausforderungen stellen.

1.2.1  Eine bessere Suchmethode

Ein besseres Verfahren ist das folgende: Fang mit der Zahl 50 an.

Diese ist zu klein, allerdings hast du soeben die Hälfte aller Zahlen ausgeschlossen! Du weißt nun, dass alle Zahlen von 1 bis 50 zu klein sind. Nächster Versuch: 75.

Zu groß, aber du hast wieder die Hälfte der verbliebenen Zahlen ausgeschlossen! Bei einer binären Suche nennst du die Zahl in der Mitte und schließt dadurch jeweils die Hälfte der noch vorhandenen Zahlen aus. Nun ist 63 an der Reihe (die Mitte zwischen 50 und 75).

So funktioniert die binäre Suche. Du hast soeben deinen ersten Algorithmus erlernt! So viele Zahlen kannst du mit jedem Rateversuch ausschließen:

An welche Zahl ich denke, spielt keine Rolle: Du benötigst höchstens 7 Versuche, um sie zu erraten, weil bei jedem Rateversuch so viele Zahlen ausgeschlossen werden.

Nehmen wir wieder an, du suchst nach einem Begriff in einem Wörterbuch, das 240.000 Einträge enthält. Was meinst du, wie viele Schritte für eine Suche im Worst Case, also im ungünstigsten Fall, nötig sind?

Bei der einfachen Suche können 240.000 Schritte notwendig sein, sofern sich das gesuchte Wort ganz am Ende des Wörterbuchs befindet. Bei der binären Suche hingegen wird bei jedem Schritt die Anzahl der verbliebenen Wörter halbiert, bis schließlich nur noch ein Wort übrig ist.

Bei der binären Suche sind also 18 Schritte erforderlich – ein riesiger Unterschied! Verallgemeinert bedeutet das: Bei einer Liste der Länge n benötigt die binäre Suche im Worst Case log₂ n Schritte, bei einer einfachen Suche sind hingegen n Schritte erforderlich.

Sehen wir uns doch einmal an, wie man eine binäre Suche in Python programmiert. Der Beispielcode verwendet Arrays. Falls du nicht weißt, wie Arrays‌ funktionieren, keine Sorge, sie werden im nächsten Kapitel erklärt. Du brauchst nur zu wissen, dass sie eine Sequenz von Elementen in einer Reihe aufeinanderfolgender Behälter speichern können, deren Gesamtheit als Array bezeichnet wird. Die Behälter werden, angefangen bei 0, durchnummeriert: Der erste befindet sich an der Position #0, der zweite ist #1, der dritte #2 usw.

Die Funktion binary_search‌ nimmt ein sortiertes Array und ein Objekt entgegen. Wenn das Objekt in diesem Array enthalten ist, liefert die Funktion dessen Position zurück. Du führst darüber Buch, welcher Teil des Arrays zu durchsuchen ist. Anfangs handelt es sich um das gesamte Array:

low = 0
high = len(list) - 1

Du überprüfst jeweils das mittlere Element:

mid = (low + high) // 2 
guess = list[mid]

Der Wert der mid-Funktion wird von Python automatisch abgerundet, sofern (low + high) keine gerade Zahl ist.

Sollte der geratene Wert zu klein sein, aktualisierst du low dementsprechend:

if guess < item:
  low = mid + 1

Und sollte der geratene Wert zu groß sein, aktualisierst du high. Hier ist der vollständige Code:

def binary_search(list, item):
  low = 0 
  high = len(list)—1 

  while low <= high: 
    mid = (low + high)  //2 
    guess =  list[mid]
    if guess == item: 
      return mid
    if guess > item: 
      high = mid - 1
    else: 
      low = mid + 1
  return None 

my_list = [1, 3, 5, 7, 9] 

print binary_search(my_list, 3) # => 1 
print binary_search(my_list, -1) # => None 

low und high führen darüber Buch, welcher Teil der Liste durchsucht wird.

Solange der Suchbereich mehr als ein Element umfasst ...

... wird das mittlere Element überprüft.

Das gesuchte Objekt wurde gefunden.

Der geratene Wert war zu groß.

Der geratene Wert war zu klein.

Das gesuchte Objekt ist in der Liste nicht enthalten.

Testen der Funktion.

Denk daran, dass die Nummerierung der Listenelemente bei 0 beginnt. Das zweite Element hat den Index 1.

»None« bedeutet in Python nil. Es zeigt an, dass ein Objekt nicht gefunden wurde.

1.2.2  Laufzeit

Bei allen vorgestellten Algorithmen werde ich die Laufzeit erklären. Ob nun die Laufzeit oder aber der Speicherplatzbedarf optimiert werden soll: Im Allgemeinen möchte man den effizientesten Algorithmus auswählen.

Zurück zur binären Suche. Wie viel Zeit sparst du durch ihre Verwendung? Beim ersten Ansatz wurden alle Zahlen der Reihe nach überprüft. Wenn die Liste 100 Zahlen enthält, sind bis zu 100 Rateversuche erforderlich. Wenn die Liste 4 Milliarden Zahlen enthält, sind bis zu 4 Milliarden Rateversuche notwendig. Die maximale Anzahl der Rateversuche entspricht also der Größe der Liste. Man bezeichnet das als lineare Laufzeit.‌‌

Bei der binären Suche verhält es sich anders. Wenn die Liste 100 Objekte enthält, sind höchstens 7 Rateversuche erforderlich. Enthält die Liste 4 Milliarden Objekte, sind höchstens 32 Rateversuche notwendig. Ziemlich leistungsstark, oder? Die binäre Suche benötigt eine logarithmische Laufzeit.‌‌ Die folgende Tabelle fasst unsere Ergebnisse zusammen.

1.3.1  Die Laufzeiten von Algorithmen nehmen unterschiedlich schnell zu

Bob programmiert einen Suchalgorithmus für die NASA. Sein Algorithmus kommt zum Einsatz, wenn eine Rakete auf dem Mond landen soll und kann den Landeplatz berechnen.

Hierbei handelt es sich um ein Beispiel dafür, dass die Laufzeiten zweier Algorithmen auf unterschiedliche Weise zunehmen können. Bob muss sich zwischen einer einfachen Suche und einer binären Suche entscheiden. Der Algorithmus muss sowohl schnell sein als auch fehlerlos funktionieren. Einerseits ist die binäre Suche schneller. Bob hat nämlich nur 10 Sekunden Zeit, um den Landeplatz zu ermitteln – denn sonst kommt die Rakete vom Kurs ab. Andererseits lässt sich die einfache Suche leichter programmieren. Und Bob möchte wirklich nicht, dass der Code zum Landen einer Rakete Bugs enthält! Vorsichtshalber will Bob die Laufzeiten beider Algorithmen messen, wenn er eine Liste verwendet, die 100 Elemente enthält.

Nehmen wir an, das Überprüfen eines Elements dauert eine Millisekunde (ms). Bei der einfachen Suche muss Bob 100 Elemente überprüfen, also dauert das Ausführen der Suche 100 ms. Bei der binären Suche muss er hingegen lediglich 7 Elemente überprüfen. log₂ 100 ist ungefähr 7, also dauert die Suche 7 ms. Realistisch betrachtet wird die Liste tatsächlich eher eine Milliarde Elemente enthalten. Wie lange würde dann die einfache Suche dauern? Und wie lange die binäre Suche? Vergewissere dich, dass du diese beiden Fragen beantworten kannst, bevor du weiterliest.

Bob führt eine binäre Suche mit einer Liste aus, die eine Milliarde Elemente enthält. Sie dauert 30 ms (log₂ 1.000.000.000 ist ungefähr 30). »30 ms!«, geht ihm durch Kopf. »Die binäre Suche ist rund 15 Mal schneller als die einfache Suche, denn bei 100 Elementen dauerte die einfache Suche 100 ms und die binäre Suche 7 ms. Also sollte die einfache Suche 30 × 15 = 450 ms dauern, richtig? Das ist deutlich unter den zulässigen 10 Sekunden.« Bob entschließt sich also dazu, die einfache Suche zu verwenden. Aber ist das die richtige Entscheidung?

Nein, denn wie sich zeigen wird, liegt Bob falsch. Völlig falsch. Die Laufzeit der einfachen Suche beträgt bei einer Milliarden Objekte eine Milliarde ms – das sind mehr als 11 Tage! Das Problem besteht hier darin, dass die Laufzeiten für binäre und einfache Suche nicht auf dieselbe Weise zunehmen.

Wenn die Anzahl der Objekte zunimmt, benötigt die binäre Suche zur Ausführung etwas mehr Zeit. Die einfache Suche jedoch benötigt sehr viel mehr Zeit zur Ausführung. Deshalb wird die binäre Suche sehr viel schneller als die einfache Suche, wenn die Zahlenliste größer wird. Bob dachte, dass die binäre Suche 15 Mal schneller als die einfache Suche ist, aber das stimmt nicht. Wenn die Liste eine Milliarden Objekte enthält, ist die binäre Suche rund 33 Millionen Mal schneller. Aus diesem Grund reicht es nicht aus zu wissen, wie lange ein Algorithmus zur Ausführung benötigt – man muss auch wissen, wie die Laufzeit anwächst, wenn die Größe der Liste zunimmt. Hier kommt die Landau-Notation ins Spiel.

Die Landau-Symbole geben an, wie schnell ein Algorithmus ist. Betrachte beispielsweise eine Liste der Größe n. Bei der einfachen Suche muss jedes einzelne Element überprüft werden, daher sind n Operationen erforderlich. Für diese Laufzeit wird das Landau-Symbol O(n) verwendet. Aber wo sind die Sekunden angegeben? Es gibt keine – die Geschwindigkeit wird nicht in Sekunden angegeben. Die Landau-Notation ermöglicht es, die Anzahl der Operationen zu vergleichen. Sie teilt dir mit, wie schnell die Anzahl der Operationen des Algorithmus anwächst.

Hier ist ein weiteres Beispiel: Die binäre Suche benötigt log n Operationen, um eine Liste der Größe n zu überprüfen. Wie sieht das als Landau-Notation aus? Hierfür schreibt man O(log n). Im Allgemeinen notiert man ein Landau-Symbol folgendermaßen:

Du kannst daran ablesen, wie viele Operationen der Algorithmus ausführen wird. Im Englischen spricht man auch von der Big-O-Notation, weil der Anzahl der Operationen ein großes »O« vorangestellt wird. (Klingt wie ein Scherz, ist aber tatsächlich wahr!)

Betrachten wir einige Beispiele. Kannst du die Laufzeiten der Algorithmen herausfinden?

1.3.2  Visualisierung verschiedener Laufzeiten

Zunächst ein praktisches Beispiel, das du mit ein paar Blättern Papier und einem Bleistift leicht nachvollziehen kannst. Deine Aufgabe besteht darin, ein Gitter zu zeichnen, das aus 16 Kästchen besteht.

Algorithmus 1

Eine Möglichkeit besteht darin, der Reihe nach 16 einzelne Kästchen zu zeichnen. Wie du weißt, gibt die Landau-Notation die Anzahl der Operationen an. In diesem Beispiel stellt das Zeichnen eines Kästchens eine Operation dar. Und du musst 16 Kästchen zeichnen. Wie viele Operationen sind also erforderlich, wenn du die Kästchen einzeln zeichnest?

Zum Zeichnen von 16 Kästchen sind 16 Schritte notwendig. Welche Laufzeit benötigt dieser Algorithmus demzufolge?

Algorithmus 2

Probiere nun den folgenden Algorithmus aus. Falte das Papierblatt.

Bei diesem Beispiel ist jedes Falten des Papierblatts eine Operation. Du hast soeben also zwei Kästchen mit nur einer Operation erstellt!

Falte das Papierblatt ein zweites, drittes und viertes Mal.

Falte das Papierblatt nach der vierten Faltung wieder auf. Und siehe da – ein tadelloses Gitter. Mit jeder Faltung verdoppelst du die Anzahl der Kästchen. Du hast also mit 4 Operationen 16 Kästchen erstellt!

Du kannst die Anzahl der Kästchen mit jeder Faltung verdoppeln, also kannst du mit 4 Schritten 16 Kästchen »zeichnen«. Welche Laufzeit benötigt dieser Algorithmus? Lege die Laufzeiten für die beiden Algorithmen fest, bevor du weitermachst.

Antworten: Algorithmus 1 benötigt die Laufzeit O(n) und Algorithmus 2 die Laufzeit O(log n).

1.3.3  Die Landau-Notation beschreibt die Laufzeit im Worst Case

Nehmen wir an, du verwendest eine einfache Suche, um in einem Telefonbuch nach einer Person zu suchen. Wie du weißt, benötigt die einfache Suche die Laufzeit O(n), was im Worst Case bedeutet, dass du sämtliche Einträge deines Telefonbuchs überprüfen musst. Im vorliegenden Fall suchst du nach meinem Namen »Adit«. Hierbei handelt es sich um den ersten Eintrag in deinem Telefonbuch. Du musst also gar nicht alle Einträge überprüfen – du hast das Gesuchte schon beim ersten Versuch gefunden. Heißt das nun, dass dieser Algorithmus die Laufzeit O(n) benötigt? Oder sogar nur O(1), weil du die Person beim ersten Versuch gefunden hast?

Die einfache Suche benötigt nach wie vor die Laufzeit O(n). In diesem Fall hast du zwar sofort gefunden, was du gesucht hast, aber hierbei handelt es sich um den günstigsten Fall. Die Landau-Notation beschreibt jedoch den Worst Case. Du kannst also sagen, dass du im Worst Case sämtliche Einträge im Telefonbuch einmal überprüfen musst – und das entspricht der benötigten Laufzeit O(n). Dabei handelt es sich also um eine Art Zusicherung (eine obere Schranke für die Laufzeit) – du kannst dir sicher sein, dass die einfache Suche niemals langsamer als O(n) sein wird.

1.3.4  Typische Laufzeiten gebräuchlicher Algorithmen

Nachstehend sind fünf Laufzeiten (sortiert nach abnehmender Geschwindigkeit) aufgeführt, die dir häufig begegnen werden:

• O(log n), die auch als logarithmische Laufzeit bezeichnet wird. Beispiel: Die binäre Suche.

• O(n), die auch als lineare Laufzeit bezeichnet wird. Beispiel: Die einfache Suche.

• O(n * log n). Beispiel: Ein schneller Sortieralgorithmus wie Quicksort (das in Kapitel 4 erörtert wird).

• O(n²). Beispiel: Ein langsamer Sortieralgorithmus wie Selectionsort (das in Kapitel 2 erörtert wird).

• O(n!). Beispiel: Ein richtig langsamer Algorithmus, wie der Algorithmus zur Lösung des Problems des Handlungsreisenden (mehr dazu in Kürze).

Nehmen wir an, du zeichnest wieder die 16 Kästchen und du kannst dir dafür einen von 5 verschiedenen Algorithmen aussuchen. Wenn du den ersten Algorithmus verwendest, wirst du eine Laufzeit von O(log n) benötigen, um die Kästchen zu zeichnen. Du kannst pro Sekunde 10 Operationen ausführen. Bei einer Laufzeit von O(log n) benötigst du 4 Operationen, um 16 Kästchen zu erzeugen (log 16 = 4). Du benötigst also 0,4 Sekunden zum Zeichnen des Gitters. Und wenn du 1.024 Kästchen zeichnen müsstest? Zum Zeichnen von 1.024 Kästchen sind log 1.024 = 10 Operationen bzw. 1 Sekunde Zeit erforderlich. Diese Angaben gelten für den ersten Algorithmus.

Der zweite Algorithmus ist langsamer: Er benötigt eine Laufzeit von O(n). Zum Zeichnen von 16 Kästchen sind 16 Operationen notwendig und zum Zeichnen von 1.024 Kästchen sind 1.024 Operationen nötig. Wie vielen Sekunden entspricht das?

Der folgenden Tabelle kannst du entnehmen, wie lange es dauert, ein Gitter mit einem der anderen Algorithmen zu zeichnen (sortiert nach zunehmender Laufzeit):

Es gibt noch andere Laufzeiten, aber diese fünf sind die gebräuchlichsten.

Diese Darstellung ist eine Vereinfachung. Tatsächlich kannst du eine bestimmte Laufzeit nicht so fein säuberlich in eine bestimmte Anzahl von Operationen umwandeln, aber fürs Erste ist diese Betrachtungsweise ausreichend. Nachdem du einige weitere Algorithmen kennengelernt hast, werden wir in Kapitel 4 auf die Landau-Notation zurückkommen. Du solltest dir an dieser Stelle die folgenden Punkte merken:

• Die Geschwindigkeit eines Algorithmus wird nicht in Sekunden bemessen, sondern durch die Zunahme der Anzahl der Operationen.

• Wir betrachten vielmehr, wie schnell die Laufzeit eines Algorithmus anwächst, wenn die Größe der Eingabe zunimmt.

• Die Laufzeit eines Algorithmus wird durch die Landau-Notation beschrieben.

• O(log n) ist ohnehin schneller als O(n), O(log n) ist aber sehr viel schneller als O(n), wenn die Größe der zu durchsuchenden Liste von Objekten zunimmt.

1.3.5  Das Problem des Handlungsreisenden

Nach der Lektüre des letzten Abschnitt wirst du dir vielleicht gedacht haben: »Das wird niemals vorkommen, dass ich auf eine Algorithmus stoße, der eine Laufzeit von O(n!) benötigt«. Ich werde versuchen, dir das Gegenteil zu beweisen. Betrachten wir ein Beispiel für einen Algorithmus mit wirklich miserabler Laufzeit. Hierbei handelt es sich um ein sehr bekanntes Problem aus der Informatik, weil die Anzahl der Operationen haarsträubend schnell zunimmt und einige sehr kluge Köpfe denken, dass es keine bessere Lösung gibt. Es wird als das Problem des Handlungsreisenden bezeichnet.‌

Ein Handlungsreisender muss fünf verschiedene Städte besuchen.

Der Handlungsreisende, den ich Opus nenne, möchte diese fünf Städte besuchen, dabei aber nur die minimal nötige Strecke zurücklegen. Mit dieser Möglichkeit können wir das Ziel erreichen: Betrachte alle möglichen Reihenfolgen, in der er die verschiedenen Städte aufsuchen kann:

Opus summiert die jeweils zurückgelegten Strecken und wählt die kürzeste Reiseroute aus. Bei 5 Städten gibt es 120 Permutationen, es sind also 120 Operationen erforderlich, um diese Aufgabe für 5 Städte zu lösen. Bei 6 Städten sind 720 Operationen nötig (es gibt 720 Permutationen). Bei 7 Städten sind es schon 5.040 Operationen!

Bei n Städten sind n! (n Fakultät)‌ Operationen nötig, um das Ergebnis zu berechnen. Der Algorithmus benötigt also eine Laufzeit von O(n!) – eine faktorielle Laufzeit. ‌‌Wenn man von den ersten paar Zahlen absieht, ist eine enorme Anzahl von Operationen erforderlich. Wenn du es mit mehr als 100 Städten zu tun hast, ist es unmöglich, das Ergebnis zu berechnen. Bevor das Resultat feststeht, wird unsere Sonne schon zu einem Roten Riesen geworden sein.

Der Algorithmus ist ja wirklich fürchterlich. Sollte Opus nicht lieber einen anderen verwenden? Das kann er aber leider nicht, denn hierbei handelt es sich um eines der ungelösten Probleme der Informatik. Es gibt keinen schnelleren Algorithmus für diese Aufgabe und viele kluge Köpfe halten es für unmöglich, einen besseren Algorithmus für diese Aufgabe zu finden. Wir können bestenfalls eine Näherungslösung berechnen. Mehr dazu in Kapitel 10.

Ein abschließender Hinweis: Erfahrene Leser sollten einen Blick auf binäre Suchbäume werfen! Im letzten Kapitel werden diese kurz beschrieben.