1
00:00:00,000 --> 00:00:03,332
>> [Muusika mängib]

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Welcome to nädalas 3 punkti.

3
00:00:06,490 --> 00:00:09,550
Aitäh, kutid, kõik tulevad
sellele varem algusaeg täna.

4
00:00:09,550 --> 00:00:11,466
Meil on kena, veidi
intiimne rühm täna.

5
00:00:11,466 --> 00:00:14,570
Loodetavasti jõuame
viimistlus, ehk alguses,

6
00:00:14,570 --> 00:00:15,780
natuke varajane täna.

7
00:00:15,780 --> 00:00:22,057
Nii kiiresti, vaid mõned
Teated päevakorda täna.

8
00:00:22,057 --> 00:00:23,890
Enne kui hakkame me oleme
läheb lihtsalt minna üle

9
00:00:23,890 --> 00:00:28,910
põgusat logistiliste küsimuste, pset
küsimused, Küsitlusel asju.

10
00:00:28,910 --> 00:00:30,250
Ja siis me ka kohe.

11
00:00:30,250 --> 00:00:34,710
Me kasutame siluri nimetatakse GDB, et
alustada paljastaja meie kood, mis David

12
00:00:34,710 --> 00:00:36,550
selgitatud loeng.

13
00:00:36,550 --> 00:00:39,420
Me läheme üle nelja liiki kehvasti.

14
00:00:39,420 --> 00:00:42,310
Me läheme üle neid päris kiiresti
kuna nad on üsna intensiivsed.

15
00:00:42,310 --> 00:00:45,710
Aga tean, et kõik slaidid ja
lähtekoodi on alati online.

16
00:00:45,710 --> 00:00:50,810
Nii vabalt, on teie tutvumiseks, et
tagasi minna ja heita pilk selle.

17
00:00:50,810 --> 00:00:53,930
>> Me läheme läbi
asümptootilise märke, mis

18
00:00:53,930 --> 00:00:55,944
on lihtsalt fancy viis
öelda "runtimes"

19
00:00:55,944 --> 00:00:58,360
kus meil on suur O, mis
David selgitatud loeng.

20
00:00:58,360 --> 00:01:01,550
Ja meil on ka Omega, mis
on alampiir tööaega.

21
00:01:01,550 --> 00:01:06,450
Ja me räägime natuke rohkem
põhjalikku selle kohta, kuidas need tööd.

22
00:01:06,450 --> 00:01:10,160
Ja lõpuks, me läheme üle Kahendotsingupuu,
sest paljud, kes on juba

23
00:01:10,160 --> 00:01:15,190
heitis pilgu oma psets ilmselt teate, et
see on küsimus, mis on oma pset.

24
00:01:15,190 --> 00:01:17,470
Nii saate kõik olla õnnelik
et me katta see täna.

25
00:01:17,470 --> 00:01:20,610
>> Ja lõpuks, ühe oma
paragrahvi tagasisidet, ma tegelikult

26
00:01:20,610 --> 00:01:23,000
lahkus umbes 15 minutit temperatuuril
lõppu lihtsalt minema üle

27
00:01:23,000 --> 00:01:27,730
logistika pset3, küsimusi,
võibolla natuke juhendamist, kui soovite,

28
00:01:27,730 --> 00:01:28,990
Enne kui hakkame programmeerimine.

29
00:01:28,990 --> 00:01:30,890
Nii proovime läbi saama
materjal päris kiiresti.

30
00:01:30,890 --> 00:01:33,880
Ja siis me saame veeta aega
võttes rohkem küsimusi jaoks pset.

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

32
00:01:35,230 --> 00:01:39,570
>> Kiiresti, lihtsalt mõned
Teated enne kui hakkame täna.

33
00:01:39,570 --> 00:01:45,410
Esiteks, tere tegemine
läbi kaks oma psets.

34
00:01:45,410 --> 00:01:49,432
Võtsin pilk your-- jah, olgem
saada aplausi, et üks.

35
00:01:49,432 --> 00:01:51,140
Tegelikult olin tõesti,
tõesti muljet.

36
00:01:51,140 --> 00:01:55,800
Ma sorteeritud esimene pset kutid
Viimase nädala ja kutid tegid uskumatu.

37
00:01:55,800 --> 00:01:58,290
>> Stiil oli punkt
Lisaks mõned kommentaarid.

38
00:01:58,290 --> 00:02:00,660
Veenduge, et olete alati
Kommenteerides oma koodi.

39
00:02:00,660 --> 00:02:03,040
Aga teie psets olid punkti.

40
00:02:03,040 --> 00:02:05,549
Ja hoida see üles.

41
00:02:05,549 --> 00:02:08,090
Ja see on hea teehöövel
näha, et kutid on hakanud

42
00:02:08,090 --> 00:02:10,704
nii palju vaeva oma stiili
ja oma disaini oma koodi

43
00:02:10,704 --> 00:02:12,120
et me tahaksime näha, kuidas.

44
00:02:12,120 --> 00:02:16,450
Nii et ma kulgeb piki oma tänulikkust
ülejäänud TAS.

45
00:02:16,450 --> 00:02:19,210
>> Kuid seal on
paari Küsitluse küsimused

46
00:02:19,210 --> 00:02:22,010
Ma tahan minna üle, et
teeks nii minu elu

47
00:02:22,010 --> 00:02:24,900
ja palju teisi
Ajutise töötaja elu veidi lihtsamaks.

48
00:02:24,900 --> 00:02:28,220
Esiteks, ma olen märganud seda
Varem week-- kui paljud teist

49
00:02:28,220 --> 00:02:32,301
käinud check50 kohta
koodi enne kui saadate?

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

51
00:02:32,800 --> 00:02:36,690
Nii et igaüks peaks tegema check50,
because-- secret-- me tegelikult

52
00:02:36,690 --> 00:02:41,540
joosta check50 osana meie õigsuse
skripte testida oma kood.

53
00:02:41,540 --> 00:02:45,480
Seega, kui teie kood ei suuda
check50, suure tõenäosusega

54
00:02:45,480 --> 00:02:47,570
see on ilmselt läheb
ei meie kontrolli ka.

55
00:02:47,570 --> 00:02:49,320
Mõnikord poisid
on õiged vastused.

56
00:02:49,320 --> 00:02:52,200
Jms, ahne, mõned
Teil on õigus numbrid,

57
00:02:52,200 --> 00:02:53,960
sa lihtsalt välja printida mõned ekstra kraam.

58
00:02:53,960 --> 00:02:55,940
Ja see ekstra kraam
tegelikult ei kontrolli,

59
00:02:55,940 --> 00:02:58,440
sest arvuti ei
tea, mis see on otsite.

60
00:02:58,440 --> 00:03:00,981
Ja nii see lihtsalt joosta,
näha, et oma toodangut ei

61
00:03:00,981 --> 00:03:03,810
mängu, mida me ootame vastust
olla, ja märkige see on vale.

62
00:03:03,810 --> 00:03:06,560
>> Ja ma tean, mis juhtus
mõned juhtumid sel nädalal.

63
00:03:06,560 --> 00:03:09,870
Nii et ma läksin tagasi ja käsitsi
Humberliigitatud igaühe koodi.

64
00:03:09,870 --> 00:03:12,780
Tulevikus aga
Palun veendu,

65
00:03:12,780 --> 00:03:14,570
et näed
vaadake 50 oma koodi.

66
00:03:14,570 --> 00:03:17,970
Sest see on selline valu TA
to pean minema tagasi ja käsitsi ümberliigitamisotsuse

67
00:03:17,970 --> 00:03:21,197
iga pset iga
ühe, natuke jäi näiteks.

68
00:03:21,197 --> 00:03:22,530
Nii et ma ei võtnud ära kõik punktid.

69
00:03:22,530 --> 00:03:25,210
Ma arvan, et ma võtsin võibolla
üks või kaks disain.

70
00:03:25,210 --> 00:03:27,710
Tulevikus aga kui
sa ei suuda check50,

71
00:03:27,710 --> 00:03:31,330
aspekti võetakse
off õigsuse eest.

72
00:03:31,330 --> 00:03:35,020
>> Lisaks psets on
tõttu reedeti kell.

73
00:03:35,020 --> 00:03:38,990
Ma arvan, et seal on seitse minutit
lõpus ajapikendust, et anname.

74
00:03:38,990 --> 00:03:42,434
Per Harvard aega, nad lubatud
seitse minutit hiljaks kõike.

75
00:03:42,434 --> 00:03:44,350
Nii et siin Yale'i, siis me
järgima, et samuti.

76
00:03:44,350 --> 00:03:47,910
Aga päris palju, kell 00:07,
kui teie pset ei ole,

77
00:03:47,910 --> 00:03:49,720
see saab olema märgistatud nii hilja.

78
00:03:49,720 --> 00:03:53,160
Ja nii, kui see on märgitud
nii hilja, siis TA-- ma olen

79
00:03:53,160 --> 00:03:54,870
ikka läheb liigitamise oma psets.

80
00:03:54,870 --> 00:03:56,760
Nii näete ikka hinne ilmuda.

81
00:03:56,760 --> 00:03:58,820
Samas teame, et
lõpuks semester,

82
00:03:58,820 --> 00:04:02,270
kõik hilja psets lihtsalt olla
automaatselt nullida arvuti.

83
00:04:02,270 --> 00:04:04,490
>> Me teeme seda kahel põhjusel.

84
00:04:04,490 --> 00:04:09,220
Üks, mõnikord saame
vabandatav, nagu Dean vabandusi,

85
00:04:09,220 --> 00:04:10,762
hiljem, et ma ei tea veel.

86
00:04:10,762 --> 00:04:13,761
Nii me tahame veenduda, et me oleme liigitamine
kõik igaks juhuks, nagu ma olen

87
00:04:13,761 --> 00:04:15,080
puudu Dean vabandust.

88
00:04:15,080 --> 00:04:17,000
Ja teiseks, pidage
meeles, sa võid veel

89
00:04:17,000 --> 00:04:19,370
tilk üks pset, et
on täies ulatuses punktid.

90
00:04:19,370 --> 00:04:21,430
Ja nii me tahame hinne
kõik oma psets lihtsalt

91
00:04:21,430 --> 00:04:24,730
veenduda, et teie ulatus on
seal ja sa üritad neid.

92
00:04:24,730 --> 00:04:29,150
Nii et isegi kui see on hilja, siis ikka
laenu saada ulatus punktid, ma arvan.

93
00:04:29,150 --> 00:04:33,730
>> Nii loo moraal on, et
Veenduge, et teie psets on õigeaegne.

94
00:04:33,730 --> 00:04:38,350
Ja kui nad ei ole õigeaegne,
tean, et see ei ole suur.

95
00:04:38,350 --> 00:04:41,678
Jah, enne kui ma liikuda, kas keegi on
küsimusi pset tagasisidet?

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

97
00:04:42,178 --> 00:04:43,630
>> Sihtrühm: Kas sa ütlesid me
võib langeda ühe psets?

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

99
00:04:44,296 --> 00:04:47,050
Nii et üheksa psets üldist
jooksul semestri.

100
00:04:47,050 --> 00:04:50,610
Ja kui teil on ulatus
points-- nii ulatus on lihtsalt,

101
00:04:50,610 --> 00:04:53,567
päris palju, mida sa selle katse
Probleem on teil kasutusele aja,

102
00:04:53,567 --> 00:04:56,150
sa näitab, et olete
näidanud olete lugenud spec.

103
00:04:56,150 --> 00:04:57,191
See on päris palju ruumi.

104
00:04:57,191 --> 00:04:59,370
Ja kui te täitmisel
ulatus punktid, me

105
00:04:59,370 --> 00:05:03,360
võib langeda madalaim
ühe välja täies ulatuses.

106
00:05:03,360 --> 00:05:06,790
Nii et oma eelise
täiendada ja proovida iga pset.

107
00:05:06,790 --> 00:05:10,320
>> Isegi upload-- kui ükski
need tööd, laadige neid kõiki.

108
00:05:10,320 --> 00:05:13,711
Ja siis me loodetavasti võimalik
annan teile mõned neist punktid tagasi.

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

110
00:05:14,210 --> 00:05:16,780
Muid küsimusi?

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

112
00:05:17,840 --> 00:05:21,960
>> Teiseks, kontoris hours-- mõne
kiire märkmeid tööaega.

113
00:05:21,960 --> 00:05:24,300
Nii esimene, tulevad varakult sel nädalal.

114
00:05:24,300 --> 00:05:26,909
Keegi on kunagi varem
tööaega esmaspäeviti.

115
00:05:26,909 --> 00:05:28,700
Christabel tuli
tööaega eile õhtul.

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

117
00:05:29,691 --> 00:05:32,190
Ja mida on meil kontoris
tundi eile õhtul, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> Sihtrühm: Meil ​​oli jäätis.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Nii see on õige, meil oli
jäätise tööaega eile õhtul.

120
00:05:36,160 --> 00:05:39,390
Kuigi ma ei saa lubada, et
me peame jäätist tööaega

121
00:05:39,390 --> 00:05:43,230
iga nädal, mida ma luban
on see, et seal on tunduvalt

122
00:05:43,230 --> 00:05:45,380
parem õpilane TA suhe.

123
00:05:45,380 --> 00:05:47,650
Nagu legit, see on nagu 00:57.

124
00:05:47,650 --> 00:05:50,350
Arvestades, võrdlen
Neljapäev, sul umbes 150

125
00:05:50,350 --> 00:05:52,830
tõesti rõhutas lapsed ja no jäätist.

126
00:05:52,830 --> 00:05:55,360
Ja see lihtsalt ei ole produktiivne kellelegi.

127
00:05:55,360 --> 00:05:58,730
Nii loo moraal on, tule varakult
to tööaega ja head asjad

128
00:05:58,730 --> 00:06:00,310
juhtub.

129
00:06:00,310 --> 00:06:02,110
>> Samuti tulevad valmis küsimusi esitada.

130
00:06:02,110 --> 00:06:03,200
Sa tead?

131
00:06:03,200 --> 00:06:05,420
Sõltumata sellest, mida ajutise töötaja, ma
arvan, on öelnud,

132
00:06:05,420 --> 00:06:10,710
oleme olnud saada paar õpilased
kes tulevad neljapäeval kell, nagu, 10:50

133
00:06:10,710 --> 00:06:15,100
ei lugenud spec
on nagu mind aidata, aidake mind.

134
00:06:15,100 --> 00:06:18,200
Kahjuks sel hetkel, seal on
ei ole palju me saame teha, et aidata teil.

135
00:06:18,200 --> 00:06:19,590
Nii et palun tule varakult sel nädalal.

136
00:06:19,590 --> 00:06:22,040
Tule varakult tööaega.

137
00:06:22,040 --> 00:06:23,350
Tule valmis küsimusi esitada.

138
00:06:23,350 --> 00:06:25,310
Veenduge, et teie
üliõpilane, on kus

139
00:06:25,310 --> 00:06:27,620
sa pead olema nii, et
Ajutise töötaja võivad aidata teil mööda,

140
00:06:27,620 --> 00:06:32,850
mis on see, mida tööaega
tuleks jaotus.

141
00:06:32,850 --> 00:06:37,380
>> Teiseks, nii et ma tean, professorid
meeldib meid üllatada testidega.

142
00:06:37,380 --> 00:06:39,439
Mul oli professor need
nagu, yo, muide,

143
00:06:39,439 --> 00:06:41,230
mäletan, et Kontrolltöö
sul on järgmisel esmaspäeval.

144
00:06:41,230 --> 00:06:42,855
Jah, ma ei teadnud, et kongressi.

145
00:06:42,855 --> 00:06:45,630
Nii et ma lähen, et TA
mis meenutab teile kõigile, et viktoriin

146
00:06:45,630 --> 00:06:47,270
0--, sest sa tead, et me oleme CS.

147
00:06:47,270 --> 00:06:50,730
Nüüd, kui me oleme teinud massiivid, saad
miks see viktoriin 0, ei viktoriin 1, eh?

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

149
00:06:51,320 --> 00:06:52,490
Oh, ma sain mõned chuckles, et üks.

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

151
00:06:53,120 --> 00:06:59,710
>> Nii viktoriini 0 on 14. oktoober, kui
sa oled esmaspäeval kolmapäevani osa

152
00:06:59,710 --> 00:07:02,920
ja 15. oktoobril, kui sa oled
teisipäeval-neljapäev osa.

153
00:07:02,920 --> 00:07:05,630
See ei kehti
Neile, Harvardi

154
00:07:05,630 --> 00:07:10,350
Kes-- Ma arvan, et sa kõik olla
võttes oma viktoriinid 14..

155
00:07:10,350 --> 00:07:13,560
>> Nii et jah, järgmisel nädalal, kui
David, loengus, läheb,

156
00:07:13,560 --> 00:07:15,747
Jah, nii umbes, et
viktoriin järgmisel nädalal, siis kõik

157
00:07:15,747 --> 00:07:17,580
ei Ehmusin
sa tulid osa

158
00:07:17,580 --> 00:07:19,664
ja te teate, et teie
Viktoriin 0 on kaks nädalat.

159
00:07:19,664 --> 00:07:21,580
Ja me peame läbivaatamine
istungid ja puha.

160
00:07:21,580 --> 00:07:26,360
Nii ei ole muret
on hirmul selle eest.

161
00:07:26,360 --> 00:07:29,890
Kõik küsimused before-- küsimusi
üldse kohta logistiliste küsimuste,

162
00:07:29,890 --> 00:07:32,591
liigitamine, tööaega, lõigud?

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

164
00:07:33,090 --> 00:07:35,100
>> Sihtrühm: Nii viktoriini on
läheb ajal loeng?

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

166
00:07:35,766 --> 00:07:39,460
Nii viktoriin, ma arvan, on 60
minuti eraldatud selle aja pesa

167
00:07:39,460 --> 00:07:42,240
et sa lihtsalt võtta
loengute.

168
00:07:42,240 --> 00:07:44,810
Nii et sa ei pea tulema
kohta, nagu juhuslik 07:00.

169
00:07:44,810 --> 00:07:46,140
See kõik on hea.

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

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

172
00:07:50,060 --> 00:07:50,840
>> Hästi.

173
00:07:50,840 --> 00:07:54,330
Nii et me läheme
kasutusele mõiste teile

174
00:07:54,330 --> 00:08:00,760
sel nädalal, et David on juba selline
on käsitlenud loengus seda viimase nädala jooksul.

175
00:08:00,760 --> 00:08:02,010
Seda nimetatakse GDB.

176
00:08:02,010 --> 00:08:05,570
Ja kui paljud teist, samas
käigus kirjalikult oma psets,

177
00:08:05,570 --> 00:08:09,981
märganud suur nupp, mis ütleb,
"Debug" peal oma IDE?

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

179
00:08:10,480 --> 00:08:13,770
Nüüd me tegelikult saada väljakaevamine
mõistatus, mida see nupp tegelikult

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

181
00:08:14,270 --> 00:08:16,790
Ja ma garanteerin teile, et see on
ilus, ilus asi.

182
00:08:16,790 --> 00:08:20,740
>> Nii siiani, ma arvan
seal on olnud kaks asja

183
00:08:20,740 --> 00:08:23,320
õpilased on tavaliselt
teed, kui silumine psets.

184
00:08:23,320 --> 00:08:27,635
Üks, nad kas lisada
printf () - nii iga paar rida,

185
00:08:27,635 --> 00:08:29,760
lisavad nad on printf () -
oh, mis see on muutuv?

186
00:08:29,760 --> 00:08:32,551
Oh, mis see on muutuv now--
ja sa sellist näha progresseerumise

187
00:08:32,551 --> 00:08:33,940
oma koodi, kuna see töötab.

188
00:08:33,940 --> 00:08:37,030
Või teine ​​meetod lapsed teha, on
et nad lihtsalt kirjutada kogu asi

189
00:08:37,030 --> 00:08:38,610
ja siis niimoodi lõpus.

190
00:08:38,610 --> 00:08:39,970
Loodetavasti see toimib.

191
00:08:39,970 --> 00:08:44,851
Ma garanteerin teile, GDB on parem
kui mõlemal viisil.

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

193
00:08:45,350 --> 00:08:46,980
Nii see on teie uus parim sõber.

194
00:08:46,980 --> 00:08:51,780
Sest see on ilus asi
mis visuaalselt näitab nii

195
00:08:51,780 --> 00:08:54,850
mida teie kood on teinud
kindlal

196
00:08:54,850 --> 00:08:57,486
samuti seda, mida kõik oma
muutujad on kaasas,

197
00:08:57,486 --> 00:08:59,610
nagu mida nende väärtused on,
tollel kindlal hetkel.

198
00:08:59,610 --> 00:09:02,670
Ja sel viisil, saab tõesti
määrata murdepunkti oma koodi.

199
00:09:02,670 --> 00:09:04,350
Võite käivitada läbi rida-realt.

200
00:09:04,350 --> 00:09:07,324
Ja GDB peavad lihtsalt eest
sa, kuvatakse teile,

201
00:09:07,324 --> 00:09:09,490
Mis kõik oma muutujad
on, mida nad teevad,

202
00:09:09,490 --> 00:09:10,656
mis toimub kood.

203
00:09:10,656 --> 00:09:13,240
Ja sellisel viisil, et see on
nii palju lihtsam näha

204
00:09:13,240 --> 00:09:17,120
mis toimub asemel printf-se
või kirjalikult ette oma avaldustega.

205
00:09:17,120 --> 00:09:19,160
>> Nii et me teeme näide sellest hiljem.

206
00:09:19,160 --> 00:09:20,660
Nii et see tundub natuke abstraktne.

207
00:09:20,660 --> 00:09:23,490
Ära muretse, me teeme näiteid.

208
00:09:23,490 --> 00:09:29,170
Ja nii sisuliselt kolm suuremat,
enamkasutatavaid funktsioone peate GDB

209
00:09:29,170 --> 00:09:32,500
on Next Step üle,
ja Astu nupud.

210
00:09:32,500 --> 00:09:34,860
Ma lähen pea üle
seal, tegelikult, just nüüd.

211
00:09:34,860 --> 00:09:40,930
>> Nii saab kutid kõik näeme, et
või peaks ma suumida natuke?

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

213
00:09:43,220 --> 00:09:44,470
Aasta tagasi, kas sa nägid seda?

214
00:09:44,470 --> 00:09:45,730
Kas ma suumida?

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

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

217
00:09:49,390 --> 00:09:50,280
Seal me läheme.

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

219
00:09:50,960 --> 00:09:57,000
>> Nii et mul on siin, minu
rakendamise eest ahne.

220
00:09:57,000 --> 00:10:01,430
Ja kui palju te poisid kirjutas
ahne samas loop form-- et

221
00:10:01,430 --> 00:10:04,890
on täiesti vastuvõetav viis seda teha
see-- üks viis seda teha on lihtsalt

222
00:10:04,890 --> 00:10:06,280
lõhe moodul.

223
00:10:06,280 --> 00:10:09,290
Sest siis võite lasta
hinna ja siis on teie ülejäänud.

224
00:10:09,290 --> 00:10:11,150
Ja siis saate lihtsalt
lisada see kõik koos.

225
00:10:11,150 --> 00:10:13,390
Kas loogika, mida ma teen
siin mõtet igaüks,

226
00:10:13,390 --> 00:10:14,117
Enne kui hakkame?

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

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

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

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

231
00:10:19,210 --> 00:10:21,290
See on päris seksikas tükk
koodi, ma ütleks.

232
00:10:21,290 --> 00:10:23,502
Nagu ma ütlesin, Taavet
Loeng, mõne aja pärast,

233
00:10:23,502 --> 00:10:25,960
saate kõik ilmuvad koodi
midagi, mis on ilus.

234
00:10:25,960 --> 00:10:29,950
Ja mõnikord, kui sa näed ilus
kood, see on selline imeline tunne.

235
00:10:29,950 --> 00:10:35,410
>> Nii aga samas see kood on väga
ilus, see ei tööta korralikult.

236
00:10:35,410 --> 00:10:37,750
Nii saab käivitada check50 selle.

237
00:10:37,750 --> 00:10:39,440
Vaata 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
Kas see pset2?

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

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

245
00:10:52,890 --> 00:10:53,900
Nii võtame check50.

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

247
00:11:01,550 --> 00:11:07,170
>> Ja kui poisid näevad siin
see ei suuda paar juhtudel.

248
00:11:07,170 --> 00:11:10,165
Ja mõned teist, et
Loomulikult teeme oma probleem komplekti,

249
00:11:10,165 --> 00:11:11,110
sa oled nagu, ah, miks see ei tööta.

250
00:11:11,110 --> 00:11:13,318
Miks on töötanud mõned
väärtusi, kuid mitte teiste jaoks?

251
00:11:13,318 --> 00:11:17,760
Noh, GDB läheb, et aidata teil arv
miks need sisendid ei tööta.

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

253
00:11:18,320 --> 00:11:21,640
Vaatame, üks
kontrolli Olin löögiks check50

254
00:11:21,640 --> 00:11:24,920
oli sisendkäibemaksu 0,41.

255
00:11:24,920 --> 00:11:27,830
Nii et õige vastus, et
siis peaks olema saada on 4.

256
00:11:27,830 --> 00:11:33,090
Kuid selle asemel, mida ma väljatrükk
on 3-n, mis on vale.

257
00:11:33,090 --> 00:11:36,190
Nii saab lihtsalt käivitada käsitsi, lihtsalt
veenduge, et check50 töötab.

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

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

260
00:11:40,130 --> 00:11:43,340
Oih, ma pean tegema ahne.

261
00:11:43,340 --> 00:11:43,840
Seal me läheme.

262
00:11:43,840 --> 00:11:44,381
Nüüd ./greedy.

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

264
00:11:46,950 --> 00:11:47,670
>> Kui palju on võlgu?

265
00:11:47,670 --> 00:11:49,550
Teeme 0.41.

266
00:11:49,550 --> 00:11:52,590
Ja eks me näe siin
et see väljastamiseks, 3

267
00:11:52,590 --> 00:11:55,160
kui õiget vastust,
tegelikult peaks olema 4.

268
00:11:55,160 --> 00:12:01,460
Nii saab sisestada GDB ja kuidas me
võib minna, millega määratakse kindlaks selle probleemi.

269
00:12:01,460 --> 00:12:03,992
>> Seega esimene samm
alati silumist koodi

270
00:12:03,992 --> 00:12:05,950
on määrata murdepunkti,
või koht, kus sa

271
00:12:05,950 --> 00:12:09,079
soovite, et arvuti või
siluri alustada vaadates.

272
00:12:09,079 --> 00:12:11,120
Nii et kui sa tõesti ei
tea, mis su probleem on,

273
00:12:11,120 --> 00:12:14,670
Tavaliselt, tüüpiline asi, mida me tahame
tegema, on määrata oma murdepunkti on peamine.

274
00:12:14,670 --> 00:12:18,520
Nii et kui te poisid ei vaata seda
punast nuppu seal,

275
00:12:18,520 --> 00:12:22,860
yep, mis oli mulle määramisel
murdepunkti põhiülesanne.

276
00:12:22,860 --> 00:12:24,130
Ma klõpsake seda.

277
00:12:24,130 --> 00:12:26,130
>> Ja siis ma saan minna oma Debug nuppu.

278
00:12:26,130 --> 00:12:27,036
Ma tabanud seda nuppu.

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

280
00:12:31,710 --> 00:12:36,555
Lubage mul taas vähendamiseks, kui saan.

281
00:12:36,555 --> 00:12:38,020
Seal me läheme.

282
00:12:38,020 --> 00:12:40,730
Nii et meil on siin, paneel õigus.

283
00:12:40,730 --> 00:12:43,680
Vabandust, poisid taga, siis
ei saa tõesti näha tõesti hästi.

284
00:12:43,680 --> 00:12:49,090
Aga sisuliselt kõik
Selle õiguse paneel teeb

285
00:12:49,090 --> 00:12:53,130
on jälgida nii esile
line, mis on rida koodi

286
00:12:53,130 --> 00:12:56,640
et arvuti töötab praegu,
samuti kõiki oma muutujate

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

288
00:12:57,600 --> 00:13:00,487
>> Nii et sul senti, mündid, n,
kõik deklareeritud erinevaid asju

289
00:13:00,487 --> 00:13:01,070
sel hetkel.

290
00:13:01,070 --> 00:13:04,850
Ära muretse, sest me ei ole tegelikult
vormindatud neid ühtegi veel muutujaid.

291
00:13:04,850 --> 00:13:07,200
Nii arvuti, teie
arvuti lihtsalt näinud,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 viimati kasutatud funktsiooni
Selle mälu minu arvutis.

293
00:13:14,376 --> 00:13:16,000
Ja nii see on, kus senti praegu on.

294
00:13:16,000 --> 00:13:19,360
Aga no, et kui sa jooksed koodi
see peaks olema vormindatud.

295
00:13:19,360 --> 00:13:24,110
>> Nii lähme läbi, rida
line, mis toimub siin.

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

297
00:13:25,350 --> 00:13:29,400
Nii siin on kolm
nuppe, et ma lihtsalt seletada.

298
00:13:29,400 --> 00:13:34,090
Sul on Play või Run funktsiooni,
nuppu, siis on samm üle nuppu,

299
00:13:34,090 --> 00:13:36,600
ja teil ka Astu nuppu.

300
00:13:36,600 --> 00:13:41,260
Ja sisuliselt kõik kolm
neid lihtsalt minna läbi oma koodi

301
00:13:41,260 --> 00:13:42,690
ja teha erinevaid asju.

302
00:13:42,690 --> 00:13:45,680
>> Nii tavaliselt, kui sa silumine,
me ei taha lihtsalt vajuta Play,

303
00:13:45,680 --> 00:13:47,930
sest Play lihtsalt joosta
oma koodi selle lõpus.

304
00:13:47,930 --> 00:13:49,070
Ja siis sa tegelikult ei
tea, mida oma probleemiga

305
00:13:49,070 --> 00:13:51,432
on, kui seate mitu murdepunktid.

306
00:13:51,432 --> 00:13:53,890
Kui seate mitu murdepunktid,
See lihtsalt automaatselt

307
00:13:53,890 --> 00:13:56,030
kestab üks murdepunkt,
Järgmise, et järgmine.

308
00:13:56,030 --> 00:13:58,030
Aga sel juhul me oleme
lihtsalt, et üks, sest me

309
00:13:58,030 --> 00:13:59,970
tahan töötada meie tee
ülevalt alla alt.

310
00:13:59,970 --> 00:14:04,830
Nii et me läheme ignoreerida seda nuppu
just nüüd Käesoleva programmi.

311
00:14:04,830 --> 00:14:08,230
>> Nii Astuüle funktsioon lihtsalt
sammud üle iga rea

312
00:14:08,230 --> 00:14:11,510
ja ütleb teile, mida
arvuti teeb.

313
00:14:11,510 --> 00:14:14,630
Samm funktsionaalsusest läheb
tegelikud funktsiooni

314
00:14:14,630 --> 00:14:16,000
see on sinu rida koodi.

315
00:14:16,000 --> 00:14:19,070
Nii näiteks, nagu printf (),
mis on funktsioon, eks?

316
00:14:19,070 --> 00:14:21,980
Kui ma tahtsin füüsiliselt sammu
arvesse printf () funktsiooni,

317
00:14:21,980 --> 00:14:25,610
Ma tegelikult minema tükk
kood, kus printf () kirjutatud ja vaata

318
00:14:25,610 --> 00:14:26,730
Mis seal toimub.

319
00:14:26,730 --> 00:14:29,924
>> Aga tavaliselt eeldame, et
kood, mis me teile toimib.

320
00:14:29,924 --> 00:14:31,340
Eeldame printf () töötab.

321
00:14:31,340 --> 00:14:33,170
Me eeldame, et GetInt () töötab.

322
00:14:33,170 --> 00:14:35,170
Seega puudub vajadus
samm neid funktsioone.

323
00:14:35,170 --> 00:14:37,170
Aga kui seal funktsioonid
et sa kirjutad ise

324
00:14:37,170 --> 00:14:39,060
mis sa tahad, et kontrollida
teada, mis toimub,

325
00:14:39,060 --> 00:14:41,200
sa tahaksid astuda
arvesse, et funktsioon.

326
00:14:41,200 --> 00:14:43,940
>> Nii just nüüd lihtsalt lähen
astuda üle selle tüki koodi.

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

328
00:14:44,485 --> 00:14:46,547
Oh, print, "Oh hai, kuidas
palju muutusi on ees? "

329
00:14:46,547 --> 00:14:47,130
Me ei hooli.

330
00:14:47,130 --> 00:14:49,830
Me teame, et see töötab,
nii me samm üle.

331
00:14:49,830 --> 00:14:53,290
>> Nii n, mis on meie float, et
me oleme initialized-- või declared--

332
00:14:53,290 --> 00:14:56,810
kuni tipus, me oleme nüüd
võrdsustades et GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Nii saab astuda üle, et.

334
00:14:57,810 --> 00:14:59,580
Ja me näeme juures
alumine siin, programmi

335
00:14:59,580 --> 00:15:03,360
annab märku, et ma sisend väärtus.

336
00:15:03,360 --> 00:15:08,580
Nii saab sisestada väärtuse tahame
testida siit, mis on 0,41.

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

338
00:15:09,160 --> 00:15:12,780
>> Nüüd n-- te poisid näha
Siin on bottom-- see

339
00:15:12,780 --> 00:15:15,140
stored-- sest me
ei ole ümardatud veel, et see on

340
00:15:15,140 --> 00:15:19,540
salvestatakse see nagu hiiglaslik
float, et on ,4099999996,

341
00:15:19,540 --> 00:15:22,550
mis on piisavalt lähedal, et meie
eesmärkidel, just nüüd, 0,41.

342
00:15:22,550 --> 00:15:26,090
Ja siis me näeme hiljem, kui me
jätkuvalt üle astuda programmi

343
00:15:26,090 --> 00:15:29,850
pärast siin, n on muutunud
ümar ja senti on saanud 41.

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

345
00:15:30,350 --> 00:15:32,230
Nii et me teame, et meie ümardamine töövõime.

346
00:15:32,230 --> 00:15:34,700
Me teame, et meil on
õige arv senti,

347
00:15:34,700 --> 00:15:36,990
nii et me teame, et see on
ei ole tõesti probleem.

348
00:15:36,990 --> 00:15:40,050
>> Nii jätkame tõhustamist
kohta selles programmis.

349
00:15:40,050 --> 00:15:40,900
Käime siin.

350
00:15:40,900 --> 00:15:46,139
Ja nii pärast seda rida koodi, me
peaks teadma, kui palju neljandikku meil.

351
00:15:46,139 --> 00:15:46,680
Me astume üle.

352
00:15:46,680 --> 00:15:52,040
Ja sa näed me tegelikult üks
kvartalis, sest me oleme maha 25

353
00:15:52,040 --> 00:15:53,790
meie esialgne väärtus 41.

354
00:15:53,790 --> 00:15:55,890
Ja meil on 16 vasakul meie senti.

355
00:15:55,890 --> 00:15:58,830
>> Kas igaüks aru, kuidas
Programmi astutakse läbi

356
00:15:58,830 --> 00:16:02,980
ja miks senti on nüüd 16
ja miks nüüd, mündid on muutunud 1?

357
00:16:02,980 --> 00:16:04,610
Kas kõik seda loogikat järgida?

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

359
00:16:05,110 --> 00:16:07,860
Nii nagu seda hetkel,
Programmi töö, eks?

360
00:16:07,860 --> 00:16:09,797
Me teame, et see teeb täpselt
mida me tahame seda.

361
00:16:09,797 --> 00:16:11,880
Ja me tegelikult ei
välja trükkida, oh, mida

362
00:16:11,880 --> 00:16:14,430
on senti sel hetkel,
Mis on mündid selles punktis.

363
00:16:14,430 --> 00:16:17,170
>> Jätkame läbimas programmi.

364
00:16:17,170 --> 00:16:18,100
Samm üle.

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

366
00:16:18,620 --> 00:16:19,700
Me läheme üle dimes.

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

368
00:16:20,200 --> 00:16:22,367
Me näeme, et see on võetud
off $ 0.10 peenraha.

369
00:16:22,367 --> 00:16:23,450
Ja nüüd on meil kaks münti.

370
00:16:23,450 --> 00:16:25,260
See on õige.

371
00:16:25,260 --> 00:16:31,555
>> Me läheme üle penni ja näeme
et meil jääb üle senti.

372
00:16:31,555 --> 00:16:32,680
Hmm, see on kummaline.

373
00:16:32,680 --> 00:16:37,540
Siin üleval on programm, pidin
et on lahutatakse oma penni.

374
00:16:37,540 --> 00:16:39,400
Võib-olla ma lihtsalt ei olnud
tehes seda rida paremalt.

375
00:16:39,400 --> 00:16:42,190
Ja oh häda, näed
siin, sest me teame,

376
00:16:42,190 --> 00:16:44,360
et meil sekkub
sisseviivaid 32 ja 33,

377
00:16:44,360 --> 00:16:50,560
see on koht, kus meie programmi
valesti oli muutujad joosta.

378
00:16:50,560 --> 00:16:55,136
Nii saame vaadata ja näha, oh,
Ma lahutades senti siin

379
00:16:55,136 --> 00:16:57,010
aga ma ei ole tegelikult
lisada oma mündi väärtus.

380
00:16:57,010 --> 00:16:57,860
Ma lisades senti.

381
00:16:57,860 --> 00:17:00,234
Ja ma ei taha lisada
senti, ma tahan lisada, et münte.

382
00:17:00,234 --> 00:17:05,420
Nii et kui me muudame, et münte,
meil tööprogrammi.

383
00:17:05,420 --> 00:17:06,730
Ma saan käivitada check50.

384
00:17:06,730 --> 00:17:11,063
Sa võid väljuda GDB õigus
siin ja seejärel käivitage check50 uuesti.

385
00:17:11,063 --> 00:17:11,938
Ma võiks lihtsalt teha.

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

387
00:17:14,822 --> 00:17:18,480
Ma pean tegema ahne.

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

389
00:17:19,940 --> 00:17:22,819
Ja siin see on trükkimine
välja õige vastuse.

390
00:17:22,819 --> 00:17:26,569
>> Nii nagu te poisid ei vaata, GDB
on tõesti võimas vahend

391
00:17:26,569 --> 00:17:29,940
sest kui meil on nii palju koodi
läheb edasi ja nii palju muutujaid

392
00:17:29,940 --> 00:17:32,510
et see on raske meie jaoks, nagu
inimene, jälgida.

393
00:17:32,510 --> 00:17:35,360
Arvuti, on GDB
siluri, on võime

394
00:17:35,360 --> 00:17:37,020
jälgida kõike.

395
00:17:37,020 --> 00:17:40,480
Ma tean, in Visionaire, kutid ilmselt
oleks tabanud mõnda killustatust vead

396
00:17:40,480 --> 00:17:43,150
sest sa jooksid
auti oma valikut.

397
00:17:43,150 --> 00:17:46,510
Näites Caesar, mis on
täpselt, mida ma olen rakendanud siin.

398
00:17:46,510 --> 00:17:50,060
>> Nii et ma unustasin, et kontrollida
Mis juhtuks, kui ma

399
00:17:50,060 --> 00:17:52,510
ei olnud kaks käsurea argumente.

400
00:17:52,510 --> 00:17:53,880
Ma lihtsalt ei pane, et kontrollida.

401
00:17:53,880 --> 00:17:57,380
Ja kui ma saan Debug-- seadsin
minu murdepunkti, et seal.

402
00:17:57,380 --> 00:17:58,055
Ma saan Debug.

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

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

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

406
00:18:17,050 --> 00:18:20,350
Seega tegelikult GDB pidi
et on mulle rääkinud seal

407
00:18:20,350 --> 00:18:22,300
oli killustatust süü olemas.

408
00:18:22,300 --> 00:18:24,883
Ma ei tea, mis juhtus
seal, aga kui ma jooksin seda,

409
00:18:24,883 --> 00:18:25,590
see töötas.

410
00:18:25,590 --> 00:18:29,410
Kui sul tekib rida koodi abil ja
GDB võib lihtsalt lõpetavad järsku sulle,

411
00:18:29,410 --> 00:18:31,540
Mine ja vaata, mis punase viga on.

412
00:18:31,540 --> 00:18:33,930
See ütlen teile, hei, sa
oli killustatust süü,

413
00:18:33,930 --> 00:18:38,550
mis tähendab, et sa üritasid pääseda
ruumi massiivi, et ei ole olemas.

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

415
00:18:39,050 --> 00:18:43,280
>> Nii järgmises probleemi
seada sel nädalal, kutid

416
00:18:43,280 --> 00:18:45,600
Tõenäoliselt on palju
muutujad ujuvad ringi.

417
00:18:45,600 --> 00:18:48,560
Sa ei kavatse olla kindel, mida
nad kõik tähendavad teatud hetkel.

418
00:18:48,560 --> 00:18:53,560
Nii GDB tõesti aitab teil figuring
välja, mida nad kõik on võrdsed

419
00:18:53,560 --> 00:18:55,940
ja on võimalik näha, et visuaalselt.

420
00:18:55,940 --> 00:19:01,995
Kas keegi segi kuidas
ükskõik mis töötas?

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

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

423
00:19:10,121 --> 00:19:10,620
Hästi.

424
00:19:10,620 --> 00:19:14,260
Nii et pärast, et oleme
läheb sukelduda õigus

425
00:19:14,260 --> 00:19:17,562
arvesse on neli erinevat
tüüpi kehvasti sel nädalal.

426
00:19:17,562 --> 00:19:19,520
Kui paljud teist, esimene
kõik, enne kui hakkame,

427
00:19:19,520 --> 00:19:23,020
lugenud kogu spec pset3?

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

429
00:19:23,824 --> 00:19:24,740
Ma olen uhke teie kutid.

430
00:19:24,740 --> 00:19:29,110
See on nagu pool klassi, mis
on oluliselt rohkem kui eelmisel korral.

431
00:19:29,110 --> 00:19:33,950
>> Nii see on suurepärane, sest kui
me räägime sisu

432
00:19:33,950 --> 00:19:36,170
in lecture-- või kahju,
in section-- Mulle meeldib

433
00:19:36,170 --> 00:19:38,210
seostada palju, et
tagasi sellele, mida pset on

434
00:19:38,210 --> 00:19:40,210
ja kuidas sa tahad
rakendada, et oma pset.

435
00:19:40,210 --> 00:19:42,400
Nii et kui sa tuled, millel
loe spec, siis see

436
00:19:42,400 --> 00:19:45,510
olla palju lihtsam mõista
mida ma räägin, kui ma ütlen,

437
00:19:45,510 --> 00:19:48,720
oh hei, see võib olla tõesti
Hea koht rakendada sellist.

438
00:19:48,720 --> 00:19:52,870
Nii neile, kes on lugenud
spec tean, et osa oma pset,

439
00:19:52,870 --> 00:19:54,900
sa lähed pea
kirjutada tüüpi omamoodi.

440
00:19:54,900 --> 00:19:58,670
Nii et see võib olla väga kasulik
jaoks palju sa täna.

441
00:19:58,670 --> 00:20:01,760
>> Nii me alustad,
Sisuliselt kõige lihtsam tüübist

442
00:20:01,760 --> 00:20:04,580
omamoodi, valik omamoodi.

443
00:20:04,580 --> 00:20:06,800
Tüüpiline algoritm
kuidas me tahaks edasi minna

444
00:20:06,800 --> 00:20:10,460
on-- David läbis need kõik
loeng, nii et ma kiiresti edasi liikuda

445
00:20:10,460 --> 00:20:13,900
siin-- sisuliselt, siis
on massiivi väärtusi.

446
00:20:13,900 --> 00:20:17,170
Ja siis leiad
Väikseim sorteerimata väärtus

447
00:20:17,170 --> 00:20:20,200
ja sa vahetada, et väärtus
Esimeses sorteerimata väärtus.

448
00:20:20,200 --> 00:20:22,700
Ja siis muudkui korrates
ülejäänud oma nimekirja.

449
00:20:22,700 --> 00:20:25,740
>> Ja siin on visuaalne selgitus
kuidas see töötaks.

450
00:20:25,740 --> 00:20:30,460
Nii näiteks, kui olime alustada
array viiest elemendist, indeks

451
00:20:30,460 --> 00:20:35,910
0-4, 3, 5, 2, 6 ja 4 väärtuste
paigutatud array-- seda praegu,

452
00:20:35,910 --> 00:20:38,530
Me elame eeldada
et nad kõik sorteerimata

453
00:20:38,530 --> 00:20:41,130
sest me pole harjunud teisiti.

454
00:20:41,130 --> 00:20:44,130
>> Niisiis, kuidas valik omamoodi oleks
Töö on see, et see oleks esimene

455
00:20:44,130 --> 00:20:46,800
jookseb läbi kogu
sorteerimata massiivi.

456
00:20:46,800 --> 00:20:49,120
Oleks noppida väikseim väärtus.

457
00:20:49,120 --> 00:20:51,750
Sel juhul 3, eks
Nüüd, on väikseim.

458
00:20:51,750 --> 00:20:52,680
Läheb 5.

459
00:20:52,680 --> 00:20:55,620
Nope, 5 ei ole suurem than--
või kahju, ei ole vähem than-- 3.

460
00:20:55,620 --> 00:20:57,779
Nii minimaalne väärtus on veel 3.

461
00:20:57,779 --> 00:20:58,695
Ja siis sa saad 2.

462
00:20:58,695 --> 00:21:00,990
Arvuti näeb, oh, 2 on väiksem kui 3.

463
00:21:00,990 --> 00:21:02,750
2 Nüüd tuleb minimaalne väärtus.

464
00:21:02,750 --> 00:21:06,630
Ja nii 2 vahetustehingud selle esimene väärtus.

465
00:21:06,630 --> 00:21:10,702
>> Nii et pärast ühe pass, me tõepoolest näha
et 2 ja 3 on vahetatud.

466
00:21:10,702 --> 00:21:13,910
Ja me lihtsalt läheb jätkata teed
Selle jälle ülejäänud massiivi.

467
00:21:13,910 --> 00:21:17,660
Nii et me läheme lihtsalt joosta
Viimase nelja indeksid massiivi.

468
00:21:17,660 --> 00:21:20,670
Me näeme, et 3 on
Järgmise minimaalne väärtus.

469
00:21:20,670 --> 00:21:23,240
Nii et me läheme vahetada, et 4.

470
00:21:23,240 --> 00:21:26,900
Ja siis me lihtsalt läheb hoida
kulgeb läbi kuni lõpuks sa

471
00:21:26,900 --> 00:21:33,730
saada sortida massiivi kus
2, 3, 4, 5 ja 6 on kõik järjestatud.

472
00:21:33,730 --> 00:21:37,530
Kas kõik mõistavad loogika
kuidas valik omamoodi töötab?

473
00:21:37,530 --> 00:21:39,669
>> Sa pead lihtsalt mingisugune
maksumusega vähemalt.

474
00:21:39,669 --> 00:21:41,210
Sa jälgida, mis see on.

475
00:21:41,210 --> 00:21:45,170
Ja iga kord, kui te leida seda, kui swap see
esimese väärtus array--

476
00:21:45,170 --> 00:21:48,740
või mitte esimene value--
Järgmise väärtuse massiivi.

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

478
00:21:50,150 --> 00:21:55,460
>> Nii nagu te poisid liiki
nägin lühike pilguheit,

479
00:21:55,460 --> 00:21:58,450
me ei kavatse pseudokoodi seda.

480
00:21:58,450 --> 00:22:02,510
Nii et kui te poisid taga taha
moodustavad rühma, igaüks laua

481
00:22:02,510 --> 00:22:06,170
võib moodustada väike partner, ma lähen
teile sinusuguseid kolm minutit

482
00:22:06,170 --> 00:22:08,190
lihtsalt rääkida läbi
loogika, inglise,

483
00:22:08,190 --> 00:22:14,161
kuidas me võiksime olla võimeline rakendama
pseudokoodi kirjutada valikut omamoodi.

484
00:22:14,161 --> 00:22:14,910
Ja seal on kristalliseerunud.

485
00:22:14,910 --> 00:22:16,118
Palun tulla ja saada kommi.

486
00:22:16,118 --> 00:22:19,520
Kui oled taga ja soovid
kommi, ma ei viska kristalliseerunud sind.

487
00:22:19,520 --> 00:22:22,850
Tegelikult teevad sina-- lahe.

488
00:22:22,850 --> 00:22:23,552
Oi vabandust.

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

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

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

492
00:25:23,880 --> 00:25:27,140
>> Nii et kui me tahaksime, kui
klassi, kirjutada pseudokoodi

493
00:25:27,140 --> 00:25:30,466
kuidas võiks läheneda
Selle probleemi lihtsalt vabalt.

494
00:25:30,466 --> 00:25:32,340
Ma lihtsalt ringi käia ja
selleks, küsida rühmad

495
00:25:32,340 --> 00:25:35,065
Järgmise rida
mida me peaksime tegema.

496
00:25:35,065 --> 00:25:37,840
Nii et kui te tahate alustada
off, mis on esimene asi,

497
00:25:37,840 --> 00:25:40,600
mida teha, kui sa üritad
rakendada nii, et lahendada see programm

498
00:25:40,600 --> 00:25:43,480
valikuliselt sortida nimekirja?

499
00:25:43,480 --> 00:25:46,349
Lihtsalt eeldame me
on massiiv, eks?

500
00:25:46,349 --> 00:25:49,088
>> Sihtrühm: Sa tahad luua mõned
omamoodi [kuuldamatu], et sa oled

501
00:25:49,088 --> 00:25:50,420
kulgeb läbi oma terve rida.

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

503
00:25:51,128 --> 00:25:54,100
Nii et sa lähed tahan kinnitada,
läbi iga ruum, eks?

504
00:25:54,100 --> 00:26:05,490
Nii suur.

505
00:26:05,490 --> 00:26:08,600
Kui te tahate, et anna mulle
Järgmine LINE yeah, taga.

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

507
00:26:11,414 --> 00:26:13,290
>> Sihtrühm: Kontrollige neid
kõik seotud väikseim.

508
00:26:13,290 --> 00:26:14,248
>> ANDI PENG: Seal me läheme.

509
00:26:14,248 --> 00:26:17,438
Nii et me tahame minna läbi ja kontrollige
vaata, mida minimaalne väärtus on, eks?

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

511
00:26:22,110 --> 00:26:24,840
Ma lähen lühendada, et "min".

512
00:26:24,840 --> 00:26:27,658
Mis te poisid tahavad teha pärast
olete leidnud minimaalne väärtus?

513
00:26:27,658 --> 00:26:28,533
>> Sihtrühm: [kuuldamatu]

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

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Nii et sa lähed tahan
lülitage see on esimene, mis massiivi,

516
00:26:33,150 --> 00:26:33,650
õige?

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

518
00:26:45,120 --> 00:26:46,850
See on alguses, ma lähen ütlen.

519
00:26:46,850 --> 00:26:47,220
Hästi.

520
00:26:47,220 --> 00:26:50,386
Nüüd, et olete vahetasid esimese
üks, mida sa tahad teha pärast seda?

521
00:26:50,386 --> 00:26:54,840
Nüüd me teame, et see siin
peab olema väikseim väärtus, eks?

522
00:26:54,840 --> 00:26:58,310
Siis on veel ülejäänud
massiiv, mis on sorteerimata.

523
00:26:58,310 --> 00:27:01,569
Mida sa tahad teha siin, kui te
poisid tahavad mulle reale?

524
00:27:01,569 --> 00:27:04,610
Sihtrühm: Nii siis tahan korrata
kogu ülejäänud massiivi.

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

526
00:27:05,276 --> 00:27:09,857
Ja mis ei iterating läbi
Selline tähenda me ilmselt vaja?

527
00:27:09,857 --> 00:27:10,440
Mis tüüpi of--

528
00:27:10,440 --> 00:27:12,057
>> Sihtrühm: Oh, veel muutuja?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Tõenäoliselt
teine ​​silmus, eks?

530
00:27:13,890 --> 00:27:28,914
Nii et me ilmselt läheb taha
itereerima through-- suur.

531
00:27:28,914 --> 00:27:31,830
Ja siis läheme tagasi
ilmselt kontrollige minimaalset uuesti,

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

533
00:27:32,100 --> 00:27:34,975
Ja sa lähed, et hoida korrates
Selles, sest silmad lihtsalt läheb

534
00:27:34,975 --> 00:27:36,010
hoida töötab, eks?

535
00:27:36,010 --> 00:27:39,190
>> Nii nagu te poisid ei vaata, me
lihtsalt üldine pseudokoodi

536
00:27:39,190 --> 00:27:41,480
kuidas me tahame seda programmi vaatama.

537
00:27:41,480 --> 00:27:46,646
See Kerrata siin, mida me
Tavaliselt on vaja kirjutada oma koodi

538
00:27:46,646 --> 00:27:49,270
Kui me tahame korrata kaudu
massiiv, mis tüüpi struktuuriga?

539
00:27:49,270 --> 00:27:51,030
Ma arvan Christabel
juba öelnud seda varem.

540
00:27:51,030 --> 00:27:51,500
>> Sihtrühm: A loop.

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

542
00:27:52,160 --> 00:27:52,770
Täpselt.

543
00:27:52,770 --> 00:27:56,060
Nii et see on ilmselt
saab olema silmus.

544
00:27:56,060 --> 00:27:59,240
Mis on check siin läheb tähenda?

545
00:27:59,240 --> 00:28:02,536
Tavaliselt, kui sa tahad, et kontrollida
kui midagi on midagi else--

546
00:28:02,536 --> 00:28:03,270
>> Sihtrühm: Kui.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: IF, eks?

548
00:28:06,790 --> 00:28:10,790
Ja siis swap siin, siis me
minna üle hiljem, sest David

549
00:28:10,790 --> 00:28:12,770
läks läbi, et loeng samuti.

550
00:28:12,770 --> 00:28:14,580
Ja siis teine ​​Kerrata implies--

551
00:28:14,580 --> 00:28:15,120
>> Sihtrühm: Teine silmus.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another silmus, täpselt.

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

554
00:28:19,870 --> 00:28:22,000
Nii et kui me vaatame
sel õigesti, me

555
00:28:22,000 --> 00:28:24,680
näete, et me ilmselt
läheb vaja astmelist silmus

556
00:28:24,680 --> 00:28:28,330
koos tingimisi avalduse olemas
ja siis tegelik tükk kood, mis on

557
00:28:28,330 --> 00:28:31,360
läheb vahetada väärtusi.

558
00:28:31,360 --> 00:28:35,980
Nii et ma olen lihtsalt üldiselt kirjutatud
pseudokoodi koodi siin.

559
00:28:35,980 --> 00:28:38,910
Ja siis me tegelikult toimub
füüsiliselt, rühmana

560
00:28:38,910 --> 00:28:40,700
proovida rakendada seda täna.

561
00:28:40,700 --> 00:28:42,486
Lähme tagasi selle 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
Miks see nii on Mitte-- seal on.

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

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

567
00:28:55,834 --> 00:28:57,500
Vabandame, lubage mul proovida suumida natuke rohkem.

568
00:28:57,500 --> 00:28:59,310
Seal me läheme.

569
00:28:59,310 --> 00:29:05,060
Kõik, mida ma siin teen on lõin
programmi nimega "valik / sort.c."

570
00:29:05,060 --> 00:29:10,860
Olen loonud hulgaliselt üheksa
väärtusi, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Praegu kui võimalik
vaata, nad on ebakorrapärane.

572
00:29:14,370 --> 00:29:17,880
n saab olema number,
ütleb summa väärtused

573
00:29:17,880 --> 00:29:18,920
sa pead oma valikut.

574
00:29:18,920 --> 00:29:20,670
Sel juhul on meil üheksa väärtusi.

575
00:29:20,670 --> 00:29:23,760
Ja ma olen just for loop siin
mis prindib sorteerimata massiivi.

576
00:29:23,760 --> 00:29:28,370
>> Ja lõpuks, ma sain ka eest
loop, et lihtsalt trükib need välja.

577
00:29:28,370 --> 00:29:32,070
Nii teoreetiliselt kui see programm
töötab korralikult, lõpus,

578
00:29:32,070 --> 00:29:35,670
näed trükitud loop
milles 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 on kõik korrektne.

580
00:29:39,310 --> 00:29:43,410
>> Nii on meil meie pseudokoodi siin.

581
00:29:43,410 --> 00:29:46,090
Kas keegi taha mina-- Ma olen lihtsalt
lähe küsima volunteers--

582
00:29:46,090 --> 00:29:49,540
ütle mulle täpselt, mida kirjutada, kui
tahame kõigepealt lihtsalt kordamiseks

583
00:29:49,540 --> 00:29:52,840
läbi alguses massiivi?

584
00:29:52,840 --> 00:29:55,204
Mis koodirida ma olen
ilmselt läheb vaja siin?

585
00:29:55,204 --> 00:29:56,990
>> Sihtrühm: [kuuldamatu]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Jah, tunnen
tasuta mina-- kahju, siis

587
00:29:59,010 --> 00:30:02,318
ei pea seisma up-- tunne
tasuta häält tõsta natuke.

588
00:30:02,318 --> 00:30:08,190
>> Sihtrühm: For int i võrdub 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI PENG: Jah, hea.

590
00:30:10,690 --> 00:30:15,220
>> Sihtrühm: i on väiksem kui massiivi pikkus.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Nii hoida
pahanda siin, sest me

592
00:30:19,630 --> 00:30:23,060
ei ole funktsioon, mis
ütleb meile pikkus array,

593
00:30:23,060 --> 00:30:25,790
meil on juba
väärtus, mis salvestab seda.

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

595
00:30:27,920 --> 00:30:31,010
Teine asi, mida meeles
in mind-- massiivi

596
00:30:31,010 --> 00:30:33,940
üheksa väärtused, mida on indeksid?

597
00:30:33,940 --> 00:30:38,720
Ütleme nii, et see massiiv oli 0-3.

598
00:30:38,720 --> 00:30:41,500
Sa näed, et viimane
indeks on tegelikult 3.

599
00:30:41,500 --> 00:30:45,530
See ei ole 4, kuigi seal
neli väärtust massiivi.

600
00:30:45,530 --> 00:30:49,866
>> Nii siin, me peame olema väga ettevaatlikud
mida meie tingimus pikkus

601
00:30:49,866 --> 00:30:50,490
läheb.

602
00:30:50,490 --> 00:30:51,948
>> Sihtrühm: Kas ei oleks n miinus 1?

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: See läheb
n miinus 1, täpselt.

604
00:30:54,440 --> 00:30:57,379
Kas see mõtet, miks
see on n miinus 1, igaüks?

605
00:30:57,379 --> 00:30:58,920
See on sellepärast, massiivid on null-indekseeritud.

606
00:30:58,920 --> 00:31:02,010
Nad algavad 0 ja kestab kuni n miinus 1.

607
00:31:02,010 --> 00:31:03,210
Jah, see on natuke keeruline.

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

609
00:31:03,730 --> 00:31:05,929
Ja siis--

610
00:31:05,929 --> 00:31:08,054
Sihtrühm: Isnt'1 et
juba hoolitsenud küll,

611
00:31:08,054 --> 00:31:11,400
lihtsalt ei ütle, "väiksem või
võrdne "ja lihtsalt öelda" alla? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: See on
tõesti hea küsimus.

613
00:31:13,108 --> 00:31:13,630
Nii et jah.

614
00:31:13,630 --> 00:31:17,410
Aga ka see, kuidas me oleme
rakendamise kontrollimise õigus,

615
00:31:17,410 --> 00:31:19,120
on vaja võrrelda kahte väärtust.

616
00:31:19,120 --> 00:31:21,009
Nii et sa tegelikult tahad
jäta ", et" tühjad.

617
00:31:21,009 --> 00:31:23,050
Sest kui võrrelda
see, et sa ei kavatse

618
00:31:23,050 --> 00:31:25,530
midagi pärast seda
võrrelda, eks?

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

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

621
00:31:29,297 --> 00:31:30,380
Lisame meie sulgudes.

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

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

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

625
00:31:34,710 --> 00:31:39,117
Nii et meil on algusest
Meie välimine loop.

626
00:31:39,117 --> 00:31:41,450
Nüüd me ilmselt tahad
luua muutuja hoidmiseks

627
00:31:41,450 --> 00:31:43,085
jälgida väikseim väärtus, eks?

628
00:31:43,085 --> 00:31:45,751
Kas keegi taha mulle anda
koodirida, mis teha?

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

630
00:31:48,700 --> 00:31:53,570
Mida me vajame, kui me läheme
tahad salvestada midagi?

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

632
00:31:55,047 --> 00:31:57,630
Võib-olla õigem nimetus, mis
oleks olla-- "temp" täiesti works--

633
00:31:57,630 --> 00:32:00,655
võibolla rohkem tabavalt nimeks oleks,
Kui me tahame, et väikseim value--

634
00:32:00,655 --> 00:32:01,624
>> Sihtrühm: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: min, siis me läheme.

636
00:32:02,790 --> 00:32:05,230
min oleks hea.

637
00:32:05,230 --> 00:32:08,340
Ja nii siin, mida me
soovid täita seda?

638
00:32:08,340 --> 00:32:09,620
See on natuke keeruline.

639
00:32:09,620 --> 00:32:13,580
Sest just nüüd on
alguses see rida,

640
00:32:13,580 --> 00:32:15,730
Te ei ole uurinud midagi, eks?

641
00:32:15,730 --> 00:32:19,200
Mis siis, automaatselt, kui
me oleme lihtsalt i võrdub 0,

642
00:32:19,200 --> 00:32:22,302
Mida me tahame initsialiseerida
Meie esimene minimaalne väärtus?

643
00:32:22,302 --> 00:32:22,802
Sihtrühm: i.

644
00:32:22,802 --> 00:32:24,790
ANDI PENG: i, täpselt.

645
00:32:24,790 --> 00:32:27,040
Christabel, miks me tahame
initsialiseerida see i?

646
00:32:27,040 --> 00:32:28,510
>> Sihtrühm: Sest, noh,
me alustades 0.

647
00:32:28,510 --> 00:32:31,660
Nii et meil on midagi võrrelda
see on minimaalne lõpuks on 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI PENG: Täpselt.

649
00:32:32,451 --> 00:32:34,400
Nii ta on täpselt õige.

650
00:32:34,400 --> 00:32:36,780
Kuna meil ei ole tegelikult
vaatasin veel midagi,

651
00:32:36,780 --> 00:32:38,680
Me ei tea, mis meie minimaalne väärtus on.

652
00:32:38,680 --> 00:32:41,960
Tahame lihtsalt initsialiseerida see
i, mis praegu on siinsamas.

653
00:32:41,960 --> 00:32:44,750
Ja kui me jätkuvalt
liiguta alla selle massiiv,

654
00:32:44,750 --> 00:32:48,122
Me näeme, et iga
täiendavaid pass, i kaupa.

655
00:32:48,122 --> 00:32:49,830
Ja nii sel hetkel,
i on ilmselt läheb

656
00:32:49,830 --> 00:32:52,329
tahan olla minimaalne,
sest see saab olema iganes

657
00:32:52,329 --> 00:32:54,520
on algusest sortimata massiivi.

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

659
00:32:55,270 --> 00:32:58,720
>> Nüüd tahame lisada
jaoks silmus siin see on

660
00:32:58,720 --> 00:33:03,225
läheb itereerima läbi
sorteerimata või ülejäänud seda valikut.

661
00:33:03,225 --> 00:33:05,808
Kas keegi taha mulle
koodirida, mis teha?

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

663
00:33:08,870 --> 00:33:11,330
Hint-- mida me vajame siin?

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

665
00:33:17,320 --> 00:33:18,820
Mis toimub minna seda loop?

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

667
00:33:19,465 --> 00:33:21,590
Sihtrühm: Nii et me tahaks
on erinev täisarv

668
00:33:21,590 --> 00:33:25,080
sest meil hakkab läbi ülejäänud
massiivi asemel i, et äkki

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

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Jah, j kõlab hästi mulle.

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

672
00:33:27,850 --> 00:33:33,930
>> Sihtrühm: Nii oleks i pluss 1, sest
sa oled hakanud järgmisel väärtus.

673
00:33:33,930 --> 00:33:40,395
Ja siis väljatöötamiseni seda uuesti, j on
väiksem kui n miinus 1, ja siis j ++.

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

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

676
00:33:48,510 --> 00:33:52,750
>> Ja siis siin, me ei kavatse taha
vaadata, kui meie tingimus on täidetud,

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

678
00:33:53,250 --> 00:33:55,740
Sest sa tahad
muuta minimaalne väärtus

679
00:33:55,740 --> 00:33:58,700
kui see on tegelikult väiksem kui see, mida
Sa võrdled seda, eks?

680
00:33:58,700 --> 00:34:01,146
Mida me siis tahame siin?

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

682
00:34:04,160 --> 00:34:04,897
Saate näha.

683
00:34:04,897 --> 00:34:06,730
Mis tüüpi aruanne
me ilmselt läheb

684
00:34:06,730 --> 00:34:08,389
ti soovite kasutada, kui me
soovite kontrollida midagi?

685
00:34:08,389 --> 00:34:09,360
>> Sihtrühm: kui avaldus.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: kui avaldus.

687
00:34:10,485 --> 00:34:13,155
Nii kui-- ja mida saab olema
tingimusel, et me tahame sees

688
00:34:13,155 --> 00:34:13,988
Meie, kui avaldus?

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

690
00:34:18,255 --> 00:34:22,960
>> Sihtrühm: Kui väärtus j
on väiksem kui väärtus i--

691
00:34:22,960 --> 00:34:24,600
>> ANDI PENG: Täpselt.

692
00:34:24,600 --> 00:34:27,480
Nii kui-- nii see massiivi nimetatakse "massiivi."

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

694
00:34:27,980 --> 00:34:30,465
Nii et kui array-- mis see oli?

695
00:34:30,465 --> 00:34:31,090
Ütle, et uuesti.

696
00:34:31,090 --> 00:34:39,590
>> Sihtrühm: Kui massiiv-j alla
array-i, siis muudaks min.

697
00:34:39,590 --> 00:34:41,590
Nii min oleks j.

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

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Kas see on mõtet?

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

701
00:34:48,670 --> 00:34:52,929
Ja nüüd siin, me tegelikult
tahan rakendada swap, eks?

702
00:34:52,929 --> 00:34:58,285
Nii meenutavad loengu, et David, kui
Ta püüdis vahetada the-- mis oli

703
00:34:58,285 --> 00:34:59,996
see-- apelsinimahla ja milk--

704
00:34:59,996 --> 00:35:01,150
>> Sihtrühm: See oli raske.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Jah, see oli omamoodi raske.

706
00:35:02,816 --> 00:35:05,310
Aga see oli päris hea
mõiste näitab aeg.

707
00:35:05,310 --> 00:35:08,430
Nii et mõtle oma väärtusi siin.

708
00:35:08,430 --> 00:35:10,794
Sul massiivi
min, massiivi i,

709
00:35:10,794 --> 00:35:12,460
või mis iganes me üritasime vahetada siin.

710
00:35:12,460 --> 00:35:15,310
Ja siis ilmselt ei saa valada need
üksteist samal ajal, eks?

711
00:35:15,310 --> 00:35:17,180
Mida me läheme
et on vaja luua siin

712
00:35:17,180 --> 00:35:19,126
et vahetada väärtusi õigesti?

713
00:35:19,126 --> 00:35:19,820
>> Sihtrühm: Ajutine muutuja.

714
00:35:19,820 --> 00:35:21,370
>> ANDI PENG: Ajutine muutuja.

715
00:35:21,370 --> 00:35:22,570
Nii teeme int temp.

716
00:35:22,570 --> 00:35:25,681
Vt käesoleva oleks parem
aeg mina-- oot, mis see oli?

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

718
00:35:26,180 --> 00:35:29,800
Nii et see oleks olnud parem
aega nimetada muutuja "temp."

719
00:35:29,800 --> 00:35:30,730
Nii teeme int temp.

720
00:35:30,730 --> 00:35:32,563
Mida me saame
seada temp võrdne siin?

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

722
00:35:34,752 --> 00:35:35,335
Sihtrühm: Min?

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

724
00:35:38,508 --> 00:35:39,716
ANDI PENG: See on natuke keeruline.

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

726
00:35:43,110 --> 00:35:44,880
See tegelikult ei ole oluline, et lõpuks.

727
00:35:44,880 --> 00:35:47,690
See ei ole oluline milliseid
Et valida swap

728
00:35:47,690 --> 00:35:50,862
nii kaua, kui sa üritad kindel, et sa oled
jälgida, mida sa vahetada.

729
00:35:50,862 --> 00:35:52,250
>> Sihtrühm: See võiks olla massiiv-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Jah, teeme hulgaliselt-i.

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

732
00:35:55,950 --> 00:35:59,305
Ja mis siis on järgmisel real
koodi me tahame siin?

733
00:35:59,305 --> 00:36:00,680
Sihtrühm: array-i võrdub massiivi-j.

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

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: Ja lõpuks?

736
00:36:08,070 --> 00:36:12,070
Sihtrühm: array-j võrdub massiivi-i.

737
00:36:12,070 --> 00:36:14,525
Sihtrühm: Või array-j võrdsete
array-temp-- või 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
Nii saab käivitada ja vaata
kui see läheb tööle.

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

742
00:36:37,520 --> 00:36:39,335
Kus on, et juhtub?

743
00:36:39,335 --> 00:36:40,210
Oh, see on probleem.

744
00:36:40,210 --> 00:36:44,320
Vaata, real 40, me oleme
üritab kasutada massiivi-j?

745
00:36:44,320 --> 00:36:47,022
Kuid kust j olemas ainult?

746
00:36:47,022 --> 00:36:48,402
>> Sihtrühm: In silmus.

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

748
00:36:49,110 --> 00:36:51,730
Mida me siis peame tegema?

749
00:36:51,730 --> 00:36:53,170
>> Sihtrühm: määratleda väljaspool the--

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

751
00:36:57,777 --> 00:37:00,610
Sihtrühm: Jah, ma arvan, et teil on
kasutada teise if, eks?

752
00:37:00,610 --> 00:37:05,230
Nii nagu, kui miinimum--
Olgu, las ma mõtlen.

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

754
00:37:08,170 --> 00:37:09,990
>> ANDI PENG: Poisid, proovige
heita Olgem

755
00:37:09,990 --> 00:37:11,270
vaata, mida on midagi, mida me teha saame siin?

756
00:37:11,270 --> 00:37:11,811
>> Sihtrühm: OK.

757
00:37:11,811 --> 00:37:15,900
Nii et kui minimaalse ei võrdu
j-- nii et kui miinimum on ikka i--

758
00:37:15,900 --> 00:37:17,570
siis ei oleks meil vahetada.

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

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Kas see on võrdne i?

761
00:37:24,712 --> 00:37:25,920
Mida sa tahad öelda?

762
00:37:25,920 --> 00:37:30,494
>> Sihtrühm: Või jah, kui
Minimaalne ei võrdu i, yeah.

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
Noh, mis lahendab, millist meie probleeme.

766
00:37:42,040 --> 00:37:47,265
Aga see ikka ei lahenda
probleemi, mis juhtub, kui j-- kuna j

767
00:37:47,265 --> 00:37:49,890
ei ole olemas väljaspool seda, mida
sa tahame teha?

768
00:37:49,890 --> 00:37:50,698
Kuulutada välja?

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

770
00:37:59,410 --> 00:38:02,730
Proovime töötab see.

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

772
00:38:04,435 --> 00:38:06,200
Meie omamoodi ei tööta.

773
00:38:06,200 --> 00:38:10,060
>> Nagu näete, meie esialgne
massiiv oli neid väärtusi.

774
00:38:10,060 --> 00:38:14,800
Ja hiljem ta peaks olema
olnud 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
See ei tööta.

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

777
00:38:16,030 --> 00:38:17,184
Mida me siis teeme?

778
00:38:17,184 --> 00:38:17,850
Sihtrühm: Debug.

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

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: Okei, saame proovida seda.

781
00:38:23,370 --> 00:38:25,030
Saame siluda.

782
00:38:25,030 --> 00:38:26,042
Zoom out natuke.

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

784
00:38:31,177 --> 00:38:33,656
Räägime meie murdepunkti.

785
00:38:33,656 --> 00:38:37,280
Lähme like-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Nii, sest me juba teame, et
need read, 15 kuni 22,

787
00:38:40,444 --> 00:38:43,610
on working-- sest kõik, mida ma teen on
lihtsalt iterating läbi ja printing--

788
00:38:43,610 --> 00:38:45,406
Võin minna ja jäta see.

789
00:38:45,406 --> 00:38:47,280
Alustame kell line 25.

790
00:38:47,280 --> 00:38:48,712
Oop, lase mind lahti saada sellest.

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

792
00:38:51,598 --> 00:38:54,057
>> Sihtrühm: Nii murdepunkti on
kus silumine hakkab?

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: või seiskub.

794
00:38:54,890 --> 00:38:55,670
Sihtrühm: või seiskub.

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

796
00:38:55,930 --> 00:38:58,640
Võimalik on määrata mitu murdepunktid ja
see võib ainult hüpata ühest teise.

797
00:38:58,640 --> 00:39:01,590
Aga sel juhul me ei tea
kus viga juhtub.

798
00:39:01,590 --> 00:39:03,780
Nii et me lihtsalt tahame
alustada ülevalt alla.

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

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

801
00:39:05,550 --> 00:39:08,460
>> Nii et see joon siin, saame samm.

802
00:39:08,460 --> 00:39:11,499
Näete siin,
meil massiivi.

803
00:39:11,499 --> 00:39:13,290
Need on väärtused,
mis on massiiv.

804
00:39:13,290 --> 00:39:16,360
Kas te näete, et kui indeks 0, siis
vastab value-- oh,

805
00:39:16,360 --> 00:39:17,526
Ma lähen, et proovida suurendada.

806
00:39:17,526 --> 00:39:20,650
Vabandame, see on tõesti raske
to see-- kell massiivi indeks 0,

807
00:39:20,650 --> 00:39:24,090
meil on väärtus 4 ja
Seejärel neljanda ja nii edasi.

808
00:39:24,090 --> 00:39:25,670
Meil on kohalikud muutujad.

809
00:39:25,670 --> 00:39:28,570
Praegu i on võrdne
0, mida me tahame seda.

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

811
00:39:31,540 --> 00:39:33,690
>> Ja nii Jätame astutakse läbi.

812
00:39:33,690 --> 00:39:36,850
Meie miinimum on võrdne 0,
mida me ka tahame seda.

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

814
00:39:39,470 --> 00:39:45,560
Ja siis me siseneda meie sekundis
loop, kui massiiv-j on väiksem kui massiivi-i,

815
00:39:45,560 --> 00:39:46,380
mida ta ei olnud.

816
00:39:46,380 --> 00:39:48,130
Nii sa nägid, kuidas
et vahele üle, et?

817
00:39:48,130 --> 00:39:52,430
>> Sihtrühm: Nii peaks, kui
minimaalne, kõik selle-- ei tohiks see

818
00:39:52,430 --> 00:39:55,424
sees esimene silmus?

819
00:39:55,424 --> 00:39:57,340
ANDI PENG: Ei, sest
sa ikka tahad testida.

820
00:39:57,340 --> 00:40:00,329
Sa tahad teha võrdluse iga
aega, isegi pärast sa jooksed läbi.

821
00:40:00,329 --> 00:40:02,620
Sul ei ole lihtsalt tahan seda teha
Esimesel läbipääs.

822
00:40:02,620 --> 00:40:05,240
Sa tahad seda teha
Iga täiendava pass uuesti.

823
00:40:05,240 --> 00:40:07,198
Nii et sa tahad, et kontrollida
Teie seisundi sees.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Nii et me lihtsalt läheb
hoida läbiv siin.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Ma annan sulle poisid vihje.

828
00:40:18,420 --> 00:40:23,910
See on seotud asjaoluga, et kui
loed oma tingimuseks,

829
00:40:23,910 --> 00:40:26,600
sa ei kontrolliks
õige indeks.

830
00:40:26,600 --> 00:40:32,510
Nii kohe loed jaoks
massiivi indeks j on väiksem kui massiivi

831
00:40:32,510 --> 00:40:33,970
indeks i.

832
00:40:33,970 --> 00:40:36,580
Aga mida sa teed üles
Alguses silmus?

833
00:40:36,580 --> 00:40:38,260
Kas sa ei kehtestamisel j võrdne i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Jah, nii saame tegelikult
väljumiseks siluri siin.

836
00:40:45,415 --> 00:40:47,040
Võtame pilk meie pseudokoodi.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- läheme
start kell i võrdub 0.

839
00:40:52,580 --> 00:40:54,760
Me läheme kuni n miinus 1.

840
00:40:54,760 --> 00:40:58,040
Kontrollime, kas meil on see õige?

841
00:40:58,040 --> 00:40:59,580
Yep, et oli õige.

842
00:40:59,580 --> 00:41:02,080
>> Siis sees siin, me oleme
kavatse luua minimaalne väärtus

843
00:41:02,080 --> 00:41:03,630
ja määrata, et võrdne i.

844
00:41:03,630 --> 00:41:04,950
Kas me seda teeme?

