1
00:00:00,000 --> 00:00:03,332
>> [MUSIC JOC]

2
00:00:03,332 --> 00:00:06,490
>> ANDI Peng: Bine ati venit la săptămâna 3 din secțiunea.

3
00:00:06,490 --> 00:00:09,550
Multumesc, voi, pentru toate provenind
la acest timp de pornire mai devreme astăzi.

4
00:00:09,550 --> 00:00:11,466
Avem un frumos, mic
grup intim astăzi.

5
00:00:11,466 --> 00:00:14,570
Deci sperăm că vom ajunge la
finisaj, probabil, mai devreme,

6
00:00:14,570 --> 00:00:15,780
un pic mai devreme astăzi.

7
00:00:15,780 --> 00:00:22,057
Atât de repede, doar câteva
anunțuri de pe ordinea de zi de astăzi.

8
00:00:22,057 --> 00:00:23,890
Înainte de a începe, suntem
de gând să merg peste

9
00:00:23,890 --> 00:00:28,910
unele probleme logistice scurte, PSET
întrebări, interogatoriu, lucruri de genul asta.

10
00:00:28,910 --> 00:00:30,250
Și apoi ne vom arunca cu capul chiar în.

11
00:00:30,250 --> 00:00:34,710
Vom folosi un program de depanare numit GDB la
începe debunking codul nostru, care David

12
00:00:34,710 --> 00:00:36,550
a explicat în curs de altă zi.

13
00:00:36,550 --> 00:00:39,420
Vom trece peste cele patru tipuri de soiuri.

14
00:00:39,420 --> 00:00:42,310
Vom merge peste ele destul de repede
deoarece acestea sunt destul de intens.

15
00:00:42,310 --> 00:00:45,710
Dar să știi că toate diapozitivele și
codul sursă sunt întotdeauna on-line.

16
00:00:45,710 --> 00:00:50,810
Deci nu ezitați, la examinare atentă dumneavoastră, pentru a
du-te înapoi și să ia o privire la asta.

17
00:00:50,810 --> 00:00:53,930
>> Vom merge prin
notație asimptotică, care

18
00:00:53,930 --> 00:00:55,944
este doar un mod de lux
de a spune "runtime"

19
00:00:55,944 --> 00:00:58,360
unde avem O mare, care
David a explicat în curs.

20
00:00:58,360 --> 00:01:01,550
Si ne-am, de asemenea, Omega, care
este runtime legat de jos.

21
00:01:01,550 --> 00:01:06,450
Și vom vorbi un pic mai mult
în profunzime cu privire la modul în care aceste lucru.

22
00:01:06,450 --> 00:01:10,160
Și, în fine, vom trece peste căutare binară,
pentru că o mulțime dintre voi care au deja

23
00:01:10,160 --> 00:01:15,190
se uită la psets dumneavoastră probabil știți că
că este o întrebare care se află într-PSET ta.

24
00:01:15,190 --> 00:01:17,470
Deci vei toții fericiți
pe care le acoperă acest lucru astăzi.

25
00:01:17,470 --> 00:01:20,610
>> Și, în fine, pe dumneavoastră
feedback-ul secțiune, de fapt am

26
00:01:20,610 --> 00:01:23,000
matureze circa 15 minute la
la sfârșitul pentru a merge doar pe

27
00:01:23,000 --> 00:01:27,730
logistica pset3, orice întrebări,
poate un pic de orientare, dacă vreți,

28
00:01:27,730 --> 00:01:28,990
înainte de a începe programarea.

29
00:01:28,990 --> 00:01:30,890
Deci, haideți să încercați să obțineți prin
materialul destul de repede.

30
00:01:30,890 --> 00:01:33,880
Și apoi putem petrece ceva timp
luând mai multe întrebări pentru PSET.

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

32
00:01:35,230 --> 00:01:39,570
>> Rapid, astfel încât doar câteva
anunțuri înainte de a începe astăzi.

33
00:01:39,570 --> 00:01:45,410
În primul rând, bun venit pentru a face
se prin intermediul a două dintre psets tale.

34
00:01:45,410 --> 00:01:49,432
Mi-am luat o privire la your-- Da, să
obține o rundă de aplauze pentru că unul.

35
00:01:49,432 --> 00:01:51,140
De fapt, am fost într-adevăr,
într-adevăr impresionat.

36
00:01:51,140 --> 00:01:55,800
Am clasificate prima PSET pentru voi
săptămână și voi ultimele facut incredibil.

37
00:01:55,800 --> 00:01:58,290
>> Stil a fost pe punctul de
în afară de câteva comentarii.

38
00:01:58,290 --> 00:02:00,660
Asigurați-vă că sunteți întotdeauna
comentând codul.

39
00:02:00,660 --> 00:02:03,040
Dar psets tale au fost pe punctul de.

40
00:02:03,040 --> 00:02:05,549
Și păstrați-l în sus.

41
00:02:05,549 --> 00:02:08,090
Și e bine pentru elev de clasa a
vedea că voi sunt punerea

42
00:02:08,090 --> 00:02:10,704
în măsura în efortul in stilul tau
și design-ul în codul

43
00:02:10,704 --> 00:02:12,120
care ne-ar dori pentru tine pentru a vedea.

44
00:02:12,120 --> 00:02:16,450
Deci, eu sunt de-a lungul mod de recunoștința mea
pentru restul AT.

45
00:02:16,450 --> 00:02:19,210
>> Cu toate acestea, există o
câteva întrebări interogatoriu

46
00:02:19,210 --> 00:02:22,010
Vreau doar să merg peste care
ar face atât viața mea

47
00:02:22,010 --> 00:02:24,900
și o mulțime de altă parte
AT "trăiește un pic mai ușor.

48
00:02:24,900 --> 00:02:28,220
În primul rând, am observat acest lucru
trecut week-- Câți dintre voi

49
00:02:28,220 --> 00:02:32,301
au fost difuzate pe check50
codul înainte de a vă prezenta?

50
00:02:32,301 --> 00:02:32,800
BINE.

51
00:02:32,800 --> 00:02:36,690
Deci, toată lumea ar trebui să facă check50,
because-- un secret-- am de fapt

52
00:02:36,690 --> 00:02:41,540
rula check50 ca parte a corectitudinii noastre
script-uri de testare codul.

53
00:02:41,540 --> 00:02:45,480
Deci, dacă codul este lipsa
check50, după toate probabilitățile,

54
00:02:45,480 --> 00:02:47,570
este, probabil, va
nu verificare nostru.

55
00:02:47,570 --> 00:02:49,320
Uneori voi
au răspunsurile corecte.

56
00:02:49,320 --> 00:02:52,200
Cum ar fi, în lacomi, unele dintre
aveți numerele corecte,

57
00:02:52,200 --> 00:02:53,960
doar imprima unele chestii in plus.

58
00:02:53,960 --> 00:02:55,940
Și că lucrurile în plus
nu, de fapt, verificarea,

59
00:02:55,940 --> 00:02:58,440
deoarece computerul nu
știu cu adevărat ce este în căutarea pentru.

60
00:02:58,440 --> 00:03:00,981
Și așa va rula doar prin,
vedea că ieșire nu

61
00:03:00,981 --> 00:03:03,810
potrivi ceea ce ne așteptăm răspunsul
să fie, și marcați este greșit.

62
00:03:03,810 --> 00:03:06,560
>> Și știu ce sa întâmplat în
o parte din cazurile tale în această săptămână.

63
00:03:06,560 --> 00:03:09,870
Deci, m-am întors și manual
declasificat cod tuturor.

64
00:03:09,870 --> 00:03:12,780
În viitor însă,
Vă rog, vă rugăm să asigurați-vă că

65
00:03:12,780 --> 00:03:14,570
pe care îl execută
verifica 50 pe codul.

66
00:03:14,570 --> 00:03:17,970
Pentru că este un fel de durere pentru AT
de a avea pentru a merge înapoi și manual declasificare

67
00:03:17,970 --> 00:03:21,197
fiecare PSET unic pentru fiecare
singur, exemplu puțin ratat.

68
00:03:21,197 --> 00:03:22,530
Așa că nu a luat de pe orice puncte.

69
00:03:22,530 --> 00:03:25,210
Cred că mi-am scos poate
una sau două pentru proiectare.

70
00:03:25,210 --> 00:03:27,710
În viitor, deși, în cazul în care
te în lipsa check50,

71
00:03:27,710 --> 00:03:31,330
puncte vor fi luate
off pentru corectitudinea.

72
00:03:31,330 --> 00:03:35,020
>> Mai mult, sunt psets
datorită vineri la prânz.

73
00:03:35,020 --> 00:03:38,990
Cred că e un șapte de minute
perioadă de grație târziu că vă oferim.

74
00:03:38,990 --> 00:03:42,434
Pe timp Harvard, au voie să
șapte minute întârziere la tot.

75
00:03:42,434 --> 00:03:44,350
Deci, aici, la Yale, vom
să adere la fel de bine.

76
00:03:44,350 --> 00:03:47,910
Dar destul de mult, la 12:07,
dacă PSET nu este în,

77
00:03:47,910 --> 00:03:49,720
se va fi marcat ca târziu.

78
00:03:49,720 --> 00:03:53,160
Și astfel în timp ce acesta este marcat
ca târziu, TA-- sunt

79
00:03:53,160 --> 00:03:54,870
încă de gând să fie clasificare psets tale.

80
00:03:54,870 --> 00:03:56,760
Astfel încât veți vedea în continuare apare un grad.

81
00:03:56,760 --> 00:03:58,820
Cu toate acestea, știu că la
la sfârșitul semestrului,

82
00:03:58,820 --> 00:04:02,270
toate psets întârziere va fi doar
zero automat de către calculator.

83
00:04:02,270 --> 00:04:04,490
>> Facem acest lucru din două motive.

84
00:04:04,490 --> 00:04:09,220
Unul, uneori ajungem
scuzat, ca scuze lui Dean,

85
00:04:09,220 --> 00:04:10,762
mai târziu că nu știu despre încă.

86
00:04:10,762 --> 00:04:13,761
Deci, ne place să ne asigurăm că te notare
totul doar în cazul în, cum ar fi, eu sunt

87
00:04:13,761 --> 00:04:15,080
lipsește scuza un Dean.

88
00:04:15,080 --> 00:04:17,000
În al doilea rând, să păstreze în
minte, puteți încă

89
00:04:17,000 --> 00:04:19,370
picătură o PSET care
Domeniul de aplicare are puncte complete.

90
00:04:19,370 --> 00:04:21,430
Și așa ne place să grad
toate psets tale doar

91
00:04:21,430 --> 00:04:24,730
pentru a vă asigura că domeniul de aplicare dvs. de
acolo și tu le încearcă.

92
00:04:24,730 --> 00:04:29,150
Deci, chiar dacă e târziu, veți încă
obține credit pentru puncte domeniul de aplicare, cred.

93
00:04:29,150 --> 00:04:33,730
>> Deci, morală a poveștii este, face
sigur psets dumneavoastră sunt în la timp.

94
00:04:33,730 --> 00:04:38,350
Iar dacă acestea nu sunt de pe-timp,
Știu că nu e mare.

95
00:04:38,350 --> 00:04:41,678
Da, înainte de a mă muta mai departe, nimeni nu avea
orice întrebări cu privire la feedback-ul PSET?

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

97
00:04:42,178 --> 00:04:43,630
>> Audiența: Ai spus noi
poate sa scada unul dintre psets?

98
00:04:43,630 --> 00:04:44,296
>> ANDI Peng: Da.

99
00:04:44,296 --> 00:04:47,050
Deci nu e nouă psets generală
pe parcursul semestrului.

100
00:04:47,050 --> 00:04:50,610
Și, dacă aveți domeniul de aplicare
points-- astfel domeniul de aplicare este doar,

101
00:04:50,610 --> 00:04:53,567
destul de mult, te a încerca
problemă, te punerea în timp,

102
00:04:53,567 --> 00:04:56,150
sunt vă arată care le-ați
a demonstrat ce ați citit spec.

103
00:04:56,150 --> 00:04:57,191
Asta e destul de mult domeniul de aplicare.

104
00:04:57,191 --> 00:04:59,370
Și dacă se îndeplinesc
Domeniul de aplicare de puncte, am

105
00:04:59,370 --> 00:05:03,360
poate scădea cel mai mic
unul afara domeniului de aplicare completă.

106
00:05:03,360 --> 00:05:06,790
Deci, care este în avantajul dumneavoastră să
completeze și să încerce fiecare PSET.

107
00:05:06,790 --> 00:05:10,320
>> Chiar dacă nici unul dintre upload--
le de lucru, le încărcați.

108
00:05:10,320 --> 00:05:13,711
Și apoi vom fi în măsură să sperăm
vă dau unele dintre aceste puncte înapoi.

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

110
00:05:14,210 --> 00:05:16,780
Orice alte întrebări?

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

112
00:05:17,840 --> 00:05:21,960
>> În al doilea rând, birou hours-- câteva
note rapide despre ore de birou.

113
00:05:21,960 --> 00:05:24,300
Deci în primul rând, veni mai devreme în săptămâna.

114
00:05:24,300 --> 00:05:26,909
Nimeni nu este niciodată la
orelor de program în zilele de luni.

115
00:05:26,909 --> 00:05:28,700
Christabel a venit la
orelor de noapte.

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

117
00:05:29,691 --> 00:05:32,190
Și ce-avem la birou
ore noaptea trecută, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> Audiența: Am avut inghetata.

119
00:05:33,020 --> 00:05:36,160
>> ANDI Peng: Deci ce-i drept, am avut
inghetata la ore de birou aseară.

120
00:05:36,160 --> 00:05:39,390
În timp ce eu nu-ți pot promite că
vom avea înghețată la ore de birou

121
00:05:39,390 --> 00:05:43,230
în fiecare săptămână, ceea ce pot să vă promit
este că va exista o semnificativ

122
00:05:43,230 --> 00:05:45,380
mai bine elev raport TA.

123
00:05:45,380 --> 00:05:47,650
Ca și legal, e ca și cum trei-un.

124
00:05:47,650 --> 00:05:50,350
Întrucât, contrast care cu
Joi, ai aproximativ 150

125
00:05:50,350 --> 00:05:52,830
într-adevăr a subliniat copii și nu înghețată.

126
00:05:52,830 --> 00:05:55,360
Și nu este vorba doar productiv pentru oricine.

127
00:05:55,360 --> 00:05:58,730
Deci, morală a poveștii este, veni mai devreme
la ore de birou și lucruri bune

128
00:05:58,730 --> 00:06:00,310
se va întâmpla.

129
00:06:00,310 --> 00:06:02,110
>> De asemenea, vin pregătiți să pună întrebări.

130
00:06:02,110 --> 00:06:03,200
Tu stii?

131
00:06:03,200 --> 00:06:05,420
Indiferent de ceea ce TAs, am
cred, au spus,

132
00:06:05,420 --> 00:06:10,710
am fost obtinerea de câteva studenți
care vin în, joi, la, cum ar fi, 10:50

133
00:06:10,710 --> 00:06:15,100
nu au citit spec
fiind ca ajută-mă, ajută-mă.

134
00:06:15,100 --> 00:06:18,200
Din păcate, în acel moment, nu există
nu de mult putem face pentru a vă ajuta.

135
00:06:18,200 --> 00:06:19,590
Deci, vă rugăm veni mai devreme în săptămâna.

136
00:06:19,590 --> 00:06:22,040
Vino devreme pentru a orelor de program.

137
00:06:22,040 --> 00:06:23,350
Vino pregătit să pună întrebări.

138
00:06:23,350 --> 00:06:25,310
Asigurați-vă că, în calitate de
un student, în cazul în care sunt

139
00:06:25,310 --> 00:06:27,620
aveți nevoie pentru a fi, astfel încât
AT vă poate ghida de-a lungul,

140
00:06:27,620 --> 00:06:32,850
care este ceea ce orelor de program
Ar trebui să fie alocat pentru.

141
00:06:32,850 --> 00:06:37,380
>> În al doilea rând, așa că știu profesori
Vrei să ne surprindă cu teste.

142
00:06:37,380 --> 00:06:39,439
Am avut un profesor cei
cum ar fi, yo, de altfel,

143
00:06:39,439 --> 00:06:41,230
amintiți-vă că intermediară
ai lunea viitoare.

144
00:06:41,230 --> 00:06:42,855
Da, nu am știut despre asta la mijlocul perioadei.

145
00:06:42,855 --> 00:06:45,630
Deci, am de gând să fie că TA
care vă reamintește că testul tot

146
00:06:45,630 --> 00:06:47,270
0-- că, știi, suntem CS.

147
00:06:47,270 --> 00:06:50,730
Acum, că ne-am matrice Done, veți obține
de ce e test 0, nu quiz 1, nu-i așa?

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

149
00:06:51,320 --> 00:06:52,490
Oh, am niște chicotește pe asta.

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

151
00:06:53,120 --> 00:06:59,710
>> Deci test 0 va fi de 14 octombrie în cazul în
vă aflați în secțiunea luni-miercuri

152
00:06:59,710 --> 00:07:02,920
și 15 octombrie, dacă sunteți în
secțiunea marți-joi.

153
00:07:02,920 --> 00:07:05,630
Acest lucru nu se aplică pentru
cei dintre voi la Harvard

154
00:07:05,630 --> 00:07:10,350
who-- Cred că vei fi tot
luarea de ajutorul testelor dvs. 14.

155
00:07:10,350 --> 00:07:13,560
>> Deci da, săptămâna viitoare, în cazul în care
David, în curs, se,

156
00:07:13,560 --> 00:07:15,747
Da, așa încât despre
test saptamana viitoare, voi toți

157
00:07:15,747 --> 00:07:17,580
nu va fi șocat, deoarece
ai venit la sectiunea

158
00:07:17,580 --> 00:07:19,664
și știți că dumneavoastră
test 0 este în două săptămâni.

159
00:07:19,664 --> 00:07:21,580
Și vom avea recenzie
sesiuni și totul.

160
00:07:21,580 --> 00:07:26,360
Deci, nu vă faceți griji despre
fiind speriat pentru asta.

161
00:07:26,360 --> 00:07:29,890
Orice întrebări before-- orice întrebări
la toate problemele logistice în ceea ce privește,

162
00:07:29,890 --> 00:07:32,591
clasificare, ore de birou, secțiuni?

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

164
00:07:33,090 --> 00:07:35,100
>> Audiența: Deci testul este
Va fi timpul prelegere?

165
00:07:35,100 --> 00:07:35,766
>> ANDI Peng: Da.

166
00:07:35,766 --> 00:07:39,460
Deci testul, cred eu, este de 60
minute alocate în acest interval de timp

167
00:07:39,460 --> 00:07:42,240
pe care le va lua doar
în sala de curs.

168
00:07:42,240 --> 00:07:44,810
Astfel încât să nu trebuie să vină în
pe, cum ar fi, o întâmplare 07:00.

169
00:07:44,810 --> 00:07:46,140
Totul este bine.

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

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

172
00:07:50,060 --> 00:07:50,840
>> In regula.

173
00:07:50,840 --> 00:07:54,330
Așa că am de gând să
introduce un concept pentru tine

174
00:07:54,330 --> 00:08:00,760
în această săptămână că David are deja un fel
de atins în curs în această săptămână trecut.

175
00:08:00,760 --> 00:08:02,010
Se numește GDB.

176
00:08:02,010 --> 00:08:05,570
Și câți dintre voi, în timp ce în
cursul de scriere psets tale,

177
00:08:05,570 --> 00:08:09,981
au observat un buton pe care scrie mare
"Debug" pe partea de sus a IDE-ul?

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

179
00:08:10,480 --> 00:08:13,770
Deci, acum vom obține de fapt, pentru a descoperi
misterul a ceea ce buton care de fapt

180
00:08:13,770 --> 00:08:14,270
face.

181
00:08:14,270 --> 00:08:16,790
Și vă garantez, este un
frumos, lucru frumos.

182
00:08:16,790 --> 00:08:20,740
>> Deci, până acum, cred că
acolo a fost două lucruri

183
00:08:20,740 --> 00:08:23,320
elevii au fost de obicei
face atunci când depanare psets.

184
00:08:23,320 --> 00:08:27,635
Unul, acestea se adaugă fie în
printf () - astfel încât la fiecare câteva rânduri,

185
00:08:27,635 --> 00:08:29,760
acestea se adaugă într-o printf () -
Oh, ce este această variabilă?

186
00:08:29,760 --> 00:08:32,551
Oh, ce este această variabilă now--
și un fel de a vedea evoluția

187
00:08:32,551 --> 00:08:33,940
de codul ca ruleaza.

188
00:08:33,940 --> 00:08:37,030
Sau a doua metodă de copii face este
că ei scriu doar totul

189
00:08:37,030 --> 00:08:38,610
și apoi du-te ca acest lucru la sfârșitul anului.

190
00:08:38,610 --> 00:08:39,970
Să sperăm că funcționează.

191
00:08:39,970 --> 00:08:44,851
Îți garantez, GDB este mai bine
decât aceste două metode.

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

193
00:08:45,350 --> 00:08:46,980
Deci, acest lucru va fi noul tău cel mai bun prieten.

194
00:08:46,980 --> 00:08:51,780
Pentru că e un lucru frumos
care afișează atât vizual

195
00:08:51,780 --> 00:08:54,850
ceea ce codul este de a face
la un anumit punct

196
00:08:54,850 --> 00:08:57,486
precum și ceea ce toate dvs.
variabile sunt transportă,

197
00:08:57,486 --> 00:08:59,610
ca ceea ce valorile lor sunt,
în acel moment specific.

198
00:08:59,610 --> 00:09:02,670
Și în acest fel, puteți într-adevăr
seta puncte de întrerupere din cod.

199
00:09:02,670 --> 00:09:04,350
Puteți rula prin linie cu linie.

200
00:09:04,350 --> 00:09:07,324
Și GDB va avea doar pentru
te, afișate pentru tine,

201
00:09:07,324 --> 00:09:09,490
ce toate variabilele
sunt, ceea ce fac ei,

202
00:09:09,490 --> 00:09:10,656
ce se întâmplă în codul.

203
00:09:10,656 --> 00:09:13,240
Și în așa fel, e
atât de mult mai ușor pentru a vedea

204
00:09:13,240 --> 00:09:17,120
ceea ce se întâmplă în loc de printf-ing
sau scriind declarațiile dumneavoastră.

205
00:09:17,120 --> 00:09:19,160
>> Deci, vom face un exemplu de acest lucru mai târziu.

206
00:09:19,160 --> 00:09:20,660
Deci, acest lucru pare un pic abstract.

207
00:09:20,660 --> 00:09:23,490
Nu vă faceți griji, vom face exemple.

208
00:09:23,490 --> 00:09:29,170
Și astfel, în esență, cele mai mari trei,
cel mai folosit funcțiile veți avea nevoie în GDB

209
00:09:29,170 --> 00:09:32,500
sunt următorii, Step peste,
și Pășește în butoane.

210
00:09:32,500 --> 00:09:34,860
Am de gând să peste cap de
acolo, de fapt, chiar acum.

211
00:09:34,860 --> 00:09:40,930
>> Deci poate voi vedea că tot
sau ar trebui să mări un pic?

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

213
00:09:43,220 --> 00:09:44,470
În partea din spate, puteți vedea că?

214
00:09:44,470 --> 00:09:45,730
Ar trebui să zoom in?

215
00:09:45,730 --> 00:09:46,480
Doar puțin?

216
00:09:46,480 --> 00:09:49,390
Bine, in regula.

217
00:09:49,390 --> 00:09:50,280
Nu mergem.

218
00:09:50,280 --> 00:09:50,960
BINE.

219
00:09:50,960 --> 00:09:57,000
>> Așa că am, aici, mi
punere în aplicare pentru lacomi.

220
00:09:57,000 --> 00:10:01,430
Și în timp ce o mulțime de voi scris
lacomi în buclă în timp ce form-- care

221
00:10:01,430 --> 00:10:04,890
este un mod perfect acceptabil de a face
it-- un alt mod de a face este de a pur și simplu

222
00:10:04,890 --> 00:10:06,280
împărți în modulo.

223
00:10:06,280 --> 00:10:09,290
Pentru că atunci puteți avea dvs.
valoare și apoi au restul dumneavoastră.

224
00:10:09,290 --> 00:10:11,150
Și apoi puteți doar
adăugați-l toate împreună.

225
00:10:11,150 --> 00:10:13,390
Are logica a ceea ce fac
aici sens pentru toată lumea,

226
00:10:13,390 --> 00:10:14,117
înainte de a începe?

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

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

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

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

231
00:10:19,210 --> 00:10:21,290
E o piesă destul de sexy
de cod, aș spune.

232
00:10:21,290 --> 00:10:23,502
Cum am spus, David, în
prelegeri, după un timp,

233
00:10:23,502 --> 00:10:25,960
veți începe să vadă toate cod
ca ceva care este frumos.

234
00:10:25,960 --> 00:10:29,950
Și, uneori, când veți vedea frumos
cod, este un astfel de sentiment minunat.

235
00:10:29,950 --> 00:10:35,410
>> Deci toate acestea, în timp ce acest cod este foarte
frumos, nu funcționează în mod corespunzător.

236
00:10:35,410 --> 00:10:37,750
Deci, haideți să ruleze check50 în acest sens.

237
00:10:37,750 --> 00:10:39,440
Verificați 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
Este că pset2?

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

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

245
00:10:52,890 --> 00:10:53,900
Deci, vom rula check50.

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

247
00:11:01,550 --> 00:11:07,170
>> Și, după cum voi puteti vedea aici,
este lipsa de câteva cazuri.

248
00:11:07,170 --> 00:11:10,165
Și pentru unii dintre voi, în
curs de a face seturi de probleme,

249
00:11:10,165 --> 00:11:11,110
esti ca, ah, de ce nu-i așa de lucru.

250
00:11:11,110 --> 00:11:13,318
De ce este de lucru pentru a putea
Valorile dar nu pentru alții?

251
00:11:13,318 --> 00:11:17,760
Ei bine, GDB este de gând să vă ajuta să figura
de ce aceste intrări nu au fost de lucru.

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

253
00:11:18,320 --> 00:11:21,640
Să vedem, una dintre cele mai
verificări am fost lipsa în check50

254
00:11:21,640 --> 00:11:24,920
a fost valoarea de intrare a 0.41.

255
00:11:24,920 --> 00:11:27,830
Deci răspunsul corect pe care
ar trebui să fie obținerea este 4.

256
00:11:27,830 --> 00:11:33,090
Dar, în loc ceea ce am imprimarea
este 3-N, care este incorect.

257
00:11:33,090 --> 00:11:36,190
Deci, hai să executați acest manual, doar
asigurați-vă că check50 funcționează.

258
00:11:36,190 --> 00:11:36,940
Să facem ./greedy.

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

260
00:11:40,130 --> 00:11:43,340
Oops, am avea de a face lacomi.

261
00:11:43,340 --> 00:11:43,840
Nu mergem.

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

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

264
00:11:46,950 --> 00:11:47,670
>> Cât de mult se datorează?

265
00:11:47,670 --> 00:11:49,550
Să facem 0.41.

266
00:11:49,550 --> 00:11:52,590
Si da, vom vedea aici
că este scoate 3

267
00:11:52,590 --> 00:11:55,160
în cazul în care răspunsul corect,
De fapt, ar trebui să fie de 4.

268
00:11:55,160 --> 00:12:01,460
Așa că haideți să introduceți GDB și a vedea cum putem
poate merge despre fixarea această problemă.

269
00:12:01,460 --> 00:12:03,992
>> Deci, primul pas în
depanarea întotdeauna codul

270
00:12:03,992 --> 00:12:05,950
este de a stabili un punct de întrerupere,
sau un punct de la care

271
00:12:05,950 --> 00:12:09,079
Vrei computerul sau
debugger pentru a începe căutarea de la.

272
00:12:09,079 --> 00:12:11,120
Deci, dacă nu prea
stiu care e problema ta,

273
00:12:11,120 --> 00:12:14,670
de obicei, lucru tipic vrem să
face este de a stabili breakpoint nostru la principal.

274
00:12:14,670 --> 00:12:18,520
Deci, dacă voi puteți vedea aceasta
butonul roșu acolo,

275
00:12:18,520 --> 00:12:22,860
Da, că mi-a fost stabilirea unui
limită privind funcția principală.

276
00:12:22,860 --> 00:12:24,130
Am faceți clic pe asta.

277
00:12:24,130 --> 00:12:26,130
>> Și apoi pot merge până la butonul meu de depanare.

278
00:12:26,130 --> 00:12:27,036
Am lovit acel buton.

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

280
00:12:31,710 --> 00:12:36,555
Lasă-mă să zoom înapoi dacă pot.

281
00:12:36,555 --> 00:12:38,020
Nu mergem.

282
00:12:38,020 --> 00:12:40,730
Deci avem, aici, un panou pe dreapta.

283
00:12:40,730 --> 00:12:43,680
Îmi pare rău, băieți în spate, ai
nu se poate vedea cu adevărat foarte bine.

284
00:12:43,680 --> 00:12:49,090
Dar, în esență, toate
acest panou drept este de a face

285
00:12:49,090 --> 00:12:53,130
este urmărirea atât a evidențiat
linie, care este o linie de cod

286
00:12:53,130 --> 00:12:56,640
care computerul este în curs de desfășurare,
precum și toate variabilele

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

288
00:12:57,600 --> 00:13:00,487
>> Deci ai de cenți, monede, n,
toate declarat lucruri diferite

289
00:13:00,487 --> 00:13:01,070
in acest punct.

290
00:13:01,070 --> 00:13:04,850
Nu vă faceți griji, pentru că avem de fapt, nu
le inițializat la orice variabile încă.

291
00:13:04,850 --> 00:13:07,200
Deci, în calculatorul dumneavoastră, dumneavoastră
Computer doar văd,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 a fost ultima funcție second-hand
de care spațiu de memorie în computerul meu.

293
00:13:14,376 --> 00:13:16,000
Și așa că e în cazul în care în prezent este de cenți.

294
00:13:16,000 --> 00:13:19,360
Dar nu că odată ce rula codul,
aceasta ar trebui să devină inițializată.

295
00:13:19,360 --> 00:13:24,110
>> Așa că haideți să treacă prin, linia de
line, ce se întâmplă aici.

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

297
00:13:25,350 --> 00:13:29,400
Deci, aici sunt cele trei
butoane care tocmai am explicat.

298
00:13:29,400 --> 00:13:34,090
Aveți Play, sau funcția Run,
buton, aveți pas peste buton,

299
00:13:34,090 --> 00:13:36,600
și aveți, de asemenea, pas în butonul.

300
00:13:36,600 --> 00:13:41,260
Și, în esență, toate cele trei
le du-te prin codul

301
00:13:41,260 --> 00:13:42,690
și de a face lucruri diferite.

302
00:13:42,690 --> 00:13:45,680
>> Deci de obicei, atunci când sunteți depanare,
noi nu vrem să lovi juca doar,

303
00:13:45,680 --> 00:13:47,930
pentru că va rula doar Joaca
codul de la sfârșitul anului acesta.

304
00:13:47,930 --> 00:13:49,070
Și atunci nu va fi de fapt
Știi care e problema ta

305
00:13:49,070 --> 00:13:51,432
este dacă nu ați stabilit mai multe puncte de întrerupere.

306
00:13:51,432 --> 00:13:53,890
Dacă setați mai multe puncte de întrerupere,
se va doar în mod automat

307
00:13:53,890 --> 00:13:56,030
a alerga de la un punct de întrerupere,
la alta, la următorul.

308
00:13:56,030 --> 00:13:58,030
Dar în acest caz ne-am
doar că unul, pentru că am

309
00:13:58,030 --> 00:13:59,970
doresc să lucreze drumul nostru
de sus în jos în jos.

310
00:13:59,970 --> 00:14:04,830
Așa că am de gând să ignore acel buton
acum în scopul acestui program.

311
00:14:04,830 --> 00:14:08,230
>> Deci, pas peste funcție doar
pași peste fiecare linie

312
00:14:08,230 --> 00:14:11,510
și vă spune ce
computerul este de a face.

313
00:14:11,510 --> 00:14:14,630
Pasul în funcțiune merge
în funcția propriu-zisă

314
00:14:14,630 --> 00:14:16,000
care e pe linia de cod.

315
00:14:16,000 --> 00:14:19,070
Deci, de exemplu, cum ar fi printf (),
că este o funcție, nu?

316
00:14:19,070 --> 00:14:21,980
Dacă aș fi vrut să pas fizic
în (funcția printf),

317
00:14:21,980 --> 00:14:25,610
Mi-ar merge de fapt, în piesa de
Cod în cazul în care printf () a fost scris și a vedea

318
00:14:25,610 --> 00:14:26,730
ce se întâmplă acolo.

319
00:14:26,730 --> 00:14:29,924
>> Dar de obicei, vom presupune că
codul pe care vă oferim funcționează.

320
00:14:29,924 --> 00:14:31,340
Vom presupune că printf () este de lucru.

321
00:14:31,340 --> 00:14:33,170
Presupunem că getint () este de lucru.

322
00:14:33,170 --> 00:14:35,170
Deci nu este nevoie să
pas în aceste funcții.

323
00:14:35,170 --> 00:14:37,170
Dar dacă nu e funcții
care te scrie

324
00:14:37,170 --> 00:14:39,060
pe care doriți să verificați
ce se întâmplă,

325
00:14:39,060 --> 00:14:41,200
ce-ar vrea să-și intensifice
în această funcție.

326
00:14:41,200 --> 00:14:43,940
>> Deci, acum suntem doar de gând
să-și intensifice pe această bucată de cod.

327
00:14:43,940 --> 00:14:44,485
Deci, să vedem.

328
00:14:44,485 --> 00:14:46,547
Oh, print, "Oh hai, cum
schimba prea mult se datorează? "

329
00:14:46,547 --> 00:14:47,130
Noi nu le pasă.

330
00:14:47,130 --> 00:14:49,830
Știm că funcționează,
asa ca am pas peste el.

331
00:14:49,830 --> 00:14:53,290
>> Deci n, care este float noastră ca
ne-am initialized-- sau declared--

332
00:14:53,290 --> 00:14:56,810
până la partea de sus, suntem acum
egalând care să GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Deci, haideți să pas peste asta.

334
00:14:57,810 --> 00:14:59,580
Si vom vedea la
fund aici, programul

335
00:14:59,580 --> 00:15:03,360
ma determinat pentru a introduce o valoare.

336
00:15:03,360 --> 00:15:08,580
Deci, haideți să introduceți valoarea ne-o dorim
pentru a testa aici, care este 0.41.

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

338
00:15:09,160 --> 00:15:12,780
>> Deci, acum N- face voi vedea
aici, la bottom-- e

339
00:15:12,780 --> 00:15:15,140
stored-- că noi
nu s-au rotunjit încă, e

340
00:15:15,140 --> 00:15:19,540
În această colecție de gigant ca
float, care este 0.4099999996,

341
00:15:19,540 --> 00:15:22,550
care este destul de aproape de nostru
scopuri, acum, la 0,41.

342
00:15:22,550 --> 00:15:26,090
Și apoi vom vedea mai târziu, așa cum am
continua pas cu pas peste program,

343
00:15:26,090 --> 00:15:29,850
după aici, n a devenit
rotunjite și cenți a devenit 41.

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

345
00:15:30,350 --> 00:15:32,230
Deci, noi știm că de lucru rotunjirea nostru.

346
00:15:32,230 --> 00:15:34,700
Știm că avem
Numărul corect de cenți,

347
00:15:34,700 --> 00:15:36,990
astfel știm că asta e
nu într-adevăr problema.

348
00:15:36,990 --> 00:15:40,050
>> Deci, vom continua pas cu pas
pe în acest program.

349
00:15:40,050 --> 00:15:40,900
Mergem aici.

350
00:15:40,900 --> 00:15:46,139
Și astfel, după această linie de cod, am
ar trebui să știe cât de multe trimestre avem.

351
00:15:46,139 --> 00:15:46,680
Am pas peste.

352
00:15:46,680 --> 00:15:52,040
Și veți vedea ce facem, de fapt, au un
sfert pentru că ne-am scăzut 25

353
00:15:52,040 --> 00:15:53,790
din valoarea noastra initiala a 41.

354
00:15:53,790 --> 00:15:55,890
Și avem 16 de cenți pentru stângă noastre.

355
00:15:55,890 --> 00:15:58,830
>> Are toată lumea să înțeleagă cum
Programul își intensifică prin

356
00:15:58,830 --> 00:16:02,980
si de ce cenți a devenit acum 16
si de ce, acum, monede a devenit 1?

357
00:16:02,980 --> 00:16:04,610
Este toată lumea urmând ca logica?

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

359
00:16:05,110 --> 00:16:07,860
Deci, ca din acest punct,
de lucru program, nu?

360
00:16:07,860 --> 00:16:09,797
Știm că face exact
ceea ce vrem să.

361
00:16:09,797 --> 00:16:11,880
Și nu am făcut de fapt
trebuie să imprime, oh, ce

362
00:16:11,880 --> 00:16:14,430
este de cenți de la acest punct,
ceea ce este de monede în acest moment.

363
00:16:14,430 --> 00:16:17,170
>> Am continua merge prin intermediul programului.

364
00:16:17,170 --> 00:16:18,100
Pas peste.

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

366
00:16:18,620 --> 00:16:19,700
Mergem peste Dimes.

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

368
00:16:20,200 --> 00:16:22,367
Vedem că este luat
off 0.10 $ pentru un ban.

369
00:16:22,367 --> 00:16:23,450
Și acum avem două monede.

370
00:16:23,450 --> 00:16:25,260
Este corect.

371
00:16:25,260 --> 00:16:31,555
>> Mergem pe bani si vom vedea
că am rămas peste cenți.

372
00:16:31,555 --> 00:16:32,680
Hmm, asta e ciudat.

373
00:16:32,680 --> 00:16:37,540
Până aici, la program, eu trebuia
au scăzut mărunțiș mele.

374
00:16:37,540 --> 00:16:39,400
Poate că pur și simplu nu a fost
face acest drept linie.

375
00:16:39,400 --> 00:16:42,190
Și vai, puteți vedea
aici, pentru că știm

376
00:16:42,190 --> 00:16:44,360
că suntem pas cu pas
prin linii 32 și 33,

377
00:16:44,360 --> 00:16:50,560
care este în cazul în care programul nostru
a avut în mod necorespunzător variabile rula.

378
00:16:50,560 --> 00:16:55,136
Astfel încât să putem uita și vedea, oh,
Sunt scăderea cenți aici,

379
00:16:55,136 --> 00:16:57,010
dar eu nu sunt de fapt
adăugând la valoarea mea de monede.

380
00:16:57,010 --> 00:16:57,860
Sunt adăugând la cenți.

381
00:16:57,860 --> 00:17:00,234
Și nu vreau să adăugați la
cenți, vreau să adăugați la monede.

382
00:17:00,234 --> 00:17:05,420
Deci, dacă vom schimba asta monede,
avem un program de lucru.

383
00:17:05,420 --> 00:17:06,730
Pot rula check50.

384
00:17:06,730 --> 00:17:11,063
Puteți ieși doar din GDB drept
aici și apoi executați din nou check50.

385
00:17:11,063 --> 00:17:11,938
Aș putea face doar asta.

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

387
00:17:14,822 --> 00:17:18,480
Trebuie să lacomi.

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

389
00:17:19,940 --> 00:17:22,819
Și aici, e de imprimare
raspunsul corect.

390
00:17:22,819 --> 00:17:26,569
>> Deci, ca voi poate vedea, GDB
este un instrument foarte puternic

391
00:17:26,569 --> 00:17:29,940
pentru că atunci când ne-am atât de mult cod
întâmplă și atât de multe variabile

392
00:17:29,940 --> 00:17:32,510
că e greu pentru noi, ca
un om, pentru a ține evidența.

393
00:17:32,510 --> 00:17:35,360
Computerul, în GDB
debugger, are capacitatea de

394
00:17:35,360 --> 00:17:37,020
pentru a urmări tot.

395
00:17:37,020 --> 00:17:40,480
Știu, în Visionaire, voi probabil
ar fi lovit unele defecte de segmentare

396
00:17:40,480 --> 00:17:43,150
pentru că au fost difuzate
în afara limitelor de matrice dumneavoastră.

397
00:17:43,150 --> 00:17:46,510
În exemplul de Cezar, care este
exact ceea ce am implementat aici.

398
00:17:46,510 --> 00:17:50,060
>> Așa că am uitat pentru a verifica
ce s-ar întâmpla dacă am

399
00:17:50,060 --> 00:17:52,510
nu au avut două argumente în linia de comandă.

400
00:17:52,510 --> 00:17:53,880
Doar că nu am pus în control.

401
00:17:53,880 --> 00:17:57,380
Și deci, dacă am alerga Debug-- am stabilit
breakpoint mea chiar acolo.

402
00:17:57,380 --> 00:17:58,055
I a alerga Debug.

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

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

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

406
00:18:17,050 --> 00:18:20,350
Deci, de fapt, ar fi trebuit GDB
să mi-au spus acolo

407
00:18:20,350 --> 00:18:22,300
a fost o eroare de segmentare acolo.

408
00:18:22,300 --> 00:18:24,883
Nu știu ce se întâmplă
chiar acolo, dar când l-am fugit,

409
00:18:24,883 --> 00:18:25,590
a fost de lucru.

410
00:18:25,590 --> 00:18:29,410
Când executați linii de cod, prin și
GDB ar putea iesi doar dintr-o dată pe tine,

411
00:18:29,410 --> 00:18:31,540
du-te în sus și uite ce eroarea roșu este.

412
00:18:31,540 --> 00:18:33,930
Acesta să-ți spun, hei, tu
a avut o eroare de segmentare,

413
00:18:33,930 --> 00:18:38,550
ceea ce înseamnă că ați încercat să acces
spațiu într-o matrice care nu exista.

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

415
00:18:39,050 --> 00:18:43,280
>> Deci, în problema următoare
stabilite în această săptămână, voi

416
00:18:43,280 --> 00:18:45,600
va avea, probabil, o mulțime de
variabile plutesc în jurul.

417
00:18:45,600 --> 00:18:48,560
Nu vei fi sigur că ceea ce
toate acestea înseamnă, la un moment dat.

418
00:18:48,560 --> 00:18:53,560
Deci GDB vă va ajuta cu adevărat în imaginind
ce sunt toate egală

419
00:18:53,560 --> 00:18:55,940
și posibilitatea de a vedea că vizual.

420
00:18:55,940 --> 00:19:01,995
Este cineva confuz cu privire la modul
oricare dintre care a fost de lucru?

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

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

423
00:19:10,121 --> 00:19:10,620
In regula.

424
00:19:10,620 --> 00:19:14,260
Deci, după care, suntem
O să se arunca cu capul dreapta

425
00:19:14,260 --> 00:19:17,562
în patru diferite
tipuri de soiuri pentru această săptămână.

426
00:19:17,562 --> 00:19:19,520
Câți dintre voi, în primul rând
de toate, înainte de a începe,

427
00:19:19,520 --> 00:19:23,020
au citit întregul spec pentru pset3?

428
00:19:23,020 --> 00:19:23,824
BINE.

429
00:19:23,824 --> 00:19:24,740
Sunt mândru de voi.

430
00:19:24,740 --> 00:19:29,110
E ca și cum jumătate din clasă, care
este semnificativ mai mult decât data trecută.

431
00:19:29,110 --> 00:19:33,950
>> Așa că e minunat, pentru că atunci când
vorbim despre conținutul

432
00:19:33,950 --> 00:19:36,170
în lecture-- sau rău,
în section-- Îmi place

433
00:19:36,170 --> 00:19:38,210
să se refere o mulțime de care
înapoi la ceea ce este PSET

434
00:19:38,210 --> 00:19:40,210
și modul în care doriți să
punerea în aplicare a care in PSET ta.

435
00:19:40,210 --> 00:19:42,400
Deci, dacă vii cu
citit spec, va

436
00:19:42,400 --> 00:19:45,510
fi mult mai ușor pentru tine de a înțelege
ce vorbesc despre atunci când spun,

437
00:19:45,510 --> 00:19:48,720
Oh Hei, acest lucru ar putea fi un adevărat
loc bun pentru a pune în aplicare acest tip.

438
00:19:48,720 --> 00:19:52,870
Astfel încât cei dintre voi care au citit
spec știu că, în calitate de parte a PSET dumneavoastră,

439
00:19:52,870 --> 00:19:54,900
ai de gând să trebuie să
scrie un tip de fel.

440
00:19:54,900 --> 00:19:58,670
Deci, acest lucru poate fi foarte util
pentru o mulțime de tine azi.

441
00:19:58,670 --> 00:20:01,760
>> Deci, vom începe cu,
în esență, tipul cel mai simplu

442
00:20:01,760 --> 00:20:04,580
de fel, genul de selecție.

443
00:20:04,580 --> 00:20:06,800
Algoritmul tipic pentru
cum ne-ar merge cu privire la această

444
00:20:06,800 --> 00:20:10,460
este-- David a trecut prin toate aceste în
curs, așa că voi trece rapid de-a lungul

445
00:20:10,460 --> 00:20:13,900
here-- este, în esență, tu
au o serie de valori.

446
00:20:13,900 --> 00:20:17,170
Și apoi găsi
cea mai mică valoare nesortate

447
00:20:17,170 --> 00:20:20,200
și te schimb ca valoarea cu
prima valoare nesortate.

448
00:20:20,200 --> 00:20:22,700
Și apoi doar repeta
cu restul de lista.

449
00:20:22,700 --> 00:20:25,740
>> Și aici o explicație vizual
de modul în care care să funcționeze.

450
00:20:25,740 --> 00:20:30,460
Deci, de exemplu, dacă ar fi să înceapă
cu o serie de cinci elemente, indicele

451
00:20:30,460 --> 00:20:35,910
0 la 4, cu 3, 5, 2, 6, și 4 valori
plasate în array-- așa acum,

452
00:20:35,910 --> 00:20:38,530
ne doar de gând să-și asume
că toate sunt nesortate

453
00:20:38,530 --> 00:20:41,130
pentru că nu am testat altfel.

454
00:20:41,130 --> 00:20:44,130
>> Deci, cum ar fi un fel de selecție
lucru este că va prima

455
00:20:44,130 --> 00:20:46,800
alerga prin totalitatea
de matrice nesortate.

456
00:20:46,800 --> 00:20:49,120
Aceasta ar alege cea mai mică valoare.

457
00:20:49,120 --> 00:20:51,750
În acest caz, 3, dreapta
acum, este cel mai mic.

458
00:20:51,750 --> 00:20:52,680
Se ajunge la 5.

459
00:20:52,680 --> 00:20:55,620
Nu, 5 nu este mai mare than--
sau îmi pare rău, nu este mai puțin than-- 3.

460
00:20:55,620 --> 00:20:57,779
Deci, valoarea minimă este încă 3.

461
00:20:57,779 --> 00:20:58,695
Și apoi vei ajunge la 2.

462
00:20:58,695 --> 00:21:00,990
Computerul vede, oh, 2 este mai mică de 3.

463
00:21:00,990 --> 00:21:02,750
2 trebuie să fie acum valoarea minimă.

464
00:21:02,750 --> 00:21:06,630
Și astfel 2 swap-uri cu care primul valoare.

465
00:21:06,630 --> 00:21:10,702
>> Deci, după o pasă, noi nu vedem într-adevăr
că 2 și 3 sunt schimbate.

466
00:21:10,702 --> 00:21:13,910
Și noi suntem doar de gând să continue să facă
acest nou cu restul matrice.

467
00:21:13,910 --> 00:21:17,660
Deci vom rula doar prin
ultimele patru indicii matrice.

468
00:21:17,660 --> 00:21:20,670
Vom vedea că este 3
următoarea valoare minimă.

469
00:21:20,670 --> 00:21:23,240
Deci vom schimba asta cu 4.

470
00:21:23,240 --> 00:21:26,900
Și apoi vom merge doar pentru a păstra
trece prin până când, în cele din urmă, ai

471
00:21:26,900 --> 00:21:33,730
ajunge la o gamă sortat în care
2, 3, 4, 5, 6 și sunt toate sortate.

472
00:21:33,730 --> 00:21:37,530
Are toată lumea să înțeleagă logica
a modului în care funcționează un fel de selecție?

473
00:21:37,530 --> 00:21:39,669
>> Trebuie doar un fel
de o valoare minimă.

474
00:21:39,669 --> 00:21:41,210
Ești urmărirea a ceea ce este asta.

475
00:21:41,210 --> 00:21:45,170
Și ori de câte ori ai găsit, îl schimb
cu prima valoare din array--

476
00:21:45,170 --> 00:21:48,740
sau, nu, prima value--
următoarea valoare din matrice.

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

478
00:21:50,150 --> 00:21:55,460
>> Deci, ca voi fel de
a văzut de la o scurtă privire,

479
00:21:55,460 --> 00:21:58,450
vom pseudocod asta.

480
00:21:58,450 --> 00:22:02,510
Deci, dacă voi în spate care doriți să
formează un grup, toată lumea la o masă

481
00:22:02,510 --> 00:22:06,170
poate forma un pic partener, am de gând
pentru a vă oferi tipi ca trei minute

482
00:22:06,170 --> 00:22:08,190
pentru a vorbi doar prin
logica, în limba engleză,

483
00:22:08,190 --> 00:22:14,161
de modul în care am putea fi în măsură să pună în aplicare
pseudocod pentru a scrie un fel de selecție.

484
00:22:14,161 --> 00:22:14,910
Și nu e bomboane.

485
00:22:14,910 --> 00:22:16,118
Vă rugăm să vină și să bomboane.

486
00:22:16,118 --> 00:22:19,520
Dacă sunteți în spate si doriti
bomboane, pot arunca bomboane la tine.

487
00:22:19,520 --> 00:22:22,850
De fapt, nu Tu-- rece.

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

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

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

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

492
00:25:23,880 --> 00:25:27,140
>> Deci, dacă am dori să, ca
o clasă, pseudocod scrie

493
00:25:27,140 --> 00:25:30,466
pentru modul în care s-ar putea apropia de o
această problemă, doar nu ezitați.

494
00:25:30,466 --> 00:25:32,340
Mă duc doar în jurul și,
în ordine, cere grupurilor

495
00:25:32,340 --> 00:25:35,065
pentru următoarea linie de
ceea ce ar trebui sa facem.

496
00:25:35,065 --> 00:25:37,840
Deci, dacă vreți să începeți
off, ceea ce este primul lucru pe care

497
00:25:37,840 --> 00:25:40,600
să fac atunci când sunteți încercarea de a
pună în aplicare un mod de a rezolva acest program

498
00:25:40,600 --> 00:25:43,480
pentru a sorta selectiv o listă?

499
00:25:43,480 --> 00:25:46,349
Să presupunem că
au o matrice, bine?

500
00:25:46,349 --> 00:25:49,088
>> Audiența: Doriți să creați unele
un fel de [neauzit] că ești

501
00:25:49,088 --> 00:25:50,420
trece prin întreaga matrice ta.

502
00:25:50,420 --> 00:25:51,128
>> ANDI Peng: dreapta.

503
00:25:51,128 --> 00:25:54,100
Deci ai de gând să doriți să repeta
prin fiecare spațiu, nu?

504
00:25:54,100 --> 00:26:05,490
Asa de bine.

505
00:26:05,490 --> 00:26:08,600
Dacă vreți să-mi dea
următor line-- Da, în spate.

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

507
00:26:11,414 --> 00:26:13,290
>> Audiența: Verificați-le
toate pentru cele mai mici.

508
00:26:13,290 --> 00:26:14,248
>> ANDI Peng: Nu mergem.

509
00:26:14,248 --> 00:26:17,438
Așa că vreau să merg prin și verificați
vedea ce valoarea minimă este, nu?

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

511
00:26:22,110 --> 00:26:24,840
Am de gând să abrevierea că la "min."

512
00:26:24,840 --> 00:26:27,658
Ce vreți să faceți după
ați găsit valoarea minimă?

513
00:26:27,658 --> 00:26:28,533
>> Audiența: [inaudibil]

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

515
00:26:29,942 --> 00:26:33,150
ANDI Peng: Deci ai de gând să doriți să
porniți-l cu primul de care matrice,

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

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

518
00:26:45,120 --> 00:26:46,850
Asta e de la început, am de gând să spun.

519
00:26:46,850 --> 00:26:47,220
In regula.

520
00:26:47,220 --> 00:26:50,386
Deci, acum că v-ați schimbat primul
o, ce vrei să faci după aceea?

521
00:26:50,386 --> 00:26:54,840
Deci, acum știm că asta aici
trebuie să fie cea mai mică valoare, nu?

522
00:26:54,840 --> 00:26:58,310
Atunci aveți o odihnă suplimentar
de matrice care este nesortate.

523
00:26:58,310 --> 00:27:01,569
Deci, ce vrei sa faci aici, dacă
Vreți să-mi dea linia următoare?

524
00:27:01,569 --> 00:27:04,610
Audiența: Deci vrei să repeta
prin restul de matrice.

525
00:27:04,610 --> 00:27:05,276
ANDI Peng: Da.

526
00:27:05,276 --> 00:27:09,857
Și așa mai departe ce iterarea prin
fel de probabil implica vom avea nevoie?

527
00:27:09,857 --> 00:27:10,440
Ce tip de--

528
00:27:10,440 --> 00:27:12,057
>> Audiența: Oh, o variabilă suplimentară?

529
00:27:12,057 --> 00:27:13,890
ANDI Peng: Probabil
alta pentru buclă, nu?

530
00:27:13,890 --> 00:27:28,914
Așa că, probabil, va dori
a repeta through-- mare.

531
00:27:28,914 --> 00:27:31,830
Și apoi o să se întoarcă și să
probabil verifica din nou minim,

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

533
00:27:32,100 --> 00:27:34,975
Și ai de gând să repeta
acest lucru, deoarece buclele doar de gând

534
00:27:34,975 --> 00:27:36,010
a continua să fie difuzate, nu?

535
00:27:36,010 --> 00:27:39,190
>> Deci, ca voi poate vedea, am
doar un pseudocod generală

536
00:27:39,190 --> 00:27:41,480
de modul în care ne-o dorim acest program să se uite.

537
00:27:41,480 --> 00:27:46,646
Acest repeta aici, ce facem
de obicei nevoie pentru a scrie în codul nostru

538
00:27:46,646 --> 00:27:49,270
dacă vrem să repeta prin intermediul unei
matrice, ce tip de structură?

539
00:27:49,270 --> 00:27:51,030
Cred că Christabel
spus deja acest lucru înainte de.

540
00:27:51,030 --> 00:27:51,500
>> Audiența: A pentru buclă.

541
00:27:51,500 --> 00:27:52,160
>> ANDI Peng: A pentru buclă?

542
00:27:52,160 --> 00:27:52,770
Exact.

543
00:27:52,770 --> 00:27:56,060
Deci aceasta este, probabil
Va fi o pentru buclă.

544
00:27:56,060 --> 00:27:59,240
Ce este o verificare aici va implica?

545
00:27:59,240 --> 00:28:02,536
De obicei, în cazul în care doriți să verificați
dacă ceva este ceva else--

546
00:28:02,536 --> 00:28:03,270
>> Audiența: Dacă.

547
00:28:03,270 --> 00:28:06,790
>> ANDI Peng: Un dacă, nu?

548
00:28:06,790 --> 00:28:10,790
Și apoi swap aici, vom
du-te peste mai târziu, pentru că David

549
00:28:10,790 --> 00:28:12,770
a trecut prin faptul că, în curs, de asemenea.

550
00:28:12,770 --> 00:28:14,580
Iar apoi a doua repeta implies--

551
00:28:14,580 --> 00:28:15,120
>> Audiența: Un alt pentru bucla.

552
00:28:15,120 --> 00:28:16,745
>> ANDI Peng: --another pentru bucla, exact.

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

554
00:28:19,870 --> 00:28:22,000
Deci, dacă ne uităm
la acest corect, am

555
00:28:22,000 --> 00:28:24,680
se poate vedea că suntem, probabil,
avea nevoie de o imbricat pentru buclă

556
00:28:24,680 --> 00:28:28,330
cu o declarație condiționată acolo
și apoi o piesă reală de cod care este

557
00:28:28,330 --> 00:28:31,360
O să schimb valorile.

558
00:28:31,360 --> 00:28:35,980
Așa că am scris doar în general,
un cod pseudocod aici.

559
00:28:35,980 --> 00:28:38,910
Și apoi vom merge de fapt
la fizic, ca o clasă,

560
00:28:38,910 --> 00:28:40,700
încercați să pună în aplicare acest lucru astăzi.

561
00:28:40,700 --> 00:28:42,486
Să ne întoarcem în acest 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
De ce este că not-- acolo este.

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

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

567
00:28:55,834 --> 00:28:57,500
Ne pare rău, lasă-mă să încerc pentru a mări un pic mai mult.

568
00:28:57,500 --> 00:28:59,310
Nu mergem.

569
00:28:59,310 --> 00:29:05,060
Tot ce fac aici e că am creat
un program numit "selecție / sort.c."

570
00:29:05,060 --> 00:29:10,860
Am creat o serie de nouă
Valorile, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
În prezent, după cum puteți
vezi, ele sunt neordonate.

572
00:29:14,370 --> 00:29:17,880
n va fi numărul care
vă spune suma valorilor

573
00:29:17,880 --> 00:29:18,920
aveți în matrice ta.

574
00:29:18,920 --> 00:29:20,670
În acest caz, avem nouă valori.

575
00:29:20,670 --> 00:29:23,760
Și eu doar am o buclă pentru aici
că imprimă matrice nesortate.

576
00:29:23,760 --> 00:29:28,370
>> Și la final, am, de asemenea, o pentru
bucla care tocmai se imprimă din nou.

577
00:29:28,370 --> 00:29:32,070
Deci teoretic, în cazul în care acest program
funcționează corect, la sfârșitul anului,

578
00:29:32,070 --> 00:29:35,670
ar trebui să vedeți o tipărite pentru buclă
în care 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 sunt corect pentru.

580
00:29:39,310 --> 00:29:43,410
>> Deci avem pseudocod aici.

581
00:29:43,410 --> 00:29:46,090
Vrea cineva sa-- Sunt doar
de gând să meargă cere volunteers--

582
00:29:46,090 --> 00:29:49,540
spune-mi exact ce să tastați, dacă
vrem să, în primul rând, doar repeta

583
00:29:49,540 --> 00:29:52,840
prin începutul acestui tablou?

584
00:29:52,840 --> 00:29:55,204
Care este linia de cod sunt
probabil, va avea nevoie de aici?

585
00:29:55,204 --> 00:29:56,990
>> Audiența: [inaudibil]

586
00:29:56,990 --> 00:29:59,010
>> ANDI Peng: Da, simt
gratuit sa-- Ne pare rău,

587
00:29:59,010 --> 00:30:02,318
Nu trebuie să stea simt up--
libertatea de a ridica vocea un pic.

588
00:30:02,318 --> 00:30:08,190
>> Audiența: Pentru int i egal 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI Peng: Da, bine.

590
00:30:10,690 --> 00:30:15,220
>> Audiența: i este mai mică decât lungimea matrice.

591
00:30:15,220 --> 00:30:19,630
>> ANDI Peng: Deci păstrați în
minte aici, pentru că noi

592
00:30:19,630 --> 00:30:23,060
nu au o funcție care
ne spune lungimea o matrice,

593
00:30:23,060 --> 00:30:25,790
avem deja o
valoare care stochează asta.

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

595
00:30:27,920 --> 00:30:31,010
Un alt lucru de a păstra
în mind-- într-o matrice

596
00:30:31,010 --> 00:30:33,940
de nouă valori, care sunt indicii?

597
00:30:33,940 --> 00:30:38,720
Să spunem doar că aceasta matrice a fost 0-3.

598
00:30:38,720 --> 00:30:41,500
Veți vedea că ultimul
Indicele este, de fapt 3.

599
00:30:41,500 --> 00:30:45,530
Nu e 4, chiar dacă nu e
patru valori în matrice.

600
00:30:45,530 --> 00:30:49,866
>> Deci aici, trebuie să fim foarte atenți
de ceea ce starea noastră de lungimea

601
00:30:49,866 --> 00:30:50,490
Va fi.

602
00:30:50,490 --> 00:30:51,948
>> Audiența: N-ar fi n minus 1?

603
00:30:51,948 --> 00:30:54,440
ANDI Peng: Va
n minus 1, exact.

604
00:30:54,440 --> 00:30:57,379
Are vreun sens, de ce
e n minus 1, toată lumea?

605
00:30:57,379 --> 00:30:58,920
Este pentru că matrice sunt indexate zero.

606
00:30:58,920 --> 00:31:02,010
Ei încep de la 0 și a alerga până la n minus 1.

607
00:31:02,010 --> 00:31:03,210
Da, e un pic complicat.

608
00:31:03,210 --> 00:31:03,730
BINE.

609
00:31:03,730 --> 00:31:05,929
Si atunci--

610
00:31:05,929 --> 00:31:08,054
Audiența: Isnt'1 care
deja grijă de, deși,

611
00:31:08,054 --> 00:31:11,400
doar prin a spune nu ", mai mică sau
egal cu "si doar că" mai puțin de? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI Peng: Acesta este un
foarte bun întrebare.

613
00:31:13,108 --> 00:31:13,630
Deci da.

614
00:31:13,630 --> 00:31:17,410
Dar, de asemenea, modul în care suntem
de punere în aplicare a dreptului de verificare,

615
00:31:17,410 --> 00:31:19,120
aveți nevoie pentru a compara două valori.

616
00:31:19,120 --> 00:31:21,009
Deci vrei de fapt să
lăsați "la" gol.

617
00:31:21,009 --> 00:31:23,050
Pentru că dacă veți compara
asta, nu te duci

618
00:31:23,050 --> 00:31:25,530
au nimic dupa ce a
pentru a compara, nu?

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

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

621
00:31:29,297 --> 00:31:30,380
Să adăugăm paranteze noastre în.

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

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

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

625
00:31:34,710 --> 00:31:39,117
Așa că avem la început
de buclă nostru exterior.

626
00:31:39,117 --> 00:31:41,450
Deci, acum, probabil, vrem să
a crea o variabilă pentru păstrarea

627
00:31:41,450 --> 00:31:43,085
evidența valoarea cea mai mică, nu?

628
00:31:43,085 --> 00:31:45,751
Nimeni nu vrea să-mi dea
linie de cod care ar face asta?

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

630
00:31:48,700 --> 00:31:53,570
De ce avem nevoie, dacă vrem
să doriți să stocați ceva?

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

632
00:31:55,047 --> 00:31:57,630
Poate un nume mai bun pentru că
ar be-- "temp" total works--

633
00:31:57,630 --> 00:32:00,655
poate o mai bună dreptate numit ar fi,
dacă vrem cel mai mic value--

634
00:32:00,655 --> 00:32:01,624
>> Audiența: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI Peng: min, acolo mergem.

636
00:32:02,790 --> 00:32:05,230
min ar fi bine.

637
00:32:05,230 --> 00:32:08,340
Și astfel aici, ce facem
doriți să-l inițializa la?

638
00:32:08,340 --> 00:32:09,620
Acesta este un pic complicat.

639
00:32:09,620 --> 00:32:13,580
Pentru că acum, la
începutul acestui tablou,

640
00:32:13,580 --> 00:32:15,730
nu ați uitat la ceva, nu?

641
00:32:15,730 --> 00:32:19,200
Deci, ceea ce, în mod automat, în cazul în care
suntem doar pe i este egal cu 0,

642
00:32:19,200 --> 00:32:22,302
ceea ce vrem pentru a inițializa
prima noastră valoare minimă a?

643
00:32:22,302 --> 00:32:22,802
Audiența: i.

644
00:32:22,802 --> 00:32:24,790
ANDI Peng: i, exact.

645
00:32:24,790 --> 00:32:27,040
Christabel, de ce vrem
să-l inițializa la i?

646
00:32:27,040 --> 00:32:28,510
>> Audiența: Pentru că, ei bine,
suntem incepand cu 0.

647
00:32:28,510 --> 00:32:31,660
Deci, pentru că nu avem nimic de a compara
l, minimul va sfârși prin a fi 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI Peng: Exact.

649
00:32:32,451 --> 00:32:34,400
Deci, ea este exact corect.

650
00:32:34,400 --> 00:32:36,780
Pentru ca avem de fapt, nu
se uită la nimic încă,

651
00:32:36,780 --> 00:32:38,680
nu știm ce valoare nostru minim este.

652
00:32:38,680 --> 00:32:41,960
Vrem să-l inițializa la doar
i, care, în prezent, este chiar aici.

653
00:32:41,960 --> 00:32:44,750
Si ca vom continua sa
deplasa în jos această matrice,

654
00:32:44,750 --> 00:32:48,122
vom vedea că, cu fiecare
pass suplimentar, i incrementează.

655
00:32:48,122 --> 00:32:49,830
Și astfel, la acel moment,
i este, probabil, va

656
00:32:49,830 --> 00:32:52,329
să vrea să fie minim,
pentru că va fi orice

657
00:32:52,329 --> 00:32:54,520
este începutul matrice nesortate.

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

659
00:32:55,270 --> 00:32:58,720
>> Deci, acum vrem să adăugați
o pentru buclă aici care este

660
00:32:58,720 --> 00:33:03,225
O să repeta prin
nesortate, sau restul acestui tablou.

661
00:33:03,225 --> 00:33:05,808
Nimeni nu vrea să-mi dea un
linie de cod care ar face asta?

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

663
00:33:08,870 --> 00:33:11,330
Hint-- ce avem nevoie aici?

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

665
00:33:17,320 --> 00:33:18,820
Ce se va merge în această buclă pentru?

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

667
00:33:19,465 --> 00:33:21,590
Audiența: Deci am vrea să
au un număr întreg diferit,

668
00:33:21,590 --> 00:33:25,080
pentru că nu mai avem prin restul
de matrice în loc de i, deci poate

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

670
00:33:25,760 --> 00:33:27,301
>> ANDI Peng: Da, J sună bine pentru mine.

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

672
00:33:27,850 --> 00:33:33,930
>> Audiența: Deci ar fi i, plus 1, pentru că
începi la valoarea următoare.

673
00:33:33,930 --> 00:33:40,395
Și apoi la end-- lucru din nou, j este
mai puțin de n minus 1, și apoi 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
>> Și apoi aici, vom dori
pentru a verifica pentru a vedea dacă starea noastră este îndeplinită,

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

678
00:33:53,250 --> 00:33:55,740
Pentru că vrei să
schimba valoarea minimă

679
00:33:55,740 --> 00:33:58,700
dacă este de fapt mai mici decât ceea ce
te-l in comparatie cu, nu?

680
00:33:58,700 --> 00:34:01,146
Deci, ce vom vrea aici?

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

682
00:34:04,160 --> 00:34:04,897
Verificați pentru a vedea.

683
00:34:04,897 --> 00:34:06,730
Ce tip de declarație
sunt, probabil, vom

684
00:34:06,730 --> 00:34:08,389
TI doriți să utilizați, dacă
doriți să verificați ceva?

685
00:34:08,389 --> 00:34:09,360
>> Audiența: O if.

686
00:34:09,360 --> 00:34:10,485
>> ANDI Peng: O if.

687
00:34:10,485 --> 00:34:13,155
Deci if-- și ce va fi
cu condiția ca ne-o dorim în interiorul

688
00:34:13,155 --> 00:34:13,988
de if nostru?

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

690
00:34:18,255 --> 00:34:22,960
>> Audiența: Dacă valoarea J
este mai mică decât valoarea eu--

691
00:34:22,960 --> 00:34:24,600
>> ANDI Peng: Exact.

692
00:34:24,600 --> 00:34:27,480
Deci, așa if-- această matrice se numește "matrice".

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

694
00:34:27,980 --> 00:34:30,465
Deci, dacă array-- ce a fost asta?

695
00:34:30,465 --> 00:34:31,090
Spun asta din nou.

696
00:34:31,090 --> 00:34:39,590
>> Audiența: Dacă array-j este mai mică de
matrice-i, atunci ne-ar schimba min.

697
00:34:39,590 --> 00:34:41,590
Deci min ar fi J.

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

699
00:34:44,590 --> 00:34:47,249
>> ANDI Peng: Are vreun sens?

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

701
00:34:48,670 --> 00:34:52,929
Și acum aici, am de fapt,
doresc să pună în aplicare swap, nu?

702
00:34:52,929 --> 00:34:58,285
Deci amintesc, în curs, David, atunci când
el a fost încercarea de a schimba ceea ce a fost the--

703
00:34:58,285 --> 00:34:59,996
suc de portocale it-- și milk--

704
00:34:59,996 --> 00:35:01,150
>> Audiența: Asta a fost brut.

705
00:35:01,150 --> 00:35:02,816
>> ANDI Peng: Da, a fost un fel de brut.

706
00:35:02,816 --> 00:35:05,310
Dar a fost un bun destul de
Conceptul de timp demonstreze.

707
00:35:05,310 --> 00:35:08,430
Deci, cred că de valorile tale aici.

708
00:35:08,430 --> 00:35:10,794
Ai o serie
de min, o serie de i,

709
00:35:10,794 --> 00:35:12,460
sau orice am încercat să schimb aici.

710
00:35:12,460 --> 00:35:15,310
Și, probabil, nu le poate turna în
reciproc, în același timp, nu?

711
00:35:15,310 --> 00:35:17,180
Deci, ce vom
a trebui să creați aici

712
00:35:17,180 --> 00:35:19,126
în scopul de a schimba valorile corect?

713
00:35:19,126 --> 00:35:19,820
>> Audiența: O variabilă temporară.

714
00:35:19,820 --> 00:35:21,370
>> ANDI Peng: O variabilă temporară.

715
00:35:21,370 --> 00:35:22,570
Deci, hai sa facem Int temp.

716
00:35:22,570 --> 00:35:25,681
Vezi, asta ar fi o mai bună
timp sa-- Hei, ce a fost asta?

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

718
00:35:26,180 --> 00:35:29,800
Deci, aceasta ar fi fost mai bine
timp pentru a denumi "temperatura". variabilă

719
00:35:29,800 --> 00:35:30,730
Deci, hai sa facem Int temp.

720
00:35:30,730 --> 00:35:32,563
Ce vom
setat temp egală cu aici?

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

722
00:35:34,752 --> 00:35:35,335
Audiența: Min?

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

724
00:35:38,508 --> 00:35:39,716
ANDI Peng: Este un pic complicat.

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

726
00:35:43,110 --> 00:35:44,880
Ea de fapt, nu contează în cele din urmă.

727
00:35:44,880 --> 00:35:47,690
Nu contează ce
Pentru alegeți să schimb în

728
00:35:47,690 --> 00:35:50,862
atâta timp cât faci sigur că ești
urmărirea ceea ce pompare.

729
00:35:50,862 --> 00:35:52,250
>> Audiența: Ar putea fi matrice-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI Peng: Da, hai sa facem matrice-i.

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

732
00:35:55,950 --> 00:35:59,305
Și atunci ce e următoarea linie
de cod vrem să avem aici?

733
00:35:59,305 --> 00:36:00,680
Audiența: array-i este egal cu matrice-J.

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

735
00:36:07,154 --> 00:36:08,070
ANDI Peng: Și, în fine?

736
00:36:08,070 --> 00:36:12,070
Audiența: array-J este egal cu matrice-i.

737
00:36:12,070 --> 00:36:14,525
Audiența: Sau array-j egali
-matrice temp-- sau, 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
Așa că haideți să ruleze acest lucru și a vedea
în cazul în care va merge.

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

742
00:36:37,520 --> 00:36:39,335
În cazul în care se întâmplă asta?

743
00:36:39,335 --> 00:36:40,210
Oh, asta eo problemă.

744
00:36:40,210 --> 00:36:44,320
Vezi, pe linia 40, suntem
încearcă să folosească array-J?

745
00:36:44,320 --> 00:36:47,022
Dar în cazul în care nu există doar în j?

746
00:36:47,022 --> 00:36:48,402
>> Audiența: în buclă pentru.

747
00:36:48,402 --> 00:36:49,110
ANDI Peng: dreapta.

748
00:36:49,110 --> 00:36:51,730
Deci, ce vom trebuie să facem?

749
00:36:51,730 --> 00:36:53,170
>> Audiența: Definirea l afara the--

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

751
00:36:57,777 --> 00:37:00,610
Audiența: Da, cred că ai
de a utiliza un alt if, nu?

752
00:37:00,610 --> 00:37:05,230
Deci cum ar fi, în cazul în care minimum--
Bine, lasă-mă să gândesc.

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

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Baieti, încercați
să aruncăm o privire Să

755
00:37:09,990 --> 00:37:11,270
vezi, ceea ce e ceva ce putem face aici?

756
00:37:11,270 --> 00:37:11,811
>> Audiența: OK.

757
00:37:11,811 --> 00:37:15,900
Deci, în cazul în care nu este egal cu minimul
j-- Deci, dacă minimul este încă Eu--

758
00:37:15,900 --> 00:37:17,570
atunci nu ar fi trebuit să schimbe.

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

760
00:37:22,450 --> 00:37:24,712
>> ANDI Peng: Are ca egal i?

761
00:37:24,712 --> 00:37:25,920
Ce vrei să spui aici?

762
00:37:25,920 --> 00:37:30,494
>> Audiența: Da Sau, în cazul în care
minim nu este egal cu i, da.

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
Ei bine, asta rezolvă, un fel de, problemele noastre.

766
00:37:42,040 --> 00:37:47,265
Dar care încă nu rezolvă
problemă de ceea ce se întâmplă în cazul în care de la J j--

767
00:37:47,265 --> 00:37:49,890
nu există în afara de ea, ceea ce
te vrem să facem cu ea?

768
00:37:49,890 --> 00:37:50,698
Declare în afara?

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

770
00:37:59,410 --> 00:38:02,730
Să încercați să rulați acest lucru.

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

772
00:38:04,435 --> 00:38:06,200
Sortare nostru nu funcționează.

773
00:38:06,200 --> 00:38:10,060
>> După cum puteți vedea, inițial nostru
matrice a avut aceste valori.

774
00:38:10,060 --> 00:38:14,800
Și după care ar trebui să aibă
fost în 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Nu functioneaza.

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

777
00:38:16,030 --> 00:38:17,184
Ce facem?

778
00:38:17,184 --> 00:38:17,850
Audiența: Debug.

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

780
00:38:21,787 --> 00:38:23,370
ANDI Peng: Bine, putem încerca asta.

781
00:38:23,370 --> 00:38:25,030
Putem depana.

782
00:38:25,030 --> 00:38:26,042
Micșora un pic.

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

784
00:38:31,177 --> 00:38:33,656
Să setați breakpoint nostru.

785
00:38:33,656 --> 00:38:37,280
Să mergem like-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Deci, pentru că știm deja că
aceste linii, 15 prin 22,

787
00:38:40,444 --> 00:38:43,610
sunt working-- că tot ce fac este
doar iterarea prin și printing--

788
00:38:43,610 --> 00:38:45,406
Eu pot merge mai departe și sari peste asta.

789
00:38:45,406 --> 00:38:47,280
Să începem de la linia 25.

790
00:38:47,280 --> 00:38:48,712
Oop, lasă-mă să scap de asta.

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

792
00:38:51,598 --> 00:38:54,057
>> Audiența: Deci breakpoint de
în cazul în care începe de depanare?

793
00:38:54,057 --> 00:38:54,890
ANDI Peng: sau se opreste.

794
00:38:54,890 --> 00:38:55,670
Audiența: sau se opreste.

795
00:38:55,670 --> 00:38:55,930
ANDI Peng: Da.

796
00:38:55,930 --> 00:38:58,640
Puteți seta mai multe puncte de întrerupere și
se poate sari doar de la unul la altul.

797
00:38:58,640 --> 00:39:01,590
Dar în acest caz nu știm
în cazul în care eroarea se întâmplă.

798
00:39:01,590 --> 00:39:03,780
Deci, vrem doar să
începe de sus în jos.

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

800
00:39:05,020 --> 00:39:05,550
BINE.

801
00:39:05,550 --> 00:39:08,460
>> Deci, această linie de aici, putem interveni.

802
00:39:08,460 --> 00:39:11,499
Puteți vedea aici,
avem un tablou.

803
00:39:11,499 --> 00:39:13,290
Acestea sunt valorile
care sunt în matrice.

804
00:39:13,290 --> 00:39:16,360
Nu vedeți că, cum indicele 0, aceasta
corespunde value-- oh,

805
00:39:16,360 --> 00:39:17,526
Am de gând să încerc pentru a mări.

806
00:39:17,526 --> 00:39:20,650
Îmi pare rău, e foarte greu
să see-- la index matrice 0,

807
00:39:20,650 --> 00:39:24,090
avem o valoare de 4 și
apoi așa mai departe și așa mai departe.

808
00:39:24,090 --> 00:39:25,670
Avem variabilele locale.

809
00:39:25,670 --> 00:39:28,570
Chiar acum i este egal cu
0, pe care ne-o dorim sa fie.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> Și Să țină pas cu pas prin.

812
00:39:33,690 --> 00:39:36,850
Minimă nostru este egal cu 0,
care, de asemenea vrem să fie.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
Și apoi vom intra în al doilea rând pentru noastre
buclă, dacă array-j este mai mică de matrice-i,

815
00:39:45,560 --> 00:39:46,380
care nu a fost.

816
00:39:46,380 --> 00:39:48,130
Deci ai vedea cum
care omit peste asta?

817
00:39:48,130 --> 00:39:52,430
>> Audiența: Deci, dacă ar trebui să
minim, toate that-- nu ar trebui ca

818
00:39:52,430 --> 00:39:55,424
fie în interiorul primul pentru bucla?

819
00:39:55,424 --> 00:39:57,340
ANDI Peng: Nu, pentru că
mai vrei să testați.

820
00:39:57,340 --> 00:40:00,329
Vrei să faci o comparație fiecare
timp, chiar și după ce executați prin ea.

821
00:40:00,329 --> 00:40:02,620
Nu vrei doar să o fac
pe prima trecere-prin intermediul.

822
00:40:02,620 --> 00:40:05,240
Vrei să o faci cu
fiecare trecere suplimentar din nou.

823
00:40:05,240 --> 00:40:07,198
Deci, doriți să verificați pentru
starea dumneavoastră interior.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Deci, noi suntem doar de gând să
continua să fie difuzate pe aici.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Îți dau un indiciu, băieți.

828
00:40:18,420 --> 00:40:23,910
Ea are de a face cu faptul că atunci când
te verificarea condiționată ta,

829
00:40:23,910 --> 00:40:26,600
nu te verificarea
pentru indicele corect.

830
00:40:26,600 --> 00:40:32,510
Deci, acum ești de verificare pentru
Indicele serie de j este mai mică de matrice

831
00:40:32,510 --> 00:40:33,970
Indicele de i.

832
00:40:33,970 --> 00:40:36,580
Dar ce faci de până la
începutul a bucla for?

