第48章 概率与随机化算法：当确定性失效时

说实话，我刚开始学数据结构时，对随机化算法是有点不屑的。总觉得算法就该是确定性的——输入一样，输出就该一样。直到我在一个推荐系统项目里，面对海量数据，传统排序和哈希方案跑得比蜗牛还慢……嗯，从那以后，我对随机化算法彻底改观了。

这一章，我们来聊聊概率与随机化算法。说白了，就是用一点点「运气」换效率。你可能会问：算法还能靠运气？别急，看完你就明白了。

48.1 概率基础：随机化的数学根基

随机化算法不是瞎蒙。它背后有严格的概率论支撑。我个人习惯把概率基础分成三块：

  • 期望与方差：衡量随机变量的平均表现和波动范围
  • 大数定律：实验次数越多，平均值越接近真实值
  • 切比雪夫不等式：给出偏离期望的概率上界

举个例子。你抛一枚均匀硬币，正面概率0.5。抛10次，可能正面7次。但抛10000次，正面比例一定接近0.5。这就是大数定律在起作用。

核心思想：随机化算法利用概率论保证「大概率正确」或「期望高效」。不是100%确定，但99.999%够用了。

48.2 蒙特卡洛方法：用随机模拟求解

蒙特卡洛方法，名字听着高大上，其实原理很简单——用随机采样来近似计算。

我在项目中遇到过一个问题：计算一个复杂形状的面积。传统方法要积分，公式推导半天。用蒙特卡洛方法呢？往形状里随机撒点，统计落在内部的点比例，乘以总面积，完事。

// 用蒙特卡洛方法估算圆周率π
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

double monte_carlo_pi(int iterations) {
    int inside = 0;
    srand(time(NULL));
    
    for (int i = 0; i < iterations; i++) {
        double x = (double)rand() / RAND_MAX;  // [0,1)
        double y = (double)rand() / RAND_MAX;
        if (x*x + y*y <= 1.0) {
            inside++;
        }
    }
    // 圆面积/正方形面积 = π/4
    return 4.0 * inside / iterations;
}

int main() {
    int n = 1000000;
    double pi = monte_carlo_pi(n);
    printf("估算π值: %f (误差: %f)\n", pi, pi - M_PI);
    return 0;
}

你想想看，这个算法每次运行结果都不一样。但迭代次数越多，结果越稳定。这就是蒙特卡洛的特点：以概率收敛。

我的经验：蒙特卡洛方法适合那些「精确解太难求，近似解够用」的场景。比如金融风险建模、物理模拟、图形学中的全局光照。

48.3 拉斯维加斯方法：永远正确，但时间随机

拉斯维加斯方法和蒙特卡洛正好相反。它保证结果绝对正确，但运行时间不确定。说白了，就是「要么给你正确答案，要么一直算下去」。

经典例子：随机化快速排序中的随机选取pivot。你选得好，O(n log n)；选得差，O(n²)。但通过随机化，我们避免了最坏情况，期望时间就是O(n log n)。

注意：拉斯维加斯方法可能永远不终止吗？理论上可能，但概率为0。实际中，我们通常设置一个最大迭代次数，超时就重新开始。

48.4 随机化快速排序：让最坏情况消失

传统快速排序最怕什么？有序数组。每次选第一个元素做pivot，直接退化成O(n²)。我在早期写排序算法时就踩过这个坑——线上数据恰好是递增的，排序慢到报警。

解决方案？随机选pivot。代码改动极小，效果天差地别。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int* a, int* b) {
    int t = *a; *a = *b; *b = t;
}

// 随机选取pivot，并放到最左边
int random_partition(int arr[], int low, int high) {
    int random_index = low + rand() % (high - low + 1);
    swap(&arr[low], &arr[random_index]);
    
    int pivot = arr[low];
    int i = low;
    
    for (int j = low + 1; j <= high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[low], &arr[i]);
    return i;
}

void randomized_quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = random_partition(arr, low, high);
        randomized_quick_sort(arr, low, pi - 1);
        randomized_quick_sort(arr, pi + 1, high);
    }
}

