W tym samouczku dowiesz się, czym jest twierdzenie główne i jak jest używane do rozwiązywania relacji rekurencji.
Metoda główna to wzór na rozwiązanie relacji powtarzania postaci:
T (n) = aT (n / b) + f (n), gdzie n = rozmiar wejścia a = liczba podproblemów w rekursji n / b = rozmiar każdego podproblemu. Zakłada się, że wszystkie podproblemy mają ten sam rozmiar. f (n) = koszt pracy wykonanej poza wywołaniem rekurencyjnym, który obejmuje koszt podzielenia problemu i koszt łączenia rozwiązań Tutaj a ≧ 1 i b> 1 są stałymi, a f (n) jest asymptotycznie dodatnią funkcjonować.
Funkcja asymptotycznie dodatnia oznacza, że dla wystarczająco dużej wartości n mamy f(n)> 0.
Twierdzenie główne służy do obliczania złożoności czasowej relacji rekurencyjnych (algorytmów dziel i zwyciężaj) w prosty i szybki sposób.
Twierdzenie mistrzowskie
Jeśli a ≧ 1i b> 1są stałymi i f(n)są funkcją asymptotycznie dodatnią, to złożoność czasowa relacji rekurencyjnej jest określona przez
T (n) = aT (n / b) + f (n) gdzie T (n) ma następujące asymptotyczne granice: 1. Jeśli f (n) = O (n log b a-ϵ ), to T (n ) = Θ (n log b a ). 2. Jeśli f (n) = Θ (n log b a ), to T (n) = Θ (n log b a * log n). 3. Jeśli f (n) = Ω (n log b a + ϵ ), to T (n) = Θ (f (n)). ϵ> 0 jest stałą.
Każdy z powyższych warunków można interpretować jako:
- Jeśli koszt rozwiązania podproblemów na każdym poziomie wzrośnie o pewien czynnik, wartość
f(n)będzie wielomianowo mniejsza niż . Zatem złożoność czasowa jest uciskana kosztem ostatniego poziomu, tj.nlogb anlogb a - Jeśli koszt rozwiązania podproblemu na każdym poziomie jest prawie równy, wówczas wartość
f(n)będzie . Zatem złożoność czasowa będzie razy łączna liczba poziomów, tj.nlogb af(n)nlogb a * log n - Jeśli koszt rozwiązania podproblemów na każdym poziomie zmniejszy się o pewien współczynnik, wartość
f(n)będzie wielomianowo większa niż . W związku z tym złożoność czasowa jest obciążona kosztami .nlogb af(n)
Rozwiązany przykład twierdzenia głównego
T (n) = 3 T (n / 2) + n2 Tutaj a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 tj. f (n) <n log b a + ϵ , gdzie ϵ jest stałą. Przypadek 3 sugeruje tutaj. Zatem T (n) = f (n) = Θ (n 2 )
Ograniczenia twierdzenia głównego
Twierdzenia głównego nie można użyć, jeśli:
- T (n) nie jest monotonne. na przykład.
T(n) = sin n f(n)nie jest wielomianem. na przykład.f(n) = 2n- a nie jest stałą. na przykład.
a = 2n a < 1
