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

2
00:00:11,100 --> 00:00:11,490
>> DAVID J.馬蘭所有權利。

3
00:00:11,490 --> 00:00:12,170
因此，歡迎回來。

4
00:00:12,170 --> 00:00:15,180
這是CS50，和
本週三結束。

5
00:00:15,180 --> 00:00:17,770
>> 所以，記得在過去的幾個星期中，
我們已經花了相當多的

6
00:00:17,770 --> 00:00:20,820
C，對編程，語法的時間。

7
00:00:20,820 --> 00:00:24,680
這是相當正常的，如果你還在
掙扎與習題集2，

8
00:00:24,680 --> 00:00:25,950
撞你的頭靠在牆上。

9
00:00:25,950 --> 00:00:28,310
這是神秘的前瞻性的錯誤消息
和錯誤，你

10
00:00:28,310 --> 00:00:29,220
不太能追下去。

11
00:00:29,220 --> 00:00:32,310
因為，放心好了，在短短
幾個星期的時間，你會回頭看

12
00:00:32,310 --> 00:00:35,930
凱撒之類的東西，[？ V-genair？]
甚至裂紋，

13
00:00:35,930 --> 00:00:40,050
實現你來多遠
在很短的一段時間。

14
00:00:40,050 --> 00:00:43,670
因此，如果這是任何安慰，
現在掛在那裡。

15
00:00:43,670 --> 00:00:46,610
>> 今天，雖然我們開始轉型
的東西更高的水平。

16
00:00:46,610 --> 00:00:49,820
我們開始想當然
你們知道如何編程，或者

17
00:00:49,820 --> 00:00:52,090
至少開始
，舒適的水平。

18
00:00:52,090 --> 00:00:56,520
我們將開始考慮我們如何能夠
設計方案更多

19
00:00:56,520 --> 00:00:57,440
有效。

20
00:00:57,440 --> 00:01:01,090
我們如何去優化
我們的算法的效率，並

21
00:01:01,090 --> 00:01:03,110
一般解決更多
有趣的問題。

22
00:01:03,110 --> 00:01:06,850
並開始想當然地認為，
如果我們想，我們可以編寫任何

23
00:01:06,850 --> 00:01:08,350
我們心目中的例子。

24
00:01:08,350 --> 00:01:11,430
因此，我們今天不要觸摸鍵盤
任何形式的代碼。

25
00:01:11,430 --> 00:01:15,150
這將是更高的水平，
最終的問題解決。

26
00:01:15,150 --> 00:01:20,490
>> 所以到這一點，讓我提出
，下列7項

27
00:01:20,490 --> 00:01:24,290
矩形代表七個門，後面
這是一個一大堆

28
00:01:24,290 --> 00:01:26,340
號，其中數字50。

29
00:01:26,340 --> 00:01:30,470
讓我在此項目
屏幕在這裡。

30
00:01:30,470 --> 00:01:36,770
並提出，我們需要一個志願者
幫我找一個前面的數字

31
00:01:36,770 --> 00:01:38,140
看到這裡的互聯網。

32
00:01:38,140 --> 00:01:40,755
上來吧，在粉紅色的。

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

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

35
00:01:43,930 --> 00:01:44,850
>> 詹妮弗：[聽不清]

36
00:01:44,850 --> 00:01:45,170
>> 國寶，J. MALAN：對不起？

37
00:01:45,170 --> 00:01:45,860
>> 詹妮弗：詹妮弗。

38
00:01:45,860 --> 00:01:46,390
>> DAVID J.馬蘭：珍妮弗。

39
00:01:46,390 --> 00:01:46,980
所有權利，珍妮弗。

40
00:01:46,980 --> 00:01:47,630
認識你很高興。

41
00:01:47,630 --> 00:01:48,370
上來吧。

42
00:01:48,370 --> 00:01:52,430
因此，這些這裡有7個門，什麼
我希望你能在這裡為我們做的，

43
00:01:52,430 --> 00:01:56,560
在所有的同學面前，
找到我們的號碼，50。

44
00:01:56,560 --> 00:02:00,860
要找到一個號碼，你可以窺見背後
這些門通過簡單輕敲

45
00:02:00,860 --> 00:02:03,030
一個門，它
將揭示其編號。

46
00:02:03,030 --> 00:02:06,080
，讓我們看看你的速度有多快
可以找到我們的號碼，50。

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15。

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16。

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50。

53
00:02:16,530 --> 00:02:17,350
幹得漂亮。

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

55
00:02:18,040 --> 00:02:19,906
圓形，珍妮弗的掌聲。

56
00:02:19,906 --> 00:02:21,530
>> [掌聲]

57
00:02:21,530 --> 00:02:22,320
>> 好的。

58
00:02:22,320 --> 00:02:25,254
那麼，什麼是你的策略
找到的數目，50？

59
00:02:25,254 --> 00:02:27,222
>> 詹妮弗：嗯，我想，也許 - 

60
00:02:27,222 --> 00:02:27,714
[聽不清]

61
00:02:27,714 --> 00:02:28,206
>> DAVID J.馬蘭：哦。

62
00:02:28,206 --> 00:02:29,630
給它一秒鐘。

63
00:02:29,630 --> 00:02:32,420
所以，你的戰略
找到的數目，50？

64
00:02:32,420 --> 00:02:34,760
>> 珍妮花：所以我剛開始在
開始看到的第一個數字

65
00:02:34,760 --> 00:02:38,590
，然後我想，也許，如果
他們排序，我就繼續

66
00:02:38,590 --> 00:02:39,970
攻高了？

67
00:02:39,970 --> 00:02:40,140
>> DAVID J.馬蘭：“確定”。

68
00:02:40,140 --> 00:02:42,910
我們似乎已經找到
的情況下。

69
00:02:42,910 --> 00:02:45,670
雖然，讓我們剝開層層
只是一點點，你想要去的

70
00:02:45,670 --> 00:02:47,640
提前透露其他門
你也可以選擇嗎？

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> 詹妮弗：哦，親愛的。

73
00:02:51,712 --> 00:02:53,128
>> DAVID J.馬蘭：啊。

74
00:02:53,128 --> 00:02:54,280
>> 珍妮花：所以我只是很幸運。

75
00:02:54,280 --> 00:02:55,270
>> DAVID J.馬蘭：所以你很幸運。

76
00:02:55,270 --> 00:02:55,710
好的。

77
00:02:55,710 --> 00:02:56,795
所以不壞。

78
00:02:56,795 --> 00:02:58,750
但是，這是一個有趣
洞察力，對不對？

79
00:02:58,750 --> 00:03:01,870
如果你認為，你沒有得到，
著實有點幸運有。

80
00:03:01,870 --> 00:03:05,350
但是如果你假定數字
排序，你可以更精確

81
00:03:05,350 --> 00:03:08,750
如何影響
你的行為？

82
00:03:08,750 --> 00:03:11,715
>> 珍妮花：所以，如果他們進行排序，我
想，也許從最小到最大。

83
00:03:11,715 --> 00:03:11,970
>> DAVID J.馬蘭：“確定”。

84
00:03:11,970 --> 00:03:15,260
>> 詹妮弗：或者，如果這結束了
真大，然後從最大到最小。

85
00:03:15,260 --> 00:03:15,540
>> DAVID J.馬蘭：“確定”。

86
00:03:15,540 --> 00:03:18,170
所以從最大到最小，或者
從最小到最大。

87
00:03:18,170 --> 00:03:21,990
但是，讓我提出，假設您有
倒霉了，以為他們

88
00:03:21,990 --> 00:03:26,840
不，實際上，分類，有多少
這些門可能你有偷看

89
00:03:26,840 --> 00:03:28,590
落後，最壞的情況下？

90
00:03:28,590 --> 00:03:29,860
>> 珍妮花：他們所有。

91
00:03:29,860 --> 00:03:30,420
>> DAVID J.馬蘭：他們所有。

92
00:03:30,420 --> 00:03:31,740
因此，讓我們概括為n。

93
00:03:31,740 --> 00:03:34,790
恰好是7，但是讓我們更
一般說有Ñ門

94
00:03:34,790 --> 00:03:35,650
這裡的屏幕。

95
00:03:35,650 --> 00:03:40,110
因此，在最壞的情況下，你將不得不
看7門，或n門背後。

96
00:03:40,110 --> 00:03:44,140
所以這真的是，這是一個有點
今天的運氣，但它是一個真正的線性

97
00:03:44,140 --> 00:03:46,440
各種各樣的算法，即使你
那種跳繩周圍。

98
00:03:46,440 --> 00:03:47,080
這公平嗎？

99
00:03:47,080 --> 00:03:47,500
>> 珍妮花：是啊。

100
00:03:47,500 --> 00:03:50,000
>> DAVID J.馬蘭：嗯，讓我看看你的
策略的改變，如果我感動我們

101
00:03:50,000 --> 00:03:52,190
這裡我們的第二個例子
7種不同的門。

102
00:03:52,190 --> 00:03:55,240
相同的數字，但是這
時間進行排序。

103
00:03:55,240 --> 00:03:58,350
什麼是你的戰略將是，
試圖把你的頭腦是什麼

104
00:03:58,350 --> 00:03:59,310
其他的數字是 - 

105
00:03:59,310 --> 00:03:59,930
>> 詹妮弗：OK。

106
00:03:59,930 --> 00:04:02,290
>> DAVID J.馬蘭： - ？

107
00:04:02,290 --> 00:04:03,180
>> 珍妮花：讓我們開始
與第一個。

108
00:04:03,180 --> 00:04:03,540
>> DAVID J.馬蘭所有權利。

109
00:04:03,540 --> 00:04:05,190
開始的第一個。

110
00:04:05,190 --> 00:04:05,960
4。

111
00:04:05,960 --> 00:04:08,810
現在，在那裡你會去，為什麼呢？

112
00:04:08,810 --> 00:04:10,040
>> 珍妮花：4是真的小。

113
00:04:10,040 --> 00:04:12,500
所以，如果他們是那種也許最小
最大的，它應該

114
00:04:12,500 --> 00:04:13,290
的兩倍，以及 - 。

115
00:04:13,290 --> 00:04:13,670
>> DAVID J.馬蘭：“確定”。

116
00:04:13,670 --> 00:04:15,990
讓我們來看看，你覺得呢？

117
00:04:15,990 --> 00:04:19,050
>> 詹妮弗：最後一個嘗試。

118
00:04:19,050 --> 00:04:19,500
尼斯。

119
00:04:19,500 --> 00:04:20,880
>> DAVID J.馬蘭：非常好做。

120
00:04:20,880 --> 00:04:21,860
好的。

121
00:04:21,860 --> 00:04:23,010
>> [掌聲]

122
00:04:23,010 --> 00:04:24,310
>> DAVID J.馬蘭：“確定”。

123
00:04:24,310 --> 00:04:26,790
所以其實你這樣做
可怕的，因為你

124
00:04:26,790 --> 00:04:27,700
這樣做很好。

125
00:04:27,700 --> 00:04:31,150
使我們無法
使某些要點。

126
00:04:31,150 --> 00:04:32,565
因此，讓我們在這裡嘗試回滾。

127
00:04:32,565 --> 00:04:34,560
>> 詹妮弗：OK。

128
00:04:34,560 --> 00:04:35,980
>> DAVID J.馬蘭：很好
做了，儘管如此。

129
00:04:35,980 --> 00:04:39,060
所以，你開始之初，
你看到，這是4，那麼你

130
00:04:39,060 --> 00:04:40,240
移到末尾。

131
00:04:40,240 --> 00:04:42,320
但是，假設你沒有得到幸運
在那裡，假設50

132
00:04:42,320 --> 00:04:42,890
別處。

133
00:04:42,890 --> 00:04:46,190
你的第三步怎麼辦？

134
00:04:46,190 --> 00:04:47,680
>> 詹妮弗：返回到開頭。

135
00:04:47,680 --> 00:04:48,320
>> DAVID J.馬蘭：返回
到開頭。

136
00:04:48,320 --> 00:04:51,320
好了，你會一直感動
這門，這是8。

137
00:04:51,320 --> 00:04:51,660
好的。

138
00:04:51,660 --> 00:04:52,650
所以，這不是50個。

139
00:04:52,650 --> 00:04:55,380
你會在哪裡看過？

140
00:04:55,380 --> 00:04:56,720
>> 詹妮弗：如果我沒有
知道他們排序。

141
00:04:56,720 --> 00:04:57,005
>> DAVID J.馬蘭：正確。

142
00:04:57,005 --> 00:04:58,490
好吧，如果你不知道
他們進行了排序 - 

143
00:04:58,490 --> 00:04:58,700
>> 詹妮弗：哦，知道，是啊。

144
00:04:58,700 --> 00:05:00,910
>> DAVID J.馬蘭 - 但你沒有
知道其中50還在嗎？

145
00:05:00,910 --> 00:05:01,785
>> 珍妮花：只要堅持下去。

