“常見經典算法”分析與研究

劉放美+蔡增玉+付長寬

摘 要： 經典算法是計算機專業核心課程之一。計算機算法的優劣，對于計算機硬件的利用和系統的性能具有重要的影響。算法也是計算機科學中重要的理論之一。本文對遞歸算法、分治算法、動態規劃算法、貪心算法等經典的算法進行研究，著重闡述算法的設計思想、優缺點及其應用，并對算法的發展進行了探索。

關鍵詞： 經典算法； 設計思想； 優缺點； 應用； 展望

中圖分類號：TP301 文獻標志碼：A 文章編號：1006-8228（2017）11-58-03

Analysis and study on common classical algorithms

Liu Fangmei1， Cai Zengyu2， Fu Changkuan1

（software engineering college， Zhengzhou University of Light Industry， Zhengzhou， Henan 450002， China；

2. School of Computer and Communication Engineering， Zhengzhou University of Light Industry）

Abstract： Classical algorithm is one of the core courses in computer science. Computer algorithm has great effect on the performance and use of computer hardware system. Algorithm is also one of the most important theories in computer science. In this paper， the classical algorithms such as the recursive algorithm， partition algorithm， dynamic programming algorithm and greedy algorithm etc. are studied， the design idea， advantages and disadvantages， and the applications of the algorithms are emphatically expounded， and the development of the algorithms is explored.

Key words： classical algorithm； design idea； advantages and disadvantages； prospect

0 引言

算法是通過基本運算及運算規定的運算順序所構成的完整的解題步驟。算法要求設計好有限的、確切的計算序列，通過設計好的步驟和計算序列可以解決同類問題。要設計出好的算法，就必須對存在的問題有深入細致的了解，還要有獨特的思考方式，只有如此，才能有奇妙的算法思想，這正是解決問題的關鍵。當解決問題的方式有多種多樣時，就會存在不同的算法思想，而它們在解決問題時有各自的優勢和不足，我們根據需求，選擇出最佳方案，用最合適的算法來解決現實中的問題，并逐步探索研究未來算法的方向，這便是我們探究與發現的初衷[1]。

1 常見經典算法分析

1.1 遞歸算法

遞歸算法是在一個函數定義或者聲明的過程中直接或者間接地又調用自身的一種方法。遞歸算法基本思想是，把一個復雜的大問題轉化為規模較小且相似的子問題來解決，可以用很少的代碼來解決多次重復計算的問題，節省了運算時間。對于一些產生情況非常多的算法問題，利用窮舉法將是非常麻煩且不明智的，如果利用遞歸可以解決的話，就可以實現交換元素，函數調用函數，最終得到結果。這避免了重復計算，節約了運算時間。

遞歸的缺陷是解決問題的運行效率非常低[2]，原因在于在遞歸調用的過程中，系統會為每一層的返回點，局部變量等開辟了堆棧來存儲，而且如果出現遞歸調用次數過多，會出現堆棧溢出的問題，這也是很可怕的。

我們應該知道遞歸都用來解決哪些問題，首先，它可以解決一些數據的定義，其次，它可以實現一些問題求解，而且，數據的結構形式也可以按照遞歸定義。按照遞歸的這些適用條件，我們很容易的想到，它可以解決我們經常見到的Fibonacci函數，回溯算法，以及樹的遍歷，圖的搜索等相關的問題。

1.2 分治算法

分治算法是把一個復雜的問題分成了多個子問題，逐步細分，直到子問題可以直接求解，而子問題的解的合并就是原問題的解。分治法的基本思想是把一個不容易解決的子問題分為規模較小的相似問題，以便于可以直接求解，遞歸地解決這些子問題，再將得到的子問題的解合并，就得到了原問題的解。

當需要解決一個輸入規模（n）很大的問題時，直接處理往往比較困難或者根本無法求解，我們希望把輸入規模縮小，即分成很多份，分別去解決，并且這些小問題容易合起來從而解決整個問題。這便是分治的優勢所在，簡單高效。但是分治法的合并步驟并不是很容易的，有的問題的合并方法比較明確，而有的問題的合并方法比較復雜，可能還需要討論多種合并方案，這也是一個小缺陷。

分治算法在一些應用中是簡單有效的，只要遇到的問題可以分解為很多小規模的相似的子問題，且子問題獨立無依賴，最后又可以合并子問題的解，就可以使用分治算法[3]。在一些經典的排序問題中，分治法起到了至關重要的作用。

1.3 動態規劃算法

動態規劃是一個過程，每次決策都依賴于當前的狀態，然后會引起狀態的轉移，如何決策就是在變化中產生出來的，這樣的多階段最優化決策解決問題的過程就是動態規劃。動態規劃把要求解的問題分成了很多子問題，從簡單的子問題入手，求出它們的解，然后再得出最終答案。與分治算法不同的是，動態規劃算法不是遞歸地求解每一個子問題，而是從簡單問題的解入手，逐步求解，最后再求出原問題的解，動態規劃的高明之處就在于，它不會重復求解某些重復出現的子問題，即一些重疊子問題，所以計算的效率是非常高的。利用動態規劃，可以保存已解決的子問題的答案，在需要的時候再加以利用，這樣減少了大量的重復計算，節省了時間。求解過程就是先找出最優解的結構，遞歸定義一個最優解的值，然后以自底向上的方式計算出最優解的值，根據計算最優解的值的信息，構造出一個最優解。但是動態規劃在存儲中間過程產生的結果需要大量的空間，這是動態規劃的明顯缺點，以空間換時間。endprint

對于動態規劃算法來說，它要依賴于問題本身所具有的兩個重要性質，一個是最優子結構性質，另一個是子問題重疊性質[4]。只有提前滿足了這兩個條件，動態規劃算法才能發揮它的高效作用。動態規劃算法的應用十分廣泛，典型應用有矩陣連乘，在解決矩陣連乘問題中，先從最簡單的兩個矩陣相乘開始，再看三個，四個，從而得到如何進行乘法運算，可以讓相乘的次數最少，最后我們可以求出矩陣連乘的次數和它們如何相乘。正是以大化小，才使解決問題更加方便。動態規劃還經常應用在最長公共子序列、最大字段和數字三角形問題上。

1.4 貪心算法

貪心算法是指在求解問題時不從整體上考慮，只做出當前最好的選擇，也就是局部最優解。貪心算法的基本思想是找出整體中局部的最優解，然后根據這些最優解來得到整體的最優解。在求解最優化問題算法中，一般會包括一系列的求解步驟，每一個求解步驟中都有一個選擇，然后得到問題的一個解。貪心算法在具體求解問題時是非常簡單有效的，有時候雖然不能得到最優解，但是可以得到近似解。貪心算法只選擇當前看起來最好的選擇，而不去考慮它整體是不是最好的，正確的運用貪心算法，應該保證貪心策略無后效性，即：某個狀態以后過程不影響以前的狀態，只和當前狀態有關。貪心算法對于解決很多問題都是非常有效的，因為局部最優解很容易找到，所以簡單易懂，效率較高，對于許多問題都可以得到整體最優解。貪心算法的缺點主要表現在它的“非理想性”。因為我們找到的問題往往并不一定符合貪心算法的適用條件，即使達到了局部最優，也很難得到我們想要的結果。貪心算法要想有效，就必須滿足問題的約束，達到局部最優的條件。如圖1所示的單源路徑問題，雖然我們無法一眼看出最優的結果，不知道該從哪一步走，但我們可以根據相鄰頂點的路徑來找出當前最好的選擇，這便是先從局部最優開始[5]。

我們可以用dist[i]來記錄當前的每個頂點的最短路徑，再從結果中找出具有最短路徑的頂點，寫入S集合中，等把所有的頂點都加入到了S集合中，dist就記錄了源頂點到其他頂點最短的路徑長度。如表1所示：

此外，貪心算法還廣泛地應用于活動安排問題，背包問題，最優裝載問題等。

