- 整数伪随机数、实数伪随机数生成方法
- 随机化算法的基本概念
- 随机化算法分类
- 舍伍德算法(Sherwood)、Las Vegas算法、Monte Carlo算法
- 不同类型算法的主要特点
- 具体算法
- 求解数值问题的随机化算法设计
- Sherwood线性时间选择算法
- Las Vegas快排算法—-期望时间复杂度
- 素数测试问题的Monte Carlo算法
随机算法指的是利用随机数来决定算法的下一步的方法。比如说，在快速排序中，我们可以随机选择 pivot。利用随机数可以减小时间复杂度与空间复杂度。这些算法大多需要用到概率论的知识。
随机数
线性同余法（Linear congruential generator） 是生成伪随机数的最常用的方法。其过程如下：
用户需要提供一个数 $x_0$ 作为 随机序列的种子。然后代入如下公式：
\[x_i = (ax_{i-1}+b)\,\mathrm{mod} \,m\]- $a$ 称为乘数（he constant multiplier）
- $b$ 称为增量（the increment）
- $m$ 称为模数（the modulus）
显然，这个算法并不是完全随机的，而是有一定周期。周期的上界是 $m$，故 $m$ 要充分大，并且要满足：
- $b,m$ 互质
- $m$ 的所有质因数要整除 $a-1$
- $m$ 是 4 的倍数，$a-1$ 也是
- $a,b,x_0$ 比 $m$ 小
- $a,b$ 是正整数
想要深入了解，可以看看北大李东风老师的 均匀分布随机数生成
计算得到的 $x_i$ 可以近似看作是落在 $[0, m-1]$ 之间的随机数。
"""
利用 lcg 算法生成 100000 个 0~99 之间的随机数，
统计每个数出现的数量，并作出柱状图
"""
import matplotlib.pyplot as plt
def lcg(modulus, a, b, seed):
"""Linear congruential generator."""
while True:
seed = (a * seed + b) % modulus #
yield seed
n=100000
length=100
stats=dict([(i,0) for i in range(length)])
for i in lcg(2**20, 4*20+1, 1303, 5):
num=i%length
stats[num]+=1
if n<0:
break
n-=1
plt.bar(range(length), [stats[i] for i in range(length)])
plt.show()
利用随机数的数值计算
利用随机性可以算出任意面积的积分（包括定积分）。我们可以将代求面积 $S_?$ 放在一个正方形面积 $S_0$ 中。然后向里面随机撒 $n_0$ 豆子，落在代求面积中的豆子有 $n_?$ 个，则：
\[\frac{S_?}{S_0}=\frac{n_?}{n_0}\\ \Rightarrow S_? = \frac{S_0 n_?}{n_0}\]下面我们来尝试计算一下圆周率。考虑一个正方形与其内切圆，如果向这个正方形内撒一把豆子，则在园内的概率为：$\dfrac{\pi r^2}{ 4 r^2}=\dfrac{n_?}{n_0}$，从而，$\pi=\dfrac{4n_?}{n_0}$。
#版权声明：本文为CSDN博主「Tab_」的原创文章，遵循CC 4.0 #BY-SA版权协议，转载请附上原文出处链接及本声明。
#原文链接：https://blog.csdn.net/weixin_45506775/java/article/details/104280020
from random import random,seed
seed(123)
darts = 100000
hits = 0.0
for i in range (darts):
x,y = random(),random()
d = pow(x**2+y**2,0.5)
if d <= 1.0:
hits = hits+1
pi = 4*(hits/darts)
print("圆周率的值为:{:.6f}".format(pi))
#运行结果
#圆周率的值为:3.138600
舍伍德（Sherwood）算法
严格来说，舍伍德算法只能算一种处理方法，并不是算法。以之前的快排算法为例，其复杂度 $O(n\log n)$ 是取平均来计算，但最差情况下的复杂度为 $O(n^2)$，为了消除这种情况，我们可以随机选取 pivot 值，这样复杂度就与输入无关。
用数学语言描述就是：设输入大小为 $n$ 的实例 $x$，对应的时间为 $t_A(x)$，记全体大小为 $n$ 的实例集合为 $X_n$，总数为 $\vert X_n\vert$ 则平均时间为：
\[\overline{t_A}(n) = \frac{1}{|X_n|}\sum_{x \in X_n} t_A(x)\]经过舍伍德算法改进后，处理时间变为 $t_B(x)=\overline{t_A}(n)+s(n)$，$s(n)$ 是随机算法导致的差异，从而平均时间为：
\[\overline{t_B}(n) = \frac{1}{|X_n|}\sum_{x \in X_n} t_B(x)\\ =\overline{t_A}(n)+s(n)\]牺牲了平均时间来改进最差时间。