Die Kosten eines Algorithmus

Operationen zählen

Die zweite Frage

Die Lektionen Korrekte Schleifen entwerfen und Rekursion haben gelehrt zu beweisen, dass ein Algorithmus korrekt ist: dass er terminiert und dass sein Ergebnis die Nachbedingung erfüllt. Nun hat die Lektion Numerische Algorithmen zwei gleichermaßen korrekte Primzahltests gezeigt, einen mit etwa $n$ Divisionen und einen mit etwa $\sqrt{n}$, und die Lektion Rekursion zwei korrekte Arten, $F_{30}$ zu berechnen, eine mit $2\,692\,537$ Aufrufen und eine mit 29 Additionen. Wenn dem so ist, genügt die Korrektheit nicht, um zu wählen: Von zwei korrekten Algorithmen kann der eine im Nu antworten und der andere nicht fertig werden, bevor die Antwort ihre Bedeutung verloren hat. Die zweite Frage, die man an einen Algorithmus richtet, lautet daher: Was kostet er?

Die Kosten ließen sich mit einer Uhr messen, und der vierte Teil der Lektion wird das tun. Aber die Zeit einer Ausführung hängt von der Maschine ab, vom Compiler, von seinen Optionen und davon, was der Computer gleichzeitig sonst noch tut; aus ihr folgt nichts über den Algorithmus auf einer anderen Maschine. Was von alledem nicht abhängt, ist die Anzahl der Schritte, die der Algorithmus macht. Daraus folgt die erste Entscheidung dieser Lektion: die Kosten durch Zählen messen und die Uhr für die Kontrolle der Zählung aufheben.

Die Größe und die dominante Operation

Alle Schritte zu zählen (jede Addition, jeden Vergleich, jedes Erhöhen des Index, jeden Speicherzugriff) wäre mühsam und nutzlos, weil fast alle einen Hauptschritt in festem Verhältnis begleiten. Man wählt daher die dominante Operation: diejenige, die bis auf einen konstanten Faktor mindestens so oft ausgeführt wird wie jede andere und deshalb alle vertritt. Beim Summieren der Elemente eines Vektors ist es die Addition; bei der Suche nach einem Maximum der Vergleich; bei einem Primzahltest die Division. Wie oft sie ausgeführt wird, drückt man in Abhängigkeit von der Eingabegröße aus, die man $n$ nennt: der Anzahl der Elemente des Vektors, der Zahl, die man testet, der Anzahl der Ziffern.

Eine einfache Schleife, die einen Vektor von $n$ Elementen durchläuft und mit jedem eine feste Menge Arbeit verrichtet, führt ihre dominante Operation $n$-mal aus. Das Maximum eines nichtleeren Vektors dagegen beginnt mit dem ersten Element als Kandidaten und vergleicht jedes der übrigen: $n - 1$ Vergleiche. Der Unterschied zwischen $n$ und $n - 1$ ist real, ändert aber, wie der dritte Teil der Lektion zeigen wird, nichts an dem, worauf es ankommt.

Der schlechteste Fall

Manche Algorithmen führen bei Daten derselben Größe nicht immer gleich viele Operationen aus. Die Suche nach einem Wert in einem Vektor, den man durchläuft, bis man ihn findet, braucht einen einzigen Vergleich, wenn der Wert an der ersten Position steht, und $n$, wenn er fehlt. Um von ihren Kosten zu sprechen, wählt man eine der beiden Situationen, und die übliche Wahl ist der schlechteste Fall: die größte Anzahl von Operationen über alle Eingaben der Größe $n$. Der Grund ist derselbe, aus dem ein Vertrag für alle Eingaben geschrieben wird, die die Vorbedingung erfüllen: Der schlechteste Fall ist eine Garantie, der beste Fall eine Hoffnung. Die lineare Suche kostet also $n$ Vergleiche im schlechtesten Fall, und wenn diese Lektion ohne Zusatz „die Kosten“ sagt, meint sie die des schlechtesten Falls.

Verschachtelte Schleifen

Die Lektion Schleifen hat gelehrt, die Durchläufe zweier verschachtelter Schleifen zu zählen. Macht die innere stets $m$ Durchläufe für jeden der $n$ der äußeren, so wird der innere Rumpf $n \cdot m$-mal ausgeführt. Hängt die innere von der äußeren ab, summiert man Zeile für Zeile. Der Fall, der bei der Arbeit mit Sammlungen am häufigsten vorkommt, ist der von allen Paaren: jedes Element mit jedem der folgenden vergleichen, etwa wenn man prüft, ob ein Vektor Wiederholungen enthält.

#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} Vergleiche; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}

n =     10:         45 Vergleiche; n(n - 1)/2 = 45n =    100:       4950 Vergleiche; n(n - 1)/2 = 4950n =   1000:     499500 Vergleiche; n(n - 1)/2 = 499500n =  10000:   49995000 Vergleiche; n(n - 1)/2 = 49995000

Der Zähler steht an der Stelle des Vergleichs, den der wirkliche Algorithmus machen würde. Im Durchlauf $i$ der äußeren Schleife läuft die innere von $i + 1$ bis $n - 1$ und macht $n - 1 - i$ Durchläufe; die Gesamtzahl ist also $(n - 1) + (n - 2) + \cdots + 1 + 0$, die Summe aus der Lektion Schleifen:

Die Ausgabe bestätigt die Formel für jede Größe. Der Zähler ist long long, weil ab einem $n$ von etwa fünfundsechzigtausend die Anzahl der Paare das Maximum von int (auf dieser Plattform 32 Bit) übersteigt, und die Formel multipliziert aus demselben Grund erst nach der Umwandlung: Der Zähler eines quadratischen Algorithmus läuft lange vor den Daten über.

Schon hier sieht man, was der dritte Teil der Lektion verallgemeinern wird: Multipliziert man $n$ mit 10, so multiplizieren sich die Vergleiche mit rund 100. Bei zehn Elementen 45 Vergleiche; bei zehntausend fast fünfzig Millionen.