[关闭]
@zqbinggong 2018-03-06T13:37:27.000000Z 字数 510 阅读 389

chap5 概率分析和随机算法

最大子数组 分治策略 算法导论

内容

一些定义

  1. 随机算法:如果一个算法的行为不仅由输入决定,而且也由随机生成器产生的数值决定,则称这个算法是随机的
  2. 概率分析和随机算法的区别:前者是假设输入是随机的,后者是将给定输入打乱

雇佣问题

  1. 只要遇见更好的应聘者,就立即雇佣并解雇当前工作人员,直到n个候选人都应聘完
  2. 当应聘者以随机次序出现,则总的雇佣费用的平均值为,c为雇佣费用

随机算法

随机排列数组

  1. 对每个元素赋予一个优先级,然后根据优先级来进行排序,可以证明,当每个元素的优先级都不同时,该过程能够产生一个均匀随机排列

2. 该算法的运行时间主要由排序过程决定

Permutate By Sorting(A)
n = A.length
let P[1...n]be a new array
for i to n
    P[i] = Rnadom(1,n^3) #此时优先级各不相同的概率是 1-1/n
sort A,using P as sort keys

原址排列给定数组

算法的运行时间是,并且该过程能够产生出一个均匀随机排列

Randomize In Place(A)
n = A.length
for i to n
    Swap A[i] with A[Random(i,n)]

代码实现

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注