1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Oddiel 3 - Ďalšie Komfortné]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [To je CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Takže prvá otázka je podivne znie.

5
00:00:12,700 --> 00:00:17,480
GDB umožňuje "ladiť" program, ale konkrétne, čo to nechať urobiť?

6
00:00:17,480 --> 00:00:22,590
Budem odpovedať, že jeden, a ja neviem, čo to presne očakáva,

7
00:00:22,590 --> 00:00:27,910
takže hádam, že je to niečo v duchu to umožňuje krok za krokom

8
00:00:27,910 --> 00:00:31,540
prejsť programu, pracovať s ním, zmena premenných, robiť všetky tieto veci -

9
00:00:31,540 --> 00:00:34,270
v podstate kompletne ovládať realizáciu programu

10
00:00:34,270 --> 00:00:38,410
a skontrolujte, či na danej časti realizácie programu.

11
00:00:38,410 --> 00:00:43,030
Takže tieto funkcie vám umožní ladiť veci.

12
00:00:43,030 --> 00:00:44,830
Dobre.

13
00:00:44,830 --> 00:00:50,520
Prečo binárne hľadanie vyžaduje, aby poľa byť zoradené?

14
00:00:50,520 --> 00:00:53,360
Kto chce odpovedať, že?

15
00:00:56,120 --> 00:01:00,070
[Študent] Vzhľadom k tomu, že nefunguje, pokiaľ to nie je zoradená. Jo >>. [Smiech]

16
00:01:00,070 --> 00:01:04,910
Ak to nie je zoradená, potom je to možné rozdeliť na dve polovice

17
00:01:04,910 --> 00:01:07,850
a viem, že všetko na ľavej strane je menší a všetko vpravo

18
00:01:07,850 --> 00:01:10,490
je väčšia, ako je stredná hodnota.

19
00:01:10,490 --> 00:01:12,790
Tak to musí byť zoradené.

20
00:01:12,790 --> 00:01:14,170
Dobre.

21
00:01:14,170 --> 00:01:17,570
Prečo je bublina triediť O n na druhú?

22
00:01:17,570 --> 00:01:23,230
Má niekto najprv chcieť dať veľmi rýchlo na vysokej úrovni prehľad o tom, čo bublina druh je?

23
00:01:25,950 --> 00:01:33,020
[Študent] Tie v podstate prejsť každý prvok a dáte zistiť niekoľko prvých prvkov.

24
00:01:33,020 --> 00:01:37,150
Ak sú z miesta, kde ste ich swap, potom skontrolovať niekoľko ďalších prvkov, a tak ďalej.

25
00:01:37,150 --> 00:01:40,770
Keď sa dostanete na koniec, potom viete, že najväčší prvok je umiestnený na konci,

26
00:01:40,770 --> 00:01:42,750
takže budete ignorovať, že jeden potom pokračovať ďalej cez,

27
00:01:42,750 --> 00:01:48,490
a zakaždým, keď budete musieť skontrolovať jeden menej prvok, kým nevykonáte žiadne zmeny. Jo >>.

28
00:01:48,490 --> 00:01:58,470
Je to tzv bubble sort, pretože ak otočíte poľa na jeho strane, takže je to hore a dole, vertikálne,

29
00:01:58,470 --> 00:02:03,100
potom veľké hodnoty budú klesať ku dnu a malé hodnoty budú bublina až na vrchol.

30
00:02:03,100 --> 00:02:05,210
To je, ako to dostalo jeho meno.

31
00:02:05,210 --> 00:02:08,220
A jo, stačí prejsť.

32
00:02:08,220 --> 00:02:11,190
Stále ide cez pole, vymieňať väčšiu hodnotu

33
00:02:11,190 --> 00:02:14,040
získať najväčšie hodnoty na dno.

34
00:02:14,040 --> 00:02:17,500
>> Prečo je to O n na druhú?

35
00:02:18,690 --> 00:02:24,620
Po prvé, niekto chce povedať, prečo je to O n na druhú?

36
00:02:24,620 --> 00:02:28,760
[Študent] Pretože pre každý beh ide n krát.

37
00:02:28,760 --> 00:02:32,100
Môžete byť istí, že ste si vzal Najsilnejším prvkom celú cestu dole,

38
00:02:32,100 --> 00:02:35,230
potom sa budete musieť zopakovať, že tak veľa prvkov. Jo >>.

39
00:02:35,230 --> 00:02:41,800
Takže majte na pamäti to, čo veľké O znamená a aké veľké Omega znamená.

40
00:02:41,800 --> 00:02:50,560
Veľký O je ako hornú hranicu o tom, ako pomaly to môže skutočne spustiť.

41
00:02:50,560 --> 00:02:58,990
Takže tým, že hovorí, že je to O n štvorčekový, to nie je O n inak by byť schopný spustiť

42
00:02:58,990 --> 00:03:02,640
v lineárnom čase, ale je to O z n kocky

43
00:03:02,640 --> 00:03:06,390
pretože to je ohraničené O n kocky.

44
00:03:06,390 --> 00:03:12,300
Ak je to ohraničené O n štvorcový, potom je to ohraničené aj n kocky.

45
00:03:12,300 --> 00:03:20,280
Takže je n na druhú, a v absolútnom najhoršom prípade nemožno lepšie ako n štvorcový,

46
00:03:20,280 --> 00:03:22,830
čo je dôvod, prečo je O z n na druhú.

47
00:03:22,830 --> 00:03:31,200
Takže vidieť mierny matematiku na to, ako vyjde von, aby sa n na druhú,

48
00:03:31,200 --> 00:03:40,530
ak budeme mať päť vecí v našom zozname, prvýkrát, koľko swapy by sme mohli potenciálne potrebné, aby

49
00:03:40,530 --> 00:03:47,170
aby sa to? Poďme vlastne len -

50
00:03:47,170 --> 00:03:52,040
Koľko swapy budeme musieť urobiť v prvom behu bublín radiť cez pole?

51
00:03:52,040 --> 00:03:53,540
[Študent] n - 1. Jo >>.

52
00:03:53,540 --> 00:03:58,340
>> Ak sú 5 prvkov, budeme musieť vykonať n - 1.

53
00:03:58,340 --> 00:04:01,100
Potom na druhom koľko swapy budeme musieť urobiť?

54
00:04:01,100 --> 00:04:03,440
[Študent] n - 2. Jo >>.

55
00:04:03,440 --> 00:04:11,640
A tretí bude n - 3, a potom pre pohodlie budem písať posledné dva

56
00:04:11,640 --> 00:04:15,270
ako potom budeme potrebovať, aby sa 2 swapy a 1 swap.

57
00:04:15,270 --> 00:04:19,899
Myslím, že posledný človek môže alebo nemusí v skutočnosti sa muselo stať.

58
00:04:19,899 --> 00:04:22,820
Je to výmena? Neviem.

59
00:04:22,820 --> 00:04:26,490
Takže sa jedná o celkové množstvo swapov alebo aspoň porovnaní budete musieť urobiť.

60
00:04:26,490 --> 00:04:29,910
Aj keď nechcete vymeniť, budete ešte potrebovať na porovnanie hodnôt.

61
00:04:29,910 --> 00:04:33,910
Tak sú n - 1 porovnanie v prvom prejdení poľa.

62
00:04:33,910 --> 00:04:42,050
Ak usporiadanie týchto vecí, poďme vlastne robiť to šesť vecí, takže to vyrovnať pekne,

63
00:04:42,050 --> 00:04:44,790
a potom budem robiť 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Takže len preskupiť tieto sumy, chceme vidieť, koľko porovnaní robíme

65
00:04:49,910 --> 00:04:52,700
v celom algoritmu.

66
00:04:52,700 --> 00:04:56,550
Takže ak vám prinášame tie chlapov tu,

67
00:04:56,550 --> 00:05:07,470
potom sme stále len súčet však veľa porovnaní existovali.

68
00:05:07,470 --> 00:05:13,280
Ale ak sčítame tieto a sčítame tieto a sčítame tieto,

69
00:05:13,280 --> 00:05:18,130
je to stále rovnaký problém. Práve sme zhrnúť tieto konkrétne skupiny.

70
00:05:18,130 --> 00:05:22,400
>> Takže teraz sa budeme sčítavať 3 n Nie je to len 3 n

71
00:05:22,400 --> 00:05:27,650
Je to vždy bude n / 2 n

72
00:05:27,650 --> 00:05:29,430
Takže tu máme náhodou 6.

73
00:05:29,430 --> 00:05:34,830
Ak sme mali 10 vecí, potom by sme mohli urobiť túto združenia pre 5 rôznych párov vecí

74
00:05:34,830 --> 00:05:37,180
a skončiť s n + n + n + n + n

75
00:05:37,180 --> 00:05:45,840
Takže ste vždy dostane n / 2 n je, a tak to budeme zapisovať to k n na druhú / 2.

76
00:05:45,840 --> 00:05:48,890
A tak aj keď je to faktor polovice, ktorý sa stane ďalej

77
00:05:48,890 --> 00:05:54,190
vzhľadom k tomu, že po každej iterácii cez pole porovnáme 1 menej

78
00:05:54,190 --> 00:05:58,040
tak to je, ako sa dostaneme cez 2, ale to je ešte n na druhú.

79
00:05:58,040 --> 00:06:01,650
My sa nestaráme o konštantný faktor o polovicu.

80
00:06:01,650 --> 00:06:07,760
Takže veľa veľké veci O takhle spolieha len na druhu robiť tento druh matematiky,

81
00:06:07,760 --> 00:06:12,260
robiť aritmetické súčty a geometrické rady ďalšie veci,

82
00:06:12,260 --> 00:06:17,750
ale väčšina z nich v tomto kurze sú celkom jasné.

83
00:06:17,750 --> 00:06:19,290
Dobre.

84
00:06:19,290 --> 00:06:24,430
Prečo je vloženie triediť Omega n? Čo omega znamená?

85
00:06:24,430 --> 00:06:27,730
[Dva študenti hovoria naraz - nezrozumiteľné] >> Jo.

86
00:06:27,730 --> 00:06:30,630
Omega si môžete myslieť, ako dolná hranica.

87
00:06:30,630 --> 00:06:36,550
>> Takže bez ohľadu na to, ako efektívne váš vloženie sort je algoritmus,

88
00:06:36,550 --> 00:06:41,810
bez ohľadu na zozname, ktorý je odovzdaný do, vždy musí porovnať aspoň n veci

89
00:06:41,810 --> 00:06:44,620
alebo to má pre iteráciu n vecí.

90
00:06:44,620 --> 00:06:47,280
Prečo je to?

91
00:06:47,280 --> 00:06:51,190
[Študent] Pretože ak je zoznam už je zoradený, potom cez prvú iteráciu

92
00:06:51,190 --> 00:06:54,080
môžete iba zaručiť, že úplne prvý element je najmenej,

93
00:06:54,080 --> 00:06:56,490
a druhá iterácia možné iba zaručiť prvé dva sú

94
00:06:56,490 --> 00:07:00,010
pretože neviete, že zvyšok zoznamu zoradené. Jo >>.

95
00:07:00,010 --> 00:07:08,910
Ak predáte v úplne zoradený zoznam, prinajmenšom budete musieť ísť cez všetky prvky

96
00:07:08,910 --> 00:07:12,180
vidieť, že nemusí nič pohyboval.

97
00:07:12,180 --> 00:07:14,720
Takže prechádzajúcej cez zoznam a povedal oh, je to už sú zoradené,

98
00:07:14,720 --> 00:07:18,240
to je nemožné, aby ste vedeli, že to sú zoradené kým zistiť každý prvok

99
00:07:18,240 --> 00:07:20,660
vidieť, že sú v zoradené poradí.

100
00:07:20,660 --> 00:07:25,290
Tak dolná hranica vloženie radiť je Omega n

101
00:07:25,290 --> 00:07:28,210
Čo je najhoršie doba chodu druhu korešpondencie,

102
00:07:28,210 --> 00:07:31,390
Najhorší prípad je veľké O znova?

103
00:07:31,390 --> 00:07:37,660
Takže v najhoršom prípade, ako sa zlúčenie sort beží?

104
00:07:42,170 --> 00:07:43,690
[Študent] N log n Jo >>.

105
00:07:43,690 --> 00:07:49,990
Najrýchlejší všeobecné triedenie algoritmy sú n log n Môžete to urobiť lepšie.

106
00:07:51,930 --> 00:07:55,130
>> Existujú špeciálne prípady, a ak budeme mať čas dnes - ale asi won't -

107
00:07:55,130 --> 00:07:59,330
sme mohli vidieť ten, ktorý robí lepšie ako n log n

108
00:07:59,330 --> 00:08:04,050
Ale vo všeobecnom prípade, nemôžete urobiť lepšie, než n log n

109
00:08:04,050 --> 00:08:09,680
A zlúčiť druh sa stane, že ten, čo by ste mali vedieť o tomto kurze, ktorý je n log n

110
00:08:09,680 --> 00:08:13,260
A tak budeme skutočne vykonávania uvedenej dnes.

111
00:08:13,260 --> 00:08:18,070
A konečne, v nie viac ako tri vety, ako sa výber radenie prácu?

112
00:08:18,070 --> 00:08:20,370
Má niekto bude chcieť odpovedať, a ja počítať svoje vety

113
00:08:20,370 --> 00:08:22,390
pretože ak pôjdete cez 3 -

114
00:08:25,530 --> 00:08:28,330
Pamätá si niekto, výber druhu?

115
00:08:31,280 --> 00:08:37,809
Výber radenie je obvykle docela ľahké si pamätať len z názvu.

116
00:08:37,809 --> 00:08:45,350
Stačí určiť iteráciou cez pole, nájsť, čo najväčšia hodnota alebo najmenší -

117
00:08:45,350 --> 00:08:47,290
bez ohľadu na poradie, ktoré ste triedenie palcov

118
00:08:47,290 --> 00:08:50,750
Takže povedzme, že sme triedenie od najmenšej k najväčšej.

119
00:08:50,750 --> 00:08:55,250
Môžete určiť iteráciou cez pole, hľadá čokoľvek minimálny prvok,

120
00:08:55,250 --> 00:08:59,750
vyberte ju, a potom už len vymeniť to, čo je na prvom mieste.

121
00:08:59,750 --> 00:09:04,090
A potom na druhom priechodu cez pole, pozrite sa na minimálny prvok znovu,

122
00:09:04,090 --> 00:09:07,490
vyberte ju a potom si vymieňať s tým, čo je na druhej pozícii.

123
00:09:07,490 --> 00:09:10,650
Takže sme len zber a výber minimálne hodnoty

124
00:09:10,650 --> 00:09:16,050
a vložením do prednej časti poľa, kým sa triedi.

125
00:09:19,210 --> 00:09:21,560
Otázky týkajúce sa, že?

126
00:09:21,560 --> 00:09:25,710
>> Tie nevyhnutne objaví vo formulároch musíte vyplniť, keď ste podanie PSet.

127
00:09:29,010 --> 00:09:32,360
Tí sú v podstate odpovede na tie.

128
00:09:32,360 --> 00:09:34,230
Dobre, takže teraz kódovanie problémy.

129
00:09:34,230 --> 00:09:40,140
Už som rozoslal cez e-mail - Bolo niekto nedostal tento e-mail? Dobre.

130
00:09:40,140 --> 00:09:46,630
Už som rozoslal cez e-mail na miesto, ktoré sme bude používať,

131
00:09:46,630 --> 00:09:52,120
a ak kliknete na moje meno - takže myslím, že budem na dne

132
00:09:52,120 --> 00:09:57,170
z dôvodu spätnej r - ale ak kliknete na moje meno uvidíte 2 revízie.

133
00:09:57,170 --> 00:10:02,650
Revízia 1 sa bude už som skopírovať a vložiť kód do priestorov

134
00:10:02,650 --> 00:10:06,900
pre hľadanie vec, ktorú budete musieť vykonávať.

135
00:10:06,900 --> 00:10:10,540
A Revízia 2 bude druh vecí, ktoré vykonávame po tom.

136
00:10:10,540 --> 00:10:15,770
Takže môžete kliknúť na mojej revízie 1 a pracovať odtiaľ.

137
00:10:17,350 --> 00:10:22,060
A teraz chceme zaviesť binárne vyhľadávanie.

138
00:10:22,060 --> 00:10:26,470
>> Má niekto chcel len dať pseudokódu na vysokej úrovni vysvetlenie

139
00:10:26,470 --> 00:10:31,440
z toho, čo budeme musieť urobiť pre vyhľadávanie? Jo.

140
00:10:31,440 --> 00:10:36,170
[Študent] Stačí vziať stred poľa a uvidíme, či to, čo ste hľadali

141
00:10:36,170 --> 00:10:38,650
je menšia než alebo viac.

142
00:10:38,650 --> 00:10:41,080
A ak je to menej, idete do polovice, ktorá je menej,

143
00:10:41,080 --> 00:10:44,750
a ak je to viac, môžete ísť do polovice, ktorá je viac a vy to zopakovať, kým stačí si jednu vec.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Jo.

145
00:10:46,570 --> 00:10:51,320
Všimnite si, že naše čísla poľa už je zoradený,

146
00:10:51,320 --> 00:10:57,190
a tak to znamená, že môžeme využiť, že sme mohli najprv skontrolujte,

147
00:10:57,190 --> 00:11:00,390
jo, ja som hľadal číslo 50.

148
00:11:00,390 --> 00:11:03,720
Takže môžem ísť do stredu.

149
00:11:03,720 --> 00:11:07,380
Stredná je ťažké definovať, kedy je to ešte rad vecí,

150
00:11:07,380 --> 00:11:10,820
ale povedzme, že budeme vždy skrátiť na stredu.

151
00:11:10,820 --> 00:11:14,420
Takže tu máme 8 vecí, takže prostrednej bude 16.

152
00:11:14,420 --> 00:11:17,330
Hľadám 50, takže 50 je väčší ako 16 rokov.

153
00:11:17,330 --> 00:11:21,310
Takže teraz môžem v podstate liečiť svoje pole ako týchto prvkov.

154
00:11:21,310 --> 00:11:23,450
Môžem vyhodiť všetko od 16 cez.

155
00:11:23,450 --> 00:11:27,440
Teraz je moja pole je práve táto 4 prvky, a opakujem.

156
00:11:27,440 --> 00:11:31,910
Takže chcem nájsť stred znovu, čo bude 42.

157
00:11:31,910 --> 00:11:34,730
42 je menší ako 50, takže môžem hodiť ďaleko tieto dva prvky.

158
00:11:34,730 --> 00:11:36,890
To je môj zostávajúce pole.

159
00:11:36,890 --> 00:11:38,430
Idem nájsť stred znova.

160
00:11:38,430 --> 00:11:42,100
Myslím, že 50 bol zlý príklad, pretože som bol vždy zahodil veci na ľavej strane,

161
00:11:42,100 --> 00:11:48,280
ale v rovnakej miere, keď som hľadal niečo

162
00:11:48,280 --> 00:11:52,100
a je to menej, než prvok som v súčasnej dobe pri pohľade na,

163
00:11:52,100 --> 00:11:55,080
potom budem vyhadzovať všetko vpravo.

164
00:11:55,080 --> 00:11:58,150
Takže teraz musíme zaviesť, že.

165
00:11:58,150 --> 00:12:02,310
Všimnite si, že musíme prejsť vo veľkosti.

166
00:12:02,310 --> 00:12:06,730
Môžeme tiež nie je nutné hard-kódu veľkosti.

167
00:12:06,730 --> 00:12:11,640
Takže ak sa zbavíme toho # define -

168
00:12:19,630 --> 00:12:21,430
Dobre.

169
00:12:21,430 --> 00:12:27,180
Ako môžem krásne zistiť, čo je veľkosť čísel pole je v súčasnej dobe?

170
00:12:27,180 --> 00:12:30,950
>> Koľko prvkov je v číslach poli?

171
00:12:30,950 --> 00:12:33,630
[Štud] Čísla, držiaky,. Dĺžka?

172
00:12:33,630 --> 00:12:36,600
[Bowden] To neexistuje v C.

173
00:12:36,600 --> 00:12:38,580
Potrebujete. Dĺžka.

174
00:12:38,580 --> 00:12:42,010
Pole nemajú vlastnosti, takže nie je dĺžka vlastnosť polí

175
00:12:42,010 --> 00:12:45,650
že bude len aby vám ako dlho to stane sa.

176
00:12:48,180 --> 00:12:51,620
[Študent] Pozri koľko pamäte má, a rozdeliť podľa toho, ako moc - >> Jo.

177
00:12:51,620 --> 00:12:55,810
Takže, ako môžeme vidieť, koľko pamäte má? >> [Študent] sizeof. Jo >>, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof je operátor, ktorý to bude vrátiť veľkosť čísla poľa.

179
00:13:01,680 --> 00:13:10,060
A to bude ale veľa celé čísla tam sú časy, veľkosť celé číslo

180
00:13:10,060 --> 00:13:14,050
pretože to je to, koľko pamäte je to vlastne nástupu do.

181
00:13:14,050 --> 00:13:17,630
Takže keď chcem na rad vecí v poli,

182
00:13:17,630 --> 00:13:20,560
potom budem chcieť rozdeliť podľa veľkosti na celé číslo.

183
00:13:22,820 --> 00:13:26,010
Dobre. Takže mi umožňuje odovzdať vo veľkosti tu.

184
00:13:26,010 --> 00:13:29,430
Prečo musím odovzdať do veľkosti vôbec?

185
00:13:29,430 --> 00:13:38,570
Prečo nemôžem jednoducho robiť tu int size = sizeof (sena) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Prečo to nefunguje?

187
00:13:41,490 --> 00:13:44,470
[Študent] Nie je to globálne premenná.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack existuje a my sme okolo v číslach ako kope sena,

189
00:13:51,540 --> 00:13:54,700
a toto je predzvesť toho, čo príde. Jo.

190
00:13:54,700 --> 00:14:00,170
[Študent] Haystack je len odkaz na to, tak to by sa vrátil, aký veľký tento odkaz je.

191
00:14:00,170 --> 00:14:02,150
Jo.

192
00:14:02,150 --> 00:14:09,000
Pochybujem, v prednáške, keď ste videli hromadu skutočnosti ešte, že jo?

193
00:14:09,000 --> 00:14:11,270
Práve sme hovorili o tom.

194
00:14:11,270 --> 00:14:16,090
Takže stack je miesto, kde všetky vaše premenné sa bude uložený.

195
00:14:16,090 --> 00:14:19,960
>> Každá pamäť, ktorá je pridelená pre lokálne premenné sa deje v zásobníku,

196
00:14:19,960 --> 00:14:24,790
a každá funkcia má svoj vlastný priestor na zásobníku, vlastný zásobník rám je to, čo sa volá.

197
00:14:24,790 --> 00:14:31,590
Takže hlavná má svoj stack frame a vnútri nej bude existovať tento čísla poľa,

198
00:14:31,590 --> 00:14:34,270
a to bude o veľkosti sizeof (čísla).

199
00:14:34,270 --> 00:14:38,180
Bude to mať veľkosť čísel rozdelených podľa veľkosti prvkov,

200
00:14:38,180 --> 00:14:42,010
ale že všetky životy v zásobníku rámci hlavné je.

201
00:14:42,010 --> 00:14:45,190
Keď zavoláme hľadanie, hľadanie má svoj vlastný zásobník rám,

202
00:14:45,190 --> 00:14:48,840
vlastný priestor pre ukladanie všetkých svojich lokálnych premenných.

203
00:14:48,840 --> 00:14:56,420
Ale tieto argumenty - takže sena nie je kópiou celého tohto poľa.

204
00:14:56,420 --> 00:15:00,990
Nechceme odovzdať v celé pole ako kópia do vyhľadávania.

205
00:15:00,990 --> 00:15:04,030
Je to len odovzdá odkaz na tejto matice.

206
00:15:04,030 --> 00:15:11,470
Takže hľadanie možné prístup k týmto číslam prostredníctvom tohto odkazu.

207
00:15:11,470 --> 00:15:17,100
Je to stále prístup k veci, ktoré žijú vo vnútri zásobníka rámu hlavných je,

208
00:15:17,100 --> 00:15:22,990
ale v podstate, keď sa dostaneme do ukazovateľov, ktoré by malo byť čoskoro,

209
00:15:22,990 --> 00:15:24,980
to je to, čo ukazovátka.

210
00:15:24,980 --> 00:15:29,400
Ukazovatele sú len odkazy na veci, a môžete použiť odkazy na prístup k veci

211
00:15:29,400 --> 00:15:32,030
ktoré sú v zásobníku iných vecí "rámov.

212
00:15:32,030 --> 00:15:37,660
Takže aj keď čísla je miestne hlavné, stále ešte môžeme pristupovať prostredníctvom tohto ukazovateľa.

213
00:15:37,660 --> 00:15:41,770
Ale pretože je to len ukazovateľ a je to len odkaz,

214
00:15:41,770 --> 00:15:45,040
sizeof (Haystack) vráti iba veľkosť odkazu samotného.

215
00:15:45,040 --> 00:15:47,950
To nevráti veľkosť vec je to ukazuje.

216
00:15:47,950 --> 00:15:51,110
To nevráti skutočnú veľkosť čísel.

217
00:15:51,110 --> 00:15:55,660
A tak to nebude fungovať, ako chceme, aby to.

218
00:15:55,660 --> 00:15:57,320
>> Otázky týkajúce sa, že?

219
00:15:57,320 --> 00:16:03,250
Ukazovatele budú preč do významne viac krvavý podrobnejšie v týždňoch prísť.

220
00:16:06,750 --> 00:16:13,740
A to je dôvod, prečo mnoho vecí, ktoré vidíte, väčšina vyhľadávacích vecí alebo triediť veci,

221
00:16:13,740 --> 00:16:16,990
oni takmer všetci budeme musieť vziať skutočnej veľkosti poľa,

222
00:16:16,990 --> 00:16:20,440
pretože v C, nemáme poňatia, čo veľkosť poľa je.

223
00:16:20,440 --> 00:16:22,720
Musíte ručne preniesť dovnútra

224
00:16:22,720 --> 00:16:27,190
A nemožno ručne odovzdať v celom poli, pretože si len prechádzať v odkaze

225
00:16:27,190 --> 00:16:30,390
a nemôže dostať do veľkosti v odkaze.

226
00:16:30,390 --> 00:16:32,300
Dobre.

227
00:16:32,300 --> 00:16:38,160
Takže teraz chceme realizovať to, čo bolo vysvetlené skôr.

228
00:16:38,160 --> 00:16:41,530
Môžete pracovať na ňom za minútu,

229
00:16:41,530 --> 00:16:45,250
a nemusíte sa báť všetko perfektne 100% funkčné.

230
00:16:45,250 --> 00:16:51,410
Stačí napísať do polovičnej pseudokódu pre to, ako si myslíte, že by to malo fungovať.

231
00:16:52,000 --> 00:16:53,630
Dobre.

232
00:16:53,630 --> 00:16:56,350
Nie je potrebné byť úplne hotový s to ešte.

233
00:16:56,350 --> 00:17:02,380
Ale niekto cíti dobre s tým, čo majú tak ďaleko,

234
00:17:02,380 --> 00:17:05,599
ako niečo, čo môžeme pracovať spoločne?

235
00:17:05,599 --> 00:17:09,690
Má niekto chcel dobrovoľne? Alebo som sa náhodne vyberať.

236
00:17:12,680 --> 00:17:18,599
Nemusí to byť priamo v každom ohľade, ale niečo, čo môžeme meniť do funkčného stavu.

237
00:17:18,599 --> 00:17:20,720
[Študent] Jasne. Dobre >>.

238
00:17:20,720 --> 00:17:27,220
Takže môžete ušetriť na revíziu kliknutím na malú ikonu Uložiť.

239
00:17:27,220 --> 00:17:29,950
Ste Ramy, že jo? >> [Študent] Jo. >> [Bowden] Dobre.

240
00:17:29,950 --> 00:17:35,140
Takže teraz môžem zobraziť revíziu a každý môže vytiahnuť revíziu.

241
00:17:35,140 --> 00:17:38,600
A máme tu - Dobre.

242
00:17:38,600 --> 00:17:43,160
Takže rámy šiel s rekurzívne riešenie, ktoré je rozhodne platné riešenie.

243
00:17:43,160 --> 00:17:44,970
Existujú dva spôsoby, ako môžete urobiť tento problém.

244
00:17:44,970 --> 00:17:48,060
Môžete to urobiť iteračné alebo rekurzívne.

245
00:17:48,060 --> 00:17:53,860
Väčšina problémy mi, že môže byť vykonané rekurzívne môže byť tiež vykonané opakované.

246
00:17:53,860 --> 00:17:58,510
Tak tu sme urobili to rekurzívne.

247
00:17:58,510 --> 00:18:03,730
>> Má niekto chcete definovať, čo to znamená, aby sa funkcia rekurzívne?

248
00:18:07,210 --> 00:18:08,920
[Študent] Ak máte funkciu volať seba

249
00:18:08,920 --> 00:18:13,470
a potom volať seba, kým to vyjde s pravdou a pravda. Jo >>.

250
00:18:13,470 --> 00:18:17,680
Rekurzívne funkcie je len funkcia, ktorá volá sama seba.

251
00:18:17,680 --> 00:18:24,140
K dispozícii sú tri veľké veci, ktoré rekurzívne funkcie musia mať.

252
00:18:24,140 --> 00:18:27,310
Prvá z nich je samozrejme, že volá sama seba.

253
00:18:27,310 --> 00:18:29,650
Druhým je base-case.

254
00:18:29,650 --> 00:18:33,390
Takže v určitom okamihu funkcie musí prestať volať sám,

255
00:18:33,390 --> 00:18:35,610
a to je to, čo referenčný prípad je pre.

256
00:18:35,610 --> 00:18:43,860
Tak tu vieme, že by sme mali prestať, mali by sme sa v našom hľadaní

257
00:18:43,860 --> 00:18:48,150
ak je štart rovná koniec - a pôjdeme nad tým, čo to znamená.

258
00:18:48,150 --> 00:18:52,130
Ale nakoniec, posledná vec, ktorá je dôležitá pre rekurzívne funkcie:

259
00:18:52,130 --> 00:18:59,250
funkcie musí nejako priblížiť základnú vec.

260
00:18:59,250 --> 00:19:04,140
Rovnako ako keď ste v skutočnosti aktualizácia nič, keď urobíte druhý rekurzívne volanie,

261
00:19:04,140 --> 00:19:07,880
ak ste doslova volá funkciu znova s ​​rovnakými argumentmi

262
00:19:07,880 --> 00:19:10,130
a žiadne globálne premenné zmenili alebo tak niečo,

263
00:19:10,130 --> 00:19:14,430
budete nikdy nedosiahne základnú vec, v tomto prípade to je zlé.

264
00:19:14,430 --> 00:19:17,950
Bude to nekonečná rekurzia a pretečenie zásobníka.

265
00:19:17,950 --> 00:19:24,330
Ale tu vidíme, že aktualizácia sa deje, pretože sme aktualizáciu kto + koniec / 2,

266
00:19:24,330 --> 00:19:28,180
sme aktualizáciu koniec argumentu tu, sme aktualizáciu počiatočné tvrdenie tu.

267
00:19:28,180 --> 00:19:32,860
Takže vo všetkých rekurzívne volanie sme aktualizáciu niečo. Dobre.

268
00:19:32,860 --> 00:19:38,110
Chcete chodiť nám prostredníctvom riešenia? Iste >>.

269
00:19:38,110 --> 00:19:44,270
Ja používam SearchHelp tak, že zakaždým, keď som túto funkciu volania

270
00:19:44,270 --> 00:19:47,910
Mám štart, kde som hľadal v poli a koniec

271
00:19:47,910 --> 00:19:49,380
, Kde som pohľade na pole.

272
00:19:49,380 --> 00:19:55,330
>> Na každom kroku, kde je to hovorí, že je to stredný element, ktorý je začiatok + koniec / 2,

273
00:19:55,330 --> 00:19:58,850
je, že rovná tomu, čo sme hľadali?

274
00:19:58,850 --> 00:20:04,650
A ak je, potom sme ho našli, a ja myslím, že je odovzdaný do úrovne rekurzie.

275
00:20:04,650 --> 00:20:12,540
A ak to nie je pravda, potom sme skontrolovať, či stredná hodnota poľa je príliš veľká,

276
00:20:12,540 --> 00:20:19,320
v takom prípade sa pozeráme na ľavej polovici poľa tým, že ide od začiatku do strednej indexu.

277
00:20:19,320 --> 00:20:22,710
A inak robíme Koniec polovice.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Dobre.

279
00:20:24,740 --> 00:20:27,730
To znie dobre.

280
00:20:27,730 --> 00:20:36,640
Dobre, takže pár vecí, a skutočne, je to veľmi vysokej úrovni, čo

281
00:20:36,640 --> 00:20:41,270
že budete nikdy vedieť tohto kurzu, ale je to pravda.

282
00:20:41,270 --> 00:20:46,080
Rekurzívne funkcie, vždy budete počuť, že sú zlé riešenie

283
00:20:46,080 --> 00:20:51,160
pretože keď rekurzívne hovoríš príliš veľakrát, získate pretečeniu zásobníka

284
00:20:51,160 --> 00:20:54,990
pretože, ako som už povedal skôr, každá funkcia má svoj vlastný zásobník rám.

285
00:20:54,990 --> 00:20:59,500
Takže každý hovor z rekurzívne funkcie má svoj vlastný zásobník rám.

286
00:20:59,500 --> 00:21:04,140
Takže ak urobíte 1.000 rekurzívne volanie, získate 1.000 zásobník snímok,

287
00:21:04,140 --> 00:21:08,390
a rýchlo sa viesť k nutnosti príliš veľa stack rámy a veci sa rozbijú.

288
00:21:08,390 --> 00:21:13,480
Takže to je dôvod, prečo rekurzívne funkcie sú všeobecne zlé.

289
00:21:13,480 --> 00:21:19,370
Ale tam je pekný podmnožina rekurzívny funkciou tzv tail-rekurzívne funkcie,

290
00:21:19,370 --> 00:21:26,120
a to sa stane, že je príkladom jednej, kde v prípade, že kompilátor vníma tento

291
00:21:26,120 --> 00:21:29,920
a to by malo, myslím, že - v Clang odovzdáte ho the-flag O2

292
00:21:29,920 --> 00:21:33,250
potom si všimnete je to chvost rekurzívne a robiť veci dobre.

293
00:21:33,250 --> 00:21:40,050
>> To bude používať rovnaké fronty rám znovu a znovu pre každú rekurzívne volanie.

294
00:21:40,050 --> 00:21:47,010
A tak, pretože ste pomocou rovnakého zásobníka rám, nemusíte sa obávať

295
00:21:47,010 --> 00:21:51,690
kedy zásobník pretekaniu, a na rovnakú dobu, ako tie povedané vyššie,

296
00:21:51,690 --> 00:21:56,380
kde akonáhle sa vrátite pravda, potom to musí vrátiť do všetkých týchto zásobníka rámov

297
00:21:56,380 --> 00:22:01,740
a 10. výzva na SearchHelp musí vrátiť do 9., sa musí vrátiť do 8..

298
00:22:01,740 --> 00:22:05,360
Takže nie je potrebné sa stane, keď funkcia chvost rekurzívne.

299
00:22:05,360 --> 00:22:13,740
A tak to, čo robí táto funkcia chvost rekurzívne je upozornenie, že pre dané výzvy na searchHelp

300
00:22:13,740 --> 00:22:18,470
rekurzívne volanie, že to robiť, je to, čo sa vracia.

301
00:22:18,470 --> 00:22:25,290
Takže v prvej volanie SearchHelp, sme buď okamžite vráti false,

302
00:22:25,290 --> 00:22:29,590
okamžite vrátiť true, alebo budeme robiť rekurzívne volanie SearchHelp

303
00:22:29,590 --> 00:22:33,810
kde to, čo sa vraciame, je to, čo, že hovor sa vracia.

304
00:22:33,810 --> 00:22:51,560
A my sme nemohli robiť to, ak sme urobili niečo ako int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
len nejaký náhodný zmena.

306
00:22:55,440 --> 00:23:01,470
>> Takže teraz to rekurzívne volanie, toto int x = SearchHelp rekurzívne volanie,

307
00:23:01,470 --> 00:23:05,740
je už chvost rekurzívny, pretože to vlastne nemá musieť vrátiť

308
00:23:05,740 --> 00:23:10,400
späť na predchádzajúcu zásobníka ráme tak, že predchádzajúce volanie funkcie

309
00:23:10,400 --> 00:23:13,040
potom môže niečo urobiť s návratovú hodnotu.

310
00:23:13,040 --> 00:23:22,190
Takže to nie je chvost rekurzívne, ale to, čo sme mali predtým, je pekne chvost rekurzívny. Jo.

311
00:23:22,190 --> 00:23:27,000
[Študent] Ak nie je druhá základňa prípad skontrolovať prvý

312
00:23:27,000 --> 00:23:30,640
pretože by mohlo nastať situácia, kedy pri odovzdať argument

313
00:23:30,640 --> 00:23:35,770
ste start = koniec, ale oni sú ihly hodnotu.

314
00:23:35,770 --> 00:23:47,310
Otázka nemôže narazíme na prípad, kedy je koniec ihly hodnota

315
00:23:47,310 --> 00:23:52,000
alebo štart = koniec, primerane, štart = koniec

316
00:23:52,000 --> 00:23:59,480
a vy ste v skutočnosti kontrolovať, že konkrétne hodnoty ešte,

317
00:23:59,480 --> 00:24:03,910
potom začať + koniec / 2 je len tak mať rovnakú hodnotu.

318
00:24:03,910 --> 00:24:07,890
Ale my už sa vrátil false, a nikdy sme vlastne čítal hodnotu.

319
00:24:07,890 --> 00:24:14,240
Takže prinajmenšom v prvom hovore, ak je veľkosť 0, potom chceme vrátiť false.

320
00:24:14,240 --> 00:24:17,710
Ale ak veľkosť je 1, potom začiatok nebude rovnaké konca,

321
00:24:17,710 --> 00:24:19,820
a budeme aspoň skontrolovať jeden prvok.

322
00:24:19,820 --> 00:24:26,750
Ale myslím, že máte pravdu v tom, že môžeme skončiť v prípade, kedy začať + koniec / 2,

323
00:24:26,750 --> 00:24:31,190
Začiatok nakoniec je rovnaký ako začiatok + koniec / 2,

324
00:24:31,190 --> 00:24:35,350
ale nikdy sme vlastne čítal tento prvok.

325
00:24:35,350 --> 00:24:44,740
>> Takže keď sme najprv skontrolovať, je stredná prvok hodnotu, ktorú hľadáte,

326
00:24:44,740 --> 00:24:47,110
potom môžeme okamžite vrátiť true.

327
00:24:47,110 --> 00:24:50,740
Else, ak sú rovnaké, potom je tu nemá zmysel pokračovať

328
00:24:50,740 --> 00:24:58,440
pretože sme len tak aktualizáciu na prípad, kedy sme na jednej prvku poľa.

329
00:24:58,440 --> 00:25:01,110
Ak tento jediný prvok nie je ten, ktorého hľadáme,

330
00:25:01,110 --> 00:25:03,530
potom je všetko v poriadku. Jo.

331
00:25:03,530 --> 00:25:08,900
[Študent] vec je, že od tej doby veľkosť je v skutočnosti väčší ako počet prvkov v poli,

332
00:25:08,900 --> 00:25:13,070
tam je už offset - >> Tak bude veľkosť -

333
00:25:13,070 --> 00:25:19,380
[Študent] povedať, či pole je veľkosť 0, potom SearchHelp skutočne kontrolovať Haystack 0.

334
00:25:19,380 --> 00:25:21,490
na prvú výzvu.

335
00:25:21,490 --> 00:25:25,300
Pole má veľkosť 0, takže 0 je - >> Jo.

336
00:25:25,300 --> 00:25:30,750
Je tu ďalšia vec, ktorá - to by mohlo byť dobré. Poďme premýšľať.

337
00:25:30,750 --> 00:25:40,120
Takže ak pole mal 10 článkov a prostredný budeme kontrolovať, je index 5,

338
00:25:40,120 --> 00:25:45,700
takže sme kontrolu 5, a povedzme, že hodnota je menšia.

339
00:25:45,700 --> 00:25:50,720
Takže sme hádzať všetko preč od 5 dopredu.

340
00:25:50,720 --> 00:25:54,030
Takže začať + end / 2 bude náš nový koniec,

341
00:25:54,030 --> 00:25:57,450
tak jo, to vždy zostať aj po skončení tohto poľa.

342
00:25:57,450 --> 00:26:03,570
Ak je to prípad, kedy to bolo párne alebo nepárne, potom by sme zistili, či, povedzme, 4,

343
00:26:03,570 --> 00:26:05,770
ale my sme stále vyhadzujete -

344
00:26:05,770 --> 00:26:13,500
Tak jo, koniec je vždy bude za skutočného konca poľa.

345
00:26:13,500 --> 00:26:18,350
Takže prvkov sme so zameraním na, koniec je vždy bude jeden po tom.

346
00:26:18,350 --> 00:26:24,270
A ak sa niekedy začiatok rovnaký koniec, my sme v poli veľkosti 0.

347
00:26:24,270 --> 00:26:35,600
>> Ďalšia vec, ktorú som myslel je, že sme aktualizáciu štart sa začať + koniec / 2,

348
00:26:35,600 --> 00:26:44,020
tak to je pravda, že mám problémy s, kde začať + koniec / 2

349
00:26:44,020 --> 00:26:46,820
je element sme kontrolu.

350
00:26:46,820 --> 00:26:58,150
Povedzme, že sme mali 10-prvok poľa. Čokoľvek.

351
00:26:58,150 --> 00:27:03,250
Takže začať + end / 2 bude niečo ako je tento,

352
00:27:03,250 --> 00:27:07,060
a ak to nie je hodnota, že chceme aktualizovať.

353
00:27:07,060 --> 00:27:10,060
Hodnota je väčšia, takže chceme sa pozrieť na tejto polovice poľa.

354
00:27:10,060 --> 00:27:15,910
Tak ako sme aktualizáciu začiatok, sme aktualizáciu štart teraz tento prvok.

355
00:27:15,910 --> 00:27:23,790
Ale to sa môže stále fungovať, alebo prinajmenšom, môžete tak urobiť začiatok + koniec / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Študent] Nemusíte byť začať + koniec [nepočuteľné] >> Jo.

357
00:27:27,850 --> 00:27:33,240
Sme už skúmali tento prvok a viem, že to nie je ten, ktorého hľadáme.

358
00:27:33,240 --> 00:27:36,800
Takže nepotrebujeme aktualizovať štart je tento prvok.

359
00:27:36,800 --> 00:27:39,560
Môžeme len preskočiť a aktualizovať začať byť tento prvok.

360
00:27:39,560 --> 00:27:46,060
A je tam niekedy prípad, povedzme, že to bolo koniec,

361
00:27:46,060 --> 00:27:53,140
takže potom kto by to, kto + koniec / 2 by to,

362
00:27:53,140 --> 00:28:00,580
kto + koniec - Jo, myslím, že to môže skončiť v nekonečnej rekurzie.

363
00:28:00,580 --> 00:28:12,690
Povedzme, že je to len pole o veľkosti 2 alebo pole o veľkosti 1. Myslím, že to bude fungovať.

364
00:28:12,690 --> 00:28:19,490
Takže v súčasnej dobe, štart je tento prvok a koniec je 1 mimo neho.

365
00:28:19,490 --> 00:28:24,110
Takže prvok, ktorý budeme kontrolovať, je to jedno,

366
00:28:24,110 --> 00:28:29,400
a potom, keď sme aktualizáciu začiatok, sme aktualizáciu štart byť 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
ktorý sa bude do konca nás späť s počiatočnou že tento prvok.

368
00:28:33,160 --> 00:28:36,210
>> Takže sme kontrolu rovnaký prvok znovu a znovu.

369
00:28:36,210 --> 00:28:43,310
Tak toto je prípad, kedy každá rekurzívne volanie, musí byť skutočne aktualizovať niečo.

370
00:28:43,310 --> 00:28:48,370
Takže musíme urobiť začiatok + koniec / 2 + 1, inak je tu prípad

371
00:28:48,370 --> 00:28:50,710
kde sme v skutočnosti aktualizácia začiatok.

372
00:28:50,710 --> 00:28:53,820
Všetci vidia, že?

373
00:28:53,820 --> 00:28:56,310
Dobre.

374
00:28:56,310 --> 00:29:03,860
Má niekto nejaké otázky týkajúce sa tohto roztoku alebo akékoľvek ďalšie komentáre?

375
00:29:05,220 --> 00:29:10,280
Dobre. Má niekto iteratívny riešenie, ktoré môžeme všetci pozrieť na?

376
00:29:17,400 --> 00:29:20,940
Sme to všetci rekurzívne?

377
00:29:20,940 --> 00:29:25,950
Alebo tiež myslím, že ak ste si otvorili jej, potom by ste mali mať prepísať svoj predchádzajúci.

378
00:29:25,950 --> 00:29:28,810
Má to automaticky ukladať? Nie som pozitívne.

379
00:29:35,090 --> 00:29:39,130
Má niekto sa opakujúce?

380
00:29:39,130 --> 00:29:42,430
Môžeme prejsť nej spoločne, ak nie.

381
00:29:46,080 --> 00:29:48,100
Myšlienka bude rovnaké.

382
00:30:00,260 --> 00:30:02,830
Iteračné riešenie.

383
00:30:02,830 --> 00:30:07,140
Budeme chcieť, aby v podstate robiť rovnakú myšlienku

384
00:30:07,140 --> 00:30:16,530
tam, kde chceme sledovať nové konci poľa a nový začiatok poľa

385
00:30:16,530 --> 00:30:18,510
a to, že znova a znova.

386
00:30:18,510 --> 00:30:22,430
A či to, čo sme sledovaní ako na začiatku a na konci vždy pretínajú,

387
00:30:22,430 --> 00:30:29,020
potom sme nenašli, a môžeme sa vrátiť false.

388
00:30:29,020 --> 00:30:37,540
Tak ako to mám urobiť, že? Každý, kto má návrhy alebo kód pre mňa vytiahnuť?

389
00:30:42,190 --> 00:30:47,450
[Študent] Do slučky while. Jo >>.

390
00:30:47,450 --> 00:30:49,450
Budeš chcieť urobiť slučku.

391
00:30:49,450 --> 00:30:51,830
>> Mali ste kód, ktorý som mohol vytiahnuť, alebo čo si chcel navrhnúť?

392
00:30:51,830 --> 00:30:56,340
[Študent] Myslím, že áno. >> Dobre. To robí veci jednoduchšie. Aké bolo vaše meno?

393
00:30:56,340 --> 00:30:57,890
[Študent] Lucas.

394
00:31:00,140 --> 00:31:04,190
Revízia 1. Dobre.

395
00:31:04,190 --> 00:31:13,200
Najnižšia je to, čo sme nazvali začať skôr.

396
00:31:13,200 --> 00:31:17,080
Up nie je to, čo sme nazvali koniec pred.

397
00:31:17,080 --> 00:31:22,750
V skutočnosti, koniec je teraz v matici. Je to prvok, by sme mali zvážiť.

398
00:31:22,750 --> 00:31:26,890
Takže nízka je 0 až je veľkosť poľa - 1,

399
00:31:26,890 --> 00:31:34,780
a teraz sme slučky, a my sa kontrola -

400
00:31:34,780 --> 00:31:37,340
Myslím, že môžete chodiť cez neho.

401
00:31:37,340 --> 00:31:41,420
Aký bol váš myslenie cez to? Prechádzka nás prostredníctvom kódu.

402
00:31:41,420 --> 00:31:49,940
[Študent] Jasne. Pozrite sa na Haystack hodnotu v strede a porovnať ho s ihlou.

403
00:31:49,940 --> 00:31:58,520
Takže ak je to väčšie než vaše ihly, potom budete chcieť - oh, vlastne, že by mala byť spätne.

404
00:31:58,520 --> 00:32:05,180
Budeš chcieť vyhodiť pravú polovicu, a tak jo, to by malo byť tak.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Tak by to malo byť menej? Je to to, čo si povedal? >> [Študent] Jo.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Dobre. Menej.

407
00:32:10,390 --> 00:32:15,700
Takže ak to, čo sa pozeráme na menšie, než to, čo chceme,

408
00:32:15,700 --> 00:32:19,410
tak jo, chceme vyhodiť ľavú polovicu,

409
00:32:19,410 --> 00:32:22,210
čo znamená, že sa aktualizácia všetko Uvažujeme

410
00:32:22,210 --> 00:32:26,610
Pohybom nízko na pravej strane poľa.

411
00:32:26,610 --> 00:32:30,130
To vyzerá dobre.

412
00:32:30,130 --> 00:32:34,550
Myslím, že to má rovnaký problém, ktorý sme si povedali na predchádzajúcu,

413
00:32:34,550 --> 00:32:49,760
, Kde v prípade nízkej je 0, a až je 1, potom nízky + až / 2 bude nastavený tak, aby sa to isté znova.

414
00:32:49,760 --> 00:32:53,860
>> A aj keď to nie je tento prípad, je ešte účinnejšia, prinajmenšom

415
00:32:53,860 --> 00:32:57,630
len vyhodiť prvok sme práve pozrel na ktorom vieme, že je v poriadku.

416
00:32:57,630 --> 00:33:03,240
Tak nízka + hore / 2 + 1 - >> [Študent] To by malo byť naopak.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Alebo by to malo byť - 1 a druhý by mal byť + 1.

418
00:33:05,900 --> 00:33:09,580
[Študent] A by mal byť dvojaký znamienko rovnosti. >> [Bowden] Jo.

419
00:33:09,580 --> 00:33:11,340
[Študent] Jo.

420
00:33:14,540 --> 00:33:15,910
Dobre.

421
00:33:15,910 --> 00:33:21,280
A konečne, teraz, keď máme túto + 1-1 vec,

422
00:33:21,280 --> 00:33:31,520
je to - to nemusí byť - je to vôbec možné, nízka skončiť s hodnotou vyššou ako hore?

423
00:33:35,710 --> 00:33:40,320
Myslím, že jediný spôsob, ako sa môže stať - je to možné? >> [Študent] Neviem.

424
00:33:40,320 --> 00:33:45,220
Ale ak to bude skrátený a potom dostane mínus 1 a potom - >> Jo.

425
00:33:45,220 --> 00:33:47,480
[Študent] To by možno si spackal.

426
00:33:49,700 --> 00:33:53,940
Myslím, že by to malo byť dobré len preto, že

427
00:33:53,940 --> 00:33:58,800
pre to, aby skončil nižšie, budú musieť byť so rovnať, myslím.

428
00:33:58,800 --> 00:34:03,070
Ale ak sú rovnaké, potom by sme urobili while začať s

429
00:34:03,070 --> 00:34:06,670
a my sme sa vrátili hodnotu. Takže myslím, že sme v pohode teraz.

430
00:34:06,670 --> 00:34:11,530
Všimnite si, že aj keď je tento problém už rekurzívne,

431
00:34:11,530 --> 00:34:17,400
rovnaký druh myšlienok platí, kde môžeme vidieť, ako to tak ľahko prepožičiava

432
00:34:17,400 --> 00:34:23,659
k rekurzívne riešenie tým, že sme len aktualizuje indexy znova a znova,

433
00:34:23,659 --> 00:34:29,960
robíme problém menšie a menšie, my sa sústredíme na podmnožinu poľa.

434
00:34:29,960 --> 00:34:40,860
[Študent] Pri nízkej je 0, a až je 1, by sa obaja 0 + 1/2, čo by na 0,

435
00:34:40,860 --> 00:34:44,429
a potom jeden by + 1, jeden by byť - 1.

436
00:34:47,000 --> 00:34:50,870
[Študent] Kde sme kontrolu rovnosti?

437
00:34:50,870 --> 00:34:55,100
Ako v prípade, že prostredný je vlastne ihla?

438
00:34:55,100 --> 00:34:58,590
Nie sme v súčasnej dobe robí, že? Oh!

439
00:35:00,610 --> 00:35:02,460
Pokiaľ to -

440
00:35:05,340 --> 00:35:13,740
Áno. Nemôžeme len tak urobiť test sem, pretože povedzme, že prvé stredu -

441
00:35:13,740 --> 00:35:16,430
[Študent] Je to vlastne ako nevyhadzujte viazané.

442
00:35:16,430 --> 00:35:20,220
Takže ak máte vyhodiť viazaný, budete musieť skontrolovať prvej alebo čokoľvek.

443
00:35:20,220 --> 00:35:23,350
Ah. Jo. >> [Študent] Jo.

444
00:35:23,350 --> 00:35:29,650
Takže teraz sme zahodil ten sme v súčasnej dobe sa pozrel na,

445
00:35:29,650 --> 00:35:33,260
čo znamená, že teraz musíme tiež mať

446
00:35:33,260 --> 00:35:44,810
if (Haystack [(low + up) / 2] == ihly), potom môžeme vrátiť true.

447
00:35:44,810 --> 00:35:52,070
A či som dal inam, alebo len v prípade, to znamená doslova to isté

448
00:35:52,070 --> 00:35:57,110
pretože by sa vrátili pravda.

449
00:35:57,110 --> 00:36:01,450
Tak som si dal else if, ale to nevadí.

450
00:36:01,450 --> 00:36:10,440
>> Takže ešte ak to, inak to, a to je bežná vec robím

451
00:36:10,440 --> 00:36:14,340
, Kde aj keď je to v prípade, keď je všetko dobré tu,

452
00:36:14,340 --> 00:36:22,780
ako nízka, môže byť nikdy vyššia ako hore, to nestojí za úvaha o tom, či je to pravda.

453
00:36:22,780 --> 00:36:28,010
Takže sa môže tiež hovoriť pri nízkej je menší ako alebo rovný

454
00:36:28,010 --> 00:36:30,720
alebo pri nízkej je menšia ako

455
00:36:30,720 --> 00:36:35,300
takže v prípade, že sú stále rovnaké, alebo nízka stane ujsť,

456
00:36:35,300 --> 00:36:40,130
potom môžeme vymaniť z tejto slučky.

457
00:36:41,410 --> 00:36:44,630
Otázky, obavy, názory?

458
00:36:47,080 --> 00:36:49,270
Dobre. To vyzerá dobre.

459
00:36:49,270 --> 00:36:52,230
Teraz chceme urobiť akúsi.

460
00:36:52,230 --> 00:37:04,030
Ak pôjdeme do mojej druhej revízii, vidíme tie isté čísla,

461
00:37:04,030 --> 00:37:07,550
ale teraz sú už v zoradené poradí.

462
00:37:07,550 --> 00:37:12,840
A my chceme zaviesť akúsi pomocou akýkoľvek algoritmus v O n log n

463
00:37:12,840 --> 00:37:17,240
Takže, ktoré algoritmus si myslíte, že by sme mali zaviesť tu? >> [Študent] Merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Jo. Zlúčiť sort je O (n log n), takže to je to, čo budeme robiť.

465
00:37:23,810 --> 00:37:26,680
A problém bude dosť podobne,

466
00:37:26,680 --> 00:37:31,920
kde sa ľahko požičiava seba k rekurzívne riešenie.

467
00:37:31,920 --> 00:37:35,580
Môžeme tiež prísť s iteratívny riešenie, ak chceme,

468
00:37:35,580 --> 00:37:42,540
ale rekurzia bude jednoduchšie tu a mali by sme robiť rekurziu.

469
00:37:45,120 --> 00:37:49,530
Myslím, že budeme prechádzať radiť zlúčenie prvý,

470
00:37:49,530 --> 00:37:54,280
hoci tam je krásne video o radiť zlúčenie už. [Smiech]

471
00:37:54,280 --> 00:37:59,780
Takže zlúčiť druh existuje - Som plytvanie toľko tejto práce.

472
00:37:59,780 --> 00:38:02,080
Oh, je tu len jeden vľavo.

473
00:38:02,080 --> 00:38:03,630
Tak zlúčenie.

474
00:38:08,190 --> 00:38:12,470
Ó, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Dobre.

476
00:38:29,910 --> 00:38:33,460
Merge má dva samostatné pole.

477
00:38:33,460 --> 00:38:36,780
Individuálne tieto dve polia sú obaja zoradené.

478
00:38:36,780 --> 00:38:40,970
Takže toto pole, 1, 3, 5, zoradené. Toto pole, 0, 2, 4, zoradené.

479
00:38:40,970 --> 00:38:46,710
Čo teraz zlúčenie mali urobiť, je spojiť ich do jedného poľa, ktorá je sama zoradené.

480
00:38:46,710 --> 00:38:57,130
Takže chceme pole o veľkosti 6, ktorá sa bude mať tieto prvky vnútri neho

481
00:38:57,130 --> 00:38:59,390
v zoradenie poradí.

482
00:38:59,390 --> 00:39:03,390
>> A tak môžeme využiť k tomu, že tieto dva polia sú zoradené

483
00:39:03,390 --> 00:39:06,800
k tomu v lineárnom čase,

484
00:39:06,800 --> 00:39:13,510
lineárny čas význam v prípade, že je veľkosť poľa x, a to je veľkosť y,

485
00:39:13,510 --> 00:39:20,970
potom celkový algoritmus by mal byť O (x + y). Dobre.

486
00:39:20,970 --> 00:39:23,150
Tak návrhy.

487
00:39:23,150 --> 00:39:26,030
[Študent] Mohli by sme začať zľava?

488
00:39:26,030 --> 00:39:30,150
Takže budete dal 0 dolu a potom 1 a potom tu ste na 2.

489
00:39:30,150 --> 00:39:33,320
Takže je to niečo ako, že máte kartu, ktorá sa pohybuje doprava. >> [Bowden] Jo.

490
00:39:33,320 --> 00:39:41,070
Pre obidva z týchto polí, ak sa sústrediť len na krajnom prvku.

491
00:39:41,070 --> 00:39:43,530
Vzhľadom k tomu, ako polia sú zoradené, vieme, že tieto 2 prvky

492
00:39:43,530 --> 00:39:46,920
sú najmenšie prvky oboch poli.

493
00:39:46,920 --> 00:39:53,500
To znamená, že 1 z týchto 2 prvkov musí byť najmenší prvok v našej zlúčené polia.

494
00:39:53,500 --> 00:39:58,190
To len tak sa stane, že najmenší je jedno na pravej tejto doby.

495
00:39:58,190 --> 00:40:02,580
Tak sme sa 0, vložte ho na ľavej strane, pretože 0 je menšia ako 1,

496
00:40:02,580 --> 00:40:08,210
takže si 0, vložte ju do našej prvej pozície, a potom sme ich aktualizuje

497
00:40:08,210 --> 00:40:12,070
aby teraz sústrediť na prvý prvok.

498
00:40:12,070 --> 00:40:14,570
A teraz sme sa opakovať.

499
00:40:14,570 --> 00:40:20,670
Takže teraz sme tieto 2 a 1. 1 je menšie, takže vložíme 1.

500
00:40:20,670 --> 00:40:25,300
My aktualizovať tento ukazovateľ aby ukazoval na toho chlapa.

501
00:40:25,300 --> 00:40:33,160
Teraz sme to znovu, tak 2. To bude aktualizovať, porovnanie týchto 2, 3.

502
00:40:33,160 --> 00:40:37,770
Táto aktualizácia, potom 4 a 5.

503
00:40:37,770 --> 00:40:42,110
Tak to je zlúčenie.

504
00:40:42,110 --> 00:40:49,010
>> Malo by byť absolútne jasné, že je lineárny čas, pretože sme jednoducho ísť cez každý prvok raz.

505
00:40:49,010 --> 00:40:55,980
A to je najväčší krok k realizácii zlúčenia radenie to robí.

506
00:40:55,980 --> 00:40:59,330
A to nie je tak ťažké.

507
00:40:59,330 --> 00:41:15,020
A pár vecí robiť starosti, je povedzme sme zlúčenie 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
V tomto prípade sme skončili v scenári, kde tento človek bude menší,

509
00:41:30,930 --> 00:41:36,160
potom aktualizovať tento ukazovateľ, toto bude menšie, je aktualizuje,

510
00:41:36,160 --> 00:41:41,280
toto je menšie, a teraz budete musieť uznať

511
00:41:41,280 --> 00:41:44,220
keď ste skutočne spustiť z prvkov, ktoré majú v porovnaní s

512
00:41:44,220 --> 00:41:49,400
Pretože sme už používali tento celého poľa,

513
00:41:49,400 --> 00:41:55,190
všetko v tomto poli je teraz práve vložené do tu.

514
00:41:55,190 --> 00:42:02,040
Takže ak sa niekedy dostanete do bodu, kedy je jeden z našich polí úplne zlúčené už,

515
00:42:02,040 --> 00:42:06,510
potom len vziať všetky prvky druhej poľa a vložiť do konca poľa.

516
00:42:06,510 --> 00:42:13,630
Takže môžeme len vložiť 4, 5, 6. Dobre.

517
00:42:13,630 --> 00:42:18,070
To je jedna vec, dávať si pozor na.

518
00:42:22,080 --> 00:42:26,120
Vykonávacie ktorý by mal byť krok 1.

519
00:42:26,120 --> 00:42:32,600
Zlúčiť radiť potom na základe toho, že je to 2 kroky, 2 hlúpe kroky.

520
00:42:38,800 --> 00:42:42,090
Poďme dať toto pole.

521
00:42:57,920 --> 00:43:05,680
Takže zlúčiť druh, krok 1 je rekurzívne rozdeliť pole na polovice.

522
00:43:05,680 --> 00:43:09,350
Takže rozdeliť toto pole na polovice.

523
00:43:09,350 --> 00:43:22,920
V súčasnej dobe máme 4, 15, 16, 50 a 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
A teraz sme to znova a rozdelili sme ich do polovice.

525
00:43:25,800 --> 00:43:27,530
Ja si len to na tejto strane.

526
00:43:27,530 --> 00:43:34,790
Takže 4, 15 a 16, 50.

527
00:43:34,790 --> 00:43:37,440
Radi by sme robiť rovnakú vec znovu tu.

528
00:43:37,440 --> 00:43:40,340
A teraz sme sa rozdelili do polovice znovu.

529
00:43:40,340 --> 00:43:51,080
A máme 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Tak to je náš základný scenár.

531
00:43:53,170 --> 00:44:00,540
Akonáhle polia sú veľkosti 1, potom prestať s rozdelením do polovice.

532
00:44:00,540 --> 00:44:03,190
>> Čo teraz budeme robiť s tým?

533
00:44:03,190 --> 00:44:15,730
Sme skončiť to bude tiež rozdeliť do 8, 23, 42, a 108.

534
00:44:15,730 --> 00:44:24,000
Takže teraz, že sme v tomto bode, teraz kroku dve radiť zlúčenie je len zlúčenie dvojice zoznamov.

535
00:44:24,000 --> 00:44:27,610
Takže chceme zlúčiť tieto. Práve sme zavolať zlúčenie.

536
00:44:27,610 --> 00:44:31,410
Vieme, že zlúčenie sa vrátiť tieto v zoradené poradí.

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

538
00:44:33,920 --> 00:44:41,440
Teraz chceme zlúčiť tieto, a že vráti zoznam s tými v zoradenie poradí,

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

540
00:44:44,160 --> 00:44:57,380
Spojíme ty - Nemôžem písať - 8, 23 a 42, 108.

541
00:44:57,380 --> 00:45:02,890
Takže máme zlúčené dvojica raz.

542
00:45:02,890 --> 00:45:05,140
Teraz už len zlúčiť znovu.

543
00:45:05,140 --> 00:45:10,130
Všimnite si, že každý z týchto zoznamov je zoradená v sebe,

544
00:45:10,130 --> 00:45:15,220
a potom môžeme len zlúčiť tieto zoznamy získať zoznam veľkosti 4, ktorý je zoradená

545
00:45:15,220 --> 00:45:19,990
a spojiť tieto dva zoznamy získať zoznam veľkosti 4, ktorá je zoradená.

546
00:45:19,990 --> 00:45:25,710
A konečne, môžeme zlúčiť tieto dva zoznamy veľkosti 4, aby si jeden zoznam veľkosti 8, ktorá je zoradená.

547
00:45:25,710 --> 00:45:34,030
Takže vidieť, že je to celkovo n log n, už sme videli, že zlúčenie je lineárne,

548
00:45:34,030 --> 00:45:40,390
takže keď máme čo do činenia s zlúčením táto, takže rovnako ako celkové náklady na zlúčenie

549
00:45:40,390 --> 00:45:43,410
týchto dvoch zoznamov je len 2, pretože -

550
00:45:43,410 --> 00:45:49,610
Alebo dobre, je to O n, ale n je tu len tieto 2 prvky, takže je to 2.

551
00:45:49,610 --> 00:45:52,850
A tieto 2 bude 2 a tieto 2 bude 2 a tieto 2 bude 2,

552
00:45:52,850 --> 00:45:58,820
takže cez všetky splýva, ktoré musíme urobiť, sme sa nakoniec robiť n

553
00:45:58,820 --> 00:46:03,210
Ako 2 + 2 + 2 + 2 je 8, čo je n,

554
00:46:03,210 --> 00:46:08,060
takže náklady na zlúčenie v tejto sade je n

555
00:46:08,060 --> 00:46:10,810
A potom to isté tu.

556
00:46:10,810 --> 00:46:16,980
Budeme zlúčenie týchto 2, potom tieto 2, a osobne to zlúčenie bude trvať štyri operácie,

557
00:46:16,980 --> 00:46:23,610
to zlúčenie bude trvať štyri operácie, ale opäť, medzi všetkými z nich,

558
00:46:23,610 --> 00:46:29,030
sme sa nakoniec zlučovanie n celkom veci, a tak tento krok trvá n

559
00:46:29,030 --> 00:46:33,670
A tak každá úroveň má n prvkov je zlúčené.

560
00:46:33,670 --> 00:46:36,110
>> A koľko úrovní je tam?

561
00:46:36,110 --> 00:46:40,160
Na každej úrovni, naše pole rastie podľa veľkosti 2.

562
00:46:40,160 --> 00:46:44,590
Tu naše polia sú veľkosti 1, tu sú veľkosti 2, tu sú veľkosti 4,

563
00:46:44,590 --> 00:46:46,470
a napokon, sú veľkosti 8.

564
00:46:46,470 --> 00:46:56,450
Takže, pretože to je zdvojenie, tam sa bude celkom log n z týchto úrovní.

565
00:46:56,450 --> 00:47:02,090
Takže s log n úrovní, každá jednotlivá úroveň pričom n celkom operácie,

566
00:47:02,090 --> 00:47:05,720
dostaneme log n n algoritmus.

567
00:47:05,720 --> 00:47:07,790
Otázky?

568
00:47:08,940 --> 00:47:13,320
Ľudia už dosiahla pokrok v tom, ako to urobiť čo?

569
00:47:13,320 --> 00:47:18,260
Je niekto už v stave, kedy som si len vytiahnuť svoj kód?

570
00:47:20,320 --> 00:47:22,260
Môžem dať chvíľku.

571
00:47:24,770 --> 00:47:27,470
Tento bude dlhší.

572
00:47:27,470 --> 00:47:28,730
Vrelo odporúčam opakovať -

573
00:47:28,730 --> 00:47:30,510
Nemusíte robiť rekurziu pre zlúčenie

574
00:47:30,510 --> 00:47:33,750
pretože robiť rekurziu pre zlúčenie, budete musieť prejsť veľa rôznych veľkostí.

575
00:47:33,750 --> 00:47:37,150
Môžete, ale je to otravné.

576
00:47:37,150 --> 00:47:43,720
Ale rekurzia pre radiť sám o sebe je celkom jednoduché.

577
00:47:43,720 --> 00:47:49,190
Stačí zavolať doslova akousi na ľavej polovici, sort na pravej polovici. Dobre.

578
00:47:51,770 --> 00:47:54,860
Každý, kto má niečo, čo som si vytiahnuť hore?

579
00:47:54,860 --> 00:47:57,540
Inak ja dám minútku.

580
00:47:58,210 --> 00:47:59,900
Dobre.

581
00:47:59,900 --> 00:48:02,970
Každý, kto má niečo, čo môžeme pracovať s?

582
00:48:05,450 --> 00:48:09,680
Inak budeme len s týmto pracujete a potom rozbaľte odtiaľ.

583
00:48:09,680 --> 00:48:14,050
>> Každý, kto má viac než to, že som si vytiahnuť?

584
00:48:14,050 --> 00:48:17,770
[Študent] Jo. Môžete vytiahnuť moje. >> Dobre.

585
00:48:17,770 --> 00:48:19,730
Áno!

586
00:48:22,170 --> 00:48:25,280
[Študent] Bola tam kopa podmienok. >> Oh, strieľať. Môžeš -

587
00:48:25,280 --> 00:48:28,110
[Študent] Musím zachrániť ju. Jo >>.

588
00:48:32,420 --> 00:48:35,730
Tak sme urobili to zlúčenie oddelene.

589
00:48:35,730 --> 00:48:38,570
Oh, ale to nie je tak zlé.

590
00:48:39,790 --> 00:48:41,650
Dobre.

591
00:48:41,650 --> 00:48:47,080
Takže druh je sám o sebe len volanie mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Vysvetlite nám, čo mergeSortHelp robí.

593
00:48:49,530 --> 00:48:55,700
[Študent] MergeSortHelp celkom veľa robí dva hlavné kroky,

594
00:48:55,700 --> 00:49:01,270
ktorý je vyriešiť každú polovicu poľa a potom zlúčiť oba.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Dobre, tak mi za sekundu.

596
00:49:10,850 --> 00:49:13,210
Myslím, že to - >> [Študent] musím -

597
00:49:17,100 --> 00:49:19,400
Jo. Som niečo chýba.

598
00:49:19,400 --> 00:49:23,100
V zlúčenie, som si uvedomil, že musím vytvoriť nové pole

599
00:49:23,100 --> 00:49:26,530
pretože som nemohol urobiť to na mieste. Áno >>. Nemôžete. Opraviť.

600
00:49:26,530 --> 00:49:28,170
[Študent] Tak som vytvoriť nové pole.

601
00:49:28,170 --> 00:49:31,510
Zabudol na konci sa ponorí znovu zmeniť.

602
00:49:31,510 --> 00:49:34,490
Dobre. Potrebujeme nové pole.

603
00:49:34,490 --> 00:49:41,000
V radiť zlučovacie, je to takmer vždy pravda.

604
00:49:41,000 --> 00:49:44,340
Časť nákladov na lepšiu algoritmu časovo

605
00:49:44,340 --> 00:49:47,310
je takmer vždy museli použiť trochu viac pamäte.

606
00:49:47,310 --> 00:49:51,570
Tak tu, bez ohľadu na to, ako to robíš zlúčiť druh,

607
00:49:51,570 --> 00:49:54,780
budete nevyhnutne potrebovať nejaké extra pamäť.

608
00:49:54,780 --> 00:49:58,240
On alebo ona vytvorila nové pole.

609
00:49:58,240 --> 00:50:03,400
A potom povieš na konci sme stačí skopírovať nové pole do pôvodného poľa.

610
00:50:03,400 --> 00:50:04,830
[Študent] Myslím, že áno, jo.

611
00:50:04,830 --> 00:50:08,210
Neviem, či to funguje, pokiaľ ide o počítanie odkazu alebo čokoľvek iné -

612
00:50:08,210 --> 00:50:11,650
Jo, bude to fungovať. >> [Študent] Dobre.

613
00:50:20,620 --> 00:50:24,480
Bolo pre vás skúste to? >> [Študent] Nie, ešte nie. Dobre >>.

614
00:50:24,480 --> 00:50:28,880
Skúste ju spustiť, a potom budem hovoriť o tom na chvíľu.

615
00:50:28,880 --> 00:50:35,200
[Študent] Musím mať všetky funkčné prototypy a všetko, že jo?

616
00:50:37,640 --> 00:50:40,840
Funkčné prototypy. Oh, myslíš ako - Áno.

617
00:50:40,840 --> 00:50:43,040
Zoradiť volá mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Tak, aby pre radenie volať mergeSortHelp, musí mergeSortHelp buď boli definované

619
00:50:47,390 --> 00:50:56,370
pred radiť alebo si len potrebujete prototyp. Stačí len skopírovať a vložiť, že.

620
00:50:56,370 --> 00:50:59,490
A podobne, mergeSortHelp volá zlúčenie,

621
00:50:59,490 --> 00:51:03,830
ale merge nie je doteraz definované, takže sa môžeme len nechať mergeSortHelp vedieť

622
00:51:03,830 --> 00:51:08,700
že to, čo zlúčenie bude vyzerať, a tým to hasne.

623
00:51:09,950 --> 00:51:15,730
Tak mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Máme problém, tu, kde nemáme základnú vec.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp je rekurzívny, takže každý rekurzívne funkcie

626
00:51:38,110 --> 00:51:42,610
bude potrebovať nejaký základné veci vedieť, kedy prestať rekurzívne volať sám.

627
00:51:42,610 --> 00:51:45,590
Čo je náš základný scenár bude tu? Jo.

628
00:51:45,590 --> 00:51:49,110
[Študent] Ak je veľkosť 1? >> [Bowden] Áno.

629
00:51:49,110 --> 00:51:56,220
Tak ako sme videli tu, zastavili sme sa rozdelenie poľa

630
00:51:56,220 --> 00:52:01,850
Akonáhle sme sa dostali do polí veľkosti 1, čo nevyhnutne sú zoradené sami.

631
00:52:01,850 --> 00:52:09,530
Takže ak veľkosť zodpovedá 1, vieme, že pole už je zoradený,

632
00:52:09,530 --> 00:52:12,970
takže môžeme len vrátiť.

633
00:52:12,970 --> 00:52:16,880
>> Všimnite si, že je neplatné, a tak sme sa nevracia nič konkrétneho, len sme sa vrátiť.

634
00:52:16,880 --> 00:52:19,580
Dobre. Tak to je náš základný scenár.

635
00:52:19,580 --> 00:52:27,440
Myslím, že náš základný scenár by tiež mohla byť, keby sme sa náhodou zlúčenie poľa veľkosti 0,

636
00:52:27,440 --> 00:52:30,030
sme asi chcú zastaviť na nejakom mieste,

637
00:52:30,030 --> 00:52:33,610
takže stačí povedať veľkosti menšej ako 2 alebo nižšia ako alebo rovná 1

638
00:52:33,610 --> 00:52:37,150
tak, že to bude fungovať za každé pole sa.

639
00:52:37,150 --> 00:52:38,870
Dobre.

640
00:52:38,870 --> 00:52:42,740
Tak to je náš základný scenár.

641
00:52:42,740 --> 00:52:45,950
Teraz už chcete chodiť nás cez zlúčenie?

642
00:52:45,950 --> 00:52:49,140
Čo všetky tieto prípady znamenajú?

643
00:52:49,140 --> 00:52:54,480
Až tu, my sme len robí rovnakú myšlienku, -

644
00:52:56,970 --> 00:53:02,470
[Študent] musím byť okolo veľkosti so všetkými hovory mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Pridal som veľkosť ako ďalšie primárne a nie je to tam, ako je veľkosť / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, veľkosť / 2, veľkosť / 2. >> [Študent] Jo, a tiež vo vyššie uvedenom funkciu.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Tu? >> [Študent] Len veľkosť. >> [Bowden] Oh. Veľkosť, veľkosť? >> [Študent] Jo.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Dobre.

649
00:53:23,010 --> 00:53:26,580
Nechajte ma premýšľať o sekundu.

650
00:53:26,580 --> 00:53:28,780
Páči narazíme na problém?

651
00:53:28,780 --> 00:53:33,690
Sme vždy zaobchádzať ľavici ako 0. >> [Študent] č

652
00:53:33,690 --> 00:53:36,340
To je zle taky. Prepáčte. Malo by to byť začiatok. Jo.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Dobre. Páči sa mi, že lepšie.

654
00:53:39,230 --> 00:53:43,880
A koniec. Dobre.

655
00:53:43,880 --> 00:53:47,200
Takže teraz chceš prejsť nám prostredníctvom zlúčenie? >> [Študent] Dobre.

656
00:53:47,200 --> 00:53:52,150
Len som prechádzal tohto nového poľa, ktoré som vytvoril.

657
00:53:52,150 --> 00:53:57,420
Jeho veľkosť je veľkosť časti poľa, ktoré chceme triediť

658
00:53:57,420 --> 00:54:03,460
a snaží sa nájsť prvok, ktorý by som mal dať v novom poľa kroku.

659
00:54:03,460 --> 00:54:10,140
Tak k tomu, že v prvej som kontrole, či ľavá polovica poľa pokračuje mať žiadne ďalšie prvky,

660
00:54:10,140 --> 00:54:14,260
a ak tomu tak nie je, potom ísť dole k tomuto inému stavu, ktorý práve hovorí, že

661
00:54:14,260 --> 00:54:20,180
v poriadku, musí byť v pravom poli, a dáme, že v súčasnej indexu newArray.

662
00:54:20,180 --> 00:54:27,620
>> A potom inak, ja som kontrolu, či pravá strana pole je tiež skončil,

663
00:54:27,620 --> 00:54:30,630
v takom prípade som dal v ľavej.

664
00:54:30,630 --> 00:54:34,180
To by mohlo byť skutočne nutné. Nie som si istý.

665
00:54:34,180 --> 00:54:40,970
Ale rovnako, ďalšie dva kontrola, ktorú z tých dvoch sa menšie doľava alebo doprava.

666
00:54:40,970 --> 00:54:49,770
A tiež v každom prípade, ja navýšením podľa toho, čo zástupný Aj zvyšovať.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Dobre.

668
00:54:52,040 --> 00:54:53,840
To vyzerá dobre.

669
00:54:53,840 --> 00:54:58,800
Má niekto nejaké pripomienky alebo obavy alebo otázky?

670
00:55:00,660 --> 00:55:07,720
Takže štyri prípady, ktoré musíme priviesť veci do jednoduchého bytia - alebo to vyzerá ako päť -

671
00:55:07,720 --> 00:55:13,100
ale musíme zvážiť, či doľava pole je vyčerpať čo musíme zlúčiť,

672
00:55:13,100 --> 00:55:16,390
či právo pole je vyčerpať čo musíme zlúčiť -

673
00:55:16,390 --> 00:55:18,400
Som ukázal na nič.

674
00:55:18,400 --> 00:55:21,730
Takže nech ľavej pole došla veci alebo právo poľa došiel vecí.

675
00:55:21,730 --> 00:55:24,320
To sú dva prípady.

676
00:55:24,320 --> 00:55:30,920
Potrebujeme tiež triviálne prípad, či ľavica, čo je menšie ako správnu vec.

677
00:55:30,920 --> 00:55:33,910
Potom chceme zvoliť ľavej vec.

678
00:55:33,910 --> 00:55:37,630
To sú prípady.

679
00:55:37,630 --> 00:55:40,990
Tak toto mal pravdu, tak je to.

680
00:55:40,990 --> 00:55:46,760
Array vľavo. Je to 1, 2, 3. Dobre. Tak jo, to sú štyri veci, ktoré sme mohli chcieť robiť.

681
00:55:50,350 --> 00:55:54,510
A nebudeme ísť cez iteračné riešenie.

682
00:55:54,510 --> 00:55:55,980
Neodporúčal by som -

683
00:55:55,980 --> 00:56:03,070
Zlúčenie druh je príklad funkcie, ktorá je ako to chvost rekurzívne,

684
00:56:03,070 --> 00:56:07,040
to nie je ľahké, aby sa to tail rekurzívne,

685
00:56:07,040 --> 00:56:13,450
ale tiež to nie je ľahké, aby sa to iteratívny.

686
00:56:13,450 --> 00:56:16,910
To je veľmi jednoduché.

687
00:56:16,910 --> 00:56:19,170
Táto implementácia druhu korešpondencie,

688
00:56:19,170 --> 00:56:22,140
zlúčenie, bez ohľadu na to, čo robíte, budete stavať zlúčenie.

689
00:56:22,140 --> 00:56:29,170
>> Takže zlúčiť druh postavený na vrchole zlúčenie rekurzívne je práve táto tri riadky.

690
00:56:29,170 --> 00:56:34,700
Iteratívne, je to viac nepríjemné a ťažké premýšľať o

691
00:56:34,700 --> 00:56:41,860
Ale všimnite si, že to nie je chvost rekurzívny, pretože mergeSortHelp - keď to sama hovorí -

692
00:56:41,860 --> 00:56:46,590
stále musí robiť veci po tomto rekurzívne volanie vráti.

693
00:56:46,590 --> 00:56:50,830
Takže to stack frame musí naďalej existovať aj po volaní tejto.

694
00:56:50,830 --> 00:56:54,170
A potom, keď budete volať, musí stack frame naďalej existovať

695
00:56:54,170 --> 00:56:57,780
pretože aj po tomto hovoru, stále potrebujeme zlúčiť.

696
00:56:57,780 --> 00:57:01,920
A to je triviálne, aby sa tento chvost rekurzívne.

697
00:57:04,070 --> 00:57:06,270
Otázky?

698
00:57:08,300 --> 00:57:09,860
Dobrá.

699
00:57:09,860 --> 00:57:13,400
Takže návrat k radenia - oh, sú dve veci, ktoré chcem ukázať. Dobre.

700
00:57:13,400 --> 00:57:17,840
Vráťme sa späť k druhu, urobíme to rýchlo.

701
00:57:17,840 --> 00:57:21,030
Alebo hľadajte. Radiť? Zoradiť. Jo.

702
00:57:21,030 --> 00:57:22,730
Vráťme sa späť do začiatkov druhu.

703
00:57:22,730 --> 00:57:29,870
Chceme vytvoriť algoritmus, ktorý triedi pole pomocou ľubovoľného algoritmu

704
00:57:29,870 --> 00:57:33,660
v O n

705
00:57:33,660 --> 00:57:40,860
Tak, ako je to možné? Má niekto nejaký druh -

706
00:57:40,860 --> 00:57:44,300
Som naznačil skôr u -

707
00:57:44,300 --> 00:57:48,300
Ak sa chystáme zlepšenie z n log n na O n,

708
00:57:48,300 --> 00:57:51,450
sme zlepšili naše algoritmus časovo,

709
00:57:51,450 --> 00:57:55,250
čo znamená, že to, čo budeme musieť urobiť, aby sa na to?

710
00:57:55,250 --> 00:57:59,520
[Študent] Space. Jo >>. Budeme používať viac priestoru.

711
00:57:59,520 --> 00:58:04,490
A to aj len viac priestoru, je to exponenciálne viac priestoru.

712
00:58:04,490 --> 00:58:14,320
Takže si myslím, tento typ algoritmu je pseudo niečo, pseudo polynómov -

713
00:58:14,320 --> 00:58:18,980
pseudo - Nemôžem si spomenúť. Pseudo niečo.

714
00:58:18,980 --> 00:58:22,210
Ale je to preto, že musíme použiť toľko priestoru

715
00:58:22,210 --> 00:58:28,610
že to možno dosiahnuť, ale nie je reálne.

716
00:58:28,610 --> 00:58:31,220
>> A ako môžeme dosiahnuť?

717
00:58:31,220 --> 00:58:36,810
Toho môžeme dosiahnuť, ak sa zaručí, že určitá element v poli

718
00:58:36,810 --> 00:58:39,600
pod určitú veľkosť.

719
00:58:42,070 --> 00:58:44,500
Takže povedzme, že veľkosť je 200,

720
00:58:44,500 --> 00:58:48,130
akýkoľvek prvok v poli je nižšia ako veľkosť 200.

721
00:58:48,130 --> 00:58:51,080
A to je skutočne veľmi realistický.

722
00:58:51,080 --> 00:58:58,660
Môžete veľmi ľahko mať pole, ktoré viete, že všetko, čo v ňom

723
00:58:58,660 --> 00:59:00,570
bude menší ako nejaké číslo.

724
00:59:00,570 --> 00:59:07,400
Ako keď mám nejaký úplne masívne vektor, alebo tak niečo

725
00:59:07,400 --> 00:59:11,810
ale viete, všetko bude medzi 0 a 5,

726
00:59:11,810 --> 00:59:14,790
potom to bude výrazne rýchlejší urobiť.

727
00:59:14,790 --> 00:59:17,930
A viazané na niektorý z prvkov je 5,

728
00:59:17,930 --> 00:59:21,980
tak tento odhad, že je to, ako moc pamäte budete používať.

729
00:59:21,980 --> 00:59:26,300
Takže viazaný je 200.

730
00:59:26,300 --> 00:59:32,960
Teoreticky je vždy viazaný od celé číslo môže byť až 4000000000,

731
00:59:32,960 --> 00:59:40,600
ale to je nereálne, pretože potom by sme používať miesto

732
00:59:40,600 --> 00:59:44,400
na poradie 4000000000. Tak to je nereálne.

733
00:59:44,400 --> 00:59:47,060
Ale tu budeme hovoriť naše viazaný je 200.

734
00:59:47,060 --> 00:59:59,570
Trik, ako to robí v O n je urobíme ďalšie pole s názvom počty veľkosti VIAZANIA.

735
00:59:59,570 --> 01:00:10,470
Takže vlastne, to je skratka pre - Ja vlastne neviem, či zvonenie to robí.

736
01:00:11,150 --> 01:00:15,330
Ale v GCC na prinajmenšom - Som za predpokladu, že zvonenie to robí taky -

737
01:00:15,330 --> 01:00:18,180
to bude len inicializácii celého poľa, aby sa 0s.

