运行时复杂度 |使用马斯特定理进行递归计算

Question

所以我遇到了一个情况，我有 2 个递归调用 - 而不是一个。我确实知道如何解决一个递归调用，但在这种情况下我不确定我是对还是错。

我有以下问题：

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

我需要为此找到最坏情况下的复杂度。（仅供参考 - 这是某种增强合并排序）

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

Answer 1

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

                                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

 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 )

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

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

运行时复杂度 |使用马斯特定理进行递归计算

Runtime Complexity | Recursive calculation using Master's Theorem

recursion

mergesort

master-theorem