September 16, 2006

一个线形复杂度的菲波那契函数

所谓菲波那契数列,就是这个东西:1,1,2,3,5,8...题目为,写一个函数fib(int n)给出数列中某个数的下标,返回这个数。
菲波那契函数的数学定义为fib(x),x=1 ? fib(x)=1 : fib(x)=fib(x-1)+fib(x-2)。
只用这个就可以给出解答:
unsigned long fib (int x) {
if (x > 2) {
return fib(x - 1) + fib(x - 2);
} else {
return 1;
}
}
测试函数如下:
int main () {
int arg;
printf("Input the length:");
scanf("%d", &arg);
printf("fibonacci(%d)=%lu\n", arg, fib(arg));
return 0;
}
但是,学过算法的人都知道,这个算法的时间复杂度是O(n2)级的,慢的要命。教科书上给出了循环方法的解答。(注:这个解答有一个超变态的一句话版本,知道的人请跟贴)
事实上,确实可以给出线形复杂度的菲波那契函数,原理来源于数列本身的性质。我大概写了一下,程序本身不好看,但肯定不会更快了:
#include
int i = 3;
unsigned long fib (int x, int y, int n) {
if (i <= n) { i++; return fib(y, x + y, n); } else { return y; } } int main () { int arg; printf("Input the length:"); scanf("%d", &arg); printf("fibonacci(%d)=%lu\n", arg, fib(1, 1, arg)); return 0; } 觉得怎么样?是不是很直白?


附:菲波那契数列有通项公式...
#python代码
import math
q = math.sqrt
def fib ( n ) :#看清楚了,这可是O( 1 )级的哦~~
return ((1 + q(5) / 2) ** n / q(5) - ((1 - 1(5)) / 2) ** n / q(5)

No comments: