CSP-S 2020 第一轮 第26题：若输入的 d[i] 为 i，此程序①平均的时间复杂度和②最坏情况下的时

题目

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假设输入的 $n,k$ 和 $d[i]$ 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：

（2.5 分）若输入的 $d[i]$ 为 $i$，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。

选项

• A. $O(n), O(n^2)$
• B. $O(n),O(n \log n)$
• C. $O(n \log n),O(n^2)$
• D. $O(n \log n),O(n \log n)$

答案

A

题解

第⑤题选 A：平均时间复杂度为 \(O(n)\)，最坏时间复杂度为 \(O(n^2)\)。

这段程序使用的是随机快速选择，作用是寻找数组中第 \(k\) 小的数。

每次调用 find 时：

1. 随机选取一个数作为基准，交换到 d[L]。
2. 用双指针扫描，把小于基准的数放到左侧，其余数放到右侧。这一步对长度为 \(m\) 的区间需要 \(O(m)\) 时间。
3. 判断第 \(k\) 小的数在哪里：若恰好是基准就返回，否则只递归处理其中一侧。

平均情况：\(O(n)\)

虽然输入 d[i] = i 是递增序列，但基准是随机选的，并不总是最小值或最大值。

随机基准有约一半的概率落在按大小排序后的中间一半位置，此时接下来处理的区间最多剩下原来的 \(\frac34\)。因此，每缩小一个固定比例，平均只需常数次划分，总工作量可以用几何级数估计：

\[ O(n)+O\left(\frac34n\right)+O\left(\left(\frac34\right)^2n\right)+\cdots =O(n). \]

最坏情况：\(O(n^2)\)

例如寻找最小值，即 \(k=1\)，却每次都随机选中当前区间的最大值。这样每次只排除一个数，处理的区间长度依次为：

\[ n,\ n-1,\ n-2,\ \ldots,\ 1. \]

总耗时为：

\[ O\bigl(n+(n-1)+\cdots+1\bigr)=O(n^2). \]

注意：第⑤题问的是总运行时间，双指针扫描的耗时也要计算，不能只统计第17行的交换次数。