第一章 算法与程序

第一章算法与程序5/2/20231第1页，共46页，2023年，2月20日，星期三数据结构课程地位

数据结构与其它课程关系图：数据结构数据库人工智能专业基础课操作系统编译原理非线性程序设计离散数学语言程序设计计算机原理设计5/2/20232第2页，共46页，2023年，2月20日，星期三数据结构的应用程序=算法+数据结构例：火车进出站问题5/2/20233第3页，共46页，2023年，2月20日，星期三参考书籍《数据结构（C语言版）》严蔚敏《C程序设计（第三版）》谭浩强5/2/20234第4页，共46页，2023年，2月20日，星期三课程安排本课程理论教学50学时，实践教学20学时，共70学时,实验为五个实验序号实验项目名称实验学时实验类型一线性表及其应用(多项式相加、相乘)4验证二哈夫曼树及哈夫曼编码译码的实现4验证三Dijkstra最短路径或Prim最小生成树4验证四实现Fibonacci检索算法4验证五快速、堆、基数排序算法的设计4综合5/2/20235第5页，共46页，2023年，2月20日，星期三第一章算法与程序5/2/20236第6页，共46页，2023年，2月20日，星期三第1章算法与程序1.1

算法的基本概念1.2算法的表示1.3

算法的设计与评价1.4

算法与程序5/2/20237第7页，共46页，2023年，2月20日，星期三1.1.1什么是算法——从欧几里德算法谈起例：求解两个正整数m和n的最大公因子的欧几里德算法。①以n除m，并令所得余数为r（必有r<n）。②若r为0，输出结果n，算法结束；否则继续步骤③。③令m=n，n=r，返回步骤①，继续进行。

思考：最小公倍数该如何计算？5/2/20238第8页，共46页，2023年，2月20日，星期三1.1.1什么是算法算法是求解问题的方法和步骤。这些方法与步骤是机械的，甚至繁琐，工作量巨大的，定义了这样机械的步骤后，就可以交给机器处理比如：圆周率的计算方法与步骤。5/2/20239第9页，共46页，2023年，2月20日，星期三1.1.2算法的基本特性输入：有多个或0个输入输出：至少有一个或多个输出。确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。有穷性：有限步骤之内正常结束，不能形成无穷循环有效性：即算法的可行性，所描述的操作都是建立在可以通过、已经实现的基本运算的基础上。5/2/202310第10页，共46页，2023年，2月20日，星期三1.2算法的表示1.2.1自然语言如：上述中欧几里德算法的3步骤

优点：易理解；缺点：易产生歧义、描述冗长、不简洁、不直观5/2/202311第11页，共46页，2023年，2月20日，星期三1.2.2流程图的表示：表示算法的起止：表示输入输出：表示判断语句：表示处理：如赋值，加减等：表示算法的走向：表示解释5/2/202312第12页，共46页，2023年，2月20日，星期三1.2.2流程图的表示

优点：易理解、步骤清晰；缺点：不易表示层次结构、过早考虑流程而忽视数据结构、篇幅大、编辑费时费力结束开始输入m,nmmodn→rr=0?n→m,r→n输出n5/2/202313第13页，共46页，2023年，2月20日，星期三1.2.3N-S图四种基本图形ABPABTF当PA直到P5/2/202314第14页，共46页，2023年，2月20日，星期三1.2.3N-S图欧几里德算法的N-S图表示输入m,nmmodnr输出nnm,rnWhiler不等于0repeatMmodnr5/2/202315第15页，共46页，2023年，2月20日，星期三1.2.4伪代码表示begininputm,nmmodn→rwhiler≠0dobeginn→mr→nmmodn→rendoutputnend

