随機洗牌算法複雜度的比較執行個體

這篇博文是意外事件哈，算是有感而發。

在我前段時間，和網友讨論關于随機洗牌算法的過程中，寫了兩篇博文。

這引發了很多讨論，這不，網友ZhaoLS又寫了一篇類似的算法，加入讨論。

這篇文章我仔細拜讀了，也給了點意見，不過我想了一下，有些問題不吐不快，我想，幹脆，我也寫篇博文來讨論一下。

還是那句話哈，一家之言，歡迎拍磚。

在網友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++商用工程之道》

（直接點選下面連結或拷貝到浏覽器位址欄）

<a href="http://s.click.taobao.com/t_3?&amp;p=mm_13866629_0_0&amp;n=23&amp;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" target="_blank">http://s.click.taobao.com/t_3?&amp;p=mm_13866629_0_0&amp;n=23&amp;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</a>