搜索算法效率比较

《搜索算法效率比较》由会员分享，可在线阅读，更多相关《搜索算法效率比较（12页珍藏版）》请在金锄头文库上搜索。

1、数数据据结结构构课课程程设设计计报报告告 搜索算法效率比较的设计搜索算法效率比较的设计 专业专业计算机科学与技术 学生姓名学生姓名Xxxxx 班级班级Xxxx 学号学号Xxxx 指导教师指导教师Xxx 完成日期完成日期2016 年 6 月 16 日 搜索算法效率比较的设计 2 目目 录录 1.设计题目3 2.设计目的及要求3 2.1目的3 2.2要求3 3.设计内容3 4.设计分析4 4.1.空间复杂度.5 4.2 非递归线性搜索设计.5 4.3 递归线性搜索.5 4.4 二叉搜索设计.6 5.设计实践7 5.1 非递归线性搜索模块设计.7 5.2 递归线性搜索模块设计.7 5.二叉搜索模块设

2、计7 5.4.主程序模块设计.8 6 测试方法10 7.程序运行效果11 8.设计心得12 搜索算法效率比较的设计 3 搜索算法效率比较的设计搜索算法效率比较的设计 1.设计题目设计题目 给定一个已排序的由N个整数组成的数列0,1,2,3,N-1，在该队列中 查找指定整数，并观察不同算法的运行时间。考虑两类算法：一个是线性搜索， 从某个方向依次扫描数列中各个元素；另一个是二叉搜索法。要完成的任务是： 分别用递归和非递归实现线性搜索；分析最坏情况下，两个线性搜索算法和二 叉搜索算法的复杂度；测量并比较这三个方法在 N=100，500，1000，2000,4000,6000,8000，10000时

3、的性能。 2.2.设计目的及要求设计目的及要求 2.1目的 （1）需要同学达到熟练掌握C语言的基本知识和技能； （2）基本掌握面向对象程序设计的基本思路和方法； （3）能够利用所学的基本知识和技能，解决简单的程序设计问题； 2.2要求 学生必须仔细阅读数据结构，认真主动完成课设的要求，有问题及时主动 通过各种方式与教师联系沟通；要发挥自主学习的能力，充分利用时间，安排 好课设的时间计划，并在课设过程中不断检测自己计划完成情况；独立思考， 课程设计中各任务的设计和调试哦要求独立完成，遇到问题可以讨论，可以通 过同学间相互讨论而解决。 3.3.设计内容设计内容 任何程序基本上都是要用特定的算法来实

4、现的。算法性能的好坏，直接决 定了所实现程序性能的优劣。此次对有关算法设计的基本知识作了简单的介绍。 针对静态查找问题，以搜索算法的不同实现，并对非递归线性搜索算法、递归 线性搜索算法和二叉搜索算法这三种方法进行了比较和分析。 算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。解决一 个问题，可能存在一种以上的算法，当这些算法都能正确解决问题时，算法需 要的资源量将成为衡量算法优良度的重要度量，列如算法所需的时间、空间等。 算法是对问题求解过程的一种描述，是为解决一个问题或一类问题给出的一个 正确的，有限长的操作序列。 由于查找一个数的过程，无论运用哪种算法对于电脑来说速度都是非常

5、快 的，都爱1ms之内，无法用计时函数测试出来。所以为了能够直观准确地表示出 各个算法间的差异，此程序用了循环查找的方法，具体的思想是：先随机生成 搜索算法效率比较的设计 4 3000个数作为查找的数据源，再随机生成3000个数作为被查找的数，让当前的 查找算法运行一趟，这样就相当于运行了3000次。 这样还不具有一定的客观性，用flag标记出刚刚运行完查找后的结果，从 数据源中找到目标的数标记为1，没找到的标记为0，并以此存为两个数组，最 后我们就可以使用这两个数组再次分别进行循环查找，同时开始计时，如此一 来就可以计算出各个算法在查找成功的情况下需要多少时间，反之在没查找到 的情况下需多长

6、时间了。 4.4.设计分析设计分析 表（List）是用来存放多个相同类型数据的数据结构之一。对表的所有操 作都可以通过使用数组来实现。在本题目中，使用数组来存放数列。虽然数组 是动态指定的，但是还是需要对表的大小的最大值进行估计。一般需要估计得 大一些，从而会浪费一定的空间。本题目中传递数组时，以常数参数const a 的方式，这样可以防止在搜索是数据被修改。 123N-1 两种线性搜索算法的程序结构分别为以下所示。非递归线性搜索从数组的 最左边开始，逐个比较，直到找到所搜索的对象或者直到最后搜索失败。递归 搜索从最右开始搜索。为什么不从最左边开始？因为从左边开始，每次递归除 要传递待处理数列

