递归的概念
直接或间接地调用自身的算法成为递归算法。
用函数自身给出定义的函数成为递归函数
递归实例
阶乘函数
Fibonacci数列
Ackerman函数
排列问题
整数划分问题
汉诺塔问题
分治法的基本思想
将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解决这些子问题，然后将各子问题合并得到原问题的解。
分治范例
二分搜索技术
基本思想：将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。如果x=a[n/2]，则找到x，算法终止；如果x<a[n/2]，则只在数组a的左半部继续搜索x；如果x>a[n/2]，则只在数组a的右半部继续搜索x。
二分搜索技术充分利用了元素间的次序关系，采用分治策略，可最坏用
O
(
l
o
g
n
)
O(logn)
O(logn)时间完成搜索任务。
大整数的乘法
基本思想：
将n位的X,Y各自都分成2段，每段长n/2位(假设n为2的幂次)，即
X
=
A
?
1
0
n
/
2
+
B
X=A*10^{n/2}+B
X=A?10n/2+B，
Y
=
C
?
1
0
n
/
2
+
D
Y=C*10^{n/2}+D
Y=C?10n/2+D，则
X
Y
=
A
C
?
1
0
n
+
1
0
n
/
2
?
(
(
A
?
B
)
?
(
D
?
C
)
+
A
C
+
B
D
)
+
B
D
XY=AC*10^n+10^{n/2}*((A-B)*(D-C)+AC+BD)+BD
XY=AC?10n+10n/2?((A?B)?(D?C)+AC+BD)+BD。即一次n位的整数乘法可以化简为三次n/2位的整数乘法与6次减法。通过减少乘法次数，提高算法效率。
Strassen矩阵乘法
基本思想：
使用分治法，将一个矩阵转换为子矩阵相乘的方式。矩阵乘法耗费时间要比矩阵加法耗费的时间多，想要改进矩阵乘法的计算时间复杂性，必须减少乘法运算。Strassen矩阵乘法用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。
棋盘覆盖
基本思想：
用分治策略，可以设计解棋盘覆盖问题的一个简捷的算法。当k>0时，将
2
k
?
2
k
2^k*2^k
2k?2k棋盘分割为4个
2
k
?
1
?
2
k
?
1
2^{k-1}*2^{k-1}
2k?1?2k?1子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为
1
?
1
1*1
1?1棋盘。
合并排序
基本思想：
递归版本：
将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成要求的排好序的集合。
非递归版本：
递归版本的合并算法的递归过程只是将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段。按此机制，可以先将数组中的相邻两元素两两配对，再用合并算法将它们排序，构成n/2组长度为2的排好序的子数组段，再将它们排序成长度为4的排好序的字数组段。如此下去，直至整个数组排好序。
快速排序
基本思想：
快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
三个步骤：
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
选择基准的方式：
（1）固定位置
取序列的第一个或最后一个元素作为基准
（2）随机化选择
随机取待排序列中任意一个元素作为基准
快速排序算法的性能取决于划分的对称性。而划分基准的随机选择，可以使期望划分变得较为对称。
效率分析：
最坏时间复杂度：
Θ
（
n
2
）
\Theta（n^2）
Θ（n2）
最好时间复杂度：
Θ
（
n
l
o
g
n
）
\Theta（nlogn）
Θ（nlogn）
平均时间复杂度：
Θ
（
n
l
o
g
n
）
\Theta（nlogn）
Θ（nlogn）
稳定性：不稳定
线性时间选择，第k小，Select算法
基本思想：
线性时间选择是基于快速排序的一种变形，本质上和快排具有类似的地方。它的目的是找出这个数组中第k小的值。
随机选择划分基准
使用一个随机数产生器Random,随机的产生指定范围之间的一个随机整数，即划分基准是随机的，这个时候线性时间算法的平均时间可以在O ( n ) 内找到。
取中位数进行划分
在线性时间内找到一个划分基准，使得这个基准的划分的两个数组的长度都至少是原来的
α
\alpha
α倍（0 <
α
\alpha
α < 1），那么最坏情况也是O（ n )的情况。
最接近点对问题
基本思想：
将所给的平面上n个点的集合S分为两个子集S1和S2(可以按照x坐标排序中分)，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。最近点对可能单纯在S1或S2中，也可能分别在S1和S2中。对于这个问题，
一维：第三种情况只可能是最靠近中线的那两个点。
二维：取两个子集递归求解最小值为d，第三种情况只会发生在 ( mid - d , mid + d ) 内，这个范围，mid左边p1，mid右边p2，p1中每个点最多在p2中存在6个点会更新答案，即按照y坐标排序后，p1每点最多只要检查p2中排好序的相继6个点。
循环赛日程表
基本思想：
对于变成为n的日程表，可分出四个边长为n/2的子日程表(左上，左下，右上，右下)，易得左上=右下，左下=右上，且左下的值等于左上的对应位置的值加上n/2。即若已知左上n/2的子日程表，可推得整个n的日程表。类推得，n/4可得n/2…即由1可得n的日程表。整个过程基于分治实现。
主定理-基于分治的算法分析
简化版：
对于递推式
T
(
n
)
=
a
T
(
n
b
)
+
Θ
(
n
d
)
T(n)=aT(\frac{n}{b})+\Theta(n^d)
T(n)=aT(bn?)+Θ(nd)，其中 d >= 0 ，那么：
T ( n ) = { Θ ( n d ) ， 当 a < b d Θ ( n d l o g n ) ， 当 a = b d Θ ( n l o g b a ) ， 当 a > b d T(n)=\begin{cases} \Theta(n^d)， & 当a<b^d \\ \Theta(n^dlogn)， & 当a=b^d \\ \Theta(n^{log_{b}a})，&当a>b^d \end{cases} T(n)=??????Θ(nd)，Θ(ndlogn)，Θ(nlogb?a)，?当a<bd当a=bd当a>bd?
正式版：
深入学习