《数据与算法课件：18 随机算法》
随机算法是计算机科学中的一种重要策略，它在解决问题时引入了不确定性，使得算法在执行过程中可能会产生不同的结果和效率。这种算法的设计思想简洁，易于实现，尤其在面对复杂问题时，随机方法往往能提供更高效的解决方案。
1. **随机算法的定义**：
随机算法是一种在执行过程中包含随机元素的算法。与确定性算法不同，随机算法在相同的输入下运行可能会产生不同的输出。它们依赖于随机数生成，当面临多个选择时，通常采用随机方式作出决策。虽然结果可能有变异性，但随机算法通常在平均性能上表现优秀。
2. **随机数生成**：
在实际应用中，计算机生成的是伪随机数，而非真正的随机数。线性同余法是最常用的伪随机数生成方法，通过一组数学公式来产生看似随机的序列。随机数的种子用于初始化序列，而为了确保随机性，种子通常选取足够大的值，并且生成器的参数应满足互质条件。
3. **数值随机算法**：
数值随机算法主要用于数值计算领域，如计算圆周率、函数定积分和非线性方程求解。例如，通过向正方形中随机投掷点来估算圆周率，或者在随机点分布中找到满足条件的解来求解非线性方程。这些方法依赖于大量随机点的统计特性，随着样本数量增加，结果的准确性逐渐提高。
4. **舍伍德算法**：
舍伍德算法旨在通过引入随机性改善那些在最坏情况下效率低下的确定性算法。比如，快速排序中通过随机选择划分元素来避免最坏情况的发生，或者在构建二叉搜索树时先随机打乱输入序列，从而避免退化成单枝树。舍伍德算法并不保证避免最坏情况，但它试图减少特定输入导致最坏情况的概率。
5. **拉斯维加斯算法**：
拉斯维加斯算法在求解问题时会做出随机决策，但保证最终得出的解一定是正确的。例如，这类算法可能会反复尝试直到找到正确答案，每次尝试的成功概率逐渐增加。虽然可能会有较高的运行时间，但其不会给出错误答案，因此适用于那些无法有效确定性解决但又需要正确解的问题。
总结来说，随机算法和相关的数值随机算法、舍伍德算法以及拉斯维加斯算法，都是计算机科学中解决复杂问题的重要工具。它们通过引入随机性，平衡了效率与正确性的关系，使得在面对大量数据或复杂计算时，能够提供更加灵活且高效的解决方案。
