算法基础-随机过程
未婚夫问题
假如现在有n个求婚者，被分别标记为1，2，3…N，她们将按顺序被你面试，你每次都必须选择接受或不接受，一旦你接受了其中一个，那么就无法面试后面的人。因此你必须在无法面试后面的人的情况下选出当下最优者。
由于无法预知这些求婚者的平均情况，所以我们必须先面试前k个人，从第k+1个人开始，一旦发现更优者就立即选择她。
关键变量
这个问题中有三个主要的关键变量
最优点x
顾名思义，最优点就是最佳求婚者出现的位置，我们的最终目标是找到最优点，如果不能，那就尽可能让找到最优点的概率最大
停止点k
在停止点 k 之前的所有求婚者都将被拒绝，而她们之间的最优者将被作为面试之后的求婚者的标准，如果发现比她们之间的最优者更优的人，就立即接受她
次优点λ
在最优点 x 之前的最佳求婚者出现的位置就是次优点。我们希望次优点 λ 出现在停止点 k 之前，而最优点 x 出现在 k 之后
概率模型
当最优点 x 出现在停止点 k 之前时，计算没有意义，因为最优点已经被排除了
当最优点 x 出现在停止点 k 之后时，总共有(n-k)个情况，由于 μ 出现的位置是随机的，总共有 n 个位置，所以所有情况发生的概率都是 1/n
只有次优点 λ 出现在前 k 个位置时，我们才能准确地找到最优点 x ，而次优点出现在前k个位置的概率为 k/(x-1)
因此我们可以计算出找到最佳求婚者的概率
我们可以使用定积分得到P的上下界
这两个定积分非常简单，因此这里直接给出结果
如果希望P尽可能大，则需要P的下界尽可能大，于是我们对k求导并令导数为0
解方程，得
显然当k=n/e时，P取到最大值36.8%
因此对于任意的n，只需要将前 36.8% 的数据作为参考，就能以最大概率在之后选出最优解
随机排列
如果想要验证上面的问题，就需要用到随机排列的数组。
均匀随机排列
均匀随机排列是指产生1~n的每一种排列的概率完全相同，即产生某一种排列的概率为全排列的倒数
给定序列[1,2,3, … ,n]，通过将这些数字随机地变换以使数组随机化，从而达到均匀随机排列。优先级数组就是一种得到均匀随机排列得方法
优先级数组
对数组A，给定另一个数组P，在P中随机地生成一个大范围整数，并根据P[i]的大小来调整A[i]的位置。例如A=[1,2,3,4,5]，而P=[13,62,6,19,52]，那么调整后的序列就是[2,5,4,1,3]
但是这种方法有一个缺陷，即必须确保数组P的每一项都唯一，幸运的是，你只需要扩大随机数范围就可以尽可能保证不出现重复
该方法代码较为简单，故不做演示
设 Ei 表示第 i 个元素被分配到第 i 个位置，则每个元素都被分配到自己对应的位置的概率为
显然当 i = 1 时，E1为1/n，因为总共有n个元素。当 i ≥ 2 时，
所以，在前 i-1 个元素的位置都已经确定的情况下，P(Ei)=1/(n-i+1)，于是我们得到
所以，使用优先级数组方法获得等同排列的概率恰好为全排列的倒数
实际上，对于数组A的任意一个随机排列S，只需要修改一下E的定义，我们都可以使用上述方法证明出 A[i] 恰好被分配到 S 数组中的指定位置 j 的概率为 1/n!