AlgoNote 题解精讲：0050. Pow(x, n) —— 用「分治 + 快速幂」把指数计算从 O(n) 优化到 O(log n)

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是《算法通关手册》AlgoNote题解目录 中第 0050 题的深度精讲。围绕 Pow(x, n) 题解 展开讲解如何利用「分治算法」将朴素的 $n$ 次累乘优化为 $O(\log n)$ 的快速幂计算并给出完整的可运行代码、逐行解析与边界分析。读完本文你将掌握快速幂的奇偶分解原理、负数指数的处理方法以及递归思路与位运算迭代实现之间的转换技巧。1. 题目速览项目内容题号0050. Pow(x, n)标签递归、数学难度中等要求计算 $x$ 的 $n$ 次方即 $x^n$题目描述给定浮点数 $x$ 和整数 $n$计算 $x$ 的 $n$ 次方。数据范围与说明$-100.0 x 100.0$。$-2^{31} \le n \le 2^{31} - 1$。$n$ 是一个整数。$-10^4 \le x^n \le 10^4$。示例示例 1输入x 2.00000, n 10 输出1024.00000示例 2输入x 2.00000, n -2 输出0.25000 解释2-2 1/22 1/4 0.252. 题意拆解幂运算的本质幂运算 $x^n$ 的数学定义是「$n$ 个 $x$ 相乘」即 $x^n \underbrace{x \times x \times \cdots \times x}_{n \text{ 个}}$。但当 $n$ 的取值高达 $2^{31} - 1$ 时逐个累乘显然是低效的当 $n$ 为正且很大时$O(n)$ 次乘法无法接受当 $n$ 为负时还需处理倒数转换即 $x^{-n} \dfrac{1}{x^n}$当 $n 0$ 时任何非零数的 $0$ 次方为 $1$$x 0, n 0$ 属于题意之外的边界常规实现下返回 $1$ 即可但本题直接按 $0^n$ 语义处理。因此本题的核心不是「会不会算幂」而是如何用更少的时间算幂。这正是分治算法的用武之地。3. 朴素思路连续乘法时间复杂度 O(n)最直观的做法是把 $x$ 累乘 $n$ 次class Solution: def myPow(self, x: float, n: int) - float: res 1 for _ in range(abs(n)): res * x return res if n 0 else 1 / res这种方法虽然正确但存在两个明显问题时间复杂度为 $O(n)$当 $n 2^{31} - 1$ 时需要执行约 21 亿次乘法无法通过评测没有利用幂运算的数学性质$x^n$ 具有天然的「可分解」结构完全可以利用分治思想将规模减半。4. 核心思路分治算法与快速幂4.1 分治思想的奇偶分解在《算法通关手册》的 分治算法章节 中给出定义分治算法Divide and Conquer即「分而治之」把一个复杂问题拆分成多个相同或相似的子问题递归分解直到子问题足够简单可以直接解决最后将子问题的解合并得到原问题的解。针对幂运算根据 $n$ 的奇偶性可以得到两个关键结论如果 $n$ 为偶数$x^n x^{n / 2} \times x^{n / 2}$如果 $n$ 为奇数$x^n x \times x^{(n - 1) / 2} \times x^{(n - 1) / 2}$。其中 $x^{n / 2}$ 或 $x^{(n - 1) / 2}$ 又可以继续向下递归划分。这样用低维度的幂计算结果就能推导出高维度的幂计算结果——每递归一次指数规模减半因此时间复杂度降为 $O(\log n)$。以 $x 2, n 10$ 为例分解过程为$$ 2^{10} 2^5 \times 2^5,\quad 2^5 2 \times 2^2 \times 2^2,\quad 2^2 2 \times 2 $$只需 4 次乘法即可得到 $1024$而朴素累乘需要 10 次。当 $n$ 越大时这一优势越明显。4.2 负数指数的处理原文档明确指出如果 $n$ 为负数可以转换为 $\dfrac{1}{x}^{(-n)}$即先对底数取倒数、再把指数取绝对值从而把问题规约到「正指数」这一标准形态$$ x^{-n} \frac{1}{x^n} \left(\frac{1}{x}\right)^{n} $$注意当 $n -2^{31}$ 时若使用 32 位有符号整数$-n$ 会发生溢出Python 的整数是任意精度的不存在此问题。若移植到 C/Java 等语言需要把中间指数变量提升为 64 位长整型long。4.3 从分治递归到二进制迭代快速幂分治思路天然对应递归实现但递归的每一层都伴随函数调用开销与栈空间消耗。观察分解过程可以发现一个规律递归每次将指数除以 $2$向下取整奇数时额外乘上一个 $x$。如果把指数 $n$ 写成二进制形式例如 $n 10_{(10)} 1010_{(2)}$那么$$ x^{10} x^{2^1 2^3} x^{2^1} \times x^{2^3} $$也就是说$x$ 的 $n$ 次方等于「$n$ 的二进制表示中所有为 1 的位」所对应的 $x^{2^i}$ 的乘积。原文档也指出「递归也可以转为递推来做」。在迭代中我们只需要用右移逐位扫描 $n$ 的二进制用「按位与」n 1判断当前最低位是否为 $1$每次循环把 $x$ 自乘为 $x^2, x^4, x^8 \cdots$对应二进制位的权重翻倍。这正是位运算在 位运算章节 中介绍的基础操作按位与、右移与分治思想结合的经典案例。5. 代码实现与逐行解析原文档给出的迭代实现如下完整保留class Solution: def myPow(self, x: float, n: int) - float: if x 0.0: return 0.0 res 1 if n 0: x 1/x n -n while n: if n 1: res * x x * x n 1 return res逐行解析行代码作用2if x 0.0:底数为 0 时任何正整数次幂都为 0直接返回避免后续无意义计算3return 0.0提前终止4res 1初始化累乘结果乘法单位元5if n 0:处理负指数6x 1/x底数取倒数7n -n指数取绝对值规约为正指数问题9while n:当 $n$ 的二进制位尚未扫描完时循环10if n 1:判断 $n$ 当前最低位是否为 1按位与11res * x最低位为 1说明 $n$ 的这一二进制位贡献了 $x^{2^i}$累乘进结果12x * x将 $x$ 平方为下一二进制位准备权重 $x^{2^{i1}}$13n 1右移一位扫描 $n$ 的下一个二进制位14return res返回最终结果推导验证当 $n 10 1010_{(2)}$ 时循环依次处理低位到高位第 1 轮最低位为 0不乘入结果x x^2第 2 轮最低位为 1res * x^2x x^4第 3 轮最低位为 0不乘入结果x x^8第 4 轮最低位为 1res * x^8。最终res x^2 * x^8 x^10与分治推导完全一致。递归版本分治思路的直接实现原文档指出该思路可用递归实现、也可转递推。下面的递归写法与上面的迭代写法等价区别在于递归会占用 $O(\log n)$ 的调用栈空间可作为一种思路对照class Solution: def myPow(self, x: float, n: int) - float: if n 0: x 1 / x n -n return self._pow(x, n) def _pow(self, x: float, n: int) - float: if n 0: # 递归基任何非零数的 0 次方为 1 return 1.0 half self._pow(x, n // 2) if n % 2 0: # n 为偶数x^n (x^(n/2))^2 return half * half return half * half * x # n 为奇数x^n (x^(n/2))^2 * x6. 复杂度分析时间复杂度$O(\log n)$。循环次数等于 $n$ 的二进制位数即 $O(\log_2 n)$递归版本同理每次递归指数减半。空间复杂度$O(1)$。迭代版本仅使用常数个变量res、x、n递归版本由于调用栈深度为 $O(\log n)$空间复杂度为 $O(\log n)$。相比之下朴素累乘方法的时间复杂度为 $O(n)$空间复杂度为 $O(1)$。从 $O(n)$ 到 $O(\log n)$ 的跨越正是分治「每步规模减半」的收益所在。7. 边界情况与易错点负指数必须先转换底数为倒数、指数取绝对值再进入幂运算主流程避免循环条件while n对负数直接失效。底数为 00^n$n 0$的结果为 0。原代码在进入主流程前对x 0.0提前返回既保证了正确性也避免了浮点精度问题。注意该提前返回同时覆盖了 $x0, n0$ 的情况此时数学上无定义LeetCode 数据范围限定 $x^n \le 10^4$实际评测不会出现该歧义组合。指数绝对值极值$n -2^{31}$ 时-n在 32 位整数下会溢出。Python 整数无此限制若用其他语言实现应先将n存入long再取绝对值。浮点输出格式示例输出要求保留 5 位小数如1024.00000实际提交时函数返回浮点数即可精度问题由评测系统按误差判定。8. 本题在 AlgoNote 知识体系中的位置分治算法本题被 分治算法章节 列为「练习题目」之首是该章节「拆分—求解—合并」三步骤的极简演示将 $x^n$ 拆为 $x^{n/2} \times x^{n/2}$分解递归计算 $x^{n/2}$求解再乘回去合并。递归算法递归算法章节 阐述了「递归是分治的实现手段之一」本题递归版与迭代版正好互为印证。位运算位运算章节 介绍了按位与、右移等基础操作本题迭代版正是用n 1与n 1完成二进制扫描的典型应用。Python 内置pow的实战佐证在仓库的 Rabin-Karp 字符串匹配实现 中pow(d, m - 1) % q正是利用内置快速幂在模意义下计算 $d^{m-1}$见该文件第 13 行用于滚动哈希的权重计算。这说明快速幂不仅是竞赛题考点也是真实算法工程如哈希、RSA 加密中的底层依赖。9. 相关阅读与练习同目录其他分治/数学类题解最大子数组和、多数元素幂运算进阶题超级次方0372. Super Pow在模 $1337$ 下计算大指数幂进一步考察分治与数学性质算法基础前置算法复杂度理解 $O(n)$ 与 $O(\log n)$ 的差距、分治算法总览题解总目录0001-0099 题解列表一句话总结Pow(x, n) 是分治思想的「最小化考场」——用好「指数减半、结果自乘」的奇偶分解再用位运算把递归改写成迭代即可在 $O(\log n)$ 时间内完成任意整数次幂的计算。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 50. Pow(x, n) 快速幂题解从 O(N) 遍历到 O(logN) 位运算的完整演进LeetCode 50. Pow x, n 快速幂题解从 O N 遍历到 O logN 位运算的完整演进 本篇文章围绕「leetcode 题解」仓库 REA文档教程知识库t5-small-qg-hl高级应用构建智能问答系统的10个实战场景t5 small qg hl高级应用构建智能问答系统的10个实战场景 t5 small qg hl是一款基于T5架构的高效问答生成模型专为从文本中提取关键信7个Python算法优化技巧从O(n²)到O(n log n)的性能蜕变7个Python算法优化技巧从O n² 到O n log n 的性能蜕变 在Python编程中算法效率往往决定了程序的性能上限。 GitHub 加速计划 /示例工程教程上一篇TensorFlow模型加载终极指南5种预训练模型复用与微调完整教程下一篇Plus Jakarta Sans 字体安装与使用完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考