Calcolando la complessità per l'algoritmo ricorsivo con relazioni in codependent

Question

Ho scritto un programma recentemente basato su un algoritmo ricorsivo, risolvendo per il numero di modi per piastrellare una scheda 3xN con Domino 2x1:

.

f (n)= f (n-2) + 2 * g (n-1)

g (n)= g (n-2) + f (n-1)

F (0)= 1, f (1)= 0, G (0)= 0, G (1)= 1

Ho provato a calcolare la complessità usando i metodi che conosco come l'albero di ricorsione e l'espansione, ma nessuno ha comportato alcuna risposta.In realtà non avevo mai imbattuto in una tale ricorsione, dove le relazioni sono codependenti.

Sto usando i metodi sbagliati o forse usando i metodi in modo sbagliato?E se sì, qualcuno può offrire una soluzione?

Answer 1

Nota di notare che $ f (n)= g (n + 1) - g (n-1) $ . Perciò $$ G (N + 1) -G (N-1)= G (N-1) - G (N-3) + 2G (N-1), $$ implicando ciò $$ G (N + 1)= 4G (N-1) - G (N-3). $$

Allo stesso modo, $ g (n)= (f (n + 1) -f (n-1)) / 2 $ , e così $$ (F (N + 1) -F (N-1)) / 2= (f (N-1) -F (N-3)) / 2 + F (N-1), $$ implicando ciò $$ F (N + 1)= 4F (N-1) - F (N-3). $$ Queste sono esattamente le stesse recidive, anche se con diversi valori iniziali.

Un'induzione semplice mostra che $ f (n)= 0 $ per dispari $ N $ while $ G (n)= 0 $ per persino $ N $ (Questo segue anche dal loro significato semantico) .

Usando la ripetizione, lo otteniamo facilmente per $ N $ , $$ F (n)= (1/2 + 1/2 \ sqrt {3}) (2 + \ sqrt {3}) ^ {n / 2} + (1/2 - 1/2 \ sqrt {3}) ( 2 - \ SQRT {3}) ^ {N / 2}. $$ Commentiamo che questa sequenza è A001835 .

Allo stesso modo, per dispari $ N $ , $$ G (N)= (1/2 + 1 / \ SQRT {3}) (2 + \ SQRT {3}) ^ {(n-1) / 2} + (1/2 - 1 / \ sqrt {3} ) (2 - \ sqrt {3}) ^ {(n-1) / 2}. $$ Questa sequenza è A001353 .

---

.

In alternativa, possiamo notarlo $$ \ Begin {Pmatrix} F (n) \\ G (n + 1) \ End {Pmatrix}= \ Begin {Pmatrix} 1 e 2 \\ 1 e 3. \ End {Pmatrix} \ Begin {Pmatrix} F (n-2) \\ G (N-1) \ End {Pmatrix} $$ Ne consegue che $$ \ Begin {Pmatrix} F (2m) \\ G (2m + 1) \ End {Pmatrix}= \ Begin {Pmatrix} 1 e 2 \\ 1 e 3. \ End {Pmatrix} ^ m \ Begin {Pmatrix} 1 \\ 1. \ End {Pmatrix} $$ Gli autovalori della matrice sono $ 2 \ pm \ sqrt {3} $ , e quindi siamo portati a formule come sopra indicato.