算法引论及简单算法.pptx

补充材料补充材料1 算法引论及简单算法算法引论及简单算法清华大学 自动化系刘连臣2010年11月1日计算机语言与程序设计基础计算机语言与程序设计基础 1注注 意意2与数据结构的区别：与数据结构的区别：考虑问题的考虑问题的角度角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。心不同设计技术的适用性和效率。考虑问题的考虑问题的高度高度：数据结构关心的是解具体问题，算法不仅如此，它提供一种解：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。决问题的通用方法。与其他课程的关系与其他课程的关系高级程序设计语言（高级程序设计语言（C语言，等）语言，等）数据结构数据结构 算法设计算法设计与与分析分析 系统的设计与实现系统的设计与实现 3主要内容主要内容o目标：目标：了解算法分析的了解算法分析的了解算法分析的了解算法分析的基本含义基本含义基本含义基本含义。掌握。掌握。掌握。掌握查找算法查找算法查找算法查找算法、排序算法排序算法排序算法排序算法、递推算法递推算法递推算法递推算法等算法理念。等算法理念。等算法理念。等算法理念。提纲提纲补补1.1 1.1 算法分析算法分析补补1.2 1.2 查找算法查找算法补补1.3 1.3 排序算法排序算法补补1.4 1.4 递推算法递推算法4补补11 算法分析算法分析o前面的课程内容以前面的课程内容以C语言语法为主语言语法为主o本补充章介绍一些基本算法本补充章介绍一些基本算法o大家在编写程序的时候，大家在编写程序的时候，“八仙过海，八仙过海，各显神通各显神通”，解决同一个问题，可以使，解决同一个问题，可以使用各种方法。用各种方法。o算法之间存在着算法之间存在着“优劣优劣”之分之分5补补1.1 算法分析算法分析1、算法分析的目的算法分析的目的 o通过对算法分析，在把算法变成程序实际运通过对算法分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法行前，就知道为完成一项任务所设计的算法的好坏，从而运行好算法，改进差算法，避的好坏，从而运行好算法，改进差算法，避免无益的人力和物力浪费。免无益的人力和物力浪费。6补补1.1 算法分析算法分析2、算法分析的含义算法分析的含义o算法分析是一种分析技术，它以独立于具体的硬件平算法分析是一种分析技术，它以独立于具体的硬件平台、编译器和编程语言的方式，来描述算法的执行行台、编译器和编程语言的方式，来描述算法的执行行为，即它关心的是算法，而不是程序。为，即它关心的是算法，而不是程序。o算法分析是一种测量算法的性能的方法，它不关心精算法分析是一种测量算法的性能的方法，它不关心精确的细节，如在算法的某次运行中总共执行了多少条确的细节，如在算法的某次运行中总共执行了多少条机器指令，而是想要一个大致的估计，即随着输入数机器指令，而是想要一个大致的估计，即随着输入数据规模的增大，算法所需工作量以何种速度递增。据规模的增大，算法所需工作量以何种速度递增。（关心变化趋势）（关心变化趋势）7补补1.1 算法分析算法分析3、算法复杂性算法复杂性 时间复杂性和空间复杂性时间复杂性和空间复杂性8补补1.1 算法分析算法分析1.有些计算机需要用户提供程序运行有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，时间的上限，一旦达到这个上限，程序将被强制结束。程序将被强制结束。2.正在开发的程序可能需要提供一个正在开发的程序可能需要提供一个满意的实时响应。满意的实时响应。为什么要考虑时间复杂性？为什么要考虑时间复杂性？91.1.多用户系统中运行时，需指明分配给该程序的内多用户系统中运行时，需指明分配给该程序的内存大小。存大小。2.2.可提前知道是否有足够可用的内存来运行该程序。可提前知道是否有足够可用的内存来运行该程序。3.3.一个问题可能有若干个内存需求各不相同的解决一个问题可能有若干个内存需求各不相同的解决方案，从中择取。方案，从中择取。4.4.利用空间复杂性来估算一个程序所能解决问题的利用空间复杂性来估算一个程序所能解决问题的最大规模。最大规模。考虑程序的空间复杂性的理由：考虑程序的空间复杂性的理由：补补1.1 算法分析算法分析104.如何进行算法分析？如何进行算法分析？o事前分析事前分析：就算法本身，通过对其执行性能的理论分析，：就算法本身，通过对其执行性能的理论分析，得出关于算法特性得出关于算法特性时间和空间时间和空间的一个特征函数的一个特征函数（）与计算机软硬件没有直接关系。与计算机软硬件没有直接关系。o事后测试事后测试：将算法编制成程序后放到计算机上运行，收：将算法编制成程序后放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断集其执行时间和空间占用等统计资料，进行分析判断直接与物理实现有关。直接与物理实现有关。补补1.1 算法分析算法分析111）事前分析）事前分析o目的：试图得出关于算法执行特性的一种形式描目的：试图得出关于算法执行特性的一种形式描 述，以述，以“理论上理论上”衡量算法衡量算法“好坏好坏”。o如何给出反映算法执行特性的描述如何给出反映算法执行特性的描述？最直接方法：最直接方法：统计算法中各种运算的执行情况：统计算法中各种运算的执行情况：运用了哪些运算运用了哪些运算 每种运算被执行的次数每种运算被执行的次数 该种运算执行一次所花费的时间该种运算执行一次所花费的时间 算法的执行时间算法的执行时间=Fi*ti补补1.1 算法分析算法分析12估算执行时间的方法估算执行时间的方法 选择一种或多种（如加、乘和比较等），然后确定这种（些）选择一种或多种（如加、乘和比较等），然后确定这种（些）操作分别执行了多少次。操作分别执行了多少次。令令n代表程序实例特征，则执行时间计算公式为：代表程序实例特征，则执行时间计算公式为：TP（n）=c1ADD(n)+c2SUB(n)+c3MUL(n)+c4DIV(n)+c1、c2、c3、c4分别表示一次加、分别表示一次加、减、乘、减、乘、除操作所需的时间。除操作所需的时间。函数函数ADD(n)、SUB(n)、MUL(n)、DIV(n)分别表示程分别表示程序序P中，所使用的加、减、乘、中，所使用的加、减、乘、除操作的次数。除操作的次数。这种方法是否成功取决这种方法是否成功取决于识别关键操作的能力，于识别关键操作的能力，这些关键操作对时间复这些关键操作对时间复杂性的影响最大。杂性的影响最大。一条语句在整个程序运行时实际执行时间一条语句在整个程序运行时实际执行时间=频率计数频率计数*每执行一次该语句所需的时间每执行一次该语句所需的时间补补1.1 算法分析算法分析13o频率计数：频率计数：算法中算法中语句语句或或运算运算的执行次数。的执行次数。例：例：x=x+y for(i=1;i=n;i+)for(i=1;i=n;i+)x=x+y;for(j=1;j=n;j+)x=x+y;(a)(b)(c)分析：分析：(a)：x=x+y执行了执行了1次次 (b)：x=x+y执行了执行了n次次 (c)：x=x+y执行了执行了n2次次 注：在事前分析中，只限于确定与所使用机器及其他环境因素无关的频率计注：在事前分析中，只限于确定与所使用机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。数，依此建立一种理论上分析模型。补补1.1 算法分析算法分析14o数量级数量级语句的数量级语句的数量级：语句的执行频率。：语句的执行频率。例：例：1，n，n2 算法的数量级算法的数量级：算法包含所有语句的执行频率之和。：算法包含所有语句的执行频率之和。算法的数量级从本质上反映了一个算法的执行特性。算法的数量级从本质上反映了一个算法的执行特性。例：求解同一问题的三个算法分别具有例：求解同一问题的三个算法分别具有n,n2,n3数量级。数量级。若若n=10，则可能的执行时间将分别是，则可能的执行时间将分别是10，100，1000 个单位时间个单位时间与环境因素无关。与环境因素无关。补补1.1 算法分析算法分析15补补1.1 算法分析算法分析5、算法复杂性的等级算法复杂性的等级o常量阶常量阶n时间复杂度为时间复杂度为O(1)n算法运行时间不随着问题的规模而变化算法运行时间不随着问题的规模而变化n如：如：o简单的赋值语句，简单的赋值语句，x=y;o算术运算，算术运算，x=y*5+z%3;o固定次数的循环语句等固定次数的循环语句等for(i=0;i10;i+)for(j=0;j20;j+)aij=0;16补补1.1 算法分析算法分析o线性阶线性阶n时间复杂度为时间复杂度为O(n)n算法运行时间随着问题的规模而成线性变化算法运行时间随着问题的规模而成线性变化for(i=0;in;i+)sum=sun+i;算法执行了多少次运算？算法执行了多少次运算？i=0;执行了执行了1次次in;执行了执行了n+1次次i+；执行了执行了n次次sum=sun+i;执行了执行了n次次共执行了共执行了3n+2次运算次运算时间复杂度就是时间复杂度就是O（3n+2）实际上，算法的时间复杂度并不精确实际上，算法的时间复杂度并不精确计算基本操作的执行次数，它主要考计算基本操作的执行次数，它主要考虑问题规模的增长率。虑问题规模的增长率。O（n）17补补1.1 算法分析算法分析o平方阶平方阶n时间复杂度为时间复杂度为O(n2)n算法运行时间随着问题的规模而成平方变化算法运行时间随着问题的规模而成平方变化for(i=0;in;i+)for(j=0;jn;j+)sum=sun+aij;/执行执行n2次次printf(“%dn”,sum);/执行执行n次次时间复杂度就是时间复杂度就是O（n2）18补补1.1 算法分析算法分析o多项式阶多项式阶n时间复杂度为时间复杂度为O(nd)d为固定常数为固定常数n算法运行时间随着问题的规模而成算法运行时间随着问题的规模而成d次多项式阶变化次多项式阶变化o对数阶对数阶 O(logn)o指数阶指数阶 O(log2n)o阶乘阶阶乘阶 O(n!)o若若T(n)=adnd+a1n+a0是一个是一个d次多项次多项 式，则有式，则有T(n)=O(nd)195、算法分类算法分类（计算时间）（计算时间）多项式时间算法：多项式时间算法：可用多项式（函数）对其计算时间限可用多项式（函数）对其计算时间限界的算法。界的算法。常见的多项式限界函数有：常见的多项式限界函数有：(1)(1)(logn)(logn)(n)(n)(nlogn)(nlogn)(n(n2 2)(n(n3 3)指数时间算法：指数时间算法：计算时间用指数函数限界的算法计算时间用指数函数限界的算法 常见的指数时间限界函数：常见的指数时间限界函数：(2(2n n)(n(n！)(n(nn n)说明：当说明：当n n取值较大时，指数时间算法和多项式时间取值较大时，指数时间算法和多项式时间 算法在计算法在计算时间上非常悬殊。算时间上非常悬殊。补补1.1 算法分析算法分析20o 计算时间的数量级对算法有效性的影响计算时间的数量级对算法有效性的影响 数量级数量级的大小对算法的有效性有的大小对算法的有效性有决定性决定性的影响。的影响。例：假设解决同一个问题的两个算法，它们都有例：假设解决同一个问题的两个算法，它们都有n个输入，计算时个输入，计算时间的数量级分别是间的数量级分别是n2和和nlogn。则：。则：n=1024：分别需要：分别需要1048576和和10240次运算。次运算。n=2048：分别需要：分别需要4194304和和22528次运算。次运算。分析：在分析：在n加倍的情况下，一个加倍的情况下，一个(n(n2 2)的算法计算时间增长的算法计算时间增长4 4倍，而一个倍，而一个(nlogn)(nlogn)算法则只用算法则只用两两倍多一点的时间即可完成。倍多一点的时间即可完成。补补1.1 算法分析算法分析21典型的计算时间函数曲线典型的计算时间函数曲线结论：结论：在顺序处在顺序处理机上扩大所处理机上扩大所处理问题的规模，理问题的规模，最有效的途径是最有效的途径是降低算法计算复降低算法计算复杂度的数量级，杂度的数量级，而不是（仅仅依而不是（仅仅依靠）提高计算机靠）提高计算机的速度。的速度。补补1.1 算法分析算法分析22补补1.2 查找算法查找算法o所谓所谓查找（查找（search），），即根据给定的某个即根据给定的某个值，在一组数据（如一个数组）中，确定有值，在一组数据（如一个数组）中，确定有没有出现相同值得数据元素。没有出现相同值得数据元素。o查找是非常实用的算法。如，查找字典。查找是非常实用的算法。如，查找字典。o问题描述问题描述，令，令b表示被查找的数组，表示被查找的数组，n表示表示数组元素的个数，数组元素的个数，x表示被查找的目标。问表示被查找的目标。问题是题是“数据数据x是否出现在数组是否出现在数组b当中？当中？”23补补1.2 查找算法查找算法1、顺序查找方法、顺序查找方法n基本思路基本思路：从数组从数组b的第一个元素开始，逐个地与的第一个元素开始，逐个地与x进行进行比较，一直到查找成功或者所有的数组元素都已经处理比较，一直到查找成功或者所有的数组元素都已经处理完毕。完毕。参考程序：参考程序：int search(int b,int n,int x)int k;for(k=0;(kn)&(bk!=x);k+)if(kn)return(k);else return(-1);算法的复杂度为算法的复杂度为O(n)24补补1.2 查找算法查找算法2、折半查找方法、折半查找方法(对于有序数组对于有序数组)参考程序：参考程序：int search(int b,int n,int x)int L,R,mid;L=0;R=n-1;while(L=R)mid=(L+R)/2;if(x=bmid)return(mid);else if(xai，则交换它们，一直比较到，则交换它们，一直比较到an。同理。同理对对a1,a2,.an-1处理，即完成排序。处理，即完成排序。void bubble(int*a,int n)/*定义两个参数：数组首地址与数组大小定义两个参数：数组首地址与数组大小*/int i,j,temp;for(i=0;in-1;i+)for(j=i+1;jaj)temp=ai;ai=aj;aj=temp;27补补1.3 排序算法排序算法o选择法选择法 o基本思路：选择法循环过程与冒泡法一致，它还定义了记号基本思路：选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把然后依次把ak同后面元素比较，若同后面元素比较，若akaj,则使则使k=j.最后最后看看看看k=i是否还成立，不成立则交换是否还成立，不成立则交换ak,ai,这样就比冒泡法这样就比冒泡法省下许多无用的交换，提高了效率。省下许多无用的交换，提高了效率。void choise(int*a,int n)int i,j,k,temp;for(i=0;in-1;i+)k=i;/*给记号赋值给记号赋值*/for(j=i+1;jaj)k=j;/*是是k总是指向最小元素总是指向最小元素*/if(i!=k)/*当当k!=i是才交换，否则是才交换，否则ai即为最小即为最小*/temp=ai;ai=ak;ak=temp;28补补1.4 递推算法递推算法o递推（递推（Recursive Algorithm），），即从某个一直得初始即从某个一直得初始条件出发，根据这个已知的事实，并按照一定规律推断出下条件出发，根据这个已知的事实，并按照一定规律推断出下一个事实。然后再从这个新的已知的事实出发，向下再推断一个事实。然后再从这个新的已知的事实出发，向下再推断一个事实。一个事实。o递推是计算机数值计算的一个重要方法，可以将复杂的运算递推是计算机数值计算的一个重要方法，可以将复杂的运算简化为若干个重复的简单运算，从而发挥计算机长于重复处简化为若干个重复的简单运算，从而发挥计算机长于重复处理的特点。理的特点。o其实质与差分方程类似，著名的例子为其实质与差分方程类似，著名的例子为Fibonacci数列。数列。29补补1.4 递推算法递推算法o例：猴子吃桃例：猴子吃桃n有一只小猴子，有一天摘了一堆桃子，当天吃有一只小猴子，有一天摘了一堆桃子，当天吃掉了一半，后来觉得不过瘾，就又多吃了一只。掉了一半，后来觉得不过瘾，就又多吃了一只。第二天，小猴子又将剩下的桃子吃掉了一半，第二天，小猴子又将剩下的桃子吃掉了一半，并多吃了一个。以后每天都吃了前一天剩下的并多吃了一个。以后每天都吃了前一天剩下的一半零一个。到了第十天的时候，发现只剩下一半零一个。到了第十天的时候，发现只剩下一只桃子了。请问小猴子第一天一共摘了多少一只桃子了。请问小猴子第一天一共摘了多少桃子？桃子？30补补1.4 递推算法递推算法o解题思路nT10=T9-T9/2-1 即即 T9=(T10+1)*2nT8=(T9+1)*2nT7=(T8+1)*2n nT1=(T2+1)*2n定义定义A为桃子的个数，第为桃子的个数，第10天为天为1个，第个，第9天为天为4个，第个，第8天为天为10个。个。#include void main()int A,i;A=1;for(i=9;i=1;i-)A=(A+1)*2 pintf(小猴子第一天共摘了小猴子第一天共摘了%d 个桃子个桃子.n，A);31补补1.4 递推算法递推算法o例：猴子分桃例：猴子分桃n1979年李政道去中国科技大学访问，出了一道题目。年李政道去中国科技大学访问，出了一道题目。5只猴子摘了一堆桃子，等第二天再来分。夜里一只猴子只猴子摘了一堆桃子，等第二天再来分。夜里一只猴子偷偷爬起来，吃掉了一只桃子，然后把剩下的桃子分成偷偷爬起来，吃掉了一只桃子，然后把剩下的桃子分成5份，取走了自己应得到的一份，然后回家了。过了会儿，份，取走了自己应得到的一份，然后回家了。过了会儿，第二只猴子也爬了起来，吃掉了一只桃子，然后把剩下第二只猴子也爬了起来，吃掉了一只桃子，然后把剩下的桃子分成的桃子分成5份，取走了自己应得到的一份。第三、四、份，取走了自己应得到的一份。第三、四、五只猴子都是这样，吃掉了一只桃子后，正好把剩下的五只猴子都是这样，吃掉了一只桃子后，正好把剩下的桃子每次都能分成桃子每次都能分成5份。份。n请问最初至少有多少个桃子？每只猴子夜里起床后看到请问最初至少有多少个桃子？每只猴子夜里起床后看到多少只桃子？多少只桃子？32补补1.4 递推算法递推算法o解题思路n定义定义peachi（1i 5）表示第表示第i只猴子看只猴子看到的桃子数。到的桃子数。npeach2=(peach1-1)*4/5npeachi=(peachi-1-1)*4/5（2i 5）n如果知道了如果知道了peach1 或者或者 peach5中的任中的任意一个，都可以递推出来每只猴子看到的桃子意一个，都可以递推出来每只猴子看到的桃子个数。个数。可惜不知道啊。可惜不知道啊。33补补1.4 递推算法递推算法o解题思路n但是我们知道：但是我们知道：npeach1%5=1；npeach2%5=1，并且，并且peach2=(peach1-1)*4/5npeach3、peach4、peach5也如此也如此n可以用枚举法，让可以用枚举法，让peach1=6，来试验是否，来试验是否满足上述条件。然后依次满足上述条件。然后依次peach1累加累加5，直，直到满足上述所有要求。到满足上述所有要求。3414.4 递推算法递推算法#include void main()int i,peach6=0;/peach0不使用，为了计算方便不使用，为了计算方便 peach1=6;while(1)for(i=2;i=5;i+)peachi=(peachi-1-1)*4/5;if(peachi%5!=1)break;if(i=5)peach1+=5;else break;printf(最初至少有最初至少有%d个桃子个桃子n,peach1);for(i=1;i=5;i+)printf(第第%d 只小猴子夜里看到了只小猴子夜里看到了%d 只桃子。只桃子。n,i,peachi);35小结与要求1.1.1.1.深入理解深入理解深入理解深入理解算法是程序设计的灵魂算法是程序设计的灵魂算法是程序设计的灵魂算法是程序设计的灵魂的含义。的含义。的含义。的含义。2.2.2.2.在在在在编编编编写写写写程程程程序序序序解解解解决决决决实实实实际际际际问问问问题题题题之之之之前前前前，必必必必须须须须要要要要有有有有解解解解决决决决问问问问题题题题的的的的思路与想法。对于该思路与想法。对于该思路与想法。对于该思路与想法。对于该方法的基本要求是自己要清楚方法的基本要求是自己要清楚方法的基本要求是自己要清楚方法的基本要求是自己要清楚。3.3.3.3.不不不不同同同同的的的的方方方方法法法法对对对对应应应应于于于于不不不不同同同同的的的的算算算算法法法法，要要要要知知知知道道道道如如如如何何何何评评评评价价价价一一一一个个个个算法优劣算法优劣算法优劣算法优劣。4.4.4.4.常常常常用用用用算算算算法法法法的的的的一一一一些些些些基基基基本本本本思思思思路路路路要要要要掌掌掌掌握握握握：常常常常用用用用的的的的查查查查找找找找算算算算法法法法、排排排排序序序序算算算算法法法法、枚枚枚枚举举举举方方方方法法法法、递递递递推推推推方方方方法法法法要要要要掌掌掌掌握握握握，并并并并会会会会解解解解决决决决一一一一些常见问题。些常见问题。些常见问题。些常见问题。谢谢各位同学！请提宝贵意见。