运行时复杂度|使用Master定理进行递归计算 [英] Runtime Complexity | Recursive calculation using Master's Theorem

问题描述

因此，我遇到了2个递归调用的情况，而不是一个.我确实知道如何解决一个递归调用，但是在这种情况下，我不确定我是对还是错.

So I've encountered a case where I have 2 recursive calls - rather than one. I do know how to solve for one recursive call, but in this case I'm not sure whether I'm right or wrong.

我有以下问题:

T(n)= T(2n/5)+ T(3n/5)+ n

T(n) = T(2n/5) + T(3n/5) + n

我需要为此找到最坏的情况. (仅供参考-这是一种增强的合并排序)

And I need to find the worst-case complexity for this. (FYI - It's some kind of augmented merge sort)

我的感觉是使用定理中的第一个方程，但是我觉得我的想法有问题.关于如何解决这样的问题的任何解释将不胜感激:)

My feeling was to use the first equation from the Theorem, but I feel something is wrong with my idea. Any explanation on how to solve problems like this will be appreciated :)

推荐答案

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

The recursion tree for the given recursion will look like this:

                                Size                        Cost

                                 n                           n
                               /   \
                             2n/5   3n/5                     n
                           /   \     /    \
                       4n/25  6n/25  6n/25  9n/25            n

                         and so on till size of input becomes 1

从根到叶子的渴望简单路径为n-> 3/5n->(3/5)^ 2 n ..直到1

The longes simple path from root to a leaf would be n-> 3/5n -> (3/5) ^2 n .. till 1

 Therefore  let us assume the height of tree = k

            ((3/5) ^ k )*n = 1 meaning  k = log to the base 5/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 5/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 5/3 of n)

          which  is O( n * log n )

现在，让我们使用替代方法进行验证:

Now, let us verify this using substitution method:

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

 Assuming this to be true:

 T(n) = T(2n/5) + T(3n/5) + n

      <= d(2n/5)log(2n/5) + d(3n/5)log(3n/5) + n

       = d*2n/5(log n  - log 5/2 )  + d*3n/5(log n  - log 5/3) + n

       = dnlog n  - d(2n/5)log 5/2 - d(3n/5)log 5/3  + n

       = dnlog n  - dn( 2/5(log 5/2)  -  3/5(log 5/3)) + n

       <= dnlog n

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

这篇关于运行时复杂度|使用Master定理进行递归计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！