Inkrementieren eines Binärzählers

Mit der Account-Methode wird die Anzahl der Bitwechsel bei der Inkrementation eines Binärzählers analysiert.

Elementare Operationen sind das Setzen von einem Bit von 0 auf 1 bzw. das Setzen von einem Bit von 1 auf 0. Die realen Kosten für beide Operationen werden auf eine Einheit gesetzt. Im Gegensatz dazu werden die amortisierten Kosten auf 2 bzw. 0 Einheiten gesetzt. Wenn ein Bit auf 1 gesetzt wird, entstehen zwei Einheiten amortisierte Kosten von denen nur eine verbraucht und der Rest auf das Konto eingezahlt wird. Bei dem Bit-Wechsel von 1 nach 0 muss eine Einheit amortisierte Kosten von dem Konto bezahlt werden.

Da nun bei jeder Inkrementation des Zählers genau ein Bit von 0 auf 1 gesetzt wird, enthält das Konto genug Einheiten um alle möglichen Wechsel von 1 auf 0 zu bezahlen. Also sind die amortisierten Gesamtkosten für ${\displaystyle n}$ Inkrementation in O${\displaystyle (n)}$.

Dynamisches Array

In der Praxis werden oft dynamische Arrays benötigt. Eine Strategie dynamische Arrays zu implementieren ist ein statisches Array immer dann zu verdoppeln, wenn es voll ist. Wir wollen die sogenannte Kontenmethode verwenden, um zu zeigen, dass die amortisierten Kosten der Einfügeoperationen O(1) sind. Wir werden feststellen, dass wir bei einer Eingabe der Größe n nur eine Laufzeit von O(1) haben. Im Durchschnitt haben wir also nur konstante Laufzeit, weil wir nicht bei jeder Einfügeoperation das Array vergrößern, sondern nur bei jeder (n+1)ten Einfügeoperation. Die (günstigen) Einfügeoperationen lassen wir auf ein gedachtes Konto einzahlen, so dass die teueren Operationen, das Vergrößern der Tabelle, bezahlt werden können.

T sei ein Array, E sei ein Element, das eingefügt werden soll. num(T) ist die aktuelle Zahl der Elemente von T, und size(T) ist die aktuelle Größe von T. Wir nehmen an, dass folgende Methoden bereits existieren: create_table(n), welche ein leeres Array mit Größe n anlegt (wir nehmen zunächst zur Vereinfachung an, dass diese Methode Laufzeit = 0 hat), elementary_insert(T,E), das ein Element E in ein Array T speichert, mit Laufzeit von O(1).

Wir betrachten folgenden Pseudocode:

function table_insert(T,E)
    if num(T) = size(T)
        U := create_table(size(T) + 1)
        for each F in T
            elementary_insert(U,F)
        destroy_table(T)
        T := U
    elementary_insert(T,E)

Für das Einfügen von n Elementen in das Array T ergibt sich eine Worst-Case Laufzeit von O(n²) — dies liegt an der for-each-Schleife in Zeile 4, die bei jedem Aufruf von table_insert durchlaufen wird und num(T) elementare Einfügeoperationen verursacht.

Wird in der Zeile 3

        U := create_table(size(T) × 2)

geschrieben, ergibt sich, da die for-each-Schleife wesentlich seltener durchlaufen wird, ein Aufwand von O(3×n−3).

Wenn wir den Algorithmus differenzierter betrachten, dann können wir die Kontenmethode nutzen. Hierfür legen wir eine Einzahlung von drei Tokens (oder Zeiteinheiten) für jede Einfügeoperation fest. Dadurch können diese günstigen Operationen die teueren Operationen bezahlen. Warum es mindestens drei Token sein müssen, sieht man später.

Wir nehmen an, dass die Tabelle anfangs leer ist und Größe size(T) = m hat. Die ersten m Einfügeoperationen brauchen daher keine Vergrößerung der Tabelle und haben eine Laufzeit von O(1). Jede Einfügeoperation kostet zunächst mal ein Token. D.h. es können pro Einfügeoperation effektiv zwei Token auf dem Konto eingezahlt werden.

