算法设计与分析 课件 第一章 绪论

计算机算法设计与分析第1章概述例1.1求两个正整数的最大公约数方法一：利用质因数分解法求解最大公约数，其具体步骤描述如下：（1）输入两个正整数a和b。（2）将a和b分别进行质因数分解，得到它们的所有质因数的乘积形式。（3）将a和b中相同的所有质因数乘积计算出来，得到的结果即为a和b的最大公约数。若a或b无质因数（除1和该数本身外），则最大公约数为1。例1.1求任意两个正整数的最大公约数以具体计算为例，假设需要求解的两个整数为42和28，42=2×3×7，28=2×2×7共同的质因数2和7，因此，42和28的最大公约数为2×7=14利用方法一可以快速求出两个整数的最大公约数，但方法一的描述过程不能称为一个正真意义上的算法，因为第(2)步没有明确如何将正整数a和b进行质因数分解，且质因数分解是一个NP类问题，目前尚未找到有效的解决方法。第(3)步也没有明确定义在两个质因数序列中如何找到相同的质因数元素。因此方法一描述不满足算法的确定性和可行性。例1.1求任意两个正整数的最大公约数方法二：利用蛮力穷举法求解最大公约数，具体步骤描述如下：（1）输入a和b。（2）将a和b中的较小者赋值给r。（3）若a、b除以r的余数同时等于0，转（5），否则往下执行（4）。（4）执行r=r-1，转（3）。（5）输出r，执行结束。主要思想：是从两个整数中较小者开始，去逐步寻找能被两整数同时整除的数，一旦发现则终止寻找，并将该数作为两整数的最大公约数。例1.1求任意两个正整数的最大公约数r=2842%28=14,28%28=0,r=28-1=2742%27=15,28%27=1,r=27-1=2642%26=16,28%26=2,r=26-1=2542%25=17,28%25=3,r=25-1=2442%24=18,28%24=4,r=24-1=2342%23=19,28%23=5,r=23-1=2242%22=20,28%22=6,r=22-1=2142%21=0,28%21=7,r=21-1=2042%20=2,28%20=8,r=20-1=1942%19=4,28%19=9,r=19-1=1842%18=6,28%18=10,r=18-1=1742%17=8,28%17=11,r=17-1=1642%16=10,28%16=12,r=16-1=1542%15=12,28%15=13,r=15-1=1442%14=0,28%14=0输出r，结果为14。以具体计算为例，设a=42和b=28，则计算过程为：例1.1求任意两个正整数的最大公约数在a=42，b=28的情况下，穷举法运行了15步才计算出结果。方法二穷举法非常简单，计算过程易于理解，但穷举法的效率非常低。例1.1求任意两个正整数的最大公约数方法三：利用辗转相除法（也称欧几里得算法）求解最大公约数，具体步骤描述如下：（1）输入两个整数a和b。（2）若a<b则将a，b的值互换，以保持a是两个整数中较大者，b为较小者。（3）将a除以b的余数赋值给r，若余数r等于0，则执行（5），否则往下执行（4）（4）将除数b赋值给a，将余数r赋值给b，转（3）重复执行（5）b为所求最大公约数，输出b，执行结束。例1.1求任意两个正整数的最大公约数以具体计算为例，设a=42和b=28，则计算过程为：r=42%28=14,a=28,b=14r=28%14=0输出b，结果为14。在a=42，b=28的情况下，辗转相除法只运行了2步就计算出结果。例1.1求任意两个正整数的最大公约数算法：辗转相除法;输入：两个正整数a,b;

输出：最大公约数Max_common_divisor(a,b)beginifa<bthena与b互换endramodbwhiler≠0doab,br,ramodbendprintbend计算机算法设计与分析第一章绪论一个快递小哥从快递中心点出发，到周边四个小区送快递，要求经过每个小区且只能每个小区仅经过一次，最后回到快递中心点。问快递小哥应如何安排派送路线较好？例1.3快递员路线安排问题起

