Einführung in die Algorithmik

Geschrieben von Daniel Graf.

Bevor wir beginnen

In diesem Einführungskapitel lernst du, was wir an der SOI unter einem Algorithmus verstehen und wie wir bestimmen, ob ein Algorithmus schneller ist als ein anderer.

An den SOI-Workshops ist dieses Thema immer mein Lieblingsthema, weshalb ich dir hier das gerne auch als Skriptkapitel präsentiere. Ich versuche möglichst keine Vorkenntnisse vorauszusetzen und es so verständlich wie möglich zu halten. Falls mir das nicht gelingt, du irgendwo den Faden verlierst oder du ganz einfach Fragen hast, melde dich gerne bei mir unter daniel@soi.ch. Diese Skripte sind noch ganz neu, wir sind also auf deine Hilfe angewiesen, um sie fortlaufend zu verbessern.

Das Kapitel basiert auf dem Inhalt der SOI-Workshops und den ersten beiden Vorlesungen im Frühjahr 2016 von “Datenstrukturen & Algorithmen” gehalten von Prof. Peter Widmayer an der ETH Zürich. Wenn dich später mal interessiert, was dort sonst noch alles behandelt wurde, findest du hier meine weiteren Mitschriften. Jetzt geht’s aber los!

Was ist ein Algorithmus?

In der Zeitung werden Algorithmen häufig als die bösen Dinge dargestellt, die einem empfehlen rote Kugelschreiber zu kaufen, weil man kürzlich blaue Kugelschreiber gekauft hat. Wir als Informatiker/innen verstehen darunter aber etwas anderes: eine systematische Anleitung, die ein spezifisches Problem löst.

Ein Beispiel, das ihr alle kennt: die Multiplikation von zwei Zahlen, wie man sie in der Primarschule lernt, Ziffer für Ziffer: Wenn wir \(62\) mal \(37\) ausrechnen wollen, so beginnen wir mit \(2 \cdot 7\). Wir schreiben das rechtsbündig auf ein Blatt. Wir machen mit \(6 \cdot 7\) weiter und schreiben das um eine Stelle versetzt darunter. Machen wir das auch für \(2 \cdot 3\) (um eine Stelle versetzt) und \(6 \cdot 3\) (um zwei Stellen versetzt), so bekommen wir eine Liste von vier Zahlen, die wir schliesslich aufaddieren, um das Endresultat zu erhalten:

   62*37
--------
      14
     42
      6
    18
--------
    2294

Die allgemeine Vorgehensweise wie wir so zwei Zahlen miteinander multiplizieren ist ein Algorithmus, also eine Anleitung wie wir von der Eingabe (zwei Zahlen) zur gewünschten Ausgabe (deren Produkt) kommen und was wir Schritt für Schritt dabei tun müssen. Dabei genügt es nicht einfach ein Beispiel durchzurechnen, sondern wir wollen ein Verfahren, das wir zum Multiplizieren zweier beliebiger Zahlen anwenden können.

An der Informatik-Olympiade studieren wir oft die Eigenschaften solcher Algorithmen. Ist diese Multiplikationsmethode korrekt? Ist sie clever? Schnell? Speichereffizient? Denn diese Fragen stehen im Zentrum der Informatik. Die Association for Computing Machinery, kurz ACM, (die weltgrösste Vereinigung von Informatiker/innen) gibt folgende Definition:

Was ist Informatik?

“Informatik ist die systematische Wissenschaft von Algorithmen und Datenstrukturen, genauer:

  • deren formale Eigenschaften
  • ihre linguistische und mechanische Realisierung
  • ihre Anwendungen

Unter den formalen Eigenschaften verstehen wir meistens die Korrektheit und die Effizienz eines Algorithmus, womit wir gleich in diesem Kapitel beginnen. Die Realisierung ist bei uns die Programmierung, was wir in einigen anderen Einsteigerkapiteln behandeln. Die Anwendungen sind dann schliesslich das, was wir in unseren Aufgaben und bei den fortgeschritteneren Themen behandeln.

Als erste Eigenschaft von Algorithmen wollen wir oft einfach unterscheiden zwischen Lösbarkeit und Unlösbarkeit. Ein Beispiel:

Staubsaugerproblem

Wir kennen den Grundriss unseres Wohnzimmers und wollen die Steckdosen in unserem Zimmer so platzieren, dass wir mit einem Staubsauger, der ein Stromkabel einer gewissen Länge hat, die ganze Wohnung putzen können. Wieviele Steckdosen brauchen wir dafür? Wie platzieren wir sie am besten? Das sind typische Aufgaben, die an der SOI behandelt werden.

Heute gibt es aber auch Staubsauger, die ohne Kabel auskommen und wie Roboter den Raum abfahren. Statt Steckdosen brauchen diese Roboter Ladestationen, die sie erreichen müssen bevor die Batterie leer ist. Auch dabei stellen sich interessante Fragen: Wie verteilen wir die Ladestationen optimal? Was ist eine gute Putzroute für den Roboter? Das Suchen einer solchen optimalen Putzrundreise ist ähnlich zu folgendem bekannten Problem:

Das Rundreiseproblem (TSP)

