Twierdzenie główne jest narzędziem służącym do rozwiązywania relacji powtarzalności, które powstają w analizie algorytmów dziel i zwyciężaj. Twierdzenie główne zapewnia systematyczny sposób rozwiązywania relacji powtarzalności w postaci:

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

1. gdzie a, b i f(n) są funkcjami dodatnimi, a n jest wielkością problemu. Twierdzenie Główne dostarcza warunków rozwiązania powtarzania się w postaci O(n^k) dla pewnej stałej k i podaje wzór na określenie wartości k.
2. Zaawansowana wersja Twierdzenia Głównego zapewnia bardziej ogólną formę twierdzenia, która może obsługiwać relacje powtarzania, które są bardziej złożone niż forma podstawowa. Zaawansowana wersja twierdzenia głównego może obsługiwać powtarzające się terminy z wieloma terminami i bardziej złożonymi funkcjami.
3. Należy zauważyć, że Główne Twierdzenie nie ma zastosowania do wszystkich relacji rekurencyjnych i nie zawsze może zapewnić dokładne rozwiązanie danej rekurencji. Jest to jednak przydatne narzędzie do analizy złożoności czasowej algorytmów dziel i zwyciężaj i stanowi dobry punkt wyjścia do rozwiązywania bardziej złożonych powtórzeń.

Twierdzenie główne służy do wyznaczania czasu działania algorytmów (algorytmów dziel i zwyciężaj) w kategoriach notacji asymptotycznej.
Rozważmy problem, który można rozwiązać za pomocą rekurencji.

 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>

Powyższy algorytm dzieli problem na A podproblemów, każdy o rozmiarze n/b, i rozwiązuj je rekurencyjnie, aby obliczyć problem, a dodatkową pracę wykonaną dla problemu wyraża się przez f(n), tj. czas na utworzenie podproblemów i połączenie ich wyników w powyższej procedurze.

Zatem zgodnie z twierdzeniem głównym czas wykonania powyższego algorytmu można wyrazić jako:

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

gdzie n = rozmiar problemu
a = liczba podproblemów w rekurencji i a>= 1
n/b = rozmiar każdego podproblemu
f(n) = koszt pracy wykonanej poza wywołaniami rekurencyjnymi, taki jak podział na podproblemy i koszt połączenia ich w celu uzyskania rozwiązania.

Nie wszystkie relacje rekurencji można rozwiązać za pomocą twierdzenia głównego, tj. Jeśli

• T(n) nie jest monotoniczne, np.: T(n) = sin n
• f(n) nie jest wielomianem, np.: T(n) = 2T(n/2) + 2^N

Twierdzenie to jest zaawansowaną wersją twierdzenia głównego, którego można użyć do określenia czasu działania algorytmów dziel i zwyciężaj, jeśli powtarzalność ma następującą postać: -

gdzie n = rozmiar problemu
a = liczba podproblemów w rekurencji i a>= 1
n/b = rozmiar każdego podproblemu
b> 1, k>= 0 i p jest liczbą rzeczywistą.

Następnie,

1. jeśli a> b^k, wówczas T(n) = θ(n^dziennik_BA)
2. jeśli a = b^k, Następnie
   (a) jeśli p> -1, to T(n) = θ(n^dziennik_BAdziennik^p+1N)
   (b) jeśli p = -1, to T(n) = θ(n^dziennik_BAzaloguj się)
   (c) jeśli p <-1, to T(n) = θ(n^dziennik_BA)
   
3. Jeśli k., zatem
   (a) jeśli p>= 0, to T(n) = θ(n^kdziennik^PN)
   (b) jeśli p < 0, to T(n) = θ(n^k)
   

Analiza złożoności czasu –

Przykład 1: Wyszukiwanie binarne – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 i p = 0
B^k= 1. Zatem a = b^koraz p> -1 [Przypadek 2.(a)]
T(n) = θ(n^dziennik_BAdziennik^p+1N)
T(n) = θ(logn) Przykład-2: Sortowanie przez scalanie – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
B^k= 2. Zatem a = b^koraz p> -1 [Przypadek 2.(a)]
T(n) = θ(n^dziennik_BAdziennik^p+1N)
T(n) = θ(nlogn) Przykład-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
B^k= 4. Zatem a k i p = 0 [Przypadek 3.(a)]
T(n) = θ(n^kdziennik^PN)
T(n) = θ(n²)

Przykład-4: T(n) = 3T(n/2) + log²N
a = 3, b = 2, k = 0, p = 2
B^k= 1. Zatem a> b^k[Przypadek 1]
T(n) = θ(n^dziennik_BA)
T(n) = θ(n^dziennik₂3)

Przykład 5: T(n) = 2T(n/2) + nlog²N
a = 2, b = 2, k = 1, p = 2
B^k= 2. Zatem a = b^k[Przypadek 2.(a)]
T(n) = θ(n^dziennik_BAdziennik^p+1N )
T(n) = θ(n^dziennik₂2dziennik³N)
T(n) = θ(nlog³N)

Przykład 6: T(n) = 2^NT(n/2) + n^N
Tego powtarzania nie można rozwiązać powyższą metodą, ponieważ funkcja nie ma postaci T(n) = aT(n/b) + θ(n^kdziennik^PN)

Pytania praktyczne GATE –

• GATE-CS-2017 (zestaw 2) | Pytanie 56
• Brama IT 2008 | Pytanie 42
• BRAMA CS 2009 | Pytanie 35

Oto kilka ważnych punktów, o których należy pamiętać w związku z Twierdzeniem Głównym:

1. Dziel i zwyciężaj nawroty: Główne twierdzenie zostało specjalnie zaprojektowane do rozwiązywania relacji powtarzania, które powstają w analizie algorytmów dziel i zwyciężaj.
2. Forma rekurencji: Główne twierdzenie ma zastosowanie do relacji rekurencji w postaci T(n) = aT(n/b) + f(n), gdzie a, b i f(n) są funkcjami dodatnimi, a n jest wielkością problemu.
3. Złożoność czasowa: Główne Twierdzenie zapewnia warunki rozwiązania powtarzania się w postaci O(n^k) dla pewnej stałej k i podaje wzór na określenie wartości k.
4. Wersja zaawansowana: Zaawansowana wersja Głównego Twierdzenia zapewnia bardziej ogólną formę twierdzenia, która może obsługiwać relacje powtarzania, które są bardziej złożone niż forma podstawowa.
5. Ograniczenia: Główne Twierdzenie nie ma zastosowania do wszystkich relacji rekurencji i nie zawsze może zapewnić dokładne rozwiązanie danej rekurencji.
6. Przydatne narzędzie: Pomimo swoich ograniczeń, Twierdzenie Główne jest użytecznym narzędziem do analizy złożoności czasowej algorytmów dziel i zwyciężaj i stanowi dobry punkt wyjścia do rozwiązywania bardziej złożonych powtórzeń.
7. Uzupełnione innymi technikami: W niektórych przypadkach twierdzenie główne może wymagać uzupełnienia innymi technikami, takimi jak metoda podstawienia lub metoda iteracji, aby całkowicie rozwiązać daną relację powtarzania.