Строгое доказательство справедливости предположения при использовании основной теоремы

Основная теорема является прекрасным инструментом для решения определенных видов повторений . Тем не менее, мы часто замазываем неотъемлемую часть при его применении. Например, во время анализа Mergesort мы с радостью

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

в

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

учитывая только . Мы заверяем себя, что этот шаг действителен - то есть - потому что ведет себя "хорошо". В общем, мы предполагаем, что для общего знаменателя.$n=2^k$$T \in \Theta(T')$$T$$n=b^k$$b$

Легко построить повторения, которые не позволяют это упрощение, используя порочный . Например, выше повторения для / с$f$$T\,$$\,T'$

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

выдаст обычным образом, используя теорему Мастера, но есть явно подпоследовательность, которая растет как . Смотрите здесь для другого, более надуманного примера.$\Theta(n)$$\Theta(n \log n)$

Как мы можем сделать это "красиво" строгим? Я совершенно уверен, что монотонности достаточно, но даже простое повторение Mergesort не является монотонным; существует периодическая составляющая (которая асимптотически доминирует). Достаточно ли исследовать и каковы необходимые и достаточные условия для , обеспечивающие работу основной теоремы?$f$$f$

В этом ответе мы предполагаем, что и неотрицательны. Наше доказательство работает всякий раз, когда для некоторого монотонного . Это включает ваш пример Mergesort, в котором , и любую функцию с полиномиальной скоростью роста (или даже ).$f$$T$$f = \Theta(g)$$g$$f=\Theta(n)$$\Theta(n^a \log^b n)$

Давайте сначала рассмотрим случай, когда является монотонно неубывающим (мы ослабим это предположение позже). Мы сконцентрируемся на повторяемости вашей выборки Это повторение требует двух базовых случаев, и . Сделаем предположение, что , что мы позже и ослабим.$f$

Я утверждаю, что является монотонно неубывающим. По полной индукции докажем, что . Это дается для , поэтому пусть . У нас есть Это означает, что Итак, если , все готово. Это всегда так, если решение для степеней двойки имеет вид .$T(n)$$T(n+1) \geq T(n)$$n = 0$$n \geq 1$

Теперь давайте ослабим предположение, что . Рассмотрим новую рекурсию определенную точно таким же образом, только . По индукции можно доказать, что . Аналогично, мы можем определить новую рекурсию удовлетворяющую , а затем . Используя теорему Мастера, мы видим, что и для одной и той же функции , а значит, и .$T(0) \leq T(1)$$T'$$T'(0) = T'(1) = \min(T(0),T(1))$$T'(n) \leq T(n)$$T''$$T''(0) = T''(1) = \max(T(0),T(1))$$T(n) \leq T''(n)$$T'=\Theta(h)$$T''=\Theta(h)$$h$$T = \Theta(h)$

Теперь давайте ослабим предположение, что является монотонным. Предположим, что для некоторой монотонной функции . Таким образом, для некоторых и достаточно больших . Для простоты будем считать, что ; общий случай может быть обработан как в предыдущем параграфе. Опять мы определяем две рекурсии , заменяя на (соответственно). Еще раз основная теорема даст тот же результат (до постоянных кратных), который также идентичен (до постоянных кратных) тому, что мы получили бы, решив исходное повторение только на степени двух.$f$$f = \Theta(g)$$g$$cg(n) \leq f(n) \leq Cg(n)$$c,C>0$$n$$n=0$$T',T''$$f$$cg,Cg$