Hallo wie beweist man folgende Aufgaben?
-
log(Basis a)(n) = O(log(Basis b)(n))
-
Es gilt weder O(n^2*(sin(Pi/2*n)+1)) noch n^2*(sin(Pi/2*n)+1) = O(n)
-
f(n) = O(g(n)) ==> für i>=0: f(n)^i = O(g(n)^i)
Hallo,
ein paar Tips/Kommentare:
- log(Basis a)(n) = O(log(Basis b)(n))
loga(n)=logb(n)/logb(a)
- Es gilt weder O(n^2*(sin(Pi/2*n)+1)) noch n^2*(sin(Pi/2*n)+1) = O(n)
f∈O(g) => f(n)/g(n)0). Ist das hier der Fall ?
- f(n) = O(g(n)) ==> für i>=0: f(n)^i = O(g(n)^i)
Wenn f(n)=O(g(n)) (korrekt wäre eigentlich f∈O(g)), gibt es eine Konstante c und einen Index n0, so daß für alle n>=n0 f(n)i (unter der Annahme, daß f(n)>=0) ?
Gruss
Enno
- log(Basis a)(n) = O(log(Basis b)(n))
loga(n)=logb(n)/logb(a)
Hallo Enno,
das hab ich gewußt, hilft mir aber auch nicht weiter.
Bei den anderen beiden werd ich bestimmt weiterkommen
Danke schonmal
Hallo,
z.Z. ist loga∈O(logb), d.h. es gibt ein c>0 und ein n0∈IN, so daß loga(n)b(n) gilt. Jetzt wählst Du einfach c=1/logb(a) und n0=0 und das wars.
Gruss
Enno
Hm okay, das hab ich verstanden.
Muss aber zu meiner Schande gestehen, dass ich trotz Deiner Tips bei den anderen Aufgaben nicht weiterkomme.
Bei der weder/noch Aufgabe gilt doch das f(n)/g(n)
Hallo,
kein Problem. Bei der „weder/noch“ Aufgabe gilt zwar für ein fixes n f(n)/g(n)=n0 f(n)/g(n)=0 gilt:
n2*(sin(Pi/2*n)+1)>=n2 für n mod 43
Würde n2*(sin(Pi/2*n)+1)∈O(n) gelten, gebe es ein fixes c und ein n0 mit
n22*(sin(Pi/2*n)+1)=c*n für alle n>=n0 mit n mod 43
Nehmen wir n zudem größer als 0 an gelangen wir zu der Aussage
n=n0,0 und n mod 43
Das ist natürlich falsch, da n beliebig groß werden kann und c fix ist.
Bei der letzten Aufgabe, folgt aus f∈O(g), das es eine Konstante c>0 und einen Index n0∈IN gibt, so daß für alle n>=n0 f(n)=0 ergibt sich damit
f(n)ii=ci*g(n)i
d.h. fi∈O(gi) (hier ist ci die Konstante).
Gruss
Enno
Hallo,
die O-Notation beschreibt ja den worst case, von daher kannst du
sin(…) [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]