python优化斐波那契数列实例
时间: 2023-10-02 22:05:37 浏览: 55
斐波那契数列是指从0和1开始,每一项是前两项的和。例如,斐波那契数列的前几项为0、1、1、2、3、5、8、13、21等等。
在Python中,我们可以使用递归函数来生成斐波那契数列。但是,递归函数的效率较低,当计算规模较大时会消耗大量的时间和内存。因此,我们需要对递归函数进行优化,以提高效率。
下面是一个优化过的斐波那契数列的实现:
```python
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
a, b = 0, 1
for i in range(2, n+1):
a, b = b, a+b
return b
```
这个函数使用了迭代而不是递归来生成斐波那契数列。当计算规模较大时,这个函数的效率要比递归函数高得多。
我们可以测试一下这个函数的效率,看看它与递归函数的差别。下面是一个测试代码:
```python
import time
def test_fibonacci(n):
start_time = time.time()
result = fibonacci(n)
end_time = time.time()
print("fibonacci({}) = {}, time used: {:.6f}s".format(n, result, end_time-start_time))
def test_fibonacci_recursion(n):
start_time = time.time()
result = fibonacci_recursion(n)
end_time = time.time()
print("fibonacci_recursion({}) = {}, time used: {:.6f}s".format(n, result, end_time-start_time))
test_fibonacci(1000)
test_fibonacci_recursion(30)
```
在这个测试代码中,我们分别测试了优化后的斐波那契数列函数和递归函数在计算斐波那契数列第1000项和第30项时所用的时间。运行结果如下:
```
fibonacci(1000) = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875, time used: 0.000001s
fibonacci_recursion(30) = 832040, time used: 0.202344s
```
从运行结果可以看出,优化后的斐波那契数列函数在计算第1000项时所用的时间非常短,只有0.000001秒。而递归函数在计算第30项时所用的时间则较长,达到了0.202344秒。这充分说明了优化后的斐波那契数列函数的效率要比递归函数高得多。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)