Частичная подстановка

Появление log2 q в показателе степени естественно следовало из решения (5.3), но такое выражение далеко не всегда можно предположить в исходной ситуации. Посмотрим, как подход, основанный на частичной подстановке, позволяет обна- ружить эту экспоненту другим способом.

Допустим, мы предполагаем, что решение (5.3) при q > 2 имеет фор- му T(n) < knd для некоторых констант к > 0 и d > 1. Это достаточно общее предпо- ложение, так как мы даже не пытаемся задать показатель степени d. Теперь начнем рассуждения методом индукции и посмотрим, какие ограничения потребуются для к и d. Имеем


Результат получился поразительно близким: если выбрать d так, чтобы q/2d = 1, то получится T(n) < knd + cn — почти то, что требуется, не считая лишнего члена cn. Итак, нужно разобраться с двумя проблемами: как выбрать d, чтобы q/2d = 1, и как избавиться от cn.

С выбором d все просто: нужно, чтобы 2d = q, поэтому d = log2 q. Как видите, показатель степени log2 q совершенно естественно появляется, когда мы решаем определить, какое значение d будет работать при подстановке в рекуррентное от- ношение.


Но еще нужно избавиться от члена cn. Для этого мы изменим форму предполо- жения для T(n) так, чтобы явно устранить его вычитанием. Попробуем проверить форму Г(я)
<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Частичная подстановка:

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