O-Notation

19.04.2015, 13:36	Auf diesen Beitrag antworten »
AlgoNewbie	O-Notation Meine Frage: Hallo zusammen, ich bin noch ziemlich neu auf dem Gebiet O-Notation / Algorithmenlaufzeit etc. Ich würde mich daher freuen wenn mir jemand zu folgender Aufgabe Hilfestellung geben könnte: Wie kann ich beweisen dass für jedes k>0 gilt: n + n log(n^k) = Theta (n)? Vielen Dank für eure Unterstützung :-) Meine Ideen: Kann es sein, dass ich auf das Master-Theorem zurückgreifen muss? Auch damit hatte ich bisher nichts am Hut, allerdings habe ich es bei meinen bisherigen Internetrecherchen an einigen Stellen mal gefunden.


19.04.2015, 15:33	Auf diesen Beitrag antworten »
Karlito	Hallo AlgoNewbie, das Mastertheorem kommt hier meines Wissens nach nicht zum tragen. Der Ansatz ist, dass Du dir die Definition von $[latex]\Theta[/latex]$ zur hand nimmst und einen Beweis führst. Also kleine Stütze: $[latex]<br /> \exists\ c > 0\ \exists\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot\|g(x)\|\le\|f(x)\| \le C\cdot\|g(x)\|<br /> [/latex]$ (Quelle: Wikipedia). Du musst also nachweisen, dass es ein c gibt, so dass $[latex]<br /> \exists\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot\|x\cdot ln(x^k)\|\le\|x\|<br /> [/latex]$ und im zweiten Teil, dass es ein C gibt so dass $[latex]<br /> \exists\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: \|x\| \le C\cdot\|x+ln(x^k)\|<br /> [/latex]$ Gruß, Karlito
19.04.2015, 16:11	Auf diesen Beitrag antworten »
AlgoNewbie	Hallo Karlito, vielen Dank erstmal für deine Hilfe. Das war sehr hilfreich. Für den ersten Fall (also O(n)) habe ich folgende Ungleichung aufgestellt: c * (n + log (n^k)) <= n c <= n/(n + log (n^k)) c <= 1 + n/log (n^k) Meine Begründung wäre nun, dass es tatsächlich ein c > 0 gibt, da n/log (n^k) immer positiv ist (da n,k > 0). Für den zweiten Fall sieht die Ungleichung ja genau so aus nur mit umgekehrtem Zeichen: c >= 1 + n/log (n^k) Auch hier ist n/log (n^k) ja immer positiv. Wählt man also ein c was <= 1 ist (aber trotzdem >0) dann ist auch diese Bedingung erfüllt. Würdest du das genau so sehen? Danke nochmal und noch einen schönen Sonntag, AlgoNewbie
19.04.2015, 18:57	Auf diesen Beitrag antworten »
Karlito	Hallo AlgoNewbie, ich habe es nicht geprüft. Ich denke es ist ungenügend, da man die Konstanten c und C in Abhängigkeit von k bestimmen sollte und das bzw. . Gruß, Karlito
Anzeige

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »