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

下面程序的时间复杂度为（ ）。

long long power_mod(long long a, long long n, long long mod) {
    if (n == 0)
        return 1;
    a = a % mod;
    if (n == 1)
        return a;
    long long pw = power_mod(a, n / 2, mod);
    long long pw2 = pw * pw % mod;
    if (n % 2 == 0)
        return pw2;
    return pw2 * a % mod;
}

这题考快速幂的时间复杂度。核心不是看代码行数，而是看递归里 n 怎么变：每次 n 减半，递归树深度就是 log₂n，每层只做常数次乘法，所以总复杂度是 O(log n)。

最容易掉进 D 选项的坑，以为每次乘法要 O(a) 时间，把 a 当成复杂度因子。其实 a 只是输入值，C++ 里 long long 乘法是常数时间，跟 n 无关。还有人会被函数名里的 n 误导选 A，把 n 当成循环次数，但 n 是指数不是迭代变量。边界条件 n==0 和 n==1 只是常数时间分支，不影响阶。

【考点】快速幂算法｜递归复杂度分析｜对数时间复杂度

1. 考纲定位

GESP 八级算法模块明确要求掌握快速幂、二分思想。命题人把这道题放在这里，就是要卡住那些只会看代码行数、不会分析递归深度的考生——C 和 D 都含 log n，但很多人分不清「递归层数」和「每次迭代代价」的区别。