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]