斐波那契数列与时间复杂度

一、斐波那契数列探究

1. 概念

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、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*）

它的起源不论是在数学、生活与自然方面都非常有用，更多关于斐波那契的介绍可参考下面知乎大佬的文章

斐波那契数列在数学和生活中的使用

2. 代码实现

这道经典算法题被力扣收录为基础题目，其中看了官方的六种解法使我陷入了深深的沉思：

我配学算法么？？？

更是看了大佬的回答让我称口赞绝！

3. Java实现斐波那契数列

常见的实现方式是递归，但通过代码测试发现，当数值大于45时，运行速率变的极其慢，所以不可取，以下是测试两种实现方式的时耗：

TimeTool类

TimeTool类用来测试代码块执行所用时间

package xyz.yolin;

import java.text.SimpleDateFormat;
import java.util.Date;

public class TimeTool {
    private static final SimpleDateFormat fmt=new SimpleDateFormat("HH:mm:ss.SSS");

    public interface Task{
        void execute();
    }
    public static void check(String title,Task task){
        if (task==null){
            return;
        }
        title=(title==null)?"":("【"+title+"】");
        System.out.println(title);
        System.out.println("开始:"+fmt.format(new Date()));
        //当前时间与1970年1月1号0时0分0秒所差的毫秒数。
        long begin=System.currentTimeMillis();
        task.execute();
        long end=System.currentTimeMillis();
        System.out.println("结束:"+fmt.format(new Date()));
        double delta=(end-begin)/1000.0 ;
        System.out.println("耗时："+delta+"秒");
        System.out.println("------------------------");
    }
}

Fib类

用了两种方式

package xyz.yolin;

public class fib {
    public static int fib1(int n){
        if (n<=1){
            return n;
        }
        return fib1(n-1)+fib1(n-2);
    }
    public static int fib2(int n){
        if(n==0){
            return 0;
        }
        int sum=1;
        int one=0;
        for (int i=1;i<n;i++){ //循环n-1次
            sum+=one;
            one=sum-one;
        }
        return sum;
    }
    public static void main(String[] args) {
        TimeTool.check("fib1",new TimeTool.Task(){
            @Override
            public void execute() {
                System.out.println(fib1(45));
            }
        });
        TimeTool.check("fib2",new TimeTool.Task(){
            @Override
            public void execute() {
                System.out.println(fib2(45));
            }
        });
    }
}

执行结果

【fib1】
开始:18:50:05.621
1134903170
结束:18:50:10.288
耗时：4.666秒
------------------------
【fib2】
开始:18:50:10.290
1134903170
结束:18:50:10.290
耗时：0.0秒
------------------------

结论

可以看到不同的算法对程序有着深刻的影响，这就要求我们要会评估算法的优劣，从而选择出最合适的算法，使程序运行更高效

评估算法的优劣

• 正确性、可读性、健壮性
• 时间复杂度：估算程序指令的执行次数（执行时间）
• 空间复杂度：估算所需占用的存储空间

二、时间复杂度

1. 常见代码时间复杂度分析

public static void test(int n){
    while((n=n/2)>0){
        System.out.println("test");
    }
}

分析：当n为8时，执行了3次，n为16时，执行4次，则总执行次数为log2n

public static void test(int n){
    for(int i=1;i<n;i=i*2){
        for(int j=0;j<n;j++){
            System.out.println("test");
        }
    }
}

分析：外层循环执行次数：1+2*log2n ,内层为：1+3n ,总执行次数为：1+3*log2n+2*nlog2n

2. 忽略不必要的参数

所以上面的时间复杂度分别为：

• O(logn)
• O(nlogn)

3.时间复杂度比较

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)