Lesson13：随机算法

确定性算法是指在给定相同输入的情况下，算法总是产生相同的结果。

随机算法是指在给定相同输入的情况下，算法可能产生不同的结果。

对于一些复杂的计算问题，确定性算法可能需要耗费大量的时间和资源，而随机算法可以在合理的时间内提供一个近似解。例如，蒙特卡罗方法在计算高维积分时表现出色。

在某些情况下，输入数据可能具有不确定性或噪声，随机算法可以更好地处理这些不确定性。例如，随机森林算法在处理有噪声的数据时表现良好。

有些问题的确定性算法设计非常复杂，而随机算法可以提供一种更为简单和直接的解决方案。例如，拉斯维加斯算法在找到正确解之前会不断尝试，设计相对简单。

在分布式计算环境中，随机算法可以有效地分配任务，减少通信开销，提高计算效率。例如，哈希算法在分布式系统中的负载均衡中起到了重要作用。

随机算法分为以下两种

• 拉斯维加斯算法(Las Vegas Algorithm): 这种算法在每次运行时都会使用随机性，但它保证最终会找到一个正确的解。也就是说，拉斯维加斯算法的输出总是正确的，但运行时间可能会有所不同。一个典型的例子是快速排序算法的随机化版本，它通过随机选择枢轴来提高平均性能。 (randomized algorithms that are always correct, and run efficiently in expectation)

• 蒙特卡罗算法(Monte Carlo Algorithm): 这种算法在每次运行时都会使用随机性，但它不一定能找到一个正确的解。也就是说，蒙特卡罗算法的输出可能不正确，但运行时间通常是固定的。一个典型的例子是蒙特卡罗方法在计算高维积分时表现出色。(efficient randomized algorithms that only need to yield the correct answer with high probability)

雇佣问题

意思就是有雇佣人和面试人两个费用，然后在面试完顺序中的任一人后需要立刻决定雇佣不雇佣。

简单的思路就是看第k人是不是比前k-1人都优秀，是就雇佣，否则不雇佣。

最坏情况必然是从最劣到最优顺序排布，这样我们全部都要雇佣。

平均情况(就是随机进来的)的雇佣复杂度是\(O(C_hlog_2N+NC_i)\)

\(C_h\)是雇佣花费，\(C_i\)是面试花费，\(N\)是面试人数。

为了避免出现最坏情况，我们可以采用随机算法，即随机打乱顺序，使用随机取值来实现。

对于在线算法，我们需要设定一个k的所谓什么"练手"值，在此之前的都是一定不雇佣的，在此后只要比k中最优秀的还优秀就仅雇佣之。

这个算法问题重重，首先非常可能出现没办法拿下最优秀的人的情况，其次，k设定为多少比较好呢？

我了个概率论领域大神啊。

那么证明了下面那个不等式之后我们就可以计算得到\(k\)的值了，计算出来是\(\frac{N}{e}\)。

快排(quicksort)

快排的最坏情况就是每次取到的都是最小/大值，这样就退化为了每次处理上一次问题规模-1的问题，复杂度就变成了\(O(N^2)\)。

利用随机算法改善："好不好"的base点，如果base点(比如)左侧分治出来的序列不大于\(\frac{n}{4}\)，那么认为不好，赶紧选一个新的。

如果这样的情景，那么\(P[found\ a\ valid\ base\ point] = \frac{1}{2}\)。