計算機算法概述

【摘要】本文在分析算法定義的基礎上，對常見的５種算法進行論述并總結各自算法的特點。

【關鍵詞】算法定義常見算法

隨著計算機技術的突飛猛進，算法逐漸成為了核心內容，不容忽視。算法更能體現計算機的精髓，計算機技術的根本，算法的設計有多種方案，不同的實現方案展現的結果不同，這提現了計算機技術的多姿多彩。對于計算機技術來說，算法分析與設計是至關重要的。在一個大型軟件系統的開發中，設計出有效的算法將起到決定性的作用。

１.定義

通俗的講，算法是解決問題的一種方法。也因此算法分析與設計成為計算技術的核心問題之一，也是計算機科學與技術專業本科及研究生的一門重要的專業基礎課。算法分析與設計是計算機軟件開發人員必修課，軟件的效率和穩定性取決于軟件中所采用的算法；對于一般程序員和計算機專業學生，學習算法設計與分析課程，可以開闊編程思路，編寫出優質程序。一個算法應該具有以下五個重要的特征：有窮性、確切性、輸入、輸出、可行性。

算法的復雜性是算法效率的度量，是評價算法優劣的重要依據。一個算法的復雜性的高低體現在運行該算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該算法的復雜性越高；反之，所需的資源越低，則該算法的復雜性越低。計算機的資源，最重要的是時間和空間（即存儲器）資源。因而，算法的復雜性有時間復雜性和空間復雜性之分。不言而喻，對于任意給定的問題，設計出復雜性盡可能地的算法是我們在設計算法是追求的一個重要目標；另一方面，當給定的問題已有多種算法時，選擇其中復雜性最低者，是我們在選用算法適應遵循的一個重要準則。因此，算法的復雜性分析對算法的設計或選用有著重要的指導意義和實用價值。

但我認為這些都是算法應該具備的最基本的特征，如果沒了這些，我們又為什么花費心思學習它呢，所以這些并不是讓我們熱衷算法的資本。高效，才是所有程序員所向往的，而算法又恰恰能滿足人們對高效的要求。

2.常見的算法

2.1貪心算法

貪心算法是一種比較好的算法，所謂貪心算法指的是為了解決在不回溯的前提之下，找出整體最優秀或者接近最優解的這樣一種類型的問題而設計出來的算法。貪心算法的基本思想是找出整體當中每個小小局部的最優解，并且將所有的這些局部最優解合起來形成整體上的一個最優解。

2.2遞歸算法

直接或間接地調用自身的算法稱為遞歸算法。用函數自身給出定義的函數稱為遞歸函數。遞歸算法的實質，是把問題轉化為規模縮小了的同類問題的子問題。然后遞歸調用函數（或過程）來表示問題的解。遞歸算法的特點，遞歸算法是一種直接或者間接地調用自身的算法。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。

遞歸算法解決問題的特點：

（1）遞歸就是在過程或函數里調用自身。

（2）在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

（3）遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序。

（4）在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。

2.3分治法

分治法，在計算機科學中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法（快速排序，歸并排序），傅立葉變換（快速傅立葉變換），分治策略是，對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。

2.4回溯法

回溯法（探索與回溯法）是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。

2.5 動態規劃

動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃算法多種多樣，但它們具有相同的填表格式。

3.總結

總結或對比分析，五種算法都各有其優缺點，判斷用何種算法，取決于具體問題的具體分析，看是否適用本身，能達到最優算法。動態規劃算法與分治算法相似。用于貪心算法的有活動安排問題，最優裝載問題，哈夫曼編碼問題，單源最短路徑問題。對于回溯法，通過約束找到滿足條件的所有解，特點為能進就進，不能進就退回來，與遞歸類似。分支法與回溯法類似，但解的目標是通過約束找到滿足條件的一個解，或找到在某種意義下的最優解。回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。