1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> 演讲嘉宾：好的，这是CS50。

3
00:00:14,910 --> 00:00:19,020
这是3周结束时，如果
你有没有冤大头不已，

4
00:00:19,020 --> 00:00:21,790
知道，会有午餐
这个星期五和往常一样，在那里

5
00:00:21,790 --> 00:00:25,430
您可以享受良好的交谈
食品在火与冰

6
00:00:25,430 --> 00:00:27,980
一些CS50年代
工作人员和同学。

7
00:00:27,980 --> 00:00:30,170
前往这个网址在这里。

8
00:00:30,170 --> 00:00:33,420
>> 现在，你可能还记得，或者你
可能很快被认识，

9
00:00:33,420 --> 00:00:35,970
这些东西在这里，这
在最后给出了

10
00:00:35,970 --> 00:00:37,850
的学期很多类。

11
00:00:37,850 --> 00:00:40,870
所谓考试蓝色书籍，其中
你写你的答案考试。

12
00:00:40,870 --> 00:00:44,240
现在我已经在这里等26
蓝色的书，对他们每个人

13
00:00:44,240 --> 00:00:47,580
通过Z.写着的名字，a和
不愧是名是简单，一

14
00:00:47,580 --> 00:00:50,490
到Z和一
手头今天的目标

15
00:00:50,490 --> 00:00:53,910
将是继续什么
我们开始在星期一，这是不

16
00:00:53,910 --> 00:00:57,830
这么多看代码，但真正
寻找思路和解决问题的能力。

17
00:00:57,830 --> 00:01:00,170
其中一个目标，
本课程的承诺

18
00:01:00,170 --> 00:01:02,985
是教你去思考更多
细心，更有条理，

19
00:01:02,985 --> 00:01:05,400
并且更有效地解决问题。

20
00:01:05,400 --> 00:01:09,526
事实上，我们能做到这一点真的
甚至没有触及一行代码。

21
00:01:09,526 --> 00:01:12,150
所以，我有一对夫妇的大象
在这里今天，橙，蓝，

22
00:01:12,150 --> 00:01:15,780
如果我们能找到一名志愿者，
也许从更远的背面比平常。

23
00:01:15,780 --> 00:01:18,070
怎么样在那里，下来吧。

24
00:01:18,070 --> 00:01:24,180
它的目的将是对
帮助再加上这里管理这门考试。

25
00:01:24,180 --> 00:01:24,935
你叫什么名字？

26
00:01:24,935 --> 00:01:25,768
>> 听众：玛丽·贝丝。

27
00:01:25,768 --> 00:01:27,560
演讲嘉宾：玛丽·贝丝，上来吧。

28
00:01:27,560 --> 00:01:29,560
让我的麦克风为您服务。

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
很高兴认识你。

31
00:01:32,880 --> 00:01:34,005
>> 听众：很高兴见到你。

32
00:01:34,005 --> 00:01:36,790
演讲嘉宾：好，让我有
这里蓝皮书A到Z，

33
00:01:36,790 --> 00:01:41,680
我要去假装
我有一个学生，

34
00:01:41,680 --> 00:01:45,770
而他们来的有点随意
在三个小时的考试块的末尾，

35
00:01:45,770 --> 00:01:49,400
所以他们结束了在某些
半随机的顺序是这样的。

36
00:01:49,400 --> 00:01:54,510
现在，在短短的一瞬间你的工作是怎么回事
以be--这其实是他们如何获得

37
00:01:54,510 --> 00:01:56,820
在结束时打开在
类，最有可能的。

38
00:01:56,820 --> 00:02:01,120
你现在的工作将是，相当
简单地说，这些蓝色的书为我们梳理

39
00:02:01,120 --> 00:02:05,220
从A到Z

40
00:02:05,220 --> 00:02:08,400
>> 听众：哦，这是
要带下去。

41
00:02:08,400 --> 00:02:13,747
>> 演讲嘉宾：我们会看
当你做到这一点，没有压力。

42
00:02:13,747 --> 00:02:15,330
听众：没有，没有压力或任何东西。

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> 演讲嘉宾：而且为了好玩，
我们提出了一个定时器。

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> 听众：太好玩了，太好玩了。

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> 演讲嘉宾：我可以抱麦克风为您服务。

49
00:02:38,574 --> 00:02:40,240
好吧，我们刚刚增加了一倍我们的速度。

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
所以在此期间，让我带来什么
要成为玛丽贝丝问题

52
00:02:49,060 --> 00:02:51,540
是什么，是她做的，怎么会是
她打算着手解决呢？

53
00:02:51,540 --> 00:02:54,040
而事实上，你可能没有
没有想过的东西

54
00:02:54,040 --> 00:02:57,440
如此简单，当你挑选的
高达26本书就是这样，

55
00:02:57,440 --> 00:02:59,350
它确实有一个自然的
订购他们。

56
00:02:59,350 --> 00:03:01,335
过程是怎样的
你实际上使用？

57
00:03:01,335 --> 00:03:03,770
它是相当随机的只是
挑选你看到的第一个

58
00:03:03,770 --> 00:03:05,250
并把它在它的地方？

59
00:03:05,250 --> 00:03:09,680
你首先将双手左右
寻找，然后找乙？

60
00:03:09,680 --> 00:03:11,722
你看看在
他们两人并排

61
00:03:11,722 --> 00:03:14,680
而只是说，等一下，这
是不对的，然后交换顺序？

62
00:03:14,680 --> 00:03:16,960
我们已经看到在周一
这有许多方法

63
00:03:16,960 --> 00:03:22,140
在其中我们可以做到这一点，
的确，我们附近结束了，

64
00:03:22,140 --> 00:03:26,360
我会留意可能
什么玛丽·贝丝在做什么。

65
00:03:26,360 --> 00:03:30,040
我们有几堆，似乎一个
更大的一个，三个小的。

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> 听众：我命令他们
当我找到两封信

68
00:03:36,415 --> 00:03:39,540
我知道是一起在一个序列中，
我把它们放在一起，让我不

69
00:03:39,540 --> 00:03:42,915
不用担心保存
轨道书一整排的。

70
00:03:42,915 --> 00:03:45,706
这只是，呵呵，首先，
我这里有这个堆栈。

71
00:03:45,706 --> 00:03:47,580
演讲嘉宾：所以，几乎像
拼图的碎片

72
00:03:47,580 --> 00:03:49,860
有合适的形状，以
相互匹配。

73
00:03:49,860 --> 00:03:51,026
听众：好看多了，是啊。

74
00:03:51,026 --> 00:03:55,320
演讲嘉宾：好的，优秀的。

75
00:03:55,320 --> 00:03:59,850
现在每个这些
桩的大概排序？

76
00:03:59,850 --> 00:04:00,990
>> 听众：是的。

77
00:04:00,990 --> 00:04:09,900
>> 演讲嘉宾：好的，从A到Z的所有
没错，恭喜你，你做到了。

78
00:04:09,900 --> 00:04:11,461
你有你的选择。

79
00:04:11,461 --> 00:04:11,960
蓝？

80
00:04:11,960 --> 00:04:13,530
好吧，谢谢你了。

81
00:04:13,530 --> 00:04:16,679
因此，玛丽·都建议
什么她的做法是，

82
00:04:16,679 --> 00:04:19,720
但什么是另一种方法，你如何
可能去整理这些东西？

83
00:04:19,720 --> 00:04:21,130
你会怎么做？

84
00:04:21,130 --> 00:04:24,060
击败的纪录会一直
一分钟，50秒左右，

85
00:04:24,060 --> 00:04:26,039
再加上那些我忘了算。

86
00:04:26,039 --> 00:04:27,080
你会怎么做？

87
00:04:27,080 --> 00:04:27,579
是吗？

88
00:04:27,579 --> 00:04:28,735
听众：以堆栈。

89
00:04:28,735 --> 00:04:29,776
从起始处开始。

90
00:04:29,776 --> 00:04:32,284
请检查您的论文。

91
00:04:32,284 --> 00:04:36,586
如果最上面的一个是高
不是，也许，他们是，

92
00:04:36,586 --> 00:04:38,980
底部的一个是
高，然后切换他们。

93
00:04:38,980 --> 00:04:41,300
>> 演讲嘉宾：好，那么开始
在顶部和底部，

94
00:04:41,300 --> 00:04:43,716
然后你的工作方式
向内那样，交换呢？

95
00:04:43,716 --> 00:04:46,580
好了，有点类似
在精神冒泡排序，

96
00:04:46,580 --> 00:04:49,160
但选择极端
不相邻的对。

97
00:04:49,160 --> 00:04:52,080
但是它的短是，有
当然了一堆不同的方式

98
00:04:52,080 --> 00:04:54,210
我们可以做到这一点，
坦率地说，我觉得你真好

99
00:04:54,210 --> 00:04:55,700
通过几个途径，对不对？

100
00:04:55,700 --> 00:05:00,567
你做那种四堆排序，并
然后有效地融合在一起。

101
00:05:00,567 --> 00:05:02,650
那就是，敢说，另一
技术完全。

102
00:05:02,650 --> 00:05:06,950
你没有把它当作一个大的一堆，
你划分的问题分为四个四边形，

103
00:05:06,950 --> 00:05:09,820
如果你愿意，然后以某种方式
合并它们的末端。

104
00:05:09,820 --> 00:05:13,410
>> 因此，让我们考虑，最终，
怎么回事我们可以做到这一点。

105
00:05:13,410 --> 00:05:15,860
我们形式化的概念
的冒泡排序最后一次，

106
00:05:15,860 --> 00:05:18,780
和冒泡排序召回是一个
算法，我们可视化

107
00:05:18,780 --> 00:05:22,640
八你的同学在这里，
起初看似随机排列。

108
00:05:22,640 --> 00:05:26,110
然后我们决定成对的，如果
两个元素是无序，

109
00:05:26,110 --> 00:05:26,950
简单地交换他们。

110
00:05:26,950 --> 00:05:28,930
于是四加二
显然失灵，

111
00:05:28,930 --> 00:05:31,080
所以这两个同班同学
交换位置。

112
00:05:31,080 --> 00:05:35,390
然后，我们重复了四和六，
然后6和8，在每次迭代中，

113
00:05:35,390 --> 00:05:36,980
移动到右侧。

114
00:05:36,980 --> 00:05:42,590
>> 所以，给八人，有多少配对
比较我做了，而走路

115
00:05:42,590 --> 00:05:45,220
左到右在一个这样的迭代？

116
00:05:45,220 --> 00:05:48,410
有多少的比较？

117
00:05:48,410 --> 00:05:49,197
七，对不对？

