algorithm - 不同大小子问题的主定理

Question

Master theorem的通用形式提到：

假设所有子问题的大小基本相同

Akra-Bazzi 方法适用于以下情况：

子问题的大小有很大不同

但是，实质性不同的标准是什么？例如，我有一个递归关系，如：

T(n) = T(n/4) + T(3n/4) + cn 
(c is some constant)

我仍然可以使用主定理来解决这种关系（例如将其近似为T(n) = 2T(3n/4) + cn）吗？或者，换句话说，这些子问题的大小是“本质上相同”还是已经“本质上不同”？

Answer 1

假设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）

因此，只需尝试一下，您就可以确认它们已经有很大的不同。