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

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

3
00:00:10,800 --> 00:00:13,500
國寶馬蘭所有權利。

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

5
00:00:14,670 --> 00:00:18,120
因此，這是第4週，開始
其已經。

6
00:00:18,120 --> 00:00:21,320
你還記得，上週，我們把
編碼一旁只是一點點

7
00:00:21,320 --> 00:00:24,240
我們開始交談多一點
高層次，一樣的東西

8
00:00:24,240 --> 00:00:28,130
搜索和排序，這雖然
有些簡單的想法，

9
00:00:28,130 --> 00:00:31,840
代表的一類問題
你將開始解決特別

10
00:00:31,840 --> 00:00:34,820
當你開始思考最終
項目和有趣的解決方案

11
00:00:34,820 --> 00:00:36,760
可能有現實世界的問題。

12
00:00:36,760 --> 00:00:39,490
現在是一個最簡單的冒泡排序
這樣的算法，它

13
00:00:39,490 --> 00:00:42,900
通過這些小的數字工作
在一個列表中，或在一個數組中種

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

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

16
00:00:47,930 --> 00:00:50,650
>> 記得我們可以想像
一點點的冒泡排序

17
00:00:50,650 --> 00:00:52,310
這樣的事情。

18
00:00:52,310 --> 00:00:53,640
所以，讓我繼續前進，單擊“開始”。

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

20
00:00:55,350 --> 00:00:58,920
如果你還記得，高大的藍色
線代表大號碼，小

21
00:00:58,920 --> 00:01:03,300
藍線代表小數字，
我們通過這一而再，再而

22
00:01:03,300 --> 00:01:07,680
再次，比較相鄰的兩間酒吧
紅色，我們要交換

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

24
00:01:11,010 --> 00:01:14,150
>> 因此，這會去，去，去
，你會看到，較大的

25
00:01:14,150 --> 00:01:16,700
元素使他們的方式
的權利，而較小的元素是

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

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

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

29
00:01:22,970 --> 00:01:25,200
和我們說，在最壞
情況下，該算法採取了

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

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

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

33
00:01:30,402 --> 00:01:31,650
>> 觀眾：元素數目。

34
00:01:31,650 --> 00:01:32,790
>> 國寶馬蘭因此n
數目的元素。

35
00:01:32,790 --> 00:01:33,730
所以我們經常這樣做。

36
00:01:33,730 --> 00:01:36,650
任何時候，我們要談論的大小
一個問題或大小的

37
00:01:36,650 --> 00:01:39,140
輸入，或花費的時間量
以產生輸出，我們只

38
00:01:39,140 --> 00:01:41,610
廣義的任何
輸入為n。

39
00:01:41,610 --> 00:01:45,970
因此，早在第0週，數頁
在電話簿為n。

40
00:01:45,970 --> 00:01:47,550
學生人數
在房間裡為：N。

41
00:01:47,550 --> 00:01:49,630
所以在這裡，太，我們繼
這個模式。

42
00:01:49,630 --> 00:01:52,800
>> 現在Ñ平方是不是特別
快，所以我們試圖做的更好。

43
00:01:52,800 --> 00:01:55,970
因此，我們看著一對夫婦
其他的算法，其中

44
00:01:55,970 --> 00:01:57,690
選擇排序。

45
00:01:57,690 --> 00:01:59,180
所以選擇排序
有一點不同。

46
00:01:59,180 --> 00:02:03,130
這幾乎是簡單的，我敢說，
由此開始的開始

47
00:02:03,130 --> 00:02:06,740
我們的志願者名單，我只是再次
一次又一次經歷

48
00:02:06,740 --> 00:02:10,060
列表，採摘最小
在一個時間元素，並把他或

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

50
00:02:13,040 --> 00:02:16,410
>> 但是它也同樣，一旦我們開始思考
通過數學和更大的

51
00:02:16,410 --> 00:02:19,860
圖片，想過多少次
我正想來回和背部

52
00:02:19,860 --> 00:02:24,090
奔波，我們說，在最壞的情況下，
太多，選擇排序，那是什麼？

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

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

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

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

57
00:02:31,880 --> 00:02:35,090
但是，如果我們想想n很大，
如果你的，做出來的數學

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

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

60
00:02:41,850 --> 00:02:42,850
真正的問題一樣多。

61
00:02:42,850 --> 00:02:45,470
因此，作為計算機科學家，我們的排序
視而不見較小

62
00:02:45,470 --> 00:02:49,220
因素和只注重的因素
一個表達式，將會使

63
00:02:49,220 --> 00:02:50,330
最大的區別。

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

65
00:02:52,840 --> 00:02:56,620
這是類似的精神，但
而不是通過迭代

66
00:02:56,620 --> 00:03:01,250
選擇最小的元素之一，在
的時間，我只花了我的手

67
00:03:01,250 --> 00:03:04,070
處理，我決定，所有
沒錯，你屬於這裡。

68
00:03:04,070 --> 00:03:06,160
然後我轉移到下一個元素
並決定，他或

69
00:03:06,160 --> 00:03:07,470
她屬於這裡。

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

71
00:03:08,810 --> 00:03:11,780
我可能會，一路走來，
以這些傢伙轉移

72
00:03:11,780 --> 00:03:13,030
為他們騰出空間。

73
00:03:13,030 --> 00:03:16,880
所以這是樣的心理逆轉
選擇排序，我們

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

75
00:03:18,630 --> 00:03:20,810
>> 因此，這些主題發生
在現實世界中。

76
00:03:20,810 --> 00:03:23,640
僅僅在幾年前，當達到一定
參議員競選總統，

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

78
00:03:27,160 --> 00:03:28,040
採訪他。

79
00:03:28,040 --> 00:03:32,010
我們認為我們會分享此YouTube
夾你在這裡，如果我們可以將

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

81
00:03:32,950 --> 00:03:39,360
>> [視頻回放]

82
00:03:39,360 --> 00:03:44,620
>> 現在，參議員，你在谷歌，
我喜歡把總統

83
00:03:44,620 --> 00:03:46,042
作為一個工作面試。

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

85
00:03:47,770 --> 00:03:50,800
>> 現在它是很難得到
一個工作作為總統。

86
00:03:50,800 --> 00:03:52,480
你要通過
現在的嚴峻考驗。

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

88
00:03:54,330 --> 00:03:59,610
我們有問題，我們要求
我們的候選人的問題。

89
00:03:59,610 --> 00:04:02,250
而這一次是從拉里·施維默。

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

91
00:04:05,325 --> 00:04:06,400
你們覺得我在開玩笑嗎？

92
00:04:06,400 --> 00:04:08,750
就是這裡。

93
00:04:08,750 --> 00:04:12,110
這是最有效的方式來
排序一百萬兩位整數？

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

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

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

97
00:04:19,029 --> 00:04:19,745
也許我們應該 - 

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

99
00:04:21,000 --> 00:04:21,470
>> 這不是一個 - 

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

101
00:04:22,185 --> 00:04:25,328
>> 我認為冒泡排序
是錯誤的方式去。

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

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

104
00:04:28,510 --> 00:04:31,211
>> 來吧，誰告訴他這個呢？

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

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

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

108
00:04:35,070 --> 00:04:39,600
於是我們開始量化這些運行
倍，所以說話，用的東西

109
00:04:39,600 --> 00:04:43,480
被稱為漸近符號，這是
剛剛提到我們轉向排序

110
00:04:43,480 --> 00:04:47,420
視而不見，那些規模較小的因素，
只盯著運行時間，

111
00:04:47,420 --> 00:04:51,250
這些算法的性能
為n隨著時間的推移變得非常大。

112
00:04:51,250 --> 00:04:55,110
因此，我們介紹大澳大O
代表的東西，我們認為

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

114
00:04:57,000 --> 00:04:59,570
巴里，而實際上，我們可以降低
比話筒一點點？

115
00:04:59,570 --> 00:05:01,040
>> 我們認為這是一個上限。

116
00:05:01,040 --> 00:05:04,710
因此，大O在n的平方手段
最壞的情況下，類似的東西

117
00:05:04,710 --> 00:05:07,780
選擇排序
平方步驟Ń。

118
00:05:07,780 --> 00:05:10,310
或類似的東西插入排序
將Ñ平方步驟。

119
00:05:10,310 --> 00:05:15,150
現在像插入
排序，最壞的情況是什麼？

120
00:05:15,150 --> 00:05:18,200
給定一個數組，什麼是最糟糕的
可能發生的情況，你可能會發現

121
00:05:18,200 --> 00:05:20,650
自己面臨著？

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

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

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

125
00:05:26,420 --> 00:05:28,840
這裡最大的元素，即使
它屬於那裡。

126
00:05:28,840 --> 00:05:31,140
所以，你說，所有的權利，
時間在這一刻，你屬於這裡，

127
00:05:31,140 --> 00:05:32,310
所以你離開單幹。

128
00:05:32,310 --> 00:05:35,425
>> 然後你意識到，哦，該死的，我要
移動這種略小的元素

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

130
00:05:36,470 --> 00:05:38,770
然後我再這樣做
一遍又一遍。

131
00:05:38,770 --> 00:05:41,410
如果我來回走了，你
會有點感覺的表現

132
00:05:41,410 --> 00:05:45,540
這個算法，我因為不斷
其他人倒在洗牌

133
00:05:45,540 --> 00:05:46,510
陣列，以騰出空間。

134
00:05:46,510 --> 00:05:47,750
因此，這是最壞的情況。

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

136
00:05:48,570 --> 00:05:50,320
這是一個扣人心弦的最後一次 - 

137
00:05:50,320 --> 00:05:54,065
我們說，插入排序
是歐米茄的什麼？

138
00:05:54,065 --> 00:05:57,530
什麼是最好的情況下運行
插入排序的時間嗎？

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

140
00:05:58,520 --> 00:06:00,980
這是我們離開的空白
在黑板上的最後一次。

141
00:06:00,980 --> 00:06:03,160
>> 歐米茄的n，因為為什麼呢？

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

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

144
00:06:09,830 --> 00:06:12,460
但是，什麼是整齊插入排序
是，由於開始

145
00:06:12,460 --> 00:06:15,340
決定，哦，你的號碼
一，你屬於這裡。

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

147
00:06:16,970 --> 00:06:17,740
>> 你兩個數。

148
00:06:17,740 --> 00:06:19,030
你也屬於這裡。

149
00:06:19,030 --> 00:06:21,010
三，甚至更好，
你屬於這裡。

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

151
00:06:25,210 --> 00:06:28,010
我們走過口頭
最後一次，它的工作要做。

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

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

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

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

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

157
00:06:45,560 --> 00:06:48,920
因此，這些不同的心智模式結束
高達產生一些很現實世界

158
00:06:48,920 --> 00:06:53,130
為我們的差異，以及這些
理論漸近差異。

159
00:06:53,130 --> 00:06:56,910
>> 因此，只要回顧一下，然後，大O的n
平方，我們已經看到了一些這樣的

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

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

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

163
00:07:02,870 --> 00:07:06,930
在最壞的情況下，它需要
一個線性的步數。

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

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

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

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

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

169
00:07:17,000 --> 00:07:18,880
加或減去一個單步的差異。

170
00:07:18,880 --> 00:07:21,180
因此，在一天結束時，
我們可以說，它是線性的。

171
00:07:21,180 --> 00:07:23,910
大O n的線性搜索，
在最壞的情況下，因為

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

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

174
00:07:29,370 --> 00:07:32,760
我們沒有講的很詳細，關於
這一點，但我們已經看到了這一點。

175
00:07:32,760 --> 00:07:36,840
運行在所謂的對數
時間，在最壞的情況下？

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

177
00:07:38,500 --> 00:07:42,930
在最壞的情況下，和二進制搜索
可能具有元素中某處

178
00:07:42,930 --> 00:07:45,640
中間，或某處
陣列內。

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

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

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

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

183
00:07:52,500 --> 00:07:56,770
但你不知道它不存在
，直到你達到這最後

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

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

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

187
00:08:03,540 --> 00:08:06,260
任何時候你想只是一個常數，
我們僅僅只是簡化排序

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

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

190
00:08:10,440 --> 00:08:13,680
恆定數量的步​​驟，
我們只是說大O 1。

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

192
00:08:15,930 --> 00:08:18,350
>> 觀眾：查找長度
一個變量。

193
00:08:18,350 --> 00:08:21,090
>> 國寶馬蘭：尋找
一個變量的長度？

194
00:08:21,090 --> 00:08:23,870
>> 觀眾：沒有，長度
如果它已經排序。

195
00:08:23,870 --> 00:08:24,160
>> 國寶馬蘭：好。

196
00:08:24,160 --> 00:08:27,850
OK，所以尋找的東西的長度
如果長度的東西，如

197
00:08:27,850 --> 00:08:30,020
被存儲在一個數組中，一些變量。

198
00:08:30,020 --> 00:08:33,380
因為你可以讀取該變量，
或打印變量，或

199
00:08:33,380 --> 00:08:34,960
只是一般訪問該變量。

200
00:08:34,960 --> 00:08:37,299
瞧，這需要恆定的時間。

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

202
00:08:38,909 --> 00:08:42,460
回想第一週的C，
僅調用printf和打印

203
00:08:42,460 --> 00:08:46,240
屏幕上的東西可以說是
恆定的時間，因為它只是需要

204
00:08:46,240 --> 00:08:50,880
一些CPU週期數顯示
該屏幕上的文字。

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

206
00:08:52,720 --> 00:08:56,430
否則怎麼可能我們模型
printf的表現？

207
00:08:56,430 --> 00:09:00,420
有人會不以為然，
也許這不是真的恆定的時間嗎？

208
00:09:00,420 --> 00:09:03,600
在什麼意義上的printf可能運行
時間，實際打印字符串

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

210
00:09:05,580 --> 00:09:07,860
>> 觀眾：[聽不清]。

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

212
00:09:08,230 --> 00:09:09,300
因此，它取決於我們的角度來看。

213
00:09:09,300 --> 00:09:13,390
如果我們真的想輸入
作為字符串的printf，

214
00:09:13,390 --> 00:09:16,380
因此，我們測量的大小，
輸入的長度 - 所以姑且稱之為

215
00:09:16,380 --> 00:09:17,780
該長度為n，以及 - 

216
00:09:17,780 --> 00:09:21,990
可以說，printf是本身的n大O
因為它會帶你n步

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

218
00:09:24,750 --> 00:09:27,730
至少，我們假設的程度
也許它使用for循環

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

220
00:09:28,560 --> 00:09:30,860
>> 不過，我們將不得不看
編寫更好地理解它。

221
00:09:30,860 --> 00:09:33,650
而事實上，一旦你們開始
分析自己的算法，你會

222
00:09:33,650 --> 00:09:34,900
從字面上做到這一點。

223
00:09:34,900 --> 00:09:37,765
眼球排序的代碼，並認為
 - 所有的權利，我有這樣的循環

224
00:09:37,765 --> 00:09:41,870
否則我這裡有一個嵌套循環，
做N事物n次，

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

226
00:09:46,050 --> 00:09:47,980
偽代碼，而不是實際的代碼。

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

228
00:09:49,730 --> 00:09:53,582
這是一個算法，在最好的
的情況下，仍然採取Ñ平方的步驟嗎？

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

230
00:09:54,014 --> 00:09:54,880
>> 觀眾：[聽不清]。

231
00:09:54,880 --> 00:09:55,900
>> 國寶馬蘭：所以選擇排序。

232
00:09:55,900 --> 00:09:59,150
因為在這個問題確實減少
這樣的事實，再次，我不知道

233
00:09:59,150 --> 00:10:02,600
我發現目前最小的，直到
我檢查了所有的混賬元素。

234
00:10:02,600 --> 00:10:08,050
因此，歐米茄，我們說，正
只是想出了一個。

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

236
00:10:09,300 --> 00:10:12,370
如果列表進行排序發生
已經在最好的情況下，我們只需要

237
00:10:12,370 --> 00:10:15,090
通過一次，
在這一點上，我們肯定。

238
00:10:15,090 --> 00:10:17,890
然後，可以說
是線性的，是肯定的。

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

240
00:10:20,570 --> 00:10:23,790
什麼，在最好的情況下，可能需要
固定數量的步​​驟？

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

242
00:10:27,220 --> 00:10:31,000
在列表的開頭是正確的，
如果這是您在何處開始

243
00:10:31,000 --> 00:10:33,070
線性遍歷該列表。

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

245
00:10:35,180 --> 00:10:37,660
舉例來說，即使二進制
搜尋歐米加1。

246
00:10:37,660 --> 00:10:40,310
因為如果你得到真正的織補
幸運和咂嘴-DAB的中間

247
00:10:40,310 --> 00:10:42,950
您的陣列是多少
你要買什麼？

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

249
00:10:45,730 --> 00:10:49,190
>> 這其中，最後，ωn日誌n。

250
00:10:49,190 --> 00:10:52,573
因此n日誌n，我們並沒有真正
談談，但 - 

251
00:10:52,573 --> 00:10:53,300
>> 觀眾：合併排序？

252
00:10:53,300 --> 00:10:53,960
>> 國寶馬蘭：合併排序。

253
00:10:53,960 --> 00:10:56,920
這是扣人心弦的最後時間，
我們提出，我們發現

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

255
00:10:58,600 --> 00:11:02,470
並合併排序只是一個這樣的
基本上是更快的算法，該算法

256
00:11:02,470 --> 00:11:03,450
一些這些傢伙。

257
00:11:03,450 --> 00:11:07,800
事實上，合併潛在不僅在
當n日誌N，在最壞的

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

259
00:11:09,460 --> 00:11:14,540
而當你有這樣的巧合
歐米茄和大O是同樣的事情？

260
00:11:14,540 --> 00:11:17,310
事實上，我們可以描述什麼
稱為θ，然而它是一個

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

262
00:11:18,220 --> 00:11:21,730
但是，這只是意味著兩個界限，
在這種情況下是相同的。

263
00:11:21,730 --> 00:11:25,770
>> 所以合併排序，這是什麼
真正歸結到我們嗎？

264
00:11:25,770 --> 00:11:27,000
嗯，記得的動機。

265
00:11:27,000 --> 00:11:30,340
讓我拉起另一個動畫
我們沒有看最後一次。

266
00:11:30,340 --> 00:11:33,390
這一次，同樣的想法，但
它是一個更大一點。

267
00:11:33,390 --> 00:11:36,160
而且我要繼續前進並指出
第一 - 我們有插入排序

268
00:11:36,160 --> 00:11:39,410
左上角，然後選擇排序，
冒泡排序，一對夫婦的其他種類 - 

269
00:11:39,410 --> 00:11:42,670
外殼和快速 - 我們沒有談到
，堆和歸併排序。

270
00:11:42,670 --> 00:11:47,090
>> 因此，至少盡量集中你的眼睛
頂端3的左邊，然後

271
00:11:47,090 --> 00:11:49,120
歸併排序，當我點擊
這個綠色的箭頭。

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

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

274
00:11:53,980 --> 00:11:56,180
我打算讓這個運行
短短的幾秒鐘。

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

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

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

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

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

280
00:12:09,480 --> 00:12:12,960
但是，這是很好的，我們今天在這裡
看歸併排序，這是一個

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

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

283
00:12:17,490 --> 00:12:21,130
在這裡我們可以看到多少
選擇排序吸。

284
00:12:21,130 --> 00:12:24,600
>> 但在另一面，它是
確實很容易實現。

285
00:12:24,600 --> 00:12:28,160
也許P設置3，這是一個
算法選擇實施

286
00:12:28,160 --> 00:12:28,960
標準版。

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

288
00:12:30,970 --> 00:12:35,210
>> 但同樣，當n變大，如果你
選擇來實現更快的算法

289
00:12:35,210 --> 00:12:39,020
喜歡歸併排序，賠率是較大且
更大的投入，你的代碼僅僅是

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

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

292
00:12:41,090 --> 00:12:42,650
你的用戶會更快樂。

293
00:12:42,650 --> 00:12:45,280
因此，有這些效果
實際上是給

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

295
00:12:47,350 --> 00:12:49,990
>> 因此，讓我們來看看什麼合併
排序實際上是一回事。

296
00:12:49,990 --> 00:12:52,992
很酷的事情是，合併
排序僅僅是這一點。

297
00:12:52,992 --> 00:12:56,300
再次，這是我們稱為什麼
偽代碼，偽代碼的存在

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

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

300
00:12:59,890 --> 00:13:02,840
>> 所以輸入n個元素 - 
只是意味著，這裡是一個數組。

301
00:13:02,840 --> 00:13:04,000
它有著N個東西。

302
00:13:04,000 --> 00:13:05,370
這就是我們說有。

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

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

305
00:13:08,640 --> 00:13:12,580
如果n是小於2，那麼它顯然
1或0，在這種情況下的事情

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

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

308
00:13:15,900 --> 00:13:18,360
因此，這是一個簡單的情況下拔掉。

309
00:13:18,360 --> 00:13:20,110
>> 否則，我們有三個步驟。

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

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

312
00:13:26,650 --> 00:13:29,400
這裡，有趣的是，
我樣的撐船，對不對？

313
00:13:29,400 --> 00:13:32,300
有一種循環定義
該算法。

314
00:13:32,300 --> 00:13:35,986
在什麼意義上是這樣的算法
定義圓？

315
00:13:35,986 --> 00:13:37,850
>> 觀眾：[聽不清]。

316
00:13:37,850 --> 00:13:41,670
>> 國寶馬蘭：是啊，我的排序算法，
它的兩個步驟“排序

317
00:13:41,670 --> 00:13:44,640
東西。“於是引出了一個
的問題，以及什麼我要使用

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

319
00:13:46,460 --> 00:13:49,600
而這裡的美景，即使
再次，這是心態彎曲

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

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

322
00:13:54,700 --> 00:13:57,070
當有人告訴你排序
左前衛，什麼是兩個

323
00:13:57,070 --> 00:13:58,240
步驟將成為下一個？

324
00:13:58,240 --> 00:14:00,550
我們將左半部分進行排序
左半邊和右

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

326
00:14:01,420 --> 00:14:04,430
該死，我怎麼排序，這兩個
半，或宿舍，現在呢？

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

328
00:14:05,260 --> 00:14:07,830
我們這裡有一個排序算法。

329
00:14:07,830 --> 00:14:10,660
即使你可能會擔心
首先，這是一種無限

330
00:14:10,660 --> 00:14:12,780
循環，這是一個週期，這是從來沒有的
將要結束 - 它是將

331
00:14:12,780 --> 00:14:15,770
最後一次發生了什麼？

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

333
00:14:16,970 --> 00:14:19,180
最終將要發生，
因為如果你繼續減半

334
00:14:19,180 --> 00:14:23,020
減半在減半這些半，肯定
最終，你要結束

335
00:14:23,020 --> 00:14:25,350
與僅有1或0個元素。

336
00:14:25,350 --> 00:14:28,500
在這一點上，這種算法
說，你就大功告成了。

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

338
00:14:31,020 --> 00:14:33,470
這最後的一步，合併。

339
00:14:33,470 --> 00:14:37,190
那個簡單的想法，只是合併兩個
的東西，這就是最終的

340
00:14:37,190 --> 00:14:40,920
讓我們對數組進行排序，
比方說，8個元素。

341
00:14:40,920 --> 00:14:44,410
所以，我有八個壓力球
在這裡，8個紙片，和一個

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

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

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

345
00:14:46,960 --> 00:14:48,970
>> DAVID馬蘭：如果我們可能需要8
志願者，讓我們來看看，如果我們能

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

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

348
00:14:52,500 --> 00:14:53,565
計算機科學是越來越有趣。

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

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

351
00:14:57,770 --> 00:14:58,580
四個在後面。

352
00:14:58,580 --> 00:15:02,220
怎麼樣，我們會做你
三此行？

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

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

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

356
00:15:12,060 --> 00:15:13,450
>> 國寶馬蘭：我其實
不知道它是什麼。

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

358
00:15:14,810 --> 00:15:16,510
檯燈？

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

360
00:15:18,650 --> 00:15:19,680
在互聯網上？

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

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

363
00:15:21,310 --> 00:15:22,310
誰願意 - 

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

365
00:15:23,570 --> 00:15:24,240
讓我們來看看。

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

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

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

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

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

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

372
00:15:35,130 --> 00:15:36,475
讓我排隊這些了。

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

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

375
00:15:37,440 --> 00:15:38,090
>> 國寶馬蘭：米歇爾？

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

377
00:15:42,000 --> 00:15:44,625
嗯，我也這樣做，我想，
只是一瞬間。

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

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

380
00:15:48,510 --> 00:15:50,950
我們一直試圖想出一個
使用的情況下，我們對Google玻璃

381
00:15:50,950 --> 00:15:53,750
認為這將是有趣的只是做
當人們在舞台上。

382
00:15:53,750 --> 00:15:57,120
我們會記錄世界
從他們的角度。

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

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

385
00:15:59,830 --> 00:16:02,260
好吧，如果你不介意穿
這下一尷尬分鐘​​，

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

387
00:16:03,150 --> 00:16:08,620
>> 所有的權利，所以我們這裡有一個數組
元素，該陣列，每

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

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

390
00:16:12,050 --> 00:16:12,810
>> DAVID馬蘭：這是非常隨機的。

391
00:16:12,810 --> 00:16:15,760
在短短的時刻，我們要嘗試
實施合併排序

392
00:16:15,760 --> 00:16:17,950
看到這一關鍵洞察力。

393
00:16:17,950 --> 00:16:21,970
這裡的技巧與歸併排序
的東西，我們沒有假設。

394
00:16:21,970 --> 00:16:24,030
我們確實需要一些
額外的空間。

395
00:16:24,030 --> 00:16:26,650
那麼，這是怎麼回事要特別
有趣的是，這些

396
00:16:26,650 --> 00:16:29,270
附近有一座小傢伙要移動
位，因為我將假設

397
00:16:29,270 --> 00:16:31,880
有一個額外的數組空間，
也就是說，在他們身後。

398
00:16:31,880 --> 00:16:34,570
>> 所以，如果他們自己的椅子後面，
這是輔助陣列。

399
00:16:34,570 --> 00:16:36,960
如果他們坐在這裡，這是
主陣列。

400
00:16:36,960 --> 00:16:40,170
但是，這是一種資源，我們有
迄今沒有利用泡沫

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

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

403
00:16:44,600 --> 00:16:46,840
他們沒有使用任何額外的內存。

404
00:16:46,840 --> 00:16:49,310
我們的空間讓人們
移動周圍的人。

405
00:16:49,310 --> 00:16:50,580
>> 因此，這是一個關鍵的洞察力。

406
00:16:50,580 --> 00:16:53,410
有這種權衡，一般在
計算機科學，資源。

407
00:16:53,410 --> 00:16:55,800
如果你想加快東西
如時間，你要

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

409
00:16:56,900 --> 00:17:00,750
那些價格是非常頻繁
空間的內存量或硬

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

411
00:17:01,700 --> 00:17:03,640
或者，坦率地說，
程序員的時間。

412
00:17:03,640 --> 00:17:06,700
多少時間，它需要你，人類，
真正實現多一些

413
00:17:06,700 --> 00:17:07,829
複雜的算法。

414
00:17:07,829 --> 00:17:09,760
但今天，權衡
是時間和空間。

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

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

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

418
00:17:16,599 --> 00:17:19,520
所以我要去嘗試，以協調
的東西，如果你們可以只

419
00:17:19,520 --> 00:17:21,800
跟隨我的領導在這裡。

420
00:17:21,800 --> 00:17:26,650
>> 所以，我要實現，首先，
第一步驟的偽代碼，這是

421
00:17:26,650 --> 00:17:29,440
在輸入n個元素，如果n是
小於2，然後返回。

422
00:17:29,440 --> 00:17:31,370
顯然，這不
適用，因此我們繼續前進。

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

424
00:17:33,340 --> 00:17:36,220
因此，這意味著我要專注我
這些只是一瞬間的關注

425
00:17:36,220 --> 00:17:37,310
四個傢伙在這裡。

426
00:17:37,310 --> 00:17:39,774
好吧，接下來我該怎麼辦？

427
00:17:39,774 --> 00:17:40,570
>> 觀眾：排序的左半邊。

428
00:17:40,570 --> 00:17:42,780
>> 國寶馬蘭：所以現在我有排序
這些傢伙的左半邊。

429
00:17:42,780 --> 00:17:45,580
因為再次，假設自己的
的目標是要排序的左半邊。

430
00:17:45,580 --> 00:17:46,440
你怎麼做到這一點呢？

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

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

433
00:17:50,160 --> 00:17:52,030
現在，我這兩個傢伙排序。

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

435
00:17:53,563 --> 00:17:54,510
>> 觀眾：排序的左半邊。

436
00:17:54,510 --> 00:17:55,460
>> 國寶MALAN：排序的左半邊。

437
00:17:55,460 --> 00:18:00,680
所以，現在這些，這個座位在這裡，
是一個大小為1的列表。

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

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

440
00:18:02,390 --> 00:18:03,690
>> 國寶馬蘭：黛西公主就在這裡。

441
00:18:03,690 --> 00:18:07,470
於是她，因為已經排序
該列表是大小為1。

442
00:18:07,470 --> 00:18:09,490
接下來我該怎麼辦？

443
00:18:09,490 --> 00:18:13,680
OK，返回，因為該列表
大小為1，小於2。

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

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

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

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

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

449
00:18:20,220 --> 00:18:20,980
>> 國寶馬蘭：琳達。

450
00:18:20,980 --> 00:18:23,210
因此，我們應該做些什麼，現在
我們有一個列表的大小為1？

451
00:18:23,210 --> 00:18:24,440
>> 觀眾：返回。

452
00:18:24,440 --> 00:18:24,760
>> DAVID馬蘭：小心。

453
00:18:24,760 --> 00:18:29,540
我們先回來了，現在的第三
一步 - 如果我描繪

454
00:18:29,540 --> 00:18:33,490
現在擁抱的兩個席位，現在我
合併這兩個元素。

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

456
00:18:35,530 --> 00:18:39,920
但是，這就是合併過程
開始引人注目。

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

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

459
00:18:44,170 --> 00:18:46,480
並且如果琳達，因為圖2是
小於4，你為什麼不

460
00:18:46,480 --> 00:18:48,130
首先你來到我身邊嗎？

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

462
00:18:48,690 --> 00:18:50,520
所以，琳達，你過來先。

463
00:18:50,520 --> 00:18:53,820
>> 現在，在現實中，如果它只是一個數組
我們可能只是她的實時移動

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

465
00:18:55,360 --> 00:18:57,770
所以，想像一下，採取了一些常數
步驟1的數。

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

467
00:18:58,480 --> 00:19:01,490
但我們需要把你的
這裡的第一個位置。

468
00:19:01,490 --> 00:19:03,930
>> 而現在，如果你能來到我身邊，
好了，我們要去

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

470
00:19:06,300 --> 00:19:09,120
即使這感覺像
服用了一段時間，什麼是好的現在是

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

472
00:19:14,710 --> 00:19:18,010
是下一步驟中，如果我們現在
進一步倒轉的故事？

473
00:19:18,010 --> 00:19:18,980
>> 觀眾：右半邊。

474
00:19:18,980 --> 00:19:19,900
>> DAVID馬蘭：排序的右半​​邊。

475
00:19:19,900 --> 00:19:21,320
所以，你們必須這樣做，以及。

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

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

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

479
00:19:25,540 --> 00:19:25,870
>> 國寶馬蘭：傑西。

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

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

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

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

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

485
00:19:33,630 --> 00:19:35,340
>> 國寶馬蘭：米歇爾顯然是
大小為1的列表。

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

487
00:19:36,050 --> 00:19:38,690
所以現在發生的魔力，
合併過程。

488
00:19:38,690 --> 00:19:39,790
那麼，誰將會第一次來嗎？

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

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

491
00:19:43,280 --> 00:19:47,090
我們現在為她提供空間
後面這把椅子在這裡。

492
00:19:47,090 --> 00:19:51,580
而現在，如果你能回來，
我們現在有，是明確的，兩個

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

494
00:19:53,810 --> 00:19:57,090
剛剛描繪的緣故，如果你
可以使一點點的空間 - 

495
00:19:57,090 --> 00:19:59,780
一個左半在這裡，其中一個
右半這裡。

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

497
00:20:01,160 --> 00:20:02,270
什麼樣的步驟是下一個？

498
00:20:02,270 --> 00:20:03,030
>> 觀眾：合併。

499
00:20:03,030 --> 00:20:04,160
>> 國寶馬蘭：所以現在我們必須進行合併。

500
00:20:04,160 --> 00:20:07,490
這樣就OK了，所以現在，令人欣慰的是，我們
剛剛釋放了四把椅子。

501
00:20:07,490 --> 00:20:11,480
因此，我們已經兩次使用盡可能多的內存，但
我們可以給之間倒裝假摔

502
00:20:11,480 --> 00:20:12,330
兩個數組。

503
00:20:12,330 --> 00:20:14,190
因此，這數字是先來？

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

505
00:20:14,850 --> 00:20:16,680
所以來到我身邊，並採取
您的座位在這裡。

506
00:20:16,680 --> 00:20:19,120
然後數字2是明顯
接下來，你來這裡。

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

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

509
00:20:23,390 --> 00:20:26,010
說真的，這些可能發生的瞬間，
移動 - 

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

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

512
00:20:28,350 --> 00:20:29,680
>> 國寶馬蘭：現在我們
在相當良好。

513
00:20:29,680 --> 00:20:34,910
的左半部分的整個
輸入現在已經被排序。

514
00:20:34,910 --> 00:20:37,370
所有的權利，讓這些傢伙
我的優勢 - 

515
00:20:37,370 --> 00:20:40,340
它是怎麼結束了所有女孩子對
離開和所有的男孩在右邊？

516
00:20:40,340 --> 00:20:42,450
>> OK，這樣的傢伙現在輪到。

517
00:20:42,450 --> 00:20:44,680
所以，我不會走你通過
這些步驟。

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

519
00:20:46,550 --> 00:20:50,050
如果你想提前去站起來，
你們這些傢伙，讓我給你話筒。

520
00:20:50,050 --> 00:20:52,990
如果你不能複製什麼
我們在這裡只是做

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

522
00:20:53,880 --> 00:20:59,530
誰需要先發言，
基於該算法？

523
00:20:59,530 --> 00:21:03,210
因此，解釋你在做什麼之前，
你做任何腳的動作。

524
00:21:03,210 --> 00:21:05,930
>> 揚聲器1：好吧，這樣以來
我的左半部分

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

526
00:21:07,790 --> 00:21:08,730
對嗎？

527
00:21:08,730 --> 00:21:09,250
>> 國寶馬蘭：好。

528
00:21:09,250 --> 00:21:10,350
>> 揚聲器1：然後 - 

529
00:21:10,350 --> 00:21:11,800
>> 國寶馬蘭：誰做
麥克風去下一個？

530
00:21:11,800 --> 00:21:12,920
>> 揚聲器1：下一個號碼。

531
00:21:12,920 --> 00:21:14,720
>> 揚聲器2：所以我的右半邊
的左半部分

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

533
00:21:17,830 --> 00:21:18,050
>> 國寶馬蘭：好。

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

535
00:21:18,550 --> 00:21:21,855
所以，現在你們兩個什麼是下一個向上？

536
00:21:21,855 --> 00:21:23,740
>> 揚聲器2：我們希望看到誰較小。

537
00:21:23,740 --> 00:21:24,200
>> DAVID馬蘭：沒錯。

538
00:21:24,200 --> 00:21:24,940
我們要合併。

539
00:21:24,940 --> 00:21:27,590
我們要用來合併空間
你進入，即使它們

540
00:21:27,590 --> 00:21:30,250
顯然已經排序，我們將
遵循相同的算法。

541
00:21:30,250 --> 00:21:31,560
那麼，誰去先回來？

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

543
00:21:35,720 --> 00:21:38,570
現在的麥克風去
這些傢伙，好不好？

544
00:21:38,570 --> 00:21:43,590
>> 揚聲器3：所以我的右半邊
左半邊，我Ñ小於

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

546
00:21:45,048 --> 00:21:46,380
>> 國寶馬蘭：好。

547
00:21:46,380 --> 00:21:49,450
>> 揚聲器4：我的右半部分
右半邊的右半邊，而我

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

549
00:21:51,740 --> 00:21:52,990
所以，現在我們合併。

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

551
00:21:55,140 --> 00:21:56,150
>> 揚聲器3：所以，我們回去吧。

552
00:21:56,150 --> 00:21:57,160
>> DAVID馬蘭：所以，你到後面去。

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

554
00:21:59,200 --> 00:22:01,240
而現在的觀眾，這是
步驟我們現在倒帶

555
00:22:01,240 --> 00:22:02,200
備份在我們的腦海中？

556
00:22:02,200 --> 00:22:02,940
>> 觀眾：合併。

557
00:22:02,940 --> 00:22:07,270
>> 國寶馬蘭：合併左半邊和右
一半的原始左半。

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

559
00:22:08,840 --> 00:22:10,520
只是為了讓這一點，
一點點的空間

560
00:22:10,520 --> 00:22:11,690
你們之間的兩個傢伙。

561
00:22:11,690 --> 00:22:13,800
所以，現在的兩個列表，
左，右。

562
00:22:13,800 --> 00:22:18,320
那麼我們怎麼現在合併你們到
前排座椅嗎？

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

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

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

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

567
00:22:27,330 --> 00:22:28,710
OK，現在我們是誰？

568
00:22:28,710 --> 00:22:29,650
>> 觀眾：沒做過。

569
00:22:29,650 --> 00:22:32,440
>> 國寶馬蘭：沒做過，因為
顯然，有一個剩餘步驟。

570
00:22:32,440 --> 00:22:35,720
不過，我之所以要使用這
像“倒帶在你的心中，行話”

571
00:22:35,720 --> 00:22:37,160
這是因為這是真的
發生了什麼。

572
00:22:37,160 --> 00:22:39,610
我們將通過所有這些步驟，
但我們暫停一排序

573
00:22:39,610 --> 00:22:42,480
的時刻，潛水深入到
算法，停頓了一會兒，

574
00:22:42,480 --> 00:22:45,840
潛水深入算法，並
現在我們要排序退我們

575
00:22:45,840 --> 00:22:49,430
頭腦和撤消所有這些層
排序，我們已經暫時擱置。

576
00:22:49,430 --> 00:22:51,790
>> 所以現在我們有兩個列表大小為4。

577
00:22:51,790 --> 00:22:54,790
如果你們能站起來，最後一次
和這裡一點空間

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

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

580
00:22:58,620 --> 00:23:01,060
誰是第一個數字，我們
需要拉進後面？

581
00:23:01,060 --> 00:23:01,870
米歇爾，當然。

582
00:23:01,870 --> 00:23:03,230
>> 所以我們把這裡的米歇爾。

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

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

585
00:23:06,440 --> 00:23:07,800
編號3？

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

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

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

589
00:23:18,850 --> 00:23:22,390
但現在讓我們來看看，如果我們不能確認
那種直觀的，這

590
00:23:22,390 --> 00:23:26,190
算法從根本上，特別是作為
n變真的大，正如我們已經看到的

591
00:23:26,190 --> 00:23:29,170
與動畫，是
從根本上更快。

592
00:23:29,170 --> 00:23:33,400
因此，我要求這個算法，在最壞的
的情況下，即使在最好的情況下，

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

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

595
00:23:39,160 --> 00:23:43,110
還有另一個方面某處
該迭代循環，

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

597
00:23:44,410 --> 00:23:49,154
我們可以把我們的手指放在什麼那些
兩個數字是指什麼？

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

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

600
00:23:54,160 --> 00:23:58,660
>> 揚聲器1：將日誌n是
我們一分為二 - 

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

602
00:23:59,630 --> 00:24:00,120
>> DAVID馬蘭：沒錯。

603
00:24:00,120 --> 00:24:03,000
我們看到在任何時候，任何算法，從而
目前為止，這種模式

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

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

606
00:24:05,700 --> 00:24:07,100
對數，底數2。

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

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

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

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

611
00:24:15,910 --> 00:24:18,760
哪裡到底從何而來？

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

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

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

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

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

617
00:24:28,820 --> 00:24:30,830
好了，你們做到了
相當直觀。

618
00:24:30,830 --> 00:24:34,140
>> 但是，如果我不是做這一點更
有條不紊，我可能已經指向

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

620
00:24:38,090 --> 00:24:42,080
用我的右手，有一半
只是後來走過

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

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

623
00:24:48,970 --> 00:24:51,890
但是，什麼是這個合併的關鍵
過程是我比較這些對

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

625
00:24:53,460 --> 00:24:57,270
從右側的一半，從左邊
半，我從來沒有一次回溯。

626
00:24:57,270 --> 00:25:00,570
>> 因此，合併本身正
不超過n個步驟。

627
00:25:00,570 --> 00:25:03,250
多少次我有
合併做到這一點呢？

628
00:25:03,250 --> 00:25:07,150
嗯，不超過n，我們只是
看到最終的合併。

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

630
00:25:13,120 --> 00:25:15,210
這將會給我們日誌n n次。

631
00:25:15,210 --> 00:25:16,310
>> 這是為什麼更好？

632
00:25:16,310 --> 00:25:19,600
那麼，如果我們已經知道該日誌
n是大於n  - 對嗎？

633
00:25:19,600 --> 00:25:22,590
我們看到在二進制搜索，電話簿
例如，日誌n為絕對

634
00:25:22,590 --> 00:25:23,760
優於線性。

635
00:25:23,760 --> 00:25:28,420
因此，這意味著Ñ次日誌n是
肯定比n倍另一個

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

637
00:25:30,390 --> 00:25:32,400
這就是我們最終的感覺。

638
00:25:32,400 --> 00:25:34,928
>> 這麼大的掌聲，如果
我們可以為這些傢伙。

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

640
00:25:38,920 --> 00:25:41,550
>> 國寶馬蘭：你的臨別禮物 - 
你可以保留的數字，

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

642
00:25:44,010 --> 00:25:45,620
和你的臨別禮物，像往常一樣。

643
00:25:45,620 --> 00:25:47,290
哦，我們會送你
的畫面，米歇爾。

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

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

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

647
00:25:50,400 --> 00:25:54,110
>> 讓我拉起來，在此期間，
我們的朋友羅布·鮑登提供

648
00:25:54,110 --> 00:25:59,520
有些不同的觀點，在此，
因為你可以想想這些

649
00:25:59,520 --> 00:26:01,280
步驟發生在一個有點
不同的方式。

650
00:26:01,280 --> 00:26:04,750
事實上，建立羅布的
向我們展示了，假設我們

651
00:26:04,750 --> 00:26:09,030
已經做了瓜分
大名單分為八個小名單，

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

653
00:26:10,570 --> 00:26:13,350
>> 所以，我們要改變一個偽代碼
點點得到的只是排序

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

655
00:26:15,320 --> 00:26:17,600
但運行時間是什麼
他做的仍然是

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

657
00:26:19,110 --> 00:26:23,540
再次，在這裡設置的是，他的
開始有八個列表的大小為1。

658
00:26:23,540 --> 00:26:27,730
所以你錯過了他的部分
實際上做日誌日誌N，N，日誌N

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

660
00:26:31,205 --> 00:26:32,120
>> [視頻回放]

661
00:26:32,120 --> 00:26:33,615
>> 這是它的第一個步驟。

662
00:26:33,615 --> 00:26:38,270
步驟二，反复
合併成對的名單。

663
00:26:38,270 --> 00:26:39,210
>> 國寶馬蘭：嗯。

664
00:26:39,210 --> 00:26:41,270
只有音頻
出我的電腦。

665
00:26:41,270 --> 00:26:42,520
讓我們試一次。

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

667
00:26:45,330 --> 00:26:48,310
>> 只是隨便挑 - 
現在，我們有四個名單。

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

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

670
00:26:52,120 --> 00:26:53,040
>> 國寶馬蘭：我們走吧。

671
00:26:53,040 --> 00:27:00,510
>> 合併108和15，我們最終
與列表15，108。

672
00:27:00,510 --> 00:27:07,170
合併50和圖4中，我們
結束與4，50。

673
00:27:07,170 --> 00:27:12,990
合併8和42，我們
結束與8位，42。

674
00:27:12,990 --> 00:27:19,970
和合併23日和16日，我們
結束與16​​，23。

675
00:27:19,970 --> 00:27:23,270
>> 現在我們的名單是大小為2。

676
00:27:23,270 --> 00:27:26,690
請注意，各
四個列表進行排序。

677
00:27:26,690 --> 00:27:29,450
因此，我們就可以開始合併
再次對列表。

678
00:27:29,450 --> 00:27:38,420
合併15和108和4和50，我們
先取4，然後15，然後

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

680
00:27:41,500 --> 00:27:50,610
合併8，42，16，23，我們先來
8，然後16，然後23個

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

682
00:27:52,700 --> 00:27:57,600
>> 所以，現在我們只有兩個列表大小
4，其中每一個進行排序。

683
00:27:57,600 --> 00:28:01,170
所以，現在我們合併這兩個列表。

684
00:28:01,170 --> 00:28:11,835
首先，我們4，然後我們把
8，然後我們採取了15，然後16，然後

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

686
00:28:19,456 --> 00:28:19,872
>> [END視頻播放]

687
00:28:19,872 --> 00:28:23,430
>> 國寶馬蘭：同樣，請注意，他從來沒有
觸動了杯一次以上

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

689
00:28:24,860 --> 00:28:26,200
所以他從來不重複。

690
00:28:26,200 --> 00:28:29,850
所以他總是移動到一邊，
這就是我們得到了我們的Ñ。

691
00:28:29,850 --> 00:28:33,290
>> 為什麼不讓我拉起一個動畫
我們前面看到的，但是這一次

692
00:28:33,290 --> 00:28:35,110
只專注於合併排序。

693
00:28:35,110 --> 00:28:38,030
讓我繼續前進，放大
在此。

694
00:28:38,030 --> 00:28:42,530
首先，讓我選擇一個隨機輸入，
放大這一點，你可以看到排序

695
00:28:42,530 --> 00:28:46,600
我們採取了什麼是理所當然的，早些時候，
合併排序，實際上做。

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

697
00:28:50,330 --> 00:28:53,140
問題一下子
開始採取良好的形狀。

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

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

700
00:28:58,860 --> 00:29:01,690
>> 所以這些都只是三種不同
採取同樣的想法。

701
00:29:01,690 --> 00:29:05,980
但關鍵的洞察力，就像鴻溝
和征服的第一類，

702
00:29:05,980 --> 00:29:10,640
是我們決定以某種方式劃分
問題變成大的東西，進入

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

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

705
00:29:15,660 --> 00:29:18,420
>> 現在，另一個有趣的方式來排序認為
這些，即使它不是

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

707
00:29:20,520 --> 00:29:21,640
下面的動畫。

708
00:29:21,640 --> 00:29:25,400
所以這是一個視頻的人放在一起
相關不同

709
00:29:25,400 --> 00:29:29,970
與各種不同的操作的聲音
插入排序，歸併排序，

710
00:29:29,970 --> 00:29:31,150
其他幾個。

711
00:29:31,150 --> 00:29:32,330
因此，在某一時刻，我會打遊戲。

712
00:29:32,330 --> 00:29:33,600
它是大約一分鐘長。

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

714
00:29:37,410 --> 00:29:41,420
也聽到這些算法如何
不同的執行與

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

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

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

718
00:29:50,400 --> 00:29:52,400
>> 國寶馬蘭：再次嘗試
每個元素插入

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

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

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

722
00:30:10,097 --> 00:30:13,630
>> 國寶馬蘭：您可以排序的感覺
如何相對較少的工作，它在做什麼

723
00:30:13,630 --> 00:30:15,834
對每一個步驟。

724
00:30:15,834 --> 00:30:20,470
這是沉悶聽起來像。

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

726
00:30:21,472 --> 00:30:25,222
>> 國寶馬蘭：這是選擇排序，
我們選擇我們想要的元素

727
00:30:25,222 --> 00:30:28,845
再次經歷一次又一次
並把它的開始。

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

729
00:30:37,674 --> 00:30:43,970
>> 國寶馬蘭：這是歸併排序，
你可以真正開始感覺。

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

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

732
00:30:54,770 --> 00:30:58,395
>> 國寶馬蘭：名為gnome的東西
排序，我們沒有看過。

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

734
00:31:13,630 --> 00:31:17,910
>> 國寶馬蘭：所以讓我看，現在，
你希望是由分心

735
00:31:17,910 --> 00:31:21,110
音樂，如果我能稍有閃失
數學位在這裡。

736
00:31:21,110 --> 00:31:24,850
因此，還有第四種辦法，我們可以
想想這意味著什麼

737
00:31:24,850 --> 00:31:29,210
功能比那些快
我們已經看到過。

738
00:31:29,210 --> 00:31:32,470
如果你未來在課程
數學的背景，你

739
00:31:32,470 --> 00:31:36,030
其實也許已經知道，你
這種技術可以一巴掌長期 - 

740
00:31:36,030 --> 00:31:40,400
即遞歸函數
以某種方式調用自身。

741
00:31:40,400 --> 00:31:44,780
>> 再次，記得歸併排序
在這個意義上的偽代碼是遞歸

742
00:31:44,780 --> 00:31:48,460
一個合併排序的步驟
是打電話排序 - 

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

744
00:31:49,740 --> 00:31:52,480
但令人欣慰的是，因為我們一直
呼叫排序，歸併排序，

745
00:31:52,480 --> 00:31:55,880
具體地，在一個較小的和更小的
和較小的名單，我們最終

746
00:31:55,880 --> 00:32:00,005
走出谷底，感謝我們就這麼叫
基地的情況下，硬編碼的情況下，

747
00:32:00,005 --> 00:32:04,270
說，如果列表很小，不到2
在這種情況下，就立即返回。

748
00:32:04,270 --> 00:32:07,550
如果我們沒有這種特殊情況，
算法絕不會走出低谷，

749
00:32:07,550 --> 00:32:11,010
事實上，你會進入一個
無限循環，真正的永遠。

750
00:32:11,010 --> 00:32:14,330
>> 但是假設我們希望現在就把
在此，再次一些數字，使用n

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

752
00:32:15,660 --> 00:32:18,680
我想問問你，有什麼
涉及的總時間

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

754
00:32:19,800 --> 00:32:22,960
或更普遍的，有什麼
它的成本的時間嗎？

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

756
00:32:24,730 --> 00:32:29,010
如果n是小於2時，所涉及的時間
在n個元素進行排序，

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

758
00:32:30,480 --> 00:32:31,410
因為我們剛剛返回。

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

760
00:32:32,510 --> 00:32:35,660
現在可以說，也許這是一個兩步
步驟弄清楚的金額

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

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

763
00:32:40,940 --> 00:32:42,580
>> 但有趣的是，這種情況下。

764
00:32:42,580 --> 00:32:47,320
遞歸分支
別人說的偽排序

765
00:32:47,320 --> 00:32:52,000
的左半邊，排序的權利
一半，合併的兩半。

766
00:32:52,000 --> 00:32:55,530
為什麼會發生這種表達
表示該費用？

767
00:32:55,530 --> 00:32:58,690
嗯，T為n的意思是，
時間排序​​n個元素。

768
00:32:58,690 --> 00:33:03,070
然後在右手側的
等號，劃分為n的T

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

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

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

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

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

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

775
00:33:15,420 --> 00:33:19,120
因為如果你有兩個列表，一個是
大小為n超過2和其他大小為n

776
00:33:19,120 --> 00:33:22,580
2，你必須基本上觸摸
這些元素，就像羅布

777
00:33:22,580 --> 00:33:24,990
感動每個杯子，只是
正如我們在每個

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

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

780
00:33:28,790 --> 00:33:31,780
>> 不幸的是，現在這個公式
本身也是遞歸的。

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

782
00:33:36,390 --> 00:33:40,670
在視頻或16杯，總共有多少個
步驟，它需要對它們進行排序

783
00:33:40,670 --> 00:33:41,550
歸併排序？

784
00:33:41,550 --> 00:33:45,790
它實際上不是一個明顯的答案，
因為現在你有排序

785
00:33:45,790 --> 00:33:48,500
遞歸地回答這個公式。

786
00:33:48,500 --> 00:33:51,190
>> 不過沒關係，因為讓我提出
我們做到以下幾點。

787
00:33:51,190 --> 00:33:56,670
所涉及的時間，16人進行排序或
16杯將要被表示的

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

789
00:33:58,020 --> 00:34:01,400
但是，這等於，根據我們的
前面的公式，2倍量

790
00:34:01,400 --> 00:34:04,780
所花費的時間進行排序
8杯加16。

791
00:34:04,780 --> 00:34:08,590
再次，加16是合併的時候，
兩個時間T 8是

792
00:34:08,590 --> 00:34:10,790
左半邊和右半邊的時間進行排序。

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

794
00:34:11,989 --> 00:34:13,210
我們必須在更深的潛水。

795
00:34:13,210 --> 00:34:16,409
這意味著我們必須回答
問題，什麼是T的8？

796
00:34:16,409 --> 00:34:19,610
T的8井僅2
4加8的時間T。

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

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

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

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

801
00:34:29,030 --> 00:34:31,940
>> 再次，我們是一種越來越
在這個循環中卡住。

802
00:34:31,940 --> 00:34:34,790
但它即將襲來
所謂的基本情況。

803
00:34:34,790 --> 00:34:37,310
因為什麼是T的1，我們要求？

804
00:34:37,310 --> 00:34:37,810
0。

805
00:34:37,810 --> 00:34:39,730
所以，現在我們終於可以倒退。

806
00:34:39,730 --> 00:34:44,290
>> 如果T 1是0，我現在可以回去最多一個
這個傢伙在這裡排隊，我可以

807
00:34:44,290 --> 00:34:46,330
插頭為T 0 1。

808
00:34:46,330 --> 00:34:51,770
因此，這意味著它等於2倍零，
否則被稱為0，加2。

809
00:34:51,770 --> 00:34:53,739
使整個表達式為2。

810
00:34:53,739 --> 00:34:58,740
>> 現在，如果我走T 2，其答案
2，將其插入中間線，T

811
00:34:58,740 --> 00:35:02,740
4，給我的2倍
2加4，所以8。

812
00:35:02,740 --> 00:35:07,080
如果我再插在8到前
行，這給了我2次，8，16。

813
00:35:07,080 --> 00:35:12,470
而如果我們再繼續，隨著
24，增加16，我們終於得到一個

814
00:35:12,470 --> 00:35:13,820
值64。

815
00:35:13,820 --> 00:35:18,480
>> 現在，本身並排序講
無關的符號n，

816
00:35:18,480 --> 00:35:20,700
大O，歐米茄，我們已經看到
一直在談論。

817
00:35:20,700 --> 00:35:24,890
但事實證明，64確實是
如圖16所示，輸入大小，

