MINT lernen

Strategie Teile und herrsche

Ein Problem ist zu groß? Halbiere es so lange, bis jedes Stück trivial ist — und setze die Antworten wieder zusammen.

1

Teilen, lösen, zusammenführen

  • Teilen:das Problem in kleinere Teilprobleme derselben Art zerlegen, meist in zwei Hälften.
  • Herrschen:jedes Teilproblem rekursiv mit demselben Verfahren lösen.
  • Zusammenführen:aus den Teillösungen die Lösung des ganzen Problems bilden.
  • Basisfall:die Abbruchbedingung: ein Teilproblem ist so klein, dass die Lösung direkt feststeht — z. B. ein einziges Element.
  • Teilbereich:statt Teilreihungen zu kopieren, übergibt man die Grenzen links und rechts; mitte = (links + rechts) / 2 ganzzahlig.
static int maximum(int[] a, int links, int rechts) {
    if (links == rechts) {                      // Basisfall: ein Element
        return a[links];
    }
    int mitte = (links + rechts) / 2;           // teilen
    int maxL = maximum(a, links, mitte);        // herrschen: linke Hälfte
    int maxR = maximum(a, mitte + 1, rechts);   // herrschen: rechte Hälfte
    if (maxL > maxR) {                          // zusammenführen
        return maxL;
    }
    return maxR;
}
// int[] punkte = {13, 7, 22, 5, 18, 9};
// maximum(punkte, 0, punkte.length - 1) liefert 22

Wähle einen Bereich an (Klick oder Enter): Ist er noch groß, wird er geteilt. Sind beide Teile gelöst, führst du sie mit demselben Klick zusammen — die Teilergebnisse wandern nach oben. Mit ▶ läuft alles in der echten Aufrufreihenfolge ab. Wechsle zwischen „Maximum“ und „Summe“.

Teilen und zusammenführen

Halte fest: Teilen bis zum Basisfall, dann von unten nach oben zusammenführen. Bei n Elementen entstehen immer n Basisfälle und genau n − 1 Zusammenführungen — egal, in welcher Reihenfolge du vorgehst.

2

Aufwand und Einordnung

  • Rekursionsgleichung:\(T(n) = a\cdot T\!\left(\frac{n}{b}\right) + f(n)\) — \(a\) Teilprobleme der Größe \(\frac{n}{b}\), \(f(n)\) = Aufwand für Teilen und Zusammenführen.
  • Maximum:\(a = 2\), \(b = 2\), ein Vergleich beim Zusammenführen, also \(f(n) = 1\) und \(V(1) = 0\).
Herleitung:
\(V(n) = 2\,V\!\left(\tfrac{n}{2}\right) + 1\)
Ansatz

Zwei halb so große Teilprobleme, danach ein Vergleich. Hier \(n = 2^k\).

\(= 4\,V\!\left(\tfrac{n}{4}\right) + 2 + 1\)
einsetzen

\(V\!\left(\frac{n}{2}\right) = 2\,V\!\left(\frac{n}{4}\right) + 1\) eingesetzt.

\(= 2^k\,V\!\left(\tfrac{n}{2^k}\right) + 2^{k-1} + \dots + 2 + 1\)
\(k\)-mal

Nach \(k = \log_2 n\) Halbierungen ist jedes Teilproblem ein einzelnes Element.

\(= n\cdot V(1) + 2^k - 1\)
Summe

\(2^k = n\) und \(1 + 2 + \dots + 2^{k-1} = 2^k - 1\).

\(V(n) = n - 1\)
Ergebnis

\(V(1) = 0\): genau so viele Vergleiche wie die einfache Schleife — Teile und herrsche lohnt sich erst, wenn das Zusammenführen Arbeit spart.

Vier Verfahren nach dem Prinzip Teile und herrsche
VerfahrenTeilenrekursiv gelöstZusammenführenVergleiche
Binäre SucheMitte bestimmen1 Hälfte—\(\approx\log_2 n\)
MaximumMitte bestimmen2 Hälften1 Vergleich\(n-1\)
MergesortMitte bestimmen2 HälftenMischen: bis \(n\)\(\approx n\log_2 n\)
QuicksortZerlegen: \(n\)2 Teile—meist \(\approx n\log_2 n\)
Merke

Teile und herrsche: teilen → Teilprobleme rekursiv lösen → Teillösungen zusammenführen; Basisfall direkt lösen. Der Aufwand hängt von Zahl und Größe der Teilprobleme und vom Aufwand für Teilen und Zusammenführen ab.

3

Allgemeine Hinweise

Teile müssen kleiner werden

Mit den Bereichen links … mitte − 1 und mitte … rechts bleibt bei zwei Elementen ein Teil so groß wie vorher: maximum(a, 0, 1) ruft sich selbst erneut auf — bis zum StackOverflowError.

Drei Fragen beim Entwurf

Was ist der Basisfall? Wie entstehen die Teilprobleme? Wie wird aus den Teillösungen die Gesamtlösung? Wer diese drei Fragen beantwortet, hat den Algorithmus schon fast.

Nicht automatisch schneller

Das rekursive Maximum braucht genauso \(n-1\) Vergleiche wie eine Schleife, dazu Methodenaufrufe auf dem Aufrufstapel. Einen echten Gewinn bringt die Strategie erst bei Sortieren und Suchen.

Videos