本文主要是介绍概率分析和随机算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、随机分析
考虑一个雇佣问题，面试n个人，在面试的过程中，只要更为优秀的人出现，就雇佣更为优秀的人，但是更换人选需要花费一笔费用c，现在估算这笔费用。
这个问题相当于维护一个当前的“获胜者”。
最坏的情形当然是替换n次，那么费用就会是cn.
随机的情况：
第i个人比前i-1个人更为优秀的概率为1/i，那么期望E[X] = 1/1 +1/2 +1/3 + …… = ln n + O(1)，也就是说，随机情况下，平均起来大概雇佣了lnn个人，费用为clnn。
二、随机算法
如何产生一个随机排列的数组？只需证明或等等同排列的概率为1/n!。
方案一：给原数组中的每个成员赋一个代表优先级值，这个值随机产生，然后按照优先级排序
PERMUTE-BY-SORTING(A)
n = A.length
let P[1..n] be a new array
for i =1 to nP[i] = RANDOM(1,n^3) # 1~n^3是为了让P中所有优先级尽可能唯一
sort A, using P as sor keys #花费代价可为Θ（nlgn）这篇关于概率分析和随机算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
