es geht zum Beispiel um eine append Operation in einem Array. Im besten Fall ist das Array groß genug und es kann einfach eingefügt werden (konstatnter Aufwand). Im schlechten Fall ist das Array voll und es muss verdoppelt werden (und somit haben wir keinen konstanten Aufwand mehr). so muss eine append Operation ohne verdopplung z.B. 1€ bezahlen und eine append mit Verdopplung 3n€.
Dir scheint es um die amortisierte Laufzeit zu gehen.
Aber wo ist nun der Vorteil? Ich meine es wird doch kein Geld gespart. Ich muss doch so oder so das Geld aus dem Budget nehmen, ob ich das jetzt spare oder direkt dann aus dem Budget nehme wenn eine teure Operation gemacht wird ? Oder denke ich da falsch?
Sagen wir mal, wir möchten 3 Elemente in einem Array speichern. Dazu schauen wir uns doch mal an, wie es sich verhält, wenn wir mit einem Array der Größe 1 beginnen und die Kapazität um 1 erhöhen, sobald eine Vergrößerung notwendig wird.
Für das erste Element müssen wir erstmal ein Array anlegen, das kostet uns 1 €. Dann müssen wir das Element dort ablegen, auch das kostet 1 €. Heißt: um das erste Element einzufügen, zahlen wir 2 €.
Jetzt kommt das zweite Element. Jetzt müssen wir ein zweites Array der Größe 2 anlegen. Das kostet uns 1 €, dann müssen wir das Element aus dem alten Array kopieren: 1 €. Zum Schluss müssen wir das zweite Element im neuen Array ablegen, macht nochmal 1 €. Um das zweite Element einzufügen, zahlen wir 3 €.
Drittes Element, gleiches Spiel: Array anlegen, macht 1 €. Zwei Elemente kopieren, kostet 2 €. Drittes Element ablegen: 1 €. Um das dritte Element einzufügen, zahlen wir also 4 €.
D. h. um das n-te Element hinzuzufügen, zahlen wir (n+1) Euro. Um n Elemente hinzuzufügen müssen also 2+3+4+5+...+(n+1) = n + sum_i=1^n i Euro bezahlt werden. Die Summe sollte Dir bekannt vorkommen: der kleine Gauss. Und damit wissen wir: quadratische Laufzeit.
Außerdem können wir die Kosten nun einfach berechnen: n + (n²+n)/2 = (n² + 3n)/2. Für 8 Elemente brauchen wir also (64 + 24)/2 = 44 €. Für 16 schon (256 + 48) / 2 = 152.
Wenn wir die Kapazitäten verdoppeln, sieht die Sache anders aus:
1. Element: wie gehabt 2 €
2. Element: wie gehabt 3 €, Kapazität auf 2 erhöht.
3. Element: wie gehabt 4 €, Kapazität ist jetzt aber auf 4 erhöht.
4. Element: 1 €
5. Element: kostet 6 €, Kapazität auf 8 erhöht
6. Element: 1 €
7. Element: 1 €
8. Element: 1 € -> bis dahin haben wir 2+3+4+6+1+1+1+1 = 19 €
9. Element: Kapazität auf 16 erhöht, 10 €
10. bis 16. Element: je 1 € -> 7 €
Macht also 19 € für 8 Elemente bzw. 35 € für 16 Elemente.