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

EN

使用递归树。参见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) n^0.5

看看树-一直到log_8(n)级树是满的，然后当我们向下走时，越来越多的内部节点缺失。通过这个理论，我们可以给出界限，

T(n) =大-Oh( j=0 to log_2( n) -1 (7/8)^j n)= ... => T(n) = O(n).T(n) = Big-Omega ( j=0 to log_8( n) -1 (7/8)^j n)= ... => T(n) = Big-Omega(n).

因此，T(n) =θ(N)。

这里的要点是: T(n/2)路径具有最高长度...

这不能是一个完整的三叉树。高度=n和叶数的对数底2必须小于n ...

希望通过这种方式你可以解决这个问题。

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

在本例中为g(x) = n、a1 = a2 = a3 = 1和b1 = 1/2、b2 = 1/4、b3 = 1/8。解这个方程

​

​

这就是你得到的p = 0.87915。解出你将得到的积分

，这意味着复杂性是：O(n)

有关的更好解释，请参见图片--

​

​

树的高度:我们取(N)(基数2)，因为n/2使树比n/4和n/8更长。我们的GP系列将一直到k=logn(基数)。