Calculando a complexidade para algoritmo recursivo com relações codependentes

Question

Eu escrevi recentemente um programa que foi baseado em um algoritmo recursivo, resolvendo o número de maneiras de apertar uma placa 3xn com 2x1 dominós:

.

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

Eu tentei calcular a complexidade usando métodos que conheço, como a árvore de recursão e expansão, mas nenhum resultou em qualquer resposta.Na verdade, eu nunca havia me deparada com tal recursão, onde as relações são codependentes.

Estou usando os métodos errados, ou talvez usar os métodos de maneira errada?E se assim for, alguém pode oferecer uma solução?

Answer 1

Deixe-nos observar que $ f (n)= g (n + 1) - g (n-1) $ . Portanto $$ G (n + 1) -g (N-1)= G (N-1) - G (N-3) + 2G (N-1), $$ implicando isso $$ G (n + 1)= 4G (N-1) - G (N-3). $$

Da mesma forma, $ g (n)= (f (n + 1) -f (n-1)) / 2 $ , e assim $$ (F (N + 1) -F (N-1)) / 2= (F (N-1) -F (N-3)) / 2 + F (N-1), $$ implicando isso $$ F (N + 1)= 4F (N-1) - F (N-3). $$ Estas são exatamente as mesmas recorrências, embora com diferentes valores iniciais.

Uma indução simples mostra que $ f (n)= 0 $ para ímpar $ n $ enquanto $ g (n)= 0 $ para até mesmo $ n $ (isso também segue de seu significado semântico) .

Usando a recorrência, facilmente recebemos isso para até mesmo $ 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}. $$ Vamos comentar que esta sequência é A001835 .

Da mesma forma, para ímpar $ 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}. $$ Esta sequência é A001353 .

---

.

Alternativamente, podemos notar que $$ \ begin {pmatrix} F (n) \\ \\ G (n + 1) \ fim {pmatrix}= \ begin {pmatrix} 1 e 2 \\ 1 e 3. \ fim {pmatrix} \ begin {pmatrix} F (n-2) \\ G (n-1) \ fim {pmatrix} $$ Segue que $$ \ begin {pmatrix} F (2m) \\ G (2m + 1) \ fim {pmatrix}= \ begin {pmatrix} 1 e 2 \\ 1 e 3. \ final {pmatrix} ^ m \ begin {pmatrix} 1 \\ 1. \ fim {pmatrix} $$ Os autovalores da matriz são $ 2 \ pm \ sqrt {3} $ , e por isso somos levados a fórmulas conforme indicado acima.