0%

算法导论第 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 解答:待完成

思考题

待完成。