某米员工爆料：35岁被裁后，投百份简历无人问津，一气之下把薪资由2W调为3W，简历改成英文，结果出乎意料！！！
虎哥约 4 分钟算法题：Pow(x, n)
最近刷到一道经典的算法题：实现一个函数 pow(x, n)，计算 x 的 n 次幂。这道题不仅是面试的常客，还时不时出现在各种竞赛中，让人一看就头大。不过别急，作为一个写代码写到怀疑人生的普通程序员，咱们可以把它分解得简单点。
题目要求
输入两个参数：x 是底数，n 是指数，返回值是 x 的 n 次幂。比如：
pow(2, 10) # 返回 1024
pow(2, -2) # 返回 0.25
这道题的坑在哪？先来吐槽一下：
n有可能是负数，这意味着要计算倒数，比如 (2^{-2} = 1 / 2^2 = 0.25)。指数可能非常大（面试官爱用的套路），比如 (10^9)，如果直接循环暴力乘法，别说结果了，CPU都能给你烧冒烟。 当然还有边界情况，比如 (x = 0, n = 0)，这种就得小心踩雷。
解法脑暴一般来说，我们可以从三种思路入手：
暴力解法：一层循环，直接把 x连乘n次。简单粗暴，但效率感人，时间复杂度 (O(n))。分治法：利用数学上的幂性质 (x^n = x^{n/2} \times x^{n/2})，通过递归分解，时间复杂度 (O(\log n))。这就像程序员写代码一样，拆分任务很关键。 优化再优化：处理负指数和边界情况。
代码来了我们直接用分治法写个 Python 实现：
def pow(x, n):
# 处理负指数
if n < 0:
x = 1 / x
n = -n def fast_pow(base, exp):
if exp == 0:
return 1
half = fast_pow(base, exp // 2)
if exp % 2 == 0:
return half * half
else:
return half * half * base
return fast_pow(x, n)
# 测试用例
print(pow(2, 10)) # 输出 1024
print(pow(2, -2)) # 输出 0.25
print(pow(0, 0)) # 输出 1
分析一下
递归拆分：
每次把问题规模减半，直到指数变成 0。指数为偶数时，结果是两次 half相乘；为奇数时，还得多乘一个底数。递归本质上是“分工合作”的体现，程序员的心路历程不也这样嘛？把大任务分成小块，一个个搞定。
时间复杂度：
因为指数每次都折半，所以总共递归次数是 (O(\log n))，很快，计算 (2^{10}) 也不过递归了 4 次。
边界处理：
(n < 0) 时先求倒数，(x^n = 1 / x^{-n})。 (x = 0, n = 0) 返回 1（约定俗成），不然数学家都吵起来了。
暴力法踩坑记
如果你一开始尝试暴力解法，比如直接写个循环乘法，像这样：
def pow(x, n):
result = 1
for _ in range(abs(n)):
result *= x
return result if n >= 0 else 1 / result
乍一看没毛病，但当 n 超过百万时，程序卡死的速度比老板喊你加班还快。如果在面试中写出这种，面试官估计就会暗戳戳加一句：“你还有什么问题要问我们的吗？”——潜台词是：你凉了。🌚
细节补充递归虽然优雅，但有些语言栈空间有限，可能会爆栈。这时候可以用迭代法实现，效果差不多，但更安全：
def pow(x, n):
if n < 0:
x = 1 / x
n = -n
result = 1
while n:
if n % 2 == 1:
result *= x
x *= x
n //= 2
return result
迭代版其实和递归版一样，都是用到了分治思想，不过不用递归了，直接撸个循环，把栈变成变量。
那么大家还有其他优化思路吗？欢迎留言，一起交流下！👨💻
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。