1
00:00:00,000 --> 00:00:03,332
>> [Glazbom]

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Dobrodošli u tjednu 3. poglavlju.

3
00:00:06,490 --> 00:00:09,550
Hvala, dečki, za sve koji dolaze
ovaj ranije danas starta.

4
00:00:09,550 --> 00:00:11,466
Imamo lijep, malo
intimna skupina danas.

5
00:00:11,466 --> 00:00:14,570
Dakle, nadam se da ćemo doći do
završiti, možda, rano,

6
00:00:14,570 --> 00:00:15,780
malo ranije danas.

7
00:00:15,780 --> 00:00:22,057
Tako brzo, samo su neki
najave dnevnom redu danas.

8
00:00:22,057 --> 00:00:23,890
Prije nego što počnemo, mi smo
će samo ići preko

9
00:00:23,890 --> 00:00:28,910
neka kratka logistički problemi, pset
pitanja, ispitati, takve stvari.

10
00:00:28,910 --> 00:00:30,250
A onda ćemo roniti u pravu.

11
00:00:30,250 --> 00:00:34,710
Mi ćemo koristiti debugger zove GDB se
početi Debunking naš kod, koji je David

12
00:00:34,710 --> 00:00:36,550
objasnio u predavanju neki dan.

13
00:00:36,550 --> 00:00:39,420
Mi ćemo ići preko četiri vrste sorti.

14
00:00:39,420 --> 00:00:42,310
Mi ćemo ići preko njih vrlo brzo
jer oni su prilično intenzivna.

15
00:00:42,310 --> 00:00:45,710
Ali znam da su svi slajdovi i
Izvorni kod su uvijek online.

16
00:00:45,710 --> 00:00:50,810
Dakle, slobodno, na lektira, na
vratiti i pogledati to.

17
00:00:50,810 --> 00:00:53,930
>> Mi ćemo proći kroz
asimptotske zapis koji

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

19
00:00:55,944 --> 00:00:58,360
gdje imamo veliki O, koji
David je objasnio u predavanju.

20
00:00:58,360 --> 00:01:01,550
I mi također imaju Omega, koji
je donja granica runtime.

21
00:01:01,550 --> 00:01:06,450
A mi ćemo govoriti malo više
u dubini pogledu kako ti posao.

22
00:01:06,450 --> 00:01:10,160
I na kraju, mi ćemo ići preko binarnog pretraživanja,
jer puno vas koji su već

23
00:01:10,160 --> 00:01:15,190
Pogledao je svoje psets vjerojatno znate da
to je pitanje koje je u svom pset.

24
00:01:15,190 --> 00:01:17,470
Dakle, svi vi ćete biti sretni
koje pokrivaju to danas.

25
00:01:17,470 --> 00:01:20,610
>> I na kraju, po svoj
poglavlje povratne informacije, ja zapravo

26
00:01:20,610 --> 00:01:23,000
ostavi 15 minuta na
kraj samo ići preko

27
00:01:23,000 --> 00:01:27,730
logistika pset3, bilo kakva pitanja,
možda malo smjernice, ako hoćete,

28
00:01:27,730 --> 00:01:28,990
Prije nego što počnemo programiranje.

29
00:01:28,990 --> 00:01:30,890
Tako ćemo pokušati dobiti kroz
materijal prilično brzo.

30
00:01:30,890 --> 00:01:33,880
A onda možemo provesti neko vrijeme
uzimanje više pitanja za pset.

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

32
00:01:35,230 --> 00:01:39,570
>> Brzo, pa samo malo
najave prije nego što počnemo već danas.

33
00:01:39,570 --> 00:01:45,410
Prvo, dobrodošli u izradi
to kroz dvije svoje psets.

34
00:01:45,410 --> 00:01:49,432
Uzeo sam pogled na your-- da, neka je
dobili aplauz za taj jedan.

35
00:01:49,432 --> 00:01:51,140
Zapravo, bio sam jako,
stvarno impresioniran.

36
00:01:51,140 --> 00:01:55,800
I polaže prvi pset za vas momci
Prošlog tjedna, a vi učinili nevjerojatno.

37
00:01:55,800 --> 00:01:58,290
>> Stil je bio na mjestu
osim nekoliko komentara.

38
00:01:58,290 --> 00:02:00,660
Pobrinite se da uvijek
Komentirajući svoj kod.

39
00:02:00,660 --> 00:02:03,040
Ali tvoji psets bili na mjestu.

40
00:02:03,040 --> 00:02:05,549
I držati ga se.

41
00:02:05,549 --> 00:02:08,090
I to je dobro za greder na
vidim da su ti dečki stavljajući

42
00:02:08,090 --> 00:02:10,704
u koliko truda u svom stilu
i vaš dizajn u kodu

43
00:02:10,704 --> 00:02:12,120
da želimo za vas vidjeti.

44
00:02:12,120 --> 00:02:16,450
Tako sam prolazeći zahvalnosti
ostatak TAS.

45
00:02:16,450 --> 00:02:19,210
>> Međutim postoji
Nekoliko ispitati pitanja

46
00:02:19,210 --> 00:02:22,010
Ja samo želim ići preko toga
kako bi moj život

47
00:02:22,010 --> 00:02:24,900
i puno drugoga
TAS 'živi malo lakše.

48
00:02:24,900 --> 00:02:28,220
Prvo, sam primjetio ovo
prošlosti week-- koliko vas

49
00:02:28,220 --> 00:02:32,301
su trčanje na check50
Vaš broj prije nego što pošaljete?

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

51
00:02:32,800 --> 00:02:36,690
Dakle, svatko bi trebao biti događaj check50,
because-- secret-- smo zapravo

52
00:02:36,690 --> 00:02:41,540
pokrenuti check50 kao dio naše ispravnosti
skripte za testiranje svoj kod.

53
00:02:41,540 --> 00:02:45,480
Dakle, ako je vaš broj je u nedostatku
check50, po svemu sudeći,

54
00:02:45,480 --> 00:02:47,570
vjerojatno će
uspjeti našu provjeru, kao dobro.

55
00:02:47,570 --> 00:02:49,320
Ponekad ti dečki
ima prave odgovore.

56
00:02:49,320 --> 00:02:52,200
Kao, u pohlepni, neki od
imate pravo brojeve,

57
00:02:52,200 --> 00:02:53,960
ti samo isprintati neke dodatne stvari.

58
00:02:53,960 --> 00:02:55,940
I to extra stvar
zapravo ne ček,

59
00:02:55,940 --> 00:02:58,440
jer računalo ne
znam što to traži.

60
00:02:58,440 --> 00:03:00,981
I tako će se izvoditi samo kroz,
vidjeti da je vaš izlaz ne

61
00:03:00,981 --> 00:03:03,810
onome što očekujemo odgovor
da, i označiti da je u krivu.

62
00:03:03,810 --> 00:03:06,560
>> I znam što se dogodilo u
neke od svojih slučajeva ovaj tjedan.

63
00:03:06,560 --> 00:03:09,870
Pa sam otišao natrag i ručno
regraded svačiji kôd.

64
00:03:09,870 --> 00:03:12,780
U budućnosti ipak,
molimo, provjerite

65
00:03:12,780 --> 00:03:14,570
da radite
provjeriti 50 na svom kodu.

66
00:03:14,570 --> 00:03:17,970
Zato što je to vrsta boli za PU
morati vratiti i ručno ponovo ocijeniti

67
00:03:17,970 --> 00:03:21,197
svaki pset za svaki
jedan, malo promašio instanca.

68
00:03:21,197 --> 00:03:22,530
Pa nisam skinuti bodove.

69
00:03:22,530 --> 00:03:25,210
Mislim da sam skinuo možda
jedan ili dva za oblikovanje.

70
00:03:25,210 --> 00:03:27,710
U budućnosti iako, ako
ti si u nedostatku check50,

71
00:03:27,710 --> 00:03:31,330
bodovi će se poduzeti
off za ispravnost.

72
00:03:31,330 --> 00:03:35,020
>> Nadalje, psets su
zbog petkom u podne.

73
00:03:35,020 --> 00:03:38,990
Mislim da postoji sedam minuta
kasno poček da vam dati.

74
00:03:38,990 --> 00:03:42,434
Po Harvard vremena, oni smiju
biti sedam minuta kasno za sve.

75
00:03:42,434 --> 00:03:44,350
Dakle ovdje na Yaleu, mi ćemo
pridržavati se to kao dobro.

76
00:03:44,350 --> 00:03:47,910
Ali prilično mnogo, na 12:07,
ako vaš pset nije,

77
00:03:47,910 --> 00:03:49,720
to će biti označena kao kasno.

78
00:03:49,720 --> 00:03:53,160
I tako, dok je označena
tek je TA-- sam

79
00:03:53,160 --> 00:03:54,870
i dalje će se ocjenjivanje vaše psets.

80
00:03:54,870 --> 00:03:56,760
Dakle, i dalje ćete vidjeti ocjenu pojaviti.

81
00:03:56,760 --> 00:03:58,820
Međutim, znamo da je u
kraj semestra,

82
00:03:58,820 --> 00:04:02,270
sve kasni psets će biti samo
nulira automatski od strane računala.

83
00:04:02,270 --> 00:04:04,490
>> Mi to iz dva razloga.

84
00:04:04,490 --> 00:04:09,220
Jedan, ponekad smo dobili
Ispričao poput dekana isprike,

85
00:04:09,220 --> 00:04:10,762
kasnije da ja ne znam o još.

86
00:04:10,762 --> 00:04:13,761
Stoga smo željeli biti sigurni da smo ocjenjivanja
sve samo u slučaju, kao što sam

87
00:04:13,761 --> 00:04:15,080
nedostaje Dean je isprika.

88
00:04:15,080 --> 00:04:17,000
I drugo, imajte na
uma, još uvijek možete

89
00:04:17,000 --> 00:04:19,370
ispusti jedan pset da
ima puni opseg bodova.

90
00:04:19,370 --> 00:04:21,430
I tako smo željeli stupnja
sve svoje psets jednostavno

91
00:04:21,430 --> 00:04:24,730
kako bi bili sigurni da je vaš opseg je
postoji i da ste ih težak.

92
00:04:24,730 --> 00:04:29,150
Dakle, čak i ako je kasno, i dalje ćete
dobiti kredit za djelokrug točaka, mislim.

93
00:04:29,150 --> 00:04:33,730
>> Dakle pouka ove priče je, učiniti
je li vaše psets su na vrijeme.

94
00:04:33,730 --> 00:04:38,350
A ako nisu u na vrijeme,
znam da to nije velika.

95
00:04:38,350 --> 00:04:41,678
Da, prije nego što sam krenuti dalje, bilo tko imati
Bilo kakva pitanja vezana pset povratne informacije?

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

97
00:04:42,178 --> 00:04:43,630
>> PUBLIKA: Jeste li kažemo
može pasti jedan od psets?

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

99
00:04:44,296 --> 00:04:47,050
Dakle, postoji devet psets ukupni
tijekom semestra.

100
00:04:47,050 --> 00:04:50,610
A ako imate opseg
points-- tako opseg je jednostavno,

101
00:04:50,610 --> 00:04:53,567
prilično mnogo, vi pokušate
problem su stavljanjem u vremenu,

102
00:04:53,567 --> 00:04:56,150
ti pokazuje da ste
pokazali ste pročitali spec.

103
00:04:56,150 --> 00:04:57,191
To je prilično mnogo prostora.

104
00:04:57,191 --> 00:04:59,370
A ako ispunjava
Opseg poena, što

105
00:04:59,370 --> 00:05:03,360
može pasti najniže
jedan od punog opsega.

106
00:05:03,360 --> 00:05:06,790
Dakle, to je u svoju korist na
završiti i pokušajte svaki pset.

107
00:05:06,790 --> 00:05:10,320
>> Čak i ako nitko od upload--
im posao, stavi ih sve.

108
00:05:10,320 --> 00:05:13,711
A onda ćemo, nadamo se moći
vam dati neke od tih točaka natrag.

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

110
00:05:14,210 --> 00:05:16,780
Ima li još pitanja?

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

112
00:05:17,840 --> 00:05:21,960
>> Drugo, ured hours-- malo
Brzi Bilješke o radnog vremena.

113
00:05:21,960 --> 00:05:24,300
Prvo, došao početkom tjedna.

114
00:05:24,300 --> 00:05:26,909
Nitko nije nikada na
Radno vrijeme ponedjeljkom.

115
00:05:26,909 --> 00:05:28,700
Christabel došao
Radno vrijeme prošle noći.

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

117
00:05:29,691 --> 00:05:32,190
A što imamo u uredu
sata sinoć, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> PUBLIKA: Imali smo sladoled.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Pa to je točno, imali smo
sladoled u uredovno vrijeme prošle noći.

120
00:05:36,160 --> 00:05:39,390
Iako ne mogu vam obećati da
ćemo morati sladoled na radnog vremena

121
00:05:39,390 --> 00:05:43,230
svaki tjedan, što mogu obećati
je da će biti znatno

122
00:05:43,230 --> 00:05:45,380
Bolje učenik TA omjeru.

123
00:05:45,380 --> 00:05:47,650
Kao čitljiv, to je kao tri prema jedan.

124
00:05:47,650 --> 00:05:50,350
Dok, kontrast koji s
Četvrtak, imaš oko 150

125
00:05:50,350 --> 00:05:52,830
stvarno je naglasio djecu i ne sladoled.

126
00:05:52,830 --> 00:05:55,360
A to jednostavno nije produktivno za svakoga.

127
00:05:55,360 --> 00:05:58,730
Dakle pouka ove priče je, doći rano
za radnog vremena i dobre stvari

128
00:05:58,730 --> 00:06:00,310
dogodit će se.

129
00:06:00,310 --> 00:06:02,110
>> Također, dolaze spremni postavljati pitanja.

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

131
00:06:03,200 --> 00:06:05,420
Bez obzira što Tas, ja
mislim, je rekao:

132
00:06:05,420 --> 00:06:10,710
mi smo bili uzimajući par studente
koji dolaze u četvrtak, na, kao, 10:50

133
00:06:10,710 --> 00:06:15,100
nije čitao spec
biti kao mi pomoći, pomozi mi.

134
00:06:15,100 --> 00:06:18,200
Nažalost u tom trenutku, ne postoji
ne možemo mnogo učiniti kako bi vam pomoći.

135
00:06:18,200 --> 00:06:19,590
Dakle, molim Vas, došli početkom tjedna.

136
00:06:19,590 --> 00:06:22,040
Dođi rano za radnog vremena.

137
00:06:22,040 --> 00:06:23,350
Dođite spremni postavljati pitanja.

138
00:06:23,350 --> 00:06:25,310
Pazite da vas, kao
student, gdje su

139
00:06:25,310 --> 00:06:27,620
morate biti tako da
TAS mogu vas voditi zajedno,

140
00:06:27,620 --> 00:06:32,850
što je ono radno vrijeme
trebao biti dodijelili za.

141
00:06:32,850 --> 00:06:37,380
>> Drugo, tako da znam profesore
vole nas iznenaditi s testovima.

142
00:06:37,380 --> 00:06:39,439
Imao sam profesora one
kao, Yo, usput,

143
00:06:39,439 --> 00:06:41,230
sjetite se da na polovici trajanja
imate sljedećeg ponedjeljka.

144
00:06:41,230 --> 00:06:42,855
Da, nisam znao o toj polovici trajanja.

145
00:06:42,855 --> 00:06:45,630
Tako ću biti da TA
koji vam podsjeća sve da kviz

146
00:06:45,630 --> 00:06:47,270
0-- jer, znate, mi smo CS.

147
00:06:47,270 --> 00:06:50,730
Sada kada smo učinili polja, te dobiti
zašto je kviz 0, a ne 1 kviz, ha?

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

149
00:06:51,320 --> 00:06:52,490
Oh, dobio sam neke nasmijao na taj jedan.

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

151
00:06:53,120 --> 00:06:59,710
>> Dakle kviz 0 će biti 14. listopada, ako
ti si u dijelu ponedjeljka u srijedu

152
00:06:59,710 --> 00:07:02,920
i 15. listopada, ako ste u
odjeljak Utorak-četvrtak.

153
00:07:02,920 --> 00:07:05,630
To se ne odnosi na
one od vas na Harvardu

154
00:07:05,630 --> 00:07:10,350
who-- Mislim da svi ćete biti
uzimati kvizova 14..

155
00:07:10,350 --> 00:07:13,560
>> Tako da, sljedeći tjedan, ako
David je u predavanju, ide,

156
00:07:13,560 --> 00:07:15,747
Da, tako o tome
Kviz sljedeći tjedan, svi

157
00:07:15,747 --> 00:07:17,580
neće biti šokirani, jer
ste došli na odjeljak

158
00:07:17,580 --> 00:07:19,664
a vi znate da je vaš
kviz 0 je u dva tjedna.

159
00:07:19,664 --> 00:07:21,580
I mi ćemo imati pregled
sjednice i sve.

160
00:07:21,580 --> 00:07:26,360
Tako da nema brige o
se prepala za to.

161
00:07:26,360 --> 00:07:29,890
Bilo kakva pitanja before-- kakvih pitanja
na svim vezi logističkih poteškoća,

162
00:07:29,890 --> 00:07:32,591
ocjenjivanja, radno vrijeme, dijelovi?

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

164
00:07:33,090 --> 00:07:35,100
>> PUBLIKA: Dakle kviz je
će biti tijekom predavanja?

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

166
00:07:35,766 --> 00:07:39,460
Dakle kviza, mislim, 60
minute dodijelili u tom terminu

167
00:07:39,460 --> 00:07:42,240
da ćete samo uzeti
u dvorani.

168
00:07:42,240 --> 00:07:44,810
Dakle, ne morate doći u
na, kao, slučajnih 7:00.

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

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

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

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

173
00:07:50,840 --> 00:07:54,330
Tako ćemo
uvesti koncept za vas

174
00:07:54,330 --> 00:08:00,760
ovaj tjedan da je David je već neka vrsta
od dotaknuo u predavanju prošli tjedan.

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

176
00:08:02,010 --> 00:08:05,570
I kako mnogi od vas, dok je u
tijek pisanja psets,

177
00:08:05,570 --> 00:08:09,981
primijetili veliki gumb na kojem piše
"Debug" na vrhu vašeg IDE?

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

179
00:08:10,480 --> 00:08:13,770
Dakle, sada smo zapravo ću iznijeti
Otajstvo što to zapravo gumba

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

181
00:08:14,270 --> 00:08:16,790
A ja vam jamčim, to je
lijepa, lijepa stvar.

182
00:08:16,790 --> 00:08:20,740
>> Dakle, do sada, mislim
došlo je do dvije stvari

183
00:08:20,740 --> 00:08:23,320
studenti su obično
radi kada pogrešaka psets.

184
00:08:23,320 --> 00:08:27,635
Jedan od njih, oni ili dodati u
printf () - pa svakih nekoliko redaka,

