O-Notation beweisen?

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.


SRPower 
Beitragsersteller
 28.04.2019, 19:22

Danke:) könnten Sie mir das für a) zeigen?

Rammstein53  29.04.2019, 06:44
@SRPower

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 ).