本文試圖從一個簡單的小題目出發(fā)，引入算法的若干基本概念，重點引入一種方法：分治法，并且給出表述算法效率的記號。本文展示了算法教與學的一種常用范式，建議新生遵循這種思路進行學習。閱讀本文不需要任何大學知識為基礎，閱讀大概需要一個小時。
題目：尋找峰值
任意給出一組數(shù)值，比如：9、12、3、7，13。如果某一個數(shù)值同時比它左邊與右邊的數(shù)值都大，則這個數(shù)值就是一個峰值。直觀上，你可以想象一個山峰的形象。當然，如果某個數(shù)在數(shù)列的最左邊，如果它比它右邊的值要大，那么這個數(shù)值也是峰值。同理，如果某個數(shù)在數(shù)列的最右邊，如果它比它左邊的值大，它也是峰值。在上面給出的數(shù)列中，12是一個峰值，同時，13也是峰值。
問題是：如何能在一個n長的數(shù)列中找到任意一個峰值？要求是，這種方法應該盡可能快。
最普通的解法
因為有n個數(shù)值，可以看為放在n個盒子中的數(shù)字，如下表：
| a1 | a2 | a3 | a4 | ... | an |
|---|
設想這樣一個過程：從第一個數(shù)值a1開始，比對a1與其左右兩邊的數(shù)值，如果滿足條件，則輸出a1的值，結束過程；否則，繼續(xù)比對a2 。不斷迭代地做下去，直得最后一個數(shù)值an也被比對過。
這個過程要不就輸出某個峰值，要不就比對完所有的數(shù)值，找不到結果而停止。必須強調(diào)，這是一個必然會終止的過程，無論它是否找到滿足條件的峰值。
類似這樣，為了完成某個特定的任務而形成的（遲早會終止的）指令系列，稱之為算法。設計出算法后，通常我們要考慮兩個問題：算法的正確性與算法的復雜性。
算法的正確性
算法的正確性考慮：算法的執(zhí)行是否總能給出正確答案。當然并非所有算法的正確性都顯而易見。幸運的是，以上方法的正確性很顯然。
算法的復雜性
算法的復雜性指的是算法執(zhí)行的效率。大致上，衡量效率是看算法從開始到結束共需要執(zhí)行多少指令。因為指令執(zhí)行需要時間，所以也往往將效率理解為算法執(zhí)行所需的時間?？紤]“尋找峰值”問題的以上解法。最理想的狀態(tài)是，比對完a1，發(fā)現(xiàn)它就是峰值，算法結束，執(zhí)行了一個比對的過程。最糟糕的狀態(tài)是，需要比對完an，無論an是否我們想要的，都執(zhí)行了n次比對過程。那么，在衡量算法的效率時，答案到底是1還是n。
其實，這里時間1是算法的下界，即算法執(zhí)行最少需要的時間，記號是Big-Omega。n是算法的*上界，即算法最多要用的執(zhí)行時間，記號是Big O，簡記為O(n)。本文暫時不考慮Omega，只考慮Big O。這里我們犧牲了很多的技術細節(jié)，以后再補充?，F(xiàn)在我們只需要知道，如果算法最多執(zhí)行n步，就記為O(n)。
此處忽略很多細節(jié)，具體可參考課本CSI的第587頁的講解。
我們接下來需要思考的問題就是，要完成任務真的最多需要執(zhí)行n步嗎？最多執(zhí)行n/2步可以嗎？或者，log n步呢？（注，log指以2為底的對數(shù)。）
更合理的算法
解題思路
怎么思考更合理的解法呢？還是從以上算法出發(fā)，我們知道的是，以上算法遍歷了數(shù)組中所有的元素，效率是O(n)。我們通常把這種方法稱為“暴力法”，每一個元素都查詢確實很暴力。要提高效率，無非就是要“不完全遍歷”，非暴力?？赡軉幔款}目要求找到一個滿足要求的元素即可，也就是說你得到一個答案即可，并不需要遍歷所有元素。所以，這是可能的。
其次，要不完全遍歷，那么可能我們需要把所有數(shù)值分成若干部分，然后在其中某些部分進行搜索，而可以忽略掉某些部分。那么問題的關鍵點就在于，如何對數(shù)值進行分組？
接著就需要思考，既然分組，而且要“丟棄”某些分組，那么分組的主要目標是什么？確保所得的某個分組中存在至少一個峰值，然后針對這個存在解的分組進行峰值的尋找，忽略其他分組。比如，如果把所有元素分成左右兩部分，如果左邊部分必然存在一個峰值，那么右邊部分就可以不管了，因為我們的目標是找到一個峰值。
如果第一次分組可以達到目標-- 存在一個解，那么可以對分組中的元素再進行分組，不斷進行下去，總能得到解。盡管我們現(xiàn)在還不知道如何分組，但是我們可以分析一下，如果可以這樣做，效率是可以極大提高的。為什么呢？
給一個直觀，比如查字典。我們是一頁一頁地查，還是把字典分成兩半，再分成兩半地不斷去查？當然，這里還沒有數(shù)學，我們接下來需要更數(shù)學化的表示。你知道一頁一頁查的復雜性是多少嗎？而分半再分半的復雜性呢？
總之，分析到現(xiàn)在，我們整個解題思路就聚焦在這樣一個目標：對所有數(shù)值分組，并確保所得的某一個分組中存在至少一個峰值。
提示：分兩組，并確保其中一組中存在峰值。如何做？
分治法
以上策略就是把需要處理的數(shù)據(jù)分成不同的部分，然后逐個部分進行處理，從而得到更好的效率。我們把這種策略稱為“分治法(Divide-and-Conquer)”。
分治法是算法策略中的一種重要方法，許多重要算法都體現(xiàn)了“分而治之”的威力，比如：二分查找、快速排序等。關于分治法，可以通過學習更多的算法來加深體會。
算法描述
正確的做法非常簡單：
1、算出數(shù)組下標的中值，取中間元素（記為mid）進行判斷；數(shù)組元素被mid分成兩部分；
2、如果mid小于其左邊的元素，則遞歸地在左邊部分進行查找；
3、如果mid小于其右邊的元素，則遞歸在右邊部分查找；
4、否則mid就是答案。
偽代碼描述如下：
# 請注意，以下并非一個正確的、完整的Python代碼，是偽代碼，僅用于說明算法的過程。
# “#”后的文字代表注釋。
n = 100000 #假如有100000個元素
# List 里面裝了所有的數(shù)值，看成n個盒子
# head和tail分別是數(shù)值的第一個下標與最后一個下標
def find_peak(List, head, tail):
i = (head + tail) / 2 #取中值，i是index的縮寫
if List[i] < List[i - 1] :
find_peak(List, head, i - 1) #遞歸地在左半部分尋找峰值
elseif List[i] < List[i + 1]:
find_peak(List, i + 1, tail) #遞歸地在右半部分尋找峰值
else:
return List[i] #已經(jīng)找到答案，返回
建議閱讀者使用C語言實現(xiàn)該算法。需要完善的是邊界下標的判斷。比如，如果下標i已經(jīng)是0的時候，下標 i 的左邊是什么？沒有東西了，怎么辦？同理，當 i 跑到了右邊盡頭也一樣要處理。改進為迭代算法更佳。
算法的正確性
必須承認，現(xiàn)在要說明算法的正確性就不那么顯然了。除了要分析、說明以外，最值得信賴的方法是證明。
分析
先分析一下為什么算法會正確。首先看第4步，算法能執(zhí)行到第4步說明mid比它的左右鄰居都大，當然是答案。然后看第二步，如果算法執(zhí)行第2步的遞歸，說明第三步無需執(zhí)行，必然在左邊的分組中會存在峰值。為什么？第三步的分析類似，不贅述?，F(xiàn)在回答這個為什么。
如果mid比左邊元素小，則遞歸進行左邊部分的搜索。要說明這種做法的正確性，只需要說明，此時在左邊部分確實會至少存在一個峰值。這也是第三步無需執(zhí)行的原因。假定mid比左邊元素（記為a）小，此時分析兩種情形：
- a比它的左邊大，那么a就是峰值；
- a比它的左邊小，此時的情形與我們正在分析的mid的情形相同，但是數(shù)組長度少了一。
分析到此，讓我們設想一下，如果左邊只有a和mid兩個元素會如何？即a是數(shù)組的最左邊的元素會如何？回答：a是峰值。這個結論與上面兩點結合起來，答案呼之欲出。
頭腦風暴結束，建議大家在草稿紙上比劃比劃，然后回到正確的思路--證明--上來。
歸納法證明
先說一句題外話。在過去的幾年中，我發(fā)現(xiàn)大一新生對歸納法證明非常不感興趣，在他們看來歸納法非?！疤茁贰?，非常沒有意思，甚至會認為“不科學”、不是證明。要改變這種狀況，也許需要更多的工作。真心希望中學里面學歸納法沒有學壞胃口。歸納法證明是一種非常值得學習和使用的方法。
證明：
1、歸納基礎
數(shù)組有1個元素，且mid比該數(shù)組最右邊（或者左邊，以下省略左邊不寫）的元素小，則存在一個峰值。顯然！
2、歸納假設
假設數(shù)組有n個元素，且mid比該數(shù)組最右邊元素小，則該數(shù)組必有峰值。
3、歸納證明“數(shù)組有n+1個元素，且mid比該數(shù)組最右邊元素小，則該數(shù)組必有峰值”
忽略若干細節(jié)，請同學們自己完成。
算法的復雜性
到了最困難的撰寫部分。以下內(nèi)容如果引起新生的不適，可暫時忽略。
用一個函數(shù)T(n)來衡量算法的效率，其中n是輸入數(shù)值的數(shù)量，在本文就是數(shù)組的大小。立即可以知道：
T(0) = 0 #沒有輸入，不要花時間
T(1) = c #c代表常數(shù)時間
T(n) = T(n/2) + c
#每次算法執(zhí)行了一下對比的過程，使用c時間，然后進入遞歸
#遞歸只針對一半的元素，所以是T(n/2)
現(xiàn)在需要算出函數(shù)T的具體數(shù)值表達。沒有什么技巧，只需要不斷地做除法：
T(n) = T(n/2) + c
T(n/2) = T((n/2)/2)+ c
T((n/2)/2) = T(((n/2)/2)/2) +c
... #這里代表不斷地除，并且假設n是2的某個冪次。
T(1) = c
然后，立即得到：（能看出來為什么嗎？）
T(n) = c + c + ... + c
最后一步，這里到底有多少個c？回憶一下十進制的二進制表達。并聯(lián)想到，除2只是左移一位。那么能“左移”多少次呢？答案：log n 次。所以：
T(n) = log n * c = O(log n)
進一步的考慮
如果我們把問題進一步擴展，不考慮一維數(shù)組，而是考慮二維數(shù)組。在二維數(shù)組中的峰值，直觀上就是一個數(shù)值，它比它的上下左右的數(shù)值都要大。在二維數(shù)組中求峰值，算法應該如何設計？復雜性是多少？
留給同學們思考練習。
關于算法的學習建議
有許多關于算法的基礎知識值得立即學習，這些內(nèi)容非常經(jīng)典，無論是教材還是網(wǎng)絡上的電子資料和代碼都非常多，因此不再繼續(xù)以下專題的寫作。建議專題如下：
- 二分查找法
- 排序算法：插入排序、歸并排序、快速排序
- 數(shù)據(jù)結構相關：隊列、堆棧、二叉樹
- 堆與堆排序
- 二叉查找樹
- 圖與圖遍歷算法
- 動態(tài)規(guī)劃基礎
- 貪心法
建議新生立即就以上專題制定學習進度計劃。
課本CSI第7章有講相關內(nèi)容。缺點是缺乏相應的訓練，內(nèi)容廣度、深度都不夠，需要進一步閱讀。個人認為，在大一第一學期及時開展相關內(nèi)容的學習是可行的，而且強烈建議進行。學習這些是為了盡快開展CLRS的閱讀，建議大一寒假進行。
有同學會問，我現(xiàn)在編程基礎都沒有，學算法會不會太冒進？回答：不會。算法與程序應該同時學習、訓練，沒有算法的程序就是沒有靈魂的程序，營養(yǎng)不足。總是訓練寫沒有營養(yǎng)的程序，程序能力不能很好地提高。反過來，學算法不考慮實現(xiàn)，不知道算法與程序之間的差異，也不能真正領悟算法的核心本質(zhì)。
輔助資料
2017年8月25日起草
2017年8月27日定稿
