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

2
00:00:11,100 --> 00:00:12,300
>> SPEAKER 1: Hej vsem!

3
00:00:12,300 --> 00:00:13,890
Dobrodošli nazaj v oddelku.

4
00:00:13,890 --> 00:00:17,480
Tako vesel, da mnogi od vas, tako tu,
Vsak, ki je gledal na spletu.

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

6
00:00:18,760 --> 00:00:20,920
Torej, kot je običajno zadnji dobrodošlice.

7
00:00:20,920 --> 00:00:24,360
Upam, da ste vsi imeli lepo
vikend, poln počitka, sprostitve.

8
00:00:24,360 --> 00:00:26,026
Včeraj je bilo lepo ven.

9
00:00:26,026 --> 00:00:27,525
Torej, upam, da ste uživali na prostem.

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

11
00:00:28,840 --> 00:00:30,610
>> Torej, najprej nekaj objav.

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

13
00:00:31,920 --> 00:00:32,700
Razvrščanje.

14
00:00:32,700 --> 00:00:37,350
Torej, večina od vas bi bilo gotten
email mi o vašem Scratch Pset,

15
00:00:37,350 --> 00:00:39,920
kakor tudi za razvrščanje Pset 1.

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

17
00:00:41,000 --> 00:00:42,220
Torej, samo nekaj stvari.

18
00:00:42,220 --> 00:00:45,150
Bodite prepričani, da uporabite check50 v style50.

19
00:00:45,150 --> 00:00:47,250
Ti so mišljeni kot
sredstva za vaju,

20
00:00:47,250 --> 00:00:50,660
se prepričajte, da ste dobili
čim več točk, kot si lahko

21
00:00:50,660 --> 00:00:52,390
ne da bi jih po nepotrebnem izgubili.

22
00:00:52,390 --> 00:00:54,407
Torej, stvari, kot so stil
so zelo pomembni.

23
00:00:54,407 --> 00:00:55,740
Bomo vzlet za to.

24
00:00:55,740 --> 00:00:58,115
Nekateri od vas morda že
opazili, da iz vašega Pset.

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

26
00:00:58,920 --> 00:01:01,450
In check50 je le
zelo enostaven način, da se prepričajte,

27
00:01:01,450 --> 00:01:05,050
da smo dejansko vrača tisto, kar
treba vrne uporabniku,

28
00:01:05,050 --> 00:01:06,690
in da je vse, kar je pravilno.

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

30
00:01:08,690 --> 00:01:12,040
>> Na drugi note, poskrbite, da
nalaganje stvari v pravo mapo.

31
00:01:12,040 --> 00:01:14,470
To naredi življenje samo
malo težje

32
00:01:14,470 --> 00:01:18,836
če si naložite Pset 2 v Pset 1
ker ko sem prenesti stvari,

33
00:01:18,836 --> 00:01:20,085
ne prenesete pravilno.

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

35
00:01:21,690 --> 00:01:24,560
In vem, da je malo deformiranega
v sistemu, da se privadite,

36
00:01:24,560 --> 00:01:26,950
ampak je super
Pazite, čeprav samo za mene,

37
00:01:26,950 --> 00:01:30,080
tako da, ko ste dobili e-pošto
na podoben 02:00 in sem razvrščanje.

38
00:01:30,080 --> 00:01:33,710
Če ne povzroči moram pogledati
vsem za vašo Pset.

39
00:01:33,710 --> 00:01:34,440
Cool.

40
00:01:34,440 --> 00:01:37,270
>> Vem, da je prezgodaj, ampak sem
popolnoma si je vzletelo straže

41
00:01:37,270 --> 00:01:40,800
esej, ki je zaradi tega v petek, ta
moji profesorji so samo všeč, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Ne pozabite, da imate
esej zaradi petek.

43
00:01:42,550 --> 00:01:45,780
Torej, vem, da nihče ne mara
razmišljati o tem, kolokviji,

44
00:01:45,780 --> 00:01:50,620
vendar vaš prvi kviz je 15. oktobra
ki oktober se začenja ta teden.

45
00:01:50,620 --> 00:01:53,290
Torej, bi bilo prej
kot ste pričakovali, je vse.

46
00:01:53,290 --> 00:01:57,510
Tako da ne boš vrgla varovala, ko
Sem omenil, da je odsek naslednji teden oh,

47
00:01:57,510 --> 00:02:00,560
tvoj kviz naslednji teden, sem mislil,
Jaz bi dal malo več

48
00:02:00,560 --> 00:02:01,500
od glave gor zdaj.

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

50
00:02:02,970 --> 00:02:04,660
>> Torej, tvoj problem določiti, številka tri.

51
00:02:04,660 --> 00:02:07,070
Kako so ljudje berejo
spec iz radovednosti?

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
Imamo nekaj.

55
00:02:10,229 --> 00:02:12,320
Vrsta navzdol od zadnjega
teden, ampak to je v redu.

56
00:02:12,320 --> 00:02:13,650
Vem, da je bilo lepo ven.

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

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

59
00:02:16,660 --> 00:02:21,010
Definitivno ko boste dobili storiti
danes prebral vaše spec vsaj

60
00:02:21,010 --> 00:02:25,240
poskusite kot nalaganje
distribucija kodo in tek

61
00:02:25,240 --> 00:02:27,430
kot prva začetnica
stvar, da vas prosim, da.

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

63
00:02:28,681 --> 00:02:32,590
Saj smo z
distribucija kodo in knjižnica

64
00:02:32,590 --> 00:02:36,790
da smo šele using-- --It je samo
drugič smo naredili to Pset,

65
00:02:36,790 --> 00:02:38,650
nore stvari, se lahko zgodi,
z vašo napravo,

66
00:02:38,650 --> 00:02:41,370
in želite, da bi našli, da
ven proti kasneje.

67
00:02:41,370 --> 00:02:45,570
>> Ker če je v četrtek zvečer ali pa je
Sredo zvečer, in iz neznanega razloga

68
00:02:45,570 --> 00:02:48,912
vaša naprava samo ne
želite zagnati s knjižnico

69
00:02:48,912 --> 00:02:50,620
ali z distribucijo
Koda, da so sredstva

70
00:02:50,620 --> 00:02:52,309
ne moreš niti začeti početje kodiranje.

71
00:02:52,309 --> 00:02:54,100
Ker si ne more preveriti
da vidim, če deluje.

72
00:02:54,100 --> 00:02:55,975
Vaše ne bo lahko
da vidim, če se pripravlja.

73
00:02:55,975 --> 00:03:00,500
Želite, da bi poskrbeli za tiste, v začetku leta
teden, ko lahko še vedno mi email

74
00:03:00,500 --> 00:03:03,100
ali eden od drugih TF,
in bomo lahko dobili tiste fiksne.

75
00:03:03,100 --> 00:03:05,410
Zato, ker so to vprašanja
da vas bodo prenehali

76
00:03:05,410 --> 00:03:07,120
s kakršnimi koli resničen napredek.

77
00:03:07,120 --> 00:03:10,055
To ni všeč eno napako, da
lahko samo nekako preskočili.

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

79
00:03:10,712 --> 00:03:13,420
Če imate težave z vašim
aparat ali distribucijo kode,

80
00:03:13,420 --> 00:03:16,211
si res želite, da bi dobili, da sprejmejo
skrbi za raje prej kot kasneje.

81
00:03:16,211 --> 00:03:20,410
Torej, tudi če ne boš dejansko
začetek kodiranje, prenos distribucije

82
00:03:20,410 --> 00:03:24,040
koda, preberite spec, poskrbite,
vse, kar se tam delajo.

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

84
00:03:25,134 --> 00:03:27,675
Če lahko samo to, da sem
Obljubimo, vaše življenje bo lažje.

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

86
00:03:28,800 --> 00:03:31,410
In tako ste verjetno bo
da to storite zdaj prav?

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

88
00:03:32,100 --> 00:03:33,950
Torej, vsa vprašanja tam?

89
00:03:33,950 --> 00:03:35,850
Morebitne logistične stvari?

90
00:03:35,850 --> 00:03:36,910
Vsakdo je dobro?

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

92
00:03:38,270 --> 00:03:41,700
>> Disclaimer za tiste,
ste v prostoru in na spletu.

93
00:03:41,700 --> 00:03:45,437
Bom poskusila preklopiti
med PowerPoint v aparatu

94
00:03:45,437 --> 00:03:47,270
saj se bomo
biti delaš nekaj kodiranje

95
00:03:47,270 --> 00:03:53,630
danes popularen od anonimni
predlog ankete sem poslala prejšnji teden.

96
00:03:53,630 --> 00:03:55,480
Torej, bomo počeli nekaj kodiranja.

97
00:03:55,480 --> 00:03:57,800
Torej, če želite tudi vi
da ogenj vaše aparate,

98
00:03:57,800 --> 00:04:02,910
in ti naj bi dobili e-mail:
od mene, z datoteko vzorca.

99
00:04:02,910 --> 00:04:04,310
Vas prosimo, da to storim.

100
00:04:04,310 --> 00:04:07,340
>> Torej, bomo govorili o
GDB, ki je debugger.

101
00:04:07,340 --> 00:04:09,970
To se dogaja, da vam pomaga
nekako ugotoviti, kje

102
00:04:09,970 --> 00:04:11,860
stvari gredo narobe v kodi.

103
00:04:11,860 --> 00:04:15,370
To je res samo način za vas, da korak
s kodo, saj se dogaja,

104
00:04:15,370 --> 00:04:19,100
in lahko natisnete spremenljivk
ali vidite, kaj se dejansko dogaja

105
00:04:19,100 --> 00:04:22,980
pod kapuco prehladna svoj program
samo teče, to je kot izjalovljen,

106
00:04:22,980 --> 00:04:25,030
in ti si všeč, ne vem
kaj se je zgodilo tukaj.

107
00:04:25,030 --> 00:04:26,730
Ne vem, kaj linija je spodletelo.

108
00:04:26,730 --> 00:04:29,040
Ne vem, kje je šlo narobe.

109
00:04:29,040 --> 00:04:31,280
Torej, GDB se dogaja, da vam pomaga s tem.

110
00:04:31,280 --> 00:04:35,240
Tudi, če se boste odločili za
naprej ja, in sprejme 61,

111
00:04:35,240 --> 00:04:38,430
da bo res, res si
najboljši prijatelj, ker sem lahko vam povem,

112
00:04:38,430 --> 00:04:40,840
ker sem šel skozi ta razred.

113
00:04:40,840 --> 00:04:43,620
>> Bomo pogled na binarno
iskanje, ki bi, če vi spomnite

114
00:04:43,620 --> 00:04:47,540
Lep primer imenik
spektakel iz razreda.

115
00:04:47,540 --> 00:04:50,620
Mi bomo za izvajanje tega, in
hoja skozi to malo bolj,

116
00:04:50,620 --> 00:04:54,650
in potem gremo skozi štiri
različne vrste, ki so Bubble,

117
00:04:54,650 --> 00:04:56,285
Izbor, vstavljanja in Merge.

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

119
00:04:57,830 --> 00:04:58,330
Cool.

120
00:04:58,330 --> 00:05:00,390
Torej, GDB, kot sem že omenil, je razhroščevalnik.

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

122
00:05:01,400 --> 00:05:09,370
In ti so nekako big
stvari, velike funkcije ali ukaza

123
00:05:09,370 --> 00:05:13,240
ki jih uporabljate v GDB in bom hodil
ste preko demo njega v sekundi.

124
00:05:13,240 --> 00:05:15,360
>> Torej, to ni samo
bo ostal povzetek.

125
00:05:15,360 --> 00:05:18,000
Bom poskusil, in da bo, kot je beton
kot je mogoče za vas.

126
00:05:18,000 --> 00:05:19,870
Torej, prekinil.

127
00:05:19,870 --> 00:05:22,200
To bo bodisi odmor
kot so nekatere številke, ki

128
00:05:22,200 --> 00:05:26,900
predstavlja vrstico v vaš program,
ali lahko poimenujete funkcijo.

129
00:05:26,900 --> 00:05:30,150
Torej, če ste rekli, glavni odmor,
se bo ustavil na glavni,

130
00:05:30,150 --> 00:05:32,400
in vam sprehod skozi te funkcije.

131
00:05:32,400 --> 00:05:36,350
>> Prav tako, če imate nekaj zunanjega
deluje kot Swap ali Cube,

132
00:05:36,350 --> 00:05:38,450
da smo pogledal na zadnji teden.

133
00:05:38,450 --> 00:05:41,780
Če rečeš kršil eno od teh,
vsakič, ko vaš program hits, da

134
00:05:41,780 --> 00:05:44,290
da bom počakal, da
povej, kaj naj naredim.

135
00:05:44,290 --> 00:05:47,860
Preden se bo to šele izvajati tako, da vam
lahko dejansko korak znotraj funkcije

136
00:05:47,860 --> 00:05:49,020
in glej, kaj se dogaja.

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

138
00:05:50,370 --> 00:05:53,515
Torej, naslednjič, samo preskoči
naslednjo vrstico, gre čez funkcij.

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

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

141
00:05:55,560 --> 00:05:56,810
To so vsi malo abstraktna.

142
00:05:56,810 --> 00:06:00,530
Torej, jaz sem samo tekoč teči skozi njih,
vendar boste jih videli v uporabi na sekundo.

143
00:06:00,530 --> 00:06:01,810
>> Stopiti v funkcijo.

144
00:06:01,810 --> 00:06:04,170
Torej, kot sem rekel,
kot pri Swap, bi bilo

145
00:06:04,170 --> 00:06:07,110
vam omogočajo, da dejansko, kot če ste
kot fizično krepitev notranjosti,

146
00:06:07,110 --> 00:06:10,990
lahko igraš s temi spremenljivkami, print
izvedeti, kaj so, kaj se dogaja.

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

148
00:06:12,140 --> 00:06:14,830
Seznam bo dobesedno samo tiskanje
ven kodo obdaja.

149
00:06:14,830 --> 00:06:17,570
Torej, če ste nekako pozabil
kje ste v vašem programu,

150
00:06:17,570 --> 00:06:19,880
ali ste se spraševala,
kaj se dogaja okoli njega,

151
00:06:19,880 --> 00:06:23,790
bo to le izpisal segment
od rada pet ali šest linij okoli njega.

152
00:06:23,790 --> 00:06:26,080
Torej, lahko se orientirali
o tem, kje ste.

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

154
00:06:27,230 --> 00:06:28,650
>> Natisni kakšne spremenljivke.

155
00:06:28,650 --> 00:06:34,590
Torej, če imate ključ, kot
pri cesarju, da bomo pogledali.

156
00:06:34,590 --> 00:06:36,220
Lahko rečemo, Print ključ na kateri koli točki.

157
00:06:36,220 --> 00:06:40,070
To vam bo povedal, kaj je vrednost, tako
da, morda nekje na poti,

158
00:06:40,070 --> 00:06:42,070
ste prepisali ključ.

159
00:06:42,070 --> 00:06:45,495
Lahko dejansko povedal, da zato, ker
lahko dejansko opazuje te vrednosti.

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

161
00:06:46,500 --> 00:06:48,780
>> V domačini, samo odtise
iz vaših lokalnih spremenljivk.

162
00:06:48,780 --> 00:06:53,120
Torej, kadarkoli si v zanko,
in si želite videti podobno, oh.

163
00:06:53,120 --> 00:06:54,270
Kaj je moj jaz?

164
00:06:54,270 --> 00:06:57,020
Kaj je to ključna vrednota
da sem inicializacijo tukaj?

165
00:06:57,020 --> 00:06:58,537
Kaj je sporočilo v tem trenutku?

166
00:06:58,537 --> 00:07:00,370
Samo, da bo izpisal vse
tistih, tako da vas

167
00:07:00,370 --> 00:07:04,330
ne bi bilo treba posebej
pravijo, Print I. Natisni sporočilo.

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
In nato Prikaži.

171
00:07:07,700 --> 00:07:10,370
Kaj to pomeni je, kot ste
korak v okviru programa,

172
00:07:10,370 --> 00:07:13,980
da bomo samo poskrbite, da je
prikazovanje neke določene spremenljivke

173
00:07:13,980 --> 00:07:14,780
na vsaki točki.

174
00:07:14,780 --> 00:07:17,160
Tako da boste also-- --it je
nekakšna bližnjica kjer

175
00:07:17,160 --> 00:07:19,530
vam ni treba, da se dogaja podobno, oh.

176
00:07:19,530 --> 00:07:23,150
Print Key ali Print I. To samo
bo samodejno naredil za vas.

177
00:07:23,150 --> 00:07:25,959
>> Torej, s tem, da gremo
da vidim, kako to gre.

178
00:07:25,959 --> 00:07:28,000
Bom poskusil in stikalo
na mojo napravo.

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

180
00:07:30,200 --> 00:07:31,271
Vidim, če lahko to storite.

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

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

183
00:07:40,970 --> 00:07:42,370
Mi smo le, da bo to ogledalo.

184
00:07:42,370 --> 00:07:44,530
Nič ni nor
na moj laptop nekako.

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
Ta mora biti to ena.

189
00:08:01,054 --> 00:08:01,795
To je tako majhen.

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

191
00:08:03,730 --> 00:08:05,120
Poglejmo, če lahko to storimo.

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 je očitno borila
tukaj samo malo,

195
00:08:15,305 --> 00:08:17,995
ampak ga bomo dobili 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
Mi smo le, da bo to povečanje.

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
Lahko vsi nekako videli?

202
00:08:31,679 --> 00:08:32,470
Mogoče malo?

203
00:08:32,470 --> 00:08:33,594
Vem, da je malo majhen.

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

205
00:08:34,570 --> 00:08:37,530
Ne morete povsem ugotoviti,
kako se bo to večji.

206
00:08:37,530 --> 00:08:38,350
Če kdo ve.

207
00:08:38,350 --> 00:08:40,309
Ali kdo ve, kako bi bilo večje?

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

209
00:08:40,932 --> 00:08:42,140
Bomo roll z njo.

210
00:08:42,140 --> 00:08:45,801
Ni važno, nekako, ker je to samo
To je številka, ki naj bi vidva

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

212
00:08:46,300 --> 00:08:48,310
>> Kaj je bolj pomembno
Terminal je tukaj.

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

214
00:08:52,840 --> 00:08:58,690
In imamo tukaj Zakaj je tako majhna?

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

216
00:09:02,325 --> 00:09:02,825
Nastavitve.

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
True Ike.

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

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

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

223
00:09:19,370 --> 00:09:21,810
Je, da je bolje za vse?

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

225
00:09:22,525 --> 00:09:23,025
Cool.

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

227
00:09:25,830 --> 00:09:28,220
>> Saj veš, ko ste v CS
razred tehnične težave

228
00:09:28,220 --> 00:09:32,971
so nekako del the--
Torej, kaj je to jasno.

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

230
00:09:33,470 --> 00:09:38,060
Torej, tukaj v oddelku,
ki smo jih imeli tukaj.

231
00:09:38,060 --> 00:09:40,830
Cezar je izvršljiva datoteka.

232
00:09:40,830 --> 00:09:41,800
Tako da mi je uspelo.

233
00:09:41,800 --> 00:09:46,370
Torej, ena stvar, da se zavedaš, s GDB je
da lahko deluje samo na izvršljive datoteke.

234
00:09:46,370 --> 00:09:48,040
Torej, ne morete zagnati na dotsy.

235
00:09:48,040 --> 00:09:50,532
Moraš dejansko narediti
Prepričajte se, da vaša koda prevede,

236
00:09:50,532 --> 00:09:51,865
in da lahko dejansko treba izvesti.

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

238
00:09:52,970 --> 00:09:56,186
>> Torej, poskrbite, da če se to ne zgodi
zbere, mi ga je prevesti,

239
00:09:56,186 --> 00:09:57,810
tako da lahko nekako teče skozenj.

240
00:09:57,810 --> 00:10:04,590
Torej, za začetek GDB, vse, kar storite,
Gloria tip GDB, in potem samo

241
00:10:04,590 --> 00:10:06,250
datoteko, ki jo želite.

242
00:10:06,250 --> 00:10:08,240
Vedno sem misspell Cezarja.

243
00:10:08,240 --> 00:10:11,730
Vendar si želite zagotoviti
saj je to izvedljivo,

244
00:10:11,730 --> 00:10:14,210
TI je dot bliskavice, tako da
pomeni, da boš

245
00:10:14,210 --> 00:10:19,240
teči CSI boš izvršiti
To datotek bodisi s razhroščevalnik.

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

247
00:10:19,910 --> 00:10:22,885
Torej, vam, da boste dobili
ta vrsta žlobudranje.

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

249
00:10:24,250 --> 00:10:25,750
To je samo vse stvari o debugger.

250
00:10:25,750 --> 00:10:28,200
Nimate zares
skrbi zdaj.

251
00:10:28,200 --> 00:10:31,460
In kot vidite, smo to
odprte parens BDP, blizu parens,

252
00:10:31,460 --> 00:10:34,690
in samo nekako izgleda
naša ukazni vrstici, kajne?

253
00:10:34,690 --> 00:10:37,010
>> Torej, kaj želimo do--
--So, Prva stvar

254
00:10:37,010 --> 00:10:39,570
je, da smo želeli izbrati
mesto za odmor.

255
00:10:39,570 --> 00:10:42,332
Torej, obstaja en hrošč
v tem programu Caesar

256
00:10:42,332 --> 00:10:44,290
da se predstavim, da
bomo izvedeli.

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

258
00:10:45,330 --> 00:10:56,350
To, kar počne, je, da traja vnos
Barfoo v vseh kape, in iz neznanega razloga

259
00:10:56,350 --> 00:11:01,950
to ne spremeni A. To samo zapusti
sama, je vse ostalo pravilno,

260
00:11:01,950 --> 00:11:03,980
vendar druga črka
Ostane nespremenjena.

261
00:11:03,980 --> 00:11:07,120
Torej, bomo poskušali
ugotovimo, zakaj je tako.

262
00:11:07,120 --> 00:11:10,440
Torej, prva stvar, ki jo običajno
želite storiti, ko ste začeli na GDB

263
00:11:10,440 --> 00:11:12,010
je ugotoviti, kje bi ga zlomil.

264
00:11:12,010 --> 00:11:14,956
>> Torej Caesar je precej kratek program.

265
00:11:14,956 --> 00:11:16,330
Moramo le eno funkcijo, kajne?

266
00:11:16,330 --> 00:11:18,520
Kakšna je bila naša naloga v Cezarja?

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

268
00:11:19,590 --> 00:11:24,350
Obstaja samo ena funkcija, Main kajne?

269
00:11:24,350 --> 00:11:26,490
Prva je funkcija
za vse programe.

270
00:11:26,490 --> 00:11:29,230
Če niste imeli Main, bom morda
biti malo v skrbeh prav zdaj,

271
00:11:29,230 --> 00:11:31,000
vendar upam, da boste vsi imeli Main tam.

272
00:11:31,000 --> 00:11:34,150
Torej, kaj lahko storimo, je, da smo lahko
le prekinil Main, kar tako.

273
00:11:34,150 --> 00:11:35,190
Torej, pravi, OK.

274
00:11:35,190 --> 00:11:37,430
Smo Ustavljanje eno tam nastavljen.

275
00:11:37,430 --> 00:11:42,870
>> Torej, zdaj stvar za zapomniti je Caesar
traja eno ukazno vrstico argumenta pravice

276
00:11:42,870 --> 00:11:45,150
in nismo storili, da še nikjer.

277
00:11:45,150 --> 00:11:47,560
Torej, kaj morate storiti, je, ko
si dejansko šel za vožnjo

278
00:11:47,560 --> 00:11:51,540
programa, vsak program, ki ste
teče v GDB, da mora ukazno vrstico

279
00:11:51,540 --> 00:11:55,010
trditve, da boš vhod
ko ste prvič začeli prikazovati.

280
00:11:55,010 --> 00:11:59,280
Torej, v tem primeru delamo
Teči s ključem tri.

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

282
00:12:00,770 --> 00:12:02,040
In bo dejansko začel.

283
00:12:02,040 --> 00:12:08,480
>> Torej, če vidite, imamo
Če je Rc ni enaka 2.

284
00:12:08,480 --> 00:12:12,210
Torej, če imajo vsi fantje
da datoteka, ki sem poslala gor

285
00:12:12,210 --> 00:12:15,100
boste videli, da je to všeč
Prva vrstica je naša glavna naloga, kajne?

286
00:12:15,100 --> 00:12:17,890
To je preverjanje, da vidim, če imamo
pravilno število argumentov.

287
00:12:17,890 --> 00:12:20,620
Torej, če ste se spraševala,
če RC je pravilna,

288
00:12:20,620 --> 00:12:23,250
lahko narediš nekaj, kar tako Print RC.

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

290
00:12:24,380 --> 00:12:28,640
RC je dva, ki je
tisto, kar smo pričakovali, kajne?

291
00:12:28,640 --> 00:12:32,010
>> Torej, lahko gremo Naprej
in nadaljuje skozi.

292
00:12:32,010 --> 00:12:33,200
Torej, imamo nekaj ključ tam.

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

294
00:12:34,260 --> 00:12:37,090
In smo lahko natisnete svoj ključ
se prepričajte, da je pravilno.

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

296
00:12:38,380 --> 00:12:39,500
Zanimivo.

297
00:12:39,500 --> 00:12:41,210
Ne ravno to, kar smo pričakovali.

298
00:12:41,210 --> 00:12:44,810
Torej, ena stvar, za uresničitev
z GDB tudi, je

299
00:12:44,810 --> 00:12:49,000
da to ni, dokler ne boste dejansko hit
Dalje, da je linija, ki ste jo pravkar videli

300
00:12:49,000 --> 00:12:50,720
dejansko izvede.

301
00:12:50,720 --> 00:12:53,870
Torej, v tem primeru Key
še ni dodeljena.

302
00:12:53,870 --> 00:12:57,050
Torej, ključ je nekaj smeti vrednost
ki jih vidite na spodnji tam.

303
00:12:57,050 --> 00:13:03,680
Negativni $ 120-- --It je ena milijarda
in nekaj nenavadnega stvari, kajne?

304
00:13:03,680 --> 00:13:05,340
To ni ključ, da smo pričakovali.

305
00:13:05,340 --> 00:13:10,720
Ampak, če smo zadeli Naprej in nato smo
poskusite in tipka Print, to je tri.

306
00:13:10,720 --> 00:13:11,710
>> Vsi videli?

307
00:13:11,710 --> 00:13:13,780
Torej, če ste dobili nekaj
da ste kot, počakaj.

308
00:13:13,780 --> 00:13:15,540
To je popolnoma
narobe, in ne vem,

309
00:13:15,540 --> 00:13:20,150
kako bi se to zgodilo, ker si želim
storiti, je dodeliti številko, spremenljivka,

310
00:13:20,150 --> 00:13:22,900
poskusite hitting Naprej, poskusite tiskati
še enkrat, in videli, če to deluje.

311
00:13:22,900 --> 00:13:27,830
Saj je le, da bo za izvedbo in
dejansko dodeliti nekaj po vas

312
00:13:27,830 --> 00:13:29,340
hit Naprej.

313
00:13:29,340 --> 00:13:30,336
Smisla za vsakogar?

314
00:13:30,336 --> 00:13:30,836
Uh huh?

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Ko random
številke, kaj to pomeni?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: To je samo naključno.

317
00:13:34,790 --> 00:13:35,710
To je samo smeti.

318
00:13:35,710 --> 00:13:38,320
To je samo nekaj, da je vaš
Računalnik bo naključno dodeliti.

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

320
00:13:39,721 --> 00:13:40,220
Cool.

321
00:13:40,220 --> 00:13:45,760
Torej, zdaj lahko gremo skozi, in tako
Zdaj imamo to navaden tekst GetString.

322
00:13:45,760 --> 00:13:48,600
Torej, povej mi samo predstavim, kaj
se bo zgodilo, ko bomo zadeli Naprej tukaj.

323
00:13:48,600 --> 00:13:51,320
Naša GDB nekako izgine, kajne?

324
00:13:51,320 --> 00:13:55,720
To je zato, ker GetString
Zdaj izvršitve, kajne?

325
00:13:55,720 --> 00:14:01,460
Torej, ko smo videli golo besedilo je enako
GetString, odprte parens in parens,

326
00:14:01,460 --> 00:14:04,380
in smo zadeli Naprej, da ima
dejansko izvrši takoj.

327
00:14:04,380 --> 00:14:06,580
Torej, to je čakala
nam vhodni nekaj.

328
00:14:06,580 --> 00:14:13,560
>> Torej, gremo na vhod našo hrano, ki
je tisto, kar ga ni, kot sem ti rekel

329
00:14:13,560 --> 00:14:18,020
in da samo pravi, da je
končal izvršitve, da je zaprt

330
00:14:18,020 --> 00:14:19,980
Nosilec pomeni, da je
izhodu iz te zanke.

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

332
00:14:21,170 --> 00:14:25,420
Torej, lahko zadeti Next, in zdaj, ko sem
prepričajte, da ste vsi seznanjeni s Cezarjem,

333
00:14:25,420 --> 00:14:27,260
to je, kaj je to linija storili.

334
00:14:27,260 --> 00:14:32,030
To je za Int I enak 0, je n enak
Strlen, golo besedilo, in nato

335
00:14:32,030 --> 00:14:33,960
I je manjše od n, J, plus plus.

336
00:14:33,960 --> 00:14:35,210
Kaj je to zanka storili?

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

338
00:14:37,900 --> 00:14:39,160
Odprite sporočilo.

339
00:14:39,160 --> 00:14:39,770
Cool.

340
00:14:39,770 --> 00:14:41,330
Torej, začnimo s tem.

341
00:14:41,330 --> 00:14:47,210
>> Torej, če bi se ta pogoj
ujemajo, za naš prvi?

342
00:14:47,210 --> 00:14:52,250
Če je B, to je golo besedilo I. smo
lahko dobite informacije o naših domačinov.

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

344
00:14:53,610 --> 00:14:57,970
Torej, je nič, in če je šest, ki
pričakujemo, naša ključna je tri.

345
00:14:57,970 --> 00:14:59,227
Vse to smisla, kajne?

346
00:14:59,227 --> 00:15:01,310
Te številke so vse
točno to, kar bi moral biti.

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

348
00:15:02,590 --> 00:15:03,870
Torej, hum?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Imam
naključnih števil za rudnik.

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

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: No, lahko --we check--
lahko klepetate o tem v sekundi.

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

353
00:15:14,110 --> 00:15:15,750
Vendar bi morali biti že to.

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

355
00:15:17,700 --> 00:15:20,130
Torej, če imamo kapital
B za našo prvo,

356
00:15:20,130 --> 00:15:22,080
Ta pogoj naj bi ga ujeli, kajne?

357
00:15:22,080 --> 00:15:27,120
Torej, če smo zadeli Naprej, vidimo,
da to Če dejansko izvaja.

358
00:15:27,120 --> 00:15:29,220
Ker če ste po
skupaj v kodi,

359
00:15:29,220 --> 00:15:33,460
ta vrstica tu, kjer golo besedilo I
se nadomesti s tem aritmetike,

360
00:15:33,460 --> 00:15:35,720
izvaja samo, če, če
Pogoj je pravilno, kajne?

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

362
00:15:36,905 --> 00:15:40,240
>> GDB je samo še, da ti pokažem
stvari, ki so dejansko izvršitve.

363
00:15:40,240 --> 00:15:45,140
Torej, če je to Če pogoj ni bil izpolnjen, saj je
le, da bo preskok na naslednjo vrstico.

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

365
00:15:46,540 --> 00:15:48,510
Torej, imamo to.

366
00:15:48,510 --> 00:15:51,171
To pomeni, da je nosilec
dospel te zanke zdaj.

367
00:15:51,171 --> 00:15:52,420
Tako, da se bo ponovno zagnal.

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

369
00:15:54,760 --> 00:15:56,280
Kar tako.

370
00:15:56,280 --> 00:15:59,120
Tako, da bomo lahko dobili informacije
o naših domačini tukaj,

371
00:15:59,120 --> 00:16:02,575
in vidimo, da je naša prva
Pismo se je spremenilo, kajne?

372
00:16:02,575 --> 00:16:05,150
To je zdaj E, kot bi moralo biti.

373
00:16:05,150 --> 00:16:07,360
Torej, lahko nadaljujemo.

374
00:16:07,360 --> 00:16:08,500
>> In imamo ta pregled.

375
00:16:08,500 --> 00:16:09,916
In ta pregled je treba delati, kajne?

376
00:16:09,916 --> 00:16:12,570
Je A. Treba je spremeniti
tri črke naprej.

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

378
00:16:14,320 --> 00:16:16,530
Ampak, če ste opazili, smo
dobili nekaj drugačnega.

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

380
00:16:17,580 --> 00:16:22,860
Torej, v tem primeru tukaj, ujet
je, in zato je ta linija izvršen,

381
00:16:22,860 --> 00:16:28,620
ki je spremenila naše B.
Toda, v tem primeru tod

382
00:16:28,620 --> 00:16:32,860
moramo, da samo preskočila,
in odšel v [? L Siff. ?]

383
00:16:32,860 --> 00:16:34,660
Torej, kaj se dogaja tam.

384
00:16:34,660 --> 00:16:37,780
Tisto, kar je povedal, je, da
vemo, da mora ujeti tukaj,

385
00:16:37,780 --> 00:16:39,200
vendar to ni.

386
00:16:39,200 --> 00:16:42,210
Lahko vsakdo videti, kaj naše
Problem je v tem skladu?

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

388
00:16:45,380 --> 00:16:46,969
To je zelo minute stvar.

389
00:16:46,969 --> 00:16:48,510
In si lahko ogledate tudi na kodo.

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

391
00:16:49,980 --> 00:16:54,940
Prav tako je line-- pozabili, kaj linija je
v there-- vendar je v [neslišno].

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

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: Je na več kot
stran, če ga preberete v knjigi.

394
00:16:58,639 --> 00:16:59,430
SPEAKER 1: Točno tako.

395
00:16:59,430 --> 00:17:02,620
Torej, razhroščevalnik ni mogel povedati
vi, ampak razhroščevalnik

396
00:17:02,620 --> 00:17:05,880
ti lahko prinese do črte
da veste, ne deluje.

397
00:17:05,880 --> 00:17:09,319
In včasih, ko se še posebej
kasneje v semestru, ko

398
00:17:09,319 --> 00:17:12,910
imate opravka s sto, a
sto nekaj vrstic kode, in si

399
00:17:12,910 --> 00:17:16,190
Ne vem, kje je to ne,
To je odličen način, da to storite.

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

401
00:17:17,900 --> 00:17:18,989
Torej, smo našli našo napako.

402
00:17:18,989 --> 00:17:21,530
Lahko ga popraviti v datoteki,
in potem bi lahko znova teči,

403
00:17:21,530 --> 00:17:23,029
in vse, kar bi delovalo odlično.

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

405
00:17:24,970 --> 00:17:30,590
In največja stvar, ki je
To se lahko zdi kot, OK.

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

407
00:17:31,090 --> 00:17:31,370
Cool.

408
00:17:31,370 --> 00:17:32,744
Vedela si, kaj iščete.

409
00:17:32,744 --> 00:17:34,910
Torej, boste vedeli, kaj storiti.

410
00:17:34,910 --> 00:17:39,021
>> GDB lahko zelo koristno, saj vas
lahko natisnete vse te stvari, ki jih

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

412
00:17:39,520 --> 00:17:41,160
To je veliko bolj uporaben kot printf.

413
00:17:41,160 --> 00:17:43,440
Koliko ste uporabili
kot printf izjav

414
00:17:43,440 --> 00:17:46,200
da ugotovimo, kje je bila napaka, kajne?

415
00:17:46,200 --> 00:17:48,450
Torej, s tem ne boste
morajo voditi vrača,

416
00:17:48,450 --> 00:17:51,139
in rad komentiral v
Printf ali komentirate,

417
00:17:51,139 --> 00:17:52,930
in ugotoviti, kaj
si je treba tiskati.

418
00:17:52,930 --> 00:17:55,670
To vam omogoča, da dejansko samo
stopiti skozi izpiše stvari

419
00:17:55,670 --> 00:18:00,000
kot greš skozi, tako da, lahko
opazovati, kako se spreminjajo v realnem času,

420
00:18:00,000 --> 00:18:02,190
kot vaš program teče.

421
00:18:02,190 --> 00:18:04,390
>> In to ne traja malo
malo navaditi.

422
00:18:04,390 --> 00:18:07,850
Jaz bi zelo priporočam le nekako
, da so malo razočarani z njim

423
00:18:07,850 --> 00:18:08,930
Za zdaj.

424
00:18:08,930 --> 00:18:13,450
Če ste porabili eno uro pred
Naslednji teden učenje, kako uporabljati GDB,

425
00:18:13,450 --> 00:18:16,140
boste sami rešiti
toliko časa kasneje.

426
00:18:16,140 --> 00:18:18,750
In dobesedno. pripovedujemo
to, da ljudje vsako leto,

427
00:18:18,750 --> 00:18:23,890
in spomnim se, ko sem prevzel
razred, sem si mislil, bom v redu.

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

429
00:18:24,700 --> 00:18:27,030
Pset 6 vstopil in bil sem
podobno, bom naučiti

430
00:18:27,030 --> 00:18:29,500
kako uporabljati GDB, ker jaz ne
vedeti, kaj se dogaja tukaj.

431
00:18:29,500 --> 00:18:32,940
>> Torej, če ste vzeli čas, da
jo uporabite za manjše programe

432
00:18:32,940 --> 00:18:35,697
da si bo
delajo na, kot delajo

433
00:18:35,697 --> 00:18:37,530
skozi nekaj podobnega
Visionare, kot je ta.

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

435
00:18:38,800 --> 00:18:42,850
Ali če želite dodatne prakso, sem prepričan,
Lahko bi prišli do Otroški voziček programov,

436
00:18:42,850 --> 00:18:45,300
za vas, za odpravljanje napak, če želite.

437
00:18:45,300 --> 00:18:49,300
>> Ampak, če si vzemite nekaj časa, da bi dobili
uporabljajo za to, samo igral z njim,

438
00:18:49,300 --> 00:18:50,550
bo zares dobro služijo.

439
00:18:50,550 --> 00:18:52,591
In to je res ena izmed
tiste stvari, ki ste jo pravkar

440
00:18:52,591 --> 00:18:57,340
poskusiti in dobili vaše roke umazane
s, preden jo zares razumeli.

441
00:18:57,340 --> 00:19:02,090
Res sem razumel le enkrat
Moral sem debug stvari z njim,

442
00:19:02,090 --> 00:19:08,170
in to je veliko lepše, da imajo idejo
kako debug raje prej kot kasneje.

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

444
00:19:08,850 --> 00:19:09,625
Cool.

445
00:19:09,625 --> 00:19:12,960
Vem, da je nekako tako kot
Seveda crash v GDB,

446
00:19:12,960 --> 00:19:16,400
in vsekakor se bom delo na pridobivanje
ti, da si večji naslednjič.

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

448
00:19:17,590 --> 00:19:18,280
Cool.

449
00:19:18,280 --> 00:19:20,390
>> Torej, če se vrnemo k naši PowerPoint.

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

451
00:19:27,194 --> 00:19:28,110
Se bo to delovalo?

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

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

456
00:19:31,600 --> 00:19:35,480
Torej, če boste kdaj potrebovali katero koli
tistih, ki si ne bodo seznam.

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

458
00:19:37,160 --> 00:19:40,830
Torej Binary Search, ki vsi
zapomni velik spektakel Davidu

459
00:19:40,830 --> 00:19:42,259
Odličen imenikov na pol.

460
00:19:42,259 --> 00:19:44,050
Res ne dobijo
imenikov več,

461
00:19:44,050 --> 00:19:46,530
ker je tako kot kadar kajne
dobili telefonske knjige te dni?

462
00:19:46,530 --> 00:19:48,220
Res ne vem.

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

464
00:19:49,840 --> 00:19:50,590
Binary Search.

465
00:19:50,590 --> 00:19:52,464
Ali kdo spomnite
kako Binary iskanja dela?

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

467
00:19:54,380 --> 00:19:55,220
Kdo sploh?

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

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Veš, ko
pogledaš na katerem polčasu

470
00:19:58,283 --> 00:20:01,146
da bi bilo v, Na podlagi tega
in se znebite drugo polovico.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Točno.

472
00:20:01,896 --> 00:20:06,290
Torej, Binary Search, to je nekako a--
--we radi imenujemo razdeli in vladaj.

473
00:20:06,290 --> 00:20:09,170
Torej, kaj boste storili, je
boste videti v sredini,

474
00:20:09,170 --> 00:20:11,990
in boste videli, če se ujema
tisto, kar iščete.

475
00:20:11,990 --> 00:20:15,420
In če se to ne zgodi, potem poskusite
ugotoviti, se dogaja, da se levo

476
00:20:15,420 --> 00:20:16,450
pol ali desno polovico.

477
00:20:16,450 --> 00:20:19,325
Torej, to je lahko, če iščete
na nekaj, kar je po abecednem,

478
00:20:19,325 --> 00:20:20,720
vidite, oh.

479
00:20:20,720 --> 00:20:22,750
Ali Allison prišel pred M?

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

481
00:20:23,250 --> 00:20:25,030
Tako, da bomo
poglej prvi polovici.

482
00:20:25,030 --> 00:20:26,450
>> Ali bi bilo všeč, s številkami.

483
00:20:26,450 --> 00:20:28,830
Karkoli, da lahko
jih primerjati je mogoče sortirati.

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

485
00:20:29,920 --> 00:20:31,260
Lahko uporabite binarni iskanje na.

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

487
00:20:32,340 --> 00:20:37,455
Torej, ne pozabite, kdo je to
Graf ali kaj je to?

488
00:20:37,455 --> 00:20:39,520
To je asimptotska Complexity.

489
00:20:39,520 --> 00:20:42,830
Torej, ta graf samo
opisuje, kako dolgo

490
00:20:42,830 --> 00:20:46,230
vas popelje rešiti problem, kot
boste povečali število stvari

491
00:20:46,230 --> 00:20:47,090
ki ga uporabljate.

492
00:20:47,090 --> 00:20:51,260
>> Torej, imamo N, ki je linearni čas.

493
00:20:51,260 --> 00:20:54,560
Če je N čez dve, kar je nekoliko
bolje, še vedno raste zelo hitro.

494
00:20:54,560 --> 00:20:58,360
In potem smo se Prijava, ki je
kaj menimo Binarni iskanje.

495
00:20:58,360 --> 00:21:03,630
Če opazimo, kot je vaš problem
dobi toliko in toliko večje,

496
00:21:03,630 --> 00:21:06,600
Čas je vas popelje, da ga rešiti
v resnici ne poveča toliko.

497
00:21:06,600 --> 00:21:09,010
To je kot primerljiva
tu na začetku.

498
00:21:09,010 --> 00:21:10,060
Ti si kot, OK.

499
00:21:10,060 --> 00:21:13,000
Kaj tu v resnici ne
glede na to, katero bomo uporabili,

500
00:21:13,000 --> 00:21:16,220
vendar pa prideš ven na milijon, milijarda.

501
00:21:16,220 --> 00:21:20,010
Ste poskušali najti some-- --you're
poskuša najti iglo v senu.

502
00:21:20,010 --> 00:21:21,550
>> Mislim, da si želite to težavo.

503
00:21:21,550 --> 00:21:25,850
Hočeš to kompleksnost, ne
linearna, ker za vse vas

504
00:21:25,850 --> 00:21:30,049
poznate svoje bo treba iskati prek
vsak posameznik igla, stvar sena,

505
00:21:30,049 --> 00:21:31,340
poskušam si za svoj iglo.

506
00:21:31,340 --> 00:21:34,730
In to ni preveč zabavno, po mojem mnenju.

507
00:21:34,730 --> 00:21:35,500
Všeč mi je hitro.

508
00:21:35,500 --> 00:21:36,620
Všeč mi je učinkovita.

509
00:21:36,620 --> 00:21:40,450
In ti kot pridni učenci
fantje so, veš pametnejše delo,

510
00:21:40,450 --> 00:21:43,010
ne težje vrsta stvar, kako vas
lahko do teh algoritmov.

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

512
00:21:45,110 --> 00:21:47,910
>> Torej, gremo na sprehod
s samo hiter primer.

513
00:21:47,910 --> 00:21:51,090
Mislim, da fantje bi morali imeti
roko na Binary Search,

514
00:21:51,090 --> 00:21:54,352
vendar v primeru, kdo je malo
fuzzy, želijo, da ga okrepi,

515
00:21:54,352 --> 00:21:56,310
bomo pojdi
skozi primer tukaj.

516
00:21:56,310 --> 00:21:59,490
Torej, iščemo, če
Niz vsebuje sedem.

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

518
00:22:00,540 --> 00:22:06,010
>> Torej, prva stvar, ki mi je
poglej v sredini, kajne?

519
00:22:06,010 --> 00:22:09,340
In tudi boš se kodiranje
Binarno iskanje v samo sekundo.

520
00:22:09,340 --> 00:22:11,310
Torej, to bo zabavno.

521
00:22:11,310 --> 00:22:13,710
Torej gledamo v
srednji mali nizi 3.

522
00:22:13,710 --> 00:22:15,501
Ali 3 enaka 7?

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

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

525
00:22:18,670 --> 00:22:19,550
To je šest.

526
00:22:19,550 --> 00:22:21,480
Torej, je to manj kot
ali več kot sedem?

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

528
00:22:23,080 --> 00:22:23,960
Manj kot.

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

530
00:22:24,570 --> 00:22:25,170
Lepi fantje zaposlitve.

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

532
00:22:25,569 --> 00:22:27,360
Čutim, rad bi jaz
imajo sladkarije, ker sem

533
00:22:27,360 --> 00:22:29,460
želeli, da ga vrgel ven ladjedelnic.

534
00:22:29,460 --> 00:22:30,270
To je tisto, kar bom naredil naslednji teden.

535
00:22:30,270 --> 00:22:31,436
To vas bo fantje ostra.

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

537
00:22:32,560 --> 00:22:34,690
>> Torej, vržemo proč, da
Prva polovica, kajne?

538
00:22:34,690 --> 00:22:35,670
to je manj kot.

539
00:22:35,670 --> 00:22:39,325
vemo, da je vse
na tej levi strani

540
00:22:39,325 --> 00:22:41,700
se dogaja, da je manj od tistega, kar
smo dejansko iščejo.

541
00:22:41,700 --> 00:22:43,491
Torej, ni potrebe, da
bodite pozorni na to.

542
00:22:43,491 --> 00:22:45,120
Samo pozabi.

543
00:22:45,120 --> 00:22:48,720
Torej, zdaj gledamo na naši desni strani,
in gledamo na sredini tam,

544
00:22:48,720 --> 00:22:50,510
in zdaj je devet.

545
00:22:50,510 --> 00:22:55,510
Torej, 9 is-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Večji od tistega, kar smo
iskal, kajne?

547
00:22:57,470 --> 00:22:59,860
Torej, gremo, da mečejo
stran vse na desni.

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

549
00:23:00,970 --> 00:23:01,940
Kot je ta.

550
00:23:01,940 --> 00:23:03,700
Zdaj ste vsi smo odšli z eno.

551
00:23:03,700 --> 00:23:07,760
Torej smo preveriti, ali je to ena, kar
iščemo? je.

552
00:23:07,760 --> 00:23:08,970
Ugotovili smo, kar smo želeli.

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

554
00:23:10,440 --> 00:23:11,690
Tako da smo storili.

555
00:23:11,690 --> 00:23:12,550
Bilineamo Search.

556
00:23:12,550 --> 00:23:15,740
>> In, če ste opazili, smo
imel sedem vhodov tam.

557
00:23:15,740 --> 00:23:24,320
To nam je všeč samo trikrat,
ampak če delaš kot milijardo,

558
00:23:24,320 --> 00:23:28,190
veste, koliko korakov je bi
da, če bi imeli štiri milijarde stvari?

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

560
00:23:29,940 --> 00:23:30,455
Kakršne koli ugibanja?

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

562
00:23:32,286 --> 00:23:33,960
To je 32.

563
00:23:33,960 --> 00:23:37,110
32 korakov, da bi našli nekaj,
v štiri milijarde

564
00:23:37,110 --> 00:23:39,650
element matrike zaradi pristojnosti dveh.

565
00:23:39,650 --> 00:23:43,550
Torej, dva je 32, je na štiri milijarde.

566
00:23:43,550 --> 00:23:50,430
>> Torej, precej noro, kako ste še vedno v
kot dokaj majhno število korakov

567
00:23:50,430 --> 00:23:52,650
najti nekaj v
štiri milijarde elementi.

568
00:23:52,650 --> 00:23:55,730
Torej na to opombo, da smo
bo to kodo

569
00:23:55,730 --> 00:23:58,950
tako da fantje lahko dejansko
nekako videli, kako to deluje.

570
00:23:58,950 --> 00:24:01,520
Vse je v redu, tako da lahko vidva kodo.

571
00:24:01,520 --> 00:24:04,100
Bom vama pustil
govori malo.

572
00:24:04,100 --> 00:24:07,970
Spoznajte ljudi okoli vas, ki je
kaj nekdo želel iz zadnjega poglavja.

573
00:24:07,970 --> 00:24:10,280
>> Tako spoznajo ljudi okoli vas.

574
00:24:10,280 --> 00:24:11,305
Govori malo.

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

576
00:24:12,580 --> 00:24:15,730
In vse, kar želim od tebe
fantje, zdaj je le

577
00:24:15,730 --> 00:24:17,575
poskušajo ustvariti oris psevdokoda.

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

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

582
00:24:23,320 --> 00:24:29,520
Vse, kar želim od vaju je, da ste
le, da bo izpolnjevanje tega while primeru.

583
00:24:29,520 --> 00:24:32,170
Zato sem te določijo zgornjo
in spodnje meje, ki

584
00:24:32,170 --> 00:24:35,250
predstavlja začetek
in konec našega array.

585
00:24:35,250 --> 00:24:40,440
In boste dejansko
zanko skozi in ugotovimo,

586
00:24:40,440 --> 00:24:42,470
kaj delamo v tem while.

587
00:24:42,470 --> 00:24:45,810
>> Torej, če lahko ugotovimo out-- imam
namig there-- kaj so primeri

588
00:24:45,810 --> 00:24:46,640
da imamo tukaj?

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

590
00:24:48,100 --> 00:24:51,560
Torej, če želite, da ugotovimo,
primeri, bomo psevdokoda tiste

591
00:24:51,560 --> 00:24:53,350
in potem bomo jih dejansko kodo.

592
00:24:53,350 --> 00:24:55,330
In to se dogaja, da sem
mislim, upam, da bom

593
00:24:55,330 --> 00:24:56,788
je malo lažje, kot ste pričakovali.

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

595
00:24:57,554 --> 00:25:00,220
Ker to ni, da je veliko kode,
pravzaprav, ki je res kul.

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
>> ŠTUDENT: [neslišno]?

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

600
00:25:36,984 --> 00:25:37,650
Inštruktor: Da.

601
00:25:37,650 --> 00:25:38,595
Nekaj ​​je bilo
najti v sredini.

602
00:25:38,595 --> 00:25:39,552
>> ŠTUDENT: Tako smo lahko uporabite.

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

604
00:25:39,770 --> 00:25:40,603
>> Inštruktor: Popolna.

605
00:25:40,603 --> 00:25:42,950
Tako da je prva stvar, ki jo morate storiti.

606
00:25:42,950 --> 00:25:44,330
Torej, najti sredino.

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

608
00:25:45,415 --> 00:25:45,915
Super.

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

610
00:25:47,770 --> 00:25:55,010
Torej imaš idejo, kako bi lahko
dejansko našli na sredini s kodo?

611
00:25:55,010 --> 00:25:55,980
>> ŠTUDENT: Ja.

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
Inštruktor: Torej n čez 2.

615
00:25:59,500 --> 00:26:05,170
Torej, ena stvar, da se spomnimo, da
vaše zgornje in spodnje meje spremenijo.

616
00:26:05,170 --> 00:26:08,110
Hranimo plitvih del
array iščemo za.

617
00:26:08,110 --> 00:26:11,970
Torej n več kot 2 deluje samo
za prvo stvar naredimo.

618
00:26:11,970 --> 00:26:17,810
Torej pokazal zgornje in spodnje upoštevati,
kako bi lahko dobili, da je srednji element?

619
00:26:17,810 --> 00:26:20,640
Ker želimo, da na sredini
med zgornjim in spodnjim, kajne?

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
>> ŠTUDENT: [neslišno].

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

624
00:26:26,170 --> 00:26:28,080
>> Inštruktor: Torej, imamo nekaj sredini.

625
00:26:28,080 --> 00:26:32,730
In to bo zgornja plus nižja več kot 2.

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

627
00:26:34,740 --> 00:26:35,690
Super.

628
00:26:35,690 --> 00:26:36,570
Tam gremo.

629
00:26:36,570 --> 00:26:37,280
Ena linija navzdol.

630
00:26:37,280 --> 00:26:38,560
Vi ste na vaši poti.

631
00:26:38,560 --> 00:26:41,400
Torej sedaj, da imamo
srednji, kaj želimo narediti?

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

633
00:26:45,050 --> 00:26:45,900
Samo na splošno.

634
00:26:45,900 --> 00:26:47,734
Nimate za to kodo.

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

636
00:26:48,335 --> 00:26:49,210
ŠTUDENT: [neslišno]?

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

638
00:27:00,310 --> 00:27:10,310
Inštruktor: Torej, to je plus, ker ste
iskanje povprečje med dvema

639
00:27:10,310 --> 00:27:10,810
od njih.

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

641
00:27:11,890 --> 00:27:17,370
Torej, če mislite o njih, kot neke vrste
povečanja od strani,

642
00:27:17,370 --> 00:27:21,640
razmišljati o tem, ko se približate
srednji, hočeš tako.

643
00:27:21,640 --> 00:27:27,150
Torej, če ste bili na obeh straneh
srednji in imamo kot 5 in 7.

644
00:27:27,150 --> 00:27:31,440
Ko jih dodate skupaj vas
dobili 12, delite z 2, je 6.

645
00:27:31,440 --> 00:27:33,726
>> Včasih je težko
pojasniti, zakaj to deluje,

646
00:27:33,726 --> 00:27:35,600
vendar če delate z
Primer včasih,

647
00:27:35,600 --> 00:27:37,962
da bomo vam pomaga ugotoviti, če
bi moral biti plus ali minus.

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

649
00:27:38,846 --> 00:27:40,830
>> ŠTUDENT: [neslišno]
točno v sredini

650
00:27:40,830 --> 00:27:43,950
če so imeli primer, ko je
tam je veliko manjših številk

651
00:27:43,950 --> 00:27:45,860
in kot enega velikega števila?

652
00:27:45,860 --> 00:27:49,750
>> Inštruktor: Torej, vse, kar potrebujete
je sredi polja.

653
00:27:49,750 --> 00:27:53,010
Torej, če ste imeli kup majhnih številkah
nato pa eno res veliko število

654
00:27:53,010 --> 00:27:54,799
na koncu, to ni važno.

655
00:27:54,799 --> 00:27:56,840
Vse, kar je pomembno, je, da
oni so razporejene, ki ste jo pravkar

656
00:27:56,840 --> 00:27:59,339
želeli videti na sredini
matrika, ker ste še vedno

657
00:27:59,339 --> 00:28:00,700
rezanjem vaš problem na pol.

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

659
00:28:03,020 --> 00:28:03,680
Cool.

660
00:28:03,680 --> 00:28:06,430
Torej, zdaj, ko imamo
srednji, kaj bomo zdaj?

661
00:28:06,430 --> 00:28:07,150
>> ŠTUDENT: Primerjaj.

662
00:28:07,150 --> 00:28:08,150
Inštruktor: primerjati.

663
00:28:08,150 --> 00:28:11,670
Torej primerjati sredini value_wanted.

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

665
00:28:14,300 --> 00:28:15,160
Cool.

666
00:28:15,160 --> 00:28:17,950
Torej vidite tukaj imamo
ta vrednost želimo tu gor.

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

668
00:28:22,012 --> 00:28:23,095
Ne pozabite, to je matrika.

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

670
00:28:24,100 --> 00:28:26,970
Torej srednji nanaša na indeks.

671
00:28:26,970 --> 00:28:29,785
Zato smo želeli narediti vrednosti sredini.

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

673
00:28:32,380 --> 00:28:35,650
Ne pozabite, če želite
Za primerjavo, dvojne enaka.

674
00:28:35,650 --> 00:28:38,250
Vam single enaka ste
le, da bo to znova dodeliti,

675
00:28:38,250 --> 00:28:41,090
in nato, seveda, to je
bo vrednost, ki jo želite.

676
00:28:41,090 --> 00:28:42,300
Torej, ne počni tega.

677
00:28:42,300 --> 00:28:44,350
>> Tako da bomo videli, če
vrednosti pri sredini

678
00:28:44,350 --> 00:28:46,460
je enaka vrednosti, ki jo želimo.

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

680
00:28:47,749 --> 00:28:48,790
Ne pozabite na svoje naramnice.

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

682
00:28:50,520 --> 00:28:52,235
Dropbox moral oditi.

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

684
00:28:54,140 --> 00:28:56,200
Torej, kaj bomo naredili v tem primeru?

685
00:28:56,200 --> 00:28:59,360
Če je to tisto, kar si želimo, da se vrnete?

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

687
00:29:01,510 --> 00:29:02,626
Poskušamo povedati.

688
00:29:02,626 --> 00:29:03,440
>> ŠTUDENT: Natisni off.

689
00:29:03,440 --> 00:29:05,314
>> Inštruktor: No,
ne želite natisniti off.

690
00:29:05,314 --> 00:29:08,220
Torej je to bool tukaj, zato smo
želite vrniti true ali false.

691
00:29:08,220 --> 00:29:12,280
Mi pravite, je ta številka
[? RRA? ?] Torej, če je,

692
00:29:12,280 --> 00:29:13,788
smo pravkar vrnil res.

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

694
00:29:16,780 --> 00:29:17,760
Če bom lahko črkovati res.

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

696
00:29:18,830 --> 00:29:20,805
>> ŠTUDENT: Zakaj ne bi vrnil nič?

697
00:29:20,805 --> 00:29:22,930
Inštruktor: Torej si lahko
vrne nič, če si hotel.

698
00:29:22,930 --> 00:29:26,780
Toda v tem primeru zato, ker
naša funkcija vrne bool,

699
00:29:26,780 --> 00:29:28,962
moramo vrniti bodisi resnična ali neresnična.

700
00:29:28,962 --> 00:29:30,920
UČENEC: Ko ste
rekoč boolean izraz,

701
00:29:30,920 --> 00:29:33,450
jo lahko nastavite enak false?

702
00:29:33,450 --> 00:29:39,860
Všeč mi je, če sem hotel povedati, če je ta pogoj
ni izpolnjen, kot je zgornja enaka false.

703
00:29:39,860 --> 00:29:42,332
Bo razumel, če si
čaka false na drugi strani?

704
00:29:42,332 --> 00:29:43,040
Inštruktor: Ja.

705
00:29:43,040 --> 00:29:44,820
Torej, dejansko, če ste
kdaj delaš nekaj

706
00:29:44,820 --> 00:29:49,600
kot je zgornja ali spodnja,
ki vrne true ali false

707
00:29:49,600 --> 00:29:53,850
in to je pravzaprav slaba slog
recimo enaka enaka true ali enaka

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

709
00:29:54,840 --> 00:30:00,210
Želite uporabiti tega rezultata
kot je sama kot ček.

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

711
00:30:04,720 --> 00:30:05,860
Ni tisto, kar sem želel.

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

713
00:30:08,150 --> 00:30:09,240
To je tisto, kar sem želel.

714
00:30:09,240 --> 00:30:13,205
Torej, v primeru, da ste prosi
o nečem, kot je ta prihranek v c.

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

716
00:30:16,320 --> 00:30:25,150
>> Torej, če imamo int main (praznino),
in kaj takega.

717
00:30:25,150 --> 00:30:31,922
In imate, če je zgornja
nekaterih vhodnih in ste

718
00:30:31,922 --> 00:30:33,630
sprašuje, če lahko to storite
kaj takega?

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

720
00:30:35,010 --> 00:30:35,679
Kajne?

721
00:30:35,679 --> 00:30:37,470
ŠTUDENT: Poskušal sem
da to storite [neslišno].

722
00:30:37,470 --> 00:30:38,450
Ker če it's--

723
00:30:38,450 --> 00:30:39,200
Inštruktor: Right.

724
00:30:39,200 --> 00:30:41,197
Torej hočeš, da je to napačna, kajne?

725
00:30:41,197 --> 00:30:41,780
ŠTUDENT: Ja.

726
00:30:41,780 --> 00:30:45,960
Inštruktor: Torej, v tem primeru
želite, da se izvrši, če to ni res.

727
00:30:45,960 --> 00:30:50,510
Tako kul stvar, ki vam je to.

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

729
00:30:52,900 --> 00:30:55,650
Torej, ne pozabite vzklik
točka zanika stvari?

730
00:30:55,650 --> 00:30:58,270
Piše [neslišno] ne pomeni.

731
00:30:58,270 --> 00:31:03,590
Torej, če pogledamo samo
ta del tukaj, ki ste jo

732
00:31:03,590 --> 00:31:05,740
pravijo, da ocenjuje, da
false, kot ste želeli.

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

734
00:31:06,790 --> 00:31:09,880
Ni napačna je res, ki
pomeni, bi to izvesti.

735
00:31:09,880 --> 00:31:11,037
Ali to smiselno?

736
00:31:11,037 --> 00:31:11,620
ŠTUDENT: Ja.

737
00:31:11,620 --> 00:31:12,453
Inštruktor: Awesome.

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
Tako da smo lahko samo vrnitev
velja v tem primeru.

741
00:31:16,330 --> 00:31:20,357
Torej, zdaj imamo dva druga
primeri, v tem primeru.

742
00:31:20,357 --> 00:31:21,565
Kaj sta dve naši drugi primeri?

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

744
00:31:31,610 --> 00:31:32,900
Recimo, da na ta način pač.

745
00:31:32,900 --> 00:31:40,660
Torej začnimo z drugo
če vrednosti na sredini

746
00:31:40,660 --> 00:31:43,230
je nižja od vrednosti, ki jo želimo.

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

748
00:31:47,200 --> 00:31:52,020
Torej, naša vrednost v sredini je manj
od vrednosti, ki jih iščete.

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

750
00:31:53,765 --> 00:31:56,720
>> Torej, ki veže kajne
mislim, da želite posodobiti?

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

752
00:31:57,870 --> 00:31:58,780
Zgornji ali spodnji?

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

754
00:32:01,440 --> 00:32:01,940
Zgornji?

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

756
00:32:03,230 --> 00:32:06,470
Torej, na kateri strani polja
bomo se gledaš?

757
00:32:06,470 --> 00:32:07,500
>> ŠTUDENT: nižja.

758
00:32:07,500 --> 00:32:09,750
>> Inštruktor: Mi gremo
da je treba videti na levi strani.

759
00:32:09,750 --> 00:32:11,120
Torej, če je še majhna vrednost manj.

760
00:32:11,120 --> 00:32:14,730
Torej srednjo vrednostjo tukaj
je manj od tistega, kar si želimo.

761
00:32:14,730 --> 00:32:17,202
Zato želimo, da bi
desna stran našega array.

762
00:32:17,202 --> 00:32:18,910
Tako bomo
posodobiti naš spodnja meja.

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

764
00:32:20,210 --> 00:32:23,020
Torej bomo dodelite naše nižje.

765
00:32:23,020 --> 00:32:25,221
In kaj misliš, da bi morale biti nižje?

766
00:32:25,221 --> 00:32:26,304
ŠTUDENT: srednja vrednost?

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

768
00:32:27,446 --> 00:32:28,820
Inštruktor: Torej srednji value--

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

770
00:32:30,136 --> 00:32:31,010
Inštruktor: --plus 1.

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

772
00:32:32,300 --> 00:32:34,380
Mi lahko kdo pove, zakaj
moramo, da je plus 1?

773
00:32:34,380 --> 00:32:35,730
>> ŠTUDENT: [? No vrednost?]
je bolj enaka njo.

774
00:32:35,730 --> 00:32:36,120
>> Inštruktor: Right.

775
00:32:36,120 --> 00:32:38,661
Saj že vemo, da
naša srednja vrednost ni enaka

776
00:32:38,661 --> 00:32:42,750
je in želimo, da ga izključijo
od vseh nadaljnjih iskanj.

777
00:32:42,750 --> 00:32:46,360
Če ste pozabili, da je plus 1, to
bo všeč zanke za nedoločen čas.

778
00:32:46,360 --> 00:32:49,620
In boste le ujeta v
neskončna zanka in potem boste segfault

779
00:32:49,620 --> 00:32:50,370
in gredo stvari slabo.

780
00:32:50,370 --> 00:32:54,780
Zato vedno poskrbite, da niste
vključno z vrednostjo, ki ste jo pravkar

781
00:32:54,780 --> 00:32:55,380
pogledal.

782
00:32:55,380 --> 00:32:58,530
Tako smo poskrbeli, da je pri plus 1.

783
00:32:58,530 --> 00:33:04,840
>> Torej, zdaj imamo zadnje stanje
ki sem vedno za varnost zaradi

784
00:33:04,840 --> 00:33:12,664
si lahko ogledate tukaj, else if vrednost na
srednji je večja od vrednosti

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

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

787
00:33:16,260 --> 00:33:20,230
To pomeni, da želimo
levo polovico roke.

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

789
00:33:21,350 --> 00:33:23,260
Torej, katero bomo posodobiti?

790
00:33:23,260 --> 00:33:23,760
Zgornji del.

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

792
00:33:25,470 --> 00:33:26,970
In kaj je to ena bo enaka?

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

794
00:33:31,630 --> 00:33:33,690
Bližnji minus 1, ker
Seveda, želimo

795
00:33:33,690 --> 00:33:38,370
se prepričajte, da nismo
videti spet na tej srednji vrednosti.

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

797
00:33:41,830 --> 00:33:45,110
In potem smo jo imeli.

798
00:33:45,110 --> 00:33:45,610
To je to.

799
00:33:45,610 --> 00:33:46,820
To je vse, binarno iskanje je.

800
00:33:46,820 --> 00:33:48,190
To ni tako slabo, kajne?

801
00:33:48,190 --> 00:33:51,590
To je kot 10 vrstic
koda z belim prostorom.

802
00:33:51,590 --> 00:33:57,510
Tako zelo močan, zelo uporaben, boste
lahko ga uporabite v enem od svojih poznejših psets.

803
00:33:57,510 --> 00:33:59,360
Morda tega ne enega, ampak kasneje.

804
00:33:59,360 --> 00:34:00,670
Tako da se ga učijo.

805
00:34:00,670 --> 00:34:01,510
Je všeč.

806
00:34:01,510 --> 00:34:02,980
To vam bo zdravljenje dobro.

807
00:34:02,980 --> 00:34:05,370
Torej, ali ima kdo koli
Vprašanja o binarnem iskanju?

808
00:34:05,370 --> 00:34:06,196
Da.

809
00:34:06,196 --> 00:34:09,840
>> ŠTUDENT: Ali je pomembno
ali je vaš n celo ali liho?

810
00:34:09,840 --> 00:34:10,750
>> Inštruktor: No.

811
00:34:10,750 --> 00:34:18,150
Ker smo ga odda v sredini kot
int, bo to samo skrajšajte.

812
00:34:18,150 --> 00:34:21,600
Torej bo ostal celo in bo
sčasoma razvrstite skozi vse.

813
00:34:21,600 --> 00:34:23,909
Torej vam ni treba skrbeti za to.

814
00:34:23,909 --> 00:34:24,580
Vsi dobro?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Super.

817
00:34:26,850 --> 00:34:27,919
Cool.

818
00:34:27,919 --> 00:34:30,836
Torej, fantje to dobil.

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
Torej, kot smo govorili, vem
David omenjeno kompleksnost runtimes.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Torej v najboljšem primeru, to je samo
ena, ki jo imenujemo konstantno časa.

825
00:34:50,340 --> 00:34:51,909
Mi lahko kdo pove, zakaj bi lahko bilo?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Katera vrsta scenarija bi to pomenilo?

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
>> ŠTUDENT: [neslišno] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
Inštruktor: Torej, srednji pa
Prvi element, ki smo prišli, kajne?

833
00:35:03,830 --> 00:35:08,167
Torej bodisi niz enega ali
vse, kar smo iskali le

834
00:35:08,167 --> 00:35:09,750
zgodi, da se zadah dab na sredini.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Tako da je naša najboljša primera.

837
00:35:13,380 --> 00:35:17,540
Boste dobili v dejanskih težav, verjetno ne
bo dosegel [neslišno], ki se pogosto.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Kaj pa naši najslabšem primeru?

840
00:35:19,750 --> 00:35:21,270
Naša najslabšem primeru je log n.

841
00:35:21,270 --> 00:35:25,360
In da ima opraviti s celotnim
Pooblastila dveh stvari, ki sem govoril.

842
00:35:25,360 --> 00:35:30,930
>> Torej, v najslabšem primeru bi to pomenilo,
da smo imeli za sekanje array navzdol

843
00:35:30,930 --> 00:35:33,270
dokler ni bil element enega.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Tako da smo morali sekanje dol na pol
tolikokrat, kot vam morebiti lahko.

846
00:35:38,930 --> 00:35:41,430
To je razlog, zakaj je log n, ker
si kar naprej delimo z dve.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Torej predpostavke, stvari, ki jih
morate vedeti, če ste kdaj

849
00:35:45,830 --> 00:35:48,050
boste uporabljali binarno iskanje.

850
00:35:48,050 --> 00:35:50,680
Vaši elementi morajo biti razporejene.

851
00:35:50,680 --> 00:35:53,890
Jih je treba sortirati, ker
To je edini način, boste

852
00:35:53,890 --> 00:35:57,060
more vedeti, če ste sposobni
vrgel ven polovico tega.

853
00:35:57,060 --> 00:36:00,260
>> Če ste imeli ta zamotana vrečko
številk in praviš,

854
00:36:00,260 --> 00:36:05,380
OK, grem preveriti na sredini
številka in številka iščem

855
00:36:05,380 --> 00:36:08,510
je manj kot to, da sem le, da bo
samovoljno vrgel ven polovico.

856
00:36:08,510 --> 00:36:11,130
Saj ne bi vedeli, če je vaš
Številke v tej drugi polovici.

857
00:36:11,130 --> 00:36:12,655
Vaš seznam je treba sortirati.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Kot je dobro, je to lahko
gre naprej malo,

860
00:36:16,560 --> 00:36:18,360
vendar morate imeti izbirni dostop.

861
00:36:18,360 --> 00:36:21,940
Moraš biti sposoben samo
pojdite na ta srednji element.

862
00:36:21,940 --> 00:36:25,110
Če imate za prečkanje
skozi nekaj

863
00:36:25,110 --> 00:36:28,630
ali je potrebno, vam dodatne ukrepe
priti do tega srednjega elementa,

864
00:36:28,630 --> 00:36:31,750
to ni več, ker se prijavite n
ste dodali več dela v njej.

865
00:36:31,750 --> 00:36:34,800
In bo to malo
bolj občutek v dveh tednih,

866
00:36:34,800 --> 00:36:37,950
vendar sem nekako želel predgovor,
vidva dala idejo o tem, kaj je

867
00:36:37,950 --> 00:36:38,999
da pridejo.

868
00:36:38,999 --> 00:36:40,790
Ampak to so dva
Pomembnejše predpostavke

869
00:36:40,790 --> 00:36:44,804
da morate za binarne seznama.

870
00:36:44,804 --> 00:36:45,720
Prepričajte se, da je urejeno.

871
00:36:45,720 --> 00:36:47,920
To je ena velika za
vi zdaj.

872
00:36:47,920 --> 00:36:52,170
In da lahko gremo v
Preostali del naših vrst.

873
00:36:52,170 --> 00:36:56,444
Torej štiri sorts-- mehurček,
vstavljanje, izbor in spajanje.

874
00:36:56,444 --> 00:36:57,485
Oni so vsi nekako kul.

875
00:36:57,485 --> 00:37:02,860
Če vi odločite za CS 124,
boste izvedeli vse o vseh mogočih vrst.

876
00:37:02,860 --> 00:37:07,575
In če ste za xkcd ventilator, tam
je res kul strip o

877
00:37:07,575 --> 00:37:11,530
kot je v resnici neučinkovitih vrst, ki sem jih
Priporočam vam bo gledati.

878
00:37:11,530 --> 00:37:16,170
Eden od njih je, kot panično vrste, ki
je všeč, oh ne, vrne naključno array.

879
00:37:16,170 --> 00:37:16,991
Zaustavitev sistema.

880
00:37:16,991 --> 00:37:17,490
Zapusti.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Tako geeky humor je vedno dobro.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Torej, ali ima kdo zapomniti vrste
od kot le splošno idejo

885
00:37:25,750 --> 00:37:27,810
kako bubble nekako deluje.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Se spomniš?

888
00:37:32,155 --> 00:37:32,755
>> ŠTUDENT: Ja.

889
00:37:32,755 --> 00:37:33,970
>> Inštruktor: Pojdi.

890
00:37:33,970 --> 00:37:38,980
>> ŠTUDENT: Torej greš skozi in
če je večji, potem ste zamenjali dva.

891
00:37:38,980 --> 00:37:39,820
>> Inštruktor: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Točno tako.

893
00:37:40,564 --> 00:37:41,730
Torej ste pravkar Ponovil skozi.

894
00:37:41,730 --> 00:37:43,050
Morate preveriti dve številki.

895
00:37:43,050 --> 00:37:46,510
Če so pred eno večje
od tistega po njem,

896
00:37:46,510 --> 00:37:50,230
jih samo zamenjali, tako da je v
ta način vse višjimi številkami

897
00:37:50,230 --> 00:37:54,990
mehurček navzgor proti koncu seznama
in vsi spodnji številke mehurček navzdol.

898
00:37:54,990 --> 00:37:59,355
>> Ti je pokazal fantje cool
zvok učinek sortiranje video?

899
00:37:59,355 --> 00:38:00,480
To je nekako kul.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Torej, kot je bilo pravkar omenjeno, Robert algoritma
ki ste ga pravkar korak po seznamu,

902
00:38:05,200 --> 00:38:07,930
zamenjavo sosednjih vrednosti
če nisi v redu.

903
00:38:07,930 --> 00:38:10,975
In potem samo ponavljajo
dokler ne naredite nobene zamenjave.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Torej ni slabo, kajne?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Torej imamo samo na hitro primer tukaj.

908
00:38:16,319 --> 00:38:18,360
Torej, to se dogaja, da razvrstite
jim v naraščajočem vrstnem redu.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Torej, ko smo šli skozi prvo
Tokrat si bomo ogledali preko osmih

911
00:38:23,470 --> 00:38:26,880
in šest očitno niso
z namenom, da jih swap.

912
00:38:26,880 --> 00:38:27,985
>> Torej, poglej naslednjo.

913
00:38:27,985 --> 00:38:29,430
Osem in štiri niso v redu.

914
00:38:29,430 --> 00:38:30,450
Swap njih.

915
00:38:30,450 --> 00:38:32,530
In nato osem in dve, jih zamenjajte.

916
00:38:32,530 --> 00:38:33,470
Tam gremo.

917
00:38:33,470 --> 00:38:39,519
Torej, po prvi izvedel, si
veste, da je vaš največje število

918
00:38:39,519 --> 00:38:41,810
se bo vse poti
na vrhu, ker je samo

919
00:38:41,810 --> 00:38:44,210
bo nenehno
večja kot vse ostalo

920
00:38:44,210 --> 00:38:46,810
in to je le, da bo balon
navzgor vse do konca tam.

921
00:38:46,810 --> 00:38:48,226
Ali je to smiselno za vsakogar?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Cool.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Torej gledamo na našem drugem prehodu.

926
00:38:53,920 --> 00:38:54,980
Šest in štiri, stikalo.

927
00:38:54,980 --> 00:38:55,920
Šest let in dva stikala.

928
00:38:55,920 --> 00:38:58,700
In zdaj imamo še nekaj stvari v red.

929
00:38:58,700 --> 00:39:02,240
Torej, za vsako je izvedel, da smo
da po celotnem seznamu

930
00:39:02,240 --> 00:39:06,320
vemo, da je, kot da je veliko število
Na koncu so bili bodo razporejene.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Torej naredimo tretji sredino,
ki je ena swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
In potem na naš četrti
opraviti imamo nič reže.

935
00:39:15,910 --> 00:39:18,570
In tako vemo, da je naš
Niz je bil razvrščen.

936
00:39:18,570 --> 00:39:20,900
>> In to je velik
stvar z mehurček vrste.

937
00:39:20,900 --> 00:39:23,720
Vemo, da ko smo
imeti nič zamenjave, ki

938
00:39:23,720 --> 00:39:26,497
pomeni, da je vse
je v popolnem redu.

939
00:39:26,497 --> 00:39:27,580
To je nekako, kako preveriti.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Tako smo se tudi dogaja, da kodo mehurček
vrsta, ki tudi ni tako slabo.

942
00:39:36,480 --> 00:39:38,120
Nobeden od teh, ki so slabe.

943
00:39:38,120 --> 00:39:40,210
Vem, da se lahko zdi nekoliko strašljivo.

944
00:39:40,210 --> 00:39:42,124
Vem, da ko sem prevzel
razred, tudi ko sem

945
00:39:42,124 --> 00:39:44,290
je poučeval v razredu za
prvič lani,

946
00:39:44,290 --> 00:39:46,165
Sem bil všeč, kako to storiti?

947
00:39:46,165 --> 00:39:48,540
Smiselno je v teoriji, ampak
kako pravzaprav to?

948
00:39:48,540 --> 00:39:51,420
Zato sem prav tako želeli, da hodi
skozi kodo z vami tukaj.

949
00:39:51,420 --> 00:39:54,915
Tako da imam psevdokoda
za vas fantje tokrat.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Torej, samo obdržati to v mislih,
smo na tem, da prehod čez.

952
00:39:58,970 --> 00:40:04,210
Torej imamo nekaj števec, ki
beleži naših zamenjav,

953
00:40:04,210 --> 00:40:08,370
saj moramo zagotoviti,
da smo preverjanje, da.

954
00:40:08,370 --> 00:40:11,830
In smo Ponovil celotno paleto
kot smo pravkar storil s tem primerom.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Če preden je element večji od
element potem, ko smo na,

957
00:40:17,325 --> 00:40:20,760
smo jih zamenjali in smo prirastek Nostra
števec, ker takoj, ko bomo zamenjali,

958
00:40:20,760 --> 00:40:23,850
želimo pustiti naš števec veš.

959
00:40:23,850 --> 00:40:26,247
Vsa vprašanja tam?

960
00:40:26,247 --> 00:40:27,580
Nekaj ​​zdi smešno tukaj.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
ŠTUDENT: Ali ste nastavili števec na nič
vsakič, ko greš skozi zanko?

963
00:40:32,350 --> 00:40:34,339
Ne boste nadaljuj
nazaj na nič vsakič?

964
00:40:34,339 --> 00:40:35,505
Inštruktor: Ni nujno.

965
00:40:35,505 --> 00:40:39,710
Torej, kaj se zgodi, ko gremo skozi tukaj.

966
00:40:39,710 --> 00:40:43,830
To storijo, ko, ne pozabite, to
se bodo izvajale enkrat ne da bi propadel.

967
00:40:43,830 --> 00:40:46,480
Tako se dogaja, da nastavite
števec enak nič,

968
00:40:46,480 --> 00:40:48,070
potem se dogaja, da skozi ponovitev.

969
00:40:48,070 --> 00:40:50,590
Saj se ponovi,
bo posodobitev števec.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Saj posodobi števec, ko je to storil,
ko je to dosegel konec matrike,

972
00:40:56,900 --> 00:41:00,830
če je naš seznam ni bil razvrščen,
števec pa se bo posodobljen.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Torej potem preverja stanje in ga
pravi, OK, je števec večji od nič.

975
00:41:07,150 --> 00:41:09,290
Če je, še enkrat.

976
00:41:09,290 --> 00:41:14,340
Želite, da ko boste ponastavili
iti skozi, števec enak nič.

977
00:41:14,340 --> 00:41:18,240
Če greš skozi sortirani
matrika, se nič ne spremeni,

978
00:41:18,240 --> 00:41:21,355
to ne uspe, vi pa
vrnitev razvrščen seznam.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Ali je to smiselno?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
ŠTUDENT: To bi v malo.

983
00:41:26,356 --> 00:41:27,147
Inštruktor: OK.

984
00:41:27,147 --> 00:41:28,980
Če je katera koli druga
Vprašanje, ki pride gor.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Da.

987
00:41:30,680 --> 00:41:33,760
>> ŠTUDENT: Kaj bi funkcijo
bo za zamenjavo elementov?

988
00:41:33,760 --> 00:41:36,900
>> Inštruktor: Torej lahko dejansko napisati
da če bomo zdaj.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Cool.

991
00:41:38,300 --> 00:41:42,155
Torej na to opombo, Alison se dogaja
preklopiti nazaj na aparat.

992
00:41:42,155 --> 00:41:43,080
To bo zabavno.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
In imamo lepo
bubble nekako stvar tukaj.

995
00:41:47,390 --> 00:41:50,800
Tako da sem že naredil kolesarjenje
preko matrike.

996
00:41:50,800 --> 00:41:53,030
Imamo zamenjave, ki
so enaki nič.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Zato želimo, da bi zamenjali meji
Elementi, če si pokvarjen.

999
00:41:58,440 --> 00:42:03,020
Torej prva stvar, moramo
Ponovil se je skozi našo paleto.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Torej, kako misliš, da bi lahko
Ponovil skozi našo paleto?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Imamo za in i enak 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Želimo, i ne sme biti manjši
kot n minus 1 minus k.

1006
00:42:22,454 --> 00:42:23,870
In bom razložiti, da v sekundi.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Torej, to je optimizacija tukaj, kjer
Spominjam se, kako sem rekel po vsakem izvedel

1009
00:42:32,830 --> 00:42:36,655
skozi array mi
vem, da vse, kar je on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Torej, po enem prehodu smo
vedo, da je to urejeno.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Po dveh prelazov vemo,
da je vse to urejeno.

1014
00:42:50,060 --> 00:42:52,750
Po treh prelazov smo
vemo, da je urejeno.

1015
00:42:52,750 --> 00:42:55,620
Tako mimogrede sem ponavljanjem
preko matrike tod

1016
00:42:55,620 --> 00:43:01,090
se je pazite, da le gre
skozi tisto, kar vemo, je, razvrščeni.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
To je samo za optimizacijo.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Lahko bi jo napišite naivno samo
ponavljanjem skozi vse,

1021
00:43:08,210 --> 00:43:09,970
da bi le trajalo dlje.

1022
00:43:09,970 --> 00:43:12,470
S tem štiri zanke je
samo lepo optimizacija

1023
00:43:12,470 --> 00:43:18,460
ker vemo, da po vsaki polni
iteracija preko matrike tod

1024
00:43:18,460 --> 00:43:24,050
kot vsako polno zanko tu, vemo,
da ena od teh elementov

1025
00:43:24,050 --> 00:43:25,760
bodo razporejene konec.

1026
00:43:25,760 --> 00:43:28,294
>> Tako da nam ni treba skrbeti za tiste.

1027
00:43:28,294 --> 00:43:29,710
Ali je to smiselno za vsakogar?

1028
00:43:29,710 --> 00:43:30,950
To cool mali trik?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Torej v tem primeru, če
smo s ponavljanjem,

1031
00:43:37,270 --> 00:43:50,590
vemo, da smo želeli preveriti, če
matrika n in n + 1 v redu.

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
Torej, tukaj je psevdokoda.

1035
00:43:54,600 --> 00:43:57,540
Želimo, da preverite, če matrika n
in n + 1 v redu.

1036
00:43:57,540 --> 00:43:59,520
Torej, kaj bi imeli tam?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
To se dogaja, da nekateri pogojno.

1039
00:44:03,120 --> 00:44:04,220
To bo, če.

1040
00:44:04,220 --> 00:44:07,066
>> UČENEC: Če matrika n
manj kot matrika n plus 1.

1041
00:44:07,066 --> 00:44:07,816
Inštruktor: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
No, manjša ali večja od.

1044
00:44:10,699 --> 00:44:11,615
ŠTUDENT: Večja kot.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Potem smo želeli, da jih swap.

1047
00:44:17,620 --> 00:44:18,570
Točno tako.

1048
00:44:18,570 --> 00:44:23,570
Torej, zdaj smo prišli v kaj
mehanizem za njihovo zamenjavo?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Torej smo šli skozi to kratko,
tip swap funkcijo prejšnji teden.

1051
00:44:28,137 --> 00:44:29,595
Ali kdo spomnite, kako je delal?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Zato ne moremo samo njihovo prerazporeditev, kajne?

1054
00:44:34,950 --> 00:44:36,640
Ker je eden od njih boste izgubili.

1055
00:44:36,640 --> 00:44:41,696
Če smo rekli, je enako B in nato B
je enaka A, vse nenadna oba

1056
00:44:41,696 --> 00:44:43,150
so samo enaka B.

1057
00:44:43,150 --> 00:44:45,720
>> Torej, kaj moramo storiti, je, da smo
imajo začasno spremenljivko, ki je

1058
00:44:45,720 --> 00:44:49,055
dogaja, da imajo enega od naših časa
smo v procesu zamenjavo.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Torej, kaj imamo, je, da bomo imeli nekaj int
Temperatura je enaka to-- jo lahko dodelite

1061
00:44:56,464 --> 00:44:59,130
da tisti, ki ste želeli, samo
poskrbite, da boste spremljate it--

1062
00:44:59,130 --> 00:45:01,840
tako da v tem primeru, jaz grem na
dodelite niz n plus 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Tako, da se dogaja, da imajo karkoli
vrednost je v tem drugem bloku

1065
00:45:07,674 --> 00:45:08,590
da gledaš.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> In potem lahko storimo, je lahko greva
naprej in znova dodelite niz n + 1,

1068
00:45:13,240 --> 00:45:14,990
saj vemo,
so, da je vrednost, shranjeno.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
To je prav tako ena velika
things-- Ne vem, če kdo od vas

1071
00:45:19,270 --> 00:45:23,780
imeli vprašanja, pri katerih, če preklopite dva
vrstic kode nenadoma stvari delal.

1072
00:45:23,780 --> 00:45:25,880
Da je zelo pomembno v CS.

1073
00:45:25,880 --> 00:45:29,450
Torej, poskrbite, da boste diagram
stvari, če je to mogoče

1074
00:45:29,450 --> 00:45:31,230
o tem, kaj se dejansko dogaja.

1075
00:45:31,230 --> 00:45:34,256
Torej, zdaj bomo
dodelite niz n + 1,

1076
00:45:34,256 --> 00:45:36,005
saj vemo,
so, da je vrednost, shranjeno.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> In bomo lahko določite, da niz
n ali v tem primeru matriki i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Preveč spremenljivk.

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
Torej, zdaj smo prerazporedili matrika i
plus 1 do enakega kaj je v matriki i.

1084
00:46:01,500 --> 00:46:08,240
In zdaj se lahko vrnemo in
dodelite niz I do česa?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Kdorkoli?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> ŠTUDENT: 10.

1089
00:46:14,010 --> 00:46:14,680
>> Inštruktor: 10.

1090
00:46:14,680 --> 00:46:15,180
Točno tako.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
In še zadnja stvar.

1093
00:46:18,640 --> 00:46:21,840
Če smo ga zamenjali zdaj,
Kaj moramo storiti?

1094
00:46:21,840 --> 00:46:23,740
Kaj je ena stvar,
da se dogaja, da nam poveste

1095
00:46:23,740 --> 00:46:27,542
če bomo kdaj odpove ta program?

1096
00:46:27,542 --> 00:46:29,250
Kaj nam pove, da smo
imajo razvrščen seznam?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Če nam ne opravljajo nobene zamenjave, kajne?

1099
00:46:33,750 --> 00:46:36,900
Če zamenjav je enaka
nič ob koncu tega.

1100
00:46:36,900 --> 00:46:42,975
Torej, ko izvedete zamenjavo, kot smo
pravkar storil tukaj, želimo posodobiti zamenjavami.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
In vem, da je bilo
Vprašanje prej o tem si lahko

1103
00:46:47,210 --> 00:46:49,689
uporabljajte nič ali ena, namesto
od true ali false.

1104
00:46:49,689 --> 00:46:50,980
In to je tisto, kar ta počne tukaj.

1105
00:46:50,980 --> 00:46:52,750
Tako da je ta pravi, če ne zamenjavami.

1106
00:46:52,750 --> 00:47:01,310
Torej, če zamenjave je enaka nič, kar is-- sem vedno
dobili moje resnice in moje falses pomešal.

1107
00:47:01,310 --> 00:47:03,960
Želimo, da ocenimo
da res in to ni.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Torej, če je nič, potem je false.

1110
00:47:09,630 --> 00:47:12,560
Če ga zanikajo z
[? bang?] postane res.

1111
00:47:12,560 --> 00:47:13,975
Torej ta vrstica izvede.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Resnice in napačne in
ničel in enic dobili nor.

1114
00:47:17,370 --> 00:47:20,690
Samo, če počasi hodi
skozi njo bo smisla.

1115
00:47:20,690 --> 00:47:23,320
Ampak to je tisto, kar ta mali
bit kode tu počne.

1116
00:47:23,320 --> 00:47:26,490
Tako da to preveri,
smo naredili nobene zamenjave.

1117
00:47:26,490 --> 00:47:30,054
Torej, če je to vse, kar je poleg
nič, da se dogaja, da so napačne

1118
00:47:30,054 --> 00:47:31,970
in stvar je
bo ponovno izvesti.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Cool?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> ŠTUDENT: Kaj narediti premor?

1123
00:47:36,000 --> 00:47:38,990
>> Inštruktor: Break samo
vas izbruhne zanke.

1124
00:47:38,990 --> 00:47:41,570
Torej, v tem primeru pa bi
rad na koncu programa

1125
00:47:41,570 --> 00:47:43,828
in vi bi samo
imajo svoj sortira seznam.

1126
00:47:43,828 --> 00:47:44,536
ŠTUDENT: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
Inštruktor: Žal mi je?

1129
00:47:49,010 --> 00:47:52,110
ŠTUDENT: Ker prej smo
rabljeni napisan 1 nad napisal nič

1130
00:47:52,110 --> 00:47:54,170
predstaviti, da če
da bo delo ali ne.

1131
00:47:54,170 --> 00:47:54,878
>> Inštruktor: Ja.

1132
00:47:54,878 --> 00:47:56,410
Tako da se lahko vrnete nič ali 1.

1133
00:47:56,410 --> 00:47:58,950
V tem primeru, ker smo dejansko ne
delaš karkoli s funkcijo,

1134
00:47:58,950 --> 00:48:00,150
smo samo želim, da bi prekinil.

1135
00:48:00,150 --> 00:48:02,680
Mi pravzaprav ne skrbi o tem.

1136
00:48:02,680 --> 00:48:06,960
Zavora je tudi dobro, če
to je uporabljena za zlom

1137
00:48:06,960 --> 00:48:10,710
štirih zank ali pogojev, ki
ne želite, da izvršiteljica.

1138
00:48:10,710 --> 00:48:12,110
Samo vas popelje iz njih.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
To je malo pomenski odtenki stvar.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Počutim se, kot da je
Veliko strani kodranje,

1143
00:48:18,445 --> 00:48:19,740
kot boste izvedeli vse o tem kmalu.

1144
00:48:19,740 --> 00:48:20,955
>> Vendar pa boste izvedeli vse o tem kmalu.

1145
00:48:20,955 --> 00:48:21,500
Obljubim.

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
Torej ne vsi dobili mehurček vrste?

1149
00:48:24,840 --> 00:48:25,550
Ni preveč slabo.

1150
00:48:25,550 --> 00:48:31,910
Ponovil skozi, swap stvari, ki uporabljajo
temp spremenljivka, in smo vsi tam nastavljen?

1151
00:48:31,910 --> 00:48:32,960
Cool.

1152
00:48:32,960 --> 00:48:34,080
Super.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Nazaj na PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Vsa vprašanja v splošnem
O teh tako daleč?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Cool.

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
>> ŠTUDENT: [neslišno] int glavni običajno.

1162
00:48:45,279 --> 00:48:46,695
Ali moraš imeti, da je za to?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> Inštruktor: Torej smo samo iščejo
le ob dejanskem razvrščanje algoritem.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Če jo je imel v
kot večji program,

1167
00:48:56,350 --> 00:48:57,891
bi imeli int glavno nekje.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Odvisno od tega, kje ste
uporabljajo ta algoritem,

1170
00:49:02,880 --> 00:49:05,860
da bi ugotovili, kaj je
se vrnil z njo.

1171
00:49:05,860 --> 00:49:09,960
Toda za naš primer, smo strogo
gledaš kako to dejansko

1172
00:49:09,960 --> 00:49:11,300
Ponovil skozi paleto.

1173
00:49:11,300 --> 00:49:12,570
Tako da ne skrbi.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Tako smo govorili o najboljšem primeru in
najslabšega scenarija za binarno iskanje.

1176
00:49:19,830 --> 00:49:22,470
Zato je tudi pomembno, da se
da za vsako od naših vrst.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Torej, kaj misliš, da je najhujše
Primer runtime mehurčkov vrste?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Vi se spomnite?

1181
00:49:30,700 --> 00:49:31,784
>> ŠTUDENT: N minus 1.

1182
00:49:31,784 --> 00:49:32,700
Inštruktor: N minus 1.

1183
00:49:32,700 --> 00:49:35,070
Torej to pomeni, da obstaja
n minus 1 primerjave.

1184
00:49:35,070 --> 00:49:40,060
Torej, ena stvar, da zavedaš,
da na prvi ponovitvi

1185
00:49:40,060 --> 00:49:43,360
gremo skozi, moramo primerjati
ti dvo tako da je 1.

1186
00:49:43,360 --> 00:49:46,685
Ti dve, tri, štiri.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Torej, po eni ponovitvi smo
že štiri primerjave.

1189
00:49:55,050 --> 00:49:58,230
Ko govorim o runtime in n.

1190
00:49:58,230 --> 00:50:04,680
N predstavlja število primerjav
kot funkcija koliko elementov

1191
00:50:04,680 --> 00:50:05,570
imamo.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Torej, gremo skozi, imamo štiri.

1194
00:50:08,860 --> 00:50:11,780
Naslednjič, ko boste vedeli, da ne
skrbeti za to.

1195
00:50:11,780 --> 00:50:15,140
Primerjamo ta dva,
ta dva, ta dva,

1196
00:50:15,140 --> 00:50:20,050
in če ne bi imeli te optimizacijo
s štirimi zanko, da sem napisal,

1197
00:50:20,050 --> 00:50:22,750
bi se primerjali tu nekako.

1198
00:50:22,750 --> 00:50:26,170
Torej bi morali
teči skozi polja

1199
00:50:26,170 --> 00:50:34,380
in da n primerjave n
krat, ker vsakič, ko

1200
00:50:34,380 --> 00:50:36,670
teči skozi to zbiramo eno stvar.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> In vsakič, ko teče skozi
matrika, naredimo n primerjave.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Torej naš runtime za to je
dejansko je n kvadrat, ki

1205
00:50:46,330 --> 00:50:48,400
je precej slabše v našem
log konca, saj da

1206
00:50:48,400 --> 00:50:51,965
pomeni, da če bi imeli štiri
Milijarde elementi, to je

1207
00:50:51,965 --> 00:50:55,260
dogaja, da nam bo štiri milijarde
kvadrat, namesto 32.

1208
00:50:55,260 --> 00:51:01,240
Torej ni najboljši runtime,
ampak za nekatere stvari,

1209
00:51:01,240 --> 00:51:04,610
veste, če ste v
določenega obsega elemente

1210
00:51:04,610 --> 00:51:06,540
bubble nekako lahko v redu za uporabo.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Torej, zdaj, kaj je najboljši primer runtime?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
ŠTUDENT: Zero?

1215
00:51:14,940 --> 00:51:16,420
Ali 1?

1216
00:51:16,420 --> 00:51:18,140
>> Inštruktor: Torej 1 bi
ena primerjava.

1217
00:51:18,140 --> 00:51:19,114
Prav.

1218
00:51:19,114 --> 00:51:20,002
>> ŠTUDENT: N minus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> Inštruktor: Torej, ja.

1221
00:51:22,320 --> 00:51:22,990
Torej n minus 1.

1222
00:51:22,990 --> 00:51:26,510
Kadarkoli imate koncept, kot n
minus 1, smo vajeni, da ga samo odložiš

1223
00:51:26,510 --> 00:51:31,680
in smo pravkar rekli, n, ker imate
Za primerjavo vsako these-- vsakega para.

1224
00:51:31,680 --> 00:51:36,470
Torej bi bilo n minus 1, ki smo
mi bi samo rekel približno n.

1225
00:51:36,470 --> 00:51:39,280
Ko imate opravka z runtime,
vse, kar je v ta približuje.

1226
00:51:39,280 --> 00:51:43,860
Dokler je eksponent
pravilno, da ste zelo dobro.

1227
00:51:43,860 --> 00:51:45,700
>> Tako imamo opravka z njo.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Tako da najbolje primeru je n, ki
pomeni, da je seznam že razporejene,

1230
00:51:51,780 --> 00:51:54,320
in vse, kar smo storili je teči skozi
in preverite, da je to urejeno.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Cool.

1233
00:51:56,855 --> 00:51:57,355
Vse je v redu.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Torej, kot vidite tu,
Samo še nekaj grafov.

1236
00:52:01,920 --> 00:52:02,660
Torej n kvadrat.

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
Veliko slabše, kot n, kot smo videli, in
veliko, veliko slabše kot log 2n.

1240
00:52:09,730 --> 00:52:12,060
In potem dobite tudi v dnevniških hlodov.

1241
00:52:12,060 --> 00:52:18,020
In ste vzeli 124, boste dobili v
kot log zvezda, ki je kot nor.

1242
00:52:18,020 --> 00:52:20,172
Torej, če vas zanima,
lookup log zvezda.

1243
00:52:20,172 --> 00:52:20,880
To je kar zabavno.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Torej imamo to veliko grafikon.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Le glave gor, to
čudovito grafikon, da imajo

1248
00:52:28,720 --> 00:52:31,350
za vaš srednjeročno, ker smo
dolgo, da vas ta stanjša.

1249
00:52:31,350 --> 00:52:36,090
Torej le glave gor, še to na vaš
Vmesno na vaši lepi goljufija stanja

1250
00:52:36,090 --> 00:52:36,616
tam.

1251
00:52:36,616 --> 00:52:37,990
Tako smo samo pogledal mehurček vrste.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
V najslabšem primeru, n kvadrat, najboljši primer, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
In bomo pogled na druge.

1256
00:52:44,950 --> 00:52:47,940
>> In kot vidite, samo
tisti, ki res dobro

1257
00:52:47,940 --> 00:52:50,910
je z zlivanjem, kar bomo dobili v zakaj.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Tako smo šli na
Naslednjič here-- izbor vrste.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Ali kdo spomnite, kako
Izbira vrste delal?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Gre za to.

1264
00:53:05,700 --> 00:53:08,210
>> ŠTUDENT: V bistvu iti skozi
red in ustvariti nov seznam.

1265
00:53:08,210 --> 00:53:11,001
In kot ste dajanje elementov
v, jih postaviti na pravo mesto

1266
00:53:11,001 --> 00:53:11,750
v novem seznamu.

1267
00:53:11,750 --> 00:53:14,040
>> Inštruktor: Torej, da zvoki
več kot vstavljanje vrste.

1268
00:53:14,040 --> 00:53:15,040
Ampak ste res blizu.

1269
00:53:15,040 --> 00:53:15,915
Oni so zelo podobni.

1270
00:53:15,915 --> 00:53:17,440
Tudi jaz se jim pomešal včasih.

1271
00:53:17,440 --> 00:53:18,981
Pred tem oddelku sem bil všeč, počakaj.

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
Torej, kaj hočete
storiti, je izbira vrste,

1275
00:53:24,141 --> 00:53:25,890
Tako si lahko misliš
o njem, in način,

1276
00:53:25,890 --> 00:53:30,140
Sem zagotovil, da sem poskusil, da ne bi dobili
jih pomešal, je gre skozi

1277
00:53:30,140 --> 00:53:33,280
in izbere
Najmanjše število in

1278
00:53:33,280 --> 00:53:36,070
navaja, da je na začetku svojega seznama.

1279
00:53:36,070 --> 00:53:37,730
Jo zamenja s tem prvo mesto.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Jih dejansko imajo zgled za mene.

1282
00:53:45,370 --> 00:53:46,540
Super.

1283
00:53:46,540 --> 00:53:50,130
Torej samo način, da razmišljajo o it-- izbor
urejanje, izberite najmanjšo vrednost.

1284
00:53:50,130 --> 00:53:51,940
In bomo
teči skozi primer

1285
00:53:51,940 --> 00:53:55,320
da mislim, da bo pomagal, ker
Mislim, vizualne vedno pomaga.

1286
00:53:55,320 --> 00:53:58,510
Tako smo začeli z nečim
da je popolnoma razvrščeni.

1287
00:53:58,510 --> 00:54:00,730
Red bodo razvrščeni,
zelena bodo razporejene.

1288
00:54:00,730 --> 00:54:02,190
To bo vse smisla v sekundi.

1289
00:54:02,190 --> 00:54:08,950
>> Torej, gremo skozi in smo Ponovil
od začetka do konca.

1290
00:54:08,950 --> 00:54:12,320
In smo rekli, v redu, 2
naše najmanjše število.

1291
00:54:12,320 --> 00:54:15,680
Torej bomo vzeti 2 in gremo
da ga premaknete na sprednji strani našega polja

1292
00:54:15,680 --> 00:54:17,734
ker je
Najmanj, kar imamo.

1293
00:54:17,734 --> 00:54:19,150
Torej, to je tisto, kar ta počne tukaj.

1294
00:54:19,150 --> 00:54:20,820
To je le, da bo zamenjala tista dva.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Torej, zdaj imamo urejeno
del in razvrščeni del.

1297
00:54:25,450 --> 00:54:27,810
In kaj je dobro, da se spomnimo
glede izbire vrste

1298
00:54:27,810 --> 00:54:30,690
je, da smo le, da izberete
Iz nerazvrščene dela.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Sortirani del, ki ga pustite pri miru.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> ŠTUDENT: Kako vedeti, kaj je
Najmanjši ne da bi ga primerjali

1303
00:54:38,452 --> 00:54:39,868
za vse druge vrednosti v matriki.

1304
00:54:39,868 --> 00:54:41,250
Inštruktor: To počne tako primerjavo.

1305
00:54:41,250 --> 00:54:42,041
Radi ga preskočila.

1306
00:54:42,041 --> 00:54:43,850
To je samo splošni skupni.

1307
00:54:43,850 --> 00:54:44,831
Ja.

1308
00:54:44,831 --> 00:54:47,205
Ko smo napisali kodo Jaz sem
prepričan, da boste bolj zadovoljni.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Vendar si shranite ta prvi
Element najmanjša.

1311
00:54:53,030 --> 00:54:56,110
Primerjajo in si
reči, OK, je manjši?

1312
00:54:56,110 --> 00:54:56,660
Da.

1313
00:54:56,660 --> 00:54:57,460
Obdržati.

1314
00:54:57,460 --> 00:54:58,640
Tukaj je manjši?

1315
00:54:58,640 --> 00:54:59,660
Ne?

1316
00:54:59,660 --> 00:55:02,510
>> To je tvoja najmanjša,
ga prerazporedil na vaše vrednosti.

1317
00:55:02,510 --> 00:55:06,340
In boste veliko srečnejši
ko gremo skozi kode.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Torej, gremo skozi, smo ga zamenjali, tako da potem
gledamo na to nerazvrščene dela.

1320
00:55:13,970 --> 00:55:15,810
Tako bomo izbrali tri out.

1321
00:55:15,810 --> 00:55:18,890
Bomo, da je na na
Konec našega sortirane odseka.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
In smo le, da bo vztrajati početje
da delaš to, in s tem.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Torej je to naša vrsta psevdokoda tukaj.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Mi bomo to kodo tu gor na sekundo.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Ampak samo nekaj, da hodi
preko na visoki ravni.

1330
00:55:37,270 --> 00:55:40,275
Boš šel iz
i je enak 0 za n minus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
To je že druga optimizacijo.

1333
00:55:43,530 --> 00:55:45,020
Ne skrbite preveč o tem.

1334
00:55:45,020 --> 00:55:46,620
Tako kot ste rekli.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Kot Jacob je rekel, kako počnemo
slediti, kaj naš minimum?

1337
00:55:54,406 --> 00:55:55,030
Kako vemo?

1338
00:55:55,030 --> 00:55:57,060
Moramo primerjati
vse, kar je v našem seznamu.

1339
00:55:57,060 --> 00:55:59,600
>> Torej minimum enak i.

1340
00:55:59,600 --> 00:56:03,870
To je samo rekel, v tem primeru
Indeks naše najmanjše vrednosti.

1341
00:56:03,870 --> 00:56:07,660
Torej to se dogaja, ponovitev prek
in gre iz j enak i plus 1.

1342
00:56:07,660 --> 00:56:11,420
Tako že vemo, da
To je naš prvi element.

1343
00:56:11,420 --> 00:56:13,240
Nam ni treba primerjati s sebi.

1344
00:56:13,240 --> 00:56:16,970
Tako smo začeli primerjavo z naslednjo
ena, ki je razlog, zakaj je i plus 1 do n

1345
00:56:16,970 --> 00:56:20,110
minus 1, ki je
Konec niza tam.

1346
00:56:20,110 --> 00:56:25,090
In mi je rekel, če matrika na
j je manjša od diod min,

1347
00:56:25,090 --> 00:56:29,200
potem dodelite kjer
naše minimalne indeksi je.

1348
00:56:29,200 --> 00:56:37,470
>> In če min ni enako i, kot
v Ljubljani, kjer smo bili spet tukaj.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Tako všeč, ko smo najprej naredili to.

1351
00:56:41,790 --> 00:56:49,310
V tem primeru bi bilo začeti na
nič, bi bilo na koncu pa dva.

1352
00:56:49,310 --> 00:56:53,010
Torej min ne bi enako i na koncu.

1353
00:56:53,010 --> 00:56:55,720
Upamo, da nam sporočite, da
jih moramo zamenjati.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Počutim se kot konkreten primer
bo pomagalo veliko več kot to.

1356
00:57:00,470 --> 00:57:04,970
Tako da bom to kodo z vami
prav zdaj, in mislim, da bo bolje.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Vrste ponavadi deluje na tak način, da v
je pogosto bolje, samo da bi jih videli.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Torej, kaj želimo storiti, je
smo najprej želeli najmanjši

1361
00:57:17,280 --> 00:57:19,890
element v svoji legi v matriki.

1362
00:57:19,890 --> 00:57:21,280
Točno to, kar je rekel Jacob.

1363
00:57:21,280 --> 00:57:23,090
Morate shraniti, da nekako.

1364
00:57:23,090 --> 00:57:25,900
Torej bomo začeli tukaj
ponavljanjem čez polja.

1365
00:57:25,900 --> 00:57:28,970
Bomo rekli, da je naš
Prva je samo za začetek.

1366
00:57:28,970 --> 00:57:38,308
Torej bomo imeli int
Najmanjše je enaka matriki na i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Torej, ena stvar, da obvestilo, vsak
Čas ta zanka izvaja,

1369
00:57:45,050 --> 00:57:48,550
začenjamo skupaj en korak naprej.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Ko smo začeli smo poglej tole.

1372
00:57:57,440 --> 00:58:00,840
Naslednjič, ko smo Ponovil skozi,
začenjamo na tale

1373
00:58:00,840 --> 00:58:02,680
in to je naša najmanjša vrednost dodelitev.

1374
00:58:02,680 --> 00:58:10,450
Zato je zelo podoben mehurček vrste
kjer vemo, da je po enem prehodu,

1375
00:58:10,450 --> 00:58:11,700
Ta zadnji element je razvrščen.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Z izbirnim vrste,
to je ravno nasprotno.

1378
00:58:15,120 --> 00:58:18,950
>> Na vsaki je izvedel, vemo, da
Prva je razvrščen.

1379
00:58:18,950 --> 00:58:21,360
Po drugem prehodu,
Drugi pa bodo razvrščeni.

1380
00:58:21,360 --> 00:58:26,470
In kot ste videli s primeri slide,
naša razporejene del samo raste.

1381
00:58:26,470 --> 00:58:34,020
Tako z določitvijo našo najmanjšo eno
do nizi i, vse to počne

1382
00:58:34,020 --> 00:58:37,340
je kaj plitvih
iščemo na tako

1383
00:58:37,340 --> 00:58:40,164
da se zmanjša število
primerjav naredimo.

1384
00:58:40,164 --> 00:58:41,770
Ali to smiselno za vsakogar?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Me morali teči skozi, da
spet počasneje, ali z drugimi besedami?

1387
00:58:46,380 --> 00:58:47,180
Vesel sem, da.

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
>> Tako da smo shranjevanje
vrednosti na tej točki,

1392
00:58:55,540 --> 00:58:57,840
ampak želimo tudi shranjevanje indeks.

1393
00:58:57,840 --> 00:59:01,010
Tako bomo za shranjevanje
Položaj najmanjši

1394
00:59:01,010 --> 00:59:02,770
ena, ki je pravkar bo i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Torej, zdaj Jacob je zadovoljen.

1397
00:59:05,440 --> 00:59:06,870
Imamo stvari shranjene.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
In zdaj moramo odmisliti
razvrščeni del matrike.

1400
00:59:11,870 --> 00:59:18,170
Torej v tem primeru je to
bi bilo naše razvrščeni.

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
>> Torej, kaj bomo storili
se bo za zanko.

1406
00:59:30,040 --> 00:59:32,066
Kadarkoli potrebujete
Ponovil skozi paleto,

1407
00:59:32,066 --> 00:59:33,440
vaš um lahko iti za zanko.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Torej, za nekaj int k
equals-- kaj mislimo

1410
00:59:38,090 --> 00:59:39,700
k bo enaka za začetek?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
To je tisto, kar smo si zastavili, kot je naša najmanjša
vrednost in ga želimo primerjati.

1413
00:59:44,766 --> 00:59:47,090
Kaj želimo primerjati z?

1414
00:59:47,090 --> 00:59:48,730
To se dogaja, da bi se ta naslednjič, kajne?

1415
00:59:48,730 --> 00:59:53,200
Zato želimo k inicializirati
k i plus 1 za zagon.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> In želimo, k smo v tem primeru
že Velikost shranjeni tukaj,

1418
01:00:02,800 --> 01:00:03,930
tako da bomo lahko šele raba velikost.

1419
01:00:03,930 --> 01:00:06,240
Velikost čemer velikost matrike.

1420
01:00:06,240 --> 01:00:09,620
In hočemo samo
posodobiti k ene vsakič.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Cool.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Zdaj moramo najti
najmanjši element tukaj.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Torej, če smo Ponovil skozi, smo
hočeš reči, če je matrika na k

1427
01:00:31,380 --> 01:00:37,080
je manjši od našega najmanjšega value--
to je, če smo dejansko

1428
01:00:37,080 --> 01:00:42,950
sledenja, kaj je
najmanjši here--

1429
01:00:42,950 --> 01:00:47,740
Nato smo želeli prerazporeditev
kakšna je naša najmanjša vrednost.

1430
01:00:47,740 --> 01:00:50,645
>> To pomeni, da, oh, smo
ponavljanjem tu skozi.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Ne glede na vrednost je tu
ni naša najmanjša stvar.

1433
01:00:53,740 --> 01:00:54,448
Mi tega ne želite.

1434
01:00:54,448 --> 01:00:56,100
Želimo, da ga prerazporedil.

1435
01:00:56,100 --> 01:01:02,050
Torej, če smo to prerazporeditev, kaj storiti
misliš, da bi lahko v tem kodeksu tukaj?

1436
01:01:02,050 --> 01:01:04,160
Želimo, da za dodelitev
Najmanjši in položaj.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Torej, kaj je sedaj najmanjši?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
ŠTUDENT: Array k.

1441
01:01:09,130 --> 01:01:09,963
Inštruktor: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
In kaj je zdaj stališče?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Kaj je indeksi
naša najmanjša vrednost?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
To je samo k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Torej diod k, k, se ujemajo.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Zato smo želeli, da je prerazporedil.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
In potem, ko smo ugotovili, naš najmanjši,
tako da na koncu tega za zanke

1454
01:01:39,950 --> 01:01:45,100
Tu smo ugotovili, kakšna je naša najmanjša
vrednost, zato smo ga pravkar zamenjali.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
V tem primeru, kot pravijo Nostra
Najmanjša vrednost je tukaj.

1457
01:01:50,816 --> 01:01:51,940
To je naša najmanjša vrednost.

1458
01:01:51,940 --> 01:01:57,690
>> Pravkar smo želeli zamenjati tukaj, ki je
kaj je funkcija swap na dnu

1459
01:01:57,690 --> 01:02:01,270
storili, kar smo pravkar napisala
skupaj nekaj minut nazaj.

1460
01:02:01,270 --> 01:02:02,775
Tako da bi bilo videti seznanjeni.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
In potem bo to šele Ponovil
prek dokler ne doseže vso pot

1463
01:02:08,030 --> 01:02:13,100
do konca, kar pomeni, da
imeti nič elemente, ki so razvrščeni

1464
01:02:13,100 --> 01:02:14,800
in vse ostalo je bilo urejeno.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Smisla?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Malo bolj konkretno?

1469
01:02:19,280 --> 01:02:19,990
Koda pomoč?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> ŠTUDENT: Za velikosti, nikoli
res določiti ali spremeniti,

1472
01:02:26,410 --> 01:02:27,340
kako to veš?

1473
01:02:27,340 --> 01:02:32,380
>> Inštruktor: Torej, ena stvar,
Opazili tu je velikost int.

1474
01:02:32,380 --> 01:02:35,680
Tako smo govoriš v tem sort-- vrste
je funkcija v tem case-- je

1475
01:02:35,680 --> 01:02:40,770
Izbira vrste, je to opravil
ima funkcijo.

1476
01:02:40,770 --> 01:02:43,460
Torej, če ne bi bil sprejet
leta, bi vi storili nekaj

1477
01:02:43,460 --> 01:02:47,840
kot z dolžino polja
ali bi si ponovitev prek

1478
01:02:47,840 --> 01:02:49,390
najti dolžino.

1479
01:02:49,390 --> 01:02:52,680
Ampak zato, ker je minilo
na, lahko smo samo uporabljati.

1480
01:02:52,680 --> 01:02:55,720
Pravkar si domnevati, da uporabnik
Vam je veljavno velikost, ki

1481
01:02:55,720 --> 01:02:57,698
dejansko predstavlja
velikost vašega array.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Cool?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Če imata vidva nobenih težav z njimi
ali želijo več prakse kodiranja vrste

1486
01:03:05,870 --> 01:03:08,050
sami, morate
pojdite na study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
To je orodje.

1489
01:03:12,670 --> 01:03:15,040
Imajo skladiščnik, ki
lahko dejansko napisati.

1490
01:03:15,040 --> 01:03:16,180
Oni psevdokoda.

1491
01:03:16,180 --> 01:03:19,310
Imajo več video posnetkov in diapozitivov
vključno s tistimi, ki jih uporabljam tukaj.

1492
01:03:19,310 --> 01:03:23,150
Torej, če ste še vedno občutek
malo fuzzy, poskusite to.

1493
01:03:23,150 --> 01:03:25,670
Kot vedno, pridi govoriti z menoj, preveč.

1494
01:03:25,670 --> 01:03:26,320
Vprašanje?

1495
01:03:26,320 --> 01:03:28,611
>> ŠTUDENT: Praviš
velikost je definirano prej?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
Inštruktor: Da.

1498
01:03:29,900 --> 01:03:35,570
Velikost je definirano prej gor
tukaj v deklaraciji funkcije.

1499
01:03:35,570 --> 01:03:39,060
Torej si domnevati, da je bil sprejet leta
s strani uporabnika, in zavoljo enostavnosti je,

1500
01:03:39,060 --> 01:03:41,896
bomo predvidevali, da
Uporabnik nam je prave velikosti.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Tako da je izbira vrste.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Fantje, vem, da smo ogromno naučili danes.

1505
01:03:47,640 --> 01:03:49,710
To je gosto podatki za oddelka.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Torej, s tem se bomo
iti vstavljanja vrste.

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
Torej, preden da moramo storiti
naša runtime analize tukaj.

1511
01:04:06,100 --> 01:04:10,190
Torej v najboljšem primeru,
odobrena, saj sem ti pokazal

1512
01:04:10,190 --> 01:04:11,960
miza sem že
nekako ga dal proč.

1513
01:04:11,960 --> 01:04:15,430
Ampak najboljši primer runtime, kaj mislimo?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Je vse urejeno.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N na kvadrat.

1518
01:04:22,070 --> 01:04:24,780
Kdo pojasnilo
zakaj misliš?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> ŠTUDENT: Ste primerjavo through--

1521
01:04:30,519 --> 01:04:31,268
Inštruktor: Right.

1522
01:04:31,268 --> 01:04:32,540
Ste primerjali skozi.

1523
01:04:32,540 --> 01:04:35,630
Na vsaki iteraciji, čeprav
smo pomanjšanja to z enim,

1524
01:04:35,630 --> 01:04:38,950
ste še vedno iščejo s pomočjo
vse, da bi našli najmanjšo enega.

1525
01:04:38,950 --> 01:04:42,390
Torej, tudi če je vaš najmanjša vrednost
je tu na začetku,

1526
01:04:42,390 --> 01:04:44,710
ste še vedno ga primerja
proti vsem ostalim

1527
01:04:44,710 --> 01:04:46,550
se prepričajte, da je najmanjša stvar.

1528
01:04:46,550 --> 01:04:49,820
Tako da boste na koncu, ki teče skozi
približno n kvadrat krat.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Vse je v redu.

1531
01:04:51,590 --> 01:04:52,785
In kaj je v najslabšem primeru?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Tudi n kvadrat, ker boš
da se delaš, da je isti postopek.

1534
01:04:57,980 --> 01:05:01,670
Torej, v tem primeru, izbor
vrsta ima nekaj

1535
01:05:01,670 --> 01:05:04,010
da smo tudi pokličete pričakovani runtime.

1536
01:05:04,010 --> 01:05:07,400
Torej, na ostalih pa smo samo vedeti
zgornja in spodnja meja.

1537
01:05:07,400 --> 01:05:11,180
Odvisno od tega, kako noro naše
seznam ali kako razvrščeni je,

1538
01:05:11,180 --> 01:05:15,350
se razlikujejo od n ali N razčetverjen.

1539
01:05:15,350 --> 01:05:16,550
Ne vemo.

1540
01:05:16,550 --> 01:05:22,820
>> Ampak zato, ker je izbira nekako enako
najslabši in najboljši primer, ki nam pove, da

1541
01:05:22,820 --> 01:05:25,880
ne glede na to, kakšne vrste vhodu smo
imajo, ali je to popolnoma

1542
01:05:25,880 --> 01:05:29,130
razporejene ali popolnoma
povratne razporejene, da je

1543
01:05:29,130 --> 01:05:30,740
bo trajalo enako količino časa.

1544
01:05:30,740 --> 01:05:33,760
Torej, v tem primeru, če vas
spomnite iz naše tabele,

1545
01:05:33,760 --> 01:05:38,610
dejansko imela vrednost,
ti dve vrsti nimajo,

1546
01:05:38,610 --> 01:05:40,390
kar je pričakovano runtime.

1547
01:05:40,390 --> 01:05:43,350
Torej vemo, da vsakič, ko
tečemo za izbiro vrste,

1548
01:05:43,350 --> 01:05:45,380
to je zagotovljeno, da
teči n kvadrat čas.

1549
01:05:45,380 --> 01:05:46,630
Ni variabilnost tam.

1550
01:05:46,630 --> 01:05:47,630
To je samo pričakovati.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
In, še enkrat, če želite, da se naučijo
več, da CS 124 v pomladi.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Vse je v redu.

1555
01:05:56,712 --> 01:05:57,545
Videli smo tole.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Cool.

1558
01:05:59,030 --> 01:06:00,930
Torej vstavljanje nekako.

1559
01:06:00,930 --> 01:06:03,330
In sem verjetno bo
Blaze skozi to.

1560
01:06:03,330 --> 01:06:05,440
Ne bo vam fantje to kodo.

1561
01:06:05,440 --> 01:06:06,580
Bomo le sprehod skozi to.

1562
01:06:06,580 --> 01:06:10,500
Torej vstavljanje vrsta je vrsta
za podobno izbire vrste

1563
01:06:10,500 --> 01:06:14,460
s tem, da imamo tako razvrščeni
in razporejene del matrike.

1564
01:06:14,460 --> 01:06:20,260
>> Toda kaj je drugačna je, da
ko gremo skozi enega po enega,

1565
01:06:20,260 --> 01:06:24,210
smo vzemite karkoli številko
je naslednji v naši razvrščeni,

1566
01:06:24,210 --> 01:06:28,507
in ga pravilno razvrstiti
v našem urejenem niz.

1567
01:06:28,507 --> 01:06:30,090
To bo bolj smiselno s primerom.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Torej vse, kar se začne kot neprebrani,
Tako kot pri izbirnem vrste.

1570
01:06:35,430 --> 01:06:38,740
In bomo rešiti to
naraščajočem vrstnem redu, kot smo bili.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Torej, na naši prvi izvedel
vzamemo prvo vrednost

1573
01:06:43,340 --> 01:06:46,700
in smo rekli, v redu, ste
zdaj na seznamu, ki ga sami.

1574
01:06:46,700 --> 01:06:49,150
>> Ker ste na seznamu
sami, ste razvrščeni.

1575
01:06:49,150 --> 01:06:52,460
Čestitke za to, da
Prvi element v tem polju.

1576
01:06:52,460 --> 01:06:54,800
Ste že razporejene vse na svoje.

1577
01:06:54,800 --> 01:06:58,900
Torej, zdaj imamo urejeno
in razvrščeni niz.

1578
01:06:58,900 --> 01:07:01,760
Torej, zdaj bomo prvi.

1579
01:07:01,760 --> 01:07:05,600
Kaj se zgodi med tukaj
in tukaj je, da rečemo,

1580
01:07:05,600 --> 01:07:08,890
OK, gremo pogledati
Prva vrednost našega nerazvrščene niz

1581
01:07:08,890 --> 01:07:13,270
in bomo vhod je v svojem
pravilno mesto v urejenem array.

1582
01:07:13,270 --> 01:07:21,460
>> Torej, kaj mi se bomo 5 in
smo rekli, v redu, 5 je večja od 3,

1583
01:07:21,460 --> 01:07:24,630
tako da smo samo vstavite desno
na pravico do tega.

1584
01:07:24,630 --> 01:07:25,130
Mi smo dobro.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Torej gremo na našo naslednjo.

1587
01:07:28,420 --> 01:07:29,720
In vzamemo 2.

1588
01:07:29,720 --> 01:07:34,330
Smo rekli, v redu, 2 manj
od 3, tako da vemo, da njim

1589
01:07:34,330 --> 01:07:36,220
mora biti
Sprednji del našega seznama zdaj.

1590
01:07:36,220 --> 01:07:41,800
Torej, kaj moramo storiti, je potisnemo 3 in 5 dol
in gremo 2 v tej prvi režo.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Tako da smo pravkar jo vstavite
pravilno mesto bi moralo biti.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Potem pogledamo naše
Naslednjič, in rečemo 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 je večja od
vse, kar je v našem urejenem polju,

1596
01:07:53,620 --> 01:07:56,000
zato smo samo označil do konca.

1597
01:07:56,000 --> 01:07:56,960
In potem gledamo 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 je manjša od 6, to je manj
od 5, vendar je večji od 3.

1600
01:08:03,020 --> 01:08:06,270
Tako smo samo vstavite naravnost v
sredina med 3 in 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Torej naj da malo
nekoliko bolj konkreten,

1603
01:08:10,530 --> 01:08:12,280
tukaj je nekako
Ideja o tem, kaj se je zgodilo.

1604
01:08:12,280 --> 01:08:16,430
Torej za vsako nerazvrščene element smo
ugotoviti, kje v urejenem delu

1605
01:08:16,430 --> 01:08:17,090
je.

1606
01:08:17,090 --> 01:08:20,680
>> Torej, v obzir je
razporejene in razvrščeni,

1607
01:08:20,680 --> 01:08:26,080
moramo prečkati skozi in slika
kam to paše v urejenem array.

1608
01:08:26,080 --> 01:08:31,460
In jo vstavite s preusmeritvijo
Elementi na desni strani jo.

1609
01:08:31,460 --> 01:08:34,910
In potem smo samo vztrajati
ponavljanjem skozi, dokler ne bomo

1610
01:08:34,910 --> 01:08:39,270
imajo povsem razvrščen seznam
kjer razvrščeni je zdaj nič

1611
01:08:39,270 --> 01:08:41,720
in sortirani prevzame
celota našem seznamu.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Torej, še enkrat, da bi stvari še
bolj konkretno, imamo psevdokoda.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Torej v bistvu za i
enaka 0 do n minus 1,

1616
01:08:52,410 --> 01:08:54,790
da je samo dolžina naši array.

1617
01:08:54,790 --> 01:09:00,979
Imamo nek element, ki je enaka
Prvi niz ali prvi indeksi.

1618
01:09:00,979 --> 01:09:03,200
Postavili smo j, ki je enaka.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Torej, medtem ko je j večji od
nič in matrika, j minus 1

1621
01:09:09,210 --> 01:09:11,660
je večja od
element, tako da vse, kar počne

1622
01:09:11,660 --> 01:09:17,479
je zagotoviti, da
Vaše j res predstavlja

1623
01:09:17,479 --> 01:09:20,010
razvrščeni del matrike.

1624
01:09:20,010 --> 01:09:30,745
>> Torej, medtem ko je še vedno stvari
razvrstiti in j minus ena is-- kaj

1625
01:09:30,745 --> 01:09:31,840
je element ona?

1626
01:09:31,840 --> 01:09:34,760
J ni bil nikoli definiran tukaj.

1627
01:09:34,760 --> 01:09:35,677
To je nekako nadležno.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Nekako.

1630
01:09:36,689 --> 01:09:39,899
Torej j minus 1, ste preverjanje
element pred njim.

1631
01:09:39,899 --> 01:09:46,460
Pravite, OK, je element
preden kjerkoli sem am-- dovolimo,

1632
01:09:46,460 --> 01:09:47,540
dejansko pripraviti to.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Torej, recimo, da je to
kot na našem drugem prehodu.

1635
01:09:56,830 --> 01:09:59,525
Torej, jaz se bo enaka
do 1, ki je tukaj.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Torej, jaz se dogaja, da je enak 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
To bi bilo 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Vse je v redu.

1642
01:10:16,750 --> 01:10:20,945
Torej naš element v tem primeru
se bo enak 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
In imamo nekaj j, ki je
bo enaka 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, se j pomanjšanja.

1647
01:10:30,971 --> 01:10:31,720
To je tisto, kar je.

1648
01:10:31,720 --> 01:10:35,680
Torej je j enak i, kaj je to
rekel je, da je, kot smo korak naprej,

1649
01:10:35,680 --> 01:10:37,530
smo samo pazite,
da nismo več

1650
01:10:37,530 --> 01:10:43,520
indeksiranje na ta način, ko skušamo
vstaviti stvari v našem seznamu razvrščeni.

1651
01:10:43,520 --> 01:10:49,850
>> Torej, ko je j enak 1, v tem primeru in
Niz j minus one-- tako matrika j minus 1

1652
01:10:49,850 --> 01:10:54,610
2 v tem case--, če je to
večja od elementa,

1653
01:10:54,610 --> 01:10:57,700
potem vse to počne
seli stvari navzdol.

1654
01:10:57,700 --> 01:11:04,790
Torej, v tem primeru, matrika j minus ena
bo matrika nič, kar je 2.

1655
01:11:04,790 --> 01:11:08,430
2 ni večje od 4,
tako da to ne izvede.

1656
01:11:08,430 --> 01:11:11,460
Torej premik ne premakne navzdol.

