这是一个简单的 C 程序：
int f(int n) {
if(n==0 || n==1) {
return n;
} else {
return 2 * f(n - 1) + 3 * f(n - 2);
}
}
该程序具有指数时间复杂度。您可以在此函数调用图中看到这一点f(5)：
我想证明该函数仅使用递推方程具有指数复杂性，而不是通过绘制图表和计算函数调用的数量。
我想出的递归关系是
T(n) = T(n-1) + T(n-2) + c
扩展给
T(n) = 2T(n - 2) + T(n - 3) + 2c
但是，我不知道如何进一步解决这个问题。如何解决这种递归关系？
对于初学者，您的重复需要某种基本情况，否则当您达到 0 时它是未定义的。为简单起见，假设
T(0) = 一个
T(1) = a + b
T(n + 2) = T(n) + T(n + 1) + c
让我们开始扩展这个递归的前几个术语：
这里有一个非常有趣的模式正在形成。让我们分别看一下 a、b 和 c 项的系数。a 项的系数遵循模式
1, 1, 2, 3, 5, 8, 13, 21, ...
这是斐波那契数列，偏移了一步。b项的系数是
0, 1, 1, 2, 3, 5, 8, 13, ...
这正是斐波那契数列。最后，让我们看一下c术语：
0, 0, 1, 2, 4, 7, 12, 20, ...
嗯，这看起来并不熟悉。但是，如果我们将它与 a 项放在一起，我们会看到：
答：1、1、2、3、5、8、13、21、...
b: 0, 0, 1, 2, 4, 7, 12, 20, ...
请注意，b 项都是 a 项减去一个！换句话说，它是将斐波那契数列移动了一步，但从每个项中减去 1。
基于这些观察，我们可以推测以下情况是正确的：
T(n) = aF n+1 + bF n + c(F n+1 - 1)
我们现在可以尝试通过归纳来证明这一点。作为我们的基本案例：
T(0) = a = 1a + 0b + 0c = 1a + 0b + (1 - 1)c = aF 1 + bF 0 + c(F 1 - 1)
T(1) = a + b = 1a + 1b + 0c = 1a + 1b + (1 - 1)c = aF 2 + bF 1 + c(F 2 - 1)
对于我们的归纳步骤，让我们假设对于某个自然数 n，
T(n) = aF n+1 + bF n + c(F n+1 - 1)
然后
T(n + 1) = aF n+2 + bF n + 1 + c(F n+2 - 1)
然后我们有
T(n + 2) = T(n) + T(n + 1) + c
= aF n+1 + bF n + c(F n+1 - 1) + aF n+2 + bF n + 1 + c(F n+2 - 1) + c
= a(F n+1 + F n+2 ) + b(F n + F n+1 ) + c(F n+1 + F n+2 - 2 + 1)
= aF n+3 + bF n+2 + c(F n+3 - 1)
这样就完成了归纳，所以我们的公式一定是正确的！
那么这与效率有什么关系呢？嗯，Binet 的公式告诉我们 F n = Θ(φ n )，其中 φ 是黄金比例（大约 1.61）。这意味着
T(n) = aF n+1 + bF n + c(F n+1 - 1) = aΘ(φ n ) + bΘ(φ n ) + cΘ(φ n ) = Θ((a + b + c) φn ) _
所以只要 a + b + c ≠ 0，运行时间就是 Θ(φ n )，它是指数的。
希望这可以帮助！