CSP-S 2020 第一轮 第24题：当输入的 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 获取对应的分数】

选项

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

答案

A

题解

严格按这份代码分析，第③题的选项有问题：不能用“递归约 \(\log n\) 层，每层交换一次”来选 C。

关键在于：初始数组递增，不代表递归处理的数组仍然递增。 第 10 行会打乱顺序，而且程序没有把枢轴交换到最终位置。

例如输入数组为 \(1,2,\ldots,15\)，取 \(k=1\)。如果连续选到枢轴 \(11、8、5\)，就会出现：

可见，每层的交换次数会随着末尾积累的小元素增加，并非始终是常数。

进一步分析，取 \(k=1\) 时，在区间仍足够长的阶段，每次向左递归通常都会多积累一个这样的元素；随机选择枢轴又会产生约 \(\log n\) 层递归。因此，平均交换次数的紧确量级实际上为 \[ \Theta\bigl((\log n)^2\bigr), \] 而选项没有列出这个量级。

所以：

• 若要求准确的复杂度量级：没有合适选项。
• 若必须从给出的 \(O\) 上界中选最小的有效上界：选 B，\(O(n)\)。
• 选 C 的“每层只交换常数次”解释，忽略了递归时数组顺序已经改变，不能成立。