- Teile die Eingabe (input) in kleinere Unterprobleme
- Bearbeite (beherrsche) die Unterprobeme rekursiv.
- Kombiniere die Unterprobleme zur Lösung des ursprünglichen Problems.
Merge-Sort, RectIntMult und Karatsuba sind Beispiele für Teile-und-Herrsche Algorithmen.
Die Anzahl der Inversionen eines Arrays ist die Zahl der Paare von Elementen, die nicht der Reihenfolge (Ordnng) entsprechen. Zwei Elemente sind dabei nicht in der richtigen Reihenfolge, falls das Element mit dem niedrigeren Index größer ist als das Element mit dem höheren Index.
Input: Ein Array $A$ mit unterschiedlichen Ganzzahlwerten
Output: Die Anzahl der Inversionen von $A$, d.h. die Anzahl der Paare in $A$ mit $A[i] > A[j]$ und $ i < j $.
Beispiel:
Hier sind unter anderem die 3 und die 2 nicht in der aufsteigend angeordnet. Dies trägt zur Anzahl der Inversionen bei.
Wieviel Inversionen gibt es hier (insgesamt)?
Wieviel Inversionen kann ein 6-stelliges Array maximal haben?
$(n-1)+(n-2)+ \dots + 2 + 1 = \frac{n (n-1)}{2}$
Die Anzahl der Inversionen ist als Ähnlichkeitsmaß für zwei Präferenzlisten.
Wie ist die Zeitkomplexität von brute-force search?
Can we do better?
Es gibt (also) drei Arten von Inversionen bei dem Teile-und-Herrsche Ansatz:
CountInv¶Input: array $A$ of $n$ distinct integers
Output: the number of inversions of $A$
if $n = 0$ or $n = 1$
// base cases
then return 0
else
leftInv $=$CountInv(first half of $A$)
rightInv $=$CountInv(second half of $A$)
splitInv $=$CountSplitInv(A)
return leftInv $+$ rightInv $+$ splitInv
Offene Frage:
Wie kann
CountSplitInveffizient (linear in der Länge) durchgeführt werden.
Wenn die erste Hälfte von $A$ die Zahlen $\frac{n}{2}+1, \frac{n}{2}+2, \dots n-1, n$ enthält und die zweite Hälfte die Zahlen $1, 2, \dots \frac{n}{2}-1, \frac{n}{2}$. Wie viele Split-Inversion müssen beim Merge berücksichtigt werden?
Für jedes Element in der ersten Hälfte haben wir Anzahl der Elemente in der zweiten Hälfte als
Anzahl der Split-Inversionen, d.h.
$n/2 \cdot n/2 = n^2/4$, also quadratisch in $n$
Ambitioniertes Ziel:
Wie kann man diese in $n$ quaratische Anzahl in linearer Zeit zählen?
Idee: Huckepack (piggyback) auf MergeSort, d.h. parallel rekursiv sortieren.
Erinnerung: Sortieren mit MergeSort ist $O(n \log n)$.
Sort-and-CountInv¶Input: array $A$ of $n$ distinct integers
Output: the sorted array $B$ (with the same integers as $A$) and the number of inversions of $A$
if $n = 0$ or $n = 1$ // base cases
then return ($A$, $0$)
else
($C$, leftInv) = Sort-and-CountInv(first half of $A$)
($D$, rightInv) = Sort-and-CountInv(second half of $A$)
($B$, splitInv) = Merge-and-CountSplitInv($C$, $D$)
return ($B$, leftInv $+$ rightInv $+$ splitInv)
Wie sieht Merge-and-CountSplitInv genau aus?
Merge (Mergesort)Merge-and-CountSplitInv¶Input: sorted arrays $C$ and $D$ with length $n/2$ each
Output: the sorted array $B$ (length $n$) and the number of split inversions between
$C$ and $D$
$i := 1$, $j := 1$, splitInv $:= 0$
for $k := 1$ to $n$ do
if $C[i] < D[j]$ then
$B[k] := C[i], i := i+1$
else
$B[k] := D[j], j := j+1$
splitInv $:=$ splitInv $+ (n/2-i+1)$
return ($B$, splitInv)
$O(n \log n)$ - Argumentation analog MergeSort
MergeSort) kann das Problem in $\Theta\left(n\log n\right)$ gelöst werden.