引出算法複雜度的故事
兩種算法
兩種算法的對比
第一部分第三課預告
上一課 數據結構和算法 | 第一部分第一課：什麼是數據結構和算法 中，我們初步認識了數據結構和算法。
既然我們要開始學習算法，就不能不提一下算法複雜度。
但在我們開始談論算法的複雜度（Complexity）之前，我希望先給大家講個小故事。
這個輕鬆的小故事可以幫助你之後更好地理解算法複雜度。
之所以今天的故事標題是「小鴨子們去旅行」 ，是因為我之前看了《嚮往的生活》 第二季，何老師他們的住房邊上有一個羊圈，裡面有天霸和點點兩隻羊，羊圈的邊上是一個雞窩，雞窩裡後來也養了一窩小鴨子。
有幾次，這一窩小鴨子從夾縫裡偷溜出雞窩，跑到住房附近的田裡的小池子裡遊泳，甚是可愛。所以我就想到用小鴨子們來做例子。
小鴨子們
我們的故事是這樣的：
農夫 Oscar 是一個非常友善的農夫，他養了很多隻小鴨子（我知道你可能會在腦海裡想像它們長大的樣子，想像北京烤鴨的樣子… 好了，趕緊打住這「邪惡」的念頭）。
農夫 Osacr 和這些小鴨子們的關係很好，它們平時可以出窩去溜達，在冬天也可以享用一間帶暖氣的小屋子。但真正讓這些小鴨子們興奮的是：每年夏季最炎熱的時候，Oscar 會開著一輛卡車，載著小鴨子們到離家較遠的山腳下去度假，那裡有很多片小池塘。小鴨子們可以在小池塘裡覓食、嬉戲，度過愉快的時光。
出發之前，農夫 Oscar 會首先在他的大卡車上放入一個大箱子，再把小鴨子們一隻只裝在大箱子裡面。大箱子是正方形的，分為一個一個隔間，每隻小鴨子就臥在一個小隔間裡。長寬各有 N 個隔間，這裡的 N 是一個我們暫時還不知道的數。池塘的數目也是 N。
但是問題來了：在度假的時候，小鴨子們是有要求的，每隻小鴨子都跟 Oscar 說它們想要遠離喧囂，儘量到比較清淨（鴨子數目少一些）的池塘裡去。
以往的每年，農夫 Oscar 不想費腦子，所以他是這麼做的：
到達目的地之後，Oscar 把卡車停在那一片池塘（池塘數目是 N）附近，從卡車上下來，打開後車門，從那一箱子小鴨子裡捧出一隻來，然後問它：「你想去哪一個池塘？」 。一旦小鴨子選定了一個池塘，Oscar 就跑到那個池塘，把小鴨子放進去。
第一隻小鴨子被放到想去的池塘之後，Oscar 跑回卡車，接著問第二隻小鴨子它想選擇哪個池塘。
因為已經有一隻小鴨子選了其中一個池塘，既然這些小鴨子都希望去鴨少更清淨的池塘，所以第二隻小鴨子肯定會選一個還沒有小鴨子在其中的池塘，然後 Oscar 又是一頓小跑。
Oscar 就以這樣的方式接著問下一隻小鴨子，並把每隻小鴨子都放到它們想去的池塘。
N 個池塘已經漸漸開始被小鴨子們佔據。一旦有池塘裡面的鴨子數比其他池塘少，那麼小鴨子就會選擇這個池塘。顯然，小鴨子進去後，這個池塘的鴨子數就會增加。
你可以想見，在 Oscar 終於把所有小鴨子都放到它們想去的池塘之後，情景應該是：N 個池塘，每個池塘裡有相同數目的 N 只小鴨子。
今年，農夫 Oscar 已經有點厭倦每次必須來回於卡車和池塘之間，只為了放一隻小鴨子，太耗時也太耗體力。
他想到了一個好主意：每一次，他會捧起 N 只小鴨子，到一個空著的池塘裡，把這 N 只小鴨子放在裡面。然後，他回到卡車，再把另一批 N 只小鴨子放到一個空著的池塘。
這樣，他只需要往返卡車 N 次，即可把所有的小鴨子都放置完畢。而且結束的時候的情景，和往年一樣：N 個池塘，每個池塘裡有相同數目的 N 只小鴨子。
因為最終分配結果和往年一樣，小鴨子們也沒有任何抱怨。
農夫 Oscar 放置小鴨子到池塘的方法，我們可以稱之為「算法」 。因為這個算法是對「放置小鴨子」這個問題的一種精確描述。
往年的算法和今年的新算法，它們都滿足了最終的條件：放置結束後，沒有一個池塘的小鴨子數是多於或少於其他池塘的，每一個池塘都有 N 只小鴨子。
因此，往年的算法和今年的算法都滿足了小鴨子們的要求，都是合格的算法。
兩種算法的不同之處在於：往年的第一種算法，每隻小鴨子都要求 Oscar 把它放到一個不同的池塘，因此 Oscar 須要往返於卡車和池塘之間的次數和小鴨子的數目是一樣的，是 N x N，也就是 N 的平方。而今年的第二種算法，Oscar 只需要往返 N 趟。
毫無疑問，今年的新算法是更高效的，而且節省下的時間和鴨子的數目成正比。
假設 N 是 6，那麼大箱子有 6 行 6 列，小鴨子的數目就是 36 只。如果 Oscar 在卡車和池塘之間往返一次的平均時間是 5 分鐘，那麼第二種算法只需要 6 x 5 = 30 分鐘。而第一種算法卻需要 6 x 6 x 5 = 180 分鐘，也就是三小時，是第二種算法的 6 倍。
兩種算法的差異隨著鴨子數目的增多會繼續擴大：假設 N 是 24，那麼大箱子有 24 行 24 列，就有 576 只小鴨子。如果 Oscar 在卡車和池塘之間往返一次的平均時間還是 5 分鐘，那麼第二種算法只需要 24 x 5 = 120 分鐘，也就是 2 小時。而第一種算法卻需要 24 x 24 x 5 = 2880 分鐘，達到了 48 小時，是第二種算法的 24 倍。
顯然農夫 Oscar 的新算法好太多了。在計算機術語中，我們會說他的新算法更有效、性能更高。我們可以用「複雜性」（Complexity）來量化這種性能，我們將在下一課中學習算法的複雜度。
今天的課就到這裡，一起加油吧！
下一課：數據結構和算法 | 第一部分第三課：算法複雜度（上）
作者：謝恩銘
出處：公眾號「程式設計師聯盟」
原文連結：https://www.jianshu.com/p/31d14bd080d4
轉載請註明出處，謝謝合作！
歡迎將我的公眾號「設為星標」✨
右下角↘️點個「在看」
是對我很大的鼓勵和幫助