O-Notation beweisen?
Hallo,
im Fach "Algorithmen und Datenstrukturen" muss ich die O-Notation beweisen.
Ich habe viel nachgelesen und verstehe trotzdem nicht wie ich das beweisen kann.
Ich habe absolut keine Ahnung wie ich vorgehen muss. :/
Die Aufgabe:
Bestimmen Sie, obf∈O(g) oderf∈Ω(g) oder beides (d.h.f∈Θ(g)). Beweisen Sie IhreAussagen unter Verwendung der Definitionen aus der Vorlesung.
f(n) g(n)
a) n^3/2 n^2/3
b) 10n^2+ log^2(n) n^2
c) 2^n 2^n+^4 + 3
d) 2^n 10n!
Ich würde mich sehr freuen, wenn mir jemand bei dieser Aufgabe helfen kann und
es mir für "dummies" erklären kann.
Danke schonmal im Vorraus!
1 Antwort
Eine Funktion f(n) ist Element von O( g(n) ), wenn für n --> unendlich gilt :
f(n) <= const * g(n)
Das heisst, dass die Funktion f(n) für grosse n nicht so schnell wächst wie g(n).
Man schreibt auch oft f(n) = O( g(n) ), aber das ist nicht korrekt.
Beispiel :
f(n) = n + n^2
f(n) < n^2 + n^2
f(n) < 2 * n^2
Daher gilt f(n) € O ( n^2 ).
In der Praxis benutzt man für g(n) meistens die Funktionen
- 2^n
- n^k
- n * log(n)
- n
- n^(1/k)
- log(n)
anders gesagt versucht man, eine Funktion f(n) auf eine der oben genannten Grenzen zu maximieren.
Wegen
f(n) <= c * g(n)
muss gelten
f(n)/g(n) <= c für grosse n
Hier am Beispiel
h1(n) = n^2/3
h2(n) = n^3/2
h1(n) / h2(n ) = 1 / n^(5/6)
Weil dieser Ausdruck für n-> unendlich gegen 0 strebt, kann man c einfach 1 setzen.
h1(n) / h2(n ) = 1 / n^(5/6) <= 1 für grosse n
Also gilt h1 € O( h2 )
Die Umkehrung:
h2(n) / h1(n ) = n^(5/6)
Dieser Ausdruck hat für n->unendlich keine Obergrenze, also ist h2 kein Element von O ( h1 ).
Danke:) könnten Sie mir das für a) zeigen?