递归方程的递归树

Question

我有这个递归方程： T(n) = T(n/2) + T(n/5) + T(n/9) + Θ(n)

我这样画我的递归树：

          cn
     /     |     \
   n/2    n/5    n/9
  / | \  / | \  / | \
  ..................

这棵树有 log(n) + 1 层，每一层的节点数是上一层的 3 倍，子问题大小每次减少 2 倍。现在这就是我看到的总成本：

我忘了说：我的解决方案正确吗？

Answer 1

假设我们有更一般的关系：

其中 f(n) 是一些功能，例如cn.

如果我们将这个关系重新代入自身，即每次递归调用，产生的下一层递归调用的参数都会乘以相应的因子：

如果我们继续，模式由这个表达式给出：

...即 Trinomial expansion。每个T项的系数由三项式系数给出，参数由λμν的不同次幂给出：

从展开式可以看出，f 项是 T 项后面的 一级递归 。因此，所有 f 项的总和，考虑到它们必须累加与 T 项不同：

以上所有内容都可以通过归纳法证明，并且可以推广到任何次递归调用。

我们什么时候终止，即去掉 T 项？正如我在评论中所说，当递归到达最长路径的末端时。这是通过考虑最慢的递减项（正如您正确推断的那样）给出的：

Thus the time complexity function's tightest closed-form bound is given by:

这很容易判断 f(n) 是否是 n 的幂。

例如，f(n) = Θ(n), α = β = γ = 1, λ = 2, μ = 5, ν = 9。因此：

括号内的项正好前面的三项式展开。因此：

自 τ < 1 起，指数项消失了。因此T(n) = O(n).

数值测试证实了这一点：

n         T(n)
-----------------------------
10        21.86111111
100       328.1442901
1000      3967.333431
10000     44150.87621
100000    471262.9357
1000000   4910520.041
10000000  50415530.84

log-log T(n) 对 n:

的图

梯度为1.054 ± 0.01166，非常接近1的理论值，从而有力地支持了T(n) = O(n)的结果。

递归方程的递归树

Recursion tree for recursive equation

algorithm

recursion

asymptotic-complexity