Upload
vuongduong
View
214
Download
0
Embed Size (px)
Citation preview
KIT � Institut für Theoretische Informatik 2
Formaler
Gegeben: Elementfolge s = 〈e1, . . . ,en〉Gesucht: s ′ = 〈e ′1, . . . ,e ′n〉 mit
I s ′ ist Permutation von s
I e ′1 ≤ ·· · ≤ e ′n für eine Totalordnung `≤'
KIT � Institut für Theoretische Informatik 3
Anwendungsbeispiele
I Allgemein: VorverarbeitungI Suche: Telefonbuch ↔ unsortierte ListeI Gruppieren (Alternative Hashing?)
KIT � Institut für Theoretische Informatik 4
Beispiele aus Kurs/Buch
I Aufbau von SuchbäumenI Kruskals MST-AlgorithmusI RucksackproblemI Scheduling, die schwersten Probleme zuerstI Sekundärspeicheralgorithmen, z. B. Datenbank-Join
Viele verwandte Probleme. Zum Beispiel Transposition dünnerMatrizen, invertierten Index aufbauen, Konversion zwischenGraphrepräsentationen.
KIT � Institut für Theoretische Informatik 5
Überblick
I Einfache Algorithmen / kleine Datenmengen
I Mergesort � ein erster e�zienter Algorithmus
I Eine passende untere Schranke
I Quicksort
I das Auswahlproblem
I ganzzahlige Schlüssel � jenseits der unteren Schranke
KIT � Institut für Theoretische Informatik 6
Einfache Sortieralgorithmen
Procedure insertionSort(a : Array [1..n] of Element)for i := 2 to n do
invariant a[1]≤ ·· · ≤ a[i −1]move a[i ] to the right place
Beispiel:〈4〉,〈7,1,1〉 〈4,7〉,〈1,1〉 〈1,4,7〉,〈1〉 〈1,1,4,7〉,〈〉
KIT � Institut für Theoretische Informatik 7
Sentinels am Beispiel Sortieren durch Einfügen
Procedure insertionSort(a : Array [1..n] of Element)for i := 2 to n do
invariant a[1]≤ ·· · ≤ a[i −1]// move a[i ] to the right placee:= a[i ]if e < a[1] then // new minimum
for j := i downto 2 do a[j ]:= a[j−1]a[1]:= e
else // use a[1] as a sentinelfor (j := i ; a[j−1] > e; j−− ) a[j ]:= a[j−1]a[j ]:= e
KIT � Institut für Theoretische Informatik 8
Analyse
Die i-te Iteration braucht Zeit Θ(i).
n
∑i=2
i =n(n+1)
2−1 = Θ
(n2)
Die i-te Iteration braucht Zeit O(1) z. B. (beinahe) sortiert.
n
∑i=2
O(1) ∈ O(n)
KIT � Institut für Theoretische Informatik 9
Sortieren durch Mischen
Idee: Teile und Herrsche
Function mergeSort(〈e1, . . . ,en〉) : Sequence of Elementif n = 1 then return 〈e1〉 // base caseelse return merge( mergeSort(〈e1, . . . ,ebn/2c〉),
mergeSort(〈ebn/2c+1, . . . ,en〉))
Gegeben:zwei sortierte Folgen a und bBerechne:sortierte Folge der Elemente aus a und b
KIT � Institut für Theoretische Informatik 11
Mischen
Jeweils min(a,b) in die Ausgabe schieben. Zeit O(n)a b c operation
〈1,2,7〉 〈1,2,8,8〉 〈〉 move a〈2,7〉 〈1,2,8,8〉 〈1〉 move b〈2,7〉 〈2,8,8〉 〈1,1〉 move a〈7〉 〈2,8,8〉 〈1,1,2〉 move b〈7〉 〈8,8〉 〈1,1,2,2〉 move a〈〉 〈8,8〉 〈1,1,2,2,7〉 concat b
〈〉 〈〉 〈1,1,2,2,7,8,8〉
KIT � Institut für Theoretische Informatik 12
Analyse
Analyse: T (n) = O(n) +T (dn/2e) +T (bn/2c) = O(n logn).
KIT � Institut für Theoretische Informatik 13
Analyse
T (n) = Θ(n) +T (dn/2e) +T (bn/2c)
Problem: RundereiAusweg: genauer rechnen (siehe Buch)Dirty trick:Eingabe auf Zweierpotenz aufblasen(z. B. (2dlogne−n)×∞ anhängen) normales Master-Theorem anwendbarZeit Θ(n logn)
KIT � Institut für Theoretische Informatik 14
Untere Schranken
Geht es schneller als Θ(n logn)?Unmöglichkeit einer Verbesserung i.allg. schwer zu beweisen �sie erfordert eine Aussage über alle denkbaren Algorithmen. einschränkende Annahmen
KIT � Institut für Theoretische Informatik 15
Eine vergleichsbasierte untere Schranke
Vergleichsbasiertes Sortieren: Informationen über Elemente nur durchZwei-Wege-Vergleich ei ≤ ej?.Satz: Deterministische vergleichsbasierte Sortieralgorithmen brauchen
n logn−O(n)
Vergleiche im schlechtesten Fall.Beweis:Betrachte Eingaben, die Permutationen von 1..n sind.Es gibt genau n! solche Permutationen.
KIT � Institut für Theoretische Informatik 16
Baumbasierte Sortierer-Darstellung
Mindestens ein Blatt pro Permutation von e1, . . . ,enAusführungszeit entspricht Tiefe T
KIT � Institut für Theoretische Informatik 17
Beweis
Baum der Tiefe T hat höchstens 2T Blätter.⇒ 2T ≥ n!
⇔ T ≥ log n!︸︷︷︸≥( n
e )n
≥ log(ne
)n= n logn−n loge = n logn−O(n)
Einfache Approximation der Fakultät:(ne
)n≤ n!≤ nn
Beweis für linken Teil:
lnn! = ∑2≤i≤n
ln i ≥∫ n
1lnx dx =
[x(lnx−1)
]x=n
x=1≥ n(lnn−1) .
⇒ n!≥en(lnn−1) =en lnn
en=
nn
en=(ne
)n
KIT � Institut für Theoretische Informatik 18
Randomisierung, Mittlere Ausführungszeit
Satz: immer noch n logn−O(n) Vergleiche.Beweis: nicht hier.
KIT � Institut für Theoretische Informatik 19
Quicksort � erster Versuch
Idee: Teile-und-Herrsche aber verglichen mit mergesort �andersrum�.Leiste Arbeit vor rekursivem Aufruf
Function quickSort(s : Sequence of Element) : Sequence of Elementif |s| ≤ 1 then return spick “some” p ∈ sa:= 〈e ∈ s : e < p〉b:= 〈e ∈ s : e = p〉c := 〈e ∈ s : e > p〉return concatenation of quickSort(a), b, and quickSort(c)
KIT � Institut für Theoretische Informatik 20
Quicksort � Analyse im schlechtesten Fall
Annahme: Pivot ist immer Minimum (oder Max.) der Eingabe
T (n) =
{Θ(1) if n = 1,
Θ(n) +T (n−1) if n ≥ 2.
⇒T (n) = Θ(n+ (n−1) + · · ·+1) = Θ
(n2)