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

《各种查找算法的性能比较测试》由会员分享，可在线阅读，更多相关《各种查找算法的性能比较测试（17页珍藏版）》请在装配图网上搜索。

1、算法设计与分析各种查找算法的性能测试目录摘要2第一章：简介（Introduction） 31.1算法背景3第二章：算法定义（AlgorithmSpecification） 42.1数据结构42.2顺序查找法的伪代码42.3二分查找（递归）法的伪代码52.4二分查找（非递归）法的伪代码6第三章：测试结果（Testing Results） 83.1测试案例表83.2散点图9第四章：分析和讨论114.1顺序查找114.1.1基本原理114.2.2时间复杂度分析114.2.3优缺点114.2.4该进的方法124.2二分查找（递归与非递归）124.2.1基本原理124.2.2时间复杂度分析134.2.3

2、优缺点134.2.4改进的方法13附录：源代码（基于C语言的）15摘要在计算机许多应用领域中，查找操作都是十分重要的研究技术。 查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找 和动态查找。我们设置待查找表的元素为整数，用不同的测试数据做测试比 较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或 者输入数据。比较的指标为关键字的查找次数。经过比较可以看到， 当规模不断增加时，各种算法之间的差别是很大的。这三种查找方法 中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找 方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分 查找只适用于有序表，且限于顺序存

3、储结构。关键字：顺序查找、二分查找（递归与非递归）第一章：简介（Introduction）1.1算法背景查找问题就是在给定的集合（或者是多重集，它允许多个元 素具有相同的值）中找寻一个给定的值，我们称之为查找键。对于查找问题来说，没有一种算法在任何情况下是都是最优 的。有些算法速度比其他算法快，但是需要较多的存储空间；有 些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性 的问题，但会发生其他的问题（动态查找表）。在数据结构课程中，我们已经学过了几种查找算法，比较 有代表性的有顺序查找（蛮力查找），二分查找（采用分治技术）， 哈希查找（理论上来讲是最好的查找方法）。第二章：算法定义（Al

4、gorithm Specification）2.1数据结构三种查找都是以整形数组作为主要的数据结构，如Int an。我 们主要测试的是算法的性能，并不是仅仅对算法的查找，以数组作为 主要的数据结构能满足实验的要求。2.2顺序查找法的伪代码算法：顺序查找法目的：在给定的集合（或者是多重集，允许多个元素具有相同的 值）中找寻一个给定的值。前提：给定一给定一个集合（或多重集）（A1、A2、A3、A4.An）。返回：寻找出给定值。伪代码如下：int SeqSearch1（int r , int n, int k） /数组 r1 rn 存放查找集合，n是数组中元素的个数（即查找表的长度），k是要查 找的

