Перейти к основному содержимому

Рекуррентные соотношения

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ
Архитектору Инженеру

Рекуррентное соотношение задаёт последовательность через предыдущие члены и начальные условия. В IT это язык, на котором описывают сложность рекурсивных алгоритмов и рост структур (деревья, очереди, кэши).

Прикладной контекст — дискретная математика; асимптотика и мастер-теорема — в теории чисел и анализе алгоритмов. Формальная «рекурсия» в теории вычислимости — отдельно: рекурсивные функции.

// Фибоначчи — классическое рекуррентное соотношение
F(0) = 0,  F(1) = 1
F(n) = F(n−1) + F(n−2)   при n ≥ 2

// Сложность наивной рекурсии без мемоизации — экспоненциальная;
// с мемоизацией или циклом — O(n)

Зачем это разработчику​

Где встречаетсяЧто описывает рекуррентность
Merge sort, quicksortT(n) = 2T(n/2) + O(n)
Бинарный поискT(n) = T(n/2) + O(1)
Обход дереваразмер поддерева через детей
Высота сбалансированного дереваh(n) = h(n/2) + 1
Число узлов полного двоичного дерева глубины dN(d) = 2N(d−1) + 1

Рекуррентность — мост между структурой алгоритма и O-оценкой времени или памяти.

Линейные однородные соотношения​

Линейное однородное соотношение k-го порядка:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ.

Характеристическое уравнение: подставляют aₙ = rⁿ и получают многочлен степени k. Корни rᵢ задают базис решения.

КорниОбщий вид члена
различные r₁,…,rₖA₁r₁ⁿ + … + Aₖrₖⁿ
кратный корень r кратности mдобавляются множители n, n², … у степеней rⁿ

Коэффициенты Aᵢ находят из начальных условий a₀, a₁, ….

Пример (Фибоначчи): aₙ = aₙ₋₁ + aₙ₋₂, характеристическое r² = r + 1. Корни (1±√5)/2; отсюда известная формула Бине и рост Θ(φⁿ) для наивной рекурсии, где φ ≈ 1.618.

Пример (сложность деления пополам): T(n) = T(n−1) + 1 при T(1)=1 даёт T(n)=n — линейный рост; T(n) = 2T(n/2) + n — см. мастер-теорему ниже.

Неоднородные соотношения​

Если в правой части есть дополнительный член d(n) (например, +n или +c), решение складывается:

aₙ = (aₙ)однородн + (aₙ)частное.

Частное решение подбирают по виду d(n): для полинома P(n) ищут полином той же степени; если d(n) = tⁿ и t — корень характеристического уравнения, степень полиномиального множителя увеличивают (кратность корня).

Три метода анализа​

МетодСутьКогда удобен
Подстановка (индукция)угадать O(…), доказать индукциейпростые оценки сверху
Характеристическое уравнениелинейные однородныеФибоначчи, линейные рекурсии
Мастер-теоремашаблон T(n)=aT(n/b)+f(n)divide-and-conquer

Подробнее про O, Θ и мастер-теорему — в статье 33.

Мастер-теорема (кратко)​

Для T(n) = a·T(n/b) + f(n), a ≥ 1, b > 1:

  1. Если f(n) = O(n^(log_b a − ε)) — доминирует деление: T(n) = Θ(n^(log_b a)).
  2. Если f(n) = Θ(n^(log_b a)) — баланс: T(n) = Θ(n^(log_b a) · log n).
  3. Если f(n) = Ω(n^(log_b a + ε)) и выполняется условие регулярности — доминирует f: T(n) = Θ(f(n)).
Рекуррентностьa, b, f(n)Результат
T(n)=2T(n/2)+n2, 2, nΘ(n log n) — merge sort
T(n)=T(n/2)+11, 2, 1Θ(log n) — бинарный поиск
T(n)=2T(n/2)+12, 2, 1Θ(n) — обход всех вершин дерева

Мастер-теорема не покрывает все случаи (например, T(n)=2T(n/2)+n log n); тогда используют дерево рекурсии или подстановку.

Связь с кодом​

функция MergeSort(A, lo, hi):
    если lo >= hi: вернуть
    mid ← (lo + hi) / 2
    MergeSort(A, lo, mid)      // T(n/2)
    MergeSort(A, mid+1, hi)    // T(n/2)
    Merge(A, lo, mid, hi)    // Θ(n)

Отсюда T(n) = 2T(n/2) + Θ(n) → Θ(n log n).

Практический вывод: перед оптимизацией рекурсии полезно записать рекуррентность; часто достаточно мемоизации или перехода на итерацию, чтобы снизить порядок роста (как с Фибоначчи O(φⁿ) → O(n)).

Назад: Графы — углубление. Дальше: Теория чисел, псевдокод и анализ алгоритмов. Самопроверка: чек-лист.

Содержание