Расчет сложности для рекурсивного алгоритма с кодезависимыми отношениями

Question

Я написал программу недавно, которая была основана на рекурсивом алгоритме, решение для количества способов плитки 3XN досок с 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

Я пытался рассчитать сложность, используя методы, которые я знаю, таких как рекурсионное дерево и расширение, но никто не привел к любому ответу.На самом деле я никогда не встречал такую рекурсию, где отношения являются кодом.

Я использую неправильные методы, или, возможно, используя методы неправильно?И если это так, может кто-нибудь предложить решение?

Answer 1

Отметим, что $ f (n)= g (n + 1) - g (n - 1) $ . Следовательно $$ G (N + 1) -G (N-1)= G (N-1) - G (N-3) + 2G (N-1), $$ подразумевая это $$ G (N + 1)= 4G (N-1) - G (N-3). $$

Точно так же, $ g (n)= (f (n + 1) -f (n - 1)) / 2 $ , и так $$ (F (N + 1) -F (N-1)) / 2= (F (N-1) -F (N-3)) / 2 + F (N-1), $$ подразумевая это $$ F (n + 1)= 4f (N-1) - F (N-3). $$ Это точно такие же рецидивы, хотя и с разными начальными значениями.

Простая индукция показывает, что $ f (n)= 0 $ для нечетных $ n $ пока $ g (n)= 0 $ для четных $ n $ (это также следует из их семантического значения) ,

Использование рецидива, мы легко получаем это для даже $ 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}. $$ Давайте комментируем, что эта последовательность a001835 .

аналогично, для нечетного $ 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}. $$ Эта последовательность A001353 .

---

альтернативно, мы можем заметить, что $$ \ begin {pmatrix} F (n) \\ G (n + 1) \ end {pmatrix}= \ begin {pmatrix} 1 & 2 \\ 1 и 3 \ end {pmatrix} \ begin {pmatrix} F (N-2) \\ G (N-1) \ end {pmatrix} $$ Следует, что $$ \ begin {pmatrix} F (2m) \\ G (2 м + 1) \ end {pmatrix}= \ begin {pmatrix} 1 & 2 \\ 1 и 3 \ end {pmatrix} ^ m \ begin {pmatrix} 1 \\ 1. \ end {pmatrix} $$ Собственные значения матрицы - $ 2 \ PM \ SQRT {3} $ , и поэтому мы приводим к формулам, как указано выше.