# 9 Amortisierte Analyse

[TOC]

[comment]: # (Zuerst ein paar LaTeX-Makros:)

$\newcommand{\N}{\mathbb{N}}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\O}{\mathcal{O}}$

*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).

## Einführung

Heute behandeln wir die Analysetechnik der amortisierten Analyse. Ein erstes Mal hatten wir diese bereits gesehen, als wir argumentiert haben, dass Quicksort nie mehr als $\O(n \log n)$ Vertauschungen durchführt. Heute wollen wir diese Technik formalisieren und viele weitere Beispiele davon sehen.

## Beispiel: ``upin``-Aufwand im AVL-Baum

Erinnern wir uns daran, was wir zum AVL-Baum schon gesehen haben:
Suche im AVL-Baum: $\O(\log n)$
Einfügen: Suchen + $\O(\log n)$ fürs Hochlaufen in ``upin``

Wie weit muss das ``upin`` wirklich hochpropagieren? In einer einzigen Einfügeoperation kann es durchaus sein, dass wir bis ganz noch oben zur Wurzel zurück suchen müssen und ``upin`` logarithmisch viele Schritte braucht. (Rotationen braucht es aber immer nur eine.) Aber was wir heute zeigen wollen ist, dass dies nicht immer wieder passieren kann. Wir wollen also zeigen, dass auf lange Sicht, also über viele Operationen hinweg, im Schnitt nicht logarithmisch viel Aufwand für ``upin`` nötig ist.

Wir betrachten den Worst Case über eine Folge von Operationen. Wir beginnen mit einem leeren Baum und führen $m$ Einfüge-Operationen durch. Wir argumentieren, dass die *totalen* Kosten nicht $\O(m \log m)$ sondern $\O(m)$ sind. Die Frage ist, wie beweisen wir diese Aussage?

Wir schauen unseren AVL-Baum an und sagen, dass ein Knoten in *strikter Balance* ist, wenn seine beiden Teilbäum genau gleich hoch sind. Wir legen nun einen fiktiven Dollar auf jeden Knoten, der in strikter Balance liegt. Dieser Dollar soll nun dafür bezahlen, wenn wir später über diesen Knoten hinweg mit ``upin`` hochlaufen.

Wie wir gesehen haben, müssen wir ``upin`` nur rekursiv aufrufen, wenn der Knoten vor dem Einfügen in strikter Balance war. Bei jedem Knoten in strikter Balance, liegt ein Dollar, mit dem wir das Hochprogieren bezahlen können. Da wir nur weiter aufsteigen, wenn wir die Balance von $0$ auf $1$ oder $-1$ geändert haben, dürfen wir diesen Dollar aufbrauchen, ohne unsere Invariante zu verletzen. Am Schluss dieser rekursiven Aufrufe endet ``upin`` entweder, weil die Balance neu direkt $0$ ist oder weil wir eine Rotation durchführen und somit die Balance auf $0$ bringen. Bei allen Knoten, die *neu* in Balance sind, müssen wir einen Dollar hinterlegen. Dies ist zum einen das neue Blatt $p$ und zum anderen sind es bis zu zwei der bis zu drei in die (Doppel-)Rotation involvierten Knoten in der Nähe des Knotens $q$ bei dem ``upin`` endet. Pro Einfügeoperation müssen wir also nur $2$ bis $3$ Dollar ausgeben. Somit sind die amortisierten Kosten, also die Kosten, die wir nicht mit den gesparten Dollars begleichen können konstant pro Einfügeoperation.


Als Analogie können wir uns das so vorstellen: Die Münzen in unserem AVL-Baum sind unsere Sparkasse, die uns hilft teure Operationen abzuzahlen. Alles was wir nicht aus der Sparkasse bezahlen können und alles was wir in die Sparkasse einwerfen, kommt aus unserem Geldbeutel. Die amortisierte Analyse erlaubt uns nun unseren Geldbeutel möglichst gleichmässig zu belasten, hier heisst das, dass wir in jedem Schritt nur einen konstanten Betrag ausgeben.

## Beispiel: Stapelspeicher

