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

Question

我有一个奇怪的算法,而不是递归调用2次.它的

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

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

Answer 1

假设：

\n\n

1：n >= 0

\n\n

2：\xce\x98(3n+1) = 3n + 1

\n\n

复杂：

\n\n

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

\n\n

推理：

\n\n

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

\n\n

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

\n\n

步骤n：

\n\n

3 * n + 1\nalg(n - 1) => 3 * (n - 1) + 1\nalg(n - 2) => 3 * (n - 2) + 1\n

\n\n

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

\n\n

                                       n\n                 n-1                                  n-2\n          n - 2        n - 3                     n - 3       n - 4\n     n - 3   n - 4   n - 4 n - 5              n - 4 n - 5  n - 5  n - 6\n    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

\n\n

很明显，这里有一个重复模式。(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\n

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

\n\n

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

\n\n

如果将 1 到 n 相加，您应该会得到所需的结果。我将扩展表达式：

\n\n

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

\n\n

更新

\n\n

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

\n\n

就你而言，这最终是：

\n\n

2^n - 1\n

\n\n

根据求和公式，k = 0, n 。现在是第一个：

\n\n

3k * 2 ^ (k - 1)\n

\n\n

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

\n\n

所以你有了：

\n\n

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

\n\n

其中签约的是：

\n\n

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

\n