1
00:00:00,000 --> 00:00:03,332
>> [Predvaja glasba]

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Dobrodošli v tednu 3 oddelka.

3
00:00:06,490 --> 00:00:09,550
Hvala, fantje, za vse, ki prihajajo
na ta zgodnejši čas že danes.

4
00:00:09,550 --> 00:00:11,466
Imamo lepo, malo
intimna danes skupina.

5
00:00:11,466 --> 00:00:14,570
Torej, upam, da bomo prišli do
konča, morda, zgodaj,

6
00:00:14,570 --> 00:00:15,780
malo zgodaj danes.

7
00:00:15,780 --> 00:00:22,057
Tako hitro, samo nekateri
Sporočila za dnevni red danes.

8
00:00:22,057 --> 00:00:23,890
Preden začnemo, smo
bo šele iti čez

9
00:00:23,890 --> 00:00:28,910
nekaj kratkih logistične zadeve, pset
Vprašanja, debrief, take stvari.

10
00:00:28,910 --> 00:00:30,250
In potem bomo potopite v desno.

11
00:00:30,250 --> 00:00:34,710
Bomo uporabili razhroščevalnik imenovano GDB za
začetek debunking našo kodo, ki David

12
00:00:34,710 --> 00:00:36,550
pojasnjeno v predavanju drugi dan.

13
00:00:36,550 --> 00:00:39,420
Mi bomo šli čez štiri vrste vrst.

14
00:00:39,420 --> 00:00:42,310
Bomo šli nad njimi precej hitro
ker oni so precej intenzivna.

15
00:00:42,310 --> 00:00:45,710
Toda vemo, da vse drsi in
Izvorna koda so vedno na spletu.

16
00:00:45,710 --> 00:00:50,810
Torej, vas prosimo, na vaše podatke, da
pojdi nazaj in poglej na to.

17
00:00:50,810 --> 00:00:53,930
>> Šli bomo skozi
asimptotska zapis, ki

18
00:00:53,930 --> 00:00:55,944
je samo fancy način
rekel "runtimes"

19
00:00:55,944 --> 00:00:58,360
kjer imamo veliko O, ki je
David je pojasnjeno v predavanju.

20
00:00:58,360 --> 00:01:01,550
In imamo tudi Omega, ki je
je spodnja meja runtime.

21
00:01:01,550 --> 00:01:06,450
In bomo govorili malo bolj
poglobljeno glede kako se ti delo.

22
00:01:06,450 --> 00:01:10,160
In nenazadnje, bomo šli preko binarnega iskanja,
saj veliko vas, ki imajo že

23
00:01:10,160 --> 00:01:15,190
pogledala vaše psets verjetno veste, da
da je vprašanje, ki je v vašem pset.

24
00:01:15,190 --> 00:01:17,470
Tako boste vsi srečni
da pokrivamo to danes.

25
00:01:17,470 --> 00:01:20,610
>> In nenazadnje, na vaš
povratne oddelek, sem dejansko

26
00:01:20,610 --> 00:01:23,000
levo približno 15 minut pri
konec bi samo iti čez

27
00:01:23,000 --> 00:01:27,730
logistika pset3, vsa vprašanja,
Mogoče malo smernic, če hočete,

28
00:01:27,730 --> 00:01:28,990
preden začnemo programiranja.

29
00:01:28,990 --> 00:01:30,890
Torej poskusimo priti skozi
material zelo hitro.

30
00:01:30,890 --> 00:01:33,880
In potem bomo lahko preživeli nekaj časa
ob več vprašanj za pset.

31
00:01:33,880 --> 00:01:35,230
V REDU.

32
00:01:35,230 --> 00:01:39,570
>> Hitro, tako da je le nekaj
Sporočila preden začnemo danes.

33
00:01:39,570 --> 00:01:45,410
Prvič, dobrodošli k temu, da
je preko dveh vaših psets.

34
00:01:45,410 --> 00:01:49,432
Ogledal sem si na your-- ja, dajmo
dobil aplavz za to.

35
00:01:49,432 --> 00:01:51,140
Pravzaprav sem bil res,
res navdušena.

36
00:01:51,140 --> 00:01:55,800
Jaz ocenjena prvo pset za vas
Prejšnji teden in vidva storila neverjetno.

37
00:01:55,800 --> 00:01:58,290
>> Style je bil na mestu
poleg nekaj pripomb.

38
00:01:58,290 --> 00:02:00,660
Poskrbite, da boste vedno
komentiral svojo kodo.

39
00:02:00,660 --> 00:02:03,040
Ampak tvoji psets bili na mestu.

40
00:02:03,040 --> 00:02:05,549
In ne odnehaj.

41
00:02:05,549 --> 00:02:08,090
In to je dobro za greder do
glej, da se vidva dajanje

42
00:02:08,090 --> 00:02:10,704
v toliko truda v vašem slogu
in vaš design v kodi

43
00:02:10,704 --> 00:02:12,120
da bi radi, da vidiš.

44
00:02:12,120 --> 00:02:16,450
Tako da sem mimo po moje hvaležnosti
za ostale ZU.

45
00:02:16,450 --> 00:02:19,210
>> Vendar pa obstajajo
Nekaj ​​debrief vprašanja

46
00:02:19,210 --> 00:02:22,010
Rad bi šel čez, da
bi tako moje življenje

47
00:02:22,010 --> 00:02:24,900
in veliko drugih
TAS "živi malo lažje.

48
00:02:24,900 --> 00:02:28,220
Najprej sem opazil to
mimo week-- koliko od vas

49
00:02:28,220 --> 00:02:32,301
so bili teče check50 na
svojo kodo pred vami predložiti?

50
00:02:32,301 --> 00:02:32,800
V REDU.

51
00:02:32,800 --> 00:02:36,690
Torej, vsi bi morali početi check50,
because-- secret-- smo dejansko

52
00:02:36,690 --> 00:02:41,540
teči check50 kot del naše resničnosti
skripte za testiranje kodo.

53
00:02:41,540 --> 00:02:45,480
Torej, če je vaša koda ni
check50, po vsej verjetnosti,

54
00:02:45,480 --> 00:02:47,570
to je verjetno, da bo
ne naše ček kot dobro.

55
00:02:47,570 --> 00:02:49,320
Včasih si fantje
imate prave odgovore.

56
00:02:49,320 --> 00:02:52,200
Tako kot v požrešen, nekateri
imate prave številke,

57
00:02:52,200 --> 00:02:53,960
si izpisal nekaj dodatnih stvari.

58
00:02:53,960 --> 00:02:55,940
In da ekstra stvari
dejansko ne opravi pregled,

59
00:02:55,940 --> 00:02:58,440
ker računalnik ne
vem, kaj je to išče.

60
00:02:58,440 --> 00:03:00,981
In tako bo to šele teči skozi,
vidite, da vaša proizvodnja ne

61
00:03:00,981 --> 00:03:03,810
ujemajo kaj pričakujemo odgovor
biti, in označiti, da je narobe.

62
00:03:03,810 --> 00:03:06,560
>> In vem, da se je zgodilo v
nekatere od vaših primerov ta teden.

63
00:03:06,560 --> 00:03:09,870
Zato sem šel nazaj in ročno
ponovno razvrstijo kodo vsakogar.

64
00:03:09,870 --> 00:03:12,780
V prihodnosti, čeprav,
Prosim, vas prosimo, poskrbite,

65
00:03:12,780 --> 00:03:14,570
da tečete
preveriti 50 na kodo.

66
00:03:14,570 --> 00:03:17,970
Ker je to neke vrste bolečin TA
bi moral iti nazaj in ročno razvrstijo

67
00:03:17,970 --> 00:03:21,197
vsak pset za vsak
eno, malo zamudil instance.

68
00:03:21,197 --> 00:03:22,530
Torej nisem vzlet nobenih točk.

69
00:03:22,530 --> 00:03:25,210
Mislim, da sem odpeljal morda
eden ali dva za oblikovanje.

70
00:03:25,210 --> 00:03:27,710
V prihodnosti, čeprav, če
ste ni check50,

71
00:03:27,710 --> 00:03:31,330
Točke bodo sprejeti
off za pravilnost.

72
00:03:31,330 --> 00:03:35,020
>> Poleg tega so psets
ob petkih opoldne.

73
00:03:35,020 --> 00:03:38,990
Mislim, da je sedem minut
pozno odlog plačila, ki vam daje.

74
00:03:38,990 --> 00:03:42,434
Per Harvard časa, oni dovoljeno
bilo sedem minut prepozno za vse.

75
00:03:42,434 --> 00:03:44,350
Torej, tukaj na univerzi Yale, bomo
upoštevati tudi to.

76
00:03:44,350 --> 00:03:47,910
Ampak precej, ob 12:07,
če vaš pset ni,

77
00:03:47,910 --> 00:03:49,720
to se dogaja, da se označi kot prepozno.

78
00:03:49,720 --> 00:03:53,160
In tako, medtem ko je označen
kot prepozno, TA-- sem

79
00:03:53,160 --> 00:03:54,870
še vedno dogaja, da se razvrščanje vaših psets.

80
00:03:54,870 --> 00:03:56,760
Tako boste še vedno videli razred prikazani.

81
00:03:56,760 --> 00:03:58,820
Vendar pa vemo, da na
konec semestra,

82
00:03:58,820 --> 00:04:02,270
vse poznih psets bo zgolj
samodejno nastavi na ničlo računalnik.

83
00:04:02,270 --> 00:04:04,490
>> To smo storili iz dveh razlogov.

84
00:04:04,490 --> 00:04:09,220
Ena, včasih smo dobili
opravičil, kot izgovore dekana,

85
00:04:09,220 --> 00:04:10,762
kasneje, da ne vem, o tem še ni.

86
00:04:10,762 --> 00:04:13,761
Tako smo želeli zagotoviti, da smo razvrščanje
vse samo v primeru, kot, da sem

87
00:04:13,761 --> 00:04:15,080
manjka izgovora Dean je.

88
00:04:15,080 --> 00:04:17,000
In drugič, da v
Um, lahko še vedno

89
00:04:17,000 --> 00:04:19,370
spusti en pset da
ima celotno področje točk.

90
00:04:19,370 --> 00:04:21,430
In tako smo želeli razred
vse vaše psets samo

91
00:04:21,430 --> 00:04:24,730
se prepričajte, da je vaše področje je
tam in si jih poskušam.

92
00:04:24,730 --> 00:04:29,150
Torej, tudi če je prepozno, boste še vedno
dobili kredit za obseg točk, mislim.

93
00:04:29,150 --> 00:04:33,730
>> Torej Nauk je zgodba, da
prepričajte, da vaš psets so na čas.

94
00:04:33,730 --> 00:04:38,350
In če niso v na čas,
vem, da to ni dobro.

95
00:04:38,350 --> 00:04:41,678
Ja, preden sem korak naprej, ali ima kdo
vsa vprašanja v zvezi z pset povratne informacije?

96
00:04:41,678 --> 00:04:42,178
Ja.

97
00:04:42,178 --> 00:04:43,630
>> OBČINSTVO: Ste Pravimo
lahko spusti eno od psets?

98
00:04:43,630 --> 00:04:44,296
>> ANDI PENG: Ja.

99
00:04:44,296 --> 00:04:47,050
Torej je skupna devet psets
tekom semestra.

100
00:04:47,050 --> 00:04:50,610
In če imate obseg
points-- tako področje je le,

101
00:04:50,610 --> 00:04:53,567
precej, so si poskusi
problem, ste dajanje v času,

102
00:04:53,567 --> 00:04:56,150
ste kažejo, da ste
dokazali ste prebrali spec.

103
00:04:56,150 --> 00:04:57,191
To je precej možnosti.

104
00:04:57,191 --> 00:04:59,370
In če ste izpolnjevanju
obseg točk smo

105
00:04:59,370 --> 00:05:03,360
lahko spusti najnižja
eden od polnega obsega.

106
00:05:03,360 --> 00:05:06,790
Tako da je v vašo korist
dokončanje in poskusite vsak pset.

107
00:05:06,790 --> 00:05:10,320
>> Tudi upload-- če nobeden od
njihovo delo, jih vse naložiti.

108
00:05:10,320 --> 00:05:13,711
In potem se bomo, upajmo, lahko
vam nekatere od teh točk nazaj.

109
00:05:13,711 --> 00:05:14,210
Cool.

110
00:05:14,210 --> 00:05:16,780
Vsa druga vprašanja?

111
00:05:16,780 --> 00:05:17,840
Great.

112
00:05:17,840 --> 00:05:21,960
>> Drugič, pisarna hours-- nekaj
Hitre opombe o uradnih ur.

113
00:05:21,960 --> 00:05:24,300
Torej, najprej, pridite zgodaj v tednu.

114
00:05:24,300 --> 00:05:26,909
Nihče ni nikoli na
Uradne ure ob ponedeljkih.

115
00:05:26,909 --> 00:05:28,700
Christabel prišel do
Uradne ure sinoči.

116
00:05:28,700 --> 00:05:29,691
Ja, Christabel.

117
00:05:29,691 --> 00:05:32,190
In kaj imamo v pisarni
ur sinoči, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> OBČINSTVO: Imeli smo sladoled.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Torej, to je pravica, smo imeli
sladoled na uradnih ur sinoči.

120
00:05:36,160 --> 00:05:39,390
Medtem ko vam ne morem obljubiti, da
bomo imeli sladoled na uradnih ur

121
00:05:39,390 --> 00:05:43,230
vsak teden, kaj se ti lahko obljubim
je, da bo prišlo do bistveno

122
00:05:43,230 --> 00:05:45,380
boljši študent razmerje TA.

123
00:05:45,380 --> 00:05:47,650
Tako kot zakonit, je kot tri proti ena.

124
00:05:47,650 --> 00:05:50,350
Ker je kontrast, ki s
Četrtek, imaš približno 150

125
00:05:50,350 --> 00:05:52,830
Res je poudaril, otroke in ne sladoled.

126
00:05:52,830 --> 00:05:55,360
In to je samo ni produktivno za vsakogar.

127
00:05:55,360 --> 00:05:58,730
Torej Nauk zgodbe je, pridite zgodaj
na uradnih ur in dobrih stvari

128
00:05:58,730 --> 00:06:00,310
se bo zgodilo.

129
00:06:00,310 --> 00:06:02,110
>> Prav tako pridejo pripravljeni, da postavljajo vprašanja.

130
00:06:02,110 --> 00:06:03,200
Ti veš?

131
00:06:03,200 --> 00:06:05,420
Glede na to, kaj ZU, I
mislim, so govorili:

132
00:06:05,420 --> 00:06:10,710
smo bili že par študentov
ki pridejo v četrtek ob, kot, 10:50

133
00:06:10,710 --> 00:06:15,100
ne, ko ste prebrali spec
da kot pomagajte mi, pomagajte mi.

134
00:06:15,100 --> 00:06:18,200
Žal na tej točki, tam je
ni veliko lahko storimo, da vam pomaga.

135
00:06:18,200 --> 00:06:19,590
Torej, prosim pridite zgodaj v tednu.

136
00:06:19,590 --> 00:06:22,040
Pridite zgodaj, da uradnih ur.

137
00:06:22,040 --> 00:06:23,350
Pridite pripravljeni zastaviti vprašanja.

138
00:06:23,350 --> 00:06:25,310
Poskrbite, da vas, kot
študent, tam, kjer

139
00:06:25,310 --> 00:06:27,620
morate biti tako, da
TAS lahko vas vodijo skupaj,

140
00:06:27,620 --> 00:06:32,850
ki je tisto, kar uradne ure
bi moral biti dodeljen za.

141
00:06:32,850 --> 00:06:37,380
>> Drugič, tako da vem, profesorje
radi, da nas preseneti s testi.

142
00:06:37,380 --> 00:06:39,439
Imel sem profesorja tiste
všeč, yo, mimogrede,

143
00:06:39,439 --> 00:06:41,230
Zapomnite si, da vmesno
imate naslednji ponedeljek.

144
00:06:41,230 --> 00:06:42,855
Ja, nisem vedel o tem vmesnimi.

145
00:06:42,855 --> 00:06:45,630
Tako da bom se, da TA
da vas spominja vse to kviz

146
00:06:45,630 --> 00:06:47,270
0--, saj veste, da smo CS.

147
00:06:47,270 --> 00:06:50,730
Zdaj, ko smo naredili nizi, dobiš
zakaj je kviz 0, ne kviz 1, eh?

148
00:06:50,730 --> 00:06:51,320
V REDU.

149
00:06:51,320 --> 00:06:52,490
Oh, imam nekaj smehlja o tem.

150
00:06:52,490 --> 00:06:53,120
V REDU.

151
00:06:53,120 --> 00:06:59,710
>> Torej bo kviz 0 bo 14. oktober, če
ste v oddelku ponedeljek-sreda

152
00:06:59,710 --> 00:07:02,920
in 15. oktober, če ste v
odsek torek-četrtek.

153
00:07:02,920 --> 00:07:05,630
To ne velja za
tiste, ki ste na Harvardu

154
00:07:05,630 --> 00:07:10,350
who-- Mislim, da boste vsi
jemanjem kvizi na 14..

155
00:07:10,350 --> 00:07:13,560
>> Torej, ja, naslednji teden, če
David, v predavanju, gre,

156
00:07:13,560 --> 00:07:15,747
ja, da o tem
Kviz naslednji teden, si vse

157
00:07:15,747 --> 00:07:17,580
ne bo šokiran, ker
ste prišli na oddelku

158
00:07:17,580 --> 00:07:19,664
in veš, da je vaš
kviz 0 je v dveh tednih.

159
00:07:19,664 --> 00:07:21,580
In bomo imeli pregled
Seje in vse.

160
00:07:21,580 --> 00:07:26,360
Torej, ne skrbi
se prestrašil za to.

161
00:07:26,360 --> 00:07:29,890
Vsa vprašanja before-- kakršnakoli vprašanja
na vseh glede logističnih vprašanj,

162
00:07:29,890 --> 00:07:32,591
razvrščanje, uradne ure, profili?

163
00:07:32,591 --> 00:07:33,090
Ja.

164
00:07:33,090 --> 00:07:35,100
>> OBČINSTVO: Torej je kviz
bo v predavanju?

165
00:07:35,100 --> 00:07:35,766
>> ANDI PENG: Ja.

166
00:07:35,766 --> 00:07:39,460
Torej kviza, mislim, da je 60
minut dodeljene v tem terminu

167
00:07:39,460 --> 00:07:42,240
da boste vzemite
v predavalnici.

168
00:07:42,240 --> 00:07:44,810
Torej vam ni treba priti v
na, kot je, naključni 7:00 PM.

169
00:07:44,810 --> 00:07:46,140
To je vse dobro.

170
00:07:46,140 --> 00:07:47,100
Ja.

171
00:07:47,100 --> 00:07:50,060
Cool.

172
00:07:50,060 --> 00:07:50,840
>> V redu.

173
00:07:50,840 --> 00:07:54,330
Torej bomo
uvesti koncept za vas

174
00:07:54,330 --> 00:08:00,760
ta teden, da je David že nekako
od dotaknila v predavanju to čez teden dni.

175
00:08:00,760 --> 00:08:02,010
To se imenuje GDB.

176
00:08:02,010 --> 00:08:05,570
In koliko od vas, medtem ko je v
potek pisanje psets,

177
00:08:05,570 --> 00:08:09,981
so opazili velik gumb, ki pravi,
"Debug" na vrhu IDE?

178
00:08:09,981 --> 00:08:10,480
V REDU.

179
00:08:10,480 --> 00:08:13,770
Torej, zdaj bomo dejansko dobili izkopala
skrivnost, kaj ta gumb dejansko

180
00:08:13,770 --> 00:08:14,270
počne.

181
00:08:14,270 --> 00:08:16,790
In zagotavljam vam, da je
lepa, lepa stvar.

182
00:08:16,790 --> 00:08:20,740
>> Torej, do sedaj, mislim,
tam je bilo dve stvari

183
00:08:20,740 --> 00:08:23,320
študenti so bili običajno
počeli, ko debugging psets.

184
00:08:23,320 --> 00:08:27,635
Ena, so bodisi dodate v
printf () - tako vsakih nekaj vrstic,

185
00:08:27,635 --> 00:08:29,760
so dodali v printf () -
oh, kaj je ta spremenljivka?

186
00:08:29,760 --> 00:08:32,551
Oh, kaj je ta spremenljivka now--
in si nekako videti napredovanje

187
00:08:32,551 --> 00:08:33,940
vaše kode, saj teče.

188
00:08:33,940 --> 00:08:37,030
Ali druga metoda otroci storiti, je,
da samo napisati celotno stvar

189
00:08:37,030 --> 00:08:38,610
in potem gredo takole na koncu.

190
00:08:38,610 --> 00:08:39,970
Upam, da to deluje.

191
00:08:39,970 --> 00:08:44,851
Zagotavljam vam, GDB je bolje
kot oba od teh metod.

192
00:08:44,851 --> 00:08:45,350
Ja.

193
00:08:45,350 --> 00:08:46,980
Torej, to bo vaš novi najboljši prijatelj.

194
00:08:46,980 --> 00:08:51,780
Ker je čudovita stvar
ki vizualno prikazuje oba

195
00:08:51,780 --> 00:08:54,850
kaj je vaša koda počne
na določeni točki

196
00:08:54,850 --> 00:08:57,486
kot tudi kar vse si
spremenljivke se prevažajo,

197
00:08:57,486 --> 00:08:59,610
všeč, kaj so njihove vrednote,
na tej določeni točki.

198
00:08:59,610 --> 00:09:02,670
In na ta način, si lahko res
nastavite prekinitvene točke v kodi.

199
00:09:02,670 --> 00:09:04,350
Lahko teči skozi linijo po liniji.

200
00:09:04,350 --> 00:09:07,324
In GDB bo samo še za
vi, prikazana za vas,

201
00:09:07,324 --> 00:09:09,490
kaj vse vaše spremenljivk
so, kaj počnejo,

202
00:09:09,490 --> 00:09:10,656
kaj se dogaja v kodeksu.

203
00:09:10,656 --> 00:09:13,240
In na tak način, da je
toliko lažje videti

204
00:09:13,240 --> 00:09:17,120
kaj namesto dogaja z printf-ing
ali zapišete vaše izjave.

205
00:09:17,120 --> 00:09:19,160
>> Torej bomo naredili zgled za to kasneje.

206
00:09:19,160 --> 00:09:20,660
Torej, to se zdi malo povzetek.

207
00:09:20,660 --> 00:09:23,490
Brez skrbi, bomo storili primere.

208
00:09:23,490 --> 00:09:29,170
In tako v bistvu tri največje,
najbolj uporabljenih funkcij, boste morali v GDB

209
00:09:29,170 --> 00:09:32,500
so Next, korak več,
in Korak v gumbov.

210
00:09:32,500 --> 00:09:34,860
Jaz grem čez glavo
tam, pravzaprav prav zdaj.

211
00:09:34,860 --> 00:09:40,930
>> Torej, vi vsi lahko videli, da
ali bi moral povečati malo?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
V zadnji, lahko vidite, da je?

214
00:09:44,470 --> 00:09:45,730
Naj povečavo?

215
00:09:45,730 --> 00:09:46,480
Samo malo?

216
00:09:46,480 --> 00:09:49,390
OK kul.

217
00:09:49,390 --> 00:09:50,280
Tam gremo.

218
00:09:50,280 --> 00:09:50,960
V REDU.

219
00:09:50,960 --> 00:09:57,000
>> Torej imam tukaj, moji
izvedba za požrešen.

220
00:09:57,000 --> 00:10:01,430
In medtem ko je veliko vaju napisal
požrešen v while form-- da

221
00:10:01,430 --> 00:10:04,890
je povsem sprejemljiv način, da to
it-- drug način za to je, da preprosto

222
00:10:04,890 --> 00:10:06,280
razdeliti v modulu.

223
00:10:06,280 --> 00:10:09,290
Ker potem lahko imate
vrednost, nato pa imajo svojo preostanek.

224
00:10:09,290 --> 00:10:11,150
In potem si lahko samo
jo dodajte vse skupaj.

225
00:10:11,150 --> 00:10:13,390
Ali logiko, kaj delam
tukaj smisla za vsakogar,

226
00:10:13,390 --> 00:10:14,117
preden začnemo?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Recimo?

229
00:10:17,980 --> 00:10:18,710
Cool.

230
00:10:18,710 --> 00:10:19,210
Great.

231
00:10:19,210 --> 00:10:21,290
To je zelo seksi kos
kode, bi rekel.

232
00:10:21,290 --> 00:10:23,502
Kot sem rekel, David, v
predavanje, čez nekaj časa,

233
00:10:23,502 --> 00:10:25,960
boste vsi začeli videvati kodo
kot nekaj, kar je lepo.

234
00:10:25,960 --> 00:10:29,950
In včasih, ko vidiš lepo
kodo, to je tako čudovit občutek.

235
00:10:29,950 --> 00:10:35,410
>> Torej kljub temu, medtem ko je ta številka, je zelo
lepa, ne deluje pravilno.

236
00:10:35,410 --> 00:10:37,750
Torej, kaj je teči check50 o tem.

237
00:10:37,750 --> 00:10:39,440
Preverite 50 20-- OOP.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
Je to pset2?

241
00:10:44,990 --> 00:10:46,870
Ja.

242
00:10:46,870 --> 00:10:47,520
Oh, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
V REDU.

245
00:10:52,890 --> 00:10:53,900
Tako smo teči check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> In kot lahko vi vidite tukaj,
to je ni nekaj primerov.

248
00:11:07,170 --> 00:11:10,165
In za nekatere od vas, v
seveda počne tvoj problem sklopov,

249
00:11:10,165 --> 00:11:11,110
ste kot, ah, zakaj se ne da delati.

250
00:11:11,110 --> 00:11:13,318
Zakaj je delal za nekatere
Vrednosti drugih pa ne?

251
00:11:13,318 --> 00:11:17,760
No, GDB se dogaja, da vam pomaga ugotoviti
zakaj ti vnosi niso bili zaposleni.

252
00:11:17,760 --> 00:11:18,320
>> V REDU.

253
00:11:18,320 --> 00:11:21,640
Torej, da vidimo, eno od
pregledih sem bil zatem check50

254
00:11:21,640 --> 00:11:24,920
je vhodna vrednost 0,41.

255
00:11:24,920 --> 00:11:27,830
Tako je pravilen odgovor, da je
morate biti pridobivanje je 4.

256
00:11:27,830 --> 00:11:33,090
Toda namesto da bi tisto, kar sem tiskanje
je 3-n, ki je napačna.

257
00:11:33,090 --> 00:11:36,190
Torej, kaj je samo teči to ročno, samo
poskrbite, da je check50 deluje.

258
00:11:36,190 --> 00:11:36,940
Naredimo ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Ups, moram narediti pohlepni.

261
00:11:43,340 --> 00:11:43,840
Tam gremo.

262
00:11:43,840 --> 00:11:44,381
Zdaj ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Koliko dolguje?

265
00:11:47,670 --> 00:11:49,550
Naredimo 0,41.

266
00:11:49,550 --> 00:11:52,590
In ja, vidimo tukaj
da je prikazovanje 3

267
00:11:52,590 --> 00:11:55,160
ko je pravilen odgovor,
Dejansko bi moral biti 4.

268
00:11:55,160 --> 00:12:01,460
Torej, kaj je vstop GDB in videli, kako
lahko greste o določitvi ta problem.

269
00:12:01,460 --> 00:12:03,992
>> Torej, prvi korak v
Vedno razhroščevanje kodo

270
00:12:03,992 --> 00:12:05,950
je, da nastavite prekinitveno točko,
ali je točka, na kateri ste

271
00:12:05,950 --> 00:12:09,079
želijo računalnika ali
razhroščevalnik za začetek gledaš.

272
00:12:09,079 --> 00:12:11,120
Torej, če ne boste res
vedo, kaj je tvoj problem,

273
00:12:11,120 --> 00:12:14,670
Ponavadi je tipična stvar, ki smo želeli
storiti, je, da našemu prelomne točke na glavni.

274
00:12:14,670 --> 00:12:18,520
Torej, če lahko vi to videli
rdeči gumb tam,

275
00:12:18,520 --> 00:12:22,860
Ja, to me je nastavljanju
Ustavljanje za glavno funkcijo.

276
00:12:22,860 --> 00:12:24,130
Sem kliknite to.

277
00:12:24,130 --> 00:12:26,130
>> In potem sem lahko šel na moj gumb Debug.

278
00:12:26,130 --> 00:12:27,036
Sem udaril ta gumb.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Naj povečavo nazaj ven, če bom lahko.

281
00:12:36,555 --> 00:12:38,020
Tam gremo.

282
00:12:38,020 --> 00:12:40,730
Torej imamo tu, na plošči na desni strani.

283
00:12:40,730 --> 00:12:43,680
Žal mi je, fantje v hrbtu, vi
ne morem videti zelo dobro.

284
00:12:43,680 --> 00:12:49,090
Ampak v bistvu, vse
ta pravica plošča počne

285
00:12:49,090 --> 00:12:53,130
se sledenja tako poudarjeno
linija, ki je linija kode

286
00:12:53,130 --> 00:12:56,640
da je računalnik trenutno izvaja,
kakor tudi vse vaše spremenljivk

287
00:12:56,640 --> 00:12:57,600
tukaj.

288
00:12:57,600 --> 00:13:00,487
>> Torej imaš centov, kovance, n,
Vse razglašena za različne stvari

289
00:13:00,487 --> 00:13:01,070
na tej točki.

290
00:13:01,070 --> 00:13:04,850
Brez skrbi, saj imamo dejansko ne
jih initialized na vseh spremenljivk še.

291
00:13:04,850 --> 00:13:07,200
Torej, v vašem računalniku, si
Računalnik je samo videti,

292
00:13:07,200 --> 00:13:14,376
oh, 32.767 je bila nazadnje uporabljali funkcijo
te pomnilniškega prostora v mojem računalniku.

293
00:13:14,376 --> 00:13:16,000
In tako, da je, kjer je trenutno centov.

294
00:13:16,000 --> 00:13:19,360
Ampak ne, da ko enkrat zaženete kodo,
to bi morala postati inicializiran.

295
00:13:19,360 --> 00:13:24,110
>> Torej, pojdimo skozi črto, ki jo
linija, kaj se dogaja tukaj.

296
00:13:24,110 --> 00:13:25,350
V REDU.

297
00:13:25,350 --> 00:13:29,400
Torej, tukaj so trije
gumbi, da sem samo pojasnil.

298
00:13:29,400 --> 00:13:34,090
Imate igrati, ali funkcijo Run,
gumb, imate Korak gumb nad,

299
00:13:34,090 --> 00:13:36,600
in imate tudi korak v gumb.

300
00:13:36,600 --> 00:13:41,260
In v bistvu, vse tri
jim pojdite skozi kodo

301
00:13:41,260 --> 00:13:42,690
in različne stvari.

302
00:13:42,690 --> 00:13:45,680
>> Torej ponavadi, ko ste debugging,
ne želimo, da samo hit Predvajaj,

303
00:13:45,680 --> 00:13:47,930
ker igra bo samo teči
kodo do konca tega.

304
00:13:47,930 --> 00:13:49,070
In potem ne bo dejansko
vedo, kaj je tvoj problem

305
00:13:49,070 --> 00:13:51,432
je razen če ste nastavili več prelomnih točk.

306
00:13:51,432 --> 00:13:53,890
Če ste nastavili več mejne vrednosti,
To bo šele samodejno

307
00:13:53,890 --> 00:13:56,030
teči od enega mejnimi vrednostmi,
na naslednjo, na naslednjo.

308
00:13:56,030 --> 00:13:58,030
Ampak v tem primeru, ki smo jih
samo, da je eden, ker smo

309
00:13:58,030 --> 00:13:59,970
želijo delati naš način
od zgoraj navzdol proti dnu.

310
00:13:59,970 --> 00:14:04,830
Torej bomo prezreti, da je gumb
zdaj za namene tega programa.

311
00:14:04,830 --> 00:14:08,230
>> Torej je korak nad funkcijo samo
koraki nad vsako posamezno vrstico

312
00:14:08,230 --> 00:14:11,510
in vam pove, kaj
računalnik počne.

313
00:14:11,510 --> 00:14:14,630
Step v funkciji gre
v dejanske funkcije

314
00:14:14,630 --> 00:14:16,000
da je na vašem vrstico kode.

315
00:14:16,000 --> 00:14:19,070
Tako na primer, kot printf (),
da je funkcija, kajne?

316
00:14:19,070 --> 00:14:21,980
Če sem želel fizično korak
v (funkciji printf),

317
00:14:21,980 --> 00:14:25,610
Jaz bi dejansko šel v kosu
številka, kjer se je printf () pisno in videli

318
00:14:25,610 --> 00:14:26,730
kaj se dogaja tam.

319
00:14:26,730 --> 00:14:29,924
>> Vendar je običajno, predpostavimo, da
koda, ki vam daje deluje.

320
00:14:29,924 --> 00:14:31,340
Predpostavljamo printf () deluje.

321
00:14:31,340 --> 00:14:33,170
Domnevamo, da GetInt () deluje.

322
00:14:33,170 --> 00:14:35,170
Tako da ni potrebe, da
korak v teh funkcij.

323
00:14:35,170 --> 00:14:37,170
Ampak, če je nalog
da ste sami napisali

324
00:14:37,170 --> 00:14:39,060
ki ga želite preveriti
izvedeti, kaj se dogaja,

325
00:14:39,060 --> 00:14:41,200
bi si želeli, da okrepijo
v tej funkciji.

326
00:14:41,200 --> 00:14:43,940
>> Torej, zdaj smo le, da bo
korak nad tem delom kodeksa.

327
00:14:43,940 --> 00:14:44,485
Torej, poglejmo.

328
00:14:44,485 --> 00:14:46,547
Oh, print, "Oh hai, kako
veliko sprememb dolguje? "

329
00:14:46,547 --> 00:14:47,130
Mi ne skrbi.

330
00:14:47,130 --> 00:14:49,830
Vemo, da se delajo,
tako da stopimo nad njim.

331
00:14:49,830 --> 00:14:53,290
>> Tako n, ki je naša plovec da
smo jih initialized-- ali declared--

332
00:14:53,290 --> 00:14:56,810
na vrhu, smo zdaj
ki je enaka da GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Torej, kaj je korak čez to.

334
00:14:57,810 --> 00:14:59,580
In mi vidimo na
dno tukaj, program

335
00:14:59,580 --> 00:15:03,360
me spodbudilo k vhodu vrednost.

336
00:15:03,360 --> 00:15:08,580
Torej, kaj je vhod vrednost, ki jo želimo
za testiranje tod ki je 0,41.

337
00:15:08,580 --> 00:15:09,160
Great.

338
00:15:09,160 --> 00:15:12,780
>> Torej, zdaj N- storiti vidva glej
tu, na bottom-- je

339
00:15:12,780 --> 00:15:15,140
stored-- ker smo
še niso zaokrožene, da je

340
00:15:15,140 --> 00:15:19,540
shranjene v tem, kot velikan
plovec, ki je ,4099999996,

341
00:15:19,540 --> 00:15:22,550
ki je dovolj blizu, da se naše
namene, prav zdaj, na 0,41.

342
00:15:22,550 --> 00:15:26,090
In potem bomo videli kasneje, kot smo
še naprej krepi nad programom,

343
00:15:26,090 --> 00:15:29,850
potem tukaj je n postala
zaokrožen in centov je postala 41.

344
00:15:29,850 --> 00:15:30,350
Great.

345
00:15:30,350 --> 00:15:32,230
Tako smo vedeli, da je delo naše zaokroževanja je.

346
00:15:32,230 --> 00:15:34,700
Vemo, da imamo
pravilno število centov,

347
00:15:34,700 --> 00:15:36,990
tako vemo, da je to
ni res problem.

348
00:15:36,990 --> 00:15:40,050
>> Torej bomo še naprej krepi
na v tem programu.

349
00:15:40,050 --> 00:15:40,900
Gremo tukaj.

350
00:15:40,900 --> 00:15:46,139
In tako po tem vrstico kode, smo
bi morali vedeti, koliko četrtine imamo.

351
00:15:46,139 --> 00:15:46,680
Stopimo čez.

352
00:15:46,680 --> 00:15:52,040
In vidiš, da ne, v resnici, ima eno
Četrtina ker smo odšteli 25

353
00:15:52,040 --> 00:15:53,790
od naše začetne vrednosti 41.

354
00:15:53,790 --> 00:15:55,890
In imamo 16 levo za naše centov.

355
00:15:55,890 --> 00:15:58,830
>> Ali vsi razumejo, kako
Program stopa skozi

356
00:15:58,830 --> 00:16:02,980
in zakaj je centov postala 16
in zakaj, zdaj, kovanci postala 1?

357
00:16:02,980 --> 00:16:04,610
Vsakdo je po tej logiki?

358
00:16:04,610 --> 00:16:05,110
Cool.

359
00:16:05,110 --> 00:16:07,860
Tako te točke je
delovnega programa, kajne?

360
00:16:07,860 --> 00:16:09,797
Vemo, da počne točno
kar smo jo želeli.

361
00:16:09,797 --> 00:16:11,880
In nismo dejansko
morali natisniti, oh, kaj

362
00:16:11,880 --> 00:16:14,430
je centov na tej točki,
kaj je kovance na tej točki.

363
00:16:14,430 --> 00:16:17,170
>> Nadaljujemo skozi program.

364
00:16:17,170 --> 00:16:18,100
Korak čez.

365
00:16:18,100 --> 00:16:18,620
Cool.

366
00:16:18,620 --> 00:16:19,700
Mi gremo čez dimes.

367
00:16:19,700 --> 00:16:20,200
Great.

368
00:16:20,200 --> 00:16:22,367
Vidimo, da je to delo
off 0,10 $ za kovanec.

369
00:16:22,367 --> 00:16:23,450
In zdaj imamo dva kovanca.

370
00:16:23,450 --> 00:16:25,260
To je res.

371
00:16:25,260 --> 00:16:31,555
>> Gremo čez penijev in vidimo
da smo krepko čez centov.

372
00:16:31,555 --> 00:16:32,680
Hmm, to je čudno.

373
00:16:32,680 --> 00:16:37,540
Tu gor na program, pa naj
da so odšteti moje penijev.

374
00:16:37,540 --> 00:16:39,400
Morda nisem bil
počne to postavo pravico.

375
00:16:39,400 --> 00:16:42,190
In žal, lahko vidite
tukaj, ker vemo,

376
00:16:42,190 --> 00:16:44,360
da stopamo
preko linij 32 in 33,

377
00:16:44,360 --> 00:16:50,560
da je, kjer naš program
nepravilno imeli spremenljivke teči.

378
00:16:50,560 --> 00:16:55,136
Tako smo lahko ogledate in videli, oh,
Jaz odšteje centov tukaj,

379
00:16:55,136 --> 00:16:57,010
ampak nisem dejansko
dodal na moj kovanec vrednosti.

380
00:16:57,010 --> 00:16:57,860
Jaz sem dodal, da centov.

381
00:16:57,860 --> 00:17:00,234
In ne želim, da se doda
centov, želim dodati kovancev.

382
00:17:00,234 --> 00:17:05,420
Torej, če bomo spremenili, da kovanci,
imamo delovni program.

383
00:17:05,420 --> 00:17:06,730
Ne morem teči check50.

384
00:17:06,730 --> 00:17:11,063
Lahko samo izhod iz GDB pravice
tukaj in nato ponovno zaženite check50.

385
00:17:11,063 --> 00:17:11,938
Jaz bi to samo naredi.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Moram narediti pohlepni.

388
00:17:18,480 --> 00:17:19,940
0.41.

389
00:17:19,940 --> 00:17:22,819
In tukaj, to je tiskanje
ven pravilen odgovor.

390
00:17:22,819 --> 00:17:26,569
>> Tako da lahko vi vidite, GDB
je res močno orodje

391
00:17:26,569 --> 00:17:29,940
za takrat, ko imamo toliko koda
dogaja in toliko spremenljivk

392
00:17:29,940 --> 00:17:32,510
da je težko za nas, kot
človek, za sledenje.

393
00:17:32,510 --> 00:17:35,360
Računalnik, v GDB
razhroščevalnik, ima sposobnost

394
00:17:35,360 --> 00:17:37,020
slediti vsem.

395
00:17:37,020 --> 00:17:40,480
Vem, v Visionaire, vidva
Morda so prizadele nekatere segmentacije napak

396
00:17:40,480 --> 00:17:43,150
ker ste bili teče
izven meja vašega array.

397
00:17:43,150 --> 00:17:46,510
V primeru Cezarja, ki je
točno to, kar sem tu izvajajo.

398
00:17:46,510 --> 00:17:50,060
>> Torej, sem pozabil, da preverite
kaj bi se zgodilo, če bi

399
00:17:50,060 --> 00:17:52,510
niso imeli dva argumenta ukazne vrstice.

400
00:17:52,510 --> 00:17:53,880
Samo nisem dal v ta pregled.

401
00:17:53,880 --> 00:17:57,380
In zato, če sem teči Debug-- nastavim
moj Ustavljanje tam desno.

402
00:17:57,380 --> 00:17:58,055
Vodim razhroščevanje.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> V REDU.

405
00:18:16,550 --> 00:18:17,050
Ja.

406
00:18:17,050 --> 00:18:20,350
Torej v resnici, je GDB naj
da so mi povedali, da

407
00:18:20,350 --> 00:18:22,300
bilo segmentacija napaka tam.

408
00:18:22,300 --> 00:18:24,883
Ne vem, kaj se je dogajalo
prav tam, ampak ko sem tekel,

409
00:18:24,883 --> 00:18:25,590
to je delal.

410
00:18:25,590 --> 00:18:29,410
Ko zaženete vrstic kode skozi in
GDB lahko samo nenadoma nehal na vas,

411
00:18:29,410 --> 00:18:31,540
pojdi gor in poglej, kaj je rdeča napaka.

412
00:18:31,540 --> 00:18:33,930
To vam povem, hej, ti
imel napako segmentacije,

413
00:18:33,930 --> 00:18:38,550
kar pomeni, da si se potrudil za dostop
Prostor v matriki, ki ne obstaja.

414
00:18:38,550 --> 00:18:39,050
Ja.

415
00:18:39,050 --> 00:18:43,280
>> Torej v naslednji problem
iz ta teden, vidva

416
00:18:43,280 --> 00:18:45,600
Verjetno bo veliko
spremenljivke plava okoli.

417
00:18:45,600 --> 00:18:48,560
Ne boš, da se prepričate, kaj
so vse to pomeni v določenem trenutku.

418
00:18:48,560 --> 00:18:53,560
Torej bo GDB res vam pomaga pri kipec
izvedeti, kaj so vsi ki je enaka

419
00:18:53,560 --> 00:18:55,940
in da bi lahko videli, da je vizualno.

420
00:18:55,940 --> 00:19:01,995
Je kdo zmeden o tem, kako
nič od tega delala?

421
00:19:01,995 --> 00:19:02,495
Cool.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
V redu.

424
00:19:10,620 --> 00:19:14,260
Torej, po tem smo
dogaja, da se potopite desno

425
00:19:14,260 --> 00:19:17,562
v štiri različne
Vrste vrst za ta teden.

426
00:19:17,562 --> 00:19:19,520
Koliko od vas, najprej
od vsega, preden začnemo,

427
00:19:19,520 --> 00:19:23,020
Prebral celotno spec za pset3?

428
00:19:23,020 --> 00:19:23,824
V REDU.

429
00:19:23,824 --> 00:19:24,740
Ponosen sem na vas.

430
00:19:24,740 --> 00:19:29,110
To je kot polovici razreda, ki
je bistveno več kot v preteklem času.

431
00:19:29,110 --> 00:19:33,950
>> Torej, to je super, ker ko
govorimo o vsebini

432
00:19:33,950 --> 00:19:36,170
v lecture-- ali žal,
v section-- rad

433
00:19:36,170 --> 00:19:38,210
povezati veliko, da
nazaj na kaj je pset je

434
00:19:38,210 --> 00:19:40,210
in kako želite
izvajati, da se v vašem pset.

435
00:19:40,210 --> 00:19:42,400
Torej, če ste prišli ob
preberite spec, bo

436
00:19:42,400 --> 00:19:45,510
bo veliko lažje za vas, da razumete
kaj sem govoril, ko sem rekel,

437
00:19:45,510 --> 00:19:48,720
oh hej, to je lahko res
dober kraj za izvajanje te vrste.

438
00:19:48,720 --> 00:19:52,870
Torej tisti, ki ste prebrali
spec vedeli, da kot del vašega pset,

439
00:19:52,870 --> 00:19:54,900
boste morali
napisati tip vrste.

440
00:19:54,900 --> 00:19:58,670
Torej, to je lahko zelo koristno
za veliko vas danes.

441
00:19:58,670 --> 00:20:01,760
>> Torej bomo začnete s,
v bistvu je najbolj preprost tip

442
00:20:01,760 --> 00:20:04,580
za razvrščanje, izbira vrste.

443
00:20:04,580 --> 00:20:06,800
Tipična algoritem za
kako bi se gremo o tem

444
00:20:06,800 --> 00:20:10,460
is-- David je šel skozi to all
predavanje, tako da bom hitro premikati vzdolž

445
00:20:10,460 --> 00:20:13,900
here-- je v bistvu, si
imajo spekter vrednosti.

446
00:20:13,900 --> 00:20:17,170
In potem se vam zdi
Najmanjši razvrščeni vrednost

447
00:20:17,170 --> 00:20:20,200
in ti swap to vrednost z
prvi neprebrani vrednost.

448
00:20:20,200 --> 00:20:22,700
In potem si ponavljajo
s preostalim vašega seznama.

449
00:20:22,700 --> 00:20:25,740
>> In tukaj je vizualna razlaga
o tem, kako bi to delovalo.

450
00:20:25,740 --> 00:20:30,460
Torej, za primer, če smo bili začeti
s paleto petih elementov, indeks

451
00:20:30,460 --> 00:20:35,910
0 do 4, s 3, 5, 2, 6 in 4 vrednosti
postavi v array-- prav zdaj,

452
00:20:35,910 --> 00:20:38,530
smo šele tekoč, da prevzame
da so si vsi razvrščeni

453
00:20:38,530 --> 00:20:41,130
ker nismo testirali drugače.

454
00:20:41,130 --> 00:20:44,130
>> Torej, kako bi izbor vrste
delo je, da bi najprej

455
00:20:44,130 --> 00:20:46,800
teči skozi celoti
nerazvrščenih array.

456
00:20:46,800 --> 00:20:49,120
To bi izbrati najmanjšo vrednost.

457
00:20:49,120 --> 00:20:51,750
V tem primeru, 3, desno
Zdaj, je najmanjša.

458
00:20:51,750 --> 00:20:52,680
Pride do 5.

459
00:20:52,680 --> 00:20:55,620
Nope, 5 ni večja than--
ali žal, ni manj than-- 3.

460
00:20:55,620 --> 00:20:57,779
Torej je minimalna vrednost še 3.

461
00:20:57,779 --> 00:20:58,695
In potem prideš do 2.

462
00:20:58,695 --> 00:21:00,990
Računalnik vidi, OH, 2 manjša od 3.

463
00:21:00,990 --> 00:21:02,750
2 mora zdaj biti minimalna vrednost.

464
00:21:02,750 --> 00:21:06,630
In tako 2 zamenjave s tem prvo vrednost.

465
00:21:06,630 --> 00:21:10,702
>> Torej, po eni priložnost, bomo zares videli
da sta 2 in 3 zamenjala.

466
00:21:10,702 --> 00:21:13,910
In smo le, da bo še naprej delal
to spet s preostalim matrike.

467
00:21:13,910 --> 00:21:17,660
Torej bomo šele teči skozi
zadnje štiri indeksi array.

468
00:21:17,660 --> 00:21:20,670
Bomo videli, da je 3
Naslednji minimalna vrednost.

469
00:21:20,670 --> 00:21:23,240
Torej bomo zamenjali, da s 4.

470
00:21:23,240 --> 00:21:26,900
In potem smo šele tekoč, da bo
teče skozi, dokler na koncu, boste

471
00:21:26,900 --> 00:21:33,730
priti do urejenih niz, v katerem
2, 3, 4, 5 in 6 so vse razporejene.

472
00:21:33,730 --> 00:21:37,530
Ali vsi razumejo logiko
kako izbira nekako deluje?

473
00:21:37,530 --> 00:21:39,669
>> Imate le nekakšen
minimalne vrednosti.

474
00:21:39,669 --> 00:21:41,210
Ste sledenja, kaj to je.

475
00:21:41,210 --> 00:21:45,170
In ko ga najdejo, ga zamenjajte
s prvo vrednost v array--

476
00:21:45,170 --> 00:21:48,740
ali ni prvi value--
naslednjo vrednost v matriki.

477
00:21:48,740 --> 00:21:50,150
Cool.

478
00:21:50,150 --> 00:21:55,460
>> Tako kot vaju vrste
Videl je kratek pogled,

479
00:21:55,460 --> 00:21:58,450
bomo to psevdokoda ven.

480
00:21:58,450 --> 00:22:02,510
Torej, če vi v zadnji želite
tvorijo skupino, vse na mizo

481
00:22:02,510 --> 00:22:06,170
lahko tvorijo malo partnerja, jaz grem
da vam fantje kot treh minutah

482
00:22:06,170 --> 00:22:08,190
da samo govoriti skozi
logika, v angleškem jeziku,

483
00:22:08,190 --> 00:22:14,161
o tem, kako bi morali biti sposobni izvajati
psevdokoda napisati izbiro vrste.

484
00:22:14,161 --> 00:22:14,910
In tam je sladkarije.

485
00:22:14,910 --> 00:22:16,118
Prosim, pridi gor in dobili sladkarije.

486
00:22:16,118 --> 00:22:19,520
Če ste v hrbtu in želite
sladkarije, sem lahko vrgel sladkarije na vas.

487
00:22:19,520 --> 00:22:22,850
Pravzaprav, ne you-- ohladi.

488
00:22:22,850 --> 00:22:23,552
Oh, oprosti.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
V REDU.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Torej, če bi želeli, kot
razred, pisanje psevdokoda

493
00:25:27,140 --> 00:25:30,466
za to, kako bi se dalo pristopiti
ta problem, samo potipati prost.

494
00:25:30,466 --> 00:25:32,340
Jaz bom samo pojdi okoli in,
v redu, vprašajte skupine

495
00:25:32,340 --> 00:25:35,065
za naslednjo linijo
kaj bi morali delati.

496
00:25:35,065 --> 00:25:37,840
Torej, če hočete, da začnete
off, kaj je prva stvar,

497
00:25:37,840 --> 00:25:40,600
storiti, ko ste poskušali
izvajati način za rešitev tega programa

498
00:25:40,600 --> 00:25:43,480
za selektivno razvrstiti seznam?

499
00:25:43,480 --> 00:25:46,349
Naj samo prevzeti smo
imajo niz, v redu?

500
00:25:46,349 --> 00:25:49,088
>> OBČINSTVO: boste želeli ustvariti nekaj
nekako [neslišno], da ste

501
00:25:49,088 --> 00:25:50,420
teče skozi celotno paleto.

502
00:25:50,420 --> 00:25:51,128
>> ANDI PENG: Right.

503
00:25:51,128 --> 00:25:54,100
Torej boste želeli ponoviti
skozi vsak prostor, kajne?

504
00:25:54,100 --> 00:26:05,490
Torej, super.

505
00:26:05,490 --> 00:26:08,600
Če hočete, da mi
Naslednji line-- ja, v hrbtu.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> OBČINSTVO: Preverite jih
vse za najmanjšo.

508
00:26:13,290 --> 00:26:14,248
>> ANDI PENG: Tukaj gremo.

509
00:26:14,248 --> 00:26:17,438
Zato želimo, da gredo skozi in preverite,
videli, kaj je minimalna vrednost, kajne?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Grem Skrajšati da "min".

512
00:26:24,840 --> 00:26:27,658
Kaj si fantje želijo storiti po
ste našli minimalno vrednost?

513
00:26:27,658 --> 00:26:28,533
>> OBČINSTVO: [neslišno]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Torej boste želeli
prižgati s prvim tega niza,

516
00:26:33,150 --> 00:26:33,650
prav?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
To je začetek, bom povedal.

519
00:26:46,850 --> 00:26:47,220
V redu.

520
00:26:47,220 --> 00:26:50,386
Torej sedaj, da ste zamenjali prvi
ena, kaj želite storiti po tem?

521
00:26:50,386 --> 00:26:54,840
Zdaj vemo, da je to ena tukaj
mora biti najmanjši vrednost, ne?

522
00:26:54,840 --> 00:26:58,310
Potem imate dodaten počitek
matrike, ki je razvrščen.

523
00:26:58,310 --> 00:27:01,569
Torej, kaj želite storiti tukaj, če vas
fantje želijo, da mi naslednjo vrstico?

524
00:27:01,569 --> 00:27:04,610
OBČINSTVO: Torej hočeš Ponovil
skozi preostanek niza.

525
00:27:04,610 --> 00:27:05,276
ANDI PENG: Ja.

526
00:27:05,276 --> 00:27:09,857
In tako kaj ponavljanjem skozi
nekako pomeni, da bomo verjetno potrebovali?

527
00:27:09,857 --> 00:27:10,440
Kakšen tip of--

528
00:27:10,440 --> 00:27:12,057
>> OBČINSTVO: Oh, dodatna spremenljivka?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Verjetno
drugo za zanke, kajne?

530
00:27:13,890 --> 00:27:28,914
Tako smo si verjetno želeli
Ponovil through-- super.

531
00:27:28,914 --> 00:27:31,830
In potem boš šel nazaj in
verjetno ponovno preverite minimum,

532
00:27:31,830 --> 00:27:32,100
prav?

533
00:27:32,100 --> 00:27:34,975
In ti boš ponavljajo
, ker zank šele tekoč

534
00:27:34,975 --> 00:27:36,010
da teče, kajne?

535
00:27:36,010 --> 00:27:39,190
>> Tako da lahko vi vidite, smo
samo še splošno psevdokoda

536
00:27:39,190 --> 00:27:41,480
kako hočemo ta program gledati.

537
00:27:41,480 --> 00:27:46,646
Ta Ponovil sem, kaj počnemo
običajno morali napisati v našo kodo

538
00:27:46,646 --> 00:27:49,270
če želimo Ponovil posredno preko
matrika, katera vrsta strukture?

539
00:27:49,270 --> 00:27:51,030
Mislim Christabel
že to rekel prej.

540
00:27:51,030 --> 00:27:51,500
>> OBČINSTVO: A za zanko.

541
00:27:51,500 --> 00:27:52,160
>> ANDI PENG: A za zanko?

542
00:27:52,160 --> 00:27:52,770
Točno tako.

543
00:27:52,770 --> 00:27:56,060
Torej, to je verjetno
bo za zanke.

544
00:27:56,060 --> 00:27:59,240
Kaj je preverjanje tukaj dogaja, da pomeni?

545
00:27:59,240 --> 00:28:02,536
Značilno je, da če hočeš, da preverite
če je nekaj nekaj else--

546
00:28:02,536 --> 00:28:03,270
>> OBČINSTVO: Če.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: An če je, kajne?

548
00:28:06,790 --> 00:28:10,790
In potem swap tukaj, bomo
iti čez kasneje, zaradi Davida,

549
00:28:10,790 --> 00:28:12,770
šel skozi, da je v predavanju, kot dobro.

550
00:28:12,770 --> 00:28:14,580
In potem drugi Ponovil implies--

551
00:28:14,580 --> 00:28:15,120
>> OBČINSTVO: Drug za zanko.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another za zanke, točno.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Torej, če gledamo
na to pravilno, smo

555
00:28:22,000 --> 00:28:24,680
lahko vidimo, da smo verjetno
bomo potrebovali ugnezdene zanke

556
00:28:24,680 --> 00:28:28,330
s pogojnim izjavo v tam
in potem dejansko del kode, ki je

557
00:28:28,330 --> 00:28:31,360
dogaja, da bi zamenjali vrednosti.

558
00:28:31,360 --> 00:28:35,980
Tako sem samo na splošno napisal
psevdokoda kodo tukaj.

559
00:28:35,980 --> 00:28:38,910
In potem smo dejansko dogaja
fizično, kot razred

560
00:28:38,910 --> 00:28:40,700
poskusite izvajati to danes.

561
00:28:40,700 --> 00:28:42,486
Vrnimo se v to IDE.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Uh-oh.

564
00:28:50,230 --> 00:28:51,754
Zakaj je, da je not-- tam.

565
00:28:51,754 --> 00:28:52,253
V REDU.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Žal mi je, da mi poskusite za povečavo malo več.

568
00:28:57,500 --> 00:28:59,310
Tam gremo.

569
00:28:59,310 --> 00:29:05,060
Vse delam tu sem jih ustvaril
program, imenovan "Izbira / sort.c."

570
00:29:05,060 --> 00:29:10,860
Sem ustvaril niz devetih
Vrednosti, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Trenutno, kot si lahko
glej so neurejenega.

572
00:29:14,370 --> 00:29:17,880
n se bo število,
vam pove količino vrednot

573
00:29:17,880 --> 00:29:18,920
imate v array.

574
00:29:18,920 --> 00:29:20,670
V tem primeru imamo devet vrednosti.

575
00:29:20,670 --> 00:29:23,760
In sem pravkar dobil za zanke tukaj
da natisne neurejen array.

576
00:29:23,760 --> 00:29:28,370
>> In na koncu, imam tudi za
zanko, ki jo je pravkar natisne znova.

577
00:29:28,370 --> 00:29:32,070
Torej teoretično, če ta program
deluje pravilno, na koncu,

578
00:29:32,070 --> 00:29:35,670
bi morali videti natisnjen za zanko
v kateri je 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 so vse pravilno v redu.

580
00:29:39,310 --> 00:29:43,410
>> Torej imamo našo psevdokoda tukaj.

581
00:29:43,410 --> 00:29:46,090
Ali kdo želel to-- sem samo
bo šel vprašati za volunteers--

582
00:29:46,090 --> 00:29:49,540
povej mi točno, kaj naj tip, če
želimo, prvič, samo ponovitev

583
00:29:49,540 --> 00:29:52,840
po začetku tega niza?

584
00:29:52,840 --> 00:29:55,204
Kaj je vrstica kode sem
Verjetno bo treba tukaj?

585
00:29:55,204 --> 00:29:56,990
>> OBČINSTVO: [neslišno]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Ja, počutim
brezplačno to-- žal, vas

587
00:29:59,010 --> 00:30:02,318
ne bi bilo treba stati up-- občutek
brezplačno dvigniti svoj glas bit.

588
00:30:02,318 --> 00:30:08,190
>> OBČINSTVO: Za int i enaka 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI PENG: Ja, dobro.

590
00:30:10,690 --> 00:30:15,220
>> OBČINSTVO: i je manjša od dolžine diod.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Torej, ne
moti tukaj, ker smo

592
00:30:19,630 --> 00:30:23,060
nimajo funkcijo,
nam pove dolžina array,

593
00:30:23,060 --> 00:30:25,790
smo že imeli
vrednost, ki shranjuje da.

594
00:30:25,790 --> 00:30:27,920
Prav?

595
00:30:27,920 --> 00:30:31,010
Druga stvar, ki vodijo
v mind-- v array

596
00:30:31,010 --> 00:30:33,940
devetih vrednot, kaj so indeksi?

597
00:30:33,940 --> 00:30:38,720
Recimo samo, da je to zaporedje je od 0 do 3.

598
00:30:38,720 --> 00:30:41,500
Vidiš, da je zadnji
Indeks je pravzaprav 3.

599
00:30:41,500 --> 00:30:45,530
To ni 4, čeprav je
štiri vrednosti v matriki.

600
00:30:45,530 --> 00:30:49,866
>> Torej tukaj, moramo biti zelo previdni
o kakšnem našem pogoj za dolžino

601
00:30:49,866 --> 00:30:50,490
se bo.

602
00:30:50,490 --> 00:30:51,948
>> OBČINSTVO: Ali ne bi bilo n minus 1?

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: To se dogaja
n minus 1, točno.

604
00:30:54,440 --> 00:30:57,379
Ali to smisel, zakaj
je n minus 1, so vsi?

605
00:30:57,379 --> 00:30:58,920
To je zato, ker so nizi nič indeksirajo.

606
00:30:58,920 --> 00:31:02,010
Začnejo na 0 in vodijo do n minus 1.

607
00:31:02,010 --> 00:31:03,210
Ja, to je malce zapleteno.

608
00:31:03,210 --> 00:31:03,730
V REDU.

609
00:31:03,730 --> 00:31:05,929
In potem--

610
00:31:05,929 --> 00:31:08,054
OBČINSTVO: Isnt'1 da
že poskrbljeno, čeprav,

611
00:31:08,054 --> 00:31:11,400
ki ga preprosto ni rekel "manj ali
enako "in samo rekel" manj kot? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: To je
Res dobro vprašanje.

613
00:31:13,108 --> 00:31:13,630
Torej, ja.

614
00:31:13,630 --> 00:31:17,410
Ampak tudi način, da smo
uresničevanje pravice preverjanje,

615
00:31:17,410 --> 00:31:19,120
boste morali primerjati dve vrednosti.

616
00:31:19,120 --> 00:31:21,009
Torej si dejansko želijo
pusti ", da" prazna.

617
00:31:21,009 --> 00:31:23,050
Ker če primerjate
ta, ne boš šel

618
00:31:23,050 --> 00:31:25,530
imajo kaj po njej
za primerjavo, da, kajne?

619
00:31:25,530 --> 00:31:27,460
Ja.

620
00:31:27,460 --> 00:31:29,297
Torej i ++.

621
00:31:29,297 --> 00:31:30,380
Dodajmo našim oklepajev v.

622
00:31:30,380 --> 00:31:30,880
Ops.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Great.

625
00:31:34,710 --> 00:31:39,117
Torej imamo začetek
naše zunanje zanke.

626
00:31:39,117 --> 00:31:41,450
Torej, zdaj smo verjetno želeli
ustvariti spremenljivko za vodenje

627
00:31:41,450 --> 00:31:43,085
koloteka najmanjše vrednosti, kajne?

628
00:31:43,085 --> 00:31:45,751
Ali kdo želel, da mi
vrstica kode, ki bi to naredil?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Kaj potrebujemo, če gremo
da želite shraniti kaj?

631
00:31:53,570 --> 00:31:55,047
>> Prav.

632
00:31:55,047 --> 00:31:57,630
Mogoče boljše ime za to
bi be-- "temp" popolnoma works--

633
00:31:57,630 --> 00:32:00,655
morda bolj primerno ime bi bilo,
če želimo najmanjšo value--

634
00:32:00,655 --> 00:32:01,624
>> OBČINSTVO: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: min, pa gremo.

636
00:32:02,790 --> 00:32:05,230
min bi bilo dobro.

637
00:32:05,230 --> 00:32:08,340
In tako sem, kaj počnemo
želite inicializirati za?

638
00:32:08,340 --> 00:32:09,620
To je malce zapleteno.

639
00:32:09,620 --> 00:32:13,580
Ker je prav zdaj v
začnejo te matrike,

640
00:32:13,580 --> 00:32:15,730
niste pogledal na nič, kajne?

641
00:32:15,730 --> 00:32:19,200
Torej, kaj, samodejno, če
smo samo na i enak 0,

642
00:32:19,200 --> 00:32:22,302
kaj želimo inicializacijo
naša prva minimalno vrednost?

643
00:32:22,302 --> 00:32:22,802
OBČINSTVO: i.

644
00:32:22,802 --> 00:32:24,790
ANDI PENG: i, točno.

645
00:32:24,790 --> 00:32:27,040
Christabel, zakaj hočemo
za inicializacijo na i?

646
00:32:27,040 --> 00:32:28,510
>> OBČINSTVO: Ker, dobro,
smo se začne z 0.

647
00:32:28,510 --> 00:32:31,660
Zato, ker nimamo ničesar za primerjavo
to naj bo minimalna koncu pa 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI PENG: Točno tako.

649
00:32:32,451 --> 00:32:34,400
Torej je ravno prav.

650
00:32:34,400 --> 00:32:36,780
Saj imamo dejansko ni
pogledal kaj še,

651
00:32:36,780 --> 00:32:38,680
ne vemo, kaj je naša najmanjša vrednost.

652
00:32:38,680 --> 00:32:41,960
Želimo, da šele inicializirati na
i, ki je trenutno, je tukaj.

653
00:32:41,960 --> 00:32:44,750
In kot smo še naprej
pomaknil navzdol ta niz,

654
00:32:44,750 --> 00:32:48,122
bomo videli, da je z vsako
Dodatna napadalca, i korakih.

655
00:32:48,122 --> 00:32:49,830
In tako je na tej točki,
i je verjetno,

656
00:32:49,830 --> 00:32:52,329
želeli, da bi bila minimalna,
ker se dogaja, da se karkoli

657
00:32:52,329 --> 00:32:54,520
je začetek nerazvrščene array.

658
00:32:54,520 --> 00:32:55,270
Cool.

659
00:32:55,270 --> 00:32:58,720
>> Torej, zdaj smo želeli dodati
za zanke tukaj, ki je

660
00:32:58,720 --> 00:33:03,225
bo Ponovil skozi
nesortirani ali preostanek tega niza.

661
00:33:03,225 --> 00:33:05,808
Ali kdo želel, da mi
vrstica kode, ki bi to naredil?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- kaj moramo tu dol?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Kaj se dogaja, da gredo v to zanko?

666
00:33:18,820 --> 00:33:19,465
Ja.

667
00:33:19,465 --> 00:33:21,590
OBČINSTVO: Torej bi hočemo
imajo drugačno celo število,

668
00:33:21,590 --> 00:33:25,080
ker smo teče skozi preostali
array namesto i, zato morda

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Ja, j zveni dobro zame.

671
00:33:27,301 --> 00:33:27,850
Enaka?

672
00:33:27,850 --> 00:33:33,930
>> SKUPINA: Torej bi bilo i plus 1, saj
ste začeli na naslednji vrednosti.

673
00:33:33,930 --> 00:33:40,395
In potem na end-- tako spet, j
manj kot n minus 1 in nato j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI PENG: Great.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> In potem je tukaj, smo želeli
da preverite, če je naš pogoj izpolnjen,

677
00:33:52,750 --> 00:33:53,250
prav?

678
00:33:53,250 --> 00:33:55,740
Ker želite
spremeniti minimalno vrednost

679
00:33:55,740 --> 00:33:58,700
če je dejansko manjši od tistega,
ste ga primerjamo z, kajne?

680
00:33:58,700 --> 00:34:01,146
Torej, kaj bomo želeli tukaj?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Preverite.

683
00:34:04,897 --> 00:34:06,730
Kakšne vrste izjave
smo verjetno bo

684
00:34:06,730 --> 00:34:08,389
ti želeli uporabiti, če bomo
želeli preveriti kaj?

685
00:34:08,389 --> 00:34:09,360
>> OBČINSTVO: An če izjavi.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: An če izjavo.

687
00:34:10,485 --> 00:34:13,155
Torej if-- in kaj se dogaja, da
pogoj, da želimo v notranjosti

688
00:34:13,155 --> 00:34:13,988
naše če izjave?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> OBČINSTVO: Če je vrednost j
manjša od vrednosti i--

691
00:34:22,960 --> 00:34:24,600
>> ANDI PENG: Točno tako.

692
00:34:24,600 --> 00:34:27,480
Torej if-- zato je ta matrika se imenuje "Niz".

693
00:34:27,480 --> 00:34:27,980
Great.

694
00:34:27,980 --> 00:34:30,465
Torej, če array-- kaj je bilo to?

695
00:34:30,465 --> 00:34:31,090
Povej še enkrat.

696
00:34:31,090 --> 00:34:39,590
>> OBČINSTVO: Če je niz-j manj kot
matrika-i, potem bi spremenila min.

697
00:34:39,590 --> 00:34:41,590
Torej bi bilo min j.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Ali je to smiselno?

700
00:34:47,249 --> 00:34:48,670
V REDU.

701
00:34:48,670 --> 00:34:52,929
In zdaj tukaj, smo dejansko
želijo izvajati swap, kajne?

702
00:34:52,929 --> 00:34:58,285
Torej se spomni, v predavanju, da David, ko
je skušal the-- kaj je swap

703
00:34:58,285 --> 00:34:59,996
it-- pomarančni sok in milk--

704
00:34:59,996 --> 00:35:01,150
>> OBČINSTVO: To je bil bruto.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Ja, to je bilo nekako bruto.

706
00:35:02,816 --> 00:35:05,310
Ampak to je zelo dobro
Koncept čas dokazuje.

707
00:35:05,310 --> 00:35:08,430
Torej, mislim, vaše vrednote tukaj.

708
00:35:08,430 --> 00:35:10,794
Imaš niz
od min, array i,

709
00:35:10,794 --> 00:35:12,460
ali karkoli smo poskušali tukaj zamenjali.

710
00:35:12,460 --> 00:35:15,310
In verjetno jih ne morete vlijemo
seboj istočasno, prav?

711
00:35:15,310 --> 00:35:17,180
Torej, kaj bomo
bi morali ustvariti tukaj

712
00:35:17,180 --> 00:35:19,126
Za pravilno swap vrednote?

713
00:35:19,126 --> 00:35:19,820
>> OBČINSTVO: začasna spremenljivka.

714
00:35:19,820 --> 00:35:21,370
>> ANDI PENG: začasna spremenljivka.

715
00:35:21,370 --> 00:35:22,570
Torej, kaj je naredil int temp.

716
00:35:22,570 --> 00:35:25,681
Glej, kar bi bilo boljše
Čas to-- vau, kaj je bilo to?

717
00:35:25,681 --> 00:35:26,180
V REDU.

718
00:35:26,180 --> 00:35:29,800
Torej bi bilo to bolje
Čas je, da ime spremenljivke "temp."

719
00:35:29,800 --> 00:35:30,730
Torej, kaj je naredil int temp.

720
00:35:30,730 --> 00:35:32,563
Kaj bomo
nastavljena temp enako tukaj?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
OBČINSTVO: Min?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI PENG: To je malce zapleteno.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
To pravzaprav ni pomembno, na koncu.

727
00:35:44,880 --> 00:35:47,690
Ni važno, kaj
Da bi se odločite za zamenjavo v

728
00:35:47,690 --> 00:35:50,862
tako dolgo, kot ste kar prepričani, da ste
sledenja, kaj ste zamenjavo.

729
00:35:50,862 --> 00:35:52,250
>> OBČINSTVO: Lahko bi bilo niz-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Ja, dajmo narediti matrično-i.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
In kaj potem je naslednja vrstica
kode želimo imeti tukaj?

733
00:35:59,305 --> 00:36:00,680
OBČINSTVO: matrika-i enaka matrično-j.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: In nazadnje?

736
00:36:08,070 --> 00:36:12,070
OBČINSTVO: niz-j enak niz-i.

737
00:36:12,070 --> 00:36:14,525
OBČINSTVO: Ali niz-j Ene
Niz-temp-- ali temp.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI PENG: OK.

740
00:36:19,430 --> 00:36:21,510
Torej, kaj je teči to in videli
če bo delovalo.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Kjer je to dogaja?

743
00:36:39,335 --> 00:36:40,210
Oh, to je problem.

744
00:36:40,210 --> 00:36:44,320
Glej, na liniji 40, smo
poskuša uporabiti matrično-j?

745
00:36:44,320 --> 00:36:47,022
Ampak kje pa j obstaja samo?

746
00:36:47,022 --> 00:36:48,402
>> OBČINSTVO: V zanko.

747
00:36:48,402 --> 00:36:49,110
ANDI PENG: Right.

748
00:36:49,110 --> 00:36:51,730
Torej, kaj bomo morali storiti?

749
00:36:51,730 --> 00:36:53,170
>> OBČINSTVO: ga Določite zunaj the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
OBČINSTVO: Ja, mislim, da imate
uporabiti drugo, če izjavo, kajne?

752
00:37:00,610 --> 00:37:05,230
Tako kot, če minimum--
Vse je v redu, naj premislim.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Fantje, poskusite
da se zazremo Oglejmo

755
00:37:09,990 --> 00:37:11,270
glej, kaj se kaj lahko storimo tu?

756
00:37:11,270 --> 00:37:11,811
>> OBČINSTVO: OK.

757
00:37:11,811 --> 00:37:15,900
Torej, če je najmanjša ni enak
j-- tako da, če je minimalna še i--

758
00:37:15,900 --> 00:37:17,570
potem mi ne bi bilo treba zamenjati.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Ali je to enako i?

761
00:37:24,712 --> 00:37:25,920
Kaj hočeš reči tu?

762
00:37:25,920 --> 00:37:30,494
>> OBČINSTVO: Ali ja, če
Minimalna ne enako i, ja.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI PENG: OK.

765
00:37:40,210 --> 00:37:42,040
No, da reši, vrsta, naše težave.

766
00:37:42,040 --> 00:37:47,265
Ampak to še vedno ne reši
Problem, kaj se zgodi, če j-- saj j

767
00:37:47,265 --> 00:37:49,890
ne obstaja zunaj njega, kar
vam želimo storiti z njim?

768
00:37:49,890 --> 00:37:50,698
Jo razglasi zunaj?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Poskusimo teče to.

771
00:38:02,730 --> 00:38:04,435
Uh-oh.

772
00:38:04,435 --> 00:38:06,200
Naša nekako ne deluje.

773
00:38:06,200 --> 00:38:10,060
>> Kot lahko vidite, naš začetnico
Niz je imel te vrednote.

774
00:38:10,060 --> 00:38:14,800
In potem bi morala imeti
je v 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Ne deluje.

776
00:38:15,530 --> 00:38:16,030
Ahh.

777
00:38:16,030 --> 00:38:17,184
Kaj počnemo?

778
00:38:17,184 --> 00:38:17,850
OBČINSTVO: Debug.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: V redu, lahko poskusite to.

781
00:38:23,370 --> 00:38:25,030
Mi lahko debug.

782
00:38:25,030 --> 00:38:26,042
Pomanjšanje bit.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Oglejmo nastavite našo prelomne točke.

785
00:38:33,656 --> 00:38:37,280
Pojdimo like-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Zato, ker smo že vedeli, da
te vrstice, 15 do 22,

787
00:38:40,444 --> 00:38:43,610
so working-- ker vse delam, je
Samo ponavljanjem skozi in printing--

788
00:38:43,610 --> 00:38:45,406
Lahko grem naprej in preskočite to.

789
00:38:45,406 --> 00:38:47,280
Začnimo na linijo 25.

790
00:38:47,280 --> 00:38:48,712
OOP, dovolite mi, da se znebite tega.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> OBČINSTVO: Torej prekinitvena točka je
kjer debugging začne?

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: Or ustavi.

794
00:38:54,890 --> 00:38:55,670
OBČINSTVO: Ali ustavi.

795
00:38:55,670 --> 00:38:55,930
ANDI PENG: Ja.

796
00:38:55,930 --> 00:38:58,640
Nastavite lahko več prelomnih točk in
je lahko samo skok od enega do drugega.

797
00:38:58,640 --> 00:39:01,590
Toda v tem primeru ne vemo,
kjer se napaka dogaja.

798
00:39:01,590 --> 00:39:03,780
Tako smo samo želim
začeti od vrha navzdol.

799
00:39:03,780 --> 00:39:05,020
Ja.

800
00:39:05,020 --> 00:39:05,550
V REDU.

801
00:39:05,550 --> 00:39:08,460
>> Torej, ta črta tukaj, smo lahko korak.

802
00:39:08,460 --> 00:39:11,499
Si lahko ogledate tukaj,
imamo celo paleto.

803
00:39:11,499 --> 00:39:13,290
To so vrednote
da so v matriki.

804
00:39:13,290 --> 00:39:16,360
Se vam zdi, da je, kako indeks 0, je
ustreza value-- oh,

805
00:39:16,360 --> 00:39:17,526
Bom poskusil, da jo povečate.

806
00:39:17,526 --> 00:39:20,650
Oprostite, to je res težko
da see-- na matrično indeksu 0,

807
00:39:20,650 --> 00:39:24,090
imamo vrednost 4 in
nato tako naprej in tako naprej.

808
00:39:24,090 --> 00:39:25,670
Imamo lokalnih spremenljivk.

809
00:39:25,670 --> 00:39:28,570
Zdaj i je enaka
0, kar smo želeli, da je.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> In tako naj ohranimo odskočna skozi.

812
00:39:33,690 --> 00:39:36,850
Naše najmanjše je enaka 0,
ki smo ga prav tako želeli, da je.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
In potem vnesemo našo drugo za
zanka, če je matrika-j manj kot matrično-i,

815
00:39:45,560 --> 00:39:46,380
ki ni bilo.

816
00:39:46,380 --> 00:39:48,130
Torej si videl, kako
da je preskočila več kot to?

817
00:39:48,130 --> 00:39:52,430
>> OBČINSTVO: Torej bi morala, če
minimum, vse that-- ne bi smeli da

818
00:39:52,430 --> 00:39:55,424
biti znotraj prva za zanko?

819
00:39:55,424 --> 00:39:57,340
ANDI PENG: Ne, ker
ste vedno želeli preizkusiti.

820
00:39:57,340 --> 00:40:00,329
Hočeš narediti primerjavo vsak
čas, tudi po tem, ko teče skozenj.

821
00:40:00,329 --> 00:40:02,620
Vi ne samo želim, da to storite
na prvem pass-through.

822
00:40:02,620 --> 00:40:05,240
Hočeš, da to storite z
vsak dodatni znova podaja.

