\section{Dynamische Arrays}
 
Wir haben in Kapitel \ref{elementare_datenstrukturen} bereits Arrays kennengelernt. Arrays sind aber sehr statisch: Am
Anfang wird ihre Größe $n$ festgelegt, danach verändert sich diese nichtmehr.

Wir können zwar auf alle Elemente $\mathcal{A}[0], \cdots, \mathcal{A}[n-1]$ mit konstantem Aufwand zugreifen und diese
auch verändern. Aber neue Elemente hinzufügen ist unmöglich.

In einer Liste $\mathcal{L}$ hingegen ist das Hinzufügen von neuen Elementen kein Problem. Dafür kostet der Zugriff auf
das $i.$ Listenelement $\mathcal{O}(i)$ Zeit, da wir uns vom Anfang der Liste bis zu $i$ durcharbeiten müssen.

Was ist aber, wenn wir beides wollen? Zugriff in konstanter Zeit und dynamisches Wachstum? Das dynamische Array ist eine
mögliche Lösung für das Problem. 

Das Grundprinzip ist dabei sehr einfach. Ein dynamisches Array is ein Array $\mathcal{A}$, welches immer größer ist
($n_\text{cap}$ Felder) als das Array, was wir gerade brauchen ($n$ Felder). Wir schreiben also auf die ersten $n$
Plätzer wie gewohnt. Wollen wir nun ein neues Element hinzufügen, schreiben wir es auf das $n+1$-te Feld und inkrementieren
$n$ um eins.
Irgendwann ist jedoch auch das benutzte Array so groß wie das darunterliegende Array ($n=n_\text{cap}$). Bevor wir nun also weitere
Elemente hinzufügen können, müssen wir das echte Array im Hintergrund durch ein größeres (zum Beispiel
$n_\text{cap} \leftarrow 2n_\text{cap}$) ersetzen. Diese Operation ist aufwendig, geschieht aber selten. Diesen Umstand machen wir uns dann später in der
sogenannten amortisierten Analyse zunutze.

\paragraph{Anwendungen} Dynamische Arrays sind weit verbreitet. Beispielsweise ist die Implementierung der List-Datenstruktur in Python ein
dynamisches Array. Aber auch in C++, Java und Rust ist verstecken sich hinter vectoren oder generischen Listenobjekten
dynamische Arrays.

\subsection{Operationen auf dynamischen Arrays}

\begin{definition}[dynamisches Array]
  Ein dynamisches Array $\mathcal{DA}$ ist ein Tupel $(\mathcal{A}, n)$, wobei $\mathcal{A}$ ein Array von Länge
  $n_\text{cap}$ ist und $n \in \{0,\cdots,n_\text{cap}-1\}$ ein Zeiger auf das nächste freie Feld.
\end{definition}

\subsubsection{Zugriff auf Arrayelemente}
Möchten wir nun auf das $i.$ Element zugreifen, wird zuerst geprüft, ob das zulässig ist. Falls ja, fallen wir auf die
normale Arrayoperation zurück: 
\[
  \mathcal{DA}[i] = 
  \begin{cases}
    \mathcal{A}[i] \text{ if } i \in \{0, \cdots , n-1\}, \\
    \texttt{error: out\_of\_bounds} \text{ otherwise}.
  \end{cases}
\]

\subsubsection{Anhängen neuer Elemente}
Wir können in einem dynamischen Array auch Elemente hinzufügen. Hier wird nur das Einfügen am Ende behandelt. Möchte man
beliebig  (Index $i$) einfügen, muss man mit Aufwand $\mathcal{O}(n-i)$ alles nach hinten verschieben.

Wie obig erwähnt, gibt es zwei Fälle. Im ersten reicht der reservierte Platz noch aus ($n \leq n_\text{cap}$). Dann schreiben wir
einfach das neue Element ins Array und inkrementieren $n$. Diese Operation hat Aufwand $\mathcal{O}(1)$. 
Im zweiten Fall müssen wir zuerst ein neues, doppelt so großes Array anlegen ($n_\text{cap} \leftarrow
2n_\text{cap}$) und alle bisherigen Elemente ins neue Array kopieren. Das braucht $\mathcal{O}(n)$ Zeit.
Danach tritt der erste Fall ein. 

