 | Generell ist es sehr sinnvoll, den Rechenzeitaufwand eines
Algorithmus in Abhängigkeit von n (Datenumfang oder
andere entscheidende Problemgröße) abzuschätzen.
|
| Hierzu eignet sich die von Paul Bachmann 1894 eingeführte
O-Notation an:
g(n) = O(f(n)) für n  N, falls
 M, n0 N, so daß gilt
| g(n) |  | M f(n) |  n  n0.
|
| Einige Beispiele:
| O(1) | konstanter Aufwand, unabhängig von n |
| O(n) | linearer Aufwand (z.B. Einlesen von n Zahlen) |
| O(n ln n) | Aufwand guter Sortierverfahren (z.B. Quicksort) |
| O(n2) | quadratischer Aufwand |
| O(nk) | polynomialer Aufwand (bei festem k) |
| O(2n) | exponentieller Aufwand |
| O(n!) | Bestimmung aller Permutationen von n Elementen |
|
| Die O-Notation hilft insbesondere bei der Beurteilung, ob
ein Algorithmus für großes n noch geeignet ist bzw.
erlaubt einen Effizienz-Vergleich zwischen verschiedenen
Algorithmen für große n.
|
![[Vorheriges Kapitel]](pprev.gif)
![[Vorherige Seite]](prev.gif)
![[Inhaltsverzeichnis]](up.gif)
![[Nächste Seite]](next.gif)
![[Nächstes Kapitel]](nnext.gif)