Algorithmus Komplexität . Bsp. f(n)=(n+1)2 + √n (100n + ln(n)) . Kleinstes b so dass f(n)€O(nb)?

Question

 

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. 

Answer 1

(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? 

Comments

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 :$

---

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 ³ /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)$$