算法(Algorithm)是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量。
算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟。或者看成按照要求設(shè)計好的有限的確切的計算序列，并且這樣的步
驟和序列可以解決一類問題。
一個算法應(yīng)該具有以下五個重要的特征：
1、有窮性： 一個算法必須保證執(zhí)行有限步之后結(jié)束;
2、確切性： 算法的每一步驟必須有確切的定義;
3、輸入：一個算法有0個或多個輸入，以刻畫運(yùn)算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件;
4、輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的;
5、可行性： 算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。
計算機(jī)科學(xué)家尼克勞斯-沃思曾著過一本著名的書《數(shù)據(jù)結(jié)構(gòu)+算法=程序》，可見算法在計算機(jī)科學(xué)界與計算機(jī)應(yīng)用界的地位。
算法的復(fù)雜度
同一問題可用不同算法解決，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個算法的評價主要從時間復(fù)雜度和空間復(fù)雜度來考慮。
時間復(fù)雜度
算法的時間復(fù)雜度是指算法需要消耗的時間資源。一般來說，計算機(jī)算法是問題規(guī)模n 的函數(shù)f(n)，算法的時間復(fù)雜度也因此記做
T(n)=Ο(f(n))
因此，問題的規(guī)模n 越大，算法執(zhí)行的時間的增長率與f(n) 的增長率正相關(guān)，稱作漸進(jìn)時間復(fù)雜度(Asymptotic Time Complexity)。
空間復(fù)雜度
算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計算和表示方法與時間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示。同時間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。
算法設(shè)計與分析的基本方法
1.遞推法
遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關(guān)系，從而達(dá)到目的，此方法稱為遞推法。
2.遞歸
遞歸指的是一個過程：函數(shù)不斷引用自身，直到引用的對象已知
3.窮舉搜索法
窮舉搜索法是對可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問題的解。
4.貪婪法
貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。
5.分治法
把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。
6.動態(tài)規(guī)劃法
動態(tài)規(guī)劃是一種在數(shù)學(xué)和計算機(jī)科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計算機(jī)科學(xué)和工程領(lǐng)域。
7.迭代法
迭代是數(shù)值分析中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題(一般是解方程或者方程組)的過程，為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。
算法分類
算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化算法、并行算法。