舍伍德算法

概率算法

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

基本思想

设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得 tA(x)远远大于tA(n)的可能性。

希望获得一个概率算法B，使得对问题的输入规模为n的每一个实例均有

这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。

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

线性表的组织

在现实世界中，线性表的例子枚不胜举，如一幅扑克牌的点数(2,3,4，…,J，Q，K，A)可构成一个线性表；数据库表中的记录也可以构成一个线性表，只不过是该线性表中的数据元索稍复杂一点罢了。正因为线性表如此重要，ANSl和ISO于1998年制定的STL(Standard Template Library)中提供了对线性表的支持。STL的容器是用来放置各种类型的对象，其中每一个容器类就是计算机的一个基本数据结构。STL有以下7个最基本的容器类：向量(Vector)，列表(List)，双端队列(Deque)，集合(Set)，多重集合(Multiset)，映像(Map)，多重映像(Multimap)等。

线性表的存储有两种方式：顺序存储和链式存储。从空间的角度看，链式存储的存储密度低，因为它需要存储附加的指针域的数据。而顺序存储不需要存储附加信息，因而存储效率比较高；从时间角度来看，由于顺序存储的逻辑顺序与物理顺序一致，其存储可采用其索引号来加以存取，因此是一种随机存取结构，表中的任意一个结点都可在O(1)的时间内直接存取，但是在表中插入和删除元素时需移动大量的元素，该结构适合经常进行查找，很少做插入和删除运算操作的场台。而链式存储与它恰恰相反，插入和删除不需要移动元素，只需要修改指针即可，但其查找的时间复杂度却为O(n)．在STL中容器类中的Vector类采用顺序存储，List类采用链式存储。后面的程序测试就是采用这两个类来进行的。

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

数组实现链表

在不包含指针的程序设计语言如VB中，可以采用数组来实现链表，实现了“虚假”的指针操作。但就是这种“虚假”指针，恰恰不仅弥补某些指针的某些缺结，还发挥了这种“虚假”指针的优点。采用这种数据结构，抛弃了顺序存储在插入运算中需要移动大量元素的缺点。采用这种数据结构，利用,舍伍德算法进行查找、插入和删除操作，其效率在传统的顺序存储和链式存储之间。

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

m_pData和m_pLink来表示所给的含有多个元素的有序集。用m_pData存储有序链表的数据，用m_pLink存储有序链表的数据元索的直接后继的指针(在数组中的索引号)。m_pLink[O]指向有序链表的第一个元素，换句话说，m_pData[m_plink[0]]是有序链表中的最小元素。一般来说，如果m_pData[i]是有序链表中的第k个元素，则m_pData[m_plink[i]]是有序链表中的第k+1个元素。有序链表的有序性表现在：对于任意的I≤i≤n，有m_pData[i]≤m_pData[m_plink[i]]。有序链表中的最大元素m_pData[k]有m_plink[k]-O(无后继，指向第零个结点，第零个结点是监视哨)且m_pDaIa[0]为一个大数。

倘若采用顺序搜索的方式在这种有序链表中查找指定的元素，每次查找与有序链表建立的顺序有关，此时采用舍伍德算法可以消除这种联系。

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

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

算法介绍

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

template＜classType＞

boolCOrderlist＜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)；//是否找到

}

程序测试

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

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

总结

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省