文档章节

只写完功能代码仅仅只是开始

drv
 drv
发布于 2016/12/28 11:31
字数 1104
阅读 12
收藏 0

  甚至有时候都算不上开始,因为功能有实效要求。

  最近面试总是遇到,理直气壮的认为实现了就行了,于是我整理了下大学数据结构的部分内容。

  主要是关于斐波那契数列的计算方法。斐波那契数列就不介绍了,大概就是这样的:fib(n) = fib(n - 1) + fib(n - 2)。

  用递归可以很容易实现:

  

  然而,这里n只设为了5,如果设置的比较大,会发现递归到40多项时已经无法忍受计算速度了,现在用数据结构里学过的时间复杂度分析:

    复杂度:T(n) = T(n - 1) + T(n - 2) + 1,用T(n - 1) 和 T(n - 2) 的时间算出T的前两项以及O(1)时间相加,因为T(0)和T(1)的时间复杂度都是1,当n > 1时,可使用s(n) = [T(n) + 1]/2求解,对边界条件s(0) = 1,s(1) = 1,碰巧等于斐波那契数列的前两项。其实也并不是碰巧,s(n) = s(n - 1) + s(n - 2)其实就等于fib(n + 1),复杂度大致为O(Φ的n次方),(Φ=二分之(一加根号5)约等于1+黄金分割比例),T(n)约等于2*s(n),时间复杂度也呈斐波那契数列变化,量级O(Φ的n次方)大致为O(2的n次方),数值上Φ的36(6的平方)次方=2的25(5的平方)次方,Φ的43次方=2的30次方=2的10次方的3次方约等于10的9次方,10的9次方是目前主流计算机大概1秒的指令吞吐量,Φ的5次方Φ**5 = 10,Φ**67约等于10**14约执行10**5秒,大概是1天,Φ**92 : 10**19 : 10**10秒 :10**5天 : 3个世纪。也就是说要算出第67项,这个算法需要1天时间,而第92项需要三个世纪。

  那么,为什么这么慢呢。其实可以从上面的代码的输出中看出原因: 

  

  这个递归中存在大量的重复计算,因为子项的计算包含子项的子项,而其他子项可能已经计算过这个步骤了,但是它不得不又算了一次从这个角度来看,最简单的解决办法就是记录所有计算过的子项,先查找,没有的话再计算,这种方式的缺点是用空间复杂度比较高。

  还可以有时间复杂度和空间复杂度都比较低的方法,动态规划,在代码上也就是嵌套改循环:

  

  92项用了不到一毫秒,注意,这里n--,实际上等于计算的是之前的方法的93项。

  虽然现在大家都接受了能用硬件增加的性能不要用程序员解决,但是实际上你即使用天河一号算递归的方法也不会比普通PC算循环的方法快,而且用硬件解决并不是说就不需要注意算法了。

  最后,摘抄了一段关于动态规划的内容,忘了当初从哪记得下来的了,所以没有出处,以上。

  能采用动态规划求解的问题的一般要具有3个性质:

  (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

  (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

  (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势

 

  以上测试代码在:https://github.com/saaavsaaa/warn-report/blob/master/src/test/java/TestObjectInstance.java

  testDyPro和testRecursion方法

  以上内容参考清华大学邓俊辉教授的数据结构视频课程

 

==========================================================

咱最近用的github:https://github.com/saaavsaaa

微信公众号:

转载请注明出处

© 著作权归作者所有

下一篇: clr 元数据
drv

drv

粉丝 2
博文 57
码字总数 75382
作品 0
东城
架构师
私信 提问
源码学习的两个问题:深度不够+直接跟着敲

一天都在照抄别人的代码,边写边理解,通过自己敲能更够好地理解,但问题是这样的效率太低。最重要的是,自己没有思路,全照着作者走,一行一行地敲,一方面没有一个整体上的概念认识,另一方...

飞凡人
2018/06/05
0
0
康/swagger-doc

文档 文档(https://gitee.com/wangkangdaydayup/swagger-doc/wikis/Home) swagger-doc 重点先说说这个项目解决了什么问题 这个总得来说是给swagger解决了大部分人不想用swagger的问题,sprin...

2017/07/16
0
0
UITextField详解之一:UITextField基本属性

UITextField是IOS开发中用户交互中重要的一个控件,常被用来做账号密码框,输入信息框等。创建一个用于输入的UITextField其实很简单,在平时使用中,更多的是需要 UITextField和其他UI控件之...

hi-小疯疯
2016/01/23
126
0
看完这篇文章还不懂Python装饰器?

1、必备 2.需求来了 初创公司有N个业务部门,1个基础平台部门,基础平台负责提供底层的功能,如:数据库操作、redis调用、监控API等功能。业务部门使用基础功能时,只需调用基础平台提供的功...

糖宝lsh
2018/11/14
0
0
还是自己撸一个java的mvc框架吧!

怎么写呢? 因为在之前写代码的时候,我把每个类要做的事情分的比较清楚,所以在添加这个功能的时候写起来还是比较简单的,需要修改的地方也比较小。 这一章里我们需要干的事情有: 定义一个...

小刀爱编程
02/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

思维导图XMind 8 Pro 绿化方法(附序列号)

按部就班: Step 1 -全新下载最新版本的 Xmind 8(注必须是英文官方的版本,中文代{过}{滤}理网站的版本修改过,无法使用pj); Step 2 -安装完毕后,点击文末的下载按钮下载pj补丁文件包,将...

一只小青蛙
49分钟前
6
0
数据结构(ER数据库)设计规范

表命名规范 表命名的规则分为3个层级,层级之间通过_分割,例如b_r_identity、d_l_identity。规约为: [leavel]_[type]_[name] [leavel] 表示数据库表的层级和功能,分为: s:业务无关的系统...

随风溜达的向日葵
今天
5
0
阿里Sentinel控制台源码修改-对接Apollo规则持久化

https://github.com/alibaba/Sentinel/wiki/%E5%9C%A8%E7%94%9F%E4%BA%A7%E7%8E%AF%E5%A2%83%E4%B8%AD%E4%BD%BF%E7%94%A8-Sentinel 动态规则扩展 https://github.com/alibaba/Sentinel/wiki......

jxlgzwh
昨天
4
0
在Linux系统中创建SSH服务器别名

如果你经常通过 SSH 访问许多不同的远程系统,这个技巧将为你节省一些时间。你可以通过 SSH 为频繁访问的系统创建 SSH 别名,这样你就不必记住所有不同的用户名、主机名、SSH 端口号和 IP 地...

老孟的Linux私房菜
昨天
10
0
高德API入门教程

项目需求 1、实现打开地图就能定位到中心显示标注点 2、点击标注显示保利可爱岛的详细信息 3、实现导航功能 <!doctype html><html><head> <meta charset="utf-8"> <meta http-......

我叫小糖主
昨天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部