Willkommen. Ich hoffe, Sie haben sich Freitag mit Herrn Jürgen gut vertragen.

Wir machen weiter mit dem Thema amortisierte Analyse.

Sie haben sich letzte Woche mit der amortisierten Analyse befasst.

Es sind unbeschränkte Arrays, die von der Größe her schrumpfen oder wachsen,

je nachdem, wie sich die Anzahl Elemente entwickelt.

Mit anderen Worten, ich habe eine Operation Pushback,

die am Ende des Arrays Elemente anhängt.

Ich habe eine Operation Popback, die hinten Elemente wieder entfernt.

Ich habe eine Funktion Reallocate, die, sobald das Array gewissermaßen zu voll wird,

die Arraygröße verdoppelt. Ein neues Array der verdoppelten Größe alloziert.

Das alte Array kopiert in dieses neue Array rein.

Sobald durch wiederholte Popbacks das Array zu weit schrumpft,

unter ein Viertel des bisher reservierten Platzes,

wird ein Array neu alloziert, das nur noch doppelt so groß ist wie der belegte Platz.

Nicht mehr viermal so groß.

Wiederum wird der Inhalt von dem alten ins neue Array kopiert.

Mit anderen Worten, das Problem war, Pushback und Popback sind normalerweise billig.

Ich schreibe ein Element in ein schon vorhandenes Array bzw. lese ein Element raus.

Aber sobald wir in die Situation kommen, dass die Größen überschritten werden

und Reallocate zuschlägt, wird es teuer.

Dann müssen wir das gesamte bisherige Array kopieren.

So, und Herr Gurin wird Ihnen vorargumentiert haben, dass trotzdem,

wenn man M-Operationen hat, man stets Zeit O von M verbraucht.

Das ist wohlgemerkt etwas stärkeres als reine Average Case Analyse.

Das könnte man hier ja auch machen und sagen, ich rechne jetzt aus,

was ist der durchschnittliche Zeitverbrauch von Popback und Pushback.

Aber das hier ist stärker.

Das hier sagt, unabhängig von irgendwelchen Zufällen,

egal welche Sequenz von M-Operationen dahinter kommt, sie braucht immer Zeit O von M.

Diese Zahlen, von denen ich sprach, kann man nun als Parameter ansehen.

In dem Programm, das vermutlich angeschrieben worden ist, steht das auch so drin.

Wir haben also einen Parameter,

Beta gleich 2, der also besagt, das Array wird verdoppelt,

also um einen Faktor Beta vergrößert, wenn es zu voll wird.

Und dann hatten wir einen zweiten Faktor, Alpha gleich 4,

der sagt, um welchen Faktor schrumpfen wir das Array?

Also wenn der Füllstand des Arrays ein 1 durch Alpha,

also in diesem Fall ein Viertel unterschreitet, dann wird das Array geschrumpft.

Das erste, was wir heute machen wollen, ist,

jetzt mal ausrechnen oder vorargumentieren, dass das auch mit beliebigen Alpha und Beta klappt.

Das heißt also, ab jetzt sind Alpha und Beta beliebig,

naja, tunlichst sollte dabei Alpha größer Beta sein,

sonst ist man unmittelbar, nachdem man das Array vergrößert hat,

wieder in der Situation, wo man es gleich wieder schrumpfen müsste, das wäre unangenehm, also Alpha größer Beta.

So, das Argument, mit dem man ausrechnet, dass tatsächlich nur Zeit von O von M verbraucht wird,

ist die sogenannte Kontierungsmethode.

Das heißt, wenn ich es recht verstehe, haben Sie gesehen,

man legt jedes Mal, wenn man einen Schritt macht, also wenn man eine Operation durchführt,

Zeit auf ein Konto. Und zwar mehr Zeit, als man eigentlich gerade verbraucht.

Also ich mache eine Operation, die dauert, sagen wir mal, 1, ist egal,