CSP-S 2022 第一轮 第26题：若val[i]的最大值为100，k取（）时算法运算次数最少。

题目

1  #include <iostream>
2
3  using namespace std;
4
5  const int MAXN = 105;
6
7  int n, m, k, val[MAXN];
8  int temp[MAXN], cnt[MAXN];
9
10 void init()
11 {
12     cin >> n >> k;
13     for (int i = 0; i < n; i++) cin >> val[i];
14     int maximum = val[0];
15     for (int i = 1; i < n; i++)
16         if (val[i] > maximum) maximum = val[i];
17     m = 1;
18     while (maximum >= k) {
19         maximum /= k;
20         m++;
21     }
22 }
23
24 void solve()
25 {
26     int base = 1;
27     for (int i = 0; i < m; i++) {
28         for (int j = 0; j < k; j++) cnt[j] = 0;
29         for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
30         for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
31         for (int j = n - 1; j >= 0; j--) {
32             temp[cnt[val[j] / base % k] - 1] = val[j];
33             cnt[val[j] / base % k]--;
34         }
35         for (int j = 0; j < n; j++) val[j] = temp[j];
36         base *= k;
37     }
38 }
39
40 int main()
41 {
42     init();
43     solve();
44     for (int i = 0; i < n; i++) cout << val[i] << ;
45     cout << endl;
46     return 0;
47 }

假设输入的 n 为不大于 100 的正整数，k 为不小于 2 且不大于 100 的正整数，val[i]在 int 表示范围内，完成下面的判断题和单选题：

若 val[i]的最大值为 100，k 取（ ）时算法运算次数最少。

选项

• A. 2
• B. 3
• C. 10
• D. 不确定

答案

D

题解

选 D. 不确定，因为运算次数不仅取决于 \(k\)，还取决于没有给定具体值的 \(n\)。

这段程序实现的是 \(k\) 进制的基数排序：每一轮按照某一位排序，共进行 \(m\) 轮。init() 算出的 \(m\)，就是最大值的 \(k\) 进制位数。

当最大值为 100 时：

但轮数少，不代表总运算次数一定少。 每轮中：

• 第 28、30 行遍历计数数组，运算量与 \(k\) 有关；
• 第 29、31、35 行遍历数据，运算量与 \(n\) 有关。

所以总时间复杂度为： \[ O\bigl(m(n+k)\bigr) \]

当 \(n\) 很小时，清空、累加计数数组的开销很显著，较小的 \(k\) 更有利；当 \(n\) 较大时，反复遍历数据的开销更显著，减少排序轮数更有利。

例如，用 \(m(n+k)\) 粗略估算：

可见，最优选择会随 \(n\) 改变。题目只给出 \(n\le100\)，因此应选 D。