[音乐播放] DAVID J.马兰：这是CS50。 这是三周的开始。 因此，我们有很多令人兴奋的 事到如今覆盖。 大量的机会 志愿者在舞台上。 而最终，今天是 不是在所有的代码。 但是，它是关于思想， 它是关于算法， 实际上带回一些 从零一周中吸取的教训， 其中，召回，我们 推出这个畸形。 而借款的启示 同时，向启动 为了解决日益复杂的 问题的算法。 但首先，一对夫妇的公告。 所以人们，如果你想加盟 CS50的工作人员和同学在午餐 本周五，在这里和在 剑桥，并在纽黑文， 请访问过程中的 网站，在那里一个URL可以找到。 讲课周三将 不能在这里桑德斯。 这将是只在网上，所以 调在CS50的网站， 这里是否在剑桥 或纽黑文也。 然后，问题设置两个 已经在你的手中。 如果你还没有在还没有跌，让我 提供了措辞强烈的建议 如此，尤其是现在，作为 问题设置提前， 你真的想从现在开始，如果不 涉足了一下周末或之前 当他们第一次外出 周五，因为你 发现他们不一定 获得每更长或更有挑战性 东南。 我想你会发现，在 一般情况下，他们往往需要大约 周围的时间量相同。 但可以肯定的依赖 在学生，并且它 取决于心态 与你接近它。 但无一例外，你会 要对一些墙壁跑起来， 而你会打 一些bug，并且你只是 不打算要能够 克服它在某个时候。 而且它是非常有价值的，能够 一步之遥，回来的第二天， 去办公时间，后在CS50讨论 或类似的，真正得到畅通。 所以记住这一点。 最早开始尽可能 就是你能做的最好的事情。 因此，这里是我们开始的地方 类，过零一周。 而且我们可以得到一个志愿者 在这里帮我找话筒？ 行。 站立起来了。 上来吧。 猜猜这是怎么回事工作。 你叫什么名字？ ALAN埃斯特拉达：阿兰·埃斯特拉达。 DAVID J.马兰：阿兰·埃斯特拉达。 上来吧。 很高兴认识你。 ALAN埃斯特拉达：很高兴见到你。 DAVID J.马兰：你在这里 我们当然在零一周。 ALAN埃斯特拉达：我是。 我曾是。 DAVID J.马兰：所以你能不能去 进取，为我们找到迈克·史密斯， 一样快，您可以吗？ 一样快，您可以。 从字面上撕裂问题 在上半年，因为你需要。 ALAN埃斯特拉达：嗯。 DAVID J.马兰：从字面上看 撕裂在一半的问题。 ALAN埃斯特拉达：哦。 毫米。 挺好。 DAVID J.马兰：OK。 好。 谢谢。 ALAN埃斯特拉达：非常好。 行。 DAVID J.马兰：所以现在， 你又缩减 该问题的一半大小。 现在，我们到了四分之一。 你是否关注 我们保持哪边？ [笑气] ALAN ESTRADA：是的，我think-- DAVID J.马兰：什么部分是我们的？ ALAN ESTRADA：消音器，所以。 DAVID J.马兰：OK。 不过，迈克·史密斯是怎么回事 是消音器后。 So-- [笑气] 好吧。 ALAN埃斯特拉达：我们在哪里找？ DAVID J.马兰：迈克·史密斯。 ALAN埃斯特拉达：迈克·史密斯。 DAVID J.马兰：现在，我们在手术。 现在，医生。 Now-- ALAN埃斯特拉达：Let's-让我们用实际。 皇马。 DAVID J.马兰：真。 行。 如果你需要真正的。 现在，它的方法是迈克·史密斯？ ALAN埃斯特拉达：这种方式。 DAVID J.马兰：哪条路？ ALAN埃斯特拉达：等待。 中号is--吧？ 我们开始with-- DAVID J.马兰：是的。 他们离开了。 你的权利。 ALAN埃斯特拉达：是的。 DAVID J.马兰：所以迈克在这里。 ALAN埃斯特拉达：什么？ [笑气] 坏的榜样，伙计们。 抱歉。 DAVID J.马兰：这将教 你跳出你的椅子。 ALAN埃斯特拉达：哦。 呵呵。 我接到你了。 我接到你了。 呵呵。 呵呵。 这is--好吧，我给你。 史密斯就在这里？ DAVID J.马兰：史密斯，谢谢。 所以我会继续找了史密斯？ ALAN ESTRADA：哦，是的。 不不不。 不好了。 这是我的。 DAVID J.马兰：哦，你得到了史密斯。 行。 ALAN ESTRADA：是的，我 得到了史密斯就在这里。 对不起，伙计们。 我想Michael--我们 在寻找迈克尔。 抱歉。 DAVID J.马兰：这是确定的。 好了，现在我们 到帕奇尼和儿子。 ALAN埃斯特拉达：帕奇尼和儿子。 DAVID J.马兰：只有你 和我在这一点。 行。 找到我们迈克·史密斯。 史密斯。 ALAN埃斯特拉达：史密斯。 DAVID J.马兰：史密斯。 我们在研发的垃圾。 ALAN埃斯特拉达：垃圾。 呵呵。 这将需要一段时间。 [笑气] DAVID J.马兰：鞋。 我们在鞋。 ALAN埃斯特拉达：现在，我们gonna-- DAVID J.马兰：好的。 ALAN埃斯特拉达：Which-- [笑气] 哦，这是伟大的。 [笑气] DAVID J.马兰：这是确定的。 ALAN ESTRADA：哦，这是件好事。 我不认为我会 有在这之后PSAT哥们。 DAVID J.马兰：好。 里斯本竞技。 ALAN埃斯特拉达：里斯本竞技。 嗯，L，M，N，O，P。 DAVID J.马兰：OK。 因此，让我们颠覆这个一半。 没关系。 这结束反正不好，因为迈克 史密斯将不会在黄页。 ALAN埃斯特拉达：仙。 DAVID J.马兰：没有，这是确定的。 但是，让我们假装 他的这个页面上。 所以，现在，你已经削弱的问题分解 到一个页面上，我们发现了麦克·史密斯。 [欢呼] 好的谢谢。 行。 这是非凡的。 但它仍然较快 不是线性搜索， 其中，我们开始在 开始的书， 我们将我们的方式，从左至右， 最终寻找麦克·史密斯。 因此，如果该电话本 也许有1000页， 也许它会采取 美国10个左右页眼泪。 但是你可能已经利用 感动的假设 期间所有这一切，这是说 该电话簿中的进步是什么？ 听众：排序。 DAVID J.马兰：它的排序。 对？ 它是按字母顺序排序，所以 所有这些名字和数字 从A的到排序 Z的，和按字母顺序排列在两者之间。 但是今天，我们现在问 这个问题，那么， 怎么做或Verizon的手机 公司让它进入那个状态？ 因为它是一回事，利用 这个假设，因此， 解决与一个问题 算法更有效。 但是，我们从来没有真正 要求在零一周，好了， 多少做到了成本 Verizon公司或其他人 吃出电话簿中有序？ 对？ 这并不重要，如果无所谓 查找麦克·史密斯 是超级快，如果它需要你 今年的页面开始排序。 对？ 你还不如干脆筛选 通过随机化的电话本， 如果它要成为超 昂贵的排序。 因此，如果我们能有另一位志愿者。 让我们在这里仰望 我们如何might--来吧up--如何 我们不妨去整理这些。 如果乔丹居然可以 在这里我们一起在舞台上。 上来吧只是一瞬间。 你叫什么名字？ 凯洛琳：卡罗琳。 DAVID J.马兰：卡罗琳，上来吧。 你会被加入 我和乔丹在这里。 卡罗琳，谢谢。 好吧。 所以，我们在这里 卡罗琳是26蓝书 这FAS使用管理 一定的期末考试。 这些越来越难找， 但是我们提前做了 是，我们已经把别人的名字 对每个这些的前部， 但我们已经把通过简单 然后扑灭的全名。 因此，我们会把这个人的名字 L，D，J，B，所有的一种方法，通过Z， 但他们以随机顺序。 所以，如果你愿意，你说话 通过问题，因为你的方式 做吧，你能不能继续前进， 梳理这些对我们来说，从A到Z. 听众：好，那么L是一样，中间的。 C的开始。 B.ĴL.前B，Q. DAVID J.马兰：保持那个 想了一秒钟。 因为否则，这仅仅是 有趣的你，我，和约旦。 在那里，我们走了。 听众：[听不清]。 R. DAVID J.马兰：OK。 你在干什么？ 凯洛琳：M来澳后， DAVID J.马兰：OK。 凯洛琳：O. DAVID J.马兰：哦，好。 凯洛琳：E. DAVID J.马兰：E，F。是啊。 凯洛琳：T，U，V。 DAVID J.马兰：V，T，U，V。因此， 看起来你是making--继续下去。 它看起来像你正在做 一大堆在这里， 和那种一大堆那边。 所以第一个字母的一半， 下半年字母。 行。 好。 那种分裂的问题一分为二。 M，N，X的呀。 凯洛琳：K. DAVID J.马兰：OK。 那种K.所以你选择 他们一个接一个， 把它向左或向右， 或Z的去在地板上。 行。 凯洛琳：Z回事地板上。 DAVID J.马兰：OK。 Y为打算在地板上。 现在，我们可以把X. 凯洛琳：G. DAVID J.马兰：G的走左边。 S被在朝好的方向发展。 好吧，一个是要全部离开的方式。 凯洛琳：A，B，C，D。 DAVID J.马兰：现在，好。 我们有A，B，C W公司去那里。 好吧，T。 凯洛琳：H，I，J。 DAVID J.马兰：H，I，J好。 凯洛琳：在中心，我gonna-- DAVID J.马兰：OK。 所以，现在，我们要样 对合并这些不同的桩。 因此，从A到C，然后我看到D和 E和F和G和H和I尼斯。 Ĵ，K。然后，这个桩 倒挂，但没关系。 当然。 我们可以削减一些角落。 行。 然后，我们需要W，X，Y，Z。 凯洛琳：没错。 DAVID J.马兰：优秀。 所以，非常感谢你 卡罗琳进行排序这些。 [欢呼] 谢谢。 非常感谢。 所以，现在让我们来考虑一下 卡罗琳如何着手这样做， 而究竟我们 能够用于：我们如何 能够解决 的问题，当我们只是 给出一大堆的随机输入。 好了，它看起来像有 有点制度存在的？ 对。 因此，早期的信 在字母表，她 是把到左侧，与 后来字母的字母表， 她投入的权利。 而当她发现 一些近信件，那些 说去旁边对方， 她把那些为了。 所以，我们种了这些小 桩发生排序的输入。 所以这是相当喜欢什么 我们中的大多数人会做。 排序，我们将通过它筛选， 我们希望一种有一个机制。 但它可能是很难写 下来在公式本身。 这感觉更多的有机比一个小。 因此，让我们来看看，如果我们现在就可以绑定 这个问题用更少的投入。 而不是26，让我们 做一些事情少得多 只说，七，背后 这些门，可以这么说。 是否有刚刚7个号码？ 如果现在的目标在 一方面是要找到一个值， 让我们来看看如何有效 我们可以去这样做。 而如果让我们现在可以来看看 开始应用一些数字， 或一些公式，用以描述 我们的电话簿的效率 算法，我们的考试书的算法，以及 更一般地，查找信息。 因此，对于这一点，让我先走了， 在触摸屏上在这里， 提出了一个网页浏览器，有 正是这七门。 如果我们能得到一个其他 志愿者来就在这里， 我已经把这些同门在这里。 快速志愿者。 这埃德蒙顿演示会 为更快和更快了。 下来吧。 你叫什么名字？ TREVOR：特雷弗。 DAVID J.马兰：特雷弗？ 好吧，特雷弗，下来吧。 因此，特雷弗曾在这里志愿 做了类似的问题，但一个是 在范围窄，那将 让我们现在尝试形式化 的过程进行排序这些数字。 所以特雷弗，很高兴见到你。 因此，这里是一个数组，所以要 说，七门列表。 来吧，找到我们的号码50。 然后在事后， 告诉我们你是怎么找到它。 如果be--所有权利。 是啊，这是这里的人吗？ 嗯，哦。 行。 你点击的那一个。 好。 而良好。 现在你点击一个。 让我给你话筒， 让你拥有了它在短短的时刻。 来吧，然后点击 接下来，你打算大门。 对很好。 TREVOR：我可以unclick门吗？ DAVID J.马兰：不，你不能unclick。 TREVOR：OK。 这个。 DAVID J.马兰：你想去哪里去了？ 哪一个？ TREVOR：那一个。 DAVID J.马兰：没有。 TREVOR：OK。 这个。 DAVID J.马兰：是的。 这是很好的。 好吧。 那么，什么是你的算法或 程序这样做，特雷弗？ TREVOR：我只是通过去 门，直到我发现了一个50。 DAVID J.马兰：OK。 优秀的算法。 所以这是很好。 因为事实上，如果我透露什么 这背后的另外两个门，是什么 我们会发现这里是 我们只有随机输入。 所以这实际上是为 好，你可以得到。 而事实上，你有优于 详尽地搜索整个数组， 因为这将是真的 倒霉，如果你击中​​了数 50在最后一门。 但是，如果我们是什么，而不是 给你一个假设。 假设我排序的所有 这些门周围， 让你有 号码排序此时， 但是这一次它的实际 一个different--此时， 它实际上排序为您服务。 而现在的目标在眼前 是打数50。 TREVOR：OK。 DAVID J.马兰：是什么 你的算法将是？ TREVOR：嗯，如果是 排序，它要么会 以be--如果大到最大， 降，这将是第一位的， 或者如果它是相反的， 这将是最后一个。 所以，我就请点击此门， 然后只需轻按最后一扇门。 DAVID J.马兰：优秀。 好吧。 因此，我们找到了50号。 所以，只要你知道 他们排序，我们 能够利用这个假设。 因此，他们是太像了 电话簿的例子。 只要你有，即使有 像这样的小问题， 您的输入预先排序，我们可以 居然发现价值可以说是 更有效。 我没有告诉你，如果它是 排序从小到大，或从大到小， 所以这是非常合理的 开始在一端或另一 实际上发现的目标值。 因此，感谢特雷弗为好。 我会propose--很好做。 我们有一个小夹子，事实上，这 是在我们最喜欢的时刻在CS50， 因此有时这些演示 按计划不太去了。 事实上，现在，我 拉错接口 与使用该触摸屏。 所以这是我的错在那里。 因此，这将使 明年的剪辑 为什么我点击我的屏幕上。 但是，让我们快速浏览一下 在去年发生了什么 周杰伦，谁上前，多 像特雷弗在这里，主动请缨， 在这个短片，你会看到 同样的演示如何做不大 揭示了解到同样的教训。 [视频回放] - 所有我要你现在要做的就是 找到我，对我们来说， 确实，数50 一步一步来。 一些-The 50？ 一些-The 50。 而且，您可以显示什么 背后都有这些门 简单地通过用手指触摸它。 该死的。 [笑气] [结束播放] DAVID J.马兰：所以很顺利。 这些都是未排序的大门。 而周杰伦，当然， 发现这一切太快。 特雷弗做一个更好的工作 在一个教育时机而言， 可以这么说，今年 需要更长的时间来找到它。 当然，后来我们给了 周杰伦第二次机会， 因此我们整理了门， 就像我们做的特雷弗， 和Trevor做超级好这段时间。 但周杰伦做到了一半快。 [视频回放] -The现在的目标是要还 找到我们的数50， 但这样做算法，和 告诉我们你是如何去了。 -行。 - 和，如果你找到它，你把这部电影。 如果你没有找到它，你还给我。 -Man。 哦！ - [听不清] OK。 所以，我要检查结束 首先要确定是否there's--哦。 [掌声] [结束播放] DAVID J.马兰：OK。 所以很明显分拣门 导致更大的效率。 因此，快两倍 就是我的意思存在。 所以周杰伦真的很幸运两次。 而且他也很幸运在这最后 今年，我点了一些蓝光光盘 实际上给出。 我很抱歉这一年，我们 没有具有相同的，特雷弗。 但更好的是是在几年前。 而有些人可能知道这 研究员，肖恩，当他在CS50谁， 有确切的被质疑 同样的问题，尽管在SD， 因为你很快就会看到，早在一天。 而且你会发现，不仅没有 他需要比周杰伦长了一点， 比特雷弗更长一点，这是 其实这个难得的机会 从事几乎每个人都在 众人一拉是价格合适，鼓励 他找到我们寻求的数量。 让我们来。快速浏览一下。 [视频回放] -行。 所以在这里你的任务， 肖恩，情况如下。 我曾经背后隐藏的这些 门七位数。 但在一些宗门藏 还有其他的负数。 而你的目标是想 数字除此之外排 作为只是一个数组，或者只是 纸片的序列 在他们身后的数字。 而你的目标是，仅在使用前 阵列在这里，我找了七位数。 而我们则要去批判 你如何去这样做。 -好吧。 -find我们七位数，请。 第 五，19，13。 [笑气] 这不是一个很难回答的问题。 一。 [笑气] 在这一点上，你的得分不是非常 好，所以你还不如继续下去。 三。 [笑气] 继续。 坦率地说，我不禁想知道 什么你甚至想，so-- [笑气] 只有最上面一行，因此 你有三个左侧。 所以找我七人。 [笑气] 17。 七。 [掌声] 好吧。 [结束播放] DAVID J.马兰：所以我们可以 观看这些整天。 当然，一些 今年的演示或许 现在最终会在明年 今年的视频以及。 所以，现在让我们来实际 集中在算法 在这里，如果我们不能看到 现在就开始正式 我们如何去获得我们的数据 进入此状态，它的排序， 所以，最终，我们实际上可以 更有效地搜索。 而且即使我们打算 使用非常小的数据集， 像八个数字我们 这里有在黑板上， 最终，这些同样的想法可以申请 1000输入，一百万的投入， 4十亿输入，因为算法 将要基本相同。 所以这是我们最后一次 今天志愿者的机会， 但也许是最复杂的， 为此我们需要8名志愿者 上车，通过走路美国 什么会很快整理的过程 是对这些音乐站在这里。 让我先回到这里。 因此，人们在turquoise--绿色的是什么呢？ 你犯？ 二。 下来吧。 行。 三。 四。 让我 - 确定，五。 你正在你的朋友提名。 六，七，八。 上来吧。 好吧。 太谢谢你了。 上来吧。 上来吧。 好吧。 所以，我们这里 - 这 是其中比较尴尬的， 因为这将要求你幽默 我的时间只是一点点。 你应第一。 你叫什么名字？ 安南：安南。 DAVID J.马兰：安南。 大卫。 你叫什么名字？ 约瑟夫：约瑟夫。 DAVID J.马兰：约瑟夫， 你是二把手。 SERENA：小威，排名第三。 斯特凡，排名第四。 辛西亚：辛西娅。 DAVID J.马兰：辛西娅，排名第五。 [听不清] DAVID J.马兰：[听不清]。 大卫，排名第六。 马特：马特。 DAVID J.马兰：马特的第七位。 然后呢？ WAVERLY：韦弗利。 DAVID J.马兰：韦弗利，排名第八。 好吧。 如果您could--哎呦。 如果你所有的，因为你的 第一个挑战，有 八音乐架 这里面对观众。 如果你可以把你的号码上 这些乐谱架以这样的方式 他们排队的 相同的数字在黑板上。 所以，让自己看起来像由 把这些音乐你的号码 站在这里。 优秀为止。 优秀的。 行。 所以，现在，我们要问 问题在几个不同的方式。 我们如何去整理 这些人在这里？ 因为我们有几种方法 早些时候，由此我们 一种使两个不同的桶。 然后，我们一般 拼凑的东西放在一起。 当我们看到两个数字 这属于一起， 我们把它们放在一起。 两个字母属于一个整体。 但是，如果让我们来看看我们 不能正式这一点， 让我们最终必须 一些伪代码，您会， 使用它可以解决这些问题。 所以，现在，我看着窗外 在这里这些数字。 而且我看到一大堆的错误。 最后，我想一上 左和八个在右侧。 所以我在看 这两个，四个和两个。 而且什么问题，很明显？ 是啊。 所以。 两个明显到来之前 四，所以你知道吗？ 让我先坐贪婪的方法， 如果你愿意，很像问题 设置埃德蒙顿如果从召回 标准版习题集之一， 在这里我只是在本地解决的问题 这是正确的在这里我面前 并且，顺其自然我。 行。 因此，二和四，让我走 前进，只是换你们两个。 如果你能实际移动 自己和自己的论文， 我似乎已经得到了 列出一个更好的状态。 现在，他们是很好的。 我会继续前进， 四和六，显示效果不错。 不是一个问题。 六，八，确定。 八和一，另一个问题。 因为什么是真正的大约八和一个？ 一位来自前八， 所以我们应该怎样做？ 让我们来交换这两个。 一个和八个。 而现在，我要坚持下去。 我会继续向前看。 让我们看看会发生什么。 八三， 当然，乱序。 让我们来交换。 八，当然，七，。 坏了。 让我们来交换。 八，五，当然，我们的交换。 好吧。 列表进行排序。 是吗？ OK，显然不是。 但它是更好一点，对不对？ 因为通知发生了什么事。 每当我们进行了互换，一个小 种数渗出的方式， 而一个更大的数字 渗滤液这样一来，不然我们就 开始说冒泡到 向左或鼓泡到右边。 现在，它是不够的，因为 充其量只是一个数目可能 已经搬到一个地方 向前，或在最坏的情况， 一些可能有 进一步移动一个位置。 所以，你知道什么，这种 中工作得很好至今。 让我再次尝试。 两个和四个，他们确定。 四，六，他们确定。 六一，乱序。 因此，让我们换你们两个。 而现在，注意到这个问题的 开始变得好一点了。 六三，乱序。 让我们来换你们两个。 六，七，你是好。 七，五，当然，乱序。 七，八，为了。 而现在，我可能需要 为此多做几次。 而事实上，想为自己 也许多少次最大 我可能要来回走？ 我们会回来的。 因此，二和四都还OK。 四一，没了。 所以，让我们交换。 再次，注意在视觉上 一个是一种冒泡 到左侧，在那里它应该的。 四个和三个交换。 四和六。 六个和五个交换。 六，七。 七，八都不错。 好。 我们正在变得更好。 所以，让我们来看看。 现在，我们有两个和一个。 当然，交换。 两个和三个，三，四，四和 五，六，七，七，八。 好。 你知道吗？ 因为我做了一个变化出现， 让我做一全面的检查。 让我一路走 回到起点。 行。 一，two--烨，看到了吗？ 出事了。 三，四，五，六，七，八。 而在这最后一关，是 你满意我现在 自称是排序？ 行。 从外观上看，这是千真万确的。 但在功能上有什么 也还只是发生 在这最后一关，让您 确认，这份名单确实 排序？ 我做了什么或不做这最后一关？ 听众：没有更改。 DAVID J.马兰：对不起？ 听众：没有变更。 DAVID J.马兰：没有更改。 因此，这将是愚蠢的我来 再次做同样的算法 如果我没有做任何 改变第一时间。 而国家并没有改变。 当然，我不会做 任何改变的第二次。 所以，它的安全，现在 也就是说，列表进行排序。 事实上，这是现在 东西，我们会一般 电话冒泡排序，即配对， 你再纠正错误， 又一次，又一次，你 不断来回， 和来回，直到你 让没有这样的掉期交易，在这一点 你可以相信，是啊，我 完成修复所有的错误。 让我们重新设置，并尝试另一种方法。 如果你们能返回到 该命令你刚才， 这看起来是这样。 现在，让我们的做法一 有点像考试的书， 因此我们不断 选择字母表的字母 我们有种想 对付下一个。 也许这是一个很高的信， 像A，或低字母Z 所以，大家又回到这个顺序。 现在让我做这个。 让我们来看看我知道我有 八个数字在这里。 我要继续前进， 只是刻意选择 最小的元素。 对？ 这似乎直觉了。 我为什么不找最小 元素，把它放在它属于， 那么获得下一个最小的元素，把 它在它所属，而只是重复。 因为直观， 应该工作了。 于是四，这是一个非常小的数目。 我会记住这是。 等待一分钟。 两个较小。 现在我还记得，其中两个 是的，忘记约四。 稍后我们会处理这一点。 六，我不感兴趣。 八，我不感兴趣的 一个是我的新小数目。 所以，我要记住的是。 三，不感兴趣。 七，不感兴趣。 五，不感兴趣。 因此，没有脱落 今年的舞台， 我要抢号埃德蒙顿 什么是你的名字？ 安南：安南。 DAVID J.马兰：安南。 如果你能和我一起在 在列表的开头， 让我们把你属于你的地方。 Unfortunately--你叫什么名字？ 史蒂芬：斯特凡。 DAVID J.马兰：斯特凡是在路上。 因此斯特凡解决此之前， 的问题，我们应该怎样做？ 我们该怎么办与斯特凡？ 听众：[听不清]。 DAVID J.马兰：OK。 因此，我们可以做到这一点。 那种我们可以采取斯特凡和他的 四，并把它放在一个变量 并抓住它的 一定的时间， 从而使空间的头号。 而这也不错。 我可以建议，为什么不 我们只要把斯特凡这里？ 为什么会这样侵犯1 的想法，我们开始 谈到最后一次，最后一周？ 是吗？ 听众：[听不清]。 DAVID J.马兰：有没有索引它。 如果你觉得这，的确，作为一个 数组，这就像消极的， 所以没有记忆实际上 在这里，如果这确实是一个数组， 就像我们上周在演讲中声明。 所以，我们不应该这样做。 我们可以将其存储在一个变量。 或者，你知道吗？ 我听到有人建议它。 还有什么可能我们做斯特凡？ 为什么我们不赶他， 让他在那里一把手了。 所以，如果你想要去那边。 事实上，这是一个 相当不错的解决方案。 现在，一方面，我有样 所取得的问题更加严重。 四是现在越来越远 从那里应该。 它应该是朝着这个一半。 但是，你知道吗？ 这可能是运气不好。 也许第八在这里。 因此，也许我们会 已经得到了幸运， 并推8更接近结尾。 因此，在一天结束时， 那种一切平均数。 我们不需要关心四人。 我只关心现在的问题是 选择的最小元素。 而现在，我要去 做的是忘掉头号 永久，因为我知道 我身后列表现在排序。 所以，我的名单是以前大小八强。 现在，它的大小七。 所以我的问题越来越 更小的，虽然线性。 所以，现在，我要选择 目前最小的元素，两种。 六，八，四，三，七，五。 这是最小的元素。 所以，我该怎么办with-- 你叫什么名字来着？ 约瑟夫：约瑟夫。 DAVID J.马兰：约瑟夫？ 我们要离开约瑟夫到位。 现在，我要假装 这些家伙are--好， 我知道这两个 已经排序。 现在，让我们专注于 其余名单。 六是目前最小的。 八是更大的。 四是现在目前最小的。 三是现在目前最小的。 所以现在，我要选择三种， 谁is--你叫什么名字来着？ SERENA：小威。 DAVID J.马兰：小威，如果你能 抓住你的号码和交换with-- 格桑：格桑。 DAVID J.马兰：格桑。 快点回来，我们很 要交换这两个。 现在，让我们把这个自动驾驶仪。 我会去把它给你们 以选择下一个最小的元素。 敦，讨债，讨债，讨债。 排名第四，你该怎么办？ 优秀的。 现在，我要再拍通。 敦，讨债，讨债，讨债。 我看到五是下一个最小。 现在，我打算采取另一种通。 敦，讨债，讨债，讨债。 六是最小的。 好。 七是最小的。 不用找了。 八是最小的。 完成。 因此，我们刚刚通过反复做 后，其他选择一种元素 正在实施的东西，我们 要为选择排序正规化。 而且这甚至 简单的解释， 在字面上你 想要做的就是保持 来回通过列表 选择，下一个最小的元素， 直到大功告成。 因此，它更简单，也许 凭直觉，高于去年。 让我们来试一试最后一个。 如果你们能重置自己 到以下位置 最后一次，让我们看看如果我们不能 现在正式另外一个方法。 事实上，会有人 在那里想提议 怎么回事，我们可能会去这样做？ 如果没有折腾出的流行语或排序 这是已知的答案， 只是凭直觉，我们能做什么？ 听众：[听不清]。 DAVID J.马兰：是的。 因此，有一些伟大的直觉那里。 好东西似乎发生迄今 在当我们把计算机科学 并征服分裂的问题 成两半，一半一半。 所以事实上，我们 可以开始这样做。 而事实上，这将是，我们将 看，我们的最佳解决方案之一呢。 但是，让我们回过头来，不久。 事实上，我们要做的 本周稍晚。 还有什么可能我们该如何解决呢？ 所以每个人都在这里是 看似随机的顺序。 你知道吗？ 而不是来回走， 来回，来回 每一次，这种感觉就像 我做了很多的步行。 为什么不让我刚开始在 在列表的开头， 和刚刚放四个它所属？ 因此，让我承担的那一刻起 我的名单只有这个第一要素。 为四排在这个时刻， 如果我所关心的是这里的一切？ 这有点平凡真实的，对不对？ 像含有一个号码列表中，并 这个数字四是明显的排序。 所以，我只是规定 这个列表进行排序。 但现在我有这个名单的其余部分。 所以，现在，我遇到两个。 其中有两个作用明显 对于四个属于？ 前四人。 所以，我能做些什么吗？ 你叫什么名字来着？ 约瑟夫：约瑟夫。 DAVID J.马兰：约瑟夫， 如果你能后退一步 只是一个与你的电话号码的时刻。 现在我应该斯特凡在这里做？ 让我们转移斯特凡在这里。 现在，让约瑟夫来到这里。 现在，让我声称， 这里的一切进行排序。 因此，类似的结果，但一 完全不同的方法。 我还没有看什么是那里。 我只是不停地服用元素 因为他们交给我， 并加以处理。 所以，现在，我看到老六。 哪里老六属于？ 我们有两个，四个，六个。 正是她现在。 因此，让我们离开那个独自一人，而现在 权利要求，这部分列表的 现在排序。 所以，这种感觉从根本上 在不同的我只是 通过列表正朝这边 线性，而且我从来没有翻倍了。 是。 好吧。 所以八，你在哪里属于？ 就在这儿。 完善。 所以，现在之一。 嗯，哦。 这感觉就像它的 将是昂贵的。 现在，以前的算法中， 我刚换的人。 所以，我可能把他在一路 开始的时候，但随后又转而约瑟夫。 但是，如果我移动约瑟夫，现在 这是怎么回事是错的？ 现在，我已经有点儿undone--我已经 采取一步步推进，然后 退一万步，因为现在 约瑟夫会失灵。 因此，让我们做到这一点。 如果你可以采取一把手 而退一步就一下。 我们怎样才能put--什么 又是你的名字吗？ 安南：安南。 DAVID J.马兰：安南的地方？ 需要什么就 到二，四，六，八？ 他们都需要转移。 因此，如果其中8把业务转移 第一，后面是6个，然后四，那么两种。 然后，安南，如果你愿意 喜欢到这里来的，不错。 但在这里，我们刚刚 那种付出了代价 在不同的点的算法中。 而最后一次与选择 排序，甚至冒泡排序， 我走回来， 第四，反反复复， 这肯定是添加了 在时间方面，并逐步从字面上。 插入排序，在第一次 一目了然，看起来像它 超级聪明，因为我只是 取得缓慢，逐步进展， 但我不打算这样来回。 但是，如果有人确实是 失灵，通知 所有我必须做的工作。 我不得不把一半的列表 只是为了腾出空间给一把手。 因此，它是同量 工作迄今它 感觉，只是不同类型的工作。 让我们继续。 所以，现在我们知道，每个人都 1到8之间进行排序。 在这里，我排名第三。 如果你喜欢拿起 第三，退一步之一。 而且你们怎么需要做什么？ 是的。 所以这是另外一个，两个，三个步骤。 三个单位的时间，仅仅花费 我，使三者可以现在适合。 最后，七。 让我们继续前进，并有 你退后一步。 这只会花费我们 一个单位时间，但没关系。 而现在，五的打算 要贵一点。 如果您想退一步。 我们需要移动八， 七，六。 然后大家现在来分类的。 因此，一只大手在这里我们的志愿者。 太谢谢你了。 [掌声] 谢谢你们。 谢谢你们。 因此，让我们现在只是怎么看 昂贵的这一切了。 让我们考虑可能是 最简单的这些，冒泡排序。 而且我说的简单，仅仅是因为 你可以只是贪婪地解决这个问题 在这里解决的配对问题。 修复配对问题 在这里，连连 周而复始，重复尽可能多 倍，你实际需要。 所以，事实证明， 用冒泡排序，那么， 要走多少步我必须采取 该算法的第一次通过？ 我可能take--让我们see--之一， 二，三，四，五，六，七。 还有的八种元素在这里。 因此，它如N减1步骤 从列表的开头获得 到列表的末尾。 但随着选择排序，还记得我 一次又一次地选择这些元素 又一次这是最小的， 我把它在的地方， 但我不 再次看我身后。 所以，我认为这是一个更加清楚一点 那么这是第一次，我可能会 必须采取所有N减1步骤 找到的最小元素。 然后，我把他们在的地方，我 驱逐谁在这里之前。 但是当时我没有 守望着这个元素， 因为我知道这是 已经最小。 所以，现在，我可以看看短短七年 元素，那么六要素， 然后五行，然后四个要素。 等数学上，如果n是 元件或号码的数目 我们开始使用，你可以想像 这是相同的如正减1， 加N减2步， 加N减去3个步骤， 加N减去4个步骤，所有的 一路下跌到只有一个步骤。 而我在我的最后一个人。 如果你还记得，很多 的统计书籍或数学书 对这些公式 精装背部或它们的前， 事实证明，这一系列 可表示更简单地 为N乘以N减1比2。 而且它是很好，如果这不是 在你的脑海里。 但是，这确实是真的。 这是写它只是一个简单的方法。 然后，如果你认为 回到小学， 当你刚开始繁殖 东西出来，这门课程， 是仅仅局限于N的平方减去n乘2分。 所有我所做的就是扩大 表达式那里。 因此，让我们重写这个 有点不同。 这n值的平方除以2减去N / 2。 所以，再一次，我只是样的应用 一些算术规则存在。 但现在发现的最大期限 在这个表达式，可以这么说， 是是n的平方。 所以，是的，这是Ñ平方 2，再减去N / 2分。 但是，一般情况下，如果n 将是一个很大的值， 我要去声称是n的平方 将是主导因素。 它只是要 更大的贡献 到步骤大于n / 2的数量。 所以，什么意思呢？ 让我们尝试一个简单的例子，甚至 虽然数学变得有点大了。 因此，假设我们有100万人次 在舞台上，即100万的事情 我们要排序。 让我们插上一百万 到正是公式 看看有多少步骤，它需要总 比如使用排序一百万元， 选择排序。 所以我们会像以前一样有相同的配方。 我想插一百万，让我得到 2百万平方分， 减去一百万除以2。 如果我这样做，数学提前 在这里，我们有500个十亿 减去50万件，其中 给我们499999500000， 这是相当不错的大。 事实上，如果你现在比较 499十亿999亿美元， 500000对我们原来的价值， 500强十亿，它是如此该死的接近。 对？ ñ平方2给出了分 us--或者说，正平方除以2 给了美国500强十亿。 那是相当的接近 为499999500000， 这就是说中减去500000， 或更一般地，减去脱 ñ平方，不是一个真正的大问题。 n个平方，使这些 数量的增长非常快。 现在，这不仅是重要的，只要 因为我们作为计算机科学家， 一般都不会去管这么多 关于这些公式的细微差别 而正是 准确的答案。 我们关心的，不仅如此，你知道吗？ 在一天结束时，这个公式 是n的平方的数量级。 是的，我们用2在那里分裂。 是的，我们减去关闭N减去2。 但在一天结束时，术语 这真的伤害了我们，并且收费我们 很多步骤是平方项。 所以，什么是计算机科学家 是要一般做 是忽略所有的那些 小订单条款， 而只是看一个 最有助于成本。 这是很好的，因为我们可以 现在谈论的更大的通用性 有关算法，并可以对它们进行比较。 而事实上，我 使用此操作系统是经过深思熟虑的。 当我说的顺序 对，我特别 指的是什么 所谓的大澳和大O 是一个符号，一个计算机 科学家用来描述 一个上限的东西。 所以，如果你说一个算法 在大O n个平方， 我建议只是一个 刚才那装置 在其运行的条件 时间和效率， 它需要的顺序 n个平方的步骤。 也许更多，也许更少。 但它是n的顺序平方。 这就是上限。 它不会是 比这更痛苦。 它不会为n的三次方，或2 到n，什么更大。 这是一个上限 在任何的费用。 因此考虑到，让我们 考虑的几个例子。 而这仅仅是一个有限列表 很常见的运行时间 为的意思是算法 说明一些事情，我们已经 已经看到了。 因此，例如，在的情况下 选择排序，就是我自称在这里 是选择排序的运行 时间是n的顺序平方。 在最坏的情况下，我将不得不 一大堆的随机数在这里的。 正如我们看到的数学， 如果我继续走 该列表，通过 列表中，选择下一个最小的 一次又一次的元素，如果我 其实写下所有的步骤 我正在为我提出通过公式 之前，它的Ñ平方的数量级 我正在采取措施。 而事实证明，泡沫 排序和插入排序 只是在最坏的情况下慢。 考虑，例如，插入排序， 在最后的算法，我们处理了， 其中有我们来看看元素， 然后将其在它所属。 然后我们看的下一个元素， 并将其插入它所属。 因此考虑可能的最佳方案。 假设我有我的志愿者排队 从字面上是这样，一至八， 已经排序。 多少个步骤是插入排序 要采取八人进行排序， 如果他们在舞台上到达 这样看？ 八人已经排序。 我用插入排序。 这最后的算法。 好吧，让我们重演了真正的快速。 所以，如果我从这里开始，我看到一个。 究竟应该属于？ 它属于这里。 我看到两个。 哪里两者属于？ 就在这儿。 我看到有三。 哪里做三件属于？ 就在这儿。 我看到四个。 就在这儿。 五，六，七，八。 我们没有理由重复自己。 所以，多少步 的是，在正的条件？ 它的n的顺序上 步骤，对不对？ ñ减1。 不过，我参加了一个线性数 步骤，现在我完成了。 所以这是最好的情况下，虽然。 那么最坏的情况？ 什么8人在那边， 七均出现了下滑， 与一，两个人在这里，所以 该列表是真正逆转吗？ 那么，会发生什么情况确实 如果这是多少？ 我们会做只是一对夫妇的例子。 如果有什么，的确，排名第八 在这里，和number--呐喊。 那么，如果确实，数 八成是一路看过来， 而我使用的插入排序？ 行。 我要求目前它在的地方。 但现在，seven--哪里7去了？ 当然，它会在这里。 所以，我要搬到8在一个地方。 现在六，哪里去了？ 好了，没事。 现在，我要搬到8比 的地方，和七个以上的地方， 然后我放下下降6。 所以第一次，它的成本 我一步解决的事情， 那么它花了我两个步骤来解决的事情。 多少个步骤是 要采取修复 事情要投入五在正确的地方？ 三。 因为现在我要 移动一个，两个，三个。 它是如何许多步骤要采取 要放四个在正确的地方？ 4加5，加6加7。 所以它的数学相同 我们描述的选择排序。 我们有这个系列 这只是增加。 1加2加3加4， 或者相反地，7加6 加5加4加起来为今天的 的目的，以n的顺序上的平方。 因此，让我规定太那个 冒泡排序也是为n的平方。 因为随着冒泡排序，每个 一次我去通过列表， 我是在大约多少步？ 每次我从字面上 步行到那里呢？ 大约n步。 多少次，但可能我 需要经过的名单？ 好了，大致N次。 也许Ñ减去1，但大致n倍。 好了，这是为什么？ 那么，与冒泡排序，如果 我们开始冒泡排序， 与列表在最坏的可能 的局面，而这又是完全 向后，有什么事情发生？ 我去通过列表和数量 一个人属于一路那边。 但随着冒泡排序，多远做一件 移动通过列表我第一遍？ 多少个点没有，他得到 接近正确的位置？ 只一个。 所以，那种如果你的理由，通过这一点， 通过该算法每一次， 大卫的大致采取n步。 但究竟有多少通行证 通过列表是它 要采取一泡 到它所属的左侧？ 他必须像移动， n个空格这种方式。 所以才做了列表的排序， 我不得不来回走动n次。 而每一次，我 看着n个元素。 所以，做事情ñn次上 n的顺序平方。 现在，我们将在一些人认为 短裤的 嵌在CS50的下一个问题 设置，另一种方法中，在这些， 但现在，我们只考虑 其他一些运行时间， 特别是如果分拣那些采取 时间一点点地下沉研究。 什么是我们已经看到的算法 这需要n个步骤的顺序吗？ 我应该采取直线号码 步骤，我们已经看到迄今？ 那是什么？ 手机目录搜索。 第一算法。 对？ 当我们是线性 寻找麦克·史密斯？ 的确。 从零一周，当我开始 翻一页的时候， 我甚至说，这是一种 线性感觉的算法， 我们不得不对那张照片 板与直红线 和直黄 行，那确实 算法是在n大O操作。 因为找到迈克·史密斯在接受电话 的n页，在最坏的情况下的书， 可能要花费n步。 怎么样服用出席？ 一二三四五六。 什么是这个运行时间 算法采取出席？ n个大O，因为在理论上我 在房间里点大家。 现在，顺便说一句，怎么样 从零一周其他优化？ 二，四，六，八，十，十二。 一个计算机科学家会 实现好，等待一分钟， 这就是顺序上 通过两个步骤除以n。 对？ 因为我做两个人的时间。 但是，我们要忽视 那些低阶项， 我们只是要 扔掉除以2， 而只是说，正对大澳 该算法为好。 这个如何？ 我们将跳过其中的一些，但什么 是一种算法，是日志的n？ 这大概需要登录n步？ 分而治之。 没错。 就像在电话簿的例子 零一周，今天早些时候， 在这里我们把问题 一遍又一遍又一遍。 我们在上周画在黑板上 零弯曲的绿线， 我们说，当天是 对数的算法。 事实上，数量步骤它 需要进行分而治之， 或二进制搜索，我们将开始 调用它，如在电话本， 是日志和步骤的顺序。 这是一个有点古怪的。 有什么需要一步到位， 或者更具体地 的步骤的常数α 也许这是二，也许是三， 但计算机科学家只 简化了它作为1大澳， 步骤一些常数。 有什么东西，你能做到这一点 采取的步骤的常数α 什么是拍手的运行时间？ 恒定时间。 对？ 像，什么是运行时间 做任何事情，只需一次 操作中，像打印˚F的Hello World。 可能被说成是恒定时间， 除非少的角落情况下与印刷楼 什么可能的运行时间 打印˚F实际上是？ 为什么？ 什么是在这种情况下，N测定？ 听众：[听不清]。 DAVID J.马兰：没错。 的字符数 我们要打印。 所以这是非常上下文敏感。 今天，我们已经集中了很多 信件和这里的板号。 但它也可能是 字符的实际字符串。 因此，原来还有另一种 此举将开始关心， 这就是相反的 大O的，可以这么说。 这是欧米茄符号。 而大O表示什么，该 上界的运行时间？ 最大限度，多少时间 可能需要的东西？ Omega--很抱歉，这保持未来 up--是那相反， 由此它的上下限 时间的东西量可能需要。 所以。比如，什么是算法 这需要始终ñ平方的步骤？ 那么，的算法之一，我们已经看到 今天，事实上，可能是为好。 选择排序。 选择排序是非常愚蠢的。 即使算法 - 对不起，连 如果数组已经排序， 选择排序是要 保留通过列表走 以确保其具有最小 元素一次又一次又一次。 而且即使你们人类的 观众知道，等一下， 你已经通过了 最小的元素，所述计算机 不知道，直到它看起来 通过列表中的所有方法。 同样，一个下界那 也可能考虑到 可能是线性时间。 多少时间没有考虑到 在最好的排序n个元素 如果使用像冒泡排序？ 假设你的名单已经排序。 我们说，冒泡排序发生在 n的平方顺序步骤。 但是，如果它已经排序？ 如果你以后意识到什么 一次通过阵列 你所做的没有掉？ 您是否需要继续做更多的通行证？ 第 因此，一个下界冒泡排序 可以说是线性的。 欧米茄的n。 我们可以看一下 这些其他人。 因此，让我们快速浏览一下 在短短这里的可视化 怎么看这些脱颖而出。 我要在这里下到这 网页是可在C50的网站， 但是这将是一个痛苦的得到工作， 由于它使用一个所谓的技术 Java小程序，这是一个 主要是不支持的，这些天， 至少是Chrome和某些其他人。 让我继续前进，加速这一 并解释这是怎么回事。 这是气泡的示范 排序，第一种算法，我们看着。 而且它是在一个可视化的每 这些棒的代表编号。 越大了吧， 大的数目。 酒吧较小， 数字越小。 你可以看到在视觉上，甚至 虽然这是怎么回事超级快， 是红色的酒吧是像我这样的， 来回走动解决问题。 您可以看到更大的元素 确实冒泡到右侧， 和更小的元素 被向上冒泡到左侧。 而到这里，如果我们 实际上看起来更加紧密， 我们其实可以算 比较和交换的数量 ，目前正在。 但是，相反，让我们来看看 在第二算法 我们前面我们 志愿者，选择排序。 视觉上，它有一个 非常不同的影响。 但它，再次，非常直观，在 我们继续选择下一个最小 元素，我们得到了一点点运气。 这种感觉从根本上更快。 但是，如果我们跑这一次又一次 并再次用大量的投入， 我们可以看到，它的的确确 还是在n大O平方。 让我们做一最后一个 在这里，插入排序， 这是第三个算法 我们看了看，并召回 ，这其中涉及的 当它遇到这些元素， 但随后可能转变 事情交给腾出空间， 插入它们所属的元素。 而这也最终给 最终结果。现在，所有这三个的 感觉蛮快的。 事实上，我跑了他们 在一个相当不错的剪辑。 但从根本上来说，它们是 很可怕的，是诚实的。 所有这些算法迄今 在n大O的运行方 需要相当多的 时间到底运行。 事实上，我们可以看到 并认为这最后 如果我拉起来这第三次和最后的演示。 这是另一种 可视化这回事 显示冒泡排序在左边， 选择排序在中间， 有什么东西，作为我们的一个 一方面提高了早期的建议， 右侧归并排序。 分而治之 战略上的权利。 而这，其实就是我们 要看看在周三。 但是，让我们的时间，这些并行运行。 它是大致相同的数 元件，所有运行在同一时间。 冒泡排序VS选用 排序VS归并排序。 现在，他们都跑 在理论的同时。 该CPU在运行 同样的速度，但你 可以感觉到多么无聊，这是 很快将成为， 而究竟有多快时， 我们注入了一下周 零的算法可以 我们加快速度。 现在，让我们比较 这些在最后一个形式。 我要继续前进 到CS50的网站，在那里 我们今天这最后一环， 如果有人在互联网上 好心拼凑一个视频 抓住什么不同的排序 算法听起来像。 这是插入排序。 [哔哔] 因此你申请一个频率 基于该栏杆的高度。 这是冒泡排序。 [扭曲的哔哔声] 即将旁边is--未来 旁边is--选择排序， 在这里再一次，我们选择 下一个最小的元素， 我们可以看到它成长 从左至右。 合并排序，因此，今天我们获胜者为止。 请注意，它是如何划分的事情 进入[听不清]半和宿舍。 侏儒排序，我们有没有 谈起，并创建直观 和audally有点 不同形状和声音。 来回， 清理东西。 还检查了堆排序 在这个家伙的网站。 就是这样。 我们会看到你下一次。 [呼呼与音乐]