《数据结构与算法设计PPT (3).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (3).pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章 绪论1.4 算法n算法、算法的特性算法、算法的特性n算法好坏的评价标准算法好坏的评价标准n算法的性能度量方法算法的性能度量方法主要内容算法：算法：对特定问题的求解过程的描述，是指令的对特定问题的求解过程的描述，是指令的有限序列，也就是为解决某一具体问题而采取的有限序列，也就是为解决某一具体问题而采取的有限的操作步骤。有限的操作步骤。程序是算法的实现，计算机按照程序逐步执行算程序是算法的实现，计算机按照程序逐步执行算法，实现对问题的求解。法，实现对问题的求解。定义：定义：一个有穷的指令集一个有穷的指令集，这些指令为解决某一特定任，这些指令为解决某一特定任务规定了一个运算序列。务规定了一个
2、运算序列。算法有输入有输入 有有0 0个或多个输入个或多个输入有输出有输出 有一个或多个输出（处理结果）有一个或多个输出（处理结果）确定性确定性 每步定义都是确切、无歧义的，对于每一每步定义都是确切、无歧义的，对于每一种输入，算法的执行路径只能有一条，即对于一种种输入，算法的执行路径只能有一条，即对于一种输入只能得到一种输出输入只能得到一种输出有穷性有穷性 算法应在执行有穷步后结束，每一步骤都算法应在执行有穷步后结束，每一步骤都能在有限时间内完成能在有限时间内完成有效性有效性 每一条运算应足够基本能被执行，即算法每一条运算应足够基本能被执行，即算法中描述的操作都可以通过已经实现的基本运算的有中
3、描述的操作都可以通过已经实现的基本运算的有限次进行实现限次进行实现算法的五个重要特性算法的五个重要特性*算法的描述：本课程采用类C+语言进行描述*常用的设计方法：*穷举法*贪心法*分治法*回溯法*动态规划法*裁剪与分枝界限法算法的描述与设计方法算法的描述与设计方法事例学习：事例学习：选择排序问题选择排序问题明确问题：明确问题：非递减排序非递减排序解决方案：解决方案：逐个选择最小数据逐个选择最小数据算法框架：算法框架：for(intfor(inti i=0;0;i i n n-1;1;i i+)/)/n n-1 1趟趟从从a a i i 检查到检查到a a n n-1 1 求出其中的最小数位置求
4、出其中的最小数位置k k;交换交换a a i i 与与a a k k;细化程序：细化程序：程序程序SelectSortSelectSort算法设计过程算法设计过程 自顶向下逐步求精自顶向下逐步求精void void selectSortselectSort(int a,const int n)(int a,const int n)/对对n n个整数个整数a0,a1,ana0,a1,an-1,1,按非递减顺序排序按非递减顺序排序for(int for(int i i=0;=0;i i n n-1;1;i i+)+)int k=int k=i i;/从从a ai i 检查到检查到anan-1,1,
5、找最小的整数找最小的整数,在在akakfor(int j=i+1;j n;for(int j=i+1;j n;j+j+)if(aj ak)k=j;if(aj 0)y=1;else if(x=0)y=0;else y=-1;return y;第一个层次程序不包含语法错误int sign(int x)int y;if(x 1)y=1;else if(x=0)y=0;else y=-1;return y;第二个层次第二个层次输入输入100 输出输出1输入输入0 输出输出0输入输入100 输出输出1int sign(int x)int y;if(x=1)y=1;else if(x=0)y=0;else
6、 y=-1;return y;第三个层次第三个层次输入输入100 输出输出1输入输入1 输出输出1输入输入0 输出输出0输入输入-1 输出输出-1输入输入-100 输出输出-1int sign(int x)int y;if(x 0)y=1;else if(x=0)y=0;else y=-1;if(x=0 x1234)y=0;return y;第四个层次第四个层次所有可能的输入所有可能的输入解决同一个问题存在多种算法，如何评估各种算法的好解决同一个问题存在多种算法，如何评估各种算法的好坏？坏？运行算法所需要的计算机资源运行算法所需要的计算机资源时间和空间时间和空间评价一个算法的优劣的重要依据评价
7、一个算法的优劣的重要依据:占用多少计算机资源占用多少计算机资源程序运行时所要花费的时间代价程序运行时所要花费的时间代价程序中使用的数据结构占用的空间代价程序中使用的数据结构占用的空间代价如何评价？如何评价？算法的后期测试：实验方法、仿真方法算法的后期测试：实验方法、仿真方法算法的事前估计：分析的方法算法的事前估计：分析的方法算法效率的度量算法效率的度量算法的后期测试算法的后期测试n实验的方法实验的方法：采用实际数据测试程序的执行时间采用实际数据测试程序的执行时间n仿真的方法仿真的方法：通过随机过程生成模拟数据进行测试通过随机过程生成模拟数据进行测试n在算法中的某些部位插装时间函数在算法中的某些
8、部位插装时间函数time time()()或者或者clock clock()()测定算法完成某一功能所花费的时间。测定算法完成某一功能所花费的时间。n采用开发工具提供的时间测量工具采用开发工具提供的时间测量工具profileprofile顺序搜索(Sequenial Search)#include using namespace std;int seqsearch(int*a,const int n,const int x)int i=0;while(i n&ai!=x)i+;if(i=n)return-1;return i;int main()int n10=5000,10000,15000
9、,20000,25000,30000,35000,40000,50000,100000;int*data;for(int j=0;j 10;j+)data=new intnj;for(int i=0;i nj;i+)datai=(rand()*1000)%1000;datanj-1=1000;/实验中待查找的数据clock_t start,stop;start=clock();seqsearch(data,nj,1000);stop=clock();double runTime=stop-start;cout nj 个数中找最后一个数所需要时间为：runTime endl;delete dat
10、a;return 0;程序测试结果输出时间效率XY点状图020406080100120140160180200020000400006000080000100000120000顺序查找不同数据规模下查找时间图程序在计算机上运行所需时间的影响因素程序在计算机上运行所需时间的影响因素算法本身选用的策略算法本身选用的策略问题的规模问题的规模规模越大，消耗时间越多规模越大，消耗时间越多书写程序的语言书写程序的语言语言越高级，消耗时间越多语言越高级，消耗时间越多编译产生的机器代码编译产生的机器代码质量质量机器执行指令的机器执行指令的速度速度为便于比较算法本身的优劣为便于比较算法本身的优劣应排除其它影响算
11、法效率的因素应排除其它影响算法效率的因素希望软件执行时间可预测希望软件执行时间可预测算法分析感兴趣的不是具体的资源占用量，而是与具体算法分析感兴趣的不是具体的资源占用量，而是与具体的平台无关、具体的输入实例无关，且随着规模增长的的平台无关、具体的输入实例无关，且随着规模增长的值是可预测的。值是可预测的。算法的事前估计算法的事前估计希望了解软件执行时间的变化趋势希望了解软件执行时间的变化趋势与问题规模之间的关系，用一定的规模数据作为输入时与问题规模之间的关系，用一定的规模数据作为输入时程序所需的基本操作的次数来描述时间效率程序所需的基本操作的次数来描述时间效率忽略细节忽略细节完成一个基本操作所需要的时间应该与具体的被操作数完成一个基本操作所需要的时间应该与具体的被操作数无关无关算法的复杂性分析算法的复杂性分析