O-Notation Umformung+Abschätzung

[Gast]

Hallo zusammen,

ich habe eine kleines Problem:
f(n) = K^(2*n+2) + n, K = sqrt(2)

Nun soll ich diese Funktion umformen und abschätzen.
Ich würde glatt sagen das ist O(2^n) wegen K^(2*n).

Wie gehe ich denn da richtig ran um das sauber mathematisch umzuformen.
In unserem Skript ist das nicht wirklich erklärt.

Ich sehe nur so Ansetze, dass man die Funktion erstmal mit bestimmten Regeln zerlegen soll.

Also als Beispiel:

4*x + 2*log2 x + 1/3x^3 = O(x) + O(log x) + O(x^3)
= O(x^3) + O(x^3) + O(x^3)
= O(x^3)
Man hat hier das asymtothische Verhalten für die Funktion betrachtet für den Grenzwert unendlich. OK soweit ok.

Aber ich sehe im Netz auch andere Vorgehensweisen.
Welche ist nun konkret die Richtige für meine Fall oben? Zerlegen und dann gucke welches Element am stärksten ist (höchste Ordnung)?

Ein kleines Beispiel für die obige Aufgabe wäre für mich gut, damit ich die anderen Aufgaben auch lösen kann. Ich lerne lieber an Beispielen. Die Beweise sind mir einfach bisschen zu schwer, auch wenn es besser wäre den Beweis zu verstehen.

[Spasstiger]

Ohne mich jemals großartig mit solchen Dingen beschäftig zu haben würde ich sagen: O(2*2^n)

Für große n ist ja der Additionsterm "+n" am Ende vernachlässigbar. Und K^(2*n+2) lässt sich für K=sqrt(2) umformen zu 2*2^n.

[pest]

Ohne mich jemals großartig mit solchen Dingen beschäftig zu haben würde ich sagen: O(2*2^n)


das 2* lässt man weg

[Spasstiger]

das 2* lässt man weg
Das hab ich auch vermutet, aber war mir nicht sicher. Ein Algorithmus mit 1*2^n arbeitet ja stets schneller als einer mit 2*2^n.

[Senior Sanchez]

Das hab ich auch vermutet, aber war mir nicht sicher. Ein Algorithmus mit 1*2^n arbeitet ja stets schneller als einer mit 2*2^n.

Faktoren fallen aber in der O-Notation einfach raus, die sind irrelevant.
Wie praxisnah das Ganze ist, ist am Ende wieder eine andere Frage. ;-)

[Gast]

Noch ne Frage:

f(n) = log n^2k; k e Z

Da habe ich O(n^2), stimmt das so weit? Ich weiß nicht wie ich da umformen soll. Ich sehe aber eben einen quadratischen Bezug.

[Spasstiger]

Noch ne Frage:

f(n) = log n^2k; k e Z

Da habe ich O(n^2), stimmt das so weit?
Ich denke nicht. log(n^2)=2*log(n).
Und da man Vorfaktoren weglässt, müsste die Lösung O(log(n)) heißen.

[Der_Donnervogel]

Faktoren fallen aber in der O-Notation einfach raus, die sind irrelevant.
Wie praxisnah das Ganze ist, ist am Ende wieder eine andere Frage. ;-)
Man muss halt wissen, dass die O-Notation für große n gedacht ist. Das ist ja AFAIR so eine Wachstumsfunktion und zeigt an wo eine Schranke liegt. Also grob sowas in der Art wie eine Limesrechnung. Wenn man aber davon ausgeht, dass n groß ist, dann wählt man damit im allgemeinen den richtigen Algorithmus. Ist n klein, ist die O-Notation aber unbrauchbar, da dann die Konstanten ins Gewicht fallen.
Ich denke nicht. log(n^2)=2*log(n).
Und da man Vorfaktoren weglässt, müsste die Lösung O(log(n)) heißen.Es ist schon zu lange her um genaues sagen zu können, aber ist k wirklich eine Konstante (also k beliebig aber fest)? Wenns eine Konstante ist, kann man sie wegfallen lassen, wenns eine Variable ist aber glaub eher nicht. Dann wärs ja sowas wie n^n. :confused:

[pest]

Ich denke nicht. log(n^2)=2*log(n).
Und da man Vorfaktoren weglässt, müsste die Lösung O(log(n)) heißen.

man lässt sie nicht "einfach" weg. man schätzt grob nach unten ab

[Trap]

man schätzt grob nach unten ab
Wie kommst du auf nach unten?

Durch die Definition der Landau Symbole ist das nicht vorgegeben.

[pest]

Wie kommst du auf nach unten?


die gebräuchlichste Notation ist imo folgende

http://www.linux-related.de/coding/pics/o-not.gif