Lineares Sondieren Algorithm en und D atenstrukturen 9. V ... · PDF fileAndere Folgen sind m...

Algo rithm en und D atenstruk turen

9. V o rlesung

Martin D ie tz fe lb in ge r

6. J u n i 2005

F G K T u E A , T U Ilm e n a u A u D – 06.06.2005

Lineares SondierenT :

(4)Januar

(5)Februar

(8)Maerz

April (8)

(12)Mai

(4)Juni

(2)Juli

(10)August

(6)September

(10)Oktober

(12)November

Dezember (3)

10:

0:1:2:3:4:5:6:7:8:9:

11:12:

FG KTuEA, TU Ilmenau AuD – 06.06.2005 1

Prop osition

Bei linearem S ond ieren in einer Tabelle d er Groß e m mit

S c h lusselmenge S = {x1, . . . ,xn} gilt, mit α = n/m:

Die erw artete (nac h (UF∗)) Anzah l von S c h lusselvergleic h en

bei erfolgloser Suche nach y /∈ S ist

≈1

2

(

1 +1

(1 − α)2

)

.

Die erw artete (nac h (UF∗)) mittlere (uber x1, . . . ,xn) Anzah l

von S c h lusselvergleic h en bei erfolgreicher Suche nach y ∈ S

ist

≈1

2

(

1 +1

1 − α

)

.

N ur von α, nicht von n, m abhangig!


erfolgloserfolgreich

Lineares SondierenAnzahl Vergleiche

0

4080

120160200

0.4 0.5 0.6 0.7 0.8 0.9 1α


Verdoppelungsstrategie bei linearem Sondieren:

V erdop p le die Tabelle, sobald der Auslastungsfaktor α = n /m

einen W ert von α0 ubersteigt — z.B. α0 = 0,75 oder α0 = 0,8.

E mpfehlung: Kombiniere lineares Sondieren mit einer guten

universellen H ashklasse.

Nicht auf die Z ufalligkeit von S vertrauen!

!!!

L ineares Sondieren p asst p erfekt zu C ache-Architekturen und

ist in der Praxis sehr schnell.


Verallgemeinerung:”open addressing“

”G eschlossenes H ashing“ (man bleibt in T)

Fur jeden Schlussel x ∈ U gibt es eine

Sondierungsfolge h(x, 0), h(x, 1), h(x, 2), . . .

in [m].

Beim Einfugen von x und Suchen nach x w erden die Zellen

von T in dieser Reihenfolge untersucht . . .

. . . bis eine leere Zelle oder der Eintrag x gefunden w ird.

(Analog empty(m), in sert(x) und looku p(x) bei linearem

Sondieren.)


Gunstig:

(∗) h(x, 0), h(x, 1), h(x, 2), . . . , h(x, m−1) erreicht jede Zelle,

d.h.: (h(x, 0), h(x, 1), h(x, 2), . . . , h(x, m − 1))

ist eine Permutation von [m].

Wenn (∗) gilt und mindestens eine Zelle in T leer ist, dann

endet jede erfolglose Suche in einer leeren Zelle.

Bei linearem Sondieren: h(x, k) = (h(x) + k) m o d m.

Andere Folgen sind moglich, zum Beispiel . . .


Quadratisches Sondieren

h : U → [m] gewohnliche Hashfunktion.

h(x, 0) = h(x)

h(x, 1) = (h(x) + 1) mod m

h(x, 2) = (h(x) − 1) mod m

h(x, 3) = (h(x) + 4) mod m

h(x, 4) = (h(x) − 4) mod m

h(x, 5) = (h(x) + 9) mod m

h(x, 6) = (h(x) − 9) mod m...

h(x, k) =(

h(x) +

⌈

k

2

⌉2

· (−1)k+1

)

mod m.


Ubung: Berechne die Folgenglieder inkrementell ohne

Multiplikationen.

. . . ja sogar ohne Divisionen (”. . . mod m“ ).

Idee 1:

n2 = 1 + 3 + 5 + 7 + . . . + (2n − 1).

Man erreicht die Quadratzahlen, indem man Inkremente

1, 3, 5, . . . addiert.

Man erreicht die negativen Quadratzahlen modulo m, indem

man (modulo m) Inkremente m− 1, m− 3, m− 5, . . . addiert.

Idee 2: Wenn 0 ≤ a < m,0 ≤ b ≤ m, dann ist a + b mod m

einer der beiden Werte a + b und (a + b) − m.


Losung:

(∗ Bei”pause“ wird die Abarbeitung der Prozedur unterbro-

chen, der Zustand aufbewahrt; beim nachsten Aufruf wird die

Verarbeitung an der Unterbrechungsstelle fortgefuhrt. ∗)

Quadratic Probe Sequence(x)

(1) h ← h(x); output h; pause;

(2) incr ← 1; n incr ← m− 1;

(3) f ← h; g ← h;

(4) for j from 1 to (m− 1)/2 do

(7) f ← (f + incr); ff← f−m; if ff ≥ 0 then f← ff;

(6) output f; pause;

(7) g ← (g + n incr); gg← g−m; if gg ≥ 0 then g← gg;

(8) output g; pause;

(9) incr ← (incr + 2); n incr ← (n incr− 2);


Fakt

Ist m Primzahl, m = 4j + 3 fur ein j ∈ N,

dann ist {h(x, k) | 0 ≤ k < m} = [m], d.h. (∗) gilt.

(Beweis: Elementare Zahlentheorie)

Beispiel : m = 19, h(x) = 0, liefert Sondierungsfolge

0, 1, 18, 4, 15, 9, 10, 16, 3, 6, 13, 17, 2, 11, 8, 7, 12, 5, 14.

M itteilung:

Quadratisches Sondieren verhalt sich der Erfahrung nach

sehr gut. (h gut verteilend, Auslastungsfaktor ≤ 0,9.)


Doppel-Hashing

Benutze zwei (unabhangig berechnete) Hashfunktionen

h1 : U → [m]

h2 : U → [m− 1]

und setze, fur k = 0, 1, 2, . . .:

h(x, k) := (h1(x) + k · (1 + h2(x))) mod m.

Ubung: Berechne die Folgenglieder inkrementell ohne Multi-

plikationen und Divisionen (”. . . mod m“).


Losung:

(∗ Bei”pause“ wird die Abarbeitung der Prozedur unter-

brochen, Zustand aufbewahrt, bis zum nachsten Aufruf; die

Verarbeitung wird an der Unterbrechungsstelle fortgefuhrt. ∗)

Double Hashing Sequence(x)

(1) h ← h1(x); output h; pause;

(2) incr ← 1 + h2(x);

(3) for j from 1 to m− 1 do

(4) h← h + incr; hh← h−m; if hh ≥ 0 then h← hh;

(5) output h; pause;


Proposition

Wenn m Primzahl ist, dann gilt fur Doppel-Hashing:

(∗) {h(x, k) | 0 ≤ k < m} = [m].

Beweis: Sei z = 1 + h2(x). Dann: 1 ≤ z ≤ m− 1.

Wenn h(x, k) = h(x, l), dann ist

(h1(x) + k · z) mod m = (h1(x) + l · z) mod m,

also (l − k) · z ≡ 0 (mod m), d.h. m teilt (l − k) · z.

Da m Primzahl ist und 1 ≤ z < m, teilt m die Zahl l − k,

also ist k = l, weil 0 ≤ k, l < m. �


Kann beweisen: Wenn h1(x), h2(x), x ∈ S, rein zufallig sind,

verhalt sich Doppel-Hashing sehr gut, namlich im wesentli-

chen wie”Uniformes Sondieren“.

”Uniformes Sondieren“/

”Ideales Hashing“

Dies ist keine Methode,

sondern eine W ahrscheinlichkeitsannahme:

(h(x, 0), h(x, 1), . . . , h(x, m− 1)) ist

eine rein zufallige Permutation von [m].

(Erinnerung: Es gibt m! verschiedene Permutationen von [m].)


Effekt: x1, . . . , xn seien gespeichert; y kommt neu hinzu.

Ganz egal was die Hashwerte von x1, . . . , xn und was

h(y, 0), . . . , h(y, k − 1) sind:

h(y, k) nimmt jeden Wert

i ∈ {0, . . . , m− 1} − {h(y, 0), . . . , h(y, k − 1)}

mit derselben Wahrscheinlichkeit 1/(m− k) an.


n: Anzahl der Schlussel in T[0 . . m− 1]; α = nm.

T ′

n,m := Zahl der Schlusselvergleiche bei erfolgloser Suche.

C ′

n,m := E(T ′

n,m).

Tn,m := Zahl der Schlusselvergleiche bei erfolgreicher Suche,

gemittelt uber x1, . . . , xn.

Cn,m := E(Tn,m).

Satz

Unter der Annahme”Uniformes Hashing“ gilt:

(i) C ′

n,m = m+1

m+1−n = 1

1− nm+1

.

Dies ist < 1

1−n/ m = 1

1−α.

Wenn α fest und m→∞, dann gilt C ′

n,m→1

1−α.


Beweis: Bei der erfolglosen Suche gibt es 2 Falle:

1. F a ll : T[h(y, 0)] ist leer.

Wahrscheinlichkeit: m−nm Kosten: 1.

2. F a ll : T[h(y, 0)] ist nicht leer.

Wahrscheinlichkeit: nm Kosten: 1 + C′

m−1,n−1.

(Suche in m− 1 Platzen, von denen n− 1 besetzt sind.)

R ekursionsformel, fur 0 ≤ n < m:

C ′

m,n =

{

1 , falls n = 0m−n

m + nm · (1 + C ′

m−1,n−1) , falls n ≥ 1.


C ′

m,0 = 1 ;

C ′

m,1 =m− 1

m+

1

m· (1 + 1) =

m + 1

m;

C ′

m,2 =m− 2

m+

2

m· (1 +

m

m− 1) = 1 +

2

m− 1=

m + 1

m− 1;

C ′

m,3 =m− 3

m+

3

m· (1 +

m

m− 2) = 1 +

3

m− 2=

m + 1

m− 2;

und so weiter. Ergibt:

C′

m,n=

m + 1

m + 1 − n.

Formaler Beweis d u rc h vollstan d ige In d u ktion . �

FG K T u E A , T U Ilmen au A u D – 06.06.2005 18

Satz

Unter der Annahme”Uniformes H ashing“ gilt b ei α = n/m:

(i) C ′

n,m = m+1

m+1−n = 1

1− nm+1

.

Dies ist < 1

1−n/ m = 1

1−α.

W enn α fest und m → ∞, dann gilt C ′

n,m →1

1−α.

(ii) Fur

Tn,m = m ittlere (ub er S) Anzahl getesteter Tab ellenp latze

b ei erfolgreicher Suche:

Cn,m = E(Tn,m) < 1

α · ln ( 1

1−α).


Beweis: Suchaufwand fur xi = Einfugeaufwand fur xi.

Mittelung uber C ′m,0,C

′m,1, . . . ,C

′m,n−1:

Cn,m =1

n·

∑

1≤i≤n

m + 1

m + 1 − (i − 1)

=m + 1

n·

(

1

m + 1+

1

m+ · · · +

1

m + 1 − (n − 1)

)

=m + 1

n· (Hm+1 − Hm+1−n)

mit Hk = 1 + 1

2+ · · ·+ 1

k. — L eicht zu sehen (Untersumme!):

Hm+1 − Hm+1−n ≤∫ m+1

m+1−nd tt =

ln(m + 1) − ln(m + 1 − n) = ln(

m+1

m+1−n

)

.


Also:

Cn,m ≤m + 1

n· ln

(

1

1 −n

m+1

)

<m

n· ln

(

1

1 −nm

)

.

Fur α = n/m, α fest, n → ∞, ist Cn,m ≈1

α ln( 1

1−α).

�


erfolgloserfolgreich

Uniformes HashingAnzahl Vergleiche

0

48

121620

0.4 0.5 0.6 0.7 0.8 0.9 1α


Loschungen? Problem: Z.B. Quadratisches Sondieren

Suchfolge”Dezember“ mit h(Dezember) = 7: 7, 8, 6, 11.

T : 0:1:2:3:4:5:6:7:8:9:

10:11:12:

Januar (8)Februar (9)

Maerz (12)

April (12)

Mai (3)

Juni (8)Juli (6)

August (1)

September (10)

Oktober (1)

November (3)

Dezember (7)

Losche”J uli“!


Loschungen? Problem: Z.B. Quadratisches Sondieren

Suchfolge”Dezember“ mit h(Dezember) = 7: 7, 8, 6, 11.

T :

!!!

0:1:2:3:4:5:6:7:8:9:

10:11:12:

Januar (8)Februar (9)

Maerz (12)

April (12)

Mai (3)

Juni (8)

August (1)

September (10)

(1)

November (3)

Dezember (7)

Oktober

Losche”Juli“!

”Dezember“ wird nicht mehr gefunden.


Ausw eg: Zelle hat Statusvariable status (voll, leer, gelosc h t).

Loschen: Zelle nicht auf leer, sondern auf gelosc h t setzen.

Suchen: Immer bis zur ersten leeren Zelle gehen.

Zellen, die gelosc h t sind, durfen mit einem neuen Schlussel

uberschrieben werden.

Ub erlauf tritt spatestens ein, wenn die letzte leere Zelle

beschrieben werden wurde.

Sinnvoller: Uberlauf tritt ein, wenn die Anzahl der vollen

und gelosc h ten Zellen zusammen eine feste Schranke bound

uberschreitet.

Z.B. m− 1 oder α0m, α0 passend zum Sondierungsverfahren.


empty(m):

Lege leeres Array T[0 . . m − 1] an.

(∗ Mogliche Eintrage:

(x, r, voll) oder (−,−, leer) oder (?, ?, geloscht). ∗)

Initialisiere alle Zellen T[i] mit (−,−, leer).

Initialisiere load mit 0. (Zahlt nicht-leere Zellen.)

Initialisiere bound (maximal m − 1).


looku p(x):

Finde erstes j in der Indexfolge h(x, 0), h(x, 1), h(x, 2), . . .

mit T[j].status = leer

oder (T[j].status = voll und T[j].key = x);

Falls T[j].status = leer : return n ot fou n d ;

Sonst: return T[j].data.


delete(x):




Falls T[j].status = leer : tue nichts;

(∗ Warnung: not found ∗)

Sonst: T[j].status← geloscht;


insert(x, r):




Merke dabei das erste l in dieser Folge,

das T[l].status ∈ {geloscht, leer} erfullt;

F all 1: T[j].status = voll : T[j].data← r; (∗Update ∗)

F all 2: T[l].status = geloscht: T[l]← (x, r, voll);

(∗ uberschreibe geloschtes Feld ∗)

F all 3: T[l].status = leer : (∗ j = l, neue Zelle ∗)

if load + 1 > bound then”Uberlaufbehandlung“

else load← load + 1; T[j]← (x, r, voll);


Uberlaufbehandlung, V erdopplung:

Sinnvoll: Uberlauf tritt ein, wenn der Anteil der vollen und

geloschten Zellen zusammen eine Schranke α0m uberschreitet.

(α0 passend zum Sondierungsverfahren festlegen.)

Zahle die vollen Zellen: Anzahl v.

Falls v + 1 > α1m fur (z.B.) α1 = 0.8α0, verdopple Tabel-

lengroß e.

Trage Schlussel neu in die groß ere Tabelle ein.

Sonst: Trage alle Schlussel neu in die alte Tabelle T ein.


Trick fur neues Eintragen:

(Ohne zusatzlichen Platz. N ur fur Spezialisten!)

1) Fur i = 0, 1, . . . , m− 1 tue folgendes:

Wenn T[i].status = voll, setze T[i].status ← a lt.

Wenn T[i].status = geloscht, setze T[i].status ← leer.


2) Fur i = 0, 1, . . . , m− 1 tue folgendes:

Wenn T[i].status = alt,

dann setze (x, r)← (T[i].key, T[i].data),

setze T[i].status = leer,

und fuge (x, r) ein – mit folgender Besonderheit:

Eine mit alt markierte Zelle wird wie leer behandelt,

der dort enthaltene Eintrag (x′, r′) wird durch (x, r, voll) ver-

drangt;

(x′, r′)wird sofort anschließend mit demselben V erfahren ein-

gefugt.

Dies setzt sich fort, bis eine Einfugung in eine mit leer mar-

kierte Zelle erfolgt.

Dann fahrt man mit der Abarbeitung der i-Schleife fort.


Sortieren

G egeben:

Universum U mit totaler Ordnung <.

Sortierproblem, abstrakt: Siehe Vorlesung 1.

G egeben:

Universum U mit totaler Ordnung <.

Elemente: (Sortier-)Schlussel.

Gegeben: Folge (a1, . . . , an) in U .

Aufgabe: Arrangiere so um zu (b1, . . . , bn), dass b1 ≤ · · · ≤ bn.

O der: Berechne eine Permutation π von {1, . . . , n}, die

(a1, . . . , an) sortiert, d.h. mit bi = aπ(i), 1 ≤ i ≤ n, gilt

b1 ≤ · · · bn.


Sortiermethoden, schon gesehen:

Straight Insertion Sort, B ubble Sort, Shell Sort (GdP1)


Sortieren

Viele Varianten:

• Eintrage enthalten neben Schlussel weitere Daten (data);

Eintrag/Item: mit Sortierschlussel (key) versehenes Objekt.

• Eintrage sind nur Zeiger/Referenzen auf Datensatze (mit

Schlusseln)

Bei Vorkommen gleicher Sortierschlussel:

Sortierverfahren heißt stabil, wenn Objekte mit identischen

Schlusseln in der Ausgabe in derselben Reihenfolge stehen wie

in der Eingabe.


Sortieren

x

π(2) π(5) π(8) π(1)

4

RA

5

OR

9

HM

4

LG IT

8

a1 a2 a3 an

1

SO

1

RT IE

1

1

SO IE

11

RT

4

RA

4

LG

5

OR

9

HM US

10

IT

8

Inform:

Item:

Schlüssel "key"

"data"dat

"Stabilität"

US

10


Array-Sortieren

Eingabe:

Array A[1 . . n] mit Eintragen a1, . . . , an ∈ U .

Aufgabe: Permutiere die Eintrage von A[1 . . n] so, dass

schließlich

A[1] ≤ A[2] ≤ A[3] ≤ . . . ≤ A[n].

Alternative: Berechne eine Permutation π von {1, . . . , n},

die A[1 . . n] sortiert.


Array-Sortieren

Bemerkung: Permutationssortieren und gewohnliches Sortie-

ren sind praktisch dasselbe Problem.

Wenn man das eine gelost hat, kann man das andere in

zusatzlicher Zeit O(n) losen.

1) Gegeben sei eine Permutation π von {1, . . . , n},

die A[1 . . n] sortiert.

Transportiere A[i] nach B[π(i)], i = 1, . . . , n.

Dann kopiere B[i] nach A[i], i = 1, . . . , n.


Array-Sortieren

Bemerkung: Permutationssortieren und gewohnliches Sortie-

ren sind praktisch dasselbe Problem.

Wenn man das eine losen kann, kann man das andere in

zusatzlicher Zeit O(n) losen.

2) Gegeben sei ein gewohnliches Sortierverfahren S.

Eingabe: A[1 . . n].

Setze B[i] ← (B[i],i), fur 1 ≤ i ≤ n.

Zweite Komponente: index.

Sortiere B[1 . . n] mittels S, Sortierschlussel: erste

Komponente.


Array-Sortieren

Beispiel :

A: 4 6 2 3 9 12 6 4 0

B: 4 6 2 3 9 12 6 4 0

index: 1 2 3 4 5 6 7 8 9

B, sortiert: 0 2 3 4 4 6 6 9 12

index: 9 3 4 1 8 2 7 5 6

π: 4 6 2 3 8 9 7 5 1

π(B[i].index)← i, fur 1 ≤ i ≤ n.

Verifiziere Korrektheit!


Listen-Sortieren

Eingabe: Liste L mit Eintragen a1, . . . , an ∈ U .

Aufgabe: Permutiere die Listenelemente in L so, dass schließ-

lich die Eintrage in L aufsteigend sortiert sind.

∗∗ ∗ ∗∗... ...

... ... ...7 3 1 6

1 3 6 7

β:α: γ: δ:

α:γ: δ:...

...

β:...

Nur Zeiger (∗) andern sich. Vorteil: Kein Datentransport.

Kosten: Platz fur Zeiger.


Maß zahlen fur Sortieralgorithmen: In Abhangigkeit von n

fragen wir nach:

1. Laufzeit (in O-Notation);

2. Anzahl der Vergleiche

A[i] < A[j] bzw. A[i] ≤ A[j]

(”wesentliche V ergleiche“);

3. Anzahl der Datenverschiebungen oder Kopiervorgange

(wichtig bei sehr umfangreichen Objekten);

4. der neb en A (und pi) benotigte Speicherplatz;


wenn dieser nur O(1), also von n unabhangig, ist:

Algorithmus arbeitet”in situ“.


Mergesort - Sortieren durch Mischen

(engl. merge = vermengen, reißverschlussartig zusam-

menfugen)

Algorithmenparadigma oder -schema:

”divide-and-conquer“ (D -A-C )

(”teile und herrsche“)


Vorgehen eines D-A-C-Algorithmus A fur Berechnungsproblem

P auf Instanz x ∈ I :

0. Trivialitatstest: Wenn P fur x einfach direkt zu losen ist,

tue dies.

Sonst:

1. Teile: Zerteile x in (zwei oder mehr) Stucke x′1, x

′2, . . . , x

′b.

Wesentlich fur Korrektheit/Terminierung: Jedes der Stucke ist

”kleiner“ als x.

2. R ekursion: Lose P fur x′1, x

′2, . . . , x

′b, durch rekursive

Verwendung von A.

3. Kombiniere: Baue aus den Teillosungen fur die Stucke

x′1, x

′2, . . . , x

′b eine Losung fur x auf.


Mergesort ist konkreter D-A-C-Algorithmus zum Sortieren

eines Arrays A[1 . . n]:

0. Trivialitatstest: Wenn n ≤ 1, ist nichts zu tun.

1. Teile: Zerlege A in zwei gleichgroße Teilarrays A1 und A2.

2. Rekursion: Sortiere A1 und A2 durch rekursive Aufrufe von

Mergesort.

3. Kombiniere: Konstruiere aus den sortierten Teilarrays aus

2. ein sortiertes Array, das alle Eintrage enthalt.

Technisch gunstiger:

Mergesort sortiert ein Teilarray A[a . . b].


Gegeben sei eine Prozedur merge(a, m, b), 1 ≤ a ≤ m < b ≤

n

d ie folge n d e s tu t:

V ora u sse tz u n g: A[a ..m] u n d A[m + 1 . .b] sin d sortie rt.

Re su lta t: A[a ..b] ist sortie rt.

A n sa tz : Qu a sip a ra lle le r D u rc h la u f d u rc h d ie T e ila rra ys.

D e ta ils: Siehe V o rlesu ng G dP 1.

A u fw a n d : ≤ b − a S c h lu sse lve rgle ic h e , Ze it Θ (b − a + 1).

F G K T u E A , T U Ilm e n a u A u D – 06.06.2005 47

Algorithm us m ergeSort(a, b)

(1) if b− a > 1 then

(2) m ← (b− a) div 2;

(3) m ergeSort(a, m);

(4) m ergeSort(m + 1, b);

(5) m erge(a, m, b).

