DAA - Max-Min-Problem
Betrachten wir ein einfaches Problem, das durch Teilen und Erobern gelöst werden kann.
Problemstellung
Das Max-Min-Problem bei der Algorithmusanalyse besteht darin, den Maximal- und Minimalwert in einem Array zu ermitteln.
Lösung
Um die maximale und minimale Anzahl in einem bestimmten Array zu finden numbers[] von Größe nkann der folgende Algorithmus verwendet werden. Zuerst vertreten wir dienaive method und dann werden wir präsentieren divide and conquer approach.
Naive Methode
Die naive Methode ist eine grundlegende Methode, um jedes Problem zu lösen. Bei dieser Methode können die maximale und minimale Anzahl getrennt ermittelt werden. Um die maximale und minimale Anzahl zu finden, kann der folgende einfache Algorithmus verwendet werden.
Algorithm: Max-Min-Element (numbers[])
max := numbers[1]
min := numbers[1]
for i = 2 to n do
if numbers[i] > max then
max := numbers[i]
if numbers[i] < min then
min := numbers[i]
return (max, min)Analyse
Die Anzahl der Vergleiche in der naiven Methode ist 2n - 2.
Die Anzahl der Vergleiche kann mithilfe des Divide and Conquer-Ansatzes reduziert werden. Es folgt die Technik.
Ansatz teilen und erobern
Bei diesem Ansatz wird das Array in zwei Hälften geteilt. Dann werden unter Verwendung des rekursiven Ansatzes maximale und minimale Zahlen in jeder Hälfte gefunden. Geben Sie später das Maximum von zwei Maxima jeder Hälfte und das Minimum von zwei Minima jeder Hälfte zurück.
In diesem gegebenen Problem beträgt die Anzahl der Elemente in einem Array $ y - x + 1 $, wobei y ist größer oder gleich x.
$ \ mathbf {\ mathit {Max - Min (x, y)}} $ gibt die Maximal- und Minimalwerte eines Arrays $ \ mathbf {\ mathit {numbers [x ... y]}} $ zurück.
Algorithm: Max - Min(x, y)
if y – x ≤ 1 then
return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y]))
else
(max1, min1):= maxmin(x, ⌊((x + y)/2)⌋)
(max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y)
return (max(max1, max2), min(min1, min2))Analyse
Lassen T(n) sei die Anzahl der Vergleiche von $ \ mathbf {\ mathit {Max - Min (x, y)}} $, wobei die Anzahl der Elemente $ n = y - x + 1 $.
Wenn T(n) stellt die Zahlen dar, dann kann die Wiederholungsrelation dargestellt werden als
$$ T (n) = \ begin {Fälle} T \ left (\ lfloor \ frac {n} {2} \ rfloor \ right) + T \ left (\ lceil \ frac {n} {2} \ rceil \ right ) +2 & für \: n> 2 \\ 1 & für \: n = 2 \\ 0 & für \: n = 1 \ end {case} $$
Nehmen wir das an n ist in Form von Macht von 2. Daher,n = 2k wo k ist die Höhe des Rekursionsbaums.
Damit,
$$ T (n) = 2.T (\ frac {n} {2}) + 2 = 2. \ left (\ begin {array} {c} 2.T (\ frac {n} {4}) + 2 \ end {array} \ right) + 2 ..... = \ frac {3n} {2} - 2 $$
Im Vergleich zur naiven Methode ist beim Divide and Conquer-Ansatz die Anzahl der Vergleiche geringer. Unter Verwendung der asymptotischen Notation werden jedoch beide Ansätze durch dargestelltO(n).