A coding kata -- Fibonacci sequence

2021年01月14日 阅读数:4
这篇文章主要向大家介绍A coding kata -- Fibonacci sequence,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

斐波拉契数列(Fibonacci sequence),想必读者都已经很是熟悉了,指的是一个这样的数列:
0112358132134……
这个数列从第3项开始,每一项都等于前两项之和。python

伊始

如何用计算机解决这个问题,最简单的办法好像就是递归实现了,不知道读者是否考虑过下面几个小问题?算法

  • 递归的方法能够求出全部的解吗,当n=80800甚至8000或者更大值的时候能够求解吗
  • 效率怎么样
  • 你有什么方法提升效率吗
  • 你是否利用了某些编程语言的特性
  • 你能想出几种不一样的解法
  • 等等

本文主要用python来带你们看看不一样的解决方案,在某些方案中我也贴出用C++的解决方案,第一个就从递归的方法来看吧编程

递归实现

def fib(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return fib(n-1) + fib(n-2)

求解上面的递归式:
$$T(n) = T(n - 1) + T(n - 2) + 1 ≈ 2^n = O(2^n)$$
上面的实现十分低效,递归的过程当中执行了太多重复的动做,时间复杂度是指数级别,并且受递归深度的限制,求解的范围十分有限。缓存

递归优化

def fib(n):
    def fib_iter(n, x, y):
        if n == 0:
            return x
        else:
            return fib_iter(n - 1, y, x + y)
    return fib_iter(n, 0, 1)

上面是尾递归优化的写法,虽然减小了不少没必要要的计算,但仍是受到递归深度的限制,下面咱们看几个更好的解决方案app

动态规划

  • 自底向上
def fib(n):
    memo = [0, 1]
    for i in range(2, n+1):
        memo.append(memo[i - 1] + memo[i - 2])
    return memo[n]
  • 自顶向下
memo = {0: 0, 1: 1}
def fib(n):
    if n in memo:
        return memo[n]

    if n == 0: return 0
    elif n == 1: return 1
    memo[n]  = fib(n - 1) + fib(n - 2)
    return memo[n]

上面两种解决方案都将问题的复杂度降到了O(n)级别,缺陷是空间复杂度也是O(n)编程语言

  • 改进方案,高效缓存

经过递归式能够知道,当前值只和前两次的值相关,因此咱们只须要保留最后两个数值便可优化

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

时间复杂度为O(n),空间复杂度降到了O(1),一样的咱们给出C++版本的实现spa

namespace {
struct fib_cache {
  fib_cache() : previous_{0}, last_{1}, size_{2} {}

  size_t size() const { return size_; }

  unsigned int operator[](unsigned int n) const {
    return n == size_ - 1 ? last_ :
           n == size_ - 2 ? previous_ :
           throw std::out_of_range("The value is no longer in the cache");
  }

  void push_back(unsigned int value) {
    size_++;
    previous_ = last_;
    last_ = value;
  }

private:
  unsigned int previous_;
  unsigned int last_;
  size_t size_;
};

} // namespace

unsigned int fib(unsigned int n) {
  fib_cache cache;
  if (cache.size() > n) {
    return cache[n];
  } else {
    const auto result = fib(n - 1) + fib(n - 2);
    cache.push_back(result);
    return result;
  }
}

上面的程序受到无符号整型最大值的约束,计算的范围有限,读者可使用C+11引入的大整形long long来解决,也能够本身实现大整数的存储计算。
上面的算法最快是O(n)级别的,下面咱们看一种O(logn)级别的算法code

矩阵算法

下面咱们先看一个fibnacci数列的矩阵关系推导递归

$$ \left[ \begin{matrix} F_n\\ F_{n-1}\\ \end{matrix} \right] = \left[ \begin{matrix} F_{n-1} + F_{n-2}\\ F_{n-1}\\ \end{matrix} \right] =\left[ \begin{matrix} 1 & 1 \\ 1 & 0\\ \end{matrix} \right] * \left[ \begin{matrix} F_{n-1} \\ F_{n-2}\\ \end{matrix} \right] $$

由上面的推导式,咱们能够轻易获得下面的结果

$$ \left[ \begin{matrix} F_n\\ F_{n-1}\\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ 1 & 0\\ \end{matrix} \right]^{n-1} * \left[ \begin{matrix} F_{1} \\ F_{0}\\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right]^{n-1} * \left[ \begin{matrix} 1\\ 0\\ \end{matrix} \right] $$

上面的公式变成了求矩阵的幂,而矩阵的幂能够用二分算法快速求幂(本质上属于分治法的思想)

$$ x^n= \begin{cases} x^{n/2} * x^{n/2}, &even\\ x^{(n-1)/2} * x^{(n-1)/2} * x, &odd \end{cases} $$

求解上面的递归式:
$$T(n) = T(n/2) + 1 = O(log n)$$
这里就不给出具体实现了,读者能够自行尝试,也可使用python的第三方numpy库去计算矩阵幂。

End

其实Fibonacci问题的解法还有不少高效的解法,等待着你的探索
此时的终点也只是下个旅途的起点……

上一篇: FP范式之旅