818
00:35:24,890 --> 00:35:27,110
登錄基地2 16。

819
00:35:27,110 --> 00:35:30,200
如果這是一個有點陌生，只是
回頭想想，它會回來

820
00:35:30,200 --> 00:35:30,700
你最終。

821
00:35:30,700 --> 00:35:33,775
如果這是2為底，它就像2
提出了什麼給你16？

822
00:35:33,775 --> 00:35:36,380
哦，那是4，所以它的16倍4。

823
00:35:36,380 --> 00:35:39,380
>> 再次，它不是一個大不了的，如果這
現在是那種朦朧的記憶。

824
00:35:39,380 --> 00:35:43,720
但現在，信仰
16日誌16是64。

825
00:35:43,720 --> 00:35:46,590
因此，事實上，這個簡單的理智
檢查，我們確認 - 

826
00:35:46,590 --> 00:35:48,250
但沒有正式證實 - 

827
00:35:48,250 --> 00:35:52,800
運行時間合併
排序的確是N個記錄Ñ。

828
00:35:52,800 --> 00:35:53,790
>> 所以不壞。

829
00:35:53,790 --> 00:35:57,260
這絕對是優於
到目前為止，我們已經看到，算法

830
00:35:57,260 --> 00:36:00,710
這是因為我們已經利用，一，
一種技術，稱為遞歸。

831
00:36:00,710 --> 00:36:03,880
但比這更有趣，
概念的分裂和征服。

832
00:36:03,880 --> 00:36:07,460
再次，真正實現0週的東西，
即使現在是反复出現在

833
00:36:07,460 --> 00:36:08,740
更引人注目的方式。

834
00:36:08,740 --> 00:36:11,750
>> 現在一個有趣的小運動，如果你
從來沒有做過這樣的 - 你可能

835
00:36:11,750 --> 00:36:14,660
不會有，因為正常排序
人們不認為做到這一點。

836
00:36:14,660 --> 00:36:20,650
但是，如果我去google.com和
我想了解一些有關

837
00:36:20,650 --> 00:36:22,356
遞歸，回車。

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [笑]

840
00:36:29,058 --> 00:36:32,030
[笑聲]

841
00:36:32,030 --> 00:36:33,385
國寶馬蘭：糟糕的玩笑慢慢蔓延。

842
00:36:33,385 --> 00:36:34,450
[笑]

843
00:36:34,450 --> 00:36:36,970
國寶MALAN：以防萬一，它的存在。

844
00:36:36,970 --> 00:36:38,710
我沒有拼寫錯了，
的笑話。

845
00:36:38,710 --> 00:36:40,810
好的。

846
00:36:40,810 --> 00:36:42,950
解釋一下你旁邊的人，如果
但相當點擊只是還沒有。

847
00:36:42,950 --> 00:36:47,650
但是，遞歸，更一般地，是指
的過程中的函數調用

848
00:36:47,650 --> 00:36:51,430
本身，或者更一般地，將一個
到東西，可以是問題

849
00:36:51,430 --> 00:36:56,220
頭痛醫頭，腳痛醫腳的解決解決相同
代表性的問題。

850
00:36:56,220 --> 00:36:58,400
>> 好吧，讓我們改變齒輪
只是一瞬間。

851
00:36:58,400 --> 00:37:00,840
我們喜歡在某些懸念結束，
讓我們開始設置

852
00:37:00,840 --> 00:37:05,870
在舞台上，幾分鐘，
一個非常簡單的想法 - 

853
00:37:05,870 --> 00:37:07,620
交換兩個元素，對不對？

854
00:37:07,620 --> 00:37:10,040
所有這些算法，我們已經
談論過去幾

855
00:37:10,040 --> 00:37:12,420
講座涉及到一些
交換排序。

856
00:37:12,420 --> 00:37:14,630
今天，它是用他們得到
出自己的椅子，

857
00:37:14,630 --> 00:37:18,570
走動，但在代碼中，我們將
只是從一個數組元素

858
00:37:18,570 --> 00:37:20,370
撲通到另一個。

859
00:37:20,370 --> 00:37:21,880
>> 那麼，我們如何去這樣做呢？

860
00:37:21,880 --> 00:37:24,850
好吧，讓我繼續寫
這裡的快速程序。

861
00:37:24,850 --> 00:37:31,600
我要繼續做
這是以下。

862
00:37:31,600 --> 00:37:33,910
讓我們把這個 - 

863
00:37:33,910 --> 00:37:38,070
我們要調用這個什麼？

864
00:37:38,070 --> 00:37:38,650
>> 事實上，沒有。

865
00:37:38,650 --> 00:37:39,420
讓我快退。

866
00:37:39,420 --> 00:37:41,220
我不想這樣做
吊人胃口。

867
00:37:41,220 --> 00:37:42,270
它會破壞其中的樂趣。

868
00:37:42,270 --> 00:37:43,600
讓我們做到這一點，而不是。

869
00:37:43,600 --> 00:37:47,430
>> 假設我想寫一點
現在方案，並擁抱

870
00:37:47,430 --> 00:37:48,700
遞歸的想法。

871
00:37:48,700 --> 00:37:50,370
我種了自己。

872
00:37:50,370 --> 00:37:51,420
我要做到以下幾點。

873
00:37:51,420 --> 00:38:00,220
>> 首先，快速包括標準io.h
以及包括cs50.h.

874
00:38:00,220 --> 00:38:03,200
然後我要繼續前進
並宣布INT主要無效

875
00:38:03,200 --> 00:38:04,360
在通常的方式。

876
00:38:04,360 --> 00:38:07,920
我意識到我已經名不副實的文件，所以
我想補充的擴展名，在這裡，所以

877
00:38:07,920 --> 00:38:09,510
我們可以正確編譯。

878
00:38:09,510 --> 00:38:10,970
啟動此功能。

879
00:38:10,970 --> 00:38:13,290
>> 的功能，我想寫點什麼，相當
簡單地說，就是要求

880
00:38:13,290 --> 00:38:16,210
用戶輸入一個數字，然後添加
之間的數字

881
00:38:16,210 --> 00:38:19,920
數，並說，0。

882
00:38:19,920 --> 00:38:22,510
所以，首先我要繼續前進
並宣布INT N。

883
00:38:22,510 --> 00:38:24,760
然後我複製一些代碼，
我們已經使用了一段時間。

884
00:38:24,760 --> 00:38:26,660
雖然東西是真實的。

885
00:38:26,660 --> 00:38:28,000
我會回來在某一時刻。

886
00:38:28,000 --> 00:38:29,010
>> 我想要做的是什麼呢？

887
00:38:29,010 --> 00:38:33,460
我想說的printf積極
請整數。

888
00:38:33,460 --> 00:38:36,130
然後我要去
說N變得到詮釋。

889
00:38:36,130 --> 00:38:38,800
如此反复，一些樣板代碼
我們以前用過的。

890
00:38:38,800 --> 00:38:40,810
我要做到這一點
而n是小於1。

891
00:38:40,810 --> 00:38:44,120
因此，這將確保用戶
給我一個正整數。

892
00:38:44,120 --> 00:38:45,490
>> 現在我要做到以下幾點。

893
00:38:45,490 --> 00:38:51,020
我想補充的所有號碼
介於1和n或0且n

894
00:38:51,020 --> 00:38:52,570
等價地，得到的總和。

895
00:38:52,570 --> 00:38:55,100
所以大的sigma符號
您可能還記得。

896
00:38:55,100 --> 00:38:59,050
所以我要做到這一點首先調用
一個函數調用西格瑪，

897
00:38:59,050 --> 00:39:06,030
在n傳遞給它，然後我要去
printf的說，答案是正確的。

898
00:39:06,030 --> 00:39:08,180
>> 因此，在短期，我得到
int的來自用戶的。

899
00:39:08,180 --> 00:39:09,280
我保證它的正面。

900
00:39:09,280 --> 00:39:12,700
我聲明了一個變量叫做答案
int類型，存儲在它的回報

901
00:39:12,700 --> 00:39:15,610
西格瑪值作為輸入，通過在n。

902
00:39:15,610 --> 00:39:17,060
然後，我打印出這個問題的答案。

903
00:39:17,060 --> 00:39:19,550
>> 不幸的是，即使西格瑪的聲音
喜歡的東西，可能是在

904
00:39:19,550 --> 00:39:24,040
math.h的文件，它的聲明，
它實際上不是。

905
00:39:24,040 --> 00:39:24,690
所以，這是確定的。

906
00:39:24,690 --> 00:39:26,170
我可以實現自己。

907
00:39:26,170 --> 00:39:29,160
我要去執行一個函數調用
標準差，它會採取

908
00:39:29,160 --> 00:39:29,900
參數 - 

909
00:39:29,900 --> 00:39:32,100
讓我們只是把它M，只是
所以它是不同的。

910
00:39:32,100 --> 00:39:35,910
然後在這裡，我要說的話，
以及，如果m是小於1  - 這是一個

911
00:39:35,910 --> 00:39:38,180
很無趣程序。

912
00:39:38,180 --> 00:39:41,700
所以，我要繼續前進，
立即返回0。

913
00:39:41,700 --> 00:39:45,920
它只是無厘頭加起來
如果m 1和m之間的數

914
00:39:45,920 --> 00:39:48,470
本身是0或負數。

915
00:39:48,470 --> 00:39:50,900
>> 然後我要繼續前進
做到這一點非常迭代。

916
00:39:50,900 --> 00:39:53,090
我會做這樣的老派，
我要繼續前進

917
00:39:53,090 --> 00:39:57,150
並說，我要去
聲明總和為0。

918
00:39:57,150 --> 00:39:59,630
然後，我將不得不
一個循環的int  - 

919
00:39:59,630 --> 00:40:02,820
並讓我這樣做符合我們的
分銷代碼，讓您擁有一個副本

920
00:40:02,820 --> 00:40:07,500
在家裡。 INT I上得到1
i是小於或等於m。

921
00:40:07,500 --> 00:40:09,430
我+ +。

922
00:40:09,430 --> 00:40:11,430
然後將裡面的for循環 - 

923
00:40:11,430 --> 00:40:12,440
我們幾乎沒有 - 

924
00:40:12,440 --> 00:40:15,810
總和得到的總和加上1。

925
00:40:15,810 --> 00:40:17,670
然後我要返回的總和。

926
00:40:17,670 --> 00:40:19,420
>> 所以我這樣做很快，
誠然相當。

927
00:40:19,420 --> 00:40:22,775
但同樣，主要功能是相當
簡單的，基於代碼我們已經

928
00:40:22,775 --> 00:40:23,190
書面迄今。

929
00:40:23,190 --> 00:40:25,610
採用雙循環，得到了肯定
int的來自用戶的。

930
00:40:25,610 --> 00:40:29,870
然後，我通過這個int到一個新的功能
叫西格瑪，調用它，再次，正。

931
00:40:29,870 --> 00:40:33,100
我存儲的返回值，得到的答案
從目前黑盒子

932
00:40:33,100 --> 00:40:35,460
已知作為σ，在一個變量中
叫的答案。

933
00:40:35,460 --> 00:40:36,580
然後，我打印出來。

