有一个大家都很熟悉的经典数学问题，即斐波那契数列算法问题。这个经典案例在算法中又会变成什么样子呢？
int fib(int n){
if(n == 0)
return 0;
if(n == 1)
return 1;
return fib(n - 1)+fib(n - 2);
}
首先，我们很容易使用递归算法来设计该算法。但是计算出结果是一个指数阶的算法，当n到100的时候，每多算一个斐波那契数需要至少多算一年。
那我们今天就主要介绍一下优化后的算法。
算法优化1:每次记录前两项的值，只需要一次加法运算得到当前项，算法时间复杂度降低到了O（n），效率大幅度提高。
算法改进2:使用迭代法，两数辗转相加，每次记录前一项，时间复杂度为O（n），空间复杂度降低到了O（1）。代码如下：
int fib(int n){
int i , s1 = 1 , s2 = 1;
if(n < 1)
return -1;
if(n == 1 || n == 2)
return 1;
for(i = 3;i <= n; i++){
s1 = s1 + s2;
s1 = s2 - s1;
}
return s2;
}
算法改进3:接下来我们来看看对数阶的斐波那契数列算法。先来看下面这种算法：
int fib(int n){
return fib_iter(1,0,n);
}
int fib_iter(a,b,count){
if(count == 0)
return b;
return fib_iter(a+b , a, count - 1);
}
在这种算法中，我们每次递归都将a+b的值赋给a，把a的值赋给b，通过观察可以发现，从1和0开始将规则反复应用n次，将产生一对数fib(n)和fib(n+1),现在将这种规则看成a = bq + aq + a*pb = bp + aq其中p=0,q=1把这种变换称为T变换，
Tpq 变换有个特性是 Tpq 的二次方等于Tp‘q’， p‘ = pp + qq , q' = 2pq + q*q
即：a = (bp+aq)p+(bq+aq+ap)q+(bq+aq+ap)p = b(2pq+q^2)+a(p^2+2pq+2q^2)
b = (bp+aq)p+(bq+aq+ap)q = b(p^2+q^2)+a(q^2+2pq)
此处p=0，q=1
int fib(int n){
return fib_iter(1,0,0,1,n);
}
int fib_iter(int a,int b,int p,int q,int count){
if (count == 0)
return b;
else if (count%2)
return fib_iter(b*p+a*q+a*p,b*p+a*q,p,q,count-1);
else
return fib_iter(a,b,p*p+q*q,q*q+2*p*q,count/2);
}
这样的算法时间复杂度可以达到对数阶。大幅地提高了算法的效率。
网友评论