Komplexitätsfunktionen (O-Notation) 189 / AlgoDS Skript Seite 13

Diese dienen zum abschätzen des (asymptotischen) Verhaltens einer Funktion. Eigentlich werden hiermit Mengen von Funktionen angegeben, aber es hat sich eingebürgert trotzdem $=$ zu schreiben (wenn das $O$ rechts steht). Z.B:

$$5n^{2}+1000n+10^{100}=O\left(n^{2}\right)$$

Obere Schranke

$$O\left(g\left(n\right)\right)=\left\{ f\left(n\right)\vert\exists... ...ists n_{0}>0\forall n>n_{0}:0\leq f\left(n\right)\leq cg\left(n\right)\right\}$$

Untere Schranke

$$\Omega\left(g\left(n\right)\right)=\left\{ f\left(n\right)\vert\e... ...ists n_{0}>0\forall n>n_{0}:0\leq cg\left(n\right)\leq f\left(n\right)\right\}$$

Genaue Schranke

$$\theta\left(g\left(n\right)\right)=O\left(g\left(n\right)\right)\cap\Omega\left(g\left(n\right)\right)$$

Wenn die Untere und Obere Schranke übereinstimmen, kann man dies als Genaue Schranke angeben.

Ergänzung

$$o\left(g\left(n\right)\right)=\left\{ f\left(n\right)\vert\forall c>0\exists n_{0}>0\forall n>n_{0}:0\leq f\left(n\right)<cg\left(n\right)\right\}$$

Gibt eine Funktion an, die auf jeden Fall größer ist als die Eingabefunktion. Sie ist also von einem Höheren Grad als $O\left(g\left(n\right)\right)$.