185
00:08:27,635 --> 00:08:29,760
dodali su u printf () -
Oh, što je to varijabla?

186
00:08:29,760 --> 00:08:32,551
Oh, što je to promjenjiva now--
i vrsta vidjeti napredovanje

187
00:08:32,551 --> 00:08:33,940
vašeg koda, kao da radi.

188
00:08:33,940 --> 00:08:37,030
Ili drugi način djeca učiniti je
da samo napisati cijelu stvar

189
00:08:37,030 --> 00:08:38,610
a zatim ići ovako na kraju.

190
00:08:38,610 --> 00:08:39,970
Nadam se to radi.

191
00:08:39,970 --> 00:08:44,851
Jamčim ti, GDB je bolje
nego oba od tih metoda.

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

193
00:08:45,350 --> 00:08:46,980
Dakle, to će biti vaš novi najbolji prijatelj.

194
00:08:46,980 --> 00:08:51,780
Zato što je lijepa stvar
koji vizualno prikazuje kako

195
00:08:51,780 --> 00:08:54,850
što je vaš broj radi
na određenom mjestu

196
00:08:54,850 --> 00:08:57,486
kao i ono što sve svoje
varijable nosi,

197
00:08:57,486 --> 00:08:59,610
kao što su njihove vrijednosti,
u tom određenom trenutku.

198
00:08:59,610 --> 00:09:02,670
I na ovaj način, možete zaista
postavite prijelomnih točaka u kodu.

199
00:09:02,670 --> 00:09:04,350
Možete izvoditi kroz liniju po liniju.

200
00:09:04,350 --> 00:09:07,324
I GDB će samo za
ti, prikazani za vas,

201
00:09:07,324 --> 00:09:09,490
ono sve svoje varijable
su, što rade,

202
00:09:09,490 --> 00:09:10,656
što se događa u kodu.

203
00:09:10,656 --> 00:09:13,240
I na takav način, da je
tako mnogo lakše vidjeti

204
00:09:13,240 --> 00:09:17,120
što se događa, umjesto printf-ing
ili zapisivao svoje izjave.

205
00:09:17,120 --> 00:09:19,160
>> Tako ćemo napraviti primjer za to kasnije.

206
00:09:19,160 --> 00:09:20,660
Dakle, to se čini malo sažetak.

207
00:09:20,660 --> 00:09:23,490
Bez brige, mi ćemo učiniti primjere.

208
00:09:23,490 --> 00:09:29,170
I tako u biti, tri najveće,
najčešće korištene funkcije morat ćete u GDB

209
00:09:29,170 --> 00:09:32,500
su Dalje, Korak više,
i Korak u tipki.

210
00:09:32,500 --> 00:09:34,860
Idem nad glavom
Postoji, zapravo, upravo sada.

211
00:09:34,860 --> 00:09:40,930
>> Dakle, možete li vi svi vidite da
ili bih trebao uvećanje malo?

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

213
00:09:43,220 --> 00:09:44,470
U leđa, možete vidjeti?

214
00:09:44,470 --> 00:09:45,730
Trebam li zumirati?

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

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

217
00:09:49,390 --> 00:09:50,280
Idemo tamo.

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

219
00:09:50,960 --> 00:09:57,000
>> Tako sam, ovdje, moj
Provedba za pohlepni.

220
00:09:57,000 --> 00:10:01,430
I dok mnogi od vas pisali
pohlepni u while petlji form-- da

221
00:10:01,430 --> 00:10:04,890
je savršeno prihvatljiv način za napraviti
it-- još jedan način da to učinite je da se jednostavno

222
00:10:04,890 --> 00:10:06,280
podijeliti u modulom.

223
00:10:06,280 --> 00:10:09,290
Jer onda možete imati svoj
vrijednost, a zatim su svoj ostatak.

224
00:10:09,290 --> 00:10:11,150
I onda možete jednostavno
dodajte sve to zajedno.

225
00:10:11,150 --> 00:10:13,390
Da li logiku što radim
Ovdje smisla svima,

226
00:10:13,390 --> 00:10:14,117
Prije nego što počnemo?

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

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

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

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

231
00:10:19,210 --> 00:10:21,290
To je prilično seksi komad
koda, rekao bih.

232
00:10:21,290 --> 00:10:23,502
Kao što sam rekao, David, u
predavanje, nakon nekog vremena,

233
00:10:23,502 --> 00:10:25,960
svi vi ćete početi dobivati ​​kod
kao nešto što je lijepo.

234
00:10:25,960 --> 00:10:29,950
A ponekad kad vidite lijepo
kod, to je takav prekrasan osjećaj.

235
00:10:29,950 --> 00:10:35,410
>> Pa ipak, dok je to kod vrlo
lijepo, to ne radi ispravno.

236
00:10:35,410 --> 00:10:37,750
Tako ćemo pokrenuti check50 o tome.

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

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

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

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

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

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

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

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

245
00:10:52,890 --> 00:10:53,900
Tako smo pokrenuti check50.

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

247
00:11:01,550 --> 00:11:07,170
>> A što vi vidite ovdje,
to nije par slučajeva.

248
00:11:07,170 --> 00:11:10,165
A za neke od vas, u
Naravno da radi svoj problem seta,

249
00:11:10,165 --> 00:11:11,110
ti si kao, ah, zašto se ne radi.

250
00:11:11,110 --> 00:11:13,318
Zašto je to raditi za neke
vrijednosti, ali ne i za druge?

251
00:11:13,318 --> 00:11:17,760
Pa, GDB će vam pomoći shvatiti
zašto ti inputi nisu radili.

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

253
00:11:18,320 --> 00:11:21,640
Tako ćemo vidjeti, jedan od
Provjere sam u nedostatku u check50

254
00:11:21,640 --> 00:11:24,920
je ulazni vrijednost 0,41.

255
00:11:24,920 --> 00:11:27,830
Dakle točan odgovor da
trebali biti uzimajući je 4.

256
00:11:27,830 --> 00:11:33,090
No, umjesto onoga što sam ispis
je 3-N, što je netočno.

257
00:11:33,090 --> 00:11:36,190
Pa neka je samo pokrenuti to ručno, samo
pobrinite se da check50 radi.

258
00:11:36,190 --> 00:11:36,940
Učinimo ./greedy.

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

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

261
00:11:43,340 --> 00:11:43,840
Idemo tamo.

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

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

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

265
00:11:47,670 --> 00:11:49,550
Učinimo 0.41.

266
00:11:49,550 --> 00:11:52,590
I Yep, vidimo ovdje
da je to izlaza 3

267
00:11:52,590 --> 00:11:55,160
kada je točan odgovor,
U stvari, treba biti 4.

268
00:11:55,160 --> 00:12:01,460
Tako ćemo ući GDB i vidjeti kako ćemo
možete ići oko rješavanja tog problema.

269
00:12:01,460 --> 00:12:03,992
>> Dakle, prvi korak u
Uvijek ispravljanje pogrešaka kôd

270
00:12:03,992 --> 00:12:05,950
je postaviti prijelomna točka,
ili točka u kojoj ste

271
00:12:05,950 --> 00:12:09,079
Želite računala ili
debugger za početak obličje at.

272
00:12:09,079 --> 00:12:11,120
Dakle, ako ne stvarno
Znaš što je tvoj problem,

273
00:12:11,120 --> 00:12:14,670
Obično, tipična stvar želimo
učiniti je postaviti našim Kontrolna točka na glavni.

274
00:12:14,670 --> 00:12:18,520
Dakle, ako vi možete vidjeti
crveni gumb pravo postoji,

275
00:12:18,520 --> 00:12:22,860
Da, to je meni podešavanje a
Prijelomna točka za glavnu funkciju.

276
00:12:22,860 --> 00:12:24,130
Kliknem da.

277
00:12:24,130 --> 00:12:26,130
>> I onda ja mogu ići i do mog gumb Debug.

278
00:12:26,130 --> 00:12:27,036
Sam pogodio taj gumb.

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

280
00:12:31,710 --> 00:12:36,555
Dopustite mi uvećanje natrag ako mogu.

281
00:12:36,555 --> 00:12:38,020
Idemo tamo.

282
00:12:38,020 --> 00:12:40,730
Tako smo, evo, ploča na desnoj strani.

283
00:12:40,730 --> 00:12:43,680
Žao mi je, dečki u leđa, što
stvarno ne mogu vidjeti jako dobro.

284
00:12:43,680 --> 00:12:49,090
Ali u biti, sve
to pravo ploča radi

285
00:12:49,090 --> 00:12:53,130
se praćenje i označena
linija, što je linija koda

286
00:12:53,130 --> 00:12:56,640
da računalo trenutno radi,
kao i sve svoje varijable

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

288
00:12:57,600 --> 00:13:00,487
>> Pa imaš centi, novčići, n,
svi proglasili za različite stvari

289
00:13:00,487 --> 00:13:01,070
u ovom trenutku.

290
00:13:01,070 --> 00:13:04,850
Bez brige, jer imamo zapravo nije
inicijalizacije ih na bilo varijable još.

291
00:13:04,850 --> 00:13:07,200
Tako je u računalu,
Računalo je samo vidio,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 bio je posljednji korišteni funkcija
te memorijskog prostora u mom računalu.

293
00:13:14,376 --> 00:13:16,000
I tako je to u kojoj se trenutno nalazi centi.

294
00:13:16,000 --> 00:13:19,360
Ali ne da nakon što pokrenete kod,
to bi trebao postati inicijalizacije.

295
00:13:19,360 --> 00:13:24,110
>> Tako ćemo proći, liniju
linija, što se ovdje događa.

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

297
00:13:25,350 --> 00:13:29,400
Dakle, ovdje su tri
tipke koje sam upravo objasnio.

298
00:13:29,400 --> 00:13:34,090
Imate igrati, ili Run funkciju,
gumb, imate korak iznad gumba,

299
00:13:34,090 --> 00:13:36,600
a imate i korak u gumb.

300
00:13:36,600 --> 00:13:41,260
A u biti, sve troje
ih jednostavno proći kroz kodu

301
00:13:41,260 --> 00:13:42,690
i raditi različite stvari.

302
00:13:42,690 --> 00:13:45,680
>> Tako obično, kad si ispravljanje pogrešaka,
mi ne želimo samo pritisnite Play,

303
00:13:45,680 --> 00:13:47,930
jer Igra će samo pokrenuti
Vaš broj na kraj njega.

304
00:13:47,930 --> 00:13:49,070
A onda nećete zapravo
Znaš što je tvoj problem

305
00:13:49,070 --> 00:13:51,432
je, osim ako ste postavili više breakpoints.

306
00:13:51,432 --> 00:13:53,890
Ako ste postavili više prijelomnih točaka,
to će samo automatski

307
00:13:53,890 --> 00:13:56,030
pokrenuti iz jedne prelomne tačke,
na sljedeći, na sljedeći.

308
00:13:56,030 --> 00:13:58,030
No, u ovom slučaju mi ​​smo
samo da je jedan, jer mi

309
00:13:58,030 --> 00:13:59,970
želite raditi naš put
od vrha prema dolje do dna.

310
00:13:59,970 --> 00:14:04,830
Tako ćemo ignorirati tu tipku
sada za potrebe ovog programa.

311
00:14:04,830 --> 00:14:08,230
>> Tako je korak više funkcija samo
koraci više svaku liniju

312
00:14:08,230 --> 00:14:11,510
i govori što
računalo radi.

313
00:14:11,510 --> 00:14:14,630
Korak u funkciju prolazi
u stvarni funkciju

314
00:14:14,630 --> 00:14:16,000
to ti je na liniji koda.

315
00:14:16,000 --> 00:14:19,070
Tako, na primjer, kao što printf (),
da je funkcija, zar ne?

316
00:14:19,070 --> 00:14:21,980
Da sam htio fizički korak
u printf () funkcije,

317
00:14:21,980 --> 00:14:25,610
Ja bi zapravo ići u komadu
broj gdje je napisao printf () i vidjeti

318
00:14:25,610 --> 00:14:26,730
što se događa tamo.

319
00:14:26,730 --> 00:14:29,924
>> Ali obično, pretpostavimo da
kod koje smo dati radi.

320
00:14:29,924 --> 00:14:31,340
Pretpostavljamo da printf () radi.

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

322
00:14:33,170 --> 00:14:35,170
Dakle, nema potrebe da se
korak u tim funkcijama.

323
00:14:35,170 --> 00:14:37,170
Ali ako postoji funkcija
da sami pišu

324
00:14:37,170 --> 00:14:39,060
koju želite provjeriti
što se događa,

325
00:14:39,060 --> 00:14:41,200
što bi željeli korak
u tu funkciju.

326
00:14:41,200 --> 00:14:43,940
>> Dakle, sada smo samo ćemo
prekoračiti ovaj dio koda.

327
00:14:43,940 --> 00:14:44,485
Tako ćemo vidjeti.

328
00:14:44,485 --> 00:14:46,547
Oh, print, "O hai, kako
mnogo promjena je dugovao? "

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

330
00:14:47,130 --> 00:14:49,830
Znamo da radi,
tako da smo korak preko njega.

331
00:14:49,830 --> 00:14:53,290
>> Dakle nje, što je naš plutaju da
mi smo initialized-- ili declared--

332
00:14:53,290 --> 00:14:56,810
gore na vrhu, mi smo sada
izjednačavanje to GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Tako ćemo korak preko toga.

334
00:14:57,810 --> 00:14:59,580
A mi vidjeti na
Dno ovdje, program

335
00:14:59,580 --> 00:15:03,360
me navelo da unos vrijednost.

336
00:15:03,360 --> 00:15:08,580
Tako ćemo Unesite vrijednost želimo
testirati ovdje, što je 0,41.

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

338
00:15:09,160 --> 00:15:12,780
>> Tako sada n- to vi vidite
Ovdje, na bottom-- je

339
00:15:12,780 --> 00:15:15,140
stored-- jer mi
još nisu zaobljeni, to je

340
00:15:15,140 --> 00:15:19,540
pohranjen u ovoj poput diva
plovak koji je 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
što je dovoljno blizu da naš
svrhe, upravo sada, na 0,41.

342
00:15:22,550 --> 00:15:26,090
A onda ćemo vidjeti kasnije, kao što smo
nastavak koračni preko programa,

343
00:15:26,090 --> 00:15:29,850
Nakon ovog, n postala
zaokružene centi postao 41.

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

345
00:15:30,350 --> 00:15:32,230
Dakle, znamo da naše zaokruživanja radi.

346
00:15:32,230 --> 00:15:34,700
Znamo da imamo
točan broj centi,

347
00:15:34,700 --> 00:15:36,990
pa znamo da je to
zapravo nije problem.

348
00:15:36,990 --> 00:15:40,050
>> Tako smo i dalje napravio
u ovom programu.

349
00:15:40,050 --> 00:15:40,900
Idemo ovdje.

350
00:15:40,900 --> 00:15:46,139
I tako, nakon ove linije koda, mi
treba znati koliko četvrtine imamo.

351
00:15:46,139 --> 00:15:46,680
Mi korak više.

352
00:15:46,680 --> 00:15:52,040
A vidiš mi, u stvari, ima jedan
kvartal, jer smo oduzeti 25

353
00:15:52,040 --> 00:15:53,790
iz naše početne vrijednosti 41.

354
00:15:53,790 --> 00:15:55,890
I imamo 16 otišao u našim centi.

355
00:15:55,890 --> 00:15:58,830
>> Da li su svi shvate kako
Program je napravio preko

356
00:15:58,830 --> 00:16:02,980
i zašto centi sada postala 16
i zašto, sada, kovanica je postao 1?

357
00:16:02,980 --> 00:16:04,610
Je li svatko slijedi tu logiku?

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

359
00:16:05,110 --> 00:16:07,860
Tako da u tom trenutku
Program je radni, zar ne?

360
00:16:07,860 --> 00:16:09,797
Znamo to radi točno
ono što mi to želimo.

361
00:16:09,797 --> 00:16:11,880
A mi zapravo nije
moraju ispisati, oh, što

362
00:16:11,880 --> 00:16:14,430
je centa u ovom trenutku,
Što je kovanice u ovom trenutku.

363
00:16:14,430 --> 00:16:17,170
>> Mi i dalje ide kroz program.

364
00:16:17,170 --> 00:16:18,100
Korak više.

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

366
00:16:18,620 --> 00:16:19,700
Idemo preko novčića.

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

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

369
00:16:22,367 --> 00:16:23,450
I sada imamo dva novčića.

370
00:16:23,450 --> 00:16:25,260
To je točno.

371
00:16:25,260 --> 00:16:31,555
>> Idemo preko novčana jedinica i vidimo
da imamo lijevo preko centi.

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

373
00:16:32,680 --> 00:16:37,540
Ovdje gore na programu, trebao sam
da oduzme moje novčana jedinica.

374
00:16:37,540 --> 00:16:39,400
Možda jednostavno nisam bila
radi te crte pravo.

375
00:16:39,400 --> 00:16:42,190
I nažalost, možete vidjeti
ovdje, jer znamo

376
00:16:42,190 --> 00:16:44,360
da smo koračni
kroz linije 32 i 33,

377
00:16:44,360 --> 00:16:50,560
to je gdje je naš program
nepropisno imao varijabli trčanje.

378
00:16:50,560 --> 00:16:55,136
Tako možemo pogledati i vidjeti, oh,
Ja oduzimanjem centi ovdje

379
00:16:55,136 --> 00:16:57,010
ali nisam zapravo
dodajući da moj novac vrijednosti.

380
00:16:57,010 --> 00:16:57,860
Ja sam dodao da centi.

381
00:16:57,860 --> 00:17:00,234
A ja ne želim dodati
centi, želim dodati novca.

382
00:17:00,234 --> 00:17:05,420
Dakle, ako smo promijenili da bi kovanica,
imamo program rada.

383
00:17:05,420 --> 00:17:06,730
Mogu se izvoditi check50.

384
00:17:06,730 --> 00:17:11,063
Vi samo možete izaći iz GDB prava
ovdje i onda pokrenuti check50 opet.

385
00:17:11,063 --> 00:17:11,938
Upravo sam mogao učiniti.

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

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

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

389
00:17:19,940 --> 00:17:22,819
I ovdje, to je tisak
iz pravi odgovor.

390
00:17:22,819 --> 00:17:26,569
>> Dakle, kao što vi vidite, GDB
je stvarno moćan alat

391
00:17:26,569 --> 00:17:29,940
kad imamo toliko broj
događa i toliko varijabli

392
00:17:29,940 --> 00:17:32,510
da je teško za nas, kao što je
ljudski, pratiti.

393
00:17:32,510 --> 00:17:35,360
Računalo, u GDB
program za pronalaženje pogrešaka, ima mogućnost

394
00:17:35,360 --> 00:17:37,020
pratiti sve.

395
00:17:37,020 --> 00:17:40,480
Znam, u Visionaire, vi vjerojatno
možda pogoditi neke segmentacije greške

396
00:17:40,480 --> 00:17:43,150
zato što su trčanje
izvan granica svoje polje.

