[Powered by Google Translate] [第3条 - 更舒适]
[罗布·鲍登 - 哈佛大学]
>> [这是CS50。 - CS50.TV]
>> 所以第一个问题是奇怪的措辞。
GDB可以让你“调试”程序，但是，更具体地说，是什么让你这样做吗？
我会回答这个问题，我不知道发生了什么准确预计，
所以我猜它的东西，它的沿线，让你一步一步
步行通过该计划，与它进行交互，更改变量，做所有这些事情 -
基本上完全控制程序的执行
并检查执行的程序的一部分。
因此，这些功能可以让你调试的东西。
好吧。
为什么二进制搜索需要一个数组进行排序？
谁愿意回答这个问题吗？
[学生]：因为这是行不通的，如果它不排序。 >>呀。 [笑声]
如果没有排序，那是不可能的分裂它的一半
知道这一切的左侧是少的一切权利
大于中间值。
因此，它需要进行排序。
好吧。
为什么是冒泡排序在O n的平方吗？
有谁首先要给予什么冒泡排序是一个非常快的高层次的概述？
[学生]：基本上，您的每一个元素，你去检查的前几个元素。
吧，如果的你交换他们的地方，然后你查了下几个元素等。
当你到达终点，那么你知道，最大的元素放在最后，
所以你忽视这一点的话，你继续经历，
每一次，你必须检查少了一个元素，直到你不改变。 >>呀。
这就是所谓的冒泡排序，因为如果你在其一侧翻转数组，所以它的向上和向下，垂直，
那么大的值会沉底，小的值将泡沫到顶部。
这就是它得到了它的名字。
是啊，你只是去。
你继续通过阵列，交换中的较​​大值
得到最大的值的底部。
>> 为什么是IT O n的平方呢？
首先，没有人说为什么它是Øn的平方？
[学生]由于每次运行时，它会n次。
您只能确保你已经采取了最大的元素一路下跌，
那么，你必须重复一样多的元素。 >>呀。
所以记住什么大的“O”表示什么大的欧米茄手段。
大O是一样的上限如何慢，其实是可以运行的。
所以说的O n的平方，它是不是O的n否则将无法运行
线性时间，但它是O n的立方
因为它的边界是由O n个立方。
如果它一定的O n的平方，那么它的界也由N的立方。
因此，它是n的平方，绝对是最糟糕的情况下，不能做的更好比n的平方，
这就是为什么它是O n个平方。
它是如何为n的平方，所以看到轻微的数学，
如果我们有五件事情在我们的名单中，第一次能有多少掉期我们可能需要进行
为了得到它？让我们实际上只是 -
多少掉期，我们要通过数组必须在第一次运行的冒泡排序？
[学生]：N - 1。 >>呀。
>> 如果有5个元素，我们需要做N - 1。
然后在第二个我们要多少掉期使吗？
[学生]：N - 2。 >>呀。
第三个是为n - 3，然后为方便起见，我会写的最后两
然后我们需要做2掉期和1交换。
我想最后一个可能会或可能不会实际需要的情况发​​生。
它是一个交换吗？我不知道。
因此，这些掉期交易的总金额，或者至少比较，你必须做出。
即使你不交换，你仍然需要的值进行比较。
因此，有n - 1个比较，在第一次运行时通过数组。
如果你重新安排这些事情，让我们实际上使六样东西，这样的事情叠加起来很好，
然后我会做3，2，1。
因此，只要重新排列这些钱，我们希望看到我们做多少次比较
在整个算法。
因此，如果我们把这些家伙在这里，
然后我们还只是总结然而有许多比较。
但是，如果我们总结，我们总结，我们总结这些，
它仍然是同样的问题。我们只是总结了这些特殊群体。
>> 所以，现在我们正在总结3 N。这不只是3 n的。
它总是要N / 2 n的。
所以，我们在这里发生的有6个。
如果我们有10件事情，那么我们可以做到这一点分组为5个不同的东西对
和N + N + N + N + N。
所以，你总是会得到N / 2 n的，所以这一点，我们就会把它记为n的平方/ 2。
因此，即使它的一半，捎来的因素
由于这一事实，通过在阵列的每个迭代中，我们比较少1
所以这就是我们得到了超过2，但它仍然为n的平方。
我们不关心的常数因子的一半。
所以这样一个大O的东西很多依赖于只是做这类数学，
做算术金额的几何级数的东西，
但他们大多在此过程是非常简单的。
好吧。
为什么是插入排序在欧米茄的n？欧米茄是什么意思？
两名学生在一次发言 - 不知所云] >>呀。
欧米茄你能想到的下限。
>> 因此，无论您的插入排序算法的效率有多高，
无论通过在列表中的，它总是有比较至少有n个东西
或重复过N。
这是为什么？
[学生]因为如果列表已经排序，然后通过一次迭代
你的第一个元素是最少的，只能保证
和第二次迭​​代中，您只能保证前两个是
因为你不知道，其余的列表进行排序。 >>呀。
如果你传递一个完全排序的列表，最起码你得去所有的元素
看，没有什么需要左右移动。
因此，通过列表，并说哦，这已经排序，
这是不可能的，你知道它的排序，直到你检查每个元素
看，他们是在排序顺序。
所以插入排序的下限是欧米茄的n。
什么是最坏的情况下，归并排序的运行时间，
最坏的情况是大O吗？
因此，在最坏的情况下，如何合并排序运行？
[学生] n日志n。 >>呀。
一般最快的排序算法是n日志n。你不能做的更好。
>> 有特殊情况下，如果我们今天有时间 - 但我们可能won't -
我们可以看到，它比n日志n。
但在一般情况下，你不能做的更好比n日志n。
合并排序恰好是一个你应该知道这门课程是n日志n。
因此，我们实际上将实施的今天。
最后，在不超过三句话，选择排序是如何工作的？
是否有人要回答的问题，我会计算你的句子
因为如果你在3 -
有谁还记得选择排序？
选择排序通常是很容易记住的名称。
您遍历该数组，无论值最大或最小 -
任何顺序排序
因此，让我们说，我们正在从最小到最大的排序。
您遍历数组，寻找任何的最小元素，
选择它，然后就交换，无论是摆在首位。
然后在数组中的第二次，再次寻找最小的元素，
选择它，然后交换在第二的位置。
因此，我们只是挑选和选择的最低值
将它们插入到阵列的前面，直到它被排序。
该问题吗？
>> 这些不可避免地出现在你的表格必须填写，当你提交的pset。
这些基本上都是那些的答案。
好了，现在编码的问题。
我已经发送过电子邮件 - 没有人不明白的电子邮件吗？好吧。
我已经发送过电子邮件，我们将要使用的空间，
如果你点击我的名字 - 所以我想我会在底部
因为向后ŕ - 但如果你点击我的名字，你会看到两个版本。
第1次修订将要被我已经复制并粘贴代码到空间
搜索的事情，你将不得不实行。
第二次修订将排序的事情，我们实施之后。
因此，您可以点击我的第1次修订，并从那里工作。
现在我们要实现二进制搜索。
>> 有没有人想只给一个伪高层次的解释
我们有做搜索？是啊。
[学生]你只取中间的数组，如果你正在寻找
小于或大于。
如果是少了，你去的那一半少，
，如果它更重要的是，你去了一半，更重要的是，你重复，直到你刚刚得到的一件事。
鲍登]是啊。
请注意，我们的数字数组已经排序，
因此，这意味着，我们可以利用这一点，我们可以先检查，
好了，我在寻找数50。
所以，我可以进入中间。
中间是很难界定的东西，它是一个偶数时，
但我们只能说我们会永远的中间截断。
所以在这里我们8件事，所以中间是16。
我在寻找50，所以50大于16。
所以，现在我基本上可以把我的数组，因为这些元素。
我可以扔掉一切从16倍。
现在我的数组是这4个元素，让我再说一遍。
于是我想再次找到中间，这将是42。
42小于50，这样我就可以扔掉这两种元素。
这是我剩下的阵列。
我要再次找到中间。
我想50是一个坏榜样，因为我总是扔掉的左的东西，
但相同的措施，如果我在寻找的东西
，它是小于的元素，我目前正在研究，
然后，我要扔掉的一切权利。
所以，现在我们需要实现这一点。
请注意，我们需要传递的大小。
我们也可以不需要进行硬编码的大小。
因此，如果我们摆脱这种定义 -
好吧。
我怎样才能很好地计算出目前的数字数组的大小是什么？
>> 数字数组有多少个元素？
[学生]数字，括号，长度？
[鲍登]不存在C中
需要的长度。
阵列所不具有的特性，所以数组有没有length属性
这只会给你然而，它正好是。
[学生]它有多大的内存和除以多少 - “”是啊。
所以我们可以看到它有多大的内存？ >> [学生] SIZEOF。 “是啊，大小。
sizeof是操作员要返回的数字数组的大小。
这是怎么回事，然而，许多整数有一个整数的大小
因为这是多大的内存，它实际上是占用了。
所以，如果我想在阵列中的一些事情，
然后，我会想除以整数的大小。
好吧。所以，让我在这里传递的大小。
为什么我需要传递的大小吗？
为什么我不能只是做了诠释大小=大小（干草堆）/ sizeof（int）的的吗？
为什么不工作？
[学生]：这是不是一个全局变量。
鲍登草堆存在，我们通过在数字草垛，
这是一种什么样的来了伏笔。是啊。
[学生]草堆只是对它的引用，所以它会返回引用是多大。
是啊。
我怀疑你在课堂上看到了堆栈真的，对吗？
我们刚刚谈到它。
所以堆栈是其中所有变量都以被存储。
>> 在堆栈中为局部变量的分配的任何内存是怎么回事，
每一个函数都有自己的堆栈空间，它自己的堆栈帧是它叫什么。
因此，主要有它的栈帧，然后在它里面会存在这方面的数字阵列，
它的尺寸大小（数字）。
这将有大小除以元素大小的数字，
但主要的堆栈帧中所有的生命。
当我们调用搜索，搜索得到它自己的堆栈帧，
自己的空间来存储所有的局部变量。
但这些参数 - 草垛是不是这整个数组的副本。
我们不会将整个阵列作为复制到搜索。
它只是传递一个引用到该数组。
因此，搜索就可以访问这些数字，通过这个引用。
它仍然访问主要的堆栈帧里面的东西，生活，
但基本上，当我们得到的指针，这应该是很快，
这是指针是什么。
只是指针引用的东西，你可以使用指针来访问的东西
在其他的事情'堆栈帧。
因此，尽管数字是当地主，我们仍然可以访问它，通过这个指针。
但是，因为它只是一个指针，它只是一个参考，
大小（干草堆）返回引用本身的大小。
它不会返回它指向的东西的大小。
它不返回数字的实际大小。
所以这是去上班，因为我们希望它。
>> 该问题吗？
指针将进入显着血淋淋的细节在数周的到来。
这就是为什么有很多的东西，你看，大多数搜索的东西或排序的东西，
他们几乎所有的事情，需要采取实际数组的大小，
因为在C中，我们不知道数组的大小。
您需要手动将它传递进来。
你也可以手动通过整个阵列，因为你只是路过的参考
它不能得到从基准的大小。
好吧。
所以，现在我们要实现什么解释过。
你可以在一分钟，
你不必担心让一切完美的100％。
只写了一半的伪代码，你是怎么想它应该工作。
好吧。
没有必要完全做到这一点。
但是，没有人感到舒适与他们有什么到目前为止，
喜欢的东西，我们可以一起吗？
有没有人想自愿吗？或者我会随机挑选。
它不具有任何措施，而是东西，我们可以通过修改进入了工作状态是正确的。
[学生]：当然可以。 “好了。
所以，你可以保存修改，点击保存图标上的小。
你专区Ramya，对不对？ >> [学生]是啊。 >> [鲍登]好吧。
所以，现在我可以看到你的修订，每个人都可以拉起来的修订。
在这里，我们有 - 好。
于是专区Ramya的递归解决方案，这无疑是一个有效的解决方案。
有两种方法可以做到这一点问题。
你可以做到这一点迭代或递归。
大多数遇到的问题，可以做递归也可以通过反复。
所以，在这里，我们已经做了递归。
>> 是否有人想函数的递归定义是什么意思？
[学生]当你有一个函数调用自身
然后调用，直到它与真正的和真实的。 >>呀。
递归函数仅仅是一个函数调用自己的。
有三个大的事情，必须有一个递归函数。
第一种是很明显，它调用自身。
第二个是基本情况。
因此，在某些时候，需要停止调用本身，
而这正是的基本情况。
所以，在这里，我们知道，我们应该停止，我们应该放弃在我们的搜索
当开始等于结束 - 我们就去了，这意味着什么。
不过，最后的最后一件事是重要的递归函数：
函数必须以某种方式接近的基本情况。
喜欢，如果你不更新任何东西时，你的第二次递归调用，
如果你真的只是调用该函数使用相同的参数
没有全局变量发生了变化或任何东西，
你将永远不会达到的基本情况，在这种情况下，这是很糟糕。
这将是一个无限递归和栈溢出。
但在这里我们可以看到，在更新发生，因为我们正在更新启动+ / 2年底，
我们正在更新结束参数在这里，我们在这里更新start参数。
因此，在所有的递归调用，我们要更新的东西。好吧。
你想，走我们通过您的解决方案？ “当然可以。
我使用搜索帮助，这样每次我有这样的函数调用
我有我在寻找数组中的开始和结束
在哪里，我要找的数组。
>> 在每一个步骤，它说这是中间的元素，这是启动+ / 2年底，
等于我们正在寻找什么？
如果是这样，那么我们发现它，我想会向上传递层次的递归。
如果这是不正确的，那么我们是否该中间​​值的数组过大，
在这种情况下，我们看阵列的左半边，从开始到中间索引。
否则，我们做半场结束。
鲍登]好吧。
听起来很好。
好了，这样一对夫妇的事情，而实际上，这是一个非常高层次的东西
你永远不会知道这门课程，但它是真实的。
递归函数，你总是听到的是一个糟糕的协议
因为如果你递归地调用自己太多的时间，你会得到堆栈溢出
因为，正如我之前说的，每一个函数都有自己的堆栈帧。
因此，每次调用递归函数都有自己的堆栈帧。
所以，如果你1000递归调用，你会得到1000个堆栈帧，
快，你有太多的栈帧，和刚刚突破。
所以这就是为什么递归函数一般都是坏的。
但有一个不错的递归函数的子集称为尾递归函数，
发生这种情况是一个例子，其中，如果编译器注意到这个
它应该，我认为 - 铛，如果你传递给它的O2标志
然后，它会发现这是尾递归的东西好。
>> 一遍又一遍，每一次递归调用，它会重复使用相同的堆栈帧。
因此，由于您使用的是相同的堆栈帧，你不不必担心
曾经堆栈溢出，并在同一时间，像你说的，
一旦你返回true，那么它返回所有这些堆栈帧的
和第10个调用搜索帮助返回的第9位，具有返回到8号。
因此，不需要时发生的功能是尾递归。
是什么让这个功能尾递归的通知，对于任何给定调用搜索帮助
的递归调用它的是它的返回。
因此，在第一次调用搜索帮助，我们将立即返回false，
立即返回true，否则我们做一个递归调用搜索帮助
我们回到调用返回。
而且我们不能这样做，如果我们做的东西，如int x =搜索帮助，返回X * 2，
只是一些随机的变化。
>> 所以，现在这个递归调用，此int x =搜索帮助递归调用，
不再是尾递归，因为它实际上不返回
返回到前一个堆栈帧，这样，以前的呼叫的功能
然后做一些事情的返回值。
因此，这是不是尾递归，但我们以前是很好的尾递归。是啊。
[学生]不应该的第二基本情况，首先检查
因为有可能的情况就是当你传递给它的参数
你已经开始=结束，但他们是针价值。
问题是不能运行的情况下到针到底是值
或开始=结束，适当的，开始结束
，你有没有检查那个特定的值，
然后开始+ / 2年底将是相同的值。
但我们已经返回false，我们从来没有真正得到的价值。
所以，最起码，在第一次调用，如果大小是0，那么，我们要返回false。
但是，如果大小为1，然后开始不等于结束，
我们将至少检查一个元素。
但我认为你是正确的，我们就可以结束的情况下，启动+ / 2年底，
开始结束了一样启动+ / 2年底，
但我们从来没有真正检查该元素。
>> 因此，如果我们首先检查的是中间的元素，我们正在寻找的价值，
那么我们就可以立即返回true。
否则，如果他们是平等的，那么有没有点继续
因为我们只是要更新的情况下，我们是一个单元素数组。
如果，不是一个单一的元素是我们正在寻找的，
然后一切是错误的。是啊。
[学生]的事情是，由于大小实际上是大于在数组中的元素数
已经有一个偏移 - “等的大小 -
[学生]说，如果数组的大小为0，然后搜索帮助将实际检查草垛0
在第一次调用。
数组的大小为0，所以0是 - “”是啊。
还有另外一件事， - 这可能是很好的。让我们来想想。
所以，如果数组有10个元素，我们要检查的是中间的一个指数5，
所以我们正在检查，让我们说，该值小于。
因此，我们把一切都带走5起。
因此，+ / 2年底将是我们新的终端，
所以是的，它总是要留结束之后的数组。
如果它是一个情况下，如果是奇数或偶数，然后我们会检查，说，4，
但我们仍然丢掉 -
所以，是的，最终总是要超出了实际的数组。
所以我们的重点元素，最终总是要一前一后的。
所以，如果开始做以往任何时候都等于结束，我们是在一个数组的大小为0。
>> 其他的事情，我的想法是，我们正在更新开始启动+ / 2年底，
所以这种情况下，我有麻烦，在那里开始+端/ 2
是的，我们正在检查的元素。
比方说，我们这10个元素的数组。不管。
因此，+ / 2年底将是像这样的东西，
如果这不是价值，说，我们要更新。
该值越大，所以，我们想看看在这半年的数组。
因此，我们如何更新开始，我们要更新开始到现在是这样的元素。
但是，这可能仍然工作，或最起码，你可以开始+结束/ 2 + 1。
[学生]您不需要开始+结束[听不清] >>呀。
我们已经检查了这个元素，而且知道这是不是我们正在寻找一个。
因此，我们并不需要更新的开始是这样的元素。
我们可以跳过它，并更新开始是这样的元素。
而且是有过的情况下，让我们说，这是结束，
因此，然后开始应该是这样的，开始+结束/ 2应该是这样的，
开始+结束 - 是的，我认为它可以在无限递归。
比方说，它只是一个大小为2的数组或数组的大小为1。我认为这会工作。
目前，开始元素和结束是超越它。
因此，我们要检查的元素是这一个，
，然后我们在更新开始时，我们要更新开始为0 + 1/2，
这是要结束我们开始这个元素。
>> 所以，我们检查了一遍又一遍相同的元素。
因此，这是每一个递归调用的情况下，必须更新的东西。
因此，我们需要做的启动+端/ 2 + 1，否则有一个
在这里我们实际上没有更新的开始。
每个人都看到了吗？
好吧。
有没有人有问题，该解决方案或任何更多的评论？
好吧。没有任何人有一个迭代的解决方案，我们都可以看吗？
我们都这样做递归？
我也想，如果你打开​​了她，那么你可能会覆盖你的前一个。
它会自动保存吗？我还不能肯定。
没有任何人有反复？
我们可以一起穿过它，如果没有。
这个想法是将是相同的。
迭代的解决方案。
我们会想，基本上做的是同样的想法
在这里我们要跟踪的数组的数组新的结束和新的开始
做一遍又一遍。
并且如果我们跟踪作为开始标记和结束计划相交，
当时我们没有找到它，我们可以返回false。
那么，如何才能做到这一点？任何人有任何建议或代码为我拉起来吗？
[学生]做一个while循环。 >>呀。
你会希望做一个循环。
>> 你的代码，我可以拉，你要什么建议吗？
[学生]我是这么认为的。 >>所有权利。这使事情变得更容易。你叫什么名字？
[学生]卢卡斯。
第1次修订。好吧。
低就是我们俗称的开始之前。
是不完全是我们称为前结束。
其实，到底是现在在阵列内。这是我们应该考虑的元素。
如此之低是0，是阵列的大小， - 1，
，现在我们正在循环，我们正在检查 -
我想你可以穿过它。
什么是你的想法通过呢？走我们通过您的代码。
[学生]：当然可以。在草垛的中间值，并把它比作针。
所以，如果要大于你的针，然后你想 - 哦，其实，应该是向后。
你会想扔掉的右半边，所以是的，这应该是方法。
[鲍登]因此，这应该是少了呢？这就是你说的吗？ >> [学生]是啊。
鲍登]好吧。更少一些。
所以，如果我们要找的是比我们想要的东西，
是啊，我们要扔掉的左半边，
这意味着我们正在更新我们的一切考虑
移动低的数组的权利。
这看起来不错。
我认为它有同样的问题，我们说，前一个，
其中，如果低为0和为1，则低+上/ 2的成立是同样的事情再次。
>> 甚至如果不是这样的情况下，它仍然是更有效地在至少
扔掉的元素，我们只是看着我们知道这是错误的。
如此之低+ / 2 + 1 - [学生]这应该是其他方式。
鲍登或者这应该是 - 1，另一个应该是+ 1。
[学生]：应该有一个双等号。 >> [鲍登]是啊。
[学生]是啊。
好吧。
最后，现在，我们有这样的+ 1 - 1的事情，
是它 - 它可能不是 - 是为低，结束了更大的值比起来，有没有可能？
我认为唯一的方法可能发生的 - 它是可能的吗？ >> [学生]：我不知道。
但是，如果它被截断，然后得到减去1，然后 - “”是啊。
[学生]，可能会出现混乱。
我认为这应该是不错的，只是因为
结束下，他们必须是平等的，我想。
但如果他们是平等的，那么我们就不会做了while循环开始
我们只是将返回的值。因此，我认为，我们现在是很好的。
请注意，尽管这个问题已不再是递归的，
同一种想法适用于我们可以看到这本身很容易
一个递归的解决方案的事实，我们只是更新的指数，一遍又一遍，
我们正在做的小问题，我们关注的一个子集的数组。
[学生]如果低为0和1，它们都为0 + 1/2，这将去0，
，然后将+ 1， - 1。
[学生]：我们在哪里检查的平等？
就像如果中间实际上是针？
目前我们还没有这样做呢？哦！
如果it's -
是。我们不能只是做了测试，在这里，因为咱们说的第一个中间 -
[学生]：它实际上是想扔掉的结合。
所以，如果你扔掉绑定的，你必须先检查或任何。
啊。是啊。 >> [学生]是啊。
所以，现在我们丢掉了一个我们目前看，
这意味着我们现在还需要有
（干草堆（低+）/ 2] ==针），然后我们就可以返回true。
是否其他人或只是如果，我把它的字面意思是同样的事情
因为这会返回true。
所以我会把其他的话，但不要紧。
>> 因此，如果这一点，否则这一点，这是常见的事，我做
即使它的情况下，一切都很好，在这里，
如低永远不能大于了起来，这是不值得的推理​​是否是真实的。
所以，你可以说，而低是小于或等于
或在低是小于
这样，如果他们永远等于或低恰巧经过，
然后我们就可以打破这个循环。
问题，问题，意见吗？
好吧。这看起来不错。
现在，我们想要做的那种。
如果我们去我的第二次​​修订，我们看到这些相同的数字，
但现在他们不再有序。
我们要实现使用任何算法在O n日志n。
所以，你认为哪种算法，我们应该在这里实现吗？ >> [学生]归并排序。
鲍登]是啊。合并排序是O（n日志n），所以这就是我们要做的。
的问题将是非常相似的，
它轻易借钱给别人，自己一个递归的解决方案。
我们也可以拿出一个迭代的解决方案，如果我们想，
但递归会更容易在这里，我们应该做的递归。
我想我们将通过合并排序第一，
虽然已经有一个可爱的视频归并排序。 [笑声]
因此，合并排序有 - 我浪费这么多的本文。
哦，只有一个左。
所以合并。
哦，1，3，5。
好吧。
合并需要两个单独的阵列。
单独这两个数组进行排序。
因此，这个数组，1，3，5，排序。此阵列中，0，2，4，排序。
现在合并你应该做的是将它们组合成一个单一的阵列本身就是排序。
因此，我们希望，都将有它里面的这些元素的数组的大小为6
在排序顺序。
>> 因此，我们可以利用一个事实，即这两个数组进行排序
做到这一点的线性时间，
线性时间的意义，如果这个数组的大小为x，这是大小y，
那么总的算法应该是O（X + Y）。好吧。
因此，建议。
[学生]我们从左边开始？
所以，你把0下来，然后1，然后你在这里的2。
因此，它是一种像你有一个标签，向右移动。 >> [鲍登]是啊。
对于这些数组，如果我们只专注于最左边的元素。
因为这两个数组进行排序，我们知道，这2个元素
是任一阵列中的最小元素。
因此，这意味着这2个要素：1，必须是我们的合并数组中最小的元素。
碰巧的是，最小的是一个正确的时间。
因此，我们采取0，将其插入在左边，因为0小于1，
所以取0，将其插入到我们的第一个位置，然后更新
到现在为止的第一个元素。
现在，我们重复。
所以，现在我们比较2和1。 1较小，因此，我们将插入1。
我们更新该指针指向这个家伙。
现在，我们再次做到这一点，所以2。这将更新，比较这2个，3个。
此更新，然后4和5。
所以这是合并。
>> 这应该是很明显的，它是线性的时间，因为我们只是一次过的每个元素。
这是实施合并排序是这样做的最大的一步。
它并不难。
有两件事情要担心的是，比方说，我们合并1，2，3，4，5，6。
在这种情况下，我们最终场景中的这个人会是较小的，
然后我们更新this指针，这将是更小，更新，
这其中的体积更小，现在你不得不承认
当你运行的元素比较。
因为我们已经使用了这整个阵列，
此数组中的一切现在只是插入到这里。
所以，如果我们运行其中之一，我们的阵列已经完全融合进点，
然后我们就采取的其他阵列中的所有元素，并将其插入到数组末尾的。
因此，我们就可以插入4，5，6。好吧。
这是一件事要注意的。
实现这应该是第1步。
合并排序，然后此基础上，它的2个步骤，2个愚蠢的步骤。
让我们把这个数组中。
所以，归并排序，第1步是，递归打破数组转换成半。
所以这个数组分割成两半。
我们现在有4，15，16，50和8，23，42，108。
现在，我们做了一遍，我们分裂成两半。
我会做的这一边。
因此，4，15和16，50。
在这里，我们会做同样的事情。
现在，我们把它分解成半。
我们有4个，15，16，50。
所以这是我们的基本情况。
一旦数组的大小为1，那么我们就停止分裂成两半。
>> 现在我们该怎么做这个吗？
我们结束了，这也将分解成8，23，42，和108。
所以，现在，我们在这一点上，现在归并排序的步骤2的合并对的列表。
因此，我们要合并这些。我们只是调用合并。
我们知道合并将返回这些排序。
4，15。
现在，我们要合并这些，这将返回一个列表的排序顺序，
16，50。
我们合并者 - 我不能写 - 8，23，42，108。
因此，我们必须对一次合并。
现在，我们只需再合并。
请注意，每个列表进行排序本身，
然后我们就可以合并这些列表进行排序的列表大小为4
合并这两个列表进行排序的列表大小为4。
最后，我们可以合并这两个列表大小为4，得到一个列表进行排序大小为8。
因此，看，这是整体的n日志n，我们已经看到的，合并是线性的，
所以，当我们在处理这些的合并，等等之类的整体成本合并
这两个名单只是因为 -
好，这是O n个，但N在这里仅仅是这2个元素，所以它的2。
而这些2将2和2将是2和2将是2，
在所有的合并，我们需要做的，我们做Ň。
像2 + 2 + 2 + 2是8，它是N，
所以在这个集合的合并成本是n。
然后是同样的东西在这里。
我们将合并这两个，那么这些2，本次合并及个别将采取四项业务，
本次合并将采取四则运算，但再一次，在所有这些，
我们最终合并N总的事情，所以这一步需要Ň。
因此，每个级别需要n个元素被合并。
>> 有多少级？
在每个级别上，我们的阵列生长的大小。
在这里我们的数组的大小为1，在这里，他们是大小为2，在这里，他们是大小为4，
最后，它们的大小为8。
所以，因为它增加了一倍，有将是一个总的日志n这些水平。
所以取n日志n个层次，每个人的水平总运营，
我们得到了一个n日志n算法。
有问题吗？
人已经取得了进展如何实现这一点呢？
有人已经在一个国家，在那里我可以拉起自己的代码吗？
我可以给一分钟。
此人将变得更长。
我强烈建议复发 -
你不必做递归合并
递归合并，因为这样做，你将不得不通过不同大小的一堆。
可以，但是这很烦人。
但是，递归进行排序本身是很容易的。
你只从字面上调用sort左半边，右半边的排序上。好吧。
任何人有什么我可以拉起来吗？
不然我会给一分钟。
好吧。
任何人有什么我们可以使用吗？
否则，我们就与这，然后从那里展开。
>> 任何人有以上这一点，我可以拉起来吗？
[学生]是啊。你可以把我的。 >>所有权利。
是的！
[学生]有很多的条件。哦，拍摄。你能 -
[学生]我一定要救它。 >>呀。
所以，我们做单独的合并。
哦，但它不是那么糟糕。
好吧。
因此，排序本身就是只是打电话mergeSortHelp。
我们解释，什么mergeSortHelp。
[学生] MergeSortHelp几乎没有两个主要步骤，
这是分类，每个阵列的一半，然后合并他们两个。
[鲍登]好吧，所以给了我第二次​​。
我认为这 - >> [学生]我需要 -
是啊。我失去了一些东西。
在合并，我意识到，我需要创建一个新的数组
因为我不能这样做的地方。 “是的。你不能。正确的。
[学生]：因此，我创建了一个新的阵列。
我忘了在年底合并，重新更改。
好吧。我们需要一个新的阵列。
在合并排序，这是几乎总是正确的。
一个更好的算法，时间上的成本部分
几乎总是需要使用更多的内存。
所以在这里，无论你怎么做归并排序，
你将不可避免地需要使用一些额外的内存。
他或她创造了一个新的阵列。
然后你说结束时，我们只需要到新的数组复制到原来的数组。
[学生]我是这么认为的，是的。
我不知道如果这样的作品在计数的参考或任何方面 -
是的，它会奏效。 >> [学生]好吧。
你有没有尝试运行此？ >> [学生]不，还没有。 “好了。
尝试运行它，然后我就说说它的第二个。
[学生]我需要把所有的函数原型和一切，但是，对不对？
函数原型。哦，你说的一样 - 是的。
排序打电话mergeSortHelp。
>> 所以为了进行排序打电话mergeSortHelp，mergeSortHelp必须已定义
排序或之前，我们需要的只是原型。只需复制并粘贴。
同样，mergeSortHelp被调用合并，
但合并还没有被定义，所以我们可以让mergeSortHelp知道
的合并将是什么样子，就是这样。
所以mergeSortHelp。
我们在这里有一个问题，我们有没有基础的情况下。
MergeSortHelp是递归的，所以任何递归函数
将需要某种形式的基本情况，知道什么时候才能停止递归调用本身。
什么是我们的基本情况，要在这里吗？是啊。
[学生]如果大小为1？ >> [鲍登]是的。
所以，像我们看到，我们停止分裂阵列
一旦我们得到数组的大小为1，这不可避免地排序。
因此，如果大小等于1，我们知道已经排序的数组，
这样，我们就可以返回。
>> 请注意，这是无效的，所以我们不返回任何特别的，我们只是返回。
好吧。所以这是我们的基本情况。
我想我们的基本情况也可能是，如果我们碰巧被合并数组的大小为0，
我们可能要停止在某些时候，
所以我们只能说大小小于2或小于或等于1
因此，这将工作的任何阵列。
好吧。
所以这是我们的基本情况。
现在你要带我们通过合并吗？
所有这些情况意味着什么呢？
在这里，我们只是在做同样的想法， -
[学生]我需要通过大小，所有的mergeSortHelp调用。
我一个额外的主增加的大小和它的不存在，如大小/ 2。
[鲍登]哦，尺寸/ 2，尺寸/ 2。 >> [学生]是啊，在上面的函数，以及。
鲍登]在这里？ >> [学生]只要大小。 >> [鲍登哦。大小，尺寸是多少？ >> [学生]是啊。
鲍登]好吧。
让我想到的第二个。
我们遇到的问题吗？
我们一直在治疗左为0。 >> [学生]第
这是不对的。抱歉。它应该是开始。是啊。
鲍登]好吧。我想效果更好。
和结束。好吧。
所以，现在你要带领我们通过合并吗？ >> [学生]好吧。
我只是走过，我创建了这个新阵列。
它的大小是阵列的部分的大小，我们要进行排序
，并试图找到的元素，我应该把在新的阵列步骤。
因此，要做到这一点，首先我检查的数组，如果左边的一半继续有任何更多的元素，
如果没有的话，那么你去，其他情况下，只是说
好了，它必须是在右边的数组，我们将提出，在目前的指数newArray。
>> 然后否则，我检查，如果阵列的右侧也完成，
在这种情况下，我只是把在左边。
这实际上可能不会是必要的。我不太肯定。
但无论如何，其他两个检查其中的两个较小的左侧或右侧。
此外，在每一种情况下，我在递增占位符，我增加。
鲍登]好吧。
看起来不错。
没有任何人有任何意见或疑虑或问题吗？
所以的情况下，我们到的是，要带的东西 - 它看起来像5 -
但我们要考虑的事情，我们需要合并左数组是否已用完，
右边的数组是否已用完的事情，我们需要合并 -
我指着不惜一切代价。
所以，左数组是否已用完的东西或已用完的东西，右边的数组。
这两种情况。
我们还需要琐碎的情况下，是否在左边的是不到正确的事情。
然后我们要选择左侧的事情。
这些都是案件。
因此，这是正确的，所以就是这样。
阵列离开了。它是1，2，3。好吧。所以，是的，这些都是我们可能想要做的四件事。
我们不会在一个迭代的解决方案。
我不会建议 -
合并排序是一个函数，是不是尾递归的例子，
这是不容易的是尾递归，
而且它不是很容易，使迭代。
这是很容易的。
此实现归并排序，
合并，不管你做什么，你要建立合并。
>> 因此，递归排序建立在合并的合并只是这三条线。
迭代，它是更烦人，更难以思考。
但是请注意，这不是尾递归，因为mergeSortHelp - 当它自称 -
这个递归调用返回后，需要做的事情。
所以这个栈帧必须继续存在，甚至在调用此函数。
然后当你调用这个堆栈帧必须继续存在
因为即使在这一号召，我们仍然需要进行合并。
它是平凡的，使该尾递归。
有问题吗？
好的。
所以回到排序 - 哦，有两件事我想告诉。好吧。
进行排序，我们将尽快这样做。
或搜索。排序？排序。是啊。
让我们回到了开始的排序。
我们要创建的数组进行排序的算法，该算法使用任何算法
在O的n。
所以，这怎么可能呢？有没有人有任何形式的 -
我之前在暗示 -
如果我们要提高n日志n的n为O，
我们已经改进我们的算法时间上，
这意味着什么，我们需要做弥补？
[学生]空间。 >>呀。我们将使用更多的空间。
，甚至没有更多的空间，这是成倍更多的空间。
因此，我认为这种类型的算法是伪的东西，伪多项式 -
伪 - 我不记得了。假的东西。
但是，这是因为我们需要用这么大的空间
这是可以实现的，但并不现实。
>> 以及我们如何做到这一点？
我们可以做到这一点，如果我们保证，任何特定的数组中的元素
低于一定的大小。
因此，让我们说，大小为200，
任何数组中的元素是尺寸200以下。
其实这是很不现实的。
你可以很容易有一个数组，你知道它的一切
是小于一些数字。
就像如果你有一些绝对庞大的向量或东西
但你知道一切都将是0和5之间，
那么它会更快地做到这一点。
，被绑定的任何元件上是5星，
所以这个界，这是你要多少内存使用。
因此，绑定的是200元。
从理论上讲，永远是绑定的，因为一个整数只能为达至4亿美元，
但是这是不切实际的，因为那么我们就可以使用的空间
4亿美元的订单。所以这是不现实的。
但在这里我们会说，我们的结合是200元。
在O n个这样做的窍门是我们另一个数组计数的大小约束。
因此，实际上，这是一条捷径 - 其实我不知道如果铛做这个。
但在GCC至少是 - 我是假设铛它太 -
这将初始化整个数组是0。
所以，如果我不想这样做，那么我可以分别做为（int i = 0;
我的束缚，我+ +）和计数[I] = 0;
所以，现在一切都被初始化为0。
我重申了我的阵列，
我在做什么是我清点人数的每一个 - 让我们去这里。
我们有4，15，16，50，8，23，42，108。
我的计数是在每个这些元素的出现数目。
让我们添加一对夫妇在这里有一些重复。
因此，我们的价值的价值，在这里，将是阵列[i]。
因此，值可能是4或8或什么的。
而现在，我计算该值多少我已经看到了，
所以计数[值] + +;
做到这一点后，计数看起来像0001。
让我们做计数[值] - 约束+ 1。
>> 现在，这只是考虑到这一事实，我们从0开始。
所以，如果200将是我们的最大数量，
0到200是201的东西。
所以，计数，它会看起来像00001，因为我们有一个4。
然后，我们将有0001，我们将有一个在8计数指数。
我们将有一个23指数数2。
我们将有一个42指数数2。
因此，我们可以使用计数。
所以num_of_item =计数[I]。
所以，如果num_of_item为2，这意味着我们要插入2号我
到我们的排序的数组。
因此，我们需要跟踪到数组有多远，我们是。
所以，索引= 0。
阵列 - 我刚写出来。
计数 -
数组[索引+ +] =我;
这是我想要的吗？我想这就是我想要的。
是的，这看起来不错。好吧。
因此，每个人都明白我的计数数组的目的是什么？
每个这些数字的出现的数目进行计数。
然后我遍历，计数数组，
和第i个位置的计数数组中
我是应该出现在我的排序的数组是多少。
这就是为什么，4的计数将是1
和8的计数将是1，23的计数为2。
因此，这是多少人，我想我排序的数组插入。
然后，我就这样做。
我插入num_of_item的，我到我的排序的数组。
>> 有问题吗？
如此反复，这是线性时间，因为我们都只是这一次迭代，
但它也是在这个数字恰好是线性，
，所以它在很大程度上取决于你所绑定的是什么。
200绑定，这是没有那么糟糕。
如果您的绑定将是10,000，那么这是有点差，
但如果你所绑定的4亿美元，这是完全不现实的
这个数组的大小为4亿美元，这是不现实的。
所以，就是这样。有问题吗？
[听不见的学生回应] >>好。
我实现了一个其他的事情时，我们会通过。
我认为这个问题是在卢卡斯和可能，我们已经看到的每一个。
我完全忘了。
我唯一​​想评论的是，当你正在处理的事情，比如指数，
你从来没有真正看到当你写一个for循环，
但在技术上，只要你处理这些指数，
你几乎总是要处理无符号整数。
这样做的原因是，当你正在处理的有符号整数，
所以，如果你有2个有符号整数和你加在一起
他们最终太大，那么你最终会用负数。
所以，什么是整数溢出。
>> 如果我增加2亿美元和1亿美元，我结束了负1亿。
这是整数，如何在电脑上工作。
因此，问题与使用 ​​-
这是罚款，除非低恰好为2亿美元，高达恰好为1亿美元，
那么这将是负1亿美元，然后我们要分2
并最终为负500万元。
因此，这是一个问题，如果你恰巧是通过一个数组
数十亿美元的东西。
但是，如果低+上发生溢出，那么这是一个问题。
只要我们让他们无符号，然后是2亿加1亿美元为3亿美元。
3亿美元，除以2，为1.5亿美元。
因此，只要他们是无符号的，一切都是完美的。
因此，这也是一个问题，当你写你的for循环，
而实际上，它很可能它会自动。
它实际上只是会骂你的。
因此，如果这个数字是太大而仅仅是一个整数，但它适合在一个无符号整数，
它会骂你的，所以这就是为什么你从​​来没有真正遇到的问题。
你可以看到索引是永远不会是负的，
因此，如果你要遍历一个数组，
你几乎总是可以说无符号整型我，但你真的不有。
事情是去上班几乎一样好。
好吧。 [窃窃私语]是什么时候？
最后一件事，我想向大家展示 - 我就这样做真快。
你知道我们是如何定义，所以我们可以定义MAX 5或东西吗？
让我们不要做最大。的绑定为200。这是我们以前所做的。
定义一个常量，它只是要进行复制和粘贴
发生的地方，我们写的约束。
>> 所以，我们其实可以做更多的＃define。
＃我们可以定义函数。
他们并不是真正的功能，但我们会打电话给他们的功能。
一个例子是类似的东西MAX（X，Y）被定义为（X <Y Y：X）。好吧。
所以，你应该习惯了三元运算符的语法，
但小于y是x？返回y，否则返回x。
所以你可以看到，你可以使之成为一个独立的功能，
的功能也能像布尔MAX需要两个参数，返回。
这是一种最常见的喔做这样的。我们称他们为宏。
这是一个宏。
这仅仅是它的语法。
做任何你想要的，你可以写一个宏。
你经常看到的宏用于调试的printfs之类的东西。
因此，一个类型的输出，有特殊的类似C中的常​​量强调LINE强调，
2强调LINE强调，
还有还有，我认为强调FUNC。这可能是它。类似的东西。
这些东西将被替换的函数名
或你的行的数目。
通常情况下，你下来，然后我可以在这里只是写写调试的printfs，
调试，它会打印的行数和功能，我恰巧在
它遇到，DEBUG声明。
您还可以打印其他的事情。
这么一件事，你应该注意的是，如果我发生的DOUBLE_MAX
像2 * y和2 * X。
因此，无论出于何种原因，你碰巧做了很多。
因此，使它的宏。
这实际上是坏了。
我想请通过做一些像DOUBLE_MAX（3，6）。
那么应该怎么回来了？
[学生] 12。
是的，12应该返回，返回12。
3被替换为x，6被替换为y，我们返回2 * 6，这是12。
现在看这个怎么样？我们应该回来了吗？
[学生] 14。 >>理想的情况下，14。
问题是，如何哈希定义的工作，请记住这是一个文字的复制和粘贴
几乎一切，还等什么，这是要被理解为
少为3比1加6次，2次加6，2倍，3。
>> 因此，对于这个原因，你几乎总是包裹在括号中的一切。
你几乎总是包裹在括号中的任何变量。
在有些情况下，你没有，就像我不知道我需要做的是在这里
因为小于的是几乎总是去上班，
虽然这可能也不是真实的。
如果有什么可笑的如DOUBLE_MAX（1 == 2），
那么这将被替换为3小于1等于等于2，
，这样的话它要小于1，这等于2，
这不是我们想要的。
因此，为了防止任何运算符优先级的问题，
始终包裹在括号中。
好吧。就是这样，下午5:30。
如果您有任何问题，在pset，让我们知道。
这应该是有趣的，和黑客版也更为现实
比去年的黑客版，所以我们希望你尝试了很多。
去年的非常热烈。
>> [CS50.TV]