146
00:05:01,785 --> 00:05:02,130
>> DAVID J.馬蘭所有權利。

147
00:05:02,130 --> 00:05:02,520
確定。

148
00:05:02,520 --> 00:05:03,800
繼續下去。

149
00:05:03,800 --> 00:05:05,270
OK，我可以工作。

150
00:05:05,270 --> 00:05:05,610
>> 詹妮弗：OK。

151
00:05:05,610 --> 00:05:07,210
>> DAVID J.馬蘭：現在，如果你只是
要繼續下去，你叫什麼

152
00:05:07,210 --> 00:05:09,680
算法下放備份成。

153
00:05:09,680 --> 00:05:10,740
>> JENNIFER：線性 - 。

154
00:05:10,740 --> 00:05:11,820
>> DAVID J.馬蘭：這是一種線性的。

155
00:05:11,820 --> 00:05:13,480
但是，讓我提議，讓我們
我把在現場。

156
00:05:13,480 --> 00:05:14,900
讓我刷新頁面。

157
00:05:14,900 --> 00:05:17,120
同樣的號碼，同樣的安排，
同門。

158
00:05:17,120 --> 00:05:21,350
但回想起在第一天
上課的時候，我們撕了電話簿

159
00:05:21,350 --> 00:05:25,480
一半，排序，是什麼
我們的策略嗎？

160
00:05:25,480 --> 00:05:26,450
>> 詹妮弗：開始在中間。

161
00:05:26,450 --> 00:05:26,690
>> DAVID J.馬蘭：“確定”。

162
00:05:26,690 --> 00:05:27,610
因此，開始在中間。

163
00:05:27,610 --> 00:05:28,790
所以，讓我們繼續前進，和模擬。

164
00:05:28,790 --> 00:05:30,720
開始在中間
露出那扇門。

165
00:05:30,720 --> 00:05:31,660
因此，數字16。

166
00:05:31,660 --> 00:05:35,290
所以，你會強烈的傢伙都做了，
誰撕了一半，電話簿

167
00:05:35,290 --> 00:05:38,450
去下一個猜測？

168
00:05:38,450 --> 00:05:39,400
>> 詹妮弗：這半場。

169
00:05:39,400 --> 00:05:41,700
>> DAVID J.馬蘭：為什麼了吧？

170
00:05:41,700 --> 00:05:43,900
>> 詹妮弗：如果他們最小
到最大，然後50

171
00:05:43,900 --> 00:05:44,720
為此。

172
00:05:44,720 --> 00:05:44,920
>> DAVID J.馬蘭：好。

173
00:05:44,920 --> 00:05:45,390
完全合理的。

174
00:05:45,390 --> 00:05:48,380
所以像電話簿，你去
的權利，而不是左側，但在這裡

175
00:05:48,380 --> 00:05:49,500
關鍵是外賣。

176
00:05:49,500 --> 00:05:53,930
您現在可以扔掉，或撕下，
這個問題的一半，讓你不

177
00:05:53,930 --> 00:05:55,970
7門，但實際上僅有3。

178
00:05:55,970 --> 00:05:57,870
這是大約一半的
大小的問題。

179
00:05:57,870 --> 00:05:58,350
好的。

180
00:05:58,350 --> 00:06:01,890
所以，現在你將有什麼
完成後，你向右走？

181
00:06:01,890 --> 00:06:05,870
>> 珍妮花：所以16還是蠻小的，
相對於50，也許我會嘗試，

182
00:06:05,870 --> 00:06:06,700
像這一個。

183
00:06:06,700 --> 00:06:07,890
>> DAVID J.馬蘭所有權利。

184
00:06:07,890 --> 00:06:08,720
42。

185
00:06:08,720 --> 00:06:10,830
所有的權利，所以現在你叫什麼
本能告訴你嗎？

186
00:06:10,830 --> 00:06:12,100
>> 珍妮花：我可以扔掉
這一點，然後只是 - 

187
00:06:12,100 --> 00:06:12,360
>> DAVID J.馬蘭：“確定”。

188
00:06:12,360 --> 00:06:14,212
好，你可以扔掉
的左半。

189
00:06:14,212 --> 00:06:14,890
>> 詹妮弗： - ，拿起這一個。

190
00:06:14,890 --> 00:06:15,530
>> DAVID J.馬蘭的權利。

191
00:06:15,530 --> 00:06:15,760
>> 珍妮花：是啊。

192
00:06:15,760 --> 00:06:17,820
>> DAVID J.馬蘭：所以，即使它很難
或許看到，當有只

193
00:06:17,820 --> 00:06:21,320
7門，想想現在，
的一致性

194
00:06:21,320 --> 00:06:22,620
你只是算法應用。

195
00:06:22,620 --> 00:06:24,510
在以前的情況下，你做
得到幸運的，這是偉大的。

196
00:06:24,510 --> 00:06:26,540
但你沒有使用啟發式，
我想說的。

197
00:06:26,540 --> 00:06:29,150
您使用自己的直覺，
知道它的排序，如果它是相當

198
00:06:29,150 --> 00:06:31,600
小的開始，很明顯，我們已經
去了更多的權利。

199
00:06:31,600 --> 00:06:34,990
但是，從某種意義上說，你很幸運，
因為也許這是100號，

200
00:06:34,990 --> 00:06:36,220
也許50是在中間。

201
00:06:36,220 --> 00:06:37,910
也許50即使在這裡。

202
00:06:37,910 --> 00:06:40,960
>> 但你做了什麼一點點不同
這個時候，你做同樣的事情

203
00:06:40,960 --> 00:06:42,150
一遍又一遍。

204
00:06:42,150 --> 00:06:45,310
我認為，你剛才
沒有，但通過手機影響

205
00:06:45,310 --> 00:06:48,100
書中的例子，多是
算法，多

206
00:06:48,100 --> 00:06:49,930
特別少套管。

207
00:06:49,930 --> 00:06:51,620
更本能。

208
00:06:51,620 --> 00:06:57,160
因此，在一天結束的時候，怎麼會
你描述的效率

209
00:06:57,160 --> 00:07:00,530
第一種算法，你在哪裡
左到右，相對於

210
00:07:00,530 --> 00:07:03,430
第二種算法在這裡？

211
00:07:03,430 --> 00:07:06,460
>> 珍妮花：這個應該，喜歡，也許
時間減半，甚至更多，是的。

212
00:07:06,460 --> 00:07:07,320
>> DAVID J.馬蘭：好吧，也許甚至更多。

213
00:07:07,320 --> 00:07:10,150
讓我們一點點推更難。

214
00:07:10,150 --> 00:07:13,030
真的，如果我們繼續
邏輯，我們肯定減半

215
00:07:13,030 --> 00:07:15,830
本次算法的運行時間
扔掉一半的

216
00:07:15,830 --> 00:07:18,470
數字，但沒有什麼我們做下
迭代，當詹妮弗透露

217
00:07:18,470 --> 00:07:20,615
第二個數字？

218
00:07:20,615 --> 00:07:22,830
>> 門再次減半。

219
00:07:22,830 --> 00:07:25,270
然後我們做了什麼，如果
有更多的門一起玩嗎？

220
00:07:25,270 --> 00:07:27,520
我們將減半，並再次，
一遍，又一遍。

221
00:07:27,520 --> 00:07:30,420
這就像你們
站在上面的第一週

222
00:07:30,420 --> 00:07:33,000
類，你坐下的一半，一半
你坐下，你的一半

223
00:07:33,000 --> 00:07:35,440
坐了下來，直到一人獨行
站在靈魂。

224
00:07:35,440 --> 00:07:39,050
我們說的運行時間
的是，它採取的步數

225
00:07:39,050 --> 00:07:40,430
順序是怎樣的？

226
00:07:40,430 --> 00:07:41,230
>> 揚聲器1：[聽不清]

227
00:07:41,230 --> 00:07:43,970
>> DAVID J.馬蘭：所以底數2的n，
或只是更簡單，登錄的n。

228
00:07:43,970 --> 00:07:45,060
因此，對數的東西。

229
00:07:45,060 --> 00:07:48,380
和圖形是不在一條直線上
只是越來越糟，這是

230
00:07:48,380 --> 00:07:52,490
沒有這個有趣的曲線
隨著時間的推移變得如此糟糕。

231
00:07:52,490 --> 00:07:53,910
因此，讓我們保持這種想法。

232
00:07:53,910 --> 00:07:54,690
讓我們感謝珍妮弗。

233
00:07:54,690 --> 00:07:56,150
感謝這麼多的最多。

234
00:07:56,150 --> 00:07:57,400
一秒鐘。

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
沒有檯燈，但我們
確實有CS50應力球。

237
00:08:02,925 --> 00:08:03,420
>> 詹妮弗：耶。

238
00:08:03,420 --> 00:08:04,410
>> DAVID J.馬蘭：好的，在這裡。

239
00:08:04,410 --> 00:08:06,545
謝謝你承擔
應力在這裡。

240
00:08:06,545 --> 00:08:07,350
好的。

241
00:08:07,350 --> 00:08:10,620
所以，讓我們來看看，如果我們現在不能
正式這一點。

242
00:08:10,620 --> 00:08:14,820
所以，再一次，我們剛剛做的是
基本上我們做同樣的事情

243
00:08:14,820 --> 00:08:16,660
在第一個星期。

244
00:08:16,660 --> 00:08:23,780
但而不是結束，只是一個線性
算法，這是我們描繪

245
00:08:23,780 --> 00:08:27,210
以前這條直線，
據此，如果我們把一個門

246
00:08:27,210 --> 00:08:29,610
屏幕上，然後珍妮弗會
不得不看，可能，

247
00:08:29,610 --> 00:08:30,600
後面多了一個門。

248
00:08:30,600 --> 00:08:33,490
如果我們把兩個門，她可能有
看看後面兩個門。

249
00:08:33,490 --> 00:08:35,990
>> ，所以這種線性
的大小之間的關係

250
00:08:35,990 --> 00:08:39,059
問題，比方說，在x軸，和
它需要的時間量

251
00:08:39,059 --> 00:08:40,440
解決在y。

252
00:08:40,440 --> 00:08:43,330
但畫面我被影射
早期是這樣的綠線。

253
00:08:43,330 --> 00:08:45,970
綠色故意的，因為
它只是感覺好多了。

254
00:08:45,970 --> 00:08:49,790
在理論上，算法，當我們做到了
電話簿，當我們做到了

255
00:08:49,790 --> 00:08:52,420
你們計數對方，
在第二種情況下，當珍妮弗只是

256
00:08:52,420 --> 00:08:55,250
做了它在這裡，它是
從根本上更好。

257
00:08:55,250 --> 00:08:57,180
因為它不只是快兩倍。

258
00:08:57,180 --> 00:08:58,870
它甚至不是快四倍。

259
00:08:58,870 --> 00:09:03,290
這完全依賴於什麼
輸入的大小，到底有多少

260
00:09:03,290 --> 00:09:05,220
最終步驟了。

261
00:09:05,220 --> 00:09:08,040
>> 所以這個簡單的想法，我們都拿了
為電話簿授予，

262
00:09:08,040 --> 00:09:10,200
可以類似地應用
這樣的東西。

263
00:09:10,200 --> 00:09:12,380
這可能是更隨便
被稱為，因為您可能

264
00:09:12,380 --> 00:09:13,940
可以想像，分而治之。

265
00:09:13,940 --> 00:09:16,390
當然，沒有什麼不同，我們做了什麼，
電話簿。

266
00:09:16,390 --> 00:09:18,300
>> 但偽代碼，召回，是這樣的。

267
00:09:18,300 --> 00:09:21,800
因此，我們不會做這個了，但記得
第一個星期，我們都站了起來

268
00:09:21,800 --> 00:09:25,140
然後你的一半坐了下來，一半
你坐下，你的一半坐了下來。

269
00:09:25,140 --> 00:09:29,280
該算法在一個實施
有點作弊的方式，在那，

270
00:09:29,280 --> 00:09:32,870
不只是我一個人計數，
從根本上說，更有效地。

271
00:09:32,870 --> 00:09:35,830
在這種情況下，我被利用
二次資源。

272
00:09:35,830 --> 00:09:39,470
排序的，多個CPU，多動腦筋，
多聰明的人

273
00:09:39,470 --> 00:09:42,740
房間幫助我得到的東西
線性的東西

274
00:09:42,740 --> 00:09:45,190
對數，從東西
紅色到綠色的東西。

275
00:09:45,190 --> 00:09:48,650
>> 但是，在這種情況下，珍妮弗單靠
從根本上改善後

276
00:09:48,650 --> 00:09:52,370
她的第一個算法的性能，
再次，只是想有點困難。

277
00:09:52,370 --> 00:09:56,650
而現在，當談到時間來實現
這些東西，搞清楚

278
00:09:56,650 --> 00:10:00,670
什麼行代碼，你能寫出這樣
，你可以重複一遍，

279
00:10:00,670 --> 00:10:03,350
一遍，又一遍，排序
在循環的方式。

280
00:10:03,350 --> 00:10:06,370
因為你不會有
做的第一件奢侈品，像珍妮弗，

281
00:10:06,370 --> 00:10:10,460
如果只是有一大堆，說
嗯，如果這第一個數字是4，

282
00:10:10,460 --> 00:10:11,800
讓我跳方式結束。

283
00:10:11,800 --> 00:10:14,180
哦，如果這個數字太大了，
讓我回到隨意移動

284
00:10:14,180 --> 00:10:15,220
到第二元件。

285
00:10:15,220 --> 00:10:18,210
你會發現，它將會是一個很大
難以形式化我們人類

286
00:10:18,210 --> 00:10:21,270
想當然是非常合理的
啟發式方法，但只有一台計算機是

287
00:10:21,270 --> 00:10:23,260
會做你告訴它做。

288
00:10:23,260 --> 00:10:25,280
>> 現在，這具有非常有趣
的影響。

289
00:10:25,280 --> 00:10:29,950
此圖意味著排序排序
壓倒視覺，但是請注意，在那裡

290
00:10:29,950 --> 00:10:32,230
在該曲線圖中的直線是什麼？

291
00:10:32,230 --> 00:10:35,330
哪裡是線性圖
我們稱之為ň？

292
00:10:35,330 --> 00:10:37,580
嗯，這是那種朝下方
這幅畫，是吧？

293
00:10:37,580 --> 00:10:40,500
因此，我們所做的是我們排序
地圖的x軸和

294
00:10:40,500 --> 00:10:44,780
y軸設法得到一個什麼樣的感覺
其他類型的曲線的樣子。

295
00:10:44,780 --> 00:10:47,760
>> 和具體的數學
今天的表達式將不那麼重要

296
00:10:47,760 --> 00:10:52,440
不多，但發現有很多
算法遠不如

297
00:10:52,440 --> 00:10:53,470
東西是線性的。

298
00:10:53,470 --> 00:10:55,410
事實上，N立方看起來很糟糕。

299
00:10:55,410 --> 00:10:58,400
2 n個看起來很糟糕。
Ñ​​平方看起來很糟糕。

300
00:10:58,400 --> 00:11:01,630
，我們將看到一些人
可能會在今天的現實。

301
00:11:01,630 --> 00:11:05,430
日誌N不那麼糟糕的感覺，但
比n底數2的n。

302
00:11:05,430 --> 00:11:08,080
但你知道，它會更
更驚人的，如果詹妮弗，或者如果我們

303
00:11:08,080 --> 00:11:12,910
第一個星期，想出了
東西是n的日誌記錄。

304
00:11:12,910 --> 00:11:15,880
>> 因此，換句話說，這整個
可能的解決方案的範圍

305
00:11:15,880 --> 00:11:18,570
問題，但即使在這裡，請注意
會發生什麼。

306
00:11:18,570 --> 00:11:22,910
當我縮小，這些曲線
會被證明是絕對

307
00:11:22,910 --> 00:11:26,630
現在屏幕上的最差？

308
00:11:26,630 --> 00:11:28,680
因此n的立方小艾
糟糕的時刻。

309
00:11:28,680 --> 00:11:32,470
但是，如果我們放大，看到更多的
x和y軸，誰去

310
00:11:32,470 --> 00:11:34,550
最終主宰？

311
00:11:34,550 --> 00:11:37,120
因此，它實際上原來，2
n，並且可以算出這個只是通過

312
00:11:37,120 --> 00:11:39,990
堵在一些越來越大
數字，你會看到2到

313
00:11:39,990 --> 00:11:42,070
N，事實上，獲取更大的快得多。

314
00:11:42,070 --> 00:11:45,530
如果我們真的縮小，2
絕對吸Ń算法。

315
00:11:45,530 --> 00:11:48,170
我的意思是要採取
相當多的時間

316
00:11:48,170 --> 00:11:49,460
電腦上翻騰通過。

317
00:11:49,460 --> 00:11:52,500
>> 但是，你會看到隨著時間的推移，特別是
甚至與未來問題集

318
00:11:52,500 --> 00:11:55,600
最後的項目，為您的數據
集變大了，好嗎？

319
00:11:55,600 --> 00:11:58,300
即使是在Facebook的第一個版本，
作為朋友，

320
00:11:58,300 --> 00:12:01,840
註冊用戶的數量得到了大，
您可以排序的電話呢

321
00:12:01,840 --> 00:12:05,530
執行線性搜索的東西，
還是一個很簡單的排序

322
00:12:05,530 --> 00:12:07,030
算法，今天我們會看到。

323
00:12:07,030 --> 00:12:09,280
你必須開始思考更難
這些問題更難。

324
00:12:09,280 --> 00:12:12,070
和類型的問題的地方，如
Facebook和谷歌，微軟，

325
00:12:12,070 --> 00:12:16,350
和其他工作，正是這些
大數據排序排序問題

326
00:12:16,350 --> 00:12:18,530
這些天越來越多。

327
00:12:18,530 --> 00:12:18,900
>> 好的。

328
00:12:18,900 --> 00:12:23,800
，所以詹妮弗的成功，第二
算法，坦率地說，她的確令人驚訝

329
00:12:23,800 --> 00:12:26,110
以及第一次，但我們
寫我的運氣，讓我們

330
00:12:26,110 --> 00:12:27,000
可這一點。

331
00:12:27,000 --> 00:12:30,970
在第二種情況下，她利用
算法，又重複了一遍，

332
00:12:30,970 --> 00:12:34,670
再次，但她認為理所當然的一
我們允許若干假設

333
00:12:34,670 --> 00:12:39,370
她，但她利用一些細節
第二，她沒有足夠的時間

334
00:12:39,370 --> 00:12:39,840
第一次。

335
00:12:39,840 --> 00:12:41,800
這是什麼？

336
00:12:41,800 --> 00:12:43,050
>> 列表排序。

337
00:12:43,050 --> 00:12:46,350
所以只要列表排序，我們
聲稱，珍妮弗是能夠做到的

338
00:12:46,350 --> 00:12:47,480
從根本上更好。

339
00:12:47,480 --> 00:12:51,450
7門，是的，是不是很有趣，
但假設我們700萬門。

340
00:12:51,450 --> 00:12:54,080
n的日誌是一定要去
執行很多，很多

341
00:12:54,080 --> 00:12:55,610
從長遠來看快。

342
00:12:55,610 --> 00:12:58,880
但她必須有
她門的排序。

343
00:12:58,880 --> 00:13:02,320
現在，我帶著這樣做的自由
事先在電腦屏幕上

344
00:13:02,320 --> 00:13:05,160
在這裡，但假設珍妮弗
不得不做自己？

345
00:13:05,160 --> 00:13:10,120
假設門問題
表示數據庫中的數據，或

346
00:13:10,120 --> 00:13:14,260
為Facebook註冊的朋友，或
任何在互聯網上的網頁

347
00:13:14,260 --> 00:13:16,880
可能需要不同的網站
索引或搜索過。

348
00:13:16,880 --> 00:13:20,940
>> 假設你剛剛有了原始數據
設置和它留給你的，或

349
00:13:20,940 --> 00:13:23,010
珍妮弗做排序？

350
00:13:23,010 --> 00:13:26,950
，而是需要我們回答
的問題，好了，多少時間

351
00:13:26,950 --> 00:13:31,080
珍妮弗，甚至我會採取
這些數字進行排序，提前讓

352
00:13:31,080 --> 00:13:32,680
她能利用？

353
00:13:32,680 --> 00:13:32,880
對嗎？

354
00:13:32,880 --> 00:13:36,620
因為言下之意，當然是
如果它需要我相當長的一段時間排序

355
00:13:36,620 --> 00:13:40,800
數字，到底誰在乎你
這麼快可以找到一個像50，

356
00:13:40,800 --> 00:13:44,850
作為在詹妮弗的情況下，如果我們多
不堪重負的總時間量

357
00:13:44,850 --> 00:13:46,920
了通過分揀事前事中？

358
00:13:46,920 --> 00:13:49,320
>> 因此，讓我們來看看，如果我們不能
這裡繪製圖片。

359
00:13:49,320 --> 00:13:51,370
我有一大堆的壓力
球，如果有幫助

360
00:13:51,370 --> 00:13:52,270
打破這兒的冰。

361
00:13:52,270 --> 00:13:55,690
如果你不介意，我們
需要七個志願者 - 

362
00:13:55,690 --> 00:13:57,060
，“確定”。

363
00:13:57,060 --> 00:13:57,240
哇。

364
00:13:57,240 --> 00:13:59,250
因此，我們不必花
檯燈，它似乎。

365
00:13:59,250 --> 00:13:59,690
好的。

366
00:13:59,690 --> 00:14:01,530
因此，如何對你們兩個在前面。

367
00:14:01,530 --> 00:14:04,160
怎麼你們倆在後面。

368
00:14:04,160 --> 00:14:04,870
所以這是四個。

369
00:14:04,870 --> 00:14:09,890
你怎麼樣在前面
五，六，七。

370
00:14:09,890 --> 00:14:10,320
就在那裡。

371
00:14:10,320 --> 00:14:13,260
您的朋友的指點你，
所以你得到的獎品。

372
00:14:13,260 --> 00:14:13,700
>> 好的。

373
00:14:13,700 --> 00:14:14,410
上來吧。

374
00:14:14,410 --> 00:14:17,120
為什麼不，我們有你
你們來就在這裡。

375
00:14:17,120 --> 00:14:18,960
我去給你們每人一個。

376
00:14:18,960 --> 00:14:22,150
繼續前進，安排自己
相同的是什麼

377
00:14:22,150 --> 00:14:25,180
在屏幕上描繪。

378
00:14:25,180 --> 00:14:26,530
>> [插入聲音]

379
00:14:26,530 --> 00:14:28,160
>> DAVID J.馬蘭：OOP，對不起。

380
00:14:28,160 --> 00:14:30,210
問題。

381
00:14:30,210 --> 00:14:32,180
好的。

382
00:14:32,180 --> 00:14:32,750
那麼，在這裡，我們去。

383
00:14:32,750 --> 00:14:34,180
5號。

384
00:14:34,180 --> 00:14:35,136
6號。

385
00:14:35,136 --> 00:14:37,770
一，二，三，四，
五，六，七。

386
00:14:37,770 --> 00:14:39,410
哦，這是很尷尬。

387
00:14:39,410 --> 00:14:41,210
>> 揚聲器2：我剛剛得到一個 - 。

388
00:14:41,210 --> 00:14:41,900
>> DAVID J.馬蘭：處理好。

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

390
00:14:43,130 --> 00:14:44,611
謝謝您的參與。

391
00:14:44,611 --> 00:14:47,200
>> [掌聲]

392
00:14:47,200 --> 00:14:48,580
>> 確定。

393
00:14:48,580 --> 00:14:48,860
好的。

394
00:14:48,860 --> 00:14:51,970
因此，我們有四，二，六，
一，三，七，五。

395
00:14:51,970 --> 00:14:56,010
完美的，所以我們有七個志願者
在這裡誰是寬度相等的

396
00:14:56,010 --> 00:14:57,430
我們玩的數組
與早期的。

397
00:14:57,430 --> 00:14:59,470
我選擇了七個原因
這將是剛

398
00:14:59,470 --> 00:15:00,840
方便一點點。

399
00:15:00,840 --> 00:15:04,400
我要首先提出，
我們梳理這七名志願者。

400
00:15:04,400 --> 00:15:06,786
如果你想，首先，
打招呼，雖然。

401
00:15:06,786 --> 00:15:08,970
由於這將是一個
尷尬幾分鐘。

402
00:15:08,970 --> 00:15:10,370
介紹一下自己。

403
00:15:10,370 --> 00:15:10,980
>> GRACE：嗨，我是格雷斯。

404
00:15:10,980 --> 00:15:14,190
我是一個大二在利維瑞特大廈。

405
00:15:14,190 --> 00:15:14,620
>> 布蘭森：你好。

406
00:15:14,620 --> 00:15:15,620
我布蘭森。

407
00:15:15,620 --> 00:15:16,920
我是一個大一的焊接。

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> GABE：你好。

410
00:15:20,230 --> 00:15:21,040
我加布。

411
00:15:21,040 --> 00:15:22,300
我是一個小輩在Cabot。

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> 尼爾：我是尼爾。

414
00:15:25,980 --> 00:15:29,090
我一大一馬修斯。

415
00:15:29,090 --> 00:15:29,550
>> 傑森：我是傑森。

416
00:15:29,550 --> 00:15:32,816
我是一個大一格里諾。

417
00:15:32,816 --> 00:15:33,700
>> MIKE：我是麥克。

418
00:15:33,700 --> 00:15:37,360
我一大一灰色。

419
00:15:37,360 --> 00:15:37,990
>> JESS：我是傑西。

420
00:15:37,990 --> 00:15:40,313
我是一個大二萊弗里特。

421
00:15:40,313 --> 00:15:41,300
>> DAVID J.馬蘭：優秀。

422
00:15:41,300 --> 00:15:41,850
好的。

423
00:15:41,850 --> 00:15:44,190
嗯，謝謝你給我們所有的
這裡的志願者迄今。

424
00:15:44,190 --> 00:15:47,110
現在手頭的挑戰會
是這些傢伙排序，但隨後

425
00:15:47,110 --> 00:15:50,250
我們要覺得有點
我們如何有效地實際上努力

426
00:15:50,250 --> 00:15:51,110
排序。

427
00:15:51,110 --> 00:15:52,580
所以，讓我們先試試這個。

428
00:15:52,580 --> 00:15:55,970
你們可以看到對方的號碼
只是把周圍的角落。

429
00:15:55,970 --> 00:15:59,380
來吧，採取了幾秒鐘，
從最小的排序自己

430
00:15:59,380 --> 00:16:01,240
左到最大的在右邊。

431
00:16:01,240 --> 00:16:02,490
去。

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> 確定。

434
00:16:07,530 --> 00:16:08,030
好。

435
00:16:08,030 --> 00:16:09,370
這真是混賬快。

436
00:16:09,370 --> 00:16:14,040
現在有人在這裡，究竟是什麼算法
這些傢伙的應用呢？

437
00:16:14,040 --> 00:16:14,900
>> 揚聲器1：最偉大的。

438
00:16:14,900 --> 00:16:15,000
>> DAVID J.馬蘭：“確定”。

439
00:16:15,000 --> 00:16:18,070
最小到最大還真有幾分
的目標，但我不知道這是

440
00:16:18,070 --> 00:16:18,890
一個真正的算法。

441
00:16:18,890 --> 00:16:21,810
最小到最大不告訴
我一步一步做什麼。

442
00:16:21,810 --> 00:16:22,833
是嗎？

443
00:16:22,833 --> 00:16:24,083
>> 揚聲器1：[聽不清]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> DAVID J.馬蘭：“確定”。

446
00:16:26,280 --> 00:16:28,920
所以，如果你看到一個人小於
你的電話號碼，然後移動到

447
00:16:28,920 --> 00:16:29,680
他們的權利。

448
00:16:29,680 --> 00:16:32,800
因此，現在越來越多的表現，
更像是一個算法，因為你

449
00:16:32,800 --> 00:16:35,410
可以說，如果這樣，那麼這個。

450
00:16:35,410 --> 00:16:37,050
因此，我們有某種
條件結構。

451
00:16:37,050 --> 00:16:39,700
這些傢伙似乎做那幾個
次，因為一些你有點感動

452
00:16:39,700 --> 00:16:40,420
的距離。

453
00:16:40,420 --> 00:16:43,410
所以大概是有某種
循環在他們的頭腦中去。

454
00:16:43,410 --> 00:16:44,610
>> 但是，讓我們盡量正規化，。

455
00:16:44,610 --> 00:16:47,540
如果你們能重置回
這種佈置。

456
00:16:47,540 --> 00:16:50,650
讓我們來看看如果我們不能正式確定這是一個
位，然後問這個問題，只是

457
00:16:50,650 --> 00:16:51,580
效率如何？

458
00:16:51,580 --> 00:16:54,220
當然，當我們這樣做時速度比較慢，
它會感覺一樣好

459
00:16:54,220 --> 00:16:57,210
一種算法，但讓我們來看看，如果我們能
把我們的手指的精確步驟。

460
00:16:57,210 --> 00:16:58,670
>> 所以，你們倆有四個和兩個。

461
00:16:58,670 --> 00:17:01,020
或您正確或不正確的順序？

462
00:17:01,020 --> 00:17:01,900
顯然不正確。

463
00:17:01,900 --> 00:17:02,710
所以我們交換。

464
00:17:02,710 --> 00:17:05,170
現在，我要移開
這裡說，四到六。

465
00:17:05,170 --> 00:17:06,240
你是正確的或不正確的？

466
00:17:06,240 --> 00:17:06,599
>> GABE：正確。

467
00:17:06,599 --> 00:17:07,180
>> DAVID J.馬蘭：正確。

468
00:17:07,180 --> 00:17:08,300
六一？

469
00:17:08,300 --> 00:17:08,609
不。

470
00:17:08,609 --> 00:17:09,630
交換。

471
00:17:09,630 --> 00:17:10,490
所以這是兩個互換。

472
00:17:10,490 --> 00:17:11,710
六，三個？

473
00:17:11,710 --> 00:17:11,980
不。

474
00:17:11,980 --> 00:17:13,000
交換。

475
00:17:13,000 --> 00:17:13,930
六，七？

476
00:17:13,930 --> 00:17:14,630
看起來不錯。

477
00:17:14,630 --> 00:17:15,396
7個和5？

478
00:17:15,396 --> 00:17:16,150
>> JESS：[聽不清]

479
00:17:16,150 --> 00:17:17,089
>> DAVID J.馬蘭：OK，交換。

480
00:17:17,089 --> 00:17:19,770
和排序。

481
00:17:19,770 --> 00:17:19,980
好的。

482
00:17:19,980 --> 00:17:21,440
所以，很顯然不是，對不對？

483
00:17:21,440 --> 00:17:22,470
於是有更多的事情。

484
00:17:22,470 --> 00:17:24,920
不過，說實在的是，這些傢伙，即使
只是本能。

485
00:17:24,920 --> 00:17:25,450
不停地移動。

486
00:17:25,450 --> 00:17:27,710
他們不只是停下來，他們一旦
糾正一個問題。

487
00:17:27,710 --> 00:17:27,839
所以。

488
00:17:27,839 --> 00:17:29,390
事實上，我將不得不
做同樣的事情。

489
00:17:29,390 --> 00:17:32,720
我要倒帶回來排序
此問題的​​開始，

490
00:17:32,720 --> 00:17:35,630
或此數組的開始
人，讓我們開始打電話給他們。

491
00:17:35,630 --> 00:17:38,366
>> 現在應該做些什麼算法
在第二遍呢？

492
00:17:38,366 --> 00:17:39,220
>> 揚聲器1：同樣的事情。

493
00:17:39,220 --> 00:17:39,940
>> DAVID J.馬蘭：同樣的事情。

494
00:17:39,940 --> 00:17:41,460
而這一點，我開始喜歡，對不對？

495
00:17:41,460 --> 00:17:44,720
只要你可以找到自己做
同樣的事情一遍又一遍，這是

496
00:17:44,720 --> 00:17:47,890
變得更像一個算法，
人類的本能。

497
00:17:47,890 --> 00:17:48,680
>> 所以，現在，在這裡，我們又來了。

498
00:17:48,680 --> 00:17:49,870
兩個和四個？

499
00:17:49,870 --> 00:17:50,220
號

500
00:17:50,220 --> 00:17:51,050
四之一？

501
00:17:51,050 --> 00:17:53,380
嗯，確實有一些
工作尚待完成。

502
00:17:53,380 --> 00:17:53,620
三？

503
00:17:53,620 --> 00:17:54,572
好。

504
00:17:54,572 --> 00:17:56,000
四和六？

505
00:17:56,000 --> 00:17:58,380
六，五？

506
00:17:58,380 --> 00:17:59,470
六，七？

507
00:17:59,470 --> 00:18:00,970
OK，現在，完成。

508
00:18:00,970 --> 00:18:01,550
OK，沒。

509
00:18:01,550 --> 00:18:02,710
我必須回去。

510
00:18:02,710 --> 00:18:05,130
>> 所以，現在，再次，我們正在做這
有點刻意。

511
00:18:05,130 --> 00:18:08,700
而現在，只是一個大腦
執行該算法。

512
00:18:08,700 --> 00:18:10,290
一個CPU，如果你願意。

513
00:18:10,290 --> 00:18:13,090
坦率地說，這是唯一的資源
我們將有機會獲得。

514
00:18:13,090 --> 00:18:16,280
一旦我們做回一個鍵盤
和我們有一些像C

515
00:18:16,280 --> 00:18:19,600
處置中，我們只寫一個程序
可以做一件事的時間。

516
00:18:19,600 --> 00:18:22,900
然而，這些傢伙剛才，我們
利用他們的集體腦力

517
00:18:22,900 --> 00:18:24,180
像你這樣的傢伙做週零。

518
00:18:24,180 --> 00:18:24,980
所以，讓我們繼續這樣做。

519
00:18:24,980 --> 00:18:26,260
>> 兩個和一個。

520
00:18:26,260 --> 00:18:26,945
二和三。

521
00:18:26,945 --> 00:18:27,460
三和四。

522
00:18:27,460 --> 00:18:28,310
四和五。

523
00:18:28,310 --> 00:18:28,620
五和六。

524
00:18:28,620 --> 00:18:30,510
六，七。

525
00:18:30,510 --> 00:18:31,880
做了什麼？

526
00:18:31,880 --> 00:18:34,560
所以我，但讓我打
魔鬼代言人。

527
00:18:34,560 --> 00:18:37,950
我的電腦誰只是
發了一通通過這個數組

528
00:18:37,950 --> 00:18:40,225
人，知道我做的嗎？

529
00:18:40,225 --> 00:18:40,670
>> 揚聲器1號

530
00:18:40,670 --> 00:18:41,050
>> DAVID J.馬蘭：那麼，為什麼呢？

531
00:18:41,050 --> 00:18:46,900
我會怎麼做，以
果斷地結束，我做？

532
00:18:46,900 --> 00:18:48,230
大概一個多通。

533
00:18:48,230 --> 00:18:48,430
對嗎？

534
00:18:48,430 --> 00:18:51,760
因為我知道從先前
通的是，我糾正了錯誤。

535
00:18:51,760 --> 00:18:53,920
這意味著，也許有
另一個錯誤

536
00:18:53,920 --> 00:18:54,840
我需要糾正。

537
00:18:54,840 --> 00:18:58,680
所以我只能確定經複捲，
然後檢查，一到兩個，兩個

538
00:18:58,680 --> 00:19:00,940
三，三，四，四，五，
五，六，六，七。

539
00:19:00,940 --> 00:19:02,510
OK，我現在沒工作。

540
00:19:02,510 --> 00:19:05,990
>> 我可以肯定記得，我沒
工作像變量一樣的東西，

541
00:19:05,990 --> 00:19:06,975
我喜歡一個int。

542
00:19:06,975 --> 00:19:12,490
叫它掉，如果掉的是有一次我0
在這裡，它從0開始，然後

543
00:19:12,490 --> 00:19:15,520
我也只是愚蠢繼續下去
來回，再次檢查，

544
00:19:15,520 --> 00:19:16,450
一遍，又一遍，對不對？

545
00:19:16,450 --> 00:19:18,450
因為你在一些被卡住
一種無限循環。

546
00:19:18,450 --> 00:19:21,250
所以，只要有0掉期，
我們可以聲稱這

547
00:19:21,250 --> 00:19:23,810
算法確實是完整的。

548
00:19:23,810 --> 00:19:25,400
>> 現在，讓我們把名稱。

549
00:19:25,400 --> 00:19:28,930
我建議我們只是算法
實現東西叫做泡沫

550
00:19:28,930 --> 00:19:32,800
形式的，在這個意義上，作為這種已知
是一種更大的數字

551
00:19:32,800 --> 00:19:37,990
泡自己的方式到頂部，漲幅高達
到的數字數組的末尾。

552
00:19:37,990 --> 00:19:40,270
但這種算法是如何高效？

553
00:19:40,270 --> 00:19:44,600
多少步了我的身體有
例如，採取排序這些

554
00:19:44,600 --> 00:19:45,850
七人？

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> 四，五？

557
00:19:49,550 --> 00:19:51,420
OK，太多的是最終
要得到答案。

558
00:19:51,420 --> 00:19:54,960
但即便如此，具體數量
是不是非常有趣。

559
00:19:54,960 --> 00:19:56,670
設為n概括。

560
00:19:56,670 --> 00:20:00,520
所以，如果我已經N多人在這裡，他們
，排序，在隨機順序

561
00:20:00,520 --> 00:20:02,180
開始的時候，在那個原來的順序。

562
00:20:02,180 --> 00:20:04,910
嗯，我有多少步
第一遍？

563
00:20:04,910 --> 00:20:09,810
這是一，二，三，四，五，
六，他們七人，所以

564
00:20:09,810 --> 00:20:13,670
七，六 - ，所以這是Ñ
減去一個步驟的第一次。

565
00:20:13,670 --> 00:20:16,280
>> 現在，我有多少步
我倒帶時要採取？

566
00:20:16,280 --> 00:20:19,310
好吧，我們實際上可以增加一倍，如果
我們真的很想，但現在，我

567
00:20:19,310 --> 00:20:22,300
只是會說，所有的權利，
另一個n減1。

568
00:20:22,300 --> 00:20:25,240
那麼N減1是會得到
惱人跟踪，讓我們

569
00:20:25,240 --> 00:20:26,400
只是小幅圍捕。

570
00:20:26,400 --> 00:20:27,770
所以2n個。

571
00:20:27,770 --> 00:20:29,310
因此，14個步驟，給予或採取。

572
00:20:29,310 --> 00:20:31,930
>> 我多少次
一個步下一次？

573
00:20:31,930 --> 00:20:33,740
嗯，這是3N。

574
00:20:33,740 --> 00:20:34,510
真的。

575
00:20:34,510 --> 00:20:37,920
現在，在最壞的情況下，為
例如，我有多少次

576
00:20:37,920 --> 00:20:41,730
來回走了，反反复复，
執行該算法，交換

577
00:20:41,730 --> 00:20:44,620
每個合格的人，大約有嗎？

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
它實際上是Ñ平方，對不對？

580
00:20:50,010 --> 00:20:53,000
>> 因為在最壞的情況下，可以種
想想這個直觀的，

581
00:20:53,000 --> 00:20:54,800
即使它可能需要一點
位時間的下沉。

582
00:20:54,800 --> 00:20:57,590
在最壞的情況下，會是什麼
七人的模樣，在

583
00:20:57,590 --> 00:21:00,230
協議條款
他們的人數？

584
00:21:00,230 --> 00:21:01,460
完全倒退，對不對？

585
00:21:01,460 --> 00:21:02,815
只是模擬，
你叫什麼名字呢？

586
00:21:02,815 --> 00:21:03,360
>> MIKE：麥克。

587
00:21:03,360 --> 00:21:03,640
>> DAVID J.馬蘭：邁克？

588
00:21:03,640 --> 00:21:08,100
OK，邁克，你只是和我一起過
這裡只是一秒鐘？

589
00:21:08,100 --> 00:21:08,880
事實上，沒有。

590
00:21:08,880 --> 00:21:10,150
對不起邁克，讓我們倒帶。

591
00:21:10,150 --> 00:21:10,910
你叫什麼名字呢？

592
00:21:10,910 --> 00:21:11,180
>> 尼爾：尼爾。

593
00:21:11,180 --> 00:21:11,640
>> DAVID J.馬蘭：尼爾。

594
00:21:11,640 --> 00:21:13,750
OK，尼爾，你來
我，如果你不介意的。

595
00:21:13,750 --> 00:21:17,150
所以我要提出的，只是
簡單起見，尼爾現在是在他

596
00:21:17,150 --> 00:21:18,510
最壞情況下。

597
00:21:18,510 --> 00:21:20,720
但記得我是如何實現
我的算法。

598
00:21:20,720 --> 00:21:24,530
我比較，比較，比較，
比較，比較哦。

599
00:21:24,530 --> 00:21:26,640
現在，這些傢伙都出來了
秩序，所以我修復。

600
00:21:26,640 --> 00:21:27,980
所以你們交換。

601
00:21:27,980 --> 00:21:31,630
但現在，考慮如何更遠
尼爾一定要去嗎？

602
00:21:31,630 --> 00:21:32,690
它大致Ñ。

603
00:21:32,690 --> 00:21:33,570
你知道，這實際上並不ñ。

604
00:21:33,570 --> 00:21:36,040
這就像，N減1，但我得到
惱火跟踪的小

605
00:21:36,040 --> 00:21:37,550
號，所以我們只叫了N。

606
00:21:37,550 --> 00:21:42,860
>> 所以，如果尼爾移動一步最大限度每個
時間，移動尼爾一步，

607
00:21:42,860 --> 00:21:46,580
我必須做出這個非常繁瑣的通
來回，這大概是

608
00:21:46,580 --> 00:21:52,080
這樣，n個步驟，共n次，
因為它是要帶我

609
00:21:52,080 --> 00:21:55,820
許多步驟尼爾所有
他所屬的地方。

610
00:21:55,820 --> 00:21:58,620
更別說其他人，如果你們
都亂序。

611
00:21:58,620 --> 00:22:01,100
>> 所以姑且稱之為的冒泡排序Ñ平方。

612
00:22:01,100 --> 00:22:04,860
這個算法的運行時間，
該算法的性能，

613
00:22:04,860 --> 00:22:07,120
該算法的效率，
我們只是描述

614
00:22:07,120 --> 00:22:08,800
一般為n的平方。

615
00:22:08,800 --> 00:22:11,650
這是很好的，因為我可以做
同樣的例子，八人，九

616
00:22:11,650 --> 00:22:15,450
人，一萬人，
答案是不會改變的。

617
00:22:15,450 --> 00:22:18,870
>> 所以，如果你們不介意，讓我們
重置你開始的地方。

618
00:22:18,870 --> 00:22:22,510
讓我們嘗試其他兩種方法
如果我們不能從根本上做

619
00:22:22,510 --> 00:22:23,820
比這更好的。

620
00:22:23,820 --> 00:22:27,130
所以這個時候，我要建議
一種不同的算法。

621
00:22:27,130 --> 00:22:29,950
這是非常聰明的，我們最後一次，
你們是正確的，有

622
00:22:29,950 --> 00:22:32,470
權利只是一種本能
的交換兩兩。

623
00:22:32,470 --> 00:22:36,500
但是，如果我真的就想辦法
簡單地說，我的目標是移動

624
00:22:36,500 --> 00:22:39,800
這樣的小數字，
推動所有的大號碼

625
00:22:39,800 --> 00:22:43,030
這樣，為什麼不我只是做，在
最天真的可能的方式，看看我

626
00:22:43,030 --> 00:22:45,730
比什麼是可以做的更好
相當複雜的算法？

627
00:22:45,730 --> 00:22:46,620
>> 所以，讓我們來看看。

628
00:22:46,620 --> 00:22:48,940
四是一個非常小的數字，所以我
要離開你有片刻。

629
00:22:48,940 --> 00:22:50,610
哦，2號，甚至更好。

630
00:22:50,610 --> 00:22:52,230
所以，你可以只是一步
一會兒嗎？

631
00:22:52,230 --> 00:22:55,670
這是我目前最小的編號
候選人，我會記住

632
00:22:55,670 --> 00:22:57,000
與一樣，一個變量。

633
00:22:57,000 --> 00:22:57,930
但我會繼續檢查。

634
00:22:57,930 --> 00:22:59,890
是否有某人的
號碼是小？

635
00:22:59,890 --> 00:23:00,460
六，沒有。

636
00:23:00,460 --> 00:23:01,390
哦，還有尼爾再次。

637
00:23:01,390 --> 00:23:04,050
>> 所以我打算推你回來
排序的概念。

638
00:23:04,050 --> 00:23:05,120
尼爾將挺身而出。

639
00:23:05,120 --> 00:23:08,440
而現在，變量，我使用
跟踪誰擁有最小

640
00:23:08,440 --> 00:23:11,390
號碼被更新為包含
尼爾的位置。

641
00:23:11,390 --> 00:23:12,110
好吧，讓我們來看看。

642
00:23:12,110 --> 00:23:13,960
三，七，五。

643
00:23:13,960 --> 00:23:15,590
好吧，我知道尼爾是最小的。

644
00:23:15,590 --> 00:23:18,110
什麼是最簡單的事情
我現在要做的嗎？

645
00:23:18,110 --> 00:23:21,410
只是，我不會浪費我的時間
冒泡尼爾一個點到左邊。

646
00:23:21,410 --> 00:23:25,350
為什麼不讓我在那裡他將尼爾
屬於當然，這是在哪裡？

647
00:23:25,350 --> 00:23:26,160
>> 所有的方式在開始時。

648
00:23:26,160 --> 00:23:27,720
所以，尼爾，跟我來。

649
00:23:27,720 --> 00:23:28,910
你叫什麼名字呢？

650
00:23:28,910 --> 00:23:29,310
>> GRACE：格雷斯。

651
00:23:29,310 --> 00:23:29,710
>> DAVID J.馬蘭：格雷斯。

652
00:23:29,710 --> 00:23:29,920
確定。

653
00:23:29,920 --> 00:23:32,490
所以，雍容，不幸的是，你
樣的方式。

654
00:23:32,490 --> 00:23:34,290
那麼，我們如何解決這個問題？

655
00:23:34,290 --> 00:23:34,490
對嗎？

656
00:23:34,490 --> 00:23:37,500
如果這是一個數組，有
只有七個地點。

657
00:23:37,500 --> 00:23:40,830
回想一下，與Rob，我們談到
聲明年齡，我們只有一個

658
00:23:40,830 --> 00:23:41,740
有限數量的年齡？

659
00:23:41,740 --> 00:23:42,535
同樣的想法在這裡。

660
00:23:42,535 --> 00:23:44,300
我們只有有限數量的整數。

661
00:23:44,300 --> 00:23:47,590
格雷斯是怎麼樣的，在我們的
這樣，那麼我們如何解決呢？

662
00:23:47,590 --> 00:23:49,555
>> 最簡單的方法是什麼樣的，
格雷斯，對不起。

663
00:23:49,555 --> 00:23:51,870
你要去走了過來
所以我們可以騰出空間。

664
00:23:51,870 --> 00:23:55,290
現在，如果你想想，也許
我們只是使問題變得更糟。

665
00:23:55,290 --> 00:23:58,510
也許我們這樣做，因為如果
格雷斯是在正確的地方？

666
00:23:58,510 --> 00:24:01,730
但我們知道，她不是，因為
否則，她會一直

667
00:24:01,730 --> 00:24:03,980
而不是站在
尼爾在這個時候，對不對？

668
00:24:03,980 --> 00:24:05,550
我們已經檢查了她的電話號碼。

669
00:24:05,550 --> 00:24:05,770
>> 好的。

670
00:24:05,770 --> 00:24:09,110
所以，現在，尼爾在正確的地方，
我可以做一個輕微的優化。

671
00:24:09,110 --> 00:24:11,740
在接下來的一分鐘，我要忽略
尼爾都在一起，所以不

672
00:24:11,740 --> 00:24:15,280
浪費他的時間，或意外
他換到錯誤的地方。

673
00:24:15,280 --> 00:24:17,805
所以，現在，我該如何尋找下一個
最小的元素嗎？

674
00:24:17,805 --> 00:24:18,480
二。

675
00:24:18,480 --> 00:24:20,225
這是一個不錯的數字，如果
你要挺身而出，

676
00:24:20,225 --> 00:24:21,100
我會永遠記得你。

677
00:24:21,100 --> 00:24:21,980
六，沒有好。

678
00:24:21,980 --> 00:24:24,820
四，三，七，五，沒有好處。

679
00:24:24,820 --> 00:24:26,800
因此，讓我打動你
你的正確的地方。

680
00:24:26,800 --> 00:24:28,470
而我們只是很幸運這個時候。

681
00:24:28,470 --> 00:24:31,350
>> 現在，我要忽視這些
兩個傢伙，現在更盡一

682
00:24:31,350 --> 00:24:32,260
通過這一點。

683
00:24:32,260 --> 00:24:33,490
六，是一個非常小的數目。

684
00:24:33,490 --> 00:24:34,300
加油前進。

685
00:24:34,300 --> 00:24:35,220
哦，對不起。

686
00:24:35,220 --> 00:24:37,640
Grace的號碼比較好，
所以踩前進。

687
00:24:37,640 --> 00:24:38,260
四。

688
00:24:38,260 --> 00:24:39,120
對不起，格雷斯。

689
00:24:39,120 --> 00:24:39,950
你回去吧。

690
00:24:39,950 --> 00:24:41,550
三是更好的。

691
00:24:41,550 --> 00:24:42,290
七。

692
00:24:42,290 --> 00:24:42,720
五。

693
00:24:42,720 --> 00:24:43,550
現在，你叫什麼名字呢？

694
00:24:43,550 --> 00:24:44,000
>> 傑森：賈森。

695
00:24:44,000 --> 00:24:44,420
>> DAVID J.馬蘭：賈森。

696
00:24:44,420 --> 00:24:47,050
因此，Jason是現在最小的
我的元素。

697
00:24:47,050 --> 00:24:49,160
他要去哪裡去了？

698
00:24:49,160 --> 00:24:50,380
那麼，六是。

699
00:24:50,380 --> 00:24:51,210
你的名字嗎？

700
00:24:51,210 --> 00:24:51,710
>> GABE：加布。

701
00:24:51,710 --> 00:24:52,340
>> DAVID J.馬蘭：加布。

702
00:24:52,340 --> 00:24:53,220
加布的方式。

703
00:24:53,220 --> 00:24:54,640
什麼是最簡單的事情嗎？

704
00:24:54,640 --> 00:24:58,390
交換這兩個傢伙，然後繼續。

705
00:24:58,390 --> 00:24:59,020
所以，現在讓我們來看看。

706
00:24:59,020 --> 00:25:00,170
誰是最小的？

707
00:25:00,170 --> 00:25:01,030
四。

708
00:25:01,030 --> 00:25:01,990
讓我只是一種作弊。

709
00:25:01,990 --> 00:25:03,090
五是將是最小的。

710
00:25:03,090 --> 00:25:05,220
接下來，我覺得，如果你想一步
未來，我有什麼做

711
00:25:05,220 --> 00:25:06,820
這些傢伙，加布？

712
00:25:06,820 --> 00:25:08,450
再交換。

713
00:25:08,450 --> 00:25:10,740
所以，現在，仍有小幅的順序。

714
00:25:10,740 --> 00:25:14,140
我發現加布是最小的，所以
我彈出他，將你們。

715
00:25:14,140 --> 00:25:15,190
並完成。

716
00:25:15,190 --> 00:25:17,200
>> 因此，答案是一樣的。

717
00:25:17,200 --> 00:25:18,600
最終的結果是一樣的。

718
00:25:18,600 --> 00:25:22,730
這兩種算法哪
是更好嗎？

719
00:25:22,730 --> 00:25:23,500
第二個，我聽說了。

720
00:25:23,500 --> 00:25:24,252
為什麼呢？

721
00:25:24,252 --> 00:25:25,900
>> 揚聲器3：n個步驟[聽不清]。

722
00:25:25,900 --> 00:25:27,600
>> DAVID J.馬蘭：這是最多的n個步驟。

723
00:25:27,600 --> 00:25:28,490
有趣。

724
00:25:28,490 --> 00:25:30,610
那麼是什麼關係嗎？

725
00:25:30,610 --> 00:25:33,630
那麼我怎麼找到
最小的元素？

726
00:25:33,630 --> 00:25:37,060
我不得不採取了多少步
找到最小的元素？

727
00:25:37,060 --> 00:25:39,220
我一看所有的方式
到底對不對？

728
00:25:39,220 --> 00:25:41,530
由於在這最壞的情況下，什麼
如果尼爾在這裡？

729
00:25:41,530 --> 00:25:45,700
因此，只要找到最小的元素
我需要n個步驟，或n減1。

730
00:25:45,700 --> 00:25:46,100
但是，“確定”。

731
00:25:46,100 --> 00:25:46,980
所以修復尼爾。

732
00:25:46,980 --> 00:25:48,740
請記住，一分鐘左右前。

733
00:25:48,740 --> 00:25:51,680
>> 但我怎麼找了下
最小的元素？

734
00:25:51,680 --> 00:25:54,830
這是N減1，或n減去2真的，
從步驟的數量。

735
00:25:54,830 --> 00:25:55,440
這樣就OK了。

736
00:25:55,440 --> 00:25:57,390
所以，我沒有Ñ零下2。

737
00:25:57,390 --> 00:25:57,600
好的。

738
00:25:57,600 --> 00:25:59,130
所以，感覺更好一點。

739
00:25:59,130 --> 00:25:59,730
好的。

740
00:25:59,730 --> 00:26:03,270
下一次多少步
找到3號？

741
00:26:03,270 --> 00:26:04,420
所以N減去4。

742
00:26:04,420 --> 00:26:07,670
因此，它的下降，少一個
在每個迭代步驟。

743
00:26:07,670 --> 00:26:08,740
因此，這並不感覺更好，對不對？

744
00:26:08,740 --> 00:26:13,450
如果最後一次大約是N倍N
這個時候它的N減1，加N減

745
00:26:13,450 --> 00:26:16,500
2，加N減去3，加上n
零下4，點，點，點。

746
00:26:16,500 --> 00:26:18,750
但是，如果你還記得你高中
課本，一點作弊

747
00:26:18,750 --> 00:26:24,380
表背面有公式，如果
你這一系列的數字加起來，

748
00:26:24,380 --> 00:26:31,280
總步數是什麼
要我把這裡嗎？

749
00:26:31,280 --> 00:26:36,580
>> 這是其中的一個，喜歡，正零下
1，次數n，再除以2。

750
00:26:36,580 --> 00:26:39,040
因此，讓我看看，如果我可以拉
這件事只是一瞬間。

751
00:26:39,040 --> 00:26:42,230
再次，我是那種四捨五入一些
編號只是為了讓我們的生活變得簡單，

752
00:26:42,230 --> 00:26:47,830
但我記得，它的東西一樣，如果
我做N減去1件事情，那麼n減去

753
00:26:47,830 --> 00:26:53,570
2，那麼n減去3，大致
超過2，這樣的事情，如果我

754
00:26:53,570 --> 00:26:55,510
乘了這一點，
實際上n的方陣。

755
00:26:55,510 --> 00:26:58,940
這不是感覺太美好了。
Ñ​​零下n次2。

756
00:26:58,940 --> 00:27:00,350
>> 但這裡的東西。

757
00:27:00,350 --> 00:27:03,720
在計算機科學中，出現問題的時候
開始變得有趣的是，當n

758
00:27:03,720 --> 00:27:04,700
變得非常大。

759
00:27:04,700 --> 00:27:08,110
當n變得非常大，這
這些價值觀是要主宰一切

760
00:27:08,110 --> 00:27:09,750
其他人呢？

761
00:27:09,750 --> 00:27:10,990
這是一種n個平方，對不對？

762
00:27:10,990 --> 00:27:13,340
是的，除以2，是相當不錯的。

763
00:27:13,340 --> 00:27:16,740
但是，如果你正在談論數十億
條數據，或萬億

764
00:27:16,740 --> 00:27:18,700
條數據，OK，所以
你快兩倍。

765
00:27:18,700 --> 00:27:22,440
但誰真正關心，如果大的數字，
如果這個因素是什麼得到

766
00:27:22,440 --> 00:27:23,040
越做越大。

767
00:27:23,040 --> 00:27:25,990
當然，它使更多的
差異比這個傢伙。

768
00:27:25,990 --> 00:27:29,120
所以，即使你們是正確的，
第二種算法，我們叫它

769
00:27:29,120 --> 00:27:32,970
選擇排序，是在現實世界中，
潛在快一點，因為我

770
00:27:32,970 --> 00:27:35,360
採取越來越少
每一個步驟的時間。

771
00:27:35,360 --> 00:27:37,340
>> 這不是真正的從根本更快。

772
00:27:37,340 --> 00:27:41,430
因為如果我們真正發揮出
大的n值，結束時

773
00:27:41,430 --> 00:27:44,750
一天，n足夠大，它仍然是
要感到相當緩慢。

774
00:27:44,750 --> 00:27:46,770
好吧，讓我一個
在這最後一關。

775
00:27:46,770 --> 00:27:48,920
這是我所說的
選擇排序。

776
00:27:48,920 --> 00:27:51,040
你們可以自己復位
最後一次？

777
00:27:51,040 --> 00:27:53,550
而在這最後的情況下，我要去
提出的東西

778
00:27:53,550 --> 00:27:54,970
所謂插入排序。

779
00:27:54,970 --> 00:27:57,470
插入排序，概念，
有點不同。

780
00:27:57,470 --> 00:28:00,980
>> 而不是去來回
我選擇最小的元素，

781
00:28:00,980 --> 00:28:05,030
只是去處理這些
傢伙，我遇到他們，並插入

782
00:28:05,030 --> 00:28:06,850
他們到他們的正確的地方。

783
00:28:06,850 --> 00:28:10,160
所以，我只是要開始與Grace，
我看到，她是第四個。

784
00:28:10,160 --> 00:28:11,720
數四屬於哪裡？

785
00:28:11,720 --> 00:28:14,940
我還沒有開始任何排序，
所以格雷斯獲得呆在那裡。

786
00:28:14,940 --> 00:28:18,355
現在，我稍後會要求，如果你能
走一步到您的權利，這

787
00:28:18,355 --> 00:28:21,650
我的排序名單，這是我的
未分類的剩餘列表。

788
00:28:21,650 --> 00:28:23,260
所以，現在我要繼續下，
你叫什麼名字呢？

789
00:28:23,260 --> 00:28:23,700
>> 布蘭森布蘭森：

790
00:28:23,700 --> 00:28:24,150
>> DAVID J.馬蘭：布蘭森。

791
00:28:24,150 --> 00:28:25,375
因此，布蘭森是2號。

792
00:28:25,375 --> 00:28:27,490
所以，我要帶你
出了一會兒。

793
00:28:27,490 --> 00:28:30,940
而現在，你屬於
在這個數組？

794
00:28:30,940 --> 00:28:32,360
所以恩典的權利。

795
00:28:32,360 --> 00:28:35,670
所以，我們又是一種使
格雷斯在這裡做了很多工作。

796
00:28:35,670 --> 00:28:37,290
我們在哪裡把你嗎？

797
00:28:37,290 --> 00:28:40,120
因此，我們要滑動你
離開了，有插入布蘭森。

798
00:28:40,120 --> 00:28:41,680
但現在我要求
你們完成。

799
00:28:41,680 --> 00:28:43,240
但是請注意，我沒有使用額外的空間。

800
00:28:43,240 --> 00:28:45,130
它仍然是2個元素
在這裡，在這裡。

801
00:28:45,130 --> 00:28:47,910
總數組的大小為7，因此我
不要欺騙你，沒事吧？

802
00:28:47,910 --> 00:28:51,950
>> 所以現在我們有加布在這裡，
六，你屬於哪裡？

803
00:28:51,950 --> 00:28:52,650
你很幸運了。

804
00:28:52,650 --> 00:28:53,820
所以，你呆在那裡。

805
00:28:53,820 --> 00:28:57,210
只取一小步的權利
只是為了讓你排序。

806
00:28:57,210 --> 00:29:00,520
現在我們有尼爾再次，數字
1，你在哪裡去了？

807
00:29:00,520 --> 00:29:03,540
現在是我們將開始看到
該算法中，雖然在第一

808
00:29:03,540 --> 00:29:05,950
一目了然，感覺很聰明，看
什麼是即將發生。

809
00:29:05,950 --> 00:29:07,370
如果你能挺身而出。

810
00:29:07,370 --> 00:29:09,260
>> 在哪裡，我們希望把尼爾？

811
00:29:09,260 --> 00:29:11,830
所以，很顯然在這裡，所以如何
我們得到尼爾？

812
00:29:11,830 --> 00:29:12,970
讓我們做到這一步一步的。

813
00:29:12,970 --> 00:29:15,620
加布，你需要去哪裡呢？

814
00:29:15,620 --> 00:29:19,590
沒錯，所以採取一大步，
或兩個半步驟，以使

815
00:29:19,590 --> 00:29:20,820
那邊的一個步驟。

816
00:29:20,820 --> 00:29:21,750
格雷斯，你去哪裡？

817
00:29:21,750 --> 00:29:22,510
好。

818
00:29:22,510 --> 00:29:23,500
所以又邁進了一步。

819
00:29:23,500 --> 00:29:24,960
最後，布蘭森？

820
00:29:24,960 --> 00:29:25,460
另一個步驟。

821
00:29:25,460 --> 00:29:27,190
現在我們可以把尼爾到位。

822
00:29:27,190 --> 00:29:28,440
>> 所以，現在，繼續這樣的邏輯。

823
00:29:28,440 --> 00:29:32,420
即使我們不轉移尼爾
過來，過來，過來，把他

824
00:29:32,420 --> 00:29:36,420
他走到哪裡，在最壞的情況下，
下一個數字，我們可能會遇到能

825
00:29:36,420 --> 00:29:42,220
的數量，例如，有一個數
零，那麼我們要全部轉移

826
00:29:42,220 --> 00:29:42,730
這些傢伙。

827
00:29:42,730 --> 00:29:44,950
假設有一個數字，負
一個，那麼我們必須轉移

828
00:29:44,950 --> 00:29:46,080
所有的這些傢伙。

829
00:29:46,080 --> 00:29:48,500
所以我們真的只是一種翻轉
周圍的問題，這樣，我們

830
00:29:48,500 --> 00:29:52,620
從轉移的費用
選拔過程，所以插入

831
00:29:52,620 --> 00:29:56,930
過程中，如你們剛剛
移動大致Ñ減去的東西

832
00:29:56,930 --> 00:29:57,940
步數。

833
00:29:57,940 --> 00:30:01,200
而且，步數只打算
增加，因為我選擇更多的數字，

834
00:30:01,200 --> 00:30:04,730
如果我要繼續推搡你們
回來，回來，回來。

835
00:30:04,730 --> 00:30:08,320
>> 所以現在傷心的事情是所有這些
算法是n的平方。

836
00:30:08,320 --> 00:30:10,570
讓我們繼續前進，感謝這些
傢伙，這些位可視化

837
00:30:10,570 --> 00:30:11,090
是不同的。

838
00:30:11,090 --> 00:30:12,312
非常出色。

839
00:30:12,312 --> 00:30:14,120
>> [掌聲]

840
00:30:14,120 --> 00:30:15,030
>> 好的。

841
00:30:15,030 --> 00:30:16,280
你去那裡。

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
感謝 - 

844
00:30:18,470 --> 00:30:19,190
>> 布蘭森：[聽不清]保持的數字。

845
00:30:19,190 --> 00:30:21,990
>> DAVID J.馬蘭：沒有，你可能
保持數字。

846
00:30:21,990 --> 00:30:23,440
好的。

847
00:30:23,440 --> 00:30:24,100
幹得漂亮。

848
00:30:24,100 --> 00:30:25,300
好的。

849
00:30:25,300 --> 00:30:30,510
因此，讓我們來看看，如果我們現在不能總結
更為迅速，並且視覺上更

850
00:30:30,510 --> 00:30:33,410
正是剛剛發生了什麼
在這裡，如下所示。

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
我要繼續前進
拉起Firefox瀏覽器。

853
00:30:38,770 --> 00:30:41,310
我們會鏈接這個示範
本課程的網站。

854
00:30:41,310 --> 00:30:43,870
Java是一個有點惱人獲得工作
在某些瀏覽器，這些天。

855
00:30:43,870 --> 00:30:46,760
所以，如果你在家裡玩這個，
意識到你可能需要使用Firefox

856
00:30:46,760 --> 00:30:47,990
得到它的工作。

857
00:30:47,990 --> 00:30:50,440
什麼，我要做的事情與此
示範以下。

858
00:30:50,440 --> 00:30:54,875
>> 在底部，我有一大堆
菜單選項，包括一個起點和一個

859
00:30:54,875 --> 00:30:55,840
“停止”按鈕。

860
00:30:55,840 --> 00:30:59,450
另外，順便說一句，似乎是一個
在這些程序中的錯誤，讓你

861
00:30:59,450 --> 00:31:03,720
不能真正看到啟動或停止
按鈕，除非你按住Command或Alt

862
00:31:03,720 --> 00:31:06,560
加和變焦，好奇
顯示更多的按鈕。

863
00:31:06,560 --> 00:31:09,090
因此，只是供參考，如果你玩
這個在家。

864
00:31:09,090 --> 00:31:12,870
現在，我要單擊“開始”，在短短
此刻，在指定的延遲後，

865
00:31:12,870 --> 00:31:16,810
只是一樣，在這裡，200毫秒
所以我們可以看到發生了什麼。

866
00:31:16,810 --> 00:31:20,180
>> 因此，我要求這是一個可視化
第一算法

867
00:31:20,180 --> 00:31:23,730
這些傢伙確實，冒泡排序，即
我們交換成對的人。

868
00:31:23,730 --> 00:31:27,490
此可視化的關鍵洞察力
是矩形條的高度

869
00:31:27,490 --> 00:31:30,510
表示的數量的大小。

870
00:31:30,510 --> 00:31:32,210
所以酒吧更高，
數字越大。

871
00:31:32,210 --> 00:31:33,680
較短的酒吧，數字越小。

872
00:31:33,680 --> 00:31:38,630
如果你注意到了，我們正在經歷
在此算法中，在第一次迭代

873
00:31:38,630 --> 00:31:42,620
交換大和小的數字，所以
少數至上

874
00:31:42,620 --> 00:31:44,280
大數量的權利。

875
00:31:44,280 --> 00:31:48,770
>> 而只要我們得到數組的末尾
多數量比七，我們

876
00:31:48,770 --> 00:31:49,900
要回去的開始。

877
00:31:49,900 --> 00:31:51,140
和預測。

878
00:31:51,140 --> 00:31:54,860
在最左邊，那個小傢伙是怎麼回事
交換到一邊，這

879
00:31:54,860 --> 00:31:56,010
過程重複。

880
00:31:56,010 --> 00:31:59,450
現在，這個可視化很快就會
無聊，所以讓我繼續前進，停止

881
00:31:59,450 --> 00:32:04,170
它，改變延遲東西
只是為了得到更快現在，感覺

882
00:32:04,170 --> 00:32:05,060
該算法。

883
00:32:05,060 --> 00:32:07,840
>> 因此，即使我已經加快了，這是
就像我的處理器升級，買

884
00:32:07,840 --> 00:32:08,580
一台新電腦。

885
00:32:08,580 --> 00:32:12,980
我還沒有從根本上改變了我
算法，但你確實可以看到更多的

886
00:32:12,980 --> 00:32:16,800
顯然比人類大
數字冒泡到頂部，

887
00:32:16,800 --> 00:32:20,900
小的數字冒泡
下到谷底。

888
00:32:20,900 --> 00:32:22,390
現在這個東西在這裡排序。

889
00:32:22,390 --> 00:32:25,260
順便說一句，在廣場，有
只是有一些簿記

890
00:32:25,260 --> 00:32:28,010
幫你算多少次比較，
或有多少掉期

891
00:32:28,010 --> 00:32:28,950
實際上已經完成。

892
00:32:28,950 --> 00:32:30,750
>> 好吧，讓我們嘗試之一
我們看到別人。

893
00:32:30,750 --> 00:32:37,116
讓我點擊這裡冒泡排序，
讓我選擇，這整個網頁

894
00:32:37,116 --> 00:32:38,936
是一點點馬車。

895
00:32:38,936 --> 00:32:41,155
讓我們接受的風險
並再次運行它。

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
我們去那裡。

898
00:32:45,030 --> 00:32:47,180
因此，讓我們做選擇排序。

899
00:32:47,180 --> 00:32:49,140
我不知道為什麼菜單
出現在那裡。

900
00:32:49,140 --> 00:32:54,070
讓我們放大到解決這個問題
錯誤，改到50。

901
00:32:54,070 --> 00:32:56,020
啊，讓我們真正做到
是更快的。

902
00:32:56,020 --> 00:32:59,160
5毫秒左右開始。

903
00:32:59,160 --> 00:33:00,470
>> 因此，這是選擇排序。

904
00:33:00,470 --> 00:33:03,070
如此反复，想想我們
與人類在這裡做了。

905
00:33:03,070 --> 00:33:08,490
我們經歷的數組，並選擇
最小的元素，

906
00:33:08,490 --> 00:33:09,250
一遍，又一遍。

907
00:33:09,250 --> 00:33:11,110
現在，我要求還是蠻不錯的。

908
00:33:11,110 --> 00:33:15,010
它仍然為n的平方，給予或採取，
但它是在現實世界中，位

909
00:33:15,010 --> 00:33:18,280
更快，因為我​​確實服用
略少的每個步驟。

910
00:33:18,280 --> 00:33:19,800
但我們只是在談論什麼？

911
00:33:19,800 --> 00:33:21,830
可能40或酒吧在這裡？

912
00:33:21,830 --> 00:33:23,200
我們不是在談論4000萬美元。

913
00:33:23,200 --> 00:33:27,430
所以它不是完全清楚的，我認為
確實是一個顯著的收益。

914
00:33:27,430 --> 00:33:32,530
>> 現在讓我回去，並改變我們的
第三個算法，它被選擇

915
00:33:32,530 --> 00:33:33,180
插入排序。

916
00:33:33,180 --> 00:33:36,380
而現在它是真的馬車，因為
菜單實在不應該是出現了下滑。

917
00:33:36,380 --> 00:33:40,840
所以，現在，我們將在這裡滾動備份
並啟動此算法。

918
00:33:40,840 --> 00:33:43,270
吶喊，啟動和停止。

919
00:33:43,270 --> 00:33:47,160
所以這一種有一個漂亮的圖案
它，讓我們再次

920
00:33:47,160 --> 00:33:50,240
插入人體，或在
這種情況下，酒吧

921
00:33:50,240 --> 00:33:52,620
其適當的位置。

922
00:33:52,620 --> 00:33:55,430
它之前已經完成
我轉頭。

923
00:33:55,430 --> 00:33:58,940
但是這一個，並且，在理論上，
仍然為n的平方。

924
00:33:58,940 --> 00:34:01,430
>> 因此，讓我們來看看，如果我們不能概括
這些如下。

925
00:34:01,430 --> 00:34:04,750
我要繼續前進，只是為了給
我們一個共同的說話方式

926
00:34:04,750 --> 00:34:08,489
這些事情，讓我介紹一下
這裡只是一個符號位。

927
00:34:08,489 --> 00:34:12,480
你看到的東西叫大
O，因為它實際上就是一個大

928
00:34:12,480 --> 00:34:16,320
O.這是一種方式，一台計算機
科學家或數學家甚至使用

929
00:34:16,320 --> 00:34:19,230
描述的運行時間
的一些算法。

930
00:34:19,230 --> 00:34:21,400
多少步驟，它實際上採取？

931
00:34:21,400 --> 00:34:25,080
>> 現在，我要自己難堪
我的筆跡，在這裡只是一個瞬間。

932
00:34:25,080 --> 00:34:29,020
但是，讓我繼續前進，說
這將是大O字在這裡。

933
00:34:29,020 --> 00:34:33,610
讓我介紹另一個
符號，資本歐米茄。

934
00:34:33,610 --> 00:34:37,080
歐米茄是相反的，
從本質上講，大澳鑑於大O

935
00:34:37,080 --> 00:34:40,790
的手段，在最壞的情況下，多少時間
可能一些算法，

936
00:34:40,790 --> 00:34:43,480
以n，ω是要
多少時間可能

937
00:34:43,480 --> 00:34:45,409
在最好的情況下採取。

938
00:34:45,409 --> 00:34:48,090
我們會看到我們所說的
最好的情況下，在短短的時刻。

939
00:34:48,090 --> 00:34:49,940
>> 所以，讓我們先從簡單的東西。

940
00:34:49,940 --> 00:34:54,719
讓我開始線性搜索。

941
00:34:54,719 --> 00:34:55,679
所以，不排序。

942
00:34:55,679 --> 00:34:58,000
我們稱這個線性搜索。

943
00:34:58,000 --> 00:35:01,140
而現在，做一點
表了這一點。

944
00:35:01,140 --> 00:35:06,600
而現在，線性搜索的情況下，
在最壞的情況下，多少步

945
00:35:06,600 --> 00:35:11,770
它要帶我找到一個
任意選擇的數？

946
00:35:11,770 --> 00:35:14,540
還有的N總門
或n總數。

947
00:35:14,540 --> 00:35:15,940
最壞的情況。

948
00:35:15,940 --> 00:35:18,800
我將不得不多少步
找到在一個數組中的數字50

949
00:35:18,800 --> 00:35:20,830
n個門？

950
00:35:20,830 --> 00:35:21,410
為什麼？

951
00:35:21,410 --> 00:35:23,680
因為它可能是所有
一路過來到年底。

952
00:35:23,680 --> 00:35:27,120
因此，就像珍妮弗遇到，
50號是一路過來，所以在

953
00:35:27,120 --> 00:35:30,760
最壞的情況下的線性搜索
大O的n，我們會說。

954
00:35:30,760 --> 00:35:33,430
>> 怎麼樣最好的情況下，
如果你很幸運嗎？

955
00:35:33,430 --> 00:35:36,200
只是要一步一步，
或恆定的步數。

956
00:35:36,200 --> 00:35:37,830
因此，我們將介紹為1。

957
00:35:37,830 --> 00:35:39,010
因此，這是相當不錯的。

958
00:35:39,010 --> 00:35:41,210
現在，如果我們做的東西
喜歡二進制搜索？

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
因此，二進制搜索，在最壞的
的情況下，花了多少時間？

961
00:35:47,846 --> 00:35:49,250
>> [插入聲音]

962
00:35:49,250 --> 00:35:51,310
>> DAVID J.馬蘭：其實我
聽到一對夫婦的地方。

963
00:35:51,310 --> 00:35:56,390
因此，它實際上登錄N，給予或採取
因為我們把一半的列表中

964
00:35:56,390 --> 00:36:00,730
一遍，一遍，又一遍，我們能夠
發現，最終，該值，

965
00:36:00,730 --> 00:36:04,750
如果它的存在，但有一個catch。

966
00:36:04,750 --> 00:36:08,590
什麼是假設，我們必須
想當然二進制搜索？

967
00:36:08,590 --> 00:36:09,700
進行排序。

968
00:36:09,700 --> 00:36:12,770
它不排序，可以分割的東西
半一遍又一遍，你

969
00:36:12,770 --> 00:36:15,490
向左走，你可以去，
你可以去左右，但你

970
00:36:15,490 --> 00:36:18,070
不會找到的元素，如果
列表中，因為沒有排序

971
00:36:18,070 --> 00:36:18,790
你可能會錯過它。

972
00:36:18,790 --> 00:36:22,120
因為你的啟發，去左
或向右將是有缺陷的，如果它是

973
00:36:22,120 --> 00:36:23,420
確實沒有排序。

974
00:36:23,420 --> 00:36:26,110
因此，有一個隱藏的成本有點
使用這樣的事情。

975
00:36:26,110 --> 00:36:29,250
>> 現在，讓我們進入我們的排序
算法搜索 - 

976
00:36:29,250 --> 00:36:31,140
哦，居然讓我們去在這個空白。

977
00:36:31,140 --> 00:36:33,190
在最好的情況下，二進制搜索？

