Рассмотрим простую проблему, которая может быть решена с помощью техники «разделяй и властвуй».
Постановка задачи
Задача Макс-Мин в анализе алгоритма — найти максимальное и минимальное значение в массиве.
Решение
Чтобы найти максимальное и минимальное число в данном массиве номеров [] размера 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) .