著名的Pascal之父——Nicklaus Wirth(沃斯)讓他獲得圖靈獎的一句話就是他提出的著名公式:“程式=資料結構+算法”,這個公式對計算機科學的影響類似于愛因斯坦的質能方程在實體界的影響。
是以可以看出來資料結構和算法在我們開發程式中有多麼的重要了,下面我們來簡單認識下資料結構和算法..
1. 資料結構和算法介紹
資料結構介紹
資料結構是計算機存儲、組織資料的方式,指互相之間存在一種或多種特定關系的資料元素的集合。
通常情況下,精心選擇的資料結構可以帶來更高的運作或者存儲效率,對于程式來說選擇一個好的資料結構可以為企業節省更多的成本。資料結構往往同高效的檢索算法和索引技術有關。
常見的資料結構圖所示:
算法介紹
在Java中,算法通常都是由類的方法來實作的。前面的資料結構,比如連結清單為啥插入、删除快,而查找慢,平衡的二叉樹插入、删除、查找都快,這都是實作這些資料結構的算法所造成的。
算法簡單來說就是解決問題的方案步驟。它能夠對一定規範的輸入,在有限時間内獲得所要求的輸出;一個算法的優劣可以用空間複雜度(算法需要消耗的記憶體空間)與時間複雜度(執行算法所需要的計算工作量)來衡量。
空間複雜度和時間複雜度越低代表算法越好,往往一個好的算法,可以大大提高我們解決問題的效率!
算法規定應該具有以下5個特征:
- 有窮性(Finiteness)
算法執行的步驟必須是有限的,如果是無限的那麼算法就無法終止。
- 确切性(Definiteness)
算法的每一步驟必須有确切的定義;
- 輸入項(Input)
一個算法開始需要有0個或多個輸入,表示對象的初始條件,有了這個初始條件才能往下進行;
- 輸出項(Output)
一個算法應該有一個或多個輸出,它表示算法對資料處理後的結果。沒有輸出的算法是毫無意義的;
- 可行性(Effectiveness)
算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步驟,即每個計算步驟都可以在有限時間内完成;
常見的算法如:遞歸法、窮舉法、分治法、動态規劃法、疊代法、回溯法等。
這篇文章我們主要講的是遞歸算法
2. 遞歸算法
什麼是遞歸?
遞歸是一種直接或間接地調用自身的算法。它通常把一個大型複雜的問題層層轉化為一個個的較小的問題來求解,遞歸政策隻需少量的程式就可描述出解題過程所需要的多次重複計算,大大地減少了程式的代碼量,簡化了程式設計;
遞歸的條件
遞歸需要有結束條件(即要有邊界條件),如果沒有邊界條件就變成了無限死循環。當遞歸不滿足邊界條件是會繼續遞歸調用自身,直到滿足邊界條件為止;滿足遞歸的要求需要是減小(有限)而不是發散(無限可能)。
遞歸弊端
非遞歸函數效率高,但較難程式設計,可讀性較差。遞歸函數的缺點是增加了系統開銷,也就是說,每遞歸一次,棧記憶體就多占用一截,并且占用的記憶體直到遞歸完成之後才能被回收,遞歸次數越多空間複雜度越高,甚至嚴重時會出現OutOfMemoryError記憶體溢出。
遞歸的流程
遞歸練習
①求1~100之間數值相加的和為?
②有一斐波那契數列數字,其規則如下: 1、1、2、3、5、8、13、21、34 (每一個數為前兩個數之和),總結規律即f[n]=f[n-1]+f[n-2],求第30位數是多少?
③若一頭小母牛,從出生起第四個年頭開始每年生一頭母牛,其生的小母牛也從第四個年頭開始生每年生一頭母牛,按此規律,第 n 年 時有多少頭母牛?
④使用遞歸删除一個非空目錄
總結
在開發中對于一些較難程式設計或者不确定循環次數下完成事件的情況下,這時候我們就可以考慮下遞歸的使用了,當然如果能夠使用一兩次循環完成的事也不需要使用遞歸算法,畢竟遞歸算法的空間複雜度還是很高的。