第99课 - 随机化算法

学习目标

通过本课的学习，你将能够：

理解随机化算法在算法竞赛中的优势和应用场景
掌握洗牌算法（Fisher-Yates）和哈希随机化的实现技巧
学会分析随机化算法的期望时间复杂度
应用随机化算法解决实际问题，避免最坏情况

核心概念

什么是随机化算法？

随机化算法是指在算法执行过程中引入随机性，使算法的运行时间或输出结果具有随机性的算法。在竞赛中，随机化算法主要有两个优势：

避免最坏情况：例如在快速排序中，随机选择基准元素可以避免已排序数组导致的O(n²)复杂度
简化问题求解：某些问题使用确定性算法很难解决，但使用随机化算法可以高效解决

洗牌算法（Fisher-Yates）

洗牌算法用于将数组随机打乱，确保每个排列出现的概率相等。核心思想是：从后往前遍历数组，将当前位置与之前随机位置交换。

哈希随机化

在字符串哈希中，随机选择哈希参数可以避免特定构造的数据导致哈希冲突，提高算法的鲁棒性。

代码示例

1. Fisher-Yates 洗牌算法

import random

def fisher_yates_shuffle(arr):
    """
    Fisher-Yates 洗牌算法
    时间复杂度: O(n)
    空间复杂度: O(1)
    """
    n = len(arr)
    # 从最后一个元素开始向前遍历
    for i in range(n-1, 0, -1):
        # 生成一个 [0, i] 之间的随机索引
        j = random.randint(0, i)
        # 交换 arr[i] 和 arr[j]
        arr[i], arr[j] = arr[j], arr[i]
    return arr

# 测试洗牌算法
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print("原始数组:", arr)
print("洗牌后:", fisher_yates_shuffle(arr.copy()))

2. 随机化快速排序

import random

def randomized_quicksort(arr):
    """
    随机化快速排序
    通过随机选择 pivot 避免最坏情况
    期望时间复杂度: O(n log n)
    """
    if len(arr) <= 1:
        return arr
    
    # 随机选择 pivot
    pivot_idx = random.randint(0, len(arr)-1)
    pivot = arr[pivot_idx]
    
    # 分割数组
    left = [x for i, x in enumerate(arr) if i != pivot_idx and x <= pivot]
    right = [x for i, x in enumerate(arr) if i != pivot_idx and x > pivot]
    
    # 递归排序并合并
    return randomized_quicksort(left) + [pivot] + randomized_quicksort(right)

# 测试随机化快速排序
arr = [3, 6, 8, 10, 1, 2, 1]
print("原始数组:", arr)
print("排序后:", randomized_quicksort(arr))

3. 字符串哈希随机化

import random

class RandomizedHash:
    """
    随机化字符串哈希
    通过随机选择哈希参数减少冲突概率
    """
    def __init__(self, max_len=100000):
        # 随机选择基数和模数
        self.base = random.randint(256, 10000)
        self.mod = random.randint(10**9, 2*10**9)
        # 预处理 base 的幂次
        self.pow = [1] * (max_len + 1)
        for i in range(1, max_len + 1):
            self.pow[i] = (self.pow[i-1] * self.base) % self.mod
    
    def hash_string(self, s):
        """计算字符串的哈希值"""
        hash_val = 0
        for i, char in enumerate(s):
            hash_val = (hash_val * self.base + ord(char)) % self.mod
        return hash_val
    
    def hash_substring(self, s, l, r):
        """计算子串 s[l..r] 的哈希值（0-indexed）"""
        hash_val = 0
        for i in range(l, r+1):
            hash_val = (hash_val * self.base + ord(s[i])) % self.mod
        return hash_val

# 测试随机化哈希
rh = RandomizedHash()
test_str = "hello world"
print(f"字符串 '{test_str}' 的哈希值: {rh.hash_string(test_str)}")
print(f"子串 'llo' 的哈希值: {rh.hash_substring(test_str, 2, 4)}")

实践练习

练习 1：实现随机化选择算法

题目描述：实现一个随机化选择算法，能在期望 O(n) 时间内找到数组中第 k 小的元素。

要求：

使用随机化避免最坏情况
不修改原数组
返回第 k 小的元素（k 从 1 开始计数）

输入：arr = [3, 2, 1, 5, 6, 4], k = 2 预期输出：2

def randomized_select(arr, k):
    # 在此实现你的代码
    pass

# 测试
arr = [3, 2, 1, 5, 6, 4]
print(f"第 {2} 小的元素是: {randomized_select(arr, 2)}")

练习 2：生日悖论验证

题目描述：模拟生日悖论问题。假设有 n 个人，他们的生日均匀分布在 365 天。随机生成 n 个生日，计算至少两个人生日相同的概率。

要求：

实现模拟函数，重复实验 10000 次
计算概率并与理论值对比
当 n=23 时，概率应约为 50%

输入：n = 23 预期输出：模拟概率: 0.50xx

import random

def birthday_paradox_simulation(n, trials=10000):
    # 在此实现你的代码
    pass

# 测试
prob = birthday_paradox_simulation(23)
print(f"23人中至少有两人生日相同的概率: {prob:.4f}")

练习 3：随机化处理字符串哈希冲突

题目描述：给定一个字符串数组，找出所有重复的字符串。使用随机化哈希减少误判。

要求：

使用随机化哈希进行初步筛选
对哈希冲突的字符串进行精确比较
返回所有重复字符串的索引对

输入：["apple", "banana", "apple", "orange", "banana"] 预期输出：[(0, 2), (1, 4)]

def find_duplicate_strings(strs):
    # 在此实现你的代码
    pass

# 测试
strs = ["apple", "banana", "apple", "orange", "banana"]
print(f"重复字符串索引: {find_duplicate_strings(strs)}")

常见错误

伪随机数种子问题：忘记设置随机种子会导致结果不可重现，在调试时设置固定种子
```
random.seed(123)  # 设置固定种子便于调试
```

洗牌算法实现错误：错误实现导致某些排列概率不相等

# 错误示例：与随机位置交换（不是 Fisher-Yates）
def wrong_shuffle(arr):
    for i in range(len(arr)):
        j = random.randint(0, len(arr)-1)  # 错误：应该选 [0, i]
        arr[i], arr[j] = arr[j], arr[i]

哈希参数选择不当：在字符串哈希中使用固定基数和模数容易被针对性数据攻击
期望复杂度误解：期望 O(n) 不代表每次都是 O(n)，可能存在偶尔的最坏情况

小结

随机化算法的优势：
- 避免确定性算法的最坏情况
- 简化某些问题的求解
- 提高算法的鲁棒性
关键技巧：
- Fisher-Yates 洗牌：确保等概率随机排列
- 随机化快速排序：随机选择 pivot 避免最坏情况
- 哈希随机化：随机选择哈希参数减少冲突
复杂度分析：
- 随机化算法的复杂度通常是期望值而非最坏情况
- 要会分析期望时间复杂度和成功概率
应用场景：
- 排序算法优化（快排、选择）
- 哈希表冲突处理
- 随机抽样和概率算法
- 竞赛中处理特殊构造数据

随机化算法是算法竞赛中的重要技巧，合理使用可以大幅提升算法的性能和鲁棒性。在实际应用中，需要权衡随机性带来的好处和可能增加的不确定性。

练习编辑器

rust