397
00:17:43,150 --> 00:17:46,510
U primjeru Caesar, koji je
upravo ono što sam provoditi ovdje.

398
00:17:46,510 --> 00:17:50,060
>> Tako sam zaboravio provjeriti
Što će se dogoditi ako ja

399
00:17:50,060 --> 00:17:52,510
nisu imali dva argumente naredbenog retka.

400
00:17:52,510 --> 00:17:53,880
Samo nisam stavio u toj prijavi.

401
00:17:53,880 --> 00:17:57,380
I tako, ako sam pokrenuti Debug-- postaviti
moja prijelomna točka na pravo postoji.

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

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

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

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

406
00:18:17,050 --> 00:18:20,350
Pa zapravo, GDB je trebao
da su mi rekli tamo

407
00:18:20,350 --> 00:18:22,300
bio kriv segmentacije tamo.

408
00:18:22,300 --> 00:18:24,883
Ne znam što se događa
pravo postoji, ali kad sam ga vodio,

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

410
00:18:25,590 --> 00:18:29,410
Kada pokrenete linija koda putem i
GDB možda samo iznenada prestati na vas,

411
00:18:29,410 --> 00:18:31,540
ići gore i pogledajte što je crvena pogreška.

412
00:18:31,540 --> 00:18:33,930
To će vam reći, hej, ti
imao kvar segmentiranja,

413
00:18:33,930 --> 00:18:38,550
što znači da ste pokušali pristupiti
Prostor u niz koji nije postojao.

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

415
00:18:39,050 --> 00:18:43,280
>> Dakle, u sljedećem problemu
Postavite ovaj tjedan, vi

416
00:18:43,280 --> 00:18:45,600
vjerojatno će imati puno
varijable plutajući oko.

417
00:18:45,600 --> 00:18:48,560
Nećeš biti sigurni što
svi oni znače u određenom trenutku.

418
00:18:48,560 --> 00:18:53,560
Dakle GDB stvarno će vam pomoći u otkrivanju
što su sve izjednačavanje

419
00:18:53,560 --> 00:18:55,940
i biti u mogućnosti da se vidi da vizualno.

420
00:18:55,940 --> 00:19:01,995
Je li netko zbunjeni o tome
ništa od toga radi?

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
U redu.

424
00:19:10,620 --> 00:19:14,260
Tako je nakon toga smo
će roniti pravo

425
00:19:14,260 --> 00:19:17,562
u četiri različite
vrste sorti za ovaj tjedan.

426
00:19:17,562 --> 00:19:19,520
Koliko vas prvo
od svega, prije nego što počnemo,

427
00:19:19,520 --> 00:19:23,020
Pročitao cijelu spec za pset3?

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

429
00:19:23,824 --> 00:19:24,740
Ja sam ponosan na vas momci.

430
00:19:24,740 --> 00:19:29,110
To je kao pola klase, koji
je znatno više nego prošli put.

431
00:19:29,110 --> 00:19:33,950
>> Dakle, to je super, jer kad
govorimo o sadržaju

432
00:19:33,950 --> 00:19:36,170
u lecture-- ili žao,
u section-- volim

433
00:19:36,170 --> 00:19:38,210
povezati mnogo toga
natrag na ono što je pset

434
00:19:38,210 --> 00:19:40,210
i kako želite
implementirati da u svom pset.

435
00:19:40,210 --> 00:19:42,400
Dakle, ako ste došli s
pročitajte spec, to će

436
00:19:42,400 --> 00:19:45,510
biti puno lakše za vas da razumijete
ono što sam pričaju kad kažem,

437
00:19:45,510 --> 00:19:48,720
Oh, hej, to može biti jako
dobro mjesto za provesti ovu vrstu.

438
00:19:48,720 --> 00:19:52,870
Dakle, oni od vas koji su pročitali
spec znaju da, kao dio svoje pset,

439
00:19:52,870 --> 00:19:54,900
ti si idući u morati
napisati tip vrste.

440
00:19:54,900 --> 00:19:58,670
Dakle, to može biti vrlo korisno
za puno vas danas.

441
00:19:58,670 --> 00:20:01,760
>> Tako ćemo krenuti s,
u biti, najviše jednostavan tip

442
00:20:01,760 --> 00:20:04,580
od vrsta, odabir vrsta.

443
00:20:04,580 --> 00:20:06,800
Tipična algoritam za
kako ćemo ići o tome

444
00:20:06,800 --> 00:20:10,460
is-- David je po njima sve u
predavanje, pa ću se brzo kreću

445
00:20:10,460 --> 00:20:13,900
here-- je bitno, što
imaju niz vrijednosti.

446
00:20:13,900 --> 00:20:17,170
I onda naći
Najmanji Nesortirano vrijednost

447
00:20:17,170 --> 00:20:20,200
i zamijeniti tu vrijednost s
prvi Nesortirano vrijednost.

448
00:20:20,200 --> 00:20:22,700
I onda ti samo ponavljamo
s ostatkom vašeg popisa.

449
00:20:22,700 --> 00:20:25,740
>> I ovdje je vizualni objašnjenje
kako bi to moglo raditi.

450
00:20:25,740 --> 00:20:30,460
Tako na primjer, ako smo za početak
s nizom od pet elemenata, indeks

451
00:20:30,460 --> 00:20:35,910
0 do 4, s 3, 5, 2, 6 i 4 vrijednosti
stavljen u array-- tako upravo sada,

452
00:20:35,910 --> 00:20:38,530
samo ćemo pretpostaviti
da su svi nesortiran

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

454
00:20:41,130 --> 00:20:44,130
>> Pa kako izbor vrsta bi
Rad je da bi prvi

455
00:20:44,130 --> 00:20:46,800
izvoditi kroz cijelosti
od nerazvrstani polja.

456
00:20:46,800 --> 00:20:49,120
Bilo bi izabrati najmanju vrijednost.

457
00:20:49,120 --> 00:20:51,750
U ovom slučaju, 3, pravo
Sada, je najmanji.

458
00:20:51,750 --> 00:20:52,680
Ona dobiva 5.

459
00:20:52,680 --> 00:20:55,620
Nope, 5 nije veći than--
ili mi je, ne manje than-- 3.

460
00:20:55,620 --> 00:20:57,779
Dakle, minimalna vrijednost je i dalje 3.

461
00:20:57,779 --> 00:20:58,695
I onda ste dobili na 2.

462
00:20:58,695 --> 00:21:00,990
Računalo vidi, oh, 2 manje od 3.

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

464
00:21:02,750 --> 00:21:06,630
I tako 2 zamjene s tog prvog vrijednosti.

465
00:21:06,630 --> 00:21:10,702
>> Dakle, nakon što jednom prolazu, doista ne vidim
koji su zamijenili 2 i 3.

466
00:21:10,702 --> 00:21:13,910
I samo ćemo nastaviti raditi
ovo ponovno s ostatkom polja.

467
00:21:13,910 --> 00:21:17,660
Tako ćemo samo prolaze kroz
posljednjih četiri indeksi polja.

468
00:21:17,660 --> 00:21:20,670
Mi ćemo vidjeti da 3
sljedeća minimalna vrijednost.

469
00:21:20,670 --> 00:21:23,240
Tako ćemo mijenjati da sa 4.

470
00:21:23,240 --> 00:21:26,900
I onda mi samo ide da bi
trčanje kroz sve, na kraju, što

471
00:21:26,900 --> 00:21:33,730
doći do sortiranog niza u kojem
2, 3, 4, 5, i 6 su svi razvrstani.

472
00:21:33,730 --> 00:21:37,530
Da li su svi razumiju logiku
kako je izbor vrsta radi?

473
00:21:37,530 --> 00:21:39,669
>> Vi samo morati nekakvu
minimalne vrijednosti.

474
00:21:39,669 --> 00:21:41,210
Ti praćenje što je to.

475
00:21:41,210 --> 00:21:45,170
I kad god ga pronaći, možete ga zamijeniti
s prvim vrijednosti u array--

476
00:21:45,170 --> 00:21:48,740
ili, nije prvi value--
sljedeća vrijednost u polju.

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

478
00:21:50,150 --> 00:21:55,460
>> Dakle, što je vama vrsta
Vidio iz kratak pogled,

479
00:21:55,460 --> 00:21:58,450
ćemo pseudokod ovo.

480
00:21:58,450 --> 00:22:02,510
Dakle, ako vi u leđa želite
tvore skupinu, sve na stol

481
00:22:02,510 --> 00:22:06,170
može formirati malo partnera, idem
da vam dečki poput tri minute

482
00:22:06,170 --> 00:22:08,190
samo kroz razgovor
logika, na engleskom jeziku,

483
00:22:08,190 --> 00:22:14,161
kako bismo mogli provesti
pseudokod napisati odabir vrsta.

484
00:22:14,161 --> 00:22:14,910
A tu je bombona.

485
00:22:14,910 --> 00:22:16,118
Molimo vas da dođete i dobiti slatkiše.

486
00:22:16,118 --> 00:22:19,520
Ako ste u leđima i želite
Candy, ja mogu baciti bombon na vas.

487
00:22:19,520 --> 00:22:22,850
Zapravo, to you-- cool.

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

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

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

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

492
00:25:23,880 --> 00:25:27,140
>> Dakle, ako želimo, kao
klasa, pisati pseudokod

493
00:25:27,140 --> 00:25:30,466
koliko bi se moglo pristupiti
ovaj problem, samo slobodno.

494
00:25:30,466 --> 00:25:32,340
Ja ću samo ići okolo i,
kako, pitajte grupe

495
00:25:32,340 --> 00:25:35,065
za sljedeću liniju
što bismo trebali raditi.

496
00:25:35,065 --> 00:25:37,840
Dakle, ako vi želite započeti
off, što je prva stvar

497
00:25:37,840 --> 00:25:40,600
učiniti kada pokušavate
implementirati način da se riješi ovaj program

498
00:25:40,600 --> 00:25:43,480
selektivno sortirati popis?

499
00:25:43,480 --> 00:25:46,349
Neka je samo pretpostavimo
imaju niz, u redu?

500
00:25:46,349 --> 00:25:49,088
>> PUBLIKA: Vi želite stvoriti neke
vrsta [nečujan] da si

501
00:25:49,088 --> 00:25:50,420
trčanje kroz cijelu lepezu.

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

503
00:25:51,128 --> 00:25:54,100
Dakle, ti si idući u ištanje to ponoviti
kroz svaki prostor, zar ne?

504
00:25:54,100 --> 00:26:05,490
Odlično.

505
00:26:05,490 --> 00:26:08,600
Ako vi želite mi dati
Sljedeći line-- da, u leđa.

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

507
00:26:11,414 --> 00:26:13,290
>> PUBLIKA: Provjerite ih
sve za najmanji.

508
00:26:13,290 --> 00:26:14,248
>> ANDI PENG: Tu idemo.

509
00:26:14,248 --> 00:26:17,438
Zato želimo proći i provjerite
vidjeti što je minimalna vrijednost, zar ne?

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

511
00:26:22,110 --> 00:26:24,840
Idem skratiti da bi "min."

512
00:26:24,840 --> 00:26:27,658
Što vi želite učiniti nakon
ste pronašli najmanju vrijednost?

513
00:26:27,658 --> 00:26:28,533
>> PUBLIKA: [nečujan]

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

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Znači ti si idući u ištanje to
prebacite ga s prvom od tog niza,

516
00:26:33,150 --> 00:26:33,650
zar ne?

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

518
00:26:45,120 --> 00:26:46,850
To je početak, ja ću reći.

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

520
00:26:47,220 --> 00:26:50,386
Pa sada da ste zamijenili prvi
jedan, što želiš raditi nakon toga?

521
00:26:50,386 --> 00:26:54,840
Dakle, sada znamo da je to neki ovdje
mora biti najmanja vrijednost, zar ne?

522
00:26:54,840 --> 00:26:58,310
Onda imate dodatni odmor
od niza koji je Nesortirano.

523
00:26:58,310 --> 00:27:01,569
Dakle, ono što želite učiniti ovdje, ako vas
dečki žele mi dati sljedeći redak?

524
00:27:01,569 --> 00:27:04,610
PUBLIKA: Dakle želite ponoviti
kroz ostatak polja.

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

526
00:27:05,276 --> 00:27:09,857
I tako ono što se kroz iterating
vrsta podrazumijeva ćemo vjerojatno trebati?

527
00:27:09,857 --> 00:27:10,440
Koja vrsta of--

528
00:27:10,440 --> 00:27:12,057
>> PUBLIKA: Oh, dodatna varijabla?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Vjerojatno
drugi za petlje, zar ne?

530
00:27:13,890 --> 00:27:28,914
Tako smo vjerojatno idući u ištanje
da ponoviti through-- super.

531
00:27:28,914 --> 00:27:31,830
A onda ćeš se vratiti i
vjerojatno ponovno provjerite minimum,

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

533
00:27:32,100 --> 00:27:34,975
I ti ćeš ponavljamo
ovo, jer petlje samo ide

534
00:27:34,975 --> 00:27:36,010
držati trčanje, zar ne?

535
00:27:36,010 --> 00:27:39,190
>> Dakle, kao što vi vidite, mi
samo opći pseudokod

536
00:27:39,190 --> 00:27:41,480
kako želimo ovaj program izgledati.

537
00:27:41,480 --> 00:27:46,646
Ovo ponoviti ovdje, ono što radimo
obično je potrebno napisati u našem kodu

538
00:27:46,646 --> 00:27:49,270
ako želimo ponoviti preko jedne
niz, što tip od strukture?

539
00:27:49,270 --> 00:27:51,030
Mislim Christabel
već je to rekao prije.

540
00:27:51,030 --> 00:27:51,500
>> PUBLIKA: for petlje.

541
00:27:51,500 --> 00:27:52,160
>> ANDI PENG: for petlje?

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

543
00:27:52,770 --> 00:27:56,060
Dakle, ovo je vjerojatno
će biti za petlju.

544
00:27:56,060 --> 00:27:59,240
Što je provjeriti ovdje će se podrazumijeva?

545
00:27:59,240 --> 00:28:02,536
Obično, ako želite provjeriti
ako je nešto nešto else--

546
00:28:02,536 --> 00:28:03,270
>> PUBLIKA: Ako.

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

548
00:28:06,790 --> 00:28:10,790
A onda je swap ovdje, mi ćemo
ići preko kasnije, jer Davida

549
00:28:10,790 --> 00:28:12,770
prošao kroz koji je u predavanju, kao dobro.

550
00:28:12,770 --> 00:28:14,580
A onda druga ponoviti implies--

551
00:28:14,580 --> 00:28:15,120
>> PUBLIKA: Još jedan za petlju.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another for petlja, upravo.

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

554
00:28:19,870 --> 00:28:22,000
Dakle, ako tražimo
ovo ispravno, mi

555
00:28:22,000 --> 00:28:24,680
možete vidjeti da smo vjerojatno
Trebat će ugniježđena za petlje

556
00:28:24,680 --> 00:28:28,330
sa uvjet u tu
a onda stvarni dio koda koji je

557
00:28:28,330 --> 00:28:31,360
će zamijeniti vrijednosti.

558
00:28:31,360 --> 00:28:35,980
Pa sam samo općenito napisano
pseudokod kod ovdje.

559
00:28:35,980 --> 00:28:38,910
A onda smo zapravo događa
fizički, kao klasu,

560
00:28:38,910 --> 00:28:40,700
pokušati provesti ovo danas.

561
00:28:40,700 --> 00:28:42,486
Idemo natrag u ovom 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
Zašto je to not-- tu je.

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

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

567
00:28:55,834 --> 00:28:57,500
Žao nam je, dopustite mi da povećavanje malo više.

568
00:28:57,500 --> 00:28:59,310
Idemo tamo.

569
00:28:59,310 --> 00:29:05,060
Sve što radim ovdje sam stvoren
program koji se zove "izbor / sort.c."

570
00:29:05,060 --> 00:29:10,860
Napravio sam niz devet
vrijednosti, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Trenutno, kao što možete
Vidite, oni su neuređen.

572
00:29:14,370 --> 00:29:17,880
nje će biti broj koji
kaže vam iznos vrijednosti

573
00:29:17,880 --> 00:29:18,920
imate u nizu.

574
00:29:18,920 --> 00:29:20,670
U ovom slučaju, imamo devet vrijednosti.

575
00:29:20,670 --> 00:29:23,760
A ja sam samo dobio za petlju ovdje
koji ispisuje iz nesortiranog polje.

576
00:29:23,760 --> 00:29:28,370
>> I na kraju, ja sam dobio za
petlja koja samo ispisuje ponovo.

577
00:29:28,370 --> 00:29:32,070
Dakle teoretski, ako ovaj program
ispravno radi, na kraju,

578
00:29:32,070 --> 00:29:35,670
trebali vidjeti tiskani for petlje
u kojoj 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 su sve ispravno u redu.

580
00:29:39,310 --> 00:29:43,410
>> Dakle, imamo našu pseudokod ovdje.

581
00:29:43,410 --> 00:29:46,090
Se bilo tko ištanje to-- Ja sam samo
ići tražiti volunteers--

582
00:29:46,090 --> 00:29:49,540
reci mi točno što tip, ako
želimo, prvi, samo ponoviti

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

584
00:29:52,840 --> 00:29:55,204
Što je linija koda sam
Vjerojatno će trebati ovdje?

585
00:29:55,204 --> 00:29:56,990
>> PUBLIKA: [nečujan]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Da, osjećam
besplatno to-- Nažalost,

587
00:29:59,010 --> 00:30:02,318
ne moraju stajati up-- dojam
besplatno podići svoj glas malo.

588
00:30:02,318 --> 00:30:08,190
>> PUBLIKA: Za int ja jednako 0--

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

590
00:30:10,690 --> 00:30:15,220
>> PUBLIKA: ja manja od duljine polja.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Tako bi se u
smeta ovdje, jer mi

592
00:30:19,630 --> 00:30:23,060
nemaju funkciju koja
govori nam da je duljina niza,

593
00:30:23,060 --> 00:30:25,790
Već smo
vrijednost koja pohranjuje to.

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

595
00:30:27,920 --> 00:30:31,010
Još jedna stvar koju treba imati
u mind-- u nizu

596
00:30:31,010 --> 00:30:33,940
devet vrijednosti, što su indeksi?

597
00:30:33,940 --> 00:30:38,720
Recimo samo to polje bilo 0 do 3.

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

599
00:30:41,500 --> 00:30:45,530
To nije 4, iako postoji
Četiri vrijednosti u nizu.

600
00:30:45,530 --> 00:30:49,866
>> Dakle ovdje, moramo biti vrlo oprezni
o tome što je naš uvjet za duljinu

601
00:30:49,866 --> 00:30:50,490
će biti.

602
00:30:50,490 --> 00:30:51,948
>> PUBLIKA: Zar ne bi bilo n minus 1?

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

604
00:30:54,440 --> 00:30:57,379
Da li to smisla, zašto
to je n minus 1, svatko?

