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

news/2024/10/30 17:22:29/

程序 = 数据结构 + 算法

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

内容简介


  1. 引出算法复杂度的故事
  2. 两种算法
  3. 两种算法的对比
  4. 第一部分第三课预告

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


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

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

但在我们开始谈论算法的复杂度(Complexity)之前,我希望先给大家讲个小故事。

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

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

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

小鸭子们


我们的故事是这样的:

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

农夫 Osacr 和这些小鸭子们的关系很好,它们平时可以出窝去溜达,在冬天也可以享用一间带暖气的小屋子。但真正让这些小鸭子们兴奋的是:每年夏季最炎热的时候,Oscar 会开着一辆卡车,载着小鸭子们到离家较远的山脚下去度假,那里有很多片小池塘。小鸭子们可以在小池塘里觅食、嬉戏,度过愉快的时光。

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

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

2. 两种算法


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

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

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

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

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

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

你可以想见,在 Oscar 终于把所有小鸭子都放到它们想去的池塘之后,情景应该是:N 个池塘,每个池塘里有相同数目的 N 只小鸭子。

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

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

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

因为最终分配结果和往年一样,小鸭子们也没有任何抱怨。

3. 两种算法的对比


农夫 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)来量化这种性能,我们将在下一课中学习算法的复杂度。

4. 第一部分第三课预告


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

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


我是 谢恩铭,公众号「程序员联盟」号主,慕课网精英讲师 Oscar 老师,终生学习者。
热爱生活,喜欢游泳,略懂烹饪。
人生格言:「向着标杆直跑」


http://www.ppmy.cn/news/271292.html

相关文章

计算机学win7画图,Windows7电脑基础使用画图程序画一个小鸭

1、启动程序 1)单击“开始-所有程序-附件-画图”,这样就打开了画图窗口 2)在窗口中,上边是工具栏,里面包含有菜单按钮和许多画图工具,像铅笔、线条、颜色等; 3)中间是工作区,里面有一个空白的画布,可以在里…

java基础_设计模式_设计基础(小鸭子游戏)

小鸭子游戏,是好多爱好者接触设计模式、认知设计模式概念的一个入门。 每个初学者的理解不同,我加上自己的理解大体是这样的:前提是处理大规模时,假设池塘中有10000头小鸭子,有红头鸭,野鸭子,木…

Android移动应用开发——实验七——小鸭子报数(广播)

 掌握布局与控件的使用方法  掌握有序广播机制,根据广播接收者的优先级顺序接收广播  掌握广播拦截机制 通过合理布局来搭建界面,界面效果如下图所示。采用有序广播方式,将下方小鸭子优先级分别设置1000、800、600。 1、当点…

用MATLAB求解小鸭过河曲线

题目描述 有只鸭子想游到河对岸的某个位置O,如果它的方向始终朝着目标O。求这只鸭子的游动曲线。问题分析 由于水流速度会对运动产生影响,此时小鸭朝向对岸的方向是一个随时变化的,合速度的方向和大小也是变化的,小鸭的运动轨迹将…

6综合项目 旅游网 【6.我的收藏和收藏排行榜】

我的收藏 分析 先登录→拿到当前登录的用户信息,从数据库中获取uid和对应uid的rid集合→将rid集合信息展示到我的收藏 前台代码 判断用户是否登录,传递uid,通过uid查找其对应的rid集合 当查询的属性涉及到多张表,则必须使用多表连…

实时分析:Flume+Kafka+SparkStreaming商品评分排行榜

写在前面 接上一篇《FlumeKafka数据采集与清洗》。 本文主要介绍用流计算SparkStreaming对数据进行实时处理。 流计算 概念 实时获取来自不同数据源的海量数据,经过实时 分析处理,获得有价值的信息 流计算秉承一个基本理念,即数据的价值…

用python画小鸭,Python 处理输入法字库(五笔极点字库转小鸭字库)

Python 处理输入法字库(五笔极点字库转小鸭字库) Python 处理输入法字库(五笔极点字库转小鸭字库) 一直都是用的小鸭五笔,091新字库是极点格式的,刚开始懒得动,直接用极点五笔了,用了一段时间碰到很多问题.其中最坑的是. 在tkinter Gui 里极点输入不能退格,一退格就乱码( ) ,我…

微信运动排行榜服务器忙,那些在微信运动排行榜上霸榜的朋友都在哪儿运动的?...

入冬以来,这天是一天比一天冷,周报君已经开启了冬眠模式,能不出门尽量不出门吹冷风,能不动尽量猫在被窝里不动。 但朋友圈里总有那么几位,他们从不畏严寒酷暑,在每一个你赖床的早晨和吃夜宵的夜晚&#xff…