Die letzten 4 Beiträge |
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 |
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 |
Karlito |
Hallo AlgoNewbie,
das Mastertheorem kommt hier meines Wissens nach nicht zum tragen. Der Ansatz ist, dass Du dir die Definition von zur hand nimmst und einen Beweis führst. Also kleine Stütze:
(Quelle: Wikipedia).
Du musst also nachweisen, dass es ein c gibt, so dass
und im zweiten Teil, dass es ein C gibt so dass
Gruß,
Karlito |
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. |
|
|