1
00:00:00,000 --> 00:00:11,100

2
00:00:11,100 --> 00:00:12,300
>> SPEAKER 1: Ahoj všichni!

3
00:00:12,300 --> 00:00:13,890
Vítejte zpět na části.

4
00:00:13,890 --> 00:00:17,480
Tak rád, že se tak mnoho z vás i zde,
a každý, kdo se dívá online.

5
00:00:17,480 --> 00:00:18,760

6
00:00:18,760 --> 00:00:20,920
Takže jako obvykle vítejte zpátky.

7
00:00:20,920 --> 00:00:24,360
Doufám, že jste všichni měli krásné
víkend plný odpočinku, relaxace.

8
00:00:24,360 --> 00:00:26,026
To včera byla krásná ven.

9
00:00:26,026 --> 00:00:27,525
Takže doufám, že se vám to líbilo venku.

10
00:00:27,525 --> 00:00:28,840

11
00:00:28,840 --> 00:00:30,610
>> Takže nejprve pár oznámení.

12
00:00:30,610 --> 00:00:31,920

13
00:00:31,920 --> 00:00:32,700
Třídění.

14
00:00:32,700 --> 00:00:37,350
Takže většina z vás by měl dostat
napište mi o vašem Scratch pset,

15
00:00:37,350 --> 00:00:39,920
jakož i třídění pro pset 1.

16
00:00:39,920 --> 00:00:41,000

17
00:00:41,000 --> 00:00:42,220
Takže, jen pár věcí.

18
00:00:42,220 --> 00:00:45,150
Ujistěte se, že používáte check50 v style50.

19
00:00:45,150 --> 00:00:47,250
Ty mají být
prostředky pro vás,

20
00:00:47,250 --> 00:00:50,660
aby se ujistil, že jste stále
co nejvíce bodů, jak můžete

21
00:00:50,660 --> 00:00:52,390
aniž by zbytečně jejich ztráty.

22
00:00:52,390 --> 00:00:54,407
Takže věci, jako je styl
jsou velmi důležité.

23
00:00:54,407 --> 00:00:55,740
Chystáme se sundat za to.

24
00:00:55,740 --> 00:00:58,115
Někteří z vás možná již
si všiml, že z vašeho pset.

25
00:00:58,115 --> 00:00:58,920

26
00:00:58,920 --> 00:01:01,450
A check50 je jen
Opravdu snadný způsob, aby se ujistil,

27
00:01:01,450 --> 00:01:05,050
že jsme vlastně vrací to, co
musí být se vrátil k uživateli,

28
00:01:05,050 --> 00:01:06,690
a že vše funguje správně.

29
00:01:06,690 --> 00:01:08,690

30
00:01:08,690 --> 00:01:12,040
>> Na druhou poznámku, ujistěte se, že
nahrát věci do správné složky.

31
00:01:12,040 --> 00:01:14,470
To je můj život jen
trochu složitější

32
00:01:14,470 --> 00:01:18,836
pokud nahrajete pset 2 do pset 1
protože když jsem stáhnout něco,

33
00:01:18,836 --> 00:01:20,085
nemají stahovat správně.

34
00:01:20,085 --> 00:01:21,690

35
00:01:21,690 --> 00:01:24,560
A já vím, že je to trochu blbě
v systému zvyknout,

36
00:01:24,560 --> 00:01:26,950
ale jen být super
pozor, i když jen pro mě,

37
00:01:26,950 --> 00:01:30,080
tak, že když jste se dostal e-maily
v jako 2 A.M. a já jsem třídění.

38
00:01:30,080 --> 00:01:33,710
Pokud ne, protože jsem se podívat
všude kolem pro pset.

39
00:01:33,710 --> 00:01:34,440
V pohodě.

40
00:01:34,440 --> 00:01:37,270
>> Já vím, že je to brzy, ale já
úplně dostal vzlétlo stráž

41
00:01:37,270 --> 00:01:40,800
eseje, která je v důsledku této pátek, že
moji profesoři byli jen rádi, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Pamatujte si, že máte
esej kvůli v pátek.

43
00:01:42,550 --> 00:01:45,780
Takže vím, že nikdo rád
přemýšlet o tom, midterms,

44
00:01:45,780 --> 00:01:50,620
ale váš první kvíz je 15. října,
který října se začíná tento týden.

45
00:01:50,620 --> 00:01:53,290
Tak, to by mohlo být dříve
než jste očekávali, je vše.

46
00:01:53,290 --> 00:01:57,510
Tak, že nejste házet nepřipraveného když
Zmiňuji se o část příští týden, že oh,

47
00:01:57,510 --> 00:02:00,560
Váš test příští týden, myslel jsem,
Já bych vám trochu více

48
00:02:00,560 --> 00:02:01,500
z hlav se nyní.

49
00:02:01,500 --> 00:02:02,970

50
00:02:02,970 --> 00:02:04,660
>> Takže nastavit váš problém, číslo tři.

51
00:02:04,660 --> 00:02:07,070
Jak lidé číst
spec ze zvědavosti?

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
OK.

54
00:02:09,199 --> 00:02:10,229
Máme pár.

55
00:02:10,229 --> 00:02:12,320
Druh dolů z posledního
týdně, ale to je v pořádku.

56
00:02:12,320 --> 00:02:13,650
Vím, že to bylo krásné ven.

57
00:02:13,650 --> 00:02:15,120

58
00:02:15,120 --> 00:02:16,660
Tak Break Out.

59
00:02:16,660 --> 00:02:21,010
Rozhodně po stihnout
dnes číst spec alespoň

60
00:02:21,010 --> 00:02:25,240
zkuste jako stažení
Distribuce kód a provoz

61
00:02:25,240 --> 00:02:27,430
jako první počáteční
věc, která vás žádají, abyste.

62
00:02:27,430 --> 00:02:28,681

63
00:02:28,681 --> 00:02:32,590
Protože jsme pomocí
distribuce kód a knihovny

64
00:02:32,590 --> 00:02:36,790
že jsme teprve using-- --It jen
Podruhé jsme udělali tuto pset,

65
00:02:36,790 --> 00:02:38,650
bláznivé věci se může stát
s přístrojem,

66
00:02:38,650 --> 00:02:41,370
a chcete zjistit, že
venku proti později.

67
00:02:41,370 --> 00:02:45,570
>> Vzhledem k tomu, jestli je to ve čtvrtek v noci, nebo je to
Ve středu v noci a z nějakého důvodu

68
00:02:45,570 --> 00:02:48,912
Váš spotřebič prostě není
chcete spustit s knihovnou

69
00:02:48,912 --> 00:02:50,620
nebo distribuce
kód, to znamená

70
00:02:50,620 --> 00:02:52,309
nemůžete ani začít dělat kódování.

71
00:02:52,309 --> 00:02:54,100
Protože není možné kontrolovat
aby zjistil, jestli to funguje.

72
00:02:54,100 --> 00:02:55,975
Váš nebudu moci
aby zjistil, jestli to překládá.

73
00:02:55,975 --> 00:03:00,500
Chcete se postarat o ty, které na začátku roku
týden, kdy můžete mi ještě e-mail

74
00:03:00,500 --> 00:03:03,100
nebo jeden z dalších TFS
a můžeme dostat ty, které stanoví.

75
00:03:03,100 --> 00:03:05,410
Vzhledem k tomu, to jsou otázky,
které tě zastavit

76
00:03:05,410 --> 00:03:07,120
v tom, aby žádný skutečný pokrok.

77
00:03:07,120 --> 00:03:10,055
Není to jako jednu chybu, že
můžete jen tak přeskočit.

78
00:03:10,055 --> 00:03:10,712

79
00:03:10,712 --> 00:03:13,420
Pokud máte problémy se svým
zařízení nebo distribuce kód,

80
00:03:13,420 --> 00:03:16,211
Opravdu chcete, aby si to vzít
péče o spíše dříve než později.

81
00:03:16,211 --> 00:03:20,410
Takže i když jste nebudeš ve skutečnosti
začít psát kód, stáhněte si distribuci

82
00:03:20,410 --> 00:03:24,040
kód, přečtěte si spec, ujistěte se,
všechno, co se tam pracuje.

83
00:03:24,040 --> 00:03:25,134
OK?

84
00:03:25,134 --> 00:03:27,675
Pokud se vám prostě to, že jsem
Slibuji svůj život bude jednodušší.

85
00:03:27,675 --> 00:03:28,800

86
00:03:28,800 --> 00:03:31,410
A tak budete pravděpodobně
to udělat teď hned?

87
00:03:31,410 --> 00:03:32,100
OK.

88
00:03:32,100 --> 00:03:33,950
Takže tam nějaké otázky?

89
00:03:33,950 --> 00:03:35,850
Veškeré logistické věci?

90
00:03:35,850 --> 00:03:36,910
Každý, kdo je dobrý?

91
00:03:36,910 --> 00:03:38,270
OK.

92
00:03:38,270 --> 00:03:41,700
>> Disclaimer pro ty,
Jste v místnosti a on-line.

93
00:03:41,700 --> 00:03:45,437
Budu se snažit přepínat
mezi PowerPoint v zařízení

94
00:03:45,437 --> 00:03:47,270
Protože se chystáme
bude dělat nějaké kódování

95
00:03:47,270 --> 00:03:53,630
dnes populární poptávky anonymní
návrh hlasování jsem poslal minulý týden.

96
00:03:53,630 --> 00:03:55,480
Takže budeme dělat nějaké kódování.

97
00:03:55,480 --> 00:03:57,800
Takže pokud vy také chtít
střílet vaše zařízení,

98
00:03:57,800 --> 00:04:02,910
a měli jste dostali e-mail
ode mne, s ukázkový soubor.

99
00:04:02,910 --> 00:04:04,310
Prosím, neváhejte to udělat.

100
00:04:04,310 --> 00:04:07,340
>> Takže, budeme mluvit o
GDB, který je debugger.

101
00:04:07,340 --> 00:04:09,970
Bude to, aby vám pomohl
druh zjistit, kde

102
00:04:09,970 --> 00:04:11,860
věci jdou špatně v kódu.

103
00:04:11,860 --> 00:04:15,370
Je to opravdu jen způsob, jak krok
prostřednictvím kódu, jak je to se děje,

104
00:04:15,370 --> 00:04:19,100
a musí být schopen vytisknout proměnné
nebo zjistit, co se vlastně děje

105
00:04:19,100 --> 00:04:22,980
Pod kapotou verše program
právě běží, je to jako chybující,

106
00:04:22,980 --> 00:04:25,030
a ty jsi jako, žádný nápad
co se tu právě stalo.

107
00:04:25,030 --> 00:04:26,730
Já nevím, co řádek to propadlo na.

108
00:04:26,730 --> 00:04:29,040
Nevím, kde se stala chyba.

109
00:04:29,040 --> 00:04:31,280
Takže, GDB bude, aby vám pomohl s tím.

110
00:04:31,280 --> 00:04:35,240
Také, pokud se rozhodnete
pokračovat ano, a vzít 61,

111
00:04:35,240 --> 00:04:38,430
to bude opravdu, ale opravdu být vaše
nejlepší přítel, protože jsem vám říct,

112
00:04:38,430 --> 00:04:40,840
proto, že jsem procházel této třídy.

113
00:04:40,840 --> 00:04:43,620
>> Jedeme se podívat na binární
Hledání, které, pokud vy pamatovat

114
00:04:43,620 --> 00:04:47,540
velký telefonní seznam příkladů
Podívaná ze třídy.

115
00:04:47,540 --> 00:04:50,620
Budeme se provádí to, a
procházce, že trochu víc,

116
00:04:50,620 --> 00:04:54,650
a pak jedeme přes čtyři
různé druhy, které jsou Bubble,

117
00:04:54,650 --> 00:04:56,285
Výběr, vkládání, a sloučit.

118
00:04:56,285 --> 00:04:57,830

119
00:04:57,830 --> 00:04:58,330
V pohodě.

120
00:04:58,330 --> 00:05:00,390
Takže, GDB, jak jsem již zmínil, je debugger.

121
00:05:00,390 --> 00:05:01,400

122
00:05:01,400 --> 00:05:09,370
A ty jsou trochu velký
věci, velké funkce nebo příkazy

123
00:05:09,370 --> 00:05:13,240
které používáte v GDB, a já budu chodit
si přes demo se převede do druhé.

124
00:05:13,240 --> 00:05:15,360
>> Takže, to není jen
Zůstaneš abstraktní.

125
00:05:15,360 --> 00:05:18,000
Pokusím se, aby to jako beton
jak je to možné pro vás.

126
00:05:18,000 --> 00:05:19,870
Takže, zlomit.

127
00:05:19,870 --> 00:05:22,200
To bude přestávka buď
jako, nějaké číslo, které

128
00:05:22,200 --> 00:05:26,900
představuje řádek v programu,
nebo můžete pojmenovat funkci.

129
00:05:26,900 --> 00:05:30,150
Takže, pokud řekneš rozbít hlavní,
se zastaví na hlavní,

130
00:05:30,150 --> 00:05:32,400
a umožní vám projít tuto funkci.

131
00:05:32,400 --> 00:05:36,350
>> Stejně tak, pokud máte nějaké externí
fungují jako Swap nebo kostka,

132
00:05:36,350 --> 00:05:38,450
že jsme se podívali na minulý týden.

133
00:05:38,450 --> 00:05:41,780
Pokud řeknete rozbít jeden z těch,
když váš program zasáhne to,

134
00:05:41,780 --> 00:05:44,290
to na tebe čekat na
říká, co má dělat.

135
00:05:44,290 --> 00:05:47,860
Než to bude jen spustit, takže vám
by se skutečně krok uvnitř funkce

136
00:05:47,860 --> 00:05:49,020
a uvidíte, co se děje.

137
00:05:49,020 --> 00:05:50,370

138
00:05:50,370 --> 00:05:53,515
Takže další, prostě přeskočí
další řádek, přejde funkce.

139
00:05:53,515 --> 00:05:54,730

140
00:05:54,730 --> 00:05:55,560
Krok.

141
00:05:55,560 --> 00:05:56,810
To vše jsou trochu abstraktní.

142
00:05:56,810 --> 00:06:00,530
Tak jsem jen tak běžet přes ně,
ale vy je uvidíte v použití v druhé.

143
00:06:00,530 --> 00:06:01,810
>> Vstupte do funkce.

144
00:06:01,810 --> 00:06:04,170
Takže jak jsem říkal,
jako u Swap, by to

145
00:06:04,170 --> 00:06:07,110
umožňují skutečně, jako kdyby jste
jako fyzicky krokování uvnitř,

146
00:06:07,110 --> 00:06:10,990
můžete si s těmito proměnnými, tisk
to, co oni jsou, co se děje.

147
00:06:10,990 --> 00:06:12,140

148
00:06:12,140 --> 00:06:14,830
Seznam bude doslova jen vytisknout
z okolního kódu.

149
00:06:14,830 --> 00:06:17,570
Takže, pokud jste trochu zapomenout
kde jste ve vašem programu,

150
00:06:17,570 --> 00:06:19,880
nebo jste zvědaví,
co se děje kolem něj,

151
00:06:19,880 --> 00:06:23,790
to bude jen vytisknout segmentu
podobných pět nebo šest řádků kolem něj.

152
00:06:23,790 --> 00:06:26,080
Takže můžete lépe zorientovat
o tom, kde se právě nacházíte.

153
00:06:26,080 --> 00:06:27,230

154
00:06:27,230 --> 00:06:28,650
>> Vytisknout nějaké proměnné.

155
00:06:28,650 --> 00:06:34,590
Takže, pokud máte klíč jako
v Caesar, že se podíváme na.

156
00:06:34,590 --> 00:06:36,220
Můžete říct, že PRINT na každém místě.

157
00:06:36,220 --> 00:06:40,070
To vám řeknu, co je hodnota, takže
že možná někde na cestě,

158
00:06:40,070 --> 00:06:42,070
k přepisu klíč.

159
00:06:42,070 --> 00:06:45,495
Můžete si skutečně říct, že proto, že
můžete skutečně sledovat tuto hodnotu.

160
00:06:45,495 --> 00:06:46,500

161
00:06:46,500 --> 00:06:48,780
>> V místních obyvatel, jen tisky
z vašich lokálních proměnných.

162
00:06:48,780 --> 00:06:53,120
Takže, kdykoliv jste ve smyčce,
a vy prostě chcete vidět podobné, oh.

163
00:06:53,120 --> 00:06:54,270
Jaká je moje já?

164
00:06:54,270 --> 00:06:57,020
Jaká je tato hodnota klíče
že jsem inicializovat tady?

165
00:06:57,020 --> 00:06:58,537
Co je zpráva v tomto bodě?

166
00:06:58,537 --> 00:07:00,370
To bude jen vytisknout vše
z těch, takže vás

167
00:07:00,370 --> 00:07:04,330
Nemusíte se jednotlivě
říci, tisk I. Print Message.

168
00:07:04,330 --> 00:07:04,970
Print Key.

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
A poté displej.

171
00:07:07,700 --> 00:07:10,370
Co to dělá, je jako vy
krok v rámci programu,

172
00:07:10,370 --> 00:07:13,980
to bude jen ujistit, že je to
zobrazovat jen některé proměnné

173
00:07:13,980 --> 00:07:14,780
v každém bodě.

174
00:07:14,780 --> 00:07:17,160
Aby jste also-- --it to
druh zástupce kde

175
00:07:17,160 --> 00:07:19,530
nemusíte jít dál, jako, oh.

176
00:07:19,530 --> 00:07:23,150
Print Key nebo Tisk I. Prostě
automaticky to pro vás.

177
00:07:23,150 --> 00:07:25,959
>> Takže, s tím, že budeme
vidět, jak to jde.

178
00:07:25,959 --> 00:07:28,000
Budu se snažit a spínače
k mému přístroji.

179
00:07:28,000 --> 00:07:30,200

180
00:07:30,200 --> 00:07:31,271
Uvidíme, jestli to zvládnu.

181
00:07:31,271 --> 00:07:31,770
All.

182
00:07:31,770 --> 00:07:40,970

183
00:07:40,970 --> 00:07:42,370
Jsme jen bude zrcadlit.

184
00:07:42,370 --> 00:07:44,530
Není nic, co blázen
na mém notebooku kdekoli.

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
OK.

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
To musí být tato.

189
00:08:01,054 --> 00:08:01,795
Je to tak malé.

190
00:08:01,795 --> 00:08:03,730

191
00:08:03,730 --> 00:08:05,120
Uvidíme, jestli to můžeme udělat.

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> OK.

194
00:08:10,940 --> 00:08:15,305
Alice se samozřejmě snaží
zde jen trochu,

195
00:08:15,305 --> 00:08:17,995
ale my si to v Momento.

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
OK.

198
00:08:22,020 --> 00:08:25,900
Jsme jen poroste to.

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
OK.

201
00:08:29,380 --> 00:08:31,679
Může každý druh vidět, že?

202
00:08:31,679 --> 00:08:32,470
Možná trochu?

203
00:08:32,470 --> 00:08:33,594
Já vím, je to trochu malý.

204
00:08:33,594 --> 00:08:34,570

205
00:08:34,570 --> 00:08:37,530
Nemůžete docela přijít na to,
jak se dělá to větší.

206
00:08:37,530 --> 00:08:38,350
Pokud někdo zná.

207
00:08:38,350 --> 00:08:40,309
Ví někdo, jak na to větší?

208
00:08:40,309 --> 00:08:40,932
OK.

209
00:08:40,932 --> 00:08:42,140
Chystáme se vrátit s ním.

210
00:08:42,140 --> 00:08:45,801
Nezáleží na tom tak jako tak, protože je to jen
To je kód, který vy by

211
00:08:45,801 --> 00:08:46,300
mají.

212
00:08:46,300 --> 00:08:48,310
>> Co je důležitější,
je terminál zde.

213
00:08:48,310 --> 00:08:52,840

214
00:08:52,840 --> 00:08:58,690
A máme tady Proč je to tak malý?

215
00:08:58,690 --> 00:09:02,325

216
00:09:02,325 --> 00:09:02,825
Nastavení.

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
Oh.

219
00:09:08,420 --> 00:09:09,500
Pravda Ike.

220
00:09:09,500 --> 00:09:10,880
Jak je to?

221
00:09:10,880 --> 00:09:11,770
Odtamtud.

222
00:09:11,770 --> 00:09:19,370

223
00:09:19,370 --> 00:09:21,810
Je to lepší pro všechny?

224
00:09:21,810 --> 00:09:22,525
OK ,.

225
00:09:22,525 --> 00:09:23,025
V pohodě.

226
00:09:23,025 --> 00:09:25,830

227
00:09:25,830 --> 00:09:28,220
>> Víte, kdy jste v CS
třídy technické problémy

228
00:09:28,220 --> 00:09:32,971
jsou trochu součástí the--
Takže, pojďme vyčistit to.

229
00:09:32,971 --> 00:09:33,470
OK.

230
00:09:33,470 --> 00:09:38,060
Takže, tady v sekci
které jsme tu měli.

231
00:09:38,060 --> 00:09:40,830
Caesar je spustitelný soubor.

232
00:09:40,830 --> 00:09:41,800
Tak jsem udělal to.

233
00:09:41,800 --> 00:09:46,370
Takže jedna věc je si uvědomit, s GDB je
že to funguje jen na spustitelné soubory.

234
00:09:46,370 --> 00:09:48,040
Takže nemůžete spustit na dotsy.

235
00:09:48,040 --> 00:09:50,532
Musíte vlastně dělat
Ujistěte se, že váš kód zkompiluje,

236
00:09:50,532 --> 00:09:51,865
a že to může být ve skutečnosti spustit.

237
00:09:51,865 --> 00:09:52,970

238
00:09:52,970 --> 00:09:56,186
>> Takže, ujistěte se, že pokud se tak nestane
sestavit si to zkompilovat,

239
00:09:56,186 --> 00:09:57,810
takže můžete trochu projet.

240
00:09:57,810 --> 00:10:04,590
Tak pro začátek GDB, vše, co udělat,
Typ Gloria GDB, a pak už jen

241
00:10:04,590 --> 00:10:06,250
soubor, který chcete.

242
00:10:06,250 --> 00:10:08,240
Vždycky jsem chybně Caesara.

243
00:10:08,240 --> 00:10:11,730
Ale vy chcete ujistit,
protože je to spustitelný,

244
00:10:11,730 --> 00:10:14,210
TI dot blesk tak, aby
znamená, že jdeš

245
00:10:14,210 --> 00:10:19,240
spustit CSI budete provádět
to soubory buď v debuggeru.

246
00:10:19,240 --> 00:10:19,910
OK.

247
00:10:19,910 --> 00:10:22,885
Takže, to, že se dostanete
tento druh blábol.

248
00:10:22,885 --> 00:10:24,250

249
00:10:24,250 --> 00:10:25,750
Je to jen všechno o debuggeru.

250
00:10:25,750 --> 00:10:28,200
Ty opravdu nemají na
starat o to právě teď.

251
00:10:28,200 --> 00:10:31,460
A jak vidíte, máme to
otevřené parens, HDP, v blízkosti parens,

252
00:10:31,460 --> 00:10:34,690
a jen tak vypadá
naše příkazového řádku, je to tak?

253
00:10:34,690 --> 00:10:37,010
>> Takže, co chceme do--
-SO, První věc,

254
00:10:37,010 --> 00:10:39,570
je chceme vybrat
místo, kde je zlomit.

255
00:10:39,570 --> 00:10:42,332
Takže, tam je jedna chyba
v tomto programu Caesar

256
00:10:42,332 --> 00:10:44,290
že jsem se představit, že
jdeme zjistit.

257
00:10:44,290 --> 00:10:45,330

258
00:10:45,330 --> 00:10:56,350
To, co to je, že se vstup
Barfoo ve všech čepice, a z nějakého důvodu

259
00:10:56,350 --> 00:11:01,950
nemění A. Je to prostě odejde
je sám, je všechno ostatní v pořádku,

260
00:11:01,950 --> 00:11:03,980
ale druhý dopis
Zůstává beze změny.

261
00:11:03,980 --> 00:11:07,120
Takže, budeme se snažit a
přijít na to, proč tomu tak je.

262
00:11:07,120 --> 00:11:10,440
Takže první věc, kterou obvykle
chci dělat při každém spuštění na GDB

263
00:11:10,440 --> 00:11:12,010
je přijít na to, kde ji zlomit.

264
00:11:12,010 --> 00:11:14,956
>> Takže Caesar je docela krátký program.

265
00:11:14,956 --> 00:11:16,330
Máme jen jednu funkci, ne?

266
00:11:16,330 --> 00:11:18,520
Jaké bylo naše funkce v Caesar?

267
00:11:18,520 --> 00:11:19,590

268
00:11:19,590 --> 00:11:24,350
Je tu jen jedna funkce, hlavní je to tak?

269
00:11:24,350 --> 00:11:26,490
Hlavní je funkce
pro všechny programy.

270
00:11:26,490 --> 00:11:29,230
Pokud jste neměli Main, mohl bych
je hned trochu strach teď,

271
00:11:29,230 --> 00:11:31,000
ale doufám, že jste všichni měli Main tam.

272
00:11:31,000 --> 00:11:34,150
Takže, co můžeme udělat, je, můžeme
prostě rozbít Main, stejně jako to.

273
00:11:34,150 --> 00:11:35,190
Tak, to říká, OK.

274
00:11:35,190 --> 00:11:37,430
Tam My jsme nastavili zarážky jeden.

275
00:11:37,430 --> 00:11:42,870
>> Tak, teď věc k zapamatování je Caesar
trvá jeden argument příkazového řádku právo

276
00:11:42,870 --> 00:11:45,150
a my jsme to ještě neudělali kdekoliv.

277
00:11:45,150 --> 00:11:47,560
Takže, co děláte, je-li
jste vlastně jít spustit

278
00:11:47,560 --> 00:11:51,540
program, program, který jste
běží v GDB, který potřebuje příkazový řádek

279
00:11:51,540 --> 00:11:55,010
argumenty, budete k zadání
při prvním spuštění běží to.

280
00:11:55,010 --> 00:11:59,280
Takže v tomto případě, my
Běh s klíčem tři.

281
00:11:59,280 --> 00:12:00,770

282
00:12:00,770 --> 00:12:02,040
A to se skutečně začít.

283
00:12:02,040 --> 00:12:08,480
>> Takže, pokud zde vidíte, máme
Je-li RC se nerovná 2.

284
00:12:08,480 --> 00:12:12,210
Takže pokud vy všichni mají
že soubor, který jsem poslal nahoru

285
00:12:12,210 --> 00:12:15,100
uvidíte, že to je jako
První řádek naše hlavní funkce, ne?

286
00:12:15,100 --> 00:12:17,890
Je to kontroluje, zda je k dispozici
správný počet argumentů.

287
00:12:17,890 --> 00:12:20,620
Takže, pokud jste přemýšlel,
RC-li správné,

288
00:12:20,620 --> 00:12:23,250
můžete dělat něco jen jako Print RC.

289
00:12:23,250 --> 00:12:24,380

290
00:12:24,380 --> 00:12:28,640
RC je dvě, což je
to, co jsme očekávali, že jo?

291
00:12:28,640 --> 00:12:32,010
>> Takže můžeme jít dál,
a pokračovat přes.

292
00:12:32,010 --> 00:12:33,200
Takže, máme tam nějaký klíč.

293
00:12:33,200 --> 00:12:34,260

294
00:12:34,260 --> 00:12:37,090
A můžeme vytisknout náš klíč
aby se ujistil, že je to správné.

295
00:12:37,090 --> 00:12:38,380

296
00:12:38,380 --> 00:12:39,500
Zajímavé.

297
00:12:39,500 --> 00:12:41,210
Ne tak docela, co jsme očekávali.

298
00:12:41,210 --> 00:12:44,810
Takže jedna věc je si uvědomit,
s GDB také, je

299
00:12:44,810 --> 00:12:49,000
že to není, dokud se skutečně hit
Dále, že řádek, který jste právě viděli

300
00:12:49,000 --> 00:12:50,720
je ve skutečnosti proveden.

301
00:12:50,720 --> 00:12:53,870
Takže v tomto případě klíčem
nebylo přiděleno dosud.

302
00:12:53,870 --> 00:12:57,050
Takže klíč je nějaký odpad hodnota
které vidíte na tam dole.

303
00:12:57,050 --> 00:13:03,680
Negativní --It je jeden miliard dolarů 120--
a něco divného věci do pořádku?

304
00:13:03,680 --> 00:13:05,340
Není to klíč, který jsme očekávali.

305
00:13:05,340 --> 00:13:10,720
Ale když jsme narazili na Další a pak jsme
pokusit Print klíč, je to tři.

306
00:13:10,720 --> 00:13:11,710
>> Všichni vidí, že?

307
00:13:11,710 --> 00:13:13,780
Takže, pokud máte něco
že jste jako, počkejte.

308
00:13:13,780 --> 00:13:15,540
To je zcela
špatně, a já nevím,

309
00:13:15,540 --> 00:13:20,150
jak by se to stalo, protože všechno, co chci
udělat, je přiřadit číslo, proměnná,

310
00:13:20,150 --> 00:13:22,900
zkuste bít Další, zkuste tisknout
znovu, a uvidíme, jestli to funguje.

311
00:13:22,900 --> 00:13:27,830
Vzhledem k tomu, že to jen bude provádět a
vlastně přiřadit něco po vás

312
00:13:27,830 --> 00:13:29,340
Další hit.

313
00:13:29,340 --> 00:13:30,336
Smysl pro každého?

314
00:13:30,336 --> 00:13:30,836
Hm?

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Při náhodné
čísla, co to znamená?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: Je to jen náhodný.

317
00:13:34,790 --> 00:13:35,710
Je to jen odpad.

318
00:13:35,710 --> 00:13:38,320
Je to prostě něco, že vaše
Počítač bude náhodně přiřadí.

319
00:13:38,320 --> 00:13:39,721

320
00:13:39,721 --> 00:13:40,220
V pohodě.

321
00:13:40,220 --> 00:13:45,760
Tak, teď se můžeme pohybovat, a tak
nyní máme tento prostý text getString.

322
00:13:45,760 --> 00:13:48,600
Takže, dovolte mi představit, co
se stane, když jsme narazili Další zde.

323
00:13:48,600 --> 00:13:51,320
Naše GDB druh zmizí, že jo?

324
00:13:51,320 --> 00:13:55,720
To proto, že getString
Nyní je realizovat, ne?

325
00:13:55,720 --> 00:14:01,460
Takže, když jsme viděli, prostý text rovná
GetString, otevřené parens a parens,

326
00:14:01,460 --> 00:14:04,380
a my hit Další, která má
Nyní skutečně popraven.

327
00:14:04,380 --> 00:14:06,580
Takže, je to čekání na
nám vstup něco.

328
00:14:06,580 --> 00:14:13,560
>> Takže jdeme na vstup naše jídlo, které
je to, co to nedaří, jak jsem vám řekl,

329
00:14:13,560 --> 00:14:18,020
a to jen říká, že je to
po spuštění, že zavřeno

330
00:14:18,020 --> 00:14:19,980
držák znamená, že je
vystupující z této smyčky.

331
00:14:19,980 --> 00:14:21,170

332
00:14:21,170 --> 00:14:25,420
Takže můžeme zasáhnout Další a teď, když jsem
jistý, že jste všichni obeznámeni od Caesara,

333
00:14:25,420 --> 00:14:27,260
je to, co je tato linka bude dělat.

334
00:14:27,260 --> 00:14:32,030
Je to pro int i = 0, N se rovná
Strlen, prostý text, a pak

335
00:14:32,030 --> 00:14:33,960
I je menší než n, I, plus, plus.

336
00:14:33,960 --> 00:14:35,210
Co je to smyčka dělat?

337
00:14:35,210 --> 00:14:37,900

338
00:14:37,900 --> 00:14:39,160
Otevřete zprávu.

339
00:14:39,160 --> 00:14:39,770
V pohodě.

340
00:14:39,770 --> 00:14:41,330
Takže, pojďme začít dělat to.

341
00:14:41,330 --> 00:14:47,210
>> Takže, pokud by tato podmínka
zápas, pro naše první?

342
00:14:47,210 --> 00:14:52,250
Pokud je to B, je to prostý text I. jsme
můžete získat informace o našich místních obyvatel.

343
00:14:52,250 --> 00:14:53,610

344
00:14:53,610 --> 00:14:57,970
Takže, je nula, a je-li šest, které
očekáváme, a naším hlavním je tři.

345
00:14:57,970 --> 00:14:59,227
Vše, co dává smysl, ne?

346
00:14:59,227 --> 00:15:01,310
Tato čísla jsou
přesně to, co by mělo být.

347
00:15:01,310 --> 00:15:02,590

348
00:15:02,590 --> 00:15:03,870
Takže, hučení?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Mám
náhodná čísla pro můj.

350
00:15:05,620 --> 00:15:09,156

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: No, můžeme check-- --we
můžete chatovat o tom ve vteřině.

352
00:15:12,030 --> 00:15:14,110

353
00:15:14,110 --> 00:15:15,750
Ale měli byste být stále to.

354
00:15:15,750 --> 00:15:17,700

355
00:15:17,700 --> 00:15:20,130
Takže, pokud máme kapitál
B pro naše první,

356
00:15:20,130 --> 00:15:22,080
tato podmínka by ho chytit, ne?

357
00:15:22,080 --> 00:15:27,120
Takže, když jsme narazili na Next, vidíme,
že, pokud skutečně vykonává.

358
00:15:27,120 --> 00:15:29,220
Protože pokud jste po
spolu v kódu,

359
00:15:29,220 --> 00:15:33,460
tento řádek tady, kde prostý text I
se nahrazuje tímto aritmetice,

360
00:15:33,460 --> 00:15:35,720
provede pouze v případě if
Podmínkou je správné v pořádku?

361
00:15:35,720 --> 00:15:36,905

362
00:15:36,905 --> 00:15:40,240
>> GDB bude jen ukázat vám,
věci, které jsou skutečně provádění.

363
00:15:40,240 --> 00:15:45,140
Takže pokud tato podmínka Pokud nebyla splněna, je to
jen tak přeskočit na další řádek.

364
00:15:45,140 --> 00:15:46,540
OK?

365
00:15:46,540 --> 00:15:48,510
Takže, máme to.

366
00:15:48,510 --> 00:15:51,171
Tento držák znamená, že je
zavřeno z této smyčky teď.

367
00:15:51,171 --> 00:15:52,420
Takže, bude to začít znovu.

368
00:15:52,420 --> 00:15:54,760

369
00:15:54,760 --> 00:15:56,280
Stejně jako, že.

370
00:15:56,280 --> 00:15:59,120
Tak, že se můžeme dostat informace
o našich místních obyvatel zde,

371
00:15:59,120 --> 00:16:02,575
a vidíme, že naše první
dopis změnilo, že?

372
00:16:02,575 --> 00:16:05,150
Nyní je E, jak to má být.

373
00:16:05,150 --> 00:16:07,360
Ano, můžeme pokračovat dál.

374
00:16:07,360 --> 00:16:08,500
>> A máme tuto kontrolu.

375
00:16:08,500 --> 00:16:09,916
A pokud tato kontrola by měla fungovat, ne?

376
00:16:09,916 --> 00:16:12,570
Je to A. Je třeba změnit
tři písmena vpřed.

377
00:16:12,570 --> 00:16:14,320

378
00:16:14,320 --> 00:16:16,530
Ale pokud si všimnete, my
něco jiného.

379
00:16:16,530 --> 00:16:17,580

380
00:16:17,580 --> 00:16:22,860
Takže v tomto případě tady, to chytil
to, a tak tato linka vykonán,

381
00:16:22,860 --> 00:16:28,620
které upravovalo naši B.
Ale v tomto případě je zde,

382
00:16:28,620 --> 00:16:32,860
jsme, že to prostě přeskočí ji,
a šel na [? L Koná. ?]

383
00:16:32,860 --> 00:16:34,660
Takže něco se tam děje.

384
00:16:34,660 --> 00:16:37,780
Co, že to říkám, je to,
víme, že by měl zachytit tu,

385
00:16:37,780 --> 00:16:39,200
ale není tomu tak.

386
00:16:39,200 --> 00:16:42,210
Může někdo vidět, co naši
Problém je v tomto řádku?

387
00:16:42,210 --> 00:16:45,380

388
00:16:45,380 --> 00:16:46,969
Je to velmi minutu věc.

389
00:16:46,969 --> 00:16:48,510
A můžete se také podívat na váš kód.

390
00:16:48,510 --> 00:16:49,980

391
00:16:49,980 --> 00:16:54,940
Je to také line-- zapomenout na to, co vedení je
v there-- ale je to v [neslyšitelné].

392
00:16:54,940 --> 00:16:55,480
Ano?

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: Je to na více než
strana, pokud ji četl v knize.

394
00:16:58,639 --> 00:16:59,430
SPEAKER 1: Přesně tak.

395
00:16:59,430 --> 00:17:02,620
Takže, debugger nemohl říct
si to, ale debugger

396
00:17:02,620 --> 00:17:05,880
Ty by mohly získat až na linii
že víte, není funkční.

397
00:17:05,880 --> 00:17:09,319
A někdy, když zejména
později v semestru, kdy

398
00:17:09,319 --> 00:17:12,910
máte co do činění s sto, a
sto pár řádků kódu, a vy

399
00:17:12,910 --> 00:17:16,190
Nevím, kde se to nedaří,
je to skvělý způsob, jak to udělat.

400
00:17:16,190 --> 00:17:17,900

401
00:17:17,900 --> 00:17:18,989
Takže jsme našli chybu.

402
00:17:18,989 --> 00:17:21,530
Můžete opravit v souboru,
a pak je možné jej znovu spustit,

403
00:17:21,530 --> 00:17:23,029
a všechno bude perfektně fungovat.

404
00:17:23,029 --> 00:17:24,970

405
00:17:24,970 --> 00:17:30,590
A největší věc je
to může zdát, OK.

406
00:17:30,590 --> 00:17:31,090
Jo.

407
00:17:31,090 --> 00:17:31,370
V pohodě.

408
00:17:31,370 --> 00:17:32,744
Věděli jste, co hledáte.

409
00:17:32,744 --> 00:17:34,910
Takže jste věděl, co má dělat.

410
00:17:34,910 --> 00:17:39,021
>> GDB může být super užitečné, protože vám
můžete vytisknout všechny tyto věci, které jste

411
00:17:39,021 --> 00:17:39,520
ne.

412
00:17:39,520 --> 00:17:41,160
Je to mnohem užitečnější než printf.

413
00:17:41,160 --> 00:17:43,440
Jak mnozí z vás používají
jako prohlášení printf

414
00:17:43,440 --> 00:17:46,200
zjistit, kde chyba byla, že jo?

415
00:17:46,200 --> 00:17:48,450
Takže, s tím, že ne
musí neustále vracet,

416
00:17:48,450 --> 00:17:51,139
a jako komentování na
Printf nebo okomentování,

417
00:17:51,139 --> 00:17:52,930
a zjistit, co
měli byste být tisk.

418
00:17:52,930 --> 00:17:55,670
To vlastně jen vám umožní
krokovat, vytiskněte věci

419
00:17:55,670 --> 00:18:00,000
jak jste prochází, takže můžete
pozorovat, jak se mění v reálném čase,

420
00:18:00,000 --> 00:18:02,190
jak váš program běží.

421
00:18:02,190 --> 00:18:04,390
>> A to trvat trochu
trochu zvykat.

422
00:18:04,390 --> 00:18:07,850
Já bych Velmi doporučuji jen tak
z toho trochu frustrovaný s ním

423
00:18:07,850 --> 00:18:08,930
právě teď.

424
00:18:08,930 --> 00:18:13,450
Máte-li strávit hodinu po
Příští týden ale naučit se používat GDB,

425
00:18:13,450 --> 00:18:16,140
ušetříte sami
tolik času později.

426
00:18:16,140 --> 00:18:18,750
A to doslova. řekneme
to lidí každý rok,

427
00:18:18,750 --> 00:18:23,890
a vzpomínám si, když jsem se
třídy, byl jsem rád, že budu v pořádku.

428
00:18:23,890 --> 00:18:24,700
Ne.

429
00:18:24,700 --> 00:18:27,030
Pset 6 přišla a já jsem byl
jako, já jsem chtěl učit

430
00:18:27,030 --> 00:18:29,500
jak používat GDB, protože se mi nelíbí
vědět, co se tady děje.

431
00:18:29,500 --> 00:18:32,940
>> Takže pokud budete mít tak čas
použít na menší programy

432
00:18:32,940 --> 00:18:35,697
že budete mít
pracuje, stejně jako pracovní

433
00:18:35,697 --> 00:18:37,530
přes něco jako
Visionare, jako je tento.

434
00:18:37,530 --> 00:18:38,800

435
00:18:38,800 --> 00:18:42,850
Nebo chcete-li další praxi, jsem si jistý,
Nemohl jsem přijít s buggy programy,

436
00:18:42,850 --> 00:18:45,300
pro vás ladit, pokud chcete.

437
00:18:45,300 --> 00:18:49,300
>> Ale pokud si jen vzít nějaký čas, aby si
na to zvyklí, jen hrát si s ním,

438
00:18:49,300 --> 00:18:50,550
to bude opravdu sloužit dobře.

439
00:18:50,550 --> 00:18:52,591
A je to opravdu jedna z
ty věci, které jste právě

440
00:18:52,591 --> 00:18:57,340
muset zkusit a dostat své špinavé ruce
se předtím, než se opravdu pochopit.

441
00:18:57,340 --> 00:19:02,090
Opravdu jen jednou pochopil
Musel jsem ladit věci s ním,

442
00:19:02,090 --> 00:19:08,170
a je to mnohem příjemnější mít představu o tom,
ladění spíše dříve než později.

443
00:19:08,170 --> 00:19:08,850
OK.

444
00:19:08,850 --> 00:19:09,625
V pohodě.

445
00:19:09,625 --> 00:19:12,960
Vím, že je to něco jako
rychlokurz v GDB,

446
00:19:12,960 --> 00:19:16,400
a já budu určitě pracovat na získání
Tyto vypadat větší příště.

447
00:19:16,400 --> 00:19:17,590

448
00:19:17,590 --> 00:19:18,280
V pohodě.

449
00:19:18,280 --> 00:19:20,390
>> Takže, pokud se vrátíme k naší aplikaci PowerPoint.

450
00:19:20,390 --> 00:19:27,194

451
00:19:27,194 --> 00:19:28,110
Je to bude fungovat?

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
AWH.

454
00:19:30,210 --> 00:19:31,101
Ano.

455
00:19:31,101 --> 00:19:31,600
OK.

456
00:19:31,600 --> 00:19:35,480
Takže, pokud jste někdy potřebovat některý z
ty zase, tam je seznam.

457
00:19:35,480 --> 00:19:37,160

458
00:19:37,160 --> 00:19:40,830
Tak binární vyhledávání, které každý
vzpomíná na skvělou podívanou Davida

459
00:19:40,830 --> 00:19:42,259
kopírování telefonních seznamů na polovinu.

460
00:19:42,259 --> 00:19:44,050
Nemám opravdu dostat
telefonní seznamy už,

461
00:19:44,050 --> 00:19:46,530
protože stejně jako kde se vám
si telefonní seznamy v těchto dnech?

462
00:19:46,530 --> 00:19:48,220
Já opravdu nevím.

463
00:19:48,220 --> 00:19:49,840

464
00:19:49,840 --> 00:19:50,590
Binární vyhledávání.

465
00:19:50,590 --> 00:19:52,464
Pamatuje si někdo,
Jak Binární hledání práce?

466
00:19:52,464 --> 00:19:54,380

467
00:19:54,380 --> 00:19:55,220
Vůbec někdo?

468
00:19:55,220 --> 00:19:56,325
Jo?

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Víte, kdy
se podíváte na nichž polovina

470
00:19:58,283 --> 00:20:01,146
to by bylo v, na tom základě,
a zbavit druhé poloviny.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Přesně tak.

472
00:20:01,896 --> 00:20:06,290
Takže, binární vyhledávání, je to docela je--
--we chtěl volat to rozděl a panuj.

473
00:20:06,290 --> 00:20:09,170
Takže, co budete dělat, je
budete vypadat ve středu,

474
00:20:09,170 --> 00:20:11,990
a uvidíte, zda to odpovídá
to, co hledáte.

475
00:20:11,990 --> 00:20:15,420
A pokud tomu tak není, zkuste se
zjistit, je, že bude ponechán

476
00:20:15,420 --> 00:20:16,450
polopenze nebo pravou polovinu.

477
00:20:16,450 --> 00:20:19,325
Takže by to mohlo být, pokud hledáte
na něco, co je podle abecedy,

478
00:20:19,325 --> 00:20:20,720
vidíš, oh.

479
00:20:20,720 --> 00:20:22,750
Má Allison přijít před M?

480
00:20:22,750 --> 00:20:23,250
Ano.

481
00:20:23,250 --> 00:20:25,030
Takže jdeme na
podívejte se na prvním pololetí.

482
00:20:25,030 --> 00:20:26,450
>> Nebo by to mohlo být jako s čísly.

483
00:20:26,450 --> 00:20:28,830
Cokoliv, co můžete
porovnání, to může být tříděny.

484
00:20:28,830 --> 00:20:29,920

485
00:20:29,920 --> 00:20:31,260
Můžete použít binární vyhledávání na.

486
00:20:31,260 --> 00:20:32,340

487
00:20:32,340 --> 00:20:37,455
Takže, někdo pamatovat
graf nebo co to je?

488
00:20:37,455 --> 00:20:39,520
Je to asymptotickou složitost.

489
00:20:39,520 --> 00:20:42,830
Takže, tento graf jen
popisuje, jak dlouho

490
00:20:42,830 --> 00:20:46,230
dostanete vyřešit problém, jak
zvýšíte počet věcí

491
00:20:46,230 --> 00:20:47,090
který používáte.

492
00:20:47,090 --> 00:20:51,260
>> Takže máme N, což je lineární čas.

493
00:20:51,260 --> 00:20:54,560
Pokud N více než dva, což je o něco
lepší, stále roste super rychlý.

494
00:20:54,560 --> 00:20:58,360
A pak jsme Přihlášení, který je
to, co považujeme za binární vyhledávání.

495
00:20:58,360 --> 00:21:03,630
Pokud si všimneme, jak váš problém
dostane mnohem a mnohem větší,

496
00:21:03,630 --> 00:21:06,600
Čas, který zabere vám to vyřešit
není opravdu zvyšuje, že hodně.

497
00:21:06,600 --> 00:21:09,010
Je to jako srovnatelné
tady na začátku.

498
00:21:09,010 --> 00:21:10,060
Jsi jako, OK.

499
00:21:10,060 --> 00:21:13,000
Něco tady není opravdu
ohledu na to, který z nich používáme,

500
00:21:13,000 --> 00:21:16,220
ale dostanete se k milionu, miliarda.

501
00:21:16,220 --> 00:21:20,010
Snažíte se najít some-- --you're
se snaží najít jehlu v kupce sena.

502
00:21:20,010 --> 00:21:21,550
>> Myslím si, že chcete tento problém.

503
00:21:21,550 --> 00:21:25,850
Chcete tuto složitost, ne
lineární, protože za všechno, co

504
00:21:25,850 --> 00:21:30,049
víte, že vaše bude se prohledávat
každý jednotlivec jehla, co sena,

505
00:21:30,049 --> 00:21:31,340
snaží hledat jehlu.

506
00:21:31,340 --> 00:21:34,730
A to není podle mého názoru příliš zábavné.

507
00:21:34,730 --> 00:21:35,500
Rychle, že jsem rád.

508
00:21:35,500 --> 00:21:36,620
Mám rád efektivní.

509
00:21:36,620 --> 00:21:40,450
A jak pracovití studenti vám přináší
kluci, víte pracovat chytřeji,

510
00:21:40,450 --> 00:21:43,010
ne těžší typ věc, jak se vám
může tvořit tyto algoritmy.

511
00:21:43,010 --> 00:21:45,110

512
00:21:45,110 --> 00:21:47,910
>> Takže, jdeme na procházku
přes jen rychlý příklad.

513
00:21:47,910 --> 00:21:51,090
Myslím si, že kluci by měli mít
ruku na binární vyhledávání,

514
00:21:51,090 --> 00:21:54,352
ale v případě, že někdo je trochu
rozmazaný, chcete ho posílit,

515
00:21:54,352 --> 00:21:56,310
budeme prostě jít
přes příklad.

516
00:21:56,310 --> 00:21:59,490
Takže, hledáme-li
pole obsahuje sedm.

517
00:21:59,490 --> 00:22:00,540

518
00:22:00,540 --> 00:22:06,010
>> Takže první věc, kterou děláme, je
hledat ve středu, ne?

519
00:22:06,010 --> 00:22:09,340
A také budete se kódování
Binary Search pár sekund.

520
00:22:09,340 --> 00:22:11,310
Takže, to bude legrace.

521
00:22:11,310 --> 00:22:13,710
Tak jsme se podívat do
střední malé pole 3.

522
00:22:13,710 --> 00:22:15,501
Má 3 se rovná 7?

523
00:22:15,501 --> 00:22:16,000
Není.

524
00:22:16,000 --> 00:22:18,670

525
00:22:18,670 --> 00:22:19,550
Je to šest.

526
00:22:19,550 --> 00:22:21,480
Takže, to je méně než
nebo větší než sedm?

527
00:22:21,480 --> 00:22:23,080

528
00:22:23,080 --> 00:22:23,960
Méně než.

529
00:22:23,960 --> 00:22:24,570
Ano.

530
00:22:24,570 --> 00:22:25,170
Dobrá práce kluci.

531
00:22:25,170 --> 00:22:25,569

532
00:22:25,569 --> 00:22:27,360
Mám pocit, že bych měl
mít sladkosti, protože jsem

533
00:22:27,360 --> 00:22:29,460
chtějí vyhodit do dvorů.

534
00:22:29,460 --> 00:22:30,270
To je to, co budu dělat příští týden.

535
00:22:30,270 --> 00:22:31,436
Bude vás kluci ostré.

536
00:22:31,436 --> 00:22:32,560

537
00:22:32,560 --> 00:22:34,690
>> Takže, vyhodíme, že
první polovina, je to tak?

538
00:22:34,690 --> 00:22:35,670
to bylo méně než.

539
00:22:35,670 --> 00:22:39,325
víme, že všechno,
na té levé straně

540
00:22:39,325 --> 00:22:41,700
bude menší než to, co
jsou vlastně hledáme.

541
00:22:41,700 --> 00:22:43,491
Takže, není třeba, aby
věnovat pozornost.

542
00:22:43,491 --> 00:22:45,120
Prostě na to zapomeň.

543
00:22:45,120 --> 00:22:48,720
Tak, teď se podíváme na naši pravé straně,
a my se ve středu tam,

544
00:22:48,720 --> 00:22:50,510
a teď je to devět.

545
00:22:50,510 --> 00:22:55,510
Takže, 9 je-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Větší, než to, co jsme
hledat, že jo?

547
00:22:57,470 --> 00:22:59,860
Takže jdeme hodit
pryč vše vpravo.

548
00:22:59,860 --> 00:23:00,970

549
00:23:00,970 --> 00:23:01,940
Takhle.

550
00:23:01,940 --> 00:23:03,700
Nyní vše, co jste odešel s jedním.

551
00:23:03,700 --> 00:23:07,760
Tak jsme se zjistit, je to jedno, co
hledáme? to je.

552
00:23:07,760 --> 00:23:08,970
Zjistili jsme, co jsme chtěli.

553
00:23:08,970 --> 00:23:10,440

554
00:23:10,440 --> 00:23:11,690
Takže jsme hotovi.

555
00:23:11,690 --> 00:23:12,550
Bilineární Search.

556
00:23:12,550 --> 00:23:15,740
>> A pokud si všimnete, my
měl tam sedm vstupů.

557
00:23:15,740 --> 00:23:24,320
To nám trvalo jen jako třikrát,
ale pokud děláte jako miliardy

558
00:23:24,320 --> 00:23:28,190
vy víte, kolik kroků to by
trvat, pokud jsme měli čtyři miliardy věci?

559
00:23:28,190 --> 00:23:29,940

560
00:23:29,940 --> 00:23:30,455
Jakékoli odhady?

561
00:23:30,455 --> 00:23:32,286

562
00:23:32,286 --> 00:23:33,960
Je to 32.

563
00:23:33,960 --> 00:23:37,110
32 kroků, jak najít něco,
ve čtyři miliardy

564
00:23:37,110 --> 00:23:39,650
prvek pole, protože síly dva.

565
00:23:39,650 --> 00:23:43,550
Takže dva je 32, je na čtyři miliardy korun.

566
00:23:43,550 --> 00:23:50,430
>> Tak dost šílené, jak jste stále v
jako poměrně malém počtu kroků

567
00:23:50,430 --> 00:23:52,650
najít něco, co v
čtyřmi miliardami prvky.

568
00:23:52,650 --> 00:23:55,730
Takže v takovém případě, že jsme
bude kód této

569
00:23:55,730 --> 00:23:58,950
tak vy můžete opravdu
druh vidět, jak to funguje.

570
00:23:58,950 --> 00:24:01,520
Dobře, takže vy můžete kódovat.

571
00:24:01,520 --> 00:24:04,100
Jdu si kluci nechat
mluvit trochu.

572
00:24:04,100 --> 00:24:07,970
Poznejte lidi kolem sebe, což je
to, co by někdo chtěl z poslední části.

573
00:24:07,970 --> 00:24:10,280
>> Takže poznat lidi kolem sebe.

574
00:24:10,280 --> 00:24:11,305
Mluvit trochu.

575
00:24:11,305 --> 00:24:12,580

576
00:24:12,580 --> 00:24:15,730
A všechno, co chci od vás
Kluci právě teď je jen

577
00:24:15,730 --> 00:24:17,575
pokusit se vytvořit nástin pseudokódu.

578
00:24:17,575 --> 00:24:18,075
OK?

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
Whoa.

581
00:24:21,325 --> 00:24:23,320

582
00:24:23,320 --> 00:24:29,520
Jediné, co chci od vás, je, že jste
jen tak pro vyplnění této chvíli případu.

583
00:24:29,520 --> 00:24:32,170
Tak jsem si stanovili tyto vyšší
a dolní meze, které

584
00:24:32,170 --> 00:24:35,250
představují začátek
a konec našeho pole.

585
00:24:35,250 --> 00:24:40,440
A budete skutečně
procházet a přijít na to,

586
00:24:40,440 --> 00:24:42,470
to, co děláme v rámci tohoto cyklu while.

587
00:24:42,470 --> 00:24:45,810
>> Takže pokud můžete přijít out-- mám
nápověda there-- jaké jsou případy,

588
00:24:45,810 --> 00:24:46,640
že tady máme?

589
00:24:46,640 --> 00:24:48,100

590
00:24:48,100 --> 00:24:51,560
Takže pokud chcete zjistit,
případy, budeme pseudokódu ty

591
00:24:51,560 --> 00:24:53,350
a pak budeme vlastně kód je.

592
00:24:53,350 --> 00:24:55,330
A to bude, jsem
si, doufejme, že to bude

593
00:24:55,330 --> 00:24:56,788
být o něco snazší, než jste očekávali.

594
00:24:56,788 --> 00:24:57,554

595
00:24:57,554 --> 00:25:00,220
Vzhledem k tomu, že to není tak moc kód,
ve skutečnosti, což je opravdu cool.

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> Mm-hm?

598
00:25:35,018 --> 00:25:35,893
>> STUDENT: [neslyšitelné]?

599
00:25:35,893 --> 00:25:36,984

600
00:25:36,984 --> 00:25:37,650
Instruktor: Ano.

601
00:25:37,650 --> 00:25:38,595
Tam bylo něco
najít ve středu.

602
00:25:38,595 --> 00:25:39,552
>> Žák: Takže můžeme použít.

603
00:25:39,552 --> 00:25:39,770
OK.

604
00:25:39,770 --> 00:25:40,603
>> Instruktor: Perfect.

605
00:25:40,603 --> 00:25:42,950
Tak to je první věc, kterou musíme udělat.

606
00:25:42,950 --> 00:25:44,330
Takže najít střed.

607
00:25:44,330 --> 00:25:45,415

608
00:25:45,415 --> 00:25:45,915
Skvělé.

609
00:25:45,915 --> 00:25:47,770

610
00:25:47,770 --> 00:25:55,010
Takže máte představu o tom, jak bychom mohli
skutečně najít střed s kódem?

611
00:25:55,010 --> 00:25:55,980
>> STUDENT: Jo.

612
00:25:55,980 --> 00:25:57,000
n nad 2?

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
Instruktor: Takže n nad 2.

615
00:25:59,500 --> 00:26:05,170
Takže jedna věc k zapamatování je, že
Vaše horní a dolní hranice měnit.

616
00:26:05,170 --> 00:26:08,110
Neustále škrtit část
matice se díváme na.

617
00:26:08,110 --> 00:26:11,970
Tak n nad 2 bude fungovat pouze
první věc, kterou děláme.

618
00:26:11,970 --> 00:26:17,810
Tak přičemž horní a dolní v úvahu,
jak bychom mohli dostat, že prostřední prvek?

619
00:26:17,810 --> 00:26:20,640
Protože chceme, aby střední
mezi horní a dolní, že jo?

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
Mm-hm?

622
00:26:22,494 --> 00:26:23,369
>> STUDENT: [neslyšitelné].

623
00:26:23,369 --> 00:26:26,170

624
00:26:26,170 --> 00:26:28,080
>> Instruktor: Takže máme nějaký střed.

625
00:26:28,080 --> 00:26:32,730
A to bude horní a dolní nad 2.

626
00:26:32,730 --> 00:26:34,740

627
00:26:34,740 --> 00:26:35,690
Úžasné.

628
00:26:35,690 --> 00:26:36,570
Tak jdeme.

629
00:26:36,570 --> 00:26:37,280
Jeden řádek dolů.

630
00:26:37,280 --> 00:26:38,560
Vy jste na vaší cestě.

631
00:26:38,560 --> 00:26:41,400
Takže teď, že máme
prostřední, co chceme dělat?

632
00:26:41,400 --> 00:26:45,050

633
00:26:45,050 --> 00:26:45,900
Jen obecně.

634
00:26:45,900 --> 00:26:47,734
Nemusíte to kód.

635
00:26:47,734 --> 00:26:48,335
Ano.

636
00:26:48,335 --> 00:26:49,210
STUDENT: [neslyšitelné]?

637
00:26:49,210 --> 00:27:00,310

638
00:27:00,310 --> 00:27:10,310
Instruktor: Takže je to navíc proto, že jste
nalezení průměr mezi dvěma

639
00:27:10,310 --> 00:27:10,810
z nich.

640
00:27:10,810 --> 00:27:11,890

641
00:27:11,890 --> 00:27:17,370
Takže pokud si myslíte, že z nich jako druh
zvýšení v ze stran,

642
00:27:17,370 --> 00:27:21,640
přemýšlet o tom, jak se budete blížit
střední, chcete takhle.

643
00:27:21,640 --> 00:27:27,150
Takže pokud jste byli na obou stranách
střední a máme jako 5 a 7.

644
00:27:27,150 --> 00:27:31,440
Když je sečteme vám
získat 12, rozdělit o 2, 6.

645
00:27:31,440 --> 00:27:33,726
>> Někdy je to těžké
vysvětlit, proč to funguje,

646
00:27:33,726 --> 00:27:35,600
ale pokud budete pracovat přes
Příklad někdy,

647
00:27:35,600 --> 00:27:37,962
to vám pomůže zjistit, zda
by mělo být plus nebo minus.

648
00:27:37,962 --> 00:27:38,846
Ano.

649
00:27:38,846 --> 00:27:40,830
>> STUDENT: [neslyšitelné]
přesně ve středu

650
00:27:40,830 --> 00:27:43,950
kdyby měli případ, kdy
je tu spousta menších čísel

651
00:27:43,950 --> 00:27:45,860
a jako jeden velký počet?

652
00:27:45,860 --> 00:27:49,750
>> Instruktor: Takže vše, co potřebujete
je uprostřed pole.

653
00:27:49,750 --> 00:27:53,010
Takže pokud jste měli spoustu malých čísel
a pak jeden opravdu velký počet

654
00:27:53,010 --> 00:27:54,799
Na konci, na tom nezáleží.

655
00:27:54,799 --> 00:27:56,840
Vše, na čem záleží, je, že
oni jsou řazeny, které jste právě

656
00:27:56,840 --> 00:27:59,339
Chcete se podívat na středu
pole, protože jste stále

657
00:27:59,339 --> 00:28:00,700
krájení váš problém na polovinu.

658
00:28:00,700 --> 00:28:03,020

659
00:28:03,020 --> 00:28:03,680
V pohodě.

660
00:28:03,680 --> 00:28:06,430
Takže teď, že máme
prostřední, co budeme dělat dál?

661
00:28:06,430 --> 00:28:07,150
>> STUDENT: Porovnejte.

662
00:28:07,150 --> 00:28:08,150
Instruktor: porovnat.

663
00:28:08,150 --> 00:28:11,670
Takže srovnávat střední až value_wanted.

664
00:28:11,670 --> 00:28:14,300

665
00:28:14,300 --> 00:28:15,160
V pohodě.

666
00:28:15,160 --> 00:28:17,950
Takže vidíte, tady máme
tato hodnota chceme tady.

667
00:28:17,950 --> 00:28:22,012

668
00:28:22,012 --> 00:28:23,095
Pamatujte, je to pole.

669
00:28:23,095 --> 00:28:24,100

670
00:28:24,100 --> 00:28:26,970
Takže střední odkazuje na indexu.

671
00:28:26,970 --> 00:28:29,785
Takže chceme dělat hodnot uprostřed.

672
00:28:29,785 --> 00:28:32,380

673
00:28:32,380 --> 00:28:35,650
Nezapomeňte, pokud chcete
porovnat, dvoulůžkové rovná.

674
00:28:35,650 --> 00:28:38,250
Děláte single rovná jste
jen tak ji přeřadit,

675
00:28:38,250 --> 00:28:41,090
a pak, samozřejmě, je to
Bude na hodnotu, kterou chcete.

676
00:28:41,090 --> 00:28:42,300
Takže nedělejte to.

677
00:28:42,300 --> 00:28:44,350
>> Takže jdeme zjistit, zda
hodnoty na střed

678
00:28:44,350 --> 00:28:46,460
je rovna hodnotě chceme.

679
00:28:46,460 --> 00:28:47,749

680
00:28:47,749 --> 00:28:48,790
Nezapomeňte na své rovnátka.

681
00:28:48,790 --> 00:28:50,520

682
00:28:50,520 --> 00:28:52,235
Dropbox měl jít pryč.

683
00:28:52,235 --> 00:28:54,140

684
00:28:54,140 --> 00:28:56,200
Tak co budeme dělat v tomto případě?

685
00:28:56,200 --> 00:28:59,360
Pokud je to, co chceme vrátit?

686
00:28:59,360 --> 00:29:01,510

687
00:29:01,510 --> 00:29:02,626
Snažíme se říct.

688
00:29:02,626 --> 00:29:03,440
>> STUDENT: Tisk off.

689
00:29:03,440 --> 00:29:05,314
>> Instruktor: No, my jsme
nechcete vytisknout.

690
00:29:05,314 --> 00:29:08,220
Tak to je bool tady, a tak jsme
chcete vrátit hodnotu true nebo false.

691
00:29:08,220 --> 00:29:12,280
Říkáme, je toto číslo
[? RRA? ?] Takže pokud je to,

692
00:29:12,280 --> 00:29:13,788
jen jsme se vrátit to pravda.

693
00:29:13,788 --> 00:29:16,780

694
00:29:16,780 --> 00:29:17,760
Když se mi podaří kouzlo pravda.

695
00:29:17,760 --> 00:29:18,830

696
00:29:18,830 --> 00:29:20,805
>> STUDENT: Proč by se tedy vrátíte nula?

697
00:29:20,805 --> 00:29:22,930
Instruktor: Takže byste mohli
vrátí nulu, pokud jste chtěli.

698
00:29:22,930 --> 00:29:26,780
Ale v tomto případě použitelné, protože
naše funkce vrací hodnotu typu bool,

699
00:29:26,780 --> 00:29:28,962
Musíme se vrátit buď true nebo false.

700
00:29:28,962 --> 00:29:30,920
STUDENT: Když jste
řka: boolean výrazu,

701
00:29:30,920 --> 00:29:33,450
Můžete je rovna false?

702
00:29:33,450 --> 00:29:39,860
Stejně jako když jsem chtěl říct, je-li tato podmínka
není splněna, jako je horní rovná false.

703
00:29:39,860 --> 00:29:42,332
Bude to, pokud jste právě pochopili
dát falešný na straně druhé?

704
00:29:42,332 --> 00:29:43,040
Instruktor: Jo.

705
00:29:43,040 --> 00:29:44,820
Takže ve skutečnosti, pokud jste
někdy něco

706
00:29:44,820 --> 00:29:49,600
jako je horní nebo je nižší,
která vrací true nebo false

707
00:29:49,600 --> 00:29:53,850
a je to vlastně špatné styl
řekněme rovná rovná pravda nebo rovno

708
00:29:53,850 --> 00:29:54,840
rovná false.

709
00:29:54,840 --> 00:30:00,210
Chcete-li použít tento výsledek
jak sám jako kontrola.

710
00:30:00,210 --> 00:30:04,720

711
00:30:04,720 --> 00:30:05,860
Ne to, co jsem chtěl.

712
00:30:05,860 --> 00:30:08,150

713
00:30:08,150 --> 00:30:09,240
To je to, co jsem chtěl.

714
00:30:09,240 --> 00:30:13,205
Takže v případě, že se ptáte
o něčem, jako je uložení této vc.

715
00:30:13,205 --> 00:30:16,320

716
00:30:16,320 --> 00:30:25,150
>> Takže pokud máme int main (void)
a něco takového.

717
00:30:25,150 --> 00:30:31,922
A máte-li je horní
nějakého vstupu a jste

718
00:30:31,922 --> 00:30:33,630
s dotazem, zda můžete dělat
něco takového?

719
00:30:33,630 --> 00:30:35,010

720
00:30:35,010 --> 00:30:35,679
Je to tak?

721
00:30:35,679 --> 00:30:37,470
STUDENT: Snažil jsem se
jak to udělat, [neslyšitelné].

722
00:30:37,470 --> 00:30:38,450
Protože pokud it's--

723
00:30:38,450 --> 00:30:39,200
Instruktor: Správně.

724
00:30:39,200 --> 00:30:41,197
Takže vy chcete to, že je falešný, ne?

725
00:30:41,197 --> 00:30:41,780
STUDENT: Jo.

726
00:30:41,780 --> 00:30:45,960
Instruktor: Takže v tomto případě,
Chcete to provést, pokud to není pravda.

727
00:30:45,960 --> 00:30:50,510
Takže v pohodě věc, kterou udělat, je to.

728
00:30:50,510 --> 00:30:52,900

729
00:30:52,900 --> 00:30:55,650
Takže pamatujte výkřik
bod popírá věci?

730
00:30:55,650 --> 00:30:58,270
To říká, že [neslyšitelné] znamená ne.

731
00:30:58,270 --> 00:31:03,590
Takže pokud se podíváme na právě
tato část zde, měli byste

732
00:31:03,590 --> 00:31:05,740
říkají, že je vyhodnocen
false, jak chcete, aby.

733
00:31:05,740 --> 00:31:06,790

734
00:31:06,790 --> 00:31:09,880
Ne falešný je pravda, která
znamená, že tento by se spustit.

735
00:31:09,880 --> 00:31:11,037
Dává to smysl?

736
00:31:11,037 --> 00:31:11,620
STUDENT: Jo.

737
00:31:11,620 --> 00:31:12,453
Instruktor: Úžasné.

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
OK.

740
00:31:14,300 --> 00:31:16,330
Takže jsme mohli jen vrátit
platí v tomto případě.

741
00:31:16,330 --> 00:31:20,357
Takže teď máme další dvě
případy, v tomto případě.

742
00:31:20,357 --> 00:31:21,565
Jaké jsou naše dva další případy?

743
00:31:21,565 --> 00:31:31,610

744
00:31:31,610 --> 00:31:32,900
Řekněme to udělat takhle.

745
00:31:32,900 --> 00:31:40,660
Takže začněme s jiný
pokud hodnoty na střed

746
00:31:40,660 --> 00:31:43,230
je menší než hodnota, kterou chceme.

747
00:31:43,230 --> 00:31:47,200

748
00:31:47,200 --> 00:31:52,020
Takže naše hodnoty ve středu, je méně
než hodnota, kterou hledáme pro.

749
00:31:52,020 --> 00:31:53,765

750
00:31:53,765 --> 00:31:56,720
>> Tak který vázaný vás dělat
, že chceme aktualizovat?

751
00:31:56,720 --> 00:31:57,870

752
00:31:57,870 --> 00:31:58,780
Horní nebo dolní?

753
00:31:58,780 --> 00:32:01,440

754
00:32:01,440 --> 00:32:01,940
Horní?

755
00:32:01,940 --> 00:32:03,230

756
00:32:03,230 --> 00:32:06,470
Takže, na které straně pole
se budeme dívat na?

757
00:32:06,470 --> 00:32:07,500
>> STUDENT: nižší.

758
00:32:07,500 --> 00:32:09,750
>> Instruktor: My jdeme
že se dívá na levé straně.

759
00:32:09,750 --> 00:32:11,120
Takže else if málo hodnota je menší.

760
00:32:11,120 --> 00:32:14,730
Tak tady vaší střední hodnotou
je méně než to, co chceme.

761
00:32:14,730 --> 00:32:17,202
A tak chceme, aby se
Pravá strana naší nabídku.

762
00:32:17,202 --> 00:32:18,910
Takže jdeme na
aktualizovat naše dolní mez.

763
00:32:18,910 --> 00:32:20,210

764
00:32:20,210 --> 00:32:23,020
Takže budeme přiřadit naše nižší.

765
00:32:23,020 --> 00:32:25,221
A co si myslíte, že by měla být nižší?

766
00:32:25,221 --> 00:32:26,304
STUDENT: střední hodnota?

767
00:32:26,304 --> 00:32:27,446

768
00:32:27,446 --> 00:32:28,820
Instruktor: Takže střední value--

769
00:32:28,820 --> 00:32:30,136
STUDENT: Plus 1.

770
00:32:30,136 --> 00:32:31,010
Instruktor: --plus 1.

771
00:32:31,010 --> 00:32:32,300

772
00:32:32,300 --> 00:32:34,380
Může mi někdo říct, proč
máme to plus 1?

773
00:32:34,380 --> 00:32:35,730
>> STUDENT: [? Žádná hodnota?]
je roven něj.

774
00:32:35,730 --> 00:32:36,120
>> Instruktor: Správně.

775
00:32:36,120 --> 00:32:38,661
Protože už víme, že
Naše střední hodnota není rovna

776
00:32:38,661 --> 00:32:42,750
to a chceme vyloučit
ze všech následných vyhledávání.

777
00:32:42,750 --> 00:32:46,360
Jestliže jste zapomněl, že plus 1, tato
bude líbit smyčky na dobu neurčitou.

778
00:32:46,360 --> 00:32:49,620
A budete jen být zachyceny
nekonečné smyčky, a pak budete segfault

779
00:32:49,620 --> 00:32:50,370
a věci jdou špatně.

780
00:32:50,370 --> 00:32:54,780
Takže vždy ujistěte, že nejste
včetně hodnoty, které jste právě

781
00:32:54,780 --> 00:32:55,380
Podíval se na.

782
00:32:55,380 --> 00:32:58,530
Tak jsme se o to postarat se znaménkem plus 1.

783
00:32:58,530 --> 00:33:04,840
>> Takže teď máme poslední podmínku
který jsem vždy z bezpečnostních důvodů

784
00:33:04,840 --> 00:33:12,664
si můžete prohlédnout zde, else if hodnota na
prostřední je větší než hodnota

785
00:33:12,664 --> 00:33:13,163
chceme.

786
00:33:13,163 --> 00:33:16,260

787
00:33:16,260 --> 00:33:20,230
To znamená, že chceme
levá polovina.

788
00:33:20,230 --> 00:33:21,350

789
00:33:21,350 --> 00:33:23,260
Takže, který z nich se budeme aktualizovat?

790
00:33:23,260 --> 00:33:23,760
Horní.

791
00:33:23,760 --> 00:33:25,470

792
00:33:25,470 --> 00:33:26,970
A co je tohle bude rovnat?

793
00:33:26,970 --> 00:33:31,630

794
00:33:31,630 --> 00:33:33,690
Střední minus 1, protože
Samozřejmě, chceme

795
00:33:33,690 --> 00:33:38,370
aby se ujistil, že nejsme
při pohledu na této střední hodnotě znovu.

796
00:33:38,370 --> 00:33:41,830

797
00:33:41,830 --> 00:33:45,110
A pak jsme si to.

798
00:33:45,110 --> 00:33:45,610
To je všechno.

799
00:33:45,610 --> 00:33:46,820
To je vše, binární vyhledávání.

800
00:33:46,820 --> 00:33:48,190
Není to tak špatné, ne?

801
00:33:48,190 --> 00:33:51,590
Je to jako 10 řádků
kód s mezerou.

802
00:33:51,590 --> 00:33:57,510
Tak velmi silný, velmi užitečné, budete
být použití v jedné ze svých pozdějších psets.

803
00:33:57,510 --> 00:33:59,360
Možná ne tenhle, ale později.

804
00:33:59,360 --> 00:34:00,670
Tak se to naučit.

805
00:34:00,670 --> 00:34:01,510
Milovat.

806
00:34:01,510 --> 00:34:02,980
To vám dobře léčit.

807
00:34:02,980 --> 00:34:05,370
Takže má někdo jakékoliv
Otázky týkající se binární hledání?

808
00:34:05,370 --> 00:34:06,196
Ano.

809
00:34:06,196 --> 00:34:09,840
>> STUDENT: Záleží na tom,
zda je váš n je sudé nebo liché?

810
00:34:09,840 --> 00:34:10,750
>> Instruktor: Ne

811
00:34:10,750 --> 00:34:18,150
Protože jsme obsadil ji do středu as
int, bude to jen zkrátit jej.

812
00:34:18,150 --> 00:34:21,600
Tak to zůstane celé číslo a to bude
nakonec roztřídit všechno.

813
00:34:21,600 --> 00:34:23,909
Takže nemusíte mít strach o tom.

814
00:34:23,909 --> 00:34:24,580
Každý dobrý?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Úžasné.

817
00:34:26,850 --> 00:34:27,919
V pohodě.

818
00:34:27,919 --> 00:34:30,836
Takže, vy jste dostali to.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Slideshow.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Tak, jak jsme mluvili o, já vím,
David zmínil složitost doby chodu.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Takže v nejlepším případě, je to jen
jeden, který nazýváme konstantní čas.

825
00:34:50,340 --> 00:34:51,909
Může mi někdo říct, proč by to mohlo být?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Jaký typ scénáře by to znamenalo?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> STUDENT: [neslyšitelné] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
Instruktor: Takže střední bytí
Prvním prvkem, který se dostáváme k, ne?

833
00:35:03,830 --> 00:35:08,167
Takže buď pole jedné nebo
co jsme hledali jen

834
00:35:08,167 --> 00:35:09,750
se stane, že plácnutí DAB ve středu.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Tak to je naše nejlepší případ.

837
00:35:13,380 --> 00:35:17,540
Se dostanete do skutečné problémy, pravděpodobně ne
bude dosáhnout [neslyšitelné], které se často.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Co o našem nejhorším případě?

840
00:35:19,750 --> 00:35:21,270
Náš nejhorší případ je log n.

841
00:35:21,270 --> 00:35:25,360
A že má co do činění s celým
pravomoci dvě věci, které jsem hovořil.

842
00:35:25,360 --> 00:35:30,930
>> Takže v nejhorším případě by to znamenalo
že jsme museli sekat pole dolů

843
00:35:30,930 --> 00:35:33,270
dokud nebylo součástí jedné.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Takže jsme museli rozsekat ho na polovinu
tolikrát, kolikrát, jak jsme jen mohli.

846
00:35:38,930 --> 00:35:41,430
To je důvod, proč je to log n, protože
stačí držet dělení dvěma.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Takže předpoklady, věci, které
Potřebuju vědět, jestli jste někdy

849
00:35:45,830 --> 00:35:48,050
bude používat binární vyhledávání.

850
00:35:48,050 --> 00:35:50,680
Vaše prvky musí být řazeny.

851
00:35:50,680 --> 00:35:53,890
Musí být tříděny, protože
že je to jediný způsob, jak

852
00:35:53,890 --> 00:35:57,060
můžete vědět, jestli jste schopni
vyhodit polovinu.

853
00:35:57,060 --> 00:36:00,260
>> Pokud jste měli tuto neuspořádané pytel
čísel a vy říkáte,

854
00:36:00,260 --> 00:36:05,380
OK, jdu zkontrolovat střed
číslo a číslo Sháním

855
00:36:05,380 --> 00:36:08,510
je méně než to, že jsem prostě jít
libovolně vyhodit jednu polovinu.

856
00:36:08,510 --> 00:36:11,130
Ty by, ne-li vědět vaše
Čísla v tomto druhém pololetí.

857
00:36:11,130 --> 00:36:12,655
Váš seznam musí být vyřešeno.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Stejně tak to může být
pokračuje trochu,

860
00:36:16,560 --> 00:36:18,360
ale musíte mít náhodný přístup.

861
00:36:18,360 --> 00:36:21,940
Musíte být schopni jen
jít do té prostřední prvek.

862
00:36:21,940 --> 00:36:25,110
Máte-li procházet
něčím

863
00:36:25,110 --> 00:36:28,630
nebo to trvá vám další kroky
abych se dostal do středního prvku,

864
00:36:28,630 --> 00:36:31,750
to se přihlásit n už proto,
přidáváte více práce do něj.

865
00:36:31,750 --> 00:36:34,800
A to bude trochu
větší smysl za dva týdny,

866
00:36:34,800 --> 00:36:37,950
ale já jsem tak nějak chtěl začínat,
dát Vy představu o tom, co je

867
00:36:37,950 --> 00:36:38,999
přijít.

868
00:36:38,999 --> 00:36:40,790
Ale to jsou dva
důležité předpoklady

869
00:36:40,790 --> 00:36:44,804
které budete potřebovat pro binární seznamu.

870
00:36:44,804 --> 00:36:45,720
Ujistěte se, že je to třídit.

871
00:36:45,720 --> 00:36:47,920
To je ten velký pro
vy právě teď.

872
00:36:47,920 --> 00:36:52,170
A na to můžeme jít do
zbytek našich druhů.

873
00:36:52,170 --> 00:36:56,444
Takže čtyři sorts-- bublina,
vložení, výběr a korespondence.

874
00:36:56,444 --> 00:36:57,485
Jsou to všechno docela fajn.

875
00:36:57,485 --> 00:37:02,860
Jestliže vy rozhodnete pro CS 124,
Dozvíte se o všech možných druhů.

876
00:37:02,860 --> 00:37:07,575
A pokud jste fanoušek xkcd zde
Je to opravdu v pohodě komiks o

877
00:37:07,575 --> 00:37:11,530
jako velmi neefektivní druhů, které jsem
Velmi doporučuji vám jít podívat.

878
00:37:11,530 --> 00:37:16,170
Jedním z nich je jako panické druhu, který
je rád, oh ne, vrátí náhodné pole.

879
00:37:16,170 --> 00:37:16,991
Vypnutí systému.

880
00:37:16,991 --> 00:37:17,490
Odejít.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Takže geeky humor je vždy dobré.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Takže má někdo pamatovat druh
jako se jen obecnou představu

885
00:37:25,750 --> 00:37:27,810
o tom, jak bublina trochu funguje.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Pamatuješ?

888
00:37:32,155 --> 00:37:32,755
>> STUDENT: Jo.

889
00:37:32,755 --> 00:37:33,970
>> Instruktor: Jdi do toho.

890
00:37:33,970 --> 00:37:38,980
>> Žák: Takže jdeš skrz
pokud je větší, pak vyměnit dva.

891
00:37:38,980 --> 00:37:39,820
>> Instruktor: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Přesně tak.

893
00:37:40,564 --> 00:37:41,730
Takže stačí iterovat.

894
00:37:41,730 --> 00:37:43,050
Můžete zkontrolovat dvě čísla.

895
00:37:43,050 --> 00:37:46,510
Jestliže před jeden je větší
než je poté,

896
00:37:46,510 --> 00:37:50,230
stačí vyměnit je tak, aby v
Tímto způsobem všechny vyšších čísel

897
00:37:50,230 --> 00:37:54,990
bublina až ke konci seznamu
a všechny nižší počty bublina dolů.

898
00:37:54,990 --> 00:37:59,355
>> Řekl vám ukázat kluci v pohodě
zvukový efekt třídění video?

899
00:37:59,355 --> 00:38:00,480
Je to docela v pohodě.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Tak jen řekl Robert, algoritmus
který jste právě krok v seznamu,

902
00:38:05,200 --> 00:38:07,930
vymění sousední hodnoty
v případě, že nejste v pořádku.

903
00:38:07,930 --> 00:38:10,975
A pak už jen stále opakovat
dokud nemáte žádné swapy.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Takže to není špatné, ne?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Tak jsme si dát rychlý příklad zde.

908
00:38:16,319 --> 00:38:18,360
Takže to bude třídit
je ve vzestupném pořadí.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Takže když jsme se projít první
Tentokrát jsme se podívat přes osm

911
00:38:23,470 --> 00:38:26,880
a šest očividně nejsou
v pořadí, jsme je vyměnit.

912
00:38:26,880 --> 00:38:27,985
>> Tak se podívejte na ten příští.

913
00:38:27,985 --> 00:38:29,430
Osm a čtyři není v pořádku.

914
00:38:29,430 --> 00:38:30,450
Vyměňte je.

915
00:38:30,450 --> 00:38:32,530
A pak osm a dvě, vyměňte je.

916
00:38:32,530 --> 00:38:33,470
Tak jdeme.

917
00:38:33,470 --> 00:38:39,519
Takže po prvním průchodu,
víte, že váš největší počet

918
00:38:39,519 --> 00:38:41,810
bude po celou cestu
na vrcholu, protože je to jen

919
00:38:41,810 --> 00:38:44,210
bude neustále
větší než všechno ostatní

920
00:38:44,210 --> 00:38:46,810
a to jen tak, aby bubliny
se celou cestu až tam do konce.

921
00:38:46,810 --> 00:38:48,226
Má to smysl pro každého?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
V pohodě.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Takže se podíváme na naši druhém průchodu.

926
00:38:53,920 --> 00:38:54,980
Šest a čtyři, switch.

927
00:38:54,980 --> 00:38:55,920
Šest a dvě, switch.

928
00:38:55,920 --> 00:38:58,700
A teď tu máme pár věcí do pořádku.

929
00:38:58,700 --> 00:39:02,240
Takže pro každý průchod, které jsme
aby po celou dobu našeho seznamu,

930
00:39:02,240 --> 00:39:06,320
Víme, že stejně jako, že mnoho čísel
na konci bude muset být seřazeny.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Takže děláme třetí přihrávku,
který je jedním swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
A pak se na náš čtvrtý
projít, máme nulové štěrbiny.

935
00:39:15,910 --> 00:39:18,570
A tak víme, že naše
pole bylo řazeny.

936
00:39:18,570 --> 00:39:20,900
>> A to je velký
věc bublinkové druhu.

937
00:39:20,900 --> 00:39:23,720
Víme, že když jsme
mají nulovou swapy, které

938
00:39:23,720 --> 00:39:26,497
znamená, že vše, co
je zcela pořadí.

939
00:39:26,497 --> 00:39:27,580
Je to trochu jak zkontrolovat.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Tak jsme se také bude kód bublinu
druh, který také není tak špatné.

942
00:39:36,480 --> 00:39:38,120
Žádný z nich není tak špatné.

943
00:39:38,120 --> 00:39:40,210
Vím, že se může zdát trochu děsivé.

944
00:39:40,210 --> 00:39:42,124
Vím, že když jsem se
třída, i když jsem

945
00:39:42,124 --> 00:39:44,290
učil třídu pro
poprvé v loňském roce,

946
00:39:44,290 --> 00:39:46,165
Byl jsem rád, jak to mám udělat?

947
00:39:46,165 --> 00:39:48,540
To dává smysl v teorii, ale
jak to vlastně udělat?

948
00:39:48,540 --> 00:39:51,420
Což je důvod, proč i já chci jít
prostřednictvím kódu s vámi zde.

949
00:39:51,420 --> 00:39:54,915
Takže mám pseudokódu
pro vás tentokrát.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Takže stačí mít na paměti, jak
chystáme se přejít přes.

952
00:39:58,970 --> 00:40:04,210
Takže máme nějaké počítadlo, které
udržuje naše swapů,

953
00:40:04,210 --> 00:40:08,370
protože musíme ujistit,
že jsme ověřit, že.

954
00:40:08,370 --> 00:40:11,830
A my opakovat celou řadu
jak jsme právě udělal s tímto příkladem.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Je-li prvek předtím, než je větší než
prvek později, kde jsme v,

957
00:40:17,325 --> 00:40:20,760
jsme vyměnit je a my zvýšit dotazy
counter protože jakmile jsme se vyměnit,

958
00:40:20,760 --> 00:40:23,850
Chceme, aby naše counter vědět.

959
00:40:23,850 --> 00:40:26,247
Nějaké otázky?

960
00:40:26,247 --> 00:40:27,580
Něco se zdá legrační sem.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
STUDENT: Myslíte si nastavit počítadlo na nulu
pokaždé, když jdete přes smyčku?

963
00:40:32,350 --> 00:40:34,339
Nezdá se vám jít dál
zpět na nulu pokaždé?

964
00:40:34,339 --> 00:40:35,505
Instruktor: Ne nutně.

965
00:40:35,505 --> 00:40:39,710
Takže co se stane, je, že jsme projít zde.

966
00:40:39,710 --> 00:40:43,830
Tak dělat, když, pamatujte, že tato
bude provádět jednou bez výjimky.

967
00:40:43,830 --> 00:40:46,480
Takže to bude nastavení
čítač roven nule,

968
00:40:46,480 --> 00:40:48,070
pak to bude iterovat.

969
00:40:48,070 --> 00:40:50,590
Jak to projde,
to bude aktualizovat počítadlo.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Jak se aktualizuje čítač, když se to dělá,
když to dosáhne konce pole,

972
00:40:56,900 --> 00:41:00,830
pokud náš seznam není tříděny,
čítače byly aktualizovány.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Tak se kontroluje stav a to
říká: OK, je čítač větší než nula.

975
00:41:07,150 --> 00:41:09,290
Pokud je, udělat to znovu.

976
00:41:09,290 --> 00:41:14,340
Chcete-li obnovit tak, že když vás
projít, čítač je rovna nule.

977
00:41:14,340 --> 00:41:18,240
Pokud půjdete přes tříděných
pole, nic se nezmění,

978
00:41:18,240 --> 00:41:21,355
tento postup selže, a
vrátit seřazený seznam.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Má to smysl?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
STUDENT: Mohlo by se trochu.

983
00:41:26,356 --> 00:41:27,147
Instruktor: OK.

984
00:41:27,147 --> 00:41:28,980
Pokud existuje jakákoli jiná
otázka, která přijde.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Ano.

987
00:41:30,680 --> 00:41:33,760
>> STUDENT: Co by funkce
být pro přečerpání prvky?

988
00:41:33,760 --> 00:41:36,900
>> Instruktor: Takže vlastně můžeme napsat
že pokud budeme právě teď.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
V pohodě.

991
00:41:38,300 --> 00:41:42,155
Takže v takovém případě, Alison se děje
přepnout zpět do přístroje.

992
00:41:42,155 --> 00:41:43,080
To bude legrace.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
A máme pěkný
bubble sort, co tady.

995
00:41:47,390 --> 00:41:50,800
Tak jsem to již udělal na kole
přes pole.

996
00:41:50,800 --> 00:41:53,030
Máme swapy, které
jsou rovny nule.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Takže chceme vyměnit přilehlé
prvky, pokud jsou mimo provoz.

999
00:41:58,440 --> 00:42:03,020
Takže první věc, kterou musíme
to je iterovat naší nabídku.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Tak jak si myslíte, že bychom mohli
iterovat naší nabídku?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Máme pro a i = 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Chceme být i nižší
než n mínus 1 mínus k.

1006
00:42:22,454 --> 00:42:23,870
A já budu vysvětlovat, že ve vteřině.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Tak tohle je optimalizace tady, kde
Vzpomínám si, jak jsem řekl, po každém průchodu

1009
00:42:32,830 --> 00:42:36,655
přes pole my
vím, že to, co je on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Takže po jednom průchodu jsme
vím, že to je řazen.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Po dvou průchodech víme,
že to vše je seřazen.

1014
00:42:50,060 --> 00:42:52,750
Po třech průchodech jsme
vím, že je třídit.

1015
00:42:52,750 --> 00:42:55,620
Tak, jak jsem iterace
přes pole zde

1016
00:42:55,620 --> 00:43:01,090
Je to ujistěte se, jít jen
prostřednictvím toho, co víme, je netříděný.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
To je jen optimalizace.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Dalo by se napsat naivně jen
iterace přes všechno,

1021
00:43:08,210 --> 00:43:09,970
by to prostě trvat déle.

1022
00:43:09,970 --> 00:43:12,470
S tímto čtyři smyčky je
jen pěkný optimalizace

1023
00:43:12,470 --> 00:43:18,460
protože víme, že po každé plné
iteraci přes pole zde,

1024
00:43:18,460 --> 00:43:24,050
jako každou celou smyčku tady víme,
že jeden z těchto prvků

1025
00:43:24,050 --> 00:43:25,760
budou rozděleny na konci.

1026
00:43:25,760 --> 00:43:28,294
>> Tak jsme se nemuseli starat o ty.

1027
00:43:28,294 --> 00:43:29,710
Má to smysl pro každého?

1028
00:43:29,710 --> 00:43:30,950
Že v pohodě malý trik?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Takže v tomto případě, pokud
jsme iterace,

1031
00:43:37,270 --> 00:43:50,590
víme, že chceme zjistit, zda
pole n a n + 1 jsou v pořádku.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Tak tady je pseudokódu.

1035
00:43:54,600 --> 00:43:57,540
Chceme zjistit, zda pole n
a n a 1 jsou v pořádku.

1036
00:43:57,540 --> 00:43:59,520
Takže to, co můžeme mít, že?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Bude to mít nějaký podmíněné.

1039
00:44:03,120 --> 00:44:04,220
Bude-li.

1040
00:44:04,220 --> 00:44:07,066
>> STUDENT: Je-li pole n je
méně než pole n plus 1.

1041
00:44:07,066 --> 00:44:07,816
Instruktor: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
No, menší nebo větší než.

1044
00:44:10,699 --> 00:44:11,615
STUDENT: Větší než.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Pak je chceme vyměnit.

1047
00:44:17,620 --> 00:44:18,570
Přesně tak.

1048
00:44:18,570 --> 00:44:23,570
Takže teď jsme se dostali do toho, co je
Mechanismus je vyměňovat?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Tak jsme šli přes tuto krátkou dobu,
typ funkce odkládacího minulý týden.

1051
00:44:28,137 --> 00:44:29,595
Pamatuje si někdo, jak to funguje?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Takže můžeme nejen přiřadit jim, že jo?

1054
00:44:34,950 --> 00:44:36,640
Vzhledem k tomu, jeden z nich se ztratí.

1055
00:44:36,640 --> 00:44:41,696
Jestliže jsme řekli, se rovná B a B
je rovna A, všechny náhle oba

1056
00:44:41,696 --> 00:44:43,150
jsou jen rovná B.

1057
00:44:43,150 --> 00:44:45,720
>> Takže to, co musíme udělat, je, že jsme
mají dočasné proměnné, které je

1058
00:44:45,720 --> 00:44:49,055
bude držet jeden z našich chvíli
jsme v procesu vyměňovat.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Takže to, co máme, je, že budeme muset nějakou int
teplota je rovna to-- můžete přiřadit

1061
00:44:56,464 --> 00:44:59,130
se podle toho, co potřebujete, stačí
ujistěte se, že budete mít přehled o to--

1062
00:44:59,130 --> 00:45:01,840
takže v tomto případě budu
přiřadit k poli n plus 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Tak, že to bude držet bez ohledu na
hodnota je v tomto druhém bloku

1065
00:45:07,674 --> 00:45:08,590
že se díváme.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> A potom, co můžeme udělat je, že může jít
dopředu a Přeřadit pole n + 1,

1068
00:45:13,240 --> 00:45:14,990
protože my víme,
mají tuto hodnotu uloženou.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
To je také jeden z velkých
things-- nemám, pokud někdo z vás vědět,

1071
00:45:19,270 --> 00:45:23,780
měl problémy, kde když přepnete dva
řádků kódu náhle věci fungují.

1072
00:45:23,780 --> 00:45:25,880
Objednávka je velmi důležité v CS.

1073
00:45:25,880 --> 00:45:29,450
Takže se ujistěte, diagram
věci, pokud je to možné

1074
00:45:29,450 --> 00:45:31,230
pokud jde o to, co se skutečně děje.

1075
00:45:31,230 --> 00:45:34,256
Takže teď budeme
přiřazení pole n + 1,

1076
00:45:34,256 --> 00:45:36,005
protože my víme,
mají tuto hodnotu uloženou.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> A můžeme přiřadit, že na poli
n, nebo v tomto případě i pole.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Příliš mnoho proměnných.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Takže teď jsme převelen pole I
plus 1 se rovná, co je v poli i.

1084
00:46:01,500 --> 00:46:08,240
A teď se můžeme vrátit a
přiřadit pole jsem se, co?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Každý, kdo?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> STUDENT: 10.

1089
00:46:14,010 --> 00:46:14,680
>> Instruktor: 10.

1090
00:46:14,680 --> 00:46:15,180
Přesně tak.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
A ještě jedna poslední věc.

1093
00:46:18,640 --> 00:46:21,840
Pokud jsme vyměnili hned,
Co musíme udělat?

1094
00:46:21,840 --> 00:46:23,740
Co je jedna věc,
, co se děje, aby nám řekli

1095
00:46:23,740 --> 00:46:27,542
jestli se někdy ukončit tento program?

1096
00:46:27,542 --> 00:46:29,250
Co nám říká, že
mají seřazený seznam?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Pokud nebudeme provádět žádné swapy, že jo?

1099
00:46:33,750 --> 00:46:36,900
Pokud swapů se rovná
nulu na konci tohoto.

1100
00:46:36,900 --> 00:46:42,975
Takže kdykoliv provést výměnu, jako my
právě tady udělal, chceme aktualizovat swapy.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
A vím, že tam byl
Otázka dříve o můžete

1103
00:46:47,210 --> 00:46:49,689
použít nula nebo jedna, místo
true nebo false.

1104
00:46:49,689 --> 00:46:50,980
A to je to, co to dělá tady.

1105
00:46:50,980 --> 00:46:52,750
Tak to říká, ne-li swapy.

1106
00:46:52,750 --> 00:47:01,310
Takže pokud swapů je nula, což je-- vždycky
dostat mé pravdy a mé falses popletl.

1107
00:47:01,310 --> 00:47:03,960
Chceme, abychom mohli zhodnotit
na hodnotu true, a to není.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Takže pokud je to nula, pak je to falešné.

1110
00:47:09,630 --> 00:47:12,560
Pokud to popírají s
[? bang?] se stává pravdou.

1111
00:47:12,560 --> 00:47:13,975
Takže tento řádek spustí.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Pravdy a falešné a
nul a jedniček si blázen.

1114
00:47:17,370 --> 00:47:20,690
Jen pokud jste pomalu chodit
přes to, že bude mít smysl.

1115
00:47:20,690 --> 00:47:23,320
Ale to je to, co tento malý
bit kódu tady dělá.

1116
00:47:23,320 --> 00:47:26,490
Takže to zkontroluje,
jsme udělali nějaké swapy.

1117
00:47:26,490 --> 00:47:30,054
Takže pokud je to něco navíc
nula, bude to, že je falešný

1118
00:47:30,054 --> 00:47:31,970
a celá věc je
bude znovu spustit.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
V pohodě?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> Student: Co je přestávka dělat?

1123
00:47:36,000 --> 00:47:38,990
>> Instruktor: Přestávka jen
vypukne vás ze smyčky.

1124
00:47:38,990 --> 00:47:41,570
Takže v tomto případě by
stejně jako ukončení programu

1125
00:47:41,570 --> 00:47:43,828
a ty by jen
mít svůj seřazený seznam.

1126
00:47:43,828 --> 00:47:44,536
STUDENT: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
Instruktor: Omlouvám se?

1129
00:47:49,010 --> 00:47:52,110
STUDENT: Protože předtím jsme
použité písemné 1 přepsány nulu

1130
00:47:52,110 --> 00:47:54,170
představit, že v případě,
že bude fungovat, nebo ne.

1131
00:47:54,170 --> 00:47:54,878
>> Instruktor: Jo.

1132
00:47:54,878 --> 00:47:56,410
Takže se můžete vrátit nula nebo jedna.

1133
00:47:56,410 --> 00:47:58,950
V tomto případě, protože nejsme ve skutečnosti
dělat něco s funkcí,

1134
00:47:58,950 --> 00:48:00,150
chceme jen to zlomit.

1135
00:48:00,150 --> 00:48:02,680
Jsme opravdu nestarám o to.

1136
00:48:02,680 --> 00:48:06,960
Brzda je také dobré, pokud
je použita pro propukají

1137
00:48:06,960 --> 00:48:10,710
ze čtyř smyček nebo podmínek, které
Nechcete, aby provádění.

1138
00:48:10,710 --> 00:48:12,110
Stačí jen ti z nich.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Je to trochu nuance věc.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Mám pocit, že je tu
hodně ruční ondulaci,

1143
00:48:18,445 --> 00:48:19,740
stejně jako se dozvíte o tom brzy.

1144
00:48:19,740 --> 00:48:20,955
>> Ale vy se dozvíte o tom brzy.

1145
00:48:20,955 --> 00:48:21,500
Slibuji.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Takže se všichni dostat Bublinkové řazení?

1149
00:48:24,840 --> 00:48:25,550
Není to tak zlé.

1150
00:48:25,550 --> 00:48:31,910
Iterovat, výměnné věci pomocí
temp variabilní, a všichni tam nastavit?

1151
00:48:31,910 --> 00:48:32,960
V pohodě.

1152
00:48:32,960 --> 00:48:34,080
Úžasné.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Zpět na PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Jakékoliv otázky obecně
o nich tak daleko?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
V pohodě.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> STUDENT: [neslyšitelné] int main obvykle.

1162
00:48:45,279 --> 00:48:46,695
Máte mít to za to?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> Instruktor: Tak jsme byli jen hledáte
jen na skutečný třídění algoritmu.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Pokud jste ji měl v rámci
jako většího programu,

1167
00:48:56,350 --> 00:48:57,891
budete mít int main někde.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
V závislosti na tom, kde jste
použití tohoto algoritmu,

1170
00:49:02,880 --> 00:49:05,860
by to zjistit, co je
vracené to.

1171
00:49:05,860 --> 00:49:09,960
Ale pro náš případ, my jsme striktně
při pohledu na to, jak to dělá ve skutečnosti

1172
00:49:09,960 --> 00:49:11,300
iterovat pole.

1173
00:49:11,300 --> 00:49:12,570
Tak jsme se nemusíte starat o to.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Tak jsme mluvili o nejlepším případě a
nejhorších scénářů pro binární vyhledávání.

1176
00:49:19,830 --> 00:49:22,470
Tak to je také důležité, aby se
že pro každý z našich druhů.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Takže to, co si myslíte, že je to nejhorší,
Případ runtime bublinkové druhu?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Vy pamatujete?

1181
00:49:30,700 --> 00:49:31,784
>> STUDENT: N minus 1.

1182
00:49:31,784 --> 00:49:32,700
Instruktor: N minus 1.

1183
00:49:32,700 --> 00:49:35,070
Takže to znamená, že existují
n minus 1 srovnání.

1184
00:49:35,070 --> 00:49:40,060
Takže jedna věc je uvědomit si,
že na první iteraci,

1185
00:49:40,060 --> 00:49:43,360
projdeme, budeme porovnávat
Tyto two-- tak to je 1.

1186
00:49:43,360 --> 00:49:46,685
Tyto dva, tři, čtyři.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Takže po jednom průchodu jsme
již čtyři srovnání.

1189
00:49:55,050 --> 00:49:58,230
Když mluvím o běhu a n.

1190
00:49:58,230 --> 00:50:04,680
N představuje počet porovnání
v závislosti na tom, jak mnoho prvků

1191
00:50:04,680 --> 00:50:05,570
máme.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Tak jsme se projít, máme čtyři.

1194
00:50:08,860 --> 00:50:11,780
Až se příště budete vědět, že ne
musí se postarat o to.

1195
00:50:11,780 --> 00:50:15,140
Porovnáme tyto dva,
tyto dvě, tyto dva,

1196
00:50:15,140 --> 00:50:20,050
a když jsme neměli, že optimalizace
se čtyřmi smyčky, které jsem napsal,

1197
00:50:20,050 --> 00:50:22,750
byste se porovnání zde tak jako tak.

1198
00:50:22,750 --> 00:50:26,170
Takže budete muset
projít pole

1199
00:50:26,170 --> 00:50:34,380
a aby n n srovnání
časy, protože pokaždé, když

1200
00:50:34,380 --> 00:50:36,670
běh přes to třídíme jednu věc.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> A pokaždé, když jsme se projít
pole, děláme n srovnání.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Takže naše runtime je to
ve skutečnosti n na druhou, což

1205
00:50:46,330 --> 00:50:48,400
je mnohem horší v naší
Přihlášení konec, protože to

1206
00:50:48,400 --> 00:50:51,965
znamená, že pokud jsme měli čtyři
miliardy prvky, je to

1207
00:50:51,965 --> 00:50:55,260
bude nám trvat čtyři miliardy
čtvercový místo 32.

1208
00:50:55,260 --> 00:51:01,240
Takže není nejlepší runtime,
ale některé věci,

1209
00:51:01,240 --> 00:51:04,610
víte, pokud jste v
určitý sortiment prvků

1210
00:51:04,610 --> 00:51:06,540
bublina druh může být v pohodě použít.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Takže teď to, co je v nejlepším případě runtime?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
STUDENT: Zero?

1215
00:51:14,940 --> 00:51:16,420
Nebo 1?

1216
00:51:16,420 --> 00:51:18,140
>> Instruktor: Takže 1 by
být jeden srovnání.

1217
00:51:18,140 --> 00:51:19,114
Přesně tak.

1218
00:51:19,114 --> 00:51:20,002
>> STUDENT: N minus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> Instruktor: Tak jo.

1221
00:51:22,320 --> 00:51:22,990
Tak n minus 1.

1222
00:51:22,990 --> 00:51:26,510
Kdykoli budete mít představu, jako n
minus 1, máme tendenci nech ho

1223
00:51:26,510 --> 00:51:31,680
a my jsme jen říct, n, protože máte
porovnat každý z these-- každého páru.

1224
00:51:31,680 --> 00:51:36,470
Bylo by tedy n minus 1, které
jsme právě řekl je přibližně n.

1225
00:51:36,470 --> 00:51:39,280
Když máte co do činění s běhu,
vše je v sbližuje.

1226
00:51:39,280 --> 00:51:43,860
Tak dlouho, jak je exponent
správné, že jste docela dobrý.

1227
00:51:43,860 --> 00:51:45,700
>> To je to, jak se s tím vypořádat.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Tak, že nejlepším případě je n, který
znamená, že seznam je již řazeno,

1230
00:51:51,780 --> 00:51:54,320
a vše, co udělat, je spustit pomocí
a zkontrolujte, zda je to třídit.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
V pohodě.

1233
00:51:56,855 --> 00:51:57,355
Dobrá.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Takže jak vidíte zde, abychom
jen nějaké další grafy.

1236
00:52:01,920 --> 00:52:02,660
Tak n na druhou.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Fun.

1239
00:52:05,120 --> 00:52:09,730
Mnohem horší než n, jak vidíme, a
mnohem, mnohem horší, než log 2n.

1240
00:52:09,730 --> 00:52:12,060
A pak se můžete také dostat do protokolů protokolu.

1241
00:52:12,060 --> 00:52:18,020
A budete mít 124, se dostanete do
jako log Star, kterého se jako blázen.

1242
00:52:18,020 --> 00:52:20,172
Takže pokud máte zájem,
vyhledávání log hvězda.

1243
00:52:20,172 --> 00:52:20,880
Je to docela legrace.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Takže máme tento skvělý graf.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Jen heads up, to
nádherný graf mít

1248
00:52:28,720 --> 00:52:31,350
pro střednědobé, protože jsme
dlouho se vás zeptat na tyto tenčí.

1249
00:52:31,350 --> 00:52:36,090
Takže jen heads up, mít to na vašem
v polovině období na svém pěkném tahák

1250
00:52:36,090 --> 00:52:36,616
zde.

1251
00:52:36,616 --> 00:52:37,990
Tak jsme se jen podíval na bubliny druhu.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
V nejhorším případě, n na druhou, nejlepší věc, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
A budeme se podívat na ostatní.

1256
00:52:44,950 --> 00:52:47,940
>> A jak můžete vidět, pouze
ten, který opravdu dělá dobře

1257
00:52:47,940 --> 00:52:50,910
je merge sort, který budeme mít na to, proč.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Takže jsme jít do
příští here-- výběr sort.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Pamatuje si někdo, jak
Výběr sort pracoval?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Jít na to.

1264
00:53:05,700 --> 00:53:08,210
>> STUDENT: V podstatě projít
pořadí a vytvořit nový seznam.

1265
00:53:08,210 --> 00:53:11,001
A stejně jako vy uvedení prvky
in, dal je na správném místě

1266
00:53:11,001 --> 00:53:11,750
v novém seznamu.

1267
00:53:11,750 --> 00:53:14,040
>> Instruktor: Takže zvuky
spíš vkládání druhu.

1268
00:53:14,040 --> 00:53:15,040
Ale ty jsi opravdu blízko.

1269
00:53:15,040 --> 00:53:15,915
Jsou velmi podobné.

1270
00:53:15,915 --> 00:53:17,440
Dokonce jsem si je popletl někdy.

1271
00:53:17,440 --> 00:53:18,981
Před této sekci byl jsem rád, počkejte.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Takže to, co chcete
udělat, je výběr třídit,

1275
00:53:24,141 --> 00:53:25,890
způsob, jak si můžete myslet
o něm a způsobu

1276
00:53:25,890 --> 00:53:30,140
Mohu ujistit, že jsem se pokusit se dostat
je popletl, je to prochází

1277
00:53:30,140 --> 00:53:33,280
a vybere
Nejmenší číslo, a to

1278
00:53:33,280 --> 00:53:36,070
uvádí, že na začátku seznamu.

1279
00:53:36,070 --> 00:53:37,730
To swapy s tímto prvním místě.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Jsou to vlastně máme příklad pro mě.

1282
00:53:45,370 --> 00:53:46,540
Úžasné.

1283
00:53:46,540 --> 00:53:50,130
Takže jen způsob, jak myslet na to-- výběru
druh, vyberte nejmenší hodnotu.

1284
00:53:50,130 --> 00:53:51,940
A budeme se
spustit pomocí příkladu

1285
00:53:51,940 --> 00:53:55,320
si myslím, že pomůže, protože
Myslím si, že vizuální vždy pomoci.

1286
00:53:55,320 --> 00:53:58,510
Takže začneme s něčím
že je zcela netříděný.

1287
00:53:58,510 --> 00:54:00,730
Red bude netříděný,
zelená bude třídit.

1288
00:54:00,730 --> 00:54:02,190
To všechno dává smysl ve vteřině.

1289
00:54:02,190 --> 00:54:08,950
>> Tak jsme se projít a my iterovat
od začátku až do konce.

1290
00:54:08,950 --> 00:54:12,320
A my říkáme, OK, 2
naše nejmenší číslo.

1291
00:54:12,320 --> 00:54:15,680
Takže budeme mít 2 a jedeme
přesunout do přední části naší nabídku

1292
00:54:15,680 --> 00:54:17,734
protože je to
nejmenší číslo máme.

1293
00:54:17,734 --> 00:54:19,150
Takže to je to, co to dělá.

1294
00:54:19,150 --> 00:54:20,820
Je to jen tak vyměnit ty dva.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Takže teď jsme řazeny
část a netříděné část.

1297
00:54:25,450 --> 00:54:27,810
A co je dobré si uvědomit,
o výběru druhu

1298
00:54:27,810 --> 00:54:30,690
je, že jsme už jen výběr
z netříděného části.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Vytříděný část, kterou prostě nechat na pokoji.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> STUDENT: Jak to víš, co je
nejmenší bez srovnání

1303
00:54:38,452 --> 00:54:39,868
na každé jiné hodnoty v poli.

1304
00:54:39,868 --> 00:54:41,250
Instruktor: Dělá porovnat.

1305
00:54:41,250 --> 00:54:42,041
Rádi přeskočí to.

1306
00:54:42,041 --> 00:54:43,850
To je jen obecná celkově.

1307
00:54:43,850 --> 00:54:44,831
Jo.

1308
00:54:44,831 --> 00:54:47,205
Když jsme psát kód Jsem
jisti, že budete více spokojeni.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Ale uložit tento první
prvek nejmenší.

1311
00:54:53,030 --> 00:54:56,110
Můžete porovnat a
říkají, OK, je to menší?

1312
00:54:56,110 --> 00:54:56,660
Ano.

1313
00:54:56,660 --> 00:54:57,460
Nech si to.

1314
00:54:57,460 --> 00:54:58,640
Zde je to menší?

1315
00:54:58,640 --> 00:54:59,660
Ne?

1316
00:54:59,660 --> 00:55:02,510
>> To je vaše nejmenší,
přiřadit ji ke svému hodnotu.

1317
00:55:02,510 --> 00:55:06,340
A budete mnohem šťastnější
když jdeme přes kód.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Tak jsme se projít, jsme to vyměnit, tak pak
se podíváme na tomto netříděného části.

1320
00:55:13,970 --> 00:55:15,810
Takže jdeme vybrat tři z.

1321
00:55:15,810 --> 00:55:18,890
Chystáme se dát na na
konec naší tříděného části.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
A my jsme jen tak, aby dělal
to, že dělá to, a dělat, že.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Tak tohle je náš druh pseudokódu zde.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Budeme kód to tady ve vteřině.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Ale jen něco chodit
přes na vysoké úrovni.

1330
00:55:37,270 --> 00:55:40,275
Budeš chodit od
i = 0 pro n minus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
To je další optimalizace.

1333
00:55:43,530 --> 00:55:45,020
Nebojte se příliš mnoho o tom.

1334
00:55:45,020 --> 00:55:46,620
Tak jak jsi říkal.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Jak Jacob říkal, jak my
sledovat, co náš minimum je?

1337
00:55:54,406 --> 00:55:55,030
Jak to víme?

1338
00:55:55,030 --> 00:55:57,060
Musíme porovnat
vše v našem seznamu.

1339
00:55:57,060 --> 00:55:59,600
>> Takže minimálně rovná i.

1340
00:55:59,600 --> 00:56:03,870
Je to jen říkám, v tomto případě
index našeho minimální hodnotu.

1341
00:56:03,870 --> 00:56:07,660
Takže to bude iterovat
a to jde od j je roven i + 1.

1342
00:56:07,660 --> 00:56:11,420
Takže už víme, že
to je náš první prvek.

1343
00:56:11,420 --> 00:56:13,240
Nepotřebujeme porovnat ji k sobě.

1344
00:56:13,240 --> 00:56:16,970
Takže začneme porovnejte ji s další
ten, který je důvod, proč je i a 1 až n

1345
00:56:16,970 --> 00:56:20,110
minus 1, což je
konec pole tam.

1346
00:56:20,110 --> 00:56:25,090
A my, pokud pole v uvedeném
j je menší než pole min,

1347
00:56:25,090 --> 00:56:29,200
pak přeřadit, kde
Naše minimální indexy je.

1348
00:56:29,200 --> 00:56:37,470
>> A v případě, min není rovno I, jak je
tam, kam jsme se vrátili sem.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Tak, jako když jsme poprvé dělali tenhle.

1351
00:56:41,790 --> 00:56:49,310
V tomto případě by byl start na
nula, bylo by to skončí tím, že dva.

1352
00:56:49,310 --> 00:56:53,010
Takže by min nerovná i na konci.

1353
00:56:53,010 --> 00:56:55,720
To nám umožňuje vědět, že
musíme je vyměnit.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Cítím se jako konkrétní příklad
pomůže mnohem víc než to.

1356
00:57:00,470 --> 00:57:04,970
Takže budu kódu to s vámi
právě teď a myslím, že to bude lepší.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Druhy mají tendenci pracovat tímto způsobem v tom
je to často lepší, jen je vidět.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Takže to, co chceme udělat, je
nejprve chci nejmenší

1361
00:57:17,280 --> 00:57:19,890
část v její poloze v poli.

1362
00:57:19,890 --> 00:57:21,280
Přesně to, co Jacob říkal.

1363
00:57:21,280 --> 00:57:23,090
Musíte uložit, že nějak.

1364
00:57:23,090 --> 00:57:25,900
Takže budeme začněte zde
iterace přes pole.

1365
00:57:25,900 --> 00:57:28,970
Budeme říkat, že je to naše
První z nich jen začít.

1366
00:57:28,970 --> 00:57:38,308
Takže budeme mít int
nejmenší je rovná pole v i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Takže jedna věc je si všimnout, každý
když se to spustí smyčka,

1369
00:57:45,050 --> 00:57:48,550
začínáme o krok dál.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Když začneme se podíváme na tento jeden.

1372
00:57:57,440 --> 00:58:00,840
Příště budeme iterovat,
začínáme na tomto jednom

1373
00:58:00,840 --> 00:58:02,680
a přiřazení je náš nejmenší hodnota.

1374
00:58:02,680 --> 00:58:10,450
Takže je to velmi podobné bubliny druhu
kde víme, že po jednom průchodu,

1375
00:58:10,450 --> 00:58:11,700
Tento poslední prvek je tříděn.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Při výběru druhu,
že je to právě naopak.

1378
00:58:15,120 --> 00:58:18,950
>> Při každém průchodu, víme, že
První z nich je seřazen.

1379
00:58:18,950 --> 00:58:21,360
Po druhém průchodu,
druhá bude třídit.

1380
00:58:21,360 --> 00:58:26,470
A jak jsi viděl s příklady prezentací,
naše řazeny část prostě pořád roste.

1381
00:58:26,470 --> 00:58:34,020
Takže nastavením naši nejmenší z
na pole i vše to dělá

1382
00:58:34,020 --> 00:58:37,340
se omezí, co
se díváme na to, jak

1383
00:58:37,340 --> 00:58:40,164
minimalizovat počet
srovnávání děláme.

1384
00:58:40,164 --> 00:58:41,770
Znamená to, že smysl pro každého?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Líbí se mi třeba projít, že
opět pomaleji nebo jinými slovy?

1387
00:58:46,380 --> 00:58:47,180
Jsem rád, že.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Takže jsme skladování
hodnota v tomto bodě,

1392
00:58:55,540 --> 00:58:57,840
ale také chceme uložit index.

1393
00:58:57,840 --> 00:59:01,010
Takže budeme ukládat
pozice nejmenší

1394
00:59:01,010 --> 00:59:02,770
jeden, který se jen bude i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Takže teď Jacob je spokojen.

1397
00:59:05,440 --> 00:59:06,870
Máme věci uloženy.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
A teď se musíme dívat přes
netříděného část pole.

1400
00:59:11,870 --> 00:59:18,170
Takže v tomto případě, že tento
Bude nám netříděný.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
To je i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Takže to, co budeme dělat
bude pro smyčce.

1406
00:59:30,040 --> 00:59:32,066
Kdykoli budete potřebovat
iterovat přes pole,

1407
00:59:32,066 --> 00:59:33,440
vaše mysl může jít do pro smyčce.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Tak pro některé int k
equals--, co si myslíme, že

1410
00:59:38,090 --> 00:59:39,700
k se bude rovnat začít?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
To je to, co jsme si stanovili jako naše nejmenší
hodnotu a chceme srovnávat.

1413
00:59:44,766 --> 00:59:47,090
Co chceme srovnávat to?

1414
00:59:47,090 --> 00:59:48,730
Je to bude to příští, je to tak?

1415
00:59:48,730 --> 00:59:53,200
Tak jsme se chceme k nutné inicializovat
aby i plus 1 na start.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> A my chceme k v tomto případě
již velikost uloženy tady,

1418
01:00:02,800 --> 01:00:03,930
takže stačí použít velikost.

1419
01:00:03,930 --> 01:00:06,240
Velikost je velikost pole.

1420
01:00:06,240 --> 01:00:09,620
A my prostě chceme, aby
aktualizovat K některým pokaždé.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
V pohodě.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Takže teď musíme najít
nejmenší prvek zde.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Takže pokud budeme iterovat jsme
chci říct, je-li pole na k

1427
01:00:31,380 --> 01:00:37,080
je nižší než naše nejmenší value--
to je místo, kde jsme vlastně

1428
01:00:37,080 --> 01:00:42,950
sledování toho, co je
nejmenší here--

1429
01:00:42,950 --> 01:00:47,740
pak chceme přiřadit
co naše nejmenší hodnota je.

1430
01:00:47,740 --> 01:00:50,645
>> To znamená, že, oh, my jsme
iterace zde.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Ať už je hodnota zde
není naše nejmenší věc.

1433
01:00:53,740 --> 01:00:54,448
Nechceme ho.

1434
01:00:54,448 --> 01:00:56,100
Chceme ji přiřadit.

1435
01:00:56,100 --> 01:01:02,050
Takže pokud jsme ho přerozdělují, co dělat
si myslíte, že by mohlo být v tomto kódu tady?

1436
01:01:02,050 --> 01:01:04,160
Chceme přiřadit
Nejmenší a pozice.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Takže to, co je nejmenší teď?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
STUDENT: Array k.

1441
01:01:09,130 --> 01:01:09,963
Instruktor: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
A jaká je pozice teď?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Co je na indexy
naše nejmenší hodnota?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Je to jen k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Takže pole k, k, se shodují se.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Takže jsme chtěli přiřadit to.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
A potom jsme našli naše nejmenší,
takže na konci tohoto cyklu for

1454
01:01:39,950 --> 01:01:45,100
zde jsme našli to, co naše nejmenší
je hodnota, takže jsme prostě vyměnit ji.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
V tomto případě, stejně jako že naše
Nejmenší hodnota je tady.

1457
01:01:50,816 --> 01:01:51,940
Toto je náš nejmenší hodnota.

1458
01:01:51,940 --> 01:01:57,690
>> Chceme jen, aby ho vyměnit tu, která je
co, že funkce odkládací na dně

1459
01:01:57,690 --> 01:02:01,270
ano, které jsme právě sepsal
spolu před pár minutami.

1460
01:02:01,270 --> 01:02:02,775
Tak by to mělo vypadat povědomě.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
A pak to bude jen opakovat
až dokud nedosáhne celou cestu

1463
01:02:08,030 --> 01:02:13,100
až do konce, což znamená, že
mají nulovou prvky, které nejsou roztříděné

1464
01:02:13,100 --> 01:02:14,800
a vše, co bylo řazeny.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Smysl?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Trochu konkrétněji?

1469
01:02:19,280 --> 01:02:19,990
Kód pomoci?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> STUDENT: Pro velikosti, nikdy
Opravdu jej definovat nebo změnit,

1472
01:02:26,410 --> 01:02:27,340
jak to víš?

1473
01:02:27,340 --> 01:02:32,380
>> Instruktor: Takže jedna věc je
Všimněte si, tady je velikost int.

1474
01:02:32,380 --> 01:02:35,680
Takže říkáme v tomto sort-- druhu
je funkce v tomto case-- je to

1475
01:02:35,680 --> 01:02:40,770
výběr třídit, je předáván
v s funkcí.

1476
01:02:40,770 --> 01:02:43,460
Takže pokud to nebyl přijat
ve byste něco

1477
01:02:43,460 --> 01:02:47,840
jako s délkou pole
nebo byste iterovat

1478
01:02:47,840 --> 01:02:49,390
najít délku.

1479
01:02:49,390 --> 01:02:52,680
Ale protože je předáván
v, můžeme jen použít.

1480
01:02:52,680 --> 01:02:55,720
Jste jen předpokládat, že uživatel
vám dal platnou velikost, která

1481
01:02:55,720 --> 01:02:57,698
vlastně představuje
Velikost vašeho pole.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
V pohodě?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Jestliže vy máte nějaké problémy s těmito
nebo chcete více praxe kódování druhů

1486
01:03:05,870 --> 01:03:08,050
na vlastní pěst, měli byste
přejít na study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Je to nástroj.

1489
01:03:12,670 --> 01:03:15,040
Mají checker, který
můžete skutečně psát.

1490
01:03:15,040 --> 01:03:16,180
Dělají pseudokódu.

1491
01:03:16,180 --> 01:03:19,310
Mají více videí a snímků
včetně těch, které používám zde.

1492
01:03:19,310 --> 01:03:23,150
Takže pokud jste stále pocit,
trochu rozmazaný, zkuste to ven.

1493
01:03:23,150 --> 01:03:25,670
Jako vždy, pojď se mnou mluvit, taky.

1494
01:03:25,670 --> 01:03:26,320
Otázka?

1495
01:03:26,320 --> 01:03:28,611
>> STUDENT: Chceš říct, že
Velikost je definováno výše?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
Instruktor: Ano.

1498
01:03:29,900 --> 01:03:35,570
Velikost je definováno výše up
tady v deklaraci funkce.

1499
01:03:35,570 --> 01:03:39,060
Takže lze předpokládat, že to bylo předáno do
uživatelem, a pro jednoduchost,

1500
01:03:39,060 --> 01:03:41,896
budeme předpokládat, že
Uživatel nám správnou velikost.

1501
01:03:41,896 --> 01:03:43,240
V pohodě.

1502
01:03:43,240 --> 01:03:44,390
Tak to je výběr sort.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Chlapi, vím, že učíme dnes hodně.

1505
01:03:47,640 --> 01:03:49,710
Je to hustý dat pro sekci.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Takže s tím budeme
jít na vložení druhu.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Takže než to, co musíme udělat
naše runtime analýza zde.

1511
01:04:06,100 --> 01:04:10,190
Takže v nejlepším případě,
udělena, protože jsem vám ukázal

1512
01:04:10,190 --> 01:04:11,960
tabulka Už jsem
druh dal pryč.

1513
01:04:11,960 --> 01:04:15,430
Ale nejlepším případě runtime, co si myslíme, že?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Vše řazeny.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N druhou.

1518
01:04:22,070 --> 01:04:24,780
Každý, kdo má vysvětlení
proč si myslíte, že?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> STUDENT: Jste porovnání through--

1521
01:04:30,519 --> 01:04:31,268
Instruktor: Správně.

1522
01:04:31,268 --> 01:04:32,540
Jste porovnání projít.

1523
01:04:32,540 --> 01:04:35,630
V každé iteraci, i když
jsme dekrementování to po druhém,

1524
01:04:35,630 --> 01:04:38,950
jste stále prohledávat
vše najít nejmenší jeden.

1525
01:04:38,950 --> 01:04:42,390
Takže i když vaše nejmenší hodnota
je tady na začátku,

1526
01:04:42,390 --> 01:04:44,710
jste stále porovnávání
proti vším

1527
01:04:44,710 --> 01:04:46,550
aby se ujistil, že je to nejmenší věc.

1528
01:04:46,550 --> 01:04:49,820
Takže skončíte procházející
přibližně n na druhou krát.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Dobrá.

1531
01:04:51,590 --> 01:04:52,785
A co je nejhorší?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Také n na druhou, protože budete
bude dělat, že stejný postup.

1534
01:04:57,980 --> 01:05:01,670
Takže v tomto případě výběr
druh má něco

1535
01:05:01,670 --> 01:05:04,010
že jsme také volat očekávané runtime.

1536
01:05:04,010 --> 01:05:07,400
Takže ostatní, jsme jen vím,
horní a dolní hranice.

1537
01:05:07,400 --> 01:05:11,180
V závislosti na tom, jak blázen naše
Seznam je netříděný nebo jak to je,

1538
01:05:11,180 --> 01:05:15,350
se liší mezi n nebo n na druhou.

1539
01:05:15,350 --> 01:05:16,550
Nevíme.

1540
01:05:16,550 --> 01:05:22,820
>> Ale protože výběr druh má stejné
nejhorší a nejlepší případ, že nám říká, že

1541
01:05:22,820 --> 01:05:25,880
bez ohledu na to, jaký typ vstupu jsme
mají, ať už je to zcela

1542
01:05:25,880 --> 01:05:29,130
řazeny nebo zcela
reverzní řazeny, je to

1543
01:05:29,130 --> 01:05:30,740
bude trvat stejnou dobu.

1544
01:05:30,740 --> 01:05:33,760
Takže v tomto případě, pokud vás
pamatovat z našeho stolu,

1545
01:05:33,760 --> 01:05:38,610
ve skutečnosti měla hodnotu, která
Tyto dva druhy nemají,

1546
01:05:38,610 --> 01:05:40,390
což je předpokládaná doba zálohování.

1547
01:05:40,390 --> 01:05:43,350
Takže víme, že vždy, když
narazíme výběr druhu,

1548
01:05:43,350 --> 01:05:45,380
je zaručeno, aby
spustit n na druhou dobu.

1549
01:05:45,380 --> 01:05:46,630
Není tam žádná variabilita.

1550
01:05:46,630 --> 01:05:47,630
Je to od nich očekává.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
A opět, pokud se chcete dozvědět,
více, vzít CS 124 na jaře.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Dobrá.

1555
01:05:56,712 --> 01:05:57,545
Viděli jsme tohle.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
V pohodě.

1558
01:05:59,030 --> 01:06:00,930
Takže vložení sort.

1559
01:06:00,930 --> 01:06:03,330
A já asi bude
na požár přes to.

1560
01:06:03,330 --> 01:06:05,440
Nebudu mít vy to kód.

1561
01:06:05,440 --> 01:06:06,580
Budeme se jen procházet přes to.

1562
01:06:06,580 --> 01:06:10,500
Takže vložení druh je druh
o podobný výběru druhu

1563
01:06:10,500 --> 01:06:14,460
v tom, že máme oba netříděné
a seřazena část pole.

1564
01:06:14,460 --> 01:06:20,260
>> Ale to, co je, je, že
jak jsme se projít jeden po druhém,

1565
01:06:20,260 --> 01:06:24,210
jsme prostě vzít bez ohledu na počet
je další v našem netříděný,

1566
01:06:24,210 --> 01:06:28,507
a správně třídit
do našeho tříděného pole.

1567
01:06:28,507 --> 01:06:30,090
Bude to větší smysl na příkladu.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Takže vše, co začíná jako netříděný,
Stejně jako u výběru druhu.

1570
01:06:35,430 --> 01:06:38,740
A budeme třídit na tuto
vzestupně, jak jsme byli.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Takže na našem prvním průchodu
Vezmeme první hodnotu

1573
01:06:43,340 --> 01:06:46,700
a říkáme, OK, jste
nyní v seznamu sami.

1574
01:06:46,700 --> 01:06:49,150
>> Protože jste v seznamu
sami, jste řazeny.

1575
01:06:49,150 --> 01:06:52,460
Gratulujeme k bytí
první prvek v tomto poli.

1576
01:06:52,460 --> 01:06:54,800
Jste již řazeno vše na vlastní pěst.

1577
01:06:54,800 --> 01:06:58,900
Takže teď jsme řazeny
a netříděné pole.

1578
01:06:58,900 --> 01:07:01,760
Takže teď jsme se poprvé.

1579
01:07:01,760 --> 01:07:05,600
Co se stane mezi zde
a zde je to, že říkáme,

1580
01:07:05,600 --> 01:07:08,890
OK, jdeme se podívat na
První hodnota naší netříděný pole

1581
01:07:08,890 --> 01:07:13,270
a budeme vstup je ve svém
správné místo v tříděném poli.

1582
01:07:13,270 --> 01:07:21,460
>> Takže to, co děláme, je bereme 5 a
říkáme, OK, 5 je vyšší než 3,

1583
01:07:21,460 --> 01:07:24,630
takže stačí vložit ji přímo
na pravé straně, že.

1584
01:07:24,630 --> 01:07:25,130
Jsme dobře.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Takže jdeme na naše další.

1587
01:07:28,420 --> 01:07:29,720
A vezmeme 2.

1588
01:07:29,720 --> 01:07:34,330
My říkáme, OK, 2 menší
než 3, takže víme, že to

1589
01:07:34,330 --> 01:07:36,220
musí být v
Přední část našeho seznamu nyní.

1590
01:07:36,220 --> 01:07:41,800
Takže to, co děláme, je, že jsme tlačit 3 a 5 se
a přejdeme 2 do toho prvního slotu.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Takže jsme prostě vložením do
správné místo, to by mělo být.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Pak se podíváme na naše
příští, a říkáme 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 je větší než
vše v našem tříděném poli,

1596
01:07:53,620 --> 01:07:56,000
tak jsme prostě označit ji až do konce.

1597
01:07:56,000 --> 01:07:56,960
A pak se podíváme na 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 je menší než 6, je to méně
než 5, ale je to menší než 3.

1600
01:08:03,020 --> 01:08:06,270
Tak jsme prostě vložte ji přímo do
uprostřed mezi 3 a 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Tak, aby se to trochu
trochu konkrétnější,

1603
01:08:10,530 --> 01:08:12,280
Zde je druh
představa o tom, co se stalo.

1604
01:08:12,280 --> 01:08:16,430
Takže pro každý prvek netříděného, ​​jsme
určit, kde v tříděném části

1605
01:08:16,430 --> 01:08:17,090
to je.

1606
01:08:17,090 --> 01:08:20,680
>> Tak, aby se nezapomínalo na
tříděny a netříděné,

1607
01:08:20,680 --> 01:08:26,080
musíme projít skrz a obr
, kde se vejde do tříděného pole.

1608
01:08:26,080 --> 01:08:31,460
A my ho vložit posunutím
prvky vpravo dolů.

1609
01:08:31,460 --> 01:08:34,910
A pak jsme prostě udržet
iterace, dokud

1610
01:08:34,910 --> 01:08:39,270
mají zcela seřazený seznam
kde netříděné je nyní nulová

1611
01:08:39,270 --> 01:08:41,720
a tříděný zabírá
celistvost našeho seznamu.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Takže, ještě jednou, aby se věci ještě
konkrétnější, máme pseudokódu.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Takže v podstatě pro i je
rovno 0 do n mínus 1,

1616
01:08:52,410 --> 01:08:54,790
to je jen délka našeho pole.

1617
01:08:54,790 --> 01:09:00,979
Máme nějaký prvek, který se rovná
První pole nebo první indexy.

1618
01:09:00,979 --> 01:09:03,200
Nastavili jsme j, která se rovná.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Takže zatímco j je větší než
nula a pole, j minus 1

1621
01:09:09,210 --> 01:09:11,660
je větší než
prvek, takže vše, co dělá

1622
01:09:11,660 --> 01:09:17,479
je zajistit, aby
Váš j Vás doopravdy zastupuje

1623
01:09:17,479 --> 01:09:20,010
netříděného část pole.

1624
01:09:20,010 --> 01:09:30,745
>> Takže zatímco tam je ještě věci
třídit a j mínus jedna je-- co

1625
01:09:30,745 --> 01:09:31,840
je její součástí?

1626
01:09:31,840 --> 01:09:34,760
J zde nebyla definována.

1627
01:09:34,760 --> 01:09:35,677
Je to trochu nepříjemné.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Tak jako tak.

1630
01:09:36,689 --> 01:09:39,899
Tak j minus 1, máte kontrolu
prvek před ním.

1631
01:09:39,899 --> 01:09:46,460
Říkáte, že, OK, je element
předtím, než tam, kde jsem am-- pojďme

1632
01:09:46,460 --> 01:09:47,540
skutečně čerpat na to.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Takže řekněme, že je to
jako na našem druhém průchodu.

1635
01:09:56,830 --> 01:09:59,525
Takže i se bude rovnat
1, který je zde.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Takže i bude roven 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
To by bylo 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Dobrá.

1642
01:10:16,750 --> 01:10:20,945
Takže naše prvkem v tomto případě
bude rovna 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
A máme nějaké j, který je
bude roven 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, j je dekrementování.

1647
01:10:30,971 --> 01:10:31,720
To je to, co to je.

1648
01:10:31,720 --> 01:10:35,680
Tak j je roven i tak, co to je
Říká se, že, jak jsme kupředu,

1649
01:10:35,680 --> 01:10:37,530
jsme jen ujistit
že nejsme přes

1650
01:10:37,530 --> 01:10:43,520
indexování tímto způsobem, když se snažíme
vložit věci do našeho seznamu seřazené.

