Использование частичной подстановки
Также существует более слабый вид подстановки, в котором предполагается общая форма решения без точных значений всех констант и других параметров.
Сначала записываем T(n) ≤ kn logb n для некоторой константы k и основания b, которые будут определены позднее.
Теперь хотелось бы знать, существуют ли значения k и b, которые будут работать в индукции. Для начала проверим один уровень индукции.
T(n) ≤ 2T(n/2) + cn ≤ 2k(n/2) logb(n/2) + cn
Появляется естественная мысль выбрать для логарифма основание b = 2, поскольку мы видим, что это позволит применить упрощение log2(n/2) = (log2 n) − 1. Продолжая с выбранным значением, получаем
T(n) ≤ 2k(n/2) log2(n/2) + cn
= 2k(n/2)[(log2 n) − 1] + cn
= kn[(log2 n) − 1] + cn
= (kn log2 n) − kn + cn.
Наконец, спросим себя: можно ли подобрать значение k, при котором последнее выражение будет ограничиваться kn log2 n? Очевидно, что ответ на этот вопрос положителен; просто нужно выбрать любое значение k, не меньшее c, и мы получаем T(n) ≤ (kn log2 n) − kn + cn ≤ kn log2 n.
Индукция завершена.
Итак, метод подстановки может пригодиться для определения точных значений констант, если у вас уже имеется некоторое представление об общей форме решения.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу