計(jì)算機(jī)算法概述

【摘要】本文在分析算法定義的基礎(chǔ)上，對常見的５種算法進(jìn)行論述并總結(jié)各自算法的特點(diǎn)。

【關(guān)鍵詞】算法定義常見算法

隨著計(jì)算機(jī)技術(shù)的突飛猛進(jìn)，算法逐漸成為了核心內(nèi)容，不容忽視。算法更能體現(xiàn)計(jì)算機(jī)的精髓，計(jì)算機(jī)技術(shù)的根本，算法的設(shè)計(jì)有多種方案，不同的實(shí)現(xiàn)方案展現(xiàn)的結(jié)果不同，這提現(xiàn)了計(jì)算機(jī)技術(shù)的多姿多彩。對于計(jì)算機(jī)技術(shù)來說，算法分析與設(shè)計(jì)是至關(guān)重要的。在一個(gè)大型軟件系統(tǒng)的開發(fā)中，設(shè)計(jì)出有效的算法將起到?jīng)Q定性的作用。

１.定義

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

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

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

2.常見的算法

2.1貪心算法

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

2.2遞歸算法

直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。遞歸算法的實(shí)質(zhì)，是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)（或過程）來表示問題的解。遞歸算法的特點(diǎn)，遞歸算法是一種直接或者間接地調(diào)用自身的算法。在計(jì)算機(jī)編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。

遞歸算法解決問題的特點(diǎn)：

（1）遞歸就是在過程或函數(shù)里調(diào)用自身。

（2）在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。

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

（4）在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。

2.3分治法

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

2.4回溯法

回溯法（探索與回溯法）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。

2.5 動(dòng)態(tài)規(guī)劃

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

3.總結(jié)

總結(jié)或?qū)Ρ确治?，五種算法都各有其優(yōu)缺點(diǎn)，判斷用何種算法，取決于具體問題的具體分析，看是否適用本身，能達(dá)到最優(yōu)算法。動(dòng)態(tài)規(guī)劃算法與分治算法相似。用于貪心算法的有活動(dòng)安排問題，最優(yōu)裝載問題，哈夫曼編碼問題，單源最短路徑問題。對于回溯法，通過約束找到滿足條件的所有解，特點(diǎn)為能進(jìn)就進(jìn)，不能進(jìn)就退回來，與遞歸類似。分支法與回溯法類似，但解的目標(biāo)是通過約束找到滿足條件的一個(gè)解，或找到在某種意義下的最優(yōu)解?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。