随机洗牌算法复杂度的比较实例

这篇博文是意外事件哈，算是有感而发。

在我前段时间，和网友讨论关于随机洗牌算法的过程中，写了两篇博文。

《我以前用过的一个洗牌算法》 http://tonyxiaohome.blog.51cto.com/925273/302220

《和一个网友关于随机洗牌算法的讨论》 http://tonyxiaohome.blog.51cto.com/925273/311861

这引发了很多讨论，这不，网友ZhaoLS又写了一篇类似的算法，加入讨论。

《生成不重复的随机数序列》 http://student.csdn.net/space.php?uid=127131&do=blog&id=32861

这篇文章我仔细拜读了，也给了点意见，不过我想了一下，有些问题不吐不快，我想，干脆，我也写篇博文来讨论一下。

还是那句话哈，一家之言，欢迎拍砖。

在网友ZhaoLS的这个算法里面，他提到了两个方案：

1）建立一个n维数组，用于保存已生成的并且合乎条件的随机数。利用Random类的Next(n-1);方法生成随机数，与前面已经生成的随机数进行比较，如果这个随机数已经生成过，就抛弃当前随机数，重新生成随机数与前面的随机数进行比较，直至所生成的随机数前面没有出现过为止，把这个随机数添加到数组中。同样方法，生成符合条件的n个随机数。

2）建立一个n维数组，用于保存生成的随机数；在建立一个n维bool型数组flag，并将元素全部初始化为false，作为某一个随机数是否已经生成的标志位。同样利用Random类的Next(n-1);方法生成随机数tmp，判断flag[tmp]是否为true，若为true（说明tmp在前面已经生成过），则放弃tmp重新生成随机数赋值给tmp，继续判断，直至flag[tmp]是否为false（说明tmp在以前还未出现过），此时将flag[tmp]赋值为true，表明tmp已经生成过了。同样方法，生成符合条件的n个随机数。

我看了一下，感觉都不是很好。

第一个办法，由于每生成一个新随机数，都要和过去的已有结果比较，这个顺序比较，复杂度是O（n），我们可以想象，随着已有结果的逐渐增多，这个O（n）就越来越长，原文中是90000个数字，这个复杂度就是O(90000)，记住哦，每生成一个随机数，都要比较90000次，而且，一旦比较失败，得重来，所以，效率很低。这在原文中已经论述了，这种方法不可取。

第二个办法，好一点，是生成一张映射表，对于可能的随机数范围的每个数字都建立一张表，以bool表示这个数字是否已经被用过了，用过，则放弃重新求随机数。这个我也觉得不好。这个方法相对第一个方法来说，取消了O（90000），但代价是，要建立一个很大的bool表格，如果我们的随机数范围是unsigned int的表示范围，0~0xFFFFFFFF，那么可以想象，起码目前的32bitsOS平台，无论是Windows还是Linux，都不支持建立这么大的数组。第二，它没有解决碰撞问题，即比较发现，一个数字已经用了，则必须重来。我们可以想象，随着一个数据段的数字被逐渐使用，这个碰撞率会越来越高，因此，越到后来，速度越慢，因为很可能运气不好，连续生成的n个随机数都是用过的，被否决，这个效率实际上比O（90000）还差，甚至几十万次都可能碰撞否决。这实际上是O（?），连O（n）都不是。因此，我觉得不好。

这里我再说一点我前文的洗牌算法，其实，我在评估洗牌算法时，前文这两种方法都有想过，但是，总觉得不好，最后才想到我博文中双随机交换的思想，因为这样效率高，复杂度可控。

我的建议，凡是给定范围内，要求生成不重复的随机序列，最好采用我文中提到的双随机因子交换的办法：

1、建立数组，按顺序填充数组的值，即a[0]=0;a[1]=1;a[n]=n...，这其实是以最小的代价，获得一个数据集，这个数据集中，每个数字只有一次出场机会，即永远不会重复。看见没，我是先解决“不重复”这个问题，没有先解决“随机”问题。

2、在这个数组中，随机去交换，无论是使用《和一个网友关于随机洗牌算法的讨论》中的一个因子遍历，另外一个因子随机取的办法，还是用我的博文中两个因子都随机取位置，互相交换，都可以，在数字不重复的大前提下，我们无非是随机乱序而已。

3、一般说来，根据经验，这个随机交换的次数只要达到数组长度的50%~100%，这个顺序已经打得很乱了，基本上就是我们要的“不重复随机序列”。

4、使用时，只要我们按照顺序去读这个数组中的值，其实已经获得很好的随机性了，且没有重复。

大家注意没有，这样做的好处，是程序复杂度可控，且没有过多的额外开销，整个程序效率很高。

1、建立数组，这没有办法，O（n），比如前文90000，我就做个O（90000）的动作。这没法优化，这是必须付出的代价。

2、交换，求两个交换因子的随机位置，算O（2），交换动作，我算O（1），因此，每次成本O（3），我按照75%左右做交换成本，90000*75%=67500，我总的数据表准备成本O（67500*3）=O（202500）。

3、以后使用数据不说了，反正都是O（1）。

我们可以算一下，我的代价，总的复杂度成本为O（202500+90000）=O（292500），就已经备表成功，可以供使用。

而网友ZhaoLS的办法，由于中间存在O（？）的存在，实际上，没法比较算法复杂度，他的办法求不出来复杂度。但可以肯定，由于有碰撞的存在，肯定很高，而且，生成表的过程，越到后面，碰撞率越高，速度就越慢。所以不建议使用。

嗯，看似一个简单的洗牌算法，其实里面体现的算法分析还是很深的，我目前想出来的最简单的办法就是我博文中的双随机因子交换的办法，我也很欢迎有兴趣的朋友，提出自己的方案，大家讨论一下，如果有更高明的办法，我也希望学习一下。

=======================================================
在线底价购买《0bug-C/C++商用工程之道》
（直接点击下面链接或拷贝到浏览器地址栏）
http://s.click.taobao.com/t_3?&p=mm_13866629_0_0&n=23&l=http%3A%2F%2Fsearch8.taobao.com%2Fbrowse%2F0%2Fn-g%2Corvv64tborsvwmjvgawdkmbqgboq---g%2Cgaqge5lhebbs6qzlfmqmttgtyo42jm6m22xllqa-------------1%2C2%2C3%2C4%2C5%2C6%2C7%2C8%2C9%2C10%2C11%2C12%2C13%2C14%2C15%2C16%2C17%2C18%2C19%2C20---40--coefp-0-all-0.htm%3Fpid%3Dmm_13866629_0_0

本文转自 tonyxiaohome 51CTO博客，原文链接：http://blog.51cto.com/tonyxiaohome/313362，如需转载请自行联系原作者