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

现在用如下代码来计算 $x^n$（$n$ 个 $x$ 相乘），其时间复杂度为（ ）。

double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}

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

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

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

1. 🎯 考纲定位（考点定位）

GESP 五级《算法设计与分析》递归模块，命题人把"快速幂"与"递归调用次数"混淆，卡住只背结论的考生——熟记 O(log n) 却不会分析实际调用树。