9

我知道如何为只调用一次自己的算法做递归关系，但我不确定如何做一次多次调用自己的事情。

例如：

T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
4

5 回答 5

7

使用递归树。请参阅 CLRS "Intro to Algorithm" 中递归树的最后一个示例。

T(n) = T(n/2) + T(n/4) + T(n/8) + n。根将是 n(cost) & 分为 3 个递归。所以递归树如下所示：

T(n) = n = n T(n/2)T(n/4)T(n/8) (n/2) (n/4) (n/8) T(n/4)T(n /8)T(n/16)T(n/8)T(n/16)T(n/32)T(n/16)T(n/32)T(n/64)

                                             n---------------------------------> n      

                             (n/2)         (n/4)           (n/8)--------------> (7/8)n

                         n/4 n/8 n/16  n/8 n/16 n/32  n/16 n/32 n/64)--------> (49/64)n
                                            ...

最长路径：最左边的分支 = n -> n/2 -> n/4 -> ... -> 1

最短分支：最右边的分支 = n -> n/8 -> n->64 -> ... -> 1

叶数（l）：3^log_8(n) < l < 3^log_2(n) => n^0.5 < l < n^1.585

查看树 - 直到 log_8(n) 级别树已满，然后随着我们往下走，越来越多的内部节点不存在。通过这个理论，我们可以给出界限，

T(n) = Big-Oh（求和 j=0 到 log_2(n)-1 (7/8)^jn) = ... => T(n) = O(n)。T(n) = Big-Omega（求和 j=0 到 log_8(n)-1 (7/8)^jn）= ... => T(n) = Big-Omega(n)。

因此，T(n) = Theta(n)。

这里的要点是：T（n / 2）路径具有最长的长度......

这不能是一棵完整的三叉树...高度 = n 的以 2 为底的对数 & # 叶子必须小于 n ...

希望，可能这样你就可以解决问题。

于 2011-08-31T17:24:28.613 回答
3

有两种方法可以解决这个问题。一个是展开递归并找到可能需要创造性并且非常困难的相似之处。另一种方法是使用Akra-Bazzi 方法。

在这种情况下g(x) = n,a1 = a2 = a3 = 1和b1 = 1/2, b2 = 1/4, b3 = 1/8。求解方程

在此处输入图像描述

这是1/2^p + 1/4^p + 1/8^p = 1你得到p = 0.87915的。求解积分你会得到在此处输入图像描述，这意味着复杂性是：O(n)

于 2015-12-13T10:41:29.957 回答
3

查看图片以获得更好的解释-

在此处输入图像描述

树的高度：我们采用 log(n)(base 2)，因为与 n/4 和 n/8 相比，n/2 使树更长。我们的 GP 系列将持续到 k=logn(base)。

于 2019-12-13T07:14:48.323 回答
0

就像编码斐波那契数列（困难的方式）作为示例一样，您只需键入以下内容：

long fib(long n){
 if(n <= 1) return n; 
 else return fib(n-1) + fib(n-2);
}

或者，更好的是，使用全局变量来记忆它以使其更快。再一次，使用斐波那契数列：

static ArrayList<Long>fib_global = new ArrayList(1000); 
  //delcare a global variable that can be appended to
long fib(long n){
   if(n >= fib_global.length)fib_global.add(fib(n-1) + fib(n-2));
   return fib_global.get(n);
}

该代码一次只会执行其中一个调用，并且很可能按照您输入它们的从左到右的顺序执行，这样您就不必担心您需要执行的次数叫什么。

于 2011-04-11T22:35:32.017 回答
0

正如CLRS所说，T(n)可以用cn数学归纳法代替。这种归纳假设适用于以下数字n。如上所述，我们需要证明的是参数值为n。因此，如下：假设：T(n) <= cn对于下面的数字n；得出结论：

T(n) = T(n/2) + T(n/4) + T(n/8) + n
    <= c/2*n + c/4*n + c/8*n + n
     = (7/8*c + 1) * n
    <= cn (when c >= 8)

就这样。

于 2019-04-27T10:55:09.860 回答