Design-and-analysis-of-algorithms-max-min-problem

DAA-最大最小問題

分割統治法によって解決できる単純な問題を考えてみましょう。

問題文

アルゴリズム分析の最大最小問題は、配列の最大値と最小値を見つけることです。

溶液

サイズ n の特定の配列 _numbers [] _ の最大数と最小数を見つけるには、次のアルゴリズムを使用できます。 最初に*単純なメソッド*を表し、次に*分割して征服するアプローチ*を提示します。

ナイーブ法

ナイーブ法は、問題を解決するための基本的な方法です。 この方法では、最大数と最小数を別々に見つけることができます。 最大数と最小数を見つけるには、次の簡単なアルゴリズムを使用できます。

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)

分析

Naiveメソッドの比較数は 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 = 2 ^ k ^* で、 *k* は再帰木の高さです。

So,

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）*で表されます。