算法设计与分析ch8

《算法设计与分析ch8》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第八章RandomizedAlgorithms骆吉洲计算机科学与工程系8.1IntroductiontoRandomizedAlgorithms8.2RandomizedNumericalAlgorithms8.3RandomizedSelectionAlgorithm8.4RandomizedAlgorithmtoTestWhetherNumberisPrime8.5RandomizedSortingAlgorithm8.6RandomizedMin-CutAlgorithm提要参考文献《计算机算法设计与分

2、析》第7章《RandomizedAlgorithms》RajeevMotwaniandPrabhakar,Raghavan,CambridgeUniversityPress《网站资料》第8章8.1IntroductiontoRandomizedAlgorithms随机算法的基本概念随机算法的分类随机算法的性能分析方法随机算法的基本概念随机算法的分类随机算法的性能分析方法什么是随机算法随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法随机算法的优越性对于有些问题:算法简单对于有些问

3、题:时间复杂性低对于有些问题:同时兼有简单和时间复杂性低随机算法的随机性对于同一实例的多次执行,效果可能完全不同时间复杂性的一个随机变量解的正确性和准确性也是随机的随机算法的基本概念随机算法的分类随机数值算法主要用于数值问题求解算法的输出往往是近似解近似解的精确度与算法执行时间成正比MonteCarlo算法主要用于求解需要准确解的问题算法可能给出错误解获得精确解概率与算法执行时间成正比LasVegas算法一旦找到一个解,该解一定是正确的找到解的概率与算法执行时间成正比增加对问题反复求解次数,可是求解无效的概率

4、任意小Sherwood算法一定能够求得一个正确解确定算法的最坏与平均复杂性差别大时,加入随机性,即得到Sherwood算法消除最坏行为与特定实例的联系随机算法分析的特征仅依赖于随机选择,不依赖于输入的分布确定算法的平均复杂性分析:依赖于输入的分布对于每个输入都要考虑算法的概率统计性能随机算法分析的目标平均时间复杂性:时间复杂性随机变量的均值获得正确解的概率获得优化解的概率解的精确度估计随机算法的性能分析8.2RandomizedNumericalAlgorithms随机算法的基本概念随机算法的分类随机算法的性

5、能分析方法计算值计算定积分计算值数学基础设有一个半径为r的园及其外切四边形向正方形随机地投掷n个点,设k个点落入园内投掷点落入园内的概率为(r2)/(4r2)=/4.用k/n逼近/4,即k/n/4,于是(4k)/n.我们可以令r=1用投掷n个点的方法计算算法K=0;Fori=1Ton随机地产生四边形中的一点(x,y);Ifx2+y21Thenk=k+1;EndforReturn(4k)/n时间复杂性=O(n)不是输入的大小,而是随机样本的大小解的精确度随着随机样本大小n增加而增加计算定积

6、分问题计算积分数学基础令f(x)是区间[a,b]上的一组独立、同分布的随机变量{i}的任意密度函数令g*(x)=g(x)/f(x),则{g*()}是密度为f(x)的随机变量集合,而且由强大数定律我们可以用来近似计算I令f(x)=1/(b-a)axb索求积分可以由如下I’来近似计算I算法I=0;Fori=1Ton随机产生[a,b]中点x;I=I+g(x);EndforReturn(b-a)*I/n时间复杂性=O(n)不是输入的大小,而是随机样本的大小解的精确度随着随机样本大小n增加而增加8.3Rando

7、mizedSelectionAlgorithms问题的定义随机算法算法的性能分析问题的定义输入:S={x1,x2,…,xn}，整数k，1kn.输出:S中第k个最小元素.记号Rank(Q,t)=集合Q中的元素t的rank(第k小元素的rank是k)min(Q,i)=集合Q中第i个最小元素.随机算法基本思想从S中随机地抽取n3/4个样本存入R,排序RS中第k最小元素可能成为R中x=kn3/4/n最小元素为了解决误差问题,我们考察区间[x-n1/2,x+n1/2]xrlrhr1rn3/4lh………………LH把S

8、中属于[L,H]数据存入P在P中查找min(S,k)LAZYSELECT(S,k)R=独立、均匀、可放回地从S随机选取的n3/4元素;在O(nlogn)时间内排序R;x=(k/n)n3/4;/*(k/n)n3/4=kn-1/4*/l=max{,0};h=min{,n3/4};L=min(R,l);H=min(R,h);Lp=Rank(S,L),Hp=Rank(S,H);/*L和H与S元素比较*/P=