Ein Handlungsreisender möchte jede Stadt in einem Land möglichst rasch besuchen. Wir suchen also die kürzeste Tour durch alle Städte. Das ist eines der bekanntesten Probleme der theoretischen Informatik und heisst Traveling Salesman [1] Problem, kurz TSP.

Eine Art das Problem zu lösen ist es, einfach alle möglichen Reihenfolgen auszuprobieren. Für jede Permutation, so nennt man Reihenfolgen in der Mathematik, der Städte berechnen wir die Kosten und merken uns das Minimum. Nun haben wir also bereits einen ersten Algorithmus für TSP. Doch ist er gut oder schlecht?

Für \(n\) Städte, die alle miteinander verbunden sind, prüfen wir so alle \(n \cdot (n-1) \cdot (n-2) \cdots 4 \cdot 3 \cdot 2 \cdot 1\) Reihenfolgen, diese Anzahl nennt man auch \(n\)-Fakultät und schreibt “\(n!\)”.

Wie grosse Probleme können wir mit so einem Algorithmus lösen? \(100\) Städte? Dazu müssten wir \(100!\) Permutationen testen. Das sind aber sicher mehr als \(2^{100}\) viele. Ist das viel? Stellen wir uns ein Blatt Papier vor. Falten wir es \(100\) Mal, dann ist der resultierende Stapel \(2^{100}\) Papierlagen dick. Das ist etwa so gross wie das bekannte Universum! [2]

Interessanterweise kennt man bis heute keine viel besseren Algorithmen für TSP. 1970 konnte man das Problem mit einem etwas cleveren Algorithmus für 120 Städten lösen. Mit dem selben Algorithmus kommt man heute auf 140 Städte, einfach durch schnellere Computer. Nur zu warten bis die Maschinen schneller werden, bringt uns also nicht allzu weit.

Mittlerweile gibt es aber auch bessere Algorithmen für gewisse Arten von Graphen, sodass wir auch Rundreisen mit hunderttausenden Städte finden können. Ein algorithmischer Durchbruch kann also eine massive Effizienzsteigerung bringen. Wie erfindet man denn einen Algorithmus?

Algorithmenentwurf

Der Entwurf und die Analyse eines Algorithmus gehen meist Hand in Hand. Manchmal braucht man wirklich einen genialen Einfall, häufiger ist der Algorithmenentwurf aber eine sehr systematische, nachvollziehbare Sache. Ein Beispiel dazu:

Beispiel: Finde den Star

Stell dir vor du sitzt in einem SOI-Workshop und wartest bis Niklaus Wirth reinkommt. Wer ist Niklaus Wirth? Niklaus Wirth ist der einzige Schweizer Turing-Preisträger (der Nobelpreis der Informatik) und der Erfinder der Programmiersprache Pascal.

Ist die Niklaus Wirth schon im Saal? Wer kennt ihn überhaupt? Ihr solltet ihn alle kennen. [3] Wir wollen also Niklaus Wirth oder einen anderen Star unter uns finden. Was ist ein Star? Und wie finden wir ihn?

Definition: Star
  • alle kennen ihn/sie
  • er/sie kennt keine/n

Als elementare Operation betrachten wir eine Frage an Person A der Form “Kennst du Person B?”. Die Antwort ist Ja oder Nein. Andere Fragen erlauben wir nicht. Wie stellen wir diese Fragen in einem Raum mit \(n\) Personen am besten?

  • Kann es sein, dass es keinen Star gibt? Ja, z.B. wenn jeder jeden kennt.
  • Kann es sein, dass es genau einen Star gibt? Ja, z.B. wenn eben Niklaus Wirth drin sitzt, denn uns kennt er vermutlich nicht.
  • Kann es sein, dass es mehr als einen Star gibt? Nein! Warum erfährst du in Fussnote [4].

Wir wollen also die Anzahl Fragen minimieren.

Ein naives Verfahren: Jeden über jeden ausfragen braucht \(n \cdot (n-1)\) Fragen. Wir füllen das komplette Tableau mit Ausnahme der Diagonale (jeder kennt sich selbst):

A  B Anna Bettina Carla
Anna
Ja Nein
Bettina Nein
Nein
Carla Ja Ja

Wie finden wir nun den Star in dieser Tabelle? Wir suchen eine Person, sodass ihre Spalte nur Ja enthält (alle kennen sie) und ihre Zeile nur aus Nein besteht (sie kennt niemanden). Im Beispiel ist also Bettina der Star.

