运行时复杂性|使用硕士定理的递归计算

问题描述：

所以我遇到了一个情况，我有2个递归调用 - 而不是一个。我知道如何解决一个递归调用，但在这种情况下，我不确定我是对还是错。运行时复杂性|使用硕士定理的递归计算

我有以下问题：

T（N）= T（2N/5）+ T（3N/5）+ N

，我需要找到这个最坏情况下的复杂性。（仅供参考 - 这是一种扩大的合并排序）

我的感觉是使用定理中的第一个方程，但我觉得我的想法有问题。如何解决这样的问题，任何的解释可以理解的:)

我能够使用递归树来解决这个问题。师父的定理不适合 –

你能详细说明你做了什么吗？ – Aviad

我应该发布整个解决方案否则它会在评论区域混乱。 –

答

对于给定的递归递归树看起来就像这样：

       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

的longes简单的路径，从根到叶会是正> 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))

运行时复杂性|使用硕士定理的递归计算

相关推荐