Zeitkomplexität (Englisch: Time Complexity) bezeichnet den Zeitbedarf eines Algorithmus in Bezug auf seine Eingabedaten. Über sie lässt sich die zeitliche Effizienz eines Algorithmus bewerten und Alternativen gegenüberstellen, etwa zur Verschlüsselung, Komprimierung, Suche oder Sortierung von Daten.
Die Zeitkomplexität ist eine der wichtigsten Metriken der allgemeineren Computational Complexity, zu Deutsch einfach „Komplexität“, von Algorithmen. Eine weitere populäre Metrik in diesem Kontext ist die Platzkomplexität (Space Complexity), auf die ich in einem Absatz weiter unten auch eingehen werde.
Fälle von Zeitkomplexität
Der Zeitbedarf eines Algorithmus hängt nicht alleine von der Größe der Eingabedaten ab. Ich möchte dies am Beispiel des bekannten Sortieralgorithmus Bubble Sort veranschaulichen. Dieser Algorithmus vergleicht nebeneinanderliegende Elemente eines Arrays und vertauscht diese wenn nötig, bis das Array sortiert ist. Der folgende Abschnitt zeigt, wie das Array [ 4, 2, 5, 1, 3 ] mit Bubble Sort in sechs Schritten aufsteigend sortiert wird:
[ 4, 2, 5, 1, 3 ]
[ 2, 4, 5, 1, 3 ] # 4, 2 -> 2, 4
[ 2, 4, 1, 5, 3 ] # 5, 1 -> 1, 5
[ 2, 4, 1, 3, 5 ] # 5, 3 -> 3, 5
[ 2, 1, 4, 3, 5 ] # 4, 1 -> 1, 4
[ 2, 1, 3, 4, 5 ] # 4, 3 -> 3, 4
[ 1, 2, 3, 4, 5 ] # 2, 1 -> 1, 2
Beim zeitlichen Aufwand zur Sortierung spricht man hier von einem durchschnittlichen Fall (average case). Es waren sechs Schritte notwendig, um das Array in eine sortierte Form zu bringen. Das Array hätte aber auch in einer Form vorliegen können, in der mehr oder weniger Schritte notwendig gewesen wären. Liegt das Array bereits in der Form [ 1, 2, 3, 4, 5 ] vor, so sind keine Operationen notwendig, man spricht hier vom besten Fall (best case). Im Fall von Bubble Sort liegt der schlechteste Fall (worst case) vor, wenn ein aufsteigend zu sortierendes Array absteigend sortiert vorliegt oder umgekehrt. Bei einem Array mit fünf Elemente sind dafür zehn Schritte erforderlich, wie der folgende Abschnitt kompakt veranschaulicht:
54321
45321
43521
43251
43215
34215
32415
32145
23145
21345
12345
O-Notation
Die O-Notation, im Englischen big O notation, auch als Landau-Notation geläufig, wird bei der Analyse von Algorithmen verwendet, um ihre Zeit- und Platzkomplexität als Funktion zu beschreiben. Die Bezeichnungen gehen auf die deutschen Zahlentheoretiker Paul Bachmann und Edmund Landau zurück. Das große O steht dabei für Ordnung und wurde von Bachmann erstmals 1894 beschrieben. Die O-Notation verwende ich in den folgenden Abschnitte, um mehrere Beispiele für Zeitkomplexität zu geben.
Berechnung der Zeitkomplexität
Nehmen wir folgende Funktion, die die Summe alle (numerischen) Elemente eines Arrays berechnet:
def sum(array):
s = 0
for e in array:
s += e
return s
In der O-Notation geben wir die Länge des Arrays mit n an. Nun zählen wir die Anzahl Schritte im Algorithmus. Unabhängig von n wird s = 0 immer ausgeführt. Die Zuweisung s += e wird für jedes Element im Array, also genau n mal ausgeführt. Damit hat die Funktion eine Zeitkomplexität von O(n + 1). Da der Wert n schneller wächst als der Wert 1, wird die Formel auf O(n) reduziert (bei steigendem n ist die 1 vernachlässigbar). Bei komplizierteren Algorithmen, wenn etwa Fallunterscheidungen und Rekursion hinzukommen, ist die Berechnung der Zeitkomplexität nicht mehr trivial und kann große Zeitaufwände oder entsprechende Erfahrung erfordern.
Bei der Berechnung der Zeitkomplexität geht es nicht unmittelbar um die tatsächlich benötigte Zeit. Diese wird von vielen Faktoren beeinflusst, wie der Startzeit eines Programmes, Abläufen wie einer Garbage Collection zur Laufzeit, Betriebssystem- und Hardwarebesonderheiten etc. Die Zeitkomplexität ist eine Vereinfachung, die veranschaulicht, mit welchem Zeitbedarf bei größeren Eingabewerten zu rechnen ist. Je größer die Eingabewerte oder je zeitkritischer die Anforderungen, umso mehr Aufmerksamkeit muss man der Zeitkomplexität widmen.
Ein ineffizienter Algorithmus stellt sich schnell als ungeeignet heraus, wenn man die mathematischen Aufgaben von Project-Euler lösen möchte (Link am Ende des Beitrags). Auch der Brute-Force-Ansatz zum Knacken eines Passwortes veranschaulicht sehr gut, wie der Zeitaufwand mit steigender Komplexität ins Unendliche wachsen kann. Letzteres kann man, wenn man nur die zehn Ziffern, die 26 Buchstaben unseres Alphabets und Groß- und Kleinschreibung sowie die 30 gängigsten Sonderzeichen betrachtet, mit O(92^n) beschreiben, wobei n die Länge des Passworts repräsentiert. Ein Passwort mit 24 Zeichen dieses Zeichensatzes ist gegenüber einem Passwort mit 6 Zeichen etwa um den Faktor 200 Quintilliarden besser gegen Brute-Force-Angriffe geschützt (das ist eine 2 mit 35 Nullen).
Verbreitete Zeitkomplexitäten
Die nachfolgenden Beispiele zeigen verschiedene Zeitkomplexitäten und sind bewusst vereinfacht.
Konstante Zeit
O(1) symbolisiert eine konstante Zeit, d.h. der Zeitbedarf wächst nicht mit n, sondern bleibt gleich. Die nachfolgende Funktion gibt das erste Element eines Arrays zurück und hat eine Zeitkomplexität von O(1), da die Größe des Arrays keinen Einfluss auf die Operation hat.
def first(array):
return array[0]
Lineare Zeit
O(n) steht für einen linearen Zeitbedarf, d.h. die erwartete Dauer wächst proportional zu n. Die folgende (nicht optimierte) Funktion gibt an, ob es sich bei einer Zahl um eine Primzahl handelt. n ist hier gleichbedeutend mit der eigentlichen Zahl und nicht mit der Größe eines Arrays, wie in vielen anderen Beispielen hier. Der Zeitbedarf ist nur im schlechtesten Fall linear, wenn es sich tatsächlich um eine Primzahl handelt. Wie schon im Eingangsbeispiel findet hier eine Vereinfachung statt: Da die Iteration von 2 bis number - 1 erfolgt, wird O(n - 2) zu O(n) verkürzt.
def is_prime(number):
if number < 2:
return False
for i in range(2, number):
d = number // i
if i * d == number:
return False
return True
Der folgende Algorithmus gibt zurück, wie oft das größte Element in einem Array vorkommt. Da das komplette Array dabei genau zweimal durchlaufen wird und es auch keinen vorzeitigen Ausstieg gibt, gilt für den besten, durchschnittlichen und schlechtesten Fall jeweils O(2n).
def count_max(array):
m = 0
c = 0
for e in array:
if e > m:
m = e
for e1 in array:
if e1 == m:
c += 1
return c
Quadratische und kubische Zeit
0(n ^ 2) repräsentiert einen quadratischen Zeitbedarf und beschreibt oft den schlechtesten Fall diverser Sortieralgorithmen, inklusive Bubble Sort. Quadratische Zeiten erreicht man durch verschachtelte Iterationen über den Eingabewert. Bei Verschachtelung ergibt sich allgemein ein Zeitbedarf von O(n ^ x) im schlechtesten Fall, wobei x die Verschachtelungstiefe darstellt. Der nachfolgende Algorithmus mit kubischem Zeitbedarf von O(n ^ 3) findet drei identische Elemente in einem Array und hat die schlechteste Zeit, wenn kein Trio gefunden wird:
def find_triplet(array):
for i, e1 in enumerate(array):
for j, e2 in enumerate(array):
for k, e3 in enumerate(array):
if i!=j and i!=k and j!=k and e1==e2==e3:
return i, j, k
return None
Logarithmische Zeit
O(log n) steht für einen logarithmischen Zeitbedarf. Viele der effizienteren Sortieralgorithmen wie Heap Sort und Merge Sort haben einen logarithmischen Zeitbedarf von O(n log n). Binäre Suchen und der folgende an diese angelehnte Algorithmus haben ebenfalls einen logarithmischen Zeitbedarf, da sich die Größe des Eingabewertes mit jeder Iteration halbiert:
actual_num = 314
def compare(num):
if actual_num < num: return -1
elif actual_num > num: return 1
else: return 0
def guess_num():
steps, minimum, maximum = 0, 0, 1000
guess = (minimum + maximum) // 2
while (res := compare(guess)) != 0:
if res < 0:
maximum = guess
if res > 0:
minimum = guess
guess = (minimum + maximum) // 2
steps += 1
return guess, steps
Die Funktion guess_num() errät in diesem Beispiel die Zahl actual_num und erhält dafür über die Funktion compare(num) Hinweise, ob die geratene Zahl kleiner, größer oder gleich der gesuchten ist. Im definierten Bereich von 0 bis 1000 kann die Anzahl der Schritte stark variieren. Legt man den Code oben in einer Datei guess.py ab, so kann man mit der Python-REPL actual_num verändern und beobachten, wie sich dies auf die Anzahl der Iterationen auswirkt:
$ python -i guess.py
>>> actual_num
314
>>> guess_num()
(314, 9)
>>> actual_num = 313
>>> guess_num()
(313, 8)
>>> actual_num = 312
>>> guess_num()
(312, 3)
Die Anzahl der Schritte reduziert sich hier von 9 auf 8 auf 3. Vergrößert man allerdings den Zahlenraum massiv, so wird diese Varianz vernachlässigbar klein. Der folgende Ausschnitt zeigt, dass sich bei einem Maximum von 100 Trillionen (eine 1 mit 19 Nullen) die Anzahl Schritte nur geringfügig unterscheidet:
>>> actual_num = 777_777_777
>>> guess_num()
(777777777, 65)
>>> actual_num = 7_777_777_777
>>> guess_num()
(7777777777, 62)
>>> actual_num = 77_777_777_777
>>> guess_num()
(77777777777, 66)
>>> actual_num = 777_777_777_777
>>> guess_num()
(777777777777, 66)
>>> actual_num = 7_777_777_777_777
>>> guess_num()
(7777777777777, 66)
Exponentielle Zeit
O(2 ^ n) beschreibt einen Algorithmus, bei dem sich der Zeitbedarf bei n+1 gegenüber n verdoppelt. Die Berechnung dauert für n=4 also doppelt so lange wie für n=3, für n=5 ist sie bereits vier mal so teuer und so weiter.
Eine nicht-optimierte rekursive Fibonacci-Funktion ist ein gutes Beispiel für einen solchen exponentiellen Zeitbedarf. Der folgende Algorithmus zeigt, dass es auch noch schlimmer geht. In der Fibonacci-Reihe ergibt sich die nächste Zahl immer aus der Summe der beiden vorherigen: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
In der fiktiven „Fubonacci“-Folge ergibt sich die nächste Zahl aus der Summe der drei vorherigen. Die Reihe beginnt wie folgt: 0, 1, 2, 3, 6, 11, 20, 37, 68...
Für diesen Algorithmus gilt O(3 ^ n), da jede Iteration drei weitere rekursive Aufrufe bedeutet. Auf meinem aktuellen Arbeitsgerät ist die Verdreifachung des Zeitbedarfs bereits ab fub(25) spürbar. Nachfolgend der Algorithmus zu dieser ausgedachten Zahlenfolge:
def fub(x):
if x < 3:
return x
return fub(x - 1) + fub(x - 2) + fub(x - 3)
Einordnung
Die gezeigten Beispiele beschreiben oft anzutreffende Zeitbedarfe, sind aber bei weitem nicht vollständig. Eine Brute-Force-Lösung für das Problem des Handelsreisenden etwa ist fakultativ komplex, d.h. es gilt O(n!). Bei dem Problem geht es darum, alle angegebenen Orte auf dem kürzesten Weg zu bereisen. Dies sind bei drei Orten noch 1 * 2 * 3 = 6 Möglichkeiten, bei fünf Orten sind es schon 1 * 2 * 3 * 4 * 5 = 120 und bei zehn Orten sogar 3628800 mögliche Routen.
Wie schon im allerersten Beispiel veranschaulicht, werden die Formeln immer auf den größten Einflussfaktor verkürzt. aus O(n + 1) wird also O(n), aus O(n ^ 2 + 2n) wird O(n ^ 2) und aus O(n ^ 4 + n ^ 2) wird O(n ^ 4). Das hat den Hintergrund, dass die kleineren Faktoren mit wachsendem n im Vergleich zum größten Faktor immer weniger ins Gewicht fallen und vereinfachte, reduzierte Formeln sich besser vergleichen lassen.
Stellt man n ^ 4 und n ^ 2 gegenüber, so macht letzteres bei n=2 noch 25% von ersterem aus – bei n=100 sind es nur noch ein Promille. Da Zeitkomplexität vor allem bei größeren Daten interessant ist, fallen die kleineren Faktoren nicht mehr ins Gewicht und lenken nur vom Eigentlichen ab. Ebenfalls der Einfachheit halber differenziert man auch nicht zwischen verschiedenen Anweisungen oder Werten. Eine Addition hat genauso viel Gewicht wie eine Multiplikation, und es spielt keine Rolle, ob die verwendeten Zahlen dabei zweistellig oder zwanzigstellig sind.
Grundsätzlich sind konstante und lineare Zeiten erstrebenswert, logarithmische Zeiten im Mittelfeld und alles ab quadratischen Zeiten aufwärts nach Möglichkeit zu vermeiden.
Platzkomplexität
Platzkomplexität ist eine weitere wichtige Metrik der Computational Complexity und spielt meines Erachtens vor allem im Embedded-Bereich und bei der Verarbeitung richtig großer Daten, etwa in der Künstlichen Intelligenz, eine Rolle. Aber auch in der Komprimierung hat sie einen hohen Stellenwert, beim Laden von Internetinhalten, gerade im mobilen Bereich, und ebenso beim Speichern und Streaming von Mediendateien.
Auch in der Platzkomplexität wird die O-Notation zur Angabe des Speicherbedarfs in Relation zu den Eingabedaten verwendet. Grundsätzlich kann differenziert werden zwischen In-Place-Algorithmen und solchen, die zusätzlichen Speicher für die Zieldaten reservieren. Darüber hinaus fällt oft Hilfsspeicher an, um temporär Informationen abzulegen, die spätestens nach Durchlauf des Algorithmus nicht mehr benötigt werden.
Der folgende Abschnitt verdeutlicht anfallenden Hilfsspeicher beim Tauschen zweier Elemente, was eine häufige Operation in vielen Sortieralgorithmen darstellt:
a, b = 5, 8 # Initialisierung
# Python-spezifische Instruktion
# zum Vertauschen der beiden Werte:
a, b = b, a
# Was aber tatsächlich passiert
# und in vielen Sprachen erforderlich ist:
temp = a
a = b
b = temp
# Zu Lasten der Zeitkomplexität
# und Lesbarkeit lässt sich
# bei numerischen Werten
# der Einsatz einer temporären Variablen
# und damit Platz sparen:
a = a + b
b = a - b
a = a - b
# Zur Verdeutlichung:
# 5 + 8 = 13 (a temp)
# 13 - 8 = 5 (b neu)
# 13 - 5 = 8 (a neu)
Strand Sort ist neben Merge Sort einer der eher wenigen populären Sortieralgorithmen, der nicht in-place arbeitet. Der Algorithmus verwendet neben dem Eingabedaten-Array zwei weitere Arrays. Am Ende ist das Eingabedaten-Array leer und eines der beiden Hilfs-Arrays enthält die sortierten Daten. Neben dem zusätzlich erforderlichen Platz ist hier vor allem die große Anzahl an Einfüge- und Löschaktionen zu berücksichtigen, die einen großen Einfluss auf das Zeitverhalten nehmen können.
Zeitkomplexität verschiedener Sortieralgorithmen
Mein GitHub-Projekt time-complexity-of-sorting-algorithms demonstriert das Zeitverhalten verschiedener Sortieralgorithmen für zufällige numerische Daten. Das Projekt lässt sich leicht anpassen und lädt zum Experimentieren ein. Per Voreinstellung werden alle Algorithmen auf ein unsortiertes Array mit 32 Zufallszahlen angewandt. Bis zu einem definierten Schwellwert von in der Voreinstellung 100 Millisekunden verdoppelt sich diese Zahl und das tatsächliche Laufzeitwachstum wird protokolliert. Daneben gibt es auch die Möglichkeit, die Performance der Algorithmen gegen statische Daten direkt mit einander zu vergleichen.
Im Projekt befinden sich Implementierungen hier erwähnter Algorithmen wie Bubble Sort, Heap Sort, Merge Sort und Strand Sort in Python.
Ich beabsichtige, in Zukunft weitere Algorithmen sowie Eingabedaten hinzuzufügen (z.B. teilweise vorsortierte Daten). Der Code ist jedoch so überschaubar, dass er von jedem mit rudimentären Programmierkenntnissen ohne großen Aufwand erweiterbar sein sollte.
- time-complexity-of-sorting-algorithms (GitHub) - project-euler