Asymptotisch schneller

Verenax
Neuling
Neuling
Beiträge: 7
Registriert: 23. Apr 2016 15:35

Asymptotisch schneller

Beitrag von Verenax » 7. Apr 2017 10:44

Hallo,

bei dem Youtube-Video zur Asymptotischen Komplexität treten bei mir noch einige Unklarheiten auf.
Bei der Formel für "f schneller als g" muss ja der Grenzwert von (Funktion f / Funktion g) = 0 ergeben. Aus mathematischer Sicht müsste ja eigentlich Funktion g größer werden als f, damit als Grenzwert = 0 herauskommen kann.
Kurz vor Ende des Videos wird dann gesagt, dass die Logarithmenfunktionen immer asymptotisch größer sind als die Konstanten. Bei dem früheren Vergleich zum logarithmischen Verhalten bei n und einer log-Funktion hat man aber gesehen, dass die Konstante Funktion deutlich schneller größer wird.
Mir fehlt wohl eine genauere Definition von "asymptotisch schneller bzw. größer", da das für mich bisher bedeutet, dass asymptotisch schneller gleichbedeutend mit zahlenmäßig größerer Komplexität ist und diese Annahme wohl eher genau umgekehrt richtig wäre.

Ich wäre also dankbar dafür, wenn mir jemand nochmal eine klarere unmissverständliche Erklärung von asymptotisch schneller geben könnte.

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

Re: Asymptotisch schneller

Beitrag von Prof. Karsten Weihe » 7. Apr 2017 16:09

Verenax hat geschrieben:Bei dem früheren Vergleich zum logarithmischen Verhalten bei n und einer log-Funktion hat man aber gesehen, dass die Konstante Funktion deutlich schneller größer wird.
Wo haben Sie gesehen, dass eine konstante Funktion schneller als eine Logarithmusfunktion wächst :?: :shock:

KW

Verenax
Neuling
Neuling
Beiträge: 7
Registriert: 23. Apr 2016 15:35

Re: Asymptotisch schneller

Beitrag von Verenax » 9. Apr 2017 10:36

In dem genannten Video wird n und der 2er log n betrachtet. Dabei ist nach bspw. 16 Iterationen der Logarithmus erst bei 4 oder bei Iteration 1024 dann bei 10. Dabei fiel der Begriff des Aufwands und dies hatte ich mit Komplexität gleichgesetzt und daher angenommen, dass ja hierbei n(äquivalent zu den Iterationen) schneller wächst, da ja auch der Aufwand mit jeder Iteration um 1 wächst wobei bei dem Logarithmus viel langsamer ein Anstieg zu erkennen ist.
Mir war es leider nicht möglich einen Screenshot dessen anzuheften, deshalb nochmal das Video https://www.youtube.com/watch?v=dpgkYeSXSPI und der Hinweis, dass es um Minute 5:30 geht.

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

Re: Asymptotisch schneller

Beitrag von Prof. Karsten Weihe » 9. Apr 2017 11:34

Verenax hat geschrieben:In dem genannten Video wird n und der 2er log n betrachtet.
In Ihrem ersten Posting hatten Sie von einer konstanten Funktion gesschrieben, das ist f(n) = c für alle n, c eben eine Konstante. Jetzt schreiben Sie von f(n) = n, also der Identität :?:

KW

Antworten

Zurück zu „Archiv“