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

Принцип разделяй и властвуй на примере сортировки слиянием.

Оглавление

• Алгоритмы и структуры данных.
  • Теория.
    • Определения.
    • Разделяй и властвуй.
    • Методы оценки времени работы рекуррентных соотношений.
    • Доказательство основной теоремы о рекуррентных оценках.
    • Двоичная куча и сортировка с её помощью.
  • Практика.
    • Сравнение времени работы различных алгоритмов сортировки.

По мере реализации пункты оглавления будут заменяться на ссылки.

Введение

Многие алгоритмы допускают рекурсивную реализацию: для решения возникающих подзадач они снова вызывают себя же. Такой подход лежит в основе принципа разделяй и властвуй. Согласно ему задача разбивается на подзадачи, которые затем либо решаются рекурсивно, либо явно, если они достаточно просты. Далее комбинируя их решения можно получить решение исходной задачи. В задачах сортировки примером такого алгоритма является сортировка слиянием.

Сортировка слиянием

Сортировка слиянием проходит в 3 этапа: сначала исходный массив делится на 2 массива меньшего размера, затем каждый из них сортируется рекурсивно. После этого отсортированные массивы сливаются в общий массив. Процесс разбиения массивов продолжается, пока размер подмассива не дойдёт до единицы, так как любой массив с единственным элементом является отсортированным.

Слияние массивов будем производить следующим образом: оба сливаемых подмассива являются отсортированными по возрастанию, следовательно наименьший элемент находится в самом начале одного из них. Этот наименьший элемент помещается в общий массив, при этом один из массивов становится короче на один элемент. Продолжая этот процесс, мы поместим все элементы исходных массивов в общий массив в порядке возрастания.

Оценим сложность по времени операции слияния. Пусть $$A$$ - исходный массив, $$p, q, r$$ - границы рассматриваемых участков. Процедура Merge(A,p,q,r) предполагает, что $$p \leqslant q < r$$, а участки A[p..q], A[q+1..r] отсортированы в порядке возрастания. В ходе работы процедуры производится $$n=r-p+1$$ сравнений, следовательно время работы процедуры Merge составляет $$\Theta(n).$$

Таким образом сортировку слиянием можно записать при помощи следующего псевдокода:

MergeSort(A,p,r)
    if p < r
        then q = [(p+r)/2]
            MergeSort(A,p,q)
            MergeSort(A,q+1,r)
            Merge(A,p,q,r)

где [x] - целая часть x.

Для сортировки исходного массива $$A$$ достаточно выполнить процедуру MergeSort(A, 1, length(A)).

Продемонстрируем пример работы сортировки слиянием:

Время работы алгоритмов разделяй и властвуй

Пусть алгоритм разбивает задачу размера $$n$$ на $$a$$ подзадач, каждая из которых в $$b$$ раз меньше по размеру. Пусть разбиение на подзадачу требует $$D(n)$$ времени, а последующее слияние занимает $$C(n)$$. Тогда в худшем случае время работы алгоритма составит $$T(n)=a * T(n/b) + D(n) + C(n).$$

Отметим, что применять принцип разделяй и властвуй имеет смысл для достаточно больших n. В случае если n мало, как правило применяется прямой метод решения задачи.

Попробуем теперь оценить время работы сортировки слияния. Для простоты положим, что размер сортируемого массива является степенью двойки. На каждом шаге сортируемая часть массива делится на две равные половины. Разбиение на части занимает константное время $$\Theta(1),$$ а последующее слияние занимает $$\Theta(n),$$ т.е.

$$ T(n) = \begin{cases} \Theta(1) &\text{if } n=1, \
2T(n/2) + \Theta(n) &\text{if } n>1. \end{cases} $$

Эту оценку можно уточнить при помощи основной теоремы о рекуррентных оценках:

Теорема. Пусть $$a \geqslant 1$$, $$b>1$$ - константы, $$f(n)$$ - функция, $$T(n)$$ определяется следующей формулой:

Тогда:

1. если $$f(n)=O(n^{\log_b{a}-\epsilon})$$ для некоторого $$\epsilon >0,$$ то $$T(n)=\Theta(n^{\log_b a});$$
2. если $$f(n)=\Theta(n^{\log_b{a}})$$ для некоторого $$\epsilon >0,$$ то $$T(n)=\Theta(n^{\log_b a}\log{n});$$
3. если $$f(n)=\Omega(n^{\log_b{a}+\epsilon})$$ для некоторого $$\epsilon >0$$ и если $$a f(n/b) \leqslant c f(n)$$ для некоторой константы $$c<1$$ и достаточно больших $$n,$$ то $$T(n)=\Theta(f(n)).$$

Согласно этой теореме получаем, что ассимптотическая оценка времени работы сортировки слиянием составляет $$\Theta(n\log{n}),$$ так как для неё $$f(n)=\Theta(n),$$ $$a=b=2.$$

Литература

1. Т. Кормен. Алгоритмы. Построение и анализ. – М.: МЦНМО, 2001. — 26-28, 66-67 c.
2. С. Скиена. Алгоритмы. Руководство по разработке. 2-е издание. – СПб.: БХВ-Петербург, 2016. — 141-143 c.