divide & conquer

#Definition #IntroProg #Informatik #MINTgrün #Studium

divide & conquer

Prinzp

Teile Eingabe in mehrere Teile auf
Löse das Problem rekursive auf den Teilen
Füge die Teillösungen zu einer Gesamtlösung zusammen

Mastertheorem

Fall 1

Laufzeit auf unterster Rekursionsstufe dominiert: $O (n^{\log_{b} (a)})$

Fall 2

Laufzeiten zusammensetzen und Rekursion vergleichbar: $O (n^{\log_{b} (a)} \cdot \log (n))$

Fall 3

Laufzeit zusammensetzen dominiert: $O (f (n))$

Basics

wodurch unterscheiden sich Teile & Herrsche Algorithmen?

Anzahl der Teilprobleme
Die Größe der Teilprobleme
Den Algorithmus für das Zusammensetzen der Teilproblem
Den Rekursionsabbruch

wann lohnt sich Teile & Herrsche?

Kann durch Laufzeitanalyse vorhergesagt werden
Wovon hängt die Laufzeit ab?
- Anzahl der Teilprobleme
- Größe der Teilprobleme
- Algorithmus für das Zusammensetzen der Teilprobleme

Rekursionsgleichung

Rekursionsgleichung von Teile & Herrsche lautet immer $T (n) = a \cdot T (\frac{n}{b}) + f (n)$
- $a$ := Anzahl der Unterprobleme
- $T (\frac{n}{b})$ := Größe der Unterprobleme (bestimmt Höhe des Rekursionsbaums)
- $f (n)$ := Aufwand für Aufteilen und Zusammenfügen
Rekursionsgleichung Mergesort
- $t (n) = 2 \cdot T (\frac{n}{2}) + c \cdot n$

binäre Suche

Problem: Finde Element b in sortiertem Feld
Algorithmus: binäre Suche

Prinzip:

Suche:
- Vergleiche Element b mit dem mittleren Element des Feldes
- wenn gefunden, gib Feldindex zurück
- wenn kleiner, dann such rekursiv im linken Teilfeld
- wenn größer, dann suche rekursiv im rechten Teilfeld
Abbruchbedingung:
- wenn Feldgröße == 0, gib "Element nicht gefunden" zurück
- wenn gefunden, gib Feldindex zurück

vereinfachte binäre Suche mit Annahme b ist im Feld A

Problem: Finde Index des Elements b in sortiertem Feld
Annahme: Element vorhanden, d.h. b existiert im sortierten Feld
Algorithmus Vereinfachte binäre Suche

Prinzip:

Suche
- Vergleiche Element b mit dem mittleren Element des Feldes
- wenn kleiner, dann suche rekursiv im linken Teilfeld
- wenn größer, dann suche rekursiv im rechten Teilfeld
Abbruchbedingung;
- Wenn Feldgröße == 1, gib den Index zurück

Algorithmus:

\begin{array}{ll} BinäreSuche (A, b, p, r) // A Feld, b Element, p Feldanfang, r Feldende \\ 1. & if p = r then return p \\ 2. & else \\ 3. & q \leftarrow ⌊ (p + r) / 2 ⌋ \\ 4. & if b \leq A [q] then return BinäreSuche (A, b, p, q) \\ 5. & else return BinäreSuche (A, b, q + 1, r) \end{array}

beweis

vorhanden ist.

Beweis: per Induktion über

n = r - p

(I.A.) Für $n = 0$ , d.h. $p = r$ , gibt der Algorithmus $p$ zurück. Dies ist der korrekte (weil einzige) Index.
(I.V.) Für alle $r, p$ mit $m = r - p$ und $0 \leq m \leq n$ findet BinäreSuche(A,b,p,r) den Index einer Zahl $b$ in einem sortierten Feld A[p..r], sofern b im Feld vorhanden ist.
(I.S.) Wir betrachten den Aufruf von BinäreSuche für beliebige $p$ , $r$ mit $n + 1 = r - p$
- Da $n + 1 > 0$ folgt $p < r$ und der Algorithmus führt den ersten else-Fall aus.
- Dort wird q auf $⌊ (p + r) / 2 ⌋$ gesetzt. – Es gilt $q \geq p$ und $q < r$ .
- Ist $b \leq A [q]$ , so wird BinäreSuche rekursiv für $A [p . . q]$ aufgerufen.
  - Da $A [p . . r]$ sortiert ist, liegt $b$ in $A [p . . q]$ .
  - Damit folgt aus (I.V.), dass der Index von $b$ gefunden wird.
