递归T(n) = T(n-1) + T(n-2) +n？

Question

递归T(n) = T(n-1) + T(n-2) +n的复杂度是多少？我用树方法做了，得到了n*2^n的答案，对吗？

Answer 1

假设我们用另一个函数替换递归调用，从而获得该函数的上、下界：

​

​

我们可以反复替换来导出它们的复杂性(假设停止条件是n = 1)：

​

​

​

​

令人惊讶的是，没有任何因素的n！因此：

一些数值试验以证实：

N   R(N)        T(N)        S(N)
-------------------------------------
10  1.14E+02    3.64E+02    2.04E+03
15  7.49E+02    4.16E+03    6.55E+04
20  4.07E+03    4.63E+04    2.10E+06
25  2.45E+04    5.14E+05    6.71E+07
30  1.31E+05    5.70E+06    2.15E+09
35  7.86E+05    6.32E+07    6.87E+10
40  4.19E+06    7.01E+08    2.20E+12
45  2.52E+07    7.78E+09    7.04E+13
50  1.34E+08    8.63E+10    2.25E+15
55  8.05E+08    9.57E+11    7.21E+16
60  4.29E+09    1.06E+13    2.31E+18
65  2.58E+10    1.18E+14    7.38E+19

​

​

在对数比例图上，这三个函数都是线性的，这意味着它们是指数的，即O(a^n)而不是O(n * a^n)。

如果你不相信这些结果，我建议你自己编写简单的程序来测试它们。

我们能做得更好吗？即为T(n)找出最紧的界限？

我们可以对T(n)进行更通用的表单替换。

​

​

我们可以立即推断出c = -1, d = 0，通过匹配相同的增长率(O(n)表示c，O(1)表示d)。

​

​

我们可以忽略3，它比指数项小得多。用a * b^n划分

​

​

我们可以丢弃较小的根，因为它的大小小于1，这意味着它将收缩而不是增长，因此是渐近无关的。因此：

您可以根据上面的对数数值图：b的梯度来测量和确认b = 10^0.209 = 1.618...的值。也可以确定绑定值：10^0.151 = 1.415... vs sqrt(2) = 1.414...，以及类似的10^0.301 = 1.999...与2。

请注意，基1.618与前面获得的界([1.414, 2])是一致的。

Answer 2

找到了一支笔和一些纸。

是的，你是对的(尽管会有更严格的界限)。

不过，我想给出一个完整性的证明(不是使用树方法，而是使用基于替换和推理的方法，因为我发现了更多的乐趣)。

我们有那个T(n) = T(n-1) + T(n-2) + n。由于我们需要找到一个上界，让我们创建一个更简单的函数T'(n) = 2T(n-1) + m，其中m是一个常量。显然，对于m >= n，这个函数将比T(n)“更大”(见脚注)，因此如果我们能够为这个函数找到一个上界，那么我们就会为原始函数找到一个上界(只要我们选择常量m时大于n )。它还具有更容易建模的优点！

让我们来看看T'(n)的一些行为

T'(n) = 2T'(n-1) +  m
      = 4T'(n-2) + 3m
      = 8T'(n-3) + 7m
      = ...
      = 2^k T'(n-k) + (2^k - 1)m

最后一个方程是通过在任意数k迭代(0 <= k <= n)之后按照逻辑级数进行处理的。

如果我们现在扩展到迭代的末尾，即n = k时，我们有：

T'(n) = 2^n T'(0) + (2^n - 1)m

如果我们让T'(0)是一个常数c0，那么我们有一个T'的上界。

T'(n) = c0*2^n + m*2^n - m

其中c0和m仍然是常量，所以我们还不能对它们做很多事情。

现在我们说，对于所有的T'，T'都比T大，所以让我们说，当我们第一次“调用”T时，我们设置了m = n。也就是说，我们已经将常量设置为n所能承受的最大值。看看我们得到了什么：

T'(n) = c0*2^n + n*2^n - n

因此是O(n*2^n)。太棒了！

对于最后的接触，由于T'比T“大”，对于所有m >= n，而且我们有T'的上限，我们知道T也必须遵守这个上限，所以T也是O(n*2^n)，就像您发现的那样。

请指出任何错误，我可能在某个地方弄错了一些字母！

编辑:真的，您还想证明T'实际上比T大，但这很简单，您可以通过一个常数和另一个和一个递减序列的事实来轻松地说服自己。