各种查找算法的性能比较测试(顺序查找、二分查找)各种查找算法的性能比较测试(顺序查找、二分查找).doc

算法设计与分析 各种查找算法的性能测试 目录 摘要 4 第一章：简介（Introduction） 5 1.1 算法背景 5 第二章：算法定义（Algorithm Specification） 5 2.1 数据结构 5 2.2顺序查找法的伪代码 6 2.3 二分查找（递归）法的伪代码 6 2.4 二分查找（非递归）法的伪代码 7 第三章：测试结果（Testing Results） 9 3.1 测试案例表 9 3.2 散点图 10 第四章：分析和讨论 12 4.1 顺序查找 12 4.1.1 基本原理 12 4.2.2 时间复杂度分析 12 4.2.3优缺点 12 4.2.4该进的方法 13 4.2 二分查找（递归与非递归） 13 4.2.1 基本原理 13 4.2.2 时间复杂度分析 14 4.2.3优缺点 14 4.2.4 改进的方法 14 附录：源代码（基于C语言的） 16 声明 18 摘要 在计算机许多应用领域中，查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。 我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的查找次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。 关键字：顺序查找、二分查找（递归与非递归） 第一章：简介（Introduction） 1.1 算法背景 查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。 对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性的问题，但会发生其他的问题（动态查找表）。 在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找），二分查找 （采用分治技术），哈希查找（理论上来讲是最好的查找方法）。 第二章：算法定义（Algorithm Specification） 2.1 数据结构 三种查找都是以整形数组作为主要的数据结构，如Int a[n]。我们主要测试的是算法的性能，并不是仅仅对算法的查找，以数组作为主要的数据结构能满足实验的要求。 2.2顺序查找法的伪代码 算法：顺序查找法 目的：在给定的集合（或者是多重集，允许多个元素具有相同的值）中找寻一个给定的值。 前提：给定一给定一个集合（或多重集）（A1、A2、A3、A4.....An）。 返回：寻找出给定值。 伪代码如下： int SeqSearch1(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合，n是数组中元素的个数（即查找表的长度），k是要查找的元素 { i=n;//从后往前把表中的元素与要查找的元素进行比较 while (i0 r[i]!=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 (a[Mid]==k) return Mid; //找到要查找的元素 else if (a[Mid]g) return (search(a,Mid-1,g));//需要在左边的更小的范围内查找 else return (search(a+Mid+1,n-Mid,g));//在右边的更大的范围内查找 } 2.4 二分查找（非递归）法的伪代码 算法：二分