\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{\texttt{add}($\mathcal{DA}, x$)}
  \KwIn{A dynamic array $\mathcal{DA}$ and the element $x$ to be added} 
  \KwOut{$\mathcal{DA}$ with $x$ appended at the end}
  \eIf{$n < n_\text{cap}$}{
    $\mathcal{A}[n] \leftarrow x$ \;
    \KwRet $(\mathcal{A}, n+1)$ \;
  }{
    $\mathcal{A}_\text{old} \leftarrow \mathcal{A}$ \;
    $\mathcal{A}$ = new Array of size $2n_\text{cap}$ \;
    $\mathcal{A}[0,\cdots,n-1] \leftarrow \mathcal{A}_\text{old}[0,\cdots,n-1]$ \;
    $\texttt{free}(\mathcal{A}_\text{old})$ \;
    \KwRet $\texttt{add}((\mathcal{A}, n), x)$ \;
  }
\end{algorithm}

Der von $\mathcal{A}_\text{old}$ belegte Speicherplatz kann nun freigegeben werden (manuell via $\texttt{free}$ oder
durch einen garbage collector). 

\subsubsection{Löschen}
Das Löschen geschieht analog zum Einfügen nur am Ende. Möchten wir in der Mitte löschen, müssen wir danach alle Elemente
nach vorne schieben (Wieder mit Aufwand $\mathcal{O}(n-i)$).

Um nicht unnötig Speicherplatz zu blockieren, verkleineren wir das Array auf die Hälfte, sobald es zu weniger als einem
Viertel belegt ist. Die Verkleinerungsoperation braucht wieder $\mathcal{O}(n)$ Zeit.

\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{\texttt{delete}($\mathcal{DA}$)}
  \KwIn{A dynamic array $\mathcal{DA}$} 
  \KwOut{$\mathcal{DA}$ without the last element}
  \eIf{$n > \frac{n_\text{cap}}{4}$}{
    \KwRet $(\mathcal{A}, n-1)$ \;
  }{
    $\mathcal{A}_\text{old} \leftarrow \mathcal{A}$ \;
    $\mathcal{A}$ = new Array of size $\frac{n_\text{cap}}{2}$ \;
    $\mathcal{A}[0,\cdots,n-1] \leftarrow \mathcal{A}_\text{old}[0,\cdots,n-1]$ \;
    $\texttt{free}(\mathcal{A}_\text{old})$ \;
    \KwRet $\texttt{delete}((\mathcal{A}, n))$ \;
  }
\end{algorithm}

\subsection{Speicherverbrauch}
Durch den Algorithmus $\texttt{add}$ ist garantiert, dass $n \leq n_\text{cap}$. Durch den Algorithmus
$\texttt{delete}$ ist garantiert, dass $n_\text{cap} \leq 4n$. Dadurch ist garantiert, dass $n \leq n_\text{cap} \leq
4n$, wir ``verschwenden'' also stets höchstens $Θ(n)$ Speicherplatz.

\subsection{Amortisierte Laufzeitanalyse}
Die amortisierte Laufzeitanalyse betrachtet die Laufzeit von $k$ konsekutiven Operationen hintereinander und errechnet
damit die durchschnittliche amortisierte Laufzeit für eine Einzeloperation. Prinzipell ähnelt sie damit also der
average-case-Analyse, jedoch ohne die Ungewissheit durch den involvierten Zufall. 


Wie wir gerade gesehen haben, haben sowohl $\texttt{add}$ als auch $\texttt{delete}$ einen worst-case-Aufwand von
$\mathcal{O}(n)$. Nehmen wir nun an, dass wir mit einem leeren dynamischen Array starten (die anfängliche Größe setzen
wir auf $n_\text{cap} = n_0 =~1$).

Welches Laufzeitverhalten würden wir nun von $k$ hintereinander durchgeführten Einfügeoperation erwarten? Pessimistisch,
rein nach dem worst-case-Verhalten, wären es $\sum_{n=0}^k f(n)$ mit $f \in \mathcal{O}(n)$.
Damit würden die Kosten für $k$ Einfügeoperationen in $\mathcal{O}(k^2)$ liegen.
Wir wissen jedoch mit Sicherheit, dass wir nach einer Einfügeoperation mit Kopieraufwand der Größe $n$ weitere 
$n$ Elemente mit konstantem Aufwand einfügen können, da das Array $\mathcal{A}$ hinter $\mathcal{DA}$ ja nun doppelt so viel Platz hat.
Damit kommen wir bei genauerer Betrachtung auf einen amortisierten Aufwand von $\mathcal{O}(k)$ für $k$ Operationen.

