CSP-S 2020 第一轮 第27题：若输入的 d[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]$ 都为同一个数，此程序平均的时间复杂度是( )。

选项

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

答案

D

题解

第⑥题选 D．\(O(n^2)\)。

设所有元素都等于 \(v\)。每次调用 find 时：

• 第 9～10 行随机选择并交换元素，但所有元素相等，数组没有变化。
• 第 13 行的 d[a] < d[L] 恒为假，a 保持为 L+1。
• 第 15 行的 d[b] >= d[L] 恒为真，b 不断左移，直到与 a 相等。因此，一次长度为 \(m\) 的区间处理需要 \(O(m)\) 时间。
• 第 19 行的条件也为假，所以 a-L 始终为 \(1\)。

于是，当 \(k>1\) 时，第 24 行实际执行的是：

``cpp return find(L + 1, R, k - 1); ``

也就是说，每次花线性时间，却只排除一个元素。当 \(k=n\) 时，总耗时为：

\[ n+(n-1)+\cdots+1=\Theta(n^2). \]

随机选取基准元素不能改善这个过程，因此平均时间复杂度仍选 \(O(n^2)\)。

严格来说，耗时还与 \(k\) 有关，为 \(\Theta(nk)\)：例如 \(k=1\) 时是 \(\Theta(n)\)。本题按允许 \(k\) 随 \(n\) 增长的整体复杂度作答。