>> [音乐播放]
国宝马兰所有权利。
好吧，欢迎回来。
因此，这是第4周，开始 其已经。
你还记得，上周，我们把 编码一旁只是一点点
我们开始交谈多一点 高层次，一样的东西
搜索和排序，这虽然 有些简单的想法，
代表的一类问题 你将开始解决特别
当你开始思考最终 项目和有趣的解决方案
可能有现实世界的问题。
现在是一个最简单的冒泡排序 这样的算法，它
通过这些小的数字工作 在一个列表中，或在一个数组中种
泡自己的方式到顶部， 大的数字移动一路下跌至
该列表的末尾。
>> 记得我们可以想象 一点点的冒泡排序
这样的事情。
所以，让我继续前进，单击“开始”。
我预选冒泡排序。
如果你还记得，高大的蓝色 线代表大号码，小
蓝线代表小数字， 我们通过这一而再，再而
再次，比较相邻的两间酒吧 红色，我们要交换
最大的和最小的，如果 他们秩序。
>> 因此，这会去，去，去 ，你会看到，较大的
元素使他们的方式 的权利，而较小的元素是
使他们的方式到左边。
但我们开始量化 效率，
在此算法中的质量。
和我们说，在最坏 情况下，该算法采取了
大约多少步？
>> 因此n的平方。
什么是N？
>> 观众：元素数目。
>> 国宝马兰因此n 数目的元素。
所以我们经常这样做。
任何时候，我们要谈论的大小 一个问题或大小的
输入，或花费的时间量 以产生输出，我们只
广义的任何 输入为n。
因此，早在第0周，数页 在电话簿为n。
学生人数 在房间里为：N。
所以在这里，太，我们继 这个模式。
>> 现在Ñ平方是不是特别 快，所以我们试图做的更好。
因此，我们看着一对夫妇 其他的算法，其中
选择排序。
所以选择排序 有一点不同。
这几乎是简单的，我敢说， 由此开始的开始
我们的志愿者名单，我只是再次 一次又一次经历
列表，采摘最小 在一个时间元素，并把他或
她在列表的开头。
>> 但是它也同样，一旦我们开始思考 通过数学和更大的
图片，想过多少次 我正想来回和背部
奔波，我们说，在最坏的情况下， 太多，选择排序，那是什么？
摆正Ń。
现在，在现实世界中，它可能 实际上是稍快。
因为再次，我没有保持 回溯一旦我排序
最小的元素。
但是，如果我们想想n很大， 如果你的，做出来的数学
我在黑板上，与n的平方 减去的东西，一切
除了n个平方，一旦N 变得非常大，不
真正的问题一样多。
因此，作为计算机科学家，我们的排序 视而不见较小
因素和只注重的因素 一个表达式，将会使
最大的区别。
>> 好了，最后，我们看了 在插入排序。
这是类似的精神，但 而不是通过迭代
选择最小的元素之一，在 的时间，我只花了我的手
处理，我决定，所有 没错，你属于这里。
然后我转移到下一个元素 并决定，他或
她属于这里。
然后，我和移动。
我可能会，一路走来， 以这些家伙转移
为他们腾出空间。
所以这是样的心理逆转 选择排序，我们
所谓插入排序。
>> 因此，这些主题发生 在现实世界中。
仅仅在几年前，当达到一定 参议员竞选总统，
，在当时的CEO埃里克·施密特（Eric Sc​​hmidt） 谷歌，居然有机会
采访他。
我们认为我们会分享此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戏剧]