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

假设输入参数 $m$ 和 $n$ 满足 $m \leq n$，则下面程序的最差情况的时间复杂度为（ ）。

int gcd(int m, int n) {
    while (m > 0) {
        int t = m;
        m = n % m;
        n = t;
    }
    return n;
}

这题考辗转相除法的复杂度，拿到题先别急着套公式，盯着循环里 m 和 n 的变化看——每次 m 变成 n%m，余数一定比除数小，所以除数至少减半，循环次数就是 log n 级别。

最容易错在以为每次循环 m 只减 1，从而选 O(n)；或者把取模运算当成 O(m) 的代价，凑出 O(n×m)；还有人分不清 m 和 n 的角色，把复杂度写成 O(m×log n)。其实取模是常数时间，关键是看除数 n 在每一步是不是真的在快速缩小。

考点定位

欧几里得算法（辗转相除法）的迭代实现，核心是理解循环次数与输入规模的关系。

算法主线与逐行推演

程序从 while (m > 0) 开始，每次循环做三件事： 1. t = m 保存当前除数； 2. m = n % m 用余数替换除数； 3. n = t 把原来的除数变成新的被除数。

这就是经典的 gcd(n, m) = gcd(m, n % m) 的迭代版。循环终止条件是 m == 0，此时返回的 n 就是最大公约数。

关键观察：除数至少减半

最“阴险”的地方在于：很多人只看 m = n % m，觉得余数可能很小，但忽略了 n 在下一步会接过 m 的位置，成为新的除数。因此，真正决定循环次数的，是新的除数（即上一轮的 m）是否足够小。

数论里有个经典结论：欧几里得算法中，每一步的除数至少是上一步除数的一半。直观理解：

• 若 n % m == 0，则 m 整除 n，循环结束；
• 若 n % m != 0，则 n % m < m，且由于 n % m 是 n 减去若干个 m 得到的，剩下的余数不可能超过 m/2（否则还能再减一次 m）。因此新的除数 m 至少变为原来的一半。

这意味着，无论输入多大，除数每两步至少减半，循环次数上界就是 log₂ n。

复杂度推导

• 每次循环里只做一次取模和两次赋值，都是常数时间操作，记为 O(1)。
• 循环次数为 O(log n)。
• 总时间复杂度 = O(log n) × O(1) = O(log n)。

所以正确答案是 A。

命题人视角与陷阱拆解

命题人这次挖坑很典型：

• 选项 B O(n) 是误以为每次循环 m 只减 1，忽略了余数会迅速变小；
• 选项 C O(n×m) 是把循环次数 O(n) 与每次运算成本 O(m) 强行相乘，却忘了取模是常数时间；
• 选项 D O(m×log n) 混淆了 m 和 n 的角色，且 log n 已经是循环次数，再乘 m 就多余了。

最阴险的细节是“最差情况”。很多人以为当 m≈n 时循环次数最多，其实欧几里得算法最坏输入是斐波那契数相邻项，但即便如此，循环次数依然是 O(log n)。题目强调“最差情况”只是为了考察你是否理解算法的本质，而不是让你死记硬背某个特例。

考频与趋势

从真实题库数据看，最大公约数与最小公倍数是高频考点：共考过 32 题，覆盖 7 个考试级别，2025 年单年就有 13 题，2024 年 7 题，2023 年 2 题。复杂度分析单独考了 39 题，且几乎全在 CSP 入门级（38 题），说明这类“读程序 + 分析复杂度”的题目在入门级非常常见。

综合来看，欧几里得算法及其复杂度分析属于“算法基础”模块的必考内容，命题人反复在不同年份、不同级别重复考查，意在确保考生掌握最基础的循环复杂度分析方法。

预测

基于上述考频分布（复杂度分析 39 题，其中入门级 38 题）和近年趋势（2025 年单年 13 题，2024 年 7 题），可以合理预测：未来几年（尤其是 CSP 入门级、GESP 八级这类基础算法题）仍会高频出现“读程序 + 分析时间复杂度”的题目，且大概率继续围绕欧几里得算法、二分查找、冒泡/选择排序等经典算法的循环次数展开。命题人可能会在题目细节上做微调，比如给出更复杂的嵌套循环或递归结构，但核心考点——“看除数是否至少减半”或“看循环变量是否至少减 1”——不会变。

因此，备考时应重点练习：识别循环中变量的变化规律，判断是 O(log n)、O(n) 还是 O(n²)，并警惕把常数时间操作误判为 O(m) 或 O(n) 的陷阱。