先写一下最朴素的O(N)算法，为了避免重复计算，这里不使用递归，而是采用循环，代码如下：
1 int fibonacci(int n)
2 {
3 assert(n >= 0);
4 if (n == 0) return 0;
5 if (n == 1) return 1;
6
7 int i = 2, tmp, a = 0, b = 1;
8 for (; i <= n; ++i)
9 {
10 tmp = b;
11 b = a + b;
12 a = tmp;
13 }
14 return b;
15 }
16
这里重点介绍如下两种方法，一种方法是《编程之美》上的，通过利用如下矩阵关系式：
[f(n), f(n-1)] = [f(1), f(0)] * [1, 1]^(n-1)
[1, 0]
这样就转化成了求矩阵[1, 1]的n-1次幂了。
[1, 0]
我们知道求a^n的方法有log(N)级别的，类似的，利用分治的思想同样可以求矩阵的n次幂。
代码如下：
1 typedef struct MATRIX
2 {
3 int a, b, c, d;
4 } MATRIX;
5
6 MATRIX matrix_multiply(MATRIX A, MATRIX B)
7 {
8 MATRIX res;
9 res.a = A.a * B.a + A.b * B.c;
10 res.b = A.a * B.b + A.b * B.d;
11 res.c = A.c * B.a + A.d * B.c;
12 res.d = A.c * B.b + A.d * B.d;
13 return res;
14 }
15
16 MATRIX matrix_power(MATRIX A, int n)
17 {
18 assert(n > 0);
19 MATRIX tmp;
20 if (n == 1) return A;
21 if (n % 2) return matrix_multiply(A, matrix_power(A, n - 1));
22 tmp = matrix_power(A, n / 2);
23 return matrix_multiply(tmp, tmp);
24 }
25
26 int fibonacci(int n)
27 {
28 assert(n >= 0);
29 if (n == 0) return 0;
30 if (n == 1) return 1;
31
32 MATRIX identify = {1, 1, 1, 0};
33 identify = matrix_power(identify, n - 1);
34 return identify.a;
35 }
36
其中matrix_multiply()用于计算两个2*2的矩阵的乘积
matrix_power()用于计算矩阵A的n次幂
算法复杂度全部集中在matrix_power上，因此为log(N)级别
另外一种方法是今天上午灵感突现，想到fibonacci数列递推式的系数同样符合fibonacci规律，如下：
f(n) = f(n - 1) + f(n - 2)
= 2f(n - 2) + f(n - 3)
= 3f(n - 3) + 2f(n - 4)
= 5f(n - 4) + 3f(n - 5)
= f(5)f(n - 4) + f(4)f(n - 5)
= ...
= f(i)f(n - i + 1) + f(i - 1)f(n - i)
有了这个公式我们可以得到如下式子：
f(2n) = f(n + 1)f(n) + f(n)f(n - 1) = f(n + 1)f(n) + f(n)[f(n + 1) - f(n)]
f(2n + 1) = f(n + 1)f(n + 1) + f(n)f(n)
所以可以得到：
f(2n) = [2f(n + 1) - f(n)]f(n)
f(2n + 1) = f(n + 1)f(n + 1) + f(n)f(n)
这样，我们同样找到了f(2x)与f(x)以及f(x+1)之间的关系，同样可以得到log(N)级别的时间复杂度
程序如下：
1 typedef struct MATRIX
2 {
3 int a, b;
4 }MATRIX;
5
6 MATRIX fibo(int n)
7 {
8 assert(n >= 0);
9 MATRIX tmp = {0, 1};
10 if (n == 0) return tmp;
11 if (n == 1)
12 {
13 tmp.a = 1, tmp.b = 1;
14 return tmp;
15 }
16 tmp = fibo(n / 2);
17 int f2n = (2 * tmp.b - tmp.a) * tmp.a;
18 int f2n1= tmp.a * tmp.a + tmp.b * tmp.b;
19 if (n % 2)
20 {
21 tmp.a = f2n1, tmp.b = f2n1 + f2n;
22 return tmp;
23 }
24 else
25 {
26 tmp.a = f2n, tmp.b = f2n1;
27 return tmp;
28 }
29 }
30
31 int fibonacci(int n)
32 {
33 assert(n >= 0);
34 return fibo(n).a;
35 }
36
posted on 2012-02-09 15:20
myjfm 阅读(563)
评论(0) 编辑 收藏 引用 所属分类:
算法基础