Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Fragen zur Vorlesung
Wir haben unter dem Thema Zeitanalyse das Beispiel mit INsertionSort gemacht. Kann mir vielleicht jemand erklären, wie man dann auf die Laufzeit kam, also dass man die Summe von i=2 bis n hat ist klar, aber wieso über i-1 ? Brauch ich keine zeit für Zuweisungen?
Nein, in KompAlg bisher irgendwie nicht.
mm und rückgabe von werten haben dann auch keinen zeitverbrauch…
richtig, zumindest noch nicht.
Meine Vermutung: es handelt sich dabei um sehr primitive Operationen, die meist direkt in der Hardware implementiert sind und daher nicht die größte Relevanz haben.
In der Vorlesung wurde eine Funktion f hergeleitet, sodass die Laufzeit von Insertion Sort in O(f) enthalten ist. In den Definitionen zum asymptotischem Wachstum (z.B. f \preceq g) gab es immer einen konstanten Faktor c, der skalierte Abweichungen zwischen f und g erlaubt. Dieser Faktor c frisst die Zuweisungen ausserhalb der inneren Schleife auf. Wurde in der Vorlesung aber auch so gesagt (also, dass es um das asymptotische Wachstum ging).
Ich habe es am Mittwoch leider nicht geschafft, alles abzuschreiben – die Tafel wurde von der Putzfrau zu schnell gewischt … 
Könnte mir jemand seine Mitschrift der letzten beiden Tafeln vom Mittwoch zukommen lassen?
Danke! 
Oh, die ist schon online :huh:
Dann ist das natürlich ein Argument 