Informatiker Board | Druckvorschau: O-Notation

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- O-Notation (http://www.informatikerboard.de/board/thread.php?threadid=2231)

Geschrieben von AlgoNewbie am 19.04.2015 um 13:36:

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.

Geschrieben von Karlito am 19.04.2015 um 15:33:

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] \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)| [/latex]$ (Quelle: Wikipedia).

Du musst also nachweisen, dass es ein c gibt, so dass
$[latex] \exists\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot|x\cdot ln(x^k)|\le|x| [/latex]$
und im zweiten Teil, dass es ein C gibt so dass
$[latex] \exists\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: |x| \le C\cdot|x+ln(x^k)| [/latex]$

Gruß,

Karlito

Geschrieben von AlgoNewbie am 19.04.2015 um 16:11:

Hallo Karlito,

vielen Dank erstmal für deine Hilfe. Das war sehr hilfreich. Daumen hoch

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

Geschrieben von Karlito am 19.04.2015 um 18:57:

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]

bzw.

.

Gruß,

Karlito