算法导论第 5 章：概率分析与随机算法

主要内容

由于概率算法在实际中用得不多，我先战略性地快速过完本章。分析一个随机算法的运行时间时，输入值由随机数生成器产生，运行时间称为期望运行时间。指示器随机变量为概率和期望之间的转换提供了一个便利的方法，用于很多随机算法的分析中。

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

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

习题解答

练习题

5.1-2 解答：将\(b-a\)次rand函数的结果累加再加上\(a\)即可。

5.2-1 解答：正好雇用一次，说明应聘者正好是反序出现；正好雇用\(n\)次，说明应聘者正好是正序出现。它们的概率都是\(1/n!\)。

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