数据结构和算法|第1部分第2课:鸭子旅行
作者谢恩铭，公开号“程序员联盟”。转载请注明出处。原件:/p/31d14bd080d4
内容介绍引出了算法复杂性的故事
两种算法
两种算法的比较
第一部分第三课预习
1.介绍算法复杂性的故事最后一课数据结构和算法|第一部分第1课:什么是数据结构和算法，我们对数据结构和算法有了初步的了解生化全球最新章节。
既然我们想开始学习算法，我们不能不提到算法的复杂性。
但是在我们开始讨论算法的复杂性之前，我想给你们讲一个小故事。
这个简单的故事可以帮助你以后更好地理解算法的复杂性。
今天故事的标题是“小鸭子旅行”的原因是因为我以前看过《渴望生活》的第二季。何老师他们家附近有一个羊圈，里面有天坝和店店两只羊。羊圈的边缘是一个鸡舍，里面养着一窝小鸭。
有几次，这一窝小鸭子从鸡舍的缝隙里偷偷溜出来，跑到房子附近田野里的一个小池塘里游泳，非常可爱。所以我想以小鸭子为例。
鸭子，我们的故事是这样的:
农民奥斯卡是一个非常友好的农民。他养了很多小鸭子(我知道你可能会想象它们在你的脑海中成长，还有北京烤鸭……好吧，赶快停止这种“邪恶”的想法)。
农民奥萨卡和这些小鸭子关系很好。它们可以在平时走出巢穴，在冬天享受一个有暖气的小房间。但是真正让这些小鸭子兴奋的是，每年最热的夏天，奥斯卡都会开着卡车到离家很远的山脚下度假，那里有很多小池塘。鸭子可以在小池塘里找到食物，玩耍，玩得开心。
在离开之前，农夫奥斯卡会先把一个大盒子放进他的大卡车里，然后把小鸭子放进这个大盒子里。大盒子是正方形的，分成几个隔间，每只小鸭都躺在一个小隔间里。有n个长度和宽度的隔间，其中n是一个我们还不知道的数字。池塘的数量也是n。
但问题是:在假期，小鸭子有要求。每只小鸭都告诉奥斯卡，它们想远离噪音，尽量去一个相对干净的池塘(更少的鸭子)。
2.两个算法在过去的一年里，农民奥斯卡不想浪费他的大脑，所以他这样做了:
到达目的地后，奥斯卡把卡车停在池塘边(池塘的数量是n)，从卡车上下来，打开后门，从装着小鸭子的盒子里拿出一只，然后问它，“你想去哪个池塘？”。一旦小鸭选择了一个池塘，奥斯卡跑到池塘，把小鸭放了进去。
第一只小鸭被放进他想去的池塘后，奥斯卡跑回卡车，然后问第二只小鸭他想选择哪个池塘。
因为一只小鸭已经选择了其中的一个池塘，因为所有这些小鸭都想去一个有更少鸭子和更干净池塘的池塘，第二只小鸭肯定会选择一个没有小鸭的池塘，奥斯卡会再次小跑。
奥斯卡然后这样问下一只小鸭，并把每只小鸭放在他们想去的池塘里。
池塘已经逐渐开始被小鸭子占据。一旦有一个池塘的鸭子比其他池塘少，鸭子就会选择这个池塘。显然，当小鸭进入后，这个池塘里的鸭子数量会增加。
可以想象，当奥斯卡最终把所有的小鸭都放到他们想去的池塘后，场景应该是:n个池塘，每个池塘有相同数量的n只小鸭。
今年，农民奥斯卡厌倦了每次都要在卡车和池塘之间来回穿梭，只为了放一只小鸭，这太费时费力了。
他想出了一个好主意:每次，他都会捡起n只小鸭子，把它们放到池塘里。然后，他回到卡车上，把另一批n只小鸭子放到池塘里。
这样，他只需要来回到卡车n次，然后所有的小鸭都可以放置。在场景的最后，像往年一样:n个池塘，每个池塘有相同数量的n只鸭子。
因为最后的分配结果和往年一样，小鸭们没有怨言。
3.两种算法的比较农民奥斯卡把小鸭放进池塘的方法可以称为“算法”。因为这个算法是对“放小鸭”问题的准确描述。
前几年的算法和今年的新算法都满足最终条件:安置后，没有一个池塘比其他池塘有更多或更少的鸭子，每个池塘有n只鸭子。
因此，前几年和今年的算法都符合小鸭的要求，都是合格的算法。
这两种算法的不同之处在于，在前几年的第一种算法中，每只小鸭都要求奥斯卡把它放在不同的池塘里，所以奥斯卡不得不在卡车和池塘之间来回寻找相同数量的小鸭，也就是n×n，也就是n的平方。在今年的第二种算法中，奥斯卡只需要n次往返。
毫无疑问，今年的新算法效率更高，节省的时间与鸭子的数量成正比。
如果n是6，那么大盒子有6行6列，小鸭子的数量是36。如果奥斯卡的卡车和池塘之间的平均往返时间是5分钟，那么第二个算法只需要6 x 5 = 30分钟。第一个算法需要6 x 6 x 5 = 180分钟，即3小时，是第二个算法的6倍。
两种算法之间的差异将随着鸭子数量的增加而不断扩大:如果n是24，那么大盒子里有24行24列，有576只鸭子。如果奥斯卡的卡车和池塘之间的平均往返时间仍然是5分钟，那么第二个算法只需要24×5 = 120分钟，即2小时。第一种算法需要24 x 24 x 5 = 2880分钟，即48小时，是第二种算法的24倍。
显然农民奥斯卡的新算法要好得多。用计算机术语来说，我们会说他的新算法更高效，性能更高。我们可以用“复杂性”来量化这种性能，我们将在下一课中学习算法的复杂性。
4.第三课的第一部分预言今天的课到此结束。来吧！
下一课:数据结构和算法|第一部分第3课:算法复杂性
我是谢恩明，公开号“程序员联盟”的主人，奥斯卡，大型开放在线课程网的精英讲师，终身学习者。热爱生活，喜欢游泳，对烹饪略知一二。人生格言:“奔向基准”
文章来源：www.atolchina.com