O-Notation
Die wichtigsten O-funktionen:
- konstanter Aufwand: 1
- logarithmisches Wachstum: log N
- lineares Wachstum: N
- N-log-N Wachstum: N*logN
- quadratisches, kubisches, .... Wachstum: N2,N3,....
- exponentielles Wachstum: 2N,3N
Generell gilt:
Polynomial lösbare Probleme sind effizient und Probleme mit
exponentiellen Aufwand sind ineffizient!
| Aufwand | Problemklasse |
| 0(1) | einige Suchverfahren für Tabellen (Hashing) |
| O(log n) | allgemeine Suchverfahren für Tabellen (Baum-Suchverfahren) |
| O(n) | squenzielle Suche, Suche in Texten, syntaktische Analyse von Programmen (bei "guter" Grammatik) |
| O(n.logn) | Sortieren |
| O(n2) | einige dynamische Optimierungsverfahren (z.B. optimale Suchbäume), Multiplikation Matrix-Vektor (einfach) |
| O(n3) | Matrizen-Multiplikation (einfach) |
| O(2n) | viele Optimierungsprobleme (zB. optimale Schaltwerke), autmatisches Beweisen |
Attach:laufzeitkomplexitaet.pdf