833
00:40:36,580 --> 00:40:38,260
Ești setarea j egal cu i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Da, astfel încât să putem, de fapt
ieși debugger aici.

836
00:40:45,415 --> 00:40:47,040
Deci, haideți să aruncăm o privire la pseudocod nostru.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- vom
încep de la i este egal cu 0.

839
00:40:52,580 --> 00:40:54,760
Vom merge până la n minus 1.

840
00:40:54,760 --> 00:40:58,040
Să verificăm, am avea acest drept?

841
00:40:58,040 --> 00:40:59,580
Da, asta a fost bine.

842
00:40:59,580 --> 00:41:02,080
>> Deci, apoi în interiorul aici, suntem
va crea o valoare minimă

843
00:41:02,080 --> 00:41:03,630
și a stabilit că egală cu i.

844
00:41:03,630 --> 00:41:04,950
Am făcut asta?

845
00:41:04,950 --> 00:41:06,270
Da, a făcut asta.

846
00:41:06,270 --> 00:41:10,430
Acum, în interiorul nostru pentru bucla, suntem
de gând să faci j este egal cu I la n 1 minus.

847
00:41:10,430 --> 00:41:11,950
Am făcut asta?

848
00:41:11,950 --> 00:41:15,540
Într-adevăr, am făcut asta.

849
00:41:15,540 --> 00:41:19,922
>> Deci toate acestea, ceea ce ne compară aici?

850
00:41:19,922 --> 00:41:20,925
>> Audiența: J plus 1.

851
00:41:20,925 --> 00:41:21,716
ANDI Peng: Exact.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
Și apoi ai de gând să doriți să o setați
minim dumneavoastră egal cu j plus 1, de asemenea.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Așa că am trecut prin asta foarte repede.

856
00:41:32,640 --> 00:41:36,190
Înțeleg voi
de ce e j plus 1?

857
00:41:36,190 --> 00:41:36,890
BINE.

858
00:41:36,890 --> 00:41:40,700
>> Deci, în matrice ta, în
prima trecere prin,

859
00:41:40,700 --> 00:41:44,850
pentru bucla, pentru Int
i este egal cu 0, hai să

860
00:41:44,850 --> 00:41:46,740
și asume acest lucru nu a fost schimbat încă.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Avem o serie de, complet,
doar patru elemente nesortate, nu?

863
00:41:56,760 --> 00:42:00,760
Deci, vrem să inițializa i egal cu 0.

864
00:42:00,760 --> 00:42:03,650
Și am de gând să doar se
alerga prin această buclă.

865
00:42:03,650 --> 00:42:08,560
Și astfel, în prima trecere, vom
pentru a inițializa o variabilă numită "min"

866
00:42:08,560 --> 00:42:11,245
care, de asemenea, i este egal, pentru că
nu avem o valoare minimă.

867
00:42:11,245 --> 00:42:12,870
Așa că e în prezent egală cu 0, de asemenea.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
Și apoi vom trece prin.

870
00:42:17,640 --> 00:42:19,270
Și vrem să repeta din nou.

871
00:42:19,270 --> 00:42:22,900
Acum, că ne-am găsit ceea ce minim nostru
este, vrem să repeta prin

872
00:42:22,900 --> 00:42:25,190
din nou, pentru a vedea dacă este comparat, nu?

873
00:42:25,190 --> 00:42:40,440
Deci J, aici, se întâmplă
la egal i, care este 0.

874
00:42:40,440 --> 00:42:46,320
Și apoi, dacă j matrice plus I, care
este cea care urmează peste, ca fiind mai puțin

875
00:42:46,320 --> 00:42:49,270
decât ceea ce minim curentă
valoare nu este, pe care doriți să schimb.

876
00:42:49,270 --> 00:42:56,850
>> Deci, hai să spunem că am
Trebuie, cum ar fi, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Acum, i este egal cu
0 și j este egal cu 0.

878
00:43:01,610 --> 00:43:05,210
Și asta e valoarea noastră minimă.

879
00:43:05,210 --> 00:43:09,950
Dacă array-j plus Eu-- Deci, dacă cel
asta e, după cea ne uităm la

880
00:43:09,950 --> 00:43:13,450
este mai mare decât cea în fața sa,
se va deveni minim.

881
00:43:13,450 --> 00:43:18,120
>> Deci, aici vom vedea că 5
nu este mai mică decât cea.

882
00:43:18,120 --> 00:43:19,730
Așa că va nu fie 5.

883
00:43:19,730 --> 00:43:23,580
Vedem că 1 este mai mică de 2, nu?

884
00:43:23,580 --> 00:43:32,970
Deci, acum știm că minim noastră este
va fi valoarea indicelui la 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Da?

886
00:43:34,030 --> 00:43:39,170
Și apoi când ajungi aici,
puteți schimba valorile corecte.

887
00:43:39,170 --> 00:43:42,610
>> Așa că atunci când voi tocmai având j
înainte, nu au fost cautati la cel

888
00:43:42,610 --> 00:43:43,260
după el.

889
00:43:43,260 --> 00:43:44,520
Te uitai la
aceeași valoare, care

890
00:43:44,520 --> 00:43:46,290
este motivul pentru care pur si simplu nu făcea nimic.

891
00:43:46,290 --> 00:43:49,721
Asta face sens pentru toată lumea,
de ce am nevoie de asta, plus 1 acolo?

892
00:43:49,721 --> 00:43:50,220
BINE.

893
00:43:50,220 --> 00:43:53,345
Acum hai să rulați prin ea pentru a face
vă că restul de codul este corect.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
De ce se întâmplă asta?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, e chiar aici min.

898
00:44:16,364 --> 00:44:17,780
Am fost compararea valorii greșit.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Oh nu.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh, da, aici am fost
schimbarea valorile greșite, de asemenea.

903
00:44:33,482 --> 00:44:34,940
Pentru că ne-am uitat la i și j.

904
00:44:34,940 --> 00:44:36,440
Acestea sunt cele pe care le-au control.

905
00:44:36,440 --> 00:44:39,160
Noi de fapt doresc să swap
minim, minim actual,

906
00:44:39,160 --> 00:44:40,550
cu oricare ar fi unul exterior este.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
Și, după cum voi puteți vedea în jos
aici, avem o gamă sortat.

909
00:45:05,402 --> 00:45:07,110
Doar avut de a face cu
faptul că atunci când

910
00:45:07,110 --> 00:45:09,350
am fost de verificare
Valorile ne-am comparat,

911
00:45:09,350 --> 00:45:11,226
nu am fost uitat la valorile corecte.

912
00:45:11,226 --> 00:45:13,850
Am fost uita la același cu cel
aici, nu de fapt schimbarea.

913
00:45:13,850 --> 00:45:17,135
Trebuie să se uite la următoarea
să-l și apoi puteți schimba.

914
00:45:17,135 --> 00:45:19,260
Deci asta e ceea ce a fost un fel de
bugging codul nostru înainte.

915
00:45:19,260 --> 00:45:22,460
Și ceea ce am făcut aici este totul
debugger ar fi putut face pentru tine

916
00:45:22,460 --> 00:45:23,810
Tocmai am făcut-o cu privire la
bord, pentru că este mai ușor

917
00:45:23,810 --> 00:45:26,320
pentru a vedea mai degrabă decât încercarea
pentru a mări depanator.

918
00:45:26,320 --> 00:45:29,391
Asta face sens pentru toată lumea?

919
00:45:29,391 --> 00:45:29,890
Misto.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> In regula.

922
00:45:35,410 --> 00:45:41,070
Putem trece la a vorbi despre
notație asimptotică, care

923
00:45:41,070 --> 00:45:44,580
este doar un mod fantezist de a spune
runtime de toate aceste tipuri.

924
00:45:44,580 --> 00:45:47,650
Așa că știu pe David, în curs,
atins runtime.

925
00:45:47,650 --> 00:45:52,124
Și el a mers prin toată formula
de modul de calculare a runtime.

926
00:45:52,124 --> 00:45:53,040
Nu vă faceți griji despre asta.

927
00:45:53,040 --> 00:45:54,660
Daca esti foarte curios
cu privire la modul care funcționează,

928
00:45:54,660 --> 00:45:55,810
nu ezitați să vorbească cu mine după secțiune.

929
00:45:55,810 --> 00:45:57,560
Putem merge prin
formulele împreună.

930
00:45:57,560 --> 00:46:00,689
Dar toate voi avea într-adevăr să
știu este că n pătrat peste 2

931
00:46:00,689 --> 00:46:01,980
este același lucru ca n pătrat.

932
00:46:01,980 --> 00:46:04,710
Deoarece cel mai mare număr,
exponentul, crește cel mai mult.

933
00:46:04,710 --> 00:46:06,590
Și astfel pentru scopurile noastre,
tot ce ne pasă

934
00:46:06,590 --> 00:46:09,470
este faptul că numărul uriaș care este în creștere.

935
00:46:09,470 --> 00:46:13,340
>> Deci, ce este cel mai bun caz
execuție de selecție fel?

936
00:46:13,340 --> 00:46:15,830
Dacă aveți de gând să aibă
a repeta printr-o listă

937
00:46:15,830 --> 00:46:18,712
și apoi repeta prin
restul de această listă,

938
00:46:18,712 --> 00:46:20,420
De câte ori este
Ai de gând să probabil,

939
00:46:20,420 --> 00:46:24,612
în cel mai rău case-- în
cel mai bun caz, sorry-- alerga prin?

940
00:46:24,612 --> 00:46:27,070
Poate mai bine întrebarea este
pentru a cere, ceea ce este cel mai rău caz

941
00:46:27,070 --> 00:46:28,153
execuție de selecție fel.

942
00:46:28,153 --> 00:46:29,366
Audiența: n pătrat.

943
00:46:29,366 --> 00:46:30,740
ANDI Peng: E ​​n patrat, chiar.

944
00:46:30,740 --> 00:46:36,986
Deci, o modalitate ușoară de a gândi de acest lucru este ca,
în orice moment aveți două imbricate pentru bucle,

945
00:46:36,986 --> 00:46:38,110
se va fi n pătrat.

946
00:46:38,110 --> 00:46:40,386
Deoarece nu numai ca esti
trece prin încă o dată,

947
00:46:40,386 --> 00:46:42,260
trebuie să te întorci
în jurul și a alerga prin ea

948
00:46:42,260 --> 00:46:44,980
încă o dată, în interiorul pentru fiecare valoare.

949
00:46:44,980 --> 00:46:48,640
Deci, în acest caz, rulați n
ori n pătrat, care este-- Ne pare rău,

950
00:46:48,640 --> 00:46:50,505
de n ori n, care este egal cu n pătrat.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Și un fel este, de asemenea, un pic
unic, în sensul

953
00:46:56,360 --> 00:46:59,774
că nu contează dacă acestea
Valorile sunt deja în ordine.

954
00:46:59,774 --> 00:47:01,440
Este încă în desfășurare pentru a rula prin intermediul oricum.

955
00:47:01,440 --> 00:47:03,872
Să spunem doar că acest lucru a fost 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Indiferent dacă este sau nu a fost în
ordine, tot s-ar fi fugit prin

957
00:47:07,080 --> 00:47:08,620
și încă verificat valoarea minimă.

958
00:47:08,620 --> 00:47:10,100
Aceasta ar fi făcut
Numărul de controale același

959
00:47:10,100 --> 00:47:12,780
de fiecare dată, chiar dacă aceasta
nu am atins nimic de fapt.

960
00:47:12,780 --> 00:47:16,940
>> Deci, în acest caz, cel mai bun și mai rău
runtime sunt de fapt echivalente.

961
00:47:16,940 --> 00:47:19,160
Deci runtime așteptat
de selecție fel,

962
00:47:19,160 --> 00:47:23,790
pe care le desemnează prin simbolul
de teta, theta, în acest caz,

963
00:47:23,790 --> 00:47:24,790
de asemenea, ar fi n pătrat.

964
00:47:24,790 --> 00:47:26,480
Toate cele trei dintre acestea ar fi n pătrat.

965
00:47:26,480 --> 00:47:29,653
Este toată lumea clar pe ce
runtime este n pătrat?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> In regula.

968
00:47:33,980 --> 00:47:39,120
Așa că am de gând doar pentru a rula rapid
prin restul de soiuri.

969
00:47:39,120 --> 00:47:41,137
Algoritmul de
bubble sort-- amintiți-vă,

970
00:47:41,137 --> 00:47:43,220
aceasta a fost prima
David a trecut în curs.

971
00:47:43,220 --> 00:47:46,000
În esență, vă pas
prin întreaga listă

972
00:47:46,000 --> 00:47:48,950
și tu ai doar swap--
compara două la un moment dat.

973
00:47:48,950 --> 00:47:51,350
Și dacă unul e mai mare,
decât doar le schimba.

974
00:47:51,350 --> 00:47:53,590
Deci, dacă acestea sunt mai mari, v-ar schimba.

975
00:47:53,590 --> 00:47:56,180
Am oficial aici.

976
00:47:56,180 --> 00:47:59,100
>> Deci, hai să spunem că a avut 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Te-ai compara 8 și un 6.

978
00:48:00,571 --> 00:48:01,570
Ai avea nevoie de pentru a le schimba.

979
00:48:01,570 --> 00:48:02,610
Te-ar compara 8 și 4.

980
00:48:02,610 --> 00:48:03,609
Ai avea nevoie de pentru a le schimba.

981
00:48:03,609 --> 00:48:07,000
Dacă trebuie să swap 8 și
de 2, le modifica, de asemenea.

982
00:48:07,000 --> 00:48:10,760
Deci, într-un astfel de sens, puteți vedea,
jucat pe o perioadă lungă de timp,

983
00:48:10,760 --> 00:48:13,730
cum un fel de valori cu bule la
capete, motiv pentru care noi o numim

984
00:48:13,730 --> 00:48:15,320
bubble sort.

985
00:48:15,320 --> 00:48:19,950
>> Ne-ar alerga doar prin din nou pe
doua trecere noastră, și a treia treci noastre,

986
00:48:19,950 --> 00:48:21,150
și a patra trecere nostru.

987
00:48:21,150 --> 00:48:25,820
În esență, bubble sort doar ruleaza
până când nu face nici mai swap-uri.

988
00:48:25,820 --> 00:48:31,109
Deci, în acest sens, aceasta este doar
Pseudocodul general pentru ea.

989
00:48:31,109 --> 00:48:32,650
Nu vă faceți griji, acestea vor fi toate on-line.

990
00:48:32,650 --> 00:48:34,990
Noi nu trebuie să mergem de fapt, peste acest lucru.

991
00:48:34,990 --> 00:48:38,134
>> Am inițializa doar un contor
variabilă care începe la 0.

992
00:48:38,134 --> 00:48:39,800
Și am repeta prin întreaga rețea.

993
00:48:39,800 --> 00:48:43,420
Și dacă o valoare este-- dacă acest lucru
Valoarea este mai mare decât această valoare,

994
00:48:43,420 --> 00:48:44,610
ai de gând pentru a le schimba.

995
00:48:44,610 --> 00:48:46,860
Și apoi ești
O să continui.

996
00:48:46,860 --> 00:48:47,970
Și ai de gând să conta.

997
00:48:47,970 --> 00:48:50,845
Și tu doar de gând să continuăm să facem
acest timp contorul este mai mare

998
00:48:50,845 --> 00:48:53,345
decât 0, ceea ce înseamnă că
de fiecare dată când trebuie să schimbe,

999
00:48:53,345 --> 00:48:55,220
știi că vrei să mergi
înapoi și verificați din nou.

1000
00:48:55,220 --> 00:48:59,510
Doriți să păstrați verificarea până când nu știți
care nu trebuie să mai schimbe.

1001
00:48:59,510 --> 00:49:05,570
>> Deci, ce sunt cele mai bune și cele mai rele
caz Runtime pentru bule fel?

1002
00:49:05,570 --> 00:49:09,300
Și hint-- aceasta este de fapt diferit
de la fel de selecție, în sensul

1003
00:49:09,300 --> 00:49:11,810
că aceste două răspunsuri nu sunt la fel.

1004
00:49:11,810 --> 00:49:14,709
Gândiți-vă la ce se va întâmpla în
un caz în cazul în care a fost deja sortate.

1005
00:49:14,709 --> 00:49:16,500
Și cred despre ceea ce
s-ar întâmpla dacă ar fi fost

1006
00:49:16,500 --> 00:49:18,372
în cazul în care nu a fost sortate.

1007
00:49:18,372 --> 00:49:20,580
Și puteți rula un fel de
prin ce se întâmplă asta.

1008
00:49:20,580 --> 00:49:22,954
Îți dau baieti, cum ar fi, 30
secunde să se gândească la asta.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> BINE.

1011
00:49:53,540 --> 00:49:57,462
Are cineva o presupunere la ceea ce
cel mai rău caz de execuție de bule fel este?

1012
00:49:57,462 --> 00:49:57,962
Da.

1013
00:49:57,962 --> 00:50:07,810
>> Audiența: ar fi, cum ar fi, de n ori
n minus 1 sau ceva de genul asta?

1014
00:50:07,810 --> 00:50:10,650
Cum ar fi, de fiecare dată când se execută,
este doar, cum ar fi, un schimb mai puțin

1015
00:50:10,650 --> 00:50:10,960
că orice ar fi fost.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI Peng: Da, așa
esti complet dreptate.

1017
00:50:12,668 --> 00:50:15,940
Și acesta este un caz în care dumneavoastră
Răspuns fost de fapt mult mai complex

1018
00:50:15,940 --> 00:50:17,240
decât cea care avem nevoie pentru a da.

1019
00:50:17,240 --> 00:50:19,772
Deci o să run-- Sunt
O să șterge toate astea aici.

1020
00:50:19,772 --> 00:50:20,480
Este toată lumea buna?

1021
00:50:20,480 --> 00:50:21,869
Pot să șterg acest lucru?

1022
00:50:21,869 --> 00:50:22,368
BINE.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Vei trece prin n
ori prima dată, nu?

1025
00:50:30,320 --> 00:50:33,200
Și ei vor trece prin
n minus 1 a doua oară, nu?

1026
00:50:33,200 --> 00:50:37,130
Și apoi ai de gând să păstreze
merge, n mina 2, etc..

1027
00:50:37,130 --> 00:50:40,210
David a făcut acest lucru într-o conferință, în cazul în care,
dacă ați adăugat la toate aceste valori,

1028
00:50:40,210 --> 00:50:48,080
ai ceva care este like-- yeah--
peste 2, care, în esență, doar reduce

1029
00:50:48,080 --> 00:50:49,784
până la n pătrat.

1030
00:50:49,784 --> 00:50:51,700
Vei obține un
fracțiune ciudat acolo.

1031
00:50:51,700 --> 00:50:53,892
Și așa știu doar că
N pătrat întotdeauna

1032
00:50:53,892 --> 00:50:55,350
are prioritate față fracțiunea.

1033
00:50:55,350 --> 00:50:58,450
Și astfel, în acest caz, cel mai rău
execuție ar fi n pătrat.

1034
00:50:58,450 --> 00:51:00,210
Dacă ar fi fost în descendent
ordine, cred că, vă

1035
00:51:00,210 --> 00:51:02,530
trebuie să facă un schimb de fiecare dată.

1036
00:51:02,530 --> 00:51:05,170
>> Care ar fi, eventual,
cel mai bun caz de execuție?

1037
00:51:05,170 --> 00:51:08,580
Să spunem doar că, în cazul în care lista a fost deja
în ordine, ceea ce ar fi runtime?

1038
00:51:08,580 --> 00:51:09,565
>> Audiența: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI Peng: E ​​n, exact.

1040
00:51:10,690 --> 00:51:11,600
Și de ce este n?

1041
00:51:11,600 --> 00:51:13,850
Audiența: Pentru că doar
Trebuie să verific fiecare dată.

1042
00:51:13,850 --> 00:51:14,770
ANDI Peng: Exact.

1043
00:51:14,770 --> 00:51:17,150
Deci, în cel mai bun Runtime posibil,
dacă această listă a fost deja

1044
00:51:17,150 --> 00:51:20,270
sorted-- să zicem 1, 2, 3, 4-- te
ar merge doar prin, ar trebui să verificați,

1045
00:51:20,270 --> 00:51:21,720
te-ar vedea, oh, toate pan afară.

1046
00:51:21,720 --> 00:51:22,636
Nu am avut de a schimba.

1047
00:51:22,636 --> 00:51:23,370
Am terminat.

1048
00:51:23,370 --> 00:51:26,500
Deci, în acest caz, e doar n
sau numărul de pași pe care tocmai ați

1049
00:51:26,500 --> 00:51:29,870
a trebuit să verifice în prima listă.

1050
00:51:29,870 --> 00:51:33,990
>> Și după, am acum a lovit
fel de inserție, în cazul în care

1051
00:51:33,990 --> 00:51:39,260
algoritmul este în esență de a împărți
l într-o porțiune sortat și nesortate.

1052
00:51:39,260 --> 00:51:42,810
Și apoi unul câte unul,
valorile sunt nesortate

1053
00:51:42,810 --> 00:51:46,880
introdus în cazul lor
poziții la începutul listei.

1054
00:51:46,880 --> 00:51:52,120
>> Deci, de exemplu, avem un
Lista de 3, 5, 2, 6, 4 nou.

1055
00:51:52,120 --> 00:51:54,750
Știm că este în prezent
nesortate că Tocmai am

1056
00:51:54,750 --> 00:51:57,030
a inceput sa caute la ea.

1057
00:51:57,030 --> 00:52:00,610
Ne ia o privire și știm că
prima valoare este sortata, nu?

1058
00:52:00,610 --> 00:52:04,190
Dacă sunteți doar uita la o serie de
mărime unul, știi că e sortate.

1059
00:52:04,190 --> 00:52:08,230
>> Deci, atunci știm că
alte patru sunt nesortate.

1060
00:52:08,230 --> 00:52:10,980
Mergem prin și vom vedea că valoarea.

1061
00:52:10,980 --> 00:52:11,730
Hai sa ne intoarcem.

1062
00:52:11,730 --> 00:52:13,130
Vezi că valoarea 5?

1063
00:52:13,130 --> 00:52:14,110
Ne ia o privire la ea.

1064
00:52:14,110 --> 00:52:15,204
Am compara cu 3.

1065
00:52:15,204 --> 00:52:17,870
Știm că este mai mare decât
3, astfel încât știm că e sortate.

1066
00:52:17,870 --> 00:52:22,940
Deci, noi știm acum că primele două
sunt sortate, iar ultimele trei nu sunt.

1067
00:52:22,940 --> 00:52:24,270
>> Ne ia o privire la două.

1068
00:52:24,270 --> 00:52:25,720
În primul rând am verifica cu 5.

1069
00:52:25,720 --> 00:52:26,700
Este mai puțin de 5?

1070
00:52:26,700 --> 00:52:27,240
Nu e.

1071
00:52:27,240 --> 00:52:29,510
Așa că trebuie să continui să cauți în jos.

1072
00:52:29,510 --> 00:52:30,940
Apoi, va verifica 2 pe 3.

1073
00:52:30,940 --> 00:52:31,850
E mai puțin de?

1074
00:52:31,850 --> 00:52:32,350
Nu.

1075
00:52:32,350 --> 00:52:35,430
Deci știi un 2 trebuie să fie introdusă
în partea din față și 3 și 5

1076
00:52:35,430 --> 00:52:38,200
ambele trebuie să fie împins afară.

1077
00:52:38,200 --> 00:52:42,190
Face acest lucru din nou cu 6 și 4.

1078
00:52:42,190 --> 00:52:48,962
Și ținem de verificare, în esență,
în cazul în care ne-am verifica, verifica, verifica.

1079
00:52:48,962 --> 00:52:51,170
Și până când este în dreapta
poziție, am un fel de doar

1080
00:52:51,170 --> 00:52:54,890
introduceți-l în poziția corectă,
care este în cazul în care numele de a venit de la.

1081
00:52:54,890 --> 00:52:59,830
>> Deci asta e doar algoritmul,
pseudocod în sine, un fel de,

1082
00:52:59,830 --> 00:53:04,990
de modul în care s-ar pune în aplicare
un fel de introducere.

1083
00:53:04,990 --> 00:53:05,954
Pseudocod este aici.

1084
00:53:05,954 --> 00:53:06,620
Totul e on-line.

1085
00:53:06,620 --> 00:53:10,720
Nu vă faceți griji dacă voi sunt
încercarea de a copia acest jos.

1086
00:53:10,720 --> 00:53:14,500
Deci, încă o dată, la fel question-- ce
ar fi cel mai bun și cel mai rău runtime

1087
00:53:14,500 --> 00:53:16,120
pentru inserarea fel?

1088
00:53:16,120 --> 00:53:17,750
Este foarte similar cu ultima întrebare.

1089
00:53:17,750 --> 00:53:20,479
Îți dau baieti, cum ar fi, 30
secunde să se gândească la aceasta, de asemenea.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Vrea cineva să
da-mi cel mai rău de execuție?

1092
00:53:50,071 --> 00:53:50,570
Da.

1093
00:53:50,570 --> 00:53:51,490
>> Audiența: n pătrat.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI Peng: E ​​n pătrat.

1095
00:53:52,573 --> 00:53:53,730
Și de ce este n pătrat?

1096
00:53:53,730 --> 00:53:57,562
>> Audiența: Deoarece în
ordine inversă, aveți

1097
00:53:57,562 --> 00:54:02,619
pentru a merge prin n ori n, care este--

1098
00:54:02,619 --> 00:54:03,660
ANDI Peng: Da, exact.

1099
00:54:03,660 --> 00:54:06,610
Deci, aceeași lucru ca și în genul bubble.

1100
00:54:06,610 --> 00:54:08,720
Dacă această listă este în
ordine descrescătoare, ești

1101
00:54:08,720 --> 00:54:11,240
Va trebui să verificați mai întâi o dată.

1102
00:54:11,240 --> 00:54:13,470
Și apoi cu fiecare
valoare suplimentară, ești

1103
00:54:13,470 --> 00:54:16,390
Va trebui să-l verifice împotriva
fiecare valoare unică, nu?

1104
00:54:16,390 --> 00:54:20,290
Și astfel totul, ai de gând să facă
un ori n trece un alt n trece, care

1105
00:54:20,290 --> 00:54:21,750
este n pătrat.

1106
00:54:21,750 --> 00:54:22,860
Ce despre cel mai bun caz?

1107
00:54:22,860 --> 00:54:24,360
Da.

1108
00:54:24,360 --> 00:54:28,840
>> Audiența: n minus 1, pentru că
Primul este deja pătrat.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI Peng: Deci, de aproape.

1110
00:54:30,270 --> 00:54:31,850
Răspunsul este, de fapt n.

1111
00:54:31,850 --> 00:54:37,189
Că în timp ce primul este
sortate, nu se poate actually--

1112
00:54:37,189 --> 00:54:38,980
ne-am avut ghinion, în
acest exemplu, că 2

1113
00:54:38,980 --> 00:54:40,930
sa întâmplat să fie cel mai mic număr.

1114
00:54:40,930 --> 00:54:43,680
Dar asta nu va fi întotdeauna cazul.

1115
00:54:43,680 --> 00:54:48,040
Dacă 2 este deja sortate la începutul
dar te uiti și există o 1 aici,

1116
00:54:48,040 --> 00:54:49,144
de 1 o va ciocni.

1117
00:54:49,144 --> 00:54:51,060
Și se va termina
prin a fi lovit oricum.

1118
00:54:51,060 --> 00:54:56,250
>> Deci, în cel mai bun caz,
este de fapt doar de gând să fie n.

1119
00:54:56,250 --> 00:54:59,090
Dacă aveți 1, 2, 3,
4, 5, 6, 7, 8, ești

1120
00:54:59,090 --> 00:55:00,940
de gând să ruleze prin
că întreaga listă dată

1121
00:55:00,940 --> 00:55:03,430
pentru a verifica pentru a vedea dacă totul e în regulă.

1122
00:55:03,430 --> 00:55:07,390
Este toată lumea clar pe care rulează
ori de selecție, precum și?

1123
00:55:07,390 --> 00:55:09,960
Știu că voi prin
acestea foarte repede.

1124
00:55:09,960 --> 00:55:13,330
Dar știu doar că, dacă știți
concepte generale, ar trebui să fie bun.

1125
00:55:13,330 --> 00:55:16,070
BINE.

1126
00:55:16,070 --> 00:55:19,790
Așa că voi da doar voi poate, cum ar fi,
un minut pentru a vorbi cu vecinii tăi

1127
00:55:19,790 --> 00:55:21,890
asupra a ceea ce sunt doar câteva
din diferențele principale

1128
00:55:21,890 --> 00:55:23,540
între aceste tipuri de tipuri.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Vom trece peste asta în curând.

1131
00:56:25,570 --> 00:56:26,444
Audiența: Oh, OK.

1132
00:56:26,444 --> 00:56:27,320
ANDI Peng: Da.

1133
00:56:27,320 --> 00:56:28,380
BINE.

1134
00:56:28,380 --> 00:56:33,420
Rece, să se întrunească din nou ca o clasă.

1135
00:56:33,420 --> 00:56:34,330
BINE.

1136
00:56:34,330 --> 00:56:37,579
Deci asta a fost un fel de
întrebare deschisă, în sensul

1137
00:56:37,579 --> 00:56:39,120
că există o mulțime de răspunsuri la ele.

1138
00:56:39,120 --> 00:56:40,746
Și vom trece peste unele dintre ele pe scurt.

1139
00:56:40,746 --> 00:56:43,411
Am vrut doar să te voi
gândesc la ceea ce diferențiază

1140
00:56:43,411 --> 00:56:44,530
toate cele trei tipuri de soiuri.

1141
00:56:44,530 --> 00:56:47,440
Și am auzit, de asemenea, o mare
question-- ce merge sort face?

1142
00:56:47,440 --> 00:56:50,110
Marea întrebare, pentru că asta e
ceea ce ne acoperă următor.

1143
00:56:50,110 --> 00:56:52,850
>> Deci, merge sort este
un fel care funcționează

1144
00:56:52,850 --> 00:56:56,100
foarte diferit de celelalte tipuri.

1145
00:56:56,100 --> 00:56:58,180
După cum voi puteți see--
a făcut David asta demo

1146
00:56:58,180 --> 00:57:01,130
unde a avut toate rece
zgomote de a vedea cum merge

1147
00:57:01,130 --> 00:57:04,010
fel a fugit, cum ar fi, infinit
mai repede decât celelalte două tipuri?

1148
00:57:04,010 --> 00:57:04,510
BINE.

1149
00:57:04,510 --> 00:57:07,580
Deci asta pentru ca merge
pune în aplicare un fel care se divid

1150
00:57:07,580 --> 00:57:11,020
și cuceri concept care ne-am
a vorbit despre o mulțime de curs.

1151
00:57:11,020 --> 00:57:14,550
În acest sens, care ne place să lucreze
mai inteligent, nu mai greu, atunci când împărțiți

1152
00:57:14,550 --> 00:57:18,120
și cuceri probleme, și le sparge
jos, iar apoi le-a pus împreună,

1153
00:57:18,120 --> 00:57:19,930
lucruri bune se întâmplă întotdeauna.

1154
00:57:19,930 --> 00:57:21,960
>> Deci felul în care merge
Lucrari de sortare, în esență,

1155
00:57:21,960 --> 00:57:24,660
este faptul că împarte o
matrice nesortate în jumătate.

1156
00:57:24,660 --> 00:57:26,500
Și apoi are două jumătăți de tablouri.

1157
00:57:26,500 --> 00:57:28,220
Și se sortează doar cele două jumătăți.

1158
00:57:28,220 --> 00:57:31,750
Doar ține împărțirea în jumătate, în
pe jumătate, în jumătate până când totul este sortată

1159
00:57:31,750 --> 00:57:33,680
și apoi recursiv
pune totul împreună.

1160
00:57:33,680 --> 00:57:36,550
>> Așa că e foarte abstract.

1161
00:57:36,550 --> 00:57:38,750
Deci, aceasta este doar un pic de pseudocod.

1162
00:57:38,750 --> 00:57:41,040
Asta face sens în
modul în care aceasta rulează?

1163
00:57:41,040 --> 00:57:43,870
Deci, hai să spunem că aveți o
matrice de n elemente, nu?

1164
00:57:43,870 --> 00:57:45,450
Dacă n este mai mică de 2, vă puteți întoarce.

1165
00:57:45,450 --> 00:57:49,040
Pentru că știi că dacă e
doar un singur lucru, acesta trebuie să fie sortate.

1166
00:57:49,040 --> 00:57:52,600
Altfel, sortați jumătatea stângă,
și apoi sortați jumătatea din dreapta,

1167
00:57:52,600 --> 00:57:54,140
și apoi îmbinați.

1168
00:57:54,140 --> 00:57:56,979
>> Deci, în timp care arata foarte usor,
în realitate, gândindu-e

1169
00:57:56,979 --> 00:58:00,270
un fel de dificil. Pentru că ești ca,
Ei bine, asta e un fel de a rula pe sine.

1170
00:58:00,270 --> 00:58:00,769
Dreapta?

1171
00:58:00,769 --> 00:58:02,430
Se rulează pe sine.

1172
00:58:02,430 --> 00:58:05,479
Deci, în acest sens, David atins
la recursivitate în clasa.

1173
00:58:05,479 --> 00:58:07,270
Și că este un concept
vom vorbi despre mai mult.

1174
00:58:07,270 --> 00:58:11,430
Este că acest fapt, aceste două linii
aici, de fapt, este doar programul

1175
00:58:11,430 --> 00:58:13,860
spunandu-i sa se rula
cu intrare diferite.

1176
00:58:13,860 --> 00:58:17,230
Deci, mai degrabă decât se rula cu
totalitatea n elemente,

1177
00:58:17,230 --> 00:58:20,530
puteti rupe în jos, în
jumătate stânga și jumătatea din dreapta

1178
00:58:20,530 --> 00:58:22,680
și apoi executați din nou.

1179
00:58:22,680 --> 00:58:26,050
>> Și apoi ne vom uita la ea vizual,
pentru că eu sunt un elev vizual.

1180
00:58:26,050 --> 00:58:27,270
Acesta funcționează mai bine pentru mine.

1181
00:58:27,270 --> 00:58:29,890
Deci ne vom uita la un exemplu vizual aici.

1182
00:58:29,890 --> 00:58:36,237
>> Să presupunem că avem o gamă, șase
Elemente, 3, 5, 2, 6, 4, 1, nu sortate.

1183
00:58:36,237 --> 00:58:37,820
Bine, există o mulțime de pe aceasta pagina.

1184
00:58:37,820 --> 00:58:43,179
Deci, dacă voi sa te uiti la
primul pas aici, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
puteti împărțită în jumătate.

1186
00:58:44,220 --> 00:58:45,976
Aveți 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Știi că aceste tu aren't--
Nu știu dacă acestea sunt sortate sau nu,

1188
00:58:48,850 --> 00:58:52,517
astfel încât să păstrați de rupere le în jos, în jumătate,
în jumătate, în jumătate, până în cele din urmă,

1189
00:58:52,517 --> 00:58:53,600
ai doar un element.

1190
00:58:53,600 --> 00:58:56,790
Și un element este întotdeauna sortate, nu?

1191
00:58:56,790 --> 00:59:01,560
>> Deci, noi știm că 3, 5, 2, 4, 6,
1, prin ele însele, sunt sortate.

1192
00:59:01,560 --> 00:59:05,870
Și acum putem le-a pus din nou împreună.

1193
00:59:05,870 --> 00:59:07,510
Deci, știm 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Am pus cele impreuna.

1195
00:59:08,510 --> 00:59:09,617
Știm că e sortat.

1196
00:59:09,617 --> 00:59:10,450
Cele 2 anii încă acolo.

1197
00:59:10,450 --> 00:59:11,830
Putem pune 4 și 6 împreună.

1198
00:59:11,830 --> 00:59:13,996
Știm că ce se sortate,
asa ca am pus ca impreuna.

1199
00:59:13,996 --> 00:59:14,940
Iar 1 este acolo.

1200
00:59:14,940 --> 00:59:18,720
>> Și apoi doar te uiți la
aceste două jumătăți aici.

1201
00:59:18,720 --> 00:59:21,300
Ai 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Puteți compara doar
începând de tot.

1203
00:59:23,465 --> 00:59:26,340
Pentru că știi că acest lucru este sortate
și știi că e sortate.

1204
00:59:26,340 --> 00:59:29,360
Deci atunci nu măcar nu trebuie să
compara 5, comparați doar 3.

1205
00:59:29,360 --> 00:59:32,070
Iar 2 este mai mic de 3, așa
Știi 2 trebuie să în cele din urmă.

1206
00:59:32,070 --> 00:59:33,120
>> Același lucru acolo.

1207
00:59:33,120 --> 00:59:34,740
De 1 trebuie să meargă aici.

1208
00:59:34,740 --> 00:59:37,330
Și când te duci pentru a pune
aceste două valori împreună,

1209
00:59:37,330 --> 00:59:39,950
știți că acest lucru este sortati si
știți că este sortată.

1210
00:59:39,950 --> 00:59:43,240
Deci atunci 1 și
2, 1 să fie mai mică de 2.

1211
00:59:43,240 --> 00:59:45,570
Care vă spune că 1
ar trebui să meargă la sfârșitul acestui

1212
00:59:45,570 --> 00:59:47,480
fără măcar să se uite la 3 sau 5.

1213
00:59:47,480 --> 00:59:50,100
Și apoi 4, puteți doar
verifica, merge chiar aici.

1214
00:59:50,100 --> 00:59:51,480
Nu trebuie să se uite la 5.

1215
00:59:51,480 --> 00:59:52,570
Același lucru cu 6.

1216
00:59:52,570 --> 00:59:55,860
Știi că 6-- doar
nu are nevoie să fie privit.

1217
00:59:55,860 --> 00:59:57,870
>> Și astfel, în acest fel, ești
doar te de economisire

1218
00:59:57,870 --> 00:59:59,526
o mulțime de pași atunci când sunteți comparat.

1219
00:59:59,526 --> 01:00:02,150
Nu trebuie să compare fiecare
Element împotriva altor elemente.

1220
01:00:02,150 --> 01:00:05,230
Trebuie doar compara cu cele
care trebuie să-l compare cu.

1221
01:00:05,230 --> 01:00:06,870
Deci, asta e un fel de concept abstract.

1222
01:00:06,870 --> 01:00:10,540
Nu vă faceți griji dacă nu este
destul de tine lovind încă dreptate.

1223
01:00:10,540 --> 01:00:14,740
Dar, în general, aceasta este
cum un fel de lucrări de îmbinare.

1224
01:00:14,740 --> 01:00:17,750
Întrebări, întrebări rapide,
înainte de a mă muta pe?

1225
01:00:17,750 --> 01:00:18,550
Da.

1226
01:00:18,550 --> 01:00:22,230
>> Audiența: Deci ați spus că luați
pozițiile 1, iar apoi de 4, și 6

1227
01:00:22,230 --> 01:00:23,860
și le-a pus în.

1228
01:00:23,860 --> 01:00:26,800
Deci, nu sunt those-- nu sunt
te uiți la ele

1229
01:00:26,800 --> 01:00:28,544
ca elemente separate, nu în ansamblul său?

1230
01:00:28,544 --> 01:00:29,210
ANDI Peng: Da.

1231
01:00:29,210 --> 01:00:32,020
Deci, ce se întâmplă
este că de fapt

1232
01:00:32,020 --> 01:00:33,650
creează o gamă de brand nou.

1233
01:00:33,650 --> 01:00:36,690
Astfel încât să știți că, de aici, am
două tablouri de dimensiuni 3, nu?

