以两种不同的方式实现电源功能。这两个代码之间的最大区别是什么?

在这种特定情况下,if条件的顺序不应影响复杂性,对性能的影响可以忽略不计。最大的区别是有2个递归调用 self.myPow(x, n//2) 在解决方案#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:
            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)),与解决方案2相同

如果你仔细观察这两个实现具有两种不同的复杂性,第一个实现的时间复杂性为 O(2^log n) = O(n) 第二个问题的复杂性为 O(log n) .

对于第一个实现,我们可以说每次平均有两个调用 myPow 而在第二种情况下,递归函数最多被调用一次以执行。即使在第一个实现中,你试图将问题细分为 n//2 当您两次调用函数以获得相同的结果时,它将变得无效。

注意:如果您存储以下值 self.myPow(x, n//2) 在变量中,你避免了对函数的冗余调用,使其复杂性为O(logn)。

这里是对代码的逐行分析:

1.

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0: # O(1)
            return 1.0/self.myPow(x, -n) # O(log n)
        elif n == 0: # O(1)
            return 1 # O(1)
        elif n == 1: # O(1)
            return x # O(1)
        elif n % 2 == 1: # O(1)
            # O(2 * log n + 1) = O(log n) - Two recursive calls on n//2 and a multiplication (see my explanation before)
            return self.myPow(x, n//2) * self.myPow(x, n//2) * x
        else: # O(1)
            # O(2 * log n) = O(log n) - Two recursive calls with n//2 (see my explanation before)
            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: # O(1)
            return 1 # O(1)
        elif n==1: # O(1)
            return x # O(1)
        elif n < 0: # O(1)
            # O(log n) since it will have the same complexity of a call with n positive, that is the same complexity of the greater between the two following returns
            return 1 / self.myPow(x, -n)
        elif n%2 == 1: # O(1)
            # O(log n) since it will resolve with n as even, so it will follow the "n-even complexity"
            return x * self.myPow(x, n-1)
        else: # O(1)
            # O(log n) since it actively reduces the problem by its half
            return self.myPow(x*x, n//2)