Version: Next

斐波那契数列

求第n个斐波那契数(Fubonacci Number)

某个数等于前两个数的和

n = n-1 + n-2

  • 0 1 1 2 3 5 8 13 ...

递归法

定义一个斐波那契函数，直接递归调用

递归法
/**
* 递归
*
* @param n 第几个斐波那契数
* @return 斐波那契值
*/
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(fib(i));
}
}

逐个相加法

第n个数，需要前面的数一共加n-1次，定义第一个数和第二个数，直接按规律加

  • 定义first和second
  • first和second相加，结果等于下一个second
  • 第一个second等于下一次的first
public static int fib2(int n) {
if (n <= 1) return n;
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int nextSecond = first + second;
first = second;
second = nextSecond;
}
return second;
}

计时工具类

public class MyTimeUtil {
private static final SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss.SSS");
public interface Task {
void execute();
}
public static void getTimeUsed(String title, Task task) {
if (task == null) return;
title = StringUtils.isEmpty(title) ? "" : ("[" + title + "]");
System.out.println(title);
System.out.println("开始时间" + format.format(new Date()));
long beginTime = System.currentTimeMillis();
task.execute();
long endTime = System.currentTimeMillis();
System.out.println("结束时间" + format.format(new Date()));
double timeUsed = (endTime - beginTime) / 1000.0;
System.out.println("耗时：" + timeUsed + “秒”);
}
}

对比耗时

public static void main(String[] args) {
int n = 45;
MyTimeUtil.getTimeUsed("递归法", () -> System.out.println(fib(n)));
System.out.println("-------------------");
MyTimeUtil.getTimeUsed("逐个相加法", () -> System.out.println(fib2(n)));
}
[递归法]
开始时间18:48:15.189
1134903170
结束时间18:48:19.260
耗时：4.071秒
-------------------
[逐个相加法]
开始时间18:48:19.263
1134903170
结束时间18:48:19.263
耗时：0.0秒

时间复杂度

递归法

O(2^n)

fib(5) -> fib(4) fib(3) -> fib(2) fib(3) + fib(2) fib(1) ...

共调用2的N次方次

逐个相加法

O(n)

线性遍历