1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [音乐播放]

3
00:00:10,800 --> 00:00:13,500
国宝马兰所有权利。

4
00:00:13,500 --> 00:00:14,670
好吧，欢迎回来。

5
00:00:14,670 --> 00:00:18,120
因此，这是第4周，开始
其已经。

6
00:00:18,120 --> 00:00:21,320
你还记得，上周，我们把
编码一旁只是一点点

7
00:00:21,320 --> 00:00:24,240
我们开始交谈多一点
高层次，一样的东西

8
00:00:24,240 --> 00:00:28,130
搜索和排序，这虽然
有些简单的想法，

9
00:00:28,130 --> 00:00:31,840
代表的一类问题
你将开始解决特别

10
00:00:31,840 --> 00:00:34,820
当你开始思考最终
项目和有趣的解决方案

11
00:00:34,820 --> 00:00:36,760
可能有现实世界的问题。

12
00:00:36,760 --> 00:00:39,490
现在是一个最简单的冒泡排序
这样的算法，它

13
00:00:39,490 --> 00:00:42,900
通过这些小的数字工作
在一个列表中，或在一个数组中种

14
00:00:42,900 --> 00:00:46,530
泡自己的方式到顶部，
大的数字移动一路下跌至

15
00:00:46,530 --> 00:00:47,930
该列表的末尾。

16
00:00:47,930 --> 00:00:50,650
>> 记得我们可以想象
一点点的冒泡排序

17
00:00:50,650 --> 00:00:52,310
这样的事情。

18
00:00:52,310 --> 00:00:53,640
所以，让我继续前进，单击“开始”。

19
00:00:53,640 --> 00:00:55,350
我预选冒泡排序。

20
00:00:55,350 --> 00:00:58,920
如果你还记得，高大的蓝色
线代表大号码，小

21
00:00:58,920 --> 00:01:03,300
蓝线代表小数字，
我们通过这一而再，再而

22
00:01:03,300 --> 00:01:07,680
再次，比较相邻的两间酒吧
红色，我们要交换

23
00:01:07,680 --> 00:01:11,010
最大的和最小的，如果
他们秩序。

24
00:01:11,010 --> 00:01:14,150
>> 因此，这会去，去，去
，你会看到，较大的

25
00:01:14,150 --> 00:01:16,700
元素使他们的方式
的权利，而较小的元素是

26
00:01:16,700 --> 00:01:17,900
使他们的方式到左边。

27
00:01:17,900 --> 00:01:21,380
但我们开始量化
效率，

28
00:01:21,380 --> 00:01:22,970
在此算法中的质量。

29
00:01:22,970 --> 00:01:25,200
和我们说，在最坏
情况下，该算法采取了

30
00:01:25,200 --> 00:01:27,940
大约多少步？

31
00:01:27,940 --> 00:01:28,980
>> 因此n的平方。

32
00:01:28,980 --> 00:01:30,402
什么是N？

33
00:01:30,402 --> 00:01:31,650
>> 观众：元素数目。

34
00:01:31,650 --> 00:01:32,790
>> 国宝马兰因此n
数目的元素。

35
00:01:32,790 --> 00:01:33,730
所以我们经常这样做。

36
00:01:33,730 --> 00:01:36,650
任何时候，我们要谈论的大小
一个问题或大小的

37
00:01:36,650 --> 00:01:39,140
输入，或花费的时间量
以产生输出，我们只

38
00:01:39,140 --> 00:01:41,610
广义的任何
输入为n。

39
00:01:41,610 --> 00:01:45,970
因此，早在第0周，数页
在电话簿为n。

40
00:01:45,970 --> 00:01:47,550
学生人数
在房间里为：N。

41
00:01:47,550 --> 00:01:49,630
所以在这里，太，我们继
这个模式。

42
00:01:49,630 --> 00:01:52,800
>> 现在Ñ平方是不是特别
快，所以我们试图做的更好。

43
00:01:52,800 --> 00:01:55,970
因此，我们看着一对夫妇
其他的算法，其中

44
00:01:55,970 --> 00:01:57,690
选择排序。

45
00:01:57,690 --> 00:01:59,180
所以选择排序
有一点不同。

46
00:01:59,180 --> 00:02:03,130
这几乎是简单的，我敢说，
由此开始的开始

47
00:02:03,130 --> 00:02:06,740
我们的志愿者名单，我只是再次
一次又一次经历

48
00:02:06,740 --> 00:02:10,060
列表，采摘最小
在一个时间元素，并把他或

49
00:02:10,060 --> 00:02:13,040
她在列表的开头。

50
00:02:13,040 --> 00:02:16,410
>> 但是它也同样，一旦我们开始思考
通过数学和更大的

51
00:02:16,410 --> 00:02:19,860
图片，想过多少次
我正想来回和背部

52
00:02:19,860 --> 00:02:24,090
奔波，我们说，在最坏的情况下，
太多，选择排序，那是什么？

53
00:02:24,090 --> 00:02:24,960
摆正Ń。

54
00:02:24,960 --> 00:02:27,490
现在，在现实世界中，它可能
实际上是稍快。

55
00:02:27,490 --> 00:02:30,620
因为再次，我没有保持
回溯一旦我排序

56
00:02:30,620 --> 00:02:31,880
最小的元素。

57
00:02:31,880 --> 00:02:35,090
但是，如果我们想想n很大，
如果你的，做出来的数学

58
00:02:35,090 --> 00:02:39,170
我在黑板上，与n的平方
减去的东西，一切

59
00:02:39,170 --> 00:02:41,850
除了n个平方，一旦N
变得非常大，不

60
00:02:41,850 --> 00:02:42,850
真正的问题一样多。

61
00:02:42,850 --> 00:02:45,470
因此，作为计算机科学家，我们的排序
视而不见较小

62
00:02:45,470 --> 00:02:49,220
因素和只注重的因素
一个表达式，将会使

63
00:02:49,220 --> 00:02:50,330
最大的区别。

64
00:02:50,330 --> 00:02:52,840
>> 好了，最后，我们看了
在插入排序。

65
00:02:52,840 --> 00:02:56,620
这是类似的精神，但
而不是通过迭代

66
00:02:56,620 --> 00:03:01,250
选择最小的元素之一，在
的时间，我只花了我的手

67
00:03:01,250 --> 00:03:04,070
处理，我决定，所有
没错，你属于这里。

68
00:03:04,070 --> 00:03:06,160
然后我转移到下一个元素
并决定，他或

69
00:03:06,160 --> 00:03:07,470
她属于这里。

70
00:03:07,470 --> 00:03:08,810
然后，我和移动。

71
00:03:08,810 --> 00:03:11,780
我可能会，一路走来，
以这些家伙转移

72
00:03:11,780 --> 00:03:13,030
为他们腾出空间。

73
00:03:13,030 --> 00:03:16,880
所以这是样的心理逆转
选择排序，我们

74
00:03:16,880 --> 00:03:18,630
所谓插入排序。

75
00:03:18,630 --> 00:03:20,810
>> 因此，这些主题发生
在现实世界中。

76
00:03:20,810 --> 00:03:23,640
仅仅在几年前，当达到一定
参议员竞选总统，

77
00:03:23,640 --> 00:03:27,160
，在当时的CEO埃里克·施密特（Eric Sc​​hmidt）
谷歌，居然有机会

78
00:03:27,160 --> 00:03:28,040
采访他。

79
00:03:28,040 --> 00:03:32,010
我们认为我们会分享此YouTube
夹你在这里，如果我们可以将

80
00:03:32,010 --> 00:03:32,950
音量。

81
00:03:32,950 --> 00:03:39,360
>> [视频回放]

82
00:03:39,360 --> 00:03:44,620
>> 现在，参议员，你在谷歌，
我喜欢把总统

83
00:03:44,620 --> 00:03:46,042
作为一个工作面试。

84
00:03:46,042 --> 00:03:47,770
>> [笑]

85
00:03:47,770 --> 00:03:50,800
>> 现在它是很难得到
一个工作作为总统。

86
00:03:50,800 --> 00:03:52,480
你要通过
现在的严峻考验。

87
00:03:52,480 --> 00:03:54,330
这也很难在谷歌找到一份工作。

88
00:03:54,330 --> 00:03:59,610
我们有问题，我们要求
我们的候选人的问题。

89
00:03:59,610 --> 00:04:02,250
而这一次是从拉里·施维默。

90
00:04:02,250 --> 00:04:05,325
>> [笑]

91
00:04:05,325 --> 00:04:06,400
你们觉得我在开玩笑吗？

92
00:04:06,400 --> 00:04:08,750
就是这里。

93
00:04:08,750 --> 00:04:12,110
这是最有效的方式来
排序一百万两位整数？

94
00:04:12,110 --> 00:04:15,810
>> [笑]

95
00:04:15,810 --> 00:04:18,260
>> 嗯，呃 - 

96
00:04:18,260 --> 00:04:19,029
>> 我很抱歉。

97
00:04:19,029 --> 00:04:19,745
也许我们应该 - 

98
00:04:19,745 --> 00:04:21,000
>> 不，不，不，不，不。

99
00:04:21,000 --> 00:04:21,470
>> 这不是一个 - 

100
00:04:21,470 --> 00:04:22,185
确定。

101
00:04:22,185 --> 00:04:25,328
>> 我认为冒泡排序
是错误的方式去。

102
00:04:25,328 --> 00:04:26,792
>> [笑]

103
00:04:26,792 --> 00:04:28,510
>> [欢呼和掌声]

104
00:04:28,510 --> 00:04:31,211
>> 来吧，谁告诉他这个呢？

105
00:04:31,211 --> 00:04:32,155
确定。

106
00:04:32,155 --> 00:04:33,350
>> [END视频播放]

107
00:04:33,350 --> 00:04:35,070
>> 国宝MALAN：所以你有它。

108
00:04:35,070 --> 00:04:39,600
于是我们开始量化这些运行
倍，所以说话，用的东西

109
00:04:39,600 --> 00:04:43,480
被称为渐近符号，这是
刚刚提到我们转向排序

110
00:04:43,480 --> 00:04:47,420
视而不见，那些规模较小的因素，
只盯着运行时间，

111
00:04:47,420 --> 00:04:51,250
这些算法的性能
为n随着时间的推移变得非常大。

112
00:04:51,250 --> 00:04:55,110
因此，我们介绍大澳大O
代表的东西，我们认为

113
00:04:55,110 --> 00:04:57,000
作为一个上限。

114
00:04:57,000 --> 00:04:59,570
巴里，而实际上，我们可以降低
比话筒一点点？

115
00:04:59,570 --> 00:05:01,040
>> 我们认为这是一个上限。

116
00:05:01,040 --> 00:05:04,710
因此，大O在n的平方手段
最坏的情况下，类似的东西

117
00:05:04,710 --> 00:05:07,780
选择排序
平方步骤Ń。

118
00:05:07,780 --> 00:05:10,310
或类似的东西插入排序
将Ñ平方步骤。

119
00:05:10,310 --> 00:05:15,150
现在像插入
排序，最坏的情况是什么？

120
00:05:15,150 --> 00:05:18,200
给定一个数组，什么是最糟糕的
可能发生的情况，你可能会发现

121
00:05:18,200 --> 00:05:20,650
自己面临着？

122
00:05:20,650 --> 00:05:21,860
>> 它是完全向后，对不对？

123
00:05:21,860 --> 00:05:24,530
因为如果它是完全向后，
你所要做的一大堆工作。

124
00:05:24,530 --> 00:05:26,420
因为如果你完全向后，
你要找到

125
00:05:26,420 --> 00:05:28,840
这里最大的元素，即使
它属于那里。

126
00:05:28,840 --> 00:05:31,140
所以，你说，所有的权利，
时间在这一刻，你属于这里，

127
00:05:31,140 --> 00:05:32,310
所以你离开单干。

128
00:05:32,310 --> 00:05:35,425
>> 然后你意识到，哦，该死的，我要
移动这种略小的元素

129
00:05:35,425 --> 00:05:36,470
左侧。

130
00:05:36,470 --> 00:05:38,770
然后我再这样做
一遍又一遍。

131
00:05:38,770 --> 00:05:41,410
如果我来回走了，你
会有点感觉的表现

132
00:05:41,410 --> 00:05:45,540
这个算法，我因为不断
其他人倒在洗牌

133
00:05:45,540 --> 00:05:46,510
阵列，以腾出空间。

134
00:05:46,510 --> 00:05:47,750
因此，这是最坏的情况。

135
00:05:47,750 --> 00:05:48,570
>> 与此相反 - 

136
00:05:48,570 --> 00:05:50,320
这是一个扣人心弦的最后一次 - 

137
00:05:50,320 --> 00:05:54,065
我们说，插入排序
是欧米茄的什么？

138
00:05:54,065 --> 00:05:57,530
什么是最好的情况下运行
插入排序的时间吗？

139
00:05:57,530 --> 00:05:58,520
所以它实际上ñ。

140
00:05:58,520 --> 00:06:00,980
这是我们离开的空白
在黑板上的最后一次。

141
00:06:00,980 --> 00:06:03,160
>> 欧米茄的n，因为为什么呢？

142
00:06:03,160 --> 00:06:06,630
那么，在最好的情况下，有什么
插入排序将要移交？

143
00:06:06,630 --> 00:06:09,830
好了，完全排序的列表
已经最小的工作要做。

144
00:06:09,830 --> 00:06:12,460
但是，什么是整齐插入排序
是，由于开始

145
00:06:12,460 --> 00:06:15,340
决定，哦，你的号码
一，你属于这里。

146
00:06:15,340 --> 00:06:16,970
哦，什么好运。

147
00:06:16,970 --> 00:06:17,740
>> 你两个数。

148
00:06:17,740 --> 00:06:19,030
你也属于这里。

149
00:06:19,030 --> 00:06:21,010
三，甚至更好，
你属于这里。

150
00:06:21,010 --> 00:06:25,210
只要它得到的末尾
列表中，每次插入排序的伪代码

151
00:06:25,210 --> 00:06:28,010
我们走过口头
最后一次，它的工作要做。

152
00:06:28,010 --> 00:06:32,790
但选择排序，相比之下，
不停地做什么？

153
00:06:32,790 --> 00:06:35,260
>> 持续通过列表
一遍又一遍。

154
00:06:35,260 --> 00:06:39,160
因为关键的洞察力，只有
一旦你看了一路

155
00:06:39,160 --> 00:06:42,500
列表末尾您可以肯定
选定的元素

156
00:06:42,500 --> 00:06:45,560
确实是目前最小的元素。

157
00:06:45,560 --> 00:06:48,920
因此，这些不同的心智模式结束
高达产生一些很现实世界

158
00:06:48,920 --> 00:06:53,130
为我们的差异，以及这些
理论渐近差异。

159
00:06:53,130 --> 00:06:56,910
>> 因此，只要回顾一下，然后，大O的n
平方，我们已经看到了一些这样的

160
00:06:56,910 --> 00:06:58,350
迄今为止算法。

161
00:06:58,350 --> 00:06:59,580
大OŃ？

162
00:06:59,580 --> 00:07:02,870
什么是算法，
可以说是大O的n？

163
00:07:02,870 --> 00:07:06,930
在最坏的情况下，它需要
一个线性的步数。

164
00:07:06,930 --> 00:07:07,810
>> OK，线性搜索。

165
00:07:07,810 --> 00:07:10,470
而在最坏的情况下，其中是
你要找的元素时，

166
00:07:10,470 --> 00:07:12,950
应用线性搜索？

167
00:07:12,950 --> 00:07:14,680
>> 行，在最坏的情况下，
它甚至不存在。

168
00:07:14,680 --> 00:07:17,000
或者在最坏的情况下，它
一路到底，这是

169
00:07:17,000 --> 00:07:18,880
加或减去一个单步的差异。

170
00:07:18,880 --> 00:07:21,180
因此，在一天结束时，
我们可以说，它是线性的。

171
00:07:21,180 --> 00:07:23,910
大O n的线性搜索，
在最坏的情况下，因为

172
00:07:23,910 --> 00:07:26,610
元素甚至不存在，或者它
所有的方式在结束。

173
00:07:26,610 --> 00:07:29,370
>> 嗯，大O n的日志。

174
00:07:29,370 --> 00:07:32,760
我们没有讲的很详细，关于
这一点，但我们已经看到了这一点。

175
00:07:32,760 --> 00:07:36,840
运行在所谓的对数
时间，在最坏的情况下？

176
00:07:36,840 --> 00:07:38,500
>> 是啊，所以二进制搜索。

177
00:07:38,500 --> 00:07:42,930
在最坏的情况下，和二进制搜索
可能具有元素中某处

178
00:07:42,930 --> 00:07:45,640
中间，或某处
阵列内。

179
00:07:45,640 --> 00:07:48,040
但你只找到它，一旦你
将列表的一半，在

180
00:07:48,040 --> 00:07:48,940
半，一半的一半。

181
00:07:48,940 --> 00:07:50,200
然后瞧，它的存在。

182
00:07:50,200 --> 00:07:52,500
再或者，最坏的情况下，
它甚至不存在。

183
00:07:52,500 --> 00:07:56,770
但你不知道它不存在
，直到你达到这最后

184
00:07:56,770 --> 00:08:00,470
最底层的元素减半
和减半减半。

185
00:08:00,470 --> 00:08:01,400
>> 大O 1。

186
00:08:01,400 --> 00:08:03,540
因此，我们可以大O 2，大O 3。

187
00:08:03,540 --> 00:08:06,260
任何时候你想只是一个常数，
我们仅仅只是简化排序

188
00:08:06,260 --> 00:08:07,280
，大O 1。

189
00:08:07,280 --> 00:08:10,440
即使如果现实的，它需要
2甚至100步，如果它是一个

190
00:08:10,440 --> 00:08:13,680
恒定数量的步骤，
我们只是说大O 1。

191
00:08:13,680 --> 00:08:15,930
什么是算法，
在大O 1？

192
00:08:15,930 --> 00:08:18,350
>> 观众：查找长度
一个变量。

193
00:08:18,350 --> 00:08:21,090
>> 国宝马兰：寻找
一个变量的长度？

194
00:08:21,090 --> 00:08:23,870
>> 观众：没有，长度
如果它已经排序。

195
00:08:23,870 --> 00:08:24,160
>> 国宝马兰：好。

196
00:08:24,160 --> 00:08:27,850
OK，所以寻找的东西的长度
如果长度的东西，如

197
00:08:27,850 --> 00:08:30,020
被存储在一个数组中，一些变量。

198
00:08:30,020 --> 00:08:33,380
因为你可以读取该变量，
或打印变量，或

199
00:08:33,380 --> 00:08:34,960
只是一般访问该变量。

200
00:08:34,960 --> 00:08:37,299
瞧，这需要恒定的时间。

201
00:08:37,299 --> 00:08:38,909
>> 相比之下，回想起划伤。

202
00:08:38,909 --> 00:08:42,460
回想第一周的C，
仅调用printf和打印

203
00:08:42,460 --> 00:08:46,240
屏幕上的东西可以说是
恒定的时间，因为它只是需要

204
00:08:46,240 --> 00:08:50,880
一些CPU周期数显示
该屏幕上的文字。

205
00:08:50,880 --> 00:08:52,720
或等待 - 它吗？

206
00:08:52,720 --> 00:08:56,430
否则怎么可能我们模型
printf的表现？

207
00:08:56,430 --> 00:09:00,420
有人会不以为然，
也许这不是真的恒定的时间吗？

208
00:09:00,420 --> 00:09:03,600
在什么意义上的printf可能运行
时间，实际打印字符串

209
00:09:03,600 --> 00:09:05,580
屏幕，是
不变以外。

210
00:09:05,580 --> 00:09:07,860
>> 观众：[听不清]。

211
00:09:07,860 --> 00:09:08,230
>> DAVID马兰：是啊。

212
00:09:08,230 --> 00:09:09,300
因此，它取决于我们的角度来看。

213
00:09:09,300 --> 00:09:13,390
如果我们真的想输入
作为字符串的printf，

214
00:09:13,390 --> 00:09:16,380
因此，我们测量的大小，
输入的长度 - 所以姑且称之为

215
00:09:16,380 --> 00:09:17,780
该长度为n，以及 - 

216
00:09:17,780 --> 00:09:21,990
可以说，printf是本身的n大O
因为它会带你n步

217
00:09:21,990 --> 00:09:24,750
打印出与N
字符，最有可能的。

218
00:09:24,750 --> 00:09:27,730
至少，我们假设的程度
也许它使用for循环

219
00:09:27,730 --> 00:09:28,560
引擎盖下。

220
00:09:28,560 --> 00:09:30,860
>> 不过，我们将不得不看
编写更好地理解它。

221
00:09:30,860 --> 00:09:33,650
而事实上，一旦你们开始
分析自己的算法，你会

222
00:09:33,650 --> 00:09:34,900
从字面上做到这一点。

223
00:09:34,900 --> 00:09:37,765
眼球排序的代码，并认为
 - 所有的权利，我有这样的循环

224
00:09:37,765 --> 00:09:41,870
否则我这里有一个嵌套循环，
做N事物n次，

225
00:09:41,870 --> 00:09:46,050
可以按自己的方式的原因
通过代码，即使它是

226
00:09:46,050 --> 00:09:47,980
伪代码，而不是实际的代码。

227
00:09:47,980 --> 00:09:49,730
>> 那么欧米茄n的平方？

228
00:09:49,730 --> 00:09:53,582
这是一个算法，在最好的
的情况下，仍然采取Ñ平方的步骤吗？

229
00:09:53,582 --> 00:09:54,014
是吗？

230
00:09:54,014 --> 00:09:54,880
>> 观众：[听不清]。

231
00:09:54,880 --> 00:09:55,900
>> 国宝马兰：所以选择排序。

232
00:09:55,900 --> 00:09:59,150
因为在这个问题确实减少
这样的事实，再次，我不知道

233
00:09:59,150 --> 00:10:02,600
我发现目前最小的，直到
我检查了所有的混账元素。

234
00:10:02,600 --> 00:10:08,050
因此，欧米茄，我们说，正
只是想出了一个。

235
00:10:08,050 --> 00:10:09,300
插入排序。

236
00:10:09,300 --> 00:10:12,370
如果列表进行排序发生
已经在最好的情况下，我们只需要

237
00:10:12,370 --> 00:10:15,090
通过一次，
在这一点上，我们肯定。

238
00:10:15,090 --> 00:10:17,890
然后，可以说
是线性的，是肯定的。

239
00:10:17,890 --> 00:10:20,570
>> 什么欧米加1？

240
00:10:20,570 --> 00:10:23,790
什么，在最好的情况下，可能需要
固定数量的步骤？

241
00:10:23,790 --> 00:10:27,220
所以线性搜索，如果你只是很幸运
和你要找的元素

242
00:10:27,220 --> 00:10:31,000
在列表的开头是正确的，
如果这是您在何处开始

243
00:10:31,000 --> 00:10:33,070
线性遍历该列表。

244
00:10:33,070 --> 00:10:35,180
>> 而这，是真正的
一些东西。

245
00:10:35,180 --> 00:10:37,660
举例来说，即使二进制
搜寻欧米加1。

246
00:10:37,660 --> 00:10:40,310
因为如果你得到真正的织补
幸运和咂嘴-DAB的中间

247
00:10:40,310 --> 00:10:42,950
您的阵列是多少
你要买什么？

248
00:10:42,950 --> 00:10:45,730
所以，你可以得到幸运，以及。

249
00:10:45,730 --> 00:10:49,190
>> 这其中，最后，ωn日志n。

250
00:10:49,190 --> 00:10:52,573
因此n日志n，我们并没有真正
谈谈，但 - 

251
00:10:52,573 --> 00:10:53,300
>> 观众：合并排序？

252
00:10:53,300 --> 00:10:53,960
>> 国宝马兰：合并排序。

253
00:10:53,960 --> 00:10:56,920
这是扣人心弦的最后时间，
我们提出，我们发现

254
00:10:56,920 --> 00:10:58,600
视觉上，有算法。

255
00:10:58,600 --> 00:11:02,470
并合并排序只是一个这样的
基本上是更快的算法，该算法

256
00:11:02,470 --> 00:11:03,450
一些这些家伙。

257
00:11:03,450 --> 00:11:07,800
事实上，合并潜在不仅在
当n日志N，在最坏的

258
00:11:07,800 --> 00:11:09,460
当n日志Ń的。

259
00:11:09,460 --> 00:11:14,540
而当你有这样的巧合
欧米茄和大O是同样的事情？

260
00:11:14,540 --> 00:11:17,310
事实上，我们可以描述什么
称为θ，然而它是一个

261
00:11:17,310 --> 00:11:18,220
少一些常见的。

262
00:11:18,220 --> 00:11:21,730
但是，这只是意味着两个界限，
在这种情况下是相同的。

263
00:11:21,730 --> 00:11:25,770
>> 所以合并排序，这是什么
真正归结到我们吗？

264
00:11:25,770 --> 00:11:27,000
嗯，记得的动机。

265
00:11:27,000 --> 00:11:30,340
让我拉起另一个动画
我们没有看最后一次。

266
00:11:30,340 --> 00:11:33,390
这一次，同样的想法，但
它是一个更大一点。

267
00:11:33,390 --> 00:11:36,160
而且我要继续前进并指出
第一 - 我们有插入排序

268
00:11:36,160 --> 00:11:39,410
左上角，然后选择排序，
冒泡排序，一对夫妇的其他种类 - 

269
00:11:39,410 --> 00:11:42,670
外壳和快速 - 我们没有谈到
，堆和归并排序。

270
00:11:42,670 --> 00:11:47,090
>> 因此，至少尽量集中你的眼睛
顶端3的左边，然后

271
00:11:47,090 --> 00:11:49,120
归并排序，当我点击
这个绿色的箭头。

272
00:11:49,120 --> 00:11:51,900
不过，我就让所有的人都跑，只是
让你感受到的多样性

273
00:11:51,900 --> 00:11:53,980
在世界上存在的算法。

274
00:11:53,980 --> 00:11:56,180
我打算让这个运行
短短的几秒钟。

275
00:11:56,180 --> 00:11:59,640
如果你专注于你的眼睛 - 挑
算法，它只是一个专注于

276
00:11:59,640 --> 00:12:02,970
秒 - 你将开始看到了
模式，它的实施。

277
00:12:02,970 --> 00:12:04,530
>> 归并排序，通知，就完成了。

278
00:12:04,530 --> 00:12:06,430
堆排序，快速排序，壳 - 

279
00:12:06,430 --> 00:12:09,480
如此看来，我们推出三
最差算法上周。

280
00:12:09,480 --> 00:12:12,960
但是，这是很好的，我们今天在这里
看归并排序，这是一个

281
00:12:12,960 --> 00:12:16,500
容易的是看，甚至
虽然它可能会弯曲你的心

282
00:12:16,500 --> 00:12:17,490
只是一点点。

283
00:12:17,490 --> 00:12:21,130
在这里我们可以看到多少
选择排序吸。

284
00:12:21,130 --> 00:12:24,600
>> 但在另一面，它是
确实很容易实现。

285
00:12:24,600 --> 00:12:28,160
也许P设置3，这是一个
算法选择实施

286
00:12:28,160 --> 00:12:28,960
标准版。

287
00:12:28,960 --> 00:12:30,970
完美的罚款，完全正确的。

288
00:12:30,970 --> 00:12:35,210
>> 但同样，当n变大，如果你
选择来实现更快的算法

289
00:12:35,210 --> 00:12:39,020
喜欢归并排序，赔率是较大且
更大的投入，你的代码仅仅是

290
00:12:39,020 --> 00:12:39,800
要跑得更快。

291
00:12:39,800 --> 00:12:41,090
您的网站更好的工作。

292
00:12:41,090 --> 00:12:42,650
你的用户会更快乐。

293
00:12:42,650 --> 00:12:45,280
因此，有这些效果
实际上是给

294
00:12:45,280 --> 00:12:47,350
我们一些更深层次的思考。

295
00:12:47,350 --> 00:12:49,990
>> 因此，让我们来看看什么合并
排序实际上是一回事。

296
00:12:49,990 --> 00:12:52,992
很酷的事情是，合并
排序仅仅是这一点。

297
00:12:52,992 --> 00:12:56,300
再次，这是我们称为什么
伪代码，伪代码的存在

298
00:12:56,300 --> 00:12:57,720
类似英语的语法。

299
00:12:57,720 --> 00:12:59,890
和简单
迷人的排序。

300
00:12:59,890 --> 00:13:02,840
>> 所以输入n个元素 - 
只是意味着，这里是一个数组。

301
00:13:02,840 --> 00:13:04,000
它有着N个东西。

302
00:13:04,000 --> 00:13:05,370
这就是我们说有。

303
00:13:05,370 --> 00:13:07,560
>> 如果n小于2时，返回。

304
00:13:07,560 --> 00:13:08,640
所以，这只是微不足道的情况下。

305
00:13:08,640 --> 00:13:12,580
如果n是小于2，那么它显然
1或0，在这种情况下的事情

306
00:13:12,580 --> 00:13:14,780
已经排序或不存在的，
所以刚刚返回。

307
00:13:14,780 --> 00:13:15,900
有什么可以做。

308
00:13:15,900 --> 00:13:18,360
因此，这是一个简单的情况下拔掉。

309
00:13:18,360 --> 00:13:20,110
>> 否则，我们有三个步骤。

310
00:13:20,110 --> 00:13:23,650
的左半部分的元素进行排序，排序
的右半部分的元素，

311
00:13:23,650 --> 00:13:26,650
然后合并排序的一半。

312
00:13:26,650 --> 00:13:29,400
这里，有趣的是，
我样的撑船，对不对？

313
00:13:29,400 --> 00:13:32,300
有一种循环定义
该算法。

314
00:13:32,300 --> 00:13:35,986
在什么意义上是这样的算法
定义圆？

315
00:13:35,986 --> 00:13:37,850
>> 观众：[听不清]。

316
00:13:37,850 --> 00:13:41,670
>> 国宝马兰：是啊，我的排序算法，
它的两个步骤“排序

317
00:13:41,670 --> 00:13:44,640
东西。“于是引出了一个
的问题，以及什么我要使用

318
00:13:44,640 --> 00:13:46,460
排序的左半
和右半边？

319
00:13:46,460 --> 00:13:49,600
而这里的美景，即使
再次，这是心态弯曲

320
00:13:49,600 --> 00:13:54,030
一部分潜在的，你可以使用相同的
算法排序的左半。

321
00:13:54,030 --> 00:13:54,700
>> 但是且慢。

322
00:13:54,700 --> 00:13:57,070
当有人告诉你排序
左前卫，什么是两个

323
00:13:57,070 --> 00:13:58,240
步骤将成为下一个？

324
00:13:58,240 --> 00:14:00,550
我们将左半部分进行排序
左半边和右

325
00:14:00,550 --> 00:14:01,420
一半的左半边。

326
00:14:01,420 --> 00:14:04,430
该死，我怎么排序，这两个
半，或宿舍，现在呢？

327
00:14:04,430 --> 00:14:05,260
>> 但是，这是确定的。

328
00:14:05,260 --> 00:14:07,830
我们这里有一个排序算法。

329
00:14:07,830 --> 00:14:10,660
即使你可能会担心
首先，这是一种无限

330
00:14:10,660 --> 00:14:12,780
循环，这是一个周期，这是从来没有的
将要结束 - 它是将

331
00:14:12,780 --> 00:14:15,770
最后一次发生了什么？

332
00:14:15,770 --> 00:14:16,970
当n是小于2。

333
00:14:16,970 --> 00:14:19,180
最终将要发生，
因为如果你继续减半

334
00:14:19,180 --> 00:14:23,020
减半在减半这些半，肯定
最终，你要结束

335
00:14:23,020 --> 00:14:25,350
与仅有1或0个元素。

336
00:14:25,350 --> 00:14:28,500
在这一点上，这种算法
说，你就大功告成了。

337
00:14:28,500 --> 00:14:31,020
>> 所以，真正的魔力在这
算法似乎是在

338
00:14:31,020 --> 00:14:33,470
这最后的一步，合并。

339
00:14:33,470 --> 00:14:37,190
那个简单的想法，只是合并两个
的东西，这就是最终的

340
00:14:37,190 --> 00:14:40,920
让我们对数组进行排序，
比方说，8个元素。

341
00:14:40,920 --> 00:14:44,410
所以，我有八个压力球
在这里，8个纸片，和一个

342
00:14:44,410 --> 00:14:45,500
谷歌玻璃 - 

343
00:14:45,500 --> 00:14:46,140
这是我得到保持。

344
00:14:46,140 --> 00:14:46,960
>> [笑]

345
00:14:46,960 --> 00:14:48,970
>> DAVID马兰：如果我们可能需要8
志愿者，让我们来看看，如果我们能

346
00:14:48,970 --> 00:14:51,430
玩这个了，所以。

347
00:14:51,430 --> 00:14:52,500
哇，好。

348
00:14:52,500 --> 00:14:53,565
计算机科学是越来越有趣。

349
00:14:53,565 --> 00:14:54,320
好的。

350
00:14:54,320 --> 00:14:57,770
所以如何你三，
最大的手在那里。

351
00:14:57,770 --> 00:14:58,580
四个在后面。

352
00:14:58,580 --> 00:15:02,220
怎么样，我们会做你
三此行？

353
00:15:02,220 --> 00:15:03,390
四个在前面。

354
00:15:03,390 --> 00:15:04,920
所以，你八，上来吧。

355
00:15:04,920 --> 00:15:12,060
>> [笑]

356
00:15:12,060 --> 00:15:13,450
>> 国宝马兰：我其实
不知道它是什么。

357
00:15:13,450 --> 00:15:14,810
它是压力球？

358
00:15:14,810 --> 00:15:16,510
台灯？

359
00:15:16,510 --> 00:15:18,650
该材料？

360
00:15:18,650 --> 00:15:19,680
在互联网上？

361
00:15:19,680 --> 00:15:20,160
>> 确定。

362
00:15:20,160 --> 00:15:21,310
所以来了。

363
00:15:21,310 --> 00:15:22,310
谁愿意 - 

364
00:15:22,310 --> 00:15:23,570
保持上来。

365
00:15:23,570 --> 00:15:24,240
让我们来看看。

366
00:15:24,240 --> 00:15:26,460
这使你的位置 - 

367
00:15:26,460 --> 00:15:27,940
你在第一的位置。

368
00:15:27,940 --> 00:15:28,670
嗯，哦，等一下。

369
00:15:28,670 --> 00:15:30,760
1，2，3，4，5，6，7  - 哦，好。

370
00:15:30,760 --> 00:15:31,310
好吧，我们是很好的。

371
00:15:31,310 --> 00:15:35,130
好吧，所以大家有一个座位，
但不是谷歌的玻璃上。

372
00:15:35,130 --> 00:15:36,475
让我排队这些了。

373
00:15:36,475 --> 00:15:37,115
你叫什么名字？

374
00:15:37,115 --> 00:15:37,440
>> 米歇尔：米歇尔。

375
00:15:37,440 --> 00:15:38,090
>> 国宝马兰：米歇尔？

376
00:15:38,090 --> 00:15:42,000
好吧，你得到的样子
怪胎，如果这是确定的。

377
00:15:42,000 --> 00:15:44,625
嗯，我也这样做，我想，
只是一瞬间。

378
00:15:44,625 --> 00:15:45,875
所有权利，备用。

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
我们一直试图想出一个
使用的情况下，我们对Google玻璃

381
00:15:50,950 --> 00:15:53,750
认为这将是有趣的只是做
当人们在舞台上。

382
00:15:53,750 --> 00:15:57,120
我们会记录世界
从他们的角度。

383
00:15:57,120 --> 00:15:58,410
好的。

384
00:15:58,410 --> 00:15:59,830
可能是谷歌意。

385
00:15:59,830 --> 00:16:02,260
好吧，如果你不介意穿
这下一尴尬分钟，

386
00:16:02,260 --> 00:16:03,150
那将是美好的。

387
00:16:03,150 --> 00:16:08,620
>> 所有的权利，所以我们这里有一个数组
元素，该阵列，每

388
00:16:08,620 --> 00:16:11,480
纸片在这些人“
手，是目前排序。

389
00:16:11,480 --> 00:16:12,050
>> 米歇尔：噢，那是太怪异了。

390
00:16:12,050 --> 00:16:12,810
>> DAVID马兰：这是非常随机的。

391
00:16:12,810 --> 00:16:15,760
在短短的时刻，我们要尝试
实施合并排序

392
00:16:15,760 --> 00:16:17,950
看到这一关键洞察力。

393
00:16:17,950 --> 00:16:21,970
这里的技巧与归并排序
的东西，我们没有假设。

394
00:16:21,970 --> 00:16:24,030
我们确实需要一些
额外的空间。

395
00:16:24,030 --> 00:16:26,650
那么，这是怎么回事要特别
有趣的是，这些

396
00:16:26,650 --> 00:16:29,270
附近有一座小家伙要移动
位，因为我将假设

397
00:16:29,270 --> 00:16:31,880
有一个额外的数组空间，
也就是说，在他们身后。

398
00:16:31,880 --> 00:16:34,570
>> 所以，如果他们自己的椅子后面，
这是辅助阵列。

399
00:16:34,570 --> 00:16:36,960
如果他们坐在这里，这是
主阵列。

400
00:16:36,960 --> 00:16:40,170
但是，这是一种资源，我们有
迄今没有利用泡沫

401
00:16:40,170 --> 00:16:42,040
排序，选择排序，
用插入排序。

402
00:16:42,040 --> 00:16:44,600
回想上周，每个人都只是
样的洗牌。

403
00:16:44,600 --> 00:16:46,840
他们没有使用任何额外的内存。

404
00:16:46,840 --> 00:16:49,310
我们的空间让人们
移动周围的人。

405
00:16:49,310 --> 00:16:50,580
>> 因此，这是一个关键的洞察力。

406
00:16:50,580 --> 00:16:53,410
有这种权衡，一般在
计算机科学，资源。

407
00:16:53,410 --> 00:16:55,800
如果你想加快东西
如时间，你要

408
00:16:55,800 --> 00:16:56,900
必须付出一定的代价。

409
00:16:56,900 --> 00:17:00,750
那些价格是非常频繁
空间的内存量或硬

410
00:17:00,750 --> 00:17:01,700
您正在使用的磁盘空间。

411
00:17:01,700 --> 00:17:03,640
或者，坦率地说，
程序员的时间。

412
00:17:03,640 --> 00:17:06,700
多少时间，它需要你，人类，
真正实现多一些

413
00:17:06,700 --> 00:17:07,829
复杂的算法。

414
00:17:07,829 --> 00:17:09,760
但今天，权衡
是时间和空间。

415
00:17:09,760 --> 00:17:11,930
>> 所以，如果你们能托起你
数字，所以我们可以看到，你

416
00:17:11,930 --> 00:17:15,839
确实匹配4，2，6，1，3，7，8。

417
00:17:15,839 --> 00:17:16,599
优秀的。

418
00:17:16,599 --> 00:17:19,520
所以我要去尝试，以协调
的东西，如果你们可以只

419
00:17:19,520 --> 00:17:21,800
跟随我的领导在这里。

420
00:17:21,800 --> 00:17:26,650
>> 所以，我要实现，首先，
第一步骤的伪代码，这是

421
00:17:26,650 --> 00:17:29,440
在输入n个元素，如果n是
小于2，然后返回。

422
00:17:29,440 --> 00:17:31,370
显然，这不
适用，因此我们继续前进。

423
00:17:31,370 --> 00:17:33,340
因此，排序的元素的左半部分。

424
00:17:33,340 --> 00:17:36,220
因此，这意味着我要专注我
这些只是一瞬间的关注

425
00:17:36,220 --> 00:17:37,310
四个家伙在这里。

426
00:17:37,310 --> 00:17:39,774
好吧，接下来我该怎么办？

427
00:17:39,774 --> 00:17:40,570
>> 观众：排序的左半边。

428
00:17:40,570 --> 00:17:42,780
>> 国宝马兰：所以现在我有排序
这些家伙的左半边。

429
00:17:42,780 --> 00:17:45,580
因为再次，假设自己的
的目标是要排序的左半边。

430
00:17:45,580 --> 00:17:46,440
你怎么做到这一点呢？

431
00:17:46,440 --> 00:17:49,140
只要按照上面的指令，即使
虽然我们做了一遍。

432
00:17:49,140 --> 00:17:50,160
因此，排序的左半边。

433
00:17:50,160 --> 00:17:52,030
现在，我这两个家伙排序。

434
00:17:52,030 --> 00:17:53,563
下一步是什么？

435
00:17:53,563 --> 00:17:54,510
>> 观众：排序的左半边。

436
00:17:54,510 --> 00:17:55,460
>> 国宝MALAN：排序的左半边。

437
00:17:55,460 --> 00:18:00,680
所以，现在这些，这个座位在这里，
是一个大小为1的列表。

438
00:18:00,680 --> 00:18:01,365
你叫什么名字呢？

439
00:18:01,365 --> 00:18:02,390
>> 公主DAISY：黛西公主。

440
00:18:02,390 --> 00:18:03,690
>> 国宝马兰：黛西公主就在这里。

441
00:18:03,690 --> 00:18:07,470
于是她，因为已经排序
该列表是大小为1。

442
00:18:07,470 --> 00:18:09,490
接下来我该怎么办？

443
00:18:09,490 --> 00:18:13,680
OK，返回，因为该列表
大小为1，小于2。

444
00:18:13,680 --> 00:18:14,320
那么什么是下一步？

445
00:18:14,320 --> 00:18:17,490
现在你有样的
原路返回，在你的心中。

446
00:18:17,490 --> 00:18:19,340
>> 排序的右半​​边，这是 - 

447
00:18:19,340 --> 00:18:19,570
你叫什么名字？

448
00:18:19,570 --> 00:18:20,220
>> LINDA：琳达。

449
00:18:20,220 --> 00:18:20,980
>> 国宝马兰：琳达。

450
00:18:20,980 --> 00:18:23,210
因此，我们应该做些什么，现在
我们有一个列表的大小为1？

451
00:18:23,210 --> 00:18:24,440
>> 观众：返回。

452
00:18:24,440 --> 00:18:24,760
>> DAVID马兰：小心。

453
00:18:24,760 --> 00:18:29,540
我们先回来了，现在的第三
一步 - 如果我描绘

454
00:18:29,540 --> 00:18:33,490
现在拥抱的两个席位，现在我
合并这两个元素。

455
00:18:33,490 --> 00:18:35,530
所以，现在不幸的是，元素
秩序。

456
00:18:35,530 --> 00:18:39,920
但是，这就是合并过程
开始引人注目。

457
00:18:39,920 --> 00:18:42,410
>> 所以，如果你们能站起来，只是
片刻，我需要你，在一个

458
00:18:42,410 --> 00:18:44,170
此刻，加强你的椅子后面。

459
00:18:44,170 --> 00:18:46,480
并且如果琳达，因为图2是
小于4，你为什么不

460
00:18:46,480 --> 00:18:48,130
首先你来到我身边吗？

461
00:18:48,130 --> 00:18:48,690
呆在那里。

462
00:18:48,690 --> 00:18:50,520
所以，琳达，你过来先。

463
00:18:50,520 --> 00:18:53,820
>> 现在，在现实中，如果它只是一个数组
我们可能只是她的实时移动

464
00:18:53,820 --> 00:18:55,360
这把椅子到这个地方。

465
00:18:55,360 --> 00:18:57,770
所以，想象一下，采取了一些常数
步骤1的数。

466
00:18:57,770 --> 00:18:58,480
而现在 - 

467
00:18:58,480 --> 00:19:01,490
但我们需要把你的
这里的第一个位置。

468
00:19:01,490 --> 00:19:03,930
>> 而现在，如果你能来到我身边，
好了，我们要去

469
00:19:03,930 --> 00:19:06,300
在位置2。

470
00:19:06,300 --> 00:19:09,120
即使这感觉像
服用了一段时间，什么是好的现在是

471
00:19:09,120 --> 00:19:14,710
的左半部分
现在左半排序。

472
00:19:14,710 --> 00:19:18,010
是下一步骤中，如果我们现在
进一步倒转的故事？

473
00:19:18,010 --> 00:19:18,980
>> 观众：右半边。

474
00:19:18,980 --> 00:19:19,900
>> DAVID马兰：排序的右半​​边。

475
00:19:19,900 --> 00:19:21,320
所以，你们必须这样做，以及。

476
00:19:21,320 --> 00:19:23,510
所以，如果你能站起来
只是一瞬间吗？

477
00:19:23,510 --> 00:19:25,192
你叫什么名字？

478
00:19:25,192 --> 00:19:25,540
>> JESS：杰西。

479
00:19:25,540 --> 00:19:25,870
>> 国宝马兰：杰西。

480
00:19:25,870 --> 00:19:29,720
OK，所以Jess是现在的左
的右半部分的一半。

481
00:19:29,720 --> 00:19:31,400
所以她的大小为1的列表。

482
00:19:31,400 --> 00:19:32,380
她显然排序。

483
00:19:32,380 --> 00:19:33,070
和你的名字吗？

484
00:19:33,070 --> 00:19:33,630
>> 米歇尔：米歇尔。

485
00:19:33,630 --> 00:19:35,340
>> 国宝马兰：米歇尔显然是
大小为1的列表。

486
00:19:35,340 --> 00:19:36,050
她已经排序。

487
00:19:36,050 --> 00:19:38,690
所以现在发生的魔力，
合并过程。

488
00:19:38,690 --> 00:19:39,790
那么，谁将会第一次来吗？

489
00:19:39,790 --> 00:19:41,560
显然，米歇尔。

490
00:19:41,560 --> 00:19:43,280
所以，如果你能过来。

491
00:19:43,280 --> 00:19:47,090
我们现在为她提供空间
后面这把椅子在这里。

492
00:19:47,090 --> 00:19:51,580
而现在，如果你能回来，
我们现在有，是明确的，两个

493
00:19:51,580 --> 00:19:53,810
半，每个的大小为2  - 

494
00:19:53,810 --> 00:19:57,090
刚刚描绘的缘故，如果你
可以使一点点的空间 - 

495
00:19:57,090 --> 00:19:59,780
一个左半在这里，其中一个
右半这里。

496
00:19:59,780 --> 00:20:01,160
>> 故事倒带进一步。

497
00:20:01,160 --> 00:20:02,270
什么样的步骤是下一个？

498
00:20:02,270 --> 00:20:03,030
>> 观众：合并。

499
00:20:03,030 --> 00:20:04,160
>> 国宝马兰：所以现在我们必须进行合并。

500
00:20:04,160 --> 00:20:07,490
这样就OK了，所以现在，令人欣慰的是，我们
刚刚释放了四把椅子。

501
00:20:07,490 --> 00:20:11,480
因此，我们已经两次使用尽可能多的内存，但
我们可以给之间倒装假摔

502
00:20:11,480 --> 00:20:12,330
两个数组。

503
00:20:12,330 --> 00:20:14,190
因此，这数字是先来？

504
00:20:14,190 --> 00:20:14,850
因此，米歇尔，很明显。

505
00:20:14,850 --> 00:20:16,680
所以来到我身边，并采取
您的座位在这里。

506
00:20:16,680 --> 00:20:19,120
然后数字2是明显
接下来，你来这里。

507
00:20:19,120 --> 00:20:21,520
第4号，6号。

508
00:20:21,520 --> 00:20:23,390
再次，即使有一个
点点步行涉及，

509
00:20:23,390 --> 00:20:26,010
说真的，这些可能发生的瞬间，
移动 - 

510
00:20:26,010 --> 00:20:26,880
OK，很好的发挥。

511
00:20:26,880 --> 00:20:28,350
>> [笑]

512
00:20:28,350 --> 00:20:29,680
>> 国宝马兰：现在我们
在相当良好。

513
00:20:29,680 --> 00:20:34,910
的左半部分的整个
输入现在已经被排序。

514
00:20:34,910 --> 00:20:37,370
所有的权利，让这些家伙
我的优势 - 

515
00:20:37,370 --> 00:20:40,340
它是怎么结束了所有女孩子对
离开和所有的男孩在右边？

516
00:20:40,340 --> 00:20:42,450
>> OK，这样的家伙现在轮到。

517
00:20:42,450 --> 00:20:44,680
所以，我不会走你通过
这些步骤。

518
00:20:44,680 --> 00:20:46,550
我们可以看到，如果我们可以重新
相同的伪代码。

519
00:20:46,550 --> 00:20:50,050
如果你想提前去站起来，
你们这些家伙，让我给你话筒。

520
00:20:50,050 --> 00:20:52,990
如果你不能复制什么
我们在这里只是做

521
00:20:52,990 --> 00:20:53,880
列表中的另一端。

522
00:20:53,880 --> 00:20:59,530
谁需要先发言，
基于该算法？

523
00:20:59,530 --> 00:21:03,210
因此，解释你在做什么之前，
你做任何脚的动作。

524
00:21:03,210 --> 00:21:05,930
>> 扬声器1：好吧，这样以来
我的左半部分

525
00:21:05,930 --> 00:21:07,790
左前卫，我返回。

526
00:21:07,790 --> 00:21:08,730
对吗？

527
00:21:08,730 --> 00:21:09,250
>> 国宝马兰：好。

528
00:21:09,250 --> 00:21:10,350
>> 扬声器1：然后 - 

529
00:21:10,350 --> 00:21:11,800
>> 国宝马兰：谁做
麦克风去下一个？

530
00:21:11,800 --> 00:21:12,920
>> 扬声器1：下一个号码。

531
00:21:12,920 --> 00:21:14,720
>> 扬声器2：所以我的右半边
的左半部分

532
00:21:14,720 --> 00:21:17,830
左半边，而我回来。

533
00:21:17,830 --> 00:21:18,050
>> 国宝马兰：好。

534
00:21:18,050 --> 00:21:18,550
你回来。

535
00:21:18,550 --> 00:21:21,855
所以，现在你们两个什么是下一个向上？

536
00:21:21,855 --> 00:21:23,740
>> 扬声器2：我们希望看到谁较小。

537
00:21:23,740 --> 00:21:24,200
>> DAVID马兰：没错。

538
00:21:24,200 --> 00:21:24,940
我们要合并。

539
00:21:24,940 --> 00:21:27,590
我们要用来合并空间
你进入，即使它们

540
00:21:27,590 --> 00:21:30,250
显然已经排序，我们将
遵循相同的算法。

541
00:21:30,250 --> 00:21:31,560
那么，谁去先回来？

542
00:21:31,560 --> 00:21:35,720
因此，心情，和7。

543
00:21:35,720 --> 00:21:38,570
现在的麦克风去
这些家伙，好不好？

544
00:21:38,570 --> 00:21:43,590
>> 扬声器3：所以我的右半边
左半边，我Ñ小于

545
00:21:43,590 --> 00:21:45,048
1，所以我只是要通过 - 

546
00:21:45,048 --> 00:21:46,380
>> 国宝马兰：好。

547
00:21:46,380 --> 00:21:49,450
>> 扬声器4：我的右半部分
右半边的右半边，而我

548
00:21:49,450 --> 00:21:51,740
还一个人，所以我
要返回。

549
00:21:51,740 --> 00:21:52,990
所以，现在我们合并。

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> 扬声器3：所以，我们回去吧。

552
00:21:56,150 --> 00:21:57,160
>> DAVID马兰：所以，你到后面去。

553
00:21:57,160 --> 00:21:59,200
所以第一，然后按8。

554
00:21:59,200 --> 00:22:01,240
而现在的观众，这是
步骤我们现在倒带

555
00:22:01,240 --> 00:22:02,200
备份在我们的脑海中？

556
00:22:02,200 --> 00:22:02,940
>> 观众：合并。

557
00:22:02,940 --> 00:22:07,270
>> 国宝马兰：合并左半边和右
一半的原始左半。

558
00:22:07,270 --> 00:22:08,840
所以，现在 - 

559
00:22:08,840 --> 00:22:10,520
只是为了让这一点，
一点点的空间

560
00:22:10,520 --> 00:22:11,690
你们之间的两个家伙。

561
00:22:11,690 --> 00:22:13,800
所以，现在的两个列表，
左，右。

562
00:22:13,800 --> 00:22:18,320
那么我们怎么现在合并你们到
前排座椅吗？

563
00:22:18,320 --> 00:22:19,600
>> 3先行。

564
00:22:19,600 --> 00:22:20,850
然后，很明显。

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
然后，7，8。

567
00:22:27,330 --> 00:22:28,710
OK，现在我们是谁？

568
00:22:28,710 --> 00:22:29,650
>> 观众：没做过。

569
00:22:29,650 --> 00:22:32,440
>> 国宝马兰：没做过，因为
显然，有一个剩余步骤。

570
00:22:32,440 --> 00:22:35,720
不过，我之所以要使用这
像“倒带在你的心中，行话”

571
00:22:35,720 --> 00:22:37,160
这是因为这是真的
发生了什么。

572
00:22:37,160 --> 00:22:39,610
我们将通过所有这些步骤，
但我们暂停一排序

573
00:22:39,610 --> 00:22:42,480
的时刻，潜水深入到
算法，停顿了一会儿，

574
00:22:42,480 --> 00:22:45,840
潜水深入算法，并
现在我们要排序退我们

575
00:22:45,840 --> 00:22:49,430
头脑和撤消所有这些层
排序，我们已经暂时搁置。

576
00:22:49,430 --> 00:22:51,790
>> 所以现在我们有两个列表大小为4。

577
00:22:51,790 --> 00:22:54,790
如果你们能站起来，最后一次
和这里一点空间

578
00:22:54,790 --> 00:22:57,230
清楚，这是左
原来，一半

579
00:22:57,230 --> 00:22:58,620
右原来的一半。

580
00:22:58,620 --> 00:23:01,060
谁是第一个数字，我们
需要拉进后面？

581
00:23:01,060 --> 00:23:01,870
米歇尔，当然。

582
00:23:01,870 --> 00:23:03,230
>> 所以我们把这里的米歇尔。

583
00:23:03,230 --> 00:23:05,080
2号？

584
00:23:05,080 --> 00:23:06,440
2号上回好。

585
00:23:06,440 --> 00:23:07,800
编号3？

586
00:23:07,800 --> 00:23:08,510
优秀的。

587
00:23:08,510 --> 00:23:16,570
4号，5号，6号，
7号和8号。

588
00:23:16,570 --> 00:23:18,850
>> OK，所以觉得好像有很多
步骤，是肯定的。

589
00:23:18,850 --> 00:23:22,390
但现在让我们来看看，如果我们不能确认
那种直观的，这

590
00:23:22,390 --> 00:23:26,190
算法从根本上，特别是作为
n变真的大，正如我们已经看到的

591
00:23:26,190 --> 00:23:29,170
与动画，是
从根本上更快。

592
00:23:29,170 --> 00:23:33,400
因此，我要求这个算法，在最坏的
的情况下，即使在最好的情况下，

593
00:23:33,400 --> 00:23:36,160
是大O n次日志n。

594
00:23:36,160 --> 00:23:39,160
即，存在的一些方面，这
算法需要n个步骤，但

595
00:23:39,160 --> 00:23:43,110
还有另一个方面某处
该迭代循环，

596
00:23:43,110 --> 00:23:44,410
需要记录n步。

597
00:23:44,410 --> 00:23:49,154
我们可以把我们的手指放在什么那些
两个数字是指什么？

598
00:23:49,154 --> 00:23:51,320
嘛，哪里 - 

599
00:23:51,320 --> 00:23:54,160
麦克风到哪去？

600
00:23:54,160 --> 00:23:58,660
>> 扬声器1：将日志n是
我们一分为二 - 

601
00:23:58,660 --> 00:23:59,630
除以二，本质上。

602
00:23:59,630 --> 00:24:00,120
>> DAVID马兰：没错。

603
00:24:00,120 --> 00:24:03,000
我们看到在任何时候，任何算法，从而
目前为止，这种模式

604
00:24:03,000 --> 00:24:04,200
分裂，分化，分裂。

605
00:24:04,200 --> 00:24:05,700
它一般会降低
东西是

606
00:24:05,700 --> 00:24:07,100
对数，底数2。

607
00:24:07,100 --> 00:24:10,180
但是，真的有可能是任何东西，
但登录基地2。

608
00:24:10,180 --> 00:24:11,330
>> 现在什么的n？

609
00:24:11,330 --> 00:24:14,550
我可以看到，我们把你
家伙 - 你分，分，

610
00:24:14,550 --> 00:24:15,910
分，分。

611
00:24:15,910 --> 00:24:18,760
哪里到底从何而来？

612
00:24:18,760 --> 00:24:19,810
>> 因此，它的合并。

613
00:24:19,810 --> 00:24:20,610
因为去想它。

614
00:24:20,610 --> 00:24:25,420
当你合并在一起，八人
其中一半是一套四

615
00:24:25,420 --> 00:24:27,770
，而另一半是另一种
四，你怎么去

616
00:24:27,770 --> 00:24:28,820
做合并？

617
00:24:28,820 --> 00:24:30,830
好了，你们做到了
相当直观。

618
00:24:30,830 --> 00:24:34,140
>> 但是，如果我不是做这一点更
有条不紊，我可能已经指向

619
00:24:34,140 --> 00:24:38,090
最左边的人先用我的左手
手，指着最左边的人

620
00:24:38,090 --> 00:24:42,080
用我的右手，有一半
只是后来走过

621
00:24:42,080 --> 00:24:46,990
名单，指着最小的元素
每一次，我的手指移动和

622
00:24:46,990 --> 00:24:48,970
超过所需要的整个列表。

623
00:24:48,970 --> 00:24:51,890
但是，什么是这个合并的关键
过程是我比较这些对

624
00:24:51,890 --> 00:24:53,460
的元素。

625
00:24:53,460 --> 00:24:57,270
从右侧的一半，从左边
半，我从来没有一次回溯。

626
00:24:57,270 --> 00:25:00,570
>> 因此，合并本身正
不超过n个步骤。

627
00:25:00,570 --> 00:25:03,250
多少次我有
合并做到这一点呢？

628
00:25:03,250 --> 00:25:07,150
嗯，不超过n，我们只是
看到最终的合并。

629
00:25:07,150 --> 00:25:13,120
因此，如果你做的东西，需要
日志n步n次，反之亦然，

630
00:25:13,120 --> 00:25:15,210
这将会给我们日志n n次。

631
00:25:15,210 --> 00:25:16,310
>> 这是为什么更好？

632
00:25:16,310 --> 00:25:19,600
那么，如果我们已经知道该日志
n是大于n  - 对吗？

633
00:25:19,600 --> 00:25:22,590
我们看到在二进制搜索，电话簿
例如，日志n为绝对

634
00:25:22,590 --> 00:25:23,760
优于线性。

635
00:25:23,760 --> 00:25:28,420
因此，这意味着Ñ次日志n是
肯定比n倍另一个

636
00:25:28,420 --> 00:25:30,390
N，又名Ń平方。

637
00:25:30,390 --> 00:25:32,400
这就是我们最终的感觉。

638
00:25:32,400 --> 00:25:34,928
>> 这么大的掌声，如果
我们可以为这些家伙。

639
00:25:34,928 --> 00:25:38,920
>> [掌声]

640
00:25:38,920 --> 00:25:41,550
>> 国宝马兰：你的临别礼物 - 
你可以保留的数字，

641
00:25:41,550 --> 00:25:44,010
如果您想。

642
00:25:44,010 --> 00:25:45,620
和你的临别礼物，像往常一样。

643
00:25:45,620 --> 00:25:47,290
哦，我们会送你
的画面，米歇尔。

644
00:25:47,290 --> 00:25:48,343
谢谢。

645
00:25:48,343 --> 00:25:49,250
好的。

646
00:25:49,250 --> 00:25:50,400
帮助自己的应力球。

647
00:25:50,400 --> 00:25:54,110
>> 让我拉起来，在此期间，
我们的朋友罗布·鲍登提供

648
00:25:54,110 --> 00:25:59,520
有些不同的观点，在此，
因为你可以想想这些

649
00:25:59,520 --> 00:26:01,280
步骤发生在一个有点
不同的方式。

650
00:26:01,280 --> 00:26:04,750
事实上，建立罗布的
向我们展示了，假设我们

651
00:26:04,750 --> 00:26:09,030
已经做了瓜分
大名单分为八个小名单，

652
00:26:09,030 --> 00:26:10,570
每个大小为1。

653
00:26:10,570 --> 00:26:13,350
>> 所以，我们要改变一个伪代码
点点得到的只是排序

654
00:26:13,350 --> 00:26:15,320
如何合并工程的核心理念。

655
00:26:15,320 --> 00:26:17,600
但运行时间是什么
他做的仍然是

656
00:26:17,600 --> 00:26:19,110
将是相同的。

657
00:26:19,110 --> 00:26:23,540
再次，在这里设置的是，他的
开始有八个列表的大小为1。

658
00:26:23,540 --> 00:26:27,730
所以你错过了他的部分
实际上做日志日志N，N，日志N

659
00:26:27,730 --> 00:26:31,205
除以输入。

660
00:26:31,205 --> 00:26:32,120
>> [视频回放]

661
00:26:32,120 --> 00:26:33,615
>> 这是它的第一个步骤。

662
00:26:33,615 --> 00:26:38,270
步骤二，反复
合并成对的名单。

663
00:26:38,270 --> 00:26:39,210
>> 国宝马兰：嗯。

664
00:26:39,210 --> 00:26:41,270
只有音频
出我的电脑。

665
00:26:41,270 --> 00:26:42,520
让我们试一次。

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> 只是随便挑 - 
现在，我们有四个名单。

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
了解之前。

670
00:26:52,120 --> 00:26:53,040
>> 国宝马兰：我们走吧。

671
00:26:53,040 --> 00:27:00,510
>> 合并108和15，我们最终
与列表15，108。

672
00:27:00,510 --> 00:27:07,170
合并50和图4中，我们
结束与4，50。

673
00:27:07,170 --> 00:27:12,990
合并8和42，我们
结束与8位，42。

674
00:27:12,990 --> 00:27:19,970
和合并23日和16日，我们
结束与16，23。

675
00:27:19,970 --> 00:27:23,270
>> 现在我们的名单是大小为2。

676
00:27:23,270 --> 00:27:26,690
请注意，各
四个列表进行排序。

677
00:27:26,690 --> 00:27:29,450
因此，我们就可以开始合并
再次对列表。

678
00:27:29,450 --> 00:27:38,420
合并15和108和4和50，我们
先取4，然后15，然后

679
00:27:38,420 --> 00:27:41,500
50，那么108。

680
00:27:41,500 --> 00:27:50,610
合并8，42，16，23，我们先来
8，然后16，然后23个

681
00:27:50,610 --> 00:27:52,700
然后42。

682
00:27:52,700 --> 00:27:57,600
>> 所以，现在我们只有两个列表大小
4，其中每一个进行排序。

683
00:27:57,600 --> 00:28:01,170
所以，现在我们合并这两个列表。

684
00:28:01,170 --> 00:28:11,835
首先，我们4，然后我们把
8，然后我们采取了15，然后16，然后

685
00:28:11,835 --> 00:28:19,456
23，42，50，108。

686
00:28:19,456 --> 00:28:19,872
>> [END视频播放]

687
00:28:19,872 --> 00:28:23,430
>> 国宝马兰：同样，请注意，他从来没有
触动了杯一次以上

688
00:28:23,430 --> 00:28:24,860
之后超越它前进。

689
00:28:24,860 --> 00:28:26,200
所以他从来不重复。

690
00:28:26,200 --> 00:28:29,850
所以他总是移动到一边，
这就是我们得到了我们的Ñ。

691
00:28:29,850 --> 00:28:33,290
>> 为什么不让我拉起一个动画
我们前面看到的，但是这一次

692
00:28:33,290 --> 00:28:35,110
只专注于合并排序。

693
00:28:35,110 --> 00:28:38,030
让我继续前进，放大
在此。

694
00:28:38,030 --> 00:28:42,530
首先，让我选择一个随机输入，
放大这一点，你可以看到排序

695
00:28:42,530 --> 00:28:46,600
我们采取了什么是理所当然的，早些时候，
合并排序，实际上做。

696
00:28:46,600 --> 00:28:50,330
>> 因此，发现，你得到这些半或
这些宿舍或这些八分之

697
00:28:50,330 --> 00:28:53,140
问题一下子
开始采取良好的形状。

698
00:28:53,140 --> 00:28:57,070
然后，最后，你看到
最末端，咣当，

699
00:28:57,070 --> 00:28:58,860
一切都合并在一起。

700
00:28:58,860 --> 00:29:01,690
>> 所以这些都只是三种不同
采取同样的想法。

701
00:29:01,690 --> 00:29:05,980
但关键的洞察力，就像鸿沟
和征服的第一类，

702
00:29:05,980 --> 00:29:10,640
是我们决定以某种方式划分
问题变成大的东西，进入

703
00:29:10,640 --> 00:29:14,760
排序相同的精神的东西，
但更小的和更小的和更小的

704
00:29:14,760 --> 00:29:15,660
和更小的。

705
00:29:15,660 --> 00:29:18,420
>> 现在，另一个有趣的方式来排序认为
这些，即使它不是

706
00:29:18,420 --> 00:29:20,520
打算给​​你相同的直观
理解，是

707
00:29:20,520 --> 00:29:21,640
下面的动画。

708
00:29:21,640 --> 00:29:25,400
所以这是一个视频的人放在一起
相关不同

709
00:29:25,400 --> 00:29:29,970
与各种不同的操作的声音
插入排序，归并排序，

710
00:29:29,970 --> 00:29:31,150
其他几个。

711
00:29:31,150 --> 00:29:32,330
因此，在某一时刻，我会打游戏。

712
00:29:32,330 --> 00:29:33,600
它是大约一分钟长。

713
00:29:33,600 --> 00:29:37,410
即使你仍然可以看到
发生的模式，这时候你可以

714
00:29:37,410 --> 00:29:41,420
也听到这些算法如何
不同的执行与

715
00:29:41,420 --> 00:29:43,950
有所不同的型态。

716
00:29:43,950 --> 00:29:45,830
>> 这是插入排序。

717
00:29:45,830 --> 00:29:50,400
>> [提示音播放]

718
00:29:50,400 --> 00:29:52,400
>> 国宝马兰：再次尝试
每个元素插入

719
00:29:52,400 --> 00:29:52,900
到属于它的地方。

720
00:29:52,900 --> 00:29:54,628
这是冒泡排序。

721
00:29:54,628 --> 00:30:10,097
>> [提示音播放]

722
00:30:10,097 --> 00:30:13,630
>> 国宝马兰：您可以排序的感觉
如何相对较少的工作，它在做什么

723
00:30:13,630 --> 00:30:15,834
对每一个步骤。

724
00:30:15,834 --> 00:30:20,470
这是沉闷听起来像。

725
00:30:20,470 --> 00:30:21,472
>> [提示音播放]

726
00:30:21,472 --> 00:30:25,222
>> 国宝马兰：这是选择排序，
我们选择我们想要的元素

727
00:30:25,222 --> 00:30:28,845
再次经历一次又一次
并把它的开始。

728
00:30:28,845 --> 00:30:37,674
>> [提示音播放]

729
00:30:37,674 --> 00:30:43,970
>> 国宝马兰：这是归并排序，
你可以真正开始感觉。

730
00:30:43,970 --> 00:30:51,810
>> [提示音播放]

731
00:30:51,810 --> 00:30:54,770
>> [笑]

732
00:30:54,770 --> 00:30:58,395
>> 国宝马兰：名为gnome的东西
排序，我们没有看过。

733
00:30:58,395 --> 00:31:13,630
>> [提示音播放]

734
00:31:13,630 --> 00:31:17,910
>> 国宝马兰：所以让我看，现在，
你希望是由分心

735
00:31:17,910 --> 00:31:21,110
音乐，如果我能稍有闪失
数学位在这里。

736
00:31:21,110 --> 00:31:24,850
因此，还有第四种办法，我们可以
想想这意味着什么

737
00:31:24,850 --> 00:31:29,210
功能比那些快
我们已经看到过。

738
00:31:29,210 --> 00:31:32,470
如果你未来在课程
数学的背景，你

739
00:31:32,470 --> 00:31:36,030
其实也许已经知道，你
这种技术可以一巴掌长期 - 

740
00:31:36,030 --> 00:31:40,400
即递归函数
以某种方式调用自身。

741
00:31:40,400 --> 00:31:44,780
>> 再次，记得归并排序
在这个意义上的伪代码是递归

742
00:31:44,780 --> 00:31:48,460
一个合并排序的步骤
是打电话排序 - 

743
00:31:48,460 --> 00:31:49,740
也就是说，本身。

744
00:31:49,740 --> 00:31:52,480
但令人欣慰的是，因为我们一直
呼叫排序，归并排序，

745
00:31:52,480 --> 00:31:55,880
具体地，在一个较小的和更小的
和较小的名单，我们最终

746
00:31:55,880 --> 00:32:00,005
走出谷底，感谢我们就这么叫
基地的情况下，硬编码的情况下，

747
00:32:00,005 --> 00:32:04,270
说，如果列表很小，不到2
在这种情况下，就立即返回。

748
00:32:04,270 --> 00:32:07,550
如果我们没有这种特殊情况，
算法绝不会走出低谷，

749
00:32:07,550 --> 00:32:11,010
事实上，你会进入一个
无限循环，真正的永远。

750
00:32:11,010 --> 00:32:14,330
>> 但是假设我们希望现在就把
在此，再次一些数字，使用n

751
00:32:14,330 --> 00:32:15,660
作为输入的大小。

752
00:32:15,660 --> 00:32:18,680
我想问问你，有什么
涉及的总时间

753
00:32:18,680 --> 00:32:19,800
执行合并排序？

754
00:32:19,800 --> 00:32:22,960
或更普遍的，有什么
它的成本的时间吗？

755
00:32:22,960 --> 00:32:24,730
>> 那么这是很容易衡量。

756
00:32:24,730 --> 00:32:29,010
如果n是小于2时，所涉及的时间
在n个元素进行排序，

757
00:32:29,010 --> 00:32:30,480
其中n为2，为0。

758
00:32:30,480 --> 00:32:31,410
因为我们刚刚返回。

759
00:32:31,410 --> 00:32:32,510
有没有工作要做。

760
00:32:32,510 --> 00:32:35,660
现在可以说，也许这是一个两步
步骤弄清楚的金额

761
00:32:35,660 --> 00:32:38,420
工作，但它足够接近0
我只是说没有工作

762
00:32:38,420 --> 00:32:40,940
如果需要的名单是如此之小
无趣。

763
00:32:40,940 --> 00:32:42,580
>> 但有趣的是，这种情况下。

764
00:32:42,580 --> 00:32:47,320
递归分支
别人说的伪排序

765
00:32:47,320 --> 00:32:52,000
的左半边，排序的权利
一半，合并的两半。

766
00:32:52,000 --> 00:32:55,530
为什么会发生这种表达
表示该费用？

767
00:32:55,530 --> 00:32:58,690
嗯，T为n的意思是，
时间排序n个元素。

768
00:32:58,690 --> 00:33:03,070
然后在右手侧的
等号，划分为n的T

769
00:33:03,070 --> 00:33:06,600
2是指，以什么样的成本？

770
00:33:06,600 --> 00:33:07,570
排序的左半。

771
00:33:07,570 --> 00:33:10,990
其他T除以2的n
大概是指的成本

772
00:33:10,990 --> 00:33:12,390
排序的右半​​边。

773
00:33:12,390 --> 00:33:14,590
>> 然后加N？

774
00:33:14,590 --> 00:33:15,420
被合并。

775
00:33:15,420 --> 00:33:19,120
因为如果你有两个列表，一个是
大小为n超过2和其他大小为n

776
00:33:19,120 --> 00:33:22,580
2，你必须基本上触摸
这些元素，就像罗布

777
00:33:22,580 --> 00:33:24,990
感动每个杯子，只是
正如我们在每个

778
00:33:24,990 --> 00:33:26,310
志愿者们在舞台上。

779
00:33:26,310 --> 00:33:28,790
因此，n是合并的费用。

780
00:33:28,790 --> 00:33:31,780
>> 不幸的是，现在这个公式
本身也是递归的。

781
00:33:31,780 --> 00:33:36,390
所以，如果问的问题，如果n是说，
16，如果有16人在舞台上

782
00:33:36,390 --> 00:33:40,670
在视频或16杯，总共有多少个
步骤，它需要对它们进行排序

783
00:33:40,670 --> 00:33:41,550
归并排序？

784
00:33:41,550 --> 00:33:45,790
它实际上不是一个明显的答案，
因为现在你有排序

785
00:33:45,790 --> 00:33:48,500
递归地回答这个公式。

786
00:33:48,500 --> 00:33:51,190
>> 不过没关系，因为让我提出
我们做到以下几点。

787
00:33:51,190 --> 00:33:56,670
所涉及的时间，16人进行排序或
16杯将要被表示的

788
00:33:56,670 --> 00:33:58,020
一般为T 16。

789
00:33:58,020 --> 00:34:01,400
但是，这等于，根据我们的
前面的公式，2倍量

790
00:34:01,400 --> 00:34:04,780
所花费的时间进行排序
8杯加16。

791
00:34:04,780 --> 00:34:08,590
再次，加16是合并的时候，
两个时间T 8是

792
00:34:08,590 --> 00:34:10,790
左半边和右半边的时间进行排序。

793
00:34:10,790 --> 00:34:11,989
>> 但是，这是不够的。

794
00:34:11,989 --> 00:34:13,210
我们必须在更深的潜水。

795
00:34:13,210 --> 00:34:16,409
这意味着我们必须回答
问题，什么是T的8？

796
00:34:16,409 --> 00:34:19,610
T的8井仅2
4加8的时间T。

797
00:34:19,610 --> 00:34:20,520
那么，什么是T的4？

798
00:34:20,520 --> 00:34:23,780
仅有2 2加4倍t T的4。

799
00:34:23,780 --> 00:34:25,489
那么，什么是T的2？

800
00:34:25,489 --> 00:34:29,030
仅有2倍的T 1加2的T 2。

801
00:34:29,030 --> 00:34:31,940
>> 再次，我们是一种越来越
在这个循环中卡住。

802
00:34:31,940 --> 00:34:34,790
但它即将袭来
所谓的基本情况。

803
00:34:34,790 --> 00:34:37,310
因为什么是T的1，我们要求？

804
00:34:37,310 --> 00:34:37,810
0。

805
00:34:37,810 --> 00:34:39,730
所以，现在我们终于可以倒退。

806
00:34:39,730 --> 00:34:44,290
>> 如果T 1是0，我现在可以回去最多一个
这个家伙在这里排队，我可以

807
00:34:44,290 --> 00:34:46,330
插头为T 0 1。

808
00:34:46,330 --> 00:34:51,770
因此，这意味着它等于2倍零，
否则被称为0，加2。

809
00:34:51,770 --> 00:34:53,739
使整个表达式为2。

810
00:34:53,739 --> 00:34:58,740
>> 现在，如果我走T 2，其答案
2，将其插入中间线，T

811
00:34:58,740 --> 00:35:02,740
4，给我的2倍
2加4，所以8。

812
00:35:02,740 --> 00:35:07,080
如果我再插在8到前
行，这给了我2次，8，16。

813
00:35:07,080 --> 00:35:12,470
而如果我们再继续，随着
24，增加16，我们终于得到一个

814
00:35:12,470 --> 00:35:13,820
值64。

815
00:35:13,820 --> 00:35:18,480
>> 现在，本身并排序讲
无关的符号n，

816
00:35:18,480 --> 00:35:20,700
大O，欧米茄，我们已经看到
一直在谈论。

817
00:35:20,700 --> 00:35:24,890
但事实证明，64确实是
如图16所示，输入大小，

818
00:35:24,890 --> 00:35:27,110
登录基地2 16。

819
00:35:27,110 --> 00:35:30,200
如果这是一个有点陌生，只是
回头想想，它会回来

820
00:35:30,200 --> 00:35:30,700
你最终。

821
00:35:30,700 --> 00:35:33,775
如果这是2为底，​​它就像2
提出了什么给你16？

822
00:35:33,775 --> 00:35:36,380
哦，那是4，所以它的16倍4。

823
00:35:36,380 --> 00:35:39,380
>> 再次，它不是一个大不了的，如果这
现在是那种朦胧的记忆。

824
00:35:39,380 --> 00:35:43,720
但现在，信仰
16日志16是64。

825
00:35:43,720 --> 00:35:46,590
因此，事实上，这个简单的理智
检查，我们确认 - 

826
00:35:46,590 --> 00:35:48,250
但没有正式证实 - 

827
00:35:48,250 --> 00:35:52,800
运行时间合并
排序的确是N个记录Ñ。

828
00:35:52,800 --> 00:35:53,790
>> 所以不坏。

829
00:35:53,790 --> 00:35:57,260
这绝对是优于
到目前为止，我们已经看到，算法

830
00:35:57,260 --> 00:36:00,710
这是因为我们已经利用，一，
一种技术，称为递归。

831
00:36:00,710 --> 00:36:03,880
但比这更有趣，
概念的分裂和征服。

832
00:36:03,880 --> 00:36:07,460
再次，真正实现0周的东西，
即使现在是反复出现在

833
00:36:07,460 --> 00:36:08,740
更引人注目的方式。

834
00:36:08,740 --> 00:36:11,750
>> 现在一个有趣的小运动，如果你
从来没有做过这样的 - 你可能

835
00:36:11,750 --> 00:36:14,660
不会有，因为正常排序
人们不认为做到这一点。

836
00:36:14,660 --> 00:36:20,650
但是，如果我去google.com和
我想了解一些有关

837
00:36:20,650 --> 00:36:22,356
递归，回车。

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [笑]

840
00:36:29,058 --> 00:36:32,030
[笑声]

841
00:36:32,030 --> 00:36:33,385
国宝马兰：糟糕的玩笑慢慢蔓延。

842
00:36:33,385 --> 00:36:34,450
[笑]

843
00:36:34,450 --> 00:36:36,970
国宝MALAN：以防万一，它的存在。

844
00:36:36,970 --> 00:36:38,710
我没有拼写错了，
的笑话。

845
00:36:38,710 --> 00:36:40,810
好的。

846
00:36:40,810 --> 00:36:42,950
解释一下你旁边的人，如果
但相当点击只是还没有。

847
00:36:42,950 --> 00:36:47,650
但是，递归，更一般地，是指
的过程中的函数调用

848
00:36:47,650 --> 00:36:51,430
本身，或者更一般地，将一个
到东西，可以是问题

849
00:36:51,430 --> 00:36:56,220
头痛医头，脚痛医脚的解决解决相同
代表性的问题。

850
00:36:56,220 --> 00:36:58,400
>> 好吧，让我们改变齿轮
只是一瞬间。

851
00:36:58,400 --> 00:37:00,840
我们喜欢在某些悬念结束，
让我们开始设置

852
00:37:00,840 --> 00:37:05,870
在舞台上，几分钟，
一个非常简单的想法 - 

853
00:37:05,870 --> 00:37:07,620
交换两个元素，对不对？

854
00:37:07,620 --> 00:37:10,040
所有这些算法，我们已经
谈论过去几

855
00:37:10,040 --> 00:37:12,420
讲座涉及到一些
交换排序。

856
00:37:12,420 --> 00:37:14,630
今天，它是用他们得到
出自己的椅子，

857
00:37:14,630 --> 00:37:18,570
走动，但在代码中，我们将
只是从一个数组元素

858
00:37:18,570 --> 00:37:20,370
扑通到另一个。

859
00:37:20,370 --> 00:37:21,880
>> 那么，我们如何去这样做呢？

860
00:37:21,880 --> 00:37:24,850
好吧，让我继续写
这里的快速程序。

861
00:37:24,850 --> 00:37:31,600
我要继续做
这是以下。

862
00:37:31,600 --> 00:37:33,910
让我们把这个 - 

863
00:37:33,910 --> 00:37:38,070
我们要调用这个什么？

864
00:37:38,070 --> 00:37:38,650
>> 事实上，没有。

865
00:37:38,650 --> 00:37:39,420
让我快退。

866
00:37:39,420 --> 00:37:41,220
我不想这样做
吊人胃口。

867
00:37:41,220 --> 00:37:42,270
它会破坏其中的乐趣。

868
00:37:42,270 --> 00:37:43,600
让我们做到这一点，而不是。

869
00:37:43,600 --> 00:37:47,430
>> 假设我想写一点
现在方案，并拥抱

870
00:37:47,430 --> 00:37:48,700
递归的想法。

871
00:37:48,700 --> 00:37:50,370
我种了自己。

872
00:37:50,370 --> 00:37:51,420
我要做到以下几点。

873
00:37:51,420 --> 00:38:00,220
>> 首先，快速包括标准io.h
以及包括cs50.h.

874
00:38:00,220 --> 00:38:03,200
然后我要继续前进
并宣布INT主要无效

