以两种不同的方式实现幂函数。这两个代码有什么大的区别?

问题描述 投票:0回答:1
  • 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)成功了。

出现这种情况有什么原因吗?我认为两者的时间复杂度是相同的。

python big-o
1个回答
0
投票

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))

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.