Первое рекуррентное отношение: алгоритм сортировки слиянием

Чтобы понять общий подход к анализу алгоритмов «разделяй и властвуй», начнем с алгоритма сортировки слиянием.

Алгоритм сортировки слиянием сортирует список чисел: сначала список делится на две половины, каждая половина рекурсивно сортируется по отдельности, после чего результаты рекурсивных вызовов (в форме двух отсортированных половин) объединяются алгоритмом слияния отсортированных списков.

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

(†) Разбить входные данные на два блока равного размера; рекурсивно решить две подзадачи для этих блоков по отдельности; объединить два результата в одно решение, с линейными затратами времени для исходного деления и итогового объединения.

В алгоритме сортировки слиянием, как и в любом алгоритме этого типа, также необходим базовый случай рекурсии, который обычно завершает выполнение для входных данных некоторого постоянного размера.

В случае сортировки слиянием предполагается, что при достижении размера 2 рекурсия останавливается, а два элемента сортируются простым сравнением.

Рассмотрим любой алгоритм, построенный по шаблону (†); обозначим T(n) худ- шее время выполнения для входных данных с размером n.

Если предположить, что n четно, алгоритм за время O(n) делит входные данные на два блока с размером n/2, а затем тратит время T(n/2) на решение каждой производной задачи (T(n/2) — худшее время выполнения для входных данных с размером n/2); и наконец, время O(n) тратится на объединение решений из двух рекурсивных вызовов.

Это время выполнения T(n) удовлетворяет следующему рекуррентному отношению.

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)