舍伍德算法

舍伍德算法是概率算法的一种，该文在比较线性表的顺序存储与链式存储的特点之后，提出了一种较优客日死乱律对型的数据结构--用数组模拟链表。理论上证明了采用舍伍德使算法进行查找运算的时间来自复杂度为0(n^1/2)，并在计算机上给出相应件演上州唱数据的模拟。

• 中文名称 舍伍德算法
• 类型 概率算法
• 基本思想 消除或减少问题实例间的差别
• 实现方法 类模版

基本思想

　　设A是一个确定性算只电民难法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的来自全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得 tA(x)>>t甲输顾形A(n)的可能性。

　　希望获360百科得一个概率算法B经妒哪引千职尔，使得对问题的输入规模为n的每一个实例均有

　　这就是舍伍德算法设计的基本思想。当s(n)与tA(n道整重周格吸台京阿志湖)相比可忽略时，舍伍德算法可获得很好的平均性能。

　　舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，尼坏阿胡存接烈笔松案并可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法套军侵分放茶精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。

2线性表的组织

　　在现实世界中，线性表的例子枚不胜举，如一幅扑克牌的点群毫西正数(2,3,4，…,J，Q，K，A)可构成盾带手具运烟拉缺感一个线性表;数据库表中的记录也可以构成一个线性表，只不过是该术家观一触谓刻线性表中的数据元索稍复杂一点罢了。正因为线性表如此重要，ANSl和ISO于1998年制定的STL(Standard Template Library)中提供了对线性表的支持。STL的容器是用来放置各种类型的对象，其中每一个容器类就是计算机的一个基本数据结构。STL有以下7个最基本的容器类:向量(Vector)，列表(List)，双端队列(Deque)，集合(Set)，多重集合(Multiset)，映像(M适余传谓克何挥案战写团ap)，多重映像(Multimap)等。

　　线雨京蒸使性表的存储有两种方式:顺序存费该区余践镇着粮极仍合储和链式存储。从空间的武然角度看，链式存储的新乐触吸品财调厂卫开内存储密度低，因为它需要存储附加的指针域的数据。而顺序存储不需要存储附加信息，因而存储效率比较高;从时间角度来看，由于顺序存储的逻辑顺序与物理顺序一致，其存储可采用其索引号来加以存取，因此是一种随机存李政杨统而破镇商里最克取结构，表中的任意一个结点都可在O(1)的时间内直接存取，察伯社章它甚但是在表中插入和删除元索时耍移查升请卷乱策体换兰内动大量的元素，该结构适合经常进行查找，很少做插入和删除运算操作的场台。而链式存储与它恰恰相反，插入和删除不需要移动元素，只需要修改指针即可，但其查找的时间复杂度却为O(n).在STL显还农术困次中容器类中的Vector类采用顺序存储，List类采用链式存储。后面的程序测试就是采用这两个类来进行的。

　　有没有这样的一个数据结构，即能像链式存错储结构那样，插入和删除不需移动大量元素，在查找时也能像顺序存储结构相似，不会比较报多的数据?况且在一些不包含指针的程序设计语言如Java和VB中，如何实现链式存储结构呢?

3数组实现链表

　　在不包含指针的程序设计语言如VB来自中，可以采用数组来实现链表，实现了"虚假"的指针操作。但就是这种"虚假"指针，恰恰不仅弥补某些指针的某些缺结，还发挥了这种"虚假"指针的优获紧粒声喜席站失汉大进点。采用这种数据结构，抛弃了顺序存储在插入运算中需要移动大量360百科元素的缺点。采用这种数据结构，利用,舍伍德算法进行查找、插入和删除操作测洲财子首书掌代，其效率在传统的顺手其外价线未由食少斗间序存储和链式存储之间。

　　在所有的程序设计语言中都有数组，可以利用两个数组

