DAA - проблема Макс-Мин

Рассмотрим простую проблему, которая может быть решена с помощью техники «разделяй и властвуй».

Постановка задачи

Задачей Макс-Мин в анализе алгоритма является поиск максимального и минимального значения в массиве.

Решение

Чтобы найти максимальное и минимальное числа в данном массиве номеров [] размера n , можно использовать следующий алгоритм. Сначала мы представляем наивный метод, а затем представим подход «разделяй и властвуй» .

Наивный метод

Наивный метод является основным методом решения любой проблемы. В этом методе максимальное и минимальное количество можно найти отдельно. Чтобы найти максимальное и минимальное число, можно использовать следующий простой алгоритм.

 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 .

Количество сравнений можно уменьшить, используя подход «разделяй и властвуй». Ниже приводится методика.

Разделяй и властвуй

При таком подходе массив делится на две половины. Затем с помощью рекурсивного подхода определяются максимальные и минимальные числа в каждой половине. Позже верните максимум двух максимумов каждой половины и минимум двух минимумов каждой половины.

В данной задаче число элементов в массиве равно $ 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 {case} T \ left (\ lfloor \ frac {n} {2} \ rfloor \ right) + T \ left (\ lceil \ frac {n} {2} \ rceil \ right ) +2 & для \: n> 2 \\ 1 & для \: n = 2 \\ 0 & для \: n = 1 \ end {case} $$

Предположим, что n имеет вид степени 2 . Следовательно, n = 2 k, где 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) .