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

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

2 голосов
/ 21 апреля 2020

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

1 Ответ

2 голосов
/ 21 апреля 2020

Это экспоненциально. Осталось только найти базу. Сначала определим векторную функцию 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)).

То есть F(n) = O(sqrt(2+sqrt(3))^n).

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

...