问题引入

如何快速求 a^n^

分析

依照 a^n^的定义只需将n个a相乘即可，这样的时间复杂度为o(n)，快速幂算法就是为了加速n个a相乘的过程。

举例来说，当n为2的幂时，比如n = 64，那么只需要乘6次就可到得到结果了。

快速幂.drawio

当n不为2的幂，比如n = 105时，可以将n拆成2的幂的和，即n = 1 + 8 + 32 + 64，即a^105^ = a^1^ * a^8^ * a^32^ * a^64^。

代码

伪代码

对n每次右移1位，当右移k次时，此时n的末尾数字就是n原来第k位上的数字，为1代表2^k^参与到a^n^的计算中，为0则代表不参与。

1
2
3
4
5
6
7
8
function BinExp(a, n) 
    r = 1
    while n != 0
        if n mod 2 == 1
            r = r × a
        a = a × a
        n >> 1
    return r

参考链接