算法与计算复杂性课程(7)概率算法

《算法与计算复杂性课程(7)概率算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、生伪随机数x//乘同余法2.n←j−i+1//总个数n3.fork←1tondo//检查第k个区间4.ifx/m≤k/nthenx←a//0

4、时间的期望：算法A反复求解实例I的平均时间.一般情况下，许多随机算法对于规模为n的不同的实例，运行时间的期望都一样，因此这个值代表随机算法的平均时间的期望.7Sherwood算法例1快速排序的随机算法算法RandQuicksort(A,p,r)1.ifp

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

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

7、−1)2c22=+tnn2c3n3cnc=(−1)+tn=−+tn22423cn3t≤+tn=(+)cn≤cn取c≥4t即可44c12算法比较拟中位数选择算法最坏情况O(n)平均情况O(n)随机算法平均时间O(n)最坏情况O(n2)每次恰好选到边界元素与实例无关，只与选择有关概率很小，可以忽略期望时间O(n)13预期复杂度分析设A为求解问题π的确定型算法，B为对应的Sherwood算法，对于输入x的计算时间分别记为t(x),t(x).令ABX={x

8、x为π的实例,

9、x

10、=n}n输入等概率分布情况下，A的平均时间复杂