不同规模子问题的主定理
Master theorem for subproblems of different sizes
Master theorem 的通用形式提到：
it is assumed that all subproblems are essentially the same size
Akra–Bazzi method 适用于：
the sub-problems have substantially different sizes
但是 显着 不同的标准是什么？例如，我有一个递归关系，如：
T(n) = T(n/4) + T(3n/4) + cn
(c is some constant)
我还能用主定理来求解这个关系吗（比如近似为T(n) = 2T(3n/4) + cn）？或者，换句话说，这些子问题的大小是 "essentially the same" 还是已经 "substantially different"？
假设 c 是某个常数，您有：T(n) = T(n/4) + T(3n/4) + O(n)
用 Akra-Bazzi 方法解决这个问题得到 O(n^2)
假设 T(n) = 2T(3n/4) + O(n) 求解得到 O(n^2.4094)（exp. 四舍五入为 4 dp）
所以只要试一试，你就可以确认它们已经有很大的不同了。
Master theorem 的通用形式提到：
it is assumed that all subproblems are essentially the same size
Akra–Bazzi method 适用于：
the sub-problems have substantially different sizes
但是 显着 不同的标准是什么？例如，我有一个递归关系，如：
T(n) = T(n/4) + T(3n/4) + cn
(c is some constant)
我还能用主定理来求解这个关系吗（比如近似为T(n) = 2T(3n/4) + cn）？或者，换句话说，这些子问题的大小是 "essentially the same" 还是已经 "substantially different"？
假设 c 是某个常数，您有：T(n) = T(n/4) + T(3n/4) + O(n)
用 Akra-Bazzi 方法解决这个问题得到 O(n^2)
假设 T(n) = 2T(3n/4) + O(n) 求解得到 O(n^2.4094)（exp. 四舍五入为 4 dp）
所以只要试一试，你就可以确认它们已经有很大的不同了。