Grundlagen der Informatik

O-Kalkül

Mathematischer Beschreibungsformalismus für die Komplexität einer Funktion. Das O-Kalkül beurteilt ausschließlich die asymptotische Komplexität einer Funktion f(n), d.h. die Entwicklung der Funktionswerte für sehr große n. Die abgeleiteten Komplexitätsklassen abstrahieren von sämtlichen konstanten Faktoren in einer Funktion und eignen sich daher sowohl implämentierungsunabhängigen Beschreibung der Laufzeit als auch des Platzverbrauchs einer Hardwareschaltung.

Diskussion