DAVID MALAN：好的。 我们回来了。 因此，在编程这一部分是什么 我以为我们会做的是一个事物的组合。 一，做一点点 东西动手， 虽然使用的是更好玩 编程environment-- 一个是示范的 正是种思路 我们一直在谈论， 而多了几分正式挂牌。 二，看一些 更多的技术途径 一个程序员实际上解决 像搜索问题的问题 我们看了前 也有更根本 排序的有趣的问题。 我们刚刚从一开始走假设 这是电话本进行了排序， 但仅凭这实际上是种 硬问题有许多不同的方式 解决它。 因此，我们将使用这些作为 一类问题 代表性的东西， 可能一般的解决。 然后我们再说吧 大约在一些细节什么 称为数据structures-- 奇的方法类似链表 和哈希表和树木 一个程序员实际上 使用一般采用 在白板上画 的画面是什么，他或她 设想用于实施 一些的软件。 因此，让我们做动手部分第一。 因此，只要把你的手脏了 环境调用s​​cratch.mit.edu。 这是我们使用的工具 在我们的本科班。 尽管它的设计 适合12岁及以上， 我们将其用于向上 那相当多的一部分 因为它是一个不错的，好玩的 学习图形化的方式 少了一些有关编程。 让头部的网址，在那里你 应该看到一个页面很喜欢这个， 并直接点击 在右上角加入划痕 并选择一个用户名和 密码并最终让自己 一个account-- scratch.mit.edu。 我以为我会以此为 第一次有机会展示这一点。 一个问题在休息的时候来到了 什么代码实际上样子。 和我们谈话 关于C在休息的时候， 在particular--特别是 在一个较旧的语言较低的水平。 而我只是做了一个快速 谷歌搜索找到的C代码 对于二进制搜索，算法，我们 用于早期的搜索该电话簿。 这个特殊的例子，当然， 不搜索电话簿。 它只是搜索一大堆 号码在计算机的存储器中。 但是，如果你想只得到一个视觉 什么实际的编程意识 语言的样子，看起来 有点像这样。 因此，这20多名， 30左右的行代码， 但我们的谈话 是具有超挖 是有关如何这实际上 被演变成零和一 如果你不能只是说恢复 处理和从零和一去 回代码。 不幸的是，该方法 如此变革 这是一个很多谈何容易。 我说干就干，居然变成 该程序，二进制搜索， 成的一个方式的零和一 程序调用编译器，我 碰巧的权利在这里我的Mac上。 如果你看一下屏幕 在这里，特别是重点 这些中间六列只， 你会看到只有零和的。 而这些都是在零和一的 究竟该组合搜索程序。 等五个位的每个块， 零和一的每个字节在这里， 代表一些指令 通常是计算机的内部。 而事实上，如果你听说过 营销口号“Intel Inside”的 - 即， 当然，只是意味着你有一个 在计算机内部的Intel CPU或大脑。 而这意味着什么是一个CPU是 你有一个指令集， 可以这么说。 世界上每一个CPU，很多 它们由英特尔这些天发， 了解有限 指令数。 而这些指令是如此之低的水平 因为这两个数字加在一起， 乘这两个数字加在一起， 从这里移动这一块的数据 这里在内存中，这种保存 从这里的信息存储器到这里， 所以forth--非常非常 低的水平，几乎电子信息。 但与那些数学 加之操作 与我们前面讨论的， 数据的表示 作为零和的，可 你建立起来的一切 一台计算机今天能做的，无论是 它的文本，图形，音乐， 或以其他方式。 所以这是很容易得到 迷失在快速的杂草。 而且还有很多的 语法挑战 因此，如果你做的最简单， 没有错别字方案的愚蠢 将任何工作。 因此，而不是使用 语言如C今天上午， 我认为这将是 更多的乐趣，真正做到 一些更直观，这 而专为儿童设计 实际上是一个完美的表现 实际编程 language--恰好 使用图片代替文字 代表这些想法。 所以一旦你确实有一个 帐户scratch.mit.edu， 点击创建按钮 在左上方的网站。 你应该看到这样一个环境 一，我要看到我的屏幕上 这里。 我们会花一点点 时间位在这里踢球。 让我们看看，如果我们不能全部解决一些 问题一起以下述方式。 那么，您会在此看到 environment--实际上只是让 我停下来。 有没有人不在这里？ 不在这里？ 好。 所以让我指出一些 这种环境的特点。 所以在屏幕的左上角，我们 有划痕的舞台，可以这么说。 刮不仅是名称 此编程语言; 这也是猫的名称 您可以通过在橙色默认情况下有看到。 他是在一个阶段，所以 就像我描述 龟作为较早在被 长方形的白板环境。 这种猫的世界完全局限 该矩形向上顶在那里。 同时，在右侧 这里右手边，它的 只是一个脚本区， 如果你将空白的石板。 这就是我们要去的地方写 我们在短短的时刻节目。 和基石，我们将 用它来写这个program--拼图 件，如果你will--是 那些在这里在中间， 他们正在分类 按功能。 所以，举例来说，我要继续前进 和展示的这些的至少一种。 我要继续前进，然后点击 控制类别向上顶。 因此，这些都是分类往上顶。 我要点击控件类。 相反，我要单击事件 类别中，最前面的一个往上顶。 如果你想沿着甚至跟随 因为我们这样做，你很欢迎。 我要单击并拖动这个 第一个，“当绿旗点击。” 然后，我会刚落 大约在我一张白纸的顶部。 什么是关于临时不错 是，这一块拼图，当 与其他拼图互锁 件，是要做到逐字 这些东西拼图要说到做到。 因此，例如，临时是右 现在在他的世界的中间。 我要继续前进，并选择 现在，让我们说，运动类， 如果你想要做的 same--运动类别。 现在我发现有一个整体的 一堆拼图这里 他们说什么，同样，那种事。 而且我要继续前进，拖放 降此举块就在这里。 并注意，一旦你得到 接近“绿色环保标志的底部 点击“按钮，通知 怎么会出现一条白线， 就好像它几乎 磁性，它想要去那里。 刚松手，它会捕捉 一起和形状将匹配。 现在你可以或许差不多 猜出我们这个打算。 如果你看一下划痕阶段 在这里，并期待它的顶部， 你会看到一个红色的灯， 停车标志和环保标志。 而且我要继续前进 看着我的screen-- 就一下，如果你能。 我要点击 绿色环保标志，现在， 他搬到这似乎是10个步骤 或10个像素，10个点，在屏幕上。 所以也不那么令人振奋， 但让我求婚 甚至没有教这个，就 用自己的自己intuition--让利 我建议你​​弄清楚如何 使刮走正确的扫尾阶段。 让他让路的右侧 屏幕，一路到右侧。 让我给你一个时刻 左右与搏斗。 你可能想看看 在其他类别的块。 好吧。 所以只是为了回顾一下，当我们有 绿旗点击这里 移动10步是 只有指令，每次我 点击绿色旗帜，是怎么回事？ 嗯，这是我的运行程序。 所以，我能做到这一点 也许手动的10倍， 但这种感觉有点 有点hackish，可以这么说， 因此我不是真的 解决这个问题。 我只是试图再次和 再，再而三 直到我有点意外 实现了指令 我提早出门来实现。 但我们知道我们的 伪早些时候有 这一想法在循环编程， 一次又一次地做一些事情。 于是，我看到了一堆你 达到什么一块拼图？ 重复，直到。 因此，我们可以做一些 喜欢重复，直到。 你是怎么重复，直到到底是什么？ 好。 让我去一个是 稍微简单一些只是一瞬间。 让我继续前进，做到这一点。 请注意，你可能有 控制之下发现， 有这种重复块，这 看起来并不像它的那么大。 这里没有多少空间 这两个黄色线之间。 但正如一些你可能有 注意，如果你拖放， 注意它是如何成长为填充形状。 你甚至可以塞进更多。 它只会保持增长，如果 拖动和悬停。 我不知道什么是 最好在这里，让我们 我至少重复五次，为 实例，然后再回到舞台 然后单击绿色标志。 而现在发现它并不令人信服。 现在，你们中的一些建议，如 维多利亚只是没有，重复10次。 而且一般不 得到他所有的方式， 但不会有成为一个更强大的 方式比任意搞清楚 有多少动作做？ 什么可能是一个更好的块 不是重复10次呢？ 是啊，为什么不能做一些事情永远不会消失？ 现在让我搬这个拼图 里面，远离之一。 现在注意无论身在何处划痕 开始，他去的边缘。 幸好麻省理工学院， 谁使划痕，只是 可以确保他从来没有 完全消失。 您可以随时抓住他的尾巴。 而就直观， 为什么他继续前进？ 这里发生了什么？ 他似乎已经停止，但 那么如果我拿起并拖动 他一直想要去那边。 这是为什么？ 诚然，一台电脑是从字面上 要做到你告诉它做什么。 所以，如果你告诉它前面做 永继的事情，移动10步， 它会一直走下去，去 直到我打红色停车标志 和完全停止该程序。 所以，即使你没有 做到这一点，我怎么会 使划痕移动速度更快 在屏幕上？ 更多的步骤，对不对？ 因此，而不是做10 在同一时间，我们为什么不 继续前进，改变中场休息 你会propose-- 50？ 所以现在我要点击绿色的 旗帜，而事实上，他也快。 与此，当然，只是 动画的一种表现。 什么是动画？ 它只是显示你的人一个 静止图像的一大堆真的， 真的，真的快。 所以，如果我们只告诉 他将更多的步骤， 我们只是有效果是 改变他在屏幕上 所有的更迅速的每单位时间的。 现在，我提出的下一个挑战 是让他反弹的边缘。 而且不知道什么谜 件exist--因为它的罚款 如果你没有得到的 在challenge--的阶段是什么 你想直观地做什么？ 我们如何要他反弹和 特征在于，在左右之间？ 是啊。 因此，我们需要某种 的条件下，与我们 似乎有条件句，所以要 控制类别下说话。 其中这些块 我们可能希望？ 是的，也许“的话，那么”。 所以注意到黄色块之中 我们这里有，有这个“如果” 或本“的话，否则”块会 让我们做出决定，这样做 或者这样做。 甚至你可以嵌套这些 做多件事情。 或者，如果你已经不在这里了呢， 继续前进，传感类 还有 - 让我们看看它在这里。 那么，什么块可能会有所帮助这里 检测如果他离开舞台？ 是啊，注意到一些，这些块 可参数化的，可以这么说。 它们可以排序的定制，而不是 不像HTML昨天属性， 其中，这些属性样的 自定义标签的行为。 同样在这里，我可以抓住这个动人 块与变化，提出这样的问题， 你去摸鼠标 指针像游标 或者是你接触的边缘？ 因此，让我进去，做到这一点。 我要缩小了一会儿。 让我抓住这个拼图 这里，这一块拼图这一点， 我要去混杂 它们只是一瞬间。 我要动这个， 改变这感人的优势， 我要去运动做到这一点。 因此，这里有一些成分。 我想我已经得到了我想要的一切。 会有人想提出我怎么 可以连接这些也许从上到下 为了解决具有的问题 刮动右向左向右 左到右到左，每 时间刚刚反弹的墙？ 我想要什么呢？ 哪个块我应该连接到 “当绿旗点击第一”？ 好了，让我们开始用“永远。” 善有善报，里面下？ 其他人。 OK，移动步骤。 好吧。 然后呢？ 所以后来的如果。 并注意，尽管它看起来 夹紧紧联系在一起， 它只会增长到填满。 它只是将跳在我想要它。 而我该怎么放的 IF和当时的？ 也许“是在触摸的优势。” 和通知，再次，它太大了 对于它，但它会增长到填满。 然后转15度？ 多少度？ 是啊，所以180会打滑 我所有的相反。 因此，让我们看看，如果我得到这个权利。 让我缩小。 让我拖刮了。 于是，他有点扭曲 现在，但是这很好。 我怎样才能轻松重置他吗？ 我要稍微作弊。 所以我又增加 块，仅仅是明确的。 我要他点90度 在默认情况下的权利， 所以我只是要告诉他 要做到这一点编程。 现在我们开始。 我们似乎都做到了。 这是一个有点古怪，因为 他走倒挂。 让我们把一个错误。 这是一个错误。 一个错误是一个程序，一个错误 逻辑错误，我的人，做。 他为什么会颠倒？ MIT有没有搞砸了还是我？ 是的，我的意思是，这不是麻省理工学院 故障。他们给了我一块拼图 上面写着转的度一定数目。 而在维多利亚的建议， 我转180度， 这是正确的直觉。 但转弯180度，从字面上 装置转动180度， 而这不是真的 我想要的东西，显然。 因为至少他在 这个二维世界， 所以转折点是真的 翻转他倒挂。 我可能要使用的块 相反，根据你所看到的吗？ 我们如何解决这个问题？ 是啊，所以我们可以点 在相反的方向。 而实际上，即使这 不会是不够的， 因为我们只能硬编码 指点左侧或右侧。 你知道我们能做什么？ 看起来我们有一个 便利块在这里。 如果我放大，看到 这是我们喜欢在这里？ 所以它看起来像麻省理工学院有一个 抽象建在这里。 此块似乎是等效 到其它块，复数？ 这一块似乎是等同 以块的这整个三人组 我们这里有。 因此，原来我可以简化我的 通过摆脱这一切的程序 而只是把这个在这里。 而现在，他仍然是一个小 越野车，而现在的罚款。 我们把它留给定。 但我的计划是，即使 简单，而且这也 会代表 在programming--目标 是理想使你的代码 简单，尽可能紧凑， 同时仍然为 可读越好。 你不想让它尽量简洁 这很难理解。 但是请注意，我把它换成 三个块一个， 那可以说是一件好事。 我抽象出来的​​概念 抽查不管你是 与仅一个街区的边缘。 现在，我们可以有乐趣与此，事实上。 这不会加那么多 知识产权价值，但顽皮的价值。 我要继续前进 在这里抓住这个声音。 因此，让我先走了，让我 停了片刻程序。 我要记录以下， 允许访问我的麦克风。 开始了。 哎哟。 让我们再试试这个。 开始了。 好吧，我录了错误的事情。 开始了。 哎哟。 哎哟。 好吧。 现在我需要摆脱的。 好吧。 所以现在我有一个 只是记录“哎哟”。 所以，现在我要去 进取，称之为“哎哟”。 我要回去 我的剧本，现在 通知有该块被称为 播放声音“喵喵”或播放声音“哎哟”。 我要去拖这一点，并在 我应该把这个滑稽的效果？ 是啊，所以现在它是一种 越野车，因为现在这个block-- 注意如何“如果边缘， 反弹“是一种自成体系。 所以，我需要解决这个问题。 让我继续前进，做到这一点。 让我摆脱这一点，回去 我们原来的，更深思熟虑 功能。 因此，“如果触及边缘，然后在”我想 转，维多利亚提出， 180度。 那我要玩 声“哎哟”呢？ 是啊，察觉到它的外 那个黄色的块状。 因此，这也将是一个 错误，但我已经注意到了这一点。 所以我要在这里拖起来， 并注意现在是里面的“如果”。 因此，“如果”这算哪门子 像臂形印迹 那唯一的打算 做什么是它里面。 所以，现在，如果我缩小在 annoying--的风险 计算机：哎哟，哎哟，哎哟。 DAVID MALAN：它 只是永远持续下去。 现在只是加快东西 在这里，让我去进取，不断开拓， 让我们say--让我去一些 从类我自己的东西。 让我开拓，让我们说，这 一个接我们的教学研究员之一制成 两三年前。 所以，有些人可能还记得 本场比赛从昔日的， 它实际上是显着的。 尽管我们已经做了 最简单的方案，现在， 让我们来考虑一下这个 实际上样子。 让我打比赛。 因此，在这场比赛中，我们有一个 青蛙，并使用箭头keys-- 他需要比我脖子了更大的步伐 我有过这种青蛙的控制。 其目标是跨越繁忙的获得 路不跑入汽车。 而让我要是在这里上去的see--，我 必须等待日志被滚动。 这感觉就像一个错误。 这是怎样的一个错误。 好吧。 我在这里这样， 在那里，然后你继续 走，直到你得到所有 青蛙的睡莲。 现在，这可能看起来 所有的更复杂， 但让我们尝试突破 下来弱智 并口头成其组件块。 因此，有可能是一个谜 我们还没有看到一块 但是这响应按键， 的事情我按下键盘上。 因此，有可能是某种 块说，如果key等于起来， 然后做一些Scratch-- 也许移动10步这种方式。 如果向下键，移动10步 这样一来，或者左键，将10个步骤 通过这种方式，10的步骤。 我已经清楚地变成猫变成了青蛙。 所以，这只是其中 服装，刮擦调用它 - 我们 刚刚导入的青蛙的图片。 还有什么是怎么回事？ 什么其他代码行， 还有什么其他拼图 布雷克那样，我们的教学老乡， 在这个程序中使用，显然是？ 什么是使一切move-- 什么编程构建？ 运动，sure--所以 移动块，肯定的。 而那是什么举动块 里面，最有可能的？ 是的，某种循环，也许 永远阻止，也许是重复block-- 重复，直到块。 这就是什么使日志和 百合垫和其他一切举动 来来回回。 这只是发生不休。 为什么有些车 移动速度比别人快？ 什么是关于这些程序有什么不同？ 是啊，也许他们中的一些正在服用 同时更多的步骤，其中一些 同时更少的步骤。 和视觉效果 快与慢。 你认为发生了什么？ 当我得到了我的青蛙一路 在街对面，河 到蕸，东西 值得一提的事。 什么，只要我这样做了？ 停了。 青蛙停了下来， 我得到了第二只青蛙。 那么，什么结构必须是 使用有什么功能？ 是啊，所以有某种 “if”条件在那里，太。 而事实证明out--我们没有看到this-- 但有在那里，其他块 可以说，如果你是感人 屏幕上的另一件事， 如果你触摸蕸，“然后”。 然后那个时候我们 使第二只青蛙出现。 因此，即使这场比赛肯定是 很过时，尽管乍一看 有这么多的事情on--和布雷克 在两分钟内没有掀起这件事， 大概花了他几 小时创造这个游戏 根据他的记忆或视频 昔日的的版本吧。 但是，所有的这些小事 要在隔离的屏幕上 归结为这些很简单 constructs--运动或声明 就像我们已经讨论过，循环和 条件，这就是它。 还有一些其他鸽友功能。 其中有些是纯粹的 审美或声， 喜欢的声音我只是打了。 但在大多数情况下，则 没有这个语言，从无到有， 所有基本的 积木您 在C，Java的，JavaScript中， PHP和Ruby，Python和 和任意数量的其他语言。 关于临时有问题吗？ 好吧。 所以我们不会在更深的下潜划伤， 虽然你这个周末是受欢迎的， 特别是如果你有孩子，或 侄女和侄子这样， 向他们介绍划伤。 它实际上是一个奇妙的俏皮 环境，因为它的作者说， 天花板很高。 尽管我们开始 非常低层次的细节， 你真的可以做相当多的 用它，这或许是 正好一个示范。 但是，让我们现在过渡到一些 复杂的问题，如果你愿意， 称为“搜索”和 “排序”，更普遍。 我们必须在这里先前已经本电话簿的 另一只为discussion-- 我们能够搜索 更有效，因为 的一个显著假设。 而仅仅是明确的，是什么 假设是我做 通过这个电话本搜索时？ 迈克·史密斯在 电话本，虽然我 将能够处理 没有他场景 还有，如果我只是提前停止。 这本书是按字母顺序。 这是一个非常慷慨 假设，因为这 意味着someone--我有点 切割角， 像我，因为有人快 别人做了很多艰苦的工作对我来说。 但是，如果手机 本书是不排序？ 也许Verizon的偷懒，只是把 每个人的姓名和电话号码在那里 也许在顺序他们 签署了电话服务。 多少时间，它带我 找一个像迈克·史密斯？ 1000页的电话book--多少 网页做我不得不通过看？ 他们全部。 你是那种倒霉。 你从字面上来看看每 如果电话簿只是页面 随机排序。 你可能会得到幸运，找到迈克 书的第一页上，因为他 是第一个客户 订购电话服务。 但他可能是最后一次了。 所以随机顺序并不好。 因此，假设我们要排序 电话簿或一般的数据排序 我们一直在考虑。 我们怎样才能做到这一点？ 那么，就让我只是尝试 这里一个简单的例子。 让我继续前进，折腾 在黑板上几号。 假设我们有是数字， 比方说，四，二，一，三。 而且，本，这些数字对我们进行排序。 OK，不错。 你怎么做到的？ 好吧。 因此，与最小的开始 值和最高的， 这就是真正的好直觉。 并意识到我们 人类实际上是相当 善于解决问题 这样，至少 当数据是比较小的。 一旦你开始有上百 数字，数千数字， 数以百万计的数字，大概奔 不能做到这一点想象中的那么快， 假设有 中的数字的空白。 很容易数到一百万 否则，只是费时。 所以算法听起来 像本现在用刚 是搜索的最小数目。 因此，即使我们人类可以采取 在大量的信息可视化， 计算机实际上是 多一点有限的。 计算机只能 看一个字节在一个时间 或在一个时间 - 也许四个字节 在时间 - 这些天，也许8个字节 但极少数 的字节在给定的时间。 因此，考虑到我们真的有 四个单独的值这里 - 你能想到奔具有 对，如果他是一个计算机，例如一叶障目 他看不到任何其他 不是在时间 - 一个号码 所以我们一般会认为，像 英语中，我们将从右至左读。 因此，第一个数字奔大概看了 在四岁，然后很快 意识到是一个相当大 number--让我继续寻找。 有两项。 等一下。 二是超过四个小。 我会记住。 现在二是最小的。 现在one--那就更好了。 这是更小。 我要忘了约两 ，只是记住一个现在。 而且他可以停止寻找？ 嗯，他可以根据 该信息， 但他最好的搜索 列表的其余部分。 因为什么，如果是零列表中？ 如果负一人在列表中？ 他只知道，他的回答 是正确的，如果他的详尽 检查整个列表。 所以，我们看一下这个休息。 Three--那是浪费时间。 倒霉的了，但我是 还是正确的这样做。 所以现在他大概 选择的最小的数 而只是把它开头 名单，因为我会在这里做的。 现在，你做了什么接下来，即使 你不想想近 到这个地步？ 重复这个过程， 所以某种循环。 有一个熟悉的概念。 因此，这里是四人。 这是目前国内最小的。 这是一个候选人。 不再。 现在，我已经看到了两个。 这是下一个最小的元素。 Three--那不是更小，所以 现在本可以挖出两个。 而现在我们重复的过程中， 当然3下一个被拉出。 重复上述过程。 四个被拉出。 而现在我们出数字， 因此列表必须被排序。 事实上，这是一个正式的算法。 计算机科学家会 称之为“选择排序” 这个想法是一个排序 再次列出iteratively-- 一次又一次选择 的最小数字。 而且它是什么太好 它只是这么混账直观。 它是如此简单。 你可以重复同样的 连连操作。 这很简单。 在这种情况下，它是速度快，但 多长时间居然拿？ 让我们把它似乎并 觉得有点单调乏味。 所以一，二，三，四，五六百， 七，八，九，十，十一，十二，十三，十四， 15，16--任意数。 我只是想这多 时间不仅仅是四个。 所以，如果我有一个整体 一串数字now--它 甚至没有关系 他们are--让我们 想想这 算法真的是喜欢。 假设有数字存在。 再次，什么都无所谓 他们，但他们是随机的。 我申请本的算法。 我需要选择最小的数字。 我该怎么办？ 而我要去物理 做这次表演出来。 寻找，寻找， 寻找，寻找，寻找。 只有时间我去 列表的末尾可以 我意识到最小 根数为两根这个时候。 一个不是在列表中。 于是，我放下了两项。 我该怎么做？ 寻找，寻找，寻找，寻找。 现在我找到了七位数，是因为 有这些numbers--差距 只是随心所欲。 好吧。 所以，现在我可以放下七人。 展望寻找，寻找。 现在我假设的 当然，这本不 有额外内存，额外 存储器，因为，当然， 我期待在相同的号码。 当然，我可以记得 所有这些数字的， 这就是千真万确的。 但是，如果本·记住所有 数字的，他已经看到， 他还没有决定 根本的进步 因为他已经有 搜索能力 通过主板上的号码。 记住所有的 数字没有帮助， 因为他依然可以作为一台电脑 仅看，我们已经说过了，一个号码 在一个时间。 因此，有没有那种骗 那里，你可以利用。 因此，在现实中，如我 继续搜索列表， 我简直要只是不停 通过来回，采摘出来 下一个最小号。 正如你可以种推断 从我的愚蠢的动作， 这只是变得非常 乏味的速度非常快， 我似乎回去和 第四，来回还真不少。 现在是公平的，我没有去 作为比较，好了，让我们see--是公平的， 我不必走很 每次尽可能多的步骤。 因为，当然，我 从列表中选择号码， 剩下的名单也越来越短。 因此，让我们想想 其实，我要走多少步是 通过每个疲惫地走时间。 在第一次的情况 我们有16个数字， 所以maximally--我们只是 对于discussion--做到这一点 我不得不通过16看 编号，以找到最小。 但是，一旦我拔光了 最小的数，如何 长得其余名单，当然，？ 只有15。 那么有多少数字做本或我有 通过第二次左右看？ 15，只是去寻找最小。 但现在，当然，列表是， 也小于以前。 那么有多少步骤，做了我 必须采取下一次？ 14，然后13，然后12，加点， 点，点，直到我留下了只有一个。 所以，现在的计算机科学家会 问，好，是什么人人平等？ 这实际上等于一些具体 数字，我们当然可以 做算术，但是我们要谈 关于算法的效率 多一点通过公式， 独立的列表是多久。 所以，你知道吗？ 这是16日，但就像我之前说的， 我们只需要调用这个问题的规模 n，其中n是一些数字。 也许是16，也许这是 三，也许这是一个亿。 我不知道。 我不在乎。 我真正想要的是 一个公式，我可以 使用比较算法 与其他算法 有人可能声称 是好还是坏。 因此，原来，只有我 从小学知道这一点， 这实际上工程以相同 事为n在N加一两岁多。 而这恰好相等，的 当然，N的平方加N超过两。 所以，如果我想要一个公式 有多少步 参与看着都 连连这些数字的 一次又一次，我会说 它n值的平方加N超过两。 但是，你知道吗？ 这只是看起来凌乱。 我真的不想一个 的东西一般意义。 你可能还记得，从 高中有 是最高阶术语的概念。 其中这些条款，第n 的平方，在n或半 随着时间的影响最大？ 更大的n变，这 这些问题的是什么？ 换句话说，如果我插 中了一千万，N平方 将是最有可能的 的主导因素， 因为一百万次 本身是大了很多 比加一个附加万元。 所以，你知道吗？ 这是多么大的混账 号，如果你一个平方数。 这其实并不重要。 我们只是十字架 并忘掉它。 所以，一个计算机科学家会说 该算法的效率 为n的量级squared-- 我的意思是真正的近似值。 它是那种大约N个平方。 随着时间的推移，做大 和更大的n变，这 是什么一个很好的估计 效率或缺乏效率 这种算法实际上是。 我推导出，当然， 从实际上做数学。 但现在我只是挥手 我的手，因为我只是 希望这种算法的一般意义。 因此，使用相同的逻辑，同时， 让我们考虑另一种算法 我们已经看到at--线性搜索。 当我搜索 为手机book-- 不选它，搜索 通过电话book-- 我们一直在说，这是 1000步，或500步。 但是，让我们笼统地说。 如果有n个网页 电话本，有什么 运行时间或 线性搜索的效率？ 它的顺序 多少个步骤，找到 用迈克·史密斯线性搜索，该 第一算法，或者甚至第二？ 在最坏的情况下，麦克 是在书的末尾。 因此，如果电话本有1000页， 我们说最后一次，在最坏的情况下， 它可能需要大致有 很多网页找迈克？ 像1000。 这是一个上限。 这是最坏的可能发生的情况。 但同样，我们正在走 从1000像现在的数字。 这只是ñ。 那么什么是合乎逻辑的结论？ 在电话找到麦克 书中有n页 可能需要在很​​最坏的情况下， 有多少n的顺序步骤？ 的确计算机 科学家会说 正在运行的时间，或 性能和效率 或低效率的算法类的， 线性搜索是n的量级。 我们可以采用同样的 穿越出来的东西逻辑 因为我只是做了第二个 算法中，我们曾与电话本， 在这里我们去一次两页。 因此，1000页的电话本可能 带我们500翻页，加一 如果我们加倍回位。 因此，如果一个电话本有n个网页，但 我们正在做的一次两页， 这大概是什么？ ñ了两个，所以这是如N超过两。 但我做了一个索赔 刚才是n超过two-- 这是一种相同的是仅仅局限于N。 这只是一个常数因子， 计算机科学家会说。 让我们只专注于 变量，真的 - 公式中的最大变量。 所以线性搜索，无论是做了一个 在同一时间或页面同时两页， 是那种基本上是相同的。 它仍然是n的顺序。 但是，我有我的照片早前声称 该第三算法不是 线性的。 它不是一条直线。 它是弯曲的线，且 代数公式有什么呢？ N--的日志记录这样的n基地二期。 而且我们没有进入过 今天对数的细节， 但大多数计算机科学家不会 甚至告诉你基础是什么。 因为这一切都只是 持续性因素，可以这么说， 只是轻微的数值差异。 因此，这将是一个非常普遍的 对于这样特别正式的计算机 科学家在一次董事会或 在白板程序员 其实这争论 算法，他们将使用 还是什么效率 他们的算法。 这未必是 你在任何伟大的详细讨论， 但一个优秀的程序员是谁家 谁拥有了坚实的，正式的背景。 他能操 你在这种方式 ，实际上使 定性的论据， 为什么一种算法或 一个软件 在某些方面，以另一种优越。 因为你肯定能 只要运行一个人的计划 和计数的秒数 花费一些数字排序， 你可以运行一些 其他人的计划 和计数数 几秒钟需要。 但是，这是一个更一般的方式 你可以用它来分析算法， 如果你愿意，只是 纸张或口头刚。 甚至没有运行它，没有 甚至还试图采样输入， 你可以通过讲道理了。 所以，与聘请开发商或者 有他或她之类的争论给你 为什么他们的算法，他们的秘密 酱搜索数十亿美元 的网页为您的 公司是更好的，这些 是种参数它们 最好应该能够做出。 或者至少这些都是 这样的东西 这将拿出讨论，在 起码在一个非常正式的讨论。 好吧。 因此，本建议的东西 所谓的选择排序。 不过，我要提出有 这样，太的其他方式。 我真的不喜欢 有关本的算法 是他继续往前走，或 有我走，来回 和来回和来回。 如果不是我是做 像这里这些数字 和我只处理每 数字又因为我给它？ 换句话说，这里的 我的号码列表。 四，一，三，二。 而且我要做到以下几点。 我要插入的数字 属于他们的地方，而 比选择它们一次一个。 换句话说，这里的四个号码。 这是我最初的名单。 我要去维护 实际上这里的新列表。 因此，这是旧的列表。 这是新的列表。 我看到的数字四个第一。 我的新列表最初是空的， 因此它是平凡的情况下 四个现在什锦列表。 我只是把我提供的电话号码， 而我把它在我的新名单。 这是新的列表排序？ 是啊。 这是愚蠢的，因为只有一个 元素，但它绝对排序。 没有什么不合适的。 这是更有趣，这种算法， 当我移动到下一个步骤。 现在我有一个。 因此，人们当然，属于在 开始的时候还是这个新的列表的末尾？ 开始的时候。 所以，我现在要做的一些工作。 我已经采取了一些 我的标记自由 通过只绘制的东西 在这里我想他们， 但是这不是真的 准确在计算机中。 一台电脑，因为我们知道，有 RAM或随机存取存储器， 这就是一个字节， 另一个字节一个字节。 如果你有一个千兆字节 RAM，你有十亿字节， 但他们身在一个位置。 你不能只是移动的东西左右 通过绘制在黑板上 哪里都行。 所以，如果我的新名单有 在内存四个地点， 不幸的是，四是 已经在错误的地方。 因此，要插入的头号 我不能只是画在这里。 此存储器位置不存在。 这将是欺骗，我一直 形象地欺骗几分钟 这里。 所以真的，如果我想提出一个在这里， 我不得不暂时复制四个 然后把一个人也没有。 这很好，这是正确的， 这是技术上是可行的， 但知道这是额外的工作。 我不只是把数字到位。 我首先要移动 号码，然后把它放到地方， 让我有种我一倍的工作量。 所以记住这一点。 但我现在有了这个元素来完成。 现在，我要抢位列第三。 其中，当然，它属于？ 在这两者之间。 我不能再骗 ，只是把它放在那里， 因为，再一次，这种记忆 在物理位置。 所以我要复制四个 并把三个在这里。 没什么大不了的。 这只是一个额外的步骤 again--感觉很便宜。 但现在我移动到两个。 这两个，当然，属于这里。 现在你开始怎么看 工作可以堆积起来。 现在，我有什么做的？ 是的，我要搬到四， 然后，我有三个拷贝， 现在我可以插入两个。 而赶上这个 算法，有趣的是， 是，假设我们有一个更极端 情况是假设八，七， 六个五，四，三，二，一。 这一点，在许多情况下， 最坏的情况下， 因为混账东西 简直是倒退。 它并不真正的 本影响的算法， 因为Ben的选择 排序他要保持 来回通过列表。 而且，因为他总是在寻找 通过整个其余列表 没关系 其中元件是。 但是，在这种情况下，我插 approach--让我们试试这个。 这样一，二，三，四， 五，六，七，八。 一二三四， 五，六，七，八。 我将采取八， 和我在哪里把它？ 好吧，在我名单的开始， 因为这个新列表进行排序。 我把它划掉。 我在哪里把七？ 该死。 它需要去那里，所以 我必须做一些复制。 而现在的七个放在这里。 现在，我移动到六人。 现在，甚至更多的工作。 八就到这里去。 七就到这里去。 现在的六个可以去这里。 现在我抢五。 现在八已去 在这里，七就到这里去， Six于这里走， 现在五，重复动作。 而且我非常 不断移动它。 所以最终，这个算法 - 我们将 把它插入实际上类别 - 有很多工作了。 这只是不同 实物比本的工作。 Ben的工作已让我相信 来回所有的时间， 选择下一个最小的 连连元件。 所以这是这个极具视觉方面的工作。 此其它算法，这仍然是 correct--会得到这份工作done-- 只是改变的工作量。 它看起来像最初你 节约，因为你只是 处理每个元素 前面不走所有 通过列表像本的方式了。 但问题是，尤其是在这些 疯狂的情况下，这一切都反了， 你是那种只 推迟的辛勤工作 直到你有修正自己的错误。 所以，如果你能想象这 八七十六加五 后来四加三和二 在列表中移动自己的方式， 我们只是改变了 工种我们正在做的。 而不是在做 开始我的迭代， 我只是在做它在 每次迭代结束。 因此，事实证明，这种算法， 同样，一般称为插入排序， 也是为n的平方的数量级。 它实际上是没有更好的， 没有更好的。 但是，有一个第三个方法 我会鼓励我们考虑， 这是这样的。 因此，假设我的名单，为简单起见 再次，为四，一，三， two--只有四个数字。 本有很好的直觉， 良好的人的直觉 之前，由我们解决了整个 列出eventually--插入排序。 我哄我们一起。 但是让我们考虑 解决这个列表最简单的方法。 未排序此列表。 为什么？ 在英语中，解释原因 它实际上没有进行排序。 是什么意思不进行排序？ 学生：这不是连续的。 DAVID MALAN：不是顺序。 给我一个例子。 学生：把它们的顺序。 DAVID MALAN：OK。 给我一个更具体的例子。 学生：升序排列。 DAVID MALAN：不按升序排列。 更精确。 我不知道你的上升是什么意思。 怎么了？ 学生：最小的 号码是不是在第一空间。 DAVID MALAN：最小号的 未在第一空间。 更加具体。 我开始流行起来。 我们计算，但 什么是坏了吗？ 学生：数值序列。 DAVID MALAN：数值序列。 每个人的一种保管的 它这里 - 非常高的水平。 只是从字面上告诉我什么 错误就像一个五十岁的威力。 学生：加一。 DAVID MALAN：那是什么？ 学生：加一。 DAVID MALAN：你的意思是加一？ 给我一个不同的五十岁。 怎么了，妈妈？ 有什么不对，爸爸？ 你是什​​么意思这是没有排序？ 学生：这是不正确的地方。 DAVID MALAN：什么是 不正确的地方？ 学生：四。 DAVID MALAN：OK，好了。 因此，四是不是哪里它应该是。 特别是，这是正确的？ 四一，第一 两个数字我明白了。 这是正确的吗？ 不，他们不按顺序，对不对？ 其实，现在想想 关于计算机了。 它只能看看也许有， 在once--也许两件事 实际上只做一件事 的时间，但它可以至少 看一件事则 紧挨着它未来的事情。 所以这些都是为了？ 当然不是。 所以，你知道吗？ 我们为什么不带宝贝 步骤解决这个问题 而不是做这些花哨 算法，如奔，其中 他用那种固定它 通过该列表循环 而不是做我做什么，在哪里 因为我们去我只是一种固定的呢？ 我们只是从字面上打破 order--数字顺序的概念， 调用它不管你want-- 在这些两两比较。 四一。 这是正确的顺序？ 因此，让我们解决这个问题。 一和四，然后 我们只是复制。 好吧，好了。 我固定的一到四。 三加二？ 没有。 让我说的话我的手指相匹配。 四加三？ 这不是为了，所以我打算 做一，三，四两。 OK，不错。 现在，四个和两个？ 我们需要解决这个问题了。 这样一，三，二，四。 因此，它是排序？ 没有，但它是更接近排序？ 这是因为我们解决了这个 错，我们修正了这个错误， 我们修正了这个错误。 因此，我们只有三种错误可以说。 仍然没有真正审视排序，但 它客观上更接近排序 因为我们修正了一些这些错误的。 现在我该怎么做？ 我有种到达列表的末尾。 我似乎已经固定 所有的错误，但没有。 因为在这种情况下，一些数字 可能已经接近向上冒泡 其他数字， 还是乱序。 因此，让我们做一遍，我会 只是做的地方这个时候。 一个和三个？ 没关系。 三加二？ 当然没有，所以让我们改变这种状况。 所以，二，三。 三，四？ 现在，让我们只是 尤其是迂腐在这里。 难道排序？ 你们人类知道它的排序。 我应该再次尝试。 所以奥利维亚提议我再试试。 为什么？ 因为计算机没有 我们人眼的奢侈 只是一眼back-- OK，我完成了。 如何计算机确定 该列表现在排序？ 机械。 我应该通过 一次，且仅当我 不做/发现任何错误我可以 然后得出结论：随着计算机，是的， 我们是好去。 所以一和二，二和 三，三，四。 现在我可以明确地说，这是 排序，因为我不需要做任何改变。 现在，这将是一个错误，只是 如果我愚蠢，电脑， 又问那些相同的问题 期待不同的答案。 不应该发生。 所以现在的列表进行排序。 不幸的是，运行时间 该算法也可为N的平方。 为什么？ 因为你有n个数，并在 最坏的情况下，你必须移动n个数 n次，因为你必须坚持下去 回查和潜在的修复 这些数字。 我们可以做的更 正式的分析了。 所以这是大家说，我们已经采取了 三种不同的方法，一是 他们立即直观 关闭距离Ben蝙蝠 我的建议的插入 排序这个 在这里你那种忽视 林为最初的树木。 不过，如果你退一步， 瞧，我们已经解决了分拣概念。 因此，这是，敢说， 一个较低的水平也许 比一些其他的 算法，但让我们 看看我们能不能​​想象 这些通过这种方式。 因此，这是一些很不错的 软件，有人 使用丰富多彩的酒吧这是写 要做到以下几点我们。 每个这些棒的代表编号。 德勒酒吧，大 数目，更小的吧， 数越小。 因此，最好我们希望有一个漂亮的金字塔 它开始时很小，并得到大， 这将意味着 这些酒吧进行排序。 所以我要继续前进，选择， 例如，本算法 序曲一选择排序。 并注意它在做什么。 他们选择的方式 想象这个算法 是的，就像我是 通过我的名单散步， 这一计划是走 通过其号码列表， 突出每个粉红色 它在看数字。 什么是关于现在发生？ 最小数 我还是奔突然发现 被移动到列表的开头。 并注意他们做了逐出 这是有数字， 这就是完美的罚款。 我没有进入详细程度。 但是，我们需要把 这个数字的地方， 所以我们只是把它移到 已创建空位。 所以，我要加速这一 起来，因为否则它 变得非常乏味迅速。 动画speed--我们走吧。 所以，现在同样的原理 我申请，但你 可以开始感受算法，如果你 会的，或者看它多一点清晰。 并且该算法具有的效果 选择下一个最小的元素， 所以你要开始 看到它坡道在左边。 并在每次迭代中，我 提出的，它确实有点不太工作。 它没有走一路 返回清单的左端， 因为它已经 那些知道的排序。 因此，那种感觉就像是 加速，即使每个步骤是 取的时间相同。 这里还有剩余更少的步骤。 现在你可以种感受 算法清理它的结束， 实际上现在它的排序。 所以插入排序是全部完成。 我需要重新随机阵列。 并注意我可以 保持它随机化， 我们会得到一个近似 同样的方法，插入排序。 让我慢下来到这里。 让我们开始，超过。 停止。 让我们跳过四人。 在那里，我们走了。 他们随机排列。 在这里，我们go--插入排序。 玩。 请注意，它在处理每 元素遇到向右走， 但是，如果它是属于在 放错了地方的通知 所有这些都发生在工作。 我们必须保持更多的转移 和以上的元素，以腾出空间 对于一个我们要到位。 因此，我们专注于 仅列表的左端。 请注意，我们甚至还没有看at--我们 在粉红色的东西都没有突出 在右边。 我们只是处理 这些问题，因为我们去， 但我们创造了很多 为自己的工作依然。 所以，如果我们加快这 现在去完成， 它有不同的感觉确实如此。 这只是专注于左侧，但到底 做一个小更多的工作作为needed-- 一种平滑的事情 过去，固定的东西， 但最终处理 每个元素一次一个 直到我们到达曲风很好，我们 都知道这是怎么回事结束， 所以这是一个有点或许给人留下深刻印象。 但清单中end-- spoiler--将被排序。 因此，让我们来看看最后一之一。 我们不能只是现在跳过。 我们快到了。 二去，一去。 瞧。 优秀。 所以，现在让我们做最后一人一个， 再以随机冒泡排序。 并注意这里，尤其是如果我慢 下来，这也保持俯冲通过。 但是请注意，它只是使成对 comparisons--排序当地的解决方案。 但是，只要我们得到 在粉红色的列表的末尾， 什么将不得不再次发生？ 是的，这将有 重新开始，因为它只 固定配对错误。 和可能已揭示还有一些。 所以，如果你的速度这件事，你会 看到的是，多顾名思义， 较小的elements--或者说， 大elements--开始 泡到顶部，如果你愿意。 和较小的元素是 开始气泡向下到左侧。 事实上，这是一种 视觉效果为好。 所以这将结束整理 在一个非常类似的方式，也是。 我们不必纠缠 在这个特别的。 现在让我开这个。 还有一些其他的排序算法 在世界上，几其中 在这里拍摄的。 尤其是对学习者谁不 一定视觉或数学， 因为我们以前那样，我们可以 也做到这一点audially 如果我们完善与此相关联。 而只是为了好玩，这里有一个 几个不同的算法， 特别是其中一个你 要注意的是所谓的“合并排序”。 它实际上是一个根本 更好的算法， 这样归并排序，一 你即将看到的那些， 不是n阶平方。 它的n倍登录的顺序 N，这实际上是小的，因此 比其他三个更快。 而且还有其他的一对夫妇 傻那些我们拭目以待。 所以在这里，我们去一些声音。 这是插入排序，如此反复 它只是处理的元素 因为他们来。 这是冒泡排序，所以它的 考虑到他们在同一时间对。 再次，最大的元素 被鼓泡到顶部。 接下来选择排序。 这是Ben的算法，其中 他再次选择的迭代 下一个最小的元素。 再次，现在你真的可以听到 它加快了，但只有在目前为止 因为它做的越来越少 在每次迭代运行。 这是一个更快，归并排序， 这是排序的数字集群 在一起，然后将它们结合起来。 所以look--左 一半已经排序。 现在它的分选的右半和 现在它打算将它们合二为一。 这就是所谓的“侏儒排序。” 你可以种看到 它会来回， 一点点在这里固定的工作， 那里之前它进入新的工作。 就是这样。 还有另外一种，这是 真的只是为学术目的， 所谓的“愚蠢的排序，”这需要 您的数据，随机进行排序， 如果是排序，然后检查。 如果不是的话，它重新排序它 随机，检查它是否排序， 如果不重复。 在理论上，概率性 这将完成， 但经过相当多的时间。 这还不是最 高效的算法。 因此，对这些有任何疑问 特殊的算法或任何 相关那里吗？ 好了，现在让我们梳理出什么都 这些线，我一直在画 什么我假设电脑 可以引擎盖下做的。 我认为，所有这些数字 我一直drawing--他们需要得到 某处存储在存储器中。 现在，我们要摆脱这个家伙了。 所以在一块内存 computer--所以RAM DIMM是 我们搜索了昨天，双 列直插式内存module--看起来是这样的。 并且每个这些小的黑色芯片 是一定数量的字节，一般。 然后将金销仿若 它连接到计算机电线， 和绿碳化硅板仅仅是 是什么让一切都在一起。 那么，这究竟意味着什么？ 如果我有点画这个同样的画面， 让我们假设为简单 这DIMM，双 列直插内存模块， 是的RAM一千兆的一千兆字节 记忆，这是多少字节总数是多少？ 一千兆是多少字节？ 比那更多的。 1124是公斤，1000。 米加是万人。 GIGA是一个数十亿。 我在撒谎？ 我们甚至可以读取标签？ 这实际上是128 千兆字节，所以它的更多。 但我们会假装这 仅仅是一千兆字节。 因此，这意味着有一个十亿 提供给我的内存字节 或8十亿位，但我们要 在字节方面谈现在， 向前进。 所以，这是什么意思是，这是 一个字节，这是另外一个字节， 这是另外一个字节， 如果我们真的想 要具体我们将不得不 画一个十亿的小广场。 但是，这是什么意思？ 好吧，让我放大 在这张图片。 如果我已经得到的东西看起来 现在这个样子，这是四个字节。 所以，我可以把四个数字在这里。 一二三四。 或者，我可以把四个字母或符号。 “嘿！”可以去那里， 因为每个字母， 我们前面所讨论的， 可以表示 用八位或ASCII或一个字节。 所以，换句话说，你可以 把8个十亿里面的东西 的记忆这一棒。 现在，这是什么意思把东西背 备份内存来支持这样吗？ 这是一个程序员 称之为“阵列”。 在计算机程序中，你不觉得 关于底层硬件本身。 你只是觉得自己的作为有 访问十亿字节总， 你可以任何你想做的事情。 但为了方便 这是一般有用 保持你的记忆权 彼此相邻这样。 所以，如果我放大this-- 因为我们肯定不会 画一个小十亿squares-- 让我们假设这个委员会代表 的内存棒了。 而我就画多达我 标记结束了在这里给我的。 所以现在我们有一棒 对板载内存 那种有一，二，三，四，五， 六个一，二，三，四，五，六， seven--所以42字节 存储器上的屏幕总。 谢谢。 是的，我做算术的权利。 所以42字节的内存在这里。 那么，这实际上意味着什么呢？ 那么，一个计算机程序员 实际上一般 认为这种内存寻址。 换句话说，每一个这些 在存储器位置，在硬件， 具有唯一的地址。 它不是一体布​​拉特尔复杂 广场，剑桥，马萨诸塞州，02138。 相反，它只是一个数字。 这是字节数为零，这是 之一，这是二，这是三个 这就是41。 等一下。 我想我说42刚才。 我开始在零算起， 所以这实际上是正确的。 现在我们不必实际绘制它 作为一个网格，如果它画成网格 我觉得其实事情 会有点误导。 什么是程序员， 在他或她自己的头脑， 一般认为这 内存就像磁带， 像一块遮蔽胶带 只是推移和永远 或者直到你耗尽内存。 所以，一种较为常见的方式绘制 而只是想想内存 会，这是字节零个，一个 两个，三个，然后点，小点，小点。 你总有这样的42个字节，甚至 虽然身体上它实际上可能 更多的东西这样。 所以，如果你觉得现在的你 内存因为这，就像磁带， 这是一个程序员再次 将要求的存储器阵列。 而当你想实际存储 东西在计算机的内存， 你一般做店里的东西 后端到背靠背到后端。 因此，我们一直在谈论数字。 而当我想解决问题 样四，一，三，二， 即使我只是画 只有数字四个一，三， 两个在板，而电脑会 真的有这样的设置在内存中。 而这将是旁边 两人在计算机的内存？ 那么，有没有答案。 我们真的不知道。 并且，只要该 电脑并不需要它， 它不必关心什么是下一个 该数字确实关心。 而当我在前面一台电脑说 只能看一眼地址的时间， 这是种原因。 不不同于记录 播放器和读取头 只能够看着某 槽在物理老派的纪录 在一个时间，同样地 可以在计算机的感谢 到其CPU和其 英特尔指令集， 其指令中 从存储器中读 或保存到一个memory-- 电脑只能看 在以时间 - 一个位置 有时它们的组合， 但在同一时间真的只是一个地点。 所以，当我们在做 这些不同的算法， 我不只是写在 vacuum--四，一，三，二。 这些数字实际上属于 某处物理存储器中。 因此，有小小的 晶体管或某种 下面的电子的 罩存储这些值。 和总共多少比特 现在参与其中，只是要清楚吗？ 因此，这是四个字节，或者 现在它的32位总。 因此，实际上有32个零和 那些组成这四件事。 甚至还有更多的在这里，但 再次，我们不关心这个。 所以，现在让我们来问另外一个 问题使用内存， 因为，在端 这一天是方差。 不管是什么，我们可能会做 的计算机上，在一天结束时 硬件仍是 同样的引擎盖下面。 我将如何存储一个字吗？ 那么，在一台电脑一个字像 “嘿！”将存储就是这样的。 如果你想要一个更长 一句话，你可以简单地 覆盖该说点什么 如“你好”，并存储在这里。 所以在这里，这contiguousness 实际上是一个优势， 因为一台电脑可以只 从右至左读。 但这里有一个问题。 在这个词的范围内， H-E-L-L-O，感叹号， 如何才能对计算机知道在哪里 字开始，这里所说的结束？ 在数字的情况下， 如何做电脑 不知过了多久序列 数字是或者它启动？ 哦，原来out-- 我们不会去过多 这个级别的detail-- 电脑在内存中移动的东西 从字面上这些地址的方式。 因此，在一台电脑，如果你 编写代码来存储的东西 喜欢的话，你在做什么 真正做的是打字 那记得在表达式 计算机的内存这话。 因此，让我做一个非常， 很简单的例子。 我要继续前进， 打开一个简单的文本程序， 我要去创造 一个名为hello.c的。 大多数的这些信息，我们 不会进入的很详细， 但我会写一 计划在同日而语， C.这是更为吓人， 我认为，不是从无到有， 但它的精神非常相似。 事实上，这些卷曲 braces--你可以种 想到了什么我只是做的了。 让我们做到这一点，其实。 当绿旗点击， 做到以下几点。 我想打印出“你好”。 因此，这是现在的伪代码。 我有点模糊的线条。 在C，这种语言我说 一下，这条线的打印打招呼 实际上变成的“printf”与 一些括号和分号。 但它是完全一样的想法。 而这种非常人性化 “当绿旗点击”变 在更为神秘的“INT主要作废。” 这确实没有映射， 所以我只是要忽略。 不过，花括号，如 弧形拼图这样。 所以，你可以种猜测。 即使你以前从未编程， 这是什么程序可能吗？ 可能是打印Hello 带有感叹号。 因此，让我们试试吧。 我要保存它。 而这又正是一个非常 老学校环境。 我无法点击，我不能再拖累。 我必须键入命令。 所以我想运行我的程序，所以 我可以这样做，喜欢的hello.c。 这是我跑的文件。 别急，我缺​​少的一个步骤。 什么了，我们说是一个必要的 步骤，如C语言？ 我刚刚编写的源 代码，但我还需要什么呢？ 是的，我需要一个编译器。 所以在这里我的Mac电脑上，我有一个 程序调用GCC，GNU C编译器， 这让我做this--转 我的源代码之中，我们会打电话给它， 机器代码。 我可以看到的是， 再次，如下，这些 是零和我 从我的源代码创建的， 所有的零和一。 如果我想运行 我的程序 - 它将发生 被调用的a.out为 历史reasons--“你好”。 我可以再次运行。 你好你好你好。 它似乎是工作。 但是，在某处意味着我 计算机的内存是词语 H-E-L-L-O，感叹号。 而事实证明，就像顺便说一句， 什么是计算机通常会 这样做，它知道在哪里 事情开始并end--它的 要在这里把一个特殊符号。 和公约是把 在单词的末尾数为零 让你知道它在哪里 实际上结束，这样你 不要让打印出越来越多 人物比你实际打算。 但这里的外卖，甚至 虽然这是相当神秘， 是它的最终 相对简单。 你被赋予某种磁带，空白 上，你可以写信空间。 您只需有一个 特殊符号，如随意 数字零，将在年底 你的话让计算机知道， 哦，我应该后停止打印 我看到了感叹号。 因为接下来的事情有 是零ASCII值， 或空字符作为 有人会调用它。 但有样的问题 在这里，让我们恢复 到了一会儿号码。 假设我这样做，事实上， 有数字数组， 并假设 节目我写的 就像一个档次书老师 和老师的课堂。 而这个程序可以让他或她 输入他们的学生成绩 在测验。 并假设学生得到 100他们的第一次测验，也许 像80上的下一个，那么一个 75，然后在第四测验90。 所以在这个故事这一点上， 数组大小四。 还有更绝的内存在 计算机，但该阵列，可以这么说， 是规模四。 假设现在老师要 分配第五测验的类。 好了，事情之一，他 或她将不得不做 现在是这里存储一个额外的价值。 但是，如果阵列的老师有 在这个程序中创建的大小的， 与阵列的问题之一是 你不能只是不断加入到内存。 因为如果有什么的另一部分 程序有单词“哎”就在那里？ 换句话说，我的记忆可以 用于在程序什么。 如果事先我输入的，嘿嘿， 我想输入4测验分数， 他们可能会去这里和这里。 如果你突然改变了主意 后来，说我想第五测验 分数，你不能只是 把它放在任何你想要的， 因为如果这个 存储器正在被使用 东西else--其他程序 或程序的某些其他特征 你正在运行？ 所以，你必须想提前 要如何存储你的数据， 因为现在你已经绘 自己变成一个数字角落。 因此，老师可能代替 编写一个程序时说 存储他或她的 档次，你知道吗？ 我要提出要求， 我写程序时， 我想零，一，二，三， 四，五，六，八年级总。 这样一，二，三，四， 五，六，七，八。 教师可以刚过分配 写他或她的节目时记忆 并说，你知道吗？ 我永远不会分配更多 不是在一个学期8测验。 这只是疯狂。 我永远也不会分配的。 使这样，他或她有 灵活存储学生的分数， 像75，90，也许一个额外的地方 学生获得加分，105。 但是，如果老师从来不 使用这些三个空格， 这里有一个直观的外卖。 他或她只是浪费空间。 因此，换句话说，有这 在编程中常见的权衡 在这里你可以分配 正是尽可能多的内存，只要你想， 它的好处是，你是超级 efficient--你不会被浪费 在all--但其缺点 是什么，如果你改变主意的时候 使用要存储方案 比你更多的数据原本打算。 因此，也许解决的办法是，那么， 编写程序以这样的方式 他们使用更多的内存 比他们实际需要。 这样，你就不会 运行到该问题， 但你是浪费的。 而更多的内存，你的程序使用， 正如我们昨天所讨论的，少 内存可用 对于其他方案， 你的电脑可能会降低越快 下来，因为虚拟内存。 所以，理想的解决方案可能是什么？ 欠清分似乎不好。 过度分配显得不好。 那么，什么可能是一个更好的解决办法？ 重新分配。 更有活力​​。 不要强迫自己选择 先验的，在开始的时候，你想要什么。 而且绝对不要过度分配， 免得你是一种浪费。 所以要实现这个目标，我们 需要抛出这个数据结构， 可以这么说，流连忘返。 还等什么程序员 通常会使用 被称为不是东西 数组，但一个链表。 换句话说，他或她会 开始思考自己的记忆 作为善良的形状，他们 可以通过以下方式绘制。 如果我想存储在一个数 一个program--所以它的九月， 我给我的学生进行测试;我想要 存储学生的第一次测验， 他们在它 - 我得到了100 要问我的电脑， 由我有计划的方式 写的，对于一个内存块。 我要去存储 在其100号，仅此而已。 然后，几个星期后 当我拿到我的第二个测验， 它的时间输入 在这90％，我准备 问电脑，哎，电脑， 我可以有内存另一块？ 这是怎么回事给我这个 记忆空块。 我打算把在90号， 但在我的程序以某种方式或other-- 我们不会担心 对于this--我需要的语法 以某种方式链接这些东西放在一起。 我将它们连起来用 看起来像这里的箭头。 出现的第三次测验， 我会说，哎，电脑， 给我的记忆另一块。 而且我要放下 不管是什么，像75， 我有这个链条 现在一起莫名其妙。 四测验到来，也许 这是朝着学期结束。 而到那个时候我的程序 可能是使用内存 所有的地方，遍布身体。 所以只是踢，我 要得出这样的规定 quiz--我忘了那是什么;一世 想也许80或something-- 来这里的路上。 但是，这很好，因为形象地 我要画这条线。 换句话说，在现实中， 在您的计算机硬件， 首次得分可能 在这里结束，因为它是 就在学期的开始。 下一个可能会在这里结束 因为时间有点已过 并且程序继续运行。 接下来的成绩，这是 75，可能是在这里。 而最后的比分可能是 80，这是在这里。 因此，在现实中，身体上，这可能是 你的计算机内存的模样。 但是，这不是一个有用的精神 范式的计算机程序员。 为什么要关注所在 赫克您的数据结束了？ 你只是想存储数据。 这有点像我们的讨论 早期绘制立方体。 为什么你关心什么 的角度为立方体 你怎么也得把画呢？ 你只想要一个立方体。 同样在这里，你 只是想成绩簿。 你只是要考虑的 此作为数字列表。 谁在乎它是如何的 在硬件中实现？ 因此，现在的抽象 在这里这张图片。 这是一个链表，如 程序员会调用它， 只要你有一个 名单，显然数字。 但它形象地联系在一起 通过这些箭头的方式， 所有这些箭头are--下方 油烟机，如果你好奇， 回想起我们的物理硬件有 地址零，一，二，三，四。 所有这些箭头就像一张地图 或指示，如果在那里90 is--现在 我计数。 零，一，二，三， 四，五，六，七。 它看起来像90处于 内存地址七位数。 所有这些箭头都是 就像一张小废 这是给予指示， 程序，说按照这个地图 去的位置七人。 在那里你会发现 学生的测验第二次得分。 同时，75--如果我继续这样， 这是七，八，九，10，11，12， 13，14，15。 这等箭头只是代表 一个地图存储位置15。 但同样，程序员一般不 不会在意这些细节。 而且在大多数所有的编程 今天语言，程序员 甚至不知道在内存 这些数字实际上是。 所有他或她必须关心的是 它们以某种方式连接在一起 在像这样的数据结构。 但事实证明，没有 让过于技术化。 但是，仅仅因为我们可以或许 买得起这里有这样的讨论， 假设我们重温 这里一个数组的这个问题。 让我们来看看，如果我们去后悔这里。 这是100，90，75，和80。 让我简要地做了这种说法。 这是一个数组，并且再次，在 阵列的显着特征 是所有的数据都回 返回到memory--回字面上 一个字节或者四个字节， 字节的一些固定数目之遥。 在一个链表，这是我们可以借鉴 这样，在底层谁 知道哪里的东西是什么？ 它甚至不需要流这样。 一些数据可能是 回左那里。 你甚至不知道。 所以用一个数组，你有一个 特征称为随机存取。 及什么随机存取装置是 计算机可以立即跳到 到在阵列的任何位置。 为什么？ 由于计算机知道 该第一位置是 零个，一个，两个，和三个。 所以，如果你想从去 这个元素到下一个元素， 你从字面上看，在 计算机的心思，只是增加一个。 如果你想要去的第三个元素， 只需添加one--下一个元素，只是 加之一。 然而，在该版本 故事的，假设 目前的计算机正在 在或处理的数量100。 你怎么下 年级成绩簿？ 你要取七 步骤，这是任意的。 要进入下一个，你必须 采取另一种八个步骤去15。 换句话说，它不是一个 数字之间一定的间隙， 所以它只是需要的 计算机更多的时间点。 计算机有要搜索 通过订单记录 找到你要找的内容。 因此而阵列往往是一个 快速的数据结构 - 因为你 可以从字面上只是做简单的算术题 并得到你想要通过添加一个， 为instance--一个链表， 你牺牲该功能。 你不能只从第一次去 第二至第三到第四。 你必须遵循的地图。 你必须采取更多的措施 获得这些价值，这 似乎是增加了成本。 因此，我们付出的代价，但什么是 该功能丹正在寻求在这里？ 什么链表 显然允许我们这样做， 这是的原点 这个特别的故事吗？ 究竟。 一个充满活力的大小吧。 我们可以添加到这个列表。 我们甚至可以缩小列表，因此 那我们只使用尽可能多的内存 因为我们其实是想等 我们永远都不会过度分配。 现在只要是真正挑剔的， 有一个隐藏的成本。 所以，你不应该只是让我信服 你认为这是一个引人注目的权衡。 这里有另一个隐藏的成本。 这样做的好处，是明确的， 是我们获得活力。 如果我想另一个元素，我可以 绘制和摆在那里的一个数字。 然后，我可以链接它 用图片这里， 而在这里，再一次，如果我 自己画到一个角落里， 如果别的东西已经在使用 这里的记忆，我的运气。 我自己画成​​角。 但是，什么是隐藏 在这张照片的成本？ 这不只是量 的时间，它需要 从这里到这里， 这七个步骤，然后 八步，这是一个以上。 什么是另一个隐藏的成本是多少？ 不仅仅是时间。 其他信息 要实现这个图象。 是啊，地图，这些小碎片 纸张，因为我把他们描述为。 这些arrows--那些不是免费的。 你知道computer-- 什么是计算机。 它具有零和一。 如果你想表示箭头或 图或一个数字，你需要一些内存。 所以其他的价格你 支付一个链表， 一个共同的计算机科学 资源，也是空间。 的确如此，所以常见的是， 权衡之中 设计软件工程 系统的时间和space-- 您的成分是二，二生 你最昂贵的成分。 这是我花费更多的时间 因为我要遵守这个地图， 但它也花费了我更多的空间 因为我要保持这种地图各处。 因此希望，因为我们已经种 在昨天和今天的讨论， 是的好处 将大于成本。 但是，这里没有明显的解决方案。 也许这是better-- 一拉快速​​和肮脏的， 作为贾巴尔先前已经提出 在问题扔存储器。 随便买更多的内存，少思考 好好的解决这个问题， 并解决它更简单的方法。 事实上更早的时候， 我们谈到了权衡， 它不是空间 计算机和时间。 它是显影剂的时间，这 是另一个的资源。 如此反复，正是这种平衡行为 试图决定其中那些事 你愿意花？ 这是最便宜的？ 这产生更好的结果？ 是吗？ 的确。 在这种情况下，如果你 表示在maps--号码 这些被称为在许多语言 “指针”或“地址” - 它的双空间。 这不一定是为双如果那样糟糕 现在我们只是存储号码。 假设我们被存储 在hospital--患者记录 所以皮尔森的姓名，电话号码， 社会安全号码，医生 历史。 这个盒子可能是多了， 更大，在这种情况 一个小小的指针的地址 接下来element--这不是什么大不了的事。 它是这样一个边缘 成本也没关系。 但是，在这种情况下，是啊，这是一个增加一倍。 好问题。 让我们来谈谈时间 有点更具体。 什么是运行时间 进行搜索这个名单？ 假设我想查询 通过所有学生的成绩， 有n值等级 在此数据结构中。 在这里，我们可以借 早期的词汇。 这是一个线性数据结构。 为n的大O是什么需要得到 该数据结构的末尾， whereas--，我们还没有看到 这before--数组给你 什么叫做固定的时间，这意味着 一个步骤或两个步骤或10 steps-- 没关系。 它是一个固定的数目。 它无关 该数组的大小。 和其中的原因， 再次，是随机接入。 电脑可以立即刚 跳到另一个位置， 因为它们都是一样的 从一切距离。 没有涉及的想法。 好吧。 所以，如果我可以，让我尝试 画两个最终的照片。 一个非常常见的被称为哈希表。 所以激励的讨论， 让我想想如何做到这一点。 那么这个怎么样？ 假设该问题 我们现在要解决 在dictionary--正在实施 所以一大堆英文单词 管他呢。 和目标是能够回答 形式的问题，这是一个字？ 所以，你想实现 拼写检查，只 像物理字典 ，你可以看看东西英寸 假设我是用一个数组来做到这一点。 我能做到这一点。 并假设的话是苹果 和香蕉和哈密瓜。 而且我想不出水果 即开始研发，所以我们只是 将有三种水果。 所以这是一个数组，我们 存储所有这些词 在本词典作为数组。 现在的问题，那么，是怎么回事 你能存储这些信息？ 好吧，我有点欺骗在这里，因为 每个字这些信件 真的是单个字节。 所以，如果我真的想成为 挑剔的，我真的应该 被除以成多 内存较小的块， 我们可以这样做。 但是，我们要碰上 同样的问题之前。 如果，因为韦氏或牛津 确实每year--他们添加单词 到dictionary--我们不 一定要画自己 与阵列的角落？ 因此，不是，也许是一个更聪明的方法 是把苹果在其自己的节点或箱， 因为我们会说，香蕉和 那么在这里，我们有哈密瓜。 而我们这些串起来的东西。 因此，这是该数组， 这是链表。 如果你不能完全看到，它只是 说“数组”，这表示“名单。” 因此，我们有相同的 确切的问题和以前一样， 因此我们现在有 活力在我们的链接列表。 但是，我们有一个相当缓慢的字典。 假设我要查找一个字。 这可能需要我的n大O字 步骤，因为这个词可能 是一路在年底 列表，像哈密瓜。 而事实证明， 在编程，排序 数据的圣杯 结构是什么 ，让你不断 时间像一个数组 但是仍然给你活力。 因此，我们可以有两全其美？ 事实上，也有一些是 称为哈希表 这可以让你做的正是 即，尽管近。 哈希表是一个票友 数据结构，我们 能想到的 一个array--组合 而我要画它 像this--和链表 我就画这样的在这里。 而办法的事情 作品如下。 如果这个now--哈希table-- 是我第三次的数据结构， 我想存储 在这句话，我不 只想存储所有的 也就是说背靠背背靠背。 我想利用一些 片的信息 有关会让词 我得到它，它的速度更快。 因此，考虑的话苹果 和香蕉和哈密瓜， 我特意选择了这些话。 为什么？ 什么样的根本 对三种不同？ 什么是显而易见的？ 他们开始与不同的字母。 所以，你知道吗？ 而不是把我所有的词语 同一个桶，可以这么说， 就像在一个大名单，为什么不 我至少尝试优化 并让我的名单1/26一样长。 一个引人注目的优化 可能是为什么不 我 - 当插入一个字 入这​​种数据结构， 到计算机的内存，为什么 不要我把所有的'一'字在这里， 这里所有的“B”字， 和所有的“C”字在这里？ 因此，这最终将一个苹果 这里，这里这里的香蕉，哈密瓜， 等等。 如果我有一个额外的 字like--什么其他？ 苹果，香蕉，梨。 有人认为水果的 与一个，b或c开始？ Blueberry--完善。 那就是要在这里结束。 因此，我们似乎有一个 稍微更好的解决方案， 因为现在如果我想 搜索苹果，我 序曲一我不只是潜水 进入我的数据结构。 我不潜入我的电脑的内存中。 我先来看看第一个字母。 这是一台电脑 科学家会说。 您散列到你的数据结构。 你把你的输入，这在 这种情况就像是苹果的一个字。 你分析它，看着 在这种情况下，第一个字母， 从而哈希处理。 散列是一个通用术语，由此 你拿东西作为输入 你产生一些输出。 并且，所述输出 情况是位置 要搜索，第一 位置，第二是地段，第三。 所以输入是苹果， 输出第一。 输入是香蕉，所述 输出应该是第二位。 输入是哈密瓜， 输出应该是第三个。 输入是蓝莓，该 输出应该再次成为第二位。 这就是可以帮助你拿 通过你的记忆快捷键 为了得到对话 或数据更加有效。 现在，这种潜在的减少了我们的时间 多达三分之一的26 因为如果你认为你 有尽可能多的“一”字为“Z” 单词作为“Q”字，这 是不是真的realistic-- 你将有跨越歪斜 在alphabet--的某些字母 但是，这将是一个增量 方法，确实允许 你去的话更迅速。 与在现实中，一复杂的 程序，世界的谷歌， 在天下 - 的Facebook的 他们将使用一个哈希表 对于很多不同的目的。 但是，他们不会如此天真 光看第一个字母 在苹果或香蕉或 梨或哈密瓜， 因为你可以看到这些 名单仍然可以长期做下去。 所以这仍然可能是排序 的linear--所以有点慢， 像n的大O字 我们前面讨论。 那么什么是真正的好哈希表会 do--它将具有更大的阵列。 而且它会使用一个更 复杂的哈希函数， 因此，它不只是看看“一个。” 也许它着眼于“一个-P-P-L-e”和 不知何故这些转换五个字母 入位置，其中 苹果应存放。 我们只是天真地使用字母“A” 独自一人，因为它的简单好用。 但哈希表，在 最后，你能想到的 作为组合 阵列，其中每一个 有一个链表，理想 应尽可能的短。 而这不是一个明显的解决方案。 事实上，大部分的微调 该那张引擎盖下方时 实施这些种类的 复杂的数据结构 是什么是正确的 所述阵列的长度是多少？ 什么是正确的散列函数？ 你如何保存，留作回忆？ 但是，如何实现快速 这种讨论 升级，无论是到目前为止，它是一种 超过一个人的头部在这一点上，这 是罚款。 但是，我们开始回忆，真 一些低级别和电子。 因此这又是本 抽象的主题， 在这里，一旦你开始采取 理所当然的，好了，我已经得到了它 - 有 物理内存，好，我知道，每 物理位置有一个地址， 好吧，我知道了，我可以代表 这些地址为arrows-- 您可以非常迅速地开始有 更复杂的对话 到底似乎允许我们 要解决类似的问题搜索 和排序更有效。 放心吧，太... 因为我觉得这 是我们已经进入了一些最深 的proper--我们这些已经CS主题 在这一天半完成 点你通常会做主持 八周在一学期的课程。 对这些有问题吗？ 没有？ 好吧。 那么，我们为什么不停在那里， 午餐开始提前几分钟， 恢复只需大约一个小时？ 我会萦绕 有点用的问题。 然后，我将不得不去 采取一对夫妇的电话，如果这是确定。 我会在此期间开启一段音乐， 但午餐应该是指日可待。