GESP 八级 · GESP 202506 C++ 八级 第 9 题

下面的 sum_digit 函数试图求出从 $1$ 到 $n$（包含 $1$ 和 $n$）的数中，包含数字 $d$ 的个数。该函数的时间复杂度为（ ）。

#include <string>
int count_digit(int n, char d) {
    int cnt = 0;
    std::string s = std::to_string(n);
    for (int i = 0; i < s.length(); i++)
        if (s[i] == d)
            cnt++;
    return cnt;
}
int sum_digit(int n, char d) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += count_digit(i, d);
    return sum;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】时间复杂度分析｜字符串转换｜对数复杂度｜循环嵌套

1. 考纲定位

• 本题考查 GESP 八级"算法基础"模块中的时间复杂度分析
• 命题人专门用这道题卡住绝大多数考生的"复杂度直觉"——看到循环就默认 O(n)，却忽略了内层函数本身还依赖 n 的位数（log n）
• 字符串转换和逐位计数是基础语法，但对数阶复杂度才是本题真正的考核点

2. 解题思维

• 先解 count_digit：std::to_string(n) 生成字符串长度是 log₁₀ n，遍历一次也是 log₁₀ n，故该函数复杂度为 O(log n)
• 再看 sum_digit：外层循环执行 n 次，内层每次 O(log n)，总复杂度 = n × O(log n) = O(n log n)
• 通法：遇到"循环调用函数"类题，先拆解内层函数的输入规模（位数/长度），再乘以外层循环次数，切勿直接套用 O(n) 或 O(1) 的直觉

3. 陷阱拆解

• 选项 B (O(n))：误以为 count_digit 是 O(1)，忽略了字符串转换和遍历的开销
• 选项 C (O(log n))：混淆了单次数学运算的复杂度，误以为总复杂度只取决于数字位数
• 选项 D (O(n²))：把位数想成 n 本身，误以为字符串长度是 n，忽略了数字位数是 log n
• 这些陷阱利用了考生对"数字"与"位数"的概念不清，以及对字符串操作的直觉偏差

4. 反命题思维

• 命题人若把 count_digit 改成直接计算数字每一位（不用字符串），复杂度仍是 O(log n)，但可能误导考生选 O(n)
• 或者把循环改成只处理 n 的每一位，会变成 O(log n)
• 刷到类似题，先问自己"命题人想考我什么"——这里就是考你识别对数阶和循环嵌套的乘积关系