https://oer-informatik.de/laufzeit-komplexitaet

Wie ändert sich das Laufzeitverhalten bei Hochskalierung der verarbeiteten Elemente?

tl/dr; (ca. 11 min Lesezeit): Was passiert eigentlich, wenn ich nicht mehr 300 sondern 300.000 Datensätze mit meinem Programm bearbeiten muss? Welche Auswirkungen hat das auf die Laufzeit? Wie kann ich das im Vorhinein bestimmen? Es wird die Big-O-Notation erklärt und es werden unterschiedliche Laufzeitverhalten von Algorithmen mit Python-Quellcode verglichen.

Die Qualität eines Algorithmus, der Listen verarbeitet, kann über das zeitliche Verhalten mit einer steigenden Anzahl an Eingabewerten dargestellt werden.

Wenn ich die Zahl der zu bearbeitenden Listenelemente verdoppelte, wie lange benötigt der Algorithmus? Doppelt so lange? Viermal so lange? Gleich lange?

Wir wollen an Hand verbreiteter Algorithmen (Sortieren, Zählen, Suchen,…) beispielhaft die zeitliche Komplexität messen, die Ursachen für zeitliche Komplexität im dokumentierten Algorithmus abschätzen und mit Hilfe einer aussagefähigen und hardwareneutralen Metrik beschreiben.

Es sollen Aussagen über drei unterschiedliche Szenarien getroffen werden:

• Wie skaliert der Algorithmus zeitlich im günstigsten Fall (z.B. Sortierung bereits sortierter Eingabewerte)? Wir können eine Aussage darüber treffen, wie lange der Algorithmus mindestens benötigt. Diese Metrik wird mit der \Omega -Notation beschreiben (besprochen: “Omega”): \Omega(n)

• Welches Zeitverhalten können wir durchschnittlich für wahllose Eingabewerte der Liste erwarten? Eine Metrik, die dies beschreibt (also einen Wert, der vom Algorithmus unter- und überschritten werden kann) wird in der \Theta-Notation (gesprochen: “Theta”) beschrieben: \Theta(n)

• Welches Zeitverhalten hat der Algorithmus im ungünstigsten Fall (beispielsweise Sortierung einer invers sortierten Liste)? Welches Zeitliche Verhalten wird in keinem Fall überschritten, beispielsweise auch nicht bei sehr ungünstig verteilten Eingabeelementen? Diese Metrik wird mit “Big O”-Notation beschrieben: O(n).

Bei vielen Algorithmen skaliert die Zeit, die ein Algorithmus benötigt, für diese drei Szenarien unterschiedlich schnell. Beispielsweise könnte bei günstigster Eingabemenge der zeitliche Ablauf konstant bleiben, obwohl er im Durchschnitt linear wächst und bei ungünstig verteilten Werten sogar quadratisch wächst:

Da wir in der Regel keine Aussage über die Verteilung der Eingabeelemente treffen können, ist für uns die Obergrenze des zeitlichen Verhaltens von größter Relevanz: Welche relative Laufzeit wird vom Algorithmus nicht überschritten? Die Big-O-Metrik wird uns hier Aussagen ermöglichen.

Bevor wir versuchen, die zeitliche Komplexität allgemein zu beschreiben, wollen wir zur Veranschaulichung das zeitliche Verhalten der Bearbeitung von unterschiedliche großen Listen mit mehreren Beispielprogrammen messen:

Messung der zeitlichen Komplexität

Wir wollen eine Funktion messen, die ein Array bearbeitet - beispielsweise die Implementierung eines Sortier-Algorithmus (dies ist die beobachtete Funktion). Die Laufzeit dieser beobachteten Funktion wird gemessen (Start- und Endzeit):

def messe_laufzeit(beobachtete_funktion, array):
    start = timer()
    beobachtete_funktion(array)
    ende = timer()
    return ende-start

Diese Methode rufen wir mit aufsteigender Anzahl an Array-Elementen auf und messen die benötigte Zeit.

Bei komplexeren Algorithmen bestimmen wir diejenige Reihenfolge an Array-Elementen, die besonders schnell (\Theta) oder besonders langsam (O) bearbeitet werden kann, andernfalls nutzen wir zufällig erstellte Elementelisten (\Omega).

Keine Abhängigkeit von der Anzahl der Elemente: O(1)

Als erstes Beispiel wollen wir eine Funktion beobachten, die lediglich das erste Element einer Liste ausgibt:

def get_first(testlist):
    print(testlist[0])

