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)