Головна теорема — це інструмент, який використовується для вирішення рекурентних співвідношень, які виникають під час аналізу алгоритмів «розділяй і володарюй». Основна теорема забезпечує систематичний спосіб розв’язування рекурентних співвідношень виду:

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

1. де a, b і f(n) — позитивні функції, а n — розмір проблеми. Основна теорема забезпечує умови для того, щоб розв’язок рекуррентної проблеми мав форму O(n^k) для деякої константи k, і вона дає формулу для визначення значення k.
2. Розширена версія Основної теореми надає більш загальну форму теореми, яка може обробляти рекурентні співвідношення, складніші за основну форму. Розширена версія головної теореми може обробляти повторення з декількома термінами та складнішими функціями.
3. Важливо зазначити, що Головна теорема не застосовна до всіх рекурентних співвідношень, і вона не завжди може забезпечити точне розв’язання даної рекурентності. Однак це корисний інструмент для аналізу складності часу алгоритмів «розділяй і володарюй» і забезпечує хорошу відправну точку для вирішення більш складних рецидивів.

Основна теорема використовується для визначення часу роботи алгоритмів (алгоритмів «розділяй і володарюй») у термінах асимптотичних нотацій.
Розглянемо задачу, яка розв’язується за допомогою рекурсії.

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>

Наведений вище алгоритм ділить задачу на a підзадачі, кожна розміром n/b, і розв’язувати їх рекурсивно для обчислення проблеми, а додаткова робота, виконана для проблеми, визначається f(n), тобто час для створення підпроблем і об’єднання їх результатів у наведеній вище процедурі.

Таким чином, згідно з головною теоремою, час виконання наведеного вище алгоритму можна виразити як:

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

де n = розмір проблеми
a = кількість підпроблем у рекурсії та a>= 1
n/b = розмір кожної підпроблеми
f(n) = вартість роботи, виконаної за межами рекурсивних викликів, як-от поділ на підпроблеми, і вартість їх об’єднання для отримання рішення.

Не всі рекурентні співвідношення можна розв’язати за допомогою головної теореми, тобто якщо

• T(n) не є монотонним, наприклад: T(n) = sin n
• f(n) не є поліномом, наприклад: T(n) = 2T(n/2) + 2^п

Ця теорема є попередньою версією основної теореми, яку можна використовувати для визначення часу роботи алгоритмів «розділяй і володарюй», якщо повторення має такий вигляд:

де n = розмір проблеми
a = кількість підпроблем у рекурсії та a>= 1
n/b = розмір кожної підпроблеми
b> 1, k>= 0 і p — дійсне число.

Потім,

1. якщо a> b^k, то T(n) = θ(n^{журнал_ba})
2. якщо a = b^k, потім
   (a) якщо p> -1, то T(n) = θ(n^{журнал_ba}журнал^p+1п)
   (b) якщо p = -1, то T(n) = θ(n^{журнал_ba}loglogn)
   (c) якщо p <-1, то T(n) = θ(n^{журнал_ba})
   
3. якщо k, тоді
   (a) якщо p>= 0, то T(n) = θ(n^kжурнал^сторп)
   (b) якщо p <0, то T(n) = θ(n^k)
   

Аналіз складності часу –

Приклад 1: двійковий пошук – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 і p = 0
b^k= 1. Отже, a = b^kі p> -1 [Випадок 2.(a)]
T(n) = θ(n^{журнал_ba}журнал^p+1п)
T(n) = θ(logn) Приклад 2: Сортування злиттям – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Отже, a = b^kі p> -1 [Випадок 2.(a)]
T(n) = θ(n^{журнал_ba}журнал^p+1п)
T(n) = θ(nlogn) Приклад 3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Отже, a k і p = 0 [Випадок 3.(a)]
T(n) = θ(n^kжурнал^сторп)
T(n) = θ(n²)

Приклад-4: T(n) = 3T(n/2) + log²п
a = 3, b = 2, k = 0, p = 2
b^k= 1. Отже, a> b^k[Випадок 1]
T(n) = θ(n^{журнал_ba})
T(n) = θ(n^{журнал₂3})

Приклад-5: T(n) = 2T(n/2) + nlog²п
a = 2, b = 2, k = 1, p = 2
b^k= 2. Отже, a = b^k[Випадок 2.(a)]
T(n) = θ(n^{журнал_ba}журнал^p+1n )
T(n) = θ(n^{журнал₂2}журнал³п)
T(n) = θ(nlog³п)

Приклад-6: T(n) = 2^пT(n/2) + n^п
Це повторення не можна розв’язати за допомогою вищезазначеного методу, оскільки функція не має вигляду T(n) = aT(n/b) + θ(n^kжурнал^сторп)

GATE Практичні запитання –

• GATE-CS-2017 (Набір 2) | Питання 56
• GATE IT 2008 | Питання 42
• GATE CS 2009 | Питання 35

Ось кілька важливих моментів, про які слід пам’ятати щодо основної теореми:

1. Повторення «розділяй і володарюй»: головна теорема спеціально розроблена для вирішення рекурентних співвідношень, які виникають під час аналізу алгоритмів «розділяй і володарюй».
2. Форма повторення: Головна теорема застосовується до рекурентних співвідношень у формі T(n) = aT(n/b) + f(n), де a, b і f(n) — додатні функції, а n — розмір проблеми.
3. Складність у часі: головна теорема забезпечує умови для того, щоб розв’язок повторення був у формі O(n^k) для деякої константи k, і вона дає формулу для визначення значення k.
4. Розширена версія: розширена версія Основної теореми надає більш загальну форму теореми, яка може обробляти рекурентні співвідношення, які є складнішими, ніж основна форма.
5. Обмеження: Основна теорема не застосовна до всіх рекурентних співвідношень, і вона не завжди може забезпечити точне розв’язання даного повторення.
6. Корисний інструмент: незважаючи на свої обмеження, Основна теорема є корисним інструментом для аналізу складності часу алгоритмів «розділяй і володарюй» і забезпечує хорошу відправну точку для розв’язання більш складних рецидивів.
7. Доповнено іншими техніками: у деяких випадках головну теорему може знадобитися доповнити іншими техніками, такими як метод підстановки або метод ітерації, щоб повністю розв’язати задане рекурентне співвідношення.