Seite 1 von 1

Asymptotisch schneller

Verfasst: 7. Apr 2017 10:44
von Verenax
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.

Re: Asymptotisch schneller

Verfasst: 7. Apr 2017 16:09
von Prof. Karsten Weihe
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

Re: Asymptotisch schneller

Verfasst: 9. Apr 2017 10:36
von Verenax
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.

Re: Asymptotisch schneller

Verfasst: 9. Apr 2017 11:34
von Prof. Karsten Weihe
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