823
00:40:05,240 --> 00:40:07,198
Torej hočeš, da preverite
vaše stanje v notranjosti.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Torej smo le, da bo
teče tu skozi.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Dam ti fantje namig.

828
00:40:18,420 --> 00:40:23,910
To je povezano z dejstvom, da, ko
ste preverjanje vaše pogojena,

829
00:40:23,910 --> 00:40:26,600
niste preverjanje
Za pravilno indeksa.

830
00:40:26,600 --> 00:40:32,510
Torej, zdaj ste preverjanje
Niz indeks j manj kot niz

831
00:40:32,510 --> 00:40:33,970
Indeks i.

832
00:40:33,970 --> 00:40:36,580
Ampak, kaj počneš na
na začetku zanke?

833
00:40:36,580 --> 00:40:38,260
Ali nisi nastavitev j enak i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Ja, tako da bomo lahko dejansko
zapustite razhroščevalnik tukaj.

836
00:40:45,415 --> 00:40:47,040
Torej, dajmo si oglejte našo psevdokoda.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- bomo
začeti na i je enak 0.

839
00:40:52,580 --> 00:40:54,760
Mi smo šli do n minus 1.

840
00:40:54,760 --> 00:40:58,040
Poglejmo, ali imamo to pravico?

841
00:40:58,040 --> 00:40:59,580
Ja, to je bilo v redu.

842
00:40:59,580 --> 00:41:02,080
>> Torej notri tukaj, smo
bo vzpostavila minimalno vrednost

843
00:41:02,080 --> 00:41:03,630
in nastavite, da je enako i.

844
00:41:03,630 --> 00:41:04,950
Ali bomo to naredili?

845
00:41:04,950 --> 00:41:06,270
Ja, to storil.

846
00:41:06,270 --> 00:41:10,430
Zdaj v naši notranji za zanke, smo
storili j enaka i za n minus 1.

847
00:41:10,430 --> 00:41:11,950
Ali bomo to naredili?

848
00:41:11,950 --> 00:41:15,540
Dejansko smo naredili to.

849
00:41:15,540 --> 00:41:19,922
>> Tako pa, kaj bomo primerjali tukaj?

850
00:41:19,922 --> 00:41:20,925
>> OBČINSTVO: j plus 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Točno tako.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
In potem boste želeli nastaviti
vaša najnižja enaka j plus 1, kot tudi.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Zato sem šel skozi to res hitro.

856
00:41:32,640 --> 00:41:36,190
Ali vi razumete
zakaj je j plus 1?

857
00:41:36,190 --> 00:41:36,890
V REDU.

858
00:41:36,890 --> 00:41:40,700
>> Torej, v vašem polju, v
vaš prvi navijači,

859
00:41:40,700 --> 00:41:44,850
Vaše zanko, za int
i je enak 0, kaj je samo

860
00:41:44,850 --> 00:41:46,740
prevzame to še ni spremenila.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Imamo celo paleto, popolnoma,
le štiri nesortirane elementi, kajne?

863
00:41:56,760 --> 00:42:00,760
Zato želimo inicializacijo i enaka 0.

864
00:42:00,760 --> 00:42:03,650
In jaz se dogaja, da samo
teči skozi to zanko.

865
00:42:03,650 --> 00:42:08,560
In tako v prvem priložnost, gremo
inicializirati spremenljivko z imenom "min"

866
00:42:08,560 --> 00:42:11,245
da je enako tudi jaz, saj
nimamo najmanjšo vrednost.

867
00:42:11,245 --> 00:42:12,870
Tako da je trenutno enaka 0, kot dobro.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
In potem smo šli skozi.

870
00:42:17,640 --> 00:42:19,270
In želimo še enkrat ponoviti.

871
00:42:19,270 --> 00:42:22,900
Zdaj, ko smo našli tisto, kar je naša minimalna
je, da želimo, da ponovitev prek

872
00:42:22,900 --> 00:42:25,190
še enkrat, da vidim, če je to primerjavo, kajne?

873
00:42:25,190 --> 00:42:40,440
Torej j, tu se dogaja
do enakega I, ki je 0.

874
00:42:40,440 --> 00:42:46,320
In potem, če matrika j plus i, ki
je tista, ki je poleg več, kot manj

875
00:42:46,320 --> 00:42:49,270
od tistega, kar vaš trenutni minimum
vrednost, ki ga želite zamenjati.

876
00:42:49,270 --> 00:42:56,850
>> Torej Dovolite samo reči, ki smo jih
nimajo podobno, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Zdaj, jaz je enaka
0 in je j enak 0.

878
00:43:01,610 --> 00:43:05,210
In to je naša najmanjša vrednost.

879
00:43:05,210 --> 00:43:09,950
Če matrično-j plus i-- tako da če eden
da je po eni smo gledate

880
00:43:09,950 --> 00:43:13,450
je večji kot tisti pred njim,
to se dogaja, da postane minimalna.

881
00:43:13,450 --> 00:43:18,120
>> Torej, tukaj vidimo, da 5
ne manj kot to.

882
00:43:18,120 --> 00:43:19,730
Tako se dogaja, da ne bo 5.

883
00:43:19,730 --> 00:43:23,580
Vidimo, da je manj kot 2, desno 1?

884
00:43:23,580 --> 00:43:32,970
Zdaj vemo, da je naša minimalna
bo vrednost indeksa pri 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Ja?

886
00:43:34,030 --> 00:43:39,170
In potem, ko si tu dol,
lahko swap pravilne vrednosti.

887
00:43:39,170 --> 00:43:42,610
>> Torej, ko vidva bile samo ob j
Prej, niste bili videti na enem

888
00:43:42,610 --> 00:43:43,260
po njej.

889
00:43:43,260 --> 00:43:44,520
Ste iskali na
enako vrednost, ki

890
00:43:44,520 --> 00:43:46,290
Zato je le bilo ničesar ne počne.

891
00:43:46,290 --> 00:43:49,721
Ali, da je smiselno, da se vsem,
Zato je potrebno, da je plus 1 tam?

892
00:43:49,721 --> 00:43:50,220
V REDU.

893
00:43:50,220 --> 00:43:53,345
Zdaj pa samo teče skozi to, da bi
Preverite, ali je preostali del kode je pravilen.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Zakaj se to dogaja?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, to je min tukaj.

898
00:44:16,364 --> 00:44:17,780
Bili smo primerjali napačno vrednost.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
O, ne.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh ja, tukaj smo bili
zamenjavo napačne vrednote, kot dobro.

903
00:44:33,482 --> 00:44:34,940
Ker smo iskali na i in j.

904
00:44:34,940 --> 00:44:36,440
To so tisti, ki smo bili preverjanja.

905
00:44:36,440 --> 00:44:39,160
Pravzaprav želimo, da bi zamenjali
minimum, sedanja minimalna,

906
00:44:39,160 --> 00:44:40,550
z karkoli tisti zunaj je.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
In kot lahko vi vidite navzdol
Tu imamo urejen niz.

909
00:45:05,402 --> 00:45:07,110
Samo moral storiti z
dejstvo, da kadar

910
00:45:07,110 --> 00:45:09,350
smo preverjanju podatkov
Vrednosti smo primerjali,

911
00:45:09,350 --> 00:45:11,226
nismo iskali na pravih vrednotah.

912
00:45:11,226 --> 00:45:13,850
Iskali smo na isti enem
tukaj, ne dejansko zamenjavo.

913
00:45:13,850 --> 00:45:17,135
Moraš pogledati na enem naslednjem
z njim in potem lahko swap.

914
00:45:17,135 --> 00:45:19,260
Torej, to je tisto, kar je bilo nekako
Pred utrujaš našo kodo.

915
00:45:19,260 --> 00:45:22,460
In kaj sem naredil tukaj je vse
Razhroščevalnik bi lahko storili za vas

916
00:45:22,460 --> 00:45:23,810
Pravkar sem to storil na
odbor, ker je lažje

917
00:45:23,810 --> 00:45:26,320
da vidim, namesto da poskuša
da povečate razhroščevalnik.

918
00:45:26,320 --> 00:45:29,391
Ali, da je smiselno, da vse?

919
00:45:29,391 --> 00:45:29,890
Cool.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> V redu.

922
00:45:35,410 --> 00:45:41,070
Mi lahko premaknete na govorimo o
asimptotska zapis, ki

923
00:45:41,070 --> 00:45:44,580
je samo fancy način pravijo
runtimes vseh teh vrst.

924
00:45:44,580 --> 00:45:47,650
Zato vem, Davida, v predavanju,
dotaknili runtimes.

925
00:45:47,650 --> 00:45:52,124
In je šel skozi celotno formulo
kako izračunati runtimes.

926
00:45:52,124 --> 00:45:53,040
Ni skrbi, da je.

927
00:45:53,040 --> 00:45:54,660
Če ste res radoveden
o tem, kako to deluje,

928
00:45:54,660 --> 00:45:55,810
vas prosimo, da govori z mano po oddelku.

929
00:45:55,810 --> 00:45:57,560
Mi lahko sprehod skozi
formule skupaj.

930
00:45:57,560 --> 00:46:00,689
Ampak vsi fantje imajo res
vedo, da n kvadrat več kot 2

931
00:46:00,689 --> 00:46:01,980
je ista stvar kot n kvadrat.

932
00:46:01,980 --> 00:46:04,710
Ker največjim številom,
eksponent, raste najbolj.

933
00:46:04,710 --> 00:46:06,590
In tako za naše namene,
Vse nas skrbi

934
00:46:06,590 --> 00:46:09,470
je, da velikan število, ki raste.

935
00:46:09,470 --> 00:46:13,340
>> Torej, kaj je najboljši primer
runtime izbirnega vrste?

936
00:46:13,340 --> 00:46:15,830
Če boste imeli
Ponovil skozi seznam

937
00:46:15,830 --> 00:46:18,712
in potem ponovitev prek
preostali del tega seznama,

938
00:46:18,712 --> 00:46:20,420
kolikokrat so
boš verjetno,

939
00:46:20,420 --> 00:46:24,612
v najslabšem case-- v
Najboljši primer, sorry-- teče skozi?

940
00:46:24,612 --> 00:46:27,070
Morda je bolje, vprašanje je,
vprašati, kaj je v najslabšem primeru

941
00:46:27,070 --> 00:46:28,153
runtime od izbora vrste.

942
00:46:28,153 --> 00:46:29,366
OBČINSTVO: n kvadrat.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: To je n kvadrat desno.

944
00:46:30,740 --> 00:46:36,986
Tako enostaven način, da pomislim, je to podobno,
kadarkoli imate dve prepleteni za zanke,

945
00:46:36,986 --> 00:46:38,110
to se dogaja, da se n kvadrat.

946
00:46:38,110 --> 00:46:40,386
Saj ne le, da so ti
teče skozi enkrat,

947
00:46:40,386 --> 00:46:42,260
moraš iti nazaj
okoli in teče skozi njo

948
00:46:42,260 --> 00:46:44,980
enkrat notri za vsako vrednost.

949
00:46:44,980 --> 00:46:48,640
Torej, v tem primeru, ste tekmovanje v teku n
krat n kvadrat, ki is-- žal,

950
00:46:48,640 --> 00:46:50,505
n krat n, ki je enaka n kvadrat.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> In nekako je tudi malo
edinstven v smislu

953
00:46:56,360 --> 00:46:59,774
da ni važno, če ti
Vrednosti so že v redu.

954
00:46:59,774 --> 00:47:01,440
To se še vedno dogaja, da teče skozi nekako.

955
00:47:01,440 --> 00:47:03,872
Naj samo povem, da je to 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Ne glede na to, ali je bilo v
Da, še vedno bi tekel skozi

957
00:47:07,080 --> 00:47:08,620
in še vedno preveriti minimalno vrednost.

958
00:47:08,620 --> 00:47:10,100
To bi postavil na
Enako število pregledov

959
00:47:10,100 --> 00:47:12,780
vsak čas, tudi če je to
dejansko ni ničesar dotakniti.

960
00:47:12,780 --> 00:47:16,940
>> Torej, v takem primeru je najboljše in najslabše
runtimes so dejansko enakovredni.

961
00:47:16,940 --> 00:47:19,160
Torej pričakovani runtime
od izbora vrste,

962
00:47:19,160 --> 00:47:23,790
ki smo ga imenuje s simbolom
od theta, theta, v tem primeru,

963
00:47:23,790 --> 00:47:24,790
bi tudi n kvadrat.

964
00:47:24,790 --> 00:47:26,480
Vse tri od teh bi n kvadrat.

965
00:47:26,480 --> 00:47:29,653
Vsakdo je jasno, zakaj
runtime je n kvadrat?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> V redu.

968
00:47:33,980 --> 00:47:39,120
Tako da sem le, da bo hitro teči
preko ostalih vrst.

969
00:47:39,120 --> 00:47:41,137
Algoritem za
bubble sort-- spomnite,

970
00:47:41,137 --> 00:47:43,220
To je bila prva
David je šel čez v predavanju.

971
00:47:43,220 --> 00:47:46,000
V bistvu, stopiš
skozi celoten seznam

972
00:47:46,000 --> 00:47:48,950
in vi ste swap-- pravkar
primerjati dva naenkrat.

973
00:47:48,950 --> 00:47:51,350
In če je večja,
od tebe samo swap njih.

974
00:47:51,350 --> 00:47:53,590
Torej, če so ti višji, bi vas zamenjali.

975
00:47:53,590 --> 00:47:56,180
Imam uradni tukaj.

976
00:47:56,180 --> 00:47:59,100
>> Torej, recimo, da imaš 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Ti bi pa jih primerjati med 8 in 6.

978
00:48:00,571 --> 00:48:01,570
Ti bi morali, da jih swap.

979
00:48:01,570 --> 00:48:02,610
Vi bi primerjal 8 in 4.

980
00:48:02,610 --> 00:48:03,609
Ti bi morali, da jih swap.

981
00:48:03,609 --> 00:48:07,000
Če imate, da bi zamenjali 8 in
z 2, jih spremeniti, pa tudi.

982
00:48:07,000 --> 00:48:10,760
Torej v takem smislu, lahko vidite,
odvija v daljšem časovnem obdobju,

983
00:48:10,760 --> 00:48:13,730
kako vrednote vrsta balona na
konci, kar je razlog, zakaj ga imenujemo

984
00:48:13,730 --> 00:48:15,320
bubble nekako.

985
00:48:15,320 --> 00:48:19,950
>> Mi bi samo teče skozi spet na
naš drugi pass, in naš tretji napadalca,

986
00:48:19,950 --> 00:48:21,150
in naša četrta akcije.

987
00:48:21,150 --> 00:48:25,820
V bistvu, bubble nekako samo teče
dokler se ne bo več nobene zamenjave.

988
00:48:25,820 --> 00:48:31,109
Torej v tem smislu, da je to le
splošna psevdokoda za to.

989
00:48:31,109 --> 00:48:32,650
Brez skrbi, to bo vse na spletu.

990
00:48:32,650 --> 00:48:34,990
Nimamo dejansko iti čez to.

991
00:48:34,990 --> 00:48:38,134
>> Pravkar smo inicializacijo števec
spremenljivka, ki se začne pri 0.

992
00:48:38,134 --> 00:48:39,800
In mi ponovitev prek celotnega niza.

993
00:48:39,800 --> 00:48:43,420
In če ena vrednost is--, če je to
je vrednost večja od te vrednosti,

994
00:48:43,420 --> 00:48:44,610
boš swap njih.

995
00:48:44,610 --> 00:48:46,860
In potem ste pravkar
dogaja, da nadaljujem.

996
00:48:46,860 --> 00:48:47,970
In boš prešteti.

997
00:48:47,970 --> 00:48:50,845
In ste šele tekoč, da delaš
to pa števec večja

998
00:48:50,845 --> 00:48:53,345
od 0, kar pomeni, da
Vsakič, ko boste morali zamenjati,

999
00:48:53,345 --> 00:48:55,220
veš želite iti
nazaj in ponovno preverite.

1000
00:48:55,220 --> 00:48:59,510
Želite obdržati kontrolo, dokler ne veste,
da vam ni treba več zamenjati.

1001
00:48:59,510 --> 00:49:05,570
>> Torej, kaj so najboljše in najslabše
Primer runtimes za bubble vrste?

1002
00:49:05,570 --> 00:49:09,300
In hint-- to je dejansko drugačna
od izbora vrste v smislu

1003
00:49:09,300 --> 00:49:11,810
da sta ti dve odgovori niso enake.

1004
00:49:11,810 --> 00:49:14,709
Pomisli, kaj bi se zgodilo v
primer, če je že urejeno.

1005
00:49:14,709 --> 00:49:16,500
In pomislite, kaj
bi se zgodilo, če bi bilo

1006
00:49:16,500 --> 00:49:18,372
v primeru, v katerem ni bilo urejeno.

1007
00:49:18,372 --> 00:49:20,580
In lahko nekako teči
s zakaj to dogaja.

1008
00:49:20,580 --> 00:49:22,954
Dam ti fantje, kot so, 30
sekund, da razmišljajo o tem.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> V REDU.

1011
00:49:53,540 --> 00:49:57,462
Ima kdo ugibati, kaj je
najslabšem primeru runtime mehurčkov vrste je?

1012
00:49:57,462 --> 00:49:57,962
Ja.

1013
00:49:57,962 --> 00:50:07,810
>> OBČINSTVO: Bi bilo, kot, n-krat
n minus 1 ali nekaj takega?

1014
00:50:07,810 --> 00:50:10,650
Kot, vsakič, ko ga zmanjka,
to je samo, kot en swap manj

1015
00:50:10,650 --> 00:50:10,960
da je vse, kar je bilo.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Ja, tako
ste popolnoma prav.

1017
00:50:12,668 --> 00:50:15,940
In to je primer, v katerem si
Odgovor je bil v resnici bolj zapletena

1018
00:50:15,940 --> 00:50:17,240
od tistega moramo dati.

1019
00:50:17,240 --> 00:50:19,772
Tako se dogaja, da run-- sem
dogaja, da izbrišete vse to tukaj.

1020
00:50:19,772 --> 00:50:20,480
So vsi dobri?

1021
00:50:20,480 --> 00:50:21,869
Morem izbrisati to?

1022
00:50:21,869 --> 00:50:22,368
V REDU.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Ti boš teči skozi n
krat prvič, kajne?

1025
00:50:30,320 --> 00:50:33,200
In oni 'tekoč teči skozi
n minus 1 drugič, kajne?

1026
00:50:33,200 --> 00:50:37,130
In potem boš obdržati
dogaja, n rudnik 2, et cetera.

1027
00:50:37,130 --> 00:50:40,210
David je to naredil na predavanju, kjer je,
če se seštejejo vse tiste vrednote,

1028
00:50:40,210 --> 00:50:48,080
dobiš nekaj, kar je like-- yeah--
več kot 2, ki v bistvu le zmanjšuje

1029
00:50:48,080 --> 00:50:49,784
do n kvadrati.

1030
00:50:49,784 --> 00:50:51,700
Boste dobili
čudno frakcija tam.

1031
00:50:51,700 --> 00:50:53,892
In tako samo vem, da
n kvadrat vedno

1032
00:50:53,892 --> 00:50:55,350
ima prednost pred frakcije.

1033
00:50:55,350 --> 00:50:58,450
In tako v tem primeru, najslabša
runtime bi n kvadrat.

1034
00:50:58,450 --> 00:51:00,210
Če je bilo v padajočem
Da, mislim, vi

1035
00:51:00,210 --> 00:51:02,530
morali narediti swap vsak čas.

