cmath pow与快速幂的时间复杂度对比

`cmath`库中的`pow()`函数通常用于计算两个数的乘方，其时间复杂度是O(log n)，因为它内部实现了一个基于递归或二分查找的方法来减少所需的计算次数。当指数较大时，这种方法相比于直接的逐位相乘（即O(n)），效率更高。

相比之下，快速幂（Fast Exponentiation）算法，也称为平方根法（Square Root Method）或 exponentiation by squaring，它的核心思想是利用指数运算的性质（a^(m+n) = a^m * a^n），通过分治策略将大指数分解为一系列小指数的乘积。这个过程可以大大降低时间复杂度。对于一个大指数k，快速幂可以在O(log k)时间内完成，这比直接计算节省了很多计算步骤。

下面是一个简单的快速幂示例（Python版本）[^2]：

def fast_pow(base, exp):
    if exp == 0:
        return 1
    elif exp % 2 == 0:
        half_exp = fast_pow(base, exp // 2)
        return half_exp * half_exp
    else:
        return base * fast_pow(base, exp - 1)

# 使用快速幂计算n=100时，base=2的100次方
n = 100
v = fast_pow(2, n)

快速幂相对于`cmath.pow()`的优势在于，当指数非常大时，它可以显著提升计算速度。然而，对于较小的指数，两者差别不大，因为`pow()`的内置优化可能已经相当高效。