chap5 概率分析和随机算法

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

内容

一些定义

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

雇佣问题

1. 只要遇见更好的应聘者，就立即雇佣并解雇当前工作人员，直到n个候选人都应聘完
2. 当应聘者以随机次序出现，则总的雇佣费用的平均值为$O(c\lg n)$,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

原址排列给定数组

算法的运行时间是$O(n)$，并且该过程能够产生出一个均匀随机排列

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

代码实现