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

$\mathrm{\Theta }$ -Notation

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

$\mathrm{\Theta }(f(n))=\{g:\mathbb{N}\to \mathbb{N}|\mathrm{\exists }{c}_1\in {ℝ}^{>0},\mathrm{\exists }{c}_2\in {ℝ}^{>0},\mathrm{\exists }{n}_o\in \mathbb{N}\mathrm{\forall }n\ge n_0:c_1\cdot f(n)\ge g(n)\ge c_2\cdot f(n)\}$

Oder etwas kompakter:

$\mathrm{\Theta }(f(n))=O(f(n))\bigcap \mathrm{\Omega }(f(n))$

Anschaulich formuliert bedeutet das, dass $\mathrm{\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: $\mathrm{\Theta }(f(n))\subseteq O(f(n))\cap \mathrm{\Omega }(f(n))und\mathrm{\Theta }(f(n))\supseteq O(f(n))\cap \mathrm{\Omega }(f(n))$

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

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

• $g(n)\in \mathrm{\Theta }(f(n))\Rightarrow \mathrm{\exists }{c}_1,c_2,n_0:\mathrm{\forall }n\ge n_0:c_{1}f(n)\ge g(n)\ge c_{2}f(n)$

$\Rightarrow \mathrm{\exists }{c}_1,n_0:\mathrm{\forall }n\ge n_0:c_{1}f(n)\ge g(n)und\mathrm{\exists }{c}_2,n_0:\mathrm{\forall }n\ge n_0:c_{1}f(n)\ge g(n)\ge c_{2}f(n)$

$\Rightarrow g(n)\in O(f(n))undg(n)\in \mathrm{\Omega }(f(n))$

$\Rightarrow g(n)\in O(f(n))\cap \mathrm{\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\le n^3$

$\Rightarrow 1\le n\text{für}n\ge 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: $\mathrm{\exists }c,n_0\in \mathbb{N}:n^3\le c\cdot n^2,\text{für alle }n>n_0$

$n^3\le c\cdot n^2,\text{für alle }n>n_0$

$\Rightarrow n\le c,\text{für alle }n>n_0$

Wähle $n=c+n_0\Rightarrow c+n_0\le c$ Widerspruch!!

Vorlage:Versteckt