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

我知道它类似于斐波那契序列，它有一个指数运行时间。但是这种递推关系有更多的分支T(n) = 2T(n-1) + 3T(n-2)+ 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)。

关于algorithm - T(n)= 2T(n-1)+ 3T(n-2)+1的运行时间是多少，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14990689/