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

起初我无法正式证明它，但经过一夜的工作，我找到了我缺少的部分 -减去低阶项的替换方法。对不起，我的证明表达不好（∵英语很差）。

---

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

Answer 2

johnchen902是正确的：

alg(n)=Θ(φ^n)在哪里φ = Golden ratio = (1 + sqrt(5)) / 2

但他的论点有点过于摇摆不定，所以让我们严格一点。他最初的论点不完整，因此我添加了我的论点，但现在他已经完成了论点。

---

loop body = Θ(3n+1)

让我们用 来表示参数的循环体n成本g(n)。那么g(n) ∈ Θ(n)自Θ(n) = Θ(3n+1).

此外，设为T(n)的总成本。然后，因为我们有递归alg(n)n >= 0n >= 2

T(n) = T(n-1) + T(n-2) + g(n)

对于n >= 3，我们可以将应用于的递归T(n-1)插入其中，

T(n) = 2*T(n-2) + T(n-3) + g(n) + g(n-1)

对于n > 3，我们可以继续，将递归应用于T(n-2)。对于足够大n的 ，因此我们有

T(n) = 3*T(n-3) + 2*T(n-4) + g(n) + g(n-1) + 2*g(n-2)
     = 5*T(n-4) + 3*T(n-5) + g(n) + g(n-1) + 2*g(n-2) + 3*g(n-3)
     ...
                                       k-1
     = F(k)*T(n+1-k) + F(k-1)*T(n-k) +  ∑ F(j)*g(n+1-j)
                                       j=1

                                 n-1
     = F(n)*T(1) + F(n-1)*T(0) +  ∑ F(j)*g(n+1-j)
                                 j=1

与斐波那契数F(n)[ F(0) = 0, F(1) = F(2) = 1]。

T(0)并且T(1)是一些常数，所以第一部分显然是Θ(F(n))。仍有待调查总和。

因为g(n) ∈ Θ(n)，我们只需要调查

       n-1
A(n) =  ∑ F(j)*(n+1-j)
       j=1

现在，

                 n-1
A(n+1) - A(n) =   ∑ F(j) + (((n+1)+1) - ((n+1)-1))*F((n+1)-1)
                 j=1

                n-1
              =  ∑ F(j)  + 2*F(n)
                j=1

              = F(n+1) - 1 + 2*F(n)
              = F(n+2) + F(n) - 1

总和，从 开始A(2) = 2 = F(5) + F(3) - 5，我们得到

A(n) = F(n+3) + F(n+1) - (n+3)

因此，与

c*n <= g(n) <= d*n

估计

F(n)*T(1) + F(n-1)*T(0) + c*A(n) <= T(n) <= F(n)*T(1) + F(n-1)*T(0) + d*A(n)

为n >= 2. 因为F(n+1) <= A(n) < F(n+4)，所有依赖于n不等式左右部分的项都是Θ(φ^n), qed

Answer 3

假设：

1：n >= 0

2：Θ(3n+1) = 3n + 1

复杂：

O(2 ^ n * (3n - 2));

推理：

int alg(int n)
   loop body = Θ(3n+1)// for every n you have O(3n+1)
   alg(n-1);
   alg(n-2)

假设 alg 在 n < 1 时不执行，您有以下重复：

第 n 步：

3 * n + 1
alg(n - 1) => 3 * (n - 1) + 1
alg(n - 2) => 3 * (n - 2) + 1

现在你基本上有了一个部门。您必须想象一个数字树，其中 N 作为父级，n-1 和 n-2 作为子级。

                                       n
                 n-1                                  n-2
          n - 2        n - 3                     n - 3       n - 4
     n - 3   n - 4   n - 4 n - 5              n - 4 n - 5  n - 5  n - 6
    n-4 n-5 | n-5 n-6 |n-5 n-6 |n-6 n-7    n-5 n-6 n-6 n-7  n-6 n-6| n-6 n-8

很明显，这里有一个重复模式。(n - k, n - k - 1) in A = {k, with k from 0 to n)对于除前两个和后两个之外的每一对，(n - 1, n - 2) and (n-2, n-3)都有3k + 1 * (2 ^ (k - 1))复杂性。

我正在查看该对的重复次数(n - k, n - k - 1)。所以现在对于每个我有k：0 to n

(3k + 1) * (2 ^ (k - 1)) iterations.

如果你从 1 到 n 总结，你应该得到想要的结果。我将扩展表达式：

(3k + 1) * (2 ^ (k - 1)) = 3k * 2 ^ (k - 1) + 2 ^ (k - 1)

更新

1 + 2 + 2^2 + 2^3 + ... + 2^n = 2 ^ (n + 1) - 1

在你的情况下，这最终是：

2^n - 1

基于求和公式和 k = 0, n 。现在第一个：

3k * 2 ^ (k - 1)

这等于 3 的总和k = 0, n of k * 2 ^ (k - 1)。这个和可以通过切换到多项式函数、积分、使用1 + a ^ 2 + a ^ 3 + ... + a ^ n公式收缩来确定，然后再次微分得到结果，即(n - 1) * 2 ^ n + 1.

所以你有了：

2 ^ n - 1 + 3 * (n - 1) * 2 ^ n + 1

签约的是：

2 ^ n * (3n - 2);

Answer 4

函数的主体需要Θ(n)时间。该函数被递归调用两次。

对于给定的函数，复杂度是，

     T(n) = T(n-1) + T(n-2) + cn        -----  1
     T(n-1) = T(n-2) + T(n-3) + c(n-1)  -----  2

1-2 ->   T(n) = 2T(n-1) - T(n-3) + c        -----  3

3 -->    T(n-1) = 2T(n-2) + T(n-4) + c      -----  4

3-4 ->   T(n) = 3T(n-1) - 2T(n-2) - T(n-3) - T(n-4) ----- 5

让g(n) = 3g(n-1)

在那里，我们可以近似T(n) = O(g(n))

g(n) 是Θ(3 ⁿ )

对于T(n) = O(3 ⁿ )