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.

Beispiel

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=1}^k \frac{1}{2^i} \leq 2n

Betrachten wir nun die amortisierten Kosten ai für eine einzelne Operation Opi 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.

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 kann 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.

Literatur

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7, S. 406-410.

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Account-Methode — Die Account Methode (oder auch Bankkonto Paradigma bzw. Buchungsmethode) ist eine Verfahrensweise der amortisierten Laufzeitanalyse. Nach der Account Methode werden den realen Kosten einzelner Operationen eines Algorithmus amortisierte Kosten… …   Deutsch Wikipedia

  • Amortisierte Analyse — In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die durchschnittlichen Kosten von Operationen in Folgen. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht nur die maximalen Kosten der einzelnen Schritte… …   Deutsch Wikipedia

  • Amortisierte Laufzeitanalyse — In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die durchschnittlichen Kosten von Operationen in Folgen. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht nur die maximalen Kosten der einzelnen Schritte… …   Deutsch Wikipedia

  • Kommandogerät-6 — Das Kommandogerät 6 (russisch: Прибор управления артиллерийским зенитным огнем 6, abgekürzt ПУАЗО 6, Transkription: Pribor uprabljenia artilleriskim senitnuim ognem) diente zur Führung des Feuers von Flak Batterien. Mit Hilfe des Gerätes wurde… …   Deutsch Wikipedia

  • Elektrische Eisenbahnen — (electric railways; chemins de fer électriques; ferrovie elettriche). Inhaltsübersicht: I. Allgemeine Entwicklung und Zukunft des elektrischen Bahnbetriebes. – II. Nutzbarmachung der Wasserkräfte für die Anlage der Stromquellen. – III.… …   Enzyklopädie des Eisenbahnwesens

  • Scuderia-Ferrari — Ferrari Name Scuderia Ferrari Marlboro Unternehmen Ferrari SpA Unternehmenssitz Maranello (I) …   Deutsch Wikipedia

  • Scuderia Ferrari — Ferrari …   Deutsch Wikipedia

  • Aggregometrie — Die Thrombozytenaggregometrie oder Thrombozytenaggregationsmessung ist ein Labortest zur Prüfung der Thrombozytenfunktion. Störungen der Funktionsfähigkeit von Thrombozyten kann durch angeborene Defekte zustande kommen oder durch die Einnahme von …   Deutsch Wikipedia

  • Light Transmission Aggregometry — Die Thrombozytenaggregometrie oder Thrombozytenaggregationsmessung ist ein Labortest zur Prüfung der Thrombozytenfunktion. Störungen der Funktionsfähigkeit von Thrombozyten kann durch angeborene Defekte zustande kommen oder durch die Einnahme von …   Deutsch Wikipedia

  • Thrombozytenaggregationsmessung — Die Thrombozytenaggregometrie oder Thrombozytenaggregationsmessung ist ein Labortest zur Prüfung der Thrombozytenfunktion. Störungen der Funktionsfähigkeit von Thrombozyten kann durch angeborene Defekte zustande kommen oder durch die Einnahme von …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”