演讲嘉宾：好的，这是CS50。 这是3周结束时，如果 你有没有冤大头不已， 知道，会有午餐 这个星期五和往常一样，在那里 您可以享受良好的交谈 食品在火与冰 一些CS50年代 工作人员和同学。 前往这个网址在这里。 现在，你可能还记得，或者你 可能很快被认识， 这些东西在这里，这 在最后给出了 的学期很多类。 所谓考试蓝色书籍，其中 你写你的答案考试。 现在我已经在这里等26 蓝色的书，对他们每个人 通过Z.写着的名字，a和 不愧是名是简单，一 到Z和一 手头今天的目标 将是继续什么 我们开始在星期一，这是不 这么多看代码，但真正 寻找思路和解决问题的能力。 其中一个目标， 本课程的承诺 是教你去思考更多 细心，更有条理， 并且更有效地解决问题。 事实上，我们能做到这一点真的 甚至没有触及一行代码。 所以，我有一对夫妇的大象 在这里今天，橙，蓝， 如果我们能找到一名志愿者， 也许从更远的背面比平常。 怎么样在那里，下来吧。 它的目的将是对 帮助再加上这里管理这门考试。 你叫什么名字？ 听众：玛丽·贝丝。 演讲嘉宾：玛丽·贝丝，上来吧。 让我的麦克风为您服务。 很高兴认识你。 听众：很高兴见到你。 演讲嘉宾：好，让我有 这里蓝皮书A到Z， 我要去假装 我有一个学生， 而他们来的有点随意 在三个小时的考试块的末尾， 所以他们结束了在某些 半随机的顺序是这样的。 现在，在短短的一瞬间你的工作是怎么回事 以be--这其实是他们如何获得 在结束时打开在 类，最有可能的。 你现在的工作将是，相当 简单地说，这些蓝色的书为我们梳理 从A到Z 听众：哦，这是 要带下去。 演讲嘉宾：我们会看 当你做到这一点，没有压力。 听众：没有，没有压力或任何东西。 演讲嘉宾：而且为了好玩， 我们提出了一个定时器。 听众：太好玩了，太好玩了。 演讲嘉宾：我可以抱麦克风为您服务。 好吧，我们刚刚增加了一倍我们的速度。 所以在此期间，让我带来什么 要成为玛丽贝丝问题 是什么，是她做的，怎么会是 她打算着手解决呢？ 而事实上，你可能没有 没有想过的东西 如此简单，当你挑选的 高达26本书就是这样， 它确实有一个自然的 订购他们。 过程是怎样的 你实际上使用？ 它是相当随机的只是 挑选你看到的第一个 并把它在它的地方？ 你首先将双手左右 寻找，然后找乙？ 你看看在 他们两人并排 而只是说，等一下，这 是不对的，然后交换顺序？ 我们已经看到在周一 这有许多方法 在其中我们可以做到这一点， 的确，我们附近结束了， 我会留意可能 什么玛丽·贝丝在做什么。 我们有几堆，似乎一个 更大的一个，三个小的。 听众：我命令他们 当我找到两封信 我知道是一起在一个序列中， 我把它们放在一起，让我不 不用担心保存 轨道书一整排的。 这只是，呵呵，首先， 我这里有这个堆栈。 演讲嘉宾：所以，几乎像 拼图的碎片 有合适的形状，以 相互匹配。 听众：好看多了，是啊。 演讲嘉宾：好的，优秀的。 现在每个这些 桩的大概排序？ 听众：是的。 演讲嘉宾：好的，从A到Z的所有 没错，恭喜你，你做到了。 你有你的选择。 蓝？ 好吧，谢谢你了。 因此，玛丽·都建议 什么她的做法是， 但什么是另一种方法，你如何 可能去整理这些东西？ 你会怎么做？ 击败的纪录会一直 一分钟，50秒左右， 再加上那些我忘了算。 你会怎么做？ 是吗？ 听众：以堆栈。 从起始处开始。 请检查您的论文。 如果最上面的一个是高 不是，也许，他们是， 底部的一个是 高，然后切换他们。 演讲嘉宾：好，那么开始 在顶部和底部， 然后你的工作方式 向内那样，交换呢？ 好了，有点类似 在精神冒泡排序， 但选择极端 不相邻的对。 但是它的短是，有 当然了一堆不同的方式 我们可以做到这一点， 坦率地说，我觉得你真好 通过几个途径，对不对？ 你做那种四堆排序，并 然后有效地融合在一起。 那就是，敢说，另一 技术完全。 你没有把它当作一个大的一堆， 你划分的问题分为四个四边形， 如果你愿意，然后以某种方式 合并它们的末端。 因此，让我们考虑，最终， 怎么回事我们可以做到这一点。 我们形式化的概念 的冒泡排序最后一次， 和冒泡排序召回是一个 算法，我们可视化 八你的同学在这里， 起初看似随机排列。 然后我们决定成对的，如果 两个元素是无序， 简单地交换他们。 于是四加二 显然失灵， 所以这两个同班同学 交换位置。 然后，我们重复了四和六， 然后6和8，在每次迭代中， 移动到右侧。 所以，给八人，有多少配对 比较我做了，而走路 左到右在一个这样的迭代？ 有多少的比较？ 七，对不对？ 因为如果有8 人，但你有一双 他们和你继续前进 1跳的权利， 你不会有八 比较，因为你不能比较 对本身的元素，否则会 仅仅是毫无意义的，让你有七。 或者更一般地，如果 我们有N多人，我们 做了N减1的比较 用冒泡排序。 所以，现在让我们考虑如何好或 坏的泡沫实际上是排序，并尝试 给自己用的词汇 这在像这样的批判算法， 很快我们自己。 所以，通过第一通 冒泡排序，在第一时间 我是从左边走到对面的权利 现阶段，我花了Ñ减1的比较。 而这将是我的 计量单位的，对不对？ 我是那种说话，散步， 有些快，有些慢， 所以我计算的秒数 没有特别明显的， 但计数的数目 我确实在周一的操作， 比较两个人，那种感觉 就像衡量一个不错的单位。 因此n减1的步骤是第一次， 但之后发生了什么？ 什么是一传一上攻 通过其他未分类列表？ 你能告诉我该元素 谁是一路过来吗？ 是吗？ 这是最大的因素，对不对？ 第八，即使她 从这里开始，我每次 对她比较 一个邻居，她不停地 冒泡向右 列表中的右手侧。 事实上，这正是 该算法得名。 现在，通过这一逻辑，有多少的比较 需要我做的第二次 我作出这样的传球从左至右？ Ñ​​减2，对吧？ 这纯粹是在浪费我的时间，如果我 保持比较8人反对某人 别的，因为我们已经知道 她是在正确的地方。 所以这是一个比特的 优化，所以下通 将是加N减去两个步骤 其中n是人的数目。 现在你可以种推断，即使 如果你不是一名计算机科学家， 如何结束。 在此算法结束时，据推测 你有只是一个比较离去。 你有一种固定的 在案例二开始列表 一都失灵 并应一和二， 所以这个谷底的 加1最后的比较。 现在，点，点，点样波是 手在一些多汁详情 但我们只是继​​续和简化。 如果您还记得高 学校，坦率地说，很多你 有数学书的有 有点小抄 前盖或 后盖表明您 什么系列求和样 这最终加起来。 在一般情况下，如果你有一个 变量如N，而事实上这其中， 如果你看着你 老同学的数学书， 你会看到，这实际上 加起来这笔款项在这里， n次Ñ减1都除以2。 所以现在我只想规定 这是真的，那么对信仰的飞跃， 这就是这个总结 最多，我们可以 证明，在更一般的情况。 但现在让我们展开了这一点。 因此，让我们乘了这一点，所以这是 Ñ​​平方，减去N，所有除以2。 这真的Ñ平方， 除以2，再减去Ñ超过2， 所以这是所有漂亮和有趣。 但是，如果我们发生 现在Plug-in的价值呢？ 假设我没有8 人，但说一百万。 和一百万只是因为 这是一个非常大的数字， 让我们插上，在看看会发生什么。 所以，如果我插上一百万到该公式 我要拿到一百万平方， 除以2，减去 万元，除以2。 现在，那是要一样的吗？ 所以500十亿，减去50万元。 如果我实际上做 在数学，这表示 该排序一百万 人与冒泡排序 可能要花费499999500000 在结束步骤或比较， 我们只是推断。 这感觉很慢，但坦率地说 测量一个特定的输入 像这样，是不是所有的说服力。 但事实上，这确实表明，当n 变大，该算法 那种感觉差， 更糟的是，不然你真的 开始感受到了疼痛 幂，使得n的平方， 这些加起来非常快。 而这个细节不 失去了对的人，其实 几年前，某参议员谁是 竞选活动，坐下来接受采访 与谷歌的埃里克 施密特，当时的CEO， 并与一个问题的挑战 就像我们今天探讨。 让我们一起来看看。 [视频回放] -Senator，你在这里 在谷歌，我喜欢 认为总统的 作为一个工作面试。 现在，它是很难得到 一份工作，担任总裁， 你正在经历的严酷了。 这也很难找到一份工作，在谷歌。 我们有问题，我们 要求我们的考生的问题， 而这一次是从拉里·施维默。 What--你们觉得我 开玩笑，这是在这里。 什么是最有效的方式来 排序一百万的32位整数？ -Well-- -I'm对不起，maybe-- 不，不，不。 我认为，冒泡排序 将错误的路要走。 -COMe上，谁告诉他的？ 我没有看到电脑 科学的背景。 -We've了在那里我们的间谍。 - 确定，让我们问一个不同的 面试问题。 [完视频回放] 演讲嘉宾：所以说起 具体的数字，虽然， 不会是那么有用。 这不是一个生活的一课泡沫 排序，给定一个亿的投入， 可能需要多达500十亿步骤。 你真的不能一概而论 从太有效 做出好的设计决定 编写程序时。 因此，让我们虽然把重点放在如何 我们可以简化这个结果。 所以，我在这里黄色高亮 n的结果的平方除以2， 所以一百万平方 除以2，然后 我已经强调了什么 最终的答案是 一旦我们减去关闭N除以2。 并声称我会做，现在是， 谁的心里很不舒服，如果你减去了关心 一老一少Ñ超过2时，第一 这个公式的一部分，是这么多的大吗？ 它支配着其他 长期，N的平方除以2 如此多的大，显然，作为 n变大像一百万， 这是真的，在一个很大的区别 一天500十亿之间到底 和499999500000？ 并不是的。 还等什么，我们要 做计算机科学家是 忽略这些低阶条款及 采取这样的事情，真的 只需将它简化为 术语，是怎么回事无所谓。 在我们的大数据集得到的，更大的 我们的数据库中得到的，就越网页 我们必须搜索，越 朋友你在Facebook。 当n变大，我们真的 要关心大 长期在任何此类分析 我们的算法性能。 而我要说，你知道吗， 冒泡排序是大O的顺序， n的顺序上的平方。 这不恰好n 方如我们所看到的， 但谁真正关心 那些小的方面， 坦率地说，谁真正 关心，如果我们除以2？ 这只是一个常数因子。 并为500十亿与250 十亿真有那么大的一笔交易？ 我可以等一年， 让我的笔记本电脑逐字 得到两倍于硬件的速度， 等诸如此类的差异 刚刚消失，自然随着时间的推移。 我们关心的是什么 的表达，该部 那将改变表达的 作为我们的输入变得越来越大。 事实上，在现实世界中， 这就是正在发生的事情越来越多 是投入到我们的问题， 算法越来越大。 因此，大O将是符号， 渐近符号，我们只 利用计算机科学家描述 的性能，或在运行时间， 的算法。 这样我们就可以比较算法 写上不同的计算机 由不同的人，通过使用 一些基本相似度量 喜欢比较的次数你 制作，或者互换的数量 你正在做的。 我们不是要 计数的时间量 传递上的时钟 墙壁上的典型。 我们不是要担心 大约是多少内存 您使用的是今天 至少，尽管这 另一种资源，我们可以衡量的。 我们要尽量立足分析 上只是基本操作，那些， 坦率地说，你可以看到最直观。 因此，与类似的n大O 平方，我要求是n的平方Ò 是一个上限，所谓 运行冒泡排序的时间。 换句话说，如果 希望声称有 上多少这个上限 几步之遥的算法可能需要， 这将是n的大O 平方在这种情况下，一个上限。 如果我不是改变 故事是不是冒泡排序， 但这个上限。 你能想到的算法 我们已经看过了已经 其上限，最大 测量的时间或操作 将所述有界 用n，一个线性函数， 没有二次一个是弯曲？ 什么是算法 始终把没有更多的 不是像n步，或 2n个步骤，或3N步骤？ 是吗？ 听众：寻找 列表中的最大号码是多少？ 音箱：完美，找到 在列表中的最大数。 如果我给出的名单 人，例如， 各是谁在持有一个号码， 什么是最大数 步骤应该带我， 一个相当聪明的人， 找到最大的人在该列表中？ N，对不对？ 由于在最坏的情况下，当 也许最大的价值是什么？ 右，一路在末端。 所以在最坏的情况下 上界，我可能 要一路走下去 在这里是这样， 哦，这里的数字8， 或任何该值。 现在，这纯粹是愚蠢的 如果我坚持下来了，对不对？ 寻找更多的元素 如果最后他们是在那里？ 因此可以肯定，n是一个上限。 我不需要拿 比更多的步骤。 那么，如果不是我提出的 还有在这个世界上的算法， 有一个运行时间的 通过日志的n大O范围内，日志N？ 那里有我们以前见过吗？ 是吗？ 听众：在电话簿的问题？ 演讲嘉宾：像电话簿的问题。 什么是如何的量度 太多的时间和多少眼泪吧 带我找到喜欢的人 迈克·史密斯在电话簿？ 我们要求它是数n和 即使不熟悉，或者是 一点点朦胧什么 对数或指数为， 只记得为log N 一般是指在过程中 在这种情况下，分割 东西两半又一次，又一次， 又一次，又一次，使得其 变的越来越小，你这样做。 因此，日志正指，当然， 到电话簿例如 在理论的二进制搜索，当我们 有虚拟门电路板上， 或者当肖恩 寻找的东西。 如果他用二进制搜索，日志N 将上限多少 时间花费。 但是，那些跑在算法 日志N承担哪些关键的细节？ 该列表进行排序，对不对？ 你的算法是错误的，如果 您输入不排序， 可是你用 像二进制搜索 因为你可能会跳 右以上的元素 没有意识到这是真的在那里。 现在什么可能意味着一，大O？ 这并不意味着你的算法 采用一个和唯一的一个步骤， 它只是意味着它需要一个 步骤恒定数目。 也许是1，也许是 10，也许是1,000 但它是独立的 问题的大小。 无论多么大的n是， 一个常数时间算法 始终以相同的步骤号码。 那么，什么可能是一个算法 我们已经讨论过，或只是 直观地说来你 总是在所谓的恒定时间运行？ 是吗？ 听众：两个数相加。 音箱：两个数相加， 2加2等于4，完成。 因此，可能的工作，还有什么？ 如何更真实的世界，是吗？ 听众：寻找 列表中的第一件事情。 演讲嘉宾：寻找第一 元素在列表中，确保万无一失。 实际上我们一直在谈论 关于数组已经， 你怎么在得到 在数组的第一元素， 无论多久 数组是C代码？ 您只需要使用像支架 零符号，咣当，你在那里。 事实上阵列，顺便说一句， 支持的东西一般称为 随机存取，随机存取 记忆，因为你可以从字面上 跳转到任何一个地方。 我们可以做到这一点，甚至更简单 我们可以倒回至零一周 当我们做划伤。 它没有多少时间了 要说块划痕执行？ 就在固定的时间，对不对？ 说些什么，说 东西，也没关系 大划痕世界是怎样的，它总是 要采取相同的时间量 简单地说一下。 所以这是一定的时间， 但什么是另一面？ 如果这是上 界，如果我们想要什么 描述下界 我们的算法的运行时间？ 几乎是最好的情况 潜在的，如果你愿意， 尽管这些条款可以适用于最 的情况下，最坏的情况下，一般情况下，更多的 一般，但我们只关注 上下限比较一般。 什么是算法，具有 下界n个步骤， 或2N步骤，或3N步骤？ n个步骤的一些因素， 这就是它的下限。 是吗？ 听众：冒泡排序？ 演讲嘉宾：冒泡排序需要 你最低限度n步，为什么呢？ 这是为什么？ 为什么会这样开始来找你 直观地说，即使它不只是 没有？ 是吗？ 听众：[听不清]。 演讲嘉宾：没错。 在可能的最佳方案 冒泡排序，和大量的算法， 如果我交给你八人 谁是已经排序， 那将是愚蠢的 你的算法， 去来回 不止一次，对不对？ 因为只要你 通过列表步行一次， 你应该明白，哦，我什么也没有 掉期，这个列表进行排序，退出。 但是，要定你n步。 反之，什么又 考虑这个问题的方法是什么？ 冒泡排序是欧米茄， 这么说的n，， 因为如果你看一下 少于n个元素，是什么 是根本问题吗？ 你不知道，如果它的排序，正确的。 我们人类的威力一目了然八 人是这样，哦，它的排序， 未带我n步，但它没有。 你的眼睛，即使你有种 有愿景的一大领域， 你看八素， 你看着八人， 这八个步骤有效。 而只有当我在整个行走 名单我知道，是的，排序。 如果我中途停止思考，所有的 没错，这是相当排序到目前为止， 什么是它没有排序的几率有多大？ 该机制的算法不会是正确的。 可能会更快，但不正确的。 所以，现在我们有办法 描述一个下界， 和什么有关固定时间？ 什么是算法，该算法具有较低的 绑定在它的一个运行时间？ 1步，2步，10步，但 恒定的，独立的n， 输入的大小？ 是的，在后面。 听众：printf的？ 演讲嘉宾：那是什么？ 听众：printf的？ 演讲嘉宾：printf的。 好了，肯定的。 所以它需要一个固定的步数。 我现在应该是now-- 我们正在谈论的C代码 不挠，事 如说，与printf的， 我们应该开始变得谨慎。 因为printf的确实需要 输入时，它是一个字符串， 和字符串做技术上有长度。 因此，如果我们现在要挑 对你，如果你不介意的话， 在技​​术上，我们可以认为，printf的 确实需要一个可变长度的输入， 并肯定它可能需要更多的 这漫长的时间来打印字符串， 比这个长。 因此，如果我们考虑一下刚才的 排序和搜索的例子吗？ 怎么样迈克·史密斯在手机 书，或二进制搜索更普遍？ 在最好的情况下，可能会发生什么？ 我打开电话本和，BAM， 还有麦克·史密斯的电话号码。 我可以打电话给他的时候了。 进了一步，也许两个步骤， 但是步骤的恒定数 如果我很幸运。 坦率地说，我们看到了 周一你的同学 在连续得到相当幸运的两倍。 而这的确是恒 时间在下限 在算法中的问题查找 数50落后结束 门。 现在，顺便说一句，如果你发现 这两个大澳，上界， 和ω，下界， 是在同一个，即 是在相同的配方 括号中，你也可以 说，只是华丽， 这东西是时间值损耗 n或西塔的其他价值。 这只是意味着大当 O和ω-是相同的。 现在怎么样选择排序？ 让我们用这个新的词汇。 在选择排序，什么是我们 老毛病又犯，又一次，又一次？ 我来回通过 在列表中，寻找谁呢？ 最小数量。 所以，要走多少步，如何 很多比较没有我 必须作出，以找出谁 在列表中的最小元素是？ Ñ​​减1，对不对？ 因为如果我刚入手一个我 鉴于我开始比较他或她， 那么他或她，他 还是她，他或她，我 只能对元素 一起Ñ减去1次。 所以，选择排序同样需要 Ñ​​减1步的第一次。 多少步它带我去 找到第二个最小的元素？ Ñ​​减2，因为我是哑巴 如果我一直在看同一人 再次，如果我已经选中了他 或者她，把他们在他们的地方。 和第三步骤中，正 减去3，则n减去4。 我们已经看到这种模式 之前，确实 选择排序相似 有一个上限 n个平方，如果我们这样做了的总和。 什么是它的下限，选择排序？ 最低限度，有多少时间必须选择 排序需要，因为我们将它定义在星期一？ 提出了两个选项。 也许这是N，和以前一样。 也许这是Ñ平方，因为它 现在作为上限​​。 听众：N的平方。 扬声器：N的平方。 为什么呢？ 听众：因为你 定义[听不清]。 演讲嘉宾：没错。 至少我定义选择排序 这是非常幼稚的，坚持下去， 找到的最小元素。 又来了，找到的最小元素。 又来了，找到的最小元素。 有没有排序 在那里，最优化 也许让我以后放弃 只是n或使步骤。 所以，事实上，选择 排序，正欧米茄平方。 那么插入排序，在这里我把 我给谁，然后我一屁股坐在了他 或她在正确的地方？ 我接着给第二个人， 一屁股坐在他或她在正确的地方。 然后旁边的人，屁股 在正确的地方他或她。 注意，这是非常 线性的，可以这么说。 我是一条直线，我 不会来回， 我从来没有回头真的，但 发生了什么，当我插入了他 或她进入初 因为我们没有在周一的名单？ 发生了什么？ 是吗？ 听众：[听不清]。 演讲嘉宾：是的，这 被抓了吧？ 你可能还记得， 你的同学，如果他们 正在作出任何动作 他们的脚，这是一个操作。 所以，如果有三个人在这里和 新人所属的方式在那边， 在很长的阶段，像这样的，肯定的是，他 或者她只是去到了最后。 但是，如果我们思考一个 计算机和存储器阵列， 这些人会 有洗牌了 让路给那个人。 所以是n减1 shufflings， Ñ​​减2 shufflings，正 零下3 shufflings是正中下怀 发生在我后面，而不是在我面前 像以前一样，在某种意义上。 现在，作为一个一旁，并作为 你可能已经看到了网上 如果你开始关注着有关 各种各样的，有这么多不同的人 在那里，他们中的一些 比别人​​做得更好。 事实上，bogosort是 这是一种乐趣来查找。 Bogosort采用一组 数字或说一副扑克牌， 随机打乱他们， 检查，如果他们来分类的。 如果不是，它再次。 如果不是，它再次。 如果不是，它再次。 令人难以置信的愚蠢。 事实上，如果你读 像维基百科的文章， 它的绰号是愚蠢的排序。 它最终会工作， 希望，给予足够的时间， 但该时间量 可能需要相当长的一段时间。 所以，如果我可以，让我们速度的东西 从早期的玛丽·贝丝的例子， 通过具有几个元素， 但有两个以上处理器。 两个人，如果你 不介意加入我。 怎么样1在这里，和 让我们go--没有人在那里？ 没有人在那里？ 行。 您与黑 衬衫，是的，下来吧。 好吧，你叫什么名字？ 听众：彼得。 演讲嘉宾：那是什么？ 听众：彼得。 演讲者：Peter，大卫，很高兴认识你。 好吧，我们有彼得在这里，如果你 想来在桌上在这里。 而你叫什么名字？ 听众：艾琳娜。 演讲嘉宾：艾琳娜。 好了，很高兴见到你。 埃琳娜满足彼得。 彼得，埃琳娜。 而我们需要安德鲁 在这里为好，请。 和你的挑战是怎么回事 要以一副扑克牌排序。 如果不熟悉，甲板 卡最终应 排序有点像 这其中，我们会做的俱乐部，然后 黑桃，则心和 钻石，从王牌为一体， 一路到王。 该卡我打算给你 将要在数量52。 我们将同样 一次，在短短的一瞬间。 我们要扔掉安德鲁 在屏幕上的位置， 这样看，你这样做。 和使所有的这 是更明显的， 这些都是我上亚马逊的卡。 因此，他们已经随机 排序，我们要一次。 而我们要 保持它真正的这个时候， 所以我们要尽量压你 否则这将让乏味的 快。 如果你能进入52排序 通过一些手段在一起的元素，现在。 再次，当我们观看这些 你们做什么，到底 会产生一个明显的 结果，想想真 他们是如何各尽其， 您可能如何描述它。 因为再次，这些都是 所有过程，算法 我们想当然地作为一个人。 但是，你可能早就有了 直觉，很久以前，你甚至 想过走 计算机科学类，你 可能曾与直觉 要解决这样的问题。 但是，一旦你认识到 模式，并开始 形式化与步骤 您正在解决这些问题， 你会发现，你能解决多少 更有趣和更复杂 问题很快。 因此，有人从观众，什么是 该算法中的至少一种元素 他们使用的是在这里吗？ 听众：[听不清] 演讲嘉宾：那是什么？ 听众：通过诉讼。 演讲嘉宾：通过诉讼。 因此，首先他们是聚类 所有的钻石一起 看来，所有的 心在一起看来， 等等，不尊重 对于卡上的号码。 现在，他们的出现，例如， 通过数量来对它们进行排序。 挺好。 好吧，那么什么会 是最后一步，然后在这里？ 一旦我们有四个排序的西服，有什么 做我们需要做的四桩 为了实现一 整理平台，很简单？ 因此，我们需要再次合并。 所以这是一个有趣的想法， 再次，敢说，是非常直观的，甚至 如果你可能从来没有掌掴 那样就可以了标签。 除以这个根本概念 问题不是在一半此时， 但至少到四件。 解决相当多 从根本上相同的问题 在彼此隔离， 然后合并的结果。 而且，优，做。 好了，又大又圆 掌声中，如果我们能。 [掌声] 演讲嘉宾：我不知道你会 做到这些，但在这里你去。 太谢谢你了。 因此，让我们来看看两分钟 八秒， 如果你想挑战你的朋友。 什么然后将要 从这样的带走 我们可以利用更普遍？ 好了，回想起 这个数字阵列， 现在回想起一些 伪代码，我们已经写在过去， 这是伪代码 解决电话簿问题。 由此伪í 列举一个更有条理的方式 描述我是如何做到一个非常直观的 将所述电话的人的算法 本书的一半，重复，重复，重复， 直到我发现有人像迈克·史密斯， 如果他确实是在电话簿。 但是我种用什么，我会打电话 很迭代的方法在这里， 特别通告第8行和第11行。 这些都是一个迭代的证据 方法，一个循环的方法， 因为这正是 在他们的行为引起。 这些线路都表示去 三线，你可以种 想在你的 心灵之眼作为一个循环。 它告诉你去备份步骤 3，重复，一遍，又一遍， 又一遍。 但是，如果我们利用的一个关键思想 在这里，我们没有最后一次， 并简化线路8 第11行和他们的邻居 像刚才这样，为黄色。 它不能从根本上缩短 伪代码非常多， 但它从根本上改变 我的算法的性质。 就是我现在说 在步骤7中，在步骤10中， 是寻找迈克 以完全相同的方式， 但只在左 一半或右半部。 因此，换句话说，如果 我是从第一步开始， 拿起电话本，开到中间 电话本，看名字， 如果史密斯是其中 名字的，叫迈克，否则 如果史密斯早在本书中，第七步 在本书的左半寻找迈克。 但是那种感觉像 它让我挂了吧？ 在黄色的，是一种 指令，但我怎么 搜索麦克左 一半的电话簿吗？ 哪里有 算法与我 可以搜索一个像迈克·史密斯？ 那么，它的盯着我们的脸。 我可以从字面上使用完全相同的 计划有效地往上走顶端 一而再，再运行 同一行的代码。 因此，即使本应该感到 像一个有点周期性的定义 在那里你回答别人的 仅通过排序问问题 再次同样的问题， 就像为什么，为什么，为什么？ 现实的情况是，因为我们已经硬编码 一组特殊的线，第4步， 其是，如果和步骤12，该 实际上是另外一个分支， 因为我们有这些治标不治本， 该算法将终止，如果我们 找到迈克，或者如果我们不这样做。 但现在STEP 7和10，我们有 我们就这么叫递归算法。 和递归确实是一个强大的理念 这是一个有点头脑的第一个弯， 我们现在可以应用如下。 归并排序将是最后的那种 我们看一下，至少在形式上类。 而且它是完全不同的 从这些过去三年，肯定 过去四年，如果我们有bogosort。 下面是伪代码合并排序。 当n个元素的输入，因此给予 大小为n的阵列中，如果n小于2， 返回。 那么，为什么我有 理智首先检查？ 有什么含义，如果我交给你 一个数组，其长度n小于2？ 它已经排序，很明显，对吧？ 因为列表中任一具有 一种元素，它是平凡 排序的，因为它是 唯一存在。 或者说，它的大小为零，这意味着中 有天生什么来排序，所以 它的排序。 只是有没有什么不对劲的地方。 这就是我们所谓的基本情况。 这是精神相似 以我们与麦克一样。 如果小李的电话本，打电话给他。 如果他不在那里，就放弃。 这是一个所谓的基本情况，以确保 这个算法在一天结束时 将停止在某些情况下。 但这里的信仰的飞跃，现在，否则， 排序的元素的左半边， 然后进行排序的权利 一半的元素， 然后合并排序的一半。 而这里也正是感觉 像我们科平了。 我问你排序 n个元素，而我 他说，好了，不要它通过排序 左和排序的权利。 但我嘴上说 其他的东西，这 是看来关键主题 在直觉到目前为止， 有合并的这个第三步骤。 其中，即使它 似乎在精神上如此愚蠢， 就像刚合并的东西 在一起，似乎 为朝着一个关键步骤 两个问题，即重组 一半最终被划分。 所以，归并排序，让我们做到这一点，如果你愿意 幽默的我，多了一个示范， 只是让我们有一些 数字与合作。 我可以换8压力 球八个人？ 好吧，你怎么样3，你们四个 在本节中，五，六，让我们 做7，8，上来吧。 好吧，是的确定。 减去8，我们走了，再加上1。 优秀的。 没事上来吧，让我们 赶紧给你的数字。 排名第二，第三位，排名第四， 第五，六，七，八名。 我没有做过8这个时候。 好了，如果你可以去进取， 让我们梳理了原来的顺序 我们昨天看了这 这样，如果你不介意的话。 让我们做吧的桌子前。 好吧，那么归并排序。 这是到哪里去 获得有趣的一种， 因为我似乎给自己 这么多的信息较少今天。 所以归并排序首先 对n个元素的输入， 这显然​​不是少了两个比，它的 8，让我有更多的工作要做。 所以，现在我们精神上的类 现在在else分支， 这意味着三个步骤。 首先，我要排序 元件的左半部。 那么，如何去这样做？ 好吧，我要种 精神上将列表在这里， 您不必 身体动了，我 打算只把重点放在 这里的元素的左半边。 那么，如何去整理 现在大小4名单？ 什么是我的算法？ 首先我检查为n比少了两个，不， 所以我继续在else块了。 排序左前卫的元素。 所以，现在再次，精神， 而这正是 你必须累积了大量的 精神的历史，如果你愿意。 现在我左边的分类 一半的左半部。 好了，所以现在我把我相同的合并 排序算法，是n小于2？ 不，它是两个，所以我要排序 左半边和右一半。 所以在这里，我们走了，排序的左半部。 为什么不干脆 走了一步。 你叫什么名字？ 听众：达伦。 音箱：丹。 丹上前。 听众：达伦。 演讲嘉宾：达伦，完成。 你说达伦还是丹？ 听众：达伦。 演讲嘉宾：达伦。 好吧，达伦已加强 向前和他现在排序。 这几乎是一个 空洞的说法，对吗？ 我岂不真的似乎要实现 任何事情，但是让我们继续。 现在让我排序的权利 一半的元素。 你叫什么名字？ 听众：卢克。 演讲嘉宾：卢克。 来吧，向前一步。 完成后，我已经整理卢克。 左半现在排序和 右半现在排序， 但同样的，这里有一个关键的步骤。 什么才是我旁边需要做什么？ 合并排序的一半。 现在我们只是有 大家来回这种方式， 因为那种我需要的 一些暂存空间。 这几乎就像这些 家伙都在桌子上， 我需要一些空间 移动至周围。 所以，我要合并 你们看 在左半侧和右半侧。 又是谁显然是第一位的， 左半或右半？ 所以，正确的上半年，让我们在移动路 这里达伦的原始位置。 现在合并他们的左半部分， 达伦是怎么回事向右移动那里。 所以感觉差不多 冒泡排序的效果， 但我的基本算法， 非常不同，这一次。 但现在也正是事情变得 有点讨厌，因为你 要倒带精神 在哪里我离开了。 我刚刚合并排序的一半， 这意味着我在我的算法是在哪里呢？ 我的右半边进行排序，对不对？ 如果你后退，从字面上 在视频中，您将 看到我们到了这 点卢克和达伦的 由左排序 一半的左半部。 然后，我们的合并 排序一半，这 装置的下一步骤是分类的 左半部右半部。 好吧，让我们 更迅速地做到这一点。 好吧，六，我会要求 现在你的排序，加油前进。 你叫什么名字？ 听众：阿德里亚诺。 演讲嘉宾：阿德里亚诺。 阿德里亚诺现在排序。 而你叫什么名字？ 听众：亚历克斯。 演讲嘉宾：亚历克斯现在排序。 左前卫，右前卫， 什么是最后一步？ 合并。 很琐碎，所以我 要在六个月合并， 退一步， 8，退一步。 现在发现这是 一个有用的外卖，有什么 现在真正对的左半 列表中，不管我们怎么开始的？ 它的排序。 现在，它不是在整理 物联网的大计划， 但它是独立地排序 的另一半。 现在哪一步我是在如果我坚持 复卷怎么回事开始？ 现在我要右半排序。 所以，现在我们回来的路上，在 故事的开始， 并让我们这样做更为迅速。 所以，我要排序 整个列表的右半边。 什么是下一步？ 排序的右半​​边的左一半。 排序的左半 右半部分的左半部。 而你叫什么名字？ 听众：奥马尔。 演讲嘉宾：奥马尔，向前一步，完成。 左半部分是排序。 而你叫什么名字？ 听众：克里斯。 演讲嘉宾：克里斯，退一步 未来，你现在来分类的。 什么是现在的关键一步？ 合并。 所以，一个人要融入地方 在这里，如果你能退后一步， 三是要 退一步，合并。 这样的左半 右半部，现已排序。 坦率地说，这个算法感觉就像我们 这是在浪费这样的时间比以前， 但如果我们在实时这样做，我们将 看到外卖成为怎样的人。 现在我在这里，对不对 一半的右边一半的， 让我继续前进，排序的左半部。 向前迈出一步，你叫什么名字？ 听众：拉姆齐。 演讲嘉宾：拉姆齐现在排序。 你叫什么名字？ 听众：码头。 演讲嘉宾：滨海现在排序， 好吧，如果你走了一步。 这里关键的一步，现在被合并，我 打算从我的两个列表采摘， 左，右。 五是要放在第一位， 七是要到明年。 再次，这是故意的。 他们正在做的事实 步骤前进和后退 是代表我们不能 这样做算法的地方，很容易 如冒泡排序和选择排序， 和插入排序，我们只是 不停交换的人。 我真的需要一个排序 草稿纸在其中 把这些人 而我的融合， 然后我可以把它们放回原处。 这就是关键，因为我使用的是 新的资源，空间，而不仅仅是时间。 OK，这是惊人的。 左半部分是排序，右半部分是 排序的，现在的关键合成步骤。 我怎么合并呢？ 所以，如果你按照我 左手和右手 我要指出我的左手 在左前卫，我的右手 在右前卫的，现在我要 决定一步步谁在合并。 谁显然是第一位的？ 第一。 所以来这边， 这里是我们的便笺。 所以，现在排名第一，并通知 我会尽我的右手， 我打算将我的右手1 跳过来点排名第三， 现在我要 同样的决定。 而实际上站在正确的 卢克在这里，如果你能面前， 因为这是我们的便笺。 那么，谁随之而来的？ 我们有卢克与排名第二 或者克里斯与排名第三。 显然卢克，数 2，让你来这里。 但是，我的左手现在是要 递增为指向达伦， 而这里的关键拿走了 合并，我将继续这样做， 很明显，如果你有种 遵循的逻辑。 但我的手都从未 要往回走， 这意味着我永远只能移动到 左边有我的合并过程， 那将是关键 我们的分析在短短的一瞬间。 所以，现在让我们迅速完成这件事。 所以三随之而来的， 然后4随之而来的， 现在5随之而来的，则6， 七，最后8。 感觉就像是最慢的算法 然而，但如果我们真的 在相同的排序运行 时钟速度的，所以要 说，具有相同的 滴答作响的时钟和以前一样。 为什么呢？ 好吧，让我们来 看的最终结果。 让我们回到了这里，让我 拉了一个直观演示 什么，我们只是做了。 放大在这里，在这个 在此页面，告诉火狐 我们要排队 在此框，让我们 说冒泡排序，与 我们现在非常熟悉， 选择排序，这是另一种 相当简单的， 现在今天的归并排序，其中 将是我们的高潮结局。 花了这么多时间越长的原因 这里有人类和我口头上的， 很明显，我解释每一步。 但如果你只需要执行这一点，很多 像我们做冒泡排序和选择 排序不仅在视觉上，观看 到底有多少更有效 这个杠杆化 分裂和征服 可以在应用到数据集的 即使没有大小八，但即使多了， 要大得多。 我给你通过归并排序，方 方用这些算法。 这是会得到痛苦 很快，并且结束 没有特别的高潮， 他们刚刚结束了排序。 但关键带走的是 看快多少排序合并 是的，除非你觉得我 只是那种玩弄你。 如果我们这样做了，最后一次， 让我们重新加载此，让我们回去 选择冒泡排序， 而只是踢， 让我们来选择插入 排序，只是为了好措施。 而这一次又一次，让我们 选择合并排序，让我们 实际上并排运行这些侧。 它不是，其实是侥幸。 我已经做了有效的是我 分我输入了一半，同样， 又一次，又一次。 而且也只有这么多的时候，你可以 将您的输入成两半，左 右。 那是什么，我们总是看到公式 描述该师在半 一次，又一次，又一次，又一次？ 听众：日志N。 演讲嘉宾：日志N。 但还有另一个关键的一步， 这种算法是不记录n步。 如果它仅记录n步， 我们将在同样的问题 如之前在这里我们不能 确保一切的排序。 你必须微创看看n个元素 可以肯定的n个元素进行排序， 否则就是信仰的飞跃。 所以它的最低限度日志n步，但 那么这个合并的关键一步 在这里我合并了我的左半边，右 半走过的阶段？ 多少个步骤是合并？ 这是N，但我不只是 合并的最后时间。 在每个这些嵌套调用，每个 这些嵌套的合并，我还是整理。 我将这这两个家伙，那么这两个 男人，那么这两个家伙，等等。 所以，我没有再合并，再。 多少次？ 所以每次我分了 列表中的一半，我做了合并。 将列表中的一半，做了合并。 因此，如果分割清单 可以做日志的n倍， 和合并，最终占据N 步骤，可能是什么，现在的上 结合在跑步 我们的算法的时间呢？ Ñ​​日志N。 事实上，这就是 我们在这里实现。 所以，你看到的时候视觉上的感觉 这三样东西并行走线 为n的平方与n的 平方与n的日志ñ。 这从根本上，我们会看到， 不仅是现在，而且在将来， 是非常非常快。 掌声鼓励了这些家伙， 我会奖励他们压力球。 让我们今天在这里宣布休会，并 我们会看到你在星期一。