Calcul de la complexité pour un algorithme récursif avec des relations codépendantes

Question

J'ai récemment écrit un programme basé sur un algorithme récursif, résolvant le nombre de façons de mosaïquer un tableau 3xn avec des dominos 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

J'ai essayé de calculer la complexité en utilisant des méthodes que je connais, telles que l'arbre de récursivité et l'expansion, mais aucune n'a donné de réponse.En fait, je n'avais jamais rencontré une telle récursion, où les relations sont codépendantes.

Est-ce que j’utilise les mauvaises méthodes, ou peut-être que j’utilise les méthodes de la mauvaise manière ?Et si oui, quelqu'un peut-il proposer une solution ?

Answer 1

Notons que $F(n) = G(n+1) - G(n-1)$.Donc$$ g (n + 1) -g (n-1) = g (n-1) - g (n-3) + 2g (n-1), $$ce qui implique que$$ g (n + 1) = 4g (n-1) - g (n-3).$$

De la même manière, $G(n) = (F(n+1)-F(n-1))/2$, et ainsi$$ (f (n + 1) -f (n-1)) / 2 = (f (n-1) -f (n-3)) / 2 + f (n-1), $$ce qui implique que$$ f (n + 1) = 4f (n-1) - f (n-3).$$Ce sont exactement les mêmes récurrences, mais avec des valeurs initiales différentes.

Une simple induction montre que $F(n) = 0$ pour bizarre $n$ alors que $G(n) = 0$ même pour $n$ (cela découle également de leur signification sémantique).

En utilisant la récurrence, nous obtenons facilement cela même pour $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}.$$Notons que cette séquence est A001835.

De même, pour les impairs $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}.$$Cette séquence est A001353.

---

Alternativement, nous pouvons remarquer quedollars n-2) g (n-1) end {pmatrix} $$Il s'ensuit que$$ begin {Pmatrix} f (2m) g (2m + 1) end {pmatrix} = begin {PMATRIX} 1 & 2 1 & 3 end {PMATRIX} ^ M Begin {PMATRIX} 1 1 end {Pmatrix} $$Les valeurs propres de la matrice sont $2 \pm \sqrt{3}$, et nous sommes ainsi conduits aux formules indiquées ci-dessus.