写一下斐波那契算法
时间: 2023-07-10 18:12:11 浏览: 92
斐波那契算法是一种常见的递归算法,用于计算斐波那契数列的第n项。斐波那契数列是指:1、1、2、3、5、8、13、21、34……其中每一项都是前两项之和。
斐波那契算法的实现如下:
```python
def fibonacci(n):
if n == 1 or n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
```
这个算法的思路是:当n等于1或2时,斐波那契数列的第n项为1;否则,第n项为前两项之和。因此,可以使用递归的方式实现这个算法。
但是,这个算法的时间复杂度比较高,因为它会重复计算一些子问题。为了优化算法,可以使用记忆化搜索,将已经计算过的子问题的结果保存下来,避免重复计算。优化后的斐波那契算法的实现如下:
```python
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n == 1 or n == 2:
result = 1
else:
result = fibonacci(n-1, memo) + fibonacci(n-2, memo)
memo[n] = result
return result
```
这个算法使用了一个字典memo来保存已经计算过的子问题的结果。如果字典中已经存在了第n项的结果,就直接返回;否则,计算第n项并保存到字典中。使用记忆化搜索后,算法的时间复杂度变为O(n),效率得到了明显的提高。