在小於O（N）的情況下生成N個準隨機數

這受到面試時的問題的啓發：您如何有效生成N個唯一的隨機數？他們的安全和分配/偏見並不重要。在小於O（N）的情況下生成N個準隨機數

我提出了一種天真的方式來調用rand（）N次，並通過反覆試驗來消除模糊，從而導致效率低下和有缺陷的解決方案。然後我讀了this SO question，這些算法非常適合獲得高質量的唯一數字，它們是O（N）。

但我懷疑有辦法獲得低於O（N）時間複雜度的虛擬任務的低質量唯一隨機數。我有一些可能的想法：

存儲許多預先計算的列表，每個包含N個數字並隨機檢索一個列表。對於固定的N，複雜度爲O（1）。使用的存儲空間是O（NR），其中R是列表的數量。
生成N/2個唯一隨機數，然後將它們除以2個不等的部分（奇數的floor/ceil，even的n + 1/n-1）。我知道這是有缺陷的（重複彈出）和O（N/2）仍然是O（N）。這更多是一種思考的食物。
生成一個大的隨機數，然後通過一些固定的操作（比特化操作，因式分解，遞歸，MapReduce或其他方法）從中擠出更多的變體。
以某種方式使用quasi-random sequence（不是數學家，只是搜索這個詞）。

您的想法？

2012-04-08 pati

他們抱怨說你的解決方案的O型複雜度太高，或者太低效了？因爲在給定範圍內生成_unique_數字的方法比試驗和錯誤更有效。另外，你的解決方案不是O（n）最壞的情況 - 爲了從n生成n的隨機置換，由於需要的重試次數，它將在O（n^2）時間內運行。 – 2012-04-11 04:45:03

假設這個例程有某種輸出（即結果被寫入某種數組）。填充大小爲N的數組（或其他數據結構）至少是一個O（N）操作，所以你不能比O（N）做得更好。

2012-04-08 16:55:34

感謝您的解釋，我相應地修改了一個問題。 – pati 2012-04-08 17:19:47

@ pati-你最好接受Oli的回答，然後發佈第二個問題。這樣，任何人都可以直接回答你的原始問題。 – templatetypedef 2012-04-08 17:24:02

好的，再次感謝，我會開始另一個。 – pati 2012-04-08 17:32:34

您可以隨後生成一個隨機數，如果結果數組包含它，只需向其中添加已生成數的最大數。

檢測已經生成的數字是否爲O（1）（使用哈希集合）。所以它是O（n），只有N random()調用。

當然，這是一個假設，我們沒有溢出上限（即BigInteger）。

2012-04-08 17:02:23

是的，這很好，很簡單的O（N）解決方案類似於[Floyd算法]（http://stackoverflow.com/a/1608585/1320363），但我認爲'數學證明的分佈質量'較少。 – pati 2012-04-08 17:31:01

這個分佈並不是您的問題所關注的問題：「他們的安全和分佈/偏見無關緊要。」 – 2012-04-08 17:43:39

當然，只是指出自己:) – pati 2012-04-08 17:59:53

回答