@chawuciren
2018-11-16T14:17:12.000000Z
字数 1357
阅读 1023
算法导论
假如我要雇佣一个助手,我让中介每天给我介绍一个,如果比前一天推荐的好,就雇佣他,每天都要给中介一笔费用。
所有的排序方法共有种,分别计算雇佣到最好的助手所用次数为1-n的概率 、……,然后计算数学期望E。
雇佣助手的价格为,每日中介费为,假设推荐了n个助手,雇佣了m次,则价钱为
将期望带入m,带入可以算出期望的钱数。
在前文中用于分析时间复杂度(averge-case runing time)
现在用于分析cost
要求了解输入序列的分布,如果不能了解,就不能用该法分析
基于Probabilistic analysis的算法
首先对题目设定进行轻微的修改,中介先给一个名单,我随机进行选择,我选择的顺序与花费挂钩,所以对于选择的顺序我应该谨慎。
概念:
randomized:不仅仅取决于输入的值还取决于输入的顺序(random-numbergenerator)
RANDOM(a,b):返回[a,b]中的一个数,每个数返回的概率是
pected running time:分析随机算法的时间
average-case runing time:非随机算法
假设有一个数组
通过过生成新的数列:
通过该序列对a进行排序
例:找到b中的最小元素b[2],把a中最小元素放在a[2]。
该算法的实现
用rand生成随机数列
以此为key使用归并排序对a进行排序
11.16更新
证明在生成随机数列中既数列升序排序的概率。
用到的公式
其实就是证明在第一个元素最小发生时,第二个元素第二小发生,在此基础上第三个元素第三小......以此类推
分别设这些事件为,求这些事件的交集发生的概率。
带入公式里面,易得,其他也很容易得到啦,结果就是1/n!。
用高中的排列组合更快得出答案。
然后再推广到生成随机数列中置换数列的情况,结果是一样的。
K-permutation为什么是n!/(n-k)!还真不知道,有空再去看Appendix C的其他部分......