茴香豆的茴字有 4 种写法,那么菲波那切数列的实现方式有几种?
没有标准答案,本文主要介绍 3 种实现方式和比较他们的优劣,以及用简单的方式引入动态规划.
定义为,第一个和第二个数字是 1, 从第 3 个到 n(n 属于正无穷)个数字为前一个数和前前一个数的和.
这是一个时间复杂度为 O(pow(2n)) 的解法,并且会有很深的调用栈,随着 n 的增加,资源消耗成指数上涨.
memoize
注意 memoize 不是 memorize, 前者更像是把上一次计算结果缓存起来.
这样的解法不用重复的调用已经算出的 fib(n),节省了时间复杂度,现在的时间复杂度为 O(n+1)
可是这根动态规划有什么关系呢?关系很大,下一期继续说.