성적 관계가있는 재귀 알고리즘의 복잡성을 계산하는 것

Question

나는 최근에 재귀 알고리즘을 기반으로 한 프로그램을 작성하여 2x1 도미노가있는 3xn 보드를 타일 수있는 방법의 수를 해결합니다.

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

재귀 트리 및 확장과 같은 방법을 사용하여 복잡성을 계산하려고 시도했지만 아무도 대답하지 않았습니다.실제로 나는 관계가 coldependent이되는 재귀를 결코 보지 못했습니다.

잘못된 방법을 사용하거나 잘못된 방법으로 방법을 사용할 수 있습니까?그렇다면 누구든지 솔루션을 제공 할 수 있습니까?

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 .

---

또는 우리는 그것을 알 수 있습니다 $$ \ 시작 {pmatrix} f (n) \\ g (n + 1) \ end {pmatrix}= \ 시작 {pmatrix} 1 & 2 \\ 1 & 3. \ end {pmatrix} \ 시작 {pmatrix} f (n-2) \\ g (n-1) \ end {pmatrix} $$ 그것은 이어진다 $$ \ 시작 {pmatrix} f (2M) \\ g (2m + 1) \ end {pmatrix}= \ 시작 {pmatrix} 1 & 2 \\ 1 & 3. \ end {pmatrix} ^ M. \ 시작 {pmatrix} 1 \\ 1 \ end {pmatrix} $$ 매트릭스의 고유 값은 $ 2 \ pm \ sqrt {3} $ 이므로 위에 언급 한 바와 같이 수식으로 이어집니다.