什么是算法？

1. 什么是算法

說(shuō)實(shí)話，這個(gè)問(wèn)題確實(shí)比較難以回答，我們先來(lái)看下百度百科對(duì)算法的定義：

算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問(wèn)題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制

簡(jiǎn)單點(diǎn)說(shuō)算法就是解決一個(gè)問(wèn)題的步驟或者方法。比如針對(duì)去上班這個(gè)問(wèn)題，我們的步驟是這樣：

首先是出門走路到地鐵站，然后坐地鐵到里公司最近的地鐵口下，最后走路到公司。這樣一個(gè)過(guò)程，可以稱之為完成這個(gè)上班任務(wù)的一個(gè)算法。但是很明顯，去上班的算法有很多種，并不止坐地鐵這一種，我們可以打的去公司、坐公交去公司等等，這樣不同的步驟也對(duì)應(yīng)著不同的算法。這些方式有好又有壞，有快也有慢，同樣算法也是一樣有好有壞有快有慢的。同一個(gè)問(wèn)題，有多種解決方法，也就是多種算法，不同的算法之間也會(huì)好壞之分。

但是不管算法如何定義，它一定要具備以下五個(gè)特征才能稱之為算法：

• 有窮性：算法必須能在有限步驟之后終止。無(wú)窮無(wú)盡執(zhí)行下去，那根本不是解決問(wèn)題的辦法，也就不能稱之為解決該問(wèn)題的方法；
• 確切性：算法的每一步必須要有確定的含義；
• 輸入項(xiàng)：算法需要有輸入或者說(shuō)初始條件。比如我們上班的算法，我們的初始條件就是從家出發(fā)；
• 輸出項(xiàng)：算法必須要有一個(gè)或者多個(gè)輸出。比如我們上班的算法，輸出項(xiàng)就是順利到達(dá)公司；
• 可行性：算法必須是可以實(shí)現(xiàn)的步驟。那種天馬行空、無(wú)法實(shí)現(xiàn)的方法就不能稱之為算法了。如果坐著宇宙飛碟去上班，這顯然不切實(shí)際，當(dāng)然也就不能成為之上班的一個(gè)算法了。

2. 為什么要學(xué)習(xí)算法

有人問(wèn)在大部分的工作場(chǎng)景下我們都用不到算法，那么我們?yōu)槭裁催€要學(xué)習(xí)算法呢？首先，需要明確以下幾個(gè)問(wèn)題：

• 工作中用不到并不代表工作中沒(méi)有用到；
• 工作中不常用并不代表面試不?？?；

學(xué) Java 的同學(xué)幾乎天天都在用 HashMap 吧？但是大家有思考過(guò)存儲(chǔ)在 HashMap 中 key 和 value 值是究竟用什么數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的？當(dāng)使用 get() 方法查找 value 時(shí)用的什么算法？

但是我們一般是不會(huì)考慮這種問(wèn)題的，因?yàn)檫@些工作都由編程語(yǔ)言給我們已經(jīng)封裝好了，我們只需要調(diào)用，調(diào)用，再調(diào)用！

那么對(duì)于 Python 也是一樣的，我們用的 dict 等類型，它背后都是 Python 解釋器給我們做了大量工作，實(shí)現(xiàn)了各種各樣復(fù)雜的算法，給我們的使用帶來(lái)了極大的方便，也導(dǎo)致我們大部分程序員似乎在工作中幾乎看不到算法的應(yīng)用？

但是，不要忘了，我們是要追求進(jìn)步的，如果你只是滿足于調(diào)用各種 API 和方法來(lái)完成工作的話這個(gè)教程對(duì)你的意義不大。不過(guò)總會(huì)有現(xiàn)有的方法滿足不了的業(yè)務(wù)場(chǎng)景，到那時(shí)候你該怎么辦呢？

此外，算法同樣是大廠最喜歡拿來(lái)考察候選人員能力的一個(gè)方式。社招中最喜歡考察算法編程能力公司的當(dāng)屬今日頭條，許多國(guó)外的互聯(lián)網(wǎng)公司如微軟、Facebook 等甚至?xí)屇阒苯邮謱懘a。

除此以外，掌握一定的算法基礎(chǔ)有以下幾個(gè)好處：

• 鍛煉自己的思維和編程能力：保持解決問(wèn)題的能力，這在工作中也是非常重要的一項(xiàng)技能；
• 在面試中存在一定競(jìng)爭(zhēng)力：優(yōu)秀的編程者往往都是被大廠爭(zhēng)奪的對(duì)象；
• 在學(xué)習(xí)一些編程語(yǔ)言源碼或者操作系統(tǒng)源碼時(shí)會(huì)有深刻體會(huì)；

3. 如何學(xué)習(xí)算法？

學(xué)習(xí)基礎(chǔ)算法的方法也很簡(jiǎn)單，就是刷題、刷題、理解后再刷題。刷題網(wǎng)站最出名的當(dāng)屬 leetcode，接下來(lái)是國(guó)內(nèi)知名的就是牛客網(wǎng)了。如果對(duì)自己要求高，可以考慮刷 ACM 編程題，比較有名的有 POJ、ZOJ。當(dāng)你能獨(dú)立刷完上面的題目時(shí)，你已經(jīng)是一名非常厲害的算法高手了，不過(guò)刷題也會(huì)耗費(fèi)大量的業(yè)余時(shí)間，要懂得適可而止，享受生活。

4. 算法的評(píng)價(jià)標(biāo)準(zhǔn)

一個(gè)算法優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)主要有兩個(gè)：時(shí)間復(fù)雜度和空間復(fù)雜度。

4.1 時(shí)間復(fù)雜度

程序的運(yùn)行時(shí)間往往有多方面因素綜合決定，即使是同一種算法，不同的輸入對(duì)應(yīng)的運(yùn)行時(shí)間可能也不相同。為針對(duì)運(yùn)行時(shí)間建立一種可行、可信的評(píng)估標(biāo)準(zhǔn)，我們往往考慮輸入數(shù)據(jù)的規(guī)模，這是最關(guān)鍵的因素。

通常情況下，問(wèn)題的規(guī)模越接近，相應(yīng)的計(jì)算成本也會(huì)很接近；而隨著問(wèn)題的規(guī)模擴(kuò)大，相應(yīng)的執(zhí)行時(shí)間也會(huì)加長(zhǎng)。因此，隨著輸入規(guī)模的擴(kuò)大，算法的執(zhí)行時(shí)間將如何增長(zhǎng)，緩慢增長(zhǎng)？線性增長(zhǎng)，還是指數(shù)級(jí)增長(zhǎng)？我們可以將算法的執(zhí)行時(shí)間和問(wèn)題的規(guī)模相互映射，得到了一個(gè)關(guān)于輸入規(guī)模的函數(shù)，這個(gè)就可以稱為該算法的時(shí)間復(fù)雜度。

4.2 空間復(fù)雜度

空間復(fù)雜度類似，我們將問(wèn)題的規(guī)模和算法所需的存儲(chǔ)空間一一映射，得到的函數(shù)稱之為空間復(fù)雜度。就目前業(yè)界而言，由于存儲(chǔ)本身的廉價(jià)性，算法工程師們大多將算法的優(yōu)化集中在時(shí)間復(fù)雜度上，所以往往將時(shí)間復(fù)雜度當(dāng)做衡量一個(gè)算法好壞的標(biāo)準(zhǔn)。當(dāng)然時(shí)間復(fù)雜度低且空間復(fù)雜度也低的算法是最好的選擇，但是往往二者不能得兼，很多問(wèn)題也需要具體情況具體分析。

5. 本教程學(xué)習(xí)基礎(chǔ)

本教程只需要簡(jiǎn)單的 Python 基礎(chǔ)即可，沒(méi)有其他的任何要求。主要是能理解一些解決問(wèn)題的方法，比如遞歸、動(dòng)態(tài)規(guī)劃，需要一些抽象的思考能力。

6. 小結(jié)

今天我們簡(jiǎn)單介紹了下算法的概念以及為什么要學(xué)習(xí)算法進(jìn)行了介紹。最后討論了下算法的一般評(píng)價(jià)標(biāo)準(zhǔn)，主要是通過(guò)時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行衡量。今天的算法介紹就到這里了，下一節(jié)就開始算法實(shí)戰(zhàn)以及相應(yīng)的編程訓(xùn)練了，祝大家學(xué)習(xí)愉快。