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

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

https://bildung.social/@oerinformatik/

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

Laufzeitkomplexität, Zeitkomplexität, Big-O-Notation, Landau-Notation, Algorithmen, Skalierung, Komplexitätsklassen, Bubblesort, Binäre Suche, Python

tl/dr; (ca. 20 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 [AI-Assisted]. (Zuletzt geändert am 27.10.2026)

Dieser Artikel ist Teil einer Artikelreihe über die Komplexität von Algorithmen: Laufzeitkomplexität und Big-O-Notation / Zyklomatische Komplexität (McCabe-Zahl) / Zyklomatische Komplexität von Bubblesort

Schon fit in diesem Thema? Nutze die Kann-Liste und die Leitfragen unter dem Artikel als Checkliste, ob Du die relevanten Kompetenzen bereits hast. Hier klicken, um Kann-Liste ein- oder auszublenden

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 verdopple, wie lange benötigt der Algorithmus? Doppelt so lange? Viermal so lange? Gleich lange?

Wir wollen anhand 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 (best case, z. B. Sortierung bereits sortierter Eingabewerte)? Wir können eine Aussage darüber treffen, wie lange der Algorithmus mindestens benötigt.

• Welches Zeitverhalten können wir durchschnittlich (average case) für zufällig verteilte Eingabewerte der Liste erwarten?

• Welches Zeitverhalten hat der Algorithmus im ungünstigsten Fall (worst case, beispielsweise Sortierung einer umgekehrt sortierten Liste)? Welches zeitliche Verhalten wird in keinem Fall überschritten, auch nicht bei sehr ungünstig verteilten Eingabeelementen?

Für jeden dieser Fälle lässt sich das Wachstum der Laufzeit mit Schranken der Landau-Notation beschreiben:

• Die Big-O-Notation O(f(n)) gibt eine obere Schranke an: Die Laufzeit wächst (bis auf einen konstanten Faktor) höchstens so schnell wie f(n).

• Die Omega-Notation \Omega(f(n)) (gesprochen: „Omega“) gibt eine untere Schranke an: Die Laufzeit wächst mindestens so schnell wie f(n).

• Die Theta-Notation \Theta(f(n)) (gesprochen: „Theta“) gilt, wenn beides zutrifft: Die Laufzeit wächst genau so schnell wie f(n) (scharfe Schranke).

Häufig wird vereinfachend \Omega mit dem günstigsten und O mit dem ungünstigsten Fall gleichgesetzt. Genau genommen sind Fall und Schranke aber zwei verschiedene Dinge: Für jeden Fall kann man eine obere, eine untere oder eine scharfe Schranke angeben. Der unten gezeigte Bubblesort mit vorzeitigem Abbruch benötigt z. B. im günstigsten Fall \Theta(n) und im ungünstigsten Fall \Theta(n^2) Schritte.

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 unterschiedlich 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 Funktion 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 (best case) oder besonders langsam (worst case) bearbeitet werden kann, andernfalls nutzen wir zufällig erstellte Elementelisten (average case).

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 etwa 5 ms und 45 ms:

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 deutlich erkennbares Minimum (ca. 5 ms) und einige Maxima (ca. 45 ms) 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 keinem Fall ist unser Algorithmus schneller als etwa 5 ms. Die durchschnittliche Laufzeit ist also ein konstanter Wert:

f(n) \approx 13\,\mathrm{ms} = \mathrm{const.}

Konstanten werden in der Big-O-Notation vereinfacht: es werden keine konkreten Werte angegeben, da dies für die Skalierung des Algorithmus unerheblich 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}\,\mathrm{ms} + 0\,\mathrm{ms}

Bei 5.000 Elementen ist die Laufzeit in keinem Fall kürzer als ca. 0,5 ms, bei 10.000 Elementen nicht kürzer als ca. 1 ms.

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 jedes i mit jedem j vergleicht – und auch jedes j mit jedem i. 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 Graphen 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 1000 Elementen ca. 125 ms, bei 2000 ca. 400 ms, bei 3000 ca. 900 ms – bei doppelter Elementeanzahl also etwa die drei- bis vierfache Zeit).

Ä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: Im ersten Durchlauf vergleicht sie n-1 Paare, im zweiten n-2 und so weiter bis zu einem einzigen Vergleich. Im ungünstigsten Fall (kein vorzeitiger Abbruch) ergibt sich die Zahl der Vergleiche als Summe:

b(n) = (n-1) + (n-2) + \dots + 2 + 1 = \frac{n \cdot (n-1)}{2} = \frac{1}{2} \cdot n^2 - \frac{1}{2} \cdot n

Für n = 5 sind das z. B. 4 + 3 + 2 + 1 = 10 = \frac{5 \cdot 4}{2} Vergleiche.

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 keinem Fall schlechter 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 binären Suche in einem sortierten Array 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 gib 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 im ungünstigsten Fall folgendermaßen von der Elementeanzahl abhängt (exakt für Zweierpotenzen, dazwischen wird \log_{2}(n) abgerundet):

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 logarithmische 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).

