第一章 算法概述
1.1算法性质：
输入、输出、确定性、有限性
1.2时间复杂度
上界记号O：如果存在正的常数C和自然数N0，使得当N≧N0时有f(N)≦Cg(N)，则f(N)有上界函数g(N)，记为f(N)= O(g(N))。
同阶记号θ：f(N)=θ(g(N))表示f(N)和g(N)同阶 。
下界记号Ω：如果存在正的常数C和自然数N0，使得当N≧N0 时有f(N)≧Cg(N)，则f(N)有下界函数g(N)，记为f(N) = Ω(g(N))。
1.3NP完全性理论
P类问题：是指一类能够用确定性算法在多项式时间内求解的判定问题。其实，在非正式的定义中，我们可以把那些在多项式时间内求解的问题当作P类问题。
NP类问题：是指一类可以用不确定性多项式算法求解的判定问题。（不确定性算法：非确定(“猜想”)阶段+确定(“验证”)阶段）
第二章 递归与分治策略
2.1 递归
递归算法是一个直接或间接地调用自己的算法。
例1：阶乘函数
int fac(int n)
{ if (n==0) return 1;
return n*fac(n-1);
}
例2：Hanoi塔问题。
汉诺塔问题可以通过以下三个步骤实现：
（1）将塔A上的n-1个碟子借助塔C先移到塔B上。
（2）把塔A上剩下的一个碟子移到塔C上。
（3）将n-1个碟子从塔B借助塔A移到塔C上。
void move(char x,char y)
{
printf("%c->%c\n",x,y);
}
void hanoi(int n, char a, char b, char c){
if (n == 1) move(a,c);
else
{
hanoi(n-1, a, c, b);
move(a,c);
hanoi(n-1, b, a, c);
}
例3：多变元递归——整数划分问题
例：整数划分问题：将一个正整数n表示为一系列正整数之和，n = n1 + n2 +…+nk 其中n1≥n2≥…≥nk≥1, k≥1。
例如 p(6) = 11 ，即整数6的划分数为11种：
6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1
最简单情形：(1) q(n, 1)=1，q(1, m) =1 n, m≥1;
递归关系： (2) q(n, n) = 1 + q(n, n–1)，n＞1;
产生的新情况： (3) q(n, m) = q(n, m–1) + q(n–m, m), n＞m＞1
划分中不含m的情况 划分中含m的情况 (4) q(n, m) = q(n, n), n＜m。
例4：多步递归——Fibonacci数列
2.2分治法
解型为T(n)=aT(n/b)+O(nd)的递归方程
设a>=1和b>1是常数，f(n)是一个函数，
T(n)是定义在非负整数集上的函数：T(n)=aT(n/b)+ O(nd) 。
例1：二分搜索技术
int BinarySearch(Type a[ ], const Type &x, int n)
{
int left=0;int right=n-1;
while (left <= right ){
int middle = (left+right)/2;
if (x == a[middle]) return middle;
if (x < a[middle]) right = middle-1;
else left = middle+1;
}
return -1;
}
例2：大整数的乘法
例3:Strassen矩阵乘法
例4：棋盘覆盖
棋盘覆盖算法(参数表)
{
如果是单个格子，则返回；
将棋盘划分成尺寸为一半的子棋盘；
判断特殊方格在哪个子棋盘中，再用相应的骨牌覆盖相应结合部，并记下它们的位置；
依次对左上角、右上角、左下角和右下角这四个子棋盘进行棋盘覆盖；
}
public void chessBoard(int tr, int tc, int dr, int dc, int size) //tr和tc为左上角方格的行、列号；dr和dc为特殊方格的行、列号；size=2^k
{ // 先画棋盘图，再说明
if (size == 1) return;
int t = tile++, // L型骨牌号
s = size/2; // 分割棋盘
// 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s)
// 特殊方格在此棋盘中
chessBoard(tr, tc, dr, dc, s);
else {// 此棋盘中无特殊方格
// 用 t 号L型骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
// 覆盖其余方格
chessBoard(tr, tc, tr+s-1, tc+s-1, s);}
// 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
chessBoard(tr, tc+s, dr, dc, s);
else {// 此棋盘中无特殊方格
// 用 t 号L型骨牌覆盖左下角
board[tr + s - 1][tc + s] = t;
// 覆盖其余方格
chessBoard(tr, tc+s, tr+s-1, tc+s, s);}
// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s)
// 特殊方格在此棋盘中
chessBoard(tr+s, tc, dr, dc, s);
else {// 用 t 号L型骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
// 覆盖其余方格
chessBoard(tr+s, tc, tr+s, tc+s-1, s);}
// 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
chessBoard(tr+s, tc+s, dr, dc, s);
else {// 用 t 号L型骨牌覆盖左上角
board[tr + s][tc + s] = t;
// 覆盖其余方格
chessBoard(tr+s, tc+s, tr+s, tc+s, s);}
}
例5：合并排序
template<class Type>
void MergeSort(Type a[ ], int left, int right)
{// a[left:right]是一个数组，
//含有 right-left+1个待排序的元素。
if (left<right)
{ //至少有2个元素
int mid = (left+right)/2; //求当前数组的分割点
MergeSort(a, left,mid);
MergeSort(a, mid+1, right);
Merge(a, b, left, mid , right);
copy(a, b, left, right);
}
}
例6：快速排序
基本思想：对于输入的子数组a[p:r],按以下三部进行排序：
① 分解 ：以a[p]为基准元素将 alp 划分成3段a[p:q-1］，a[q]和a[q+1:r]，使a[p:q-1］中任何一个元素小于等于a[q]，而 a[q+1:r］中任何一个元素大于等于a[q]。下标q在划分过程中确定。
② 递归求解：通过递归调用快速排序算法，分别对a[p:q-1］和a[q+1:r]进行排序。
③ 合并：由于对 a[p:q-1］和a[q+1:r］的排序是就地进行的，因此在a[p:q-1］和 alg+1:r］都已排好的序后，不需要执行任何计算，a[p:r]则已排好序。
基于这个思想，可实现快速排序算法如下
template<class Type>
void QuickSort(Type a[ ], int p,int r)
{
if(p<r)
{
int q=Partition(a,p,r);
QuickSort(a,p,q-1);//对左半段排序
QuickSort(a,q+1,r);//对右半段排序
}
}
时间复杂度分析：
