Landau-Notation: Wachstumsraten
Eingaben
| Eingabegröße n | 20 |
|---|
Landau-Notation: Wachstumsraten
Eingabegröße n eingeben und vergleichen, wie viele Operationen die gängigen Zeitkomplexitätsklassen erfordern — von O(log n) bis O(n!).
Eingaben
Eingabegröße
Ergebnisse
Geben Sie einen Wert ein, um die Ergebnisse zu sehen.
Gängige Komplexitäten
Extremes Wachstum
Landau-Notation: Wachstumsraten
Die Landau-Notation (O-Notation) klassifiziert, wie der Ressourcenbedarf eines Algorithmus mit der Eingabegröße skaliert. Anstatt Sekunden auf einer bestimmten Maschine zu messen, erfasst sie die Form des Wachstums — verdoppelt sich der Aufwand, wenn n verdoppelt wird, oder vervierfacht er sich? Die sechs Komplexitätsklassen unten sind die in Lehrbüchern und Bewerbungsgesprächen am häufigsten anzutreffenden.
Die sechs gängigen Klassen
O(log n) — Logarithmisch. Jeder Schritt eliminiert einen konstanten Bruchteil der verbleibenden Arbeit. Eine binäre Suche auf einem sortierten Array mit einer Milliarde Elementen benötigt nur 30 Vergleiche, weil bei jedem Schritt der Suchraum halbiert wird. Balancierte Suchbäume und viele Teile-und-herrsche-Rekurrenzen fallen in diese Klasse.
O(n) — Linear. Der Aufwand wächst proportional zur Eingabegröße. Ein einmaliges Durchlaufen eines Arrays zur Suche des Maximums, das Zählen von Zeichen in einer Zeichenkette oder das Lesen jedes Elements einer Liste sind linear. Lineare Algorithmen gelten im Allgemeinen als effizient.
O(n log n) — Linearithmisch. Die häufigste Komplexität beim Sortieren. Mergesort, Heapsort und Timsort (verwendet in Python und Java) erreichen alle O(n log n), was auch die theoretische untere Schranke für vergleichsbasiertes Sortieren ist. Bei sind das etwa zwanzig Millionen Operationen — in der Praxis schnell.
O(n²) — Quadratisch. Zwei verschachtelte Schleifen über die Eingabe. Bubblesort, Insertionsort und die naive Matrizenmultiplikation haben alle O(n²) im schlechtesten Fall. Bei sind das hundert Millionen Operationen; bei eine Billion — für große Datenmengen unpraktikabel.
O(2ⁿ) — Exponentiell. Der Aufwand verdoppelt sich mit jedem zusätzlichen Element. Der naive rekursive Fibonacci-Algorithmus berechnet Teilprobleme exponentiell neu; die Brute-Force-Aufzählung aller Teilmengen einer Menge wächst ebenfalls als . Bei n = 40 übersteigt die Anzahl eine Billion.
O(n!) — Faktoriell. Die am schnellsten wachsende Klasse in der alltäglichen Algorithmenanalyse. Brute-Force-Lösungen für Permutationsprobleme — die Aufzählung jeder möglichen Tour beim Travelling-Salesman-Problem — führen eine Operation pro Permutation durch, und es gibt Permutationen. Bei n = 20 übersteigt die Anzahl zwei Trilliarden Operationen.
Rechenbeispiel bei n = 20
Das Verhältnis zwischen O(n log n) und O(n!) bei n = 20 beträgt etwa — der Unterschied zwischen einem schnellen Sortiervorgang und einer Wartezeit, die das Alter des Universums übertrifft.
Praktische Orientierung
Konstanten und Cache-Effekte spielen bei kleinem n eine Rolle; die Komplexität dominiert bei großem n. Ein Richtwert von etwa n = 10.000 markiert den Bereich, ab dem O(n²) auf moderner Hardware (bei einfachen Operationen) spürbar wird. Jenseits von n = 10^6 ist im Allgemeinen ein O(n log n)-Algorithmus oder besser erforderlich. Exponentielle und faktorielle Algorithmen erfordern für reale Eingaben Approximationen, dynamische Programmierung oder Beschneidungsstrategien.
Zahlenbasis-Konverter ist nützlich, wenn mit binären Darstellungen des Eingaberaums gearbeitet wird.
Häufig gestellte Fragen (FAQ)
Was misst die Landau-Notation tatsächlich?
Die Landau-Notation (O-Notation, Big-O) beschreibt die obere Schranke, mit der die Laufzeit (oder der Speicherbedarf) eines Algorithmus mit wachsender Eingabegröße n zunimmt. Konstante Faktoren und Terme niedrigerer Ordnung werden dabei bewusst ignoriert, da sie bei großem n immer weniger ins Gewicht fallen.
Ein O(n²)-Algorithmus wird bei hinreichend großen Eingaben stets einen O(n log n)-Algorithmus übertreffen, unabhängig von der Hardwaregeschwindigkeit. Die O-Notation ist ein Werkzeug zum Vergleich von Algorithmusentwürfen — keine exakte Vorhersage der Wanduhrzeit.
Warum wird der Logarithmus zur Basis 2 verwendet?
Die meisten Teile-und-herrsche-Algorithmen (binäre Suche, Mergesort, ausgeglichene Suchbäume) halbieren ihre Arbeit bei jedem Schritt; die Tiefe dieser Aufteilung ist daher log₂ n. In der O-Analyse ist die Logarithmusbasis nur ein konstanter Faktor, der die Komplexitätsklasse nicht verändert — log₂ n und log₁₀ n unterscheiden sich nur um eine Konstante.
Die Basis 2 ist in der Informatik jedoch konventionell, da sie der binären Aufteilung entspricht. Dieser Rechner verwendet Basis 2, um dieser Konvention zu folgen.
Ab welcher Eingabegröße wird die Komplexität relevant?
Bei kleinen Eingaben, etwa n < 50, übertrifft ein gut optimierter O(n²)-Algorithmus häufig einen theoretisch schnelleren O(n log n)-Algorithmus, da er geringeren konstanten Aufwand und besseres Cache-Verhalten hat. Komplexität beginnt zu dominieren, sobald n in den Hundert- oder Tausenderbereich reicht.
Bei n = 1.000 führt ein O(n log n)-Sortieralgorithmus etwa 10.000 Vergleiche durch, ein O(n²)-Algorithmus hingegen 1.000.000. Bei n = 1.000.000 beträgt das Verhältnis eine Milliarde zu einer Billion — die Komplexität ist dann das einzig Ausschlaggebende.
Werden O(n!)-Algorithmen in der Praxis eingesetzt?
O(n!)-Algorithmen sind für alle bis auf die kleinsten Eingaben unpraktikabel. Bei n = 20 übersteigt n! zwei Trillionen Operationen — weit jenseits dessen, was ein Computer in einer menschlichen Lebensspanne abarbeiten kann.
In der Praxis werden NP-schwere Probleme wie das Travelling-Salesman-Problem mit Approximationsalgorithmen, Heuristiken oder dynamischer Programmierung gelöst, um die vollständige Aufzählung aller Permutationen zu vermeiden. Die Faktorialspalte in diesem Rechner verdeutlicht, warum diese Näherungsverfahren existieren.