简单随机化算法（随机算法）
本文目录
随机算法
***隐藏网址***
一个随机算法的最坏运行时间几乎总是和非随机化算法的最坏情形运行时间相同。重要的区别在于，好的随机化算法没有不好的输入，而只有坏的随机数（相对于特定的输入）。
比如说：对于快速排序，方法A用第一个元素作为枢纽元，方法B使用随机选出的元素作为枢纽元。
通过随机化算法，特定的输入不再重要。重要的是随机数，我们可以得到一个期望的运行时间，此时我们是对所有可能的随机数取平均而不是对所有可能的输入求平均。
随机数有许多已知的统计性质；伪随机数满足这些性质的大部分。
真正需要的是随机数的序列。这些数应该独立地出现。
线性同余数发生器
产生随机数的最简单的方法是线性同余数发生器，由Lehmer于1951年提出：
例如：M = 11，x0 = 1
A = 7： 7， 5， 2， 3， 10， 4， 6， 9， 8， 1， 7 ，5 ，2... （周期为10 = M-1）
A = 5： 5， 3， 4， 9， 1， 5， 3， 4...（周期为5 《 M -1）
一个有问题的随机数发生器（返回(0,1)开区间值）：乘法溢出
工作在32位机器上的随机数发生器
证明：为什么δ(xi)或者是0，或者是1
为什么仅当余项的值小于0时，δ(xi)=1
说明：因为这里是对M取余，所以是M的倍数则自然消掉；并且δ(xi)两项都是取整函数，因此肯定为整数，另外xi+1总是介于1~M-1之间，因此当余项小于0，则取1
随机化的第一个用途是以O(lgn)期望时间支持查找和插入的数据结构。
每个2^i 结点就有一个指针指向下一个2^i结点，总的指针个数仅仅是加倍，但现在在一次查找中最多考察floor(lgn)个结点。因此总的时间消耗为O(lgn)。
本质上是二分查找：
放松上面数据结构的结构条件，就构成了跳跃表：
如果我们想查找19是否存在？如何查找呢？我们从头结点开始，首先和9进行判断，此时大于9，然后和21进行判断，小于21，此时这个值肯定在9结点和21结点之间，此时，我们和17进行判断，大于17，然后和21进行判断，小于21，此时肯定在17结点和21结点之间，此时和19进行判断，找到了。
1）实现
2）空间大小耗费
3）查找
1-2-3跳跃表的实现特点：
在同一层级的链表（不超过3个结点）中找到首个大于item的结点，然后向下移一层。
4）插入
必须保证当一个高度为h的新结点加入进来时不会产生具有四个高度为h的结点的间隙。
***隐藏网址***
设在第L层，并要降到下一层。如果下一层的间隙容量是3，则提高该间隙的中间项使其高度为L，从而形成两个容量为1的间隙。由于这使得朝下删除的道路上消除了容量为3的间隙，因此插入式安全的。
5）删除
***隐藏网址***
确定一个大数是否是素数的问题。
结点包括：
具有最低优先级的结点必然是根。树是根据优先级的N!种可能的排列而不是根据项的N!中排列形成的。
1）插入
插入之后，通过左旋和右旋恢复堆序性质：
2）删除
这个删除方法也可以采用红黑树的删除方法，将删除归结为叶子节点的删除。（使用后继，这样可以节省很多旋转）
随机化的算法
在我们的生活中，人们经常会去掷色子来看结果，投硬币来决定行动，这就牵涉到一个问题：随机。
计算机为我们提供好了随机方法（部分计算器也提供了），那么对于有些具有瑕疵的算法，如果配上随机化算法的话，又是可以得到一样不到的结果。
这种算法看上去是凭着运气做事，其实，随机化算法是有一定的理论基础的，我们可以想象，在这个闭区间里，随机1000次，随机到2这个数的几率是多大，何况1000次的随机在计算机程序中仅仅是一眨眼的功夫。可以看出，随机化算法有着广阔的前景。只是由于随机化算法比较难于掌控，所以并不是很多人都接触过他，但肯定有很多人都听说过。
下面，我们就随机化问题，举一个例子：
一个长度在4..10的字符串中，需要判定是否可以在字符串中删去若干字符，使得改变后字符串符合以下条件之一：
（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。
例如：长度为6字符串“POPKDK”，若删除其中的“O”，“D”两个字母，则原串变为：“PPKK”，符合条件（2）AABB。
分析：
这道题很容易想到一种算法：运用排列组合：枚举每4个字母，然后逐一判断。算法是可行的，但是如果需要题目中加上一句话：需要判断n个字符串，且n《=100000，那么这样的耗时是不能让人忍受①的，因为在枚举的过程中，是非常浪费时间的。
(①：这里是指信息学中要求算法的普遍运算时间为：1000ms）
所以这道题有可能可以借助于随机化算法，下面我们来算一下在10个组符中取4个字符一共有多少种取法：C(4,10)=210。那么很容易得知，随机化算法如果随机100次，能都到的结果基本上就正确了，而随机时的时间消耗是O(1)，只需要判断没有随机重复即可，判重的时间复杂度也为O(1)，并且最多随机100次，这样就可以有效地得到答案，最大运算次数为：O(100n)，这是在计算机的承受范围内（1000ms）的。
从这里就能看出，随机化算法是一个很好的概率算法，但是它并不能保证正确，而且它单独使用的情况很少，大部分是与其他的算法：例如贪心、搜索等配合起来运用。
再举一个例子：
排序问题。快速排序是排序方法中较为便捷的方法之一，但是由于它极不稳定，最好的时候时间复杂度为O(n㏒n)，这里的㏒是指以2为底的对数运算。最坏的时候能达到与普通排序方法一样的O(n^2)。
而制约快速排序的有两个：一是数据，越无序的数据，快排的速度越快；二是中间点的枚举。
因为两个制约条件都与随机有着不可分开的关系。
所以，在快速排序中加入随机化算法无疑是十分重要的。
微信红包的随机算法是怎样实现的
我们在一个20人的群中，自己发红包以及结合其他人发出红包的情况，整合成两轮的数据。每次金额设置都是20块并且有20个，第一轮是发了15次，第二轮是发了19次，总结成表格，然后为了避免突发的数据影响判断，我们将两轮数据杂糅从而生成了其他的三轮数据，一共是五轮数据。罗列如下表，高亮的数据为最佳手气。每一列的数据最早抢到红包的在最底端，越往上越晚抢。
从所有黄色的数值（最佳手气金额）可看出，所有最佳手气值都在平均值*2的前后附近（平均值=总金额/红包总个数，这里平均值=20/20=1），事实上确实如此，可通过微信红包分发算法得到验证，算法具体见后文
然后我们选取部分数据开始制作散点图。横轴为1-20，分别表示抢到红包的人的编号，随递增而越早。也就是20代表最早抢到的人。纵轴为金额。同样的形状颜色的点代表一次发红包，然后我们抓取部分数据显示为散点图，越密集代表该顺序位的用户得到的金额越稳定。散点图如下：
规律一：我们可以看到，所有红包大多数金额分布在0.5到1.5元之间，显示为图中方框所示，大部分点都分布在这个位置。然后是顺序位密集程度的对比，可以发现20、19，也就是最先抢到红包的人，小圆圈所示基本的点都集中在小范围，说明先抢红包的人得到的金额会比较稳定，但同时最佳手气的概率也比较低。大圆圈所示的是极不稳定，飘忽的金额分布，表示越晚抢红包得到的金额会飘忽不稳，但同时，抢到最佳手气等大金额的红包概率也比早抢的高。
根据上面的分析，我们又写了一个过滤计数函数，针对金额的分段的红包个数进行统计：
比如2.0-2.5
得到如下金额分布：
折线图：
规律二：绝大多数的红包的金额都集中在1-1.5，也就是说20块钱发20个红包的金额分布集中在比平均数大一点点的附近，同时较大幅超过平均数金额的红包大大少于低于于平均数的红包数量。
那我们继续扩大数据的规模，将几轮数据的均值和标准差分别做成折线图：
综合上面各个折线图的情况，我们可以得到越早抢红包的标准差越小，越晚抢红包的标准差越大，但同时，由均值和总额可以看出来，越早抢红包的均值往往要更高，红包金额得到最佳手气概率也会相对较小，越晚抢红包的人则得到最佳手气等大手气的概率更大。
为了得到更为趋近规律的曲线和规律，我们决定将两轮真实数据合并起来，然后给出幂函数的趋近线（虚线），如下图：
由于均值受极值波动影响较大，所以我们去除一些因为偶然差产生的极端点（圆圈的点）从而发现是递增的趋势。
规律三：可以很明显的看到，均值是随着抢红包的越晚而缓慢递减，标准差值同时也往上递增，这个趋势结合之前的分析，我们猜想，即标准差越大说明，领取到最大的红包和最小红包的风险越大，也就是说越晚抢标准差越大，对于冒险主义者来讲是最好的，因为他有很大概率获得最大的金额，但也大概率获得最小的红包，风险与收益并存；均值越大，说明每次都拿到一个不大不小的红包，虽然获得最小和最大金额红包的概率很小，但起码不亏本，也就是说越早抢，均值越稳定，这比较适合不喜欢冒险的人。
验证预测结果：
21：24分 发送预测结果到另一位同学微信：
随后开始发红包：
结果：
最佳手气为第8个人且金额为1.13
与预测结果一致，规律基本正确！
总结：
（1）最佳手气为1.13块，根据我们推导的预测公式=总额/红包总个数*2*随机数（0-2的double数）, 也就是说最佳手气在总额/红包总个数*2值的前后附近。这里我们判断在0.8-1.3之间，推断正确
（2)平均值为0.5元，0.5-0.8元的红包有3个，小于0.5的红包有6个，说明大于平均值的红包个数多于小于平均值的个数。与我们的第二点预测完全正确
(3)最佳手气位置：根据我们的散点图发现，最先抢到红包的人，得到的金额会比较稳定，但同时最佳手气的概率也比较低。表示越晚抢红包得到的金额波动较大，但同时抢到最佳手气等大金额的红包概率也比早抢的高。所以我们推断，最佳手气位置在最后20%-30%之间。
微信红包随机分发算法c＋＋模拟：
基本思路：每次抢到一个红包金额等于：红包剩余金额/红包剩余个数*2*随机数（0-1的double型），如果计算的结果小于等于0.01，则取0.01值
主要代码：
double packages;
double Luckiest_money=0;
void getPackage(int remainSize,double remainMoney){
srand((unsigned)time(NULL));
for(int i=0;i
Paillier算法随机化加密特性小记
Paillier加密算法是Pascal Paillier在1999年发明的公钥加密算法，该算法基于复合剩余类的困难问题，是一种满足加法的同态加密算法。
作为一种半同态加密方案，Paillier方案在隐私计算的各个场景中有着广泛的应用。
比如在联邦学习中，对特征提供方提供的特征需要进行统计分析、处理，比如WOE分析、分箱处理等，都需要用到标签方持有的样本标签，而标签是需要重点保护的。应用Paillier算法，对标签进行加密，然后交由对方基于密文标签进行加和计算。
一开始有个疑惑，在常见的二分类场景，标签通常是0和1。即使加密，其密文也就是两个值，这样岂不是还是会泄露标签信息（起**泄露正负样本的分布情况）？
这里就需要提到Paillier算法的随机化特性，算法在加密过程中，会选取一个符合条件的随机数参与加密，这样对于相同的明文，就产生了不同的密文。而在解密过程中，这个随机数会自动消除。
这里对该随机化特性背后的原理做简单理解性的描述。算法细节可参见Paillier论文及相关介绍。
费马小定理是数论中著名的一个定理：若 是一个整数， 是一个质数，那么 是 的倍数，可以表示为 ；若 不是 的倍数，该定理可以写成： 。
也就是说， 的 次方之后模 ，就变成了单位。在乘法运算中，相当于把 的效果给消解掉了。
Paillier算法中的随机化特性基本就是这样一个原理。
在Paillier算法中，使用了卡迈克尔函数 和卡迈克尔定理，对于正整数 ， ，其中 ，即 与 互质。算法中，会选择两个大素数 和 ，令 ，此时 ，即 和 的最小公倍数，该值会作为私钥。
费马小定理的扩展 - 费马欧拉定理和卡迈克尔定理可做对比：设 是一个正整数， ，则 ； 是欧拉函数，表示小于 的正整数中，和 互素的数的个数；当 是一个素数时，即为费马小定理。
