recurrence - 用递归树猜测渐近上界。用代入法和主定理验证

Question

我的任务如下：通过使用递归树找到递归的渐近上限的猜测。通过以下方式验证渐近上界：

1: Substitution method
2: Master Theorem

T(n)= { Θ(1)               if n = 1
      { 3T(n/3) + Θ(n)     if n > 1

我该如何处理？我对递归树、替换方法和主定理有一些了解。请帮忙！

score 1 · Accepted Answer

我们有 Master 定理的案例 2，因为

a = 3
b = 3
f(n) = n = Θ(n^log_3(3)) = Θ(n)

所以

T(n) = Θ(n*lg(n))

当然

lg(n) = log_2(n).

直观地说，这意味着 T 的成本既不受递归成本的支配，也不受递归中所做工作的支配。这就像说在递归树中，每一层节点的成本与叶子的成本渐近相同。

1 回答 1