O Kalkül

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

f∈O(g)cf∈O(g)f+c∈O(g)f+h∈O(max⁡(f,h))t⋅h∈O( fh )\begin{equation} \begin{aligned} &f \in O(g) \\ &c f \in O(g) \\ &f+c \in O(g) \\ &f+h \in O(\operatorname{max}(f, h)) \\ &t \cdot h \in O(\text { fh }) \end{aligned} \end{equation}

ff ist in O(g)O(g) wenn ein MM existiert sodass ab einem n0n_0 gilt

∣f(n)∣≤g(n).|f(n)|\leq g(n).
  • Eine Folge ana_n ist genau dann beschränkt, wenn an∈O(1)a_n\in O(1).
  • Eine Folge bn∈O(1n)b_n\in O(\frac{1}{n}) ist eine Nullfolge.

Es seien

f1(n)=g1(n)+O(h1(n)),f_1(n)=g_1(n)+O\left(h_1(n)\right), f2(n)=g2(n)+O(h2(n)).f_2(n)=g_2(n)+O\left(h_2(n)\right).

Dann gilt

f1(n)f2(n)=g1(n)g2(n)+O(h1(n)h2(n)).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))λ)O((ln(n))^\lambda) Exponentiell → O(nλ)O(n^\lambda)

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

Genauer

O(g):={f∈M:∃C>0,∃n0>0:∣f(n)∣≤C∣g(n)∣ fu¨r alle n≥n0},Ω(g):={f∈M:∃c>0,∃n0>0:∣f(n)∣≥c∣g(n)∣ fu¨r alle n≥n0},Θ(g):=O(g)∩Ω(g).\begin{aligned} &O(g):=\left\{f \in M: \exists C>0, \exists n_{0}>0:|f(n)| \leq C|g(n)| \text { für alle } n \geq n_{0}\right\}, \\ &\Omega(g):=\left\{f \in M: \exists c>0, \exists n_{0}>0:|f(n)| \geq c|g(n)| \text { für alle } n \geq n_{0}\right\}, \\ &\Theta(g):=O(g) \cap \Omega(g) . \end{aligned}