【设计之美】02 兔子数列

一、递归求解阶乘

1、时间复杂度O(n) 空间复杂度O(n)

2、递推 回归

3、T(n) = T(n-1) + 1

4、复杂度： 直接能看出、假设运行m次 求m 、分析的结果

二、魔鬼序列

1、棋盘的麦子

棋盘上的麦子，第一个格子里放一粒麦子,在第二个格子里放两粒,在第三个格子里放四粒,在第四个格子里放8粒,以此类推,每一个格子都是前一格子的两倍。放慢64个格子需要多少？

1) S = 1 + 2^1 + 2^2 + 2^3 + ....+ 3^63 2) 2S = 2^ + ...+ 2^64 两式相减 S = 2^64-1

三、常见的算法复杂度有以下几类

1、常数阶 O(1)

2、多项式阶 O(n^m)

3、对数阶O(logn) 、O(nlogn)

4、指数阶 O(2^n) O(n!) O(n^n)

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

四、兔子数列（ 斐波那契数列）

1、假设第一个月有一对刚诞生的兔子,第二个月进入成熟期,第三个月开始生育兔子,而1对成熟的兔子每个月会生1对兔子,兔子永不死去…那么,由一对初生兔子开始,n个月后会有多少对兔子呢？

当月兔子数 = 上月兔子数 + 上上月兔子数 F(n) = F(n-1) + F(n-2) n>2 F(1) = 1, F(2) =1

2、递归求解 与 优化

package com.haoxiansheng.algorithm100day; import java.time.Instant; /** * @author flame * @data 2020/10/4 */ public class FibTest { public static void main(String[] args) { System.out.println(Instant.now()); // System.out.println(fib1(20)); System.out.println(Instant.now()); System.out.println(fib2(50)); System.out.println(Instant.now()); } /** * 斐波那契数列 * * @param n * @return */ public static long fib1(int n) { if (n < 1) { return -1; } else if (n == 1 || n == 2) { return 1; } else { return fib1(n - 1) + fib1(n - 2); } } /** * 斐波那契数列的优化 * @param n * @return */ public static long fib2(int n) { if (n < 1) { return -1; } else { long[] a = new long[n +1]; a[1] = 1; a[2] = 1; for (int i = 3; i <= n; i++) { a[i] = a[i - 1] + a[i - 2]; } return a[n]; } } }