Zeit- und Platzklassen

Es gibt zwei wesentliche Fragen, die man sich über ein Programm idR stellt: Wie viel Zeit benötigt es, und wie viel Speicher braucht es dafür. Üblicherweise berechnet man den maximalen Platz bzw. die maximale Zeit in Abhängigkeit der Länge der Eingabe.

Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen Asymptotik, die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor).

Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach "ist ${\cal O}(f)$", wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.