+1 Daumen
763 Aufrufe

Ich brauche Hilfe bei dieser Aufgabe ich habe keinen Ahnung wie man dies begründet.  Kann mir bitte jemand behilflich sein? Ich hab ein wenig gegooglt und bin Komplexität von funktionen lassen gestoßen. Aber so wirklich kann ich nichts anfangen. Bild Mathematik

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

(a) Da folgende Ungleichungen gelten $$\ln n< n, \forall n>0$$ $$|\sin n|\leq 1, \forall n$$ bekommen wir folgendes $$f(n)=4\ln n+\frac{n\cdot |\sin n|}{2}\leq 4n+\frac{n\cdot 1}{2}=4n+\frac{n}{2}=\frac{9}{2}n$$


Also gilt $$f(n)\in O(n)$$


Kannst du  das ähnlich für (b) machen?

Avatar von 6,9 k

Ich bin mir extrem unsicher dabei

 Kannst du bitte erklären warum bei der Ungleichung nur  noch 4 n statt 4 ln (n) steht?  Und es wäre sehr sehr nett wenn du mir diese formel die habe ich zu dem Thema gefunden bedeuten soll ich verstehe gerade 0. :(  die b hab ich jetzt mal probiert so einigermaßen :$Bild Mathematik

Man hat die Ungleichung $$\ln (n) \leq n$$ wenn wir mit 4 diese Ungleichung multiplizieren bekommen wir $$4 \ln (n) \leq 4 n$$


(b) Ich habe nicht ganz verstanden wie du das $$\ln(n)^{\frac{3}{2}}$$ bekommen hast.

Du kannst folgendes machen:

Man hat $$\ln (n)\leq n, \forall n>0 \\ \sqrt{n}\leq n, \forall n\geq 1 \\ n+1\leq n+n=2n, \forall n\geq 1$$

Also haben wir dass $$f(n)=(n+1)^2+\sqrt{n}(100n+\ln (n))\\ \leq (2n)^2+n(100n+n) \\ =4n^2+101n^2 \\ =105n^2 \\ \Rightarrow f(n)\in O(n^2)$$

vielen Dank :)

ich habe vieles um einiges mehr verstanden, aber eine frage habe ich noch man hat diese Ungleichungen schon gegeben, die habe ich im Netz auch gefunden , aber wie kommt man denn darauf, dass n+1 < n +n ist woher weiß man das.

f(n) = 4ln(n) + n cos (n)     ( durch 2)

                                 2

, (b) f(n) = 4n 3 /n+1 ,

ich bin so vorgegangen wie du aber n 3 ist doch größer als n was betrachtet man daP?

und bei cos (n)habe ich cos < +1 -1 = 0 ergibt ist das korrekt?

Die Ungleichung n+1≤n+n gilt für jedes n≥1.


Bei $$f(n)=4\ln (n)+\frac{n\cos (n)}{2}$$ benutzt du die Ungleichungen $$\ln (n)\leq n, \forall n>0$$ und $$\cos (n)\leq |\cos (n)|\leq 1$$

Bei (b) benutzen wir folgende Ungleichung: $$n+1> n \Rightarrow \frac{1}{n+1}<\frac{1}{n}$$ Also haben wir dann $$f(n)=\frac{4n^3}{n+1}<\frac{4n^3}{n}=4n^2\Rightarrow f(n)\in O(n^2)$$

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community