Решение отношения рецидива $ t (n) = 2t ( lfloor n/2 rfloor) + n $

Question

Решение отношения рецидива $ t (n) = 2t ( lfloor n/2 rfloor) + n $.
Книга, из которой этот пример, ложно утверждает, что $ t (n) = O (n) $, угадая $ t (n) leq cn $, а затем спорить

$ qquad begin {align*} t (n) & leq 2 (c lfloor n/2 rfloor) + n & leq cn + n & = o (n) Quad Quad Quad longleftarrow text {неверно !!} end {align*} $

Поскольку $ C $ является постоянной. Ошибка в том, что мы не доказали точный форма индуктивной гипотезы.

Выше я точно цитировал то, что говорит в книге. Теперь мой вопрос: почему мы не можем написать $ cn+n = dn $, где $ d = c+1 $, и теперь у нас есть $ t (n) leq dn $ и, следовательно, $ t (n) = o (n) $?

Примечание:

1. Правильный ответ $ t (n) = O (n log n). $
2. Книга, которую я здесь говорю, Введение в алгоритмы Кормен и др., Стр. 86, 3 -е издание.

Answer 1

Авторы дают ответ:

Ошибка в том, что мы не доказали точная форма из индуктивной гипотезы, то есть $ t (n) leq cn $.

Конечно, это трудно понять, если вы не привыкли делать индукции (справа), потому что они не делают индукцию явно/строго. Короче говоря: вам нужно иметь один Постоянные $ C $ для всех $ n $, но это (не) доказательство конструирует многие (по одному на $ n $).

---

Всего помните, что означает $ t (n) in o (n) $:

$ qquad displayStyle tastiasts c in mathbb {n}. , isists n_0 in mathbb {n}. , forall n geq n_0. , t (n) leq cn $

или, эквивалентно,

$ qquad displayStyle существует c in mathbb {n}. , forall n in mathbb {n} t (n) leq cn $.

Вторая форма работает лучше для индукции, как вы знаете якорь. Так что вам нужно один постоянный $ c $, который обеспечивает верхнюю границу для все $ n $.

Давайте осмотрим, что делает индукция:

• Индукционный якорь: якорь $ t $ не дается явно, но он постоянный, поэтому мы находим подходящую $ C $.
• Гипотеза индукции: существует около $ C $ так, чтобы $ t (k) leq cn $ для всех $ k leq n $, для некоторых произвольных, но фиксированных $ n $.
• Индуктивный шаг: как показано в вопросе, построить $ d> c $, чтобы $ t (n+1) leq dn $.

Итак, по сути, мы строим новый постоянно на каждую $ n $. Это вообще не соответствует определению $ o $ вообще! И, что еще хуже, это совершенно бессмысленно: каждый функция может быть «ограничена» любой другой Функция, если вы можете скорректировать фактор с помощью $ n $.

Что касается индукционного доказательства, $ C $ должен быть частью претензии (и оно скрыто в $ o $), то есть «за пределами» индукции. Затем та же $ C $ появляется в якоре, гипотезе и шаге. Увидеть последнюю часть этот ответ Для примера.