GESP 八级 · GESP 202406 C++ 八级 第 14 题

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

int gcd(int m, int n) {
    if (m == 0)
        return n;
    return gcd(n % m, m);
}

辗转相除法求最大公约数：gcd(a,b) = gcd(b, a%b)，当b=0时返回a。时间复杂度O(log min(a,b))。

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

【考点】递归｜欧几里得算法｜算法复杂度

1. 🎯 考纲定位

GESP 八级算法模块，考查递归实现与欧几里得算法的时间复杂度分析。命题人卡住的是很多考生"背复杂度模板却不理解推导过程"的弱点——看到递归就默认 O(n)，看到求值就默认 O(n!)，完全没考虑递归深度和每次调用的代价。