根据Wikipedia，线性同余生成器由以下递归关系定义：
X(n) = {a.X(n-1) + c} mod m
其中0 < m, 0 <= a < m, 0 <= c < m,0 <= X(0) < m是指定生成器的整数常量。
如果给出a, c, m, X(0), 和的值n，我可以很快确定集合的k第 -th 最小值 ( 1 <= k <= n)吗？{X(0), X(1), ..., X(n)}（快于O(n)- 基于排序算法）
问问题
230 次
1 回答
1
假设您k在生成过程中没有存储最低的项目......
如果(n >= m)和 常数满足整个周期的标准（参考这里），那么第k-th 最小的项目将是k-1。
如果(n >= m)和 常量不符合条件，或者(n < m)您需要进行线性搜索，如果k迄今为止最低的 -th 是k-1.
于 2013-10-11T23:36:01.657 回答