118
00:05:49,197 --> 00:05:51,405
因为如果有8
人，但你有一双

119
00:05:51,405 --> 00:05:53,880
他们和你继续前进
1跳的权利，

120
00:05:53,880 --> 00:05:56,060
你不会有八
比较，因为你不能比较

121
00:05:56,060 --> 00:05:59,226
对本身的元素，否则会
仅仅是毫无意义的，让你有七。

122
00:05:59,226 --> 00:06:01,290
或者更一般地，如果
我们有N多人，我们

123
00:06:01,290 --> 00:06:04,300
做了N减1的比较
用冒泡排序。

124
00:06:04,300 --> 00:06:08,150
>> 所以，现在让我们考虑如何好或
坏的泡沫实际上是排序，并尝试

125
00:06:08,150 --> 00:06:13,570
给自己用的词汇
这在像这样的批判算法，

126
00:06:13,570 --> 00:06:14,430
很快我们自己。

127
00:06:14,430 --> 00:06:16,970
所以，通过第一通
冒泡排序，在第一时间

128
00:06:16,970 --> 00:06:20,909
我是从左边走到对面的权利
现阶段，我花了Ñ减1的比较。

129
00:06:20,909 --> 00:06:22,950
而这将是我的
计量单位的，对不对？

130
00:06:22,950 --> 00:06:26,170
我是那种说话，散步，
有些快，有些慢，

131
00:06:26,170 --> 00:06:29,300
所以我计算的秒数
没有特别明显的，

132
00:06:29,300 --> 00:06:32,260
但计数的数目
我确实在周一的操作，

133
00:06:32,260 --> 00:06:35,900
比较两个人，那种感觉
就像衡量一个不错的单位。

134
00:06:35,900 --> 00:06:40,980
>> 因此n减1的步骤是第一次，
但之后发生了什么？

135
00:06:40,980 --> 00:06:46,610
什么是一传一上攻
通过其他未分类列表？

136
00:06:46,610 --> 00:06:49,840
你能告诉我该元素
谁是一路过来吗？

137
00:06:49,840 --> 00:06:51,300
是吗？

138
00:06:51,300 --> 00:06:52,870
这是最大的因素，对不对？

139
00:06:52,870 --> 00:06:55,710
第八，即使她
从这里开始，我每次

140
00:06:55,710 --> 00:06:57,860
对她比较
一个邻居，她不停地

141
00:06:57,860 --> 00:07:00,480
冒泡向右
列表中的右手侧。

142
00:07:00,480 --> 00:07:02,710
事实上，这正是
该算法得名。

143
00:07:02,710 --> 00:07:07,630
>> 现在，通过这一逻辑，有多少的比较
需要我做的第二次

144
00:07:07,630 --> 00:07:09,800
我作出这样的传球从左至右？

145
00:07:09,800 --> 00:07:10,730
Ñ​​减2，对吧？

146
00:07:10,730 --> 00:07:14,297
这纯粹是在浪费我的时间，如果我
保持比较8人反对某人

147
00:07:14,297 --> 00:07:16,630
别的，因为我们已经知道
她是在正确的地方。

148
00:07:16,630 --> 00:07:19,760
所以这是一个比特的
优化，所以下通

149
00:07:19,760 --> 00:07:23,899
将是加N减去两个步骤
其中n是人的数目。

150
00:07:23,899 --> 00:07:26,940
现在你可以种推断，即使
如果你不是一名计算机科学家，

151
00:07:26,940 --> 00:07:27,680
如何结束。

152
00:07:27,680 --> 00:07:31,259
在此算法结束时，据推测
你有只是一个比较离去。

153
00:07:31,259 --> 00:07:33,800
你有一种固定的
在案例二开始列表

154
00:07:33,800 --> 00:07:36,540
一都失灵
并应一和二，

155
00:07:36,540 --> 00:07:40,330
所以这个谷底的
加1最后的比较。

156
00:07:40,330 --> 00:07:44,500
>> 现在，点，点，点样波是
手在一些多汁详情

157
00:07:44,500 --> 00:07:46,452
但我们只是继​​续和简化。

158
00:07:46,452 --> 00:07:48,660
如果您还记得高
学校，坦率地说，很多你

159
00:07:48,660 --> 00:07:50,340
有数学书的有
有点小抄

160
00:07:50,340 --> 00:07:52,550
前盖或
后盖表明您

161
00:07:52,550 --> 00:07:56,400
什么系列求和样
这最终加起来。

162
00:07:56,400 --> 00:07:59,600
在一般情况下，如果你有一个
变量如N，而事实上这其中，

163
00:07:59,600 --> 00:08:01,634
如果你看着你
老同学的数学书，

164
00:08:01,634 --> 00:08:04,050
你会看到，这实际上
加起来这笔款项在这里，

165
00:08:04,050 --> 00:08:07,970
n次Ñ减1都除以2。

166
00:08:07,970 --> 00:08:11,172
所以现在我只想规定
这是真的，那么对信仰的飞跃，

167
00:08:11,172 --> 00:08:12,880
这就是这个总结
最多，我们可以

168
00:08:12,880 --> 00:08:14,341
证明，在更一般的情况。

169
00:08:14,341 --> 00:08:15,590
但现在让我们展开了这一点。

170
00:08:15,590 --> 00:08:19,920
因此，让我们乘了这一点，所以这是
Ñ​​平方，减去N，所有除以2。

171
00:08:19,920 --> 00:08:23,200
这真的Ñ平方，
除以2，再减去Ñ超过2，

172
00:08:23,200 --> 00:08:25,010
所以这是所有漂亮和有趣。

173
00:08:25,010 --> 00:08:27,060
但是，如果我们发生
现在Plug-in的价值呢？

174
00:08:27,060 --> 00:08:29,724
假设我没有8
人，但说一百万。

175
00:08:29,724 --> 00:08:31,890
和一百万只是因为
这是一个非常大的数字，

176
00:08:31,890 --> 00:08:34,039
让我们插上，在看看会发生什么。

177
00:08:34,039 --> 00:08:39,039
所以，如果我插上一百万到该公式
我要拿到一百万平方，

178
00:08:39,039 --> 00:08:42,868
除以2，减去
万元，除以2。

179
00:08:42,868 --> 00:08:44,159
现在，那是要一样的吗？

180
00:08:44,159 --> 00:08:47,354
所以500十亿，减去50万元。

181
00:08:47,354 --> 00:08:49,270
如果我实际上做
在数学，这表示

182
00:08:49,270 --> 00:08:53,920
该排序一百万
人与冒泡排序

183
00:08:53,920 --> 00:09:01,800
可能要花费499999500000
在结束步骤或比较，

184
00:09:01,800 --> 00:09:02,900
我们只是推断。

185
00:09:02,900 --> 00:09:06,860
>> 这感觉很慢，但坦率地说
测量一个特定的输入

186
00:09:06,860 --> 00:09:09,160
像这样，是不是所有的说服力。

187
00:09:09,160 --> 00:09:14,050
但事实上，这确实表明，当n
变大，该算法

188
00:09:14,050 --> 00:09:16,280
那种感觉差，
更糟的是，不然你真的

189
00:09:16,280 --> 00:09:20,450
开始感受到了疼痛
幂，使得n的平方，

190
00:09:20,450 --> 00:09:21,770
这些加起来非常快。

191
00:09:21,770 --> 00:09:25,340
而这个细节不
失去了对的人，其实

192
00:09:25,340 --> 00:09:29,640
几年前，某参议员谁是
竞选活动，坐下来接受采访

193
00:09:29,640 --> 00:09:32,180
与谷歌的埃里克
施密特，当时的CEO，

194
00:09:32,180 --> 00:09:36,380
并与一个问题的挑战
就像我们今天探讨。

195
00:09:36,380 --> 00:09:38,468
让我们一起来看看。

196
00:09:38,468 --> 00:09:45,280
>> [视频回放]

197
00:09:45,280 --> 00:09:48,560
>> -Senator，你在这里
在谷歌，我喜欢

198
00:09:48,560 --> 00:09:53,382
认为总统的
作为一个工作面试。

199
00:09:53,382 --> 00:09:56,434
现在，它是很难得到
一份工作，担任总裁，

200
00:09:56,434 --> 00:09:58,100
你正在经历的严酷了。

201
00:09:58,100 --> 00:10:01,860
这也很难找到一份工作，在谷歌。

202
00:10:01,860 --> 00:10:05,490
我们有问题，我们
要求我们的考生的问题，

203
00:10:05,490 --> 00:10:09,770
而这一次是从拉里·施维默。

204
00:10:09,770 --> 00:10:14,760
What--你们觉得我
开玩笑，这是在这里。

205
00:10:14,760 --> 00:10:17,930
什么是最有效的方式来
排序一百万的32位整数？

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -I'm对不起，maybe--

209
00:10:25,200 --> 00:10:27,400
>> 不，不，不。

210
00:10:27,400 --> 00:10:30,700
我认为，冒泡排序
将错误的路要走。

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> -COMe上，谁告诉他的？

213
00:10:38,180 --> 00:10:40,590
我没有看到电脑
科学的背景。

214
00:10:40,590 --> 00:10:42,130
>> -We've了在那里我们的间谍。

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>>  - 确定，让我们问一个不同的
面试问题。

217
00:10:48,444 --> 00:10:49,300
>> [完视频回放]

218
00:10:49,300 --> 00:10:52,290
>> 演讲嘉宾：所以说起
具体的数字，虽然，

219
00:10:52,290 --> 00:10:53,890
不会是那么有用。

220
00:10:53,890 --> 00:10:56,810
这不是一个生活的一课泡沫
排序，给定一个亿的投入，

221
00:10:56,810 --> 00:10:58,590
可能需要多达500十亿步骤。

222
00:10:58,590 --> 00:11:01,120
你真的不能一概而论
从太有效

223
00:11:01,120 --> 00:11:03,560
做出好的设计决定
编写程序时。

224
00:11:03,560 --> 00:11:07,070
因此，让我们虽然把重点放在如何
我们可以简化这个结果。

225
00:11:07,070 --> 00:11:11,780
>> 所以，我在这里黄色高亮
n的结果的平方除以2，

226
00:11:11,780 --> 00:11:14,330
所以一百万平方
除以2，然后

227
00:11:14,330 --> 00:11:16,710
我已经强调了什么
最终的答案是

228
00:11:16,710 --> 00:11:20,180
一旦我们减去关闭N除以2。

229
00:11:20,180 --> 00:11:24,850
并声称我会做，现在是，
谁的心里很不舒服，如果你减去了关心

230
00:11:24,850 --> 00:11:30,060
一老一少Ñ超过2时，第一
这个公式的一部分，是这么多的大吗？

