java实现斐波那契数列的3种方法
本文导语: 先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案。去面试的时候,由于面试前天晚上11点钟才到阿里巴巴指定面试城市,找到旅馆住下基本都1点多,加上晚上完全没有睡好,直接导致第二天面试...
先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案。去面试的时候,由于面试前天晚上11点钟才到阿里巴巴指定面试城市,找到旅馆住下基本都1点多,加上晚上完全没有睡好,直接导致第二天面试效果很不好(对于那些正在找工作的大虾们不要向小虾一下悲剧,提前做好准备还是很重要滴),面试大概进行了一个多小时(面试结束回去的时候基本走路都快睡着了,悲催!!),面试快结束的时候面试官问的我问题就是关于费波那西数列,当时头脑完全浆糊,只知道要设置三个变量或者用List先初始化,当写到for循环的时候,脑袋简直浆糊的不能再浆糊了,没写出来,最后只能在面试官的步步诱导下写出了下面的第一种方式,很不应该呀;从现在来看阿里只是把粗枝大叶的把整个应用的框架搭建起来了,真是变革、挖金的黄金期(有能力的大虾赶紧去),毕竟阿里巴巴手中99%的数据都是重要数据而向百度这类的主推搜索的巨头99%数据都是垃圾相比,对于数据分析来说,阿里更能通过对手中掌握的多种多样的用户详细数据进行分析,更能精确定位用户的品味及需求,为精确推送和精准广告推送提供更好的服务。如果说腾讯未来的梦想是做用户生活中的水电气的话,那阿里可能实现的未来梦想就是用户的衣食住行外加代收水电气等等,O(∩_∩)O~还是转入正题吧。
对于优秀的算法设计员来说,在程序功能主体实现的基础上无非关心两个东西,一个设计算法的时间复杂度,一个是空间复杂度(说白了就是执行一个程序所用的时间和占用的内存空间);在根据不同的应用场景的基础上,一般充满智慧的算法设计师会在时间和空间两个相对矛盾的资源中寻求到平衡点,如实时性要求高的系统一般会以空间资源换取时间或者对于常用到的对象一般会常驻内存以提高响应时间(缓存技术和现在比较流行NoSQL中大多是内存数据库都是如此),对于内存资源比较宝贵的嵌入式系统而言一般会以时间上的延迟来换取时间。
下面从费波那西数列三个实现上来说说,怎么才能真正设计出真正符合实际应用场景的优秀算法
首先说说费波那西数列:
从文字上说,费波那西数列由0和1开始,之后的费波那西系数就由之前的两数相加,数列形式如下:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,………………
在数学上,是以递归的方法来定义:
F_0=0
F_1=1
F_n = F_{n-1}+ F_{n-2}
实现需求:输入序号n返回得到对应费波那西数
程序实现1——函数自迭代
/**
* 函数自迭代
* @Title: fnType1
* @Description: TODO
* @param @param n
* @param @return
* @return int
* @throws Exception
*/
public int fnType1(int n)throws Exception{
if(n==0){
return 0;
}else if(n==1||n==2){
return 1;
}else if(n>2){
int temp=fnType1(n-1)+fnType1(n-2);
if(temp