 Dynamischer Stack. Amortisierte Analyse |
Marvin812
unregistriert
 |
|
| Dynamischer Stack. Amortisierte Analyse |
     |
Meine Frage:
Hallo,
ich habe folgendes Problem bezüglich der amorisierten Laufzeitanalyse.
Und zwar:
Man arbeitet mit einem Array-basierten Stack der länge m.
Sollte dieser Stack irgendwann per push() -Methode voll sein, so wird der Stack auf Länge 2m vergrößert, indem man einen neuen Stack der größe 2m erstellt,den alten Stack rüberkopiert und dann den alten mit dem neuen Stack ersetzt.
Ich soll nun folgendes machen:
a) Wort-Case Laufzeit einer Push()-Operation bestimmen und begründen.
b) Zeigen Sie, dass das Einfügen von n Elementen per push() höchsten Zeit O(n) beansprucht. Sie können davon ausgehen, dass n= 2^k eine Zweierpotenz ist. Die intiale Kapazität betragt m=1.
Meine Ideen:
a) Normalerweise würde ich hier sagen, dass die Laufzeit m beträgt, da im schlimmsten Fall das Array voll ist und rüberkopiert werden. Hier wird dann per Schleife m mal das jeweilige Element rüberkopiert => O(m)
Push() selber hat ja eine Laufzeit von O(1),wenn das Array nicht voll ist.
b) Hier weiß ich leider nicht so ganz weiter. Der Tipp mit der Zweiterpotenz hilft jetzt auch nicht so sehr. Außer ,dass ich weiß dass das Array halt für alle nächsten Zweierpotenzen vergrößert werden muss.
Oder hat das hier etwas mit der Amortisierten Analyse zu tun?
Für 2^k Elemente muss ich mein Array k mal vergrößern.
Heißt doch soviel, dass ich k mal eine Laufzeit von jeweils O(m) wobei m hier immer die aktuelle Größe ist und sich damit verändert.
Vor dem Einfügen des letzten Elementes ist das Array irgendwann auf die größe 2^k angewachsen. Heißt es, dass die Laufzeit damit O(k*2^k) = O(k*n) = O(n) beträgt?
|
|
11.07.2016 17:37 |
|
|
|
|
Die Zweierpotenz brauchst du eigentlich gar nicht (Konstanten - hier der Faktor 2 - spielen in der O Notation keine Rolle).
Für n = 2^k hast du richtig erkannt, dass k mal vergrößert werden muss. Und zwar mit der aktuellen Größe. Dann wirst du mathematisch unsauber.
![[latex]\sum_{i=0}^{k} 2^i = 2^{k+1}-1 = 2n-1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\sum_{i=0}^{k} 2^i = 2^{k+1}-1 = 2n-1)
In der Formel ist die konstante Zeit, wenn nicht vergrößert werden muss, enthalten.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
11.07.2016 18:06 |
|
|
Marvin812
unregistriert
|
|
Oh,Gott danke. Dass ich so was nicht gesehen habe.
Das Problem war eigentlich diese aufsummierung für die Laufzeit der aktuellen Größe.
Geometrisch Reihe => Fertig. Vielen dank 
|
|
|
11.07.2016 18:33 |
|
|
|
