1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [第3條 - 更舒適]

2
00:00:02,570 --> 00:00:05,070
[羅布·鮑登 - 哈佛大學]

3
00:00:05,070 --> 00:00:07,310
>> [這是CS50。 -  CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> 所以第一個問題是奇怪的措辭。

5
00:00:12,700 --> 00:00:17,480
GDB可以讓你“調試”程序，但是，更具體地說，是什麼讓你這樣做嗎？

6
00:00:17,480 --> 00:00:22,590
我會回答這個問題，我不知道發生了什麼準確預計，

7
00:00:22,590 --> 00:00:27,910
所以我猜它的東西，它的沿線，讓你一步一步

8
00:00:27,910 --> 00:00:31,540
步行通過該計劃，與它進行交互，更改變量，做所有這些事情 - 

9
00:00:31,540 --> 00:00:34,270
基本上完全控制程序的執行

10
00:00:34,270 --> 00:00:38,410
並檢查執行的程序的一部分。

11
00:00:38,410 --> 00:00:43,030
因此，這些功能可以讓你調試的東西。

12
00:00:43,030 --> 00:00:44,830
好吧。

13
00:00:44,830 --> 00:00:50,520
為什麼二進制搜索需要一個數組進行排序？

14
00:00:50,520 --> 00:00:53,360
誰願意回答這個問題嗎？

15
00:00:56,120 --> 00:01:00,070
[學生]：因為這是行不通的，如果它不排序。 >>呀。 [笑聲]

16
00:01:00,070 --> 00:01:04,910
如果沒有排序，那是不可能的分裂它的一半

17
00:01:04,910 --> 00:01:07,850
知道這一切的左側是少的一切權利

18
00:01:07,850 --> 00:01:10,490
大於中間值。

19
00:01:10,490 --> 00:01:12,790
因此，它需要進行排序。

20
00:01:12,790 --> 00:01:14,170
好吧。

21
00:01:14,170 --> 00:01:17,570
為什麼是冒泡排序在O n的平方嗎？

22
00:01:17,570 --> 00:01:23,230
有誰首先要給予什麼冒泡排序是一個非常快的高層次的概述？

23
00:01:25,950 --> 00:01:33,020
[學生]：基本上，您的每一個元素，你去檢查的前幾個元素。

24
00:01:33,020 --> 00:01:37,150
吧，如果的你交換他們的地方，然後你查了下幾個元素等。

25
00:01:37,150 --> 00:01:40,770
當你到達終點，那麼你知道，最大的元素放在最後，

26
00:01:40,770 --> 00:01:42,750
所以你忽視這一點的話，你繼續經歷，

27
00:01:42,750 --> 00:01:48,490
每一次，你必須檢查少了一個元素，直到你不改變。 >>呀。

28
00:01:48,490 --> 00:01:58,470
這就是所謂的冒泡排序，因為如果你在其一側翻轉數組，所以它的向上和向下，垂直，

29
00:01:58,470 --> 00:02:03,100
那麼大的值會沉底，小的值將泡沫到頂部。

30
00:02:03,100 --> 00:02:05,210
這就是它得到了它的名字。

31
00:02:05,210 --> 00:02:08,220
是啊，你只是去。

32
00:02:08,220 --> 00:02:11,190
你繼續通過陣列，交換中的較大值

33
00:02:11,190 --> 00:02:14,040
得到最大的值的底部。

34
00:02:14,040 --> 00:02:17,500
>> 為什麼是IT O n的平方呢？

35
00:02:18,690 --> 00:02:24,620
首先，沒有人說為什麼它是Øn的平方？

36
00:02:24,620 --> 00:02:28,760
[學生]由於每次運行時，它會n次。

37
00:02:28,760 --> 00:02:32,100
您只能確保你已經採取了最大的元素一路下跌，

38
00:02:32,100 --> 00:02:35,230
那麼，你必須重複一樣多的元素。 >>呀。

39
00:02:35,230 --> 00:02:41,800
所以記住什麼大的“O”表示什麼大的歐米茄手段。

40
00:02:41,800 --> 00:02:50,560
大O是一樣的上限如何慢，其實是可以運行的。

41
00:02:50,560 --> 00:02:58,990
所以說的O n的平方，它是不是O的n否則將無法運行

42
00:02:58,990 --> 00:03:02,640
線性時間，但它是O n的立方

43
00:03:02,640 --> 00:03:06,390
因為它的邊界是由O n個立方。

44
00:03:06,390 --> 00:03:12,300
如果它一定的O n的平方，那麼它的界也由N的立方。

45
00:03:12,300 --> 00:03:20,280
因此，它是n的平方，絕對是最糟糕的情況下，不能做的更好比n的平方，

46
00:03:20,280 --> 00:03:22,830
這就是為什麼它是O n個平方。

47
00:03:22,830 --> 00:03:31,200
它是如何為n的平方，所以看到輕微的數學，

48
00:03:31,200 --> 00:03:40,530
如果我們有五件事情在我們的名單中，第一次能有多少掉期我們可能需要進行

49
00:03:40,530 --> 00:03:47,170
為了得到它？讓我們實際上只是 - 

50
00:03:47,170 --> 00:03:52,040
多少掉期，我們要通過數組必須在第一次運行的冒泡排序？

51
00:03:52,040 --> 00:03:53,540
[學生]：N  -  1。 >>呀。

52
00:03:53,540 --> 00:03:58,340
>> 如果有5個元素，我們需要做N  -  1。

53
00:03:58,340 --> 00:04:01,100
然後在第二個我們要多少掉期使嗎？

54
00:04:01,100 --> 00:04:03,440
[學生]：N  -  2。 >>呀。

55
00:04:03,440 --> 00:04:11,640
第三個是為n  -  3，然後為方便起見，我會寫的最後兩

56
00:04:11,640 --> 00:04:15,270
然後我們需要做2掉期和1交換。

57
00:04:15,270 --> 00:04:19,899
我想最後一個可能會或可能不會實際需要的情況發生。

58
00:04:19,899 --> 00:04:22,820
它是一個交換嗎？我不知道。

59
00:04:22,820 --> 00:04:26,490
因此，這些掉期交易的總金額，或者至少比較，你必須做出。

60
00:04:26,490 --> 00:04:29,910
即使你不交換，你仍然需要的值進行比較。

61
00:04:29,910 --> 00:04:33,910
因此，有n  -  1個比較，在第一次運行時通過數組。

62
00:04:33,910 --> 00:04:42,050
如果你重新安排這些事情，讓我們實際上使六樣東西，這樣的事情疊加起來很好，

63
00:04:42,050 --> 00:04:44,790
然後我會做3，2，1。

64
00:04:44,790 --> 00:04:49,910
因此，只要重新排列這些錢，我們希望看到我們做多少次比較

65
00:04:49,910 --> 00:04:52,700
在整個算法。

66
00:04:52,700 --> 00:04:56,550
因此，如果我們把這些傢伙在這裡，

67
00:04:56,550 --> 00:05:07,470
然後我們還只是總結然而有許多比較。

68
00:05:07,470 --> 00:05:13,280
但是，如果我們總結，我們總結，我們總結這些，

69
00:05:13,280 --> 00:05:18,130
它仍然是同樣的問題。我們只是總結了這些特殊群體。

70
00:05:18,130 --> 00:05:22,400
>> 所以，現在我們正在總結3 N。這不只是3 n的。

71
00:05:22,400 --> 00:05:27,650
它總是要N / 2 n的。

72
00:05:27,650 --> 00:05:29,430
所以，我們在這裡發生的有6個。

73
00:05:29,430 --> 00:05:34,830
如果我們有10件事情，那麼我們可以做到這一點分組為5個不同的東西對

74
00:05:34,830 --> 00:05:37,180
和N + N + N + N + N。

75
00:05:37,180 --> 00:05:45,840
所以，你總是會得到N / 2 n的，所以這一點，我們就會把它記為n的平方/ 2。

76
00:05:45,840 --> 00:05:48,890
因此，即使它的一半，捎來的因素

77
00:05:48,890 --> 00:05:54,190
由於這一事實，通過在陣列的每個迭代中，我們比較少1

78
00:05:54,190 --> 00:05:58,040
所以這就是我們得到了超過2，但它仍然為n的平方。

79
00:05:58,040 --> 00:06:01,650
我們不關心的常數因子的一半。

80
00:06:01,650 --> 00:06:07,760
所以這樣一個大O的東西很多依賴於只是做這類數學，

81
00:06:07,760 --> 00:06:12,260
做算術金額的幾何級數的東西，

82
00:06:12,260 --> 00:06:17,750
但他們大多在此過程是非常簡單的。

83
00:06:17,750 --> 00:06:19,290
好吧。

84
00:06:19,290 --> 00:06:24,430
為什麼是插入排序在歐米茄的n？歐米茄是什麼意思？

85
00:06:24,430 --> 00:06:27,730
兩名學生在一次發言 - 不知所云] >>呀。

86
00:06:27,730 --> 00:06:30,630
歐米茄你能想到的下限。

87
00:06:30,630 --> 00:06:36,550
>> 因此，無論您的插入排序算法的效率有多高，

88
00:06:36,550 --> 00:06:41,810
無論通過在列表中的，它總​​是有比較至少有n個東西

89
00:06:41,810 --> 00:06:44,620
或重複過N。

90
00:06:44,620 --> 00:06:47,280
這是為什麼？

91
00:06:47,280 --> 00:06:51,190
[學生]因為如果列表已經排序，然後通過一次迭代

92
00:06:51,190 --> 00:06:54,080
你的第一個元素是最少的，只能保證

93
00:06:54,080 --> 00:06:56,490
和第二次迭​​代中，您只能保證前兩個是

94
00:06:56,490 --> 00:07:00,010
因為你不知道，其餘的列表進行排序。 >>呀。

95
00:07:00,010 --> 00:07:08,910
如果你傳遞一個完全排序的列表，最起碼你得去所有的元素

96
00:07:08,910 --> 00:07:12,180
看，沒有什麼需要左右移動。

97
00:07:12,180 --> 00:07:14,720
因此，通過列表，並說哦，這已經排序，

98
00:07:14,720 --> 00:07:18,240
這是不可能的，你知道它的排序，直到你檢查每個元素

99
00:07:18,240 --> 00:07:20,660
看，他們是在排序順序。

100
00:07:20,660 --> 00:07:25,290
所以插入排序的下限是歐米茄的n。

101
00:07:25,290 --> 00:07:28,210
什麼是最壞的情況下，歸併排序的運行時間，

102
00:07:28,210 --> 00:07:31,390
最壞的情況是大O嗎？

103
00:07:31,390 --> 00:07:37,660
因此，在最壞的情況下，如何合併排序運行？

104
00:07:42,170 --> 00:07:43,690
[學生] n日誌n。 >>呀。

105
00:07:43,690 --> 00:07:49,990
一般最快的排序算法是n日誌n。你不能做的更好。

106
00:07:51,930 --> 00:07:55,130
>> 有特殊情況下，如果我們今天有時間 - 但我們可能won't  - 

107
00:07:55,130 --> 00:07:59,330
我們可以看到，它比n日誌n。

108
00:07:59,330 --> 00:08:04,050
但在一般情況下，你不能做的更好比n日誌n。

109
00:08:04,050 --> 00:08:09,680
合併排序恰好是一個你應該知道這門課程是n日誌n。

