我使用递归树来解决这个递归式。每个级别的总成本为n,树的深度在log (n) base 4和log (n) base 4/3之间。直觉上,我预计解决方案最多是每个级别的成本乘以级别数。O(cn log (n) base 4/3) = O(n log n)。想知道我的方法和解决方案是否正确?
编辑:之前缺少原文问题描述并回答了错误的解决方案,以下是我更正后的尝试
直觉上,你是正确的。
为了更正式一些,你可以通过数学方法来证明它。
这里有一个魔术技巧: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)
这与我们的猜测相符。