0
Sei x die Größe eines leeren Arrays. Wenn das Array voll wird, wird ein neues mit einer Länge k> x erstellt. Der Inhalt des alten Arrays wird in den neuen kopiert, und das neue Element wird ebenfalls gespeichert.Amortisierte Analyse [Dynamic Array]
- Ein Array mit der Länge k in k erstellt Schritte
- ein Element Kopieren konstanten Zeit in Anspruch nimmt.
Frage: Wie Sie k wählen, so dass jeder Einsatz Betrieb konstante Zeit amortisiert hat, und das Einfügen von n Elementen nimmt Θ (n)? Beweisen Sie Ihre Annahme, dass Ihre Wahl zu einer amortisierten Zeit pro Insert-Operation mit amortisierter Analyse führt.
Mein Bauchgefühl sagt k = 2 * n wäre eine gute Idee, aber ich habe keine Ahnung, wie ich es beweisen soll. Ich glaube nicht, dass ich die amortisierte Analyse überhaupt verstanden habe. Irgendwelche Vorschläge?
Dividieren der Gesamtanzahl der Schritte, die von der Gesamtzahl der Elemente. –