1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] 第3週，續]

2
00:00:02,280 --> 00:00:04,110
>> [戴維·J·馬蘭 - 哈佛大學]

3
00:00:04,110 --> 00:00:07,130
>> [這是CS50。 -  CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> 好的。歡迎回來。這是CS50，這是第3週的結束。

5
00:00:11,010 --> 00:00:14,680
>> 因此，對於那些不熟悉的，去年哈佛推出什麼所謂的創新實驗室，

6
00:00:14,680 --> 00:00:18,530
我的實驗室，這是一個美妙的河對岸的哈佛商學院的校園建設

7
00:00:18,530 --> 00:00:22,640
這是大學生，GSAS學生，學生來自全國各地的校園，

8
00:00:22,640 --> 00:00:27,000
包括教師，這是一個地方走到一起，工作創新的事情，

9
00:00:27,000 --> 00:00:29,180
尤其是創業的事情

10
00:00:29,180 --> 00:00:33,410
如果你和0個或更多的朋友所思所想，做一些創業

11
00:00:33,410 --> 00:00:37,080
無論是在這一類，這個類後，或超越。

12
00:00:37,080 --> 00:00:41,540
>> 所以，他們做了Ĵ長期的事情之一是這些行程，

13
00:00:41,540 --> 00:00:44,510
其中一個是紐約，其中之一是矽谷。

14
00:00:44,510 --> 00:00:47,530
空間是非常有限的，但它是一個擁有MBA學位的機會擦肩

15
00:00:47,530 --> 00:00:52,200
和研究生的學生在校園裡，實際上花時間在這些各自領域

16
00:00:52,200 --> 00:00:55,500
聊天的初創公司，聊天企業家等。

17
00:00:55,500 --> 00:00:57,870
因此，如果感興趣的話，看看這個網址。

18
00:00:57,870 --> 00:01:01,220
它也可以用網上的幻燈片。

19
00:01:01,220 --> 00:01:04,610
>> 我們可以淡化房子的音頻只是一點點嗎？

20
00:01:04,610 --> 00:01:08,640
如果你想和我們一起吃午飯，這個星期五​​，下午1:15在火與冰，頭上有。

21
00:01:08,640 --> 00:01:11,390
道歉，如果已經填寫的表格的時候，當你到達那裡的。

22
00:01:11,390 --> 00:01:13,750
但是，我們將繼續這一傳統開始。

23
00:01:13,750 --> 00:01:17,350
>> 今天，我們繼續，我們能夠解決的各種問題的高級別討論會，

24
00:01:17,350 --> 00:01:21,330
重點要少得多，至少今天，代碼和更多的想法。

25
00:01:21,330 --> 00:01:24,720
所以想回0週時，我們撕了電話簿中的一半，

26
00:01:24,720 --> 00:01:28,260
該計劃的目的是做什麼的，誠然，一點點戲劇性的

27
00:01:28,260 --> 00:01:32,360
但發送的點，搜索不必須是，必然，

28
00:01:32,360 --> 00:01:35,100
乍一看，你可能認為很明顯。

29
00:01:35,100 --> 00:01:40,200
一般的解決問題的可能不一定永遠是最好的 - 

30
00:01:40,200 --> 00:01:44,130
最明顯的解決方案不一定是最好的。

31
00:01:44,130 --> 00:01:47,300
因此，我們必須電話簿，坦率地說，我們所有的人在這個房間裡的本能，

32
00:01:47,300 --> 00:01:51,470
最有可能的是，開始時，尋找麥克·史密斯在中間，然後向左走還是向右

33
00:01:51,470 --> 00:01:54,280
根據我們發生任何字母結束。

34
00:01:54,280 --> 00:01:57,560
>> 但是，簡單的想法，我們人類已採取了這麼久授予

35
00:01:57,560 --> 00:02:00,670
真的應該開始你的頭腦來的最前沿

36
00:02:00,670 --> 00:02:03,900
因為所面臨的問題複雜得多比一本電話簿，

37
00:02:03,900 --> 00:02:07,420
那些同樣簡單，卓越的見解是什麼，讓我們

38
00:02:07,420 --> 00:02:10,259
解決更複雜，更有趣的問題，

39
00:02:10,259 --> 00:02:12,930
其中的一些事情，我們需要對已經授予這些天。

40
00:02:12,930 --> 00:02:15,720
數十億的網頁在那裡，但谷歌和Bing之類的

41
00:02:15,720 --> 00:02:17,660
能找到東西對於我們這樣的。

42
00:02:17,660 --> 00:02:22,300
這不會發生使用線性搜索，通過搜索所有可能的網頁。

43
00:02:22,300 --> 00:02:25,290
Facebook是能夠告訴你是誰，你所有的朋友或者朋友的朋友，

44
00:02:25,290 --> 00:02:28,250
而且也可以做似乎是在瞬間，這些天

45
00:02:28,250 --> 00:02:30,820
即使他們擁有數百萬用戶。

46
00:02:30,820 --> 00:02:34,250
>> 因此，我們實際上如何解決規模問題上，最終將減少

47
00:02:34,250 --> 00:02:37,830
我們的想法看著在0週，多一點。

48
00:02:37,830 --> 00:02:42,320
我們不會重新執行該算法，但記得，我們​​也做了這個練習在0週

49
00:02:42,320 --> 00:02:44,780
我們每個人都站起來，拿上1號，

50
00:02:44,780 --> 00:02:48,720
然後我們每個人都自我計數的配對過，一起加入你的號碼，

51
00:02:48,720 --> 00:02:51,930
然後上坐了下來，該團伙每次迭代的一半。

52
00:02:51,930 --> 00:02:56,750
因此，我們從500名學生，250至125，等等。

53
00:02:56,750 --> 00:03:00,080
但是，正如我們週一表示，有強大的思想

54
00:03:00,080 --> 00:03:02,460
是，如果我們對這個問題的規模增加一倍

55
00:03:02,460 --> 00:03:06,480
由律政司司長或EC 10和所有的孩子都回來進了房間，加入我們，

56
00:03:06,480 --> 00:03:09,510
好了，我們可以大概算，整個聚合組

57
00:03:09,510 --> 00:03:13,380
更多的大循環迭代，因為他們只可能會增加一倍的大小

58
00:03:13,380 --> 00:03:15,630
或在EC 10的情況下多一點的兩倍大小。

59
00:03:15,630 --> 00:03:18,440
因此，我們將不得不多花一點點的時間，

60
00:03:18,440 --> 00:03:22,000
但我們不會花400或700以上的步驟。

61
00:03:22,000 --> 00:03:26,550
>> 只是為了畫這幅畫，這是一個少一些抽象的方式，讓我們無法讓每個人都站起來。

62
00:03:26,550 --> 00:03:31,100
但是，如果你選擇了坐今天的樂隊不會介意站了起來，

63
00:03:31,100 --> 00:03:34,580
讓我們看看我們可以計算出在你們中間誰是最高的人是

64
00:03:34,580 --> 00:03:36,730
做同類型的比較算法。

65
00:03:36,730 --> 00:03:41,830
所以，如果你坐在樂隊，我的道歉，但第1步，站起來;

66
00:03:41,830 --> 00:03:44,650
第2步，對附近你與任何人，

67
00:03:44,650 --> 00:03:49,360
找出誰是高了，坐下，如果你是短的。

68
00:03:49,360 --> 00:03:51,360
然後重複。

69
00:03:51,360 --> 00:03:56,280
[學生口中念念有詞]

70
00:04:13,450 --> 00:04:15,320
>> 好吧。

71
00:04:15,320 --> 00:04:19,010
好吧。一個放置。你叫什麼名字？ “安德魯。

72
00:04:19,010 --> 00:04:21,959
>> 安德魯，你是最高的人今天在樂隊的部分。

73
00:04:21,959 --> 00:04:28,100
>> 恭喜你。 [掌聲和歡呼]好吧。有一個座位。因此，我們發現安德魯。

74
00:04:28,100 --> 00:04:30,870
但是，如何將它已採取了我，例如，找到安德魯

75
00:04:30,870 --> 00:04:33,740
在這個樂團節50 +左右的人嗎？

76
00:04:33,740 --> 00:04:36,900
我可以採取一個非常簡單的方法，並從這裡開始。

77
00:04:36,900 --> 00:04:39,270
而我有2人站起來和我只是對它們進行比較，

78
00:04:39,270 --> 00:04:42,120
然後我說誰是略短，“好了，你坐下。”

79
00:04:42,120 --> 00:04:44,380
我會記住這位高個子的人。

80
00:04:44,380 --> 00:04:49,030
然後，我再說一遍，再說一遍，再說一遍，我掛在最高的人

81
00:04:49,030 --> 00:04:51,920
直到我發現有人比他們稍微高一點，在這一點

82
00:04:51,920 --> 00:04:54,950
略短的人，然後坐下。

83
00:04:54,950 --> 00:04:57,690
但是，在這個樂隊部分的算法，如果你的N，

84
00:04:57,690 --> 00:05:00,480
該算法要採取的步驟是多少？ >> [學生]。

85
00:05:00,480 --> 00:05:03,580
>> 要取n，正確的，因為在最壞的情況下，可以這麼說，

86
00:05:03,580 --> 00:05:09,090
最高的人是最後的人，我只是隨機的運氣不好。

87
00:05:09,090 --> 00:05:14,260
因此，在最壞的情況下，該算法的運行時間是線性的，它是N，

88
00:05:14,260 --> 00:05:18,070
其中n是總數的人在該空間的大小的問題。

89
00:05:18,070 --> 00:05:19,600
有關此算法呢？

90
00:05:19,600 --> 00:05:22,080
事實上，你都站了起來，然後你再一半的坐了下來，

91
00:05:22,080 --> 00:05:23,950
你一半的坐了下來，你一半的坐了下來。

92
00:05:23,950 --> 00:05:26,070
多少步，如果你在這裡的N？

93
00:05:26,070 --> 00:05:30,200
[學生] n日誌n。 “這將是更糟糕。登錄N。

94
00:05:30,200 --> 00:05:32,930
>> 因此，日誌N，即使你不記得什麼是對數，

95
00:05:32,930 --> 00:05:38,410
現在，只要明白，不知怎麼的，涉及此減半減半，並減少一半。

96
00:05:38,410 --> 00:05:41,000
它不必是2的因數。 3，它可能是一個因素。

97
00:05:41,000 --> 00:05:46,560
但它的這種重複的因子，例如同種大小的問題，從這裡開始

98
00:05:46,560 --> 00:05:49,620
但隨即在這裡，那麼在這裡，然後在這裡，然後在這裡。

99
00:05:49,620 --> 00:05:53,580
你不採取小咬出了問題，你真的砍個不停。

100
00:05:53,580 --> 00:05:56,160
有一個大一舉每個時間。

101
00:05:56,160 --> 00:06:00,810
因此，我們有50人，然後25，然後12½或13人站立，

102
00:06:00,810 --> 00:06:05,370
6½依此類推，直到最後只是安德魯罰站。

103
00:06:05,370 --> 00:06:08,710
因此，我們將調用該日誌的n，你可以想像如下。

104
00:06:08,710 --> 00:06:12,570
回憶這幅畫在這裡就像是一個線性算法紅線，

105
00:06:12,570 --> 00:06:17,520
黃線是2的計數算法，用於計算學生

106
00:06:17,520 --> 00:06:22,300
在過去，但今天的制勝法寶是要保持這個綠色的線

107
00:06:22,300 --> 00:06:25,470
如果我們在樂隊部分人的數量增加一倍，或只是說，

108
00:06:25,470 --> 00:06:29,170
地獄，讓整個房間中的每個人都站起來，而不是什麼大不了的

109
00:06:29,170 --> 00:06:31,560
因為我們的兩倍，有多少人在這裡，

110
00:06:31,560 --> 00:06:33,500
更多的迭代，而不是一個問題。

111
00:06:33,500 --> 00:06:36,200
>> 我們發現安德魯或任何人恰好是身高超過安德魯

112
00:06:36,200 --> 00:06:38,770
在夾層或在陽台上。

113
00:06:38,770 --> 00:06:42,140
因此，這個簡單的想法，我們花了這麼多是理所當然的在電話簿中，

114
00:06:42,140 --> 00:06:46,170
認識到有這麼多不同的地方，我們也可以將它。

115
00:06:46,170 --> 00:06:50,810
我一巴掌一些術語 - 事實上，而不是行話第一，

116
00:06:50,810 --> 00:06:52,750
讓我去給你的圖片在這裡。

117
00:06:52,750 --> 00:06:56,970
現在，我們談到n和n / 2，然後登錄的n，

118
00:06:56,970 --> 00:07:00,500
，但我們可以肯定是，我們將在本學期，

119
00:07:00,500 --> 00:07:05,130
其他類型的數學公式來描述這個一般概念的運行時間。

120
00:07:05,130 --> 00:07:07,580
這些都是現在的內容，因為我們將看到不久

121
00:07:07,580 --> 00:07:09,900
算法，這實際上代表。

122
00:07:09,900 --> 00:07:17,990
>> 但是請注意，這裡的直線n，則直線，其實是非常低的指向右側。

123
00:07:17,990 --> 00:07:22,950
這是一種錯覺，因為我們只需要改變，X軸代表什麼樣

124
00:07:22,950 --> 00:07:26,130
和y軸，並且我們可以使我們想要在任何方向上的直線點。

125
00:07:26,130 --> 00:07:30,350
但原因，它是如此看似平坦

126
00:07:30,350 --> 00:07:35,690
是因為我們需要在這個圖表上的運行時間要慢得多，以騰出空間。

127
00:07:35,690 --> 00:07:39,030
現在，知道有一些很糟糕的算法，在生活中，

128
00:07:39,030 --> 00:07:43,790
其中一些不取n個步驟，或者更好的，記錄n個步驟，但更多。

129
00:07:43,790 --> 00:07:48,820
所以，上面的線N在底部的通知n的n次日誌，

130
00:07:48,820 --> 00:07:51,410
我們會看到，這是什麼意思不久。

131
00:07:51,410 --> 00:07:56,010
以上說的是n的平方，我們還沒有看到任何n的平方算法，但我們要的。

132
00:07:56,010 --> 00:07:57,660
這看起來真的很糟糕。

133
00:07:57,660 --> 00:08:01,610
有2到n，一些指數，感覺更糟糕。

134
00:08:01,610 --> 00:08:05,760
然而，奇怪的是，那麼那裡的N立方，如果你是那種超前的思維，

135
00:08:05,760 --> 00:08:10,000
如果你有種做數學題，2的n其實變得更加截彎取直，

136
00:08:10,000 --> 00:08:15,930
高得多的比n的三次方，如果你足夠遠的軸。

137
00:08:15,930 --> 00:08:19,890
所以注意到現在這些軸是任意2〜10的在x軸上。

138
00:08:19,890 --> 00:08:21,770
>> 這是什麼意思呢？

139
00:08:21,770 --> 00:08:23,890
這意味著，在房間內的2人到10人。

140
00:08:23,890 --> 00:08:27,200
這是所有的x是指：的背景下，無論是大小的問題。

141
00:08:27,200 --> 00:08:30,420
和垂直軸現在是秒或步驟數目的數 - 

142
00:08:30,420 --> 00:08:31,840
一些單位的時間。

143
00:08:31,840 --> 00:08:34,740
但是請注意，它的0〜60和0〜10。

144
00:08:34,740 --> 00:08:38,549
但是，如果我們種縮小時，你可能會在Excel或一些看圖軟件，

145
00:08:38,549 --> 00:08:43,370
我們去了20萬，看到的東西，如2的n

146
00:08:43,370 --> 00:08:47,520
要完全壓倒的n的平方的運行時間，

147
00:08:47,520 --> 00:08:50,960
Ň立方，n日誌n  - 我們已經談了迄今為止的一切。

148
00:08:50,960 --> 00:08:54,190
但美中不足的是，當你開始談論的東西，如Facebook

149
00:08:54,190 --> 00:08:57,150
在那裡你有很多，很多，很多人都相互聯繫，

150
00:08:57,150 --> 00:09:00,650
你有N人，每個人都可能有許多為n的朋友

151
00:09:00,650 --> 00:09:02,860
如果每個人都在世界排序的哥們哥們，

152
00:09:02,860 --> 00:09:08,100
，這是n次，Ň了，所以，可能的N平方友誼，

153
00:09:08,100 --> 00:09:10,950
至少在1個方向，N的平方可能的友誼。

154
00:09:10,950 --> 00:09:15,330
所以這已經表明，搜索Facebook的社交圖，可以這麼說，

155
00:09:15,330 --> 00:09:18,090
可以從在這些種的公式來表示。

156
00:09:18,090 --> 00:09:19,820
>> 我們會回來，並更加具體，

157
00:09:19,820 --> 00:09:23,280
但就目前而言，客觀上為接下來的幾個星期

158
00:09:23,280 --> 00:09:27,170
將是肯定不會去執行的算法或代碼

159
00:09:27,170 --> 00:09:29,870
為此佔用了盡可能多的時間，這樣的事情。

160
00:09:29,870 --> 00:09:33,110
但令人不可思議的事情有關計算機科學，如果你繼續在這一領域

161
00:09:33,110 --> 00:09:38,320
類，如CS121，CS124，這兩者都是理論課，

162
00:09:38,320 --> 00:09:41,300
其實是有在這個世界上存在的一些問題，

163
00:09:41,300 --> 00:09:45,710
，從根本上說，據我們所知，也沒有得到解決得更快

164
00:09:45,710 --> 00:09:48,880
比最壞的這些圖實際上建議。

165
00:09:48,880 --> 00:09:53,660
所以這是一個開放的問題，在這個世界上做的更好，比人類迄今為止很多。

166
00:09:53,660 --> 00:09:56,130
>> 所以，讓我們開始這個例子。

167
00:09:56,130 --> 00:09:59,650
我們看到肖恩這對相機的鬥爭，太笨拙視頻。

168
00:09:59,650 --> 00:10:05,270
但現實情況是，當肖恩的任務是找到這樣的板7號，

169
00:10:05,270 --> 00:10:10,300
記得，我說：“有這些紙片或白色的門背後的地方

170
00:10:10,300 --> 00:10:12,570
“7。肖恩，我們找到它。”

171
00:10:12,570 --> 00:10:14,200
這是奇妙的尷尬觀看

172
00:10:14,200 --> 00:10:15,790
因為他真的在努力解決這個問題。

173
00:10:15,790 --> 00:10:19,720
但現實情況是，肖恩以及在房間裡的任何人都可以做的。

174
00:10:19,720 --> 00:10:21,890
他花了一點時間比一般的人可能有，

175
00:10:21,890 --> 00:10:24,760
但他認為有一些技巧，這個問題，

176
00:10:24,760 --> 00:10:26,590
他認為他失去了一些東西。

177
00:10:26,590 --> 00:10:29,320
它並沒有幫助數以百計的眼睛，軸承在他身上。

178
00:10:29,320 --> 00:10:34,250
>> 但現實的問題是，如果輸入一串隨機數

179
00:10:34,250 --> 00:10:37,120
你被要求找到1號，

180
00:10:37,120 --> 00:10:39,770
你可以做的最好的是線性搜索。

181
00:10:39,770 --> 00:10:44,060
開始在左邊移動到右邊，開始在右邊移動到左邊。

182
00:10:44,060 --> 00:10:48,300
追溯，我們可能會想，“肖恩，為什麼你不只是從另一端嗎？”

183
00:10:48,300 --> 00:10:52,120
7可能很容易地在這裡隨機的，

184
00:10:52,120 --> 00:10:54,980
但我刻意把它放在那裡，因為我想他也不會在年底開始。

185
00:10:54,980 --> 00:10:59,320
所以，我種操縱的情況，但可以是任何地方偶然的機會7。

186
00:10:59,320 --> 00:11:02,380
因此，從右端開始，然後可能是更好的，

187
00:11:02,380 --> 00:11:04,320
但如果明年我謹7其他地方嗎？

188
00:11:04,320 --> 00:11:06,830
這不是從根本上解決問題的辦法 - 

189
00:11:06,830 --> 00:11:10,520
從1月底或其他 - 當你沒有其他的假設。

190
00:11:10,520 --> 00:11:13,620
所以，肖恩開始尋找通過數字，他說：“10，這是不是在這裡。”

191
00:11:13,620 --> 00:11:17,280
然後，他來到這裡，看到19，然後他停約20秒，

192
00:11:17,280 --> 00:11:22,330
然後他打開了13，然後它變得明顯

193
00:11:22,330 --> 00:11:24,270
有沒有這裡似乎有一種模式。

194
00:11:24,270 --> 00:11:28,090
它不是1，2，3，4或等。在數字的差距，這並沒有幫助。

195
00:11:28,090 --> 00:11:32,320
過，事實上，我用這些廉價的紙片覆蓋上的數字

196
00:11:32,320 --> 00:11:35,270
其實是故意的，因為如果我刪除了所有這些紙片，

197
00:11:35,270 --> 00:11:38,760
對我們大多數人，肖恩包括，可能會掃了一眼樣的宏觀

198
00:11:38,760 --> 00:11:43,410
在黑板上，說：“哦，7顯然是正確的。”我們這樣做是瞬間。

199
00:11:43,410 --> 00:11:46,460
>> 而這可能會對人類大腦工作的方式在一定程度上，

200
00:11:46,460 --> 00:11:50,730
但在現實中，可能是他的眼睛或心靈掠過數字由右至左，

201
00:11:50,730 --> 00:11:55,190
左到右，中間就出來了 - 這是怎麼回事生理

202
00:11:55,190 --> 00:11:57,640
這樣，感覺就像是瞬間發生的，

203
00:11:57,640 --> 00:12:01,360
但賠率是即使內部有一些方法，發現7種。

204
00:12:01,360 --> 00:12:05,160
事實上，現在我們談論陣列和數據結構

205
00:12:05,160 --> 00:12:08,780
的計算機的內存裡面，只有我們人類的事情可以做

206
00:12:08,780 --> 00:12:13,070
是看在個人記憶體位置的時間。

207
00:12:13,070 --> 00:12:16,600
>> 因此，所有其他的位置可能被掩蓋了一些一張紙

208
00:12:16,600 --> 00:12:21,170
因為我們看不到也無妨。我們只能做一件事，那就是在一個時間。

209
00:12:21,170 --> 00:12:25,030
因此，在這種情況下，在Sean的情況下，我們來到這裡，然後我們就在這裡

210
00:12:25,030 --> 00:12:31,040
然後我們就在這裡，這裡，這裡，這裡，得到了年底聰明

211
00:12:31,040 --> 00:12:34,450
只是種跳過這個任意，發現7有。

212
00:12:34,450 --> 00:12:37,470
這一次是沒有特別突出的。它也壞了。

213
00:12:37,470 --> 00:12:39,530
但他終於找到了7。

214
00:12:39,530 --> 00:12:45,360
但是，現在的外賣真的是最好的，你可以做的時候沒有信息

215
00:12:45,360 --> 00:12:50,400
隨機排序的數字是從左側或從右側開始。

216
00:12:50,400 --> 00:12:54,950
哎呀，你可以隨意打開門，但即使如此，這是什麼意思是隨機的？

217
00:12:54,950 --> 00:12:57,220
那麼，我們就必須以某種方式正式化意味著什麼，從這裡開始，

218
00:12:57,220 --> 00:13:01,150
然後到了這裡，然後在這裡。肖恩做了偉大的，它是看著很有趣。

219
00:13:01,150 --> 00:13:06,340
我們改變什麼，如果不是一點點的問題，並提出了今年的肖恩，如果你願意嗎？

220
00:13:06,340 --> 00:13:09,460
會有人舞台上，解決一個稍微不同的問題

221
00:13:09,460 --> 00:13:12,330
出現在相機？

222
00:13:12,330 --> 00:13:15,720
>> 讓我們超越的樂隊，因為你們已經相當複雜，今天已經。

223
00:13:15,720 --> 00:13:21,430
怎麼樣，在粉紅色的帽子嗎？下來吧。你叫什麼名字？ “亞歷克斯。 “亞歷克斯。好吧。

224
00:13:21,430 --> 00:13:24,580
因此，亞歷克斯將是今年的Sean，並在未來幾年內將出現在

225
00:13:24,580 --> 00:13:27,770
價值CS50講座。

226
00:13:27,770 --> 00:13:30,340
亞歷克斯，認識你很高興。 >>也很高興見到你。

227
00:13:30,340 --> 00:13:33,470
面臨的挑戰是，你必須在你的手稍微輕鬆一點兒

228
00:13:33,470 --> 00:13:38,950
我告訴你相同的號碼在這裡，但他們現在排序。

229
00:13:38,950 --> 00:13:41,800
所以，現在你的目標是找到7號。

230
00:13:41,800 --> 00:13:45,370
實際上，我們真的應該讓這個 - 你們種作弊行為，就像一台計算機不會，

231
00:13:45,370 --> 00:13:47,990
在看什麼，剛才的數字。

232
00:13:47,990 --> 00:13:50,360
用粉筆，這實際上是要幫助所有的東西，

233
00:13:50,360 --> 00:13:52,810
但讓​​我們假設，你不知道原來的數組。

234
00:13:52,810 --> 00:13:56,600
你現在知道的是，你有一個數組排序的數字

235
00:13:56,600 --> 00:14:00,360
可能有它們之間的差距，你的目標是要找到7號。

236
00:14:00,360 --> 00:14:05,080
你會怎樣，一個合理的人，去發現7號呢？

237
00:14:05,080 --> 00:14:07,770
>> 從低到高嗎？ “好了。轉到低到高。

238
00:14:07,770 --> 00:14:10,990
也不可撕裂他們。讓剛抬起起來，所以我們可以重複使用。

239
00:14:10,990 --> 00:14:14,730
好了，所以1。等待。在你堅持下去，這是1，顯然是錯誤的。

240
00:14:14,730 --> 00:14:17,270
所以通過你的頭腦是怎麼回事呢？你的下一步行動是什麼？

241
00:14:17,270 --> 00:14:23,250
下一個。 “好了。下一個。好。 3，那麼不正確。你的下一步行動是什麼？

242
00:14:23,250 --> 00:14:27,670
繼續下去。 >>所有權利。繼續下去。 5。

243
00:14:27,670 --> 00:14:31,110
因此，保持下去，並讓我交給你為後人。

244
00:14:31,110 --> 00:14:35,720
7。 >>太優秀了。非常好。找到了7號。 [掌聲]

245
00:14:35,720 --> 00:14:39,720
所以這是很好的，但肖恩也發現7號。

246
00:14:39,720 --> 00:14:44,490
我說，你還沒有真正利用這個額外的資料片，

247
00:14:44,490 --> 00:14:47,780
這是，這些數字的排序條件。

248
00:14:47,780 --> 00:14:51,520
因此，我們可以做的更好？任何建議嗎？是啊，在後面。

249
00:14:51,520 --> 00:14:54,710
[學生]二進制搜索。 >>我不知道什麼是二進制搜索。

250
00:14:54,710 --> 00:14:58,030
>> [學生]開始在中間。 “開始在中間。好吧。因此，讓我們看看我們是否能到達那裡。

251
00:14:58,030 --> 00:15:02,580
所以，如果不是有人告訴你從中間開始，去進取，不斷開拓中間的門。

252
00:15:02,580 --> 00:15:04,580
有8人，所以你將有任意選擇一個

253
00:15:04,580 --> 00:15:09,800
稍微向左或向右。好吧。 7！ [掌聲]非常不錯的。

254
00:15:09,800 --> 00:15:11,410
好了，但在我們這個嗎？

255
00:15:11,410 --> 00:15:14,990
讓我們假設只是為了打破平局，你已經開始在這裡

256
00:15:14,990 --> 00:15:16,670
因為，同樣可以發生。

257
00:15:16,670 --> 00:15:19,540
我們正好知道7。因此，這是13。

258
00:15:19,540 --> 00:15:21,980
所以，如果他們排序，我們才剛剛開始在中間，

259
00:15:21,980 --> 00:15:24,600
會是什麼最佳下一步的行動了嗎？

260
00:15:24,600 --> 00:15:27,740
轉到左邊。所以來這裡的電話簿的例子。

261
00:15:27,740 --> 00:15:30,130
如果13是在這裡，我們知道對列表進行排序，

262
00:15:30,130 --> 00:15:33,900
所有這些紙片是無趣的，我們現在

263
00:15:33,900 --> 00:15:37,400
因為我們已經知道，必須向左側

264
00:15:37,400 --> 00:15:39,510
如果這些數字進行排序，我們發現有13。

265
00:15:39,510 --> 00:15:42,500
>> 那麼，什麼是你的下一步行動在這裡？ >>跳轉到左邊。 >>好，好。

266
00:15:42,500 --> 00:15:45,080
所以，去到左邊， - 等待，嘿，嘿，嘿。這是一種欺騙行為。

267
00:15:47,140 --> 00:15:51,350
所以，你發現7，但我們剛剛申請的算法是什麼？

268
00:15:51,350 --> 00:15:56,450
開始在中間。 >>好。那麼什麼是合乎邏輯的延伸，同樣的想法嗎？

269
00:15:56,450 --> 00:15:58,970
哦，不僅僅是這些。 “沒錯。 “等我從這裡開始。 >>好。

270
00:15:58,970 --> 00:16:02,020
所以，現在我們就略向左側。這是3。

271
00:16:02,020 --> 00:16:05,310
但有趣的外賣現在是哪一個你不關心嗎？

272
00:16:05,310 --> 00:16:08,040
這2個。 >>這2個。所以，現在這個可以走，這一次可以走。

273
00:16:08,040 --> 00:16:12,330
這是8，然後現在的問題是，現在是大小尺寸為4 2。

274
00:16:12,330 --> 00:16:16,430
我們已經很接近了。同樣，到中間的這2個元素。

275
00:16:16,430 --> 00:16:20,430
>> 好吧。因此，這是不幸的，現在我們總是要離開了，因為我們是向下舍入。

276
00:16:20,430 --> 00:16:25,150
但是，這很好，因為我們現在拋出這個遠離一切，留給我們的只有7。

277
00:16:25,150 --> 00:16:30,490
讓我們掌聲雷動。我們再次發現了7。 [掌聲]好吧。當然。

278
00:16:30,490 --> 00:16:32,220
掛在1秒鐘。

279
00:16:32,220 --> 00:16:36,630
儘管這過程中種了一點點的時間比我們認為這將

280
00:16:36,630 --> 00:16:40,150
坦率地說，你的第一直覺是最好的，對不對？我們發現瞬間。

281
00:16:40,150 --> 00:16:46,740
但我們會發現7的速度，無論什麼時候，在這個例子中，而這個

282
00:16:46,740 --> 00:16:50,100
因為，如果所有的數字排序，就像在電話簿的頁面，

283
00:16:50,100 --> 00:16:54,580
事實上，你可以砍一半的問題再，再而三。

284
00:16:54,580 --> 00:16:56,740
這是不是很容易看到這一點只有8個數字

285
00:16:56,740 --> 00:17:00,100
相對於一個1000頁的電話本，你真的看到在視覺上，

286
00:17:00,100 --> 00:17:03,120
但在這種情況下，在這裡，當肖恩搜索7，

287
00:17:03,120 --> 00:17:06,020
多少步驟，在最壞的情況下，它會採取他嗎？ >> [學生] 7。

288
00:17:06,020 --> 00:17:11,670
7在最壞的情況下。那麼，在最壞的情況下，如果有8個門。

289
00:17:11,670 --> 00:17:13,440
他將採取8個步驟。

290
00:17:13,440 --> 00:17:18,170
>> 因此，如果有的n門，它可能已採取肖恩在幾年前n個步驟。

291
00:17:18,170 --> 00:17:21,520
現在，亞歷克斯，你的情況，因為這些數字進行排序 - 

292
00:17:21,520 --> 00:17:25,130
我們可以推斷出這一點，我們從那裡一直迄今為止，在這個故事中的一種 - 

293
00:17:25,130 --> 00:17:28,300
亞歷克斯的更智能的算法的運行時間

294
00:17:28,300 --> 00:17:30,770
從中間開始，然後重複？

295
00:17:30,770 --> 00:17:36,490
[學生] 3。 “所以，這將是3，粗略地說，如果你去從8日至4以2比1。

296
00:17:36,490 --> 00:17:40,660
因此，3個步驟，或者，更普遍的是，這是日誌n再次。

297
00:17:40,660 --> 00:17:43,380
任何時候，你要減半，減半減半和減半，

298
00:17:43,380 --> 00:17:45,290
這是一個表達這種想法的日誌n。

299
00:17:45,290 --> 00:17:48,140
因此，該會已採取你只有3個步驟，它的確做到了

300
00:17:48,140 --> 00:17:50,890
一旦我們打開門減半減半，

301
00:17:50,890 --> 00:17:53,770
而這一切都採取肖恩約7或8個步驟。

302
00:17:53,770 --> 00:17:56,330
所以，謝謝你為我們今年。 >>謝謝。很高興見到你。

303
00:17:56,330 --> 00:18:00,170
謝謝亞歷克斯。 ，>>類似地。 [掌聲]

304
00:18:00,170 --> 00:18:02,150
>> 那麼真正的含義是什麼？

305
00:18:02,150 --> 00:18:06,050
現在想像一下，這是不是8個門，其中，坦白地說，我們所有能找到的東西

306
00:18:06,050 --> 00:18:10,430
後面8門很快就撕開紙片，與我們的本能。

307
00:18:10,430 --> 00:18:14,430
但是，如果它是一個萬門？如果它是4十億門？

308
00:18:14,430 --> 00:18:19,630
4十億門的情況下，你真的想要去Alex的算法，

309
00:18:19,630 --> 00:18:23,150
二進制搜索，因為我們將開始稱這是“或”分而治之“，更普遍的，

310
00:18:23,150 --> 00:18:25,220
你可以將減半，並減少一半的問題，

311
00:18:25,220 --> 00:18:30,510
因為如果你有4十億門，多少次，你砍四十億一半嗎？

312
00:18:30,510 --> 00:18:33,870
[學生] 32。 >>這是實際上是32。您可以在紙上或在你的頭上。

313
00:18:33,870 --> 00:18:38,490
你去四十億2億至1十億半十億，至250億美元，點，點，點。

314
00:18:38,490 --> 00:18:41,620
如果你做出來的數學，你要確實得到32，

315
00:18:41,620 --> 00:18:44,950
，這實際上涉及到計算機科學，因為我們平時的2的冪數。

316
00:18:44,950 --> 00:18:47,600
2到32恰好是4億美元。

317
00:18:47,600 --> 00:18:51,440
所以有很多的這些權力2種計算機科學相關。

318
00:18:51,440 --> 00:18:55,120
>> 但約8億美元呢？多少個步驟是，將要採取的如果有8十億大門呢？

319
00:18:55,120 --> 00:19:00,350
[學生] 33。 “等33。如果有16十億門？多少個步驟是，將要採取的嗎？

320
00:19:00,350 --> 00:19:05,020
[學生] 34。 >> 34。我們可以繼續令人生厭。但是，這是一個強大的東西。

321
00:19:05,020 --> 00:19:09,430
你可以介紹你的問題，但更多的投入到數十億，沒什麼大不了的，

322
00:19:09,430 --> 00:19:14,140
你只需要1個附加咬了一口，從而為我們提供了類似二進制搜索

323
00:19:14,140 --> 00:19:15,920
“或”分而治之“，更普遍。

324
00:19:15,920 --> 00:19:17,990
但我是那種欺騙在這裡，對不對？

325
00:19:17,990 --> 00:19:22,410
她在Alex的算法的情況下，肖恩的優勢。

326
00:19:22,410 --> 00:19:27,780
她知道，這些數字進行排序，但亞歷克斯沒有自己對它們進行排序。

327
00:19:27,780 --> 00:19:30,520
我提前來到了確保在黑板上種

328
00:19:30,520 --> 00:19:33,670
我畫了他們所有的排序順序，然後我介紹了他們的論文。

329
00:19:33,670 --> 00:19:35,850
但多少工作，這是我嗎？

330
00:19:35,850 --> 00:19:40,110
如果我們已經開始了與這些數字在一些看似隨機的順序 - 

331
00:19:40,110 --> 00:19:43,320
在這種情況下，這些簡單的數字，1至8在這裡 - 

332
00:19:43,320 --> 00:19:46,090
我們怎麼去排序這些值嗎？

333
00:19:46,090 --> 00:19:52,530
如果你是一個人，這個任務，你會採取什麼樣的直觀的方法

334
00:19:52,530 --> 00:19:54,800
一大堆的數字進行排序？

335
00:19:54,800 --> 00:19:57,050
這些東西拼圖。是啊。

336
00:19:57,050 --> 00:19:59,950
>> [學生]我想每個數字比較，每一個

337
00:19:59,950 --> 00:20:03,180
並保持要左邊。 >>好，好。

338
00:20:03,180 --> 00:20:05,720
所以，每一個數字，它旁邊的一個比較，

339
00:20:05,720 --> 00:20:09,610
，然後就繼續沿著列表，種rejiggering的事情，當您去。

340
00:20:09,610 --> 00:20:13,800
所以，在這裡，我們有一個機會，也許更多的人參與進來。

341
00:20:13,800 --> 00:20:16,290
我們有更多的志願者誰願意上來嗎？

342
00:20:16,290 --> 00:20:23,950
少一點壓力，因為你不是唯一的一個。 1，2，3，4，5，6，7，8。

343
00:20:23,950 --> 00:20:28,190
下來吧。你們都將是數字1到8。

344
00:20:28,190 --> 00:20:36,050
讓我們來看看如果我們不能做到這一點排序亞歷克斯以同樣的方式，我做到了提前。

345
00:20:36,050 --> 00:20:37,640
1，2，3，4。

346
00:20:37,640 --> 00:20:40,760
來吧，如果你願意，舞台上的音樂之間的立場，我在這裡

347
00:20:40,760 --> 00:20:44,960
以相同的順序在屏幕上滑動。

348
00:20:47,910 --> 00:20:49,680
嗯，哦。

349
00:20:50,370 --> 00:20:53,230
我們將工作，你到下一個例子。哦，等等，等等。在這裡，我們走了。等待。

350
00:20:53,230 --> 00:20:57,570
下面的例子是現在。在這裡，你走。第8號。上來吧。

351
00:20:57,570 --> 00:21:00,270
好的。排序自己根據本。

352
00:21:00,270 --> 00:21:03,620
只是一點點滑動側面的音樂站在這裡。

353
00:21:03,620 --> 00:21:12,310
因此，我們有4個，2，6  - 在那裡，在這裡，就在這裡 -  3。

354
00:21:12,310 --> 00:21:17,570
是啊。好吧。你在這裡。不，你呆在那裡。

355
00:21:17,570 --> 00:21:21,840
是的，沒錯。不，我是錯的。就在那裡。好了，非常好。好吧。

356
00:21:21,840 --> 00:21:24,930
現在讓我們來對它們進行排序按遞增順序。

357
00:21:24,930 --> 00:21:26,210
>> 我怎麼能這樣做呢？

358
00:21:26,210 --> 00:21:28,630
剛才提出的算法是，為什麼我們不比較

359
00:21:28,630 --> 00:21:31,970
的人誰種下彼此，然後修復任何錯誤，

360
00:21:31,970 --> 00:21:33,540
移動由左到右。

361
00:21:33,540 --> 00:21:36,580
所以，在這裡，我們有4個和2個明顯的。讓我們交換你。好吧。

362
00:21:36,580 --> 00:21:40,760
所以我現在要向下移動一行。 4和6，沒。 [笑聲]

363
00:21:40,760 --> 00:21:45,010
6和8，很不錯。 8和1，讓我換你們。好的。

364
00:21:45,010 --> 00:21:48,030
因此，8和3，交換你們。

365
00:21:48,030 --> 00:21:52,280
8和7，讓我換你們。 5和8，優良的。

366
00:21:52,280 --> 00:21:54,820
我給你一個排序的列表。

367
00:21:54,820 --> 00:21:56,860
好的。所以不大。

368
00:21:56,860 --> 00:22:01,180
但它是更好，因為更大的數字 -  8點 - 

369
00:22:01,180 --> 00:22:04,030
有怎樣的冒了出來，從左邊到右邊。

370
00:22:04,030 --> 00:22:08,010
所以我得到了1對的，但感覺這樣的問題並沒有完全解決。

371
00:22:08,010 --> 00:22:11,150
>> 所以，你會建議我們下一步要做的嗎？ >> [學生]繼續做下去。 >>我們繼續做下去。

372
00:22:11,150 --> 00:22:13,740
而實現，我們再次設置的東西，只是讓所有的人

373
00:22:13,740 --> 00:22:17,180
排序聰明地安排自己的基礎上，圖片，

374
00:22:17,180 --> 00:22:19,040
但現在我們要更加有條不紊。

375
00:22:19,040 --> 00:22:21,510
我們是它的算法，雖然我們編寫代碼 - 

376
00:22:21,510 --> 00:22:23,520
在這種情況下，口頭的偽代碼。

377
00:22:23,520 --> 00:22:26,040
所以，讓我們再試一次。這工作得很好。它並沒有解決它。

378
00:22:26,040 --> 00:22:30,400
但是，當它懷疑，嘗試，再嘗試。 SO 2和4，沒有幫助了。

379
00:22:30,400 --> 00:22:33,200
4和6。 “啊！ 6和1，現在稍微好一點。

380
00:22:33,200 --> 00:22:39,740
3，良好的。 6和7，7和5，7和8，良好。

381
00:22:39,740 --> 00:22:44,060
你知道，我也許可以忽略現在，因為他是在列表末尾。

382
00:22:44,060 --> 00:22:47,250
也許我們不必擔心有人路過他。

383
00:22:47,250 --> 00:22:49,240
但是讓我們看看如果這是一個安全的假設。

384
00:22:49,240 --> 00:22:52,340
現在的名單是 - 該死的 - 沒有排序。讓我們再試一次。

385
00:22:52,340 --> 00:22:56,440
因此，2和4，4和1，4和3。

386
00:22:56,440 --> 00:22:59,230
圖4和圖6，良好。 6和5，良好的。

387
00:22:59,230 --> 00:23:04,890
6，7，和8，良好的。但是請注意，我只是停在這裡現在，現在停在這裡嗎？

388
00:23:04,890 --> 00:23:07,770
[學生]是的。 >>呀？

389
00:23:07,770 --> 00:23:11,160
如果你已經一路9號有什麼？

390
00:23:11,160 --> 00:23:13,640
它已排序的。 >>好。這已排序的第一時間。

391
00:23:13,640 --> 00:23:16,050
好。所以，讓我們再回去。我們快到了。

392
00:23:16,050 --> 00:23:22,800
1和2，2和3，3和4，4和5，5和6，6和7，7和8。

393
00:23:22,800 --> 00:23:26,640
>> 我現在所做的，但同樣，我是一個電腦，可以做什麼，我告訴我說，做，

394
00:23:26,640 --> 00:23:30,120
現在是我唯一的回憶，其實我只是做了一點工作。

395
00:23:30,120 --> 00:23:31,700
這裡發生了改變。

396
00:23:31,700 --> 00:23:37,100
所以我沒有視覺或技術上確認確實排序算法，此列表。

397
00:23:37,100 --> 00:23:40,720
所以剛剛好措施，只是肛門約，讓我們這樣做更多的時間。

398
00:23:40,720 --> 00:23:44,040
因此，1和2中，2和3，3和4。你知道嗎？

399
00:23:44,040 --> 00:23:46,190
說的好措施，我要跟踪我的手，這

400
00:23:46,190 --> 00:23:51,110
多少掉期，我只是讓我知道多少工作，其實我已經做了。

401
00:23:51,110 --> 00:23:56,930
3和4，4和5，5和6，6和7，7和8。掉期交易。

402
00:23:56,930 --> 00:24:00,800
所以，現在我將合法是一個白痴再次做到這一點

403
00:24:00,800 --> 00:24:03,330
因為如果我這樣做沒有工作的人通過本通，

404
00:24:03,330 --> 00:24:06,710
那麼顯然會再次發生，如果他們都不是那種隨機

405
00:24:06,710 --> 00:24:10,410
adversarially自己身邊。所以，現在我可以停止。

406
00:24:10,410 --> 00:24:15,120
現在，讓我們問這樣的問題，多少工作，這實際上把我嗎？

407
00:24:15,120 --> 00:24:18,260
多少步驟？ >> N的平方。

408
00:24:18,260 --> 00:24:20,400
是的，所以n的平方。你在哪裡得到n的平方呢？

409
00:24:20,400 --> 00:24:22,660
你必須檢查每一個NUM  - 

410
00:24:22,660 --> 00:24:26,530
有n個數，並與其他n個數字，你必須檢查每一個數字。

411
00:24:26,530 --> 00:24:29,030
好。 “因此，它的N的平方。 >>好。

412
00:24:29,030 --> 00:24:31,060
>> 所以感覺像它很可能是n的平方，正確的嗎？

413
00:24:31,060 --> 00:24:33,820
這些傢伙的N，8特別是在這種情況下，

414
00:24:33,820 --> 00:24:37,590
但通過這個列表每次我去，我是比較對第二次的第一人，

415
00:24:37,590 --> 00:24:39,650
第二對第三一遍又一遍，

416
00:24:39,650 --> 00:24:42,450
當我到了年底，我做了什麼？我重做了。

417
00:24:42,450 --> 00:24:46,280
因此，如果我們概括這樣的解釋，我們有N多人

418
00:24:46,280 --> 00:24:51,090
，我，很明顯，8個步驟，n個步驟，我每次去通過這個算法。

419
00:24:51,090 --> 00:24:56,070
但我有多少次，在最壞的情況下通過這個列表的人去嗎？

420
00:24:56,070 --> 00:24:59,370
[學生] N倍。 >>大概N，正確的，因為在最壞的情況下，

421
00:24:59,370 --> 00:25:03,410
什麼可能是最糟糕的情況下，安排這些傢伙從一開始就？

422
00:25:03,410 --> 00:25:06,520
如果他們完全相反的順序

423
00:25:06,520 --> 00:25:09,310
因為只是想精神，let's  - 你叫什麼名字？ “博文。

424
00:25:09,310 --> 00:25:12,510
博文。好吧。因此，博文，到這兒來，一會兒就好了。

425
00:25:12,510 --> 00:25:16,150
>> 假設鮑恩在算法開始時，在這裡，

426
00:25:16,150 --> 00:25:19,790
我們不知道其他人，但鮑恩在這裡，根據這個算法 - 

427
00:25:19,790 --> 00:25:23,820
，如果你想與我漫步 - 要泡了，因為他做的第一時間，

428
00:25:23,820 --> 00:25:25,740
所有的方式結束。

429
00:25:25,740 --> 00:25:29,400
但是，假如博文旁邊的人是7號。

430
00:25:29,400 --> 00:25:33,450
我要回去拿7號，這意味著我必須去所有的方式回到這裡。

431
00:25:33,450 --> 00:25:36,980
現在，我必須有同樣的散步，誰是7號的人。

432
00:25:36,980 --> 00:25:40,140
但是，6號他旁邊的是什麼？

433
00:25:40,140 --> 00:25:42,180
然後，我要回去，並得到6。

434
00:25:42,180 --> 00:25:46,490
所以，再一次，我說的就是這個循環的每個迭代的n每個人，

435
00:25:46,490 --> 00:25:50,090
我可能使n，這些散步，以確保我拉

436
00:25:50,090 --> 00:25:53,760
所有的最大的元素和背部，到了最後的名單。

437
00:25:53,760 --> 00:25:58,230
所以N的n次，n次n或n的平方。

438
00:25:58,230 --> 00:26:02,050
>> 所以在這裡，我們已經有一個算法，不再n，即不再日誌n，

439
00:26:02,050 --> 00:26:04,820
它實際上比我們以前做過的任何事情更糟糕。

440
00:26:04,820 --> 00:26:09,840
因此，亞歷克斯種很幸運，我做了所有的工作顯然她的面前，

441
00:26:09,840 --> 00:26:14,690
所有的昂貴的工作，這樣她就可以享受在這個二進制搜索算法，

442
00:26:14,690 --> 00:26:16,420
這是日誌的n。

443
00:26:16,420 --> 00:26:18,240
但是，這與週一的主題是一致的。

444
00:26:18,240 --> 00:26:23,260
我們給多一點點空間，我們使用的位數越多，為了加快我們的運行時間。

445
00:26:23,260 --> 00:26:26,170
因此，很像有這個時間和空間之間的權衡，

446
00:26:26,170 --> 00:26:31,060
也有可能是權衡之間花費的時間前樣的東西準備去

447
00:26:31,060 --> 00:26:35,000
實際執行的算法，如搜索。讓我們嘗試另一種。

448
00:26:35,000 --> 00:26:39,050
如果你們不介意只是快速地重新安排自己再次匹配，

449
00:26:39,050 --> 00:26:42,240
讓我們嘗試略有不同的東西，這是不是很簡單

450
00:26:42,240 --> 00:26:45,760
作為剛修好的的成對錯誤，這是超級直觀的。

451
00:26:45,760 --> 00:26:48,150
的，而不是讓我們多一點故意做這個。

452
00:26:48,150 --> 00:26:51,010
這一次，我也將提出可能是非常直觀的。

453
00:26:51,010 --> 00:26:55,070
>> 讓我們從列表中選擇最小的人一次又一次地。所以，在這裡，我們走了。

454
00:26:55,070 --> 00:26:57,350
4，你是我見過這麼遠的最小的人，

455
00:26:57,350 --> 00:27:00,520
所以我要精神上記住，只是指著你現在的。

456
00:27:00,520 --> 00:27:05,020
2。哦！忘記4號。我剛剛發現的最小的元素在此列表中。

457
00:27:05,020 --> 00:27:07,410
我要種記住這一點。 6，8。

458
00:27:07,410 --> 00:27:11,190
哦！ 1。再見。所以現在我會記住數字1。

459
00:27:11,190 --> 00:27:14,790
我們知道，1是最小的，但我的電腦。如果有一個0？

460
00:27:14,790 --> 00:27:17,140
如果是-1？我必須繼續下去。

461
00:27:17,140 --> 00:27:20,990
因此，3，7，5，沒了。好吧。因此，數字1是最小的。

462
00:27:20,990 --> 00:27:23,640
讓我從列表中選擇你 - 我們就會走這條路 - 

463
00:27:23,640 --> 00:27:27,760
任意把你在年初的列表。

464
00:27:27,760 --> 00:27:29,740
現在，等待一分鐘。我有種上當受騙。

465
00:27:29,740 --> 00:27:34,010
如果這些人不是代表8人，而是一個數組列表，

466
00:27:34,010 --> 00:27:37,050
8的連續內存塊 - 你不介意退一步就一下嗎？

467
00:27:37,050 --> 00:27:39,060
實際上，有沒有空間，你在這裡。

468
00:27:39,060 --> 00:27:41,840
那麼，如何才能使空間 - 你叫什麼名字？ “薩米。 “薩米。

469
00:27:41,840 --> 00:27:43,710
我們如何讓空間為薩米？

470
00:27:43,710 --> 00:27:46,760
>> 我們將n表示在我面前。 “好了。

471
00:27:46,760 --> 00:27:48,850
因此，我們可以把n個人在他面前的人，

472
00:27:48,850 --> 00:27:52,400
所以如果你們想故意的，戲劇性的一步到左邊。

473
00:27:52,400 --> 00:27:57,000
他們都做到步調一致，但我最後一次寫了一些代碼，

474
00:27:57,000 --> 00:27:59,740
你不能排序的移動很多事情都在。

475
00:27:59,740 --> 00:28:02,450
我們可以做一個循環中，每個人都曾經在一段時間移動。

476
00:28:02,450 --> 00:28:04,340
所以，如果你們不介意退一步的權利，

477
00:28:04,340 --> 00:28:07,230
和Sammy，如果你能後退一步，因為還是有沒有為你的房間，

478
00:28:07,230 --> 00:28:11,420
現在讓我們做到這一點。是Sammy剛才？就在那裡。

479
00:28:11,420 --> 00:28:16,140
所以還有一定的差距。所以，你可以移動到Sammy的點。

480
00:28:16,140 --> 00:28:20,580
旁邊的人了，現在旁邊的人，旁邊的人。現在我們有房為薩米。

481
00:28:20,580 --> 00:28:23,490
現在，有人從觀眾 - 這是很好的，這是正確的，

482
00:28:23,490 --> 00:28:27,070
它覺得有點費時的 - 什麼是快？是啊。

483
00:28:27,070 --> 00:28:29,440
[學生]一個新的陣列？ >>那是什麼？ >> [學生]一個新的陣列？ >>好，好。

484
00:28:29,440 --> 00:28:33,200
>> 公正的貿易平衡，符合這個主題，為什麼沒有我只是一個新的數組

485
00:28:33,200 --> 00:28:36,570
 然後Sammy將游泳在這些人面前的空間，例如，

486
00:28:36,570 --> 00:28:39,600
我們就可以開始填充一個新的數組。這也是工作。

487
00:28:39,600 --> 00:28:42,450
但我不感興趣花費更多的空間。另一種方法是什麼？

488
00:28:42,450 --> 00:28:46,630
[學生]交換。 “好了。我們可以交換這兩個傢伙。你叫什麼名字？

489
00:28:46,630 --> 00:28:49,390
馬里奧。 “馬里奧。所以，馬里奧，你目前在這裡。

490
00:28:49,390 --> 00:28:52,480
薩米，你可以備份只是一瞬間嗎？馬里奧在這裡。

491
00:28:52,480 --> 00:28:55,830
我們沒有你的空間了，所以，如果你不介意的薩米是，

492
00:28:55,830 --> 00:29:02,430
我們就會把薩米在這裡，現在我要說的是Sammy的交換操作的速度更快。

493
00:29:02,430 --> 00:29:06,370
我們做了的交換操作這些傢伙，也許2交換這些傢伙，

494
00:29:06,370 --> 00:29:11,210
但我們沒有做1，2，3，4，這樣的感覺更好。現在，等待一分鐘。

495
00:29:11,210 --> 00:29:14,660
我種使問題變得更糟，因為4種接近年初。

496
00:29:14,660 --> 00:29:19,470
4號是為此一點點接近，但我真的不知道或關心的。

497
00:29:19,470 --> 00:29:23,330
因此，這只是運氣不好，4號是一點點遠離其注定的地方。

498
00:29:23,330 --> 00:29:25,110
現在讓我們重複這個算法。

499
00:29:25,110 --> 00:29:28,410
>> 總括來說，只要這個故事，所有我們所做的只是遍歷這個列表

500
00:29:28,410 --> 00:29:31,130
尋找最小的人。

501
00:29:31,130 --> 00:29:34,530
所以，現在讓我們再做一次。我們不必擔心薩米了。

502
00:29:34,530 --> 00:29:37,590
我們可以去這裡。哦！編號2。這是一個非常小的數字。

503
00:29:37,590 --> 00:29:41,180
6，8，4，3，7，5。好，好。

504
00:29:41,180 --> 00:29:43,770
幸運的是，巧合的是，我沒有動 -  >>威利。

505
00:29:43,770 --> 00:29:45,910
威利，因為他是在他的正確的地方。

506
00:29:45,910 --> 00:29:48,110
讓我們再這樣做，而忽略這兩個傢伙。

507
00:29:48,110 --> 00:29:50,460
6。這是一個非常小的數字。哦！ 8肯定是更大的。

508
00:29:50,460 --> 00:29:53,410
4。讓我們把注意力集中在4。哦！ 3，甚至更好。

509
00:29:53,410 --> 00:29:58,290
7和5。那麼，我們該怎麼辦 -  >>羅傑。 “羅傑？

510
00:29:58,290 --> 00:30:00,250
讓我們來交換他的6號。

511
00:30:00,250 --> 00:30:03,570
所以，如果想6和3交換，

512
00:30:03,570 --> 00:30:07,320
我們現在已經種得到幸運的，6是接近的地方，她應該是，

513
00:30:07,320 --> 00:30:10,300
但在這裡只是巧合。現在讓我們去這裡。

514
00:30:10,300 --> 00:30:13,430
圖8是一個非常小的數字。哦！圖4是較小的。

515
00:30:13,430 --> 00:30:17,130
6，7，5。什麼我們現在做的嗎？ >>交換。 “沒錯。

516
00:30:17,130 --> 00:30:19,010
所以，現在讓我們做這種快。

517
00:30:19,010 --> 00:30:24,460
8，6，7，5。哪裡5去了？好。好吧。

518
00:30:24,460 --> 00:30:28,380
6，7，8。 6到留在她。你叫什麼名字？ “羅莎莉。

519
00:30:28,380 --> 00:30:31,770
羅莎莉可以留在她。 7到 - 讓我們來看看。 7，8。好吧。

520
00:30:31,770 --> 00:30:35,100
所以得到保持，她是。你叫什麼名字？ >> Amna。 >> Amna。

521
00:30:35,100 --> 00:30:39,670
>> 所以Amna可以留在她的是，與已經在那裡他現在應該是8號。

522
00:30:39,670 --> 00:30:43,960
好，好。感覺就像我們剛剛為自己創造工作，在這裡，雖然。

523
00:30:43,960 --> 00:30:47,440
最後該算法的運行時間？

524
00:30:47,440 --> 00:30:51,900
如果我們認為這些人不為8，但為n？ >>的n。

525
00:30:51,900 --> 00:30:55,440
它的n個步驟，但我們每一次檢查。

526
00:30:55,440 --> 00:30:57,570
好吧。 N而你每一次檢查？

527
00:30:57,570 --> 00:31:03,450
好的，但如果它的n個步驟，不應該我已經能夠為您解決您正要1，2，3，4？

528
00:31:03,450 --> 00:31:05,590
哦！好了，這是一個很大的區別。

529
00:31:05,590 --> 00:31:08,050
因此n的平方為什麼呢？到底發生了什麼？

530
00:31:08,050 --> 00:31:12,130
在此列表中有n個人，而是要找到列表中的最小的人

531
00:31:12,130 --> 00:31:16,200
在最壞的情況下，我要採取許多步驟？ >> N.

532
00:31:16,200 --> 00:31:19,160
>> N，對了，因為在最壞的情況下，1號是一路那邊，

533
00:31:19,160 --> 00:31:20,990
所以我必須去得到他或她的。

534
00:31:20,990 --> 00:31:25,500
然後當我終於實現1是最小的，那麼它是相當快的交換。

535
00:31:25,500 --> 00:31:28,450
但現在我必須從頭開始，看是誰嗎？

536
00:31:28,450 --> 00:31:31,980
下一個最小的人，這是2。凡在最壞的情況下為2？

537
00:31:31,980 --> 00:31:34,320
哦，我的上帝。這一切都在這裡結束的方式。

538
00:31:34,320 --> 00:31:37,000
所以，現在我只是做了另一種n步，另一個n個步驟。

539
00:31:37,000 --> 00:31:41,200
如果我們有n個人，在最壞的情況下，最小的人是n步之遙，

540
00:31:41,200 --> 00:31:45,230
這再次n次，n，且讓我們再次有n個平方。

541
00:31:45,230 --> 00:31:47,280
這是不是感覺這麼好。

542
00:31:47,280 --> 00:31:52,150
而事實上，即使在最好的情況下 - 假設他們開始排序 - 

543
00:31:52,150 --> 00:31:59,080
它需要多少步我使用這種算法排序N多人嗎？

544
00:31:59,080 --> 00:32:01,010
Ň的平方。 >>我聽到Ň的平方。為什麼Ň平方？

545
00:32:01,010 --> 00:32:05,240
因為你仍然必須檢查每一個時間。 >>呀。

546
00:32:05,240 --> 00:32:08,060
你有來交換他們。 ，>>即使我們人類是一種全知

547
00:32:08,060 --> 00:32:10,770
在這個意義上，視覺上，我們就可以看到，這是排序的種，

548
00:32:10,770 --> 00:32:12,140
一台計算機是沒有那麼聰明。

549
00:32:12,140 --> 00:32:14,040
要看看這裡和這裡和這裡，

550
00:32:14,040 --> 00:32:16,610
但如果它在尋找什麼是最小的元素，

551
00:32:16,610 --> 00:32:22,110
你只知道你什麼時候發現的最小元素？一旦你在最後。

552
00:32:22,110 --> 00:32:25,880
但在這一點上，你只找到了目前最小的元素。

553
00:32:25,880 --> 00:32:28,810
你不一定知道別的世界的狀態。

554
00:32:28,810 --> 00:32:30,880
所以，你必須去再，再而三。

555
00:32:30,880 --> 00:32:34,880
>> 所以這一次我真的看起來愚蠢的，因為，好吧，我檢查2，你是最小的，

556
00:32:34,880 --> 00:32:37,530
但我不知道，在總。

557
00:32:37,530 --> 00:32:41,090
3，4，5，6，7，8。好，好。 2確實是最小的。

558
00:32:41,090 --> 00:32:43,150
現在，讓我們找到下一個最小的。好吧。

559
00:32:43,150 --> 00:32:48,350
3，你是目前國內最小的。讓我們來看看。 4，5，6，7，8。好了，很幸運的了。

560
00:32:48,350 --> 00:32:53,170
3確實是在正確的地方。但我會繼續這樣做，再，再而三。

561
00:32:53,170 --> 00:32:55,990
我們怎樣才能做到以往任何時候都稍微好一點的呢？

562
00:32:55,990 --> 00:33:00,120
相反的人，泡了從最小到最大的兩兩

563
00:33:00,120 --> 00:33:04,350
，而不是在列表中選擇了當時最小的人來來回回，

564
00:33:04,350 --> 00:33:09,780
我們為什麼不，而不是將這些人進入一個新的列表步驟一步？

565
00:33:09,780 --> 00:33:13,080
讓我們來試試這個。現在讓我叫這個東西插入排序。

566
00:33:13,080 --> 00:33:17,250
所以，在這裡，我們都在這裡。號碼1。在此列表中的其他任何人，我不在乎。

567
00:33:17,250 --> 00:33:21,310
現在我的目標是把1號的開頭的排序列表。

568
00:33:21,310 --> 00:33:23,910
我要提出，因為我只有8個內存塊，

569
00:33:23,910 --> 00:33:28,670
隨意現在的我，我的所謂的未排序的列表之間的牆，

570
00:33:28,670 --> 00:33:32,740
和任何人誰是在我後面我稍後會要求進行排序。

571
00:33:32,740 --> 00:33:34,680
所以現在我們有數字1。

572
00:33:34,680 --> 00:33:39,240
我想，插入他到我的排序列表，所以在這裡，我只是將我的牆上，

573
00:33:39,240 --> 00:33:43,930
現在我要求這個列表進行排序，這個列表是無序的 - 至少據我所知。

574
00:33:43,930 --> 00:33:46,070
一次，我不能看到所有的數字。

575
00:33:46,070 --> 00:33:49,000
>> 現在，我碰巧遇到2號。和他一起，我該怎麼辦？

576
00:33:49,000 --> 00:33:54,380
我你現在插入排序的列表。但是請注意，這是多麼容易。

577
00:33:54,380 --> 00:33:59,650
我只需要看看。 1號是存在的。哦，顯然2進入1號側。

578
00:33:59,650 --> 00:34:03,700
現在我該怎麼做3？我你進入插入排序的列表。但是，這是超級容易。

579
00:34:03,700 --> 00:34:07,250
這是超級容易，這是超級容易，這是超級簡單，超級簡單，超級方便。

580
00:34:07,250 --> 00:34:12,790
進行排序，現在一切都在我的身後，並沒有多少步驟，採取？

581
00:34:12,790 --> 00:34:15,620
[學生]。>>因此，它只有n。我們很幸運。

582
00:34:15,620 --> 00:34:18,860
這是只有n個為什麼？ >> [學生]因為該列表進行排序。

583
00:34:18,860 --> 00:34:21,630
已排序的列表。因此，我們很幸運。

584
00:34:21,630 --> 00:34:25,639
但是，我們設計了一個算法就是這樣的運氣，利用這個時間，

585
00:34:25,639 --> 00:34:29,420
，最好的情況下，不浪費不必要的時間。

586
00:34:29,420 --> 00:34:31,750
所以，我們現在有什麼，我們會打電話給泡各種

587
00:34:31,750 --> 00:34:33,949
人們泡了兩兩種。

588
00:34:33,949 --> 00:34:38,100
我們現在有選擇排序，我們剜出最小的人，一次又一次的。

589
00:34:38,100 --> 00:34:42,350
現在，我們有插入排序，排序的主動放人屬於他們的地方

590
00:34:42,350 --> 00:34:45,000
在一個日益排序列表。

591
00:34:45,000 --> 00:34:49,679
如果我們可以，這些傢伙在這裡的一片掌聲。 [掌聲]

592
00:34:49,679 --> 00:34:52,310
讓我們以我們在這裡休息5分鐘。

593
00:34:52,310 --> 00:34:55,139
當我們回來時，我們會吹出來的水的所有這些算法

594
00:34:55,139 --> 00:35:00,260
更好的東西。好的。非常感謝。您可以保留這些作為紀念品。

595
00:35:01,710 --> 00:35:04,330
好的。我們又回來了。

596
00:35:04,330 --> 00:35:08,420
>> 重溫一下真正的快，我們有3種不同的方法來排序，

597
00:35:08,420 --> 00:35:13,000
這是整點到這一點，如果有人像Alex

598
00:35:13,000 --> 00:35:16,930
可以搜索列表中的數字更快，比別人像肖恩可能。

599
00:35:16,930 --> 00:35:19,830
即使我們有這樣的簡單的例子，8號，

600
00:35:19,830 --> 00:35:24,000
你可以推斷輕鬆地以8個網頁，8億個網頁，

601
00:35:24,000 --> 00:35:26,680
還是800萬Facebook上的好友。

602
00:35:26,680 --> 00:35:30,090
因此，這些算法當然可以擴展到那些種值，

603
00:35:30,090 --> 00:35:32,300
和想法，最終都是一樣的。

604
00:35:32,300 --> 00:35:36,140
因此，冒泡排序是第一次在這裡我們種冒泡最大的人

605
00:35:36,140 --> 00:35:39,110
所有的權利人兩兩交換。

606
00:35:39,110 --> 00:35:42,040
然後，我們有什麼，我們會打電話給選擇排序，我有點刻意地

607
00:35:42,040 --> 00:35:46,480
一直在尋找在列表中，選擇最小的數字，一遍又一遍，並再次，

608
00:35:46,480 --> 00:35:49,530
其中的邏輯結果是，最終的排序條件列表。

609
00:35:49,530 --> 00:35:53,780
然後在第三個問題，我插入到適當的地方的人，

610
00:35:53,780 --> 00:35:57,720
我們做了一個很做作的例子，在已排序的列表，

611
00:35:57,720 --> 00:36:01,100
但發送消息，在插入排序的情況下，

612
00:36:01,100 --> 00:36:02,670
你可以得到幸運。

613
00:36:02,670 --> 00:36:07,930
如果已排序的數字，它只會帶你n個步驟盡可能多的確認，

614
00:36:07,930 --> 00:36:10,870
而選擇排序中，你多一點的隧道視野

615
00:36:10,870 --> 00:36:14,360
和你也沒有意識到已經排序的列表。

616
00:36:14,360 --> 00:36:16,830
因此，讓我們看到冒泡排序在這裡的行動。

617
00:36:16,830 --> 00:36:19,590
在下面的例子中，我們看到豎線

618
00:36:19,590 --> 00:36:23,030
其高度的號碼，以便我們可以排序的可視化排序發生。

619
00:36:23,030 --> 00:36:26,630
酒吧，較小的數字越小;酒吧越大，數字越大。

620
00:36:26,630 --> 00:36:28,860
>> 我們將發揮它在此默認速度。

621
00:36:28,860 --> 00:36:33,460
這將現在移動快了一點，但紅色是什麼2條

622
00:36:33,460 --> 00:36:35,480
並排比較。

623
00:36:35,480 --> 00:36:39,520
如果你仔細觀察，會發生什麼情況是，如果酒吧秩序，

624
00:36:39,520 --> 00:36:42,300
中較小的一個被移動到左側，右側的大的一個，

625
00:36:42,300 --> 00:36:44,360
然後你繼續前進。

626
00:36:44,360 --> 00:36:48,520
因此，如果我們這樣做了一遍又一遍，注意到最小的酒吧

627
00:36:48,520 --> 00:36:51,090
要保持緩慢的左

628
00:36:51,090 --> 00:36:54,130
最大的酒吧，要保持緩慢方式的權利。

629
00:36:54,130 --> 00:36:58,490
事實上，我們已經開始看到一個模式的右手邊一路

630
00:36:58,490 --> 00:37:04,790
就像我們看到8和7最終冒泡到盡頭，我們的人的名單。

631
00:37:04,790 --> 00:37:08,750
所以，這是怎麼回事能很快地得到一個有點乏味，所以讓我停止了一會兒。

632
00:37:08,750 --> 00:37:10,980
讓我改變的速度要快得多。

633
00:37:10,980 --> 00:37:15,380
我不會改變的算法，我只是讓，動畫得更快。

634
00:37:15,380 --> 00:37:18,410
冒泡排序，相同的算法，

635
00:37:18,410 --> 00:37:21,910
但現在你可以看到速度遠遠超過我們的口頭示範

636
00:37:21,910 --> 00:37:25,900
最大的元素確實冒出來的頂部。

637
00:37:25,900 --> 00:37:29,860
>> 順便說一句，這些小方塊在左下角和右下角

638
00:37:29,860 --> 00:37:33,520
只是為你做多少次比較小提醒。

639
00:37:33,520 --> 00:37:37,620
但就目前而言，我們可以將精力集中在金字塔的形狀，就這樣吧。

640
00:37:37,620 --> 00:37:41,510
最小的元素是在左邊，在右邊的最大，並在兩者之間的一切。

641
00:37:41,510 --> 00:37:44,470
現在讓我們來看看選擇排序，而不是採取。

642
00:37:44,470 --> 00:37:47,260
我要繼續前進，點擊停止。我們將得到一個新的隨機的酒吧。

643
00:37:47,260 --> 00:37:50,930
選擇排序，回想一下，在列表中再，再而三，

644
00:37:50,930 --> 00:37:54,900
採摘最小的元素。因此，這裡的選擇排序。

645
00:37:54,900 --> 00:37:58,390
它看起來像有較少的工作，現在發生的，因為我們還沒有比較成對

646
00:37:58,390 --> 00:38:02,590
但我們只是櫻桃採摘最小的元素由右至左排序。

647
00:38:02,590 --> 00:38:06,890
這花了很短的時間，因此已經有一個二分法。

648
00:38:06,890 --> 00:38:11,820
僅僅因為一個算法取n的平方時間，如冒泡排序

649
00:38:11,820 --> 00:38:16,100
如選擇排序，這些都是真正的最壞情況下的運行時間。

650
00:38:16,100 --> 00:38:21,790
例如，在的情況下，讓我們說，選擇排序，

651
00:38:21,790 --> 00:38:27,240
其實，我選擇最小的人，並把他或她在這裡，

652
00:38:27,240 --> 00:38:29,620
然後我做了一遍，然後我做了一遍，

653
00:38:29,620 --> 00:38:32,070
但有輕微的優化，我可以做的。

654
00:38:32,070 --> 00:38:35,040
>> 當我在這種情況下，移動數字1  - 薩米 - 

655
00:38:35,040 --> 00:38:38,630
什麼，我需要做的，他此後嗎？ >> [學生]離開他。

656
00:38:38,630 --> 00:38:40,140
離開他，對不對？什麼也沒有。

657
00:38:40,140 --> 00:38:44,310
我並不需要再次薩米交談過，因為如果我選擇了最小的元素

658
00:38:44,310 --> 00:38:48,580
在這裡，把他，為什麼要浪費時間去年底我的整個列表？

659
00:38:48,580 --> 00:38:54,590
在接下來的迭代，讓我實際上只移動到2號，3號。

660
00:38:54,590 --> 00:38:57,640
因此，在現實中，我沒有做N Things的n倍。

661
00:38:57,640 --> 00:39:05,380
我是做N Things的，然後再有n  -  1的東西，那麼n  - 兩件事情，那麼n  -  3樣東西，

662
00:39:05,380 --> 00:39:07,080
那麼n  -  4，點，點，點。

663
00:39:07,080 --> 00:39:09,470
我們有一個幾何級數位，這意味著

664
00:39:09,470 --> 00:39:11,450
你逐漸變小的數字相加。

665
00:39:11,450 --> 00:39:17,940
不是N + N + N + N，但N + 7 + 6 + 5 + 4 + 3 + 2 + 1。

666
00:39:17,940 --> 00:39:21,380
有什麼工作是 - 

667
00:39:21,380 --> 00:39:24,280
我要搞砸了我的板只是一個瞬間 - 

668
00:39:24,280 --> 00:39:28,990
的去上班了的東西，如N（N  -  1）/ 2

669
00:39:28,990 --> 00:39:31,930
如果我們只是看看後面的一本數學書，你把所有的作弊表，

670
00:39:31,930 --> 00:39:33,410
的公式。

671
00:39:33,410 --> 00:39:37,760
如果你只是增加一些N + N  -  1 + N  -  2，它的工作原理是這樣的。

672
00:39:37,760 --> 00:39:42,320
如果我們只是種繁殖了這一點，該公司的N平方減去n / 2。

673
00:39:42,320 --> 00:39:46,400
我一直說Ň平方，雖然，那是因為我是一種精神的快捷方式

674
00:39:46,400 --> 00:39:51,950
因為在現實中，N的平方減去n除以2，的確是真正的步數

675
00:39:51,950 --> 00:39:55,510
選擇排序算法，像如果我們真的計算

676
00:39:55,510 --> 00:39:58,800
所有這些比較，所有的小繁忙的工作中，我們正在做。

677
00:39:58,800 --> 00:40:03,210
但坦率地說，當n變得像一百萬或一個億，到底誰在乎

678
00:40:03,210 --> 00:40:07,160
如果你正在做一個億平方減一億美元，除以2？

679
00:40:07,160 --> 00:40:09,320
有十億平方是​​一個龐大的數字。

680
00:40:09,320 --> 00:40:13,580
你可以把另一個十億它關閉 -  N。這不是什麼大不了的。

681
00:40:13,580 --> 00:40:18,770
因此，更大的數字，不太重要的低有序的條件。

682
00:40:18,770 --> 00:40:24,230
誰在乎你，如果你在談論的十五次冪的步數除以2？

683
00:40:24,230 --> 00:40:29,710
>> 因此，在一般情況下，計算機科學家傾向於扔掉一切，但最大的一屆，

684
00:40:29,710 --> 00:40:33,140
我們只是種簡化了世界，並說該算法

685
00:40:33,140 --> 00:40:38,130
花了大約ñ平方的步驟。這是一個算法的運行時間。

686
00:40:38,130 --> 00:40:40,760
所以，我們會回來，這只是一瞬間的一些具體的例子，

687
00:40:40,760 --> 00:40:45,940
但現在，這樣的直觀的動機只是簡化了我們的世界背後

688
00:40:45,940 --> 00:40:51,170
和談論的最重要的條件，而不是進入所有這些花哨的公式。

689
00:40:51,170 --> 00:40:53,540
因此，選擇排序，和我們有點幸運了。

690
00:40:53,540 --> 00:40:57,360
讓我們來看看在插入排序。讓我繼續前進，開始這個。

691
00:40:57,360 --> 00:41:00,330
現在的模式發生的事情是，有一點不同，

692
00:41:00,330 --> 00:41:03,410
我們開始用隨機數，

693
00:41:03,410 --> 00:41:06,890
但是如果我們實際上在最壞的情況下，向上計數的步數

694
00:41:06,890 --> 00:41:11,070
如果該列表以正確的順序，全面啟動

695
00:41:11,070 --> 00:41:13,380
我們將只需要n個步驟，盡可能多的實現。

696
00:41:13,380 --> 00:41:18,240
>> 但是，如果該列表實際上是向後 - 例如，這裡在這種情況下 - 

697
00:41:18,240 --> 00:41:23,860
然後發現，其實我們要在這種情況下，做了很多的工作。

698
00:41:23,860 --> 00:41:27,080
它應該那種感覺，你喜歡這個人是種更努力地工作

699
00:41:27,080 --> 00:41:30,900
讓那些更小的元素的左側，這是因為我們有不吉利的。

700
00:41:30,900 --> 00:41:34,210
意外的反向排序的列表。

701
00:41:34,210 --> 00:41:38,110
與此相反，插入排序，如果我們模仿我們所做的與我們人類在這裡

702
00:41:38,110 --> 00:41:42,670
開始大家一起排序，然後再啟動，這是一個相當不錯的算法，對不對？

703
00:41:42,670 --> 00:41:45,010
，事實上，它已經排序。

704
00:41:45,010 --> 00:41:48,670
因此，讓我們嘗試總結到底有多少時間，這些東西都是我們

705
00:41:48,670 --> 00:41:52,360
通過引入只是有點術語或符號，這實際上是更簡單

706
00:41:52,360 --> 00:41:54,320
比花哨的建議。

707
00:41:54,320 --> 00:41:59,030
這件事在這裡，大O在屏幕上，是一個計算機科學家通常會使用

708
00:41:59,030 --> 00:42:03,640
來描述的算法的最壞的情況下的運行時間。

709
00:42:03,640 --> 00:42:07,360
>> 同樣，最壞的情況下，這是完全依賴於上下文的。

710
00:42:07,360 --> 00:42:10,890
我們所說的最壞的情況完全變化的基礎上的，我們正在談論的問題。

711
00:42:10,890 --> 00:42:14,550
但在排序的情況下，可能出現的最壞的情況嗎？

712
00:42:14,550 --> 00:42:17,860
是倒退，因為它只是感覺一樣，這意味著大量的工作，為我們的一切。

713
00:42:17,860 --> 00:42:21,330
我已經記下了幾個到目前為止，我們已經看到的算法：

714
00:42:21,330 --> 00:42:24,930
線性搜索，二進制搜索，如電話簿或紙片，

715
00:42:24,930 --> 00:42:28,960
然後像冒泡排序，選擇排序，插入排序，我們看到了我們人類，

716
00:42:28,960 --> 00:42:31,770
，然後，最終將被稱為歸併排序。

717
00:42:31,770 --> 00:42:37,710
因此，在最壞情況下的線性搜索，多少步它採取尋找數字7

718
00:42:37,710 --> 00:42:40,690
如果有n門像肖恩面嗎？ >> [學生]。

719
00:42:40,690 --> 00:42:44,180
N.所以我們要編寫大O的n。

720
00:42:44,180 --> 00:42:47,010
我只是要填補一些空白。這僅僅是一格的空白。

721
00:42:47,010 --> 00:42:52,990
但在最好的情況下，線性搜索，7可能會在一開始的列表，

722
00:42:52,990 --> 00:42:55,520
和肖恩可能已經開始尋找在開始的列表。

723
00:42:55,520 --> 00:42:58,940
所以，如果你正在使用的線性搜索和檢查左到右，或可能是從右到左 - 

724
00:42:58,940 --> 00:43:02,650
它們是等價的 - 在最好的情況下，多少步線性搜索，

725
00:43:02,650 --> 00:43:05,550
像肖恩的算法？只有1步。

726
00:43:05,550 --> 00:43:09,450
>> 所以我說這是歐米茄符號。

727
00:43:09,450 --> 00:43:11,570
這是只是資本歐米茄。

728
00:43:11,570 --> 00:43:15,000
歐米茄只是說最好的情況下運行時間的性感方式。

729
00:43:15,000 --> 00:43:18,900
因此，在最好的情況下的運行時間是一個單一的步驟或步驟的恆定數目的 - 

730
00:43:18,900 --> 00:43:24,270
在這種情況下 - 但在最壞的情況下，大O，它實際上是n個步驟。

731
00:43:24,270 --> 00:43:28,110
這一個在這裡，θ，我們其實並沒有去看看現在。

732
00:43:28,110 --> 00:43:30,090
這個特殊的例子是不相關的。

733
00:43:30,090 --> 00:43:31,990
但現在讓我們嘗試二進制搜索。

734
00:43:31,990 --> 00:43:35,990
用二進制搜索在最壞的情況下，多少步要採取尋找數字7

735
00:43:35,990 --> 00:43:38,340
或任何我們所想要的？ >> [學生]登錄N。

736
00:43:38,340 --> 00:43:40,980
仍然要採取日誌n，因為就像亞歷克斯把倒霉的

737
00:43:40,980 --> 00:43:44,030
當我們真正的工作有條不紊問題

738
00:43:44,030 --> 00:43:48,220
和她沒有發現，直到最後的門，她看著7號，

739
00:43:48,220 --> 00:43:51,720
儘管，在公平，她扔掉了一定的門前進的道路上，

740
00:43:51,720 --> 00:43:56,920
在最壞情況下的二進制搜索日誌n的運行時間。

741
00:43:56,920 --> 00:43:59,230
再次，這充分說明這個劃分和征服。

742
00:43:59,230 --> 00:44:01,140
但是，在最好的情況下，又如何呢？

743
00:44:01,140 --> 00:44:04,790
和亞歷克斯親身經歷，最好的情況下，當她來到了舞台上。

744
00:44:04,790 --> 00:44:07,290
多少步驟，在二進制搜索？ >> [學生] 1。

745
00:44:07,290 --> 00:44:09,380
1，只因為她是幸運的。

746
00:44:09,380 --> 00:44:12,520
但是，這很好，因為歐米茄是最好的情況，

747
00:44:12,520 --> 00:44:15,770
最好的情況下輸入，即使它只是隨機的好運氣。

748
00:44:15,770 --> 00:44:18,900
>> 現在，我們也要去到只是休假空白的種，現在。

749
00:44:18,900 --> 00:44:21,010
現在怎麼樣冒泡排序？

750
00:44:21,010 --> 00:44:24,290
冒泡排序在最壞的情況下，每個人都在以相反的順序，

751
00:44:24,290 --> 00:44:26,380
因此，我們做了很多的氣泡。

752
00:44:26,380 --> 00:44:30,190
但究竟有多少步驟，要在最壞的情況嗎？ >> [學生] N的平方。

753
00:44:30,190 --> 00:44:32,550
這是n個平方，因為如果你仔細想想，

754
00:44:32,550 --> 00:44:36,410
如果該列表是完全向後 -  8是在這裡，就在這裡 - 

755
00:44:36,410 --> 00:44:40,530
事情開始泡沫，8號移動方式，這種方式，

756
00:44:40,530 --> 00:44:44,540
這種方式，這種方式，但如果是7號，在最壞的情況嗎？

757
00:44:44,540 --> 00:44:47,720
在這裡，她仍然在那裡。所以，我們做了一遍又一遍。

758
00:44:47,720 --> 00:44:53,190
這就是我們得到n個步驟，然後再有n  -  1步，然後再有n  -  2個步驟。

759
00:44:53,190 --> 00:44:55,960
如果你把我的話 - 如果你種繁殖出來，

760
00:44:55,960 --> 00:45:00,110
它的大致Ň平方一些其他條款，我們將不理會現在的中端 - 

761
00:45:00,110 --> 00:45:06,890
然後在最壞的情況下，冒泡排序為n的平方，給予或採取。

762
00:45:06,890 --> 00:45:09,490
但最好的情況下，冒泡排序呢？

763
00:45:09,490 --> 00:45:13,050
最好的情況是什麼？所有的數字進行排序了。

764
00:45:13,050 --> 00:45:15,920
是什麼啟發我所用，我用的伎倆，

765
00:45:15,920 --> 00:45:20,110
意識到，我已沒有工作，因此提前停止嗎？

766
00:45:20,110 --> 00:45:23,590
[學生]檢查一次。 >>檢查一次。但什麼是我做沿途嗎？

767
00:45:23,590 --> 00:45:26,130
我跟踪我做了多少掉期。

768
00:45:26,130 --> 00:45:30,650
我意識到，如果我沒有任何掉期計算我的手指，然後我做了沒有工作。

769
00:45:30,650 --> 00:45:34,300
我當然不應該再嘗試做任何工作，這樣我就可以停止。

770
00:45:34,300 --> 00:45:37,830
>> 因此，在最好的情況下，冒泡排序的列表時，已排序，

771
00:45:37,830 --> 00:45:41,530
你會說什麼的歐米伽符號，最好的情況下運行時間？

772
00:45:41,530 --> 00:45:48,040
這只是N。我們做了一些工作，但我們只需要做1漫步的價值，工作。

773
00:45:48,040 --> 00:45:50,490
在這裡，我要離開這部分空白。

774
00:45:50,490 --> 00:45:52,430
和現在選擇排序。

775
00:45:52,430 --> 00:45:56,010
選擇排序我拔最小的人一遍又一遍。

776
00:45:56,010 --> 00:45:58,380
的運行時間，這是我們說什麼？

777
00:45:58,380 --> 00:46:00,590
這在最壞的情況下為n的平方。

778
00:46:00,590 --> 00:46:05,220
不幸的是，在最好的情況下，它也是n平方

779
00:46:05,220 --> 00:46:08,840
因為我不擁有那種無所不知的觀點對整個世界;

780
00:46:08,840 --> 00:46:13,140
我只知道，我確實發現了一個完整的迭代最小的人。

781
00:46:13,140 --> 00:46:15,860
因此，選擇排序種吸在這個意義上，

782
00:46:15,860 --> 00:46:17,920
但好處是它的一種直觀。

783
00:46:17,920 --> 00:46:21,470
這是很容易的代碼，因為所有你必須做的是寫一對夫婦的嵌套循環，

784
00:46:21,470 --> 00:46:24,620
通常情況下，通過尋找最小的元素

785
00:46:24,620 --> 00:46:27,840
然後把在列表末尾在它所屬的最小元素。

786
00:46:27,840 --> 00:46:29,900
因此，這裡也有將是一個權衡。

787
00:46:29,900 --> 00:46:34,440
它需要你去思考，去開發的東西，通過編寫代碼的時間量

788
00:46:34,440 --> 00:46:39,460
很可能需要更多的時間，如果你想有一個更好的算法和更快的性能。

789
00:46:39,460 --> 00:46:41,780
>> 但是，如果你真的只是種代碼的東西了快速和骯髒的

790
00:46:41,780 --> 00:46:45,000
只是一種最愚蠢的想法，你能想到的，

791
00:46:45,000 --> 00:46:47,580
可能你幾分鐘的代碼，但與大型數據集

792
00:46:47,580 --> 00:46:49,580
你的算法可能需要幾個小時才能運行。

793
00:46:49,580 --> 00:46:51,690
甚至我在讀研究生，有時會這些權衡。

794
00:46:51,690 --> 00:46:55,660
這將是凌晨3點，我嘗試分析一些非常大的數據集

795
00:46:55,660 --> 00:46:59,650
我是這樣做的安全性研究，這是不是花5分鐘

796
00:46:59,650 --> 00:47:03,210
調整我的程序的數據進行分析，並去睡覺

797
00:47:03,210 --> 00:47:08,420
或花8個小時，得到它恰到好處，所以它運行的瞬間，而不是去睡覺。

798
00:47:08,420 --> 00:47:10,530
因此，也有它是一種有意識的決定。

799
00:47:10,530 --> 00:47:12,740
開發時間少，更多的睡眠。

800
00:47:12,740 --> 00:47:14,780
回想起來，我可能不應該鼓勵

801
00:47:14,780 --> 00:47:19,120
當這裡的目標是優化的代碼質量，

802
00:47:19,120 --> 00:47:21,280
但同樣在現實世界中是一個非常合理的折衷。

803
00:47:21,280 --> 00:47:25,130
更少的時間，更少的性能，反之亦然。

804
00:47:25,130 --> 00:47:28,110
所以，在這裡，我們終於有機會談論THETA。

805
00:47:28,110 --> 00:47:32,830
θ符號是計算機科學家們可以在談話中帶來

806
00:47:32,830 --> 00:47:36,160
大O和歐米茄發生是相同的。

807
00:47:36,160 --> 00:47:40,160
你說THETA真正地發送消息，這是一種緊張的約束。

808
00:47:40,160 --> 00:47:43,340
無論情況是好還是壞，它的N的平方。

809
00:47:43,340 --> 00:47:46,510
因此，它是不相關的故事在這裡。

810
00:47:46,510 --> 00:47:48,560
插入排序是最後一次，我們看到了，

811
00:47:48,560 --> 00:47:50,830
我只是將每個人放到合適的地方。

812
00:47:50,830 --> 00:47:54,930
在最好的情況是插入排序的運行時間，因為我們在這裡看到了嗎？

813
00:47:54,930 --> 00:47:57,250
[學生]：最好的情況是什麼？ >>最好的情況。

814
00:47:57,250 --> 00:48:00,100
>> N，因為在最好的情況下，每個人排序，

815
00:48:00,100 --> 00:48:02,580
和薩米並沒有其他人真的有移動。

816
00:48:02,580 --> 00:48:04,610
他們已經在他們的正確的地方。

817
00:48:04,610 --> 00:48:08,570
所以插入排序在最好的情況是，在這種情況下，正。

818
00:48:08,570 --> 00:48:12,770
但是，在最壞的情況下，它是一種n個平方。為什麼呢？

819
00:48:12,770 --> 00:48:16,230
如果我名單上的人是相反的順序，

820
00:48:16,230 --> 00:48:21,260
我第一次從8號開始，我將他或她進入正確的位置，這是在這裡。

821
00:48:21,260 --> 00:48:25,270
我種移動到側邊。這些傢伙是無序的，他或她進行排序。

822
00:48:25,270 --> 00:48:28,970
但現在，我偶然發現誰後呢？ >> [學生] 7。

823
00:48:28,970 --> 00:48:31,250
7在最壞的情況下，因為它是在相反的順序。

824
00:48:31,250 --> 00:48:34,920
>> 因此，這裡是7。 7屬於哪裡？肯定在我身後。

825
00:48:34,920 --> 00:48:39,460
但現在7實際上不屬於我，但緊隨其後的8號後面，

826
00:48:39,460 --> 00:48:41,880
所以我說，“對不起，8號，可以請你移動這樣

827
00:48:41,880 --> 00:48:44,640
“7，以騰出空間嗎？”現在我遇到6。

828
00:48:44,640 --> 00:48:48,530
“哦，對不起，8號和7號，你可以移動，以騰出空間為6？”

829
00:48:48,530 --> 00:48:52,360
所以，換句話說，插入排序，即使我沒有做太多的運動，

830
00:48:52,360 --> 00:48:56,330
我後面的人做更多的工作，而這得到了，以耗資有人時間。

831
00:48:56,330 --> 00:48:58,000
它要花費計算機的時間。

832
00:48:58,000 --> 00:49:01,450
因此，在插入排序的情況下，我們仍然深受其害。

833
00:49:01,450 --> 00:49:06,260
如果你開始添加的總步數，我們最終打大致Ň平方

834
00:49:06,260 --> 00:49:11,160
因為這些傢伙需要的人要插入到該列表中，以騰出空間。

835
00:49:11,160 --> 00:49:15,960
因此，在這種情況下，Theta是不是適用於特別在手的故事。

836
00:49:15,960 --> 00:49:21,100
這是所有好和好。我們有這3種不同的方式談論的運行時間。

837
00:49:21,100 --> 00:49:26,370
但是，什麼這實際上意味著在實質，如果我們真正嘗試編寫一個算法？

838
00:49:26,370 --> 00:49:31,620
>> 最後，我提議，有一個更好的算法有

839
00:49:31,620 --> 00:49:33,740
本身具有一定的取捨。

840
00:49:33,740 --> 00:49:36,890
我們把它稱為歸併排序，它是這片神奇的算法排序

841
00:49:36,890 --> 00:49:42,840
工作快弄好了，它是如此容易表達，至少在偽代碼。

842
00:49:42,840 --> 00:49:46,900
該算法的合併排序的實施將是如下。

843
00:49:46,900 --> 00:49:50,860
當你給定的n個元素 -  n個數，n個人，不管是誰 - 第一次有一個完整性檢查。

844
00:49:50,860 --> 00:49:56,340
如果n小於2，歸併排序只是停止。它返回時，這麼說。

845
00:49:56,340 --> 00:50:00,830
為什麼你會停止，如果n是小於2？ >> [聽不見的學生反應]

846
00:50:00,830 --> 00:50:04,480
右。並再次，n不為在列表中的數目，n是列表的大小。

847
00:50:04,480 --> 00:50:07,660
如果n小於2，這意味著你的名單是1，

848
00:50:07,660 --> 00:50:09,640
你很明顯排序的，如果是1號，

849
00:50:09,640 --> 00:50:11,710
或0，在這種情況下，沒有什麼排序，

850
00:50:11,710 --> 00:50:13,570
因此，我們需要這種形式的基本情況。

851
00:50:13,570 --> 00:50:20,350
如果該列表是如此之短，只是沒有做，確實沒有做任何事情。返回。

852
00:50:20,350 --> 00:50:25,090
否則的左一半的元素進行排序，然後排序的右半​​部分的元素，

853
00:50:25,090 --> 00:50:27,410
然後合併排序半。

854
00:50:27,410 --> 00:50:32,130
>> 這種看起來像一個小騙子，我問你如何排序的元素

855
00:50:32,130 --> 00:50:34,900
你告訴我“的左半部分進行排序，排序的右半​​邊。”

856
00:50:34,900 --> 00:50:37,240
我想，“好吧，你怎麼排序的左半邊嗎？”

857
00:50:37,240 --> 00:50:40,670
“排序的左一半的左半邊，排序的左半邊的右半部分，然後完成。”

858
00:50:40,670 --> 00:50:44,060
你是週期性的定義是什麼意思排序，

859
00:50:44,060 --> 00:50:46,790
但事實證明，在這種情況下，這實際上是輝煌的。

860
00:50:46,790 --> 00:50:50,230
這不是真正的這種惡性循環永遠不會結束

861
00:50:50,230 --> 00:50:52,550
因為它結束的時候嗎？ >> [學生]當你達到10件事。

862
00:50:52,550 --> 00:50:54,220
當你達到10件事。

863
00:50:54,220 --> 00:50:57,850
因此，即使你可能會開始有8人，和我說，這些人“之類的左半邊，

864
00:50:57,850 --> 00:51:00,480
這4人，“然後我說，”怎麼你的左半邊排序嗎？“

865
00:51:00,480 --> 00:51:03,450
“好了，在這裡的2人進行排序。”然後你會說，“好吧，好吧。”

866
00:51:03,450 --> 00:51:05,520
“你是怎麼排序的左半邊這些人嗎？”

867
00:51:05,520 --> 00:51:09,040
“只是有點這個人在這裡。”現在的輝煌啟示什麼？

868
00:51:09,040 --> 00:51:13,050
我有，排序1人。完成。我沒有做任何工作。

869
00:51:13,050 --> 00:51:16,580
但現在我要解決的這個人，但他們是一個人，沒有任何關係。

870
00:51:16,580 --> 00:51:21,490
>> 因此，魔術顯然是在這第三步：合併排序的一半。

871
00:51:21,490 --> 00:51:25,770
所以，歸併排序這輝煌的洞察力，如果你打破一個大問題分解

872
00:51:25,770 --> 00:51:28,650
2個較小的，相同大小的問題

873
00:51:28,650 --> 00:51:32,710
，然後就種膠更小的解決方案結合在一起結束時，

874
00:51:32,710 --> 00:51:34,720
我建議，我們可以做的更好的[點擊音]

875
00:51:34,720 --> 00:51:38,050
選擇排序或插入排序。

876
00:51:38,050 --> 00:51:40,690
其實我已經忽略了半小時，但我真的不知道這是怎麼回事

877
00:51:40,690 --> 00:51:45,040
今天外面。 [呼呼的聲音] [笑]

878
00:51:45,040 --> 00:51:49,660
因此，讓我們看看我們可以看到這一點幫助我們的朋友羅布·鮑登。

879
00:51:49,660 --> 00:51:52,810
歸併排序的過程中，有2個大的步驟。

880
00:51:52,810 --> 00:51:56,400
首先，連續分裂列表杯分為兩半

881
00:51:56,400 --> 00:51:59,610
直到我們有一堆名單，他們只用1杯。

882
00:51:59,610 --> 00:52:02,150
不要擔心，如果列表中包含一個奇數

883
00:52:02,150 --> 00:52:04,830
你不能讓他們之間的一個完全乾淨的切割。

884
00:52:04,830 --> 00:52:08,740
只需隨便挑哪一個清單，包括額外的杯子中。

885
00:52:08,740 --> 00:52:11,320
因此，讓我們這些列表拆分。

886
00:52:12,420 --> 00:52:14,570
現在，我們有2個列表。

887
00:52:18,930 --> 00:52:20,930
現在，我們有4個列表。

888
00:52:25,730 --> 00:52:28,740
現在我們有8個列表，每個列表中的單杯。

889
00:52:28,740 --> 00:52:31,520
所以這是它的第1步。

890
00:52:31,520 --> 00:52:37,280
對於第2步，我們多次合併對使用合併算法，我們以前學過的列表。

891
00:52:37,280 --> 00:52:44,320
合併108和15，我們結束了15日，108。

892
00:52:45,240 --> 00:52:51,330
，合併50和4，我們最終有4個，50。

893
00:52:51,330 --> 00:52:56,950
，合併8和42，我們有8個，42。

894
00:52:57,790 --> 00:53:04,360
合併23和16，我們最終有16個，23。

895
00:53:04,360 --> 00:53:08,030
現在我們的列表大小為2。

896
00:53:08,030 --> 00:53:10,980
請注意，每個的4列出的是排序條件，

897
00:53:10,980 --> 00:53:14,230
這樣，我們就可以開始再次對列表合併。

898
00:53:14,230 --> 00:53:22,150
合併15和108以及4和50，我們先來的4個，然後15，

899
00:53:22,150 --> 00:53:26,250
然後是50，那麼108。

900
00:53:26,250 --> 00:53:33,020
合併8，42，16，23，我們先來8，那麼16，

901
00:53:33,020 --> 00:53:37,170
然後是23次，然後在42。

902
00:53:37,170 --> 00:53:42,490
所以現在我們有2列出了大小為4，每一個排序。

903
00:53:42,490 --> 00:53:45,940
所以，現在我們合併這兩個列表。

904
00:53:45,940 --> 00:53:54,230
首先，我們乘4，然後我們乘坐8，然後乘坐15

905
00:53:54,230 --> 00:54:05,280
和16和23和42和50和108。

906
00:54:05,280 --> 00:54:09,020
我們就大功告成了。我們現在有一個排序的列表。

907
00:54:09,020 --> 00:54:13,740
>> 羅布樣的東西，我們尚未利用。

908
00:54:13,740 --> 00:54:16,540
有人建議，但我們並沒有真正做到這一點。

909
00:54:16,540 --> 00:54:19,230
他是做一些身體上的杯子，建議

910
00:54:19,230 --> 00:54:23,680
他花了一些資源，除了時間。 >> [學生]空間。 >>空間。

911
00:54:23,680 --> 00:54:27,360
事實上，他有這種雙向電平表空間，在那裡，他在這裡

912
00:54:27,360 --> 00:54:31,960
和下行空間在這裡實際上是暗示，他用兩倍的空間

913
00:54:31,960 --> 00:54:36,390
因此，我們的算法 - 插入排序，冒泡排序，選擇排序 - 

914
00:54:36,390 --> 00:54:40,780
但他卻利用這一額外的空間來搬東西來回種

915
00:54:40,780 --> 00:54:42,600
而為了讓事情。

916
00:54:42,600 --> 00:54:47,540
即使感覺就像我們到了一個排序的列表，感覺就像過了好一會兒。

917
00:54:47,540 --> 00:54:51,060
在現實中，羅布做什麼的就是這樣一個算法。

918
00:54:51,060 --> 00:54:56,780
他首先把大小為n的問題，把它分成的左半和右半。

919
00:54:56,780 --> 00:54:59,380
這時候，他感動的杯子。然後，他重複了這一過程。

920
00:54:59,380 --> 00:55:03,390
他在這裡和在這裡的2台2分4。

921
00:55:03,390 --> 00:55:08,520
然後，他重複了這一過程，這些不同的杯子2套1分2。

922
00:55:08,520 --> 00:55:11,000
而這正是輝煌的機會出現。

923
00:55:11,000 --> 00:55:15,840
羅伯的故事在這一點上，有8個大小為1的列表，

924
00:55:15,840 --> 00:55:18,860
所有這一切都已經進行排序。

925
00:55:18,860 --> 00:55:20,630
>> 那麼，他怎麼繼續做？

926
00:55:20,630 --> 00:55:25,260
成對他把這個排序的列表，這個排序的列表和它們合併。

927
00:55:25,260 --> 00:55:28,200
然後，他把這個和合併他們，那麼這個人，合併他們，

928
00:55:28,200 --> 00:55:30,670
那麼這個合併。

929
00:55:30,670 --> 00:55:32,390
然後他做了什麼呢？

930
00:55:32,390 --> 00:55:36,580
然後，他重新合併的大的列表，然後再重新合併的大列表。

931
00:55:36,580 --> 00:55:41,170
如果你認為這只是直觀的，現在，什麼是他真正在做什麼？

932
00:55:41,170 --> 00:55:45,450
他一半除以問題，在一半，在一半，在一半

933
00:55:45,450 --> 00:55:47,600
為了得到這些超小的列表。

934
00:55:47,600 --> 00:55:51,290
他是那種相結合的一倍，兩倍，一倍，兩倍。

935
00:55:51,290 --> 00:55:54,120
所以，他在做什麼的兩倍多的工作，到目前為止，我們已經看到的

936
00:55:54,120 --> 00:55:56,930
與任何涉及分而治之，但沒什麼大不了的。

937
00:55:56,930 --> 00:55:59,630
雙倍的工作是沒有什麼大不了的。這只是一個常數因子。

938
00:55:59,630 --> 00:56:03,920
就像我們算術表達式之前，我只是要過的常數因子

939
00:56:03,920 --> 00:56:10,170
如2次。誰在乎呢？如果它是20億倍，這仍然有很多步驟。

940
00:56:10,170 --> 00:56:13,160
所以此合併似乎是關鍵的洞察力。

941
00:56:13,160 --> 00:56:17,000
讓我們通過這只是數字前 - 噢，那是不是要繼續還。

942
00:56:17,000 --> 00:56:22,890
讓我們通過這個數字只是實際看到了。

943
00:56:22,890 --> 00:56:25,940
這主要是一點點可憐的人的動畫。

944
00:56:25,940 --> 00:56:27,750
我們的建議。

945
00:56:27,750 --> 00:56:31,480
合併排序的運行時間 - 我們只需要在談論這個問題的一種方式。

946
00:56:31,480 --> 00:56:34,380
這不是數學，這僅僅是一個簡潔的方式表達自己種。

947
00:56:34,380 --> 00:56:39,080
因此，T代表時間，n代表什麼？ >> [學生]的大小 - 

948
00:56:39,080 --> 00:56:41,400
>> [馬蘭]的問題，大小的人數。

949
00:56:41,400 --> 00:56:45,470
因此，我要求的運行時間排序n的人將是0的時間量

950
00:56:45,470 --> 00:56:50,290
如果n小於2，因為如果你1杯或沒有杯子，你有什麼排序。

951
00:56:50,290 --> 00:56:55,160
但更普遍的是，我要提出的運行時間進行排序n個元素

952
00:56:55,160 --> 00:56:59,350
將是所花費的時間，以排序的左半加右半

953
00:56:59,350 --> 00:57:03,110
加 - 這是什麼額外+ N？ >> [學生]歸併排序。

954
00:57:03,110 --> 00:57:07,260
[馬蘭它實際上是合併，因為如果你有N / 2個元素

955
00:57:07,260 --> 00:57:11,500
你這裡有n / 2個元素，多少時間需要將它們合併？

956
00:57:11,500 --> 00:57:15,050
就像羅布，你必須在這裡採摘這一個，也許採摘在這裡，

957
00:57:15,050 --> 00:57:17,120
在這裡採摘，採摘在這裡，在這裡採摘。

958
00:57:17,120 --> 00:57:19,400
您擁有一次觸摸的杯子。

959
00:57:19,400 --> 00:57:22,030
如果有4杯加4杯，8杯

960
00:57:22,030 --> 00:57:25,200
或者，更普遍的是，8正杯。

961
00:57:25,200 --> 00:57:28,470
因此，合併步驟中，我們可以表達為n，

962
00:57:28,470 --> 00:57:31,330
並且，從字面上涉及的次數羅布物理觸摸

963
00:57:31,330 --> 00:57:33,410
這些保麗龍杯。

964
00:57:33,410 --> 00:57:35,850
現在讓我們做一個任意的例子。

965
00:57:35,850 --> 00:57:41,850
如果有16杯，運行時間排序，Rob的算法，16杯嗎？

966
00:57:41,850 --> 00:57:44,710
它的2倍量的所花費的時間排序8杯

967
00:57:44,710 --> 00:57:46,920
因為在這裡，我們有8杯8杯。

968
00:57:46,920 --> 00:57:51,520
我不知道需要多久，所以我們概括為T的時刻。

969
00:57:51,520 --> 00:57:53,320
誰知道它是什麼呢？

970
00:57:53,320 --> 00:57:58,990
但現在我可以按的遞歸或重複問同樣的問題。

971
00:57:58,990 --> 00:58:01,920
需要多少時間排序8杯水嗎？

972
00:58:01,920 --> 00:58:07,030
8杯，我說需要花費的時間進行排序4杯加4杯量，

973
00:58:07,030 --> 00:58:08,880
然後把它們合併在一起。

974
00:58:08,880 --> 00:58:13,080
精細。我們正在進入一個循環了。排序4杯多久？

975
00:58:13,080 --> 00:58:19,150
所花費的時間進行排序4杯2杯加2杯排序，加上合併過程。

976
00:58:19,150 --> 00:58:21,440
精細。排序2杯多久？

977
00:58:21,440 --> 00:58:26,290
2杯的時間量，它需要進行排序1杯加分類，另一杯所花費的時間

978
00:58:26,290 --> 00:58:29,040
加量合併所花費的時間，這僅僅是2。

979
00:58:29,040 --> 00:58:33,340
>> 精細。最後一個問題。排序1杯多久？

980
00:58:33,340 --> 00:58:37,260
這是我們預測的基本情況，我們會稍早觸及的。

981
00:58:37,260 --> 00:58:42,250
事實上，它沒有任何排序的最小的問題

982
00:58:42,250 --> 00:58:44,120
意味著，現在，類的小學風格，

983
00:58:44,120 --> 00:58:46,460
我們可以去堵塞這些數字。互動式

984
00:58:46,460 --> 00:58:50,630
現在，我們知道T的1是什麼，這樣我就可以插入T的1 0。

985
00:58:50,630 --> 00:58:54,420
這將會給我的答案為T 2，然後我可以插在更高了。

986
00:58:54,420 --> 00:58:56,930
這將讓我的T 4，我可以插在更高了。

987
00:58:56,930 --> 00:58:58,920
這將讓我的T 8，我可以插在更高了。

988
00:58:58,920 --> 00:59:04,330
如果我真的做出來的，這些問題的答案堵在數學上，

989
00:59:04,330 --> 00:59:08,590
然後我得到的​​T 16是64。

990
00:59:08,590 --> 00:59:12,090
64代表什麼？

991
00:59:12,090 --> 00:59:15,700
如果T是16，是的，這16次4。

992
00:59:15,700 --> 00:59:20,120
因此，我要求這件事情，現在的運行時間稱為歸併排序 - 

993
00:59:20,120 --> 00:59:22,590
這將是迄今為止，我們已經看到了奇 - 

994
00:59:22,590 --> 00:59:26,160
將被稱為n日誌n

995
00:59:26,160 --> 00:59:31,140
因為可以搶多少次分裂一大堆杯的一半嗎？登錄N。

996
00:59:31,140 --> 00:59:34,370
這是相同的電話簿的例子，這是自計數的例子一樣。

997
00:59:34,370 --> 00:59:36,380
>> 多少次，你分了一半的東西嗎？

998
00:59:36,380 --> 00:59:38,410
然而，有此合併的步驟。

999
00:59:38,410 --> 00:59:42,920
您可能要分杯一而再，再而三成半，

1000
00:59:42,920 --> 00:59:45,640
但每次你要合併。

1001
00:59:45,640 --> 00:59:48,270
我們前面所說的，合併Ň杯需要n個步驟

1002
00:59:48,270 --> 00:59:52,060
因為你必須鼓起了一杯，剜出一個杯子，你必須觸摸每杯一次，

1003
00:59:52,060 --> 00:59:53,510
就像搶一樣。

1004
00:59:53,510 --> 00:59:59,430
因此，如果我們正在做的事情log N次，我們正在做的N Things的這些迭代，

1005
00:59:59,430 --> 01:00:03,090
這些halvings，我們有n次日誌n。

1006
01:00:03,090 --> 01:00:07,220
因此，如果我們插入在16在這個例子中，16次記錄16  - 

1007
01:00:07,220 --> 01:00:10,600
不要擔心，這是為什麼現在的情況，因為我從來沒畫的基礎 - 

1008
01:00:10,600 --> 01:00:16,100
但日誌16基座2是4，16倍，4是64。

1009
01:00:16,100 --> 01:00:22,350
但相反的，如果我們使用冒泡排序，選擇排序或插入排序16號，

1010
01:00:22,350 --> 01:00:26,420
什麼的運行時間，如果n為16？

1011
01:00:26,420 --> 01:00:33,310
這將是16平方，這是256，即使你還沒有完全遵循了所有的數學，

1012
01:00:33,310 --> 01:00:38,390
256是大於64。這真的是神奇的外賣。

1013
01:00:38,390 --> 01:00:41,990
並認識到，通過在較小的例子，你會工作的pset

1014
01:00:41,990 --> 01:00:44,260
使得一切更加直觀。

1015
01:00:44,260 --> 01:00:49,070
但是，什麼是真正的意思的感覺，這種算法是這樣的：

1016
01:00:49,070 --> 01:00:54,520
如果我們看一下這裡的歸併排序 - 讓我在此窗口中拉起來 - 

1017
01:00:54,520 --> 01:00:58,560
這是一個略有不同的例子，我們有所有這些算法 - 

1018
01:00:58,560 --> 01:01:01,440
泡沫，選擇和合併 - 只並排。

1019
01:01:01,440 --> 01:01:03,740
>> 他們都開始用隨機的酒吧，這是很好的。

1020
01:01:03,740 --> 01:01:06,240
沒有人有一個比其他的基本優點。

1021
01:01:06,240 --> 01:01:09,500
我要在瞬間點擊這些動畫 - 開始，開始，開始 - 

1022
01:01:09,500 --> 01:01:13,270
這樣一來，我可以粗略地說，他們都在同一時間開始，

1023
01:01:13,270 --> 01:01:17,450
讓我們來看看，冒泡排序的最壞情況下的運行時間是什麼？ >> [學生] N的平方。

1024
01:01:17,450 --> 01:01:21,560
Ň的平方。選擇排序的最壞情況運行時間是什麼？ Ň的平方。

1025
01:01:21,560 --> 01:01:25,150
和合併排序是很明顯的 - 即使你不太明白，現在所有的數學，

1026
01:01:25,150 --> 01:01:30,610
它會隨著時間的推移變得更加直觀 - 是，我們主張，n次日誌n。

1027
01:01:30,610 --> 01:01:35,210
因為日誌，n是嚴格小於n一旦我們有很大的數字，

1028
01:01:35,210 --> 01:01:40,230
n倍日誌n是小於n次n或n的平方。

1029
01:01:40,230 --> 01:01:44,410
那麼，這是什麼感覺，實際上是一個更好的算法的運行時間，

1030
01:01:44,410 --> 01:01:50,380
n次日誌n，而不是為n的平方？在這裡，我們走了。單擊開始，單擊，單擊。

1031
01:01:55,690 --> 01:01:58,650
>> 這就是它使用類似歸併排序。

1032
01:01:58,650 --> 01:02:01,680
我們有一個時刻。讓我們來看看這裡發生了什麼。

1033
01:02:09,440 --> 01:02:12,440
[笑]冒泡排序是誰的錢？

1034
01:02:14,960 --> 01:02:16,730
而有時取決於輸入。

1035
01:02:16,730 --> 01:02:18,120
讓我們來看看。

1036
01:02:18,120 --> 01:02:23,320
來吧。我覺得他應該正在迎頭趕上。 >> [學生]，冒泡排序！

1037
01:02:23,320 --> 01:02:27,370
[學生口中念念有詞]

1038
01:02:27,370 --> 01:02:29,120
[馬蘭]是啊，是啊。

1039
01:02:29,120 --> 01:02:34,520
[學生口中念念有詞走，走，走！

1040
01:02:37,210 --> 01:02:40,450
[歡呼] [掌聲]

1041
01:02:40,450 --> 01:02:46,240
1日，最後的演示，所以現在如果它是一個小技巧來包裝你的頭腦圍繞數學

1042
01:02:46,240 --> 01:02:49,280
那裡的可視化排序，你實際上可以聽到的速度

1043
01:02:49,280 --> 01:02:51,000
不同的算法不同。

1044
01:02:51,000 --> 01:02:53,900
這是一個動畫的人，其實聽起來就

1045
01:02:53,900 --> 01:02:56,980
的交換的方法和對條形高度的。

1046
01:02:56,980 --> 01:03:00,440
正如我們將要看到這裡，有幾個排序算法，在那裡，人們想到。

1047
01:03:00,440 --> 01:03:03,660
這第一個將是插入排序，這將飛過

1048
01:03:03,660 --> 01:03:07,090
給你的感覺如何將這些不同的算法工作的聲音。

1049
01:03:07,090 --> 01:03:09,080
這裡是插入排序。

1050
01:03:09,080 --> 01:03:18,410
[電子蜂鳴聲]

1051
01:03:18,410 --> 01:03:20,730
[馬蘭]冒泡排序。

1052
01:03:20,730 --> 01:03:46,850
[更快的電子蜂鳴聲]

1053
01:03:46,850 --> 01:03:48,950
[馬蘭]選擇排序。

1054
01:03:48,950 --> 01:04:03,580
[更快的電子蜂鳴聲]

1055
01:04:03,580 --> 01:04:05,770
[馬蘭]歸併排序。

1056
01:04:05,770 --> 01:04:17,270
[電子蜂鳴聲]

1057
01:04:17,270 --> 01:04:20,180
[嗶嗶減慢] [笑]

1058
01:04:20,180 --> 01:04:22,590
[馬蘭]地精排序。

1059
01:04:22,590 --> 01:04:38,580
[電子蜂鳴聲]

1060
01:04:39,740 --> 01:04:46,150
>> 這是CS50。我們會下週見。 [掌聲和歡呼]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]