优点：无须严格的语法、简练；缺点：不直观5/2/202316第16页，共46页，2023年，2月20日，星期三1.2.5程序语言表示#include<iostream>voidmain(){intm,n,r;cout<<”inputm:”;cin>>m;cout<<”inputn:”;cin>>n;r=m%n;while(r!=0){m=n;n=r;r=m%n;}cout<<”thebiggestcommonfactoris”<<n;}5/2/202317第17页，共46页，2023年，2月20日，星期三1.3算法的设计与评价1.3.1评价算法的标准⑴正确性：满足具体问题的要求，结果正确，能解决实际问题，经得起一切可能输入的考验；⑵可读性：算法描述可以阅读、理解，便于交流和审核；⑶健壮性（鲁棒性）：能应对异常，控制程序的执行；⑷高效率：既要在尽可能短的时间内执行完成，又要尽可能地节省存储空间。(5)简洁性：所设计出来的算法要尽可能地简洁。5/2/202318第18页，共46页，2023年，2月20日，星期三1.3.2算法的时间和空间效率与时间有关算法执行时间算法执行时间复杂度复杂度计算方法常见法则平均时间复杂度和最坏或最好时间复杂度与空间有关算法空间复杂度5/2/202319第19页，共46页，2023年，2月20日，星期三1.3.2算法的时间和空间效率1.算法执行时间算法执行时间=

每条语句×执行次数(频度)

这里假设每条语句执行的时间都是单位时间；这些语句包括加法语句，赋值语句等不是具体的时间，而是所有语句执行次数总和；5/2/202320第20页，共46页，2023年，2月20日，星期三1.3.3算法的时间和空间效率例：计算两矩阵相乘所耗费的时间

1 for（i=1；i<=n;i++）

2 for（j=1；j<=n;j++）

3{c[i][j]=0;4for(k=1;k<=n;k++)5c[i][j]=c[i][j]+a[i][k]*b[k][j];}

对应的语句频度总执行次数为n的函数：T(n)=2n3+3n2+n+1n+1n(n+1)n2n2(n+1)n35/2/202321第21页，共46页，2023年，2月20日，星期三1.3.2算法的时间和空间效率2.算法的时间复杂度思考：当n→∞时，T(n)=2n3+3n2+n+1与哪部分有关？当n→∞时，limT(n)/n3=2可知T(n)与n3是同阶函数，即具有相同的增长率我们引入大O符号表示算法的时间复杂度，即表示算法的增长率，记作：

T(n)=O(n3)5/2/202322第22页，共46页，2023年，2月20日，星期三1.3.2算法的时间和空间效率如何计算算法的时间复杂度？原则：无需考虑全部运算时间，仅考虑执行次数最多的语句，一般是循环的最内层语句1 for（i=0；i<n;i++）

2 for（j=0；j<n;j++）