845
00:41:04,950 --> 00:41:06,270
Yep, tegin seda.

846
00:41:06,270 --> 00:41:10,430
Nüüd on meie sisemine silmus, me oleme
kavatseb teha j võrdub i kuni n miinus 1.

847
00:41:10,430 --> 00:41:11,950
Kas me seda teeme?

848
00:41:11,950 --> 00:41:15,540
Tõepoolest, me tegime seda.

849
00:41:15,540 --> 00:41:19,922
>> Nii aga mida me võrrelda siin?

850
00:41:19,922 --> 00:41:20,925
>> Sihtrühm: j pluss 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Täpselt.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
Ja siis sa lähed soovite seada
Sinu minimaalne võrdne j pluss 1 samuti.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Nii et ma läksin läbi, et tõesti kiiresti.

856
00:41:32,640 --> 00:41:36,190
Kas te poisid aru
miks see j pluss 1?

857
00:41:36,190 --> 00:41:36,890
OKEI.

858
00:41:36,890 --> 00:41:40,700
>> Nii oma rida, in
Sinu esimese läbida,

859
00:41:40,700 --> 00:41:44,850
Sinu jaoks silmus, et int
i võrdub 0, olgem lihtsalt

860
00:41:44,850 --> 00:41:46,740
oletame, et tegemist ei ole veel muutunud.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Meil on hulgaliselt, täiesti,
vaid nelja sorteerimata elemente, eks?

863
00:41:56,760 --> 00:42:00,760
Nii et me tahame initsialiseerida i võrdne 0.

864
00:42:00,760 --> 00:42:03,650
Ja ma ei kavatse lihtsalt
jookseb läbi selle silmuse.

865
00:42:03,650 --> 00:42:08,560
Ja nii esimeses pass, me ei kavatse
initsialiseerida muutuja nimega "min"

866
00:42:08,560 --> 00:42:11,245
et ka võrdne i, sest
meil ei ole minimaalset väärtust.

867
00:42:11,245 --> 00:42:12,870
Nii et praegu on võrdne 0 samuti.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
Ja siis me läheme läbi.

870
00:42:17,640 --> 00:42:19,270
Ja me tahame korrata uuesti.

871
00:42:19,270 --> 00:42:22,900
Nüüd, kui oleme leidnud selle, mida meie miinimum
on, me tahame korrata läbi

872
00:42:22,900 --> 00:42:25,190
uuesti näha, kas see on võrreldes, eks?

873
00:42:25,190 --> 00:42:40,440
Nii j, siin läheb
võrdsele i, mis on 0.

874
00:42:40,440 --> 00:42:46,320
Ja siis, kui massiivi j pluss i, mis
on see, et järgmiseks üle, kui vähem

875
00:42:46,320 --> 00:42:49,270
kui see, mida teie praegune minimaalne
väärtus on, tahad vahetada.

876
00:42:49,270 --> 00:42:56,850
>> Nii ütleme lihtsalt me ​​oleme
sai, nagu, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Just nüüd, ma on võrdne
0 ja j on võrdne 0.

878
00:43:01,610 --> 00:43:05,210
Ja see on meie miinimumi.

879
00:43:05,210 --> 00:43:09,950
Kui massiiv-j pluss i-- nii et kui üks
see on pärast üht me vaatame

880
00:43:09,950 --> 00:43:13,450
on suurem kui esimene enne,
see saab muutuda minimaalne.

881
00:43:13,450 --> 00:43:18,120
>> Nii et siin me näeme, et 5
ei ole vähem.

882
00:43:18,120 --> 00:43:19,730
Nii see läheb ei ole 5.

883
00:43:19,730 --> 00:43:23,580
Me näeme, et 1 on alla 2, eks?

884
00:43:23,580 --> 00:43:32,970
Nüüd me teame, et meie miinimum
saab olema indeksi väärtus 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Jah?

886
00:43:34,030 --> 00:43:39,170
Ja siis, kui sa siin,
saab vahetada õige väärtusi.

887
00:43:39,170 --> 00:43:42,610
>> Nii et kui te poisid olid lihtsalt võttes j
Enne, sa ei vaata ühe

888
00:43:42,610 --> 00:43:43,260
pärast seda.

889
00:43:43,260 --> 00:43:44,520
Sa otsisid
sama väärtusega, mis

890
00:43:44,520 --> 00:43:46,290
Sellepärast ta lihtsalt ei tee midagi.

891
00:43:46,290 --> 00:43:49,721
Kas see mõtet kõigile,
miks meil on vaja, et pluss 1 on?

892
00:43:49,721 --> 00:43:50,220
OKEI.

893
00:43:50,220 --> 00:43:53,345
Nüüd lihtsalt jookseb läbi see, et
Kindlasti ülejäänud kood on õige.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Miks on see juhtub?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, see on min siin.

898
00:44:16,364 --> 00:44:17,780
Olime võrrelda vale väärtus.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Oh ei.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh yeah, siia alla olime
Vahetatakse vale väärtuste samuti.

903
00:44:33,482 --> 00:44:34,940
Kuna otsisime i ja j.

904
00:44:34,940 --> 00:44:36,440
Need on need, olime kontrollida.

905
00:44:36,440 --> 00:44:39,160
Me tegelikult tahad vahetada
vähemalt praeguse minimaalne,

906
00:44:39,160 --> 00:44:40,550
iganes see väljaspool on.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
Ja kui poisid ei vaata alla
siin on meil sorteeritud massiivi.

909
00:45:05,402 --> 00:45:07,110
See lihtsalt oli pistmist
asjaolu, et kui

910
00:45:07,110 --> 00:45:09,350
olime kontrollimine
väärtusi meid võrrelda,

911
00:45:09,350 --> 00:45:11,226
me ei otsinud õigel väärtusi.

912
00:45:11,226 --> 00:45:13,850
Otsisime samal ühe
Siin ei ole tegelikult see vahetada.

913
00:45:13,850 --> 00:45:17,135
Sul on vaadata ühe järgmise
seda ja siis saate vahetada.

914
00:45:17,135 --> 00:45:19,260
Nii et see, mis oli omamoodi
pealtkuulamise meie koodi enne.

915
00:45:19,260 --> 00:45:22,460
Ja mida ma tegin siin on kõike
siluri oleks võinud teha teile

916
00:45:22,460 --> 00:45:23,810
Ma lihtsalt tegin seda kohta
pardal, sest see on lihtsam

917
00:45:23,810 --> 00:45:26,320
näha selle asemel
suumimiseks siluri.

918
00:45:26,320 --> 00:45:29,391
Kas see mõtet kõigile?

919
00:45:29,391 --> 00:45:29,890
Cool.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Hästi.

922
00:45:35,410 --> 00:45:41,070
Me saame liikuda edasi rääkima
asümptootilise märke, mis

923
00:45:41,070 --> 00:45:44,580
on lihtsalt fancy viis öelda
runtimes kõiki neid kehvasti.

924
00:45:44,580 --> 00:45:47,650
Nii et ma tean, David, loengus,
puudutanud runtimes.

925
00:45:47,650 --> 00:45:52,124
Ja ta käis läbi kogu valem
kuidas arvutada runtimes.

926
00:45:52,124 --> 00:45:53,040
Ära muretse selle pärast.

927
00:45:53,040 --> 00:45:54,660
Kui sa oled tõesti uudishimulik
kuidas see töötab,

928
00:45:54,660 --> 00:45:55,810
julgelt minuga rääkida pärast osa.

929
00:45:55,810 --> 00:45:57,560
Me ei käi
valemid koos.

930
00:45:57,560 --> 00:46:00,689
Aga kõik kutid on tõesti
tean, et n ruudus jagatud 2

931
00:46:00,689 --> 00:46:01,980
on sama asi nagu n ruudus.

932
00:46:01,980 --> 00:46:04,710
Kuna kõige rohkem,
astendaja, kasvab kõige.

933
00:46:04,710 --> 00:46:06,590
Ja nii meie eesmärkidel,
kõik me hoolime

934
00:46:06,590 --> 00:46:09,470
on see, et hiiglane number, mis on kasvanud.

935
00:46:09,470 --> 00:46:13,340
>> Mis on parimal juhul
Runtime valiku omamoodi?

936
00:46:13,340 --> 00:46:15,830
Kui sa lähed on
itereerima läbi nimekirja

937
00:46:15,830 --> 00:46:18,712
ja siis korrata läbi
ülejäänud seda nimekirja,

938
00:46:18,712 --> 00:46:20,420
mitu korda on
sa lähed ilmselt,

939
00:46:20,420 --> 00:46:24,612
halvimal case-- on
Parimal juhul sorry-- joosta?

940
00:46:24,612 --> 00:46:27,070
Võib-olla on parem küsimus on
küsida, milline on kõige mustema

941
00:46:27,070 --> 00:46:28,153
Runtime valiku omamoodi.

942
00:46:28,153 --> 00:46:29,366
Sihtrühm: n ruudus.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: See on n ruudus, eks.

944
00:46:30,740 --> 00:46:36,986
Nii lihtne mõelda see on nagu,
iga kord, kui on kaks pesitseda jaoks silmuseid,

945
00:46:36,986 --> 00:46:38,110
see saab olema n ruudus.

946
00:46:38,110 --> 00:46:40,386
Sest mitte ainult sa
läbiv taas

947
00:46:40,386 --> 00:46:42,260
sa pead minema tagasi
ümber ja jookseb läbi see

948
00:46:42,260 --> 00:46:44,980
jälle sees iga väärtus.

949
00:46:44,980 --> 00:46:48,640
Nii et juhul, näed n
korda n ruudus, mis on-- vabandust,

950
00:46:48,640 --> 00:46:50,505
n korda n, mis võrdub n ruudus.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Ja omamoodi on ka natuke
unikaalne selles mõttes,

953
00:46:56,360 --> 00:46:59,774
et see ei ole oluline, kas need
väärtused on juba selleks.

954
00:46:59,774 --> 00:47:01,440
See on ikka läbiks niikuinii.

955
00:47:01,440 --> 00:47:03,872
Ütleme nii, et see oli 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Sõltumata sellest, kas see oli
Selleks, et ikka oleks jooksis läbi

957
00:47:07,080 --> 00:47:08,620
ja veel kontrollida minimaalne väärtus.

958
00:47:08,620 --> 00:47:10,100
See oleks teinud
Sama arvu kontrolli

959
00:47:10,100 --> 00:47:12,780
iga kord, isegi kui see
tegelikult ei puutu midagi.

960
00:47:12,780 --> 00:47:16,940
>> Nii sellisel juhul paremini ja halvemini
runtimes on tegelikult samaväärne.

961
00:47:16,940 --> 00:47:19,160
Nii et oodata runtime
Valiku omamoodi,

962
00:47:19,160 --> 00:47:23,790
millele meil määrata sümboliga
beta, teeta, sel juhul

963
00:47:23,790 --> 00:47:24,790
Samuti oleks n ruudus.

964
00:47:24,790 --> 00:47:26,480
Kõik need kolm oleks n ruudus.

965
00:47:26,480 --> 00:47:29,653
Kas kõik selge, miks
Runtime on n ruudus?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Hästi.

968
00:47:33,980 --> 00:47:39,120
Nii et ma olen lihtsalt läheb kiiresti käivitada
läbi ülejäänud kehvasti.

969
00:47:39,120 --> 00:47:41,137
Algoritmi
mull sort-- mäletan,

970
00:47:41,137 --> 00:47:43,220
see oli esimene
David läks üle loengus.

971
00:47:43,220 --> 00:47:46,000
Sisuliselt sa samm
läbi kogu nimekiri

972
00:47:46,000 --> 00:47:48,950
ja sa swap-- sa lihtsalt
võrrelda kahte korraga.

973
00:47:48,950 --> 00:47:51,350
Ja kui üks on suurem,
kui sa lihtsalt vahetada neid.

974
00:47:51,350 --> 00:47:53,590
Nii et kui need on suuremad, siis oleks vahetada.

975
00:47:53,590 --> 00:47:56,180
Mul ametlik siin.

976
00:47:56,180 --> 00:47:59,100
>> Nii ütleme lihtsalt sul oli 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Sa võrrelda 8 ja 6.

978
00:48:00,571 --> 00:48:01,570
Sa pead vahetada neid.

979
00:48:01,570 --> 00:48:02,610
Sa oleks võrrelda 8 ja 4.

980
00:48:02,610 --> 00:48:03,609
Sa pead vahetada neid.

981
00:48:03,609 --> 00:48:07,000
Kui teil on vahetada 8 ja
2, muuta neid samuti.

982
00:48:07,000 --> 00:48:10,760
Nii selline tunne, näete,
mängitakse läbi pika aja jooksul,

983
00:48:10,760 --> 00:48:13,730
kuidas väärtused mingi mull
otsad, mis on, miks me nimetame seda

984
00:48:13,730 --> 00:48:15,320
mull omamoodi.

985
00:48:15,320 --> 00:48:19,950
>> Me lihtsalt joosta uuesti
Meie teine ​​pass, ja meie kolmas pass,

986
00:48:19,950 --> 00:48:21,150
ja meie neljas pass.

987
00:48:21,150 --> 00:48:25,820
Sisuliselt mull omamoodi lihtsalt jookseb
kuni sa ei tee enam vahetustehinguid.

988
00:48:25,820 --> 00:48:31,109
Nii selles mõttes, et see on lihtsalt
üldise pseudokoodi ta.

989
00:48:31,109 --> 00:48:32,650
Ära muretse, need kõik on online.

990
00:48:32,650 --> 00:48:34,990
Me ei pea tegelikult minna üle selle.

991
00:48:34,990 --> 00:48:38,134
>> Me lihtsalt initsialiseerida counter
muutuja, mis algab 0.

992
00:48:38,134 --> 00:48:39,800
Ja me korrata läbi terve rea.

993
00:48:39,800 --> 00:48:43,420
Ja kui üks väärtus on-- kui see
väärtus on suurem kui väärtus,

994
00:48:43,420 --> 00:48:44,610
sa lähed, et vahetada neid.

995
00:48:44,610 --> 00:48:46,860
Ja siis sa oled lihtsalt
läheb edasi.

996
00:48:46,860 --> 00:48:47,970
Ja sa lähed loota.

997
00:48:47,970 --> 00:48:50,845
Ja sa oled lihtsalt kavatse hoida teed
Käesoleva samas lugeja suurem

998
00:48:50,845 --> 00:48:53,345
kui 0, mis tähendab, et
iga kord, sa pead swap,

999
00:48:53,345 --> 00:48:55,220
sa tead sa tahad minna
tagasi ja vaadata uuesti.

1000
00:48:55,220 --> 00:48:59,510
Sa tahad, et hoida kontrolli kuni te ei tea
et sa ei pea vahetada enam.

1001
00:48:59,510 --> 00:49:05,570
>> Mis on parim ja halvim
Juhul runtimes mull omamoodi?

1002
00:49:05,570 --> 00:49:09,300
Ja hint-- see on tegelikult erinev
valikust omamoodi mõttes

1003
00:49:09,300 --> 00:49:11,810
et need kaks vastust ei ole samad.

1004
00:49:11,810 --> 00:49:14,709
Mõelge, mis juhtuks
juhul, kui see oli juba järjestatud.

1005
00:49:14,709 --> 00:49:16,500
Ja mõelda, mida
juhtuks, kui see oli

1006
00:49:16,500 --> 00:49:18,372
puhul, kus see ei järjestatud.

1007
00:49:18,372 --> 00:49:20,580
Ja saab omamoodi joosta
läbi, miks see juhtub.

1008
00:49:20,580 --> 00:49:22,954
Ma annan sulle poisid, nagu, 30
sekundit mõelda seda.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> OKEI.

1011
00:49:53,540 --> 00:49:57,462
Kas keegi on vist see, mida
Halvimal juhul runtime mull sorteerida on?

1012
00:49:57,462 --> 00:49:57,962
Jah.

1013
00:49:57,962 --> 00:50:07,810
>> Sihtrühm: see oleks nagu, n korda
n miinus 1 või midagi sellist?

1014
00:50:07,810 --> 00:50:10,650
Nagu iga kord, kui ta jookseb,
see on lihtsalt, nagu üks swap vähem

1015
00:50:10,650 --> 00:50:10,960
mis iganes see oli.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Jah, nii
sa oled täiesti õige.

1017
00:50:12,668 --> 00:50:15,940
Ja see on juhtum, kus oma
Vastus oli tegelikult keerulisem

1018
00:50:15,940 --> 00:50:17,240
kui üks peame andma.

1019
00:50:17,240 --> 00:50:19,772
Nii see läheb run-- ma olen
läheb kustutab kõik see siin.

1020
00:50:19,772 --> 00:50:20,480
Kas kõik hea?

1021
00:50:20,480 --> 00:50:21,869
Kas ma saan kustutada selle?

1022
00:50:21,869 --> 00:50:22,368
OKEI.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Sa lähed joosta n
korda esmakordselt, eks?

1025
00:50:30,320 --> 00:50:33,200
Ja nad ei kavatse joosta
n miinus 1 teine ​​kord, eks?

1026
00:50:33,200 --> 00:50:37,130
Ja siis sa lähed hoida
läheb, n minu 2, jne.

1027
00:50:37,130 --> 00:50:40,210
Taavet tegi seda loengus, kus
Kui te liita kõik need väärtused,

1028
00:50:40,210 --> 00:50:48,080
sa saad midagi, mis on like-- yeah--
üle 2, mis oma olemuselt lihtsalt vähendab

1029
00:50:48,080 --> 00:50:49,784
alla n ruudus.

1030
00:50:49,784 --> 00:50:51,700
Sa lähed, et saada
imelik osa seal.

1031
00:50:51,700 --> 00:50:53,892
Ja nii lihtsalt tean, et
n ruudus alati

1032
00:50:53,892 --> 00:50:55,350
ülimuslik osa.

1033
00:50:55,350 --> 00:50:58,450
Ja nii sel juhul, halvimal
Runtime oleks n ruudus.

1034
00:50:58,450 --> 00:51:00,210
Kui see oli kahanevas
Selleks, arvan, sa

1035
00:51:00,210 --> 00:51:02,530
pead tegema swap iga kord.

1036
00:51:02,530 --> 00:51:05,170
>> Mis oleks, potentsiaalselt
Parimal juhul runtime?

1037
00:51:05,170 --> 00:51:08,580
Ütleme lihtsalt, kui loetelu on juba
selleks, milline oleks Runtime olla?

1038
00:51:08,580 --> 00:51:09,565
>> Sihtrühm: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: See on n, täpselt.

1040
00:51:10,690 --> 00:51:11,600
Ja miks on see n?

1041
00:51:11,600 --> 00:51:13,850
Sihtrühm: Sest sa lihtsalt
kontrollima iga kord.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Täpselt.

1043
00:51:14,770 --> 00:51:17,150
Nii parimal võimalikul runtime,
kui see nimekiri oli juba

1044
00:51:17,150 --> 00:51:20,270
sorted-- oletame 1, 2, 3, 4-- sa
oleks lihtsalt läbi minema, siis oleks vaadata,

1045
00:51:20,270 --> 00:51:21,720
sa näeksid, oh, nad kõik üle viia.

1046
00:51:21,720 --> 00:51:22,636
Ma ei pea vahetama.

1047
00:51:22,636 --> 00:51:23,370
Olen lõpetanud.

1048
00:51:23,370 --> 00:51:26,500
Nii et juhul, see on lihtsalt n
või mitmeid samme sa lihtsalt

1049
00:51:26,500 --> 00:51:29,870
oli kontrollida esimeses nimekirja.

1050
00:51:29,870 --> 00:51:33,990
>> Ja pärast, nüüd tabas
sisestamise sorteerida, kus

1051
00:51:33,990 --> 00:51:39,260
algoritm on sisuliselt lõhe
see sorditud ja sortimata osa.

1052
00:51:39,260 --> 00:51:42,810
Ja siis ükshaaval
sorteerimata väärtused

1053
00:51:42,810 --> 00:51:46,880
lisada oma asjakohased
positsioone loendi alguses.

1054
00:51:46,880 --> 00:51:52,120
>> Nii näiteks on meil
nimekiri 3, 5, 2, 6, 4 uuesti.

1055
00:51:52,120 --> 00:51:54,750
Me teame, et see on praegu
sorteerimata sest oleme lihtsalt

1056
00:51:54,750 --> 00:51:57,030
Hakkasin uurima seda.

1057
00:51:57,030 --> 00:52:00,610
Me vaatleme ja me teame, et
esimene väärtus on järjestatud, eks?

1058
00:52:00,610 --> 00:52:04,190
Kui oled ainus vaadates massiivi
suurus ühe, sa tead, et see on järjestatud.

1059
00:52:04,190 --> 00:52:08,230
>> Nii siis me teame, et
Ülejäänud neli sorteerimata.

1060
00:52:08,230 --> 00:52:10,980
Me läheme läbi ja me näeme, et väärtus.

1061
00:52:10,980 --> 00:52:11,730
Lähme tagasi.

1062
00:52:11,730 --> 00:52:13,130
Vaata, et väärtus 5?

1063
00:52:13,130 --> 00:52:14,110
Me vaatleme seda.

1064
00:52:14,110 --> 00:52:15,204
Me võrdleme seda 3.

1065
00:52:15,204 --> 00:52:17,870
Me teame, et see on suurem kui
3, nii et me teame, et see on järjestatud.

1066
00:52:17,870 --> 00:52:22,940
Nii et me teame nüüd, et kaks esimest
on järjestatud ja viimased kolm ei ole.

1067
00:52:22,940 --> 00:52:24,270
>> Me vaatleme 2.

1068
00:52:24,270 --> 00:52:25,720
Kõigepealt vaadake seda 5.

1069
00:52:25,720 --> 00:52:26,700
Kas see on väiksem kui 5?

1070
00:52:26,700 --> 00:52:27,240
See ei ole.

1071
00:52:27,240 --> 00:52:29,510
Nii et me peame hoidma alla vaadates.

1072
00:52:29,510 --> 00:52:30,940
Siis vaadake 2 välja 3.

1073
00:52:30,940 --> 00:52:31,850
Kas see vähem kui?

1074
00:52:31,850 --> 00:52:32,350
Ei.

1075
00:52:32,350 --> 00:52:35,430
Nii et sa tead 2 tuleb lisada
arvesse ees ja 3 ja 5

1076
00:52:35,430 --> 00:52:38,200
Nii tuleb välja lükata.

1077
00:52:38,200 --> 00:52:42,190
Tehke seda jälle 6 ja 4.

1078
00:52:42,190 --> 00:52:48,962
Ja me lihtsalt hoida kontrolli sisuliselt
kus me lihtsalt vaadata, vaadata, vaadata.

1079
00:52:48,962 --> 00:52:51,170
Ja kuni see on õiges
positsioon, meil sellist lihtsalt

1080
00:52:51,170 --> 00:52:54,890
pistke see õiges asendis,
mis on nime korral see tuli.

1081
00:52:54,890 --> 00:52:59,830
>> Nii et lihtsalt algoritm,
pseudokoodi per se, omamoodi,

1082
00:52:59,830 --> 00:53:04,990
kuidas me ellu
insertsioonis omamoodi.

1083
00:53:04,990 --> 00:53:05,954
Pseudokoodi on siin.

1084
00:53:05,954 --> 00:53:06,620
See kõik on online.

1085
00:53:06,620 --> 00:53:10,720
Ära muretse, kui teiega on
üritab kopeerida selle alla.

1086
00:53:10,720 --> 00:53:14,500
Nii et taas, sama question-- mida
oleks parim ja halvim runtimes

1087
00:53:14,500 --> 00:53:16,120
sisestamiseks omamoodi?

1088
00:53:16,120 --> 00:53:17,750
See on väga sarnane viimasele küsimusele.

1089
00:53:17,750 --> 00:53:20,479
Ma annan sulle poisid, nagu, 30
sekundit mõtlema ka.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Kas keegi taha
mulle halvim runtime?

1092
00:53:50,071 --> 00:53:50,570
Jah.

1093
00:53:50,570 --> 00:53:51,490
>> Sihtrühm: n ruudus.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI PENG: See on n ruudus.

1095
00:53:52,573 --> 00:53:53,730
Ja miks on see n ruudus?

1096
00:53:53,730 --> 00:53:57,562
>> Sihtrühm: Sest
vastupidises järjekorras, siis on

1097
00:53:57,562 --> 00:54:02,619
läbima n korda n, mis on--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Jah, täpselt.

1099
00:54:03,660 --> 00:54:06,610
Nii sama asi nagu mull omamoodi.

1100
00:54:06,610 --> 00:54:08,720
Kui see nimekiri on
järjekorras, et sa oled

1101
00:54:08,720 --> 00:54:11,240
läheb on kõigepealt kontrollida üks kord.

1102
00:54:11,240 --> 00:54:13,470
Ja siis iga
lisaväärtust, sa oled

1103
00:54:13,470 --> 00:54:16,390
läheb on võrdlemisel
iga väärtus, eks?

1104
00:54:16,390 --> 00:54:20,290
Ja nii kokku, sa lähed tegema
n pass korda teise n läbida, mis

1105
00:54:20,290 --> 00:54:21,750
on n ruudus.

1106
00:54:21,750 --> 00:54:22,860
Aga parim juhtum?

1107
00:54:22,860 --> 00:54:24,360
Jah.

1108
00:54:24,360 --> 00:54:28,840
>> Sihtrühm: n miinus 1, sest
Esimene neist on juba ruudus.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Nii lähedal.

1110
00:54:30,270 --> 00:54:31,850
Vastus on tegelikult n.

1111
00:54:31,850 --> 00:54:37,189
Kuna samal ajal esimene on
sorteeritud, ei pruugi see actually-- see

1112
00:54:37,189 --> 00:54:38,980
me lihtsalt lucked tegemiseks,
et näiteks, et 2

1113
00:54:38,980 --> 00:54:40,930
juhtus olema väikseim number.

1114
00:54:40,930 --> 00:54:43,680
Aga see ei ole alati nii.

1115
00:54:43,680 --> 00:54:48,040
Kui 2 on juba järjestatud alguses
aga sa vaatad ja seal on 1 siin,

1116
00:54:48,040 --> 00:54:49,144
1 läheb juhtuma see.

1117
00:54:49,144 --> 00:54:51,060
Ja see läheb lõpuks
up on lõin niikuinii.

1118
00:54:51,060 --> 00:54:56,250
>> Nii et parimal juhul,
see on tegelikult lihtsalt saab olema n.

1119
00:54:56,250 --> 00:54:59,090
Kui teil on 1, 2, 3,
4, 5, 6, 7, 8, sa oled

1120
00:54:59,090 --> 00:55:00,940
läbiks
et kogu nimekirja kord

1121
00:55:00,940 --> 00:55:03,430
vaadata, kas kõik on korras.

1122
00:55:03,430 --> 00:55:07,390
Kas kõik selge jooksmine
korda valiku ka?

1123
00:55:07,390 --> 00:55:09,960
Ma tean, et ma lähen läbi
Nende tõesti kiire.

1124
00:55:09,960 --> 00:55:13,330
Aga tean, et kui sa tead
üldmõisteid, siis peaks olema hea.

1125
00:55:13,330 --> 00:55:16,070
OKEI.

1126
00:55:16,070 --> 00:55:19,790
Nii et ma lihtsalt annan teile poisid äkki, nagu,
minut rääkida oma naabritega

1127
00:55:19,790 --> 00:55:21,890
mida on vaid mõned
peamisi erinevusi

1128
00:55:21,890 --> 00:55:23,540
nende tüüpide vahel kehvasti.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Me läheme üle, et varsti.

1131
00:56:25,570 --> 00:56:26,444
Sihtrühm: Oh, OK.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Jah.

1133
00:56:27,320 --> 00:56:28,380
OKEI.

1134
00:56:28,380 --> 00:56:33,420
Cool, olgem taasalustama klassina.

1135
00:56:33,420 --> 00:56:34,330
OKEI.

1136
00:56:34,330 --> 00:56:37,579
Nii et see oli omamoodi
avatud küsimus selles mõttes,

1137
00:56:37,579 --> 00:56:39,120
et seal on palju vastuseid neile.

1138
00:56:39,120 --> 00:56:40,746
Ja me läheme üle mõned neist lühidalt.

1139
00:56:40,746 --> 00:56:43,411
Ma lihtsalt tahtsin sulle poisid
mõelda, mida eristab

1140
00:56:43,411 --> 00:56:44,530
kõigi kolme sorti.

1141
00:56:44,530 --> 00:56:47,440
Ja ma kuulsin ka, suur
question-- mida ei Merge omamoodi teha?

1142
00:56:47,440 --> 00:56:50,110
Hea küsimus, sest see on
mida me hõlmava kõrval.

1143
00:56:50,110 --> 00:56:52,850
>> Nii liita omamoodi on
üks omamoodi, mis toimib

1144
00:56:52,850 --> 00:56:56,100
väga erinevalt teistest kehvasti.

1145
00:56:56,100 --> 00:56:58,180
Nagu te poisid saavad see--
Taavet seda teha demo

1146
00:56:58,180 --> 00:57:01,130
kus ta oli kõik lahe
müra näha, kuidas ühendada

1147
00:57:01,130 --> 00:57:04,010
Sorteeri jooksis, nagu, lõpmatult
kiiremini kui teised kaks liiki?

1148
00:57:04,010 --> 00:57:04,510
OKEI.

1149
00:57:04,510 --> 00:57:07,580
Nii et sellepärast ühendamine
Sorteeri rakendab et lõhe

1150
00:57:07,580 --> 00:57:11,020
ja vallutada mõiste, et me oleme
rääkisime palju loengus.

1151
00:57:11,020 --> 00:57:14,550
Selles mõttes, et meile meeldib töötada
targemaks, ei raskem, kui jagate

1152
00:57:14,550 --> 00:57:18,120
ja vallutada probleeme, ja murda neid
maha ja siis pane need kokku,

1153
00:57:18,120 --> 00:57:19,930
head asjad alati juhtuma.

1154
00:57:19,930 --> 00:57:21,960
>> Nii nii, et ühendada
Sorteeri sisuliselt töötab

1155
00:57:21,960 --> 00:57:24,660
on, et see jagab
sorteerimata massiivi poole.

1156
00:57:24,660 --> 00:57:26,500
Ja siis see ju kaks poolt massiivid.

1157
00:57:26,500 --> 00:57:28,220
Ja see lihtsalt sorteerib need kaks poolt.

1158
00:57:28,220 --> 00:57:31,750
See lihtsalt hoiab jagades pooleks, in
pool, poole, kuni kõik on järjestatud

1159
00:57:31,750 --> 00:57:33,680
ja siis rekursiivselt
paneb see kõik koos.

1160
00:57:33,680 --> 00:57:36,550
>> Nii et tõesti abstraktne.

1161
00:57:36,550 --> 00:57:38,750
Nii et see on lihtsalt natuke pseudokoodi.

1162
00:57:38,750 --> 00:57:41,040
Kas see mõtet
kuidas see töötab?

1163
00:57:41,040 --> 00:57:43,870
Nii ütleme lihtsalt teil on
massiivi n elementi, eks?

1164
00:57:43,870 --> 00:57:45,450
Kui n on väiksem kui 2, siis saad tagasi.

1165
00:57:45,450 --> 00:57:49,040
Sest sa tead, et kui seal on
Ainult üks asi, see tuleb sorteerida.

1166
00:57:49,040 --> 00:57:52,600
Else, sorteerida vasakul pool,
ja siis sorteerida õige poole,

1167
00:57:52,600 --> 00:57:54,140
ja siis liita.

1168
00:57:54,140 --> 00:57:56,979
>> Niisiis, kui see tundub tõesti lihtne,
tegelikult mõelda seda on

1169
00:57:56,979 --> 00:58:00,270
Selline keeruline. Sest sa oled nagu,
Noh, see on omamoodi töötab ise.

1170
00:58:00,270 --> 00:58:00,769
Õigus?

1171
00:58:00,769 --> 00:58:02,430
See töötab ise.

1172
00:58:02,430 --> 00:58:05,479
Nii selles mõttes, David puudutanud
upon recursion klassis.

1173
00:58:05,479 --> 00:58:07,270
Ja see mõiste
me räägime rohkem.

1174
00:58:07,270 --> 00:58:11,430
See, et asjaolu, et need kaks rida
siin, tegelikult on lihtsalt programm

1175
00:58:11,430 --> 00:58:13,860
ütlen seda käivitada ise
erinevate sisend.

1176
00:58:13,860 --> 00:58:17,230
Nii et pigem joosta ennast
tervikuna n elementi,

1177
00:58:17,230 --> 00:58:20,530
saab jaotada see sisse
vasakul pool ja paremal pool

1178
00:58:20,530 --> 00:58:22,680
ja seejärel käivitage see uuesti.

1179
00:58:22,680 --> 00:58:26,050
>> Ja siis me vaatame seda visuaalselt,
sest ma olen visuaalne õppija.

1180
00:58:26,050 --> 00:58:27,270
See toimib paremini mulle.

1181
00:58:27,270 --> 00:58:29,890
Nii me vaatame visuaalne näide.

1182
00:58:29,890 --> 00:58:36,237
>> Oletame, et meil on hulgaliselt kuus
elemente, 3, 5, 2, 6, 4, 1, mitte sorteerida.

1183
00:58:36,237 --> 00:58:37,820
Olgu, seal on palju sellel lehel.

1184
00:58:37,820 --> 00:58:43,179
Nii et kui te kutid saate vaadata
Esimene samm siit, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
saate jagada see pooleks.

1186
00:58:44,220 --> 00:58:45,976
Sul on 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Sa tead, et need aren't-- sa
ei tea, kas nad järjestatud või mitte,

1188
00:58:48,850 --> 00:58:52,517
nii hoiate murdes neil maha, poole,
pooleks, pooleks, kuni lõpuks

1189
00:58:52,517 --> 00:58:53,600
sul on ainult üks element.

1190
00:58:53,600 --> 00:58:56,790
Ja üks element on alati järjestatud, eks?

1191
00:58:56,790 --> 00:59:01,560
>> Nii et me teame, et 3, 5, 2, 4, 6,
1 ise, on järjestatud.

1192
00:59:01,560 --> 00:59:05,870
Ja nüüd me ei pane neid uuesti kokku.

1193
00:59:05,870 --> 00:59:07,510
Saame teada, et 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Panime need kokku.

1195
00:59:08,510 --> 00:59:09,617
Me teame, et on sorteeritud.

1196
00:59:09,617 --> 00:59:10,450
2 on ikka alles.

1197
00:59:10,450 --> 00:59:11,830
Me ei pane 4 ja 6 kokku.

1198
00:59:11,830 --> 00:59:13,996
Me teame, et see on järjestatud,
Niisiis panime kokku.

1199
00:59:13,996 --> 00:59:14,940
Ja 1 on olemas.

1200
00:59:14,940 --> 00:59:18,720
>> Ja siis sa lihtsalt vaadata
Nende kahe poole siin.

1201
00:59:18,720 --> 00:59:21,300
Sul on 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Sa võid võrrelda
hakanud kõike.

1203
00:59:23,465 --> 00:59:26,340
Sest sa tead, et see on järjestatud
ja sa tead, et see on järjestatud.

1204
00:59:26,340 --> 00:59:29,360
Siis sa ei pea isegi
võrdle 5, sa lihtsalt võrrelda 3.

1205
00:59:29,360 --> 00:59:32,070
Ja 2 on väiksem kui 3, nii
sa tead, 2 peab minema lõpuni.

1206
00:59:32,070 --> 00:59:33,120
>> Sama asi seal.

1207
00:59:33,120 --> 00:59:34,740
1. peab minema siit.

1208
00:59:34,740 --> 00:59:37,330
Ja siis, kui sa lähed panna
Nende kahe väärtuse kokku

1209
00:59:37,330 --> 00:59:39,950
sa tead, et see sorteeritakse ja
sa tead, et see on järjestatud.

1210
00:59:39,950 --> 00:59:43,240
Nii siis 1 ja
2 1 on alla 2.

1211
00:59:43,240 --> 00:59:45,570
See ütleb teile, et 1
peaks minema lõpuks see

1212
00:59:45,570 --> 00:59:47,480
isegi ilma vaadates 3 või 5.

1213
00:59:47,480 --> 00:59:50,100
Ja siis 4, saate lihtsalt
vaadake, see läheb otse siin.

1214
00:59:50,100 --> 00:59:51,480
Sa ei pea vaatama 5.

1215
00:59:51,480 --> 00:59:52,570
Sama asi 6.

1216
00:59:52,570 --> 00:59:55,860
Sa tead, et 6-- see lihtsalt
ei tuleks käsitleda.

1217
00:59:55,860 --> 00:59:57,870
>> Ja nii, et teed, sa oled
lihtsalt säästa ennast

1218
00:59:57,870 --> 00:59:59,526
palju samme, kui sa võrrelda.

1219
00:59:59,526 --> 01:00:02,150
Sa ei pea võrrelda iga
element vastu muid elemente.

1220
01:00:02,150 --> 01:00:05,230
Sa lihtsalt võrreldakse ones
et on vaja võrrelda seda vastu.

1221
01:00:05,230 --> 01:00:06,870
Nii et selline abstraktne mõiste.

1222
01:00:06,870 --> 01:00:10,540
Ära muretse, kui see ei ole
üsna lööb sind veel.

1223
01:00:10,540 --> 01:00:14,740
Aga üldiselt on see
kuidas ühendamise omamoodi toimib.

1224
01:00:14,740 --> 01:00:17,750
Küsimused, kiiret küsimust,
enne kui ma liikuda?

1225
01:00:17,750 --> 01:00:18,550
Jah.

1226
01:00:18,550 --> 01:00:22,230
>> Sihtrühm: Nii et sa ütlesid, et te võtate
1 ja seejärel 4 ja 6

1227
01:00:22,230 --> 01:00:23,860
ja panna neid.

1228
01:00:23,860 --> 01:00:26,800
Nii ei ole those-- ei
sa neid vaadates

1229
01:00:26,800 --> 01:00:28,544
eraldi elemendid, mitte kogu?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Jah.

1231
01:00:29,210 --> 01:00:32,020
Mis juhtub
on see, et sa põhimõtteliselt

1232
01:00:32,020 --> 01:00:33,650
loovad täiesti uue massiivi.

1233
01:00:33,650 --> 01:00:36,690
Nii et sa tead, et siin on mul
Kahe rea suurus 3, eks?

1234
01:00:36,690 --> 01:00:39,600
Nii et sa tead, et minu sorteeritud massiiv
peab olema kuus elementi.

1235
01:00:39,600 --> 01:00:42,270
Nii et sa lihtsalt luua
uus mälu.

1236
01:00:42,270 --> 01:00:44,270
Nii et sa oled selline nagu
on raiskav mälu,

