计算机算法设计与分析第1章算法概述课件

课程安排理论课：1～10周，40学时周二(5-6)、周五(1-2)上机：18学时期末考试：闭卷笔试，第11周上课点名三次不到者取消考试资格；迟到或作业缺交，一次扣10分（平时成绩）。1课程安排理论课：1～10周，40学时1教学目的和要求本课程是计算机类专业的专业基础课程；通过课程学习和上机实践，对计算机常用算法有一个较全面的了解，掌握通用算法的一般设计方法；学会对算法的时间、空间复杂度分析，掌握提高算法效率的方法和途径。2教学目的和要求本课程是计算机类专业的专业基础课程；2学习算法的重要性（一）从理论和实践的角度理解

—计算机科学的基石；掌握标准算法（二）从算法对于程序的重要性来讲

—皮之不存，毛将附焉？（三）从对同学们的能力培养看

—开发分析问题的能力3学习算法的重要性（一）从理论和实践的角度理解3算法分析与设计课程

与数据结构课程（一）数据结构关心的对象各种数据结构的作用和效率、具体的问题（二）算法设计与分析关心的对象算法设计技术的适用性和效率、一般性方法4算法分析与设计课程

与数据结构课程（一）数据结构关心的对象授课内容第1章算法概述第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法*7-9章属研究生学习内容，可自学了解。5授课内容第1章算法概述5第1章算法概述学习要点:

一、理解算法的概念，以及问题求解的过程。二、掌握算法的几种描述方式。三、理解算法的计算复杂性概念。四、掌握算法渐近复杂性的数学表述。6第1章算法概述学习要点:6什么是算法？我们来编写一个烧开水的算法：输入自来水循环（反复）加热直到水开输出开水7什么是算法？我们来编写一个烧开水的算法：7一、算法(Algorithm)

算法概念：通俗地讲，算法是指解决问题的一种方法或一个过程。严格地讲，算法是由若干条指令组成的有穷序列。图1.1算法的概念图8一、算法(Algorithm)算法概念：通俗地（一）算法的性质1、算法具有某些特性，如下几条：(1)输入：有零个或多个外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。这些输出是和输入有某种特定关系的量。9（一）算法的性质1、算法具有某些特性，如下几条：9（一）算法的性质(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性（有穷性）：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。10（一）算法的性质(3)确定性：组成算法的每条指令是清晰，无歧（一）算法的性质(5)可实现性：此性质是指算法中有待实现的运算都是相当基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。（补充）11（一）算法的性质(5)可实现性：此性质是指算法中有待实现的运（一）算法性质2、关于算法有几个要点：(1)算法所处理的输入的值域必须严格定义。(2)同样一种算法可以用几种不同的形式来描述。12（一）算法性质2、关于算法有几个要点：12（一）算法性质(3)同一个问题可以存在多种解决的算法。(4)同一个问题的几种算法可能会基于完全不同的解题思路，而且解题速度也会有显著不同。13（一）算法性质(3)同一个问题可以存在多种解决的算法。13（二）问题求解过程1)问题的陈述

用科学规范的语言,对所求解的问题做准确的描述.2)建立数学模型通过对问题的分析,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述.3)算法设计根据数学模型设计问题的计算机求解算法.14（二）问题求解过程1)问题的陈述14（二）问题求解过程4)算法的正确性证明

证明算法对一切合法输入均能在有限次计算后产生正确输出.5)算法的程序实现将算法正确地编写成机器语言程序.6)算法分析对执行该算法所消耗的计算机资源进行估算.15（二）问题求解过程4)算法的正确性证明15（三）如何设计算法通过学习已被实践证明是有用的一些基本设计策略，如递归、回溯等，掌握一般的算法设计方法，学会设计高效的算法。16（三）如何设计算法通过学习已被实践证明是有用的一些基本设计策（四）如何确认算法（证明其正确性）证明算法对所有可能的输入都能算出正确的答案，这一工作称为算法确认。这一领域是当前许多计算机工作者集中研究的对象，还处于相当初期的阶段。在学习本课程中，我们仅对算法的正确性进行一般的非形式化讨论，以及对算法的程序实现进行测试验证。17（四）如何确认算法（证明其正确性）证明算法对所有可能的输入都（五）如何分析（评价）算法分析算法包括定量的分析算法需要多少计算时间和存储空间，分析算法不仅可以预计算法能否有效得完成任务，而且可以知道算法在最坏、最好和平均情况下的运算时间，对解决同一问题的不同算法的优劣作出比较。18（五）如何分析（评价）算法分析算法包括定量的分析算法需要多二、算法的几种描述方式1、计算两个整数的最大公约数问题的一个现代数学术语表述欧几里得算法基于的方法是重复应用下列等式：

gcd(m,n)=gcd(n,mmodn)，直到mmodn等于0。gcd(60,24)=gcd(24,12)=gcd(12,0)=12注：gcd(m,0)=m，mmodn表示m除以n之后的余数，称为模运算19二、算法的几种描述方式1、计算两个整数的最大公约数问题的一个2、算法的一个结构化的描述计算gcd（m，n）的欧几里得算法：第一步：如果n=0,返回m的值作为结果，同时过程结束；否则，进入第二步。第二步：用n去除m，将余数赋给r。第三步：将n的值赋给m，将r的值赋给n，返回第一步。202、算法的一个结构化的描述计算gcd（m，n）的欧几里得算法ALGORITHMEuclid（m，n）//计算gcd（m，n）//输入：非负整数m，n，其中m，n不同时为零//输出：m，n的最大公约数whilen≠0do r ←mmodn m ←n n ←rreturnm3、算法的一个伪代码描述21ALGORITHMEuclid（m，n）3、算法的一个伪代4、算法的一个c++程序语言实现intEuclid（intm，intn）//计算gcd（m，n）//输入：非负整数m，n，其中m，n不同时为零//输出：m，n的最大公约数{intr=0;if(m*n==0)return0;//m，n不符合输入规范时返回0

while(n>0){r=mmodn; m=n; n=r;}returnm;}

224、算法的一个c++程序语言实现intEuclid（int其他方法程序流程图等，不再一一列举。23其他方法程序流程图等，不再一一列举。23三、算法复杂性分析算法复杂性是算法效率的度量，是评价算法优劣的重要依据。算法复杂性的高低体现在运行算法所需要的计算机资源，即时间和空间（存储器）资源的多少上。算法的时间复杂性T(n)，空间复杂性S(n)。其中n是问题的规模（输入大小）。24三、算法复杂性分析算法复杂性是算法效率的度量，是评价算法优劣三、算法复杂性分析

本课程主要对算法的时间复杂性进行分析。关于算法的复杂性，有两个问题要弄清楚：（1）用怎样的一个量（指标）来表达一个算法的复杂性；（2）对于一个算法，怎样具体计算它的复杂性。25三、算法复杂性分析本课程主要对算法的时间复杂性进行分析。21、算法的三种时间复杂性算法的最坏、最好和平均时间复杂性（1）最坏情况下的时间复杂性

Tmax(n)=max{T(I)|size(I)=n}（2）最好情况下的时间复杂性

Tmin(n)=min{T(I)|size(I)=n}其中size(I)=n表示I是规模为n的实例261、算法的三种时间复杂性算法的最坏、最好和平均时间复杂性261、算法的三种时间复杂性（3）平均情况下的时间复杂性

Tavg(n)=

其中p(I)是实例I出现的概率。271、算法的三种时间复杂性（3）平均情况下的时间复杂性272、算法的时间复杂性计算例：顺序查找算法的时间复杂度计算：

已知不重复，从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数。对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0。

A[1]A[m]A[i]=c282、算法的时间复杂性计算例：顺序查找算法的时间复杂度计算：A分析:问题的规模为m设元运算执行时间：赋值a,判断t,加法s设c在A中查找成功29分析:292、算法的时间复杂性计算

