【有书共读】《算法导论》第4章 - 分治策略 读书笔记（下）
用代入法求解递归式
分为两步：
- 猜测解的形式
- 用数学归纳法求出解中的常数，并证明解是正确的
用递归树方法求解递归式
在递归树中，每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。
我们为递归式T(n) = 3T(⌊n/4⌋) + Θ(n2)创建一棵递归树：
整棵树的代价就是所有层次的代价之和。
用主方法求解递归式
主方法可以直接求解如下形式的递归式：T(n) = aT(n / b) + f(n)
主方法依赖于主定理：
投递阿里云等公司10个岗位