1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Oddíl 3 - Další 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 první otázka je podivně zní.

5
00:00:12,700 --> 00:00:17,480
GDB umožňuje "ladit" program, ale konkrétně, co to nechat udělat?

6
00:00:17,480 --> 00:00:22,590
Budu odpovědět, že jeden, a já nevím, co to přesně očekává,

7
00:00:22,590 --> 00:00:27,910
takže hádám, že je to něco v duchu to umožňuje krok za krokem

8
00:00:27,910 --> 00:00:31,540
projít programu, pracovat s ním, změna proměnných, dělat všechny tyto věci -

9
00:00:31,540 --> 00:00:34,270
v podstatě kompletně ovládat provádění programu

10
00:00:34,270 --> 00:00:38,410
a zkontrolujte, zda na dané části realizace programu.

11
00:00:38,410 --> 00:00:43,030
Takže tyto funkce vám umožní ladit věci.

12
00:00:43,030 --> 00:00:44,830
Dobře.

13
00:00:44,830 --> 00:00:50,520
Proč binární hledání vyžaduje, aby pole být seřazeny?

14
00:00:50,520 --> 00:00:53,360
Kdo chce odpovědět, že?

15
00:00:56,120 --> 00:01:00,070
[Student] Vzhledem k tomu, že nefunguje, pokud to není seřazena. Jo >>. [Smích]

16
00:01:00,070 --> 00:01:04,910
Pokud to není seřazena, pak je to možné rozdělit na dvě poloviny

17
00:01:04,910 --> 00:01:07,850
a vím, že všechno, co na levé straně je menší a všechno vpravo

18
00:01:07,850 --> 00:01:10,490
je větší, než je střední hodnota.

19
00:01:10,490 --> 00:01:12,790
Tak to musí být seřazeny.

20
00:01:12,790 --> 00:01:14,170
Dobře.

21
00:01:14,170 --> 00:01:17,570
Proč je bublina třídit O n na druhou?

22
00:01:17,570 --> 00:01:23,230
Má někdo nejprve chtít dát velmi rychle na vysoké úrovni přehled o tom, co bublina druh je?

23
00:01:25,950 --> 00:01:33,020
[Student] Ty v podstatě projít každý prvek a dáte zjistit několik prvních prvků.

24
00:01:33,020 --> 00:01:37,150
Pokud jsou z místa, kde jste je swap, pak zkontrolovat několik dalších prvků, a tak dále.

25
00:01:37,150 --> 00:01:40,770
Když se dostanete na konec, pak víte, že největší prvek je umístěn na konci,

26
00:01:40,770 --> 00:01:42,750
takže budete ignorovat, že jeden pak pokračovat dál přes,

27
00:01:42,750 --> 00:01:48,490
a pokaždé, když budete muset zkontrolovat jeden méně prvek, dokud neprovedete žádné změny. Jo >>.

28
00:01:48,490 --> 00:01:58,470
Je to tzv. bubble sort, protože pokud otočíte pole na jeho straně, takže je to nahoru a dolů, vertikální,

29
00:01:58,470 --> 00:02:03,100
pak velké hodnoty klesne na dno a nízké hodnoty vůle bublina až na vrchol.

30
00:02:03,100 --> 00:02:05,210
To je, jak to dostalo jeho jméno.

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

32
00:02:08,220 --> 00:02:11,190
Pořád jde přes pole, vyměňovat větší hodnotu

33
00:02:11,190 --> 00:02:14,040
aby se největší hodnoty na dno.

34
00:02:14,040 --> 00:02:17,500
>> Proč je to O n na druhou?

35
00:02:18,690 --> 00:02:24,620
Za prvé, někdo chce říct, proč je to O n na druhou?

36
00:02:24,620 --> 00:02:28,760
[Student] Protože pro každý běh jde n krát.

37
00:02:28,760 --> 00:02:32,100
Můžete být jisti, že jste si vzal Nejsilnějším prvkem celou cestu dolů,

38
00:02:32,100 --> 00:02:35,230
pak se budete muset zopakovat, že tak mnoho prvků. Jo >>.

39
00:02:35,230 --> 00:02:41,800
Takže mějte na paměti to, co velké O znamená a jaké velké Omega znamená.

40
00:02:41,800 --> 00:02:50,560
Velký O je jako horní mez na to, jak pomalu to může skutečně spustit.

41
00:02:50,560 --> 00:02:58,990
Takže tím, že říká, že je to O n. čtverečkovaný, to není O n jinak by být schopen spustit

42
00:02:58,990 --> 00:03:02,640
v lineárním čase, ale je to O z n kostičky

43
00:03:02,640 --> 00:03:06,390
protože to je ohraničeno O n kostičky.

44
00:03:06,390 --> 00:03:12,300
Pokud je to ohraničeno O n čtvercový, pak je to ohraničeno i n kostičky.

45
00:03:12,300 --> 00:03:20,280
Takže je n na druhou, a v absolutním nejhorším případě nelze lépe než n čtvercový,

46
00:03:20,280 --> 00:03:22,830
což je důvod, proč je O z n na druhou.

47
00:03:22,830 --> 00:03:31,200
Takže vidět mírný matematiku na to, jak vyjde ven, aby se n na druhou,

48
00:03:31,200 --> 00:03:40,530
pokud budeme mít pět věcí v našem seznamu, poprvé, kolik swapy bychom mohli potenciálně třeba, aby se

49
00:03:40,530 --> 00:03:47,170
aby se to? Pojďme vlastně jen -

50
00:03:47,170 --> 00:03:52,040
Kolik swapy budeme muset udělat v prvním běhu bublin řadit přes pole?

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

52
00:03:53,540 --> 00:03:58,340
>> Pokud jsou 5 prvků, budeme muset provést n - 1.

53
00:03:58,340 --> 00:04:01,100
Pak na druhém kolik swapy budeme muset udělat?

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

55
00:04:03,440 --> 00:04:11,640
A třetí bude n - 3, a pak pro pohodlí budu psát poslední dva

56
00:04:11,640 --> 00:04:15,270
jak pak budeme potřebovat, aby se 2 swapy a 1 swap.

57
00:04:15,270 --> 00:04:19,899
Myslím, že poslední člověk může nebo nemusí ve skutečnosti se muselo stát.

58
00:04:19,899 --> 00:04:22,820
Je to výměna? Nevím.

59
00:04:22,820 --> 00:04:26,490
Takže se jedná o celkové množství swapů nebo alespoň srovnání budete muset udělat.

60
00:04:26,490 --> 00:04:29,910
I když nechcete vyměnit, budete ještě potřebovat k porovnání hodnot.

61
00:04:29,910 --> 00:04:33,910
Tak jsou n - 1 srovnání v prvním projetí pole.

62
00:04:33,910 --> 00:04:42,050
Pokud uspořádání těchto věcí, pojďme vlastně dělat to šest věcí, takže to vyrovnat pěkně,

63
00:04:42,050 --> 00:04:44,790
a pak budu dělat 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Takže jen přeskupit tyto částky, chceme vidět, kolik srovnání děláme

65
00:04:49,910 --> 00:04:52,700
v celém algoritmu.

66
00:04:52,700 --> 00:04:56,550
Takže pokud vám přinášíme ty chlapy tady,

67
00:04:56,550 --> 00:05:07,470
pak jsme stále jen součet však mnoho srovnání existovaly.

68
00:05:07,470 --> 00:05:13,280
Ale pokud sečteme tyto a sečteme tyto a sečteme tyto,

69
00:05:13,280 --> 00:05:18,130
je to stále stejný problém. Právě jsme shrnout tyto konkrétní skupiny.

70
00:05:18,130 --> 00:05:22,400
>> Takže teď se budeme sčítat 3 n. Není to jen 3 n.

71
00:05:22,400 --> 00:05:27,650
Je to vždycky 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
Pokud jsme měli 10 věcí, pak bychom mohli udělat tuto sdružení pro 5 různých párů věcí

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

75
00:05:37,180 --> 00:05:45,840
Takže jste vždy dostane n / 2 n je, a tak to budeme zapisovat to k n na druhou / 2.

76
00:05:45,840 --> 00:05:48,890
A tak i když je to faktor poloviny, který se stane dál

77
00:05:48,890 --> 00:05:54,190
vzhledem k tomu, že po každé iteraci přes pole porovnáme 1 méně

78
00:05:54,190 --> 00:05:58,040
tak to je, jak se dostaneme přes 2, ale to je ještě n na druhou.

79
00:05:58,040 --> 00:06:01,650
My se nestaráme o konstantní faktor o polovinu.

80
00:06:01,650 --> 00:06:07,760
Takže hodně velké věci O takhle spoléhá jen na druhu dělat tento druh matematiky,

81
00:06:07,760 --> 00:06:12,260
dělat aritmetické součty a geometrické řady další věci,

82
00:06:12,260 --> 00:06:17,750
ale většina z nich v tomto kurzu jsou docela jasné.

83
00:06:17,750 --> 00:06:19,290
Dobře.

84
00:06:19,290 --> 00:06:24,430
Proč je vložení třídit Omega n? Co omega znamená?

85
00:06:24,430 --> 00:06:27,730
[Dva studenti mluví najednou - nesrozumitelné] >> Jo.

86
00:06:27,730 --> 00:06:30,630
Omega si můžete myslet, jak dolní mez.

87
00:06:30,630 --> 00:06:36,550
>> Takže bez ohledu na to, jak efektivní váš vložení sort je algoritmus,

88
00:06:36,550 --> 00:06:41,810
bez ohledu na seznamu, který je předán do, vždy musí porovnat alespoň n věci

89
00:06:41,810 --> 00:06:44,620
nebo to má pro iteraci n věcí.

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

91
00:06:47,280 --> 00:06:51,190
[Student] Protože pokud je seznam již řazeno, pak přes první iteraci

92
00:06:51,190 --> 00:06:54,080
můžete pouze zaručit, že úplně první element je nejméně,

93
00:06:54,080 --> 00:06:56,490
a druhá iterace lze pouze zaručit první dva jsou

94
00:06:56,490 --> 00:07:00,010
protože nevíte, že zbytek seznamu seřazeny. Jo >>.

95
00:07:00,010 --> 00:07:08,910
Pokud předáte ve zcela seřazený seznam, přinejmenším budete muset jít přes všechny prvky

96
00:07:08,910 --> 00:07:12,180
vidět, že nemusí nic být se pohyboval.

97
00:07:12,180 --> 00:07:14,720
Takže procházející přes seznam a řekl oh, je to už jsou seřazena,

98
00:07:14,720 --> 00:07:18,240
to je nemožné, abyste věděli, že to jsou seřazena dokud zjistit každý prvek

99
00:07:18,240 --> 00:07:20,660
aby se zjistilo, zda jsou v seřazeném pořadí.

100
00:07:20,660 --> 00:07:25,290
Tak dolní mez vložení řadit je Omega n.

101
00:07:25,290 --> 00:07:28,210
Co je nejhorší doba chodu druhu korespondence,

102
00:07:28,210 --> 00:07:31,390
Nejhorší případ je velké O znovu?

103
00:07:31,390 --> 00:07:37,660
Takže v nejhorším případě, jak se sloučení sort běží?

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

105
00:07:43,690 --> 00:07:49,990
Nejrychlejší obecné třídění algoritmy jsou n log n. Můžete to udělat lépe.

106
00:07:51,930 --> 00:07:55,130
>> Existují speciální případy, a pokud budeme mít čas dnes - ale asi won't -

107
00:07:55,130 --> 00:07:59,330
jsme mohli vidět ten, který dělá lépe než n log n.

108
00:07:59,330 --> 00:08:04,050
Ale v obecném případě, nemůžete udělat lépe, než n log n.

109
00:08:04,050 --> 00:08:09,680
A sloučit druh se stane, že ten, co byste měli vědět o tomto kurzu, který je n log n.

110
00:08:09,680 --> 00:08:13,260
A tak budeme skutečně provádí, že dnes.

111
00:08:13,260 --> 00:08:18,070
A konečně, v ne více než tři věty, jak se výběr řazení práci?

112
00:08:18,070 --> 00:08:20,370
Má někdo bude chtít odpovědět, a já počítat své věty

113
00:08:20,370 --> 00:08:22,390
protože pokud půjdete přes 3 -

114
00:08:25,530 --> 00:08:28,330
Pamatuje si někdo, výběr druhu?

115
00:08:31,280 --> 00:08:37,809
Výběr řazení je obvykle docela snadné si pamatovat jen z názvu.

116
00:08:37,809 --> 00:08:45,350
Stačí iterovat přes pole, najít, co největší hodnota nebo nejmenší -

117
00:08:45,350 --> 00:08:47,290
bez ohledu na pořadí, které jste třídění palců

118
00:08:47,290 --> 00:08:50,750
Takže řekněme, že jsme třídění od nejmenší k největší.

119
00:08:50,750 --> 00:08:55,250
Můžete iterovat přes pole, hledá bez ohledu na minimální prvek,

120
00:08:55,250 --> 00:08:59,750
vyberte ji, a pak už jen vyměnit to, co je na prvním místě.

121
00:08:59,750 --> 00:09:04,090
A pak na druhém průchodu přes pole, podívejte se na minimální prvek znovu,

122
00:09:04,090 --> 00:09:07,490
vyberte ji a poté si vyměňovat s tím, co je na druhé pozici.

123
00:09:07,490 --> 00:09:10,650
Takže jsme jen sběr a výběr minimální hodnoty

124
00:09:10,650 --> 00:09:16,050
a vložením do přední části pole, dokud se třídí.

125
00:09:19,210 --> 00:09:21,560
Otázky týkající se, že?

126
00:09:21,560 --> 00:09:25,710
>> Ty nevyhnutelně objevují ve formách, které musíte vyplnit, když jste podání PSet.

127
00:09:29,010 --> 00:09:32,360
Ti jsou v podstatě odpovědi na ty.

128
00:09:32,360 --> 00:09:34,230
Dobře, takže teď kódování problémy.

129
00:09:34,230 --> 00:09:40,140
Už jsem rozeslal přes e-mail - Bylo někdo nedostal tento e-mail? Dobře.

130
00:09:40,140 --> 00:09:46,630
Už jsem rozeslal přes e-mail na místo, které jsme bude používat,

131
00:09:46,630 --> 00:09:52,120
a pokud kliknete na mé jméno - takže myslím, že budu na dně

132
00:09:52,120 --> 00:09:57,170
z důvodu zpětné r - ale pokud kliknete na mé jméno uvidíte 2 revize.

133
00:09:57,170 --> 00:10:02,650
Revize 1 se bude už jsem zkopírovat a vložit kód do prostorů

134
00:10:02,650 --> 00:10:06,900
pro hledání věc, kterou budete muset provádět.

135
00:10:06,900 --> 00:10:10,540
A Revize 2 bude druh věcí, které provádíme po tom.

136
00:10:10,540 --> 00:10:15,770
Takže můžete kliknout na mé revize 1 a pracovat odtamtud.

137
00:10:17,350 --> 00:10:22,060
A nyní chceme zavést binární vyhledávání.

138
00:10:22,060 --> 00:10:26,470
>> Má někdo chtěl jen dát pseudokódu na vysoké úrovni vysvětlení

139
00:10:26,470 --> 00:10:31,440
z toho, co budeme muset udělat pro vyhledávání? Jo.

140
00:10:31,440 --> 00:10:36,170
[Student] Stačí vzít střed pole a uvidíme, jestli to, co jste hledali

141
00:10:36,170 --> 00:10:38,650
je menší než nebo více.

142
00:10:38,650 --> 00:10:41,080
A pokud je to méně, jdete do poloviny, která je méně,

143
00:10:41,080 --> 00:10:44,750
a pokud je to víc, můžete jít do poloviny, která je více a vy to zopakovat, dokud stačí si jednu věc.

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

145
00:10:46,570 --> 00:10:51,320
Všimněte si, že naše čísla pole je již řazeno,

146
00:10:51,320 --> 00:10:57,190
a tak to znamená, že můžeme využít, že jsme mohli nejprve zkontrolujte,

147
00:10:57,190 --> 00:11:00,390
jo, já jsem hledal číslo 50.

148
00:11:00,390 --> 00:11:03,720
Takže můžu jít do středu.

149
00:11:03,720 --> 00:11:07,380
Střední je těžké definovat, kdy je to ještě řada věcí,

150
00:11:07,380 --> 00:11:10,820
ale řekněme, že budeme vždy zkrátit na středu.

151
00:11:10,820 --> 00:11:14,420
Takže tu máme 8 věcí, takže prostřední bude 16.

152
00:11:14,420 --> 00:11:17,330
Hledám 50, takže 50 je větší než 16 let.

153
00:11:17,330 --> 00:11:21,310
Takže teď můžu v podstatě léčit své pole jako těchto prvků.

154
00:11:21,310 --> 00:11:23,450
Mohu vyhodit vše od 16 přes.

155
00:11:23,450 --> 00:11:27,440
Teď je moje pole je právě tato 4 prvky, a opakuji.

156
00:11:27,440 --> 00:11:31,910
Takže chci najít střed znovu, což bude 42.

157
00:11:31,910 --> 00:11:34,730
42 je menší než 50, takže můžu hodit daleko tyto dva prvky.

158
00:11:34,730 --> 00:11:36,890
To je můj zbývající pole.

159
00:11:36,890 --> 00:11:38,430
Jdu najít střed znovu.

160
00:11:38,430 --> 00:11:42,100
Myslím, že 50 byl špatný příklad, protože jsem byl vždycky zahodil věci na levé straně,

161
00:11:42,100 --> 00:11:48,280
ale ve stejné míře, když jsem hledal něco

162
00:11:48,280 --> 00:11:52,100
a je to méně, než prvek jsem v současné době při pohledu na,

163
00:11:52,100 --> 00:11:55,080
pak budu vyhazovat všechno vpravo.

164
00:11:55,080 --> 00:11:58,150
Takže teď musíme zavést, že.

165
00:11:58,150 --> 00:12:02,310
Všimněte si, že musíme projít ve velikosti.

166
00:12:02,310 --> 00:12:06,730
Můžeme také není nutné hard-kódu velikosti.

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

168
00:12:19,630 --> 00:12:21,430
Dobře.

169
00:12:21,430 --> 00:12:27,180
Jak mohu krásně zjistit, co velikost čísel pole je v současné době?

170
00:12:27,180 --> 00:12:30,950
>> Kolik prvků je v číslech poli?

171
00:12:30,950 --> 00:12:33,630
[Studentských] Čísla, držáky,. Délka?

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

173
00:12:36,600 --> 00:12:38,580
Potřebujete. Délka.

174
00:12:38,580 --> 00:12:42,010
Pole nemají vlastnosti, takže není délka vlastnost polí

175
00:12:42,010 --> 00:12:45,650
že bude jen aby vám jak dlouho to stane se.

176
00:12:48,180 --> 00:12:51,620
[Student] Viz kolik paměti má, a rozdělit podle toho, jak moc - >> Jo.

177
00:12:51,620 --> 00:12:55,810
Takže, jak můžeme vidět, kolik paměti má? >> [Student] sizeof. Jo >>, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof je operátor, který to bude vrátit velikost čísla pole.

179
00:13:01,680 --> 00:13:10,060
A to bude ale mnoho celá čísla tam jsou časy, velikost celé číslo

180
00:13:10,060 --> 00:13:14,050
protože to je to, kolik paměti je to vlastně nástupu do.

181
00:13:14,050 --> 00:13:17,630
Takže pokud chci, aby řadu věcí v poli,

182
00:13:17,630 --> 00:13:20,560
pak budu chtít rozdělit podle velikosti na celé číslo.

183
00:13:22,820 --> 00:13:26,010
Dobře. Takže mi umožňuje předat ve velikosti zde.

184
00:13:26,010 --> 00:13:29,430
Proč musím předat do velikosti vůbec?

185
00:13:29,430 --> 00:13:38,570
Proč nemůžu prostě dělat tady int size = sizeof (sena) / sizeof (int)?

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

187
00:13:41,490 --> 00:13:44,470
[Student] Není to globální proměnná.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack existuje a my jsme kolem v číslech jako kupce sena,

189
00:13:51,540 --> 00:13:54,700
a tohle je předzvěst toho, co přijde. Jo.

190
00:13:54,700 --> 00:14:00,170
[Student] Haystack je jen odkaz na to, tak to by se vrátit, jak velký tento odkaz je.

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

192
00:14:02,150 --> 00:14:09,000
Pochybuji, v přednášce, když jste viděli hromadu skutečnosti ještě, že jo?

193
00:14:09,000 --> 00:14:11,270
Právě jsme mluvili o tom.

194
00:14:11,270 --> 00:14:16,090
Takže stack je místo, kde všechny vaše proměnné se bude uložen.

195
00:14:16,090 --> 00:14:19,960
>> Každá paměť, která je přidělena pro lokální proměnné se děje v zásobníku,

196
00:14:19,960 --> 00:14:24,790
a každá funkce má svůj vlastní prostor na zásobníku, vlastní zásobník rám je to, co se jmenuje.

197
00:14:24,790 --> 00:14:31,590
Takže hlavní má svůj stack frame a uvnitř ní bude existovat tento čísla pole,

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

199
00:14:34,270 --> 00:14:38,180
Bude to mít velikost čísel rozdělených podle velikosti prvků,

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

201
00:14:42,010 --> 00:14:45,190
Když zavoláme hledání, hledání má svůj vlastní zásobník rám,

202
00:14:45,190 --> 00:14:48,840
vlastní prostor pro ukládání všech svých lokálních proměnných.

203
00:14:48,840 --> 00:14:56,420
Ale tyto argumenty - takže sena není kopie celého tohoto pole.

204
00:14:56,420 --> 00:15:00,990
Nechceme předat v celé pole jako kopie do vyhledávání.

205
00:15:00,990 --> 00:15:04,030
Je to jen předá odkaz na této matice.

206
00:15:04,030 --> 00:15:11,470
Takže hledání lze přístup k těmto číslům prostřednictvím tohoto odkazu.

207
00:15:11,470 --> 00:15:17,100
Je to stále přístup k věci, které žijí uvnitř zásobníku rámu hlavních je,

208
00:15:17,100 --> 00:15:22,990
ale v podstatě, když se dostaneme do ukazatelů, které by mělo být brzy,

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

210
00:15:24,980 --> 00:15:29,400
Ukazatele jsou jen odkazy na věci, a můžete použít odkazy na přístup k věci

211
00:15:29,400 --> 00:15:32,030
které jsou v zásobníku jiných věcí "rámů.

212
00:15:32,030 --> 00:15:37,660
Takže i když čísla je místní hlavní, stále ještě můžeme přistupovat prostřednictvím tohoto ukazatele.

213
00:15:37,660 --> 00:15:41,770
Ale protože je to jen ukazatel a je to jen odkaz,

214
00:15:41,770 --> 00:15:45,040
sizeof (haystack) vrátí pouze velikost odkazu samotného.

215
00:15:45,040 --> 00:15:47,950
To nevrátí velikost věc je to ukazuje.

216
00:15:47,950 --> 00:15:51,110
To nevrátí skutečnou velikost čísel.

217
00:15:51,110 --> 00:15:55,660
A tak to nebude fungovat, jak chceme, aby to.

218
00:15:55,660 --> 00:15:57,320
>> Otázky týkající se, že?

219
00:15:57,320 --> 00:16:03,250
Ukazatele budou pryč do významně více krvavý podrobněji v týdnech přijít.

220
00:16:06,750 --> 00:16:13,740
A to je důvod, proč mnoho věcí, které vidíte, většina vyhledávacích věcí nebo třídit věci,

221
00:16:13,740 --> 00:16:16,990
oni téměř všichni budeme muset vzít skutečné velikosti pole,

222
00:16:16,990 --> 00:16:20,440
protože v C, nemáme ponětí, co velikost pole je.

223
00:16:20,440 --> 00:16:22,720
Musíte ručně přenést dovnitř

224
00:16:22,720 --> 00:16:27,190
A nelze ručně předat v celém poli, protože jsi jen procházet v odkazu

225
00:16:27,190 --> 00:16:30,390
a to může dostat do velikosti v odkazu.

226
00:16:30,390 --> 00:16:32,300
Dobře.

227
00:16:32,300 --> 00:16:38,160
Takže teď chceme realizovat to, co bylo vysvětleno dříve.

228
00:16:38,160 --> 00:16:41,530
Můžete pracovat na něm za minutu,

229
00:16:41,530 --> 00:16:45,250
a nemusíte se bát všechno perfektně 100% funkční.

230
00:16:45,250 --> 00:16:51,410
Stačí napsat do poloviční pseudokódu pro to, jak si myslíte, že by to mělo fungovat.

231
00:16:52,000 --> 00:16:53,630
Dobře.

232
00:16:53,630 --> 00:16:56,350
Není třeba být zcela hotový s to ještě.

233
00:16:56,350 --> 00:17:02,380
Ale někdo cítí dobře s tím, co mají tak daleko,

234
00:17:02,380 --> 00:17:05,599
jako něco, co můžeme pracovat společně?

235
00:17:05,599 --> 00:17:09,690
Má někdo chtěl dobrovolně? Nebo jsem se náhodně vybírat.

236
00:17:12,680 --> 00:17:18,599
Nemusí to být přímo v každém ohledu, ale něco, co můžeme měnit do funkčního stavu.

237
00:17:18,599 --> 00:17:20,720
[Student] Jasně. Dobře >>.

238
00:17:20,720 --> 00:17:27,220
Takže můžete ušetřit na revizi kliknutím na malou ikonu Uložit.

239
00:17:27,220 --> 00:17:29,950
Jste Ramya, že jo? >> [Student] Jo. >> [Bowden] Dobře.

240
00:17:29,950 --> 00:17:35,140
Takže teď můžu zobrazit revizi a každý může vytáhnout revizi.

241
00:17:35,140 --> 00:17:38,600
A máme tady - Dobře.

242
00:17:38,600 --> 00:17:43,160
Tak Ramya šel s rekurzivní řešení, které je rozhodně platné řešení.

243
00:17:43,160 --> 00:17:44,970
Existují dva způsoby, jak můžete udělat tento problém.

244
00:17:44,970 --> 00:17:48,060
Můžete to udělat iteračně nebo rekurzivně.

245
00:17:48,060 --> 00:17:53,860
Většina problémy mi, že může být provedeno rekurzivně může být rovněž provedeno opakované.

246
00:17:53,860 --> 00:17:58,510
Tak tady jsme udělali to rekurzivně.

247
00:17:58,510 --> 00:18:03,730
>> Má někdo chcete definovat, co to znamená, aby se funkce rekurzivní?

248
00:18:07,210 --> 00:18:08,920
[Student] Pokud máte funkci volat sebe

249
00:18:08,920 --> 00:18:13,470
a pak volat sebe, dokud to vyjde s pravdou a pravda. Jo >>.

250
00:18:13,470 --> 00:18:17,680
Rekurzivní funkce je jen funkce, která volá sama sebe.

251
00:18:17,680 --> 00:18:24,140
K dispozici jsou tři velké věci, které rekurzivní funkce musí mít.

252
00:18:24,140 --> 00:18:27,310
První z nich je samozřejmě, že volá sama sebe.

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čitém okamžiku funkce musí přestat volat sám,

255
00:18:33,390 --> 00:18:35,610
a to je to, co referenční případ je pro.

256
00:18:35,610 --> 00:18:43,860
Tak tady víme, že bychom měli přestat, měli bychom se v našem hledání

257
00:18:43,860 --> 00:18:48,150
je-li start rovná konec - a půjdeme nad tím, co to znamená.

258
00:18:48,150 --> 00:18:52,130
Ale nakonec, poslední věc, která je důležitá pro rekurzivní funkce:

259
00:18:52,130 --> 00:18:59,250
funkce musí nějak přiblížit základní věc.

260
00:18:59,250 --> 00:19:04,140
Stejně jako když jste ve skutečnosti aktualizace nic, když uděláte druhý rekurzivní volání,

261
00:19:04,140 --> 00:19:07,880
pokud jste doslova volá funkci znovu se stejnými argumenty

262
00:19:07,880 --> 00:19:10,130
a žádné globální proměnné změnily nebo tak něco,

263
00:19:10,130 --> 00:19:14,430
budete nikdy nedosáhne základní věc, v tomto případě to je špatné.

264
00:19:14,430 --> 00:19:17,950
Bude to nekonečná rekurze a přetečení zásobníku.

265
00:19:17,950 --> 00:19:24,330
Ale tady vidíme, že aktualizace se děje, protože jsme aktualizaci kdo + konec / 2,

266
00:19:24,330 --> 00:19:28,180
jsme aktualizaci konec argumentu tady, jsme aktualizaci počáteční tvrzení zde.

267
00:19:28,180 --> 00:19:32,860
Takže ve všech rekurzivní volání jsme aktualizaci něco. Dobře.

268
00:19:32,860 --> 00:19:38,110
Chcete chodit nám prostřednictvím řešení? Jistě >>.

269
00:19:38,110 --> 00:19:44,270
Já používám SearchHelp tak, že pokaždé, když jsem tuto funkci volání

270
00:19:44,270 --> 00:19:47,910
Mám start, kde jsem hledal v poli a konec

271
00:19:47,910 --> 00:19:49,380
, kde jsem pohledu na pole.

272
00:19:49,380 --> 00:19:55,330
>> Na každém kroku, kde je to říká, že je to střední element, který je začátek + konec / 2,

273
00:19:55,330 --> 00:19:58,850
je, že rovná tomu, co jsme hledali?

274
00:19:58,850 --> 00:20:04,650
A pokud je, pak jsme ho našli, a já myslím, že je předán do úrovně rekurze.

275
00:20:04,650 --> 00:20:12,540
A pokud to není pravda, pak jsme zkontrolovat, zda střední hodnota pole je příliš velká,

276
00:20:12,540 --> 00:20:19,320
v takovém případě se díváme na levé polovině pole tím, že jde od začátku do střední indexu.

277
00:20:19,320 --> 00:20:22,710
A jinak děláme Konec poloviny.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Dobře.

279
00:20:24,740 --> 00:20:27,730
To zní dobře.

280
00:20:27,730 --> 00:20:36,640
Dobře, takže pár věcí, a skutečně, je to velmi vysoké úrovni, co

281
00:20:36,640 --> 00:20:41,270
že budete nikdy vědět tohoto kurzu, ale je to pravda.

282
00:20:41,270 --> 00:20:46,080
Rekurzivní funkce, vždy uslyšíte, že jsou špatné řešení

283
00:20:46,080 --> 00:20:51,160
protože když rekurzivně říkáš příliš mnohokrát, získáte přetečení zásobníku

284
00:20:51,160 --> 00:20:54,990
protože, jak jsem již řekl dříve, každá funkce má svůj vlastní zásobník rám.

285
00:20:54,990 --> 00:20:59,500
Takže každý hovor z rekurzivní funkce má svůj vlastní zásobník rám.

286
00:20:59,500 --> 00:21:04,140
Takže pokud uděláte 1.000 rekurzivní volání, získáte 1.000 zásobník snímků,

287
00:21:04,140 --> 00:21:08,390
a rychle se vést k nutnosti příliš mnoho stack rámy a věci se rozbijí.

288
00:21:08,390 --> 00:21:13,480
Takže to je důvod, proč rekurzivní funkce jsou obecně špatné.

289
00:21:13,480 --> 00:21:19,370
Ale tam je pěkný podmnožina rekurzivních funkcí tzv. tail-rekurzivní funkce,

290
00:21:19,370 --> 00:21:26,120
a to se stane, že je příkladem jedné, kde v případě, že kompilátor vnímá tento

291
00:21:26,120 --> 00:21:29,920
a to by mělo, myslím, že - v Clang předáte ho-O2 flag

292
00:21:29,920 --> 00:21:33,250
pak si všimnete je to ocas rekurzivní a dělat věci dobře.

293
00:21:33,250 --> 00:21:40,050
>> To bude používat stejné fronty rám znovu a znovu pro každou rekurzivní volání.

294
00:21:40,050 --> 00:21:47,010
A tak, protože jste pomocí stejného zásobníku rám, nemusíte se obávat

295
00:21:47,010 --> 00:21:51,690
kdy zásobník přetékání, a současně, jak si řekl,

296
00:21:51,690 --> 00:21:56,380
kde jakmile se vrátíte pravda, pak to musí vrátit do všech těchto zásobníku rámů

297
00:21:56,380 --> 00:22:01,740
a 10. výzva k SearchHelp musí vrátit do 9., se musí vrátit do 8..

298
00:22:01,740 --> 00:22:05,360
Takže není třeba se stane, když funkce ocas rekurzivní.

299
00:22:05,360 --> 00:22:13,740
A tak to, co dělá tato funkce ocas rekurzivní je upozornění, že pro dané výzvy k searchHelp

300
00:22:13,740 --> 00:22:18,470
rekurzivní volání, že to dělat, je to, co se vrací.

301
00:22:18,470 --> 00:22:25,290
Takže v první výzvě k SearchHelp, jsme buď okamžitě vrátí false,

302
00:22:25,290 --> 00:22:29,590
okamžitě vrátit true, nebo budeme dělat rekurzivní volání SearchHelp

303
00:22:29,590 --> 00:22:33,810
kde to, co se vracíme, je to, co, že hovor se vrací.

304
00:22:33,810 --> 00:22:51,560
A my jsme nemohli dělat to, pokud jsme udělali něco jako int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
jen nějaký náhodný změna.

306
00:22:55,440 --> 00:23:01,470
>> Takže teď to rekurzivní volání, toto int x = SearchHelp rekurzivní volání,

307
00:23:01,470 --> 00:23:05,740
je již ocas rekurzivní, protože to vlastně nemá muset vrátit

308
00:23:05,740 --> 00:23:10,400
zpět na předchozí zásobníku rámu tak, že předchozí volání funkce

309
00:23:10,400 --> 00:23:13,040
pak může něco udělat s návratovou hodnotou.

310
00:23:13,040 --> 00:23:22,190
Takže to není ocas rekurzivní, ale to, co jsme měli předtím, je pěkně ocas rekurzivní. Jo.

311
00:23:22,190 --> 00:23:27,000
[Student] Pokud není druhá základna případ zkontrolovat první

312
00:23:27,000 --> 00:23:30,640
protože by mohlo nastat situace, kdy při předat argument

313
00:23:30,640 --> 00:23:35,770
jste start = konec, ale oni jsou jehly hodnotu.

314
00:23:35,770 --> 00:23:47,310
Otázka nemůže narazíme na případ, kdy je konec jehly hodnota

315
00:23:47,310 --> 00:23:52,000
nebo start = konec, přiměřeně, start = konec

316
00:23:52,000 --> 00:23:59,480
a vy jste ve skutečnosti kontrolovat, že konkrétní hodnoty ještě,

317
00:23:59,480 --> 00:24:03,910
pak začít + konec / 2 je jen tak mít stejnou hodnotu.

318
00:24:03,910 --> 00:24:07,890
Ale my už se vrátil false, a nikdy jsme vlastně četl hodnotu.

319
00:24:07,890 --> 00:24:14,240
Takže přinejmenším v prvním hovoru, pokud je velikost 0, pak chceme vrátit false.

320
00:24:14,240 --> 00:24:17,710
Ale pokud velikost je 1, pak začátek nebude stejné konce,

321
00:24:17,710 --> 00:24:19,820
a budeme alespoň zkontrolovat jeden prvek.

322
00:24:19,820 --> 00:24:26,750
Ale myslím, že máte pravdu v tom, že můžeme skončit v případě, kdy začít + konec / 2,

323
00:24:26,750 --> 00:24:31,190
Začátek nakonec je stejný jako začátek + konec / 2,

324
00:24:31,190 --> 00:24:35,350
ale nikdy jsme vlastně četl tento prvek.

325
00:24:35,350 --> 00:24:44,740
>> Takže když jsme nejprve zkontrolovat, je střední prvek hodnotu, kterou hledáte,

326
00:24:44,740 --> 00:24:47,110
pak můžeme okamžitě vrátit true.

327
00:24:47,110 --> 00:24:50,740
Else, pokud jsou stejné, pak je tu nemá smysl pokračovat

328
00:24:50,740 --> 00:24:58,440
protože jsme jen tak aktualizaci na případ, kdy jsme na jedné prvku pole.

329
00:24:58,440 --> 00:25:01,110
Pokud tento jediný prvek není ten, kterého hledáme,

330
00:25:01,110 --> 00:25:03,530
pak je vše v pořádku. Jo.

331
00:25:03,530 --> 00:25:08,900
[Student] věc je, že od té doby velikost je ve skutečnosti větší než počet prvků v poli,

332
00:25:08,900 --> 00:25:13,070
tam je už offset - >> Tak bude velikost -

333
00:25:13,070 --> 00:25:19,380
[Student] říci, zda pole je velikost 0, pak SearchHelp skutečně kontrolovat Haystack 0.

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

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

336
00:25:25,300 --> 00:25:30,750
Je tu další věc, která - to by mohlo být dobré. Pojďme přemýšlet.

337
00:25:30,750 --> 00:25:40,120
Takže pokud pole měl 10 článků a prostřední budeme kontrolovat, je index 5,

338
00:25:40,120 --> 00:25:45,700
takže jsme kontrolu 5, a řekněme, že hodnota je menší.

339
00:25:45,700 --> 00:25:50,720
Takže jsme házet všechno pryč od 5 kupředu.

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

341
00:25:54,030 --> 00:25:57,450
tak jo, to vždycky zůstat i po skončení tohoto pole.

342
00:25:57,450 --> 00:26:03,570
Pokud je to případ, kdy to bylo sudé nebo liché, pak bychom zjistili, zda, řekněme, 4,

343
00:26:03,570 --> 00:26:05,770
ale my jsme pořád vyhazujete -

344
00:26:05,770 --> 00:26:13,500
Tak jo, konec je vždy bude za skutečného konce pole.

345
00:26:13,500 --> 00:26:18,350
Takže prvků jsme se zaměřením na, konec je vždy bude jeden po tom.

346
00:26:18,350 --> 00:26:24,270
A pokud se někdy začátek stejný konec, my jsme v poli velikosti 0.

347
00:26:24,270 --> 00:26:35,600
>> Druhá věc, kterou jsem myslel je, že jsme aktualizaci start se začít + konec / 2,

348
00:26:35,600 --> 00:26:44,020
tak to je pravda, že mám potíže s, kde začít + konec / 2

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

350
00:26:46,820 --> 00:26:58,150
Řekněme, že jsme měli 10-prvek pole. Cokoliv.

351
00:26:58,150 --> 00:27:03,250
Takže začít + end / 2 bude něco jako je tento,

352
00:27:03,250 --> 00:27:07,060
a pokud to není hodnota, že chceme aktualizovat.

353
00:27:07,060 --> 00:27:10,060
Hodnota je větší, takže chceme se podívat na této poloviny pole.

354
00:27:10,060 --> 00:27:15,910
Tak jak jsme aktualizaci začátek, jsme aktualizaci start nyní tento prvek.

355
00:27:15,910 --> 00:27:23,790
Ale to se může stále fungovat, nebo přinejmenším, můžete tak učinit začátek + konec / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Student] Nemusíte být začít + konec [neslyšitelné] >> Jo.

357
00:27:27,850 --> 00:27:33,240
Jsme již zkoumali tento prvek a vím, že to není ten, kterého hledáme.

358
00:27:33,240 --> 00:27:36,800
Takže nepotřebujeme aktualizovat start je tento prvek.

359
00:27:36,800 --> 00:27:39,560
Můžeme jen přeskočit a aktualizovat začít být tento prvek.

360
00:27:39,560 --> 00:27:46,060
A je tam někdy případ, řekněme, že to bylo konec,

361
00:27:46,060 --> 00:27:53,140
takže pak kdo by to, kdo + konec / 2 by to,

362
00:27:53,140 --> 00:28:00,580
kdo + konec - Jo, myslím, že to může skončit v nekonečné rekurze.

363
00:28:00,580 --> 00:28:12,690
Řekněme, že je to jen pole o velikosti 2 nebo pole o velikosti 1. Myslím, že to bude fungovat.

364
00:28:12,690 --> 00:28:19,490
Takže v současné době, start je tento prvek a konec je 1 mimo něj.

365
00:28:19,490 --> 00:28:24,110
Takže prvek, který budeme kontrolovat, je to jedno,

366
00:28:24,110 --> 00:28:29,400
a pak, když jsme aktualizaci začátek, jsme aktualizaci start být 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
který se bude do konce nás zpět s počáteční že tento prvek.

368
00:28:33,160 --> 00:28:36,210
>> Takže jsme kontrolu stejný prvek znovu a znovu.

369
00:28:36,210 --> 00:28:43,310
Tak tohle je případ, kdy každá rekurzivní volání, musí být skutečně aktualizovat něco.

370
00:28:43,310 --> 00:28:48,370
Takže musíme udělat začátek + konec / 2 + 1, jinak je tu případ

371
00:28:48,370 --> 00:28:50,710
kde jsme ve skutečnosti aktualizace začátek.

372
00:28:50,710 --> 00:28:53,820
Všichni vidí, že?

373
00:28:53,820 --> 00:28:56,310
Dobře.

374
00:28:56,310 --> 00:29:03,860
Má někdo nějaké dotazy týkající se tohoto roztoku nebo jakékoli další komentáře?

375
00:29:05,220 --> 00:29:10,280
Dobře. Má někdo iterativní řešení, které můžeme všichni podívat na?

376
00:29:17,400 --> 00:29:20,940
Jsme to všichni rekurzivně?

377
00:29:20,940 --> 00:29:25,950
Nebo také myslím, že pokud jste si otevřeli její, pak byste měli mít přepsat svůj předchozí.

378
00:29:25,950 --> 00:29:28,810
Má to automaticky ukládat? Nejsem pozitivní.

379
00:29:35,090 --> 00:29:39,130
Má někdo se opakující?

380
00:29:39,130 --> 00:29:42,430
Můžeme projít ní společně, ne-li.

381
00:29:46,080 --> 00:29:48,100
Tato myšlenka je bude stejné.

382
00:30:00,260 --> 00:30:02,830
Iterační řešení.

383
00:30:02,830 --> 00:30:07,140
Budeme chtít, aby v podstatě dělat stejnou myšlenku

384
00:30:07,140 --> 00:30:16,530
tam, kde chceme sledovat nového konce pole a nový začátek pole

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

386
00:30:18,510 --> 00:30:22,430
A jestli to, co jsme sledování jako na začátku a na konci vždy protínají,

387
00:30:22,430 --> 00:30:29,020
pak jsme nenašli, a můžeme se vrátit false.

388
00:30:29,020 --> 00:30:37,540
Tak jak to mám udělat, že? Každý, kdo má návrhy nebo kód pro mě vytáhnout?

389
00:30:42,190 --> 00:30:47,450
[Student] Do smyčky while. Jo >>.

390
00:30:47,450 --> 00:30:49,450
Budeš chtít udělat smyčku.

391
00:30:49,450 --> 00:30:51,830
>> Měli jste kód, který jsem mohl vytáhnout, nebo co jsi chtěl navrhnout?

392
00:30:51,830 --> 00:30:56,340
[Student] Myslím, že ano. >> Dobře. To dělá věci jednodušší. Jaké bylo vaše jméno?

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

394
00:31:00,140 --> 00:31:04,190
Revize 1. Dobře.

395
00:31:04,190 --> 00:31:13,200
Nejnižší je to, co jsme nazvali začít dříve.

396
00:31:13,200 --> 00:31:17,080
Up není to, co jsme nazvali konec před.

397
00:31:17,080 --> 00:31:22,750
Ve skutečnosti, konec je nyní v matici. Je to prvek, bychom měli zvážit.

398
00:31:22,750 --> 00:31:26,890
Takže nízká je 0 až je velikost pole - 1,

399
00:31:26,890 --> 00:31:34,780
a teď jsme smyčky, a my se kontrola -

400
00:31:34,780 --> 00:31:37,340
Myslím, že můžete chodit přes něj.

401
00:31:37,340 --> 00:31:41,420
Jaký byl váš myšlení přes to? Procházka nás prostřednictvím kódu.

402
00:31:41,420 --> 00:31:49,940
[Student] Jasně. Podívejte se na haystack hodnotu ve středu a porovnat jej s jehlou.

403
00:31:49,940 --> 00:31:58,520
Takže pokud je to větší než vaše jehly, pak budete chtít - oh, vlastně, že by měla být zpětně.

404
00:31:58,520 --> 00:32:05,180
Budeš chtít vyhodit pravou polovinu, a tak jo, to by mělo být tak.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Tak by to mělo být méně? Je to to, co jsi řekl? >> [Student] Jo.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Dobře. Méně.

407
00:32:10,390 --> 00:32:15,700
Takže pokud to, co se díváme na menší, než to, co chceme,

408
00:32:15,700 --> 00:32:19,410
tak jo, chceme vyhodit levou polovinu,

409
00:32:19,410 --> 00:32:22,210
což znamená, že se aktualizace vše Uvažujeme

410
00:32:22,210 --> 00:32:26,610
Pohybem nízko na pravé straně pole.

411
00:32:26,610 --> 00:32:30,130
To vypadá dobře.

412
00:32:30,130 --> 00:32:34,550
Myslím, že to má stejný problém, který jsme si řekli na předchozí,

413
00:32:34,550 --> 00:32:49,760
, kde v případě nízké je 0, a až je 1, potom nízký + až / 2 bude nastaven tak, aby se totéž znovu.

414
00:32:49,760 --> 00:32:53,860
>> A i když to není tento případ, je ještě účinnější, přinejmenším

415
00:32:53,860 --> 00:32:57,630
jen vyhodit prvek jsme právě podíval na kterém víme, že je v pořádku.

416
00:32:57,630 --> 00:33:03,240
Tak nízká + nahoru / 2 + 1 - >> [Student] To by mělo být naopak.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Nebo by to mělo být - 1 a druhý by měl být + 1.

418
00:33:05,900 --> 00:33:09,580
[Student] A by měl být dvojí rovnítko. >> [Bowden] Jo.

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

420
00:33:14,540 --> 00:33:15,910
Dobře.

421
00:33:15,910 --> 00:33:21,280
A konečně, nyní, když máme tuto + 1-1 věc,

422
00:33:21,280 --> 00:33:31,520
je to - to nemusí být - je to vůbec možné, nízká skončit s hodnotou vyšší než nahoru?

423
00:33:35,710 --> 00:33:40,320
Myslím, že jediný způsob, jak se může stát - je to možné? >> [Student] Nevím.

424
00:33:40,320 --> 00:33:45,220
Ale pokud to bude zkrácen a pak dostane minus 1 a potom - >> Jo.

425
00:33:45,220 --> 00:33:47,480
[Student] To by možná si zpackal.

426
00:33:49,700 --> 00:33:53,940
Myslím, že by to mělo být dobré jen proto, že

427
00:33:53,940 --> 00:33:58,800
pro to, aby skončil nižší, budou muset být se rovnat, myslím.

428
00:33:58,800 --> 00:34:03,070
Ale pokud jsou stejné, pak bychom udělali while začít s

429
00:34:03,070 --> 00:34:06,670
a my jsme se vrátili hodnotu. Takže myslím, že jsme v pohodě teď.

430
00:34:06,670 --> 00:34:11,530
Povšimněte si, že i když je tento problém již rekurzivní,

431
00:34:11,530 --> 00:34:17,400
stejný druh myšlenek platí, kde můžeme vidět, jak to tak snadno propůjčuje

432
00:34:17,400 --> 00:34:23,659
k rekurzivní řešení tím, že jsme jen aktualizuje indexy znovu a znovu,

433
00:34:23,659 --> 00:34:29,960
děláme problém menší a menší, my se soustředíme na podmnožinu pole.

434
00:34:29,960 --> 00:34:40,860
[Student] Při nízké je 0, a až je 1, by se oba 0 + 1/2, což by na 0,

435
00:34:40,860 --> 00:34:44,429
a pak jeden by + 1, jeden by být - 1.

436
00:34:47,000 --> 00:34:50,870
[Student] Kde jsme kontrolu rovnosti?

437
00:34:50,870 --> 00:34:55,100
Jako v případě, že prostřední je vlastně jehla?

438
00:34:55,100 --> 00:34:58,590
Nejsme v současné době dělá, že? Oh!

439
00:35:00,610 --> 00:35:02,460
Pokud to -

440
00:35:05,340 --> 00:35:13,740
Ano. Nemůžeme jen tak udělat test sem, protože řekněme, že první středu -

441
00:35:13,740 --> 00:35:16,430
[Student] Je to vlastně jako nevyhazujte vázané.

442
00:35:16,430 --> 00:35:20,220
Takže pokud máte vyhodit vázaná, budete muset zkontrolovat první nebo cokoliv.

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

444
00:35:23,350 --> 00:35:29,650
Takže teď jsme zahodil ten jsme v současné době se podíval na,

445
00:35:29,650 --> 00:35:33,260
což znamená, že nyní musíme také mít

446
00:35:33,260 --> 00:35:44,810
if (haystack [(low + up) / 2] == jehly), pak můžeme vrátit true.

447
00:35:44,810 --> 00:35:52,070
A jestli jsem dal jinam, nebo jen v případě, to znamená doslova totéž

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

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

450
00:36:01,450 --> 00:36:10,440
>> Takže ještě pokud to, jinak to, a to je běžná věc dělám

451
00:36:10,440 --> 00:36:14,340
, kde i když je to v případě, kdy je vše dobré zde,

452
00:36:14,340 --> 00:36:22,780
jako nízká, může být nikdy vyšší než nahoru, to nestojí za úvaha o tom, zda je to pravda.

453
00:36:22,780 --> 00:36:28,010
Takže se může také říkat při nízké je menší než nebo roven

454
00:36:28,010 --> 00:36:30,720
nebo při nízké je menší než

455
00:36:30,720 --> 00:36:35,300
takže v případě, že jsou stále stejné, nebo nízká stane ujít,

456
00:36:35,300 --> 00:36:40,130
pak můžeme vymanit z této smyčky.

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

458
00:36:47,080 --> 00:36:49,270
Dobře. To vypadá dobře.

459
00:36:49,270 --> 00:36:52,230
Teď chceme udělat jakousi.

460
00:36:52,230 --> 00:37:04,030
Pokud půjdeme do mé druhé revizi, vidíme tytéž čísla,

461
00:37:04,030 --> 00:37:07,550
ale nyní jsou již v seřazeném pořadí.

462
00:37:07,550 --> 00:37:12,840
A my chceme zavést jakousi pomocí jakýkoli algoritmus v O n log n.

463
00:37:12,840 --> 00:37:17,240
Takže, které algoritmus si myslíte, že bychom měli zavést tady? >> [Student] Merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Jo. Sloučit sort je O (n log n), takže to je to, co budeme dělat.

465
00:37:23,810 --> 00:37:26,680
A problém bude dost podobně,

466
00:37:26,680 --> 00:37:31,920
kde se snadno půjčuje sebe k rekurzivní řešení.

467
00:37:31,920 --> 00:37:35,580
Můžeme také přijít s iterativní řešení, pokud chceme,

468
00:37:35,580 --> 00:37:42,540
ale rekurze bude jednodušší tady a měli bychom dělat rekurzi.

469
00:37:45,120 --> 00:37:49,530
Myslím, že budeme procházet řadit sloučení první,

470
00:37:49,530 --> 00:37:54,280
ačkoli tam je krásné video o řadit sloučení již. [Smích]

471
00:37:54,280 --> 00:37:59,780
Takže sloučit druh existuje - Jsem plýtvání tolik této práce.

472
00:37:59,780 --> 00:38:02,080
Oh, je tu jen jeden vlevo.

473
00:38:02,080 --> 00:38:03,630
Tak sloučení.

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

475
00:38:26,090 --> 00:38:27,440
Dobře.

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

477
00:38:33,460 --> 00:38:36,780
Individuálně tyto dvě pole jsou oba seřazeny.

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

479
00:38:40,970 --> 00:38:46,710
Co teď sloučení měli udělat, je spojit je do jediného pole, která je sama seřazeny.

480
00:38:46,710 --> 00:38:57,130
Takže chceme pole o velikosti 6, která se bude mít tyto prvky uvnitř něj

481
00:38:57,130 --> 00:38:59,390
v seřazeném pořadí.

482
00:38:59,390 --> 00:39:03,390
>> A tak můžeme využít k tomu, že tyto dva pole jsou seřazeny

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

484
00:39:06,800 --> 00:39:13,510
lineární čas význam v případě, že je velikost pole x, a to je velikost y,

485
00:39:13,510 --> 00:39:20,970
pak celkový algoritmus by měl být O (x + y). Dobře.

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

487
00:39:23,150 --> 00:39:26,030
[Student] Mohli bychom začít zleva?

488
00:39:26,030 --> 00:39:30,150
Takže budete dal 0 dolů a pak 1 a pak zde jste na 2.

489
00:39:30,150 --> 00:39:33,320
Takže je to něco jako, že máte kartu, která se pohybuje doprava. >> [Bowden] Jo.

490
00:39:33,320 --> 00:39:41,070
Pro oba z těchto polí, pokud se soustředit jen na krajním prvku.

491
00:39:41,070 --> 00:39:43,530
Vzhledem k tomu, jak pole jsou seřazeny, víme, že tyto 2 prvky

492
00:39:43,530 --> 00:39:46,920
jsou nejmenší prvky obou poli.

493
00:39:46,920 --> 00:39:53,500
To znamená, že 1 z těchto 2 prvků musí být nejmenší prvek v naší sloučené pole.

494
00:39:53,500 --> 00:39:58,190
To jen tak se stane, že nejmenší je jedno na pravé této doby.

495
00:39:58,190 --> 00:40:02,580
Tak jsme se 0, vložte jej na levé straně, protože 0 je menší než 1,

496
00:40:02,580 --> 00:40:08,210
takže si 0, vložte ji do naší první pozice, a pak jsme je aktualizuje

497
00:40:08,210 --> 00:40:12,070
aby nyní soustředit na první prvek.

498
00:40:12,070 --> 00:40:14,570
A teď jsme se opakovat.

499
00:40:14,570 --> 00:40:20,670
Takže teď jsme tyto 2 a 1. 1 je menší, takže vložíme 1.

500
00:40:20,670 --> 00:40:25,300
My aktualizovat tento ukazatel aby ukazoval na toho chlapa.

501
00:40:25,300 --> 00:40:33,160
Nyní jsme to znovu, tak 2. To bude aktualizovat, porovnání těchto 2, 3.

502
00:40:33,160 --> 00:40:37,770
Tato aktualizace, pak 4 a 5.

503
00:40:37,770 --> 00:40:42,110
Tak to je sloučení.

504
00:40:42,110 --> 00:40:49,010
>> Mělo by být naprosto jasné, že je lineární čas, protože jsme prostě jít přes každý prvek jednou.

505
00:40:49,010 --> 00:40:55,980
A to je největší krok k realizaci sloučení řazení to dělá.

506
00:40:55,980 --> 00:40:59,330
A to není tak těžké.

507
00:40:59,330 --> 00:41:15,020
A pár věcí dělat starosti, je řekněme jsme sloučení 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
V tomto případě jsme skončili ve scénáři, kde tento člověk bude menší,

509
00:41:30,930 --> 00:41:36,160
pak aktualizovat tento ukazatel, tohle bude menší, je aktualizuje,

510
00:41:36,160 --> 00:41:41,280
tohle je menší, a teď budete muset uznat

511
00:41:41,280 --> 00:41:44,220
když jste skutečně spustit z prvků, které mají v porovnání s.

512
00:41:44,220 --> 00:41:49,400
Protože jsme již používali tento celého pole,

513
00:41:49,400 --> 00:41:55,190
vše v tomto poli je nyní právě vložené do zde.

514
00:41:55,190 --> 00:42:02,040
Takže pokud se někdy dostanete do bodu, kdy je jeden z našich polí zcela sloučeny již,

515
00:42:02,040 --> 00:42:06,510
pak jen vzít všechny prvky druhé pole a vložit do konce pole.

516
00:42:06,510 --> 00:42:13,630
Takže můžeme jen vložit 4, 5, 6. Dobře.

517
00:42:13,630 --> 00:42:18,070
To je jedna věc, dávat si pozor na.

518
00:42:22,080 --> 00:42:26,120
Prováděcí který by měl být krok 1.

519
00:42:26,120 --> 00:42:32,600
Sloučit řadit pak na základě toho, že je to 2 kroky, 2 hloupé kroky.

520
00:42:38,800 --> 00:42:42,090
Pojďme dát toto pole.

521
00:42:57,920 --> 00:43:05,680
Takže sloučit druh, krok 1 je rekurzivně rozdělit pole na poloviny.

522
00:43:05,680 --> 00:43:09,350
Takže rozdělit toto pole na poloviny.

523
00:43:09,350 --> 00:43:22,920
V současné době máme 4, 15, 16, 50 a 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
A teď jsme to znovu a rozdělili jsme je do poloviny.

525
00:43:25,800 --> 00:43:27,530
Já si jen to na této straně.

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
Rádi bychom dělat stejnou věc znovu tady.

528
00:43:37,440 --> 00:43:40,340
A teď jsme se rozdělili do poloviny 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í scénář.

531
00:43:53,170 --> 00:44:00,540
Jakmile pole jsou velikosti 1, pak přestat s rozdělením do poloviny.

532
00:44:00,540 --> 00:44:03,190
>> Co teď budeme dělat s tím?

533
00:44:03,190 --> 00:44:15,730
Jsme skončit to bude také rozdělit do 8, 23, 42, a 108.

534
00:44:15,730 --> 00:44:24,000
Takže teď, že jsme v tomto bodě, nyní kroku dvě řadit sloučení je jen sloučení dvojice seznamů.

535
00:44:24,000 --> 00:44:27,610
Takže chceme sloučit tyto. Právě jsme zavolat sloučení.

536
00:44:27,610 --> 00:44:31,410
Víme, že sloučení se vrátit tyto v seřazeném pořadí.

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

538
00:44:33,920 --> 00:44:41,440
Nyní chceme sloučit tyto, a že vrátí seznam s těmi v seřazeném pořadí,

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

540
00:44:44,160 --> 00:44:57,380
Spojíme ty - Nemůžu psát - 8, 23 a 42, 108.

541
00:44:57,380 --> 00:45:02,890
Takže máme sloučené dvojice jednou.

542
00:45:02,890 --> 00:45:05,140
Teď už jen sloučit znovu.

543
00:45:05,140 --> 00:45:10,130
Všimněte si, že každý z těchto seznamů je seřazena v sobě,

544
00:45:10,130 --> 00:45:15,220
a pak můžeme jen sloučit tyto seznamy získat seznam velikosti 4, který je seřazena

545
00:45:15,220 --> 00:45:19,990
a spojit tyto dva seznamy získat seznam velikosti 4, která je seřazena.

546
00:45:19,990 --> 00:45:25,710
A konečně, můžeme sloučit tyto dva seznamy velikosti 4, aby si jeden seznam velikosti 8, která je seřazena.

547
00:45:25,710 --> 00:45:34,030
Takže vidět, že je to celkově n log n, už jsme viděli, že sloučení je lineární,

548
00:45:34,030 --> 00:45:40,390
takže když máme co do činění s sloučením tato, takže stejně jako celkové náklady na sloučení

549
00:45:40,390 --> 00:45:43,410
těchto dvou seznamů je jen 2, protože -

550
00:45:43,410 --> 00:45:49,610
Nebo dobře, je to O n, ale n je zde jen tyto 2 prvky, takže je to 2.

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

552
00:45:52,850 --> 00:45:58,820
takže přes všechny splývá, které musíme udělat, jsme se nakonec dělat n.

553
00:45:58,820 --> 00:46:03,210
Jako 2 + 2 + 2 + 2 je 8, což je n,

554
00:46:03,210 --> 00:46:08,060
takže náklady na sloučení v této sadě je n.

555
00:46:08,060 --> 00:46:10,810
A pak to samé tady.

556
00:46:10,810 --> 00:46:16,980
Budeme sloučení těchto 2, pak tyto 2, a osobně to sloučení bude trvat čtyři operace,

557
00:46:16,980 --> 00:46:23,610
to sloučení bude trvat čtyři operace, ale opět, mezi všemi z nich,

558
00:46:23,610 --> 00:46:29,030
jsme se nakonec slučování n celkem věci, a tak tento krok trvá n.

559
00:46:29,030 --> 00:46:33,670
A tak každá úroveň má n prvků je sloučeny.

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

561
00:46:36,110 --> 00:46:40,160
Na každé úrovni, naše pole roste podle velikosti 2.

562
00:46:40,160 --> 00:46:44,590
Zde naše pole jsou velikosti 1, zde jsou velikosti 2, zde jsou velikosti 4,

563
00:46:44,590 --> 00:46:46,470
a konečně, jsou velikosti 8.

564
00:46:46,470 --> 00:46:56,450
Takže, protože to je zdvojení, tam se bude celkem 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ň přičemž n celkem operace,

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
Lidé již dosáhla pokroku v tom, jak to provést co?

569
00:47:13,320 --> 00:47:18,260
Je někdo již ve stavu, kdy jsem si jen vytáhnout svůj kód?

570
00:47:20,320 --> 00:47:22,260
Můžu dát chvilku.

571
00:47:24,770 --> 00:47:27,470
Tenhle bude delší.

572
00:47:27,470 --> 00:47:28,730
Vřele doporučuji opakovat -

573
00:47:28,730 --> 00:47:30,510
Nemusíte dělat rekurzi pro sloučení

574
00:47:30,510 --> 00:47:33,750
protože dělat rekurzi pro sloučení, budete muset projít spoustu různých velikostí.

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 rekurze pro řadit sám o sobě je docela snadné.

577
00:47:43,720 --> 00:47:49,190
Stačí zavolat doslova jakousi na levé polovině, sort na pravé polovině. Dobře.

578
00:47:51,770 --> 00:47:54,860
Každý, kdo má něco, co jsem si vytáhnout vzhůru?

579
00:47:54,860 --> 00:47:57,540
Jinak já dám minutku.

580
00:47:58,210 --> 00:47:59,900
Dobře.

581
00:47:59,900 --> 00:48:02,970
Každý, kdo má něco, co můžeme pracovat s?

582
00:48:05,450 --> 00:48:09,680
Jinak budeme jen s tímto pracujete a potom rozbalte odtamtud.

583
00:48:09,680 --> 00:48:14,050
>> Každý, kdo má víc než to, že jsem si vytáhnout?

584
00:48:14,050 --> 00:48:17,770
[Student] Jo. Můžete vytáhnout moje. >> Dobře.

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

586
00:48:22,170 --> 00:48:25,280
[Student] Byla tam spousta podmínek. >> Oh, střílet. Můžeš -

587
00:48:25,280 --> 00:48:28,110
[Student] Musím zachránit ji. Jo >>.

588
00:48:32,420 --> 00:48:35,730
Tak jsme udělali to sloučení odděleně.

589
00:48:35,730 --> 00:48:38,570
Oh, ale to není tak špatné.

590
00:48:39,790 --> 00:48:41,650
Dobře.

591
00:48:41,650 --> 00:48:47,080
Takže druh je sám o sobě jen volání mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Vysvětlete nám, co mergeSortHelp dělá.

593
00:48:49,530 --> 00:48:55,700
[Student] MergeSortHelp docela hodně dělá dva hlavní kroky,

594
00:48:55,700 --> 00:49:01,270
který je vyřešit každou polovinu pole a pak sloučit oba.

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

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

597
00:49:17,100 --> 00:49:19,400
Jo. Jsem něco chybí.

598
00:49:19,400 --> 00:49:23,100
V sloučení, jsem si uvědomil, že musím vytvořit nové pole

599
00:49:23,100 --> 00:49:26,530
protože jsem nemohl udělat to na místě. Ano >>. Nemůžete. Opravit.

600
00:49:26,530 --> 00:49:28,170
[Student] Tak jsem vytvořit nové pole.

601
00:49:28,170 --> 00:49:31,510
Zapomněl na konci se ponoří znovu změnit.

602
00:49:31,510 --> 00:49:34,490
Dobře. Potřebujeme nové pole.

603
00:49:34,490 --> 00:49:41,000
V řadit slučovací, je to téměř vždy pravda.

604
00:49:41,000 --> 00:49:44,340
Část nákladů na lepší algoritmu časově

605
00:49:44,340 --> 00:49:47,310
je téměř vždy museli použít trochu více paměti.

606
00:49:47,310 --> 00:49:51,570
Tak tady, bez ohledu na to, jak to děláš sloučit druh,

607
00:49:51,570 --> 00:49:54,780
budete nevyhnutelně potřebovat nějaké extra paměť.

608
00:49:54,780 --> 00:49:58,240
On nebo ona vytvořila nové pole.

609
00:49:58,240 --> 00:50:03,400
A pak řekneš na konci jsme stačí zkopírovat nové pole do původního pole.

610
00:50:03,400 --> 00:50:04,830
[Student] Myslím, že ano, jo.

611
00:50:04,830 --> 00:50:08,210
Nevím, jestli to funguje, pokud jde o počítání odkazu nebo cokoliv jiného -

612
00:50:08,210 --> 00:50:11,650
Jo, bude to fungovat. >> [Student] Dobře.

613
00:50:20,620 --> 00:50:24,480
Bylo pro vás zkuste to? >> [Student] Ne, ještě ne. Dobře >>.

614
00:50:24,480 --> 00:50:28,880
Zkuste ji spustit, a pak budu mluvit o tom na chvíli.

615
00:50:28,880 --> 00:50:35,200
[Student] Musím mít všechny funkční prototypy a všechno, že jo?

616
00:50:37,640 --> 00:50:40,840
Funkční prototypy. Oh, myslíš jako - Ano.

617
00:50:40,840 --> 00:50:43,040
Seřadit volá mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Tak, aby pro řazení volat mergeSortHelp, musí mergeSortHelp buď byly definovány

619
00:50:47,390 --> 00:50:56,370
před řadit nebo si jen potřebujete prototyp. Stačí jen zkopírovat a vložit, že.

620
00:50:56,370 --> 00:50:59,490
A podobně, mergeSortHelp volá sloučení,

621
00:50:59,490 --> 00:51:03,830
ale merge není dosud definováno, takže se můžeme jen nechat mergeSortHelp vědět

622
00:51:03,830 --> 00:51:08,700
že to, co sloučení bude vypadat, 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, tady, kde nemáme základní věc.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp je rekurzivní, takže každý rekurzivní funkce

626
00:51:38,110 --> 00:51:42,610
bude potřebovat nějaký základní věci vědět, kdy přestat rekurzivně volat sám.

627
00:51:42,610 --> 00:51:45,590
Co je náš základní scénář bude tady? Jo.

628
00:51:45,590 --> 00:51:49,110
[Student] Pokud je velikost 1? >> [Bowden] Ano.

629
00:51:49,110 --> 00:51:56,220
Tak jako jsme viděli tady, zastavili jsme se rozdělení pole

630
00:51:56,220 --> 00:52:01,850
Jakmile jsme se dostali do polí velikosti 1, což nevyhnutelně jsou seřazeny sami.

631
00:52:01,850 --> 00:52:09,530
Takže pokud velikost odpovídá 1, víme, že pole je již řazeno,

632
00:52:09,530 --> 00:52:12,970
takže můžeme jen vrátit.

633
00:52:12,970 --> 00:52:16,880
>> Všimněte si, že je neplatné, a tak jsme se nevrací nic konkrétního, jen jsme se vrátit.

634
00:52:16,880 --> 00:52:19,580
Dobře. Tak to je náš základní scénář.

635
00:52:19,580 --> 00:52:27,440
Myslím, že náš základní scénář by také mohla být, kdybychom se náhodou sloučení pole o velikosti 0,

636
00:52:27,440 --> 00:52:30,030
jsme asi chtějí zastavit na nějakém místě,

637
00:52:30,030 --> 00:52:33,610
takže stačí říci velikosti menší než 2 nebo nižší než nebo rovna 1

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

639
00:52:37,150 --> 00:52:38,870
Dobře.

640
00:52:38,870 --> 00:52:42,740
Tak to je náš základní scénář.

641
00:52:42,740 --> 00:52:45,950
Teď už chcete chodit nás přes sloučení?

642
00:52:45,950 --> 00:52:49,140
Co všechny tyto případy znamenají?

643
00:52:49,140 --> 00:52:54,480
Až tady, my jsme jen dělá stejnou myšlenku, -

644
00:52:56,970 --> 00:53:02,470
[Student] musím být kolem velikosti se všemi hovory mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Přidal jsem velikost jako další primární a není to tam, jako je velikost / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, velikost / 2, velikost / 2. >> [Student] Jo, a také ve výše uvedeném funkci.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Tady? >> [Student] Jen velikost. >> [Bowden] Oh. Velikost, velikost? >> [Student] Jo.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Dobře.

649
00:53:23,010 --> 00:53:26,580
Nechte mě přemýšlet o vteřinu.

650
00:53:26,580 --> 00:53:28,780
Líbí narazíme na problém?

651
00:53:28,780 --> 00:53:33,690
Jsme vždy zacházet levici jako 0. >> [Student] č.

652
00:53:33,690 --> 00:53:36,340
To je špatně taky. Promiňte. Mělo by to být začátek. Jo.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Dobře. Líbí se mi, že lépe.

654
00:53:39,230 --> 00:53:43,880
A konec. Dobře.

655
00:53:43,880 --> 00:53:47,200
Takže teď chceš projít nám prostřednictvím sloučení? >> [Student] Dobře.

656
00:53:47,200 --> 00:53:52,150
Jen jsem procházel tohoto nového pole, které jsem vytvořil.

657
00:53:52,150 --> 00:53:57,420
Jeho velikost je velikost části pole, které chceme třídit

658
00:53:57,420 --> 00:54:03,460
a snaží se najít prvek, který bych měl dát v novém pole kroku.

659
00:54:03,460 --> 00:54:10,140
Takže k tomu, že v první jsem ověřit, jestli je levá polovina pole i nadále mít žádné další prvky,

660
00:54:10,140 --> 00:54:14,260
a pokud tomu tak není, pak jít dolů k tomuto jinému stavu, který právě říká, že

661
00:54:14,260 --> 00:54:20,180
v pořádku, musí být v pravém poli, a dáme, že v současné indexu newArray.

662
00:54:20,180 --> 00:54:27,620
>> A pak jinak, já jsem ověřit, jestli je pravá strana pole je také skončil,

663
00:54:27,620 --> 00:54:30,630
v takovém případě jsem dal v levé.

664
00:54:30,630 --> 00:54:34,180
To by mohlo být skutečně nutné. Nejsem si jistý.

665
00:54:34,180 --> 00:54:40,970
Ale stejně, další dva kontrola, kterou z těch dvou se menší doleva nebo doprava.

666
00:54:40,970 --> 00:54:49,770
A také v každém případě, já navýšením podle toho, co zástupný I zvyšovat.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Dobře.

668
00:54:52,040 --> 00:54:53,840
To vypadá dobře.

669
00:54:53,840 --> 00:54:58,800
Má někdo nějaké připomínky nebo obavy nebo otázky?

670
00:55:00,660 --> 00:55:07,720
Takže čtyři případy, které musíme přivést věci do pouhého bytí - nebo to vypadá jako pět -

671
00:55:07,720 --> 00:55:13,100
ale musíme zvážit, zda doleva pole je vyčerpat co musíme sloučit,

672
00:55:13,100 --> 00:55:16,390
zda právo pole je vyčerpat co musíme sloučit -

673
00:55:16,390 --> 00:55:18,400
Jsem ukázal na nic.

674
00:55:18,400 --> 00:55:21,730
Takže ať levé pole došla věci nebo právo pole došel věcí.

675
00:55:21,730 --> 00:55:24,320
To jsou dva případy.

676
00:55:24,320 --> 00:55:30,920
Potřebujeme také triviální případ, zda levice, co je menší než správnou věc.

677
00:55:30,920 --> 00:55:33,910
Pak chceme zvolit levé věc.

678
00:55:33,910 --> 00:55:37,630
To jsou případy.

679
00:55:37,630 --> 00:55:40,990
Tak tohle měl pravdu, tak je to.

680
00:55:40,990 --> 00:55:46,760
Array vlevo. Je to 1, 2, 3. Dobře. Tak jo, to jsou čtyři věci, které jsme mohli chtít dělat.

681
00:55:50,350 --> 00:55:54,510
A nebudeme jít přes iterační řešení.

682
00:55:54,510 --> 00:55:55,980
Nedoporučoval bych -

683
00:55:55,980 --> 00:56:03,070
Sloučení druh je příklad funkce, která je jak to ocas rekurzivní,

684
00:56:03,070 --> 00:56:07,040
to není snadné, aby se to tail rekurzivní,

685
00:56:07,040 --> 00:56:13,450
ale také to není snadné, aby se to iterativní.

686
00:56:13,450 --> 00:56:16,910
To je velmi snadné.

687
00:56:16,910 --> 00:56:19,170
Tato implementace druhu korespondence,

688
00:56:19,170 --> 00:56:22,140
sloučení, bez ohledu na to, co děláte, budete stavět sloučení.

689
00:56:22,140 --> 00:56:29,170
>> Takže sloučit druh postaven na vrcholu sloučení rekurzivně je právě tato tři řádky.

690
00:56:29,170 --> 00:56:34,700
Iterativně, je to více nepříjemné a těžké přemýšlet o.

691
00:56:34,700 --> 00:56:41,860
Ale všimněte si, že to není ocas rekurzivní, protože mergeSortHelp - když to sama říká -

692
00:56:41,860 --> 00:56:46,590
stále musí dělat věci po tomto rekurzivních volání vrátí.

693
00:56:46,590 --> 00:56:50,830
Takže to stack frame musí nadále existovat i po volání této.

694
00:56:50,830 --> 00:56:54,170
A pak, když budete volat, musí stack frame nadále existovat

695
00:56:54,170 --> 00:56:57,780
protože i po tomto hovoru, stále potřebujeme sloučit.

696
00:56:57,780 --> 00:57:01,920
A to je triviální, aby se tento ocas rekurzivní.

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 řazení - oh, jsou dvě věci, které chci ukázat. Dobře.

700
00:57:13,400 --> 00:57:17,840
Vraťme se zpět k druhu, uděláme to rychle.

701
00:57:17,840 --> 00:57:21,030
Nebo hledejte. Řadit? Seřadit. Jo.

702
00:57:21,030 --> 00:57:22,730
Vraťme se zpět do začátků druhu.

703
00:57:22,730 --> 00:57:29,870
Chceme vytvořit algoritmus, který třídí pole pomocí libovolného algoritmu

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

705
00:57:33,660 --> 00:57:40,860
Tak, jak je to možné? Má někdo nějaký druh -

706
00:57:40,860 --> 00:57:44,300
Jsem naznačil dříve u -

707
00:57:44,300 --> 00:57:48,300
Pokud se chystáme zlepšení z n log n na O n,

708
00:57:48,300 --> 00:57:51,450
jsme zlepšili naše algoritmus časově,

709
00:57:51,450 --> 00:57:55,250
což znamená, že to, co budeme muset udělat, aby se na to?

710
00:57:55,250 --> 00:57:59,520
[Student] Space. Jo >>. Budeme používat více prostoru.

711
00:57:59,520 --> 00:58:04,490
A to i jen více prostoru, je to exponenciálně více prostoru.

712
00:58:04,490 --> 00:58:14,320
Takže si myslím, tento typ algoritmu je pseudo něco, pseudo polynomů -

713
00:58:14,320 --> 00:58:18,980
pseudo - Nemůžu si vzpomenout. Pseudo něco.

714
00:58:18,980 --> 00:58:22,210
Ale je to proto, že musíme použít tolik prostoru

715
00:58:22,210 --> 00:58:28,610
že toho lze dosáhnout, ale není reálné.

716
00:58:28,610 --> 00:58:31,220
>> A jak můžeme dosáhnout?

717
00:58:31,220 --> 00:58:36,810
Toho můžeme dosáhnout, pokud se zaručí, že určitá element v poli

718
00:58:36,810 --> 00:58:39,600
pod určitou velikost.

719
00:58:42,070 --> 00:58:44,500
Takže řekněme, že velikost je 200,

720
00:58:44,500 --> 00:58:48,130
jakýkoliv prvek v poli je nižší než velikost 200.

721
00:58:48,130 --> 00:58:51,080
A to je skutečně velmi realistický.

722
00:58:51,080 --> 00:58:58,660
Můžete velmi snadno mít pole, které víte, že vše, co v něm

723
00:58:58,660 --> 00:59:00,570
bude menší než nějaké číslo.

724
00:59:00,570 --> 00:59:07,400
Jako když mám nějaký naprosto masivní vektor, nebo tak něco

725
00:59:07,400 --> 00:59:11,810
ale víte, všechno bude mezi 0 a 5,

726
00:59:11,810 --> 00:59:14,790
pak to bude výrazně rychlejší udělat.

727
00:59:14,790 --> 00:59:17,930
A vázané na některý z prvků je 5,

728
00:59:17,930 --> 00:59:21,980
tak tento odhad, že je to, jak moc paměti budete používat.

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

730
00:59:26,300 --> 00:59:32,960
Teoreticky je vždy vázaný od celé číslo může být až 4000000000,

731
00:59:32,960 --> 00:59:40,600
ale to je nereálné, protože pak bychom používat místo

732
00:59:40,600 --> 00:59:44,400
na pořadí 4000000000. Tak to je nereálné.

733
00:59:44,400 --> 00:59:47,060
Ale tady budeme říkat naše vázaný je 200.

734
00:59:47,060 --> 00:59:59,570
Trik dělat to v O n je uděláme další pole s názvem počty velikosti VÁZÁNI.

735
00:59:59,570 --> 01:00:10,470
Takže vlastně, to je zkratka pro - Já vlastně nevím, jestli zvonění to dělá.

736
01:00:11,150 --> 01:00:15,330
Ale v GCC na přinejmenším - Jsem za předpokladu, že zvonění to dělá taky -

737
01:00:15,330 --> 01:00:18,180
to bude jen inicializaci celého pole, aby se 0s.

738
01:00:18,180 --> 01:00:25,320
Takže pokud nechci dělat, pak bych mohl samostatně udělat for (int i = 0;

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

740
01:00:31,500 --> 01:00:35,260
Takže teď je vše inicializována na 0.

741
01:00:35,260 --> 01:00:39,570
I iteraci své pole,

742
01:00:39,570 --> 01:00:51,920
a to, co dělám, je počítám počet každého - Pojď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
Co Počítám je počet výskytů každého z těchto prvků.

745
01:01:00,010 --> 01:01:03,470
Pojďme skutečně přidat pár dalších tady s některými opakování.

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

747
01:01:11,070 --> 01:01:14,850
Takže val by mohl být 4 nebo 8 nebo cokoliv jiného.

748
01:01:14,850 --> 01:01:18,870
A teď jsem počítat, kolik z této hodnoty jsem viděl,

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

750
01:01:21,230 --> 01:01:29,430
Po to provést, počítá se bude vypadat jako 0001.

751
01:01:29,430 --> 01:01:42,190
Pojďme udělat počítá [val] - ŘÍDIT + 1.

752
01:01:42,190 --> 01:01:48,230
>> Teď to je jen odpovídat za to, že jsme počínaje 0.

753
01:01:48,230 --> 01:01:50,850
Takže pokud 200 bude naše největší číslo,

754
01:01:50,850 --> 01:01:54,720
pak 0-200 je 201 věcí.

755
01:01:54,720 --> 01:02:01,540
Takže se počítá, bude to vypadat, jako 00001, protože máme jeden 4.

756
01:02:01,540 --> 01:02:10,210
Pak budeme mít 0001, kde budeme mít 1 v 8. indexu počtu.

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

758
01:02:14,560 --> 01:02:17,630
Budeme mít 2 v indexu 42. počtu.

759
01:02:17,630 --> 01:02:21,670
Takže můžeme použít počet.

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

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

762
01:02:52,540 --> 01:02:55,290
do našeho tříděném poli.

763
01:02:55,290 --> 01:03:02,000
Takže musíme sledovat, jak daleko jsme se do pole.

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

765
01:03:05,470 --> 01:03:09,910
Array - budu jen psát.

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, co chci? Myslím, že je to to, co chci.

769
01:03:35,100 --> 01:03:38,290
Ano, to vypadá dobře. Dobře.

770
01:03:38,290 --> 01:03:43,050
Takže si všichni pochopili, co je cílem mé počítá pole je?

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

772
01:03:48,140 --> 01:03:51,780
Pak jsem iterace, která se počítá pole,

773
01:03:51,780 --> 01:03:57,190
a tá pozice v poli se počítá

774
01:03:57,190 --> 01:04:01,930
je počet i to, že by se měl objevit v mém tříděném poli.

775
01:04:01,930 --> 01:04:06,840
To je důvod, proč se 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, kolik z nich chci vložit do mého tříděném poli.

778
01:04:16,900 --> 01:04:19,200
Pak jsem to.

779
01:04:19,200 --> 01:04:28,960
Jsem vložení num_of_item i to do mého tříděném poli.

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

781
01:04:32,460 --> 01:04:43,100
A tak opět, je to lineární čas, protože jsme se právě iterace přes to jednou,

782
01:04:43,100 --> 01:04:47,470
ale je to také lineární v tom, co toto číslo se stane být,

783
01:04:47,470 --> 01:04:50,730
a tak to silně závisí na tom, co je vázán.

784
01:04:50,730 --> 01:04:53,290
S vázaný na 200, to není tak špatné.

785
01:04:53,290 --> 01:04:58,330
Pokud váš vázaný bude 10.000, pak je to trochu horší,

786
01:04:58,330 --> 01:05:01,360
ale pokud vaše spojený se bude 4000000000, to je naprosto nereálné

787
01:05:01,360 --> 01:05:07,720
a toto pole bude muset být velikosti 4 miliardy korun, což je nereálné.

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

789
01:05:10,860 --> 01:05:13,270
[Neslyšitelné Student odpověď] >> Dobře.

790
01:05:13,270 --> 01:05:15,710
Uvědomil jsem si, jednu věc, když jsme šli přes.

791
01:05:17,980 --> 01:05:23,720
Myslím, že problém byl v Lucasovi a pravděpodobně jeden každý jsme viděli.

792
01:05:23,720 --> 01:05:26,330
Úplně jsem zapomněla.

793
01:05:26,330 --> 01:05:31,040
Jediné, co jsem chtěl vyjádřit, je, že když máte co do činění s věcmi, jako je indexů,

794
01:05:31,040 --> 01:05:38,320
nikdy opravdu vidět, když píšete pro smyčce,

795
01:05:38,320 --> 01:05:41,120
ale technicky, když máte co do činění s těmito indexy,

796
01:05:41,120 --> 01:05:45,950
měli byste skoro vždy řešit s celých čísel bez znaménka.

797
01:05:45,950 --> 01:05:53,850
Důvodem pro to je, když máte co do činění s podepsanými celá čísla,

798
01:05:53,850 --> 01:05:56,090
takže pokud máte 2 podepsané celá čísla a přidejte je spolu

799
01:05:56,090 --> 01:06:00,640
a oni skončí příliš velké, pak vy skončíte s záporné číslo.

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

801
01:06:03,410 --> 01:06:10,500
>> Pokud mohu přidat 2000000000 a 1000000000, jsem skončit s negativním 1000000000.

802
01:06:10,500 --> 01:06:15,480
To je, jak celá čísla pracovat na počítačích.

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 pořádku s výjimkou případů nízká stane být 2 miliardy až se stane na 1 mld. Kč,

805
01:06:23,500 --> 01:06:27,120
pak bude negativní 1 miliarda a pak budeme dělit, že 2

806
01:06:27,120 --> 01:06:29,730
a skončit s negativním 500000000.

807
01:06:29,730 --> 01:06:33,760
Tak tohle je jen problém, pokud se stalo, že se hledá přes pole

808
01:06:33,760 --> 01:06:38,070
miliard věcí.

809
01:06:38,070 --> 01:06:44,050
Ale pokud low + až se stane přetečení, pak je to problém.

810
01:06:44,050 --> 01:06:47,750
Jakmile jsme, aby byly nesignováno, pak 2 miliard eur 1000000000 je 3 mld. Kč.

811
01:06:47,750 --> 01:06:51,960
3000000000 děleno 2 je 1,5 mld. Kč.

812
01:06:51,960 --> 01:06:55,670
Takže jakmile to unsigned, všechno je perfektní.

813
01:06:55,670 --> 01:06:59,900
A tak to také problém, když jste psaní pro smyčky,

814
01:06:59,900 --> 01:07:03,940
a vlastně, to asi dělá to automaticky.

815
01:07:09,130 --> 01:07:12,330
To bude vlastně jen křičet na vás.

816
01:07:12,330 --> 01:07:21,610
Takže pokud toto číslo je příliš velký, aby se během jediné celé číslo, ale to by se vešly do celé číslo bez znaménka,

817
01:07:21,610 --> 01:07:24,970
bude křičet na tebe, tak to je důvod, proč jste nikdy narazit na problém.

818
01:07:29,150 --> 01:07:34,820
Můžete vidět, že index je nikdy nebude negativní,

819
01:07:34,820 --> 01:07:39,220
a tak, když jste iterace přes pole,

820
01:07:39,220 --> 01:07:43,970
můžete téměř vždy říci, unsigned int i, ale nemáte opravdu muset.

821
01:07:43,970 --> 01:07:47,110
Věci jdou do práce skoro stejně dobře.

822
01:07:48,740 --> 01:07:50,090
Dobře. [Šeptá] Jaký je čas?

823
01:07:50,090 --> 01:07:54,020
Poslední věc, kterou jsem chtěl ukázat - a já to prostě udělat to opravdu rychle.

824
01:07:54,020 --> 01:08:03,190
Víš, jak jsme # define, takže můžeme # define MAX jako 5 nebo tak něco?

825
01:08:03,190 --> 01:08:05,940
Pojďme to udělat MAX. # Define vázán jako 200. To je to, co jsme dělali před.

826
01:08:05,940 --> 01:08:10,380
To definuje konstantu, která je jen tak zkopírovat a vložit

827
01:08:10,380 --> 01:08:13,010
všude tam, kde se stalo psát VÁZÁNI.

828
01:08:13,010 --> 01:08:18,189
>> Takže můžeme skutečně udělat více s # definuje.

829
01:08:18,189 --> 01:08:21,170
Můžeme # define funkce.

830
01:08:21,170 --> 01:08:23,410
Jsou to opravdu funguje, ale budeme jim říkat funkce.

831
01:08:23,410 --> 01:08:36,000
Příkladem by mohl být něco jako MAX (x, y) je definována jako (x <y y:? X). Dobře.

832
01:08:36,000 --> 01:08:40,660
Takže byste měli zvyknout na syntaxi ternární operátor,

833
01:08:40,660 --> 01:08:49,029
ale je x menší než y? Návrat y, jinak vrátí x.

834
01:08:49,029 --> 01:08:54,390
Takže můžete vidět, můžete tuto samostatnou funkci,

835
01:08:54,390 --> 01:09:01,399
a funkce může být jako bool MAX trvá 2 argumenty, vrátit.

836
01:09:01,399 --> 01:09:08,340
To je jeden z nejčastějších z nich vidím udělal takhle. Říkáme jim makra.

837
01:09:08,340 --> 01:09:11,790
To je makro.

838
01:09:11,790 --> 01:09:15,859
To je jen syntaxe pro něj.

839
01:09:15,859 --> 01:09:18,740
Můžete napsat makro dělat, co chcete.

840
01:09:18,740 --> 01:09:22,649
Ty často vidět makra pro ladění printfs a tak.

841
01:09:22,649 --> 01:09:29,410
Takže typu printf, existují speciální konstanty v C jako podtržení LINE podtržítko,

842
01:09:29,410 --> 01:09:31,710
2 podtrhuje LINE podtržítko,

843
01:09:31,710 --> 01:09:37,550
a tam je také myslím, že 2 podtržítka FUNC. To by mohlo být ono. Něco takového.

844
01:09:37,550 --> 01:09:40,880
Tyto věci budou nahrazeny s názvem funkce

845
01:09:40,880 --> 01:09:42,930
nebo číslo linky, které jste na.

846
01:09:42,930 --> 01:09:48,630
Často, můžete napsat ladění printfs, že tady dole jsem mohl pak jen napsat

847
01:09:48,630 --> 01:09:54,260
DEBUG a vytiskne se číslo řádku a funkce, které jsem náhodou být v

848
01:09:54,260 --> 01:09:57,020
že došlo, že DEBUG prohlášení.

849
01:09:57,020 --> 01:09:59,550
A můžete také vytisknout jiné věci.

850
01:09:59,550 --> 01:10:05,990
Takže jedna věc, kterou by měl dávat pozor, je, jestli jsem náhodou # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
něco jako 2 * y a 2 * x.

852
01:10:11,380 --> 01:10:14,310
Takže z jakéhokoliv důvodu, jste náhodou k tomu, že hodně.

853
01:10:14,310 --> 01:10:16,650
Tak, aby to makro.

854
01:10:16,650 --> 01:10:18,680
To je skutečně zlomené.

855
01:10:18,680 --> 01:10:23,050
Nazval bych to tím, že dělá něco jako DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Takže to, co by měla být vrácena?

857
01:10:28,840 --> 01:10:30,580
[Student] 12.

858
01:10:30,580 --> 01:10:34,800
Ano, měla 12 být vráceny, a 12 je vrácena.

859
01:10:34,800 --> 01:10:43,350
3 bude nahrazeno za x, dostane 6 nahrazuje pro y, a vracíme se 2 * 6, která je 12.

860
01:10:43,350 --> 01:10:47,710
Teď co tohle? Co by se mělo vrátit?

861
01:10:47,710 --> 01:10:50,330
[Student] 14. V ideálním případě >>, 14.

862
01:10:50,330 --> 01:10:55,290
Problém je, že jak hash definuje práci, pamatujte, že je to doslovný kopírování a vkládání

863
01:10:55,290 --> 01:11:00,160
ze dne skoro všechno, takže to, co to bude vykládat jako

864
01:11:00,160 --> 01:11:11,270
je 3 méně než 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 tohoto důvodu téměř vždy zabalit vše v závorkách.

866
01:11:22,180 --> 01:11:25,050
Jakákoli proměnná téměř vždy zabalit v závorkách.

867
01:11:25,050 --> 01:11:29,570
Existují případy, kdy nemáte k, jako já vím, že nemám potřebu k tomu, že zde

868
01:11:29,570 --> 01:11:32,110
protože méně, než je do značné míry vždy jen chodit do práce,

869
01:11:32,110 --> 01:11:34,330
i když to nemusí být dokonce pravda.

870
01:11:34,330 --> 01:11:41,870
Pokud je něco směšné jako DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
pak, že se to být nahrazen s 3 méně než 1 rovná rovná 2,

872
01:11:49,760 --> 01:11:53,460
a tak pak to bude dělat 3 méně než 1, to, že rovné 2,

873
01:11:53,460 --> 01:11:55,620
což je to, co chceme.

874
01:11:55,620 --> 01:12:00,730
Tak, aby se zabránilo operátor přednost problémy,

875
01:12:00,730 --> 01:12:02,870
vždy zabalte v závorkách.

876
01:12:03,290 --> 01:12:07,700
Dobře. A to je to, 5:30.

877
01:12:08,140 --> 01:12:12,470
Máte-li jakékoli dotazy týkající se PSet, dejte nám vědět.

878
01:12:12,470 --> 01:12:18,010
To by měla být zábava, a hacker vydání je také mnohem realističtější

879
01:12:18,010 --> 01:12:22,980
než hackerské vydání v loňském roce, tak doufáme, že spousta z vás to zkusit.

880
01:12:22,980 --> 01:12:26,460
V loňském roce to byl velmi zdrcující.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]