1657
01:11:11,460 --> 01:11:18,790
Kaj se tukaj to počne je le
premik urejen paleto navzdol.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
V tem primeru, dejansko smo
lahko do-- Naredimo to 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Torej, če smo prehodili z
ta primer, smo zdaj tu.

1662
01:11:31,970 --> 01:11:32,740
To je urejeno.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
To je neprebrani.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
Torej i je enak 2, tako
naša elementa enaka 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
In naša j je enaka 2.

1670
01:11:52,270 --> 01:12:00,620
Torej gledamo skozi in smo
reči, OK, je matrika j minus ena

1671
01:12:00,620 --> 01:12:03,470
večja od elementa
da gledaš?

1672
01:12:03,470 --> 01:12:05,540
In odgovor je da, kajne?

1673
01:12:05,540 --> 01:12:11,275
4 je večji od 3 in j
2, tako da je ta koda izvede.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Torej, kaj zdaj počnemo niz na
2, tako da tukaj smo jih zamenjali.

1676
01:12:18,550 --> 01:12:25,620
Tako smo samo reči, OK, matrika
na 2 je zdaj bo 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
In j bo enaka
j minus 1, ki je 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
To je grozno, ampak
vi dobili idejo.

1681
01:12:37,200 --> 01:12:38,360
J je sedaj enaka 1.

1682
01:12:38,360 --> 01:12:44,360
In j matrika se pravkar bo
enako naš element, ki je bil 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
I izbrisati nekaj, kar ne bi smel
imajo ali miswrote nekaj,

1685
01:12:48,570 --> 01:12:49,910
ampak vi dobili idejo.

1686
01:12:49,910 --> 01:12:50,640
>> To se premaknete na n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
In potem, če bi bila ta, da bi se zanka
Ponovno bi bilo reči, OK, j je 1 zdaj.

1689
01:12:57,960 --> 01:13:00,665
In niz j minus 1 je zdaj 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Je 2 manj kot naš element?

1692
01:13:03,760 --> 01:13:04,540
Ne?

1693
01:13:04,540 --> 01:13:07,970
To pomeni, da smo jih
Vstavi ta element

1694
01:13:07,970 --> 01:13:10,110
v pravem mestu v naši sortirane array.

1695
01:13:10,110 --> 01:13:14,400
Potem lahko to traja in smo rekli,
OK, naša sortirani array je tukaj.

1696
01:13:14,400 --> 01:13:19,940
In bi bilo potrebno to številko 6 in se
všeč, OK, je 6 manj kot to številko?

1697
01:13:19,940 --> 01:13:20,480
Ne?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
Mi smo v redu.

1700
01:13:22,680 --> 01:13:23,530
>> Še enkrat.

1701
01:13:23,530 --> 01:13:24,740
Pravimo, 7.

1702
01:13:24,740 --> 01:13:29,010
Je 7 manj kot konec
naše urejenem niz?

1703
01:13:29,010 --> 01:13:29,520
No.

1704
01:13:29,520 --> 01:13:30,430
Tako da smo v redu.

1705
01:13:30,430 --> 01:13:32,760
Tako da bo to urejeno.

1706
01:13:32,760 --> 01:13:38,610
V bistvu je vse to počne
se govori vzemi

1707
01:13:38,610 --> 01:13:42,060
Prvi element
Vaše razvrščeni matrika,

1708
01:13:42,060 --> 01:13:46,010
ugotoviti, kam gre
v urejenem niz.

1709
01:13:46,010 --> 01:13:48,780
In to samo skrbi
zamenjav za to.

1710
01:13:48,780 --> 01:13:51,300
Ti si v bistvu samo zamenjavo
dokler ne bo na pravem mestu.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Vizualna podoba je, da ste
gibljejo vse navzdol s tem.

1713
01:13:56,990 --> 01:13:59,420
>> Torej, to je, kot pol balona vrsta-posestnik.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Oglejte si študijo 50.

1716
01:14:03,420 --> 01:14:06,000
Toplo priporočam poskuša
kodo to sami.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Če imate kakršnakoli vprašanja ali želite
glej vzorčno kodo za vstavljanje vrste,

1719
01:14:12,450 --> 01:14:13,750
prosim povej mi.

1720
01:14:13,750 --> 01:14:14,500
Jaz sem vedno okoli.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Torej v najslabšem primeru runtime
in najboljši primer runtime.

1723
01:14:20,200 --> 01:14:30,700
Kot ste videli fant iz tabele sem že
ti so pokazali, da je tako n kvadrati n.

1724
01:14:30,700 --> 01:14:35,590
>> Tako nekako gredo dol, kaj smo se pogovarjali
o z našimi prejšnjimi vrstami, najslabša

1725
01:14:35,590 --> 01:14:38,760
Primer runtime je, da če
to je popolnoma Nerazvrščene,

1726
01:14:38,760 --> 01:14:42,530
moramo primerjati vse te n-kratne.

1727
01:14:42,530 --> 01:14:47,020
Mi cel kup primerjav
ker če je to v obratnem vrstnem redu,

1728
01:14:47,020 --> 01:14:50,360
bomo rekli, v redu, to
je isti, to je dobro,

1729
01:14:50,360 --> 01:14:54,650
in to bo treba primerjati
pred prvo se preselil nazaj.

1730
01:14:54,650 --> 01:14:56,710
In ko pridemo k
konec repa, imamo

1731
01:14:56,710 --> 01:14:59,440
za primerjavo, primerjati in
primerjati proti vsemu.

1732
01:14:59,440 --> 01:15:03,030
>> Tako da konča se
približno n kvadrat.

1733
01:15:03,030 --> 01:15:09,510
Če je pravilna, potem ste
reči, OK, 2, si dober.

1734
01:15:09,510 --> 01:15:11,330
3, ste v primerjavi z 2.

1735
01:15:11,330 --> 01:15:12,310
Ste dobri.

1736
01:15:12,310 --> 01:15:14,150
4, ki ste jo pravkar primerjati z repom.

1737
01:15:14,150 --> 01:15:14,990
Ste dobri.

1738
01:15:14,990 --> 01:15:17,140
6, primerjati z repom, da ste v redu.

1739
01:15:17,140 --> 01:15:20,870
Torej, za vsako mesto, če je že
razporejene, delaš eno primerjavo.

1740
01:15:20,870 --> 01:15:22,320
Torej, to je samo n.

1741
01:15:22,320 --> 01:15:26,840
In ker imamo najboljšo prakso runtime
n in najslabši runtime n

1742
01:15:26,840 --> 01:15:28,680
kvadrat, nimamo pričakovan čas delovanja.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Odvisno je le od
kaos našem seznamu tam.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
In še enkrat, drugo
Graf in drugo mizo.

1747
01:15:39,530 --> 01:15:41,170
Torej razlike med vrstami.

1748
01:15:41,170 --> 01:15:44,180
Jaz sem le, da bo vetrič skozi, sem
Počutim se, kot smo obširno govoril

1749
01:15:44,180 --> 01:15:46,570
o tem, kako vse vrste
lahko spreminja in povezati.

1750
01:15:46,570 --> 01:15:50,564
Torej zlivanjem je zadnja
Ti se rodila fantje s.

1751
01:15:50,564 --> 01:15:52,105
Imamo precej barvito sliko.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Torej zlivanjem je rekurzivni algoritem.

1754
01:15:56,040 --> 01:15:59,910
Torej, fantje vedo, kaj
rekurzivna funkcija?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Kdo želel povedati?

1757
01:16:03,320 --> 01:16:04,739
Želite poskusiti?

1758
01:16:04,739 --> 01:16:07,280
Torej rekurzivna funkcija je samo
funkcija, ki sebe imenuje.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Torej, če ste fantje poznajo
z Fibonaccijevega zaporedja,

1761
01:16:11,590 --> 01:16:15,670
da se šteje, rekurzivna, ker
ste vzeli prejšnji dve

1762
01:16:15,670 --> 01:16:17,530
in jih dodajte skupaj
da dobite naslednjo.

1763
01:16:17,530 --> 01:16:21,440
Torej rekurzivni, sem vedno mislim
rekurzije kot kot spiralo

1764
01:16:21,440 --> 01:16:24,430
tako ste kot spirala navzdol vanj.

1765
01:16:24,430 --> 01:16:27,150
Ampak to je samo funkcija
ki sebe imenuje.

1766
01:16:27,150 --> 01:16:32,660
>> In dejansko, res hitro sem
Lahko ti pokažem, kaj to izgleda.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Torej rekurzivna tukaj, če pogledamo, da je to
rekurzivni način, da se sešteje v array.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Torej vse, kar moramo storiti, je
imamo funkcijo vsote

1771
01:16:47,880 --> 01:16:52,210
Vsota, ki traja velikost in vrsto.

1772
01:16:52,210 --> 01:16:55,210
In, če ste opazili, velikost
postopno znižanje po enem vsakič.

1773
01:16:55,210 --> 01:17:00,365
In vse kar naredi je, če je x enak
zero-- tako da, če velikost polja

1774
01:17:00,365 --> 01:17:02,710
je enako zero-- vrne nič.

1775
01:17:02,710 --> 01:17:10,440
>> Sicer pa povzema to
Zadnji element matrike,

1776
01:17:10,440 --> 01:17:14,790
in potem traja vsoto
Preostali del matrike.

1777
01:17:14,790 --> 01:17:17,555
Torej, to je samo zrušijo
v manjše in manjše težave.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Skrajšam zgodbo, rekurzija,
funkcija, ki sebe imenuje.

1780
01:17:21,890 --> 01:17:25,740
Če je to vse kar imaš od tega,
to je tisto, rekurzivna funkcija.

1781
01:17:25,740 --> 01:17:29,870
Če ste vzeli 51, boste dobili zelo,
zelo zadovoljni z rekurzije.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
To je res kul.

1784
01:17:32,370 --> 01:17:34,660
Je bilo smiselno na podobno
03:00 eno noč ven.

1785
01:17:34,660 --> 01:17:37,900
In sem si mislil, zakaj
nisem nikoli uporabljati to?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Torej za urejanje z zlivanjem, v bistvu
kaj se dogaja, da storiti, je, da je

1788
01:17:42,430 --> 01:17:45,620
tekoč, da ga razčleniti in ga zlomil
navzdol, dokler je samo posamezni elementi.

1789
01:17:45,620 --> 01:17:47,570
Se posamezni elementi so enostavno rešiti.

1790
01:17:47,570 --> 01:17:48,070
Vidimo, da.

1791
01:17:48,070 --> 01:17:50,760
Če imate samo en element, to je
že šteje razvrščeni.

1792
01:17:50,760 --> 01:17:53,800
Torej na vhod n elementov,
če je n manj kot 2,

1793
01:17:53,800 --> 01:17:58,120
Samo vrnejo ker ta sredstva
to je lahko samo 0 ali 1, kot smo videli.

1794
01:17:58,120 --> 01:18:00,050
Tistih, ki se štejejo za Urejeni elementi.

1795
01:18:00,050 --> 01:18:02,170
>> V nasprotnem primeru ga zlomil na pol.

1796
01:18:02,170 --> 01:18:06,336
Razvrstiti v prvi polovici, razvrščanje sekundo
jih pol, in nato združi skupaj.

1797
01:18:06,336 --> 01:18:07,460
Zakaj se imenuje zlivanjem.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Torej imamo tu bomo rešiti te.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Tako smo ostali jih imajo
dokler velikost polja je 1.

1802
01:18:17,210 --> 01:18:20,790
Torej, ko je 1, smo pravkar vrnil
ker je to sortirani matrika,

1803
01:18:20,790 --> 01:18:23,940
in to je sortirani matrika, in da je
sortirani matrika, smo vsi razporejene.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Torej, kaj moramo storiti, je nam
jih začele združitvijo.

1806
01:18:29,420 --> 01:18:31,820
>> Torej, kako si lahko
pomislite spajanje

1807
01:18:31,820 --> 01:18:36,240
ste pravkar odstranili manjše
število vsakega izmed pod nizi

1808
01:18:36,240 --> 01:18:38,330
in samo dodajte na pojavila array.

1809
01:18:38,330 --> 01:18:44,290
Torej, če pogledaš tukaj, ko imamo
ti sklopi imamo 4, 6 in 1.

1810
01:18:44,290 --> 01:18:47,280
Ko želimo združiti ti,
gledamo na teh prvih dveh

1811
01:18:47,280 --> 01:18:50,730
in smo rekli, v redu, 1 manjša,
gre za spredaj.

1812
01:18:50,730 --> 01:18:54,330
4 in 6, ni nič za primerjavo
je, jo samo označite na koncu.

1813
01:18:54,330 --> 01:18:58,020
>> Ko združimo ta dva, smo samo
vzemite manjši eno od teh dveh,

1814
01:18:58,020 --> 01:18:59,310
tako da je 1.

1815
01:18:59,310 --> 01:19:01,690
In zdaj bomo
manjši od teh dveh, SO 2.

1816
01:19:01,690 --> 01:19:03,330
Manjši od teh dveh, 3.

1817
01:19:03,330 --> 01:19:06,260
Manjši od teh dveh, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Torej ste pravkar potegnete teh.

1819
01:19:08,630 --> 01:19:11,210
In ker oni '
bilo prej urejeno,

1820
01:19:11,210 --> 01:19:14,300
imate le eno
Primerjava vsakič tam.

1821
01:19:14,300 --> 01:19:19,610
Zato bolj koda tukaj, samo predstavitev.

1822
01:19:19,610 --> 01:19:24,410
Tako da začnete na sredini in
si nekako levo in desno

1823
01:19:24,410 --> 01:19:26,180
in potem samo združiti tiste.

1824
01:19:26,180 --> 01:19:30,080
>> In nimamo kodo
za spajanje tukaj.

1825
01:19:30,080 --> 01:19:34,110
Ampak, še enkrat, če greste na
študija 50, bo pa tam.

1826
01:19:34,110 --> 01:19:36,860
V nasprotnem primeru pride govoriti z mano
Če ste še vedno zmeden.

1827
01:19:36,860 --> 01:19:42,340
Tako kul stvar tukaj je, da je najboljši primer,
v najslabšem primeru, in pričakuje, runtime

1828
01:19:42,340 --> 01:19:46,250
so vsi v dnevniku n, ki
je veliko bolje, kot smo jih

1829
01:19:46,250 --> 01:19:48,000
gledati do konca naših vrst.

1830
01:19:48,000 --> 01:19:51,840
Smo videli n smo na kvadrat
in kaj smo dejansko

1831
01:19:51,840 --> 01:19:54,380
tu je n log n, kar je super.

1832
01:19:54,380 --> 01:19:55,830
>> Poglejte, kako veliko bolje, da je.

1833
01:19:55,830 --> 01:19:56,780
Takšno lepo krivuljo.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Toliko bolj učinkovito.

1836
01:20:00,120 --> 01:20:03,510
Če si kdaj lahko, uporaba zlivanjem.

1837
01:20:03,510 --> 01:20:04,810
To vam bo prihranilo čas.

1838
01:20:04,810 --> 01:20:07,670
Potem spet, kot smo rekli, če
ste v tej spodnjem območju,

1839
01:20:07,670 --> 01:20:09,480
to ne pomeni, da da
veliko razliko.

1840
01:20:09,480 --> 01:20:11,360
Prideš do tisoč
in na tisoče vložkov,

1841
01:20:11,360 --> 01:20:13,318
boste zagotovo želeli
učinkovitejši algoritem.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
In, še enkrat, naša lepa tabela vse
vrste, da vidva danes naučili.

1844
01:20:19,400 --> 01:20:21,157
>> Torej, vem, da je bilo gosto dan.

1845
01:20:21,157 --> 01:20:23,490
To se ne gredo nujno
da vam pomaga z vašo pset.

1846
01:20:23,490 --> 01:20:28,250
Ampak jaz samo želim, da bi odklonitev
da oddelek ne gre le za psets.

1847
01:20:28,250 --> 01:20:31,240
Vse to gradivo je pošteno
Igra za vaše kolokviji.

1848
01:20:31,240 --> 01:20:35,430
In tudi, če ne nadaljujemo s CS,
to so res pomembne osnove

1849
01:20:35,430 --> 01:20:37,870
da bi morali vedeti.

1850
01:20:37,870 --> 01:20:41,700
Tako da bo nekaj dni bo
malo več pset pomoč,

1851
01:20:41,700 --> 01:20:44,600
vendar pa bo nekaj tednov se
veliko bolj dejanska vsebina

1852
01:20:44,600 --> 01:20:46,600
da se morda ne zdi super
koristno za vas prav zdaj,

1853
01:20:46,600 --> 01:20:51,215
ampak obljubim, če boste še naprej
na bo zelo, zelo koristno.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Torej, to je to za oddelek.

1856
01:20:54,250 --> 01:20:55,250
Do žice.

1857
01:20:55,250 --> 01:20:56,570
To sem naredil v eni minuti.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Vendar pa greste.

1860
01:20:58,970 --> 01:21:01,240
In imam krofe ali sladkarije.

1861
01:21:01,240 --> 01:21:03,464
Je kdo alergičen na
kaj, mimogrede?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Jajca in mleko.

1864
01:21:05,890 --> 01:21:08,120
Torej, krofi so no?

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
Vse je v redu.

1868
01:21:10,770 --> 01:21:12,120
Čokolada ne?

1869
01:21:12,120 --> 01:21:12,620
Zvezdnimi.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Zvezdne so dobri.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Bomo imeli
Eksplozija, nato pa naslednji teden.

1874
01:21:17,045 --> 01:21:18,240
To je tisto, kar bom.

1875
01:21:18,240 --> 01:21:19,690
Vi fantje so super teden.

1876
01:21:19,690 --> 01:21:20,460
Preberite si spec.

1877
01:21:20,460 --> 01:21:22,130
>> Pustite me, če imate kakršnakoli vprašanja.

1878
01:21:22,130 --> 01:21:25,300
Pset dve stopnji mora biti
da se vam do četrtka.

1879
01:21:25,300 --> 01:21:28,320
Če imate vprašanja
o tem, kako sem se razvrščajo nekaj

1880
01:21:28,320 --> 01:21:32,250
ali zakaj sem se razvrščajo nekaj tako, kot sem
tokrat, prosim email mi, pridi govoriti z mano.

1881
01:21:32,250 --> 01:21:34,210
Jaz sem malo nor to
teden, ampak obljubim

1882
01:21:34,210 --> 01:21:36,340
Jaz bom še vedno odgovoriti v roku 24 ur.

1883
01:21:36,340 --> 01:21:38,240
Torej imajo velik teden, vsem.

1884
01:21:38,240 --> 01:21:40,090
Vso srečo na vaši pset.

1885
01:21:40,090 --> 01:21:41,248