写一个Python快速求幂

以下是一个Python实现的快速求幂函数：

def pow(base, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        return pow(base * base, exponent // 2)
    else:
        return base * pow(base, exponent - 1)

这个函数使用了一个递归算法来快速求幂。它的基本思想是将指数分解成二进制，然后通过连续平方来计算幂。具体来说，如果指数是偶数，我们可以将底数平方并将指数除以2，然后再次递归地调用pow函数。如果指数是奇数，我们可以将底数乘以pow(base, exponent - 1)。通过这种方式，我们可以使用O(log n)的时间复杂度来计算幂，而不是使用O(n)的暴力方法。

相关问题

写一个Python的快速幂算法

我可以用以下代码来写一个Python的快速幂算法：def quick_power(base, exponent):
result = 1
while exponent > 0:
if exponent & 1 == 1:
result *= base
exponent >>= 1
base *= base
return result

python 快速幂

Python中的快速幂是一种用于快速计算幂运算的算法。它通过将指数进行二进制拆分，并利用指数的二进制表示中的特性来减少计算量。

以下是Python中实现快速幂的一种常见方法：

def fast_power(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result *= base
        base *= base
        exponent //= 2
    return result

在这个方法中，我们使用了一个循环来迭代计算。首先，我们将结果初始化为1。然后，我们不断地将底数平方，并将指数除以2，直到指数为0为止。如果当前指数是奇数，我们就将结果乘以底数。最后，返回计算得到的结果。

这种方法的时间复杂度为O(log n)，其中n是指数的大小。相比于简单的循环逐个相乘的方法，快速幂可以大大减少计算次数，提高计算效率。