1:
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n < 0:
return 1.0/self.myPow(x, -n)
elif n==0:
return 1
elif n == 1:
return x
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:
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n==0:
return 1
elif n==1:
return x
elif n < 0:
return 1 / self.myPow(x, -n)
elif n%2 == 1:
return x * self.myPow(x, n-1)
else:
return self.myPow(x*x, n//2)
我用两种不同的方式实现了幂函数。
我期望时间复杂度是相同的,但是在 leetcode 上尝试时,1)某些示例超时并失败,但 2)成功了。
出现这种情况有什么原因吗?我认为两者的时间复杂度是相同的。
if 条件的顺序不应影响该条件的复杂性,并且对性能的影响可以忽略不计。最大的区别是在最后两种情况下都有 2 次调用递归函数
self.myPow(x, n//2)
。您应该调用它一次,将其存储在变量中,然后将它们相乘以避免冗余。
# 1
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n < 0:
return 1.0/self.myPow(x, -n)
elif n==0:
return 1
elif n == 1:
return x
elif n%2 == 1:
half_pow = self.myPow(x, n//2)
return half_pow * half_pow * x
else:
half_pow = self.myPow(x, n//2)
return half_pow * half_pow
这将复杂度从 O(n) 降低到 O(log(n))