Wenn wir alle \(n(n-1)=n^2-n\) möglichen Fragen stellen, können wir also entscheiden, ob es einen Start gibt und ihn auch finden. Beim Entwerfen von Algorithmen wollen wir immer möglichst effizient sein, also möglichst wenige Fragen stellen. Können wir auch einen Star finden oder mit Sicherheit sagen, dass es keinen Star gibt ohne jede mögliche Frage zu stellen? Wieviele Fragen brauchen wir mindestens? Sei dazu \(F(n)\) die Anzahl Fragen, die wir bei \(n\) Personen stellen. Bis jetzt ist also \(F(n) = n^2-n\). Für \(n=1000\) brauchen wir also \(999'000\) Fragen. Das wollen wir nun auf lediglich \(2996\) Fragen reduzieren.

Dazu versuchen wir es mit Induktion: Induktion heisst nichts anderes als zuerst nur ein paar wenige Leute zu befragen und dann eine Person nach der anderen hinzuzunehmen. Die einfachsten Fälle sind \(n=1\) mit \(F(1)=0\) (eine einzelne Person ist ein Star) und \(n=2\). Mit zwei Personen können wir die Aufgabe immer mit zwei Fragen lösen: Wir schreiben \(F(2) = 2\). Für mehr als zwei Personen: Wir schicken jemanden raus, bestimmen mit dem gleichen Verfahren den potentiellen Star im Rest und holen die rausgeschickte Person wieder rein. Für diese Person müssen wir schauen, ob sie ein Star ist oder bestätigen, dass der Star von vorhin immer noch einer ist. Das kann bis \(2(n-1)\) Fragen kosten. Das kann man so hinschreiben:

\begin{equation*} F(n) = 2(n-1)+F(n-1) = 2(n-1) + 2(n-2) +...+2 = n(n-1) \end{equation*}

Wir haben also leider nichts gespart und stellen immer noch etwa \(n^2\) viele Fragen. Wir haben aber ein neues Konzept angewandt: Wir benutzen das gleiche Lösungsverfahren auf einer Teilmenge der Personen immer und immer wieder. Das nennt man Rekursion (vom lateinischen “zurücklaufen”).

Wieso sparen wir keine Fragen? Da es sein kann, dass die rausgeschickte Person ein Star ist, brauchen wir viele Fragen, wenn sie wieder reinkommt. Können wir garantieren, dass wir nicht den Star rausschicken? Hier kommt der Trick: Wenn wir A nach B fragen gibt es zwei Fälle: Wenn A B kennt ist A kein Star, falls A B nicht kennt, dann ist B kein Star. In beiden Fällen finden wir also eine Person, die kein Star ist und können diese Person vor die Tür schicken. (Ob die andere Person ein Star ist oder nicht, wissen wir noch nicht.) So können wir mit nur einer Frage immer einen Nicht-Star rausschicken. Dieses “Nicht-Star-Rausschicken” wiederholen wir bis nur noch eine Person übrig bleibt. Diese letzte Person müssen wir dann genauer ausfragen, denn sie könnte potentiell ein Star sein, muss aber nicht. Dazu holen wir nun eine Person nach der anderen wieder ins Zimmer und fragen sie, ob sie den Starkandidaten kennt und umgekehrt. Bei jeder Person die wieder reinkommt, können wir also den potentiellen Star mit nur zwei Fragen überprüfen. Das ist cool, oder?

Um die genaue Anzahl Fragen \(F(n)\) für \(n\) Personen auszurechnen ist ein wenig Rechnerei nötig. Falls du das im Mathematikunterricht noch nicht gesehen hast, kein Problem. Du kannst dir einfach merken, dass wir mit \(3n\) Fragen auskommen: für jede Person ausser dem Star investieren wir drei Fragen, eine beim Rausschicken und zwei beim Reinholen. Für \(1000\) Leute genügen also \(3000\) Fragen. Für die Super-Interessierten unter euch gibt es ganz am Ende den mathematischen Beweis im Anhang.

Wir fassen zusammen: Zuerst benötigten wir \(n\cdot(n-1)\) Fragen. Aber nachdem wir genau hinschauten, um herauszufinden, haben wir ein viel schnelleres Verfahren mit nur \(3n\) Fragen gefunden. Das Verfahren ist so schnell, dass wir nur einen kleinen Bruchteil aller möglichen Fragen stellen müssen.

Denksportaufgabe: Geht es besser?

Kostenmodell

Für Probleme, die wir mit dem Computer lösen wollen, ist die elementare Operation nicht “eine Frage stellen” sondern eher Dinge wie eine Zahl einlesen, zwei Zahlen vergleichen, Werte zuweisen etc. Das sind alles simple Operationen. Weiter ins Detail, auf die Ebene der einzelnen Bits und Bytes, wollen wir in der Informatikolympiade meist nicht gehen. Wie lange eine einzelne Addition zweier (kleiner) Zahlen effektiv dauert hängt von vielen Faktoren ab: der Taktzahl unserer CPU, der Effizienz des Compilers, die Ausnutzung des Cache-Speichers, der Wahl der Programmiersprache usw. Der Einfachheit halber, nehmen wir an, dass jede dieser Operationen einem einzelnen gleichgrossen Schritt entspricht und nennen dies das Einheitskostenmodell. Als erste Idee wollen wir also konstante Faktoren der Zeitunterschiede der Operationen ignorieren.

Das steht im Gegensatz zu unserem Beispiel am Anfang, wo eine Multiplikation zweier Zahlen mehrere Operationen bedeutete. Für beliebig lange Zahlen (oft BigInts genannt) ist nicht mehr realistisch, anzunehmen sie in einem Schritt multiplizieren zu können. Da macht es Sinn die einzelnen Stellen und die Operationen damit zu betrachten. Im “Normalfall” sind die meisten Zahlen mit denen wir zu tun haben aber von “vernünftiger” Grösse, z.B. höchstens ein paar Milliarden. Solche Zahlen können auf heutigen CPUs tatsächlich in einem einzigen Schritt multipliziert werden, weshalb die Einheitskostenannahme da sehr sinnig ist. Wenn wir nichts anderes sagen, dann analysieren wir an der SOI immer mit dem Einheitskostenmodell. Wir nehmen also an, dass der Aufwand für arithmetische Operationen unabhängig von der Grösse der Operanden ist.

Die zweite Idee ist, dass wir uns nur für grosse Eingaben interessieren, bei denen der Algorithmus lange läuft. Denn bei kleinen Eingaben ist auch ein naiver Algorithmus vernünftig schnell.

Wenn wir zwei Algorithmen miteinander vergleichen wollen, dann ist derjenige besser, der auf grossen Eingaben schneller läuft. Um das mathematisch präzise zu beschreiben, machen wir Vereinfachungen: Konstante Faktoren und Verschiebungen wollen wir weglassen. Eine lineare Wachstumskurve mit Steigung \(1\) erachten wir als gleich schnell wie eine Kurve mit Steigung \(20\). Damit wollen wir kompensieren, was wir uns mit dem Einheitskostenmodell eingehandelt haben, denn bereits da drin verstecken wir ja schon konstante Faktoren.

Intuitive O-Notation

Was heisst das nun konkret? Wenn wir ein Programm vor uns haben das bei einer Eingabe der Grösse \(n\) folgende Anzahl Schritte durchführt: \(5n^3 + 2n^2 + 8n + 50\), dann interessiert uns bei einem solchen Polynom nur der Summand mit der höchsten Potenz, also \(5n^3\), denn alles andere ist im Vergleich dazu für grosse \(n\) verschwindend klein. Ausserdem interessieren uns ja keine konstanten Faktoren, also vereinfachen wir \(5n^3\) zu \(n^3\). Kompakt hinschreiben können wir das mit der \(\mathcal{O}\)-Notation:

Wir schreiben:

\(3n^3 + 2n^2 + 8n + 50 \in \mathcal{O}(n^3)\)

und lesen das als:

Ein Programm mit \(3n^3 + 2n^2 + 8n + 50\) Schritten läuft asymptotisch höchstens so langsam wie ein Programm mit \(n^3\) Schritten.

Für Polynome interessiert uns als nur die höchste Potenz. Häufige andere Funktionen, die dir begegnen werden: Logarithmen sind schneller (= ergeben schnellere Programme = wachsen langsamer) als Wurzeln, Wurzeln sind schneller als Polynome und Polynome sind schneller als Exponentialfunktionen.

Formale O-Notation

Diese “Oh-Notation” kann man auch mathematisch formal definieren. Wenn dich das nicht interessiert, überspring einfach diesen Abschnitt.

Dazu definieren wir eine Menge von Funktionen, die auch nicht schneller wachsen als eine Wachstumsfunktion \(g: \mathbb{N} \rightarrow \mathbb{N}\). Wir schreiben dies mit einem grossen, kalligraphischen ‘O’, als

\(\mathcal{O}(g) = \{f: \mathbb{N} \rightarrow \mathbb{N}, \exists c_1, c_2: \forall n: f(n) \leq c_1 + c_2 \cdot g(n) \}\).

Wir sagen:

Alle Funktionen \(f\) in \(\mathcal{O}(g)\) wachsen asymptotisch nicht schneller als \(g\).

Damit können wir nun Dinge vereinfachen wie: \(3n-4 \in \mathcal{O}(n)\) indem wir z.B. als \(c_1 = 0\) und \(c_2 = 3\) wählen. Meistens sind wir also zufrieden wenn wir sagen können

Die Suche nach einem Star dauert \(\mathcal{O}(n)\) Fragen.

oder

Wir finden den Star in linearer Zeit.

Die genaue Anzahl Fragen (dieses \(F(n) = 3n-4\) was wir oben gezeigt haben) interessiert uns meistens gar nicht.

Die beiden Konstanten in der Definition erlauben es uns also die eine Funktion gegenüber der anderen zu skalieren und zu verschieben.

Da man früher keine \(\in\) Zeichen schreiben konnten, hat man häufig \(3n-4 = \mathcal{O}(n)\) geschrieben, korrekt ist aber schon die \(\in\) Notation, denn \(3n-4\) ist nur eine der vielen Funktionen, die in der Menge \(\mathcal{O}(n)\) enthalten sind.

Anwendungen der O-Notation

Nun kann man das selbe auch machen mit “mindestens so schnell wachsend” als Klasse \(\Omega(g)\). Oder als “weniger schnell wachsend” mit klein-O also \(o(g)\).

Ist eine Funktion \(f\) sowohl in \(\mathcal{O}(g)\) also auch in \(\Omega(g)\), sagen wir dass \(f\) und \(g\) asymptotisch gleich schnell wachsen und schreiben \(f \in \Theta(g)\). Zum Beispiel gilt \(3n-4 \in \Theta(n)\).

An diese asymptotische Notation muss man sich etwas gewöhnen. In der Algorithmik ist sie allgegenwärtig und wir werden ihr bei jedem SOI-Thema wieder begegnen. Lass dich aber dadurch nicht abschrecken. Die häufigsten Dinge, die du sehen wirst sind diese hier:

  • \(\mathcal{O}(n)\): lineare Laufzeit (z.B. für den schnellen Star-Algorithmus)
  • \(\mathcal{O}(n^2)\): quadratische Laufzeit (z.B. für den Star-Algorithmus der alle Fragen stellt)
  • \(\mathcal{O}(\log n)\): logarithmische Laufzeit (z.B. für binäre Suche)
  • \(\mathcal{O}(n \log n)\): leicht super-lineare Laufzeit (z.B. für Sortieralgorithmen)

Wo sind wir?

Wir haben bis jetzt gesehen, wie wir Algorithmen entwerfen und analysieren wollen. Wir haben ein Analysemodell gesehen, das sehr grob ist: Einen Algorithmus, der \(2n\) Schritte braucht, betrachten wir als gleich schnell wie einen der \(10'000n+10^6\) Schritte braucht. Das ist natürlich sehr ungenau, aber der durchschlagende Erfolg der Algorithmik beruht darauf, dass diese Analyse oft sehr gut funktioniert. Und wenn man die Eingabegrössen gross genug wählt (und heutige Eingabegrössen sind oft riesig), dann ist \(\mathcal{O}(n)\) immer schneller als \(\mathcal{O}(n^2)\), egal wie gross die versteckte Konstante ist.

Wir wollen jetzt erneut Algorithmen für ein neues Problem entwerfen, die “gut” sind. Wie misst man denn die Qualität von Algorithmen?

  • Korrektheit: Macht das Programm, was es soll? Wir machen das meist relativ informell.
  • Effizienz: Zeit und Platz: Wie lange läuft der Algorithmus und wieviel Speicher verbraucht er dabei?
  • Qualität der Lösung: Wie nahe kommen wir an das Optimum? Das haben wir bisher noch nicht gesehen. Daher ein Beispiel dazu:

Beispiel Maximum Subarray

Betrachten wir folgende \(n=14\) Zahlen

5 7 12 -48 9 36 -17 22 11 -49 49 -49 111 -117

Aus diesen Zahlen wollen wir ein Teilstück, ein Intervall, extrahieren, sodass die Summe darin maximal wird. Für so kleine Eingaben wie das Beispiel oben können wir problemlos alle Teilintervalle ausprobieren, doch für \(n=10^6\) kann dies lange dauern.

Wir können das auch als Aktienkurs anschauen. Dann seien die Zahlen die Tagesänderungen und wir fragen uns im Nachhinein: Wann hätten wir am besten kaufen und wieder verkaufen sollen, um unseren Profit zu maximieren?

Erste naive Lösung

Hier eine Pseudocode-Implementierung eines Algorithmus, der einfach alles ausprobiert. Sei dabei d[k] die \(k\)-te Zahl der Eingabe, also die Kursänderung am Tag \(k\).

for i = 1 to n do
    for j = i to n do
        S := 0
        for k = i to j do
            S := S + d[k]
        merke maximales S

Wir betrachten also jedes mögliche Intervall \([i,j]\) und berechnen die entsprechende Summe \(S\). Wie lange läuft dieser Algorithmus?

Maximale Laufzeit: Zählen wir die Anzahl Additionen sehr grosszügig: Jede Schleife wird maximal \(n\) mal ausgeführt. Da die Schleifen ineinander verschachtelt sind, nehmen wir das Produkt, also \(n\cdot n\cdot n = n^3\) in \(\mathcal{O}(n^3)\).

Doch ist dieser Algorithmus wirklich so langsam oder haben wir einfach viel zu grob abgeschätzt? Schätzen wir die Laufzeit mal noch konservativ ab, zählen also eher zu wenig Additionen. Nehmen wir dazu nun an, dass sich der Anfang des Intervalls \(i\) nur im ersten Drittel des Arrays bewegt und das Ende des Intervals \(j\) nur im letzten Drittel des Arrays. Dann gilt für jedes Paar \(i,j\), dass \(k\) mindestens \(\frac{n}{3}\) Werte annimmt. Insgesamt benötigen wir also auch unter dieser Annahme mindestens \(\frac{n^3}{27}\) Schritte also in \(\Omega(n^3)\).

Da wir die selbe, kubische untere und obere Schranke gezeigt haben, können wir also sagen, dass die Laufzeit unseres Algorithmus in \(\Theta(n^3)\) liegt. Das ist nicht besonders schnell und wohl höchstens für ein paar hundert Börsentage praktikabel.

Wir haben also ein Programm das korrekt ist, aber wir hätten gerne ein schnelleres. Da stellt sich die Frage: Was machen wir zuviel hier? Berechnen wir etwas das wir gar nicht müssten oder berechnen wir mehrmals das gleiche? Wenn wir unserem Algorithmus bei der Arbeit “zuschauen” fällt auf, dass er immer wieder das gleiche macht. Er summiert die Zahlen von \(i\) bis \(j\) und im nächsten Schritt von \(i\) bis \(j+1\). Dabei werden nahezu die gleichen Zahlen summiert, im nächsten Schritt kommt einfach noch eine einzige neue Zahl dazu. Können wir die Summe der Zahlen von \(i\) bis \(j\) nicht schneller bestimmen?

Lösung mit Präfixsummen

Es genügt, lediglich alle Präfixsummen zu berechnen: Ein Präfix ist ein Anfangsstück einer Sequenz. Der Präfix der Länge \(i\) unserer Eingabe sind also einfach die ersten \(i\) Zahlen.

Wir berechnen für jede Position \(i\) die Summe \(S_i\) = Summe der Zahlen bis und mit Position \(i\). All diese \(S_i\) Werte können wir für aufsteigende \(i\) in linearer Zeit, also in \(\mathcal{O}(n)\), berechnen: Denn um eine Präfixsumme \(S_i\) zu berechnen, genügt es die \(i\)-te Zahl zur bereits berechneten Summe \(S_{i-1}\) dazu zu addieren. Danach ist die Summe von i bis j einfach \(S_j - S_{i-1}\).

Wir können uns nun die innerste Schleife sparen:

// Berechne die Präfixsummen in O(n)
S[0] := 0
for i := 1 to n do
    S[i] := S[i-1]+d[i]
// Bilde die Summe für jedes Interval in O(n^2)
for i := 1 to n do
    for j := i to n do
        S := S[j]-S[i-1]
        merke maximales S

Wie viel schneller sind wir damit? Das Vorberechnen der Präfixsummen geht in \(n\) Schritten. Danach können wir für jedes der \(\mathcal{O}(n^2)\) Intervalle in konstant vielen Schritten die Summe berechnen. Somit resultieren \(\mathcal{O}(n^2 + n) = \mathcal{O}(n^2)\) Schritte.

Teile und Herrsche (Divide-and-Conquer)

Sind wir jetzt zufrieden? \(\mathcal{O}(n^2)\) kann für viele reale Eingaben noch immer zu langsam sein. Doch anders als vorhin gibt es bei dieser Lösung nicht einen offensichtlich Engpass, den wir beheben können.

Um noch schneller zu werden, wollen wir nun noch einen weiteren Trick des Algorithmenentwurfs anschauen: Teile und Herrsche. Es ist eine mächtige Technik, die bereits die Römer kannten (lateinisch: divide et impera) – allerdings nicht im Zusammenhang mit Algorithmen sondern eher mit strenger Aussenpolitik.

Wie vorhin beim Star, versuchen wir eine induktive Lösung zu suchen. Hier werden wir nicht einfach ein Element wegnehmen (wie beim Star vorhin), sondern in der Mitte teilen:

Wir teilen unsere Zahlenfolge in zwei Teile. Wo kann die Lösung, d.h. das Teilintervall mit der grössten Zahlensumme, liegen? Wir unterscheiden drei Fälle: Entweder liegt das gesuchte Intervall genau in der linken Hälfte, genau in der rechten Hälfte, oder es enthält Teile der rechten und der linken Hälfte. Genau diese drei Fälle wollen wir anschauen und für jeden Fall das maximale Intervall berechnen. Dann müssen wir nur noch aus den drei Intervallen jenes mit der grössten Summe wählen.

Eine solche Strategie, die das Problem in kleinere Portionen aufteilt und diese separat löst und wieder zusammensetzt, nennt man “Divide and Conquer”. Hat uns diese Aufteilung hier was gebracht?

Die ersten beiden Fälle könne wir einfach behandeln, indem wir die entsprechende Hälfte separat betrachten und die Lösung (rekursiv mit dem gleichen Verfahren) berechnen. Wie können wir aber die Lösung für den dritten Fall berechnen? Wir suchen links das beste Teilstück, das am rechten Rand endet, und setzen es zusammen mit dem besten Teilstück im rechten Teil, das am linken Rand endet. Wir müssen also die Präfixsummen der rechten und die Suffixsummen der linken Hälfte betrachten. Wir haben bereits gesehen, dass diese in linearer Zeit berechnet werden können. Wir addieren also die maximale Präfixsumme der rechten Hälfte und die maximale Suffixsumme der linken Hälfte. So können wir die Lösung für den dritten Fall in linearer Zeit ausrechnen.

Divide-and-Conquer Algorithmus:
  • falls höchstens ein Element:
    • falls genau ein positives Element: nimm dieses Element
    • sonst: 0
  • falls mehrere Elemente:
    • teile in der Mitte
    • bestimme die optimalen Lösungen separat für die beiden Teile
    • bestimme die besten Randstücke links und rechts
    • wähle den besten der drei Lösungkandidaten

Analyse: Nun wollen wir die Laufzeit unseres Algorithmus analysieren, um zu sehen, ob wir überhaupt eine Verbesserung erzielen konnten. Das wird wieder etwas ein Rumgerechne - wenn du willst kannst du das ruhig überspringen und direkt bei der linearen Lösung weiterlesen. [5]

Wir schreiben \(T(n)\) für die Laufzeit mit \(n\) Elementen. Für den Fall, wo wir (unter Umständen mehrfach) Teillösungen berechnen, können wir die Laufzeit so hinschreiben

\begin{align} T(n) &= \text{teilen + linke Lösung + rechte Lösung + Randstücke bestimmen}\\ &= 1 + T\left(\frac{n}{2}\right) + T\left(\frac{n}{2}\right) + a' \cdot n\\ &\leq 2 \cdot T\left(\frac{n}{2}\right) + a \cdot n. \end{align}

Dabei sei \(a'\) eine Konstante, die beschränkt wie aufwändig das Bestimmen der Lösung über die Mitte ist, \(a = a'+1\) und für den Basisfall mit \(n=1\) sei \(T(1)=b\) für eine Konstante \(b\).

Wie löst man eine solche Rekursionsgleichung? Wir machen, was wir auch zuvor gemacht haben. Wir setzten ein paar Mal ein und schauen, ob wir ein Gefühl für die Lösung kriegen.

\(\begin{align} T(n) &= 2 \cdot T\left(\frac{n}{2}\right) + a \cdot n \\ &= 2 \cdot \left(2 \cdot T\left(\frac{n}{4}\right)+a \cdot \frac{n}{2} \right) + a \cdot n = 4 T\left(\frac{n}{4}\right) + 2an\\ &= 2 \cdot \left(2 \cdot \left(2 \cdot T\left(\frac{n}{8}\right)+a \cdot \frac{n}{4}\right)+a \cdot \frac{n}{2}\right) + a \cdot n = 8 T\left(\frac{n}{8}\right) + 3an\\ &...\\ &= 2^i T\left(\frac{n}{2^i}\right) + i \cdot a \cdot n \end{align}\)

Das hier endet falls \(n=2^i\) ist, also falls \(i = \log_2 n\), denn dann benutzen wir \(T(1)\) und die Rekursion endet. Also vermuten wir sowas wie \(T(n) = n\cdot b + a\cdot n\cdot \log n\), was dann \(T(n) \in \mathcal{O}(n \log n)\) bedeuten würde.

Doch stimmt das auch? Um es zu beweisen wollen wir nie die \(\mathcal{O}\)-Notation verwenden, denn essentiellen Konstanten in einer Rekursionsgleichung zu verstecken kann gefährlich sein.

Beweis mittels vollständiger Induktion: Zu beweisen: Es gibt \(c_1\) und \(c_2\), s.d. \(T(n) \leq c_1 n \log n + c_2\)

Induktionsanfang: Um \(T(1) \leq c_2\) zu erhalten, wähle \(c_2 \geq b\).

Induktionshyptohese (IH): Für \(T\left(\frac{n}{2}\right)\) wissen wir bereits, dass \(T\left(\frac{n}{2}\right) \leq c_1 \frac{n}{2} \log \left(\frac{n}{2}\right) + c_2\).

Induktionsschritt:

\(\begin{align} T(n) &\leq 2\cdot T\left(\frac{n}{2}\right) + a\cdot n \\ &\stackrel{\text{IH}}{\leq} 2\cdot \left(c_1\cdot \frac{n}{2}\cdot \log\left(\frac{n}{2}\right) + c_2\right) + a\cdot n\\ &= c_1\cdot n\cdot \log(n) - c_1 n + 2 c_2 + an \\ &\stackrel{!}{\leq} c_1\cdot n\cdot \log(n) + c_2 \underbrace{-c_1 n + c_2 + an}_{\stackrel{!}{\leq} 0} \end{align}\)

Können wir die letzte Ungleichung erfüllen? Wir haben noch etwas Spielraum, da wir \(c_1\) noch nicht fixiert haben. Welche Bedingung muss für \(c_1\) gelten?

\(\begin{align} -c_1 n + c_2 + an &\leq 0\\ (a-c_1) &\leq - \frac{c_2}{n}\\ \frac{c_2}{n} + a &\leq c_1 \end{align}\)

Wähle dazu z.B. \(c_1 = a+c_2\). Damit wissen wir, dass unser Divide-and-Conquer Algorithmus in Zeit \(\mathcal{O}(n\log n)\) läuft.

Lineare Lösung

Geht es noch besser? Nochmal von vorne: Versuchen wir nochmals eine Induktion von links nach rechts.

Als Bedingung, die immer gelten soll, nehmen wir an, dass wir nach dem \(i\)-ten Schritt die optimale Lösung für die ersten \(i\) Elemente kennen. Wenn wir nun das \((i+1)\)-te Element dazunehmen, dann wollen wir rasch herausfinden, ob dieses neue Element zum besten Interval gehört. Dazu merken wir uns für den Teil bis \(i\) nicht nur das Maximum sondern auch wieviel wir erreichen können, wenn wir am rechten Rand des aktuellen Präfixes, also bei Element \(i\), enden. Damit können wir dann leicht vergleichen, ob wir mit dem neuen Element ein neues Maximum erreichen können oder nicht.

Dazu brauchen wir, dass wenn wir bis Position \(i\) gekommen sind wir bereits folgende Dinge kennen:

  • das Maximum im Bereich \(1, \dots, i\),
  • das Maximum, das bei \(i\) endet.
randmax := 0
max := 0
for i = 1 to n do
    randmax := randmax + d[i]
    if randmax < 0 then randmax := 0
    if max < randmax then max := randmax

Dieses Verfahren ist super einfach zu implementieren und hat gar nur lineare Laufzeit! Also \(\mathcal{O}(n)\), super!

Untere Schranke

Nun werden wir ehrgeizig und wollen es noch besser machen. Schaffen wir \(\mathcal{O}(\sqrt n)\) oder gar \(\mathcal{O}(\log(n))\)? Oder geht es gar nicht besser?

Folgende Überlegung zeigt, dass wir nicht besser als linear sein können: Angenommen wir haben einen Algorithmus, der nicht jedes Element anschauen muss. Dann ist dieser nicht korrekt:

  • Berechnet der Algorithmus eine Lösung, die das nicht-angeschaute Element enthält, dann sei es einfach \(-\infty\). Wir hätte besser nichts genommen.
  • Enthält die Lösung das nicht-angeschaute Element allerdings nicht, dann sei es einfach \(\infty\), sodass es zwingend in der Lösung vorkommen sollte.

Demnach muss jeder korrekte Algorithmus alle Elemente mindestens einmal betrachten. Die Laufzeit liegt also in \(\Omega(n)\). Da dies nicht eine Eigenschaft eines spezifischen Algorithmus ist, sondern für alle Algorithmen gilt, die das MaxSubarray-Problem lösen sprechen wir von der Laufzeitkomplexität des Problems.

Die Grösse des Inputs ist nicht immer eine untere Schranke für die Laufzeit. Erinnern wir uns an das Star-Problem. Da war die Eingabegrösse quadratisch (jeder mit jedem), aber wir mussten nur linear viele Fragen stellen.

Hier noch ein paar Zusatzfragen (gleich mit den Antworten):

  • Wie finden wir das Interval (und nicht nur dessen Summe)? Antwort: Wir führen im Algorithmus immer die aktuellen Schranken von max und randmax mit und übergeben/aktualisieren diese bei jeder Änderung.
  • Wie sieht es mit dem Speicherverbrauch aus? Antwort: Wir unterscheiden zwei Speicherarten: Speicher der das Programm benötigt (inklusive der Eingabe) und wie viel Speicher wir zusätzlich benötigen während der Laufzeit. So haben beispielsweise der erste und der letzte Algorithmus nur konstanten Zusatzspeicher für die Werte S, randmax und max. Sobald wir aber beispielsweise alle Präfixsummen vorberechnen, wie im zweiten Algorithmus, so brauchen wir linearen, also \(\mathcal{O}(n)\), Zusatzspeicher. Bonusfrage: Wie viel Zusatzspeicher benötigt der Divide-and-Conquer-Algorithmus? [6]

So, das wär’s mit dem Crash-Kurs in Algorithmen-Entwurf und -Analyse. Falls du Fragen hast, dann melde dich bei mir (daniel@soi.ch) und ansonsten noch viel Vergnügen mit den anderen Skript-Kapiteln.

Anhang

Hier einige zusätzliche Beweise, die für das Verständnis des Kapitels nicht so wichtig sind.

Induktion der Staraufgabe

Die Funktion \(F(n)\) können wir so aufschreiben:

\begin{equation*} F(n) = \begin{cases} 2 & \text{für } n=2\\ 1 + F(n-1) + 2 & \text{für } n>2 \end{cases} \end{equation*}

Die beiden Fälle beschreiben, ob wir noch jemanden rausschicken oder nicht. Nun teleskopieren wir, setzen die Formel also ein paar mal ein und sehen was rauskommt:

\begin{align} F(n) &= 3 + F(n-1) = 3 + 3 + F(n-2) = 3+3+3+F(n-3)\\ &= \underbrace{3+\dots+3}_{\text{$n-2$ Mal}}+\underbrace{F(2)}_{=2} \\ &= 3(n-2) + 2 = 3n-4 \end{align}

Um formal zu zeigen, dass \(F(n)=3n-4\) gilt, beweisen wir es durch vollständige Induktion:

  • Vermutung: \(F(n)\) = \(3(n-1)-4\)
  • Induktionsanfang: \(F(2)\) = \(2\)
  • Induktionsschritt: \(F(n) = 3 + F(n-1) = 3 + 3(n-1) -4 = 3n-4\)
[1]oder politisch korrekt: Traveling Salesperson Problem
[2]Die Grösse des beobachtbaren Universums ist etwa \(2^{80}\) Kilometer (Quelle: Wolfram Alpha). Der Weltrekord für das Falten von Papier liegt bei \(13\) Mal. 2002 hat die Maturandin Britney Gallivan ein Stück Papier zwölf mal gefaltet. Selbst dazu war schon eine Klopapierrolle von über einem Kilometer Länge nötig [Details]. Seither gab es mehrere Versuche den Rekord zu brechen. 2012 hat es eine Gruppe Schüler am MIT geschafft \(13\) mal zu falten [Artikel] und auch ein Team der BBC hat sich daran versucht [Video].
[3]Mehr über ihn in der Wikipedia.
[4]Gäbe es zwei Stars, so müsste der eine den anderen kennen, damit den anderen alle kennen und dieser damit ein Star sein kann. Der eine kennt dann aber nicht keinen und ist daher per Definition kein Star, weil er den anderen kennt. Verwirrt?
[5]Spoiler: Es kommt \(\mathcal{O}(n \log n)\) raus.
[6]Geschickt implementiert ist ein Aufruf mit \(\mathcal{O}(1)\) Zusatzspeicher machbar und die Rekursionstiefe beträgt maximal \(\log n\), also Zusatzspeicher in \(\mathcal{O}(\log n)\).