605
00:30:57,379 --> 00:30:58,920
To je zato što su nizovi nula indeksirana.

606
00:30:58,920 --> 00:31:02,010
Oni počinju u 0 i pokrenuti do n minus 1.

607
00:31:02,010 --> 00:31:03,210
Da, to je malo zeznuto.

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

609
00:31:03,730 --> 00:31:05,929
I onda--

610
00:31:05,929 --> 00:31:08,054
PUBLIKA: Isnt'1 da
već zbrinuta ipak,

611
00:31:08,054 --> 00:31:11,400
strane samo ne govori "manje ili
jednako "i samo govori" manje od? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: To je
jako dobro pitanje.

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

614
00:31:13,630 --> 00:31:17,410
Ali isto tako, na način na koji smo
provedbu provjere pravo,

615
00:31:17,410 --> 00:31:19,120
morate usporediti dvije vrijednosti.

616
00:31:19,120 --> 00:31:21,009
Tako da zapravo žele
ostaviti "na" prazna.

617
00:31:21,009 --> 00:31:23,050
Jer ako usporedite
ovo, ne ide

618
00:31:23,050 --> 00:31:25,530
ništa nakon nje
usporediti, zar ne?

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

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

621
00:31:29,297 --> 00:31:30,380
Dodajmo naše zagrade u.

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

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

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

625
00:31:34,710 --> 00:31:39,117
Tako smo na početku
naše vanjske petlje.

626
00:31:39,117 --> 00:31:41,450
Dakle, sada smo vjerojatno želite
stvoriti varijablu za čuvanje

627
00:31:41,450 --> 00:31:43,085
Staza od najmanjih vrijednosti, zar ne?

628
00:31:43,085 --> 00:31:45,751
Se bilo tko želi mi dati
linija koda koji će to učiniti?

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

630
00:31:48,700 --> 00:31:53,570
Što nam je potrebno ako ćemo
da želite spremiti nešto?

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

632
00:31:55,047 --> 00:31:57,630
Možda bolje ime za koji
bi be-- "temp" potpuno works--

633
00:31:57,630 --> 00:32:00,655
možda više podesno zove biti,
ako želimo najmanji value--

634
00:32:00,655 --> 00:32:01,624
>> PUBLIKA: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: min, tamo idemo.

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

637
00:32:05,230 --> 00:32:08,340
I tako ovdje, što nam je činiti
želite inicijalizirati se?

638
00:32:08,340 --> 00:32:09,620
To je malo zeznuto.

639
00:32:09,620 --> 00:32:13,580
Zato odmah na
početkom ovog niza,

640
00:32:13,580 --> 00:32:15,730
nisi pogledao ništa, zar ne?

641
00:32:15,730 --> 00:32:19,200
Pa što, automatski, ako
mi smo samo na sam jednak 0,

642
00:32:19,200 --> 00:32:22,302
Što želimo inicijalizirati
naš prvi minimalna vrijednost?

643
00:32:22,302 --> 00:32:22,802
PUBLIKA: ja.

644
00:32:22,802 --> 00:32:24,790
ANDI PENG: ja, zapravo.

645
00:32:24,790 --> 00:32:27,040
Christabel, zašto želimo
da ga inicijalizirati na i?

646
00:32:27,040 --> 00:32:28,510
>> PUBLIKA: Jer, dobro,
smo počevši 0.

647
00:32:28,510 --> 00:32:31,660
Pa zato što nemam ništa za usporedbu
da, minimalna će završiti 0.

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

649
00:32:32,451 --> 00:32:34,400
Tako da je to točno.

650
00:32:34,400 --> 00:32:36,780
Budući da smo zapravo
pogledao ništa još,

651
00:32:36,780 --> 00:32:38,680
ne znamo što je naša minimalna vrijednost.

652
00:32:38,680 --> 00:32:41,960
Želimo samo ga inicijalizirati na
I, što, trenutno, nalazi upravo ovdje.

653
00:32:41,960 --> 00:32:44,750
I kao što smo i dalje
pomicati prema dolje taj niz,

654
00:32:44,750 --> 00:32:48,122
vidjet ćemo da je, sa svakim
Dodatni proći, ja koracima.

655
00:32:48,122 --> 00:32:49,830
I tako u tom trenutku,
Vjerojatno će

656
00:32:49,830 --> 00:32:52,329
da žele biti minimalna,
jer to će biti ono

657
00:32:52,329 --> 00:32:54,520
je početak nerazvrstani polja.

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

659
00:32:55,270 --> 00:32:58,720
>> Dakle, sada želimo dodati
for petlja ovdje to

660
00:32:58,720 --> 00:33:03,225
će ponoviti kroz
nesortirani ili ostatak ovog polja.

661
00:33:03,225 --> 00:33:05,808
Se bilo tko želi mi dati
linija koda koji će to učiniti?

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

663
00:33:08,870 --> 00:33:11,330
Hint-- što trebamo ovdje dolje?

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

665
00:33:17,320 --> 00:33:18,820
Što će ići ovo za petlje?

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

667
00:33:19,465 --> 00:33:21,590
PUBLIKA: Tako bismo želite
imaju različite cijeli broj,

668
00:33:21,590 --> 00:33:25,080
zato što smo trčanje kroz ostatak
od niza umjesto I, pa možda

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

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Da, j zvuči dobro za mene.

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

672
00:33:27,850 --> 00:33:33,930
>> PUBLIKA: Tako bi ja plus 1, jer je
ste počinju na sljedećem vrijednosti.

673
00:33:33,930 --> 00:33:40,395
A onda se na end-- Pa opet, j
manji od n minus 1, a zatim j ++.

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

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

676
00:33:48,510 --> 00:33:52,750
>> I onda ovdje, idemo želite
provjeriti da li se susreli naš uvjet,

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

678
00:33:53,250 --> 00:33:55,740
Jer želite
mijenjati minimalnu vrijednost

679
00:33:55,740 --> 00:33:58,700
ako je to zapravo manji nego što je
ste uspoređujući ga, zar ne?

680
00:33:58,700 --> 00:34:01,146
Pa što ćemo željeti ovdje?

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

682
00:34:04,160 --> 00:34:04,897
Provjerite vidjeti.

683
00:34:04,897 --> 00:34:06,730
Koja vrsta izjave
su mi vjerojatno ide

684
00:34:06,730 --> 00:34:08,389
TI želite koristiti ako
želite provjeriti nešto?

685
00:34:08,389 --> 00:34:09,360
>> PUBLIKA: An ako izjavi.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: if izjava.

687
00:34:10,485 --> 00:34:13,155
Dakle if-- i što će biti
uvjet da želimo unutar

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

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

690
00:34:18,255 --> 00:34:22,960
>> PUBLIKA: Ako je vrijednost j
manja od vrijednosti i--

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

692
00:34:24,600 --> 00:34:27,480
Dakle if-- tako da ovaj niz se naziva "polje".

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

694
00:34:27,980 --> 00:34:30,465
Dakle, ako array-- što je to?

695
00:34:30,465 --> 00:34:31,090
Reci to ponovo.

696
00:34:31,090 --> 00:34:39,590
>> PUBLIKA: Ako array-j je manje od
Niz-ja, onda bismo promijenili min.

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

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

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Da li to smisla?

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

701
00:34:48,670 --> 00:34:52,929
I sada ovdje, mi zapravo
želite provesti zamjenu, zar ne?

702
00:34:52,929 --> 00:34:58,285
Pa sjećam, u predavanju, da je David, kad je
je pokušavao the-- što je bilo zamijeniti

703
00:34:58,285 --> 00:34:59,996
it-- sok od naranče i milk--

704
00:34:59,996 --> 00:35:01,150
>> PUBLIKA: To je bruto.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Da, to je vrsta bruto.

706
00:35:02,816 --> 00:35:05,310
Ali to je bio prilično dobar
Koncept pokazujući put.

707
00:35:05,310 --> 00:35:08,430
Dakle, mislim da od svojih vrijednosti ovdje.

708
00:35:08,430 --> 00:35:10,794
Imate niz
od min, niz I.,

709
00:35:10,794 --> 00:35:12,460
ili što god su mi pokušavamo zamijeniti ovdje.

710
00:35:12,460 --> 00:35:15,310
A vjerojatno ne možete ih sipati u
jedni druge u isto vrijeme, zar ne?

711
00:35:15,310 --> 00:35:17,180
Dakle, što ćemo
da je potrebno stvoriti ovdje

712
00:35:17,180 --> 00:35:19,126
kako bi se mijenjati vrijednosti ispravno?

713
00:35:19,126 --> 00:35:19,820
>> PUBLIKA: Privremena promjenjiva.

714
00:35:19,820 --> 00:35:21,370
>> ANDI PENG: Privremena promjenjiva.

715
00:35:21,370 --> 00:35:22,570
Tako ćemo učiniti int temp.

716
00:35:22,570 --> 00:35:25,681
Vidi, to će biti bolje
Vrijeme to-- Hej, što je to?

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

718
00:35:26,180 --> 00:35:29,800
Dakle, to bi bio bolji
Vrijeme u ime varijablu "temp".

719
00:35:29,800 --> 00:35:30,730
Tako ćemo učiniti int temp.

720
00:35:30,730 --> 00:35:32,563
Što ćemo
postavljen temp jednaka do ovdje?

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

722
00:35:34,752 --> 00:35:35,335
PUBLIKA: Min?

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

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

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

726
00:35:43,110 --> 00:35:44,880
To zapravo nije bitno na kraju.

727
00:35:44,880 --> 00:35:47,690
Nije važno što
Kako bi se odlučite zamijeniti u

728
00:35:47,690 --> 00:35:50,862
dok god ste sigurni da ste
praćenje ono što zamjene.

729
00:35:50,862 --> 00:35:52,250
>> PUBLIKA: To bi mogao biti niz-ja.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Da, neka je učiniti array-i.

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

732
00:35:55,950 --> 00:35:59,305
I što onda je sljedeći redak
koda mi želimo imati ovdje?

733
00:35:59,305 --> 00:36:00,680
PUBLIKA: array-ja jednako array-j.

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

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: I na kraju?

736
00:36:08,070 --> 00:36:12,070
PUBLIKA: array-j jednak niz-ja.

737
00:36:12,070 --> 00:36:14,525
Publika: Ili niz-j jednaki
Niz-temp-- ili, temp.

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

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

740
00:36:19,430 --> 00:36:21,510
Tako ćemo pokrenuti ovo i vidjeti
ako će to raditi.

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

742
00:36:37,520 --> 00:36:39,335
Gdje se to događa?

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

744
00:36:40,210 --> 00:36:44,320
Vidi, na liniji 40, mi smo
pokušavate koristiti array-j?

745
00:36:44,320 --> 00:36:47,022
Ali gdje se j postoje samo u?

746
00:36:47,022 --> 00:36:48,402
>> PUBLIKA: U for petlji.

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

748
00:36:49,110 --> 00:36:51,730
Dakle, što ćemo morati učiniti?

749
00:36:51,730 --> 00:36:53,170
>> PUBLIKA: Definirajte ga van the--

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

751
00:36:57,777 --> 00:37:00,610
PUBLIKA: Da, mislim da imate
koristiti drugo, ako izjava, zar ne?

752
00:37:00,610 --> 00:37:05,230
Dakle kao što je, ako je minimum--
Sve je u redu, da razmislim.

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

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Dečki, pokušajte
pogledati Idemo

755
00:37:09,990 --> 00:37:11,270
vidjeti, što je nešto što možemo učiniti ovdje?

756
00:37:11,270 --> 00:37:11,811
>> PUBLIKA: U redu.

757
00:37:11,811 --> 00:37:15,900
Dakle, ako je minimalna nije jednak
j-- tako dalje, ako je minimalna je i--

758
00:37:15,900 --> 00:37:17,570
onda neće morati mijenjati.

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

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Da li to jednako ja?

761
00:37:24,712 --> 00:37:25,920
Što želiš reći ovdje?

762
00:37:25,920 --> 00:37:30,494
>> PUBLIKA: Ili da, ako je
Minimalna nije jednak ja, da.

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

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

765
00:37:40,210 --> 00:37:42,040
Pa to rješava, vrsta, naši problemi.

766
00:37:42,040 --> 00:37:47,265
Ali to još uvijek ne riješi
problem što će se dogoditi ako j-- jer j

767
00:37:47,265 --> 00:37:49,890
ne postoji izvan njega, što je
Što želimo učiniti s njom?

768
00:37:49,890 --> 00:37:50,698
Objavite ga van?

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

770
00:37:59,410 --> 00:38:02,730
Pokušajmo trčanje ovo.

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

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

773
00:38:06,200 --> 00:38:10,060
>> Kao što možete vidjeti na prvi pogled
Niz je imao te vrijednosti.

774
00:38:10,060 --> 00:38:14,800
I nakon toga bi trebao imati
je u 1, 2, 3, 4, 5, 6, 7, 8, 9.

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

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

777
00:38:16,030 --> 00:38:17,184
Što nam je činiti?

778
00:38:17,184 --> 00:38:17,850
PUBLIKA: Debug.

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

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: U redu, možemo pokušati.

781
00:38:23,370 --> 00:38:25,030
Možemo ispravljanje.

782
00:38:25,030 --> 00:38:26,042
Smanjivanje malo.

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

784
00:38:31,177 --> 00:38:33,656
Idemo postaviti našim Kontrolna točka.

785
00:38:33,656 --> 00:38:37,280
Idemo volimo-članovima OK.

786
00:38:37,280 --> 00:38:40,444
>> Pa zato što smo već znali da
ove linije, 15 do 22,

787
00:38:40,444 --> 00:38:43,610
su working-- jer sve što radim je
Samo iterating kroz i printing--

788
00:38:43,610 --> 00:38:45,406
Ja mogu ići naprijed i preskočiti to.

789
00:38:45,406 --> 00:38:47,280
Krenimo na liniji 25.

790
00:38:47,280 --> 00:38:48,712
OOP, neka mi dobili osloboditi od toga.

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

792
00:38:51,598 --> 00:38:54,057
>> PUBLIKA: Tako je prijelomna točka-a
gdje počinje ispravljanje pogrešaka?

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: ili zaustavlja.

794
00:38:54,890 --> 00:38:55,670
PUBLIKA: ili zaustavlja.

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

796
00:38:55,930 --> 00:38:58,640
Možete postaviti više kontrolne točke i
to samo može skočiti iz jednog u drugi.

797
00:38:58,640 --> 00:39:01,590
No, u ovom slučaju ne znamo
gdje je greška se događa.

798
00:39:01,590 --> 00:39:03,780
Dakle, mi samo želimo
početi od vrha prema dolje.

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

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

801
00:39:05,550 --> 00:39:08,460
>> Dakle, ovaj redak ovdje, možemo uskočiti.

802
00:39:08,460 --> 00:39:11,499
Možete vidjeti ovdje,
imamo niz.

803
00:39:11,499 --> 00:39:13,290
Oni su vrijednosti
da su u nizu.

804
00:39:13,290 --> 00:39:16,360
Vidiš da je, kako je indeks 0, to
odgovara value-- oh,

805
00:39:16,360 --> 00:39:17,526
Ja ću pokušati za uvećanje.

806
00:39:17,526 --> 00:39:20,650
Nažalost, to je stvarno teško
da see-- na indeks polja 0,

807
00:39:20,650 --> 00:39:24,090
imamo vrijednost 4 i
zatim slično i tako dalje.

808
00:39:24,090 --> 00:39:25,670
Mi imamo lokalne varijable.

809
00:39:25,670 --> 00:39:28,570
Sada sam je jednaka
0, što želimo da bude.

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

811
00:39:31,540 --> 00:39:33,690
>> I tako ćemo zadržati koračni kroz.

812
00:39:33,690 --> 00:39:36,850
Minimalnog jednak 0,
što želimo da bude.

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

814
00:39:39,470 --> 00:39:45,560
A onda ulazimo naš drugi za
petlje, ako je niz-j je manja od polja-i,

815
00:39:45,560 --> 00:39:46,380
koji nije.

816
00:39:46,380 --> 00:39:48,130
Pa jeste li vidjeli kako
da preskočili to?

817
00:39:48,130 --> 00:39:52,430
>> PUBLIKA: Dakle, treba li, ako
minimalna, sve that-- ne treba da

818
00:39:52,430 --> 00:39:55,424
biti u prva for petlja?

819
00:39:55,424 --> 00:39:57,340
ANDI PENG: Ne, jer
dalje želite testirati.

820
00:39:57,340 --> 00:40:00,329
Želite napraviti usporedbu sve
Vrijeme, čak i nakon što pokrenete kroz njega.

821
00:40:00,329 --> 00:40:02,620
Ne samo želite učiniti
na prvom prolaznih.

822
00:40:02,620 --> 00:40:05,240
Želiš to učiniti s
svaka dodatna opet proći.

823
00:40:05,240 --> 00:40:07,198
Dakle, želite da provjerite
vaše stanje unutra.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Dakle, mi samo ide na
držati trčanje ovuda.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Dat ću ti dečki savjet.

828
00:40:18,420 --> 00:40:23,910
To ima veze s činjenicom da kada
ste checking vaš uvjetno,

829
00:40:23,910 --> 00:40:26,600
niste provjeru
za ispravan indeksa.

830
00:40:26,600 --> 00:40:32,510
Dakle, sada ste provjere
niz indeks j manji od niza

831
00:40:32,510 --> 00:40:33,970
indeks i.

832
00:40:33,970 --> 00:40:36,580
No, ono što radiš gore na
Početkom za petlje?

833
00:40:36,580 --> 00:40:38,260
Niste li postavljanje j jednak I.?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Da, tako da možemo zapravo
zatvorili debugger ovdje.

836
00:40:45,415 --> 00:40:47,040
Tako ćemo pogledati našu pseudokod.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- ćemo
početi na sam jednak 0.

839
00:40:52,580 --> 00:40:54,760
Mi ćemo ići do n minus 1.

840
00:40:54,760 --> 00:40:58,040
Pogledajmo, nije mi imamo to pravo?

841
00:40:58,040 --> 00:40:59,580
Da, to je u redu.

842
00:40:59,580 --> 00:41:02,080
>> Pa onda iznutra ovdje smo
će stvoriti minimalnu vrijednost

843
00:41:02,080 --> 00:41:03,630
i postaviti to jednako i.

844
00:41:03,630 --> 00:41:04,950
Jesmo li to učiniti?

845
00:41:04,950 --> 00:41:06,270
Da, to učinio.

846
00:41:06,270 --> 00:41:10,430
Sada u našem unutarnjem za petlju, mi smo
učiniti j jednak ja se n 1 minus.

847
00:41:10,430 --> 00:41:11,950
Jesmo li to učiniti?

848
00:41:11,950 --> 00:41:15,540
Doista, mi to učinili.

849
00:41:15,540 --> 00:41:19,922
>> Pa ipak, što smo uspoređujući ovdje?

