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
Die Frage ist, ob diese Aussagen wahr sind. Und wenn, warum?
Wenn nicht, warum nicht :-)
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.
Ok das ist mir klargeworden, danke.
Aber wie kann man das rechnerisch/formal beweisen?
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
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.
kann sein, dass du pingelig bist
Als angehender Informatiker muss man pingelig sein!
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?
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]