59
правок
Изменения
Нет описания правки
</tex>
где <tex>a</tex> — количество подзадач, на которые мы разбиваем нашу задачу, <tex>n</tex> — размер нашей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач, <math>d</math> — начальная стоимость для данной задачи(при <mathtex>n = 1</mathtex>).
Пусть <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>
Заметим, чтобы узнать <tex>t(7)</tex> , мы должны знать <tex>t(\dfrac{7/}{2})</tex>, чтобы узнать <tex>t(\dfrac{7/}{2})</tex>, мы должны узнать <tex>t(\dfrac{7/}{4})</tex>, <tex>1 < \dfrac{7/}{4 } < 2</tex>, тогда <tex>t(\dfrac{7/}{4}) = \dfrac{35/}{4}</tex> , <tex>t(\dfrac{7/}{2}) = 3\cdot35/cdot\dfrac{35}{4 } + \dfrac{49/}{4}</tex>, тогда <tex>t(7) = 3t(\dfrac{7/}{2}) + 7^2 = \dfrac{329/}{2}</tex>
==== Пример 2 ====
