0fn*_*fnt 3 algorithm probability
是否有可能统一地对n个大小的数组的元素进行混洗,即任何n的概率!在预期O(n)时间内发生的组合是相同的.怎么会这样？我必须将元素改组A为新数组B
当我尝试这样做时,我想到的第一件事就是i从1到n中选择一个随机数,看看是否A[i]已经被选中,如果是,那么重复一遍,否则放在A[i]第一个可用的位置B.然而,这个优惠券收集器问题已经预料到了O(n log n).有人可以建议O(n)预期的时间算法.
谢谢.
Mat*_*Mat 11
你应该看看Fisher-Yates shuffle.
来自文章:
正确实施,Fisher-Yates shuffle是公正的,因此每个排列都是同样可能的.该算法的现代版本也相当有效,只需要与被洗牌的项目数量成比例的时间,而不需要额外的存储空间.
所以它符合您的要求.它也非常容易实现.
| 归档时间： |
|
| 查看次数： |
3607 次 |
| 最近记录： |