搜索
EditbyJamesWu2011/1/101.概率算法部分1.0几个基本概念1.0.1期望时间和平均时间的区别确定算法的平均执行时间：输入规模一定的所有输入实例是等概率出现时，算法的平均执行时间概率算法的期望执行时间：反复解同一个输入实例所花的平均执行时间概率算法的平均期望时间：所有输入实例上平均的期望执行时间概率算法的最坏期望时间：最坏的输入实例上的期望执行时间1.0.2Uniform函数在X中随机，均匀和独立地取一个元素的算法：ModularExponent(a,j,p){//求方幂模s=ajmodp,注意先求aj可能会溢出s←1;whilej0do{if(jisodd)s←s·amodp;a←a2modp;j←jdiv2;}returns;}Draw(a,p){//在X中随机取一元素j←uniform(1..p-1);returnModularExponent(a,j,p);//在X中随机取一元素}1.1概率算法的分类1.1.1数字算法主要用于找到一个数字问题的近似解使用的理由现实世界中的问题在原理上可能就不存在精确解，例如，实验数据本身就是近似的，一个无理数在计算机中只能近似地表示精确解存在但无法在可行的时间内求得，有时答案是以置信区间的形式给出的1.1.2MonteCarlo算法特点：MC算法总是给出一个答案，但该答案未必正确，成功(即答案是正确的)的概率正比于算法执行的时间缺点：一般不能有效地确定算法的答案是否正确1.1.3LasVagas算法LV算法绝不返回错误的答案。特点：获得的答案必定正确，但有时它仍根本就找不到答案。和MC算法一样，成功的概率亦随算法执行时间增加而增加。无论输入何种实例，只要算法在该实例上运行足够的次数，则算法失败的概率就任意小。1.1.4Sherwood算法Sherwood算法总是给出正确的答案。当某些确定算法解决一个特殊问题平均的时间比最坏时间快得多时，我们可以使用Sherwood算法来减少，甚至是消除好的和坏的实例之间的差别。1.2算法的实现方式1.2.1数字算法1.2.1.1HitorMiss算法计算积分（面积法）HitorMiss(f,n){k←0;fori←1tondo,x←uniform(0,1);y←uniform(0,1);iff(x,y)在满足的面积内thenk++;}returnk/n;}1.2.1.2Crude算法计算积分（积分化求平均值法）Crude(f,n,a,b){sum←0;fori←1tondo,x←uniform(a,b);sum←sum+f(x);}return(b-a)sum/n;}1.2.1.3两种方法的比较对于给定的迭代次数n，Crude算法的方差不会大于HitorMiss的方差。但不能说，Crude算法总是优于HitorMiss。因为后者在给定的时间内能迭代的次数更多。例如，计算π值时，Crude需计算平方根，而用投镖算法darts时，即HitorMiss无需计算平方根。1.2.1.4确定的算法——梯形算法（上底加下底乘以高除以2）Trapezoid(f,n,a,b){//假设n≥2delta←(b-a)/(n-1);sum←(f(a)+f(b))/2;forx←a+deltastepdeltatob–deltadosum←sum+f(x)returnsum×delta;}一般地，在同样的精度下，梯形算法的迭代次数少于MC积分，但是有时确定型积分算法求不出解，若用MC积分则不会发生该类问题，或虽然发生，但概率小得多。在确定算法中，为了达到一定的精度，采样点的数目随着积分维数成指数增长，例如，一维积分若有100个点可达到一定的精度，则二维积分可能要计算1002个点才能达到同样的精度，三维积分则需计算1003个点。(系统的方法)但概率算法对维数的敏感度不大，仅是每次迭代中计算的量稍增一点，实际上，MC积分特别适合用于计算4或更高维数的定积分。若要提高精度，则可用混合技术：部分采用系统的方法，部分采用概率的方法1.2.1.5例1：求集合的势问题描述：估算一个集合中元素的个数解决思路：设X是具有n个元素的集合，我们有回放地随机，均匀和独立地从X中选取元素，设k是出现第1次重复之前所选出的元素数目，则当n足够大时，k的期望值趋近为β√n，这里β=√π2≈1.253利用此结论可以得出估计|X|的概率算法：β√n=√𝑛𝜋2=k⟹n=2𝑘2𝜋算法：SetCount(X){k←0;S←Ф;a←uniform(X);do{k++;S←S∪,a-;a←uniform(X);}while(a∉S)return2k2/π}复杂度：注意：∵k的期望值是√𝑛𝜋2，∴上述算法n需足够大，且运行多次后才能确定n=|X|，即取多次运行后的平均值才能是n。该算法的时间和空间均为θ(√n)，因为k=θ(√n)1.2.1.6例2：多重集合中不同数目的估计用散列表π(m+1),m=5+lgM，若以元素e的hash(e)以00…01开头（前面k-1个0），则π(𝑘)=1最后返回π中第一个出现0的位置z，则集合中不同元素的下界和上界分别是[2z-2,2z]复杂度：时间O(N)，空间：O(lgN)1.2.2Sherwood算法1.2.2.1Sherwood算法的基本思想对于一个确定性算法，它的平均时间很容易计算：T（确定性算法平均时间）=（每次执行的时间之和）/（执行总次数）但是会存在这样一个不好的情况：某次执行的时间远远大于平均执行时间，比如最坏情况。Sherwood算法的目的就是为了解决这个问题，利用概率的方法（或者说随机的方法）避免了最坏情况的发生，但这是要付出其他的时间代价（比如在取随机的时候需要花费一点时间），所以Sherwood算法的平均时间稍稍大于确定性算法的平均时间。Sherwood算法的应用范围：在确定性算法中，它的平均执行时间较优，最坏性能较差，这样的算法就用Sherwood算法去改进Sherwood一般方法是：①将被解的实例变换到一个随机实例。//预处理②用确定算法解此随机实例，得到一个解。③将此解变换为对原实例的解。//后处理1.2.2.2Sherwood算法预处理的数学模型1.确定性算法：f:X-Y2.确定性算法的实例集合：X,size为n时写作Xn3.Sherwood算法用于均匀随机抽样的集合：A，size为n时写作An，|An|=|Xn|4.随机抽样的预处理及后处理时用到的一对函数，对应上面的①③，（PPT在这里有误）u:X×A-Yv:A×Y-Xu,v满足三个性质：(∀n∈N)(∀x,y∈Xn)(∃!r∈An)，使得u(x,r)=y这条对应①，其中∃!表示有且仅有一个(∀n∈N)(∀x∈Xn)(∀r∈An)，使得f(x)=v(r,f(u(x,r)))这条对应③函数u,v在最坏情况下能够有效计算1.2.2.3Sherwood算法的过程确定算法f(x)可改造为Sherwood算法：RH(x){//用Sherwood算法计算f(x)n←length*x+;//x的size为nr←uniform(An);//随机取一元素y←u(x,r);//将原实例x转化为随机实例ys←f(y);//用确定算法求y的解sreturnv(r,s);//将s的解变换为x的解}1.2.2.4例1：选择和排序的Sherwood算法只需进行简单的打乱顺序即可，u即表示打乱顺序函数shuffleShuffle(T){n←length*T+;fori←1ton-1do{//在T[i..n]中随机选1元素放在T[i]上j←uniform(i..n);T*i+←T*j+;}}1.2.2.5例2：离散对数计算问题描述：设a=gxmodp，记logg,pa=x，称x为a的(以g为底模除p)对数。从p，g，a计算x称为离散对数问题。问题在于：给出p,g,a，怎么求x简单算法：①∀x,计算gx最多计算0≤x≤p-1或1≤x≤p，因为实际上离散对数g是循环群；②验证a=gxmodp是否成立。dlog(g,a,p){//当这样的对数不存在时，算法返回px←0;y←1;do{x++;y←y*g;//计算y=gx-while(a≠ymodp)and(x≠p);returnx}问题：最坏O(p)，若P很大怎么办？所以简单算法不行而且x的算出来的快慢取决于a的取值，a的取值能够让算法较早找到正确的x，则算法很快就完了，否则很慢，直到p。Sherwood算法解决方法根据上面的分析，Sherwood算法应该使得这个算法不会根据a,p的取值影响算法的快慢定理：1.Logg,p(stmodp)=(logg,ps+logg,pt)mod(p-1)2.Logg,p(grmodp)=r,0=r=p–2dlogRH(g,ap){//求logg,pa,a=gxmodp，求x//Sherwood算法r←uniform(0..p-2);b←ModularExponent(g,r,p);//求幂模b=grmodp，定理1真数的一部分c←bamodp;//((grmodp)(gxmodp))modp=gr+xmodp=c,定理2中的真数y←logg,pc;//使用确定性算法求logp,gc,y=r+x，定理2return(y-r)mod(p-1);//求x，定理1}在这里，唯一耗费时间的是b←ModularExponent(g,r,p)，它的执行时间与a,p的取值无关，只与随机取出的r有关1.2.2.6例3：搜索有序表问题描述：在有序表中搜索x，如果存在返回其index基本搜索函数：Search(x,i){//从index=i开始搜索x，这是一个顺序查找过程whilexval[i]doi←ptr*i+;returni;}4种算法：A(x),时间复杂度O(n)A(x){returnSearch(x,head);}D(x)，时间复杂度O(n/3)D(x){i←uniform(1..n);y←val*i+;case{xy:returnSearch(x,head);//case1xy:returnSearch(x,ptr[i]);//case2otherwise:returni;//case3，x=y}}B(x)，时间复杂度O(√𝐧)算法基本思想：对于一个有序表S，它上面的元素分别是a1,a2,…,an，它们之间可以是乱序的，要查找的x是其中一员。若把a1,a2,…,an有序排列成为ao1ao2…aon，x仍然是其中一员。把ao1ao2…aon划分成L个区间，x也必然是某个区间中的一员。那么根据Search(x,i)是一个有序查找过程，只需要找到x所在区间中在x之前的元素的index，或者x所在区间的前面任何一个区间的元素的index，在调用Search(x,index)，其时间肯定不超过2n/L，而且期望时间是n/L。而根据S中元素分布的均匀性，a1,a2,…,an排列的前L个元素在概率上，是由ao1ao2…aon的L划分中，每个区间各取一个元素组成的，所以会出现：ao1ao2…aon的L划分中x所在区间中在x之前的元素，或者是，x所在区间的前面任何一个区间的元素，满足这两点中的任意一点即可，数越大越靠近X。那么算法可以这么描述：找S的a1,a2,…,an序列的前L个元素中最大的数，得到它的index，然后用Search(x,index)，经过期望时间n/L，最终找到x，则时间复杂度是O(L+n/L)，当L=√n时取到最小值O(2√n)B(x){//设x在val[1..n]中i←head;max←val*i+;//max初值是表val中最小值forj←1to√ndo{//在val的前个√n数中找不大于xy←val*j+;//的最大整数y相应的下标iifmaxy≤xthen,i←j;max←y;}//endif}//endforreturnSearch(x,i);//从y开始继续搜索}C(x)，时间复杂度O(√𝐧)，平滑B(x)在不同实例上的执行时间C(