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

2
00:00:11,270 --> 00:00:14,910
>> 演講嘉賓：好的，這是CS50。

3
00:00:14,910 --> 00:00:19,020
這是3週結束時，如果
你有沒有冤大頭不已，

4
00:00:19,020 --> 00:00:21,790
知道，會有午餐
這個星期五​​和往常一樣，在那裡

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

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

7
00:00:27,980 --> 00:00:30,170
前往這個網址在這裡。

8
00:00:30,170 --> 00:00:33,420
>> 現在，你可能還記得，或者你
可能很快被認識，

9
00:00:33,420 --> 00:00:35,970
這些東西在這裡，這
在最後給出了

10
00:00:35,970 --> 00:00:37,850
的學期很多類。

11
00:00:37,850 --> 00:00:40,870
所謂考試藍色書籍，其中
你寫你的答案考試。

12
00:00:40,870 --> 00:00:44,240
現在我已經在這裡等26
藍色的書，對他們每個人

13
00:00:44,240 --> 00:00:47,580
通過Z.寫著的名字，a和
不愧是名是簡單，一

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

15
00:00:50,490 --> 00:00:53,910
將是繼續什麼
我們開始在星期一，這是不

16
00:00:53,910 --> 00:00:57,830
這麼多看代碼，但真正
尋找思路和解決問題的能力。

17
00:00:57,830 --> 00:01:00,170
其中一個目標，
本課程的承諾

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

19
00:01:02,985 --> 00:01:05,400
並且更有效地解決問題。

20
00:01:05,400 --> 00:01:09,526
事實上，我們能做到這一點真的
甚至沒有觸及一行代碼。

21
00:01:09,526 --> 00:01:12,150
所以，我有一對夫婦的大象
在這裡今天，橙，藍，

22
00:01:12,150 --> 00:01:15,780
如果我們能找到一名志願者，
也許從更遠的背面比平常。

23
00:01:15,780 --> 00:01:18,070
怎麼樣在那裡，下來吧。

24
00:01:18,070 --> 00:01:24,180
它的目的將是對
幫助再加上這裡管理這門考試。

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

26
00:01:24,935 --> 00:01:25,768
>> 聽眾：瑪麗·貝絲。

27
00:01:25,768 --> 00:01:27,560
演講嘉賓：瑪麗·貝絲，上來吧。

28
00:01:27,560 --> 00:01:29,560
讓我的麥克風為您服務。

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

30
00:01:32,172 --> 00:01:32,880
很高興認識你。

31
00:01:32,880 --> 00:01:34,005
>> 聽眾：很高興見到你。

32
00:01:34,005 --> 00:01:36,790
演講嘉賓：好，讓我有
這裡藍皮書A到Z，

33
00:01:36,790 --> 00:01:41,680
我要去假裝
我有一個學生，

34
00:01:41,680 --> 00:01:45,770
而他們來的有點隨意
在三個小時的考試塊的末尾，

35
00:01:45,770 --> 00:01:49,400
所以他們結束了在某些
半隨機的順序是這樣的。

36
00:01:49,400 --> 00:01:54,510
現在，在短短的一瞬間你的工作是怎麼回事
以be--這其實是他們如何獲得

37
00:01:54,510 --> 00:01:56,820
在結束時打開在
類，最有可能的。

38
00:01:56,820 --> 00:02:01,120
你現在的工作將是，相當
簡單地說，這些藍色的書為我們梳理

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

40
00:02:05,220 --> 00:02:08,400
>> 聽眾：哦，這是
要帶下去。

41
00:02:08,400 --> 00:02:13,747
>> 演講嘉賓：我們會看
當你做到這一點，沒有壓力。

42
00:02:13,747 --> 00:02:15,330
聽眾：沒有，沒有壓力或任何東西。

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

44
00:02:19,230 --> 00:02:23,570
>> 演講嘉賓：而且為了好玩，
我們提出了一個定時器。

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

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

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

48
00:02:36,741 --> 00:02:38,574
>> 演講嘉賓：我可以抱麥克風為您服務。

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

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

51
00:02:44,190 --> 00:02:49,060
所以在此期間，讓我帶來什麼
要成為瑪麗貝絲問題

52
00:02:49,060 --> 00:02:51,540
是什麼，是她做的，怎麼會是
她打算著手解決呢？

53
00:02:51,540 --> 00:02:54,040
而事實上，你可能沒有
沒有想過的東西

54
00:02:54,040 --> 00:02:57,440
如此簡單，當你挑選的
高達26本書就是這樣，

55
00:02:57,440 --> 00:02:59,350
它確實有一個自然的
訂購他們。

56
00:02:59,350 --> 00:03:01,335
過程是怎樣的
你實際上使用？

57
00:03:01,335 --> 00:03:03,770
它是相當隨機的只是
挑選你看到的第一個

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

59
00:03:05,250 --> 00:03:09,680
你首先將雙手左右
尋找，然後找乙？

60
00:03:09,680 --> 00:03:11,722
你看看在
他們兩人並排

61
00:03:11,722 --> 00:03:14,680
而只是說，等一下，這
是不對的，然後交換順序？

62
00:03:14,680 --> 00:03:16,960
我們已經看到在週一
這有許多方法

63
00:03:16,960 --> 00:03:22,140
在其中我們可以做到這一點，
的確，我們附近結束了，

64
00:03:22,140 --> 00:03:26,360
我會留意可能
什麼瑪麗·貝絲在做什麼。

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

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

67
00:03:33,790 --> 00:03:36,415
>> 聽眾：我命令他們
當我找到兩封信

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

69
00:03:39,540 --> 00:03:42,915
不用擔心保存
軌道書一整排的。

70
00:03:42,915 --> 00:03:45,706
這只是，呵呵，首先，
我這裡有這個堆棧。

71
00:03:45,706 --> 00:03:47,580
演講嘉賓：所以，幾乎像
拼圖的碎片

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

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

74
00:03:51,026 --> 00:03:55,320
演講嘉賓：好的，優秀的。

75
00:03:55,320 --> 00:03:59,850
現在每個這些
樁的大概排序？

76
00:03:59,850 --> 00:04:00,990
>> 聽眾：是的。

77
00:04:00,990 --> 00:04:09,900
>> 演講嘉賓：好的，從A到Z的所有
沒錯，恭喜你，你做到了。

78
00:04:09,900 --> 00:04:11,461
你有你的選擇。

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

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

81
00:04:13,530 --> 00:04:16,679
因此，瑪麗·都建議
什麼她的做法是，

82
00:04:16,679 --> 00:04:19,720
但什麼是另一種方法，你如何
可能去整理這些東西？

83
00:04:19,720 --> 00:04:21,130
你會怎麼做？

84
00:04:21,130 --> 00:04:24,060
擊敗的紀錄會一直
一分鐘，50秒左右，

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

86
00:04:26,039 --> 00:04:27,080
你會怎麼做？

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

88
00:04:27,579 --> 00:04:28,735
聽眾：以堆棧。

89
00:04:28,735 --> 00:04:29,776
從起始處開始。

90
00:04:29,776 --> 00:04:32,284
請檢查您的論文。

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

92
00:04:36,586 --> 00:04:38,980
底部的一個是
高，然後切換他們。

93
00:04:38,980 --> 00:04:41,300
>> 演講嘉賓：好，那麼開始
在頂部和底部，

94
00:04:41,300 --> 00:04:43,716
然後你的工作方式
向內那樣，交換呢？

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

96
00:04:46,580 --> 00:04:49,160
但選擇極端
不相鄰的對。

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

98
00:04:52,080 --> 00:04:54,210
我們可以做到這一點，
坦率地說，我覺得你真好

99
00:04:54,210 --> 00:04:55,700
通過幾個途徑，對不對？

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

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

102
00:05:02,650 --> 00:05:06,950
你沒有把它當作一個大的一堆，
你劃分的問題分為四個四邊形，

103
00:05:06,950 --> 00:05:09,820
如果你願意，然後以某種方式
合併它們的末端。

104
00:05:09,820 --> 00:05:13,410
>> 因此，讓我們考慮，最終，
怎麼回事我們可以做到這一點。

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

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

107
00:05:18,780 --> 00:05:22,640
八你的同學在這裡，
起初看似隨機排列。

108
00:05:22,640 --> 00:05:26,110
然後我們決定成對的，如果
兩個元素是無序，

109
00:05:26,110 --> 00:05:26,950
簡單地交換他們。

110
00:05:26,950 --> 00:05:28,930
於是四加二
顯然失靈，

111
00:05:28,930 --> 00:05:31,080
所以這兩個同班同學
交換位置。

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

113
00:05:35,390 --> 00:05:36,980
移動到右側。

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

115
00:05:42,590 --> 00:05:45,220
左到右在一個這樣的迭代？

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

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

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

119
00:05:51,405 --> 00:05:53,880
他們和你繼續前進
1跳的權利，

120
00:05:53,880 --> 00:05:56,060
你不會有八
比較，因為你不能比較

121
00:05:56,060 --> 00:05:59,226
對本身的元素，否則會
僅僅是毫無意義的，讓你有七。

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

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

124
00:06:04,300 --> 00:06:08,150
>> 所以，現在讓我們考慮如何好或
壞的泡沫實際上是排序，並嘗試

125
00:06:08,150 --> 00:06:13,570
給自己用的詞彙
這在像這樣的批判算法，

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

127
00:06:14,430 --> 00:06:16,970
所以，通過第一通
冒泡排序，在第一時間

128
00:06:16,970 --> 00:06:20,909
我是從左邊走到對面的權利
現階段，我花了Ñ減1的比較。

129
00:06:20,909 --> 00:06:22,950
而這將是我的
計量單位的，對不對？

130
00:06:22,950 --> 00:06:26,170
我是那種說話，散步，
有些快，有些慢，

131
00:06:26,170 --> 00:06:29,300
所以我計算的秒數
沒有特別明顯的，

132
00:06:29,300 --> 00:06:32,260
但計數的數目
我確實在週一的操作，

133
00:06:32,260 --> 00:06:35,900
比較兩個人，那種感覺
就像衡量一個不錯的單位。

134
00:06:35,900 --> 00:06:40,980
>> 因此n減1的步驟是第一次，
但之後發生了什麼？

135
00:06:40,980 --> 00:06:46,610
什麼是一傳一上攻
通過其他未分類列表？

136
00:06:46,610 --> 00:06:49,840
你能告訴我該元素
誰是一路過來嗎？

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

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

139
00:06:52,870 --> 00:06:55,710
第八，即使她
從這裡開始，我每次

140
00:06:55,710 --> 00:06:57,860
對她比較
一個鄰居，她不停地

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

142
00:07:00,480 --> 00:07:02,710
事實上，這正是
該算法得名。

143
00:07:02,710 --> 00:07:07,630
>> 現在，通過這一邏輯，有多少的比較
需要我做的第二次

144
00:07:07,630 --> 00:07:09,800
我作出這樣的傳球從左至右？

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

146
00:07:10,730 --> 00:07:14,297
這純粹是在浪費我的時間，如果我
保持比較8人反對某人

147
00:07:14,297 --> 00:07:16,630
別的，因為我們已經知道
她是在正確的地方。

148
00:07:16,630 --> 00:07:19,760
所以這是一個比特的
優化，所以下通

149
00:07:19,760 --> 00:07:23,899
將是加N減去兩個步驟
其中n是人的數目。

150
00:07:23,899 --> 00:07:26,940
現在你可以種推斷，即使
如果你不是一名計算機科學家，

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

152
00:07:27,680 --> 00:07:31,259
在此算法結束時，據推測
你有只是一個比較離去。

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

154
00:07:33,800 --> 00:07:36,540
一都失靈
並應一和二，

155
00:07:36,540 --> 00:07:40,330
所以這個谷底的
加1最後的比較。

156
00:07:40,330 --> 00:07:44,500
>> 現在，點，點，點樣波是
手在一些多汁詳情

157
00:07:44,500 --> 00:07:46,452
但我們只是繼續和簡化。

158
00:07:46,452 --> 00:07:48,660
如果您還記得高
學校，坦率地說，很多你

159
00:07:48,660 --> 00:07:50,340
有數學書的有
有點小抄

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

161
00:07:52,550 --> 00:07:56,400
什麼系列求和樣
這最終加起來。

162
00:07:56,400 --> 00:07:59,600
在一般情況下，如果你有一個
變量如N，而事實上這其中，

163
00:07:59,600 --> 00:08:01,634
如果你看著你
老同學的數學書，

164
00:08:01,634 --> 00:08:04,050
你會看到，這實際上
加起來這筆款項在這裡，

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

166
00:08:07,970 --> 00:08:11,172
所以現在我只想規定
這是真的，那麼對信仰的飛躍，

167
00:08:11,172 --> 00:08:12,880
這就是這個總結
最多，我們可以

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

169
00:08:14,341 --> 00:08:15,590
但現在讓我們展開了這一點。

170
00:08:15,590 --> 00:08:19,920
因此，讓我們乘了這一點，所以這是
Ñ​​平方，減去N，所有除以2。

171
00:08:19,920 --> 00:08:23,200
這真的Ñ平方，
除以2，再減去Ñ超過2，

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

173
00:08:25,010 --> 00:08:27,060
但是，如果我們發生
現在Plug-in的價值呢？

174
00:08:27,060 --> 00:08:29,724
假設我沒有8
人，但說一百萬。

175
00:08:29,724 --> 00:08:31,890
和一百萬只是因為
這是一個非常大的數字，

176
00:08:31,890 --> 00:08:34,039
讓我們插上，在看看會發生什麼。

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

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

179
00:08:42,868 --> 00:08:44,159
現在，那是要一樣的嗎？

180
00:08:44,159 --> 00:08:47,354
所以500十億，減去50萬元。

181
00:08:47,354 --> 00:08:49,270
如果我實際上做
在數學，這表示

182
00:08:49,270 --> 00:08:53,920
該排序一百萬
人與冒泡排序

183
00:08:53,920 --> 00:09:01,800
可能要花費499999500000
在結束步驟或比較，

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

185
00:09:02,900 --> 00:09:06,860
>> 這感覺很慢，但坦率地說
測量一個特定的輸入

186
00:09:06,860 --> 00:09:09,160
像這樣，是不是所有的說服力。

187
00:09:09,160 --> 00:09:14,050
但事實上，這確實表明，當n
變大，該算法

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

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

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

191
00:09:21,770 --> 00:09:25,340
而這個細節不
失去了對的人，其實

192
00:09:25,340 --> 00:09:29,640
幾年前，某參議員誰是
競選活動，坐下來接受採訪

193
00:09:29,640 --> 00:09:32,180
與谷歌的埃里克
施密特，當時的CEO，

194
00:09:32,180 --> 00:09:36,380
並與一個問題的挑戰
就像我們今天探討。

195
00:09:36,380 --> 00:09:38,468
讓我們一起來看看。

196
00:09:38,468 --> 00:09:45,280
>> [視頻回放]

197
00:09:45,280 --> 00:09:48,560
>> -Senator，你在這裡
在谷歌，我喜歡

198
00:09:48,560 --> 00:09:53,382
認為總統的
作為一個工作面試。

199
00:09:53,382 --> 00:09:56,434
現在，它是很難得到
一份工作，擔任總裁，

200
00:09:56,434 --> 00:09:58,100
你正在經歷的嚴酷了。

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

202
00:10:01,860 --> 00:10:05,490
我們有問題，我們
要求我們的考生的問題，

203
00:10:05,490 --> 00:10:09,770
而這一次是從拉里·施維默。

204
00:10:09,770 --> 00:10:14,760
What--你們覺得我
開玩笑，這是在這裡。

205
00:10:14,760 --> 00:10:17,930
什麼是最有效的方式來
排序一百萬的32位整數？

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

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

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

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

210
00:10:27,400 --> 00:10:30,700
我認為，冒泡排序
將錯誤的路要走。

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

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

213
00:10:38,180 --> 00:10:40,590
我沒有看到電腦
科學的背景。

214
00:10:40,590 --> 00:10:42,130
>> -We've了在那裡我們的間諜。

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

216
00:10:44,930 --> 00:10:48,444
>>  - 確定，讓我們問一個不同的
面試問題。

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

218
00:10:49,300 --> 00:10:52,290
>> 演講嘉賓：所以說起
具體的數字，雖然，

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

220
00:10:53,890 --> 00:10:56,810
這不是一個生活的一課泡沫
排序，給定一個億的投入，

221
00:10:56,810 --> 00:10:58,590
可能需要多達500十億步驟。

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

223
00:11:01,120 --> 00:11:03,560
做出好的設計決定
編寫程序時。

224
00:11:03,560 --> 00:11:07,070
因此，讓我們雖然把重點放在如何
我們可以簡化這個結果。

225
00:11:07,070 --> 00:11:11,780
>> 所以，我在這裡黃色高亮
n的結果的平方除以2，

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

227
00:11:14,330 --> 00:11:16,710
我已經強調了什麼
最終的答案是

228
00:11:16,710 --> 00:11:20,180
一旦我們減去關閉N除以2。

229
00:11:20,180 --> 00:11:24,850
並聲稱我會做，現在是，
誰的心裡很不舒服，如果你減去了關心

230
00:11:24,850 --> 00:11:30,060
一老一少Ñ超過2時，第一
這個公式的一部分，是這麼多的大嗎？

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

232
00:11:33,910 --> 00:11:37,510
如此多的大，顯然，作為
n變大像一百萬，

233
00:11:37,510 --> 00:11:41,450
這是真的，在一個很大的區別
一天500十億之間到底

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

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

236
00:11:46,349 --> 00:11:48,640
還等什麼，我們要
做計算機科學家是

237
00:11:48,640 --> 00:11:53,270
忽略這些低階條款及
採取這樣的事情，真的

238
00:11:53,270 --> 00:11:56,050
只需將它簡化為
術語，是怎麼回事無所謂。

239
00:11:56,050 --> 00:12:00,315
在我們的大數據集得到的，更大的
我們的數據庫中得到的，就越網頁

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

241
00:12:02,690 --> 00:12:07,340
>> 當n變大，我們真的
要關心大

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

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

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

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

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

247
00:12:22,060 --> 00:12:24,390
坦率地說，誰真正
關心，如果我們除以2？

248
00:12:24,390 --> 00:12:25,870
這只是一個常數因子。

249
00:12:25,870 --> 00:12:29,480
並為500十億與250
十億真有那麼大的一筆交易？

250
00:12:29,480 --> 00:12:32,190
我可以等一年，
讓我的筆記本電腦逐字

251
00:12:32,190 --> 00:12:34,810
得到兩倍於硬件的速度，
等諸如此類的差異

252
00:12:34,810 --> 00:12:36,650
剛剛消失，自然隨著時間的推移。

253
00:12:36,650 --> 00:12:39,300
>> 我們關心的是什麼
的表達，該部

254
00:12:39,300 --> 00:12:42,489
那將改變表達的
作為我們的輸入變得越來越大。

255
00:12:42,489 --> 00:12:45,280
事實上，在現實世界中，
這就是正在發生的事情越來越多

256
00:12:45,280 --> 00:12:48,330
是投入到我們的問題，
算法越來越大。

257
00:12:48,330 --> 00:12:53,470
因此，大O將是符號，
漸近符號，我們只

258
00:12:53,470 --> 00:12:57,160
利用計算機科學家描述
的性能，或在運行時間，

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

260
00:12:58,130 --> 00:13:00,800
這樣我們就可以比較算法
寫上不同的計算機

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

262
00:13:04,170 --> 00:13:07,557
喜歡比較的次數你
製作，或者互換的數量

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

264
00:13:08,140 --> 00:13:11,910
>> 我們不是要
計數的時間量

265
00:13:11,910 --> 00:13:13,981
傳遞上的時鐘
牆壁上的典型。

266
00:13:13,981 --> 00:13:16,230
我們不是要擔心
大約是多少內存

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

268
00:13:17,820 --> 00:13:19,370
另一種資源，我們可以衡量的。

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

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

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

272
00:13:30,700 --> 00:13:35,820
是一個上限，所謂
運行冒泡排序的時間。

273
00:13:35,820 --> 00:13:38,820
換句話說，如果
希望聲稱有

274
00:13:38,820 --> 00:13:41,370
上多少這個上限
幾步之遙的算法可能需要，

275
00:13:41,370 --> 00:13:46,240
這將是n的大O
平方在這種情況下，一個上限。

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

277
00:13:49,710 --> 00:13:50,910
但這個上限。

278
00:13:50,910 --> 00:13:54,030
你能想到的算法
我們已經看過了已經

279
00:13:54,030 --> 00:13:59,530
其上限，最大
測量的時間或操作

280
00:13:59,530 --> 00:14:04,300
將所述有界
用n，一個線性函數，

281
00:14:04,300 --> 00:14:07,260
沒有二次一個是彎曲？

282
00:14:07,260 --> 00:14:10,780
什麼是算法
始終把沒有更多的

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

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

285
00:14:13,360 --> 00:14:15,030
>> 聽眾：尋找
列表中的最大號碼是多少？

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

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

288
00:14:18,940 --> 00:14:21,440
各是誰在持有一個號碼，
什麼是最大數

289
00:14:21,440 --> 00:14:23,770
步驟應該帶我，
一個相當聰明的人，

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

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

292
00:14:28,100 --> 00:14:31,320
由於在最壞的情況下，當
也許最大的價值是什麼？

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

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

295
00:14:34,575 --> 00:14:36,450
要一路走下去
在這裡是這樣，

296
00:14:36,450 --> 00:14:39,170
哦，這裡的數字8，
或任何該值。

297
00:14:39,170 --> 00:14:41,330
現在，這純粹是愚蠢的
如果我堅持下來了，對不對？

298
00:14:41,330 --> 00:14:43,840
尋找更多的元素
如果最後他們是在那裡？

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

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

301
00:14:47,420 --> 00:14:51,580
>> 那麼，如果不是我提出的
還有在這個世界上的算法，

302
00:14:51,580 --> 00:14:57,750
有一個運行時間的
通過日誌的n大O範圍內，日誌N？

303
00:14:57,750 --> 00:15:00,390
那裡有我們以前見過嗎？

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

305
00:15:00,890 --> 00:15:03,309
>> 聽眾：在電話簿的問題？

306
00:15:03,309 --> 00:15:04,850
演講嘉賓：像電話簿的問題。

307
00:15:04,850 --> 00:15:07,754
什麼是如何的量度
太多的時間和多少眼淚吧

308
00:15:07,754 --> 00:15:10,170
帶我找到喜歡的人
邁克·史密斯在電話簿？

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

310
00:15:13,212 --> 00:15:15,170
一點點朦朧什麼
對數或指數為，

311
00:15:15,170 --> 00:15:17,650
只記得為log N
一般是指在過程中

312
00:15:17,650 --> 00:15:20,790
在這種情況下，分割
東西兩半又一次，又一次，

313
00:15:20,790 --> 00:15:25,790
又一次，又一次，使得其
變的越來越小，你這樣做。

314
00:15:25,790 --> 00:15:28,470
>> 因此，日誌正指，當然，
到電話簿例如

315
00:15:28,470 --> 00:15:32,662
在理論的二進制搜索，當我們
有虛擬門電路板上，

316
00:15:32,662 --> 00:15:34,370
或者當肖恩
尋找的東西。

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

318
00:15:37,374 --> 00:15:38,040
時間花費。

319
00:15:38,040 --> 00:15:44,027
但是，那些跑在算法
日誌N承擔哪些關鍵的細節？

320
00:15:44,027 --> 00:15:45,360
該列表進行排序，對不對？

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

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

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

324
00:15:51,704 --> 00:15:53,600
沒有意識到這是真的在那裡。

325
00:15:53,600 --> 00:15:55,600
>> 現在什麼可能意味著一，大O？

326
00:15:55,600 --> 00:15:59,117
這並不意味著你的算法
採用一個和唯一的一個步驟，

327
00:15:59,117 --> 00:16:01,200
它只是意味著它需要一個
步驟恆定數目。

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

329
00:16:04,060 --> 00:16:07,750
但它是獨立的
問題的大小。

330
00:16:07,750 --> 00:16:10,850
無論多麼大的n是，
一個常數時間算法

331
00:16:10,850 --> 00:16:12,747
始終以相同的步驟號碼。

332
00:16:12,747 --> 00:16:15,080
那麼，什麼可能是一個算法
我們已經討論過，或只是

333
00:16:15,080 --> 00:16:20,418
直觀地說來你
總是在所謂的恆定時間運行？

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

335
00:16:20,918 --> 00:16:22,001
>> 聽眾：兩個數相加。

336
00:16:22,001 --> 00:16:25,320
音箱：兩個數相加，
2加2等於4，完成。

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

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

339
00:16:28,560 --> 00:16:30,686
>> 聽眾：尋找
列表中的第一件事情。

340
00:16:30,686 --> 00:16:32,810
演講嘉賓：尋找第一
元素在列表中，確保萬無一失。

341
00:16:32,810 --> 00:16:34,540
實際上我們一直在談論
關於數組已經，

342
00:16:34,540 --> 00:16:36,540
你怎麼在得到
在數組的第一元素，

343
00:16:36,540 --> 00:16:40,465
無論多久
數組是C代碼？

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

345
00:16:43,090 --> 00:16:46,120
事實上陣列，順便說一句，
支持的東西一般稱為

346
00:16:46,120 --> 00:16:49,240
隨機存取，隨機存取
記憶，因為你可以從字面上

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

348
00:16:50,284 --> 00:16:52,700
我們可以做到這一點，甚至更簡單
我們可以倒回至零一周

349
00:16:52,700 --> 00:16:53,900
當我們做劃傷。

350
00:16:53,900 --> 00:16:59,707
它沒有多少時間了
要說塊划痕執行？

351
00:16:59,707 --> 00:17:00,790
就在固定的時間，對不對？

352
00:17:00,790 --> 00:17:03,960
說些什麼，說
東西，也沒關係

353
00:17:03,960 --> 00:17:07,359
大划痕世界是怎樣的，它總是
要採取相同的時間量

354
00:17:07,359 --> 00:17:08,490
簡單地說一下。

355
00:17:08,490 --> 00:17:11,089
>> 所以這是一定的時間，
但什麼是另一面？

356
00:17:11,089 --> 00:17:13,030
如果這是上
界，如果我們想要什麼

357
00:17:13,030 --> 00:17:17,089
描述下界
我們的算法的運行時間？

358
00:17:17,089 --> 00:17:19,852
幾乎是最好的情況
潛在的，如果你願意，

359
00:17:19,852 --> 00:17:23,060
儘管這些條款可以適用於最
的情況下，最壞的情況下，一般情況下，更多的

360
00:17:23,060 --> 00:17:26,359
一般，但我們只關注
上下限比較一般。

361
00:17:26,359 --> 00:17:31,920
什麼是算法，具有
下界n個步驟，

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

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

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

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

366
00:17:37,910 --> 00:17:41,610
>> 演講嘉賓：冒泡排序需要
你最低限度n步，為什麼呢？

367
00:17:41,610 --> 00:17:42,279
這是為什麼？

368
00:17:42,279 --> 00:17:45,320
為什麼會這樣開始來找你
直觀地說，即使它不只是

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

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

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

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

373
00:17:51,652 --> 00:17:52,360
演講嘉賓：沒錯。

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

375
00:17:55,810 --> 00:17:58,769
如果我交給你八人
誰是已經排序，

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

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

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

379
00:18:04,285 --> 00:18:08,090
你應該明白，哦，我什麼也沒有
掉期，這個列表進行排序，退出。

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

381
00:18:09,700 --> 00:18:12,033
>> 反之，什麼又
考慮這個問題的方法是什麼？

382
00:18:12,033 --> 00:18:15,240
冒泡排序是歐米茄，
這麼說的n，，

383
00:18:15,240 --> 00:18:19,050
因為如果你看一下
少於n個元素，是什麼

384
00:18:19,050 --> 00:18:23,009
是根本問題嗎？

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

386
00:18:24,550 --> 00:18:26,800
我們人類的威力一目了然八
人是這樣，哦，它的排序，

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

388
00:18:28,430 --> 00:18:30,810
你的眼睛，即使你有種
有願景的一大領域，

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

390
00:18:33,184 --> 00:18:34,610
這八個步驟有效。

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

392
00:18:38,612 --> 00:18:41,320
如果我中途停止思考，所有的
沒錯，這是相當排序到目前為止，

393
00:18:41,320 --> 00:18:42,520
什麼是它沒有排序的機率有多大？

394
00:18:42,520 --> 00:18:44,186
該機制的算法不會是正確的。

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

396
00:18:46,250 --> 00:18:48,500
>> 所以，現在我們有辦法
描述一個下界，

397
00:18:48,500 --> 00:18:49,710
和什麼有關固定時間？

398
00:18:49,710 --> 00:18:54,565
什麼是算法，該算法具有較低的
綁定在它的一個運行時間？

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

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

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

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

403
00:19:04,600 --> 00:19:05,309
>> 聽眾：printf的？

404
00:19:05,309 --> 00:19:06,183
演講嘉賓：那是什麼？

405
00:19:06,183 --> 00:19:07,184
聽眾：printf的？

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

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

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

409
00:19:10,720 --> 00:19:13,170
我現在應該是now--
我們正在談論的C代碼

410
00:19:13,170 --> 00:19:16,040
不撓，事
如說，與printf的，

411
00:19:16,040 --> 00:19:17,710
我們應該開始變得謹慎。

412
00:19:17,710 --> 00:19:21,090
因為printf的確實需要
輸入時，它是一個字符串，

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

414
00:19:23,220 --> 00:19:25,530
因此，如果我們現在要挑
對你，如果你不介意的話，

415
00:19:25,530 --> 00:19:29,430
在技​​術上，我們可以認為，printf的
確實需要一個可變長度的輸入，

416
00:19:29,430 --> 00:19:32,270
並肯定它可能需要更多的
這漫長的時間來打印字符串，

417
00:19:32,270 --> 00:19:33,560
比這個長。

418
00:19:33,560 --> 00:19:36,570
>> 因此，如果我們考慮一下剛才的
排序和搜索的例子嗎？

419
00:19:36,570 --> 00:19:40,450
怎麼樣邁克·史密斯在手機
書，或二進制搜索更普遍？

420
00:19:40,450 --> 00:19:42,220
在最好的情況下，可能會發生什麼？

421
00:19:42,220 --> 00:19:45,577
我打開電話本和，BAM，
還有麥克·史密斯的電話號碼。

422
00:19:45,577 --> 00:19:46,660
我可以打電話給他的時候了。

423
00:19:46,660 --> 00:19:49,390
>> 進了一步，也許兩個步驟，
但是步驟的恆定數

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

425
00:19:50,230 --> 00:19:52,570
坦率地說，我們看到了
週一你的同學

426
00:19:52,570 --> 00:19:54,710
在連續得到相當幸運的兩倍。

427
00:19:54,710 --> 00:19:57,050
而這的確是恆
時間在下限

428
00:19:57,050 --> 00:20:01,280
在算法中的問題查找
數50落後結束

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

430
00:20:01,830 --> 00:20:06,400
>> 現在，順便說一句，如果你發現
這兩個大澳，上界，

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

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

433
00:20:11,830 --> 00:20:15,170
說，只是華麗，
這東西是時間值損耗

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

435
00:20:18,270 --> 00:20:20,661
這只是意味著大當
O和ω-是相同的。

436
00:20:20,661 --> 00:20:21,910
現在怎麼樣選擇排序？

437
00:20:21,910 --> 00:20:23,400
讓我們用這個新的詞彙。

438
00:20:23,400 --> 00:20:27,407
在選擇排序，什麼是我們
老毛病又犯，又一次，又一次？

439
00:20:27,407 --> 00:20:29,990
我來回通過
在列表中，尋找誰呢？

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

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

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

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

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

445
00:20:44,437 --> 00:20:47,770
因為如果我剛入手一個我
鑑於我開始比較他或她，

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

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

448
00:20:52,010 --> 00:20:55,630
所以，選擇排序同樣需要
Ñ​​減1步的第一次。

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

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

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

452
00:21:06,280 --> 00:21:09,270
和第三步驟中，正
減去3，則n減去4。

453
00:21:09,270 --> 00:21:11,020
我們已經看到這種模式
之前，確實

454
00:21:11,020 --> 00:21:13,460
選擇排序相似
有一個上限

455
00:21:13,460 --> 00:21:16,210
n個平方，如果我們這樣做了的總和。

456
00:21:16,210 --> 00:21:19,790
什麼是它的下限，選擇排序？

457
00:21:19,790 --> 00:21:25,350
最低限度，有多少時間必須選擇
排序需要，因為我們將它定義在星期一？

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

459
00:21:29,370 --> 00:21:30,490
提出了兩個選項。