- Ist $b > A [q]$ , so wird BinäreSuche rekursiv für $A [q + 1. . r]$ aufgerufen.
  - Da $A [p . . r]$ sortiert ist, liegt $b$ in $A [q + 1. . r]$ .
  - Damit folgt aus (I.V.), dass der Index von $b$ gefunden wird.

Laufzeit

\begin{array}{ll} 1. & if p = r then return p & 1 \\ 2. & else & 1 \\ 3. & q \leftarrow ⌊ (p + r) / 2 ⌋ & 1 \\ 4. & if b \leq A [q] then return BinäreSuche (A, b, p, q) & 1 + T (⌊ n / 2 ⌋) \\ 5. & else return BinäreSuche (A, b, q + 1, r) & 1 + T (⌈ n / 2 ⌉) \\ 5 + max {T (⌊ n / 2 ⌋), T (⌈ n / 2 ⌉)} \end{array}

Laufzeit: T (n) = {\begin{cases} 1, & falls n = 1 \\ 5 + max {T (⌊ n / 2 ⌋), T (⌈ n / 2 ⌉)}, & falls n > 1 \end{cases}

Rekursionsgleichung: $T (n) = 1 \cdot T (\frac{n}{2}) + c$

!introprog-v12-teile-herrsche-die-zweite, p.91

Binäre Suche ohne Annahme

**Problem:**Finde Element b in sortiertem Feld
Eingabe: Sortiertes Feld A, gesuchtes Element b
Ausgabe: Index i mit A[i] = b oder -1 (für nicht gefunden)

Algorithmus

\begin{array}{ll} 1. & if p = r and A [p] = b then return p / / Element gefunden \\ 2. & else if p = r and A [p] \neq b then return - 1 / / Element nicht gefunden \\ 3. & else \\ 4. & q \leftarrow ⌊ (p + r) / 2 ⌋ \\ 5. & if b \leq A [q] then return BinäreSuche (A, b, p, q) / / links \\ 6. & else return BinäreSuche (A, b, q + 1, r) / / rechts \end{array}

binäre Suche vs. lineare Suche

Laufzeit	10	100	1.000	10.000	100.000
n	10	100	1.000	10.000	100.000
log n	3	6	10	13	17

Integer Multiplikation

Problem: Multipliziere zwei n-Bit Integer
Eingabe: Zwei n-Bit Integer X,Y
Ausgabe: 2n-Bit Integer Z mit Z=XY
Annahmen:
- Wir können n-Bit Integer in Θ(n) (worst case) Zeit addieren
- Wir können n-Bit Integer in Θ(n+k) (worst case) Zeit mit $2^{k}$ multiplizieren (durch Shift)

Schulmethode (binär)

!200
Laufzeit: $O (n^{2})$

mit Teile & Herrschen

Einfaches Teile und Herrsche

!introprog-v12-teile-herrsche-die-zweite, p.124
Laufzeit: $T (n) = 4 \cdot T (\frac{n}{2}) + c n$
!introprog-v12-teile-herrsche-die-zweite, p.146

verbessertes Teile und Herrsche

!introprog-v12-teile-herrsche-die-zweite, p.149
$(a + B) (C + D) - A C - B D = B C + A D$
Laufzeit: $3 T (\frac{n}{2}) + c n$
!introprog-v12-teile-herrsche-die-zweite, p.179
Laufzeitgewinn

Laufzeit	10	100	1.000
$n^{2}$	100	10.000	1.000.000
$n^{1, 59}$	39	1.514	58.885
Faktor	2,56	6,6	17
![[introprog-v12-teile-herrsche-die-zweite.pdf#page=180&rect=349,51,688,321	introprog-v12-teile-herrsche-die-zweite, p.180]]

divide & conquer

Mastertheorem

Basics

Rekursionsgleichung

binäre Suche

Prinzip:

vereinfachte binäre Suche mit Annahme b ist im Feld A

Prinzip:

Algorithmus:

beweis

Laufzeit

Rekursionsgleichung: T(n)=1⋅T(n2)+c

Binäre Suche ohne Annahme

Algorithmus

binäre Suche vs. lineare Suche

Integer Multiplikation

Schulmethode (binär)

mit Teile & Herrschen

Einfaches Teile und Herrsche

verbessertes Teile und Herrsche

Rekursionsgleichung: $T (n) = 1 \cdot T (\frac{n}{2}) + c$