Основная теорема о рекуррентных соотношениях

В этой статье вы познакомитесь с основной теоремой о рекуррентных соотношениях и узнаете, как использовать ее для решения рекуррентных соотношений.

Основная теорема о рекуррентных соотношениях — это формула, предназначенная для решения рекуррентных соотношений следующего вида:

T(n) = aT(n/b) + f(n), где
n = объем входных данных
a = количество подзадач в рекурсии
n/b = размер каждой подзадачи. Предполагается, что все подзадачи имеют одинаковый размер.
f(n) = оценка выполненной работы вне рекурсивных вызовов.

Также она включает в себя вычислительную стоимость деления на подзадачи объединения решений этих подзадач.

Здесь a ≥ 1 и b > 1 — константы, а f(n) — асимптотически положительная функция.

Асимптотически положительная функция — функция, где при достаточно больших значениях n f(n)>0.

Основная теорема о рекуррентных соотношениях — простой и быстрый способ вычисления временной сложности рекуррентных соотношений (например, «Разделяй и властвуй»).

Формулировка теоремы

Если a ≥ 1 и b > 1 — константы, а f(n) — асимптотически положительная функция, то временная сложность рекуррентного соотношения задается выражением:

T(n) = aT(n/b) + f(n)

T(n) имеет следующие асимптотические оценки:

Если f(n) = O(n^log_b ^a-ϵ), то T(n) = Θ(n^log_b ^a).
Если f(n) = Θ(n^log_b ^a), то T(n) = Θ(n^log_b ^a*log n).
Если f(n) = Ω(n^log_b ^a+ϵ), то T(n) = Θ(f(n)).

ϵ > 0 — константа.

Каждое из этих условий можно интерпретировать следующим образом:

Если стоимость решения подзадач на каждом уровне увеличивается на некий коэффициент, то значение f(n) станет полиномиально меньше, чем n^log_b ^a. То есть, временная сложность зависит от стоимости последнего уровня — n^log_b ^a.
Если стоимость решения подзадач на каждом уровне примерно одинакова, то значение f(n) станет равно n^log_b ^a. То есть, временная сложность будет равна f(n), умноженной на количество уровней — n^log_b ^a*log n.
Если стоимость решения подзадач на каждом уровне уменьшается на некий коэффициент, то значение f(n) станет полиномиально больше, чем n^log_b ^a. То есть, временная сложность зависит от стоимости f(n).

Пример использования

T(n) = 3T(n/2) + n²
Здесь:
a = 3
n/b = n/2
f(n) = n²
log_ba = log₂3 ≈ 1.58 < 2
то есть f(n) > n^{log_b a+ϵ}, где ϵ — константа.
То есть, это 3 случай.
Следовательно, T(n) = f(n) = Θ(n²)

Откуда в теореме берется величина n^log_b ^a? Запустите блок-схему ниже: она моделирует дерево рекурсии для a = 2 и b = 2 — на каждом уровне задача делится пополам, а количество подзадач удваивается. Введите n, например 16 или 64.

n = int(input())
a = 2
b = 2
levels = 0
leaves = 1
while n > 1:
    n = n // b
    levels = levels + 1
    leaves = leaves * a
print("Уровней рекурсии:", levels)
print("Подзадач на нижнем уровне:", leaves)

Уровней получается log_b n, а подзадач на нижнем уровне — a^{log_b n}, то есть n^log_b ^a. Именно с этой величиной теорема сравнивает f(n), чтобы понять, какой из трех случаев применить.

Когда не работает

Основную теорему о рекуррентных соотношениях нельзя использовать в следующих случаях:

T(n) не монотонна — например, T(n) = sin n.
f(n) не полиномиальна — например, f(n) = 2n.
a не константа — например, а = 2n.
a < 1.