460
00:21:30,490 --> 00:21:32,360
也許這是N，和以前一樣。

461
00:21:32,360 --> 00:21:35,040
也許這是Ñ平方，因為它
現在作為上限。

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

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

464
00:21:36,664 --> 00:21:37,368
為什麼呢？

465
00:21:37,368 --> 00:21:40,060
>> 聽眾：因為你
定義[聽不清]。

466
00:21:40,060 --> 00:21:41,510
>> 演講嘉賓：沒錯。

467
00:21:41,510 --> 00:21:45,077
至少我定義選擇排序
這是非常幼稚的，堅持下去，

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

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

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

471
00:21:49,490 --> 00:21:51,700
有沒有排序
在那裡，最優化

472
00:21:51,700 --> 00:21:54,350
也許讓我以後放棄
只是n或使步驟。

473
00:21:54,350 --> 00:21:57,080
所以，事實上，選擇
排序，正歐米茄平方。

474
00:21:57,080 --> 00:22:00,667
>> 那麼插入排序，在這裡我把
我給誰，然後我一屁股坐在了他

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

476
00:22:01,750 --> 00:22:04,958
我接著給第二個人，
一屁股坐在他或她在正確的地方。

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

478
00:22:07,910 --> 00:22:10,537
注意，這是非常
線性的，可以這麼說。

479
00:22:10,537 --> 00:22:12,620
我是一條直線，我
不會來回，

480
00:22:12,620 --> 00:22:16,080
我從來沒有回頭真的，但
發生了什麼，當我插入了他

481
00:22:16,080 --> 00:22:20,302
或她進入初
因為我們沒有在週一的名單？

482
00:22:20,302 --> 00:22:21,010
發生了什麼？

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

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

485
00:22:23,122 --> 00:22:24,830
演講嘉賓：是的，這
被抓了吧？

486
00:22:24,830 --> 00:22:26,746
你可能還記得，
你的同學，如果他們

487
00:22:26,746 --> 00:22:29,670
正在作出任何動作
他們的腳，這是一個操作。

488
00:22:29,670 --> 00:22:33,610
所以，如果有三個人在這裡和
新人所屬的方式在​​那邊，

489
00:22:33,610 --> 00:22:37,360
在很長的階段，像這樣的，肯定的是，他
或者她只是去到了最後。

490
00:22:37,360 --> 00:22:40,074
但是，如果我們思考一個
計算機和存儲器陣列，

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

492
00:22:41,990 --> 00:22:43,260
讓路給那個人。

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

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

495
00:22:50,660 --> 00:22:52,710
像以前一樣，在某種意義上。

499
00:22:52,557 --> 00:22:54,640
現在，作為一個一旁，並作為
你可能已經看到了網上

500
00:22:54,640 --> 00:22:57,699
如果你開始關注著有關
各種各樣的，有這麼多不同的人

501
00:22:57,699 --> 00:22:59,490
在那裡，他們中的一些
比別人做得更好。

502
00:22:59,490 --> 00:23:02,200
事實上，bogosort是
這是一種樂趣來查找。

503
00:23:02,200 --> 00:23:06,650
Bogosort採用一組
數字或說一副撲克牌，

504
00:23:06,650 --> 00:23:09,870
隨機打亂他們，
檢查，如果他們來分類的。

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

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

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

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

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

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

511
00:23:21,200 --> 00:23:25,180
它最終會工作，
希望，給予足夠的時間，

512
00:23:25,180 --> 00:23:28,240
但該時間量
可能需要相當長的一段時間。

513
00:23:28,240 --> 00:23:31,650
所以，如果我可以，讓我們速度的東西
從早期的瑪麗·貝絲的例子，

514
00:23:31,650 --> 00:23:35,150
通過具有幾個元素，
但有兩個以上處理器。

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

516
00:23:37,100 --> 00:23:40,972
怎麼樣1在這裡，和
讓我們go--沒有人在那裡？

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

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

519
00:23:42,221 --> 00:23:44,190
您與黑
襯衫，是的，下來吧。

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

521
00:23:45,000 --> 00:23:45,720
>> 聽眾：彼得。

522
00:23:45,720 --> 00:23:46,100
>> 演講嘉賓：那是什麼？

523
00:23:46,100 --> 00:23:46,766
>> 聽眾：彼得。

524
00:23:46,766 --> 00:23:49,450
演講者：Peter，大衛，很高興認識你。

525
00:23:49,450 --> 00:23:53,670
好吧，我們有彼得在這裡，如果你
想來在桌上在這裡。

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

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

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

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

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

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

532
00:23:59,170 --> 00:24:02,290
而我們需要安德魯
在這裡為好，請。

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

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

535
00:24:08,190 --> 00:24:11,064
排序有點像
這其中，我們會做的俱樂部，然後

536
00:24:11,064 --> 00:24:13,660
黑桃，則心和
鑽石，從王牌為一體，

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

538
00:24:15,570 --> 00:24:20,890
>> 該卡我打算給你
將要在數量52。

539
00:24:20,890 --> 00:24:23,160
我們將同樣
一次，在短短的一瞬間。

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

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

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

543
00:24:31,070 --> 00:24:33,490
這些都是我上亞馬遜的卡。

544
00:24:33,490 --> 00:24:42,861
因此，他們已經隨機
排序，我們要一次。

545
00:24:42,861 --> 00:24:44,610
而我們要
保持它真正的這個時候，

546
00:24:44,610 --> 00:24:47,820
所以我們要盡量壓你
否則這將讓乏味的

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

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

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

550
00:25:04,710 --> 00:25:07,180
>> 再次，當我們觀看這些
你們做什麼，到底

551
00:25:07,180 --> 00:25:10,200
會產生一個明顯的
結果，想想真

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

553
00:25:12,962 --> 00:25:15,045
因為再次，這些都是
所有過程，算法

554
00:25:15,045 --> 00:25:17,090
我們想當然地作為一個人。

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

556
00:25:22,349 --> 00:25:24,390
想過走
計算機科學類，你

557
00:25:24,390 --> 00:25:27,223
可能曾與直覺
要解決這樣的問題。

558
00:25:27,223 --> 00:25:29,560
但是，一旦你認識到
模式，並開始

559
00:25:29,560 --> 00:25:32,407
形式化與步驟
您正在解決這些問題，

560
00:25:32,407 --> 00:25:35,490
你會發現，你能解決多少
更有趣和更複雜

561
00:25:35,490 --> 00:25:39,190
問題很快。

562
00:25:39,190 --> 00:25:42,351
因此，有人從觀眾，什麼是
該算法中的至少一種元素

563
00:25:42,351 --> 00:25:43,350
他們使用的是在這裡嗎？

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

565
00:25:44,275 --> 00:25:45,150
演講嘉賓：那是什麼？

566
00:25:45,150 --> 00:25:47,062
聽眾：通過訴訟。

567
00:25:47,062 --> 00:25:47,770
演講嘉賓：通過訴訟。

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

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

570
00:25:52,560 --> 00:25:56,520
等等，不尊重
對於卡上的號碼。

571
00:25:56,520 --> 00:26:00,900
現在，他們的出現，例如，
通過數量來對它們進行排序。

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

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

574
00:26:08,910 --> 00:26:12,370
>> 好吧，那麼什麼會
是最後一步，然後在這裡？

575
00:26:12,370 --> 00:26:16,950
一旦我們有四個排序的西服，有什麼
做我們需要做的四樁

576
00:26:16,950 --> 00:26:20,059
為了實現一
整理平台，很簡單？

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

578
00:26:21,350 --> 00:26:25,160
>> 所以這是一個有趣的想法，
再次，敢說，是非常直觀的，甚至

579
00:26:25,160 --> 00:26:28,140
如果你可能從來沒有掌摑
那樣就可以了標籤。

580
00:26:28,140 --> 00:26:31,900
除以這個根本概念
問題不是在一半此時，

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

582
00:26:33,410 --> 00:26:36,810
解決相當多
從根本上相同的問題

583
00:26:36,810 --> 00:26:40,480
在彼此隔離，
然後合併的結果。

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

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

586
00:26:50,140 --> 00:26:52,140
好了，又大又圓
掌聲中，如果我們能。

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

588
00:26:56,480 --> 00:26:59,740
>> 演講嘉賓：我不知道你會
做到這些，但在這裡你去。

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

590
00:27:01,690 --> 00:27:04,660
因此，讓我們來看看兩分鐘
八秒，

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

592
00:27:07,490 --> 00:27:12,160
什麼然後將要
從這樣的帶走

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

594
00:27:13,830 --> 00:27:16,080
好了，回想起
這個數字陣列，

595
00:27:16,080 --> 00:27:19,060
現在回想起一些
偽代碼，我們已經寫在過去，

596
00:27:19,060 --> 00:27:22,080
這是偽代碼
解決電話簿問題。

597
00:27:22,080 --> 00:27:25,150
由此偽í
列舉一個更有條理的方式

598
00:27:25,150 --> 00:27:28,400
描述我是如何做到一個非常直觀的
將所述電話的人的算法

599
00:27:28,400 --> 00:27:31,650
本書的一半，重複，重複，重複，
直到我發現有人像邁克·史密斯，

600
00:27:31,650 --> 00:27:33,790
如果他確實是在電話簿。

601
00:27:33,790 --> 00:27:37,610
>> 但是我種用什麼，我會打電話
很迭代的方法在這裡，

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

603
00:27:42,160 --> 00:27:46,750
這些都是一個迭代的證據
方法，一個循環的方法，

604
00:27:46,750 --> 00:27:49,040
因為這正是
在他們的行為引起。

605
00:27:49,040 --> 00:27:52,910
這些線路都表示去
三線，你可以種

606
00:27:52,910 --> 00:27:55,140
想在你的
心靈之眼作為一個循環。

607
00:27:55,140 --> 00:27:59,080
它告訴你去備份步驟
3，重複，一遍，又一遍，

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

609
00:28:00,010 --> 00:28:04,410
>> 但是，如果我們利用的一個關鍵思想
在這裡，我們沒有最後一次，

610
00:28:04,410 --> 00:28:10,280
並簡化線路8
第11行和他們的鄰居

611
00:28:10,280 --> 00:28:12,840
像剛才這樣，為黃色。

612
00:28:12,840 --> 00:28:16,480
它不能從根本上縮短
偽代碼非常多，

613
00:28:16,480 --> 00:28:20,530
但它從根本上改變
我的算法的性質。

614
00:28:20,530 --> 00:28:24,220
就是我現在說
在步驟7中，在步驟10中，

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

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

617
00:28:31,580 --> 00:28:33,420
>> 因此，換句話說，如果
我是從第一步開始，

618
00:28:33,420 --> 00:28:36,150
拿起電話本，開到中間
電話本，看名字，

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

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

621
00:28:44,340 --> 00:28:47,130
但是那種感覺像
它讓我掛了吧？

622
00:28:47,130 --> 00:28:49,240
在黃色的，是一種
指令，但我怎麼

623
00:28:49,240 --> 00:28:51,870
搜索麥克左
一半的電話簿嗎？

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

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

626
00:28:57,100 --> 00:28:58,980
那麼，它的盯著我們的臉。

627
00:28:58,980 --> 00:29:03,090
我可以從字面上使用完全相同的
計劃有效地往上走頂端

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

629
00:29:06,490 --> 00:29:10,610
>> 因此，即使本應該感到
像一個有點週期性的定義

630
00:29:10,610 --> 00:29:13,480
在那裡你回答別人的
僅通過排序問問題

631
00:29:13,480 --> 00:29:15,990
再次同樣的問題，
就像為什麼，為什麼，為什麼？

632
00:29:15,990 --> 00:29:21,580
現實的情況是，因為我們已經硬編碼
一組特殊的線，第4步，

633
00:29:21,580 --> 00:29:25,320
其是，如果和步驟12，該
實際上是另外​​一個分支，

634
00:29:25,320 --> 00:29:30,120
因為我們有這些治標不治本，
該算法將終止，如果我們

635
00:29:30,120 --> 00:29:32,050
找到邁克，或者如果我們不這樣做。

636
00:29:32,050 --> 00:29:36,810
但現在STEP 7和10，我們有
我們就這麼叫遞歸算法。

637
00:29:36,810 --> 00:29:40,420
和遞歸確實是一個強大的理念
這是一個有點頭腦的第一個彎，

638
00:29:40,420 --> 00:29:42,500
我們現在可以應用如下。

639
00:29:42,500 --> 00:29:46,600
>> 歸併排序將是最後的那種
我們看一下，至少在形式上類。

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

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

642
00:29:52,140 --> 00:29:54,810
下面是偽代碼合併排序。

643
00:29:54,810 --> 00:30:00,170
當n個元素的輸入，因此給予
大小為n的陣列中，如果n小於2，

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

645
00:30:01,040 --> 00:30:03,610
那麼，為什麼我有
理智首先檢查？

646
00:30:03,610 --> 00:30:09,477
有什麼含義，如果我交給你
一個數組，其長度n小於2？

647
00:30:09,477 --> 00:30:11,060
它已經排序，很明顯，對吧？

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

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

650
00:30:15,180 --> 00:30:18,138
或者說，它的大小為零，這意味著中
有天生什麼來排序，所以

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

652
00:30:18,720 --> 00:30:20,410
只是有沒有什麼不對勁的地方。

653
00:30:20,410 --> 00:30:22,310
這就是我們所謂的基本情況。

654
00:30:22,310 --> 00:30:24,440
>> 這是精神相似
以我們與麥克一樣。

655
00:30:24,440 --> 00:30:26,023
如果小李的電話本，打電話給他。

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

657
00:30:27,740 --> 00:30:31,240
這是一個所謂的基本情況，以確保
這個算法在一天結束時

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

659
00:30:33,540 --> 00:30:37,890
>> 但這裡的信仰的飛躍，現在，否則，
排序的元素的左半邊，

660
00:30:37,890 --> 00:30:39,740
然後進行排序的權利
一半的元素，

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

662
00:30:41,189 --> 00:30:43,230
而這裡也正是感覺
像我們科平了。

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

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

665
00:30:50,712 --> 00:30:52,420
但我嘴上說
其他的東西，這

666
00:30:52,420 --> 00:30:55,530
是看來關鍵主題
在直覺到目前為止，

667
00:30:55,530 --> 00:30:57,380
有合併的這個第三步驟。

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

669
00:31:00,430 --> 00:31:02,320
就像剛合併的東西
在一起，似乎

670
00:31:02,320 --> 00:31:05,380
為朝著一個關鍵步驟
兩個問題，即重組

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

672
00:31:07,330 --> 00:31:12,090
>> 所以，歸併排序，讓我們做到這一點，如果你願意
幽默的我，多了一個示範，

673
00:31:12,090 --> 00:31:14,730
只是讓我們有一些
數字與合作。

674
00:31:14,730 --> 00:31:19,470
我可以換8壓力
球八個人？

675
00:31:19,470 --> 00:31:29,320
好吧，你怎麼樣3，你們四個
在本節中，五，六，讓我們

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

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

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

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

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

681
00:31:39,150 --> 00:31:42,000
沒事上來吧，讓我們
趕緊給你的數字。

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

683
00:31:50,800 --> 00:31:52,140
我沒有做過8這個時候。

684
00:31:52,140 --> 00:31:56,390
>> 好了，如果你可以去進取，
讓我們梳理了原來的順序

685
00:31:56,390 --> 00:31:59,810
我們昨天看了這
這樣，如果你​​不介意的話。

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

687
00:32:03,620 --> 00:32:06,510
好吧，那麼歸併排序。

688
00:32:06,510 --> 00:32:08,820
這是到哪裡去
獲得有趣的一種，

689
00:32:08,820 --> 00:32:12,800
因為我似乎給自己
這麼多的信息較少今天。

690
00:32:12,800 --> 00:32:15,149
>> 所以歸併排序首先
對n個元素的輸入，

691
00:32:15,149 --> 00:32:18,440
這顯然不是少了兩個比，它的
8，讓我有更多的工作要做。

692
00:32:18,440 --> 00:32:21,140
所以，現在我們精神上的類
現在在else分支，

693
00:32:21,140 --> 00:32:22,540
這意味著三個步驟。

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

695
00:32:25,017 --> 00:32:26,350
那麼，如何去這樣做？

696
00:32:26,350 --> 00:32:28,950
好吧，我要種
精神上將列表在這裡，

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

698
00:32:30,700 --> 00:32:33,180
打算只把重點放在
這裡的元素的左半邊。

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

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

701
00:32:38,730 --> 00:32:42,580
首先我檢查為n比少了兩個，不，
所以我繼續在else塊了。

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

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

