algorithm - 如何求解递归复杂度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)。我想知道我处理问题的方法和解决方案是否正确？

Answer 1

这样想:对于递归树的前 log₄ n 层，这些层的工作总和将为 cn，因为如果你将所有层的总大小加起来子问题，总计 n，因此总工作量为 cn。这意味着所做的功是 Ω(n log n)。

您可以通过假装在树的每一层完成的工作总和为 O(n) 来上限完成的工作(它实际上随着您在树中越来越低而下降，所以这是一个上限)，高度为 log_4/3 n。这给出了 O(n log n) 的工作上限。

因为做的功是Ω(n log n)和O(n log n)，所以做功更恰当的是Θ(n log n)。

希望这对您有所帮助!