231
00:11:30,060 --> 00:11:33,910
它支配着其他
长期，N的平方除以2

232
00:11:33,910 --> 00:11:37,510
如此多的大，显然，作为
n变大像一百万，

233
00:11:37,510 --> 00:11:41,450
这是真的，在一个很大的区别
一天500十亿之间到底

234
00:11:41,450 --> 00:11:45,730
和499999500000？

235
00:11:45,730 --> 00:11:46,349
并不是的。

236
00:11:46,349 --> 00:11:48,640
还等什么，我们要
做计算机科学家是

237
00:11:48,640 --> 00:11:53,270
忽略这些低阶条款及
采取这样的事情，真的

238
00:11:53,270 --> 00:11:56,050
只需将它简化为
术语，是怎么回事无所谓。

239
00:11:56,050 --> 00:12:00,315
在我们的大数据集得到的，更大的
我们的数据库中得到的，就越网页

240
00:12:00,315 --> 00:12:02,690
我们必须搜索，越
朋友你在Facebook。

241
00:12:02,690 --> 00:12:07,340
>> 当n变大，我们真的
要关心大

242
00:12:07,340 --> 00:12:11,560
长期在任何此类分析
我们的算法性能。

243
00:12:11,560 --> 00:12:16,230
而我要说，你知道吗，
冒泡排序是大O的顺序，

244
00:12:16,230 --> 00:12:18,060
n的顺序上的平方。

245
00:12:18,060 --> 00:12:20,090
这不恰好n
方如我们所看到的，

246
00:12:20,090 --> 00:12:22,060
但谁真正关心
那些小的方面，

247
00:12:22,060 --> 00:12:24,390
坦率地说，谁真正
关心，如果我们除以2？

248
00:12:24,390 --> 00:12:25,870
这只是一个常数因子。

249
00:12:25,870 --> 00:12:29,480
并为500十亿与250
十亿真有那么大的一笔交易？

250
00:12:29,480 --> 00:12:32,190
我可以等一年，
让我的笔记本电脑逐字

251
00:12:32,190 --> 00:12:34,810
得到两倍于硬件的速度，
等诸如此类的差异

252
00:12:34,810 --> 00:12:36,650
刚刚消失，自然随着时间的推移。

253
00:12:36,650 --> 00:12:39,300
>> 我们关心的是什么
的表达，该部

254
00:12:39,300 --> 00:12:42,489
那将改变表达的
作为我们的输入变得越来越大。

255
00:12:42,489 --> 00:12:45,280
事实上，在现实世界中，
这就是正在发生的事情越来越多

256
00:12:45,280 --> 00:12:48,330
是投入到我们的问题，
算法越来越大。

257
00:12:48,330 --> 00:12:53,470
因此，大O将是符号，
渐近符号，我们只

258
00:12:53,470 --> 00:12:57,160
利用计算机科学家描述
的性能，或在运行时间，

259
00:12:57,160 --> 00:12:58,130
的算法。

260
00:12:58,130 --> 00:13:00,800
这样我们就可以比较算法
写上不同的计算机

261
00:13:00,800 --> 00:13:04,170
由不同的人，通过使用
一些基本相似度量

262
00:13:04,170 --> 00:13:07,557
喜欢比较的次数你
制作，或者互换的数量

263
00:13:07,557 --> 00:13:08,140
你正在做的。

264
00:13:08,140 --> 00:13:11,910
>> 我们不是要
计数的时间量

265
00:13:11,910 --> 00:13:13,981
传递上的时钟
墙壁上的典型。

266
00:13:13,981 --> 00:13:16,230
我们不是要担心
大约是多少内存

267
00:13:16,230 --> 00:13:17,820
您使用的是今天
至少，尽管这

268
00:13:17,820 --> 00:13:19,370
另一种资源，我们可以衡量的。

269
00:13:19,370 --> 00:13:23,610
我们要尽量立足分析
上只是基本操作，那些，

270
00:13:23,610 --> 00:13:25,930
坦率地说，你可以看到最直观。

271
00:13:25,930 --> 00:13:30,700
因此，与类似的n大O
平方，我要求是n的平方Ò

272
00:13:30,700 --> 00:13:35,820
是一个上限，所谓
运行冒泡排序的时间。

273
00:13:35,820 --> 00:13:38,820
换句话说，如果
希望声称有

274
00:13:38,820 --> 00:13:41,370
上多少这个上限
几步之遥的算法可能需要，

275
00:13:41,370 --> 00:13:46,240
这将是n的大O
平方在这种情况下，一个上限。

276
00:13:46,240 --> 00:13:49,710
>> 如果我不是改变
故事是不是冒泡排序，

277
00:13:49,710 --> 00:13:50,910
但这个上限。

278
00:13:50,910 --> 00:13:54,030
你能想到的算法
我们已经看过了已经

279
00:13:54,030 --> 00:13:59,530
其上限，最大
测量的时间或操作

280
00:13:59,530 --> 00:14:04,300
将所述有界
用n，一个线性函数，

281
00:14:04,300 --> 00:14:07,260
没有二次一个是弯曲？

282
00:14:07,260 --> 00:14:10,780
什么是算法
始终把没有更多的

283
00:14:10,780 --> 00:14:12,860
不是像n步，或
2n个步骤，或3N步骤？

284
00:14:12,860 --> 00:14:13,360
是吗？

285
00:14:13,360 --> 00:14:15,030
>> 听众：寻找
列表中的最大号码是多少？

286
00:14:15,030 --> 00:14:16,930
>> 音箱：完美，找到
在列表中的最大数。

287
00:14:16,930 --> 00:14:18,940
如果我给出的名单
人，例如，

288
00:14:18,940 --> 00:14:21,440
各是谁在持有一个号码，
什么是最大数

289
00:14:21,440 --> 00:14:23,770
步骤应该带我，
一个相当聪明的人，

290
00:14:23,770 --> 00:14:27,530
找到最大的人在该列表中？

291
00:14:27,530 --> 00:14:28,100
N，对不对？

292
00:14:28,100 --> 00:14:31,320
由于在最坏的情况下，当
也许最大的价值是什么？

293
00:14:31,320 --> 00:14:32,700
右，一路在末端。

294
00:14:32,700 --> 00:14:34,575
所以在最坏的情况下
上界，我可能

295
00:14:34,575 --> 00:14:36,450
要一路走下去
在这里是这样，

296
00:14:36,450 --> 00:14:39,170
哦，这里的数字8，
或任何该值。

297
00:14:39,170 --> 00:14:41,330
现在，这纯粹是愚蠢的
如果我坚持下来了，对不对？

298
00:14:41,330 --> 00:14:43,840
寻找更多的元素
如果最后他们是在那里？

299
00:14:43,840 --> 00:14:45,340
因此可以肯定，n是一个上限。

300
00:14:45,340 --> 00:14:47,420
我不需要拿
比更多的步骤。

301
00:14:47,420 --> 00:14:51,580
>> 那么，如果不是我提出的
还有在这个世界上的算法，

302
00:14:51,580 --> 00:14:57,750
有一个运行时间的
通过日志的n大O范围内，日志N？

303
00:14:57,750 --> 00:15:00,390
那里有我们以前见过吗？

304
00:15:00,390 --> 00:15:00,890
是吗？

305
00:15:00,890 --> 00:15:03,309
>> 听众：在电话簿的问题？

306
00:15:03,309 --> 00:15:04,850
演讲嘉宾：像电话簿的问题。

307
00:15:04,850 --> 00:15:07,754
什么是如何的量度
太多的时间和多少眼泪吧

308
00:15:07,754 --> 00:15:10,170
带我找到喜欢的人
迈克·史密斯在电话簿？

309
00:15:10,170 --> 00:15:13,212
我们要求它是数n和
即使不熟悉，或者是

310
00:15:13,212 --> 00:15:15,170
一点点朦胧什么
对数或指数为，

311
00:15:15,170 --> 00:15:17,650
只记得为log N
一般是指在过程中

312
00:15:17,650 --> 00:15:20,790
在这种情况下，分割
东西两半又一次，又一次，

313
00:15:20,790 --> 00:15:25,790
又一次，又一次，使得其
变的越来越小，你这样做。

314
00:15:25,790 --> 00:15:28,470
>> 因此，日志正指，当然，
到电话簿例如

315
00:15:28,470 --> 00:15:32,662
在理论的二进制搜索，当我们
有虚拟门电路板上，

316
00:15:32,662 --> 00:15:34,370
或者当肖恩
寻找的东西。

317
00:15:34,370 --> 00:15:37,374
如果他用二进制搜索，日志N
将上限多少

318
00:15:37,374 --> 00:15:38,040
时间花费。

319
00:15:38,040 --> 00:15:44,027
但是，那些跑在算法
日志N承担哪些关键的细节？

320
00:15:44,027 --> 00:15:45,360
该列表进行排序，对不对？

321
00:15:45,360 --> 00:15:47,789
你的算法是错误的，如果
您输入不排序，

322
00:15:47,789 --> 00:15:49,830
可是你用
像二进制搜索

323
00:15:49,830 --> 00:15:51,704
因为你可能会跳
右以上的元素

324
00:15:51,704 --> 00:15:53,600
没有意识到这是真的在那里。

325
00:15:53,600 --> 00:15:55,600
>> 现在什么可能意味着一，大O？

326
00:15:55,600 --> 00:15:59,117
这并不意味着你的算法
采用一个和唯一的一个步骤，

327
00:15:59,117 --> 00:16:01,200
它只是意味着它需要一个
步骤恒定数目。

328
00:16:01,200 --> 00:16:04,060
也许是1，也许是
10，也许是1,000

329
00:16:04,060 --> 00:16:07,750
但它是独立的
问题的大小。

330
00:16:07,750 --> 00:16:10,850
无论多么大的n是，
一个常数时间算法

331
00:16:10,850 --> 00:16:12,747
始终以相同的步骤号码。

332
00:16:12,747 --> 00:16:15,080
那么，什么可能是一个算法
我们已经讨论过，或只是

333
00:16:15,080 --> 00:16:20,418
直观地说来你
总是在所谓的恒定时间运行？

334
00:16:20,418 --> 00:16:20,918
是吗？

335
00:16:20,918 --> 00:16:22,001
>> 听众：两个数相加。

336
00:16:22,001 --> 00:16:25,320
音箱：两个数相加，
2加2等于4，完成。

337
00:16:25,320 --> 00:16:27,227
因此，可能的工作，还有什么？

338
00:16:27,227 --> 00:16:28,560
如何更真实的世界，是吗？

339
00:16:28,560 --> 00:16:30,686
>> 听众：寻找
列表中的第一件事情。

