59
правок
Изменения
Нет описания правки
</tex>
где <math>a</math> — количество подзадач, на которые мы разбиваем нашу задачу, <math>n</math> — размер нашей задачи, <tex dpi = "145125">\dfrac{n}{b}</tex> — размер подзадачи, <math> n ^ {c} </math> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач, <math>d</math> — единичная стоимость для данной задачи.
Пусть <math>a</math> — <math>\mathbb N </math> число большее 1, <math>b</math> — <math>\mathbb R </math> число большее 1, пусть также <math>c</math> — <math>\mathbb R^{+} </math> число и <math>d</math> — <math>\mathbb R^{+} </math> , тогда решение данного рекуррентного соотношения разбивается на три возможных случая:
Откуда получаем:
1. <math>\log_b a < c </math> <math>\Rightarrow</math> <math>T(n) = \Theta\left( n^{c} \right)</math> (т.к. <tex dpi = "130"> (\fracdfrac{a}{b^c})^i</tex> убывающая геометрическая прогрессия)
2. <math>\log_b a = c </math> <math>\Rightarrow</math> <tex dpi = "125"> T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot(\frac{a}{b^c})^i = </tex> <tex dpi = "125> n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}(\frac{a}{b^c})^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>
</math>
<math>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </math>
*:<math>a</math> не является константой; количество подзадач может меняться
*<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math>
*:не полиномиальное различие <math>f(n)</math> и <mathtex dpi = "140">n^{\log_b a}</mathtex>, т.к. <tex dpi = "145">\frac{f(n)}{n^{\log_b a}} = \frac{\frac{n}{\log n}}{n^{log_2 2}} = \frac{n}{n \log n} = \frac{1}{\log n} < n^\epsilon</tex>, для любого <tex dpi = "145">\epsilon > 0</tex>
*<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math>
*:<math>a</math> < 1 не может быть меньше одной подзадачи
