第一章 算法概述
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;
}