1234
01:00:36,690 --> 01:00:39,600
Deci știți că matrice mea sortat
trebuie să aibă șase elemente.

1235
01:00:39,600 --> 01:00:42,270
Deci, doar să creați un
nouă sumă de memorie.

1236
01:00:42,270 --> 01:00:44,270
Deci ești un fel de
fiind risipă de memorie,

1237
01:00:44,270 --> 01:00:46,186
dar asta nu contează
pentru că este atât de mic.

1238
01:00:46,186 --> 01:00:48,590
Deci te uiti la 1
și te uiți la 2.

1239
01:00:48,590 --> 01:00:50,770
Și știi că 1 este mai mică de 2.

1240
01:00:50,770 --> 01:00:53,840
Deci știi că ar trebui să meargă în 1
începutul tuturor celor.

1241
01:00:53,840 --> 01:00:55,850
>> Nici măcar nu trebuie să
uita-te la 3 și 5.

1242
01:00:55,850 --> 01:00:57,400
Deci știi 1 merge acolo.

1243
01:00:57,400 --> 01:00:59,300
Apoi, va taie practic pe 1.

1244
01:00:59,300 --> 01:01:00,370
E, cum ar fi, mort pentru noi.

1245
01:01:00,370 --> 01:01:03,690
Apoi avem doar 2,
3, 5, și apoi 4 și 6.

1246
01:01:03,690 --> 01:01:06,270
Și apoi știi asta,
compara 4 și 2,

1247
01:01:06,270 --> 01:01:07,560
oh, 2 ar trebui să meargă acolo.

1248
01:01:07,560 --> 01:01:09,685
Deci ai plop 2 jos, ai taie.

1249
01:01:09,685 --> 01:01:12,060
Deci, atunci doar ai 3
și 5 în 4 și 6.

1250
01:01:12,060 --> 01:01:14,650
Și vă păstrați tocare-l
până când le-a pus în matrice.

1251
01:01:14,650 --> 01:01:17,110
>> Audiența: Deci tu ești doar mereu
compararea [neauzit]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI Peng: Exact.

1253
01:01:17,710 --> 01:01:19,590
Deci, în acest sens, ești
doar compararea, în esență,

1254
01:01:19,590 --> 01:01:21,240
un număr de împotriva celeilalte numărul.

1255
01:01:21,240 --> 01:01:22,990
Și pentru că știi
că este sortate, tu

1256
01:01:22,990 --> 01:01:24,350
Nu trebuie să se uite prin
toate numerele.

1257
01:01:24,350 --> 01:01:25,870
Trebuie doar să te uiți la prima.

1258
01:01:25,870 --> 01:01:27,582
Și apoi puteți plop doar
le în jos, pentru că știi

1259
01:01:27,582 --> 01:01:29,640
din care fac parte în cazul în care au nevoie să aparțină.

1260
01:01:29,640 --> 01:01:31,030
Da.

1261
01:01:31,030 --> 01:01:32,920
Buna intrebare.

1262
01:01:32,920 --> 01:01:35,290
>> Și apoi, dacă vreunul dintre voi
sunt un pic ambițios,

1263
01:01:35,290 --> 01:01:38,660
nu ezitați să se uite la acest cod.

1264
01:01:38,660 --> 01:01:40,680
Aceasta este de fapt
implementarea fizică

1265
01:01:40,680 --> 01:01:42,150
de modul în care ne-ar scrie merge sort.

1266
01:01:42,150 --> 01:01:44,070
Și puteți vedea, este foarte scurt.

1267
01:01:44,070 --> 01:01:46,310
Dar ideile din spatele
aceasta sunt destul de complexe.

1268
01:01:46,310 --> 01:01:50,865
Deci, dacă vă simțiți ca de desen asta
în temele seara asta, nu ezitați să.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> BINE.

1271
01:01:54,740 --> 01:01:58,070
David, de asemenea, a trecut acest lucru în curs.

1272
01:01:58,070 --> 01:02:00,660
Care sunt cel mai bun caz
runtime, cele mai grave runtime caz,

1273
01:02:00,660 --> 01:02:05,680
și runtime așteptate ale merge fel?

1274
01:02:05,680 --> 01:02:07,260
Cateva secunde de a gândi.

1275
01:02:07,260 --> 01:02:11,198
Acest lucru este destul de greu, dar un fel de
intuitiv dacă te gândești la asta.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
In regula.

1278
01:02:23,054 --> 01:02:25,269
>> Audiența: Este cel mai rău caz, n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI Peng: Exact.

1280
01:02:26,060 --> 01:02:29,380
Și de ce este n log n.

1281
01:02:29,380 --> 01:02:32,230
>> Audiența: Nu este pentru că
devine exponențial rapid,

1282
01:02:32,230 --> 01:02:35,390
deci este ca o funcție de care
în loc de a fi pur și simplu n

1283
01:02:35,390 --> 01:02:37,529
pătrat sau ceva?

1284
01:02:37,529 --> 01:02:38,320
ANDI Peng: Exact.

1285
01:02:38,320 --> 01:02:40,750
Deci motivul pentru care
rulare pe acest lucru este n Conectare

1286
01:02:40,750 --> 01:02:44,310
n este because-- ceea ce ești tu
face în toate aceste etape?

1287
01:02:44,310 --> 01:02:46,190
Ești doar o tocare în jumătate, nu?

1288
01:02:46,190 --> 01:02:48,750
Și așa că atunci când că facem
jurnal, tot ceea ce face

1289
01:02:48,750 --> 01:02:53,150
este divizarea o problemă în jumătate,
în jumătate, în jumătate, în mai multe reprize.

1290
01:02:53,150 --> 01:02:56,430
Și în acest sens, puteți fel
de a elimina modelul liniar

1291
01:02:56,430 --> 01:02:57,510
pe care le-am folosit.

1292
01:02:57,510 --> 01:03:00,254
Pentru că, atunci când taie
lucruri în jumătate, este un jurnal.

1293
01:03:00,254 --> 01:03:02,420
Asta e doar matematic
mod de a reprezenta aceasta.

1294
01:03:02,420 --> 01:03:06,310
>> Și apoi în cele din urmă, la sfârșitul anului, ești
făcând doar o ultimă trecere prin

1295
01:03:06,310 --> 01:03:07,930
pentru a pune toate acestea în ordine, nu?

1296
01:03:07,930 --> 01:03:10,330
Și deci, dacă aveți doar să
verifica un singur lucru, care este n.

1297
01:03:10,330 --> 01:03:13,420
Și așa ești un fel de
înmulțirea cele două împreună.

1298
01:03:13,420 --> 01:03:17,660
Deci e ca si cum ai că finală
verifica N aici cu un jurnal de n

1299
01:03:17,660 --> 01:03:18,390
Aici sus.

1300
01:03:18,390 --> 01:03:21,060
Și dacă multiplica
le, care a n log n.

1301
01:03:21,060 --> 01:03:26,100
>> Și astfel cel mai bun caz și cel mai rău
caz și de așteptat sunt toate n log n.

1302
01:03:26,100 --> 01:03:27,943
Este, de asemenea ca un alt fel.

1303
01:03:27,943 --> 01:03:30,090
E ca si cum un fel de selecție
în sensul că acesta

1304
01:03:30,090 --> 01:03:32,131
nu conteaza ceea ce dvs.
Lista este, e doar de gând

1305
01:03:32,131 --> 01:03:34,801
să facă același lucru de fiecare data.

1306
01:03:34,801 --> 01:03:35,300
BINE.

1307
01:03:35,300 --> 01:03:39,950
Deci, ca voi poate vedea, chiar dacă
soiurile pe care le-am trecut through-- n

1308
01:03:39,950 --> 01:03:41,660
pătrat, nu e foarte eficient.

1309
01:03:41,660 --> 01:03:47,060
Și chiar acest n log n este
nu cel mai eficient.

1310
01:03:47,060 --> 01:03:49,720
Dacă voi sunt curioși,
există mecanisme de sortare

1311
01:03:49,720 --> 01:03:54,310
care sunt atât de eficient, care sunt
aproape în esență, plat în timpul rulării.

1312
01:03:54,310 --> 01:03:55,420
>> Ai niște log n lui.

1313
01:03:55,420 --> 01:03:58,190
Ai niște log log n lui.

1314
01:03:58,190 --> 01:04:00,330
Noi nu atingeți asupra lor
în această clasă acum.

1315
01:04:00,330 --> 01:04:02,663
Dar dacă voi sunteți curioși,
nu ezitați să Google, ceea ce este

1316
01:04:02,663 --> 01:04:04,392
cele mai eficiente mecanisme de sortare.

1317
01:04:04,392 --> 01:04:06,350
Nu știu, există
unele foarte amuzant,

1318
01:04:06,350 --> 01:04:09,860
like-- există unele foarte
cele amuzante pe care oamenii fac.

1319
01:04:09,860 --> 01:04:12,210
Și te întrebi cum
gândit vreodată la asta.

1320
01:04:12,210 --> 01:04:15,730
Deci Google, dacă aveți ceva de rezervă
timp, pe, care sunt câteva modalități amuzante

1321
01:04:15,730 --> 01:04:17,730
că people-- precum și
oameni ways-- eficiente

1322
01:04:17,730 --> 01:04:20,371
au fost în măsură să pună în aplicare felul.

1323
01:04:20,371 --> 01:04:20,870
BINE.

1324
01:04:20,870 --> 01:04:22,880
Și aici este doar un grafic la îndemână pic.

1325
01:04:22,880 --> 01:04:26,850
Știu că voi toți, înainte de asta test 0,
va fi în camera ta, probabil, încearcă

1326
01:04:26,850 --> 01:04:27,960
să memoreze asta.

1327
01:04:27,960 --> 01:04:30,940
Așa că e frumos acolo pentru voi.

1328
01:04:30,940 --> 01:04:37,120
Doar nu uitați că logica made--
de ce aceste numere au fost loc.

1329
01:04:37,120 --> 01:04:39,870
Dacă sunteți mereu pierdut, face doar
vă că știți ce tipuri sunt.

1330
01:04:39,870 --> 01:04:40,820
Și puteți rula prin
le în mintea ta

1331
01:04:40,820 --> 01:04:42,903
să dau seama de ce cei
răspunsurile sunt aceste răspunsuri.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> In regula.

1334
01:04:47,600 --> 01:04:49,680
Deci vom să se mute
pe, în cele din urmă, la căutarea.

1335
01:04:49,680 --> 01:04:51,638
Pentru că așa cum cei dintre voi
care au citit PSET,

1336
01:04:51,638 --> 01:04:55,175
Căutarea este, de asemenea, parte din
seturi problemă din această săptămână.

1337
01:04:55,175 --> 01:04:57,300
Vi se va cere să pună în aplicare
două tipuri de căutări.

1338
01:04:57,300 --> 01:05:00,070
Una dintre ele este o căutare liniară și
unul este o căutare binară.

1339
01:05:00,070 --> 01:05:01,760
>> Deci căutarea liniară este destul de ușor.

1340
01:05:01,760 --> 01:05:04,070
Tu vrei să element de căutare
unei liste pentru a vedea dacă-l.

1341
01:05:04,070 --> 01:05:05,444
Trebuie doar să itera prin.

1342
01:05:05,444 --> 01:05:08,170
Și dacă este egal cu ceva,
puteți doar întoarce, nu?

1343
01:05:08,170 --> 01:05:10,890
Dar cel pe care suntem cel mai
interesat în a vorbi despre

1344
01:05:10,890 --> 01:05:14,550
este binar de căutare, dreapta, care este
diviza și cuceri care mecanism

1345
01:05:14,550 --> 01:05:18,190
David a fost să demonstreze în curs.

1346
01:05:18,190 --> 01:05:20,810
>> Amintiți-vă de exemplu cartea de telefon
că el continuă creșterea,

1347
01:05:20,810 --> 01:05:23,960
cel care a luptat de tip
un pic pe acest an trecut,

1348
01:05:23,960 --> 01:05:27,530
în cazul în care împarte problema în jumătate,
în jumătate, în jumătate, din nou și din nou,

1349
01:05:27,530 --> 01:05:30,730
până când găsiți ceea ce căutați pentru?

1350
01:05:30,730 --> 01:05:33,727
Și le-ați luat
rulare de la fel de bine.

1351
01:05:33,727 --> 01:05:35,810
Și puteți vedea, e
mult mai eficiente

1352
01:05:35,810 --> 01:05:39,080
decât orice alt tip de căutare.

1353
01:05:39,080 --> 01:05:41,880
>> Deci felul în care ne-ar merge cu privire la
de punere în aplicare o căutare binară

1354
01:05:41,880 --> 01:05:46,510
este, dacă am fi avut o matrice,
index 0 până la 6, șapte elemente,

1355
01:05:46,510 --> 01:05:49,790
putem să ne uităm la mijloc, right--
Ne pare rău, în cazul în care întrebarea noastră first--

1356
01:05:49,790 --> 01:05:53,840
dacă vrem să ne punem întrebarea de, nu
matrice conține elementul de 7,

1357
01:05:53,840 --> 01:05:56,840
Evident, fiind oameni, și având
o astfel de matrice mic, este ușor pentru noi

1358
01:05:56,840 --> 01:05:58,210
să spun da.

1359
01:05:58,210 --> 01:06:05,750
Dar modul de a pune în aplicare un binar
căutare ar fi să se uite la mijloc.

1360
01:06:05,750 --> 01:06:08,020
>> Știm că indicele 3 este
mijloc, pentru că noi

1361
01:06:08,020 --> 01:06:09,270
știu că sunt șapte elemente.

1362
01:06:09,270 --> 01:06:10,670
Ce 7 împărțit la 2?

1363
01:06:10,670 --> 01:06:12,850
Puteți taie la plus 1.

1364
01:06:12,850 --> 01:06:14,850
Ai 3 în mijloc.

1365
01:06:14,850 --> 01:06:17,590
Deci, este matrice de 3 egală cu 7?

1366
01:06:17,590 --> 01:06:18,900
Nu este, nu?

1367
01:06:18,900 --> 01:06:21,050
Dar putem face un cuplu de controale.

1368
01:06:21,050 --> 01:06:25,380
Este serie de 3 mai mică de 7 sau
este matrice de 3 mai mare decât 7?

1369
01:06:25,380 --> 01:06:27,240
>> Și știm că este mai puțin de 7.

1370
01:06:27,240 --> 01:06:30,259
Deci, noi știm că, oh, aceasta trebuie să
să nu fie în jumătatea stângă.

1371
01:06:30,259 --> 01:06:32,300
Știm că trebuie să fie
în jumătatea dreaptă, nu?

1372
01:06:32,300 --> 01:06:34,662
Astfel încât să putem taie doar de pe jumătate din matrice.

1373
01:06:34,662 --> 01:06:36,370
Noi nu măcar nu trebuie să
mai uita-te la ea.

1374
01:06:36,370 --> 01:06:38,711
Pentru ca stim ca
jumătate din problem-- noastre

1375
01:06:38,711 --> 01:06:41,210
știm că răspunsul este în
jumătatea dreaptă a problemei noastre.

1376
01:06:41,210 --> 01:06:42,580
Deci, ne-am uita la asta acum.

1377
01:06:42,580 --> 01:06:44,860
>> Deci, acum ne uităm la
mijlocul a ceea ce a mai rămas.

1378
01:06:44,860 --> 01:06:46,880
Că indicele de 5.

1379
01:06:46,880 --> 01:06:50,200
Noi facem din nou aceeași verificarea
și vom vedea că este mai mic.

1380
01:06:50,200 --> 01:06:52,050
Deci, ne uităm la stânga pe care.

1381
01:06:52,050 --> 01:06:53,430
Și apoi vom vedea că check.

1382
01:06:53,430 --> 01:06:57,600
Este valoarea la matrice
index 4 egal cu 7?

1383
01:06:57,600 --> 01:06:58,260
Este.

1384
01:06:58,260 --> 01:07:03,580
Deci, putem întoarce adevărat, pentru că
am gasit valoarea în lista noastră.

1385
01:07:03,580 --> 01:07:06,738
Are modul în care am trecut prin
care face sens pentru toată lumea?

1386
01:07:06,738 --> 01:07:08,760
BINE.

1387
01:07:08,760 --> 01:07:11,670
Îți dau baieti poate, cum ar fi,
trei, patru minute pentru a descoperi

1388
01:07:11,670 --> 01:07:13,270
Cum să pseudocod acest.

1389
01:07:13,270 --> 01:07:18,070
>> Deci imaginați-vă-am rugat să scrie o
funcție numită căutare (), care a revenit

1390
01:07:18,070 --> 01:07:20,640
o valoare, o valoare Boolean,
care a fost adevarat sau false-- ca,

1391
01:07:20,640 --> 01:07:22,970
adevărat dacă ai găsit
valoare, false, dacă nu.

1392
01:07:22,970 --> 01:07:25,230
Și apoi ai fost
a trecut în valoarea pe care

1393
01:07:25,230 --> 01:07:28,410
căutați în valori, care
este array-- oh, mi-am pus cu siguranta

1394
01:07:28,410 --> 01:07:29,410
că în locul nepotrivit.

1395
01:07:29,410 --> 01:07:29,580
BINE.

1396
01:07:29,580 --> 01:07:31,829
Oricum, faptul că ar trebui să aibă
fost în partea dreaptă a valorilor.

1397
01:07:31,829 --> 01:07:36,280
Și apoi int n este numărul
de elemente în care matrice.

1398
01:07:36,280 --> 01:07:39,430
Cum te-ai duce despre încercarea
să pseudocod această problemă în?

1399
01:07:39,430 --> 01:07:41,630
Îți dau tipi ca
trei minute pentru a face asta.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Nu, cred că nu e only--
Da, nu e unul chiar aici.

1402
01:08:02,595 --> 01:08:03,261
Audiența: Pot?

1403
01:08:03,261 --> 01:08:04,388
ANDI Peng: Da, am ai.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Este că de lucru?

1406
01:08:11,050 --> 01:08:12,290
Bine, in regula.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> BINE.

1409
01:10:44,720 --> 01:10:47,630
Toate baieti dreapta, suntem
gând să-l țină în frâu.

1410
01:10:47,630 --> 01:10:49,730
BINE.

1411
01:10:49,730 --> 01:10:54,020
Deci presupunem că avem acest minunat
mic tablou cu valori N în ea.

1412
01:10:54,020 --> 01:10:55,170
Nu am trage linii.

1413
01:10:55,170 --> 01:10:58,649
Dar cum ar fi să mergem despre
încercarea de a scrie acest lucru?

1414
01:10:58,649 --> 01:11:00,440
Nimeni nu vrea să
da-mi prima linie?

1415
01:11:00,440 --> 01:11:02,814
Dacă doriți să-mi dai
prima linie de acest pseudocod.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> Audiența: [inaudibil]

1418
01:11:08,430 --> 01:11:10,138
Audiența: Ai vrea
a repeta through--

1419
01:11:10,138 --> 01:11:11,094
Audiența: Doar un alt pentru buclă?

1420
01:11:11,094 --> 01:11:11,760
Audiența: -Pentru.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI Peng: Deci asta e un pic complicat.

1423
01:11:17,780 --> 01:11:23,130
Gândiți about-- vrei
a continua să fie difuzate această buclă

1424
01:11:23,130 --> 01:11:27,950
de peste si peste din nou, până când?

1425
01:11:27,950 --> 01:11:30,819
>> Audiența: Până la [neauzit]
valoare este egală cu această valoare.

1426
01:11:30,819 --> 01:11:31,610
ANDI Peng: Exact.

1427
01:11:31,610 --> 01:11:33,900
Astfel încât să puteți de fapt doar write--
putem chiar simplifica mai mult.

1428
01:11:33,900 --> 01:11:35,630
Putem face doar o buclă în timp ce, nu?

1429
01:11:35,630 --> 01:11:39,380
Astfel încât să puteți avea doar loop--
știm că este un timp.

1430
01:11:39,380 --> 01:11:42,850
Dar pentru acum, am de gând
a spune "buclă" - prin ce?

1431
01:11:42,850 --> 01:11:46,640
Buclă until-- ceea ce este
condiția noastră se încheie?

1432
01:11:46,640 --> 01:11:47,510
Cred că am auzit.

1433
01:11:47,510 --> 01:11:48,530
Am auzit pe cineva spun.

1434
01:11:48,530 --> 01:11:51,255
>> Audiența: Valorile egal de mijloc.

1435
01:11:51,255 --> 01:11:52,255
ANDI Peng: spune din nou.

1436
01:11:52,255 --> 01:11:54,470
Audiența: Sau, până la
Valoarea sunteți în căutare

1437
01:11:54,470 --> 01:11:58,470
este egală cu valoarea de mijloc.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI Peng: Ce se întâmplă dacă nu e acolo?

1439
01:12:00,280 --> 01:12:03,113
Ce se întâmplă dacă valoarea pe care căutați
pentru că nu este, de fapt, în acest tablou?

1440
01:12:03,113 --> 01:12:05,890
Audiența: Reveniți 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI Peng: Dar ce vrem să
bucla până dacă avem o afecțiune?

1442
01:12:08,850 --> 01:12:09,350
Da.

1443
01:12:09,350 --> 01:12:11,239
>> Audiența: Până când nu este doar o valoare?

1444
01:12:11,239 --> 01:12:13,530
ANDI Peng: Puteți buclă
until-- astfel încât să știți că ești

1445
01:12:13,530 --> 01:12:15,714
va avea o valoare maximă, nu?

1446
01:12:15,714 --> 01:12:18,130
Și știi că vei
pentru a avea o valoare min, nu?

1447
01:12:18,130 --> 01:12:20,379
Pentru că, de asemenea, că e ceva
Am uitat să spun înainte,

1448
01:12:20,379 --> 01:12:22,640
că ceva care este
critice despre căutare binară

1449
01:12:22,640 --> 01:12:24,182
este faptul că matrice dvs. este deja sortate.

1450
01:12:24,182 --> 01:12:26,973
Pentru ca nu exista nici o modalitate de a face
acest lucru, dacă acestea sunt valori doar aleatoare.

1451
01:12:26,973 --> 01:12:29,190
Nu știu dacă e nimeni
mai mare decât celălalt, nu?

1452
01:12:29,190 --> 01:12:32,720
>> Astfel încât să știți că Max și
min tale sunt aici, nu?

1453
01:12:32,720 --> 01:12:35,590
Dacă aveți de gând să fie de reglare
max în minute tale si mid--

1454
01:12:35,590 --> 01:12:38,470
Să presupunem dvs.
Valoarea mijlocul lunii este here-- corect

1455
01:12:38,470 --> 01:12:43,910
ai de gând să practic
buclă până minimă este

1456
01:12:43,910 --> 01:12:47,510
aproximativ la fel ca max ta, dreapta, sau
în cazul în care max nu este la fel ca dumneavoastră min.

1457
01:12:47,510 --> 01:12:48,040
Dreapta?

1458
01:12:48,040 --> 01:12:51,340
Pentru că atunci când acest lucru se întâmplă, știi că
în cele din urmă le-ați lovit de aceeași valoare.

1459
01:12:51,340 --> 01:12:59,135
Deci vrei să bucla până min dvs.
este mai mică sau egală sa-- oops,

1460
01:12:59,135 --> 01:13:01,510
Nu mai mică sau egală cu,
în altă parte around-- max este.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Făcut asta face sens?

1463
01:13:16,160 --> 01:13:18,810
Am luat câteva încearcă să acest drept.

1464
01:13:18,810 --> 01:13:21,869
Dar buclă până când valoarea ta max
este, în esență, aproape mai puțin

1465
01:13:21,869 --> 01:13:23,410
mic sau egal cu minimum, nu?

1466
01:13:23,410 --> 01:13:25,201
Asta e atunci când știi
care le-ați convergente.

1467
01:13:25,201 --> 01:13:29,290
Audiența: Când doriți maxim dvs.
Valoarea fie mai mică decât valoarea minimă?

1468
01:13:29,290 --> 01:13:31,040
ANDI Peng: Dacă vă păstrați
ajustându-l, care

1469
01:13:31,040 --> 01:13:32,380
este ceea ce vom
să faci în acest sens.

1470
01:13:32,380 --> 01:13:33,460
Are sens?

1471
01:13:33,460 --> 01:13:35,750
Minime și maxime sunt doar
numere întregi care sunt, probabil, ne

1472
01:13:35,750 --> 01:13:39,260
O să doriți să creați pentru a menține
evidența unde căutați.

1473
01:13:39,260 --> 01:13:41,790
Deoarece există matrice
indiferent de ceea ce facem.

1474
01:13:41,790 --> 01:13:45,030
Cum ar fi, nu suntem de fapt fizic
tocare de pe matrice, nu?

1475
01:13:45,030 --> 01:13:47,261
Noi doar ajustarea
în cazul în care ne uităm.

1476
01:13:47,261 --> 01:13:48,136
Are sens?

1477
01:13:48,136 --> 01:13:48,472
>> Audiența: Da.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI Peng: OK.

1479
01:13:49,110 --> 01:13:57,090
Deci, dacă asta e condiția pentru bucla noastră,
ceea ce vrem interiorul această buclă?

1480
01:13:57,090 --> 01:13:58,700
Ce vom fi doresc să facă?

1481
01:13:58,700 --> 01:14:02,390
Deci acum, avem
max si un min, drept,

1482
01:14:02,390 --> 01:14:04,962
probabil a creat aici pe undeva.

1483
01:14:04,962 --> 01:14:07,170
Vom dori, probabil,
pentru a găsi un mijloc, nu?

1484
01:14:07,170 --> 01:14:08,450
Cum vom fi
în stare să găsească mijlocul?

1485
01:14:08,450 --> 01:14:09,491
Care este mathematical--

1486
01:14:09,491 --> 01:14:11,079
Audiența: Max plus min împărțit la 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI Peng: Exact.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Are sens?

1490
01:14:21,620 --> 01:14:25,780
Și nu voi vedea ce am
nu doar use-- ce am făcut asta

1491
01:14:25,780 --> 01:14:27,850
în loc de a face doar n împărțit la 2?

1492
01:14:27,850 --> 01:14:30,310
Este pentru că n este o valoare
care va rămâne la fel.

1493
01:14:30,310 --> 01:14:30,979
Dreapta?

1494
01:14:30,979 --> 01:14:34,020
Dar, așa cum ne-am adapta minim nostru și
valori maxime, ei vor să se schimbe.

1495
01:14:34,020 --> 01:14:36,040
Și, ca urmare, de mijloc nostru
se va schimba prea.

1496
01:14:36,040 --> 01:14:37,873
Deci, de aceea ne-o dorim
pentru a face acest lucru chiar aici.

1497
01:14:37,873 --> 01:14:38,510
BINE.

1498
01:14:38,510 --> 01:14:41,600
>> Și apoi, acum, că
am găsit our-- da.

1499
01:14:41,600 --> 01:14:44,270
>> Audiența: Doar un question-- rapid
cand spui min și max,

1500
01:14:44,270 --> 01:14:46,410
suntem presupunând că
este deja sortate?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI Peng: Da, asta e de fapt o
condiție prealabilă pentru o căutare binară,

1502
01:14:48,400 --> 01:14:49,816
că trebuie să știi este sortate.

1503
01:14:49,816 --> 01:14:53,660
Care este motivul pentru fel, vă scrie în ta
problemă pusă înaintea căutarea binară.

1504
01:14:53,660 --> 01:14:55,910
BINE.

1505
01:14:55,910 --> 01:14:58,876
Deci, acum că știm unde punctul de mijloc nostru
este, ce vrei să faci aici?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> Audiența: Vrem să compare
că la celălalt.

1508
01:15:04,319 --> 01:15:05,110
ANDI Peng: Exact.

1509
01:15:05,110 --> 01:15:12,280
Deci ai de gând să compare
la mijlocul de valoare, nu?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
Și ce spune asta
noi atunci când vom compara?

1512
01:15:18,670 --> 01:15:22,226
Ce vrem sa facem după aceea?

1513
01:15:22,226 --> 01:15:25,389
>> Audiența: Dacă valoarea este mai mare
decât la mijlocul, dorim să-l taie.

1514
01:15:25,389 --> 01:15:26,180
ANDI Peng: Exact.

1515
01:15:26,180 --> 01:15:33,940
Deci, în cazul în care valoarea este mai mare
decât la mijlocul, suntem

1516
01:15:33,940 --> 01:15:36,550
va doriți să modificați aceste
maxes minim și, nu?

1517
01:15:36,550 --> 01:15:38,980
Ce vrem să se schimbe?

1518
01:15:38,980 --> 01:15:42,145
Deci, dacă știm că valoarea este undeva
aici, ceea ce nu-i putem pentru a schimba?

1519
01:15:42,145 --> 01:15:44,758
Vrem să schimbăm nostru
minim pentru a fi la mijlocul, nu?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
Și apoi altceva, dacă e în acest
jumătate, ceea ce vrem să se schimbe?

1522
01:15:54,292 --> 01:15:55,306
>> Audiența: maxim ta.

1523
01:15:55,306 --> 01:15:55,972
ANDI Peng: Da.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
Și apoi tu doar mergi
pentru a păstra looping, nu?

1526
01:16:04,680 --> 01:16:08,920
Pentru că acum, după o iterație
prin, ai un max aici.

1527
01:16:08,920 --> 01:16:10,760
Și apoi puteți recalcula un mid.

1528
01:16:10,760 --> 01:16:11,990
Și apoi puteți compara.

1529
01:16:11,990 --> 01:16:14,766
Și ai de gând să continui
până la minute și a maxes

1530
01:16:14,766 --> 01:16:15,890
au convergente în esență.

1531
01:16:15,890 --> 01:16:17,890
Și atunci știi că
ai lovit la sfârșitul anului acesta.

1532
01:16:17,890 --> 01:16:20,280
Și fie că ai găsit-
sau nu ai în acel moment.

1533
01:16:20,280 --> 01:16:23,170
>> Are acest sens tuturor?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
BINE.

1536
01:16:26,770 --> 01:16:27,900
Acest lucru este foarte important,
pentru că veți avea

1537
01:16:27,900 --> 01:16:29,760
pentru a scrie acest lucru în seara asta cod dumneavoastră.

1538
01:16:29,760 --> 01:16:32,660
Dar voi aveți o destul de bine
sentiment de ceea ce ar trebui sa facem,

1539
01:16:32,660 --> 01:16:34,051
care este bun.

1540
01:16:34,051 --> 01:16:34,550
BINE.

1541
01:16:34,550 --> 01:16:38,840
Deci avem despre șapte
minute a plecat secțiune.

1542
01:16:38,840 --> 01:16:43,170
Deci vom vorbi despre
acest PSET că vom face.

1543
01:16:43,170 --> 01:16:46,410
Deci PSET este împărțit în două jumătăți.

1544
01:16:46,410 --> 01:16:50,230
Prima jumătate implică
de punere în aplicare o descoperire

1545
01:16:50,230 --> 01:16:54,210
în care scrie o căutare liniară, un
căutare binară, și un algoritm de sortare.

1546
01:16:54,210 --> 01:16:56,690
>> Deci aceasta este prima
timp într-un PSET unde

1547
01:16:56,690 --> 01:17:00,050
vom fi oferindu-vă voi ceea ce se numește
cod de distribuție, care este codul

1548
01:17:00,050 --> 01:17:02,740
că ne-am pre-scris,
dar tocmai a plecat câteva piese de pe

1549
01:17:02,740 --> 01:17:04,635
pentru tine de a termina de scris.

1550
01:17:04,635 --> 01:17:07,510
Deci, voi, atunci când te uiți la acest
cod, s-ar putea obține cu adevărat speriat.

1551
01:17:07,510 --> 01:17:08,630
Dacă sunteți la fel ca, ahh, am
Nu știu despre ce face,

1552
01:17:08,630 --> 01:17:11,670
Nu știu, cum ar fi, care pare
atât de complicat, ahh, relaxați-vă.

1553
01:17:11,670 --> 01:17:12,170
E bine.

1554
01:17:12,170 --> 01:17:12,930
Citiți spec.

1555
01:17:12,930 --> 01:17:16,920
Spec va explica exact
ce toate aceste programe fac.

1556
01:17:16,920 --> 01:17:20,560
>> De exemplu, generate.c este un program
care va veni cu PSET ta.

1557
01:17:20,560 --> 01:17:24,060
Nu trebuie de fapt să-l atingă, dar
tu ar trebui să înțeleagă ce face.

1558
01:17:24,060 --> 01:17:28,550
Și generate.c, tot ce este face
fie generatoare de numere aleatoare

1559
01:17:28,550 --> 01:17:32,400
sau puteți da o sămânță, ca un
Numărul prestabilite că este nevoie de,

1560
01:17:32,400 --> 01:17:34,140
și generează mai multe numere.

1561
01:17:34,140 --> 01:17:37,170
Deci, există o modalitate specifică
punerea în aplicare a generate.c în care

1562
01:17:37,170 --> 01:17:42,760
puteți face doar o grămadă de numere
pentru tine de a testa alte metode pe tine.

1563
01:17:42,760 --> 01:17:45,900
>> Deci, dacă ai vrut să, pentru
exemplu, testați găsi dumneavoastră,

1564
01:17:45,900 --> 01:17:48,970
ce-ar vrea să rulați generate.c,
genera o grămadă de numere,

1565
01:17:48,970 --> 01:17:50,880
și apoi executați funcția ajutoare.

1566
01:17:50,880 --> 01:17:53,930
Funcția dvs. ajutoare este în cazul în care sunteți
de fapt, scrierea de cod fizic.

1567
01:17:53,930 --> 01:17:59,330
Și cred că de ajutoare ca un fișier bibliotecă
te scris că descoperire este de asteptare.

1568
01:17:59,330 --> 01:18:02,950
Și astfel în helpers.c, veți
face căutarea și sortarea.

1569
01:18:02,950 --> 01:18:06,500
>> Si apoi vei esență
doar le pe toate la un loc.

1570
01:18:06,500 --> 01:18:10,350
Spec vă va spune cum să
a pus că pe linia de comandă.

1571
01:18:10,350 --> 01:18:14,880
Și vei putea pentru a testa dacă sau
nu un fel și de căutare sunt de lucru.

1572
01:18:14,880 --> 01:18:15,870
Misto.

1573
01:18:15,870 --> 01:18:18,720
Are cineva a început deja și
problemele întâmpinate sau întrebări

1574
01:18:18,720 --> 01:18:20,520
ei au acum cu asta?

1575
01:18:20,520 --> 01:18:21,020
BINE.

1576
01:18:21,020 --> 01:18:21,476
>> Audiența: Așteaptă.

1577
01:18:21,476 --> 01:18:21,932
Am o intrebare.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI Peng: Da.

1579
01:18:22,844 --> 01:18:28,390
>> Audiența: Așa că am început să fac
căutarea liniară în helpers.c

1580
01:18:28,390 --> 01:18:29,670
și nu a fost într-adevăr de lucru.

1581
01:18:29,670 --> 01:18:34,590
Dar apoi mai târziu, am aflat ne-am
trebuie să-l ștergeți și de a face căutare binară.

1582
01:18:34,590 --> 01:18:36,991
Deci, contează în cazul în care nu funcționează?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI Peng: răspuns scurt este nu.

1585
01:18:41,510 --> 01:18:42,642
Dar din moment ce noi suntem not--

1586
01:18:42,642 --> 01:18:44,350
Audiența: Dar nimeni nu
de fapt de verificare.

1587
01:18:44,350 --> 01:18:46,058
ANDI Peng: Noi niciodată nu suntem
O să văd asta.

1588
01:18:46,058 --> 01:18:49,590
Dar, probabil, doriți să faceți
vă că de căutare este de lucru.

1589
01:18:49,590 --> 01:18:51,700
Pentru că dacă liniar dvs.
căutare nu funcționează,

1590
01:18:51,700 --> 01:18:54,410
atunci sunt șanse binar dvs.
căutare nu este de gând să lucreze la fel de bine.

1591
01:18:54,410 --> 01:18:56,646
Pentru că aveți similare
logică în ambele.

1592
01:18:56,646 --> 01:18:58,020
Și nu, nu contează.

1593
01:18:58,020 --> 01:19:01,300
Deci, singurele vei întoarce
în fel și sunt de căutare binară.

1594
01:19:01,300 --> 01:19:02,490
Da.

1595
01:19:02,490 --> 01:19:06,610
>> Și, de asemenea, o mulțime de copii au fost
încercarea de a compila helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Nu esti de fapt este permis
a face acest lucru, pentru că helpers.c

1597
01:19:09,550 --> 01:19:11,200
nu are o funcție principală.

1598
01:19:11,200 --> 01:19:13,550
Și așa trebuie doar
fi de fapt compilarea

1599
01:19:13,550 --> 01:19:18,670
genera și pentru a găsi, pentru că a găsi apeluri
helpers.c și funcțiile din cadrul acestuia.

1600
01:19:18,670 --> 01:19:20,790
Astfel încât face depanare
o durere în fund.

1601
01:19:20,790 --> 01:19:22,422
Dar asta e ceea ce trebuie să facem.

1602
01:19:22,422 --> 01:19:23,880
Audiența: Tocmai ai face toate, nu?

1603
01:19:23,880 --> 01:19:27,290
ANDI Peng: Puteți doar
face toate la fel de bine, da.

1604
01:19:27,290 --> 01:19:28,060
BINE.

1605
01:19:28,060 --> 01:19:32,570
Deci asta e, în termeni de ceea ce
PSET cere ca toți să faci.

1606
01:19:32,570 --> 01:19:35,160
Dacă aveți orice întrebări, simt
liber să mă întrebi după secțiune.

1607
01:19:35,160 --> 01:19:37,580
Voi fi aici pentru, cum ar fi, de 20 de minute.

1608
01:19:37,580 --> 01:19:40,500
>> Și da, PSET lui
într-adevăr nu așa de rău.

1609
01:19:40,500 --> 01:19:41,680
Voi ar trebui să fie OK.

1610
01:19:41,680 --> 01:19:43,250
Acestea, urmați doar orientări.

1611
01:19:43,250 --> 01:19:47,840
Un fel de un sentiment de, în mod logic, ceea ce
ar trebui să se întâmple și vei fi bine.

1612
01:19:47,840 --> 01:19:48,690
Nu fi prea frică.

1613
01:19:48,690 --> 01:19:50,220
Există o mulțime de cod
deja scris acolo.

1614
01:19:50,220 --> 01:19:53,011
Nu fi prea speriați dacă nu
să înțeleagă ce înseamnă toate astea.

1615
01:19:53,011 --> 01:19:54,749
În cazul în care o mulțime, e în regulă.

1616
01:19:54,749 --> 01:19:55,790
Și vin la ore de birou.

1617
01:19:55,790 --> 01:19:57,520
Vă vom ajuta să luați o privire.

1618
01:19:57,520 --> 01:20:00,810
>> Audiența: Cu extra
funcții, ne crezi pe cei sus?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI Peng: Da, acestea sunt în codul.

1620
01:20:03,417 --> 01:20:05,750
În jocul de 15, jumătate din
este deja scris pentru tine.

1621
01:20:05,750 --> 01:20:09,310
Deci, aceste funcții sunt
deja în codul.

1622
01:20:09,310 --> 01:20:12,020
Da.

1623
01:20:12,020 --> 01:20:12,520
In regula.

1624
01:20:12,520 --> 01:20:14,000
Ei bine, cel mai bun de noroc.

1625
01:20:14,000 --> 01:20:15,180
E o zi dezgustător.

1626
01:20:15,180 --> 01:20:19,370
Deci, sperăm că voi nu se simt prea
rău stau în interiorul și codificare.

1627
01:20:19,370 --> 01:20:22,133