Kurs:Algorithmen und Datenstrukturen/Vorlesung/Theta-Notation

Aus Wikiversity
Zur Navigation springen Zur Suche springen




-Notation[Bearbeiten]

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

Oder etwas kompakter:

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

Beweis[Bearbeiten]

Zu zeigen:


Zeige

Beispiel 1[Bearbeiten]

Wir stellen uns die Frage, ob bzw. ob eine obere Schranke für ist. Die Antwort ist ja. Die Begründung dazu lautet folgendermaßen:

Beispiel 2[Bearbeiten]

Wir stellen uns die Frage, ob bzw. ob eine obere Schranke für ist. Die Antwort ist nein. Beweisen kann man das durch Widerspruch. Unsere Annahme ist:

Wähle Widerspruch!!


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg