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
>> [Ово је ЦС50. - ЦС50.ТВ]

4
00:00:07,310 --> 00:00:12,700
>> Дакле, прво питање је чудно срочена.

5
00:00:12,700 --> 00:00:17,480
ГДБ вам омогућава да "дебуг" програм, али, конкретно, шта то да радиш?

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
Зашто је мехур врста у О од н квадрата?

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
>> Зашто је О н квадрат?

35
00:02:18,690 --> 00:02:24,620
Прво, да ли неко жели да каже зашто је то О н квадрат?

36
00:02:24,620 --> 00:02:28,760
[Ученик] Јер за сваку стазе иде н пута.

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
Зато имајте на уму шта велики О значи и шта значи велике Омега.

40
00:02:41,800 --> 00:02:50,560
Велики О је као горња граница колико споро заправо може да се покрене.

41
00:02:50,560 --> 00:02:58,990
Дакле, рекавши да је О од н квадрата, није О н иначе би било у стању да покрене

42
00:02:58,990 --> 00:03:02,640
у линеарном времену, али то је О од н куб

43
00:03:02,640 --> 00:03:06,390
јер је омеђена О н куб.

44
00:03:06,390 --> 00:03:12,300
Ако је омеђена О од н квадрат, онда је такође ограничен н куб.

45
00:03:12,300 --> 00:03:20,280
Тако да је н квадрат, а у апсолутном најгорем случају то не може да уради боље од н квадрата,

46
00:03:20,280 --> 00:03:22,830
због чега је о н квадрат.

47
00:03:22,830 --> 00:03:31,200
Дакле, да видимо мало математике како излази да је н квадрат,

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
[Ученик] н - 1. >> Да.

52
00:03:53,540 --> 00:03:58,340
>> Ако постоји 5 елемената, ми ћемо морати да се н - 1.

53
00:03:58,340 --> 00:04:01,100
Затим на другој колико свопови ћемо морати да направи?

54
00:04:01,100 --> 00:04:03,440
[Ученик] н - 2. >> Да.

55
00:04:03,440 --> 00:04:11,640
И трећи ће бити н - 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
Дакле, постоје н - 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 н а. То није само 3 н а.

71
00:05:22,400 --> 00:05:27,650
Увек ће бити н / 2 н а.

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
и завршити са н + н + н + н + н.

75
00:05:37,180 --> 00:05:45,840
Дакле, увек ћете добити н / 2 н-их, па то ћемо га Ситница до н квадрат / 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, али се још увек н квадрат.

79
00:05:58,040 --> 00:06:01,650
Ми не бринемо о сталном фактор пола.

80
00:06:01,650 --> 00:06:07,760
Дакле, много великих ствари О овако ослања само на врсте раде овакве математике,

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
Зашто је убацивање врста омега од н? Шта омега значи?

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
без обзира на списку који је усвојен у, она увек мора да се упореди најмање н ствари

89
00:06:41,810 --> 00:06:44,620
или мора да прелазили преко н ствари.

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
Дакле, доња граница за уметање врсте је Омега н.

101
00:07:25,290 --> 00:07:28,210
Шта најгори случај покренут време стапања врсте,

102
00:07:28,210 --> 00:07:31,390
најгорем случају биће опет велики О?

103
00:07:31,390 --> 00:07:37,660
Дакле, у најгорем сценарију, како обједињавање некако покренем?

104
00:07:42,170 --> 00:07:43,690
[Ученик] Н лог н. >> Да.

105
00:07:43,690 --> 00:07:49,990
Најбрже опште сортирање алгоритми су н лог н. Ви не можете урадити боље.

106
00:07:51,930 --> 00:07:55,130
>> Постоје посебни случајеви, и ако имамо времена данас - али ћемо вероватно вон'т -

107
00:07:55,130 --> 00:07:59,330
смо могли видети један који ради боље од н лог н.

108
00:07:59,330 --> 00:08:04,050
Али, у општем случају, не можете да урадите боље од н лог н.

109
00:08:04,050 --> 00:08:09,680
И обједињавање некако деси да буде једна треба да знате за овај курс који је н лог н.

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
>> То неминовно појављују у облику морате да попуните када подношења псет.

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
због уназад р - али ако кликнете на моје име видећете 2 ревизије.

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
А Ревизија 2 ће бити нека ствар коју можемо имплементирати након тога.

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
[Бовден] То не постоји у Ц.

173
00:12:36,600 --> 00:12:38,580
Потребна дужина..

174
00:12:38,580 --> 00:12:42,010
Низови немају својства, тако да не постоји дужина власништво низова

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
Дакле, како можемо видети колико меморије има? >> [Ученик] сизеоф. >> Да, сизеоф.

178
00:12:55,810 --> 00:13:01,680
Сизеоф је оператор који ће вратити величину низа бројева.

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
Зашто не могу да урадим сам овде инт сизе = сизеоф (пласт) / сизеоф (инт)?

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
јер у Ц, ми немамо појма шта је величина низа се.

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
Ти си Рамиа, зар не? >> [Ученик] Да. >> [Боуден] Ок.

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
Тако Рамиа отишао са Рекурзив решење, што је свакако важи решење.

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
вршимо ажурирање овде крај аргумент, ми овде ажурирање почетну тезу.

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
Дакле, ако направите 1.000 рекурзивног позива, добићете 1.000 стек оквире,

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
и то би, ја мислим - у кланг ако прође то тхе-О2 заставе

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
где се некада вратите тачно, онда то мора да се врати до свих ових рамова стека

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
Дакле, у првом позиву СеарцхХелп, одмах смо се врате лажна,

302
00:22:25,290 --> 00:22:29,590
одмах врати истина, или ћемо направити рекурзивно позив СеарцхХелп

303
00:22:29,590 --> 00:22:33,810
где оно што ми враћа оно што тај позив се враћа.

304
00:22:33,810 --> 00:22:51,560
И нисмо могли да урадите ако смо урадили нешто слично инт к = СеарцхХелп, повратка к * 2,

305
00:22:51,560 --> 00:22:55,440
само неки случајни промена.

306
00:22:55,440 --> 00:23:01,470
>> Дакле, сада ово рекурзивног позива, ова инт к = СеарцхХелп рекурзивни позив,

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
Али већ смо се вратили лажна и заправо никада не проверава вредност.

319
00:24:07,890 --> 00:24:14,240
Дакле, у најмању руку, у првом позиву, ако је величина 0, онда желимо да се врати фалсе.

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
онда можемо одмах да врати истина.

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
тако да смо проверу 5, и рецимо да је вредност мања.

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
Дакле тренутно почетак је тај елемент и крај је 1 ван њега.

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
онда нисмо га пронађе и ми можемо вратити лажна.

388
00:30:29,020 --> 00:30:37,540
Па како то да урадим? Свако имате предлоге или код за мене вуку горе?

389
00:30:42,190 --> 00:30:47,450
[Ученик] До петљу док. >> Да.

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
Али, ако су они једнаки, онда не би урадио док петљу да се почне са

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
Ако то је -

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] == игла), онда можемо вратити истина.

447
00:35:44,810 --> 00:35:52,070
А да ли сам ставио друго или само ако то значи буквално исту ствар

448
00:35:52,070 --> 00:35:57,110
јер би то вратило истина.

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
И ми желимо да се спроведе врсту Коришћењем било ког алгоритма за Ø н лог н.

463
00:37:12,840 --> 00:37:17,240
Дакле, који алгоритам мислиш да би требало да спроведе? >> [Ученик] Обједињавање врста.

464
00:37:17,240 --> 00:37:23,810
[Боуден] Да. Обједињавање врста је О (н лог н), тако да је оно што ћемо да радимо.

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
линеарно време значи ако је низ је величина к и то је величина и

