Wie lange läuft dieses Sortierprogramm? Möglicherweise dauert es bei großen Eingaben (d. h. viele Strings) sehr lange, bis das Programm mit der Sortierung fertig ist und sich wieder zurückmeldet. Manchmal ist es sinnvoll, schon vor dem Start abschätzen zu können, wie lange das Programm laufen wird. Niemand wird jahrelang auf das Sortieren eines Telefonbuches warten wollen! Offenbar ist die Laufzeit abhängig von der Anzahl n der zu sortierenden Strings. Können wir für die Laufzeit eine Formel in Abhängigkeit von n finden?

Sehen wir uns das Programm genau an, so stellen wir fest, dass es aus zwei ineinander geschachtelten for-Schleifen besteht. In beiden laufen die Laufvariablen von 0 bis n, doch die innere Laufvariable startet erst dort, wo die äußere gerade steht. Im Inneren der beiden Schleifen befinden sich ein if mit einem Vergleich und einige eventuell durchgeführte Zuweisungen. Ein gutes Maß für die Laufzeit ist die Anzahl der durchgeführten Vergleiche.^[11] In der ersten Iteration finden n Vergleiche statt, in der zweiten n-1, dann n-2, dann n-3 usw. Insgesamt werden also 1+2+...+n Vergleiche durchgeführt. Nach der bekannten Gauß'schen Summenformel sind das genau 1/2·(n-1)·n Vergleiche. Abbildung 2.8 veranschaulicht dies. Die gerasterte Fläche entspricht der Anzahl der durchgeführten Vergleiche. Offenbar entspricht sie ca. der halben Fläche eines Quadrates mit der Seitenlänge n. Sie beträgt also ungefähr 1/2·n².

Abbildung 2.8. Laufzeitanalyse von Sortieren durch Minimumsuche

Wie ist dieser Ausdruck zu werten? Ist das gut oder schlecht? Verdoppeln wir die Anzahl der zu sortierenden Strings, so vervierfacht sich die Rechenzeit! Verzehnfachen wir sie, so dauert es sogar 100 Mal länger, bis das Programm terminiert! Dies alles ist durch den Ausdruck n^2 bedingt. Man sagt: Sortieren durch Minimumsuche hat quadratische Komplexität. Dies lässt erahnen, dass dieses Verfahren für große Datenmengen ungeeignet ist, weil es einfach viel zu viel Zeit benötigte.

Hier wäre es also ein Trugschluss zu sagen: „Wir kaufen einfach für viel Geld einen doppelt so schnellen Rechner, dann können wir auch doppelt so viele Strings (in der gleichen Zeit) sortieren.“ Theoretische Laufzeitüberlegungen schützen vor solchen Trugschlüssen.

Die Anzahl der (Maschinen-)Instruktionen, die ein Programm während seiner Laufzeit ausführt, bezeichnet man in der Informatik als seine Zeitkomplexität. Diese ist hauptsächlich von der Größe seiner Eingabe, d. h. etwa von der Anzahl der zu sortierenden Strings (und deren Länge), und dem verwendeten Algorithmus abhängig. So wird etwa die Zeitkomplexität des Programms „Sortieren eines Arrays von n Strings durch Minimumsuche“ durch den Ausdruck c·n² beschrieben. Dabei ist c eine Konstante, die abhängig ist von der verwendeten Programmiersprache, von der Güte des Compilers oder Interpreters, von der CPU, von der Größe des Hauptspeichers und der Zugriffszeit auf diesen, vom Können des Programmierers und nicht zuletzt vom Algorithmus selbst, der einfache, aber auch zeitaufwändige Maschineninstruktionen erfordern kann. (Den Faktor 1/2 haben wir dabei der Einfachheit halber in das c gezogen.) Während man also das c durch Verbesserung äußerer Umstände (und oftmals Investition von viel Geld) kleiner machen kann, bleibt der Term n^2 jedoch immer erhalten.

Anders ausgedrückt: Das c ist bei der Beschreibung der Laufzeitkomplexität nicht wirklich wichtig! Um diesem Umstand Rechnung zu tragen, werden Laufzeitkomplexitäten in der Informatik immer in der so genannten O-Notation angegeben. Man sagt: Das Sortierverfahren hat Laufzeit O(n^2). Der Ausdruck O wird auch als Landau'sches Symbol bezeichnet.

Mathematisch gesehen steht O(n^2) für eine Menge von Funktionen, und zwar für all diejenigen Funktionen, die „auf lange Sicht“ nicht stärker wachsen als die Funktion n^2, d. h. für diejenigen Funktionen, die durch die Funktion n^2 (bis auf einen konstanten Faktor) nach oben beschränkt sind. Genau gesagt gilt: Eine Funktion f ist Element der Menge O(n^2), wenn es einen Faktor c und ein n0 gibt, so dass ab diesem n0 für alle größeren n gilt:

Die Funktion n^2 wird dann als asymptotische obere Schranke von f bezeichnet. Allgemein sagt die Schreibweise f(n)=O(g(n)) aus, dass die Funktion f durch die Funktion g asymptotisch nach oben beschränkt ist.^[12]

Es kann dabei für eine Funktion f aus O(n^2) durchaus sein, dass sie wesentlich langsamer wächst als n^2, dass - mathematisch ausgedrückt - der Quotient aus f und n^2 mit wachsendem n gegen 0 geht. Ein Beispiel dafür ist die Funktion f(n)=n. Das ist aber bei der Funktion f, die die Laufzeit unseres Sortierverfahrens beschreibt, nicht so. Dieses Verfahren benötigt benötigt immer n^2 Vergleiche (bis auf einen konstanten Faktor von 1/2). Daher ist n^2 auch eine asymptotisch untere Schranke für f. Dieses f verhält sich auf lange Sicht genau wie n^2. Mathematisch ausgedrückt: Es gibt Faktoren c1 und c2 und eine ganze Zahl n0, so dass ab diesem n0 für alle größeren n gilt:

f wird also durch n^2 nach oben und nach unten beschränkt. Für die Menge dieser Funktionen gibt es ebenfalls eine eigene Schreibweise: Theta(n^2).

Abbildung 2.9 stellt eine Funktion f, die durch O(g(n)) nach oben beschränkt ist, einer Funktion f gegenüber, deren asymptotisches Verhalten durch Theta(g(n)) beschrieben wird: Letztere liegt in einem „Schlauch“ um g(n), der sich durch die beiden Faktoren c1 und c2 ergibt.

Abbildung 2.9. Die asymptotischen Schranken O und Theta

Diese Notationen tauchen immer wieder im LEDA-Manual bei der Beschreibung nicht-trivialer Operationen auf. Damit können wir die Größenordnung des verwendeten Verfahrens abschätzen, i. Allg. aber keine genaue Laufzeitvorhersage treffen. (Weil wir i. Allg. das von zu vielen Faktoren abhängende c nicht kennen, auch wenn es sich oft experimentell bestimmen lässt; s. hierzu auch Übung 8)

Häufig findet sich im Manual die Aussage, eine Operation benötige „konstante Zeit“. Damit ist gemeint, dass diese Operation unabhängig von der Größe der Eingabe mit konstant vielen Maschineninstruktionen ausgeführt wird. Die Funktion, die das Laufzeitverhalten beschreibt, ist somit in O(1). Entsprechendes gilt für die Ausdrücke „lineare Zeit“ und „logarithmische Zeit“: Mit Hilfe der O-Notation wird dies oft als „benötigt Zeit O(n) bzw. O(log(n))“ ausgedrückt.

Darüber hinaus findet sich im Manual oft der Ausdruck „erwartete Zeit“ O(g(n)). Damit ist gemeint, dass die Laufzeit einer Operation von Ausführung zu Ausführung schwanken kann, dass aber der Erwartungswert der Laufzeit asymptotisch durch die Funktion g(n) nach oben beschränkt ist.

