斐波那契数列

ゝ一纸荒年。 2022-10-29 06:26 34阅读 0赞

\#\#题目描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39

### 思路 ###

1.  递归（函数栈调用消耗太高）  
    时间复杂度O(2^n)，空间复杂度O(n)。
2.  使用循环替换递归  
    时间复杂度O(n)，空间复杂度O(1)。
3.  动态规划  
    时间复杂度O(n)，空间复杂度O(1)。
4.  矩阵快速幂  
    ![1805130-20200215163227344-1078661951.png][]  
    ![1805130-20200215163236520-1637915881.png][]  
    时间复杂度O(lgn)，空间复杂度O(1)。

### 递归算法 ###

public class Solution {
        public int Fibonacci(int n) {
            if(n < 0)    return 0;
            if(n < 2)    return n;
            return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }

### 循环算法 ###

public class Solution {
        public int Fibonacci(int n) {
            int a = 0, b = 1, c = 1;
            while(n-- > 0) {
                a = b;
                b = c;
                c = a + b;
            }
            return a;
        }
    }

### 动态规划 ###

public class Solution {
        public int Fibonacci(int n) {
            int[] dp = new int[] {0, 1};
            while(n-- > 0) {
                dp[1] = dp[0] + dp[1];
                dp[0] = dp[1] - dp[0];
            }
            return dp[0];
        }
    }

### 矩阵快速幂 ###

class Solution {
        private int[][] matmul(int[][] a, int[][] b, int m, int n, int t) {
            int[][] tmp = new int[m][n];
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    tmp[i][j] = 0;
                    for(int k = 0; k < t; k++) {
                        tmp[i][j] += a[i][k] * b[k][j];
                    }
                }
            }
            return tmp;
        }
        
        public int Fibonacci(int n){
            if(n < 1)     return 0;
            if(n == 1)    return 1;
            int[][] matT = new int[][] {
       {1, 1}, {1, 0}};
            int[][] fibT = new int[][] {
       {1}, {0}};
            while(n > 1){
                // 二进制转换，最高位1用最终快速幂矩阵，其余位1用当前幂矩阵
                if(n%2 == 1){
                    fibT = matmul(matT, fibT, 2, 1, 2);
                }
                matT = matmul(matT, matT, 2, 2, 2);
                n /= 2;
            }
            fibT = matmul(matT, fibT, 2, 1, 2);
            return fibT[1][0];
        }
    }

### 简单快速幂求2的n次方 ###

class Solution {
        public long pow(int n) {
            long ans = 1, base = 2;
            while(n > 0) {
                if(n%2 == 1) {
                    ans = (ans * base) % 1000000007;
                }
                base = (base * base) % 1000000007;
                n >>= 1;
            }
            return ans;
        }
    }

### 笔记 ###

1.快速幂余项的个数联想二进制权重  
2.循环实现，三次赋值，一次加法  
dp实现，两次赋值，一次加法，一次减法  
后者效率未见得高  
3.尾递归优化

[1805130-20200215163227344-1078661951.png]: /images/20221024/a9e998007ab247a28cd8a2bae3b2da4f.png
[1805130-20200215163236520-1637915881.png]: /images/20221024/d936d968509a4701930bbbb5143ec138.png