[音乐播放] 国宝马兰所有权利。好吧，欢迎回来。因此，这是第4周，开始其已经。你还记得，上周，我们把编码一旁只是一点点我们开始交谈多一点高层次，一样的东西搜索和排序，这虽然有些简单的想法，代表的一类问题你将开始解决特别当你开始思考最终项目和有趣的解决方案可能有现实世界的问题。现在是一个最简单的冒泡排序这样的算法，它通过这些小的数字工作在一个列表中，或在一个数组中种泡自己的方式到顶部，大的数字移动一路下跌至该列表的末尾。记得我们可以想象一点点的冒泡排序这样的事情。所以，让我继续前进，单击“开始”。我预选冒泡排序。如果你还记得，高大的蓝色线代表大号码，小蓝线代表小数字，我们通过这一而再，再而再次，比较相邻的两间酒吧红色，我们要交换最大的和最小的，如果他们秩序。因此，这会去，去，去，你会看到，较大的元素使他们的方式的权利，而较小的元素是使他们的方式到左边。但我们开始量化效率，在此算法中的质量。和我们说，在最坏情况下，该算法采取了大约多少步？因此n的平方。什么是N？观众：元素数目。国宝马兰因此n 数目的元素。所以我们经常这样做。任何时候，我们要谈论的大小一个问题或大小的输入，或花费的时间量以产生输出，我们只广义的任何输入为n。因此，早在第0周，数页在电话簿为n。学生人数在房间里为：N。所以在这里，太，我们继这个模式。现在Ñ平方是不是特别快，所以我们试图做的更好。因此，我们看着一对夫妇其他的算法，其中选择排序。所以选择排序有一点不同。这几乎是简单的，我敢说，由此开始的开始我们的志愿者名单，我只是再次一次又一次经历列表，采摘最小在一个时间元素，并把他或她在列表的开头。但是它也同样，一旦我们开始思考通过数学和更大的图片，想过多少次我正想来回和背部奔波，我们说，在最坏的情况下，太多，选择排序，那是什么？摆正Ń。现在，在现实世界中，它可能实际上是稍快。因为再次，我没有保持回溯一旦我排序最小的元素。但是，如果我们想想n很大，如果你的，做出来的数学我在黑板上，与n的平方减去的东西，一切除了n个平方，一旦N 变得非常大，不真正的问题一样多。因此，作为计算机科学家，我们的排序视而不见较小因素和只注重的因素一个表达式，将会使最大的区别。好了，最后，我们看了在插入排序。这是类似的精神，但而不是通过迭代选择最小的元素之一，在的时间，我只花了我的手处理，我决定，所有没错，你属于这里。然后我转移到下一个元素并决定，他或她属于这里。然后，我和移动。我可能会，一路走来，以这些家伙转移为他们腾出空间。所以这是样的心理逆转选择排序，我们所谓插入排序。因此，这些主题发生在现实世界中。仅仅在几年前，当达到一定参议员竞选总统，，在当时的CEO埃里克·施密特（Eric Schmidt）谷歌，居然有机会采访他。我们认为我们会分享此YouTube 夹你在这里，如果我们可以将音量。 [视频回放] 现在，参议员，你在谷歌，我喜欢把总统作为一个工作面试。 [笑] 现在它是很难得到一个工作作为总统。你要通过现在的严峻考验。这也很难在谷歌找到一份工作。我们有问题，我们要求我们的候选人的问题。而这一次是从拉里·施维默。 [笑] 你们觉得我在开玩笑吗？就是这里。这是最有效的方式来排序一百万两位整数？ [笑] 嗯，呃 - 我很抱歉。也许我们应该 - 不，不，不，不，不。这不是一个 - 确定。我认为冒泡排序是错误的方式去。 [笑] [欢呼和掌声] 来吧，谁告诉他这个呢？确定。 [END视频播放] 国宝MALAN：所以你有它。于是我们开始量化这些运行倍，所以说话，用的东西被称为渐近符号，这是刚刚提到我们转向排序视而不见，那些规模较小的因素，只盯着运行时间，这些算法的性能为n随着时间的推移变得非常大。因此，我们介绍大澳大O 代表的东西，我们认为作为一个上限。巴里，而实际上，我们可以降低比话筒一点点？我们认为这是一个上限。因此，大O在n的平方手段最坏的情况下，类似的东西选择排序平方步骤Ń。或类似的东西插入排序将Ñ平方步骤。现在像插入排序，最坏的情况是什么？给定一个数组，什么是最糟糕的可能发生的情况，你可能会发现自己面临着？它是完全向后，对不对？因为如果它是完全向后，你所要做的一大堆工作。因为如果你完全向后，你要找到这里最大的元素，即使它属于那里。所以，你说，所有的权利，时间在这一刻，你属于这里，所以你离开单干。然后你意识到，哦，该死的，我要移动这种略小的元素左侧。然后我再这样做一遍又一遍。如果我来回走了，你会有点感觉的表现这个算法，我因为不断其他人倒在洗牌阵列，以腾出空间。因此，这是最坏的情况。与此相反 - 这是一个扣人心弦的最后一次 - 我们说，插入排序是欧米茄的什么？什么是最好的情况下运行插入排序的时间吗？所以它实际上ñ。这是我们离开的空白在黑板上的最后一次。欧米茄的n，因为为什么呢？那么，在最好的情况下，有什么插入排序将要移交？好了，完全排序的列表已经最小的工作要做。但是，什么是整齐插入排序是，由于开始决定，哦，你的号码一，你属于这里。哦，什么好运。你两个数。你也属于这里。三，甚至更好，你属于这里。只要它得到的末尾列表中，每次插入排序的伪代码我们走过口头最后一次，它的工作要做。但选择排序，相比之下，不停地做什么？持续通过列表一遍又一遍。因为关键的洞察力，只有一旦你看了一路列表末尾您可以肯定选定的元素确实是目前最小的元素。因此，这些不同的心智模式结束高达产生一些很现实世界为我们的差异，以及这些理论渐近差异。因此，只要回顾一下，然后，大O的n 平方，我们已经看到了一些这样的迄今为止算法。大OŃ？什么是算法，可以说是大O的n？在最坏的情况下，它需要一个线性的步数。 OK，线性搜索。而在最坏的情况下，其中是你要找的元素时，应用线性搜索？行，在最坏的情况下，它甚至不存在。或者在最坏的情况下，它一路到底，这是加或减去一个单步的差异。因此，在一天结束时，我们可以说，它是线性的。大O n的线性搜索，在最坏的情况下，因为元素甚至不存在，或者它所有的方式在结束。嗯，大O n的日志。我们没有讲的很详细，关于这一点，但我们已经看到了这一点。运行在所谓的对数时间，在最坏的情况下？是啊，所以二进制搜索。在最坏的情况下，和二进制搜索可能具有元素中某处中间，或某处阵列内。但你只找到它，一旦你将列表的一半，在半，一半的一半。然后瞧，它的存在。再或者，最坏的情况下，它甚至不存在。但你不知道它不存在，直到你达到这最后最底层的元素减半和减半减半。大O 1。因此，我们可以大O 2，大O 3。任何时候你想只是一个常数，我们仅仅只是简化排序，大O 1。即使如果现实的，它需要 2甚至100步，如果它是一个恒定数量的步骤，我们只是说大O 1。什么是算法，在大O 1？观众：查找长度一个变量。国宝马兰：寻找一个变量的长度？观众：没有，长度如果它已经排序。国宝马兰：好。 OK，所以寻找的东西的长度如果长度的东西，如被存储在一个数组中，一些变量。因为你可以读取该变量，或打印变量，或只是一般访问该变量。瞧，这需要恒定的时间。相比之下，回想起划伤。回想第一周的C，仅调用printf和打印屏幕上的东西可以说是恒定的时间，因为它只是需要一些CPU周期数显示该屏幕上的文字。或等待 - 它吗？否则怎么可能我们模型 printf的表现？有人会不以为然，也许这不是真的恒定的时间吗？在什么意义上的printf可能运行时间，实际打印字符串屏幕，是不变以外。观众：[听不清]。 DAVID马兰：是啊。因此，它取决于我们的角度来看。如果我们真的想输入作为字符串的printf，因此，我们测量的大小，输入的长度 - 所以姑且称之为该长度为n，以及 - 可以说，printf是本身的n大O 因为它会带你n步打印出与N 字符，最有可能的。至少，我们假设的程度也许它使用for循环引擎盖下。不过，我们将不得不看编写更好地理解它。而事实上，一旦你们开始分析自己的算法，你会从字面上做到这一点。眼球排序的代码，并认为 - 所有的权利，我有这样的循环否则我这里有一个嵌套循环，做N事物n次，可以按自己的方式的原因通过代码，即使它是伪代码，而不是实际的代码。那么欧米茄n的平方？这是一个算法，在最好的的情况下，仍然采取Ñ平方的步骤吗？是吗？观众：[听不清]。国宝马兰：所以选择排序。因为在这个问题确实减少这样的事实，再次，我不知道我发现目前最小的，直到我检查了所有的混账元素。因此，欧米茄，我们说，正只是想出了一个。插入排序。如果列表进行排序发生已经在最好的情况下，我们只需要通过一次，在这一点上，我们肯定。然后，可以说是线性的，是肯定的。什么欧米加1？什么，在最好的情况下，可能需要固定数量的步骤？所以线性搜索，如果你只是很幸运和你要找的元素在列表的开头是正确的，如果这是您在何处开始线性遍历该列表。而这，是真正的一些东西。举例来说，即使二进制搜寻欧米加1。因为如果你得到真正的织补幸运和咂嘴-DAB的中间您的阵列是多少你要买什么？所以，你可以得到幸运，以及。这其中，最后，ωn日志n。因此n日志n，我们并没有真正谈谈，但 - 观众：合并排序？国宝马兰：合并排序。这是扣人心弦的最后时间，我们提出，我们发现视觉上，有算法。并合并排序只是一个这样的基本上是更快的算法，该算法一些这些家伙。事实上，合并潜在不仅在当n日志N，在最坏的当n日志Ń的。而当你有这样的巧合欧米茄和大O是同样的事情？事实上，我们可以描述什么称为θ，然而它是一个少一些常见的。但是，这只是意味着两个界限，在这种情况下是相同的。所以合并排序，这是什么真正归结到我们吗？嗯，记得的动机。让我拉起另一个动画我们没有看最后一次。这一次，同样的想法，但它是一个更大一点。而且我要继续前进并指出第一 - 我们有插入排序左上角，然后选择排序，冒泡排序，一对夫妇的其他种类 - 外壳和快速 - 我们没有谈到，堆和归并排序。因此，至少尽量集中你的眼睛顶端3的左边，然后归并排序，当我点击这个绿色的箭头。不过，我就让所有的人都跑，只是让你感受到的多样性在世界上存在的算法。我打算让这个运行短短的几秒钟。如果你专注于你的眼睛 - 挑算法，它只是一个专注于秒 - 你将开始看到了模式，它的实施。归并排序，通知，就完成了。堆排序，快速排序，壳 - 如此看来，我们推出三最差算法上周。但是，这是很好的，我们今天在这里看归并排序，这是一个容易的是看，甚至虽然它可能会弯曲你的心只是一点点。在这里我们可以看到多少选择排序吸。但在另一面，它是确实很容易实现。也许P设置3，这是一个算法选择实施标准版。完美的罚款，完全正确的。但同样，当n变大，如果你选择来实现更快的算法喜欢归并排序，赔率是较大且更大的投入，你的代码仅仅是要跑得更快。您的网站更好的工作。你的用户会更快乐。因此，有这些效果实际上是给我们一些更深层次的思考。因此，让我们来看看什么合并排序实际上是一回事。很酷的事情是，合并排序仅仅是这一点。再次，这是我们称为什么伪代码，伪代码的存在类似英语的语法。和简单迷人的排序。所以输入n个元素 - 只是意味着，这里是一个数组。它有着N个东西。这就是我们说有。如果n小于2时，返回。所以，这只是微不足道的情况下。如果n是小于2，那么它显然 1或0，在这种情况下的事情已经排序或不存在的，所以刚刚返回。有什么可以做。因此，这是一个简单的情况下拔掉。否则，我们有三个步骤。的左半部分的元素进行排序，排序的右半部分的元素，然后合并排序的一半。这里，有趣的是，我样的撑船，对不对？有一种循环定义该算法。在什么意义上是这样的算法定义圆？观众：[听不清]。国宝马兰：是啊，我的排序算法，它的两个步骤“排序东西。“于是引出了一个的问题，以及什么我要使用排序的左半和右半边？而这里的美景，即使再次，这是心态弯曲一部分潜在的，你可以使用相同的算法排序的左半。但是且慢。当有人告诉你排序左前卫，什么是两个步骤将成为下一个？我们将左半部分进行排序左半边和右一半的左半边。该死，我怎么排序，这两个半，或宿舍，现在呢？但是，这是确定的。我们这里有一个排序算法。即使你可能会担心首先，这是一种无限循环，这是一个周期，这是从来没有的将要结束 - 它是将最后一次发生了什么？当n是小于2。最终将要发生，因为如果你继续减半减半在减半这些半，肯定最终，你要结束与仅有1或0个元素。在这一点上，这种算法说，你就大功告成了。所以，真正的魔力在这算法似乎是在这最后的一步，合并。那个简单的想法，只是合并两个的东西，这就是最终的让我们对数组进行排序，比方说，8个元素。所以，我有八个压力球在这里，8个纸片，和一个谷歌玻璃 - 这是我得到保持。 [笑] DAVID马兰：如果我们可能需要8 志愿者，让我们来看看，如果我们能玩这个了，所以。哇，好。计算机科学是越来越有趣。好的。所以如何你三，最大的手在那里。四个在后面。怎么样，我们会做你三此行？四个在前面。所以，你八，上来吧。 [笑] 国宝马兰：我其实不知道它是什么。它是压力球？台灯？该材料？在互联网上？确定。所以来了。谁愿意 - 保持上来。让我们来看看。这使你的位置 - 你在第一的位置。嗯，哦，等一下。 1，2，3，4，5，6，7 - 哦，好。好吧，我们是很好的。好吧，所以大家有一个座位，但不是谷歌的玻璃上。让我排队这些了。你叫什么名字？米歇尔：米歇尔。国宝马兰：米歇尔？好吧，你得到的样子怪胎，如果这是确定的。嗯，我也这样做，我想，只是一瞬间。所有权利，备用。我们一直试图想出一个使用的情况下，我们对Google玻璃认为这将是有趣的只是做当人们在舞台上。我们会记录世界从他们的角度。好的。可能是谷歌意。好吧，如果你不介意穿这下一尴尬分钟，那将是美好的。所有的权利，所以我们这里有一个数组元素，该阵列，每纸片在这些人“ 手，是目前排序。米歇尔：噢，那是太怪异了。 DAVID马兰：这是非常随机的。在短短的时刻，我们要尝试实施合并排序看到这一关键洞察力。这里的技巧与归并排序的东西，我们没有假设。我们确实需要一些额外的空间。那么，这是怎么回事要特别有趣的是，这些附近有一座小家伙要移动位，因为我将假设有一个额外的数组空间，也就是说，在他们身后。所以，如果他们自己的椅子后面，这是辅助阵列。如果他们坐在这里，这是主阵列。但是，这是一种资源，我们有迄今没有利用泡沫排序，选择排序，用插入排序。回想上周，每个人都只是样的洗牌。他们没有使用任何额外的内存。我们的空间让人们移动周围的人。因此，这是一个关键的洞察力。有这种权衡，一般在计算机科学，资源。如果你想加快东西如时间，你要必须付出一定的代价。那些价格是非常频繁空间的内存量或硬您正在使用的磁盘空间。或者，坦率地说，程序员的时间。多少时间，它需要你，人类，真正实现多一些复杂的算法。但今天，权衡是时间和空间。所以，如果你们能托起你数字，所以我们可以看到，你确实匹配4，2，6，1，3，7，8。优秀的。所以我要去尝试，以协调的东西，如果你们可以只跟随我的领导在这里。所以，我要实现，首先，第一步骤的伪代码，这是在输入n个元素，如果n是小于2，然后返回。显然，这不适用，因此我们继续前进。因此，排序的元素的左半部分。因此，这意味着我要专注我这些只是一瞬间的关注四个家伙在这里。好吧，接下来我该怎么办？观众：排序的左半边。国宝马兰：所以现在我有排序这些家伙的左半边。因为再次，假设自己的的目标是要排序的左半边。你怎么做到这一点呢？只要按照上面的指令，即使虽然我们做了一遍。因此，排序的左半边。现在，我这两个家伙排序。下一步是什么？观众：排序的左半边。国宝MALAN：排序的左半边。所以，现在这些，这个座位在这里，是一个大小为1的列表。你叫什么名字呢？公主DAISY：黛西公主。国宝马兰：黛西公主就在这里。于是她，因为已经排序该列表是大小为1。接下来我该怎么办？ OK，返回，因为该列表大小为1，小于2。那么什么是下一步？现在你有样的原路返回，在你的心中。排序的右半边，这是 - 你叫什么名字？ LINDA：琳达。国宝马兰：琳达。因此，我们应该做些什么，现在我们有一个列表的大小为1？观众：返回。 DAVID马兰：小心。我们先回来了，现在的第三一步 - 如果我描绘现在拥抱的两个席位，现在我合并这两个元素。所以，现在不幸的是，元素秩序。但是，这就是合并过程开始引人注目。所以，如果你们能站起来，只是片刻，我需要你，在一个此刻，加强你的椅子后面。并且如果琳达，因为图2是小于4，你为什么不首先你来到我身边吗？呆在那里。所以，琳达，你过来先。现在，在现实中，如果它只是一个数组我们可能只是她的实时移动这把椅子到这个地方。所以，想象一下，采取了一些常数步骤1的数。而现在 - 但我们需要把你的这里的第一个位置。而现在，如果你能来到我身边，好了，我们要去在位置2。即使这感觉像服用了一段时间，什么是好的现在是的左半部分现在左半排序。是下一步骤中，如果我们现在进一步倒转的故事？观众：右半边。 DAVID马兰：排序的右半边。所以，你们必须这样做，以及。所以，如果你能站起来只是一瞬间吗？你叫什么名字？ JESS：杰西。国宝马兰：杰西。 OK，所以Jess是现在的左的右半部分的一半。所以她的大小为1的列表。她显然排序。和你的名字吗？米歇尔：米歇尔。国宝马兰：米歇尔显然是大小为1的列表。她已经排序。所以现在发生的魔力，合并过程。那么，谁将会第一次来吗？显然，米歇尔。所以，如果你能过来。我们现在为她提供空间后面这把椅子在这里。而现在，如果你能回来，我们现在有，是明确的，两个半，每个的大小为2 - 刚刚描绘的缘故，如果你可以使一点点的空间 - 一个左半在这里，其中一个右半这里。故事倒带进一步。什么样的步骤是下一个？观众：合并。国宝马兰：所以现在我们必须进行合并。这样就OK了，所以现在，令人欣慰的是，我们刚刚释放了四把椅子。因此，我们已经两次使用尽可能多的内存，但我们可以给之间倒装假摔两个数组。因此，这数字是先来？因此，米歇尔，很明显。所以来到我身边，并采取您的座位在这里。然后数字2是明显接下来，你来这里。第4号，6号。再次，即使有一个点点步行涉及，说真的，这些可能发生的瞬间，移动 - OK，很好的发挥。 [笑] 国宝马兰：现在我们在相当良好。的左半部分的整个输入现在已经被排序。所有的权利，让这些家伙我的优势 - 它是怎么结束了所有女孩子对离开和所有的男孩在右边？ OK，这样的家伙现在轮到。所以，我不会走你通过这些步骤。我们可以看到，如果我们可以重新相同的伪代码。如果你想提前去站起来，你们这些家伙，让我给你话筒。如果你不能复制什么我们在这里只是做列表中的另一端。谁需要先发言，基于该算法？因此，解释你在做什么之前，你做任何脚的动作。扬声器1：好吧，这样以来我的左半部分左前卫，我返回。对吗？国宝马兰：好。扬声器1：然后 - 国宝马兰：谁做麦克风去下一个？扬声器1：下一个号码。扬声器2：所以我的右半边的左半部分左半边，而我回来。国宝马兰：好。你回来。所以，现在你们两个什么是下一个向上？扬声器2：我们希望看到谁较小。 DAVID马兰：没错。我们要合并。我们要用来合并空间你进入，即使它们显然已经排序，我们将遵循相同的算法。那么，谁去先回来？因此，心情，和7。现在的麦克风去这些家伙，好不好？扬声器3：所以我的右半边左半边，我Ñ小于 1，所以我只是要通过 - 国宝马兰：好。扬声器4：我的右半部分右半边的右半边，而我还一个人，所以我要返回。所以，现在我们合并。扬声器3：所以，我们回去吧。 DAVID马兰：所以，你到后面去。所以第一，然后按8。而现在的观众，这是步骤我们现在倒带备份在我们的脑海中？观众：合并。国宝马兰：合并左半边和右一半的原始左半。所以，现在 - 只是为了让这一点，一点点的空间你们之间的两个家伙。所以，现在的两个列表，左，右。那么我们怎么现在合并你们到前排座椅吗？ 3先行。然后，很明显。然后，7，8。 OK，现在我们是谁？观众：没做过。国宝马兰：没做过，因为显然，有一个剩余步骤。不过，我之所以要使用这像“倒带在你的心中，行话” 这是因为这是真的发生了什么。我们将通过所有这些步骤，但我们暂停一排序的时刻，潜水深入到算法，停顿了一会儿，潜水深入算法，并现在我们要排序退我们头脑和撤消所有这些层排序，我们已经暂时搁置。所以现在我们有两个列表大小为4。如果你们能站起来，最后一次和这里一点空间清楚，这是左原来，一半右原来的一半。谁是第一个数字，我们需要拉进后面？米歇尔，当然。所以我们把这里的米歇尔。 2号？ 2号上回好。编号3？优秀的。 4号，5号，6号， 7号和8号。 OK，所以觉得好像有很多步骤，是肯定的。但现在让我们来看看，如果我们不能确认那种直观的，这算法从根本上，特别是作为 n变真的大，正如我们已经看到的与动画，是从根本上更快。因此，我要求这个算法，在最坏的的情况下，即使在最好的情况下，是大O n次日志n。即，存在的一些方面，这算法需要n个步骤，但还有另一个方面某处该迭代循环，需要记录n步。我们可以把我们的手指放在什么那些两个数字是指什么？嘛，哪里 - 麦克风到哪去？扬声器1：将日志n是我们一分为二 - 除以二，本质上。 DAVID马兰：没错。我们看到在任何时候，任何算法，从而目前为止，这种模式分裂，分化，分裂。它一般会降低东西是对数，底数2。但是，真的有可能是任何东西，但登录基地2。现在什么的n？我可以看到，我们把你家伙 - 你分，分，分，分。哪里到底从何而来？因此，它的合并。因为去想它。当你合并在一起，八人其中一半是一套四，而另一半是另一种四，你怎么去做合并？好了，你们做到了相当直观。但是，如果我不是做这一点更有条不紊，我可能已经指向最左边的人先用我的左手手，指着最左边的人用我的右手，有一半只是后来走过名单，指着最小的元素每一次，我的手指移动和超过所需要的整个列表。但是，什么是这个合并的关键过程是我比较这些对的元素。从右侧的一半，从左边半，我从来没有一次回溯。因此，合并本身正不超过n个步骤。多少次我有合并做到这一点呢？嗯，不超过n，我们只是看到最终的合并。因此，如果你做的东西，需要日志n步n次，反之亦然，这将会给我们日志n n次。这是为什么更好？那么，如果我们已经知道该日志 n是大于n - 对吗？我们看到在二进制搜索，电话簿例如，日志n为绝对优于线性。因此，这意味着Ñ次日志n是肯定比n倍另一个 N，又名Ń平方。这就是我们最终的感觉。这么大的掌声，如果我们可以为这些家伙。 [掌声] 国宝马兰：你的临别礼物 - 你可以保留的数字，如果您想。和你的临别礼物，像往常一样。哦，我们会送你的画面，米歇尔。谢谢。好的。帮助自己的应力球。让我拉起来，在此期间，我们的朋友罗布·鲍登提供有些不同的观点，在此，因为你可以想想这些步骤发生在一个有点不同的方式。事实上，建立罗布的向我们展示了，假设我们已经做了瓜分大名单分为八个小名单，每个大小为1。所以，我们要改变一个伪代码点点得到的只是排序如何合并工程的核心理念。但运行时间是什么他做的仍然是将是相同的。再次，在这里设置的是，他的开始有八个列表的大小为1。所以你错过了他的部分实际上做日志日志N，N，日志N 除以输入。 [视频回放] 这是它的第一个步骤。步骤二，反复合并成对的名单。国宝马兰：嗯。只有音频出我的电脑。让我们试一次。只是随便挑 - 现在，我们有四个名单。了解之前。国宝马兰：我们走吧。合并108和15，我们最终与列表15，108。合并50和图4中，我们结束与4，50。合并8和42，我们结束与8位，42。和合并23日和16日，我们结束与16，23。现在我们的名单是大小为2。请注意，各四个列表进行排序。因此，我们就可以开始合并再次对列表。合并15和108和4和50，我们先取4，然后15，然后 50，那么108。合并8，42，16，23，我们先来 8，然后16，然后23个然后42。所以，现在我们只有两个列表大小 4，其中每一个进行排序。所以，现在我们合并这两个列表。首先，我们4，然后我们把 8，然后我们采取了15，然后16，然后 23，42，50，108。 [END视频播放] 国宝马兰：同样，请注意，他从来没有触动了杯一次以上之后超越它前进。所以他从来不重复。所以他总是移动到一边，这就是我们得到了我们的Ñ。为什么不让我拉起一个动画我们前面看到的，但是这一次只专注于合并排序。让我继续前进，放大在此。首先，让我选择一个随机输入，放大这一点，你可以看到排序我们采取了什么是理所当然的，早些时候，合并排序，实际上做。因此，发现，你得到这些半或这些宿舍或这些八分之问题一下子开始采取良好的形状。然后，最后，你看到最末端，咣当，一切都合并在一起。所以这些都只是三种不同采取同样的想法。但关键的洞察力，就像鸿沟和征服的第一类，是我们决定以某种方式划分问题变成大的东西，进入排序相同的精神的东西，但更小的和更小的和更小的和更小的。现在，另一个有趣的方式来排序认为这些，即使它不是打算给你相同的直观理解，是下面的动画。所以这是一个视频的人放在一起相关不同与各种不同的操作的声音插入排序，归并排序，其他几个。因此，在某一时刻，我会打游戏。它是大约一分钟长。即使你仍然可以看到发生的模式，这时候你可以也听到这些算法如何不同的执行与有所不同的型态。这是插入排序。 [提示音播放] 国宝马兰：再次尝试每个元素插入到属于它的地方。这是冒泡排序。 [提示音播放] 国宝马兰：您可以排序的感觉如何相对较少的工作，它在做什么对每一个步骤。这是沉闷听起来像。 [提示音播放] 国宝马兰：这是选择排序，我们选择我们想要的元素再次经历一次又一次并把它的开始。 [提示音播放] 国宝马兰：这是归并排序，你可以真正开始感觉。 [提示音播放] [笑] 国宝马兰：名为gnome的东西排序，我们没有看过。 [提示音播放] 国宝马兰：所以让我看，现在，你希望是由分心音乐，如果我能稍有闪失数学位在这里。因此，还有第四种办法，我们可以想想这意味着什么功能比那些快我们已经看到过。如果你未来在课程数学的背景，你其实也许已经知道，你这种技术可以一巴掌长期 - 即递归函数以某种方式调用自身。再次，记得归并排序在这个意义上的伪代码是递归一个合并排序的步骤是打电话排序 - 也就是说，本身。但令人欣慰的是，因为我们一直呼叫排序，归并排序，具体地，在一个较小的和更小的和较小的名单，我们最终走出谷底，感谢我们就这么叫基地的情况下，硬编码的情况下，说，如果列表很小，不到2 在这种情况下，就立即返回。如果我们没有这种特殊情况，算法绝不会走出低谷，事实上，你会进入一个无限循环，真正的永远。但是假设我们希望现在就把在此，再次一些数字，使用n 作为输入的大小。我想问问你，有什么涉及的总时间执行合并排序？或更普遍的，有什么它的成本的时间吗？那么这是很容易衡量。如果n是小于2时，所涉及的时间在n个元素进行排序，其中n为2，为0。因为我们刚刚返回。有没有工作要做。现在可以说，也许这是一个两步步骤弄清楚的金额工作，但它足够接近0 我只是说没有工作如果需要的名单是如此之小无趣。但有趣的是，这种情况下。递归分支别人说的伪排序的左半边，排序的权利一半，合并的两半。为什么会发生这种表达表示该费用？嗯，T为n的意思是，时间排序n个元素。然后在右手侧的等号，划分为n的T 2是指，以什么样的成本？排序的左半。其他T除以2的n 大概是指的成本排序的右半边。然后加N？被合并。因为如果你有两个列表，一个是大小为n超过2和其他大小为n 2，你必须基本上触摸这些元素，就像罗布感动每个杯子，只是正如我们在每个志愿者们在舞台上。因此，n是合并的费用。不幸的是，现在这个公式本身也是递归的。所以，如果问的问题，如果n是说， 16，如果有16人在舞台上在视频或16杯，总共有多少个步骤，它需要对它们进行排序归并排序？它实际上不是一个明显的答案，因为现在你有排序递归地回答这个公式。不过没关系，因为让我提出我们做到以下几点。所涉及的时间，16人进行排序或 16杯将要被表示的一般为T 16。但是，这等于，根据我们的前面的公式，2倍量所花费的时间进行排序 8杯加16。再次，加16是合并的时候，两个时间T 8是左半边和右半边的时间进行排序。但是，这是不够的。我们必须在更深的潜水。这意味着我们必须回答问题，什么是T的8？ T的8井仅2 4加8的时间T。那么，什么是T的4？仅有2 2加4倍t T的4。那么，什么是T的2？仅有2倍的T 1加2的T 2。再次，我们是一种越来越在这个循环中卡住。但它即将袭来所谓的基本情况。因为什么是T的1，我们要求？ 0。所以，现在我们终于可以倒退。如果T 1是0，我现在可以回去最多一个这个家伙在这里排队，我可以插头为T 0 1。因此，这意味着它等于2倍零，否则被称为0，加2。使整个表达式为2。现在，如果我走T 2，其答案 2，将其插入中间线，T 4，给我的2倍 2加4，所以8。如果我再插在8到前行，这给了我2次，8，16。而如果我们再继续，随着 24，增加16，我们终于得到一个值64。现在，本身并排序讲无关的符号n，大O，欧米茄，我们已经看到一直在谈论。但事实证明，64确实是如图16所示，输入大小，登录基地2 16。如果这是一个有点陌生，只是回头想想，它会回来你最终。如果这是2为底，它就像2 提出了什么给你16？哦，那是4，所以它的16倍4。再次，它不是一个大不了的，如果这现在是那种朦胧的记忆。但现在，信仰 16日志16是64。因此，事实上，这个简单的理智检查，我们确认 - 但没有正式证实 - 运行时间合并排序的确是N个记录Ñ。所以不坏。这绝对是优于到目前为止，我们已经看到，算法这是因为我们已经利用，一，一种技术，称为递归。但比这更有趣，概念的分裂和征服。再次，真正实现0周的东西，即使现在是反复出现在更引人注目的方式。现在一个有趣的小运动，如果你从来没有做过这样的 - 你可能不会有，因为正常排序人们不认为做到这一点。但是，如果我去google.com和我想了解一些有关递归，回车。 [笑] [笑声] 国宝马兰：糟糕的玩笑慢慢蔓延。 [笑] 国宝MALAN：以防万一，它的存在。我没有拼写错了，的笑话。好的。解释一下你旁边的人，如果但相当点击只是还没有。但是，递归，更一般地，是指的过程中的函数调用本身，或者更一般地，将一个到东西，可以是问题头痛医头，脚痛医脚的解决解决相同代表性的问题。好吧，让我们改变齿轮只是一瞬间。我们喜欢在某些悬念结束，让我们开始设置在舞台上，几分钟，一个非常简单的想法 - 交换两个元素，对不对？所有这些算法，我们已经谈论过去几讲座涉及到一些交换排序。今天，它是用他们得到出自己的椅子，走动，但在代码中，我们将只是从一个数组元素扑通到另一个。那么，我们如何去这样做呢？好吧，让我继续写这里的快速程序。我要继续做这是以下。让我们把这个 - 我们要调用这个什么？事实上，没有。让我快退。我不想这样做吊人胃口。它会破坏其中的乐趣。让我们做到这一点，而不是。假设我想写一点现在方案，并拥抱递归的想法。我种了自己。我要做到以下几点。首先，快速包括标准io.h 以及包括cs50.h. 然后我要继续前进并宣布INT主要无效在通常的方式。我意识到我已经名不副实的文件，所以我想补充的扩展名，在这里，所以我们可以正确编译。启动此功能。的功能，我想写点什么，相当简单地说，就是要求用户输入一个数字，然后添加之间的数字数，并说，0。所以，首先我要继续前进并宣布INT N。然后我复制一些代码，我们已经使用了一段时间。虽然东西是真实的。我会回来在某一时刻。我想要做的是什么呢？我想说的printf积极请整数。然后我要去说N变得到诠释。如此反复，一些样板代码我们以前用过的。我要做到这一点而n是小于1。因此，这将确保用户给我一个正整数。现在我要做到以下几点。我想补充的所有号码介于1和n或0且n 等价地，得到的总和。所以大的sigma符号您可能还记得。所以我要做到这一点首先调用一个函数调用西格玛，在n传递给它，然后我要去 printf的说，答案是正确的。因此，在短期，我得到 int的来自用户的。我保证它的正面。我声明了一个变量叫做答案 int类型，存储在它的回报西格玛值作为输入，通过在n。然后，我打印出这个问题的答案。不幸的是，即使西格玛的声音喜欢的东西，可能是在 math.h的文件，它的声明，它实际上不是。所以，这是确定的。我可以实现自己。我要去执行一个函数调用标准差，它会采取参数 - 让我们只是把它M，只是所以它是不同的。然后在这里，我要说的话，以及，如果m是小于1 - 这是一个很无趣程序。所以，我要继续前进，立即返回0。它只是无厘头加起来如果m 1和m之间的数本身是0或负数。然后我要继续前进做到这一点非常迭代。我会做这样的老派，我要继续前进并说，我要去声明总和为0。然后，我将不得不一个循环的int - 并让我这样做符合我们的分销代码，让您拥有一个副本在家里。 INT I上得到1 i是小于或等于m。我+ +。然后将里面的for循环 - 我们几乎没有 - 总和得到的总和加上1。然后我要返回的总和。所以我这样做很快，诚然相当。但同样，主要功能是相当简单的，基于代码我们已经书面迄今。采用双循环，得到了肯定 int的来自用户的。然后，我通过这个int到一个新的功能叫西格玛，调用它，再次，正。我存储的返回值，得到的答案从目前黑盒子已知作为σ，在一个变量中叫的答案。然后，我打印出来。如果我们现在继续的故事，西格玛是如何实施？我建议如下推行。首先，一点点的错误检查以确保该用户的不梅辛与我并传入一些负面或0值。然后我声明了一个变量综上所述，将它设置为0。现在，我开始从i等于 1所有的方式，包括米，因为我想包括所有数字从1到m，首尾。这里面的for循环，我只是做总和得到现在不管它是什么，再加上 i的值。加上i的值。顺便说一句，如果你没有看到这之前，有一些语法糖此行。我可以改写为加等于I，只是为了保存自己敲几下键盘看起来有点凉。但是这一切。它的功能同样的事情。不幸的是，这种代码的不会还编译。如果我运行make的西格玛0，怎么我我大叫？什么是它不喜欢呢？观众：[听不清]。国宝马兰：是啊，我没有申报向上顶，右边的功能？ C是一种愚蠢的，它仅做什么你告诉它的事情，而你必须这样做的顺序。所以如果我打在这里输入，我要关于Sigma隐警告声明。哦，不是一个问题。我可以去到顶部，我可以说，没事的，请等待一分钟。六西格玛是一个函数，返回一个int，并预期 int作为输入，分号。或者，我可以把整个功能上述主要的，但在一般情况下，最好针对该建议，因为它是很高兴上面的顶部，所以总是有主可以潜水的权利，并知道什么是程序首先通过阅读主要做。所以，现在让我清楚的画面。重拍0西格玛。所有似乎退房。让我跑SIGMA 0。正间。我给它的数量 3，以保持它的简单。所以，应该给我3 加2加1，所以6。回车，我确实得到6。我可以做更大的东西 - 50，12，75。正如切线，我要做的可笑的东西像一个真正的大号，呵呵，那实际工作 - 诶，我不认为这是正确的。让我们来看看。让我们真的惹它。这是一个问题。这是怎么回事呢？该代码是没有那么糟糕。它仍然是线性的。吹口哨是一个很好的效果，虽然。这是怎么回事呢？不知道如果我听到它。因此，原来 - 这是作为一个旁白。这不是核心到递归的想法。事实证明，是因为我试图代表这样一个大的数字，最它可能被误解 C作为一个并不乐观的数字，但负数。我们还没有谈到这一点，但它原来有负数在世界上除了正数。和手段，通过它可以表示负数基本上是，你使用一个特殊的位来指示正面负面以上。这是一个有点比这更复杂，但是这是最基本的想法。不幸的是，如果C是混乱的一个那些位作为实际意义，哦，这是一个负号，我的循环在这里，例如，实际上是从来没有要终止。所以，如果我实际打印的东西一遍又一遍，我们会看到一大堆。但是，这是除了点。这是真的只是一种对知识的好奇心，我们还会回来最终备份。但现在，这是一个正确的如果我们假设执行用户将提供整数适合内整数。但我要求这个代码，坦率地说，可以做简单得多。如果在手的目标是采取多项像米，加起来所有的之间的数字，并且1，或反过来介于1和它，我要求我可以借用这种想法，合并排序了，这是一个问题这种规模和分割成更小的东西。也许不是一半，但规模较小，但代表性地是相同的。同样的想法，但一个较小的问题。因此，实际上，我 - 让我好好保存这个文件不同的版本号。我们称这个版本 1而不是0。我要求其实我可以这种重新实现此心态弯曲方式。我要独自离开它的一部分。我会说，如果m是或者甚至等于0 - 我只是要一点点肛门我的错误检查 - 我要继续前进，返回0。这是任意的。我只是简单地决定，如果用户我给了我一个负数，返回0，他们应该已经读过的文档更加紧密。其他 - 注意什么，我要做的事情。否则，我要返回米加 - 什么是西格玛米？那么，Σ的m加m减1，加m的负2，加m零下3。我不想写出来。我为什么不只是撑船？递归调用自己稍微规模较小的问题，分号，收工？对吗？现在在这里，太，你可能会感到或担心这是一个无限循环，我诱导，由此我实现西格玛致电西格玛。但是，这是完全确定的，因为我想提前增加了哪条线路？观众：[听不清]。国宝马兰：23日至26日，是我的，如果条件。因为关于什么是好的减法这里，因为我保持交给西格玛小问题，小的问题，更小的 - 它不是的一半大小。这只是一小步，不过没关系。因为最终，我们将继续努力我们一路下跌为1或0。一旦我们打0，Sigma的不会调用本身了。这将立即返回0。所以效果，如果你样的风在你的心中，是增加M PLUS M减1，加m减2，加m减 3，加点，点，点，M减米，最终给你0，最终效果添加的所有这些东西放在一起。所以，我们还没有，用递归解决了这个问题，我们之前没能解决。事实上，版本0，每问题到今天为止，已经解只需使用循环或在循环或类似的结构。但是，递归，我敢说，给我们以不同的方式思考问题，因此如果我们可以采取一个问题，除从东西到有些东西有点大较小的，我要求，我们可以解决这个问题也许是多了几分优雅条款设计，用更少的代码，甚至解决的问题，会更难，因为我们最终会看到，解决纯属迭代。但扣人心弦的，我没有要离开我们是这样的。让我继续前进，打开一个文件 - 其实，让我去这样做真正的快。让我继续前进，并提出以下。其中今天的代码是这样的文件在这里。在这里，这一个noswap。所以这是一个愚蠢的小程序，我掀起了要求做以下。在main中，它首先声明为int，名为x和分配为1的值。然后，它声明int y和分配值2。然后打印出x和y是什么。然后，它说，交换，点点点。然后，它声称要调用一个函数称为交换，传递x和 Y，其中的想法是，希望 x和y会回来不同的，相反的。然后，它声称交换！一个惊叹号。然后打印出x和y。但事实证明，这很简单的演示下来这里是实际马车。即使我宣布一个临时的变量和暂时把它，然后我重新分配一个b的值 - 觉得合理，因为我保存副本的温度。然后我更新b等于无论是在温度。这类壳移动游戏到b和b成通过使用该中间人名为temp的感觉完全合理的。但我要求当我运行这个代码，我现在要做的 - 让我继续前进，将其粘贴在这里。我会打电话给这个noswap.c。顾名思义，这是不将是一个正确的程序。让noswap /无掉。 x是1，y是2，交换，交换。 x为1时，y是2。这是从根本上是错误的，甚至虽然这似乎是完美的合理的，我。还有一个原因，但我们不要揭示的原因，只是还没有。现在我想的第二个扣人心弦的离开你，公布各种优惠券代码。今年我们的创新与已故天激起了不平凡的数字的问题，这是不是我们的本意。这些优惠券代码的意图，据此，如果你这样做是问题的一部分提前设置，从而获得一个额外的一天，真的帮助你们有所帮助自己年初开始，排序激励你。有助于我们之间分配负载办公时间更好地使它的排序共赢。不幸的是，我觉得我的指示没有，到今天为止，已经很清楚，所以我又回到这个周末更新规格更大，更大胆的文字解释这些子弹。只是说它更公开，默认情况下，问题集将于周四日中午，按照教学大纲。如果你起步早，完成一部分周三12:00设置问题下午，部分，涉及到的优惠券代码，这个想法是，你可以扩展您的截止日期为 P设定至周五。也就是说，咬下一小部分的P 设置通常是相对更大的问题，你买自己一个额外的一天。再次，它可以让你思考设置的问题，让你去办公时间越快。但优惠券代码的问题仍是必需的，即使你不提交。但更令人信服的是这样的。（舞台WHISPER），而那些人离开早期是会后悔的。乡亲在阳台上。我提前给乡亲道歉阳台上的原因，这将是清除在短短的时刻。因此，我们很幸运，有一个 CS50的前任主管教学研究员一家名为dropbox.com。他们非常慷慨地捐出了优惠券代码，这里这么大的空间，这是从平时的2千兆字节。所以我想我们会做这个最后要注意的是做一点的赠品，在短短的时刻，我们将揭示赢家有优惠券代码，然后你可以去他们的网站，键入它，瞧，得到了一大堆更多的Dropbox空间为您的家电和您的个人文件。第一，谁愿意参加在该图中？ OK，现在这使得它更有趣。人谁收到这25千兆字节优惠券代码 - 这是远远更引人注目的莫过于后期现在，也许是 - 是一个谁是坐在最重要的一个座垫下方有该优惠券代码。现在，您可以看下面您的坐垫。 [视频回放] 一个，两个，三个。 [尖叫] 你得到一辆车！你得到一辆车！国宝马兰：我们将看到上周三。你得到一辆车！你得到一辆车！你得到一辆车！你得到一辆车！你得到一辆车！国宝马兰：阳台乡亲，来这里到前面，在那里我们有演员。 - 每个人都得到一辆车！人人都有车！ [END视频播放] 旁白：在未来CS50 - 扬声器5：哦，我的天哪天哪天哪天哪天哪天哪天哪天哪天哪天哪 - [UKELELE戏剧]