在没有迭代的情况下求解递归关系(Solving a Recurrence relation without iteration)

在没有迭代的情况下求解递归关系(Solving a Recurrence relation without iteration)

我该如何解决这个问题？

T（n）= T（n / 4）+ T（3n / 4）+ cn

Ans是\ theta（nLogn）

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

How do I Solve this ?

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

Ans is \theta(nLogn)

How this answer can be achieved using master theorem or any other effecient method?

最满意答案

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

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

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

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

The longes simple path from root to a leaf would be n-> 3n/4 -> (3/4) ^2 n .. till 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 )

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