GESP 八级 · GESP 202603 C++ 八级 第 3 题

下列代码实现了快速幂算法，其时间复杂度为（ ）。

long long fastPow(long long b, long long e, long long mod) {
    long long result = 1;
    while (e > 0) {
        if (e & 1)
            result = result * b % mod;
        b = b * b % mod;
        e >>= 1;
    }
    return result;
}

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

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

【考点】快速幂（指数按位分解）｜对数级循环次数

考纲定位：GESP 八级「算法设计」模块。命题人专门卡住学生——看到 while(e > 0) 就下意识以为复杂度是 O(e)，这其实是「线性模拟」的直觉陷阱。

解题思维：核心观察是 e >>= 1 让指数每轮减半。循环次数 = 二进制位数 = ⌊log₂e⌋+1 = O(log e)。这是「按位分解」通法：把大指数拆成 2 的幂次和，用平方迭代计算，适用于任何需要指数级循环的场景（如矩阵快速幂、递推取模）。

陷阱拆解：

• A 错在哪：用 log b 是偷换概念——b 只在乘法里用，不控制循环次数。
• C 错在哪：mod 只用于取模运算，是常数时间操作。
• D 最阴险：表面看像「循环到 e 为 0」就是 O(e)，但 e 每轮减半，这是典型的「对数级」伪装成线性。
• 如果 e=1024（2¹⁰），循环仅 10 次；e=10¹⁸ 也才～60 次——线性 O(e) 完全不是一个量级。

反命题思维：若把 e >>= 1 改成 e--，瞬间变 O(e)；若改成 e >>= 2 则 O(log e/2) = O(log e)。刷到「循环里变量每次减半/除以常数」的题，先问自己：「真正控制循环次数的是哪个变量？」