j***y
发帖数: 2074 | 4 第126页：
The algorithm considers the integers 0, 1, 2, ..., n-1 in order, and selects
each one by appropriate random test. By visiting the integers in order, we
guarantee that the output will be sorted.
To understand the selection criterion, let's consider the example that m=2
and n=5. We should select the first integer 0 with probability 2/5; a
program implements that by a statment like
if (bigrand() % 5) < 2
这里我有点疑问，为什么选第一个数字的时候不是1/5的概率，而是2/5的概率呢？机会
均等地从5个数字中选1个数字，难道概率不应该是1/5吗？
还是我理解的有问题？ |
|
