algorithm - 运行时间是多少：T(n) = 2T(n-1) + 3T(n-2)+ 1

Question

我知道它类似于具有指数运行时间的斐波那契数列。然而，这种递归关系有更多的分支。的渐近界是T(n) = 2T(n-1) + 3T(n-2)+ 1什么？

Answer 1

通常，您需要对 T(0) 和 T(1) 做出一些假设，因为它们的数量会成倍增加，并且它们的值可能会决定 T(n) 的函数形式。但是在这种情况下，这似乎并不重要。

然后，这种形式的递推关系可以通过找到它们的特征多项式来解决。我发现这篇文章： http: //www.wikihow.com/Solve-Recurrence-Relations

我得到了根为 3 和 1 的特征多项式，因此猜到了形式T(n) = c_1*3^n + c_2。特别是，T(n) = 1/2*3^n - 1/4满足递归关系，我们可以验证这一点。

1/2*3^n - 1/4 = 2*T(n-1) + 3*T(n-2) + 1
              = 2*(1/2*3^(n-1) - 1/4) + 3*(1/2*3^(n-2) - 1/4) + 1
              = 3^(n-1) - 1/2 + 1/2*3^(n-1) - 3/4 + 1
              = 3/2*3^(n-1) - 1/4
              = 1/2*3^n - 1/4

因此它会给出那个T(n) = Theta(3^n)。但是，这可能不是满足递归的唯一函数，其他可能性也取决于您定义的值T(0)和T(1)，但它们都应该是O(3^n)。

Answer 2

这种类型的递归称为：非齐次递归关系，您必须在一开始就解决齐次递归（最后没有常数的递归）。如果您有兴趣，请阅读其背后的数学。

我会告诉你一个简单的方法。只需在wolfram-alpha中输入您的方程，您将得到：

,

这显然是指数级的复杂性：O(3^n)