两种幂函数实现方法：为何时间复杂度表现差异显著？

你实现的两个幂函数看似都是分治思路，但实际时间复杂度天差地别，这就是方法1超时、方法2通过的核心原因。

方法1的问题：重复递归调用导致线性时间复杂度 #

方法1的核心坑点在于，计算n//2对应的幂时，连续调用了两次self.myPow(x, n//2)，完全没有缓存结果复用。

举个具体例子，当n=8时：

• 调用myPow(x,8)会触发两次myPow(x,4)
• 每个myPow(x,4)又会触发两次myPow(x,2)
• 每个myPow(x,2)再触发两次myPow(x,1)

最终递归调用总次数是1+2+4+8=15次，也就是n-1次，时间复杂度实际为O(n)。当LeetCode测试用例中出现超大整数n（比如10^9级别）时，这种线性复杂度会让调用次数直接爆炸，触发超时。

方法1的问题核心代码片段：

elif n%2 == 1:
    return self.myPow(x, n//2) * self.myPow(x, n//2) * x
else:
    return self.myPow(x, n//2) * self.myPow(x, n//2)

方法2的优化：单次递归调用实现对数时间复杂度 #

方法2是标准的快速幂实现，每次递归只调用一次自身，彻底避免了重复计算：

• 当n为偶数时，直接计算myPow(x*x, n//2)，把底数平方、指数减半，仅需一次递归
• 当n为奇数时，转化为x * myPow(x, n-1)，最终会进入偶数分支的快速处理逻辑

同样以n=8为例：

• myPow(x,8) → myPow(x²,4)
• myPow(x²,4) → myPow(x^4,2)
• myPow(x^4,2) → myPow(x^8,1)

总调用次数仅为3次，也就是log₂(n)次，时间复杂度为O(logn)。面对超大n时，这种对数复杂度的调用次数极少，完全能通过LeetCode的时间限制。

方法2的优化核心代码片段：

elif n%2 == 1:
    return x * self.myPow(x, n-1)
else:
    return self.myPow(x*x, n//2)

简单总结：方法1看似用了分治思路，但因重复递归调用退化为线性时间复杂度；方法2是真正的快速幂实现，通过单次递归达成对数时间复杂度，这就是二者性能差异的根本原因。

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