Amortisierte Analyse

Transcript

Amortisierte Analyse 1 Motivation Bei vielen Algorithmen treten Folgen von Operationen auf Datenstrukturen wie zum Beispiel Stacks, Queues oder Heaps auf. Man ist dann daran interessiert die Zeit abzuschätzen, die eine solche Folge von n Operationen im worst-case benötigt. Oftmals kennt man dabei die worst-case Laufzeiten jeder einzelnen Operation, eine Abschätzung der Gesamtlaufzeit bei der man für jede Operation den worst-case annimmt erweist sich jedoch in vielen Fällen als zu pessimistisch. Amortisierte Analyse ist eine Technik, die es ermöglicht die durchschnittliche Laufzeit jeder Operation in einer Sequenz von Operationen im worst-case abzuschätzen. Dadurch ist es in vielen Fällen möglich, bessere obere Schranken an die Laufzeit bei n Operationen zu erhalten. Der intuitive Grund dafür ist, dass nicht alle Operationen teuer sein müssen, da sie zur Ausführung zum Beispiel vorangehende andere günstigere Operationen benötigen. Es gibt im Wesentlichen drei verschiedene Vorgehensweisen bei der amortisierten Analyse: die Aggregatmethode, die Guthaben-Methode und die Potentialmethode. Diese werden im Folgenden am Beispiel eines Multipop-Stacks und eines Binärzählers vorgestellt. Anwendungsbeispiel: Binärzähler Wir betrachten einen k-Bit Binärzähler. Dieser besteht aus P i einem Array von k-Bits b0 , . . . , bk−1 , das die Zahl x = k−1 i=0 2 bi codiert. Dabei ist anfangs x = 0. Der Binärzähler hat genau eine Operation increment, die x um 1 erhöht (modulo 2k ) und das Bitarray entsprechend modifiziert. Die Kosten einer Inkrement-Operation seien dabei die Anzahl der dafür benötigten Bitänderungen. 2 Die Guthaben-Methode Die Idee der Guthaben-Methode ist es, einige Operationen so zu besteuern, dass sie effektiv die Kosten anderer Operationen mittragen. Wir tun also so, als ob die Kosten dieser Operationen höher sind als ihre tatsächlichen Kosten. Diese Kosten heißen amortisierte Kosten und der Differenzbetrag zu den tatsächlichen Kosten wird dem Guthaben hinzugefügt. Dieses Guthaben wird genutzt um die Kosten von Operationen zu tragen, deren amortisierte Kosten niedriger als ihre tatsächlichen Kosten sind. Die Kunst besteht hier in der geeigneten Wahl amortisierter Kosten, da sichergestellt werden muss, dass der Kontostand niemals negativ wird. Dadurch erhält man durch die Summe der amortisierten Kosten eine obere Schranke an die Summe der tatäschlichen Kosten. Betrachten wir das Beispiel des Binärzählers: Die amortisierten Kosten für das Setzen eines Bits auf 1 seien hier 2, für das Setzen eines Bits auf 0 hingegen seien sie 0. Das Guthaben entspricht also zu jeder Zeit der Anzahl der auf 1 gesetzten Bits und ist daher nie negativ. Weiterhin wird bei jeder increment-Operation höchstens ein Bit auf 1 gesetzt. (Genauer: Es wird immer genau ein Bit auf 1 gesetzt, außer bei Erhöhung von x = 2k − 1.) Daher sind die amortisierten Kosten jeder Operation höchstens 2 und es gilt wieder T (n) = n X i=1 ti ≤ n X ai ≤ 2n = O(n). i=1 3 Die Potentialmethode Bei der Potentialmethode definiert man eine geeignete Potentialfunktion Φ, die vom aktuellen Zustand der Datenstruktur abhängt. Ähnlich wie bei der Guthaben-Methode kann ein positives Potential genutzt werden, um die Kosten zukünftiger Operationen zu bezahlen. Dabei sei Φ(0) ≥ 0 als das Ausgangspotential vor der Ausführung jeglicher Operationen und Φ(i) das Potential nach Operation i (man wählt meist Φ(0) = 0). Man beachte, dass das Potential nur vom Zustand der Datenstruktur und damit nur indirekt von den vorangegangenen Operationen abhängt. Die amortisierten Kosten werden dann als Summe der tatsächlichen Kosten und der Potentialänderung definiert: ai = ti + Φ(i) − Φ(i − 1). Dann gilt für die Summe der amortisierten Kosten n X ai = i=1 n X ti + Φ(n) − Φ(0). i=1 Wenn wir also sicherstellen können, dass für jedes i das Potential Φ(i) ≥ Φ(0) ist, dann ist die Summe der amortisierten Kosten eine obere Schranke an die Summe der tatsächlichen Kosten T (n) ≤ n X ai . i=1 Im Beispiel des Binärzählers wählen wir als Potential die Anzahl der 1-en in unserem Feld. Diese ist offenbar nie negativ. Angenommen die i-te Operation setzt ri Bits auf 0. Dann gilt für die Kosten dieser Operation ti ≤ ri + 1, da höchstens ein weiteres Bit auf 1 gesetzt wird. Für das neue Potential gilt dann Φ(i) ≤ Φ(i − 1) − ri + 1, also Φ(i) − Φ(i − 1) ≤ 1 − ri . Damit erhählt man für die amortisierten Kosten ai = ti + Φ(i) − Φ(i − 1) ≤ ri + 1 + 1 − ri = 2 und insgesamt wieder T (n) ≤ n X i=1 ai ≤ 2n = O(n).