Komplexität – Warum wir Komplexität messen

Technik-Kiste 00-Allgemeines 22. Januar 2026 Zugriffe: 543

Wenn du einen Algorithmus ausführst, hängt sein Zeit- und Ressourcenverbrauch stark davon ab, auf welchem Computer er läuft. Aber wie kannst du unabhängig von der Hardware beurteilen, ob ein Problem „gut“ oder „schlecht“ gelöst wurde? Genau dafür führen wir Schranken für den Ressourcenverbrauch von Algorithmen ein.

Stell dir vor, du hast eine Tüte mit Bonbons. Du möchtest diese zwischen dir und deiner Freundin aufteilen. Dabei ist es egal, welche sie bekommt – entscheidend ist nur, wie viele. Schließlich sind alle gleich lecker.

Um herauszufinden, wie viele Möglichkeiten es gibt, die Bonbons aufzuteilen, hast du unterschiedliche Algorithmen geschrieben. Jetzt willst du wissen:

Welcher Algorithmus ist besser geeignet?
Wie viele Berechnungsschritte brauchen die beiden Verfahren, wenn du zum Beispiel zehn Bonbons aufteilen möchtest?

💡kleiner Fakt: Es gibt immer n – 1 Möglichkeiten, also genau eine Möglichkeit weniger als es Bonbons gibt.

Zu jedem lösbaren Problem existieren unendlich viele Algorithmen. Das erkennst du leicht in einem kleinen Gedankenspiel: Wenn dir jemand einen Algorithmus gibt, kannst du jederzeit einen neuen schreiben, der exakt dasselbe Ergebnis liefert – selbst, wenn du nur eine überflüssige Zeile wie anzahl := anzahl einfügst.

Natürlich sind solche Änderungen nicht sinnvoll. In der Praxis geht es darum, effiziente Lösungen zu finden. Ein Algorithmus muss nicht nur korrekt sein, sondern auch mit möglichst wenig Ressourcen auskommen. Dabei ist die Laufzeit meist wichtiger als der Speicherverbrauch – denn Speicher ist heutzutage günstig, während lange Wartezeiten nerven.

Wenn zwei Algorithmen dasselbe Ergebnis liefern, aber einer schneller ist, gilt er als der bessere. Deshalb vergleichen wir im Folgenden die Laufzeit von Algorithmen.

Eingabegröße: Warum sie entscheidend ist

Stell dir vor, du hast ein Stapel Karten mit verschiedenen Symbolen darauf – zum Beispiel fünf Karten mit Tieren: Hund, Katze, Maus, Vogel und Fisch. Du mischst die Karten und sortierst sie anschließend wieder, indem du immer das „kleinste“ Tier nach deiner Reihenfolge suchst und vorne ablegst. Das dauert ein bisschen.

Jetzt mach denselben Versuch mit zehn Karten. Du wirst merken: Es braucht deutlich länger. Genau so verhält es sich mit Algorithmen – je größer die Eingabe, desto mehr Arbeit steckt in der Berechnung.

Aber was bedeutet eigentlich „Eingabegröße“?

Formale Sicht: Man könnte sagen, die Eingabegröße ist der Speicherplatz, den die Eingabe benötigt.
Praktische Sicht: Häufig ist es einfacher, einfach die Anzahl der Eingabewerte zu zählen. Ob du eine Zahl „1“ oder „1000“ hast, spielt dabei keine große Rolle – beide gelten als ein Element.
Alternative Sicht: Manchmal betrachten wir direkt den Wert einer Zahl als Eingabegröße. Wenn dein Algorithmus nur eine Zahl n bekommt, dann hängt die Laufzeit direkt davon ab, wie groß n ist.

Je nach Problem definieren wir die Eingabegröße also unterschiedlich:

Bei Texten ist es die Länge der Zeichenkette.
Bei Graphen zählen wir Knoten und Kanten.
Bei Bildern könnte es die Breite und Höhe sein.

Das Prinzip bleibt gleich: Je größer die Eingabe, desto länger dauert die Berechnung.

Allerdings ist es nicht immer so eindeutig. Zwei Eingaben mit gleicher Größe können unterschiedlich lange Laufzeiten verursachen. Beispiel: Ein Sortieralgorithmus kann extrem schnell sein, wenn die Liste schon sortiert ist, aber deutlich länger brauchen, wenn alles durcheinander liegt.

Darum unterscheiden wir drei Fälle:

Best Case: Die Eingabe ist besonders günstig, der Algorithmus läuft sehr schnell.
Average Case: Wir betrachten die durchschnittliche Laufzeit über viele Eingaben.
Worst Case: Wir nehmen den schlimmsten Fall an und messen, wie lange der Algorithmus maximal braucht.

Für die Analyse ist der Worst Case meist am interessantesten – denn er garantiert dir, dass der Algorithmus auch unter ungünstigen Bedingungen noch in akzeptabler Zeit fertig wird.

Messen der Laufzeit

Die einfachste Möglichkeit, die Laufzeit eines Algorithmus zu bestimmen, ist: du misst sie direkt. Nimm dir ein Beispiel, führe den Algorithmus mit verschiedenen Eingaben aus und stoppe die Zeit.

Vielleicht hast du schon gemerkt: Zwei Personen sortieren dieselbe Kartenliste unterschiedlich schnell. Genauso verhält es sich bei Computern. Die Laufzeit hängt von vielen Faktoren ab – Prozessorleistung, Betriebssystem, Hintergrundprogramme und vielem mehr.

Ein anschauliches Beispiel:

Auf deinem Handy läuft ein Algorithmus vielleicht spürbar langsamer, weil der Prozessor weniger Leistung hat.
Auf einem High-End-PC mit starker Hardware wirkt derselbe Algorithmus plötzlich blitzschnell.

Die gemessene Zeit ist also immer nur ein Wert für genau diese Umgebung. Sie sagt dir, wie schnell der Algorithmus dort war – aber nicht, wie er sich auf einem anderen System verhält.

Trotzdem ist das Messen nützlich: Wenn du wissen willst, wie sich ein Algorithmus in deiner konkreten Umgebung schlägt, liefert dir die praktische Messung wertvolle Informationen. Für die theoretische Analyse reicht das aber nicht. Dort wollen wir Aussagen treffen, die unabhängig von der Hardware gelten.

Um wirklich zu verstehen, wie sich ein Algorithmus verhält, müssen wir seine Laufzeit berechnen – und zwar so, dass die Ergebnisse nicht von deinem Handy oder einem High-End-PC abhängen. Wir wollen ein Modell, das zeigt, wie sich die Laufzeit mit wachsender Eingabegröße verändert.

Im nächsten Kapitel schauen wir uns deshalb an, wie man die Laufzeit von Algorithmen abstrakt beschreibt und berechnet.

Berechnen der Laufzeit

Wir haben bereits gesehen: Die Laufzeit eines Algorithmus hängt von der Eingabegröße ab. Um das genauer zu fassen, beschreiben wir die Laufzeit als Funktion:

Eingabe: die Größe der Daten, die du verarbeitest
Ausgabe: die längste Laufzeit, die der Algorithmus für eine Eingabe dieser Größe benötigt

Beispiel: Zwei verschiedene Ansätze

Stell dir vor, du hast zwei Algorithmen, die beide dasselbe Problem lösen sollen – etwa das Verteilen von Aufgaben in einer Lerngruppe.

Algorithmus 1 arbeitet mit zwei ineinander verschachtelten Schleifen. Für jede Person wird jede mögliche Verteilung geprüft. Das bedeutet: Bei n Personen werden n² Kombinationen durchlaufen. Die Schrittanzahl wächst also quadratisch.
Algorithmus 2 nutzt eine direkte Berechnung. Er prüft nur wenige Bedingungen und liefert das Ergebnis in linearer Zeit, also mit ungefähr 3n + 2 Schritten.

Wenn du beide Funktionen vergleichst, siehst du sofort: Algorithmus 2 ist für kleine Eingaben deutlich schneller.

Visualisierung der Laufzeiten von Algorithmus 1 und 2. Quelle: Technik-Kiste.de

Vorsicht: Der Schein kann trügen

Ein Diagramm der Laufzeiten kann jedoch täuschen. Stell dir zwei weitere Algorithmen vor:

Algorithmus A mit Laufzeit 20n²
Algorithmus B mit Laufzeit 2n

Für kleine Eingaben (z. B. n = 1 bis 512) wirkt Algorithmus B klar überlegen. Doch ab einer bestimmten Größe kippt das Bild: Schon bei n = 1024 ist B plötzlich langsamer als A – und für noch größere Eingaben scheint B gar nicht mehr praktikabel.

Visualisierung zweier Algorithmen mit stark ansteigender Laufzeit. Quelle: Technik-Kiste.de

Das zeigt: Es reicht nicht, nur ein paar Werte auszurechnen. Wir müssen verstehen, wie sich die Laufzeit langfristig entwickelt.

Langfristiges Verhalten

In der Mathematik bedeutet „langfristig“: Wir betrachten das Verhalten der Laufzeitfunktion für n à ∞ in Form der Bestimmung des Limes.

💡Was bedeutet Limes?

Wenn wir eine Funktion f(n) betrachten, dann fragen wir uns: Was passiert mit dem Funktionswert, wenn n immer größer wird – also gegen unendlich geht?

Der Limes beschreibt genau diesen Grenzwert. Er sagt uns, welchem Wert sich die Funktion annähert, wenn die Eingabe beliebig groß wird. Berechnet wird dieser durch folgende Formel:

Formel zur Berechnung des Limes. Quelle: Technik-Kiste.de

Wenn du zwei Algorithmen A und B mit ihren jeweiligen Schrittzahlen vergleichen willst, dann bildest du den Quotienten und betrachtest den Limes für n à ∞.

Das Ergebnis dieses Limes ist der Grenzwert, der dir zeigt, wie sich die beiden Laufzeiten im Verhältnis zueinander entwickeln, wenn die Eingabegröße immer weiterwächst:

Bedeutung der Ergebnisse der Formel. Quelle: Technik-Kiste.de

Ein normaler Taschenrechner kann kein „Grenzwert für n à ∞.“ direkt berechnen. Aber du kannst einfach sehr große Zahlen einsetzen, z. B. n=1000, n=10,000, n=100,000.

Du siehst dann: Der Wert wächst immer weiter. Damit weißt du, dass der Limes gegen unendlich geht. Probiere es doch einfach mal aus!

Zurück zu unseren Beispielen:

Vergleichen wir f(n) = 3n² + n + 2 mit g(n) = 3n + 2, dann wächst f(n) unendlich viel schneller als g(n).
Vergleichen wir weitere Laufzeiten anderer Algorithmen wie c(n) = 20n² mit d(n) = 2n, dann ist c(n) für große n unendlich viel kleiner als d(n).
Vergleichen wir f(n) mit c(n), unterscheiden sie sich nur durch einen konstanten Faktor. Beide wachsen gleich schnell, nur dass f(n) etwas „kompakter“ ist.

Was bedeutet das praktisch?

Wenn zwei Algorithmen sich nur durch einen konstanten Faktor unterscheiden, kann ein schnellerer Computer den Unterschied ausgleichen.
Wenn sich die Wachstumsraten aber grundsätzlich unterscheiden (z. B. quadratisch vs. linear), hilft auch die beste Hardware nichts – der Unterschied bleibt für große Eingaben bestehen.

Die Landau-Notation: Laufzeiten clever vergleichen

Du hast gelernt, wie man mit dem Limes das Wachstum zweier Funktionen vergleichen kann. Aber mal ehrlich: Willst du wirklich jedes Mal Grenzwerte berechnen, nur um zu wissen, welcher Algorithmus schneller ist?

Zum Glück gibt’s eine Abkürzung: die Landau-Notation, auch bekannt als Groß-O-Notation. Sie erlaubt dir, Algorithmen in Laufzeitklassen einzuteilen – also in Gruppen von Funktionen, die sich langfristig ähnlich verhalten.

Wann verwende ich welches Zeichen?

Hier eine einfache Übersicht in einem Satz je Symbol:

O(f): Verwende das große O, wenn du sagen willst, dass ein Algorithmus höchstens so schnell wächst wie f(n) – also eine obere Schranke.
Ω(f): Verwende das große Omega, wenn du ausdrücken willst, dass ein Algorithmus mindestens so schnell wächst wie f(n) – also eine untere Schranke.
Θ(f): Verwende das große Theta, wenn du zeigen willst, dass ein Algorithmus genauso schnell wächst wie f(n), bis auf einen konstanten Faktor – also eine exakte Schranke.

