生成不重複的隨機數在一個真正的大範圍

我目前正在調查獲得的隨機數，而不重複efficent方式。要了解這個問題的一個方法是在這篇文章中給出的示例：生成不重複的隨機數在一個真正的大範圍

我們用數字形式0一頂帽子n-1和我們取k個隨機形成的帽子。

給出具有k個位置的矢量的空間，其中每個位置具有介於0和n-1之間的整數並且矢量沒有重複的情況下，更爲正式的方式來陳述問題將是：。我們希望能夠以均勻分佈隨機查看元素。

我發現這樣做的these三種方式。我也讀了關於油藏採樣。

但我很感興趣在 n是真正的大和k比N多小的情況下。而且，即使在這種情況下，O（k^2）中具有時間複雜度的算法也可能是不可接受的。另一方面，如果n很大，那麼O（n）中的任何具有空間或時間複雜度的算法都是不可接受的。所以我想知道是否有其他一些衆所周知的（甚至不是衆所周知的）算法來做到這一點。

我將要並欣賞任何類型的文件，書籍，鏈接等和建議的任何引用。

在此先感謝。 PS：我知道很多類似的問題已經被問到，但在這種情況下，O（f（n））中的任何內容都是不可接受的。 f（）幾乎可以起到任何作用。

從一個非常大的空間ň生成ķ樣品可以在O（k）的時間通過保持樣品在哈希表中進行與鮑勃·弗洛伊德的算法。請參閱https://stackoverflow.com/a/6978109

2013-10-17 12:12:21

謝謝。我發現這個算法，忘了提及它。問題是：我不明白哈希表究竟如何處理O（k）空間（和O（k）時間因子，我們必須初始化它）。如果我們想避免碰撞，那麼表格的大小是否在O（k）？ –

實現的細節很大程度上取決於實際的數字，但是像2k這樣的大小的散列表應該具有最小的衝突，並且即使使用簡單的線性探測也很有效。你爲什麼認爲它不會？ –

嗨。我對漸近複雜性感興趣。我問大小爲O（k）的表是否足以維持O（k）時間複雜度。我讀了弗洛伊德算法和其他資源的原始文件，但無法找到證明。所以這就是我對時間複雜性持懷疑態度的原因。這似乎不自然，所以我想看到一個合適的證據。 –

回答