Ein anderes (einfacheres) Beispiel für die amortisierte Anlyse sei ein Stapel (engl. *Stack*). Wir können mit ``push`` in $\O(1)$ Elemente auf den Stapel legen und ebenfalls in $\O(1)$ das oberste Element mit ``pop`` entfernen. Wir erlauben nun eine weitere Operation ``multipop(k)``, die so lange Elemente entfernt, bis ein Element ``k`` entfernt wird. Für einen Stapel mit $n$ Elementen kostet uns ein ``multipop(k)`` lineare Laufzeit $\O(n)$, da wir im schlimmsten Fall alle Elemente auf dem Stapel entfernen müssen.

|2|
|8|
|2| -> multipop(7) -> |5|
|7|
|5|

Betrachten wir eine Folge von $m$ Operationen. Ohne amortisierte Analyse würde unserer grobe Analyse $O(m^2)$ Kosten ergeben. Intuitiv ist aber klar, dass $m$ Operationen auf einem leeren Stapel nicht so viel kosten können, denn wir können ja insgesamt höchstens $m$ Elemente einfügen, weshalb ``multipop`` nicht $m$ Mal $\Theta(m)$ kosten kann.

Wir machen diese Intuition formal, indem wir bei jedem Einfügen noch einen zusätzlichen Dollar auf den Stapeleintrag hinlegen, der dann fürs spätere ``pop``, bzw. fürs ``multipop`` des Elementes bezahlt. Alle späteren ``pop`` und ``multipop`` sind dann also quasi schon bezahlt.

Also hat ``push`` amortisierte Kosten $2$ und die anderen Operationen ``pop`` und ``multipop`` amortisierte Kosten $0$. Daraus kriegen wir die *amortisierten Gesamtkosten* von $2m$ was uns asymptotisch $\O(1)$ pro Operation ergibt. Amortisiert analysiert geht es also viel besser!

Machen wir es noch etwas formaler. Wir können, den Kontostand auch als Invariante betrachten. Dazu definieren wir eine Kontostandsfunktion:
$$\begin{align}
\text{Kontostand} &= \text{Anzahl Stapelelemente}\\
bal_l &= \text{Kontostand nach der $l$-ten Operation}\\
t_l &= \text{tatsächliche Kosten der $l$-ten Operation}\\
a_l &= \text{amortisierte Kosten der $l$-ten Operation}\\
\hline
a_l &= t_l + bal_l - bal_{l-1}\\
\Sigma_{l=1}^{m} a_l &= \Sigma_{l=1}^{m} t_l + bal_m - bal_0\\
\text{Wir wollen } \Sigma_{l} a_l &\geq \Sigma t_l \text{ und } bal_m - bal_0 \geq 0 \text{ durch } \forall l: bal_l \geq 0
\end{align}$$

Wenn wir den Kontostand geschickt wählen, müssen wir somit nur noch überprüfen, dass wir die gewünschten amortisierten Kosten $a_l$ erhalten und dass wir unser Konto nie überziehen ($\forall l: bal_l \geq 0$). Für unser ``push`` ist $t_l=1$ und $bal_l - bal_{l-1} = 1$ und somit $a_l = 2$. Fürs Multipop ist $t_l$ die Anzahl entfernter Elemente, was gleich auch der negative Bankkontodifferenz entspricht, weshalb $a_l=0$.

## Beispiel: Binärer Zähler
Wir beginnen bei $0$ und zählen hoch. Die Frage ist wie viel ein "plus eins" kostet, d.h. wie viele Bitflips nötig sind.

$10111011$ $\ra$ $10111100$
$k$-stellige Zahl (mit Overflow Wrap-around)

Wenn wir um eins erhöhen beginnen wir rechts und flippen die Bits der Reihe nach, bis wir eine Null in eine Eins flippen.

Es ist klar, dass wir höchstens $k$ Bits flippen. Mit etwas Überlegung findet man jedoch heraus, dass wir amortisiert nur $\O(1)$ Bits flippen müssen, indem wir bei jedem Einfügen für zwei Flips bezahlen.