3{c[i][j]=0;4for(k=0;k<n;k++)5c[i][j]=c[i][j]+a[i][k]*b[k][j];}5/2/202323第23页，共46页，2023年，2月20日，星期三1.3.3算法的时间和空间效率例：计算以下语句的时间复杂度1.for(i=1;i<=n;i++)for(j=1;j<=i;j++)3.for(k=1;k<=j;k++)4.x=x+1;jT(n)=O(n3)5/2/202324第24页，共46页，2023年，2月20日，星期三1.3.3算法的时空效率3.算法时间复杂度的常见运算法则：执行一条基本语句用O(1)时间顺序结构，用求和准则估计选择结构，检验语句需要用O(1)时间,主要耗费时间是if从句或else从句后的语句循环结构常按乘法法则估计,即O(n)5/2/202325第25页，共46页，2023年，2月20日，星期三1.3.3算法的时空效率3.算法时间复杂度的常见运算法则：⑴常数法则一：T(n)=O(f(n)+C)=O(f(n))其中C为常数⑵常数法则二：T(n)=O(C*f(n))=O(f(n))⑶求和法则一：若T1(n)=O(f(n))，T2(n)=O(g(n))，则T1(n)+T2(n)=O(max(f(n),g(n)))⑷求和法则二：若T1(m)=O(f(m))，T2(n)=O(g(n))，则T1(m)+T2(n)=O(f(m)+g(n))⑸乘法法则：若T1(n)=O(f(n))，T2(n)=O(g(n))，则T1(n)×T2(n)=O((f(n)×g(n))(6)乘法法则：若T1(m)=O(f(m))，T2(n)=O(g(n))，则T1(n)×T2(n)=O((f(m)×g(n))5/2/202326第26页，共46页，2023年，2月20日，星期三1.3.3算法的时空效率3.算法时间复杂度的常见运算法则例1：用法则计算两矩阵相乘所耗费的时间

1 for（i=1；i<=n;i++）

2 for（j=1；j<=n;j++）

3{c[i][j]=0;4for(k=1;k<=n;k++)5c[i][j]=c[i][j]+a[i][k]*b[k][j];}

5/2/202327第27页，共46页，2023年，2月20日，星期三1.3.2算法的时间和空间效率例2：计算以下语句的时间复杂度1.i=1;j=0;2.while((i+j)<=n)3.if(i>j)j++;4.elsei++5/2/202328第28页，共46页，2023年，2月20日，星期三1.3.2算法的时间和空间效率例3:计算以下语句的时间复杂度

i=0;s=0;while(s<n){i++;s=s+i;}5/2/202329第29页，共46页，2023年，2月20日，星期三1.3.2算法的时空效率4.平均时间复杂度和最坏时间复杂度算法运行的时间与待处理的数据有关可以选用平均，最好，最坏的时间复杂度来衡量例如直接插入排序，冒泡排序等5/2/202330第30页，共46页，2023年，2月20日，星期三1.3.3算法的时空效率5.常用的时间复杂度O(1)常数型O(n)线性型O(n2)平方型O(n3)立方型O(2n)指数型O(log2n)对数型O(nlog2n)二维型5/2/202331第31页，共46页，2023年，2月20日，星期三常用的时间复杂度频率计数5.常用的时间复杂度log2nnnlog2nn2n32n一般讲：前3种可实现，后3种虽理论上是可实现的，实际上只有对N限制在很小范围才有意义，当N较大时，不可能实现。

0101121224842481664163824645122564166425650966553653216010243276821474836485/2/202332第32页，共46页，2023年，2月20日，星期三1.3.3算法的时空效率6.空间效率程序本身占用的存储空间算法或程序中输入和输出数据所占用的空间执行过程中临时占用的存储空间度量一个算法执行过程中的额外花销也可以用大O方法，成为算法的空间复杂度5/2/202333第33页，共46页，2023年，2月20日，星期三1.3.4常见的算法设计方法1.穷举法（枚举法）根据问题给定的条件，确定解的可能取值区间，然后对整个区间上的所有可能的解进行逐一的验证。2.迭代法迭代法的基本思想是，由一个量的原值求出它的新值，不断地再用新值替代原值求出它的下一个新值，直到得到满意的解。如：计算S=1+2+3+…+1000S=S+i5/2/202334第34页，共46页，2023年，2月20日，星期三1.3.4常见的算法设计方法3.递推法从已知的条件出发，逐次推算出中间结果，有中间结果继续向后推算，直至最终结果。

如：求菲波那契数列的第n(假设n>2)项问题。

F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)5/2/202335第35页，共46页，2023年，2月20日，星期三1.3.4常见的算法设计方法4.递归法递归过程：一个过程直接或间接地调用其自身。其算法的效率一般较低，只有不得已时才采用递归法。例：求N的阶层函数5/2/202336第36页，共46页，2023年，2月20日，星期三1.3.4常见的算法设计方法5.回溯法通过对问题的分析找出一个解决问题的线索，沿着这个线索逐步试探，试探若成功就继续下一步试探，若不成功就回溯到前面步骤并更换线路再试探，直至搜索到问题的最终解。如：求解“迷宫问题”。5/2/202337第37页，共46页，2023年，2月20日，星期三1.3.4常见的算法设计方法6.贪婪法（贪心法）它通过一系列的选择来得到问题的一个解，它在每一步所作出的选择，都是在当前状态下看来是最好的选择，并希望通过每次所做的贪婪选择导致最终结果是求解问题的一个最优解。如：最小生成树问题，最短路径问题的求解。5/2/202338第38页，共46页，2023年，2月20日，星期三1.3.4常见的算法设计方法7.分治法将规模较大的复杂问题分解成若干规模小的子问题，在找出各个子问题的解后再组合成整个问题的解。如：二分检索、快速排序等算法。5/2/202339第39页，共46页，2023年，2月20日，星期三1.4算法与程序1.4.1程序的概念特征如下：（1）描述某一问题的任务和功能（2）遵循一定的语法规则和算法的执行步骤（3）计算机上执行（4）由人编写（5）自动运行（6）程序是算法的程序设计语言的描述5/2/202340第40页，共46页，2023年，2月20日，星期三1.4.2问题求解与实现策略问题求解的一般过程：（