Aufwand und Komplexität

Das vorige Kapitel hat dir fünf Sortierverfahren gezeigt, und am Ende lagen die Zahlen jedes Mal in derselben Reihenfolge. Wenn alle fünf dasselbe leisten — warum gibt es dann fünf?

Irgendwer muss sich schließlich für eines entscheiden: die Entwickler:in, die eine Musik-App schreibt, oder die Lehrer:in, die eine Klassenliste ordnet. Woran macht sie das fest? Solange niemand sagen kann, worin sich die Verfahren überhaupt unterscheiden, bleibt nur Geschmack.

Man müsste sie vergleichen können. Genau darum geht es hier: erst suchen wir, was man an einem Verfahren sinnvollerweise misst, dann messt ihr eure Verfahren selbst, und am Ende bekommen die Kurven, die dabei herauskommen, einen Namen.

„Schneller" ist kein Maß

Auf einem neuen Rechner ist jedes Verfahren schneller, und das sagt über das Verfahren nichts aus. Sekunden messen also die Maschine, nicht den Algorithmus.

Man zählt deshalb Arbeitsschritte — und zwar nicht alle, sondern nur die, auf die es ankommt.

Elementaroperation

Eine Elementaroperation ist der Arbeitsschritt, den man bei der Bewertung eines Algorithmus zählt, weil er den Aufwand bestimmt. Welcher das ist, hängt vom Anwendungsfall ab: beim Sortieren meist der Vergleich oder der Tausch.

Ist ein Tausch teuer, weil ganze Datensätze bewegt werden, zählt man Tausche. Ist der Vergleich teuer, weil lange Texte verglichen werden, zählt man Vergleiche.

Aufgabe

1. Nebeneinanderlegen. Ihr habt im Team für alle drei einfachen Verfahren Vergleiche und Tausche notiert. Tragt die Zahlen in eine gemeinsame Tabelle ein.
2. Entscheiden. Welches Verfahren würdet ihr wählen, wenn ein Vergleich billig und ein Tausch teuer ist? Und welches, wenn es umgekehrt ist? Begründet eure Antwort mit euren Zahlen.

Die Messreihe

Fünf Zahlen von Hand zu sortieren zeigt, wie ein Verfahren arbeitet. Wie viel Arbeit es macht, zeigt sich erst, wenn die Mengen wachsen — und so viele Zahlen denkt sich niemand aus.

Hier bekommst du sie:

Anzahl

Messreihe:

zahlen = [199, 39, 819, 537, 588, 869, 669, 921, 999, 27]

Gezählt wird diesmal der Vergleich, und zwar bei allen vier Verfahren. Quick-Sort tauscht überhaupt nicht, und Selection-Sort tauscht genau einmal je Position — an den Tauschen allein ließe sich also nicht ablesen, wie viel Arbeit die vier machen.

Vier Verfahren, vier Kurven

1. Editor öffnen. Diese Aufgabe steht in keinem Rahmen auf dieser Seite — hier schreibst du zum ersten Mal in einem eigenen Editor. Öffne python.jetzt in einem neuen Tab; das genügt und läuft im Browser, ohne dass du etwas installierst. Wer Thonny auf dem Rechner hat, nimmt das. Vor dir liegt dann ein leeres Blatt: Diesmal steht nichts da, was du nur zu ergänzen hättest.
2. Aufteilen. Ihr arbeitet zu viert. Jede Person übernimmt eines der vier vergleichenden Verfahren aus dem vorigen Kapitel: Bubble-Sort, Insertion-Sort, Selection-Sort oder Quick-Sort. Proxmap-Sort bleibt diesmal außen vor. Tippe dein Verfahren im Editor ab oder kopier es von dort herüber.
3. Zählen lassen. Leg eine Variable vergleiche = 0 an und schreib in dein Verfahren an jede Stelle, an der zwei Zahlen verglichen werden, ein vergleiche = vergleiche + 1. Am Ende gibst du sie mit print(vergleiche) aus. Von Hand mit Strichen kommst du hier nicht weit — bei 40 Zahlen sind es mehrere hundert.
4. Messen. Hol dir oben 10 Zahlen, kopier die Zeile in dein Programm und lass es laufen. Danach dasselbe mit 20 und mit 40 Zahlen. Notiere jedes Mal, wie viele Vergleiche herauskamen.
5. Zeichnen. Trag deine Messwerte in ein Koordinatensystem ein: waagerecht die Anzahl der Zahlen, senkrecht die Vergleiche. Verbinde sie zu einer Kurve.
6. Zusammenlegen. Zum Schluss zeichnet ihr alle vier Kurven in ein gemeinsames Koordinatensystem, mit derselben Einteilung für alle.

