算法及其复杂性分析.ppt

算法设计与分析实用教程,杨克昌 严权锋,请用PowerPoint 2003播放,中国水利水电出版社,课堂讲授：,学时安排：36（讲授）18（上机）(可根据实际教学计划进行调整；第9 章不讲授，作为“算法设计与分析课程设计”题材选用),算法设计在案例求解中的地位与应用。算法时间复杂度分析方法与算法优劣评价。重点讲授应用算法设计求解典型案例，并进行复杂性分析，引导设计变通。小组讨论与基本案例相关的拓展与引申案例求解，为“课程设计”作准备。,上机实践：,学习建议：,学会归纳、总结和提炼；,自觉调整学习状态：,培养算法设计与分析的兴趣自觉完成布置的作业加深对算法应用的理解善于变通、拓展与改进,注重算法设计，提高解决实际案例的能力。,上机环境：VC+6.0上机通过每章指定的案例求解与习题按要求填写实验报告,教学要求了解算法概念、算法特征及算法的描述建立算法的复杂性概念掌握结构化设计的基本方法本章重点应用 c 语言描述算法掌握常用算法时间复杂度分析,算法及其复杂必分析,1.1 算法及其描述,算法是程序设计的基础，是计算机科学的核心。1.1.1 算法定义 算法是计算机解决问题的过程，是解决某一问题的运算序列。或者说算法是问题求解过程的运算描述。当面临某一问题时，算法就是解决这个问题的方法与步骤的描述。,1.算法的三要素,算法由操作、控制结构与数据结构三者组成。(1)操作：算术运算，关系运算，逻辑运算；输入、输出、赋值等操作。(2)控制结构：顺序结构，选择结构，循环结构，模块调用。(3)数据结构：数据之间的逻辑关系，如数组、堆栈、队列、链表、树、图、堆、散列等。,2.算法的基本特征,一个算法由有限条可完全机械地执行的、有确定结果的指令组成，具有以下特性：(1)确定性(2)可行性(3)有穷性(4)算法有零个或多个输入(5)算法有一个或多个输出,1.1.2 算法描述,（1）一个问题可以设计不同的算法来求解；同一个算法可以采用不同的形式来描述。（2）描述算法可以有：自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。（3）当一个算法使用计算机程序设计语言描述时，就是程序。本书采用C语言与自然语言相结合来描述算法。,例1-1 求两个整数最大公约数的欧几里德算法,(1)数 a 除以 b 得余数 r；若r=0，则b为所求的最大公约数。(2)若 r0，以b为a，r为b，继续(1).描述如下：scanf(%ld,%ld,/输出结果,1.2 算法的复杂性分析,算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。最重要的计算机资源是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。时间复杂度与空间复杂度集中反映算法的效率。,1.2.1 时间复杂度,对算法时间复杂度的分析，通常利用实验对比方法、数学方法来分析算法。实验对比分析很简单，两个算法相互比较求解时间。数学方法能在严密的逻辑推理基础上判断算法的优劣。在算法分析中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。,一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总语句（运算）的数量级决定。,一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。在分析算法时，隐藏细节的数学表示方法为大写字母“O”记法，它可以帮助我们简化算法复杂度计算的许多细节，提取主要成分。,http:/,算法的执行频数的数量级直接决定算法的时间复杂度。,2个语句各执行1次，共执行2次。时间复杂度为O(1),(1)x=x+1;s=s+x;,例1-3 试计算下面三个程序段的时间复杂度,(2)for(k=1;k=n;k+)x=x+y;y=x+y;s=x+y;,“k=1”执行1次；“k=n”与“k+”各执行n次；3个赋值语句，每个赋值语句各执行n次；共执行5n+1次.时间复杂度为O(n).,例1-3 试计算下面三个程序段的执行频数,(3)for(t=1,k=1;k=n;k+)t=t*2;for(j=1;j=t;j+)s=s+j;,“t=1”与“k=1”各执行1次；“k=n”与“k+”各执行n次；“t=t*2”执行n次；“j=1”执行n次；“j=t”、“j+”与内循环的赋值语句“s=s+j”各执行频数为:总的执行频数为：,http:/,时间复杂度符号O的两个定理:,在估算算法的时间复杂度时，为简单计，以后只考虑内循环语句的执行频数，而不细致计算各循环设计语句及其它语句的执行次数，这样简化处理不影响算法的时间复杂度。,例1-4 估算以下程序段所代表算法的时间复杂度。for(k=1;k=n;k+)for(j=1;j=k;j+)x=k+j;s=s+x;,每个赋值语句执行频率为n(n+1)/2,该算法的时间复杂度为:O(n2),一个算法的运行时间，与问题的规模相关，也与输入的数据相关。,例如对给定的n个整数a(1),a(2),a(n)排序：for(i=1;iaj)h=ai;ai=aj;aj=h;,3个赋值语句的执行频数之和，最理想的情形下为零（当所有n个整数已从小到大排列时），最坏情形下为3n(n1)/2（当n个整数为从大到小排列时）。按平均情形来分析，其时间复杂度为O(n2)。,对于一个实用算法，我们通常不必深入研究它时间复杂度的上界和下界，只需要了解该算法的特性，然后在合适的时候应用它。,为了求解某一问题，设计出复杂性尽可能低的算法是追求的重要目标。或者说，求解某一问题有多种算法时，选择其中复杂性最低的算法是选用算法的重要准则。,对算法的改进与优化，主要表现在有效缩减算法的运行时间与所占空间。,http:/,1.2.2 空间复杂度,一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。固定空间需求包括程序代码、常量与静态变量等所占的空间。可变空间需求包括局部作用域非静态变量所占用的空间、从堆空间中动态分配的空间与调用函数所需的系统栈空间等。,算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。,二维或三维数组是空间复杂度高的主要因素之一。在算法设计时，为降低空间复杂度，要注意尽可能少用高维数组。,从应用的角度看，因空间所限影响算法运行的情形较为少见。因而在设计算法时，应把降低算法的时间复杂度作为首要的考虑因素。,在论述某一算法时，如果其空间复杂度不高，不至于因所占有的内存空间而影响算法实现时，通常不涉及对该算法的空间复杂度的讨论。,1.3 算法设计与分析实例,1.欧几里德算法的时间复杂度估算，设每次辗转相除的余数减半，开始时输入数a,b的最小值为n=2t，则有即得欧几里德算法的时间复杂度为O(logn)。,1.3.1 求解最大公约数,2.应用最大公约数的定义求解 设置c枚举循环，c从b开始递减取值至1，若c同时是a、b的约数(即满足a%c=0 and b%c=0，最先出现的显然为最大公约数），则输出最大公约数(a,b)的结果。,scanf(%ld,%ld,/输出结果。,设输入数a,b的最小值为n，以上按最大公约数定义的枚举的平均频数或为n/2,或为n/3，其时间复杂度为O(n)。3 复杂度比较 两个算法相比，显然欧几里德算法的时间复杂度较低，即其求解效率较高。,注意：求解一个实际案例，算法可能有多种多样，我们不必局限于某一个或某一种模式，可选择一些自己所熟悉的算法进行设计。当面临的数据量规模很大时，选择时间复杂度低的算法是必要的。,1.当n规模较小(n13)时 scanf(%d,/输出n!单循环设计，时间复杂度为O(n)，空间复杂度为O(1)。,1.3.2 计算n!试精确计算n!=123n，这里正整数n从键盘输入。,2.当n规模较大时 n规模较大，n!的位数也就相应地大，设计a数组存储n!的各位数字，a1存储个位数字，a2存储十位数字，余类推。,通过常用对数累加和s=lg2+lg3+lgn确定n!的位数m=s+1,即a数组元素的个数。设置2重循环，模拟整数竖式乘法实施各数组元素的累乘：乘数k：k=2,3,n；累乘积各位aj：j=1,2,m；实施乘运算：t=aj*k+g;/第j位乘k，g为进位数 aj=t%10;/乘积t的个位数字存于本元素 g=t/10;/乘积t的十位以上数字作为进位数输出：从高位am开始，逐位输出，至a1结束。,scanf(%d,/输出n!的各位数,http:/,当n规模较大时的双循环设计，时间复杂度为O(mn)，空间复杂度为O(m)。显然mn，把m换算为n，注意到m数量级平均为n*lgn，因而时间复杂度为O(n2logn)，空间复杂度为O(nlogn)。,注意：同样是精确求解n的阶乘n!，求解范围的差异导致了算法设计及其复杂性的不同。大规模n情形下精确求解，算法的时间复杂度与空间复杂度都要高于小规模情形的算法。或者说，扩大n!精确求解的范围，是以提高算法的时间复杂度与空间复杂度为代价的。,1.4 算法与程序设计,计算机的一切操作都是由程序控制的，离开了程序，计算机将一事无成。从这个意义来说，计算机的本质是程序的机器，程序是计算机的灵魂。,而算法是程序的核心。程序是某一算法用计算机程序设计语言的具体实现。,1.4.1 算法与程序,程序设计反映了利用计算机解决问题的全过程，包括:建立数学模型;数据的组织方式;设计合适的算法;编写程序来实现算法;上机调试程序，使之运行后能产生求解问题的结果。,一个程序应包括对数据的描述与对运算操作的描述两个方面的内容。数据结构+算法=程序,数据结构是对数据的描述;算法是对运算操作的描述。,1.4.2 结构化程序设计,任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。所以，顺序结构、选择结构和循环结构被称为程序设计的三种基本结构，也是结构化程序设计必须采用的结构。,结构化程序设计方法是目前国内外普遍采用的一种程序设计方法。结构化程序设计方法在实践中不断发展和完善，已成为软件开发的重要方法讨论。,结构化程序设计的基本要点:,（1）自顶向下，逐步求精（2）模块化设计（3）结构化编码,逐步求精总是和自顶向下结合使用，将问题求解逐步具体化的过程，一般把逐步求精看作自顶向下设计的具体体现。,模块化是结构化程序设计的重要原则。一个程序是由一个主控模块和若干子模块组成。主控模块用来完成某些公用操作及功能选择;而子模块用来完成某项特定的功能。,例1-9 把欧几里德算法设计成子模块，通过主模块调用实现求n个整数的最大公约数。,/实现欧几里德算法的函数gcd(a,b),/求n个整数的最大公约数,n-1次调用gcd(a,b),第1章作业,习题1:1,3,4,6,第1章上机(VC+6.0),上机通过1.3.1,1.3.2；上机通过习题 1-7:输出n=15,n=21的对称方阵;上机通过 1.3.3，输出能被2011、2017整除的n.小组讨论：1.3三例算法的时间复杂度。,参见附录A 在VC+6.0环境下运行C程序方法简介,欢迎大家提出教学建议,返回,