Учебники

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

Июль 31, 2018

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

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

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

Решение

Чтобы найти максимальное и минимальное число в данном массиве номеров [] размера 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 mathitMax−Min(x,y) вернет максимальное и минимальное значения массива  mathbf mathitnumbers[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 mathitMax−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( fracn2)+2=2. left( beginarrayc2.T( fracn4)+2 endarray right)+2.....= frac3n2−2

По сравнению с наивным методом, в подходе «разделяй и властвуй», количество сравнений меньше. Однако, используя асимптотические обозначения, оба подхода представлены O (n) .

42
Share: