Раскрутка рекуррентности в алгоритме сортировки слиянием
Рис. 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.
Еще по теме Раскрутка рекуррентности в алгоритме сортировки слиянием:
- Слияние с Гуру
- 5) Слияние с Мастером
- Статья 106. Слияние, присоединение, деление и преобразование юридического лица
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Алгоритм исцеления:
- Статья 107. Порядок прекращения юридического лица путем слияния, присоединение, деления и преобразования
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.