Изменения

|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> : <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> увеличивается, уменьшается или остается константой соответственно.Поэтому мы должны разобрать три случая, когда <tex>\left(\dfrac{a}{b^c}\right)^i</tex> больше <tex>1</tex>, равен <math>1</math> или меньше <math>1</math>.Рассмотрим <tex dpi = "140">\left(\dfrac{a}{b^c}\right)^i = 1</tex> <tex dpi = "140">\Leftrightarrow a = b^c\Leftrightarrow\ log_b a = c \log_b b\Leftrightarrow\log_b a = c</tex>.

<tex dpi = "130"> d\cdot \displaystyle\sum_{i=1}^{\log_b n}n^c\left(\frac{a}{b^c}\right)^i = n^c\cdot d \cdot\displaystyle\sum_{i=1}^{\log_b n}\left(\frac{a}{b^c}\right)^i</tex>

1. <tex>\log_b a < c </tex> <tex>\Rightarrow</tex> <tex>T(n) = \Theta\left( n^{c} \right)</tex> (т.к. <tex dpi = "130"> \left(\dfrac{a}{b^c}\right)^i</tex> убывающая геометрическая прогрессия)

2. <tex>\log_b a = c </tex> <tex>\Rightarrow</tex> <tex dpi = "125130"> T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = </tex> <tex dpi = "125130> n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}\left(\frac{a}{b^c}\right)^i = n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}1^i = n^c + n^c\log_b n = \Theta\left( n^{c} \log n \right) </tex>

3. <tex>\log_b a > c </tex> <tex>\Rightarrow</tex> <tex dpi = "125"> T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}\left(\fracdfrac{a}{b^c}\right)^i = \Theta\left( n^c\cdot\left(\fracdfrac{a}{b^c}\right)^{log_b n} \right)</tex>, но <tex dpi = "150130"> n^c\cdot\left(\fracdfrac{a}{b^c}\right)^{log_b n} </tex> <tex dpi = "130"> = </tex> <tex dpi = "150130"> n^c\cdot\left(\fracdfrac{a^{log_b n} }{(b^c)^{log_b n}}\right) </tex> <tex dpi = "130"> = </tex> <tex dpi = "150130"> n^c\cdot\left(\fracdfrac{n^{log_b a}}{n^c}\right)</tex> <tex dpi = "130150"> = </tex> <tex dpi = "130150"> \Theta\left( n^{\log_b a} \right) </tex>

3 \; t\!\left(\fracdfrac{x}{2}\right) + x^{2} , & x > \ge 2\\ 5x , & 1 < \le x < 2

Заметим, чтобы узнать <tex>t(7)</tex> , мы должны знать <tex>t\left(\dfrac{7}{2}\right)</tex>, чтобы узнать <tex>t\left(\dfrac{7}{2}\right)</tex>, мы должны узнать <tex>t\left(\dfrac{7}{4}\right)</tex>, <tex>1 < \dfrac{7}{4} < 2</tex>, тогда <tex>t\left(\dfrac{7}{4}\right) = \dfrac{35}{4}</tex> , <tex>t\left(\dfrac{7}{2}\right) = 3\cdot\dfrac{35}{4} + \dfrac{49}{4}</tex>, тогда <tex>t(7) = 3t\left(\dfrac{7}{2}\right) + 7^2 = \dfrac{329}{2}</tex>

2 \; T\!\left(\fracdfrac{n}{3}\right) + f(n) , & n > 1\\

Данное соотношение подходит под первый случай <tex>\left(a = 2, b = 3, c = \dfrac{3}{2}\right)</tex>, поэтому его асимптотика совпадает с асимптотикой <tex>f(n)</tex>(следуя из определения <tex> \Theta </tex> и <tex> O </tex>).

*<tex dpi = "130">T(n) = 2^nT\left (\fracdfrac{n}{2}\right )+n^n</tex>

*<tex dpi = "130">T(n) = 2T\left (\fracdfrac{n}{2}\right )+\frac{n}{\log n}</tex>

*<tex dpi = "130">T(n) = 0.5T\left (\fracdfrac{n}{2}\right )+n</tex>

*<tex dpi = "130">T(n) = 64T\left (\fracdfrac{n}{8}\right )-n^2\log n</tex>