738
01:00:18,180 --> 01:00:25,320
Takže ak nechcem robiť, potom by som mohol samostatne urobiť for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <Bound; i + +) a počíta [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Takže teraz je všetko inicializovaná na 0.

741
01:00:35,260 --> 01:00:39,570
Aj iterácii svoje pole,

742
01:00:39,570 --> 01:00:51,920
a to, čo robím, je počítam počet každého - Poďme sem.

743
01:00:51,920 --> 01:00:55,480
Máme 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Čo Počítam je počet výskytov každého z týchto prvkov.

745
01:01:00,010 --> 01:01:03,470
Poďme skutočne pridať pár ďalších tu s niektorými opakovania.

746
01:01:03,470 --> 01:01:11,070
Takže hodnota, ktorú máme, je hodnota, ktorá bude pole [i].

747
01:01:11,070 --> 01:01:14,850
Takže val by mohol byť 4 alebo 8 alebo čokoľvek iného.

748
01:01:14,850 --> 01:01:18,870
A teraz som počítať, koľko z tejto hodnoty som videl,

749
01:01:18,870 --> 01:01:21,230
takže sa počíta [val] + +;

750
01:01:21,230 --> 01:01:29,430
Po to urobiť, počíta sa bude vyzerať ako 0001.

751
01:01:29,430 --> 01:01:42,190
Poďme urobiť počíta [val] - RIADIŤ + 1.

752
01:01:42,190 --> 01:01:48,230
>> Teraz to je len zodpovedať za to, že sme počnúc 0.

753
01:01:48,230 --> 01:01:50,850
Takže ak 200 bude naše najväčšie číslo,

754
01:01:50,850 --> 01:01:54,720
potom 0-200 je 201 vecí.

755
01:01:54,720 --> 01:02:01,540
Takže sa počíta, bude to vyzerať, ako 00001, pretože máme jeden 4.

756
01:02:01,540 --> 01:02:10,210
Potom budeme mať 0001, kde budeme mať 1 v 8. indexu počtu.

757
01:02:10,210 --> 01:02:14,560
Budeme mať 2 v 23. indexu počtu.

758
01:02:14,560 --> 01:02:17,630
Budeme mať 2 v indexe 42. počte.

759
01:02:17,630 --> 01:02:21,670
Takže môžeme použiť počet.

760
01:02:34,270 --> 01:02:44,920
Takže num_of_item = počíta [i].

761
01:02:44,920 --> 01:02:52,540
A ak num_of_item je 2, to znamená, že chceme vložiť 2 z počtu i

762
01:02:52,540 --> 01:02:55,290
do nášho triedenom poli.

763
01:02:55,290 --> 01:03:02,000
Takže musíme sledovať, ako ďaleko sme sa do poľa.

764
01:03:02,000 --> 01:03:05,470
Takže index = 0.

765
01:03:05,470 --> 01:03:09,910
Array - budem len písať.

766
01:03:16,660 --> 01:03:18,020
Počty -

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i;

768
01:03:28,580 --> 01:03:32,490
Je to to, čo chcem? Myslím, že je to to, čo chcem.

769
01:03:35,100 --> 01:03:38,290
Áno, to vyzerá dobre. Dobre.

770
01:03:38,290 --> 01:03:43,050
Takže si všetci pochopili, čo je cieľom mojej počíta pole je?

771
01:03:43,050 --> 01:03:48,140
To počíta počet výskytov každého z týchto čísel.

772
01:03:48,140 --> 01:03:51,780
Potom som iterácie, ktorá sa počíta polia,

773
01:03:51,780 --> 01:03:57,190
a tá pozícia v poli sa počíta

774
01:03:57,190 --> 01:04:01,930
je počet aj to, že by sa mal objaviť v mojom triedenom poli.

775
01:04:01,930 --> 01:04:06,840
To je dôvod, prečo sa počty 4 bude 1

776
01:04:06,840 --> 01:04:11,840
a počty 8 bude 1, počty 23 bude 2.

777
01:04:11,840 --> 01:04:16,900
Tak to je, koľko z nich chcem vložiť do môjho triedenom poli.

778
01:04:16,900 --> 01:04:19,200
Potom som to.

779
01:04:19,200 --> 01:04:28,960
Som vloženie num_of_item aj to do môjho triedenom poli.

780
01:04:28,960 --> 01:04:31,670
>> Otázky?

781
01:04:32,460 --> 01:04:43,100
A tak opäť, je to lineárny čas, pretože sme sa práve iterácia cez to raz,

782
01:04:43,100 --> 01:04:47,470
ale je to tiež lineárna v tom, čo toto číslo sa stane byť,

783
01:04:47,470 --> 01:04:50,730
a tak to silne závisí na tom, čo je viazaný.

784
01:04:50,730 --> 01:04:53,290
S viazaný na 200, to nie je tak zlé.

785
01:04:53,290 --> 01:04:58,330
Ak váš viazaný bude 10.000, potom je to trochu horšie,

786
01:04:58,330 --> 01:05:01,360
ale ak vaša spojený sa bude 4000000000, to je absolútne nereálne

787
01:05:01,360 --> 01:05:07,720
a toto pole bude musieť byť veľkosti 4 miliardy korún, čo je nereálne.

788
01:05:07,720 --> 01:05:10,860
Tak to je to. Otázky?

789
01:05:10,860 --> 01:05:13,270
[Nepočuteľné Študent odpoveď] >> Dobre.

790
01:05:13,270 --> 01:05:15,710
Uvedomil som si, jednu vec, keď sme išli cez.

791
01:05:17,980 --> 01:05:23,720
Myslím, že problém bol v Lucasovi a pravdepodobne jeden každý sme videli.

792
01:05:23,720 --> 01:05:26,330
Úplne som zabudla.

793
01:05:26,330 --> 01:05:31,040
Jediné, čo som chcel vyjadriť, je, že keď máte čo do činenia s vecami, ako je indexov,

794
01:05:31,040 --> 01:05:38,320
nikdy naozaj vidieť, keď píšete pre sláčiky,

795
01:05:38,320 --> 01:05:41,120
ale technicky, keď máte čo do činenia s týmito indexy,

796
01:05:41,120 --> 01:05:45,950
mali by ste skoro vždy riešiť s celých čísel bez znamienka.

797
01:05:45,950 --> 01:05:53,850
Dôvodom pre to je, keď máte čo do činenia s podpísanými celé čísla,

798
01:05:53,850 --> 01:05:56,090
takže ak máte 2 podpísané celé čísla a pridajte ich spolu

799
01:05:56,090 --> 01:06:00,640
a oni skončí príliš veľké, potom vy skončíte s záporné číslo.

800
01:06:00,640 --> 01:06:03,410
Takže to je to, čo integer overflow je.

801
01:06:03,410 --> 01:06:10,500
>> Ak môžem pridať 2000000000 a 1000000000, som skončiť s negatívnym 1000000000.

802
01:06:10,500 --> 01:06:15,480
To je, ako celé čísla pracovať na počítačoch.

803
01:06:15,480 --> 01:06:17,510
Takže problém s použitím -

804
01:06:17,510 --> 01:06:23,500
To je v poriadku s výnimkou prípadov nízka stane byť 2 miliardy až sa stane na 1 mld Sk,

805
01:06:23,500 --> 01:06:27,120
potom bude negatívne 1 miliarda a potom budeme deliť, že 2

806
01:06:27,120 --> 01:06:29,730
a skončiť s negatívnym 500000000.

807
01:06:29,730 --> 01:06:33,760
Tak toto je len problém, ak sa stalo, že sa hľadá cez pole

808
01:06:33,760 --> 01:06:38,070
miliárd vecí.

809
01:06:38,070 --> 01:06:44,050
Ale ak low + až sa stane pretečeniu, potom je to problém.

810
01:06:44,050 --> 01:06:47,750
Akonáhle sme, aby boli nesignováno, potom 2 miliárd eur 1000000000 je 3 mld Sk.

811
01:06:47,750 --> 01:06:51,960
3000000000 deleno 2 je 1,5 mld Sk.

812
01:06:51,960 --> 01:06:55,670
Takže akonáhle to unsigned, všetko je perfektné.

813
01:06:55,670 --> 01:06:59,900
A tak to aj problém, keď ste písanie pre slučky,

814
01:06:59,900 --> 01:07:03,940
a vlastne, to asi robí to automaticky.

815
01:07:09,130 --> 01:07:12,330
To bude vlastne len kričať na vás.

816
01:07:12,330 --> 01:07:21,610
Takže ak toto číslo je príliš veľký, aby sa počas jedinej celé číslo, ale to by sa zmestili do celé číslo bez znamienka,

817
01:07:21,610 --> 01:07:24,970
bude kričať na teba, tak to je dôvod, prečo ste nikdy naraziť na problém.

818
01:07:29,150 --> 01:07:34,820
Môžete vidieť, že index je nikdy nebude negatívne,

819
01:07:34,820 --> 01:07:39,220
a tak, keď ste iterácia cez pole,

820
01:07:39,220 --> 01:07:43,970
môžete takmer vždy povedať, unsigned int i, ale nemáte naozaj musieť.

821
01:07:43,970 --> 01:07:47,110
Veci idú do práce skoro rovnako dobre.

822
01:07:48,740 --> 01:07:50,090
Dobre. [Šepká] Aký je čas?

823
01:07:50,090 --> 01:07:54,020
Posledná vec, ktorú som chcel ukázať - a ja to jednoducho urobiť to naozaj rýchlo.

824
01:07:54,020 --> 01:08:03,190
Vieš, ako sme # define, takže môžeme # define MAX ako 5 alebo tak niečo?

825
01:08:03,190 --> 01:08:05,940
Poďme to urobiť MAX. # Define viazaný ako 200. To je to, čo sme robili pred.

826
01:08:05,940 --> 01:08:10,380
To definuje konštantu, ktorá je len tak skopírovať a vložiť

827
01:08:10,380 --> 01:08:13,010
všade tam, kde sa stalo písať VIAZANIA.

828
01:08:13,010 --> 01:08:18,189
>> Takže môžeme skutočne urobiť viac s # definuje.

829
01:08:18,189 --> 01:08:21,170
Môžeme # define funkcie.

830
01:08:21,170 --> 01:08:23,410
Sú to naozaj funguje, ale budeme im hovoriť funkcie.

831
01:08:23,410 --> 01:08:36,000
Príkladom by mohol byť niečo ako MAX (x, y) je definovaná ako (x <y y:? X). Dobre.

832
01:08:36,000 --> 01:08:40,660
Takže by ste mali zvyknúť na syntax ternárnu operátor,

833
01:08:40,660 --> 01:08:49,029
ale je x menšie ako y? Návrat y, inak vráti x.

834
01:08:49,029 --> 01:08:54,390
Takže môžete vidieť, môžete túto samostatnú funkciu,

835
01:08:54,390 --> 01:09:01,399
a funkcia môže byť ako bool MAX trvá 2 argumenty, vrátiť.

836
01:09:01,399 --> 01:09:08,340
To je jeden z najčastejších z nich vidím urobil takhle. Hovoríme im makrá.

837
01:09:08,340 --> 01:09:11,790
To je makro.

838
01:09:11,790 --> 01:09:15,859
To je len syntaxe pre neho.

839
01:09:15,859 --> 01:09:18,740
Môžete napísať makro robiť, čo chcete.

840
01:09:18,740 --> 01:09:22,649
Tie často vidieť makrá pre ladenie printfs a tak.

841
01:09:22,649 --> 01:09:29,410
Takže typu printf, existujú špeciálne konštanty v C ako podčiarknutie LINE podčiarkovník,

842
01:09:29,410 --> 01:09:31,710
2 podčiarkuje LINE podčiarkovník,

843
01:09:31,710 --> 01:09:37,550
a tam je tiež myslím, že 2 podčiarkovníky FUNC. To by mohlo byť ono. Niečo také.

844
01:09:37,550 --> 01:09:40,880
Tieto veci budú nahradené s názvom funkcie

845
01:09:40,880 --> 01:09:42,930
alebo číslo linky, ktoré ste na.

846
01:09:42,930 --> 01:09:48,630
Často, môžete napísať ladenie printfs, že tu dole som mohol potom len napísať

847
01:09:48,630 --> 01:09:54,260
DEBUG a vytlačí sa číslo riadku a funkcie, ktoré som náhodou byť v

848
01:09:54,260 --> 01:09:57,020
že došlo, že DEBUG vyhlásenie.

849
01:09:57,020 --> 01:09:59,550
A môžete tiež vytlačiť iné veci.

850
01:09:59,550 --> 01:10:05,990
Takže jedna vec, ktorú by mal dávať pozor, je, či som náhodou # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
niečo ako 2 * y a 2 * x.

852
01:10:11,380 --> 01:10:14,310
Takže z akéhokoľvek dôvodu, ste náhodou k tomu, že veľa.

853
01:10:14,310 --> 01:10:16,650
Tak, aby to makro.

854
01:10:16,650 --> 01:10:18,680
To je skutočne zlomené.

855
01:10:18,680 --> 01:10:23,050
Nazval by som to tým, že robí niečo ako DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Takže to, čo by mala byť vrátená?

857
01:10:28,840 --> 01:10:30,580
[Študent] 12.

858
01:10:30,580 --> 01:10:34,800
Áno, mala 12 byť vrátené, a 12 je vrátená.

859
01:10:34,800 --> 01:10:43,350
3 bude nahradené za x, dostane 6 nahrádza pre y, a vraciame sa 2 * 6, ktorá je 12.

860
01:10:43,350 --> 01:10:47,710
Teraz čo toto? Čo by sa malo vrátiť?

861
01:10:47,710 --> 01:10:50,330
[Študent] 14. V ideálnom prípade >>, 14.

862
01:10:50,330 --> 01:10:55,290
Problém je, že ako hash definuje prácu, pamätajte, že je to doslovný kopírovanie a vkladanie

863
01:10:55,290 --> 01:11:00,160
zo dňa skoro všetko, takže to, čo to bude vykladať ako

864
01:11:00,160 --> 01:11:11,270
je 3 menej ako 1 plus 6, 2 krát 1 plus 6, 2 krát 3.

865
01:11:11,270 --> 01:11:19,780
>> Takže z tohto dôvodu takmer vždy zabaliť všetko v zátvorkách.

866
01:11:22,180 --> 01:11:25,050
Akákoľvek premenná takmer vždy zabaliť v zátvorkách.

867
01:11:25,050 --> 01:11:29,570
Existujú prípady, keď nemáte k, ako ja viem, že nemám potrebu k tomu, že tu

868
01:11:29,570 --> 01:11:32,110
pretože menej, než je do značnej miery vždy len chodiť do práce,

869
01:11:32,110 --> 01:11:34,330
aj keď to nemusí byť dokonca pravda.

870
01:11:34,330 --> 01:11:41,870
Ak je niečo smiešne ako DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
potom, že sa to byť nahradený s 3 menej ako 1 rovná rovná 2,

872
01:11:49,760 --> 01:11:53,460
a tak potom to bude robiť 3 menej ako 1, to, že rovné 2,

873
01:11:53,460 --> 01:11:55,620
čo je to, čo chceme.

874
01:11:55,620 --> 01:12:00,730
Tak, aby sa zabránilo operátor prednosť problémy,

875
01:12:00,730 --> 01:12:02,870
vždy zabaľte v zátvorkách.

876
01:12:03,290 --> 01:12:07,700
Dobre. A to je to, 5:30.

877
01:12:08,140 --> 01:12:12,470
Ak máte akékoľvek otázky týkajúce sa PSet, dajte nám vedieť.

878
01:12:12,470 --> 01:12:18,010
To by mala byť zábava, a hacker vydanie je tiež oveľa realistickejšie

879
01:12:18,010 --> 01:12:22,980
ako hackerské vydanie v minulom roku, tak dúfame, že veľa z vás to skúsiť.

880
01:12:22,980 --> 01:12:26,460
V minulom roku to bol veľmi zdrvujúce.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]