第一章 算法与程序精选文档.ppt

《第一章 算法与程序精选文档.ppt》由会员分享，可在线阅读，更多相关《第一章 算法与程序精选文档.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 算法与程序5/3/20231本讲稿第一页，共四十六页数据结构课程地位l 数据结构与其它课程关系图：数据结构与其它课程关系图：数据结构数据库数据库人工智能人工智能专业基础课专业基础课操作系统操作系统编译原理编译原理非线性程序设计非线性程序设计离散数学离散数学语言程序设计语言程序设计计算机原理设计计算机原理设计5/3/20232本讲稿第二页，共四十六页数据结构的应用程序=算法+数据结构例：火车进出站问题例：火车进出站问题5/3/20233本讲稿第三页，共四十六页参考书籍数据结构（C语言版）严蔚敏C程序设计（第三版）谭浩强 5/3/20234本讲稿第四页，共四十六页课程安排l本课程理论教学5

2、0学时，实践教学20学时，共70学时,实验为五个实验序号序号实验项目名称实验项目名称实验学时实验学时实验类型实验类型一一线性表及其应用线性表及其应用(多项式相加、相多项式相加、相乘乘)4验证验证二二哈夫曼树及哈夫曼编码译码的实哈夫曼树及哈夫曼编码译码的实现现4验证验证三三Dijkstra最短路径最短路径或或Prim最小生成树最小生成树4验证验证四四实现实现Fibonacci检索算法检索算法4验证验证五五快速、堆、基数排序算法的设计快速、堆、基数排序算法的设计4综合综合5/3/20235本讲稿第五页，共四十六页第一章 算法与程序算法与程序5/3/20236本讲稿第六页，共四十六页第1章 算法与程

3、序l1.11.1 算法的基本概念算法的基本概念l1.2 1.2 算法的表示算法的表示l1.31.3 算法的设计与评价算法的设计与评价l1.41.4 算法与程序算法与程序5/3/20237本讲稿第七页，共四十六页1.1.11.1.1什么是算法什么是算法从欧几里德算法谈起l例：求解两个正整数m和n的最大公因子的欧几里德算法。以n除m，并令所得余数为r（必有rn）。若r为0，输出结果n，算法结束；否则继续步骤。令m=n，n=r，返回步骤，继续进行。思考：最小公倍数该如何计算？思考：最小公倍数该如何计算？5/3/20238本讲稿第八页，共四十六页1.1.11.1.1什么是算法什么是算法算法是求解问题的

4、方法和步骤。算法是求解问题的方法和步骤。这些方法与步骤是机械的，甚至繁琐，工这些方法与步骤是机械的，甚至繁琐，工作量巨大的，定义了这样机械的步骤后，作量巨大的，定义了这样机械的步骤后，就可以交给机器处理就可以交给机器处理比如：圆周率的计算方法与步骤。比如：圆周率的计算方法与步骤。5/3/20239本讲稿第九页，共四十六页1.1.2 1.1.2 算法的基本特性1.输 入：有多个或0个输入 2.输 出：至少有一个或多个输出。3.确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。4.有穷性：有限步骤之内正常结束，不能形成无穷循环5.有效性：即算法的可行性，所描述的操作都是建立在可以通过、已

5、经实现的基本运算的基础上。5/3/202310本讲稿第十页，共四十六页1.2 算法的表示 l1.2.1 自然语言 如：上述中欧几里德算法的3步骤 l 优点：易理解；l 缺点：易产生歧义、描述冗长、不简洁、不直观5/3/202311本讲稿第十一页，共四十六页1.2.2 流程图的表示：表示算法的起止：表示输入输出：表示判断语句：表示处理：如赋值，加减等：表示算法的走向：表示解释5/3/202312本讲稿第十二页，共四十六页1.2.2 流程图的表示 优点：易理解、步骤清晰；缺点：不易表示层次结构、过早考虑流程而忽视数据结构、篇幅大、编辑费时费力 结束开始输入m,nm mod nrr=0?n m,r

6、n输出n5/3/202313本讲稿第十三页，共四十六页1.2.3 N-S图四种基本图形ABPABTF当PA直到P5/3/202314本讲稿第十四页，共四十六页1.2.3 N-S图欧几里德算法的欧几里德算法的N-S图表示图表示输入输入m,nm mod n r输出输出nn m,r nWhile r不等于不等于0 repeatM mod n r5/3/202315本讲稿第十五页，共四十六页1.2.4 伪代码表示lbeginl input m,nl m mod n rl while r0 dol beginl n ml r nl m mod n rl endl output nl end 优点：无须严

