 O-Notation |
AlgoNewbie
Grünschnabel
Dabei seit: 19.04.2015
Beiträge: 2
 |
|
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 13:36 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo AlgoNewbie,
das Mastertheorem kommt hier meines Wissens nach nicht zum tragen. Der Ansatz ist, dass Du dir die Definition von ![[latex]\Theta[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\Theta) 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]](http://www.matheboard.de/latex2png/latex2png.php?<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 />
) (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]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\exists\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot|x\cdot ln(x^k)|\le|x|<br />
)
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]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\exists\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: |x| \le C\cdot|x+ln(x^k)|<br />
)
Gruß,
Karlito
|
|
|
19.04.2015 15:33 |
|
|
AlgoNewbie
Grünschnabel
Dabei seit: 19.04.2015
Beiträge: 2
|
|
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 16:11 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 ![[latex]x_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?x_0) bzw. ![[latex]n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n_0) .
Gruß,
Karlito
|
|
|
19.04.2015 18:57 |
|
|
|