7、的左边界外，还需要传递运算数组的右边界（即N-1，这在本 题目里也是变化的）。从而右边开始，每次只需传递数组的右边界（左边界固 定为0）。 所谓时间复杂度：时间复杂度 在刚才提到的时间频度中，n称为问题的规 模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时 呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操 作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数 f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称 f(n)是T(n)的同数量级函数。记作T(n)=(f(n),称(f(n) 为算法的渐进

8、时 间复杂度，简称时间复杂度。 按数量级递增排列，常见的时间复杂度有：常数 阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立 方阶O(n3),.， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上 述时间复杂度不断增大，算法的执行效率越低。 最坏时间复杂度和平均时间复杂度：最坏情况下的时间复杂度称最坏时间 复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间 的上界，这就保证了算法的运行时间不会比任何更长。 在最坏情况下的时间复 杂度为

9、T(n)=0(n)，它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。 搜索算法效率比较的设计 5 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期 望运行时间。 此算法可以通过非递归线性搜索，线性递归搜索以及二叉法三种来进行搜 索算法效率比较，从中辨析出三种算法中哪种算法最有效。同时在主函数中用 clock()来调用库函数 4.1.空间复杂度 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的 空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执 行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外， 还需要一些对数据

10、进行操作的工作单元和存储一些为现实计算所需信息的辅助 空间。程序执行时所需存储空间包括以下两部分。 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。 主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空 间。这部分属于静态空间。 可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空 间等。这部分的空间大小与算法有关。 4.2 非递归线性搜索设计 在一个已知无序队列中找出与给定关键字相同的数的具体位置。原理是让 关键字与队列中的二叔从第一个开始逐个比较，直到找出与给定关键字相同的 数为止。它对于表的结构没有任何要求，其缺点是查找效率低；其优点是算法

11、简单。 4.3 递归线性搜索 递归作为一种算法在程序设计语言中广泛应用，是指函数/过程/子程序在运 开始 两数是否相等 是 否 返 回 位 置 返回 搜索算法效率比较的设计 6 行过程序中直接或间接调用自身而产生的重入现象，程序调用自身的编程技巧 成为递归。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方 法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的 问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次城府 计算，大大地减少了程序的代码量。递归的能力在于用有线的语句来定义对象 的无限集合。用递归思想写出来的程序往往十分简洁易懂。递归就是在过程或 函

12、数里调用自身；在使用递增归策略时，必须有一个明确的递归结束条件，成 为递归出口。 4.4 二叉搜索设计 二叉搜索的算法思想是将数列按有序化（递增或递减）排列，查找过程中 采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元 素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过 一次比较，将查找区间缩小一般。 流程图： 开始 搜索算法效率比较的设计 7 5.5.设计实践设计实践 5.1 非递归线性搜索模块设计 非递归线性搜索的特点在于它的，每一次进行搜索时总是从数组的最左边 开始，逐个比较，直到找到所搜索的对象或者直到最后搜索失败。 int IterativeSe

13、quentialSearch(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

14、return mid; return -1; 对于输入数据量很大时，线性搜索的时间太慢，不宜使用。二叉搜索采用 折半的思想，它的运行时间为 O（log2N） ，比线性搜索要快许多，特别是在处 理的数据量比较大的时候非常有用。 搜索算法效率比较的设计 8 5.4.主程序模块设计 此程序的作用是分别进行了定义，调用函数。并且通过 clock()函数调用 库函数。 程序如下： int main ( ) /* clock() 返回函数运行时间 */ int i,n,x,a10000; long k,l; printf(“Please enter n:n“); scanf(“%d“, /* 输入数据 *

15、/ if(n10000) /*处理异常输入*/ printf(“error!“); return -1; x=n; /* 指定要查找的数 */ for(i=0;in;i+) /*数组初始化 */ ai=i; printf(“Please enter iterations:n“); /*为了更准确地计算运行 时间，我们可以重复多次调用算法，再取平均值*/ scanf(“%ld“, if(k1) /*处理异常输入*/ printf(“error!“); return -1; /* 非递归线性搜索 */ start = clock(); /* 记录函数的开始时间 */ for(l=0;lk;l+)

16、IterativeSequentialSearch(a,x,n); stop = clock(); /*记录函数的结束时间*/ duration = (double)(stop - start)/CLK_TCK; /*计算函数运行时 间 */ printf(“nIterativeSequentialSearch:nIterations:%ldnTicks:%d nTotal Time:%.8lfnDuration:%.8lfn“,k,(int)(stop- start),duration,duration/k);/*输出花费时间*/ 搜索算法效率比较的设计 9 /* 递归线性搜索 */ start = clock();