数据结构和算法 | 第一部分第二课:小鸭子们去旅行

数据结构和算法 | 第一部分第二课:小鸭子们去旅行

作者 谢恩铭,公众号「程序员联盟」。
转载请注明出处。
原文:https://www.jianshu.com/p/31d14bd080d4


《数据结构算法》全系列

内容简介


  1. 引出算法复杂度W w $ P 0 ) ; K d的故事
  2. 两种算法
  3. 两种算法的对比
  4. 第一部分第三课预告

1. 引出算法复杂度的故事


上一课 数据结构和算法 | 第一部分第一课:什么是数据结构和算法 中,我们初步认识了数据结构和算] m 2 x法。

既然我们要开始学习算法,就不能不提一下算法复杂度

但在我们开始谈论算法的D U * u W 4复杂度(Complexity)之前,我希望先给大0 t E i R :家讲个小故事。

这个轻松的小故事可以帮助你之后更好地理解算法复杂度。

之所以今天的故事标题是: e j 3 W 小鸭子们去旅行」 ,是因为我之前看了《向往的生活》 第二季,何老师他们的住房边上有一个羊圈,里面有天霸和点点两只羊,羊圈的边上是一个鸡窝,鸡窝里后来也养了一窝小鸭子

有几次,这一窝小鸭子从夹缝里偷溜出鸡窝,跑到E * ~ X住房附近的田里的小池子里游泳,甚是可爱。所以我就想到用小鸭子们来做例子。

数据结构和算法 | 第一部分第二课:小鸭子们去旅行


我们的故事是这样的:

农夫 Oscar 是一个非常友善的农夫,他养了很多只小鸭子(我知道你可能会在脑海里想象它们长大的样子,想象北京烤鸭的样子… 好了,赶紧打住这“邪恶”的念头)。

