斐波那契函数的优化

Android开发者使用java开发,但是Android平台并没有使用java虚拟机来执行代码,而是把代码编译成Android使用的虚拟机的字节码(Dalvik 虚拟机).java代码先是被编译成了java的字节码,然后会被odex 编译器编译成delvik虚拟机执行的字节码.无论是Android中还是java中程序的性能优化都是必不可少的一大难题.我们先从简单的斐波那契数列来简做分析:

1.什么是斐波那契数列?

a)?例如 0 ?1 ?2 ?3 ?5 ?8 ?13 ..... 这样的数列.第一个数为1 ?第二个数为1 ?后边的数是前两个数的和

b)?F0 = 1 ?

F1 = 1

Fn?= Fn-1+Fn-2

2.我们先按照简单的思路实现一下这个数列,求出第n个数的值

a)?

这是计算第10个数,感觉很快就打印出来了.咱们来计算一下第100个数试试

发现等了好长时间都没有打印出来结果.我们来分析一下为什么没有打印出结果:

1.方法是如何被调用的?

a)?方法是放在栈内存中执行的

b)?执行完最后一行代码后出栈操作

2.这个fib函数有没有出栈?

a)?咱们要求出的是第100个数的值

i.?首先 fib(100) = fib(99)+fib(98)=fib(98)+fib(97)+fib(98)........

ii.?发现从头开始我们的方法就一直开始做入栈操作而没有做出栈操作

3.这个方法能不能优化?

a)?能

4.怎么优化递归函数

a)?先做第一步优化:消除一个方法调用,减少入栈次数

注意一点:这现在还不是一个尾递归调用,只是减少了一个方法的入栈操作

b) 第二步:将递归改为迭代实现(由于斐波那契就是前两个数的和,所以一个循环就能搞定 看下刚刚我们第100个数的值都算不出来,现在400位的一下就出来了)

计算fib(40)花了大概1ms.计算fib(400)也就几毫秒的时间.无论是面试中还是实际工作中,最主要的还是避免在递归方法中方法长度改变.简单的可以理解为在递归的返回表达式中,最多时自己调自己,不要增加返回表达式的长度.很多人在使用递归函数的时候就之间写了,不考虑是否会出现耗时操作.性能优化路远且坚.