1
00:00:00,000 --> 00:00:00,990

2
00:00:00,990 --> 00:00:02,970
>> [音乐播放]

3
00:00:02,970 --> 00:00:10,400

4
00:00:10,400 --> 00:00:12,550
>> DAVID J.马兰：这是CS50。

5
00:00:12,550 --> 00:00:14,612
这是三周的开始。

6
00:00:14,612 --> 00:00:16,820
因此，我们有很多令人兴奋的
事到如今覆盖。

7
00:00:16,820 --> 00:00:20,160
大量的机会
志愿者在舞台上。

8
00:00:20,160 --> 00:00:22,780
而最终，今天是
不是在所有的代码。

9
00:00:22,780 --> 00:00:24,820
但是，它是关于思想，
它是关于算法，

10
00:00:24,820 --> 00:00:28,420
实际上带回一些
从零一周中吸取的教训，

11
00:00:28,420 --> 00:00:31,910
其中，召回，我们
推出这个畸形。

12
00:00:31,910 --> 00:00:33,880
而借款的启示
同时，向启动

13
00:00:33,880 --> 00:00:36,879
为了解决日益复杂的
问题的算法。

14
00:00:36,879 --> 00:00:38,420
但首先，一对夫妇的公告。

15
00:00:38,420 --> 00:00:42,020
所以人们，如果你想加盟
CS50的工作人员和同学在午餐

16
00:00:42,020 --> 00:00:44,670
本周五，在这里和在
剑桥，并在纽黑文，

17
00:00:44,670 --> 00:00:48,060
请访问过程中的
网站，在那里一个URL可以找到。

18
00:00:48,060 --> 00:00:50,390
讲课周三将
不能在这里桑德斯。

19
00:00:50,390 --> 00:00:53,610
这将是只在网上，所以
调在CS50的网站，

20
00:00:53,610 --> 00:00:55,850
这里是否在剑桥
或纽黑文也。

21
00:00:55,850 --> 00:00:58,110
>> 然后，问题设置两个
已经在你的手中。

22
00:00:58,110 --> 00:01:03,067
如果你还没有在还没有跌，让我
提供了措辞强烈的建议

23
00:01:03,067 --> 00:01:05,150
如此，尤其是现在，作为
问题设置提前，

24
00:01:05,150 --> 00:01:08,669
你真的想从现在开始，如果不
涉足了一下周末或之前

25
00:01:08,669 --> 00:01:10,710
当他们第一次外出
周五，因为你

26
00:01:10,710 --> 00:01:14,380
发现他们不一定
获得每更长或更有挑战性

27
00:01:14,380 --> 00:01:14,950
东南。

28
00:01:14,950 --> 00:01:17,575
我想你会发现，在
一般情况下，他们往往需要大约

29
00:01:17,575 --> 00:01:18,892
周围的时间量相同。

30
00:01:18,892 --> 00:01:20,850
但可以肯定的依赖
在学生，并且它

31
00:01:20,850 --> 00:01:22,880
取决于心态
与你接近它。

32
00:01:22,880 --> 00:01:24,910
但无一例外，你会
要对一些墙壁跑起来，

33
00:01:24,910 --> 00:01:26,350
而你会打
一些bug，并且你只是

34
00:01:26,350 --> 00:01:27,950
不打算要能够
克服它在某个时候。

35
00:01:27,950 --> 00:01:31,380
而且它是非常有价值的，能够
一步之遥，回来的第二天，

36
00:01:31,380 --> 00:01:35,286
去办公时间，后在CS50讨论
或类似的，真正得到畅通。

37
00:01:35,286 --> 00:01:36,160
所以记住这一点。

38
00:01:36,160 --> 00:01:40,830
最早开始尽可能
就是你能做的最好的事情。

39
00:01:40,830 --> 00:01:44,160
因此，这里是我们开始的地方
类，过零一周。

40
00:01:44,160 --> 00:01:47,441
而且我们可以得到一个志愿者
在这里帮我找话筒？

41
00:01:47,441 --> 00:01:47,940
行。

42
00:01:47,940 --> 00:01:48,900
站立起来了。

43
00:01:48,900 --> 00:01:50,080
上来吧。

44
00:01:50,080 --> 00:01:53,707
猜猜这是怎么回事工作。

45
00:01:53,707 --> 00:01:54,415
你叫什么名字？

46
00:01:54,415 --> 00:01:55,570
ALAN埃斯特拉达：阿兰·埃斯特拉达。

47
00:01:55,570 --> 00:01:56,778
DAVID J.马兰：阿兰·埃斯特拉达。

48
00:01:56,778 --> 00:01:57,910
上来吧。

49
00:01:57,910 --> 00:01:58,619
很高兴认识你。

50
00:01:58,619 --> 00:01:59,910
ALAN埃斯特拉达：很高兴见到你。

51
00:01:59,910 --> 00:02:02,772
DAVID J.马兰：你在这里
我们当然在零一周。

52
00:02:02,772 --> 00:02:03,028
ALAN埃斯特拉达：我是。

53
00:02:03,028 --> 00:02:03,160
我曾是。

54
00:02:03,160 --> 00:02:05,868
>> DAVID J.马兰：所以你能不能去
进取，为我们找到迈克·史密斯，

55
00:02:05,868 --> 00:02:08,639
一样快，您可以吗？

56
00:02:08,639 --> 00:02:10,639
一样快，您可以。

57
00:02:10,639 --> 00:02:13,756
从字面上撕裂问题
在上半年，因为你需要。

58
00:02:13,756 --> 00:02:15,130
>> ALAN埃斯特拉达：嗯。

59
00:02:15,130 --> 00:02:17,380
DAVID J.马兰：从字面上看
撕裂在一半的问题。

60
00:02:17,380 --> 00:02:20,210

61
00:02:20,210 --> 00:02:22,083
>> ALAN埃斯特拉达：哦。

62
00:02:22,083 --> 00:02:22,583
毫米。

63
00:02:22,583 --> 00:02:23,300
挺好。

64
00:02:23,300 --> 00:02:23,700
>> DAVID J.马兰：OK。

65
00:02:23,700 --> 00:02:24,200
好。

66
00:02:24,200 --> 00:02:24,701
谢谢。

67
00:02:24,701 --> 00:02:25,700
ALAN埃斯特拉达：非常好。

68
00:02:25,700 --> 00:02:26,210
行。

69
00:02:26,210 --> 00:02:27,610
>> DAVID J.马兰：所以现在，
你又缩减

70
00:02:27,610 --> 00:02:29,320
该问题的一半大小。

71
00:02:29,320 --> 00:02:31,267
现在，我们到了四分之一。

72
00:02:31,267 --> 00:02:33,475
你是否关注
我们保持哪边？

73
00:02:33,475 --> 00:02:34,405
>> [笑气]

74
00:02:34,405 --> 00:02:35,970
>> ALAN ESTRADA：是的，我think--

75
00:02:35,970 --> 00:02:37,594
>> DAVID J.马兰：什么部分是我们的？

76
00:02:37,594 --> 00:02:39,150
ALAN ESTRADA：消音器，所以。

77
00:02:39,150 --> 00:02:39,941
>> DAVID J.马兰：OK。

78
00:02:39,941 --> 00:02:42,810
不过，迈克·史密斯是怎么回事
是消音器后。

79
00:02:42,810 --> 00:02:44,130
So--

80
00:02:44,130 --> 00:02:48,180
>> [笑气]

81
00:02:48,180 --> 00:02:48,742
>> 好吧。

82
00:02:48,742 --> 00:02:50,200
ALAN埃斯特拉达：我们在哪里找？

83
00:02:50,200 --> 00:02:52,049
DAVID J.马兰：迈克·史密斯。

84
00:02:52,049 --> 00:02:53,090
ALAN埃斯特拉达：迈克·史密斯。

85
00:02:53,090 --> 00:02:54,760
DAVID J.马兰：现在，我们在手术。

86
00:02:54,760 --> 00:02:57,840
现在，医生。

87
00:02:57,840 --> 00:02:58,340
Now--

88
00:02:58,340 --> 00:02:59,856
>> ALAN埃斯特拉达：Let's-让我们用实际。

89
00:02:59,856 --> 00:03:00,370
皇马。

90
00:03:00,370 --> 00:03:00,970
>> DAVID J.马兰：真。

91
00:03:00,970 --> 00:03:01,470
行。

92
00:03:01,470 --> 00:03:03,700
如果你需要真正的。

93
00:03:03,700 --> 00:03:05,250
现在，它的方法是迈克·史密斯？

94
00:03:05,250 --> 00:03:06,250
>> ALAN埃斯特拉达：这种方式。

95
00:03:06,250 --> 00:03:07,333
>> DAVID J.马兰：哪条路？

96
00:03:07,333 --> 00:03:08,240
ALAN埃斯特拉达：等待。

97
00:03:08,240 --> 00:03:08,790
中号is--吧？

98
00:03:08,790 --> 00:03:09,110
我们开始with--

99
00:03:09,110 --> 00:03:10,090
>> DAVID J.马兰：是的。

100
00:03:10,090 --> 00:03:10,650
他们离开了。

101
00:03:10,650 --> 00:03:11,430
你的权利。

102
00:03:11,430 --> 00:03:11,710
>> ALAN埃斯特拉达：是的。

103
00:03:11,710 --> 00:03:13,126
>> DAVID J.马兰：所以迈克在这里。

104
00:03:13,126 --> 00:03:13,990
ALAN埃斯特拉达：什么？

105
00:03:13,990 --> 00:03:14,665
>> [笑气]

106
00:03:14,665 --> 00:03:17,365

107
00:03:17,365 --> 00:03:18,330
>> 坏的榜样，伙计们。

108
00:03:18,330 --> 00:03:18,830
抱歉。

109
00:03:18,830 --> 00:03:21,610
DAVID J.马兰：这将教
你跳出你的椅子。

110
00:03:21,610 --> 00:03:22,318
>> ALAN埃斯特拉达：哦。

111
00:03:22,318 --> 00:03:22,890
呵呵。

112
00:03:22,890 --> 00:03:23,390
我接到你了。

113
00:03:23,390 --> 00:03:24,670
我接到你了。

114
00:03:24,670 --> 00:03:25,170
呵呵。

115
00:03:25,170 --> 00:03:25,669
呵呵。

116
00:03:25,669 --> 00:03:26,812
这is--好吧，我给你。

117
00:03:26,812 --> 00:03:27,520
史密斯就在这里？

118
00:03:27,520 --> 00:03:28,894
>> DAVID J.马兰：史密斯，谢谢。

119
00:03:28,894 --> 00:03:30,535
所以我会继续找了史密斯？

120
00:03:30,535 --> 00:03:30,790
>> ALAN ESTRADA：哦，是的。

121
00:03:30,790 --> 00:03:31,340
不不不。

122
00:03:31,340 --> 00:03:31,600
不好了。

123
00:03:31,600 --> 00:03:31,940
这是我的。

124
00:03:31,940 --> 00:03:32,580
>> DAVID J.马兰：哦，你得到了史密斯。

125
00:03:32,580 --> 00:03:33,415
行。

126
00:03:33,415 --> 00:03:34,040
>> ALAN ESTRADA：是的，我
得到了史密斯就在这里。

127
00:03:34,040 --> 00:03:34,700
对不起，伙计们。

128
00:03:34,700 --> 00:03:35,860
我想Michael--我们
在寻找迈克尔。

129
00:03:35,860 --> 00:03:36,550
抱歉。

130
00:03:36,550 --> 00:03:37,550
>> DAVID J.马兰：这是确定的。

131
00:03:37,550 --> 00:03:39,950
好了，现在我们
到帕奇尼和儿子。

132
00:03:39,950 --> 00:03:41,242
>> ALAN埃斯特拉达：帕奇尼和儿子。

133
00:03:41,242 --> 00:03:43,158
DAVID J.马兰：只有你
和我在这一点。

134
00:03:43,158 --> 00:03:44,050
行。

135
00:03:44,050 --> 00:03:45,130
找到我们迈克·史密斯。

136
00:03:45,130 --> 00:03:45,830
史密斯。

137
00:03:45,830 --> 00:03:46,310
>> ALAN埃斯特拉达：史密斯。

138
00:03:46,310 --> 00:03:46,750
>> DAVID J.马兰：史密斯。

139
00:03:46,750 --> 00:03:47,728
我们在研发的垃圾。

140
00:03:47,728 --> 00:03:48,644
ALAN埃斯特拉达：垃圾。

141
00:03:48,644 --> 00:03:50,096
呵呵。

142
00:03:50,096 --> 00:03:52,480
这将需要一段时间。

143
00:03:52,480 --> 00:03:54,340
>> [笑气]

144
00:03:54,340 --> 00:03:55,804

145
00:03:55,804 --> 00:03:56,720
DAVID J.马兰：鞋。

146
00:03:56,720 --> 00:03:58,080
我们在鞋。

147
00:03:58,080 --> 00:04:00,210
>> ALAN埃斯特拉达：现在，我们gonna--

148
00:04:00,210 --> 00:04:01,105
>> DAVID J.马兰：好的。

149
00:04:01,105 --> 00:04:01,980
ALAN埃斯特拉达：Which--

150
00:04:01,980 --> 00:04:03,620
[笑气]

151
00:04:03,620 --> 00:04:05,440
哦，这是伟大的。

152
00:04:05,440 --> 00:04:06,910
[笑气]

153
00:04:06,910 --> 00:04:08,380

154
00:04:08,380 --> 00:04:09,390
>> DAVID J.马兰：这是确定的。

155
00:04:09,390 --> 00:04:11,365
>> ALAN ESTRADA：哦，这是件好事。

156
00:04:11,365 --> 00:04:14,425
我不认为我会
有在这之后PSAT哥们。

157
00:04:14,425 --> 00:04:15,300
DAVID J.马兰：好。

158
00:04:15,300 --> 00:04:16,078
里斯本竞技。

159
00:04:16,078 --> 00:04:17,036
ALAN埃斯特拉达：里斯本竞技。

160
00:04:17,036 --> 00:04:18,668
嗯，L，M，N，O，P。

161
00:04:18,668 --> 00:04:19,459
DAVID J.马兰：OK。

162
00:04:19,459 --> 00:04:21,600
因此，让我们颠覆这个一半。

163
00:04:21,600 --> 00:04:22,270
没关系。

164
00:04:22,270 --> 00:04:25,606
这结束反正不好，因为迈克
史密斯将不会在黄页。

165
00:04:25,606 --> 00:04:26,430
>> ALAN埃斯特拉达：仙。

166
00:04:26,430 --> 00:04:27,140
>> DAVID J.马兰：没有，这是确定的。

167
00:04:27,140 --> 00:04:28,930
但是，让我们假装
他的这个页面上。

168
00:04:28,930 --> 00:04:33,260
所以，现在，你已经削弱的问题分解
到一个页面上，我们发现了麦克·史密斯。

169
00:04:33,260 --> 00:04:35,180
>> [欢呼]

170
00:04:35,180 --> 00:04:35,757

171
00:04:35,757 --> 00:04:36,340
好的谢谢。

172
00:04:36,340 --> 00:04:40,700

173
00:04:40,700 --> 00:04:41,200
行。

174
00:04:41,200 --> 00:04:43,646
这是非凡的。

175
00:04:43,646 --> 00:04:45,954
但它仍然较快
不是线性搜索，

176
00:04:45,954 --> 00:04:47,870
其中，我们开始在
开始的书，

177
00:04:47,870 --> 00:04:51,210
我们将我们的方式，从左至右，
最终寻找麦克·史密斯。

178
00:04:51,210 --> 00:04:53,540
因此，如果该电话本
也许有1000页，

179
00:04:53,540 --> 00:04:56,300
也许它会采取
美国10个左右页眼泪。

180
00:04:56,300 --> 00:04:59,380
>> 但是你可能已经利用
感动的假设

181
00:04:59,380 --> 00:05:03,602
期间所有这一切，这是说
该电话簿中的进步是什么？

182
00:05:03,602 --> 00:05:04,310
听众：排序。

183
00:05:04,310 --> 00:05:05,000
DAVID J.马兰：它的排序。

184
00:05:05,000 --> 00:05:05,160
对？

185
00:05:05,160 --> 00:05:07,909
它是按字母顺序排序，所以
所有这些名字和数字

186
00:05:07,909 --> 00:05:11,230
从A的到排序
Z的，和按字母顺序排列在两者之间。

187
00:05:11,230 --> 00:05:13,100
但是今天，我们现在问
这个问题，那么，

188
00:05:13,100 --> 00:05:16,170
怎么做或Verizon的手机
公司让它进入那个状态？

189
00:05:16,170 --> 00:05:19,560
>> 因为它是一回事，利用
这个假设，因此，

190
00:05:19,560 --> 00:05:22,570
解决与一个问题
算法更有效。

191
00:05:22,570 --> 00:05:24,900
但是，我们从来没有真正
要求在零一周，好了，

192
00:05:24,900 --> 00:05:27,790
多少做到了成本
Verizon公司或其他人

193
00:05:27,790 --> 00:05:29,620
吃出电话簿中有序？

194
00:05:29,620 --> 00:05:29,780
>> 对？

195
00:05:29,780 --> 00:05:31,529
这并不重要，如果无所谓
查找麦克·史密斯

196
00:05:31,529 --> 00:05:35,190
是超级快，如果它需要你
今年的页面开始排序。

197
00:05:35,190 --> 00:05:35,690
对？

198
00:05:35,690 --> 00:05:38,620
你还不如干脆筛选
通过随机化的电话本，

199
00:05:38,620 --> 00:05:40,690
如果它要成为超
昂贵的排序。

200
00:05:40,690 --> 00:05:42,350
因此，如果我们能有另一位志愿者。

201
00:05:42,350 --> 00:05:46,350
让我们在这里仰望
我们如何might--来吧up--如何

202
00:05:46,350 --> 00:05:48,100
我们不妨去整理这些。

203
00:05:48,100 --> 00:05:51,990
>> 如果乔丹居然可以
在这里我们一起在舞台上。

204
00:05:51,990 --> 00:05:55,100
上来吧只是一瞬间。

205
00:05:55,100 --> 00:05:56,359
你叫什么名字？

206
00:05:56,359 --> 00:05:57,150
凯洛琳：卡罗琳。

207
00:05:57,150 --> 00:05:58,691
DAVID J.马兰：卡罗琳，上来吧。

208
00:05:58,691 --> 00:06:02,070
你会被加入
我和乔丹在这里。

209
00:06:02,070 --> 00:06:03,800
卡罗琳，谢谢。

210
00:06:03,800 --> 00:06:04,300
好吧。

211
00:06:04,300 --> 00:06:08,330
所以，我们在这里
卡罗琳是26蓝书

212
00:06:08,330 --> 00:06:10,747
这FAS使用管理
一定的期末考试。

213
00:06:10,747 --> 00:06:13,330
这些越来越难找，
但是我们提前做了

214
00:06:13,330 --> 00:06:15,800
是，我们已经把别人的名字
对每个这些的前部，

215
00:06:15,800 --> 00:06:18,133
但我们已经把通过简单
然后扑灭的全名。

216
00:06:18,133 --> 00:06:22,720
因此，我们会把这个人的名字
L，D，J，B，所有的一种方法，通过Z，

217
00:06:22,720 --> 00:06:24,090
但他们以随机顺序。

218
00:06:24,090 --> 00:06:26,890
所以，如果你愿意，你说话
通过问题，因为你的方式

219
00:06:26,890 --> 00:06:31,620
做吧，你能不能继续前进，
梳理这些对我们来说，从A到Z.

220
00:06:31,620 --> 00:06:34,070
>> 听众：好，那么L是一样，中间的。

221
00:06:34,070 --> 00:06:35,050
C的开始。

222
00:06:35,050 --> 00:06:42,410
B.ĴL.前B，Q.

223
00:06:42,410 --> 00:06:45,140
>> DAVID J.马兰：保持那个
想了一秒钟。

224
00:06:45,140 --> 00:06:48,910
因为否则，这仅仅是
有趣的你，我，和约旦。

225
00:06:48,910 --> 00:06:49,724
在那里，我们走了。

226
00:06:49,724 --> 00:06:50,640
听众：[听不清]。

227
00:06:50,640 --> 00:06:57,299
R.

228
00:06:57,299 --> 00:06:58,090
DAVID J.马兰：OK。

229
00:06:58,090 --> 00:06:59,310
你在干什么？

230
00:06:59,310 --> 00:07:01,730
>> 凯洛琳：M来澳后，

231
00:07:01,730 --> 00:07:02,564
>> DAVID J.马兰：OK。

232
00:07:02,564 --> 00:07:03,064
>> 凯洛琳：O.

233
00:07:03,064 --> 00:07:04,120
DAVID J.马兰：哦，好。

234
00:07:04,120 --> 00:07:04,970
>> 凯洛琳：E.

235
00:07:04,970 --> 00:07:06,730
>> DAVID J.马兰：E，F。是啊。

236
00:07:06,730 --> 00:07:07,620
>> 凯洛琳：T，U，V。

237
00:07:07,620 --> 00:07:10,689
>> DAVID J.马兰：V，T，U，V。因此，
看起来你是making--继续下去。

238
00:07:10,689 --> 00:07:12,730
它看起来像你正在做
一大堆在这里，

239
00:07:12,730 --> 00:07:13,910
和那种一大堆那边。

240
00:07:13,910 --> 00:07:16,230
所以第一个字母的一半，
下半年字母。

241
00:07:16,230 --> 00:07:16,460
行。

242
00:07:16,460 --> 00:07:16,960
好。

243
00:07:16,960 --> 00:07:19,680
那种分裂的问题一分为二。

244
00:07:19,680 --> 00:07:21,771
M，N，X的呀。

245
00:07:21,771 --> 00:07:22,270
凯洛琳：K.

246
00:07:22,270 --> 00:07:22,980
DAVID J.马兰：OK。

247
00:07:22,980 --> 00:07:25,070
那种K.所以你选择
他们一个接一个，

248
00:07:25,070 --> 00:07:27,620
把它向左或向右，
或Z的去在地板上。

249
00:07:27,620 --> 00:07:28,012
行。

250
00:07:28,012 --> 00:07:29,190
>> 凯洛琳：Z回事地板上。

251
00:07:29,190 --> 00:07:29,360
>> DAVID J.马兰：OK。

252
00:07:29,360 --> 00:07:30,920
Y为打算在地板上。

253
00:07:30,920 --> 00:07:31,735
现在，我们可以把X.

254
00:07:31,735 --> 00:07:32,409
>> 凯洛琳：G.

255
00:07:32,409 --> 00:07:33,700
DAVID J.马兰：G的走左边。

256
00:07:33,700 --> 00:07:36,017
S被在朝好的方向发展。

257
00:07:36,017 --> 00:07:37,642
好吧，一个是要全部离开的方式。

258
00:07:37,642 --> 00:07:38,790
>> 凯洛琳：A，B，C，D。

259
00:07:38,790 --> 00:07:39,873
>> DAVID J.马兰：现在，好。

260
00:07:39,873 --> 00:07:43,260
我们有A，B，C W公司去那里。

261
00:07:43,260 --> 00:07:45,566
好吧，T。

262
00:07:45,566 --> 00:07:46,611
>> 凯洛琳：H，I，J。

263
00:07:46,611 --> 00:07:47,860
DAVID J.马兰：H，I，J好。

264
00:07:47,860 --> 00:07:49,160
凯洛琳：在中心，我gonna--

265
00:07:49,160 --> 00:07:50,000
DAVID J.马兰：OK。

266
00:07:50,000 --> 00:07:52,375
所以，现在，我们要样
对合并这些不同的桩。

267
00:07:52,375 --> 00:08:00,730
因此，从A到C，然后我看到D和
E和F和G和H和I尼斯。

268
00:08:00,730 --> 00:08:05,540
Ĵ，K。然后，这个桩
倒挂，但没关系。

269
00:08:05,540 --> 00:08:06,040
当然。

270
00:08:06,040 --> 00:08:07,240
我们可以削减一些角落。

271
00:08:07,240 --> 00:08:07,950
行。

272
00:08:07,950 --> 00:08:10,530
然后，我们需要W，X，Y，Z。

273
00:08:10,530 --> 00:08:11,250
>> 凯洛琳：没错。

274
00:08:11,250 --> 00:08:11,880
>> DAVID J.马兰：优秀。

275
00:08:11,880 --> 00:08:14,122
所以，非常感谢你
卡罗琳进行排序这些。

276
00:08:14,122 --> 00:08:15,030
>> [欢呼]

277
00:08:15,030 --> 00:08:17,287
>> 谢谢。

278
00:08:17,287 --> 00:08:18,120
非常感谢。

279
00:08:18,120 --> 00:08:22,910
所以，现在让我们来考虑一下
卡罗琳如何着手这样做，

280
00:08:22,910 --> 00:08:26,040
而究竟我们
能够用于：我们如何

281
00:08:26,040 --> 00:08:28,409
能够解决
的问题，当我们只是

282
00:08:28,409 --> 00:08:29,950
给出一大堆的随机输入。

283
00:08:29,950 --> 00:08:31,610
>> 好了，它看起来像有
有点制度存在的？

284
00:08:31,610 --> 00:08:32,110
对。

285
00:08:32,110 --> 00:08:34,495
因此，早期的信
在字母表，她

286
00:08:34,495 --> 00:08:37,120
是把到左侧，与
后来字母的字母表，

287
00:08:37,120 --> 00:08:38,270
她投入的权利。

288
00:08:38,270 --> 00:08:40,500
而当她发现
一些近信件，那些

289
00:08:40,500 --> 00:08:43,124
说去旁边对方，
她把那些为了。

290
00:08:43,124 --> 00:08:46,750
所以，我们种了这些小
桩发生排序的输入。

291
00:08:46,750 --> 00:08:50,540
>> 所以这是相当喜欢什么
我们中的大多数人会做。

292
00:08:50,540 --> 00:08:53,530
排序，我们将通过它筛选，
我们希望一种有一个机制。

293
00:08:53,530 --> 00:08:56,930
但它可能是很难写
下来在公式本身。

294
00:08:56,930 --> 00:08:59,010
这感觉更多的有机比一个小。

295
00:08:59,010 --> 00:09:02,560
因此，让我们来看看，如果我们现在就可以绑定
这个问题用更少的投入。

296
00:09:02,560 --> 00:09:05,170
>> 而不是26，让我们
做一些事情少得多

297
00:09:05,170 --> 00:09:09,890
只说，七，背后
这些门，可以这么说。

298
00:09:09,890 --> 00:09:11,300
是否有刚刚7个号码？

299
00:09:11,300 --> 00:09:15,240
如果现在的目标在
一方面是要找到一个值，

300
00:09:15,240 --> 00:09:17,850
让我们来看看如何有效
我们可以去这样做。

301
00:09:17,850 --> 00:09:22,460
而如果让我们现在可以来看看
开始应用一些数字，

302
00:09:22,460 --> 00:09:26,310
或一些公式，用以描述
我们的电话簿的效率

303
00:09:26,310 --> 00:09:31,060
算法，我们的考试书的算法，以及
更一般地，查找信息。

304
00:09:31,060 --> 00:09:34,770
>> 因此，对于这一点，让我先走了，
在触摸屏上在这里，

305
00:09:34,770 --> 00:09:41,100
提出了一个网页浏览器，有
正是这七门。

306
00:09:41,100 --> 00:09:46,670
如果我们能得到一个其他
志愿者来就在这里，

307
00:09:46,670 --> 00:09:48,480
我已经把这些同门在这里。

308
00:09:48,480 --> 00:09:49,170
快速志愿者。

309
00:09:49,170 --> 00:09:51,130
>> 这埃德蒙顿演示会
为更快和更快了。

310
00:09:51,130 --> 00:09:51,600
下来吧。

311
00:09:51,600 --> 00:09:52,308
你叫什么名字？

312
00:09:52,308 --> 00:09:53,040
TREVOR：特雷弗。

313
00:09:53,040 --> 00:09:53,998
>> DAVID J.马兰：特雷弗？

314
00:09:53,998 --> 00:09:55,770
好吧，特雷弗，下来吧。

315
00:09:55,770 --> 00:09:59,212
因此，特雷弗曾在这里志愿
做了类似的问题，但一个是

316
00:09:59,212 --> 00:10:02,170
在范围窄，那将
让我们现在尝试形式化

317
00:10:02,170 --> 00:10:03,970
的过程进行排序这些数字。

318
00:10:03,970 --> 00:10:05,500
>> 所以特雷弗，很高兴见到你。

319
00:10:05,500 --> 00:10:08,720
因此，这里是一个数组，所以要
说，七门列表。

320
00:10:08,720 --> 00:10:10,327
来吧，找到我们的号码50。

321
00:10:10,327 --> 00:10:12,410
然后在事后，
告诉我们你是怎么找到它。

322
00:10:12,410 --> 00:10:19,124

323
00:10:19,124 --> 00:10:20,040
如果be--所有权利。

324
00:10:20,040 --> 00:10:21,945
是啊，这是这里的人吗？

325
00:10:21,945 --> 00:10:24,680
嗯，哦。

326
00:10:24,680 --> 00:10:25,560
行。

327
00:10:25,560 --> 00:10:26,680
你点击的那一个。

328
00:10:26,680 --> 00:10:28,690
好。

329
00:10:28,690 --> 00:10:29,780
>> 而良好。

330
00:10:29,780 --> 00:10:30,970
现在你点击一个。

331
00:10:30,970 --> 00:10:34,060
让我给你话筒，
让你拥有了它在短短的时刻。

332
00:10:34,060 --> 00:10:37,000
来吧，然后点击
接下来，你打算大门。

333
00:10:37,000 --> 00:10:39,812
对很好。

334
00:10:39,812 --> 00:10:41,020
TREVOR：我可以unclick门吗？

335
00:10:41,020 --> 00:10:42,620
DAVID J.马兰：不，你不能unclick。

336
00:10:42,620 --> 00:10:43,119
TREVOR：OK。

337
00:10:43,119 --> 00:10:43,974
这个。

338
00:10:43,974 --> 00:10:45,640
DAVID J.马兰：你想去哪里去了？

339
00:10:45,640 --> 00:10:46,410
哪一个？

340
00:10:46,410 --> 00:10:47,230
>> TREVOR：那一个。

341
00:10:47,230 --> 00:10:48,042
>> DAVID J.马兰：没有。

342
00:10:48,042 --> 00:10:48,450
>> TREVOR：OK。

343
00:10:48,450 --> 00:10:48,735
这个。

344
00:10:48,735 --> 00:10:49,020
>> DAVID J.马兰：是的。

345
00:10:49,020 --> 00:10:49,700
这是很好的。

346
00:10:49,700 --> 00:10:50,380
好吧。

347
00:10:50,380 --> 00:10:53,900
那么，什么是你的算法或
程序这样做，特雷弗？

348
00:10:53,900 --> 00:10:56,149
>> TREVOR：我只是通过去
门，直到我发现了一个50。

349
00:10:56,149 --> 00:10:56,940
DAVID J.马兰：OK。

350
00:10:56,940 --> 00:10:58,150
优秀的算法。

351
00:10:58,150 --> 00:10:59,540
所以这是很好。

352
00:10:59,540 --> 00:11:03,120
因为事实上，如果我透露什么
这背后的另外两个门，是什么

353
00:11:03,120 --> 00:11:06,954
我们会发现这里是
我们只有随机输入。

354
00:11:06,954 --> 00:11:08,870
所以这实际上是为
好，你可以得到。

355
00:11:08,870 --> 00:11:12,509
而事实上，你有优于
详尽地搜索整个数组，

356
00:11:12,509 --> 00:11:15,300
因为这将是真的
倒霉，如果你击中​​了数

357
00:11:15,300 --> 00:11:16,604
50在最后一门。

358
00:11:16,604 --> 00:11:18,520
但是，如果我们是什么，而不是
给你一个假设。

359
00:11:18,520 --> 00:11:20,630
假设我排序的所有
这些门周围，

360
00:11:20,630 --> 00:11:23,500
让你有
号码排序此时，

361
00:11:23,500 --> 00:11:29,730
但是这一次它的实际
一个different--此时，

362
00:11:29,730 --> 00:11:32,640
它实际上排序为您服务。

363
00:11:32,640 --> 00:11:35,380
而现在的目标在眼前
是打数50。

364
00:11:35,380 --> 00:11:36,090
>> TREVOR：OK。

365
00:11:36,090 --> 00:11:37,670
>> DAVID J.马兰：是什么
你的算法将是？

366
00:11:37,670 --> 00:11:39,628
>> TREVOR：嗯，如果是
排序，它要么会

367
00:11:39,628 --> 00:11:42,710
以be--如果大到最大，
降，这将是第一位的，

368
00:11:42,710 --> 00:11:44,751
或者如果它是相反的，
这将是最后一个。

369
00:11:44,751 --> 00:11:48,897
所以，我就请点击此门，
然后只需轻按最后一扇门。

370
00:11:48,897 --> 00:11:49,980
DAVID J.马兰：优秀。

371
00:11:49,980 --> 00:11:50,270
好吧。

372
00:11:50,270 --> 00:11:51,150
因此，我们找到了50号。

373
00:11:51,150 --> 00:11:52,970
所以，只要你知道
他们排序，我们

374
00:11:52,970 --> 00:11:55,040
能够利用这个假设。

375
00:11:55,040 --> 00:11:57,040
因此，他们是太像了
电话簿的例子。

376
00:11:57,040 --> 00:11:59,540
只要你有，即使有
像这样的小问题，

377
00:11:59,540 --> 00:12:02,380
您的输入预先排序，我们可以
居然发现价值可以说是

378
00:12:02,380 --> 00:12:03,130
更有效。

379
00:12:03,130 --> 00:12:05,800
>> 我没有告诉你，如果它是
排序从小到大，或从大到小，

380
00:12:05,800 --> 00:12:08,080
所以这是非常合理的
开始在一端或另一

381
00:12:08,080 --> 00:12:09,750
实际上发现的目标值。

382
00:12:09,750 --> 00:12:11,400
因此，感谢特雷弗为好。

383
00:12:11,400 --> 00:12:13,260
我会propose--很好做。

384
00:12:13,260 --> 00:12:16,960
我们有一个小夹子，事实上，这
是在我们最喜欢的时刻在CS50，

385
00:12:16,960 --> 00:12:19,700
因此有时这些演示
按计划不太去了。

386
00:12:19,700 --> 00:12:22,050
事实上，现在，我
拉错接口

387
00:12:22,050 --> 00:12:23,508
与使用该触摸屏。

388
00:12:23,508 --> 00:12:24,660
所以这是我的错在那里。

389
00:12:24,660 --> 00:12:26,600
>> 因此，这将使
明年的剪辑

390
00:12:26,600 --> 00:12:28,570
为什么我点击我的屏幕上。

391
00:12:28,570 --> 00:12:31,390
但是，让我们快速浏览一下
在去年发生了什么

392
00:12:31,390 --> 00:12:34,770
周杰伦，谁上前，多
像特雷弗在这里，主动请缨，

393
00:12:34,770 --> 00:12:39,380
在这个短片，你会看到
同样的演示如何做不大

394
00:12:39,380 --> 00:12:41,074
揭示了解到同样的教训。

395
00:12:41,074 --> 00:12:41,740
[视频回放]

396
00:12:41,740 --> 00:12:45,360
 - 所有我要你现在要做的就是
找到我，对我们来说，

397
00:12:45,360 --> 00:12:51,674
确实，数50
一步一步来。

398
00:12:51,674 --> 00:12:52,450
>> 一些-The 50？

399
00:12:52,450 --> 00:12:53,190
>> 一些-The 50。

400
00:12:53,190 --> 00:12:55,356
而且，您可以显示什么
背后都有这些门

401
00:12:55,356 --> 00:12:58,540
简单地通过用手指触摸它。

402
00:12:58,540 --> 00:13:00,910
该死的。

403
00:13:00,910 --> 00:13:02,870
>> [笑气]

404
00:13:02,870 --> 00:13:03,806
>> [结束播放]

405
00:13:03,806 --> 00:13:05,430
DAVID J.马兰：所以很顺利。

406
00:13:05,430 --> 00:13:06,796
这些都是未排序的大门。

407
00:13:06,796 --> 00:13:08,670
而周杰伦，当然，
发现这一切太快。

408
00:13:08,670 --> 00:13:12,910
特雷弗做一个更好的工作
在一个教育时机而言，

409
00:13:12,910 --> 00:13:15,850
可以这么说，今年
需要更长的时间来找到它。

410
00:13:15,850 --> 00:13:17,950
当然，后来我们给了
周杰伦第二次机会，

411
00:13:17,950 --> 00:13:20,320
因此我们整理了门，
就像我们做的特雷弗，

412
00:13:20,320 --> 00:13:22,300
和Trevor做超级好这段时间。

413
00:13:22,300 --> 00:13:26,124
但周杰伦做到了一半快。

414
00:13:26,124 --> 00:13:26,790
[视频回放]

415
00:13:26,790 --> 00:13:29,650
-The现在的目标是要还
找到我们的数50，

416
00:13:29,650 --> 00:13:33,030
但这样做算法，和
告诉我们你是如何去了。

417
00:13:33,030 --> 00:13:33,660
>> -行。

418
00:13:33,660 --> 00:13:35,604
>>  - 和，如果你找到它，你把这部电影。

419
00:13:35,604 --> 00:13:37,228
如果你没有找到它，你还给我。

420
00:13:37,228 --> 00:13:38,044
>> -Man。

421
00:13:38,044 --> 00:13:38,860
>> 哦！

422
00:13:38,860 --> 00:13:40,800
>>  -  [听不清] OK。

423
00:13:40,800 --> 00:13:46,236
所以，我要检查结束
首先要确定是否there's--哦。

424
00:13:46,236 --> 00:13:48,646
>> [掌声]

425
00:13:48,646 --> 00:13:53,948

426
00:13:53,948 --> 00:13:55,729
>> [结束播放]

427
00:13:55,729 --> 00:13:56,520
DAVID J.马兰：OK。

428
00:13:56,520 --> 00:13:59,760
所以很明显分拣门
导致更大的效率。

429
00:13:59,760 --> 00:14:01,680
因此，快两倍
就是我的意思存在。

430
00:14:01,680 --> 00:14:03,270
所以周杰伦真的很幸运两次。

431
00:14:03,270 --> 00:14:06,685
而且他也很幸运在这最后
今年，我点了一些蓝光光盘

432
00:14:06,685 --> 00:14:07,560
实际上给出。

433
00:14:07,560 --> 00:14:09,768
我很抱歉这一年，我们
没有具有相同的，特雷弗。

434
00:14:09,768 --> 00:14:11,540
但更好的是是在几年前。

435
00:14:11,540 --> 00:14:14,820
而有些人可能知道这
研究员，肖恩，当他在CS50谁，

436
00:14:14,820 --> 00:14:17,780
有确切的被质疑
同样的问题，尽管在SD，

437
00:14:17,780 --> 00:14:19,360
因为你很快就会看到，早在一天。

438
00:14:19,360 --> 00:14:22,622
而且你会发现，不仅没有
他需要比周杰伦长了一点，

439
00:14:22,622 --> 00:14:25,580
比特雷弗更长一点，这是
其实这个难得的机会

440
00:14:25,580 --> 00:14:29,820
从事几乎每个人都在
众人一拉是价格合适，鼓励

441
00:14:29,820 --> 00:14:31,889
他找到我们寻求的数量。

442
00:14:31,889 --> 00:14:32,930
让我们来。快速浏览一下。

443
00:14:32,930 --> 00:14:33,320
>> [视频回放]

444
00:14:33,320 --> 00:14:33,820
>> -行。

445
00:14:33,820 --> 00:14:36,680
所以在这里你的任务，
肖恩，情况如下。

446
00:14:36,680 --> 00:14:40,860
我曾经背后隐藏的这些
门七位数。

447
00:14:40,860 --> 00:14:45,120
但在一些宗门藏
还有其他的负数。

448
00:14:45,120 --> 00:14:47,500
而你的目标是想
数字除此之外排

449
00:14:47,500 --> 00:14:50,390
作为只是一个数组，或者只是
纸片的序列

450
00:14:50,390 --> 00:14:51,510
在他们身后的数字。

451
00:14:51,510 --> 00:14:55,540
而你的目标是，仅在使用前
阵列在这里，我找了七位数。

452
00:14:55,540 --> 00:14:58,570
而我们则要去批判
你如何去这样做。

453
00:14:58,570 --> 00:14:59,070
-好吧。

454
00:14:59,070 --> 00:15:00,850
-find我们七位数，请。

455
00:15:00,850 --> 00:15:10,500

456
00:15:10,500 --> 00:15:11,000
第

457
00:15:11,000 --> 00:15:15,050

458
00:15:15,050 --> 00:15:18,550
五，19，13。

459
00:15:18,550 --> 00:15:22,240

460
00:15:22,240 --> 00:15:24,770
>> [笑气]

461
00:15:24,770 --> 00:15:25,910
>> 这不是一个很难回答的问题。

462
00:15:25,910 --> 00:15:29,410

463
00:15:29,410 --> 00:15:29,910
一。

464
00:15:29,910 --> 00:15:33,218

465
00:15:33,218 --> 00:15:34,695
>> [笑气]

466
00:15:34,695 --> 00:15:37,861
在这一点上，你的得分不是非常
好，所以你还不如继续下去。

467
00:15:37,861 --> 00:15:40,610

468
00:15:40,610 --> 00:15:41,110
三。

469
00:15:41,110 --> 00:15:43,890

470
00:15:43,890 --> 00:15:45,378
>> [笑气]

471
00:15:45,378 --> 00:15:46,370

472
00:15:46,370 --> 00:15:47,774
>> 继续。

473
00:15:47,774 --> 00:15:50,690
坦率地说，我不禁想知道
什么你甚至想，so--

474
00:15:50,690 --> 00:15:51,959
>> [笑气]

475
00:15:51,959 --> 00:15:53,229

476
00:15:53,229 --> 00:15:55,020
只有最上面一行，因此
你有三个左侧。

477
00:15:55,020 --> 00:15:56,200
所以找我七人。

478
00:15:56,200 --> 00:15:59,700

479
00:15:59,700 --> 00:16:02,167
>> [笑气]

480
00:16:02,167 --> 00:16:14,870

481
00:16:14,870 --> 00:16:15,370
17。

482
00:16:15,370 --> 00:16:25,675

483
00:16:25,675 --> 00:16:26,946
七。

484
00:16:26,946 --> 00:16:28,780
>> [掌声]

485
00:16:28,780 --> 00:16:29,426
>> 好吧。

486
00:16:29,426 --> 00:16:30,360
>> [结束播放]

487
00:16:30,360 --> 00:16:31,840
>> DAVID J.马兰：所以我们可以
观看这些整天。

488
00:16:31,840 --> 00:16:34,090
当然，一些
今年的演示或许

489
00:16:34,090 --> 00:16:36,330
现在最终会在明年
今年的视频以及。

490
00:16:36,330 --> 00:16:39,040
所以，现在让我们来实际
集中在算法

491
00:16:39,040 --> 00:16:42,140
在这里，如果我们不能看到
现在就开始正式

492
00:16:42,140 --> 00:16:46,650
我们如何去获得我们的数据
进入此状态，它的排序，

493
00:16:46,650 --> 00:16:50,054
所以，最终，我们实际上可以
更有效地搜索。

494
00:16:50,054 --> 00:16:52,470
而且即使我们打算
使用非常小的数据集，

495
00:16:52,470 --> 00:16:54,511
像八个数字我们
这里有在黑板上，

496
00:16:54,511 --> 00:16:58,230
最终，这些同样的想法可以申请
1000输入，一百万的投入，

497
00:16:58,230 --> 00:17:02,100
4十亿输入，因为算法
将要基本相同。

498
00:17:02,100 --> 00:17:05,359
>> 所以这是我们最后一次
今天志愿者的机会，

499
00:17:05,359 --> 00:17:09,790
但也许是最复杂的，
为此我们需要8名志愿者

500
00:17:09,790 --> 00:17:12,960
上车，通过走路美国
什么会很快整理的过程

501
00:17:12,960 --> 00:17:15,212
是对这些音乐站在这里。

502
00:17:15,212 --> 00:17:16,170
让我先回到这里。

503
00:17:16,170 --> 00:17:19,692
>> 因此，人们在turquoise--绿色的是什么呢？

504
00:17:19,692 --> 00:17:21,130
你犯？

505
00:17:21,130 --> 00:17:21,630
二。

506
00:17:21,630 --> 00:17:23,069
下来吧。

507
00:17:23,069 --> 00:17:23,569
行。

508
00:17:23,569 --> 00:17:24,420
三。

509
00:17:24,420 --> 00:17:25,400
四。

510
00:17:25,400 --> 00:17:27,247
让我 - 确定，五。

511
00:17:27,247 --> 00:17:28,830
你正在你的朋友提名。

512
00:17:28,830 --> 00:17:31,340
六，七，八。

513
00:17:31,340 --> 00:17:32,130
上来吧。

514
00:17:32,130 --> 00:17:32,630
好吧。

515
00:17:32,630 --> 00:17:33,190
太谢谢你了。

516
00:17:33,190 --> 00:17:33,689
上来吧。

517
00:17:33,689 --> 00:17:34,790
上来吧。

518
00:17:34,790 --> 00:17:35,330
>> 好吧。

519
00:17:35,330 --> 00:17:38,890
所以，我们这里 - 这
是其中比较尴尬的，

520
00:17:38,890 --> 00:17:42,390
因为这将要求你幽默
我的时间只是一点点。

521
00:17:42,390 --> 00:17:43,442
你应第一。

522
00:17:43,442 --> 00:17:44,150
你叫什么名字？

523
00:17:44,150 --> 00:17:44,610
>> 安南：安南。

524
00:17:44,610 --> 00:17:45,526
>> DAVID J.马兰：安南。

525
00:17:45,526 --> 00:17:46,092
大卫。

526
00:17:46,092 --> 00:17:46,800
你叫什么名字？

527
00:17:46,800 --> 00:17:47,140
>> 约瑟夫：约瑟夫。

528
00:17:47,140 --> 00:17:49,190
>> DAVID J.马兰：约瑟夫，
你是二把手。

529
00:17:49,190 --> 00:17:52,260
>> SERENA：小威，排名第三。

530
00:17:52,260 --> 00:17:53,722
斯特凡，排名第四。

531
00:17:53,722 --> 00:17:54,430
辛西亚：辛西娅。

532
00:17:54,430 --> 00:17:57,548
DAVID J.马兰：辛西娅，排名第五。

533
00:17:57,548 --> 00:17:58,452
[听不清]

534
00:17:58,452 --> 00:17:59,618
DAVID J.马兰：[听不清]。

535
00:17:59,618 --> 00:18:00,391
大卫，排名第六。

536
00:18:00,391 --> 00:18:00,890
马特：马特。

537
00:18:00,890 --> 00:18:02,160
DAVID J.马兰：马特的第七位。

538
00:18:02,160 --> 00:18:02,850
然后呢？

539
00:18:02,850 --> 00:18:03,210
>> WAVERLY：韦弗利。

540
00:18:03,210 --> 00:18:04,470
>> DAVID J.马兰：韦弗利，排名第八。

541
00:18:04,470 --> 00:18:04,970
好吧。

542
00:18:04,970 --> 00:18:06,510
如果您could--哎呦。

543
00:18:06,510 --> 00:18:08,820
如果你所有的，因为你的
第一个挑战，有

544
00:18:08,820 --> 00:18:10,820
八音乐架
这里面对观众。

545
00:18:10,820 --> 00:18:14,200
如果你可以把你的号码上
这些乐谱架以这样的方式

546
00:18:14,200 --> 00:18:16,560
他们排队的
相同的数字在黑板上。

547
00:18:16,560 --> 00:18:19,560
所以，让自己看起来像由
把这些音乐你的号码

548
00:18:19,560 --> 00:18:21,960
站在这里。

549
00:18:21,960 --> 00:18:25,980
优秀为止。

550
00:18:25,980 --> 00:18:26,600
>> 优秀的。

551
00:18:26,600 --> 00:18:26,890
行。

552
00:18:26,890 --> 00:18:29,556
所以，现在，我们要问
问题在几个不同的方式。

553
00:18:29,556 --> 00:18:31,610
我们如何去整理
这些人在这里？

554
00:18:31,610 --> 00:18:34,500
因为我们有几种方法
早些时候，由此我们

555
00:18:34,500 --> 00:18:36,360
一种使两个不同的桶。

556
00:18:36,360 --> 00:18:38,842
然后，我们一般
拼凑的东西放在一起。

557
00:18:38,842 --> 00:18:41,050
当我们看到两个数字
这属于一起，

558
00:18:41,050 --> 00:18:41,975
我们把它们放在一起。

559
00:18:41,975 --> 00:18:43,350
两个字母属于一个整体。

560
00:18:43,350 --> 00:18:45,058
>> 但是，如果让我们来看看我们
不能正式这一点，

561
00:18:45,058 --> 00:18:48,044
让我们最终必须
一些伪代码，您会，

562
00:18:48,044 --> 00:18:49,710
使用它可以解决这些问题。

563
00:18:49,710 --> 00:18:51,870
所以，现在，我看着窗外
在这里这些数字。

564
00:18:51,870 --> 00:18:55,030
而且我看到一大堆的错误。

565
00:18:55,030 --> 00:18:57,750
最后，我想一上
左和八个在右侧。

566
00:18:57,750 --> 00:19:00,650
>> 所以我在看
这两个，四个和两个。

567
00:19:00,650 --> 00:19:02,930
而且什么问题，很明显？

568
00:19:02,930 --> 00:19:04,261
是啊。

569
00:19:04,261 --> 00:19:04,760
所以。

570
00:19:04,760 --> 00:19:07,160
两个明显到来之前
四，所以你知道吗？

571
00:19:07,160 --> 00:19:10,210
让我先坐贪婪的方法，
如果你愿意，很像问题

572
00:19:10,210 --> 00:19:13,790
设置埃德蒙顿如果从召回
标准版习题集之一，

573
00:19:13,790 --> 00:19:16,820
在这里我只是在本地解决的问题
这是正确的在这里我面前

574
00:19:16,820 --> 00:19:17,690
并且，顺其自然我。

575
00:19:17,690 --> 00:19:17,870
>> 行。

576
00:19:17,870 --> 00:19:20,161
因此，二和四，让我走
前进，只是换你们两个。

577
00:19:20,161 --> 00:19:22,400
如果你能实际移动
自己和自己的论文，

578
00:19:22,400 --> 00:19:25,040
我似乎已经得到了
列出一个更好的状态。

579
00:19:25,040 --> 00:19:26,330
>> 现在，他们是很好的。

580
00:19:26,330 --> 00:19:28,480
我会继续前进，
四和六，显示效果不错。

581
00:19:28,480 --> 00:19:29,110
不是一个问题。

582
00:19:29,110 --> 00:19:30,440
六，八，确定。

583
00:19:30,440 --> 00:19:31,860
八和一，另一个问题。

584
00:19:31,860 --> 00:19:34,750
因为什么是真正的大约八和一个？

585
00:19:34,750 --> 00:19:36,990
一位来自前八，
所以我们应该怎样做？

586
00:19:36,990 --> 00:19:38,090
让我们来交换这两个。

587
00:19:38,090 --> 00:19:39,316
一个和八个。

588
00:19:39,316 --> 00:19:40,690
而现在，我要坚持下去。

589
00:19:40,690 --> 00:19:42,030
我会继续向前看。

590
00:19:42,030 --> 00:19:42,840
让我们看看会发生什么。

591
00:19:42,840 --> 00:19:44,680
八三，
当然，乱序。

592
00:19:44,680 --> 00:19:45,815
让我们来交换。

593
00:19:45,815 --> 00:19:46,940
八，当然，七，。

594
00:19:46,940 --> 00:19:47,481
坏了。

595
00:19:47,481 --> 00:19:48,280
让我们来交换。

596
00:19:48,280 --> 00:19:49,940
八，五，当然，我们的交换。

597
00:19:49,940 --> 00:19:50,560
好吧。

598
00:19:50,560 --> 00:19:51,880
列表进行排序。

599
00:19:51,880 --> 00:19:53,060
是吗？

600
00:19:53,060 --> 00:19:54,280
>> OK，显然不是。

601
00:19:54,280 --> 00:19:55,860
但它是更好一点，对不对？

602
00:19:55,860 --> 00:19:57,270
因为通知发生了什么事。

603
00:19:57,270 --> 00:20:01,749
每当我们进行了互换，一个小
种数渗出的方式，

604
00:20:01,749 --> 00:20:03,790
而一个更大的数字
渗滤液这样一来，不然我们就

605
00:20:03,790 --> 00:20:06,880
开始说冒泡到
向左或鼓泡到右边。

606
00:20:06,880 --> 00:20:10,080
>> 现在，它是不够的，因为
充其量只是一个数目可能

607
00:20:10,080 --> 00:20:11,990
已经搬到一个地方
向前，或在最坏的情况，

608
00:20:11,990 --> 00:20:13,880
一些可能有
进一步移动一个位置。

609
00:20:13,880 --> 00:20:16,369
所以，你知道什么，这种
中工作得很好至今。

610
00:20:16,369 --> 00:20:17,410
让我再次尝试。

611
00:20:17,410 --> 00:20:18,880
两个和四个，他们确定。

612
00:20:18,880 --> 00:20:20,180
四，六，他们确定。

613
00:20:20,180 --> 00:20:21,790
六一，乱序。

614
00:20:21,790 --> 00:20:23,007
因此，让我们换你们两个。

615
00:20:23,007 --> 00:20:25,840
而现在，注意到这个问题的
开始变得好一点了。

616
00:20:25,840 --> 00:20:27,006
六三，乱序。

617
00:20:27,006 --> 00:20:28,100
让我们来换你们两个。

618
00:20:28,100 --> 00:20:29,730
六，七，你是好。

619
00:20:29,730 --> 00:20:32,230
七，五，当然，乱序。

620
00:20:32,230 --> 00:20:33,920
七，八，为了。

621
00:20:33,920 --> 00:20:36,470
而现在，我可能需要
为此多做几次。

622
00:20:36,470 --> 00:20:39,830
而事实上，想为自己
也许多少次最大

623
00:20:39,830 --> 00:20:41,330
我可能要来回走？

624
00:20:41,330 --> 00:20:42,390
>> 我们会回来的。

625
00:20:42,390 --> 00:20:43,700
因此，二和四都还OK。

626
00:20:43,700 --> 00:20:44,940
四一，没了。

627
00:20:44,940 --> 00:20:45,747
所以，让我们交换。

628
00:20:45,747 --> 00:20:47,830
再次，注意在视觉上
一个是一种冒泡

629
00:20:47,830 --> 00:20:49,163
到左侧，在那里它应该的。

630
00:20:49,163 --> 00:20:50,010
四个和三个交换。

631
00:20:50,010 --> 00:20:51,330
四和六。

632
00:20:51,330 --> 00:20:53,100
六个和五个交换。

633
00:20:53,100 --> 00:20:53,959
六，七。

634
00:20:53,959 --> 00:20:55,000
七，八都不错。

635
00:20:55,000 --> 00:20:55,500
>> 好。

636
00:20:55,500 --> 00:20:58,460
我们正在变得更好。

637
00:20:58,460 --> 00:20:59,130
所以，让我们来看看。

638
00:20:59,130 --> 00:21:00,940
现在，我们有两个和一个。

639
00:21:00,940 --> 00:21:02,520
当然，交换。

640
00:21:02,520 --> 00:21:07,520
两个和三个，三，四，四和
五，六，七，七，八。

641
00:21:07,520 --> 00:21:08,020
好。

642
00:21:08,020 --> 00:21:08,730
你知道吗？

643
00:21:08,730 --> 00:21:11,190
因为我做了一个变化出现，
让我做一全面的检查。

644
00:21:11,190 --> 00:21:13,023
让我一路走
回到起点。

645
00:21:13,023 --> 00:21:13,680
行。

646
00:21:13,680 --> 00:21:14,750
一，two--烨，看到了吗？

647
00:21:14,750 --> 00:21:15,870
出事了。

648
00:21:15,870 --> 00:21:18,420
三，四，五，六，七，八。

649
00:21:18,420 --> 00:21:21,920
而在这最后一关，是
你满意我现在

650
00:21:21,920 --> 00:21:23,830
自称是排序？

651
00:21:23,830 --> 00:21:24,330
行。

652
00:21:24,330 --> 00:21:25,880
从外观上看，这是千真万确的。

653
00:21:25,880 --> 00:21:28,410
但在功能上有什么
也还只是发生

654
00:21:28,410 --> 00:21:31,870
在这最后一关，让您
确认，这份名单确实

655
00:21:31,870 --> 00:21:32,660
排序？

656
00:21:32,660 --> 00:21:34,477
>> 我做了什么或不做这最后一关？

657
00:21:34,477 --> 00:21:35,810
听众：没有更改。

658
00:21:35,810 --> 00:21:36,120
DAVID J.马兰：对不起？

659
00:21:36,120 --> 00:21:37,070
听众：没有变更。

660
00:21:37,070 --> 00:21:38,653
DAVID J.马兰：没有更改。

661
00:21:38,653 --> 00:21:41,947
因此，这将是愚蠢的我来
再次做同样的算法

662
00:21:41,947 --> 00:21:43,780
如果我没有做任何
改变第一时间。

663
00:21:43,780 --> 00:21:45,160
而国家并没有改变。

664
00:21:45,160 --> 00:21:47,576
当然，我不会做
任何改变的第二次。

665
00:21:47,576 --> 00:21:49,820
所以，它的安全，现在
也就是说，列表进行排序。

666
00:21:49,820 --> 00:21:52,069
>> 事实上，这是现在
东西，我们会一般

667
00:21:52,069 --> 00:21:56,900
电话冒泡排序，即配对，
你再纠正错误，

668
00:21:56,900 --> 00:22:00,210
又一次，又一次，你
不断来回，

669
00:22:00,210 --> 00:22:03,370
和来回，直到你
让没有这样的掉期交易，在这一点

670
00:22:03,370 --> 00:22:07,089
你可以相信，是啊，我
完成修复所有的错误。

671
00:22:07,089 --> 00:22:08,630
让我们重新设置，并尝试另一种方法。

672
00:22:08,630 --> 00:22:11,590
如果你们能返回到
该命令你刚才，

673
00:22:11,590 --> 00:22:13,780
这看起来是这样。

674
00:22:13,780 --> 00:22:17,640
现在，让我们的做法一
有点像考试的书，

675
00:22:17,640 --> 00:22:21,122
因此我们不断
选择字母表的字母

676
00:22:21,122 --> 00:22:22,830
我们有种想
对付下一个。

677
00:22:22,830 --> 00:22:26,420
也许这是一个很高的信，
像A，或低字母Z

678
00:22:26,420 --> 00:22:28,170
>> 所以，大家又回到这个顺序。

679
00:22:28,170 --> 00:22:29,800
现在让我做这个。

680
00:22:29,800 --> 00:22:34,880
让我们来看看我知道我有
八个数字在这里。

681
00:22:34,880 --> 00:22:37,410
我要继续前进，
只是刻意选择

682
00:22:37,410 --> 00:22:38,520
最小的元素。

683
00:22:38,520 --> 00:22:38,760
对？

684
00:22:38,760 --> 00:22:39,801
这似乎直觉了。

685
00:22:39,801 --> 00:22:42,560
我为什么不找最小
元素，把它放在它属于，

686
00:22:42,560 --> 00:22:45,280
那么获得下一个最小的元素，把
它在它所属，而只是重复。

687
00:22:45,280 --> 00:22:46,820
>> 因为直观，
应该工作了。

688
00:22:46,820 --> 00:22:48,441
于是四，这是一个非常小的数目。

689
00:22:48,441 --> 00:22:49,940
我会记住这是。

690
00:22:49,940 --> 00:22:50,523
等待一分钟。

691
00:22:50,523 --> 00:22:51,577
两个较小。

692
00:22:51,577 --> 00:22:53,910
现在我还记得，其中两个
是的，忘记约四。

693
00:22:53,910 --> 00:22:55,050
稍后我们会处理这一点。

694
00:22:55,050 --> 00:22:56,460
六，我不感兴趣。

695
00:22:56,460 --> 00:22:57,810
八，我不感兴趣的

696
00:22:57,810 --> 00:22:59,780
一个是我的新小数目。

697
00:22:59,780 --> 00:23:01,470
所以，我要记住的是。

698
00:23:01,470 --> 00:23:02,534
三，不感兴趣。

699
00:23:02,534 --> 00:23:03,450
七，不感兴趣。

700
00:23:03,450 --> 00:23:04,530
五，不感兴趣。

701
00:23:04,530 --> 00:23:07,390
>> 因此，没有脱落
今年的舞台，

702
00:23:07,390 --> 00:23:09,890
我要抢号埃德蒙顿
什么是你的名字？

703
00:23:09,890 --> 00:23:10,150
>> 安南：安南。

704
00:23:10,150 --> 00:23:11,220
>> DAVID J.马兰：安南。

705
00:23:11,220 --> 00:23:13,540
如果你能和我一起在
在列表的开头，

706
00:23:13,540 --> 00:23:14,870
让我们把你属于你的地方。

707
00:23:14,870 --> 00:23:16,080
Unfortunately--你叫什么名字？

708
00:23:16,080 --> 00:23:16,650
>> 史蒂芬：斯特凡。

709
00:23:16,650 --> 00:23:18,191
>> DAVID J.马兰：斯特凡是在路上。

710
00:23:18,191 --> 00:23:23,490
因此斯特凡解决此之前，
的问题，我们应该怎样做？

711
00:23:23,490 --> 00:23:25,412
我们该怎么办与斯特凡？

712
00:23:25,412 --> 00:23:27,269
>> 听众：[听不清]。

713
00:23:27,269 --> 00:23:28,060
DAVID J.马兰：OK。

714
00:23:28,060 --> 00:23:28,850
因此，我们可以做到这一点。

715
00:23:28,850 --> 00:23:31,730
那种我们可以采取斯特凡和他的
四，并把它放在一个变量

716
00:23:31,730 --> 00:23:33,530
并抓住它的
一定的时间，

717
00:23:33,530 --> 00:23:35,220
从而使空间的头号。

718
00:23:35,220 --> 00:23:36,280
而这也不错。

719
00:23:36,280 --> 00:23:39,270
我可以建议，为什么不
我们只要把斯特凡这里？

720
00:23:39,270 --> 00:23:41,610
为什么会这样侵犯1
的想法，我们开始

721
00:23:41,610 --> 00:23:44,830
谈到最后一次，最后一周？

722
00:23:44,830 --> 00:23:45,330
是吗？

723
00:23:45,330 --> 00:23:45,740
>> 听众：[听不清]。

724
00:23:45,740 --> 00:23:46,860
>> DAVID J.马兰：有没有索引它。

725
00:23:46,860 --> 00:23:49,735
如果你觉得这，的确，作为一个
数组，这就像消极的，

726
00:23:49,735 --> 00:23:52,900
所以没有记忆实际上
在这里，如果这确实是一个数组，

727
00:23:52,900 --> 00:23:55,090
就像我们上周在演讲中声明。

728
00:23:55,090 --> 00:23:56,250
所以，我们不应该这样做。

729
00:23:56,250 --> 00:23:57,340
我们可以将其存储在一个变量。

730
00:23:57,340 --> 00:23:57,820
>> 或者，你知道吗？

731
00:23:57,820 --> 00:23:59,153
我听到有人建议它。

732
00:23:59,153 --> 00:24:01,020
还有什么可能我们做斯特凡？

733
00:24:01,020 --> 00:24:03,770
为什么我们不赶他，
让他在那里一把手了。

734
00:24:03,770 --> 00:24:05,170
所以，如果你想要去那边。

735
00:24:05,170 --> 00:24:07,300
事实上，这是一个
相当不错的解决方案。

736
00:24:07,300 --> 00:24:10,480
现在，一方面，我有样
所取得的问题更加严重。

737
00:24:10,480 --> 00:24:13,650
四是现在越来越远
从那里应该。

738
00:24:13,650 --> 00:24:14,900
它应该是朝着这个一半。

739
00:24:14,900 --> 00:24:16,100
>> 但是，你知道吗？

740
00:24:16,100 --> 00:24:17,630
这可能是运气不好。

741
00:24:17,630 --> 00:24:18,822
也许第八在这里。

742
00:24:18,822 --> 00:24:20,530
因此，也许我们会
已经得到了幸运，

743
00:24:20,530 --> 00:24:22,460
并推8更接近结尾。

744
00:24:22,460 --> 00:24:24,710
因此，在一天结束时，
那种一切平均数。

745
00:24:24,710 --> 00:24:26,085
我们不需要关心四人。

746
00:24:26,085 --> 00:24:29,400
我只关心现在的问题是
选择的最小元素。

747
00:24:29,400 --> 00:24:32,030
>> 而现在，我要去
做的是忘掉头号

748
00:24:32,030 --> 00:24:35,160
永久，因为我知道
我身后列表现在排序。

749
00:24:35,160 --> 00:24:36,720
所以，我的名单是以前大小八强。

750
00:24:36,720 --> 00:24:37,720
现在，它的大小七。

751
00:24:37,720 --> 00:24:40,340
所以我的问题越来越
更小的，虽然线性。

752
00:24:40,340 --> 00:24:43,022
所以，现在，我要选择
目前最小的元素，两种。

753
00:24:43,022 --> 00:24:46,520
六，八，四，三，七，五。

754
00:24:46,520 --> 00:24:47,770
这是最小的元素。

755
00:24:47,770 --> 00:24:49,416
所以，我该怎么办with--
你叫什么名字来着？

756
00:24:49,416 --> 00:24:49,760
>> 约瑟夫：约瑟夫。

757
00:24:49,760 --> 00:24:50,085
>> DAVID J.马兰：约瑟夫？

758
00:24:50,085 --> 00:24:52,000
我们要离开约瑟夫到位。

759
00:24:52,000 --> 00:24:54,842
现在，我要假装
这些家伙are--好，

760
00:24:54,842 --> 00:24:56,550
我知道这两个
已经排序。

761
00:24:56,550 --> 00:24:58,424
现在，让我们专注于
其余名单。

762
00:24:58,424 --> 00:25:00,080
六是目前最小的。

763
00:25:00,080 --> 00:25:01,190
八是更大的。

764
00:25:01,190 --> 00:25:02,970
四是现在目前最小的。

765
00:25:02,970 --> 00:25:04,762
三是现在目前最小的。

766
00:25:04,762 --> 00:25:07,720
所以现在，我要选择三种，
谁is--你叫什么名字来着？

767
00:25:07,720 --> 00:25:08,190
SERENA：小威。

768
00:25:08,190 --> 00:25:10,620
DAVID J.马兰：小威，如果你能
抓住你的号码和交换with--

769
00:25:10,620 --> 00:25:11,550
格桑：格桑。

770
00:25:11,550 --> 00:25:12,940
DAVID J.马兰：格桑。

771
00:25:12,940 --> 00:25:15,220
快点回来，我们很
要交换这两个。

772
00:25:15,220 --> 00:25:17,360
现在，让我们把这个自动驾驶仪。

773
00:25:17,360 --> 00:25:21,589
我会去把它给你们
以选择下一个最小的元素。

774
00:25:21,589 --> 00:25:22,380
敦，讨债，讨债，讨债。

775
00:25:22,380 --> 00:25:24,560
排名第四，你该怎么办？

776
00:25:24,560 --> 00:25:26,261
优秀的。

777
00:25:26,261 --> 00:25:27,760
现在，我要再拍通。

778
00:25:27,760 --> 00:25:28,590
敦，讨债，讨债，讨债。

779
00:25:28,590 --> 00:25:31,465
我看到五是下一个最小。

780
00:25:31,465 --> 00:25:32,840
现在，我打算采取另一种通。

781
00:25:32,840 --> 00:25:33,631
敦，讨债，讨债，讨债。

782
00:25:33,631 --> 00:25:34,880
六是最小的。

783
00:25:34,880 --> 00:25:35,520
好。

784
00:25:35,520 --> 00:25:36,585
七是最小的。

785
00:25:36,585 --> 00:25:37,085
不用找了。

786
00:25:37,085 --> 00:25:38,630
八是最小的。

787
00:25:38,630 --> 00:25:39,170
完成。

788
00:25:39,170 --> 00:25:43,900
>> 因此，我们刚刚通过反复做
后，其他选择一种元素

789
00:25:43,900 --> 00:25:47,230
正在实施的东西，我们
要为选择排序正规化。

790
00:25:47,230 --> 00:25:49,120
而且这甚至
简单的解释，

791
00:25:49,120 --> 00:25:51,310
在字面上你
想要做的就是保持

792
00:25:51,310 --> 00:25:54,700
来回通过列表
选择，下一个最小的元素，

793
00:25:54,700 --> 00:25:55,720
直到大功告成。

794
00:25:55,720 --> 00:25:58,650
>> 因此，它更简单，也许
凭直觉，高于去年。

795
00:25:58,650 --> 00:26:00,020
让我们来试一试最后一个。

796
00:26:00,020 --> 00:26:03,060
如果你们能重置自己
到以下位置

797
00:26:03,060 --> 00:26:08,600
最后一次，让我们看看如果我们不能
现在正式另外一个方法。

798
00:26:08,600 --> 00:26:12,857
事实上，会有人
在那里想提议

799
00:26:12,857 --> 00:26:14,440
怎么回事，我们可能会去这样做？

800
00:26:14,440 --> 00:26:17,439
如果没有折腾出的流行语或排序
这是已知的答案，

801
00:26:17,439 --> 00:26:19,689
只是凭直觉，我们能做什么？

802
00:26:19,689 --> 00:26:21,635
>> 听众：[听不清]。

803
00:26:21,635 --> 00:26:22,510
DAVID J.马兰：是的。

804
00:26:22,510 --> 00:26:24,620
因此，有一些伟大的直觉那里。

805
00:26:24,620 --> 00:26:28,020
好东西似乎发生迄今
在当我们把计算机科学

806
00:26:28,020 --> 00:26:30,832
并征服分裂的问题
成两半，一半一半。

807
00:26:30,832 --> 00:26:32,540
所以事实上，我们
可以开始这样做。

808
00:26:32,540 --> 00:26:35,754
而事实上，这将是，我们将
看，我们的最佳解决方案之一呢。

809
00:26:35,754 --> 00:26:37,420
但是，让我们回过头来，不久。

810
00:26:37,420 --> 00:26:40,500
事实上，我们要做的
本周稍晚。

811
00:26:40,500 --> 00:26:42,180
还有什么可能我们该如何解决呢？

812
00:26:42,180 --> 00:26:44,647
所以每个人都在这里是
看似随机的顺序。

813
00:26:44,647 --> 00:26:45,230
你知道吗？

814
00:26:45,230 --> 00:26:48,320
而不是来回走，
来回，来回

815
00:26:48,320 --> 00:26:50,624
每一次，这种感觉就像
我做了很多的步行。

816
00:26:50,624 --> 00:26:52,790
为什么不让我刚开始在
在列表的开头，

817
00:26:52,790 --> 00:26:54,960
和刚刚放四个它所属？

818
00:26:54,960 --> 00:26:59,680
因此，让我承担的那一刻起
我的名单只有这个第一要素。

819
00:26:59,680 --> 00:27:04,937
为四排在这个时刻，
如果我所关心的是这里的一切？

820
00:27:04,937 --> 00:27:06,520
这有点平凡真实的，对不对？

821
00:27:06,520 --> 00:27:10,000
像含有一个号码列表中，并
这个数字四是明显的排序。

822
00:27:10,000 --> 00:27:13,070
>> 所以，我只是规定
这个列表进行排序。

823
00:27:13,070 --> 00:27:15,090
但现在我有这个名单的其余部分。

824
00:27:15,090 --> 00:27:17,240
所以，现在，我遇到两个。

825
00:27:17,240 --> 00:27:21,690
其中有两个作用明显
对于四个属于？

826
00:27:21,690 --> 00:27:22,580
前四人。

827
00:27:22,580 --> 00:27:23,862
所以，我能做些什么吗？

828
00:27:23,862 --> 00:27:24,820
你叫什么名字来着？

829
00:27:24,820 --> 00:27:25,090
>> 约瑟夫：约瑟夫。

830
00:27:25,090 --> 00:27:26,030
>> DAVID J.马兰：约瑟夫，
如果你能后退一步

831
00:27:26,030 --> 00:27:27,790
只是一个与你的电话号码的时刻。

832
00:27:27,790 --> 00:27:31,130
现在我应该斯特凡在这里做？

833
00:27:31,130 --> 00:27:33,720
让我们转移斯特凡在这里。

834
00:27:33,720 --> 00:27:35,520
现在，让约瑟夫来到这里。

835
00:27:35,520 --> 00:27:39,660
现在，让我声称，
这里的一切进行排序。

836
00:27:39,660 --> 00:27:42,474
因此，类似的结果，但一
完全不同的方法。

837
00:27:42,474 --> 00:27:44,140
我还没有看什么是那里。

838
00:27:44,140 --> 00:27:46,310
我只是不停地服用元素
因为他们交给我，

839
00:27:46,310 --> 00:27:47,240
并加以处理。

840
00:27:47,240 --> 00:27:48,330
>> 所以，现在，我看到老六。

841
00:27:48,330 --> 00:27:51,110
哪里老六属于？

842
00:27:51,110 --> 00:27:53,250
我们有两个，四个，六个。

843
00:27:53,250 --> 00:27:54,800
正是她现在。

844
00:27:54,800 --> 00:27:57,750
因此，让我们离开那个独自一人，而现在
权利要求，这部分列表的

845
00:27:57,750 --> 00:27:58,772
现在排序。

846
00:27:58,772 --> 00:28:01,230
所以，这种感觉从根本上
在不同的我只是

847
00:28:01,230 --> 00:28:05,230
通过列表正朝这边
线性，而且我从来没有翻倍了。

848
00:28:05,230 --> 00:28:05,730
是。

849
00:28:05,730 --> 00:28:06,230
好吧。

850
00:28:06,230 --> 00:28:08,190
所以八，你在哪里属于？

851
00:28:08,190 --> 00:28:08,730
就在这儿。

852
00:28:08,730 --> 00:28:09,310
完善。

853
00:28:09,310 --> 00:28:10,210
所以，现在之一。

854
00:28:10,210 --> 00:28:10,900
嗯，哦。

855
00:28:10,900 --> 00:28:13,010
这感觉就像它的
将是昂贵的。

856
00:28:13,010 --> 00:28:15,690
现在，以前的算法中，
我刚换的人。

857
00:28:15,690 --> 00:28:18,648
所以，我可能把他在一路
开始的时候，但随后又转而约瑟夫。

858
00:28:18,648 --> 00:28:21,450
但是，如果我移动约瑟夫，现在
这是怎么回事是错的？

859
00:28:21,450 --> 00:28:24,250
>> 现在，我已经有点儿undone--我已经
采取一步步推进，然后

860
00:28:24,250 --> 00:28:26,300
退一万步，因为现在
约瑟夫会失灵。

861
00:28:26,300 --> 00:28:26,830
因此，让我们做到这一点。

862
00:28:26,830 --> 00:28:29,150
如果你可以采取一把手
而退一步就一下。

863
00:28:29,150 --> 00:28:30,490
我们怎样才能put--什么
又是你的名字吗？

864
00:28:30,490 --> 00:28:31,130
>> 安南：安南。

865
00:28:31,130 --> 00:28:32,610
>> DAVID J.马兰：安南的地方？

866
00:28:32,610 --> 00:28:36,091
需要什么就
到二，四，六，八？

867
00:28:36,091 --> 00:28:37,570
他们都需要转移。

868
00:28:37,570 --> 00:28:42,590
因此，如果其中8把业务转移
第一，后面是6个，然后四，那么两种。

869
00:28:42,590 --> 00:28:45,380
然后，安南，如果你愿意
喜欢到这里来的，不错。

870
00:28:45,380 --> 00:28:47,760
但在这里，我们刚刚
那种付出了代价

871
00:28:47,760 --> 00:28:49,510
在不同的点的算法中。

872
00:28:49,510 --> 00:28:52,550
而最后一次与选择
排序，甚至冒泡排序，

873
00:28:52,550 --> 00:28:54,700
我走回来，
第四，反反复复，

874
00:28:54,700 --> 00:28:58,360
这肯定是添加了
在时间方面，并逐步从字面上。

875
00:28:58,360 --> 00:29:00,660
>> 插入排序，在第一次
一目了然，看起来像它

876
00:29:00,660 --> 00:29:05,150
超级聪明，因为我只是
取得缓慢，逐步进展，

877
00:29:05,150 --> 00:29:07,120
但我不打算这样来回。

878
00:29:07,120 --> 00:29:09,410
但是，如果有人确实是
失灵，通知

879
00:29:09,410 --> 00:29:10,840
所有我必须做的工作。

880
00:29:10,840 --> 00:29:14,750
我不得不把一半的列表
只是为了腾出空间给一把手。

881
00:29:14,750 --> 00:29:16,790
因此，它是同量
工作迄今它

882
00:29:16,790 --> 00:29:18,690
感觉，只是不同类型的工作。

883
00:29:18,690 --> 00:29:19,370
>> 让我们继续。

884
00:29:19,370 --> 00:29:22,657
所以，现在我们知道，每个人都
1到8之间进行排序。

885
00:29:22,657 --> 00:29:23,740
在这里，我排名第三。

886
00:29:23,740 --> 00:29:25,864
如果你喜欢拿起
第三，退一步之一。

887
00:29:25,864 --> 00:29:28,260
而且你们怎么需要做什么？

888
00:29:28,260 --> 00:29:28,760
是的。

889
00:29:28,760 --> 00:29:33,070
所以这是另外一个，两个，三个步骤。

890
00:29:33,070 --> 00:29:36,010
三个单位的时间，仅仅花费
我，使三者可以现在适合。

891
00:29:36,010 --> 00:29:37,460
最后，七。

892
00:29:37,460 --> 00:29:39,730
>> 让我们继续前进，并有
你退后一步。

893
00:29:39,730 --> 00:29:42,780
这只会花费我们
一个单位时间，但没关系。

894
00:29:42,780 --> 00:29:44,170
而现在，五的打算
要贵一点。

895
00:29:44,170 --> 00:29:45,340
如果您想退一步。

896
00:29:45,340 --> 00:29:48,380
我们需要移动八，
七，六。

897
00:29:48,380 --> 00:29:50,749
然后大家现在来分类的。

898
00:29:50,749 --> 00:29:52,290
因此，一只大手在这里我们的志愿者。

899
00:29:52,290 --> 00:29:53,554
太谢谢你了。

900
00:29:53,554 --> 00:29:56,220
>> [掌声]

901
00:29:56,220 --> 00:29:56,860
>> 谢谢你们。

902
00:29:56,860 --> 00:29:57,520
谢谢你们。

903
00:29:57,520 --> 00:30:02,940
因此，让我们现在只是怎么看
昂贵的这一切了。

904
00:30:02,940 --> 00:30:06,210
让我们考虑可能是
最简单的这些，冒泡排序。

905
00:30:06,210 --> 00:30:09,950
而且我说的简单，仅仅是因为
你可以只是贪婪地解决这个问题

906
00:30:09,950 --> 00:30:11,660
在这里解决的配对问题。

907
00:30:11,660 --> 00:30:13,720
修复配对问题
在这里，连连

908
00:30:13,720 --> 00:30:17,680
周而复始，重复尽可能多
倍，你实际需要。

909
00:30:17,680 --> 00:30:21,050
>> 所以，事实证明，
用冒泡排序，那么，

910
00:30:21,050 --> 00:30:25,820
要走多少步我必须采取
该算法的第一次通过？

911
00:30:25,820 --> 00:30:30,850
我可能take--让我们see--之一，
二，三，四，五，六，七。

912
00:30:30,850 --> 00:30:32,190
还有的八种元素在这里。

913
00:30:32,190 --> 00:30:35,280
因此，它如N减1步骤
从列表的开头获得

914
00:30:35,280 --> 00:30:36,380
到列表的末尾。

915
00:30:36,380 --> 00:30:41,350
>> 但随着选择排序，还记得我
一次又一次地选择这些元素

916
00:30:41,350 --> 00:30:44,590
又一次这是最小的，
我把它在的地方，

917
00:30:44,590 --> 00:30:46,616
但我不
再次看我身后。

918
00:30:46,616 --> 00:30:49,490
所以，我认为这是一个更加清楚一点
那么这是第一次，我可能会

919
00:30:49,490 --> 00:30:52,680
必须采取所有N减1步骤
找到的最小元素。

920
00:30:52,680 --> 00:30:55,920
然后，我把他们在的地方，我
驱逐谁在这里之前。

921
00:30:55,920 --> 00:30:57,500
>> 但是当时我没有
守望着这个元素，

922
00:30:57,500 --> 00:30:59,040
因为我知道这是
已经最小。

923
00:30:59,040 --> 00:31:01,581
所以，现在，我可以看看短短七年
元素，那么六要素，

924
00:31:01,581 --> 00:31:03,290
然后五行，然后四个要素。

925
00:31:03,290 --> 00:31:06,900
等数学上，如果n是
元件或号码的数目

926
00:31:06,900 --> 00:31:11,990
我们开始使用，你可以想像
这是相同的如正减1，

927
00:31:11,990 --> 00:31:14,250
加N减2步，
加N减去3个步骤，

928
00:31:14,250 --> 00:31:16,780
加N减去4个步骤，所有的
一路下跌到只有一个步骤。

929
00:31:16,780 --> 00:31:18,160
而我在我的最后一个人。

930
00:31:18,160 --> 00:31:20,650
>> 如果你还记得，很多
的统计书籍或数学书

931
00:31:20,650 --> 00:31:24,730
对这些公式
精装背部或它们的前，

932
00:31:24,730 --> 00:31:27,690
事实证明，这一系列
可表示更简单地

933
00:31:27,690 --> 00:31:28,857
为N乘以N减1比2。

934
00:31:28,857 --> 00:31:31,273
而且它是很好，如果这不是
在你的脑海里。

935
00:31:31,273 --> 00:31:32,420
但是，这确实是真的。

936
00:31:32,420 --> 00:31:34,449
这是写它只是一个简单的方法。

937
00:31:34,449 --> 00:31:36,240
然后，如果你认为
回到小学，

938
00:31:36,240 --> 00:31:38,698
当你刚开始繁殖
东西出来，这门课程，

939
00:31:38,698 --> 00:31:41,820
是仅仅局限于N的平方减去n乘2分。

940
00:31:41,820 --> 00:31:44,772
所有我所做的就是扩大
表达式那里。

941
00:31:44,772 --> 00:31:46,730
因此，让我们重写这个
有点不同。

942
00:31:46,730 --> 00:31:49,780
这n值的平方除以2减去N / 2。

943
00:31:49,780 --> 00:31:53,270
>> 所以，再一次，我只是样的应用
一些算术规则存在。

944
00:31:53,270 --> 00:31:57,140
但现在发现的最大期限
在这个表达式，可以这么说，

945
00:31:57,140 --> 00:31:58,540
是是n的平方。

946
00:31:58,540 --> 00:32:02,910
所以，是的，这是Ñ平方
2，再减去N / 2分。

947
00:32:02,910 --> 00:32:05,080
>> 但是，一般情况下，如果n
将是一个很大的值，

948
00:32:05,080 --> 00:32:08,740
我要去声称是n的平方
将是主导因素。

949
00:32:08,740 --> 00:32:10,490
它只是要
更大的贡献

950
00:32:10,490 --> 00:32:12,877
到步骤大于n / 2的数量。

951
00:32:12,877 --> 00:32:13,960
所以，什么意思呢？

952
00:32:13,960 --> 00:32:16,795
让我们尝试一个简单的例子，甚至
虽然数学变得有点大了。

953
00:32:16,795 --> 00:32:20,210
>> 因此，假设我们有100万人次
在舞台上，即100万的事情

954
00:32:20,210 --> 00:32:21,320
我们要排序。

955
00:32:21,320 --> 00:32:23,730
让我们插上一百万
到正是公式

956
00:32:23,730 --> 00:32:27,230
看看有多少步骤，它需要总
比如使用排序一百万元，

957
00:32:27,230 --> 00:32:28,560
选择排序。

958
00:32:28,560 --> 00:32:30,760
>> 所以我们会像以前一样有相同的配方。

959
00:32:30,760 --> 00:32:34,120
我想插一百万，让我得到
2百万平方分，

960
00:32:34,120 --> 00:32:35,990
减去一百万除以2。

961
00:32:35,990 --> 00:32:40,180
如果我这样做，数学提前
在这里，我们有500个十亿

962
00:32:40,180 --> 00:32:47,460
减去50万件，其中
给我们499999500000，

963
00:32:47,460 --> 00:32:49,270
这是相当不错的大。

964
00:32:49,270 --> 00:32:54,370
>> 事实上，如果你现在比较
499十亿999亿美元，

965
00:32:54,370 --> 00:33:01,210
500000对我们原来的价值，
500强十亿，它是如此该死的接近。

966
00:33:01,210 --> 00:33:06,850
对？ ñ平方2给出了分
us--或者说，正平方除以2

967
00:33:06,850 --> 00:33:08,370
给了美国500强十亿。

968
00:33:08,370 --> 00:33:13,510
那是相当的接近
为499999500000，

969
00:33:13,510 --> 00:33:17,970
这就是说中减去500000，
或更一般地，减去脱

970
00:33:17,970 --> 00:33:20,010
ñ平方，不是一个真正的大问题。

971
00:33:20,010 --> 00:33:22,490
n个平方，使这些
数量的增长非常快。

972
00:33:22,490 --> 00:33:25,790
>> 现在，这不仅是重要的，只要
因为我们作为计算机科学家，

973
00:33:25,790 --> 00:33:29,350
一般都不会去管这么多
关于这些公式的细微差别

974
00:33:29,350 --> 00:33:31,400
而正是
准确的答案。

975
00:33:31,400 --> 00:33:33,390
我们关心的，不仅如此，你知道吗？

976
00:33:33,390 --> 00:33:37,810
在一天结束时，这个公式
是n的平方的数量级。

977
00:33:37,810 --> 00:33:39,350
>> 是的，我们用2在那里分裂。

978
00:33:39,350 --> 00:33:41,360
是的，我们减去关闭N减去2。

979
00:33:41,360 --> 00:33:46,860
但在一天结束时，术语
这真的伤害了我们，并且收费我们

980
00:33:46,860 --> 00:33:48,995
很多步骤是平方项。

981
00:33:48,995 --> 00:33:51,370
所以，什么是计算机科学家
是要一般做

982
00:33:51,370 --> 00:33:54,160
是忽略所有的那些
小订单条款，

983
00:33:54,160 --> 00:33:56,900
而只是看一个
最有助于成本。

984
00:33:56,900 --> 00:34:00,530
>> 这是很好的，因为我们可以
现在谈论的更大的通用性

985
00:34:00,530 --> 00:34:02,470
有关算法，并可以对它们进行比较。

986
00:34:02,470 --> 00:34:04,550
而事实上，我
使用此操作系统是经过深思熟虑的。

987
00:34:04,550 --> 00:34:06,680
当我说的顺序
对，我特别

988
00:34:06,680 --> 00:34:09,560
指的是什么
所谓的大澳和大O

989
00:34:09,560 --> 00:34:14,090
是一个符号，一个计算机
科学家用来描述

990
00:34:14,090 --> 00:34:16,710
一个上限的东西。

991
00:34:16,710 --> 00:34:21,150
>> 所以，如果你说一个算法
在大O n个平方，

992
00:34:21,150 --> 00:34:23,380
我建议只是一个
刚才那装置

993
00:34:23,380 --> 00:34:27,710
在其运行的条件
时间和效率，

994
00:34:27,710 --> 00:34:30,090
它需要的顺序
n个平方的步骤。

995
00:34:30,090 --> 00:34:31,420
也许更多，也许更少。

996
00:34:31,420 --> 00:34:33,435
但它是n的顺序平方。

997
00:34:33,435 --> 00:34:34,560
这就是上限。

998
00:34:34,560 --> 00:34:36,530
它不会是
比这更痛苦。

999
00:34:36,530 --> 00:34:40,800
它不会为n的三次方，或2
到n，什么更大。

1000
00:34:40,800 --> 00:34:43,800
这是一个上限
在任何的费用。

1001
00:34:43,800 --> 00:34:46,150
因此考虑到，让我们
考虑的几个例子。

1002
00:34:46,150 --> 00:34:49,820
而这仅仅是一个有限列表
很常见的运行时间

1003
00:34:49,820 --> 00:34:52,870
为的意思是算法
说明一些事情，我们已经

1004
00:34:52,870 --> 00:34:53,600
已经看到了。

1005
00:34:53,600 --> 00:34:58,060
>> 因此，例如，在的情况下
选择排序，就是我自称在这里

1006
00:34:58,060 --> 00:35:02,250
是选择排序的运行
时间是n的顺序平方。

1007
00:35:02,250 --> 00:35:06,260
在最坏的情况下，我将不得不
一大堆的随机数在这里的。

1008
00:35:06,260 --> 00:35:08,600
正如我们看到的数学，
如果我继续走

1009
00:35:08,600 --> 00:35:11,310
该列表，通过
列表中，选择下一个最小的

1010
00:35:11,310 --> 00:35:14,410
一次又一次的元素，如果我
其实写下所有的步骤

1011
00:35:14,410 --> 00:35:18,750
我正在为我提出通过公式
之前，它的Ñ平方的数量级

1012
00:35:18,750 --> 00:35:20,370
我正在采取措施。

1013
00:35:20,370 --> 00:35:24,520
>> 而事实证明，泡沫
排序和插入排序

1014
00:35:24,520 --> 00:35:27,370
只是在最坏的情况下慢。

1015
00:35:27,370 --> 00:35:32,040
考虑，例如，插入排序，
在最后的算法，我们处理了，

1016
00:35:32,040 --> 00:35:35,500
其中有我们来看看元素，
然后将其在它所属。

1017
00:35:35,500 --> 00:35:38,720
然后我们看的下一个元素，
并将其插入它所属。

1018
00:35:38,720 --> 00:35:40,990
>> 因此考虑可能的最佳方案。

1019
00:35:40,990 --> 00:35:45,590
假设我有我的志愿者排队
从字面上是这样，一至八，

1020
00:35:45,590 --> 00:35:47,440
已经排序。

1021
00:35:47,440 --> 00:35:51,300
多少个步骤是插入排序
要采取八人进行排序，

1022
00:35:51,300 --> 00:35:55,640
如果他们在舞台上到达
这样看？

1023
00:35:55,640 --> 00:35:57,410
>> 八人已经排序。

1024
00:35:57,410 --> 00:35:58,760
我用插入排序。

1025
00:35:58,760 --> 00:36:02,180
这最后的算法。

1026
00:36:02,180 --> 00:36:03,640
好吧，让我们重演了真正的快速。

1027
00:36:03,640 --> 00:36:05,504
所以，如果我从这里开始，我看到一个。

1028
00:36:05,504 --> 00:36:06,420
究竟应该属于？

1029
00:36:06,420 --> 00:36:07,730
它属于这里。

1030
00:36:07,730 --> 00:36:08,330
我看到两个。

1031
00:36:08,330 --> 00:36:09,660
哪里两者属于？

1032
00:36:09,660 --> 00:36:10,260
就在这儿。

1033
00:36:10,260 --> 00:36:10,900
我看到有三。

1034
00:36:10,900 --> 00:36:11,920
哪里做三件属于？

1035
00:36:11,920 --> 00:36:12,480
就在这儿。

1036
00:36:12,480 --> 00:36:13,100
>> 我看到四个。

1037
00:36:13,100 --> 00:36:13,600
就在这儿。

1038
00:36:13,600 --> 00:36:15,660
五，六，七，八。

1039
00:36:15,660 --> 00:36:17,320
我们没有理由重复自己。

1040
00:36:17,320 --> 00:36:21,260
所以，多少步
的是，在正的条件？

1041
00:36:21,260 --> 00:36:23,870
它的n的顺序上
步骤，对不对？ ñ减1。

1042
00:36:23,870 --> 00:36:27,567
不过，我参加了一个线性数
步骤，现在我完成了。

1043
00:36:27,567 --> 00:36:28,900
所以这是最好的情况下，虽然。

1044
00:36:28,900 --> 00:36:29,983
那么最坏的情况？

1045
00:36:29,983 --> 00:36:32,730
什么8人在那边，
七均出现了下滑，

1046
00:36:32,730 --> 00:36:35,840
与一，两个人在这里，所以
该列表是真正逆转吗？

1047
00:36:35,840 --> 00:36:38,300
>> 那么，会发生什么情况确实
如果这是多少？

1048
00:36:38,300 --> 00:36:41,300
我们会做只是一对夫妇的例子。

1049
00:36:41,300 --> 00:36:49,300
如果有什么，的确，排名第八
在这里，和number--呐喊。

1050
00:36:49,300 --> 00:36:52,660

1051
00:36:52,660 --> 00:36:56,430
那么，如果确实，数
八成是一路看过来，

1052
00:36:56,430 --> 00:36:57,790
而我使用的插入排序？

1053
00:36:57,790 --> 00:36:58,290
>> 行。

1054
00:36:58,290 --> 00:37:00,280
我要求目前它在的地方。

1055
00:37:00,280 --> 00:37:03,152
但现在，seven--哪里7去了？

1056
00:37:03,152 --> 00:37:04,360
当然，它会在这里。

1057
00:37:04,360 --> 00:37:06,760
所以，我要搬到8在一个地方。

1058
00:37:06,760 --> 00:37:08,554
现在六，哪里去了？

1059
00:37:08,554 --> 00:37:09,220
好了，没事。

1060
00:37:09,220 --> 00:37:13,150
现在，我要搬到8比
的地方，和七个以上的地方，

1061
00:37:13,150 --> 00:37:14,440
然后我放下下降6。

1062
00:37:14,440 --> 00:37:16,870
>> 所以第一次，它的成本
我一步解决的事情，

1063
00:37:16,870 --> 00:37:18,570
那么它花了我两个步骤来解决的事情。

1064
00:37:18,570 --> 00:37:20,370
多少个步骤是
要采取修复

1065
00:37:20,370 --> 00:37:22,720
事情要投入五在正确的地方？

1066
00:37:22,720 --> 00:37:23,340
三。

1067
00:37:23,340 --> 00:37:29,520
因为现在我要
移动一个，两个，三个。

1068
00:37:29,520 --> 00:37:32,430
它是如何许多步骤要采取
要放四个在正确的地方？

1069
00:37:32,430 --> 00:37:36,040
4加5，加6加7。

1070
00:37:36,040 --> 00:37:40,260
>> 所以它的数学相同
我们描述的选择排序。

1071
00:37:40,260 --> 00:37:42,130
我们有这个系列
这只是增加。

1072
00:37:42,130 --> 00:37:45,650
1加2加3加4，
或者相反地，7加6

1073
00:37:45,650 --> 00:37:52,610
加5加4加起来为今天的
的目的，以n的顺序上的平方。

1074
00:37:52,610 --> 00:37:57,640
>> 因此，让我规定太那个
冒泡排序也是为n的平方。

1075
00:37:57,640 --> 00:38:01,340
因为随着冒泡排序，每个
一次我去通过列表，

1076
00:38:01,340 --> 00:38:03,100
我是在大约多少步？

1077
00:38:03,100 --> 00:38:06,260
每次我从字面上
步行到那里呢？

1078
00:38:06,260 --> 00:38:07,960
大约n步。

1079
00:38:07,960 --> 00:38:12,650
多少次，但可能我
需要经过的名单？

1080
00:38:12,650 --> 00:38:13,920
>> 好了，大致N次。

1081
00:38:13,920 --> 00:38:15,680
也许Ñ减去1，但大致n倍。

1082
00:38:15,680 --> 00:38:16,430
好了，这是为什么？

1083
00:38:16,430 --> 00:38:19,560
那么，与冒泡排序，如果
我们开始冒泡排序，

1084
00:38:19,560 --> 00:38:23,570
与列表在最坏的可能
的局面，而这又是完全

1085
00:38:23,570 --> 00:38:25,550
向后，有什么事情发生？

1086
00:38:25,550 --> 00:38:28,830
我去通过列表和数量
一个人属于一路那边。

1087
00:38:28,830 --> 00:38:33,280
>> 但随着冒泡排序，多远做一件
移动通过列表我第一遍？

1088
00:38:33,280 --> 00:38:36,620
多少个点没有，他得到
接近正确的位置？

1089
00:38:36,620 --> 00:38:37,240
只一个。

1090
00:38:37,240 --> 00:38:40,281
所以，那种如果你的理由，通过这一点，
通过该算法每一次，

1091
00:38:40,281 --> 00:38:41,880
大卫的大致采取n步。

1092
00:38:41,880 --> 00:38:44,940
但究竟有多少通行证
通过列表是它

1093
00:38:44,940 --> 00:38:49,060
要采取一泡
到它所属的左侧？

1094
00:38:49,060 --> 00:38:51,840
>> 他必须像移动，
n个空格这种方式。

1095
00:38:51,840 --> 00:38:57,960
所以才做了列表的排序，
我不得不来回走动n次。

1096
00:38:57,960 --> 00:39:01,540
而每一次，我
看着n个元素。

1097
00:39:01,540 --> 00:39:05,410
所以，做事情ñn次上
n的顺序平方。

1098
00:39:05,410 --> 00:39:07,220
>> 现在，我们将在一些人认为
短裤的

1099
00:39:07,220 --> 00:39:10,440
嵌在CS50的下一个问题
设置，另一种方法中，在这些，

1100
00:39:10,440 --> 00:39:13,490
但现在，我们只考虑
其他一些运行时间，

1101
00:39:13,490 --> 00:39:16,840
特别是如果分拣那些采取
时间一点点地下沉研究。

1102
00:39:16,840 --> 00:39:21,790
什么是我们已经看到的算法
这需要n个步骤的顺序吗？

1103
00:39:21,790 --> 00:39:27,560
>> 我应该采取直线号码
步骤，我们已经看到迄今？

1104
00:39:27,560 --> 00:39:29,350
那是什么？

1105
00:39:29,350 --> 00:39:30,480
手机目录搜索。

1106
00:39:30,480 --> 00:39:31,390
第一算法。

1107
00:39:31,390 --> 00:39:31,560
对？

1108
00:39:31,560 --> 00:39:33,650
当我们是线性
寻找麦克·史密斯？

1109
00:39:33,650 --> 00:39:34,150
的确。

1110
00:39:34,150 --> 00:39:37,180
从零一周，当我开始
翻一页的时候，

1111
00:39:37,180 --> 00:39:40,095
我甚至说，这是一种
线性感觉的算法，

1112
00:39:40,095 --> 00:39:42,720
我们不得不对那张照片
板与直红线

1113
00:39:42,720 --> 00:39:44,678
和直黄
行，那确实

1114
00:39:44,678 --> 00:39:46,810
算法是在n大O操作。

1115
00:39:46,810 --> 00:39:50,680
>> 因为找到迈克·史密斯在接受电话
的n页，在最坏的情况下的书，

1116
00:39:50,680 --> 00:39:52,422
可能要花费n步。

1117
00:39:52,422 --> 00:39:53,630
怎么样服用出席？

1118
00:39:53,630 --> 00:39:55,790
一二三四五六。

1119
00:39:55,790 --> 00:39:59,420
什么是这个运行时间
算法采取出席？

1120
00:39:59,420 --> 00:40:03,070
n个大O，因为在理论上我
在房间里点大家。

1121
00:40:03,070 --> 00:40:05,861
>> 现在，顺便说一句，怎么样
从零一周其他优化？

1122
00:40:05,861 --> 00:40:08,117
二，四，六，八，十，十二。

1123
00:40:08,117 --> 00:40:10,200
一个计算机科学家会
实现好，等待一分钟，

1124
00:40:10,200 --> 00:40:12,320
这就是顺序上
通过两个步骤除以n。

1125
00:40:12,320 --> 00:40:12,820
对？

1126
00:40:12,820 --> 00:40:14,444
因为我做两个人的时间。

