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

35
00:02:18,690 --> 00:02:24,620
Първо, няма кой искам да кажа защо е О N на квадрат?

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
Така че имайте предвид това, което Big O означава и какви големи Омега средства.

40
00:02:41,800 --> 00:02:50,560
The Big O е като горна граница за това как бавно тя действително може да работи.

41
00:02:50,560 --> 00:02:58,990
Така че, като казват, че е O N квадрат, той не е O на N или иначе щеше да бъде в състояние да тече

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

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 на квадрат, и в абсолютно най-лошия случай не може да направи по-добре, отколкото н квадрат,

46
00:03:20,280 --> 00:03:22,830
което е, защо е O N квадрат.

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 елемента, ние ще трябва да се направи N - 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
И трето ще бъде N - 3, а след това за удобство ще напиша последните две

56
00:04:11,640 --> 00:04:15,270
както и тогава ние ще трябва да направят две суапове и 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 н. Това не е само на 3 н.

71
00:05:22,400 --> 00:05:27,650
Той винаги ще бъде N / 2 н.

72
00:05:27,650 --> 00:05:29,430
Така че тук сме се случи да има 6.

73
00:05:29,430 --> 00:05:34,830
Ако имахме 10 неща, тогава бихме могли да направим тази група в продължение на пет различни двойки неща

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 и така че това ще го нахвърлям н квадрат / 2.

76
00:05:45,840 --> 00:05:48,890
И така, въпреки че това е фактор на половина, което се случва, да дойде в

77
00:05:48,890 --> 00:05:54,190
поради факта, че през всяка итерация над масива сравним един по-малко

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
или има за обхождане н неща.

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 дневник н. >> Да.

105
00:07:43,690 --> 00:07:49,990
Най-бързите общи алгоритми за сортиране н н дневник. Не можеш да направиш по-добре.

106
00:07:51,930 --> 00:07:55,130
>> Има специални случаи, и ако имаме време днес, но вероятно won't -

107
00:07:55,130 --> 00:07:59,330
можем да видим този, който прави по-добре от N дневник н.

108
00:07:59,330 --> 00:08:04,050
Но в общия случай, не може да направи по-добре, отколкото N дневник н.

109
00:08:04,050 --> 00:08:09,680
И се сливат вид се случва да бъде този, който трябва да знаете за този курс, който е 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
поради назад R, но ако кликнете върху името ми, ще видите две ревизии.

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
Revision 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
>> Някой иска ли да даде pseudocode високо ниво обяснение

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
[Bowden Да.

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
Сега масив ми е само тези четири елемента, и повтарям.

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
[Bowden Това не съществува в C.

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
И така, как можем да видим, колко памет има? >> Студент Sizeof. >> Да, 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
Защо не мога просто правя тук INT размер = sizeof (купа сено) / 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
[Bowden Haystack съществува и ние сме преминаване в числа като купа сено,

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
и тя ще бъде на размера sizeof (брой).

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
sizeof (купа сено) се връща размера на самия референтен.

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
Просто напишете половината pseudocode за това как смятате, че тя трябва да работи.

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
Така че може да ви спести преразглеждане, като кликнете върху малката икона Save.

239
00:17:27,220 --> 00:17:29,950
Ти си Ramya, нали? >> Студент Да. >> Bowden Добре.

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
актуализиране на края аргумент тук, ние сме актуализиране началото аргумент тук.

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
Аз съм с SearchHelp, така че всеки път, когато правя тази функция повикване

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
А иначе правим края на 1/2.

278
00:20:22,710 --> 00:20:24,740
[Bowden Добре.

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

297
00:21:56,380 --> 00:22:01,740
и 10 призив към SearchHelp трябва да се върне към 9, трябва да се върне до 8-ми.

298
00:22:01,740 --> 00:22:05,360
Така че това не трябва да се случи, когато функции са опашката рекурсивна.

299
00:22:05,360 --> 00:22:13,740
И така, това, което прави тази функция опашката рекурсивен е известие, че за дадена покана да searchHelp

300
00:22:13,740 --> 00:22:18,470
рекурсивно повикване, което прави, е това, което е връщане.

301
00:22:18,470 --> 00:22:25,290
Така в първата покана за SearchHelp, или незабавно да върне невярна,

302
00:22:25,290 --> 00:22:29,590
незабавно да върне вярно, или ние правим рекурсивен призив към SearchHelp

303
00:22:29,590 --> 00:22:33,810
когато Връщаме е това, че се завръща повикване.

304
00:22:33,810 --> 00:22:51,560
И не можем да направим това, ако сме направили нещо като Int X = SearchHelp, връщане х * 2,

305
00:22:51,560 --> 00:22:55,440
просто някаква случайна промяна.

306
00:22:55,440 --> 00:23:01,470
>> Така че сега този рекурсивно повикване, вътр х = SearchHelp рекурсивно повикване,

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, тогава SearchHelp действително ще провери купа сено 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
Така че в момента, началото е този елемент и в края е една отвъд него.

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
[Bowden] Така че това трябва да бъде по-малко? Е, че това, което каза? >> Студент Да.

406
00:32:08,830 --> 00:32:10,390
[Bowden Добре. По-малко.

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 и е една, а след това ниско + нагоре / 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
[Bowden] Или това трябва да бъде една, а другият трябва да бъде + 1.

418
00:33:05,900 --> 00:33:09,580
[Ученик] И трябва да има двоен знак за равенство. >> Bowden Да.

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 и нагоре е едно, и двамата щели да е 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
Ah. Да. >> Студент Да.

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
(купа сено (ниско + Up) / 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
И ние искаме да приложи вид с помощта на всеки алгоритъм в O N дневник н.

463
00:37:12,840 --> 00:37:17,240
Така че, който алгоритъм мислиш ли, че трябва да прилагат тук? >> Студент Merge вид.

464
00:37:17,240 --> 00:37:23,810
[Bowden Да. Обединяване вид е O (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
линейното време смисъл, ако този масив е размер х и това е размер г.,

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 и след това тук сте на две.

489
00:39:30,150 --> 00:39:33,320
Така че това е нещо като имате раздел, който се движи надясно. >> Bowden Да.

490
00:39:33,320 --> 00:39:41,070
За двете тези масиви, ако ние просто се съсредоточи върху най-лявата елемент.

491
00:39:41,070 --> 00:39:43,530
Тъй като двата масива са подредени, ние знаем, че тези два елемента

492
00:39:43,530 --> 00:39:46,920
са най-малките елементи в двата масива.

493
00:39:46,920 --> 00:39:53,500
Така че това означава, че една от тези два елемента трябва да бъде най-малкият елемент в обединената ни масив.

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. Това ще обнови, да сравните тези два, три.

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
Обединяване сортирате след това на базата на това, че е две стъпки, два глупави стъпки.

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
Така че, за да се види, че това е като цяло N дневник N, ние вече видяхме, че сливането е линейна,

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

555
00:46:08,060 --> 00:46:10,810
И тогава едно и също нещо тук.

556
00:46:10,810 --> 00:46:16,980
Ще се слеят тези две, след това тези две, и индивидуално това сливане ще отнеме четири операции,

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
Така че, тъй като тя се удвоява, там ще да бъде общо на дневника N от тези нива.

565
00:46:56,450 --> 00:47:02,090
Така че с дневника н нива, всяко ниво, като 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
Просто буквално се обадя вид на лявата половина, нещо от дясната половина. Добре.

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
[Bowden Добре, така че ми даде втори.

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? >> Bowden Да.

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
така че ние може просто да се каже, размер по-малко от два или по-малко или равно на 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
[Bowden] О, Размерът / 2, Размерът / 2. >> [Ученик] Да, а също и по-горе функция, както и.

647
00:53:16,210 --> 00:53:21,320
[Bowden] тук? >> [Ученик] Само размер. >> Bowden О Размер размер? >> Студент Да.

648
00:53:21,320 --> 00:53:23,010
[Bowden Добре.

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
[Bowden Добре. Харесва ми, че по-добре.

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
[Bowden Добре.

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
Array напусна. Това е 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
И това е nontrivial да направи тази опашка рекурсивно.

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
Ако сме на път да подобри от дневник н н О N,

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
[Ученик] Space. >> Да. Отиваме да се използва от повече пространство.

711
00:57:59,520 --> 00:58:04,490
И дори не само повече пространство, това е експоненциално по-голямо пространство.

712
00:58:04,490 --> 00:58:14,320
Така че аз мисля, че този вид алгоритъм е псевдо нещо, псевдо polynom

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
Но в GCC най-малкото - Аз съм предположи звъня го прави -

737
01:00:15,330 --> 01:00:18,180
това просто ще се инициализира целия масив да бъде 0s.

738
01:00:18,180 --> 01:00:25,320
Така че, ако не искате да направите това, тогава бих могъл отделно направя за (INT I = 0;

739
01:00:25,320 --> 01:00:31,500
I <вързан, 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
Така че се брои, тя ще изглежда като 00 001, защото имаме един 4.

756
01:02:01,540 --> 01:02:10,210
Тогава ще имаме 0001, където ще имаме 1 в 8-ия индекс на брой.

757
01:02:10,210 --> 01:02:14,560
Ще имаме два в 23-та индекс на брой.

758
01:02:14,560 --> 01:02:17,630
Ще имаме две в индекса на 42-рата брой.

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
Array - аз просто ще го напиша.

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
ItH позиция в масив на графовете

774
01:03:57,190 --> 01:04:01,930
е броят на е, че трябва да се появи в сортират масив.

775
01:04:01,930 --> 01:04:06,840
Ето защо броя на 4 ще бъде едно

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
никога не видите това, когато пишете за цикъл,

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
така че ако имате два подписани числа и да ги съберем

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 000 000.

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 милиарда евро, разделен на две, е 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
почти винаги може да се каже, грозен Int аз, но вие наистина не трябва да.

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
Нека не правим MAX. # Определят обвързана като 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
Един пример ще бъде нещо като MAX (X, Y) се дефинира като (X <Y Y: х). Добре.

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
и функция може да бъде като булев MAX 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
Често макроси за отстраняване на грешки 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 * х.

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 се замества за х 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
е три по-малко от 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
Ако има нещо нелепо като DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
това ще се заменя с три по-малко от 1 равен, е равно на 2,

872
01:11:49,760 --> 01:11:53,460
и така то тогава ще да направя три по-малко от 1, не които са равни на две

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]