850
00:41:19,922 --> 00:41:20,925
>> PUBLIKA: j plus 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Točno.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
A onda idete da želite postaviti
Vaš minimalno jednak j plus 1, kao i.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Tako sam prošao kroz to jako brzo.

856
00:41:32,640 --> 00:41:36,190
Razumijem da li vi momci
zašto je j plus 1?

857
00:41:36,190 --> 00:41:36,890
U REDU.

858
00:41:36,890 --> 00:41:40,700
>> Dakle, u svom polju, u
Vaš prvi proći kroz,

859
00:41:40,700 --> 00:41:44,850
Vaš for petlji, za int
ja jednak 0, neka je samo

860
00:41:44,850 --> 00:41:46,740
Pretpostavljamo da je to još nije promijenio.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Imamo niz, u potpunosti,
samo četiri Nesortirani elemente, zar ne?

863
00:41:56,760 --> 00:42:00,760
Dakle, želimo inicijalizirati i jednaka 0.

864
00:42:00,760 --> 00:42:03,650
I ja se događa samo
prođite kroz ovaj petlje.

865
00:42:03,650 --> 00:42:08,560
I tako je u prvom prolazu, idemo
inicijalizirati varijablu pod nazivom "min"

866
00:42:08,560 --> 00:42:11,245
koji je također jednako ja, jer
nemamo minimalnu vrijednost.

867
00:42:11,245 --> 00:42:12,870
Tako da je sada jednaka 0, kao dobro.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
A onda ćemo proći.

870
00:42:17,640 --> 00:42:19,270
I želimo opet ponoviti.

871
00:42:19,270 --> 00:42:22,900
Sada kada smo otkrili što je naša minimalna
je, želimo ponoviti kroz

872
00:42:22,900 --> 00:42:25,190
opet vidjeti ako je usporedbom, zar ne?

873
00:42:25,190 --> 00:42:40,440
Tako j, ovdje će
na jednako i, što je 0.

874
00:42:40,440 --> 00:42:46,320
A onda, ako niz j plus ja, koji
je onaj koji je pored više, što je manje

875
00:42:46,320 --> 00:42:49,270
nego što vaš trenutni minimum
vrijednost, što želite mijenjati.

876
00:42:49,270 --> 00:42:56,850
>> Pa neka je samo reći da smo
nema, kao što je, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Upravo sada, ja je jednak
0 i j je jednak 0.

878
00:43:01,610 --> 00:43:05,210
I to je naša minimalna vrijednost.

879
00:43:05,210 --> 00:43:09,950
Ako array-j plus i-- pa ako jedan
to je poslije onog Gledamo

880
00:43:09,950 --> 00:43:13,450
je veća od one prije nje,
to će postati minimum.

881
00:43:13,450 --> 00:43:18,120
>> Dakle ovdje vidimo da 5
nije manja od toga.

882
00:43:18,120 --> 00:43:19,730
Dakle, to će ne biti 5.

883
00:43:19,730 --> 00:43:23,580
Vidimo da je 1 manje od 2, zar ne?

884
00:43:23,580 --> 00:43:32,970
Dakle, sada znamo da je naša minimalna je
će biti vrijednost indeksa na 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Da?

886
00:43:34,030 --> 00:43:39,170
I onda kada se ovdje,
možete mijenjati ispravne vrijednosti.

887
00:43:39,170 --> 00:43:42,610
>> Pa kad vi jednostavno su vlasništvo j
prije, ne gleda na jedan

888
00:43:42,610 --> 00:43:43,260
nakon njega.

889
00:43:43,260 --> 00:43:44,520
Gledate
istu vrijednost, što

890
00:43:44,520 --> 00:43:46,290
Zato jednostavno ne radi ništa.

891
00:43:46,290 --> 00:43:49,721
Znači li to da smisla svima,
Zato je potrebno da se plus 1 tamo?

892
00:43:49,721 --> 00:43:50,220
U REDU.

893
00:43:50,220 --> 00:43:53,345
Sada samo trčanje kroz to da bi
je li ostatak koda je ispravan.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Zašto se to događa?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, to je min ovdje.

898
00:44:16,364 --> 00:44:17,780
Mi smo bili uspoređujući pogrešnu vrijednost.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
O ne.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> O da, ovdje smo
zamjene pogrešne vrijednosti, kao dobro.

903
00:44:33,482 --> 00:44:34,940
Budući da smo bili u potrazi na i i j.

904
00:44:34,940 --> 00:44:36,440
To su oni bili smo provjeru.

905
00:44:36,440 --> 00:44:39,160
Mi zapravo žele mijenjati
minimalna, trenutna minimalna,

906
00:44:39,160 --> 00:44:40,550
s onim što ona vani.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
A što vi vidite dolje
Ovdje imamo sortirani niz.

909
00:45:05,402 --> 00:45:07,110
To jednostavno morali učiniti s
Činjenica da kada

910
00:45:07,110 --> 00:45:09,350
smo provjere
Vrijednosti su nas uspoređuju,

911
00:45:09,350 --> 00:45:11,226
nismo bili u potrazi na pravim vrijednostima.

912
00:45:11,226 --> 00:45:13,850
Tražili smo na istom jednom
Ovdje, zapravo ne zamjene.

913
00:45:13,850 --> 00:45:17,135
Morate pogledajte jedan pored
na njega i onda možete mijenjati.

914
00:45:17,135 --> 00:45:19,260
Dakle, to je ono što je vrsta
prislušni naš kod prije.

915
00:45:19,260 --> 00:45:22,460
I ono što sam učinio ovdje je sve
debugger može učiniti za vas

916
00:45:22,460 --> 00:45:23,810
Upravo sam to učinio na
odbora, zato što je lakše

917
00:45:23,810 --> 00:45:26,320
vidjeti nego pokušava
za povećavanje na ispravljanje pogrešaka.

918
00:45:26,320 --> 00:45:29,391
Znači li to da smisla svima?

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
>> U redu.

922
00:45:35,410 --> 00:45:41,070
Možemo prijeći na razgovor o
asimptotske zapis koji

923
00:45:41,070 --> 00:45:44,580
je samo fancy način rekavši
runtimes svih tih vrsta.

924
00:45:44,580 --> 00:45:47,650
Pa ja znam Davida, u predavanju,
dotakla trajanjima.

925
00:45:47,650 --> 00:45:52,124
I on je otišao kroz cijeli formuli
kako izračunati runtimes.

926
00:45:52,124 --> 00:45:53,040
Bez brige o tome.

927
00:45:53,040 --> 00:45:54,660
Ako ste stvarno znatiželjan
o tome kako se to radi,

928
00:45:54,660 --> 00:45:55,810
slobodno razgovarati sa mnom nakon dijelu.

929
00:45:55,810 --> 00:45:57,560
Možemo prošetati
Formule zajedno.

930
00:45:57,560 --> 00:46:00,689
No, svi ti dečki moraju stvarno
znam je da je n na kvadrat preko 2

931
00:46:00,689 --> 00:46:01,980
je ista stvar kao n na kvadrat.

932
00:46:01,980 --> 00:46:04,710
Budući da najveći broj,
eksponent, raste najviše.

933
00:46:04,710 --> 00:46:06,590
I tako za naše potrebe,
sve nam je stalo

934
00:46:06,590 --> 00:46:09,470
je da je div broj koji raste.

935
00:46:09,470 --> 00:46:13,340
>> Dakle, ono što je najbolje,
Runtime od odabira vrste?

936
00:46:13,340 --> 00:46:15,830
Ako ćeš imati
se ponoviti kroz popis

937
00:46:15,830 --> 00:46:18,712
a zatim ponoviti kroz
Ostatak tog popisa,

938
00:46:18,712 --> 00:46:20,420
koliko puta su
ćete vjerojatno,

939
00:46:20,420 --> 00:46:24,612
u najgorem case-- u
najboljem slučaju, sorry-- izvoditi kroz?

940
00:46:24,612 --> 00:46:27,070
Možda je bolje pitanje
pitati, što je najgori slučaj

941
00:46:27,070 --> 00:46:28,153
Runtime od odabira vrste.

942
00:46:28,153 --> 00:46:29,366
PUBLIKA: n na kvadrat.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: To je n na kvadrat, zar ne.

944
00:46:30,740 --> 00:46:36,986
Tako jednostavan način da mislite to je kao,
svaki put imate dva ugniježđena za petlje,

945
00:46:36,986 --> 00:46:38,110
to će biti n na kvadrat.

946
00:46:38,110 --> 00:46:40,386
Jer ne samo da su ti
prolazi kroz još jednom,

947
00:46:40,386 --> 00:46:42,260
morate se vratiti
oko i prođite kroz njega

948
00:46:42,260 --> 00:46:44,980
jednom u svakom vrijednosti.

949
00:46:44,980 --> 00:46:48,640
Dakle, u tom slučaju, vi radite n
puta n na kvadrat, koji is-- žao,

950
00:46:48,640 --> 00:46:50,505
n puta n, koja je jednaka n na kvadrat.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> A vrsta je i malo
jedinstvena u smislu

953
00:46:56,360 --> 00:46:59,774
da nije važno ako ti
vrijednosti su već u redu.

954
00:46:59,774 --> 00:47:01,440
I dalje će se izvoditi kroz ionako.

955
00:47:01,440 --> 00:47:03,872
Recimo samo da je to bio 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Bez obzira da li ili ne to je u
red, i dalje bi vodio kroz

957
00:47:07,080 --> 00:47:08,620
i još uvijek provjeriti minimalnu vrijednost.

958
00:47:08,620 --> 00:47:10,100
To bi napravio
Isti broj provjera

959
00:47:10,100 --> 00:47:12,780
svaki put, čak i ako je to
nije zapravo ništa dirati.

960
00:47:12,780 --> 00:47:16,940
>> Dakle, u takvom slučaju, najbolje i najgore
runtimes su zapravo ekvivalent.

961
00:47:16,940 --> 00:47:19,160
Dakle, očekivani izvođenja
od odabira vrste,

962
00:47:19,160 --> 00:47:23,790
koju odredi simbolom
od theta, theta, u ovom slučaju,

963
00:47:23,790 --> 00:47:24,790
Također bi se n na kvadrat.

964
00:47:24,790 --> 00:47:26,480
Sva tri od njih će se n na kvadrat.

965
00:47:26,480 --> 00:47:29,653
Jesu li svi jasno zašto
vrijeme izvođenja n na kvadrat?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> U redu.

968
00:47:33,980 --> 00:47:39,120
Dakle, Samo ću se brzo pokretanje
kroz ostatak vrstama.

969
00:47:39,120 --> 00:47:41,137
Algoritam za
mjehurić sort-- zapamtite,

970
00:47:41,137 --> 00:47:43,220
ovo je bio prvi
David prijeđe u predavanju.

971
00:47:43,220 --> 00:47:46,000
U osnovi, vi korak
cijeli popis

972
00:47:46,000 --> 00:47:48,950
a vi ste samo swap--
Usporedite dvije odjednom.

973
00:47:48,950 --> 00:47:51,350
A ako je veća,
nego ti samo ih zamijeniti.

974
00:47:51,350 --> 00:47:53,590
Dakle, ako su veća, što bi zamijeniti.

975
00:47:53,590 --> 00:47:56,180
Imam službeni ovdje.

976
00:47:56,180 --> 00:47:59,100
>> Pa neka je samo reći da je imao 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Ti bi usporediti 8 i 6.

978
00:48:00,571 --> 00:48:01,570
Ti bi ih morati zamijeniti.

979
00:48:01,570 --> 00:48:02,610
Ti bi usporediti 8 i 4.

980
00:48:02,610 --> 00:48:03,609
Ti bi ih morati zamijeniti.

981
00:48:03,609 --> 00:48:07,000
Ako morate mijenjati 8 i
2, promijenite ih kako je dobro.

982
00:48:07,000 --> 00:48:10,760
Tako je u tom smislu, što možete vidjeti,
igrao tijekom dugog vremenskog razdoblja,

983
00:48:10,760 --> 00:48:13,730
kako se vrijednosti vrsta mjehurić
krajevi, što je razlog zašto smo ga nazvati

984
00:48:13,730 --> 00:48:15,320
mjehurić vrsta.

985
00:48:15,320 --> 00:48:19,950
>> Mi bi samo pokrenuti kroz ponovno
naš drugi prolaz, a naš treći proći,

986
00:48:19,950 --> 00:48:21,150
i naš četvrti proći.

987
00:48:21,150 --> 00:48:25,820
U osnovi, Bubble sort samo radi
dok ne bi bilo više swap.

988
00:48:25,820 --> 00:48:31,109
Dakle, u tom smislu, ovo je samo
opći pseudokod za to.

989
00:48:31,109 --> 00:48:32,650
Bez brige, to će sve biti online.

990
00:48:32,650 --> 00:48:34,990
Mi ne moramo zapravo ići preko toga.

991
00:48:34,990 --> 00:48:38,134
>> Mi samo inicijalizirati brojača
varijabla koja počinje na 0.

992
00:48:38,134 --> 00:48:39,800
A mi ponoviti kroz cijeli niz.

993
00:48:39,800 --> 00:48:43,420
A ako jedna vrijednost is-- ako je to
vrijednost veća od te vrijednosti,

994
00:48:43,420 --> 00:48:44,610
ti ćeš ih zamijeniti.

995
00:48:44,610 --> 00:48:46,860
I onda si jednostavno
će zadržati ide.

996
00:48:46,860 --> 00:48:47,970
A ti ćeš brojati.

997
00:48:47,970 --> 00:48:50,845
A ti si samo ide da radi
to dok je brojač je veći

998
00:48:50,845 --> 00:48:53,345
od 0, što znači da je
svaki put morate zamijeniti,

999
00:48:53,345 --> 00:48:55,220
znate da želite ići
natrag i ponovno provjeriti.

1000
00:48:55,220 --> 00:48:59,510
Želite li zadržati provjere sve dok ne znate
da ne moram mijenjati više.

1001
00:48:59,510 --> 00:49:05,570
>> Dakle, što su najbolje i najgore
Slučaj trajanjima mjehurića vrste?

1002
00:49:05,570 --> 00:49:09,300
I hint-- to je zapravo drugačija
od odabira vrste u smislu

1003
00:49:09,300 --> 00:49:11,810
da ta dva odgovora nisu isti.

1004
00:49:11,810 --> 00:49:14,709
Razmislite o tome što će se dogoditi u
slučaj, ako je već riješeno.

1005
00:49:14,709 --> 00:49:16,500
I razmišljati o tome što
će se dogoditi ako je to

1006
00:49:16,500 --> 00:49:18,372
u slučaju kada nije riješeno.

1007
00:49:18,372 --> 00:49:20,580
A možete vrsta pokrenuti
kroz zašto to događa.

1008
00:49:20,580 --> 00:49:22,954
Dat ću ti dečki, kao što su, 30
sekunde razmišljati o tome.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> U REDU.

1011
00:49:53,540 --> 00:49:57,462
Se bilo tko imati pogodak na ono što je
najgori slučaj runtime od mjehurića vrste je?

1012
00:49:57,462 --> 00:49:57,962
Da.

1013
00:49:57,962 --> 00:50:07,810
>> PUBLIKA: Biste li se, poput, n puta
n minus 1 ili nešto slično?

1014
00:50:07,810 --> 00:50:10,650
Kao i svaki put radi,
to je samo, kao, jedna zamjena manje

1015
00:50:10,650 --> 00:50:10,960
da što god to bilo.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Da, tako
ti si potpuno u pravu.

1017
00:50:12,668 --> 00:50:15,940
A ovo je slučaj u kojem svoj
Odgovor je zapravo složenija

1018
00:50:15,940 --> 00:50:17,240
od onoga što je potrebno dati.

1019
00:50:17,240 --> 00:50:19,772
Dakle, to će run-- sam
će izbrisati sve ovo ovdje.

1020
00:50:19,772 --> 00:50:20,480
Jesu li svi dobro?

1021
00:50:20,480 --> 00:50:21,869
Mogu li izbrisati ovo?

1022
00:50:21,869 --> 00:50:22,368
U REDU.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Ti si idući u trčanje kroz n
puta prvi put, zar ne?

1025
00:50:30,320 --> 00:50:33,200
I oni će se izvoditi kroz
n minus 1 drugi put, zar ne?

1026
00:50:33,200 --> 00:50:37,130
A onda idete zadržati
ide, n moja 2, i tako dalje.

1027
00:50:37,130 --> 00:50:40,210
David je to učinio u predavanju, gdje je,
ako zbrojiti sve te vrijednosti,

1028
00:50:40,210 --> 00:50:48,080
dobivate nešto što je volimo-članovima yeah--
više od 2, što u biti samo smanjuje

1029
00:50:48,080 --> 00:50:49,784
do n na kvadrat.

1030
00:50:49,784 --> 00:50:51,700
Ti si idući u dobiti
čudno udio tamo.

1031
00:50:51,700 --> 00:50:53,892
I tako samo znam da
n kvadratna uvijek

1032
00:50:53,892 --> 00:50:55,350
ima prednost u odnosu na frakcije.

1033
00:50:55,350 --> 00:50:58,450
I tako, u ovom slučaju, najgore
runtime bi se n na kvadrat.

1034
00:50:58,450 --> 00:51:00,210
Ako je u silaznom
red, mislim, vi

1035
00:51:00,210 --> 00:51:02,530
napraviti swap svaki put.

1036
00:51:02,530 --> 00:51:05,170
>> Što bi, potencijalno,
najbolji slučaj izvođenja?

1037
00:51:05,170 --> 00:51:08,580
Recimo, ako je popis je već bio
kako bi, što bi runtime biti?

1038
00:51:08,580 --> 00:51:09,565
>> PUBLIKA: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: To je nje, točno.

1040
00:51:10,690 --> 00:51:11,600
A zašto je to nje?

1041
00:51:11,600 --> 00:51:13,850
PUBLIKA: jer ste upravo
moraju provjeriti na svaki jednom.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Točno.

1043
00:51:14,770 --> 00:51:17,150
Tako na najbolji mogući izvođenja,
ako je ovaj popis je već bio

1044
00:51:17,150 --> 00:51:20,270
sorted-- recimo 1, 2, 3, 4-- si
će samo proći kroz, što bi provjeriti,

1045
00:51:20,270 --> 00:51:21,720
vidjet ćete, oh, svi oni uspjeti.

1046
00:51:21,720 --> 00:51:22,636
Nisam za zamjenu.

1047
00:51:22,636 --> 00:51:23,370
Gotov sam.

1048
00:51:23,370 --> 00:51:26,500
Dakle, u tom slučaju, to je samo n
ili broj koraka koji ste upravo

1049
00:51:26,500 --> 00:51:29,870
morao provjeriti na prvom popisu.

1050
00:51:29,870 --> 00:51:33,990
>> A nakon toga, mi sada hit
umetanje vrsta, gdje

1051
00:51:33,990 --> 00:51:39,260
algoritam je bitno podijeliti
je u razvrstana i nerazvrstani dio.

1052
00:51:39,260 --> 00:51:42,810
A onda jedan po jedan,
su Nesortirani vrijednosti