110
00:08:09,680 --> 00:08:13,260
因此，我們實際上將實施的今天。

111
00:08:13,260 --> 00:08:18,070
最後，在不超過三句話，選擇排序是如何工作的？

112
00:08:18,070 --> 00:08:20,370
是否有人要回答的問題，我會計算你的句子

113
00:08:20,370 --> 00:08:22,390
因為如果你在3  - 

114
00:08:25,530 --> 00:08:28,330
有誰還記得選擇排序？

115
00:08:31,280 --> 00:08:37,809
選擇排序通常是很容易記住的名稱。

116
00:08:37,809 --> 00:08:45,350
您遍歷該數組，無論值最大或最小 - 

117
00:08:45,350 --> 00:08:47,290
任何順序排序

118
00:08:47,290 --> 00:08:50,750
因此，讓我們說，我們正在從最小到最大的排序。

119
00:08:50,750 --> 00:08:55,250
您遍歷數組，尋找任何的最小元素，

120
00:08:55,250 --> 00:08:59,750
選擇它，然後就交換，無論是擺在首位。

121
00:08:59,750 --> 00:09:04,090
然後在數組中的第二次，再次尋找最小的元素，

122
00:09:04,090 --> 00:09:07,490
選擇它，然後交換在第二的位置。

123
00:09:07,490 --> 00:09:10,650
因此，我們只是挑選和選擇的最低值

124
00:09:10,650 --> 00:09:16,050
將它們插入到陣列的前面，直到它被排序。

125
00:09:19,210 --> 00:09:21,560
該問題嗎？

126
00:09:21,560 --> 00:09:25,710
>> 這些不可避免地出現在你的表格必須填寫，當你提交的pset。

127
00:09:29,010 --> 00:09:32,360
這些基本上都是那些的答案。

128
00:09:32,360 --> 00:09:34,230
好了，現在編碼的問題。

129
00:09:34,230 --> 00:09:40,140
我已經發送過電子郵件 - 沒有人不明白的電子郵件嗎？好吧。

130
00:09:40,140 --> 00:09:46,630
我已經發送過電子郵件，我們將要使用的空間，

131
00:09:46,630 --> 00:09:52,120
如果你點擊我的名字 - 所以我想我會在底部

132
00:09:52,120 --> 00:09:57,170
由於向後ŕ - 但如果你點擊我的名字，你會看到兩個版本。

133
00:09:57,170 --> 00:10:02,650
第1次修訂將要被我已經複製並粘貼代碼到空間

134
00:10:02,650 --> 00:10:06,900
搜索的事情，你將不得不實行。

135
00:10:06,900 --> 00:10:10,540
第二次修訂將排序的事情，我們實施之後。

136
00:10:10,540 --> 00:10:15,770
因此，您可以點擊我的第1次修訂，並從那裡工作。

137
00:10:17,350 --> 00:10:22,060
現在我們要實現二進制搜索。

138
00:10:22,060 --> 00:10:26,470
>> 有沒有人想只給一個偽高層次的解釋

139
00:10:26,470 --> 00:10:31,440
我們有做搜索？是啊。

140
00:10:31,440 --> 00:10:36,170
[學生]你只取中間的數組，如果你正在尋找

141
00:10:36,170 --> 00:10:38,650
小於或大於。

142
00:10:38,650 --> 00:10:41,080
如果是少了，你去的那一半少，

143
00:10:41,080 --> 00:10:44,750
，如果它更重要的是，你去了一半，更重要的是，你重複，直到你剛剛得到的一件事。

144
00:10:44,750 --> 00:10:46,570
鮑登]是啊。

145
00:10:46,570 --> 00:10:51,320
請注意，我們的數字數組已經排序，

146
00:10:51,320 --> 00:10:57,190
因此，這意味著，我們可以利用這一點，我們可以先檢查，

147
00:10:57,190 --> 00:11:00,390
好了，我在尋找數50。

148
00:11:00,390 --> 00:11:03,720
所以，我可以進入中間。

149
00:11:03,720 --> 00:11:07,380
中間是很難界定的東西，它是一個偶數時，

150
00:11:07,380 --> 00:11:10,820
但我們只能說我們會永遠的中間截斷。

151
00:11:10,820 --> 00:11:14,420
所以在這裡我們8件事，所以中間是16。

152
00:11:14,420 --> 00:11:17,330
我在尋找50，所以50大於16。

153
00:11:17,330 --> 00:11:21,310
所以，現在我基本上可以把我的數組，因為這些元素。

154
00:11:21,310 --> 00:11:23,450
我可以扔掉一切從16倍。

155
00:11:23,450 --> 00:11:27,440
現在我的數組是這4個元素，讓我再說一遍。

156
00:11:27,440 --> 00:11:31,910
於是我想再次找到中間，這將是42。

157
00:11:31,910 --> 00:11:34,730
42小於50，這樣我就可以扔掉這兩種元素。

158
00:11:34,730 --> 00:11:36,890
這是我剩下的陣列。

159
00:11:36,890 --> 00:11:38,430
我要再次找到中間。

160
00:11:38,430 --> 00:11:42,100
我想50是一個壞榜樣，因為我總是扔掉的左的東西，

161
00:11:42,100 --> 00:11:48,280
但相同的措施，如果我在尋找的東西

162
00:11:48,280 --> 00:11:52,100
，它是小於的元素，我目前正在研究，

163
00:11:52,100 --> 00:11:55,080
然後，我要扔掉的一切權利。

164
00:11:55,080 --> 00:11:58,150
所以，現在我們需要實現這一點。

165
00:11:58,150 --> 00:12:02,310
請注意，我們需要傳遞的大小。

166
00:12:02,310 --> 00:12:06,730
我們也可以不需要進行硬編碼的大小。

167
00:12:06,730 --> 00:12:11,640
因此，如果我們擺脫這種定義 - 

168
00:12:19,630 --> 00:12:21,430
好吧。

169
00:12:21,430 --> 00:12:27,180
我怎樣才能很好地計算出目前的數字數組的大小是什麼？

170
00:12:27,180 --> 00:12:30,950
>> 數字數組有多少個元素？

171
00:12:30,950 --> 00:12:33,630
[學生]數字，括號，長度？

172
00:12:33,630 --> 00:12:36,600
[鮑登]不存在C中

173
00:12:36,600 --> 00:12:38,580
需要的長度。

174
00:12:38,580 --> 00:12:42,010
陣列所不具有的特性，所以數組有沒有length屬性

175
00:12:42,010 --> 00:12:45,650
這只會給你然而，它正好是。

176
00:12:48,180 --> 00:12:51,620
[學生]它有多大的內存和除以多少 - “”是啊。

177
00:12:51,620 --> 00:12:55,810
所以我們可以看到它有多大的內存？ >> [學生] SIZEOF。 “是啊，大小。

178
00:12:55,810 --> 00:13:01,680
sizeof是操作員要返回的數字數組的大小。

179
00:13:01,680 --> 00:13:10,060
這是怎麼回事，然而，許多整數有一個整數的大小

180
00:13:10,060 --> 00:13:14,050
因為這是多大的內存，它實際上是佔用了。

181
00:13:14,050 --> 00:13:17,630
所以，如果我想在陣列中的一些事情，

182
00:13:17,630 --> 00:13:20,560
然後，我會想除以整數的大小。

183
00:13:22,820 --> 00:13:26,010
好吧。所以，讓我在這裡傳遞的大小。

184
00:13:26,010 --> 00:13:29,430
為什麼我需要傳遞的大小嗎？

185
00:13:29,430 --> 00:13:38,570
為什麼我不能只是做了詮釋大小=大小（幹草堆）/ sizeof（int）的的嗎？

186
00:13:38,570 --> 00:13:41,490
為什麼不工作？

187
00:13:41,490 --> 00:13:44,470
[學生]：這是不是一個全局變量。

188
00:13:44,470 --> 00:13:51,540
鮑登草堆存在，我們通過在數字草垛，

189
00:13:51,540 --> 00:13:54,700
這是一種什麼樣的來了伏筆。是啊。

190
00:13:54,700 --> 00:14:00,170
[學生]草堆只是對它的引用，所以它會返回引用是多大。

191
00:14:00,170 --> 00:14:02,150
是啊。

192
00:14:02,150 --> 00:14:09,000
我懷疑你在課堂上看到了堆棧真的，對嗎？

193
00:14:09,000 --> 00:14:11,270
我們剛剛談到它。

194
00:14:11,270 --> 00:14:16,090
所以堆棧是其中所有變量都以被存儲。

195
00:14:16,090 --> 00:14:19,960
>> 在堆棧中為局部變量的分配的任何內存是怎麼回事，

196
00:14:19,960 --> 00:14:24,790
每一個函數都有自己的堆棧空間，它自己的堆棧幀是它叫什麼。

197
00:14:24,790 --> 00:14:31,590
因此，主要有它的棧幀，然後在它裡面會存在這方面的數字陣列，

198
00:14:31,590 --> 00:14:34,270
它的尺寸大小（數字）。

199
00:14:34,270 --> 00:14:38,180
這將有大小除以元素大小的數字，

200
00:14:38,180 --> 00:14:42,010
但主要的堆棧幀中所有的生命。

201
00:14:42,010 --> 00:14:45,190
當我們調用搜索，搜索得到它自己的堆棧幀，

202
00:14:45,190 --> 00:14:48,840
自己的空間來存儲所有的局部變量。

203
00:14:48,840 --> 00:14:56,420
但這些參數 - 草垛是不是這整個數組的副本。

204
00:14:56,420 --> 00:15:00,990
我們不會將整個陣列作為複製到搜索。

205
00:15:00,990 --> 00:15:04,030
它只是傳遞一個引用到該數組。

206
00:15:04,030 --> 00:15:11,470
因此，搜索就可以訪問這些數字，通過這個引用。

207
00:15:11,470 --> 00:15:17,100
它仍然訪問主要的堆棧幀裡面的東西，生活，

208
00:15:17,100 --> 00:15:22,990
但基本上，當我們得到的指針，這應該是很快，

209
00:15:22,990 --> 00:15:24,980
這是指針是什麼。

210
00:15:24,980 --> 00:15:29,400
只是指針引用的東西，你可以使用指針來訪問的東西

211
00:15:29,400 --> 00:15:32,030
在其他的事情'堆棧幀。

212
00:15:32,030 --> 00:15:37,660
因此，儘管數字是當地主，我們仍然可以訪問它，通過這個指針。

213
00:15:37,660 --> 00:15:41,770
但是，因為它只是一個指針，它只是一個參考，

214
00:15:41,770 --> 00:15:45,040
大小（幹草堆）返回引用本身的大小。

215
00:15:45,040 --> 00:15:47,950
它不會返回它指向的東西的大小。

216
00:15:47,950 --> 00:15:51,110
它不返回數字的實際大小。

217
00:15:51,110 --> 00:15:55,660
所以這是去上班，因為我們希望它。

218
00:15:55,660 --> 00:15:57,320
>> 該問題嗎？

219
00:15:57,320 --> 00:16:03,250
指針將進入顯著血淋淋的細節在數週的到來。

220
00:16:06,750 --> 00:16:13,740
這就是為什麼有很多的東西，你看，大多數搜索的東西或排序的東西，

221
00:16:13,740 --> 00:16:16,990
他們幾乎所有的事情，需要採取實際數組的大小，

