各种查找算法的性能比较测试

算法设计与分析各种查找算法的性能测试目录TOC\o"1-5"\h\z\o"CurrentDocument"摘要2\o"CurrentDocument"第一章：简介（Introduction）31.1算法背景3\o"CurrentDocument"第二章：算法定义（AlgorithmSpecification）42.1数据结构42.2顺序查找法的伪代码42.3二分查找（递归）法的伪代码52.4二分查找（非递归）法的伪代码6\o"CurrentDocument"第三章：测试结果（TestingResults）83.1测试案例表83.2散点图9\o"CurrentDocument"第四章：分析和讨论114.1顺序查找114.1.1基本原理114.2.2时间复杂度分析11\o"CurrentDocument"4.2.3优缺点114.2.4该进的方法124.2二分查找（递归与非递归）124.2.1基本原理124.2.2时间复杂度分析13\o"CurrentDocument"4.2.3优缺点134.2.4改进的方法13\o"CurrentDocument"附录：源代码（基于C语言的）15摘要在计算机许多应用领域中，查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的查找次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。关键字：顺序查找、二分查找（递归与非递归）第一章：简介（Introduction）1.1算法背景查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性的问题，但会发生其他的问题（动态查找表）。在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找），二分查找（采用分治技术），哈希查找（理论上来讲是最好的查找方法）。第二章：算法定义（AlgorithmSpecification）2.1数据结构三种查找都是以整形数组作为主要的数据结构，如Inta[n]。我们主要测试的是算法的性能，并不是仅仅对算法的查找，以数组作为主要的数据结构能满足实验的要求。2.2顺序查找法的伪代码算法：顺序查找法目的：在给定的集合（或者是多重集，允许多个元素具有相同的值）中找寻一个给定的值。前提：给定一给定一个集合（或多重集）（A1、A2、A3、A4.....An）。返回：寻找出给定值。伪代码如下：intSeqSearch1（intr[],intn,intk）//数组r[1]~r[n]存放查找集合，n是数组中元素的个数（即查找表的长度），k是要查找的元素{i=n;//从后往前把表中的元素与要查找的元素进行比较while（i>0&&r[i]!=k）i--;returni;//i的值为0则没找到，为非0则i为要查找元素的位置}2.3二分查找（递归）法的伪代码算法：二分查找（递归）法目的：在给定的集合（或者是多重集，允许多个元素具有相同的值）中找寻一个给定的值。前提:给定一给定一个集合（或多重集）（A1、A2、A3、A4.....An）。返回：寻找出给定值。伪代码如下：intsearch(inta[],intn,intk)//查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素{Low=0,High=n-1;//选择查找的最大的范围Mid=(Low+High)/2;if((Low>=High)||(n==-1))return-1;//数字-1表示没有结果elseif(a[Mid]==k)returnMid;//找到要查找的元素elseif(a[Mid]>g)return(search(a,Mid-1,g));//需要在左边的更小的范围内查找elsereturn(search(a+Mid+1,n-Mid,g));//在右边的更大的范围内查找}2.4二分查找(非递归)法的伪代码算法：二分查找(非递归)法目的：在给定的集合(或者是多重集，允许多个元素具有相同的值)中找寻一个给定的值。前提：给定一给定一个集合(或多重集)(A1、A2、A3、A4.....An)。返回：寻找出给定值。伪代码如下：intBinarySearch(inta[],intn,intk)//查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素。{Low=0;high=n-1;//置区间初值while(low<high)mid=(low+high)/2;if(key==a[mid])returnmid;//查找成功elseif(key>a[i])low=middle+1;//在后半区间查找elsehigh二middle-1;//在前半区间查找return0;//查找失败}

第三章：测试结果（TestingResults）3.1测试案例表实验项目二各种查找算法的性能测试（数据数多少不同时用时）数据3080200200010000顺序查找0000.00150.002二分查找（递归）00000.001二分查找（非递归）00000实验项目二各种查找算法的性能测试（查找值不同时用时）数据序\10251204775000

顺序查找00000二分查找（递归）00000二分查找（非递归）000003.2散点图各种查找的性能比-顺序查找T一二分递归二分非递归在测试过程中n的值取了30、80、200、2000、10000；取这些值是因为我想测试在随机数多少不一的情况下所用时间的区别。经过实验发现查找过程中三种查找方法都很迅速，但当数字增大时还是有

些差别，顺序查找用时最多。O18O186420••••

oooO

间时用所心OO1X20003000400050006000查找值大小

—顺序查找二分查找（递归）二分查找（非递在实验过程中我们在同规模5000的情况下把key值取了10、25、120、477、5000；取逼些值是想看看在查找值不一的情况下所用时间的不同。经过实验发现无论key取值多少三种查找时间依旧相同。实验中我们所预期的结果是：输入不同的规模，根据随机数的产生，三种查找方法都会出现相应的时间。可是，实验过程中，随机数的原因，很多次测量都是0，就只有极少数的情况下会出现时间，而且出现的时间都很小，都是0.001或者0.002。第四章：分析和讨论4.1顺序查找4.1.1基本原理从表的一端向另一端逐个进行记录的关键字和给定值(要查找的元素)的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查找记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。4.2.2时间复杂度分析由于顺序查找是从表的一端向另一端逐个进行记录的关键字和给定值的比较，对于n个元素的表，不成功的比较次数为n，查找成功：最好的情况为1次，最差的情况为n次，所以查找成功时的平均查找长度为(n+1)/2，且顺序查找的时间复杂度为O(n)。4.2.3优缺点与其他查找算法相比，其缺点是平均查找长度较大，特别是当n较大时，查找效率低，但他有个很大的优点是算法简单且适应面广，它对表的结构无任何要求，无论记录是否按关键字有序均可应用。

