Случай одной подзадачи

Рассмотрим случай q = 1 в (5.3), который хорошо демонстрирует еще одну раз- новидность алгоритма. Хотя в этой главе пример применения рекуррентности для q = 1 не встречается, он будет представлен в главе 13, как упоминалось ранее.

Для начала попробуем построить решение методом раскрутки рекуррентного отношения.

♦ Анализ нескольких начальных уровней: начальные уровни рекурсии изображены на рис. 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, получаем

с завершением индукции.

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

Еще по теме Случай одной подзадачи:

  1. История одной паники
  2. Из ответа Д.С. одной маме
  3. ВООРУЖИТЕСЬ ОДНОЙ ВЕЛИКОЙ ИСТИНОЙ
  4. Придерживайтесь одной линии мышления
  5. Вот пример одной из жидких диет.
  6. Об одной любопытной черте характера русских
  7. 2. Не делать более одной вещи одновременно
  8. Об одной интересной черте характера тюрков
  9. 5. Изменение и расторжение договора в судебном порядке по требованию одной из сторон
  10. История одной мистификации, или Рассказы Саши Лебедева
  11. ДОБРО И ЗЛО: ОБРАТНЫЕ СТОРОНЫ ОДНОЙ И ТОЙ ЖЕ МОНЕТЫ.