Wenn wir die ersten m Elemente einfügen, ist das Array voll und es gilt: num(T) = m. Das Konto hat (3 - 1)×m = 2m Tokens. Wenn wir das (m + 1)te Element einfügen, muss das Array vergrößert werden. Das Erstellen einer Tabelle soll zunächst Laufzeit von 0 haben. Die Schleife in Zeile 4 braucht n elementare Einfügeoperationen, was genau m Tokens kostet. Wenn man die Einfügeoperation in der letzten Zeile hinzunimmt, betragen die Gesamtkosten für die Operation m + 1. Nach dieser Operation liegen auf dem Konto noch 2m + 3 - (m + 1) = m + 2 Tokens. Nun fügen wir weitere m - 1 Elemente in das Array. Das Konto hat jetzt m + 2 + 2×(m - 1) = 3m Tokens. Wenn wir ein weiteres Element anfügen (das ist das (2m + 1)te Element) dann verursacht die Operation Kosten von 2m + 1 Tokens und (wie jede Einfügeoperation) eine Einzahlung von drei Tokens. Nach dieser Operation hat das Konto 3m + 3 - (2m + 1) = m + 2 Tokens. Beachte: Das ist derselbe Kontostand wie nach dem Einfügen vom (m + 1)ten Element. Wir können zeigen, dass dies immer der Fall ist, egal wie oft das Array verdoppelt wird.

Wir können nun erklären, wieso die Tokenzahl für eine Einfügeoperation mindestens drei sein muss: Ein Token wird direkt für das Einfügen des neuen Elements verbraucht, ein Token wird reserviert, für den Fall, dass die Tabelle verdoppelt wird und das eingefügte Element kopiert werden muss, und der letzte Token wird für das Kopieren eines anderen Elements reserviert, das bereits vor der letzten Verdoppelung des Arrays in dem Array vorhanden war. (d. h. bei size[T] = m, zahlen m/2 Elemente für m Elemente die nächste Kopieraktion im Voraus, bei einem neu erstellten Array wird das dritte Token gar nicht verbraucht). Beachte: Die Tokens einer Einfügeoperation werden genau zur nächsten Verdoppelung zugeordnet.

Wir haben angenommen, dass das Erstellen eines neuen Arrays eine Laufzeit von 0 hat. In der Realität kann das Erstellen eines Arrays der Größe n eine Laufzeit von O(n) haben. Würde das was an unserer Überlegung ändern? Nein, es stellt sich heraus, dass wir mit derselben Methode zeigen können, dass die amortisierte Laufzeit wieder O(1) ist. Wir müssen nur die Tokeneinzahlung anders definieren:

Wenn ein neues Array mit Größe 2m erstellt wird, gibt es ein aktuelles Array mit Größe m. Wenn die Elemente im aktuellen Arrays genug Tokens auf das Konto eingezahlt haben, gibt es keine Probleme und wir erhalten wieder eine konstante Laufzeit. Wie müssen wir nun die Tokeneinzahlung definieren? Wir können nicht erwarten, dass die ersten ${\displaystyle {\frac {m}{2}}}$ Elemente für die neue Tabelle zahlen. Diese haben bereits für das aktuelle Array gezahlt. Wir müssen also die letzten ${\displaystyle {\frac {m}{2}}}$ Elemente dafür zahlen lassen. Also müssen wir ${\displaystyle {\frac {2m}{m/2}}=4}$ Tokens zu der Zahlung jeder Einfügeoperation hinzufügen, so dass jede Einfügeoperation nun 3 + 4 = 7 Tokens kosten muss.

Schritte bei der amortisierten Laufzeitanalyse:

Löschoperationen lassen sich genauso analysieren. Bspw. wäre eine Verkleinerung der Tabelle genauso sinnvoll, wenn man Speicherplatz sparen will. Man würde hierfür pro Elementarlöschoperation sogar nur zwei Tokens brauchen. Anschaulich lässt sich das leicht begründen: Bei einer Vergrößerung müssen m/2 Elemente für den Aufwand m Elemente zu kopieren aufkommen. Bei einer Verkleinerung muss jedes Element nur ein Token für das Kopieren auf das Konto eingezahlt haben.