Python实现Pow(x,n)时优化时空复杂度解决超时问题

初始版本存在的问题 #

你最初的实现使用列表存储所有中间计算结果，会产生O(n)的不必要内存开销，代码如下：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        temp = [];
        span = range(1,abs(n))
        if n ==0:
            return 1
        if abs(n)==1:
            temp.append(x)
        else:
            for y in span:
                if y == 1:
                    temp = []
                    temp.append(x*x)
                else:
                    temp.append(temp[-1] * x)
        if(n < 0):
            return 1/temp[-1]
        else:
            return temp[-1]

你后续做的第一步优化方向是对的：用单个变量替代列表存储临时计算值，把空间复杂度降到了O(1)，修改后的代码如下：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        span = range(1,abs(n))
        if n ==0:
            return 1
        if abs(n)==1:
            temp = x
        else:
            for y in span:
                if y == 1:
                    temp = x*x
                else:
                    temp = temp * x
        if(n < 0):
            return 1/temp
        else:
            return temp

这版代码的核心瓶颈是时间复杂度为O(n)，需要逐次做乘法，当n取2147483647这类极大值时，循环次数超过20亿次，必然触发超时。

最优优化思路：迭代版快速幂 #

不需要引入任何特殊数据结构，仅通过指数二进制拆分就能把时间复杂度降到O(log n)——对于n=2147483647的场景，仅需要31次循环即可完成计算，完全不会超时。

核心逻辑 #

• 任何整数指数都可以拆分为二进制位的和，比如n=5（二进制101）等价于4+1，因此x^5 = x^4 * x^1
• 迭代过程中持续对底数做平方操作，对应指数权重每次翻倍
• 遍历指数的二进制位，只要当前位为1，就把当前权重对应的底数乘到最终结果里
• 负数指数可以提前转换：把x取倒数，n转为正整数后再统一计算

优化后代码 #

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # 统一处理负指数场景
        if n < 0:
            x = 1 / x
            n = -n
        res = 1.0
        while n > 0:
            # 当前二进制位为1，累加当前权重的幂值到结果
            if n & 1:  # 等价于n%2 ==1，位运算速度更快
                res *= x
            # 底数平方，权重翻倍
            x *= x
            # 指数右移一位，等价于n = n//2
            n >>= 1
        return res

优化收益 #

• 空间复杂度保持O(1)，仅使用3个变量，无额外内存开销
• 时间复杂度降至O(log n)，相比原始O(n)实现，大输入场景下性能提升超千万倍
• 代码逻辑更简洁，不需要额外写分支处理n=0、n=±1等边界情况，循环逻辑天然覆盖所有场景

内容的提问来源于stack exchange，提问作者Noble Eugene