Раскрутка рекуррентности в алгоритме сортировки слиянием

Начнем с первого способа разрешения рекуррентности в (5.1). Основная идея представлена на рис. 5.1.

Рис.

5.1. Раскрутка рекуррентности T(n) < 2T(n/2) + O(n)

♦ Анализ нескольких начальных уровней: на первом уровне рекурсии имеется одна задача с размером n, которая выполняется за время cn плюс время, потраченное на все последующие рекурсивные вызовы. На следующем уровне имеются две задачи с размером n/2. Каждая задача выполняется за время максимум cn/2, что дает в сумме cn плюс время последующих рекурсивных вызовов. На третьем уровне используются четыре задачи с размером n/4, каждая выполняется за время cn/4, итого максимум cn.

♦ Выявление закономерности: что вообще происходит? На уровне j рекурсии количество подзадач удваивается j раз и поэтому равно 2j. Каждая задача соот- ветственно уменьшается вдвое j раз; следовательно, размер каждой подзадачи равен n/2 , и она выполняется за время максимум сn/2j. Таким образом, вклад уровня j в общее время выполнения составляет максимум 2 (cn/2 ) = cn.

♦ Суммирование по всем уровням рекурсии: выясняется, что у рекурсии из (5.1) общий объем работы, выполняемой на каждом уровне, имеет одну и ту же верхнюю границу cn. Количество делений входных данных для сокращения их размера с n до 2 составляет log2 n. Суммируя объем работы cn по log n уровням рекурсии, получаем общее время выполнения O(n log n).

Следующее утверждение подводит итог анализа.

(5.2) Любая функция T(·), удовлетворяющая условию (5.1), имеет границу O(n log n) при n > 1.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.