求解递推关系 T(n)=T(n-1)*T(n-2)+c 其中 T(0)=1 和 T(1)=2

Question

我需要解决

的递推关系

T(n) = T(n - 1) * T(n - 2) + c    where T(0) = 1 and T(1) = 2.

该算法计算 2^f(n)，其中 f(n) 是第 n^th 斐波那契数。我假设 T(n - 2) 约等于 T(n - 1) 然后我将关系重写为

T(n) = T(n - 1)^2 + c

最终我达到了 O(n) 的复杂度。这个算法：

Power(n):
    if n == 0 then x = 1;
    else if n == 1 then x = 2;
    else x = Power(n - 1) * Power(n - 2);
    return x;

递归关系 T(n) = T(n - 1) * T(n - 2) + c 的复杂度是 O(n) 吗？

Answer 1

您混淆了算法中的乘法和递归关系中的乘法。您计算 Power(n - 1) 和 Power(n - 2) 并将它们相乘，但这不需要 T(n - 1) * T(n - 2) 时间。这些值分别计算，然后相乘，假设常数时间乘法，需要 T(n - 1) + T(n - 2) 时间。

循环则变成T(n) = T(n - 1) + T(n - 2) + c。我们将通过替换来解决这个问题。我将跳过选择 n₀;我们的归纳假设将是 T(n) = d * 2^n - 1。（我们需要 -1 来允许稍后取消 c；这称为加强归纳假设，请参见 here）。

T(n) = T(n - 1) + T(n - 2) + c
     = d * (2^(n - 1) - 1) + d * (2^(n - 2) - 1) + c    (substitute by IH)
     = 3d * 2^(n - 2) - 2d + c
    <= d * 2^n - 2d + c                                 (3 < 2^2)
    <= d * 2^n                                          (when d > c / 2)

结论：T(n) ∈ O(2ⁿ).

额外的事实：严格的界限实际上是 Θ(φⁿ)，其中 φ 是黄金比例。有关解释，请参阅 this answer。

Answer 2

首先，对运行时间进行建模的循环对于 T(1) = T(0) = 1 是 T(n) = T(n-1) + T(n-2) + C，对于某些 C>0。这是因为您进行了两次递归调用，一个在 n-1 上，另一个在 n-2.

上

如果我们忘记了额外的常数（它最终贡献了一个因子C），那么你的递归就是Fibonacci recurrence。确切的解决方案是这样的（图片来源：维基百科）：

哪里

和

你可以说 T(n) = Theta(1.618... ^ n).

求解递推关系 T(n)=T(n-1)*T(n-2)+c 其中 T(0)=1 和 T(1)=2

Solving the Recurrence Relation T(n)=T(n-1)*T(n-2)+c where T(0)=1 and T(1)=2

algorithm

recurrence

time-complexity