Beispiel: Drei Algorithmen, drei Klassen

Stell dir vor, du hast drei Algorithmen zur Berechnung von Bonuspunkten in einem Spiel:

Algorithmus A prüft für jede Kombination von Spielern alle möglichen Punktverteilungen → Laufzeit: n² + 3n + 5
Algorithmus B zählt einfach die Spieler durch → Laufzeit: 5n + 2
Algorithmus C gibt immer denselben Wert zurück → Laufzeit: konstant, z. B. 7

Dann gilt anhand der Polynome:

A gehört zur Klasse O(n²)
B gehört zur Klasse O(n)
C gehört zur Klasse O(1)

Und wenn du A und B vergleichst, kannst du sagen:

A ist Ω(n²), weil es mindestens quadratisch wächst
B ist Θ(n), weil es exakt linear wächst

Was ist ein Polynom?

Ein Polynom ist einfach eine Summe von Potenzen einer Variablen mit Zahlen davor. Zum Beispiel:

f(n) = 2n³ + 5n² + 7n + 1

Hier ist n die Variable, und die Exponenten 3, 2, 1, 0 bestimmen, wie schnell die einzelnen Terme wachsen.

💡Wichtig: Für große n dominiert immer der höchste Exponent – der sogenannte führende Term.

Beispiel: Zwei Polynome vergleichen

Nimm diese beiden Funktionen:

f(n) = n⁵+ 4n² + n + 3

g(n) = 6n⁴+ 100n³

Der höchste Exponent bei f(n) ist 5, bei g(n) ist es 4.
→ Also wächst f(n) langfristig schneller als g(n).

Warum nicht einfach immer O(n⁵) schreiben?

Klar, du könntest sagen: „Mein Algorithmus ist in O(n⁵).“ Aber wenn er in Wahrheit nur O(n²) braucht, wäre das eine viel zu grobe Schätzung.

Deshalb suchen wir in der Analyse nach einer asymptotisch möglichst genauen Schranke – also einer Funktion, die das tatsächliche Laufzeitverhalten so eng wie möglich beschreibt, ohne es zu unterschätzen.

Quantoren: Aussagen über viele Werte

Bisher hast du mit logischen Aussagen gearbeitet, die sich auf einzelne Werte beziehen. Zum Beispiel:

f(x) > 5

Das ist eine Aussage über den Funktionswert an einer bestimmten Stelle x. Sie kann wahr oder falsch sein – je nachdem, welchen Wert x hat.

Mit Quantoren kannst du solche Aussagen verallgemeinern und festlegen, für welche Werte sie gelten sollen.

Die beiden wichtigsten Quantoren

Allquantor (∀)– „für alle“
Damit sagst du: Die Aussage gilt für alle Werte einer bestimmten Menge. Beispiel:

∀x: f(x) > 6

→ Für alle natürlichen Zahlen x ist der Funktionswert größer als 6.

Existenzquantor (∃) – „es existiert“
Damit sagst du: Es gibt mindestens einen Wert, für den die Aussage gilt. Beispiel:

∃x: f(x) > 6

→ Es gibt mindestens eine natürliche Zahl x, für die f(x) größer als 6 ist.

Bereich einschränken

Du kannst auch festlegen, aus welchem Bereich die Variable stammt:

∀x ∈ N: für alle natürlichen Zahlen
∃x > 20: es gibt ein x, das größer als 20 ist

Und wenn du mehrere Variablen brauchst, kannst du einfach mehrere Quantoren hintereinanderschreiben:

∀x ∈ N ∃y ∈ N: x < y

→ Für jede natürliche Zahl x gibt es eine größere Zahl y.

Wichtig: Die Reihenfolge der Quantoren ist entscheidend.

∀x ∃y: x < y bedeutet: zu jedem x gibt es ein größeres y.
∃y ∀x: x < y würde behaupten, dass es ein y gibt, das größer ist als alle x – was nicht stimmt.

Quantoren in der Landau-Notation

Die Definition der Menge O(f) klingt zunächst sperrig, wird aber mit Quantoren klar:

∃c > 0 ∃n₀≥ 0∀n > n₀: g(n) ≤ c * f(n)

