如何解决递归复杂度T(n)= T(n/4)+ T(3n/4)+ cn [英] How to solve the recursive complexity T(n) = T(n/4)+T(3n/4)+cn

问题描述

我正在使用递归树解决这种重复.每个级别的总成本为n，树的深度在log (n) base 4和log (n) base 4/3之间.凭直觉，我希望解决方案最多是级别数乘以每个级别的成本. O(cn log (n) base 4/3) = O(n log n).我想知道我解决问题的方法和解决方案是否正确?

I am solving this recurrence using a recursion tree. The total cost of each level is n, and the depth of the tree is between log (n) base 4 and log (n) base 4/3. Intuitively, I expect the solution to be at most the number of levels times the cost at each level. O(cn log (n) base 4/3) = O(n log n). I was wondering if my approach towards the problem, and my solution is correct?

推荐答案

以这种方式思考:对于递归树的第一个log ₄ n层，跨这些层的工作之和将为cn，因为如果您将所有子问题的总和求和，则总和应为n，因此总工作量为cn.这意味着完成的工作是Ω(n log n).

Think of it this way: for the first log₄ n layers of the recursion tree, the sum of the work across those layers will be cn, because if you sum up the total sizes of all the subproblems, it should total n so the total work is cn. This means that the work done is Ω(n log n).

您可以通过假装在树的每一层中完成的工作的总和为O(n)来限制所做的工作(随着您在树中越来越低，它实际上会下降，因此这是一个上限)，高度为log _4/3 n.这为O(n log n)的工作提供了一个上限.

You can upper-bound the work done by pretending that the sum of the work done in each layer of the tree is O(n) (it actually drops off as you go lower and lower in the tree, so this is an upper bound) and the height is log_4/3 n. This gives an upper bound on the work of O(n log n).

由于完成的工作为Ω(n log n)和O(n log n)，所以完成的工作更正确为&θ;(n log n).

Since the work done is Ω(n log n) and O(n log n), the work done is more properly Θ(n log n).

希望这会有所帮助！

这篇关于如何解决递归复杂度T(n)= T(n/4)+ T(3n/4)+ cn的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！