Использование частичной подстановки

Также существует более слабый вид подстановки, в котором предполагается общая форма решения без точных значений всех констант и других параметров.

Предположим, вы считаете, что 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.

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

Еще по теме Использование частичной подстановки:

  1. Неполная (частичная) дееспособность
  2. Раздел III Использование достижений криминалистической психологии при собирании, оценке, использовании личностной информации
  3. 1. Понятие и виды неполной (частичной) дееспособности несовершеннолетних
  4. 2. Ограничение неполной (частичной) дееспособности несовершеннолетних
  5. МЕТОДИКА ВОСПРОИЗВЕДЕНИЯ ЧАСТИЧНОГО
  6. Примеры частично скрытого паразитизма:
  7. 2. Неполная (частичная) дееспособность несовершеннолетних в возрасте от 14 до 18 лет
  8. Правило частичного согласияс возражениями оппонента.
  9. Правило частичного согласия с возражениями оппонента.
  10. 3. Частичная дееспособность малолетних (несовершеннолетних в возрасте от 6 до 14 лет)