斐波那契数列递归算法的优化

public class Fibonacci {
//优化使用的数组
static long[] cach = new long[51];

public static void main(String[] args) {
   long a = System.currentTimeMillis();
   System.out.println( fd( 50 ) );
   long l = System.currentTimeMillis();
   System.out.println( l - a );
   long l1 = System.currentTimeMillis();
   fd1( 50 );
   long l2 = System.currentTimeMillis();
   System.out.println( l2 - l1 );
}

//未优化的
private static int fd1(int n) {
   if (n == 1 || n == 2) {
      return 1;
   }
   int a = fd1( n - 1 ) + fd1( n - 2 );
   return n;
}

//优化后的
private static long fd(int n) {
   // 结束条件
   if (n == 1 || n == 2) {
      return 1;
   }
   // 检查数组中有没有计算好的结果,如果有,直接返回结果,如果没有进行计算,并存入数组
   // 1.1 如果有,直接返回结果
   if (cach[n] != 0) {
      return cach[n];
   }
   // 1.2 如果没有, 进行计算,并存入数组
   long x = fd( n - 1 ) + fd( n - 2 );
   cach[n] = x;
   
   return x;
   
}
}
//运行结果
12586269025
0//优化后运行时间的毫秒值
35868//未优化运行时间的毫秒值

热门文章

暂无图片
编程学习 ·

PAT 1161 Merging Linked Lists

原题链接:暂无 关键词:链表 Given two singly linked lists L 1 =a 1 →a 2 →…→a n−1 →a n L1=a1→a2→…→an−1→an and L 2 =b 1 →b 2 →…→b m−1 →b m L2=b1→b2→…→bm−1→bm . If n≥2m n≥2m , you are supposed to reverse and merge the shorter one i…
暂无图片
编程学习 ·

学习Java第十六天

