Aggregat-Methode
# Aggregat-Methode

Die Aggregat-Methode (auch Aggregationsmethode oder Ganzheitsmethode) ist ein Vorgehen der amortisierten (Laufzeit-)Analyse. Bei der Aggregat-Methode wird versucht die durchschnittlichen Kosten einer Einzeloperation zu ermitteln, indem man zunächst die Gesamtkosten aller Operationen ermittelt und diese dann durch die Anzahl der Operationen dividiert.

## Beispiele

### Binärzähler

Die Aggregat-Methode wird am Beispiel eines Binärzählers, dessen einzig mögliche Operation eine Inkrementation ist, durchgeführt.

Der Worst Case bei einem Binärzähler mit k Bit tritt dann auf, wenn bei einer Inkrementation alle k Bit gekippt werden müssen. Seien die Kosten für einen Bitwechsel 1. Dann würden nach der Worst-Case-Abschätzung bei n Operationen Kosten von nk entstehen. Diese Abschätzung ist allerdings zu pessimistisch. Mittels der amortisierten Analyse wird versucht eine realistischere und weniger pessimistische Abschätzung der Kosten nach oben zu erreichen.

Betrachten wir die Anzahl der Bitwechsel bei einem Zähler mit 4 Bit:

| Zähler | Anzahl Bitwechsel |
| - | - |
| 0000 | - |
| 0001 | 1 |
| 0010 | 2 |
| 0011 | 1 |
| 0100 | 3 |
| 0101 | 1 |
| 0110 | 2 |
| 0111 | 1 |
| 1000 | 4 |

Wenn man sich die Folge der Bitwechsel anschaut, fällt auf, dass sich das niedrigste Bit bei jeder Inkrementation ändert, das nächsthöhere bei jeder zweiten, das wiederum nächsthöhere bei jeder vierten usw. Damit ergibt sich bei n Inkrementationen folgende Summe von Bitwechseln:

$n+\left\lfloor {\frac {n}{2}}\right\rfloor +\left\lfloor {\frac {n}{2^{2}}}\right\rfloor +\left\lfloor {\frac {n}{2^{3}}}\right\rfloor +\cdots +\left\lfloor {\frac {n}{2^{k}}}\right\rfloor \leq n\sum _{i=0}^{k}{\frac {1}{2^{i}}}$

Diese Summe können wir nach oben abschätzen:

$n\sum _{i=0}^{k}{\frac {1}{2^{i}}}\leq n\sum _{i=0}^{\infty }{\frac {1}{2^{i}}}$

Die Summe dieser unendlichen Reihe ist wohlbekannt und lautet 2. Daraus folgt:

$n\sum _{i=0}^{k}{\frac {1}{2^{i}}}\leq 2n$

Betrachten wir nun die amortisierten Kosten $a_{i}$ für eine einzelne Operation $Op_{i}$ der insgesamt n Operationen, indem wir die bereits ermittelten Gesamtkosten durch die Anzahl n der Operationen teilen, erhalten wir:

$a_{i}\leq {\frac {2n}{n}}=2$

Damit sind die amortisierten Kosten für eine Operation höchstens 2 und somit in O(1), egal, wie viele Bits der Zähler insgesamt hat.

### Wörterbuch

