迭代平方（Iterated Squaring）的时间复杂度分析问询

嘿，我们来一步步拆解你给出的迭代平方算法的时间复杂度，结合mult()函数的复杂度定义来推导它的上界。

算法核心流程回顾 #

先看一下你的代码实现：

def power(a, b):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = mult(result, a)
        a = mult(a, a)
        b = b // 2
    return result

这是标准的快速幂实现，它通过把指数b拆成二进制形式，把原本需要b次乘法的计算压缩到O(log b)次循环里——毕竟每次循环b都会被整除2，循环次数刚好等于b的二进制位数，也就是⌊log₂b⌋ + 1。

乘法操作的复杂度简化 #

题目里说mult(x, y)的复杂度是x*y + x + y，这里的x和y是输入数的位长。其实这里x*y是绝对的主导项：当x和y都大于等于1时，x+y最多也就2xy，所以整个表达式可以简化成O(x*y)，这是我们分析的核心基础。

位长变化与总复杂度计算 #

假设初始时输入a的位长是n（也就是a是个n位的整数），我们来逐个分析循环里的乘法操作：

1. 每次循环必做的a = mult(a, a) #

这个平方操作每次都会执行，而a的位长会跟着循环次数翻倍：

• 第1次循环：a是n位，复杂度是O(n*n) = O(n²)
• 第2次循环：a变成了2n位（n位数平方最多是2n位），复杂度是O((2n)*(2n)) = O(4n²)
• 第3次循环：a变成4n位，复杂度是O((4n)*(4n)) = O(16n²)
• ...
• 第t次循环（t = O(log b)）：a的位长是n*2^{t-1}，复杂度是O((n*2^{t-1})²) = O(n²*4^{t-1})

这是个首项为n²、公比为4的等比数列，求和结果是：
$$n² * \frac{4^t - 1}{3}$$
因为t = O(log b)，代入后4^t = 4^{O(log b)} = (2^2)^{O(log b)} = 2^{O(log b)} = b²（毕竟4^{log₂b} = b²），所以这部分的总复杂度是O(n²b²)。

2. 条件触发的result = mult(result, a) #

只有当b是奇数的时候才会执行这个操作，最多执行O(log b)次。每次执行时，result的位长不会超过最终结果a^b的位长（也就是O(n*b)），a的位长最多也是O(n*b)，所以单次操作的复杂度是O((n*b)*(n*b)) = O(n²b²)。就算执行O(log b)次，总复杂度也还是被O(n²b²)覆盖——毕竟log b和b比起来就是个小因子，不会影响上界。

最终时间复杂度上界 #

把两部分的复杂度加起来，这个迭代平方算法的时间复杂度上界就是：
O(n²b²)
这里的n是输入a的位长。

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