斐波那契数列是一个很有意思的数列,应用领域非常广.
定义:
F(n+1)=F(n)+F(n-1)
有意思的是,F(n)/F(n+1)趋于黄金分割0.618.
如何计算斐波那契数呢?
朴素的思想,利用定义.
算法1代码如下:
|
1
2
3
4
5
6
7
8
|
static int Fibonacci1(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}
|
分析下算法复杂度:
T(n+1)=T(n)+T(n-1)=2*T(n-1)+T(n-2)=…=F(n)+F(n-1)=F(n+1)
由于直接递归调用,结果中的每一个1都来自底层的F(1)和F(2),
那么为了求第n个数,就要调用F(n)次函数.
由于斐波那契数列是指数增长,所以该算法的时间复杂度也是指数增长,即O(2^n).
仔细想下,从头开始往后算,也不过是线性复杂度,比算法1好太多了.
于是得到算法2:
|
1
2
3
4
5
6
7
8
9
10
11
|
static int Fibonacci2(int n)
{
int[] a = new int[n];
a[0] = 1;
a[1] = 1;
for (int i = 2; i < n; i++)
{
a[i] = a[i - 1] + a[i - 2];
}
return a[n - 1];
}
|
时间复杂度就是O(n).
求斐波那契数列的算法还能再快一些吗?
答案是肯定的.
算法3:
借助下图所示的结论:
我们求一个矩阵的n次方即可.
两个2维矩阵的乘法次数可以看作常量.
矩阵额n次方利用分治法,只需要O(lg n)的复杂度就能计算出来.
所以该算法的复杂度是O(lg n),比算法2又快了很多,特别是数字非常大的时候.
比如n从1亿变成4亿,算法2需要的时间要变成原来的四倍,但是算法3仅仅增加了个常数2(lg 4=2).
算法代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
static int Fibonacci3(int n)
{
int[,] a = new int[2, 2] { { 1, 1 }, { 1, 0 } };
int[,] b = MatirxClub(a, n);
return b[1, 0];
}
static int[,] MatirxClub(int[,] a, int n)
{
if (n == 1) { return a; }
else if (n == 2) { return Matirx(a, a); }
else if (n % 2 == 0)
{
int[,] temp = MatirxClub(a, n / 2);
return Matirx(temp, temp);
}
else
{
int[,] temp = MatirxClub(a, n / 2);
return Matirx(Matirx(temp, temp), a);
}
}
static int[,] Matirx(int[,] a, int[,] b)
{
int[,] c = new int[2, 2];
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
c[i, j] += a[i, k] * b[k, j];
}
}
}
return c;
}
|
随手写了个测试程序对比它们的效率.
算法1计算n=42和算法2计算n=400 000 000所需的时间差不多.
由此可见,指数时间复杂度的算法太可怕…
但是算法3对于n=400 000 000也几乎一瞬间就算完了.
本站文章版权归原作者及原出处所有 。内容为作者个人观点， 并不代表本站赞同其观点和对其真实性负责，本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台，网站上部分文章为转载，并不用于任何商业目的，我们已经尽可能的对作者和来源进行了通告，但是能力有限或疏忽，造成漏登，请及时联系我们，我们将根据著作权人的要求，立即更正或者删除有关内容。本站拥有对此声明的最终解释权。
