一、第三章簡單回顧
中間略過了第三章， 第三章主要是介紹如何從數學層面上科學地定義算法複雜度，以緻于能夠以一套公有的标準來分析算法。其中，我認為隻要記住三個符号就可以了，其他的就看個人情況，除非你需要對一個算法剖根問底，不然還真用不到，我們隻需有個印象，知道這玩意是用來分析算法性能的。三個量分别是：确定一個函數漸近上界的Ο符号，漸近下屆Ω符号，以及漸近緊确界Θ符号，這是在分析一個算法的界限時常用的分析方法，具體的就詳看書本了，對于我們更多關注上層算法的表達來說，這些顯得不是那麼重要，我的了解是Ο可以簡單看成最壞運作時間，Ω是最好運作時間，Θ是平均運作時間。一般我們在寫一個算法的運作時間時，大多是以Θ符号來表示。參考下面這幅經典的圖：
二、第四章兩大闆塊
第四章講遞歸，也是數學的東西太多了，我準備這樣來組織這章的結構：先用一個例子（最大子數組和）來講解用到遞歸的一個經典方法——分治法，然後在引入如何解遞歸式，即引入解遞歸式的三種方法。
1、由分治法引發的
這一章提出了一個在現在各大IT公司在今天依然很喜歡考的一道筆試面試題：
要求時間複雜度是O(n)，我們暫且不管這個，由淺入深地分析一下這道題，時間複雜度從O(n^2)->O(nlgn)->O(n)。
1）、第一，大部分人想到的肯定是暴力法，兩個for循環，時間複雜度自然是O(n^2)，如下：
2）、第二，看了《算法導論》，你可能會想到分治法，看完之後你肯定會為該分治思想而驚歎，尤其是“橫跨中點”的計算思想。簡單說下該分治思想，其實很簡單，最大和子數組無非有三種情況：左邊，右邊，中間。
時間複雜度分析：
根據分治的思想，時間複雜度的計算包括三部分：兩邊+中間。由于分治的依托就是遞歸，我們可以寫出下面的遞推式（和合并排序的遞推式是一樣的）：
其中的Θ(n)為處理最大和在數組中間時的情況，經過計算（怎麼計算的，請看本節第二部分：解分治法的三種方法），可以得到分治法的時間複雜度為Θ(nlgn)。代碼如下：
3）、第三，看了《算法導論》習題4.1-5，你又有了另外一種思路：數組A[1...j+1]的最大和子數組，有兩種情況：a) A[1...j]的最大和子數組; b) 某個A[i...j+1]的最大和子數組，假設你現在不知道動态規劃，這種方法也許會讓你眼前一亮，确實是這麼回事，恩，看代碼吧。時間複雜度不用想，肯定是O(n)。和暴力法比起來，我們的改動僅僅是用一個指針指向某個使和小于零的子數組的左區間（當和小于零時，區間向左減小，當和在增加時，區間向右增大）。是以，我們給這種方法取個名字叫區間法。
第四，你可能在平常的學習過程中，聽說過該問題最經典的解是用動态規劃來解，等你學習之後，你發現确實是這樣，然後你又一次為之驚歎。動态規劃算法最主要的是尋找遞推關系式，大概思想是這樣的：數組A[1...j+1]的最大和：要麼是A[1...j]+A[j+1]的最大和，要麼是A[j+1]，據此，可以很容易寫出其遞推式為：
sum[i+1] = Max(sum[i] + A[i+1], A[i+1])
化簡之後，其實就是比較sum[i] ?> 0（sum[i] + A[i+1] ?> A[i+1]）,由此，就很容易寫出代碼如下：
可以看出，區間法和動态規劃有幾分相似，我覺得兩種方法的出發點和終點都是一緻的，隻不過過程不同。動态規劃嚴格遵循遞推式，而區間法是尋找使區間變化的辨別，即和是否小于零，而這個辨別正是動态規劃采用的。