Grundlegende Algorithmen: Lösungshinweise

Kapitel 2

2.1

Nach jedem Vergleich wissen wir von der größeren Zahl, dass sie nicht das Minimum sein kann. Werden weniger als n-1 Vergleiche ausgeführt, so gibt es mindestens zwei Zahlen, die noch für das Minimum in Frage kommen. Wir können beide Werte im Nachinein geeignet erniedrigen, ohne dass die vorherigen Vergleiche dadurch falsch werden. Je nachdem, wie wir das tun, ist entweder die eine oder die andere das Minimum. Ein beliebiger Algorithmus mit maximal n-2 Vergleichen kann also nicht feststellen, welche der beiden nun wirklich das Minimum ist.

2.2

Erweitere den Schlüssel k des i-ten Datensatzes zu (k,i) und verwende eine lexikographische Ordnung, die auf der ersten Komponente die ursprüngliche Ordnung verwendet.

2.3

Die obere Schranke ist klar, da es maximal n(n+1)/2 Verschiebungen geben kann.
Bei n Elementen ist die Wahrscheinlichkeit, dass das letzte Element Rang k hat gerade 1/n. Somit ist die erwartete Anzahl an Verschiebungen gerade die Summe von i=0 bis i=n über i/n, was (n+1)/2 ergibt.
Per Induktion lässt sich zeigen, dass dann die erwartete Anzahl von Verschiebungen durch 1/4(n-1)² nach unten beschränkt ist.

2.4

Es gilt.

2.5

Man kann zeigen: In der i-ten Phase wird das i-te größte Element an die richtige Position gebracht.

2.6

Man mische jeweils zwei der k Folgen zu einer neuen Folge zusammen. Man erhält dann k/2 Folgen der Länge 2n/k. Dies führt man fort, bis nur noch eine Folge übrig ist. In der i-ten Phase werden also je zwei Folgen der Länge 2^i-1n/k zu einer Folge der Länge 2ⁱn/k zusammengemischt. Dabei gibt es je Phase k/2ⁱ Mischvorgänge. Insgesamt benötigt jede Phase maximal n Vergleiche und da es maximal log(k) Phasen gibt, maximal nlog(k) Vergleiche:
T(n) < k*T(n/k)+nlog(k).
Per Induktion kann man zeigen, dass T(n)=O(nlog(n)) gilt.

2.7

Mit vollständiger Induktion und Fallunterscheidung, ob n gerade oder ungerade ist. Für den Fall n ungerade ist der Beweis technisch etwas aufwendiger.

2.8

T(n)=n-1.

2.9

Man muss nur zeigen, dass innerhalb eines Levels die Knoten aufsteigend nummeriert werden und dass der linkeste Knoten eines Levels eine um eins größere Nummer als der rechteste Knoten des vorherigen Levels erhält. Dies lässt sich mit Abzählen leicht nachweisen.

2.10

Laufzeit Θ(nlog(n)).

2.11

Für k=2 ist der beschriebene Algorithmus vom Prinzip her derselbe wie Heapsort. Die Details der Implementierung weichen jedoch etwas voneinander ab.
Zu Beginn werden in den Gruppen die Minima bestimmt. Dies benötigt O(n) Vergleiche. Anschließend werden in m Gruppen von jeweils maximal k Elementen die Maxima bestimmt. Da dies etwa n Mal wiederholt wird, ergibt sich eine Laufzeit von O(nmk)=O(knlog_k(n)).
Dies geht etwas effizienter für große k, wenn man nicht nur in jeder Gruppe das Minimum bestimmt, sondern die Elemente als sortiertes Feld verwaltet. Wenn man die Gruppen als Baum interpretiert, hat der Baum insgesamt O(n/k) Knoten (d.h. Gruppen). Das Sortieren aller Gruppen benötigt daher insgesamt O(n/k*klog(k)) =O(nlog(k)). Das Einfügen eines neuen Elements mittels binärer Suche in eine Gruppe kann in Zeit O(log(k)) geschehen. Somit benötigt die zweite Phase maximal Zeit O(nmlog(k)) =O(nlog_k(n)log(k)) =O(nlog(n)).

2.12

Ersetze in den beiden do-while-Schleifen (array[i] < array[pivot]) bzw. (array[j] > array[pivot]) durch (array[i] ≤ array[pivot]) bzw. (array[j] ≥ array[pivot]).

2.13

Betrachte H_n als Ober- bzw. Untersumme des Integrals über dx/x mit geeigneten Grenzen.

2.14

Man rechnet nach, dass die Höhe des entstehenden Rekursionsbaumes durch log(n)/log(1/(1-ε))=O(log(n) beschränkt ist (wobei ε konstant ist). Auf jedem Level benötigen alle Partitionierungen der einzelnen Teilintervalle (die ja eine Partition von [1:n] sein müssen) maximal Zeit O(n). Somit ist der Zeitbedarf insgesamt O(nlog(n)).

2.15

Quicksort: (3,3,1,1,2); wobei das letzte Element als Pivot gewählt wird.
Heapsort: (1,2,2,2); Beachte, dass das Feld bereits die Heap-Bedingung erfüllt.

2.16

Zeige mittels vollständiger Induktion, dass V_wc(n)≥1/2(n-1)n. Dabei zeigst sich, wie die worst-case Eingabe aussieht.

2.17

Nachrechnen.

2.18

Verfahre analog zu Mergesort und teile die Folge in eine linke und rechte Folge. Bestimme rekursiv die optimalen Teilsequenzen. Die optimale Teilsequenz ergibt sich aus den beiden optimalen Lösungen der Rekursion sowie einer optimalen Folge die über den Schnittpunkt hinweggeht. Letztere kann in linearer Zeit gefunden werden.

2.19

Fleißaufgabe; Mittels lineare Suche siehe [PS] bzw. [PDF].

2.20

Fleißaufgabe

2.21

Verwende einen Entscheidungsbaum: Da es (n+m)!/(n!m!) verschiedene Lösungen gibt, ist eine untere Schranke log((n+m)!/(n!m!))