x**n两种递归实现的时间复杂度差异疑问

我为练习递归写了两个Python函数计算x**n，结果完全一致，但其中一个耗时是另一个的两倍。用cProfile计时发现Solution类的myPow耗时是Solution2的两倍，理论上二者时间复杂度都是O(log n)，想知道原因。

代码实现 #

Solution类 #

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1
        if n == 1:
            return x
        if n == -1:
            return 1/x

        if n % 2 == 0:
            ## even
            return self.myPow(x * x, n / 2)
        else:
            if n > 0:
                return x * self.myPow(x * x, (n-1)/2)
            else:
                return 1/x * self.myPow(x * x, (n+1) / 2 )

Solution2类 #

class Solution2(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """

        ## Base cases
        if n == 0:
            return 1
        if n == 1:
            return x

        t = self.myPow(x, abs(n) // 2)

        if n > 0:
            if n % 2 == 0:
                return t * t
            else:
                return x * t * t
        else:
            if n % 2 == 0:
                return 1 / (t * t)
            else:
                return 1 / (x * t * t)

性能差异原因 #

虽然两个实现的时间复杂度都是O(log n)，但实际运行的常数开销差异导致了耗时两倍的差距，具体原因如下：

• 分支判断的额外开销：Solution的函数里有三个基础条件判断（n==0、n==1、n==-1），且非基础情况需要嵌套判断奇偶和正负，多层分支会增加每次函数调用的判断耗时；而Solution2只保留两个基础条件，先统一计算绝对值的递归结果，再做一次扁平的分支判断，逻辑更简洁，判断次数更少。
• 递归参数的计算开销：Solution每次递归调用前都要计算x*x作为新的入参，这个乘法操作伴随每一层递归执行；而Solution2的递归调用仅传递原x，乘法操作t*t只在递归返回后执行一次，复用了递归结果t，减少了递归过程中的计算开销。
• 负数n的处理效率：Solution对负数n的处理分散在每一层递归中，每次都要判断正负并调整计算逻辑；而Solution2直接将负数转换为绝对值计算，最后统一处理倒数，把负数逻辑和递归逻辑分离，简化了递归流程，降低了每层递归的复杂度。

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