>> [音乐播放]
>> ANDI鹏：欢迎来到第3个星期
谢谢你们，所有的未来 到今天这个较早的开始时间。
我们已经有了一个很好的，小 今天的亲密组。
所以希望我们会得到 说完，或许，早，
一点点今天一早。
那么快，只是一些 今天议程公告。
在我们开始之前，我们 要只走了过来
一些简单的后勤问题，PSET 题，汇报，这样的事情。
然后，我们将深入权利英寸
我们将使用一个名为GDB来调试程序 启动揭穿我们的代码，大卫
有一天在课堂解释。
我们就去了四种类型的排序。
我们会去超过他们很快 因为他们非常密集。
但是要知道，所有的幻灯片和 源代码是永远在线。
所以感到自由，在你细读，以 回去看看那个。
>> 我们将通过 渐近符号，这
仅仅是一个奇特的方式 说“运行时间”
在这里，我们有大O，从而 大卫在演讲解释。
而且我们也有欧米茄，这 是下界运行时。
我们将讨论多一点 深入的关于如何将这些工作。
最后，我们就去了二进制搜索， 因为很多你谁已经
看了一眼你的pset便知 这是一个问题，在你的pset中。
所以，你都会很高兴 我们管这个今天。
>> 最后，根据您的 部分反馈意见，其实我
在离开约15分钟 年底刚刚走了过来
pset3物流，如有问题， 也许有点指导，如果你愿意，
我们开始编程了。
因此，让我们试着打通 该材料很快。
然后我们就可以花一些时间 同时为处理器集更多的问题。
好。
>> 很快，所以只是少数 我们之前宣布从今天开始。
首先，欢迎来制作 它通过两个你的pset中。
我看了看your--是啊，让我们 获得掌声的那一个。
其实，我是真的， 真的很感动。
我分级的第一个PSET为你们 上周，你们做了令人难以置信的。
>> 风格是在点 除了一些意见。
请确保你总是 注释你的代码。
但是，你的pset中都点上。
并保持了起来。
而且它的良好的平地机到 看到你们是把
在你的风格尽可能多的努力 和你在你的代码设计
我们想给你看。
所以我路过沿着我的谢意 为助教的其余部分。
>> 然而，有一个 一些汇报的问题
我只是想说明一下 可使两个我的生活
和许多其它的 助教的生活更容易一点。
首先，我注意到这个 过去week--你们有多少人
已经运行check50 在你的代码提交？
好。
所以每个人都应该做的check50， 因为 - 一个secret--我们实际上
运行check50作为我们的正确性的一部分 脚本测试代码。
所以，如果你的代码是失败的 check50，在所有的可能性，
它可能会 失败我们检查为好。
有时候你们 有正确的答案。
像，在贪婪的，一些 你有正确的号码，
你只需打印出一些额外的东西。
而这额外的东西 实际上未通过检查，
因为电脑不 真的知道它在寻找。
因此，这将只运行通过， 看到你的输出不
符合我们所期待的答​​案 要，并注明这是错误的。
>> 我知道，发生在 你的一些情况下，这个星期。
所以，我回去和手动 regraded每个人的代码。
在未来虽然， 请，请确保
你正在运行 在你的代码检查50。
因为它是一种为TA疼痛 不得不回去手动再分类
每一个每一个PSET 单，很少错过实例。
所以，我没有脱任何积分。
我想，我脱下也许 的一个或两个用于设计。
在未来虽然，如果 你失败check50，
点将会采取 关闭正确性。
>> 此外，pset中是 由于周五中午。
我觉得有一个7分钟 我们给你迟到宽限期。
每哈佛的时候，他们获准 为7分钟迟到的一切。
因此，这里在耶鲁，我们将 坚持这一点。
但相当多，在12:07， 如果你的PSET不在，
这将是为后期标记。
因此，虽然它被标记为 为末，TA--我
还是会被分级您的pset。
所以，你仍然会看到一个档次的出现。
但是，要知道，在 学期结束时，
所有后期的pset将只是 由计算机自动归零。
>> 我们这样做有两个原因。
其中，有时我们得到 原谅，就像院长的借口，
后来，我不知道呢。
因此，我们希望确保我们分级 一切都为了以防万一，比如，我
缺少院长的借口。
其次，要 心中，你仍然可以
摔个PSET的 有完整的范围点。
因此，我们要分级 所有的pset只是
以确保您的范围的 那里，你想他们。
因此，即使是晚了，你还是会 获得信贷的范围点，我想。
>> 因此，道德的故事，使 确保你的pset是导通时间。
并且如果它们不是在导通时间， 知道这是不是很大。
是啊，在我继续前进，没有任何人有 有关PSET反馈有任何疑问？
是啊。
>> 听众：你是说，我​​们 可以去掉的pset之一？
>> ANDI彭：是的。
因此，有九pset中整体 在这学期的课程。
如果你有范围 points--因此范围是正义的，
相当多，你尝试了 问题是，你投入的时间，
你表明你已经 表明您已经阅读了规范。
这是相当多的范围。
如果你正在履行 范围点，我们
可以降最低 一出的全部范围。
所以这是你的优势， 完成并想尽一切PSET。
>> 即使upload--如果没有 他们的工作，快点上传所有。
然后我们就希望能够 给你一些这些点回来。
酷。
其他问题吗？
太好了。
>> 其次，办公hours--数 有关办公时间快速笔记。
因此，首先，走在了本周初。
没有人是曾经在 办公时间周一休息。
Christabel来到 昨晚办公时间。
是啊，Christabel。
和我们有在办公室什么 小时昨晚，Christabel？
>> 听众：我们有冰淇淋。
>> ANDI彭：所以这是正确的，我们有 冰淇淋办公时间昨晚。
虽然我不能答应你， 我们将有冰淇淋办公时间
每个星期，我可以向你保证 的是，将有显著
更好的学生到TA的比例。
像合法的，它像三一。
然而，对比，与 周四，你已经得到了约150
真正强调的孩子和没有冰淇淋。
而且它只是没有生产任何人。
所以这个故事的寓意是，来得早 在办公时间，办好事
会发生。
>> 此外，有备而来提问。
你懂的？
不管什么助教，我 想，一直在说，
我们已经获得一对学生情侣 谁在周四进来的一样，10:50
不看了规范 是一样帮助我，帮助我。
不幸的是，在这一点上，还有 没有多少，我们可以做些什么来帮助你。
所以，请进来本周初。
来得早在办公时间。
有备而来的提问。
请确保您作为 一个学生，都在那里
你必须使得 助教可以引导你前进，
这正是办公时间 应分配的。
>> 其次，所以我知道教授 喜欢我们测试的惊喜。
我有一个教授的 像哟，顺便说一下，
请记住，中期 你下周一。
是啊，我不知道是中期。
所以我将是那个TA 提醒大家，测验
0--因为，你知道，我们是CS。
现在，我们已经做了数组，你会得到 为什么它的测验0，没有测验1，是吗？
好。
呵呵，我得到了一个有些笑。
好。
>> 因此，测验0将是10月14日，如果 你在周一至周三节
而10月15日，如果你在 周二至周四部分。
这不适用于 那些你在哈佛
who--我想你会都是 以14号的测验。
>> 所以呀，在下周，如果 大卫在演讲中，云，
是啊，所以有关 竞猜下周，大家
将不会因为震惊 您来第
你知道你的 测验0是在两个星期。
而且我们必须检讨 会议和一切。
所以不愁 被吓到了点。
如有任何疑问before--任何疑问 在所有有关的后勤问题，
分级，办公时间，部分？
是啊。
>> 听众：所以小测验 将要演讲期间？
>> ANDI彭：是的。
所以测验，我想，是60 分配在时隙分钟
你会只拿 在报告厅。
所以，你不必进来 上一样，随机下午7:00。
都很好。
是啊。
酷。
>> 好吧。
所以，我们要 介绍一个概念，你
本周大卫早已种 这个过去一周触及的讲座。
这就是所谓的GDB。
你们有多少人而且，当 写你的pset的过程中，
已经注意到一个很大的按钮，上面写着 在您的IDE顶部的“调试”？
好。
所以，现在，我们将真正得到挖掘 其实什么按钮的奥秘
确实。
我向你保证，这是一个 美丽的，美丽的东西。
>> 所以到现在为止，我觉得 还有的是两件事情
学生已通常 调试的pset在做。
一，他们要么加入 printf（）的 - 所以每几行字，
他们加入一个printf（） - 哦，这是什么变量？
哦，这是什么变量now-- 样的，你会看到进展
你的代码，因为它运行。
或者第二种方法孩子们做的是 他们只写了整个事情
然后转到这样在末端。
希望它的工作原理。
我向你保证，GDB更好 比两者的那些方法。
是啊。
因此，这将是你最好的朋友。
因为它是一个美丽的东西 在视觉上同时显示
你的代码做 在特定点
以及所有的你的 变量都在进行，
喜欢什么他们的价值观， 在该特定的点。
而这样一来，你才能真正 设置在代码中的断点。
您可以通过一行一行地运行。
和GDB只会有 您，向您显示，
什么你所有的变量 是，他们在做什么，
这是怎么回事代码。
并且在这样的方式，它的 所以更容易看到
发生了什么的printf的-ING代替 或写下你的陈述。
>> 所以我们会做后面的一个例子。
因此，这似乎有点抽象。
不用担心，我们会做的例子。
所以本质上，三个最大的， 最常用的功能，你需要在GDB
是接下来，步过， 而步入按钮。
我将头以上 在那里，其实，就是现在。
>> 所以你们可以都看到， 或者我应该放大一点？
在后面，你能看到吗？
我应该放大？
只是一点点？
嗯不错。
在那里，我们走了。
好。
>> 所以我在这里，我 实现贪婪。
虽然很多你们的写 贪婪form--，虽然环
是一种完全可以接受的方式做 它 - 另一种方式来做到这一点是根​​本
在分模。
因为那样的话，你可以有你 值，然后让你的其余部分。
然后你可以只 加上它一起。
请问对我在做什么逻辑 这里是有意义的每一个人，
之前我们开始？
有点？
酷。
太好了。
这是一个非常性感的一块 的代码，我会说。
就像我说的，大卫，在 讲课，过了一段时间，
你们都开始看到的代码 作为东西是美丽的。
有时，当你看到漂亮 代码，它是这样一个美妙的感觉。
>> 因此然而，尽管这个代码是非常 美丽的，它不能正常工作。
因此，让我们在这个运行check50。
检查50 20--空中接力。
2？
那是pset2？
是啊。
哦，PSET1。
好。
所以我们运行check50。
>> 正如你们所看到的， 它的失败一对夫妇的案件。
而对于一些你，在 做你的问题集的过程中，
你喜欢啊，为什么不工作。
为什么工作一段 值，而不是为别人？
那么，GDB是要帮助你的身影 为什么这些投入并没有工作。
>> 好。
所以，让我们来看看，之一 检查我是失败的check50
为0.41的输入值。
所以正确答案 你应该得到一个4。
而是我所打印出 是3-n中，这是不正确。
因此，让我们只是手动运行它，只是 确保check50正常工作。
让我们做./greedy。
哎呀，我一定要贪婪。
在那里，我们走了。
现在./greedy。
>> 多少钱是欠？
让我们做0.41。
而且是的，我们在这里看到 ，它的输出3
当正确的答案， 事实上，应为4。
因此，让我们进入GDB，看看我们如何 可以去解决这个问题。
>> 因此在第一步骤中 一直调试代码
是设置一个断点， 或在这一点，你
希望计算机或 调试器开始寻找。
所以，如果你真的不 知道你的问题是什么，
通常情况下，一般的事情，我们要 做的是设置了断点为主。
所以，如果你们可以看到这 红色按钮就在那里，
是的，这是我的设置 断点的主要功能。
我点击了。
>> 然后我就可以去了我的Debug按钮。
我打那个按钮。
让我放大了，如果我能。
在那里，我们走了。
因此，我们有，在这里，在面板上的权利。
我很抱歉，伙计们在后面，你 实在看不出真的很好。
但本质上，所有的 该右侧面板做
被跟踪的两个突出 线，这是代码行
计算机正在运行， 以及所有的变量
到这里。
>> 所以，你有美分，硬币，N， 所有申报不同的东西
在此刻。
不用担心，因为我们没有真正 它们初始化的变量呢。
因此，在你的电脑，你 电脑只是看到，
哦，32767是最后使用的功能 在我的电脑的内存空间。
所以这就是美分是目前。
但是，没有，一旦运行该代码， 它应该成为初始化。
>> 因此，让我们通过，一行 行，这是怎么回事的。
好。
所以，在这里是三个 按钮，我刚才解释。
你有玩，或者运行功能， 按钮，你有步骤结束按钮，
你也有步骤为按钮。
并且基本上，所有三个 他们只是通过你的代码
而做不同的事情。
>> 所以通常情况下，当你正在调试， 我们不希望只是打游戏，
因为比赛将只运行 你的代码，它的结束。
然后，你不会真的 知道你的问题
除非你设置多个断点。
如果设置了多个断点， 它只是自动
从一个断点运行， 到下一个，到下一个。
但是，在这种情况下，我们已经 只是那一个，因为我们
希望我们的工作方式 从顶部向下至底部。
所以，我们要忽略按钮 现在为了这个计划。
>> 因此，在步函数只是 在每一行的步骤
并告诉您 计算机在做什么。
该步骤为函数去 到实际的功能
这是对你的代码行。
因此，例如，如printf（）， 这是一个函数，对不对？
如果我想在物理上一步 到printf（）函数，
我真的进入片 其中，printf（）的写，看看代码
这是怎么回事那里。
>> 但通常，我们假设 我们为您提供的代码工作。
我们假设printf（）的正常工作。
我们假设调用getInt（）的工作。
因此，有没有必要 走进这些功能。
但是，如果有功能 你写你自己
要检查 发生了什么事情，
你会想一步 入该功能。
>> 所以现在我们只是 跨过这段代码。
所以，让我们来看看。
哦，打印，“哦，海，怎么样 多大的改变是欠？“
我们不关心。
我们知道的工作， 所以我们跳过它。
>> 因此n，这是我们的浮动是 我们已经initialized--或declared--
在顶部，我们现在是 等于说，以GetFloat（）。
因此，让我们跨过这道。
而我们在看 底部这里，程序
这促使我输入一个值。
因此，让我们输入我们想要的值 在这里测试，这是0.41。
太好了。
>> 所以，现在N--做你们看 这里，在bottom--它的
stored--因为我们 还没有四舍五入的是，它
存储在这个像巨大 浮动是0.4099999996，
这是足够接近我们的 目的，现在，到0.41。
然后，我们将在后面看到，因为我们 继续加强在该程序，
后这里，正变得 圆润和分成为41。
太好了。
因此，我们知道，我们的舍入的工作。
我们知道，我们有 正确的数量美分，
所以我们知道，这是 没有真正的问题。
>> 因此，我们将继续加强 在此计划。
我们去这里。
而这行代码之后的话，我们 要知道我们有多少个季度有。
我们跳过。
而且你看我们做什么，其实，有一个 季度，因为我们已经减去25
从41我们的初始值。
我们有16个左右为我们美分。
>> 大家是否明白如何 该程序是通过步进
为什么美分现已成为16 为什么，现在，硬币已经成为1？
是每个人以下的逻辑是什么？
酷。
因此，作为这一点的，在 计划的工作，对不对？
我们知道这是做完全 我们希望它。
而我们实际上并没有 要打印出来，哦，
是仙在这一点上， 什么是硬币在此点。
>> 我们将继续经历的程序。
跨越。
酷。
我们去了助攻。
太好了。
我们看到，它采取 关闭$ 0.10一角钱。
而现在我们有两个硬币。
这是正确的。
>> 我们去了几个便士而我们看到的 我们已经得到了遗留美分。
嗯，这很奇怪。
在这里，在该程序中，我应该 已减去我便士。
也许我只是没有 这样做行权。
唉，你可以看到 在这里，因为我们知道
我们正在加紧 通过线32和33，
这就是我们的计划 不当有变量运行。
因此，我们可以看看，看看，哦， 我在这里减去美分，
但我没有实际 添加到我的币值。
我加入到美分。
我不希望添加到 分钱，我要添加到硬币。
因此，如果我们改变，要硬币， 我们已经有了一个工作程序。
我可以运行check50。
你可以只退出的GDB右出 这里，然后再次运行check50。
我可以做到这一点。
我一定要贪婪。
0.41。
而在这里，它的印刷 出正确的答案。
>> 所以当你们可以看到，GDB 是一个非常强大的工具
当我们有这么多的代码 怎么回事，这么多的变数
它很难对我们来说，作为 一个人，来跟踪。
计算机，在GDB 调试器，有能力
多事的。
我知道，在VISIONAIRE，你们可能 可能击中了一些段故障
因为你正在运行 从你的阵列的界限。
在凯撒的例子，这是 正是我在这里实现。
>> 所以，我忘了检查 如果会发生什么，我
没有两个命令行参数。
我只是没有摆在那检查。
所以，如果我跑Debug--我设置 我的断点就在这里。
我运行调试。
>> 好。
是啊。
所以实际上，GDB应该 已经告诉我，
是分割故障出现。
我不知道发生了什么事情 在那里，但是当我运行它，
这是工作。
当您运行通过行代码 GDB可能只是突然退出你，
上去看看红色的错误是什么。
它会告诉你的，嘿嘿，你 有段错误，
这意味着您尝试访问 以阵列的空间不存在的。
是啊。
>> 因此，在接下来的问题 本周集，你们
可能有很多 变量左右浮动。
你不会是知道 它们都是指在某一点。
因此，广发行将真正帮助你在盘算 它们是什么都等于
并能够看到直观。
有没有人困惑于如何 任何被工作？
酷。
好吧。
所以在这之后，我们 去潜水权
成四种不同的 排序类型本周。
你们有多少人，第一次 所有的人，在我们开始之前，
读完整个规范的pset3？
好。
我是你们的骄傲。
这就像半个班，这 是显著超过上一次。
>> 所以，这是伟大的，因为当 我们谈论的内容
在lecture--还是遗憾， 在section--我喜欢
以涉及了很多的 回PSET是什么
你想如何 实现在你的pset中。
所以，如果你来有 读取规格，它会
是一个更容易让你明白 我说的是，当我说，
嘿，这可能是一个真正的 实现这种好地方。
所以，你们谁读了 SPEC知道，作为你的PSET的一部分，
你将不得不 写一个排序的类型。
所以，这可能是非常有帮助 今天很多你。
>> 因此，我们将刚开始时， 本质上，最简单类型
排序，选择排序。
典型的算法 我们怎么会去这
is--大卫通过这些全都走了进去 讲座，所以我会很快待着
这里 - 本质上，你 有值的数组。
然后你找到 最小的未分类的价值
和你交换与价值 第一个未排序的值。
然后你只是不断重复 以列表的其余部分。
>> 而且这里有一个直观的解释 如何将工作。
因此，例如，如果我们开始 与五个元件的阵列，索引
0至4，用3,5，2,6，和4个值 所以，现在摆在array--，
我们只是假设 他们都是未分类
因为我们还没有测试过，否则。
>> 因此，如何选择排序会 工作是，那就先
通过整体运行 未排序的数组。
这将挑选出的最小值。
在这种情况下，如图3所示，右 现在，是最小的。
它得到5。
不，5不大于than-- 或不好意思，不低于than-- 3。
所以最小值仍然3。
然后你到2。
电脑看，哦，2小于3。
2现在必须的最小值。
所以2掉期与第一个值。
>> 因此，人们通过后，我们确实看到 该2和3被交换。
而我们只是要继续做 这再次与阵列的其余部分。
因此，我们将只运行通过 最后四个指标的数组。
我们会看到，3 下一最小值。
所以，我们要交换与4。
然后，我们只是要继续 贯穿直到最后，你
得到一个排序的数组中 2，3，4，5，和6被所有排序。
大家是否明白逻辑 如何选择排序工作？
>> 你只要有某种 的最小值。
你跟踪的那是什么。
每当你找到它，你将其交换 与在array--第一值
或者，不是第一value-- 阵列中的下一个值。
酷。
>> 所以当你们那种 从短暂的一瞥看到，
我们要伪代码这一点。
所以，如果你们在后面要 组成一个小组，每个人都在一张桌子
可以形成一个小伙伴，我要去 给你们喜欢3分钟
刚才讲通过 逻辑，英语，
对我们如何能够实现 伪代码写一个选择排序。
还有的糖果。
请上来，并得到糖果。
如果你在后面，你想 糖果，我会向你扔糖果。
其实，做你 - 爽。
噢对不起。
好。
>> 所以，如果我们想，作为 一类，写伪代码
如何人们可能接近 这个问题，只是觉得自由。
我就到处去和， 为了，问群体
对于下一行 我们应该做的。
所以，如果你们想开始 关，什么是第一件事情
当你试图做 实现的方式来解决这个方案
有选择地排序列表？
让我们只是假设我们 有一个数组，没事吧？
>> 听众：你想创造一些 排序[听不清]你是
通过你的整个阵列的运行。
>> ANDI彭：对。
所以，你会想迭代 通过每一个空间，对不对？
很好。
如果你们想给我 接下来line--是啊，在后面。
>> 听众：检查他们 全部为最小。
>> ANDI彭：我们去那里。
因此，我们希望通过和检查 看到最小值是什么，对不对？
我要缩写，为“最小”。
你们有什么想后做 你已经找到了最小值？
>> 听众：[听不清]
ANDI彭：所以你会想 与第一个数组中打开它，
对？
这是开始的时候，我会说。
好吧。
所以，现在你已经换第一 一，什么你想以后做什么？
所以，现在我们知道，这一个在这里 必须是最小的值，对不对？
然后，你有一个额外的休息 该阵列是无序的。
所以，你想在这里做的，如果你有什么 人想给我的下一行？
听众：那么接下来你要遍历 通过该阵列的剩余部分。
ANDI彭：是的。
还等什么，通过它遍历 那种暗示我们可能会需要什么？
什么类型的of--
>> 听众：哦，一个额外的变量？
ANDI彭：可能 另一个循环，对不对？
因此，我们可能会想 迭代through--很大。
然后，你要回去 可能再次检查最低，
对？
而你要不断重复 这一点，因为环正要
继续运行，对吧？
>> 所以当你们可以看到，我们 只是有一个大致的伪代码
我们如何希望这个节目的样子。
这里这个迭代，我们怎么 通常需要在我们的代码编写
如果我们要遍历一个 阵列，什么类型的结构？
我想Christabel 之前已经说过这一点。
>> 听众：for循环。
>> ANDI彭：一种循环？
没错。
因此，这可能是 将是一个for循环。
什么是这里的检查会意味着什么呢？
通常情况下，如果你想查询 如果有什么东西else--
>> 听众：如果。
>> ANDI彭：如果一个，对不对？
然后在这里交换，我们将 去了以后，因为大卫·
通过讲座去为好。
然后第二个迭代implies--
>> 听众：另一个循环。
>> ANDI彭：--another for循环，没错。
因此，如果我们正在寻找 在这个正确的，我们
可以看到，我们可能 将需要一个嵌套的循环
在有一个条件语句 然后代码的一个实际的一块是
要交换值。
所以，我只是一般写 这里一个伪代码。
然后，我们实际上会 到身体上，作为一类，
试试这个今天实现。
让我们回到这个IDE。
>> 嗯，哦。
这是为什么不是 - 它就在那里。
好。
对不起，让我尽量放大一点。
在那里，我们走了。
我做的是在这里我创建 一个名为“选择/ sort.c。”
我创建了九个数组 值，4，8 2，1，6,9，7,5，3。
目前，你可以 看，他们是无序的。
n为将成为数 告诉你值量
你在你的阵列。
在这种情况下，我们有九个值。
我刚刚得到了一个for循环在这里 打印出的排序的数组。
>> 而在最后，我也得到了一个为 循环，只是打印出来了。
因此从理论上说，如果此程序 工作正常，到了最后，
你应该看到一个打印的循环 其中，1，2，3，4，5，6，7，8，
9都是正确的顺序。
>> 所以，我们在这里得到了我们的伪代码。
有谁想用于：我只是 要去问volunteers--
确切地告诉我，如果什么类型 我们希望，第一，只是想迭代
通过这个数组的开始？
什么是代码行我 可能要在这里需要什么？
>> 听众：[听不清]
>> ANDI彭：是啊，感觉 免费用于：对不起，你
不必忍受up--手感 自由地提高你的声音有点。
>> 顾客：INT I等于0--
>> ANDI彭：是的，不错。
>> 观众：我是小于数组的长度。
>> ANDI彭：因此，保持在 介意在这里，因为我们
不具有功能 告诉我们的阵列的长度，
我们已经有一个 值，其存储。
对？
另一件让 在mind--以阵列
九价值观，有什么指标？
远的不说这个数组是0至3。
你看，最后 指数实际上是3。
这不是4，即使有 阵列中的四个值。
>> 所以在这里，我们必须非常小心， 什么我们条件的长度
将是。
>> 听众：那岂不是为n减去1？
ANDI彭：这是怎么回事 Ñ​​减去1，正好。
这是否有意义，为什么 它n值减1，每个人？
这是因为数组是零索引。
他们从0开始并运行最多n个减1。
是的，这是一个有点棘手。
好。
接着 -
听众：Isnt'1那 已经采取的虽然照顾，
通过刚才不是说“小于或 等于“，只是说：”不到？“
>> ANDI彭：这是一个 非常好的问题。
所以，是的。
而且，我们的方式是说 实施检查权，
你需要比较两个值。
所以，你真的想 离开“到”空。
因为如果你比较 这一次，你不会
有后什么 要比较的，对不对？
是啊。
所以我++。
让我们添加括号研究。
哎呦。
太好了。
因此，我们有初 我们的外环。
所以，现在我们可能要 建立保持一个变量
轨道的最小值，对不对？
没有人想给我 行代码，将做到这一点？
我们需要什么，如果我们打算 想储存什么？
>> 对。
对于也许一个更好的名字 将be--“临时”完全works--
也许更恰当地命名会是这样， 如果我们希望最小value--
>> 听众：最小。
ANDI彭：分钟，我们走吧。
分将是一件好事。
所以在这里，我们怎么 要初始化为？
这是一个有点棘手。
因为现在在 开始本阵，
你有没有看什么，对不对？
还等什么，自动，如果 我们只是i等于0，
我们怎么想初始化 我们的第一个最小值？
观众：我。
ANDI彭：我，没错。
Christabel，那我们为什么还要 它初始化到我？
>> 听众：因为， 我们从0开始。
所以，因为我们没有什么可比较 它，最小最终会被0。
>> ANDI鹏：没错。
所以她完全正确。
因为我们还没有真正 看着任何东西，
我们不知道我们的最低值。
我们希望只是将其初始化为 我，这，目前，就在这里。
而且，我们将继续 向下移动，这阵，
我们将看到，每个 额外的传球，我递增。
因此，在这一点上， 我很可能会
想为最小， 因为这将是什么
是未排序数组的开始。
酷。
>> 所以，现在我们要添加 一个for循环，这里的
要遍历 未分类，或该阵列的其余部分。
没有人想给我一个 行代码，将做到这一点？
Hint--我们需要什么到这里？
这是怎么回事往这个循环？
是啊。
听众：所以我们会想 有一个不同的整数，
因为我们通过休息运行 数组，而不是我，所以也许对
学家
>> ANDI彭：是啊，J听起来不错。
等于？
>> 听众：那将是我加1，因为 你开始的下一个值。
然后到end--如此反复，j为 小于n减去1，然后J ++以下。
ANDI彭：太好了。
>> 然后在这里，我们将要 检查，看看是否符合我们的条件，
对？
因为你想 改变的最小值
如果它实际上是小于什么 你对比的话，对不对？
那么，我们将要在这里？
请检查。
声明什么类型 我们有可能将
TI想，如果用我们 要检查些什么呢？
>> 听众：if语句。
>> ANDI彭：if语句。
所以if--，什么将是 我们希望里面的状况
我们的if语句？
>> 听众：如果j值 小于I--值
>> ANDI鹏：没错。
所以if--所以这个数组被称为“数组”。
太好了。
因此，如果array--那是什么？
再说一次。
>> 听众：如果array-j是小于 数组我的话，就要改变最小。
所以分钟就学家
>> ANDI彭：这是否有意义吗？
好。
而现在到这里，我们其实 要实现交换，对不对？
所以记得，在演讲中，大卫，当 他是想换the--是什么
它 - 橙汁和milk--
>> 听众：这是毛。
>> ANDI彭：是啊，这是种毛。
但它是一个相当不错的 概念展示时间。
因此，认为你的价值在这里。
你有一个数组 的分，i的阵列，
或不管我们想在这里交换。
而且你可能无法将其倒入 对方在同一时间，对吧？
那么究竟是为了什么 需要创建在这里
为了正确交换价值？
>> 听众：一个临时变量。
>> ANDI彭：一个临时变量。
因此，让我们做INT温度。
你看，这将是一个更好的 时间用于：哇，那是什么？
好。
因此，这将是一个更好的 时间命名变量“温度”。
因此，让我们做INT温度。
什么是我们要 SET TEMP等于在这里？
听众：最小？
ANDI彭：这是一个有点棘手。
它实际上无所谓到底。
它什么都无所谓 为了您选择交换
只要你确保你 跟踪你交换什么。
>> 听众：这可能是数组我。
>> ANDI彭：是的，让我们做阵列我。
然后什么是下一行 的代码，我们要在这里？
听众：阵列-i等于阵列-J。
ANDI彭：最后一点？
听众：阵列-J等于阵列我。
听众：或数组，j为 阵列temp--或温度。
>> ANDI彭：OK。
因此，让我们运行这个，看看 如果它去上班。
哪里是怎么回事？
哦，这是一个问题。
见，第40行，我们 尝试使用数组-J？
但是，在没有Ĵ只存在吗？
>> 听众：在for循环。
ANDI彭：对。
那么，我们将需要做什么？
>> 听众：外the--将其定义
听众：是的，我想你 if语句，使用权的另一个？
所以像，如果minimum-- 好吧，让我想想。
>> ANDI彭：伙计们，试试 看看咱们的
看看，什么的东西，我们可以在这里做什么？
>> 听众：OK。
因此，如果最低不等于 j--所以如果最小仍然I--
那么我们就不会掉。
>> ANDI彭：这是否等于我？
你怎么在这里想说的？
>> 听众：或者是啊，如果 最低不等于我，是的。
ANDI彭：OK。
好了，解决了，那种，我们的问题。
但是，这仍然没有解决 如果j--发生，因为Ĵ哪些问题
外面它不存在，什么 你，我们想用它做？
外部声明呢？
让我们尝试运行此。
嗯，哦。
我们的排序不工作。
>> 正如你所看到的，我们最初的 数组有这些值。
事后它应该有 一直在1，2，3，4，5，6，7，8，9。
它不工作。
啊。
我们做什么？
听众：调试。
ANDI鹏：好的，我们可以试试。
我们可以调试。
缩小了一点。
让我们设置的断点。
让我们去like--确定。
>> 所以，因为我们已经知道， 这些线路，15至22，
在working--因为我做的是 通过与printing--只是迭代
我可以继续跳过。
让我们从第25行。
空中接力，让我摆脱这一点。
>> 听众：所以断点的 其中，调试开始？
ANDI彭：或停止。
听众：或停止。
ANDI彭：是的。
您可以设置多个断点和 它可以只从一个到另一个跳。
但是，在这种情况下，我们不知道 那里的错误发生。
所以，我们只是想 从上向下展开。
是的。
好。
>> 因此，这条线在这里，我们可以介入。
你可以看到这儿， 我们已经有了一个数组。
这些都是价值 是阵列中。
你看到了，怎么指数为0， 对应于value--哦，
我要去尝试进行放大。
对不起，这真的很难 以see--数组索引0，
我们有4的值， 然后依此类推等等。
我们有自己的局部变量。
现在我等于 0，这是我们希望它是。
>> 因此，让我们继续单步调试。
我们的最低等于0， 我们也希望它是。
然后，我们进入我们的第二个用于 环，如果阵列-j是小于阵列-i的，
它不是。
所以，你怎么看 即跳过了吗？
>> 听众：所以要把如果 最低，所有that--不应该的
在里面的第一个for循环？
ANDI彭：没有，因为 你还是想测试。
你想要做一个比较每 时间，即使你通过它运行。
你不只是想这样做 在第一通过。
你想做到这一点的 再每增加一个通行证。
所以，你要检查 你的病情里面。
所以，我们只是要 让经过这里运行。
我给你们一个提示。
它必须做的事实是，当 你检查你的条件，
你不检查 正确的索引。
所以现在你检查 歼数组索引小于阵列
我索引。
但是，你在做什么了，在 for循环的开始？
难道你不设置Ĵ等于我？
>> 是啊，所以我们实际上可以 退出调试器在这里。
因此，让我们来看看我们的伪代码。
For--我们要 开始我等于0。
我们要上浮到n减去1。
让我们来看看，没我们有这个权利？
是的，这是正确的。
>> 因此，然后在里面在这里，我们 要创建一个最小值
并设置等于i。
难道我们这样做吗？
是的，这样做。
现在，在我们内心的for循环中，我们 要做到j为我到n减去1。
难道我们这样做吗？
事实上，我们做到了。
>> 所以，不管，什么是我们比较吗？
>> 听众：J-加1。
ANDI鹏：没错。
然后你会想设置 您的最低等于到j加1为好。
所以，我通过真的很快去了。
难道你们明白 为什么它的歼加1？
好。
>> 因此，在你的阵列，在 你的第一个闯关，
你的for循环，对于int i等于0，我们只
假设这并没有改变呢。
我们的阵列，完全， 短短四年未排序的元素，对不对？
因此，我们要初始化i等于0。
而我是要只 通过这个循环运行。
因此在第一轮，我们要 初始化一个名为“分”变
这也等于我，因为 我们没有一个最小值。
所以这是当前等于0为好。
然后，我们将经历。
我们想再次重复。
现在我们已经找到了我们的最低 是，我们要遍历
再看看它的比较，对不对？
所以Ĵ，在这里，是怎么回事 等于I，这是0。
然后，如果阵列Ĵ再加上我，这 就是一个是下完了，一样都不能少
比你目前的最低 值，要交换。
>> 所以，让我们只说我们已经 有，像，2，5，1，8。
现在，我等于 0和j是等于0。
这就是我们的最低值。
如果阵列-j的加I--因此如果所述一个 这就是我们正在寻找在一前一后
大于前一， 这将成为最低。
>> 所以在这里我们可以看到，5 是不逊色。
因此，这将不会是5。
我们看到，1小于2，对不对？
所以，现在我们知道，我们的最低是 将是0，1，2的指数值。
是吗？
然后当你到这里， 你可以交换正确的价值观。
>> 所以，当你们刚刚有第j 之前，你是不是在看一
后。
你在看 相同的值，这
就是为什么它只是没有做任何事情。
这是否有意义给大家， 为什么我们需要一个加1呢？
好。
现在，让我们只运行通过它来作 确认代码的其余部分是正确的。
这是为什么发生？
啊，这是分就在这里。
我们比较了错误的值。
不好了。
>> 哦，是的，在这儿我们 交换了错误的值也是如此。
因为我们在看i和j。
这些都是那些我们被检查。
事实上，我们希望交换的 至少，目前最低，
与任何一个外面。
正如你们所看到下跌 在这里，我们有一个排序的数组。
这只是不得不做 事实，当
我们被检查 值的我们相比，
我们不看正确的价值观。
我们在看的同一个 在这里，没有实际交换它。
你要看看一个接一个 它，然后你可以交换。
所以，这是什么样的 前缠着我们的代码。
而我在这里所做的一切 调试器可以为你做
我只是做了它的 板，因为它更容易
看而不是试图 可放大的调试器。
这是否有意义给大家？
酷。
>> 好吧。
我们可以继续谈 渐近符号，这
是说的只是一种奇特的方式 所有这些各种各样的运行时间。
所以我知道大卫在演讲中， 在运行时感动。
他走遍了整个公式 如何计算的运行时。
关于无后顾之忧。
如果你真的很好奇 其工作原理，
随时节后跟我说话。
我们可以穿行 公式在一起。
但是，所有你们要真 知道是n的平方超过2
是同样的事情为N的平方。
因为最大数目， 该指数增长最。
所以我们的目的， 我们关心的
是巨大的数量也在不断增长。
>> 那么，什么是最好的情况下， 选择排序的运行时间？
如果你想有 遍历列表
然后遍历 该列表的其余部分，
多少次都 你要大概，
在最坏的case--在 最好的情况下，sorry--跑过来吗？
也许更好的问题是 要问，什么是最坏的情况下
运行时选择排序的。
听众：N的平方。
ANDI彭：这n值的平方，正确的。
因此，一个简单的方法来认为这是喜欢， 任何时候你有两个嵌套的for循环，
它会为n的平方。
因为不仅是你 通过再次运行，
你要回去 周围，​​并通过它运行
里面的每一个值一次。
因此，在这种情况下，你在行驶中N n次平方，这is--抱歉，
n次N，这等于N的平方。
>> 和排序也有点 在这个意义上独特
它不如果这些关系 值已经在秩序。
它仍然会通过反正运行。
远的不说，这是1，2，3，4。
不管它是否是在 命令，它仍然会通过跑
并且仍然检查的最小值。
它会作出 检查相同数量的
每一次，即使它 实际上并没有碰任何东西。
>> 因此，在这样的情况下，最好和最差 运行时实际上是等价的。
因此，预计运行时间 选择排序的，
这是我们指定的符号 的θ，θ-，在这种情况下，
还将为n的平方。
所有这三个为N的平方。
是为什么每个人都清楚 运行时间为n的平方？
>> 好吧。
所以我只是要快速运行 通过对各种休息。
该算法 泡泡类别 - 记住，
这是第一个 大卫走过去的讲座。
从本质上讲，你一步 整个列表
你刚才swap--你 同时比较两个。
而如果一个人的更大， 比你只是换他们。
因此，如果这些是更大的，你就掉。
我已经得到了官方的就在这里。
>> 因此，让我们只说你有8个，6个，4个，2。
你会比较8和6。
你需要交换它们。
您会比较8和4。
你需要交换它们。
如果您有交换8 2，改变他们。
因此，在这样的意义上，你可以看到， 发挥出了相当长的时间周期，
怎么样值泡沫来 两端，这就是为什么我们叫它
冒泡排序。
>> 我们只想上运行再次通过 我们的二传，而我们的第三关，
而我们的第四个阶段。
从本质上讲，冒泡排序只是运行 直到你不作任何更多的互换。
因此，在这个意义上，这仅仅是 一般伪它。
不用担心，这些都将在网上。
我们没有真正去了这一点。
>> 我们只是初始化一个计数器 从0开始的变量。
而我们通过整个数组迭代。
如果一个值is--如果这 值大于该值，
你要交换它们。
然后，你只是 要继续下去。
而你要算。
而你只是要继续做 这同时计数器的值大
大于0，这意味着 每次你要交换，
你知道你想要去 回去检查一次。
你要继续检查，直到你知道 你不必换了。
>> 那么，什么是最好的和最差 情况下的运行时间冒泡排序？
这hint--实际上是不同的 从某种意义上选择排序
这两个答案是不一样的。
想想会发生什么 的情况下，如果它已经被排序。
想想什么 如果它是会发生
在的情况下在它被排序。
你可以种运行 通过为什么会发生的事情。
我给你们一样，30 秒，想想。
>> 好。
是否有人在猜测什么 冒泡排序的最坏情况下的运行时间是？
是啊。
>> 听众：会是一样，n次 ñ减1或类似的东西？
像，每次运行时， 它只是一样，一个交换少
这不管是什么。
>> ANDI彭：是啊，所以 你是完全正确的。
这是在这种情况下你 答案竟是更复杂
比我们需要给。
因此，这将run--我 要删除这一切都在这里。
是每个人都好？
我能抹去吗？
好。
你会到n运行 第一次时间，对吧？
他们正在经历的运行 Ñ​​减去1秒的时间，对吧？
然后，你要保持 去，N矿2，等等。
大卫这样做的讲座，其中， 如果你加起来所有的值，
你得到的东西，是like-- yeah-- 超过2，这本质上只是减少
下降到n的平方。
你会得到一个 怪异的部分在里面。
所以只要知道 第n总是平方
优先于分数。
因此在这种情况下，最坏的 运行时间为N的平方。
如果它是在降 顺序，想想，你
不得不做出交换每一次。
>> 什么是潜在的， 最好的情况下运行？
这么说吧，如果列表已经 为了，你会在运行时？
>> 听众：N。
ANDI彭：这是N，正好。
为什么是这N +
听众：因为你刚才 必须检查每一次。
ANDI鹏：没错。
因此，在可能的最佳运行时， 如果此列表中已经
sorted--比方说，1，2，3，4--您 只想去实现它，你会检查，
你会看到，哦，他们都做成。
我没得换。
我受够了。
因此，在这种情况下，它仅仅局限于N 或步数，你只是
不得不检查的第一个列表。
>> 及后，我们现在打 插入排序，其中，
该算法本质上是鸿沟 它变成一个排序和未排序的部分。
然后一个接一个， 未排序值
在其相应插 在列表的开头位置。
>> 因此，例如，我们有一个 的3名单，5,2，6,4试。
我们知道，这是目前 未分类的，因为我们刚刚
开始寻找它。
我们来看看，我们知道， 第一个值进行排序，对吧？
如果你只关注一个数组 尺寸之一，你知道它的排序。
>> 于是我们知道， 其他四个都是无序。
我们通过和我们看到的价值。
我们回去吧。
见5的价值？
我们来看看它。
我们把它比作3。
我们知道，它是大于 3，让我们知道，多数民​​众赞成排序。
所以，现在我们知道，前两个 进行排序和最后三个不是。
>> 我们来看看2。
我们首先检查一下与5。
是小于5？
它不是。
因此，我们必须继续找下去。
然后检查2关闭3。
是小于？
第
所以，你知道2必须插入 入前和3和5
都必须被推出。
6和4再次做到这一点。
我们只是保持检查从本质上讲， 在这里我们只是检查，检查，检查。
而直到它在正确的 样的位置，我们只是
将其插入合适的位置， 这就是它的名字是从哪里来的。
>> 所以，这仅仅是算法， 那种伪代码本身，
关于我们如何实现 插入排序。
伪代码是在这里。
这一切都在网上。
不，如果你们有隐忧 试图复制下来。
所以再次，相同的问题 - 是什么 将是最好的和最差的运行时间
插入排序？
这是非常相似的最后一个问题。
我给你们一样，30 秒想想这一点。
>> 确定有没有人要 给我最糟糕的运行？
是啊。
>> 听众：N的平方。
>> ANDI彭：这n值的平方。
为什么它Ñ平方？
>> 听众：因为在 相反的顺序，你有
要经过n次N，其中is--
ANDI彭：是的，没错。
所以，同样的事情在冒泡排序。
如果此列表中 降序排列，你
不得不先检查一次。
然后每 额外的价值，你
将不得不对检查 每一个值，对不对？
所以干脆，你会做 正通时代另外N通，这
为n的平方。
那么最好的情况？
是啊。
>> 听众：N减1，因为 第一个是已经平方。
>> ANDI彭：那么，关闭。
其实答案ñ。
因为当第一个是 排序，也可以不actually--它
我们只是走运了，在 即例如，2
正好是最小的数目。
但是，这不会总是这种情况。
如果2已经排序的开始 但是你看，有一个1在这里，
1将要碰撞。
而这将结束 最多被撞毁反正。
>> 因此，在最好的情况下， 它实际上只是要为n。
如果有1个，2个，3个， 4，5，6，7，8，你
经过运行 这整个列表一次
检查，如果一切都很好看。
在其上运行大家清楚 选择的时候呢？
我知道我经历 这些真快。
但是，仅仅知道，如果你知道 一般概念，您应该不错。
好。
所以，我只是给你们也许一样， 一分钟谈谈你的邻居
什么都只是一些 的主要区别
与这些类型的排序。
我们一起去了很快。
听众：哦，好。
ANDI彭：是的。
好。
酷，让我们重新召集的一类。
好。
所以，这是一种一 在这个意义上开放式的问题
这有很多他们的答案的。
我们将介绍一些他们的简要介绍。
我只想让你们 思考什么区别
这三种类型的排序。
而且我听说，也有很大 的问题 - 是什么归并排序呢？
大的问题，因为这是 我们正在覆盖下一个。
>> 所以，归并排序是 一个分类的功能
非常不同于其他种类。
正如你们可以see-- David是不是做演示
在那里，他把所有的酷 看到如何合并的声音
排序跑了一样，无限 比其他两种类型的快？
好。
所以，这是因为合并 排序实现了鸿沟
而治之的概念，我们已经 谈到了很多在课堂上。
在这个意义上，我们喜欢的工作 更聪明，而不是更辛苦，当你把
而治之的问题，并打破他们 下来，然后把它们放在一起，
美好的事物总是发生。
>> 这样合并的方式 排序基本工作原理
是，它把一个 无序阵列中的一半。
然后它有阵列的两半。
它只是排序那些两半。
它只是保持在半分，在 一半，一半，直到万事俱备
然后递归 把他们放在一起。
>> 这就是真正的抽象。
所以，这只是一个有点伪的。
这是否有意义的 它的运行方式？
因此，让我们只说你有一个 n个元素的数组，对不对？
如果n小于2，可以退货。
因为你知道，如果有 只有一件事，它必须被排序。
否则，你排序左前卫， 然后排序的右半​​部分，
然后合并。
>> 因此，虽然看起来很容易， 在现实中，思考它的
样的困难。因为你喜欢， 嗯，这是运行的一种自身。
对？
它本身运行。
因此，在这个意义上，大卫·感动 在递归类。
这是一个概念 我们将谈论更多。
那就是这一点，这两条线 在这里，其实只是节目
告诉它运行本身 与不同的输入。
因此，而不是与运行本身 n个元素的全部，
你可以把它分解成的 左半部和右半
然后再运行它。
>> 然后我们来看看它在视觉上， 因为我是一个视觉学习者。
它为我好。
所以，我们来看看一个可视化的例子在这里。
>> 比方说，我们有一个数组，六 元素，3，5，2,6，4,1，不进行排序。
好吧，有很多这个页面上。
所以，如果你们可以看看 这里第一步骤中，3，5，2,6，4,1，
您可以在一半分裂它。
您有3个，5个，2，6,4，1。
你知道这些aren't--您 不知道他们正在排序或没有，
所以你把它们分解，在上半年， 成两半，一半，直至最后，
你只有一个元素。
而一个元素总是排序，对吧？
>> 因此，我们知道，3，5，2，4，6， 1，由本身，进行排序。
现在，我们可以把他们重新走到一起。
因此，我们知道的3,5。
我们把这些在一起。
我们知道这是排序。
2.仍然存在。
我们可以把4和6一起。
我们知道，多数民​​众赞成排序， 所以我们这身打扮。
而1是存在的。
>> 然后你只要看看 这两个半就在这里。
你有3,5，2，2，3，5。
你可以只比较 开始的一切。
因为你知道，这是排序 你知道，多数民​​众赞成排序。
所以，那么你甚至没有给 对比5，你只要比较一下3。
和2小于3，所以 你知道2必须走到底。
>> 同样的事情在那边。
1.必须在这里。
然后，当你去把 这两个值加在一起，
你知道，这是分类和 你知道这是排序。
于是在1和 图2中，1是小于2。
这告诉你，1 应该在本月底
看也不看3或5。
然后是4，你可以 检查，它会就在这里。
你不必看5。
同样的事情在6。
你知道6--它只是 并不需要研究。
>> 所以这样一来，你是 只是拯救自己
很多步骤，当你比较。
你不必比较每 元素与其他元素。
你只是比较反对的人 你需要将它与比较。
所以这是一种抽象的概念。
不用担心，如果它不是 相当击中你的权利呢。
但是总体来说，这是 如何合并排序工作。
问题，简单的问题， 之前，我继续前进？
是啊。
>> 听众：所以你说，你拿 1，然后在4和6
并把他们进来。
所以不those--不 你看他们
作为单独的元素，而不是整？
ANDI彭：是的。
所以发生了什么 是，你基本上
正在创造一个全新的阵列。
所以，你知道，在这里，我有 尺寸3的两个数组，对不对？
所以，你知道，我的排序的数组 需要有六个要素。
所以，你只要创建一个 新的内存量。
所以，你是那种喜欢 被浪费的存储器，
但是，这并不重要 因为它是如此之小。
所以，你看1 你看2。
而你知道，1小于2。
所以，你知道，1应该在 所有这些的开始。
>> 你甚至都不需要 看3和5。
所以，你知道1去那里。
然后，你基本上砍掉1。
这是一样，死了我们。
然后，我们只是有2个， 3，5，然后4和6。
然后你知道，你 比较4和2，
呵呵，2应该在那里。
所以，你扑通2下来，你砍了下来。
所以，那么你只需要3 和5中的4个和6个。
而你只是不断砍它关闭 直到你把他们到数组中。
>> 听众：所以，你只是总是 比较[听不清]？
>> ANDI鹏：没错。
因此，在这个意义上说，你是 只是相比较，从本质上讲，
一个号码对另一个号码。
而且因为你知道 ，它的排序，
不必翻阅 所有的数值。
你只需要看看第一个。
然后你可以扑通 下来，因为你知道
他们属于他们需要属于。
是啊。
好问题。
>> 然后，如果哪 有点雄心勃勃，
随意看看这段代码。
这实际上是 物理实现
我们如何会写归并排序。
你可以看到，这是非常短的。
但背后的想法 这是相当复杂的。
所以，如果你觉得自己画了这一点 在你的功课今晚，随意。
>> 好。
大卫也去了这个讲座。
什么是最好的情况下， 运行时，最坏的情况下运行时，
和合并排序的预计运行时间？
几秒钟思考。
这是相当困难的，但那种 直观的，如果你仔细想想。
好吧。
>> 听众：是最坏的情况的n log N +
ANDI鹏：没错。
为什么说它是N日志ñ。
>> 听众：是不是因为它 成为指数更快，
因此它就像一个函数 而不只是单纯的为N
平方什么？
ANDI鹏：没错。
这样之所以 运行时在此为n日志
n是因为 - 你是什么人 在做所有这些步骤？
你只是砍了一半，对不对？
所以，当我们正在做的 日志，所有它做
被分割的问题在一半， 成两半，一半，在更半部。
而在这个意义上，可以种 对消除线性模型
我们一直在使用。
因为当你砍 事情的一半，这是一个记录。
这只是数学 代表它的方式。
>> 然后终于，到了最后，你 只是让通过一个最后一关
把所有的人都在秩序，对不对？
所以，如果你只需要 查一件事，那n值。
所以你是那种 乘两者结合起来。
因此，这就像你已经得到了最终的 检验N-下来日志的n这里
上面这儿。
如果你乘 他们，那是N日志ñ。
>> 所以，最好的和最坏 情况和预期是所有N日志N。
它也像另一个排序。
这就像选择排序 在某种意义上说，它
不要紧，你的 列表，它只是会
做同样的事情，每一次。
好。
所以当你们可以看到，即使 我们已经走了through-- n中的种种
平方，这不是很有效。
而即使是这样的n log n是 不是最有效的。
如果你们是好奇， 有某种机制
这是如此有效，以至于他们 几乎是基本持平的运行时间。
>> 你有一些日志ñ的。
你有一些loglogN个的。
我们不触及他们 在这个类现在。
但是，如果你们是好奇， 随意谷歌，什么是
最有效的分类机制。
我不知道，有 一些很搞笑的人，
like--有一些真的 有趣的那些人做。
你想知道他们是如何 没有想过这一点。
因此谷歌，如果你有一些空闲 时间上，都有些什么有趣的方式
该people--以及 高效ways--人
之所以能够实现排序。
好。
而这里只是一个方便的小图。
我知道在座的各位，是竞猜0之前， 会在你的房间可能是试图
记住这一点。
所以这是很好的在那里为你们。
但不要忘记，made--逻辑 为什么这些数字正在发生。
如果你总是输了，只是让 确保你知道什么是排序是。
你可以贯穿 它们在你的心中
弄清楚为什么那些 答案是这些问题的答案。
>> 好吧。
所以，我们要动 在最后，在搜索。
因为那些对你 谁看过处理器集，
搜索也是部分 这个星期的习题集。
你会被要求执行 两种类型的搜索。
一个是线性搜索和 一个是一个二进制搜索。
>> 所以线性搜索是相当容易的。
你只是想搜索的元素 列表，看看你得到它。
你只需要遍历。
如果它等于什么， 你可以返回它，对吗？
但是，一个我们最 兴趣谈论
是二进制搜索，右，这是 分而治之的机制，
大卫被证明在讲座。
>> 还记得电话簿的例子 他不断拉扯大，
一个那种他挣扎 有点过去的一年，
在那里你把这个问题了一半， 一半，一半，一遍又一遍，
直到你找到你想要的？
而你已经得到了 那运行时也是如此。
你可以看到，它的 显著更高效
比任何其他类型的搜索。
>> 所以我们会去的方式 实现的二进制搜索
是，如果我们有一个数组， 索引为0到6，7的元素，
我们可以看看在中间，right-- 很抱歉，如果我们的问题first--
如果我们要问的问题，请问 该阵列含有的7的元件，
显然，是人类，并且具有 这样一小阵，很容易让我们
说是。
但方式来实现二进制 搜索将是寻找在中间。
>> 我们知道，指数3 中间，因为我们
知道有七个要素。
什么7除以2？
你可以额外1砍掉。
你在中间得到了3。
所以为3数组等于7？
它是不是，对不对？
但是，我们可以做一对夫妇的检查。
是3小于7或阵列 是3阵列大于7？
>> 我们知道，这是不到7。
因此，我们知道，哦，就必须 不会在左半部。
我们知道，它必须是 在右前卫，对不对？
因此，我们可以只砍掉一半的阵列。
我们甚至不有 看它了。
因为我们知道， 一半的problem--的
我们知道答案是 我们的问题的右半部分。
因此，我们只看现在。
>> 所以，现在我们来看看 中间还剩下些什么。
该指数5。
我们再次做同样的检查 而且我们看到，它的体积更小。
因此，我们期待的是左边。
然后我们看到检查。
是在阵列值 索引4等于7？
它是。
因此，我们可以返回true，因为 我们发现在我们的列表中选择值。
我是否通过去的方式 是否有意义给大家？
好。
我给你们也许一样， 三，四分钟，以搞清楚
如何在伪代码本。
>> 所以，想象一下，我问你写 函数调用搜索（）的返回
一个值，布尔值， 这是真的还是false--类似，
如果你找到了真正的 值，如果你没有假的。
然后你 在值传递你
在寻找到值， 是array--哦，我一定会把
在错误的地方。
好。
不管怎样，应该有 到过的值的右侧。
然后INT n是数 在该数组元素。
你会如何​​去努力 伪代码在这个问题？
我给你们喜欢 三分钟的时间做到这一点。
不，我认为有only-- 是啊，有一个正确的在这里。
听众：可以吗？
ANDI彭：是啊，我给你。
是不是工作？
嗯不错。
>> 好。
好球员，我们 要收服入。
好。
因此，假设我们已经有了这个可爱的 小数组在它的n值。
我没有画线。
但是我们怎么能去 尝试写这个？
有没有人要 给我的第一行？
如果你想给我 第一行该伪代码。
>> 听众：[听不清]
听众：你想要 遍历through--
听众：只为循环的另一个？
听众：──。
>> ANDI彭：所以这一块是有点棘手。
想想about--你想 要继续运行这个循环
一遍又一遍，直到什么时候呢？
>> 听众：直到[听不清] 值等于该值。
ANDI鹏：没错。
所以，你可以真正地写 - 我们甚至可以把它简化了。
我们可以写一个while循环，对不对？
所以，你可以有loop-- 我们知道，这是一段时间。
但现在，我要去 说“循环” - 通过什么？
环until--是什么 我们结束条件？
我想我听到了。
我听到有人说了吧。
>> 听众：值等于中间。
ANDI彭：再说一遍。
听众：或者，直到 值要搜索
为等于中间值。
>> ANDI彭：如果有什么是不是在那里？
如果你正在寻找的价值 对于实际上不是在这阵？
听众：你返回1。
>> ANDI鹏：但是我们要 循环，直到如果我们有一个条件？
是啊。
>> 听众：直到有只有一个值？
ANDI彭：你可以循环 until--让你知道，你是
将有一个最大值，对不对？
而你知道，你会 有一个最小值，对不对？
也因为，这东西 我忘了之前的说法，
这东西是 约二分查找关键
是你的数组已经排序。
因为没有办法做 这一点，如果他们只是随机值。
你不知道，如果一个人的 比另一个大，对吧？
>> 所以，你知道你的最大和 您分钟都在这里，对不对？
如果你将要调整 你最大的您分钟和mid--
就让我们假设你的 中间值右这里 -
你要基本 循环，直到你的最小值是
大致相同的最大，右，或 如果你的max是不一样的分。
对？
因为当发生这种情况，你知道， 你最终击中了相同的值。
所以，你要循环，直到你分钟 小于或等于用于：哎呀，
不小于或等于 around--最大的另一种方法是。
>> 这是否有意义？
我花了一些尝试，以获得这一权利。
但循环，直到你的最大值 基本上是差不多少
大于或等于您的最低，对不对？
当你知道这是 你已经收敛。
听众：当你将最大 值是小于最小？
ANDI彭：如果你保持 调整它，这
就是我们要 在做这个。
那有意义吗？
最小和最大只是 整数，我们可能
将要创建的保留 赛道上，我们正在寻找的。
因为数组存在 无论我们在做什么的。
就像，我们没有实际的物理 斩去阵列，对不对？
我们只是调整 我们正在寻找。
那有意义吗？
>> 听众：是的。
>> ANDI彭：OK。
所以，如果这对我们的循环中的条件， 我们需要什么这个循环里面？
什么是我们将要想要做什么？
所以，现在，我们已经有了 一个最大和最小，权，
可能产生在这里的某个地方。
我们将可能希望 找一个中间的，对不对？
我们该如​​何为 能找到中间？
什么是mathematical--
听众：最大加分除以2。
ANDI鹏：没错。
那有意义吗？
做你们明白为什么我们 不只是use--为什么我们这样做
而不是做了2只除以n？
这是因为n是一个值 那将保持不变。
对？
但是，当我们调整我们的最低和 最大值，他们将改变。
其结果，我们的中间 都不会改变太多。
所以这就是为什么我们要 在这里做的权利。
好。
>> 然后，现在 我们发现our--耶。
>> 听众：只是一个快速的问题 - 当你说最大和最小，
在我们假设 它已经排序？
>> ANDI彭：是啊，这实际上是一个 先决条件二进制搜索，
你必须知道它的排序。
这就是为什么排序，你写你的 您的二进制搜索之前，习题集。
好。
所以，现在我们知道我们的中点 是，你要什么做的吗？
>> 听众：我们想比较 即到另一个。
ANDI鹏：没错。
所以，你要比较 月中的价值，对不对？
而这是什么告诉 我们，当我们比较？
什么是我们想要做的之后？
>> 听众：如果该值越大 比中期，我们希望把它割下来。
ANDI鹏：没错。
因此，如果该值大 比中旬，我们
会想改变这些 最小和马克塞斯，对不对？
我们需要什么改变？
因此，如果我们知道价值的地方 在这里，你有什么，我们要改变？
我们要改变我们的 最小的是中端，对不对？
然后否则，如果它在这个 上半年，有什么事我们要改变？
>> 听众：你最大的。
ANDI彭：是的。
然后，你只是去 保持循环，对不对？
因为现在，一次迭代后， 通过，你已经有了一个最大这里。
然后你就可以重新计算中间。
然后你就可以比较。
而你要坚持下去 直到分钟和马克塞斯
已经基本收敛。
而且，当你知道这是 你打它的结束。
而无论你已经找到了 或者你有没有在这一点上。
>> 这是否有意义给大家？
好。
这是非常重要的， 因为你有
在您的代码今晚这样写。
但是你们有一个相当不错的 什么，你应该做的意义，
这是很好的。
好。
所以，我们已经得到了大约七 离开分钟一节。
所以，我们要谈谈 这pset的，我们会做。
因此的pset分为两半。
上半年涉及 实施发现
在你写一个线性搜索，一 二进制搜索，和一个排序算法。
>> 因此，这是第一个 一次在PSET哪里
我们会给予你们什么所谓 分配代码，这是代码
我们已经预先写好， 只是留下了一些棋子落
为你完成写作。
所以你们这些家伙，当你看这个 代码中，你可能会真是吓坏了。
如果你只是想，啊，我 不知道这是什么在做，
我不知道一样，这似乎 这么复杂，啊，放松。
好的。
阅读规格。
该规范将解释你到底 什么所有这些方案都在做。
>> 例如，generate.c是一个程序 这会是你的pset中。
你实际上并没有去触摸它，但 你应该明白它在做什么。
而generate.c，所有它做的是 或者产生随机数
或者你可以给它一个种子，像 预先安排的号码，它需要，
它产生更多的数字。
因此，有一种特定的方式来 实施generate.c其中
你可以做一串数字 为您测试您的其他方法上。
>> 所以，如果你想为 例如，测试你的发现，
你想运行generate.c， 生成一串数字，
然后运行你的助手功能。
你的助手功能就是你 实际的物理写代码。
并认为佣工作为库文件 你写的那些发现正在呼叫。
所以在helpers.c，你会 做搜索和排序。
>> 然后，你要基本上 只是把它们放在一起。
该规范将告诉你如何 把在命令行上。
你就可以测试是否 不是你的排序和搜索工作。
酷。
有没有人已经开始， 遇到问题或疑问
他们现在所拥有的这个吗？
好。
>> 听众：等待。
我有一个问题。
>> ANDI彭：是的。
>> 听众：所以我就开始做 在helpers.c线性搜索
它并没有真正的工作。
但后来，我发现我们只是 要删除它，做二进制搜索。
因此，它的问题，如果它不能正常工作？
>> ANDI彭：简短的答案是否定的。
但由于我们是不是 -
听众：但是，没有一个人的 其实检查。
ANDI彭：我们从来没有 要看到这一点。
但是，你可能想使 确保你的搜索工作。
因为如果你的线性 搜索无法正常工作，
那么机会是你的二进制 搜索是不会正常工作。
因为你也有类似的 逻辑在两人面前。
不，这其实并不重要。
所以唯一的，你转 在有排序和二进制搜索。
是啊。
>> 而且，很多孩子们 尝试编译helpers.c。
你没有真正允许 要做到这一点，因为helpers.c
不具有的主要功能。
所以，你只应该 是实际编制
产生和发现，因为找不到电话 helpers.c并在它的职能。
这样就使得调试 一个痛苦的对接。
但是，这就是我们要做的。
听众：你刚才做的所有，对不对？
ANDI彭：你可以 让所有的嗯，是的。
好。
所以这是它在什么条件 pset的要求你都做。
如果您有任何问题，请随时 免费区之后问我。
我会在这里一样，20分钟。
>> 和是的，处理器集的 真的没有那么糟糕。
你们应该没问题。
这些，只是遵循的指导方针。
一种有意识，从逻辑上讲，是什么 应该发生，你会没事的。
不要太害怕。
有很多的代码 已经写在那里。
不要太害怕，如果你不 明白了这一切手段。
如果这是一个很大，这是完全罚款。
而来到办公时间。
我们会帮你看看。
>> 听众：用多余的 功能，我们看这些吗？
>> ANDI彭：是的，这些都是在代码中。
在游戏中的15，一半的 它已经为你写的。
因此，这些功能 已经在代码中。
是的。
好吧。
那么，最好的运气。
这是一个恶心的一天。
所以希望你们不要觉得太 不好呆在里面和编码。