CSP-S 2023 第一轮 第15题：现在用如下代码来计算x"，其时间复杂度为（）

题目

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

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);
}

选项

• A. $O(n)$
• B. $O(1)$
• C. $O(log n)$
• D. $O(n \log n)$

答案

A

题解

选 A. \(O(n)\)。

关键在于：代码把 quick_power(x, n / 2) 调用了两次，每次都会重新计算，所以时间复杂度的递推式为： \[ T(n)=2T(\lfloor n/2\rfloor)+O(1). \]

从递归树来看：

• 第 0 层有 1 次调用；
• 第 1 层有 2 次调用；
• 第 2 层有 4 次调用；
• ……
• 递归深度约为 \(\log_2 n\)，最后一层约有 \(n\) 次调用。

总调用次数约为： \[ 1+2+4+\cdots+n=2n-1, \] 因此时间复杂度为 \(O(n)\)。注意：递归深度是 \(O(\log n)\)，不代表总运行时间也是 \(O(\log n)\)。

如果把重复计算的结果保存下来： ``cpp double half = quick_power(x, n / 2); return half * half * ((n & 1) ? x : 1); `` 每层就只递归一次，此时时间复杂度才是 \(O(\log n)\)。