各种查找算法的性能比较测试(顺序查找、二分查找).doc
算法设计与分析各种查找算法的性能测试目录摘要4第一章：简介（Introduction）51.1 算法背景5第二章：算法定义（Algorithm Specification）52.1 数据结构52.2顺序查找法的伪代码62.3 二分查找（递归）法的伪代码62.4 二分查找（非递归）法的伪代码7第三章：测试结果（Testing Results）93.1 测试案例表93.2 散点图10第四章：分析和讨论124.1 顺序查找124.1.1 基本原理124.2.2 时间复杂度分析124.2.3优缺点124.2.4该进的方法134.2 二分查找（递归与非递归）134.2.1 基本原理134.2.2 时间复杂度分析144.2.3优缺点144.2.4 改进的方法14附录：源代码（基于C语言的）16声明18摘要在计算机许多应用领域中，查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的查找次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。关键字：顺序查找、二分查找（递归与非递归）第一章：简介（Introduction） 1.1 算法背景 查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。 对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性的问题，但会发生其他的问题（动态查找表）。 在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找），二分查找 （采用分治技术），哈希查找（理论上来讲是最好的查找方法）。 第二章：算法定义（Algorithm Specification）2.1 数据结构三种查找都是以整形数组作为主要的数据结构，如Int an。我们主要测试的是算法的性能，并不是仅仅对算法的查找，以数组作为主要的数据结构能满足实验的要求。2.2顺序查找法的伪代码 算法：顺序查找法目的：在给定的集合（或者是多重集，允许多个元素具有相同的值）中找寻一个给定的值。前提：给定一给定一个集合（或多重集）（A1、A2、A3、A4.An）。返回：寻找出给定值。伪代码如下： int SeqSearch1(int r , int n, int k) /数组r1 rn存放查找集合，n是数组中元素的个数（即查找表的长度），k是要查找的元素 i=n;/从后往前把表中的元素与要查找的元素进行比较 while (i>0 && 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=(Low+High)/2; if (Low>=High)|(n=-1) return -1;/数字-1表示没有结果else if (aMid=k) return Mid; /找到要查找的元素 else if (aMid>g) return (search(a,Mid-1,g);/需要在左边的更小的范围内查找 elsereturn (search(a+Mid+1,n-Mid,g);/在右边的更大的范围内查找 2.4 二分查找（非递归）法的伪代码 算法：二分查找（非递归）法目的：在给定的集合（或者是多重集，允许多个元素具有相同的值）中找寻一个给定的值。前提：给定一给定一个集合（或多重集）（A1、A2、A3、A4.An）。返回：寻找出给定值。伪代码如下：int BinarySearch(int a,int n,int k) /查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素。 Low=0; high=n-1; /置区间初值while(low<high) mid=(low+high)/2; if (key=amid) return mid;/查找成功elseif (key>ai) low=middle+1;/在后半区间查找 elsehigh=middle-1;/在前半区间查找 return 0;/查找失败第三章：测试结果（Testing Results）3.1 测试案例表实验项目二 各种查找算法的性能测试（数据数多少不同时用时）数据N排序3080200200010000顺序查找0000.00150.002二分查找（递归）00000.001二分查找（非递归）00000实验项目二 各种查找算法的性能测试（查找值不同时用时）数据K排序10251204775000顺序查找00000二分查找（递归）00000二分查找（非递归）000003.2 散点图 在测试过程中n的值取了30、80、200、2000、10000；取这些值是因为我想测试在随机数多少不一的情况下所用时间的区别。经过实验发现查找过程中三种查找方法都很迅速，但当数字增大时还是有些差别，顺序查找用时最多。 在实验过程中我们在同规模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该进的方法4.2 二分查找（递归与非递归）4.2.1 基本原理二分查找又称折半查找，二分查找首先要求待查找的表是有序表，如果要查找的元素是表的中间的那个元素，则找到要查找的元素，查找成功；如果要查找的元素比中间的那个元素小则使用相同的策略只在左边的区间查找就可以；如果要查找的元素比中间的那个元素大，则使用相同的策略在右边的区间进行查找；每次将待查找的元素的所在区间缩小一半。4.2.2 时间复杂度分析 二分查找的时间复杂度是O(log(n)，最好的情况是指针mid指的第一个数就是要找的值，最坏的情况的所找的值是第一个或最后一个数，最坏情况下的时间复杂度是O(n)。4.2.3优缺点 查找的效率较高，但是只适用于有序表，且限于顺序存储结构，对线性链表无法有效的进行查找，还有二分查找在一些特殊情况下,其查找效率很低,如查找元素是数列中的第一个元素和最后一个元素。4.2.4 改进的方法改进后的二分查找算法思路：若k不等于amid，则同时改变low和high的值，使下一次的啊low与k之间的距离尽可能等于k与ahigh之间的距离，为下一次的二分查找k成功提供最大的可能。伪代码如下：（1） low=0；high=n-1（2） Index=1（3） Mid=(high+low)/2（4） While ( low<=high and index=-1)（5） If k<mid（6） high=mid-1（7） Low=high-2*pos1（8） Else if x>amid（9） Low=mid+1（10） High=low+2*pos2（11） Else index=mid（12） Return index注:任意两个元素ai与aj之间的距离为pos，pos1为k与ahigh之间的距离，pos2为k与alow之间的距离。附录：源代码（基于C语言的）#include "stdio.h"#include "stdlib.h"#include "time.h" /*顺序查找*/ int SeqSearch(int a , int n, int key) /数组a1 an存放查找集合，n是数组中元素的个数（即查找表的长度），key是要查找的元素 int i;/定义了一个整形变量i i=n;/从后往前把表中的元素与要查找的元素进行比较 while (i>0 && ai!=key)/*当i大于0并且目前找到的元素和要找的元素不相等，则执行下一条语句*/ i-; return i;/i的值为0则没找到，为非0则i为要查找元素的位置 /*二分查找的递归*/ int diguisearch(int a,int n,int key)/数组a1 an存放查找集合，n是数组中元素的个数（即查找表的长度），key是要查找的元素 int High,Low,Mid;/定义了整形变量High,Low,Mid Low=0,High=n-1;/选择查找的最大的范围 Mid=(Low+High)/2; if (Low>=High)|(n=-1) return -1;/数字-1表示没有结果 else if (aMid=key) return Mid; /找到要查找的元素 else if (aMid>key) return (diguisearch(a,Mid-1,key);/需要在左边的更小的范围内查找 else return (diguisearch(a+Mid+1,n-Mid,key);/在右边的更大的范围内查找 /二分法非递归 int feidiguisearch(int a,int n,int key)/*数组a1 an存放查找集合，n是数组中元素的个数（即查找表的长度），key是要查找的元素*/ int mid;/定义了一个整形变量midint low=0;/定义了一个整形变量low,并且赋值为0int high=n-1;/选择查找的最大的范围 while(low<high) mid=(low+high)/2; if (key=amid)/如果数组的中间元素和要查找的元素相等 return mid;/查找成功 else if (key>amid) low=mid+1;/在后半区间查找 else high=mid-1;/在前半区间查找 return -1;/查找失败void main() int n=200; /定义一个变量n，n=200 int a200; /定义一个数组a，数组里数的个数是200 int key=59; srand(unsigned)time(NULL); /*初始化随机函数种子，這句是拿系统时间作为种子，由于时间是变化的，种子变化，可以产生不相同的随机数*/ for(int i=0;i<n;i+)/初始化变量i的值为0，当i=0时执行循环，在每次循环后i执行加1操作 ai=rand()%100; /随机数的取值从0到100之间 /*for(int b=0;b<n;b+) printf("%d ",ab); */ clock_t start,end; /声明时间变量 double duration; /声明用于记录时间的变量 start=clock();/开始记录时间 SeqSearch(a,n,key);/计算直接查找规模为n的时候用的时间 printf("%d",key);/输出要查找的元素，即key end=clock();/停止记录时间 duration=(double)(end-start)/CLOCKS_PER_SEC; /求时间差并把时间差记录在 duration中 printf("nthe SeqSearch time is=%f secondsn",duration); /输出时间差，也就是计算所用的时间 start=clock();/开始记录时间 diguisearch(a,n,key); /计算二分递归查找规模为n的时候用的时间 printf("%d",key);/输出要查找的元素，即key end=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);/输出要查找的元素，即key end=clock();/停止记录时间 duration=(double)(end-start)/CLOCKS_PER_SEC;/求时间差并把时间差记录在duration中 printf("nthe feidiguisearch time is=%f secondsn",duration); /输出时间差，也就是计算所用的时间 system("pause"); /j结束程序运行
