#课堂笔记# 斐波那契数列的算法优化问题

问题

斐波那契数列最基本的算法是使用递归法 (Recursion)来求解第 n 项。

基本代码:

def foo1(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return foo1(n-1) + foo1(n-2)

由于这个算法的时间复杂度很高,达到了 O(n^2)。于是需要一个时间复杂度更小一点的算法。

Solution 1 使用迭代递推

这是目前最主流的想法,就是从 n = 1 开始往后推,一直推到自己想要的一项为止,只需要一个最简单的 For 循环就可以实现。

def foo2(n):
    l = [0,1]
    for i in range(2,n+1):
        l.append(l[i-1]+l[i-2])

    return l[n]

Solution 2 使用数组来储存中间结果

其实这一个思路也是差不多的,主要是 @NeverBehave 的老师说,只能 改进 递归的思想,不可以换成迭代。

于是我就想到了,在递归中会遇到很多重复次数计算 n-3 , n-4, n-5 …. n = 1 的情况,在这过程中会创建大量的函数帧,导致运行效率过低,如果我们能保证对于每一次函数帧的n值只计算一遍,那么就可以避免很多不必要的计算。于是就有了下面这个改进的方法

#include 

using namespace std;

int cache[200];

int foo3(int n)
{
	//Base Step
	if(n < 2)
	{
		return 1;
	}
	if(cache[n]!=0)
	{
		//如果当前 n 值已经计算过,直接 return,不需要再进行下一步递归
		return cache[n];
	}
	//如果当前 n 值没有计算过,进行递归操作。
	cache[n] = foo3(n-1) + foo3(n-2);
	return cache[n];
}

int main(int argc, char *argv[]) {
	// 初始化cache数组,填充0
	for (int i = 0;i<200;i++) {
		cache[i] = 0;
	}
	
	std::cout << "n = 40, fib = " << foo3(40) << std::endl;
	return EXIT_SUCCESS;
}
  1. VPS234说道:

    这个是大学必须的算法 :razz:

  2. nice说道:

    一个字 : 高级

  3. 初夏阳光说道:

    开始学C语言之后感觉看这些容易理解多了。算法的时间复杂度我还是没接触。
    (大佬加油嗷~虽然不知道你什么时候会看到这个评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注