Eine Art das zu sehen ist die Folgende: Jedes zweite Hochzählen braucht nur einen Flip, denn die erste Stelle ist ja immer abwechslungsweise $0$ und $1$. Und wenn die letzte Stelle $0$ ist, sind wir nach nur einem Flip ferig. Jedes vierte Hochzählen braucht 2 Flips, jedes $2^{k}$-te braucht $k$ Flips. Die gesamte Summe über $n$ Hochzählschritte wird also $\O(n)$ Flips benötigen (Geometrische Summe).

In unserem Goldmünzenmodell ist die Argumentation noch einfacher. Wir sagen, dass wir jedes Mal wenn wir eine $0$ in eine $1$ flippen, eine Münze deponieren, die für das spätere Zurückflippen dieser $1$ in eine $0$ bezahlen kann. Damit sind dann die amortisierten Kosten jeder Operation gleich $2$, da wir nur für das neue $1$-Bit aus dem Geldbeutel bezahlen müssen und alle auf $0$ zurückgesetzten Bits aus dem Bankkonto bezahlen können.^[Im Falle eines Overflows sind die amortisierten Kosten gar $0$, da wir gar keine neue $1$ erstellen.]

## Kompetitive Analyse für Häufigkeiten von Suchabfragen in linearen Listen

Wir haben eine lineare Liste in der wir nach Schlüsseln suchen können. Wir erlauben kein Einfügen oder Entfernen, aber wir wollen die Analyse etwas genauer machen als einfach nur zu sagen "im schlimmsten Fall ist alles linear".

-> a -> b -> c -> d

Nehmen wir an, dass wir sehr verschieden häufig nach den verschiedenen Schlüssel in der Liste suchen. Es gibt sozusagen "Lieblingsschlüssel" nach denen besonders häufig gesucht wird, z.B sucht man in einer Personendatenbank der ETH vielleicht am öftesten nach der Rektorin, einzelne Studenten werden hingegen selten gesucht.

Können wir die Listenstruktur nun etwas umarrangieren, sodass die Suche schneller geht?

### Frequency Count

Erste Idee: Wenn ich die Häufigkeiten kenne, kann ich die Liste einfach nach Häufigkeit absteigend sortieren. Zuvorderst der häufigste Schlüssel, dann der zweithäufigste etc. Dann hab ich für den "beliebtesten" Knoten nur Kosten $O(1)$.

### Transpose
Aber was machen wir wenn wir die Häufigkeiten der Schlüssel nicht kennen?

Wir könnten das gesuchte Element jeweils ein wenig nach vorne rücken, sodass es, wenn es immer wieder gesucht wird, mit der Zeit am Anfang der Liste landet. Diese Idee namens *transpose* tauscht also immer den gesuchten Listeneintrag mit seinem Vorgänger. Am teuersten wird dies, wenn man immer nach dem letzten Element sucht.

Beispiel

-> ... -> y -> x
(Suche nach x)
-> ... -> x -> y
(Suche nach y)
-> ... -> y -> x
(Suche nach x)
-> ... -> x -> y
(Suche nach y)
-> ... -> y -> x
...

Für $m$ Operationen auf einer Liste der Länge $n$ ergeben sich also Kosten $\Theta (m\cdot n)$. Im schlimmsten Fall laufen wir also doch immer bis ganz ans Ende. Doch ist das unser Fehler? Kann es ein anderes Listenoptimuerngsverfahren geben, das auf der *selben* Abfragefolge deutlich besser ist?

### Move to front

Eine solche Strategie heisst *move to front* und setzt jeweils beim Zugriff das Element ganz an den Anfang der Liste.

-> y -> ... -> x ->... (wir suchen nach x)
-> x -> y --------> (wir setzen x an den Anfang)

Das teure Beispiel von *transpose* funktioniert hier jetzt nicht mehr. Nach zwei Operationen sind $x$ und $y$ ganz vorne und wir haben nur noch konstanten Aufwand pro Operation.

Wir vergleichen unsere Methode jetzt mit einem *idealen* Konkurrenten $A$. Kann der viel besser sein?

Wir nehmen dabei an, dass unser Konkurrent so wie Move to Front nur das zugegriffene Element $x$ bewegen darf, die anderen Elemente also nicht vertauscht. Aber der Konkurrent könnte $x$ statt ganz nach vorne sonst irgendwohin schieben und wir wollen argumentieren, dass dies nicht (viel) besser sein kann.

Wir betrachten als Kosten die Anzahl Vertauschungen in der Liste. Dabei sagen wir, dass das Vertauschen von $x$ nach vorne nichts kostet (denn diese Elemente haben wir bereits bei der Suche angeschaut) und nach hinten kostet es so viel, wie die Distanz um die das Element nach hinten verschoben wird. Also:
* nach vorne: gratis (später $F$ für *free*)
* nach hinten: kostet (später $X$ für *extra*)

Behauptung: Move to front ist nicht schlechter als ein idealer Konkurrent.

Unser Verfahren $MTF$ und das optimale $A$ starten beide mit der selben Liste.

Als Kontostand nehmen wir die Anzahl der Inversionen zwischen den beiden Listen, also die Anzahl Paare, die in $A$ anders rum sind als in $MTF$

A 4 2 3 1 5
MTF 2 3 1 4 5

Dieses Beispiel hat drei Inversionen ($12$,$13$,$14$). Äquivalent dazu können wir $A$ auch umnummerieren von $1$ bis $5$:

A 1 2 3 4 5
MTF 2 3 4 1 5

Somit steht in $A$ an $i$-ter Stelle das Element $i$. Schauen wir uns nun an, was bei einem Zugriff auf das Element $i$ passiert. In $MTF$ steht es an einer Stelle $k$ und wir schieben es ganz nach vorne.


Was passiert mit unserem Kontostand, der Anzahl Inversionen?

Dazu bezeichnen wir mit $x_i$ die Anzahl Elemente, die in $A$ nach $i$ und in $MTF$ vor $i$ stehen (die Kreise in der Skizze oben). Bei einem Zugriff auf $i$ in der $l$-ten Operation gilt deshalb:
$bal_l = bal_{l-1}\underbrace{-x_i+(k-1-x_i)}_{\text{MTF schiebt i nach vorne}}- F^{A}_{l}(i) + X_{l}^{A}(i)$, wobei
* $x_i$ Inversionen gegenüber $A$ aufgeflöst werden und $k-1-x_i$ neue entstehen,
* $F^{A}_{l}(i)$ die Anzahl freier Tauschungen bezeichnet, wenn $A$ das $i$ nach vorne schiebt, und
* $X^{A}_l(i)$ die Anzahl extra Tauschungen bezeichnet, wenn $A$ das $i$ nach hinten schiebt.

$F^{A}_{l}(i)$ und $X^{A}_l(i)$ beschreiben also, wie die Aktion von $A$ den Bankkontostand beeinflusst. Da wir $A$ nicht explizit kennen, können wir diese Werte nur abschätzen.

Nun gilt für die amortisierten Kosten von $MTF$:

$$\begin{align}a_l^{MTF}
&=\underbrace{k-x_i}_{\leq i} + \underbrace{k-1 -x_i}_{\leq i-1} - F^{A}_{i} + X_{l}^{A}(i) \\
&\leq 2i-1- F^{A}_{i} + X_{l}^{A}(i)\\
&= 2 \cdot C_{l}^{A} (i) - 1 - F_{l}^{A} (i) + X_{l}^{A}(i),\end{align}$$
wobei $C_l^A(i)$ die Kosten von $A$ zum Suchen von $i$ bezeichnet. Es gilt $C_l^A(i) = i$, da wir ja so nummeriert haben, dass $i$ in $A$ an $i$-ter Stelle steht.

Daraus folgt nun, wenn wir über alle Operationen summieren
$$\sum_{l=1}^m t_l^{MTF}
\leq \sum_{l=1}^m a_l^{MTF}\\
\leq 2\sum_{l=1}^m C_l^{A}(i) \underbrace{- m - \sum_{l}F_l^A(i)}_{\leq 0} + \sum_l X_l^A(i)\\
\leq 2\underbrace{\left(\sum_l C_l^A(i) + \sum X_l^A(i)\right)}_{\text{Kosten von A}}.
$$

Somit sind die Kosten von Move to Front gesamthaft höchstens das Doppelte von $A$ und wir sagen daher, dass MTF $2$-kompetitiv ist.