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)。