1036
00:51:02,530 --> 00:51:05,170
>> Kaj bi bilo, potencialno
najboljši primer runtime?

1037
00:51:05,170 --> 00:51:08,580
Recimo samo, če je bil seznam že
V redu, kaj bi bilo runtime bilo?

1038
00:51:08,580 --> 00:51:09,565
>> OBČINSTVO: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: To je n, točno.

1040
00:51:10,690 --> 00:51:11,600
In zakaj je to n?

1041
00:51:11,600 --> 00:51:13,850
OBČINSTVO: Ker vas samo
morali preveriti vsak enkrat.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Točno tako.

1043
00:51:14,770 --> 00:51:17,150
Torej v najboljšem možnem runtime,
če bi bil ta seznam že

1044
00:51:17,150 --> 00:51:20,270
sorted-- recimo, 1, 2, 3, 4-- si
bi samo šel skozi, bi morali preveriti,

1045
00:51:20,270 --> 00:51:21,720
bi videli, oh, so vsi pan ven.

1046
00:51:21,720 --> 00:51:22,636
Nisem morali zamenjati.

1047
00:51:22,636 --> 00:51:23,370
Končal sem.

1048
00:51:23,370 --> 00:51:26,500
Torej, v tem primeru, saj je samo n
ali število korakov, ki ste jo pravkar

1049
00:51:26,500 --> 00:51:29,870
moral preveriti na prvem seznamu.

1050
00:51:29,870 --> 00:51:33,990
>> In potem smo zdaj hit
vstavljanje razvrščanje, kjer

1051
00:51:33,990 --> 00:51:39,260
algoritem je v bistvu za divide
je v urejenem in nerazvrščene obrok.

1052
00:51:39,260 --> 00:51:42,810
In potem enega po enega,
nerazvrščenih vrednosti

1053
00:51:42,810 --> 00:51:46,880
vstavljena v njihovo ustrezno
pozicije v začetku seznama.

1054
00:51:46,880 --> 00:51:52,120
>> Tako, na primer, imamo
seznam 3, 5, 2, 6, 4 znova.

1055
00:51:52,120 --> 00:51:54,750
Vemo, da je trenutno
razvrščeni ker smo pravkar

1056
00:51:54,750 --> 00:51:57,030
začeli gledaš na to.

1057
00:51:57,030 --> 00:52:00,610
Mi si oglejte in vemo, da
prva vrednost je razvrščen, kajne?

1058
00:52:00,610 --> 00:52:04,190
Če iščete samo na paleto
velikost enega, veš, da je to urejeno.

1059
00:52:04,190 --> 00:52:08,230
>> Torej vemo, da je
Ostali štirje so razvrščeni.

1060
00:52:08,230 --> 00:52:10,980
Gremo skozi in smo videli, da je vrednost.

1061
00:52:10,980 --> 00:52:11,730
Pojdimo nazaj.

1062
00:52:11,730 --> 00:52:13,130
Glej, da vrednost 5?

1063
00:52:13,130 --> 00:52:14,110
Bomo pogled na to.

1064
00:52:14,110 --> 00:52:15,204
Mi ga primerjajte s 3.

1065
00:52:15,204 --> 00:52:17,870
Vemo, da je večja od
3, tako da vemo, da je to urejeno.

1066
00:52:17,870 --> 00:52:22,940
Tako zdaj vemo, da sta prva dva
so razporejene, zadnji trije pa niso.

1067
00:52:22,940 --> 00:52:24,270
>> Mi si oglejte 2.

1068
00:52:24,270 --> 00:52:25,720
Najprej smo ga preveri s 5.

1069
00:52:25,720 --> 00:52:26,700
Je manj kot 5?

1070
00:52:26,700 --> 00:52:27,240
Ni.

1071
00:52:27,240 --> 00:52:29,510
Zato moramo obdržati gleda.

1072
00:52:29,510 --> 00:52:30,940
Potem si oglejte 2 off 3.

1073
00:52:30,940 --> 00:52:31,850
Je manj kot?

1074
00:52:31,850 --> 00:52:32,350
No.

1075
00:52:32,350 --> 00:52:35,430
Toliko, da veš 2 se vstavi
v sprednji in 3 in 5

1076
00:52:35,430 --> 00:52:38,200
imata, da ga vlečejo ven.

1077
00:52:38,200 --> 00:52:42,190
Spet naredite to z 6 in 4.

1078
00:52:42,190 --> 00:52:48,962
In smo samo sproti preverja v bistvu,
kjer smo samo preveriti, preverite, preverite.

1079
00:52:48,962 --> 00:52:51,170
In dokler je v desno
Položaj smo nekako le

1080
00:52:51,170 --> 00:52:54,890
ga vstavite v pravilnem položaju,
ki je, če je ime nje prišli.

1081
00:52:54,890 --> 00:52:59,830
>> Torej, to je samo algoritem,
psevdokoda per se, vrsta,

1082
00:52:59,830 --> 00:53:04,990
o tem, kako bi izvajanje
vstavljanja vrste.

1083
00:53:04,990 --> 00:53:05,954
Psevdokoda je tukaj.

1084
00:53:05,954 --> 00:53:06,620
To je vse na spletu.

1085
00:53:06,620 --> 00:53:10,720
Brez skrbi, če se vidva
poskušajo kopirati to navzdol.

1086
00:53:10,720 --> 00:53:14,500
Torej še enkrat, isto question-- kaj
bi bilo najbolje in najslabše runtimes

1087
00:53:14,500 --> 00:53:16,120
za vstavljanje vrste?

1088
00:53:16,120 --> 00:53:17,750
To je zelo podoben zadnje vprašanje.

1089
00:53:17,750 --> 00:53:20,479
Dam ti fantje, kot so, 30
sekund, da razmišljajo o tem, kot dobro.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Ali kdo želi
daj mi najhujšo runtime?

1092
00:53:50,071 --> 00:53:50,570
Ja.

1093
00:53:50,570 --> 00:53:51,490
>> OBČINSTVO: n kvadrat.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI PENG: To je n kvadrat.

1095
00:53:52,573 --> 00:53:53,730
In zakaj je to n kvadrat?

1096
00:53:53,730 --> 00:53:57,562
>> OBČINSTVO: Ker v
obratnem vrstnem redu, imate

1097
00:53:57,562 --> 00:54:02,619
iti skozi n krat n, ki is--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Ja, točno.

1099
00:54:03,660 --> 00:54:06,610
Torej isto, kot v mehurček vrste.

1100
00:54:06,610 --> 00:54:08,720
Če je ta seznam v
padajočem vrstnem redu, vi ste

1101
00:54:08,720 --> 00:54:11,240
bodo morali preveriti, prvi enkrat.

1102
00:54:11,240 --> 00:54:13,470
In potem z vsakim
dodatno vrednost, ste

1103
00:54:13,470 --> 00:54:16,390
bodo morali preveriti pred
vsak vrednost, kajne?

1104
00:54:16,390 --> 00:54:20,290
In tako v celoti, si boste, da bi
an krat n napadalca drugo n pass, ki

1105
00:54:20,290 --> 00:54:21,750
je n kvadrat.

1106
00:54:21,750 --> 00:54:22,860
Kaj o najboljšem primeru?

1107
00:54:22,860 --> 00:54:24,360
Ja.

1108
00:54:24,360 --> 00:54:28,840
>> SKUPINA: n minus 1, saj
Prvi je že na kvadrat.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Torej, blizu.

1110
00:54:30,270 --> 00:54:31,850
Odgovor je pravzaprav n.

1111
00:54:31,850 --> 00:54:37,189
Ker pa prva je
razporejene, je ne more actually--

1112
00:54:37,189 --> 00:54:38,980
smo pravkar lucked ven, v
da je na primer, da je 2

1113
00:54:38,980 --> 00:54:40,930
zgodilo, da se najmanjše število.

1114
00:54:40,930 --> 00:54:43,680
Ampak, da ne bo vedno tako.

1115
00:54:43,680 --> 00:54:48,040
Če je 2 že razporejene v začetku
ampak pogledaš in tam je 1 tukaj,

1116
00:54:48,040 --> 00:54:49,144
za 1 se dogaja, da jo prestavim.

1117
00:54:49,144 --> 00:54:51,060
In to se dogaja, da končate
up se nekako vrč.

1118
00:54:51,060 --> 00:54:56,250
>> Torej v najboljšem primeru,
To je pravzaprav šele bo n.

1119
00:54:56,250 --> 00:54:59,090
Če imate 1, 2, 3,
4, 5, 6, 7, 8, si

1120
00:54:59,090 --> 00:55:00,940
tekoč teči skozi
da celoten seznam enkrat

1121
00:55:00,940 --> 00:55:03,430
preveriti, da vidim, če vse je v redu.

1122
00:55:03,430 --> 00:55:07,390
Vsakdo je jasno, na tek
krat izbire, kot tudi?

1123
00:55:07,390 --> 00:55:09,960
Vem, da bom s pomočjo
ti zelo hitro.

1124
00:55:09,960 --> 00:55:13,330
Ampak samo vem, da če veste
splošnih pojmov, morate biti dobro.

1125
00:55:13,330 --> 00:55:16,070
V REDU.

1126
00:55:16,070 --> 00:55:19,790
Torej bom samo vam fantje morda, kot so,
minuto, da se pogovorite s svojim sosedom

1127
00:55:19,790 --> 00:55:21,890
o tem, kaj so le nekateri
od glavnih razlik

1128
00:55:21,890 --> 00:55:23,540
med temi vrstami vrst.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Mi bomo šli čez, da kmalu.

1131
00:56:25,570 --> 00:56:26,444
OBČINSTVO: Oh, v redu.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Ja.

1133
00:56:27,320 --> 00:56:28,380
V REDU.

1134
00:56:28,380 --> 00:56:33,420
Cool, kaj je sestati kot razred.

1135
00:56:33,420 --> 00:56:34,330
V REDU.

1136
00:56:34,330 --> 00:56:37,579
Torej je bila to nekakšna
odprta vprašanja v smislu

1137
00:56:37,579 --> 00:56:39,120
da obstaja veliko odgovorov nanje.

1138
00:56:39,120 --> 00:56:40,746
In bomo šli čez nekatere od njih na kratko.

1139
00:56:40,746 --> 00:56:43,411
Želela sem, da bi dobili fantje
razmišljam o tem, kaj razlikuje

1140
00:56:43,411 --> 00:56:44,530
vse tri vrste vrst.

1141
00:56:44,530 --> 00:56:47,440
In slišal sem, tudi, velik
question-- kaj zlivanjem storiti?

1142
00:56:47,440 --> 00:56:50,110
Great vprašanje, ker je to
kaj smo zajema naslednje.

1143
00:56:50,110 --> 00:56:52,850
>> Torej zlivanjem je
ena vrsta, ki deluje

1144
00:56:52,850 --> 00:56:56,100
zelo različno od drugih vrst.

1145
00:56:56,100 --> 00:56:58,180
Kot lahko vidva see--
je David to naredil demo

1146
00:56:58,180 --> 00:57:01,130
kjer je imel vse kul
trušč vidim, kako združiti

1147
00:57:01,130 --> 00:57:04,010
nekako tekel, kot so, neskončno
hitreje kot drugi dve vrsti?

1148
00:57:04,010 --> 00:57:04,510
V REDU.

1149
00:57:04,510 --> 00:57:07,580
Torej, to je zato, ker se združita
Razvrsti izvaja to ločnico

1150
00:57:07,580 --> 00:57:11,020
in osvojiti koncept, ki smo jih
govoril o veliko v predavanju.

1151
00:57:11,020 --> 00:57:14,550
V tem smislu, da želimo delati
pametneje, ne težje, ko si razdeliti

1152
00:57:14,550 --> 00:57:18,120
in osvojiti probleme, in jih odmor
navzdol, nato pa jih skupaj,

1153
00:57:18,120 --> 00:57:19,930
dobre stvari vedno dogajajo.

1154
00:57:19,930 --> 00:57:21,960
>> Torej tako, da združijo
nekako v bistvu deluje

1155
00:57:21,960 --> 00:57:24,660
je, da ločuje
nesortirani matrika na pol.

1156
00:57:24,660 --> 00:57:26,500
In potem je dobil dve polovici nizi.

1157
00:57:26,500 --> 00:57:28,220
In to samo razvrsti teh dveh polovic.

1158
00:57:28,220 --> 00:57:31,750
To samo ohranja delimo na pol, v
pol, na pol, dokler se vse razporejene

1159
00:57:31,750 --> 00:57:33,680
in nato rekurzivno
ga postavlja vse skupaj.

1160
00:57:33,680 --> 00:57:36,550
>> Tako, da je res abstraktna.

1161
00:57:36,550 --> 00:57:38,750
Torej je to le malo psevdokoda.

1162
00:57:38,750 --> 00:57:41,040
Ali, da je smiselno v
tako, kot je tek?

1163
00:57:41,040 --> 00:57:43,870
Torej Dovolite samo povem, imate
array n elementov, kajne?

1164
00:57:43,870 --> 00:57:45,450
Če je n manj kot 2, se lahko vrnete.

1165
00:57:45,450 --> 00:57:49,040
Ker veš, da če je
Samo ena stvar je treba razporejene.

1166
00:57:49,040 --> 00:57:52,600
Else, boste razvrstiti levo polovico,
nato pa razvrstite desno polovico,

1167
00:57:52,600 --> 00:57:54,140
in potem si združita.

1168
00:57:54,140 --> 00:57:56,979
>> Torej, medtem ko je videti zelo enostavno,
v resnici, razmišljam o tem je

1169
00:57:56,979 --> 00:58:00,270
nekako težko. Ker ste všeč,
No, to je nekako teče sama.

1170
00:58:00,270 --> 00:58:00,769
Prav?

1171
00:58:00,769 --> 00:58:02,430
To je tekmovanje v teku na sebi.

1172
00:58:02,430 --> 00:58:05,479
Torej, v tem smislu, David dotaknil
ob rekurzije v razredu.

1173
00:58:05,479 --> 00:58:07,270
In to je koncept
bomo govorili o več.

1174
00:58:07,270 --> 00:58:11,430
To je, da so to ti dve vrstici
tukaj, v resnici je samo program

1175
00:58:11,430 --> 00:58:13,860
je povedal, da se vodijo
z različno močjo.

1176
00:58:13,860 --> 00:58:17,230
Torej, namesto da se vozijo z
celota n elementov,

1177
00:58:17,230 --> 00:58:20,530
lahko ga razdeliti na
levo polovico in desno polovico

1178
00:58:20,530 --> 00:58:22,680
in ga nato znova zaženite.

1179
00:58:22,680 --> 00:58:26,050
>> In potem bomo pogled na to vizualno,
ker sem vizualni učenec.

1180
00:58:26,050 --> 00:58:27,270
To deluje bolje za mene.

1181
00:58:27,270 --> 00:58:29,890
Torej bomo pogled na vizualni primer tukaj.

1182
00:58:29,890 --> 00:58:36,237
>> Recimo, da imamo niz, šest
Elementi, 3, 5, 2, 6, 4, 1, niso razporejene.

1183
00:58:36,237 --> 00:58:37,820
Vse je v redu, tam je veliko na tej strani.

1184
00:58:37,820 --> 00:58:43,179
Torej, če lahko vi ogledate na
Prvi korak tukaj, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
jo lahko razdelili na pol.

1186
00:58:44,220 --> 00:58:45,976
Imate 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Saj veš, da ti te aren't--
Ne vem, če oni razporejene ali ne,

1188
00:58:48,850 --> 00:58:52,517
tako da boste vedno znova zrušijo, na pol,
na pol, na pol, dokler sčasoma,

1189
00:58:52,517 --> 00:58:53,600
imate samo en element.

1190
00:58:53,600 --> 00:58:56,790
In se en element vedno razporejene, kajne?

1191
00:58:56,790 --> 00:59:01,560
>> Torej vemo, da 3, 5, 2, 4, 6,
1, sami po sebi, so razporejene.

1192
00:59:01,560 --> 00:59:05,870
In zdaj smo jih lahko spet skupaj.

1193
00:59:05,870 --> 00:59:07,510
Torej vemo, 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Čaka smo tiste skupaj.

1195
00:59:08,510 --> 00:59:09,617
Vemo, da je razvrščeni.

1196
00:59:09,617 --> 00:59:10,450
V 2 je še vedno tam.

1197
00:59:10,450 --> 00:59:11,830
Mi lahko dal 4 in 6 skupaj.

1198
00:59:11,830 --> 00:59:13,996
Vemo, da je to urejeno,
tako smo se, da skupaj.

1199
00:59:13,996 --> 00:59:14,940
In 1 je tam.

1200
00:59:14,940 --> 00:59:18,720
>> In potem si poglej
ti dve polovici tukaj.

1201
00:59:18,720 --> 00:59:21,300
Imate 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Lahko samo primerjati
začetek vsega.

1203
00:59:23,465 --> 00:59:26,340
Ker veš, da je to urejeno
in veš, da je to urejeno.

1204
00:59:26,340 --> 00:59:29,360
Torej, potem ne boste imeli celo
primerjajo 5, ki ste jo pravkar primerjati 3.

1205
00:59:29,360 --> 00:59:32,070
In 2 manjši od 3, tako
veste 2 mora iti na koncu.

1206
00:59:32,070 --> 00:59:33,120
>> Ista stvar tam.

1207
00:59:33,120 --> 00:59:34,740
Za 1 mora iti tukaj.

1208
00:59:34,740 --> 00:59:37,330
In potem ko greš, da dajo
ti dve vrednosti skupaj,

1209
00:59:37,330 --> 00:59:39,950
ste vedeli, da je to urejeno in
ste vedeli, da je to urejeno.

1210
00:59:39,950 --> 00:59:43,240
Tedaj 1 in
2 je 1 manjši od 2.

1211
00:59:43,240 --> 00:59:45,570
To vam pove, da je 1
bi morala iti na koncu tega

1212
00:59:45,570 --> 00:59:47,480
celo brez gledaš 3 ali 5.

1213
00:59:47,480 --> 00:59:50,100
In potem na 4, lahko samo
preveriti, gre prav tu.

1214
00:59:50,100 --> 00:59:51,480
Nimate pogledati na 5.

1215
00:59:51,480 --> 00:59:52,570
Ista stvar s 6.

1216
00:59:52,570 --> 00:59:55,860
Saj veš, da 6-- je samo
Ni treba, da je treba preučiti.

1217
00:59:55,860 --> 00:59:57,870
>> In tako na ta način, da ste
Samo varčevanje sebe

1218
00:59:57,870 --> 00:59:59,526
veliko korakov, ko ste primerjali.

1219
00:59:59,526 --> 01:00:02,150
Nimate primerjati vsak
element v primerjavi z drugimi elementi.

1220
01:00:02,150 --> 01:00:05,230
Pravkar ste se primerjajo s tistimi,
da boste morali, da ga primerjajo.

1221
01:00:05,230 --> 01:00:06,870
Torej, to je nekako kot abstrakten pojem.

1222
01:00:06,870 --> 01:00:10,540
Brez skrbi, če to ni
precej vas tepe še desno.

1223
01:00:10,540 --> 01:00:14,740
Vendar na splošno, to je
kako zlivanjem deluje.

1224
01:00:14,740 --> 01:00:17,750
Vprašanja, hitre vprašanja,
preden sem korak naprej?

1225
01:00:17,750 --> 01:00:18,550
Ja.

1226
01:00:18,550 --> 01:00:22,230
>> OBČINSTVO: Torej, ste rekli, da ste vzeli
za 1, nato pa 4 in 6

1227
01:00:22,230 --> 01:00:23,860
in jih dal v.

1228
01:00:23,860 --> 01:00:26,800
Torej niso those-- niso
gledaš njih

1229
01:00:26,800 --> 01:00:28,544
kot ločenih elementov, ne kot celote?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Ja.

1231
01:00:29,210 --> 01:00:32,020
Torej, kaj se dogaja
je, da si v bistvu

1232
01:00:32,020 --> 01:00:33,650
ustvarjajo povsem novo paleto.

1233
01:00:33,650 --> 01:00:36,690
Torej veste, da je tu, imam
dve nizi velikosti 3, kajne?

1234
01:00:36,690 --> 01:00:39,600
Torej veste, da je moja sortirani niz
mora imeti šest elementov.

1235
01:00:39,600 --> 01:00:42,270
Torej si ustvarite
novo količino pomnilnika.

1236
01:00:42,270 --> 01:00:44,270
Torej ste nekako kot
pri čemer potratno spomina,

1237
01:00:44,270 --> 01:00:46,186
vendar to ni pomembno
ker je tako majhna.

1238
01:00:46,186 --> 01:00:48,590
Torej si poglej 1
in si poglej na 2.

1239
01:00:48,590 --> 01:00:50,770
In veste, da je manj kot 2 za 1.

1240
01:00:50,770 --> 01:00:53,840
Torej veste, da je treba iti v 1
začetek vse tiste.

1241
01:00:53,840 --> 01:00:55,850
>> Vam ni treba niti
poglej na 3 in 5.

1242
01:00:55,850 --> 01:00:57,400
Torej veste, 1 gre tja.

1243
01:00:57,400 --> 01:00:59,300
Potem ste v bistvu odsekati na 1.

1244
01:00:59,300 --> 01:01:00,370
To je, kot, mrtev za nas.

1245
01:01:00,370 --> 01:01:03,690
Potem imamo samo 2,
3, 5 in nato 4 in 6.

1246
01:01:03,690 --> 01:01:06,270
In potem veste, da vas
primerjajo 4 in 2,

1247
01:01:06,270 --> 01:01:07,560
Oh, 2 bi moral iti tja.

1248
01:01:07,560 --> 01:01:09,685
Torej si Pasti za 2 navzdol, jo odsekati.

1249
01:01:09,685 --> 01:01:12,060
Torej boste morali 3
in 5 pri 4 in 6.

1250
01:01:12,060 --> 01:01:14,650
In ti kar naprej ga sekljanje off
dokler jih dal v array.

1251
01:01:14,650 --> 01:01:17,110
>> OBČINSTVO: Torej ste pravkar vedno
primerjavo [neslišno]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Točno tako.

1253
01:01:17,710 --> 01:01:19,590
Torej, v tem smislu, da ste
samo primerjavo, v bistvu,

1254
01:01:19,590 --> 01:01:21,240
ena številka zoper drugo številko.

1255
01:01:21,240 --> 01:01:22,990
In ker veš
da je to urejeno, vam

1256
01:01:22,990 --> 01:01:24,350
ne bi bilo treba pogledati skozi
vse številke.

1257
01:01:24,350 --> 01:01:25,870
Moraš pogledati na prvega.

1258
01:01:25,870 --> 01:01:27,582
In potem si lahko samo Pljuskanje
jim dol, saj veš,

1259
01:01:27,582 --> 01:01:29,640
jim pripadajo, kjer so morali pripadati.

1260
01:01:29,640 --> 01:01:31,030
Ja.

1261
01:01:31,030 --> 01:01:32,920
Dobro vprašanje.

1262
01:01:32,920 --> 01:01:35,290
>> In potem, če kdo od vas
so malo ambiciozen,

1263
01:01:35,290 --> 01:01:38,660
vas prosimo, da pogled na to oznako.

1264
01:01:38,660 --> 01:01:40,680
To je dejansko
fizična izvedba

1265
01:01:40,680 --> 01:01:42,150
o tem, kako bi mi napisali zlivanjem.

1266
01:01:42,150 --> 01:01:44,070
In lahko vidite, da je zelo kratek.

1267
01:01:44,070 --> 01:01:46,310
Toda Zamisel
to so precej zapleteni.

1268
01:01:46,310 --> 01:01:50,865
Torej, če se počutite, kot risba tole
v svojo domačo nalogo nocoj, vas prosimo, da.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> V REDU.

1271
01:01:54,740 --> 01:01:58,070
Torej, David je šel tudi čez to v predavanju.

1272
01:01:58,070 --> 01:02:00,660
Kateri so najboljši primer
runtimes, najslabšem primeru runtimes,

1273
01:02:00,660 --> 01:02:05,680
in pričakovane runtimes z zlivanjem?

1274
01:02:05,680 --> 01:02:07,260
Nekaj ​​sekund razmišljati.

1275
01:02:07,260 --> 01:02:11,198
To je zelo težko, vendar vrsta
intuitivno, če mislite o tem.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
V redu.

1278
01:02:23,054 --> 01:02:25,269
>> OBČINSTVO: Je najslabšem primeru n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Točno tako.

1280
01:02:26,060 --> 01:02:29,380
In zakaj je n log n.

1281
01:02:29,380 --> 01:02:32,230
>> OBČINSTVO: Ali ni to zato, ker je
postane eksponentno hitreje,

1282
01:02:32,230 --> 01:02:35,390
tako je kot funkcija, ki
namesto samo preprosto čemer n

1283
01:02:35,390 --> 01:02:37,529
kvadrat ali kaj?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Točno tako.

1285
01:02:38,320 --> 01:02:40,750
Torej je razlog, zakaj je
runtime na to je n log

1286
01:02:40,750 --> 01:02:44,310
n je because-- kaj so ti
delaš v vseh teh korakov?

1287
01:02:44,310 --> 01:02:46,190
Ste pravkar sekljanje na pol, kajne?

1288
01:02:46,190 --> 01:02:48,750
In tako, ko sva početje
log, vse, kar počne

1289
01:02:48,750 --> 01:02:53,150
je tako, da se problem v polovici,
v polovici, v polovici, v več polovic.

1290
01:02:53,150 --> 01:02:56,430
In v tem smislu, lahko nekako
o odpravi linearnim modelom

1291
01:02:56,430 --> 01:02:57,510
da smo bili z uporabo.

1292
01:02:57,510 --> 01:03:00,254
Ker ko sesekljajte
stvari na pol, to je dnevnik.

1293
01:03:00,254 --> 01:03:02,420
To je samo matematična
način, ki ga zastopajo.

1294
01:03:02,420 --> 01:03:06,310
>> In potem na koncu, ob koncu, ste
samo izdelavo ene zadnjo podajo mimo

1295
01:03:06,310 --> 01:03:07,930
da dajo vse od njih v redu, kajne?

1296
01:03:07,930 --> 01:03:10,330
In tako, če boste morali
preveri eno stvar, ki je n.

1297
01:03:10,330 --> 01:03:13,420
In tako si nekako
množenjem dva skupaj.

1298
01:03:13,420 --> 01:03:17,660
Torej, to je, kot imaš, da je končna
preverite, n tu dol z log n

1299
01:03:17,660 --> 01:03:18,390
tu gor.

1300
01:03:18,390 --> 01:03:21,060
In če pomnožimo
jim, da je n log n.

1301
01:03:21,060 --> 01:03:26,100
>> In tako je najboljši primer in najslabše
primera in pričakovanjih so vse n log n.

1302
01:03:26,100 --> 01:03:27,943
To je tako kot druge vrste.

1303
01:03:27,943 --> 01:03:30,090
To je kot izbirni vrste
v smislu, da je

1304
01:03:30,090 --> 01:03:32,131
Ni važno, kaj je tvoj
seznam je, to je le, da bo

1305
01:03:32,131 --> 01:03:34,801
narediti isto stvar vsak čas.

1306
01:03:34,801 --> 01:03:35,300
V REDU.

1307
01:03:35,300 --> 01:03:39,950
Tako da lahko vi vidite, čeprav
so vrste, da smo šli through-- n

1308
01:03:39,950 --> 01:03:41,660
kvadrat, da ni zelo učinkovito.

1309
01:03:41,660 --> 01:03:47,060
In tudi to n log n
ni najbolj učinkovita.

1310
01:03:47,060 --> 01:03:49,720
Če sta vidva radovedni,
tam je Mehanizmi vrsta

1311
01:03:49,720 --> 01:03:54,310
ki so tako učinkoviti, da oni
skoraj v bistvu ravno v času izvajanja.

1312
01:03:54,310 --> 01:03:55,420
>> Imaš nekaj dnevnik n-jev.

1313
01:03:55,420 --> 01:03:58,190
Imaš nekaj dnevnik n dnevniku.

1314
01:03:58,190 --> 01:04:00,330
Ne dotikajte se nanje
V tem razredu prav zdaj.

1315
01:04:00,330 --> 01:04:02,663
Ampak, če ste fantje radovedni,
vas prosimo, da google, kaj je

1316
01:04:02,663 --> 01:04:04,392
najbolj učinkovitih mehanizmov za sortiranje.

1317
01:04:04,392 --> 01:04:06,350
Ne vem, obstajajo
nekateri res smešno tisti,

1318
01:04:06,350 --> 01:04:09,860
like-- tam je nekaj res
smešni tisti, ki jih ljudje naredijo.

1319
01:04:09,860 --> 01:04:12,210
In vas sprašujem, kako so
kdaj pomislil na to.

1320
01:04:12,210 --> 01:04:15,730
Torej, google, če imate nekaj prostega
Čas, on, kaj so nekatere smešne načine

1321
01:04:15,730 --> 01:04:17,730
da people-- ter
učinkovita ways-- ljudje

1322
01:04:17,730 --> 01:04:20,371
so bili sposobni izvajati vrst.

1323
01:04:20,371 --> 01:04:20,870
V REDU.

1324
01:04:20,870 --> 01:04:22,880
In tukaj je samo priročen mali grafikon.

1325
01:04:22,880 --> 01:04:26,850
Vem, da vas vse, pred tem kvizu 0,
bo v svoji sobi verjetno poskuša

1326
01:04:26,850 --> 01:04:27,960
da si zapomnimo, da je.

1327
01:04:27,960 --> 01:04:30,940
Tako da je lepo tam za vas.

1328
01:04:30,940 --> 01:04:37,120
Samo ne pozabite na logiko, ki made--
Zato te številke so bile, ki se pojavljajo.

1329
01:04:37,120 --> 01:04:39,870
Če ste vedno izgubili, samo da
prepričani, da veste, kaj vrste so.

1330
01:04:39,870 --> 01:04:40,820
In lahko teče skozi
jim v mislih

1331
01:04:40,820 --> 01:04:42,903
da ugotovimo, zakaj tisti,
odgovori so ti odgovori.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> V redu.

1334
01:04:47,600 --> 01:04:49,680
Torej bomo, da se premaknete
na končno na iskanje.

1335
01:04:49,680 --> 01:04:51,638
Saj, kot tiste, ki ste
ki ste prebrali pset,

1336
01:04:51,638 --> 01:04:55,175
Iskanje je tudi del
problem ta teden določa.

1337
01:04:55,175 --> 01:04:57,300
Boste morali izvajati
dve vrsti iskanj.

1338
01:04:57,300 --> 01:05:00,070
Ena je linearna iskanje in
eden je binarno iskanje.

1339
01:05:00,070 --> 01:05:01,760
>> Torej linearna iskanje je dokaj preprost.

1340
01:05:01,760 --> 01:05:04,070
Pravkar želite iskati element
seznama, da vidim, če ste jo dobili.

1341
01:05:04,070 --> 01:05:05,444
Moraš Ponovil skozi.

1342
01:05:05,444 --> 01:05:08,170
In če je to enako, nekaj,
si lahko samo vrniti, kajne?

1343
01:05:08,170 --> 01:05:10,890
Ampak tisti, ki smo najbolj
zanima govoriš

1344
01:05:10,890 --> 01:05:14,550
dvojiško iskanje, desno, ki je
razdeli in vladaj mehanizem, ki

1345
01:05:14,550 --> 01:05:18,190
David je dokazovanje v predavanju.

1346
01:05:18,190 --> 01:05:20,810
>> Spomnimo se primera telefonskega imenika
da ga še naprej vzgajajo,

1347
01:05:20,810 --> 01:05:23,960
tista, ki je nekako boril
malo o tem preteklem letu,

1348
01:05:23,960 --> 01:05:27,530
kjer si razdeliti problem na pol,
na pol, na pol, znova in znova,

1349
01:05:27,530 --> 01:05:30,730
dokler ne boste našli, kar iščete?

1350
01:05:30,730 --> 01:05:33,727
In imaš
runtime na to, kot dobro.

1351
01:05:33,727 --> 01:05:35,810
In lahko vidite, da je
bistveno bolj učinkovita

1352
01:05:35,810 --> 01:05:39,080
kot katero koli drugo vrsto iskanja.

1353
01:05:39,080 --> 01:05:41,880
>> Torej način, da bi šel okoli
izvajanje binarno iskanje

1354
01:05:41,880 --> 01:05:46,510
je, če bomo imeli niz,
indeks 0 do 6, sedem elementov,

1355
01:05:46,510 --> 01:05:49,790
smo lahko ogledate v sredini, right--
Žal mi je, če je naše vprašanje first--

1356
01:05:49,790 --> 01:05:53,840
če želimo vprašati vprašanje, ali
matrika vsebuje element 7,

1357
01:05:53,840 --> 01:05:56,840
Očitno je, da pri človeku, in ima
tako majhen matrika, je enostaven za nas

1358
01:05:56,840 --> 01:05:58,210
reči da.

1359
01:05:58,210 --> 01:06:05,750
Toda način, da se izvaja binarno
iskanje bi bilo pogledati v sredini.

1360
01:06:05,750 --> 01:06:08,020
>> Vemo, da je indeks 3
srednji, ker smo

1361
01:06:08,020 --> 01:06:09,270
vem, obstaja sedem elementov.

1362
01:06:09,270 --> 01:06:10,670
Kaj 7 deljeno z 2?

1363
01:06:10,670 --> 01:06:12,850
Lahko odsekati, da dodatno 1.

1364
01:06:12,850 --> 01:06:14,850
Imaš 3 v sredini.

1365
01:06:14,850 --> 01:06:17,590
Torej je niz 3 enaka 7?

1366
01:06:17,590 --> 01:06:18,900
To ni, kajne?

1367
01:06:18,900 --> 01:06:21,050
Ampak ne moremo storiti nekaj pregledov.

1368
01:06:21,050 --> 01:06:25,380
Je niz 3 manj kot 7 ali
je niz 3 večji kot 7?

1369
01:06:25,380 --> 01:06:27,240
>> In vemo, da je manj kot 7.

1370
01:06:27,240 --> 01:06:30,259
Torej vemo, da, oh, mora o tem
ne bi bila v levi polovici.

1371
01:06:30,259 --> 01:06:32,300
Vemo, da mora biti
V desni polovici, kajne?

1372
01:06:32,300 --> 01:06:34,662
Tako smo lahko samo odsekati pol array.

1373
01:06:34,662 --> 01:06:36,370
Nimamo niti za
poglej več.

1374
01:06:36,370 --> 01:06:38,711
Ker vemo, da
polovica našega problem--

1375
01:06:38,711 --> 01:06:41,210
vemo, da je odgovor na
desna polovica našega problema.

1376
01:06:41,210 --> 01:06:42,580
Tako smo samo poglej, da je zdaj.

1377
01:06:42,580 --> 01:06:44,860
>> Torej, zdaj gledamo na
sredina, kar je ostalo.

1378
01:06:44,860 --> 01:06:46,880
Ta indeks 5.

1379
01:06:46,880 --> 01:06:50,200
Smo spet naredil isto pregled
in vidimo, da je manjši.

1380
01:06:50,200 --> 01:06:52,050
Torej, gledamo na levi strani, ki.

1381
01:06:52,050 --> 01:06:53,430
In potem smo videli, da je ček.

1382
01:06:53,430 --> 01:06:57,600
Je vrednost niz na
indeks 4 enaka 7?

1383
01:06:57,600 --> 01:06:58,260
Je.

1384
01:06:58,260 --> 01:07:03,580
Tako bomo lahko vrnili res, ker
smo našli vrednost v našem seznamu.

1385
01:07:03,580 --> 01:07:06,738
Ali kako sem šel skozi
da je smiselno, da se vse?

1386
01:07:06,738 --> 01:07:08,760
V REDU.

1387
01:07:08,760 --> 01:07:11,670
Dam ti fantje morda, kot so,
tri, štiri minute, da ugotovimo,

1388
01:07:11,670 --> 01:07:13,270
kako psevdokoda to.

1389
01:07:13,270 --> 01:07:18,070
>> Torej, si predstavljajte, sem vas prosil, da napišete
Funkcija se imenuje iskanje (), ki se je vrnil

1390
01:07:18,070 --> 01:07:20,640
vrednost, logično vrednost,
da je res ali false-- podobno,

1391
01:07:20,640 --> 01:07:22,970
res, če ugotovi, da je
vrednost false, če nisi.

1392
01:07:22,970 --> 01:07:25,230
In potem ste bili
opravili na vrednost, ki jo

1393
01:07:25,230 --> 01:07:28,410
iskali v vrednosti, ki
je array-- oh, jaz definitivno dal

1394
01:07:28,410 --> 01:07:29,410
da je na napačnem mestu.

1395
01:07:29,410 --> 01:07:29,580
V REDU.

1396
01:07:29,580 --> 01:07:31,829
Kakorkoli že, da bi morali imeti
je na desni strani vrednot.

1397
01:07:31,829 --> 01:07:36,280
In nato int n število
elementov v tem polju.

1398
01:07:36,280 --> 01:07:39,430
Kako bi šel o poskusu
da psevdokoda ta problem v?

1399
01:07:39,430 --> 01:07:41,630
Dam ti fantje, kot so
tri minute, da to storim.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Ne, mislim, da je only--
Ja, tam je ena prav tukaj.

1402
01:08:02,595 --> 01:08:03,261
OBČINSTVO: Can I?

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Ja, imam te.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Je to deluje?

1406
01:08:11,050 --> 01:08:12,290
OK kul.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> V REDU.

1409
01:10:44,720 --> 01:10:47,630
V redu fantje, mi smo
tekoč, da ga nadzorovali.

1410
01:10:47,630 --> 01:10:49,730
V REDU.

1411
01:10:49,730 --> 01:10:54,020
Torej, predpostavimo, da smo dobili to lepo
malo matrika zn vrednot v njej.

1412
01:10:54,020 --> 01:10:55,170
Nisem pripravi proge.

1413
01:10:55,170 --> 01:10:58,649
Toda kako bi šel o
poskuša to napisati?

1414
01:10:58,649 --> 01:11:00,440
Ali kdo želi
daj mi prvo vrstico?

1415
01:11:00,440 --> 01:11:02,814
Če želite, da bi me
prva linija tega psevdokoda.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> OBČINSTVO: [neslišno]

1418
01:11:08,430 --> 01:11:10,138
OBČINSTVO: Bi želeli
Ponovil through--

1419
01:11:10,138 --> 01:11:11,094
OBČINSTVO: Just another za zanko?

1420
01:11:11,094 --> 01:11:11,760
OBČINSTVO: --for.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Torej, ta je malce zapleteno.

1423
01:11:17,780 --> 01:11:23,130
Pomislite about-- želite
da bo tekmovanje v teku to zanko

1424
01:11:23,130 --> 01:11:27,950
znova in znova do kdaj?

1425
01:11:27,950 --> 01:11:30,819
>> OBČINSTVO: Do [neslišno]
vrednost je enaka tej vrednosti.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Točno tako.

1427
01:11:31,610 --> 01:11:33,900
Torej lahko dejansko samo write--
bomo lahko celo poenostavi več.

1428
01:11:33,900 --> 01:11:35,630
Mi lahko samo narediti while zanko, kajne?

1429
01:11:35,630 --> 01:11:39,380
Tako da lahko samo še loop--
vemo, da je nekaj časa.

1430
01:11:39,380 --> 01:11:42,850
Ampak za zdaj, bom
reči "zanko" - skozi kaj?

1431
01:11:42,850 --> 01:11:46,640
Loop until-- kaj je
naša konča stanje?

1432
01:11:46,640 --> 01:11:47,510
Mislim, da sem ga slišal.

1433
01:11:47,510 --> 01:11:48,530
Sem slišal nekoga reči.

1434
01:11:48,530 --> 01:11:51,255
>> Publika: Vrednote enaka sredini.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: Ponovi.

1436
01:11:52,255 --> 01:11:54,470
OBČINSTVO: Ali, dokler
vrednost, ki jo iščete

1437
01:11:54,470 --> 01:11:58,470
Za je enaka srednji vrednosti.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Kaj pa, če je ni tam?

1439
01:12:00,280 --> 01:12:03,113
Kaj, če je vrednost, ki jo iščete
za dejansko ni v tem polju?

1440
01:12:03,113 --> 01:12:05,890
OBČINSTVO: Vrnete 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Ampak kaj hočemo
zanka, dokler če imamo stanje?

1442
01:12:08,850 --> 01:12:09,350
Ja.

1443
01:12:09,350 --> 01:12:11,239
>> OBČINSTVO: Dokler obstaja samo ena vrednost?

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: Lahko zanka
until-- tako da boste vedeli, da ste

1445
01:12:13,530 --> 01:12:15,714
dogaja, da imajo max vrednost, kajne?

1446
01:12:15,714 --> 01:12:18,130
In veš, da boš
imeti min vrednost, ne?

1447
01:12:18,130 --> 01:12:20,379
Ker je tudi, da je nekaj
Pozabil sem povedati prej,

1448
01:12:20,379 --> 01:12:22,640
da je nekaj, kar je
kritično o binarnem iskanju

1449
01:12:22,640 --> 01:12:24,182
je, da je vaš matrika že razporejene.

1450
01:12:24,182 --> 01:12:26,973
Ker ni način dela
to če oni samo naključne vrednosti.

1451
01:12:26,973 --> 01:12:29,190
Saj ne vem, če je
večji od drugega, kajne?

1452
01:12:29,190 --> 01:12:32,720
>> Tako da boste vedeli, da vaš max in
vaše min tukaj, kajne?

1453
01:12:32,720 --> 01:12:35,590
Če ste tekoč, da se prilagajanje
Vaše max v vaših minut in mid--

1454
01:12:35,590 --> 01:12:38,470
kaj je samo prevzeti vaš
mid vrednost je prav here--

1455
01:12:38,470 --> 01:12:43,910
boste v bistvu
zanka, dokler vam minimum

1456
01:12:43,910 --> 01:12:47,510
približno enako kot max, desno ali
če vaš max ni isto kot vaš min.

1457
01:12:47,510 --> 01:12:48,040
Prav?

1458
01:12:48,040 --> 01:12:51,340
Ker, ko se to zgodi, veste, da
da ste na koncu zadeli enako vrednost.

1459
01:12:51,340 --> 01:12:59,135
Torej hočeš, da zanke, dokler vam min
je manjša od ali enaka to-- oops,

1460
01:12:59,135 --> 01:13:01,510
ni manjša ali enaka
drugi način around-- max je.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Ali, da je smisel?

1463
01:13:16,160 --> 01:13:18,810
Vzel sem nekaj neuspešnih poizkusih, da bi dobili to pravico.

1464
01:13:18,810 --> 01:13:21,869
Ampak zanka do vašega max vrednosti
je v bistvu skoraj manj

1465
01:13:21,869 --> 01:13:23,410
od ali enaka vaši minimum, kajne?

1466
01:13:23,410 --> 01:13:25,201
To je, ko veš
ki ste jih približale.

1467
01:13:25,201 --> 01:13:29,290
OBČINSTVO: Ko bi vaša največja
vrednost manj kot minimum?

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Če se boste držali
ga prilagodi, kar

1469
01:13:31,040 --> 01:13:32,380
je tisto, kar se dogaja
da se delaš na tem.

1470
01:13:32,380 --> 01:13:33,460
Ali to smiselno?

1471
01:13:33,460 --> 01:13:35,750
Najmanjši in max so samo
cela števila, ki smo verjetno

1472
01:13:35,750 --> 01:13:39,260
dogaja, da želijo ustvariti obdržati
tir, kjer iščemo.

1473
01:13:39,260 --> 01:13:41,790
Ker je matrika obstaja
ne glede na to, kaj počnemo.

1474
01:13:41,790 --> 01:13:45,030
Kot, da smo dejansko ni fizično
sekanje off matriki, kajne?

1475
01:13:45,030 --> 01:13:47,261
Mi samo prilagajanje
kjer smo iskali.

1476
01:13:47,261 --> 01:13:48,136
Ali to smiselno?

1477
01:13:48,136 --> 01:13:48,472
>> OBČINSTVO: Ja.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Torej, če je to pogoj za našo zanke,
kaj želimo znotraj te zanke?

1480
01:13:57,090 --> 01:13:58,700
Kaj bomo se želijo storiti?

1481
01:13:58,700 --> 01:14:02,390
Torej sedaj, imamo
max in min, desno,

1482
01:14:02,390 --> 01:14:04,962
verjetno ustvaril tu nekje.

1483
01:14:04,962 --> 01:14:07,170
Bomo verjetno želeli
najti sredino, kajne?

1484
01:14:07,170 --> 01:14:08,450
Kako se bomo, da bo
mogli najti na sredini?

1485
01:14:08,450 --> 01:14:09,491
Kaj je mathematical--

1486
01:14:09,491 --> 01:14:11,079
OBČINSTVO: Max plus min deljeno z 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Točno tako.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Ali to smiselno?

1490
01:14:21,620 --> 01:14:25,780
In ne vi vidite, zakaj smo
ni samo use-- zakaj smo to storili

1491
01:14:25,780 --> 01:14:27,850
namesto da bi le n deliti z 2?

1492
01:14:27,850 --> 01:14:30,310
To je zato, ker n je vrednost
da se dogaja, da ostanejo enake.

1493
01:14:30,310 --> 01:14:30,979
Prav?

1494
01:14:30,979 --> 01:14:34,020
Toda, kot smo prilagodili našo minimalno in
Najvišje vrednosti, oni bodo spremenile.

1495
01:14:34,020 --> 01:14:36,040
In kot rezultat, naši srednji
se bo preveč spremenilo.

1496
01:14:36,040 --> 01:14:37,873
Torej, to je, zakaj hočemo
to storiti prav tukaj.

1497
01:14:37,873 --> 01:14:38,510
V REDU.

1498
01:14:38,510 --> 01:14:41,600
>> In potem, zdaj,
Ugotovili smo our-- ja.

1499
01:14:41,600 --> 01:14:44,270
>> OBČINSTVO: Samo hitro question--
ko rečeš min in max,

1500
01:14:44,270 --> 01:14:46,410
smo ob predpostavki, da
to je že urejeno?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Ja, to je pravzaprav
predpogoj za binarnega iskanja,

1502
01:14:48,400 --> 01:14:49,816
da moraš vedeti, da je urejeno.

1503
01:14:49,816 --> 01:14:53,660
Kateri je razlog, zakaj nekako, pišete v vašem
problem nastaviti pred vašim binarnega iskanja.

1504
01:14:53,660 --> 01:14:55,910
V REDU.

1505
01:14:55,910 --> 01:14:58,876
Torej sedaj, da vemo, kje je naša sredina
je, kaj želiš narediti tukaj?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> OBČINSTVO: želimo primerjati
da drugi.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Točno tako.

1509
01:15:05,110 --> 01:15:12,280
Torej boš za primerjavo
mid da vrednost, kajne?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
In kaj to povedati
nam, ko smo primerjali?

1512
01:15:18,670 --> 01:15:22,226
Kaj želimo storiti potem?

1513
01:15:22,226 --> 01:15:25,389
>> OBČINSTVO: Če je vrednost večja
od srede, želimo, da ga odreže.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Točno tako.

1515
01:15:26,180 --> 01:15:33,940
Torej, če je vrednost večja
od srede, smo

1516
01:15:33,940 --> 01:15:36,550
bodo želeli spremeniti te
minimum in maxes, kajne?

1517
01:15:36,550 --> 01:15:38,980
Kaj želimo spremeniti?

1518
01:15:38,980 --> 01:15:42,145
Torej, če vemo, da je vrednost je nekje
tukaj, kaj vas storimo, da spremeniti?

1519
01:15:42,145 --> 01:15:44,758
Želimo, da spremenimo svojo
Minimalna biti sredi, kajne?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
In potem pa, če je v tem
pol, kaj želimo spremeniti?

1522
01:15:54,292 --> 01:15:55,306
>> OBČINSTVO: Vaša največja.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Ja.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
In potem ste šele tekoč
obdržati zanka, kajne?

1526
01:16:04,680 --> 01:16:08,920
Ker sedaj, po eni ponovitvi
skozi, imaš max tukaj.

1527
01:16:08,920 --> 01:16:10,760
In potem lahko preračunate vmesni pregled.

1528
01:16:10,760 --> 01:16:11,990
In potem se lahko primerjajo.

1529
01:16:11,990 --> 01:16:14,766
In ti boš nadaljuj
še min in maxes

1530
01:16:14,766 --> 01:16:15,890
so v bistvu približale.

1531
01:16:15,890 --> 01:16:17,890
In to je, ko veš, da
da ste zadeli konec tega.

1532
01:16:17,890 --> 01:16:20,280
In, bodisi, da ste ga našli
ali niste na tej točki.

1533
01:16:20,280 --> 01:16:23,170
>> Ali je to smiselno, da vse?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
V REDU.

1536
01:16:26,770 --> 01:16:27,900
To je zelo pomembno,
ker boste imeli

1537
01:16:27,900 --> 01:16:29,760
to napisati v kodi nocoj.

1538
01:16:29,760 --> 01:16:32,660
Ampak vi imate zelo dober
občutek, kaj je treba narediti,

1539
01:16:32,660 --> 01:16:34,051
kar je dobro.

1540
01:16:34,051 --> 01:16:34,550
V REDU.

1541
01:16:34,550 --> 01:16:38,840
Torej imamo približno sedem
minut zapustil oddelek.

1542
01:16:38,840 --> 01:16:43,170
Torej bomo govorili o
to pset, da bomo počeli.

1543
01:16:43,170 --> 01:16:46,410
Torej je pset razdeljena na dve polovici.

1544
01:16:46,410 --> 01:16:50,230
Prva polovica vključuje
izvajanje najdbo

1545
01:16:50,230 --> 01:16:54,210
v katerem pišete linearno iskanje, A
binarno iskanje, in sortiranje algoritem.

1546
01:16:54,210 --> 01:16:56,690
>> Torej je to prva
Čas v pset kjer

1547
01:16:56,690 --> 01:17:00,050
bomo vam fantje, kar se imenuje
distribucija koda, ki je koda

1548
01:17:00,050 --> 01:17:02,740
da smo vnaprej napisan,
ampak samo pustil nekaj kosov off

1549
01:17:02,740 --> 01:17:04,635
za vas, da napišete.

1550
01:17:04,635 --> 01:17:07,510
Torej, fantje, ko si poglej tole
kodo, boste morda dobili res prestrašila.

1551
01:17:07,510 --> 01:17:08,630
Če ste šele všeč, Ahh, I
Ne vem, kaj to počne,

1552
01:17:08,630 --> 01:17:11,670
Ne vem, kot, da se zdi,
tako zapletena, ahh, se sprostite.

1553
01:17:11,670 --> 01:17:12,170
To je v redu.

1554
01:17:12,170 --> 01:17:12,930
Preberite spec.

1555
01:17:12,930 --> 01:17:16,920
Spec bo razložil, da vam točno
kaj vse te programe počnete.

1556
01:17:16,920 --> 01:17:20,560
>> Na primer, generate.c je program
da bo z vašo pset.

1557
01:17:20,560 --> 01:17:24,060
Ne boste dejansko morali dotakniti, vendar
morate razumeti, kaj počne.

1558
01:17:24,060 --> 01:17:28,550
In generate.c, vse to počne, je
bodisi generiranje naključnih števil

1559
01:17:28,550 --> 01:17:32,400
ali lahko daš to seme, tako kot
vnaprej dogovorjeno število, ki je potrebno,

1560
01:17:32,400 --> 01:17:34,140
in ustvarja več številk.

1561
01:17:34,140 --> 01:17:37,170
Torej obstaja poseben način
izvajanje generate.c v kateri

1562
01:17:37,170 --> 01:17:42,760
lahko samo, da kup številk
za vas, da preizkusite svoje druge metode, na.

1563
01:17:42,760 --> 01:17:45,900
>> Torej, če boste želeli, za
Na primer, preizkusite svojo najdbo,

1564
01:17:45,900 --> 01:17:48,970
bi si želeli teči generate.c,
ustvariti kup številk,

1565
01:17:48,970 --> 01:17:50,880
in nato zaženite vaš pomočniki funkcijo.

1566
01:17:50,880 --> 01:17:53,930
Vaš pomočniki funkcija je, če ste
dejansko fizično pisanje kode.

1567
01:17:53,930 --> 01:17:59,330
In pomislite pomočnikov kot datoteko s knjižnico
pišete, da je najdba kliče.

1568
01:17:59,330 --> 01:18:02,950
In tako znotraj helpers.c, boste
storiti iskanje in sortiranje.

1569
01:18:02,950 --> 01:18:06,500
>> In potem boš v bistvu
jih vse samo skupaj.

1570
01:18:06,500 --> 01:18:10,350
Spec vam bo povedal, kako
dal, da v ukazni vrstici.

1571
01:18:10,350 --> 01:18:14,880
In boste lahko preverili, ali
ni tvoja razvrščanje in iskanje delajo.

1572
01:18:14,880 --> 01:18:15,870
Cool.

1573
01:18:15,870 --> 01:18:18,720
Je kdo že začel in
ki so se pojavljale težave ali vprašanja

1574
01:18:18,720 --> 01:18:20,520
imajo zdaj s tem?

1575
01:18:20,520 --> 01:18:21,020
V REDU.

1576
01:18:21,020 --> 01:18:21,476
>> OBČINSTVO: Počakajte.

1577
01:18:21,476 --> 01:18:21,932
Imam vprašanje.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Ja.

1579
01:18:22,844 --> 01:18:28,390
>> OBČINSTVO: Zato sem začel delaš
linearna iskanje v helpers.c

1580
01:18:28,390 --> 01:18:29,670
in to ni bilo res deluje.

1581
01:18:29,670 --> 01:18:34,590
Ampak kasneje sem ugotovil, smo pravkar
morali izbrisati in narediti binarno iskanje.

1582
01:18:34,590 --> 01:18:36,991
Torej je to važno, če to ne deluje?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: Kratek odgovor je ne.

1585
01:18:41,510 --> 01:18:42,642
Ampak, ker smo not--

1586
01:18:42,642 --> 01:18:44,350
OBČINSTVO: Ampak nihče
dejansko preverjanje.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Smo nikoli
bomo videli, da.

1588
01:18:46,058 --> 01:18:49,590
Vendar pa boste verjetno želeli, da bi
Prepričajte vaše iskanje deluje.

1589
01:18:49,590 --> 01:18:51,700
Ker če je vaš linearno
iskanje ne deluje,

1590
01:18:51,700 --> 01:18:54,410
potem so možnosti, tvoj binarni
iskanje ne bo delovalo, kot dobro.

1591
01:18:54,410 --> 01:18:56,646
Ker imate podobne
logika v oba.

1592
01:18:56,646 --> 01:18:58,020
In ne, to ni važno.

1593
01:18:58,020 --> 01:19:01,300
Torej edine boste obrniti
v so nekakšna in binarno iskanje.

1594
01:19:01,300 --> 01:19:02,490
Ja.

1595
01:19:02,490 --> 01:19:06,610
>> In tako je bilo veliko otrok
poskušali zbrati helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Saj ne boš dejansko dovoljeno
za to, ker helpers.c

1597
01:19:09,550 --> 01:19:11,200
nima glavno funkcijo.

1598
01:19:11,200 --> 01:19:13,550
In tako bi smeli samo
bo dejansko sestavljanje

1599
01:19:13,550 --> 01:19:18,670
ustvarjajo in najti, ker najdejo klici
helpers.c in funkcije v njem.

1600
01:19:18,670 --> 01:19:20,790
Tako da omogoča razhroščevanje
bolečina v riti.

1601
01:19:20,790 --> 01:19:22,422
Ampak to je tisto, kar moramo storiti.

1602
01:19:22,422 --> 01:19:23,880
OBČINSTVO: Moraš narediti vse, kajne?

1603
01:19:23,880 --> 01:19:27,290
ANDI PENG: Lahko samo
narediti vse, kot tudi, ja.

1604
01:19:27,290 --> 01:19:28,060
V REDU.

1605
01:19:28,060 --> 01:19:32,570
Tako, da je to v smislu, kaj
pset se vas prosi vse narediti.

1606
01:19:32,570 --> 01:19:35,160
Če imate kakršnakoli vprašanja, vas
prosimo, da me po oddelku vprašati.

1607
01:19:35,160 --> 01:19:37,580
Jaz bom tu, kot, 20 minut.

1608
01:19:37,580 --> 01:19:40,500
>> In ja, so pset je
res, da ni slabo.

1609
01:19:40,500 --> 01:19:41,680
Vidva bi morala biti v redu.

1610
01:19:41,680 --> 01:19:43,250
To, sledite smernicam.

1611
01:19:43,250 --> 01:19:47,840
Nekako imajo občutek, logično, kaj
naj bi se dogajalo in boste v redu.

1612
01:19:47,840 --> 01:19:48,690
Ne bodite preveč strah.

1613
01:19:48,690 --> 01:19:50,220
Tam je veliko kode
tam že napisal.

1614
01:19:50,220 --> 01:19:53,011
Ne bodite preveč strah, če ne
razumeti, kaj vse to pomeni.

1615
01:19:53,011 --> 01:19:54,749
Če je veliko, to je povsem v redu.

1616
01:19:54,749 --> 01:19:55,790
In prišli do uradnih ur.

1617
01:19:55,790 --> 01:19:57,520
Pomagali vam bomo, da pogled.

1618
01:19:57,520 --> 01:20:00,810
>> OBČINSTVO: Z dodatno
funkcije, ne gledamo tiste gor?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Ja, to so v kodeksu.

1620
01:20:03,417 --> 01:20:05,750
V igri 15, pol leta
to je že napisal za vas.

1621
01:20:05,750 --> 01:20:09,310
Torej te funkcije so
že v kodeksu.

1622
01:20:09,310 --> 01:20:12,020
Ja.

1623
01:20:12,020 --> 01:20:12,520
V redu.

1624
01:20:12,520 --> 01:20:14,000
No, veliko sreče.

1625
01:20:14,000 --> 01:20:15,180
To je ogabno dan.

1626
01:20:15,180 --> 01:20:19,370
Torej, upam, da vama ne počutim preveč
slabega o bivanju v notranjosti in kodiranja.

1627
01:20:19,370 --> 01:20:22,133