CSP-S 2024 第一轮 第18题：假设数组c长度无限制，该程序所实现的算法的时间复杂度是0(b)的。（）

题目

#include <iostream>
using namespace std;

const int N = 1000;
int c[N];

int logic(int x, int y) {
    return (x & y) ^ ((x ^ y) | (~x & y));
}

void generate(int a, int b, int *c) {
    for (int i = 0; i < b; i++)
        c[i] = logic(a, i) % (b + 1);
}

void recursion(int depth, int *arr, int size) {
    if (depth <= 0 || size <= 1) return;
    int pivot = arr[0];
    int i = 0, j = size - 1;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
    recursion(depth - 1, arr, j + 1);
    recursion(depth - 1, arr + i, size - i);
}

int main() {
    int a, b, d;
    cin >> a >> b >> d;
    generate(a, b, c);
    recursion(d, c, b);
    for (int i = 0; i < b; ++i) cout << c[i] << " ";
    cout << endl;
}

假设数组 $c$ 长度无限制，该程序所实现的算法的时间复杂度是 $O(b)$ 的。（  ）

选项

• T. 正确
• F. 错误

答案

F

题解

选 F（错误）。递归部分最坏会达到 \(O(b^2)\)。

先看各部分：

• generate 循环 \(b\) 次，每次都是常数次位运算，时间为 \(O(b)\)。
• 最后的输出循环也是 \(O(b)\)。
• recursion 是一个限制递归深度的快速排序过程，复杂度取决于划分情况和输入的 \(d\)。

可以构造一个最坏情况：令 \(a=0,\ d\ge b\)。

此时： \[ \operatorname{logic}(0,i) =0\oplus(i\mid i)=i, \] 所以生成的数组为 \[ c=[0,1,2,\ldots,b-1]. \]

每次递归都选第一个元素作为 pivot。由于数组已经升序，pivot 总是当前最小值：

• j 要从末尾一路向前扫描，本次花费与当前数组长度成正比；
• 划分后，一个子数组为空，另一个长度只减少 \(1\)。

因此，总时间为 \[ \Theta(b)+\Theta(b-1)+\cdots+\Theta(2) =\Theta(b^2). \]

注意：如果 \(d\) 是固定常数，时间确实是 \(O(b)\)；但这里 \(d\) 是输入，不能当作固定常数，所以题目判断为错误。