Die Messung zeigt eine breite Streuung in der Laufzeit zwischen 7ms und 45ms:

Eine Abhängigkeit der Laufzeit dieses Algorithmus von der Anzahl der Elemente der Liste ist jedoch nicht erkennbar. Die großen Schwankungen rühren vermutlich von unterschiedlicher verfügbarer Prozessorzeit her. Es gibt ein deutliche erkennbares Minimum (ca. 7ms) und einige Maxima (ca. 45ms) der Laufzeit und einen Bereich, in dem sich die Laufzeit i.d.R. befindet, weitere Aussagen lassen sich aber auf Basis der Messung nicht treffen.

Die Laufzeit dieses Algorithmus scheint eine Funktion zu sein, die nicht in Abhängigkeit der Anzahl der Elemente steht.

Wenn wir versuchen, die durchschnittliche Laufzeit als Funktion anzugeben, dann liegt die etwa bei 13 Millisekunden - unabhängig von der Anzahl der Elemente. In jedem Fall ist unser Algorithmus besser als etwa 7 ms. Es handelt sich also um einen konstanten Wert:

f(n) = 7 ms = const.

Konstanten werden in der Big-O--Notation vereinfacht: es werden keine konkreten Werte angegeben, da dies für die Skalierung des Algorithmus unerhelblich ist. Stattdessen wird immer 1 notiert. Die Big-O-Notation für einen Algorithmus, der nicht abhängig von der Anzahl der Elemente der bearbeiteten Liste ist, wäre also:

O(1)

Lineare Abhängigkeit von der Anzahl der Elemente O(n)

Eine Liste wird für jedes Element genau einmal durchlaufen. Ein Beispiel für einen Algorithmus, der dieser zeitlichen Komplexität folgt ist eine Summenbildung durch Iteration:

def get_sum(testlist):
    sum =0
    for i in testlist:
        sum = sum + i
    return sum

Wenn wir diese Funktion mit wenigen Elementen durchlaufen, können wir (vereinfacht) die Anzahl der ausgeführten Befehle abzählen (hier für 0-4 Elemente):

Tragen wir die ausgeführten Befehle über die Elementeanzahl in einem Graph auf, so erhalten wir eine erste Idee davon, wie unser Algorithmus mit steigender Anzahl an Elementen skaliert:

Eine Messung dieser Werte führt zu großen Schwankungen:

Verbindet man die lokalen Minima oder bildet den gleitenden Durchschnitt der gemessenen Werte lässt sich ein linearer Zusammenhang erkennen. Eine Verdopplung der Elemente führt also durchschnittlich zu einer Verdopplung der Operationen (und damit der Rechenzeit). Dieses proportionale Verhalten lässt sich für unsere Beispielmessung in etwa durch folgende Funktionsgleichung ausdrücken:

l(n) = n \cdot \frac{1}{10.000} ms + 0ms

Bei 5.000 Elementen ist die Laufzeit in jedem Fall besser als ca. 0,5 ms, bei 10.000 Elementen ca. 1ms.

Für das Skalierungsverhalten des Algorithmus spielt die Steigung der Geraden (in unserem Beispiel \frac{1}{10.000}) keine Rolle, daher wird auch hier wieder dieser konstante Faktor weggelassen. Lineare Zusammenhänge zwischen der Anzahl der Elemente und der Laufzeit werden in der Big-O- Notation bezeichnet mit:

O(n)

Quadratische Abhängigkeit O(n^2)

Wenn wir zwei verschachtelte Schleifen haben, handelt es sich häufig um eine quadratische Abhängigkeit: da der Index doppelt durchlaufen wird geht mit einer Verdopplung der Elemente eine Vervierfachung der benötigten Zeit einher.

Ein Beispiel hierfür zählt alle mehrfach vorkommenden Elemente.

def find_duplicates(testlist):
    duplicates = 0
    for i in testlist:
      for j in testlist:
          if i == j:
            duplicates =+ 1
    return duplicates

Dieses Beispiel ist bewusst so gehalten, dass es alle x mit y vergleicht - und auch alle y mit x. Somit würde jedes Element einmal, jedes Duplikat zweimal gefunden.

Hier wird es schon etwas mühsamer, die Befehle zu zählen. Für n=0..3 Elemente ist dies hier einmal exemplarisch durchgeführt:

Es sind also 2, 6, 14 bzw. 26 Operationen nötig für n=0..3. Tragen wir auch hier die ausgeführte Befehlsanzahl über die Elementeanzahl in einem Graph auf, so erhalten wir einen Graphen, der an eine Parabel - also eine quadratische Funktion - erinnert:

Die Anzahl der ausgeführten Befehle in Abhängigkeit von der Elementeanzahl ergibt sich genau genommen zu:

b(n) = 2 \cdot n^2 + 2 \cdot n + 2

… aber so viel Genauigkeit ist an dieser Stelle gar nicht gewünscht, schließlich wollen wir nur die Skalierung abschätzen - zumal wir wissen, dass nicht alle Befehle gleich viel Rechenzeit benötigen. Bei derartigen Polynomen (so nennen sich Terme mit dem Aufbau a_k \cdot x^k +a_{k-1} \cdot x^{k-1} + ... + a_{1} \cdot x^{1} + a_{0} ) ist der Einfluss der Summanden mit kleinerem Exponenten für sehr große Zahlen vernachlässigbar. Die Größenordnung wird nur durch den höchsten Exponenten bestimmt.

Zur Abschätzung der Skalierung von b(n) = 2 \cdot n^2 + 2 \cdot n + 2 können wir also unsere Regeln anwenden:

1. Nur den Summanden betrachten, der den größten Einfluss auf das Skalierungsverhalten hat: b^*(n) = 2 \cdot n^2

2. Konstanten und konstante Faktoren können vernachlässigt werden: b^{**}(n) = n^2

Wir vereinfachen also und können sagen: die zeitliche Komplexität des Algorithmus ist besser oder gleich O(n^2)

Können wir das auch an Hand der Messwerte bestätigen?

Auch hier ist ein parabelhafter Anstieg erkennbar, der quadratisch skaliert (bei den ersten 1000 Elementen noch 125ms, bei 2000 ca. 250ms, bei 3000 ca. 625ms usw.).

Ähnlich sieht es beim Bubblesort-Algorithmus aus: es liegen zwei verschachtelte Schleifen vor:

def bubbleSort(arr):
    arraylength = len(arr)

    for outer_index in range(arraylength-1):
        vertauscht = False
        for inner_index in range(0, arraylength-outer_index-1):
            if arr[inner_index] > arr[inner_index + 1] :
                arr[inner_index], arr[inner_index + 1] = arr[inner_index + 1], arr[inner_index]
                vertauscht = True          
        if vertauscht == False:
            break

Bei genauer Betrachtung fällt auf, dass die innere Schleife bei jedem Durchlauf der äußeren Schleife um genau einen Durchlauf kürzer wird. Unsere Laufzeit wächst zwar zunächst quadratisch (z.B. mit b_{1}(n) = a \cdot n^2), wird aber bei jedem Schleifendurchlauf immer linear etwas schneller (b_{2}(n) = b \cdot n). Im Ganzen ergibt sich also eine Laufzeit, die über die Anzahl der Elemente skaliert wie:

b(n) = a \cdot n^2 - b \cdot n

Auch hier gelten die Vereinfachungsregeln: der Einfluss des linearen Anteils ist bei großem n sehr gering und kann vernachlässigt werden, ebenso die Konstanten. Bubblesort skaliert somit auch in jedem Fall besser als:

O(n^2)

Auch hier lässt die Messung den erwarteten quadratischen Anstieg erkennen:

Kubische Abhängigkeit O(n^3)

Analog zur quadratischen Abhängigkeit gilt bei drei ineinander verschachtelten Schleifen eine kubische Abhängigkeit, die analog in Big-O-Notation mit O(n^3) notiert wird. In der Praxis kommt diese jedoch deutlich seltener vor. Die Überlegungen zur quadratischen Abhängigkeit der Verarbeitungsschritte von der Elementeanzahl gelten für kubische Algorithmen entsprechend.

Logarithmische Abhängigkeit O(log(n))

Ein anderes zeitliches Skalierungsverhalten liegt beispielsweise bei der Suche in einem sortieren Binärbaum vor: Es wird der Index eines bestimmten Zahlenwerts in einem Array gesucht. Wird die Zahl gefunden, soll der Index zurückgegeben werden, andernfalls ist der Rückgabewert -1.

Der Ablauf des Algorithmus ist etwa wie folgt:

• bestimme den Wert in der Mitte des Arrays

• prüfe, ob die gesuchte Zahl größer als, kleiner als oder gleich der Zahl ist

• bei Gleichheit gebe den Index des momentanen Mittenwerts zurück

• andernfalls führe die obigen Schritte mit der Hälfte der Zahlen erneut durch, in denen die gesuchte Zahl liegt.

In Python könnte das (ohne Rekursion) etwa so aussehen:

def binary_search(testlist, gesuchter_eintrag):
    untergrenze = 0
    obergrenze = len(testlist) - 1

    while (untergrenze <= obergrenze):

        geschaetzter_mittelwert = (obergrenze + untergrenze) // 2

        if testlist[geschaetzter_mittelwert] < gesuchter_eintrag:
            untergrenze = geschaetzter_mittelwert + 1
        elif testlist[geschaetzter_mittelwert] > gesuchter_eintrag:
            obergrenze = geschaetzter_mittelwert - 1
        else:
            return geschaetzter_mittelwert
    return -1

Dieser Algorithmus skaliert langsamer als die lineare Skalierung, die wir oben betrachtet haben, da sich mit jedem Schleifendurchlauf die Anzahl der zu durchsuchenden Elemente halbiert.

Aus der obigen Tabelle lässt sich für den genannten Code herleiten, dass die Anzahl der Befehle folgendermaßen von der Elementeanzahl abhängt:

b(n) = 5 \cdot log_{2}(n) + 6

Da diese Funktion sehr langsam wächst lässt sich der Verlauf bei einer linearen Skalierung kaum erkennen. Bei der Verarbeitungszeit überwiegt das Rauschen, lediglich am Beginn der Messung lässt sich die logaritmische Steigung erkennen.

Regeln zur Bestimmung einer vereinfachten zeitlichen Komplexität

In der Regel werden zeitliche Komplexitäten zur Bewertung von Algorithmen nicht gemessen - diese Ergebnisse hängen stark von der verwendeten Rechnerarchitektur ab - und, wie man oben sieht, von der momentanen Systemlast (Rauschen).

Statt dessen versucht man, an Hand des Aufbaus und der Wiederholungsstrukturen eine Aussage zu treffen, mit welcher Größenordnung die Laufzeit des Algorithmus bei steigender Anzahl der Eingabegrößen skaliert. Dazu nutzt man Vereinfachungsregeln, die helfen, die relevante Skalierung herauszuarbeiten:

Instruktionen in Abhängigkeit der Elementeanzahl

Die Anzahl der Instruktionen in Abhängigkeit der Elementeanzahl (n) herausarbeiten. Besonderes Augenmerk liegt hierbei auf Wiederholungsstrukturen. Einzelne Programmsequenzen können zusammengefasst werden.

Konstanten vernachlässigen

Konstante Faktoren sind zwar relevant, wenn wir gleichartig-komplexe Algorithmen vergleichen wollen - für das große Ganze spielen sie aber keine Rolle. Bei einer sehr großen Anzahl an Elementen ist ihr Einfluss zu vernachlässigen. Aus O(5n) würde also O(n)

Nur die Terme mit größtem Einfluss betrachten

Für die Skalierbarkeit eines Algorithmus ist nur derjenige Term relevant, der den steilsten Verlauf hat - wir können also beispielsweise in Polynomen die Terme mit niedrigerem Exponenten vernachlässigen. Aus

O(n^3 + 2n^2 + 5n)

wird somit

O(n^3)

Allgemeiner gesprochen gilt bei hinreichend großem n:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

Der Grafik können wir entnehmen, dass erst bei großem n die Reihenfolge wie oben angegeben ist. Es kann durchaus sein, dass für kleine Eingabemengen ein anderer Algorithmus zeitlich überlegen ist als für große n. Wir betrachten jedoch nur die Skalierbarkeit - also den Extremwert für sehr große Elementeanzahlen.

Wir erkennen die abweichende Reihenfolge beispielsweise bei dem zweit- und drittsteilsten Verlauf: der grüne Verlauf für O(n^3) ist im abgebildeten Intervall noch günstiger (schneller) als der Verlauf für O(2^n) - werden größere n betrachtet wird sich das ändern.

Weitere Literatur und Quellen

• Die Idee der Messung mit Python wurde von Terrence Aluda auf dev.to inspiriert: Big O notation using Python

Quellen und offene Ressourcen (OER)

Die Ursprungstexte (als Markdown), Grafiken und zugrunde liegende Diagrammquelltexte finden sich (soweit möglich in weiterbearbeitbarer Form) in folgendem git-Repository:

https://gitlab.com/oer-informatik/algorithmik/pseudocode.

Sofern nicht explizit anderweitig angegeben sind sie zur Nutzung als Open Education Resource (OER) unter Namensnennung (H. Stein, oer-informatik.de) freigegeben gemäß der Creative Commons Namensnennung 4.0 International Lizenz (CC BY 4.0).