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

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

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

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) имеет следующие асимптотические оценки:

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+ϵ), то T(n) = Θ(f(n)).

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

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

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

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

T(n) = 3T(n/2) + n2
Здесь:
a = 3
n/b = n/2
f(n) = n2
logb a = log2 3 ≈ 1.58 < 2
то есть f(n) < nlogb a+ϵ, где ϵ — константа.
То есть, это 3 случай.
Следовательно, T(n) = f(n) = Θ(n2) 

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

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

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