CSP-S 2020 第一轮 第25题：当输入的 d[i] 是严格单调递减序列时，第 17 行的 swap 平

题目

#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]$ 是严格单调递减序列时，第 17 行的 swap 平均执行次数是( )。

选项

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

答案

B

题解

第④题选 B：\(O(n)\)。

这题统计的是第 17 行 swap 的总执行次数，要把各次递归都算进去。

程序每次随机选一个基准值 d[L]，然后把小于它的数放到左边，大于或等于它的数放到右边，最后只在包含第 \(k\) 小元素的一侧继续递归。

对于严格递减序列，第一次划分平均就需要 \(O(n)\) 次交换。 因为较大的数集中在左边，较小的数集中在右边，与划分要求相反。例如：

``text 原序列：8 7 6 5 4 3 2 1 选 5 为基准，第 10 行交换后： 5 7 6 8 4 3 2 1 ``

划分时，需要交换 7 和 1、6 和 2、8 和 3。一般而言，基准值落在大小排名的中间一半的概率约为 \(1/2\)，此时需要交换的元素对数与 \(n\) 成正比。因此，平均交换次数至少是线性量级。

另一方面，每次处理长度为 \(m\) 的区间，交换次数至多为 \(O(m)\)；随机选择基准值，使后续递归区间的规模平均按常数比例缩小，所以全部递归的平均工作量为：

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

因此，第 17 行 swap 的平均总执行次数是 \(O(n)\)。