每日科普 · 2026-11-05 周四

考研 408 × 求职面试

知识点 · 算法设计与分析 · 进阶

概率分析与随机化算法的期望复杂度

概率分析是在算法运行前，对输入分布或算法内部随机选择取平均，计算期望运行时间。随机化算法把随机性放进算法本身：即使面对最坏输入，也只对随机选择求期望，因此通常能避免“特定输入导致退化”。
例如随机化快速排序每次随机选主元，任意两个元素被比较的概率为 2/(j-i+1)，总期望比较次数为 O(n log n)。
注意：期望复杂度不是每次运行时间，也不等于最坏复杂度；最坏仍可能 O(n^2)，但发生概率很低。
分析常用指示变量、线性期望和高概率界；Las Vegas 算法保证结果正确、随机运行时间，Monte Carlo 算法允许小概率错误。面试中要区分平均情况、期望和最坏情况。

每日一题 · 算法设计与分析

概率分析与随机化算法的期望复杂度

关于随机化快速排序的期望复杂度，下列说法正确的是：
A. 对任意输入，其期望时间复杂度为 O(n log n)
B. 只有输入随机排列时，期望才是 O(n log n)
C. 其最坏时间复杂度为 O(n log n)
D. 期望复杂度等于每次运行的实际复杂度

解析

选 A。随机化快排的随机性来自主元选择，期望是对算法随机选择取平均，因此对任意输入都成立。任意两元素 x_i、x_j 被比较当且仅当二者中较早被选为主元，概率为 2/(j-i+1)。累加得期望比较次数 O(n log n)。B 混淆了平均情况与随机化；C 最坏仍为 O(n^2)；D 期望不是单次实际运行时间。

面试小贴士 · 算法设计与分析

概率分析与随机化算法的期望复杂度

常问期望与最坏/平均的区别、随机快排为何 O(n log n)、如何给高概率界。答：先说明随机性来源，再取期望，用指示变量给关键概率，最后补充最坏情况和高概率。易错：把期望当最坏、把随机化等同输入随机、忽略随机源独立。

代码实现 · C++

代码示例

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& a, int l, int r) {
    int p = l + rand() % (r - l + 1); // 随机选主元
    swap(a[p], a[l]);
    int pivot = a[l], i = l;
    for (int j = l + 1; j <= r; ++j)
        if (a[j] < pivot) swap(a[++i], a[j]);
    swap(a[l], a[i]);
    return i;
}

void quickSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int m = partition(a, l, r);
    quickSort(a, l, m - 1);
    quickSort(a, m + 1, r);
}

int main() {
    srand(time(0));
    vector<int> a = {5, 3, 8, 1, 9, 2, 7};
    int n = (int)a.size();
    quickSort(a, 0, n - 1);
    for (int x : a) cout << x << " ";
}