Java多态(下) 接口 接口定义了某一批类所要遵守的规范,接口不关心这些类的内部数据,页不关心这些类里方法的实现细节,它只规定这些类里必须提供某些方法 语法: [修饰符] interface 接口名 [ extends 父接口1,父接口2...] {零到多个常量定义...零到多个抽象方法的定义...零…
暂无图片
编程学习 ·

Python之OpenCV的学习(一)

一.安装 打开Pycharm:File -> Settings -> Project:xxxx下的Project Interpreter,如图所示然后,点击右边的加号进行搜索点击左下角Install Package即可 如果搜索不出来,可以看一下是不是pip源的问题 点击Manage Repositories我使用的是豆瓣pip源:http://pypi.douba…
暂无图片
编程学习 ·

nginx 通过域名代理tcp端口

碰到一种场景,使用nginx进行反向代理tcp端口,网上大部门的设置都是一个端口代理一个端口,没有一个端口通过域名代理后端多个端口的情况。 在sf上面看到一个设置教程,记录下 只需要修改nginx.conf,添加如下配置即可, stream {map $ssl_preread_server_name $name {mysql.t…
暂无图片
编程学习 ·

2020.7.1崔庆才教材《Python3网络爬虫开发实战》3.4爬取猫眼电影排行代码更正(绕过美团验证码)

前情提要 首先附上崔大神的github源码:3.4爬取猫眼电影排行 毕竟此段代码完成时间较早,截至2020.7.1日,发现了此段代码中两个需要修改的地方。 希望能给学习崔大神的小白一些帮助,希望大家有个好前途。 一、猫眼电影反爬更新 下图是崔大神的代码:估计是太多人学习爬虫拿猫…
暂无图片
编程学习 ·

Centos7实现MySQL数据库备份与恢复

简介MySQL数据库的备份可以分为逻辑备份和物理备份,逻辑备份工具主要为:mysqldump而物理备份工具主要为:xtrabackup,两种备份方式各有优缺点备份工具mysqldumpxtrabackup优点支持热备份和增量备份,需要磁盘空间小支持热备份和增量备份,业务影响小,停机时间短,缺点业务影…
暂无图片
编程学习 ·

文件-复制-删除-移动

import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.FileWriter; import java.io.InputStream; import java.io.PrintWriter; public class CopyFile { public CopyFile() { } /** * 新建目录 * @param folderPat…
暂无图片
编程学习 ·

理论:深度介绍OSPF路由协议

目录前言1 OSPF路由协议概述1.1 内部网关协议和外部网关协议1.2 OSPF协议1.3 链路状态协议工作原理简介1.4 OSPF的工作过程2 OSPF的基本概念2.1 OSPF区域2.2 区域ID2.3 骨干区域Area 02.4 非骨干区域2.5 Router ID2.6 Router ID选取规则2.7 DR和BDR3 Router-id及DR选举原则4 OS…
暂无图片
编程学习 ·

查找 -- 7.1 Sear for a Range -- 图解

/********************************************************************************************************** 描述 Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be i…
暂无图片
编程学习 ·

linux usb usbip驱动详解(二)

终于来到usbip驱动代码分析了!我们在做产品时,通常是先讨论方案、制定协议、编码和测试。usbip的方案是行得通的,它是从URB对象获取信息,然后从tcp发送出去的,URB是linux usb子系统里面用于抽象usb通信而精心设计的对象,只要server和client两边在恰当的时机分别隔断各自系…
暂无图片
编程学习 ·

Autosar4.4:通用架构模板 - 元建模模式与模型转换(2/3)

元模型化模式是参数化的结构,当将其应用于实际参数时,会产生规则的,非参数化的结构。 结构只是由关联和聚合关联的元类的集合。 模式的好处在于,它们允许重复使用重复结构,而无需重复其定义。 本章介绍元建模模式的概念,以及它们在AUTOSAR元模型中的使用和表示法。 另一个…
暂无图片
编程学习 ·

python_ask_02-Are object and instance the same?

ID = python_ask_02 文章目录QuestionAnswerReference Question Are object and instance the same? Answer Are they the same? My answer is NO. We say everything is object, but we never say everything is instance. Class and instance are both object.「对象」是一…
暂无图片
编程学习 ·

项目实训——初版的页面优化(2)

项目实训——初版的页面优化(2)题目太长的解决就业帮助具体内容的收起展开表格的美化 再次进行了一次小组会议,找到了更加多的需要优化和完善的地方。比如题目很容易出框,讨论区话题的显示需要限制长度等等。同时也新增一些功能,比如评论的删除。这篇先写完善。 题目太长的…
暂无图片
编程学习 ·

百度百科创建好像成功不了,BBdoc文档搜索词条都四个版本了无法成功!

看来想创建成功百度百科几乎是不太可能,不知道啥原因?本来想通过百度百科让更多人了解到BBdoc文档搜索工具,可以早日使用上,但就是无法成功。BBdoc文档搜索官网:http://www.bbdoc.cn/版本1提示错误:版本2提示错误:版本3提示错误:版本4提示错误:不想有版本5了,快崩溃哪…
暂无图片
编程学习 ·

PYQT中QtMultimedia模块使用及处理

PYQT中,使用QtMultimedia模块,播放视频。 本文可以实现的功能是点击播放按钮,可以播放视频;点击暂停按钮,可以停止播放视频;拉动进度条,可以定位视频播放位置。 附上代码: from PyQt5.QtCore import QUrl import PyQt5.QtWidgets from PyQt5.QtMultimedia import * fro…
暂无图片
编程学习 ·

自学python第三天

if 、while、for的使用 1、if条件 1.1、简单if if 条件:条件成⽴立执⾏行行的代码1条件成⽴立执⾏行行的代码2 ......例如 if True:print(条件成⽴立执⾏行行的代码1)print(条件成⽴立执⾏行行的代码2) # 下⽅方的代码没有缩进到if语句句块,所以和if条件⽆无关 print(我是⽆无…
暂无图片
编程学习 ·

node.js学习

node server.js 开启服务 const http = require(http); const fs = require(fs);let server = http.createServer(function(request, response) {let {url} = request;fs.readFile(www/+url,(err,data) => {if (err){response.write(404)}else{response.write(data)}respons…
暂无图片
编程学习 ·

442. 数组中重复的数据 原地哈希

442. 数组中重复的数据 难度:中等 题目描述解题思路 不使用额外空间,而且时间复杂度O(n),那就原地哈希了 思路很清楚,就是把每个数字放到对应的下标处,如果最后不对应,就是重复出现的数字 /** 442. 数组中重复的数据* 2020/7/2*/public static List<Integer> findD…