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 |
O-Notation: Für große \(n\) zählt nur der am schnellsten wachsende Summand, konstante Faktoren entfallen: \(3n^2+5n+2\) wächst wie \(n^2\).
Definition: \(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\). \(f\) ist eine obere Schranke für das Wachstum.
Klassen: \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n\log n)\), \(O(n^2)\), \(O(2^n)\) — von langsam nach schnell wachsend.
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.
- Exponentiell:schon bei \(n = 60\) über \(10^{18}\) Schritte — praktisch nicht lösbar.
Definition: \(T(n)\in O(f(n))\), wenn \(T(n)\le c\cdot f(n)\) für alle \(n\ge n_0\).
Rangfolge: \(O(1)\subset O(\log n)\subset O(n)\subset O(n\log n)\subset O(n^2)\subset O(2^n)\)
Vergleich: Bei kleinen \(n\) kann der quadratische Algorithmus schneller sein; die Konstante \(c\) verschiebt nur den Schnittpunkt. Ab dort gewinnt die bessere Wachstumsklasse immer deutlicher.
Abschätzen: Verhältnis \(T(2n):T(n)\): bei \(O(n^2)\) etwa 4, bei \(O(n)\) genau 2.
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.