algorithm - 如何解决这个递归关系: T(n) = T(n-1) * T(n-2)

Question

考虑这个递归关系:

T(n) = T(n-1) * T(n-2)    n>2
T(1) = 1, T(2) = 2

我该如何解决？最后:T(n) = O(?)

我认为我们应该记录双方的日志或类似的东西。但是我没有继续的想法。

Answer 1

首先对两部分取对数得到:

log(T(n)) = log(T(n-1)) + log(T(n-2))

现在你用 log(T(n)) 代替它到 K(n) 所以你必须解决问题 K(n) = K(n-1) + K(n-2) .做类似的事情你会得到解决方案

K(n) = c1 * F(n) + c2 * L(n)，其中 F(n) 是 Fibonacci number L(n) 是 Lucas number而 c1, c2 只是一些常量。所以现在要得到你的答案，你只需要恢复对数。

所以你的解决方案是e^(c1 * F(n) + c2 * L(n))。按照我之前的解释，这个的复杂度是 O(e^(phi^n))