终ABCDEA03456B30265C42043D56405E65350（1）问题分析与问题抽象，这是一个典型的TSP问题将小区抽象为下图的顶点，两个小区之间有路直达，则对应的两个顶点之间有边关联，边的权值为两个小区之间的距离。则将快递员路线安排问题抽象为从顶点A(设A为快递中心)出发经过图中其余顶点后回到顶点A的最短简单回路问题。例1.3快递员路线安排问题3365456542EBDCA（2）数学建模：例1.3快递员路线安排问题3365456542EBDCA（3）方法一蛮力法：列出每一条可供选择的路线，计算出每条路线的距离长度，最后从中选择出一条最短路线。最短路程为：A-->B-->C-->E-->D-->A或者A-->D-->E-->C-->B-->A，最短路径长度为:18。例1.3快递员路线安排问题3365456542EBDCA（3）蛮力法算法效率分析：使用蛮力法列举除出发小区外所有小区的排列，然后选取路径最短的路线。n-1个小区的排列数为(n-1)!，当n=20时，遍历路线总数约为1.216×1017，计算机以每秒1000万条路线的检索速度计算，则约需要386年才能完成。故蛮力法的时间复杂度太高，当顶点数过多时并不适用。例1.3快递员路线安排问题（3）方法二贪心法：每次在选择下一个小区时，只考虑当前情况。在没有经过的小区中，选择距离当前小区最近的一个，直到经过所有小区，最后回到快递中心。A例1.3快递员路线安排问题3365456542EBDCA贪心法的优点是效率很高，只要n-1步判断就能得到结果。但缺点是不一定能找到问题的最优解。算法：贪心法—伪代码描述输入：小区数量n，邻接矩阵e[i,j]，顶点v[i]，出发小区编号go_city，index当前小区编号。输出：最短路线上的顶点信息，最短路径长度min_l。Greedy(index):beginfori

1tondo ifi不是出发顶点go_citythen forj

1tondo if没有经过小区jthen

筛选与当前出发点最短的顶点，并标记为cur_j endifendfor min_l

min_l+e[index,cur_j] index

cur_j//从出发点cur_j，继续下一步求解

并置cur_j顶点为经过标记

endifend for

min_lmin_l+e[index,go_city]//加上最后一个小区到go_city小区的距离end例1.3快递员路线安排问题计算机算法设计与分析第一章概述1.4.1算法的效率分析目的评估算法体现算法运行时所需要消耗的计算机资源占用CPU的计算时间量称为时间复杂度占用内存的存储空间量称为空间复杂度算法复杂度分析一般采用事前分析方式而是不事后统计法算法的效率分析算法的时间复杂度T和空间复杂度S的函数：T=T(N,I)S=S(N,I)N表示问题规模，I表示算法输入在实际应用中，关注时间效率多于空间效率。算法时间复杂度分析评估算法时间复杂度，应尽量做到客观反映算法的本质特征和属性。所以，算法时间复杂度分析应该要有一个不依赖于计算机硬件配置、问题规模和输入实例的抽象表示。算法时间复杂度分析假设在一台抽象的计算机上提供了k种元运算O1，O2，…，Ok，每个元运算执行的时间分别为t1，t2，...，tk。元运算通常指的是算法中最基本的操作步骤，一个元运算可以是基本的算术运算（如加法、减法、乘法、除法）、比较操作、赋值操作、数组访问或迭代循环等。算法时间复杂度分析T(N，I)表示算法在这台抽象计算机上运行所需要的的时间，设，在算法中

元运算Oi被调用的次数为ei，ei=ei(N,I)，因此，T(N,I)一般化的表示：算法时间复杂度分析为消除公式中ti表示的元运算执行的具体时间，不妨假设所有的元运算都在一个单位时间内完成或者将ti抽象表示为一条执行语句或表达式所用时间，则计算T(N,I)的工作就变为统计计算语句的频度，从而简化复杂度的求解。例1.4插入排序问题时间复杂度计算

算法：插入排序（升序排序）

输入：数组元素array，元素个数n

输出：升序的数组元素array

InsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移动元素6 j

j–17 end8 array[j+1]

key9

endend当输入数据为1,2,3,4,5时，语句2、3、8被执行4次，语句5、6被执行0次。当输入数据为5,4,3,2,1时，语句2、3、8被执行4次，语句5、6被执行10次。算法时间复杂度分析对同一个算法，运行不同的输入实例时，算法语句执行的次数差异明显。实际上，在统计时间复杂度时，我们不可能对规模N的每一种合法输入都去统计各个算法语句执行的次数，这时就需要对输入实例做一个合理简化，即将输入实例进行特化。算法时间复杂度分析（1）最坏情况下的时间复杂度：IN是规模为N的合法输入集合，I*是IN中使T(N,I)达到Tmax(N)的合法输入。最坏情况下的时间复杂度就是将所有的合法输入实例中最坏的那个输入实例I*找出来，统计在输入实例I*时算法语句执行的次数来评估算法时间复杂度。算法时间复杂度分析（2）最好情况下的时间复杂度：I'是IN中使T(N,I)达到Tmin(N)的合法输入，将所有的合法输入实例中最好的那个输入实例I'找出来，统计在输入实例I'时算法语句执行的次数来评估算法时间复杂度。算法时间复杂度分析（3）平均情况下的时间复杂度：P(I)是算法应用中出现输入实例I的概率，全部合法输入实例的概率总和为1。平均时间复杂度是用每一个输入实例出现的概率，计算其数学期望。在分析算法时间复杂度的时候，往往关注的是最坏情况下算法的时间复杂度。例1.4插入排序问题时间复杂度计算

算法：插入排序（升序排序）

输入：数组元素array，元素个数n

输出：升序的数组元素array

InsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移动元素6 j

j–17 end8 array[j+1]

key9

endend语句2,3,8分别执行N-1次语句5,6执行的次数分为1,2,3，...，N-1次算法时间复杂度分析语句2,3,8分别执行N-1次，语句5,6执行的次数分为1,2,3，...，N-1次，所以：当N比较大时，N2/2为主要因素，后面项为次要因素忽略次要因素，简化时间复杂度函数的表示。计算机算法设计与分析第一章概述渐近时间复杂度分析设T(N)是算法A的时间复杂度函数，N是问题规模，N≥0，且N∈Z。当N

∞时，T(N)

∞。对于T(N)，如果存在T'(N)，使得当N

∞时有那么，我们就说T'(N)是算法A当N

∞的渐近复杂度。渐近时间复杂度分析在渐近复杂度函数T'(N)中，阶与T'(N)中的常数因子没有关系，所以T'(N)可进一步简化，省略常数因子。例1.4中的T'(N)可取值N2即可。需要注意的是，函数简化并不是一种精确计算复杂度的方法，而是一种近似评估的方式。例1.4中的T'(N)=N2/2+5N/2-3渐近时间复杂度分析定义1.1设f(N)和g(N)是正整数集上的函数。如果∃c≥0和自然数N0，使得当N≥N0时有0≤f(N)≤cg(N)，则称函数f(N)充分大时上有界，g(N)是f(N)的一个上界，记为f(N)=O(g(N))，即f(N)的阶不高于g(N)的阶，如图所示。不是直接比较f(N)和g(N)的数值大小，O表示的只是一个充分大的上界，上界的阶越低则算法时间复杂度的评估越精确，结果值越有价值N0cg(N)f(N)渐近时间复杂度分析例1.5求5n+4，n2+nlogn，2n+n2，10000的上界。n≥4时，5n+4≤6n，则5n+4=O(n)n≥1时，n2+nlogn≤2n2，则n2+nlogn=O(n2)n≥1时，2n+n2≤2*2n，则2n+n2=O(2n)对于常整数10000，算法执行时间与问题规模无关，无论问题规模多大，算法都在固定时间内完成。因此无论是10000还是其他任何常数输入，它的时间复杂度是一个常数级别的复杂度，即O(1)。渐近时间复杂度分析例1.6给定多项式函数：

