• 找到分类:

  • 快速幂

    04-25-19

    幂运算是非常常见的一种运算,求a^{n}最容易想到的方法便是通过循环逐个累乘,其复杂度为O(n),这在很多时候是不够的,所以我们需要一种算法来优化幂运算的过程

    快速幂这个东西比较好理解,今天把它系统的总结一下防止忘记.

    首先,快速幂的目的就是做到快速求幂,假设我们要求a^{b},按照朴素算法就是把a连乘b次,这样一来时间复杂度是O(b),即是O(n)级别,快速幂能做到O(logn),快了好多好多.

    它的原理如下:

    假设我们要求a^{b},将b写为二进制的形式,该二进制数第i位的权为2^{i-1}.

    e.g. b=11时, a^{11}=a^{2^{0}+2^{1}+2^{3}}

    11的二进制是1011,11 = 2^{3} \times 1 + 2^{2} \times 0 + 2^{1} \times 1 + 2^{0} \times 1,因此,我们将 a^{11}转化为算 a^{2^{0}}*a^{2^{1}}*a^{2^{3}},也就是a^{1}*a^{2}*a^{8} .原来算11次,现在算三次,但是这三项貌似不好求.

    不急,下面会有详细解释.

    由于是二进制,很自然地想到用位运算这个强大的工具:&(按位与)和>>(右移运算符). &运算通常用于二进制取位操作,例如一个数x& 1 的结果就是取二进制的最末位。还可以判断奇偶,e.g.x&1==0为偶,x&1==1为奇。 >>n运算比较单纯,将数字写成二进制形式,右移n位,即将二进制数去掉最后n位.   

    int binaryPow(int a, int b) {
        int ans = 1, base = a;
        while (b != 0) {
            if (b & 1 != 0)
                ans *= base;
            base *= base;
            b >>= 1;
        }
        return ans;
    }

    代码很短,也很好理解,以b=11为例,11_{10}=1011_{2},二进制从右向左算,但乘出来的顺序是 a^{2^{0}}*a^{2^{1}}*a^{2^{3}},是从左向右的.我们不断的让base*=base目的即是累乘,以便随时对ans做出贡献.

    其中要理解base*=base这一步:因为 base*base  \Longleftrightarrow base^{2},下一步再乘,就是base^{2}* base^{2} \Longleftrightarrow base^{4},然后同理  base^{4}* base^{4} \Longleftrightarrow base^{8},由此可以做到base \longrightarrow base^{2} \longrightarrow base^{4} \longrightarrow base^{8} \longrightarrow base^{16} \longrightarrow base^{32} \cdots指数正是2^{i},再看上面的例子,a^{1}*a^{2}*a^{8},这三项就可以完美解决了.

    如果需要取模的话,直接在每一步运算中对base和ans取模即可.

  • tset0

    04-25-19

    \Longleftrightarrow

  • test

    04-25-19
    
    

    D(x) = \begin{cases}O(1), & \text{if} \quad n \leq c;\\2T(n/2)+O(n), & \text{if} \quad n > c\end{cases}