GESP 五级 · GESP 202409 C++ 五级 第 7 题

下面函数可以将 $n$ 的所有质因数找出来，其时间复杂度是（ ）。

#include <iostream>
#include <vector>

vector<int> get_prime_factors(int n) {
    vector<int> factors;

    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }

    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }

    if (n > 2) {
        factors.push_back(n);
    }

    return factors;
}

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

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

【考点】质因数分解｜循环复杂度分析｜数论界限

1. 🎯 考纲定位 GESP 五级对应 C++ 数论与算法模块，本题正是"算法复杂度分析"模块的压轴题。命题人卡住绝大多数考生的弱点——分不清"循环上限"与"循环次数"的区别，盲目套用 O(n) 或 O(n log n) 公式，导致选项 B、D 成为高频陷阱。

2. 🧠 解题思维 看到题先定位循环结构：外层 for 循环上限是 i*i <= n，即 i 最大到 √n，故外层迭代次数为 √n/2 = O(√n)；内层 while 循环每次 n 至少除以 i（i≥3），总次数为 log₃n = O(log n)。最外层处理因子 2 的 while 循环迭代 log₂n = O(log n)，最后 if 语句仅执行一次。整体复杂度为 O(√n log n)，选项 C 正确。

3. 🪤 陷阱拆解 选项 A O(n²) 源于误以为外层循环上限是 n 而非 √n；选项 B O(n log n) 是普通分解算法（如试除法到 n）的复杂度，命题人利用学生忽略"i*i <= n"的优化；选项 D O(n) 则假设每次 while 只执行一次，忽略了内层循环的 log n 因子。题目最阴险的细节在于 while 循环内 n 的更新：n /= i 后 n 显著减小，但 i 本身可能大于 2，导致总次数为 log n 而非 log₂n，若不理解这一点，极易选错。

4. 🔄 反命题思维 若将条件改为"分解所有因子（含重复）"或"处理负数"，外层循环上限不变，但内层 while 可能多执行，复杂度变为 O(√n log n + 额外项)。刷到类似题时，先问自己"命题人想考我什么"——是循环上限、循环次数，还是最后剩余的大质数？本题核心在于识别 √n 与 log n 的乘积结构。