Question

随机算法

Answer 1

相关总结参见 http://www.jianshu.com/p/60ea83ea17cc

一个随机算法的最坏运行时间几乎总是和非随机化算法的最坏情形运行时间相同。重要的区别在于，好的随机化算法没有不好的输入，而只有坏的随机数（相对于特定的输入）。
比如说：对于快速排序，方法A用第一个元素作为枢纽元，方法B使用随机选出的元素作为枢纽元。

通过随机化算法，特定的输入不再重要。重要的是随机数，我们可以得到一个期望的运行时间，此时我们是对所有可能的随机数取平均而不是对所有可能的输入求平均。

随机数有许多已知的统计性质；伪随机数满足这些性质的大部分。
真正需要的是随机数的序列。这些数应该独立地出现。

线性同余数发生器
产生随机数的最简单的方法是线性同余数发生器，由Lehmer于1951年提出：

例如：M = 11，x0 = 1
A = 7： 7， 5， 2， 3， 10， 4， 6， 9， 8， 1， 7 ，5 ，2... （周期为10 = M-1）
A = 5： 5， 3， 4， 9， 1， 5， 3， 4...（周期为5 < M -1）

一个有问题的随机数发生器（返回(0,1)开区间值）：乘法溢出

工作在32位机器上的随机数发生器

证明：为什么δ(xi)或者是0，或者是1
为什么仅当余项的值小于0时，δ(xi)=1
说明：因为这里是对M取余，所以是M的倍数则自然消掉；并且δ(xi)两项都是取整函数，因此肯定为整数，另外xi+1总是介于1~M-1之间，因此当余项小于0，则取1

随机化的第一个用途是以O(lgn)期望时间支持查找和插入的数据结构。
每个2^i 结点就有一个指针指向下一个2^i结点，总的指针个数仅仅是加倍，但现在在一次查找中最多考察floor(lgn)个结点。因此总的时间消耗为O(lgn)。
本质上是二分查找：

放松上面数据结构的结构条件，就构成了跳跃表：

如果我们想查找19是否存在？如何查找呢？我们从头结点开始，首先和9进行判断，此时大于9，然后和21进行判断，小于21，此时这个值肯定在9结点和21结点之间，此时，我们和17进行判断，大于17，然后和21进行判断，小于21，此时肯定在17结点和21结点之间，此时和19进行判断，找到了。

1）实现

2）空间大小耗费

3）查找
1-2-3跳跃表的实现特点：
在同一层级的链表（不超过3个结点）中找到首个大于item的结点，然后向下移一层。

4）插入
必须保证当一个高度为h的新结点加入进来时不会产生具有四个高度为h的结点的间隙。
插入采用2-3-4树的自顶向下的方法（保证当前结点不是4-结点）：（参考 http://www.jianshu.com/p/8258ed821859 ）
设在第L层，并要降到下一层。如果下一层的间隙容量是3，则提高该间隙的中间项使其高度为L，从而形成两个容量为1的间隙。由于这使得朝下删除的道路上消除了容量为3的间隙，因此插入式安全的。

5）删除
删除采用2-3-4树的自顶向下的方法（保证当前结点不是2-结点）：（参考 http://www.jianshu.com/p/8258ed821859 ）

确定一个大数是否是素数的问题。

结点包括：

具有最低优先级的结点必然是根。树是根据优先级的N!种可能的排列而不是根据项的N!中排列形成的。

1）插入

插入之后，通过左旋和右旋恢复堆序性质：

2）删除
这个删除方法也可以采用红黑树的删除方法，将删除归结为叶子节点的删除。（使用后继，这样可以节省很多旋转）