934
00:40:36,580 --> 00:40:39,090
>> 如果我們現在繼續的故事，
西格瑪是如何實施？

935
00:40:39,090 --> 00:40:40,840
我建議如下推行。

936
00:40:40,840 --> 00:40:43,560
首先，一點點的錯誤檢查
以確保該用戶的不

937
00:40:43,560 --> 00:40:46,480
梅辛與我並傳入
一些負面或0值。

938
00:40:46,480 --> 00:40:49,710
然後我聲明了一個變量
綜上所述，將它設置為0。

939
00:40:49,710 --> 00:40:55,910
>> 現在，我開始從i等於
1所有的方式，包括米，

940
00:40:55,910 --> 00:41:00,130
因為我想包括所有
數字從1到m，首尾。

941
00:41:00,130 --> 00:41:04,350
這裡面的for循環，我只是做
總和得到現在不管它是什麼，再加上

942
00:41:04,350 --> 00:41:08,900
i的值。

943
00:41:08,900 --> 00:41:10,370
加上i的值。

944
00:41:10,370 --> 00:41:14,090
>> 順便說一句，如果你沒有看到這
之前，有一些語法糖

945
00:41:14,090 --> 00:41:14,870
此行。

946
00:41:14,870 --> 00:41:21,120
我可以改寫為加等於I，
只是為了保存自己敲幾下鍵盤

947
00:41:21,120 --> 00:41:22,570
看起來有點涼。

948
00:41:22,570 --> 00:41:23,140
但是這一切。

949
00:41:23,140 --> 00:41:24,660
它的功能同樣的事情。

950
00:41:24,660 --> 00:41:26,710
>> 不幸的是，這種代碼的
不會還編譯。

951
00:41:26,710 --> 00:41:31,600
如果我運行make的西格瑪0，怎麼我
我大叫？

952
00:41:31,600 --> 00:41:33,473
什麼是它不喜歡呢？

953
00:41:33,473 --> 00:41:35,740
>> 觀眾：[聽不清]。

954
00:41:35,740 --> 00:41:37,800
>> 國寶馬蘭：是啊，我沒有申報
向上頂，右邊的功能？

955
00:41:37,800 --> 00:41:40,590
C是一種愚蠢的，它僅
做什麼你告訴它的事情，而你

956
00:41:40,590 --> 00:41:41,880
必須這樣做的順序。

957
00:41:41,880 --> 00:41:45,910
所以如果我打在這裡輸入，我要
關於Sigma隱警告

958
00:41:45,910 --> 00:41:46,860
聲明。

959
00:41:46,860 --> 00:41:48,120
>> 哦，不是一個問題。

960
00:41:48,120 --> 00:41:50,370
我可以去到頂部，我可以
說，沒事的，請等待一分鐘。

961
00:41:50,370 --> 00:41:54,240
六西格瑪是一個函數，返回
一個int，並預期

962
00:41:54,240 --> 00:41:56,620
int作為輸入，分號。

963
00:41:56,620 --> 00:41:59,550
或者，我可以把整個功能
上述主要的，但在一般情況下，最好

964
00:41:59,550 --> 00:42:02,260
針對該建議，因為它是
很高興上面的頂部，所以總是有主

965
00:42:02,260 --> 00:42:06,310
可以潛水的權利，並知道什麼是
程序首先通過閱讀主要做。

966
00:42:06,310 --> 00:42:07,930
>> 所以，現在讓我清楚的畫面。

967
00:42:07,930 --> 00:42:09,330
重拍0西格瑪。

968
00:42:09,330 --> 00:42:10,340
所有似乎退房。

969
00:42:10,340 --> 00:42:11,970
讓我跑SIGMA 0。

970
00:42:11,970 --> 00:42:12,770
正間。

971
00:42:12,770 --> 00:42:15,580
我給它的數量
3，以保持它的簡單。

972
00:42:15,580 --> 00:42:18,710
所以，應該給我3
加2加1，所以6。

973
00:42:18,710 --> 00:42:20,750
回車，我確實得到6。

974
00:42:20,750 --> 00:42:21,820
>> 我可以做更大的東西 - 

975
00:42:21,820 --> 00:42:24,080
50，12，75。

976
00:42:24,080 --> 00:42:27,690
正如切線，我要做的
可笑的東西像一個真正的大

977
00:42:27,690 --> 00:42:30,375
號，呵呵，那實際工作 - 

978
00:42:30,375 --> 00:42:31,600
誒，我不認為這是正確的。

979
00:42:31,600 --> 00:42:32,810
讓我們來看看。

980
00:42:32,810 --> 00:42:34,060
讓我們真的惹它。

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> 這是一個問題。

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
這是怎麼回事呢？

985
00:42:44,970 --> 00:42:46,050
該代碼是沒有那麼糟糕。

986
00:42:46,050 --> 00:42:48,470
它仍然是線性的。

987
00:42:48,470 --> 00:42:50,810
吹口哨是一個很好的效果，雖然。

988
00:42:50,810 --> 00:42:52,060
這是怎麼回事呢？

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> 不知道如果我聽到它。

991
00:42:55,620 --> 00:42:57,620
因此，原來 - 
這是作為一個旁白。

992
00:42:57,620 --> 00:42:59,400
這不是核心到
遞歸的想法。

993
00:42:59,400 --> 00:43:02,480
事實證明，是因為我試圖
代表這樣一個大的數字，最

994
00:43:02,480 --> 00:43:06,980
它可能被誤解
C作為一個並不樂觀的數字，

995
00:43:06,980 --> 00:43:09,980
但負數。

996
00:43:09,980 --> 00:43:12,690
>> 我們還沒有談到這一點，但它
原來有負數

997
00:43:12,690 --> 00:43:14,210
在世界上除了
正數。

998
00:43:14,210 --> 00:43:16,290
和手段，通過它可以
表示負數

999
00:43:16,290 --> 00:43:19,530
基本上是，你使用一個
特殊的位來指示

1000
00:43:19,530 --> 00:43:20,400
正面負面以上。

1001
00:43:20,400 --> 00:43:22,950
這是一個有點比這更複雜，
但是這是最基本的想法。

1002
00:43:22,950 --> 00:43:26,740
>> 不幸的是，如果C是混亂的一個
那些位作為實際意義，

1003
00:43:26,740 --> 00:43:30,790
哦，這是一個負號，我的循環
在這裡，例如，實際上是從來沒有

1004
00:43:30,790 --> 00:43:31,740
要終止。

1005
00:43:31,740 --> 00:43:33,850
所以，如果我實際打印的東西
一遍又一遍，我們會

1006
00:43:33,850 --> 00:43:34,650
看到一大堆。

1007
00:43:34,650 --> 00:43:36,220
但是，這是除了點。

1008
00:43:36,220 --> 00:43:38,590
這是真的只是一種
對知識的好奇心，我們還會回來

1009
00:43:38,590 --> 00:43:39,550
最終備份。

1010
00:43:39,550 --> 00:43:43,400
但現在，這是一個正確的
如果我們假設執行

1011
00:43:43,400 --> 00:43:45,970
用戶將提供整數
適合內整數。

1012
00:43:45,970 --> 00:43:49,370
>> 但我要求這個代碼，坦率地說，
可以做簡單得多。

1013
00:43:49,370 --> 00:43:54,060
如果在手的目標是採取多項
像米，加起來所有的

1014
00:43:54,060 --> 00:43:59,510
之間的數字，並且1，或反過來
介於1和它，我要求

1015
00:43:59,510 --> 00:44:03,380
我可以借用這種想法，合併
排序了，這是一個問題

1016
00:44:03,380 --> 00:44:05,660
這種規模和分割
成更小的東西。

1017
00:44:05,660 --> 00:44:09,875
也許不是一半，但規模較小，但
代表性地是相同的。

1018
00:44:09,875 --> 00:44:12,130
同樣的想法，但一個較小的問題。

1019
00:44:12,130 --> 00:44:15,470
>> 因此，實際上，我 - 讓我好好保存這個文件
不同的版本號。

1020
00:44:15,470 --> 00:44:17,670
我們稱這個版本
1而不是0。

1021
00:44:17,670 --> 00:44:20,790
我要求其實我可以
這種重新實現此

1022
00:44:20,790 --> 00:44:22,160
心態彎曲方式。

1023
00:44:22,160 --> 00:44:23,710
>> 我要獨自離開它的一部分。

1024
00:44:23,710 --> 00:44:27,710
我會說，如果m是
或者甚至等於0  - 

1025
00:44:27,710 --> 00:44:29,280
我只是要一點點
肛門

1026
00:44:29,280 --> 00:44:30,520
我的錯誤檢查 - 

1027
00:44:30,520 --> 00:44:33,190
我要繼續前進，返回0。

1028
00:44:33,190 --> 00:44:34,490
這是任意的。

1029
00:44:34,490 --> 00:44:37,500
我只是簡單地決定，如果用戶
我給了我一個負數，

1030
00:44:37,500 --> 00:44:41,490
返回0，他們應該已經讀過
的文檔更加緊密。

1031
00:44:41,490 --> 00:44:42,170
>> 其他 - 

1032
00:44:42,170 --> 00:44:44,070
注意什麼，我要做的事情。

1033
00:44:44,070 --> 00:44:49,260
否則，我要返回米加 - 

1034
00:44:49,260 --> 00:44:51,010
什麼是西格瑪米？

1035
00:44:51,010 --> 00:44:56,710
那麼，Σ的m加m減1，
加m的負2，加m零下3。

1036
00:44:56,710 --> 00:44:58,030
我不想寫出來。

1037
00:44:58,030 --> 00:44:59,120
我為什麼不只是撐船？

1038
00:44:59,120 --> 00:45:05,080
遞歸調用自己稍微
規模較小的問題，分號，

1039
00:45:05,080 --> 00:45:06,840
收工？

1040
00:45:06,840 --> 00:45:07,040
>> 對嗎？

1041
00:45:07,040 --> 00:45:10,980
現在在這裡，太，你可能會感到或擔心
這是一個無限循環，我

1042
00:45:10,980 --> 00:45:15,450
誘導，由此我實現
西格瑪致電西格瑪。

1043
00:45:15,450 --> 00:45:20,342
但是，這是完全確定的，因為我
想提前增加了哪條線路？

1044
00:45:20,342 --> 00:45:22,600
>> 觀眾：[聽不清]。

1045
00:45:22,600 --> 00:45:25,430
>> 國寶馬蘭：23日至26日，
是我的，如果條件。

1046
00:45:25,430 --> 00:45:28,390
因為關於什麼是好的
減法這裡，因為我保持

1047
00:45:28,390 --> 00:45:31,180
交給西格瑪小問題，小
的問題，更小的 - 它不是

1048
00:45:31,180 --> 00:45:31,870
的一半大小。

1049
00:45:31,870 --> 00:45:34,380
這只是一小步，
不過沒關係。

1050
00:45:34,380 --> 00:45:38,050
因為最終，我們將繼續努力
我們一路下跌為1或0。

1051
00:45:38,050 --> 00:45:41,630
一旦我們打0，Sigma的不
會調用本身了。

1052
00:45:41,630 --> 00:45:43,590
這將立即返回0。

