Использование частичной подстановки
Предположим, вы считаете, что T(n) = O(n log n), но не уверены в константе в обозначении O(·).
Метод подстановки может использоваться даже без точного значения этой константы. Сначала записываем T(n) < кn logb n для некоторой кон- станты к и основания b, которые будут определены позднее.(Вообще говоря, основание и константа связаны друг с другом, так как основа- ние логарифма можно изменить простым умножением на константу, — см. главу 2.)
Теперь хотелось бы знать, существуют ли значения к и b, которые будут рабо- тать в индукции. Для начала проверим один уровень индукции.
Появляется естественная мысль выбрать для логарифма основание b = 2, по- скольку мы видим, что это позволит применить упрощение log2(n/2) = (log2 n) - 1. Продолжая с выбранным значением получаем
Наконец, спросим себя: можно ли подобрать значение к, при котором последнее выражение будет ограничиваться кп log2 n? Очевидно, что ответ на этот вопрос по- ложителен; просто нужно выбрать любое значение к, не меньшее с, и мы получаем
Индукция завершена.
Итак, метод подстановки может пригодиться для определения точных значе- ний констант, если у вас уже имеется некоторое представление об общей форме решения.
5.2.
Еще по теме Использование частичной подстановки:
- Неполная (частичная) дееспособность
- Раздел III Использование достижений криминалистической психологии при собирании, оценке, использовании личностной информации
- 1. Понятие и виды неполной (частичной) дееспособности несовершеннолетних
- 2. Ограничение неполной (частичной) дееспособности несовершеннолетних
- МЕТОДИКА ВОСПРОИЗВЕДЕНИЯ ЧАСТИЧНОГО
- Примеры частично скрытого паразитизма:
- 2. Неполная (частичная) дееспособность несовершеннолетних в возрасте от 14 до 18 лет
- Правило частичного согласияс возражениями оппонента.
- Правило частичного согласия с возражениями оппонента.
- 3. Частичная дееспособность малолетних (несовершеннолетних в возрасте от 6 до 14 лет)