快速幂

快速幂

简介

根据名称，快速、幂。幂代表次方，连在一起就是快速的计算数的n次方。核心思想是降低幂，减少运算次数。

举个例子：计算$x^{50}$一般我们会这样去计算，$a^n=\underbrace{a\times a \times \cdots \times a}_\text{n个a} $ ，但是需要计算n次，

如果我们选择使用使用${(x^2)}^{25}$, 只需要计算25次，也就是$\frac{n}{2}$次。
$$
\begin{align}
令x_1=& x \
x^{50} =& x_1^{50}\
=&(x_1^2)^{25}\tag{1}
\end{align}
$$

不断将指数降低，同时底数增大，时间复杂度会来到$O(log_2^n)$

需要注意的是

• 当需要降低的幂n为奇数的时候，我们需要在前面乘以当前的值，例如：上面的25次幂我们继续降低幂次，应该是

$$
\begin{align}
设x_n =& x_{n-1} \times x_{n-1} = x_{n-1}^2, x_1=x\
\
x^{50} =& (x_1^2)^{25} \tag{1}\

=& (x_2)^{25} \tag{2}\
=&x_2 \times(x_2^2)^{12}\

=& x_2 \times x_3^{12}\
=& x_2 \times (x_3^2)^6\
=& x_2 \times x_4^6\
=& x_2 \times (x_4^2)^3\
=& x_2 \times (x_5)^3\
=& x_2 \times x_5 \times x_6\

\end{align}
$$

从计算表达式可以看出来我们只需要计算7次（$$x_1x_1, …, x5x5, x_2 \times x_5 \times x_6$$）就可以将式子求出来。

代码

    /**
     * 快速幂求x^n(递归)
     * @param x 底数
     * @param n 幂
     * @return 结果
     */
    public int power1(int x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n % 2 == 1) {
            return x * power1(x, n >> 1);
        }
        return power1(x, n >> 1);
    }

    /**
     * 快速幂求x^n(非递归)
     * @param x 底数
     * @param n 幂
     * @return 结果
     */
    public int power2(int x, int n) {
        if (n == 0) {
            return 1;
        }
        int res = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                res = res * x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }

矩阵快速幂

矩阵快速幂是快速幂的思想推广，一般用于线性齐次方程。快速求解递推关系式。

例子1：斐波那契数列

斐波那契数列有个显著的递推公式, 满足线性齐次。
$$
F(n) = F(n-1) + F(n-2)
$$
我们使用矩阵来表达
$$
\begin{align}
\left[
\begin{matrix}
F(n) \
F(n-1) \
\end{matrix}
\right]
= &
\left[
\begin{matrix}
1 & 1 \
1 & 0 \
\end{matrix}
\right]
\times
\left[
\begin{matrix}
F(n-1) \
F(n-2) \
\end{matrix}
\right]
\=&
\left[
\begin{matrix}
1 & 1 \
1 & 0 \
\end{matrix}
\right]
\times
\left[
\begin{matrix}
1 & 1 \
1 & 0 \
\end{matrix}
\right]
\times
\left[
\begin{matrix}
F(n-2) \
F(n-3) \
\end{matrix}
\right]
\=& \cdots
\=&
\left[
\begin{matrix}
1 & 1 \
1 & 0 \
\end{matrix}
\right]
^{n-1}
\times
\left[
\begin{matrix}
F(1) \
F(0) \
\end{matrix}
\right]
\end{align}
$$

代码

    /**
     * 思路：矩阵快速幂
     *
     * 时间复杂度：O（logn）
     * 空间复杂度：O（1）
     * @param n 第n个数
     * @return 第n个数的前两数之和
     */
    public int fib3(int n) {
        if (n <= 1) {
            return n;
        }
        int[][] m = {{1,1},{1,0}};
        return pow(m, n -1)[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        int[][] result = {{1,0},{0,1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                result = multiply(a, result);
            }
            a = multiply(a, a);
            n >>= 1;
        }
        return result;
    }


    /**
     * 2x2矩阵相乘
     *
     * @param a 矩阵a
     * @param b 矩阵b
     * @return 矩阵
     */
    public int[][] multiply(int[][] a , int [][] b) {
        int[][] temp = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                temp[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j];
            }
        }
        return temp;
    }