1053
00:45:43,590 --> 00:45:47,960
>> 所以效果，如果你樣的風
在你的心中，是增加M PLUS

1054
00:45:47,960 --> 00:45:52,740
M減1，加m減2，加m減
3，加點，點，點，M減

1055
00:45:52,740 --> 00:45:57,820
米，最終給你0，
最終效果添加的所有

1056
00:45:57,820 --> 00:45:59,070
這些東西放在一起。

1057
00:45:59,070 --> 00:46:02,380
所以，我們還沒有，用遞歸
解決了這個問題，我們

1058
00:46:02,380 --> 00:46:03,470
之前沒能解決。

1059
00:46:03,470 --> 00:46:06,840
事實上，版本0，每
問題到今天為止，已經解

1060
00:46:06,840 --> 00:46:09,980
只需使用循環或在
循環或類似的結構。

1061
00:46:09,980 --> 00:46:13,150
>> 但是，遞歸，我敢說，給我們
以不同的方式思考

1062
00:46:13,150 --> 00:46:17,010
問題，因此如果我們可以採取一個
問題，除從東西

1063
00:46:17,010 --> 00:46:22,340
到有些東西有點大
較小的，我要求，我們可以解決這個問題

1064
00:46:22,340 --> 00:46:26,040
也許是多了幾分優雅條款
設計，用更少的代碼，

1065
00:46:26,040 --> 00:46:30,980
甚至解決的問題，會
更難，因為我們最終會

1066
00:46:30,980 --> 00:46:33,280
看到，解決純屬迭代。

1067
00:46:33,280 --> 00:46:35,980
>> 但扣人心弦的，我沒有
要離開我們是這樣的。

1068
00:46:35,980 --> 00:46:40,720
讓我繼續前進，打開
一個文件 - 

1069
00:46:40,720 --> 00:46:44,300
其實，讓我去
這樣做真正的快。

1070
00:46:44,300 --> 00:46:46,875
讓我繼續前進，並提出
以下。

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
其中今天的代碼是這樣的文件在這裡。

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
在這裡，這一個noswap。

1075
00:47:03,050 --> 00:47:06,260
>> 所以這是一個愚蠢的小程序，
我掀起了要求做

1076
00:47:06,260 --> 00:47:06,940
以下。

1077
00:47:06,940 --> 00:47:10,140
在main中，它首先聲明
為int，名為x和分配

1078
00:47:10,140 --> 00:47:11,100
為1的值。

1079
00:47:11,100 --> 00:47:13,520
然後，它聲明int y和
分配值2。

1080
00:47:13,520 --> 00:47:15,310
然後打印出x和y是什麼。

1081
00:47:15,310 --> 00:47:17,781
然後，它說，交換，點點點。

1082
00:47:17,781 --> 00:47:21,670
>> 然後，它聲稱要調用一個函數
稱為交換，傳遞x和

1083
00:47:21,670 --> 00:47:24,290
Y，其中的想法是，希望
x和y會回來

1084
00:47:24,290 --> 00:47:25,620
不同的，相反的。

1085
00:47:25,620 --> 00:47:27,110
然後，它聲稱交換！

1086
00:47:27,110 --> 00:47:28,420
一個驚嘆號。

1087
00:47:28,420 --> 00:47:30,190
然後打印出x和y。

1088
00:47:30,190 --> 00:47:33,480
>> 但事實證明，這很
簡單的演示下來

1089
00:47:33,480 --> 00:47:35,570
這裡是實際馬車。

1090
00:47:35,570 --> 00:47:38,870
即使我宣布一個臨時的
變量和暫時把

1091
00:47:38,870 --> 00:47:42,010
它，然後我重新分配
一個b的值 - 

1092
00:47:42,010 --> 00:47:45,080
覺得合理，因為我
保存副本的溫度。

1093
00:47:45,080 --> 00:47:48,410
然後我更新b等於
無論是在溫度。

1094
00:47:48,410 --> 00:47:51,610
這類殼移動遊戲
到b和b成通過使用該

1095
00:47:51,610 --> 00:47:54,360
中間人名為temp的感覺
完全合理的。

1096
00:47:54,360 --> 00:47:57,270
>> 但我要求當我運行這個
代碼，我現在要做的 - 

1097
00:47:57,270 --> 00:47:59,490
讓我繼續前進，將其粘貼在這裡。

1098
00:47:59,490 --> 00:48:01,995
我會打電話給這個noswap.c。

1099
00:48:01,995 --> 00:48:05,630
顧名思義，這是不
將是一個正確的程序。

1100
00:48:05,630 --> 00:48:09,460
讓noswap /無掉。

1101
00:48:09,460 --> 00:48:12,110
x是1，y是2，交換，交換。

1102
00:48:12,110 --> 00:48:14,220
x為1時，y是2。

1103
00:48:14,220 --> 00:48:16,920
這是從根本上是錯誤的，甚至
雖然這似乎是完美的

1104
00:48:16,920 --> 00:48:17,730
合理的，我。

1105
00:48:17,730 --> 00:48:21,330
還有一個原因，但我們不
要揭示的原因，只是還沒有。

1106
00:48:21,330 --> 00:48:24,610
>> 現在我想的第二個扣人心弦的
離開你，

1107
00:48:24,610 --> 00:48:27,120
公佈各種優惠券代碼。

1108
00:48:27,120 --> 00:48:31,590
今年我們的創新與已故天
激起了不平凡的數字

1109
00:48:31,590 --> 00:48:33,830
的問題，這是
不是我們的本意。

1110
00:48:33,830 --> 00:48:36,590
這些優惠券代碼的意圖，
據此，如果你這樣做是問題的一部分

1111
00:48:36,590 --> 00:48:39,850
提前設置，從而獲得一個額外的一天，
真的幫助你們有所幫助

1112
00:48:39,850 --> 00:48:42,420
自己年初開始，排序
激勵你。

1113
00:48:42,420 --> 00:48:44,880
有助於我們之間分配負載
辦公時間更好地使

1114
00:48:44,880 --> 00:48:45,740
它的排序共贏。

1115
00:48:45,740 --> 00:48:48,860
>> 不幸的是，我覺得我的指示
沒有，到今天為止，已經很清楚，所以

1116
00:48:48,860 --> 00:48:52,230
我又回到這個週末更新
規格更大，更大膽的文字

1117
00:48:52,230 --> 00:48:53,600
解釋這些子彈。

1118
00:48:53,600 --> 00:48:56,900
只是說它更公開，
默認情況下，問題集將於週四

1119
00:48:56,900 --> 00:48:58,400
日中午，按照教學大綱。

1120
00:48:58,400 --> 00:49:02,030
如果你起步早，完成一部分
週三12:00設置問題

1121
00:49:02,030 --> 00:49:05,170
下午，部分，涉及到的優惠券
代碼，這個想法是，你可以擴展

1122
00:49:05,170 --> 00:49:07,710
您的截止日期為
P設定至週五。

1123
00:49:07,710 --> 00:49:10,890
也就是說，咬下一小部分的P
設置通常是相對

1124
00:49:10,890 --> 00:49:13,200
更大的問題，你買
自己一個額外的一天。

1125
00:49:13,200 --> 00:49:15,190
再次，它可以讓你思考
設置的問題，讓你去

1126
00:49:15,190 --> 00:49:16,380
辦公時間越快。

1127
00:49:16,380 --> 00:49:20,670
但優惠券代碼的問題仍是
必需的，即使你不提交。

1128
00:49:20,670 --> 00:49:23,340
>> 但更令人信服的是這樣的。

1129
00:49:23,340 --> 00:49:26,520
（舞台WHISPER），而那些人離開
早期是會後悔的。

1130
00:49:26,520 --> 00:49:28,620
鄉親在陽台上。

1131
00:49:28,620 --> 00:49:32,510
我提前給鄉親道歉
陽台上的原因，這將是

1132
00:49:32,510 --> 00:49:33,920
清除在短短的時刻。

1133
00:49:33,920 --> 00:49:37,050
>> 因此，我們很幸運，有一個
CS50的前任主管教學研究員

1134
00:49:37,050 --> 00:49:39,302
一家名為dropbox.com。

1135
00:49:39,302 --> 00:49:45,500
他們非常慷慨地捐出了
優惠券代碼，這裡這麼大的空間，

1136
00:49:45,500 --> 00:49:48,180
這是從
平時的2千兆字節。

1137
00:49:48,180 --> 00:49:51,740
所以我想我們會做這個
最後要注意的是做一點的贈品，

1138
00:49:51,740 --> 00:49:55,380
在短短的時刻，我們將揭示
贏家有優惠券

1139
00:49:55,380 --> 00:49:57,980
代碼，然後你可以去他們的
網站，鍵入它，瞧，得到了

1140
00:49:57,980 --> 00:50:01,370
一大堆更多的Dropbox空間為您的
家電和您的個人文件。

1141
00:50:01,370 --> 00:50:05,690
>> 第一，誰願意參加
在該圖中？

1142
00:50:05,690 --> 00:50:09,630
OK，現在這使得它更有趣。

1143
00:50:09,630 --> 00:50:14,010
人誰收到這25千兆字節
優惠券代碼 - 這是遠遠

1144
00:50:14,010 --> 00:50:16,150
更引人注目的莫過於後期
現在，也許是 - 

1145
00:50:16,150 --> 00:50:20,620
是一個誰是坐在最重要的一個
座墊下方有

1146
00:50:20,620 --> 00:50:21,620
該優惠券代碼。

1147
00:50:21,620 --> 00:50:23,480
現在，您可以看下面
您的坐墊。

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [視頻回放]

1150
00:50:29,680 --> 00:50:31,620
>> 一個，兩個，三個。

1151
00:50:31,620 --> 00:50:35,015
>> [尖叫]

1152
00:50:35,015 --> 00:50:35,985
>> 你得到一輛車！

1153
00:50:35,985 --> 00:50:36,670
你得到一輛車！

1154
00:50:36,670 --> 00:50:37,970
>> 國寶馬蘭：我們將看到
上週三。

1155
00:50:37,970 --> 00:50:38,904
>> 你得到一輛車！

1156
00:50:38,904 --> 00:50:39,371
你得到一輛車！

1157
00:50:39,371 --> 00:50:40,305
你得到一輛車！

1158
00:50:40,305 --> 00:50:41,706
你得到一輛車！

1159
00:50:41,706 --> 00:50:43,107
你得到一輛車！

1160
00:50:43,107 --> 00:50:45,530
>> 國寶馬蘭：陽台鄉親，來
這裡到前面，

1161
00:50:45,530 --> 00:50:46,866
在那裡我們有演員。

1162
00:50:46,866 --> 00:50:50,282
>>  - 每個人都得到一輛車！

1163
00:50:50,282 --> 00:50:52,234
人人都有車！

1164
00:50:52,234 --> 00:50:52,722
>> [END視頻播放]

1165
00:50:52,722 --> 00:50:54,590
>> 旁白：在未來CS50  - 

1166
00:50:54,590 --> 00:51:00,374
>> 揚聲器5：哦，我的天哪天哪天哪天哪
天哪天哪天哪天哪天哪天哪 - 

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE戲劇]