避不開(kāi)的算法，如何吃透？
當(dāng)你使用搜索引擎（例如Google Chrome、Mozilla Firefox等）的時(shí)候，后臺(tái)發(fā)生了什么？當(dāng)你詢問(wèn)虛擬助手（例如Alexa、Google助手或Siri）的時(shí)候，后臺(tái)發(fā)生了什么？它們?cè)趺磿?huì)知道答案？為何它們會(huì)顯示正確答案？所有這些都要感謝算法。
每當(dāng)你使用手機(jī)、計(jì)算機(jī)、筆記本電腦或計(jì)算器時(shí)，其實(shí)都在使用算法。
那么，什么是算法？
如果你想做數(shù)學(xué)運(yùn)算，比如說(shuō)兩個(gè)數(shù)字相乘（不使用任何電子設(shè)備），那么你需要在紙上做乘法。你按照一定的規(guī)則獲得正確的答案。你也可以使用耗時(shí)更少的方法來(lái)做計(jì)算。這就是算法。
算法是為執(zhí)行特定的任務(wù)而設(shè)計(jì)的一組指令。
有些算法很簡(jiǎn)單，而有些則非常復(fù)雜，具體取決于你要實(shí)現(xiàn)的目標(biāo)。
算法的歷史
了解歷史總是有好處，因?yàn)闅v史可以幫助你更好地理解主題，并了解何時(shí)使用這些知識(shí)。
“算法”一詞源自九世紀(jì)波斯數(shù)學(xué)家Muhammad Ibn Musa Al-Khwarizmi（代數(shù)之父），拉丁語(yǔ)為Algoritmi。最初算法被稱(chēng)為Algorismus。15世紀(jì)后期，改名為Algorithmus（源自希臘語(yǔ)Arithmetic）?，F(xiàn)代英語(yǔ)中的Algorithm一詞是于19世紀(jì)引入的。
算法在中國(guó)古代文獻(xiàn)中稱(chēng)為“術(shù)”，最早出現(xiàn)在《周髀算經(jīng)》、《九章算術(shù)》。特別是《九章算術(shù)》，給出四則運(yùn)算、最大公約數(shù)、最小公倍數(shù)、開(kāi)平方根、開(kāi)立方根、求素?cái)?shù)的埃拉托斯特尼篩法，線性方程組求解的算法。三國(guó)時(shí)代的劉徽給出求圓周率的算法：劉徽割圓術(shù)。
1842年，Ada Lovelace首次編寫(xiě)了計(jì)算引擎的算法，因此許多人常常稱(chēng)她為世界上第一位計(jì)算機(jī)程序員。她為巴貝奇分析機(jī)（自動(dòng)計(jì)算的機(jī)械計(jì)算機(jī)）編寫(xiě)了求解伯努利微分方程的算法（巴貝奇分析機(jī)由計(jì)算機(jī)之父Charles Babbage開(kāi)發(fā)）。
1936年，Alan Turing的圖靈機(jī)首次提出了第一個(gè)以現(xiàn)代形式表示的算法。
如何表達(dá)算法？
表達(dá)算法的方法多種多樣，例如自然語(yǔ)言、偽代碼、流程圖、編程語(yǔ)言、動(dòng)態(tài)圖表、控制表等等。
使用自然語(yǔ)言表達(dá)算法不夠清晰，因此很少用于復(fù)雜或技術(shù)算法。偽代碼、流程圖、drakon圖和控制表是表達(dá)算法的結(jié)構(gòu)化方法，因?yàn)榕c自然語(yǔ)言相比，它們可以避免許多歧義。編程語(yǔ)言旨在以可由計(jì)算機(jī)執(zhí)行的形式表達(dá)算法。
在計(jì)算機(jī)系統(tǒng)中，算法是由軟件開(kāi)發(fā)人員以他們選擇的任何編程語(yǔ)言編寫(xiě)的邏輯。但是，在設(shè)計(jì)算法時(shí)，我們需要記住一些規(guī)則。其中包括：
- 輸入：算法至少需要一個(gè)或多個(gè)輸入值。如果沒(méi)有給出輸入，那么算法將產(chǎn)生什么輸出呢？
- 輸出：算法至少應(yīng)產(chǎn)生一個(gè)輸出。如果沒(méi)有產(chǎn)生任何結(jié)果，則無(wú)需設(shè)計(jì)算法。
- 效率：算法應(yīng)該保證高效利用計(jì)算和內(nèi)存資源。產(chǎn)生的輸出應(yīng)該又正確又快。
- 簡(jiǎn)單性：算法不應(yīng)過(guò)于復(fù)雜。
- 可擴(kuò)展性：算法必須能夠在不更改核心邏輯的情況下進(jìn)行擴(kuò)展。
- 有限性：算法必須在有限步驟后終止。假設(shè)輸入錯(cuò)誤的情況下，算法在第一步就終止，我們將永遠(yuǎn)無(wú)法得知算法有什么問(wèn)題。而且，算法也不能陷入無(wú)限循環(huán)。
- 不依賴于編程語(yǔ)言：算法必須與語(yǔ)言無(wú)關(guān)，也就是說(shuō)，它必須是可以用任何一種語(yǔ)言都可以實(shí)現(xiàn)的簡(jiǎn)單指令，但是無(wú)論任何語(yǔ)言，輸出都應(yīng)當(dāng)相同。
下面，我們來(lái)構(gòu)建一個(gè)簡(jiǎn)單的算法：兩個(gè)數(shù)字的加法（且滿足上述要求）。
- 第1步：開(kāi)始；
- 第2步：聲明變量num1，num2和sum；
- 第3步：讀取值num1和num2；
- 第4步：將num1和num2相加，然后將值賦給sum。
- 第5步：顯示和；
- 第6步：停止。
下面，為了測(cè)試這個(gè)算法，我們使用一種編程語(yǔ)言來(lái)實(shí)現(xiàn)它，我選擇用Java語(yǔ)言來(lái)實(shí)現(xiàn)，你可以任意選擇其他語(yǔ)言。
- public class Addition
- {
- public static void main(String[] args) {
- int num1, num2, sum;
- Scanner sc = new Scanner(System.in);
- System.out.println(“Enter First Number: “);
- num1 = sc.nextInt;
- System.out.println(“Enter Second Number: “);
- num2 = sc.nextInt;
- sc.close;
- sum = num1 + num2;
- System.out.println(“Sum of two numbers: “+sum);
- }
- }
輸出如下：
我們的算法運(yùn)作良好，且滿足上述要求。
算法必須高效。算法的效率取決于時(shí)間和空間。一個(gè)好的算法占用的時(shí)間更少，占用的空間也更少，我們無(wú)法時(shí)刻兼顧兩者。如果減少時(shí)間，則則空間可能會(huì)增加，反之亦然。因此，我們必須妥協(xié)一方。算法的空間復(fù)雜度表示算法運(yùn)行時(shí)占用或需要的總空間。時(shí)間復(fù)雜度是指算法花完成任務(wù)所需的操作數(shù)。以最少操作數(shù)執(zhí)行任務(wù)的算法就是最有效的算法。此外，算法花費(fèi)的時(shí)間還取決于計(jì)算機(jī)的計(jì)算速度，但是在我們考慮算法的效率率時(shí)，通常不會(huì)考慮這些外部因素。衡量算法效率的一種方法是測(cè)量算法在不同輸入下找到答案所需的操作次數(shù)。
算法的種類(lèi)
- 遞歸算法：通過(guò)重復(fù)將問(wèn)題分解為同類(lèi)的子問(wèn)題而解決問(wèn)題。
- 分治算法：把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。
- 動(dòng)態(tài)規(guī)劃算法（又名動(dòng)態(tài)優(yōu)化算法）：記住過(guò)去的結(jié)果，以備將來(lái)使用。與分治算法相似，這種算法可以將復(fù)雜的問(wèn)題分解相對(duì)簡(jiǎn)單的子問(wèn)題，然后將解決方案保存起來(lái)，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接使用，而無(wú)需再次重新計(jì)算。
- 貪婪算法：在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望得出結(jié)果是最好或最優(yōu)的算法。該算法不能保證最終獲得最佳解決方案。
- 暴力算法：簡(jiǎn)單明了，嘗試所有的可能性，直到找到滿意的解決方案為止。
- 回溯算法：嘗試分步地去解決一個(gè)問(wèn)題。如果發(fā)現(xiàn)其中某一步的解決方案失敗，則后退一步或幾步，重新開(kāi)始尋找解決方案。
如今，幾乎每個(gè)領(lǐng)域都使用算法，例如數(shù)據(jù)科學(xué)、機(jī)器學(xué)習(xí)、農(nóng)業(yè)、科學(xué)、運(yùn)輸?shù)取Ｋ惴ㄊ敲總€(gè)應(yīng)用程序（Google Chrome與Mozilla Firefox、Uber與Ola）最大的不同之處，例如Google Chrome和Mozilla Firefox都是搜索引擎應(yīng)用程序，它們提供相同的結(jié)果，但是結(jié)果的順序有所不同，這是因?yàn)槎呤褂昧瞬煌呐判蛩惴?。Google的排序算法與Firefox不同。
算法無(wú)處不在，并將繼續(xù)傳播，算法讓我們的生活更加輕松，但我們還需要考慮一些問(wèn)題，例如，
- 當(dāng)有一天數(shù)據(jù)和預(yù)測(cè)模型統(tǒng)治世界，那么我們就會(huì)喪失人性和判斷力。
- 隨著更智能、更高效的算法逐步取代許多的人類(lèi)活動(dòng)，失業(yè)人數(shù)將上升。
21世紀(jì)，算法就像魔術(shù)一樣，我們可以解釋其背后的原理以及如何創(chuàng)建網(wǎng)絡(luò)等，卻無(wú)法機(jī)械地解釋為什么這些算法會(huì)產(chǎn)生特定的輸出。而這僅僅是個(gè)開(kāi)始。
