,总共有(n-k)个情况,由于 μ 出现的位置是随机的,总共有 n 个位置,所以所有情况发生的概率都是 1/n
只有次优点 λ 出现在前 k 个位置时,我们才能准确地找到最优点 x ,而次优点出现在前k...均匀随机排列
均匀随机排列是指产生1~n的每一种排列的概率完全相同,即产生某一种排列的概率为全排列的倒数
给定序列[1,2,3, … ,n],通过将这些数字随机地变换以使数组随机化,从而达到均匀随机排列...优先级数组就是一种得到均匀随机排列得方法
优先级数组
对数组A,给定另一个数组P,在P中随机地生成一个大范围整数,并根据P[i]的大小来调整A[i]的位置。...例如A=[1,2,3,4,5],而P=[13,62,6,19,52],那么调整后的序列就是[2,5,4,1,3]
但是这种方法有一个缺陷,即必须确保数组P的每一项都唯一,幸运的是,你只需要扩大随机数范围就可以尽可能保证不出现重复...A的任意一个随机排列S,只需要修改一下E的定义,我们都可以使用上述方法证明出 A[i] 恰好被分配到 S 数组中的指定位置 j 的概率为 1/n!