[音乐播放] DAVID J.马兰所有权利。因此，欢迎回来。这是CS50，和本周三结束。所以，记得在过去的几个星期中，我们已经花了相当多的 C，对编程，语法的时间。这是相当正常的，如果你还在挣扎与习题集2，撞你的头靠在墙上。这是神秘的前瞻性的错误消息和错误，你不太能追下去。因为，放心好了，在短短几个星期的时间，你会回头看凯撒之类的东西，[？ V-genair？] 甚至裂纹，实现你来多远在很短的一段时间。因此，如果这是任何安慰，现在挂在那里。今天，虽然我们开始转型的东西更高的水平。我们开始想当然你们知道如何编程，或者至少开始，舒适的水平。我们将开始考虑我们如何能够设计方案更多有效。我们如何去优化我们的算法的效率，并一般解决更多有趣的问题。并开始想当然地认为，如果我们想，我们可以编写任何我们心目中的例子。因此，我们今天不要触摸键盘任何形式的代码。这将是更高的水平，最终的问题解决。所以到这一点，让我提出，下列7项矩形代表七个门，后面这是一个一大堆号，其中数字50。让我在此项目屏幕在这里。并提出，我们需要一个志愿者帮我找一个前面的数字看到这里的互联网。上来吧，在粉红色的。好的。你叫什么名字？詹妮弗：[听不清] 国宝，J. MALAN：对不起？詹妮弗：詹妮弗。 DAVID J.马兰：珍妮弗。所有权利，珍妮弗。认识你很高兴。上来吧。因此，这些这里有7个门，什么我希望你能在这里为我们做的，在所有的同学面前，找到我们的号码，50。要找到一个号码，你可以窥见背后这些门通过简单轻敲一个门，它将揭示其编号。，让我们看看你的速度有多快可以找到我们的号码，50。 15。 16。 50。干得漂亮。好的。圆形，珍妮弗的掌声。 [掌声] 好的。那么，什么是你的策略找到的数目，50？詹妮弗：嗯，我想，也许 - [听不清] DAVID J.马兰：哦。给它一秒钟。所以，你的战略找到的数目，50？珍妮花：所以我刚开始在开始看到的第一个数字，然后我想，也许，如果他们排序，我就继续攻高了？ DAVID J.马兰：“确定”。我们似乎已经找到的情况下。虽然，让我们剥开层层只是一点点，你想要去的提前透露其他门你也可以选择吗？詹妮弗：哦，亲爱的。 DAVID J.马兰：啊。珍妮花：所以我只是很幸运。 DAVID J.马兰：所以你很幸运。好的。所以不坏。但是，这是一个有趣洞察力，对不对？如果你认为，你没有得到，着实有点幸运有。但是如果你假定数字排序，你可以更精确如何影响你的行为？珍妮花：所以，如果他们进行排序，我想，也许从最小到最大。 DAVID J.马兰：“确定”。詹妮弗：或者，如果这结束了真大，然后从最大到最小。 DAVID J.马兰：“确定”。所以从最大到最小，或者从最小到最大。但是，让我提出，假设您有倒霉了，以为他们不，实际上，分类，有多少这些门可能你有偷看落后，最坏的情况下？珍妮花：他们所有。 DAVID J.马兰：他们所有。因此，让我们概括为n。恰好是7，但是让我们更一般说有Ñ门这里的屏幕。因此，在最坏的情况下，你将不得不看7门，或n门背后。所以这真的是，这是一个有点今天的运气，但它是一个真正的线性各种各样的算法，即使你那种跳绳周围。这公平吗？珍妮花：是啊。 DAVID J.马兰：嗯，让我看看你的策略的改变，如果我感动我们这里我们的第二个例子 7种不同的门。相同的数字，但是这时间进行排序。什么是你的战略将是，试图把你的头脑是什么其他的数字是 - 詹妮弗：OK。 DAVID J.马兰： - ？珍妮花：让我们开始与第一个。 DAVID J.马兰所有权利。开始的第一个。 4。现在，在那里你会去，为什么呢？珍妮花：4是真的小。所以，如果他们是那种也许最小最大的，它应该的两倍，以及 - 。 DAVID J.马兰：“确定”。让我们来看看，你觉得呢？詹妮弗：最后一个尝试。尼斯。 DAVID J.马兰：非常好做。好的。 [掌声] DAVID J.马兰：“确定”。所以其实你这样做可怕的，因为你这样做很好。使我们无法使某些要点。因此，让我们在这里尝试回滚。詹妮弗：OK。 DAVID J.马兰：很好做了，尽管如此。所以，你开始之初，你看到，这是4，那么你移到末尾。但是，假设你没有得到幸运在那里，假设50 别处。你的第三步怎么办？詹妮弗：返回到开头。 DAVID J.马兰：返回到开头。好了，你会一直感动这门，这是8。好的。所以，这不是50个。你会在哪里看过？詹妮弗：如果我没有知道他们排序。 DAVID J.马兰：正确。好吧，如果你不知道他们进行了排序 - 詹妮弗：哦，知道，是啊。 DAVID J.马兰 - 但你没有知道其中50还在吗？珍妮花：只要坚持下去。 DAVID J.马兰所有权利。确定。继续下去。 OK，我可以工作。詹妮弗：OK。 DAVID J.马兰：现在，如果你只是要继续下去，你叫什么算法下放备份成。 JENNIFER：线性 - 。 DAVID J.马兰：这是一种线性的。但是，让我提议，让我们我把在现场。让我刷新页面。同样的号码，同样的安排，同门。但回想起在第一天上课的时候，我们撕了电话簿一半，排序，是什么我们的策略吗？詹妮弗：开始在中间。 DAVID J.马兰：“确定”。因此，开始在中间。所以，让我们继续前进，和模拟。开始在中间露出那扇门。因此，数字16。所以，你会强烈的家伙都做了，谁撕了一半，电话簿去下一个猜测？詹妮弗：这半场。 DAVID J.马兰：为什么了吧？詹妮弗：如果他们最小到最大，然后50 为此。 DAVID J.马兰：好。完全合理的。所以像电话簿，你去的权利，而不是左侧，但在这里关键是外卖。您现在可以扔掉，或撕下，这个问题的一半，让你不 7门，但实际上仅有3。这是大约一半的大小的问题。好的。所以，现在你将有什么完成后，你向右走？珍妮花：所以16还是蛮小的，相对于50，也许我会尝试，像这一个。 DAVID J.马兰所有权利。 42。所有的权利，所以现在你叫什么本能告诉你吗？珍妮花：我可以扔掉这一点，然后只是 - DAVID J.马兰：“确定”。好，你可以扔掉的左半。詹妮弗： - ，拿起这一个。 DAVID J.马兰的权利。珍妮花：是啊。 DAVID J.马兰：所以，即使它很难或许看到，当有只 7门，想想现在，的一致性你只是算法应用。在以前的情况下，你做得到幸运的，这是伟大的。但你没有使用启发式，我想说的。您使用自己的直觉，知道它的排序，如果它是相当小的开始，很明显，我们已经去了更多的权利。但是，从某种意义上说，你很幸运，因为也许这是100号，也许50是在中间。也许50即使在这里。但你做了什么一点点不同这个时候，你做同样的事情一遍又一遍。我认为，你刚才没有，但通过手机影响书中的例子，多是算法，多特别少套管。更本能。因此，在一天结束的时候，怎么会你描述的效率第一种算法，你在哪里左到右，相对于第二种算法在这里？珍妮花：这个应该，喜欢，也许时间减半，甚至更多，是的。 DAVID J.马兰：好吧，也许甚至更多。让我们一点点推更难。真的，如果我们继续逻辑，我们肯定减半本次算法的运行时间扔掉一半的数字，但没有什么我们做下迭代，当詹妮弗透露第二个数字？门再次减半。然后我们做了什么，如果有更多的门一起玩吗？我们将减半，并再次，一遍，又一遍。这就像你们站在上面的第一周类，你坐下的一半，一半你坐下，你的一半坐了下来，直到一人独行站在灵魂。我们说的运行时间的是，它采取的步数顺序是怎样的？扬声器1：[听不清] DAVID J.马兰：所以底数2的n，或只是更简单，登录的n。因此，对数的东西。和图形是不在一条直线上只是越来越糟，这是没有这个有趣的曲线随着时间的推移变得如此糟糕。因此，让我们保持这种想法。让我们感谢珍妮弗。感谢这么多的最多。一秒钟。没有台灯，但我们确实有CS50应力球。詹妮弗：耶。 DAVID J.马兰：好的，在这里。谢谢你承担应力在这里。好的。所以，让我们来看看，如果我们现在不能正式这一点。所以，再一次，我们刚刚做的是基本上我们做同样的事情在第一个星期。但而不是结束，只是一个线性算法，这是我们描绘以前这条直线，据此，如果我们把一个门屏幕上，然后珍妮弗会不得不看，可能，后面多了一个门。如果我们把两个门，她可能有看看后面两个门。，所以这种线性的大小之间的关系问题，比方说，在x轴，和它需要的时间量解决在y。但画面我被影射早期是这样的绿线。绿色故意的，因为它只是感觉好多了。在理论上，算法，当我们做到了电话簿，当我们做到了你们计数对方，在第二种情况下，当珍妮弗只是做了它在这里，它是从根本上更好。因为它不只是快两倍。它甚至不是快四倍。这完全依赖于什么输入的大小，到底有多少最终步骤了。所以这个简单的想法，我们都拿了为电话簿授予，可以类似地应用这样的东西。这可能是更随便被称为，因为您可能可以想象，分而治之。当然，没有什么不同，我们做了什么，电话簿。但伪代码，召回，是这样的。因此，我们不会做这个了，但记得第一个星期，我们都站了起来然后你的一半坐了下来，一半你坐下，你的一半坐了下来。该算法在一个实施有点作弊的方式，在那，不只是我一个人计数，从根本上说，更有效地。在这种情况下，我被利用二次资源。排序的，多个CPU，多动脑筋，多聪明的人房间帮助我得到的东西线性的东西对数，从东西红色到绿色的东西。但是，在这种情况下，珍妮弗单靠从根本上改善后她的第一个算法的性能，再次，只是想有点困难。而现在，当谈到时间来实现这些东西，搞清楚什么行代码，你能写出这样，你可以重复一遍，一遍，又一遍，排序在循环的方式。因为你不会有做的第一件奢侈品，像珍妮弗，如果只是有一大堆，说嗯，如果这第一个数字是4，让我跳方式结束。哦，如果这个数字太大了，让我回到随意移动到第二元件。你会发现，它将会是一个很大难以形式化我们人类想当然是非常合理的启发式方法，但只有一台计算机是会做你告诉它做。现在，这具有非常有趣的影响。此图意味着排序排序压倒视觉，但是请注意，在那里在该曲线图中的直线是什么？哪里是线性图我们称之为ň？嗯，这是那种朝下方这幅画，是吧？因此，我们所做的是我们排序地图的x轴和 y轴设法得到一个什么样的感觉其他类型的曲线的样子。和具体的数学今天的表达式将不那么重要不多，但发现有很多算法远不如东西是线性的。事实上，N立方看起来很糟糕。 2 n个看起来很糟糕。 Ñ平方看起来很糟糕。，我们将看到一些人可能会在今天的现实。日志N不那么糟糕的感觉，但比n底数2的n。但你知道，它会更更惊人的，如果詹妮弗，或者如果我们第一个星期，想出了东西是n的日志记录。因此，换句话说，这整个可能的解决方案的范围问题，但即使在这里，请注意会发生什么。当我缩小，这些曲线会被证明是绝对现在屏幕上的最差？因此n的立方小艾糟糕的时刻。但是，如果我们放大，看到更多的 x和y轴，谁去最终主宰？因此，它实际上原来，2 n，并且可以算出这个只是通过堵在一些越来越大数字，你会看到2到 N，事实上，获取更大的快得多。如果我们真的缩小，2 绝对吸Ń算法。我的意思是要采取相当多的时间电脑上翻腾通过。但是，你会看到随着时间的推移，特别是甚至与未来问题集最后的项目，为您的数据集变大了，好吗？即使是在Facebook的第一个版本，作为朋友，注册用户的数量得到了大，您可以排序的电话呢执行线性搜索的东西，还是一个很简单的排序算法，今天我们会看到。你必须开始思考更难这些问题更难。和类型的问题的地方，如 Facebook和谷歌，微软，和其他工作，正是这些大数据排序排序问题这些天越来越多。好的。，所以詹妮弗的成功，第二算法，坦率地说，她的确令人惊讶以及第一次，但我们写我的运气，让我们可这一点。在第二种情况下，她利用算法，又重复了一遍，再次，但她认为理所当然的一我们允许若干假设她，但她利用一些细节第二，她没有足够的时间第一次。这是什么？列表排序。所以只要列表排序，我们声称，珍妮弗是能够做到的从根本上更好。 7门，是的，是不是很有趣，但假设我们700万门。 n的日志是一定要去执行很多，很多从长远来看快。但她必须有她门的排序。现在，我带着这样做的自由事先在电脑屏幕上在这里，但假设珍妮弗不得不做自己？假设门问题表示数据库中的数据，或为Facebook注册的朋友，或任何在互联网上的网页可能需要不同的网站索引或搜索过。假设你刚刚有了原始数据设置和它留给你的，或珍妮弗做排序？，而是需要我们回答的问题，好了，多少时间珍妮弗，甚至我会采取这些数字进行排序，提前让她能利用？对吗？因为言下之意，当然是如果它需要我相当长的一段时间排序数字，到底谁在乎你这么快可以找到一个像50，作为在詹妮弗的情况下，如果我们多不堪重负的总时间量了通过分拣事前事中？因此，让我们来看看，如果我们不能这里绘制图片。我有一大堆的压力球，如果有帮助打破这儿的冰。如果你不介意，我们需要七个志愿者 - ，“确定”。哇。因此，我们不必花台灯，它似乎。好的。因此，如何对你们两个在前面。怎么你们俩在后面。所以这是四个。你怎么样在前面五，六，七。就在那里。您的朋友的指点你，所以你得到的奖品。好的。上来吧。为什么不，我们有你你们来就在这里。我去给你们每人一个。继续前进，安排自己相同的是什么在屏幕上描绘。 [插入声音] DAVID J.马兰：OOP，对不起。问题。好的。那么，在这里，我们去。 5号。 6号。一，二，三，四，五，六，七。哦，这是很尴尬。扬声器2：我刚刚得到一个 - 。 DAVID J.马兰：处理好。好的。谢谢您的参与。 [掌声] 确定。好的。因此，我们有四，二，六，一，三，七，五。完美的，所以我们有七个志愿者在这里谁是宽度相等的我们玩的数组与早期的。我选择了七个原因这将是刚方便一点点。我要首先提出，我们梳理这七名志愿者。如果你想，首先，打招呼，虽然。由于这将是一个尴尬几分钟。介绍一下自己。 GRACE：嗨，我是格雷斯。我是一个大二在利维瑞特大厦。布兰森：你好。我布兰森。我是一个大一的焊接。 GABE：你好。我加布。我是一个小辈在Cabot。尼尔：我是尼尔。我一大一马修斯。杰森：我是杰森。我是一个大一格里诺。 MIKE：我是麦克。我一大一灰色。 JESS：我是杰西。我是一个大二莱弗里特。 DAVID J.马兰：优秀。好的。嗯，谢谢你给我们所有的这里的志愿者迄今。现在手头的挑战会是这些家伙排序，但随后我们要觉得有点我们如何有效地实际上努力排序。所以，让我们先试试这个。你们可以看到对方的号码只是把周围的角落。来吧，采取了几秒钟，从最小的排序自己左到最大的在右边。去。确定。好。这真是混账快。现在有人在这里，究竟是什么算法这些家伙的应用呢？扬声器1：最伟大的。 DAVID J.马兰：“确定”。最小到最大还真有几分的目标，但我不知道这是一个真正的算法。最小到最大不告诉我一步一步做什么。是吗？扬声器1：[听不清] DAVID J.马兰：“确定”。所以，如果你看到一个人小于你的电话号码，然后移动到他们的权利。因此，现在越来越多的表现，更像是一个算法，因为你可以说，如果这样，那么这个。因此，我们有某种条件结构。这些家伙似乎做那几个次，因为一些你有点感动的距离。所以大概是有某种循环在他们的头脑中去。但是，让我们尽量正规化，。如果你们能重置回这种布置。让我们来看看如果我们不能正式确定这是一个位，然后问这个问题，只是效率如何？当然，当我们这样做时速度比较慢，它会感觉一样好一种算法，但让我们来看看，如果我们能把我们的手指的精确步骤。所以，你们俩有四个和两个。或您正确或不正确的顺序？显然不正确。所以我们交换。现在，我要移开这里说，四到六。你是正确的或不正确的？ GABE：正确。 DAVID J.马兰：正确。六一？不。交换。所以这是两个互换。六，三个？不。交换。六，七？看起来不错。 7个和5？ JESS：[听不清] DAVID J.马兰：OK，交换。和排序。好的。所以，很显然不是，对不对？于是有更多的事情。不过，说实在的是，这些家伙，即使只是本能。不停地移动。他们不只是停下来，他们一旦纠正一个问题。所以。事实上，我将不得不做同样的事情。我要倒带回来排序此问题的开始，或此数组的开始人，让我们开始打电话给他们。现在应该做些什么算法在第二遍呢？扬声器1：同样的事情。 DAVID J.马兰：同样的事情。而这一点，我开始喜欢，对不对？只要你可以找到自己做同样的事情一遍又一遍，这是变得更像一个算法，人类的本能。所以，现在，在这里，我们又来了。两个和四个？号四之一？嗯，确实有一些工作尚待完成。三？好。四和六？六，五？六，七？ OK，现在，完成。 OK，没。我必须回去。所以，现在，再次，我们正在做这有点刻意。而现在，只是一个大脑执行该算法。一个CPU，如果你愿意。坦率地说，这是唯一的资源我们将有机会获得。一旦我们做回一个键盘和我们有一些像C 处置中，我们只写一个程序可以做一件事的时间。然而，这些家伙刚才，我们利用他们的集体脑力像你这样的家伙做周零。所以，让我们继续这样做。两个和一个。二和三。三和四。四和五。五和六。六，七。做了什么？所以我，但让我打魔鬼代言人。我的电脑谁只是发了一通通过这个数组人，知道我做的吗？扬声器1号 DAVID J.马兰：那么，为什么呢？我会怎么做，以果断地结束，我做？大概一个多通。对吗？因为我知道从先前通的是，我纠正了错误。这意味着，也许有另一个错误我需要纠正。所以我只能确定经复卷，然后检查，一到两个，两个三，三，四，四，五，五，六，六，七。 OK，我现在没工作。我可以肯定记得，我没工作像变量一样的东西，我喜欢一个int。叫它掉，如果掉的是有一次我0 在这里，它从0开始，然后我也只是愚蠢继续下去来回，再次检查，一遍，又一遍，对不对？因为你在一些被卡住一种无限循环。所以，只要有0掉期，我们可以声称这算法确实是完整的。现在，让我们把名称。我建议我们只是算法实现东西叫做泡沫形式的，在这个意义上，作为这种已知是一种更大的数字泡自己的方式到顶部，涨幅高达到的数字数组的末尾。但这种算法是如何高效？多少步了我的身体有例如，采取排序这些七人？四，五？ OK，太多的是最终要得到答案。但即便如此，具体数量是不是非常有趣。设为n概括。所以，如果我已经N多人在这里，他们，排序，在随机顺序开始的时候，在那个原来的顺序。嗯，我有多少步第一遍？这是一，二，三，四，五，六，他们七人，所以七，六 - ，所以这是Ñ 减去一个步骤的第一次。现在，我有多少步我倒带时要采取？好吧，我们实际上可以增加一倍，如果我们真的很想，但现在，我只是会说，所有的权利，另一个n减1。那么N减1是会得到恼人跟踪，让我们只是小幅围捕。所以2n个。因此，14个步骤，给予或采取。我多少次一个步下一次？嗯，这是3N。真的。现在，在最坏的情况下，为例如，我有多少次来回走了，反反复复，执行该算法，交换每个合格的人，大约有吗？它实际上是Ñ平方，对不对？因为在最坏的情况下，可以种想想这个直观的，即使它可能需要一点位时间的下沉。在最坏的情况下，会是什么七人的模样，在协议条款他们的人数？完全倒退，对不对？只是模拟，你叫什么名字呢？ MIKE：麦克。 DAVID J.马兰：迈克？ OK，迈克，你只是和我一起过这里只是一秒钟？事实上，没有。对不起迈克，让我们倒带。你叫什么名字呢？尼尔：尼尔。 DAVID J.马兰：尼尔。 OK，尼尔，你来我，如果你不介意的。所以我要提出的，只是简单起见，尼尔现在是在他最坏情况下。但记得我是如何实现我的算法。我比较，比较，比较，比较，比较哦。现在，这些家伙都出来了秩序，所以我修复。所以你们交换。但现在，考虑如何更远尼尔一定要去吗？它大致Ñ。你知道，这实际上并不ñ。这就像，N减1，但我得到恼火跟踪的小号，所以我们只叫了N。所以，如果尼尔移动一步最大限度每个时间，移动尼尔一步，我必须做出这个非常繁琐的通来回，这大概是这样，n个步骤，共n次，因为它是要带我许多步骤尼尔所有他所属的地方。更别说其他人，如果你们都乱序。所以姑且称之为的冒泡排序Ñ平方。这个算法的运行时间，该算法的性能，该算法的效率，我们只是描述一般为n的平方。这是很好的，因为我可以做同样的例子，八人，九人，一万人，答案是不会改变的。所以，如果你们不介意，让我们重置你开始的地方。让我们尝试其他两种方法如果我们不能从根本上做比这更好的。所以这个时候，我要建议一种不同的算法。这是非常聪明的，我们最后一次，你们是正确的，有权利只是一种本能的交换两两。但是，如果我真的就想办法简单地说，我的目标是移动这样的小数字，推动所有的大号码这样，为什么不我只是做，在最天真的可能的方式，看看我比什么是可以做的更好相当复杂的算法？所以，让我们来看看。四是一个非常小的数字，所以我要离开你有片刻。哦，2号，甚至更好。所以，你可以只是一步一会儿吗？这是我目前最小的编号候选人，我会记住与一样，一个变量。但我会继续检查。是否有某人的号码是小？六，没有。哦，还有尼尔再次。所以我打算推你回来排序的概念。尼尔将挺身而出。而现在，变量，我使用跟踪谁拥有最小号码被更新为包含尼尔的位置。好吧，让我们来看看。三，七，五。好吧，我知道尼尔是最小的。什么是最简单的事情我现在要做的吗？只是，我不会浪费我的时间冒泡尼尔一个点到左边。为什么不让我在那里他将尼尔属于当然，这是在哪里？所有的方式在开始时。所以，尼尔，跟我来。你叫什么名字呢？ GRACE：格雷斯。 DAVID J.马兰：格雷斯。确定。所以，雍容，不幸的是，你样的方式。那么，我们如何解决这个问题？对吗？如果这是一个数组，有只有七个地点。回想一下，与Rob，我们谈到声明年龄，我们只有一个有限数量的年龄？同样的想法在这里。我们只有有限数量的整数。格雷斯是怎么样的，在我们的这样，那么我们如何解决呢？最简单的方法是什么样的，格雷斯，对不起。你要去走了过来所以我们可以腾出空间。现在，如果你想想，也许我们只是使问题变得更糟。也许我们这样做，因为如果格雷斯是在正确的地方？但我们知道，她不是，因为否则，她会一直而不是站在尼尔在这个时候，对不对？我们已经检查了她的电话号码。好的。所以，现在，尼尔在正确的地方，我可以做一个轻微的优化。在接下来的一分钟，我要忽略尼尔都在一起，所以不浪费他的时间，或意外他换到错误的地方。所以，现在，我该如何寻找下一个最小的元素吗？二。这是一个不错的数字，如果你要挺身而出，我会永远记得你。六，没有好。四，三，七，五，没有好处。因此，让我打动你你的正确的地方。而我们只是很幸运这个时候。现在，我要忽视这些两个家伙，现在更尽一通过这一点。六，是一个非常小的数目。加油前进。哦，对不起。 Grace的号码比较好，所以踩前进。四。对不起，格雷斯。你回去吧。三是更好的。七。五。现在，你叫什么名字呢？杰森：贾森。 DAVID J.马兰：贾森。因此，Jason是现在最小的我的元素。他要去哪里去了？那么，六是。你的名字吗？ GABE：加布。 DAVID J.马兰：加布。加布的方式。什么是最简单的事情吗？交换这两个家伙，然后继续。所以，现在让我们来看看。谁是最小的？四。让我只是一种作弊。五是将是最小的。接下来，我觉得，如果你想一步未来，我有什么做这些家伙，加布？再交换。所以，现在，仍有小幅的顺序。我发现加布是最小的，所以我弹出他，将你们。并完成。因此，答案是一样的。最终的结果是一样的。这两种算法哪是更好吗？第二个，我听说了。为什么呢？扬声器3：n个步骤[听不清]。 DAVID J.马兰：这是最多的n个步骤。有趣。那么是什么关系吗？那么我怎么找到最小的元素？我不得不采取了多少步找到最小的元素？我一看所有的方式到底对不对？由于在这最坏的情况下，什么如果尼尔在这里？因此，只要找到最小的元素我需要n个步骤，或n减1。但是，“确定”。所以修复尼尔。请记住，一分钟左右前。但我怎么找了下最小的元素？这是N减1，或n减去2真的，从步骤的数量。这样就OK了。所以，我没有Ñ零下2。好的。所以，感觉更好一点。好的。下一次多少步找到3号？所以N减去4。因此，它的下降，少一个在每个迭代步骤。因此，这并不感觉更好，对不对？如果最后一次大约是N倍N 这个时候它的N减1，加N减 2，加N减去3，加上n 零下4，点，点，点。但是，如果你还记得你高中课本，一点作弊表背面有公式，如果你这一系列的数字加起来，总步数是什么要我把这里吗？这是其中的一个，喜欢，正零下 1，次数n，再除以2。因此，让我看看，如果我可以拉这件事只是一瞬间。再次，我是那种四舍五入一些编号只是为了让我们的生活变得简单，但我记得，它的东西一样，如果我做N减去1件事情，那么n减去 2，那么n减去3，大致超过2，这样的事情，如果我乘了这一点，这是实际上n的方阵。这不是感觉太美好了。 Ñ零下n次2。但这里的东西。在计算机科学中，出现问题的时候开始变得有趣的是，当n 变得非常大。当n变得非常大，这这些价值观是要主宰一切其他人呢？这是一种n个平方，对不对？是的，除以2，是相当不错的。但是，如果你正在谈论数十亿条数据，或万亿条数据，OK，所以你快两倍。但谁真正关心，如果大的数字，如果这个因素是什么得到越做越大。当然，它使更多的差异比这个家伙。所以，即使你们是正确的，第二种算法，我们叫它选择排序，是在现实世界中，潜在快一点，因为我采取越来越少每一个步骤的时间。这不是真正的从根本更快。因为如果我们真正发挥出大的n值，结束时一天，n足够大，它仍然是要感到相当缓慢。好吧，让我一个在最后一传。这是我所说的选择排序。你们可以自己复位最后一次？而在这最后的情况下，我要去提出的东西所谓插入排序。插入排序，概念，有点不同。而不是去来回我选择最小的元素，只是去处理这些家伙，我遇到他们，并插入他们到他们的正确的地方。所以，我只是要开始与Grace，我看到，她是第四个。数四属于哪里？我还没有开始任何排序，所以格雷斯获得呆在那里。现在，我稍后会要求，如果你能走一步到您的权利，这我的排序列表，这是我未分类的剩余列表。所以，现在我要继续下，你叫什么名字呢？布兰森布兰森： DAVID J.马兰：布兰森。因此，布兰森是2号。所以，我要带你出了一会儿。而现在，你属于在这个数组？所以恩典的权利。所以，我们又是一种使格雷斯在这里做了很多工作。我们在哪里把你吗？因此，我们要滑动你离开了，有插入布兰森。但现在我要求你们完成。但是请注意，我没有使用额外的空间。它仍然是2个元素在这里，在这里。总数组的大小为7，因此我不要欺骗你，没事吧？所以现在我们有加布在这里，六，你属于哪里？你很幸运了。所以，你呆在那里。只取一小步的权利只是为了让你排序。现在我们有尼尔再次，数字 1，你在哪里去了？现在是我们将开始看到该算法中，虽然在第一一目了然，感觉很聪明，看什么是即将发生。如果你能挺身而出。在哪里，我们希望把尼尔？所以，很显然在这里，所以如何我们得到尼尔？让我们做到这一步一步的。加布，你需要去哪里呢？没错，所以采取一大步，或两个半步骤，以使那边的一个步骤。格雷斯，你去哪里？好。所以又迈进了一步。最后，布兰森？另一个步骤。现在我们可以把尼尔到位。所以，现在，继续这样的逻辑。即使我们不转移尼尔过来，过来，过来，把他他走到哪里，在最坏的情况下，下一个数字，我们可能会遇到能的数量，例如，有一个数零，那么我们要全部转移这些家伙。假设有一个数字，负一个，那么我们必须转移所有的这些家伙。所以我们真的只是一种翻转周围的问题，这样，我们从转移的费用选拔过程，所以插入过程中，如你们刚刚移动大致Ñ减去的东西步数。而且，步数只打算增加，因为我选择更多的数字，如果我要继续推搡你们回来，回来，回来。所以现在伤心的事情是所有这些算法是n的平方。让我们继续前进，感谢这些家伙，这些位可视化是不同的。非常出色。 [掌声] 好的。你去那里。感谢 - 布兰森：[听不清]保持的数字。 DAVID J.马兰：没有，你可能保持数字。好的。干得漂亮。好的。因此，让我们来看看，如果我们现在不能总结更为迅速，并且视觉上更正是刚刚发生了什么在这里，如下所示。我要继续前进拉起Firefox浏览器。我们会链接这个示范本课程的网站。 Java是一个有点恼人获得工作在某些浏览器，这些天。所以，如果你在家里玩这个，意识到你可能需要使用Firefox 得到它的工作。什么，我要做的事情与此示范以下。在底部，我有一大堆菜单选项，包括一个起点和一个 “停止”按钮。另外，顺便说一句，似乎是一个在这些程序中的错误，让你不能真正看到启动或停止按钮，除非你按住Command或Alt 加和变焦，好奇显示更多的按钮。因此，只是供参考，如果你玩这个在家。现在，我要单击“开始”，在短短此刻，在指定的延迟后，只是一样，在这里，200毫秒所以我们可以看到发生了什么。因此，我要求这是一个可视化第一算法这些家伙确实，冒泡排序，即我们交换成对的人。此可视化的关键洞察力是矩形条的高度表示的数量的大小。所以酒吧更高，数字越大。较短的酒吧，数字越小。如果你注意到了，我们正在经历在此算法中，在第一次迭代交换大和小的数字，所以少数至上大数量的权利。而只要我们得到数组的末尾多数量比七，我们要回去的开始。和预测。在最左边，那个小家伙是怎么回事交换到一边，这过程重复。现在，这个可视化很快就会无聊，所以让我继续前进，停止它，改变延迟东西只是为了得到更快现在，感觉该算法。因此，即使我已经加快了，这是就像我的处理器升级，买一台新电脑。我还没有从根本上改变了我算法，但你确实可以看到更多的显然比人类大数字冒泡到顶部，小的数字冒泡下到谷底。现在这个东西在这里排序。顺便说一句，在广场，有只是有一些簿记帮你算多少次比较，或有多少掉期实际上已经完成。好吧，让我们尝试之一我们看到别人。让我点击这里冒泡排序，让我选择，这整个网页是一点点马车。让我们接受的风险并再次运行它。我们去那里。因此，让我们做选择排序。我不知道为什么菜单出现在那里。让我们放大到解决这个问题错误，改到50。啊，让我们真正做到是更快的。 5毫秒左右开始。因此，这是选择排序。如此反复，想想我们与人类在这里做了。我们经历的数组，并选择最小的元素，一遍，又一遍。现在，我要求还是蛮不错的。它仍然为n的平方，给予或采取，但它是在现实世界中，位更快，因为我确实服用略少的每个步骤。但我们只是在谈论什么？可能40或酒吧在这里？我们不是在谈论4000万美元。所以它不是完全清楚的，我认为确实是一个显着的收益。现在让我回去，并改变我们的第三个算法，它被选择插入排序。而现在它是真的马车，因为菜单实在不应该是出现了下滑。所以，现在，我们将在这里滚动备份并启动此算法。呐喊，启动和停止。所以这一种有一个漂亮的图案它，让我们再次插入人体，或在这种情况下，酒吧其适当的位置。它之前已经完成我转头。但是这一个，并且，在理论上，仍然为n的平方。因此，让我们来看看，如果我们不能概括这些如下。我要继续前进，只是为了给我们一个共同的说话方式这些事情，让我介绍一下这里只是一个符号位。你看到的东西叫大 O，因为它实际上就是一个大 O.这是一种方式，一台计算机科学家或数学家甚至使用描述的运行时间的一些算法。多少步骤，它实际上采取？现在，我要自己难堪我的笔迹，在这里只是一个瞬间。但是，让我继续前进，说这将是大O字在这里。让我介绍另一个符号，资本欧米茄。欧米茄是相反的，从本质上讲，大澳鉴于大O 的手段，在最坏的情况下，多少时间可能一些算法，以n，ω是要多少时间可能在最好的情况下采取。我们会看到我们所说的最好的情况下，在短短的时刻。所以，让我们先从简单的东西。让我开始线性搜索。所以，不排序。我们称这个线性搜索。而现在，做一点表了这一点。而现在，线性搜索的情况下，在最坏的情况下，多少步它要带我找到一个任意选择的数？还有的N总门或n总数。最坏的情况。我将不得不多少步找到在一个数组中的数字50 n个门？为什么？因为它可能是所有一路过来到年底。因此，就像珍妮弗遇到， 50号是一路过来，所以在最坏的情况下的线性搜索大O的n，我们会说。怎么样最好的情况下，如果你很幸运吗？只是要一步一步，或恒定的步数。因此，我们将介绍为1。因此，这是相当不错的。现在，如果我们做的东西喜欢二进制搜索？因此，二进制搜索，在最坏的的情况下，花了多少时间？ [插入声音] DAVID J.马兰：其实我听到一对夫妇的地方。因此，它实际上登录N，给予或采取因为我们把一半的列表中一遍，一遍，又一遍，我们能够发现，最终，该值，如果它的存在，但有一个catch。什么是假设，我们必须想当然二进制搜索？进行排序。它不排序，可以分割的东西半一遍又一遍，你向左走，你可以去，你可以去左右，但你不会找到的元素，如果列表中，因为没有排序你可能会错过它。因为你的启发，去左或向右将是有缺陷的，如果它是确实没有排序。因此，有一个隐藏的成本有点使用这样的事情。现在，让我们进入我们的排序算法搜索 - 哦，居然让我们去在这个空白。在最好的情况下，二进制搜索？这也是1，如果它恰好是在中间的阵列，或中间的电话簿。现在，让我们做冒泡排序。如此反复，现在我们正在进入排序，而不是搜索。在最坏的情况下，没有多少步理赔冒泡排序要采取？摆正Ń。所以我要画，。哦，我的笔迹看起来更糟当它预计的那么大。好的。所以这Ñ平方。而冒泡排序在最好的情况下，多少步，要采取？ 1，我听说了。扬声器1：N。 DAVID J.马兰：N，我听说了。扬声器1：2。 DAVID J.马兰：2，我听说了。我听到3？好的。所以我听说过1，N 2，但让我们挑除了至少在最前面的那建议，1。这不是一个坏的本能，因为它一种遵循一种模式。但是，如果只需要1步，如何在世界我声称，该清单排序，因为如果我只允许 1步，多少个元素其实，我可以检查，以确保？那么，就1，这意味着有Ñ 减去1个元素，可能是满分秩序，我只是去后的信仰看着1元事情进行排序。所以这里不正确。因此，微创，有多少我要看看吗？ [插入声音] DAVID J. MALAN：N减1，还是真的， N，因为我需要看每元件，以确保它不是秩序。但是，我们将再次排序波我们手较小的数字，假设，当n变大时，他们反正无趣。因此，冒泡排序。而现在，让我们做这些最后两个。选择排序，然后我们会做插入排序。然后，我们会打击你的头脑的东西多比所有这些。好的。这是最坏的情况下运行选择时间排序？扬声器4：N的平方。 DAVID J.马兰：n的方阵，我听到。但是，为什么Ñ平方，直观？扬声器4：因为我们只是做了它。 DAVID J.马兰：因为我们只是做了它。确定。好答案。但直觉上，这是为什么选择排序Ñ平方？我们有什么做一遍又一遍吗？我们必须保持通过扫描，你最小，你是最小的，你是最小的。并授予，我们可以取n 步骤，则n减1，那么n减去2。但是，如果你有种把它们统统加起来，或采取的信心，我已经加入他们在前进，我们大致得到Ñ 平方减去一些小的数字。所以，我现在就打电话给这n的平方。但最好的选择排序的情况下，多少步要带我吗？扬声器5：[听不清] DAVID J.马兰：这是不幸的仍然为n的平方，右？因为如果我选择最小元素，我们在这里有七人，我只知道，一旦我得到非常最后，我发现最小数，无论他或她可能已经。但我怎么找了下最小的号码是多少？我必须做的另一张通行证。因此，在最好的情况下，什么是输入选择排序？这是一个已排序列表，头号，数二，数三，数四。但我一台电脑。我只能看一眼在一个时间的事情。我不能排序采取的一个步骤像人类和说，哦，这看起来是正确的。我只能判决正确性选择排序方式选择最小数。但是，即使我发现的头号第一，如果我不知道别的约其他号码，我不，我知道，我已经交给一个数组或一组门后面是数字，只有这样，我知道，一个是最小的吗？如果我得到的所有的方式在这里实现，该死的，一个是最小的。但我怎么确定二是下一个最小的？通过做同样的低效率一遍又一遍。最后，用插入排序，如何，在最坏的情况下，我们说，它执行？它也为n的平方。最好的情况下怎么样？我们会离开，作为一个扣人心弦的。我们要填补那个空白的下一次，但首先，让我建议，我们从根本上做得比所有这些，好吗？因此，认为自己是什么插入排序将是。嗯，这是不是很剧烈，因为我是唯一一个看到了变化。哇。确定。所以，在这里，我们有一个有点不同的示范。如果我在这里放大，你会看到，在左边我们有冒泡排序，中间我们有选择排序，最右边，我们有些东西还没有看过所谓合并排序。但我们一直在考虑什么在这里做今天迄今。当珍妮弗第一次来到了舞台上，我们经历过的数字数组一遍，又一遍，线性搜索，我们得到了线性运行时间，大O N，可以这么说。当我们现在考虑的第一周类，当我们分而治之，我们电话簿撕裂，和珍妮弗，我们集体利用关键的洞察力，这是重复自己一遍又一遍莫名其妙地扔掉，扔掉，扔掉，一半的问题，或通常，分割一半中的一个问题，然后把一块较小概念上等同的问题另一方面，我们莫名其妙地做从根本上更好。但随着冒泡排序，选择排序，插入排序，我们可能詹妮弗没有这样的见解。我们非常简单，只是走回提出了一大堆的时候，我们调整了一点点东西，交换在这个命令，也许插入或选择。但是在一天结束的时候，我做了很多尴尬的步行来回。我们并没有真正利用的东西智能不喜欢像珍妮弗除以和征服。因此，归并排序，与此相反，我们直到下周不会看到，它是怎么回事除以利用的关键概念的输入，然后减半，然后减半，再减半。和在该循环的每次迭代，排序的左半边和右减半的话，左半边的左半部分，和右半边的左方，再的左半部的右半部分，并的右半边的右半部分。并重复一遍又一遍。所以，你会看到在视觉上，但是这是什么在等待着我们下周。而在一般情况下，当我们觉得一点点任何这样的问题上有点困难。我们有N平方的左侧，正在中间，和n平方 n在登录的权利。因此，有你真正的悬念。我们会看到你在星期一。 [掌声]