算法导论阅读笔记1-5

算法导论

---

5.1 随机算法和概率算法

The hiring problem

假如我要雇佣一个助手，我让中介每天给我介绍一个，如果比前一天推荐的好，就雇佣他，每天都要给中介一笔费用。

我的解决思路

所有的排序方法共有$n!$种，分别计算雇佣到最好的助手所用次数为1-n的概率 $X_1$ 、$X_2$……$X_n$，然后计算数学期望E。
雇佣助手的价格为$c_h$，每日中介费为$c_i$,假设推荐了n个助手，雇佣了m次，则价钱为$O(nc_i+mc_h)$
将期望带入m，带入可以算出期望的钱数。

Probabilistic analysis

在前文中用于分析时间复杂度(averge-case runing time)
现在用于分析cost
要求了解输入序列的分布，如果不能了解，就不能用该法分析

Randomized algorithms

基于Probabilistic analysis的算法
首先对题目设定进行轻微的修改，中介先给一个名单，我随机进行选择，我选择的顺序与花费挂钩，所以对于选择的顺序我应该谨慎。
概念：
randomized：不仅仅取决于输入的值还取决于输入的顺序（random-numbergenerator）
RANDOM(a,b)：返回[a,b]中的一个数，每个数返回的概率是$1/(b-a+1)$
pected running time:分析随机算法的时间
average-case runing time:非随机算法

5.2 Indicator random variables

$$I[A] = \begin{cases} 1, & \text{if A happen,} \\ 0, & \text{if A not happen,} \end{cases}$$
如果时间A发生了，值为1，否则为0
$$E[I[A]]=Pr[A\ occurs]*1+Pr[A\ not\ occurs]*0$$
I[A]期望的计算，Pr表示概率
设事件第n天雇不雇佣为$X_n$,则有$X_n=I[H]=9 \begin{cases} 1, & \text{if H happen} \\ 0, & \text{if H not happen} \end{cases}$
$$E[X_I]=1/i$$
对每天进行求和：$\sum_{i=0}^n E[X_n] =ln\ n+O(1)$(P1153A.7有介绍)

5.3 生成随机数列

假设有一个数组$a[4]=\{1,2,3,4\}$
通过过$RANDOM(1,n^3)$生成新的数列:$b[4]=\{36,10,55,66\}$
通过该序列对a进行排序
例:找到b中的最小元素b[2],把a中最小元素放在a[2]。
该算法的实现

用rand生成随机数列
以此为key使用归并排序对a进行排序

---

11.16更新

proof

证明在生成随机数列中既数列升序排序的概率。
用到的公式
其实就是证明在第一个元素最小发生时，第二个元素第二小发生，在此基础上第三个元素第三小......以此类推
分别设这些事件为$E_1,E_2......E_N$,求这些事件的交集发生的概率。
带入公式里面，易得$P(E_1)=1/n，P(E_2)=1/(n-1)$，其他也很容易得到啦，结果就是1/n!。
用高中的排列组合更快得出答案。
然后再推广到生成随机数列中置换数列的情况，结果是一样的。
K-permutation为什么是n!/(n-k)!还真不知道，有空再去看Appendix C的其他部分......

5.4深入使用