Время рекурсивного алгоритма записывается через рекуррентное соотношение: T(n) выражается через значения T на меньших входах и собственную работу вызова. В уроке три способа его решить: развёртывание/подстановка, дерево рекурсии и основная теорема.
Четыре знакомых рекуррента
| Рекуррент | Пример | Решение |
|---|---|---|
T(n) = T(n-1) + c | факториал, сумма списка | O(n) |
T(n) = T(n-1) + n | рекурсивная сортировка выбором | O(n^2) |
T(n) = T(n/2) + c | бинарный поиск | O(log n) |
T(n) = 2T(n/2) + n | сортировка слиянием | O(n log n) |
T(n) = 2T(n-1) + c | два вызова на каждом шаге | O(2^n) |
Метод развёртывания: для T(n) = T(n-1) + n получаем T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2. Код ниже считает реальную работу четырёх рекуррентов, и результаты совпадают с теорией.
def work_linear(n): # T(n) = T(n-1) + 1
return 0 if n == 0 else 1 + work_linear(n - 1)
def work_quad(n): # T(n) = T(n-1) + n
return 0 if n == 0 else n + work_quad(n - 1)
def work_log(n): # T(n) = T(n/2) + 1
return 0 if n <= 1 else 1 + work_log(n // 2)
def work_nlogn(n): # T(n) = 2T(n/2) + n
return 0 if n <= 1 else n + 2 * work_nlogn(n // 2)
for n in (16, 64, 256):
print(n, work_linear(n), work_quad(n), work_log(n), work_nlogn(n))