Im Unterschied zur average-case-Analyse haben wir bei einer amortisierten Analyse also \emph{garantiert}, dass $k$ subsequente Operationen nicht jedes
mal im worst case landen.
\begin{definition}[Amortisierte Laufzeit]
  Seien $o_1, o_2, \dots$ endlich viele verschiedene Operationen. Der \emph{amortisierte} Aufwand von Operationenfolgen
  $f_\bullet \in \{o_1, o_2, \dots\}^{\mathbb{N}}$ der Länge $n$ wird definiert als:
  \[
    T_{\text{amo}}(n) = \frac{\max(\{\sum_{i=1}^n T(f_{\bullet_i}) | f_\bullet \in \{o_1, o_2, \dots\}^{\mathbb{N}}\})}{n}.
  \]
\end{definition}

Im Kontext der dynamische Arrays haben wir zwei Operationen, $o_1 = \texttt{add}(\mathcal{DA}, x)$ und
$o_2 = \texttt{delete}(\mathcal{DA})$, wobei der hinzugefügte Wert $x$ keinerlei Auswirkungen auf die Laufzeit hat.

\subsubsection{Aggregierte Analyse}
Zuerst betrachten wir die Einzeloperationen $\texttt{add}$ und $\texttt{delete}$ separat. Das entspricht also
Funktionsfolgen $f_\bullet = (\texttt{add}, \texttt{add}, \dots)$ bzw $f_\bullet = (\texttt{delete}, \texttt{delete},
\dots)$.

Der Einfachheit halber weisen wir den Zeilen [1] bis [3] von $\texttt{add}$ 
den Aufwand $f(n) = 1$ und den Zeilen [4] bis [8] den Aufwand
\[
  g(n) = 
  \begin{cases}
    n-1 \text{ falls } n = 2^x + 1 \text{ für ein } x \in \mathbb{N} \\
    0   \text{ sonst}
  \end{cases}
\]
zu, siehe Abbildung~\ref{fig:dynamic_array_aufwand}.
\begin{figure}[h]
  \centering
  \input{bilder/dynamic_array_aufwand.tex}
  \caption{Wir sehen die Laufzeit für das Einfügen in ein dynamisches Array. Auf der $x$-Achse die Anzahl der Elemente,
  auf der $y$-Achse die Laufzeit. Der Einfachheit halber wurde ein Aufwand von $1$ für das einfache Einfügen und ein
Aufwand von $n$ für das Kopieren von $n$ Elementen angenommen.} 
  \label{fig:dynamic_array_aufwand}
\end{figure}

 Wenn wir mit einem leeren dynamischen Array anfangen, haben nun
$k$ Aufrufe von \texttt{add} den Aufwand:
\begin{align*}
  \sum_{n=0}^k T_\texttt{add}(n) &= \sum_{n=0}^k f(n) + \sum_{n=0}^k g(n) \\
  &= k + \sum_{i=0}^{\floor*{\log_2 (k-1)}} 2^i \\
  &= k + 2^{1 + \floor{\log_2 (k-1)}} \\
  &\leq k + 2(k-1) \\
  &\leq 3k \in \mathcal{O}(k)
\end{align*}

\noindent Ein einzelner Aufruf von $\texttt{add}$ hat damit einen amortisierten Aufwand von $\mathcal{O}(1)$.

Diese Rechnung lässt sich analog auf $k$ konsekutive \texttt{delete}-Operation übertragen, solange wir voraussetzen, dass das
dynamische Array zu Beginn $k \leq n_\text{cap} \leq 4k$ groß ist.

\subsubsection{Accountingmethode}
Wir wollen nun untersuchen, was passiert, wenn wir zwischen Löschen und Einfügen nach Belieben wechseln.

In der aggregierten Analyse von \texttt{add} haben wir einfach $k$ Operationen von $\texttt{add}$ subsequent ausgeführt,
den kumulativen Aufwand berechnet und dann durch $k$ geteilt, um den Aufwand pro Schritt zu berechnen. Das ging einfach
und direkt, da es nur eine Operationenfolge $f_\bullet$ gab: $(\texttt{add}, \texttt{add,} \dots, \texttt{add})$.
Nun sind wir aber an gemischten Operationenfolgenden von \texttt{add} und \texttt{delete} interessiert. Für $k=3$ gibt
es schon $8$ mögliche Operationenfolgen: (\texttt{add}, \texttt{add}, \texttt{add}), (\texttt{add}, \texttt{add},
\texttt{delete}), \dots. Über all diese Möglichkeiten zu gehen und den maximalen durchschnittlichen Wert einer Sequenz
zu bestimmen, wäre sehr mühselig.

Wir gehen daher einen anderen Weg, die Accountingmethode. Hier wird der Datenstruktur selber ein Zeitkonto $K$ zugeordnet,
in welche Operationen ein- und auszahlen. Schnelle Operationen wie ein \texttt{add} ohne Erweiterung von
$\mathcal{A}$ zahlen dann mehr ein als sie kosten, wird dann aber eine Erweiterung von $\mathcal{A}$ fällig, wird sie
aus dem angespartem Guthaben bezahlt.

Wir vereinfachen die Laufzeit von \texttt{add} und \texttt{delete} wie bei der aggregierten Analyse und haben damit folgende Tabelle für die Kosten und Einzahlungen:
\begin{center}
  \begin{tabular}[c]{l | c | c}
    Laufzeit der $i$-ten Operation $f_i$        & Laufzeitkosten $a_i$  & Einzahlung $e_i$  \\
    \hline
    \texttt{add} (ohne Umstrukturierung)        &   1                   &   3               \\
    \texttt{add} (mit Umstrukturierung)         &   $n_i$               &   2               \\
    \texttt{delete} (ohne Umstrukturierung)     &   1                   &   3               \\
    \texttt{delete} (mit Umstrukturierung)      &   $n_i$               &   2               \\
  \end{tabular}
\end{center}

Wir betrachten dabei alles zu Zeitpunkten $i \in \mathbb{N}$. Dabei ist $f_i$ die Operation zum $i.$ Zeitpunkt, $n_i$ bezeichnet
die Anzahl der Elemente im $\mathcal{DA}$ zum Zeitpunkt $i$ (vor dem Ausführen der Operation $f_i$), $a_i$ sind die dazu assoziierten (echten) Laufzeitkosten und $e_i$ die
dafür eingezahlten Beträge. Der Kontostand schwankt auch mit der Zeit und wird daher indiziert.

Dadurch, dass das Konto der Datenstruktur zugerechnet wird, und nicht nur einer speziellen Operation, können wir jetzt
auch gemischte Operationsreihenfolgen analysieren. Solange der Kontostand nicht negativ wird, sind die Einzahlungen wohl
eine ausreichende Abschätzung für die tatsächlichen Laufzeitkosten.

Wir beobachten zuerst: Die eingezahlten Kosten vor einer Umstrukturierung decken die echten Kosten dieser
Umstrukturierung:

\begin{lemma}
  Sei eine Operationenfolge $f_\bullet$ gegeben. Seien $i<j$ zwei Zeitpunkte, bei denen eine Umstrukturierung stattfindet. Dann ist
  $K_i \leq K_j$.
  \label{lemma:DA}
\end{lemma}
\begin{proof}
  Wir beobachten zuerst: Direkt nach einer Umstrukturierung, als zu Beginn von Zeitpunkt $i+1$ gilt:
  \begin{align}
    n_{i+1} = \frac{n_\text{cap}}{2}.
    \label{eq:post_resizing}
  \end{align}
  Nun gibt es zwei Fälle für die Umstrukturierung zum Zeitpunkt $j$:
  
  Fall 1: Die Umstrukturierung ist eine Erweiterung, es ist also $f_j$ gleich $\texttt{add}$.\\
  Dann gibt es mindestens $n_{i+1}$ $\texttt{add}$-Operationen zwischen Zeitpunkt $i$ und $j$, da ansonsten $n$ nicht
  genug gewachsen ist, um eine Erweiterung anzustoßen. Der Kontostand wächst daher bis zum Zeitpunkt $j-1$:
  \[
    K_{j-1} = K_i + \sum_{t=i+1}^{j-1} (e_t - a_t) \geq K_i + 3(n_{i+1}-1) - 1(n_{i+1}-1) = K_i + 2n_{i+1} - 2.
  \]
  Die Abschätzung $\geq$ rechtfertigt sich dadurch, dass zwischen $i$ und $j$ durchaus mehr als $n_{i+1}-1$ Zeitschritte liegen
  können. Beispielsweise dann, wenn in der Operationenfolge auch mal ein $\texttt{delete}$ auftaucht, was dann ein
  weiteres $\texttt{add}$ zum Ausgleich braucht.

  Im Schritt $j$ wird nach Voraussetzung eine Umstrukturierung fällig. Daher betragen die Kosten $a_j =  
  n_{\text{cap}} = 2 n_{i+1}$, während die Einzahlung $e_j = 2$ beträgt. Das entspricht aber genau der vorher
  angesparten Summe:
  \[
    K_j = K_{j-1} + e_j - a_j ≥ K_i.
  \]

  Fall 2, die Umstrukturierung in Form einer Verschmälerung verläuft analog und ist eine Übungsaufgabe.