Stattdessen 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(\log n) < O(n) < O(n \log n) < 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) liegt im abgebildeten Intervall noch über dem Verlauf für O(2^n), ist dort also ungünstiger (langsamer). Erst ab n = 10 liegt 2^n über n^3 (2^{10} = 1024 > 10^3 = 1000).

Leitfragen

1. Was beschreibt die zeitliche Komplexität eines Algorithmus, und warum wird sie meist nicht gemessen, sondern abgeschätzt? Antwort

Sie beschreibt, wie die Laufzeit mit wachsender Anzahl n der verarbeiteten Elemente skaliert. Gemessene Laufzeiten hängen von Rechnerarchitektur und Systemlast ab (Rauschen), deshalb schätzt Du die Komplexität hardwareneutral aus dem Aufbau und den Wiederholungsstrukturen ab, siehe Abschnitt „Regeln zur Bestimmung einer vereinfachten zeitlichen Komplexität“.

2. Welche Komplexität haben der Zugriff auf das erste Element, die Summe über alle Elemente und zwei verschachtelte Schleifen über dieselbe Liste? Antwort

Der Zugriff auf das erste Element ist unabhängig von der Elementeanzahl: O(1). Die Summenbildung durchläuft jedes Element einmal: O(n). Zwei verschachtelte Schleifen über dieselbe Liste führen zu n \cdot n Durchläufen: O(n^2), siehe Abschnitt „Quadratische Abhängigkeit“.

3. Warum hat die binäre Suche eine logarithmische Komplexität? Antwort

Die binäre Suche halbiert in einem sortierten Array mit jedem Schleifendurchlauf den Bereich, in dem noch gesucht wird. Bei doppelter Elementeanzahl ist also nur ein Durchlauf mehr nötig, die Laufzeit wächst mit O(\log n), siehe Abschnitt „Logarithmische Abhängigkeit“.

4. Wie vereinfachst Du b(n) = 2 \cdot n^2 + 2 \cdot n + 2 für die Big-O-Notation? Antwort

Du betrachtest nur den Term mit dem größten Einfluss für große n (2 \cdot n^2) und lässt den konstanten Faktor weg. Es bleibt O(n^2), siehe Abschnitt „Konstanten vernachlässigen“ und Abschnitt „Nur die Terme mit größtem Einfluss betrachten“.

5. In welcher Reihenfolge wachsen die üblichen Komplexitätsklassen, und gilt diese Reihenfolge auch für kleine n? Antwort

Für hinreichend große n gilt O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!). Für kleine n kann die Reihenfolge abweichen, deshalb kann bei kleinen Eingabemengen ein Algorithmus mit schlechterer Komplexitätsklasse schneller sein, siehe Abschnitt „Nur die Terme mit größtem Einfluss betrachten“.

6. Was unterscheidet günstigsten, durchschnittlichen und ungünstigsten Fall, und warum interessiert meist der ungünstigste? Antwort

Die Fälle beschreiben das Laufzeitverhalten bei besonders günstig, zufällig und besonders ungünstig verteilten Eingabewerten (beim Sortieren z. B. bereits sortiert, zufällig, umgekehrt sortiert). Weil die Verteilung der Eingabewerte meist nicht bekannt ist, interessiert vor allem die obere Schranke im ungünstigsten Fall, die mit der Big-O-Notation angegeben wird, siehe Einleitung des Artikels.

Links und weitere Informationen

• Die Idee der Messung mit Python wurde von Usman Malik auf Stack Abuse (“Big O Notation and Algorithm Analysis with Python Examples”) und Terrence Aluda auf dev.to (“Big O notation using Python”) inspiriert

• Python-Skript zur Laufzeitmessung im Repository

• zum Weiterlesen: Programmentwürfe lesen, prüfen und korrigieren und Zyklomatische Komplexität

Hinweis zur Nachnutzung als Open Educational Resource (OER)

Dieser Artikel und seine Texte, Bilder, Grafiken, Code und sonstiger Inhalt sind - sofern nicht anders angegeben - lizenziert unter CC BY 4.0. Nennung gemäß TULLU-Regel bitte wie folgt: “Wie ändert sich das Laufzeitverhalten bei Hochskalierung der verarbeiteten Elemente?” von oer-informatik.de (H. Stein), Lizenz: CC BY 4.0. Der Artikel wurde unter https://oer-informatik.de/laufzeit-komplexitaet veröffentlicht, die Quelltexte sind in weiterverarbeitbarer Form verfügbar im Repository unter https://gitlab.com/oer-informatik/algorithmik/algorithmen. Erstellt mit KI-Assistenz; von mir umfassend redaktionell überarbeitet, geprüft und freigegeben. Stand: 27.10.2026.

[Kommentare zum Artikel lesen, schreiben] / [Artikel teilen] / [gitlab-Issue zum Artikel schreiben]