1.5 經典算法的比較

經典算法有很多，每個算法都有其獨到之處。本文對遞歸算法，分治算法，動態規劃算法和貪心算法進行歸納分析，總結了各自的優缺點，如表2所示。要想真正地將算法用到恰到好處，就必須根據應用場景，在相應的條件下使用合適算法解決實際問題[6]。

2 未來展望

很多人認為，未來算法的重要性會變低，但是作為計算機科學領域最重要的基石之一的算法，它的重要性是會日益加強的。而且算法也將不局限于計算機和網絡，它所應用的范圍也會越來越大。

2.1 算法在未來的重要性

在很多程序員看來，編程語言最值得關注，其實隨著時代的發展，算法會變得越來越有用，雖然編程語言的種類越來越多，有些編程語言由冷門到熱門，然而有些也會從熱門變為冷門，技術在不停地更新換代，但是有些東西是不變的，例如算法，數據結構，編程原理，關系型數據庫原理，計算機體系結構等等。未來編程，算法將會是一種內在的“修養”，沒有算法的思想和理論，就不可能成為真正的程序員。

2.2 算法在未來的應用

如今計算機已經全面普及，價格也很低廉。當在激烈的競爭中，用戶體驗成為了關鍵，用算法去設計各種應用，是一個必然的選擇。在存儲方面，大數據存儲是關鍵問題，算法能有效的提高大數據存儲的效率。在科學研究方面，無論是三維模型還是數據處理，都會需要很大的計算量，都要靠算法來解決。例如Google每天都會處理數以億計的搜索，存儲幾千萬用戶的數據，通過互聯網將巨量的信息提交給每個用戶，很顯然，如果沒有找到好的算法，這些是不可能完成的。所以Google數據中心使用的是超大型并行計算機，讓并行算法在并行計算的環境下執行，使處理請求速度得到飛躍式的提升。

2.3 算法前景

算法的作用在未來計算機的發展中不可估量，不僅在大數據和云計算方面，也用于解決實驗數據的處理和存儲，還用來研究人類基因，發明新的醫療方式，可以保障國家網絡安全，預測天災的發生等。算法在未來的機遇和挑戰并存的環境中是不可或缺的，是不可以替代的。我們要用發展的眼光來看待算法，與時俱進，不可輕視它，冷落它，須始終保持一顆對算法探索研究的心，爭取利用算法來造福美好的未來。

3 總結

本文對常用經典算法進行了概括與分析，探究了算法的設計思想與優缺點，并根據算法的具體應深入探討算法。從分析和研究我們可以看出，在不同的情況下，應該選擇不同的算法。同時，我們也能發現在復雜的問題面前，一個正確高效的算法是非常重要的，每一個算法都有自己的優缺點，在算法選擇時，要考慮算法本身的特性。面對復雜的問題，要具體問題具體分析，將復雜的問題簡單化，將算法的思想與解題步驟巧妙地聯系在一起，用科學有效的方法來解決問題，這是學習的意義所在。算法有著美好而又遠大的前景，還需要我們獨具慧心，發掘算法的潛力，造福我們的生活。

參考文獻（References）：

[1] 陳德裕，杭月芹.數據結構中經典算法的教學研究[J].計算機

時代，2009.6：3-4

[2] 袁勁松，楊偉明.遞歸算法設計及效率分析[J].計算機與數字

工程，2007.2：12-13

[3] 李健勇，李曄，劉艷紅，張杰，李建春，黃道穎.任意數量選手的

循環賽賽程分治算法[J].鄭州輕工業學院學報（自然科學版），2007.4：26-27

[4] 宛楠，張義.動態規劃算法分析[J].長江大學學報（自然科學

版），2013.7：3-6

[5] 常友渠，肖貴元，曾敏.貪心算法的探討與研究[J].重慶電力高

等專科學校學報，2008.3：31-32

[6] 歐陽圣，胡望宇.幾種經典搜索算法研究與應用[J]. 計算機系

統應用，2011.5：16-17endprint