„Benutzer Diskussion:Matthäus Gdaniec“ – Versionsunterschied

Beispiele

In den folgenden Beispielen ist $f=f(x)$ stets als Funktion von $x$ zu verstehen.

Notation	Bedeutung	Anschauliche Erklärung	Beispiele für Laufzeiten
$f\in {\mathcal {O}}(1)$	$f$ ist konstant	$f$ wächst nicht, wenn sich das Argument ändert.	Addition Erg = 1 + n
$f\in {\mathcal {O}}(\log x)$	$f$ wächst logarithmisch	$f$ wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt. Merke: Die Basis des Logarithmus ist egal.	Binäre Suche
$f\in {\mathcal {O}}({\sqrt {x}})$	$f$ wächst wie die Wurzelfunktion	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument vervierfacht	Primzahltest
$f\in {\mathcal {O}}(x)$	$f$ wächst linear	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument verdoppelt.	Addieren aller Zahlen des Arguments For (i=0; i<n; i++) Erg+=i;
$f\in {\mathcal {O}}(x^{2})$	$f$ wächst quadratisch	$f$ wächst ungefähr auf das vierfache, wenn sich das Argument verdoppelt	Einfacher Sortieralgorithmus Worst Case Bubblesort
$f\in {\mathcal {O}}(2^{x})$	$f$ wächst exponentiell	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument um eins erhöht
$f\in {\mathcal {O}}(x!)$	$f$ wächst faktoriell	$f$ wächst ungefähr um das $x$-fache, wenn sich das Argument von $x-1$ auf $x$ erhöht.

Rechenbeispiele

Zu der ${\mathcal {O}}$ Notation (Obereren Schranke)

Gegeben sei eine Funktion f(x) mit f(x)= 3x³-2x²+x-9

Auf den 1. Blick sieht man das die Funktion exponentiell wächst, also muss f(x) ≥ ${\mathcal {O}}(x^{n})$ sein für ein noch unbestimmtes n0 ( beliege Menge ≤ eigentliche Menge )

Es muss also zutreffen: f(x) ≤ ${\mathcal {O}}(x^{n})$ für alle n≥n0

${\mathcal {O}}(g(x))$ kann auch wie folgt geschrieben werden : c * g(x)

Also:

f(x) ≤ c * g(x) für alle n ≥ n0

Da diese Funktion exponentiell wächst und die höchste Potenz 3 ist muss g(x) = x³ sein.

3x³+2x²+x+9 ≤ c * x³ für alle n ≥ n0

Wahl c:

c ≥ 3, da f(x) = 3x³+2x²+x+9

Graphen

wähle c = 15 & n0=1 ( beide Werte zufällig gewählt )

Beweis:

3x³+2x²+x+9 ≤ 15 * x³ für alle n≥ n0 | -3x³

2x²+x+9 ≤ 12 * x³ für alle n≥ n0 | /x³

${\frac {2}{x}}$+ ${\frac {1}{x^{2}}}$+ ${\frac {9}{x^{3}}}$ ≤ 12 für alle n≥ n0

Da n0=1

2/1 + 1/1 + 9/1 ≤ 12

12 ≤ 12

Damit ist bewiesen, dass für alle n≥1 ${\mathcal {O}}(x^{3})$zutrifft.

Bei Werten >1 werden die Werte auf der linken Seite der Ungleichung immer kleiner und der Wert auf der rechten Seite bleibt konstant.