Teile und herrsche und der Rekursionsbaum
Kurz gesagt: Teile und herrsche zerlegt ein Problem in kleinere Teile derselben Art, löst sie rekursiv und setzt die Antwort zusammen; der Rekursionsbaum zeigt die Kosten als Ebenen mal Arbeit pro Ebene.
Problem
Wie viele Lieferungen wurden vertauscht
Der Kurierdienst verspricht jedem Kunden eine Lieferzeit. Die Bestellungen haben also eine versprochene Reihenfolge: 1, 2, 3 und so weiter. Die Transporter fahren aber, wie sie fahren, und am Abend fragt der Bericht: Wie weit ist die heutige Reihenfolge der Lieferungen von der versprochenen entfernt?
Das Maß ist die Zahl der vertauschten Paare: Bestellung 5 wurde vor Bestellung 3 geliefert, obwohl 3 früher versprochen war. Ein solches Paar heißt Inversion. Sind die Lieferungen genau in der versprochenen Reihenfolge, gibt es 0 Inversionen.
Die erste Lösung prüft jedes Paar:
def count_pairs(ranks): inversions = 0 for i in range(len(ranks)): for j in range(i + 1, len(ranks)): if ranks[i] > ranks[j]: inversions += 1 return inversionsranks = [4, 1, 7, 3, 8, 2, 6, 5]print(f"Inversionen: {count_pairs(ranks)}")Inversionen: 12Bei 8 Bestellungen sind das 28 Paare. Bei n Bestellungen sind es n(n − 1)/2, also O(n²). Die Firma macht 100.000 Lieferungen am Tag, und die Paare sind 4.999.950.000. Der Bericht, der im Test einen Augenblick braucht, läuft am Abend minutenlang.
Die Idee
Teilen, zählen, zusammensetzen
Der Ansatz ist Teile und herrsche, wie bei Mergesort: Teile die Lieferungen in die erste und die zweite Hälfte. Jedes vertauschte Paar ist von einer von drei Arten:
- beide Bestellungen liegen in der ersten Hälfte;
- beide liegen in der zweiten;
- eine liegt in der ersten, die andere in der zweiten.
Die ersten zwei Arten sind dasselbe Problem, nur halb so groß: Die Rekursion zählt sie. Das Schwierige ist die dritte Art, die Paare über die Hälften hinweg. Prüfst du jedes einzeln, bist du wieder bei n².
Hier hilft das Zusammenfügen. Nimm an, beide Hälften sind schon sortiert. Beim Zusammenfügen nimmst du die kleinere der zwei ersten noch nicht genommenen Zahlen. Ist die kleinere rechts, ist jede links noch nicht genommene Zahl größer als sie und früher angekommen, weil sie aus der ersten Hälfte ist. Jede davon ist eine Inversion. Ein Vergleich zählt also auf einmal so viele, wie links Zahlen übrig sind.
So „fährt“ das Zählen auf dem Mergesort mit: dasselbe Teilen, dasselbe Zusammenfügen und eine Zeile mehr.
Sieh es dir an
Zählen beim Zusammenfügen
sort_count sortiert die Lieferungen an Ort und Stelle und liefert, wie viele Inversionen sie haben. Sieh dir das letzte Zusammenfügen an: Jede Zahl von rechts, die hinuntergeht, zählt die links nicht genommenen Zahlen:
def sort_count(ranks): if len(ranks) <= 1: return 0 mid = len(ranks) // 2 left = ranks[:mid] right = ranks[mid:] a = sort_count(left) b = sort_count(right) cross = 0 i = j = k = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: ranks[k] = left[i] i += 1 else: cross += len(left) - i ranks[k] = right[j] j += 1 k += 1 ranks[k:] = left[i:] + right[j:] return a + b + crossSchritt für Schritt, in Worten
- sort_count bekommt 8 Bestellungen in der Reihenfolge, in der sie ankamen. Jede Zahl ist der Platz der Bestellung in der versprochenen Reihenfolge.
- mid = 4: die ersten vier Lieferungen [4, 1, 7, 3] und die letzten vier [8, 2, 6, 5]. Jedes vertauschte Paar liegt entweder in einer Hälfte oder über beide hinweg.
- Jede Hälfte ruft sort_count für sich selbst auf: Sie zählt ihre eigenen Paare (a = 3, b = 4) und kommt sortiert zurück.
- Jetzt die Paare über die Hälften hinweg. i und j zeigen auf die erste noch nicht genommene Zahl. 1 < 2: Die linke geht nach unten, keine Inversion.
- 2 rechts ist kleiner. Jede links übrige Zahl ([3, 4, 7]) ist größer und früher angekommen: len(left) - i = 3 Inversionen auf einmal.
- Jedes Mal dieselbe Regel: 5 fügt 1 hinzu, 6 fügt 1 hinzu. cross = 5, nach 7 Vergleichen.
- Eine Seite ist zu Ende. Der Rest geht ohne Vergleich ans Ende: Er fügt keine Inversionen hinzu.
- a + b + cross = 3 + 4 + 5 = 12. Die Paarprüfung sieht sich alle 28 Paare an; das Zusammenfügen findet dieselben 12 mit insgesamt 17 Vergleichen.
ranks = [4, 1, 7, 3, 8, 2, 6, 5]print(f"Inversionen: {sort_count(ranks)}")print(f"Sortiert: {ranks}")Inversionen: 12Sortiert: [1, 2, 3, 4, 5, 6, 7, 8]Die Funktion sortiert das Array, das sie bekommt. Brauchst du auch die Reihenfolge der Lieferungen, übergib eine Kopie.
In Python kann die Funktion beide Ergebnisse als Tupel liefern,return merged, count. Hier geschieht das Sortieren in der Liste selbst: ranks[k:] = left[i:] + right[j:] setzt den Rest ans Ende, weil einer der zwei Teile leer ist.Probier es aus
Sage die Ausgabe voraus
Die zwei Hälften, [2, 4, 6] und [1, 3, 5], sind schon sortiert, also gibt es in ihnen keine Inversionen. Wie viele sind es über die Hälften hinweg?
def sort_count(ranks): if len(ranks) <= 1: return 0 mid = len(ranks) // 2 left = ranks[:mid] right = ranks[mid:] a = sort_count(left) b = sort_count(right) cross = 0 i = j = k = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: ranks[k] = left[i] i += 1 else: cross += len(left) - i ranks[k] = right[j] j += 1 k += 1 ranks[k:] = left[i:] + right[j:] return a + b + cross
ranks = [2, 4, 6, 1, 3, 5]print(f"Inversionen: {sort_count(ranks)}")1 kommt zuerst und zählt die drei, die links übrig sind (2, 4, 6). Dann 2 von links, 3 von rechts zählt 4 und 6, 4 von links, 5 von rechts zählt 6, und zuletzt 6. Die Summe ist 3 + 2 + 1 = 6. Von den 15 Paaren sind 6 vertauscht.
Die Idee
Der Rekursionsbaum
Was kostet das? Zeichne die Aufrufe als Baum. Oben steht der Aufruf mit allen n Bestellungen. Darunter die zwei Aufrufe, die er macht, mit je n/2. Unter jedem davon noch zwei, und so weiter bis nach unten.
Dann markiere für jeden Aufruf seine Arbeit: was er selbst tut, außerhalb seiner rekursiven Aufrufe. Hier ist das das Zusammenfügen: Es geht einmal durch jede Bestellung, die der Aufruf bekommen hat.
Jetzt addiere Ebene für Ebene. Oben ist die Arbeit n. Auf der nächsten Ebene gibt es zwei Aufrufe mit je n/2: wieder n. Dann vier mit je n/4: wieder n. Die Ebenen sind, wie oft sich n bis auf 1 halbiert, etwa log₂ n. Die Kosten sind also die Ebenen mal die Arbeit pro Ebene: n · log₂ n.
Das nennt man den Rekursionsbaum. So zählst du die Kosten jedes Teile-und-herrsche-Verfahrens: Du rätst nicht, du addierst Ebene für Ebene.
Sieh es dir an
Drei Bäume, drei Kosten
Dasselbe Zählen für drei Funktionen mit 8 Bestellungen. Die binäre Suche aus ihrer Lektion, mit Rekursion geschrieben. Das Zählen durch Zusammenfügen. Und eine dritte Funktion, die auch teilt, aber schlecht: die ersten n − 1 Bestellungen rekursiv, und die letzte wird mit allen davor verglichen.
def sort_count(ranks): if len(ranks) <= 1: return 0 mid = len(ranks) // 2 left = ranks[:mid] right = ranks[mid:] a = sort_count(left) b = sort_count(right) cross = 0 i = j = k = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: ranks[k] = left[i] i += 1 else: cross += len(left) - i ranks[k] = right[j] j += 1 k += 1 ranks[k:] = left[i:] + right[j:] return a + b + crossdef find(ranks, target, lo, hi): if lo > hi: return -1 mid = (lo + hi) // 2 if ranks[mid] == target: return mid if ranks[mid] < target: return find(ranks, target, mid + 1, hi) return find(ranks, target, lo, mid - 1)def count_slow(ranks, n): if n <= 1: return 0 inv = count_slow(ranks, n - 1) for i in range(n - 1): if ranks[i] > ranks[n - 1]: inv += 1 return invSchritt für Schritt, in Worten
- Jede Box ist ein Aufruf, und die Zahl darin ist, wie viele Bestellungen er bekommt. find sieht die Mitte einmal an: Arbeit 1.
- Dann ruft es sich für EINE Hälfte selbst auf: 8 → 4 → 2 → 1. Ein Zweig, und jede Ebene macht 1.
- 4 Ebenen × 1 = 4. Die Ebenen sind, wie oft sich n bis auf 1 halbiert, etwa log₂ n: O(log n).
- sort_count ruft sich für BEIDE Hälften selbst auf. Das Zusammenfügen oben geht durch alle 8 Bestellungen, die zwei darunter durch 4 + 4 = 8.
- Auf jeder Ebene doppelt so viele Aufrufe, jeder mit der halben Zahl von Bestellungen: Die Arbeit pro Ebene bleibt 8. Die Aufrufe mit einer Bestellung kehren nur zurück: 0.
- 3 Ebenen × 8 = 24: log₂ n Ebenen mit je n, O(n log n). Bei 100.000 Bestellungen sind das 17 Ebenen, nicht 100.000.
- count_slow teilt auch, aber schlecht: die ersten n − 1 Bestellungen und die letzte. Die Rekursion geht mit n − 1 weiter: 8 → 7 → 6 …
- Auf jeder Ebene wird die letzte Bestellung mit allen davor verglichen: 7, 6, … 1. 8 Ebenen, und 7 + 6 + 5 + … + 1 = 28: genau die 28 Paare, O(n²).
- Die Kosten sind die Form des Baums: Ebenen × Arbeit pro Ebene. Halbieren ergibt log n Ebenen; einzelnes Abspalten ergibt n Ebenen. Teilen allein genügt nicht: Die Hälften müssen gleich groß sein.
sorted_ranks = [1, 2, 3, 4, 5, 6, 7, 8]print("find:", find(sorted_ranks, 8, 0, len(sorted_ranks) - 1))ranks = [4, 1, 7, 3, 8, 2, 6, 5]print("count_slow:", count_slow(ranks, len(ranks)))print("sort_count:", sort_count(ranks))find: 7count_slow: 12sort_count: 12Die Form des Baums entscheidet:
- Ein Zweig, die Hälfte: log₂ n Ebenen mit wenig Arbeit. O(log n).
- Zwei Zweige, Hälften: log₂ n Ebenen mit je n. O(n log n).
- Ein Zweig, um eins kleiner: n Ebenen mit je n. O(n²). Das ist das Prüfen von Paaren, nur mit Rekursion geschrieben.
Dasselbe geschieht bei Quicksort mit schlechtem Pivot: Bei sortierter Eingabe spaltet der Pivot einen Preis ab, und die anderen n − 1 bleiben in einem Teil. Der Baum ist eine Kette aus n Ebenen, und die Komplexität ist n².
Sieh es dir an
Miss es: paarweise gegen Zusammenfügen
Lass beide auf denselben Lieferungen laufen. Bei den Paaren zählen wir die geprüften Paare, beim Zusammenfügen die Vergleiche. Paarweise läuft bei 100.000 nicht wirklich: Bench schätzt es aus der Kurve.
- Inversionen über Paare
O(n²) - Inversionen beim Mischen
O(n log n)
| Algorithmus | n = 10 | n = 1.000 | n = 10.000 | n = 100.000 |
|---|---|---|---|---|
| Inversionen über Paare | 45 | 499.500 | 49.995.000 | ≈ 4.999.500.000 |
| Inversionen beim Mischen | 21 | 8.693 | 120.553 | 1.536.329 |
def sort_count(ranks): if len(ranks) <= 1: return 0 mid = len(ranks) // 2 left = ranks[:mid] right = ranks[mid:] a = sort_count(left) b = sort_count(right) cross = 0 i = j = k = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: ranks[k] = left[i] i += 1 else: cross += len(left) - i ranks[k] = right[j] j += 1 k += 1 ranks[k:] = left[i:] + right[j:] return a + b + crossBei 1000 Lieferungen sind die Paare 499.500 und die Vergleiche 8.693. Bei 100.000 macht das Zusammenfügen 1.536.329 Vergleiche gegen 4.999.950.000 Paare: über 3000-mal weniger. Und die Inversionen sind dieselben, 2.504.458.463.
Genauer, für Neugierige
Dieselben Zahlen in deiner Sprache. Die Lieferungen werden mit einem kleinen Generator mit Seed gemischt, sind also bei jedem Lauf, in jeder Sprache und in Bench gleich:
checks = 0comparisons = 0
def deliveries(n): ranks = list(range(1, n + 1)) x = 2026 for k in range(n - 1, 0, -1): x = x * 48271 % 2147483647 j = x % (k + 1) ranks[k], ranks[j] = ranks[j], ranks[k] return ranks
def count_pairs(ranks): global checks inversions = 0 for i in range(len(ranks)): for j in range(i + 1, len(ranks)): checks += 1 if ranks[i] > ranks[j]: inversions += 1 return inversions
def sort_count(ranks): global comparisons if len(ranks) <= 1: return 0 mid = len(ranks) // 2 left = ranks[:mid] right = ranks[mid:] a = sort_count(left) b = sort_count(right) cross = 0 i = j = k = 0 while i < len(left) and j < len(right): comparisons += 1 if left[i] <= right[j]: ranks[k] = left[i] i += 1 else: cross += len(left) - i ranks[k] = right[j] j += 1 k += 1 ranks[k:] = left[i:] + right[j:] return a + b + cross
for n in [10, 1000]: checks = 0 inv = count_pairs(deliveries(n)) print(f"paarweise, n = {n}: {checks} Prüfungen, {inv} Inversionen")for n in [10, 1000, 100000]: comparisons = 0 inv = sort_count(deliveries(n)) print(f"durch Zusammenfügen, n = {n}: {comparisons} Vergleiche, {inv} Inversionen")paarweise, n = 10: 45 Prüfungen, 14 Inversionenpaarweise, n = 1000: 499500 Prüfungen, 249193 Inversionendurch Zusammenfügen, n = 10: 21 Vergleiche, 14 Inversionendurch Zusammenfügen, n = 1000: 8693 Vergleiche, 249193 Inversionendurch Zusammenfügen, n = 100000: 1536329 Vergleiche, 2504458463 Inversionenlong sein: Ein int hört bei 2.147.483.647 auf und läuft ohne Fehler über.Probier es aus
Finde den Fehler
Ein Kollege hat die Funktion umgeschrieben. Für die 8 Lieferungen aus der Szene sagt sie 5 statt 12:
ranks = [4, 1, 7, 3, 8, 2, 6, 5]print(f"Inversionen: {sort_count(ranks)}")print(f"Sortiert: {ranks}")Inversionen: 5Sortiert: [1, 2, 3, 4, 5, 6, 7, 8]In welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Die Funktion liefert nur cross: die Paare über die Hälften dieses Aufrufs hinweg. Die Inversionen in der linken Hälfte (a) und der rechten Hälfte (b) wurden von der Rekursion gezählt, werden hier aber weggeworfen. So kommen nur die Paare des letzten Zusammenfügens nach oben, 5. Teile und herrsche baut die Antwort aus allen drei Teilen: a + b + cross.
Probier es aus
Ergänze
Die Zahl rechts ist kleiner und geht nach unten. Um wie viel wächst cross?
def sort_count(ranks):
if len(ranks) <= 1:
return 0
mid = len(ranks) // 2
left = ranks[:mid]
right = ranks[mid:]
a = sort_count(left)
b = sort_count(right)
cross = 0
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
ranks[k] = left[i]
i += 1
else:
cross +=
ranks[k] = right[j]
j += 1
k += 1
ranks[k:] = left[i:] + right[j:]
return a + b + crossDie linke Hälfte ist sortiert, und i zeigt auf die erste nicht genommene Zahl darin. Alle ab i bis zum Ende sind größer als die rechts und früher angekommen: Das sind len(left) - i Paare. Mit cross++ würdest du eines pro Nehmen zählen und die meisten verpassen.
Übung
Der Tagesbericht
Löse die Aufgabe in deinem Editor.
Vertauschte Paare. Lies die Reihenfolge der Lieferungen (die versprochenen Nummern, durch Leerzeichen getrennt) und gib aus, wie viele Paare vertauscht sind und von wie vielen. Nutze sort_count aus der Lektion.
3 1 2 6 4 5 10 7 9 8Vertauschte Paare: 8 von 45Weitere Aufgaben
- Zeichne den Baum. Eine Funktion teilt ihre Eingabe in drei gleiche Teile und ruft sich für jeden auf, und ihre Arbeit außerhalb der Aufrufe ist n. Zeichne die Ebenen: Wie viele sind es, und wie groß ist die Arbeit pro Ebene? Und wenn es zwei Teile sind, die Arbeit jedes Aufrufs aber n² ist?
- Wer verspätet sich am meisten. Zähle für jede Bestellung, wie viele Bestellungen mit größerer Nummer vor ihr geliefert wurden. Die Summe dieser Zahlen ist die Zahl der Inversionen. Wie sammelst du sie beim Zusammenfügen? Hinweis: Geht eine Zahl von rechts nach unten, zählen die links nicht genommenen Zahlen für sie.
- Ist es fast sortiert. Zähle die Inversionen in einer fast sortierten Reihenfolge (zwei benachbarte Bestellungen vertauscht). Wie viele Vergleiche macht das Zusammenfügen? Und Insertionsort aus den einfachen Sortierverfahren mit derselben Eingabe?
Genauer
Das Mastertheorem und die anderen Sprachen
Der Rekursionsbaum funktioniert für jedes Teile-und-herrsche-Verfahren. Für die häufigste Art gibt es auch eine fertige Regel.
Genauer, für Neugierige
Das Mastertheorem als Intuition. Eine Funktion, die ihre Eingabe in b gleiche Teile zerlegt, sich a-mal aufruft und außerhalb der Aufrufe die Arbeit f(n) macht, schreibt man T(n) = a · T(n/b) + f(n). Zeichne den Baum und vergleiche die Arbeit oben mit der Arbeit unten:
- Die Arbeit ist auf jeder Ebene gleich. Du multiplizierst mit der Zahl der Ebenen, log n. Mergesort: T(n) = 2 · T(n/2) + n, n pro Ebene, O(n log n). Binäre Suche: T(n) = T(n/2) + 1, 1 pro Ebene, O(log n).
- Die Arbeit schrumpft nach unten. Die oberste Ebene entscheidet. T(n) = 2 · T(n/2) + n² ist O(n²): Die unteren Ebenen sind n²/2, n²/4 und so weiter, und ihre Summe liegt unter einem weiteren n².
- Die Arbeit wächst nach unten. Die Blätter entscheiden. Karatsubas Multiplikation großer Zahlen ist T(n) = 3 · T(n/2) + n: drei Hälften auf jeder Ebene, die Arbeit wächst pro Ebene um 3/2, und die Komplexität ist etwa n^1,58 statt des n² der Schulmultiplikation.
Die schlechte Teilung T(n) = T(n − 1) + n gehört gar nicht zu dieser Art: Die Eingabe wird nicht durch b geteilt, sie schrumpft um eins. Das Theorem hilft dort nicht, der Baum aber schon: n Ebenen mit etwa n, O(n²).
Die Mathematik dahinter steht in jedem Lehrbuch über Algorithmen. Für die Arbeit genügt das Bild: wie viele Ebenen und wie viel Arbeit pro Ebene.
Wie tief die Rekursion geht. Der Aufrufstapel ist so hoch wie die Ebenen des Baums. Das Zählen durch Zusammenfügen sind 17 Ebenen bei 100.000 Bestellungen und passt überall. Die schlechte Teilung sind n Ebenen.
In Python ist das ein Problem. Die Rekursionsgrenze liegt bei 1000 Ebenen, und die Funktion mit n − 1 fällt lange um, bevor sich die langsame Zeit zeigt:
def deliveries(n): ranks = list(range(1, n + 1)) x = 2026 for k in range(n - 1, 0, -1): x = x * 48271 % 2147483647 j = x % (k + 1) ranks[k], ranks[j] = ranks[j], ranks[k] return ranks
def count_slow(ranks, n): if n <= 1: return 0 inv = count_slow(ranks, n - 1) for i in range(n - 1): if ranks[i] > ranks[n - 1]: inv += 1 return inv
def sort_count(ranks): if len(ranks) <= 1: return 0 mid = len(ranks) // 2 left = ranks[:mid] right = ranks[mid:] a = sort_count(left) b = sort_count(right) cross = 0 i = j = k = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: ranks[k] = left[i] i += 1 else: cross += len(left) - i ranks[k] = right[j] j += 1 k += 1 ranks[k:] = left[i:] + right[j:] return a + b + cross
ranks = deliveries(5000)try: count_slow(ranks, len(ranks))except RecursionError as e: print("count_slow:", type(e).__name__)print("sort_count:", sort_count(ranks))count_slow: RecursionErrorsort_count: 6243322Inversionen als Maß. Die Zahl der Inversionen zwischen zwei Reihenfolgen misst, wie sehr sie sich unterscheiden: So vergleicht man Ranglisten, zum Beispiel die Ergebnisse einer Suchmaschine mit den Bewertungen von Menschen. Insertionsort macht genau so viele Verschiebungen, wie seine Eingabe Inversionen hat. Deshalb ist er bei fast sortierter Eingabe schnell und bei gemischter langsam.
Test