杂谈·一个神一般的随机算法

这篇文章，我们从一个经典的面试题开始讲起。这个题目，可能会有很多形式，但是背后的逻辑是一样的：如何写出一个公平的洗牌算法。

洗牌嘛，不就是个随机算法吗？直接搞一个数组，把牌全部放进去，然后对调两张牌，随机k次即可。

你要敢这样回答，那面试官肯定会问，k取多少呢？

显然不能是个常量，如果你取10,000，如果只有100张牌，显然太多了，如果有100,000张呢？又太少了。

那你可能会想，让k随着牌的数量变化不就行了？嗯，的确，这个想法已经比刚刚的强很多了，但是你要敢这么回答，面试官多半会坏笑然后问你，你这个算法，公平吗？
再回去看看问题：如何写出一个公平的洗牌算法。

刚刚忙活了那么久，其实连问题的本质都没有触及。这题的关键，在于设计公平。

一个面试官面试，往往看的不是你是否答对了问题，因为一道面试题，答案不只一种。如果你有对题目足够强的思维能力，你就是面试官要的人。如果你看到这道题，一开始就是从公平入手，那么你是很优秀的。因为背出一个算法很容易，但是这种探求问题根源的思维角度，绝不是一朝之功。这是一种不断面对问题，不断解决问题而逐渐锻炼出来的能力。

那么我们就来看看，对于这个算法，公平的定义是什么。

如果有n张牌，那么排序的可能性就是n!。我们可以生成所有的可能性，然后随机选一个。这种算法是绝对公平的。但是，复杂度太高。这个复杂度达到了$O(n!)$。因为我们需要计算$n!$种排列，那么就至少需要$n!$的时间。

有的同学可能对这样的复杂度不太感冒。这是一个比$2^n$还要高的复杂度。$2^n$是n个2相乘，而$n!$也是n个数，而这些数除了1比2小以外，其他的数都≥2。而$2^n$已经是指数爆炸了，在n≥4的时候，$n!$以极快的速度超越$2^n$。

这个算法的确是公平的，但是时间不能允许。

我们再换一种角度去思考公平的问题。公平其实也可以理解为，我们每一张牌出现在每一个位置的概率都相等。这个定义和上面提到的暴力算法其实是等价的，学过概率论的同学可以去证明下。根据这个定义，我们就可以很快写出一个简单的算法：

for (int i = n-1; i >= 0; i--)
    swap(arr[i], arr[rand() % (i +1)]);

说它简单，是因为就一层循环。

小伙伴们可以看看这个循环在干什么。其实就是将下标为i的元素，和一个随机下标的元素交换位置。而为了确保随机的数在[0,i]的范围内，我们用了取余运算除以(i+1)。

这个算法就是大名鼎鼎的 Knuth-Shuffle，即 Knuth 洗牌算法。

原理待会儿再讲，我们先来看看这个传奇般的人物。

中文名:高纳德。算法理论的创始人。我们现在所使用的各种算法复杂度分析的符号，就是他发明的。上世纪60-70年代计算机算法的黄金时期,近乎就是他一手主导的。他的成就实在是太多，一本书估计都写不完。

大家最津津乐道的，就是他所写的《The Art of Computer Programming 》，简称TAOCP 。这套书准备写七卷，然后，到今天还没有写完，但已经被《科学美国人》评为可以媲美相对论的巨著。微软还是IT界老大的时代，盖茨就说过，如果你看完了这套书的第一卷本，那你直接给我发简历。

至于这套书为什么写这么慢，因为老头子当时写这本书，写到一半觉得时下的排版工具都太烂了，于是转手就发明了现在流行的TeX……

另外，他可能也觉得当时的所有编程语言都无法描述自己的思想，于是自己发明了一套抽象逻辑语言用于展示这套书的逻辑部分……

（感受到了和大佬的差距）

下面这句话，和大家共勉：

A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
——Donald E. Knuth 1978

下面就来看看具体是怎么通过这样一个简单的算法来实现绝对公平的。

其实，可怕的地方，就在于太简单……
我们用5个数字来简单模拟下这个算法：

1 2 3 4 5

这个算法，会在5个元素中选出一个元素和最后一个元素交换。假设我们选择3。就变成这样：

1 2 5 4 3

那么这个3出现在最后的概率是多少呢？从5个里面挑嘛，那肯定是$\frac{1}{5}$嘛。

再选一个，假设选到了1，那么就变成这样：

4 2 5 1 3

这个1出现在这个位置的概率又是多少呢？

上面那一轮，1没被挑走，而这一轮里面挑走了。

$\frac{4}{5}\times\frac{1}{4}=\frac{1}{5}$

还是等于$\frac{1}{5}$！

继续，假设这次是2。

4 5 2 1 3

概率依旧

$\frac{4}{5}\times\frac{3}{4}\times\frac{1}{3}=\frac{1}{5}$

假设下一个是4，那么

5 4 2 1 3

概率

$\frac{4}{5}\times\frac{3}{4}\times\frac{2}{3}\times\frac{1}{2}=\frac{1}{5}$

而这样5就只能在第一个位置了，概率还是

$\frac{4}{5}\times\frac{3}{4}\times\frac{2}{3}\times\frac{1}{2}=\frac{1}{5}$

大家看到了，自始至终，所有的位置出现的概率都是相等的，如果数组长度是n，那么每个位置的概率就是$\frac{1}{n}$，而复杂度$O(n)$，比$O(n!)$少了太多太多……

这个算法不仅仅可以用来洗牌，很多场景下的随机都可以使用。大家可以自己思考下，也可以运用于实际的解题甚至是开发之中。

其实大家应该有感觉了，算法绝对不是枯燥的逻辑堆砌，而是神一般的逻辑创造。这个世界也是如此，尽管极其复杂，变化万千，但又竟是如此简洁，巧妙而优雅…