Fibonacci Optimization

[junxnone]

Reference

• 斐波那契数列算法优化

Brief

• 问题描述:
  • 条件
    • 第一个月初有一对刚诞生的兔子
    • 第二个月之后，即第三个月初他们可以生育
    • 每月每对可生育的兔子会诞生下一对新兔子
    • 兔子永不死去
  • 问题: 假设在第N月共有兔子a对，第N+1月共有兔子b对，则N+2月该有多少对兔子？

Algos

递归法

• 时间复杂度 O(2^n)

int fib(int n){
  if(n < 2) return n;
  return fib(n-1) + fib(n-2);
}

递推法

• 时间复杂度 O(n)
• 空间复杂度 O(n)

int fib(int n){
  int n_1 = 0, n_2 = 1;
  int tmp;
  for(int i = 2; i < n; i++){
    tmp = n_1;
    n_1 = n_2;
    n_2 += tmp;
  }
}

递推式

• f(2) = f(1) + f(0)
• f(3) = f(2) + f(1) = 2 * f(1) + f(0)
• f(4) = f(3) + f(2) = 3 * f(1) + 2 * f(0)
• ...
• f(n) = f(n-1) + f(n-2) = A * f(1) + B * f(0)

• 问题转化为 M ^ N 的优化