【算法详解】洗牌算法[通俗易懂]
大家好,又见面了,我是你们的朋友全栈君。
1. 问题描述
洗牌算法是常见的随机问题;它可以抽象成:得到一个M以内的所有自然数的随机顺序数组。
常见问题描述:
1.将自然数1 ~ 100随机插入到一个大小为100的数组,无重复元素
2. 1 ~ 52张扑克牌重新洗牌
什么是好的洗牌算法:
洗牌之后,如果能够保证每一个数出现在所有位置上的概率是相等的,那么这种算法是符合要求的;这在个前提下,尽量降低时间和空间复杂度。
2. 算法实现
第一个算法:
随机抽出一张牌,检查这种牌是否被抽取过,如果已经被抽取过,则重新抽取,知道找到没有被抽取的牌;重复该过程,知道所有的牌都被抽取到。
这种算法是比较符合大脑的直观思维,这种算法有两种形式:
1. 每次随机抽取后,将抽取的牌拿出来,则此时剩余的牌为(N-1),这种算法避免了重复抽取,但是每次抽取一张牌后,都有一个删除操作,需要在原始数组中删除随机选中的牌(可使用Hashtable实现)
2. 每次随机抽取后,将抽取的符合要求的牌做好标记,但并不删除;与1相比,省去了删除的操作,但增加了而外的存储标志为的空间,同时导致可每次可能会抽取之前抽过的牌
这种方法的时间/空间复杂度都不好。
第二个算法:
每次随机抽出两张牌交换,交换一定次数后结束:
void shuffle(int* array, int len) { const int suff_time = len; for (int idx = 0; i < suff_time; i++) { int i = rand() % len; int j = rand() % len; int temp = array[i]; array[i] = array[j]; array[j] = temp; } }
这是一个常见的洗牌算法; 但是如何确定一个合适的交换次数?
假设交换了m此,则某张牌始终没有被交换的概率为 (n-2)/n * (n-2)/n, … …* (n-2)/n = ((n-2)/n)^m;我们希望其概率小于摸个值,求出m的解.假设概率小于1/1000,对于n=52,m大概为176,实际上远远大于数组的长度.
第三个算法:
该算法每次随机选取一个数,然后将该数与数组中最后(或最前)的元素相交换(如果随机选中的是最后/最前的元素,则相当于没有发生交换);然后缩小选取数组的范围,去掉最后的元素,即之前随机抽取出的数。重复上面的过程,直到剩余数组的大小为1,即只有一个元素时结束:
void shuffle(int* array, int len)
{
int i = len;
int j = 0;
int temp= = 0;
if (i == 0)
{
return;
}
while (--i)
{
j = rand() % (i+1);
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
该算法的数学证明请参照具体的论文或者 博文;
该算法复杂度为O(n),且各元素随机概率相等。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/191038.html原文链接:https://javaforall.cn
相关文章
- OHEM算法论文理解
- 智能车图像处理-阳光算法[通俗易懂]
- 算法 时间复杂度概念及案例
- 逆变器运用到的c语言算法,详解六种逆变电源的控制算法[通俗易懂]
- 快速傅里叶变换(FFT)算法【详解】[通俗易懂]
- uc/os-II的内存改进与实现TLSF算法的详解,移植实现(二)[通俗易懂]
- 【RSA解密】蓝桥杯第十届省赛A组 扩展欧几里得算法
- Floyd算法详解——包括解题步骤与编程[通俗易懂]
- 12306抢票算法大曝光
- 算法的复杂性详解及原理
- dijkstra算法详解—简单易懂[通俗易懂]
- 详解九章算法的作者是谁_arrayset
- PID算法详解[通俗易懂]
- ❤️十大排序算法详解❤️——可能是你看过最全的,完整版代码
- # 分布式理论协议与算法 第二弹 ACID原则
- 【数据结构与算法】图遍历算法 ( 深度优先搜索代码示例 )
- 非阻塞算法简介详解程序员
- 算法-链表实现栈详解手机开发
- Java数据结构和算法(十一)——红黑树详解编程语言
- 算法-青蛙变态跳台阶详解编程语言
- 算法Linux CFS调度算法——简单高效的任务调度方案(linuxcfs调度)
- 复杂链表的复制算法详解编程语言
- 不同路径算法详解编程语言
- 无重复字符的最长子串及最小覆盖子串(滑动窗口法)算法详解编程语言
- 顺序表的基本算法详解编程语言
- Peterson算法(解决临界区问题)详解
- 精准计时Redis计时器算法分析(计时器算法 redis)
- 使用 Redis 算法实现精准数据排重(利用redis 数据排重)
- Oracle中判断数字相等的算法(oracle中数字判等)
- 传阿里唯一的P12算法专家,调入蚂蚁金服
- utf8的编码算法转载