如何求解递归复杂度T(n) = T(n/3)+T(2n/3)+cn

Question

当计算中值时，我们知道，如果将输入数组分解为五个子组并递归求解，我们就会得到O(n)复杂度，但如果将数组分解为3，则不会返回O(n)复杂度。

有人知道怎么证明吗？

Answer 1

会是nlg(n)。

尝试绘制它的递归树:每个级别的总成本等于n，该树的深度为lg(n)。

注:实际上它的深度介于log(n)基3和log(n)基3/2之间，但由于所有基的对数顺序相同，我们可以把它看作是lg(n)。

Answer 2

看起来标题中的递归是错误的，但是我认为用于解决递归的主定理会很方便。您可以看到，从一个分母转到另一个分母会使您进入一个不同的情况，从O(n)到更糟的情况。