\end{proof}

Damit können wir zeigen, dass das dynamische Array einen amortisierten Aufwand von $\mathcal{O}(1)$ hat:

\begin{theorem}
  Das dynamische Array hat einen asymptotischen Aufwand von $\mathcal{O}(1)$ für \texttt{\emph{add}}- und
  \texttt{\emph{delete}}-Operationen, auch bei gemischter Reihenfolge.
  \label{satz:DAAmo}
\end{theorem}
\begin{proof}
  Sollten keinerlei Umstrukturierungen nötig sein, ist $a_i < e_i$ klar. Aber auch bei Umstrukturierungen ist aus dem
  vorherigen Lemma klar: Ist $K_0 = 0$ und damit nicht negativ, bleibt $K_i ≥ 0$ für alle $i \in \mathbb{N}$.
  Da die tatsächliche Laufzeit $T(f_i) = a_i$, haben wir also 
  \[
    \sum_{i=1}^n T(f_i) = \sum_{i=1}^n a_i \leq \sum_{i=1}^n e_i \leq 3n.
  \]
  Das gilt für alle möglichen Operationenfolgen, also auch für die zeitaufwendigste.

  Nach Definition ist damit ist Laufzeit pro Operation 
  \[
    T_{\text{amo}}(n) = \frac{\max(\{\sum_{i=1}^n T(f_i) | f_\bullet \in \{\texttt{add}, \texttt{delete}\}^{\mathbb{N}})}{n}
      \leq \frac{3n}{n} = 3 \in \mathcal{O}(1).
  \]
\end{proof}




%\subsubsection{Aggregierte Analyse vs Accountingmethode}
%Warum nun den Extraaufwand für die Accountingmethode? Der Vorteil wird klar, wenn wir uns eine modifizierte Version von
%\texttt{delete} anschauen. Betrachten wir \texttt{delete'}, welches ident zu delete ist, nur dass der resize schon bei
%$n < \frac{n_\text{cap}}{2}$ ausgelöst wird (es ändert sich also in Zeile [1] $\frac{n_\text{cap}}{4}$ zu
%$\frac{n_\text{cap}}{2}$):
%
%Während die modifizierte Variante \texttt{delete'} in der aggregierten Analyse weiterhin
%$\mathcal{O}(1)$ amortisierten Aufwand hat, kommt es im Zusammenspiel mit \texttt{add} zu Problemen, da Gleichung
%(\ref{eq:post_resizing}) nur noch nach dem Erweitern, nicht mehr nach dem Verkleinern gilt!
%
%Sei also beispielsweise $n = n_\text{cap} = 1024$. Nun wird wird beim Hinzufügen eines weiteren Elements $n = 1025$ und
%damit $n_\text{cap}$ auf $2048$ erweitert, zusammen mit einer Kopieraufwand von $1024$ Elementen.
%Im nächsten Schritt löschen wir aber wieder das letzte Element, $n$ ist nun wieder $1024 = \frac{n_\text{cap}}{2}$,
%das Array wird verkleinert, was wieder das Kopieren von $1024$ Elementen impliziert.
%
%Hier kann eine amortisierte Analyse mittels Accountingmethode keinen amortisierten Aufwand von $\mathcal{O}(1)$
%garantieren, während die aggretierte Analyse blind für dieses Problem ist.
