数据结构概述课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构概述课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 概述 课件
- 资源描述:
-
1、数据结构与算法基础数据结构与算法基础 第三部分第三部分:算法及效率度量:算法及效率度量n算法、算法的特性算法、算法的特性n算法好坏的评价标准算法好坏的评价标准n算法的性能度量方法算法的性能度量方法n渐进时间复杂度渐进时间复杂度n渐进空间复杂度渐进空间复杂度主要内容算法算法算法的特性算法的特性算法的分类算法的分类 void selectSort(int a,const int n)/对对n个整数个整数a0,a1,an-1,按非递减顺序排序按非递减顺序排序 for(int i=0;i n-1;i+)int k=i;/从从ai检查到检查到an-1,找最小的整数找最小的整数,在在ak for(int
2、j=i+1;j n;j+)if(aj ak)k=j;/k指示当前找到的最小整数指示当前找到的最小整数 int temp=ai;ai=ak;ak=temp;/交换交换ai与与ak 第一个层次第一个层次程序不包含语法错误程序不包含语法错误第二个层次第二个层次输入输入100 输出输出1输入输入0 输出输出0输入输入100 输出输出1第三个层次第三个层次输入输入100 输出输出1输入输入1 输出输出1输入输入0 输出输出0输入输入-1 输出输出-1输入输入-100 输出输出-1第四个层次第四个层次所有可能的输入所有可能的输入算法效率的度量算法效率的度量n实验的方法实验的方法:采用实际数据测试程序的执行
3、时间;:采用实际数据测试程序的执行时间;n仿真的方法仿真的方法:模拟数据进行测试;:模拟数据进行测试;n在算法中的某些部位插装时间函数在算法中的某些部位插装时间函数 time()或者或者clock()测定算法完成某一功能所花费的时间。测定算法完成某一功能所花费的时间。n采用开发工具提供的时间测量工具采用开发工具提供的时间测量工具profile算法的后期测试算法的后期测试 void TimeSearch()/在在0.1000中搜索中搜索0,10,90,100,200,1000 int a1001,n20;for(int j=0;j=1000;j+)aj=j;/a1=1,a2=2,for(j=0;
4、j 10;j+)nj=10*j;/n0=0,n1=10,n2=20 nj+10=100*(j+1);/n10=100,n11=200,n12=300.printf(%12s%12s%12sn,n,500000,1);希望软件执行时间可预测希望软件执行时间可预测 算法分析算法分析感兴趣的不是具体的资源占用量,而是与具体感兴趣的不是具体的资源占用量,而是与具体的平台无关、具体的输入实例无关,且随着规模增长的的平台无关、具体的输入实例无关,且随着规模增长的值是可预测的。值是可预测的。希望了解软件执行时间的变化趋势希望了解软件执行时间的变化趋势 与问题与问题规模之间的关系,用一定的规模数据作为输入时规
5、模之间的关系,用一定的规模数据作为输入时程序所需的基本操作的次数来描述时间效率程序所需的基本操作的次数来描述时间效率 忽略细节忽略细节 完成完成一个基本操作所需要的时间应该与具体的被操作数一个基本操作所需要的时间应该与具体的被操作数无关无关 算法的复杂性分析算法的复杂性分析 float sum(float a,const int n)1 2 float s=0.0;3 for(int i=0;i n;i+)4 s+=ai;5 return s;6 程序的精确步数没有实际意义,程序步数的数量级别可以程序的精确步数没有实际意义,程序步数的数量级别可以反映程序的实质。反映程序的实质。n:一个特定算法
6、的一个特定算法的“运行工作量运行工作量”的大小,只依赖于问题的大小,只依赖于问题的规模(通常用整数量的规模(通常用整数量n表示)表示)f(n):算法中基本操作的执行次数,即它是问题规模的函数。算法中基本操作的执行次数,即它是问题规模的函数。算法的渐进时间复杂度,简称算法时间复杂度记作算法的渐进时间复杂度,简称算法时间复杂度记作:T(n)=O(f(n)表示随问题规模表示随问题规模n的增大,算法执行时间的增长率与的增大,算法执行时间的增长率与f(n)的的增长率相同。表示算法执行时间的增长的数量级。增长率相同。表示算法执行时间的增长的数量级。n大大O表示法定义表示法定义 当当NN0时存在一个正的常数
7、时存在一个正的常数c和和N0,使得,使得T(n)cF(n),则(则(Big-Oh)T(N)就是就是O(F(n)含义:当含义:当n增大时,算法的运行时间的增长率小于等于增大时,算法的运行时间的增长率小于等于(n)的增长率的增长率。算法的渐进分析就是要估计,当数据规模逐步增大时资算法的渐进分析就是要估计,当数据规模逐步增大时资源开销源开销f(n)的增长趋势,得到一个精确的界限比较费时的增长趋势,得到一个精确的界限比较费时费力,也没有必要费力,也没有必要 时间复杂度的渐进表示法 1 log2n n nlog2n n2 n3 2n 3n n!加法规则加法规则 针对并列程序段:顺序结构,针对并列程序段:
展开阅读全文