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

——TechZone(Harris)

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

洗牌嘛，不就是个随机算法吗？直接搞一个数组，把牌全部放进去，然后对调两张牌，随机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界老大的时代，盖茨就说过，如果你看完了这套书的第一卷本，那你直接给我发简历。