[音乐播放] 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，一半的 它已经为你写的。 因此，这些功能 已经在代码中。 是的。 好吧。 那么，最好的运气。 这是一个恶心的一天。 所以希望你们不要觉得太 不好呆在里面和编码。