第1页:计算机算法设计与分析封面
计算机算法设计与分析
第2页:课程基本内容
基本内容
- 导引(第一、二章)
- 基本的算法设计策略
- 分治法(第四章)
- 贪心方法(第五章)
- 动态规划(第六章)
- 回溯法(第八章)
- 分支-限界法(第九章)
- 基本算法分析方法
- NP-难度和NP-完全问题(第十章)
第3页:课程学习目标
学习目标
- 掌握基本的算法设计方法
- 掌握分析算法的基本方法(时间、空间复杂度分析)
- 灵活运用基本的算法设计方法,用于解决实际问题
第4页:第二章导引目录
第二章导引
- 2.1算法
- 2.2分析算法及数学基础
- 2.3用SPARKS语言写算法
- 2.4基本数据结构
第5页:算法的概念(一)
2.1算法一、算法的概念(I)数值计算求解数值问题,插值计算、数值积分等非数值计算求解非数值问题,主要进行判断比较算法
第6页:算法的概念(二)
- 算法的概念(II)Knuth:算法就是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。
- 算法早于计算机出现
第7页:算法的五个重要特性
- 二、算法的五个重要特性算法(Algorithm)
- 确定性每一种运算必须要有确切的定义,无二义性
- 能行性运算都是基本运算,原则上能在有限时间内完成
- 输入有0个或多个输入
- 输出一个或多个输出
- 有穷性在执行了有穷步运算后终止
- Notes:仅仅有穷还不够,还要在现代计算机上有效才行
第8页:程序与算法的区别
程序(Program)(计算过程)
- 程序是算法用某种程序设计语言的具体实现。
- 程序可以不满足算法的性质(5)有穷性。
- 例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。
- 操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
- 程序=算法+数据结构(By Wirth)
第9页:计算机求解问题的步骤
用计算机求解问题的步骤
- 设计、确认、分析、编码、检查、调试、计时证明正确性分析算法理解问题精确解或近似解算法设计策略选择数据结构设计算法设计程序
第10页:算法学习的五个内容
三、算法学习的五个内容
- 如何设计算法运用一些基本设计策略规划算法
- 如何表示算法用恰当的方式表示算法
- 如何确认算法算法正确性的证明(算法确认algorithm validation)
- 如何分析算法通过时间和空间复杂度的分析,确定算法的优劣
- 如何测试程序测试程序是否会产生错误的结果设计高效算法SPARKS语言穷举、数学归纳法、反证法、构造性证明、测试目的是比较和改进算法调试和时空分布图
第11页:算法分析的目的与前提
一、如何分析算法
- 分析算法的目的设计更高效的算法
- 算法分析的前提要求独立于具体的软硬件环境单纯分析算法一台通用计算机(理想情况下)顺序处理、每次一条指令、存储容量足够大、存取时间恒定
- 算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。2.2分析算法
第12页:算法分析的准备工作
2.2分析算法一、如何分析算法
- 算法分析的准备
- 首先确定使用哪些运算以及执行这些运算所用的时间。(运算包括基本运算和由一些更基本的任意长序列的运算所组成的复杂运算)
- 其次是要确定出能反映算法在各种情况下工作的数据集。(即要求我们编造出能产生最好、最坏和有代表性情况的数据配置,通过使用这些数据来运行算法,以更了解算法的性能)
第13页:事前分析与事后测试
二、全面分析算法的两个阶段
- 事前分析(a prior analysis)
- 求出该算法的一个时间限界函数(一些关于参数的函数)
- 事前分析只限于每条语句的频率计数(frequency count).语句的执行次数,与所用的机器无关,且独立于程序设计语言,可由算法直接确定
- 事后测试(a posterior testing)
- 收集此算法的实际执行时间和占用空间的统计资料2.2分析算法
第14页:语句频率计数示例
- 例:计算语句x←x+y在下面三个程序段中的频率计数beginx←x+yendFC:1beginfor i←1 to n dox←x+yendFC:nbeginfor i←1 to n dofor j←1 to n dox←x+yendFC:n2
- 语句的数量级是指执行它的频率计数之和
- 算法的数量级是指算法的所有语句的频率计数之和确定一个算法的数量级十分重要,因为它在本质上反映了算法所需的计算时间。准确分析出一个算法的计算时间有时是很困难的,因此我们对算法的计算时间进行渐进表示。2.2分析算法
第15页:算法复杂性形式化表述
算法复杂性分析形式化表述算法复杂性即算法所需要的计算机资源算法的时间复杂性T(n);
算法的空间复杂性S(n)。
其中n是问题的规模(输入大小)。
第16页:时间复杂性的三种情形
算法的时间复杂性(1)最坏情况下的时间复杂性Tmax(n) = max{T(I) | size(I)=n}(2)最好情况下的时间复杂性Tmin(n) = min{T(I) | size(I)=n}(3)平均情况下的时间复杂性Tavg(n) =其中I是问题规模为n的实例,p(I)是实例I出现的概率。
第17页:计算时间的渐近表示
2.2分析算法
- n:问题的规模
- f(n):算法的计算时间
- g(n):形式简单的函数
- (f(n)-g(n) )/f(n)→0,asn→∞;
- 在数学上,g(n)是f(n)的渐近表达式,是f(n)略去低阶项留下的主项。它比f(n)简单。三、计算时间的渐近表示
第18页:定义1.1 大O记号
定义1.1
- 如果存在两个正常数c和n0,对于所有的n≥n0,有|f(n)|≤c|g(n)|,则记做f(n)=O(g(n)) .•f(n)表示算法的计算时间,n是输入或输出量,g(n)是在事前分析中确定的某个形式的简单函数,f(n)与机器和语言有关,而g(n)是独立于机器和语言的。•一个算法具有O(g(n))的计算时间是指如果这个算法用n值不变的同一类数据在某台机器上运行时,所用的时间总是小于|g(n)|的一个常数倍。•g(n)是计算时间f(n)的一个上界函数,f(n)的数量级就是g(n)。
第19页:大O记号举例
例子f(n)=O(g(n))
- f(n)=3n,g(n)=4n
- f(n)=n+1024,g(n)=1025n
- f(n)=2n2+11n-10,g(n)=3n2
- f(n)=n2,g(n)=n3
- 反例:f(n)=n3,g(n)=n2
第20页:定理1.1 多项式阶
定理1.1
- 若A(n)=amnm+……+a1n+a0是一个m次多项式,则A(n)=O(nm)
第21页:定理1.1的推论
- 定理1.1表明,变量n的最高阶数为m的任一多项式,与nm同阶。因此一个计算时间为m阶多项式的算法,其时间都可以用O(nm)来表示。
- 若一个算法有数量级为c1nm1,c2nm2,… cknmk的k个语句,则算法的数量级及计算时间就是c1nm1+c2nm2+…+cknmk=O(nm)其中m=max{mi|1≤i≤k}
第22页:多项式时间与指数时间算法
从计算时间上对算法分类
- 多项式时间算法(polynomial time algorithm):用多项式来对其计算时间限界的算法O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
- 指数时间算法(exponential time algorithm):计算时间用指数函数限界的算法O(2n)<O(n!)<O(nn)
第23页:时间复杂性函数对比图
不同时间复杂性函数的对比
第24页:小规模数据下的对比
小规模数据
第25页:中等规模数据下的对比
中等规模数据
第26页:Ω与Θ记号定义
- 定义1.2如果存在两个正常数c和n0,对于所有的n ≥n0,有|f(n) |≥c|g(n)|,则记做f(n)=Ω(g(n)) .这种情况称g(n)是计算时间f(n)的一个下界函数。在某些情况下,可能会出现g(n)既是f(n)的上界,又是它的下界,为此引入数学符号Θ来表示。
- 定义1.3如果存在两个正常数c1,c2和n0,对于所有的n≥n0,有c1 |g(n)|≤|f(n)|≤c2 |g(n)|,则记作:f(n)=Θ(g(n)).
第27页:渐近分析中的函数比较
渐近分析中函数比较a=f(n);
b= c×g(n)f(n)=O(g(n))≈a≤b;
f(n)=Ω(g(n))≈a≥b;
f(n)=Θ(g(n))≈a= b;
第28页:渐近记号的传递性
渐近表示函数的若干性质(1)传递性
- f(n)=Θ(g(n)),g(n)=Θ(h(n))⇒f(n)=Θ(h(n));
- f(n)=O(g(n)),g(n)=O(h(n))⇒f(n)=O(h(n));
- f(n)=Ω(g(n)),g(n)=Ω(h(n))⇒f(n)=Ω(h(n));
第29页:反身性对称性与互对称性
(2)反身性f(n)=Θ(f(n));
f(n)=O(f(n));
f(n)=Ω(f(n)).(3)对称性f(n)=Θ(g(n))⇔g(n)=Θ(f(n)).(4)互对称性f(n)=O(g(n))⇔g(n)=Ω(f(n));
第30页:渐近记号的算术运算
(5)算术运算O(f(n))+O(g(n))=O(max{f(n),g(n)});
O(f(n))+O(g(n))=O(f(n)+g(n));
O(f(n))*O(g(n))=O(f(n)*g(n));
O(cf(n))=O(f(n));
f(n)=O(g(n))⇒O(f(n))+O(g(n))=O(g(n))。
ΘΩ也有类似性质,证明方法类似。
第31页:O加法取大者的证明
规则O(f(n))+O(g(n))=O(max{f(n),g(n)})的证明:对于任意f1(n) =O(f(n)),存在正常数c1和自然数n1,使得对所有n≥n1,有f1(n)≤c1f(n)。
类似地,对于任意g1(n) =O(g(n)),存在正常数c2和自然数n2,使得对所有n≥n2,有g1(n)≤c2g(n)。
令c3=max{c1,c2},n3=max{n1,n2},h(n)= max{f(n),g(n)}。
则对所有的n≥n3,有f1(n) +g1(n)≤c1f(n) +c2g(n)≤c3f(n) +c3g(n)=c3(f(n) +g(n))≤2c3max{f(n),g(n)}= 2c3h(n) =O(max{f(n),g(n)}) .
第32页:O加法合并的证明
规则O(f(n))+O(g(n))=O(f(n)+g(n))的证明:对于任意f1(n) =O(f(n)),存在正常数c1和自然数n1,使得对所有n≥n1,有f1(n)≤c1f(n)。
类似地,对于任意g1(n) =O(g(n)),存在正常数c2和自然数n2,使得对所有n≥n2,有g1(n)≤c2g(n)。
令c3=max{c1,c2},n3=max{n1,n2},h(n)=f(n)+g(n)。
则对所有的n≥n3,有O(f(n))+O(g(n))=f1(n) +g1(n)≤c1f(n) +c2g(n)≤c3f(n) +c3g(n)=c3(f(n) +g(n))=c3h(n) =O(f(n)+g(n)) .
第33页:O乘法规则的证明
规则O(f(n))*O(g(n))=O(f(n)*g(n))的证明:对于任意f1(n) =O(f(n)),存在正常数c1>1和自然数n1,使得对所有n≥n1,有f1(n)≤c1f(n)。
类似地,对于任意g1(n) =O(g(n)),存在正常数c2>1和自然数n2,使得对所有n≥n2,有g1(n)≤c2g(n)。
令c3=c1*c2,n3=max{n1,n2},h(n)=f(n)*g(n)。
则对所有的n≥n3,有O(f(n))*O(g(n))=f1(n) *g1(n)≤c1f(n) *c2g(n)=c3f(n)*g(n)=c3h(n)=O(f(n)*g(n)) .
第34页:求和公式通式
数学基础(1)求和公式通式
第35页:单调函数与取整函数
算法渐近复杂性分析中常用函数(2)单调函数单调递增:m≤n⇒f(m)≤f(n);
单调递减:m≤n⇒f(m)≥f(n);
严格单调递增:m<n⇒f(m)<f(n);
严格单调递减:m<n⇒f(m) >f(n).(3)取整函数⌊x⌋:不大于x的最大整数;
⌊2.5⌋=2⌊2⌋=2⌈x⌉:不小于x的最小整数。
⌈2.5⌉=3⌈2⌉=2
第36页:取整函数的性质
取整函数的若干性质x-1 <⌊x⌋≤x≤⌈x⌉<x+1;
⌊n/2⌋+⌈n/2⌉=n;
对于n≥0,a, b>0,有:⌈⌈n/a⌉/b⌉=⌈n/ab⌉;
⌊⌊n/a⌋/b⌋=⌊n/ab⌋;
⌈a/b⌉≤(a+(b-1))/b;
⌊a/b⌋≥(a-(b-1))/b;
f(x)=⌊x⌋,g(x)=⌈x⌉为单调递增函数。
第37页:多项式函数
(4)多项式函数p(n)=a0+a1n+a2n2+…+adnd;
ad>0;
p(n) =Θ(nd);
p(n) =O(nk)⇔p(n)多项式有界;
p(n) =O(1)⇔p(n)≤c;
第38页:指数函数及其性质
(5)指数函数一些性质对于正整数m,n和实数a>0:a0=1;
a1=a;
a-1=1/a;
(am)n=amn;
(am)n=(an)m;
aman=am+n;
a>1⇒an为单调递增函数;
a>1⇒⇒nb=o(an)
第39页:ex的不等式与渐近展开
ex≥1+x;
|x|≤1⇒1+x≤ex≤1+x+x2;
ex= 1+x+Θ(x2), asx→0;
第40页:对数函数
(5)对数函数logn= log2n;
lgn= log10n;
lnn= logen;
logkn= (logn)k;
log logn= log(logn);
fora>0,b>0,c>0
第41页:
第42页:对数与多项式的不等式
|x|≤1⇒forx>-1,for anya> 0,,⇒logbn= o(na)
第43页:阶乘函数与Stirling公式
(6)阶乘函数Stirling’s approximation
第44页:
第45页:时空分布图
时空分布图
- 要求时钟及其精确度操作系统的工作方式
- 处理噪声增加输入规模增加执行次数
- 时空分布图的做法
- 用途比较同一问题的不同算法对算法改进前后进行比较
第46页:SPARKS语言基本语法
2.3用SPARKS语言写算法
- SPARKS语言的基本数据类型:整型(integer),实型(real),布尔型(boolean),字符型(char)
- SPARKS语言的变量命名规则:以字母开头,不允许使用特殊字符,不允许与保留字重复
- 赋值语句:变量←表达式
- 逻辑运算符:and , or , not
- 关系运算符:<,≤,=,≠,>,≥布尔值: true,false
- 数组:任意整数下界和上界的多维数组integer A(l1:u1, …, ln:un);例: integer x, y; char ch;例: integer A(1:10); real B(3:6 , 1:4);
第47页:SPARKS条件与case语句
SPARKS语言的条件语句 if条件 then s1 endif if条件 then s1 else s2 endif case:条件1: s1…:条件n: sn: else: sn+1 end case SPARKS语言的 case语句2.3用SPARKS语言写算法
第48页:SPARKS循环语句
- SPARKS语言的循环语句while条件doSrepeatloopSuntil条件repeatfor变量←初值to终值by变量增值doSrepeat2.3用SPARKS语言写算法
第49页:SPARKS转移与控制语句
- exit转到含有exit的最内层循环语句后面的第一条语句
- goto标号
- cycle结束本次循环
- return
- stop2.3用SPARKS语言写算法
第50页:SPARKS过程与输入输出
SPARKS语言的函数(过程) procedure NAME(<参数列表>)<说明部分>S return(<表达式>) end NAME函数名,通常用大写字母说明参数的数据类型和函数中使用的变量 parameters形式参数 global全局变量 local局部变量函数的语句部分 SPARKS语言的输入、输出: read(参数表); print(参数表);2.3用SPARKS语言写算法
第51页:求最大元MAX过程示例
procedure MAX(A, n, j) parameters real A(1:n); parameters integer n, j; real xmax; local integer i;xmax←A(1); for i←2 to n do if A(i)>xmax thenxmax←A(i); j←i; endif repeat return(xmax); end MAX同质异相2.3用SPARKS语言写算法 global xmax integer i, j, n
第52页:基本数据结构
栈和队列
- 树
- 集合的树表示和不相交集合的合并
- 图2.4基本数据结构
第53页:本章小结
小结
- 算法的五个重要特性确定性、可行性、输入、输出、有穷性
- 算法分析的基本概念和思想
- 算法时间复杂度的渐进表示了解意义、会使用、能推导证明性质