斐波那契數列是一個很有意思的數列,應用領域非常廣.
定義:
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也幾乎一瞬間就算完了.
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
