无需迭代即可解决递归关系

Question

我该如何解决这个问题？

T(n) = T(n/4) + T(3n/4) + cn

答案是 \theta(nLogn)

如何使用主定理或任何其他有效方法来获得这个答案？

Answer 1

给定递归的递归树如下所示：

                                Size                        Cost

                                 n                           n
                               /   \
                             n/4   3n/4                      n
                           /   \     /    \
                        n/16  3n/16 3n/16  9n/16             n

                        and so on till size of input becomes 1

从根到叶的最长简单路径是 n-> 3n/4 -> (3/4) ^2 n .. 直到 1

 Therefore  let us assume the height of tree = k

            ((3/4) ^ k )*n = 1 meaning  k = log to the base 4/3 of n

 In worst case we expect that every level gives a cost of  n and hence 

        Total Cost = n * (log to the base 4/3 of n)

 However we must keep one thing in mind that ,our tree is not complete and therefore

 some levels near the bottom would be partially complete.

 But in asymptotic analysis we ignore such intricate details.

 Hence in worst Case Cost = n * (log to the base 4/3 of n)

          which  is O( n * log n )

现在，让我们用替换法验证一下：

 T(n) =  O( n * log n)  iff T(n) < = dnlog(n) for some d>0

 Assuming this to be true:

 T(n) = T(n/4) + T(3n/4) + n

      <= d(n/4)log(n/4) + d(3n/4)log(3n/4) + n

       = d*n/4(log n  - log 4 )  + d*3n/4(log n  - log 4/3) + n

       = dnlog n  - d(n/4)log 4 - d(3n/4)log 4/3  + n

       = dnlog n  - dn( 1/4(log 4)  -  3/4(log 4/3)) + n

       <= dnlog n

       as long as d >=  1/( 1/4(log 4)  -  3/4(log 4/3) )

无需迭代即可解决递归关系

Solving a Recurrence relation without iteration

recursion

recurrence

time-complexity

big-theta