CSP-J 2022 第一轮 第 25 题：程序（二）：g(n,m)的时间复杂度

题目

1  #include <algorithm>
2  #include <iostream>
3  #include <limits>
4
5  using namespace std;
6
7  const int MAXN = 105;
8  const int MAXK = 105;
9
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14     if (m == 1) return n;
15     if (n == 0) return 0;
16
17     int ret = numeric_limits<int>::max();
18     for (int i = 1; i <= n; i++)
19         ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);
20     return ret;
21 }
22
23 int g(int n, int m)
24 {
25     for (int i = 1;i <= n; i++)
26         h[i][1]= i;
27     for (int j = 1;j<= m; j++)
28         h[0][j]= 0;
29
30     for (int i= 1; i <= n; i++){
31         for (int j= 2; j <= m; j++){
32             h[i][j] = numeric_limits<int>::max();
33             for (int k = 1;k <= i;k++)
34             h[i][j]= min(
35                 h[i][j],
36                 max(h[i - k][j],h[k - 1][j - 1]) +1);
37         }
38     }
39
40     return h[n][m];
41 }
42
43 int main()
44 {
45     int n,m;
46     cin >> n>> m;
47     cout << f(n, m) << endl << g(n, m)<< endl;
48     return 0;
49 }

假设输入的n、m均是不超过100 的正整数，完成下面的判断题和单选题：

算法 $g(n,m)$ 最为准确的时间复杂度分析结果为（ ）。

选项

• A. $O(n^{3/2}m)$
• B. $O(nm)$
• C. $O(n^{2}m)$
• D. $O(nm^{2})$

答案

C

题解

选 C. \(O(n^2m)\)。

重点看 g(n,m) 第 30～38 行的三层循环：

• i 从 \(1\) 到 \(n\)；
• 对每个 i，j 循环 \(m-1\) 次；
• 对每组 i,j，k 从 \(1\) 到 \(i\)，循环 \(i\) 次。

最内层只有数组访问、比较、赋值，单次耗时为 \(O(1)\)，所以总执行次数为 \[ \sum_{i=1}^{n}(m-1)i =(m-1)\frac{n(n+1)}2. \]

前面的初始化耗时 \(O(n+m)\)，因此通常按 \(m\ge2\) 分析，总时间复杂度为 \(O(n^2m)\)。

注意：虽然 g 和 f 计算的结果相同，但 g 直接查表，没有调用 f，不需要计入递归的耗时。