59
правок
Изменения
Нет описания правки
|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>O\left(\left(\dfrac{n}{b^i}\right) ^ c\right)</tex> дополнительных затрат, поэтому общее количество совершенных действий на уровне <tex>i</tex> :
<tex> O\left(a^i\left(\dfrac{n}{b^i}\right)^c \right) = O\left (n^c\left(\dfrac{a^i}{b^{ic}}\right)\right) = O\left (n^c\left(\dfrac{a}{b^c}\right)^i\right)</tex>
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <tex>\left(\dfrac{a}{b^c}\right)^i</tex> увеличивается, уменьшается или остается константой соответственно.
Распишем всю работу в течение рекурсивного спуска:
<tex dpi = "130">T(n) = \displaystyle\sum_{i=0}^{\log_b n}O\left(n^c\cdot\left(\frac{a}{b^c}\right)^i\right) + O(1)= ОO\left(n^c\cdot\displaystyle\sum_{i=0}^{\log_b n}\left(\frac{a}{b^c}\right)^i + O(1)\right)</tex>
Откуда получаем:
