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

Question

我有一个比被递归调用 2 次更奇怪的算法。这是

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

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

Answer 1

复杂性:alg(n) = Θ(φ^n) 其中 φ = 黄金比例 = (1 + sqrt(5))/2

起初我无法正式证明它，但经过一夜的工作，我找到了我遗漏的部分 - 替换方法 减法 低阶术语。对不起，我的证明表达不好(∵英语不好)。

---

令 循环体 = Θ(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)。