875
00:38:03,200 --> 00:38:04,360
在通常的方式。

876
00:38:04,360 --> 00:38:07,920
我意识到我已经名不副实的文件，所以
我想补充的扩展名，在这里，所以

877
00:38:07,920 --> 00:38:09,510
我们可以正确编译。

878
00:38:09,510 --> 00:38:10,970
启动此功能。

879
00:38:10,970 --> 00:38:13,290
>> 的功能，我想写点什么，相当
简单地说，就是要求

880
00:38:13,290 --> 00:38:16,210
用户输入一个数字，然后添加
之间的数字

881
00:38:16,210 --> 00:38:19,920
数，并说，0。

882
00:38:19,920 --> 00:38:22,510
所以，首先我要继续前进
并宣布INT N。

883
00:38:22,510 --> 00:38:24,760
然后我复制一些代码，
我们已经使用了一段时间。

884
00:38:24,760 --> 00:38:26,660
虽然东西是真实的。

885
00:38:26,660 --> 00:38:28,000
我会回来在某一时刻。

886
00:38:28,000 --> 00:38:29,010
>> 我想要做的是什么呢？

887
00:38:29,010 --> 00:38:33,460
我想说的printf积极
请整数。

888
00:38:33,460 --> 00:38:36,130
然后我要去
说N变得到诠释。

889
00:38:36,130 --> 00:38:38,800
如此反复，一些样板代码
我们以前用过的。

890
00:38:38,800 --> 00:38:40,810
我要做到这一点
而n是小于1。

891
00:38:40,810 --> 00:38:44,120
因此，这将确保用户
给我一个正整数。

892
00:38:44,120 --> 00:38:45,490
>> 现在我要做到以下几点。

893
00:38:45,490 --> 00:38:51,020
我想补充的所有号码
介于1和n或0且n

894
00:38:51,020 --> 00:38:52,570
等价地，得到的总和。

895
00:38:52,570 --> 00:38:55,100
所以大的sigma符号
您可能还记得。

896
00:38:55,100 --> 00:38:59,050
所以我要做到这一点首先调用
一个函数调用西格玛，

897
00:38:59,050 --> 00:39:06,030
在n传递给它，然后我要去
printf的说，答案是正确的。

898
00:39:06,030 --> 00:39:08,180
>> 因此，在短期，我得到
int的来自用户的。

899
00:39:08,180 --> 00:39:09,280
我保证它的正面。

900
00:39:09,280 --> 00:39:12,700
我声明了一个变量叫做答案
int类型，存储在它的回报

901
00:39:12,700 --> 00:39:15,610
西格玛值作为输入，通过在n。

902
00:39:15,610 --> 00:39:17,060
然后，我打印出这个问题的答案。

903
00:39:17,060 --> 00:39:19,550
>> 不幸的是，即使西格玛的声音
喜欢的东西，可能是在

904
00:39:19,550 --> 00:39:24,040
math.h的文件，它的声明，
它实际上不是。

905
00:39:24,040 --> 00:39:24,690
所以，这是确定的。

906
00:39:24,690 --> 00:39:26,170
我可以实现自己。

907
00:39:26,170 --> 00:39:29,160
我要去执行一个函数调用
标准差，它会采取

908
00:39:29,160 --> 00:39:29,900
参数 - 

909
00:39:29,900 --> 00:39:32,100
让我们只是把它M，只是
所以它是不同的。

910
00:39:32,100 --> 00:39:35,910
然后在这里，我要说的话，
以及，如果m是小于1  - 这是一个

911
00:39:35,910 --> 00:39:38,180
很无趣程序。

912
00:39:38,180 --> 00:39:41,700
所以，我要继续前进，
立即返回0。

913
00:39:41,700 --> 00:39:45,920
它只是无厘头加起来
如果m 1和m之间的数

914
00:39:45,920 --> 00:39:48,470
本身是0或负数。

915
00:39:48,470 --> 00:39:50,900
>> 然后我要继续前进
做到这一点非常迭代。

916
00:39:50,900 --> 00:39:53,090
我会做这样的老派，
我要继续前进

917
00:39:53,090 --> 00:39:57,150
并说，我要去
声明总和为0。

918
00:39:57,150 --> 00:39:59,630
然后，我将不得不
一个循环的int  - 

919
00:39:59,630 --> 00:40:02,820
并让我这样做符合我们的
分销代码，让您拥有一个副本

920
00:40:02,820 --> 00:40:07,500
在家里。 INT I上得到1
i是小于或等于m。

921
00:40:07,500 --> 00:40:09,430
我+ +。

922
00:40:09,430 --> 00:40:11,430
然后将里面的for循环 - 

923
00:40:11,430 --> 00:40:12,440
我们几乎没有 - 

924
00:40:12,440 --> 00:40:15,810
总和得到的总和加上1。

925
00:40:15,810 --> 00:40:17,670
然后我要返回的总和。

926
00:40:17,670 --> 00:40:19,420
>> 所以我这样做很快，
诚然相当。

927
00:40:19,420 --> 00:40:22,775
但同样，主要功能是相当
简单的，基于代码我们已经

928
00:40:22,775 --> 00:40:23,190
书面迄今。

929
00:40:23,190 --> 00:40:25,610
采用双循环，得到了肯定
int的来自用户的。

930
00:40:25,610 --> 00:40:29,870
然后，我通过这个int到一个新的功能
叫西格玛，调用它，再次，正。

931
00:40:29,870 --> 00:40:33,100
我存储的返回值，得到的答案
从目前黑盒子

932
00:40:33,100 --> 00:40:35,460
已知作为σ，在一个变量中
叫的答案。

933
00:40:35,460 --> 00:40:36,580
然后，我打印出来。

934
00:40:36,580 --> 00:40:39,090
>> 如果我们现在继续的故事，
西格玛是如何实施？

935
00:40:39,090 --> 00:40:40,840
我建议如下推行。

936
00:40:40,840 --> 00:40:43,560
首先，一点点的错误检查
以确保该用户的不

937
00:40:43,560 --> 00:40:46,480
梅辛与我并传入
一些负面或0值。

938
00:40:46,480 --> 00:40:49,710
然后我声明了一个变量
综上所述，将它设置为0。

939
00:40:49,710 --> 00:40:55,910
>> 现在，我开始从i等于
1所有的方式，包括米，

940
00:40:55,910 --> 00:41:00,130
因为我想包括所有
数字从1到m，首尾。

941
00:41:00,130 --> 00:41:04,350
这里面的for循环，我只是做
总和得到现在不管它是什么，再加上

942
00:41:04,350 --> 00:41:08,900
i的值。

943
00:41:08,900 --> 00:41:10,370
加上i的值。

944
00:41:10,370 --> 00:41:14,090
>> 顺便说一句，如果你没有看到这
之前，有一些语法糖

945
00:41:14,090 --> 00:41:14,870
此行。

946
00:41:14,870 --> 00:41:21,120
我可以改写为加等于I，
只是为了保存自己敲几下键盘

947
00:41:21,120 --> 00:41:22,570
看起来有点凉。

948
00:41:22,570 --> 00:41:23,140
但是这一切。

949
00:41:23,140 --> 00:41:24,660
它的功能同样的事情。

950
00:41:24,660 --> 00:41:26,710
>> 不幸的是，这种代码的
不会还编译。

951
00:41:26,710 --> 00:41:31,600
如果我运行make的西格玛0，怎么我
我大叫？

952
00:41:31,600 --> 00:41:33,473
什么是它不喜欢呢？

953
00:41:33,473 --> 00:41:35,740
>> 观众：[听不清]。

954
00:41:35,740 --> 00:41:37,800
>> 国宝马兰：是啊，我没有申报
向上顶，右边的功能？

955
00:41:37,800 --> 00:41:40,590
C是一种愚蠢的，它仅
做什么你告诉它的事情，而你

956
00:41:40,590 --> 00:41:41,880
必须这样做的顺序。

957
00:41:41,880 --> 00:41:45,910
所以如果我打在这里输入，我要
关于Sigma隐警告

958
00:41:45,910 --> 00:41:46,860
声明。

959
00:41:46,860 --> 00:41:48,120
>> 哦，不是一个问题。

960
00:41:48,120 --> 00:41:50,370
我可以去到顶部，我可以
说，没事的，请等待一分钟。

961
00:41:50,370 --> 00:41:54,240
六西格玛是一个函数，返回
一个int，并预期

962
00:41:54,240 --> 00:41:56,620
int作为输入，分号。

963
00:41:56,620 --> 00:41:59,550
或者，我可以把整个功能
上述主要的，但在一般情况下，最好

964
00:41:59,550 --> 00:42:02,260
针对该建议，因为它是
很高兴上面的顶部，所以总是有主

965
00:42:02,260 --> 00:42:06,310
可以潜水的权利，并知道什么是
程序首先通过阅读主要做。

966
00:42:06,310 --> 00:42:07,930
>> 所以，现在让我清楚的画面。

967
00:42:07,930 --> 00:42:09,330
重拍0西格玛。

968
00:42:09,330 --> 00:42:10,340
所有似乎退房。

969
00:42:10,340 --> 00:42:11,970
让我跑SIGMA 0。

970
00:42:11,970 --> 00:42:12,770
正间。

971
00:42:12,770 --> 00:42:15,580
我给它的数量
3，以保持它的简单。

972
00:42:15,580 --> 00:42:18,710
所以，应该给我3
加2加1，所以6。

973
00:42:18,710 --> 00:42:20,750
回车，我确实得到6。

974
00:42:20,750 --> 00:42:21,820
>> 我可以做更大的东西 - 

975
00:42:21,820 --> 00:42:24,080
50，12，75。

976
00:42:24,080 --> 00:42:27,690
正如切线，我要做的
可笑的东西像一个真正的大

977
00:42:27,690 --> 00:42:30,375
号，呵呵，那实际工作 - 

978
00:42:30,375 --> 00:42:31,600
诶，我不认为这是正确的。

979
00:42:31,600 --> 00:42:32,810
让我们来看看。

980
00:42:32,810 --> 00:42:34,060
让我们真的惹它。

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> 这是一个问题。

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
这是怎么回事呢？

985
00:42:44,970 --> 00:42:46,050
该代码是没有那么糟糕。

986
00:42:46,050 --> 00:42:48,470
它仍然是线性的。

987
00:42:48,470 --> 00:42:50,810
吹口哨是一个很好的效果，虽然。

988
00:42:50,810 --> 00:42:52,060
这是怎么回事呢？

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> 不知道如果我听到它。

991
00:42:55,620 --> 00:42:57,620
因此，原来 - 
这是作为一个旁白。

992
00:42:57,620 --> 00:42:59,400
这不是核心到
递归的想法。

993
00:42:59,400 --> 00:43:02,480
事实证明，是因为我试图
代表这样一个大的数字，最

994
00:43:02,480 --> 00:43:06,980
它可能被误解
C作为一个并不乐观的数字，

995
00:43:06,980 --> 00:43:09,980
但负数。

996
00:43:09,980 --> 00:43:12,690
>> 我们还没有谈到这一点，但它
原来有负数

997
00:43:12,690 --> 00:43:14,210
在世界上除了
正数。

998
00:43:14,210 --> 00:43:16,290
和手段，通过它可以
表示负数

999
00:43:16,290 --> 00:43:19,530
基本上是，你使用一个
特殊的位来指示

1000
00:43:19,530 --> 00:43:20,400
正面负面以上。

1001
00:43:20,400 --> 00:43:22,950
这是一个有点比这更复杂，
但是这是最基本的想法。

1002
00:43:22,950 --> 00:43:26,740
>> 不幸的是，如果C是混乱的一个
那些位作为实际意义，

1003
00:43:26,740 --> 00:43:30,790
哦，这是一个负号，我的循环
在这里，例如，实际上是从来没有

1004
00:43:30,790 --> 00:43:31,740
要终止。

1005
00:43:31,740 --> 00:43:33,850
所以，如果我实际打印的东西
一遍又一遍，我们会

1006
00:43:33,850 --> 00:43:34,650
看到一大堆。

1007
00:43:34,650 --> 00:43:36,220
但是，这是除了点。

1008
00:43:36,220 --> 00:43:38,590
这是真的只是一种
对知识的好奇心，我们还会回来

1009
00:43:38,590 --> 00:43:39,550
最终备份。

1010
00:43:39,550 --> 00:43:43,400
但现在，这是一个正确的
如果我们假设执行

1011
00:43:43,400 --> 00:43:45,970
用户将提供整数
适合内整数。

1012
00:43:45,970 --> 00:43:49,370
>> 但我要求这个代码，坦率地说，
可以做简单得多。

1013
00:43:49,370 --> 00:43:54,060
如果在手的目标是采取多项
像米，加起来所有的

1014
00:43:54,060 --> 00:43:59,510
之间的数字，并且1，或反过来
介于1和它，我要求

1015
00:43:59,510 --> 00:44:03,380
我可以借用这种想法，合并
排序了，这是一个问题

1016
00:44:03,380 --> 00:44:05,660
这种规模和分割
成更小的东西。

1017
00:44:05,660 --> 00:44:09,875
也许不是一半，但规模较小，但
代表性地是相同的。

1018
00:44:09,875 --> 00:44:12,130
同样的想法，但一个较小的问题。

1019
00:44:12,130 --> 00:44:15,470
>> 因此，实际上，我 - 让我好好保存这个文件
不同的版本号。

1020
00:44:15,470 --> 00:44:17,670
我们称这个版本
1而不是0。

1021
00:44:17,670 --> 00:44:20,790
我要求其实我可以
这种重新实现此

1022
00:44:20,790 --> 00:44:22,160
心态弯曲方式。

1023
00:44:22,160 --> 00:44:23,710
>> 我要独自离开它的一部分。

