Nie jestem zaznajomiony z technikami rozwiązywania konfliktów poza głównym twierdzeniem, drzewami rekursji i metodą substytucji. Domyślam się, że rozwiązanie poniższego nawrót do wielkiego-O bound nie wykorzystuje jedną z tych metod:Jak rozwiązać następujące nawroty?
T(n) = T(n-1) + 2T(n-2) + 1
Możemy dokonać zmiany U(n) = T(n) + 1/2 a następnie dostać nawrotu
U(n) = T(n) + 1/2
= T(n-1) + 2T(n-2) + 1 + 1/2
= T(n-1) + 1/2 + 2(T(n-2) + 1/2)
= U(n-1) + 2U(n-2),
który jest mała magia, ale, jak wspomina templatetypedef, magię można stworzyć za pomocą metody anihilatora. Teraz musimy rozwiązać liniowy jednorodny nawrót. Charakterystyczne czynniki wielomianowe jako (x+1)(x-2), więc roztwory są U(n) = a(-1)^n + b2^n, gdzie a i są dowolnymi stałymi. Równoważnie, T(n) = a(-1)^n + b2^n - 1/2, który jest Theta(2^n), z wyjątkiem szczególnych przypadków.
Ta rekurencja nazywa non-homogeneous linear recurrence. i to jest rozwiązane poprzez przekształcenie go w jednorodnej jednym:
T(n) = T(n-1) + 2T(n-2) + 1
T(n+1) = T(n) + 2T(n-1) + 1
Odjęcie 1 od 2 i zmianę podstawy, masz T(n) = 2 T(n-1) + T(n-2) - 2 T(n-3). Odpowiedni charakterystyczny równanie:
x^3 - 2x^2 - x + 2 = 0
który posiada rozwiązania x = {-1, 1, 2}. Oznacza to, że rekurencja wygląda następująco:
c1 * (-1)^n + c2 * 2^n + c3 * 1^n = c1 * 2^n + c2 (-1)^n + c3
Jeżeli wszystkie te stałe można znaleźć wiedząc T (0) i T (1). Dla twojej analizy złożoności jasne jest, że jest to wykładnicza O(2^n).
Jaki jest podstawowy przypadek dla 'T (n)'? –
To jest świetne miejsce do użycia metody anihilatora ... której tak naprawdę nie potrafię. :-) – templatetypedef
Skrzynka bazowa nie jest dostarczana. Zgaduję, że nie jest konieczne, aby osiągnąć duży-O związany? – velen