978
00:36:33,190 --> 00:36:36,290
這也是1，如果它恰好是
在中間的陣列，或

979
00:36:36,290 --> 00:36:37,810
中間的電話簿。

980
00:36:37,810 --> 00:36:39,710
現在，讓我們做冒泡排序。

981
00:36:39,710 --> 00:36:42,570
如此反复，現在我們正在進入
排序，而不是搜索。

982
00:36:42,570 --> 00:36:47,220
>> 在最壞的情況下，沒有多少步
理賠冒泡排序要採取？

983
00:36:47,220 --> 00:36:48,410
擺正Ń。

984
00:36:48,410 --> 00:36:49,200
所以我要畫，。

985
00:36:49,200 --> 00:36:51,710
哦，我的筆跡看起來更糟
當它預計的那麼大。

986
00:36:51,710 --> 00:36:52,510
好的。

987
00:36:52,510 --> 00:36:53,570
所以這Ñ平方。

988
00:36:53,570 --> 00:36:59,460
而冒泡排序在最好的情況下，
多少步，要採取？

989
00:36:59,460 --> 00:37:00,980
1，我聽說了。

990
00:37:00,980 --> 00:37:01,760
>> 揚聲器1：N。

991
00:37:01,760 --> 00:37:03,286
>> DAVID J.馬蘭：N，我聽說了。

992
00:37:03,286 --> 00:37:04,200
>> 揚聲器1：2。

993
00:37:04,200 --> 00:37:05,010
>> DAVID J.馬蘭：2，我聽說了。

994
00:37:05,010 --> 00:37:06,670
我聽到3？

995
00:37:06,670 --> 00:37:07,080
好的。

996
00:37:07,080 --> 00:37:11,390
所以我聽說過1，N 2，但讓我們挑
除了至少在最前面的那

997
00:37:11,390 --> 00:37:12,330
建議，1。

998
00:37:12,330 --> 00:37:15,370
這不是一個壞的本能，因為它
一種遵循一種模式。

999
00:37:15,370 --> 00:37:19,670
但是，如果只需要1步，如何在
世界我聲稱，該清單

1000
00:37:19,670 --> 00:37:22,900
排序，因為如果我只允許
1步，多少個元素

1001
00:37:22,900 --> 00:37:25,230
其實，我可以檢查，以確保？

1002
00:37:25,230 --> 00:37:28,270
那麼，就1，這意味著有Ñ
減去1個元素，可能是滿分

1003
00:37:28,270 --> 00:37:31,310
秩序，我只是去後的信仰
看著1元

1004
00:37:31,310 --> 00:37:31,850
事情進行排序。

1005
00:37:31,850 --> 00:37:33,930
所以這裡不正確。

1006
00:37:33,930 --> 00:37:35,710
因此，微創，有多少
我要看看嗎？

1007
00:37:35,710 --> 00:37:36,680
>> [插入聲音]

1008
00:37:36,680 --> 00:37:40,160
>> DAVID J. MALAN：N減1，還是真的，
N，因為我需要看每

1009
00:37:40,160 --> 00:37:42,190
元件，以確保
它不是秩序。

1010
00:37:42,190 --> 00:37:44,750
但是，我們將再次排序波我們
手較小的數字，

1011
00:37:44,750 --> 00:37:47,100
假設，當n變大時，他們
反正無趣。

1012
00:37:47,100 --> 00:37:48,380
因此，冒泡排序。

1013
00:37:48,380 --> 00:37:49,830
而現在，讓我們做這些最後兩個。

1014
00:37:49,830 --> 00:37:53,520
選擇排序，然後我們會
做插入排序。

1015
00:37:53,520 --> 00:37:57,160
然後，我們會打擊你的
頭腦的東西多

1016
00:37:57,160 --> 00:37:58,926
比所有這些。

1017
00:37:58,926 --> 00:38:00,410
好的。

1018
00:38:00,410 --> 00:38:04,700
>> 這是最壞的情況下運行
選擇時間排序？

1019
00:38:04,700 --> 00:38:05,680
>> 揚聲器4：N的平方。

1020
00:38:05,680 --> 00:38:06,710
>> DAVID J.馬蘭：n的方陣，我聽到。

1021
00:38:06,710 --> 00:38:09,790
但是，為什麼Ñ平方，直觀？

1022
00:38:09,790 --> 00:38:11,170
>> 揚聲器4：因為我們只是做了它。

1023
00:38:11,170 --> 00:38:12,260
>> DAVID J.馬蘭：因為我們只是做了它。

1024
00:38:12,260 --> 00:38:12,550
確定。

1025
00:38:12,550 --> 00:38:13,380
好答案。

1026
00:38:13,380 --> 00:38:16,660
但直覺上，這是為什麼選擇
排序Ñ平方？

1027
00:38:16,660 --> 00:38:18,980
我們有什麼做
一遍又一遍嗎？

1028
00:38:18,980 --> 00:38:22,570
我們必須保持通過掃描，
你最小，你是

1029
00:38:22,570 --> 00:38:24,020
最小的，你是最小的。

1030
00:38:24,020 --> 00:38:27,480
並授予，我們可以取n
步驟，則n減1，那麼n減去2。

1031
00:38:27,480 --> 00:38:30,700
但是，如果你有種把它們統統加起來，
或採取的信心，我已經加入

1032
00:38:30,700 --> 00:38:34,810
他們在前進，我們大致得到Ñ
平方減去一些小的數字。

1033
00:38:34,810 --> 00:38:36,730
所以，我現在就打電話給這n的平方。

1034
00:38:36,730 --> 00:38:39,530
但最好的選擇排序
的情況下，多少步

1035
00:38:39,530 --> 00:38:40,632
要帶我嗎？

1036
00:38:40,632 --> 00:38:41,840
>> 揚聲器5：[聽不清]

1037
00:38:41,840 --> 00:38:44,350
>> DAVID J.馬蘭：這是不幸的
仍然為n的平方，右？

1038
00:38:44,350 --> 00:38:49,590
因為如果我選擇最小
元素，我們在這裡有七人，

1039
00:38:49,590 --> 00:38:53,280
我只知道，一旦我得到非常
最後，我發現最小

1040
00:38:53,280 --> 00:38:55,670
數，無論他或
她可能已經。

1041
00:38:55,670 --> 00:38:58,820
但我怎麼找了下
最小的號碼是多少？

1042
00:38:58,820 --> 00:39:00,160
我必須做的另一張通行證。

1043
00:39:00,160 --> 00:39:04,810
因此，在最好的情況下，什麼是
輸入選擇排序？

1044
00:39:04,810 --> 00:39:07,830
這是一個已排序列表，頭號，
數二，數三，數四。

1045
00:39:07,830 --> 00:39:08,600
但我一台電腦。

1046
00:39:08,600 --> 00:39:10,190
我只能看一眼
在一個時間的事情。

1047
00:39:10,190 --> 00:39:12,465
我不能排序採取的一個步驟
像人類和說，

1048
00:39:12,465 --> 00:39:14,030
哦，這看起來是正確的。

1049
00:39:14,030 --> 00:39:17,580
>> 我只能判決正確性
選擇排序方式選擇

1050
00:39:17,580 --> 00:39:18,370
最小數。

1051
00:39:18,370 --> 00:39:21,390
但是，即使我發現的頭號第一，
如果我不知道別的約

1052
00:39:21,390 --> 00:39:24,460
其他號碼，我不，我
知道，我已經交給一個數組

1053
00:39:24,460 --> 00:39:27,930
或一組門後面是
數字，只有這樣，我知道，一個

1054
00:39:27,930 --> 00:39:28,680
是最小的嗎？

1055
00:39:28,680 --> 00:39:32,440
如果我得到的所有的方式在這裡實現，
該死的，一個是最小的。

1056
00:39:32,440 --> 00:39:34,870
>> 但我怎麼確定
二是下一個最小的？

1057
00:39:34,870 --> 00:39:38,350
通過做同樣的低效率
一遍又一遍。

1058
00:39:38,350 --> 00:39:42,210
最後，用插入排序，
如何，在最壞的情況下，

1059
00:39:42,210 --> 00:39:44,990
我們說，它執行？

1060
00:39:44,990 --> 00:39:49,100
它也為n的平方。

1061
00:39:49,100 --> 00:39:53,020
最好的情況下怎麼樣？

1062
00:39:53,020 --> 00:39:56,282
我們會離開，作為一個扣人心弦的。

1063
00:39:56,282 --> 00:40:00,090
我們要填補那個空白的下一次，
但首先，讓我建議，我們

1064
00:40:00,090 --> 00:40:02,620
從根本上做得比
所有這些，好嗎？

1065
00:40:02,620 --> 00:40:05,220
>> 因此，認為自己是什麼插入
排序將是。

1066
00:40:05,220 --> 00:40:06,910
嗯，這是不是很劇烈，
因為我是唯一一個

1067
00:40:06,910 --> 00:40:08,970
看到了變化。

1068
00:40:08,970 --> 00:40:09,620
哇。

1069
00:40:09,620 --> 00:40:10,420
確定。

1070
00:40:10,420 --> 00:40:12,615
所以，在這裡，我們有一個有點
不同的示範。

1071
00:40:12,615 --> 00:40:16,580
如果我在這裡放大，你會看到，在
左邊我們有冒泡排序，

1072
00:40:16,580 --> 00:40:20,740
中間我們有選擇排序，
最右邊，我們有些東西

1073
00:40:20,740 --> 00:40:23,380
還沒有看過
所謂合併排序。

1074
00:40:23,380 --> 00:40:26,080
但我們一直在考慮什麼
在這裡做今天迄今。

1075
00:40:26,080 --> 00:40:29,200
當珍妮弗第一次來到了舞台上，
我們經歷過的數字數組

1076
00:40:29,200 --> 00:40:33,750
一遍，又一遍，線性搜索，
我們得到了線性運行時間，大O

1077
00:40:33,750 --> 00:40:35,100
N，可以這麼說。

1078
00:40:35,100 --> 00:40:41,000
>> 當我們現在考慮的第一週
類，當我們分而治之，

1079
00:40:41,000 --> 00:40:43,740
我們電話簿撕裂，
和珍妮弗，我們集體

1080
00:40:43,740 --> 00:40:47,500
利用關鍵的洞察力，這是
重複自己一遍又一遍

1081
00:40:47,500 --> 00:40:50,930
莫名其妙地扔掉，扔掉，
扔掉，一半的問題，或

1082
00:40:50,930 --> 00:40:55,320
通常，分割一半中的一個問題，
然後把一塊較小

1083
00:40:55,320 --> 00:40:59,630
概念上等同的問題
另一方面，我們莫名其妙地做

1084
00:40:59,630 --> 00:41:00,910
從根本上更好。

1085
00:41:00,910 --> 00:41:04,720
但隨著冒泡排序，選擇
排序，插入排序，我們可能

1086
00:41:04,720 --> 00:41:06,560
詹妮弗沒有這樣的見解。

1087
00:41:06,560 --> 00:41:10,220
我們非常簡單，只是走回
提出了一大堆的時候，我們

1088
00:41:10,220 --> 00:41:12,650
調整了一點點東西，交換
在這個命令，也許

1089
00:41:12,650 --> 00:41:13,730
插入或選擇。

1090
00:41:13,730 --> 00:41:16,950
但是在一天結束的時候，我做了很多
尷尬的步行來回。

1091
00:41:16,950 --> 00:41:21,160
我們並沒有真正利用的東西
智能不喜歡像珍妮弗除以

1092
00:41:21,160 --> 00:41:22,040
和征服。

1093
00:41:22,040 --> 00:41:25,620
>> 因此，歸併排序，與此相反，我們
直到下週不會看到，它是怎麼回事

1094
00:41:25,620 --> 00:41:29,540
除以利用的關鍵概念
的輸入，然後減半，然後

1095
00:41:29,540 --> 00:41:30,580
減半，再減半。

1096
00:41:30,580 --> 00:41:34,590
和在該循環的每次迭代，
排序的左半邊和右

1097
00:41:34,590 --> 00:41:38,200
減半的話，左半邊的左半部分，
和右半邊的左方，再

1098
00:41:38,200 --> 00:41:40,990
的左半部的右半部分，並
的右半邊的右半部分。

1099
00:41:40,990 --> 00:41:42,840
並重複一遍又一遍。

1100
00:41:42,840 --> 00:41:46,170
>> 所以，你會看到在視覺上，但是這
是什麼在等待著我們下週。

1101
00:41:46,170 --> 00:41:49,760
而在一般情況下，當我們覺得一點點
任何這樣的問題上有點困難。

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
我們有N平方的左側，正
在中間，和n平方

1104
00:41:57,970 --> 00:41:59,400
n在登錄的權利。

1105
00:41:59,400 --> 00:42:00,590
因此，有你真正的懸​​念。

1106
00:42:00,590 --> 00:42:02,040
我們會看到你在星期一。

1107
00:42:02,040 --> 00:42:05,163
>> [掌聲]