485
00:39:13,510 --> 00:39:20,970
онда укупна алгоритам треба да буде О (к + и). Ок.

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
То значи да мора да 1 од тих 2 елемената бити најмањи елемент у нашој обједињеном низу.

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
онда смо ажурирали овај показивач, ово ће бити мањи, ажурирате ово,

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
Дакле, сада смо у овом тренутку, сада корак два стапања врсте је само спајање парова на листи.

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
Тако да се види да је ово општи н лог н, ми смо већ видели да Стапање је линеарно,

548
00:45:34,030 --> 00:45:40,390
па кад се бавимо овим спајањем, па као укупну цену стапања

549
00:45:40,390 --> 00:45:43,410
за ове две листе је само 2 јер -

550
00:45:43,410 --> 00:45:49,610
Или добро, то је О н, али н овде је само ова 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, који је н

554
00:46:03,210 --> 00:46:08,060
тако трошкова спајања у овом сету је Н.

555
00:46:08,060 --> 00:46:10,810
А онда је иста ствар овде.

556
00:46:10,810 --> 00:46:16,980
Ми ћемо спојити ове 2, онда оне 2, а појединачно ово стапање ће бити четири операције,

557
00:46:16,980 --> 00:46:23,610
ово стапање ће бити четири операције, али опет, између свих њих,

558
00:46:23,610 --> 00:46:29,030
завршимо спајање н укупна ствари, па овај корак траје н.

559
00:46:29,030 --> 00:46:33,670
И тако сваки ниво има н елемената које су стопљене.

560
00:46:33,670 --> 00:46:36,110
>> А колико нивоа има?

561
00:46:36,110 --> 00:46:40,160
На сваком нивоу, наш низ расте по величини 2.

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
Дакле, пошто је удвостручење, постоје ће бити укупно лог н од тих нивоа.

565
00:46:56,450 --> 00:47:02,090
Тако је и са лог н нивоа, сваки појединац ниво узимајући н укупног пословања,

566
00:47:02,090 --> 00:47:05,720
добијамо н лог н алгоритам.

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
Ви буквално само позовите врсте на левој половини, некако на десној половини. Ок.

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
Тако некако сам је само зове мергеСортХелп.

592
00:48:47,080 --> 00:48:49,530
Објасните нам шта мергеСортХелп ради.

593
00:48:49,530 --> 00:48:55,700
[Ученик] МергеСортХелп прилично кошта два главна корака,

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
Сортирање зове мергеСортХелп.

618
00:50:43,040 --> 00:50:47,390
>> Тако да би некако да позове мергеСортХелп, мергеСортХелп мора или су дефинисани

619
00:50:47,390 --> 00:50:56,370
пре врсти или ћемо само треба прототип. Само копирајте и налепите то.

620
00:50:56,370 --> 00:50:59,490
Слично томе, мергеСортХелп зове се споје,

621
00:50:59,490 --> 00:51:03,830
али стапања још није дефинисан, тако да можемо само да нека знају мергеСортХелп

622
00:51:03,830 --> 00:51:08,700
да то је оно споји ће изгледати, и то је то.

623
00:51:09,950 --> 00:51:15,730
Тако мергеСортХелп.

624
00:51:22,770 --> 00:51:32,660
Имамо проблем овде где немамо базу случај.

625
00:51:32,660 --> 00:51:38,110
МергеСортХелп је рекурзивна, тако да је свака рекурзивна функција

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
[Ученик] Морам да се пролази величину са свим мергеСортХелп позиве.

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
ок, то мора да буде у добром низу, а ми ћемо ставити у садашњем индекса невАрраи.

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
Дакле, четири случаја које имамо да би ствари у само бити - или изгледа пет -

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
Али приметите да то није реп рекурзивна јер мергеСортХелп - када она сама зове -

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
у О од н.

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
Ако ћемо ускоро да се побољша од н лог н до Ø н,

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
Трик да раде у О од н је правимо још низ назива тачака величине ОБАВЕЗАНИ.

735
00:59:59,570 --> 01:00:10,470
Дакле стварно, ово је пречица за - Ја стварно не знам да ли кланг ради.

736
01:00:11,150 --> 01:00:15,330
Али у ГЦЦ на најмању руку - Ја сам под претпоставком кланг то ради превише -

737
01:00:15,330 --> 01:00:18,180
ово ће само покрене читав низ буде 0с.

738
01:00:18,180 --> 01:00:25,320
Дакле, ако ја не желим да то урадим, онда сам могао да урадим одвојено фор (инт и = 0;

739
01:00:25,320 --> 01:00:31,500
и <повезано; и + +) и тачке [и] = 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
Дакле, вредност имамо овде, вредност која ће бити низ [и].

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, где ћемо имати 1 у 8. индекс рачунати.

757
01:02:10,210 --> 01:02:14,560
Ми ћемо имати 2 у 23. индекса рачунати.

758
01:02:14,560 --> 01:02:17,630
Ми ћемо имати 2 у 42. индекса рачунати.

759
01:02:17,630 --> 01:02:21,670
Дакле, можемо да користимо бројање.

760
01:02:34,270 --> 01:02:44,920
Дакле нум_оф_итем = рачуна [и].

761
01:02:44,920 --> 01:02:52,540
И тако, ако нум_оф_итем је 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
и тој позицији у низу тачкама

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
Ја сам убацивања нум_оф_итем је у мојој сортираном низу.

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
ти стварно никад видети када пишете за петље,

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
И то је такође проблем када пишете ваш за петље,

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
Знате како смо дефинисали смо # # како бисмо може дефинисати као МАКС 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
>> Дакле, ми заправо можемо урадити више са # дефинише.

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
Пример би био нешто попут МАКС (к, и) је дефинисана као (к <и и: к). Ок.

832
01:08:36,000 --> 01:08:40,660
Тако да би требало да се навикнете на синтакси тернарном оператера,

833
01:08:40,660 --> 01:08:49,029
али је к мање од и? Повратак и, ретурн к.

834
01:08:49,029 --> 01:08:54,390
Дакле, можете видети можете направити ову посебну функцију,

835
01:08:54,390 --> 01:09:01,399
и функција може бити као воид МАКС траје 2 аргументе, вратите.

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
Ви често видети макрое за отклањање грешака принтфс и остало.

841
01:09:22,649 --> 01:09:29,410
Дакле, типа инт, постоје посебни константе у Ц као наглашавају ЛИНЕ подвучем

842
01:09:29,410 --> 01:09:31,710
2 подвлачи ЛИНЕ подвучем

843
01:09:31,710 --> 01:09:37,550
и ту је ја мислим 2 наглашава ФУНЦ. То би могло да буде. Нешто слично.

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
Често пишете отклањање грешака принтфс да овде сам тада могао само пишем

847
01:09:48,630 --> 01:09:54,260
ДЕБУГ и она ће штампати број линије и функције које сам се деси да буде у

848
01:09:54,260 --> 01:09:57,020
да је наишао на ту изјаву отклањање грешака.

849
01:09:57,020 --> 01:09:59,550
А такође можете да одштампате и друге ствари.

850
01:09:59,550 --> 01:10:05,990
Дакле, једна ствар коју треба да пазиш је ако се деси да # дефине ДОУБЛЕ_МАКС

851
01:10:05,990 --> 01:10:11,380
као нешто налик 2 * и и 2 * к.

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
Ја бих то назвао радећи нешто ДОУБЛЕ_МАКС (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 добија заменио за к, 6 бива замењен за и, а ми смо се вратили 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 пута 1 плус 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
Ако постоји нешто смешно као ДОУБЛЕ_МАКС (1 == 2),

871
01:11:41,870 --> 01:11:49,760
онда ће да се замени са 3 мање од 1 једнак једнак 2,

872
01:11:49,760 --> 01:11:53,460
па онда ће то урадити 3 мањи од 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
Ако имате било каквих питања у вези са псет, обавестите нас.

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
>> [ЦС50.ТВ]