1 分治策略
《算法设计与分析》是计算机专业的重要核心课。这门课使用的教材是第三版算法导论黑皮书，由于课程并没有涉及到书中全部的章节，笔记只是对其中少数几个部分的理解。
但是这套答案对于很多题目都没有给出完整回答，仅作参考。
主方法用来求解递归式，获得一些
关于主定理
主定理 令 $a\geq 1$ 和 $b > 1$ 是常数，$f(n)$ 是一个函数，$T(n)$ 是定义在非负整数上的递归式 $$T(n)=aT(n/b)+f(n)\tag{1.1}$$
其中我们将 $n/b$ 解释为 $\lfloor n/b\rfloor$ 或 $\lceil n/b\rceil$。那么：
- 若对于某个常数 $\varepsilon > 0$ 有 $f(n)=O(n^{\log _b a-\varepsilon})$，则 $ T(n)=\Theta(n^{\log _b a})$。
- 若 $f(n)=\Theta(n^{\log _ ba})$，则 $T(n)=(n^{\log _ ba}\lg n)$。
- 若对于某个常数 $\varepsilon > 0$ 有 $f(n)=\Omega(n^{\log _b a+\varepsilon})$，且对于某个常数 $c < 1$ 和足够大的 $n$ 有 $af(n/b)\leq cf(n)$，则 $T(n)=\Theta(f(n))$。