Hallo zusammen,
ich habe eine Aufgabe zu einer amortisierten Laufzeitanalyse bekommen. Ich hoffe das ist hier das richtige Forum für sowas :D
Zunächst einmal die Aufgabenstellung:
$$\text{Betrachten Sie eine Datenstruktur D, die mit doppelt verketteten Listen implementiert wird und}\\ \text{folgende Operationen bereitsstellt:}\\\text{D := create() erzeugt eine leere Liste, tatsächlicher Aufwand t(create())}\in O(1)\\insert(D, b) \Rightarrow \text{fügt ein Element b hinten an der Liste an, tatsächlicher Aufwand t(insert(D, b))} \in O(1)\\remove_k(D) \Rightarrow \text{entfernt jedes k-te Element aus der Liste, tatsächlicher Aufwand } t(remove_k(D)) \in O(n)\\\\\text{Geben Sie eine Potentialfunktion } \phi_i=c\cdot n_i \text{ an und zeigen Sie damit, dass die beiden Operationen} insert(D,b) \\\text{und } remove_k(D)\text{ für jedes feste k einen amortisierten Aufwand aus O(1) haben}$$
Wir hatten so etwas ähnliches im Skript nur mit Unterschied, dass wir jedes 2-te Element entfernt haben und nicht jedes k-te. Hier einmal, wie wir das in der VL gemacht haben:
$$\text{Potentialfunktion:} \phi_i=2n_i\\ \textbf{insert(D,b)}, n_i=n_{i-1}+1, \text{tatsächlicher Aufwand } t_i=1\\ a_i\\=1+\phi_i-\phi_{i-1}\\=1+2n_i-2n_{i-1} \text{ (Potentialfunktion einsetzen)}\\=1+2(n_{i-1}+1)-2n_{i-1}\\=1+2 \in O(1)\\\\\textbf{remove}_2(D), n_i=\frac{n_{i-1}}{2}, \text{tatsächlicher Aufwand } t_i=n_{i-1}\\ a_i\\=n_{i-1}+\phi_i-\phi_{i-1}\\=n_{i-1}+2n_i-2n_{i-1} \text{ (Potentialfunktion einsetzen)}\\=n_{i-1}+2\frac{n_{i-1}}{2}-2n_{i-1} \text{ (Veränderung durch 2-tes Element entfernen einsetzen)}\\=0 \in O(1)$$
Ich habe noch ein wenig erweitert, damit man besser versteht, was wir genau gemacht haben.
Mein Problem ist, wie ich die Potentialfunktion jetzt anpasse.
$$\text{Bei } remove_k(D) \text{ ist klar, dass statt zuvor } n_i = \frac{n_{i-1}}{2} \text{ für k } n_i = \frac{n_{i-1}}{k} \text{ sein muss.}$$
Ich weiß nur leider einfach nicht, welche Potentialfunktion geschickt wäre, so dass für beides O(1) raus kommt. Für das insert() ist das kein Problem, für das remove krige ich den Faktor n_{i-1} nie dort raus.
Vielen Dank im Voraus!
