算法设计与分析8

《算法设计与分析8》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、概率算法随机数概念伪随机数生成算法几种主要的概率算法Sherwood算法LasVegasLasVegas算法MonteCarlo算法1伪随机数随机数与伪随机数概率算法中要进行随机选择，需要大量随机数.通常根据某种规则生成随机数，这些随机数不是真正随机的，但在一定程度上可以模拟随机数，一般叫做伪随机数随机变量X的取值范围是((,)0,1)且对任意的0

2、,机器最大数.乘数：b,2≤b

3、om(i,j)//产生a,,,…,a之间随机数ij1.产生伪随机数x//乘同余法2.n←j−i+1//总个数n2.fork←1tondo//检查第k个区间3i3.iffx/m≤k/nthenx←akik+i−14.return//0k/nx/m≤k/n6确定型算法与随机算法1.特点：确定型算法:对某个特定输入的每次运行过程是可重复的，运行结果是一样的.随机算法：对某个特定输入的每次运行过程是随机的，运行结果也可能是随机的.2.随机算法的优势：在运行时间或者空间需求上随机算法比确定型算法往往有较好的改进随机算法设计简单7随机

4、算法复杂性度量随机算法A对于规模为n的某个给定的实例I的一次执行的时间与另一次可能不一样.随机算法A对于某个规模为n的实例I的运行时间的期望：算法A反复求解实例I的平均时间.一般情况下，许多随机算法对于规模为n的不同的实例，运行时间期望都一样，因此这个期望时间代表随机算法的平均预期时间.8Sherwood算法例1快速排序的随机算法算法RandQuicksort(A,p,r)1.ifp

5、ndom(p,r)2.A[i]↔A[p]3.returnPartition(A,p,r)9算法比较确定型排序算法Quicksort最坏情况下时间为O(n2)平均情况下为O(nlogn)确定型排序+选择算法如果选用中位数进行划分,时间为O(nlogn)随机快速排序算法预期时间O(nlogn)最坏情况概率非常小，在实际应用中可以忽略10例2随机选择算法算法RandSelect(A,p,r,k)//从A[p..r]中选第k小1if1.ifp=rthenreturnthenreturnA[p]2.i←Random(p,r)3.以A[i]为标准划分A4.j←划分后小于等于A[i]的数构成数组的大小5.

6、ifk≤j6.thenreturnRandSelect(A,p,p+j-1,k)7.elsereturnRandS(Select(A,p+j,r,k-j)11时间期望值估计假设随机选择时，1..n中每个数被选的概率相等，并且假设第k个数总是出现在划分后两个数组中较大的数组（最坏情况的上界）.那么，随机选择算法的时间期望为1nT(n)≤(T(n−1)+T(n−2)+...T(+1)n2nn+T()+T(+1)+...+T(n−1))+O(n)222n−1≤∑T(i)+O(n)ni=n/2注意n为奇数，上式没有T(n/2)项12时间的期望（续）n−12T(n)≤∑T(i)+tnni=n/2设T(

7、k)≤ck对对切一切k