GESP 八级 · GESP 202503 C++ 八级 第 10 题

2025 是个神奇的数字，因为它是由两个数 20 和 25 拼接而成，而且 $2025 = (20 + 25)^2$。小杨决定写个程序找找小于 $N$ 的正整数中共有多少这样神奇的数字。该函数的时间复杂度为（ ）。

#include <string>
int count_miracle(int N) {
    int cnt = 0;
    for (int n = 1; n * n < N; n++) {
        int n2 = n * n;
        std::string s = std::to_string(n2);
        for (int i = 1; i < s.length(); i++)
            if (s[i] != '0') {
                std::string s1 = s.substr(0, i);
                std::string sr = s.substr(i);
                int n1 = std::stoi(s1);
                int nr = std::stoi(sr);
                if (__________) // 在此处填入选项
                    cnt++;
            }
    }
    return cnt;
}

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

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

【考点】时间复杂度分析｜字符串操作复杂度｜循环嵌套

🎯 考纲定位 GESP 八级 算法复杂度与字符串处理。命题人卡住的是考生对「to_string 和 stoi 非 O(1)」的忽视——以为字符串拼接是常数时间，实则与位数成线性关系。

🧠 解题思维 外层循环 n 从 1 到 ≈√N，共 Θ(√N) 次；每次 to_string(n²) 生成 ≈2log₁₀n 字符，耗时 O(log N)；内层 substr 与 stoi 各需扫描整个子串，单次 O(log N)，内循环本身 Θ(log N) 次，故内层整体 O((log N)²)；总复杂度 Θ(√N(log N)²)。

🪤 陷阱拆解 选项 B 仅考虑外层循环，误把 to_string 当作 O(1)；选项 C 漏掉内层循环的字符串操作成本；选项 A 更是把 N 直接代入，完全误解循环边界。最阴险的是 substr 和 stoi 的线性扫描——若只记结论不拆解内层循环，必选错。

🔄 反命题思维 若把 N 换成 N²，外层循环变成 Θ(N)，总复杂度将升至 O(N(log N)²)。刷到此类题先问：to_string 和 stoi 耗时与什么相关？答案永远是「与位数即 log 值相关」。