斐波那契数列的三种写法（递归，循环，改进后的递归）

2024-03-15 13:47| 来源: 网络整理| 查看: 265

斐波那契数列的三种写法（递归，循环，改进后的递归）斐波那契数列实现1. 普通递归2.循环3.改进后的递归总结

斐波那契数列

我们将F(n) = 1，1，2，3，5，8，13…(F(n-1)+F(n-2))这样的数列称为斐波那契数列

实现 1. 普通递归 int f1(int n) { if(n t = first+second; first = second; second = t; } return t; }

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

3.改进后的递归

算法是博大精深的，我们不仅要会写代码更要写好代码，接下来我们对普通递归进行优化，我们仔细观察就会发现递归和循环之间是有某种联系的，递归有些像逆循环，掌握这个思想后我们来实现改进后的递归函数。

int f3(int first, int second, int n) { if(n == 1 || n == 2) return 1; else if (n == 3) return first + second; else return f3(second, first + second, n - 1); }

代码中实现递归调用的时候和上面循环方法的赋值是相同的，例如第一次递归调用的时候将second赋值给first，first+second赋值给second。该方法时间复杂度O(n)，空间复杂度O(1)

总结

我们发现递归的代码量很少，但是普通递归的时间复杂度很大，在我们进行优化后，便可以得到代码量又少，算法复杂度交低的代码了。根据效率从高到低的时间复杂度排序为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、 k次方阶O(n^k)、指数阶O(2^n)。

【本文地址】

公司简介

联系我们