大学生创业贷款政策.ppt

概率算法
随机数
概念
伪随机数生成算法
几种主要的概率算法
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
模数:m, 机器最大数.
乘数:b, 2b<m,计算前给定
常数:c, 0c<m,计算前给定
种子:d, 0d<m, 计算时随机给出
伪随机数生成算法
3
乘同余法
参数: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
5. then x←ak+i1
6. return // 0<x<m
5
算法Random (i, j)
1
m
ai
aj
x
x/m>k/n
x/mk/n
ai+k-1
6
特点:
确定型算法: 对某个特定输入的每次运行过程是可重复的,运行结果是一样的.
随机算法:对某个特定输入的每次运行过程是随机的,运行结果也可能是随机的.
随机算法的优势:
在运行时间或者空间需求上随机算法比确定型算法往往有较好的改进
随机算法设计简单
确定型算法与随机算法
7
随机算法复杂性度量
随机算法 A 对规模为n 的某个实例 I 的两次执行时间可能不一样.
随机算法 A 对某个规模为 n 的实例 I 执行时间的期望:算法 A 反复求解实例 I 的平均时间.
一般情况下,许多随机算法对于规模为n 的不同的实例的执行时间的期望都一样,因此这个期望值代表随机算法的平均时间复杂度.
8
算法 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) 随机选择一个参照数作为轴
快速排序的随机算法
Sherwood算法
9
确定型排序算法 Quicksort
最坏情况下时间为O(n2)
平均情况下为 O(nlogn)
随机快速排序算法
预期时间 O(nlogn)
最坏情况概率非常小,在实际应用中可以忽略
算法比较
10