『算法导论』第 5 章

主要内容

本章介绍概率分析随机算法。由于概率算法在实际中用得不多,我先战略性地快速过完本章。

分析一个随机算法的运行时间时,输入值由随机数生成器产生,运行时间称为期望运行时间。指示器随机变量为概率和期望之间的转换提供了一个便利的方法,用于很多随机算法的分析中。

利用指示器随机变量分析雇用问题,雇用一个新的办公助理的期望次数为$\ln n + O(1)$,即,面试了$n$个人,平均起来,实际上大约只雇用其中的$\ln n$个人。

随机排列数组有两种算法。第一种算法的思想是,为数组的每个元素赋一个随机的优先级,然后根据优先级对数组中的元素进行排序,运行时间为$\Theta(n \lg n)$;第二种算法的思想是,每一次迭代,将数组的元素与它后面的随机位置的元素交换,运行时间为$\Theta(n)$。

习题解答

练习题

5.1-1 解答:待完成

5.1-2 解答:将$b-a$次rand函数的结果累加再加上$a$即可。

5.1-3 解答:待完成

5.2-1 解答:正好雇用一次,说明应聘者正好是反序出现;正好雇用$n$次,说明应聘者正好是正序出现。它们的概率都是$1/n!$。

5.2-2 解答:正好雇用两次,说明有一个逆序对。可以看成将排序好的序列选出两个元素交换位置,所以概率为:$C_n^2/n!$。

5.2-3 解答:待完成

5.2-4 解答:待完成

5.2-5 解答:待完成

5.3-1 解答:待完成

5.3-2 解答:待完成

5.3-3 解答:待完成

5.3-4 解答:待完成

5.3-5 解答:待完成

5.3-6 解答:待完成

5.3-7 解答:待完成

思考题

待完成。