算法（Algorithm）是為了解決一個特定的問題而精心設計的一套數學模型以及在這套數學模型上的一系列操作步驟，這些操作步驟是將描述的輸入數據逐步處理、轉換，并最后得到一個確定的結果。當然，準確性是基本前提，時間和空間效率是衡量一個算法優劣的重要評估標準。算法通常在函數中使用控制結構來實現。
1 算法分類
算法是一個比較大的概念范疇，為便于理解，可以從算法思想，典型應用及與數據結構的關系，將算法分為三類：
1.1 經典算法思想
一般來說，算法設計沒有什么固定的方法可循。但是通過大量的實踐，人們也總結出算法某些共性的規律，包括窮舉法(Enumeration)、遞推法(Recurrence)、遞歸法、分治法(Divide and Conquer)、貪心法、回溯法(Backtracking)、動態規劃法等。
1.2 經典算法思想在典型問題上的應用
如排序、查找（檢索）等算法。盡管計算學科的整個發展可以很短，但前人們還是留下了很多非常經典的算法，僅就排序而言，就可以數出一大堆，如冒泡排序法、快速排序法、選擇排序法、插入排序法、基數排序法等。
1.3 在數據結構上應用的算法
包括增、查、刪、改、遍歷、圖的最路徑、最小生成樹、樹的遍歷方法，線性表的二分查找，以及數據類型的運算符，類類型的操作符重載。
有些算法充滿著智慧，如Dijistra最短路徑、Huffman樹、蒙特卡洛方法、快速排序、堆排序、紅黑樹、A+樹、字符串匹配的KMP算法等。
2 從算法中的分治思想來體現各類算法思想中的細微區別
復雜的問題可以分而治之。對于復雜的問題，通常都需要應用分治的思想，同時，很多算法中也有分治思想的體現。分治法所能解決的問題一般具有以下幾個特征：
① 該問題的規模縮小到一定的程度就可以容易地解決；
② 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質
③ 利用該問題分解出的子問題的解可以合并為該問題的解；
④ 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。
因為問題的計算復雜性一般是隨著問題規模的增加而增加，因此大部分問題滿足這個特征。
遞歸的子問題之間是同類、縱向的關系，而枚舉是橫向的關系。
如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態規劃。
特征④涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態規劃較好。
動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，但是經分解得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。
遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。動態規劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數時間查看一下結果。
通常不同的子問題個數隨問題的大小呈多項式增長。因此用動態規劃算法只需要多項式時間，從而獲得較高的解題效率。
顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。如單源最短路徑問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優解，其最終結果卻是最優解的很好近似。
貪心算法和動態規劃算法都要求問題具有最優子結構性質，這是兩類算法的一個共同點。嚴格地說，用動態規劃的問題一般都有前后重疊的，需要用前一階段的結果局部貪心推出下一個階段結果。貪心算法一般要得到最優解只能各個階段沒有重疊，以局部最優構造全局最優。
3 了解算法的8個要點
3.1 算法是程序設計的“熟語”（常見短語）,有大算法與有小算法；
3.2 算法中解決問題的步驟是明確且有限的；
3.3 計算機不靠直覺而是機械地解決問題（就是簡單傻瓜式地一步一步做）；
3.4 了解并應用典型算法；
3.5 利用計算機的處理速度；無論是多么冗長繁瑣的步驟，只要明確并且機械就是優秀的算法；
3.6 使用編程技巧提升程序執行速度；也就是說解決問題的方法是可以優化的，就像做事有方法，效率就會高一樣，算法也是可以優化的；
3.7 找出數字間的規律；因為在計算機中所有的信息都可以用數字表示，因此構造算法，就可以利用到存在于數字間的規律。規律+邏輯；
3.8 先在紙上考慮算法；也就是先在紙上把步驟用文字或圖形表示出來，用簡單的數字先做驗證；
4 九種基本算法思想簡述
4.1枚舉法Enumeration method
枚舉算法思想的最大特點是，在面對任何問題時它會去嘗試每一種解決方法。在進行歸納推理時，如果逐個考察了某類事件的所有可能情況，因而得出一般結論，那么這個結論是可靠的，這種歸納方法叫作枚舉法。
枚舉算法的思想是：將問題的所有可能的答案一一列舉，然后根據條件判斷此答案是否合適，保留合適的，丟棄不合適的。在C語言中，枚舉算法一般使用while循環實現。使用枚舉算法解題的基本思路如下。
① 確定枚舉對象、枚舉范圍和判定條件。
② 逐一列舉可能的解，驗證每個解是否是問題的解。
枚舉算法一般按照如下3 個步驟進行。
① 題解的可能范圍，不能遺漏任何一個真正解，也要避免有重復。
② 判斷是否是真正解的方法。
③ 使可能解的范圍降至最小，以便提高解決問題的效率。
4.2迭代法Iteration method
迭代法也稱輾轉法，是一種不斷用變量的舊值遞推新值的過程。與迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。迭代法又分為精確迭代和近似迭代。“二分法”和“牛頓迭代法”屬于近似迭代法，功能都比較類似。
迭代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。
在使用迭代算法解決問題時，需要做好如下3 個方面的工作。
（1）確定迭代變量
在可以使用迭代算法解決的問題中，至少存在一個迭代變量，即直接或間接地不斷由舊值遞推出新值的變量。
（2）建立迭代關系式
迭代關系式是指如何從變量的前一個值推出其下一個值的公式或關系。通常可以使用遞推或倒推的方法來建立迭代關系式，迭代關系式的建立是解決迭代問題的關鍵。
（3）對迭代過程進行控制
在編寫迭代程序時，必須確定在什么時候結束迭代過程，不能讓迭代過程無休止地重復執行下去。通常可分為如下兩種情況來控制迭代過程：
① 所需的迭代次數是個確定的值，可以計算出來，可以構建一個固定次數的循環來實現對迭代過程的控制；
② 所需的迭代次數無法確定，需要進一步分析出用來結束迭代過程的條件。
4.3遞推法Recurrence method
與枚舉算法思想相比，遞推算法能夠通過已知的某個條件，利用特定的關系得出中間推論，然后逐步遞推，直到得到結果為止。由此可見，遞推算法要比枚舉算法聰明，它不會嘗試每種可能的方案。
遞推算法可以不斷利用已有的信息推導出新的東西，在日常應用中有如下兩種遞推算法。
① 順推法：從已知條件出發，逐步推算出要解決問題的方法。例如斐波那契數列就可以通過順推法不斷遞推算出新的數據。
② 逆推法：從已知的結果出發，用迭代表達式逐步推算出問題開始的條件，即順推法的逆過程。
4.4遞歸法Recursion method
因為遞歸算法思想往往用函數的形式來體現，所以遞歸算法需要預先編寫功能函數。這些函數是獨立的功能，能夠實現解決某個問題的具體功能，當需要時直接調用這個函數即可。
在計算機編程應用中，遞歸算法對解決大多數問題是十分有效的，它能夠使算法的描述變得簡潔而且易于理解。遞歸算法有如下3 個特點。
① 遞歸過程一般通過函數或子過程來實現。
② 遞歸算法在函數或子過程的內部，直接或者間接地調用自己的算法。
③ 遞歸算法實際上是把問題轉化為規模縮小了的同類問題的子問題，然后再遞歸調用函數或過程來表示問題的解。
在使用遞歸算法時，應該注意如下4 點。
① 遞歸是在過程或函數中調用自身的過程。
② 在使用遞歸策略時，必須有一個明確的遞歸結束條件，這稱為遞歸出口。
③ 遞歸算法通常顯得很簡潔，但是運行效率較低，所以一般不提倡用遞歸算法設計程序。
④ 在遞歸調用過程中，系統用棧來存儲每一層的返回點和局部量。如果遞歸次數過多，則容易造成棧溢出，所以一般不提倡用遞歸算法設計程序。
4.5分治法Divide and conquer
分治算法采取各個擊破的方法，將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。只要求出子問題的解，就可得到原問題的解。
在編程過程中，經常遇到處理數據相當多、求解過程比較復雜、直接求解法會比較耗時的問題。在求解這類問題時，可以采用各個擊破的方法。具體做法是：先把這個問題分解成幾個較小的子問題，找到求出這幾個子問題的解法后，再找到合適的方法，把它們組合成求整個大問題的解。如果這些子問題還是比較大，還可以繼續再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治算法的基本思想。
使用分治算法解題的一般步驟如下。
① 分解，將要解決的問題劃分成若干個規模較小的同類問題。
② 求解，當子問題劃分得足夠小時，用較簡單的方法解決。
③ 合并，按原問題的要求，將子問題的解逐層合并構成原問題的解。
4.6動態規劃Dynamic programming
動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。
(1) 基本概念
每次決策依賴于當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。
(2) 基本思想
與分治法類似，也是將待求解的問題分解為若干個子問題，按順序求解子問題，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解，依次解決各子問題，最后一個子問題就是初始問題的解。
與分治法最大的差別：適合于用動態規劃法求解的問題，經分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。
(3) 適用的情況
① 最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。
② 無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響，也就是說，某狀態以后的過程不會影響以前的狀態，只與當前狀態有關。
④ 有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質并不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）
(4) 解題步驟
動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟：
初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態
① 劃分階段：按照問題的時間特征，把問題分為若干個階段，在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。
② 確定狀態和狀態變量：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來，當然，狀態的選擇要滿足無后效性。
③確定決策并寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀態之間的關系來確定決策方法和狀態轉移方程。
④ 尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。
一般，只要解決問題的階段、狀態和狀態轉移決策確定了，就可以寫出狀態轉移方程。實際應用中可以按以下幾個簡化的步驟進行設計：
① 分析最優解的性質，并刻畫其結構特征。
② 遞歸的定義最優解。
③ 以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優值。
④ 根據計算最優值時得到的信息，構造問題的最優解。
(5) 算法實現的說明
動態規劃的主要難點在于上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。使用動態規劃求解問題，最重要的就是確定動態規劃三要素：
① 問題的階段
② 每個階段的狀態
③ 從前一個階段轉化到后一個階段之間的遞推關系。
遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。
確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。
4.7貪心法Greedy
貪心算法也被稱為貪婪算法，它在求解問題時總想用在當前看來是最好方法來實現。這種算法思想不從整體最優上考慮問題，僅僅是在某種意義上的局部最優求解。雖然貪心算法并不能得到所有問題的整體最優解，但是面對范圍相當廣泛的許多問題時，能產生整體最優解或者是整體最優解的近似解。由此可見，貪心算法只是追求某個范圍內的最優，可以稱之為“溫柔的貪婪”。
貪心算法從問題的某一個初始解出發，逐步逼近給定的目標，以便盡快求出更好的解。當達到算法中的某一步不能再繼續前進時，就停止算法，給出一個近似解。由貪心算法的特點和思路可看出，貪心算法存在以下3 個問題。
① 不能保證最后的解是最優的。
② 不能用來求最大或最小解問題。
③ 只能求滿足某些約束條件的可行解的范圍。
貪心算法的基本思路如下。
① 建立數學模型來描述問題。
② 把求解的問題分成若干個子問題。
③ 對每一子問題求解，得到子問題的局部最優解。
④ 把子問題的局部最優解合并成原來解問題的一個解。
實現該算法的基本過程如下。
（1）從問題的某一初始解出發。
（2）while能向給定總目標前進一步。
（3）求出可行解的一個解元素。
（4）由所有解元素組合成問題的一個可行解。
4.8回溯法Recursive search
回溯法也叫試探法，試探法的處事方式比較委婉，它先暫時放棄關于問題規模大小的限制，并將問題的候選解按某種順序逐一進行枚舉和檢驗。當發現當前候選解不可能是正確的解時，就選擇下一個候選解。如果當前候選解除了不滿足問題規模要求外能夠滿足所有其他要求時，則繼續擴大當前候選解的規模，并繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在試探算法中，放棄當前候選解，并繼續尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，并繼續試探的過程稱為向前試探。
使用試探算法解題的基本步驟如下所示。
① 針對所給問題，定義問題的解空間。
② 確定易于搜索的解空間結構。
③ 以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。
試探法為了求得問題的正確解，會先委婉地試探某一種可能的情況。在進行試探的過程中，一旦發現原來選擇的假設情況是不正確的，立即會自覺地退回一步重新選擇，然后繼續向前試探，如此這般反復進行，直至得到解或證明無解時才死心。
4.9分支限界法Branch and Bound Method
分支限界法類似于回溯法，也是一種在問題的解空間樹上搜索問題解的算法，但在一般情況下，分支限界法與回溯法的求解目標不同。回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數值達到極大或極小的解，即在某種意義下的最優解。
由于求解目標不同，導致分支限界法與回溯法在解空間樹上的搜索方式也不相同。回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。
分支限界法的搜索策略：在擴展結點處，先生成其所有的兒子結點（分支），然后再從當前的活結點表中選擇下一個擴展對點。為了有效地選擇下一擴展結點，以加速搜索的進程，在每一活結點處，計算一個函數值（限界），并根據這些已計算出的函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。
分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有子集樹和排列樹。在搜索問題的解空間樹時，分支限界法與回溯法對當前擴展結點所使用的擴展方式不同。在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，那些導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所求的解或活結點表為空時為止。
回溯法深度優先搜索堆棧活結點的所有可行子結點被遍歷后才被從棧中彈出找出滿足約束條件的所有解。
分支限界法廣度優先或最小消耗優先搜索隊列、優先隊列每個結點只有一次成為活結點的機會找出滿足約束條件的一個解或特定意義下的最優解。
