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

文档介绍：第2章算法
计科系:王丹丹
复习
1、什么是数据结构?
2、本课程主要研究什么?
3、什么是数据的逻辑结构和物理结构?
4、数据的逻辑结构有哪几种?存储结构有哪两种形式?
5、逻辑结构与物理结构间的关系?
数据结构主要研究什么?
数据结构是一门研究数据的各种逻辑结构和存储结构,以及对数据各种操作的课程。
数据的逻辑结构
数据的存储结构
数据的操作(算法):检索、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队
树形结构
图形结构
本章内容
数据结构与算法关系
两种算法的比较
算法定义
算法的特性
算法设计的要求

函数的渐近增长
算法时间复杂度
常见的时间复杂度
最坏情况和平均情况
算法空间复杂度
总结回顾
要能回答的问题
1、算法与程序的区别?
2、算法的评价标准?
3、什么是算法的时间复杂度?
4、怎样计算算法的时间复杂度?
思考:写一个求1+2+3+……+100结果的程序?
算法的定义
算法(Algorithm):对特定问题求解方法(步骤)的一种描述,是指令的有限序列,其中每一条指令表示一个或多个操作。
程序:计算机能够理解和执行的指令序列。
算法与程序的区别和联系
算法的执行是有穷的,而一个程序不一定满足有穷性。例操作系统,只要整个系统不遭破坏,它将永远不会停止,即使没有作业需要处理,它仍处于动态等待中。因此,操作系统不是一个算法。
程序中的指令必须是机器可执行的,而算法中的指令则无此限制。
算法代表了对问题的解,而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述,则它就是一个程序。
算法的特性
输入输出
一个算法应该有零个或多个输入,一个或多个输出。
有穷性
一个算法必须在执行有穷步之后结束。
确定性
算法中的每一步必须有确切的含义,无二义性。
可行性
算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。
算法设计的要求
评价一个好算法的几个标准
正确性(Correctness ): 算法应满足具体问题的需求。
可读性(Readability): 算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。
健壮性(Robustness): 算法应具有容错处理。当输入非法或错误数据时,算法应能适当地作出反应或进行处理,而不会产生莫名其妙的输出结果。
效率与存储量需求: 效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般地,这两者与问题的规模有关。