Eine außerordentlich verbreitete Sorte von Datenstrukturen sind die binären Suchbäume. Sie lösen bspw. das “Wörterbuch”problem (s. Binärer Suchbaum#Motivation), und zwar die balancierten unter ihnen die wichtigsten Operationen im schlechtesten Fall (worst case) in logarithmischer Zeit. Eine Aussage über amortisiertes Laufzeitverhalten findet sich ggf. im entsprechenden Artikel.

Hier werde eine Datenstruktur, genannt amortisierte Wörterbuch-Datenstruktur (englisch amortized dictionary data structure), vorgestellt, deren amortisiertes Laufzeitverhalten für das Suchen in $O(log^2$ n) und für das Einfügen in O(log n) ist.

Die Anzahl n der Einträge sei in der binären Darstellung:

    $n=:\sum _{i=0}^{k}\lambda _{i}2^{i}$ mit $\lambda _{i}\in \{0,1\}$

Die Datenstruktur besteht dann aus k+1 sortierten Folgen, die entweder ganz leer $(λ_i=0)$ oder ganz voll $(λ_i=1)$ sind. Die einzelnen Elemente der Datenstruktur werden beliebig auf diese Folgen verteilt.

Beispiel: Es sei n = 11 (dann ist 11 = 1 + 2 + 8 und k = 3). Die Elemente seien C,D,E,F,H,J,M,P,S,W und Y, die wie folgt über die Datenstruktur verteilt seien:

    $Λ_0:[E]λ_0$ = 1 $Λ_1:[D,H]λ_1$ = 1 $Λ_2:leerλ_2$ = 0 $Λ_3:[C,F,J,M,P,S,W,Y]$ $λ_3$ = 1

Eine Suchoperation geschieht durch binäres Suchen in jeder Folge $Λ_i$ dar, plus einer logischen Zusammenfassung, so dass sich im schlechtesten Fall das Laufzeitverhalten

    $\sum _{i=0}^{k}\lambda _{i}\lceil \log(2^{i}+1)\rceil +k+1=\sum _{i=0}^{k}\lambda _{i}(i+1)+k+1$ = $O(log^2$ n)

ergibt.

Eine Einfügung verwendet Mergesort, dessen Aufwand durch die Summe der beiden Längen gegeben ist. Um den Buchstaben K einzufügen, wird eine Folge Λ der Länge 1 mit dem Inhalt K gebildet. Ist nun $Λ_0$ leer (Häufigkeit 1/2), machen wir Λ zu $Λ_0$ und sind fertig. Wenn nicht (wie im obigen Beispiel) (Häufigkeit 1/2), mischen (englisch merge) wir Λ mit $Λ_0$ mit Aufwand 1 + 1; der Name des Ergebnisses sei wieder Λ. Ist dann $Λ_1$ leer (Häufigkeit 1/4), machen wir Λ zu $Λ_1$ und sind fertig. Wenn nicht (Häufigkeit 1/4), mischen wir Λ mit $Λ_1$ mit Aufwand 2 + 2 und neuem Namen Λ. Ist dann $Λ_2$ leer (wie im obigen Beispiel) (Häufigkeit 1/8), machen wir Λ zu $Λ_2$ und sind fertig. Wenn nicht (Häufigkeit 1/8), geht es weiter wie gehabt. Im obigen Beispiel ergibt die Einfügung von K:

    $Λ_0:leerλ_0$ = 0 $Λ_1:leerλ_1$ = 0 $Λ_2:[D,E,H,K]λ_2$ = 1 $Λ_3:[C,F,J,M,P,S,W,Y]$ $λ_3$ = 1

Der Gesamtaufwand ist maximal

    1/2·(1 + 1) + 1/4·(2 + 2) + ... + $2^{–k}·2^k$ = k + 1 in O(log n)

**Ergebnis**

Bei der vorgestellten Datenstruktur sind die amortisierten Kosten für eine Einfügung in O(log n).

**Bemerkung**

Sie sind damit nicht besser als bei AVL- oder Rot-Schwarz-Bäumen, bei denen reine Einfügungen (reine Baumänderungen) amortisiert konstant sind, das Aufsuchen der Einfügeposition mit O(log n) aber noch hinzugerechnet werden muss. Bemerkenswerterweise sind die Einfügekosten jedoch kleiner als zugehörige reine Suchkosten.

## Abgrenzung

Im Gegensatz zur Account-Methode werden bei der Aggregat-Methode die amortisierten Kosten auch von unterschiedlichen Arten von Operationen gleichgesetzt. D. h., mit der Account-Methode können verschiedenen Arten von Operationen unterschiedliche amortisierte Kosten zugeordnet werden. Außerdem wird bei der Account-Methode die Differenz zwischen amortisierten und realen Kosten auf einem Konto gebucht.

