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

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

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

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

Решение

Чтобы найти максимальное и минимальное числа в заданном массиве 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.

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

Подход разделяй и властвуй

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

В данной задаче количество элементов в массиве равно $ 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 & для \: 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).