c++ - 具有两个递归调用的算法的复杂性

我有一个奇怪的算法，比被递归调用2次。它的

int alg(int n)
   loop body = Θ(3n+1)
   alg(n-1);
   alg(n-2)

我不知何故需要找到此算法的复杂性。我试图使用上述方程式的特征多项式找到它，但是结果系统很难求解，所以我想知道是否还有其他直接的方法。

最佳答案

复杂度:alg(n) = Θ(φ^n)，其中φ=黄金比率= (1 + sqrt(5)) / 2
一开始我不能正式证明它，但是经过一夜的工作，我发现了我缺少的部分-用减去一个低阶术语的替换方法。对不起，我的证明不好(∵英语不好)。

让loop body = Θ(3n+1) ≦ tn
假设(猜测)该cφ^n ≦ alg(n) ≦ dφ^n - 2tn为n (n ≧ 4)
考虑alg(n+1):

Θ(n)+ alg(n)+ alg(n-1)≤alg(n + 1)≦Θ(n)+ alg(n)+ alg(n-1)
c *φ^ n + c *φ^(n-1)≤alg(n + 1)≤tn +dφ^ n-2tn +dφ^(n-1)-2t(n-1)
c *φ^(n + 1)≤alg(n + 1)≤tn + d *φ^(n + 1)-4tn + 2
c *φ^(n + 1)≤alg(n + 1)≤d *φ^(n + 1)-3tn + 2
c *φ^(n + 1)≤alg(n + 1)≤d *φ^(n + 1)-2t(n + 1)(∵n≥4)

因此，它对于n + 1是正确的。通过数学归纳，我们可以知道对于所有n都是正确的。

依次为cφ^n ≦ alg(n) ≦ dφ^n - 2tn和alg(n) = Θ(φ^n)。

关于c++ - 具有两个递归调用的算法的复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16507791/