2.1 算法的概念

2.1.1 算法的定義

算法（Algorithm）描述的是解決某個(gè)問題的完整步驟，可以理解為一系列的指令，也可以理解為一種系統(tǒng)的策略機(jī)制。也就是說，當(dāng)輸入符合一定規(guī)范的時(shí)候，算法能用有限的時(shí)間、有限的空間或一定的效率獲得所要求的輸出。在數(shù)學(xué)中，解決一個(gè)問題的有限的順序排列的運(yùn)算步驟組成了一個(gè)算法。類比數(shù)學(xué)思想，在計(jì)算機(jī)中，解決一個(gè)問題的有限的順序排列的指令可以稱為一個(gè)算法。算法中的指令描述的是計(jì)算過程，當(dāng)運(yùn)行一個(gè)算法時(shí)，計(jì)算機(jī)將從初始狀態(tài)開始，經(jīng)過有限且明確的指令，產(chǎn)生輸出并停止運(yùn)行。

2.1.2 算法的特征

一般來說，對(duì)于一個(gè)算法，有5個(gè)重要的特征：輸入項(xiàng)（Input）、輸出項(xiàng)（Output）、確定性（Definiteness）、可行性（Finiteness）和有窮性（Effectiveness）^[1]，見表2-1。

2.1.3 算法的評(píng)價(jià)

由于同一個(gè)問題可以用不同的算法解決，因此往往需要根據(jù)具體的要求選擇合適的算法，這就要對(duì)算法進(jìn)行評(píng)價(jià)，主要的評(píng)價(jià)依據(jù)為時(shí)間復(fù)雜度（Time Complexity）和空間復(fù)雜度（Space Complexity）。

1.時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度是一個(gè)能夠定性描述算法運(yùn)行時(shí)間的函數(shù)，也可以把它看作一個(gè)關(guān)于問題規(guī)模的函數(shù)，常用符號(hào)O表示。一般來說，問題的規(guī)模越大，算法執(zhí)行的指令越多，時(shí)間越長，則算法的時(shí)間復(fù)雜度越大^[2]。

例如，計(jì)算下列代碼的時(shí)間復(fù)雜度。

具體的計(jì)算過程見表2-2。

由表2-2可知，上述代碼的時(shí)間復(fù)雜度為O（n³）。

2.空間復(fù)雜度

算法的空間復(fù)雜度是度量該算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間大小的度量函數(shù)，問題的規(guī)模越大，算法的空間復(fù)雜度也越大。空間復(fù)雜度的表示符號(hào)與時(shí)間復(fù)雜度相同，都用O表示。

除了時(shí)間復(fù)雜度和空間復(fù)雜度，還可以用正確性、可讀性、容錯(cuò)性等指標(biāo)評(píng)價(jià)一個(gè)算法，對(duì)算法進(jìn)行評(píng)估可以在節(jié)約資源的前提下，選擇更合適的算法去解決問題。