222
00:16:16,990 --> 00:16:20,440
因為在C中，我們不知道數組的大小。

223
00:16:20,440 --> 00:16:22,720
您需要手動將它傳遞進來。

224
00:16:22,720 --> 00:16:27,190
你也可以手動通過整個陣列，因為你只是路過的參考

225
00:16:27,190 --> 00:16:30,390
它不能得到從基準的大小。

226
00:16:30,390 --> 00:16:32,300
好吧。

227
00:16:32,300 --> 00:16:38,160
所以，現在我們要實現什麼解釋過。

228
00:16:38,160 --> 00:16:41,530
你可以在一分鐘，

229
00:16:41,530 --> 00:16:45,250
你不必擔心讓一切完美的100％。

230
00:16:45,250 --> 00:16:51,410
只寫了一半的偽代碼，你是怎麼想它應該工作。

231
00:16:52,000 --> 00:16:53,630
好吧。

232
00:16:53,630 --> 00:16:56,350
沒有必要完全做到這一點。

233
00:16:56,350 --> 00:17:02,380
但是，沒有人感到舒適與他們有什麼到目前為止，

234
00:17:02,380 --> 00:17:05,599
喜歡的東西，我們可以一起嗎？

235
00:17:05,599 --> 00:17:09,690
有沒有人想自願嗎？或者我會隨機挑選。

236
00:17:12,680 --> 00:17:18,599
它不具有任何措施，而是東西，我們可以通過修改進入了工作狀態是正確的。

237
00:17:18,599 --> 00:17:20,720
[學生]：當然可以。 “好了。

238
00:17:20,720 --> 00:17:27,220
所以，你可以保存修改，點擊保存圖標上的小。

239
00:17:27,220 --> 00:17:29,950
你專區Ramya，對不對？ >> [學生]是啊。 >> [鮑登]好吧。

240
00:17:29,950 --> 00:17:35,140
所以，現在我可以看到你的修訂，每個人都可以拉起來的修訂。

241
00:17:35,140 --> 00:17:38,600
在這裡，我們有 - 好。

242
00:17:38,600 --> 00:17:43,160
於是專區Ramya的遞歸解決方案，這無疑是一個有效的解決方案。

243
00:17:43,160 --> 00:17:44,970
有兩種方法可以做到這一點問題。

244
00:17:44,970 --> 00:17:48,060
你可以做到這一點迭代或遞歸。

245
00:17:48,060 --> 00:17:53,860
大多數遇到的問題，可以做遞歸也可以通過反复。

246
00:17:53,860 --> 00:17:58,510
所以，在這裡，我們已經做了遞歸。

247
00:17:58,510 --> 00:18:03,730
>> 是否有人想函數的遞歸定義是什麼意思？

248
00:18:07,210 --> 00:18:08,920
[學生]當你有一個函數調用自身

249
00:18:08,920 --> 00:18:13,470
然後調用，直到它與真正的和真實的。 >>呀。

250
00:18:13,470 --> 00:18:17,680
遞歸函數僅僅是一個函數調用自己的。

251
00:18:17,680 --> 00:18:24,140
有三個大的事情，必須有一個遞歸函數。

252
00:18:24,140 --> 00:18:27,310
第一種是很明顯，它調用自身。

253
00:18:27,310 --> 00:18:29,650
第二個是基本情況。

254
00:18:29,650 --> 00:18:33,390
因此，在某些時候，需要停止調用本身，

255
00:18:33,390 --> 00:18:35,610
而這正是的基本情況。

256
00:18:35,610 --> 00:18:43,860
所以，在這裡，我們知道，我們應該停止，我們應該放棄在我們的搜索

257
00:18:43,860 --> 00:18:48,150
當開始等於結束 - 我們就去了，這意味著什麼。

258
00:18:48,150 --> 00:18:52,130
不過，最後的最後一件事是重要的遞歸函數：

259
00:18:52,130 --> 00:18:59,250
函數必須以某種方式接近的基本情況。

260
00:18:59,250 --> 00:19:04,140
喜歡，如果你不更新任何東西時，你的第二次遞歸調用，

261
00:19:04,140 --> 00:19:07,880
如果你真的只是調用該函數使用相同的參數

262
00:19:07,880 --> 00:19:10,130
沒有全局變量發生了變化或任何東西，

263
00:19:10,130 --> 00:19:14,430
你將永遠不會達到的基本情況，在這種情況下，這是很糟糕。

264
00:19:14,430 --> 00:19:17,950
這將是一個無限遞歸和棧溢出。

265
00:19:17,950 --> 00:19:24,330
但在這裡我們可以看到，在更新發生，因為我們正在更新啟動+ / 2年底，

266
00:19:24,330 --> 00:19:28,180
我們正在更新結束參數在這裡，我們在這裡更新start參數。

267
00:19:28,180 --> 00:19:32,860
因此，在所有的遞歸調用，我們要更新的東西。好吧。

268
00:19:32,860 --> 00:19:38,110
你想，走我們通過您的解決方案？ “當然可以。

269
00:19:38,110 --> 00:19:44,270
我使用搜索幫助，這樣每次我有這樣的函數調用

270
00:19:44,270 --> 00:19:47,910
我有我在尋找數組中的開始和結束

271
00:19:47,910 --> 00:19:49,380
在哪裡，我要找的數組。

272
00:19:49,380 --> 00:19:55,330
>> 在每一個步驟，它說這是中間的元素，這是啟動+ / 2年底，

273
00:19:55,330 --> 00:19:58,850
等於我們正在尋找什麼？

274
00:19:58,850 --> 00:20:04,650
如果是這樣，那麼我們發現它，我想會向上傳遞層次的遞歸。

275
00:20:04,650 --> 00:20:12,540
如果這是不正確的，那麼我們是否該中間值的數組過大，

276
00:20:12,540 --> 00:20:19,320
在這種情況下，我們看陣列的左半邊，從開始到中間索引。

277
00:20:19,320 --> 00:20:22,710
否則，我們做半場結束。

278
00:20:22,710 --> 00:20:24,740
鮑登]好吧。

279
00:20:24,740 --> 00:20:27,730
聽起來很好。

280
00:20:27,730 --> 00:20:36,640
好了，這樣一對夫婦的事情，而實際上，這是一個非常高層次的東西

281
00:20:36,640 --> 00:20:41,270
你永遠不會知道這門課程，但它是真實的。

282
00:20:41,270 --> 00:20:46,080
遞歸函數，你總是聽到的是一個糟糕的協議

283
00:20:46,080 --> 00:20:51,160
因為如果你遞歸地調用自己太多的時間，你會得到堆棧溢出

284
00:20:51,160 --> 00:20:54,990
因為，正如我之前說的，每一個函數都有自己的堆棧幀。

285
00:20:54,990 --> 00:20:59,500
因此，每次調用遞歸函數都有自己的堆棧幀。

286
00:20:59,500 --> 00:21:04,140
所以，如果你1000遞歸調用，你會得到1000個堆棧幀，

287
00:21:04,140 --> 00:21:08,390
快，你有太多的棧幀，和剛剛突破。

288
00:21:08,390 --> 00:21:13,480
所以這就是為什麼遞歸函數一般都是壞的。

289
00:21:13,480 --> 00:21:19,370
但有一個不錯的遞歸函數的子集稱為尾遞歸函數，

290
00:21:19,370 --> 00:21:26,120
發生這種情況是一個例子，其中，如果編譯器注意到這個

291
00:21:26,120 --> 00:21:29,920
它應該，我認為 - 鐺，如果你傳遞給它的O2標誌

292
00:21:29,920 --> 00:21:33,250
然後，它會發現這是尾遞歸的東西好。

293
00:21:33,250 --> 00:21:40,050
>> 一遍又一遍，每一次遞歸調用，它會重複使用相同的堆棧幀。

294
00:21:40,050 --> 00:21:47,010
因此，由於您使用的是相同的堆棧幀，你不不必擔心

295
00:21:47,010 --> 00:21:51,690
曾經堆棧溢出，並在同一時間，像你說的，

296
00:21:51,690 --> 00:21:56,380
一旦你返回true，那麼它返回所有這些堆棧幀的

297
00:21:56,380 --> 00:22:01,740
和第10個調用搜索幫助返回的第9位，具有返回到8號。

298
00:22:01,740 --> 00:22:05,360
因此，不需要時發生的功能是尾遞歸。

299
00:22:05,360 --> 00:22:13,740
是什麼讓這個功能尾遞歸的通知，對於任何給定調用搜索幫助

300
00:22:13,740 --> 00:22:18,470
的遞歸調用它的是它的返回。

301
00:22:18,470 --> 00:22:25,290
因此，在第一次調用搜索幫助，我們將立即返回false，

302
00:22:25,290 --> 00:22:29,590
立即返回true，否則我們做一個遞歸調用搜索幫助

303
00:22:29,590 --> 00:22:33,810
我們回到調用返回。

304
00:22:33,810 --> 00:22:51,560
而且我們不能這樣做，如果我們做的東西，如int x =搜索幫助，返回X * 2，

305
00:22:51,560 --> 00:22:55,440
只是一些隨機的變化。

306
00:22:55,440 --> 00:23:01,470
>> 所以，現在這個遞歸調用，此int x =搜索幫助遞歸調用，

307
00:23:01,470 --> 00:23:05,740
不再是尾遞歸，因為它實際上不返回

308
00:23:05,740 --> 00:23:10,400
返回到前一個堆棧幀，這樣，以前的呼叫的功能

309
00:23:10,400 --> 00:23:13,040
然後做一些事情的返回值。

310
00:23:13,040 --> 00:23:22,190
因此，這是不是尾遞歸，但我們以前是很好的尾遞歸。是啊。

311
00:23:22,190 --> 00:23:27,000
[學生]不應該的第二基本情況，首先檢查

312
00:23:27,000 --> 00:23:30,640
因為有可能的情況就是當你傳遞給它的參數

313
00:23:30,640 --> 00:23:35,770
你已經開始=結束，但他們是針價值。

314
00:23:35,770 --> 00:23:47,310
問題是不能運行的情況下到針到底是值

315
00:23:47,310 --> 00:23:52,000
或開始=結束，適當的，開始結束

316
00:23:52,000 --> 00:23:59,480
，你有沒有檢查那個特定的值，

317
00:23:59,480 --> 00:24:03,910
然後開始+ / 2年底將是相同的值。

318
00:24:03,910 --> 00:24:07,890
但我們已經返回false，我們從來沒有真正得到的價值。

319
00:24:07,890 --> 00:24:14,240
所以，最起碼，在第一次調用，如果大小是0，那麼，我們要返回false。

320
00:24:14,240 --> 00:24:17,710
但是，如果大小為1，然後開始不等於結束，

321
00:24:17,710 --> 00:24:19,820
我們將至少檢查一個元素。

322
00:24:19,820 --> 00:24:26,750
但我認為你是正確的，我們就可以結束的情況下，啟動+ / 2年底，

323
00:24:26,750 --> 00:24:31,190
開始結束了一樣啟動+ / 2年底，

324
00:24:31,190 --> 00:24:35,350
但我們從來沒有真正檢查該元素。

325
00:24:35,350 --> 00:24:44,740
>> 因此，如果我們首先檢查的是中間的元素，我們正在尋找的價值，

326
00:24:44,740 --> 00:24:47,110
那麼我們就可以立即返回true。

