Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Theta-Notation

$\Theta$ -Notation

Die exakte Ordnung $\Theta$ von f(n) ist definiert als:

$\Theta (f(n))=\{g:\mathbb {N} \to \mathbb {N} |\exists c_{1}\in \mathbb {R} ^{>0},\exists c_{2}\in \mathbb {R} ^{>0},\exists n_{o}\in \mathbb {N} \ \forall n\geq n_{0}:c_{1}\cdot f(n)\geq g(n)\geq c_{2}\cdot f(n)\}$

Oder etwas kompakter:

$\Theta (f(n))=O(f(n))\bigcap \Omega (f(n))$

Anschaulich formuliert bedeutet das, dass $\Theta$ die Menge aller durch f nach unten und oben beschränkter Funktionen und somit die asymptotische untere und obere Schranke ist.

Beweis

Zu zeigen: $\Theta (f(n))\subseteq O(f(n))\cap \Omega (f(n))~und~\Theta (f(n))\supseteq O(f(n))\cap \Omega (f(n))$

$\Theta (f(n))\subseteq O(f(n))\cap \Omega (f(n)):$

Zeige $g(n)\in \Theta (f(n))\Rightarrow g(n)\in O(f(n))\cap \Omega (f(n)).$

$g(n)\in \Theta (f(n))\Rightarrow \exists c_{1},c_{2},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)\geq c_{2}f(n)$

$\Rightarrow \exists c_{1},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)~und~\exists c_{2},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)\geq c_{2}f(n)$

$\Rightarrow g(n)\in O(f(n))~und~g(n)\in \Omega (f(n))$

$\Rightarrow g(n)\in O(f(n))\cap \Omega (f(n))$

Beispiel 1

Wir stellen uns die Frage, ob $n^{2}\in O(n^{3})$ bzw. ob $n^{3}$ eine obere Schranke für $n^{2}$ ist. Die Antwort ist ja. Die Begründung dazu lautet folgendermaßen:

$n_{0}=1,c=1$

$\Rightarrow n^{2}\leq n^{3}$

$\Rightarrow 1\leq n\ {\text{für}}\ n\geq 1$

Beispiel 2

Wir stellen uns die Frage, ob $n^{3}\in O(n^{2})$ bzw. ob $n^{2}$ eine obere Schranke für $n^{3}$ ist. Die Antwort ist nein. Beweisen kann man das durch Widerspruch. Unsere Annahme ist: $\exists c,n_{0}\in \mathbb {N} :n^{3}\leq c\cdot n^{2},{\text{für alle }}n>n_{0}$