intsearch(intA[],intm,intc) {inti=1; a while(A[i]<c&&i<m)

2mt i=i+1; (m-1)(s+a) if(A[i]==c) t returni;

elsereturn0; a }302、算法的时间复杂性计算intsearch(int最好情况:比较次数为1Tmin(m)=2a+2t－－时间复杂度函数最坏情况：比较次数为mTmax(m)=(m+1)a+(2m+1)t+(m-1)s平均情况：假定所有数组元素是不同的，并且每个元素被查找的概率是相同的。则平均比较次数为(m+1)/2Tavg(m)=0.5(m+3)a+0.5(2m+3)t+0.5(m-1)s2、算法的时间复杂性计算31最好情况:比较次数为12、算法的时间复杂性计算313、算法的改进上面例子中顺序查找算法的改进有：进行二分（折半）查找，即反复把供查找的数组分成两半，然后在其中一半继续查找。A[1]A[m]A[mid]A[mid]>cA[mid]<c323、算法的改进上面例子中顺序查找算法的改进有：A[1]A[m3、算法的改进intsearch_Bin(intA[],intc,intm) {intlow=1,high=m,mid=0,found=0;while(found==0&&high>=low){mid=(low+high)/2;if(A[mid]==c)found=1; elseif(A[mid]<c)low=mid+1elsehigh=mid-1 } if(found==1)returnmid;

elsereturn0; }333、算法的改进intsearch_Bin(intA[]3、算法的改进在最坏情况下，查找成功时最多只需检测A[1...m]中的∟logm」+1个分量，而改进前最坏情况下需要比较m个分量。如：c=5,A[1...11]={1,2,3,.....,11}对于查找算法，减少比较次数可以最有效地降低算法时间复杂度。算法改进的目的就是为了提高效率！注：本书中出现的logn相当于log2n。343、算法的改进在最坏情况下，查找成功时最多只需检测A[1.4、时间复杂性的计量算法的时间复杂性计量是算法的运算时间，但对于同一类问题，采用算法的基本运算次数作为算法的运算时间。“汉诺塔”的基本运算是圆盘的移动次数；查找、排序算法：元素的比较次数；矩阵相乘：两个数的相乘；树的搜索：节点的访问；图的算法：节点和边的访问。354、时间复杂性的计量算法的时间复杂性计量是算法的运算时间，但四、算法的渐近复杂性随着要求用计算机解决的问题越来越复杂，规模越来越大，对这类问题的求解算法做复杂性分析具有特别重要的意义。因此，对于规模充分大，结构又十分复杂的算法，人们提出了如何简化其复杂性分析，及求解其复杂性函数f(n)的上界和下界的问题。36四、算法的渐近复杂性随着要求用计算机解决的问题越来越复杂，规渐近复杂性的数学表述用形式简单的函数代替形式复杂的函数：T(n),asn;（这里是指充分大）(T(n)-t(n))/T(n)0

，asn;t(n)是T(n)的渐近性态，为算法的渐近复杂性。37渐近复杂性的数学表述用形式简单的函数代替形式复杂的函数：37渐近复杂性的数学表述(T(n)-t(n))/T(n)0

，asn;在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。例如：T(n)=3n2+4nlogn+7;t(n)=3n2

T(n)=4nlogn+7n;t(n)=4nlogn因此，只要考察当问题规模充分大时，算法复杂性在渐进意义下的阶，就可以判定出哪一个算法的效率高。38渐近复杂性的数学表述(T(n)-t(n))/T(n)为此，我们引入以下渐进意义下的记号：

O

o

θ39为此，我们引入以下渐进意义下的记号：39（1）渐近上界记号O在下面的讨论中，对所有n，时间复杂性函数f(n)0，g(n)0，g(n)也称为f(n)的阶函数。渐近上界记号O——给出函数f的一个上限O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)

cg(n)}40（1）渐近上界记号O在下面的讨论中，对所有n，时间复杂性函数（1）渐近上界记号O——例例1：【线性函数】考察f(n)=3n+2。当n>=2时，3n+2<=3n+n=4n，所以f(n)=O(n)，f(n)是一个线性变化的函数。类似地，100n+6=O(n)。特别地，当f(n)是一个常数c时，如f(n)=9，可以记为f(n)=O(1)。41（1）渐近上界记号O——例例1：【线性函数】考察f(n)=3（1）渐近上界记号O——例例2：【平方函数】考察f(n2)=10n2+4n+2。当n>=2时，10n2+4n+2<=10n2+5n

，当n>=5时，10n2+5n<=10n2+n2

＝11n2

，所以f(n)=O(n2)。同理，对于f(n)=6×2n+n2

，f(n)=O(2n)。（当n>=4时，n2<=2n

）42（1）渐近上界记号O——例例2：【平方函数】考察f(n2)=（2）渐近下界记号渐近下界记号

——给出函数f的一个下限

(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0

cg(n)

f(n)}43（2）渐近下界记号渐近下界记号——给出函数f的一个下限（2）渐近下界记号

——例例：对于所有n，有以下推导：∵3n+22n∴3n+2=(n)∵100n+6100n∴

100n+6=(n)∵10n2+4n+2

10n2

∴

10n2+4n+2=(n2)∵6×2n+n2

6×2n

∴6×2n+n2=(2n)。44（2）渐近下界记号——例例：对于所有n，有以下推导：44（3）非紧上界记号o和

非紧下界记号非紧上界记号oo(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0f(n)<cg(n)}等价于

f(n)/g(n)0

，asn。45（3）非紧上界记号o和

非紧下界记号非紧上界记号o45（3）非紧上界记号o和非紧下界记号非紧下界记号

(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0cg(n)

<f(n)}等价于

f(n)/g(n)

，asn。f(n)

(g(n))

g(n)

o(f(n))46（3）非紧上界记号o和非紧下界记号非紧下界记号46（3）非紧上界记号o和非紧下界记号－例例1：3n+2=o(n2)。例2：10n2+4n+2=

(n)。47（3）非紧上界记号o和非紧下界记号－例例1：3n+2=（4）紧渐近界记号θ

θ(g(n))={f(n)|存在正常数c1,c2和n0使得对所有nn0有：c1g(n)f(n)

c2g(n)}记号θ适用于同一个函数g既可以作为函数f的上限也可以作为f的下限的情形。

定理1：

θ(g(n))=O(g(n))

(g(n))48（4）紧渐近界记号θθ(g(n))={f(n)|（4）紧渐近界记号θ—例例：对于所有n，有：3n+2=θ(n)100n+6=θ(n)10n2+4n+2=θ(n2)6×2n+n2=θ(2n)。49（4）紧渐近界记号θ—例例：对于所有n，有：49Oθf(n)=O(g(n))f(n)的阶不高于g(n)的阶；f(n)=(g(n))f(n)的阶不低于g(n)的阶；f(n)=θ(g(n))f(n)与g(n)同阶。课后习题1-650Oθf(n)=O(g(n))O的运算规则以下设f(n),g(n)是定义在正数集上的正函数：(1)O(f)+O(g）=O(max(f,g))(2)O(f)+O(g）=O(f+g)(3)O(f)O(g）=O(fg)(4)如果f(n)=O(g(n)),则O(f)+O(g)=O(g)(5)O(cf(n))=O(f(n)),其中c是一个正的常数(6)f=O(f)51O的运算规则以下设f(n),g(n)是定义在正数集上的正函数