4.2.4该进的方法自然语言描述：当没有超出范围并且没有我到就要继续查找』设置变量自然语言描述：当没有超出范围并且没有我到就要继续查找』设置变量0,result没找到/ffiuAn1j4.2二分查找（递归与非递归）4.2.1基本原理二分查找又称折半查找，二分查找首先要求待查找的表是有序表，如果要查找的元素是表的中间的那个元素，则找到要查找的元素，查找成功；如果要查找的元素比中间的那个元素小则使用相同的策略只在左边的区间查找就可以；如果要查找的元素比中间的那个元素大，则使用相同的策略在右边的区间进行查找；每次将待查找的元素的所在区间缩小一半。4.2.2时间复杂度分析二分查找的时间复杂度是O（log（n）），最好的情况是指针mid指的第一个数就是要找的值，最坏的情况的所找的值是第一个或最后一个数，最坏情况下的时间复杂度是O（n）。4.2.3优缺点查找的效率较高，但是只适用于有序表，且限于顺序存储结构，对线性链表无法有效的进行查找，还有二分查找在一些特殊情况下，其查找效率很低，如查找元素是数列中的第一个元素和最后一个元素。4.2.4改进的方法改进后的二分查找算法思路：若k不等于a[mid]，则同时改变low和high的值，使下一次的啊[low]与k之间的距离尽可能等于k与a[high]之间的距离，为下一次的二分查找k成功提供最大的可能。伪代码如下：（1）low=0；high=n-1（2）Index=1（3）Mid=（high+low）/2（4）While（low<=highandindex=-1）（5）Ifk<[mid]（6）（high=mid-1（7）Low=high-2*pos1}Elseifx>a[mid]Low=mid+1High=low+2*pos2Elseindex=mid(12)Returnindex注:任意两个元素a[i]与a[j]之间的距离为pos,pos1为k与a[high]之间的距离，pos2为k与a[low]之间的距离。附录：源代码(基于C语言的)#include"stdio.h"#include"stdlib.h"#include"time.h"/*顺序查找*/intSeqSearch(inta[],intn,intkey)//数组a[1]~a[n]存放查找集合，n是数组中元素的个数(即查找表的长度)，key是要查找的元素{inti;//定义了一个整形变量ii=n;〃从后往前把表中的元素与要查找的元素进行比较while(i>0&&a[i]!=key)/*当i大于0并且目前找到的元素和要找的元素不相等，则执行下一条语句*/i--;returni;//i的值为0则没找到，为非0则i为要查找元素的位置}/*二分查找的递归*/intdiguisearch(inta[],intn,intkey)//数组a[1]~a[n]存放查找集合，n是数组中元素的个数(即查找表的长度)，key是要查找的元素{intHigh,Low,Mid;//定义了整形变量High,Low,MidLow=0,High=n-1;//选择查找的最大的范围Mid=(Low+High)/2;if((Low>=High)||(n==-1))return-1;//数字-1表示没有结果elseif(a[Mid]==key)returnMid;〃找到要查找的元素elseif(a[Mid]>key)return(diguisearch(a,Mid-1,key));//需要在左边的更小的范围内查找elsereturn(diguisearch(a+Mid+1,n-Mid,key));//在右边的更大的范围内查找}〃二分法非递归intfeidiguisearch(inta[],intn,intkey)/*数组a[1]~a[n]存放查找集合，n是数组中元素的个数(即查找表的长度)，key是要查找的元素*/{intmid;〃定义了一个整形变量midintlow=0;//定义了一个整形变量low,并且赋值为0inthigh=n-1;//选择查找的最大的范围while(lowvhigh){mid=(low+high)/2;if(key==a[mid])//如果数组的中间元素和要查找的元素相等returnmid;〃查找成功elseif(key>a[mid])low=mid+1;//在后半区间查找elsehigh=mid-1;//在前半区间查找}return-1;//查找失败}voidmain(){intn=200;//定义一个变量n，n=200inta[200];//定义一个数组a[]，数组里数的个数是200intkey=59;srand((unsigned)time(NULL));/*初始化随机函数种子，逼句是拿系统时间作为种子，由于时间是变化的，种子变化，可以产生不相同的随机数*/for(inti=0;ivn;i++)//初始化变量i的值为0，当i=0时执行循环，在每次循环后i执行加1操作{a[i]=rand()%100;//随机数的取值从0到100之间}/*for(intb=0;bvn;b++){printf("%d",a[b]);}*/clock_tstart,end;〃声明时间变量doubleduration;〃声明用于记录时间的变量start=clock();//开始记录时间SeqSearch(a,n,key);//计算直接查找规模为n的时候用的时间printf("%d",key);//输出要查找的元素，即keyend=clock();//停止记录时间duration=(double)(end-start)/CLOCKS_PER