5、元素i=n;/从后往前把表中的元素与要查找的元素进行比较while （i0 & ri!=k）i-;return i;/i的值为0则没找到，为非0则i为要查找元 素的位置2.3二分查找（递归）法的伪代码算法：二分查找（递归）法目的：在给定的集合（或者是多重集，允许多个元素具有相同 的值）中找寻一个给定的值。前提:给定一给定一个集合（或多重集）（A1、A2、A3、A4.An）。返回：寻找出给定值。伪代码如下：int search(int a,int n,int k)/查找表放在数组 a 中，n 是 查找表中元素的个数，k是待查找的元素Low=0,High=n-1;/选择查找的最大的范围Mid=(L

6、ow+High)/2;if (Low=High)|(n=-1) return -1;/数字-1 表示没有结果else if (aMid=k) return Mid; /找到要查找的元素else if (aMidg)return (search(a,Mid-1,g);/需要在左边的更小的范围内查 找elsereturn (search(a+Mid+1,n-Mid,g);/在右边的更大的范围内 查找2.4二分查找(非递归)法的伪代码算法：二分查找(非递归)法目的：在给定的集合(或者是多重集，允许多个元素具有相同的 值)中找寻一个给定的值。前提：给定一给定一个集合(或多重集)(A1、A2、A3、A4

7、.An)。返回：寻找出给定值。伪代码如下：int BinarySearch(int a,int n,int k) /查找表放在数组 a 中，n是查找表中元素的个数，k是待查找的元素。Low=0;high=n-1; /置区间初值while(lowai)low=middle+1;/在后半区间查找elsehigh二middle-1;/在前半区间查找return 0;/查找失败第三章：测试结果（Testing Results）3.1测试案例表实验项目二 各种查找算法的性能测试（数据数多少不同时用时）数据3080200200010000顺序查找0000.00150.002二分查找（递归）00000.00

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

9、顺序查找 二分查找（递归）二分查找（非递在实验过程中我们在同规模5000的情况下把key值取了 10、25、 120、477、5000；取逼些值是想看看在查找值不一的情况下所用时间 的不同。经过实验发现无论key取值多少三种查找时间依旧相同。实验中我们所预期的结果是：输入不同的规模，根据随机数的产 生，三种查找方法都会出现相应的时间。可是，实验过程中，随机数 的原因，很多次测量都是0，就只有极少数的情况下会出现时间，而 且出现的时间都很小，都是0.001或者0.002。第四章：分析和讨论4.1顺序查找4.1.1基本原理从表的一端向另一端逐个进行记录的关键字和给定值(要查找 的元素)的比较，若某

10、个记录的关键字和给定值比较相等，则查找成 功，找到所查找记录；反之，若直至第一个记录，其关键字和给定值 比较都不等，则表明表中没有所查记录，查找不成功。4.2.2时间复杂度分析由于顺序查找是从表的一端向另一端逐个进行记录的关键字和 给定值的比较，对于n个元素的表，不成功的比较次数为n，查找成 功：最好的情况为1次，最差的情况为n次，所以查找成功时的平均 查找长度为(n+1)/2，且顺序查找的时间复杂度为O(n)。4.2.3优缺点与其他查找算法相比，其缺点是平均查找长度较大，特别是当 n较大时，查找效率低，但他有个很大的优点是算法简单且适应面广， 它对表的结构无任何要求，无论记录是否按关键字有序

11、均可应用。4.2.4该进的方法自然语言描述：当没有超出范围并且没有我到就要继续查找设置变量0, result没找到/ ffiuAn1F1ra,N1 j枚举算法的一个案例可以用“我钥匙”问题为模型 循环结构嵌套分支结构4.2二分查找（递归与非递归）4.2.1基本原理二分查找又称折半查找，二分查找首先要求待查找的表是有序表， 如果要查找的元素是表的中间的那个元素，则找到要查找的元素，查 找成功；如果要查找的元素比中间的那个元素小则使用相同的策略只 在左边的区间查找就可以；如果要查找的元素比中间的那个元素大， 则使用相同的策略在右边的区间进行查找；每次将待查找的元素的所 在区间缩小一半。4.2.2时

12、间复杂度分析二分查找的时间复杂度是O（log（n），最好的情况是指针mid指的 第一个数就是要找的值，最坏的情况的所找的值是第一个或最后一个 数，最坏情况下的时间复杂度是O （n）。4.2.3优缺点查找的效率较高，但是只适用于有序表，且限于顺序存储结构，对 线性链表无法有效的进行查找，还有二分查找在一些特殊情况下，其 查找效率很低，如查找元素是数列中的第一个元素和最后一个元素。4.2.4改进的方法改进后的二分查找算法思路：若k不等于amid，则同时改变 low和high的值，使下一次的啊low与k之间的距离尽可能等于k 与ahigh之间的距离，为下一次的二分查找k成功提供最大的可能。 伪代码如

13、下：（1）low=0 ； high=n-1（2）Index=1（3）Mid=（high+low）/2（4）While （ low=high and index=-1）（5）If kamid(9) Low=mid+1(10) High=low+2*pos2(11) Else index=mid(12)(12) Return index注:任意两个元素ai与 aj之间的距离为pos, pos1为k与ahigh之 间的距离，pos2为k与alow之间的距离。附录：源代码(基于C语言的)#include stdio.h#include stdlib.h#include time.h/*顺序查找*/in

14、t SeqSearch(int a , int n, int key) /数组 a1 an存放查找集合，n 是数组中元素的个数(即查找表的长度)，key是要查找的元素int i;/定义了一个整形变量ii=n; 从后往前把表中的元素与要查找的元素进行比较while (i0 & ai!=key)/*当i大于0并且目前找到的元素和要找的元素不相等，则执行下一条语句*/i-;return i;/i的值为0则没找到，为非0则i为要查找元素的位置/*二分查找的递归*/int diguisearch(int a,int n,int key)/数组 a1 an存放查找集合，n 是数组中元 素的个数(即查找表的

15、长度)，key是要查找的元素int High,Low,Mid;/定义了整形变量 High,Low,MidLow=0,High=n-1;/选择查找的最大的范围Mid=(Low+High)/2;if (Low=High)|(n=-1) return -1;/ 数字-1 表示没有结果else if (aMid=key) return Mid; 找到要查找的元素else if (aMidkey)return (diguisearch(a,Mid-1,key);/需要在左边的更小的范围内查找elsereturn (diguisearch(a+Mid+1,n-Mid,key);/在 右边的更大的范围内查找

16、二分法非递归int feidiguisearch(int a,int n,int key)/*数组 a1 an存放查找集合，n 是数组中元素的个数(即查找表的长度)，key是要查找的元素*/int mid; 定义了一个整形变量midint low=0;/定义了一个整形变量low,并且赋值为0int high=n-1;/选择查找的最大的范围while(lowvhigh)mid=(low+high)/2;if (key=amid)/如果数组的中间元素和要查找的元素相等return mid; 查找成功else if (keyamid)low=mid+1;/在后半区间查找elsehigh=mid-1;

17、/在前半区间查找return -1;/查找失败void main()int n=200; /定义一个变量 n，n=200int a200; /定义一个数组a，数组里数的个数是200int key=59;srand(unsigned)time(NULL); /*初始化随机函数种子，逼句是拿系统时间作为种子，由于时间是变化的，种子变化，可以产生不相同的随机数*/for(int i=0;ivn;i+)/初始化变量i的值为0，当i=0时执行循环，在每次循环后i执 行加1操作ai=rand()%100; /随机数的取值从0到100之间/*for(int b=0;bvn;b+)printf(%d ,ab)

18、;*/clock_t start,end; 声明时间变量double duration; 声明用于记录时间的变量start=clock();/开始记录时间SeqSearch(a,n,key);/计算直接查找规模为n的时候用的时间printf(%d,key);/输出要查找的元素，即keyend=clock();/停止记录时间duration=(double)(end-start)/CLOCKS_PER_SEC; / 求时间差并把时间差记录在 duration 中printf(nthe SeqSearch time is=%f secondsn”,duration); /输出时间差，也就是计算 所

19、用的时间start=clock();/开始记录时间diguisearch(a,n,key); /计算二分递归查找规模为n的时候用的时间printf(%d,key);/输出要查找的元素，即keyend=clock();/停止记录时间duration=(double)(end-start)/CLOCKS_PER_SEC;/ 求时间差并把时间差记录在duration 中printf(nthe diguisearch time is=%f secondsn”,duration); /输出时间差，也就是计算所用的时间start=clock();/开始记录时间feidiguisearch(a,n,key);/计算二分非递归查找规模为n的时候用的时间printf(%d,key);/输出要查找的元素，即keyend=clock();/停止记录时间duration=(double)(end-start)/CLOCKS_PER_SEC;/ 求时间差并把时间差记录在duration 中printf(nthe feidiguisearch time is=%f secondsn”,duration); /输出时间差，也就是计算所用的时间system(pause); /j 结束程序运行