初入算法（2）—— 進入算法世界

目錄

​​前言​​

​​一.爆炸增量函數​​

​​1.引入故事：《一棋盤的麥子》​​

​​2.算法中的時間複雜度​​

​​3.常見的時間複雜度類型​​

​​二.兔子數列​​

​​1.什麼是兔子數列​​

​​2.遞推公式​​

​​3.尾數循環​​

前言

努力是為了不平庸~

在分享的同時加深對于算法的了解，同時吸收他人的奇思妙想，一起見證技術er的成長~

本章将會繼續在​​初入算法（1）——進入算法世界​​ 的基礎上繼續通過趣學算法進行算法的學習。

一.爆炸增量函數

1.引入故事：《一棋盤的麥子》

有一個古老的傳說，一位國王的女兒不幸落水，水中有很多鳄魚，國王情急之下下令：“誰能把公主救上來，就把女兒嫁給他。”很多人紛紛退讓，一個勇敢的小夥子挺身而出，冒着生命危險把公主救了上來，國王一看是個窮小子，想要反悔，說：“除了女兒，你要什麼都可以。”小夥子說：“好吧，我隻要一棋盤的麥子。您在第1個格子裡放1粒麥子，在第2個格子裡放2粒，在第3個格子裡放4粒，在第4個格子裡放8粒，以此類推，每一個格子裡麥子的粒數都是前一格子裡麥子粒數的兩倍。把這64個格子放滿了就行，我就要這麼多。”國王聽後哈哈大笑，覺得小夥子的要求很容易滿足，滿口答應。結果發現，把全國的麥子都拿來，也填不完這64個格子…..…國王無奈，隻好把女兒嫁給了這個小夥子。

解析：通過這個故事，算出64格可放的麥子，總和為S

S=1+2一次方＋2的二次方+2的三次方......+2的63次方①

對式①等号的兩邊乘以2，等式仍然成立

2S=2的一次方+2的二次方+2的三次方+....+2的64次方

用式②減去①得

S=2的64次方-1= 18 446 744 073 709 551615

重量=7729000（億千克）

我們稱這樣的函數為爆炸增量函數。

2.算法中的時間複雜度

如果算法的時間複雜度是O(2n次方)

會怎樣？随着n的增長，算法會不會“爆掉”？我們經常見到有些算法調試沒問題，

運作一段時間也沒問題，但在關鍵的時候當機（shutdown）。

例如：線上考試系

統，50人考試沒問題，100人考試也沒問題，但如果全校10000人考試就可能當機。

科普：當機就是當機，指計算機無法正常工作，包括一切原因導緻的當機。計算機主機出現意外故障而當機，一些伺服器（如資料庫伺服器）死鎖，伺服器的某些服務停止運作等，都可以稱為當機。

3.常見的時間複雜度類型

（1）常數階

常數階算法的運作次數是一個常數，如5、20、100。常數階算法的時間複雜度通常用O（1)表示。

（2）多項式階

很多算法的時間複雜度是多項式，通常用O（n)、O(n²)、O(n³）等表示。

（3）指數階

指數階算法的運作效率極差，程式員往往像躲“惡魔”一樣避開這種算法。指數階算法的時間複雜度通常用O（2ⁿ）、O（n!）、O（nⁿ）等表示。

（4）對數階

對數階算法的運作效率較高，通常用O（logn)、O（nlogn)等表示。

二.兔子數列

1.什麼是兔子數列

兔子數列又稱斐波那契數列（Fibonacci sequence），又稱黃金分割數列，因數學家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在現代實體、準晶體結構、化學等領域，斐波那契數列都有直接的應用，為此，美國數學會從 1963 年起出版了以《斐波那契數列季刊》為名的一份數學雜志，用于專門刊載這方面的研究成果

斐波那契數列概述圖

例子：

假設第1個月有1對初生的兔子，第2個月進入成熟期，第3個月開始生育兔子，而1對成熟的兔子每月會生1對兔子，兔子永不死去…….那麼，由1對初生的兔子開始，12個月後會有多少對兔子呢？

 當月兔子數=上月兔子數+上上月兔子數

算法設計：遞歸算法

int Fib1(int n){
    if(n==1||n==2)
    return 1;
    return Fib1(n-1)+Fib1(n-2);
}      

算法驗證：

假設T(n)表示計算Fib1（n)所需的基本操作次數，那麼：

n=1時，T(n)=1；
n=2時，T(n)=1；
n=3時，T（n）=3；//調用Fib1（2）和Fib1（1）并執行一次加法運算（Fib1（2）+Fib1（1））      

是以，當n>2時需要分别調用Fib1（n-1）和Fib1（n-2）并執行一次加法運算，換

言之：

n>2時，T(n)=T(n-1)+T(n-2)+1；      

遞歸表達式和時間複雜度T(n)的關系如下：

 由此可得：

 如何算出F(n)?

 求出斐波那契數列的通項公式：

2.遞推公式

斐波那契數列：1，1，2，3，5，8，13，21，34，55，89...

如果設an為該數列的第n項（），那麼這句話可以寫成如下形式：

 顯然這是一個線性​​遞推數列​​

通項公式内容

 (如上，又稱為“比内公式”，是用​​無理數​​​表示​​有理數​​的一個範例。)

3.尾數循環

斐波那契數列的個位數：一個60步的循環

11235,83145,94370,77415,61785,38190,