求解递归 T(n) = 3T(n / 2) + n

Question

正在备考，不知道如何获取这个关系生成的递归树的高度：

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

我知道树看起来像这样，我必须添加所有项：

           c*n
          / | \
         /  |  \   
    c*n/2 c*n/2 c*n/2 
      .     .     .
      .     .     .

谢谢！！

Answer 1

当你有一个形式的递推关系时

T(n) = aT(n / b) + f(n)

那么递归树的高度只取决于b的选择（当然假设a > 0）。这样做的原因是树中的每个节点都代表展开上述递归时发生的情况，而上述递归中唯一可以展开某些内容的地方是 T(n / b) 项。如果增加或减少a，就会增加或减少树的分支因子（例如，2T(n/b)表示扩展一个节点时会产生两个节点，3T(n/b)表示即展开节点时会生成三个节点），但树的分支因子与层数无关。它只是告诉你会有多少个级别。同样，改变 f(n) 只会增加或减少每个节点完成的总工作量，这不会影响递归树的形状。

那么 b 具体如何影响树的高度？好吧，在这个递推关系中，每次我们扩展 T 时，我们最终都会将输入的大小除以系数 b。这意味着在树的顶层，我们将遇到大小为 n 的问题。下面是大小为 n / b 的问题。下面是大小为 (n / b) / b = n / b² 的问题。通常，在树的第 k 层，问题大小为 n / b^k。当问题大小下降到 0 或 1 时递归停止，这发生在 k = log_b n 时。换句话说，递归树的高度将是 O(log_b n).

现在，只知道树高并不能告诉您完成的总工作量，因为我们还需要知道分支因子和每个级别完成的工作。它们可以通过许多不同的方式相互交互，但幸运的是，有一个名为 master theorem 的美丽定理，让您只需查看 a、b 和 f(n) 就可以非常优雅地读出解决方案.在你的情况下，重复是

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

将其代入主定理，我们看到递归的解是 T(n) = O(n^{log₂ 3}).这大约是 O(n^1.58).

求解递归 T(n) = 3T(n / 2) + n

Solving the recurrence T(n) = 3T(n / 2) + n

tree

recursion

recurrence