1127
00:40:14,444 --> 00:40:17,015
但是，我们要忽视
那些低阶项，

1128
00:40:17,015 --> 00:40:19,140
我们只是要
扔掉除以2，

1129
00:40:19,140 --> 00:40:21,830
而只是说，正对大澳
该算法为好。

1130
00:40:21,830 --> 00:40:22,760
>> 这个如何？

1131
00:40:22,760 --> 00:40:26,170
我们将跳过其中的一些，但什么
是一种算法，是日志的n？

1132
00:40:26,170 --> 00:40:29,900
这大概需要登录n步？

1133
00:40:29,900 --> 00:40:30,870
分而治之。

1134
00:40:30,870 --> 00:40:31,369
没错。

1135
00:40:31,369 --> 00:40:33,900
就像在电话簿的例子
零一周，今天早些时候，

1136
00:40:33,900 --> 00:40:36,191
在这里我们把问题
一遍又一遍又一遍。

1137
00:40:36,191 --> 00:40:39,070
我们在上周画在黑板上
零弯曲的绿线，

1138
00:40:39,070 --> 00:40:41,460
我们说，当天是
对数的算法。

1139
00:40:41,460 --> 00:40:44,970
>> 事实上，数量步骤它
需要进行分而治之，

1140
00:40:44,970 --> 00:40:48,610
或二进制搜索，我们将开始
调用它，如在电话本，

1141
00:40:48,610 --> 00:40:50,680
是日志和步骤的顺序。

1142
00:40:50,680 --> 00:40:52,470
这是一个有点古怪的。

1143
00:40:52,470 --> 00:40:54,910
>> 有什么需要一步到位，
或者更具体地

1144
00:40:54,910 --> 00:40:56,240
的步骤的常数α

1145
00:40:56,240 --> 00:40:58,865
也许这是二，也许是三，
但计算机科学家只

1146
00:40:58,865 --> 00:41:01,423
简化了它作为1大澳，
步骤一些常数。

1147
00:41:01,423 --> 00:41:04,256
有什么东西，你能做到这一点
采取的步骤的常数α

1148
00:41:04,256 --> 00:41:08,030

1149
00:41:08,030 --> 00:41:10,930
>> 什么是拍手的运行时间？

1150
00:41:10,930 --> 00:41:11,920
恒定时间。

1151
00:41:11,920 --> 00:41:12,420
对？

1152
00:41:12,420 --> 00:41:15,490
像，什么是运行时间
做任何事情，只需一次

1153
00:41:15,490 --> 00:41:18,570
操作中，像打印˚F的Hello World。

1154
00:41:18,570 --> 00:41:24,110
可能被说成是恒定时间，
除非少的角落情况下与印刷楼

1155
00:41:24,110 --> 00:41:28,260
什么可能的运行时间
打印˚F实际上是？

1156
00:41:28,260 --> 00:41:28,790
为什么？

1157
00:41:28,790 --> 00:41:30,550
什么是在这种情况下，N测定？

1158
00:41:30,550 --> 00:41:32,251
>> 听众：[听不清]。

1159
00:41:32,251 --> 00:41:33,250
DAVID J.马兰：没错。

1160
00:41:33,250 --> 00:41:34,900
的字符数
我们要打印。

1161
00:41:34,900 --> 00:41:36,191
所以这是非常上下文敏感。

1162
00:41:36,191 --> 00:41:39,910
今天，我们已经集中了很多
信件和这里的板号。

1163
00:41:39,910 --> 00:41:43,540
但它也可能是
字符的实际字符串。

1164
00:41:43,540 --> 00:41:46,420
因此，原来还有另一种
此举将开始关心，

1165
00:41:46,420 --> 00:41:48,530
这就是相反的
大O的，可以这么说。

1166
00:41:48,530 --> 00:41:50,120
>> 这是欧米茄符号。

1167
00:41:50,120 --> 00:41:53,380
而大O表示什么，该
上界的运行时间？

1168
00:41:53,380 --> 00:41:55,580
最大限度，多少时间
可能需要的东西？

1169
00:41:55,580 --> 00:41:59,250
Omega--很抱歉，这保持未来
up--是那相反，

1170
00:41:59,250 --> 00:42:02,960
由此它的上下限
时间的东西量可能需要。

1171
00:42:02,960 --> 00:42:10,480
>> 所以。比如，什么是算法
这需要始终ñ平方的步骤？

1172
00:42:10,480 --> 00:42:15,600
那么，的算法之一，我们已经看到
今天，事实上，可能是为好。

1173
00:42:15,600 --> 00:42:16,720
选择排序。

1174
00:42:16,720 --> 00:42:18,270
选择排序是非常愚蠢的。

1175
00:42:18,270 --> 00:42:21,760
即使算法 - 对不起，连
如果数组已经排序，

1176
00:42:21,760 --> 00:42:24,150
选择排序是要
保留通过列表走

1177
00:42:24,150 --> 00:42:28,907
以确保其具有最小
元素一次又一次又一次。

1178
00:42:28,907 --> 00:42:31,740
而且即使你们人类的
观众知道，等一下，

1179
00:42:31,740 --> 00:42:33,948
你已经通过了
最小的元素，所述计算机

1180
00:42:33,948 --> 00:42:37,300
不知道，直到它看起来
通过列表中的所有方法。

1181
00:42:37,300 --> 00:42:40,240
同样，一个下界那
也可能考虑到

1182
00:42:40,240 --> 00:42:42,000
可能是线性时间。

1183
00:42:42,000 --> 00:42:48,260
>> 多少时间没有考虑到
在最好的排序n个元素

1184
00:42:48,260 --> 00:42:52,420
如果使用像冒泡排序？

1185
00:42:52,420 --> 00:42:54,280
假设你的名单已经排序。

1186
00:42:54,280 --> 00:42:56,696
我们说，冒泡排序发生在
n的平方顺序步骤。

1187
00:42:56,696 --> 00:42:59,640
但是，如果它已经排序？

1188
00:42:59,640 --> 00:43:02,310
如果你以后意识到什么
一次通过阵列

1189
00:43:02,310 --> 00:43:03,540
你所做的没有掉？

1190
00:43:03,540 --> 00:43:05,970
您是否需要继续做更多的通行证？

1191
00:43:05,970 --> 00:43:06,470
>> 第

1192
00:43:06,470 --> 00:43:10,340
因此，一个下界冒泡排序
可以说是线性的。

1193
00:43:10,340 --> 00:43:11,830
欧米茄的n。

1194
00:43:11,830 --> 00:43:14,450
我们可以看一下
这些其他人。

1195
00:43:14,450 --> 00:43:17,990
因此，让我们快速浏览一下
在短短这里的可视化

1196
00:43:17,990 --> 00:43:20,790
怎么看这些脱颖而出。

1197
00:43:20,790 --> 00:43:24,592
我要在这里下到这
网页是可在C50的网站，

1198
00:43:24,592 --> 00:43:27,550
但是这将是一个痛苦的得到工作，
由于它使用一个所谓的技术

1199
00:43:27,550 --> 00:43:30,560
Java小程序，这是一个
主要是不支持的，这些天，

1200
00:43:30,560 --> 00:43:32,730
至少是Chrome和某些其他人。

1201
00:43:32,730 --> 00:43:37,070
>> 让我继续前进，加速这一
并解释这是怎么回事。

1202
00:43:37,070 --> 00:43:40,840
这是气泡的示范
排序，第一种算法，我们看着。

1203
00:43:40,840 --> 00:43:43,950
而且它是在一个可视化的每
这些棒的代表编号。

1204
00:43:43,950 --> 00:43:45,710
越大了吧，
大的数目。

1205
00:43:45,710 --> 00:43:47,520
酒吧较小，
数字越小。

1206
00:43:47,520 --> 00:43:50,353
你可以看到在视觉上，甚至
虽然这是怎么回事超级快，

1207
00:43:50,353 --> 00:43:53,699
是红色的酒吧是像我这样的，
来回走动解决问题。

1208
00:43:53,699 --> 00:43:56,740
您可以看到更大的元素
确实冒泡到右侧，

1209
00:43:56,740 --> 00:43:59,650
和更小的元素
被向上冒泡到左侧。

1210
00:43:59,650 --> 00:44:01,870
而到这里，如果我们
实际上看起来更加紧密，

1211
00:44:01,870 --> 00:44:04,330
我们其实可以算
比较和交换的数量

1212
00:44:04,330 --> 00:44:05,350
，目前正在。

1213
00:44:05,350 --> 00:44:07,360
>> 但是，相反，让我们来看看
在第二算法

1214
00:44:07,360 --> 00:44:11,240
我们前面我们
志愿者，选择排序。

1215
00:44:11,240 --> 00:44:13,500
视觉上，它有一个
非常不同的影响。

1216
00:44:13,500 --> 00:44:16,820
但它，再次，非常直观，在
我们继续选择下一个最小

1217
00:44:16,820 --> 00:44:18,660
元素，我们得到了一点点运气。

1218
00:44:18,660 --> 00:44:20,110
这种感觉从根本上更快。

1219
00:44:20,110 --> 00:44:22,840
但是，如果我们跑这一次又一次
并再次用大量的投入，

1220
00:44:22,840 --> 00:44:26,680
我们可以看到，它的的确确
还是在n大O平方。

1221
00:44:26,680 --> 00:44:29,920
>> 让我们做一最后一个
在这里，插入排序，

1222
00:44:29,920 --> 00:44:33,180
这是第三个算法
我们看了看，并召回

1223
00:44:33,180 --> 00:44:36,700
，这其中涉及的
当它遇到这些元素，

1224
00:44:36,700 --> 00:44:39,290
但随后可能转变
事情交给腾出空间，

1225
00:44:39,290 --> 00:44:41,660
插入它们所属的元素。

1226
00:44:41,660 --> 00:44:45,330
>> 而这也最终给
最终结果。现在，所有这三个的

1227
00:44:45,330 --> 00:44:46,490
感觉蛮快的。

1228
00:44:46,490 --> 00:44:48,740
事实上，我跑了他们
在一个相当不错的剪辑。

1229
00:44:48,740 --> 00:44:52,510
但从根本上来说，它们是
很可怕的，是诚实的。

1230
00:44:52,510 --> 00:44:56,960
所有这些算法迄今
在n大O的运行方

1231
00:44:56,960 --> 00:44:59,270
需要相当多的
时间到底运行。

1232
00:44:59,270 --> 00:45:01,920
>> 事实上，我们可以看到
并认为这最后

1233
00:45:01,920 --> 00:45:04,090
如果我拉起来这第三次和最后的演示。

1234
00:45:04,090 --> 00:45:05,840
这是另一种
可视化这回事

1235
00:45:05,840 --> 00:45:08,500
显示冒泡排序在左边，
选择排序在中间，

1236
00:45:08,500 --> 00:45:13,410
有什么东西，作为我们的一个
一方面提高了早期的建议，

1237
00:45:13,410 --> 00:45:15,020
右侧归并排序。

1238
00:45:15,020 --> 00:45:16,937
分而治之
战略上的权利。

1239
00:45:16,937 --> 00:45:19,520
而这，其实就是我们
要看看在周三。

1240
00:45:19,520 --> 00:45:21,990
但是，让我们的时间，这些并行运行。

1241
00:45:21,990 --> 00:45:26,765
它是大致相同的数
元件，所有运行在同一时间。

1242
00:45:26,765 --> 00:45:30,940

1243
00:45:30,940 --> 00:45:34,440
冒泡排序VS选用
排序VS归并排序。

1244
00:45:34,440 --> 00:45:36,760
>> 现在，他们都跑
在理论的同时。

1245
00:45:36,760 --> 00:45:39,830
该CPU在运行
同样的速度，但你

1246
00:45:39,830 --> 00:45:44,014
可以感觉到多么无聊，这是
很快将成为，

1247
00:45:44,014 --> 00:45:45,930
而究竟有多快时，
我们注入了一下周

1248
00:45:45,930 --> 00:45:49,330
零的算法可以
我们加快速度。

1249
00:45:49,330 --> 00:45:51,760
>> 现在，让我们比较
这些在最后一个形式。

1250
00:45:51,760 --> 00:45:55,710
我要继续前进
到CS50的网站，在那里

1251
00:45:55,710 --> 00:45:59,020
我们今天这最后一环，
如果有人在互联网上

1252
00:45:59,020 --> 00:46:03,960
好心拼凑一个视频
抓住什么不同的排序

1253
00:46:03,960 --> 00:46:07,510
算法听起来像。

1254
00:46:07,510 --> 00:46:09,577
这是插入排序。

1255
00:46:09,577 --> 00:46:12,072
>> [哔哔]

1256
00:46:12,072 --> 00:46:13,070

1257
00:46:13,070 --> 00:46:16,850
>> 因此你申请一个频率
基于该栏杆的高度。

1258
00:46:16,850 --> 00:46:19,826
这是冒泡排序。

1259
00:46:19,826 --> 00:46:21,822
>> [扭曲的哔哔声]

1260
00:46:21,822 --> 00:46:33,299

1261
00:46:33,299 --> 00:46:45,774
>> 即将旁边is--未来
旁边is--选择排序，

1262
00:46:45,774 --> 00:46:48,820
在这里再一次，我们选择
下一个最小的元素，

1263
00:46:48,820 --> 00:46:51,820
我们可以看到它成长
从左至右。

1264
00:46:51,820 --> 00:47:01,120

1265
00:47:01,120 --> 00:47:04,000
>> 合并排序，因此，今天我们获胜者为止。

1266
00:47:04,000 --> 00:47:09,659

1267
00:47:09,659 --> 00:47:12,450
请注意，它是如何划分的事情
进入[听不清]半和宿舍。

1268
00:47:12,450 --> 00:47:17,510

1269
00:47:17,510 --> 00:47:21,660
侏儒排序，我们有没有
谈起，并创建直观

1270
00:47:21,660 --> 00:47:24,450
和audally有点
不同形状和声音。

1271
00:47:24,450 --> 00:47:27,060

1272
00:47:27,060 --> 00:47:30,160
来回，
清理东西。

1273
00:47:30,160 --> 00:47:32,230
还检查了堆排序
在这个家伙的网站。

1274
00:47:32,230 --> 00:47:36,100

1275
00:47:36,100 --> 00:47:36,810
>> 就是这样。

1276
00:47:36,810 --> 00:47:38,210
我们会看到你下一次。

1277
00:47:38,210 --> 00:47:42,647

1278
00:47:42,647 --> 00:47:48,334
>> [呼呼与音乐]

1279
00:47:48,334 --> 00:50:24,839