随机算法 东南大学计算机学院方效林
东南大学计算机学院 方效林 随机算法
本章内容 随机算法的基本概念 随机采样问题 第k小元素问题的随机算法 Sherwood随机化方法 判断字符串是否相等问题 子串匹配问题 求最近点对的随机算法 素数测试
本章内容 ◼ 随机算法的基本概念 ◼ 随机采样问题 ◼ 第k小元素问题的随机算法 ◼ Sherwood随机化方法 ◼ 判断字符串是否相等问题 ◼ 子串匹配问题 ◼ 求最近点对的随机算法 ◼ 素数测试 2
随机算法的基本概念 例子 o判断函数f(x1,x2X)在区域D中是否恒为0, 2 f很复杂,不能数学化简,如何判断就很麻烦 o若随机产生一个n维坐标(r2)D,代入 得f(r,2rn)≠0,则可判定区域D内f不恒为0 o若对很多个随机产生的坐标进行测试,结果次 次均为0,则可说f0的概率是非常小 有不少问题,目前只有效率很差的确定性求解 算法,但用随机算法去求解,可以很快地获 得相当可信的结果 3
随机算法的基本概念 ◼ 例子 判断函数 f(x1 ,x2 ,…xn )在区域 D中是否恒为0， f 很复杂，不能数学化简，如何判断就很麻烦 若随机产生一个n维坐标(r1 ,r2 ,… rn )D，代入 得f(r1 ,r2 ,… rn )≠0，则可判定区域D内f不恒为0 若对很多个随机产生的坐标进行测试，结果次 次均为0，则可说f≠0的概率是非常小 ◼ 有不少问题，目前只有效率很差的确定性求解 算法， 但用随机算法去求解，可以很快地获 得相当可信的结果 3
随机算法的基本概念 随机算法 o随机算法是一种使用概率和统计方法在其执行过程 中对于下一计算步骤作出随机选择的算法 ■随机算法的优越性 o对于有些问题:算法简单 对于有些问题:时间复杂性低 o对于有些问题:同时兼有简单和时间复杂性低
随机算法的基本概念 ◼ 随机算法 随机算法是一种使用概率和统计方法在其执行过程 中对于下一计算步骤作出随机选择的算法 ◼ 随机算法的优越性 对于有些问题：算法简单 对于有些问题：时间复杂性低 对于有些问题：同时兼有简单和时间复杂性低 4
随机算法的基本概念 ■随机算法分类 o随机数值算法 Monte Carlo算法 Las Vegas算法 Sherwood算法 随机数值算法 o主要用于数值问题求解 o算法的输出往往是近似解 o近似解的精确度与算法执行时间成正比
随机算法的基本概念 ◼ 随机算法分类 随机数值算法 Monte Carlo算法 Las Vegas算法 Sherwood算法 ◼ 随机数值算法 主要用于数值问题求解 算法的输出往往是近似解 近似解的精确度与算法执行时间成正比 5