Terminierung, Korrektheit: Induktion ub er k = b− a + 1:

Klar falls a = b.

Falls a < b: Teilarrays hab en L angen d(b − a + 1)/2e und

b(b− a + 1)/2c – b eides < (b− a + 1).

N ach I.V. liefern die rekursiven Aufrufe in (3) und (4) das

korrekte Resultat.

N ach Annahme ub er m erge sortiert dann Zeile (5) korrekt.


Zeitanalyse:

1) Die Kosten (Rechenzeit) sind proportional zur Anzahl der

durchgefuhrten Vergleiche.

2) W ir fi nden eine obere Schranke CMS(k) fur die Anzahl der

Vergleiche, die mergeSort(a, b) ausfuhrt, auf k = b − a + 1

Schlusseln.

R ek ursionsungleichung:

CMS(1) = 0;

CMS(k) ≤ k − 1︸︷︷︸

m erge

+CMS(bk/2c) + CMS(dk/2e),

fur k ≥ 2.

Resultierende Schranken:


k 1 2 3 4 5 6 7 8 9 10 11

CMS(k) ≤ 0 1 3 5 8 11 14 17 21 25 29

Diff .: dlog ke − 1 2 2 3 3 3 3 4 4 4

Kann zeigen: CMS(k) ≤∑

1≤i≤kdlog ie.

Exakte B erechnung der Summe ist moglich. Liefert:

CMS(k) ≤ dlog ke · k − 2dlo g ke + 1.


”E ntw icklungsmethode“ : Losung fur den Fall k = 2`.

CMS(k)

= CMS(2`)

≤ 2` + 2 · CMS(2`−1)

