Amortisierte Analyse Prof. Dr. S. Albers
Prof. Dr. Th. Ottmann
Amortisierte Analyse Prof. Dr. S. Albers
Prof. Dr. Th. Ottmann
Amortisierung
Betrachte eine Folge a1, a2, ... , an von
n Operation auf Datenstruktur D
Ti = Ausführungszeit von ai
T = T1 + T2 + ... + Tn, Gesamtlaufzeit
Oft kann die Laufzeit einer einzelnen Operation in einem großen Bereich schwanken, z. B. in
1,...,n,
aber nicht bei allen Operationen der Folge kann der schlechteste Fall auftreten
Analyse von Algorithmen
Best Case
Worst Case
Average Case
Amortisierte Worst Case
Was sind die durchschnittlichen Kosten
einer schlechtest möglichen Folge
von Operationen?
Amortisierung
Idee:
Zahle für billige Operation etwas mehr
Verwende Erspartes um für teure Operationen zu zahlen
Drei Methoden:
1. Aggregatmethode
2. Bankkonto – Methode
3. Potentialfunktion – Methode
Idee:
Bezahle zwei KE für das Verwandeln einer 0 in eine 1
jede 1 hat eine KE auf dem Konto
Beobachtung:
In jedem Schritt wird genau eine 0 in eine 1 verwandelt
Potentialfunktion
Datenstruktur D (D)
tl = wirkliche Kosten der l-ten Operation
l = Potential nach Ausführung der l-ten Operation (= (Dl) )
al = amortisierte Kosten der l-ten Operation
Definition:
al = tl + l - l-1
Beispiel: Dualzähler
Di = Stand der i-ten Operation
i = (Di) = # von Einsen in Di Bi-1 Di-1: .....0/1.....01.....1 Bi = Bi-1 – bi + 1 Di : .....0/1.....10.....0 # von Einsen i–te Operation ti = wirkliche Bitwechselkosten von Operation i
= bi+1
Dualzähler
ti = wirkliche Bitwechselkosten von Operation i
ai = amortisierte Bitwechselkosten von Operation i
Dynamische Tabellen
Problem:
Verwaltung einer Tabelle unter den Operationen Einfügen und
Entfernen, so dass
die Tabellengröße der Anzahl der Elemente
angepasst werden kann
immer ein konstanter Anteil der Tabelle
mit Elementen belegt ist
die Kosten für n Einfüge- oder
Entferne–Operationen O(n) sind.
Organisation der Tabelle: Hashtabelle, Heap, Stack, etc.
Belegungsfaktor T: Anteil der Tabellenplätze von T, die belegt sind.
Implementation Einfügen
class dynamic table {
int [] table;
int size; // Größe der Tabelle
int num; // Anz. der Elemente
dynamicTable() { // Initialisierung der leeren Tabelle
table = new int [1];
size = 1;
num = 0;
}
Implemenation Einfügen
insert ( int x) {
if (num == size ) {
new Table = new int [2*size];
for (i = 0; i < size; i++)
füge table[i] in newTable ein;
table = newTable;
size = 2*size;
}
füge x in table ein;
num = num + 1;
}
Kosten von n Einfüge-Operationen in eine anfangs leere Tabelle
ti = Kosten der i-ten Einfüge-Operation
Worst case:
ti = 1, falls die Tabelle vor der Operation i nicht voll ist
ti = (i – 1) + 1, falls die Tabelle vor der Operation i voll ist.
Also verursachen n Einfüge-Operationen höchstens
Gesamtkosten von
Amortisierter Worst-Case:
Aggregat -, Bankkonto -, Potential-Methode
Potential-Methode
T Tabelle mit
k = T.num Elemente und
s = T.size Größe
Potentialfunktion
(T) = 2 k – s
Potential-Methode
Eigenschaften
0 = (T0) = ( leere Tabelle ) = -1
Für alle i 1 : i = (Ti) 0
Weil n - 0 0 gilt, ist
Unmittelbar vor einer Tabellenexpansion ist k = s,
also (T) = k = s.
Unmittelbar nach einer Tabellenexpansion ist k = s/2,
also (T) = 2k – s = 0.
Berechnung der amortisierten Kosten ai der i-ten Einfüge-Operation
ki = # Elemente in T nach der i-ten Operation
si = Tabellengröße von T nach der i-ten Operation
Fall 1: i-te Operation löst keine Expansion aus
ki = ki-1 + 1, si = si-1
ai = 1 + (2ki - si) - (2ki-1 – si-1)
= 1 + 2(ki - ki-1)
= 3
Fall 2: i-te Operation löst Expansion aus
ki = ki-1 + 1, si = 2si-1
ai = ki-1 + 1 + (2ki - si) - (2ki-1 – si-1)
= 3
Einfügen und Entfernen von Elementen
Jetzt: Kontrahiere Tabelle, wenn Belegung zu gering!
Zíele:
(1) Belegungsfaktor bleibt durch eine Konstante
nach unten beschränkt
(2) amortisierte Kosten einer einzelnen Einfüge- oder Entferne- Operation sind konstant.
1. Versuch
Expansion: wie vorher
Kontraktion: Halbiere Tabellengröße, sobald Tabelle
weniger als ½ voll ist!
„Schlechte“ Folge von Einfüge- und Entfernenoperationen
D, D: Kontraktion n/2 + 1 I, I : Expansion n/2 + 1 D, D: Kontraktion n/2 + 1 I: Expansion 3 n/2 n/2 mal Einfügen
(Tabelle voll) Kosten Gesamtkosten der Operationsfolge:
In/2, I,D,D,I,I,D,D,... der Länge n sind
Comments