[音乐播放]
好的
欢迎回来
这是CS50 这是第三周的最后一节课
回忆一下 在过去的几周中 我们
花了一些时间讲C语言 编程 以及语句
如果你还是觉得练习2有点困难
需要绞尽脑汁来做的话 这很正常
那些难懂的错误信息和bug
是挺难解决的
因为在几周后
你会回头看到Caesar, Vigenere加密法
然后意识到自己在短短时间内 学到了多少
所以如果这能安慰一下你们的话 现在再忍一下就好
不过在今天 我们会把难度提升一个档次
我们会开始默认你们已经知道怎样编程
或者至少对初级水平的编程已经比较熟悉了
我们会开始考虑 要怎样设计程序
来让它更好地运行
怎样才能让算法的效率最优
能解决更多有趣的问题
我们开始默认觉得 如果我们想的话
我们可以把想到的例子都用代码写出来
所以今天 我们不在键盘上写任何形式的代码
我们要往更高的层次上去 也就是终极目标 解决问题
为了达到这个目的 让我假设
这7个长方形代表7扇门 在它们后面
有一大堆数字 其中有一个是50
让我把这个投影到屏幕上
我提议 找一个志愿者来帮我
找到这个数字
请上台来 那位穿粉红色衣服的
好
你叫什么名字
[学生回答]
不好意思?
Jennifer
好的Jennifer
很高兴认识你
上台来
所以现在这里有7扇门 我想要你在你的同学面前
帮我们找到50这个数字
想要找到一个数字 你可以通过点击一扇门
来看到门后的数字
让我们看看你多快能找到50这个数字
15
16
50
很好
好的
掌声给Jennifer
[掌声]
好
所以你找50这个数字的策略是什么呢?
嗯 我想如果…
[学生回答]
哦
等一下
你找50这个数字的策略是?
我从最前面开始 看第一个数字是什么
然后我想 如果它们是排序好的
那我就按次序往上点击就好了
好
我们发现好像真的是这样
不过 让我们透过现象看本质
你能不能把你没选的门里的数字点开
哦 天
啊
所以我只是运气好
你只是运气好
好
所以 不错
但这个发现很有趣不是么
如果你假设 而且你真的运气比较好
如果你假设数字已经排序好
你能说的更清楚些 这会怎样影响到你的行动么?
如果它们是排序好的 我想也许是从小到大排的
哦
或者如果数字很大 那也许是从大到小排的
好
所以 从大到小 或者从小到大
但让我假设你没有这么好运
假设这些数字事实上没有被排好序
最坏的情况下 你要看多少扇门才能找到50呢?
所有的门
我们把这个叫统称为n
这种情况下 n是7 但是一般情况下 我们说
屏幕上有n扇门
所以在最坏的情况下 你得要看7扇门 或者是 n扇门
所以今天 真的是运气挺好的
但这其实是个线性算法 只不过你今天省了几步
这样说还准确么
是的
好 让我看看 如果我们看下一个例子
这里有7扇不同的门 你的策略会不会变
数字是一样的 但这一次 它们被分类了
这一次你的策略会是什么
试着不要想先前的数字--
好
--是什么
让我们从第一个开始
好的
从第一个开始
4
现在你要怎么做 以及为什么
4很小
所以如果它们是被分类好了的 也许是从小到大排的
那应该有这两倍--
好
让我们来看看 你觉得应该是哪个?
试试最后一个
很好
做得很好
好
[掌声]
好
找你上台太糟了
因为你做得太好了
这让我们很难完成教学目的
所以让我们倒带一点点
好
不过真的做得很好
你从第一个开始 你看到数字是4
然后你就去看了最后一个
但假设你没那么幸运
假设50并不在那
你第三步会怎么做?
回到最前面
所以你会点这扇门 这里面是8
好
这并不是50
你下一个会看哪里
如果我不知道它们是排序好的?
没错
不对 如果你知道它们是排好序了的
哦 知道 对
但你还不知道50在哪里
那就继续
好
继续
这样我就好办了
好
如果你这样继续的话
你的算法变成怎样的呢
线性--
变成某种线性算法
但让我来为难你一下
让我刷新一下
一样的数字 一样的排列 一样的门
但是回忆一下上课第一天
我们把一本电话黄页一撕两半 那时我们的策略是什么?
从中间开始
好
从中间开始
那就这我们来模拟一下这个过程
从中间开始 打开这扇门
是16
那个撕了书的人会怎么做呢?
下一个猜哪扇呢
到这一半中去
为什么去右半边呢
如果是按从小到大排列的 那
50应该在最后
好
这很合理
所以像电话黄页一样 你会去右半边 而不是左半边找
但这里是最重要的一点
你现在可以扔掉 或者撕掉一半的问题了
剩下的不是7扇门 而是只有三扇门
也就差不多是这个问题的一半
好
你去右半边之后 会做什么
16和50相比挺小的
所以也许我会试 这个
好
42
好 那现在你的直觉怎么说
我可以把这个扔掉然后--
好
很好 你可以把左边这部分扔掉了
--选这个
右边的
没错
所以虽然因为我们只有7扇门 所以不太明显
但是想像一下
你刚才用的这个算法的稳定性
在前一种情况下 你确实是运气好 这很好
但这里我会说 你确实用了一种启发式规则
你确实用到了你的直觉 你知道数字是排序好的
所以如果一开始数字很小 那很显然 我们要往右边走
但从某种意义上来说 你是运气好 因为也许这个数字会是100
也许50会靠中间
也许50会在这里
但这一次 不同的是
你是在重复做一件事
我会说 你刚才做的 虽然是受了撕电话黄页的影响
是一个有算法 有规则系统的事
而不是只针对某种特别情况
不像先前那么直觉性
所以归根到底 你会怎样比较
你的第一个算法 也就是从左到右
和你的第二个算法谁效率高呢?
这一种会把时间缩短一半 甚至更多
好 也许更多
让我们再多努力一把
如果我们延用这个逻辑 我们确实会把时间
缩短一半 因为我们把一半的数字都丢掉了
但是我们在进行第二次循环的时候 也就是当Jennifer
点开第二个数字的时候 我们做了什么呢
我们又把门的数量缩减了一半
如果我们还有更多的门的话 我们又会怎样呢
我们会再把它们的数量减半 然后再减半 再减半
这和你们在第一周的课上 大家都站起来
然后其中一半坐下 再一半坐下 再一半
直到只有一个人站着 是一样的
我们说了 这样运行的时间 要运行所需的步骤数
和什么有关
[学生回答]
以2为底n的对数 也就是 log n
所以是对数
而它的图形不是一条直线 随时间增加变得越来越糟
而是一条曲线 随时间增加 不会越来越糟
所以我们记住这一点
然后谢谢Jennifer
谢谢你上台来
等一下
今天没有台灯了 但我们有CS50的减压球
好耶
好的
谢谢你为我们增添了压力
好
现在让我们看看能不能把这个弄正式些
再一次 我们刚才做的
和我们在第一周做的其实是一回事
但是最后得到的 不是先前展示给大家看过的直线
也就是说 如果我们在屏幕后增加门的数量
那么Jennifer就得要去
多看一扇门
如果我们多添两扇门 她就可能要多看两扇门
所以说 问题的大小 也就是x轴 和
解决问题要花的时候 y
是线性相关的
但是我们先前讲到的是这条绿线
绿线显然表示 这种方案比较好
理论上来说 这个算法 也就是我们应对电话黄页的算法
我们数教室里有多少人的算法 刚刚的第二种算法
从根本上来说 要更优
因为它不是快两倍
它也不是快四倍
它快多少 完成取决于input的大小
也就是最终要花多少步
所以简单来说 我们解决电话黄页问题的思路
也可以应用到这个上面来
这种方法 也被人叫做
分治处理法
不是像我们去撕书那样
但是伪代码 是这样的
我们不会再做一次 但回忆一下 第一周
所有人都站起来 然后一半坐下 再一半坐下
这个算法运行时我们有作弊
因为不是我一个人
更有效率地在数数 我依靠了其他资源
就好像是多个CPU 多个大脑 多个聪明人
一起帮我去把线性的东西
变成对数的 把红的变成绿的
但在这里 Jennifer一个人 多想了一会儿
就把她第一次算法的表现提升了不少
现在 我们想要实现这个
那要怎样写代码 才能让它一直重复做某事呢
就像是循环一样
你们不会像Jennifer一开始一样
有这么多"如果"可以来假设 如果第一个数字是4
那就这我跳到最后去
如果那个数字太大 那就让我再移回去
到第二扇门去
你会发现 要去把人觉得非常合理的规则
程式化会有多难 但是电脑只会做
你叫它做的事
这其实非常有趣
这张图视觉上来看是有点乱
但是注意 直线在图中的什么地方?
我们叫做n的直线图在哪
差不多在图片的底部 对不对
我们做的 是从远处来观察x与y轴
来看其他的曲线长什么样
它其中数学上的细节 我们今天不用知道得太清楚
不过请注意 有很多其他的算法
比线性的东西还要糟很多
确实 n的三次方就挺糟的
2的n次方也挺糟 n的平方也是
我们会看到在现实世界 以上的情况会在何处出现
log n也不太糟了 但是以2为底n的对数 比n要好
但是 如果 Jennifer 或者我们在第一周时
就想到log n 的对数的话 那就更好了
换句话来说 解决问题有很多不同的方法
但在这里 注意会发生什么
当我缩小时 这些曲线中的哪一个
一定是最糟的?
n的三次方现在看上去挺糟的
但如果q 们缩小界面 看到更多的x与y轴部分的话
哪一个会是最糟的
事实上 是2的n次方 你可以通过
用越来越大的数字来试验 来证明
2的n次方确实 增长的速度最快
如果我们真的缩小很多的话 就会发现2的n次方真的很糟
我是说 它会让电脑花
很多时间来解决问题
但经过一段时间你们会愈发明白的 特别是在后面的练习中
以及最后的大作业中 你们的数据量是会变大的好么
在Facebook初代版本中 当朋友的数量
和注册用户的数量变大时
你可以用线性搜索
或是一个很简单的排序算法 就像我们今天看到的那样
你们要好好想想这些问题
Facebook Google和Microsoft这样的地方
会去想的 关于大数据的问题
这些问题近日吸引了很多人关注
好
Jennifer在第二个算法上的成功 说实话
她第一次就做得好极了 但是就让我们说那是因为运气好
这样我们就能表达一下这个观点
也就是 在第二次中 她用了一种算法
可以重复使用 但是她利用了我们告诉她的一个假设
去探索了一些细节
这是她在第一次没有做的
那是什么呢?
是这列数字是排序好的
当它们被排序后 我们就说 Jennifer
从根本上 可以做得更好
七扇门可能还不够有趣 但假如有700万扇门
从长远看log n一定会
要运行得快很多
但是 她需要有人帮她把门排序
现在 是我先前就去在屏幕上把它排好序了
但假如Jennifer需要自己做这件事呢
假设这些门代表的是数据库中的数据
或者是注册Facebook的人 或者是
网站会搜索到的任意网页
如果有人给你了一个未经处理过的数据集
或是给Jennifer 要你们来排序 会怎么样
这就需要我们回答这样一个问题
Jennifer 或者是我 来提前将这些数字排序
需要花多少时间?
是不是?
我们可以推测 去将这些数字排序
会花掉我不少时间 谁又会在意你能不能很快找到50这个数字呢
在Jennifer的情况里 事先排好序
会不会并没有帮我们省下太多的时间呢?
让我们看看能不能做个展示
我还有好多减压球
如果这能调动到大家的话
如果大家不介意 我们需要7位志愿者
好
哇
看来不用靠台灯招揽志愿者了
好
前面的这两位同学
还有 后面的这两位
这是四个人了
还有前面的第 5 6 7个
就是你
你的朋友们把你推举出来 所以你可以得到奖
好
上来吧
请站到这边
我们给你们每人一个数字
然后按屏幕上显示的
站好
[学生交谈]
唉呀 不好意思
Bug
好
好 现在可以了
数字5
数字6
1 2 3 4 5 6 7
这有点尴尬
我要--
好
好的
谢谢参与
[掌声]
好
我们有 4 2 6 1 3 7 5
太好了 我们有7位志愿者 这和我们先前在玩的数组
长度是一致的
我选择了7这个数字
是因为它会带来一些便利
我提议 我们先把这7位志愿者排好序
不过 如果你们想的话 可以先和大家打声音招呼
这将会是让人尴尬的几分钟
请你们一一自我介绍下
大家好 我是Grace
我大二 住在Leverett宿舍
大家好
我是Branson
大一 住在Weld
大家好
我是Gabe
大三 住在Cabot
我是Neil
大一 住在Matthews
我是Jason
大一 住在Greenough
我是Mike
大一 住在Grays
我是Jess
大二 住在Leverett
太好了
好
谢谢你们志愿上台来
现在我们面临的挑战是 怎样来排序
然后我们要好好想想
我们排序的方法效率有多高
我们先来试试这个
你们可以看见彼此的数字
那就请花点时间 自己排序下
从左到右 从小到大排列
开始
好
这真的很快
这边的同学 有谁能说说刚才他们用了什么算法?
从小到大
好
从小到大是我们的目标
但我不确定这是种算法
从小到大并不会告诉我 一步一步要怎样做
什么?
[学生回答]
好
如果你看见一个人 他的数字比你小
那就移到他右边
这样就更清楚一点了 更像个算法
因为你在说 如果怎样怎样 那就怎样怎样
所以我们有个像条件结构的东西
这些人好像做了几次 因为你们其中一些人
移动得挺远
所以 我们可以推测出 他们脑中是在进行某种循环的
但让我们尝试把它系统化
如果你们能重新回到这种排列
让我们看看能不能系统化这个进程 然后提出这个问题
这种方法效率到底有多高?
当然 当我们慢慢进行时 我们会觉得这好像不是一个很好的算法
但让我们看看我们能不能找到准确的步骤
所以你们俩分别是4和2
你们的顺序对不对呢?
显然不对
所以我们互换了
然后我会到这里 然后说 4和6
对还是不对?
对了
对
6和1
不对
换
所以现在换了2次
6和3
不对
换
6和7
看起来是对的
7和5
[学生回答]
好 换
这样就排好了
好
显然没排好呢 对不对
还有工作要做
但是 这些人 本能地
就继续移动位置了
他们在解决了一个问题后 并没有停下来
所以
我也得这么做
我要回到这个问题的开始
或者是回到这群人这个数组的开始
现在我要进行第二轮了 那我的算法是什么呢
还是一样
一样
我开始喜欢这个了 对不对
当你发现自己可以一遍遍做同样的事时
这就越来越像一个算法 还不是人类的本能了
所以现在 我们再来一次
2和4?
不用换
4和1 ?
所以确实 还有工作没做完
4和3?
好
4和6?
6和5？
6和7?
好 现在 完成了
好吧 还是没有
我还要再回去
现在 又一次 我们要更有意识地来做这件事
现在 只有一个大脑在运行这个算法
也就是 一个CPU
事实上 当我们回到键盘前
去用像C语言这样的东西时 这是我们能用到的唯一资源
我们就只是在写一个程序 它一次只能做一件事
但是 先前这些人 我们利用了他们的集体智慧
就像你们在第0周时那样
所以让我们继续
2和1
2和3
3和4
4和5
5和6
6和7
完成了么?
完成了 但让我扮一下魔鬼代言人
我 电脑 如果刚看了这一个数组的话
知道我自己已经完成工作了么?
不
为什么不呢
我要怎样 才能做出 我已经完成了 的结论呢
也许还要再过一遍
对不对?
因为过前一遍时 我只知道自己更正了一个错误
这意味着 也许还有错误
需要我来更正
所以我只能再重头检查一遍
1和2 2和3 3和4 4和5 5和6 6和7 才能确定
现在我什么也没做
我还记得我对一个像变量这样的东西 像是一个整数
没有进行任何处理
我叫它swaps(交换位置)如果从一开始没有交换位置 swaps是0
那我就很蠢地一直来回检查
一遍又一遍 对不对
因为你会陷在一个无限循环里
所以当交换位置次数为0时 我们就说
这个算法已经完成了
现在 让我们给它起个名
我提议的 并且我们完成了的这个算法
叫 冒泡排序法 也就是说 大一点的数字
就像泡泡一样升到上面去 或者说 升到这个数字数组的尾端去
但这个算法效率有多高呢
比如 我刚才做了多少步
才把这7个人排好?
4到5?
当然 答案最终可以是 太多步了
但这个具体的数字并不重要
让我们把它叫做n
如果我让n个人上来 然后一开始
他们是随机排列的
第一遍过去 我要做多少步
是 1 2 3 4 5 6 有7个人
是6步--所以第一遍是n-1步
当我再来一次时 要做多少步?
事实上我们可以把它乘2 但现在
我就说 好 再做n-1步
n-1计起来有点麻烦
就让我们四舍五入下
所以是2n步
所以大概是14步
那下一次 我要做多少步?
是3n步
是的
现在 在最坏的情况下
我要来回过多少次 来运行这个算法
让人们交换位置呢?
是n平方次 是不是
因为在最坏的情况下 你可以靠直觉猜出来
虽然可能要花点时间
在最坏的情况下 这7个人
会是怎样排列的呢?
完成反了 对不对
为了模拟那种情况 你叫什么名字来着
Mike
Mike?
好 Mike你可以同我一起站过来一下么
事实上 不要
不好意思Mike 让我们重新来过
你叫什么名字?
Neil
好 Neil 你能不能和我过来下 如果你不介意的话
我想提议 为了简便Neil现在
面临着他最坏的情况
但回忆下我是怎样进行我的算法的
我是在比较比较再比较
哦 这两个人顺序不对 然后我去改正
所以你俩交换位置
但现在想一下 Neil要走多远呢
大概是n
准确来说 不是n
应该是n-1 但我觉得这有点烦
所以我们就算是n吧
如果Neil一次最多只能移一位 而且为了让Neil移动
我得来回再过一遍的话
这就大概是 n步乘以n次
因为我要把Neil移到他应该待的位置 就要进行这么多次
还不算其他人 如果你们也被错误地排列的话
我们就说 冒泡排序法是n的平方
这个算法的运行时间 这个算法的表现
这个算法的效率
我们都可以用n平方来形容
这很方便 因为如果我用8个人9个人
100万个人来举例子 答案都不会变
所以如果你们不介意 请回来最初始的位置
让我们再试其他两种方法
来看看我们能不能做得更好
这一次 我提议 用一种不同的算法
上次 我们看得很明了
你们本能地就开始一对对进行位置交换
但是如果我想要简单地解决这个问题
把所有小的数字移到这边
把大的数字移到那边 那我为什么不试试最简单的办法
来看看会不会比刚才那个有点复杂的算法要好?
让我们来试试
4是个挺小的数字 那我就让你待在这
2更好
所以你能不能往前站一步?
这是我现在的 最小数字候选人
我要用 一个变量记住它
但我还要继续检查
还有没有更小的数字?
6 不对
哦 又到了Neil
概念上来说 我要把你推到后面去
Neil会到前面来
现在 我用来记录最小的数字的那个变量
已经更新了 它现在包含的是Neil的位置
让我们看下
3，7，5
我知道Neil是最小的
那现在我要做的 最简单的事是什么?
我不想浪费时间 只是把Neil冒泡向左边一位
我们为什么不把Neil放在他应该在的位置 也就是哪里呢?
最最前面这里
所以Neil 跟我来
你叫什么名字?
Grace
好
那么Grace 不幸的是 你好像挡到路了
所以我们要怎样解决这个问题?
嗯?
如果这是一个数组 里面只有7个位置
还记得 Rob的课里 我们讲过要声明年龄
而我们只有一定数量的年龄
这里也是一样
我们只有一定数量的整数
Grace好像挡到了路 那我们怎么办呢
最简单的方法是 Grace 对不起
你得挪到那儿去 给我们腾出位置
如果我们想一下 也许我们把问题弄得更复杂了
这是有可能的 因为 如果Grace本来就在正确的位置呢?
但我们知道她不在 因为如果是那样的话
她就应该站在前面 而不是Neil了 对不对
我们已经检查过她的数字了
好
现在 Neil在正确的位置了 我可以简单优化一下
下面 我要完全忽略Neil
这样就不要浪费时间 也不会不小心把他换到错误的位置去
那么现在 我要怎样才能找到除Neil外 最小的元素呢?
2
这个数字挺不错 你能不能向前一步
我会记得你的
6 不行
4 3 7 5 都不太行
那么就让我把你移到正确的位置去
我们这次很幸运
现在 我要忽略这两个人 然后再
重复过一次
6 这个数字还算小
上前来
哦 不好意思
Grace的数字更好 上前一步
4
不好意思Grace
请回去
数字3要更好
7
5
你叫什么名字?
Jason
所以现在Jason是我选中的最小的元素
他要做什么呢?
在6现在的位置
你叫什么名字?
Gabe
Gabe挡住了路
最简单的办法是什么?
让他们俩交换位置然后继续
所以让我们看看
谁最小?
4
让我作弊一下
5是最小的数字
我找到了 如果你可以向前一步
我要怎么处理这些人 和Gabe呢?
再交换一次
所以现在 顺序还是有点不对
我发现Gabe是最小的 所以我让他出来 把你们移到一边
这下好了
所以答案还是一样
最终结果是一样
这两种算法哪个更好呢?
我听到有人说第二种
为什么?
它用了n步…
它最多用n步
有意思
是这样么?
我是怎样找到最小的元素的?
我要找到最小的元素要花多少步?
我一直看到尾端 对不对?
因为最坏的情况下 如果Neil在最后面的话
所以光是找到最小的元素就要花我n步了 或是说 n-1步
但是 好
所以把Neil弄好了
记得大概在一分钟前
但我是怎么找到下一个最小的元素的?
我花了n-1 或者说是 n-2步
所以好的
我花了n-2步
好
这感觉要好一点了
好
我们找到数字3花了多少步?
n-4步
所以是在变少的 每次循环 会少一步
所以这个感觉要好一点对不对
如果上一种方法大概是n乘以n步的话 这次是n-1加
n-2加n-3加n-4……
但如果你还记得你的高中课表背后
总有一面写着所有的公式 如果你把这些数字加起来
那么我一共要花多少步呢?
是 n(n-1)/2步
让我看看能不能很快算出来
同样 为了简便 我会算个大概
但如果我算n-1 n-2
然后n-3的话 差不多就是这个除以2
如果我先乘好的话 差不多就是n平方
这个感觉不是太好 n平方-n/2?
但要记得
在计算机里 n越大时
问题才越有意思
当n真的很大时 哪个数字
会开始比其他的都重要?
n平方 对不对?
所以 除以2还是不错的
但如果我们关注的是以十亿、千亿记的数据
那么 你就有别人两倍快了
但谁又会关注这个数字
如果这一部分越来越大
而且当然 它比这边这个的影响要大
所以即使你们是对的 第二种算法
我们叫它选择法排序 在现实世界中 确实会更快
因为我每一次要用的步数都在变少
从根本上来说 它并没有变快
因为如果n真的很大的话
最终 如果n够大 它还是会很慢
让我最后再来试一种方法
刚才这一种叫选择排序法
你们能不能再一次回到初始位置去?
最后这一次 我要提议一种
叫插入排序法
插入排序 从概念上来说 有一点不同
它不是来回去找最小的元素
而是在遇见每个数字的时候 就挨个处理
把它们插入到正确的位置
所以我会从Grace开始 我看到她是数字4
数字4应该在哪里?
我还没有开始排序 所以Grace可以留在这个位置
现在我要声明 如果你可以往右一步
这是我排序好的 这是我还没排序好的部分
现在我要继续了 你叫什么名字?
Branson
Branson是数字2
那我要叫你出列一下
现在 你在这个数组里应该在哪?
在Grace右边
再一次 我们让Grace辛苦一下
我们要把你放在哪?
我们要把你往左移 然后要把Branson放这里
但现在我声称你们已经放好了
不过注意 我没有用到额外的空间
还是 2 个元素在这边 5个在那边
数组全长7位 所以我没玩花样 对吧
现在 我们这里有Gabe 是数字6 你应该在哪里?
你又走运了
你可以留在这
就稍微往右一步 这样让人知道你是排序好了的
现在我们又碰到了Neil 数字1 你要去哪呢
现在 我们就能开始看到这个算法
虽然可能初看时 觉得还挺聪明 但看一下接下来会发生什么
你可不可以往前一步
我们想把Neil放在哪?
当然是这里 那我们要怎样把Neil放那里呢
让我们一步一步来
Gabe 你要去哪
没错 跨一大步 或是两小步
到这边来
Grace 你要去哪
很好
又是一步
最后 Branson?
又一步
现在我们可以把Neil放进他的位置了
现在 延续这个逻辑
虽然我们没有把Neil移呀呀
移到他的位置去 最坏的情况下 我们看到的下一个数字
可能 比如说 下一个数字是0
那我们就要把这些人都移一遍
假如有-1这个数字 那我们又要
把所有人移一遍
所以我们其实是在把问题反过来
把选择的过程 变成了 插入的过程
也就是说 你们要移到n-某个数字
的步数
而这个数字 当我遇到越来越多的数字时 会不断增长
如果我们断把你们往后 再往后移
所以 让人伤心的是 所有这些算法都是n平方
让我们谢谢这些志愿者
然后用不同的方式来展示一下这个问题
做得很好
[掌声]
好的
这边走
感谢--
我们需要还回数字么
不用 你们可以留着这些数字
好
做得很好
好
现在让我们看看能不能更快地 从视觉上
来总结一下刚才发生的事
让我打开Firefox
我们会把这个展示的链接放到课程网站上
现在Java在一些浏览器上运行得不是太好
所以如果你们在家弄的话 你们可能要用Firefox
它才会运行
我下面要展示的是
在最底下 有一些菜单选择
包括一个 开始 和 停止 键
另外 这些程序里好像有个bug
当你不按住command或alt+键 然后放大
你是看不到开始和停止键的
所以就提醒你们一下 如果你们要在家试着玩的话
现在 我要点击开始键 然后我要规定延迟
大概200毫秒 这样我们就能看见发生什么了
这是第一种算法形象展示
冒泡排序法 也就是我们将人们一对对交换位置
理解这幅图的关键在于 这些柱的高度
代表了数字的大小
所以 柱越高 数字越大
柱越短 数字越小
如果你注意的话 我们在经过这种算法的第一次循环
将大的与小的数字交换位置 这样小的数字
就会在前面 而大的数字会在右边
当我们来到数组尾部 这次长度可不止是7位了
我们就回到最前边
预计一下 会发生这样的事
在最左边 这个小数字会被换到边上
这个过程不断重复
现在这个展示马上就变得无聊了
所以让我让它停下 把延迟调低点
这样就能感受一下这个算法了
虽然我已经让它加速了 这就你是升级我的处理器
买了台新电脑一样
我并没有从根本上改变我的算法 但你可以更清晰地看到
不像我们用人展示时那样 大的数字冒泡到了顶端
小数字冒泡到了底端
现在 这些数字排序好了
另外 在这些正方形里 这只是帮你保存记录
帮你数有刚才一共有多少次的比较
或者说发生了多少次位置交换
让我们再去试刚才看到的另一种方法
让我点击一下这里的冒泡排序法 然后让我选择
这个网页有点问题
我们就冒这个险 再运行
好了
让我们选选择排序法
我不知道为什么菜单从那边出来了
让我们放大一下 把这个bug修好 把这个改成50
让我们更快一点好了
5毫秒 然后 点击开始
这是选择排序法
所以又一次 想一想刚才我们用志愿者的时候发生了什么
我们检查整个数组 选择中最小的元素
一遍又一遍
我说这还是挺糟的
它依然是 n平方 但在真实在世界里
它确实快了一点 因为每一次 我确实都有少做一步
但我们在讲的
这里最多有 差不多40个柱子吧
我们不是在讨论 4000万
所以 我并没有很清楚地看到 提高了多少
让我回去 换成我们的第三种算法
我们选 插入排序法
现在真的问题很大 因为菜单不应该在下面这里的
让我回到上面 然后开始这个算法
开始 停止
这种算法的规律还挺妙的
像当时我们用志愿者一样 这里 我们是把柱子
插入到它们应该在的位置
然后这在我转身前就完成了
但这种算法 理论上 仍旧是n平方
所以让我们看看能不能将以上的总结一下
我要让我们有种简便的方法来讨论这些
所以让我介绍一个概念
你们马上会看到的 叫大O 因为它真的
就是一个很大的O 这是计算机科学家或是数学家
用来形容一个算法运行时间的方式
它到底要花多少步?
不好意思 我手写字很丑
但让我假装 这里的就会是大O
让我再介绍一个符号 大写的 omega
omega将会是大O的反面
big O表示 在最坏的情况下 用n表示 这个算法要花多少步
omega表示的是 最好的情况下
它要花多少时间
我们马上会看到 "最好的情况"是什么意思
让我们从简单的开始
让我从一个线性搜索开始
所以没有排序
我们叫它线性搜索
现在 用这个画出一张表
在线性搜索的情况下 如果是最糟的情形
我想要找到一个数字需要花多少步?
一共有n扇门 也就是n个数字
最坏的情况
我想要在一个有n扇门的数组里找到50这个数字
要花多少步?
n步 为什么?
因为也许我要一个个过一直找到最后
所以就像是Jennifer碰到的情况那样 50在很后面
所以我们说 线性搜索最坏的情况 是n的大O
那最好的情况又是什么呢 如果你真的很幸运的话
只会花一步 或者是一个常数
也就是1
这听上去挺不错
那如果我们做一个二进制搜索呢?
二进制搜索 在最坏的情况下 要花多少时间?
[学生回答]
所以事实上 我听到很多人给了我这个答案
事实上是log n步 因为当我们把它
一分为二 再分为二 再分 我们最终会找到那个值
如果这个值确实在那儿的话 但是有个地方要注意
我们进行二进制搜索 我们默认的前提是什么?
它必须是排序好的
如果它没有被排序 你可以不断把它一分为二
你可以在左边找 或是在右边找 或是左边右边一起找
但如果它没被排序 你是不会在其中找到那个元素
因为你可能过错过它
因为你用的这个规则 在左边还是右边找 如果没先排序好
就会是有问题的
所以要用这种方法的话 这个隐性的付出需要注意
现在 让我们来看我们的排序算法 而不是搜索--
哦 实际上 让我们来填一下这个空
二进制算法最好的情况?
还是1 如果正好是在数组的正中间的话
或者说 是电话黄页的正中间
现在让我们来做冒泡排序
又一次 我们看到的是排序法 还不是搜索了
在最坏的情况下 冒泡法要花多少步?
n平方
我把它画下来
我手写的东西被放大后 看起来更糟了
好
这是n平方
冒泡法最好的情况下 要花多少步?
1我听到有人说
n
n 我听到有人说
2
我听到有人说2
有人说是3么?
好
我听到有人说1 n 2 让我们先看看
第一个答案 1
直觉猜这个很合理 因为符合以上的规律
但是如果只要花1步的话 我要怎样才能确定
这个列表排序好了呢 因为如果我只能做一步的话
我能检查几个元素呢?
只有1个 也就是说 n-1个元素有可能都不在正确的位置上
而我只能靠信念 在检查了一个元素之后
就说这已经排序好了
所以1不是正确答案
所以我最少要看多少个呢?
[学生回答]
n-1个 或者说 n个 因为我需要看
所有的元素 来确定它们顺序都正确
但 我们把那个-1给去掉了 因为我们预设说
n越大 它们就越无趣了
这就是冒泡排序法
现在 让我们再做剩下的两个方法
选择排序法 然后是插入排序法
然后我们会用一个比它们好得多的方法
来让你们大吃一惊
好
选择排序法里最坏的情况要花多少时间
n平方
我听到有人说n平方
但为什么你说是n平方呢
因为我们刚才做过了
好
回答得好
但是直觉上来说 为什么选择排序法是n平方
我们要一次又一次地做什么呢?
我们要一停地扫描过去 问 你是最小的么
你是最小的么 你是最小的么
我们要花n步 然后是n-1 然后是n-2
但如果你把它们加起来
或者相信我已经提前加好了 我们大概会得到n平方减去一个很小的数字
所以我就算它是n平方
那么 选择排序法里的最好的情况下
要花我多少步呢?
[学生回答]
不幸的是 还是n平方 对不对
因为我是在选择最小的元素 而我们有7个人在这
我只知道 我要到最后面 才能找到最小的数字
无论她或他先前是在哪
但我要怎样找到次小的数字?
我要重新过一遍
所以在最好的情况下 选择排序法的input是什么
是一个已经排序好的表 1 2 3 4
但我是一个电脑
我一次只能看一样东西
我不能像人类一样 退后一步 然后说
哦 这个看上去顺序是对的
在选择排序法中 要让我宣布排序正确 我只能
去选择最小的数字
但就算我第一下就找到了数字1 我也不知道其他的数字是怎样
我只知道 有人给了我一个数组
或者是一组门 门后有数字 我想要知道 1是不是最小的数字
唯一的方法是
我要到最后 然后意识到 糟了 1确实是最小的数字
但我要怎样才能确定2是次小的数字?
我要再进行一次这种低效率的工作
所以最后 用插入排序法 最坏的情况
会是怎样?
还是n平方
那最好的情况呢?
我们在这留个悬念
下一次 我们会揭开谜底
但让我提议 我们要在根本上 做到更好 好不好
所以自己想一想 插入排序法会是怎样
好像并没有太戏剧化
因为我是唯一一个看到变化的人
哇
好
所以这里我们有了一个不同的展示
如果我在这边放大 你们会看到在左边 我们有冒泡法
在中间 我们有选择法 在最右边
是我们还没有讲到的 归并排序法
但想一下今天为止 我们都做了什么
当Jennifer上台来时 我们检查了这一数组的数字
一次 又一次 用的是线性搜索 然后我们得到了线性的运行时间
也就是n的大O
当我们现在来想我们课的第一周里 我们用了分治处理法
我们撕了电话黄页 同Jennifer 我们一起发现关键在于
不断重复你在做的事
不断地丢掉一半的问题
或者说 将问题分成两半 然后将更小的那一半
视作去另一半相同
这样 我们确实从根本上 有了提高
但是用冒泡法 选择法或是插入法
我们并没有像Jennifer那样发现关键
我们只是来来回回看来看去
改了一点小地方 交换了位置
可能进行了插入或者选择
但是总而言之 我很尴尬地来来回回很多次
我们并没有像Jennifer那样
聪明地去分割 去解决问题
所以 我们下周会讲到的归并排序法 正相反
利用了关键的一点 就是将input减半
减半 再减半
每一次经过循环 排序左半边 然后右半边
然后是左半边的左半边 然后是左半边的右半边
然后是右半边的左半边 然后是右半边的右半边
然后不断重复
你们会看到形象地展示的 但是会在下一周
总得来说 当我们仔细想一想这种问题后
我们在左边 有n平方 在中间也有n平方
在右边 有log n
这是真正留给你们的悬念
下周一见
[掌声]