5.1.3 Randomized algorithms ●ldea 我们可能不知道输入的分布,也可能无法对输入 的分布进行可计算的建模 在算法中通过对输入进行随机化处理,从而为输 入强加一种分布
12 5.1.3 Randomized algorithms ⚫ Idea ◆ 我们可能不知道输入的分布，也可能无法对输入 的分布进行可计算的建模 ◆ 在算法中通过对输入进行随机化处理，从而为输 入强加一种分布
5.1.3 Randomized algorithms ●对雇用问题,改变策略: 猎头公司预先提供n个候选人列表 每天,我们随机选取一人进行面试 无须担心候选人是否被随机提供,我们通过随机 运算预处理可以控制候选人的随机顺序(§53)
13 5.1.3 Randomized algorithms ⚫ 对雇用问题，改变策略: ◆ 猎头公司预先提供n 个候选人列表 ◆ 每天，我们随机选取一人进行面试 ◆ 无须担心候选人是否被随机提供，我们通过随机 运算预处理可以控制候选人的随机顺序(§5.3)
5.1.3 Randomized algorithms 随机算法:如果一个算法的行为不只是由输入决定,同 时也由随机数生成器所产生的数值决定,则称这个算法 是随机的。 随机数生成器 RANDOM ◆ RANDOM(a,b返回一个介于a与b的整数,而每个 整数出现的机会均等。 and each of the b-a+1 possible values of r is equally likely. ◆RAND0M实际上由一个确定的算法〔伪随机产生器〕产 生,其结果表面上看上去像是随机数
14 5.1.3 Randomized algorithms ⚫ 随机算法： 如果一个算法的行为不只是由输入决定，同 时也由随机数生成器所产生的数值决定，则称这个算法 是随机的。 ⚫ 随机数生成器RANDOM ◆ RANDOM(a, b)返回一个介于 a与b 的整数，而每个 整数出现的机会均等。and each of the b-a+1 possible values of r is equally likely. ◆ RANDOM实际上由一个确定的算法〔伪随机产生器〕产 生，其结果表面上看上去像是随机数
5.1.3 Randomized algorithms 随机数产生器 Most random number generators generate a sequence of integers by the following recurrence Xo=a given integer(seed), XH1=axi mod M For example, for Xo=1, a=5, M=13, we have X1=5%13=5,X2=25%13=12,X3=60%13=8.Each integer in the sequence lies in the range 0, M-1 15
15 5.1.3 Randomized algorithms ⚫ 随机数产生器 ◆ Most random number generators generate a sequence of integers by the following recurrence ◆ X0= a given integer (seed), Xi+1 = aXi mod M ◆ For example, for X0=1, a=5, M=13, we have X1=5%13=5, X2=25%13=12, X3= 60%13=8. Each integer in the sequence lies in the range [0, M - 1]