Video 3-4: Asymtotiken aus Plots?

0:04 Man könnte versucht sein, wenn man Funktionen asymptotisch vergleichen will, welche wächst asymptotisch schneller, dann äh könnte man versucht sein, einfach die Funktion zu plotten für eine gewisse Größe und dann wird man ja schon sehen, welche schneller wächst. Und das ist auch durchaus eine sinnvolle erste ein sinnvoller erster Versuch, um so eine ganz grobe Idee zu bekommen.

0:27 Ähm, da kann man die Frage stellen, warum quälen wir sie dann mit Limus Superior an all diesem äh abstrakteren ähm Begriffen, wenn das Bild doch reicht? Und der Punkt ist, dass diese Bilder eben irre führen können, wenn die Funktionen ein bisschen weniger gutmütig sind. Ein klassisches Bild, wie man es für Algorithmen oft kriegt, ist sowas. Für kleine Eingabegrößen ist dieser diese rote Linie deutlich niedriger und ich würde wahrscheinlich bis Eingabegröße 1800 eher den roten Algorithmus ausführen wollen, weil seine Laufzeit niedriger ist. Dann gibt's aber so ein Punkt, an dem sich für den grünen Algorithmus ein Breakven etabliert und danach scheint der grüne besser zu sein.

1:14 Also könnte man aus dem Bild die ab die Aussage herleiten. Asymptotisch für ganz große N ist wahrscheinlich die grüne Funktion besser, weil die rote hier deutlich steiler ansteigt. Das sieht aus, als würde die nach oben abhauen und die grüne irgendwie etwas flacher ansteigen. Äh, wenn man aber die gleichen Funktionen ein bisschen weiter plottet, also sie müssen jetzt hier auf die X-Achse schauen, hier geht's bis 2000, jetzt geht's bis 10.000, dann sieht das in der Tat so aus. Ähm, die rote Funktion steigt deutlich schneller als die grüne.

1:48 Und dann passiert aber plötzlich was Seltsames. Wenn ich noch weiter rauszoome, also bis 200.000, dann ist jetzt plötzlich die grüne Funktion deutlich schneller am wachsen als die rote. Was ist das denn? Also hier gibt's so ein Anfangsbereich. Ja, da ist ganz am Anfang war ja die rote Funktion niedriger und die grüne größer. Das bleibt auch eine ganze Weile so. Dann gibt's aber noch mal so ein äh Punkt, wo sie sich wieder kreuzen. Und wenn ich Ihnen nur die Bilder zeige, die die Funktionen sehen so glatt und harmlos aus, man zieht denen nicht unbedingt an, dass die sich da jetzt noch mal kreuzen. Ähm, das ist natürlich ein völlig konstruiertes Beispiel. Hier sind die zwei Funktionen, wenn Sie sie sehen wollen. Also ist über ein Integral hergeleitet, aber letztlich ist es beides äh asymptotisch, ungefähr quadratisch und hier gezielt so manipuliert, dass es sich immer wieder schneidet und endlich oft, aber die Funktionen sind asymptotisch äquivalent, die wachsen genau gleich schnell, aber keins der Bilder gibt diese Message her.

2:49 Das ist sozusagen meine Warnung, dass ähm wie auch Mathematiker Ihnen oft sagen werden, Funktionen, der Raum der Funktionen ist so groß, da gibt's ziemlich viel äh fiese Beispiele, wenn man lang genug sucht. So, auch hier, man kann aus den Bildern selbst nicht eine definitive Aussage treffen. Umgekehrt sind die Funktionen hier auch schon sehr konstruiert. äh, dass die in dem Algorithmus tatsächlich als Laufzeit dann das Ergebnis sind, mag vielleicht nicht vorkommen.