5.3.4. Алгоритм сортировки Merge Sort.

Если алгоритм рекурсивно обращается к самому себе, время его работы часто описывается с помощью рекуррентного уравнения, илирекуррентного соотно­шения, в котором полное время, требуемое для решения всей задачи с объемом вводап, выражается через время решения вспомогательных подзадач. Затем дан­ное рекуррентное уравнение решается с помощью определенных математических методов, и устанавливаются границы производительности алгоритма.

Получение рекуррентного соотношения для времени работы алгоритма, осно­ванного на принципе "разделяй и властвуй", базируется на трех этапах, соответ­ствующих парадигме этого принципа. Обозначим через Т (п) время решения зада­чи, размер которой равенп. Если размер задачи достаточно мал, скажем,п с, где с — некоторая заранее известная константа, то задача решается непосредственно в течение определенного фиксированного времени, которое мы обозначим через(1). Предположим, что наша задача делится наа подзадач, объем каждой из которых равен 1/bот объема исходной задачи. (В алгоритме сортировки мето­дом слияния числаа и b были равны 2, однако нам предстоит ознакомиться со многими алгоритмами разбиения, в которыха b.) Если разбиение задачи на вспомогательные подзадачи происходит в течение времениD (n), а объединение решений подзадач в решение исходной задачи — в течение времени С (n), то мы получим такое рекуррентное соотношение:

(5.4)

Приведем теорему (без доказательства), с помощью которой можно показать, что величина Т (n) представляет собой (n lg n), где lg n обозначает log₂ n.

Посколь­ку логарифмическая функция растет медленнее, чем линейная, то для достаточно большого количества входных элементов производительность алгоритма сорти­ровки методом слияния, время работы которого равно (nlgn), превзойдет про­изводительность алгоритма сортировки методом вставок, время работы которого в наихудшем случае равно (п²).

Теорема 5.1 (Основная теорема). Пусть а 1 иb > 1 - константы, f(n) — произвольная функция, а Т (n) — функция, определенная на множестве неотри­цательных целых чисел с помощью рекуррентного соотношения

T(n)=аТ(n/b) +f(n), (5.5)

где выражение п/b интерпретируется либо как , либо как. Тогда асимп­тотическое поведение функции Т (n) можно выразить следующим образом.

1. Если f(n) =О () для некоторой константы > 0, то

.

2. Если , то

3. Если для некоторой константы > 0, и если для некоторой константы с < 1 и всех достаточно боль­шихn, тоТ (п) =

Правда, можно и без упомянутой теоремы интуитивно понять, что решением рекуррентного соотношения () является выражение Т(п) = 0(nlgn). Пере­пишем уравнение () в таком виде:

(5.6)

где константа с обозначает время, которое требуется для решения задачи, раз­мер который равен 1, а также удельное (приходящееся на один элемент) время, требуемое для разделения и сочетания.

Оценим быстродействие алгоритма: время работы определяется рекурсивной формулой T(n) = 2T(n/2) + Θ(n). Ее решение: T(n) = n log n - результат весьма неплох, учитывая отсутствие "худшего случая". Однако, несмотря на хорошее общее быстродействие, у сортировки слиянием есть и серьезный минус: она требует Θ(n) памяти. Хорошо запрограммированная внутренняя сортировка слиянием работает немного быстрее пирамидальной, но медленнее быстрой, при этом требуя много памяти под буфер. Поэтому mergeSort используют для упорядочения массивов, лишь если требуется устойчивость метода(которой нет ни у быстрой, ни у пирамидальной сортировок).

Процесс решения рекуррентного соотношения () проиллюстрирован на рис. 5.3. Для удобства предположено, чтоnравно степени двойки.

Рис.5.6. Построение дерева рекурсии для уравнения T(n)=2T(n/2) +cn.