327
00:24:47,110 --> 00:24:50,740
否則，如果他們是平等的，那麼有沒有點繼續

328
00:24:50,740 --> 00:24:58,440
因為我們只是要更新的情況下，我們是一個單元素數組。

329
00:24:58,440 --> 00:25:01,110
如果，不是一個單一的元素是我們正在尋找的，

330
00:25:01,110 --> 00:25:03,530
然後一切是錯誤的。是啊。

331
00:25:03,530 --> 00:25:08,900
[學生]的事情是，由於大小實際上是大於在數組中的元素數

332
00:25:08,900 --> 00:25:13,070
已經有一個偏移 - “等的大小 - 

333
00:25:13,070 --> 00:25:19,380
[學生]說，如果數組的大小為0，然後搜索幫助將實際檢查草垛0

334
00:25:19,380 --> 00:25:21,490
在第一次調用。

335
00:25:21,490 --> 00:25:25,300
數組的大小為0，所以0是 - “”是啊。

336
00:25:25,300 --> 00:25:30,750
還有另外一件事， - 這可能是很好的。讓我們來想想。

337
00:25:30,750 --> 00:25:40,120
所以，如果數組有10個元素，我們要檢查的是中間的一個指數5，

338
00:25:40,120 --> 00:25:45,700
所以我們正在檢查，讓我們說，該值小於。

339
00:25:45,700 --> 00:25:50,720
因此，我們把一切都帶走5起。

340
00:25:50,720 --> 00:25:54,030
因此，+ / 2年底將是我們新的終端，

341
00:25:54,030 --> 00:25:57,450
所以是的，它總是要留結束之後的數組。

342
00:25:57,450 --> 00:26:03,570
如果它是一個情況下，如果是奇數或偶數，然後我們會檢查，說，4，

343
00:26:03,570 --> 00:26:05,770
但我們仍然丟掉 - 

344
00:26:05,770 --> 00:26:13,500
所以，是的，最終總是要超出了實際的數組。

345
00:26:13,500 --> 00:26:18,350
所以我們的重點元素，最終總是要一前一後的。

346
00:26:18,350 --> 00:26:24,270
所以，如果開始做以往任何時候都等於結束，我們是在一個數組的大小為0。

347
00:26:24,270 --> 00:26:35,600
>> 其他的事情，我的想法是，我們正在更新開始啟動+ / 2年底，

348
00:26:35,600 --> 00:26:44,020
所以這種情況下，我有麻煩，在那裡開始+端/ 2

349
00:26:44,020 --> 00:26:46,820
是的，我們正在檢查的元素。

350
00:26:46,820 --> 00:26:58,150
比方說，我們這10個元素的數組。不管。

351
00:26:58,150 --> 00:27:03,250
因此，+ / 2年底將是像這樣的東西，

352
00:27:03,250 --> 00:27:07,060
如果這不是價值，說，我們要更新。

353
00:27:07,060 --> 00:27:10,060
該值越大，所以，我們想看看在這半年的數組。

354
00:27:10,060 --> 00:27:15,910
因此，我們如何更新開始，我們要更新開始到現在是這樣的元素。

355
00:27:15,910 --> 00:27:23,790
但是，這可能仍然工作，或最起碼，你可以開始+結束/ 2 + 1。

356
00:27:23,790 --> 00:27:27,850
[學生]您不需要開始+結束[聽不清] >>呀。

357
00:27:27,850 --> 00:27:33,240
我們已經檢查了這個元素，而且知道這是不是我們正在尋找一個。

358
00:27:33,240 --> 00:27:36,800
因此，我們並不需要更新的開始是這樣的元素。

359
00:27:36,800 --> 00:27:39,560
我們可以跳過它，並更新開始是這樣的元素。

360
00:27:39,560 --> 00:27:46,060
而且是有過的情況下，讓我們說，這是結束，

361
00:27:46,060 --> 00:27:53,140
因此，然後開始應該是這樣的，開始+結束/ 2應該是這樣的，

362
00:27:53,140 --> 00:28:00,580
開始+結束 - 是的，我認為它可以在無限遞歸。

363
00:28:00,580 --> 00:28:12,690
比方說，它只是一個大小為2的數組或數組的大小為1。我認為這會工作。

364
00:28:12,690 --> 00:28:19,490
目前，開始元素和結束是超越它。

365
00:28:19,490 --> 00:28:24,110
因此，我們要檢查的元素是這一個，

366
00:28:24,110 --> 00:28:29,400
，然後我們在更新開始時，我們要更新開始為0 + 1/2，

367
00:28:29,400 --> 00:28:33,160
這是要結束我們開始這個元素。

368
00:28:33,160 --> 00:28:36,210
>> 所以，我們檢查了一遍又一遍相同的元素。

369
00:28:36,210 --> 00:28:43,310
因此，這是每一個遞歸調用的情況下，必須更新的東西。

370
00:28:43,310 --> 00:28:48,370
因此，我們需要做的啟動+端/ 2 + 1，否則有一個

371
00:28:48,370 --> 00:28:50,710
在這裡我們實際上沒有更新的開始。

372
00:28:50,710 --> 00:28:53,820
每個人都看到了嗎？

373
00:28:53,820 --> 00:28:56,310
好吧。

374
00:28:56,310 --> 00:29:03,860
有沒有人有問題，該解決方案或任何更多的評論？

375
00:29:05,220 --> 00:29:10,280
好吧。沒有任何人有一個迭代的解決方案，我們都可以看嗎？

376
00:29:17,400 --> 00:29:20,940
我們都這樣做遞歸？

377
00:29:20,940 --> 00:29:25,950
我也想，如果你打開了她，那麼你可能會覆蓋你的前一個。

378
00:29:25,950 --> 00:29:28,810
它會自動保存嗎？我還不能肯定。

379
00:29:35,090 --> 00:29:39,130
沒有任何人有反复？

380
00:29:39,130 --> 00:29:42,430
我們可以一起穿過它，如果沒有。

381
00:29:46,080 --> 00:29:48,100
這個想法是將是相同的。

382
00:30:00,260 --> 00:30:02,830
迭代的解決方案。

383
00:30:02,830 --> 00:30:07,140
我們會想，基本上做的是同樣的想法

384
00:30:07,140 --> 00:30:16,530
在這裡我們要跟踪的數組的數組新的結束和新的開始

385
00:30:16,530 --> 00:30:18,510
做一遍又一遍。

386
00:30:18,510 --> 00:30:22,430
並且如果我們跟踪作為開始標記和結束計劃相交，

387
00:30:22,430 --> 00:30:29,020
當時我們沒有找到它，我們可以返回false。

388
00:30:29,020 --> 00:30:37,540
那麼，如何才能做到這一點？任何人有任何建議或代碼為我拉起來嗎？

389
00:30:42,190 --> 00:30:47,450
[學生]做一個while循環。 >>呀。

390
00:30:47,450 --> 00:30:49,450
你會希望做一個循環。

391
00:30:49,450 --> 00:30:51,830
>> 你的代碼，我可以拉，你要什麼建議嗎？

392
00:30:51,830 --> 00:30:56,340
[學生]我是這麼認為的。 >>所有權利。這使事情變得更容易。你叫什麼名字？

393
00:30:56,340 --> 00:30:57,890
[學生]盧卡斯。

394
00:31:00,140 --> 00:31:04,190
第1次修訂。好吧。

395
00:31:04,190 --> 00:31:13,200
低就是我們俗稱的開始之前。

396
00:31:13,200 --> 00:31:17,080
是不完全是我們稱為前結束。

397
00:31:17,080 --> 00:31:22,750
其實，到底是現在在陣列內。這是我們應該考慮的元素。

398
00:31:22,750 --> 00:31:26,890
如此之低是0，是陣列的大小， -  1，

399
00:31:26,890 --> 00:31:34,780
，現在我們正在循環，我們正在檢查 - 

400
00:31:34,780 --> 00:31:37,340
我想你可以穿過它。

401
00:31:37,340 --> 00:31:41,420
什麼是你的想法通過呢？走我們通過您的代碼。

402
00:31:41,420 --> 00:31:49,940
[學生]：當然可以。在草垛的中間值，並把它比作針。

403
00:31:49,940 --> 00:31:58,520
所以，如果要大於你的針，然後你想 - 哦，其實，應該是向後。

404
00:31:58,520 --> 00:32:05,180
你會想扔掉的右半邊，所以是的，這應該是方法。

405
00:32:05,180 --> 00:32:08,830
[鮑登]因此，這應該是少了呢？這就是你說的嗎？ >> [學生]是啊。

406
00:32:08,830 --> 00:32:10,390
鮑登]好吧。更少一些。

407
00:32:10,390 --> 00:32:15,700
所以，如果我們要找的是比我們想要的東西，

408
00:32:15,700 --> 00:32:19,410
是啊，我們要扔掉的左半邊，

409
00:32:19,410 --> 00:32:22,210
這意味著我們正在更新我們的一切考慮

410
00:32:22,210 --> 00:32:26,610
移動低的數組的權利。

411
00:32:26,610 --> 00:32:30,130
這看起來不錯。

412
00:32:30,130 --> 00:32:34,550
我認為它有同樣的問題，我們說，前一個，

413
00:32:34,550 --> 00:32:49,760
其中，如果低為0和為1，則低+上/ 2的成立是同樣的事情再次。

414
00:32:49,760 --> 00:32:53,860
>> 甚至如果不是這樣的情況下，它仍然是更有效地在至少

415
00:32:53,860 --> 00:32:57,630
扔掉的元素，我們只是看著我們知道這是錯誤的。

416
00:32:57,630 --> 00:33:03,240
如此之低+ / 2 + 1  -  [學生]這應該是其他方式。

417
00:33:03,240 --> 00:33:05,900
鮑登或者這應該是 -  1，另一個應該是+ 1。

418
00:33:05,900 --> 00:33:09,580
[學生]：應該有一個雙等號。 >> [鮑登]是啊。

419
00:33:09,580 --> 00:33:11,340
[學生]是啊。

420
00:33:14,540 --> 00:33:15,910
好吧。

421
00:33:15,910 --> 00:33:21,280
最後，現在，我們有這樣的+ 1  -  1的事情，

422
00:33:21,280 --> 00:33:31,520
是它 - 它可能不是 - 是為低，結束了更大的值比起來，有沒有可能？

423
00:33:35,710 --> 00:33:40,320
我認為唯一的方法可能發生的 - 它是可能的嗎？ >> [學生]：我不知道。

424
00:33:40,320 --> 00:33:45,220
但是，如果它被截斷，然後得到減去1，然後 - “”是啊。

425
00:33:45,220 --> 00:33:47,480
[學生]，可能會出現混亂。

426
00:33:49,700 --> 00:33:53,940
我認為這應該是不錯的，只是因為

427
00:33:53,940 --> 00:33:58,800
結束下，他們必須是平等的，我想。

428
00:33:58,800 --> 00:34:03,070
但如果他們是平等的，那麼我們就不會做了while循環開始

429
00:34:03,070 --> 00:34:06,670
我們只是將返回的值。因此，我認為，我們現在是很好的。

430
00:34:06,670 --> 00:34:11,530
請注意，儘管這個問題已不再是遞歸的，

431
00:34:11,530 --> 00:34:17,400
同一種想法適用於我們可以看到這本身很容易

432
00:34:17,400 --> 00:34:23,659
一個遞歸的解決方案的事實，我們只是更新的指數，一遍又一遍，

433
00:34:23,659 --> 00:34:29,960
我們正在做的小問題，我們關注的一個子集的數組。

434
00:34:29,960 --> 00:34:40,860
[學生]如果低為0和1，它們都為0 + 1/2，這將去0，

435
00:34:40,860 --> 00:34:44,429
，然後將+ 1， -  1。

436
00:34:47,000 --> 00:34:50,870
[學生]：我們在哪裡檢查的平等？

437
00:34:50,870 --> 00:34:55,100
就像如果中間實際上是針？

438
00:34:55,100 --> 00:34:58,590
目前我們還沒有這樣做呢？哦！

439
00:35:00,610 --> 00:35:02,460
如果it's  - 

440
00:35:05,340 --> 00:35:13,740
是。我們不能只是做了測試，在這裡，因為咱們說的第一個中間 - 

441
00:35:13,740 --> 00:35:16,430
[學生]：它實際上是想扔掉的結合。

442
00:35:16,430 --> 00:35:20,220
所以，如果你扔掉綁定的，你必須先檢查或任何。

443
00:35:20,220 --> 00:35:23,350
啊。是啊。 >> [學生]是啊。

444
00:35:23,350 --> 00:35:29,650
所以，現在我們丟掉了一個我們目前看，

445
00:35:29,650 --> 00:35:33,260
這意味著我們現在還需要有

446
00:35:33,260 --> 00:35:44,810
（幹草堆（低+）/ 2] ==針），然後我們就可以返回true。

447
00:35:44,810 --> 00:35:52,070
是否其他人或只是如果，我把它的字面意思是同樣的事情

448
00:35:52,070 --> 00:35:57,110
因為這會返回true。

449
00:35:57,110 --> 00:36:01,450
所以我會把其他的話，但不要緊。

450
00:36:01,450 --> 00:36:10,440
>> 因此，如果這一點，否則這一點，這是常見的事，我做

451
00:36:10,440 --> 00:36:14,340
即使它的情況下，一切都很好，在這裡，

452
00:36:14,340 --> 00:36:22,780
如低永遠不能大於了起來，這是不值得的推理​​是否是真實的。

453
00:36:22,780 --> 00:36:28,010
所以，你可以說，而低是小於或等於

454
00:36:28,010 --> 00:36:30,720
或在低是小於

455
00:36:30,720 --> 00:36:35,300
這樣，如果他們永遠等於或低恰巧經過，

456
00:36:35,300 --> 00:36:40,130
然後我們就可以打破這個循環。

457
00:36:41,410 --> 00:36:44,630
問題，問題，意見嗎？

458
00:36:47,080 --> 00:36:49,270
好吧。這看起來不錯。

459
00:36:49,270 --> 00:36:52,230
現在，我們想要做的那種。

460
00:36:52,230 --> 00:37:04,030
如果我們去我的第二次​​修訂，我們看到這些相同的數字，

461
00:37:04,030 --> 00:37:07,550
但現在他們不再有序。

462
00:37:07,550 --> 00:37:12,840
我們要實現使用任何算法在O n日誌n。

463
00:37:12,840 --> 00:37:17,240
所以，你認為哪種算法，我們應該在這裡實現嗎？ >> [學生]歸併排序。

464
00:37:17,240 --> 00:37:23,810
鮑登]是啊。合併排序是O（n日誌n），所以這就是我們要做的。

465
00:37:23,810 --> 00:37:26,680
的問題將是非常相似的，

466
00:37:26,680 --> 00:37:31,920
它輕易借錢給別人，自己一個遞歸的解決方案。

467
00:37:31,920 --> 00:37:35,580
我們也可以拿出一個迭代的解決方案，如果我們想，

468
00:37:35,580 --> 00:37:42,540
但遞歸會更容易在這裡，我們應該做的遞歸。

469
00:37:45,120 --> 00:37:49,530
我想我們將通過合併排序第一，

470
00:37:49,530 --> 00:37:54,280
雖然已經有一個可愛的視頻歸併排序。 [笑聲]

471
00:37:54,280 --> 00:37:59,780
因此，合併排序有 - 我浪費這麼多的本文。

472
00:37:59,780 --> 00:38:02,080
哦，只有一個左。

473
00:38:02,080 --> 00:38:03,630
所以合併。

474
00:38:08,190 --> 00:38:12,470
哦，1，3，5。

475
00:38:26,090 --> 00:38:27,440
好吧。

476
00:38:29,910 --> 00:38:33,460
合併需要兩個單獨的陣列。

477
00:38:33,460 --> 00:38:36,780
單獨這兩個數組進行排序。

478
00:38:36,780 --> 00:38:40,970
因此，這個數組，1，3，5，排序。此陣列中，0，2，4，排序。

479
00:38:40,970 --> 00:38:46,710
現在合併你應該做的是將它們組合成一個單一的陣列本身就是排序。

480
00:38:46,710 --> 00:38:57,130
因此，我們希望，都將有它裡面的這些元素的數組的大小為6

481
00:38:57,130 --> 00:38:59,390
在排序順序。

482
00:38:59,390 --> 00:39:03,390
>> 因此，我們可以利用一個事實，即這兩個數組進行排序

483
00:39:03,390 --> 00:39:06,800
做到這一點的線性時間，

484
00:39:06,800 --> 00:39:13,510
線性時間的意義，如果這個數組的大小為x，這是大小y，

485
00:39:13,510 --> 00:39:20,970
那麼總的算法應該是O（X + Y）。好吧。

486
00:39:20,970 --> 00:39:23,150
因此，建議。

487
00:39:23,150 --> 00:39:26,030
[學生]我們從左邊開始？

488
00:39:26,030 --> 00:39:30,150
所以，你把0下來，然後1，然後你在這裡的2。

489
00:39:30,150 --> 00:39:33,320
因此，它是一種像你有一個標籤，向右移動。 >> [鮑登]是啊。

490
00:39:33,320 --> 00:39:41,070
對於這些數組，如果我們只專注於最左邊的元素。

491
00:39:41,070 --> 00:39:43,530
因為這兩個數組進行排序，我們知道，這2個元素

492
00:39:43,530 --> 00:39:46,920
是任一陣列中的最小元素。

493
00:39:46,920 --> 00:39:53,500
因此，這意味著這2個要素：1，必須是我們的合併數組中最小的元素。

494
00:39:53,500 --> 00:39:58,190
碰巧的是，最小的是一個正確的時間。

495
00:39:58,190 --> 00:40:02,580
因此，我們採取0，將其插入在左邊，因為0小於1，

496
00:40:02,580 --> 00:40:08,210
所以取0，將其插入到我們的第一個位置，然後更新

497
00:40:08,210 --> 00:40:12,070
到現在為止的第一個元素。

498
00:40:12,070 --> 00:40:14,570
現在，我們重複。

499
00:40:14,570 --> 00:40:20,670
所以，現在我們比較2和1。 1較小，因此，我們將插入1。

500
00:40:20,670 --> 00:40:25,300
我們更新該指針指向這個傢伙。

501
00:40:25,300 --> 00:40:33,160
現在，我們再次做到這一點，所以2。這將更新，比較這2個，3個。

502
00:40:33,160 --> 00:40:37,770
此更新，然後4和5。

503
00:40:37,770 --> 00:40:42,110
所以這是合併。

504
00:40:42,110 --> 00:40:49,010
>> 這應該是很明顯的，它是線性的時間，因為我們只是一次過的每個元素。

505
00:40:49,010 --> 00:40:55,980
這是實施合併排序是這樣做的最大的一步。

506
00:40:55,980 --> 00:40:59,330
它並不難。

507
00:40:59,330 --> 00:41:15,020
有兩件事情要擔心的是，比方說，我們合併1，2，3，4，5，6。

508
00:41:15,020 --> 00:41:30,930
在這種情況下，我們最終場景中的這個人會是較小的，

509
00:41:30,930 --> 00:41:36,160
然後我們更新this指針，這將是更小，更新，

510
00:41:36,160 --> 00:41:41,280
這其中的體積更小，現在你不得不承認

511
00:41:41,280 --> 00:41:44,220
當你運行的元素比較。

512
00:41:44,220 --> 00:41:49,400
因為我們已經使用了這整個陣列，

513
00:41:49,400 --> 00:41:55,190
此數組中的一切現在只是插入到這裡。

514
00:41:55,190 --> 00:42:02,040
所以，如果我們運行其中之一，我們的陣列已經完全融合進點，

515
00:42:02,040 --> 00:42:06,510
然後我們就採取的其他陣列中的所有元素，並將其插入到數組末尾的。

516
00:42:06,510 --> 00:42:13,630
因此，我們就可以插入4，5，6。好吧。

517
00:42:13,630 --> 00:42:18,070
這是一件事要注意的。

518
00:42:22,080 --> 00:42:26,120
實現這應該是第1步。

519
00:42:26,120 --> 00:42:32,600
合併排序，然後此基礎上，它的2個步驟，2個愚蠢的步驟。

520
00:42:38,800 --> 00:42:42,090
讓我們把這個數組中。

521
00:42:57,920 --> 00:43:05,680
所以，歸併排序，第1步是，遞歸打破數組轉換成半。

522
00:43:05,680 --> 00:43:09,350
所以這個數組分割成兩半。

523
00:43:09,350 --> 00:43:22,920
我們現在有4，15，16，50和8，23，42，108。

524
00:43:22,920 --> 00:43:25,800
現在，我們做了一遍，我們分裂成兩半。

525
00:43:25,800 --> 00:43:27,530
我會做的這一邊。

526
00:43:27,530 --> 00:43:34,790
因此，4，15和16，50。

527
00:43:34,790 --> 00:43:37,440
在這裡，我們會做同樣的事情。

528
00:43:37,440 --> 00:43:40,340
現在，我們把它分解成半。

529
00:43:40,340 --> 00:43:51,080
我們有4個，15，16，50。

530
00:43:51,080 --> 00:43:53,170
所以這是我們的基本情況。

531
00:43:53,170 --> 00:44:00,540
一旦數組的大小為1，那麼我們就停止分裂成兩半。

532
00:44:00,540 --> 00:44:03,190
>> 現在我們該怎麼做這個嗎？

533
00:44:03,190 --> 00:44:15,730
我們結束了，這也將分解成8，23，42，和108。

534
00:44:15,730 --> 00:44:24,000
所以，現在，我們在這一點上，現在歸併排序的步驟2的合併對的列表。

535
00:44:24,000 --> 00:44:27,610
因此，我們要合併這些。我們只是調用合併。

536
00:44:27,610 --> 00:44:31,410
我們知道合併將返回這些排序。

537
00:44:31,410 --> 00:44:33,920
4，15。

538
00:44:33,920 --> 00:44:41,440
現在，我們要合併這些，這將返回一個列表的排序順序，

539
00:44:41,440 --> 00:44:44,160
16，50。

540
00:44:44,160 --> 00:44:57,380
我們合併者 - 我不能寫 -  8，23，42，108。

541
00:44:57,380 --> 00:45:02,890
因此，我們必須對一次合併。

542
00:45:02,890 --> 00:45:05,140
現在，我們只需再合併。

543
00:45:05,140 --> 00:45:10,130
請注意，每個列表進行排序本身，

544
00:45:10,130 --> 00:45:15,220
然後我們就可以合併這些列表進行排序的列表大小為4

545
00:45:15,220 --> 00:45:19,990
合併這兩個列表進行排序的列表大小為4。

546
00:45:19,990 --> 00:45:25,710
最後，我們可以合併這兩個列表大小為4，得到一個列表進行排序大小為8。

547
00:45:25,710 --> 00:45:34,030
因此，看，這是整體的n日誌n，我們已經看到的，合併是線性的，

548
00:45:34,030 --> 00:45:40,390
所以，當我們在處理這些的合併，等等之類的整體成本合併

549
00:45:40,390 --> 00:45:43,410
這兩個名單只是因為 - 

550
00:45:43,410 --> 00:45:49,610
好，這是O n個，但N在這裡僅僅是這2個元素，所以它的2。

551
00:45:49,610 --> 00:45:52,850
而這些2將2​​和2將是2和2將是2，

552
00:45:52,850 --> 00:45:58,820
在所有的合併，我們需要做的，我們做Ň。

553
00:45:58,820 --> 00:46:03,210
像2 + 2 + 2 + 2是8，它是N，

554
00:46:03,210 --> 00:46:08,060
所以在這個集合的合併成本是n。

555
00:46:08,060 --> 00:46:10,810
然後是同樣的東西在這裡。

556
00:46:10,810 --> 00:46:16,980
我們將合併這兩個，那麼這些2，本次合併及個別將採取四項業務，

557
00:46:16,980 --> 00:46:23,610
本次合併將採取四則運算，但再一次，在所有這些，

558
00:46:23,610 --> 00:46:29,030
我們最終合併N總的事情，所以這一步需要Ň。

559
00:46:29,030 --> 00:46:33,670
因此，每個級別需要n個元素被合併。

560
00:46:33,670 --> 00:46:36,110
>> 有多少級？

561
00:46:36,110 --> 00:46:40,160
在每個級別上，我們的陣列生長的大小。

562
00:46:40,160 --> 00:46:44,590
在這裡我們的數組的大小為1，在這裡，他們是大小為2，在這裡，他們是大小為4，

563
00:46:44,590 --> 00:46:46,470
最後，它們的大小為8。

564
00:46:46,470 --> 00:46:56,450
所以，因為它增加了一倍，有將是一個總的日誌n這些水平。

565
00:46:56,450 --> 00:47:02,090
所以取n日誌n個層次，每個人的水平總運營，

566
00:47:02,090 --> 00:47:05,720
我們得到了一個n日誌n算法。

567
00:47:05,720 --> 00:47:07,790
有問題嗎？

568
00:47:08,940 --> 00:47:13,320
人已經取得了進展如何實現這一點呢？

569
00:47:13,320 --> 00:47:18,260
有人已經在一個國家，在那裡我可以拉起自己的代碼嗎？

570
00:47:20,320 --> 00:47:22,260
我可以給一分鐘。

571
00:47:24,770 --> 00:47:27,470
此人將變得更長。

572
00:47:27,470 --> 00:47:28,730
我強烈建議復發 - 

573
00:47:28,730 --> 00:47:30,510
你不必做遞歸合併

574
00:47:30,510 --> 00:47:33,750
遞歸合併，因為這樣做，你將不得不通過不同大小的一堆。

575
00:47:33,750 --> 00:47:37,150
可以，但是這很煩人。

576
00:47:37,150 --> 00:47:43,720
但是，遞歸進行排序本身是很容易的。

577
00:47:43,720 --> 00:47:49,190
你只從字面上調用sort左半邊，右半邊的排序上。好吧。

578
00:47:51,770 --> 00:47:54,860
任何人有什麼我可以拉起來嗎？

579
00:47:54,860 --> 00:47:57,540
不然我會給一分鐘。

580
00:47:58,210 --> 00:47:59,900
好吧。

581
00:47:59,900 --> 00:48:02,970
任何人有什麼我們可以使用嗎？

582
00:48:05,450 --> 00:48:09,680
否則，我們就與這，​​然後從那裡展開。

583
00:48:09,680 --> 00:48:14,050
>> 任何人有以上這一點，我可以拉起來嗎？

584
00:48:14,050 --> 00:48:17,770
[學生]是啊。你可以把我的。 >>所有權利。

585
00:48:17,770 --> 00:48:19,730
是的！

586
00:48:22,170 --> 00:48:25,280
[學生]有很多的條件。哦，拍攝。你能 - 

587
00:48:25,280 --> 00:48:28,110
[學生]我一定要救它。 >>呀。

588
00:48:32,420 --> 00:48:35,730
所以，我們做單獨的合併。

589
00:48:35,730 --> 00:48:38,570
哦，但它不是那麼糟糕。

590
00:48:39,790 --> 00:48:41,650
好吧。

591
00:48:41,650 --> 00:48:47,080
因此，排序本身就是只是打電話mergeSortHelp。

592
00:48:47,080 --> 00:48:49,530
我們解釋，什麼mergeSortHelp。

593
00:48:49,530 --> 00:48:55,700
[學生] MergeSortHelp幾乎沒有兩個主要步驟，

594
00:48:55,700 --> 00:49:01,270
這是分類，每個陣列的一半，然後合併他們兩個。

595
00:49:04,960 --> 00:49:08,050
[鮑登]好吧，所以給了我第二次​​。

596
00:49:10,850 --> 00:49:13,210
我認為這 -  >> [學生]我需要 - 

597
00:49:17,100 --> 00:49:19,400
是啊。我失去了一些東西。

598
00:49:19,400 --> 00:49:23,100
在合併，我意識到，我需要創建一個新的數組

599
00:49:23,100 --> 00:49:26,530
因為我不能這樣做的地方。 “是的。你不能。正確的。

600
00:49:26,530 --> 00:49:28,170
[學生]：因此，我創建了一個新的陣列。

601
00:49:28,170 --> 00:49:31,510
我忘了在年底合併，重新更改。

602
00:49:31,510 --> 00:49:34,490
好吧。我們需要一個新的陣列。

603
00:49:34,490 --> 00:49:41,000
在合併排序，這是幾乎總是正確的。

604
00:49:41,000 --> 00:49:44,340
一個更好的算法，時間上的成本部分

605
00:49:44,340 --> 00:49:47,310
幾乎總是需要使用更多的內存。

606
00:49:47,310 --> 00:49:51,570
所以在這裡，無論你怎麼做歸併排序，

607
00:49:51,570 --> 00:49:54,780
你將不可避免地需要使用一些額外的內存。

608
00:49:54,780 --> 00:49:58,240
他或她創造了一個新的陣列。

609
00:49:58,240 --> 00:50:03,400
然後你說結束時，我們只需要到新的數組複製到原來的數組。

610
00:50:03,400 --> 00:50:04,830
[學生]我是這麼認為的，是的。

611
00:50:04,830 --> 00:50:08,210
我不知道如果這樣的作品在計數的參考或任何方面 - 

612
00:50:08,210 --> 00:50:11,650
是的，它會奏效。 >> [學生]好吧。

613
00:50:20,620 --> 00:50:24,480
你有沒有嘗試運行此？ >> [學生]不，還沒有。 “好了。

614
00:50:24,480 --> 00:50:28,880
嘗試運行它，然後我就說說它的第二個。

615
00:50:28,880 --> 00:50:35,200
[學生]我需要把所有的函數原型和一切，但是，對不對？

616
00:50:37,640 --> 00:50:40,840
函數原型。哦，你說的一樣 - 是的。

617
00:50:40,840 --> 00:50:43,040
排序打電話mergeSortHelp。

618
00:50:43,040 --> 00:50:47,390
>> 所以為了進行排序打電話mergeSortHelp，mergeSortHelp必須已定義

619
00:50:47,390 --> 00:50:56,370
排序或之前，我們需要的只是原型。只需複製並粘貼。

620
00:50:56,370 --> 00:50:59,490
同樣，mergeSortHelp被調用合併，

621
00:50:59,490 --> 00:51:03,830
但合併還沒有被定義，所以我們可以讓mergeSortHelp知道

622
00:51:03,830 --> 00:51:08,700
的合併將是什麼樣子，就是這樣。

623
00:51:09,950 --> 00:51:15,730
所以mergeSortHelp。

624
00:51:22,770 --> 00:51:32,660
我們在這裡有一個問題，我們有沒有基礎的情況下。

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp是遞歸的，所以任何遞歸函數

626
00:51:38,110 --> 00:51:42,610
將需要某種形式的基本情況，知道什麼時候才能停止遞歸調用本身。

627
00:51:42,610 --> 00:51:45,590
什麼是我們的基本情況，要在這裡嗎？是啊。

628
00:51:45,590 --> 00:51:49,110
[學生]如果大小為1？ >> [鮑登]是的。

629
00:51:49,110 --> 00:51:56,220
所以，像我們看到，我們停止分裂陣列

630
00:51:56,220 --> 00:52:01,850
一旦我們得到數組的大小為1，這不可避免地排序。

631
00:52:01,850 --> 00:52:09,530
因此，如果大小等於1，我們知道已經排序的數組，

632
00:52:09,530 --> 00:52:12,970
這樣，我們就可以返回。

633
00:52:12,970 --> 00:52:16,880
>> 請注意，這是無效的，所以我們不返回任何特別的，我們只是返回。

634
00:52:16,880 --> 00:52:19,580
好吧。所以這是我們的基本情況。

635
00:52:19,580 --> 00:52:27,440
我想我們的基本情況也可能是，如果我們碰巧被合併數組的大小為0，

636
00:52:27,440 --> 00:52:30,030
我們可能要停止在某些時候，

637
00:52:30,030 --> 00:52:33,610
所以我們只能說大小小於2或小於或等於1

638
00:52:33,610 --> 00:52:37,150
因此，這將工作的任何陣列。

639
00:52:37,150 --> 00:52:38,870
好吧。

640
00:52:38,870 --> 00:52:42,740
所以這是我們的基本情況。

641
00:52:42,740 --> 00:52:45,950
現在你要帶我們通過合併嗎？

642
00:52:45,950 --> 00:52:49,140
所有這些情況意味著什麼呢？

643
00:52:49,140 --> 00:52:54,480
在這裡，我們只是在做同樣的想法， - 

644
00:52:56,970 --> 00:53:02,470
[學生]我需要通過大小，所有的mergeSortHelp調用。

645
00:53:02,470 --> 00:53:10,080
我一個額外的主增加的大小和它的不存在，如大小/ 2。

646
00:53:10,080 --> 00:53:16,210
[鮑登]哦，尺寸/ 2，尺寸/ 2。 >> [學生]是啊，在上面的函數，以及。

647
00:53:16,210 --> 00:53:21,320
鮑登]在這裡？ >> [學生]只要大小。 >> [鮑登哦。大小，尺寸是多少？ >> [學生]是啊。

648
00:53:21,320 --> 00:53:23,010
鮑登]好吧。

649
00:53:23,010 --> 00:53:26,580
讓我想到的第二個。

650
00:53:26,580 --> 00:53:28,780
我們遇到的問題嗎？

651
00:53:28,780 --> 00:53:33,690
我們一直在治療左為0。 >> [學生]第

652
00:53:33,690 --> 00:53:36,340
這是不對的。抱歉。它應該是開始。是啊。

653
00:53:36,340 --> 00:53:39,230
鮑登]好吧。我想效果更好。

654
00:53:39,230 --> 00:53:43,880
和結束。好吧。