Vor euch liegen jetzt vier Kurven. Bevor ihr sie deuten könnt, braucht ihr Namen für die Formen, die es überhaupt gibt.

Komplexität: wie die Arbeit wächst

Wie viel Arbeit ein Algorithmus macht, ist keine einzelne Zahl. Es ist die Antwort auf eine Frage, die man immer wieder stellen kann: Was passiert, wenn ich doppelt so viele Daten nehme? „Doppelt so viel Arbeit" ist etwas völlig anderes als „viermal so viel Arbeit" — und dieser Unterschied bleibt bestehen, ganz gleich, auf welchem Rechner das Verfahren läuft. Wie die Arbeit mit der Datenmenge wächst, nennt man die Komplexität eines Algorithmus.

Formen, in denen Arbeit wachsen kann, gibt es viele. Drei davon begegnen dir immer wieder, und alle drei kennst du aus dem Mathematikunterricht: die flach auslaufende Logarithmuskurve, die Gerade und die Parabel. Abgekürzt schreibt man sie mit einem großen O und der Rechenvorschrift dahinter; das n darin steht für die Anzahl der Daten.

Logarithmisch — O(log n)

Der Logarithmus zählt Halbierungen: Aus 1000 werden 500, dann 250, dann 125 — nach zehn Schritten bist du bei 1. Die Kurve steigt am Anfang steil an und wird danach immer flacher.

Doppelt so viele Daten kosten nur einen einzigen Schritt mehr. Besser kann es nicht laufen; so arbeitet die Suche in einer sortierten Liste.

Linear — O(n)

Eine Gerade. Der Aufwand ist ein festes Vielfaches der Menge, jedes Element kostet gleich viel.

Doppelt so viele Daten kosten doppelt so viel Arbeit.

Quadratisch — O(n²)

Die Normalparabel. Sie beginnt harmlos und wird dann sehr schnell sehr steil.

Doppelt so viele Daten kosten viermal so viel Arbeit, zehnmal so viele hundertmal so viel.

Warum vor der Kurve kein Faktor steht

Ein Verfahren, das n² Schritte braucht, und eines, das n² geteilt durch vier Schritte braucht, heißen beide O(n²). Der Faktor fällt weg, weil er über das Wachstum nichts aussagt: Ein doppelt so schneller Rechner halbiert die Zeit ebenfalls und macht aus einer Parabel trotzdem keine Gerade.

Die O-Schreibweise ist deshalb gröber, als sie aussieht. Sie nennt die Form, nicht die Zahl. Zwei Verfahren derselben Form können sich in der Praxis um ein Vielfaches unterscheiden.

Hochrechnen

Ein quadratisches Verfahren braucht n² Elementaroperationen. Dein Rechner schafft ungefähr 100 Millionen davon pro Sekunde.

1. Rechne aus, wie lange ein solches Verfahren für 1000, für 100 000 und für 1 000 000 Zahlen bräuchte.
2. Vergleiche die drei Zeiten miteinander. Um welchen Faktor wächst die Menge, um welchen die Zeit?

Nach oben hört es mit der Parabel nicht auf. Es gibt Aufgaben, bei denen jedes einzelne zusätzliche Element den Aufwand verdoppelt — O(2ⁿ) — oder ihn mit der Anzahl multipliziert — O(n!). Solche Kurven verlassen nach wenigen Schritten jedes Blatt Papier, und gegen sie hilft auch der schnellste Rechner nichts mehr; davon handelt das nächste Kapitel. Vorher aber gehört deine eigene Kurve eingeordnet — die Zahlen dafür liegen längst vor dir.

Ordne deine Kurve ein

Vergleiche deine Kurve mit den drei Formen aus diesem Abschnitt und ordne sie der nächstgelegenen zu.