《数据结构》--算法ppt课件.ppt

《《数据结构》--算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章算法计科系：王丹丹复习1、什么是数据结构？2、本课程主要研究什么？3、什么是数据的逻辑结构和物理结构？4、数据的逻辑结构有哪几种？存储结构有哪两种形式？5、逻辑结构与物理结构间的关系？数据结构主要研究什么？数据结构是一门研究数据的各种逻辑结构和存储结构，以及对数据各种操作的课程。数据的逻辑结构数据的存储结构数据的操作(算法)：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构本章内容2.2数据结构与算法关系2.3两种算法的比较2.4算法定义2.5算法的特性2.6算法设计的要求2.7算法效率的度量2.8函数的渐近增长2.9算

2、法时间复杂度2.10常见的时间复杂度2.11最坏情况和平均情况2.12算法空间复杂度2.1.3总结回顾要能回答的问题1、算法与程序的区别？2、算法的评价标准？3、什么是算法的时间复杂度？4、怎样计算算法的时间复杂度？思考：写一个求1+2+3+……+100结果的程序？2.4算法的定义算法(Algorithm)：对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。程序:计算机能够理解和执行的指令序列。算法与程序的区别和联系算法的执行是有穷的，而一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需

3、要处理，它仍处于动态等待中。因此，操作系统不是一个算法。程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。2.5算法的特性输入输出一个算法应该有零个或多个输入，一个或多个输出。有穷性一个算法必须在执行有穷步之后结束。确定性算法中的每一步必须有确切的含义，无二义性。可行性算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。2.6算法设计的要求评价一个好算法的几个标准正确性(Correctness)：算法应满足具体问题的需求。可读性(Readab

4、ility)：算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。健壮性(Robustness)：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。算法的设计与分析算法的设计1、通过对问题进行详细地分析，抽象出相应的数学模型；2、确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；3、描述算法（C语言中的函数）；4、选用某种语言将算法转换成程序；5、调试并运行

5、这些程序。算法的设计与分析算法的设计算法能用文字、高级语言、伪代码进行描述。案例按学号进行顺序查找NO=20020005的学生。设i=1，比较第i个元素的学号是否等于NO,如果相等，则查找成功，查找过程结束；否则，i++，继续比较。学生信息表中，所有元素的学号都不等于NO，则查找失败。算法设计的要求正确性1可读性健壮性时间效率高和存储量低234时间效率：算法的执行时间。如何度量？思考：算法的优劣？算法效率的度量方法事后统计方法：利用计算机计时器对不同算法编制的程序的运行时间进行比较。事前分析估计方法：计算机程序编制前，依据统计方法对算法进行估算。2.7算法效率的度量方

6、法缺陷事后统计方法花费大量的时间和精力依赖计算机硬件和软件等环境因素算法的测试数据设计困难事先分析估算方法-运行消耗时间算法采用的策略、方法01编译产生的代码质量02机器执行指令的速度04问题的输入规模03因素算法好坏软件支持输入量的多少硬件性能第一种算法第二种算法执行：1+（n+1）+n+1=2n+3次执行：1+1+1=3次例子延伸算法的执行次数：对于同样输入规模，要多于前面两个。算法的执行时间：随着n的增加也将远远多于前两种。测定运行时间最可靠的方法：计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比！启示同样问题，输入规模为n求和算法操作数量第一

7、种F(n)=n第二种F(n)=1第三种F(n)=n*n不同算法的操作数量对比随着n值的越来越大，它们在时间效率上的差异也就越来越大。2.8函数的渐近增长观察数据的特点？判断：算法A和B哪个更好？函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。可以忽略这些加法常数！2.8函数的渐近增长与最高次项相乘的常数并不重要！2.8函数的渐近增长最高次项的指数大的，函数随着n的增长，结果也会变得增长特别快。2.8函数的渐近增长判断一个算法好坏，我们只通过