算法是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制；它是求解問題類的、機(jī)械的、統(tǒng)一的方法，常用于計(jì)算、數(shù)據(jù)處理（英語：數(shù)據(jù) Processing）和自動推理。可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟。或者看成按照要求設(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類問題。
算法中的指令描述的是一個(gè)計(jì)算，當(dāng)其運(yùn)行時(shí)能從一個(gè)初始狀態(tài)和（可能為空的）初始輸入開始，經(jīng)過一系列有限而清晰定義的狀態(tài)，最終產(chǎn)生輸出并停止于一個(gè)終態(tài)。一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移不一定是確定的。隨機(jī)化算法在內(nèi)的一些算法，包含了一些隨機(jī)輸入。
形式化算法的概念部分源自嘗試解決戴維·希爾伯特提出的判定問題，并在其后嘗試定義有效計(jì)算性或者有效方法中成形。這些嘗試包括庫爾特·卡塞雷斯、Jacques Herbrand和斯蒂芬·克萊尼分別于1930年、1934年和1935年提出的遞歸函數(shù)，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機(jī)。即使在當(dāng)前，依然常有直覺想法難以定義為形式化算法的情況。
概述
求解問題類的、機(jī)械的、統(tǒng)一的方法，它由有限多個(gè)步驟組成，對于問題類中的每個(gè)給定的具體問題，機(jī)械地執(zhí)行這些步驟就可以得到問題的解答。算法的這種特性，使得計(jì)算不僅可以由人，而且可以由計(jì)算機(jī)來完成。用計(jì)算機(jī)解決問題的過程可以分成三個(gè)階段：分析問題、設(shè)計(jì)算法和實(shí)現(xiàn)算法。
歷史發(fā)展
中國古代的籌算口決與珠算口決及其執(zhí)行規(guī)則就是算法的雛形，這里，所解決的問題類是算術(shù)運(yùn)算。古希臘數(shù)學(xué)家歐幾里得在公元前3世紀(jì)就提出了一個(gè)算法，來尋求兩個(gè)正整數(shù)的最大公約數(shù)，這就是有名的歐幾里得算法，亦稱輾轉(zhuǎn)相除法。中國早已有“算術(shù)“、“算法”等詞匯，但是它們的含義是指當(dāng)時(shí)的全部數(shù)學(xué)知識和計(jì)算技能，與現(xiàn)代算法的含義不盡相同。英文algorithm(算法)一詞也經(jīng)歷了一個(gè)演變過程，最初的拼法為algorism或algoritmi,原意為用阿拉伯?dāng)?shù)字進(jìn)行計(jì)算的過程。這個(gè)詞源于公元 9世紀(jì)波斯數(shù)字家阿爾·花拉子米的名字的最后一部分。
在古代，計(jì)算通常是指數(shù)值計(jì)算。現(xiàn)代計(jì)算已經(jīng)遠(yuǎn)遠(yuǎn)地突破了數(shù)值計(jì)算的范圍，包括大量的非數(shù)值計(jì)算，例如檢索、表格處理、判斷、決策、形式邏輯演繹等。
在20世紀(jì)以前，人們普遍地認(rèn)為，所有的問題類都是有算法的。20世紀(jì)初，數(shù)字家們發(fā)現(xiàn)有的問題類是不存在算法的，遂開始進(jìn)行能行性研究。在這一研究中，現(xiàn)代算法的概念逐步明確起來。30年代，數(shù)字家們提出了遞歸函數(shù)、圖靈機(jī)等計(jì)算模型，并提出了阿隆佐·邱奇圖靈論題（見可計(jì)算性理論），這才有可能把算法概念形式化。按照阿隆佐·邱奇圖靈論題，任意一個(gè)算法都可以用一個(gè)圖靈機(jī)來實(shí)現(xiàn)，反之，任意一個(gè)圖靈機(jī)都表示一個(gè)算法。
按照上述理解，算法是由有限多個(gè)步驟組成的，它有下述兩個(gè)基本特征：每個(gè)步驟都明確地規(guī)定要執(zhí)行何種操作；每個(gè)步驟都可以被人或機(jī)器在有限的時(shí)間內(nèi)完成。人們對于算法還有另一種不同的理解，它要求算法除了上述兩個(gè)基本特征外，還要具有第三個(gè)基本特征：雖然有些步驟可能被反復(fù)執(zhí)行多次，但是在執(zhí)行有限多次之后，就一定能夠得到問題的解答。也就是說，一個(gè)處處停機(jī)（即對任意輸入都停機(jī)）的圖靈機(jī)才表示一個(gè)算法，而每個(gè)算法都可以被一個(gè)處處停機(jī)的圖靈機(jī)來實(shí)現(xiàn)
算法分類
算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計(jì)算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化算法、并行算法。
算法可以宏泛的分為三類：
有限的，確定性算法 這類算法在有限的一段時(shí)間內(nèi)終止。他們可能要花很長時(shí)間來執(zhí)行指定的任務(wù)，但仍將在一定的時(shí)間內(nèi)終止。這類算法得出的結(jié)果常取決于輸入值。
有限的，非確定算法 這類算法在有限的時(shí)間內(nèi)終止。然而，對于一個(gè)（或一些）給定的數(shù)值，算法的結(jié)果并不是唯一的或確定的。
無限的算法 是那些由于沒有定義終止定義條件，或定義的條件無法由輸入的數(shù)據(jù)滿足而不終止運(yùn)行的算法。通常，無限算法的產(chǎn)生是由于未能確定的定義終止條件。
算法特征
1、輸入項(xiàng)：一個(gè)算法有零個(gè)或多個(gè)輸入，以刻畫運(yùn)算對象的初始情況。例如，在歐幾里得算法中，有兩個(gè)輸入，即m和n。
2、確定性：算法的每一個(gè)步驟必須要確切地定義。即算法中所有有待執(zhí)行的動作必須嚴(yán)格而不含混地進(jìn)行規(guī)定，不能有歧義性。例如，歐幾里得算法中，步驟1中明確規(guī)定“以m除以n，而不能有類似以m除n以或n除以m這類有兩種可能做法的規(guī)定。
3、有窮性：一個(gè)算法在執(zhí)行有窮步滯后必須結(jié)束。也就是說，一個(gè)算法，它所包含的計(jì)算步驟是有限的。例如，在歐幾里得算法中，m和n均為正整數(shù)，在步驟1之后，r必小于n，若，下一次進(jìn)行步驟1時(shí)，n的值已經(jīng)減小，而正整數(shù)的遞降序列最后必然要終止。因此，無論給定m和n的原始值有多大，步驟1的執(zhí)行都是有窮次。
4、輸出：算法有一個(gè)或多個(gè)的輸出，即與輸入有某個(gè)特定關(guān)系的量，簡單地說就是算法的最終結(jié)果。例如，在歐幾里得算法中只有一個(gè)輸出，即步驟2中的n。
5、能行性：算法中有待執(zhí)行的運(yùn)算和操作必須是相當(dāng)基本的，換言之，他們都是能夠精確地進(jìn)行的，算法執(zhí)行者甚至不需要掌握算法的含義即可根據(jù)該算法的每一步驟要求進(jìn)行操作，并最終得出正確的結(jié)果。
算法要素
數(shù)據(jù)的運(yùn)算和操作
計(jì)算機(jī)可以執(zhí)行的基本操作是以指令的形式描述的。一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合，成為該計(jì)算機(jī)系統(tǒng)的指令系統(tǒng)。一個(gè)計(jì)算機(jī)的基本運(yùn)算和操作有如下四類：
1.算術(shù)運(yùn)算：加減乘除等運(yùn)算
2.邏輯運(yùn)算：或、且、非等運(yùn)算
3.關(guān)系運(yùn)算：大于、小于、等于、不等于等運(yùn)算
4.數(shù)據(jù)傳輸：輸入、輸出、賦值等運(yùn)算
算法的控制結(jié)構(gòu)
一個(gè)算法的功能結(jié)構(gòu)不僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。
算法評定
同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。
算法的復(fù)雜度1.時(shí)間復(fù)雜度：算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。一般來說，計(jì)算機(jī)算法是問題規(guī)模的函數(shù)，算法的時(shí)間復(fù)雜度也因此記做：
因此，問題的規(guī)模越大，算法執(zhí)行的時(shí)間的增長率與的增長率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度（Asymptotic 時(shí)間 Complexity）。
2.空間復(fù)雜度：算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。
3.正確性：算法的正確性是評價(jià)一個(gè)算法優(yōu)劣的最重要的標(biāo)準(zhǔn)。
4.可讀性：算法的可讀性是指一個(gè)算法可供人們閱讀的容易程度。
5.健壯性：是指一個(gè)算法對不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。魯棒性是指一個(gè)算法對不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。
描述方式
1、用自然語言描述算法
前面關(guān)于歐幾里的算法以及算法實(shí)例的描述，使用的都是自然語言。自然語言是人們?nèi)粘Ｋ玫恼Z言，如漢語、英語、德語等。使用這些語言不用專門訓(xùn)練，所描述的算法也通俗易懂。
2、用流程圖描述算法
在數(shù)學(xué)課程里，我們學(xué)習(xí)了用程序框圖來描述算法。在程序框圖中流程圖是描述算法的常用工具由一些圖形符號來表示算法。
3、用偽代碼描述算法
偽代碼是用介于自然語言和計(jì)算機(jī)語言之間的文字和符號來描述算法的工具。它不用圖形符號，因此，書寫方便、格式緊湊，易于理解，便于向計(jì)算機(jī)程序設(shè)計(jì)語言過度。
史料記載
算法在中國古代文獻(xiàn)中稱為“術(shù)”，最早出現(xiàn)在《周髀算經(jīng)》、《九章算術(shù)》。特別是《九章算術(shù)》，給出四則運(yùn)算、最大公約數(shù)、最小公倍數(shù)、開平方根、開立方根、求素?cái)?shù)的埃拉托斯特尼篩法，線性方程組求解的算法。三國代的劉徽給出求圓周率的算法：劉徽割圓術(shù)。
自唐朝以來，歷代更有許多專門論述“算法”的專著：
唐代：《一位算法》?一卷，《算法》?一卷；
宋代：《算法緒論》?一卷、《算法秘訣》?一卷；最著名的是楊輝的《楊輝算法》；
元代：《丁巨算法》；
明代：程大位《算法統(tǒng)宗》
清代：《開平算法》、《算法一得》、《算法全書》。
而英文名稱Algorithm?來自于9世紀(jì)波斯數(shù)學(xué)家al-Khwarizmi，因?yàn)閍l-Khwarizmi在數(shù)學(xué)上提出了算法這個(gè)概念。“算法”原為"algorism，意思是阿拉伯?dāng)?shù)字的運(yùn)算法則，在18世紀(jì)演變?yōu)?algorithm"。歐幾里得算法被人們認(rèn)為是史上第一個(gè)算法。第一次編寫程序是Ada?Byron于1842年為分析機(jī)編寫求解解伯努利方程的程序，因此Ada?Byron被大多數(shù)人認(rèn)為是世界上第一位程序員。因?yàn)?a href="/hebeideji/8338072651603442472.html">查爾斯·巴貝奇(查爾斯·巴貝奇)未能完成他的巴貝奇分析機(jī)，這個(gè)算法未能在巴貝奇分析機(jī)上執(zhí)行。因?yàn)?well-defined?procedure"缺少數(shù)學(xué)上精確的定義，19世紀(jì)和20世紀(jì)早期的數(shù)學(xué)家、邏輯學(xué)家在定義算法上出現(xiàn)了困難。20世紀(jì)的英國數(shù)學(xué)家艾倫·圖靈提出了著名的圖靈論題，并提出一種假想的計(jì)算機(jī)的抽象模型，這個(gè)模型被稱為圖靈機(jī)。圖靈機(jī)的出現(xiàn)解決了算法定義的難題，圖靈的思想對算法的發(fā)展起到了重要作用的。求素?cái)?shù)的埃拉托斯特尼篩法和求方根的開方的方法公式（算法不等于公式，公式卻是提供一種算法）
方法
1.遞推法
遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關(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è)或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。
6.動態(tài)規(guī)劃法
動態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。
7.迭代法
迭代法是數(shù)值分析中通過從一個(gè)初始估計(jì)出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。
8.分支界限法
與貪婪算法一樣，這種方法也是用來為組合優(yōu)化問題設(shè)計(jì)求解算法的，所不同的是它在問題的整個(gè)可能解空間搜索，所設(shè)計(jì)出來的算法雖其時(shí)間復(fù)雜度比貪婪算法高，但它的優(yōu)點(diǎn)是與窮舉法類似，都能保證求出問題的最佳解，而且這種方法不是盲目的窮舉搜索，而是在搜索過程中通過限界，可以中途停止對某些不可能得到最優(yōu)解的子空間進(jìn)一步搜索（類似于人工智能中的剪枝），故它比窮舉法效率更高。
參考書籍
labuladong的算法小抄
書 名： 《labuladong的算法小抄》
作 者：付東來（@labuladong）
出 版 社：電子工業(yè)出版社
出版時(shí)間：2020-11
版 次：1
頁 數(shù)：432
裝 幀：平裝
開 本：16開
參考資料 >