Analyse von Algorithmen

Definitionen:
- Das Logarithmische Kostenmaß beschreibt die Komplexität proportional zur Anzahl an Bitoperationen.
- Das Einheitskostenmaß beschreibt die Komplexität proportional zu elementaren Operationen, die i.A. Vergleiche und arithmetische Operationen einer Random Access Machine umfassen. Die Kosten einer elementaren Operation sind konstant, also $O(1)$.

Vorsicht:
Die Berechnung der Zahl $n!$ lässt sich nicht mit dem Einheitskostenmaß abschätzen, da $n!$ aus $\log(n!) = n \log n$ Bits besteht:
$\log n! =_{Stirling} \log (\sqrt{2 \pi n} (n/e)^n) = ... = n \log n - O(n)$

Das Einheitskostenmaß darf nur dann verwendet werden, wenn die Ausgabe nicht um Ordnungen größer als die Eingabe ist.

Definitionen:
- Eine Worst Case Analyse schätzt die Komplexität des schlimmstmöglichen Falles ab.
- Eine Average Case Analyse schätzt die durchschnittlich zu erwartende (Erwartungswert!) Komplexität ab.