algorithm - 解决递归关系的 Akra–Bazzi 方法？

Question

T(n) = T(n/2) + T(n/4) + n

我不确定这个递归关系是否可以通过 Master 定理求解，但我发现更简单的方法是使用 Akra–Bazzi 方法。这里，我们有 a1 = 1，b1 = 1/2，a2 = 1，b2 = 1/4，所以求解 p 我们有 (1/2)^p + (1/4)^p = 1。所以，p = 1, 然后使用公式，渐近行为可以确定为 T(n) = θ(n + nlogn) = θ(nlogn)?

Answer 1

这不是真的。在当前状态下，p = log(1 + sqrt(5))/log(2) - 1。因此，它将是 T(n) = Theta(n)(请参阅详细信息 here)。