655
00:53:43,880 --> 00:53:47,200
所以，現在你要帶領我們通過合併嗎？ >> [學生]好吧。

656
00:53:47,200 --> 00:53:52,150
我只是走過，我創建了這個新陣列。

657
00:53:52,150 --> 00:53:57,420
它的大小是陣列的部分的大小，我們要進行排序

658
00:53:57,420 --> 00:54:03,460
，並試圖找到的元素，我應該把在新的陣列步驟。

659
00:54:03,460 --> 00:54:10,140
因此，要做到這一點，首先我檢查的數組，如果左邊的一半繼續有任何更多的元素，

660
00:54:10,140 --> 00:54:14,260
如果沒有的話，那麼你去，其他情況下，只是說

661
00:54:14,260 --> 00:54:20,180
好了，它必須是在右邊的數組，我們將提出，在目前的指數newArray。

662
00:54:20,180 --> 00:54:27,620
>> 然後否則，我檢查，如果陣列的右側也完成，

663
00:54:27,620 --> 00:54:30,630
在這種情況下，我只是把在左邊。

664
00:54:30,630 --> 00:54:34,180
這實際上可能不會是必要的。我不太肯定。

665
00:54:34,180 --> 00:54:40,970
但無論如何，其他兩個檢查其中的兩個較小的左側或右側。

666
00:54:40,970 --> 00:54:49,770
此外，在每一種情況下，我在遞增佔位符，我增加。

667
00:54:49,770 --> 00:54:52,040
鮑登]好吧。

668
00:54:52,040 --> 00:54:53,840
看起來不錯。

669
00:54:53,840 --> 00:54:58,800
沒有任何人有任何意見或疑慮或問題嗎？

670
00:55:00,660 --> 00:55:07,720
所以的情況下，我們到的是，要帶的東西 - 它看起來像5  - 

671
00:55:07,720 --> 00:55:13,100
但我們要考慮的事情，我們需要合併左數組是否已用完，

672
00:55:13,100 --> 00:55:16,390
右邊的數組是否已用完的事情，我們需要合併 - 

673
00:55:16,390 --> 00:55:18,400
我指著不惜一切代價。

674
00:55:18,400 --> 00:55:21,730
所以，左數組是否已用完的東西或已用完的東西，右邊的數組。

675
00:55:21,730 --> 00:55:24,320
這兩種情況。

676
00:55:24,320 --> 00:55:30,920
我們還需要瑣碎的情況下，是否在左邊的是不到正確的事情。

677
00:55:30,920 --> 00:55:33,910
然後我們要選擇左側的事情。

678
00:55:33,910 --> 00:55:37,630
這些都是案件。

679
00:55:37,630 --> 00:55:40,990
因此，這是正確的，所以就是這樣。

680
00:55:40,990 --> 00:55:46,760
陣列離開了。它是1，2，3。好吧。所以，是的，這些都是我們可能想要做的四件事。

681
00:55:50,350 --> 00:55:54,510
我們不會在一個迭代的解決方案。

682
00:55:54,510 --> 00:55:55,980
我不會建議 - 

683
00:55:55,980 --> 00:56:03,070
合併排序是一個函數，是不是尾遞歸的例子，

684
00:56:03,070 --> 00:56:07,040
這是不容易的是尾遞歸，

685
00:56:07,040 --> 00:56:13,450
而且它不是很容易，使迭代。

686
00:56:13,450 --> 00:56:16,910
這是很容易的。

687
00:56:16,910 --> 00:56:19,170
此實現歸併排序，

688
00:56:19,170 --> 00:56:22,140
合併，不管你做什麼，你要建立合併。

689
00:56:22,140 --> 00:56:29,170
>> 因此，遞歸排序建立在合併的合併僅僅是這三條線。

690
00:56:29,170 --> 00:56:34,700
迭代，它是更煩人，更難以思考。

691
00:56:34,700 --> 00:56:41,860
但是請注意，這不是尾遞歸，因為mergeSortHelp  - 當它自稱 - 

692
00:56:41,860 --> 00:56:46,590
這個遞歸調用返回後，需要做的事情。

693
00:56:46,590 --> 00:56:50,830
所以這個棧幀必須繼續存在，甚至在調用此函數。

694
00:56:50,830 --> 00:56:54,170
然後當你調用這個堆棧幀必須繼續存在

695
00:56:54,170 --> 00:56:57,780
因為即使在這一號召，我們仍然需要進行合併。

696
00:56:57,780 --> 00:57:01,920
它是平凡的，使該尾遞歸。

697
00:57:04,070 --> 00:57:06,270
有問題嗎？

698
00:57:08,300 --> 00:57:09,860
好的。

699
00:57:09,860 --> 00:57:13,400
所以回到排序 - 哦，有兩件事我想告訴。好吧。

700
00:57:13,400 --> 00:57:17,840
進行排序，我們將盡快這樣做。

701
00:57:17,840 --> 00:57:21,030
或搜索。排序？排序。是啊。

702
00:57:21,030 --> 00:57:22,730
讓我們回到了開始的排序。

703
00:57:22,730 --> 00:57:29,870
我們要創建的數組進行排序的算法，該算法使用任何算法

704
00:57:29,870 --> 00:57:33,660
在O的n。

705
00:57:33,660 --> 00:57:40,860
所以，這怎麼可能呢？有沒有人有任何形式的 - 

706
00:57:40,860 --> 00:57:44,300
我之前在暗示 - 

707
00:57:44,300 --> 00:57:48,300
如果我們要提高n日誌n的n為O，

708
00:57:48,300 --> 00:57:51,450
我們已經改進我們的算法時間上，

709
00:57:51,450 --> 00:57:55,250
這意味著什麼，我們需要做彌補？

710
00:57:55,250 --> 00:57:59,520
[學生]空間。 >>呀。我們將使用更多的空間。

711
00:57:59,520 --> 00:58:04,490
，甚至沒有更多的空間，這是成倍更多的空間。

712
00:58:04,490 --> 00:58:14,320
因此，我認為這種類型的算法是偽的東西，偽多項式 - 

713
00:58:14,320 --> 00:58:18,980
偽 - 我不記得了。假的東西。

714
00:58:18,980 --> 00:58:22,210
但是，這是因為我們需要用這麼大的空間

715
00:58:22,210 --> 00:58:28,610
這是可以實現的，但並不現實。

716
00:58:28,610 --> 00:58:31,220
>> 以及我們如何做到這一點？

717
00:58:31,220 --> 00:58:36,810
我們可以做到這一點，如果我們保證，任何特定的數組中的元素

718
00:58:36,810 --> 00:58:39,600
低於一定的大小。

719
00:58:42,070 --> 00:58:44,500
因此，讓我們說，大小為200，

720
00:58:44,500 --> 00:58:48,130
任何數組中的元素是尺寸200以下。

721
00:58:48,130 --> 00:58:51,080
其實這是很不現實的。

722
00:58:51,080 --> 00:58:58,660
你可以很容易有一個數組，你知道它的一切

723
00:58:58,660 --> 00:59:00,570
是小於一些數字。

724
00:59:00,570 --> 00:59:07,400
就像如果你有一些絕對龐大的向量或東西

725
00:59:07,400 --> 00:59:11,810
但你知道一切都將是0和5之間，

726
00:59:11,810 --> 00:59:14,790
那麼它會更快地做到這一點。

727
00:59:14,790 --> 00:59:17,930
，被綁定的任何元件上是5星，

728
00:59:17,930 --> 00:59:21,980
所以這個界，這是你要多少內存使用。

729
00:59:21,980 --> 00:59:26,300
因此，綁定的是200元。

730
00:59:26,300 --> 00:59:32,960
從理論上講，永遠是綁定的，因為一個整數只能為達至4億美元，

731
00:59:32,960 --> 00:59:40,600
但是這是不切實際的，因為那麼我們就可以使用的空間

732
00:59:40,600 --> 00:59:44,400
4億美元的訂單。所以這是不現實的。

733
00:59:44,400 --> 00:59:47,060
但在這裡我們會說，我們的結合是200元。

734
00:59:47,060 --> 00:59:59,570
在O n個這樣做的竅門是我們另一個數組計數的大小約束。

735
00:59:59,570 --> 01:00:10,470
因此，實際上，這是一條捷徑 - 其實我不知道如果鐺做這個。

736
01:00:11,150 --> 01:00:15,330
但在GCC至少是 - 我是假設鐺它太 - 

737
01:00:15,330 --> 01:00:18,180
這將初始化整個數組是0。

738
01:00:18,180 --> 01:00:25,320
所以，如果我不想這樣做，那麼我可以分別做為（int i = 0;

739
01:00:25,320 --> 01:00:31,500
我的束縛，我+ +）和計數[I] = 0;

740
01:00:31,500 --> 01:00:35,260
所以，現在一切都被初始化為0。

741
01:00:35,260 --> 01:00:39,570
我重申了我的陣列，

742
01:00:39,570 --> 01:00:51,920
我在做什麼是我清點人數的每一個 - 讓我們去這裡。

743
01:00:51,920 --> 01:00:55,480
我們有4，15，16，50，8，23，42，108。

744
01:00:55,480 --> 01:01:00,010
我的計數是在每個這些元素的出現數目。

745
01:01:00,010 --> 01:01:03,470
讓我們添加一對夫婦在這裡有一些重複。

746
01:01:03,470 --> 01:01:11,070
因此，我們的價值的價值，在這裡，將是陣列[i]。

747
01:01:11,070 --> 01:01:14,850
因此，值可能是4或8或什麼的。

748
01:01:14,850 --> 01:01:18,870
而現在，我計算該值多少我已經看到了，

749
01:01:18,870 --> 01:01:21,230
所以計數[值] + +;

750
01:01:21,230 --> 01:01:29,430
做到這一點後，計數看起來像0001。

751
01:01:29,430 --> 01:01:42,190
讓我們做計數[值]  - 約束+ 1。

752
01:01:42,190 --> 01:01:48,230
>> 現在，這只是考慮到這一事實，我們從0開始。

753
01:01:48,230 --> 01:01:50,850
所以，如果200將是我們的最大數量，

754
01:01:50,850 --> 01:01:54,720
0到200是201的東西。

755
01:01:54,720 --> 01:02:01,540
所以，計數，它會看起來像00001，因為我們有一個4。

756
01:02:01,540 --> 01:02:10,210
然後，我們將有0001，我們將有一個在8計數指數。

757
01:02:10,210 --> 01:02:14,560
我們將有一個23指數數2。

758
01:02:14,560 --> 01:02:17,630
我們將有一個42指數數2。

759
01:02:17,630 --> 01:02:21,670
因此，我們可以使用計數。

760
01:02:34,270 --> 01:02:44,920
所以num_of_item =計數[I]。

761
01:02:44,920 --> 01:02:52,540
所以，如果num_of_item為2，這意味著我們要插入2號我

762
01:02:52,540 --> 01:02:55,290
到我們的排序的數組。

763
01:02:55,290 --> 01:03:02,000
因此，我們需要跟踪到數組有多遠，我們是。

764
01:03:02,000 --> 01:03:05,470
所以，索引= 0。

765
01:03:05,470 --> 01:03:09,910
陣列 - 我剛寫出來。

766
01:03:16,660 --> 01:03:18,020
計數 - 

767
01:03:19,990 --> 01:03:28,580
數組[索引+ +] =我;

