1.核心思想与动机

为什么需要随机？

• 简单性：随机算法通常比对应的确定性算法更简单、易于实现。
• 速度：通常更快，尤其是在平均情况下。
• 避免最坏情况：确定性算法的性能可能被精心设计的输入（最坏情况输入）拖垮，随机性使得算法对所有输入都表现良好（以高概率）。
• 解决确定性算法难以解决的问题：有些问题（如素数判定）在很长一段时间内没有高效确定性算法，但随机算法可以高效解决。

两类主要的随机算法

根据对“正确性”的要求，随机算法主要分为两类：

A. 拉斯维加斯算法

• 定义：结果永远正确，但运行时间是随机的。
• 口号：“要么给我正确答案，要么不告诉我答案，但我绝不撒谎。”
• 核心：通过随机性来巧妙、高效地组织结构或选择路径，但最终会验证结果的正确性。
• 经典例子：
  • 随机快速排序：随机选择一个主元，算法永远会正确排序数组，但运行时间依赖于主元的选择质量，随机化使得期望运行时间为 O(n log n)，并且对任意输入都能达到这个期望，避免了最坏情况 O(n²)。
  • 随机化选择算法：在未排序数组中找第k小的元素。

B. 蒙特卡洛算法

• 定义：运行时间通常是固定的（或有限制的），但结果有一定的概率是错误的。
• 口号：“我总是很快给出一个答案，但这个答案可能不对。”
• 核心：利用随机性进行抽样或近似估算，用速度换取绝对的确定性。
• 进一步分类：
  1. 偏真算法：如果答案是“是”，它一定说“是”；如果答案是“否”，它可能误判为“是”（单侧错误），常用于判定问题。
     • 例子：素数判定的米勒-拉宾算法，如果算法输出“合数”，则数字一定是合数；如果输出“可能是素数”，则有极小概率是错的（实际应用中可以做到概率极低，如小于 2^(-100)）。
  2. 偏假算法：与偏真相反。
  3. 无偏算法：无论答案是“是”还是“否”，都有出错概率。
     • 例子：用随机采样估算圆周率π，或用重复抽样来降低误差（如通过多次运行偏真算法来降低整体错误率）。

关键概念与分析工具

A. 期望运行时间

• 这是分析拉斯维加斯算法的主要工具,计算算法在所有可能的随机选择上的运行时间的加权平均。
• 随机快速排序的期望比较次数为 ~2n ln n。

B. 误差概率

• 这是分析蒙特卡洛算法的核心,算法输出错误答案的概率是多少？
• 这个概率是相对于算法的随机选择而言的，而不是针对输入，也就是说，对于同一个固定输入，算法每次运行时使用的随机数不同，可能导致不同的结果。

C. 放大成功率

• 对于一个误差概率为 p < 1/2 的蒙特卡洛算法，如何降低误差？
• 基本技巧：重复运行，独立运行算法 k 次，然后采取多数决（对于无偏算法）或只要出现一次特定结果就判定（对于偏真/偏假算法）。
• 概率放大：经过 k 次独立运行，错误概率可以从 p 指数级下降到 p^k 或利用切尔诺夫界等工具证明其下降到 e^{-c k} 级别。

D. 随机源与伪随机数

• 理论分析中,我们假设算法可以访问“完美的”随机比特。
• 实践中,使用伪随机数生成器，对于大多数应用，高质量的PRNG足以保证算法有效。

经典案例分析

• 随机最小割：在一个无向图中找到全局最小割，确定性算法复杂。Karger 算法通过随机收缩边，以不小于 2/(n(n-1)) 的概率找到最小割，通过重复运行 O(n² log n) 次，可以以任意高的概率找到最小割，这是一个非常巧妙、简单且不直观的蒙特卡洛算法。
• 素数判定：米勒-拉宾算法是典型的偏真蒙特卡洛算法，在实践中完全取代了确定性算法（直到后来出现确定性的AKS算法，但速度慢得多）。
• 哈希：许多哈希表的实现（如链地址法）依赖于哈希函数将键均匀地映射到槽中，一个随机或强伪随机的哈希函数对于避免最坏情况至关重要。
• 随机游走与采样：谷歌的PageRank、蒙特卡洛积分法。

概率分析与“平均情况分析”的区别

这是初学者容易混淆的概念：

• 平均情况分析：假设输入服从某种特定的概率分布（如所有排列等概率），分析确定性算法的平均性能。
• 随机算法的概率分析：输入是任意固定的（可以是充满恶意的），算法的性能是针对算法的随机选择取平均或高概率保证。

随机算法的优势在于,对于任意一个固定的坏输入，其糟糕的表现只会以很小的概率发生。

随机算法的应用领域

• 算法设计：排序、选择、搜索、图算法。
• 数值计算：蒙特卡洛积分、模拟。
• 机器学习与优化：随机梯度下降、模拟退火、遗传算法。
• 密码学：密钥生成、协议设计（零知识证明）。
• 负载均衡：将任务随机分配给服务器。
• 避免冲突：以太网中的退避算法。

随机算法打破了传统确定性算法的思维定式,通过巧妙的“抛硬币”决策，以简单的逻辑、高效的性能和鲁棒的抗最坏情况能力，解决了大量实际问题，理解其核心——拉斯维加斯算法（时间随机，结果正确） 与蒙特卡洛算法（时间固定，结果可能错误）——以及如何用期望时间和误差概率来分析它们，是掌握这一领域的基础。

标签： 用户导向 价值实现