数据结构课件 第二章 算法分析.ppt

文档介绍：第二章算法分析
什么是算法分析
算法运行时间举例
最大连续子序列之和问题
静态搜索问题
检验一个算法分析
BIG-Oh分析法的限制
评价算法标准:
执行算法所耗费的时间,即效率问题
执行算法所耗费的存储空间,主要考虑辅助的存储空间
算法应易于理解,具有可读性,易于编码,易于调试等
健壮性,即当输入一些非法数据时,算法也应做出适当的反映或进行处理
什么是算法分析
算法所花费的运行时间取决于它所处理的数据输入量
算法的运行时间是数据输入量的一个函数
例:从网络上下载一个文件,假如有一个两秒的最初延时(用以建立连接),,如果文件有几千个字节,下载时间可用公式T(N)= N/+2表示
,这些曲线代表了在算法分析中遇到的四个函数:线性函数、O(NlogN)、二次方函数、立方函数,输入规模N从1至100,运行时间为0至10毫秒

中等规模输入时的运行时间
。
算法运行时间举例
本节讲解事例:
数组中的最小元素
平面中距离最近的两点
最小元素问题
解决方案
定义一个变量min存储最小元素
初始化min为第一个元素
顺序扫描整个数组,将min更改为合适的元素
算法运行时间为O(N)
返回
寻找距离最近点问题
解决方案:
计算每对点间的距离
保留最短距离
运行时间:计算比较花费时间,存在N(N-1)/2对点,大约为对点
最大连续子序列之和问题
给出N个整数(可为负)A1,A2…..An,找出的最大值(与队列次序相同),如果所有整数为负,最大值为0
解决方案:
简单易懂的O(N3)算法
改进的O(N2)算法
线性算法