作者 謝恩銘诫舅，公眾號(hào)「程序員聯(lián)盟」（微信號(hào)：coderhub）廊遍。
轉(zhuǎn)載請(qǐng)注明出處璃谨。
原文：http://www.reibang.com/p/31d14bd080d4
內(nèi)容簡(jiǎn)介
- 引出算法復(fù)雜度的故事
- 兩種算法
- 兩種算法的對(duì)比
- 第一部分第三課預(yù)告
1. 引出算法復(fù)雜度的故事
上一課 數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第一課：什么是數(shù)據(jù)結(jié)構(gòu)和算法 中蚀瘸，我們初步認(rèn)識(shí)了數(shù)據(jù)結(jié)構(gòu)和算法。
既然我們要開(kāi)始學(xué)習(xí)算法绢掰，就不能不提一下算法復(fù)雜度痒蓬。
但在我們開(kāi)始談?wù)撍惴ǖ膹?fù)雜度（Complexity）之前，我希望先給大家講個(gè)小故事滴劲。
這個(gè)輕松的小故事可以幫助你之后更好地理解算法復(fù)雜度攻晒。
之所以今天的故事標(biāo)題是「小鴨子們?nèi)ヂ眯小?，是因?yàn)槲抑翱戳恕断蛲纳睢?第二季班挖，何老師他們的住房邊上有一個(gè)羊圈鲁捏，里面有天霸和點(diǎn)點(diǎn)兩只羊，羊圈的邊上是一個(gè)雞窩萧芙，雞窩里后來(lái)也養(yǎng)了一窩小鴨子给梅。
有幾次假丧，這一窩小鴨子從夾縫里偷溜出雞窩，跑到住房附近的田里的小池子里游泳动羽，甚是可愛(ài)包帚。所以我就想到用小鴨子們來(lái)做例子。
我們的故事是這樣的：
農(nóng)夫 Oscar 是一個(gè)非常友善的農(nóng)夫曹质，他養(yǎng)了很多只小鴨子（我知道你可能會(huì)在腦海里想象它們長(zhǎng)大的樣子，想象北京烤鴨的樣子… 好了擎场，趕緊打住這“邪惡”的念頭）羽德。
農(nóng)夫 Osacr 和這些小鴨子們的關(guān)系很好，它們平時(shí)可以出窩去溜達(dá)迅办，在冬天也可以享用一間帶暖氣的小屋子宅静。但真正讓這些小鴨子們興奮的是：每年夏季最炎熱的時(shí)候，Oscar 會(huì)開(kāi)著一輛卡車站欺，載著小鴨子們到離家較遠(yuǎn)的山腳下去度假姨夹，那里有很多片小池塘。小鴨子們可以在小池塘里覓食矾策、嬉戲磷账，度過(guò)愉快的時(shí)光。
出發(fā)之前贾虽，農(nóng)夫 Oscar 會(huì)首先在他的大卡車上放入一個(gè)大箱子逃糟，再把小鴨子們一只只裝在大箱子里面。大箱子是正方形的蓬豁，分為一個(gè)一個(gè)隔間绰咽，每只小鴨子就臥在一個(gè)小隔間里。長(zhǎng)寬各有 N 個(gè)隔間地粪，這里的 N 是一個(gè)我們暫時(shí)還不知道的數(shù)取募。池塘的數(shù)目也是 N。
但是問(wèn)題來(lái)了：在度假的時(shí)候蟆技，小鴨子們是有要求的玩敏，每只小鴨子都跟 Oscar 說(shuō)它們想要遠(yuǎn)離喧囂，盡量到比較清凈（鴨子數(shù)目少一些）的池塘里去质礼。
2. 兩種算法
以往的每年聊品，農(nóng)夫 Oscar 不想費(fèi)腦子，所以他是這么做的：
到達(dá)目的地之后几苍，Oscar 把卡車停在那一片池塘（池塘數(shù)目是 N）附近翻屈，從卡車上下來(lái)，打開(kāi)后車門(mén)妻坝，從那一箱子小鴨子里捧出一只來(lái)伸眶，然后問(wèn)它：“你想去哪一個(gè)池塘惊窖？” 。一旦小鴨子選定了一個(gè)池塘厘贼，Oscar 就跑到那個(gè)池塘界酒，把小鴨子放進(jìn)去。
第一只小鴨子被放到想去的池塘之后嘴秸，Oscar 跑回卡車毁欣，接著問(wèn)第二只小鴨子它想選擇哪個(gè)池塘。
因?yàn)橐呀?jīng)有一只小鴨子選了其中一個(gè)池塘岳掐，既然這些小鴨子都希望去鴨少更清凈的池塘凭疮，所以第二只小鴨子肯定會(huì)選一個(gè)還沒(méi)有小鴨子在其中的池塘，然后 Oscar 又是一頓小跑串述。
Oscar 就以這樣的方式接著問(wèn)下一只小鴨子执解，并把每只小鴨子都放到它們想去的池塘。
N 個(gè)池塘已經(jīng)漸漸開(kāi)始被小鴨子們占據(jù)纲酗。一旦有池塘里面的鴨子數(shù)比其他池塘少衰腌，那么小鴨子就會(huì)選擇這個(gè)池塘。顯然觅赊，小鴨子進(jìn)去后右蕊，這個(gè)池塘的鴨子數(shù)就會(huì)增加。
你可以想見(jiàn)吮螺，在 Oscar 終于把所有小鴨子都放到它們想去的池塘之后尤泽，情景應(yīng)該是：N 個(gè)池塘，每個(gè)池塘里有相同數(shù)目的 N 只小鴨子规脸。
今年坯约，農(nóng)夫 Oscar 已經(jīng)有點(diǎn)厭倦每次必須來(lái)回于卡車和池塘之間，只為了放一只小鴨子莫鸭，太耗時(shí)也太耗體力闹丐。
他想到了一個(gè)好主意：每一次，他會(huì)捧起 N 只小鴨子被因，到一個(gè)空著的池塘里卿拴，把這 N 只小鴨子放在里面。然后梨与，他回到卡車堕花，再把另一批 N 只小鴨子放到一個(gè)空著的池塘。
這樣粥鞋，他只需要往返卡車 N 次缘挽，即可把所有的小鴨子都放置完畢。而且結(jié)束的時(shí)候的情景，和往年一樣：N 個(gè)池塘壕曼，每個(gè)池塘里有相同數(shù)目的 N 只小鴨子苏研。
因?yàn)樽罱K分配結(jié)果和往年一樣，小鴨子們也沒(méi)有任何抱怨腮郊。
3. 兩種算法的對(duì)比
農(nóng)夫 Oscar 放置小鴨子到池塘的方法摹蘑，我們可以稱之為“算法” 。因?yàn)檫@個(gè)算法是對(duì)“放置小鴨子”這個(gè)問(wèn)題的一種精確描述轧飞。
往年的算法和今年的新算法衅鹿，它們都滿足了最終的條件：放置結(jié)束后，沒(méi)有一個(gè)池塘的小鴨子數(shù)是多于或少于其他池塘的过咬，每一個(gè)池塘都有 N 只小鴨子大渤。
因此，往年的算法和今年的算法都滿足了小鴨子們的要求援奢，都是合格的算法兼犯。
兩種算法的不同之處在于：往年的第一種算法忍捡，每只小鴨子都要求 Oscar 把它放到一個(gè)不同的池塘集漾，因此 Oscar 須要往返于卡車和池塘之間的次數(shù)和小鴨子的數(shù)目是一樣的，是 N x N砸脊，也就是 N 的平方具篇。而今年的第二種算法，Oscar 只需要往返 N 趟凌埂。
毫無(wú)疑問(wè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ù)語(yǔ)中智哀，我們會(huì)說(shuō)他的新算法更有效次询、性能更高。我們可以用“復(fù)雜性”（Complexity）來(lái)量化這種性能瓷叫，我們將在下一課中學(xué)習(xí)算法的復(fù)雜度屯吊。
4. 第一部分第三課預(yù)告
今天的課就到這里，一起加油吧摹菠！
下一課：數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第三課：算法復(fù)雜度
我是 謝恩銘盒卸，公眾號(hào)「程序員聯(lián)盟」（微信號(hào)：coderhub）運(yùn)營(yíng)者，慕課網(wǎng)精英講師 Oscar 老師次氨，終生學(xué)習(xí)者蔽介。
熱愛(ài)生活，喜歡游泳煮寡，略懂烹飪虹蓄。
人生格言：「向著標(biāo)桿直跑」