农夫 Osacr 和这H = T 0些小鸭子k c $ J c y *们的关系很好,它们平时可以出窝去m 7 e溜达,在冬天也可以享用一间带暖气j , P 3 1 c的小屋子。但真正让这些小鸭子们兴奋的是:每年夏季最炎热的时候,Oscar 会开着一辆卡车,载着小鸭子们到离家较远的山脚下去度假,那里有很多片小池塘。小鸭子们可以在小池塘里觅食、嬉戏,度过愉{ : D m y V W [快的{ A R r f v P :时光。

出发之前,农夫 Oscar 会首先在他的大卡车上放入一个大箱子,再把小鸭子们一只只装在大箱子里面。大箱子是正方形的,分为一个一个隔间,每只小鸭子就卧在一个小隔间里。长宽各有 N 个隔间,这里的 N 是一个我们暂时还不知道的数。池F 3 q W塘的数目也是4 z - 5 N。

但是问题来了:在度假的时候,小鸭子们是有要求的,每只小鸭子都跟 Oscar 说它们想要远离喧嚣,尽量到比较清净(鸭子数目少一些)的池塘里去。

2. 两种算法


以往的每年,农夫 Oscar 不想费脑子,所以他是这么做的:

到达目的地之后,Oscar 把卡车停在那一片池塘(池塘数目是 N)附近,从卡车上下来,打开后车门: P j / E,从那一箱子小鸭子里捧出一只来,然后问它:“你想去哪一个池塘?” 。一旦小鸭子选定了一个池塘,Oscar 就跑到那个池塘W k k = ^ H V -,把小鸭子放进去。

第一只小鸭子被放到想去的池塘之后,Oscar 跑回卡车,接着问第二只小鸭子它想选择哪个池塘。

因为已经有一只小鸭子选了其中一个池塘,既然这些小鸭子都希望去鸭少更清净的池塘,所以第二只小鸭子肯定会选一个还没有小鸭子在其中的池塘,然后 Osca% ^ q { j ^ E |r 又是一顿小跑。

Oscar 就以这样的方式接着问下一只小鸭子,并把每只小鸭子都放到它u ) d f | + Y们想去的池塘。

N 个池塘已经渐渐开始被小鸭子们占据。一旦有池塘里面的鸭子数比其他池塘少,那么小鸭子就会选择这个池塘。显然,小鸭子进去后,这个池塘的鸭子数就会增加。

你可以想见,在 OsL Q Icar 终于把所有小鸭子都放到它们想去的池塘_ p & [ ( Y |之后,情景应该是:N 个池塘,每个池塘里有相同数目的 N 只小鸭子。

今年,农夫 Oscar 已经有点厌倦每次c _ * @ .必须来回于卡车和池塘之间,只为了放一只u O ^ ) U小鸭子,太耗时也太耗体力。

他想到了一个好主意:每一次,他会捧起 N 只小鸭子,到一个空着的池塘里,把这 N 只小鸭子放在里面。然后,他回到卡车,再把另一批 N 只小鸭子放到一个空着的池塘。

这样,他只需要往返卡车 N 次,即可把所有的小鸭子都放置完毕。而且结束的时候的情景,和往年一样:N 个池塘,每个池塘里有相同数目的 N 只小鸭子。

因为最终分配结果和往年一样,小鸭子们也没有任何抱o _ g j U _ G ) :f + N d G (

3. 两O c [ 3 # z @ p ,种算法的对比


农夫 Oscar 放置小鸭? Z w ] ? m子到池塘的方法,我们可以称之为“算法” 。因为这个算法是对“放置小鸭子”这个问题的一种精确描述。

往年的算法和今年的新算法,它们都满足了最终的条件:放置结束后,没有一个池W 4 2 u 2 N &塘的小鸭子数是多于或少于其他池塘的,每一个池塘都有 N 只小鸭子x Y d F q。

因此,往年的算法和今年的算法都满足了小鸭子们的要求,都t . 5 0 R m ? 2 p是合格的算法。

两种算法的不同之处在于:往年的第一种算法,} { *每只小鸭子都要求 Oscar 把它q ; l ! 5 b放到一个不同的池塘,因此 Oscar 须要往返于卡车和池塘之间的次数和小鸭D ) b | ! e ( w子的数目是一m c / q : 0 f样的,是 N x N,也就是 N 的平方。而今年的第二种算法,Oscar 只需要往返 N 趟。

毫无疑问,B G I ! K n d今年的新算法是更高效的,而且节省下的时间和鸭子的数目成正比。

假设 N 是 6,那么大箱子有 6 行 6 列,小鸭子的数目就是 36 只。如果 Oscarh w n u H y 5 在卡车和池塘之间往I = x X B ) % s 0返一次的平均时间是 5 分钟,那么第二种算法只需要 6 x 5 = 30 分H 9 } , ~ & L钟。而第一种算法却需要 6 x 6 x 5 = 180 分钟,也就是三小时,是第二种算法的 6 倍。

M e w E种算法的差异随着鸭子数目的增多会继续扩大:假设 N 是 24,那么大箱子有 24 行 24 列,就有 576 只小鸭子。如果 Oscar 在卡车和池塘之间往返一次的平均时间还是 5 分钟,那么第二种算法只需要 24 x 5 = 120 分钟,也就是 2 小时。而第一种算法却需要 24 x 24 x 5 = 2880 分钟,达到了 48 小时,是第二种算法的 24 倍。

显然农夫 Oscar 的新算法好太多了。在计算机术语中,我们会说他的新算法更有效、性能更高。我们可以用“复杂性”(Complexity)来量化这种性能,我们将在下一课o ] ~ * H c X n中学习算法的复杂度。

4. 第一部分第三课预告


今天的课就到这里,一起加P 9 b油吧!

下一课:数据结构和算法 | 第一部分第三课:算法复杂度


我是 谢恩铭,公众号「程序员联盟」运营者,慕课网z m m w Y Y q $ F精英讲师 Oscar 老师,终生学习者。
热爱生活,喜欢游泳,略懂烹饪。s A o k a
人生格言:「向着标杆直跑」