1237
01:00:44,270 --> 01:00:46,186
kuid mis ei ole oluline
sest see on nii väike.

1238
01:00:46,186 --> 01:00:48,590
Nii te vaatate 1
ja te vaatate 2.

1239
01:00:48,590 --> 01:00:50,770
Ja sa tead, et 1 on alla 2.

1240
01:00:50,770 --> 01:00:53,840
Nii et sa tead, et 1 peaks minema
alguses Kõigil neil.

1241
01:00:53,840 --> 01:00:55,850
>> Sa ei pea isegi
vaadata 3 ja 5.

1242
01:00:55,850 --> 01:00:57,400
Nii et sa tead 1 läheb seal.

1243
01:00:57,400 --> 01:00:59,300
Siis sa põhimõtteliselt tükelda ära 1.

1244
01:00:59,300 --> 01:01:00,370
See on nagu surnud meile.

1245
01:01:00,370 --> 01:01:03,690
Siis me lihtsalt 2,
3, 5, ja siis 4 ja 6.

1246
01:01:03,690 --> 01:01:06,270
Ja siis sa tead, et sa
võrrelda 4 ja 2,

1247
01:01:06,270 --> 01:01:07,560
oh, 2 peaks sinna minna.

1248
01:01:07,560 --> 01:01:09,685
Nii et sa sulpsti 2 alla, siis selle maha raiuda.

1249
01:01:09,685 --> 01:01:12,060
Siis sa lihtsalt pead 3
ja 5 4 ning 6.

1250
01:01:12,060 --> 01:01:14,650
Ja sa lihtsalt hoida raiumine ära
kuni paned neid array.

1251
01:01:14,650 --> 01:01:17,110
>> Sihtrühm: Nii et sa oled lihtsalt alati
võrreldes [kuuldamatu]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Täpselt.

1253
01:01:17,710 --> 01:01:19,590
Nii selles mõttes, et sa oled
lihtsalt võrrelda sisuliselt

1254
01:01:19,590 --> 01:01:21,240
üks number võrreldes teiste number.

1255
01:01:21,240 --> 01:01:22,990
Ja kuna sa tead
et see on järjestatud, siis

1256
01:01:22,990 --> 01:01:24,350
ei pea otsima läbi
kõik numbrid.

1257
01:01:24,350 --> 01:01:25,870
Sa pead lihtsalt vaadata esimene.

1258
01:01:25,870 --> 01:01:27,582
Ja siis saate lihtsalt sulpsti
neid maha, sest sa tead

1259
01:01:27,582 --> 01:01:29,640
nad kuuluvad, kus nad peavad kuuluma.

1260
01:01:29,640 --> 01:01:31,030
Jah.

1261
01:01:31,030 --> 01:01:32,920
Hea küsimus.

1262
01:01:32,920 --> 01:01:35,290
>> Ja kui siis keegi teist
on natuke ambitsioonikas,

1263
01:01:35,290 --> 01:01:38,660
vabalt vaadata seda koodi.

1264
01:01:38,660 --> 01:01:40,680
See on tegelikult
tegelik rakendamine

1265
01:01:40,680 --> 01:01:42,150
kuidas me kirjutada ühendamine omamoodi.

1266
01:01:42,150 --> 01:01:44,070
Ja näed, et see on väga lühike.

1267
01:01:44,070 --> 01:01:46,310
Aga ideede
see on päris keeruline.

1268
01:01:46,310 --> 01:01:50,865
Nii et kui teil on tunne, nagu joonistus see välja
oma kodutöö täna julgelt.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> OKEI.

1271
01:01:54,740 --> 01:01:58,070
Ja Taavet läks ka üle selle loengu.

1272
01:01:58,070 --> 01:02:00,660
Mis on parimal juhul
runtimes, halvimal juhul runtimes,

1273
01:02:00,660 --> 01:02:05,680
ja oodata runtimes of ühendamine omamoodi?

1274
01:02:05,680 --> 01:02:07,260
Paar sekundit mõelda.

1275
01:02:07,260 --> 01:02:11,198
See on päris raske, kuid selline
intuitiivne kui sa mõtle selle peale.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Hästi.

1278
01:02:23,054 --> 01:02:25,269
>> Sihtrühm: Kas halvimal juhul n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Täpselt.

1280
01:02:26,060 --> 01:02:29,380
Ja miks on see n log n.

1281
01:02:29,380 --> 01:02:32,230
>> Sihtrühm: Kas mitte sellepärast, et ta
muutub eksponentsiaalselt kiiremini,

1282
01:02:32,230 --> 01:02:35,390
nii et see on nagu sõltuvus, mis
selle asemel, et lihtsalt lihtsalt seda n

1283
01:02:35,390 --> 01:02:37,529
ruuduline või midagi?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Täpselt.

1285
01:02:38,320 --> 01:02:40,750
Nii et põhjus, miks
Runtime sellel on n log

1286
01:02:40,750 --> 01:02:44,310
n on because-- mida sa
teeme kõik need sammud?

1287
01:02:44,310 --> 01:02:46,190
Sa oled lihtsalt raiumine selle pooleks, eks?

1288
01:02:46,190 --> 01:02:48,750
Ja nii, kui me teeme
sisse, kõik, mis ta teeb

1289
01:02:48,750 --> 01:02:53,150
on jagades probleem pooleks,
pooleks, pooleks, rohkem pooleks.

1290
01:02:53,150 --> 01:02:56,430
Ja selles mõttes, saate liiki
ning kõrvaldada lineaarne mudel

1291
01:02:56,430 --> 01:02:57,510
et me olen kasutanud.

1292
01:02:57,510 --> 01:03:00,254
Sest kui sa karbonaad
asjad poole, see on samamoodi.

1293
01:03:00,254 --> 01:03:02,420
See on lihtsalt matemaatiline
viis seda väljendada.

1294
01:03:02,420 --> 01:03:06,310
>> Ja siis lõpuks, lõpuks, sa oled
lihtsalt tegemist ühe viimase läbida

1295
01:03:06,310 --> 01:03:07,930
panna nad kõik selleks, eks?

1296
01:03:07,930 --> 01:03:10,330
Ja kui sa lihtsalt pead
vaadake üks asi, mis on n.

1297
01:03:10,330 --> 01:03:13,420
Ja nii sa oled selline
korrutades kaks kokku.

1298
01:03:13,420 --> 01:03:17,660
Nii et see on nagu sul, et lõplik
vaadake n siin koos log n

1299
01:03:17,660 --> 01:03:18,390
siin.

1300
01:03:18,390 --> 01:03:21,060
Ja kui sa korrutada
neid, mis on n log n.

1301
01:03:21,060 --> 01:03:26,100
>> Ja nii parima kui ka halvima
Juhul ning oodata on kõik n log n.

1302
01:03:26,100 --> 01:03:27,943
Samuti nagu teine ​​omamoodi.

1303
01:03:27,943 --> 01:03:30,090
See on nagu valikut omamoodi
selles mõttes, et see

1304
01:03:30,090 --> 01:03:32,131
Ei ole oluline, milline on sinu
nimekiri on, see lihtsalt läheb

1305
01:03:32,131 --> 01:03:34,801
teha sama asja iga kord.

1306
01:03:34,801 --> 01:03:35,300
OKEI.

1307
01:03:35,300 --> 01:03:39,950
Nii nagu te poisid ei vaata, kuigi
kehvasti, et oleme läinud through-- n

1308
01:03:39,950 --> 01:03:41,660
ruuduline, see ei ole väga tõhus.

1309
01:03:41,660 --> 01:03:47,060
Ja isegi see n log n on
ei ole kõige tõhusam.

1310
01:03:47,060 --> 01:03:49,720
Kui Te olete uudishimulik,
seal on omamoodi mehhanismid

1311
01:03:49,720 --> 01:03:54,310
mis on nii tõhus, et nad
peaaegu põhiliselt tasased tööaega.

1312
01:03:54,310 --> 01:03:55,420
>> Sul on mõned log n on.

1313
01:03:55,420 --> 01:03:58,190
Sul on mõned log log n on.

1314
01:03:58,190 --> 01:04:00,330
Me ei puuduta neid
Selle klassi praegu.

1315
01:04:00,330 --> 01:04:02,663
Aga kui te kutid on uudishimulik,
julgelt Google, mis on

1316
01:04:02,663 --> 01:04:04,392
kõige tõhusam sortimine mehhanismid.

1317
01:04:04,392 --> 01:04:06,350
Ma ei tea, on
mõned tõesti naljakas ones,

1318
01:04:06,350 --> 01:04:09,860
like-- seal on mõned tõesti
naljakas ones, et inimesed teevad.

1319
01:04:09,860 --> 01:04:12,210
Ja sa ei tea, kuidas nad
kunagi mõelnud, et.

1320
01:04:12,210 --> 01:04:15,730
Nii google, kui teil on mõni vaba
aja, milline on mõned naljakas viise

1321
01:04:15,730 --> 01:04:17,730
et people-- samuti
tõhus ways-- inimesed

1322
01:04:17,730 --> 01:04:20,371
suutnud rakendada kehvasti.

1323
01:04:20,371 --> 01:04:20,870
OKEI.

1324
01:04:20,870 --> 01:04:22,880
Ja siin on lihtsalt mugav väike skeem.

1325
01:04:22,880 --> 01:04:26,850
Ma tean, et te kõik, enne seda viktoriini 0,
on oma toas ilmselt üritab

1326
01:04:26,850 --> 01:04:27,960
meelde, et.

1327
01:04:27,960 --> 01:04:30,940
Nii et on tore seal kutid.

1328
01:04:30,940 --> 01:04:37,120
Lihtsalt ärge unustage loogika, et made--
miks need numbrid olid toimunud.

1329
01:04:37,120 --> 01:04:39,870
Kui sa oled alati kadunud, lihtsalt
kindel, et tead, mida kehvasti on.

1330
01:04:39,870 --> 01:04:40,820
Ja sa võid joosta
neid meelt

1331
01:04:40,820 --> 01:04:42,903
aru saada, miks neid
Vastused on need vastused.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Hästi.

1334
01:04:47,600 --> 01:04:49,680
Nii et me läheme liikuma
kohta, lõpuks, et otsida.

1335
01:04:49,680 --> 01:04:51,638
Sest kui need teile
kes on lugenud pset,

1336
01:04:51,638 --> 01:04:55,175
otsing ei ole ka osa
Sel nädalal probleem seab.

1337
01:04:55,175 --> 01:04:57,300
Teil palutakse rakendada
kahte tüüpi otsinguid.

1338
01:04:57,300 --> 01:05:00,070
Üks on lineaarne otsing ja
üks on binaarne otsing.

1339
01:05:00,070 --> 01:05:01,760
>> Nii lineaarne otsing on üsna lihtne.

1340
01:05:01,760 --> 01:05:04,070
Sa tahad otsida element
loetelu, et näha, kui sa saad selle.

1341
01:05:04,070 --> 01:05:05,444
Sa pead lihtsalt korrata läbi.

1342
01:05:05,444 --> 01:05:08,170
Ja kui see võrdub midagi,
võite lihtsalt tagasi, eks?

1343
01:05:08,170 --> 01:05:10,890
Aga see, kes me oleme kõige
huvitatud räägi

1344
01:05:10,890 --> 01:05:14,550
on binaarse otsing, õige, mis on
Jaga ja valitse mehhanism, mis

1345
01:05:14,550 --> 01:05:18,190
David oli näidates loeng.

1346
01:05:18,190 --> 01:05:20,810
>> Mäleta telefoniraamatust näiteks
et ta hoiab kasvatamisel,

1347
01:05:20,810 --> 01:05:23,960
üks, et ta mingi võitlesid
natuke seda viimase aasta jooksul

1348
01:05:23,960 --> 01:05:27,530
kus sa jagada probleem pooleks,
pooleks, pooleks, ikka ja jälle,

1349
01:05:27,530 --> 01:05:30,730
kuni leiad, mida otsite?

1350
01:05:30,730 --> 01:05:33,727
Ja sul
Runtime selle samuti.

1351
01:05:33,727 --> 01:05:35,810
Ja näed, et see on
oluliselt efektiivsemaks

1352
01:05:35,810 --> 01:05:39,080
kui mis tahes muud liiki otsing.

1353
01:05:39,080 --> 01:05:41,880
>> Nii nii, et me oleks minna
rakendamise binaarne otsing

1354
01:05:41,880 --> 01:05:46,510
on, kui meil oleks massiivi,
indeks 0 kuni 6, seitse elemente,

1355
01:05:46,510 --> 01:05:49,790
saame vaadata keskel, right--
kahju, kui meie küsimusele first--

1356
01:05:49,790 --> 01:05:53,840
Kui tahame küsida küsimus, kas
massiiv sisaldab elementi 7,

1357
01:05:53,840 --> 01:05:56,840
Ilmselt on inimestele ning võttes
Sellise väikese hulga, see on lihtne meile

1358
01:05:56,840 --> 01:05:58,210
öelda jah.

1359
01:05:58,210 --> 01:06:05,750
Aga kuidas rakendada binaarne
otsingu oleks otsida keskel.

1360
01:06:05,750 --> 01:06:08,020
>> Me teame, et indeks 3
keskel, sest me

1361
01:06:08,020 --> 01:06:09,270
tean, seal on seitse elementi.

1362
01:06:09,270 --> 01:06:10,670
Mis 7 jagatuna 2?

1363
01:06:10,670 --> 01:06:12,850
Võite tükelda ära, et ekstra 1.

1364
01:06:12,850 --> 01:06:14,850
Sul on 3 keskel.

1365
01:06:14,850 --> 01:06:17,590
Nii on massiiv 3 võrdub 7?

1366
01:06:17,590 --> 01:06:18,900
See ei ole õige?

1367
01:06:18,900 --> 01:06:21,050
Aga me saame teha paar kontrolli.

1368
01:06:21,050 --> 01:06:25,380
Kas massiivi 3 kuni 7 või
on rida 3 on suurem kui 7?

1369
01:06:25,380 --> 01:06:27,240
>> Ja me teame, et see on vähem kui 7.

1370
01:06:27,240 --> 01:06:30,259
Nii et me teame, et oh, see peab
saa olla vasakul poolel.

1371
01:06:30,259 --> 01:06:32,300
Me teame, et see peab olema
õiges poole, eks?

1372
01:06:32,300 --> 01:06:34,662
Nii saame lihtsalt karbonaad off pool massiivi.

1373
01:06:34,662 --> 01:06:36,370
Me isegi ei pea
vaadata seda enam.

1374
01:06:36,370 --> 01:06:38,711
Kuna me teame, et
pool meie problem--

1375
01:06:38,711 --> 01:06:41,210
me teame, et vastus on
paremal pool meie probleem.

1376
01:06:41,210 --> 01:06:42,580
Nii et me lihtsalt vaadata, et nüüd.

1377
01:06:42,580 --> 01:06:44,860
>> Nüüd vaatame
keskel, mida on jäänud.

1378
01:06:44,860 --> 01:06:46,880
See indeks 5.

1379
01:06:46,880 --> 01:06:50,200
Me teha sama uuesti kontrollida
ja me näeme, et see on väiksem.

1380
01:06:50,200 --> 01:06:52,050
Nii me vaatame vasakule, et.

1381
01:06:52,050 --> 01:06:53,430
Ja siis me näeme, et kontrollida.

1382
01:06:53,430 --> 01:06:57,600
Kas array väärtus
indeks 4 võrdub 7?

1383
01:06:57,600 --> 01:06:58,260
See on.

1384
01:06:58,260 --> 01:07:03,580
Nii saame tagasi tõsi, sest
leidsime väärtus meie nimekirjas.

1385
01:07:03,580 --> 01:07:06,738
Kas nii, nagu ma läksin läbi
mis mõtet kõigile?

1386
01:07:06,738 --> 01:07:08,760
OKEI.

1387
01:07:08,760 --> 01:07:11,670
Ma annan sulle poisid äkki, nagu,
kolm, neli minutit, et aru saada,

1388
01:07:11,670 --> 01:07:13,270
kuidas pseudokoodi seda.

1389
01:07:13,270 --> 01:07:18,070
>> Seega kujutada Ma palusin sul kirjutada
funktsiooni nimetatakse otsingumootori (), et tagasi

1390
01:07:18,070 --> 01:07:20,640
väärtus, tõeväärtuse,
see oli õige või false-- nagu,

1391
01:07:20,640 --> 01:07:22,970
tõsi, kui olete leidnud
väärtus, vale, kui sa seda ei teinud.

1392
01:07:22,970 --> 01:07:25,230
Ja siis olid
möödunud aastal väärtus, mida

1393
01:07:25,230 --> 01:07:28,410
otsisid arvesse väärtusi, mis
on array-- oh, ma kindlasti panna

1394
01:07:28,410 --> 01:07:29,410
et vales kohas.

1395
01:07:29,410 --> 01:07:29,580
OKEI.

1396
01:07:29,580 --> 01:07:31,829
Niikuinii, et peaks olema
olnud paremal väärtusi.

1397
01:07:31,829 --> 01:07:36,280
Ja siis int n on number
elementide, mis massiivi.

1398
01:07:36,280 --> 01:07:39,430
Kuidas minna püüdnud
to pseudokoodi et probleem?

1399
01:07:39,430 --> 01:07:41,630
Ma annan sulle sinusuguseid
kolm minutit teha.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Ei, ma arvan, et seal on ainult--
Jah, seal on üks õige siin.

1402
01:08:02,595 --> 01:08:03,261
Sihtrühm: Kas ma?

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Jah, ma sain sulle.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Kas see töö?

1406
01:08:11,050 --> 01:08:12,290
OK, lahe.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> OKEI.

1409
01:10:44,720 --> 01:10:47,630
Olgu poisid, me oleme
läheb rein seda.

1410
01:10:47,630 --> 01:10:49,730
OKEI.

1411
01:10:49,730 --> 01:10:54,020
Nii eeldame meil see armas
vähe massiivi n väärtuste ta.

1412
01:10:54,020 --> 01:10:55,170
Ma ei tõmmata jooned.

1413
01:10:55,170 --> 01:10:58,649
Aga kuidas me minna
üritan kirjutada seda?

1414
01:10:58,649 --> 01:11:00,440
Kas keegi taha
mulle esimene rida?

1415
01:11:00,440 --> 01:11:02,814
Kui soovite mulle anda
esimene rida selles pseudokoodi.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> Sihtrühm: [kuuldamatu]

1418
01:11:08,430 --> 01:11:10,138
Sihtrühm: Sa tahad
itereerima through--

1419
01:11:10,138 --> 01:11:11,094
Sihtrühm: Lihtsalt üks silmus?

1420
01:11:11,094 --> 01:11:11,760
Sihtrühm: --for.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Nii see on natuke keeruline.

1423
01:11:17,780 --> 01:11:23,130
Mõtle about-- soovid
hoida töötab see loop

1424
01:11:23,130 --> 01:11:27,950
ikka ja jälle, kuni millal?

1425
01:11:27,950 --> 01:11:30,819
>> Sihtrühm: Kuni [kuuldamatu]
võrdub selle väärtus.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Täpselt.

1427
01:11:31,610 --> 01:11:33,900
Nii saab tegelikult lihtsalt write--
saame isegi lihtsustada seda rohkem.

1428
01:11:33,900 --> 01:11:35,630
Me võime lihtsalt teha samas loop, eks?

1429
01:11:35,630 --> 01:11:39,380
Nii saab lihtsalt loop--
me teame, et see on samas.

