Другие рекуррентные отношения
В предыдущем разделе в ходе решения задачи было получено рекуррентное отношение (5.1), которое еще встретится при разработки нескольких алгоритмов типа «разделяй и властвуй» позднее в этой главе.
Для дальнейшего исследования этой темы рассмотрим класс рекуррентных отношений, который обобщает (5.1), и посмотрим, как разрешаются рекуррентности из этого класса. Другие представители класса еще встретятся при разработке алгоритмов и в этой, и в последующих главах.
Случай q > 2 встретится позднее в этой главе, когда мы займемся разработкой алгоритмов для целочисленного умножения; разновидность с q = 1 будет представлена позднее, когда мы будем разрабатывать рандомизированный алгоритм нахождения медианы в главе 13.
Если T(n) обозначает время выполнения алгоритма, построенного по такому принципу, то T(n) подчиняется следующему рекуррентному отношению, которое напрямую обобщает (5.1) с заменой 2 на q:
(5.3) Для некоторой константы c, для n>2, и T(n) ≤ qT(n/2) + cn T(2) ≤ c
В следующем разделе описано, как решить (5.3) с использованием уже применявшихся методов: раскрутки, подстановки и частичной подстановки. Случаи q > 2 и q = 1 рассматриваются по отдельности, так как они качественно отличаются друг от друга, а также от случая q = 2.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу