1
00:00:00,000 --> 00:00:11,100
[音乐播放]

2
00:00:11,100 --> 00:00:11,490
好的

3
00:00:11,490 --> 00:00:12,170
欢迎回来

4
00:00:12,170 --> 00:00:15,180
这是CS50 这是第三周的最后一节课

5
00:00:15,180 --> 00:00:17,770
回忆一下 在过去的几周中 我们

6
00:00:17,770 --> 00:00:20,820
花了一些时间讲C语言 编程 以及语句

7
00:00:20,820 --> 00:00:24,680
如果你还是觉得练习2有点困难

8
00:00:24,680 --> 00:00:25,950
需要绞尽脑汁来做的话 这很正常

9
00:00:25,950 --> 00:00:28,310
那些难懂的错误信息和bug

10
00:00:28,310 --> 00:00:29,220
是挺难解决的

11
00:00:29,220 --> 00:00:32,310
因为在几周后

12
00:00:32,310 --> 00:00:35,930
你会回头看到Caesar, Vigenere加密法

13
00:00:35,930 --> 00:00:40,050
然后意识到自己在短短时间内 学到了多少

14
00:00:40,050 --> 00:00:43,670
所以如果这能安慰一下你们的话 现在再忍一下就好

15
00:00:43,670 --> 00:00:46,610
不过在今天 我们会把难度提升一个档次

16
00:00:46,610 --> 00:00:49,820
我们会开始默认你们已经知道怎样编程

17
00:00:49,820 --> 00:00:52,090
或者至少对初级水平的编程已经比较熟悉了

18
00:00:52,090 --> 00:00:56,520
我们会开始考虑 要怎样设计程序

19
00:00:56,520 --> 00:00:57,440
来让它更好地运行

20
00:00:57,440 --> 00:01:01,090
怎样才能让算法的效率最优

21
00:01:01,090 --> 00:01:03,110
能解决更多有趣的问题

22
00:01:03,110 --> 00:01:06,850
我们开始默认觉得 如果我们想的话

23
00:01:06,850 --> 00:01:08,350
我们可以把想到的例子都用代码写出来

24
00:01:08,350 --> 00:01:11,430
所以今天 我们不在键盘上写任何形式的代码

25
00:01:11,430 --> 00:01:15,150
我们要往更高的层次上去 也就是终极目标 解决问题

26
00:01:15,150 --> 00:01:20,490
为了达到这个目的 让我假设

27
00:01:20,490 --> 00:01:24,290
这7个长方形代表7扇门 在它们后面

28
00:01:24,290 --> 00:01:26,340
有一大堆数字 其中有一个是50

29
00:01:26,340 --> 00:01:30,470
让我把这个投影到屏幕上

30
00:01:30,470 --> 00:01:36,770
我提议 找一个志愿者来帮我

31
00:01:36,770 --> 00:01:38,140
找到这个数字

32
00:01:38,140 --> 00:01:40,755
请上台来 那位穿粉红色衣服的

33
00:01:40,755 --> 00:01:43,050
好

34
00:01:43,050 --> 00:01:43,930
你叫什么名字

35
00:01:43,930 --> 00:01:44,850
[学生回答]

36
00:01:44,850 --> 00:01:45,170
不好意思?

37
00:01:45,170 --> 00:01:45,860
Jennifer

38
00:01:45,860 --> 00:01:46,390
Jennifer

39
00:01:46,390 --> 00:01:46,980
好的Jennifer

40
00:01:46,980 --> 00:01:47,630
很高兴认识你

41
00:01:47,630 --> 00:01:48,370
上台来

42
00:01:48,370 --> 00:01:52,430
所以现在这里有7扇门 我想要你在你的同学面前

43
00:01:52,430 --> 00:01:56,560
帮我们找到50这个数字

44
00:01:56,560 --> 00:02:00,860
想要找到一个数字 你可以通过点击一扇门

45
00:02:00,860 --> 00:02:03,030
来看到门后的数字

46
00:02:03,030 --> 00:02:06,080
让我们看看你多快能找到50这个数字

47
00:02:09,979 --> 00:02:11,229
15

48
00:02:13,110 --> 00:02:14,360
16

49
00:02:16,270 --> 00:02:16,530
50

50
00:02:16,530 --> 00:02:17,350
很好

51
00:02:17,350 --> 00:02:18,040
好的

52
00:02:18,040 --> 00:02:19,906
掌声给Jennifer

53
00:02:19,906 --> 00:02:21,530
[掌声]

54
00:02:21,530 --> 00:02:22,320
好

55
00:02:22,320 --> 00:02:25,254
所以你找50这个数字的策略是什么呢?

56
00:02:25,254 --> 00:02:27,222
嗯 我想如果…

57
00:02:27,222 --> 00:02:27,714
[学生回答]

58
00:02:27,714 --> 00:02:28,206
哦

59
00:02:28,206 --> 00:02:29,630
等一下

60
00:02:29,630 --> 00:02:32,420
你找50这个数字的策略是?

61
00:02:32,420 --> 00:02:34,760
我从最前面开始 看第一个数字是什么

62
00:02:34,760 --> 00:02:38,590
然后我想 如果它们是排序好的

63
00:02:38,590 --> 00:02:39,970
那我就按次序往上点击就好了

64
00:02:39,970 --> 00:02:40,140
好

65
00:02:40,140 --> 00:02:42,910
我们发现好像真的是这样

66
00:02:42,910 --> 00:02:45,670
不过 让我们透过现象看本质

67
00:02:45,670 --> 00:02:47,640
你能不能把你没选的门里的数字点开

68
00:02:50,400 --> 00:02:51,712
哦 天

69
00:02:51,712 --> 00:02:53,128
啊

70
00:02:53,128 --> 00:02:54,280
所以我只是运气好

71
00:02:54,280 --> 00:02:55,270
你只是运气好

72
00:02:55,270 --> 00:02:55,710
好

73
00:02:55,710 --> 00:02:56,795
所以 不错

74
00:02:56,795 --> 00:02:58,750
但这个发现很有趣不是么

75
00:02:58,750 --> 00:03:01,870
如果你假设 而且你真的运气比较好

76
00:03:01,870 --> 00:03:05,350
如果你假设数字已经排序好

77
00:03:05,350 --> 00:03:08,750
你能说的更清楚些 这会怎样影响到你的行动么?

78
00:03:08,750 --> 00:03:11,715
如果它们是排序好的 我想也许是从小到大排的

79
00:03:11,715 --> 00:03:11,970
哦

80
00:03:11,970 --> 00:03:15,260
或者如果数字很大 那也许是从大到小排的

81
00:03:15,260 --> 00:03:15,540
好

82
00:03:15,540 --> 00:03:18,170
所以 从大到小 或者从小到大

83
00:03:18,170 --> 00:03:21,990
但让我假设你没有这么好运

84
00:03:21,990 --> 00:03:26,840
假设这些数字事实上没有被排好序

85
00:03:26,840 --> 00:03:28,590
最坏的情况下 你要看多少扇门才能找到50呢?

86
00:03:28,590 --> 00:03:29,860
所有的门

87
00:03:29,860 --> 00:03:30,420
所有的门

88
00:03:30,420 --> 00:03:31,740
我们把这个叫统称为n

89
00:03:31,740 --> 00:03:34,790
这种情况下 n是7 但是一般情况下 我们说

90
00:03:34,790 --> 00:03:35,650
屏幕上有n扇门

91
00:03:35,650 --> 00:03:40,110
所以在最坏的情况下 你得要看7扇门 或者是 n扇门

92
00:03:40,110 --> 00:03:44,140
所以今天 真的是运气挺好的

93
00:03:44,140 --> 00:03:46,440
但这其实是个线性算法 只不过你今天省了几步

94
00:03:46,440 --> 00:03:47,080
这样说还准确么

95
00:03:47,080 --> 00:03:47,500
是的

96
00:03:47,500 --> 00:03:50,000
好 让我看看 如果我们看下一个例子

97
00:03:50,000 --> 00:03:52,190
这里有7扇不同的门 你的策略会不会变

98
00:03:52,190 --> 00:03:55,240
数字是一样的 但这一次 它们被分类了

99
00:03:55,240 --> 00:03:58,350
这一次你的策略会是什么

100
00:03:58,350 --> 00:03:59,310
试着不要想先前的数字--

101
00:03:59,310 --> 00:03:59,930
好

102
00:03:59,930 --> 00:04:02,290
--是什么

103
00:04:02,290 --> 00:04:03,180
让我们从第一个开始

104
00:04:03,180 --> 00:04:03,540
好的

105
00:04:03,540 --> 00:04:05,190
从第一个开始

106
00:04:05,190 --> 00:04:05,960
4

107
00:04:05,960 --> 00:04:08,810
现在你要怎么做 以及为什么

108
00:04:08,810 --> 00:04:10,040
4很小

109
00:04:10,040 --> 00:04:12,500
所以如果它们是被分类好了的 也许是从小到大排的

110
00:04:12,500 --> 00:04:13,290
那应该有这两倍--

111
00:04:13,290 --> 00:04:13,670
好

112
00:04:13,670 --> 00:04:15,990
让我们来看看 你觉得应该是哪个?

113
00:04:15,990 --> 00:04:19,050
试试最后一个

114
00:04:19,050 --> 00:04:19,500
很好

115
00:04:19,500 --> 00:04:20,880
做得很好

116
00:04:20,880 --> 00:04:21,860
好

117
00:04:21,860 --> 00:04:23,010
[掌声]

118
00:04:23,010 --> 00:04:24,310
好

119
00:04:24,310 --> 00:04:26,790
找你上台太糟了

120
00:04:26,790 --> 00:04:27,700
因为你做得太好了

121
00:04:27,700 --> 00:04:31,150
这让我们很难完成教学目的

122
00:04:31,150 --> 00:04:32,565
所以让我们倒带一点点

123
00:04:32,565 --> 00:04:34,560
好

124
00:04:34,560 --> 00:04:35,980
不过真的做得很好

125
00:04:35,980 --> 00:04:39,060
你从第一个开始 你看到数字是4

126
00:04:39,060 --> 00:04:40,240
然后你就去看了最后一个

127
00:04:40,240 --> 00:04:42,320
但假设你没那么幸运

128
00:04:42,320 --> 00:04:42,890
假设50并不在那

129
00:04:42,890 --> 00:04:46,190
你第三步会怎么做?

130
00:04:46,190 --> 00:04:47,680
回到最前面

131
00:04:47,680 --> 00:04:48,320
回到最前面

132
00:04:48,320 --> 00:04:51,320
所以你会点这扇门 这里面是8

133
00:04:51,320 --> 00:04:51,660
好

134
00:04:51,660 --> 00:04:52,650
这并不是50

135
00:04:52,650 --> 00:04:55,380
你下一个会看哪里

136
00:04:55,380 --> 00:04:56,720
如果我不知道它们是排序好的?

137
00:04:56,720 --> 00:04:57,005
没错

138
00:04:57,005 --> 00:04:58,490
不对 如果你知道它们是排好序了的

139
00:04:58,490 --> 00:04:58,700
哦 知道 对

140
00:04:58,700 --> 00:05:00,910
但你还不知道50在哪里

141
00:05:00,910 --> 00:05:01,785
那就继续

142
00:05:01,785 --> 00:05:02,130
好

143
00:05:02,130 --> 00:05:02,520
好

144
00:05:02,520 --> 00:05:03,800
继续

145
00:05:03,800 --> 00:05:05,270
这样我就好办了

146
00:05:05,270 --> 00:05:05,610
好

147
00:05:05,610 --> 00:05:07,210
如果你这样继续的话

148
00:05:07,210 --> 00:05:09,680
你的算法变成怎样的呢

149
00:05:09,680 --> 00:05:10,740
线性--

150
00:05:10,740 --> 00:05:11,820
变成某种线性算法

151
00:05:11,820 --> 00:05:13,480
但让我来为难你一下

152
00:05:13,480 --> 00:05:14,900
让我刷新一下

153
00:05:14,900 --> 00:05:17,120
一样的数字 一样的排列 一样的门

154
00:05:17,120 --> 00:05:21,350
但是回忆一下上课第一天

155
00:05:21,350 --> 00:05:25,480
我们把一本电话黄页一撕两半 那时我们的策略是什么?

156
00:05:25,480 --> 00:05:26,450
从中间开始

157
00:05:26,450 --> 00:05:26,690
好

158
00:05:26,690 --> 00:05:27,610
从中间开始

159
00:05:27,610 --> 00:05:28,790
那就这我们来模拟一下这个过程

160
00:05:28,790 --> 00:05:30,720
从中间开始 打开这扇门

161
00:05:30,720 --> 00:05:31,660
是16

162
00:05:31,660 --> 00:05:35,290
那个撕了书的人会怎么做呢?

163
00:05:35,290 --> 00:05:38,450
下一个猜哪扇呢

164
00:05:38,450 --> 00:05:39,400
到这一半中去

165
00:05:39,400 --> 00:05:41,700
为什么去右半边呢

166
00:05:41,700 --> 00:05:43,900
如果是按从小到大排列的 那

167
00:05:43,900 --> 00:05:44,720
50应该在最后

168
00:05:44,720 --> 00:05:44,920
好

169
00:05:44,920 --> 00:05:45,390
这很合理

170
00:05:45,390 --> 00:05:48,380
所以像电话黄页一样 你会去右半边 而不是左半边找

171
00:05:48,380 --> 00:05:49,500
但这里是最重要的一点

172
00:05:49,500 --> 00:05:53,930
你现在可以扔掉 或者撕掉一半的问题了

173
00:05:53,930 --> 00:05:55,970
剩下的不是7扇门 而是只有三扇门

174
00:05:55,970 --> 00:05:57,870
也就差不多是这个问题的一半

175
00:05:57,870 --> 00:05:58,350
好

176
00:05:58,350 --> 00:06:01,890
你去右半边之后 会做什么

177
00:06:01,890 --> 00:06:05,870
16和50相比挺小的

178
00:06:05,870 --> 00:06:06,700
所以也许我会试 这个

179
00:06:06,700 --> 00:06:07,890
好

180
00:06:07,890 --> 00:06:08,720
42

181
00:06:08,720 --> 00:06:10,830
好 那现在你的直觉怎么说

182
00:06:10,830 --> 00:06:12,100
我可以把这个扔掉然后--

183
00:06:12,100 --> 00:06:12,360
好

184
00:06:12,360 --> 00:06:14,212
很好 你可以把左边这部分扔掉了

185
00:06:14,212 --> 00:06:14,890
--选这个

186
00:06:14,890 --> 00:06:15,530
右边的

187
00:06:15,530 --> 00:06:15,760
没错

188
00:06:15,760 --> 00:06:17,820
所以虽然因为我们只有7扇门 所以不太明显

189
00:06:17,820 --> 00:06:21,320
但是想像一下

190
00:06:21,320 --> 00:06:22,620
你刚才用的这个算法的稳定性

191
00:06:22,620 --> 00:06:24,510
在前一种情况下 你确实是运气好 这很好

192
00:06:24,510 --> 00:06:26,540
但这里我会说 你确实用了一种启发式规则

193
00:06:26,540 --> 00:06:29,150
你确实用到了你的直觉 你知道数字是排序好的

194
00:06:29,150 --> 00:06:31,600
所以如果一开始数字很小 那很显然 我们要往右边走

195
00:06:31,600 --> 00:06:34,990
但从某种意义上来说 你是运气好 因为也许这个数字会是100

196
00:06:34,990 --> 00:06:36,220
也许50会靠中间

197
00:06:36,220 --> 00:06:37,910
也许50会在这里

198
00:06:37,910 --> 00:06:40,960
但这一次 不同的是

199
00:06:40,960 --> 00:06:42,150
你是在重复做一件事

200
00:06:42,150 --> 00:06:45,310
我会说 你刚才做的 虽然是受了撕电话黄页的影响

201
00:06:45,310 --> 00:06:48,100
是一个有算法 有规则系统的事

202
00:06:48,100 --> 00:06:49,930
而不是只针对某种特别情况

203
00:06:49,930 --> 00:06:51,620
不像先前那么直觉性

204
00:06:51,620 --> 00:06:57,160
所以归根到底 你会怎样比较

205
00:06:57,160 --> 00:07:00,530
你的第一个算法 也就是从左到右

206
00:07:00,530 --> 00:07:03,430
和你的第二个算法谁效率高呢?

207
00:07:03,430 --> 00:07:06,460
这一种会把时间缩短一半 甚至更多

208
00:07:06,460 --> 00:07:07,320
好 也许更多

209
00:07:07,320 --> 00:07:10,150
让我们再多努力一把

210
00:07:10,150 --> 00:07:13,030
如果我们延用这个逻辑 我们确实会把时间

211
00:07:13,030 --> 00:07:15,830
缩短一半 因为我们把一半的数字都丢掉了

212
00:07:15,830 --> 00:07:18,470
但是我们在进行第二次循环的时候 也就是当Jennifer

213
00:07:18,470 --> 00:07:20,615
点开第二个数字的时候 我们做了什么呢

214
00:07:20,615 --> 00:07:22,830
我们又把门的数量缩减了一半

215
00:07:22,830 --> 00:07:25,270
如果我们还有更多的门的话 我们又会怎样呢

216
00:07:25,270 --> 00:07:27,520
我们会再把它们的数量减半 然后再减半 再减半

217
00:07:27,520 --> 00:07:30,420
这和你们在第一周的课上 大家都站起来

218
00:07:30,420 --> 00:07:33,000
然后其中一半坐下 再一半坐下 再一半

219
00:07:33,000 --> 00:07:35,440
直到只有一个人站着 是一样的

220
00:07:35,440 --> 00:07:39,050
我们说了 这样运行的时间 要运行所需的步骤数

221
00:07:39,050 --> 00:07:40,430
和什么有关

222
00:07:40,430 --> 00:07:41,230
[学生回答]

223
00:07:41,230 --> 00:07:43,970
以2为底n的对数 也就是 log n

224
00:07:43,970 --> 00:07:45,060
所以是对数

225
00:07:45,060 --> 00:07:48,380
而它的图形不是一条直线 随时间增加变得越来越糟

226
00:07:48,380 --> 00:07:52,490
而是一条曲线 随时间增加 不会越来越糟

227
00:07:52,490 --> 00:07:53,910
所以我们记住这一点

228
00:07:53,910 --> 00:07:54,690
然后谢谢Jennifer

229
00:07:54,690 --> 00:07:56,150
谢谢你上台来

230
00:07:56,150 --> 00:07:57,400
等一下

231
00:08:00,170 --> 00:08:02,925
今天没有台灯了 但我们有CS50的减压球

232
00:08:02,925 --> 00:08:03,420
好耶

233
00:08:03,420 --> 00:08:04,410
好的

234
00:08:04,410 --> 00:08:06,545
谢谢你为我们增添了压力

235
00:08:06,545 --> 00:08:07,350
好

236
00:08:07,350 --> 00:08:10,620
现在让我们看看能不能把这个弄正式些

237
00:08:10,620 --> 00:08:14,820
再一次 我们刚才做的

238
00:08:14,820 --> 00:08:16,660
和我们在第一周做的其实是一回事

239
00:08:16,660 --> 00:08:23,780
但是最后得到的 不是先前展示给大家看过的直线

240
00:08:23,780 --> 00:08:27,210
也就是说 如果我们在屏幕后增加门的数量

241
00:08:27,210 --> 00:08:29,610
那么Jennifer就得要去

242
00:08:29,610 --> 00:08:30,600
多看一扇门

243
00:08:30,600 --> 00:08:33,490
如果我们多添两扇门 她就可能要多看两扇门

244
00:08:33,490 --> 00:08:35,990
所以说 问题的大小  也就是x轴 和

245
00:08:35,990 --> 00:08:39,059
解决问题要花的时候 y

246
00:08:39,059 --> 00:08:40,440
是线性相关的

247
00:08:40,440 --> 00:08:43,330
但是我们先前讲到的是这条绿线

248
00:08:43,330 --> 00:08:45,970
绿线显然表示 这种方案比较好

249
00:08:45,970 --> 00:08:49,790
理论上来说 这个算法 也就是我们应对电话黄页的算法

250
00:08:49,790 --> 00:08:52,420
我们数教室里有多少人的算法 刚刚的第二种算法

251
00:08:52,420 --> 00:08:55,250
从根本上来说 要更优

252
00:08:55,250 --> 00:08:57,180
因为它不是快两倍

253
00:08:57,180 --> 00:08:58,870
它也不是快四倍

254
00:08:58,870 --> 00:09:03,290
它快多少 完成取决于input的大小

255
00:09:03,290 --> 00:09:05,220
也就是最终要花多少步

256
00:09:05,220 --> 00:09:08,040
所以简单来说 我们解决电话黄页问题的思路

257
00:09:08,040 --> 00:09:10,200
也可以应用到这个上面来

258
00:09:10,200 --> 00:09:12,380
这种方法 也被人叫做

259
00:09:12,380 --> 00:09:13,940
分治处理法

260
00:09:13,940 --> 00:09:16,390
不是像我们去撕书那样

261
00:09:16,390 --> 00:09:18,300
但是伪代码 是这样的

262
00:09:18,300 --> 00:09:21,800
我们不会再做一次 但回忆一下 第一周

263
00:09:21,800 --> 00:09:25,140
所有人都站起来 然后一半坐下 再一半坐下

264
00:09:25,140 --> 00:09:29,280
这个算法运行时我们有作弊

265
00:09:29,280 --> 00:09:32,870
因为不是我一个人

266
00:09:32,870 --> 00:09:35,830
更有效率地在数数 我依靠了其他资源

267
00:09:35,830 --> 00:09:39,470
就好像是多个CPU 多个大脑 多个聪明人

268
00:09:39,470 --> 00:09:42,740
一起帮我去把线性的东西

269
00:09:42,740 --> 00:09:45,190
变成对数的 把红的变成绿的

270
00:09:45,190 --> 00:09:48,650
但在这里 Jennifer一个人 多想了一会儿

271
00:09:48,650 --> 00:09:52,370
就把她第一次算法的表现提升了不少

272
00:09:52,370 --> 00:09:56,650
现在 我们想要实现这个

273
00:09:56,650 --> 00:10:00,670
那要怎样写代码 才能让它一直重复做某事呢

274
00:10:00,670 --> 00:10:03,350
就像是循环一样

275
00:10:03,350 --> 00:10:06,370
你们不会像Jennifer一开始一样

276
00:10:06,370 --> 00:10:10,460
有这么多"如果"可以来假设 如果第一个数字是4

277
00:10:10,460 --> 00:10:11,800
那就这我跳到最后去

278
00:10:11,800 --> 00:10:14,180
如果那个数字太大 那就让我再移回去

279
00:10:14,180 --> 00:10:15,220
到第二扇门去

280
00:10:15,220 --> 00:10:18,210
你会发现 要去把人觉得非常合理的规则

281
00:10:18,210 --> 00:10:21,270
程式化会有多难 但是电脑只会做

282
00:10:21,270 --> 00:10:23,260
你叫它做的事

283
00:10:23,260 --> 00:10:25,280
这其实非常有趣

284
00:10:25,280 --> 00:10:29,950
这张图视觉上来看是有点乱

285
00:10:29,950 --> 00:10:32,230
但是注意 直线在图中的什么地方?

286
00:10:32,230 --> 00:10:35,330
我们叫做n的直线图在哪

287
00:10:35,330 --> 00:10:37,580
差不多在图片的底部 对不对

288
00:10:37,580 --> 00:10:40,500
我们做的 是从远处来观察x与y轴

289
00:10:40,500 --> 00:10:44,780
来看其他的曲线长什么样

290
00:10:44,780 --> 00:10:47,760
它其中数学上的细节 我们今天不用知道得太清楚

291
00:10:47,760 --> 00:10:52,440
不过请注意 有很多其他的算法

292
00:10:52,440 --> 00:10:53,470
比线性的东西还要糟很多

293
00:10:53,470 --> 00:10:55,410
确实 n的三次方就挺糟的

294
00:10:55,410 --> 00:10:58,400
2的n次方也挺糟 n的平方也是

295
00:10:58,400 --> 00:11:01,630
我们会看到在现实世界 以上的情况会在何处出现

296
00:11:01,630 --> 00:11:05,430
log n也不太糟了 但是以2为底n的对数 比n要好

297
00:11:05,430 --> 00:11:08,080
但是 如果 Jennifer 或者我们在第一周时

298
00:11:08,080 --> 00:11:12,910
就想到log n 的对数的话 那就更好了

299
00:11:12,910 --> 00:11:15,880
换句话来说 解决问题有很多不同的方法

300
00:11:15,880 --> 00:11:18,570
但在这里 注意会发生什么

301
00:11:18,570 --> 00:11:22,910
当我缩小时 这些曲线中的哪一个

302
00:11:22,910 --> 00:11:26,630
一定是最糟的?

303
00:11:26,630 --> 00:11:28,680
n的三次方现在看上去挺糟的

304
00:11:28,680 --> 00:11:32,470
但如果q 们缩小界面 看到更多的x与y轴部分的话

305
00:11:32,470 --> 00:11:34,550
哪一个会是最糟的

306
00:11:34,550 --> 00:11:37,120
事实上 是2的n次方 你可以通过

307
00:11:37,120 --> 00:11:39,990
用越来越大的数字来试验 来证明

308
00:11:39,990 --> 00:11:42,070
2的n次方确实 增长的速度最快

309
00:11:42,070 --> 00:11:45,530
如果我们真的缩小很多的话 就会发现2的n次方真的很糟

310
00:11:45,530 --> 00:11:48,170
我是说 它会让电脑花

311
00:11:48,170 --> 00:11:49,460
很多时间来解决问题

312
00:11:49,460 --> 00:11:52,500
但经过一段时间你们会愈发明白的 特别是在后面的练习中

313
00:11:52,500 --> 00:11:55,600
以及最后的大作业中 你们的数据量是会变大的好么

314
00:11:55,600 --> 00:11:58,300
在Facebook初代版本中 当朋友的数量

315
00:11:58,300 --> 00:12:01,840
和注册用户的数量变大时

316
00:12:01,840 --> 00:12:05,530
你可以用线性搜索

317
00:12:05,530 --> 00:12:07,030
或是一个很简单的排序算法 就像我们今天看到的那样

318
00:12:07,030 --> 00:12:09,280
你们要好好想想这些问题

319
00:12:09,280 --> 00:12:12,070
Facebook Google和Microsoft这样的地方

320
00:12:12,070 --> 00:12:16,350
会去想的 关于大数据的问题

321
00:12:16,350 --> 00:12:18,530
这些问题近日吸引了很多人关注

322
00:12:18,530 --> 00:12:18,900
好

323
00:12:18,900 --> 00:12:23,800
Jennifer在第二个算法上的成功 说实话

324
00:12:23,800 --> 00:12:26,110
她第一次就做得好极了 但是就让我们说那是因为运气好

325
00:12:26,110 --> 00:12:27,000
这样我们就能表达一下这个观点

326
00:12:27,000 --> 00:12:30,970
也就是 在第二次中 她用了一种算法

327
00:12:30,970 --> 00:12:34,670
可以重复使用 但是她利用了我们告诉她的一个假设

328
00:12:34,670 --> 00:12:39,370
去探索了一些细节

329
00:12:39,370 --> 00:12:39,840
这是她在第一次没有做的

330
00:12:39,840 --> 00:12:41,800
那是什么呢?

331
00:12:41,800 --> 00:12:43,050
是这列数字是排序好的

332
00:12:43,050 --> 00:12:46,350
当它们被排序后 我们就说 Jennifer

333
00:12:46,350 --> 00:12:47,480
从根本上 可以做得更好

334
00:12:47,480 --> 00:12:51,450
七扇门可能还不够有趣 但假如有700万扇门

335
00:12:51,450 --> 00:12:54,080
从长远看log n一定会

336
00:12:54,080 --> 00:12:55,610
要运行得快很多

337
00:12:55,610 --> 00:12:58,880
但是 她需要有人帮她把门排序

338
00:12:58,880 --> 00:13:02,320
现在 是我先前就去在屏幕上把它排好序了

339
00:13:02,320 --> 00:13:05,160
但假如Jennifer需要自己做这件事呢

340
00:13:05,160 --> 00:13:10,120
假设这些门代表的是数据库中的数据

341
00:13:10,120 --> 00:13:14,260
或者是注册Facebook的人 或者是

342
00:13:14,260 --> 00:13:16,880
网站会搜索到的任意网页

343
00:13:16,880 --> 00:13:20,940
如果有人给你了一个未经处理过的数据集

344
00:13:20,940 --> 00:13:23,010
或是给Jennifer 要你们来排序 会怎么样

345
00:13:23,010 --> 00:13:26,950
这就需要我们回答这样一个问题

346
00:13:26,950 --> 00:13:31,080
Jennifer 或者是我 来提前将这些数字排序

347
00:13:31,080 --> 00:13:32,680
需要花多少时间?

348
00:13:32,680 --> 00:13:32,880
是不是?

349
00:13:32,880 --> 00:13:36,620
我们可以推测 去将这些数字排序

350
00:13:36,620 --> 00:13:40,800
会花掉我不少时间 谁又会在意你能不能很快找到50这个数字呢

351
00:13:40,800 --> 00:13:44,850
在Jennifer的情况里 事先排好序

352
00:13:44,850 --> 00:13:46,920
会不会并没有帮我们省下太多的时间呢?

353
00:13:46,920 --> 00:13:49,320
让我们看看能不能做个展示

354
00:13:49,320 --> 00:13:51,370
我还有好多减压球

355
00:13:51,370 --> 00:13:52,270
如果这能调动到大家的话

356
00:13:52,270 --> 00:13:55,690
如果大家不介意 我们需要7位志愿者

357
00:13:55,690 --> 00:13:57,060
好

358
00:13:57,060 --> 00:13:57,240
哇

359
00:13:57,240 --> 00:13:59,250
看来不用靠台灯招揽志愿者了

360
00:13:59,250 --> 00:13:59,690
好

361
00:13:59,690 --> 00:14:01,530
前面的这两位同学

362
00:14:01,530 --> 00:14:04,160
还有 后面的这两位

363
00:14:04,160 --> 00:14:04,870
这是四个人了

364
00:14:04,870 --> 00:14:09,890
还有前面的第 5 6 7个

365
00:14:09,890 --> 00:14:10,320
就是你

366
00:14:10,320 --> 00:14:13,260
你的朋友们把你推举出来 所以你可以得到奖

367
00:14:13,260 --> 00:14:13,700
好

368
00:14:13,700 --> 00:14:14,410
上来吧

369
00:14:14,410 --> 00:14:17,120
请站到这边

370
00:14:17,120 --> 00:14:18,960
我们给你们每人一个数字

371
00:14:18,960 --> 00:14:22,150
然后按屏幕上显示的

372
00:14:22,150 --> 00:14:25,180
站好

373
00:14:25,180 --> 00:14:26,530
[学生交谈]

374
00:14:26,530 --> 00:14:28,160
唉呀 不好意思

375
00:14:28,160 --> 00:14:30,210
Bug

376
00:14:30,210 --> 00:14:32,180
好

377
00:14:32,180 --> 00:14:32,750
好 现在可以了

378
00:14:32,750 --> 00:14:34,180
数字5

379
00:14:34,180 --> 00:14:35,136
数字6

380
00:14:35,136 --> 00:14:37,770
1 2 3 4 5 6 7

381
00:14:37,770 --> 00:14:39,410
这有点尴尬

382
00:14:39,410 --> 00:14:41,210
我要--

383
00:14:41,210 --> 00:14:41,900
好

384
00:14:41,900 --> 00:14:43,130
好的

385
00:14:43,130 --> 00:14:44,611
谢谢参与

386
00:14:44,611 --> 00:14:47,200
[掌声]

387
00:14:47,200 --> 00:14:48,580
好

388
00:14:48,580 --> 00:14:48,860
好

389
00:14:48,860 --> 00:14:51,970
我们有 4 2 6 1 3 7 5

390
00:14:51,970 --> 00:14:56,010
太好了 我们有7位志愿者 这和我们先前在玩的数组

391
00:14:56,010 --> 00:14:57,430
长度是一致的

392
00:14:57,430 --> 00:14:59,470
我选择了7这个数字

393
00:14:59,470 --> 00:15:00,840
是因为它会带来一些便利

394
00:15:00,840 --> 00:15:04,400
我提议 我们先把这7位志愿者排好序

395
00:15:04,400 --> 00:15:06,786
不过 如果你们想的话 可以先和大家打声音招呼

396
00:15:06,786 --> 00:15:08,970
这将会是让人尴尬的几分钟

397
00:15:08,970 --> 00:15:10,370
请你们一一自我介绍下

398
00:15:10,370 --> 00:15:10,980
大家好 我是Grace

399
00:15:10,980 --> 00:15:14,190
我大二 住在Leverett宿舍

400
00:15:14,190 --> 00:15:14,620
大家好

401
00:15:14,620 --> 00:15:15,620
我是Branson

402
00:15:15,620 --> 00:15:16,920
大一 住在Weld

403
00:15:19,755 --> 00:15:20,230
大家好

404
00:15:20,230 --> 00:15:21,040
我是Gabe

405
00:15:21,040 --> 00:15:22,300
大三 住在Cabot

406
00:15:24,826 --> 00:15:25,980
我是Neil

407
00:15:25,980 --> 00:15:29,090
大一 住在Matthews

408
00:15:29,090 --> 00:15:29,550
我是Jason

409
00:15:29,550 --> 00:15:32,816
大一 住在Greenough

410
00:15:32,816 --> 00:15:33,700
我是Mike

411
00:15:33,700 --> 00:15:37,360
大一 住在Grays

412
00:15:37,360 --> 00:15:37,990
我是Jess

413
00:15:37,990 --> 00:15:40,313
大二 住在Leverett

414
00:15:40,313 --> 00:15:41,300
太好了

415
00:15:41,300 --> 00:15:41,850
好

416
00:15:41,850 --> 00:15:44,190
谢谢你们志愿上台来

417
00:15:44,190 --> 00:15:47,110
现在我们面临的挑战是 怎样来排序

418
00:15:47,110 --> 00:15:50,250
然后我们要好好想想

419
00:15:50,250 --> 00:15:51,110
我们排序的方法效率有多高

420
00:15:51,110 --> 00:15:52,580
我们先来试试这个

421
00:15:52,580 --> 00:15:55,970
你们可以看见彼此的数字

422
00:15:55,970 --> 00:15:59,380
那就请花点时间 自己排序下

423
00:15:59,380 --> 00:16:01,240
从左到右 从小到大排列

424
00:16:01,240 --> 00:16:02,490
开始

425
00:16:07,010 --> 00:16:07,530
好

426
00:16:07,530 --> 00:16:08,030
好

427
00:16:08,030 --> 00:16:09,370
这真的很快

428
00:16:09,370 --> 00:16:14,040
这边的同学 有谁能说说刚才他们用了什么算法?

429
00:16:14,040 --> 00:16:14,900
从小到大

430
00:16:14,900 --> 00:16:15,000
好

431
00:16:15,000 --> 00:16:18,070
从小到大是我们的目标

432
00:16:18,070 --> 00:16:18,890
但我不确定这是种算法

433
00:16:18,890 --> 00:16:21,810
从小到大并不会告诉我 一步一步要怎样做

434
00:16:21,810 --> 00:16:22,833
什么?

435
00:16:22,833 --> 00:16:24,083
[学生回答]

436
00:16:26,010 --> 00:16:26,280
好

437
00:16:26,280 --> 00:16:28,920
如果你看见一个人 他的数字比你小

438
00:16:28,920 --> 00:16:29,680
那就移到他右边

439
00:16:29,680 --> 00:16:32,800
这样就更清楚一点了 更像个算法

440
00:16:32,800 --> 00:16:35,410
因为你在说 如果怎样怎样 那就怎样怎样

441
00:16:35,410 --> 00:16:37,050
所以我们有个像条件结构的东西

442
00:16:37,050 --> 00:16:39,700
这些人好像做了几次 因为你们其中一些人

443
00:16:39,700 --> 00:16:40,420
移动得挺远

444
00:16:40,420 --> 00:16:43,410
所以 我们可以推测出 他们脑中是在进行某种循环的

445
00:16:43,410 --> 00:16:44,610
但让我们尝试把它系统化

446
00:16:44,610 --> 00:16:47,540
如果你们能重新回到这种排列

447
00:16:47,540 --> 00:16:50,650
让我们看看能不能系统化这个进程 然后提出这个问题

448
00:16:50,650 --> 00:16:51,580
这种方法效率到底有多高?

449
00:16:51,580 --> 00:16:54,220
当然 当我们慢慢进行时 我们会觉得这好像不是一个很好的算法

450
00:16:54,220 --> 00:16:57,210
但让我们看看我们能不能找到准确的步骤

451
00:16:57,210 --> 00:16:58,670
所以你们俩分别是4和2

452
00:16:58,670 --> 00:17:01,020
你们的顺序对不对呢?

453
00:17:01,020 --> 00:17:01,900
显然不对

454
00:17:01,900 --> 00:17:02,710
所以我们互换了

455
00:17:02,710 --> 00:17:05,170
然后我会到这里 然后说 4和6

456
00:17:05,170 --> 00:17:06,240
对还是不对?

457
00:17:06,240 --> 00:17:06,599
对了

458
00:17:06,599 --> 00:17:07,180
对

459
00:17:07,180 --> 00:17:08,300
6和1

460
00:17:08,300 --> 00:17:08,609
不对

461
00:17:08,609 --> 00:17:09,630
换

462
00:17:09,630 --> 00:17:10,490
所以现在换了2次

463
00:17:10,490 --> 00:17:11,710
6和3

464
00:17:11,710 --> 00:17:11,980
不对

465
00:17:11,980 --> 00:17:13,000
换

466
00:17:13,000 --> 00:17:13,930
6和7

467
00:17:13,930 --> 00:17:14,630
看起来是对的

468
00:17:14,630 --> 00:17:15,396
7和5

469
00:17:15,396 --> 00:17:16,150
[学生回答]

470
00:17:16,150 --> 00:17:17,089
好 换

471
00:17:17,089 --> 00:17:19,770
这样就排好了

472
00:17:19,770 --> 00:17:19,980
好

473
00:17:19,980 --> 00:17:21,440
显然没排好呢 对不对

474
00:17:21,440 --> 00:17:22,470
还有工作要做

475
00:17:22,470 --> 00:17:24,920
但是 这些人 本能地

476
00:17:24,920 --> 00:17:25,450
就继续移动位置了

477
00:17:25,450 --> 00:17:27,710
他们在解决了一个问题后 并没有停下来

478
00:17:27,710 --> 00:17:27,839
所以

479
00:17:27,839 --> 00:17:29,390
我也得这么做

480
00:17:29,390 --> 00:17:32,720
我要回到这个问题的开始

481
00:17:32,720 --> 00:17:35,630
或者是回到这群人这个数组的开始

482
00:17:35,630 --> 00:17:38,366
现在我要进行第二轮了 那我的算法是什么呢

483
00:17:38,366 --> 00:17:39,220
还是一样

484
00:17:39,220 --> 00:17:39,940
一样

485
00:17:39,940 --> 00:17:41,460
我开始喜欢这个了 对不对

486
00:17:41,460 --> 00:17:44,720
当你发现自己可以一遍遍做同样的事时

487
00:17:44,720 --> 00:17:47,890
这就越来越像一个算法 还不是人类的本能了

488
00:17:47,890 --> 00:17:48,680
所以现在 我们再来一次

489
00:17:48,680 --> 00:17:49,870
2和4?

490
00:17:49,870 --> 00:17:50,220
不用换

491
00:17:50,220 --> 00:17:51,050
4和1 ?

492
00:17:51,050 --> 00:17:53,380
所以确实 还有工作没做完

493
00:17:53,380 --> 00:17:53,620
4和3?

494
00:17:53,620 --> 00:17:54,572
好

495
00:17:54,572 --> 00:17:56,000
4和6?

496
00:17:56,000 --> 00:17:58,380
6和5？

497
00:17:58,380 --> 00:17:59,470
6和7?

498
00:17:59,470 --> 00:18:00,970
好 现在 完成了

499
00:18:00,970 --> 00:18:01,550
好吧 还是没有

500
00:18:01,550 --> 00:18:02,710
我还要再回去

501
00:18:02,710 --> 00:18:05,130
现在 又一次 我们要更有意识地来做这件事

502
00:18:05,130 --> 00:18:08,700
现在 只有一个大脑在运行这个算法

503
00:18:08,700 --> 00:18:10,290
也就是 一个CPU

504
00:18:10,290 --> 00:18:13,090
事实上 当我们回到键盘前

505
00:18:13,090 --> 00:18:16,280
去用像C语言这样的东西时 这是我们能用到的唯一资源

506
00:18:16,280 --> 00:18:19,600
我们就只是在写一个程序 它一次只能做一件事

507
00:18:19,600 --> 00:18:22,900
但是 先前这些人 我们利用了他们的集体智慧

508
00:18:22,900 --> 00:18:24,180
就像你们在第0周时那样

509
00:18:24,180 --> 00:18:24,980
所以让我们继续

510
00:18:24,980 --> 00:18:26,260
2和1

511
00:18:26,260 --> 00:18:26,945
2和3

512
00:18:26,945 --> 00:18:27,460
3和4

513
00:18:27,460 --> 00:18:28,310
4和5

514
00:18:28,310 --> 00:18:28,620
5和6

515
00:18:28,620 --> 00:18:30,510
6和7

516
00:18:30,510 --> 00:18:31,880
完成了么?

517
00:18:31,880 --> 00:18:34,560
完成了 但让我扮一下魔鬼代言人

518
00:18:34,560 --> 00:18:37,950
我 电脑 如果刚看了这一个数组的话

519
00:18:37,950 --> 00:18:40,225
知道我自己已经完成工作了么?

520
00:18:40,225 --> 00:18:40,670
不

521
00:18:40,670 --> 00:18:41,050
为什么不呢

522
00:18:41,050 --> 00:18:46,900
我要怎样 才能做出 我已经完成了 的结论呢

523
00:18:46,900 --> 00:18:48,230
也许还要再过一遍

524
00:18:48,230 --> 00:18:48,430
对不对?

525
00:18:48,430 --> 00:18:51,760
因为过前一遍时 我只知道自己更正了一个错误

526
00:18:51,760 --> 00:18:53,920
这意味着 也许还有错误

527
00:18:53,920 --> 00:18:54,840
需要我来更正

528
00:18:54,840 --> 00:18:58,680
所以我只能再重头检查一遍

529
00:18:58,680 --> 00:19:00,940
1和2  2和3 3和4 4和5 5和6 6和7 才能确定

530
00:19:00,940 --> 00:19:02,510
现在我什么也没做

531
00:19:02,510 --> 00:19:05,990
我还记得我对一个像变量这样的东西 像是一个整数

532
00:19:05,990 --> 00:19:06,975
没有进行任何处理

533
00:19:06,975 --> 00:19:12,490
我叫它swaps(交换位置)如果从一开始没有交换位置 swaps是0

534
00:19:12,490 --> 00:19:15,520
那我就很蠢地一直来回检查

535
00:19:15,520 --> 00:19:16,450
一遍又一遍 对不对

536
00:19:16,450 --> 00:19:18,450
因为你会陷在一个无限循环里

537
00:19:18,450 --> 00:19:21,250
所以当交换位置次数为0时 我们就说

538
00:19:21,250 --> 00:19:23,810
这个算法已经完成了

539
00:19:23,810 --> 00:19:25,400
现在 让我们给它起个名

540
00:19:25,400 --> 00:19:28,930
我提议的 并且我们完成了的这个算法

541
00:19:28,930 --> 00:19:32,800
叫 冒泡排序法 也就是说 大一点的数字

542
00:19:32,800 --> 00:19:37,990
就像泡泡一样升到上面去 或者说 升到这个数字数组的尾端去

543
00:19:37,990 --> 00:19:40,270
但这个算法效率有多高呢

544
00:19:40,270 --> 00:19:44,600
比如 我刚才做了多少步

545
00:19:44,600 --> 00:19:45,850
才把这7个人排好?

546
00:19:48,560 --> 00:19:49,550
4到5?

547
00:19:49,550 --> 00:19:51,420
当然 答案最终可以是 太多步了

548
00:19:51,420 --> 00:19:54,960
但这个具体的数字并不重要

549
00:19:54,960 --> 00:19:56,670
让我们把它叫做n

550
00:19:56,670 --> 00:20:00,520
如果我让n个人上来 然后一开始

551
00:20:00,520 --> 00:20:02,180
他们是随机排列的

552
00:20:02,180 --> 00:20:04,910
第一遍过去 我要做多少步

553
00:20:04,910 --> 00:20:09,810
是 1 2 3 4 5 6 有7个人

554
00:20:09,810 --> 00:20:13,670
是6步--所以第一遍是n-1步

555
00:20:13,670 --> 00:20:16,280
当我再来一次时 要做多少步?

556
00:20:16,280 --> 00:20:19,310
事实上我们可以把它乘2 但现在

557
00:20:19,310 --> 00:20:22,300
我就说 好 再做n-1步

558
00:20:22,300 --> 00:20:25,240
n-1计起来有点麻烦

559
00:20:25,240 --> 00:20:26,400
就让我们四舍五入下

560
00:20:26,400 --> 00:20:27,770
所以是2n步

561
00:20:27,770 --> 00:20:29,310
所以大概是14步

562
00:20:29,310 --> 00:20:31,930
那下一次 我要做多少步?

563
00:20:31,930 --> 00:20:33,740
是3n步

564
00:20:33,740 --> 00:20:34,510
是的

565
00:20:34,510 --> 00:20:37,920
现在 在最坏的情况下

566
00:20:37,920 --> 00:20:41,730
我要来回过多少次 来运行这个算法

567
00:20:41,730 --> 00:20:44,620
让人们交换位置呢?

568
00:20:47,720 --> 00:20:50,010
是n平方次 是不是

569
00:20:50,010 --> 00:20:53,000
因为在最坏的情况下 你可以靠直觉猜出来

570
00:20:53,000 --> 00:20:54,800
虽然可能要花点时间

571
00:20:54,800 --> 00:20:57,590
在最坏的情况下 这7个人

572
00:20:57,590 --> 00:21:00,230
会是怎样排列的呢?

573
00:21:00,230 --> 00:21:01,460
完成反了 对不对

574
00:21:01,460 --> 00:21:02,815
为了模拟那种情况 你叫什么名字来着

575
00:21:02,815 --> 00:21:03,360
Mike

576
00:21:03,360 --> 00:21:03,640
Mike?

577
00:21:03,640 --> 00:21:08,100
好 Mike你可以同我一起站过来一下么

578
00:21:08,100 --> 00:21:08,880
事实上 不要

579
00:21:08,880 --> 00:21:10,150
不好意思Mike 让我们重新来过

580
00:21:10,150 --> 00:21:10,910
你叫什么名字?

581
00:21:10,910 --> 00:21:11,180
Neil

582
00:21:11,180 --> 00:21:11,640
Neil

583
00:21:11,640 --> 00:21:13,750
好 Neil 你能不能和我过来下 如果你不介意的话

584
00:21:13,750 --> 00:21:17,150
我想提议 为了简便Neil现在

585
00:21:17,150 --> 00:21:18,510
面临着他最坏的情况

586
00:21:18,510 --> 00:21:20,720
但回忆下我是怎样进行我的算法的

587
00:21:20,720 --> 00:21:24,530
我是在比较比较再比较

588
00:21:24,530 --> 00:21:26,640
哦 这两个人顺序不对 然后我去改正

589
00:21:26,640 --> 00:21:27,980
所以你俩交换位置

590
00:21:27,980 --> 00:21:31,630
但现在想一下 Neil要走多远呢

591
00:21:31,630 --> 00:21:32,690
大概是n

592
00:21:32,690 --> 00:21:33,570
准确来说 不是n

593
00:21:33,570 --> 00:21:36,040
应该是n-1 但我觉得这有点烦

594
00:21:36,040 --> 00:21:37,550
所以我们就算是n吧

595
00:21:37,550 --> 00:21:42,860
如果Neil一次最多只能移一位 而且为了让Neil移动

596
00:21:42,860 --> 00:21:46,580
我得来回再过一遍的话

597
00:21:46,580 --> 00:21:52,080
这就大概是 n步乘以n次

598
00:21:52,080 --> 00:21:55,820
因为我要把Neil移到他应该待的位置 就要进行这么多次

599
00:21:55,820 --> 00:21:58,620
还不算其他人 如果你们也被错误地排列的话

600
00:21:58,620 --> 00:22:01,100
我们就说 冒泡排序法是n的平方

601
00:22:01,100 --> 00:22:04,860
这个算法的运行时间 这个算法的表现

602
00:22:04,860 --> 00:22:07,120
这个算法的效率

603
00:22:07,120 --> 00:22:08,800
我们都可以用n平方来形容

604
00:22:08,800 --> 00:22:11,650
这很方便 因为如果我用8个人9个人

605
00:22:11,650 --> 00:22:15,450
100万个人来举例子 答案都不会变

606
00:22:15,450 --> 00:22:18,870
所以如果你们不介意 请回来最初始的位置

607
00:22:18,870 --> 00:22:22,510
让我们再试其他两种方法

608
00:22:22,510 --> 00:22:23,820
来看看我们能不能做得更好

609
00:22:23,820 --> 00:22:27,130
这一次 我提议 用一种不同的算法

610
00:22:27,130 --> 00:22:29,950
上次 我们看得很明了

611
00:22:29,950 --> 00:22:32,470
你们本能地就开始一对对进行位置交换

612
00:22:32,470 --> 00:22:36,500
但是如果我想要简单地解决这个问题

613
00:22:36,500 --> 00:22:39,800
把所有小的数字移到这边

614
00:22:39,800 --> 00:22:43,030
把大的数字移到那边 那我为什么不试试最简单的办法

615
00:22:43,030 --> 00:22:45,730
来看看会不会比刚才那个有点复杂的算法要好?

616
00:22:45,730 --> 00:22:46,620
让我们来试试

617
00:22:46,620 --> 00:22:48,940
4是个挺小的数字 那我就让你待在这

618
00:22:48,940 --> 00:22:50,610
2更好

619
00:22:50,610 --> 00:22:52,230
所以你能不能往前站一步?

620
00:22:52,230 --> 00:22:55,670
这是我现在的 最小数字候选人

621
00:22:55,670 --> 00:22:57,000
我要用 一个变量记住它

622
00:22:57,000 --> 00:22:57,930
但我还要继续检查

623
00:22:57,930 --> 00:22:59,890
还有没有更小的数字?

624
00:22:59,890 --> 00:23:00,460
6 不对

625
00:23:00,460 --> 00:23:01,390
哦 又到了Neil

626
00:23:01,390 --> 00:23:04,050
概念上来说 我要把你推到后面去

627
00:23:04,050 --> 00:23:05,120
Neil会到前面来

628
00:23:05,120 --> 00:23:08,440
现在 我用来记录最小的数字的那个变量

629
00:23:08,440 --> 00:23:11,390
已经更新了 它现在包含的是Neil的位置

630
00:23:11,390 --> 00:23:12,110
让我们看下

631
00:23:12,110 --> 00:23:13,960
3，7，5

632
00:23:13,960 --> 00:23:15,590
我知道Neil是最小的

633
00:23:15,590 --> 00:23:18,110
那现在我要做的 最简单的事是什么?

634
00:23:18,110 --> 00:23:21,410
我不想浪费时间 只是把Neil冒泡向左边一位

635
00:23:21,410 --> 00:23:25,350
我们为什么不把Neil放在他应该在的位置 也就是哪里呢?

636
00:23:25,350 --> 00:23:26,160
最最前面这里

637
00:23:26,160 --> 00:23:27,720
所以Neil 跟我来

638
00:23:27,720 --> 00:23:28,910
你叫什么名字?

639
00:23:28,910 --> 00:23:29,310
Grace

640
00:23:29,310 --> 00:23:29,710
Grace

641
00:23:29,710 --> 00:23:29,920
好

642
00:23:29,920 --> 00:23:32,490
那么Grace 不幸的是 你好像挡到路了

643
00:23:32,490 --> 00:23:34,290
所以我们要怎样解决这个问题?

644
00:23:34,290 --> 00:23:34,490
嗯?

645
00:23:34,490 --> 00:23:37,500
如果这是一个数组 里面只有7个位置

646
00:23:37,500 --> 00:23:40,830
还记得 Rob的课里 我们讲过要声明年龄

647
00:23:40,830 --> 00:23:41,740
而我们只有一定数量的年龄

648
00:23:41,740 --> 00:23:42,535
这里也是一样

649
00:23:42,535 --> 00:23:44,300
我们只有一定数量的整数

650
00:23:44,300 --> 00:23:47,590
Grace好像挡到了路 那我们怎么办呢

651
00:23:47,590 --> 00:23:49,555
最简单的方法是 Grace 对不起

652
00:23:49,555 --> 00:23:51,870
你得挪到那儿去 给我们腾出位置

653
00:23:51,870 --> 00:23:55,290
如果我们想一下 也许我们把问题弄得更复杂了

654
00:23:55,290 --> 00:23:58,510
这是有可能的 因为 如果Grace本来就在正确的位置呢?

655
00:23:58,510 --> 00:24:01,730
但我们知道她不在 因为如果是那样的话

656
00:24:01,730 --> 00:24:03,980
她就应该站在前面 而不是Neil了 对不对

657
00:24:03,980 --> 00:24:05,550
我们已经检查过她的数字了

658
00:24:05,550 --> 00:24:05,770
好

659
00:24:05,770 --> 00:24:09,110
现在 Neil在正确的位置了 我可以简单优化一下

660
00:24:09,110 --> 00:24:11,740
下面 我要完全忽略Neil

661
00:24:11,740 --> 00:24:15,280
这样就不要浪费时间 也不会不小心把他换到错误的位置去

662
00:24:15,280 --> 00:24:17,805
那么现在 我要怎样才能找到除Neil外 最小的元素呢?

663
00:24:17,805 --> 00:24:18,480
2

664
00:24:18,480 --> 00:24:20,225
这个数字挺不错 你能不能向前一步

665
00:24:20,225 --> 00:24:21,100
我会记得你的

666
00:24:21,100 --> 00:24:21,980
6 不行

667
00:24:21,980 --> 00:24:24,820
4 3 7 5 都不太行

668
00:24:24,820 --> 00:24:26,800
那么就让我把你移到正确的位置去

669
00:24:26,800 --> 00:24:28,470
我们这次很幸运

670
00:24:28,470 --> 00:24:31,350
现在 我要忽略这两个人 然后再

671
00:24:31,350 --> 00:24:32,260
重复过一次

672
00:24:32,260 --> 00:24:33,490
6 这个数字还算小

673
00:24:33,490 --> 00:24:34,300
上前来

674
00:24:34,300 --> 00:24:35,220
哦 不好意思

675
00:24:35,220 --> 00:24:37,640
Grace的数字更好 上前一步

676
00:24:37,640 --> 00:24:38,260
4

677
00:24:38,260 --> 00:24:39,120
不好意思Grace

678
00:24:39,120 --> 00:24:39,950
请回去

679
00:24:39,950 --> 00:24:41,550
数字3要更好

680
00:24:41,550 --> 00:24:42,290
7

681
00:24:42,290 --> 00:24:42,720
5

682
00:24:42,720 --> 00:24:43,550
你叫什么名字?

683
00:24:43,550 --> 00:24:44,000
Jason

684
00:24:44,000 --> 00:24:44,420
Jason

685
00:24:44,420 --> 00:24:47,050
所以现在Jason是我选中的最小的元素

686
00:24:47,050 --> 00:24:49,160
他要做什么呢?

687
00:24:49,160 --> 00:24:50,380
在6现在的位置

688
00:24:50,380 --> 00:24:51,210
你叫什么名字?

689
00:24:51,210 --> 00:24:51,710
Gabe

690
00:24:51,710 --> 00:24:52,340
Gabe

691
00:24:52,340 --> 00:24:53,220
Gabe挡住了路

692
00:24:53,220 --> 00:24:54,640
最简单的办法是什么?

693
00:24:54,640 --> 00:24:58,390
让他们俩交换位置然后继续

694
00:24:58,390 --> 00:24:59,020
所以让我们看看

695
00:24:59,020 --> 00:25:00,170
谁最小?

696
00:25:00,170 --> 00:25:01,030
4

697
00:25:01,030 --> 00:25:01,990
让我作弊一下

698
00:25:01,990 --> 00:25:03,090
5是最小的数字

699
00:25:03,090 --> 00:25:05,220
我找到了 如果你可以向前一步

700
00:25:05,220 --> 00:25:06,820
我要怎么处理这些人 和Gabe呢?

701
00:25:06,820 --> 00:25:08,450
再交换一次

702
00:25:08,450 --> 00:25:10,740
所以现在 顺序还是有点不对

703
00:25:10,740 --> 00:25:14,140
我发现Gabe是最小的 所以我让他出来 把你们移到一边

704
00:25:14,140 --> 00:25:15,190
这下好了

705
00:25:15,190 --> 00:25:17,200
所以答案还是一样

706
00:25:17,200 --> 00:25:18,600
最终结果是一样

707
00:25:18,600 --> 00:25:22,730
这两种算法哪个更好呢?

708
00:25:22,730 --> 00:25:23,500
我听到有人说第二种

709
00:25:23,500 --> 00:25:24,252
为什么?

710
00:25:24,252 --> 00:25:25,900
它用了n步…

711
00:25:25,900 --> 00:25:27,600
它最多用n步

712
00:25:27,600 --> 00:25:28,490
有意思

713
00:25:28,490 --> 00:25:30,610
是这样么?

714
00:25:30,610 --> 00:25:33,630
我是怎样找到最小的元素的?

715
00:25:33,630 --> 00:25:37,060
我要找到最小的元素要花多少步?

716
00:25:37,060 --> 00:25:39,220
我一直看到尾端 对不对?

717
00:25:39,220 --> 00:25:41,530
因为最坏的情况下 如果Neil在最后面的话

718
00:25:41,530 --> 00:25:45,700
所以光是找到最小的元素就要花我n步了 或是说 n-1步

719
00:25:45,700 --> 00:25:46,100
但是 好

720
00:25:46,100 --> 00:25:46,980
所以把Neil弄好了

721
00:25:46,980 --> 00:25:48,740
记得大概在一分钟前

722
00:25:48,740 --> 00:25:51,680
但我是怎么找到下一个最小的元素的?

723
00:25:51,680 --> 00:25:54,830
我花了n-1 或者说是 n-2步

724
00:25:54,830 --> 00:25:55,440
所以好的

725
00:25:55,440 --> 00:25:57,390
我花了n-2步

726
00:25:57,390 --> 00:25:57,600
好

727
00:25:57,600 --> 00:25:59,130
这感觉要好一点了

728
00:25:59,130 --> 00:25:59,730
好

729
00:25:59,730 --> 00:26:03,270
我们找到数字3花了多少步?

730
00:26:03,270 --> 00:26:04,420
n-4步

731
00:26:04,420 --> 00:26:07,670
所以是在变少的 每次循环 会少一步

732
00:26:07,670 --> 00:26:08,740
所以这个感觉要好一点对不对

733
00:26:08,740 --> 00:26:13,450
如果上一种方法大概是n乘以n步的话 这次是n-1加

734
00:26:13,450 --> 00:26:16,500
n-2加n-3加n-4……

735
00:26:16,500 --> 00:26:18,750
但如果你还记得你的高中课表背后

736
00:26:18,750 --> 00:26:24,380
总有一面写着所有的公式 如果你把这些数字加起来

737
00:26:24,380 --> 00:26:31,280
那么我一共要花多少步呢?

738
00:26:31,280 --> 00:26:36,580
是 n(n-1)/2步

739
00:26:36,580 --> 00:26:39,040
让我看看能不能很快算出来

740
00:26:39,040 --> 00:26:42,230
同样 为了简便 我会算个大概

741
00:26:42,230 --> 00:26:47,830
但如果我算n-1 n-2

742
00:26:47,830 --> 00:26:53,570
然后n-3的话 差不多就是这个除以2

743
00:26:53,570 --> 00:26:55,510
如果我先乘好的话 差不多就是n平方

744
00:26:55,510 --> 00:26:58,940
这个感觉不是太好 n平方-n/2?

745
00:26:58,940 --> 00:27:00,350
但要记得

746
00:27:00,350 --> 00:27:03,720
在计算机里 n越大时

747
00:27:03,720 --> 00:27:04,700
问题才越有意思

748
00:27:04,700 --> 00:27:08,110
当n真的很大时 哪个数字

749
00:27:08,110 --> 00:27:09,750
会开始比其他的都重要?

750
00:27:09,750 --> 00:27:10,990
n平方 对不对?

751
00:27:10,990 --> 00:27:13,340
所以 除以2还是不错的

752
00:27:13,340 --> 00:27:16,740
但如果我们关注的是以十亿、千亿记的数据

753
00:27:16,740 --> 00:27:18,700
那么 你就有别人两倍快了

754
00:27:18,700 --> 00:27:22,440
但谁又会关注这个数字

755
00:27:22,440 --> 00:27:23,040
如果这一部分越来越大

756
00:27:23,040 --> 00:27:25,990
而且当然 它比这边这个的影响要大

757
00:27:25,990 --> 00:27:29,120
所以即使你们是对的 第二种算法

758
00:27:29,120 --> 00:27:32,970
我们叫它选择法排序 在现实世界中 确实会更快

759
00:27:32,970 --> 00:27:35,360
因为我每一次要用的步数都在变少

760
00:27:35,360 --> 00:27:37,340
从根本上来说 它并没有变快

761
00:27:37,340 --> 00:27:41,430
因为如果n真的很大的话

762
00:27:41,430 --> 00:27:44,750
最终 如果n够大 它还是会很慢

763
00:27:44,750 --> 00:27:46,770
让我最后再来试一种方法

764
00:27:46,770 --> 00:27:48,920
刚才这一种叫选择排序法

765
00:27:48,920 --> 00:27:51,040
你们能不能再一次回到初始位置去?

766
00:27:51,040 --> 00:27:53,550
最后这一次 我要提议一种

767
00:27:53,550 --> 00:27:54,970
叫插入排序法

768
00:27:54,970 --> 00:27:57,470
插入排序 从概念上来说 有一点不同

769
00:27:57,470 --> 00:28:00,980
它不是来回去找最小的元素

770
00:28:00,980 --> 00:28:05,030
而是在遇见每个数字的时候 就挨个处理

771
00:28:05,030 --> 00:28:06,850
把它们插入到正确的位置

772
00:28:06,850 --> 00:28:10,160
所以我会从Grace开始 我看到她是数字4

773
00:28:10,160 --> 00:28:11,720
数字4应该在哪里?

774
00:28:11,720 --> 00:28:14,940
我还没有开始排序 所以Grace可以留在这个位置

775
00:28:14,940 --> 00:28:18,355
现在我要声明 如果你可以往右一步

776
00:28:18,355 --> 00:28:21,650
这是我排序好的 这是我还没排序好的部分

777
00:28:21,650 --> 00:28:23,260
现在我要继续了 你叫什么名字?

778
00:28:23,260 --> 00:28:23,700
Branson

779
00:28:23,700 --> 00:28:24,150
Branson

780
00:28:24,150 --> 00:28:25,375
Branson是数字2

781
00:28:25,375 --> 00:28:27,490
那我要叫你出列一下

782
00:28:27,490 --> 00:28:30,940
现在 你在这个数组里应该在哪?

783
00:28:30,940 --> 00:28:32,360
在Grace右边

784
00:28:32,360 --> 00:28:35,670
再一次 我们让Grace辛苦一下

785
00:28:35,670 --> 00:28:37,290
我们要把你放在哪?

786
00:28:37,290 --> 00:28:40,120
我们要把你往左移 然后要把Branson放这里

787
00:28:40,120 --> 00:28:41,680
但现在我声称你们已经放好了

788
00:28:41,680 --> 00:28:43,240
不过注意 我没有用到额外的空间

789
00:28:43,240 --> 00:28:45,130
还是 2 个元素在这边 5个在那边

790
00:28:45,130 --> 00:28:47,910
数组全长7位 所以我没玩花样 对吧

791
00:28:47,910 --> 00:28:51,950
现在 我们这里有Gabe 是数字6 你应该在哪里?

792
00:28:51,950 --> 00:28:52,650
你又走运了

793
00:28:52,650 --> 00:28:53,820
你可以留在这

794
00:28:53,820 --> 00:28:57,210
就稍微往右一步 这样让人知道你是排序好了的

795
00:28:57,210 --> 00:29:00,520
现在我们又碰到了Neil 数字1 你要去哪呢

796
00:29:00,520 --> 00:29:03,540
现在 我们就能开始看到这个算法

797
00:29:03,540 --> 00:29:05,950
虽然可能初看时 觉得还挺聪明 但看一下接下来会发生什么

798
00:29:05,950 --> 00:29:07,370
你可不可以往前一步

799
00:29:07,370 --> 00:29:09,260
我们想把Neil放在哪?

800
00:29:09,260 --> 00:29:11,830
当然是这里 那我们要怎样把Neil放那里呢

801
00:29:11,830 --> 00:29:12,970
让我们一步一步来

802
00:29:12,970 --> 00:29:15,620
Gabe 你要去哪

803
00:29:15,620 --> 00:29:19,590
没错 跨一大步 或是两小步

804
00:29:19,590 --> 00:29:20,820
到这边来

805
00:29:20,820 --> 00:29:21,750
Grace 你要去哪

806
00:29:21,750 --> 00:29:22,510
很好

807
00:29:22,510 --> 00:29:23,500
又是一步

808
00:29:23,500 --> 00:29:24,960
最后 Branson?

809
00:29:24,960 --> 00:29:25,460
又一步

810
00:29:25,460 --> 00:29:27,190
现在我们可以把Neil放进他的位置了

811
00:29:27,190 --> 00:29:28,440
现在 延续这个逻辑

812
00:29:28,440 --> 00:29:32,420
虽然我们没有把Neil移呀呀

813
00:29:32,420 --> 00:29:36,420
移到他的位置去 最坏的情况下 我们看到的下一个数字

814
00:29:36,420 --> 00:29:42,220
可能 比如说 下一个数字是0

815
00:29:42,220 --> 00:29:42,730
那我们就要把这些人都移一遍

816
00:29:42,730 --> 00:29:44,950
假如有-1这个数字 那我们又要

817
00:29:44,950 --> 00:29:46,080
把所有人移一遍

818
00:29:46,080 --> 00:29:48,500
所以我们其实是在把问题反过来

819
00:29:48,500 --> 00:29:52,620
把选择的过程 变成了 插入的过程

820
00:29:52,620 --> 00:29:56,930
也就是说 你们要移到n-某个数字

821
00:29:56,930 --> 00:29:57,940
的步数

822
00:29:57,940 --> 00:30:01,200
而这个数字 当我遇到越来越多的数字时 会不断增长

823
00:30:01,200 --> 00:30:04,730
如果我们断把你们往后 再往后移

824
00:30:04,730 --> 00:30:08,320
所以 让人伤心的是 所有这些算法都是n平方

825
00:30:08,320 --> 00:30:10,570
让我们谢谢这些志愿者

826
00:30:10,570 --> 00:30:11,090
然后用不同的方式来展示一下这个问题

827
00:30:11,090 --> 00:30:12,312
做得很好

828
00:30:12,312 --> 00:30:14,120
[掌声]

829
00:30:14,120 --> 00:30:15,030
好的

830
00:30:15,030 --> 00:30:16,280
这边走

831
00:30:18,390 --> 00:30:18,470
感谢--

832
00:30:18,470 --> 00:30:19,190
我们需要还回数字么

833
00:30:19,190 --> 00:30:21,990
不用 你们可以留着这些数字

834
00:30:21,990 --> 00:30:23,440
好

835
00:30:23,440 --> 00:30:24,100
做得很好

836
00:30:24,100 --> 00:30:25,300
好

837
00:30:25,300 --> 00:30:30,510
现在让我们看看能不能更快地 从视觉上

838
00:30:30,510 --> 00:30:33,410
来总结一下刚才发生的事

839
00:30:36,510 --> 00:30:38,770
让我打开Firefox

840
00:30:38,770 --> 00:30:41,310
我们会把这个展示的链接放到课程网站上

841
00:30:41,310 --> 00:30:43,870
现在Java在一些浏览器上运行得不是太好

842
00:30:43,870 --> 00:30:46,760
所以如果你们在家弄的话 你们可能要用Firefox

843
00:30:46,760 --> 00:30:47,990
它才会运行

844
00:30:47,990 --> 00:30:50,440
我下面要展示的是

845
00:30:50,440 --> 00:30:54,875
在最底下 有一些菜单选择

846
00:30:54,875 --> 00:30:55,840
包括一个 开始 和 停止 键

847
00:30:55,840 --> 00:30:59,450
另外 这些程序里好像有个bug

848
00:30:59,450 --> 00:31:03,720
当你不按住command或alt+键 然后放大

849
00:31:03,720 --> 00:31:06,560
你是看不到开始和停止键的

850
00:31:06,560 --> 00:31:09,090
所以就提醒你们一下 如果你们要在家试着玩的话

851
00:31:09,090 --> 00:31:12,870
现在 我要点击开始键 然后我要规定延迟

852
00:31:12,870 --> 00:31:16,810
大概200毫秒 这样我们就能看见发生什么了

853
00:31:16,810 --> 00:31:20,180
这是第一种算法形象展示

854
00:31:20,180 --> 00:31:23,730
冒泡排序法 也就是我们将人们一对对交换位置

855
00:31:23,730 --> 00:31:27,490
理解这幅图的关键在于 这些柱的高度

856
00:31:27,490 --> 00:31:30,510
代表了数字的大小

857
00:31:30,510 --> 00:31:32,210
所以 柱越高 数字越大

858
00:31:32,210 --> 00:31:33,680
柱越短 数字越小

859
00:31:33,680 --> 00:31:38,630
如果你注意的话 我们在经过这种算法的第一次循环

860
00:31:38,630 --> 00:31:42,620
将大的与小的数字交换位置 这样小的数字

861
00:31:42,620 --> 00:31:44,280
就会在前面 而大的数字会在右边

862
00:31:44,280 --> 00:31:48,770
当我们来到数组尾部 这次长度可不止是7位了

863
00:31:48,770 --> 00:31:49,900
我们就回到最前边

864
00:31:49,900 --> 00:31:51,140
预计一下 会发生这样的事

865
00:31:51,140 --> 00:31:54,860
在最左边 这个小数字会被换到边上

866
00:31:54,860 --> 00:31:56,010
这个过程不断重复

867
00:31:56,010 --> 00:31:59,450
现在这个展示马上就变得无聊了

868
00:31:59,450 --> 00:32:04,170
所以让我让它停下 把延迟调低点

869
00:32:04,170 --> 00:32:05,060
这样就能感受一下这个算法了

870
00:32:05,060 --> 00:32:07,840
虽然我已经让它加速了 这就你是升级我的处理器

871
00:32:07,840 --> 00:32:08,580
买了台新电脑一样

872
00:32:08,580 --> 00:32:12,980
我并没有从根本上改变我的算法 但你可以更清晰地看到

873
00:32:12,980 --> 00:32:16,800
不像我们用人展示时那样 大的数字冒泡到了顶端

874
00:32:16,800 --> 00:32:20,900
小数字冒泡到了底端

875
00:32:20,900 --> 00:32:22,390
现在 这些数字排序好了

876
00:32:22,390 --> 00:32:25,260
另外 在这些正方形里 这只是帮你保存记录

877
00:32:25,260 --> 00:32:28,010
帮你数有刚才一共有多少次的比较

878
00:32:28,010 --> 00:32:28,950
或者说发生了多少次位置交换

879
00:32:28,950 --> 00:32:30,750
让我们再去试刚才看到的另一种方法

880
00:32:30,750 --> 00:32:37,116
让我点击一下这里的冒泡排序法 然后让我选择

881
00:32:37,116 --> 00:32:38,936
这个网页有点问题

882
00:32:38,936 --> 00:32:41,155
我们就冒这个险 再运行

883
00:32:44,560 --> 00:32:45,030
好了

884
00:32:45,030 --> 00:32:47,180
让我们选选择排序法

885
00:32:47,180 --> 00:32:49,140
我不知道为什么菜单从那边出来了

886
00:32:49,140 --> 00:32:54,070
让我们放大一下 把这个bug修好 把这个改成50

887
00:32:54,070 --> 00:32:56,020
让我们更快一点好了

888
00:32:56,020 --> 00:32:59,160
5毫秒 然后 点击开始

889
00:32:59,160 --> 00:33:00,470
这是选择排序法

890
00:33:00,470 --> 00:33:03,070
所以又一次 想一想刚才我们用志愿者的时候发生了什么

891
00:33:03,070 --> 00:33:08,490
我们检查整个数组 选择中最小的元素

892
00:33:08,490 --> 00:33:09,250
一遍又一遍

893
00:33:09,250 --> 00:33:11,110
我说这还是挺糟的

894
00:33:11,110 --> 00:33:15,010
它依然是 n平方 但在真实在世界里

895
00:33:15,010 --> 00:33:18,280
它确实快了一点 因为每一次 我确实都有少做一步

896
00:33:18,280 --> 00:33:19,800
但我们在讲的

897
00:33:19,800 --> 00:33:21,830
这里最多有 差不多40个柱子吧

898
00:33:21,830 --> 00:33:23,200
我们不是在讨论 4000万

899
00:33:23,200 --> 00:33:27,430
所以 我并没有很清楚地看到 提高了多少

900
00:33:27,430 --> 00:33:32,530
让我回去 换成我们的第三种算法

901
00:33:32,530 --> 00:33:33,180
我们选 插入排序法

902
00:33:33,180 --> 00:33:36,380
现在真的问题很大 因为菜单不应该在下面这里的

903
00:33:36,380 --> 00:33:40,840
让我回到上面 然后开始这个算法

904
00:33:40,840 --> 00:33:43,270
开始 停止

905
00:33:43,270 --> 00:33:47,160
这种算法的规律还挺妙的

906
00:33:47,160 --> 00:33:50,240
像当时我们用志愿者一样 这里 我们是把柱子

907
00:33:50,240 --> 00:33:52,620
插入到它们应该在的位置

908
00:33:52,620 --> 00:33:55,430
然后这在我转身前就完成了

909
00:33:55,430 --> 00:33:58,940
但这种算法 理论上 仍旧是n平方

910
00:33:58,940 --> 00:34:01,430
所以让我们看看能不能将以上的总结一下

911
00:34:01,430 --> 00:34:04,750
我要让我们有种简便的方法来讨论这些

912
00:34:04,750 --> 00:34:08,489
所以让我介绍一个概念

913
00:34:08,489 --> 00:34:12,480
你们马上会看到的 叫大O 因为它真的

914
00:34:12,480 --> 00:34:16,320
就是一个很大的O 这是计算机科学家或是数学家

915
00:34:16,320 --> 00:34:19,230
用来形容一个算法运行时间的方式

916
00:34:19,230 --> 00:34:21,400
它到底要花多少步?

917
00:34:21,400 --> 00:34:25,080
不好意思 我手写字很丑

918
00:34:25,080 --> 00:34:29,020
但让我假装 这里的就会是大O

919
00:34:29,020 --> 00:34:33,610
让我再介绍一个符号 大写的 omega

920
00:34:33,610 --> 00:34:37,080
omega将会是大O的反面

921
00:34:37,080 --> 00:34:40,790
big O表示 在最坏的情况下 用n表示 这个算法要花多少步

922
00:34:40,790 --> 00:34:43,480
omega表示的是 最好的情况下

923
00:34:43,480 --> 00:34:45,409
它要花多少时间

924
00:34:45,409 --> 00:34:48,090
我们马上会看到 "最好的情况"是什么意思

925
00:34:48,090 --> 00:34:49,940
让我们从简单的开始

926
00:34:49,940 --> 00:34:54,719
让我从一个线性搜索开始

927
00:34:54,719 --> 00:34:55,679
所以没有排序

928
00:34:55,679 --> 00:34:58,000
我们叫它线性搜索

929
00:34:58,000 --> 00:35:01,140
现在 用这个画出一张表

930
00:35:01,140 --> 00:35:06,600
在线性搜索的情况下 如果是最糟的情形

931
00:35:06,600 --> 00:35:11,770
我想要找到一个数字需要花多少步?

932
00:35:11,770 --> 00:35:14,540
一共有n扇门 也就是n个数字

933
00:35:14,540 --> 00:35:15,940
最坏的情况

934
00:35:15,940 --> 00:35:18,800
我想要在一个有n扇门的数组里找到50这个数字

935
00:35:18,800 --> 00:35:20,830
要花多少步?

936
00:35:20,830 --> 00:35:21,410
n步 为什么?

937
00:35:21,410 --> 00:35:23,680
因为也许我要一个个过一直找到最后

938
00:35:23,680 --> 00:35:27,120
所以就像是Jennifer碰到的情况那样 50在很后面

939
00:35:27,120 --> 00:35:30,760
所以我们说 线性搜索最坏的情况 是n的大O

940
00:35:30,760 --> 00:35:33,430
那最好的情况又是什么呢 如果你真的很幸运的话

941
00:35:33,430 --> 00:35:36,200
只会花一步 或者是一个常数

942
00:35:36,200 --> 00:35:37,830
也就是1

943
00:35:37,830 --> 00:35:39,010
这听上去挺不错

944
00:35:39,010 --> 00:35:41,210
那如果我们做一个二进制搜索呢?

945
00:35:43,860 --> 00:35:47,846
二进制搜索 在最坏的情况下 要花多少时间?

946
00:35:47,846 --> 00:35:49,250
[学生回答]

947
00:35:49,250 --> 00:35:51,310
所以事实上 我听到很多人给了我这个答案

948
00:35:51,310 --> 00:35:56,390
事实上是log n步 因为当我们把它

949
00:35:56,390 --> 00:36:00,730
一分为二 再分为二 再分 我们最终会找到那个值

950
00:36:00,730 --> 00:36:04,750
如果这个值确实在那儿的话 但是有个地方要注意

951
00:36:04,750 --> 00:36:08,590
我们进行二进制搜索 我们默认的前提是什么?

952
00:36:08,590 --> 00:36:09,700
它必须是排序好的

953
00:36:09,700 --> 00:36:12,770
如果它没有被排序  你可以不断把它一分为二

954
00:36:12,770 --> 00:36:15,490
你可以在左边找 或是在右边找 或是左边右边一起找

955
00:36:15,490 --> 00:36:18,070
但如果它没被排序 你是不会在其中找到那个元素

956
00:36:18,070 --> 00:36:18,790
因为你可能过错过它

957
00:36:18,790 --> 00:36:22,120
因为你用的这个规则 在左边还是右边找 如果没先排序好

958
00:36:22,120 --> 00:36:23,420
就会是有问题的

959
00:36:23,420 --> 00:36:26,110
所以要用这种方法的话 这个隐性的付出需要注意

960
00:36:26,110 --> 00:36:29,250
现在 让我们来看我们的排序算法 而不是搜索--

961
00:36:29,250 --> 00:36:31,140
哦 实际上 让我们来填一下这个空

962
00:36:31,140 --> 00:36:33,190
二进制算法最好的情况?

963
00:36:33,190 --> 00:36:36,290
还是1 如果正好是在数组的正中间的话

