Изменения

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 = "130"> T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = </tex> <tex dpi = "130> 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(\dfrac{a}{b^c}\right)^i = n^c\cdot\left(\dfrac{a}{b^c}\right)^{log_b n}</tex>, но <tex dpi = "130"> n^c\cdot\left(\dfrac{a}{b^c}\right)^{log_b n} </tex> <tex dpi = "130"> = </tex> <tex dpi = "130"> n^c\cdot\left(\dfrac{a^{log_b n} }{(b^c)^{log_b n}}\right) </tex> <tex dpi = "130"> = </tex> <tex dpi = "130"> n^c\cdot\left(\dfrac{n^{log_b a}}{n^c}\right)</tex> <tex dpi = "150"> = </tex> <tex dpi = "150"> \Theta\left( n^{\log_b a} \right) </tex>

Пусть при решении поставленной задачи, существует алгоритм, который разбивает ее на <tex> a </tex> подзадач,при этом <tex>n</tex> — размер общей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер каждой подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и <mathtex>d</mathtex> — начальная стоимость для данной задачи(при <tex>n = 1</tex>).Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.