如何求解：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(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 (Summation j=0 to 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 ...

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

Answer 2

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

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

Answer 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)

Answer 4

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

长 fib(长 n){
 if(n <= 1) 返回 n; 
 否则返回 fib(n-1) + fib(n-2);
}     

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

static ArrayListfib_global = new ArrayList(1000); 
  //delcare 一个可以追加的全局变量
长 fib(长 n){
   if(n >= fib_global.length)fib_global.add(fib(n-1) + fib(n-2));
   返回 fib_global.get(n);
}

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

Answer 5

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

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)

仅此而已。