964
00:36:36,290 --> 00:36:37,810
或者说 是电话黄页的正中间

965
00:36:37,810 --> 00:36:39,710
现在让我们来做冒泡排序

966
00:36:39,710 --> 00:36:42,570
又一次 我们看到的是排序法 还不是搜索了

967
00:36:42,570 --> 00:36:47,220
在最坏的情况下 冒泡法要花多少步?

968
00:36:47,220 --> 00:36:48,410
n平方

969
00:36:48,410 --> 00:36:49,200
我把它画下来

970
00:36:49,200 --> 00:36:51,710
我手写的东西被放大后 看起来更糟了

971
00:36:51,710 --> 00:36:52,510
好

972
00:36:52,510 --> 00:36:53,570
这是n平方

973
00:36:53,570 --> 00:36:59,460
冒泡法最好的情况下 要花多少步?

974
00:36:59,460 --> 00:37:00,980
1我听到有人说

975
00:37:00,980 --> 00:37:01,760
n

976
00:37:01,760 --> 00:37:03,286
n 我听到有人说

977
00:37:03,286 --> 00:37:04,200
2

978
00:37:04,200 --> 00:37:05,010
我听到有人说2

979
00:37:05,010 --> 00:37:06,670
有人说是3么?

980
00:37:06,670 --> 00:37:07,080
好

981
00:37:07,080 --> 00:37:11,390
我听到有人说1 n 2 让我们先看看

982
00:37:11,390 --> 00:37:12,330
第一个答案 1

983
00:37:12,330 --> 00:37:15,370
直觉猜这个很合理 因为符合以上的规律

984
00:37:15,370 --> 00:37:19,670
但是如果只要花1步的话 我要怎样才能确定

985
00:37:19,670 --> 00:37:22,900
这个列表排序好了呢 因为如果我只能做一步的话

986
00:37:22,900 --> 00:37:25,230
我能检查几个元素呢?

987
00:37:25,230 --> 00:37:28,270
只有1个 也就是说 n-1个元素有可能都不在正确的位置上

988
00:37:28,270 --> 00:37:31,310
而我只能靠信念 在检查了一个元素之后

989
00:37:31,310 --> 00:37:31,850
就说这已经排序好了

990
00:37:31,850 --> 00:37:33,930
所以1不是正确答案

991
00:37:33,930 --> 00:37:35,710
所以我最少要看多少个呢?

992
00:37:35,710 --> 00:37:36,680
[学生回答]

993
00:37:36,680 --> 00:37:40,160
n-1个 或者说 n个 因为我需要看

994
00:37:40,160 --> 00:37:42,190
所有的元素 来确定它们顺序都正确

995
00:37:42,190 --> 00:37:44,750
但 我们把那个-1给去掉了 因为我们预设说

996
00:37:44,750 --> 00:37:47,100
n越大 它们就越无趣了

997
00:37:47,100 --> 00:37:48,380
这就是冒泡排序法

998
00:37:48,380 --> 00:37:49,830
现在 让我们再做剩下的两个方法

999
00:37:49,830 --> 00:37:53,520
选择排序法 然后是插入排序法

1000
00:37:53,520 --> 00:37:57,160
然后我们会用一个比它们好得多的方法

1001
00:37:57,160 --> 00:37:58,926
来让你们大吃一惊

1002
00:37:58,926 --> 00:38:00,410
好

1003
00:38:00,410 --> 00:38:04,700
选择排序法里最坏的情况要花多少时间

1004
00:38:04,700 --> 00:38:05,680
n平方

1005
00:38:05,680 --> 00:38:06,710
我听到有人说n平方

1006
00:38:06,710 --> 00:38:09,790
但为什么你说是n平方呢

1007
00:38:09,790 --> 00:38:11,170
因为我们刚才做过了

1008
00:38:11,170 --> 00:38:12,260
因为我们刚才做过了

1009
00:38:12,260 --> 00:38:12,550
好

1010
00:38:12,550 --> 00:38:13,380
回答得好

1011
00:38:13,380 --> 00:38:16,660
但是直觉上来说 为什么选择排序法是n平方

1012
00:38:16,660 --> 00:38:18,980
我们要一次又一次地做什么呢?

1013
00:38:18,980 --> 00:38:22,570
我们要一停地扫描过去 问 你是最小的么

1014
00:38:22,570 --> 00:38:24,020
你是最小的么 你是最小的么

1015
00:38:24,020 --> 00:38:27,480
我们要花n步 然后是n-1 然后是n-2

1016
00:38:27,480 --> 00:38:30,700
但如果你把它们加起来

1017
00:38:30,700 --> 00:38:34,810
或者相信我已经提前加好了 我们大概会得到n平方减去一个很小的数字

1018
00:38:34,810 --> 00:38:36,730
所以我就算它是n平方

1019
00:38:36,730 --> 00:38:39,530
那么 选择排序法里的最好的情况下

1020
00:38:39,530 --> 00:38:40,632
要花我多少步呢?

1021
00:38:40,632 --> 00:38:41,840
[学生回答]

1022
00:38:41,840 --> 00:38:44,350
不幸的是 还是n平方 对不对

1023
00:38:44,350 --> 00:38:49,590
因为我是在选择最小的元素 而我们有7个人在这

1024
00:38:49,590 --> 00:38:53,280
我只知道 我要到最后面 才能找到最小的数字

1025
00:38:53,280 --> 00:38:55,670
无论她或他先前是在哪

1026
00:38:55,670 --> 00:38:58,820
但我要怎样找到次小的数字?

1027
00:38:58,820 --> 00:39:00,160
我要重新过一遍

1028
00:39:00,160 --> 00:39:04,810
所以在最好的情况下 选择排序法的input是什么

1029
00:39:04,810 --> 00:39:07,830
是一个已经排序好的表 1 2 3 4

1030
00:39:07,830 --> 00:39:08,600
但我是一个电脑

1031
00:39:08,600 --> 00:39:10,190
我一次只能看一样东西

1032
00:39:10,190 --> 00:39:12,465
我不能像人类一样 退后一步 然后说

1033
00:39:12,465 --> 00:39:14,030
哦 这个看上去顺序是对的

1034
00:39:14,030 --> 00:39:17,580
在选择排序法中 要让我宣布排序正确 我只能

1035
00:39:17,580 --> 00:39:18,370
去选择最小的数字

1036
00:39:18,370 --> 00:39:21,390
但就算我第一下就找到了数字1 我也不知道其他的数字是怎样

1037
00:39:21,390 --> 00:39:24,460
我只知道 有人给了我一个数组

1038
00:39:24,460 --> 00:39:27,930
或者是一组门 门后有数字 我想要知道 1是不是最小的数字

1039
00:39:27,930 --> 00:39:28,680
唯一的方法是

1040
00:39:28,680 --> 00:39:32,440
我要到最后 然后意识到 糟了 1确实是最小的数字

1041
00:39:32,440 --> 00:39:34,870
但我要怎样才能确定2是次小的数字?

1042
00:39:34,870 --> 00:39:38,350
我要再进行一次这种低效率的工作

1043
00:39:38,350 --> 00:39:42,210
所以最后 用插入排序法 最坏的情况

1044
00:39:42,210 --> 00:39:44,990
会是怎样?

1045
00:39:44,990 --> 00:39:49,100
还是n平方

1046
00:39:49,100 --> 00:39:53,020
那最好的情况呢?

1047
00:39:53,020 --> 00:39:56,282
我们在这留个悬念

1048
00:39:56,282 --> 00:40:00,090
下一次 我们会揭开谜底

1049
00:40:00,090 --> 00:40:02,620
但让我提议 我们要在根本上 做到更好 好不好

1050
00:40:02,620 --> 00:40:05,220
所以自己想一想 插入排序法会是怎样

1051
00:40:05,220 --> 00:40:06,910
好像并没有太戏剧化

1052
00:40:06,910 --> 00:40:08,970
因为我是唯一一个看到变化的人

1053
00:40:08,970 --> 00:40:09,620
哇

1054
00:40:09,620 --> 00:40:10,420
好

1055
00:40:10,420 --> 00:40:12,615
所以这里我们有了一个不同的展示

1056
00:40:12,615 --> 00:40:16,580
如果我在这边放大 你们会看到在左边 我们有冒泡法

1057
00:40:16,580 --> 00:40:20,740
在中间 我们有选择法 在最右边

1058
00:40:20,740 --> 00:40:23,380
是我们还没有讲到的 归并排序法

1059
00:40:23,380 --> 00:40:26,080
但想一下今天为止 我们都做了什么

1060
00:40:26,080 --> 00:40:29,200
当Jennifer上台来时 我们检查了这一数组的数字

1061
00:40:29,200 --> 00:40:33,750
一次 又一次 用的是线性搜索 然后我们得到了线性的运行时间

1062
00:40:33,750 --> 00:40:35,100
也就是n的大O

1063
00:40:35,100 --> 00:40:41,000
当我们现在来想我们课的第一周里 我们用了分治处理法

1064
00:40:41,000 --> 00:40:43,740
我们撕了电话黄页 同Jennifer 我们一起发现关键在于

1065
00:40:43,740 --> 00:40:47,500
不断重复你在做的事

1066
00:40:47,500 --> 00:40:50,930
不断地丢掉一半的问题

1067
00:40:50,930 --> 00:40:55,320
或者说 将问题分成两半 然后将更小的那一半

1068
00:40:55,320 --> 00:40:59,630
视作去另一半相同

1069
00:40:59,630 --> 00:41:00,910
这样 我们确实从根本上 有了提高

1070
00:41:00,910 --> 00:41:04,720
但是用冒泡法 选择法或是插入法

1071
00:41:04,720 --> 00:41:06,560
我们并没有像Jennifer那样发现关键

1072
00:41:06,560 --> 00:41:10,220
我们只是来来回回看来看去

1073
00:41:10,220 --> 00:41:12,650
改了一点小地方 交换了位置

1074
00:41:12,650 --> 00:41:13,730
可能进行了插入或者选择

1075
00:41:13,730 --> 00:41:16,950
但是总而言之 我很尴尬地来来回回很多次

1076
00:41:16,950 --> 00:41:21,160
我们并没有像Jennifer那样

1077
00:41:21,160 --> 00:41:22,040
聪明地去分割 去解决问题

1078
00:41:22,040 --> 00:41:25,620
所以 我们下周会讲到的归并排序法 正相反

1079
00:41:25,620 --> 00:41:29,540
利用了关键的一点 就是将input减半

1080
00:41:29,540 --> 00:41:30,580
减半 再减半

1081
00:41:30,580 --> 00:41:34,590
每一次经过循环 排序左半边 然后右半边

1082
00:41:34,590 --> 00:41:38,200
然后是左半边的左半边 然后是左半边的右半边

1083
00:41:38,200 --> 00:41:40,990
然后是右半边的左半边 然后是右半边的右半边

1084
00:41:40,990 --> 00:41:42,840
然后不断重复

1085
00:41:42,840 --> 00:41:46,170
你们会看到形象地展示的 但是会在下一周

1086
00:41:46,170 --> 00:41:49,760
总得来说 当我们仔细想一想这种问题后

1087
00:41:52,435 --> 00:41:57,970
我们在左边 有n平方 在中间也有n平方

1088
00:41:57,970 --> 00:41:59,400
在右边 有log n

1089
00:41:59,400 --> 00:42:00,590
这是真正留给你们的悬念

1090
00:42:00,590 --> 00:42:02,040
下周一见

1091
00:42:02,040 --> 00:42:05,163
[掌声]