В этом руководстве вы узнаете, что такое основная теорема и как она используется для решения рекуррентных соотношений.
Мастер-метод - это формула решения рекуррентных соотношений вида:
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 журнал 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 - постоянная.
Каждое из вышеперечисленных условий можно интерпретировать как:
- Если стоимость решения подзадач на каждом уровне увеличивается в определенном разы, значение
f(n)станет полиномиально меньше, чем . Таким образом, временная сложность подавляется стоимостью последнего уровня, т.е.nlogb anlogb a - Если стоимость решения подзадач на каждом уровне примерно одинакова, то значение
f(n)будет равно . Таким образом, временная сложность будет умножена на общее количество уровней, т.е.nlogb af(n)nlogb a * log n - Если стоимость решения подзадач на каждом уровне уменьшится в определенном разы, значение
f(n)станет полиномиально больше, чем . Таким образом, временная сложность подавляется стоимостью .nlogb af(n)
Решенный пример основной теоремы
T (n) = 3T (n / 2) + n2 Здесь a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 т.е. f (n) <n log b a + ϵ , где ϵ - постоянная. Случай 3 подразумевает здесь. Таким образом, T (n) = f (n) = Θ (n 2 )
Ограничения основной теоремы
Основная теорема не может быть использована, если:
- T (n) не монотонен. например.
T(n) = sin n f(n)не является полиномом. например.f(n) = 2n- а не является константой. например.
a = 2n a < 1