1053
00:51:42,810 --> 00:51:46,880
umetnuta u njihovo primjereno
pozicije u početku liste.

1054
00:51:46,880 --> 00:51:52,120
>> Tako, na primjer, imamo
Popis 3, 5, 2, 6, 4 ponovo.

1055
00:51:52,120 --> 00:51:54,750
Mi znamo da je to trenutno
nesortirani jer smo upravo

1056
00:51:54,750 --> 00:51:57,030
počeo gledati u njega.

1057
00:51:57,030 --> 00:52:00,610
Mi pogledamo i znamo da je
prva vrijednost razvrstani, zar ne?

1058
00:52:00,610 --> 00:52:04,190
Ako ste samo gleda na niz
jedna veličina, znaš da je to riješeno.

1059
00:52:04,190 --> 00:52:08,230
>> Dakle, onda znamo da je
ostala četiri su Nesortirano.

1060
00:52:08,230 --> 00:52:10,980
Idemo kroz i vidimo tu vrijednost.

1061
00:52:10,980 --> 00:52:11,730
Vratimo.

1062
00:52:11,730 --> 00:52:13,130
Vidiš onu vrijednost 5?

1063
00:52:13,130 --> 00:52:14,110
Mi se na to gledate.

1064
00:52:14,110 --> 00:52:15,204
Mi to usporediti s 3.

1065
00:52:15,204 --> 00:52:17,870
Znamo da je veći od
3, tako da smo znali da je to riješeno.

1066
00:52:17,870 --> 00:52:22,940
Dakle, sada znamo da su prve dvije
su razvrstani a zadnje tri nisu.

1067
00:52:22,940 --> 00:52:24,270
>> Mi pogledamo 2.

1068
00:52:24,270 --> 00:52:25,720
Prvo smo to provjeriti s 5.

1069
00:52:25,720 --> 00:52:26,700
Je li to manje od 5?

1070
00:52:26,700 --> 00:52:27,240
Nije.

1071
00:52:27,240 --> 00:52:29,510
Dakle, moramo držati obličje dolje.

1072
00:52:29,510 --> 00:52:30,940
Zatim provjerite 2 gola 3.

1073
00:52:30,940 --> 00:52:31,850
Je li to manje od?

1074
00:52:31,850 --> 00:52:32,350
Ne.

1075
00:52:32,350 --> 00:52:35,430
Pa znate 2 mora biti umetnuta
sprijeda i 3 i 5

1076
00:52:35,430 --> 00:52:38,200
oba moraju biti gurnula van.

1077
00:52:38,200 --> 00:52:42,190
Učinite to opet sa 6 i 4.

1078
00:52:42,190 --> 00:52:48,962
A mi samo držati ček u biti,
gdje smo samo provjeriti, ček, ček.

1079
00:52:48,962 --> 00:52:51,170
I dok je u pravu
Položaj smo vrsta samo

1080
00:52:51,170 --> 00:52:54,890
umetnite ga u pravom položaju,
što je, gdje ime je došao iz.

1081
00:52:54,890 --> 00:52:59,830
>> Dakle, to je samo algoritam,
pseudokod po sebi, vrsta,

1082
00:52:59,830 --> 00:53:04,990
kako bismo provesti
umetanje vrsta.

1083
00:53:04,990 --> 00:53:05,954
Pseudokod je ovdje.

1084
00:53:05,954 --> 00:53:06,620
To je sve na internetu.

1085
00:53:06,620 --> 00:53:10,720
Bez brige, ako ti dečki su
pokušavaju kopirati ovaj dolje.

1086
00:53:10,720 --> 00:53:14,500
Dakle, još jednom, ista question-- ono
bilo bi najbolje i najgore runtimes

1087
00:53:14,500 --> 00:53:16,120
za umetanje vrste?

1088
00:53:16,120 --> 00:53:17,750
To je vrlo slično na posljednje pitanje.

1089
00:53:17,750 --> 00:53:20,479
Dat ću ti dečki, kao što su, 30
sekunde razmišljati o tome što je dobro.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK bilo tko želi
daj mi najgori runtime?

1092
00:53:50,071 --> 00:53:50,570
Da.

1093
00:53:50,570 --> 00:53:51,490
>> PUBLIKA: n na kvadrat.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI PENG: To je n na kvadrat.

1095
00:53:52,573 --> 00:53:53,730
I zašto je n kvadrat?

1096
00:53:53,730 --> 00:53:57,562
>> PUBLIKA: Budući da u
obrnutom redoslijedu, imate

1097
00:53:57,562 --> 00:54:02,619
proći kroz n puta n, koji is--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Da, točno.

1099
00:54:03,660 --> 00:54:06,610
Dakle ista stvar kao u balonu vrste.

1100
00:54:06,610 --> 00:54:08,720
Ako ovaj popis u
silaznom redoslijedu, ti si

1101
00:54:08,720 --> 00:54:11,240
morati provjeriti prvi puta.

1102
00:54:11,240 --> 00:54:13,470
I onda sa svakim
dodatna vrijednost, ti si

1103
00:54:13,470 --> 00:54:16,390
morati provjeriti protiv
svaki vrijednosti, zar ne?

1104
00:54:16,390 --> 00:54:20,290
I tako zajedno, ti si idući u izraditi
N proći vremena još n prođe, što

1105
00:54:20,290 --> 00:54:21,750
je n kvadrat.

1106
00:54:21,750 --> 00:54:22,860
Što o najboljem slučaju?

1107
00:54:22,860 --> 00:54:24,360
Da.

1108
00:54:24,360 --> 00:54:28,840
>> PUBLIKA: n minus 1, jer je
Prvi je već na kvadrat.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Dakle, u neposrednoj blizini.

1110
00:54:30,270 --> 00:54:31,850
Odgovor je zapravo nje.

1111
00:54:31,850 --> 00:54:37,189
Jer dok se prvi je
razvrstani, ne može ga actually--

1112
00:54:37,189 --> 00:54:38,980
samo smo sreće, u
to primjer, da 2

1113
00:54:38,980 --> 00:54:40,930
dogodilo se da je najmanji broj.

1114
00:54:40,930 --> 00:54:43,680
Ali to neće uvijek biti slučaj.

1115
00:54:43,680 --> 00:54:48,040
Ako 2 već razvrstani u početku
ali izgleda i tu je 1 ovdje

1116
00:54:48,040 --> 00:54:49,144
U 1. će ga čekić.

1117
00:54:49,144 --> 00:54:51,060
A to će završiti
gore bitak nabasao ionako.

1118
00:54:51,060 --> 00:54:56,250
>> Dakle, u najboljem slučaju,
to je zapravo samo će biti n.

1119
00:54:56,250 --> 00:54:59,090
Ako imate 1, 2, 3,
4, 5, 6, 7, 8, ti si

1120
00:54:59,090 --> 00:55:00,940
će se izvoditi kroz
da cijeli popis odjednom

1121
00:55:00,940 --> 00:55:03,430
provjeriti da li je sve u redu.

1122
00:55:03,430 --> 00:55:07,390
Jesu li svi jasno na trčanje
Vremena izbor isto kao i?

1123
00:55:07,390 --> 00:55:09,960
Znam da ću kroz
to jako brzo.

1124
00:55:09,960 --> 00:55:13,330
Ali samo znam da ako znate
opći pojmovi, te bi trebao biti dobar.

1125
00:55:13,330 --> 00:55:16,070
U REDU.

1126
00:55:16,070 --> 00:55:19,790
Pa ja samo ću ti dečki možda, kao što je,
minutu da razgovaraju sa svojim susjedima

1127
00:55:19,790 --> 00:55:21,890
o tome što su samo neki
od glavnih razlika

1128
00:55:21,890 --> 00:55:23,540
između ovih tipova sorti.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Mi ćemo ići preko uskoro.

1131
00:56:25,570 --> 00:56:26,444
PUBLIKA: Oh, u redu.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Da.

1133
00:56:27,320 --> 00:56:28,380
U REDU.

1134
00:56:28,380 --> 00:56:33,420
Cool, neka je ponovno sastati kao klasa.

1135
00:56:33,420 --> 00:56:34,330
U REDU.

1136
00:56:34,330 --> 00:56:37,579
Dakle, to je neka vrsta
otvoreni pitanje u smislu

1137
00:56:37,579 --> 00:56:39,120
da ima puno odgovora na njih.

1138
00:56:39,120 --> 00:56:40,746
A mi ćemo ići preko neke od njih nakratko.

1139
00:56:40,746 --> 00:56:43,411
Samo sam htjela da ti dečki
razmišljam o tome što diferencira

1140
00:56:43,411 --> 00:56:44,530
Sve tri vrste sorti.

1141
00:56:44,530 --> 00:56:47,440
I ja sam čuo, također, velika
question-- što se spajaju vrsta učiniti?

1142
00:56:47,440 --> 00:56:50,110
Veliko pitanje, jer je to
ono što smo pokrivaju sljedeća.

1143
00:56:50,110 --> 00:56:52,850
>> Dakle spojiti vrsta je
jedna vrsta koja funkcionira

1144
00:56:52,850 --> 00:56:56,100
vrlo različito od ostalih vrsta.

1145
00:56:56,100 --> 00:56:58,180
Kako vi možete see--
David učinio da demo

1146
00:56:58,180 --> 00:57:01,130
gdje je imao sve svjež
zvukovi vidim kako spojiti

1147
00:57:01,130 --> 00:57:04,010
vrsta ran, kao, beskonačno
brže od druge dvije vrste?

1148
00:57:04,010 --> 00:57:04,510
U REDU.

1149
00:57:04,510 --> 00:57:07,580
Dakle, to je zato spajanje
sortirati provodi tu podjelu

1150
00:57:07,580 --> 00:57:11,020
i osvojiti koncept da smo
govorio o puno u predavanju.

1151
00:57:11,020 --> 00:57:14,550
U tom smislu da smo htjeli raditi
pametnije, a ne teže, kada podijelimo

1152
00:57:14,550 --> 00:57:18,120
i osvojiti probleme, te ih razbiti
prema dolje, a zatim ih staviti zajedno,

1153
00:57:18,120 --> 00:57:19,930
dobre stvari uvijek događaju.

1154
00:57:19,930 --> 00:57:21,960
>> Tako je način na koji se spajaju
sortirati suštini radi

1155
00:57:21,960 --> 00:57:24,660
je da dijeli
nesortirani niz na pola.

1156
00:57:24,660 --> 00:57:26,500
A onda je dobio dvije polovice polja.

1157
00:57:26,500 --> 00:57:28,220
I to samo sortira te dvije polovice.

1158
00:57:28,220 --> 00:57:31,750
To samo čuva podjele na pola, u
pola, na pola dok je sve sortirano

1159
00:57:31,750 --> 00:57:33,680
a onda rekurzivno
stavlja sve to zajedno.

1160
00:57:33,680 --> 00:57:36,550
>> Tako da je stvarno sažetak.

1161
00:57:36,550 --> 00:57:38,750
Dakle, ovo je samo malo pseudokod.

1162
00:57:38,750 --> 00:57:41,040
Znači li to da smisla u
način na koji je pokrenut?

1163
00:57:41,040 --> 00:57:43,870
Pa neka je samo reći imate
niz od n elemenata, zar ne?

1164
00:57:43,870 --> 00:57:45,450
Ako je n manji od 2, možete se vratiti.

1165
00:57:45,450 --> 00:57:49,040
Zato što znam da ako postoji
samo jedna stvar, to mora biti riješeno.

1166
00:57:49,040 --> 00:57:52,600
Inače, možete sortirati lijevu polovicu,
i onda sortirati desnu polovicu,

1167
00:57:52,600 --> 00:57:54,140
i onda spojiti.

1168
00:57:54,140 --> 00:57:56,979
>> Dakle, dok je izgleda stvarno lako,
u stvarnosti, razmišljam o tome je

1169
00:57:56,979 --> 00:58:00,270
vrsta teško. Jer ti si kao,
Pa, to je vrsta radi na sebi.

1170
00:58:00,270 --> 00:58:00,769
Pravo?

1171
00:58:00,769 --> 00:58:02,430
To je trčanje po sebi.

1172
00:58:02,430 --> 00:58:05,479
Dakle, u tom smislu, David dotaknu
nakon rekurzije u klasi.

1173
00:58:05,479 --> 00:58:07,270
I to je koncept
ćemo govoriti o više.

1174
00:58:07,270 --> 00:58:11,430
To je da je ovaj, ove dvije linije
Ovdje, zapravo je samo program

1175
00:58:11,430 --> 00:58:13,860
to govori da se izvoditi
s različitim ulazom.

1176
00:58:13,860 --> 00:58:17,230
Dakle, umjesto da se izvoditi u
cjelokupnost n elemenata,

1177
00:58:17,230 --> 00:58:20,530
možete ga razbiti dolje u
lijeva polovica, a pravo pola

1178
00:58:20,530 --> 00:58:22,680
a zatim ga ponovno pokrenuti.

1179
00:58:22,680 --> 00:58:26,050
>> A onda ćemo gledati na to vizualno,
jer sam vizualni učenik.

1180
00:58:26,050 --> 00:58:27,270
To radi bolje za mene.

1181
00:58:27,270 --> 00:58:29,890
Tako ćemo pogledati vizualnom primjer ovdje.

1182
00:58:29,890 --> 00:58:36,237
>> Recimo imamo niz, šest
Elementi, 3, 5, 2, 6, 4, 1, nije riješeno.

1183
00:58:36,237 --> 00:58:37,820
U redu, tu je mnogo na ovoj stranici.

1184
00:58:37,820 --> 00:58:43,179
Dakle, ako vi možete pogledati na
Prvi korak ovdje, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
možete ga podijeliti na pola.

1186
00:58:44,220 --> 00:58:45,976
Imate 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Vi znate da oni vas aren't--
ne znam ako su razvrstani ili ne,

1188
00:58:48,850 --> 00:58:52,517
tako da bi ih se razbije, na pola,
na pola, na pola, sve dok na kraju,

1189
00:58:52,517 --> 00:58:53,600
imate samo jedan element.

1190
00:58:53,600 --> 00:58:56,790
I jedan element uvijek razvrstani, zar ne?

1191
00:58:56,790 --> 00:59:01,560
>> Tako znamo da je 3, 5, 2, 4, 6,
1, po sebi, su razvrstani.

1192
00:59:01,560 --> 00:59:05,870
I sada možemo ih staviti natrag zajedno.

1193
00:59:05,870 --> 00:59:07,510
Dakle, mi znamo 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Mi smo stavili one zajedno.

1195
00:59:08,510 --> 00:59:09,617
Mi znamo da je to riješeno.

1196
00:59:09,617 --> 00:59:10,450
Na 2 je još tamo.

1197
00:59:10,450 --> 00:59:11,830
Možemo staviti 4 i 6 zajedno.

1198
00:59:11,830 --> 00:59:13,996
Znamo da je to riješeno,
pa smo stavili zajedno.

1199
00:59:13,996 --> 00:59:14,940
A 1 je tu.

1200
00:59:14,940 --> 00:59:18,720
>> I onda samo pogledajte
ove dvije polovice ovdje.

1201
00:59:18,720 --> 00:59:21,300
Imate 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Vi samo možete usporediti
početak svega.

1203
00:59:23,465 --> 00:59:26,340
Zato što znam da je to razvrstani
a vi znate da je to riješeno.

1204
00:59:26,340 --> 00:59:29,360
Pa onda ne morate
usporediti 5, samo usporediti 3.

1205
00:59:29,360 --> 00:59:32,070
A 2 je manje od 3, tako da
znate 2 mora ići na kraju.

1206
00:59:32,070 --> 00:59:33,120
>> Ista stvar tamo.

1207
00:59:33,120 --> 00:59:34,740
U 1. mora ići ovdje.

1208
00:59:34,740 --> 00:59:37,330
I onda kad idete staviti
te dvije vrijednosti zajedno,

1209
00:59:37,330 --> 00:59:39,950
znate da je to razvrstani i
znate da je to riješeno.

1210
00:59:39,950 --> 00:59:43,240
Pa onda 1 i
2 je 1 manja od 2.

1211
00:59:43,240 --> 00:59:45,570
To vam govori da je 1
treba ići na kraju ovog

1212
00:59:45,570 --> 00:59:47,480
čak i bez gledanja na 3 ili 5.

1213
00:59:47,480 --> 00:59:50,100
A onda je 4, možete jednostavno
ček, to ide ovdje.

1214
00:59:50,100 --> 00:59:51,480
Ne morate gledati na 5.

1215
00:59:51,480 --> 00:59:52,570
Ista stvar sa 6.

1216
00:59:52,570 --> 00:59:55,860
Znaš da je to samo 6--
ne treba pogledao.

1217
00:59:55,860 --> 00:59:57,870
>> I tako na taj način, ti si
Samo se štedi

1218
00:59:57,870 --> 00:59:59,526
puno koraka kada se uspoređuju.

1219
00:59:59,526 --> 01:00:02,150
Ne morate usporediti svaku
Element protiv drugih elemenata.

1220
01:00:02,150 --> 01:00:05,230
Vi samo usporediti protiv onih
što vam je potrebno da ga usporediti protiv.

1221
01:00:05,230 --> 01:00:06,870
Dakle, to je vrsta apstraktnog koncepta.

1222
01:00:06,870 --> 01:00:10,540
Bez brige, ako to nije
dosta vas udarajući još u pravu.

1223
01:00:10,540 --> 01:00:14,740
Ali općenito, to je
kako spajanje vrsta radova.

1224
01:00:14,740 --> 01:00:17,750
Pitanja, kratkih pitanja,
prije nego što sam krenuti dalje?

1225
01:00:17,750 --> 01:00:18,550
Da.

1226
01:00:18,550 --> 01:00:22,230
>> PUBLIKA: Pa rekli ste da uzmete
U 1., a zatim 4, i 6

1227
01:00:22,230 --> 01:00:23,860
i stavio ih u.

1228
01:00:23,860 --> 01:00:26,800
Pa nisu those-- nisu
gledaš ih

1229
01:00:26,800 --> 01:00:28,544
kao zasebne elemente, a ne kao cjelinu?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Da.

1231
01:00:29,210 --> 01:00:32,020
Dakle, što se događa
je da u osnovi

1232
01:00:32,020 --> 01:00:33,650
stvaraju potpuno novi niz.

1233
01:00:33,650 --> 01:00:36,690
Tako da znate da, ovdje sam
dva polja od veličine 3, zar ne?

1234
01:00:36,690 --> 01:00:39,600
Pa znaš da je moj sortirati niz
treba imati šest elemenata.

1235
01:00:39,600 --> 01:00:42,270
Dakle, vi samo stvoriti
Nova količina memorije.

1236
01:00:42,270 --> 01:00:44,270
Dakle, ti si nešto kao
biti rasipan memorije,

1237
01:00:44,270 --> 01:00:46,186
ali to nije važno
zato što je tako mali.

1238
01:00:46,186 --> 01:00:48,590
Tako da pogledajte 1
a vi pogledajte 2.

1239
01:00:48,590 --> 01:00:50,770
I znate da je 1 manje od 2.

1240
01:00:50,770 --> 01:00:53,840
Pa znaš da je 1 bi trebao ići u
početak svima.

1241
01:00:53,840 --> 01:00:55,850
>> Ne morate čak ni
pogledajte 3 i 5.

1242
01:00:55,850 --> 01:00:57,400
Pa znate 1 ide tamo.

1243
01:00:57,400 --> 01:00:59,300
Onda ti zapravo odsjeći na 1.

1244
01:00:59,300 --> 01:01:00,370
To je, kao što je, mrtav za nas.

1245
01:01:00,370 --> 01:01:03,690
Onda imamo samo 2,
3, 5, i 6, a zatim 4.

1246
01:01:03,690 --> 01:01:06,270
A onda znate da, vas
usporediti 4 i 2,

1247
01:01:06,270 --> 01:01:07,560
oh, 2 bi trebao ići tamo.

1248
01:01:07,560 --> 01:01:09,685
Znači li pasti na 2 dolje, možete ga odsjeći.

1249
01:01:09,685 --> 01:01:12,060
Pa onda samo imaju 3
i 5 u 4 i 6.

1250
01:01:12,060 --> 01:01:14,650
A ti samo nastavi ga sjeckanje off
dok ih stavite u nizu.

1251
01:01:14,650 --> 01:01:17,110
>> PUBLIKA: Znači ti si samo uvijek
Uspoređujući [nečujan]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Točno.

1253
01:01:17,710 --> 01:01:19,590
Dakle, u tom smislu, da ste
Samo usporedbom, u biti,

1254
01:01:19,590 --> 01:01:21,240
jedan broj u odnosu na drugi broj.

1255
01:01:21,240 --> 01:01:22,990
A budući da znate
da je to riješeno, te

1256
01:01:22,990 --> 01:01:24,350
ne moraju gledati kroz
svi brojevi.

1257
01:01:24,350 --> 01:01:25,870
Vi samo morati gledati na prvom.

1258
01:01:25,870 --> 01:01:27,582
I onda možete jednostavno pasti
ih dolje, jer znate

1259
01:01:27,582 --> 01:01:29,640
oni pripadaju, gdje im je potrebno da pripadaju.

1260
01:01:29,640 --> 01:01:31,030
Da.

1261
01:01:31,030 --> 01:01:32,920
Dobro pitanje.

1262
01:01:32,920 --> 01:01:35,290
>> A onda, ako bilo koji od vas
su malo ambiciozan,

1263
01:01:35,290 --> 01:01:38,660
slobodno pogledajte ovaj kod.

1264
01:01:38,660 --> 01:01:40,680
To je zapravo
fizička implementacija

1265
01:01:40,680 --> 01:01:42,150
kako bismo pisati pisma vrsta.

1266
01:01:42,150 --> 01:01:44,070
A što možete vidjeti, to je vrlo kratko.

1267
01:01:44,070 --> 01:01:46,310
Ali ideje iza
to su prilično složena.

1268
01:01:46,310 --> 01:01:50,865
Dakle, ako se osjećate kao crtež ovo
u zadaću večeras, slobodno.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> U REDU.

1271
01:01:54,740 --> 01:01:58,070
Tako David prijeđe ovo predavanje.

1272
01:01:58,070 --> 01:02:00,660
Koji su najbolji slučaj
runtimes, najgori slučaj runtimes,

1273
01:02:00,660 --> 01:02:05,680
a očekivani runtimes udruživanja vrste?

1274
01:02:05,680 --> 01:02:07,260
Nekoliko sekundi razmišljati.

1275
01:02:07,260 --> 01:02:11,198
To je prilično teško, ali nekako
intuitivno, ako mislite o tome.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
U redu.

1278
01:02:23,054 --> 01:02:25,269
>> PUBLIKA: Je najgori slučaj n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Točno.

1280
01:02:26,060 --> 01:02:29,380
A zašto je to n log n.

1281
01:02:29,380 --> 01:02:32,230
>> PUBLIKA: Nije li to zato što
postaje eksponencijalno brže,

1282
01:02:32,230 --> 01:02:35,390
pa to je kao funkcija koje
umjesto da jednostavno se n

1283
01:02:35,390 --> 01:02:37,529
kvadrat ili nešto?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Točno.

1285
01:02:38,320 --> 01:02:40,750
Dakle, razlog zašto je
runtime na to n log

1286
01:02:40,750 --> 01:02:44,310
n because-- što ste vi
radi u svim ovim koracima?

1287
01:02:44,310 --> 01:02:46,190
Ti si samo cijepanje na pola, zar ne?

1288
01:02:46,190 --> 01:02:48,750
I tako, kada činimo
prijavite, sve što to radiš

1289
01:02:48,750 --> 01:02:53,150
se dijeljenjem problem na pola,
na pola, na pola, na više polovice.

1290
01:02:53,150 --> 01:02:56,430
I u tom smislu, možete vrsta
od eliminirati linearnog modela

1291
01:02:56,430 --> 01:02:57,510
koje smo koristili.

1292
01:02:57,510 --> 01:03:00,254
Jer kada nasjeckajte
stvari u poluvremenu, to je zapisnik.

1293
01:03:00,254 --> 01:03:02,420
To je samo matematički
način ga zastupa.

1294
01:03:02,420 --> 01:03:06,310
>> I onda na kraju, na kraju, ti si
samo što još jednu loptu kroz

1295
01:03:06,310 --> 01:03:07,930
staviti ih sve u redu, zar ne?

1296
01:03:07,930 --> 01:03:10,330
I tako, ako je samo da
provjeriti jednu stvar, to je nje.

1297
01:03:10,330 --> 01:03:13,420
I tako ste vrsta
množenjem dva zajedno.

1298
01:03:13,420 --> 01:03:17,660
Dakle, to je kao da ste je dobio da konačna
provjerite n ovdje sa log n

1299
01:03:17,660 --> 01:03:18,390
ovdje.

1300
01:03:18,390 --> 01:03:21,060
A ako pomnožite
ih, što je n log n.

1301
01:03:21,060 --> 01:03:26,100
>> I tako, najbolje i najgore
Slučaj i očekuje se svi n log n.

1302
01:03:26,100 --> 01:03:27,943
To je također kao drugoj vrsti.

1303
01:03:27,943 --> 01:03:30,090
To je kao izbor vrste
u smislu da

1304
01:03:30,090 --> 01:03:32,131
ne smeta što je vaš
Popis je, to samo ide

1305
01:03:32,131 --> 01:03:34,801
kako napraviti istu stvar svaki put.

1306
01:03:34,801 --> 01:03:35,300
U REDU.

1307
01:03:35,300 --> 01:03:39,950
Dakle, kao što vi vidite, iako
su vrste koje smo prošli through-- n

1308
01:03:39,950 --> 01:03:41,660
kvadrat, nije učinkovit.

1309
01:03:41,660 --> 01:03:47,060
Pa čak i to n log n
Ne najučinkovitiji.

1310
01:03:47,060 --> 01:03:49,720
Ako ti dečki su znatiželjni,
postoji sortirati mehanizmi

1311
01:03:49,720 --> 01:03:54,310
koji su toliko učinkovita da su oni
gotovo suštini stan u runtime.

1312
01:03:54,310 --> 01:03:55,420
>> Imaš neki dnevnik n-a.

1313
01:03:55,420 --> 01:03:58,190
Imaš neki log log n-a.

1314
01:03:58,190 --> 01:04:00,330
Mi ne dirati po njima
u ovoj klasi upravo sada.

1315
01:04:00,330 --> 01:04:02,663
Ali, ako ti dečki su znatiželjni,
slobodno google, što je

1316
01:04:02,663 --> 01:04:04,392
Najučinkovitiji mehanizmi sortiranje.

1317
01:04:04,392 --> 01:04:06,350
Ne znam, postoje
neke one stvarno smiješno,

1318
01:04:06,350 --> 01:04:09,860
volimo-članovima ima nekih stvarno
smiješne one koje ljudi čine.

1319
01:04:09,860 --> 01:04:12,210
A vi se pitate kako
ikada razmišljali o tome.

1320
01:04:12,210 --> 01:04:15,730
Dakle google, ako imate neki rezervni
vrijeme, na što su neke smiješne načine

1321
01:04:15,730 --> 01:04:17,730
da people-- kao
učinkovite svatko od ljudi

1322
01:04:17,730 --> 01:04:20,371
bili u mogućnosti provesti vrste.

1323
01:04:20,371 --> 01:04:20,870
U REDU.

1324
01:04:20,870 --> 01:04:22,880
I ovdje je samo zgodan mali grafikon.

1325
01:04:22,880 --> 01:04:26,850
Znam sve vas, prije tog kviza 0,
će biti u vašoj sobi, vjerojatno pokušavajući

1326
01:04:26,850 --> 01:04:27,960
zapamtiti da.

1327
01:04:27,960 --> 01:04:30,940
Tako da je lijepo tamo za vas momci.

1328
01:04:30,940 --> 01:04:37,120
Samo ne zaboravite logiku da made--
zašto ti brojevi su događaju.

1329
01:04:37,120 --> 01:04:39,870
Ako ste uvijek gubi, samo bi
sigurni da znate što vrste su.

1330
01:04:39,870 --> 01:04:40,820
A možete pokrenuti preko
ih u svom umu

1331
01:04:40,820 --> 01:04:42,903
shvatiti zašto oni
odgovori su ti odgovori.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> U redu.

1334
01:04:47,600 --> 01:04:49,680
Tako ćemo premjestiti
na kraju, na traženje.

1335
01:04:49,680 --> 01:04:51,638
Jer kao što je one od vas
koji su pročitali pset,

1336
01:04:51,638 --> 01:04:55,175
Pretraživanje je također dio
ovotjedni Problem postavlja.

1337
01:04:55,175 --> 01:04:57,300
Vi ćete biti zatraženo da provede
dvije vrste pretraživanja.

1338
01:04:57,300 --> 01:05:00,070
Jedan je linearni pretraživanje i
jedan je binarno traženje.

1339
01:05:00,070 --> 01:05:01,760
>> Tako je linearna pretraživanje je prilično jednostavan.

1340
01:05:01,760 --> 01:05:04,070
Vi samo želite potražiti elementa
popisa vidjeti ako ste ga dobili.

1341
01:05:04,070 --> 01:05:05,444
Vi samo morati ponoviti kroz.

1342
01:05:05,444 --> 01:05:08,170
A ako je jednak nešto,
možete jednostavno vratiti, zar ne?

1343
01:05:08,170 --> 01:05:10,890
Ali onaj koji smo najviše
zainteresirani za razgovor o

1344
01:05:10,890 --> 01:05:14,550
je binarno pretraživanje, pravo, koje je
podijeli pa vladaj mehanizam koji

1345
01:05:14,550 --> 01:05:18,190
David pokazujući na predavanju.

1346
01:05:18,190 --> 01:05:20,810
>> Zapamti imeniku primjer
da je stalno odgoja,

1347
01:05:20,810 --> 01:05:23,960
onaj koji je vrsta borili
malo o ovoj protekloj godini,

1348
01:05:23,960 --> 01:05:27,530
gdje ste podijeliti problem na pola,
na pola, na pola, opet i opet,

1349
01:05:27,530 --> 01:05:30,730
dok ne pronađete ono što tražite?

1350
01:05:30,730 --> 01:05:33,727
A ti si dobio
Runtime to kao dobro.

1351
01:05:33,727 --> 01:05:35,810
A što možete vidjeti, to je
značajno učinkovitije

1352
01:05:35,810 --> 01:05:39,080
od bilo koje druge vrste pretraživanja.

1353
01:05:39,080 --> 01:05:41,880
>> Dakle, način na koji bismo otići o
provedbi binarnu pretragu

1354
01:05:41,880 --> 01:05:46,510
je, ako smo imali niz,
indeks 0 do 6, sedam elemenata

1355
01:05:46,510 --> 01:05:49,790
možemo gledati u sredini, redu-
ispričavam se, ako je naše pitanje first--

1356
01:05:49,790 --> 01:05:53,840
ako želimo postaviti pitanje, ne
Niz sadrži element 7,

1357
01:05:53,840 --> 01:05:56,840
Očito, kao ljudi, i da
tako mala polje, to je lako za nas

1358
01:05:56,840 --> 01:05:58,210
reći da.

1359
01:05:58,210 --> 01:06:05,750
No, način provedbe binarnu
Traženje bi gledati u sredini.

1360
01:06:05,750 --> 01:06:08,020
>> Znamo da je indeks 3
srednji, jer mi

1361
01:06:08,020 --> 01:06:09,270
znam postoji sedam elemenata.

1362
01:06:09,270 --> 01:06:10,670
Što 7 podijeljeni po 2?

1363
01:06:10,670 --> 01:06:12,850
Možete odsjeći da dodatni 1.

1364
01:06:12,850 --> 01:06:14,850
Imaš 3 u sredini.

1365
01:06:14,850 --> 01:06:17,590
Tako je niz 3 jednaka do 7?

1366
01:06:17,590 --> 01:06:18,900
To nije, zar ne?

1367
01:06:18,900 --> 01:06:21,050
Ali možemo napraviti par čekova.

1368
01:06:21,050 --> 01:06:25,380
Je niz 3 manje od 7 ili
je niz 3 veći od 7?

1369
01:06:25,380 --> 01:06:27,240
>> A mi znamo da je manje od 7.

1370
01:06:27,240 --> 01:06:30,259
Dakle, znamo da, oh, ona mora
ne biti u lijevoj polovici.

1371
01:06:30,259 --> 01:06:32,300
Znamo da to mora biti
u desnoj polovici, zar ne?

1372
01:06:32,300 --> 01:06:34,662
Dakle, možemo samo odsjeći pola niz.

1373
01:06:34,662 --> 01:06:36,370
Mi čak ne moraju
na to gledate više.

1374
01:06:36,370 --> 01:06:38,711
Jer znamo da
pola naše problem--

1375
01:06:38,711 --> 01:06:41,210
znamo da je odgovor u
pravo polovice našeg problema.

1376
01:06:41,210 --> 01:06:42,580
Tako smo samo pogledajte kako je sada.

1377
01:06:42,580 --> 01:06:44,860
>> Dakle, sada gledamo
sredina ono što je ostalo.

1378
01:06:44,860 --> 01:06:46,880
To Indeks 5.

1379
01:06:46,880 --> 01:06:50,200
Mi radimo isti ček opet
a vidimo da je to manja.

1380
01:06:50,200 --> 01:06:52,050
Dakle, mi gledamo na lijevoj strani kako.

1381
01:06:52,050 --> 01:06:53,430
A onda ćemo vidjeti da je ček.

1382
01:06:53,430 --> 01:06:57,600
Je vrijednost niz na
Indeks 4 jednaka do 7?

1383
01:06:57,600 --> 01:06:58,260
Je.

1384
01:06:58,260 --> 01:07:03,580
Tako možemo vratiti istina, jer
našli smo vrijednosti u našem listu.

1385
01:07:03,580 --> 01:07:06,738
Da li način na koji sam otišao kroz
koje imaju smisla svima?

1386
01:07:06,738 --> 01:07:08,760
U REDU.

1387
01:07:08,760 --> 01:07:11,670
Dat ću ti dečki možda, kao što je,
tri, četiri minute shvatiti

1388
01:07:11,670 --> 01:07:13,270
kako pseudokod to.

1389
01:07:13,270 --> 01:07:18,070
>> Pa zamislite Pitao sam vas napisati
funkcija zove pretragu () koji se vratio

1390
01:07:18,070 --> 01:07:20,640
vrijednost, Boolean vrijednost,
to je istina ili false-- slično,

1391
01:07:20,640 --> 01:07:22,970
vrijedi ako je utvrdio
vrijednost false ako nije.

1392
01:07:22,970 --> 01:07:25,230
I onda si
prošao u vrijednosti koju

1393
01:07:25,230 --> 01:07:28,410
tražili u vrijednosti, koje
je array-- oh, definitivno staviti

1394
01:07:28,410 --> 01:07:29,410
da na krivom mjestu.

1395
01:07:29,410 --> 01:07:29,580
U REDU.

1396
01:07:29,580 --> 01:07:31,829
Uglavnom, koji bi trebao imati
bio na pravom vrijednosti.

1397
01:07:31,829 --> 01:07:36,280
A onda int n broj
elemenata u tom nizu.

1398
01:07:36,280 --> 01:07:39,430
Kako bi idete o težak
da pseudokod taj problem?

1399
01:07:39,430 --> 01:07:41,630
Dat ću ti dečki poput
tri minute da to učiniti.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Ne, mislim da only--
Da, postoji jedan pravi ovdje.

1402
01:08:02,595 --> 01:08:03,261
PUBLIKA: Mogu li?

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Da, dobio sam.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Je li to radi?

1406
01:08:11,050 --> 01:08:12,290
OK super.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> U REDU.

1409
01:10:44,720 --> 01:10:47,630
U redu dečki, mi smo
će ga obuzdati.

1410
01:10:47,630 --> 01:10:49,730
U REDU.

1411
01:10:49,730 --> 01:10:54,020
Dakle, pretpostavimo da imamo ovu lijepu
Malo polje sn vrijednosti u njemu.

1412
01:10:54,020 --> 01:10:55,170
Nisam nacrtati linije.

1413
01:10:55,170 --> 01:10:58,649
No, kako bi se ići o
pokušavajući napisati to?

1414
01:10:58,649 --> 01:11:00,440
Da li netko želi
daj mi prvu liniju?

1415
01:11:00,440 --> 01:11:02,814
Ako želite da mi daju
prva linija ovog pseudokod.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> PUBLIKA: [nečujan]

1418
01:11:08,430 --> 01:11:10,138
PUBLIKA: želiš
na ponoviti through--

1419
01:11:10,138 --> 01:11:11,094
PUBLIKA: Samo još jedan za petlju?

1420
01:11:11,094 --> 01:11:11,760
PUBLIKA: --for.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Pa ovo je malo zeznuto.

1423
01:11:17,780 --> 01:11:23,130
Razmislite about-- želite
držati trčanje ovu petlju

1424
01:11:23,130 --> 01:11:27,950
iznova i iznova do kada?

1425
01:11:27,950 --> 01:11:30,819
>> PUBLIKA: Do [nečujan]
vrijednost je jednaka toj vrijednosti.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Točno.

1427
01:11:31,610 --> 01:11:33,900
Tako da zapravo možete samo write--
možemo čak ga pojednostaviti više.

1428
01:11:33,900 --> 01:11:35,630
Mi samo možemo učiniti while petlja, zar ne?

1429
01:11:35,630 --> 01:11:39,380
Tako možete samo imati loop--
znamo da je to neko vrijeme.

1430
01:11:39,380 --> 01:11:42,850
No, za sada, idem
reći "petlju" - kroz što?

