《各种查找算法的性能分析》由会员分享，可在线阅读，更多相关《各种查找算法的性能分析（13页珍藏版）》请在金锄头文库上搜索。
1、项目名称：各种查找算法的性能测试项目成员：组编号：完成时间：目录前言 .2 正文 .2 第一章 简介 .2 1.1顺序查找问题描述.2 1.2 二分查找问题描述 .2 第二章 算法定义 .2 2.1 顺序查找算法定义.2 2.2 二分查找算法定义.3 第三章测试结果（ Testing Results).53.1 实验结果表.5 3.2 散点图记录.5 第四章 分析和讨论 .64.1 顺序查找分析.6 4.2 二分查找分析 .6 附录：源代码（基于C语言的 ).7声明 . 13 前言查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的 值，我们称之为查找键。 对于
2、查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快， 但是需要较多的存储空间； 有些算法速度非常快， 但仅适用于有序数组。 查找问题没有稳定性的问题， 但会发生其他的问题（动态查找表） 。 在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找）， 二分查找（采用分治技术），哈希查找（理论上来讲是最好的查找方法）。第一章：简介（ Introduction）1.1 顺序查找问题描述：顺序查找从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和
3、给定值比较都不等，则表明表中没有所查记录，查找不成功。1.2 二分查找问题描述：（1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。（2）编写程序实现：在保存于数组ai有序数据元素中查找数据元素k 是否存在。数元素k 要包含两种情况： 一种是数据元素k 包含在数组中； 另一种是数据元素k 不包含在数组中（3） 数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。（4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。第二章：算法定义（Algorithm Specification）2.1 顺序查找从表的一端向另一端逐个进
4、行记录的关键字和给定值（要查找的元素）的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查找记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。顺序查找的算法如下：int SeqSearch1(int r , int n, int k) /数组 r1 rn 存放查找集合， n 是数组中元素的个数（即查找表的长度） ，k 是要查找的元素 i=n;/ 从后往前把表中的元素与要查找的元素进行比较while (i0 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+H
6、igh)/2; /quicksort(a,0,SIZE-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);/在右边的更大的范围内查找 （2）二分查找的非递归算法int binary_search_1 (int a,int n,int k) /非递归的二分查找算法的
7、伪代码：查找表放在数组a 中，n是查找表中元素的个数，k 是待查找的元素 int Low,High,i,mid; Low=0; High=n-1; while(Lowamid) Low=mid+1;/ 在后半区间查找else High=mid-1;/ 在前半区间查找 return 0;/ 查找失败第三章：测试结果（Testing Results）3.1 实验结果表：查找算法随机数组元素个数（个）查找时间（seconds）顺序查找2 0.022000 4 0.047000 6 0.062000 8 0.082000 10 0.100000 二分查找2 0.190000 4 0.390000 6
8、0.390000 8 0.060000 10 0.0600003.2 散点图：注释：横轴为数组元素个数，纵轴为(查找时间 /1000)。第四章：分析和讨论4.1.实现顺序查找算法：（1）顺序查找算法思路很简单，就是一种遍历的思想，一个个查找目标元素，实现也很简单。（2）对于有 n 个元素的表适用顺序查找。比较次数：不成功：比较n 次。成功查找：最好的情况为1 次 ， 即 第 一个 元素 即为 目标 元素 ；最 差 的 情 况 为 n 次； 平均 比 较 次 数（ n+1 ） /2 次 。所以当表很大时，顺序查找的代价是很大的。（3）顺序查找算法不会有重复的比较出现，即一旦找到即成功，但同时这种
9、代价是当表中有重复的目标元素时（比如有多个目标元素）我们只能得到第一个元素的位置。顺序查找算法时间复杂度为O(n) 。4.2 实现二分查找算法：（1）二分查找法思路：递增排列的表，首先从中间元素开始查找，如果元素比目标元素小，则查找后半部分表，反之查找前半部分表，并重复这一过程。这样每次查找中我们都把表的长度减半。（2）二分查找在实现中有量Low 和 High，每次减半的过程体现在Low 和 High 的改变上，在代码的实现上可以使用单纯的循环或者用函数递归的思想。递归思想更容易理解， 但编写之后我们发现函数是尾递归，尾递归通常可以用简单的循环实现，循环在操作来说没有了函数调用的过程，更节省时
10、间和空间。（3）编码中小小地方的改动可能对程序有很大的改观。如上述两种二分查找非递归binary_search_1 （不比较等于的情况）递归binary_search_2 （添加等于情况）折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始， 如果中间元素正好是要查找的元素，则搜素过程结束； 如果某一特定元素大于或者小于中间元素， 则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。 如果在某一步骤数组为空， 则代表找不到。 这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度： 二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(lgn) 或 O(n)。（n 代表集合中元素的个数）空间复杂度： 虽以递归形式定义，但是尾递归，可改写为循环, 所以空间复杂度为 O(n)=O(lgn)。附录：源代码（基于C语言的）#include “stdio.h“ #include “time.h“ #include “stdlib.h“ #define SIZE 1000/ 待排数的规模#define PRT_RT 1/ 是否显示排序前后的数组情况，对较大规模的数组不显示/0 为不显示， 1 为显示/顺序查找算法i
