Wachstum statt genauer Zahl
Ob man \(3n + 3\) oder \(2n + 5\) Schritte zählt, hängt davon ab, was man mitzählt. Für große Datenmengen zählt nur, wie schnell die Schrittzahl mit \(n\) wächst.
- Grundidee:nur der am schnellsten wachsende Summand zählt, konstante Faktoren entfallen: \(3n^2 + 5n + 2\) wächst wie \(n^2\).
- O-Notation:\(T(n) \in O(f(n))\), wenn es Konstanten \(c > 0\) und \(n_0\) gibt mit \(T(n) \le c \cdot f(n)\) für alle \(n \ge n_0\).
- Bedeutung:\(f\) ist eine obere Schranke für das Wachstum — gelesen „\(T\) ist von der Ordnung \(f\)“.
- Beispiele:\(3n + 3 \in O(n)\) · \(\frac{n(n-1)}{2} \in O(n^2)\) · \(\lfloor\log_2 n\rfloor + 1 \in O(\log n)\).
Gesucht sind \(c\) und \(n_0\), sodass \(T(n) \le c \cdot n^2\) ab \(n_0\) gilt.
Für \(n \ge 1\) ist \(n \le n^2\) und \(1 \le n^2\) — jeder Summand wird nur größer.
Mit \(c = 10\) und \(n_0 = 1\) ist die Bedingung erfüllt.
Genauso lässt sich jede Summe von Potenzen auf die höchste Potenz zurückführen.
| Klasse | Name | Beispiel | \(n\) verdoppeln |
|---|---|---|---|
| \(O(1)\) | konstant | Zugriff a[i] | gleich |
| \(O(\log n)\) | logarithmisch | binäre Suche | + 1 Schritt |
| \(O(n)\) | linear | lineare Suche, Summe | · 2 |
| \(O(n \log n)\) | n log n | schnelle Sortierverfahren (Mergesort) | etwas mehr als · 2 |
| \(O(n^2)\) | quadratisch | Selection-, Insertion-, Bubblesort | · 4 |
| \(O(2^n)\) | exponentiell | alle Teilmengen durchprobieren | quadriert sich |
Klassen vergleichen
Algorithmus A arbeitet linear, braucht aber pro Element viel: \(c \cdot n\) Schritte. Algorithmus B ist quadratisch mit \(\frac{n^2}{2}\) Schritten. Welcher ist besser?
Stelle mit den Reglern den Ausschnitt bis \(n\) und den Faktor \(c\) von A ein. Beobachte, wo sich A und B schneiden, und vergrößere dann den Ausschnitt Schritt für Schritt bis zu einer Million.
Halte fest: Bei kleinen \(n\) kann der quadratische Algorithmus schneller sein — die Konstante \(c\) verschiebt nur den Schnittpunkt nach \(n = 2c\). Ab dort gewinnt die bessere Wachstumsklasse, und zwar immer deutlicher.
- Abschätzen:Verhältnis \(T(2n) : T(n)\) bilden — bei \(O(n^2)\) etwa 4, bei \(O(n)\) genau 2, bei \(O(\log n)\) nur ein Schritt mehr.
- Hochrechnen:braucht ein \(O(n^2)\)-Verfahren für 10 000 Werte 0,1 s, dann für 100 000 Werte etwa \(10^2 \cdot 0{,}1\,\text{s} = 10\,\text{s}\).
- Exponentiell:schon bei \(n = 60\) über \(10^{18}\) Schritte — praktisch nicht lösbar.
\(T(n) \in O(f(n))\), wenn \(T(n) \le c \cdot f(n)\) für alle \(n \ge n_0\) · \(O(1) \subset O(\log n) \subset O(n) \subset O(n \log n) \subset O(n^2) \subset O(2^n)\)
Allgemeine Hinweise
Keine Konstanten in der Klasse
Man schreibt \(O(n^2)\), nicht \(O(\frac{n^2}{2})\) oder \(O(n^2 + n)\). Die Konstanten sind für die Klasse bedeutungslos — für die tatsächliche Laufzeit bei kleinen \(n\) aber nicht.
Basis des Logarithmus egal
Es gilt \(\log_2 n \approx 3{,}32 \cdot \log_{10} n\). Verschiedene Basen unterscheiden sich nur um einen konstanten Faktor, deshalb schreibt man einfach \(O(\log n)\).
Klasse ist keine Zeitangabe
\(O(n^2)\) sagt nichts über Sekunden. Erst mit einer Messung für ein \(n\) lässt sich die Zeit für ein anderes \(n\) hochrechnen.