搜索算法效率比较

数据结构课程设计报告搜索算法效率比较的设计专业 计算机科学与技术学生姓名Xxxxx班级Xxxx学号Xxxx指导教师Xxx完成日期 2016年6月16日1.设计题目42.设计目的及要求错误!未定义书签。2.1. 目的错误!未定义书签。2.2. 要求错误!未定义书签。3.设计内容44. 设计分析54.1.空间复杂度54.2非递归线性搜索设计64.3递归线性搜索64.4二叉搜索设计65. 设计实践75.1非递归线性搜索模块设计75.2递归线性搜索模块设计85.3二叉搜索模块设计85.4.主程序模块设计86测试方法107. 程序运行效果118. 设计心得13搜索算法效率比较的设计1. 概述算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。解决 一个问题，可能存在一种以上算法，当这些算法都能正确解决问题时，算法需要 的资源量将成为衡量算法优良度的重要度量，例如算法所需的时间、空间等。1.1. 设计目的数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构 课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质 是十分必要的。课程设计的目的：1. 要求学生达到熟练掌握C语言的基本知识和技能。2. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能 力。3. 提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的 正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。4. 培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一 步提高程序设计水平。5. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本 方法和技能。1.2. 设计要求数据结构课程设计用C/C+编程实现。课程设计的一般步骤：1. 问题描述与分析：根据设计题目的要求，充分地分析和理解问题，明确 问题要求做什么？限制条件是什么？2. 数据结构设计：为实现每个功能选择的逻辑结构和存储结构，分析原因 及合理性。3. 软件结构设计：设计软件模块之间的结构。4. 算法设计：算法的设计及算法分析。每个部分的算法设计说明，可以用 流程图描述算法。5. 程序编码：把详细设计的结果进一步求精为程序设计语言程序。源程序 要按照软件工程的规则来编写，要求结构清晰，重要功能部分要加上清晰的程序 注释。6. 调试分析：掌握调试工具的各种功能，设计测试数据，测试输出的结果。 并进行算法的时间复杂度和空间复杂度的分析。7. 总结：课程设计过程的收获，遇到问题以及解决问题的思路和方法，程 序调试能力的思考，对数据结构这门课程的认识及思考等。8. 编写课程设计报告。学生必须仔细阅读数据结构，认真主动完成课设的要求，有问题及时主动通 过各种方式与教师联系沟通；要发挥自主学习的能力，充分利用时间，安排好课 设的时间计划，并在课设过程中不断检测自己计划完成情况；独立思考，课程设 计中各任务的设计和调试哦要求独立完成，遇到问题可以讨论，可以通过同学间 相互讨论而解决。2. 设计题目给定一个已排序的由N个整数组成的数列0,1,2,3,N-1，在该队列中 查找指定整数，并观察不同算法的运行时间。考虑两类算法：一个是线性搜索，从某个方向依次扫描数列中各个元素；另 一个是二叉搜索法。要完成的任务是：分别用递归和非递归实现线性搜索；分析最坏情况下，两个线性搜索算法和二叉搜索算法的复杂度； 测量并比较这三个方法在N=100，500，1000，2000，4000，6000，8000, 10000时的性能。3. 设计内容任何程序基本上都是要用特定的算法来实现的。算法性能的好坏，直接决定 了所实现程序性能的优劣。此次对有关算法设计的基本知识作了简单的介绍。针 对静态查找问题，以搜索算法的不同实现，并对非递归线性搜索算法、递归线性 搜索算法和二叉搜索算法这三种方法进行了比较和分析。算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。解决一个 问题，可能存在一种以上的算法，当这些算法都能正确解决问题时，算法需要的 资源量将成为衡量算法优良度的重要度量，列如算法所需的时间、空间等。算法 是对问题求解过程的一种描述，是为解决一个问题或一类问题给出的一个正确 的，有限长的操作序列。由于查找一个数的过程，无论运用哪种算法对于电脑来说速度都是非常快 的，都爱1ms之内，无法用计时函数测试出来。所以为了能够直观准确地表示出 各个算法间的差异，此程序用了循环查找的方法，具体的思想是:先随机生成3000 个数作为查找的数据源，再随机生成3000个数作为被查找的数，让当前的查找算 法运行一趟，这样就相当于运行了 3000次。这样还不具有一定的客观性，用flag标记出刚刚运行完查找后的结果，从数 据源中找到目标的数标记为1，没找到的标记为0,并以此存为两个数组，最后我 们就可以使用这两个数组再次分别进行循环查找，同时开始计时，如此一来就可 以计算出各个算法在查找成功的情况下需要多少时间，反之在没查找到的情况下 需多长时间了。4. 设计分析表(List)是用来存放多个相同类型数据的数据结构之一。对表的所有操作 都可以通过使用数组来实现。在本题目中，使用数组来存放数列。虽然数组是动 态指定的，但是还是需要对表的大小的最大值进行估计。一般需要估计得大一些， 从而会浪费一定的空间。本题目中传递数组时，以常数参数const a的方式， 这样可以防止在搜索是数据被修改。123 N-1两种线性搜索算法的程序结构分别为以下所示。非递归线性搜索从数组的最 左边开始，逐个比较，直到找到所搜索的对象或者直到最后搜索失败。递归搜索 从最右开始搜索。为什么不从最左边开始？因为从左边开始，每次递归除要传递 待处理数列的左边界外，还需要传递运算数组的右边界(即N-1，这在本题目里 也是变化的)。从而右边开始，每次只需传递数组的右边界(左边界固定为)。所谓时间复杂度：时间复杂度在刚才提到的时间频度中，n称为问题的规 模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时 呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操 作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n), 使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是 T(n)的同数量级函数。记作T(n) = O(f(n),称O(f(n)为算法的渐进时间复杂 度，简称时间复杂度。按数量级递增排列，常见的时间复杂度有：常数阶0(1), 对数阶0(log2n),线性阶0(n),线性对数阶0(nlog2n),平方阶0(n2)，立方阶 0(n3),.，k次方阶0(nk),指数阶0(2n)。随着问题规模n的不断增大，上述时 间复杂度不断增大，算法的执行效率越低。最坏时间复杂度和平均时间复杂度：最坏情况下的时间复杂度称最坏时间复 杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这 样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上 界，这就保证了算法的运行时间不会比任何更长。在最坏情况下的时间复杂度 为T(n)=0(n)，它表示对于任何输入实例，该算法的运行时间不可能大于0(n)。平 均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运 行时间。此算法可以通过非递归线性搜索，线性递归搜索以及二叉法三种来进行搜索 算法效率比较，从中辨析出三种算法中哪种算法最有效。同时在主函数中用 clock()来调用库函数4.1.空间复杂度一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的 空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行 时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需 要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。 程序执行时所需存储空间包括以下两部分。固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。 这部分属于静态空间。可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间 等。这部分的空间大小与算法有关。4.2非递归线性搜索设计在一个已知无序队列中找出与给定关键字相同的数的具体位置。原理是让关 键字与队列中的二叔从第一个开始逐个比较，直到找出与给定关键字相同的数为 止。它对于表的结构没有任何要求，其缺点是查找效率低；其优点是算法简单。4.3递归线性搜索递归作为一种算法在程序设计语言中广泛应用，是指函数/过程/子程序在运 行过程序中直接或间接调用自身而产生的重入现象，程序调用自身的编程技巧成 为递归。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法， 它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题 来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次城府计算， 大大地减少了程序的代码量。递归的能力在于用有线的语句来定义对象的无限集 合。用递归思想写出来的程序往往十分简洁易懂。递归就是在过程或函数里调用 自身；在使用递增归策略时，必须有一个明确的递归结束条件，成为递归出口。4.4二叉搜索设计二叉搜索的算法思想是将数列按有序化（递增或递减）排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值 小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比 较，将查找区间缩小一般。流程图：开始0nreturnreturn5. 设计实践5.1非递归线性搜索模块设计非递归线性搜索的特点在于它的，每一次进行搜索时总是从数组的最左边开 始，逐个比较，直到找到所搜索的对象或者直到最后搜索失败。int IterativeSequentialSearch(const int a,int x,int n)( int i;for(i=0;ik，则中点值之后的数都大于k，所以k值在该表的左边，所以确定一个 新的查找区间；如果中点值k，则中点值之后的数都小于k，k值在该表的右边， 再在该表的右边确定一个新的查找区间；依次循环。它的核心程序如下：int BinarySearch(const int a,int x,int n) int low,mid,high; low=0;high=n-1;while(lowx) low=mid+1;else if(amidx) high=mid-1; else return mid; return -1; 对于输入数据量很大时，线性搜索的时间太慢，不宜使用。二叉搜索采用折 半的思想，它的运行时间为O(log2N)，比线性搜索要快许多，特别是在处理的 数据量比较大的时候非常有用。5.4.主程序模块设计此程序的作用是分别进行了定义，调用函数。并且通过clock()函数调用库 函数。程序如下：int main ()(/* clock()返回函数运行时间*/int i,n,x,a10000;long k,l;printf(Please enter n:n);scanf(d，&n);/* 输入数据 */if(n10000)/*处理异常输入*/(printf(error!)； return -1;x=n;/*指定要查找的数*/for(i=0;in;i+)/*数组初始化 */ai=i;printf(Please enter iterations:n); /*为了更准确地计算运行时 间，我们可以重复多次调用算法，再取平均值*/scanf(%ld,&k);if(k1)/*处理异常输入*/(printf(error!)； return -1;/* 非递归线性搜索 */start = clock(); /*记录函数的开始时间*/for(l=0;lk;l+)IterativeSequentialSearch(a,x,n);stop = clock(); /*记录函数的结束时间*/duration = (double)(stop - start)/CLK_TCK; /计算函数运行时间 */printf(nIterativeSequentialSearch:nIterations:%ldnTicks:%d nTotalTime:%.8lfnDuration:%.8lfn，k,(int)(stop-start),duration,duration/k );/*输出花费时间*/* 递归线性搜索 */start = clock(); /*记录函数的开始时间*/for(l=0;lk;l+)RecursiveSequentialSearch(a,x,n);stop = clock(); /*记录函数的结束时间*/duration = (double)(stop - start)/CLK_TCK; /计算函数运行时间 */printf(nRecursiveSequentialSearch:nIterations:%ldnTicks:%dnTotal Time:%.8lfnDuration:%.8lfn”,k,(int)(stop-start),duration,duration/k )；/*输出花费时间*/* 二叉搜索 */printf(nIterations of Binary Search is 100 times of iterations more than other two searchsn);k=100*k;/*由于二叉搜索的时间比较快，为了避免出现0秒，二叉搜索算法调用的次数是线性搜索的100倍*/start = clock(); /*记录函数的开始时间*/for(l=0;lk;l+)BinarySearch(a,x,n);stop = clock(); /*记录函数的结束时间*/duration = (double)(stop - start)/CLK_TCK; /*输出花费时间*/ printf(nBinarySearch:nIterations:%ldnTicks:%dnTotalTime:%.8lfnDuration:%.8lfn”,k,(int)(stop-start),duration,duration/k);/* 输出花费时间*/return 1;6测试方法按题目要求分别输入N=100,500,1000,2000, 10000，对于每一个N要选择 不同的重复调用次数K,直到测试结果趋于稳定。按要求输入数据，测试程序能否对输入内容进行数据合法性检测并进行相应 的异常处理。列如N=0，K=0，考察程序对异常情况进行处理的能力。测试案例：N1005001000重复次数2051000非递归线性搜索总时钟跳数105函数执行K次总时间（秒）0.001000000.000000000.00500000平均运行时间（秒）0.000050000.000000000.00000500重复次数2051000递归线性搜索总时钟跳数函数执行K次总时间（秒）10.0010000000.00000000440.04400000平均运行时间（秒）0.000005000.000000000.00004400重复次数2000500100000二叉搜索总时钟跳数函数执行K次总时间（秒）10.0010000000.00000000130.01300000平均运行时间（秒）0.000000500.000000000.00000013N200010000重复次数6080非递归线性搜索总时钟跳数函数执行K次总时间（秒）10.0010000050.00500000平均运行时间（秒）0.000016670.00006250重复次数6080递归线性搜索总时钟跳数函数执行K次总时间（秒）60.00600000360.03600000平均运行时间（秒）0.000100000.00045000重复次数60008000二叉搜索总时钟跳数函数执行K次总时间（秒）10.0010000010.00100000平均运行时间（秒）0.000000170.00000012在实际测试中，当程序运行时间太快，会无法获得实际运行时间。为了避免 这种情况，可以将同一操作运行K遍，得到1秒以上的时间，再将结果除以重复 次数K得到平均时间。若单重循环还不能达到目的，可用多重嵌套循环解决。7.程序运行效果当运行程序时，所输入 K的值没有错误的时候会出现如下界面：当输入的值有错误的时候，表示所输入的值不在所规定的范围内时，会出现 以下的界面：TnWAJ祜俣芸古市力麻.人=8.设计心得在这次课程设计里，也让我从中有所收获。虽说只有一个礼拜，但在课后还 是花了不少时间。看教材中的程序时，发现一个程序设计就是算法与数据结构的 结合体，看程序有时都看不懂，更别提自己编译了，觉得自己在这方面需要掌握 的内容还有很多狠多。虽然过程曲折可谓一语难尽。整天都是对着电脑，不然就 是翻阅资料。这次课程设计使我体会到只有做到细心耐心，恒心才能做好事情。课程设计是培养学生综合运用所学知识，发现，提出，分析和解决实际问题， 锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程.同时 加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解。培 养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分 析问题，解决问题的能力。而且做课程设计同时也是对课本知识的巩固和加强， 平时看课本是，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解 了。而且还可以记住很多东西。通过这次课程设计，我懂得了理论与实际相结合 是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合 起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力 和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第 一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不 足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和 认识。但也让我认识到我还有很多的不足，需要大量的学习，以此来达到能力的 提高及熟练的应用。