C語(yǔ)言中斐波那契數(shù)列的三種實(shí)現(xiàn)方式(遞歸、循環(huán)、矩陣)
《劍指offer》里講到了一種斐波那契數(shù)列的 O(logN) 時(shí)間復(fù)雜度的實(shí)現(xiàn),覺(jué)得挺有意思的,三種方法都記錄一下。
一、遞歸
一般來(lái)說(shuō)遞歸實(shí)現(xiàn)的代碼都要比循環(huán)要簡(jiǎn)潔,但是效率不高,比如遞歸計(jì)算斐波那契數(shù)列第n個(gè)元素。
long long Fibonacci_Solution1(unsigned int n) { // printf("%d ", n); if (n <= 0) return 0; if (n == 1) return 1; return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2); }
如果計(jì)算數(shù)列的第4個(gè)位置上(從0開(kāi)始)的數(shù)(0 1 1 2 3),也就是3,上邊的 printf 輸出應(yīng)該是 4 3 2 1 0 1 2 1 0,這是因?yàn)橛?jì)算 F(4) 要計(jì)算 F(3) 和 F(2),而計(jì)算 F(3) 的時(shí)候又要計(jì)算 F(2) 和 F(1),所以會(huì)有很多重復(fù)計(jì)算。用下圖可以更好地說(shuō)明。
遞歸雖然有簡(jiǎn)潔的優(yōu)點(diǎn),但它同時(shí)也有顯著地缺點(diǎn)。遞歸由于是函數(shù)調(diào)用自身,而函數(shù)調(diào)用是有空間和時(shí)間的消耗的:每一次函數(shù)調(diào)用,都需要在內(nèi)存棧中分配空間以保存參數(shù)、返回地址及臨時(shí)變量,而且往棧里壓入數(shù)據(jù)和彈出數(shù)據(jù)都需要時(shí)間。
而且除了效率問(wèn)題之外,遞歸可能引起 調(diào)用棧溢出,因?yàn)樾枰獮槊恳淮魏瘮?shù)調(diào)用在內(nèi)存棧中分配空間,而每個(gè)進(jìn)程的棧的容量是有限的。當(dāng)?shù)俟痰膶蛹?jí)太多,就會(huì)超出棧的容量,導(dǎo)致棧溢出。比如上邊的代碼,輸入40,可以正確返回 12502500,但是輸入 5000 就會(huì)出錯(cuò)。
二、循環(huán)
最常規(guī)的正確做法就是用循環(huán)從小到大計(jì)算。
long long Fibonacci_Solution2(unsigned n) { if (n <= 1) return n; long long fib1 = 1, fib0 = 0, fibN = 0; for (unsigned int i = 2; i <= n; ++i) { fibN = fib1 + fib0; fib0 = fib1; fib1 = fibN; } return fibN; }
或者下邊這種
long long Fibonacci_Solution2(unsigned n) { if (n <= 1) return n; long long a = 0, b = 1; for (unsigned int i = 2; i <= n; ++i) { b = a + b; a = b - a; } return b; }
三、矩陣
數(shù)中提到了一種 O(logN) 時(shí)間復(fù)雜度的算法,就是利用數(shù)學(xué)公式計(jì)算。
首先需要知道下邊這個(gè)數(shù)學(xué)公式:
這個(gè)公式用數(shù)學(xué)歸納法可以證明,所以只需要計(jì)算右邊矩陣的 n-1 次方就能得到 f(n),現(xiàn)在問(wèn)題就變成了計(jì)算 2x2 矩陣的 n-1 次方,這樣做 n-2 次乘法就可以了,時(shí)間復(fù)雜度還是 O(N),但是還可以加速,如下式:
所以我們可以看出,想求 n 次方可以求出 n / 2 次方再平方,所以時(shí)間復(fù)雜度可以將為 O(logN)。
struct Matrix2By2 { Matrix2By2(long long m00 = 0, long long m01 = 0, long long m10 = 0, long long m11 = 0) :m_00(m00), m_01(m01), m_10(m10), m_11(m11) {} long long m_00, m_01, m_10, m_11; }; Matrix2By2 MatrixMultiply(const Matrix2By2& matrix1, const Matrix2By2& matrix2) { return Matrix2By2( matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10, matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11, matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10, matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11 ); } Matrix2By2 MatrixPower(unsigned int n) { assert(n > 0); Matrix2By2 matrix; if (n == 1) matrix = Matrix2By2(1, 1, 1, 0); else if (n % 2 == 0) { // n是偶數(shù) matrix = MatrixPower(n / 2); matrix = MatrixMultiply(matrix, matrix); } else if (n % 2 == 1) { // n是奇數(shù) matrix = MatrixPower((n - 1) / 2); matrix = MatrixMultiply(matrix, matrix); matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0)); } return matrix; } long long Fibonacci_Solution3(unsigned int n) { if (n <= 1) return n; Matrix2By2 PowerNMinus2 = MatrixPower(n - 1); return PowerNMinus2.m_00; }
為了測(cè)試上邊三種方式的代碼的正確性,可以用如下樣例來(lái)測(cè)試。
// ====================測(cè)試代碼==================== void Test(int n, int expected) { if (Fibonacci_Solution1(n) == expected) printf("Test for %d in solution1 passed.\n", n); else printf("Test for %d in solution1 failed.\n", n); if (Fibonacci_Solution2(n) == expected) printf("Test for %d in solution2 passed.\n", n); else printf("Test for %d in solution2 failed.\n", n); if (Fibonacci_Solution3(n) == expected) printf("Test for %d in solution3 passed.\n", n); else printf("Test for %d in solution3 failed.\n", n); } int main(int argc, char* argv[]) { Test(0, 0); Test(1, 1); Test(2, 1); Test(3, 2); Test(4, 3); Test(5, 5); Test(6, 8); Test(7, 13); Test(8, 21); Test(9, 34); Test(10, 55); Test(40, 102334155); return 0; }
到此這篇關(guān)于C語(yǔ)言中斐波那契數(shù)列的三種實(shí)現(xiàn)方式(遞歸、循環(huán)、矩陣)的文章就介紹到這了,更多相關(guān)C語(yǔ)言 斐波那契數(shù)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)設(shè)計(jì)模式之裝飾者模式詳解
這篇文章主要介紹了C++設(shè)計(jì)模式之裝飾模式,裝飾模式能夠?qū)崿F(xiàn)動(dòng)態(tài)的為對(duì)象添加功能,是從一個(gè)對(duì)象外部來(lái)給對(duì)象添加功能,需要的朋友可以參考下2021-09-09C語(yǔ)言編程之初識(shí)數(shù)組線(xiàn)性查找和二分查找
本篇文章是C語(yǔ)言編程篇,主要為大家介紹C語(yǔ)言編程中數(shù)組的線(xiàn)性查找及二分查找分析講解,有需要的朋友可以借鑒參考下,希望可以有所幫助2021-09-09C/C++?Qt?TableDelegate?自定義代理組件使用詳解
TableDelegate自定義代理組件的主要作用是對(duì)原有表格進(jìn)行調(diào)整,本文主要介紹了QT中TableDelegate?自定義代理組件的使用教程,感興趣的朋友可以了解一下2021-12-12C++ GDI實(shí)現(xiàn)圖片格式轉(zhuǎn)換
GDI+(Graphics Device Interface Plus)是一種用于圖形繪制和圖像處理的應(yīng)用程序編程接口(API),在Windows平臺(tái)上廣泛使用,本文就來(lái)介紹一下如何使用GDI實(shí)現(xiàn)圖片格式轉(zhuǎn)換吧2023-12-12C/C++使用Zlib實(shí)現(xiàn)文件的壓縮與解壓
zlib 是一個(gè)開(kāi)源的數(shù)據(jù)壓縮庫(kù),旨在提供高效、輕量級(jí)的壓縮和解壓縮算法,本文將介紹如何使用 zlib 庫(kù)進(jìn)行數(shù)據(jù)的壓縮和解壓縮,以及如何保存和讀取壓縮后的文件,感興趣的可以了解下2023-11-11C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的三子棋游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)三子棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-09-09