一、舍伍德(Sherwood)算法

舍伍德算法是概率算法的一种，该文在比较线性表的顺序存储与链式存储的特点之后，提出了一种较优的数据结构——用数组模拟链表。理论上证明了采用舍伍德算法进行查找运算的时间复杂度为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)相比可忽略时，舍伍德算法可获得很好的平均性能。

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

延伸阅读：

二、数值随机化算法

数值随机化算法常用于数值问题的求解，得到的往往是近似解，且近似解的精度随计算时间的增加而不断提高。在许多情况下，要计算出问题的精确解是不可能的或没有必要的，因此用数值随机化算法可以得到相当满意的解。随机数

随机数在随机化算法中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在随机化算法中使用的随机数都是一定程度上随机的，即伪随机数。线性同余法是产生伪随机数最常用的方法。由线性同余法产生的随机序列a1,a2,a3,…,an满足：a0 = d

an = (ban-1 + c)mod m  n = 1,2,…

式中，b>=0，c>=0，d>=m。d称为该随机序列的种子，如何选取该方法中的常数b、c和m直接关系到所称生的随机序列的随机性能，这是随机性能理论研究的内容。从直观上看，m应该取得充分大，因此可取m为机器大数，另应取gcd(m,d)=1，所以d可取为一素数。我们建立一个随机数类RandomNumber，包含一个需由用户初始化的种子randSeed。给定初始种子后，即可产生与之相应的随机序列。种子randSeed是一个无符号整数，可由用户选定也可用系统时间自动产生。函数Random()的输入参数n<=65535是一个无符号整数，返回0~n-1范围内的随机整数。函数fRandom()返回一个0-1之间的随机实数。

上一篇

java的数据结构与C语言的数据结构有什么区别与联系?

下一篇

依次插入结点法生成二叉排序树是什么意思?