768
01:03:28,580 --> 01:03:32,490
這是我想要的嗎？我想這就是我想要的。

769
01:03:35,100 --> 01:03:38,290
是的，這看起來不錯。好吧。

770
01:03:38,290 --> 01:03:43,050
因此，每個人都明白我的計數數組的目的是什麼？

771
01:03:43,050 --> 01:03:48,140
每個這些數字的出現的數目進行計數。

772
01:03:48,140 --> 01:03:51,780
然後我遍歷，計數數組，

773
01:03:51,780 --> 01:03:57,190
和第i個位置的計數數組中

774
01:03:57,190 --> 01:04:01,930
我是應該出現在我的排序的數組是多少。

775
01:04:01,930 --> 01:04:06,840
這就是為什麼，4的計數將是1

776
01:04:06,840 --> 01:04:11,840
和8的計數將是1，23的計數為2。

777
01:04:11,840 --> 01:04:16,900
因此，這是多少人，我想我排序的數組插入。

778
01:04:16,900 --> 01:04:19,200
然後，我就這樣做。

779
01:04:19,200 --> 01:04:28,960
我插入num_of_item的，我到我的排序的數組。

780
01:04:28,960 --> 01:04:31,670
>> 有問題嗎？

781
01:04:32,460 --> 01:04:43,100
如此反复，這是線性時間，因為我們都只是這一次迭代，

782
01:04:43,100 --> 01:04:47,470
但它也是在這個數字恰好是線性，

783
01:04:47,470 --> 01:04:50,730
，所以它在很大程度上取決於你所綁定的是什麼。

784
01:04:50,730 --> 01:04:53,290
200綁定，這是沒有那麼糟糕。

785
01:04:53,290 --> 01:04:58,330
如果您的綁定將是10,000，那麼這是有點差，

786
01:04:58,330 --> 01:05:01,360
但如果你所綁定的4億美元，這是完全不現實的

787
01:05:01,360 --> 01:05:07,720
這個數組的大小為4億美元，這是不現實的。

788
01:05:07,720 --> 01:05:10,860
所以，就是這樣。有問題嗎？

789
01:05:10,860 --> 01:05:13,270
[聽不見的學生回應] >>好。

790
01:05:13,270 --> 01:05:15,710
我實現了一個其他的事情時，我們會通過。

791
01:05:17,980 --> 01:05:23,720
我認為這個問題是在盧卡斯和可能，我們已經看到的每一個。

792
01:05:23,720 --> 01:05:26,330
我完全忘了。

793
01:05:26,330 --> 01:05:31,040
我唯一​​想評論的是，當你正在處理的事情，比如指數，

794
01:05:31,040 --> 01:05:38,320
你從來沒有真正看到當你寫一個for循環，

795
01:05:38,320 --> 01:05:41,120
但在技術上，只要你處理這些指數，

796
01:05:41,120 --> 01:05:45,950
你幾乎總是要處理無符號整數。

797
01:05:45,950 --> 01:05:53,850
這樣做的原因是，當你正在處理的有符號整數，

798
01:05:53,850 --> 01:05:56,090
所以，如果你有2個有符號整數和你加在一起

799
01:05:56,090 --> 01:06:00,640
他們最終太大，那麼你最終會用負數。

800
01:06:00,640 --> 01:06:03,410
所以，什麼是整數溢出。

801
01:06:03,410 --> 01:06:10,500
>> 如果我增加2億美元和1億美元，我結束了負1億。

802
01:06:10,500 --> 01:06:15,480
這是整數，如何在電腦上工作。

803
01:06:15,480 --> 01:06:17,510
因此，問題與使用 - 

804
01:06:17,510 --> 01:06:23,500
這是罰款，除非低恰好為2億美元，高達恰好為1億美元，

805
01:06:23,500 --> 01:06:27,120
那麼這將是負1億美元，然後我們要分2

806
01:06:27,120 --> 01:06:29,730
並最終為負500萬元。

807
01:06:29,730 --> 01:06:33,760
因此，這是一個問題，如果你恰巧是通過一個數組

808
01:06:33,760 --> 01:06:38,070
數十億美元的東西。

809
01:06:38,070 --> 01:06:44,050
但是，如果低+上發生溢出，那麼這是一個問題。

810
01:06:44,050 --> 01:06:47,750
只要我們讓他們無符號，然後是2億加1億美元為3億美元。

811
01:06:47,750 --> 01:06:51,960
3億美元，除以2，為1.5億美元。

812
01:06:51,960 --> 01:06:55,670
因此，只要他們是無符號的，一切都是完美的。

813
01:06:55,670 --> 01:06:59,900
因此，這也是一個問題，當你寫你的for循環，

814
01:06:59,900 --> 01:07:03,940
而實際上，它很可能它會自動。

815
01:07:09,130 --> 01:07:12,330
它實際上只是會罵你的。

816
01:07:12,330 --> 01:07:21,610
因此，如果這個數字是太大而僅僅是一個整數，但它適合在一個無符號整數，

817
01:07:21,610 --> 01:07:24,970
它會罵你的，所以這就是為什麼你從來沒有真正遇到的問題。

818
01:07:29,150 --> 01:07:34,820
你可以看到索引是永遠不會是負的，

819
01:07:34,820 --> 01:07:39,220
因此，如果你要遍歷一個數組，

820
01:07:39,220 --> 01:07:43,970
你幾乎總是可以說無符號整型我，但你真的不有。

821
01:07:43,970 --> 01:07:47,110
事情是去上班幾乎一樣好。

822
01:07:48,740 --> 01:07:50,090
好吧。 [竊竊私語]是什麼時候？

823
01:07:50,090 --> 01:07:54,020
最後一件事，我想向大家展示 - 我就這樣做真快。

824
01:07:54,020 --> 01:08:03,190
你知道我們是如何定義，所以我們可以定義MAX 5或東西嗎？

825
01:08:03,190 --> 01:08:05,940
讓我們不要做最大。的綁定為200。這是我們以前所做的。

826
01:08:05,940 --> 01:08:10,380
定義一個常量，它只是要進行複製和粘貼

827
01:08:10,380 --> 01:08:13,010
發生的地方，我們寫的約束。

828
01:08:13,010 --> 01:08:18,189
>> 所以，我們其實可以做更多的＃define。

829
01:08:18,189 --> 01:08:21,170
＃我們可以定義函數。

830
01:08:21,170 --> 01:08:23,410
他們並不是真正的功能，但我們會打電話給他們的功能。

831
01:08:23,410 --> 01:08:36,000
一個例子是類似的東西MAX（X，Y）被定義為（X <Y Y：X）。好吧。

832
01:08:36,000 --> 01:08:40,660
所以，你應該習慣了三元運算符的語法，

833
01:08:40,660 --> 01:08:49,029
但小於y是x？返回y，否則返回x。

834
01:08:49,029 --> 01:08:54,390
所以你可以看到，你可以使之成為一個獨立的功能，

835
01:08:54,390 --> 01:09:01,399
的功能也能像布爾MAX需要兩個參數，返回。

836
01:09:01,399 --> 01:09:08,340
這是一種最常見的喔做這樣的。我們稱他們為宏。

837
01:09:08,340 --> 01:09:11,790
這是一個宏。

838
01:09:11,790 --> 01:09:15,859
這僅僅是它的語法。

839
01:09:15,859 --> 01:09:18,740
做任何你想要的，你可以寫一個宏。

840
01:09:18,740 --> 01:09:22,649
你經常看到的宏用於調試的printfs之類的東西。

841
01:09:22,649 --> 01:09:29,410
因此，一個類型的輸出，有特殊的類似C中的常​​量強調LINE強調，

842
01:09:29,410 --> 01:09:31,710
2強調LINE強調，

843
01:09:31,710 --> 01:09:37,550
還有還有，我認為強調FUNC。這可能是它。類似的東西。

844
01:09:37,550 --> 01:09:40,880
這些東西將被替換的函數名

845
01:09:40,880 --> 01:09:42,930
或你的行的數目。

846
01:09:42,930 --> 01:09:48,630
通常情況下，你下來，然後我可以在這裡只是寫寫調試的printfs，

847
01:09:48,630 --> 01:09:54,260
調試，它會打印的行數和功能，我恰巧在

848
01:09:54,260 --> 01:09:57,020
它遇到，DEBUG聲明。

849
01:09:57,020 --> 01:09:59,550
您還可以打印其他的事情。

850
01:09:59,550 --> 01:10:05,990
這麼一件事，你應該注意的是，如果我發生的DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
像2 * y和2 * X。

852
01:10:11,380 --> 01:10:14,310
因此，無論出於何種原因，你碰巧做了很多。

853
01:10:14,310 --> 01:10:16,650
因此，使它的宏。

854
01:10:16,650 --> 01:10:18,680
這實際上是壞了。

855
01:10:18,680 --> 01:10:23,050
我想請通過做一些像DOUBLE_MAX（3，6）。

856
01:10:23,050 --> 01:10:27,530
那麼應該怎麼回來了？

857
01:10:28,840 --> 01:10:30,580
[學生] 12。

858
01:10:30,580 --> 01:10:34,800
是的，12應該返回，返回12。

859
01:10:34,800 --> 01:10:43,350
3被替換為x，6被替換為y，我們返回2 * 6，這是12。

860
01:10:43,350 --> 01:10:47,710
現在看這個怎麼樣？我們應該回來了嗎？

861
01:10:47,710 --> 01:10:50,330
[學生] 14。 >>理想的情況下，14。

862
01:10:50,330 --> 01:10:55,290
問題是，如何哈希定義的工作，請記住這是一個文字的複製和粘貼

863
01:10:55,290 --> 01:11:00,160
幾乎一切，還等什麼，這是要被理解為

864
01:11:00,160 --> 01:11:11,270
少為3比1加6次，2次加6，2倍，3。

865
01:11:11,270 --> 01:11:19,780
>> 因此，對於這個原因，你幾乎總是包裹在括號中的一切。

866
01:11:22,180 --> 01:11:25,050
你幾乎總是包裹在括號中的任何變量。

867
01:11:25,050 --> 01:11:29,570
在有些情況下，你沒有，就像我不知道我需要做的是在這裡

868
01:11:29,570 --> 01:11:32,110
因為小於的是幾乎總是去上班，

869
01:11:32,110 --> 01:11:34,330
雖然這可能也不是真實的。

870
01:11:34,330 --> 01:11:41,870
如果有什麼可笑的如DOUBLE_MAX（1 == 2），

871
01:11:41,870 --> 01:11:49,760
那麼這將被替換為3小於1等於等於2，

872
01:11:49,760 --> 01:11:53,460
，這樣的話它要小於1，這等於2，

873
01:11:53,460 --> 01:11:55,620
這不是我們想要的。

874
01:11:55,620 --> 01:12:00,730
因此，為了防止任何運算符優先級的問題，

875
01:12:00,730 --> 01:12:02,870
始終包裹在括號中。

876
01:12:03,290 --> 01:12:07,700
好吧。就是這樣，下午5:30。

877
01:12:08,140 --> 01:12:12,470
如果您有任何問題，在pset，讓我們知道。

878
01:12:12,470 --> 01:12:18,010
這應該是有趣的，和黑客版也更為現實

879
01:12:18,010 --> 01:12:22,980
比去年的黑客版，所以我們希望你嘗試了很多。

880
01:12:22,980 --> 01:12:26,460
去年的非常熱烈。

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]