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

概率算法
随机数
概念
伪随机数生成算法
几种主要的概率算法
Sherwood算法
Las Vegas算法
Monte Carlo算法
1
伪随机数
随机数与伪随机数
概率算法中要进行随机选择,需要大量随机数.
通常根据某种规则生成随机数,这些随机数不
是真正随机的,但在一定程度上可以模拟随机
数,一般叫做伪随机数
随机变量X的取值范围是(0,1)且对任意的0<a<1,
P{0<X≤a}=a, 则称X服从(0,1)上的均匀分布
2
伪随机数生成算法
伪随机数生成算法---线性同余法
生成伪随机序列为{ai}, i= 0,1,…, n,…,
0<ai<m
⎧a0 = d
⎨
⎩ an = (ban−1 + c)mod m n = 1,2,...
模数:m, 机器最大数.
乘数:b, 2≤b<m,计算前给定
常数:c, 0≤c<m,计算前给定
种子:d, 0≤d<m, 计算时随机给出 3
乘同余法
⎧a0 = d
⎨
⎩ an = ban−1 mod m n = 1,2,...
参数:c = 0,d ≠ 0,m=231-1, b=75
实例:d=1
16,807, 282,475,249,
1,622,650,073, 984,943,658,
1,144,108,930, 470,211,272,
101,027,544, 1,457,850,878
……
4
离散型伪随机数的产生
输入:P={ai, ai+1, …, aj},
输出:伪随机数ak∈P
算法:Random(i, j) // 产生ai,…,aj之间随机数
1. 产生伪随机数x //乘同余法
2. n ← j−i+1 //总个数n
3. for k←1 to n do // 检查第k个区间
4. if x/m ≤ k/n then x←ak+i-1 // 0<x<m
5. return
5
确定型算法与随机算法
:
确定型算法: 对某个特定输入的每次运行过程
是可重复的,运行结果是一样的.
随机算法:对某个特定输入的每次运行过程是随机
的,运行结果也可能是随机的.
2. 随机算法的优势:
在运行时间或者空间需求上随机算法比确定型算法
往往有较好的改进
随机算法设计简单
6
随机算法复杂性度量
随机算法A对于规模为n的某个给定的实例I 的一次
执行的时间与另一次可能不一样.
随机算法A对于某个规模为n的实例I 的运行时间的
期望:算法A反复求解实例I 的平均时间.
一般情况下,许多随机算法对于规模为n的不同的实
例,运行时间的期望都一样,因此这个值代表随机
算法的平均时间的期望.
7
Sherwood算法
例1 快速排序的随机算法
算法 RandQuicksort(A,p,r)
1. if p<r then
2. q←RandPartition(A,p,r)
3. RandQuicksort(A,p,q-1)
4. RandQuicksort(A,q+1,r)
算法 RandPartition(A,p,r)
1. i←Random(p,r)
2. A[i]↔A[p]
3. return Partition(A,p,r) 8
算法比较
确定型排序算法 Quicksort
最坏情况下时间为O(n2)
平均情况下为 O(nlogn)
确定型排序+选择算法
如果选用中位数进行划分, 时间为O(nlogn)
随机快速排序算法
期望时间 O(nlogn)
最坏情况概率非常小,在实际应用中可以忽略
9
例2 随机选择算法
算法 RandSelect(A, p, r, k) //从A[p..r]中选第k小
1. if p=r then return A[p]
2. i←Random(p, r)
3. 以A[i]为标准划分A
4. j←划分后小于等于A[i]的数构成数组的大小
5. if k≤ j
6. then return RandSelect(A, p, p+j-1, k)
7. else return RandSelect(A, p+j, r, k-j)
10