随机算法（上）

1. 随机算法的介绍

1.1 随机算法基本概念

           随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法。随机算法具有一定的优越性：对于有些问题 ，算法简单；对于有些问题，时间复杂性低；对于有些问题，同时兼有简单和时间复杂性低。随机算法具有随机性：对于同一实例的多次执行，效果可能完全不同；时间复杂性是一个随机变量；解的正确性和准确性也是随机的。常见的随机算法分为随机数值算法、Monte Carlo算法、Las Vegas算法、Sherwood算法。

         

1.2 随机算法的性能分析

           随机算法分析的特征：仅依赖于随机选择，不依赖于输入的分布；确定算法的平均复杂性分析依赖于输入的分布；对于每个入都要考虑算法的概率统计性能。

           随机算法分析的目标：平均时间复杂性是时间复杂性随机变量的均值；获得正确解的概率；获得优化解的概率；解的精确度估计。

2. 随机数值算法

2.1 计算π

       设有一个半径为r的圆，其外切四边形的边长则为2r。利用面积之比P，可得π = 4*P。因此若想求得π值，只需要利用随机算法求出这个比率P即可。算法步骤如下：

       k = 0

       For i = 1 To  n:

            产生一个点（x,y）使其落在四边形内；

            如果（x,y）也落在圆内，k = k + 1;

       return (4k) / n;

      该算法的时间复杂性为O(n), 解的精确度随着样本大小n增加而增加。

2.2 计算定积分

           算法步骤如下：

           I = 0

           For i = 1 To n :

               产生（a,b）上一点x

               I = I + g(x)

           EndFor

           return I * (b - a) / n

           该算法的时间复杂性为O(n)，其中n为样本的大小；解的精度随着样本大小n的增加而增加。