先寫一下最樸素的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 閱讀(594)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