Случай одной подзадачи
Для начала попробуем построить решение методом раскрутки рекуррентного отношения.
♦ Анализ нескольких начальных уровней: начальные уровни рекурсии изображены на рис. 5.3. На первом уровне рекурсии имеется одна задача с размером n, кото- рая выполняется за время cn плюс время, потраченное на все последующие ре- курсивные вызовы. На следующем уровне имеется одна задача с размером n/2, которая вносит вклад cn/2; далее идет уровень с одной задачей с размером n/4, добавляющая время cn/4. Как видите, в отличие от предыдущего случая общий объем работы при q = 1 сокращается с ростом уровня рекурсии.
♦
Выявление закономерности: на произвольном уровне j по-прежнему остается одна подзадача с размером n/2j.
Ее вклад в общее время выполнения состав- ляет cn/2 j.♦
Суммирование по всем уровням рекурсии: рекурсия имеет log2 n уровней, а общий объем выполняемой работы определяется следующей суммой:
Эта геометрическая сумма очень легко вычисляется; даже если продолжить ее до бесконечности, она будет стремиться к 2. Следовательно, выполняется от- ношение
Подведем итог:
(5.5) Любая функция T(∙), удовлетворяющая условию (5.3) с q = 1, имеет гра- ницу O(n).
На первый взгляд этот результат выглядит противоестественно. Алгоритм вы- полняет log n уровней рекурсии, но общее время выполнения остается линейным по n. Суть в том, что геометрическая прогрессия с убывающей экспонентой весьма эффективна: половина работы, выполняемой алгоритмом, выполняется на верхнем уровне рекурсии.
Также стоит заметить, что частичная подстановка в рекурсии очень хорошо работает в данном случае. Предположим, как и ранее, что решение задается в фор-
ме T(n) < knd. Попробуем установить это посредством индукции с использованием (5.3), предполагая, что решение работает для меньшего значения n/2:
Если теперь просто выбрать d = 1 и к = 2c, получаем
с завершением индукции.
Еще по теме Случай одной подзадачи:
- История одной паники
- Из ответа Д.С. одной маме
- Вот пример одной из жидких диет.
- Об одной любопытной черте характера русских
- 2. Не делать более одной вещи одновременно
- Об одной интересной черте характера тюрков
- 5. Изменение и расторжение договора в судебном порядке по требованию одной из сторон
- История одной мистификации, или Рассказы Саши Лебедева
- ДОБРО И ЗЛО: ОБРАТНЫЕ СТОРОНЫ ОДНОЙ И ТОЙ ЖЕ МОНЕТЫ.
- С ОДНОЙ СТОРОНЫ - ВЫРАЖЕНИЕ ЧУВСТВ, С ДРУГОЙ - ПЕРЕДАЧА ИНФОРМАЦИИ
- 11. Сделки, совершенные в результате злонамеренного соглашения представителя одной стороны с другой