Das bedeutet:

Es gibt eine Konstante c, die größer als 0 ist und als Faktor dient.
Es gibt eine Konstante n₀, die den Startpunkt festlegt und mindestens 0 beträgt.
Für alle Eingaben n größer als n₀ gilt: g(n) wächst nicht schneller als ein Vielfaches von f(n).

Bedeutung von n₀ und c

n₀: Ab dieser Eingabegröße gilt die Aussage zuverlässig. Vorher können sich die Funktionen noch kreuzen.
c: Ein konstanter Faktor, der Unterschiede wie „Computer ist (c)-mal schneller“ beschreibt. Solche Unterschiede ignorieren wir, weil uns nur das grundsätzliche Wachstum interessiert.

Von konstant bis exponentiell: Typische Laufzeiten von Algorithmen

Nachdem du die Grundlagen der Landau-Notation kennengelernt hast, stellt sich die Frage: Wie wendest du sie praktisch an, um Algorithmen zu analysieren?

Die gute Nachricht: Du musst nicht immer jeden einzelnen Befehl zählen. In der Regel genügt es, darauf zu achten, wie viele Schleifen über die Eingabegröße laufen und ob sie verschachtelt sind. Daraus lassen sich die typischen Laufzeitklassen leicht ableiten.

Konstante Laufzeit – O(1)

Ein Algorithmus läuft in konstanter Zeit, wenn er unabhängig von der Eingabegröße immer gleich viele Schritte benötigt.

Beispiel: Du greifst direkt auf ein bestimmtes Element in einer Liste zu.
Beispiel: Eine einfache Addition zweier Zahlen.

Lineare Laufzeit – O(n)

Eine einzelne Schleife über die Eingabegröße (n) führt zu linearer Laufzeit.

Beispiel: Du durchsuchst ein unsortiertes Array nach dem kleinsten Wert.
Jeder Schritt hängt direkt von der Anzahl der Elemente ab.

Quadratische Laufzeit – O(n²)

Zwei ineinander verschachtelte Schleifen über (n) ergeben quadratische Laufzeit.

Beispiel: Du vergleichst jedes Element einer Liste mit jedem anderen.
Viele einfache Sortierverfahren (wie Bubble Sort oder Selection Sort) liegen in dieser Klasse.

Logarithmische Laufzeit – O(log n)

Manchmal halbierst du die Eingabegröße bei jedem Schritt.

Beispiel: Du suchst einen Wert in einem bereits sortierten Array mit der Binärsuche.
Jeder Schritt reduziert die Menge drastisch, sodass die Laufzeit nur langsam wächst.

Lineareithmetische Laufzeit – O(n log n)

Diese Laufzeit taucht bei vielen effizienten Sortieralgorithmen auf.

Beispiel: Mergesort oder Quicksort.
Sie kombinieren lineares Durchlaufen mit einer logarithmischen Struktur.

Exponentielle Laufzeit – O(2ⁿ)

Wenn du für jede Eingabe alle möglichen Lösungen ausprobierst, wächst die Laufzeit extrem schnell.

Beispiel: Du testest alle möglichen Belegungen für n Variablen einer logischen Formel.
Schon kleine Eingaben führen zu riesigen Laufzeiten.

Fakultätslaufzeit – O(n!)

Noch schlimmer wird es, wenn du alle möglichen Reihenfolgen durchprobierst.

Beispiel: Du berechnest die kürzeste Rundreise durch n Städte, indem du alle möglichen Touren ausprobierst.
Die Anzahl der Möglichkeiten wächst schneller als jede Exponentialfunktion.

Warum Laufzeitklassen wichtig sind

Um zu verdeutlichen, wie stark sich diese Unterschiede auswirken, hier ein Vergleich:

Ein Algorithmus mit O(log n) braucht selbst bei (n = 10,000) nur Mikrosekunden.
Ein Algorithmus mit O(n²) benötigt bei derselben Eingabegröße schon mehrere Sekunden.
Ein Algorithmus mit O(2ⁿ) würde bei (n = 83) länger laufen, als unser Universum bisher existiert hat.

Das zeigt: Schnellere Computer helfen nur begrenzt. Entscheidend ist die Laufzeitklasse des Algorithmus.