《北京大学屈婉玲算法设计与分析最新课件09》由会员分享，可在线阅读，更多相关《北京大学屈婉玲算法设计与分析最新课件09（44页珍藏版）》请在金锄头文库上搜索。
1、第第9章 随机算法章 随机算法 Las Vegas 型随机算法型随机算法 随机快速排序随机快速排序随机快速排序随机快速排序 随机选择随机选择 随机随机 后放置后放置随机随机 n后放置后放置 Monte Carlo型随机算法型随机算法 主元素测试主元素测试主元素测试主元素测试 串相等测试串相等测试 模式匹配模式匹配模式匹配模式匹配 素数测试素数测试 随机算法的分类与局限性随机算法的分类与局限性 随机快速排序算法随机快速排序算法随机快速排序算法随机快速排序算法 算法算法9.1 随机快速排序算法随机快速排序算法 输入输入包含包含个元素的数组个元素的数组输入输入：包含包含 n 个元素的数组个元素的数组
2、 输出：经过排序的输出：经过排序的 n 个元素的数组个元素的数组 若数组包含若数组包含或或个元素则返回个元素则返回1. 若数组包含若数组包含 0 或或 1 个元素则返回个元素则返回 2. 从数组中随机选择一个元素作为从数组中随机选择一个元素作为枢轴枢轴元素元素 把把数组元素分为个子数组数组元素分为个子数组并且按照并且按照顺序顺序排列排列3. 把把数组元素分为数组元素分为三三个子数组个子数组，并且按照并且按照 A, B, C 顺序顺序排列排列 A：包含比枢轴元素小的元素；：包含比枢轴元素小的元素； B：包含与枢轴元素相等的元素；：包含与枢轴元素相等的元素； C：包含比枢轴元素大的元素：包含比枢轴
3、元素大的元素. 4对对 A 和和 C 递归地执行上述步骤递归地执行上述步骤. 算法分析算法分析算法分析算法分析 定理定理9.1 设数组含设数组含n个不同元素，对任意常数个不同元素，对任意常数 0，随机快速 排序算法的期望比较次数 ，随机快速 排序算法的期望比较次数 T(n) 2 n ln n. 证明证明一一 ：求解递推式求解递推式证明证明：求解递推式求解递推式 随机选取枢轴元素，其位于排序后第随机选取枢轴元素，其位于排序后第 i 位置位置 (i=1,2,n)的概的概 率是率是1/n，A和和C的元素数分别是的元素数分别是 i 个和个和 n i 1个个, 得得率是率是1/n，A和和C的元素数分别是
4、的元素数分别是 i 个和个和 n i 1个个, 得得 )1()( 1 )1()( 1 1 +=+= = = inTiT n nnT n i 解为解为 (nlogn). 可归纳证明精确上界是可归纳证明精确上界是 T(n) 2n ln n. xdxxniinnT n n ln2 2 )1(ln2 2 )1()( 1 + + + + = = nn n nnn xdxx n nii n nnT i ln2) 2 1 2 ln( 2 )1( ln2)1(ln2)1()( 2 2 1 1 + + + + + = = n22 随机选择算法随机选择算法随机选择算法随机选择算法 算法算法 RandSelect(
5、A, p, r, k) /从从Apr中选第中选第k小小 1. if p=r then return Ap 2. i Random(p, r)(p, ) 3. 以以 Ai 为标准划分为标准划分 A 4. j 划分后小于等于划分后小于等于 Ai 的数构成数组的大小的数构成数组的大小j划分后小于等于划分后小于等于 的数构成数组的大小的数构成数组的大小 5. if k j 6.then return RandSelect (A, p, p+j-1, k)6. then return RandSelect (A, p, p j 1, k) 7. else return RandSelect (A, p+
6、j, r, k-j) 4 时间期望值估计时间期望值估计时间期望值估计时间期望值估计 假设假设1 n 中每个数被选的概率相等，并且假设第中每个数被选的概率相等，并且假设第 k 个数总是个数总是 出现在划分后两个数组中较大的数组出现在划分后两个数组中较大的数组 ，算法的期望时间为算法的期望时间为出现在划分后两个数组中较大的数组出现在划分后两个数组中较大的数组 ，算法的期望时间为算法的期望时间为 )1 2 (.)2()1( 1 )( n TnTnT n nT+ )()( 2 )()1(.)1 2 () 2 ( 1 2/ nOiT n nOnT n T n T n ni + = = 归纳归纳归纳步骤如
7、归纳步骤如假设对假设对命题为真命题为真 n n n cnn 2 ) 1 2 ( 22 + + 归纳归纳证明证明 T(n) cn. 归纳步骤如归纳步骤如下：下：假设对假设对 k=+=+pppppp 调用调用 k 次次M ji算法正确的概率为算法正确的概率为 kkk pppppppp =+=+21)1 (1)1 (.)1 ()1 ( 12 调用调用 k 次次Majority算法正确的概率为算法正确的概率为 调用次数调用次数 k123456 正确概率大于正确概率大于0.50.750.8750.9380.9690.985 12 改进途径改进途径改进途径改进途径 对于任意给定的 对于任意给定的 0, 如
8、果要使出错的概率不超过 ，则调用如果要使出错的概率不超过 ，则调用 次数次数 k 满足满足 2 1 2 1 logloglog)(kk k 次数次数 k 满足满足 1 loglog kk 出错概率不超过出错概率不超过 的算法的算法MCMajority 算法算法 MCMajority(T,n, ) 1. k log(1/ ) 2. for i1 to k 3if M jit (T) thtt3. if Majority(T,n) then return true 4. return false 13 串相等测试串相等测试串相等测试串相等测试 问题：问题：A 有一个长串有一个长串 x, B 有长串
9、有长串 y，A 和和 B 希望知道希望知道 x=y? 方法方法方法方法一一： A 将将 x 发送给发送给 B，B 测试测试 x = y? 发送消耗发送消耗长串占用信道资源大长串占用信道资源大发送消耗发送消耗：长串占用信道资源大长串占用信道资源大 方法二方法二： A用用导出一个短串导出一个短串 f( )(fingerprints)A 用用 x 导出一个短串导出一个短串 f(x) (fingerprints) A 将将 f(x) 发送到发送到 B B 使用同样方法导出相对于使用同样方法导出相对于 y 的短串的短串 f(y)B 使用同样方法导出相对于使用同样方法导出相对于 y 的短串的短串 f(y)
10、 B 比较比较 f(x) 与与 f(y) 如果如果 f(x) f(y)，则，则 x y; 如果如果 f(x) = f(y)，则不确定，则不确定. 14 指纹产生指纹产生指纹产生指纹产生 设设 x 和和 y 的二进制表示为正整数的二进制表示为正整数 I(x), I(y) 选择素数选择素数指纹函数为指纹函数为选择素数选择素数 p, 指纹函数为指纹函数为 Ip(x) = I(x) mod p A 传送传送 p 和和 Ip(x) 给给 B. 当当 p 不太大时，传送一个短串不太大时，传送一个短串. 存在问题存在问题存在问题存在问题： x = y Ip(x) = Ip(y) I (x) = I (y)x
11、 = yIp(x) Ip(y) x y 出错条件：固定出错条件：固定 p | (I(x)I(y)p | (I(x) I(y) 15 改进算法的途径改进算法的途径改进算法的途径改进算法的途径 改进方法： 随机选择素数改进方法： 随机选择素数 p 进行测试进行测试 算法算法 StringEqualityTest 1. 随机选择小于随机选择小于 M 的素数的素数 p/M为正整数为正整数 2. A 发送发送 p 和和 Ip(x) 给给 B 3. B 测试是否测试是否 Ip(x) = Ip(y) p( )p(y) 出错的必要条件：出错的必要条件： 的位数等于的位数等于的位数的位数x 的位数等于的位数等于
12、 y 的位数的位数 p | (I(x) I(y) 16 有关素数的性质有关素数的性质有关素数的性质有关素数的性质 函数函数 (t): 小于小于 t 的不同的素数个数，的不同的素数个数， 例如例如， (20)=8, 素数素数8个个：2, 3, 5, 7, 11, 13, 17, 19例如例如(), 素数素数 个个, , , , 两个相关结果：两个相关结果： 素数定素数定l /)(1) 素数定素数定理理 (2) 若若 k2n, n不太小，整除不太小，整除 k 的不同素数个数小于的不同素数个数小于 (n) tttln/)( n103104105106107 (n)168122995927849866
13、4579 t/lnt1451086868672382620421 比值比值1.1591.1321.1041.0851.071 k 210 =1024, 整除整除 k 的素数个数的素数个数 (10) = 4, 例如例如 k = 984，整除整除 984 的素数只有的素数只有 2, 3, 41 17 例如例如 k 984，整除整除 984 的素数只有的素数只有 2, 3, 41 出错概率估计出错概率估计出错概率估计出错概率估计 n: x 和和 y 的二进制表示的位数的二进制表示的位数 x y 2nx, y 2n 若选择若选择 M 2n2, 一一次测试的次测试的出错概率估计出错概率估计： yIxIp
14、pp n |)()(2| |整除的素数，且是小于整除的素数，且是小于 若选择若选择,次测试的次测试的出错概率估计出错概率估计： nnnnn M 1ln/ln/)( )( nnnnnMln2/2)2ln(/2)( 222 18 改进算法改进算法改进算法改进算法 重复执行重复执行 j 次，每次随机选择小于次，每次随机选择小于M 的素数的素数 算法算法 StringTest 输入：输入：x, y，n位二进制数位二进制数 输出：“输出：“Yes” (如果如果x = y); 或者“或者“No” (如果如果 x y) 1. for i1 to j 2. 随机选择小于随机选择小于M 的素数的素数 p / M
15、为正整数为正整数 3. A 发送发送 p 和和 Ip(x) 给给 B 测试测试4. B 测试测试 5. if Ip(x) Ip(y) 6tht“N ”6. then return “No” 7. return”Yes” 19 算法分析算法分析算法分析算法分析 令令 j = loglogn , 则算法出错的概率则算法出错的概率 n j nn loglog 1 ) 1 ( 实例 ：实例 ：x 和和 y 是是1000000位二进制数位二进制数 n = 106 M = 2 1012 = 240.8631 素数素数 p 的二进制表示至多 的二进制表示至多 log M +1 = 41 位位 I (x) 的位数至多的位数至多 log(p-1) + 1 log M +1 = 41Ip(x) 的位数至多的位数至多 log(p-1)
