Übungen mit Lösung SS2018 PDF

Preview

Summary

Sommersemester...

Description

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen

6. April 2018

Präsenzaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 1

Aufgabe 1.1 (O-Notation) Beweisen oder widerlegen Sie die folgenden Aussagen: 1. 3n ∈ O(n), 2.

2 n

∈ O(1),

3. n2 ∈ O(1) 1. z.Z. ∃c ∈ R>0 ∃n0 ∈ N>0 ∀n ∈ N≥no : 3n ≤ cn Setze c := 3, setze n0 := 1, sei n ≥ n0 ∈ N>0 . Es gilt: 3n = cn 2. z.Z. ∃c ∈ R>0 ∃n0 ∈ N>0 ∀n ∈ N≥no :

2 ≤c n

Setze c := 1, setze n0 := 2, sei n ≥ n0 ∈ N. Es gilt: n2 ≤ 1 = c 3. z.Z. ∀c ∈ R>0 ∀n0 ∈ N>0 ∃n ∈ N≥no : n > c Sei c ∈ R>0 , sei n0 ∈ N>0 , setze n := ⌈c + n0 ⌉. Es gilt n > n0 und n2 = ⌈c + n0 ⌉2 > c. Aufgabe 1.2 (Vollständige Induktion) Sei n ∈ N. Beweisen Sie per Induktion: n−1

∑ (2i + 1) = n2.

i=0

Beweis per Induktion über n ∈ N Da noch nicht ganz klar ist, ob bei uns 0 ∈ N gilt, hier beide mögliche Induktionsanfänge. I.A.: Sei n = 0, es gilt: n−1

0− 1

−1

i=0

i=0

∑ (2i + 1) = ∑ (2i + 1) = ∑ (2i + 1) = 0 i=0

Sei n = 1, es gilt: n−1

1− 1

0

∑ (2i + 1) = ∑ (2i + 1) = ∑ (2i + 1) = (2 · 0 + 1) = 1 i=0

i=0

i=0

2 n 2 I.V. Sei n ∈ N gegeben und es gelte ∑n−1 i=0 (2i + 1) = n . z.Z. ∑i=0 (2i + 1) = (n + 1) I.S. n−1

n

∑ (2i + 1) = 2n + 1 + ∑ (2i + 1) i=0

i=0 2

= 2n + 1 + n = (n + 1)2

Aufgabe 1.3 (Laufzeit) Beschreiben Sie für den folgenden Algorithmus das Ergebnis der Berechnung und bestimmen Sie die Laufzeit gemäß der O -Notation. Algorithmus M AT M ULT (A, B) 1 2 3 4 5 6 7 8 9 10 11 12 13 14

integer n = length(A); integer m = length(B); integer p = length(B[0]); erzeuge Array C[n][p]; for i = 0 to n -1 do for j = 0 to p -1 do double sum = 0.0; for k = 0 to m-1 do sum = sum + (A[i][k] * B[k][j]); od C[i][j] = sum; od od return C

Gegeben sind eine (n × m) und eine (m × p) Matrix, als zweidimensionale Array A und B. Der Algorithmus bestimmt das Produktes der zwei Matrizen. Zur Analyse des Rechenaufwands:

Algorithmus M AT M ULT (A, B) 1 2 3 4 5 6 7 8 9 10 11 12 13 14

integer n = length(A); integer m = length(B); O(1) integer p = length(B[0]); erzeuge Array C[n][p]; }O(n · p) for i = 0 to n -1 do for j = 0 to p -1 do double sum = 0.0; for k = 0 to m-1 do sum = sum + (A[i][k] * B[k][j]); od C[i][j] = sum; od od return C

m Durchl.

p Durchl. n Durchl.

Zeile Kosten

Häufigkeit der Ausführung

1-3 4 5 6 7 8 9 11

1 mal 1 mal n + 1 mal (letzter Test) n · (p + 1) mal (letzter Test) n · p mal n · p · (m + 1) mal n · p · m mal n · p mal

c1 c2 · n · p c3 c4 c5 c6 c7 c8

Zusammen erhält man c1 + c2 · n · p + (n + 1)c3 + c4 · n · (p + 1) + c5 · n · p + c6 · n · p · (m + 1) + c7 n · p · m + c8 n · p. Das bedeutet, dass die Laufzeit dieses Algorithmus in O(npm) ist.

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen

13. April 2018

Präsenzaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 2

Präsenzaufgabe 2.1 (Sortieren) Sortieren Sie die Sequenz [7, 3, 5, 4, 1, 2, 8, 6] mittels Insertion Sort und mittels Selection Sort. Präsenzaufgabe 2.2 (ggT) Zeigen Sie, dass für alle a, b ∈ N gilt, dass ggT (a, b) = ggT (b, a mod b). Hinweis: Nach Definition gilt a mod b = a − (a div b) · b. Erinnerung: ggT (a, b) := max{t ∈ N | t |a und t |b} Lösung. Sei d = ggT (a, b) und d ′ = ggT (b, a mod b). Nach Definition des ggT erhalten wir sofort d|a, d|b, d ′ |b und d ′ |a mod b. Wir möchten nun d = d ′ zeigen. Falls d|a mod b gilt, so erhalten wir d ≤ d ′ , denn d ′ ist der größte gemeinsame Teiler von b und a mod b. Fall d ′ |a gilt, so erhalten wir d ′ ≤ d, denn d ist der größte gemeinsame Teiler von a und b. Wenn wir also zeigen, dass d ′ |a und d|a mod b, so gilt d = d ′ und sind wir fertig. Da a mod b = a − (a div b) · b und d sowohl a als auch b teilt, gilt d|a mod b. Da a = (a div b) · b + (a mod b) und d ′ sowohl b als auch a mod b teilt, gilt auch d ′ |a. Präsenzaufgabe 2.3 (O -Notation) Zeigen Sie, dass die Funktion f (n) = ⌈2 log2 (n)⌉! nicht polynomiell beschränkt ist; d.h. für jedes feste k ∈ N gilt f 6∈ O(nk ). Hinweis: Zeigen Sie zunächst für alle n ∈ N>0 , dass n! ≥ (n/2)n/2 gilt. Lösung. Behauptung: Für jedes k ∈ N gilt f 6∈ O(nk ) Hilfsbehauptung: Für alle n ∈ N>0 gilt n! ≥ (n/2)n/2 . Beweis. Es gilt n! ≥ (n/2)n/2 , da die Hälfte aller Faktoren von n! mindestens n/2 ist. n

n! = ∏ i ≥ i=1

n

n

∏

i≥

i=⌈ n2 ⌉

∏ i=⌈ n2 ⌉

ln m 2

n

≥

∏ i=⌈2n⌉

n  n n−⌈ n2 ⌉+1  n ⌊ n2 ⌋+1  n n2 = ≥ = 2 2 2 2

Durch Substitution gilt mit der obigen Ungleichung, für n ≥ 2 Hil f sb.

⌈2 log(n)⌉!

 log(n) n≥2 ≥ (⌈2 log(n)⌉/2)(⌈2 log(n)⌉/2) ≥ log(n)log(n) = 2log(log(n))  log(log(n)) = 2log(n) log(log(n)) = 2log(n) = nlog(log(n)).

Um zu zeigen, dass f 6∈ O(nk ) liegt, müssen wir jetzt also zeigen, dass für alle Exponenten k gilt: ∀c ∈ R>0 : ∀n0 ∈ N>0 : ∃n ≥ n0 : f (n) > c · nk . Seien k, n0 ∈ N und c ∈ R>0 . Wir zeigen, dass ein n ≥ n0 existiert, so dass nlog(log n) > n⌈c⌉+k = n⌈c⌉ nk ≥ c· nk . Damit gilt dann auch f (n) 6∈ O(nk ). Wir müssen also n so wählen, dass log(logn) > ·⌈c⌉+k ⌈c⌉ + k und n ≥ ⌈c⌉ gilt, was mit n = max{n0 , 22 , ⌈c⌉} + 1 möglich ist.

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen

20. April 2018

Präsenzaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 3

Präsenzaufgabe 3.1 (Knapsack) Lösen Sie folgende Instanz des Rucksack Problems mit dem Algorithmus aus der Vorlesung: Kapazität:10 Item 0 1 2 3 4 Gewicht 3 2 3 7 2 Profit 1 1 1 3 1 Überlegen Sie sich außerdem wie eine optimale Lösung des Rucksackproblems bestimmt werden kann und modifizieren Sie den untenstehenden Algorithmus entsprechend. Algorithmus K NAP SACK(P,W, B) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

integer n = length(W); integer maxprofit = 0; for i=0 to n-1 do maxprofit=maxprofit + P[i] od Erzeuge Feld A mit n * (maxprofit+1) A[0,0]=0; for t=1 to maxprofit do if p[0] t then A[0,t]=B + 1; else A[0,t]=W[0]; fi od for i=1 to n-1 do for t=0 to maxprofit do if t 0 then loesung.add(0); fi return loesung;

Präsenzaufgabe 3.2 (Rekurrenz) Die Funktion T : N0 → N0 sei für alle n ∈ N0 durch T (0) = 0, T (n) = aT (n − 1) + a − 1 für n ≥ 1 definiert. Finden Sie eine geschlossene Darstellung für T und beweisen Sie Ihr Ergebnis mit vollständiger Induktion. Lösung. Zunächst einmal eine kurze Hinleitung, wie man auf die geschlossene Form kommt. Im Wesentlichen gibt es zwei Ansätze: Bottom-Up oder Top-Down. Bottom-Up: Hier versuchen wir, durch Einsetzen von n = 1, 2, 3, . . . die geschlossene Form zu

erkennen. • Für n = 1 gilt T (n) = T (1) = a · T (0) + a − 1 = a · 0 + a − 1 = a − 1. • Für n = 2 gilt T (n) = T (2) = a · T (1) + a − 1 = a · (a − 1) + a − 1 = a2 − a + a − 1 = a2 − 1. • Für n = 3 gilt T (n) = T (3) = a ·T (2) +a −1 = a ·(a2 −1) + a −1 = a3 −a + a −1 = a3 − 1. • Für n = 4 gilt T (n) = T (4) = a ·T (3) +a −1 = a ·(a3 −1) + a −1 = a4 −a + a −1 = a4 − 1. Es scheint also T (n) = an − 1 zu gelten. Top-Down: Hier versuchen wir, durch wiederholtes Einsetzen der Rekursion die geschlossene

Form zu erkenen. Es gilt: T (n) = a · T (n − 1) + a − 1 = a[a · T (n − 2) + a − 1] + a − 1 = a2 · T (n − 2) + a2 − a + a − 1 = a2 · T (n − 2) + a2 − 1 = a2 [a · T (n − 3) + a − 1] + a2 − 1 = a3 · T (n − 3) + a3 − a2 + a2 − 1 = a3 · T (n − 3) + a3 − 1 = a3 [a · T (n − 4) + a − 1] + a3 − 1 = a4 · T (n − 3) + a4 − a3 + a3 − 1 = a4 · T (n − 3) + a4 − 1. Nach n Schritten steht dort also T (n) = an · T (n − n) + an − 1 = an − 1. Es scheint also T (n) = an − 1 zu gelten. Behauptung: Es gilt T (n) = an − 1 f.a. n ∈ N. Beweis per Induktion über n ∈ N. Induktions Anfang: Sei n = 0, es gilt T (0) = 0 = 20 − 1. Induktions Voraussetzung: Es gelte T (n) = an − 1 für ein festes n ∈ N. Induktions Schritt: z.Z. T (n + 1) = 2n+1 − 1 Es gilt, T (n + 1) = aT (n) + (a − 1) =I.V. a(an − 1) + (a − 1) = an+1 − a + a − 1 = an+1 − 1.

Präsenzaufgabe 3.3 (O -Notation) Seien a, b ∈ R>1 . Zeigen Sie, dass loga (n + 1) ∈ Θ(logb (n + 1)) gilt. log (x)

Zeigen Sie dafür zunächst: für alle x > 0 und alle a, b ∈ R>1 gilt loga (x) = log b(a) . b

Hinweis: logc (n) ist definiert als der Wert x, für den cx = n gilt. Lösung. Es gilt loga (xy) = loga (x) + loga (y) und daher auch loga (xy ) = y loga (x). log (x)

Hilfsbehauptung: loga (x) = log b(a) b

Beweis für die Hilfsbehauptung: Es gilt aloga (x) = x

⇔

(nach Definition)

loga (x)

) = logb (x)

⇔

(wende logb (·) auf beide Seiten an)

loga (x) logb (a) = logb (x) logb (x) loga (x) = logb (a)

⇔

(Nutze obige Rechenregel)

logb (a

(Umstellen)

Beweis Skizze: Setze c := max{logb a, 1/ logb a}, setze n0 := 1. Dann gilt für alle n ∈ N≥n0 : c≥logb (a) 1 1 1 logb (n) = loga (n) = log (n) logb (n) ≤ logb (a) logb (a) b c

c≥1/ logb (a)

≤

c logb (n)

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen

27. April 2018

Präsenzaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 4

Präsenzaufgabe 4.1 (Quicksort) Sortieren Sie die folgende Sequenz mittels Quicksort und notieren sie Zwischenergebnisse. Benutzen Sie hierfür den Algorithmus quicksort aus der Vorlesung mit der dort angegebenen Umordnungs-Strategie. [4, 6, 3, 9, 7, 4, 2, 8, 6] Lösung. Wir geben das Zwischenergebnis nach jedem rekursiven Aufruf von quicksort an. Die eingekreisten Elemente sind die Pivot-Elemente für den nächsten Aufruf. Mit einem Unterstrich sind die Elemente gekennzeichnet, die bereits richtig platziert sind und von quicksort nicht mehr bearbeitet werden. 4 6, 3, 9, 7, 4, 2, 8, 6] 1. [, 3 2, 4, 9, 7, 4, 6, 8, 6] 2. [, 3 4, 9, 7, 4, 6, 8, 6] 3. [2, , 9 7, 4, 6, 8, 6] 4. [2, 3, 4, , 6 7, 4, 6, 8, 9] 5. [2, 3, 4, , 4 6, 7, 6, 8, 9] 6. [2, 3, 4, , 7 6, 8, 9] 7. [2, 3, 4, 4, 6, , 6 7, 8, 9] 8. [2, 3, 4, 4, 6, , 8 9] 9. [2, 3, 4, 4, 6, 6, 7, , 10. [2, 3, 4, 4, 6, 6, 7, 8, 9]

Präsenzaufgabe 4.2 (Mergesort) Für ein Feld A, welches mit ganzen Zahlen A[0], . . . , A[n − 1] gefüllt ist, ist eine Inversion ein Index-Paar (i, j) mit i < j, so dass A[i] > A[ j]. Das Feld A = [5, 1, 3, 2] hat also die Inversionen (0, 1), (0, 2)(0, 3), (2, 3). 1. Geben Sie einen einfachen Algorithmus an, der in Zeit O(n2 ) die Inversionen in einem Feld der Länge A zählt. 2. Geben Sie einen Algorithmus an, der die Inversionen in Zeit O(n · log n) zählt. Hinweis: Modifizieren Sie MergeSort geeignet.

Lösung. 1. Der folgende Algorithmus löst das Problem offensichtlich in quadratischer Zeit, indem es alle Inversionen zählt: Algorithmus COUNT I NVERSIONS (A) 1 2 3 4 5 6 7 8 9 10 11

integer n = length(S); integer c = 0; integer i,j; for i = 0 to n-1 do for j = i + 1 to n-1 do if A[i] > A[j] then c = c + 1; fi od od return c

2. Wir können das Problem auch rekursiv mittels Mergesort lösen, indem wir zusätzlich zu den nun geordneten Arrays auch noch die Anzahl der Inversionen innerhalb des Arrays zurückgeben. Wenn wir also S in S1 und S2 aufteilen, geben uns die rekursiven Aufrufe die Anzahl von Inversionen c1 in S1 und die Anzahl an Inversionen c2 in S2 . Nun kann es aber noch Inversionen zwischen den beiden Arrays geben, wenn ein Element in S2 kleiner als ein Element in S1 ist. Die Anzahl c3 von diesen Inversionen müssen wir auch noch zählen. Das können wir wie folgt während der merge-Prozedur tun: Gilt irgendwann B[ j] < A[i], so haben wir ein Element x in S2 gefunden, das kleiner als A[i] ist. Da S1 sortiert ist, ist x auch größer als A[i + 1], . . . , A[N − 1]. Somit erzeugt x genau N − i Inversionen. Gilt zum Beispiel S1 = [1, 3, 5] und S2 = [2, 4], so ist B[ j = 0] < A[i = 1] und erzeugt somit N − i = 3 − 1 = 2 Inversionen. Algorithmus MERGESORT (S) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

integer n = length(S); integer m,i; integer c1 = 0, c2 = 0, c3 = 0; if (n >=2) then m = n div 2; erzeuge Feld S1 mit m Elementen; erzeuge Feld S2 mit n-m Elementen; for i=0 to m-1 do S1[i] = S[i]; od for i=0 to n-m-1 do S2[i] = S[m+i]; od c1 = mergesort(S1); c2 = mergesort(S2); c3 = merge(S1,S2,S); return c1 + c2 + c3 fi

Algorithmus M ERGE(A, B,C) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

integer N = length(A); integer M = length(B); integer i = 0, j = 0, k = 0, c = 0 ; while ((i < N) oder (j < M)) do if (i = N) then A(1): kopiere Rest von B nach C; else if (j = M) then A(2): kopiere Rest von A nach C; else A(3): if A[i] ≤ B[j] then kopiere A[i] nach C[k]; inkrementiere i und k; else kopiere B[j] nach C[k]; inkrementiere i und k; c = c + (N-i); // Zähle Inversionen fi fi fi od return c

Präsenzaufgabe 4.3 (Backtracking) Gegeben sei eine Landkarte auf der eine Menge L von Ländern abgebildet sind. Gesucht ist eine Färbung der Länder mit höchstens k Farben, so dass keine benachbarten Länder dieselbe Farbe erhalten. Geben Sie ein Programm in Pseudocode an, welches mit Hilfe von Backtracking eine Färbung der Landkarte bestimmt oder ausgibt, dass keine gültige Färbung mit k Farben existiert. Sie dürfen annehmen, dass eine Funktion Nachbar(i, j) existiert, die ihnen angibt, ob die Länder i und j benachbart sind. Lösung. Idee: • Die Färbung wird über ein Array C der Länge n geregelt, wobei C[j]=i bedeutet, dass Land j mit Farbe i gefärbt wurde. • Die Länder werden aufsteigend betrachtet. • Wenn das aktuelle Land gefärbt werden kann, wird die Farbe gespeichert und das nächste Land betrachtet. • Wenn das aktuelle Land j + 1 nicht gefärbt werden kann, wird das vorherige Land mit einer neuen Farbe betrachtet (also C[j] inkrementiert). Algorithmus FÄRBE L AND (i, c,C) 1

C[i] = c;

Algorithmus E NTFERNE FARBE(i,C) 1

C[i] = 0;

Algorithmus FARBE G ÜLTIG(i, c,C) 1 2 3 4 5 6

for j = 0 to i-1 do if Nachbar(i,j) && return false; fi od return true;

C[j]==c then

Algorithmus C OMP LETE(i,C, n, k) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

if i = n then return true; else boolean success = false; integer c = 1; while c x. • Bestimme die Längen a1 , a2 der Teilarrays A1 und A2 . Hierbei steht x an Position a1 und ist das (a1 + 1)-te Element • Wenn i = a1 + 1, gib x zurück; anderenfalls bestimme rekursiv das i-te Element in A1 falls i ≤ a1 bzw das (i − a1 − 1)-te Element in A2 falls i > a1 + 1.

Lösung. Gesucht: 8. Element [12, 10, 4, 6, 15|9, 14, 1, 13, 11|8, 3, 7, 5, 2] 5 7, 8] [4, 6, 10 , 12, 15|1, 9, 11 , 13, 14|2, 3, , [10, 11, 5] Array der Mediane. Gesucht: 2. Element 10 11] Median der Mediane [5, , [4, 6, 10, 8, 7, 1, 9, 5, 3, 2, 14, 13, 11, 15, 12] Teilen des Arrays mit Pivot 10 [4, 6, 2, 8, 7, 1, 9, 5, 3, 10, 14, 13, 11, 15, 12] Pivot 10 an richtige Stelle setzen [4, 6, 2, 8, 7|1, 9, 5, 3]Verbleibendes Teilarray. gesucht: 8. Element 6 7, 8|1, , 3 5, 9] [2, 4, , [6, 3] Array der Mediane. Gesucht: 1. Element 3 6] Median der Mediane [ , [2, 1, 6, 7, 8, 4, 3, 5, 9] Teilen des Arrays mit Pivot 3 [2, 1, 3, 7, 8, 4, 6, 5, 9] Pivot 3 an richtige Stelle setzen [7, 8, 4, 6, 5, 9]Verbleibendes Teilarray. gesucht: 5. Element [4, 5, 6, 7, 8, 9]Sortiere Teilarray. gesucht: 5. Element Gib 8 zurück Fun-Fact: Der Algorithmus wurde von Manuel Blum, Bob Floyd, Vaughan Pratt, Ron Rivest und Bob Tarjan entwickelt, als sie zeigen wollten, dass Median-Bestimmung genau so schwer wie Sortieren ist. Bis auf Vaughan Pratt haben alle anderen Autoren inzwischen einen TuringAward! Präsenzaufgabe 5.2 (Median) Betrachten Sie die Abwandlung des Median-Algorithmus, der das Array statt in Gruppen der Größe 5 in Gruppen der Größe 3 teilt. Können Sie für diesen Algorithmus ebenfalls zeigen, dass seine Laufzeit durch O(n) beschränkt ist? Hinweise: • Zur Vereinfachung nehmen wir an, dass der Algorithmus für größere Arrays eine größere Laufzeit benötigt; also, dass die Laufzeit monoton steigt. • Treffen Sie eine Abschätzung wie viele der Elemente mindestens größer beziehungsweise kleiner als der Median der Mediane sein müssen. • Geben Sie eine möglichst große untere sowie eine möglichst kleine obere Schranke für die Größe des verbleibenden Teilarrays an. • Erstellen Sie aus dieser Erkenntnis eine Rekurrenzgleichung T (n) für die Worst-Case Laufzeit. • Findet sich eine Konstante c ∈ R>0 und ein n0 ∈ N≥1 sodass für alle n ∈ N≥n0 gilt: T (n) ≤ cn? Lösung. Sei x der Median der Mediane. Behauptung: Es kann passieren, dass nur ⌈3n⌉ − 1 der Elemente verworfen werden können. Beweis: • Das Array wird in ⌈3n⌉ Gruppen geteilt.

• ⌈ 3n ⌉ − 1 der Gruppen haben 3 Elemente, die letzte Gruppe hat möglicherweise weniger Elemente.   n Element in der Menge der Media• Der Median der Mediane  n ist das ⌊ ⌈ 3 ⌉ + n1 /2⌋-größte  ne. Es gibt also ⌊ ⌈3 ⌉ + 1 /2⌋ − 1 =⌊ ⌈ 3 ⌉ −1 /2⌋ Gruppen, deren Mediane kleiner als x sind und ⌈ n3 ⌉ − ⌊ ⌈ n3 ⌉ + 1 /2⌋ = ⌈ ⌈ 3n ⌉ − 1 /2⌉ Gruppen, deren Mediane Größer als x sind. • In jeder bis auf einer Gruppen mit einem Median kleiner als x gibt es genau 2 Elemente, die kleiner als x sind. Eine der Gruppen kann weniger als drei Elemente enthalten und damit hat diese Gruppe nur ein Element, dass kleiner als x ist. • Zusätzlich enthält die Gruppe mit x genau ein Element das kleiner als x ist.   – n ist durch 3 teilbar: dann sind 2⌊ ⌈3n⌉ − 1 /2⌋ + 1 Elemente kleiner als x. Es gilt

⌈(n + 1)/3⌉ − 2 = ⌈n/3⌉ − 1 ≤ 2⌊(⌈n/3⌉ − 1) /2⌋ + 1 ≤ ⌈n/3⌉ = ⌈(n + 1)/3⌉ − 1

  – n ist nicht durch 3 teilbar: dann sind 2⌊ ⌈ 3n ⌉ − 1 /2⌋ + 1 − 1 Elemente kleiner als x. Es gilt: ⌈(n + 1)/3⌉ − 2 = ⌈n/3⌉ − 2 ≤ 2⌊(⌈n/3⌉ − 1) /2⌋ ≤ ⌈n/3⌉ − 1 = ⌈(n + 1)/3⌉ − 1 • In den Gruppen mit Median größer als x gibt es ebenfalls genau 2 Elemente die größer als x sind, bis auf die letzte Gruppe, in der es nur ein Element sein könnte. • Zusätzlich enthält die Gruppe mit x genau ein Element, dass Größer als x ist.   – n ist durch 3 teilbar: Dann gibt es 2⌈ ⌈ 3n ⌉ − 1 /2⌉ + 1 Elemente, die größer als x sind. Es gilt n/3 ≤ 2⌈(⌈n/3⌉ − 1) /2⌉ + 1 ≤ n/3 + 1   – n ist nicht durch 3 teilbar: Dann sind 2⌈ ⌈ 3n ⌉ − 1 /2⌉ − 1 + 1 Elemente größer als x. Es gilt n/3 ≤ ⌈n/3⌉ − 1 ≤ 2⌈(⌈n/3⌉ − 1) /2⌉ ≤ ⌈n/3⌉ • Damit können im schlimmsten Fall gemeinsam mit x nur ⌈(n + 1)/3⌉ − 1 Elemente verworfen werden, (wenn x kleiner ist als das gesuchte Element ist, ⌈n/3⌉ − 1 nicht durch 2 teilbar ist und alle übrigen Elemente größer als x sind). Rekurrenzgleichung: Sei l ∈ N konstant, sodass wir das Restarray ab einer Größe kleiner gleich l sortieren und den Median ablesen. Wir wollen nun Rekurrenzgleichungen aufstellen, in denen wir T (n) geeignet nach oben und unten abschätzen. Der Median-Algorithmus wird 2 mal rekursiv Aufgerufen. Einmal auf einem Array der Größe ⌈n/3⌉ um den Median der Mediane zu bestimmen und einmal auf dem Array der Zahlen des verbleibenden Suchbereichs. Die Größe des Restarrays ist nach oben beschränkt durch n − (⌈(n + 1)/3⌉ − 1) = ⌊2(n + 1)/3⌋. Es gibt also Konstanten a, b ∈ N≥1 , so dass wir T (n) wie folgt nach oben abschätzen können: ( a falls n ≤ l T (n) ≤ T (⌈n/3⌉) + T (⌊2(n + 1)/3⌋) + bn sonst Frage: Ist T (n) ∈ O(n)?

Annahme: ∃c ∈ R>0 ∃n0 ∈ N≥1 ∃n′ ∈ N≥n0 ∀n ∈ {n0 , . . . , n′ }T (n) ≤ cn Definiere n := n′ + 1. Dann gilt: T (n) ≤ T (⌈n/3⌉) + T (⌊2(n + 1)/3⌋) + bn Annahme

≤ c ⌈n/3⌉ + c(⌊2(n + 1)/3⌋) + bn > cn + bn > cn ⇒ Wir können T (n) auf diese Weise nicht durch cn ...