[数据结构与算法]算法设计与分析：第二章总结

主定理求解递归式的复杂度

网上的正式说法看不懂， 按照自己理解整理的，如有错误欢迎指正。

设递推式为 $T(n)=aT(\frac{n}{b})+\Theta (n^k),k\ge 0$ ，其中 $n$ 为问题规模，$a$ 为递推子问题的数量，$\frac{n}{b}$ 为每个子问题的规模（假设每个子问题的规模基本一样），则：

1. 如果 ${\log }_{b}a<k$，$T(n)=\Theta (n^{{\log }_{b}a})$
2. 如果 ${\log }_{b}a=k$，$T(n)=\Theta (n^{{\log }_{b}a}\log n)$
3. 如果 ${\log }_{b}a>k$，$T(n)=\Theta (n^k)$

分治范例

1.二分搜索技术

2.大整数乘法

3.Strassen矩阵乘法

4.棋盘覆盖

5.合并排序

6.快速排序

7.选择问题求第k小

8.最近点对问题

9.循环赛日程表