Aggregat-Methode
www.infos-aus-germanien.info
Einordnung: Theoretische Informatik
- Was heißt Aggregat-Methode auf:
Englisch - Französisch - Italienisch - Niederländisch und Schwedisch sowie Spanisch
- Sie wissen mehr über das Thema Aggregat-Methode und möchten uns dazu etwas mitteilen?
Benutzen Sie dazu bitte unser Forum und eröffnen Sie einen neuen Thread zum Thema 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. Dies sei am Beispiel eines Binärzählers gezeigt, dessen einzig mögliche Operation in der Inkrementation bestehe.
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ächst höhere bei jeder zweiten, das wiederrum nächst höhere bei jeder vierten usw. Damit ergibt sich bei n Inkrementationen folgende Summe von Bitwechseln:
<math>n + \lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{2^2}\rfloor + \lfloor\frac{n}{2^3}\rfloor + ... + \lfloor\frac{n}{2^k}\rfloor = n \sum_{i=0}^k \lfloor\frac{1}{2^i}\rfloor <math>
Diese Summe können wir nach oben abschätzen:
<math>n \sum_{i=0}^k \lfloor\frac{1}{2^i}\rfloor \leq n \sum_{i=0}^\infty \frac{1}{2^i}<math>
Die Summe dieser unendlichen Reihe ist wohlbekannt und lautet 2. Daraus folgt:
<math>n \sum_{i=1}^k \lfloor\frac{1}{2^i}\rfloor \leq 2n<math>
Betrachten wir nun die amortisierten Kosten <math>a_i<math>für eine einzelne Operation <math>Op_i<math> der insgesamt n Operationen, indem wir die bereits ermittelten Gesamtkosten durch die Anzahl n der Operationen teilen, erhalten wir:
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.
- Suche nach Aggregat-Methode Infos mit: Yahoo