59
правок
Изменения
Нет описания правки
Рассмотрим пару ошибочно-составленных соотношений:
*<math>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math>
*:''<math>a'' </math> не является константой; количество подзадач может меняться
*<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math>
*:не полиномиальное различие <math>f(n) </math> и <math>n^{\log_b a}</math>
*<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math>
*:''<math>a''</math> <1 не может быть меньше одной подзадачи
*<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math>
*:<math>f(n) </math> не положительна
*<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math>
*:регулярно меняющееся <math>f(n)</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>
|}
