3622
правки
Изменения
м
→Формулировка и доказательство мастер-теоремы
# Если <tex>c < \log_b a</tex>, то <tex>T(n) = O\left( n^{\log_b a} \right)</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>\left(\dfrac{n}{b^i}\right)</tex> требует <tex>\left(\dfrac{n}{b^i}\right) ^ c</tex> дополнительных затрат, поэтому общее количество совершенных действий на уровне <tex>i</tex> :
<tex> a^i\left(\dfrac{n}{b^i}\right)^c = n^c\left(\dfrac{a^i}{b^{ic}}\right) = n^c\left(\dfrac{a}{b^c}\right)^i</tex>
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <tex>\left(\dfrac{a}{b^c}\right)^i</tex> увеличивается, уменьшается или остается константой соответственно.
