FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Theoretische Informatik (HS)

Gross O notation - Rechnungen

Gross O notation - Rechnungen 2008-02-13 12:52
Anonymer User
Hi, ich habe folgendes Problem:

Frage ist:
n^3 element O(n^2) ??
Wie berechnet man sowas?

und
2^(n+1) element O(n^2) ??

Vielen Dank im vorraus

RE: Gross O notation - Rechnungen 2008-02-13 12:52
Anonymer User
Die Frage ist, ob diese Aussagen wahr sind. Und wenn, warum?
Wenn nicht, warum nicht :-)

RE: Gross O notation - Rechnungen 2008-02-13 13:38
Fred
In O(g) sind ja alle solche Funktionen f drin, die nicht schneller wachsen als g.

n^3 element O(n^2) ??
Nein, da kubisch schneller wächst als quadratisch.

2^(n+1) element O(n^2) ??
Nein, da exponentiell schneller wächst als quadratisch.

Man kann ja folgende Reihenfolge "auswendig" lernen:
- konstant
- logarithmisch
- linear
- linearithmisch
- quadratisch
- kubisch
- exponentiell

Da sind sicher noch ein paar mehr, aber das dürften so in etwa die wichtigsten Komplexitätsklassen sein. Also die, die man in der Praxis häufig antrifft.

RE: Gross O notation - Rechnungen 2008-02-13 13:50
Anonymer User
Ok das ist mir klargeworden, danke.
Aber wie kann man das rechnerisch/formal beweisen?

RE: Gross O notation - Rechnungen 2008-02-13 13:51
Slater
der Grenzwert von c*n^2/n^3 dürfte sicherlich gegen 0 streben -> n^3 wächst schneller als n^2

c = beliebige Konstante

RE: Gross O notation - Rechnungen 2008-02-13 13:54
Fred
Wenn man ganz pingelig ist, dann strebt glaube ich der Grenzwert nicht gegen 0, sondern die Folge strebt gegen den Grenzwert 0. Kann aber auch sein, dass ich mich irre.

RE: Gross O notation - Rechnungen 2008-02-13 13:59
Slater
kann sein, dass du pingelig bist

RE: Gross O notation - Rechnungen 2008-02-13 14:06
Fred
Als angehender Informatiker muss man pingelig sein!

RE: Gross O notation - Rechnungen 2008-02-13 15:34
Anonymer User
Also wenn ich das richtig verstanden habe könnte man die folgenden Aufgaben so lösen:

a) n^3 element O (n^2)

n0 = 0
-> 2 <= 2^(n+1) <= c * n^2
-> 2 <= (2^(n+1))/ n^2 <= c
Da (2^(n+1)) exponentiell wächst und n^2 quadratisch,
läuft der Grenzwert dieser Folge auf unendlich zu.
Da unendlich irgendwann grösser als eine konstante c ist,
gilt die Aussage a nicht:

weiteres Beispiel:
b) (n+1)! element O(n!)

n0= 1
-> 1 <= (n+1)! <= c * n!
-> 1 <= (n+1)!/n! <= c
-> 1 <= n <= c

da der grenzwert von n auf undendlich zuläuft.
ist n irgendwann grösser als eine feste konstante c und
deshalb gilt Aussage b nicht.

wäre das ein formal rechnerischer beweis?

RE: Gross O notation - Rechnungen 2008-02-14 02:13
georg
wäre das ein formal rechnerischer beweis?

Hm, mich würde z.B. die Formulierung "unendlich wird irgendwann
größer als jede Konstante" stören. Um das ganze rechnerisch zu
vereinfachen, kann man folgende Charakterisierung nutzen:
es ist [latex]f\in O(g) \Longleftrightarrow (\exists n,c\forall m\ge n: f(m)/g(m)\le c)[/latex].
Und Beschränktheit bzw. Nicht-Beschränktheit läßt sich meistens
einfach nachrechnen.

D.h. um zu entscheiden, ob [latex]n^3\in O(n^2)[/latex], muss man
prüfen, ob die Funktion h mit [latex]h(n)=n^3/n^2=n[/latex] beschränkt ist
(d.h. nur Werte annimmt, die unter einem gewissen Maximum liegen).
Das ist sie offensichtlich nicht. Also gilt die Behauptung nicht.


Für den zweiten Teil muss man prüfen, ob h mit [latex]h(n)=\frac{(n+1)!}{n!}=n+1[/latex]

beschränkt ist. Aber das ist wieder nicht der Fall…

PS: Die Charakterisierung klappt natürlich nur, wenn g keine Nullstelle hat.
Falls sie doch eine hat, kann man auch benutzen:
[latex]f\in O(g) \Longleftrightarrow (\exists n,c\forall m\ge n: f(m)/(g(m)+1)\le c)[/latex]