算法及其發(fā)展歷程

1、算法及其發(fā)展歷程（資料來源：維基百科）算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟。或者看成按照要求設(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類問題。一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征： 1、有窮性： 一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束； 2、確切性： 算法的每一步驟必

2、須有確切的定義； 3、輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件； 4、輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的； 5、可行性： 算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。計(jì)算機(jī)科學(xué)家尼克勞斯-沃思曾著過一本著名的書數(shù)據(jù)結(jié)構(gòu)十算法= 程序，可見算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。 編輯本段算法的復(fù)雜度同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。時(shí)

3、間復(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）?？臻g復(fù)雜度算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。詳見百度百科詞條算法復(fù)雜度 編輯本段算法設(shè)計(jì)與分析的基本方法1.遞推法遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。它把問

4、題分成若干步，找出相鄰幾步的關(guān)系，從而達(dá)到目的，此方法稱為遞推法。2.遞歸遞歸指的是一個(gè)過程：函數(shù)不斷引用自身，直到引用的對象已知3.窮舉搜索法窮舉搜索法是對可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問題的解。4.貪婪法貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。5.分治法把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單

5、的直接求解，原問題的解即子問題的解的合并。6.動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。7.迭代法迭代是數(shù)值分析中通過從一個(gè)初始估計(jì)出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。 編輯本段算法分類算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計(jì)算幾何的算法、圖論的算法、動(dòng)態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化

6、算法、并行算法。算法可以宏泛的分為三類：有限的，確定性算法 這類算法在有限的一段時(shí)間內(nèi)終止。他們可能要花很長時(shí)間來執(zhí)行指定的任務(wù)，但仍將在一定的時(shí)間內(nèi)終止。這類算法得出的結(jié)果常取決于輸入值。有限的，非確定算法 這類算法在有限的時(shí)間內(nèi)終止。然而，對于一個(gè)（或一些）給定的數(shù)值，算法的結(jié)果并不是唯一的或確定的。無限的算法 是那些由于沒有定義終止定義條件，或定義的條件無法由輸入的數(shù)據(jù)滿足而不終止運(yùn)行的算法。通常，無限算法的產(chǎn)生是由于未能確定的定義終止條件。 編輯本段舉例經(jīng)典的算法有很多，如：歐幾里德算法，割圓術(shù)，秦九韶算法。 編輯本段算法經(jīng)典專著目前市面上有許多論述算法的書籍，其中最著名的便是計(jì)算機(jī)程

7、序設(shè)計(jì)藝術(shù)（The Art Of Computer Programming) 以及算法導(dǎo)論（Introduction To Algorithms）。 編輯本段算法的歷史“算法”即演算法的大陸中文名稱出自周髀算經(jīng)；而英文名稱Algorithm 來自于9世紀(jì)波斯數(shù)學(xué)家al-Khwarizmi，因?yàn)閍l-Khwarizmi在數(shù)學(xué)上提出了算法這個(gè)概念?！八惴ā痹瓰閍lgorism，意思是阿拉伯?dāng)?shù)字的運(yùn)算法則，在18世紀(jì)演變?yōu)閍lgorithm。歐幾里得算法被人們認(rèn)為是史上第一個(gè)算法。 第一次編寫程序是Ada Byron于1842年為巴貝奇分析機(jī)編寫求解解伯努利方程的程序，因此Ada Byron被大多數(shù)人認(rèn)為是世界上第一位程序員。因?yàn)椴闋査拱拓惼?Charles Babbage)未能完成他的巴貝奇分析機(jī)，這個(gè)算法未能在巴貝奇分析機(jī)上執(zhí)行。 因?yàn)閣ell-defined procedure缺少數(shù)學(xué)上精確的定義，19世紀(jì)