1651
01:10:43,520 --> 01:10:49,850
>> Takže když j je roven 1, v tomto případě, a
array j minus one-- tak array j minus 1

1652
01:10:49,850 --> 01:10:54,610
je 2 v tomto case--, pokud je to
větší než prvek,

1653
01:10:54,610 --> 01:10:57,700
pak to všechno dělá
se přesouvá věci dolů.

1654
01:10:57,700 --> 01:11:04,790
Takže v tomto případě, pole j mínus jedna
by pole nulová, což je 2.

1655
01:11:04,790 --> 01:11:08,430
2 není větší než 4,
tak to neprovede.

1656
01:11:08,430 --> 01:11:11,460
Takže posun nepohybuje dolů.

1657
01:11:11,460 --> 01:11:18,790
Co to však je zde jen
pohybem seřazené pole dolů.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
V tomto případě, ve skutečnosti, jsme
by do-- udělejme tuto tři.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Takže pokud jsme se projít s
tento příklad, my jsme teď tady.

1662
01:11:31,970 --> 01:11:32,740
To je seřazen.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
To je netříděný.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
V pohodě?

1667
01:11:39,860 --> 01:11:46,620
Takže i je rovno 2, takže
náš prvek je rovno 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
A naše j je roven 2.

1670
01:11:52,270 --> 01:12:00,620
Tak jsme se prohlédnout a my
říkají, OK, je pole j mínus jedna

1671
01:12:00,620 --> 01:12:03,470
větší než prvek
že se díváme?

1672
01:12:03,470 --> 01:12:05,540
A odpověď je ano, je to tak?

1673
01:12:05,540 --> 01:12:11,275
4 je větší než 3, a j
je 2, takže tento kód spustí.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Takže teď to, co děláme pole na
2, tak tady jsme se je vyměnit.

1676
01:12:18,550 --> 01:12:25,620
Tak jsme se jen říct, OK, pole
na 2 se nyní bude 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
A j bude rovnat
j minus 1, což je 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
To je hrozné, ale
vy dostanete nápad.

1681
01:12:37,200 --> 01:12:38,360
J je nyní roven 1.

1682
01:12:38,360 --> 01:12:44,360
A pole j se jen bude
rovná naší prvku, který byl 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
I vymazat něco, co jsem neměl
mají nebo miswrote něco,

1685
01:12:48,570 --> 01:12:49,910
ale vy dostanete nápad.

1686
01:12:49,910 --> 01:12:50,640
>> To se pohybují n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
A pak, pokud tomu tak bylo, bylo by to smyčka
znovu, a to bych řekl, OK, j je 1 nyní.

1689
01:12:57,960 --> 01:13:00,665
A pole j minus 1 je nyní 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Je 2 menší než naše prvek?

1692
01:13:03,760 --> 01:13:04,540
Ne?

1693
01:13:04,540 --> 01:13:07,970
To znamená, že máme
vkládá tento prvek

1694
01:13:07,970 --> 01:13:10,110
ve správném místě v našem tříděného poli.

1695
01:13:10,110 --> 01:13:14,400
Pak se můžeme vzít a říkáme,
OK, naše seřazené pole je tady.

1696
01:13:14,400 --> 01:13:19,940
A to by se toto číslo 6 a musí být
jako, OK, 6 menší než toto číslo?

1697
01:13:19,940 --> 01:13:20,480
Ne?

1698
01:13:20,480 --> 01:13:21,080
V pohodě.

1699
01:13:21,080 --> 01:13:22,680
Jsme v pořádku.

1700
01:13:22,680 --> 01:13:23,530
>> Udělej to znovu.

1701
01:13:23,530 --> 01:13:24,740
Říkáme 7.

1702
01:13:24,740 --> 01:13:29,010
Je menší než 7 do konce
naší tříděného pole?

1703
01:13:29,010 --> 01:13:29,520
Ne.

1704
01:13:29,520 --> 01:13:30,430
Takže jsme v pohodě.

1705
01:13:30,430 --> 01:13:32,760
Takže by to být tříděny.

1706
01:13:32,760 --> 01:13:38,610
V podstatě to všechno dělá
Je to říká vzít

1707
01:13:38,610 --> 01:13:42,060
První prvek
Váš netříděné pole,

1708
01:13:42,060 --> 01:13:46,010
zjistit, kde to jde
v tříděném poli.

1709
01:13:46,010 --> 01:13:48,780
A to jen stará
swapů k tomu, že.

1710
01:13:48,780 --> 01:13:51,300
Vy jste v podstatě jen vymění
dokud je to na správném místě.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Vizuální image je to, že jste
pohybující se všechno se tím, že.

1713
01:13:56,990 --> 01:13:59,420
>> Takže je to jako polovina bublina trochu ve stylu.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Podívejte se na studii 50.

1716
01:14:03,420 --> 01:14:06,000
Vřele doporučuji se snaží
kódovat na vlastní pěst.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Pokud máte nějaké otázky, nebo chcete-li
viz ukázkový kód pro vložení druhu,

1719
01:14:12,450 --> 01:14:13,750
dejte mi prosím vědět.

1720
01:14:13,750 --> 01:14:14,500
Vždycky jsem se kolem sebe.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Takže v nejhorším případě runtime
a nejlepším případě runtime.

1723
01:14:20,200 --> 01:14:30,700
Jak jste chlap viděl z tabulky už jsem
vám ukázal, že to tak n na druhou a n.

1724
01:14:30,700 --> 01:14:35,590
>> Tak laskav a šel pryč z toho, co jsme si povídali
o s našimi předchozími druhy, nejhorší

1725
01:14:35,590 --> 01:14:38,760
případ runtime je, že pokud
je to zcela netříděného

1726
01:14:38,760 --> 01:14:42,530
musíme porovnat všechny tyto n-krát.

1727
01:14:42,530 --> 01:14:47,020
Děláme spoustu srovnání
protože pokud je to v opačném pořadí,

1728
01:14:47,020 --> 01:14:50,360
budeme říkat, OK, to
je stejný, to je dobré,

1729
01:14:50,360 --> 01:14:54,650
a ten bude muset být ve srovnání
proti první se přesunout zpět.

1730
01:14:54,650 --> 01:14:56,710
A jak se dostaneme k
konec ocasu, máme

1731
01:14:56,710 --> 01:14:59,440
porovnávat, porovnávat a
porovnat proti všemu.

1732
01:14:59,440 --> 01:15:03,030
>> Takže to nakonec byla
n přibližně čtvercový.

1733
01:15:03,030 --> 01:15:09,510
Pokud je to v pořádku, tak si
říkají, OK, 2, jsi dobrý.

1734
01:15:09,510 --> 01:15:11,330
3, jste v porovnání s 2.

1735
01:15:11,330 --> 01:15:12,310
Jsi dobrá.

1736
01:15:12,310 --> 01:15:14,150
4, stačí porovnat na ocasu.

1737
01:15:14,150 --> 01:15:14,990
Jsi dobrá.

1738
01:15:14,990 --> 01:15:17,140
6, v porovnání s ocasem, že jsi v pořádku.

1739
01:15:17,140 --> 01:15:20,870
Takže pro každé místo, pokud je již
řazeny, děláš jednu srovnání.

1740
01:15:20,870 --> 01:15:22,320
Takže je to jen n.

1741
01:15:22,320 --> 01:15:26,840
A protože máme nejlepší případovou runtime
n a nejhorším případě běhu n

1742
01:15:26,840 --> 01:15:28,680
čtvercový, nemáme očekávaný runtime.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Záleží jen na
chaos našeho seznamu zde.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
A opět další
graf a další tabulky.

1747
01:15:39,530 --> 01:15:41,170
Takže rozdíly mezi druhy.

1748
01:15:41,170 --> 01:15:44,180
Já jsem prostě jít vánek přes, I
pocit, že jsme mluvili značně

1749
01:15:44,180 --> 01:15:46,570
o tom, jak všechny druhy
o lišit a propojit.

1750
01:15:46,570 --> 01:15:50,564
Takže Merge sort je poslední
I se nesl vám kluci s.

1751
01:15:50,564 --> 01:15:52,105
Máme dost barevný obraz.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Takže sloučit druh je rekurzivní algoritmus.

1754
01:15:56,040 --> 01:15:59,910
Tak si kluci vědí, co
rekurzivní funkce?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Každý, kdo chtěl říct?

1757
01:16:03,320 --> 01:16:04,739
Chcete-li to zkusit?

1758
01:16:04,739 --> 01:16:07,280
Tak rekurzivní funkce je jen
funkce, která volá sama sebe.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Takže pokud vy jste obeznámeni
s Fibonacci sekvence,

1761
01:16:11,590 --> 01:16:15,670
která je považována za rekurzivní, protože
budete mít předchozí dva

1762
01:16:15,670 --> 01:16:17,530
a přidejte je spolu
dostat své další.

1763
01:16:17,530 --> 01:16:21,440
Tak rekurzivní, Vždycky si myslím,
rekurze jako jako spirála

1764
01:16:21,440 --> 01:16:24,430
takže jste jako po spirále dolů do něj.

1765
01:16:24,430 --> 01:16:27,150
Ale je to jen funkce
která volá sama sebe.

1766
01:16:27,150 --> 01:16:32,660
>> A ve skutečnosti, velmi rychle jsem
může ukázat, jak to vypadá.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Tak tady rekurzivní, podíváme-li se, je to
rekurzivní způsob, jak shrnout přes pole.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Takže vše, co děláme, je
máme funkci sum

1771
01:16:47,880 --> 01:16:52,210
částka, která má velikost a pole.

1772
01:16:52,210 --> 01:16:55,210
A pokud si všimnete, velikost
úbytky podle jednoho pokaždé.

1773
01:16:55,210 --> 01:17:00,365
A to vše dělá, je, pokud x je rovno
zero-- takže pokud velikost pole

1774
01:17:00,365 --> 01:17:02,710
je roven zero-- vrátí nulu.

1775
01:17:02,710 --> 01:17:10,440
>> Jinak to shrnuje tento
poslední prvek pole,

1776
01:17:10,440 --> 01:17:14,790
a pak vezme součet
zbytek pole.

1777
01:17:14,790 --> 01:17:17,555
Takže je to jen rozebrat to
do menších a menších problémů.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Dlouhý příběh krátký, rekurze,
funkce, která volá sama sebe.

1780
01:17:21,890 --> 01:17:25,740
Jestli je to všechno, co máš z toho,
že to, co rekurzivní funkce.

1781
01:17:25,740 --> 01:17:29,870
Pokud budete mít 51, dostanete velmi,
velmi pohodlné s rekurze.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Je to opravdu cool.

1784
01:17:32,370 --> 01:17:34,660
Dávalo to smysl, jako
3 AM jednu noc.

1785
01:17:34,660 --> 01:17:37,900
A byl jsem rád, proč
Nikdy jsem použít?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Takže pro sloučení druhu, v podstatě
co to bude dělat, je, že je to

1788
01:17:42,430 --> 01:17:45,620
chystá vyrazit a zlomit to
dolů, dokud je to jen jednotlivé prvky.

1789
01:17:45,620 --> 01:17:47,570
Jednotlivé prvky jsou lehce vyřešit.

1790
01:17:47,570 --> 01:17:48,070
Vidíme, že.

1791
01:17:48,070 --> 01:17:50,760
Máte-li jeden prvek, je to
již považován za tříděný.

1792
01:17:50,760 --> 01:17:53,800
A tak na vstupu n prvků,
jestliže n je menší než 2,

1793
01:17:53,800 --> 01:17:58,120
jen vrátit protože to znamená
to je buď 0 nebo 1, jak jsme viděli.

1794
01:17:58,120 --> 01:18:00,050
Ty jsou považovány za tříděné prvky.

1795
01:18:00,050 --> 01:18:02,170
>> Jinak rozbít na polovinu.

1796
01:18:02,170 --> 01:18:06,336
Seřadit první polovinu, třídit druhý
poloviny, a pak spojit je dohromady.

1797
01:18:06,336 --> 01:18:07,460
Proč se to jmenuje merge sort.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Takže máme tu budeme třídit tyto.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Tak jsme se držet s nimi
dokud se velikost pole je 1.

1802
01:18:17,210 --> 01:18:20,790
Takže když je to 1, právě jsme se vrátit
protože se jedná o setříděné pole,

1803
01:18:20,790 --> 01:18:23,940
a to je tříděného pole, a to je
setříděné pole, jsme všichni řazeny.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Takže to, co děláme, je, že jsme
začít sloučení dohromady.

1806
01:18:29,420 --> 01:18:31,820
>> Takže způsob, jak můžete
přemýšlet o slučování je

1807
01:18:31,820 --> 01:18:36,240
stačí odstranit menší
Počet každé z dílčích polí

1808
01:18:36,240 --> 01:18:38,330
a jen připojit jej k objevily pole.

1809
01:18:38,330 --> 01:18:44,290
Takže, když se podíváte tady, když máme
Tyto sady máme 4, 6, a 1.

1810
01:18:44,290 --> 01:18:47,280
Když chceme sloučit tyto,
Podíváme se na těchto prvních dvou

1811
01:18:47,280 --> 01:18:50,730
a říkáme, OK, 1 menší,
to jde dopředu.

1812
01:18:50,730 --> 01:18:54,330
4 a 6, není nic k porovnání
to, stačí označit ji až do konce.

1813
01:18:54,330 --> 01:18:58,020
>> Když jsme se spojit tyto dvě, právě jsme
mít menší jeden z těchto dvou,

1814
01:18:58,020 --> 01:18:59,310
takže je to jedno.

1815
01:18:59,310 --> 01:19:01,690
A teď jsme se
menší z těchto dvou, SO 2.

1816
01:19:01,690 --> 01:19:03,330
Menší z těchto dvou, 3.

1817
01:19:03,330 --> 01:19:06,260
Menší z těchto dvou, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Takže jste právě sundal ty.

1819
01:19:08,630 --> 01:19:11,210
A protože jsem
byly řazeny dříve,

1820
01:19:11,210 --> 01:19:14,300
stačí jedno
Porovnání pokaždé, když.

1821
01:19:14,300 --> 01:19:19,610
Takže více kódu, prostě reprezentace.

1822
01:19:19,610 --> 01:19:24,410
Takže začnete ve středu a
třídit vlevo a vpravo

1823
01:19:24,410 --> 01:19:26,180
a pak stačí spojit ty.

1824
01:19:26,180 --> 01:19:30,080
>> A my nemáme kód
pro sloučení tady.

1825
01:19:30,080 --> 01:19:34,110
Ale opět, když jdete na
studium 50, bude to tam.

1826
01:19:34,110 --> 01:19:36,860
V opačném případě přijde se mnou mluvit
pokud jste stále zmatená.

1827
01:19:36,860 --> 01:19:42,340
Tak super věc je, že nejlepší případ,
v nejhorším případě, a očekává, že runtime

1828
01:19:42,340 --> 01:19:46,250
jsou v protokolu n, které
je mnohem lepší, než jsme

1829
01:19:46,250 --> 01:19:48,000
vidět po zbytek našich druhů.

1830
01:19:48,000 --> 01:19:51,840
Viděli jsme n na druhou
a to, co jsme vlastně

1831
01:19:51,840 --> 01:19:54,380
sem je n log n, což je skvělé.

1832
01:19:54,380 --> 01:19:55,830
>> Podívejte se, jak daleko lepší to je.

1833
01:19:55,830 --> 01:19:56,780
Taková pěkná křivka.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Tak mnohem efektivnější.

1836
01:20:00,120 --> 01:20:03,510
Pokud jste někdy možné, použijte sloučit druh.

1837
01:20:03,510 --> 01:20:04,810
To vám ušetří čas.

1838
01:20:04,810 --> 01:20:07,670
Pak znovu, jak jsme řekli, je-li
jste v této nižší regionu,

1839
01:20:07,670 --> 01:20:09,480
to neznamená, že to
velký rozdíl.

1840
01:20:09,480 --> 01:20:11,360
Získáte až tisíce
a tisíce vstupů,

1841
01:20:11,360 --> 01:20:13,318
budete určitě chtít
efektivnější algoritmus.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
A opět, naše milá tabulka všech
druhy, které kluci se dnes dozvěděl.

1844
01:20:19,400 --> 01:20:21,157
>> Takže vím, že to byl hustý den.

1845
01:20:21,157 --> 01:20:23,490
To nemusí nutně jít
které vám pomohou s vaší pset.

1846
01:20:23,490 --> 01:20:28,250
Ale jen chci, aby disclaimer
že oddíl není jen o psets.

1847
01:20:28,250 --> 01:20:31,240
To vše materiál je fér
Hra pro vaše midterms.

1848
01:20:31,240 --> 01:20:35,430
A také pokud si pokračovat s CS,
Toto jsou opravdu důležité základy

1849
01:20:35,430 --> 01:20:37,870
které budete potřebovat vědět.

1850
01:20:37,870 --> 01:20:41,700
Takže pár dní bude
trochu pset pomoc,

1851
01:20:41,700 --> 01:20:44,600
ale několik týdnů bude
mnohem skutečný obsah

1852
01:20:44,600 --> 01:20:46,600
že se může zdát Super
užitečné pro vás právě teď,

1853
01:20:46,600 --> 01:20:51,215
ale slibuji, že pokud budete pokračovat
na bude velmi, velmi užitečné.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Tak to je pro sekci.

1856
01:20:54,250 --> 01:20:55,250
Dolů drátu.

1857
01:20:55,250 --> 01:20:56,570
Udělal jsem to během jedné minuty.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Ale tam jdete.

1860
01:20:58,970 --> 01:21:01,240
A já budu mít koblihy nebo bonbóny.

1861
01:21:01,240 --> 01:21:03,464
Je někdo alergický na
něco, mimochodem?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Vajec a mléka.

1864
01:21:05,890 --> 01:21:08,120
Takže koblihy jsou ne?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Dobrá.

1868
01:21:10,770 --> 01:21:12,120
Čokoláda ne?

1869
01:21:12,120 --> 01:21:12,620
Starburst.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starburst jsou dobré.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Budeme mít
Starburst příští týden poté.

1874
01:21:17,045 --> 01:21:18,240
To je to, co budu mít.

1875
01:21:18,240 --> 01:21:19,690
Vy máte skvělý týden.

1876
01:21:19,690 --> 01:21:20,460
Číst vaše spec.

1877
01:21:20,460 --> 01:21:22,130
>> Dejte mi vědět, pokud máte jakékoliv dotazy.

1878
01:21:22,130 --> 01:21:25,300
Pset dva stupně by měla být
k tobě do čtvrtka.

1879
01:21:25,300 --> 01:21:28,320
Pokud máte nějaké otázky
o tom, jak jsem se třídí něco

1880
01:21:28,320 --> 01:21:32,250
nebo proč jsem se třídí něco tak, jak jsem
se, prosím, napište mi, pojď se mnou mluvit.

1881
01:21:32,250 --> 01:21:34,210
Jsem trochu blázen to
týden, ale slibuji,

1882
01:21:34,210 --> 01:21:36,340
Budu ještě odpovědět do 24 hodin.

1883
01:21:36,340 --> 01:21:38,240
Takže mají velký týden, všichni.

1884
01:21:38,240 --> 01:21:40,090
Hodně štěstí na vaší pset.

1885
01:21:40,090 --> 01:21:41,248