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

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

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

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

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

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

(5.1) Для некоторой константы с,

T(2) < с.

Структура (5.1) типична для рекуррентных отношений: имеется неравенство или равенство, ограничивающее T(n) в выражении, использующем T(k) для мень- ших значений к, и существует базовый случай, который фактически сообщает, что T(n) является константой для константы n.

Также заметьте, что (5.1) можно записать неформально в виде T(n) < 2T(n/2) + O(n), исключив константу с. Тем не менее явное включение с обычно бывает полезно при анализе рекуррентных отношений.

Чтобы упростить описание, мы будем считать, что параметры (такие, как n) чет- ные. Такое предположение создает некоторую неточность; без него два рекурсивных вызова будут применяться к задачам размера j л/Э|, а рекуррентное отношение должно иметь вид


для n > 2. Однако для всех рекуррентных отношений, которые мы будем рассма- тривать (и которые встречаются на практике), игнорирование верхней или нижней границы чисел обычно не влияет на асимптотические границы, а формулы заметно упрощаются.

Учтите, что (5.1) не дает явной асимптотической границы для скорости роста функции T, скорее T(n) задается неявно в контексте его значений для входных данных меньшего размера. Для получения явной границы необходимо разрешить рекуррентное отношение так, чтобы обозначения T присутствовали только в левой части неравенства.

Задача разрешения рекуррентности была встроена в некоторые стандартные компьютерные алгебраические системы, а многие стандартные рекуррентные от- ношения успешно разрешаются автоматизированными средствами. Тем не менее будет полезно разобраться в процессе разрешения рекуррентности и научиться распознавать рекуррентные отношения, приводящие к хорошему времени вы- полнения, — разработка эффективных алгоритмов «разделяй и властвуй» тесно связана с пониманием того, как рекуррентное отношение определяет время вы- полнения.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Слияние с Гуру
  2. 5) Слияние с Мастером
  3. Статья 106. Слияние, присоединение, деление и преобразование юридического лица
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ УДАЧИ
  6. АЛГОРИТМ
  7. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  8. Алгоритм исцеления:
  9. Статья 107. Порядок прекращения юридического лица путем слияния, присоединение, деления и преобразования
  10. Алгоритм избавления от боли
  11. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  12. Алгоритм обработки результатов.
  13. 2. Специфика и алгоритмы работы с источниками.
  14. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  15. § 4 Законные условия для вступления в брак. – Первое условие – свободное сознание сторон. – Понятие о принуждении. – Обычай женить и выдавать замуж в семье и в отношениях вотчинной власти. – Право государства принуждать к браку. – Историческое значение авторизации к браку. – Требование родительского согласия по иностранным законодательствам. – Ограничение свободы в браке со стороны государства и общины. – Постановления русского закона. – Хозяйственное значение брака в крестьянском быту и его пос
  16. Упражнение первое
  17. Сефера: Крайон, для чего все эти существа прибыли вместе с нами из Атлантиды? Для чего слияние рас прошлого и настоящего (или будущего)?
  18. Упражнение двадцать первое
  19. 1. Вычислим первое число.