Как сформулировать рекуррентное уравнение для времени работы алгоритма «разделяй и властвуй»

Хорошо,$T(n) = T(a) + T(b) + 2n$в первом случае с$a,b$ограничено, как вы упомянули

Сначала сформулируем задачу в терминах явного рекуррентного соотношения.

Позволять$a _ 1 = a _ 2 = 1$и$b _ 1 = b _ 2 = \frac 1 2$, и рассмотрим функции$T , h _ 1 , h _ 2 , g$и с тем свойством, что

$$T ( x ) = g ( x ) + a _ 1 T \big( b _ 1 x + h _ 1 ( x ) \big) + a _ 2 T \big( b _ 2 x + h _ 2 ( x ) \big) \text .$$ Также предположим, что$| h _ 1 ( x ) | , | h _ 2 ( x ) | \le \frac x 4$. Найдите асимптотические оценки для$T$, когда$g ( x ) = 2 x$, и когда$g ( x ) = x ^ 2$.

Я намеренно сформулировал проблему так, как указано выше, чтобы она выглядела похожей на форму, фигурирующую в теореме Акра-Бацци , которая является одним из самых известных обобщений основной теоремы . Как вы можете видеть в примечании Лейтона к теореме Акра-Бацци, данная асимптотическая оценка теоремы гарантированно работает только тогда, когда существует некоторая положительная константа$\epsilon$такой, что у нас есть$| h _ 1 ( x ) | , | h _ 2 ( x ) | \le \frac x { ( \log x ) ^ { 1 + \epsilon } }$для всех достаточно большой$x$(вместе с другими требованиями, которые выполняются в нашей задаче). К сожалению, в нашей задаче это не так, и вы не можете использовать основную теорему или ее известные обобщения, как вы ожидали. Но, к счастью, порядок роста, заданный теоремой, работает в нашей задаче по другой простой причине. Таким образом, у нас есть хорошее предположение, использующее обобщенную главную теорему, и нам нужно только предоставить доказательство. Как$p = 1$это единственное действительное число, удовлетворяющее$a _ 1 b _ 1 ^ p + a _ 2 b _ 2 ^ p = 1$(критическая мощность), заданный порядок роста$\Theta \bigg( x ^ p \left( 1 + \int _ 1 ^ x \frac { g ( u ) } { u ^ { p + 1 } } \ \mathrm d u \right) \bigg)$становится$\Theta ( x \log x )$в случае$g ( x ) = 2 x$, и$\Theta \left( x ^ 2 \right)$в случае$g ( x ) = x ^ 2$.

Чтобы понять, почему границы работают, обратите внимание, что обе$x \mapsto x \log x$и$x \mapsto x ^ 2$являются дифференцируемыми выпуклыми функциями (в нашей области интереса, скажем,$x \ge 1$). Таким образом, их производные,$x \mapsto 1 + \log x$и$x \mapsto 2 x$, строго возрастают и, следовательно, инъективны. Рассмотрим дифференцируемую функцию с действительным знаком$f$определенный на интервале$I = \left[ \frac n 2 - m , \frac n 2 + m \right]$для некоторого положительного$n$и$m$, такое, что его производная$f '$строго возрастает. Определять$F : I \to \mathbb R$с$F ( a ) = f ( a ) + f ( n - a )$. Затем$F$является дифференцируемым и$F ' ( a ) = f ' ( a ) - f ' ( n - a )$. Как$f '$является инъективным, значение$F '$может стать нулем только тогда, когда$a = n - a$, т.е.$a = \frac n 2$. Таким образом, в качестве экстремумов$F$может происходить только в конечных точках$I$или где значение$F '$становится нулем, мы можем проверить, что для всех$a \in I$,

Случай$T ( n ) = T \big( a ( n ) \big) + T \big( b ( n ) \big) + 2 n$

Выберите положительные константы$c _ 1 \le 2$и$c _ 2 \ge \frac 1 { 1 - \frac 3 8 \log _ 2 3 }$такой, что у нас есть

Случай$T ( n ) = T \big( a ( n ) \big) + T \big( b ( n ) \big) + n ^ 2$

Выберите положительные константы$c _ 1 \le 2$и$c _ 2 \ge \frac 8 3$такой, что у нас есть