3622
правки
Изменения
м
* # Если <tex>c > \log_b a</tex>, то <tex>T(n) = \Theta\left( n^{c} \right)</tex>
* # Если <tex>c = \log_b a</tex>, то <tex>T(n) = \Theta\left( n^{c} \log n \right)</tex>
* # Если <tex>c < \log_b a</tex>, то <tex>T(n) = \Theta\left( n^{\log_b a} \right)</tex>
→Формулировка и доказательство мастер-теоремы
Тогда решение данной рекурренты зависит от соотношения между <tex>a, b, c</tex> так:
|proof= Давайте рассмотрим дерево рекурсии. Всего в нем будет <tex>\log_b n</tex> уровней. На каждом таком уровне, количество подзадач будет умножаться на <tex>a</tex>, так на уровне <tex>i</tex> будет <tex>a^i</tex> подзадач. Также известно, что каждая подзадача на уровне <tex>i</tex> размера <tex>\dfrac{n}{b^i}</tex>. Подзадача размера <tex>\dfrac{n}{b^i}</tex> требует <tex>\left(\dfrac{n}{b^i}\right) ^ c</tex> дополнительных затрат, поэтому общее количество совершенных операций на уровне <tex>i</tex> :
