快速幂小结

（本文不涉及取模运算……）

快速幂，顾名思义，就是快速地求幂运算。

现在要求x=yⁿ的值，最朴素的解法：

int pow(int y, int n) {
    int result = 1;
    for (int i = 0; i < n; i++) {
        result *= y;
    }
    return result;
}

x=pow(y,n)

复杂度是O(n)

当n是偶数的时候，我们设n=2*m，则x=yⁿ=y^2*m=(y^m)^2

当n是奇数的时候，我们设n=2*m+1，则x=yⁿ=y^2*m+1=y*(y^m)^2

这样，我们就把复杂度从O(n)降到了O(n/2)，递归下去，算法的复杂度就是O(log₂n)……该怎么解释这个……其实我不会……

用递归实现比较容易理解，具体代码：

int quick_pow(int y, int n) {
    if (n == 0) return 1;
    if (n % 2 == 1) {
        // n是奇数 n=2*m+1
        // x = y^(2*m+1) = y * (y^m)^2
        int m = n / 2;
        int temp = quick_pow(y, m);
        return y * temp *temp;
    } else {
        // n是偶数 n=2*m
        // x = y^(2*m) = (y^m)^2
        int m = n / 2;
        int temp = quick_pow(y, m);
        return temp *temp;
    }
}

可以简化一下~~

int quick_pow(int y, int n) {
    if (!n) return 1;
    int temp = quick_pow(y, n >> 1);
    if (n & 1) return y * temp *temp;
    else return temp *temp;
}

非递归的版本也很容易理解啦

int quick_pow(int y, int n) {
    int result = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            // y^n = y^(2*m+1) = y*(y^2)^m
            result *= y;
            // 接下来让y=y^2, n=m
            y = y * y;
            n = n / 2;
        } else {
            // y^n = y^(2*m) = (y^2)^m
            y = y * y;
            n = n / 2;
        }
    }
    return result;
}

简化一下~~~

int quick_pow(int y, int n) {
    int result = 1;
    while (n) {
        if (n & 1) result *= y;
        y = y * y;
        n >>= 1;
    }
    return result;
}

矩阵快速幂

我们都知道斐波那契数列（Fibonacci sequence），1、1、2、3、5、8、13、21、34……每一项是前两项的和。

如果要求第n项，需要从第一项开始递推。

int fibonacci(int n) {
    int a[n];
    a[0] = 1, a[1] = 1;
    for (int i = 2; i < n; i++) {
        a[i] = a[i-1] + a[i-2];
    }
    return a[n-1];
}