如何使用Python实现斐波那契数列
作者:FOOFISH-PYTHON之禅 发布时间:2021-12-09 08:20:30
斐波那契数列(Fibonacci)最早由印度数学家Gopala提出,而第一个真正研究斐波那契数列的是意大利数学家 Leonardo Fibonacci,斐波那契数列的定义很简单,用数学函数可表示为:
数列从0和1开始,之后的数由前两个数相加而得出,例如斐波那契数列的前10个数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34。
用 Python 实现斐波那契数列常见的写法有三种,各算法的执行效率也有很大差别,在面试中也会偶尔会被问到,通常面试的时候不是让你简单的用递归写写就完了,还会问你时间复杂度怎样,空间复杂度怎样,有没有可改进的地方。
递归法
所谓递归就是指函数的定义中使用了函数自身的方法
def fib_recur(n):
assert n >= 0
if n in (0, 1):
return n
return fib_recur(n - 1) + fib_recur(n - 2)
for i in range(20):
print(fib_recur(i), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
递归是一种代码最简洁的方法,但它是效率非常低,因为会出现大量的重复计算,时间复杂度是:O(1.618 ^ n),1.618是黄金分割。同时受限于 Python 中递归的最大深度是 1000,所以用递归来求解并不是一种可取的办法。
递推法
递推法就是从0和1开始,前两项相加逐个求出第3、第4个数,直到求出第n个数的值
def fib_loop(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
for i in range(20):
print(fib_loop(i), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
这种算法的时间复杂是O(n),呈线性增长,如果数据量巨大,速度越到后面会越慢。
上面两种方式都是使用分而治之的思想,就是把一个大的问题化小,然后利用小问题的求解得到目标问题的答案。
矩阵法
《线性代数》是大学计算机专业低年级的课程,这门课教的就是矩阵,那时候觉得这东西学起来很枯燥,没什么用处,工作后你才发现搞机器学习、数据分析、数据建模时大有用处,书到用时方恨少。其实矩阵的本质就是线性方程式。
斐波那契数列中两个相邻的项分别为:F(n) 和 F(n - 1),如果把这两个数当作一个2行1列的矩阵可表示为:
因为 F(n) = F(n-1)+F(n-2),所以就有:
通过反推,其实它是两个矩阵的乘积得来的
依此类推:
最后可推出:
因此想要求出F(n)的值,只要能求出右边矩阵的n-1次方的值,最后求得两矩阵乘积,取新矩阵的第一行的第一列的值即可,比如n=3时,
可以得知F(3)的值2,F(2)的值为1,因为幂运算可以使用二分加速,所以矩阵法的时间复杂度为 O(log n)
我们可以用科学计算包 numpy 来实现矩阵法:
import numpy
def fib_matr(n):
return (numpy.matrix([[1, 1], [1, 0]]) ** (n - 1) * numpy.matrix([[1], [0]]))[0, 0]
for i in range(20):
print(int(fib_matr(i)), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
3中不同的算法效率对比:
从上面图可以看出递归法效率惊人的低,矩阵法在数据量比较大的时候才突显出它的优势,递推法随着数据的变大,所花的时间也越来越大。
来源:https://foofish.net/daily-question4.html
猜你喜欢
- python图像爬虫包 最近在做一些图像分类的任务时,为了扩充我们的数据集,需要在搜索引擎下爬取额外的图片来扩充我们的训练集。搞人工智能真的
- 利用这个小游戏可以学习一下ython3.3中tkinter的使用方法# -*- coding: utf-8 -*-import tkinte
- PHP PDO预定义常量以下常量由本扩展模块定义,因此只有在本扩展的模块被编译到PHP中,或者在运行时被动态加载后才有效。注意:PDO使用类
- 本文实例讲述了php生成shtml类及其用法。分享给大家供大家参考。具体如下:<?php class Shtml{ &nb
- 需求 Oracle调用第三方外部程序。Oracle使用sqluldr2快速导出大批量数据,然后用winrar压缩后发送邮件。源码 java
- 准备篇:CentOS 6.6系统安装配置图解教程https://www.jb51.net/os/239738.html一、配置防火墙,开启8
- 目前可实现:MD5算法、SHA256算法、先MD5后SHA256、先SHA256后MD5、两次MD5、两次SHA256、前8位MD5算法后8
- 本文实例讲述了Python单链表原理与实现方法。分享给大家供大家参考,具体如下:Python实现单链表关于链表链表(Linked List)
- import threadingfrom time import sleepdef test_func(id): &n
- 一 导言设计一个好的用户系统往往不是那么容易,Django提供的用户系统可以快速实现基本的功能,并可以在此基础上继续扩展以满足我们的需求。先
- Pycharm是当前进行python开发,尤其是Django开发最好的IDE。GitHub是程序员的圣地,几乎人人都在用。本文假设你对pyc
- 本文介绍TSV文件类型及其应用,同时介绍Golang语句读取TSV文件并转为struct的实现过程。认识TSV文件也许你之前不了解TSV文件
- Symfony2是一个基于PHP语言的Web开发框架,有着开发速度快、性能高等特点。本文以一个程序示例的实现过程详细叙述了Symfony2框
- <script language="JScript" Runat="Server&q
- 开发环境:win10-64 python2.7.16 chrome77from selenium import we
- 在Windows中安装MySQL时,有3种MySQL 5.1安装软件包可供选择:· 基本安装:该安装软件包的文件名类似
- 本文介绍了python中的计时器timeit的使用方法,分享给大家,具体如下:timeit通常在一段程序的前后都用上time.time(),
- 客户端: <%@ Page Language="C#" AutoEventWireup="true&qu
- CSS的出现使网页制作者在对网页元素的控制方便许多,当然,有利必有弊,CSS只能对颜色、大小、距离等静
- 1. 功能说明,在页面使用smarty循环100次输出,类似for循环100次{section name=total loop=100}{$