DAA-最大-最小問題
分割統治法で解決できる簡単な問題を考えてみましょう。
問題文
アルゴリズム分析の最大値と最小値の問題は、配列の最大値と最小値を見つけることです。
解決
特定の配列の最大数と最小数を見つけるには numbers[] サイズの n、次のアルゴリズムを使用できます。まず、私たちはnaive method そして、私たちは提示します divide and conquer approach。
ナイーブな方法
ナイーブな方法は、あらゆる問題を解決するための基本的な方法です。この方法では、最大数と最小数を別々に見つけることができます。最大数と最小数を見つけるには、次の簡単なアルゴリズムを使用できます。
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)
分析
ナイーブ法での比較数は 2n - 2。
分割統治法を使用すると、比較の数を減らすことができます。以下はそのテクニックです。
分割統治法
このアプローチでは、アレイは2つに分割されます。次に、再帰的アプローチを使用して、各半分の最大数と最小数を見つけます。後で、各半分の最大2つの最大値と各半分の最小2つの最小値を返します。
この特定の問題では、配列内の要素の数は$ y-x + 1 $です。ここで、 y 以上 x。
$ \ mathbf {\ mathit {Max --Min(x、y)}} $は、配列$ \ mathbf {\ mathit {numbers [x ... y]}} $の最大値と最小値を返します。
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))
分析
しましょう T(n) $ \ mathbf {\ mathit {Max --Min(x、y)}} $によって行われた比較の数です。ここで、要素の数$ n = y-x + 1 $です。
場合 T(n) 数を表す場合、漸化式は次のように表すことができます。
$$ T(n)= \ begin {cases} T \ left(\ lfloor \ frac {n} {2} \ rfloor \ right)+ T \ left(\ lceil \ frac {n} {2} \ rceil \ right )+ 2&for \:n> 2 \\ 1&for \:n = 2 \\ 0&for \:n = 1 \ end {cases} $$
それを仮定しましょう n の力の形である 2。したがって、n = 2k どこ k は再帰ツリーの高さです。
そう、
$$ 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 $$
ナイーブ法と比較して、分割統治法では、比較の数が少なくなります。ただし、漸近表記を使用すると、両方のアプローチは次のように表されます。O(n)。