≤ 2` + 2 · 2`−1 + 4 · CMS(2`−2)

≤ 3 · 2` + 23 · CMS(2`−3)

≤ . . .

≤ j · 2` + 2j · CMS(2`−j)

≤ . . .

≤ ` · 2` + 2` · CMS(2`−`)

= k log k.


Alternative: Direkte Analyse, Induktionsbeweis.

TMS(k) seien die Kosten eines Aufrufs mergeSort(a, b), auf

k = b− a + 1 Schlusseln, im schlechtesten Fall.

Es gibt Konstante c > 0 und d > 0 mit

TMS(1) ≤ c;

TMS(k) ≤ d · k + TMS(bk/2c) + TMS(dk/2e), fur k ≥ 2.

Trick: Losung mit P arametern A, B raten; der Induktionsbe-

weis liefert die richtigen P arameter.


Behauptung: TMS(k) ≤ A · k + Bk log k, fur alle k ≥ 1.

Beweis: Induktion uber k.

Interessant: Die genauen Werte A und B werden erst durch

die Rechnung ermittelt.

k = 1: TMS(1) ≤ c ≤ A · k, falls A ≥ c.

k ≥ 2:


TMS(k) ≤ d · k + TMS(bk/2c) + TMS(dk/2e)

I.V.

≤ d · k + Abk/2c+ Bbk/2c logbk/2c

+ Adk/2e+ Bdk/2e logdk/2e

≤ d · k + Ak + Bk logdk/2e

≤ d · k + Ak + Bk(log k + 0.6− 1)

denn: k ≥ 3⇒ log(k + 1) ≤ log k + 0.6. Also:

TMS(k) ≤ (d + A− 0.4B)k + Bk log k.

Wenn wir A = c und B = d/0.4 wahlen, funktioniert der

Induktionsbeweis.


Analog zeigt man:

TMS(k) ≥ A′k+B′k log k, fur gewisse Konstanten A′, B′ > 0.


Satz

Die Anwendung des Mergesort-Algorithmus, d. h. der Auf-

ruf mergeSort(1, n), auf einem Array von n Objekten

benotigt hochstens n log n Vergleiche und hat Kosten (Lauf-

zeit) O(n log n).

M ergesort ist stabil (wenn merge entsprechend eingestellt

wird).

M ergesort benotigt zusatzlichen Speicherplatz,

ist also nicht”in situ“ ,

(n/2 Arrayeintrage, wenn man weiter keine Vorkehrungen

trifft).


Variante 1: (Standardmaß ig angewandt)

Ziel: Uberproportional hohen Zeitaufwand fur rekursive Aufru-

fe bei kleinen Teilarrays vermeiden.

Strategie: In mergeSort kleine Teilarrays

(b−a ≤ ∆, ∆ ≥ 1 konstant) durch (z. B.) Straight-Insertion-

Sort sortieren.

Das optimale ∆ auf einer konkreten Maschine kann nur ein

Experiment liefern.


Variante 2: Sortieren von (linearen) Listen.

Wenn die Liste L nur ein Element enthalt, ist nichts zu tun.

Andernfalls wird die Liste in 2 Teillisten L1, L2 der halben

Lange zerteilt.

(Durchlaufe L, hange die Eintrage abwechselnd an L1 und L2

an.

Kosten: Θ(Lange von L).)

Auf L1 und L2 wird der Algorithmus rekursiv angewendet.

Dann werden die beiden nun sortierten Listen gemischt.

(Vgl. Ubung zu dunn besetzten Matrizen.)

Laufzeitanalyse: Identisch zum Obigen.


Variante 3: Iteratives Mergesort,”b ottom-up“

Idee: Arbeite in Runden i = 1, 2, 3, . . . , dlog ne.

Vor Runde i: Teilarrays A[(l− 1)2i + 1 . . . l2i] sind aufsteigend

sortiert.

(Eventuell ist das am weitesten rechts stehende Teilarray un-

vollstandig.)

In Runde i fuhre

merge((l − 2)2i + 1, (l − 1)2i, l2i) aus,

fur l = 2, 4, . . . , 2bn/2i+1c.

(Mogliche Sonderrolle fur unvollstandige Teilarrays ganz

rechts.)


Beisp iel :

7 2 9 6 3 1 6 10 2 17 12 6 2 7 4

6 10 2 17 2 7 42 7 6 9 1 3 6 12

6 10 2 22 9 1 36 7 6 12 17 4 7

10 29766321 2 4 6 7 12 17

A:

C:

A:

C:

A:

Runde

1

2

4

3

1 2 2 2 3 4 6 6 7 7 9 10 17126


Trick, spart Kopierarbeit:

Benutze 2 Arrays, die in jeder Runde ihre Rolle wechseln.

Zeitverhalten von iterativem Mergesort:

wie bei rekursivem Mergesort.

Bei dieser Variante bietet sich noch eine alternative, einfache

Zeitanalyse an:

J ede Runde kostet offenbar Zeit Θ(n), und es gibt dlog ne

Runden: also ist die Gesamtzeit

Θ(ndlog ne) = Θ(n log n).


Variante 4: Mehrweg-Mergesort

Besonders in Kombination mit dem iterativen Verfahren inter-

essant ist die Moglichkeit, in einer merge-Runde nicht nur ein

Array, sondern 3, 4, oder mehr Teilarrays zusammenzumischen.

Beispiel :

1 7 9 13 2 5 7 9 3 6 6 10 2 4 11 12

Die nächsten gewählten Elemente:

C:

A:

aus 4 (Rest−)Arrays.

1 2 2 3 4 5 6 6 7 7

"9" aus 1.Teilarray,

4−way merge: wähle kleinstes Element

"9" aus 2. Teilarray, 10, 11, etc.


Bei Cache-Architekturen oder Sortieren von Daten auf H inter-

grundspeichern (Platten) kann diese Variante Laufzeitvorteile

bringen, da die Anzahl der Cache- bzw. Seitenfehler (cache

m isses bzw. page faults) verringert wird.

Fruher: Sortieren von Daten auf Bandern.

Algorithmus der Wahl: Mergesort.


Date post:	07-Feb-2018
Category:	Documents
Upload:	lytu
View:	215 times
Download:	0 times

Lineares Sondieren Algorithm en und D atenstrukturen 9. V ... · PDF fileAndere Folgen sind m...

Documents