CSP-J 2024 第一轮 第 29 题：程序（三）：b越大运行时间是否越长

题目

#include <iostream>
#include <cmath>
using namespace std;

int customFunction(int a, int b) {
    if (b == 0) {
        return a;
    }
    return a + customFunction(a, b-1);
}

int main() {
    int x, y;
    cin >> x >> y;
    int result = customFunction(x, y);
    cout << pow(result, 2) << endl;
    return 0;
}

（本题选“正确”或“错误”均给分）当 $b$ 的值越大，程序的运行时间越长。（  ）

选项

• √. 正确
• ×. 错误

答案

√ 或 ×（均给分）

题解

按通常的算法分析，假设 \(b\ge 0\)，可以选“√ 正确”。 题目已注明两种答案均给分。

关键看递归语句： ``cpp return a + customFunction(a, b-1); `` 每调用一次，\(b\) 减少 \(1\)，直到 \(b=0\) 才停止。例如：

• \(b=2\)：调用过程为 \(2\to1\to0\)，共调用 3 次。
• \(b=4\)：调用过程为 \(4\to3\to2\to1\to0\)，共调用 5 次。

所以，初始 \(b\) 为非负整数时，总共调用 \(b+1\) 次，并进行 \(b\) 次加法。\(b\) 越大，需要执行的操作越多，时间复杂度为 \(O(b)\)。

这里说的“运行时间越长”是指理论上的运算量增加，并不保证实际测量的耗时每次都严格增加。