[科普中國]-程序算法

程序算法特性有窮性

在有限的操作步驟內(nèi)完成。有窮性是算法的重要特性，任何一個(gè)問題的解決不論其采取什么樣的算法，其終歸是要把問題解決好。如果一種算法的執(zhí)行時(shí)間是無限的，或在期望的時(shí)間內(nèi)沒有完成，那么這種算法就是無用和徒勞的，我們不能稱其為算法。

確定性每個(gè)步驟確定，步驟的結(jié)果確定。算法中的每一個(gè)步驟其目的應(yīng)該是明確的，對問題的解決是有貢獻(xiàn)的。如果采取了一系列步驟而問題沒有得到徹底的解決，也就達(dá)不到目的，則該步驟是無意義的。

可行性每個(gè)步驟有效執(zhí)行，得到確定的結(jié)果。每一個(gè)具體步驟在通過計(jì)算機(jī)實(shí)現(xiàn)時(shí)應(yīng)能夠使計(jì)算機(jī)完成，如果這一步驟在計(jì)算機(jī)上無法實(shí)現(xiàn)，也就達(dá)不到預(yù)期的目的，那么這一步驟是不完善的和不正確的，是不可行的。

零個(gè)或多個(gè)輸入從外界獲得信息。算法的過程可以無數(shù)據(jù)輸入，也可以有多種類型的多個(gè)數(shù)據(jù)輸入，需根據(jù)具體的問題加以分析。

一個(gè)或多個(gè)輸出算法得到的結(jié)果就是算法的輸出（不一定就是打印輸出）。算法1的目的是為解決一個(gè)具體問題，一旦問題得以解決，就說明采取的算法是正確的，而結(jié)果的輸出正是驗(yàn)證這一目的的最好方式。2

算法復(fù)雜度同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評價(jià)主要從3時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。

時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。一般來說，計(jì)算機(jī)算法是問題規(guī)模n 的函數(shù)f(n)，算法的時(shí)間復(fù)雜度也因此記做T(n)=Ο(f(n))；因此，問題的規(guī)模n 越大，算法執(zhí)行的時(shí)間的增長率與f(n) 的增長率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度（Asymptotic Time Complexity）。

空間復(fù)雜度算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。