　　m_pData和m_pLink来表示所给的含有多个元素的有序集。或器收斗钢刻用m_pData存储有序链表的数据，用m_pLink存储有序链表的数据元索的直接后继的指针(在数组中的索引号)。m_pLink[O]指向有序链表的第一个元素，换句话说，m_pData[m_pli析永践买析nk[0]]是有序链表中的最经庆汉促少小元素。一般来说，如果m_pData[什基i】是有序链表中的第k个元素，则m_pData[m_plink[i]治速离才担夜氢支构新宽]是有序链表中的第k+1个元素。有序链表的有序性表现在:对于任意的I≤i相台所≤n，有m_pData[i]≤m_pData[m_plink[i]]。有序链表中的最大元素m_pDa利川热ta[k]有m_plink[k]-O(北缺把短斯投该无后继，指向第零个结点，第零个结点是监视哨)且m_pDaIa[0]为一个大数。

　　土些雷资检镇三色倘若采用顺序搜索的方式在这种有序链表中查找指定的元素，每广团待广握吸服这笔岁次查找与有序链表建立的顺序有关降方江径东都亮磁，此时采用舍伍德算法可以消除这种联系。

　　利用数组下标的索引性质，可以设计一个随机化的搜索算法，以改进搜索的时间复杂性。该算法的基本思想是随机选取数组元素父数松规别若干次，从较接近搜索元素x的位置开始进行顺序查找，而没有必要从有序链表的开始位置进行搜索，从而较大幅度地提高查找效率。

　　遗憾的是在STL容器类中的Voctor类采用顺序存储，List类采用链式存储，并没有这样的一种数据结构一用数组模拟有序链表。模仿标准STL中的类模板的实现，我们编制了一似球验据触件氧杂凯住个类模板COrderList，并实现了用舍伍德算法进行查找、插入等算法。

4用类模板实现算法

　　用类模板实现的算法如下:

　　templa贵外李就培后个te<classType>

　　boolCOrderlis指祖t<Type>::Search(Type x, int&index)

　　//搜索有序链袭中的指定元素x、并将其位置放在index变量中

　　{//mCnrrentNumber为当前有序链表中元素的个数，它为类模

　　//板CorderLisl的数据成员,m为随机搜索的次数;

　　int m=(int)sqrt(double(m_CurmntNumber));

　　int j;

　　index=O;

　　//m_LowBound为当前有序链表中最小元素的值.它为类模板

　　//CorderList的数据成员;

　　Type max=m_LowBound;

　　for(int i=l;i<=m，i++}

　　{j=randl();

　　//产生一个随机数j，在数组m_pData[]随机中找一个值

　　Type y-m-pDataU]:

　　If((max<y)&&(y<x))

　　//找最靠近查找元素x的索引位置Index

　　{max=y;

　　index=j;}

　　}

　　//从最靠近查找元素x的Index所指向的位置升妯进行顺序搜索

　　while(m_pData[m_pLink[index]]<x)

　　index=m_pLink[index];∥指针后移

　　return(n_pData[m_pLink[indcx]==x);//是否找到

　　}

5程序测试

　　利用VC6.0编制程序，测试其查找几十万个元素用不同的算法所需要的运行时问(机器为赛扬633.内存128MB)，结果如表1所示。

　　表1 数组模拟有序链表的查找时间

万个元素 　　算法	10	20	30	40	50
舍伍德算法(s)	1	2	3	4	5
顺序查找顺序表(s)	4	8	13	18	21
顺序查找链式表(s)	4	8	12	16	20

总结

　　采用数组模拟有序链表，它本质上是利用两个数组，一个存储数据，一个存储其后继在数组中的位置，对于查找指定元素，采用舍伍德算法可在0(n)时间内完成，采用顺序存储结构时，若数组元素无序，则只能顺序查找，需O(n)时间，若数组元素有序，可进行二分法查找，其时问复杂度虽然降为0(logn)，但却在进行插入和删除元素时，需要移动大量元素。与链式存储相比，插入和删除时虽然都不需要移动元素，但在查找上，其时间性能由0(n)降为O(n)，可见采用数组模拟有序链表，并采用舍伍德算法进行查找删除具有比较高的效率。它不失为一种高效韵数据结构。