В този урок ще научите какво е основната теорема и как се използва за решаване на рецидивиращи връзки.
Основният метод е формула за решаване на рекурентни връзки на формата:
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 е константа.
Всяко от горните условия може да се тълкува като:
- Ако цената за решаване на подзадачите на всяко ниво се увеличи с определен коефициент, стойността на
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 не е константа. напр.
a = 2n a < 1
