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

Недавно я написал программу, основанную на рекурсивном алгоритме, вычисляющем количество способов замостить доску 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

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

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

Редактировать: я задал тот же вопрос в CS Stack Exchange, и там также был дан хороший ответ. https://cs.stackexchange.com/questions/124514/calculating-complexity-for-recursive-algorithm-with-codependent-relations


recursion recurrence algorithm tiling time-complexity
person Amir Baghi    schedule 21.04.2020    source источник
comment
Вы можете попробовать задать вопрос на CS Stack Exchange, так как они лучше подготовлены для решения теоретических вопросов. См. также: Какая информатика/программирование Сайты Stack Exchange, на которых я размещаю публикации?   -  person John Kugelman    schedule 21.04.2020
comment
@JohnKugelman Конечно! Цените руководство.   -  person Amir Baghi    schedule 21.04.2020

Ответы (1)


arrow_upward
3
arrow_downward

Он экспоненциальный. Осталось найти базу. Сначала определите векторную функцию V(n) следующим образом.

       ( F(n)   )
V(n) = ( F(n-1) )
       ( G(n)   )
       ( G(n-1) )

И теперь у нас есть V(n) = A * V(n-1), где A — некоторая матрица. Если я не напутал, эта матрица такова:

[ 0 1 2 0 ]
[ 1 0 0 0 ]
[ 1 0 0 1 ]
[ 0 0 1 0 ]

Из ваших начальных условий:

       ( 1 )
V(1) = ( 0 )
       ( 1 )
       ( 0 )

И теперь у нас есть следующее правило. V(n+1) = A^n * V(1). Если вы знакомы с матричной математикой, рост этой экспоненты зависит от ведущего собственного значения. Что (после проверки https://www.dcode.fr/matrix-eigenvalues) происходит быть sqrt(2+sqrt(3)).

So F(n) = O(sqrt(2+sqrt(3))^n).

(Теория, стоящая за этим, обычно объясняется последовательностью Фибоначчи, но ее можно применить к любому разностному уравнению.)

person btilly    schedule 21.04.2020