59
правок
Изменения
Нет описания правки
</tex>
, тогда где <tex>a</tex> — <tex>\mathbb N </tex> число большее <tex>1</tex>, <tex>b</tex> — <tex>\mathbb R </tex> число большее <tex>1</tex>, <tex>c</tex> — <tex>\mathbb R^{+} </tex> число и <tex>d</tex> — <tex>\mathbb R^{+} </tex>. Тогда решение данной рекурренты зависит от соотношения между <tex>a, b, c</tex> так:
* Если <tex>c > \log_b a</tex>, то <tex>T(n) = \Theta\left( n^{c} \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(\frac{a}{b^c})^i = n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}(\frac{a}{b^c})^i = \Theta\left( n^c\cdot(\frac{a}{b^c})^{log_b n} \right)</tex>, но <tex dpi = "150"> n^c\cdot(\frac{a}{b^c})^{log_b n} </tex> <tex dpi = "130"> = </tex> <tex dpi = "150"> n^c\cdot(\frac{a^{log_b n} }{(b^c)^{log_b n}}) </tex> <tex dpi = "130"> = </tex> <tex dpi = "150"> n^c\cdot(\frac{n^{log_b a}}{n^c})</tex> <tex dpi = "130"> = </tex> <tex dpi = "130"> \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> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и <math>d</math> — начальная стоимость для данной задачи(при <tex>n = 1</tex>).Где <tex>a</tex> — <tex>\mathbb N </tex> число большее <tex>1</tex>, <tex>b</tex> — <tex>\mathbb R </tex> число большее <tex>1</tex>, <tex>c</tex> — <tex>\mathbb R^{+} </tex> число и <tex>d</tex> — <tex>\mathbb R^{+} </tex>.Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.
}}
