各种查找算法的性能测试各种查找算法的性能测试.doc

 目录 第一章：简介 1 第二章：算法规范 2 数据结构 2 伪代码 3 第三章：算法测试 4 顺序查找结果 4 二分查找结果 5 第四章：分析讨论 6 算法分析 6 时间复杂度分析 6 附录 7 声明 7 ：简介 问题的描述： 查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。 对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性的问题，但会发生其他的问题（动态查找表）。 在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找），二分查找 （递归，非递归）。 利用随机函数产生N个随机整数，利用顺序查找，二分法查找（递归，非递归），并统计每一种查找所消耗的时间。把查找花的时间排在表格里面。 第二章:算法规范 数据结构： 在所有的查找策略中，我们用了数组，函数作为主要的数据结构。 因为我们只是测试了不查找所需要的时间，也即分析了顺序查找,二分法查找（递归，非递归）的性能，没涉及其他复杂的操作，所以在这个项目中用了静态实现数组就可以。 伪代码如下所示 顺序查找： 1. int SeqSearch1(int r[ ], int n, int k) 3.1．while (i0 r[i]!=k)； 3.2．循环 i--； 3.3．返回是否找到要查找的元素k； 二分法查找： 递归 int search(int a[],int n,int k) Low=0,High=n-1; Mid=(Low+High)/2; if ((Low=High)||(n==-1)) return -1 1.21 else if (a[Mid]==k) return Mid; 1.22 else if (a[Mid]g) return (search(a,Mid-1,g)) return (search(a+Mid+1,n-Mid,g)); 非递归 1 int BinarySearch (int a[],int n,int k) 1.1 Low=0; high=n-1; 1.2 while(lowhigh) 1.21 mid=(low+high)/2; 1.22 if (key==a[mid]) 1.23 return mid查找到元素 1.3 if (keya[i]) 1.31 low=middle+1 1.32 high=middle-1 1.4 return查找失败 第三章：测试结果 测试结果：请选择查找方式 顺序查找： 二分查找： 第四章：分析和讨论 （一）算法思想分析： 1．顺序查找：从表的一端向另一端逐个进行记录的关键字和给定值（要查找的元素）的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查找记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。 2．二分查找：二分查找又称折半查找，二分查找首先要求待查找的表是有序表，如果要查找的元素是表的中间的那个元素，则找到要查找的元素，查找成功；如果要查找的元素比中间的那个元素小则使用相同的策略只在左边的区间查找就可以；如果要查找的元素比中间的那个元素大，则使用相同的策略在右边的区间进行查找；每次将待查找的元素的所在区间缩小一半. 分析：顺序查找平均长度为（n+1）/2 二分法查找平均长度为log2(n+1)-1 （二）时间复杂度分析 查找方法 时间复杂度 顺序查找 O(n) 二分法查找 O (logn) 附录：源代码（基于c语言） #include stdio.h #include math.h #include stdlib.h #includetime.h #define N 40 #define k 1869 void main() { void ChooseSort(int a[],int n); int SeqSearch1(int a[ ], int n, int key);//顺序查找// int BinSearch2(int Array[],int SizeOfArray,int key/*要找的值*/); int BinSearch1(int Array[],int low,int high,int key);//非递归查找// int a[N],i; for(i=1;i=N;i++) {