1430
01:11:39,380 --> 01:11:42,850
Aga just nüüd, ma lähen
öelda "loop" - kaudu, mis?

1431
01:11:42,850 --> 01:11:46,640
Loop until-- mis on
lõppev haigus?

1432
01:11:46,640 --> 01:11:47,510
Ma arvan, et ma kuulsin seda.

1433
01:11:47,510 --> 01:11:48,530
Ma kuulsin kedagi ütlemas seda.

1434
01:11:48,530 --> 01:11:51,255
>> Sihtrühm: Väärtused võrdub keskel.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: Ütle seda uuesti.

1436
01:11:52,255 --> 01:11:54,470
Sihtrühm: Või, kuni
väärtus, mida te otsite

1437
01:11:54,470 --> 01:11:58,470
on võrdne keskväärtusena.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Mis siis, kui see ei ole seal?

1439
01:12:00,280 --> 01:12:03,113
Mis siis, kui väärtus, mida te otsite
on tegelikult ei selles massiivi?

1440
01:12:03,113 --> 01:12:05,890
Sihtrühm: Sa tagasi 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Aga mida me tahame
loop kuni kui meil on tingimus?

1442
01:12:08,850 --> 01:12:09,350
Jah.

1443
01:12:09,350 --> 01:12:11,239
>> Sihtrühm: Kuni seal on ainult üks väärtus?

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: Võite loop
until--, et sa tead, et sa oled

1445
01:12:13,530 --> 01:12:15,714
läheb on max väärtus, eks?

1446
01:12:15,714 --> 01:12:18,130
Ja sa tead, et sa lähed
min oleks väärtus, eks?

1447
01:12:18,130 --> 01:12:20,379
Kuna ka, et midagi
Ma unustasin öelda enne,

1448
01:12:20,379 --> 01:12:22,640
et midagi, mis on
kriitiline Kahendotsingupuu

1449
01:12:22,640 --> 01:12:24,182
on see, et teie massiiv on juba järjestatud.

1450
01:12:24,182 --> 01:12:26,973
Sest seal on kuidagi teed
see, kui nad lihtsalt juhuslik väärtusi.

1451
01:12:26,973 --> 01:12:29,190
Sa ei tea, kui üks on
suurem kui teine, eks?

1452
01:12:29,190 --> 01:12:32,720
>> Nii et sa tead, et su max ja
Sinu minutit siin, eks?

1453
01:12:32,720 --> 01:12:35,590
Kui sa lähed tuleb reguleerida
Teie max sinu minutit ja mid--

1454
01:12:35,590 --> 01:12:38,470
olgem lihtsalt eeldada oma
Keskmine väärtus on siin--

1455
01:12:38,470 --> 01:12:43,910
sa lähed põhimõtteliselt
loop kuni oma miinimum

1456
01:12:43,910 --> 01:12:47,510
umbes sama, mis sinu max, õigus, või
Kui teie maks ei ole sama, mis sinu min.

1457
01:12:47,510 --> 01:12:48,040
Õigus?

1458
01:12:48,040 --> 01:12:51,340
Sest kui see juhtub, siis tea, et
oled lõpuks tabas sama väärtusega.

1459
01:12:51,340 --> 01:12:59,135
Nii et sa tahad loop, kuni teie min
on väiksem või võrdne-- oops,

1460
01:12:59,135 --> 01:13:01,510
mitte väiksem või võrdne,
Teine võimalus lihtsalt ringi max.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Kas see on mõtet?

1463
01:13:16,160 --> 01:13:18,810
Võtsin paar üritab saada seda õigust.

1464
01:13:18,810 --> 01:13:21,869
Aga loop kuni oma max väärtus
on sisuliselt peaaegu vähem

1465
01:13:21,869 --> 01:13:23,410
võrdne või oma minimaalne, eks?

1466
01:13:23,410 --> 01:13:25,201
See, kui sa tead,
et olete ühtlustunud.

1467
01:13:25,201 --> 01:13:29,290
Sihtrühm: Millal peaks oma maksimaalse
väärtus olla väiksem kui minimaalne?

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Kui hoiate
kohandades seda, mis

1469
01:13:31,040 --> 01:13:32,380
on see, mida me
olla teeme seda.

1470
01:13:32,380 --> 01:13:33,460
Kas see on mõtet?

1471
01:13:33,460 --> 01:13:35,750
Minimaalne ja maksimaalne on vaid
täisarvud, et oleme ilmselt

1472
01:13:35,750 --> 01:13:39,260
lähed tahan luua hoida
peal, kus me otsime.

1473
01:13:39,260 --> 01:13:41,790
Kuna massiivi olemas
sõltumata sellest, mida me teeme.

1474
01:13:41,790 --> 01:13:45,030
Nagu, me ei ole tegelikult füüsiliselt
hakkimispiirkond massiivi, eks?

1475
01:13:45,030 --> 01:13:47,261
Me lihtsalt reguleerida
kus me otsime.

1476
01:13:47,261 --> 01:13:48,136
Kas see on mõtet?

1477
01:13:48,136 --> 01:13:48,472
>> Sihtrühm: Jah.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Nii et kui see on eelduseks meie loop,
Mida me tahame sees see loop?

1480
01:13:57,090 --> 01:13:58,700
Mida me saame teha tahame?

1481
01:13:58,700 --> 01:14:02,390
Nii kohe, meil
max ja min, õigus,

1482
01:14:02,390 --> 01:14:04,962
ilmselt loodud siin kusagil.

1483
01:14:04,962 --> 01:14:07,170
Me läheme ilmselt tahad
leida kompromiss, eks?

1484
01:14:07,170 --> 01:14:08,450
Kuidas me saame olla
võimalik leida keskel?

1485
01:14:08,450 --> 01:14:09,491
Mis mathematical--

1486
01:14:09,491 --> 01:14:11,079
Sihtrühm: Max pluss min jagatud 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Täpselt.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Kas see on mõtet?

1490
01:14:21,620 --> 01:14:25,780
Ja te poisid aru, miks me
ei ole lihtsalt use-- miks me seda tegime

1491
01:14:25,780 --> 01:14:27,850
selle asemel teeme lihtsalt n jagatud 2?

1492
01:14:27,850 --> 01:14:30,310
See on sellepärast, et n on väärtus
et läheb samaks.

1493
01:14:30,310 --> 01:14:30,979
Õigus?

1494
01:14:30,979 --> 01:14:34,020
Aga kui me kohandame oma minimaalse ja
maksimaalseid väärtusi, nad ei kavatse muuta.

1495
01:14:34,020 --> 01:14:36,040
Ja tulemus, meie keskel
hakkab muutuma liiga.

1496
01:14:36,040 --> 01:14:37,873
Nii et miks me tahame
seda teha siin.

1497
01:14:37,873 --> 01:14:38,510
OKEI.

1498
01:14:38,510 --> 01:14:41,600
>> Ja siis, et nüüd,
oleme leidnud our-- yeah.

1499
01:14:41,600 --> 01:14:44,270
>> Sihtrühm: Lihtsalt kiire question--
kui sa ütled min ja max,

1500
01:14:44,270 --> 01:14:46,410
me eeldades, et
see on juba järjestatud?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Jah, see on tegelikult
eelduseks Kahendotsingupuu,

1502
01:14:48,400 --> 01:14:49,816
et sa pead teadma, see on järjestatud.

1503
01:14:49,816 --> 01:14:53,660
Mistõttu omamoodi, sa kirjutad oma
Probleem panen oma binaarne otsing.

1504
01:14:53,660 --> 01:14:55,910
OKEI.

1505
01:14:55,910 --> 01:14:58,876
Nüüd, kui me teame, kus meie keskpunktis
on, mida sa tahad teha siin?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> Sihtrühm: Me tahame võrrelda
et teine.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Täpselt.

1509
01:15:05,110 --> 01:15:12,280
Nii et sa lähed võrrelda
keskpaigast kuni väärtuses, eks?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
Ja mida ütleb see
meid, kui me võrdleme?

1512
01:15:18,670 --> 01:15:22,226
Mida me tahame teha hiljem?

1513
01:15:22,226 --> 01:15:25,389
>> Sihtrühm: Kui väärtus on suurem
kui keskel, tahame lõigata ära.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Täpselt.

1515
01:15:26,180 --> 01:15:33,940
Nii et kui väärtus on suurem
kui keskel, me oleme

1516
01:15:33,940 --> 01:15:36,550
tahame seda muuta need
minimaalne ja maxes, eks?

1517
01:15:36,550 --> 01:15:38,980
Mida me tahame muuta?

1518
01:15:38,980 --> 01:15:42,145
Nii et kui me teame, väärtus on kuskil
siin, mida sa meil muuta?

1519
01:15:42,145 --> 01:15:44,758
Me tahame muuta meie
minimaalne olema keskel, eks?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
Ja siis teine, kui see on antud
poole, mida me tahame muuta?

1522
01:15:54,292 --> 01:15:55,306
>> Sihtrühm: Teie maksimaalne.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Jah.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
Ja siis sa oled lihtsalt läheb
hoida silmukoiminen, eks?

1526
01:16:04,680 --> 01:16:08,920
Sest nüüd pärast ühte iteratsiooni
läbi, sul on max siin.

1527
01:16:08,920 --> 01:16:10,760
Ja siis saab arvutada ümber keskel.

1528
01:16:10,760 --> 01:16:11,990
Ja siis saad võrrelda.

1529
01:16:11,990 --> 01:16:14,766
Ja sa lähed edasi minema
kuni mins ja maxes

1530
01:16:14,766 --> 01:16:15,890
on sisuliselt lähenesid.

1531
01:16:15,890 --> 01:16:17,890
Ja see, kui sa tead, et
olete tabanud lõpuni.

1532
01:16:17,890 --> 01:16:20,280
Ja kas olete leidnud
või sa ei ole sel hetkel.

1533
01:16:20,280 --> 01:16:23,170
>> Kas see mõtet kõigile?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
OKEI.

1536
01:16:26,770 --> 01:16:27,900
See on päris oluline,
sest sa pead

1537
01:16:27,900 --> 01:16:29,760
kirjutada seda koodi täna.

1538
01:16:29,760 --> 01:16:32,660
Aga kutid on päris hea
tunnet, mida sa peaks tegema,

1539
01:16:32,660 --> 01:16:34,051
mis on hea.

1540
01:16:34,051 --> 01:16:34,550
OKEI.

1541
01:16:34,550 --> 01:16:38,840
Nii on meil umbes seitse
minutit aega osa.

1542
01:16:38,840 --> 01:16:43,170
Nii et me ei kavatse rääkida
Selle pset, et me teeme.

1543
01:16:43,170 --> 01:16:46,410
Nii pset jaguneb kaheks pooleks.

1544
01:16:46,410 --> 01:16:50,230
Esimene pool hõlmab
rakendades leida

1545
01:16:50,230 --> 01:16:54,210
kus sa kirjutad lineaarne otsing, et
Kahendotsingupuu ja sorteerimisalgoritm.

1546
01:16:54,210 --> 01:16:56,690
>> Nii on see esimene
korda pset, kus

1547
01:16:56,690 --> 01:17:00,050
me olla annab teile poisid, mida nimetatakse
jaotus kood, mis on koodi

1548
01:17:00,050 --> 01:17:02,740
et me oleme eelnevalt kirjutatud,
kuid just lahkunud mõned tükid ära

1549
01:17:02,740 --> 01:17:04,635
teil lõpetada kirjalikult.

1550
01:17:04,635 --> 01:17:07,510
Nii kutid, kui te vaatate seda
koodi, võite saada väga hirmul.

1551
01:17:07,510 --> 01:17:08,630
Kui sa oled lihtsalt meeldib, ahh, ma
ei tea, mis see teeb,

1552
01:17:08,630 --> 01:17:11,670
Ma ei tea, nagu, mis tundub
nii keeruline, ahh, lõõgastuda.

1553
01:17:11,670 --> 01:17:12,170
See on OK.

1554
01:17:12,170 --> 01:17:12,930
Loe spec.

1555
01:17:12,930 --> 01:17:16,920
Spec selgitab teile täpselt
Mis need kõik teevad.

1556
01:17:16,920 --> 01:17:20,560
>> Näiteks generate.c on programm
et tulevad oma pset.

1557
01:17:20,560 --> 01:17:24,060
Sa tegelikult ei pea seda puudutada, kuid
sa peaksid mõistma, mida ta teeb.

1558
01:17:24,060 --> 01:17:28,550
Ja generate.c, kõik see teeb on
kas teeniva juhuslikud arvud

1559
01:17:28,550 --> 01:17:32,400
või saate anda talle seemne, nagu
jätavad arv, mis kulub,

1560
01:17:32,400 --> 01:17:34,140
ja see tekitab rohkem numbreid.

1561
01:17:34,140 --> 01:17:37,170
Nii et konkreetne võimalus
rakendada generate.c kus

1562
01:17:37,170 --> 01:17:42,760
võite lihtsalt hunnik numbreid
kus saab testida oma muid meetodeid.

1563
01:17:42,760 --> 01:17:45,900
>> Nii et kui sa tahad, et
Näiteks testida oma leid,

1564
01:17:45,900 --> 01:17:48,970
sa tahaksid joosta generate.c,
luua hunnik numbreid,

1565
01:17:48,970 --> 01:17:50,880
ja siis käivitada oma abilised funktsiooni.

1566
01:17:50,880 --> 01:17:53,930
Sinu abilised funktsioon on koht, kus sa oled
tegelikult füüsiliselt kirjutada koodi.

1567
01:17:53,930 --> 01:17:59,330
Ja mõelda abilised nii raamatukogu faili
sa oled kirjalikult, et leida helistab.

1568
01:17:59,330 --> 01:18:02,950
Ja nii sees helpers.c, saate
teha otsides ja sorteerimine.

1569
01:18:02,950 --> 01:18:06,500
>> Ja siis sa lähed sisuliselt
lihtsalt panna need kõik kokku.

1570
01:18:06,500 --> 01:18:10,350
Spec ütleb teile, kuidas
panna, et kui anda käsureal.

1571
01:18:10,350 --> 01:18:14,880
Ja saate testida, kas või
ei oma ja otsimise töötavad.

1572
01:18:14,880 --> 01:18:15,870
Cool.

1573
01:18:15,870 --> 01:18:18,720
Kas keegi on juba alanud ja
tekkinud probleeme või küsimusi

1574
01:18:18,720 --> 01:18:20,520
nad on just nüüd seda?

1575
01:18:20,520 --> 01:18:21,020
OKEI.

1576
01:18:21,020 --> 01:18:21,476
>> Sihtrühm: Oota.

1577
01:18:21,476 --> 01:18:21,932
Mul on küsimus.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Jah.

1579
01:18:22,844 --> 01:18:28,390
>> Sihtrühm: Nii hakkasin teed
lineaarse otsingule helpers.c

1580
01:18:28,390 --> 01:18:29,670
ja see ei tööta päris.

1581
01:18:29,670 --> 01:18:34,590
Aga hiljem sain teada, et me lihtsalt
pea kustutama ja tegema Kahendotsingupuu.

1582
01:18:34,590 --> 01:18:36,991
Nii on see oluline, kui see ei tööta?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: Lühike vastus on ei.

1585
01:18:41,510 --> 01:18:42,642
Aga kuna me oleme Mitte--

1586
01:18:42,642 --> 01:18:44,350
Sihtrühm: Aga keegi ei
tegelikult kontrollida.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Oleme kunagi
näeme, et.

1588
01:18:46,058 --> 01:18:49,590
Aga sa ilmselt tahad teha
Kindlasti otsingut töötab.

1589
01:18:49,590 --> 01:18:51,700
Sest kui teie lineaarne
otsing ei tööta,

1590
01:18:51,700 --> 01:18:54,410
siis tõenäoliselt on teie binaarne
Otsing ei kavatse töötada nii hästi.

1591
01:18:54,410 --> 01:18:56,646
Kuna teil on sarnane
loogikat neis mõlemas.

1592
01:18:56,646 --> 01:18:58,020
Ja ei, see ei ole tegelikult küsimus.

1593
01:18:58,020 --> 01:19:01,300
Nii et ainsad, saate sisse lülitada
aastal on omamoodi ja binaarne otsing.

1594
01:19:01,300 --> 01:19:02,490
Jah.

1595
01:19:02,490 --> 01:19:06,610
>> Ja ka palju lapsi oli
püüab koostada helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Sa tegelikult ei lubatud
seda teha, sest helpers.c

1597
01:19:09,550 --> 01:19:11,200
ei ole põhifunktsiooni.

1598
01:19:11,200 --> 01:19:13,550
Ja et sa peaksid ainult
olla tegelikult koostamine

1599
01:19:13,550 --> 01:19:18,670
luua ja leida, sest leiavad kõned
helpers.c ja funktsioone see.

1600
01:19:18,670 --> 01:19:20,790
Nii et teeb silumine
valu tagumik.

1601
01:19:20,790 --> 01:19:22,422
Aga see, mida me peame tegema.

1602
01:19:22,422 --> 01:19:23,880
Sihtrühm: Teed kõik, eks?

1603
01:19:23,880 --> 01:19:27,290
ANDI PENG: Sa võid
kõik hästi, jah.

1604
01:19:27,290 --> 01:19:28,060
OKEI.

1605
01:19:28,060 --> 01:19:32,570
Nii ongi selle järgi, mida
pset küsib teile kõigile teha.

1606
01:19:32,570 --> 01:19:35,160
Kui teil on küsimusi, tunnen
tasuta küsi Pärast punkti.

1607
01:19:35,160 --> 01:19:37,580
Ma tulen siia, nagu 20 minutit.

1608
01:19:37,580 --> 01:19:40,500
>> Ja jah, siis pset on
tõesti ei ole nii hull.

1609
01:19:40,500 --> 01:19:41,680
Te peaks olema OK.

1610
01:19:41,680 --> 01:19:43,250
Need, järgige juhiseid.

1611
01:19:43,250 --> 01:19:47,840
Kind of on tunne, loogiliselt, mida
tuleks juhtub ja siis saad trahvi.

1612
01:19:47,840 --> 01:19:48,690
Ära ole liiga hirmul.

1613
01:19:48,690 --> 01:19:50,220
Seal on palju koodi
juba kirjutanud seal.

1614
01:19:50,220 --> 01:19:53,011
Ära ole liiga hirmul, kui sa seda ei tee
aru, mida see kõik tähendab.

1615
01:19:53,011 --> 01:19:54,749
Kui see on palju, see on täiesti korras.

1616
01:19:54,749 --> 01:19:55,790
Ja tulevad tööaega.

1617
01:19:55,790 --> 01:19:57,520
Me aitame teil võtta pilk.

1618
01:19:57,520 --> 01:20:00,810
>> Sihtrühm: Mis extra
funktsioone, me vaatame neid üles?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Jah, need on kood.

1620
01:20:03,417 --> 01:20:05,750
Mängus on 15 poole
see on juba kirjutatud teile.

1621
01:20:05,750 --> 01:20:09,310
Nii et need funktsioonid on
Juba koodi.

1622
01:20:09,310 --> 01:20:12,020
Yep.

1623
01:20:12,020 --> 01:20:12,520
Hästi.

1624
01:20:12,520 --> 01:20:14,000
Noh, palju õnne.

1625
01:20:14,000 --> 01:20:15,180
See on vastik päev.

1626
01:20:15,180 --> 01:20:19,370
Loodetavasti kutid ei tunne liiga
halba viibib sees ja kodeerimine.

1627
01:20:19,370 --> 01:20:22,133