algorithm - 解决不容易以 MT 形式表示的递归关系

Question

我有以下递归关系:

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

在这种情况下，我认为解决方案是通过以下方式找到的:

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

在这里，可以应用主定理:

 a = b = 2, f(n) = n
 n^(log2(2)) vs n --> n vs n

因此，解决方案是:

 Theta(n log n)

我将如何找到以下情况的解决方案:

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

那些看起来不太容易放入 MT 形式，所以我不太确定该怎么做。

Answer 1

这些是 Akra--Bazzi 可以处理的形式:https://en.m.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method