随机化算法

  • 整数伪随机数、实数伪随机数生成方法
  • 随机化算法的基本概念
  • 随机化算法分类
    • 舍伍德算法(Sherwood)、Las Vegas算法、Monte Carlo算法
    • 不同类型算法的主要特点
  • 具体算法
    • 求解数值问题的随机化算法设计
    • Sherwood线性时间选择算法
    • Las Vegas快排算法—-期望时间复杂度
    • 素数测试问题的Monte Carlo算法

随机算法指的是利用随机数来决定算法的下一步的方法。比如说,在快速排序中,我们可以随机选择 pivot。利用随机数可以减小时间复杂度与空间复杂度。这些算法大多需要用到概率论的知识。

随机数

线性同余法(Linear congruential generator) 是生成伪随机数的最常用的方法。其过程如下:

用户需要提供一个数 $x_0$ 作为 随机序列的种子。然后代入如下公式:

  • $a$ 称为乘数(he constant multiplier)
  • $b$ 称为增量(the increment)
  • $m$ 称为模数(the modulus)

显然,这个算法并不是完全随机的,而是有一定周期。周期的上界是 $m$,故 $m$ 要充分大,并且要满足:

  1. $b,m$ 互质
  2. $m$ 的所有质因数要整除 $a-1$
  3. $m$ 是 4 的倍数,$a-1$ 也是
  4. $a,b,x_0$ 比 $m$ 小
  5. $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()

lcg

利用随机数的数值计算

利用随机性可以算出任意面积的积分(包括定积分)。我们可以将代求面积 $S_?$ 放在一个正方形面积 $S_0$ 中。然后向里面随机撒 $n_0$ 豆子,落在代求面积中的豆子有 $n_?$ 个,则:

下面我们来尝试计算一下圆周率。考虑一个正方形与其内切圆,如果向这个正方形内撒一把豆子,则在园内的概率为:$\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$ 则平均时间为:

经过舍伍德算法改进后,处理时间变为 $t_B(x)=\overline{t_A}(n)+s(n)$,$s(n)$ 是随机算法导致的差异,从而平均时间为:

牺牲了平均时间来改进最差时间。

拉斯维加斯算法