基于系统的查找算法研究

[摘 要]本文分析了查找算法在系统开发中的重要性，通过比较常见的静态查找算法，得出最优的二分法查找，是系统开发过程中查找算法的首选。

[关键词]算法 顺序查找 二分法查找 分块查找

一、系统算法概述

算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

一个算法应该具有以下五个重要的特征： 1.有穷性：一个算法必须保证执行有限步之后结束； 2.确切性：算法的每一步骤必须有确切的定义； 3.输入：一个算法有0个或多个输入，以刻画运算对象的初始情况； 4.输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果;5.可行性：算法原则上能够精确地运行，有限次运算后即可完成。

由此可以看出，一个算法的好坏对于系统能否成功有着决定性的作用。对于任何一个系统设计人员来说，系统算法的设计都是考虑问题的重中之重。因此算法的优良直接影响着系统的使用价值。

二、算法复杂性分析

算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。

不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。

三、查找算法概述

查找是确定数据元素集合中是否存在数据元素等于特定元素或者是否存在元素满足某种给定特征的过程。要进行查找，必须知道待查找对象的特征，也就是要知道待查找数据元素的关键字。一般地，衡量查找算法效率的标准是平均查找长度ASL，也就是为确定某一结点在数据集合中的位置，给定值与集合中的结点关键字所需进行的比较次数。对于具有n个数据元素的集合，查找某元素成功的平均查找长度为：ASL= 其中n是查找表中结点的个数；Ci为查找第i个元素的概率 =1。在分析查找算法的复杂性时，若未特别说明，认为每个结点具有相同的查找概率，即p1=p2..=pn=1/n。查找算法在各类程序中应用非常广泛。查找算法主要有两大类：一类是基于静态查找表上的操作，另一类是基于动态查找表上的操作。本系统主要是基于静态查找表上的操作，其主要使用的查找算法有：顺序查找、二分法查找与分块查找。

1.顺序查找。顺序查找是一种最简单的查找方法。它的基本思想是：从表的一端开始，顺序进行查找，直到找到的结点关键字与给定的Key相等为止，若查找结束后，仍未找到关键字等于Key的结点，则查找失败。顺序查找算法的缺点是查找时间长。其查找成功时的平均查找长度为：

在查找失败时，算法的平均查找长度为：

2.二分法查找。二分法查找又称为折半查找，采用二分法查找可以大大提高查找效率，它要求线性表的结点按其关键字从小到大（或从大到小）按序排列并采用顺序存储结构。二分法查找的基本过程是：设L[low..high]是当前的查找区间，首先让待查找的数据元素同线性表中间结点mid=[(low+high)/2]的关键字相比较，若比较相等，则查找成功并结束二分查找；若待查找的数据元素比中间结点的关键字要小，则在线性表的前半部分L[low...mid-1]进行二分查找；反之，则在线性表的后半部分[mid+1...high]进行二分查找，直到找到满足条件的结点或者确定表中没有这样的结点为止。

二分查找每经过一次比较就将查找范围缩小一半，因此比较次数是log2n这个量级的。不妨设n=2k-1(2的K次方)，容易看出，线性表至多被平分k次即可完成查找。也即，在最坏的情况下，查找算法k=log2（n+1）次即可结束。二分查找的平均查找次数为：

用数学归纳法容易证明：

所以

不论查找成功或失败，二分查找比顺序查找要快的多。

3.分块查找。分块查找又称为索引顺序查找，他是顺序查找算法与二分查找算法的一种结合，其基本思想是：首先把线性表分成若干块，在每块中，结点的存放不一定有序，但块与块之间必须是分块有序的。分块查找方法通过将查找缩小在某个块中从而提高了查找的效率，其查找的效率由两部分组成，一是为确定待查找元素所在块而对索引表查找的平均查找长度E1，二是块内查找所需的平均查找长度Eb。

若以顺序查找来确定分块，则分块查找成功时的平均查找长度为：

ASLids=E1+Eb= =（（n/s）+s）/2 +1

n：总元素个数 ，b：n个元素被分成的块数，则每块中的元素个数就是s=n/b。

若以二分查找来确定分块，则分块查找成功时的平均查找长度为：

ASLids= E1+Eb≈log2(n/s +1)+s/2

由此可见，分块查找比顺序查找要快，但比二分查找要慢。

在最坏的情况下，顺序查找算法和二分查找算法在解决同一个问题时，两个算法所需要检测的分量个数却大不相同，前者要m=2 k个，后者只要k+1个。可见算法二分查找算法比算法顺序查找算法高效得多。

解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。上图是运行这两种算法的时间曲线。该图表明，当m适当大（m>m0）时，二分查找算法（B_Search）比顺序查找算法（Search）省时，而且当m更大时，节省的时间急剧增加。

四、结 论

我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。

参考文献：

[1]郭绍忠.基于GPU的单源最短路径算法的设计与实现.商场现代化，2011,9

[2]李云清.数据结构（C语言版）.人民邮电出版社，2006,8