Grundlegende Algorithmen: Lösungshinweise

Kapitel 3

3.1

Beweis durch Induktion. Dabei darf man die n-1 Vergleiche für das Partitionieren nicht vergessen (man könnte das Partitionieren bei der Medianbestimmung miterledigen, dies wurde hier aber nicht vorausgesetzt!) und den Term O(n) mit 0 ansetzen.

3.2

Es sind sogar nur 6 Vergleiche ausreihend und notwendig.

• Bild zunächst zwei Paare von Elementen und vergleiche diese (1. und 2. Vergeich).
• Vergleiche die beiden gröseren miteinander (3. Vergleich). Das Maximimun muss nun Rang 1 oder zwei besitzen und kommt als Median nicht in Frage.
• Nun haben wir ein Paar von Elementen, die bereits miteinander verglichen wurden und zwei Elemente, die jeweils nicht mit den restlichen dre Elementen verglichen wurden. Vergleiche die beiden einzelen Elemente (4. Vergleich), so dass wir wieder zwei Paare von Elementen eralten, die miteinander verglichen wurden.
• Vergleiche nun wieder die beiden Maxima der Paare (5. Vergleich). Dieses muss nun den Rang 1 oder zwei besitzten, d.h. wir kennen jetzt die beiden größten Elemente.
• Im letzten und 6. Vergleich vergleichen wir jetzt unter den drei verbliebenen Elementen, die beiden Elemente, die noch keinen Vergleich gegen diese Elemente verloren haben. Das größere davon besitzt den Rang 3 und ist der gesuchte Median.

Die allgemeine untere Schranke aus diesem Kapitel liefert die hier gesuchte untere Schranke.

3.3

Nachrechnen.

3.4

Für k=3 zeigt sich, dass die lineare Laufzeit nicht zu halten ist.
Für ungerade k>5 ist die Analyse nicht einfach, da es aufwendig ist, die minimale Anzahl von Vergleichen zur Medianbestummung zu ermitteln. Eine ausführliche Analyse (aufwendig!) zeigt, dass die Werte zuerst absteigen und dann wieder zunehmen, wobei dies nur für sehr große n gilt.

3.5

Man vergleiche die Mediane der beiden Listen. Wenn beide gleich sind, hat man den Median der Gesamtmenge gefunden. Andernfalls kann man (m+n)/2 Elemente als Kandidaten für den Median der Gesamtmenge ausschließen und man wendet das Verfahren rekursiv auf die verbleibenden Liste der Länge m/2 bzw. n/2 an.

3.6

Bestimme zuerst mit Hilfe eines fast vollständigen binären Baumes das Maximum (n-1 Vergleiche). Bestimme dann das Maximum aller Verlierer gegen das eigentliche Maximum (log(n)-1 Vergleiche).
---

3.7

Wir diskutieren nur den Fall, dass n gerade ist. Führe zuerst n/2 Vergleiche von disjunkten Paaren aus (n/2 Vergleiche). Die jeweils größeren bzw. kleineren Elemente sammle in der Menge G bzw. L. Bestimme in G das Maximum und in L das Minimum (2(n/2-1)=n-2 Vergleiche).

Wir diskutieren nur den Fall, dass n gerade ist. Wir führen folgende Bezichnungen für Elemente ein

1. o bedeutet, das Element war noch an keinem Vergleich beteiligt;
2. + bedeutet, das Element hat alle bisherigen Vergleiche gewonnen;
3. - bedeutet, das Element hat alle bisherigen Vergleiche verloren;
4. * bedeutet, das Element hat bereits Vergleiche sowohl gewonnen als auch verloren.

Elemente * brauchen wir nicht mehr zu berücksichtigen, sie können weder das Maximum noch das Minimum sein. Demnach machen nur noch folgende Vergleiche einen Sinn (beachte die Symmetrie):

1. o/o geht über in +/-;
2. o/+ geht schlimmstenfalls in -/+ über;
3. o/- geht schlimmstenfalls in +/- über;
4. +/+ geht in +/* über;
5. +/- geht schlimmstenfalls in +/- über (Vergleich somit sinnlos!);
6. -/- geht in -/* über;

Somit ist der Vergleich o/o der fruchtbarste, er liefert zwei Einschränkungen. Alle anderen (außer +/-) liefern im schlimmsten Fall nur eine weitere Einschränkung. Man überlegt sich leicht, dass mindestens 2n-2 Einschränkungen benötigt werden, bevor ein beliebiger Algorithmus sowohl das Maximum als auch das Minimum verkünden kann.
Somit kann ein cleverer Algorithmus mit n/2 Vergleichen vom Typ o/o insgesamt maximal n Einschränkungen holen; dann gibt es nur noch Elemente vom Typ + oder -. Die benötigen restlichen n-2 Einschränkungen müssen dann mit n-2 Vergleichen vom Typ +/+ bzw. -/- gemacht werden. Daher sind mindestens 3n/2-2 Vergleich nötig.

3.8

Konstruiere nebenher einen Graphen, der für jedes Ergebnis x<y die Kante (x,y) aufnimmt. Zum Schluss entferne alles ausgehenden Kanten des Medians m (d.h. (m,*)). Man kann zeigen, dass die Zusammenhangskomponente mit m genau die k Elemente umfasst, die größer gleich m sind.

3.9

Bestimme den Median der Menge und partitioniere die Menge in zwei Mengen, eine mit Elementen kleiner gleich und eine mit Elementen größer als der Median. Suche rekursiv in der richtigen Menge weiter.