int main() {
    srand(time(NULL));
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    randomized_quick_sort(arr, 0, n-1);
    
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

为什么随机化有效？因为最坏情况输入的概率被均匀分散了。你想想看，攻击者想构造一个让快速排序变慢的输入，但pivot是随机选的，他根本不知道你会选哪个。这就是随机化的威力。

48.5 随机化哈希：让冲突更均匀

哈希表最头疼的问题是什么？哈希冲突。传统哈希函数是固定的，攻击者可以构造大量冲突key，把哈希表退化成链表。

随机化哈希的思路：哈希函数本身带随机性。每次运行程序，哈希函数都不一样。这样攻击者无法提前知道哈希行为。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 随机化哈希表（简化版）
#define TABLE_SIZE 100

typedef struct {
    int key;
    int value;
} Entry;

typedef struct {
    Entry* table[TABLE_SIZE];
    int a, b;  // 随机参数
    int prime; // 大素数
} RandomHashTable;

// 初始化随机哈希参数
void init_hash_table(RandomHashTable* ht) {
    ht->prime = 1000003;  // 一个大素数
    ht->a = rand() % (ht->prime - 1) + 1;
    ht->b = rand() % ht->prime;
    
    for (int i = 0; i < TABLE_SIZE; i++)
        ht->table[i] = NULL;
}

// 通用哈希函数: h(k) = ((a*k + b) % prime) % TABLE_SIZE
int hash(RandomHashTable* ht, int key) {
    return ((ht->a * key + ht->b) % ht->prime) % TABLE_SIZE;
}

void insert(RandomHashTable* ht, int key, int value) {
    int index = hash(ht, key);
    // 这里简化处理，实际需要处理冲突
    Entry* e = (Entry*)malloc(sizeof(Entry));
    e->key = key;
    e->value = value;
    ht->table[index] = e;
}

int main() {
    srand(time(NULL));
    RandomHashTable ht;
    init_hash_table(&ht);
    
    printf("随机参数: a=%d, b=%d\n", ht.a, ht.b);
    printf("key=42 的哈希值: %d\n", hash(&ht, 42));
    printf("key=100 的哈希值: %d\n", hash(&ht, 100));
    
    return 0;
}

关键点：随机化哈希的「随机」体现在哈希函数参数上，而不是哈希表本身。每次程序启动，参数不同，但运行过程中参数不变。这样既保证了随机性，又保证了确定性（同一个key在同一运行中哈希值相同）。

48.6 知识体系总览

下面这张图，是我梳理的本章知识结构。你可以把它当作一张地图，随时回来查阅。

概率与随机化算法知识体系 随机化算法 概率基础 蒙特卡洛方法 • 期望与方差 • 大数定律 • 切比雪夫不等式 • 随机采样近似计算 • 以概率收敛 • 结果有误差，但可控 拉斯维加斯方法 （结果正确，时间随机） 随机化快速排序 & 随机化哈希 （避免最坏情况，均匀分布）

48.7 避坑指南与实用建议

讲到这里，我想分享几个实际开发中的教训：

  • 随机数种子要设好：我曾经在服务器上忘了srand(time(NULL))，结果每次重启程序随机数都一样，调试了半天才发现。建议用更高质量的随机数源，比如/dev/urandom。
  • 蒙特卡洛的精度：误差和迭代次数的平方根成反比。想提高10倍精度，需要100倍采样。别盲目增加迭代次数，要考虑性价比。
  • 随机化不是万能药：它解决的是「最坏情况」问题，不是「平均情况」问题。如果你的数据本身已经随机，随机化带来的收益有限。
  • 可复现性：调试随机化算法时，固定随机种子。等调试完再放开。不然每次运行结果不同，bug都复现不了。

一句话总结：蒙特卡洛用随机换精度（结果可能错），拉斯维加斯用随机换时间（结果一定对）。两者都是「用可控的不确定性，换取性能的大幅提升」。

好了，这一章的内容就到这里。随机化算法是个很实用的工具，尤其当你面对大规模数据或恶意输入时。下次写排序或哈希，不妨试试随机化版本——你会发现，世界变得美好了许多。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →