如何解决递归复杂度 T(n) = T(n/4)+T(3n/4)+cn 的问题。

Question

我使用递归树来解决这个递归式。每个级别的总成本为n，树的深度在log (n) base 4和log (n) base 4/3之间。直觉上，我预计解决方案最多是每个级别的成本乘以级别数。O(cn log (n) base 4/3) = O(n log n)。想知道我的方法和解决方案是否正确？

- user3339453

Answer 1

这样想：在递归树的前log₄n层中，跨这些层的工作总和将为cn，因为如果你总结所有子问题的总大小，它应该总共为n，所以总工作量是cn。这意味着完成的工作是Ω(n log n)。

你可以将完成的工作上限设定为假装每个树层中完成的工作总和为O(n)（随着你越来越低地走进树中，实际上会下降，因此这是一个上限），而高度为log_4/3n。这给出了工作量的O(n log n)上限。

由于完成的工作是Ω(n log n)和O(n log n)，因此完成的工作更恰当地是Θ(n log n)。

希望这有所帮助！

- templatetypedef

Answer 2

编辑：之前缺少原文问题描述并回答了错误的解决方案，以下是我更正后的尝试

直觉上，你是正确的。

为了更正式一些，你可以通过数学方法来证明它。

这里有一个魔术技巧：Akra-Bazzi定理，它是主定理的更一般版本。

对于关系式T(n) = T(n/4) + T(3n/4) + cn

我们得到 g(n) = cn, k = 2, a1 = a2 = 1, b1 = 1/4, b2 = 3/4

根据定理，我们必须解出a1b1^p + a2b2^p = 1的p值，很明显p = 1

然后T(n) = O(n^p * (1+integration(1/n dn))) = O(n*(1+log(n))) = O(nlogn)

这与我们的猜测相符。

- shole