O Kalkül

Diese Notation kann verwendet werden um Laufzeitanalyse eines Programms oder Algorithmus zu beschreiben.

$$\begin{array}{c}\begin{array}{rl}& f\in O(g)\\ & cf\in O(g)\\ & f+c\in O(g)\\ & f+h\in O(\max (f,h))\\ & t\cdot h\in O(\text{ fh })\end{array}\end{array}$$

$f$ ist in $O(g)$ wenn ein $M$ existiert sodass ab einem $n_0$ gilt $|f(n)|\le g(n).$

• Eine Folge $a_n$ ist genau dann beschränkt, wenn $a_n\in O(1)$.
• Eine Folge $b_n\in O(\frac{1}{n})$ ist eine Nullfolge.

Es seien $f_1(n)=g_1(n)+O\left(h_1(n)\right),$ $f_2(n)=g_2(n)+O\left(h_2(n)\right).$ Dann gilt $f_1(n)f_2(n)=g_1(n)g_2(n)+O\left(h_1(n)h_2(n)\right).$

Polynomial → $O((ln(n){)}^{\lambda })$ Exponentiell → $O(n^{\lambda })$

• P → polynomial time
• NP → z.B.: $2^n$
• PSPACE
• EXPTIME → $2^{f(n)}$

Genauer

$$\begin{array}{rl}& O(g):=\left\{f\in M:\exists C>0,\exists n_0>0:|f(n)|\le C|g(n)|\text{ fu¨r alle }n\ge n_0\right\},\\ & \Omega (g):=\left\{f\in M:\exists c>0,\exists n_0>0:|f(n)|\ge c|g(n)|\text{ fu¨r alle }n\ge n_0\right\},\\ & \Theta (g):=O(g)\cap \Omega (g).\end{array}$$