Методы разрешения рекуррентности

Существуют два основных подхода к разрешению рекуррентности.

Самый естественный и понятный подход к поиску решения — «раскрутка» ре- курсии с отслеживанием времени выполнения на нескольких начальных уровнях и выявлением закономерности, которая сохраняется в ходе рекурсии.

Затем время выполнения суммируется по всем уровням рекурсии (то есть до достижения ниж- него предела для подзадач постоянного размера) с получением общего времени выполнения.

Во втором варианте строится гипотеза, которая подставляется в рекуррентное отношение и проверяется на жизнеспособность. Для формальной проверки таких подстановок используется индукция по n. Существует полезная разновидность этого метода, в которой известна общая форма решения, но неизвестны точные зна- чения всех параметров. Оставляя эти параметры неопределенными в подстановке, часто удается подобрать их по мере необходимости.

А теперь мы обсудим каждый из этих методов на примере рекуррентного от- ношения (5.1).

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

Еще по теме Методы разрешения рекуррентности:

  1. Разрешение
  2. 2.2. Разрешение на добычу полезных ископаемых
  3. Разрешение конфликтов
  4. 10.2. Разрешение социальных конфликтов
  5. § 4. Динамика и разрешение юридического конфликта
  6. Разрешение конфликта и его последствия.
  7. Разрешение проблем
  8. 14.7. Трудовые споры и порядок их разрешения
  9. § 3. Порядок рассмотрения и разрешения дела
  10. ГЛАВА XVII. РАЗРЕШЕНИЕ ЭКОНОМИЧЕСКИХ СПОРОВ ТРЕТЕЙСКИМИ СУДАМИ
  11. Экспертное разрешение психологических вопросов
  12. Статья 71. Сделки, которые совершаются с разрешения органа опеки и попечительства
  13. § 3. РАЗРЕШЕНИЕ ПРОТИВОРЕЧИЙ В ПРОЦЕССЕ ПРИМЕНЕНИЯ СОЦИАЛЬНОЙ ТЕОРИИ
  14. ПОНЯТИЕ О МЕТОДАХ ОБУЧЕНИЯ. МЕТОД И ПРИЕМ. ОСНОВНЫЕ ПОДХОДЫ К КЛАССИФИКАЦИИ МЕТОДОВ ОБУЧЕНИЯ
  15. Ключ мог родиться только в России. Ключ к себе — ключ к системам. (это не метод среди методов, а Ключ к собственному методу)
  16. 6. Ребенок проходит многие ступени своей социализации через разрешение противоречий в среде своих сверстников
  17. 2. Сравнительно-правовой метод – частнонаучный метод юридической науки
  18. Статья 224. Правовые последствия совершения правового действия без разрешения органа опеки и попечительства