LeetCode 50. Pow(x, n)：从暴力法到快速幂的优化之路

LeetCode 中经典的幂运算题目——50. Pow(x, n)。这道题看似简单只需计算 x 的 n 次幂但隐藏着从“暴力求解”到“高效优化”的核心思路也是面试中常考的基础算法题适合新手入门理解“分治思想”和“迭代优化”。先明确题目要求实现 pow(x, n)即计算 x 的整数 n 次幂函数n 可以是正数、负数或 0无需考虑大数溢出问题题目默认测试用例在有效范围内。一、暴力法直观但低效的初始思路拿到题目最直观的想法就是“重复乘法”——如果 n 是正数就把 x 连续乘 n 次如果 n 是负数就先计算 x 的 |n| 次幂再取倒数如果 n 是 0直接返回 1任何数的 0 次幂都是 1。对应代码就是题目中给出的 myPow_1我们来逐行解析其逻辑functionmyPow_1(x:number,n:number):number{// 边界处理x为0时0的任意正次幂都是00的0次幂题目默认返回1这里已被n0覆盖if(x0)return0;// 边界处理任何数的0次幂都是1if(n0)return1;// 处理负指数将负指数转化为正指数底数变为倒数constXn0?x:1/x;constNn0?n:-n;// 初始化结果为底数因为要乘N次初始值为X再乘N-1次letansX;// 循环N-1次累计乘法for(leti1;iN;i){ans*X;}returnans;};暴力法的优点与局限优点逻辑简单、代码易写上手难度低适合初学者理解幂运算的本质。局限时间复杂度太高。当 n 是一个很大的整数比如 10^9时循环需要执行 10^9 - 1 次这会导致程序超时LeetCode 的测试用例中n 可以达到 ±2^31 - 1暴力法必然过不了。举个例子计算 pow(2, 1000000)暴力法需要循环 999999 次而优化后的方法只需几十次计算效率差距天壤之别。因此我们需要找到一种更高效的计算方式——快速幂。二、快速幂分治思想的高效实现快速幂的核心思路是**“分而治之”**将幂运算拆分成更小的子问题通过“指数折半、底数平方”的方式减少乘法次数。核心原理如下对于任意整数 n我们可以将其拆分为若 n 是偶数x^n (x2)(n/2) —— 底数平方指数折半只需计算 (x²) 的 (n/2) 次幂若 n 是奇数x^n x * (x2)((n-1)/2) —— 先多乘一次当前底数再按偶数的逻辑拆分若 n 是负数x^n 1 / x^(-n) —— 转化为正指数的倒数再按上述逻辑计算。这样一来每次计算都能将指数规模缩小一半时间复杂度从暴力法的 O(n) 优化到 O(log n)即使 n 是 10^9也只需约 30 次计算效率极大提升。迭代版快速幂myPow_2 解析题目中给出的 myPow_2 是快速幂的迭代实现比递归实现更节省栈空间避免递归深度过大导致栈溢出我们逐行拆解逻辑functionmyPow_2(x:number,n:number):number{// 边界处理任何数的0次幂都是1if(n0)return1;// 结果初始化初始值为1后续累计乘法letres1;// 取n的绝对值统一按正指数处理最后再处理负指数letabsNMath.abs(n);// 循环条件指数折半到0时停止while(absN0){// 若当前指数是奇数需要多乘一次当前的底数对应奇数拆分逻辑if(absN%21){res*x;}// 底数平方对应指数折半后的底数更新x*x;// 指数折半向下取整处理奇数时(n-1)/2等价于Math.floor(n/2)absNMath.floor(absN/2);}// 若n是负指数返回结果的倒数否则直接返回结果returnn0?res:1/res;};迭代快速幂的执行流程举例理解以 pow(2, 5) 为例一步步看代码如何执行初始值res1absN5x2第一次循环absN50absN是奇数5%21res122x224absNMath.floor(5/2)2第二次循环absN20absN是偶数res不变还是2x4*416absNMath.floor(2/2)1第三次循环absN10absN是奇数res21632x1616256absNMath.floor(1/2)0循环结束n50返回res32正确结果2^532。再举一个负指数例子pow(2, -3)初始值res1absN3x2循环执行后res8对应2^38n-30返回1/80.125正确结果2^-31/8。三、两种方法对比总结方法时间复杂度空间复杂度优点缺点暴力法myPow_1O(n)O(1)逻辑简单、代码易写效率低n 较大时超时快速幂myPow_2O(log n)O(1)效率极高适配大指数逻辑稍复杂需理解分治思想四、关键注意点与拓展边界处理n0 时无论 x 是什么除了 0^0题目默认返回 1都返回 1x0 时若 n0 返回 0n0 会出现数学错误但题目测试用例大概率不会包含这种情况。负指数处理核心是“转化为正指数 取倒数”避免直接处理负指数导致逻辑混乱。指数折半的细节Math.floor(absN / 2) 等价于整数除法absN 1位运算效率更高可以替换优化但可读性稍差。递归版快速幂除了迭代实现也可以用递归实现分治思想更直观但递归深度会达到 O(log n)当 n 极大时可能出现栈溢出因此迭代版更推荐在实际开发中使用。五、总结LeetCode 50. Pow(x, n) 的核心是“优化幂运算的效率”从暴力法的 O(n) 到快速幂的 O(log n)本质是分治思想的应用——将大问题拆分成小问题通过重复利用中间结果减少计算次数。对于新手来说建议先理解暴力法的逻辑再思考“为什么暴力法效率低”进而推导快速幂的优化思路结合例子手动模拟执行流程就能轻松掌握。这道题不仅是一道算法题更能帮助我们理解“优化”的本质不是推翻重来而是找到问题的规律用更巧妙的方式减少冗余计算。