如何解决:T(n)= T(n/2)+ T(n/4)+ T(n/8)+(n)

Question

我知道如何对只调用一次的算法进行递归关系,但我不确定如何在一次出现时多次调用自身.

例如:

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

Answer 1

使用递归树.请参阅CLRS"算法简介"中的递归树的最后一个示例.

T(n)= T(n/2)+ T(n/4)+ T(n/8)+ n.根将是n(成本)并分为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)路径长度最长......

这不一定是一个完整的三元树... height = log of base 2 of n&#of leaves必须小于n ...

希望,可能这样你可以解决问题.

Answer 2

请参阅图片以获得更好的解释-

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

Answer 3

就像编码斐波那契数列（困难的方法）一样，您只需输入以下内容：

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);
}

该代码一次只会执行其中一个调用，并且很可能按照您输入的从左到右的顺序执行，这样您就不必真正担心需要执行的次数。打电话给某事。