Amortisierte Analyse Prof. Dr. S. Albers
Prof. Dr. Th. Ottmann
2. Versuch
Expansion: Verdoppele die Tabellengröße, wenn in die volle Tabelle eingefügt wird.
Kontraktion: Sobald der Belegungsfaktor unter ¼ sinkt ,
halbiere die Tabellengröße.
Folgerung:
Die Tabelle ist stets wenigstens zu ¼ voll, d.h.
¼ (T) 1
Kosten einer Folge von Einfüge- und
Entferne-Operationen?
Analyse Einfügen und Enfernen
k = T.num, s = T.size, = k/s
Potentialfunktion
Analyse Einfügen und Entfernen
Unmittelbar nach einer Expansion oder Kontraktion
der Tabelle:
s = 2k, also (T) = 0
Einfügen
i-te Operation: ki = ki-1 + 1
Fall 1: i-1 ½
Fall 2: i-1 < ½
Fall 2.1: i < ½
Fall 2.2: i ½
Einfügen
Potentialfunktion Fall 2.1: i-1 < ½, i < ½ (keine Expansion)
Einfügen
Fall 2.2: i-1 < ½, i ½ (keine Expansion) Potentialfunktion
Entfernen
ki = ki-1 - 1
Fall 1: i-1 < ½
Fall1.1: Entfernen verursacht keine Kontraktion
si = si-1 Potentialfunktion
Entfernen
Fall 1.2: i-1 < ½ Entfernen verursacht Kontraktion
2si = si –1 ki-1 = si-1/4 ki = ki-1 - 1
Fall 1: i-1 < ½ Potentialfunktion
Entfernen
Fall 2: i-1 ½ keine Kontraktion
si = si –1 ki = ki-1 - 1
Fall2.1: i-1 ½
Potentialfunktion
Entfernen
Fall 2: i-1 ½ keine Kontraktion
si = si –1 ki = ki-1 - 1
Fall2.2: i < ½
Potentialfunktion
Comments