704
00:32:45,608 --> 00:32:49,550
你必須累積了大量的
精神的歷史，如果你願意。

705
00:32:49,550 --> 00:32:51,940
現在我左邊的分類
一半的左半部。

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

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

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

709
00:33:02,042 --> 00:33:03,750
為什麼不乾脆
走了一步。

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

711
00:33:04,415 --> 00:33:04,860
>> 聽眾：達倫。

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

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

714
00:33:06,040 --> 00:33:06,748
>> 聽眾：達倫。

715
00:33:06,748 --> 00:33:09,000
演講嘉賓：達倫，完成。

716
00:33:09,000 --> 00:33:10,090
你說達倫還是丹？

717
00:33:10,090 --> 00:33:10,550
>> 聽眾：達倫。

718
00:33:10,550 --> 00:33:11,216
>> 演講嘉賓：達倫。

719
00:33:11,216 --> 00:33:14,422
好吧，達倫已加強
向前和他現在排序。

720
00:33:14,422 --> 00:33:16,130
這幾乎是一個
空洞的說法，對嗎？

721
00:33:16,130 --> 00:33:18,862
我豈不真的似乎要實現
任何事情，但是讓我們繼續。

722
00:33:18,862 --> 00:33:20,820
現在讓我排序的權利
一半的元素。

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

724
00:33:21,200 --> 00:33:21,690
>> 聽眾：盧克。

725
00:33:21,690 --> 00:33:22,273
>> 演講嘉賓：盧克。

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

727
00:33:23,400 --> 00:33:25,640
完成後，我已經整理盧克。

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

729
00:33:28,570 --> 00:33:30,770
但同樣的，這裡有一個關鍵的步驟。

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

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

732
00:33:33,941 --> 00:33:36,648
現在我們只是有
大家來回這種方式，

733
00:33:36,648 --> 00:33:38,620
因為那種我需要的
一些暫存空間。

734
00:33:38,620 --> 00:33:40,411
這幾乎就像這些
傢伙都在桌子上，

735
00:33:40,411 --> 00:33:42,460
我需要一些空間
移動至周圍。

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

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

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

739
00:33:48,740 --> 00:33:52,710
所以，正確的上半年，讓我們在移動路
這裡達倫的原始位置。

740
00:33:52,710 --> 00:33:57,640
現在合併他們的左半部分，
達倫是怎麼回事向右移動那裡。

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

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

743
00:34:02,482 --> 00:34:04,815
但現在也正是事情變得
有點討厭，因為你

744
00:34:04,815 --> 00:34:06,810
要倒帶精神
在哪裡我離開了。

745
00:34:06,810 --> 00:34:09,893
我剛剛合併排序的一半，
這意味著我在我的算法是在哪裡呢？

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

747
00:34:12,229 --> 00:34:13,770
我的右半邊進行排序，對不對？

748
00:34:13,770 --> 00:34:15,910
>> 如果你後退，從字面上
在視頻中，您將

749
00:34:15,910 --> 00:34:18,339
看到我們到了這
點盧克和達倫的

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

751
00:34:21,370 --> 00:34:23,430
然後，我們的合併
排序一半，這

752
00:34:23,430 --> 00:34:27,941
裝置的下一步驟是分類的
左半部右半部。

753
00:34:27,941 --> 00:34:29,649
好吧，讓我們
更迅速地做到這一點。

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

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

756
00:34:33,990 --> 00:34:34,589
>> 聽眾：阿德里亞諾。

757
00:34:34,589 --> 00:34:35,200
>> 演講嘉賓：阿德里亞諾。

758
00:34:35,200 --> 00:34:36,010
阿德里亞諾現在排序。

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

760
00:34:36,450 --> 00:34:37,080
>> 聽眾：亞歷克斯。

761
00:34:37,080 --> 00:34:38,379
>> 演講嘉賓：亞歷克斯現在排序。

762
00:34:38,379 --> 00:34:40,750
左前衛，右前衛，
什麼是最後一步？

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

764
00:34:41,250 --> 00:34:44,310
很瑣碎，所以我
要在六個月合併，

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

766
00:34:46,930 --> 00:34:49,530
現在發現這是
一個有用的外賣，有什麼

767
00:34:49,530 --> 00:34:53,930
現在真正對的左半
列表中，不管我們怎麼開始的？

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

769
00:34:55,090 --> 00:34:57,750
>> 現在，它不是在整理
物聯網的大計劃，

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

771
00:35:00,250 --> 00:35:04,100
現在哪一步我是在如果我堅持
複捲怎麼回事開始？

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

773
00:35:05,680 --> 00:35:07,630
所以，現在我們回來的路上，在
故事的開始，

774
00:35:07,630 --> 00:35:08,921
並讓我們這樣做更為迅速。

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

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

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

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

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

780
00:35:19,590 --> 00:35:20,230
>> 聽眾：奧馬爾。

781
00:35:20,230 --> 00:35:21,970
>> 演講嘉賓：奧馬爾，向前一步，完成。

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

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

784
00:35:23,330 --> 00:35:23,820
>> 聽眾：克里斯。

785
00:35:23,820 --> 00:35:25,620
>> 演講嘉賓：克里斯，退一步
未來，你現在來分類的。

786
00:35:25,620 --> 00:35:27,010
什麼是現在的關鍵一步？

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

788
00:35:27,510 --> 00:35:30,509
所以，一個人要融入地方
在這裡，如果你能退後一步，

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

790
00:35:32,930 --> 00:35:38,080
這樣的左半
右半部，現已排序。

791
00:35:38,080 --> 00:35:41,747
坦率地說，這個算法感覺就像我們
這是在浪費這樣的時間比以前，

792
00:35:41,747 --> 00:35:44,830
但如果我們在實時這樣做，我們將
看到外賣成為怎樣的人。

793
00:35:44,830 --> 00:35:47,970
現在我在這裡，對不對
一半的右邊一半的，

794
00:35:47,970 --> 00:35:50,170
讓我繼續前進，排序的左半部。

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

796
00:35:51,482 --> 00:35:52,190
聽眾：拉姆齊。

797
00:35:52,190 --> 00:35:53,210
演講嘉賓：拉姆齊現在排序。

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

799
00:35:53,570 --> 00:35:54,200
>> 聽眾：碼頭。

800
00:35:54,200 --> 00:35:57,033
>> 演講嘉賓：濱海現在排序，
好吧，如果你走了一步。

801
00:35:57,033 --> 00:36:00,690
這裡關鍵的一步，現在被合併，我
打算從我的兩個列表採摘，

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

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

804
00:36:05,150 --> 00:36:06,410
再次，這是故意的。

805
00:36:06,410 --> 00:36:08,535
他們正在做的事實
步驟前進和後退

806
00:36:08,535 --> 00:36:12,997
是代表我們不能
這樣做算法的地方，很容易

807
00:36:12,997 --> 00:36:15,830
如冒泡排序和選擇排序，
和插入排序，我們只是

808
00:36:15,830 --> 00:36:16,960
不停交換的人。

809
00:36:16,960 --> 00:36:19,940
我真的需要一個排序
草稿紙在其中

810
00:36:19,940 --> 00:36:21,827
把這些人
而我的融合，

811
00:36:21,827 --> 00:36:23,410
然後我可以把它們放回原處。

812
00:36:23,410 --> 00:36:27,260
這就是關鍵，因為我使用的是
新的資源，空間，而不僅僅是時間。

813
00:36:27,260 --> 00:36:28,270
>> OK，這是驚人的。

814
00:36:28,270 --> 00:36:32,050
左半部分是排序，右半部分是
排序的，現在的關鍵合成步驟。

815
00:36:32,050 --> 00:36:33,450
我怎麼合併呢？

816
00:36:33,450 --> 00:36:35,470
所以，如果你按照我
左手和右手

817
00:36:35,470 --> 00:36:38,930
我要指出我的左手
在左前衛，我的右手

818
00:36:38,930 --> 00:36:42,680
在右前衛的，現在我要
決定一步步誰在合併。

819
00:36:42,680 --> 00:36:44,650
誰顯然是第一位的？

820
00:36:44,650 --> 00:36:45,150
第一。

821
00:36:45,150 --> 00:36:47,327
所以來這邊，
這裡是我們的便箋。

822
00:36:47,327 --> 00:36:49,910
所以，現在排名第一，並通知
我會盡我的右手，

823
00:36:49,910 --> 00:36:54,152
我打算將我的右手1
跳過來點排名第三，

824
00:36:54,152 --> 00:36:55,860
現在我要
同樣的決定。

825
00:36:55,860 --> 00:36:58,387
而實際上站在正確的
盧克在這裡，如果你能面前，

826
00:36:58,387 --> 00:36:59,720
因為這是我們的便箋。

827
00:36:59,720 --> 00:37:00,610
那麼，誰隨之而來的？

828
00:37:00,610 --> 00:37:05,000
我們有盧克與排名第二
或者克里斯與排名第三。

829
00:37:05,000 --> 00:37:07,460
顯然盧克，數
2，讓你來這裡。

830
00:37:07,460 --> 00:37:11,270
>> 但是，我的左手現在是要
遞增為指向達倫，

831
00:37:11,270 --> 00:37:15,160
而這裡的關鍵拿走了
合併，我將繼續這樣做，

832
00:37:15,160 --> 00:37:17,340
很明顯，如果你有種
遵循的邏輯。

833
00:37:17,340 --> 00:37:19,670
但我的手都從未
要往回走，

834
00:37:19,670 --> 00:37:23,861
這意味著我永遠只能移動到
左邊有我的合併過程，

835
00:37:23,861 --> 00:37:26,360
那將是關鍵
我們的分析在短短的一瞬間。

836
00:37:26,360 --> 00:37:27,859
>> 所以，現在讓我們迅速完成這件事。

837
00:37:27,859 --> 00:37:31,650
所以三隨之而來的，
然後4隨之而來的，

838
00:37:31,650 --> 00:37:38,750
現在5隨之而來的，則6，
七，最後8。

839
00:37:38,750 --> 00:37:42,960
感覺就像是最慢的算法
然而，但如果我們真的

840
00:37:42,960 --> 00:37:45,510
在相同的排序運行
時鐘速度的，所以要

841
00:37:45,510 --> 00:37:48,106
說，具有相同的
滴答作響的時鐘和以前一樣。

842
00:37:48,106 --> 00:37:48,605
為什麼呢？

843
00:37:48,605 --> 00:37:51,100
好吧，讓我們來
看的最終結果。

844
00:37:51,100 --> 00:37:56,990
>> 讓我們回到了這裡，讓我
拉了一個直觀演示

845
00:37:56,990 --> 00:37:59,030
什麼，我們只是做了。

846
00:37:59,030 --> 00:38:06,110
放大在這裡，在這個
在此頁面，告訴火狐

847
00:38:06,110 --> 00:38:08,200
我們要排隊
在此框，讓我們

848
00:38:08,200 --> 00:38:11,260
說冒泡排序，與
我們現在非常熟悉，

849
00:38:11,260 --> 00:38:14,130
選擇排序，這是另一種
相當簡單的，

850
00:38:14,130 --> 00:38:18,250
現在今天的歸併排序，其中
將是我們的高潮結局。

851
00:38:18,250 --> 00:38:21,530
花了這麼多時間越長的原因
這裡有人類和我口頭上的，

852
00:38:21,530 --> 00:38:23,480
很明顯，我解釋每一步。

853
00:38:23,480 --> 00:38:26,920
但如果你只需要執行這一點，很多
像我們做冒泡排序和選擇

854
00:38:26,920 --> 00:38:30,890
排序不僅在視覺上，觀看
到底有多少更有效

855
00:38:30,890 --> 00:38:33,330
這個槓桿化
分裂和征服

856
00:38:33,330 --> 00:38:39,150
可以在應用到數據集的
即使沒有大小八，但即使多了，

857
00:38:39,150 --> 00:38:39,970
要大得多。

858
00:38:39,970 --> 00:38:44,585
我給你通過歸併排序，方
方用這些算法。

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
這是會得到痛苦
很快，並且結束

861
00:38:58,530 --> 00:39:00,890
沒有特別的高潮，
他們剛剛結束了排序。

862
00:39:00,890 --> 00:39:05,280
但關鍵帶走的是
看快多少排序合併

863
00:39:05,280 --> 00:39:08,110
是的，除非你覺得我
只是那種玩弄你。

864
00:39:08,110 --> 00:39:13,100
如果我們這樣做了，最後一次，
讓我們重新加載此，讓我們回去

865
00:39:13,100 --> 00:39:14,960
選擇冒泡排序，
而只是踢，

866
00:39:14,960 --> 00:39:17,330
讓我們來選擇插入
排序，只是為了好措施。

867
00:39:17,330 --> 00:39:20,020
而這一次又一次，讓我們
選擇合併排序，讓我們

868
00:39:20,020 --> 00:39:21,595
實際上並排運行這些側。

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> 它不是，其實是僥倖。

871
00:39:26,930 --> 00:39:31,140
我已經做了有效的是我
分我輸入了一半，同樣，

872
00:39:31,140 --> 00:39:32,240
又一次，又一次。

873
00:39:32,240 --> 00:39:35,590
而且也只有這麼多的時候，你可以
將您的輸入成兩半，左

874
00:39:35,590 --> 00:39:36,240
右。

875
00:39:36,240 --> 00:39:39,425
那是什麼，我們總是看到公式
描述該師在半

876
00:39:39,425 --> 00:39:41,050
一次，又一次，又一次，又一次？

877
00:39:41,050 --> 00:39:41,890
>> 聽眾：日誌N。

878
00:39:41,890 --> 00:39:42,760
>> 演講嘉賓：日誌N。

879
00:39:42,760 --> 00:39:46,300
但還有另一個關鍵的一步，
這種算法是不記錄n步。

880
00:39:46,300 --> 00:39:48,992
如果它僅記錄n步，
我們將在同樣的問題

881
00:39:48,992 --> 00:39:51,200
如之前在這裡我們不能
確保一切的排序。

882
00:39:51,200 --> 00:39:54,480
你必須微創看看n個元素
可以肯定的n個元素進行排序，

883
00:39:54,480 --> 00:39:55,950
否則就是信仰的飛躍。

884
00:39:55,950 --> 00:39:59,810
>> 所以它的最低限度日誌n步，但
那麼這個合併的關鍵一步

885
00:39:59,810 --> 00:40:04,370
在這裡我合併了我的左半邊，右
半走過的階段？

886
00:40:04,370 --> 00:40:06,980
多少個步驟是合併？

887
00:40:06,980 --> 00:40:10,150
這是N，但我不只是
合併的最後時間。

888
00:40:10,150 --> 00:40:15,089
在每個這些嵌套調用，每個
這些嵌套的合併，我還是整理。

889
00:40:15,089 --> 00:40:18,380
我將這這兩個傢伙，那麼這兩個
男人，那麼這兩個傢伙，等等。

890
00:40:18,380 --> 00:40:19,955
>> 所以，我沒有再合併，再。

891
00:40:19,955 --> 00:40:20,580
多少次？

892
00:40:20,580 --> 00:40:23,510
所以每次我分了
列表中的一半，我做了合併。

893
00:40:23,510 --> 00:40:25,460
將列表中的一半，做了合併。

894
00:40:25,460 --> 00:40:28,570
因此，如果分割清單
可以做日誌的n倍，

895
00:40:28,570 --> 00:40:33,880
和合併，最終佔據N
步驟，可能是什麼，現在的上

896
00:40:33,880 --> 00:40:37,000
結合在跑步
我們的算法的時間呢？

897
00:40:37,000 --> 00:40:37,980
Ñ​​日誌N。

898
00:40:37,980 --> 00:40:40,560
>> 事實上，這就是
我們在這裡實現。

899
00:40:40,560 --> 00:40:44,650
所以，你看到的時候視覺上的感覺
這三樣東西並行走線

900
00:40:44,650 --> 00:40:47,930
為n的平方與n的
平方與n的日誌ñ。

901
00:40:47,930 --> 00:40:51,010
這從根本上，我們會看到，
不僅是現在，而且在將來，

902
00:40:51,010 --> 00:40:52,760
是非常非常快。

903
00:40:52,760 --> 00:40:56,010
掌聲鼓勵了這些傢伙，
我會獎勵他們壓力球。

904
00:40:56,010 --> 00:41:00,260
讓我們今天在這裡宣布休會，並
我們會看到你在星期一。

905
00:41:00,260 --> 00:41:02,255