3.3 Obere Schranke

js70
Neuling
Neuling
Beiträge: 6
Registriert: 12. Mai 2015 10:36

3.3 Obere Schranke

Beitrag von js70 »

Ist in Aufgabe 3.3 mit \(log^kn\) die k-fache Verkettung \((log\circ\ldots\circ log)(n)\) oder das Produkt \(logn\cdot\ldots\cdot logn\) gemeint?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: 3.3 Obere Schranke

Beitrag von Prof. Karsten Weihe »

js70 hat geschrieben:Ist in Aufgabe 3.3 mit \(log^kn\) die k-fache Verkettung \((log\circ\ldots\circ log)(n)\) oder das Produkt \(logn\cdot\ldots\cdot logn\) gemeint?
Das Produkt.

KW

Roey
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 29. Apr 2015 16:20

Re: 3.3 Obere Schranke

Beitrag von Roey »

Dann stellt sich jedoch die Frage, ob log^k n wirklich element von O(n) ist, da ja ab einer gewissen Größe von n jedes weitere logn die Zahl um ein Vielfaches erhöht und somit n langsamer wächst als log^k(n). oder habe ich was falsch verstanden?

bspw.
sei k = 9999999
und n = 9999998

so wächst log^k(n) bei n = 9999999 um 6.79... × 10^12073134
n dagegen wächst um 1

Bei einer Verkettung hingegen senkt jedes weitere log unsere Zahl

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: 3.3 Obere Schranke

Beitrag von Prof. Karsten Weihe »

Roey hat geschrieben:Dann stellt sich jedoch die Frage, ob log^k n wirklich element von O(n) ist, da ja ab einer gewissen Größe von n jedes weitere logn die Zahl um ein Vielfaches erhöht und somit n langsamer wächst als log^k(n). oder habe ich was falsch verstanden?
Muss wohl. Was meinen Sie mit "jedes weitere logn"? Die Potenz k bleibt konstant, nur das n ist ein Parameter, die Funktion lautet \(n\rightarrow\log^kn\) und nicht \((n,k)\rightarrow\log^kn\) :!:

KW

Roey
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 29. Apr 2015 16:20

Re: 3.3 Obere Schranke

Beitrag von Roey »

Aber es heißt ja nur, dass k e N ist, es wurde kein Wertebereich gegeben.
Angenommen wir haben als k eine zwanzigstellige Zahl, so würde log^k(n) beim steigenden n durch den limes schneller wachsen als n.
Dies passiert, sobald der einzelne Term log(n) > 1 ist.

D.h. das bis zu einem gewissen Punkt n schneller wächst, es sich ab einem gewissen n ausgependelt hat und dann wächst log^k(n) schneller.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: 3.3 Obere Schranke

Beitrag von Prof. Karsten Weihe »

Roey hat geschrieben:Aber es heißt ja nur, dass k e N ist, es wurde kein Wertebereich gegeben.
Yep.

Roey hat geschrieben: Angenommen wir haben als k eine zwanzigstellige Zahl, so würde log^k(n) beim steigenden n durch den limes schneller wachsen als n.
Dies passiert, sobald der einzelne Term log(n) > 1 ist.
Diese Argumentation müsste ja eigentlich schon für k=1 zutreffen :?:

Also kann an der Argumentation irgendetwas nicht stimmen ... ich denke, hier ist der entscheidende Punkt: Wenn Sie \(n\) und \(n+1\) gegenüberstellen, dann müssen Sie auch \(\log(n)\) und \(\log(n+1)\) gegenüberstellen, und es gilt nun einmal \(\log(n+1)-\log(n)<1\), wenn \(\log(n)>1\) ist.

KW

Roey
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 29. Apr 2015 16:20

Re: 3.3 Obere Schranke

Beitrag von Roey »

Ah das war dann mein Fehler. Ich habe den gesamten Term multipliziert betrachtet und nicht den einzelnen log.

Vielen Dank

Antworten

Zurück zu „Archiv“