340
00:16:30,686 --> 00:16:32,810
演讲嘉宾：寻找第一
元素在列表中，确保万无一失。

341
00:16:32,810 --> 00:16:34,540
实际上我们一直在谈论
关于数组已经，

342
00:16:34,540 --> 00:16:36,540
你怎么在得到
在数组的第一元素，

343
00:16:36,540 --> 00:16:40,465
无论多久
数组是C代码？

344
00:16:40,465 --> 00:16:43,090
您只需要使用像支架
零符号，咣当，你在那里。

345
00:16:43,090 --> 00:16:46,120
事实上阵列，顺便说一句，
支持的东西一般称为

346
00:16:46,120 --> 00:16:49,240
随机存取，随机存取
记忆，因为你可以从字面上

347
00:16:49,240 --> 00:16:50,284
跳转到任何一个地方。

348
00:16:50,284 --> 00:16:52,700
我们可以做到这一点，甚至更简单
我们可以倒回至零一周

349
00:16:52,700 --> 00:16:53,900
当我们做划伤。

350
00:16:53,900 --> 00:16:59,707
它没有多少时间了
要说块划痕执行？

351
00:16:59,707 --> 00:17:00,790
就在固定的时间，对不对？

352
00:17:00,790 --> 00:17:03,960
说些什么，说
东西，也没关系

353
00:17:03,960 --> 00:17:07,359
大划痕世界是怎样的，它总是
要采取相同的时间量

354
00:17:07,359 --> 00:17:08,490
简单地说一下。

355
00:17:08,490 --> 00:17:11,089
>> 所以这是一定的时间，
但什么是另一面？

356
00:17:11,089 --> 00:17:13,030
如果这是上
界，如果我们想要什么

357
00:17:13,030 --> 00:17:17,089
描述下界
我们的算法的运行时间？

358
00:17:17,089 --> 00:17:19,852
几乎是最好的情况
潜在的，如果你愿意，

359
00:17:19,852 --> 00:17:23,060
尽管这些条款可以适用于最
的情况下，最坏的情况下，一般情况下，更多的

360
00:17:23,060 --> 00:17:26,359
一般，但我们只关注
上下限比较一般。

361
00:17:26,359 --> 00:17:31,920
什么是算法，具有
下界n个步骤，

362
00:17:31,920 --> 00:17:33,350
或2N步骤，或3N步骤？

363
00:17:33,350 --> 00:17:36,241
n个步骤的一些因素，
这就是它的下限。

364
00:17:36,241 --> 00:17:36,740
是吗？

365
00:17:36,740 --> 00:17:37,910
>> 听众：冒泡排序？

366
00:17:37,910 --> 00:17:41,610
>> 演讲嘉宾：冒泡排序需要
你最低限度n步，为什么呢？

367
00:17:41,610 --> 00:17:42,279
这是为什么？

368
00:17:42,279 --> 00:17:45,320
为什么会这样开始来找你
直观地说，即使它不只是

369
00:17:45,320 --> 00:17:46,530
没有？

370
00:17:46,530 --> 00:17:47,030
是吗？

371
00:17:47,030 --> 00:17:47,990
>> 听众：[听不清]。

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
演讲嘉宾：没错。

374
00:17:52,360 --> 00:17:55,810
在可能的最佳方案
冒泡排序，和大量的算法，

375
00:17:55,810 --> 00:17:58,769
如果我交给你八人
谁是已经排序，

376
00:17:58,769 --> 00:18:00,560
那将是愚蠢的
你的算法，

377
00:18:00,560 --> 00:18:02,202
去来回
不止一次，对不对？

378
00:18:02,202 --> 00:18:04,285
因为只要你
通过列表步行一次，

379
00:18:04,285 --> 00:18:08,090
你应该明白，哦，我什么也没有
掉期，这个列表进行排序，退出。

380
00:18:08,090 --> 00:18:09,700
但是，要定你n步。

381
00:18:09,700 --> 00:18:12,033
>> 反之，什么又
考虑这个问题的方法是什么？

382
00:18:12,033 --> 00:18:15,240
冒泡排序是欧米茄，
这么说的n，，

383
00:18:15,240 --> 00:18:19,050
因为如果你看一下
少于n个元素，是什么

384
00:18:19,050 --> 00:18:23,009
是根本问题吗？

385
00:18:23,009 --> 00:18:24,550
你不知道，如果它的排序，正确的。

386
00:18:24,550 --> 00:18:26,800
我们人类的威力一目了然八
人是这样，哦，它的排序，

387
00:18:26,800 --> 00:18:28,430
未带我n步，但它没有。

388
00:18:28,430 --> 00:18:30,810
你的眼睛，即使你有种
有愿景的一大领域，

389
00:18:30,810 --> 00:18:33,184
你看八素，
你看着八人，

390
00:18:33,184 --> 00:18:34,610
这八个步骤有效。

391
00:18:34,610 --> 00:18:38,612
而只有当我在整个行走
名单我知道，是的，排序。

392
00:18:38,612 --> 00:18:41,320
如果我中途停止思考，所有的
没错，这是相当排序到目前为止，

393
00:18:41,320 --> 00:18:42,520
什么是它没有排序的几率有多大？

394
00:18:42,520 --> 00:18:44,186
该机制的算法不会是正确的。

395
00:18:44,186 --> 00:18:46,250
可能会更快，但不正确的。

396
00:18:46,250 --> 00:18:48,500
>> 所以，现在我们有办法
描述一个下界，

397
00:18:48,500 --> 00:18:49,710
和什么有关固定时间？

398
00:18:49,710 --> 00:18:54,565
什么是算法，该算法具有较低的
绑定在它的一个运行时间？

399
00:18:54,565 --> 00:18:58,350
1步，2步，10步，但
恒定的，独立的n，

400
00:18:58,350 --> 00:18:59,310
输入的大小？

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
是的，在后面。

403
00:19:04,600 --> 00:19:05,309
>> 听众：printf的？

404
00:19:05,309 --> 00:19:06,183
演讲嘉宾：那是什么？

405
00:19:06,183 --> 00:19:07,184
听众：printf的？

406
00:19:07,184 --> 00:19:07,850
演讲嘉宾：printf的。

407
00:19:07,850 --> 00:19:08,400
好了，肯定的。

408
00:19:08,400 --> 00:19:10,720
所以它需要一个固定的步数。

409
00:19:10,720 --> 00:19:13,170
我现在应该是now--
我们正在谈论的C代码

410
00:19:13,170 --> 00:19:16,040
不挠，事
如说，与printf的，

411
00:19:16,040 --> 00:19:17,710
我们应该开始变得谨慎。

412
00:19:17,710 --> 00:19:21,090
因为printf的确实需要
输入时，它是一个字符串，

413
00:19:21,090 --> 00:19:23,220
和字符串做技术上有长度。

414
00:19:23,220 --> 00:19:25,530
因此，如果我们现在要挑
对你，如果你不介意的话，

415
00:19:25,530 --> 00:19:29,430
在技​​术上，我们可以认为，printf的
确实需要一个可变长度的输入，

416
00:19:29,430 --> 00:19:32,270
并肯定它可能需要更多的
这漫长的时间来打印字符串，

417
00:19:32,270 --> 00:19:33,560
比这个长。

418
00:19:33,560 --> 00:19:36,570
>> 因此，如果我们考虑一下刚才的
排序和搜索的例子吗？

419
00:19:36,570 --> 00:19:40,450
怎么样迈克·史密斯在手机
书，或二进制搜索更普遍？

420
00:19:40,450 --> 00:19:42,220
在最好的情况下，可能会发生什么？

421
00:19:42,220 --> 00:19:45,577
我打开电话本和，BAM，
还有麦克·史密斯的电话号码。

422
00:19:45,577 --> 00:19:46,660
我可以打电话给他的时候了。

423
00:19:46,660 --> 00:19:49,390
>> 进了一步，也许两个步骤，
但是步骤的恒定数

424
00:19:49,390 --> 00:19:50,230
如果我很幸运。

425
00:19:50,230 --> 00:19:52,570
坦率地说，我们看到了
周一你的同学

426
00:19:52,570 --> 00:19:54,710
在连续得到相当幸运的两倍。

427
00:19:54,710 --> 00:19:57,050
而这的确是恒
时间在下限

428
00:19:57,050 --> 00:20:01,280
在算法中的问题查找
数50落后结束

429
00:20:01,280 --> 00:20:01,830
门。

430
00:20:01,830 --> 00:20:06,400
>> 现在，顺便说一句，如果你发现
这两个大澳，上界，

431
00:20:06,400 --> 00:20:09,310
和ω，下界，
是在同一个，即

432
00:20:09,310 --> 00:20:11,830
是在相同的配方
括号中，你也可以

433
00:20:11,830 --> 00:20:15,170
说，只是华丽，
这东西是时间值损耗

434
00:20:15,170 --> 00:20:18,270
n或西塔的其他价值。

435
00:20:18,270 --> 00:20:20,661
这只是意味着大当
O和ω-是相同的。

436
00:20:20,661 --> 00:20:21,910
现在怎么样选择排序？

437
00:20:21,910 --> 00:20:23,400
让我们用这个新的词汇。

438
00:20:23,400 --> 00:20:27,407
在选择排序，什么是我们
老毛病又犯，又一次，又一次？

439
00:20:27,407 --> 00:20:29,990
我来回通过
在列表中，寻找谁呢？

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
最小数量。

442
00:20:34,730 --> 00:20:37,560
>> 所以，要走多少步，如何
很多比较没有我

443
00:20:37,560 --> 00:20:43,250
必须作出，以找出谁
在列表中的最小元素是？

444
00:20:43,250 --> 00:20:44,437
Ñ​​减1，对不对？

445
00:20:44,437 --> 00:20:47,770
因为如果我刚入手一个我
鉴于我开始比较他或她，

446
00:20:47,770 --> 00:20:49,519
那么他或她，他
还是她，他或她，我

447
00:20:49,519 --> 00:20:52,010
只能对元素
一起Ñ减去1次。

448
00:20:52,010 --> 00:20:55,630
所以，选择排序同样需要
Ñ​​减1步的第一次。

449
00:20:55,630 --> 00:20:59,540
>> 多少步它带我去
找到第二个最小的元素？

450
00:20:59,540 --> 00:21:02,920
Ñ​​减2，因为我是哑巴
如果我一直在看同一人

451
00:21:02,920 --> 00:21:06,280
再次，如果我已经选中了他
或者她，把他们在他们的地方。

452
00:21:06,280 --> 00:21:09,270
和第三步骤中，正
减去3，则n减去4。

453
00:21:09,270 --> 00:21:11,020
我们已经看到这种模式
之前，确实

454
00:21:11,020 --> 00:21:13,460
选择排序相似
有一个上限

455
00:21:13,460 --> 00:21:16,210
n个平方，如果我们这样做了的总和。

456
00:21:16,210 --> 00:21:19,790
什么是它的下限，选择排序？

457
00:21:19,790 --> 00:21:25,350
最低限度，有多少时间必须选择
排序需要，因为我们将它定义在星期一？

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
提出了两个选项。

460
00:21:30,490 --> 00:21:32,360
也许这是N，和以前一样。

461
00:21:32,360 --> 00:21:35,040
也许这是Ñ平方，因为它
现在作为上限​​。

462
00:21:35,040 --> 00:21:35,874
>> 听众：N的平方。

463
00:21:35,874 --> 00:21:36,664
扬声器：N的平方。

464
00:21:36,664 --> 00:21:37,368
为什么呢？

465
00:21:37,368 --> 00:21:40,060
>> 听众：因为你
定义[听不清]。

466
00:21:40,060 --> 00:21:41,510
>> 演讲嘉宾：没错。

467
00:21:41,510 --> 00:21:45,077
至少我定义选择排序
这是非常幼稚的，坚持下去，

468
00:21:45,077 --> 00:21:46,160
找到的最小元素。

469
00:21:46,160 --> 00:21:47,770
又来了，找到的最小元素。

470
00:21:47,770 --> 00:21:49,490
又来了，找到的最小元素。

471
00:21:49,490 --> 00:21:51,700
有没有排序
在那里，最优化

472
00:21:51,700 --> 00:21:54,350
也许让我以后放弃
只是n或使步骤。

473
00:21:54,350 --> 00:21:57,080
所以，事实上，选择
排序，正欧米茄平方。

474
00:21:57,080 --> 00:22:00,667
>> 那么插入排序，在这里我把
我给谁，然后我一屁股坐在了他

475
00:22:00,667 --> 00:22:01,750
或她在正确的地方？

476
00:22:01,750 --> 00:22:04,958
我接着给第二个人，
一屁股坐在他或她在正确的地方。

477
00:22:04,958 --> 00:22:07,910
然后旁边的人，屁股
在正确的地方他或她。

478
00:22:07,910 --> 00:22:10,537
注意，这是非常
线性的，可以这么说。

479
00:22:10,537 --> 00:22:12,620
我是一条直线，我
不会来回，

480
00:22:12,620 --> 00:22:16,080
我从来没有回头真的，但
发生了什么，当我插入了他

481
00:22:16,080 --> 00:22:20,302
或她进入初
因为我们没有在周一的名单？

482
00:22:20,302 --> 00:22:21,010
发生了什么？

483
00:22:21,010 --> 00:22:21,510
是吗？

484
00:22:21,510 --> 00:22:23,122
听众：[听不清]。

485
00:22:23,122 --> 00:22:24,830
演讲嘉宾：是的，这
被抓了吧？

486
00:22:24,830 --> 00:22:26,746
你可能还记得，
你的同学，如果他们

487
00:22:26,746 --> 00:22:29,670
正在作出任何动作
他们的脚，这是一个操作。

488
00:22:29,670 --> 00:22:33,610
所以，如果有三个人在这里和
新人所属的方式在那边，

489
00:22:33,610 --> 00:22:37,360
在很长的阶段，像这样的，肯定的是，他
或者她只是去到了最后。

490
00:22:37,360 --> 00:22:40,074
但是，如果我们思考一个
计算机和存储器阵列，

491
00:22:40,074 --> 00:22:41,990
这些人会
有洗牌了

492
00:22:41,990 --> 00:22:43,260
让路给那个人。

493
00:22:43,260 --> 00:22:46,930
所以是n减1 shufflings，
Ñ​​减2 shufflings，正

494
00:22:46,930 --> 00:22:50,660
零下3 shufflings是正中下怀
发生在我后面，而不是在我面前

495
00:22:50,660 --> 00:22:52,710
像以前一样，在某种意义上。

499
00:22:52,557 --> 00:22:54,640
现在，作为一个一旁，并作为
你可能已经看到了网上

500
00:22:54,640 --> 00:22:57,699
如果你开始关注着有关
各种各样的，有这么多不同的人

501
00:22:57,699 --> 00:22:59,490
在那里，他们中的一些
比别人​​做得更好。

502
00:22:59,490 --> 00:23:02,200
事实上，bogosort是
这是一种乐趣来查找。

503
00:23:02,200 --> 00:23:06,650
Bogosort采用一组
数字或说一副扑克牌，

504
00:23:06,650 --> 00:23:09,870
随机打乱他们，
检查，如果他们来分类的。

505
00:23:09,870 --> 00:23:12,130
如果不是，它再次。

506
00:23:12,130 --> 00:23:14,140
如果不是，它再次。

507
00:23:14,140 --> 00:23:15,440
如果不是，它再次。

508
00:23:15,440 --> 00:23:17,060
令人难以置信的愚蠢。

509
00:23:17,060 --> 00:23:19,520
>> 事实上，如果你读
像维基百科的文章，

510
00:23:19,520 --> 00:23:21,200
它的绰号是愚蠢的排序。

511
00:23:21,200 --> 00:23:25,180
它最终会工作，
希望，给予足够的时间，

512
00:23:25,180 --> 00:23:28,240
但该时间量
可能需要相当长的一段时间。

513
00:23:28,240 --> 00:23:31,650
所以，如果我可以，让我们速度的东西
从早期的玛丽·贝丝的例子，

514
00:23:31,650 --> 00:23:35,150
通过具有几个元素，
但有两个以上处理器。

515
00:23:35,150 --> 00:23:37,100
两个人，如果你
不介意加入我。

516
00:23:37,100 --> 00:23:40,972
怎么样1在这里，和
让我们go--没有人在那里？

517
00:23:40,972 --> 00:23:41,722
没有人在那里？

518
00:23:41,722 --> 00:23:42,221
行。

519
00:23:42,221 --> 00:23:44,190
您与黑
衬衫，是的，下来吧。

520
00:23:44,190 --> 00:23:45,000
好吧，你叫什么名字？

521
00:23:45,000 --> 00:23:45,720
>> 听众：彼得。

522
00:23:45,720 --> 00:23:46,100
>> 演讲嘉宾：那是什么？

523
00:23:46,100 --> 00:23:46,766
>> 听众：彼得。

524
00:23:46,766 --> 00:23:49,450
演讲者：Peter，大卫，很高兴认识你。

525
00:23:49,450 --> 00:23:53,670
好吧，我们有彼得在这里，如果你
想来在桌上在这里。

526
00:23:53,670 --> 00:23:54,550
而你叫什么名字？

527
00:23:54,550 --> 00:23:55,216
>> 听众：艾琳娜。

528
00:23:55,216 --> 00:23:55,970
演讲嘉宾：艾琳娜。

529
00:23:55,970 --> 00:23:57,030
好了，很高兴见到你。

530
00:23:57,030 --> 00:23:58,060
埃琳娜满足彼得。

531
00:23:58,060 --> 00:23:59,170
彼得，埃琳娜。

532
00:23:59,170 --> 00:24:02,290
而我们需要安德鲁
在这里为好，请。

533
00:24:02,290 --> 00:24:06,107
和你的挑战是怎么回事
要以一副扑克牌排序。

534
00:24:06,107 --> 00:24:08,190
如果不熟悉，甲板
卡最终应

535
00:24:08,190 --> 00:24:11,064
排序有点像
这其中，我们会做的俱乐部，然后

536
00:24:11,064 --> 00:24:13,660
黑桃，则心和
钻石，从王牌为一体，

537
00:24:13,660 --> 00:24:15,570
一路到王。

538
00:24:15,570 --> 00:24:20,890
>> 该卡我打算给你
将要在数量52。

539
00:24:20,890 --> 00:24:23,160
我们将同样
一次，在短短的一瞬间。

540
00:24:23,160 --> 00:24:26,410
我们要扔掉安德鲁
在屏幕上的位置，

541
00:24:26,410 --> 00:24:28,170
这样看，你这样做。

542
00:24:28,170 --> 00:24:31,070
和使所有的这
是更明显的，

543
00:24:31,070 --> 00:24:33,490
这些都是我上亚马逊的卡。

544
00:24:33,490 --> 00:24:42,861
因此，他们已经随机
排序，我们要一次。

545
00:24:42,861 --> 00:24:44,610
而我们要
保持它真正的这个时候，

546
00:24:44,610 --> 00:24:47,820
所以我们要尽量压你
否则这将让乏味的

547
00:24:47,820 --> 00:24:48,460
快。

548
00:24:48,460 --> 00:24:53,860
如果你能进入52排序
通过一些手段在一起的元素，现在。

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> 再次，当我们观看这些
你们做什么，到底

551
00:25:07,180 --> 00:25:10,200
会产生一个明显的
结果，想想真

552
00:25:10,200 --> 00:25:12,962
他们是如何各尽其，
您可能如何描述它。

553
00:25:12,962 --> 00:25:15,045
因为再次，这些都是
所有过程，算法

554
00:25:15,045 --> 00:25:17,090
我们想当然地作为一个人。

555
00:25:17,090 --> 00:25:22,349
但是，你可能早就有了
直觉，很久以前，你甚至

556
00:25:22,349 --> 00:25:24,390
想过走
计算机科学类，你

557
00:25:24,390 --> 00:25:27,223
可能曾与直觉
要解决这样的问题。

558
00:25:27,223 --> 00:25:29,560
但是，一旦你认识到
模式，并开始

559
00:25:29,560 --> 00:25:32,407
形式化与步骤
您正在解决这些问题，

560
00:25:32,407 --> 00:25:35,490
你会发现，你能解决多少
更有趣和更复杂

561
00:25:35,490 --> 00:25:39,190
问题很快。

562
00:25:39,190 --> 00:25:42,351
因此，有人从观众，什么是
该算法中的至少一种元素

563
00:25:42,351 --> 00:25:43,350
他们使用的是在这里吗？

564
00:25:43,350 --> 00:25:44,275
>> 听众：[听不清]

565
00:25:44,275 --> 00:25:45,150
演讲嘉宾：那是什么？

566
00:25:45,150 --> 00:25:47,062
听众：通过诉讼。

567
00:25:47,062 --> 00:25:47,770
演讲嘉宾：通过诉讼。

568
00:25:47,770 --> 00:25:50,630
因此，首先他们是聚类
所有的钻石一起

569
00:25:50,630 --> 00:25:52,560
看来，所有的
心在一起看来，

570
00:25:52,560 --> 00:25:56,520
等等，不尊重
对于卡上的号码。

571
00:25:56,520 --> 00:26:00,900
现在，他们的出现，例如，
通过数量来对它们进行排序。

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
挺好。

574
00:26:08,910 --> 00:26:12,370
>> 好吧，那么什么会
是最后一步，然后在这里？

575
00:26:12,370 --> 00:26:16,950
一旦我们有四个排序的西服，有什么
做我们需要做的四桩

576
00:26:16,950 --> 00:26:20,059
为了实现一
整理平台，很简单？

577
00:26:20,059 --> 00:26:21,350
因此，我们需要再次合并。

578
00:26:21,350 --> 00:26:25,160
>> 所以这是一个有趣的想法，
再次，敢说，是非常直观的，甚至

579
00:26:25,160 --> 00:26:28,140
如果你可能从来没有掌掴
那样就可以了标签。

580
00:26:28,140 --> 00:26:31,900
除以这个根本概念
问题不是在一半此时，

581
00:26:31,900 --> 00:26:33,410
但至少到四件。

582
00:26:33,410 --> 00:26:36,810
解决相当多
从根本上相同的问题

583
00:26:36,810 --> 00:26:40,480
在彼此隔离，
然后合并的结果。

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
而且，优，做。

586
00:26:50,140 --> 00:26:52,140
好了，又大又圆
掌声中，如果我们能。

587
00:26:52,140 --> 00:26:56,480
>> [掌声]

588
00:26:56,480 --> 00:26:59,740
>> 演讲嘉宾：我不知道你会
做到这些，但在这里你去。

589
00:26:59,740 --> 00:27:01,690
太谢谢你了。

590
00:27:01,690 --> 00:27:04,660
因此，让我们来看看两分钟
八秒，

591
00:27:04,660 --> 00:27:07,490
如果你想挑战你的朋友。

592
00:27:07,490 --> 00:27:12,160
什么然后将要
从这样的带走

593
00:27:12,160 --> 00:27:13,830
我们可以利用更普遍？

594
00:27:13,830 --> 00:27:16,080
好了，回想起
这个数字阵列，

595
00:27:16,080 --> 00:27:19,060
现在回想起一些
伪代码，我们已经写在过去，

596
00:27:19,060 --> 00:27:22,080
这是伪代码
解决电话簿问题。

597
00:27:22,080 --> 00:27:25,150
由此伪í
列举一个更有条理的方式

598
00:27:25,150 --> 00:27:28,400
描述我是如何做到一个非常直观的
将所述电话的人的算法

599
00:27:28,400 --> 00:27:31,650
本书的一半，重复，重复，重复，
直到我发现有人像迈克·史密斯，

600
00:27:31,650 --> 00:27:33,790
如果他确实是在电话簿。

601
00:27:33,790 --> 00:27:37,610
>> 但是我种用什么，我会打电话
很迭代的方法在这里，

602
00:27:37,610 --> 00:27:42,160
特别通告第8行和第11行。

603
00:27:42,160 --> 00:27:46,750
这些都是一个迭代的证据
方法，一个循环的方法，

604
00:27:46,750 --> 00:27:49,040
因为这正是
在他们的行为引起。

605
00:27:49,040 --> 00:27:52,910
这些线路都表示去
三线，你可以种

606
00:27:52,910 --> 00:27:55,140
想在你的
心灵之眼作为一个循环。

607
00:27:55,140 --> 00:27:59,080
它告诉你去备份步骤
3，重复，一遍，又一遍，

608
00:27:59,080 --> 00:28:00,010
又一遍。

609
00:28:00,010 --> 00:28:04,410
>> 但是，如果我们利用的一个关键思想
在这里，我们没有最后一次，

610
00:28:04,410 --> 00:28:10,280
并简化线路8
第11行和他们的邻居

611
00:28:10,280 --> 00:28:12,840
像刚才这样，为黄色。

612
00:28:12,840 --> 00:28:16,480
它不能从根本上缩短
伪代码非常多，

613
00:28:16,480 --> 00:28:20,530
但它从根本上改变
我的算法的性质。

614
00:28:20,530 --> 00:28:24,220
就是我现在说
在步骤7中，在步骤10中，

615
00:28:24,220 --> 00:28:29,140
是寻找迈克
以完全相同的方式，

616
00:28:29,140 --> 00:28:31,580
但只在左
一半或右半部。

617
00:28:31,580 --> 00:28:33,420
>> 因此，换句话说，如果
我是从第一步开始，

618
00:28:33,420 --> 00:28:36,150
拿起电话本，开到中间
电话本，看名字，

619
00:28:36,150 --> 00:28:39,010
如果史密斯是其中
名字的，叫迈克，否则

620
00:28:39,010 --> 00:28:44,340
如果史密斯早在本书中，第七步
在本书的左半寻找迈克。

621
00:28:44,340 --> 00:28:47,130
但是那种感觉像
它让我挂了吧？

622
00:28:47,130 --> 00:28:49,240
在黄色的，是一种
指令，但我怎么

623
00:28:49,240 --> 00:28:51,870
搜索麦克左
一半的电话簿吗？

624
00:28:51,870 --> 00:28:54,210
哪里有
算法与我

625
00:28:54,210 --> 00:28:57,100
可以搜索一个像迈克·史密斯？

626
00:28:57,100 --> 00:28:58,980
那么，它的盯着我们的脸。

627
00:28:58,980 --> 00:29:03,090
我可以从字面上使用完全相同的
计划有效地往上走顶端

628
00:29:03,090 --> 00:29:06,490
一而再，再运行
同一行的代码。

629
00:29:06,490 --> 00:29:10,610
>> 因此，即使本应该感到
像一个有点周期性的定义

630
00:29:10,610 --> 00:29:13,480
在那里你回答别人的
仅通过排序问问题

631
00:29:13,480 --> 00:29:15,990
再次同样的问题，
就像为什么，为什么，为什么？

632
00:29:15,990 --> 00:29:21,580
现实的情况是，因为我们已经硬编码
一组特殊的线，第4步，

633
00:29:21,580 --> 00:29:25,320
其是，如果和步骤12，该
实际上是另外一个分支，

634
00:29:25,320 --> 00:29:30,120
因为我们有这些治标不治本，
该算法将终止，如果我们

635
00:29:30,120 --> 00:29:32,050
找到迈克，或者如果我们不这样做。

636
00:29:32,050 --> 00:29:36,810
但现在STEP 7和10，我们有
我们就这么叫递归算法。

637
00:29:36,810 --> 00:29:40,420
和递归确实是一个强大的理念
这是一个有点头脑的第一个弯，

638
00:29:40,420 --> 00:29:42,500
我们现在可以应用如下。

639
00:29:42,500 --> 00:29:46,600
>> 归并排序将是最后的那种
我们看一下，至少在形式上类。

640
00:29:46,600 --> 00:29:50,040
而且它是完全不同的
从这些过去三年，肯定

641
00:29:50,040 --> 00:29:52,140
过去四年，如果我们有bogosort。

642
00:29:52,140 --> 00:29:54,810
下面是伪代码合并排序。

643
00:29:54,810 --> 00:30:00,170
当n个元素的输入，因此给予
大小为n的阵列中，如果n小于2，

644
00:30:00,170 --> 00:30:01,040
返回。

645
00:30:01,040 --> 00:30:03,610
那么，为什么我有
理智首先检查？

646
00:30:03,610 --> 00:30:09,477
有什么含义，如果我交给你
一个数组，其长度n小于2？

647
00:30:09,477 --> 00:30:11,060
它已经排序，很明显，对吧？

648
00:30:11,060 --> 00:30:13,640
因为列表中任一具有
一种元素，它是平凡

649
00:30:13,640 --> 00:30:15,180
排序的，因为它是
唯一存在。

650
00:30:15,180 --> 00:30:18,138
或者说，它的大小为零，这意味着中
有天生什么来排序，所以

651
00:30:18,138 --> 00:30:18,720
它的排序。

652
00:30:18,720 --> 00:30:20,410
只是有没有什么不对劲的地方。

653
00:30:20,410 --> 00:30:22,310
这就是我们所谓的基本情况。

654
00:30:22,310 --> 00:30:24,440
>> 这是精神相似
以我们与麦克一样。

655
00:30:24,440 --> 00:30:26,023
如果小李的电话本，打电话给他。

656
00:30:26,023 --> 00:30:27,740
如果他不在那里，就放弃。

657
00:30:27,740 --> 00:30:31,240
这是一个所谓的基本情况，以确保
这个算法在一天结束时

658
00:30:31,240 --> 00:30:33,540
将停止在某些情况下。

659
00:30:33,540 --> 00:30:37,890
>> 但这里的信仰的飞跃，现在，否则，
排序的元素的左半边，

660
00:30:37,890 --> 00:30:39,740
然后进行排序的权利
一半的元素，

661
00:30:39,740 --> 00:30:41,189
然后合并排序的一半。

662
00:30:41,189 --> 00:30:43,230
而这里也正是感觉
像我们科平了。

663
00:30:43,230 --> 00:30:46,900
我问你排序
n个元素，而我

664
00:30:46,900 --> 00:30:50,712
他说，好了，不要它通过排序
左和排序的权利。

665
00:30:50,712 --> 00:30:52,420
但我嘴上说
其他的东西，这

666
00:30:52,420 --> 00:30:55,530
是看来关键主题
在直觉到目前为止，

667
00:30:55,530 --> 00:30:57,380
有合并的这个第三步骤。

668
00:30:57,380 --> 00:31:00,430
其中，即使它
似乎在精神上如此愚蠢，

669
00:31:00,430 --> 00:31:02,320
就像刚合并的东西
在一起，似乎

670
00:31:02,320 --> 00:31:05,380
为朝着一个关键步骤
两个问题，即重组

671
00:31:05,380 --> 00:31:07,330
一半最终被划分。

672
00:31:07,330 --> 00:31:12,090
>> 所以，归并排序，让我们做到这一点，如果你愿意
幽默的我，多了一个示范，

673
00:31:12,090 --> 00:31:14,730
只是让我们有一些
数字与合作。

674
00:31:14,730 --> 00:31:19,470
我可以换8压力
球八个人？

675
00:31:19,470 --> 00:31:29,320
好吧，你怎么样3，你们四个
在本节中，五，六，让我们

676
00:31:29,320 --> 00:31:30,720
做7，8，上来吧。

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
好吧，是的确定。

679
00:31:36,520 --> 00:31:38,640
减去8，我们走了，再加上1。

680
00:31:38,640 --> 00:31:39,150
优秀的。

681
00:31:39,150 --> 00:31:42,000
没事上来吧，让我们
赶紧给你的数字。

682
00:31:42,000 --> 00:31:50,800
排名第二，第三位，排名第四，
第五，六，七，八名。

683
00:31:50,800 --> 00:31:52,140
我没有做过8这个时候。

684
00:31:52,140 --> 00:31:56,390
>> 好了，如果你可以去进取，
让我们梳理了原来的顺序

685
00:31:56,390 --> 00:31:59,810
我们昨天看了这
这样，如果你不介意的话。

686
00:31:59,810 --> 00:32:03,620
让我们做吧的桌子前。

687
00:32:03,620 --> 00:32:06,510
好吧，那么归并排序。

688
00:32:06,510 --> 00:32:08,820
这是到哪里去
获得有趣的一种，

689
00:32:08,820 --> 00:32:12,800
因为我似乎给自己
这么多的信息较少今天。

690
00:32:12,800 --> 00:32:15,149
>> 所以归并排序首先
对n个元素的输入，

691
00:32:15,149 --> 00:32:18,440
这显然​​不是少了两个比，它的
8，让我有更多的工作要做。

692
00:32:18,440 --> 00:32:21,140
所以，现在我们精神上的类
现在在else分支，

693
00:32:21,140 --> 00:32:22,540
这意味着三个步骤。

694
00:32:22,540 --> 00:32:25,017
首先，我要排序
元件的左半部。

695
00:32:25,017 --> 00:32:26,350
那么，如何去这样做？

696
00:32:26,350 --> 00:32:28,950
好吧，我要种
精神上将列表在这里，

697
00:32:28,950 --> 00:32:30,700
您不必
身体动了，我

698
00:32:30,700 --> 00:32:33,180
打算只把重点放在
这里的元素的左半边。

699
00:32:33,180 --> 00:32:36,770
那么，如何去整理
现在大小4名单？

700
00:32:36,770 --> 00:32:38,730
什么是我的算法？

701
00:32:38,730 --> 00:32:42,580
首先我检查为n比少了两个，不，
所以我继续在else块了。

702
00:32:42,580 --> 00:32:43,900
排序左前卫的元素。

703
00:32:43,900 --> 00:32:45,608
>> 所以，现在再次，精神，
而这正是

704
00:32:45,608 --> 00:32:49,550
你必须累积了大量的
精神的历史，如果你愿意。

705
00:32:49,550 --> 00:32:51,940
现在我左边的分类
一半的左半部。

706
00:32:51,940 --> 00:32:57,000
好了，所以现在我把我相同的合并
排序算法，是n小于2？

707
00:32:57,000 --> 00:33:00,590
不，它是两个，所以我要排序
左半边和右一半。

708
00:33:00,590 --> 00:33:02,042
所以在这里，我们走了，排序的左半部。

709
00:33:02,042 --> 00:33:03,750
为什么不干脆
走了一步。

710
00:33:03,750 --> 00:33:04,415
你叫什么名字？

711
00:33:04,415 --> 00:33:04,860
>> 听众：达伦。

712
00:33:04,860 --> 00:33:05,260
>> 音箱：丹。

713
00:33:05,260 --> 00:33:06,040
丹上前。

714
00:33:06,040 --> 00:33:06,748
>> 听众：达伦。

715
00:33:06,748 --> 00:33:09,000
演讲嘉宾：达伦，完成。

716
00:33:09,000 --> 00:33:10,090
你说达伦还是丹？

717
00:33:10,090 --> 00:33:10,550
>> 听众：达伦。

718
00:33:10,550 --> 00:33:11,216
>> 演讲嘉宾：达伦。

719
00:33:11,216 --> 00:33:14,422
好吧，达伦已加强
向前和他现在排序。

720
00:33:14,422 --> 00:33:16,130
这几乎是一个
空洞的说法，对吗？

721
00:33:16,130 --> 00:33:18,862
我岂不真的似乎要实现
任何事情，但是让我们继续。

722
00:33:18,862 --> 00:33:20,820
现在让我排序的权利
一半的元素。

723
00:33:20,820 --> 00:33:21,200
你叫什么名字？

724
00:33:21,200 --> 00:33:21,690
>> 听众：卢克。

725
00:33:21,690 --> 00:33:22,273
>> 演讲嘉宾：卢克。

726
00:33:22,273 --> 00:33:23,400
来吧，向前一步。

727
00:33:23,400 --> 00:33:25,640
完成后，我已经整理卢克。

728
00:33:25,640 --> 00:33:28,570
左半现在排序和
右半现在排序，

729
00:33:28,570 --> 00:33:30,770
但同样的，这里有一个关键的步骤。

730
00:33:30,770 --> 00:33:32,940
什么才是我旁边需要做什么？

731
00:33:32,940 --> 00:33:33,941
合并排序的一半。

732
00:33:33,941 --> 00:33:36,648
现在我们只是有
大家来回这种方式，

733
00:33:36,648 --> 00:33:38,620
因为那种我需要的
一些暂存空间。

734
00:33:38,620 --> 00:33:40,411
这几乎就像这些
家伙都在桌子上，

735
00:33:40,411 --> 00:33:42,460
我需要一些空间
移动至周围。

736
00:33:42,460 --> 00:33:44,170
所以，我要合并
你们看

737
00:33:44,170 --> 00:33:45,960
在左半侧和右半侧。

738
00:33:45,960 --> 00:33:48,740
又是谁显然是第一位的，
左半或右半？

739
00:33:48,740 --> 00:33:52,710
所以，正确的上半年，让我们在移动路
这里达伦的原始位置。

740
00:33:52,710 --> 00:33:57,640
现在合并他们的左半部分，
达伦是怎么回事向右移动那里。

741
00:33:57,640 --> 00:33:59,750
>> 所以感觉差不多
冒泡排序的效果，

742
00:33:59,750 --> 00:34:02,482
但我的基本算法，
非常不同，这一次。

743
00:34:02,482 --> 00:34:04,815
但现在也正是事情变得
有点讨厌，因为你

744
00:34:04,815 --> 00:34:06,810
要倒带精神
在哪里我离开了。

745
00:34:06,810 --> 00:34:09,893
我刚刚合并排序的一半，
这意味着我在我的算法是在哪里呢？

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
我的右半边进行排序，对不对？

748
00:34:13,770 --> 00:34:15,910
>> 如果你后退，从字面上
在视频中，您将

749
00:34:15,910 --> 00:34:18,339
看到我们到了这
点卢克和达伦的

750
00:34:18,339 --> 00:34:21,370
由左排序
一半的左半部。

751
00:34:21,370 --> 00:34:23,430
然后，我们的合并
排序一半，这

752
00:34:23,430 --> 00:34:27,941
装置的下一步骤是分类的
左半部右半部。

753
00:34:27,941 --> 00:34:29,649
好吧，让我们
更迅速地做到这一点。

754
00:34:29,649 --> 00:34:33,282
好吧，六，我会要求
现在你的排序，加油前进。

755
00:34:33,282 --> 00:34:33,990
你叫什么名字？

756
00:34:33,990 --> 00:34:34,589
>> 听众：阿德里亚诺。

757
00:34:34,589 --> 00:34:35,200
>> 演讲嘉宾：阿德里亚诺。

758
00:34:35,200 --> 00:34:36,010
阿德里亚诺现在排序。

759
00:34:36,010 --> 00:34:36,450
而你叫什么名字？

760
00:34:36,450 --> 00:34:37,080
>> 听众：亚历克斯。

761
00:34:37,080 --> 00:34:38,379
>> 演讲嘉宾：亚历克斯现在排序。

762
00:34:38,379 --> 00:34:40,750
左前卫，右前卫，
什么是最后一步？

763
00:34:40,750 --> 00:34:41,250
合并。

764
00:34:41,250 --> 00:34:44,310
很琐碎，所以我
要在六个月合并，

765
00:34:44,310 --> 00:34:46,930
退一步，
8，退一步。

766
00:34:46,930 --> 00:34:49,530
现在发现这是
一个有用的外卖，有什么

767
00:34:49,530 --> 00:34:53,930
现在真正对的左半
列表中，不管我们怎么开始的？

768
00:34:53,930 --> 00:34:55,090
它的排序。

769
00:34:55,090 --> 00:34:57,750
>> 现在，它不是在整理
物联网的大计划，

770
00:34:57,750 --> 00:35:00,250
但它是独立地排序
的另一半。

771
00:35:00,250 --> 00:35:04,100
现在哪一步我是在如果我坚持
复卷怎么回事开始？

772
00:35:04,100 --> 00:35:05,680
现在我要右半排序。

773
00:35:05,680 --> 00:35:07,630
所以，现在我们回来的路上，在
故事的开始，

774
00:35:07,630 --> 00:35:08,921
并让我们这样做更为迅速。

775
00:35:08,921 --> 00:35:11,320
所以，我要排序
整个列表的右半边。

776
00:35:11,320 --> 00:35:13,060
什么是下一步？

777
00:35:13,060 --> 00:35:15,840
排序的右半​​边的左一半。

778
00:35:15,840 --> 00:35:18,715
排序的左半
右半部分的左半部。

779
00:35:18,715 --> 00:35:19,590
而你叫什么名字？

780
00:35:19,590 --> 00:35:20,230
>> 听众：奥马尔。

781
00:35:20,230 --> 00:35:21,970
>> 演讲嘉宾：奥马尔，向前一步，完成。

782
00:35:21,970 --> 00:35:22,860
左半部分是排序。

783
00:35:22,860 --> 00:35:23,330
而你叫什么名字？

784
00:35:23,330 --> 00:35:23,820
>> 听众：克里斯。

785
00:35:23,820 --> 00:35:25,620
>> 演讲嘉宾：克里斯，退一步
未来，你现在来分类的。

786
00:35:25,620 --> 00:35:27,010
什么是现在的关键一步？

787
00:35:27,010 --> 00:35:27,510
合并。

788
00:35:27,510 --> 00:35:30,509
所以，一个人要融入地方
在这里，如果你能退后一步，

789
00:35:30,509 --> 00:35:32,930
三是要
退一步，合并。

790
00:35:32,930 --> 00:35:38,080
这样的左半
右半部，现已排序。

791
00:35:38,080 --> 00:35:41,747
坦率地说，这个算法感觉就像我们
这是在浪费这样的时间比以前，

792
00:35:41,747 --> 00:35:44,830
但如果我们在实时这样做，我们将
看到外卖成为怎样的人。

793
00:35:44,830 --> 00:35:47,970
现在我在这里，对不对
一半的右边一半的，

794
00:35:47,970 --> 00:35:50,170
让我继续前进，排序的左半部。

795
00:35:50,170 --> 00:35:51,482
向前迈出一步，你叫什么名字？

796
00:35:51,482 --> 00:35:52,190
听众：拉姆齐。

797
00:35:52,190 --> 00:35:53,210
演讲嘉宾：拉姆齐现在排序。

798
00:35:53,210 --> 00:35:53,570
你叫什么名字？

799
00:35:53,570 --> 00:35:54,200
>> 听众：码头。

800
00:35:54,200 --> 00:35:57,033
>> 演讲嘉宾：滨海现在排序，
好吧，如果你走了一步。

801
00:35:57,033 --> 00:36:00,690
这里关键的一步，现在被合并，我
打算从我的两个列表采摘，

802
00:36:00,690 --> 00:36:01,720
左，右。

803
00:36:01,720 --> 00:36:05,150
五是要放在第一位，
七是要到明年。

804
00:36:05,150 --> 00:36:06,410
再次，这是故意的。

805
00:36:06,410 --> 00:36:08,535
他们正在做的事实
步骤前进和后退

806
00:36:08,535 --> 00:36:12,997
是代表我们不能
这样做算法的地方，很容易

807
00:36:12,997 --> 00:36:15,830
如冒泡排序和选择排序，
和插入排序，我们只是

808
00:36:15,830 --> 00:36:16,960
不停交换的人。

809
00:36:16,960 --> 00:36:19,940
我真的需要一个排序
草稿纸在其中

810
00:36:19,940 --> 00:36:21,827
把这些人
而我的融合，

811
00:36:21,827 --> 00:36:23,410
然后我可以把它们放回原处。

812
00:36:23,410 --> 00:36:27,260
这就是关键，因为我使用的是
新的资源，空间，而不仅仅是时间。

813
00:36:27,260 --> 00:36:28,270
>> OK，这是惊人的。

814
00:36:28,270 --> 00:36:32,050
左半部分是排序，右半部分是
排序的，现在的关键合成步骤。

815
00:36:32,050 --> 00:36:33,450
我怎么合并呢？

816
00:36:33,450 --> 00:36:35,470
所以，如果你按照我
左手和右手

817
00:36:35,470 --> 00:36:38,930
我要指出我的左手
在左前卫，我的右手

818
00:36:38,930 --> 00:36:42,680
在右前卫的，现在我要
决定一步步谁在合并。

819
00:36:42,680 --> 00:36:44,650
谁显然是第一位的？

820
00:36:44,650 --> 00:36:45,150
第一。

821
00:36:45,150 --> 00:36:47,327
所以来这边，
这里是我们的便笺。

822
00:36:47,327 --> 00:36:49,910
所以，现在排名第一，并通知
我会尽我的右手，

823
00:36:49,910 --> 00:36:54,152
我打算将我的右手1
跳过来点排名第三，

824
00:36:54,152 --> 00:36:55,860
现在我要
同样的决定。

825
00:36:55,860 --> 00:36:58,387
而实际上站在正确的
卢克在这里，如果你能面前，

826
00:36:58,387 --> 00:36:59,720
因为这是我们的便笺。

827
00:36:59,720 --> 00:37:00,610
那么，谁随之而来的？

828
00:37:00,610 --> 00:37:05,000
我们有卢克与排名第二
或者克里斯与排名第三。

829
00:37:05,000 --> 00:37:07,460
显然卢克，数
2，让你来这里。

830
00:37:07,460 --> 00:37:11,270
>> 但是，我的左手现在是要
递增为指向达伦，

831
00:37:11,270 --> 00:37:15,160
而这里的关键拿走了
合并，我将继续这样做，

832
00:37:15,160 --> 00:37:17,340
很明显，如果你有种
遵循的逻辑。

833
00:37:17,340 --> 00:37:19,670
但我的手都从未
要往回走，

834
00:37:19,670 --> 00:37:23,861
这意味着我永远只能移动到
左边有我的合并过程，

835
00:37:23,861 --> 00:37:26,360
那将是关键
我们的分析在短短的一瞬间。

836
00:37:26,360 --> 00:37:27,859
>> 所以，现在让我们迅速完成这件事。

837
00:37:27,859 --> 00:37:31,650
所以三随之而来的，
然后4随之而来的，

838
00:37:31,650 --> 00:37:38,750
现在5随之而来的，则6，
七，最后8。

839
00:37:38,750 --> 00:37:42,960
感觉就像是最慢的算法
然而，但如果我们真的

840
00:37:42,960 --> 00:37:45,510
在相同的排序运行
时钟速度的，所以要

841
00:37:45,510 --> 00:37:48,106
说，具有相同的
滴答作响的时钟和以前一样。

842
00:37:48,106 --> 00:37:48,605
为什么呢？

843
00:37:48,605 --> 00:37:51,100
好吧，让我们来
看的最终结果。

844
00:37:51,100 --> 00:37:56,990
>> 让我们回到了这里，让我
拉了一个直观演示

845
00:37:56,990 --> 00:37:59,030
什么，我们只是做了。

846
00:37:59,030 --> 00:38:06,110
放大在这里，在这个
在此页面，告诉火狐

847
00:38:06,110 --> 00:38:08,200
我们要排队
在此框，让我们

848
00:38:08,200 --> 00:38:11,260
说冒泡排序，与
我们现在非常熟悉，

849
00:38:11,260 --> 00:38:14,130
选择排序，这是另一种
相当简单的，

850
00:38:14,130 --> 00:38:18,250
现在今天的归并排序，其中
将是我们的高潮结局。

851
00:38:18,250 --> 00:38:21,530
花了这么多时间越长的原因
这里有人类和我口头上的，

852
00:38:21,530 --> 00:38:23,480
很明显，我解释每一步。

853
00:38:23,480 --> 00:38:26,920
但如果你只需要执行这一点，很多
像我们做冒泡排序和选择

854
00:38:26,920 --> 00:38:30,890
排序不仅在视觉上，观看
到底有多少更有效

855
00:38:30,890 --> 00:38:33,330
这个杠杆化
分裂和征服

856
00:38:33,330 --> 00:38:39,150
可以在应用到数据集的
即使没有大小八，但即使多了，

857
00:38:39,150 --> 00:38:39,970
要大得多。

858
00:38:39,970 --> 00:38:44,585
我给你通过归并排序，方
方用这些算法。

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
这是会得到痛苦
很快，并且结束

861
00:38:58,530 --> 00:39:00,890
没有特别的高潮，
他们刚刚结束了排序。

862
00:39:00,890 --> 00:39:05,280
但关键带走的是
看快多少排序合并

863
00:39:05,280 --> 00:39:08,110
是的，除非你觉得我
只是那种玩弄你。

864
00:39:08,110 --> 00:39:13,100
如果我们这样做了，最后一次，
让我们重新加载此，让我们回去

865
00:39:13,100 --> 00:39:14,960
选择冒泡排序，
而只是踢，

866
00:39:14,960 --> 00:39:17,330
让我们来选择插入
排序，只是为了好措施。

867
00:39:17,330 --> 00:39:20,020
而这一次又一次，让我们
选择合并排序，让我们

868
00:39:20,020 --> 00:39:21,595
实际上并排运行这些侧。

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> 它不是，其实是侥幸。

871
00:39:26,930 --> 00:39:31,140
我已经做了有效的是我
分我输入了一半，同样，

872
00:39:31,140 --> 00:39:32,240
又一次，又一次。

873
00:39:32,240 --> 00:39:35,590
而且也只有这么多的时候，你可以
将您的输入成两半，左

874
00:39:35,590 --> 00:39:36,240
右。

875
00:39:36,240 --> 00:39:39,425
那是什么，我们总是看到公式
描述该师在半

876
00:39:39,425 --> 00:39:41,050
一次，又一次，又一次，又一次？

877
00:39:41,050 --> 00:39:41,890
>> 听众：日志N。

878
00:39:41,890 --> 00:39:42,760
>> 演讲嘉宾：日志N。

879
00:39:42,760 --> 00:39:46,300
但还有另一个关键的一步，
这种算法是不记录n步。

880
00:39:46,300 --> 00:39:48,992
如果它仅记录n步，
我们将在同样的问题

881
00:39:48,992 --> 00:39:51,200
如之前在这里我们不能
确保一切的排序。

882
00:39:51,200 --> 00:39:54,480
你必须微创看看n个元素
可以肯定的n个元素进行排序，

883
00:39:54,480 --> 00:39:55,950
否则就是信仰的飞跃。

884
00:39:55,950 --> 00:39:59,810
>> 所以它的最低限度日志n步，但
那么这个合并的关键一步

885
00:39:59,810 --> 00:40:04,370
在这里我合并了我的左半边，右
半走过的阶段？

886
00:40:04,370 --> 00:40:06,980
多少个步骤是合并？

887
00:40:06,980 --> 00:40:10,150
这是N，但我不只是
合并的最后时间。

888
00:40:10,150 --> 00:40:15,089
在每个这些嵌套调用，每个
这些嵌套的合并，我还是整理。

889
00:40:15,089 --> 00:40:18,380
我将这这两个家伙，那么这两个
男人，那么这两个家伙，等等。

890
00:40:18,380 --> 00:40:19,955
>> 所以，我没有再合并，再。

891
00:40:19,955 --> 00:40:20,580
多少次？

892
00:40:20,580 --> 00:40:23,510
所以每次我分了
列表中的一半，我做了合并。

893
00:40:23,510 --> 00:40:25,460
将列表中的一半，做了合并。

894
00:40:25,460 --> 00:40:28,570
因此，如果分割清单
可以做日志的n倍，

895
00:40:28,570 --> 00:40:33,880
和合并，最终占据N
步骤，可能是什么，现在的上

896
00:40:33,880 --> 00:40:37,000
结合在跑步
我们的算法的时间呢？

897
00:40:37,000 --> 00:40:37,980
Ñ​​日志N。

898
00:40:37,980 --> 00:40:40,560
>> 事实上，这就是
我们在这里实现。

899
00:40:40,560 --> 00:40:44,650
所以，你看到的时候视觉上的感觉
这三样东西并行走线

900
00:40:44,650 --> 00:40:47,930
为n的平方与n的
平方与n的日志ñ。

901
00:40:47,930 --> 00:40:51,010
这从根本上，我们会看到，
不仅是现在，而且在将来，

902
00:40:51,010 --> 00:40:52,760
是非常非常快。

903
00:40:52,760 --> 00:40:56,010
掌声鼓励了这些家伙，
我会奖励他们压力球。

904
00:40:56,010 --> 00:41:00,260
让我们今天在这里宣布休会，并
我们会看到你在星期一。

905
00:41:00,260 --> 00:41:02,255