《各种查找算法性能分析》由会员分享，可在线阅读，更多相关《各种查找算法性能分析（14页珍藏版）》请在金锄头文库上搜索。
1、项目名称：各种查找算法的性能测试项目成员:组编号：完成时间：目录前言2正文2第一章简介21.1顺序查找问题描述 21.2二分查找问题描述 2第二章算法定义22.1顺序查找算法定义22.2二分查找算法定义 3第三章测试结果(Testing Results) 53.1实验结果表 53.2散点图记录 5第四章分析和讨论64.1顺序查找分析 64.2二分查找分析 6附录：源代码(基于 C语言的)7声明13、八 、亠刖言查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的 值，我们称之为查找键。对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法
2、快， 但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性的问题， 但会发生其他的问题（动态查找表）。在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找），二分查找（采用分治技术），哈希查找（理论上来讲是最好的查找方法）。第一章：简介（Introduction）i.i顺序查找问题描述：顺序查找从表中最后一个记录开始， 逐个进行记录的关键字和给定值的比较， 若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。1.2二分查找问题描述：（1）分
3、析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半 查找函数。（2）编写程序实现：在保存于数组ai有序数据元素中查找数据元素k是否存在。数元素 k要包含两种情况：一种是数据元素k包含在数组中；另一种是数据元素k不包含在数 组中（3）数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。（4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。第二章：算法定义（ AlgorithmSpecificati on ）2.1顺序查找从表的一端向另一端逐个进行记录的关键字和给定值（要查找的元素）的比较，若某个记录的关键字和给定值比较相等，则查找成功，
4、找到所查找记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功顺序查找的算法如下：int SeqSearch1(int r , int n, int k) /数组 r1 rn存放查找集合，n 是数组中元素的个数(即查找表的长度)，k是要查找的元素i=n;/从后往前把表中的元素与要查找的元素进行比较while (i0 & ri!=k)/当i0并且数组元素中的值不等于要查找元素时，i减一继续执行while循环 i-；return i;/i的值为0则没找到，为非0则i为要查找元素的位置2.2二分查找二分查找又称折半查找，二分查找首先要求待查找的表是有序表，如果
5、要查找的元素是表的中间 的那个元素，则找到要查找的元素，查找成功；如果要查找的元素比中间的那个元素小则使用相同的 策略只在左边的区间查找就可以；如果要查找的元素比中间的那个元素大，则使用相同的策略在右边的区间进行查找；每次将待查找的元素的所在区间缩小一半。(1) 二分查找算法的递归算法int binary_search_2 (int a,int n,int k)递归的二分查找算法的伪代码：查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素int Low,Mid,High;Low=0,High=n-1;选择查找的最大的范围Mid=(Low+High)/2;quicksort(a,0,S
6、IZE-1);if (Low=High) return -1;/ 数字-1 表示没有结果if (aMid=k) return Mid; / 找到要查找的元素else if (aMidk)return (binary_search_2 (a,Mid-1,k);需要在左边的更小的范围内查找else return ( binary_search_2 (a+Mid+1,High-Mid,k); 在右边的更大的范围内查找a中，n(2) 二分查找的非递归算法int binary_search_1 (int a,int n,int k) /非递归的二分查找算法的伪代码：查找表放在数组是查找表中元素的个数，k
7、是待查找的元素int Low,High,i,mid;Low=0;High=n-1;while(LowvHigh)mid=(Low+High)/2;if(k=amid)return mid;/查找成功else if(kamid)Low=mid+1;在后半区间查找else High=mid-1;/在前半区间查找return 0;/查找失败第三章：测试结果(Testing Results )3.1实验结果表:查找算法随机数组兀素个数(个)查找时间(sec on ds)20.022000顺序查找40.04700060.06200080.0820001100.10000020.190000二分查找40.
8、39000060.39000080.0600001100.0600003.2散点图:70605040302C+顺序查找*二分查找1012第四章：分析和讨论4.1.实现顺序查找算法：（1）顺序查找算法思路很简单，就是一种遍历的思想，一个个查找目标元素，实现也很简单。（2）对于有n个元素的表适用顺序查找。比较次数：不成功：比较 n次。成功查找：最好的情况为1次，即第一个元素即为目标元素；最差的情况为n次；平均比较次数（n+1） /2次。 所以当表很大时，顺序查找的代价是很大的。（3）顺序查找算法不会有重复的比较出现，即一旦找到即成功，但同时这种代价是当表中有重复的目标元素时（比如有多个目标元素）我
9、们只能得到第一个元素的位置。顺序查找算法时间复杂度为0（n）。4.2实现二分查找算法：（1）二分查找法思路：递增排列的表，首先从中间元素开始查找，如果元素比目标元素小，则查找 后半部分表，反之查找前半部分表，并重复这一过程。这样每次查找中我们都把表的长度减半。（2）二分查找在实现中有量Low和High，每次减半的过程体现在 Low和High的改变上，在代码的实现上可以使用单纯的循环或者用函数递归的思想。 递归思想更容易理解，但编写之后我们发现函数是尾递归，尾递归通常可以用简单的循环实现， 循环在操作来说没有了函数调用的过程，更节省时间和空间。（3）编码中小小地方的改动可能对程序有很大的改观。如
10、上述两种二分查找非递归 bin ary_search_1 （不比较等于的情况）递归 bin ary_search_2 （添加等 于情况）丈较次数二分至找算劝查我备注binary search llg n *1- 1比较次数丑良binary seErch 22 lg n - 3211 n置优膏抚只比较1次折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为
11、空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小 一半。时间复杂度：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(lgn)或0(n) (n代表集合中元素的个数)空间复杂度：虽以递归形式定义，但是尾递归，可改写为循环，所以空间复杂度为0(n)=0(lgn)。附录：源代码(基于C语言的)#i nclude stdio.h#i nclude time.h#i nclude stdlib.h#define SIZE 1000待排数的规模#define PRT_RT 1是否显示排序前后的数组情况，对较大规模的数组不显示0为不显示，1为显示顺序查找算法int SeqSearch1(int
12、r , int n, int k) /数组r1 rn存放查找集合，n是数组中元素的个数(即查找 表的长度)，k是要查找的元素int i=n;从后往前把表中的元素与要查找的元素进行比较while(i0 & ri!=k)return i;/i的值为0则没找到，为非0则i为要查找元素的位置/二分查找的递归算法int binary_search_2 (int a,int n,int k)递归的二分查找算法的伪代码：查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素int Low,Mid,High;Low=0,High=n-1;选择查找的最大的范围Mid=(Low+High)/2;if (Lo
13、w=High) return -1;/ 数字-1 表示没有结果if (aMid=k) return Mid; /找到要查找的元素else if (aMidk)return (binary_search_2 (a,Mid-1,k);/需要在左边的更小的范围内查找else return ( binary_search_2 (a+Mid+1,High-Mid,k);/在右边的更大的范围内查找/二分查找的非递归算法int bin ary_search_1 (int a,i nt n ,i nt k)int Low,High,i,mid;Low=0;High=n-1;while(LowvHigh)mid
14、=(Low+High)/2;if(k=amid)return mid;/查找成功else if(kamid)Low=mid+1;在后半区间查找else High=mid-1;/在前半区间查找return 0;/查找失败/快速排序算法void quicksort nt c,i nt start,i nt end)int i,j,mid;i=start;j=e nd;mid=ci;while(start=e nd)return;while(ij)while(imid)j-;if(ij)ci=cj;i+；while(ij & cimid)i+；if(ij)cj=ci;j-；ci=mid;quicksort(c,start,i-1);递归调用快速排序继续对前半部分的元素进行排序 quicksort(c,i+1,e nd);/递归调用快速排
