我正在使用递归树解决这个递归问题。每一层的总代价为n，树的深度在log (n) base 4和log (n) base 4/3之间。直觉上，我希望解决方案最多是级别数乘以每个级别的成本。 O(cn log (n) base 4/3) = O(n log n)。我想知道我处理问题的方法和解决方案是否正确？
最佳答案
这样想:对于递归树的前 log4 n 层，这些层的工作总和将为 cn，因为如果你将所有层的总大小加起来子问题，总计 n，因此总工作量为 cn。这意味着所做的功是 Ω(n log n)。
您可以通过假装在树的每一层完成的工作总和为 O(n) 来上限完成的工作(它实际上随着您在树中越来越低而下降，所以这是一个上限)，高度为 log4/3 n。这给出了 O(n log n) 的工作上限。
因为做的功是Ω(n log n)和O(n log n)，所以做功更恰当的是Θ(n log n)。
希望这对您有所帮助!
关于algorithm - 如何求解递归复杂度T(n) = T(n/4)+T(3n/4)+cn，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22033805/