Pow(x,n)快速幂：为什么只递归一次，以及负指数的int边界

我最开始的切入点是把七个 3 的连乘拆开而不是直接背“快速幂模板”。这个想法值得保留但有两个地方需要说准拆式不能漏乘数相同的半次幂只求一次才是优化的关键。1. 从3的7次方开始但不要重复求两份力扣 50Pow(x,n)计算实数底数 x 的整数 n 次幂n 的范围包含 int 最小值。题目排除了零底数的非正指数这里不把练习解法扩成处理任意 NaN、无穷大和全部数学定义的库函数。正确的拆法是3^7 3 * (3^3) * (3^3) 3^3 3 * (3^1) * (3^1) 3^1 3 * (3^0) * (3^0) 3^0 1原文曾把中间一步写成3 * [3 * 3^1] * [3 * 3^1]漏掉了每份括号中的一个3^1不是正确等式。这里按上面的拆法修正。令tmp powPositive(x, n / 2)偶数指数返回 tmp*tmp奇数指数再乘 x。表达式有两份 tmp但递归调用只有一次。n递归拿到的 tmp本层返回0不再递归113^0 1113 333^1 3333 2773^3 2727273 2187如果写两次powPositive(x, n/2)再相乘两个相同子问题仍会重新算递归树的规模恢复为线性量级。保存 tmp 是在复用计算结果不只是省一个变量名。2. 原来的手画图哪里需要纠正这张图表达的“只计算一半再复用”是对的。旧版入口还是 int 指数下面的代码会把它改成 long 并先处理负指数。下面原图红字中的“递归函数给你3的6次方”应读成“给你3的3次方”。在 n7 这一层递归只算 7/23平方才成为 3^6最后再乘一个 3。保留原图是为了能回看当时的拆分过程具体指数以本次上面的表格为准不把旧笔误继续当结论。3. 负指数先处理取反之前先扩宽原入口写成n 0 ? 1.0 / pow(x, -n) : pow(x, n)这里的-n仍是 int 运算。最小值 -2147483648 的相反数 2147483648 无法放进 int结果还是原来的负值。Java 语言规范一元负号。不能因此武断地说原程序对最小值必然失败。原辅助函数也接受负数Java 整数除法向零截断递归仍会终止它可能碰巧得到绝对指数的幂。例如 x1 时原代码和修正代码都返回 1。但它破坏了“辅助函数只算非负指数”的清晰约定也让推理依赖一个未解释的溢出行为。更稳妥的组织方式先转 long再取反负指数先把底数换成倒数辅助函数只处理非负次数。class Solution { public double myPow(double x, int n) { long exponent n; if (exponent 0) { x 1.0 / x; exponent -exponent; } return powPositive(x, exponent); } private double powPositive(double x, long n) { if (n 0) return 1.0; double tmp powPositive(x, n / 2); return n % 2 0 ? tmp * tmp : tmp * tmp * x; } }long exponent -n仍然是先在 int 中取反再赋值不能替代这里的“先扩宽再取反”。转换顺序本身就是算法实现的一部分。出口 n0 返回 1也能处理合法的非零底数零指数。n1 没有单独写出口它会递归到 n0然后乘回 x并不会漏算。4. O(log|n|)到底省在哪里每层指数减半只调用一次进行常数次乘法。对非零指数时间和递归栈均为 O(log|n|)n0 为 O(1)。对 int 指数提升后的最大非负次数是 2147483648减半到零只需要几十层不是几十亿层。计算 3^7 时四次调用的指数是 7、3、1、0。相比直接连乘优势在指数很大时更明显。底数接近 1 也不能改用“结果大概不变”跳过计算大次数会积累显著差异。5. 怎么测样例、极值和浮点误差分开处理下面保存为 PowCheck.java与前面的 Solution.java 一起编译。参考结果用 Java Math.pow而不是另写相同的递归公式。浮点数允许舍入误差不能直接比较也不能让 NaN 混过误差判断。public class PowCheck { static int cases; static void check(double x, int n, double relativeTolerance) { double actual new Solution().myPow(x, n); double expected Math.pow(x, n); if (!Double.isFinite(actual) || !Double.isFinite(expected)) { throw new AssertionError(non-finite result); } double tolerance 1e-12 relativeTolerance * Math.abs(expected); if (!(Math.abs(actual - expected) tolerance)) { throw new AssertionError(x x , n n , expected expected , actual actual); } cases; } public static void main(String[] args) { double[] bases {-1.5, -1.0, -0.8, 0.8, 1.0, 1.1, 1.5}; for (double x : bases) for (int n -20; n 20; n) { check(x, n, 1e-10); } for (int n : new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE}) { check(1.0, n, 0.0); check(-1.0, n, 0.0); } check(1.000000001, Integer.MIN_VALUE, 1e-6); check(0.999999999, Integer.MAX_VALUE, 1e-6); check(0.0, 5, 0.0); check(2.0, Integer.MIN_VALUE, 0.0); check(0.44528, 0, 0.0); System.out.println(PASS: cases finite floating-point cases); } }javac Solution.java PowCheck.java java PowCheckJava 17 本次运行结果PASS: 296 finite floating-point cases近 1 底数的极大指数单独使用较宽的相对容差因为倒数及乘法的舍入误差会被放大这只是明确的对照阈值不是证明函数在所有 double 输入上都具有这种误差上界。2 的最小 int 指数在 double 中下溢为零不等于实数数学结果严格为零。本次还运行旧入口来核对最小 int 值的取反现象并用漏掉奇数补乘 x、负指数忘记倒数的错误版本确认测试能拒绝它们。没有声称重提力扣或完成浮点库级验证。这题最有价值的递归视角仍然是原来的相信半次幂的返回值然后补全本层。但把入口范围、取反类型和返回值指数都讲清楚才能让“相信递归”真正落到可验证的程序上。