本文目录导读：
- 随机化快速排序（Randomized Quicksort）
- 蒙特卡洛算法：估计 π 的值
- 拉斯维加斯算法：随机化的字符串匹配（Rabin-Karp 变种）
- 随机化算法在“大厂面试”中的经典案例：蓄水池抽样（Reservoir Sampling）
- 随机算法在“AI/机器学习”中的体现：随机梯度下降（SGD）
- 总结：如何区分两类随机算法？
随机算法是计算机科学中非常重要的一类算法，核心在于利用随机性来简化问题或解决问题，下面我从几个典型类别出发，各举一个经典案例,并附上简化的代码逻辑和思路分析。
随机化快速排序（Randomized Quicksort）
背景：普通快速排序在数组已经有序的情况下，时间复杂度会退化为 O(n²)。
思路：为了避免最坏情况，随机选取一个元素作为基准（pivot），而不是固定选第一个或最后一个，这样，期望时间复杂度始终是 O(n log n),且不需要依赖输入数据的分布。
代码逻辑（伪代码）：
import random
def randomized_partition(arr, low, high):
# 随机选一个索引作为pivot，并交换到末尾
rand_pivot = random.randint(low, high)
arr[rand_pivot], arr[high] = arr[high], arr[rand_pivot]
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
def randomized_quicksort(arr, low, high):
if low < high:
pi = randomized_partition(arr, low, high)
randomized_quicksort(arr, low, pi - 1)
randomized_quicksort(arr, pi + 1, high)
核心价值：用随机化打破了输入数据对算法性能的“恶意”影响。
蒙特卡洛算法：估计 π 的值
背景：这是最经典的蒙特卡洛模拟（Monte Carlo Simulation），蒙特卡洛算法用大量随机采样来逼近精确解,适用于难以用解析方法求解的问题。
思路：在一个正方形内随机撒点，计算落在其内切圆内的点数比例，这个比例趋近于 π / 4（正方形面积比）。
代码逻辑（Python）：
import random
def estimate_pi(num_points=1000000):
inside_circle = 0
for _ in range(num_points):
x = random.uniform(-1, 1)
y = random.uniform(-1, 1)
if x*x + y*y <= 1:
inside_circle += 1
return (inside_circle / num_points) * 4
# 结果接近 3.14159...
print(estimate_pi())
特点：结果不保证100%精确，但采样点越多，结果越接近真实值（误差随样本量增加而减小）。
拉斯维加斯算法：随机化的字符串匹配（Rabin-Karp 变种）
背景：拉斯维加斯算法的特点是结果一定正确，但运行时间可能随机（通常用随机数来加速平均情况）。
思路：在字符串匹配时，我们计算子串的哈希值，为了防止哈希冲突导致错误判断，我们随机选取一个大的模数（如随机素数），或者用多重哈希，由于用随机模数，不同字符串哈希冲突的概率极低，可以近似认为不冲突，从而保证结果正确，但大幅提升平均速度。
（更极端的案例是“随机化中点分割”，这里以简单的“随机素数哈希”为例）
伪代码思想：
import random
def randomized_rabin_karp(text, pattern):
# 随机选择一个大素数作为模数，降低冲突概率
prime = random.choice([1000000007, 1000000009, 1000000021])
n, m = len(text), len(pattern)
# 计算pattern的哈希值（略）
# 滑动窗口比较哈希值，如果哈希相等，再逐步确认字符（确保正确性）
# ...
核心价值：用“随机化”来降低最坏情况的概率，同时通过二次验证保证结果绝对正确。
随机化算法在“大厂面试”中的经典案例：蓄水池抽样（Reservoir Sampling）
问题：不知道数据流的总长度，需要等概率地从中随机抽取 K 个样本，该问题在大数据处理场景很常见。
算法思路：
- 对于前 K 个元素，直接全部放入“蓄水池”。
- 对于第 t 个元素（t > K），我们随机生成一个 1 到 t 之间的随机数 d。
- d <= K，则用该元素替换蓄水池中的第 d 个元素；否则跳过。
结果：经过所有数据后，蓄水池中每个元素被选中的概率都是 K / N（N为总长度），且不需要知道N是多少。
代码逻辑：
import random
def reservoir_sampling(stream, k):
reservoir = []
for i, item in enumerate(stream):
if i < k:
reservoir.append(item)
else:
# 以 k/i 的概率决定是否替换
j = random.randint(0, i)
if j < k:
reservoir[j] = item
return reservoir
应用场景：搜索引擎的抽样日志、大文件随机抽行。
随机算法在“AI/机器学习”中的体现：随机梯度下降（SGD）
SGD 属于优化算法，但它的“随机”特性非常核心。
思路：普通梯度下降（GD）每次要遍历全部数据才能算一次梯度，太慢，SGD 每次随机选一个样本（或一小批 batch） 计算梯度并更新参数，虽然更新路径有噪声（抖动），但在大规模数据下，收敛速度极快,且能跳出局部最优。
如何区分两类随机算法？
| 算法类型 | 代表案例 | 特点 | 结果是否一定正确 |
|---|---|---|---|
| 蒙特卡洛 | 计算 π | 随机采样求近似解 | 不一定正确（有误差） |
| 拉斯维加斯 | 快速排序、字符串匹配 | 随机过程可能不同，但结果必对 | 一定正确（除非运气极差） |
如果你对某一种的数学原理（比如证明期望复杂度）或者代码实现细节特别感兴趣，可以告诉我,我再深入解释具体步骤。