7、格的语法、简练；缺点：不直观5/3/202316本讲稿第十六页，共四十六页1.2.5 程序语言表示l#include lvoid main()ll int m,n,r;l coutm;l coutn;l r=m%n;l while(r!=0)l l m=n;n=r;l r=m%n;l l cout”the biggest common factor is”n;l5/3/202317本讲稿第十七页，共四十六页1.3 算法的设计与评价1.3.1 评价算法的标准 正确性：满足具体问题的要求，结果正确，能解决实际问题，经得起一切可能输入的考验；可读性：算法描述可以阅读、理解，便于交流和审核；健壮性（鲁

8、棒性）：能应对异常，控制程序的执行；高效率：既要在尽可能短的时间内执行完成，又要尽可能地节省存储空间。(5)简洁性：所设计出来的算法要尽可能地简洁。5/3/202318本讲稿第十八页，共四十六页1.3.2算法的时间和空间效率 与时间有关l算法执行时间l算法执行时间复杂度l复杂度计算方法常见法则l平均时间复杂度和最坏或最好时间复杂度与空间有关l算法空间复杂度5/3/202319本讲稿第十九页，共四十六页1.3.2算法的时间和空间效率 1.算法执行时间 算法执行时间=每条语句执行次数(频度)这里假设每条语句执这里假设每条语句执行的时间都是单位时行的时间都是单位时间；间；这些语句包括加法语句，这些语

9、句包括加法语句，赋值语句等赋值语句等不是具体的时间，而不是具体的时间，而是所有语句执行次数是所有语句执行次数总和；总和；5/3/202320本讲稿第二十页，共四十六页1.3.3算法的时间和空间效率 例：计算两矩阵相乘所耗费的时间l 1 for（i=1；i=n;i+）l 2 for（j=1；j=n;j+）l 3 cij=0;l 4 for(k=1;k=n;k+)l 5 cij=cij+aik*bkj;l 对应的语句频度对应的语句频度总执行次数为总执行次数为n的函数：的函数：T(n)=2n3+3n2+n+1n+1n(n+1)n2n2(n+1)n35/3/202321本讲稿第二十一页，共四十六页1.

10、3.2算法的时间和空间效率 2.算法的时间复杂度l思考：当当n时，时，T(n)=2n3+3n2+n+1与哪部分有与哪部分有关？关？l当当n时，时，lim T(n)/n3=2 l可知可知T(n)与与n3是同阶函数，即具有相同的增长率是同阶函数，即具有相同的增长率 l 我们引入大我们引入大O符号表示算法的时间复杂度，即表示算符号表示算法的时间复杂度，即表示算法的增长率，记作：法的增长率，记作：T(n)=O(n3)5/3/202322本讲稿第二十二页，共四十六页1.3.2算法的时间和空间效率 如何计算算法的时间复杂度？l原则：无需考虑全部运算时间，仅考虑执行次数最多的语句，一般是循环的最内层语句 1

11、for（i=0；i n;i+）2 for（j=0；jn;j+）3 cij=0;4 for(k=0;k n;k+)5 cij=cij+aik*bkj;5/3/202323本讲稿第二十三页，共四十六页1.3.3算法的时间和空间效率 例：计算以下语句的时间复杂度1.for(i=1;i=n;i+)2.for(j=1;j=i;j+)3.for(k=1;k=j;k+)4.x=x+1;jT(n)=O(n3)5/3/202324本讲稿第二十四页，共四十六页1.3.3 算法的时空效率3.算法时间复杂度的常见运算法则：算法时间复杂度的常见运算法则：l执行一条基本语句用执行一条基本语句用O(1)时间时间l顺序结构，

12、用求和准则估计顺序结构，用求和准则估计l选择结构，检验语句需要用选择结构，检验语句需要用O(1)时间时间,主主要耗费时间是要耗费时间是if从句或从句或else从句后的语句从句后的语句l循环结构常按乘法法则估计循环结构常按乘法法则估计,即即O(n)5/3/202325本讲稿第二十五页，共四十六页1.3.3 算法的时空效率3.算法时间复杂度的常见运算法则：算法时间复杂度的常见运算法则：l 常数法则一：常数法则一：T(n)=O(f(n)+C)=O(f(n)其中其中C为常数为常数l 常数法则二：常数法则二：T(n)=O(C*f(n)=O(f(n)l 求和法则一：若求和法则一：若T1(n)=O(f(n)

13、，T2(n)=O(g(n)，则则T1(n)+T2(n)=O(max(f(n),g(n)l 求和法则二：若求和法则二：若T1(m)=O(f(m)，T2(n)=O(g(n)，则则T1(m)+T2(n)=O(f(m)+g(n)l 乘法法则：若乘法法则：若T1(n)=O(f(n)，T2(n)=O(g(n)，则则T1(n)T2(n)=O(f(n)g(n)l(6)乘法法则：若乘法法则：若T1(m)=O(f(m)，T2(n)=O(g(n)，则则T1(n)T2(n)=O(f(m)g(n)5/3/202326本讲稿第二十六页，共四十六页1.3.3 算法的时空效率3.算法时间复杂度的常见运算法则例1：用法则计算两

14、矩阵相乘所耗费的时间 1for（i=1；i=n;i+）2 for（j=1；j=n;j+）3 cij=0;4 for(k=1;k=n;k+)5 cij=cij+aik*bkj;5/3/202327本讲稿第二十七页，共四十六页1.3.2算法的时间和空间效率 例2：计算以下语句的时间复杂度1.i=1;j=0;2.while(i+j)j)j+;4.else i+5/3/202328本讲稿第二十八页，共四十六页1.3.2算法的时间和空间效率例3:计算以下语句的时间复杂度 i=0;s=0;while(s2)项问题。F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)5/3/202335本讲稿第

15、三十五页，共四十六页1.3.4常见的算法设计方法4.递归法 递归过程：一个过程直接或间接地调用其自身。其算法的效率一般较低，只有不得已时才采用递归法。例：求N的阶层函数5/3/202336本讲稿第三十六页，共四十六页1.3.4常见的算法设计方法5.回溯法 通过对问题的分析找出一个解决问题的线索，沿着这个线索逐步试探，试探若成功就继续下一步试探，若不成功就回溯到前面步骤并更换线路再试探，直至搜索到问题的最终解。如：求解“迷宫问题”。5/3/202337本讲稿第三十七页，共四十六页1.3.4常见的算法设计方法6.贪婪法（贪心法）它通过一系列的选择来得到问题的一个解，它在每一步所作出的选择，都是在当

16、前状态下看来是最好的选择，并希望通过每次所做的贪婪选择导致最终结果是求解问题的一个最优解。如：最小生成树问题，最短路径问题的求解。5/3/202338本讲稿第三十八页，共四十六页1.3.4常见的算法设计方法7.分治法将规模较大的复杂问题分解成若干规模小的子问题，在找出各个子问题的解后再组合成整个问题的解。如：二分检索、快速排序等算法。5/3/202339本讲稿第三十九页，共四十六页1.4 算法与程序1.4.1 程序的概念特征如下：（1）描述某一问题的任务和功能（2）遵循一定的语法规则和算法的执行步骤（3）计算机上执行（4）由人编写（5）自动运行（6）程序是算法的程序设计语言的描述5/3/202

17、340本讲稿第四十页，共四十六页1.4.2 问题求解与实现策略问题求解的一般过程：（1）明确问题要求（2）建立数学模型（3）设计算法（4）编写程序（5）调试程序（6）运行与结果分析（7）编写程序文档5/3/202341本讲稿第四十一页，共四十六页1.4.3 调试和查错策略错误类型：a）语法错误（Syntax Error）-编译器自动查错和报告 b）运行时期错误（Run-Time Error）c）逻辑错误（Logic Error）推断错误的策略：（1）试探法 （2）回溯法 （3）二分查找 （4）归纳法 （5）演绎法5/3/202342本讲稿第四十二页，共四十六页1.4.3 调试和查错策略软件测试

18、的方法：（1）逻辑覆盖 （2）等价类划分 （3）边界值分析 （4）图形技术5/3/202343本讲稿第四十三页，共四十六页1.4.4 程序设计方法概述1.结构化程序设计2.面向对象程序设计3.可视化程序设计4.分布式程序设计 5.并行程序设计 5/3/202344本讲稿第四十四页，共四十六页小结本章学习了以下几个内容l算法的基本概念算法的基本概念l算法的表示算法的表示l算法的设计与评价算法的设计与评价（算法复杂度的计算）（算法复杂度的计算）l常见算法的介绍常见算法的介绍5/3/202345本讲稿第四十五页，共四十六页作业题目：设计n个数的排序算法，并且要求计算算法时间复杂度。（要求n个数的排序写成函数形式，在main()中调用）5/3/202346本讲稿第四十六页，共四十六页