1431
01:11:42,850 --> 01:11:46,640
Petlja until-- ono što je
naša završava stanje?

1432
01:11:46,640 --> 01:11:47,510
Mislim da sam čuo.

1433
01:11:47,510 --> 01:11:48,530
Čuo sam da je netko to reći.

1434
01:11:48,530 --> 01:11:51,255
>> Publika: Vrijednosti jednaka sredini.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: Ponovit.

1436
01:11:52,255 --> 01:11:54,470
PUBLIKA: Ili, dok se
Vrijednost ste u potrazi

1437
01:11:54,470 --> 01:11:58,470
je jednaka srednja vrijednost.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Što ako to nije tamo?

1439
01:12:00,280 --> 01:12:03,113
Što ako je vrijednost koju traži
je zapravo u tom nizu?

1440
01:12:03,113 --> 01:12:05,890
PUBLIKA: Vraćate 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Ali ono što želimo
petlje sve dok, ako imamo stanje?

1442
01:12:08,850 --> 01:12:09,350
Da.

1443
01:12:09,350 --> 01:12:11,239
>> PUBLIKA: Do postoji samo jedna vrijednost?

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: Možete petlje
until-- tako da znate da ste

1445
01:12:13,530 --> 01:12:15,714
će imati max vrijednosti, zar ne?

1446
01:12:15,714 --> 01:12:18,130
I znate da idete
imati min vrijednost, pravo?

1447
01:12:18,130 --> 01:12:20,379
Zato također, da je nešto
Zaboravio sam reći prije,

1448
01:12:20,379 --> 01:12:22,640
da nešto što je
kritički o binarnom pretraživanje

1449
01:12:22,640 --> 01:12:24,182
je da je vaš niz već riješeno.

1450
01:12:24,182 --> 01:12:26,973
Budući da ne postoji način radi
to ako su samo slučajne vrijednosti.

1451
01:12:26,973 --> 01:12:29,190
Ne znam je li on to
veći od drugoga, zar ne?

1452
01:12:29,190 --> 01:12:32,720
>> Dakle, znate da je vaš i Max
Vaši minuta ovdje, zar ne?

1453
01:12:32,720 --> 01:12:35,590
Ako ste idući u biti podešavanje
Vaša max u vašem min i mid--

1454
01:12:35,590 --> 01:12:38,470
neka je samo pretpostaviti da
Sredinom vrijednost je u pravu here--

1455
01:12:38,470 --> 01:12:43,910
ti si idući u osnovi
petlje sve dok je vaš minimum

1456
01:12:43,910 --> 01:12:47,510
otprilike isto kao max, pravo, ili
ako vaš Max nije isto kao minuta.

1457
01:12:47,510 --> 01:12:48,040
Pravo?

1458
01:12:48,040 --> 01:12:51,340
Jer kad se to dogodi, znate da
si na kraju pogodio istu vrijednost.

1459
01:12:51,340 --> 01:12:59,135
Dakle, želite petlju dok vam min
je manji od ili jednak to-- Ups,

1460
01:12:59,135 --> 01:13:01,510
ne manje od ili jednake,
Drugi način around-- max je.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Je li to smisla?

1463
01:13:16,160 --> 01:13:18,810
Uzeo sam nekoliko pokušaja da se to pravo.

1464
01:13:18,810 --> 01:13:21,869
Ali petlje do maks vrijednosti
je u biti skoro manje

1465
01:13:21,869 --> 01:13:23,410
od ili jednak vašem minimum, zar ne?

1466
01:13:23,410 --> 01:13:25,201
To je kad znaš
da ste konvergentne.

1467
01:13:25,201 --> 01:13:29,290
PUBLIKA: Kad bi vaš maksimalni
vrijednost biti manja od minimalno?

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Ako zadržite
podešavanja, koja

1469
01:13:31,040 --> 01:13:32,380
je ono što ćemo
da se radi na tome.

1470
01:13:32,380 --> 01:13:33,460
Ima li to smisla?

1471
01:13:33,460 --> 01:13:35,750
Minimalna i maksimalna samo
integers da smo vjerojatno

1472
01:13:35,750 --> 01:13:39,260
će htjeti stvoriti zadržati
zapis u kojem tražimo.

1473
01:13:39,260 --> 01:13:41,790
Budući da je niz postoji
bez obzira na to što radimo.

1474
01:13:41,790 --> 01:13:45,030
Kao, nismo zapravo fizički
cijepanje off niz, zar ne?

1475
01:13:45,030 --> 01:13:47,261
Mi samo podešavanje
gdje tražimo.

1476
01:13:47,261 --> 01:13:48,136
Ima li to smisla?

1477
01:13:48,136 --> 01:13:48,472
>> PUBLIKA: Da.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: U redu.

1479
01:13:49,110 --> 01:13:57,090
Dakle, ako je to uvjet za naše petlji,
Što želimo unutar ove petlje?

1480
01:13:57,090 --> 01:13:58,700
Što ćemo se žele učiniti?

1481
01:13:58,700 --> 01:14:02,390
Pa sada, imamo
max i min, pravo,

1482
01:14:02,390 --> 01:14:04,962
Vjerojatno je stvorio ovdje negdje.

1483
01:14:04,962 --> 01:14:07,170
Idemo vjerojatno želite
pronaći sredinu, pravo?

1484
01:14:07,170 --> 01:14:08,450
Kako ćemo biti
mogućnosti naći sredinu?

1485
01:14:08,450 --> 01:14:09,491
Što je mathematical--

1486
01:14:09,491 --> 01:14:11,079
PUBLIKA: Max plus min podijeljena 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Točno.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Ima li to smisla?

1490
01:14:21,620 --> 01:14:25,780
I nemojte vi vidite zašto smo
nije samo use-- zašto je to učinio

1491
01:14:25,780 --> 01:14:27,850
umjesto da radi samo n podijeljeni po 2?

1492
01:14:27,850 --> 01:14:30,310
To je zato što je n vrijednost
to će ostati isti.

1493
01:14:30,310 --> 01:14:30,979
Pravo?

1494
01:14:30,979 --> 01:14:34,020
No, kao što smo prilagoditi naše najmanje i
maksimalne vrijednosti, oni će se promijeniti.

1495
01:14:34,020 --> 01:14:36,040
I kao rezultat toga, naša sredina
će se promijeniti.

1496
01:14:36,040 --> 01:14:37,873
Pa zato što želimo
to učiniti upravo ovdje.

1497
01:14:37,873 --> 01:14:38,510
U REDU.

1498
01:14:38,510 --> 01:14:41,600
>> A onda, sad kad
našli smo our-- da.

1499
01:14:41,600 --> 01:14:44,270
>> PUBLIKA: Just a quick question--
kad kažeš min i max,

1500
01:14:44,270 --> 01:14:46,410
smo uz pretpostavku da
to je već razvrstani?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Da, to je zapravo
Preduvjet za binarnog pretraživanja,

1502
01:14:48,400 --> 01:14:49,816
koje morate znati je to riješeno.

1503
01:14:49,816 --> 01:14:53,660
Koji je razlog zašto vrsta, pišete u svom
Problem postaviti prije binarnog pretraživanja.

1504
01:14:53,660 --> 01:14:55,910
U REDU.

1505
01:14:55,910 --> 01:14:58,876
Pa sada da znamo gdje je naša sredina
je, što želiš raditi ovdje?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> PUBLIKA: Želimo usporedbu
da na drugi.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Točno.

1509
01:15:05,110 --> 01:15:12,280
Dakle, ti si idući u usporedbu
Sredinom na vrijednosti, zar ne?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
A što to kažem
nas kada usporedimo?

1512
01:15:18,670 --> 01:15:22,226
Što želimo učiniti nakon toga?

1513
01:15:22,226 --> 01:15:25,389
>> PUBLIKA: Ako je vrijednost veća
od sredine, želimo ga odrezati.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Točno.

1515
01:15:26,180 --> 01:15:33,940
Dakle, ako je vrijednost veća
od sredine, mi smo

1516
01:15:33,940 --> 01:15:36,550
idući u ištanje to promijenili
minimalne i maxes, zar ne?

1517
01:15:36,550 --> 01:15:38,980
Što želimo promijeniti?

1518
01:15:38,980 --> 01:15:42,145
Dakle, ako znamo da je vrijednost negdje
ovdje, što ti mi za promjenu?

1519
01:15:42,145 --> 01:15:44,758
Želimo promijeniti naš
Minimalna biti sredinom, zar ne?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
A onda drugo, ako je to u ovom
pola, što želimo promijeniti?

1522
01:15:54,292 --> 01:15:55,306
>> PUBLIKA: Vaša maksimalna.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Da.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
A onda ste samo ide
zadržati petlje, zar ne?

1526
01:16:04,680 --> 01:16:08,920
Jer sada, nakon jedne iteracije
putem, imaš max ovdje.

1527
01:16:08,920 --> 01:16:10,760
A onda možete ponovno izračunati sredine.

1528
01:16:10,760 --> 01:16:11,990
A onda možete usporediti.

1529
01:16:11,990 --> 01:16:14,766
A vi ćete zadržati ide
do minuta i maxes

1530
01:16:14,766 --> 01:16:15,890
su u biti konvergentne.

1531
01:16:15,890 --> 01:16:17,890
A to je kada znaš da je
si pogodio kraj njega.

1532
01:16:17,890 --> 01:16:20,280
A bilo ste ga pronašli
ili niste u tom trenutku.

1533
01:16:20,280 --> 01:16:23,170
>> Da li to smisla svima?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
U REDU.

1536
01:16:26,770 --> 01:16:27,900
To je prilično važno,
jer ćete imati

1537
01:16:27,900 --> 01:16:29,760
napisati to u kodu večeras.

1538
01:16:29,760 --> 01:16:32,660
Ali ti dečki imaju prilično dobar
Osjećaj ono što bi trebao biti događaj,

1539
01:16:32,660 --> 01:16:34,051
što je dobro.

1540
01:16:34,051 --> 01:16:34,550
U REDU.

1541
01:16:34,550 --> 01:16:38,840
Dakle, imamo oko sedam
minuta napustio odjeljak.

1542
01:16:38,840 --> 01:16:43,170
Tako ćemo razgovarati o
ovo pset da ćemo biti događaj.

1543
01:16:43,170 --> 01:16:46,410
Dakle pset je podijeljen u dva dijela.

1544
01:16:46,410 --> 01:16:50,230
Prva polovica uključuje
provedbi nalaz

1545
01:16:50,230 --> 01:16:54,210
u kojem ste napisali linearnog traženja,
binarno traženje i sortiranje algoritam.

1546
01:16:54,210 --> 01:16:56,690
>> Dakle, ovo je prvi
Vrijeme u pset gdje

1547
01:16:56,690 --> 01:17:00,050
mi ćemo biti dajući vam dečki što se zove
Raspodjela kod, što je kod

1548
01:17:00,050 --> 01:17:02,740
koje smo prethodno napisano,
ali jednostavno ostavio neke dijelove off

1549
01:17:02,740 --> 01:17:04,635
ti završiti pisanje.

1550
01:17:04,635 --> 01:17:07,510
Dakle, momci, kada pogledate ovaj
broj, možda ćete stvarno dobiti prepala.

1551
01:17:07,510 --> 01:17:08,630
Ako ste samo željeli, ahh, ja
ne znam što da radi,

1552
01:17:08,630 --> 01:17:11,670
Ne znam, kao da se čini
tako komplicirano, ahh, opustite se.

1553
01:17:11,670 --> 01:17:12,170
Uredu je.

1554
01:17:12,170 --> 01:17:12,930
Pročitajte spec.

1555
01:17:12,930 --> 01:17:16,920
Spec će vam objasniti točno
Što sve od tih programa rade.

1556
01:17:16,920 --> 01:17:20,560
>> Na primjer, generate.c je program
koji će doći sa svojim pset.

1557
01:17:20,560 --> 01:17:24,060
Vi zapravo ne morate dirati, ali
trebali shvatiti što to radite.

1558
01:17:24,060 --> 01:17:28,550
I generate.c, sve što radi je
bilo generiranje slučajnih brojeva

1559
01:17:28,550 --> 01:17:32,400
ili možete dati ga sjeme, poput
planiran broj koji je potrebno,

1560
01:17:32,400 --> 01:17:34,140
i to stvara više brojeva.

1561
01:17:34,140 --> 01:17:37,170
Dakle, postoji određeni način
provesti generate.c u kojoj

1562
01:17:37,170 --> 01:17:42,760
možete jednostavno napraviti hrpa brojeva
za vas testirati svoje druge metode dalje.

1563
01:17:42,760 --> 01:17:45,900
>> Dakle, ako ste htjeli, za
primjer, testirati svoje otkriće,

1564
01:17:45,900 --> 01:17:48,970
što bi željeli pokrenuti generate.c,
generiranje hrpa brojeva,

1565
01:17:48,970 --> 01:17:50,880
a zatim pokrenuti pomagača funkciju.

1566
01:17:50,880 --> 01:17:53,930
Vaš pomagači funkcija gdje ste
zapravo fizički pisanja koda.

1567
01:17:53,930 --> 01:17:59,330
A misliti pomagača kao knjižnica datoteke
pišete da otkriće zove.

1568
01:17:59,330 --> 01:18:02,950
I tako u helpers.c, vi ćete
ne traži i sortiranje.

1569
01:18:02,950 --> 01:18:06,500
>> A onda idete na osnovi
Samo ih sve staviti zajedno.

1570
01:18:06,500 --> 01:18:10,350
Spec će vam reći kako
staviti na komandne linije.

1571
01:18:10,350 --> 01:18:14,880
A vi ćete biti u mogućnosti testirati hoće li ili
nije tvoja vrsta i traženje rade.

1572
01:18:14,880 --> 01:18:15,870
Cool.

1573
01:18:15,870 --> 01:18:18,720
Je li netko već počeli i
Problemi s kojima se susreću ili pitanja

1574
01:18:18,720 --> 01:18:20,520
oni su sada s tim?

1575
01:18:20,520 --> 01:18:21,020
U REDU.

1576
01:18:21,020 --> 01:18:21,476
>> PUBLIKA: Čekaj.

1577
01:18:21,476 --> 01:18:21,932
Imam jedno pitanje.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Da.

1579
01:18:22,844 --> 01:18:28,390
>> PUBLIKA: Tako sam počeo raditi
linearni traži u helpers.c

1580
01:18:28,390 --> 01:18:29,670
i to nije stvarno radi.

1581
01:18:29,670 --> 01:18:34,590
Ali onda kasnije sam saznala smo upravo
morati izbrisati i napraviti binarno pretraživanje.

1582
01:18:34,590 --> 01:18:36,991
Tako je to važno, ako to ne radi?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: Kratak odgovor je ne.

1585
01:18:41,510 --> 01:18:42,642
No, budući da smo not--

1586
01:18:42,642 --> 01:18:44,350
PUBLIKA: Ali nitko ne
zapravo provjeru.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Mi smo Nikad
će to vidjeti.

1588
01:18:46,058 --> 01:18:49,590
Ali vjerojatno želite učiniti
je li vaša potraga radi.

1589
01:18:49,590 --> 01:18:51,700
Jer ako vaš linearni
traži ne radi,

1590
01:18:51,700 --> 01:18:54,410
onda su šanse vaš binarni
Traženje ne ide na posao kao dobro.

1591
01:18:54,410 --> 01:18:56,646
Jer imate slične
Logika u oba od njih.

1592
01:18:56,646 --> 01:18:58,020
I ne, to nije važno.

1593
01:18:58,020 --> 01:19:01,300
Dakle, jedini ćete uključiti
u su vrsta i binarno traženje.

1594
01:19:01,300 --> 01:19:02,490
Da.

1595
01:19:02,490 --> 01:19:06,610
>> I također, puno djece su
pokušava sastaviti helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Nisi zapravo dopušteno
to učiniti, jer helpers.c

1597
01:19:09,550 --> 01:19:11,200
nema glavnu ulogu.

1598
01:19:11,200 --> 01:19:13,550
I tako da bi trebao samo
se zapravo sastavljanju

1599
01:19:13,550 --> 01:19:18,670
generiranje i naći, jer naći pozive
helpers.c i djeluje u njemu.

1600
01:19:18,670 --> 01:19:20,790
Tako da čini ispravljanje pogrešaka
bol u kundak.

1601
01:19:20,790 --> 01:19:22,422
No, to je ono što moramo učiniti.

1602
01:19:22,422 --> 01:19:23,880
PUBLIKA: Vi samo napraviti sve, zar ne?

1603
01:19:23,880 --> 01:19:27,290
ANDI PENG: Možete samo
učiniti sve što je dobro, da.

1604
01:19:27,290 --> 01:19:28,060
U REDU.

1605
01:19:28,060 --> 01:19:32,570
Dakle, to je to u smislu onoga što
pset traži da svi rade.

1606
01:19:32,570 --> 01:19:35,160
Ako imate bilo kakvih pitanja, osjećam
slobodno me pitajte nakon dijelu.

1607
01:19:35,160 --> 01:19:37,580
Ja ću biti ovdje, kao što su, 20 minuta.

1608
01:19:37,580 --> 01:19:40,500
>> I da, u pset-a
stvarno nije tako loše.

1609
01:19:40,500 --> 01:19:41,680
Vi bi trebali biti u redu.

1610
01:19:41,680 --> 01:19:43,250
To, samo slijedite upute.

1611
01:19:43,250 --> 01:19:47,840
Vrsta imaju osjećaj, logično, što
treba biti događa i što će biti u redu.

1612
01:19:47,840 --> 01:19:48,690
Nemojte biti previše uplašena.

1613
01:19:48,690 --> 01:19:50,220
Postoji mnogo koda
već napisao tamo.

1614
01:19:50,220 --> 01:19:53,011
Nemojte biti previše uplašena, ako ne
shvatiti što sve to znači.

1615
01:19:53,011 --> 01:19:54,749
Ako je puno, to je potpuno u redu.

1616
01:19:54,749 --> 01:19:55,790
I doći do radnog vremena.

1617
01:19:55,790 --> 01:19:57,520
Mi ćemo vam pomoći da se pogledati.

1618
01:19:57,520 --> 01:20:00,810
>> PUBLIKA: Uz doplatu
Funkcije, ne gledamo one gore?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Da, oni su u kodu.

1620
01:20:03,417 --> 01:20:05,750
U igri 15, pola
to je napisano već za vas.

1621
01:20:05,750 --> 01:20:09,310
Dakle, oni su funkcije
Već u kodu.

1622
01:20:09,310 --> 01:20:12,020
Yep.

1623
01:20:12,020 --> 01:20:12,520
U redu.

1624
01:20:12,520 --> 01:20:14,000
Pa, mnogo sreće.

1625
01:20:14,000 --> 01:20:15,180
To je odvratno dan.

1626
01:20:15,180 --> 01:20:19,370
Dakle, nadamo se da dečki ne osjećam previše
loše borave unutar i kodiranje.

1627
01:20:19,370 --> 01:20:22,133