【Java系列】斐波拉契数列

向右看齐 2023-09-30 18:29 13阅读 0赞

**介绍**

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：*F*(0)=0，*F*(1)=1, *F*(n)=*F*(n - 1)+*F*(n - 2)（*n* ≥ 2，*n* ∈ N\*）在现代物理、晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

--------------------

**Java编码实现斐波那契数列**

**方案1：递归**

根据斐波那契数列的数学表示方式：*F*(1)=1，*F*(2)=1, *F*(n)=*F*(n - 1)+*F*(n - 2)（*n* ≥ 2，*n* ∈ N\*）

很容易就可以得出；

package com.example.demo;
    
    /**
     * @author Biyu
     * @projectName demo
     * @className: Fibonacci
     * @description //TODO
     * @date: 2023-01-05 
     */
    public class Fibonacci {
        public static void main(String[] args) {
            for (int i = 1; i <= 10; i++){
                System.out.printf("Fibonacci of %d is: %d\n", i, fib1(i));
            }
        }
    
        public static int fib1(int n) {
            if(n <= 2) {
                return 1;
            }
            return fib1(n - 1) + fib1(n - 2);
        }
    }

问题：使用以上代码完成斐波那契数列，时间复杂度是0(n^2),空间复杂度是0(n);

**方案2： 将递归转化为非递归优化**

定义一个数组存放，存放斐波拉契数列每一项数据；免去递归调用；

package com.example.demo;
    
    /**
     * @author Biyu
     * @projectName demo
     * @className: Fibonacci
     * @description //TODO
     * @date: 2023-01-05 
     */
    public class Fibonacci {
        public static void main(String[] args) {
            for (int i = 1; i <= 10; i++){
                System.out.printf("Fibonacci of %d is: %d\n", i, fib2(i));
            }
        }
    
        public static int fib2(int n) {
            if(n <= 2) return 1;
            int[] array = new int[n + 1];
            array[1] = array[2] = 1;
            for (int i = 3; i <= n; i++) {
                array[i] = array[i - 1] + array[i - 2];
            }
            return array[n];
        }
    }

**空间复杂度：**额外定义了一个数组；空间复杂度依然是0(n)，但是没有递归产生的空间。

**时间复杂度：**时间复杂度是0(n)

**方案3：定义2个变量代替数组**

package com.example.demo;
    
    /**
     * @author Biyu
     * @projectName demo
     * @className: Fibonacci
     * @description //TODO
     * @date: 2023-01-05 
     */
    public class Fibonacci {
        public static void main(String[] args) {
            for (int i = 1; i <= 10; i++){
                System.out.printf("Fibonacci of %d is: %d\n", i, fib3(i));
            }
        }
    
        public static int fib3(int n) {
            if(n <= 2) {
                return 1;
            }
            int n1 = 1;
            int n2 = 1;
            for (int i=3;i<=n;i++) {
                n2 = n1 + n2;
                n1 = n2 - n1;
            }
            return n2;
        }
    }

**空间复杂度：**不需要额外定义数组，只定义2个变量即可，所以空间复杂度0(1);

**时间复杂度：**时间复杂度是0(n)

**方案4:利用尾递归实现，java可以对尾递归的栈空间优化**

package com.example.demo;
    
    /**
     * @author Biyu
     * @projectName demo
     * @className: Fibonacci
     * @description //TODO
     * @date: 2023-01-05 
     */
    public class Fibonacci {
        public static void main(String[] args) {
            for (int i = 1; i <= 10; i++){
                System.out.printf("Fibonacci of %d is: %d\n", i, fib4(i));
            }
        }
    
        public static int fib4(int n) {
            return fib4(n,1,1);
        }
    
        public static int fib4(int n, int n1,int n2) {
            if(n <= 2) {
                return n2;
            }
            return fib4(n - 1,n2,n1+n2);
        }
    }

**空间复杂度：**递归的深度为0(n)，但是由于是尾递归，优化后的空间复杂度是0(1)

**时间复杂度：**时间复杂度是0(n)