1024
00:44:23,710 --> 00:44:27,710
我会说，如果m是
或者甚至等于0  - 

1025
00:44:27,710 --> 00:44:29,280
我只是要一点点
肛门

1026
00:44:29,280 --> 00:44:30,520
我的错误检查 - 

1027
00:44:30,520 --> 00:44:33,190
我要继续前进，返回0。

1028
00:44:33,190 --> 00:44:34,490
这是任意的。

1029
00:44:34,490 --> 00:44:37,500
我只是简单地决定，如果用户
我给了我一个负数，

1030
00:44:37,500 --> 00:44:41,490
返回0，他们应该已经读过
的文档更加紧密。

1031
00:44:41,490 --> 00:44:42,170
>> 其他 - 

1032
00:44:42,170 --> 00:44:44,070
注意什么，我要做的事情。

1033
00:44:44,070 --> 00:44:49,260
否则，我要返回米加 - 

1034
00:44:49,260 --> 00:44:51,010
什么是西格玛米？

1035
00:44:51,010 --> 00:44:56,710
那么，Σ的m加m减1，
加m的负2，加m零下3。

1036
00:44:56,710 --> 00:44:58,030
我不想写出来。

1037
00:44:58,030 --> 00:44:59,120
我为什么不只是撑船？

1038
00:44:59,120 --> 00:45:05,080
递归调用自己稍微
规模较小的问题，分号，

1039
00:45:05,080 --> 00:45:06,840
收工？

1040
00:45:06,840 --> 00:45:07,040
>> 对吗？

1041
00:45:07,040 --> 00:45:10,980
现在在这里，太，你可能会感到或担心
这是一个无限循环，我

1042
00:45:10,980 --> 00:45:15,450
诱导，由此我实现
西格玛致电西格玛。

1043
00:45:15,450 --> 00:45:20,342
但是，这是完全确定的，因为我
想提前增加了哪条线路？

1044
00:45:20,342 --> 00:45:22,600
>> 观众：[听不清]。

1045
00:45:22,600 --> 00:45:25,430
>> 国宝马兰：23日至26日，
是我的，如果条件。

1046
00:45:25,430 --> 00:45:28,390
因为关于什么是好的
减法这里，因为我保持

1047
00:45:28,390 --> 00:45:31,180
交给西格玛小问题，小
的问题，更小的 - 它不是

1048
00:45:31,180 --> 00:45:31,870
的一半大小。

1049
00:45:31,870 --> 00:45:34,380
这只是一小步，
不过没关系。

1050
00:45:34,380 --> 00:45:38,050
因为最终，我们将继续努力
我们一路下跌为1或0。

1051
00:45:38,050 --> 00:45:41,630
一旦我们打0，Sigma的不
会调用本身了。

1052
00:45:41,630 --> 00:45:43,590
这将立即返回0。

1053
00:45:43,590 --> 00:45:47,960
>> 所以效果，如果你样的风
在你的心中，是增加M PLUS

1054
00:45:47,960 --> 00:45:52,740
M减1，加m减2，加m减
3，加点，点，点，M减

1055
00:45:52,740 --> 00:45:57,820
米，最终给你0，
最终效果添加的所有

1056
00:45:57,820 --> 00:45:59,070
这些东西放在一起。

1057
00:45:59,070 --> 00:46:02,380
所以，我们还没有，用递归
解决了这个问题，我们

1058
00:46:02,380 --> 00:46:03,470
之前没能解决。

1059
00:46:03,470 --> 00:46:06,840
事实上，版本0，每
问题到今天为止，已经解

1060
00:46:06,840 --> 00:46:09,980
只需使用循环或在
循环或类似的结构。

1061
00:46:09,980 --> 00:46:13,150
>> 但是，递归，我敢说，给我们
以不同的方式思考

1062
00:46:13,150 --> 00:46:17,010
问题，因此如果我们可以采取一个
问题，除从东西

1063
00:46:17,010 --> 00:46:22,340
到有些东西有点大
较小的，我要求，我们可以解决这个问题

1064
00:46:22,340 --> 00:46:26,040
也许是多了几分优雅条款
设计，用更少的代码，

1065
00:46:26,040 --> 00:46:30,980
甚至解决的问题，会
更难，因为我们最终会

1066
00:46:30,980 --> 00:46:33,280
看到，解决纯属迭代。

1067
00:46:33,280 --> 00:46:35,980
>> 但扣人心弦的，我没有
要离开我们是这样的。

1068
00:46:35,980 --> 00:46:40,720
让我继续前进，打开
一个文件 - 

1069
00:46:40,720 --> 00:46:44,300
其实，让我去
这样做真正的快。

1070
00:46:44,300 --> 00:46:46,875
让我继续前进，并提出
以下。

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
其中今天的代码是这样的文件在这里。

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
在这里，这一个noswap。

1075
00:47:03,050 --> 00:47:06,260
>> 所以这是一个愚蠢的小程序，
我掀起了要求做

1076
00:47:06,260 --> 00:47:06,940
以下。

1077
00:47:06,940 --> 00:47:10,140
在main中，它首先声明
为int，名为x和分配

1078
00:47:10,140 --> 00:47:11,100
为1的值。

1079
00:47:11,100 --> 00:47:13,520
然后，它声明int y和
分配值2。

1080
00:47:13,520 --> 00:47:15,310
然后打印出x和y是什么。

1081
00:47:15,310 --> 00:47:17,781
然后，它说，交换，点点点。

1082
00:47:17,781 --> 00:47:21,670
>> 然后，它声称要调用一个函数
称为交换，传递x和

1083
00:47:21,670 --> 00:47:24,290
Y，其中的想法是，希望
x和y会回来

1084
00:47:24,290 --> 00:47:25,620
不同的，相反的。

1085
00:47:25,620 --> 00:47:27,110
然后，它声称交换！

1086
00:47:27,110 --> 00:47:28,420
一个惊叹号。

1087
00:47:28,420 --> 00:47:30,190
然后打印出x和y。

1088
00:47:30,190 --> 00:47:33,480
>> 但事实证明，这很
简单的演示下来

1089
00:47:33,480 --> 00:47:35,570
这里是实际马车。

1090
00:47:35,570 --> 00:47:38,870
即使我宣布一个临时的
变量和暂时把

1091
00:47:38,870 --> 00:47:42,010
它，然后我重新分配
一个b的值 - 

1092
00:47:42,010 --> 00:47:45,080
觉得合理，因为我
保存副本的温度。

1093
00:47:45,080 --> 00:47:48,410
然后我更新b等于
无论是在温度。

1094
00:47:48,410 --> 00:47:51,610
这类壳移动游戏
到b和b成通过使用该

1095
00:47:51,610 --> 00:47:54,360
中间人名为temp的感觉
完全合理的。

1096
00:47:54,360 --> 00:47:57,270
>> 但我要求当我运行这个
代码，我现在要做的 - 

1097
00:47:57,270 --> 00:47:59,490
让我继续前进，将其粘贴在这里。

1098
00:47:59,490 --> 00:48:01,995
我会打电话给这个noswap.c。

1099
00:48:01,995 --> 00:48:05,630
顾名思义，这是不
将是一个正确的程序。

1100
00:48:05,630 --> 00:48:09,460
让noswap /无掉。

1101
00:48:09,460 --> 00:48:12,110
x是1，y是2，交换，交换。

1102
00:48:12,110 --> 00:48:14,220
x为1时，y是2。

1103
00:48:14,220 --> 00:48:16,920
这是从根本上是错误的，甚至
虽然这似乎是完美的

1104
00:48:16,920 --> 00:48:17,730
合理的，我。

1105
00:48:17,730 --> 00:48:21,330
还有一个原因，但我们不
要揭示的原因，只是还没有。

1106
00:48:21,330 --> 00:48:24,610
>> 现在我想的第二个扣人心弦的
离开你，

1107
00:48:24,610 --> 00:48:27,120
公布各种优惠券代码。

1108
00:48:27,120 --> 00:48:31,590
今年我们的创新与已故天
激起了不平凡的数字

1109
00:48:31,590 --> 00:48:33,830
的问题，这是
不是我们的本意。

1110
00:48:33,830 --> 00:48:36,590
这些优惠券代码的意图，
据此，如果你这样做是问题的一部分

1111
00:48:36,590 --> 00:48:39,850
提前设置，从而获得一个额外的一天，
真的帮助你们有所帮助

1112
00:48:39,850 --> 00:48:42,420
自己年初开始，排序
激励你。

1113
00:48:42,420 --> 00:48:44,880
有助于我们之间分配负载
办公时间更好地使

1114
00:48:44,880 --> 00:48:45,740
它的排序共赢。

1115
00:48:45,740 --> 00:48:48,860
>> 不幸的是，我觉得我的指示
没有，到今天为止，已经很清楚，所以

1116
00:48:48,860 --> 00:48:52,230
我又回到这个周末更新
规格更大，更大胆的文字

1117
00:48:52,230 --> 00:48:53,600
解释这些子弹。

1118
00:48:53,600 --> 00:48:56,900
只是说它更公开，
默认情况下，问题集将于周四

1119
00:48:56,900 --> 00:48:58,400
日中午，按照教学大纲。

1120
00:48:58,400 --> 00:49:02,030
如果你起步早，完成一部分
周三12:00设置问题

1121
00:49:02,030 --> 00:49:05,170
下午，部分，涉及到的优惠券
代码，这个想法是，你可以扩展

1122
00:49:05,170 --> 00:49:07,710
您的截止日期为
P设定至周五。

1123
00:49:07,710 --> 00:49:10,890
也就是说，咬下一小部分的P
设置通常是相对

1124
00:49:10,890 --> 00:49:13,200
更大的问题，你买
自己一个额外的一天。

1125
00:49:13,200 --> 00:49:15,190
再次，它可以让你思考
设置的问题，让你去

1126
00:49:15,190 --> 00:49:16,380
办公时间越快。

1127
00:49:16,380 --> 00:49:20,670
但优惠券代码的问题仍是
必需的，即使你不提交。

1128
00:49:20,670 --> 00:49:23,340
>> 但更令人信服的是这样的。

1129
00:49:23,340 --> 00:49:26,520
（舞台WHISPER），而那些人离开
早期是会后悔的。

1130
00:49:26,520 --> 00:49:28,620
乡亲在阳台上。

1131
00:49:28,620 --> 00:49:32,510
我提前给乡亲道歉
阳台上的原因，这将是

1132
00:49:32,510 --> 00:49:33,920
清除在短短的时刻。

1133
00:49:33,920 --> 00:49:37,050
>> 因此，我们很幸运，有一个
CS50的前任主管教学研究员

1134
00:49:37,050 --> 00:49:39,302
一家名为dropbox.com。

1135
00:49:39,302 --> 00:49:45,500
他们非常慷慨地捐出了
优惠券代码，这里这么大的空间，

1136
00:49:45,500 --> 00:49:48,180
这是从
平时的2千兆字节。

1137
00:49:48,180 --> 00:49:51,740
所以我想我们会做这个
最后要注意的是做一点的赠品，

1138
00:49:51,740 --> 00:49:55,380
在短短的时刻，我们将揭示
赢家有优惠券

1139
00:49:55,380 --> 00:49:57,980
代码，然后你可以去他们的
网站，键入它，瞧，得到了

1140
00:49:57,980 --> 00:50:01,370
一大堆更多的Dropbox空间为您的
家电和您的个人文件。

1141
00:50:01,370 --> 00:50:05,690
>> 第一，谁愿意参加
在该图中？

1142
00:50:05,690 --> 00:50:09,630
OK，现在这使得它更有趣。

1143
00:50:09,630 --> 00:50:14,010
人谁收到这25千兆字节
优惠券代码 - 这是远远

1144
00:50:14,010 --> 00:50:16,150
更引人注目的莫过于后期
现在，也许是 - 

1145
00:50:16,150 --> 00:50:20,620
是一个谁是坐在最重要的一个
座垫下方有

1146
00:50:20,620 --> 00:50:21,620
该优惠券代码。

1147
00:50:21,620 --> 00:50:23,480
现在，您可以看下面
您的坐垫。

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [视频回放]

1150
00:50:29,680 --> 00:50:31,620
>> 一个，两个，三个。

1151
00:50:31,620 --> 00:50:35,015
>> [尖叫]

1152
00:50:35,015 --> 00:50:35,985
>> 你得到一辆车！

1153
00:50:35,985 --> 00:50:36,670
你得到一辆车！

1154
00:50:36,670 --> 00:50:37,970
>> 国宝马兰：我们将看到
上周三。

1155
00:50:37,970 --> 00:50:38,904
>> 你得到一辆车！

1156
00:50:38,904 --> 00:50:39,371
你得到一辆车！

1157
00:50:39,371 --> 00:50:40,305
你得到一辆车！

1158
00:50:40,305 --> 00:50:41,706
你得到一辆车！

1159
00:50:41,706 --> 00:50:43,107
你得到一辆车！

1160
00:50:43,107 --> 00:50:45,530
>> 国宝马兰：阳台乡亲，来
这里到前面，

1161
00:50:45,530 --> 00:50:46,866
在那里我们有演员。

1162
00:50:46,866 --> 00:50:50,282
>>  - 每个人都得到一辆车！

1163
00:50:50,282 --> 00:50:52,234
人人都有车！

1164
00:50:52,234 --> 00:50:52,722
>> [END视频播放]

1165
00:50:52,722 --> 00:50:54,590
>> 旁白：在未来CS50  - 

1166
00:50:54,590 --> 00:51:00,374
>> 扬声器5：哦，我的天哪天哪天哪天哪
天哪天哪天哪天哪天哪天哪 - 

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE戏剧]