59
правок
Изменения
Нет описания правки
==Примеры==
1.Пусть у нас задана задано такое рекуррентное соотношение: Рассчитать для <math>x = 7</math>.
<math> t(x) = \begin{cases}
5x , & 1 < x < 2
\end{cases}
</math> Заметим, чтобы узнать <math>t(7)</math> , мы должны знать <math>t(7/2)</math>, чтобы узнать <math>t(7/2)</math>, мы должны узнать <math>t(7/4)</math>, <math>1 < 7/4 < 2</math>, тогда <math>t(7/4) = 35/4</math> , <math>t(7/2) = 3*35/4 + 49/4</math>, тогда <math>t(7) = 3t(7/2) + 7^2 = 329/2</math>
2. Задано такое соотношение:
<math> T(n) = \begin{cases}
2 \; tT\!\left(\frac{n}{3}\right) + f(n) , & n > 1\\
d , & n = 1
\end{cases}
</math>
<math>f(n) = n\sqrt n > n^{3/2} = O(n^{3/2}) </math>, а также
<math>f(n) = n\sqrt n < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </math>
==Недопустимые соотношения==
Рассмотрим пару ошибочно-составленных соотношений:
*<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math>
*:''a'' не является константой; количество подзадач может меняться
*<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math>
*:не полиномиальное различие f(n) и <math>n^{\log_b a}</math>
*<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math>
*:''a''<1 не может быть меньше одной подзадачи
*<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math>
*:f(n) не положительна
*<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math>
*:регулярно меняющееся f(n)
== Application to common algorithms ==
{| class="wikitable"
|-
! Алгоритм
! Рекуррентное соотношение
! Время работы
! Комментарий
|-
| [[Целочисленный двоичный поиск]]
| <math>T(n) = T\left(\frac{n}{2}\right) + O(1)</math>
| <math>O(\log n)</math>
| По мастер-теореме <math>c = \log_b a</math>, где <math>a = 1, b = 2, c = 0</math>
|-
| Обход бинарного дерева
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math>
| <math>O(n)</math>
| По мастер-теореме <math>c < \log_b a</math> where <math>a = 2, b = 2, c = 0</math>
|-
| [[Сортировка слиянием]]
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(n)</math>
| <math>O(n \log n)</math>
| По мастер-теореме <math>c = \log_b a</math>, where <math>a = 2, b = 2, c = 1</math>
|}
