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