Zurück zu unserem Sortieralgorithmus: Eine Laufzeit von Theta(n^2) bedeutet, dass eine hinreichend große Eingabe das System laufzeitmäßig immer in die Knie zwingen wird. Statt also viel Geld und Mühe in eine Verkleinerung des Faktors c zu investieren, sollten wir uns eher auf die Suche nach einem besseren Algorithmus machen. Selbstverständlich müssen wir dank LEDA nicht lange danach suchen: LEDA hat alle bekannten effizienten Sortierverfahren eingebaut. So lesen wir z. B. auf der Manualseite von array im Abschnitt „Implementierung“, dass die Methode sort() von Arrays den bekannten Quicksort-Algorithmus implementiert, dessen (erwartete) Komplexität O(n·log(n)) ist, was asymptotisch gesehen wesentlich besser ist als Theta(n^2). Das bedeutet, dass Quicksort auf lange Sicht Sortieren durch Minimumsuche schlägt: Wenn n groß genug ist, wird der Ausdruck c1·n·log(n) ganz sicher kleiner als der Ausdruck c2·n^2, unabhängig davon, wie groß die beiden systemabhängigen Konstanten c1 und c2 der beiden Verfahren sind; der Quotient der beiden Ausdrücke geht gegen 0. (Für kleine n dagegen kann es durchaus sein, dass c1·n·log(n) größer ist als c2·n^2; in der Tat lohnt sich Quicksort auf sehr kleinen Arrays gegenüber Sortieren durch Minimumsuche nicht.)

Nun zurück zur Ausgangsfrage: Können wir mit unserem Sortieralgorithmus Telefonbücher in annehmbarer Zeit sortieren? Das kommt, nach oben Gesagtem, ganz auf die Anzahl der Einträge (also Einwohner der Stadt) und auf die systemabhängige Konstante c an. Für heutige Maschinen gilt: das Telefonbuch von Saarbrücken auf jeden Fall, das von München gerade noch so und das von Deutschland nicht. Mit der Methode sort() der Klasse array dagegen ist auch das letzte Problem kein Problem.

Je besser die Zeitkomplexität eines Algorithmus ist, desto schneller wird der Algorithmus in der Praxis seine Arbeit verrichten. Neben der Zeitkomplexität ist auch noch die Platzkomplexität wichtig: Das ist im Wesentlichen die Anzahl der Speicherzellen, die ein Algorithmus benötigt. Auch diese Anzahl ist bei einem guten Algorithmus möglichst gering.

Häufig besteht für ein Problem ein Zeit-Platz-Tradeoff, d. h. es kann nicht mit wenig Rechenzeit und wenig Speicherverbrauch gelöst werden. Dann muss man einen Kompromiss schließen und dabei Rechenzeit gegen Speicherverbrauch eintauschen oder umgekehrt, je nach dem, welchen Algorithmus man wählt, und wie man diesen parametrisiert.

Manchmal finden wir im Manual auch die Aussage, eine Operation benötige amortisierte Zeit O(f(n)). Damit ist gemeint, dass die Gesamtzeit für n solcher Operationen durch eine Funktion g(n) asymptotisch nach oben begrenzt ist, und dass f(n)=O(g(n)/n) ist. Die amortisierte Zeit ist also (eine Schranke für) die durchschnittliche Zeit einer Operation im schlechtesten Fall.

Der Spezialfall einer amortisierten Zeit von O(1) bedeutet, dass eine Folge von n solcher Operationen nur Zeit O(n) benötigt. Man spricht dann von konstanter amortisierter Zeit.

Solche Aussagen sind oft das Ergebnis einer amortisierten Analyse: Nicht jede der n Operationen benötigt gleich viel Zeit; einige der Operationen sind laufzeitintensiv und leisten viel „Vorarbeit“ (oder auch „Nacharbeit“), was sich aber dadurch auszahlt, dass die restlichen Operationen durch die geleistete Vorarbeit so schnell ablaufen können, dass eine Gesamtzeit von O(g(n)) nicht überschritten wird. Die Investition in die Vorarbeit oder Nacharbeit amortisiert sich also.