产生N个准随机数小于O（N） [英] Generate N quasi random numbers in less than O(N)
问题描述
这个灵感来自于一个问题，在面试：你如何有效地产生N个独特的随机数？他们的安全和分配/偏见并不重要。
This was inspired by a question at a job interview: how do you efficiently generate N unique random numbers? Their security and distribution/bias don't matter.
我建议调用RAND（）N次，并通过试验和错误消除愚弄的天真的方式，从而获得效率低下和有缺陷的解决方案。然后，我读过<一个href="http://stackoverflow.com/questions/1608181/unique-random-numbers-in-an-integer-array-in-the-c-programming-language">this SO质疑，这些算法都是伟大的好品质独特的数字，他们是O（N）。
I proposed a naive way of calling rand() N times and eliminating dupes by trial and error, thus getting inefficient and flawed solution. Then I've read this SO question, these algorithms are great for getting quality unique numbers and they are O(N).
但我怀疑有办法来获得低质量的唯一的随机号码迟钝的任务，在不到O（N）的时间复杂度。我得到了一些可能的想法：
But I suspect there are ways to get low-quality unique random numbers for dummy tasks in less than O(N) time complexity. I got some possible ideas:
- pcomputed存储许多$ P $列出了每个含有N号和检索一个列表中随机。复杂度为O（1）使用固定N.存储空间为O（NR），其中R是列表的数量。
- 生成N / 2个独特的随机数，然后通过2不相等份（地板/ CEIL为奇数，n + 1个/ n-1个对偶）它们划分。我知道这是有缺陷的（可以重复弹出）和O（N / 2）仍然是O（N）。这更多的是一种精神食粮。
- 生成一个大的随机数，然后通过一些固定的操作像位运算，因式分解，递归，麻preduce或别的东西榨取它更多的变种。
- 使用一个伪随机序列某种方式（而不是一个数学的家伙，只是GOOGLE了这术语）。
- Store many precomputed lists each containing N numbers and retrieve one list randomly. Complexity is O(1) for fixed N. Storage space used is O(NR) where R is number of lists.
- Generate N/2 unique random numbers and then divide them by 2 inequal parts (floor/ceil for odd numbers, n+1/n-1 for even). I know this is flawed (duplicates can pop up) and O(N/2) is still O(N). This is more of a food for thought.
- Generate one big random number and then squeeze more variants from it by some fixed manipulations like bitwise operations, factorization, recursion, MapReduce or something else.
- Use a quasi-random sequence somehow (not a math guy, just googled this term).
您的想法？
推荐答案
presumably这个程序有一些类型的输出（即结果写入某种类型的数组）。填充的大小N阵列（或其他数据结构）至少一个O（N）操作，所以你不能比O（N）做的更好。
Presumably this routine has some kind of output (i.e. the results are written to an array of some kind). Populating an array (or some other data-structure) of size N is at least an O(N) operation, so you can't do better than O(N).
这篇关于产生N个准随机数小于O（N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
