作者 謝恩銘，公眾號「程序員聯(lián)盟」（微信號：coderhub）。
轉(zhuǎn)載請注明出處。
原文：http://www.itdecent.cn/p/31d14bd080d4
內(nèi)容簡介
- 引出算法復(fù)雜度的故事
- 兩種算法
- 兩種算法的對比
- 第一部分第三課預(yù)告
1. 引出算法復(fù)雜度的故事
上一課 數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第一課：什么是數(shù)據(jù)結(jié)構(gòu)和算法 中，我們初步認(rèn)識了數(shù)據(jù)結(jié)構(gòu)和算法。
既然我們要開始學(xué)習(xí)算法，就不能不提一下算法復(fù)雜度。
但在我們開始談?wù)撍惴ǖ膹?fù)雜度（Complexity）之前，我希望先給大家講個(gè)小故事。
這個(gè)輕松的小故事可以幫助你之后更好地理解算法復(fù)雜度。
之所以今天的故事標(biāo)題是「小鴨子們?nèi)ヂ眯小?，是因?yàn)槲抑翱戳恕断蛲纳睢?第二季，何老師他們的住房邊上有一個(gè)羊圈，里面有天霸和點(diǎn)點(diǎn)兩只羊，羊圈的邊上是一個(gè)雞窩，雞窩里后來也養(yǎng)了一窩小鴨子。
有幾次，這一窩小鴨子從夾縫里偷溜出雞窩，跑到住房附近的田里的小池子里游泳，甚是可愛。所以我就想到用小鴨子們來做例子。
我們的故事是這樣的：
農(nóng)夫 Oscar 是一個(gè)非常友善的農(nóng)夫，他養(yǎng)了很多只小鴨子（我知道你可能會(huì)在腦海里想象它們長大的樣子，想象北京烤鴨的樣子… 好了，趕緊打住這“邪惡”的念頭）。
農(nóng)夫 Osacr 和這些小鴨子們的關(guān)系很好，它們平時(shí)可以出窩去溜達(dá)，在冬天也可以享用一間帶暖氣的小屋子。但真正讓這些小鴨子們興奮的是：每年夏季最炎熱的時(shí)候，Oscar 會(huì)開著一輛卡車，載著小鴨子們到離家較遠(yuǎn)的山腳下去度假，那里有很多片小池塘。小鴨子們可以在小池塘里覓食、嬉戲，度過愉快的時(shí)光。
出發(fā)之前，農(nóng)夫 Oscar 會(huì)首先在他的大卡車上放入一個(gè)大箱子，再把小鴨子們一只只裝在大箱子里面。大箱子是正方形的，分為一個(gè)一個(gè)隔間，每只小鴨子就臥在一個(gè)小隔間里。長寬各有 N 個(gè)隔間，這里的 N 是一個(gè)我們暫時(shí)還不知道的數(shù)。池塘的數(shù)目也是 N。
但是問題來了：在度假的時(shí)候，小鴨子們是有要求的，每只小鴨子都跟 Oscar 說它們想要遠(yuǎn)離喧囂，盡量到比較清凈（鴨子數(shù)目少一些）的池塘里去。
2. 兩種算法
以往的每年，農(nóng)夫 Oscar 不想費(fèi)腦子，所以他是這么做的：
到達(dá)目的地之后，Oscar 把卡車停在那一片池塘（池塘數(shù)目是 N）附近，從卡車上下來，打開后車門，從那一箱子小鴨子里捧出一只來，然后問它：“你想去哪一個(gè)池塘？” 。一旦小鴨子選定了一個(gè)池塘，Oscar 就跑到那個(gè)池塘，把小鴨子放進(jìn)去。
第一只小鴨子被放到想去的池塘之后，Oscar 跑回卡車，接著問第二只小鴨子它想選擇哪個(gè)池塘。
因?yàn)橐呀?jīng)有一只小鴨子選了其中一個(gè)池塘，既然這些小鴨子都希望去鴨少更清凈的池塘，所以第二只小鴨子肯定會(huì)選一個(gè)還沒有小鴨子在其中的池塘，然后 Oscar 又是一頓小跑。
Oscar 就以這樣的方式接著問下一只小鴨子，并把每只小鴨子都放到它們想去的池塘。
N 個(gè)池塘已經(jīng)漸漸開始被小鴨子們占據(jù)。一旦有池塘里面的鴨子數(shù)比其他池塘少，那么小鴨子就會(huì)選擇這個(gè)池塘。顯然，小鴨子進(jìn)去后，這個(gè)池塘的鴨子數(shù)就會(huì)增加。
你可以想見，在 Oscar 終于把所有小鴨子都放到它們想去的池塘之后，情景應(yīng)該是：N 個(gè)池塘，每個(gè)池塘里有相同數(shù)目的 N 只小鴨子。
今年，農(nóng)夫 Oscar 已經(jīng)有點(diǎn)厭倦每次必須來回于卡車和池塘之間，只為了放一只小鴨子，太耗時(shí)也太耗體力。
他想到了一個(gè)好主意：每一次，他會(huì)捧起 N 只小鴨子，到一個(gè)空著的池塘里，把這 N 只小鴨子放在里面。然后，他回到卡車，再把另一批 N 只小鴨子放到一個(gè)空著的池塘。
這樣，他只需要往返卡車 N 次，即可把所有的小鴨子都放置完畢。而且結(jié)束的時(shí)候的情景，和往年一樣：N 個(gè)池塘，每個(gè)池塘里有相同數(shù)目的 N 只小鴨子。
因?yàn)樽罱K分配結(jié)果和往年一樣，小鴨子們也沒有任何抱怨。
3. 兩種算法的對比
農(nóng)夫 Oscar 放置小鴨子到池塘的方法，我們可以稱之為“算法” 。因?yàn)檫@個(gè)算法是對“放置小鴨子”這個(gè)問題的一種精確描述。
往年的算法和今年的新算法，它們都滿足了最終的條件：放置結(jié)束后，沒有一個(gè)池塘的小鴨子數(shù)是多于或少于其他池塘的，每一個(gè)池塘都有 N 只小鴨子。
因此，往年的算法和今年的算法都滿足了小鴨子們的要求，都是合格的算法。
兩種算法的不同之處在于：往年的第一種算法，每只小鴨子都要求 Oscar 把它放到一個(gè)不同的池塘，因此 Oscar 須要往返于卡車和池塘之間的次數(shù)和小鴨子的數(shù)目是一樣的，是 N x N，也就是 N 的平方。而今年的第二種算法，Oscar 只需要往返 N 趟。
毫無疑問，今年的新算法是更高效的，而且節(jié)省下的時(shí)間和鴨子的數(shù)目成正比。
假設(shè) N 是 6，那么大箱子有 6 行 6 列，小鴨子的數(shù)目就是 36 只。如果 Oscar 在卡車和池塘之間往返一次的平均時(shí)間是 5 分鐘，那么第二種算法只需要 6 x 5 = 30 分鐘。而第一種算法卻需要 6 x 6 x 5 = 180 分鐘，也就是三小時(shí)，是第二種算法的 6 倍。
兩種算法的差異隨著鴨子數(shù)目的增多會(huì)繼續(xù)擴(kuò)大：假設(shè) N 是 24，那么大箱子有 24 行 24 列，就有 576 只小鴨子。如果 Oscar 在卡車和池塘之間往返一次的平均時(shí)間還是 5 分鐘，那么第二種算法只需要 24 x 5 = 120 分鐘，也就是 2 小時(shí)。而第一種算法卻需要 24 x 24 x 5 = 2880 分鐘，達(dá)到了 48 小時(shí)，是第二種算法的 24 倍。
顯然農(nóng)夫 Oscar 的新算法好太多了。在計(jì)算機(jī)術(shù)語中，我們會(huì)說他的新算法更有效、性能更高。我們可以用“復(fù)雜性”（Complexity）來量化這種性能，我們將在下一課中學(xué)習(xí)算法的復(fù)雜度。
4. 第一部分第三課預(yù)告
今天的課就到這里，一起加油吧！
下一課：數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第三課：算法復(fù)雜度
我是 謝恩銘，公眾號「程序員聯(lián)盟」（微信號：coderhub）運(yùn)營者，慕課網(wǎng)精英講師 Oscar 老師，終生學(xué)習(xí)者。
熱愛生活，喜歡游泳，略懂烹飪。
人生格言：「向著標(biāo)桿直跑」