试证明T(n)=O(nm)。证明：设n0=1,对于任意的n，若n≥n0=1，则：存在c≥0和自然数n0=1，使得当n≥n0时有T(n)≤cnm，故T(n)=O(nm)成立。渐近时间复杂度分析根据定义1.1，我们有如下O(n)的性质：（1）O(f)+O(g)=O(max(f,g))；算法最复杂的部分运行时间就是算法的时间复杂度。（2）O(f)+O(g)=O(f+g)；算法中并行语句的时间复杂度等于各个语句运行时间之和。（3）O(f)×O(g)=O(f×g)；循环的时间复杂度等于循环体运行时间与循环次数的乘积。（4）O(cf(n))=O(f(n))，c∈Z+；算法的时间复杂度是运行时间函数的数量级。（5）如果g(n)=O(f(n))，则O(f)+O(g)=O(f)；算法的时间复杂度是运行时间函数的最高阶。（6）f=O(f)。渐近时间复杂度分析定义1.2设f(N)和g(N)是正整数集上的函数。如果∃c≥0和自然数N0，使得当N≥N0时有f(N)≥cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是f(N)的一个下界，记为f(N)=Ω(g(N))，即f(N)的阶不低于g(N)的阶，如图所示。N0cg(N)f(N)渐近时间复杂度分析例1.8求5n+1，n2+nlogn的下界。当n≥1时，5n+1≥5n，则5n+1=Ω(n)当n≥1时，n2+nlogn≥n2，则n2+

nlogn

=Ω(n2)；n2+

nlogn

≥nlogn，则n2+

nlogn

=Ω(nlogn)，但nlogn≠Ω(n2)。根据定义1.2可知，n2+nlogn=Ω(n2)和n2+

nlogn

=Ω(nlogn)都成立，算法时间复杂度一般取最大下界。下界的阶越高，评估越精确，结果越有价值，Ω通常也表示求解问题的最好情况下的时间复杂度。渐近时间复杂度分析定义1.3设f(N)和g(N)是正整数集上的函数。如果∃c1≥0、∃c2≥0和自然数N0，使得当N≥N0时有0≤c1g(N)≤f(N)≤c2g(N)，则称g(N)是f(N)的紧确界。记为f(N)=θ(g(N))，如图1.7所示。若f(N)=θ(g(N))，则当且仅当f(n)=O(g(N))且f(N)=Ω(g(N))，也称g(N)和f(N)同阶。N0c1g(N)f(N)c2g(N)渐近时间复杂度分析例1.9

求n2+nlogn的紧确界。由例1.5和例1.8可知：n2+nlogn=O(n2)，n2+nlogn=Ω(n2)，因此n2+nlogn=θ(n2)。计算机算法设计与分析第一章概述非递归算法的时间复杂度分析在分析非递归算法时，主要遵循如下步骤：（1）确定核心操作：比如算法中的赋值、比较、算术运算、逻辑运算、变量输入输出等操作，一般称为基本操作。也可以将内层循环的若干个基本操作构成的程序块整体看成一个稍大一点的基本操作。（2）计算核心操作总的执行次数：计算核心基本操作的执行次数，一般是多项式和的形式。（3）求解其渐近解：对核心操作总执行次数表达式进行计算化简，并用O(•)形式表示。非递归算法的时间复杂度分析例1.10查找元素t在数组a中第一次出现的位置，若查找失败返回-1。分析顺序查找算法时间复杂度。本算法描述中的核心操作是语句3，最好的情况下，时间复杂度T(n)=O(1)。最坏的情况是整个循环语句1执行完毕，即语句3被执行n次而结束，此时T(n)=O(n)非递归算法的时间复杂度分析例1.11查找元素t在升序数组a中第一次出现的位置，若查找失败返回-1。分析二分查找算法时间复杂度。非递归算法的时间复杂度分析核心操作是语句3~6，最好的情况下，执行到语句4直接结束，时间复杂度T(n)=O(1)。最坏情况是每次进入while循环，搜索范围a[left]~a[right]