随机算法之舍伍德算法

缘起

闲来无事, 了解一下随机化算法.

分析

我们知道，平时用的算法都是确定性算法. 所谓确定性算法指的是对于固定的输入, 得到答案的时间是确定的（注意, 算法的随机性并不是说对于固定的输入，得到的答案可能不同，如果是这样的话, 就根本不是一个正确的算法）. 所谓随机化算法，指的就是对于确定的输入, 得到正确解的时间是不固定的.

常见的随机化算法有如下四种分类

1. 数值算法
2. 蒙特卡洛
3. 拉斯维加斯
4. 舍伍德

第一种我们不去研究. 我将研究其余三种算法. 本文研究的是第四种——舍伍德算法. 那么舍伍德算法是为了解决什么问题呢?

假设A是一个确定性算法，那么对于某个固定样例x, 计算样例x的结果需要花费的时间是t(x), 假设x的规模是n, 并且令Xn是所有规模为x的样例. 则当输入的样例规模为n的时候, 算法A的平均花费时间T是

既然是平均, 那必然就存在某个特定的样例x, 使得 t(x)>>T, 其中 >> 表示远大于. 所以如果想卡你的话, 我就出x这种样例来卡你算法的表现. 怎么办呢? 我们想将算法A改造成一个算法B——使得对于每个X_n中的样例x, 算法B花费在x上的时间是某个固定的 T+w(n), 其中w(x)是一个仅仅与x有关的不大的波动函数. 于是我们将算法A改造成了一个均摊性能较好的算法B. 这就是舍伍德算法的思想和干的事情.

所以舍伍德算法的基本思路就是将输入洗牌（shuffle）预处理. 这样, 就不会因为输入的缘故导致算法表现太差. （当然, 有得必有失，也失去了算法表现极好的机会）.