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

2
00:00:11,100 --> 00:00:12,300
>> SPEAKER 1: Hei toată lumea!

3
00:00:12,300 --> 00:00:13,890
Bine ați revenit la pct.

4
00:00:13,890 --> 00:00:17,480
Mă bucur să văd atât de mulți dintre voi amândoi aici,
și toți cei care se uită on-line.

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

6
00:00:18,760 --> 00:00:20,920
Deci, ca de obicei înapoi bun venit.

7
00:00:20,920 --> 00:00:24,360
Sper că toate au avut un minunat
week-end, plin de odihnă, relaxare.

8
00:00:24,360 --> 00:00:26,026
A fost frumos ieri.

9
00:00:26,026 --> 00:00:27,525
Așa că, sper că va plăcut în aer liber.

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

11
00:00:28,840 --> 00:00:30,610
>> Deci, în primul rând o pereche de anunțuri.

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

13
00:00:31,920 --> 00:00:32,700
Standard folosit.

14
00:00:32,700 --> 00:00:37,350
Așa că, cele mai multe dintre voi ar fi ajuns un
e-mail de la mine despre PSET ta Scratch,

15
00:00:37,350 --> 00:00:39,920
precum și de clasificare pentru PSET 1.

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

17
00:00:41,000 --> 00:00:42,220
Așa că, doar câteva lucruri.

18
00:00:42,220 --> 00:00:45,150
Asigurați-vă că pentru a utiliza check50 în style50.

19
00:00:45,150 --> 00:00:47,250
Acestea sunt menite să fie
Resurse pentru voi,

20
00:00:47,250 --> 00:00:50,660
pentru a vă asigura că sunteți obtinerea
cât mai multe puncte ca tine poate

21
00:00:50,660 --> 00:00:52,390
fără a pierde inutil ele.

22
00:00:52,390 --> 00:00:54,407
Așa că, lucruri de genul stil
sunt foarte importante.

23
00:00:54,407 --> 00:00:55,740
Vom lua off pentru ea.

24
00:00:55,740 --> 00:00:58,115
Unii dintre voi ar putea avea deja
observat că de la PSET ta.

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

26
00:00:58,920 --> 00:01:01,450
Și check50 este doar un
mod foarte ușor de a vă asigura

27
00:01:01,450 --> 00:01:05,050
că suntem de fapt revenirea ceea ce
trebuie să fie returnat utilizatorului,

28
00:01:05,050 --> 00:01:06,690
și că totul funcționează corect.

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

30
00:01:08,690 --> 00:01:12,040
>> La a doua notă, asigurați-vă că dumneavoastră
încărcarea lucruri în folderul corect.

31
00:01:12,040 --> 00:01:14,470
Aceasta face ca viața mea doar o
pic mai dificil

32
00:01:14,470 --> 00:01:18,836
dacă încărcați PSET 2 în PSET 1
pentru că atunci când am descărca lucruri,

33
00:01:18,836 --> 00:01:20,085
ele nu se descarcă corect.

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

35
00:01:21,690 --> 00:01:24,560
Și știu că e un pic subred
într-un sistem să se obișnuiască cu,

36
00:01:24,560 --> 00:01:26,950
ci doar să fie super-
până la în cazul în care numai pentru mine,

37
00:01:26,950 --> 00:01:30,080
astfel încât atunci când sunteți de asistent e-mailuri
la fel ca 2 A.M. si eu sunt de clasificare.

38
00:01:30,080 --> 00:01:33,710
Dacă nu pentru că am să te uiți
peste tot în jurul pentru PSET ta.

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

40
00:01:34,440 --> 00:01:37,270
>> Știu că e devreme, dar eu
total a fost luată cu garda jos

41
00:01:37,270 --> 00:01:40,800
de un eseu care este cauza aceasta vineri, că
profesorii mei au fost la fel ca, oh da.

42
00:01:40,800 --> 00:01:42,550
Amintiți-vă, aveți un
eseu datorită vineri.

43
00:01:42,550 --> 00:01:45,780
Așa că, știu că nu-i place
să se gândească la examenele,

44
00:01:45,780 --> 00:01:50,620
dar primul test este în 15 octombrie,
care se octombrie începând din această săptămână.

45
00:01:50,620 --> 00:01:53,290
Astfel, ar putea fi mai devreme
decât v-ați așteptat este tot.

46
00:01:53,290 --> 00:01:57,510
Astfel că nu ești aruncat cu garda jos atunci când
Menționez secțiune de săptămâna viitoare că oh,

47
00:01:57,510 --> 00:02:00,560
dvs. de test săptămâna viitoare, m-am gândit
Ți-aș da un pic mai mult

48
00:02:00,560 --> 00:02:01,500
de un heads-up acum.

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

50
00:02:02,970 --> 00:02:04,660
>> Astfel, problema ta stabilite, numărul trei.

51
00:02:04,660 --> 00:02:07,070
Modul în care oamenii au citit
spec din curiozitate?

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
OK.

54
00:02:09,199 --> 00:02:10,229
Avem un cuplu.

55
00:02:10,229 --> 00:02:12,320
Un fel de jos din trecut
săptămână, dar asta e OK.

56
00:02:12,320 --> 00:02:13,650
Știu că a fost mai frumos.

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

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

59
00:02:16,660 --> 00:02:21,010
Categoric după ce te-ai făcut
citește astăzi spec ta cu cel puțin

60
00:02:21,010 --> 00:02:25,240
încercați ca descărcarea
Codul de distribuție și funcționare

61
00:02:25,240 --> 00:02:27,430
la fel ca prima inițială
lucru pe care vă rog să.

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

63
00:02:28,681 --> 00:02:32,590
Pentru ca suntem cu ajutorul
Codul de distribuție și o bibliotecă

64
00:02:32,590 --> 00:02:36,790
că am fost doar using-- --It e doar
a doua oară am făcut acest PSET,

65
00:02:36,790 --> 00:02:38,650
lucruri nebunești se poate intampla
cu aparatul,

66
00:02:38,650 --> 00:02:41,370
și doriți să găsiți că
acum versus mai târziu.

67
00:02:41,370 --> 00:02:45,570
>> Pentru că dacă e joi seara sau e
Miercuri noapte și pentru un motiv oarecare

68
00:02:45,570 --> 00:02:48,912
aparatul pur și simplu nu
doresc să curgă de la biblioteca

69
00:02:48,912 --> 00:02:50,620
sau cu distribuția
cod, că mijloacele

70
00:02:50,620 --> 00:02:52,309
nu poți începe să faci de codificare.

71
00:02:52,309 --> 00:02:54,100
Pentru că nu poți verifica
pentru a vedea dacă funcționează.

72
00:02:54,100 --> 00:02:55,975
Dumneavoastră nu va fi capabil
pentru a vedea dacă acesta compilează.

73
00:02:55,975 --> 00:03:00,500
Vrei să aibă grijă de cei care la începutul anului
a săptămânii, atunci când se poate trimite un email pentru încă mă

74
00:03:00,500 --> 00:03:03,100
sau una dintre celelalte TFS,
și putem obține cele fixe.

75
00:03:03,100 --> 00:03:05,410
Deoarece acestea sunt probleme
care sunt de gând să te oprească

76
00:03:05,410 --> 00:03:07,120
de la a face orice progres real.

77
00:03:07,120 --> 00:03:10,055
Nu e ca un bug, care
poti doar un fel de săriți peste.

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

79
00:03:10,712 --> 00:03:13,420
Dacă aveți probleme cu dvs.
aparat sau cod de distribuție,

80
00:03:13,420 --> 00:03:16,211
chiar vrei să te că ia
de îngrijire de mai devreme, mai degrabă decât mai târziu.

81
00:03:16,211 --> 00:03:20,410
Deci, chiar dacă nu ești de fapt o să
începe de codificare, descarcati distribuție

82
00:03:20,410 --> 00:03:24,040
cod, citiți spec, asigurați-vă că
totul merge acolo.

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

84
00:03:25,134 --> 00:03:27,675
Dacă se poate face doar asta, am
promit, viața voastră va fi mai ușor.

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

86
00:03:28,800 --> 00:03:31,410
Și așa ești, probabil, va
să o fac chiar acum corect?

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

88
00:03:32,100 --> 00:03:33,950
Așa că, orice întrebări acolo?

89
00:03:33,950 --> 00:03:35,850
Orice lucruri logistice?

90
00:03:35,850 --> 00:03:36,910
Toată lumea e bine?

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

92
00:03:38,270 --> 00:03:41,700
>> Disclaimer pentru cei de
te în cameră și on-line.

93
00:03:41,700 --> 00:03:45,437
Am de gând să fie încercarea de a comuta
între PowerPoint în aparat

94
00:03:45,437 --> 00:03:47,270
pentru că am de gând
să fie faci unele de codificare

95
00:03:47,270 --> 00:03:53,630
astăzi la cererea publicului de anonim
poll sugestie am trimis săptămâna trecută.

96
00:03:53,630 --> 00:03:55,480
Așa că, vom face unele de codificare.

97
00:03:55,480 --> 00:03:57,800
Așa că, dacă voi dori, de asemenea
pentru a porni aparatele dumneavoastră,

98
00:03:57,800 --> 00:04:02,910
și ar trebui să-au luat un e-mail
de la mine, cu un fișier mostră.

99
00:04:02,910 --> 00:04:04,310
Vă rugăm să nu ezitați să fac asta.

100
00:04:04,310 --> 00:04:07,340
>> Așa că, vom vorbi despre
GDB, care este un program de depanare.

101
00:04:07,340 --> 00:04:09,970
O să te ajute
un fel de seama unde

102
00:04:09,970 --> 00:04:11,860
lucrurile nu merg bine în cod.

103
00:04:11,860 --> 00:04:15,370
Este într-adevăr doar o modalitate de a-și intensifice
prin codul așa cum se întâmplă,

104
00:04:15,370 --> 00:04:19,100
și să fie capabil de a imprima variabile
sau pentru a vedea ce se întâmplă de fapt

105
00:04:19,100 --> 00:04:22,980
sub capota versetele Program
doar rulează, e ca si cum faulting,

106
00:04:22,980 --> 00:04:25,030
si tu esti ca, nici o idee
ce sa întâmplat aici.

107
00:04:25,030 --> 00:04:26,730
Nu știu ce linie a eșuat la.

108
00:04:26,730 --> 00:04:29,040
Nu știu de unde a mers prost.

109
00:04:29,040 --> 00:04:31,280
Așa că, GDB este de gând să te ajut cu asta.

110
00:04:31,280 --> 00:04:35,240
De asemenea, dacă vă decideți să
continuă da, și să ia 61,

111
00:04:35,240 --> 00:04:38,430
aceasta va într-adevăr, să fie într-adevăr ta
cel mai bun prieten, pentru că eu pot să vă spun

112
00:04:38,430 --> 00:04:40,840
pentru că am de gând prin acea categorie.

113
00:04:40,840 --> 00:04:43,620
>> Ne vom uita la binar
căutare, care, dacă voi aminti

114
00:04:43,620 --> 00:04:47,540
marele exemplu de carte de telefon
spectacol de clasă.

115
00:04:47,540 --> 00:04:50,620
Vom fi de punere în aplicare, care, și
mersul pe jos prin faptul că un pic mai mult,

116
00:04:50,620 --> 00:04:54,650
iar apoi vom trece prin patru
diferite tipuri, care sunt bule,

117
00:04:54,650 --> 00:04:56,285
Selecție, Insertion, și Merge.

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

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

120
00:04:58,330 --> 00:05:00,390
Astfel, GDB cum am menționat, este un program de depanare.

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

122
00:05:01,400 --> 00:05:09,370
Și acestea sunt un fel de big
lucruri, funcțiile mari sau comenzi

123
00:05:09,370 --> 00:05:13,240
pe care le utilizați în GDB, și voi umbla
tu printr-un demo de ea într-o secundă.

124
00:05:13,240 --> 00:05:15,360
>> Așa că, acest lucru nu este doar
O să stați abstract.

125
00:05:15,360 --> 00:05:18,000
Voi încerca și să-l ca beton
este posibil pentru voi.

126
00:05:18,000 --> 00:05:19,870
Așa că, rupe.

127
00:05:19,870 --> 00:05:22,200
Va fi, fie pauză
cum ar fi, unele număr, care

128
00:05:22,200 --> 00:05:26,900
reprezintă o linie în programul tău,
sau poti numi o funcție.

129
00:05:26,900 --> 00:05:30,150
Așa că, dacă spui rupe principal,
se va opri la principal,

130
00:05:30,150 --> 00:05:32,400
si lasa te plimbi prin această funcție.

131
00:05:32,400 --> 00:05:36,350
>> De asemenea, dacă aveți ceva extern
functioneaza ca Swap sau Cube,

132
00:05:36,350 --> 00:05:38,450
că ne-am uitat la săptămâna trecută.

133
00:05:38,450 --> 00:05:41,780
Dacă spui rupe unul din cei,
ori de câte ori programul dvs. ajunge la asta,

134
00:05:41,780 --> 00:05:44,290
se va aștepta pentru tine de a
spune-l ce să facă.

135
00:05:44,290 --> 00:05:47,860
Înainte de a va executa doar ca să
ar putea interveni de fapt in interiorul functiei

136
00:05:47,860 --> 00:05:49,020
și să vedem ce se întâmplă.

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

138
00:05:50,370 --> 00:05:53,515
Așa că, în continuare, doar sare peste
linia următoare, trece peste funcțiile.

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

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

141
00:05:55,560 --> 00:05:56,810
Acestea sunt toate puțin abstract.

142
00:05:56,810 --> 00:06:00,530
Deci, am de gând doar pentru a rula prin intermediul lor,
dar le vei vedea în uz într-o secundă.

143
00:06:00,530 --> 00:06:01,810
>> Pas într-o funcție.

144
00:06:01,810 --> 00:06:04,170
Deci, cum spuneam,
cum ar fi cu Swap, ar fi

145
00:06:04,170 --> 00:06:07,110
vă permit să fapt ca daca esti
ca pas cu pas fizic în interior,

146
00:06:07,110 --> 00:06:10,990
poți pune cu aceste variabile, imprimare
ce sunt, să vedem ce se întâmplă.

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

148
00:06:12,140 --> 00:06:14,830
Listă doar literalmente imprima
din codul înconjurător.

149
00:06:14,830 --> 00:06:17,570
Deci, dacă un fel de uitat
în cazul în care vă aflați în programul tău,

150
00:06:17,570 --> 00:06:19,880
sau te intrebi
ce se întâmplă în jurul lui,

151
00:06:19,880 --> 00:06:23,790
acest lucru va imprima doar un segment
de place cinci sau șase rânduri în jurul ei.

152
00:06:23,790 --> 00:06:26,080
Deci, puteți obține orientate
despre locul unde ești.

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

154
00:06:27,230 --> 00:06:28,650
>> Printeaza unele variabile.

155
00:06:28,650 --> 00:06:34,590
Așa că, dacă aveți cheia ca
în Cezar, că ne vom uita la.

156
00:06:34,590 --> 00:06:36,220
Se poate spune Print cheie în orice moment.

157
00:06:36,220 --> 00:06:40,070
O să-ți spun ce valoarea este atât de
care, poate undeva pe drum,

158
00:06:40,070 --> 00:06:42,070
ai suprascris cheia.

159
00:06:42,070 --> 00:06:45,495
Vă pot spune de fapt că, din cauza
puteți observa că de fapt valoare.

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

161
00:06:46,500 --> 00:06:48,780
>> În localnicii, doar amprentele
din variabilele locale.

162
00:06:48,780 --> 00:06:53,120
Așa că, oricând ești într-o buclă,
si doriti doar pentru a vedea cum ar fi, oh.

163
00:06:53,120 --> 00:06:54,270
Ce este mea?

164
00:06:54,270 --> 00:06:57,020
Ce este această valoare cheie
pe care am inițializa aici?

165
00:06:57,020 --> 00:06:58,537
Care este mesajul în acest moment?

166
00:06:58,537 --> 00:07:00,370
Se va imprima doar tot
dintre acestea, astfel încât să

167
00:07:00,370 --> 00:07:04,330
Nu trebuie să individual
spune, Print I. Print mesaj.

168
00:07:04,330 --> 00:07:04,970
Imprimare Key.

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
Și apoi Afișare.

171
00:07:07,700 --> 00:07:10,370
Ceea ce nu este la fel de tine
pas prin intermediul programului,

172
00:07:10,370 --> 00:07:13,980
se va face doar vă că este
unde sunt afișate unele anumite variabile

173
00:07:13,980 --> 00:07:14,780
la fiecare punct.

174
00:07:14,780 --> 00:07:17,160
Astfel încât să also-- --it e
un fel de scurtătură în cazul în care

175
00:07:17,160 --> 00:07:19,530
nu trebuie să continui ca, oh.

176
00:07:19,530 --> 00:07:23,150
Print cheie sau Print I. Pur și simplu
se va face în mod automat pentru tine.

177
00:07:23,150 --> 00:07:25,959
>> Astfel, cu asta, vom
pentru a vedea cum merge.

178
00:07:25,959 --> 00:07:28,000
Am de gând să încerc și comutator
pe la aparat mea.

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

180
00:07:30,200 --> 00:07:31,271
Vezi dacă pot să fac acest lucru.

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

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

183
00:07:40,970 --> 00:07:42,370
Noi doar de gând să-l oglindă.

184
00:07:42,370 --> 00:07:44,530
Nu e nimic nebun
pe laptop-ul meu oricum.

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
OK.

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
Acest lucru trebuie să fie acesta.

189
00:08:01,054 --> 00:08:01,795
E atât de mic.

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

191
00:08:03,730 --> 00:08:05,120
Să vedem dacă putem face acest lucru.

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> OK.

194
00:08:10,940 --> 00:08:15,305
Alice este, evident, luptă
aici doar un pic,

195
00:08:15,305 --> 00:08:17,995
dar o vom lua într-un momento.

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
OK.

198
00:08:22,020 --> 00:08:25,900
Suntem doar de gând să crească asta.

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
OK.

201
00:08:29,380 --> 00:08:31,679
Poate toată lumea un fel de a vedea asta?

202
00:08:31,679 --> 00:08:32,470
Poate un pic?

203
00:08:32,470 --> 00:08:33,594
Știu că e un pic mai mic.

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

205
00:08:34,570 --> 00:08:37,530
Nu puteți da seama
modul de a face acest lucru mai mari.

206
00:08:37,530 --> 00:08:38,350
Dacă cineva știe.

207
00:08:38,350 --> 00:08:40,309
Stie cineva cum să facă mai mare?

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

209
00:08:40,932 --> 00:08:42,140
Noi o să se rostogolească cu el.

210
00:08:42,140 --> 00:08:45,801
Nu conteaza oricum, pentru că e doar
care este codul pe care voi trebuie

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

212
00:08:46,300 --> 00:08:48,310
>> Ce e mai important
este terminalul aici.

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

214
00:08:52,840 --> 00:08:58,690
Și avem aici De ce este atât de mic?

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

216
00:09:02,325 --> 00:09:02,825
Setări.

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
Oh.

219
00:09:08,420 --> 00:09:09,500
Adevărat Ike.

220
00:09:09,500 --> 00:09:10,880
Cum e asta?

221
00:09:10,880 --> 00:09:11,770
De acolo.

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

223
00:09:19,370 --> 00:09:21,810
E mai bine pentru toată lumea?

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

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

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

227
00:09:25,830 --> 00:09:28,220
>> Știi când ești într-un CS
dificultăți tehnice de clasă

228
00:09:28,220 --> 00:09:32,971
sunt un fel de parte de the--
Deci, să îndepărteze acest lucru.

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

230
00:09:33,470 --> 00:09:38,060
Așa că, chiar aici, în secțiune,
pe care am avut aici.

231
00:09:38,060 --> 00:09:40,830
Cezar este un fișier executabil.

232
00:09:40,830 --> 00:09:41,800
Așa că am făcut.

233
00:09:41,800 --> 00:09:46,370
Așa că, un lucru pentru a realiza cu GDB este
că aceasta funcționează doar pe fișierele executabile.

234
00:09:46,370 --> 00:09:48,040
Deci, nu se poate rula pe o dotsy.

235
00:09:48,040 --> 00:09:50,532
Va trebui să facă de fapt
sigur că codul dvs. compilează,

236
00:09:50,532 --> 00:09:51,865
și că aceasta poate fi de fapt rula.

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

238
00:09:52,970 --> 00:09:56,186
>> Așa că, asigurați-vă că în cazul în care nu
compila, sa-l pentru a compila,

239
00:09:56,186 --> 00:09:57,810
astfel încât să puteți fel de a alerga prin ea.

240
00:09:57,810 --> 00:10:04,590
Așa că, pentru a începe GDB, tot ce faci,
Gloria tip GDB, iar apoi doar

241
00:10:04,590 --> 00:10:06,250
fișier pe care doriți.

242
00:10:06,250 --> 00:10:08,240
Intotdeauna mi-am misspell Cezar.

243
00:10:08,240 --> 00:10:11,730
Dar doriți să vă asigurați că
din moment ce este un executabil,

244
00:10:11,730 --> 00:10:14,210
dot rapidă ti, astfel încât
înseamnă că va

245
00:10:14,210 --> 00:10:19,240
pentru a rula CSI ai de gând să execute
acest fișiere, fie cu debugger.

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

247
00:10:19,910 --> 00:10:22,885
Deci, nu asta, veți obține
acest tip de păsărească.

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

249
00:10:24,250 --> 00:10:25,750
E doar toate lucrurile despre debugger.

250
00:10:25,750 --> 00:10:28,200
Nu trebuie într-adevăr să
vă faceți griji despre asta chiar acum.

251
00:10:28,200 --> 00:10:31,460
Și, după cum vedeți, avem această
parens deschise, PIB-ul, parens apropiate,

252
00:10:31,460 --> 00:10:34,690
și doar un fel de arata ca
linia noastra de comanda, nu?

253
00:10:34,690 --> 00:10:37,010
>> Deci, ce vrem să do--
--So, Primul lucru

254
00:10:37,010 --> 00:10:39,570
este ne-o dorim pentru a alege
un loc să-l rupe.

255
00:10:39,570 --> 00:10:42,332
Astfel, există un bug
în acest program Cezar

256
00:10:42,332 --> 00:10:44,290
că eu prezint, că
vom afla.

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

258
00:10:45,330 --> 00:10:56,350
Ea ceea ce face este dureaza de intrare
Barfoo în toate capacele, și pentru un motiv oarecare

259
00:10:56,350 --> 00:11:01,950
aceasta nu se schimba A. Pur și simplu frunze
l în pace, e orice altceva corect,

260
00:11:01,950 --> 00:11:03,980
dar a doua scrisoare
O rămâne neschimbat.

261
00:11:03,980 --> 00:11:07,120
Așa că, vom încerca și
dau seama de ce, care este.

262
00:11:07,120 --> 00:11:10,440
Așa că, primul lucru pe care în mod obișnuit
vreau să fac de fiecare dată când începe GDB

263
00:11:10,440 --> 00:11:12,010
Este seama de unde să-l rupe.

264
00:11:12,010 --> 00:11:14,956
>> Deci, Cezar este un program destul de scurt.

265
00:11:14,956 --> 00:11:16,330
Doar avem o singură funcție, nu?

266
00:11:16,330 --> 00:11:18,520
Care a fost funcția noastră în Cezar?

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

268
00:11:19,590 --> 00:11:24,350
Există doar o singură funcție, chiar Main?

269
00:11:24,350 --> 00:11:26,490
Principal este o funcție
pentru toate programele.

270
00:11:26,490 --> 00:11:29,230
Dacă nu ați avea principal, aș putea
fi un pic ingrijorat acum,

271
00:11:29,230 --> 00:11:31,000
dar sper că toate au avut Main acolo.

272
00:11:31,000 --> 00:11:34,150
Deci, ce putem face este să putem
doar rupe principal, la fel ca asta.

273
00:11:34,150 --> 00:11:35,190
Așa că, se spune, OK.

274
00:11:35,190 --> 00:11:37,430
Am stabilit un punct de întrerupere noastră acolo.

275
00:11:37,430 --> 00:11:42,870
>> Așa că, acum lucru de retinut este Cezar
reușește o comandă argument linie dreaptă

276
00:11:42,870 --> 00:11:45,150
și nu am făcut asta încă nicăieri.

277
00:11:45,150 --> 00:11:47,560
Deci, ce faci este atunci când
tu de fapt mergi pentru a rula

278
00:11:47,560 --> 00:11:51,540
programul, orice program care ești
se execută în GDB care are nevoie de linie de comandă

279
00:11:51,540 --> 00:11:55,010
argumente, ai de gând să intrare
atunci când începe primul rulează-l.

280
00:11:55,010 --> 00:11:59,280
Așa că, în acest caz, ne vom face
Pornește cu o cheie de trei.

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

282
00:12:00,770 --> 00:12:02,040
Și va începe de fapt.

283
00:12:02,040 --> 00:12:08,480
>> Așa că, dacă vedeți aici, avem
Dacă RC nu este egal cu 2.

284
00:12:08,480 --> 00:12:12,210
Deci, dacă voi avea tot
care fișier pe care am trimis în sus

285
00:12:12,210 --> 00:12:15,100
veți vedea că e ca
primul rând funcția noastră principală, nu?

286
00:12:15,100 --> 00:12:17,890
Este verificare pentru a vedea dacă avem
numărul corect de argumente.

287
00:12:17,890 --> 00:12:20,620
Așa că, dacă vă întrebați
în cazul în care RC este corectă,

288
00:12:20,620 --> 00:12:23,250
poti face ceva la fel ca Print RC.

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

290
00:12:24,380 --> 00:12:28,640
RC este doi, care este
ceea ce ne-am așteptat, nu?

291
00:12:28,640 --> 00:12:32,010
>> Așa că, putem merge în continuare,
și continuă prin.

292
00:12:32,010 --> 00:12:33,200
Deci, avem o cheie acolo.

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

294
00:12:34,260 --> 00:12:37,090
Și putem imprima cheia noastră
pentru a vă asigura că este corect.

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

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

297
00:12:39,500 --> 00:12:41,210
Nu este destul de ceea ce ne-am așteptat.

298
00:12:41,210 --> 00:12:44,810
Așa că, un singur lucru pentru a realiza
cu GDB, de asemenea, este

299
00:12:44,810 --> 00:12:49,000
asta nu e până când de fapt lovit
În continuare, că linia pe care tocmai l-ai văzut

300
00:12:49,000 --> 00:12:50,720
este, de fapt executat.

301
00:12:50,720 --> 00:12:53,870
Așa că, în acest caz Cheie
nu a fost atribuit încă.

302
00:12:53,870 --> 00:12:57,050
Așa că, Key este o valoare gunoi
pe care le vezi pe partea de jos acolo.

303
00:12:57,050 --> 00:13:03,680
Negativ $ 120-- --It de un miliard
și ceva lucruri ciudate corect?

304
00:13:03,680 --> 00:13:05,340
Nu e cheia care ne-am așteptat.

305
00:13:05,340 --> 00:13:10,720
Dar dacă ne-am lovit pe Următorul, apoi ne
încercați și tasta Print, e trei.

306
00:13:10,720 --> 00:13:11,710
>> Toată lumea poate vedea că?

307
00:13:11,710 --> 00:13:13,780
Așa că, dacă aveți ceva
că tu ești ca, așteptați.

308
00:13:13,780 --> 00:13:15,540
Acest lucru este complet
greșit, și eu nu știu

309
00:13:15,540 --> 00:13:20,150
cum acest lucru se va întâmpla pentru că tot ce vreau
să faceți este să atribui un număr, o variabilă,

310
00:13:20,150 --> 00:13:22,900
încercați lovind Apoi, încercați să imprimați
-o din nou, și a vedea dacă funcționează.

311
00:13:22,900 --> 00:13:27,830
Pentru ca este doar de gând să execute și
atribuie de fapt ceva după tine

312
00:13:27,830 --> 00:13:29,340
lovit următor.

313
00:13:29,340 --> 00:13:30,336
Face sens pentru toată lumea?

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

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Când aleatoare
Numerele ce înseamnă asta?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: E doar aleator.

317
00:13:34,790 --> 00:13:35,710
E doar gunoi.

318
00:13:35,710 --> 00:13:38,320
E doar ceva ce dvs.
computer va atribui aleatoriu.

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

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

321
00:13:40,220 --> 00:13:45,760
Deci, acum ne putem deplasa prin, și așa
acum avem acest getString text simplu.

322
00:13:45,760 --> 00:13:48,600
Așa că, lasă-mă să introducă ceea ce
se va întâmpla atunci când am lovit pe Următorul aici.

323
00:13:48,600 --> 00:13:51,320
GDB nostru fel de dispare, nu?

324
00:13:51,320 --> 00:13:55,720
Asta pentru că getString
acum este de executare, nu?

325
00:13:55,720 --> 00:14:01,460
Așa că, atunci când am văzut text simplu este egal
GetString, parens deschise și parens,

326
00:14:01,460 --> 00:14:04,380
și ne-am lovit continuare, care are
de fapt executat acum.

327
00:14:04,380 --> 00:14:06,580
Astfel, este de așteptare pentru
ne la intrare ceva.

328
00:14:06,580 --> 00:14:13,560
>> Așa că, vom intrare hrana noastră care
este ceea ce este în lipsa cum v-am spus

329
00:14:13,560 --> 00:14:18,020
și că doar spune că e
a terminat de executare, că închis

330
00:14:18,020 --> 00:14:19,980
Suport înseamnă că este
care iese din bucla asta.

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

332
00:14:21,170 --> 00:14:25,420
Astfel, ne putem lovi în continuare, și acum, așa cum am
sigur că ești familiar de la Cezar,

333
00:14:25,420 --> 00:14:27,260
aceasta este, ceea ce este această linie de gând să faci.

334
00:14:27,260 --> 00:14:32,030
E pentru Int I este egal cu 0, N este egal
Strlen, text simplu, și apoi

335
00:14:32,030 --> 00:14:33,960
I este mai mică decât n, I, plus, plus.

336
00:14:33,960 --> 00:14:35,210
Ce este această buclă de gând să faci?

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

338
00:14:37,900 --> 00:14:39,160
Deschideți mesajul tău.

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

340
00:14:39,770 --> 00:14:41,330
Deci, să începem a face asta.

341
00:14:41,330 --> 00:14:47,210
>> Așa că, ar trebui această condiție
se potrivesc, pentru prima noastră o?

342
00:14:47,210 --> 00:14:52,250
Dacă e un B, e text simplu I. Noi
pot obține informații despre localnici noastre.

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

344
00:14:53,610 --> 00:14:57,970
Așa că, eu este zero, iar în cazul în care șase, care
ne așteptăm, iar cheia noastră este de trei.

345
00:14:57,970 --> 00:14:59,227
Tot ceea ce face sens, nu?

346
00:14:59,227 --> 00:15:01,310
Aceste numere sunt toate
exact ce ar trebui să fie.

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

348
00:15:02,590 --> 00:15:03,870
Așa că, hum?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Eu am
numere aleatoare pentru a mea.

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

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: Ei bine, putem --we check--
poate vorbi despre faptul că într-o secundă.

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

353
00:15:14,110 --> 00:15:15,750
Dar tu ar trebui să fie de asistent asta.

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

355
00:15:17,700 --> 00:15:20,130
Așa că, dacă avem un capital
B pentru primul nostru este de

356
00:15:20,130 --> 00:15:22,080
această condiție ar trebui să-l prind, nu?

357
00:15:22,080 --> 00:15:27,120
Așa că, dacă ne-am lovit continuare, vom vedea
că acest În cazul în care de fapt executa.

358
00:15:27,120 --> 00:15:29,220
Pentru că dacă ești următor
de-a lungul în codul dvs.,

359
00:15:29,220 --> 00:15:33,460
această linie de aici, unde text simplu I
se înlocuiește cu această aritmetică,

360
00:15:33,460 --> 00:15:35,720
execută numai în cazul în care în cazul în care
condiție este corect corect?

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

362
00:15:36,905 --> 00:15:40,240
>> GDB este doar de gând să-ți arăt
lucruri care sunt de fapt de executare.

363
00:15:40,240 --> 00:15:45,140
Deci, în cazul în care această condiție cazul în care nu a fost îndeplinită, e
doar de gând pentru a trece la următoarea linie.

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

365
00:15:46,540 --> 00:15:48,510
Deci, avem asta.

366
00:15:48,510 --> 00:15:51,171
Această categorie înseamnă că este
închis din care bucla acum.

367
00:15:51,171 --> 00:15:52,420
Așa că, o să înceapă din nou.

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

369
00:15:54,760 --> 00:15:56,280
La fel ca asta.

370
00:15:56,280 --> 00:15:59,120
Astfel, încât să putem obține multe informații
despre localnici noastre aici,

371
00:15:59,120 --> 00:16:02,575
și vedem că primul nostru
scrisoare sa schimbat, nu?

372
00:16:02,575 --> 00:16:05,150
Este acum un E, așa cum ar trebui să fie.

373
00:16:05,150 --> 00:16:07,360
Astfel, putem continua mai departe.

374
00:16:07,360 --> 00:16:08,500
>> Și avem această verificare.

375
00:16:08,500 --> 00:16:09,916
Iar această verificare ar trebui să lucreze, nu?

376
00:16:09,916 --> 00:16:12,570
E A. Ar fi schimbată
trei litere înainte.

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

378
00:16:14,320 --> 00:16:16,530
Dar, dacă observați, noi
a obține ceva diferit.

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

380
00:16:17,580 --> 00:16:22,860
Deci, în acest caz aici, a prins-
ea, și așa mai departe această linie executat,

381
00:16:22,860 --> 00:16:28,620
care a modificat nostru B.
Dar, în acest caz aici,

382
00:16:28,620 --> 00:16:32,860
avem că doar o omit,
și a mers la [? L Siff. ?]

383
00:16:32,860 --> 00:16:34,660
Deci, ceva se întâmplă acolo.

384
00:16:34,660 --> 00:16:37,780
Ceea ce îți spune este că,
știm că ar trebui să prind aici,

385
00:16:37,780 --> 00:16:39,200
dar nu este.

386
00:16:39,200 --> 00:16:42,210
Poate cineva sa vezi ce noastre
problemă este aceea că linia?

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

388
00:16:45,380 --> 00:16:46,969
Este un lucru foarte minut.

389
00:16:46,969 --> 00:16:48,510
Și ai putea uita, de asemenea, la codul.

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

391
00:16:49,980 --> 00:16:54,940
Este, de asemenea line-- uita ce linia este
în there-- dar se află într-[neauzit].

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

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: E pe cea mai mare decât
pagina dacă l-ai citit în carte.

394
00:16:58,639 --> 00:16:59,430
SPEAKER 1: Exact.

395
00:16:59,430 --> 00:17:02,620
Așa că, debugger nu a putut spune
tu asta, dar debugger

396
00:17:02,620 --> 00:17:05,880
ai putea să trecem la o linie
care știți că nu funcționează.

397
00:17:05,880 --> 00:17:09,319
Și, uneori, când mai ales
mai târziu, în semestrului, atunci când

398
00:17:09,319 --> 00:17:12,910
ai de a face cu o sută, o
sute de câteva linii de cod, și te

399
00:17:12,910 --> 00:17:16,190
Nu știu unde e lipsa,
aceasta este o modalitate foarte bună de a face acest lucru.

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

401
00:17:17,900 --> 00:17:18,989
Așa că, am găsit bug nostru.

402
00:17:18,989 --> 00:17:21,530
Puteți să-l repara în fișierul dvs.,
și apoi ai putea rula din nou,

403
00:17:21,530 --> 00:17:23,029
și totul va funcționa perfect.

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

405
00:17:24,970 --> 00:17:30,590
Și cel mai important lucru este
acest lucru poate parea, OK.

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

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

408
00:17:31,370 --> 00:17:32,744
Ai știut ceea ce căutați.

409
00:17:32,744 --> 00:17:34,910
Așa că, ai știut ce să facă.

410
00:17:34,910 --> 00:17:39,021
>> GDB poate fi foarte util pentru că
poate imprima toate aceste lucruri pe care le

411
00:17:39,021 --> 00:17:39,520
nu ar fi.

412
00:17:39,520 --> 00:17:41,160
Este mult mai util decât printf.

413
00:17:41,160 --> 00:17:43,440
Câți dintre voi folosiți
cum ar fi declarațiile printf

414
00:17:43,440 --> 00:17:46,200
pentru a descoperi în cazul în care un bug a fost, nu?

415
00:17:46,200 --> 00:17:48,450
Așa că, cu acest lucru, tu nu faci
Trebuie să continui înapoi,

416
00:17:48,450 --> 00:17:51,139
și ca comentând în
Printf, sau comentarea,

417
00:17:51,139 --> 00:17:52,930
și dau seama ce
ar trebui să fie de imprimare.

418
00:17:52,930 --> 00:17:55,670
Acest fapt, doar vă permite să
pas prin, imprima lucruri

419
00:17:55,670 --> 00:18:00,000
cum ai de gând prin, așa, puteți
observa cum se schimbă în timp real,

420
00:18:00,000 --> 00:18:02,190
ca programul se execută.

421
00:18:02,190 --> 00:18:04,390
>> Și aceasta nu ia un pic
bit de a fi utilizate pentru a.

422
00:18:04,390 --> 00:18:07,850
Mi-ar recomanda foarte doar un fel
de a fi un pic frustrat cu ea

423
00:18:07,850 --> 00:18:08,930
pentru chiar acum.

424
00:18:08,930 --> 00:18:13,450
Daca petreci o oră de-a lungul
săptămâna viitoare a învăța cum să folosească GDB,

425
00:18:13,450 --> 00:18:16,140
te va salva
atât de mult timp mai târziu.

426
00:18:16,140 --> 00:18:18,750
Și literalmente. noi spunem
acest oamenilor în fiecare an,

427
00:18:18,750 --> 00:18:23,890
și Îmi amintesc când am luat
clasă, am fost ca, voi fi bine.

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

429
00:18:24,700 --> 00:18:27,030
PSET 6 intrat în și am fost
cum ar fi, am să învețe

430
00:18:27,030 --> 00:18:29,500
modul de utilizare a GDB pentru că eu nu fac
știu ce se întâmplă pe aici.

431
00:18:29,500 --> 00:18:32,940
>> Deci, dacă vă faceți timp pentru așa
să-l utilizați pe programe mai mici

432
00:18:32,940 --> 00:18:35,697
care ai de gând să fie
de lucru pe, cum ar fi de lucru

433
00:18:35,697 --> 00:18:37,530
prin ceva de genul
Visionare, cum ar fi aceasta.

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

435
00:18:38,800 --> 00:18:42,850
Sau, dacă vrei practică în plus, sunt sigur
Aș putea veni cu programe de buggy,

436
00:18:42,850 --> 00:18:45,300
pentru tine de a depana dacă doriți.

437
00:18:45,300 --> 00:18:49,300
>> Dar dacă luați doar ceva timp pentru a obține
obișnuiești cu el, juca doar în jurul valorii de cu ea,

438
00:18:49,300 --> 00:18:50,550
ea va servi foarte bine.

439
00:18:50,550 --> 00:18:52,591
Și este într-adevăr una dintre
acele lucruri pe care le pur și simplu

440
00:18:52,591 --> 00:18:57,340
trebuie să încerci, și ia-ți mâinile murdare
cu, înainte de a vă într-adevăr înțeles.

441
00:18:57,340 --> 00:19:02,090
Am într-adevăr doar înțeles dată
Am avut de a depana lucruri cu ea,

442
00:19:02,090 --> 00:19:08,170
și este mult mai plăcut de a avea o idee de
cum de a depana mai devreme, mai degrabă decât mai târziu.

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

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

445
00:19:09,625 --> 00:19:12,960
Știu că e un fel de
un curs intensiv în GDB,

446
00:19:12,960 --> 00:19:16,400
și voi lucra cu siguranta pe asistent
acestea să se uite mai mari data viitoare.

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

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

449
00:19:18,280 --> 00:19:20,390
>> Așa că, dacă ne întoarcem la PowerPoint nostru.

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

451
00:19:27,194 --> 00:19:28,110
Se întâmplă acest lucru la locul de muncă?

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
AWH.

454
00:19:30,210 --> 00:19:31,101
Da.

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

456
00:19:31,600 --> 00:19:35,480
Așa că, dacă ai nevoie vreodată de
cei din nou, nu e pe lista.

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

458
00:19:37,160 --> 00:19:40,830
Căutare așa binară, care toată lumea
își amintește mare spectacol a lui David

459
00:19:40,830 --> 00:19:42,259
ripping cărți de telefon în jumătate.

460
00:19:42,259 --> 00:19:44,050
Eu nu obține cu adevărat
anymore cărți de telefon,

461
00:19:44,050 --> 00:19:46,530
pentru că așa cum în cazul în care faci
a obține cărți de telefon în aceste zile?

462
00:19:46,530 --> 00:19:48,220
Eu chiar nu știu.

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

464
00:19:49,840 --> 00:19:50,590
Binary căutare.

465
00:19:50,590 --> 00:19:52,464
Are cineva aminte
cum binare lucrări de cautare?

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

467
00:19:54,380 --> 00:19:55,220
Oricine la toate?

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

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Știi când
te uiti la care jumătate

470
00:19:58,283 --> 00:20:01,146
ar fi în, Bazat pe faptul că,
și a scăpa de cealaltă jumătate.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Exact.

472
00:20:01,896 --> 00:20:06,290
Așa că, căutare binară, e un fel de un--
--we place să numim diviza și cuceri.

473
00:20:06,290 --> 00:20:09,170
Deci, ce vei face este
te vei uita la mijloc,

474
00:20:09,170 --> 00:20:11,990
și veți vedea dacă se potrivește
ceea ce căutați.

475
00:20:11,990 --> 00:20:15,420
Și dacă nu o face, atunci când încercați să
da seama, așa va fi lăsat

476
00:20:15,420 --> 00:20:16,450
jumătate sau jumătatea din dreapta.

477
00:20:16,450 --> 00:20:19,325
Așa că, acest lucru ar putea fi dacă sunteți în căutarea
la ceva care este alfabetic,

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

479
00:20:20,720 --> 00:20:22,750
Are Allison veni în fața M?

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

481
00:20:23,250 --> 00:20:25,030
Așa că, vom
uita-te la prima jumătate a anului.

482
00:20:25,030 --> 00:20:26,450
>> Sau ar putea fi ca cu numere.

483
00:20:26,450 --> 00:20:28,830
Orice lucru care puteți
compara, acesta poate fi sortate.

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

485
00:20:29,920 --> 00:20:31,260
Puteți utiliza căutare binar pe.

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

487
00:20:32,340 --> 00:20:37,455
Așa că, oricine amintiți-vă acest
grafic sau ce e asta?

488
00:20:37,455 --> 00:20:39,520
E Complexitatea asimptotice.

489
00:20:39,520 --> 00:20:42,830
Astfel, acest grafic doar
descrie cât de mult

490
00:20:42,830 --> 00:20:46,230
te duce pentru a rezolva o problemă cât mai
vă crește numărul de lucruri

491
00:20:46,230 --> 00:20:47,090
pe care îl utilizați.

492
00:20:47,090 --> 00:20:51,260
>> Deci, avem N, care este timpul liniar.

493
00:20:51,260 --> 00:20:54,560
Dacă N peste doi, care este ușor
mai bine, încă se dezvoltă foarte rapid.

494
00:20:54,560 --> 00:20:58,360
Și apoi ne-am Autentifică-te, ceea ce este
ceea ce noi considerăm de căutare binară.

495
00:20:58,360 --> 00:21:03,630
Dacă observăm, ca problema ta
devine mult și mult mai mare,

496
00:21:03,630 --> 00:21:06,600
în momentul în care ai nevoie pentru a rezolva
nu reprezintă cu adevărat crește atât de mult.

497
00:21:06,600 --> 00:21:09,010
E ca și cum comparabil
aici, la început.

498
00:21:09,010 --> 00:21:10,060
Ești ca, OK.

499
00:21:10,060 --> 00:21:13,000
Nimic aici nu prea
Indiferent care o vom folosi,

500
00:21:13,000 --> 00:21:16,220
dar tu ieși la un milion, un miliard.

501
00:21:16,220 --> 00:21:20,010
Sunteți încercarea de a găsi some-- --you're
încercarea de a găsi un ac în carul cu fân.

502
00:21:20,010 --> 00:21:21,550
>> Cred că vrei această problemă.

503
00:21:21,550 --> 00:21:25,850
Vrei această complexitate, nu
liniară pentru că pentru tot ce ai

504
00:21:25,850 --> 00:21:30,049
stiti voi tău trebuie să căutați prin
fiecare ac individ, lucru de fân,

505
00:21:30,049 --> 00:21:31,340
încercând să uite pentru ac dumneavoastră.

506
00:21:31,340 --> 00:21:34,730
Și asta nu e prea distractiv, în opinia mea.

507
00:21:34,730 --> 00:21:35,500
Îmi place repede.

508
00:21:35,500 --> 00:21:36,620
Îmi place eficient.

509
00:21:36,620 --> 00:21:40,450
Și studenți în calitate de harnici te
Voi sunteți, știți lucreze mai inteligent,

510
00:21:40,450 --> 00:21:43,010
nu mai greu lucru de tip, cum ai
pot face acești algoritmi.

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

512
00:21:45,110 --> 00:21:47,910
>> Deci, noi vom umbla
prin intermediul doar un exemplu rapid.

513
00:21:47,910 --> 00:21:51,090
Cred că voi ar trebui să aibă
o mână pe Căutare binară,

514
00:21:51,090 --> 00:21:54,352
dar în cazul în care cineva este un pic
neclare, să-l consolideze,

515
00:21:54,352 --> 00:21:56,310
vom merge doar
printr-un exemplu aici.

516
00:21:56,310 --> 00:21:59,490
Așa că, căutăm în cazul în care
matrice conține șapte.

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

518
00:22:00,540 --> 00:22:06,010
>> Așa că, primul lucru ce facem este
uita-te la mijloc, nu?

519
00:22:06,010 --> 00:22:09,340
Și, de asemenea, ai de gând să fie de codificare
Cauta binar în doar o secundă.

520
00:22:09,340 --> 00:22:11,310
Așa că, o să fie distractiv.

521
00:22:11,310 --> 00:22:13,710
Așa că ne uităm în
tablouri mici de mijloc 3.

522
00:22:13,710 --> 00:22:15,501
Are 3 egală cu 7?

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

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

525
00:22:18,670 --> 00:22:19,550
E de șase.

526
00:22:19,550 --> 00:22:21,480
Deci, este mai mică de
sau mai mare de șapte?

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

528
00:22:23,080 --> 00:22:23,960
Mai puțin de.

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

530
00:22:24,570 --> 00:22:25,170
Baieti de locuri de muncă frumos.

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

532
00:22:25,569 --> 00:22:27,360
Simt Îmi place că ar trebui
Trebuie bomboane pentru că am

533
00:22:27,360 --> 00:22:29,460
doriți să-l arunce în șantierele.

534
00:22:29,460 --> 00:22:30,270
E ceea ce am de gând să fac săptămâna viitoare.

535
00:22:30,270 --> 00:22:31,436
Acesta vă va ține băieți ascuțite.

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

537
00:22:32,560 --> 00:22:34,690
>> Așa că, ne-am arunca că
prima repriză, nu?

538
00:22:34,690 --> 00:22:35,670
a fost mai mică.

539
00:22:35,670 --> 00:22:39,325
știm că tot
pe care stanga

540
00:22:39,325 --> 00:22:41,700
va fi mai mică decât ceea ce
suntem de fapt în căutarea pentru.

541
00:22:41,700 --> 00:22:43,491
Deci, nu este nevoie să
acorde o atenție la ea.

542
00:22:43,491 --> 00:22:45,120
Doar uita despre asta.

543
00:22:45,120 --> 00:22:48,720
Deci, acum ne uităm la partea noastră dreaptă,
și ne uităm la mijloc acolo,

544
00:22:48,720 --> 00:22:50,510
iar acum e nouă.

545
00:22:50,510 --> 00:22:55,510
Astfel, 9 este-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Mai mare decât ceea ce suntem
cautati, nu?

547
00:22:57,470 --> 00:22:59,860
Așa că, vom arunca
departe tot la dreapta.

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

549
00:23:00,970 --> 00:23:01,940
Ca asta.

550
00:23:01,940 --> 00:23:03,700
Acum, tot ce mai rămâne cu unul.

551
00:23:03,700 --> 00:23:07,760
Așa că am verifica, este aceasta ceea ce
căutăm? ea este.

552
00:23:07,760 --> 00:23:08,970
S-au găsit ceea ce ne-am dorit.

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

554
00:23:10,440 --> 00:23:11,690
Deci, am terminat.

555
00:23:11,690 --> 00:23:12,550
Biliniare de căutare.

556
00:23:12,550 --> 00:23:15,740
>> Și dacă observați, noi
a avut șapte intrări acolo.

557
00:23:15,740 --> 00:23:24,320
Ea doar ne-a luat ca de trei ori,
dar dacă faci ca un miliarde de euro,

558
00:23:24,320 --> 00:23:28,190
voi ști câți pași ca ar fi
ia dacă am fi avut patru miliarde de lucruri?

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

560
00:23:29,940 --> 00:23:30,455
Orice presupuneri?

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

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

563
00:23:33,960 --> 00:23:37,110
32 pași pentru a găsi ceva
într-o patru miliarde

564
00:23:37,110 --> 00:23:39,650
element de matrice din cauza puteri de două.

565
00:23:39,650 --> 00:23:43,550
Deci doi este la 32, este la patru miliarde.

566
00:23:43,550 --> 00:23:50,430
>> Cum așa destul de nebun ești încă în
ca un număr destul de mic de etape

567
00:23:50,430 --> 00:23:52,650
pentru a găsi ceva în
patru miliarde de elemente.

568
00:23:52,650 --> 00:23:55,730
Deci, pe această notă, suntem
O să codul această

569
00:23:55,730 --> 00:23:58,950
astfel voi putea de fapt
un fel de a vedea cum functioneaza aceasta.

570
00:23:58,950 --> 00:24:01,520
Bine, deci voi putea cod.

571
00:24:01,520 --> 00:24:04,100
Am de gând să vă voi lăsa
vorbim de un pic.

572
00:24:04,100 --> 00:24:07,970
Ia să știu de oameni din jurul tau, care este
ceea ce cineva a vrut de la ultima secțiune.

573
00:24:07,970 --> 00:24:10,280
>> Deci, ajunge să cunoască oamenii din jurul tău.

574
00:24:10,280 --> 00:24:11,305
Vorbesc pentru un pic.

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

576
00:24:12,580 --> 00:24:15,730
Si tot ce vreau de la tine
baieti acum este doar

577
00:24:15,730 --> 00:24:17,575
încercați să creați o schiță de pseudocod.

578
00:24:17,575 --> 00:24:18,075
OK?

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
Whoa.

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

582
00:24:23,320 --> 00:24:29,520
Tot ce vreau de la voi este că ești
doar de gând să completați în acest caz în timp ce.

583
00:24:29,520 --> 00:24:32,170
Deci, am stabilit aceste superioară
și limite inferioare care

584
00:24:32,170 --> 00:24:35,250
reprezintă începutul
și la sfârșitul de oferta noastră.

585
00:24:35,250 --> 00:24:40,440
Și aveți de gând să efectiv
bucla prin și dau seama

586
00:24:40,440 --> 00:24:42,470
ceea ce facem noi în această buclă în timp ce.

587
00:24:42,470 --> 00:24:45,810
>> Deci, dacă vă puteți da seama out-- am
un indiciu there-- care sunt cazurile

588
00:24:45,810 --> 00:24:46,640
pe care le avem aici?

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

590
00:24:48,100 --> 00:24:51,560
Deci, dacă doriți să dau seama
de cazuri, vom pseudocod cele

591
00:24:51,560 --> 00:24:53,350
și apoi le vom cod de fapt.

592
00:24:53,350 --> 00:24:55,330
Și aceasta va fi, eu
cred, să sperăm că va

593
00:24:55,330 --> 00:24:56,788
fi un pic mai ușor decât vă așteptați.

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

595
00:24:57,554 --> 00:25:00,220
Pentru că nu e atât de mult cod,
de fapt, ceea ce este foarte cool.

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> Mm-hm?

598
00:25:35,018 --> 00:25:35,893
>> STUDENT: [inaudibil]?

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

600
00:25:36,984 --> 00:25:37,650
INSTRUCTOR: Da.

601
00:25:37,650 --> 00:25:38,595
Nu a fost ceva
pentru a găsi în mijloc.

602
00:25:38,595 --> 00:25:39,552
>> STUDENT: Deci, putem folosi asta.

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

604
00:25:39,770 --> 00:25:40,603
>> INSTRUCTOR: Perfect.

605
00:25:40,603 --> 00:25:42,950
Deci, asta e primul lucru pe care trebuie să facem.

606
00:25:42,950 --> 00:25:44,330
Deci, găsi pe centru.

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

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

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

610
00:25:47,770 --> 00:25:55,010
Deci, ai o idee despre cum am putea
afla de fapt la mijloc cu codul?

611
00:25:55,010 --> 00:25:55,980
>> STUDENT: Da.

612
00:25:55,980 --> 00:25:57,000
n peste 2?

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
INSTRUCTOR: Deci, n peste 2.

615
00:25:59,500 --> 00:26:05,170
Deci, un lucru de reținut este faptul că
dvs. de limite superioare și inferioare se schimbe.

616
00:26:05,170 --> 00:26:08,110
Noi mereu constrictia partea
de matrice suntem în căutarea de a.

617
00:26:08,110 --> 00:26:11,970
Deci, n peste 2 va funcționa numai
pentru primul lucru pe care îl facem.

618
00:26:11,970 --> 00:26:17,810
Deci, luând superioara si inferioara în considerare,
cum am putea obține acest element de mijloc?

619
00:26:17,810 --> 00:26:20,640
Pentru ca vrem pe centru
între superior și inferior, dreapta?

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
Mm-hm?

622
00:26:22,494 --> 00:26:23,369
>> STUDENT: [inaudibil].

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

624
00:26:26,170 --> 00:26:28,080
>> INSTRUCTOR: Deci avem ceva de mijloc.

625
00:26:28,080 --> 00:26:32,730
Și va fi superioară plus de jos peste 2.

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

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

628
00:26:35,690 --> 00:26:36,570
Acolo mergem.

629
00:26:36,570 --> 00:26:37,280
O linie în jos.

630
00:26:37,280 --> 00:26:38,560
Sunteți pe drumul tau.

631
00:26:38,560 --> 00:26:41,400
Deci, acum că ne-am nostru
de mijloc, ce vrem să facem?

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

633
00:26:45,050 --> 00:26:45,900
Doar în general.

634
00:26:45,900 --> 00:26:47,734
Nu trebuie să-l cod.

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

636
00:26:48,335 --> 00:26:49,210
STUDENT: [inaudibil]?

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

638
00:27:00,310 --> 00:27:10,310
INSTRUCTOR: Deci e plus pentru că ești
găsirea media între cele două

639
00:27:10,310 --> 00:27:10,810
dintre acestea.

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

641
00:27:11,890 --> 00:27:17,370
Deci, dacă vă gândiți la ele ca natură
de creștere de pe părțile laterale,

642
00:27:17,370 --> 00:27:21,640
gândiți-vă cum vă apropiați
mijloc, vrei ca asta.

643
00:27:21,640 --> 00:27:27,150
Deci, dacă ai fost pe fiecare parte a
de mijloc, și avem ca 5 și 7.

644
00:27:27,150 --> 00:27:31,440
Atunci când le adăugați împreună tine
primi 12, împărțiți de 2, este de 6.

645
00:27:31,440 --> 00:27:33,726
>> Uneori este greu să
explica de ce functioneaza,

646
00:27:33,726 --> 00:27:35,600
dar dacă lucrați prin
un exemplu uneori,

647
00:27:35,600 --> 00:27:37,962
aceasta va ajuta să îți dai seama dacă
ar trebui să fie de plus sau minus.

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

649
00:27:38,846 --> 00:27:40,830
>> STUDENT: [inaudibil]
exact în mijloc

650
00:27:40,830 --> 00:27:43,950
dacă au avut un caz în care
există o mulțime de numere mai mici

651
00:27:43,950 --> 00:27:45,860
și ca un număr mare?

652
00:27:45,860 --> 00:27:49,750
>> INSTRUCTOR: Deci, tot ce ai nevoie
este mijlocul matrice.

653
00:27:49,750 --> 00:27:53,010
Deci, dacă ați avut o grămadă de numere mici
și apoi un număr cu adevărat mare

654
00:27:53,010 --> 00:27:54,799
la sfârșitul anului, nu contează.

655
00:27:54,799 --> 00:27:56,840
Tot ce contează e că
acestea sunt sortate, doar

656
00:27:56,840 --> 00:27:59,339
vrea să se uite la mijlocul
matrice pentru că ești încă

657
00:27:59,339 --> 00:28:00,700
retezarea problema în jumătate.

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

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

660
00:28:03,680 --> 00:28:06,430
Deci, acum că avem
de mijloc, ce facem mai departe?

661
00:28:06,430 --> 00:28:07,150
>> STUDENT: Compara.

662
00:28:07,150 --> 00:28:08,150
INSTRUCTOR: comparare.

663
00:28:08,150 --> 00:28:11,670
Deci, compara mijloc de value_wanted.

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

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

666
00:28:15,160 --> 00:28:17,950
Deci, vedeți aici avem
această valoare vrem aici.

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

668
00:28:22,012 --> 00:28:23,095
Amintiți-vă acest lucru este un tablou.

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

670
00:28:24,100 --> 00:28:26,970
Deci mijloc se referă la indicele.

671
00:28:26,970 --> 00:28:29,785
Așa că vrem să facem valori de mijloc.

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

673
00:28:32,380 --> 00:28:35,650
Nu uita, dacă doriți
pentru a compara, egali duble.

674
00:28:35,650 --> 00:28:38,250
Tu faci egal singur ești
doar de gând să le retrocedeze,

675
00:28:38,250 --> 00:28:41,090
și apoi, desigur, e
va fi valoarea dorită.

676
00:28:41,090 --> 00:28:42,300
Deci, nu face asta.

677
00:28:42,300 --> 00:28:44,350
>> Deci, vom vedea dacă
la valori, la mijloc

678
00:28:44,350 --> 00:28:46,460
este egal cu valoarea ne-o dorim.

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

680
00:28:47,749 --> 00:28:48,790
Nu uita aparatul dentar.

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

682
00:28:50,520 --> 00:28:52,235
Dropbox ar trebui să plece.

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

684
00:28:54,140 --> 00:28:56,200
Deci, ce facem in acest caz?

685
00:28:56,200 --> 00:28:59,360
Dacă e ceea ce vrem să se întoarcă?

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

687
00:29:01,510 --> 00:29:02,626
Încercăm să spun.

688
00:29:02,626 --> 00:29:03,440
>> STUDENT: Printeaza off.

689
00:29:03,440 --> 00:29:05,314
>> INSTRUCTOR: Ei bine, ne-am
Nu doriți să imprimați off.

690
00:29:05,314 --> 00:29:08,220
Deci, aceasta este o bool aici, așa că am
doresc să se întoarcă adevărat sau fals.

691
00:29:08,220 --> 00:29:12,280
Noi spunem, este acest număr
o [? RRA? ?] Deci, dacă aceasta este,

692
00:29:12,280 --> 00:29:13,788
ne-am întoarce adevărat.

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

694
00:29:16,780 --> 00:29:17,760
Dacă aș putea scrie adevărat.

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

696
00:29:18,830 --> 00:29:20,805
>> STUDENT: De ce nu te-ai întoarce la zero?

697
00:29:20,805 --> 00:29:22,930
INSTRUCTOR: Deci, ai putea
a reveni zero, dacă vrei.

698
00:29:22,930 --> 00:29:26,780
Dar, în acest caz, deoarece
Funcția noastră returnează un bool,

699
00:29:26,780 --> 00:29:28,962
avem nevoie pentru a reveni fie adevărat sau fals.

700
00:29:28,962 --> 00:29:30,920
STUDENT: Când ești
spunând expresie boolean,

701
00:29:30,920 --> 00:29:33,450
poți seta egală cu false?

702
00:29:33,450 --> 00:29:39,860
Ca și cum dacă vreau să spun, în cazul în care această condiție
nu este îndeplinită, așa cum este superior este egal fals.

703
00:29:39,860 --> 00:29:42,332
Va înțelege dacă doar
a pus false pe de altă parte?

704
00:29:42,332 --> 00:29:43,040
INSTRUCTOR: Da.

705
00:29:43,040 --> 00:29:44,820
Deci, de fapt, dacă sunteți
vreodată să faci ceva

706
00:29:44,820 --> 00:29:49,600
ca este superior sau este mai mică,
care returnează adevărat sau fals

707
00:29:49,600 --> 00:29:53,850
și e stilul de fapt rău pentru
să zicem egal este egal cu adevărat sau egali

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

709
00:29:54,840 --> 00:30:00,210
Doriți să utilizați acest rezultat
la fel de sine ca cecul.

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

711
00:30:04,720 --> 00:30:05,860
Nu ceea ce am vrut.

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

713
00:30:08,150 --> 00:30:09,240
Asta e ceea ce am vrut.

714
00:30:09,240 --> 00:30:13,205
Deci, în cazul ceri
despre ceva de genul salva aceasta în c.

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

716
00:30:16,320 --> 00:30:25,150
>> Deci, dacă avem int main (void)
și ceva de genul asta.

717
00:30:25,150 --> 00:30:31,922
Și aveți dacă este superioară
de unele de intrare și ești

718
00:30:31,922 --> 00:30:33,630
întreabă dacă poți să faci
ceva de genul asta?

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

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

721
00:30:35,679 --> 00:30:37,470
STUDENT: Am încercat
pentru a face o [inaudibil].

722
00:30:37,470 --> 00:30:38,450
Pentru că dacă it's--

723
00:30:38,450 --> 00:30:39,200
INSTRUCTOR: Corect.

724
00:30:39,200 --> 00:30:41,197
Deci vrei ca acest lucru să fie fals, nu?

725
00:30:41,197 --> 00:30:41,780
STUDENT: Da.

726
00:30:41,780 --> 00:30:45,960
INSTRUCTOR: Deci, în acest caz,
doriți să-l execute, dacă nu e adevărat.

727
00:30:45,960 --> 00:30:50,510
Deci, cool thing faci este acest lucru.

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

729
00:30:52,900 --> 00:30:55,650
Deci, amintiți-vă de exclamare
Punct neagă lucrurile?

730
00:30:55,650 --> 00:30:58,270
Se spune [inaudibil] nu înseamnă.

731
00:30:58,270 --> 00:31:03,590
Deci, dacă ne uităm la doar
această parte aici, ai fi

732
00:31:03,590 --> 00:31:05,740
spun că se evaluează la
fals așa cum doriți să.

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

734
00:31:06,790 --> 00:31:09,880
Nu fals este adevărat ceea ce
înseamnă acest lucru ar executa.

735
00:31:09,880 --> 00:31:11,037
Asta face sens?

736
00:31:11,037 --> 00:31:11,620
STUDENT: Da.

737
00:31:11,620 --> 00:31:12,453
INSTRUCTOR: Awesome.

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
OK.

740
00:31:14,300 --> 00:31:16,330
Deci, am putea reveni pur și simplu
adevărat în acest caz.

741
00:31:16,330 --> 00:31:20,357
Deci, acum avem alte două
cazuri în acest caz.

742
00:31:20,357 --> 00:31:21,565
Care sunt celelalte două cazuri noastre?

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

744
00:31:31,610 --> 00:31:32,900
Să-l în acest fel face.

745
00:31:32,900 --> 00:31:40,660
Așa că haideți să începem cu altceva
dacă valorile de la centru

746
00:31:40,660 --> 00:31:43,230
este mai mică decât valoarea ne-o dorim.

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

748
00:31:47,200 --> 00:31:52,020
Deci, valoarea noastră în mijloc este mai puțin
decât valoarea pe care-l căutăm.

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

750
00:31:53,765 --> 00:31:56,720
>> Deci, care leagă nu-
cred ca ne-o dorim pentru a actualiza?

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

752
00:31:57,870 --> 00:31:58,780
Superior sau inferior?

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

754
00:32:01,440 --> 00:32:01,940
De sus?

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

756
00:32:03,230 --> 00:32:06,470
Deci, care parte a șirului
vom fi uitat la?

757
00:32:06,470 --> 00:32:07,500
>> STUDENT: mai mică.

758
00:32:07,500 --> 00:32:09,750
>> INSTRUCTOR: Noi mergem
să fi uitat la stânga.

759
00:32:09,750 --> 00:32:11,120
Deci, dacă mai mică valoare este mai mică.

760
00:32:11,120 --> 00:32:14,730
Deci, valoarea ta de mijloc aici
este mai mică decât ceea ce ne dorim.

761
00:32:14,730 --> 00:32:17,202
Așa că ne-am dori să ia
partea dreapta a oferta noastră.

762
00:32:17,202 --> 00:32:18,910
Așa că am de gând să
actualiza legat nostru mai mic.

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

764
00:32:20,210 --> 00:32:23,020
Deci, vom realocați mai jos noastre.

765
00:32:23,020 --> 00:32:25,221
Și ce crezi că ar trebui să fie mai mic?

766
00:32:25,221 --> 00:32:26,304
STUDENT: valoarea de mijloc?

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

768
00:32:27,446 --> 00:32:28,820
INSTRUCTOR: Deci value-- de mijloc

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

770
00:32:30,136 --> 00:32:31,010
INSTRUCTOR: --plus 1.

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

772
00:32:32,300 --> 00:32:34,380
Poate cineva sa-mi spui de ce
avem că plus 1?

773
00:32:34,380 --> 00:32:35,730
>> STUDENT: [? Nici o valoare?]
este mai mult egală cu ea.

774
00:32:35,730 --> 00:32:36,120
>> INSTRUCTOR: Corect.

775
00:32:36,120 --> 00:32:38,661
Pentru că știm deja că
Valoarea noastră de mijloc nu este egal cu

776
00:32:38,661 --> 00:32:42,750
ea și vrem să-l excludă
din toate căutările ulterioare.

777
00:32:42,750 --> 00:32:46,360
Dacă uitați că plus 1, acest
va place buclă pe termen nelimitat.

778
00:32:46,360 --> 00:32:49,620
Și veți fi doar prins într-o
buclă infinită și apoi veți segfault

779
00:32:49,620 --> 00:32:50,370
și lucrurile merg prost.

780
00:32:50,370 --> 00:32:54,780
Deci, întotdeauna asigurați-vă că nu ești
inclusiv valoarea pe care tocmai ați

781
00:32:54,780 --> 00:32:55,380
sa uitat la.

782
00:32:55,380 --> 00:32:58,530
Așa că am grijă de asta cu un plus de 1.

783
00:32:58,530 --> 00:33:04,840
>> Deci, acum avem ultima noastră condiție
pe care am mereu pentru mai multă siguranță

784
00:33:04,840 --> 00:33:12,664
puteți verifica aici, altfel daca valoarea la
la mijloc este mai mare decât valoarea

785
00:33:12,664 --> 00:33:13,163
ne-o dorim.

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

787
00:33:16,260 --> 00:33:20,230
Asta înseamnă că ne-o dorim
jumătatea din stânga.

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

789
00:33:21,350 --> 00:33:23,260
Deci, pe care o vom actualiza?

790
00:33:23,260 --> 00:33:23,760
De sus.

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

792
00:33:25,470 --> 00:33:26,970
Și ce este aceasta o va egala?

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

794
00:33:31,630 --> 00:33:33,690
Orientul Mijlociu minus 1, deoarece,
Desigur, ne dorim

795
00:33:33,690 --> 00:33:38,370
pentru a vă asigura că nu suntem
cauta la valoarea de mijloc din nou.

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

797
00:33:41,830 --> 00:33:45,110
Și apoi îl avem.

798
00:33:45,110 --> 00:33:45,610
Asta e tot.

799
00:33:45,610 --> 00:33:46,820
Asta e tot binar de căutare este.

800
00:33:46,820 --> 00:33:48,190
Nu e așa de rău, nu?

801
00:33:48,190 --> 00:33:51,590
E ca și cum 10 de linii de
cod cu spațiu alb.

802
00:33:51,590 --> 00:33:57,510
Deci, foarte puternic, foarte util, vă va fi,
fie folosind-o într-una din psets mai târziu.

803
00:33:57,510 --> 00:33:59,360
Poate că acest lucru nu unul, ci mai târziu.

804
00:33:59,360 --> 00:34:00,670
Deci, să învețe.

805
00:34:00,670 --> 00:34:01,510
Place.

806
00:34:01,510 --> 00:34:02,980
Acesta vă va trata bine.

807
00:34:02,980 --> 00:34:05,370
Deci, are cineva vreo
întrebări cu privire căutare binar?

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

809
00:34:06,196 --> 00:34:09,840
>> STUDENT: Contează
dacă n este par sau impar?

810
00:34:09,840 --> 00:34:10,750
>> INSTRUCTOR: Nu.

811
00:34:10,750 --> 00:34:18,150
Pentru că l-am aruncat la mijloc ca
un int, aceasta se va trunchia doar.

812
00:34:18,150 --> 00:34:21,600
Deci, acesta va rămâne un număr întreg și se va
în cele din urmă a sorta prin toate.

813
00:34:21,600 --> 00:34:23,909
Deci, nu trebuie să vă faceți griji cu privire la asta.

814
00:34:23,909 --> 00:34:24,580
Toată lumea bine?

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

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

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

818
00:34:27,919 --> 00:34:30,836
Așa că, voi reușit acest lucru.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Slideshow.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Deci, ca am vorbit despre, știu
David a menționat runtime complexitate.

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

824
00:34:44,420 --> 00:34:50,340
>> Deci, în cel mai bun caz, e doar
unul, pe care o numim timp constant.

825
00:34:50,340 --> 00:34:51,909
Poate cineva sa-mi spui de ce ar putea fi?

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

827
00:34:52,969 --> 00:34:55,800
Ce tip de scenariu ar presupune asta?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> STUDENT: [inaudibil] first--

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

832
00:35:00,789 --> 00:35:03,830
INSTRUCTOR: Deci, centru fiind
prim element care am ajuns, nu?

833
00:35:03,830 --> 00:35:08,167
Deci, fie o serie de una sau
indiferent de căutăm doar

834
00:35:08,167 --> 00:35:09,750
se întâmplă să fie tamponare jart în mijloc.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Deci, asta e cel mai bine cazul nostru.

837
00:35:13,380 --> 00:35:17,540
Tu nu intrăm în probleme reale, probabil,
O să ajungă la [inaudibil] care de multe ori.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Ce despre cel mai rău caz nostru?

840
00:35:19,750 --> 00:35:21,270
Cel mai rău caz noastra este log n.

841
00:35:21,270 --> 00:35:25,360
Și care are de a face cu întregul
competențe de două lucru pe care am vorbit despre.

842
00:35:25,360 --> 00:35:30,930
>> Deci, în cel mai rău caz ar însemna
care a trebuit să taie matrice jos

843
00:35:30,930 --> 00:35:33,270
până când a fost un element de una.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Așa că a trebuit să-l taie în jumătate
de câte ori este posibil, am putut.

846
00:35:38,930 --> 00:35:41,430
De aceea e log n că
doar vă păstrați împărțirea la doi.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Deci ipoteze, lucruri pe care le
Trebuie să știu dacă ești vreodată

849
00:35:45,830 --> 00:35:48,050
de gând să utilizeze un binar de căutare.

850
00:35:48,050 --> 00:35:50,680
Elementele dvs. trebuie să fie sortate.

851
00:35:50,680 --> 00:35:53,890
Ei trebuie să fie sortate, deoarece
că e singurul mod în care

852
00:35:53,890 --> 00:35:57,060
poate ști dacă sunt în măsură
să arunce jumătate din ea.

853
00:35:57,060 --> 00:36:00,260
>> Dacă ați avut acest sac amestecate
de numere și spui,

854
00:36:00,260 --> 00:36:05,380
OK, am de gând pentru a verifica mijloc
Numărul și numărul caut

855
00:36:05,380 --> 00:36:08,510
este mai mică decât atât, eu sunt doar de gând
pentru a arunca arbitrar pe jumătate.

856
00:36:08,510 --> 00:36:11,130
Tu nu ar ști dacă dumneavoastră
numere în acel celălalt pe jumătate.

857
00:36:11,130 --> 00:36:12,655
Lista dvs. trebuie să fie sortate.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
De asemenea, acest lucru poate fi
merge mai departe un pic,

860
00:36:16,560 --> 00:36:18,360
dar ai nevoie de acces aleator.

861
00:36:18,360 --> 00:36:21,940
Aveți nevoie pentru a fi în măsură să doar
du-te la acest element de mijloc.

862
00:36:21,940 --> 00:36:25,110
Dacă trebuie să traverseze
prin ceva

863
00:36:25,110 --> 00:36:28,630
sau e nevoie de tine masuri suplimentare
pentru a ajunge la acel element de mijloc,

864
00:36:28,630 --> 00:36:31,750
aceasta nu mai că log n
când adăugați mai mult de lucru în ea.

865
00:36:31,750 --> 00:36:34,800
Iar acest lucru va face un pic
mai mult sens în două săptămâni,

866
00:36:34,800 --> 00:36:37,950
dar am doar un fel de a vrut să prefața,
voi da o idee de ceea ce este

867
00:36:37,950 --> 00:36:38,999
să vină.

868
00:36:38,999 --> 00:36:40,790
Dar acestea sunt cele două
ipoteze importante

869
00:36:40,790 --> 00:36:44,804
de care aveți nevoie pentru o listă binar.

870
00:36:44,804 --> 00:36:45,720
Asigurați-vă că este sortate.

871
00:36:45,720 --> 00:36:47,920
Asta e unul mare pentru
voi chiar acum.

872
00:36:47,920 --> 00:36:52,170
Și pe care putem merge în
restul felul noastre.

873
00:36:52,170 --> 00:36:56,444
Deci, patru bule sorts--,
inserție, selecție și îmbinare.

874
00:36:56,444 --> 00:36:57,485
Sunt tot felul de rece.

875
00:36:57,485 --> 00:37:02,860
În cazul în care voi decide să ia CS 124,
veți afla despre tot felul de felul.

876
00:37:02,860 --> 00:37:07,575
Si daca esti un fan xkcd, acolo
este o cale de benzi desenate foarte misto

877
00:37:07,575 --> 00:37:11,530
cum ar fi într-adevăr felul ineficiente, pe care am
recomandăm ai de gând să se uite la.

878
00:37:11,530 --> 00:37:16,170
Una dintre ele este ca un fel de panică, care
este ca, oh nu, întoarce matrice aleatoare.

879
00:37:16,170 --> 00:37:16,991
Sistem de închidere.

880
00:37:16,991 --> 00:37:17,490
Lasă.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Deci, umor geeky este întotdeauna bun.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Deci, nimeni nu amintesc natură
ca și cum doar o idee generală

885
00:37:25,750 --> 00:37:27,810
de modul în care funcționează bule fel.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Îți amintești?

888
00:37:32,155 --> 00:37:32,755
>> STUDENT: Da.

889
00:37:32,755 --> 00:37:33,970
>> INSTRUCTOR: Du-te pentru ea.

890
00:37:33,970 --> 00:37:38,980
>> STUDENT: Deci, te duci prin și
dacă e mai mare, atunci ai swap două.

891
00:37:38,980 --> 00:37:39,820
>> INSTRUCTOR: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Exact.

893
00:37:40,564 --> 00:37:41,730
Deci, doar tu repeta prin.

894
00:37:41,730 --> 00:37:43,050
Cameră cu două numere.

895
00:37:43,050 --> 00:37:46,510
În cazul în care cea dinainte este mai mare
decât cea după aceea,

896
00:37:46,510 --> 00:37:50,230
tu doar le schimba, astfel încât în
în acest fel toate numerele mai mari

897
00:37:50,230 --> 00:37:54,990
balon până spre sfârșitul listei
și toate numerele mai mici bule jos.

898
00:37:54,990 --> 00:37:59,355
>> Te-a arăta baieti rece
efect de sunet sortare video?

899
00:37:59,355 --> 00:38:00,480
E un fel de misto.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Deci, așa cum am spus Robert, algoritmul
pe care le pas tocmai prin lista,

902
00:38:05,200 --> 00:38:07,930
schimbarea valorilor adiacente
în cazul în care nu sunt în ordine.

903
00:38:07,930 --> 00:38:10,975
Și apoi doar repeta
până când nu face nici swap-urilor.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Așa că nu-i rău, nu?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Deci, avem doar un exemplu repede aici.

908
00:38:16,319 --> 00:38:18,360
Deci, acest lucru se întâmplă pentru a sorta
le în ordine crescătoare.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Așa că atunci când trecem prin primul
timp, ne uităm prin opt

911
00:38:23,470 --> 00:38:26,880
și șase, evident, nu sunt
în ordine, le schimb.

912
00:38:26,880 --> 00:38:27,985
>> Deci, uita-te la următoarea.

913
00:38:27,985 --> 00:38:29,430
Opt și patru nu în ordine.

914
00:38:29,430 --> 00:38:30,450
A le schimba.

915
00:38:30,450 --> 00:38:32,530
Și apoi opt și doi, a le schimba.

916
00:38:32,530 --> 00:38:33,470
Acolo mergem.

917
00:38:33,470 --> 00:38:39,519
Deci, după prima trecere, tu
Știi că numărul dvs. de cea mai mare

918
00:38:39,519 --> 00:38:41,810
va fi până la capăt
la partea de sus pentru că e doar

919
00:38:41,810 --> 00:38:44,210
va fi în mod constant
mai mare decât orice altceva

920
00:38:44,210 --> 00:38:46,810
și este doar de gând să bule
tot drumul până la sfârșit acolo.

921
00:38:46,810 --> 00:38:48,226
Are care are sens pentru toată lumea?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Rece.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Deci, atunci ne uităm la a doua trecere noastră.

926
00:38:53,920 --> 00:38:54,980
Șase și patru, comutator.

927
00:38:54,980 --> 00:38:55,920
Șase și doi, comutator.

928
00:38:55,920 --> 00:38:58,700
Și acum avem câteva lucruri în ordine.

929
00:38:58,700 --> 00:39:02,240
Deci, pentru fiecare adversari pe care le
face prin întreaga listă noastra,

930
00:39:02,240 --> 00:39:06,320
știm că la fel ca că multe numere
la sfârșitul va fi fost sortate.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Așa că am făcut-o a treia trecere,
care este una de swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Și apoi pe al patrulea nostru
trece, avem de zero sloturi.

935
00:39:15,910 --> 00:39:18,570
Și așa știm că nostru
matrice a fost sortate.

936
00:39:18,570 --> 00:39:20,900
>> Și că este big
lucru cu bule fel.

937
00:39:20,900 --> 00:39:23,720
Știm că atunci când ne
au zero, swap-uri, care

938
00:39:23,720 --> 00:39:26,497
înseamnă că tot
este în ordine completă.

939
00:39:26,497 --> 00:39:27,580
E un fel de modul în care ne verifica.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Deci, suntem, de asemenea, de gând să codul bule
care sortare, de asemenea, nu este așa de rău.

942
00:39:36,480 --> 00:39:38,120
Nici unul dintre acestea sunt chiar atât de rău.

943
00:39:38,120 --> 00:39:40,210
Știu că poate părea un pic înfricoșător.

944
00:39:40,210 --> 00:39:42,124
Știu că atunci când am luat
clasa, chiar și atunci când am

945
00:39:42,124 --> 00:39:44,290
învăța clasa de
prima dată anul trecut,

946
00:39:44,290 --> 00:39:46,165
Am fost cum ar fi, cum fac asta?

947
00:39:46,165 --> 00:39:48,540
Se face sens în teorie, dar
cum facem de fapt acest lucru?

948
00:39:48,540 --> 00:39:51,420
Motiv pentru care eu, de asemenea, vreau sa merg
prin cod cu voi aici.

949
00:39:51,420 --> 00:39:54,915
Deci, am un pseudocod
pentru voi de data asta.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Deci, chiar a păstra acest lucru în minte ca
suntem pe cale de tranziție de peste.

952
00:39:58,970 --> 00:40:04,210
Deci avem ceva contra că
ține evidența operațiunilor de swap noastre,

953
00:40:04,210 --> 00:40:08,370
pentru că avem nevoie să ne asigurăm
că suntem verifica acest lucru.

954
00:40:08,370 --> 00:40:11,830
Și am repeta pentru întreaga rețea,
așa cum ne-am facut cu acest exemplu.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Dacă elementul înainte este mai mare decât
elementul după ce, unde suntem la,

957
00:40:17,325 --> 00:40:20,760
le schimba și ne-am incrementa nostru
contor pentru că de îndată ce vom schimba,

958
00:40:20,760 --> 00:40:23,850
Dorim să contra noastră știe că.

959
00:40:23,850 --> 00:40:26,247
Orice întrebări acolo?

960
00:40:26,247 --> 00:40:27,580
Ceva pare amuzant aici.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
STUDENT: Nu setați contorul la zero
de fiecare dată când trece prin bucla?

963
00:40:32,350 --> 00:40:34,339
Nu-ți continui
înapoi la zero de fiecare dată?

964
00:40:34,339 --> 00:40:35,505
INSTRUCTOR: Nu neapărat.

965
00:40:35,505 --> 00:40:39,710
Deci, ce se întâmplă este că mergem pe aici.

966
00:40:39,710 --> 00:40:43,830
Deci în timp ce, amintiți-vă, aceasta
va executa o dată, fără a eșua.

967
00:40:43,830 --> 00:40:46,480
Deci, se va seta
contra egale cu zero,

968
00:40:46,480 --> 00:40:48,070
apoi se va repeta prin.

969
00:40:48,070 --> 00:40:50,590
După cum se reiterează prin,
acesta va fi actualizat contra.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
După cum se actualizează contra, atunci când este făcut,
atunci când este atins la sfârșitul matrice,

972
00:40:56,900 --> 00:41:00,830
dacă lista noastră nu a fost sortate,
contor va au fost actualizate.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Deci, atunci se verifică starea și-l
spune, OK, este contra mai mare decât zero.

975
00:41:07,150 --> 00:41:09,290
În cazul în care este, o fac din nou.

976
00:41:09,290 --> 00:41:14,340
Doriți să resetați, astfel încât, atunci când
du-te prin, contra este egală cu zero.

977
00:41:14,340 --> 00:41:18,240
Dacă te duci printr-o sortat
matrice, nu se schimbă nimic,

978
00:41:18,240 --> 00:41:21,355
aceasta nu reușește, și tu
a reveni lista sortată.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Are care face sens?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
STUDENT: S-ar putea într-un pic.

983
00:41:26,356 --> 00:41:27,147
INSTRUCTOR: OK.

984
00:41:27,147 --> 00:41:28,980
Dacă există orice altă
Întrebarea care apare.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Da.

987
00:41:30,680 --> 00:41:33,760
>> STUDENT: Ce ar fi funcția
fie pentru schimbarea elementelor?

988
00:41:33,760 --> 00:41:36,900
>> INSTRUCTOR: Deci, putem scrie de fapt
că dacă vom chiar acum.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Rece.

991
00:41:38,300 --> 00:41:42,155
Deci, pe această notă, Alison se întâmplă
pentru a comuta înapoi la aparatul.

992
00:41:42,155 --> 00:41:43,080
O să fie distractiv.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Și avem frumos nostru
bubble sort lucru aici.

995
00:41:47,390 --> 00:41:50,800
Așa că am făcut-o deja cu bicicleta
prin matrice.

996
00:41:50,800 --> 00:41:53,030
Avem swap-uri noastre că
sunt egale cu zero.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Așa că vrem să schimb adiacent
Elemente dacă sunt în ordine.

999
00:41:58,440 --> 00:42:03,020
Deci, primul lucru pe care trebuie să
nu se repeta prin oferta noastră.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Deci, cum crezi că s-ar putea
itera prin oferta noastră?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Avem pentru și i este egal cu 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Ne dorim i să fie mai puțin
decât n minus 1 minus k.

1006
00:42:22,454 --> 00:42:23,870
Și vă voi explica că într-o secundă.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Deci, aceasta este o optimizare aici în cazul în care,
amintesc cum am spus, după fiecare trecere

1009
00:42:32,830 --> 00:42:36,655
prin WE matrice
știu că orice e on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Deci, după o pasă noi
știu că acest lucru este sortata.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
După două treceri știm
că toate acestea sunt sortate.

1014
00:42:50,060 --> 00:42:52,750
După trei treceri noi
știu că e sortate.

1015
00:42:52,750 --> 00:42:55,620
Deci, modul în care am iterarea
prin matrice de aici,

1016
00:42:55,620 --> 00:43:01,090
este este asigurându-vă că pentru a merge numai
prin ceea ce știm este nesortate.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Asta e doar o optimizare.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Ai putea scrie naivitate doar
iterarea prin tot,

1021
00:43:08,210 --> 00:43:09,970
ar fi nevoie de doar mai mult.

1022
00:43:09,970 --> 00:43:12,470
Cu această patru buclă este
doar o optimizare frumos

1023
00:43:12,470 --> 00:43:18,460
pentru că știm că, după fiecare complet
repetare prin matrice de aici,

1024
00:43:18,460 --> 00:43:24,050
ca fiecare buclă click aici, știm
că unul din aceste elemente

1025
00:43:24,050 --> 00:43:25,760
vor fi sortate la sfârșitul anului.

1026
00:43:25,760 --> 00:43:28,294
>> Deci, noi nu trebuie să vă faceți griji cu privire la acestea.

1027
00:43:28,294 --> 00:43:29,710
Are care are sens pentru toată lumea?

1028
00:43:29,710 --> 00:43:30,950
Că truc pic rece?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Deci, în acest caz, în cazul în care
suntem iterarea prin,

1031
00:43:37,270 --> 00:43:50,590
știm că vrem să verificăm dacă
matrice n și n plus 1 sunt în ordine.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Deci, aici e pseudocod.

1035
00:43:54,600 --> 00:43:57,540
Ne dorim să verificăm dacă matrice n
și n plus 1 sunt în ordine.

1036
00:43:57,540 --> 00:43:59,520
Deci, ceea ce am putea avea acolo?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
O să fie ceva condiționată.

1039
00:44:03,120 --> 00:44:04,220
Acesta va fi o dacă.

1040
00:44:04,220 --> 00:44:07,066
>> STUDENT: Dacă matrice n este
mai puțin de matrice n plus 1.

1041
00:44:07,066 --> 00:44:07,816
INSTRUCTOR: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Ei bine, mai mică sau mai mare de.

1044
00:44:10,699 --> 00:44:11,615
STUDENT: Mai mare.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Apoi ne-am dori pentru a le schimba.

1047
00:44:17,620 --> 00:44:18,570
Exact.

1048
00:44:18,570 --> 00:44:23,570
Deci, acum ajungem la ceea ce este
mecanism pentru schimbarea ei?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Așa că am trecut prin acest scurt,
un tip de funcție de swap săptămâna trecută.

1051
00:44:28,137 --> 00:44:29,595
Are cineva aminte cum a mers?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Astfel încât nu putem să le realoca doar, nu?

1054
00:44:34,950 --> 00:44:36,640
Pentru că unul dintre ei se va pierde.

1055
00:44:36,640 --> 00:44:41,696
Dacă am spus A este egal cu B, apoi B
este egal cu A, toate dintr-o dată atât de ei

1056
00:44:41,696 --> 00:44:43,150
sunt doar egal cu B.

1057
00:44:43,150 --> 00:44:45,720
>> Deci, ceea ce trebuie să faceți este să ne
au o variabilă temporară care este

1058
00:44:45,720 --> 00:44:49,055
O să dețină una dintre timp ce al nostru
suntem în procesul de pompare.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Deci, ceea ce avem este că vom avea unele int
Temperatura este egal sa-- puteti atribui

1061
00:44:56,464 --> 00:44:59,130
pentru oricare o doriți, doar
asigurați-vă că țineți evidența it--

1062
00:44:59,130 --> 00:45:01,840
astfel încât în ​​acest caz, am de gând să
atribui o matrice de n plus 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Așa că o să dețină orice
Valoarea este aceea că al doilea bloc

1065
00:45:07,674 --> 00:45:08,590
care ne uitam la.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Și atunci ce putem face este să putem merge
înainte și matrice realocați n plus 1,

1068
00:45:13,240 --> 00:45:14,990
pentru că noi știm
au ca valoarea stocată.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Aceasta este, de asemenea, una din marile
lucruri-- Nu știu dacă vreunul dintre voi

1071
00:45:19,270 --> 00:45:23,780
a avut probleme în cazul în care, dacă trece doi
de linii de cod dintr-o dată lucrurile s-au.

1072
00:45:23,780 --> 00:45:25,880
Comanda este foarte important în CS.

1073
00:45:25,880 --> 00:45:29,450
Deci, asigurați-vă că diagrama
lucrurile dacă este posibil

1074
00:45:29,450 --> 00:45:31,230
cu privire la ceea ce se întâmplă de fapt.

1075
00:45:31,230 --> 00:45:34,256
Deci, acum vom
realocați matrice n plus 1,

1076
00:45:34,256 --> 00:45:36,005
pentru că noi știm
au ca valoarea stocată.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Și putem atribui care a matrice
n sau, în acest caz matrice i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Prea multe variabile.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Matrice Deci, acum ne-am realocat i
plus 1 pentru a egala ceea ce este în matrice i.

1084
00:46:01,500 --> 00:46:08,240
Și acum ne putem întoarce și
atribui matrice i pentru ce?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Oricine?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> STUDENT: 10.

1089
00:46:14,010 --> 00:46:14,680
>> INSTRUCTOR: 10.

1090
00:46:14,680 --> 00:46:15,180
Exact.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Și un ultim lucru.

1093
00:46:18,640 --> 00:46:21,840
Dacă l-am schimbat acum,
Ce trebuie să facem?

1094
00:46:21,840 --> 00:46:23,740
Care este singurul lucru
care ne va spune

1095
00:46:23,740 --> 00:46:27,542
dacă am termina vreodată acest program?

1096
00:46:27,542 --> 00:46:29,250
Ce ne spune că noi
au o listă sortate?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Dacă nu vom efectua nicio swap-uri, nu?

1099
00:46:33,750 --> 00:46:36,900
În cazul în care swap-uri este egal cu
zero, la sfârșitul acestei.

1100
00:46:36,900 --> 00:46:42,975
Deci, ori de câte ori a efectua un schimb, așa cum am
doar a facut aici, vrem să actualizați swap-uri.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Și știu că a fost o
întrebare mai devreme despre poti tine

1103
00:46:47,210 --> 00:46:49,689
utilizați zero sau unu loc
de adevărat sau fals.

1104
00:46:49,689 --> 00:46:50,980
Și asta e ceea ce face acest lucru aici.

1105
00:46:50,980 --> 00:46:52,750
Deci, aceasta spune că dacă nu swap-urilor.

1106
00:46:52,750 --> 00:47:01,310
Deci, dacă swap-uri este zero, pe care am este-- mereu
primi adevăruri mei și falses mele amestecat.

1107
00:47:01,310 --> 00:47:03,960
Ne dorim să evaluăm
pentru adevărat și nu e.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Deci, dacă e zero, atunci e fals.

1110
00:47:09,630 --> 00:47:12,560
Dacă îl neagă cu o
[? bang-ului?] devine adevărat.

1111
00:47:12,560 --> 00:47:13,975
Deci, atunci această linie se execută.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Adevăruri și false și
zero-uri și cele primi nebun.

1114
00:47:17,370 --> 00:47:20,690
Doar dacă mergi încet
prin ea se va face sens.

1115
00:47:20,690 --> 00:47:23,320
Dar asta e ceea ce acest mic
bit de cod aici nu.

1116
00:47:23,320 --> 00:47:26,490
Deci, aceasta verifică
am făcut nici un swap-urilor.

1117
00:47:26,490 --> 00:47:30,054
Deci, dacă e ceva în afară de
zero, aceasta va fi falsă

1118
00:47:30,054 --> 00:47:31,970
și totul este
O să execute din nou.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Rece?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> STUDENT: Ce face pauză?

1123
00:47:36,000 --> 00:47:38,990
>> INSTRUCTOR: Break doar
te rupe din bucla.

1124
00:47:38,990 --> 00:47:41,570
Deci, în acest caz, ar
la fel ca termina programul

1125
00:47:41,570 --> 00:47:43,828
și v-ar doar
Lista ta sortate.

1126
00:47:43,828 --> 00:47:44,536
STUDENT: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
INSTRUCTOR: Îmi pare rău?

1129
00:47:49,010 --> 00:47:52,110
STUDENT: Pentru ca anterior noi
second scris 1 pe scris la zero

1130
00:47:52,110 --> 00:47:54,170
să prezinte că, dacă
care va funcționa sau nu.

1131
00:47:54,170 --> 00:47:54,878
>> INSTRUCTOR: Da.

1132
00:47:54,878 --> 00:47:56,410
Astfel încât să puteți returna zero sau 1.

1133
00:47:56,410 --> 00:47:58,950
În acest caz, pentru că noi nu suntem de fapt
a face ceva cu funcția,

1134
00:47:58,950 --> 00:48:00,150
vrem doar pentru a rupe.

1135
00:48:00,150 --> 00:48:02,680
Nu ne pasă cu adevărat despre el.

1136
00:48:02,680 --> 00:48:06,960
De asemenea, este bine dacă frână
este folosit pentru izbucnirii

1137
00:48:06,960 --> 00:48:10,710
de patru bucle sau condiții care
nu doriți să păstrați de executare.

1138
00:48:10,710 --> 00:48:12,110
Este doar te scoate din ele.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
E un pic de lucru nuanță.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Mă simt ca și cum nu există
o mulțime de ondularea de mână,

1143
00:48:18,445 --> 00:48:19,740
ca și cum veți afla despre acest curând.

1144
00:48:19,740 --> 00:48:20,955
>> Dar veți afla despre acest curând.

1145
00:48:20,955 --> 00:48:21,500
Promit.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Deci, nu toată lumea ajunge cu bule fel?

1149
00:48:24,840 --> 00:48:25,550
Nu prea rău.

1150
00:48:25,550 --> 00:48:31,910
Repeta prin, lucruri de swap folosind o
variabila temp, și suntem gata acolo?

1151
00:48:31,910 --> 00:48:32,960
Rece.

1152
00:48:32,960 --> 00:48:34,080
Minunat.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Înapoi la PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Orice întrebări, în general,
despre acestea până acum?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Rece.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> STUDENT: [inaudibil] int principal de obicei.

1162
00:48:45,279 --> 00:48:46,695
Nu trebuie să aveți că pentru acest lucru?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> INSTRUCTOR: Deci, am fost doar cauți
doar la algoritmul actual de sortare.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Dacă ați avea în
ca un program mai mare,

1167
00:48:56,350 --> 00:48:57,891
ai avea o undeva principal int.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
În funcție de unde
folosesc acest algoritm,

1170
00:49:02,880 --> 00:49:05,860
ar determina ceea ce este
fiind returnat de aceasta.

1171
00:49:05,860 --> 00:49:09,960
Dar pentru cazul nostru, suntem strict
uita la modul în care face acest lucru de fapt

1172
00:49:09,960 --> 00:49:11,300
itera printr-o serie.

1173
00:49:11,300 --> 00:49:12,570
Deci, noi nu vă faceți griji despre asta.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Așa că am vorbit despre cel mai bun caz și
cele mai grave scenarii pentru căutare binare.

1176
00:49:19,830 --> 00:49:22,470
Deci, este de asemenea important să se facă
că pentru fiecare dintre tipurile noastre.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Deci, ce credeți că este cel mai rău
caz de execuție de bule fel?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Voi aminti?

1181
00:49:30,700 --> 00:49:31,784
>> STUDENT: N minus 1.

1182
00:49:31,784 --> 00:49:32,700
INSTRUCTOR: N minus 1.

1183
00:49:32,700 --> 00:49:35,070
Asta înseamnă că există
n minus 1 comparatii.

1184
00:49:35,070 --> 00:49:40,060
Deci, un singur lucru pentru a realiza este
că pe prima iterație,

1185
00:49:40,060 --> 00:49:43,360
ne trece prin, vom compara
acestea two-- așa că e 1.

1186
00:49:43,360 --> 00:49:46,685
Acestea două, trei, patru.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Deci, după o iterație noi
au deja patru comparații.

1189
00:49:55,050 --> 00:49:58,230
Când vorbesc despre execuție și n.

1190
00:49:58,230 --> 00:50:04,680
N reprezintă numărul de comparații
în funcție de cât de multe elemente

1191
00:50:04,680 --> 00:50:05,570
avem.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Așa că am trece prin, avem patru.

1194
00:50:08,860 --> 00:50:11,780
Data viitoare când știi că nu
trebuie să aibă grijă de asta.

1195
00:50:11,780 --> 00:50:15,140
Vom compara aceste două,
aceste două, acestea două,

1196
00:50:15,140 --> 00:50:20,050
iar dacă nu am avut că de optimizare
cu patru bucla pe care am scris,

1197
00:50:20,050 --> 00:50:22,750
v-ar fi compararea aici oricum.

1198
00:50:22,750 --> 00:50:26,170
Deci, va trebui să
alerga prin matrice

1199
00:50:26,170 --> 00:50:34,380
și de a face comparații n n
ori, pentru că de fiecare dată ne

1200
00:50:34,380 --> 00:50:36,670
alerga prin ea am un fel un lucru.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Și de fiecare dată când trec prin
matrice, facem n comparații.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Deci, de execuție noastră pentru acest lucru este
de fapt n patrat, care

1205
00:50:46,330 --> 00:50:48,400
este mult mai rău în nostru
jurnal final pentru că

1206
00:50:48,400 --> 00:50:51,965
înseamnă dacă am fi avut patru
miliarde de elemente, e

1207
00:50:51,965 --> 00:50:55,260
O să ne ia patru miliarde
pătrat în loc de 32.

1208
00:50:55,260 --> 00:51:01,240
Deci, nu cel mai bun Runtime,
dar pentru unele lucruri,

1209
00:51:01,240 --> 00:51:04,610
știi, dacă ești în
un anumit interval de elemente

1210
00:51:04,610 --> 00:51:06,540
balon fel poate fi bine utilizat.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Și acum ce este cel mai bun Runtime caz?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
STUDENT: Zero?

1215
00:51:14,940 --> 00:51:16,420
Sau 1?

1216
00:51:16,420 --> 00:51:18,140
>> INSTRUCTOR: Deci, 1 ar
fie o comparație.

1217
00:51:18,140 --> 00:51:19,114
Dreapta.

1218
00:51:19,114 --> 00:51:20,002
>> STUDENT: N minus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> INSTRUCTOR: Deci, da.

1221
00:51:22,320 --> 00:51:22,990
Deci, n minus 1.

1222
00:51:22,990 --> 00:51:26,510
Ori de câte ori aveți un concept ca n
minus 1, avem tendința de a doar o picătură off

1223
00:51:26,510 --> 00:51:31,680
și spunem doar n pentru că ai
pentru a compara fiecare dintre these-- fiecare pereche.

1224
00:51:31,680 --> 00:51:36,470
Așa că ar fi n minus 1, pe care noi
am spune pur și simplu este de aproximativ n.

1225
00:51:36,470 --> 00:51:39,280
Când ai de a face cu timpul rulării,
totul este în aproximate.

1226
00:51:39,280 --> 00:51:43,860
Atâta timp cât exponentul este
corect, ești destul de bun.

1227
00:51:43,860 --> 00:51:45,700
>> Asta e modul în care avem de a face cu ea.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Așa că cel mai bun caz este n, care
înseamnă că lista este deja sortate,

1230
00:51:51,780 --> 00:51:54,320
și tot ce faceți este să rulați prin
și verificați că este sortate.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Rece.

1233
00:51:56,855 --> 00:51:57,355
Bine.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Deci, după cum vedeți aici,
Trebuie doar unele mai multe grafice.

1236
00:52:01,920 --> 00:52:02,660
Deci, n pătrat.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Fun.

1239
00:52:05,120 --> 00:52:09,730
Mult mai rău decât n așa cum vom vedea, și
mult, mult mai rău decât jurnal 2n.

1240
00:52:09,730 --> 00:52:12,060
Și atunci veți obține, de asemenea, în busteni jurnal.

1241
00:52:12,060 --> 00:52:18,020
Și vă voi lua 124, intri în
cum ar fi stele din jurnal, care este ca un nebun.

1242
00:52:18,020 --> 00:52:20,172
Deci, dacă sunteți interesat,
căutare jurnal stele.

1243
00:52:20,172 --> 00:52:20,880
E un fel de distracție.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Deci avem acest mare grafic.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Doar un heads-up, aceasta o
diagramă minunat de a avea

1248
00:52:28,720 --> 00:52:31,350
pentru termen mediu, deoarece noi
mult timp să vă întreb aceste subtiaza.

1249
00:52:31,350 --> 00:52:36,090
Deci, doar un heads-up, avea acest lucru asupra ta
pe termen mediu pe foaia de ieftin frumos

1250
00:52:36,090 --> 00:52:36,616
acolo.

1251
00:52:36,616 --> 00:52:37,990
Așa că ne-am uitat la balon fel.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
În cel mai rău caz, n patrat, cel mai bun caz, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Și ne vom uita la ceilalți.

1256
00:52:44,950 --> 00:52:47,940
>> Și, după cum puteți vedea, singurul
unul care într-adevăr bine

1257
00:52:47,940 --> 00:52:50,910
este un fel de îmbinare, pe care o vom primi în ce.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Deci, vom merge la
următor un fel de selecție here--.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Are cineva aminte cum
selecție a lucrat fel?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Du-te pentru ea.

1264
00:53:05,700 --> 00:53:08,210
>> STUDENT: du-te Practic prin
un ordin și de a crea o listă nouă.

1265
00:53:08,210 --> 00:53:11,001
Și, la fel cum te inscrie elemente
in, le-a pus în locul potrivit

1266
00:53:11,001 --> 00:53:11,750
în noua listă.

1267
00:53:11,750 --> 00:53:14,040
>> INSTRUCTOR: Așa că sunetele
mai mult ca inserție fel.

1268
00:53:14,040 --> 00:53:15,040
Dar ești foarte aproape.

1269
00:53:15,040 --> 00:53:15,915
Sunt foarte asemănătoare.

1270
00:53:15,915 --> 00:53:17,440
Chiar și eu să-i amestecat uneori.

1271
00:53:17,440 --> 00:53:18,981
Înainte de această secțiune am fost ca, așteptați.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Deci, ce vrei să
face este de selecție fel,

1275
00:53:24,141 --> 00:53:25,890
modul în care vă puteți gândi
cu privire la aceasta și modul în care

1276
00:53:25,890 --> 00:53:30,140
Am asigurați-vă că nu încercați să obțineți
le-a amestecat sus, este trece printr-

1277
00:53:30,140 --> 00:53:33,280
și se selectează
cel mai mic număr și-l

1278
00:53:33,280 --> 00:53:36,070
pune că la începutul listei.

1279
00:53:36,070 --> 00:53:37,730
Acesta se swap-uri cu acel prim loc.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Ei au de fapt un exemplu pentru mine.

1282
00:53:45,370 --> 00:53:46,540
Minunat.

1283
00:53:46,540 --> 00:53:50,130
Deci, doar un mod de a gândi de selecție it--
sortare, selectați cea mai mică valoare.

1284
00:53:50,130 --> 00:53:51,940
Și am de gând să
executa printr-un exemplu

1285
00:53:51,940 --> 00:53:55,320
care cred ca va ajuta pentru că
Cred vizuale ajută întotdeauna.

1286
00:53:55,320 --> 00:53:58,510
Deci, să începem cu ceva
care este complet nesortate.

1287
00:53:58,510 --> 00:54:00,730
Red va fi nesortate,
verde vor fi sortate.

1288
00:54:00,730 --> 00:54:02,190
Se va face toate sens într-o secundă.

1289
00:54:02,190 --> 00:54:08,950
>> Așa că am trece prin noi și repeta
de la început până la sfârșit.

1290
00:54:08,950 --> 00:54:12,320
Și noi spunem, OK, 2 este
numărul nostru mai mic.

1291
00:54:12,320 --> 00:54:15,680
Așa că am de gând să ia 2 și noi te vom
pentru al muta la partea din față a oferta noastră

1292
00:54:15,680 --> 00:54:17,734
pentru că este
cel mai mic număr avem.

1293
00:54:17,734 --> 00:54:19,150
Deci, asta e ceea ce acest lucru este aici.

1294
00:54:19,150 --> 00:54:20,820
E doar de gând să schimb cei doi.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Așa că acum am o sortate
parte și o parte nesortate.

1297
00:54:25,450 --> 00:54:27,810
Și ceea ce e bine să-și amintească
despre selecție de sortare

1298
00:54:27,810 --> 00:54:30,690
Este suntem doar selectând
din partea nesortat.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Partea de sortat tocmai te lase în pace.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> STUDENT: Cum se știe ce este
cel mai mic fără comparandu-l

1303
00:54:38,452 --> 00:54:39,868
pentru fiecare altă valoare în matrice.

1304
00:54:39,868 --> 00:54:41,250
INSTRUCTOR: Aceasta nu se compara.

1305
00:54:41,250 --> 00:54:42,041
Ne place omise.

1306
00:54:42,041 --> 00:54:43,850
Acest lucru este pur și simplu globală generală.

1307
00:54:43,850 --> 00:54:44,831
Da.

1308
00:54:44,831 --> 00:54:47,205
Când ne-am scrie codul eu sunt
sigur că vei fi mai mulțumiți.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Dar magazin acest prim
ca element mai mic.

1311
00:54:53,030 --> 00:54:56,110
Tu comparati si tu
spune, OK, e mai mic?

1312
00:54:56,110 --> 00:54:56,660
Da.

1313
00:54:56,660 --> 00:54:57,460
Păstrați-l.

1314
00:54:57,460 --> 00:54:58,640
Aici este mai mic?

1315
00:54:58,640 --> 00:54:59,660
Nu?

1316
00:54:59,660 --> 00:55:02,510
>> Aceasta este cea mai mică tău,
realocați-l la valoarea ta.

1317
00:55:02,510 --> 00:55:06,340
Și vei fi mult mai fericit
când vom merge prin cod.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Așa că am trece prin, l-am schimb, astfel încât atunci
ne uităm la această porțiune nesortate.

1320
00:55:13,970 --> 00:55:15,810
Deci, vom selecta trei.

1321
00:55:15,810 --> 00:55:18,890
Vom să-l puneți pe la
sfârșitul porțiunii noastre sortat.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Și suntem doar de gând să continuăm să facem
că, făcând asta, și de a face asta.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Deci, aceasta este un fel nostru de pseudocod aici.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Vom cod aici într-o secundă.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Dar doar ceva de mers pe jos
printr-un nivel ridicat.

1330
00:55:37,270 --> 00:55:40,275
Vei merge de la
i este egal cu 0 la n minus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Asta e un alt optimizare.

1333
00:55:43,530 --> 00:55:45,020
Nu vă faceți griji prea mult despre asta.

1334
00:55:45,020 --> 00:55:46,620
Deci, după cum spuneai.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Așa cum Iacov a spus, cum putem
ține evidența a ceea ce minim nostru este?

1337
00:55:54,406 --> 00:55:55,030
De unde știm?

1338
00:55:55,030 --> 00:55:57,060
Trebuie să comparăm
totul în lista noastră.

1339
00:55:57,060 --> 00:55:59,600
>> Deci, minim i egal.

1340
00:55:59,600 --> 00:56:03,870
E doar că în acest caz
indicele de valoare noastre minim.

1341
00:56:03,870 --> 00:56:07,660
Deci, atunci se va repeta prin
și merge de la j i plus 1 egal.

1342
00:56:07,660 --> 00:56:11,420
Deci, noi știm deja că
asta e prima noastră elementului.

1343
00:56:11,420 --> 00:56:13,240
Noi nu trebuie să-l compara cu ea însăși.

1344
00:56:13,240 --> 00:56:16,970
Deci, vom începe o comparatie cu alta
una care este de ce este i plus 1 la n

1345
00:56:16,970 --> 00:56:20,110
minus 1, care este
capăt al șirului acolo.

1346
00:56:20,110 --> 00:56:25,090
Și am spus că dacă matrice la
j este mai mică de matrice min,

1347
00:56:25,090 --> 00:56:29,200
apoi ne-am realocați în cazul în care
Indicii noastre minime sunt.

1348
00:56:29,200 --> 00:56:37,470
>> Și dacă min nu este egal cu i, ca
în cazul în care ne-am intors aici.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Deci, ca atunci când am făcut prima dată această unul.

1351
00:56:41,790 --> 00:56:49,310
În acest caz, se va incepe de la
zero, aceasta s-ar sfârși prin a fi doi.

1352
00:56:49,310 --> 00:56:53,010
Deci, min nu ar fi egal i în cele din urmă.

1353
00:56:53,010 --> 00:56:55,720
Care ne permite să știu că
avem nevoie pentru a le schimba.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Mă simt ca un exemplu concret
va ajuta mult mai mult decât aceasta.

1356
00:57:00,470 --> 00:57:04,970
Așa că vom cod asta cu voi
chiar acum și cred că va fi mai bine.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Felul tendința de a lucra în acest fel, în care
este de multe ori mai bine doar pentru a le vedea.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Deci, ceea ce vrem să facem este
ne-o dorim în primul rând cel mai mic

1361
00:57:17,280 --> 00:57:19,890
elementul în poziția sa în matrice.

1362
00:57:19,890 --> 00:57:21,280
Exact ceea ce Jacob spunea.

1363
00:57:21,280 --> 00:57:23,090
Aveți nevoie pentru a stoca într-un fel.

1364
00:57:23,090 --> 00:57:25,900
Deci, vom începe aici
iterarea peste matrice.

1365
00:57:25,900 --> 00:57:28,970
Noi o să spun că este nostru
în primul rând o doar pentru a începe cu.

1366
00:57:28,970 --> 00:57:38,308
Deci, vom avea int
cel mai mic este egal cu matrice la i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Deci, un singur lucru pentru a observa, fiecare
de data asta buclă executa,

1369
00:57:45,050 --> 00:57:48,550
suntem incepand cu un pas mai departe de-a lungul.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Când începem ne uităm la asta.

1372
00:57:57,440 --> 00:58:00,840
Data viitoare vom repeta prin,
suntem incepand de la acesta

1373
00:58:00,840 --> 00:58:02,680
și o valoare mai mică nostru atribuire.

1374
00:58:02,680 --> 00:58:10,450
Deci, este foarte similar cu bule de sortare
unde știm că, după o pasă,

1375
00:58:10,450 --> 00:58:11,700
acest ultim element este sortata.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Cu selecție de sortare,
e exact opusul.

1378
00:58:15,120 --> 00:58:18,950
>> La fiecare trecere, știm că
primul este sortat.

1379
00:58:18,950 --> 00:58:21,360
După a doua trecere,
al doilea va fi sortate.

1380
00:58:21,360 --> 00:58:26,470
Și, după cum ați văzut cu exemple de diapozitive,
porțiune nostru sortate doar continuă să crească.

1381
00:58:26,470 --> 00:58:34,020
Deci, prin stabilirea una noastră cel mai mic
pentru tablouri i, tot ce face

1382
00:58:34,020 --> 00:58:37,340
este constricția ce
ne uităm la astfel ca

1383
00:58:37,340 --> 00:58:40,164
pentru a reduce numărul
comparațiilor facem.

1384
00:58:40,164 --> 00:58:41,770
Asta face sens pentru toată lumea?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Ai nevoie de mine pentru a rula prin care
din nou, mai lent sau cu alte cuvinte?

1387
00:58:46,380 --> 00:58:47,180
Sunt fericit să.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Deci, suntem stochează
Valoarea la acest moment,

1392
00:58:55,540 --> 00:58:57,840
dar ne-am dori, de asemenea pentru a stoca index.

1393
00:58:57,840 --> 00:59:01,010
Deci, vom stoca
Poziția de cel mai mic

1394
00:59:01,010 --> 00:59:02,770
unul, care este doar de gând să fi i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Deci, acum, Jacob este îndeplinită.

1397
00:59:05,440 --> 00:59:06,870
Avem lucruri stocate.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Și acum trebuie să privim prin
partea nesortate din matrice.

1400
00:59:11,870 --> 00:59:18,170
Deci, în acest caz, acest
ar fi nesortate nostru.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Acest lucru este i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Deci, ce vom face
va fi pentru o buclă.

1406
00:59:30,040 --> 00:59:32,066
Ori de câte ori aveți nevoie pentru a
itera printr-o serie,

1407
00:59:32,066 --> 00:59:33,440
mintea ta ar putea merge la o buclă.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Deci, pentru a putea int k
equals-- ce credem noi

1410
00:59:38,090 --> 00:59:39,700
k este de gând să egaleze pentru a începe cu?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Aceasta este ceea ce ne-am stabilit ca cel mai mic noastre
valoare și vrem să-l comparare.

1413
00:59:44,766 --> 00:59:47,090
Ce vrem să-l compara cu?

1414
00:59:47,090 --> 00:59:48,730
O să fie acesta următorul, nu?

1415
00:59:48,730 --> 00:59:53,200
Așa că vrem k să fie inițializat
la i plus 1 pentru a începe.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Și ne dorim k în acest caz
deja dimensiune stocate aici,

1418
01:00:02,800 --> 01:00:03,930
astfel încât să putem folosi doar dimensiunea.

1419
01:00:03,930 --> 01:00:06,240
Dimensiunea fiind dimensiunea matricii.

1420
01:00:06,240 --> 01:00:09,620
Și vrem doar să
actualizare k de unul de fiecare dată.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Rece.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Deci, acum trebuie să găsim
cel mai mic element aici.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Deci, dacă am repeta prin, noi
vreau să spun, dacă matrice la k

1427
01:00:31,380 --> 01:00:37,080
este mai mică decât cea mai mică value-- nostru
acest lucru este în cazul în care suntem de fapt

1428
01:00:37,080 --> 01:00:42,950
urmărirea a ceea ce este
cel mai mic here--

1429
01:00:42,950 --> 01:00:47,740
apoi ne-am dori să realocați
ce valoare mai mică nostru este.

1430
01:00:47,740 --> 01:00:50,645
>> Acest lucru înseamnă că, oh, suntem
iterarea pe aici.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Oricare ar fi valoare nu este aici este
nu mai mic lucru nostru.

1433
01:00:53,740 --> 01:00:54,448
Noi nu-l vreau.

1434
01:00:54,448 --> 01:00:56,100
Vrem să le retrocedeze.

1435
01:00:56,100 --> 01:01:02,050
Deci, dacă suntem o realocare, ceea ce face
credeți că ar putea fi în acest cod aici?

1436
01:01:02,050 --> 01:01:04,160
Vrem să realocați
cel mai mic și poziția.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Deci, ceea ce este cea mai mică acum?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
STUDENT: Array k.

1441
01:01:09,130 --> 01:01:09,963
INSTRUCTOR: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
Și care este poziția acum?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Ce-i indicii de
Valoarea noastră mai mic?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
E doar k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Deci, k matrice, k, se potrivesc.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Așa că am vrut să realocați asta.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Și apoi după ce am găsit cel mai mic noastre,
astfel încât la sfârșitul acestei pentru buclă

1454
01:01:39,950 --> 01:01:45,100
aici am gasit ceea ce cel mai mic noastre
Valoarea este, deci ne-am l schimb.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
În acest caz, cum ar fi spus noastră
cea mai mică valoare nu este aici.

1457
01:01:50,816 --> 01:01:51,940
Aceasta este valoarea noastră mai mic.

1458
01:01:51,940 --> 01:01:57,690
>> Vrem doar să-l schimb aici, ceea ce este
ce această funcție schimb în partea de jos

1459
01:01:57,690 --> 01:02:01,270
făcut-o, pe care tocmai am scris în sus
împreună în urmă cu câteva minute.

1460
01:02:01,270 --> 01:02:02,775
Deci, ar trebui să arate familiar.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Și atunci se va repeta doar
prin până când ajunge la capăt

1463
01:02:08,030 --> 01:02:13,100
până la capăt, ceea ce înseamnă că
avea zero elemente care sunt nesortate

1464
01:02:13,100 --> 01:02:14,800
și orice altceva a fost sortate.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Face sens?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Un pic mai concret?

1469
01:02:19,280 --> 01:02:19,990
Codul de ajutor?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> STUDENT: Pentru o dimensiune, pe care nu
într-adevăr defini sau schimba-l,

1472
01:02:26,410 --> 01:02:27,340
cum nu-l știți?

1473
01:02:27,340 --> 01:02:32,380
>> INSTRUCTOR: Deci, un singur lucru a
observa aici este dimensiunea int.

1474
01:02:32,380 --> 01:02:35,680
Așa că am să spui că în acest fel sort--
este o funcție în acest case-- e

1475
01:02:35,680 --> 01:02:40,770
selecție fel, e trecut
în cu funcția.

1476
01:02:40,770 --> 01:02:43,460
Deci, în cazul în care nu a fost trecut
in, v-ar face ceva

1477
01:02:43,460 --> 01:02:47,840
ca și cu lungimea unui array
sau v-ar repeta prin

1478
01:02:47,840 --> 01:02:49,390
pentru a găsi lungimea.

1479
01:02:49,390 --> 01:02:52,680
Ci pentru că e trecut
în, putem doar să-l folosească.

1480
01:02:52,680 --> 01:02:55,720
Trebuie doar presupune că utilizatorul
ți-a dat o dimensiune validă care

1481
01:02:55,720 --> 01:02:57,698
reprezintă de fapt
o dimensiune de matrice dumneavoastră.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Rece?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Dacă voi avea probleme cu acestea
sau vrei mai multe practici de codificare felul

1486
01:03:05,870 --> 01:03:08,050
pe cont propriu, ar trebui
Mergi la study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Este un instrument.

1489
01:03:12,670 --> 01:03:15,040
Ei au un verificator care
puteți scrie de fapt.

1490
01:03:15,040 --> 01:03:16,180
Ei fac pseudocod.

1491
01:03:16,180 --> 01:03:19,310
Ei au mai multe videoclipuri și diapozitive
inclusiv cele pe care le folosesc aici.

1492
01:03:19,310 --> 01:03:23,150
Deci, dacă sunteți încă simți un
pic neclare, încercați asta.

1493
01:03:23,150 --> 01:03:25,670
Ca de obicei, vin să vorbească cu mine, de asemenea.

1494
01:03:25,670 --> 01:03:26,320
Întrebare?

1495
01:03:26,320 --> 01:03:28,611
>> STUDENT: Vrei să spui că
mărime este definit ca mai înainte?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
INSTRUCTOR: Da.

1498
01:03:29,900 --> 01:03:35,570
Dimensiunea este definit ca mai înainte în sus
aici, în declarația funcției.

1499
01:03:35,570 --> 01:03:39,060
Astfel încât să se presupună că aceasta a fost adoptată în
de către utilizator, precum și din motive de simplificare,

1500
01:03:39,060 --> 01:03:41,896
vom presupune că
utilizator ne-a dat dimensiunea corectă.

1501
01:03:41,896 --> 01:03:43,240
Rece.

1502
01:03:43,240 --> 01:03:44,390
Așa că e de selecție fel.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Băieți, știu că am învățat foarte mult astăzi.

1505
01:03:47,640 --> 01:03:49,710
E un dens de date pentru secțiunea.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Deci, cu asta, vom
pentru a merge la inserarea fel.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Deci, înainte de asta trebuie să facem
Analiza noastră rulare aici.

1511
01:04:06,100 --> 01:04:10,190
Deci, în cel mai bun caz,
acordată de când ți-am arătat

1512
01:04:10,190 --> 01:04:11,960
tabelul I deja
un fel de dat degajeze.

1513
01:04:11,960 --> 01:04:15,430
Dar cel mai bun la rulare caz, ce credem noi?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Totul sortate.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N pătrat.

1518
01:04:22,070 --> 01:04:24,780
Oricine are o explicație
de ce crezi?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> STUDENT: Ești compararea through--

1521
01:04:30,519 --> 01:04:31,268
INSTRUCTOR: Corect.

1522
01:04:31,268 --> 01:04:32,540
Ești compararea prin intermediul.

1523
01:04:32,540 --> 01:04:35,630
La fiecare iterație, chiar dacă
suntem decrementare aceasta de unul,

1524
01:04:35,630 --> 01:04:38,950
aveți în continuare căutarea prin
totul pentru a găsi cel mai mic.

1525
01:04:38,950 --> 01:04:42,390
Deci, chiar dacă valoarea cea mai mică
este aici, la început,

1526
01:04:42,390 --> 01:04:44,710
aveți în continuare o comparare
împotriva orice altceva

1527
01:04:44,710 --> 01:04:46,550
pentru a vă asigura că este cel mai mic lucru.

1528
01:04:46,550 --> 01:04:49,820
Deci, veți termina care trece prin
aproximativ de n ori pătrat.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Bine.

1531
01:04:51,590 --> 01:04:52,785
Si ceea ce este cel mai rau caz?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
De asemenea, n patrat pentru că ai de gând
pentru a face aceeași procedură.

1534
01:04:57,980 --> 01:05:01,670
Deci, în acest caz, de selecție
are ceva de sortare

1535
01:05:01,670 --> 01:05:04,010
pe care o numim, de asemenea, de execuție de așteptat,.

1536
01:05:04,010 --> 01:05:07,400
Deci, în celelalte, doar noi știm
limitele superioare și inferioare.

1537
01:05:07,400 --> 01:05:11,180
În funcție de cât de nebun nostru
Lista este sau cât de nesortate este,

1538
01:05:11,180 --> 01:05:15,350
acestea variază între n sau n patrat.

1539
01:05:15,350 --> 01:05:16,550
Nu știm.

1540
01:05:16,550 --> 01:05:22,820
>> Dar, pentru că de selecție fel are aceeași
cel mai rău și cel mai bun caz, care ne spune că

1541
01:05:22,820 --> 01:05:25,880
indiferent de ce tip de intrare noi
au, fie că este vorba complet

1542
01:05:25,880 --> 01:05:29,130
sortate sau complet
inversa sortate, e

1543
01:05:29,130 --> 01:05:30,740
de gând să ia aceeași cantitate de timp.

1544
01:05:30,740 --> 01:05:33,760
Deci, în acest caz, dacă
amintiți-vă de la masa noastră,

1545
01:05:33,760 --> 01:05:38,610
a avut de fapt o valoare care
aceste două tipuri nu au,

1546
01:05:38,610 --> 01:05:40,390
care este de așteptat rulare.

1547
01:05:40,390 --> 01:05:43,350
Deci, noi știm că ori de câte ori
fugim de selecție fel,

1548
01:05:43,350 --> 01:05:45,380
este garantat de
rula un timp n pătrat.

1549
01:05:45,380 --> 01:05:46,630
Nu există nici o variabilitate acolo.

1550
01:05:46,630 --> 01:05:47,630
E doar de așteptat.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
Și, din nou, dacă vrei să înveți
mai mult, ia CS 124 in primavara.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Bine.

1555
01:05:56,712 --> 01:05:57,545
Am văzut asta.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Rece.

1558
01:05:59,030 --> 01:06:00,930
Un fel atât de inserție.

1559
01:06:00,930 --> 01:06:03,330
Și eu, probabil, va
să ardă prin aceasta.

1560
01:06:03,330 --> 01:06:05,440
Nu voi avea voi l cod.

1561
01:06:05,440 --> 01:06:06,580
Vom merge pe jos doar prin ea.

1562
01:06:06,580 --> 01:06:10,500
Deci, inserare fel este un fel
de similar cu selecție de sortare

1563
01:06:10,500 --> 01:06:14,460
în care avem atât un nesortate
și sortate parte din matrice.

1564
01:06:14,460 --> 01:06:20,260
>> Dar ceea ce este diferit este faptul că
așa cum am trece prin unul câte unul,

1565
01:06:20,260 --> 01:06:24,210
vom lua doar orice număr
este următorul în nesortate noastră,

1566
01:06:24,210 --> 01:06:28,507
și-l rezolve corect
în oferta noastră sortat.

1567
01:06:28,507 --> 01:06:30,090
Va face mai mult sens cu un exemplu.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Deci, totul incepe ca nesortate,
la fel ca și cu selecție de sortare.

1570
01:06:35,430 --> 01:06:38,740
Și vom sorta acest lucru în
ordine crescătoare așa cum am fost.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Deci, la prima noastră trecere
vom lua prima valoare

1573
01:06:43,340 --> 01:06:46,700
și spunem, OK, esti
acum într-o listă de unul singur.

1574
01:06:46,700 --> 01:06:49,150
>> Pentru că vă aflați într-o listă
de unul singur, pe care sunt sortate.

1575
01:06:49,150 --> 01:06:52,460
Felicitări pentru a fi
prim element în această matrice.

1576
01:06:52,460 --> 01:06:54,800
Te sortate deja toate pe cont propriu.

1577
01:06:54,800 --> 01:06:58,900
Așa că acum am o sortate
și o serie nesortate.

1578
01:06:58,900 --> 01:07:01,760
Deci, acum vom lua primul.

1579
01:07:01,760 --> 01:07:05,600
Ce se întâmplă între aici
și aici este că noi spunem,

1580
01:07:05,600 --> 01:07:08,890
OK, ne vom uita la
primă valoare de oferta noastră nesortate

1581
01:07:08,890 --> 01:07:13,270
și vom intrare-l la ei
locul corect în matrice sortat.

1582
01:07:13,270 --> 01:07:21,460
>> Deci, ceea ce facem este să luăm 5 și
spunem, OK, 5 este mai mare de 3,

1583
01:07:21,460 --> 01:07:24,630
asa ca am doar o introduce drept
la dreapta de care.

1584
01:07:24,630 --> 01:07:25,130
Suntem bine.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Deci, atunci vom merge pe una noastră viitoare.

1587
01:07:28,420 --> 01:07:29,720
Și vom lua 2.

1588
01:07:29,720 --> 01:07:34,330
Noi spunem, OK, 2 este mai puțin
decât 3, astfel știm că

1589
01:07:34,330 --> 01:07:36,220
trebuie să fie la
fata de lista noastră de acum.

1590
01:07:36,220 --> 01:07:41,800
Deci, ceea ce facem este ne împinge 3 și 5 jos
și ne-am muta 2 în care primul fantă.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Deci, noi doar îl introduceți în
locul corect ar trebui să fie.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Apoi ne uităm la noastre
un viitor, și spunem 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 este mai mare decât
totul în oferta noastră sortat,

1596
01:07:53,620 --> 01:07:56,000
asa ca am doar o eticheta pe până la capăt.

1597
01:07:56,000 --> 01:07:56,960
Și apoi ne uităm la 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 este mai mic de 6, este mai puțin
decât 5, dar este mai mare de 3.

1600
01:08:03,020 --> 01:08:06,270
Așa că ne-am introduceți-l direct în
mijloc între 3 și 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Deci, pentru a face ca un pic
ceva mai concret,

1603
01:08:10,530 --> 01:08:12,280
aici este un fel de
idee de ceea ce sa întâmplat.

1604
01:08:12,280 --> 01:08:16,430
Deci, pentru fiecare element nesortate, ne-am
determina în cazul în care în porțiunea de sortat

1605
01:08:16,430 --> 01:08:17,090
ea este.

1606
01:08:17,090 --> 01:08:20,680
>> Deci, păstrând în minte
sortate și nesortate,

1607
01:08:20,680 --> 01:08:26,080
avem de a traversa prin și figura
de unde se potrivește în tabloul sortat.

1608
01:08:26,080 --> 01:08:31,460
Și l-am introduce prin transferarea
Elemente de la dreapta în jos.

1609
01:08:31,460 --> 01:08:34,910
Și apoi ne-am păstra
iterarea prin până la noi

1610
01:08:34,910 --> 01:08:39,270
au o listă sortate complet
în cazul în care nesortate este acum la zero

1611
01:08:39,270 --> 01:08:41,720
și sortat preia
toate elementele de pe lista noastră.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Așa că, din nou, pentru a face lucrurile chiar
mai concret, avem pseudocod.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Deci, practic pentru i este
egal cu 0 până la n minus 1,

1616
01:08:52,410 --> 01:08:54,790
asta e doar lungimea de oferta noastră.

1617
01:08:54,790 --> 01:09:00,979
Avem un element care este egală cu
prima matrice sau primele indicii.

1618
01:09:00,979 --> 01:09:03,200
Ne-am propus j egală cu asta.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Deci, în timp ce j este mai mare decât
zero și matrice, j minus 1

1621
01:09:09,210 --> 01:09:11,660
este mai mare decât
Element, deci tot ce face

1622
01:09:11,660 --> 01:09:17,479
este de a face sigur că
j dumneavoastră reprezintă într-adevăr

1623
01:09:17,479 --> 01:09:20,010
porțiunea nesortate de matrice.

1624
01:09:20,010 --> 01:09:30,745
>> Deci, în timp ce există încă lucruri
pentru a sorta și j minus un este-- ce

1625
01:09:30,745 --> 01:09:31,840
este elementul ei?

1626
01:09:31,840 --> 01:09:34,760
J nu a fost niciodată definit aici.

1627
01:09:34,760 --> 01:09:35,677
E un fel de enervant.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Oricum.

1630
01:09:36,689 --> 01:09:39,899
Deci, j minus 1, ești verificare
elementul în fața sa.

1631
01:09:39,899 --> 01:09:46,460
Vrei să spui, OK, este elementul
înainte ori de câte ori am am-- să

1632
01:09:46,460 --> 01:09:47,540
de fapt, trage asta.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Așa că haideți să spun acest lucru este
ca pe a doua trecere noastră.

1635
01:09:56,830 --> 01:09:59,525
Deci, eu o să fie egal
la 1, ceea ce este aici.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Deci, eu va fi egal cu 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Acest lucru ar fi 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Bine.

1642
01:10:16,750 --> 01:10:20,945
Deci, elementul nostru în acest caz
va fi egal cu 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Și avem ceva j care este
va fi egal cu 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, J este decrementarea.

1647
01:10:30,971 --> 01:10:31,720
Asta e ceea ce este.

1648
01:10:31,720 --> 01:10:35,680
Deci, j este egal cu i, deci ce e asta
spune este că, așa cum am merge mai departe,

1649
01:10:35,680 --> 01:10:37,530
suntem doar asigurându-vă
că nu suntem pe

1650
01:10:37,530 --> 01:10:43,520
indexarea acest fel, atunci când noi încercăm
pentru a introduce lucrurile în lista noastră sortate.

1651
01:10:43,520 --> 01:10:49,850
>> Deci, atunci când j este egal cu 1 în acest caz și
matrice j minus Unu atât de matrice j minus 1

1652
01:10:49,850 --> 01:10:54,610
este 2 în acest case-- dacă e
mai mare decât elementul,

1653
01:10:54,610 --> 01:10:57,700
atunci toate acestea se face
se schimbă lucrurile în jos.

1654
01:10:57,700 --> 01:11:04,790
Deci, în acest caz, matrice j minus una
ar fi matrice de zero, care este de 2.

1655
01:11:04,790 --> 01:11:08,430
2 nu este mai mare de 4,
deci acest lucru nu executa.

1656
01:11:08,430 --> 01:11:11,460
Deci, schimbarea nu se mișcă în jos.

1657
01:11:11,460 --> 01:11:18,790
Ce este acest lucru nu aici este doar
mutarea matrice ta sortat jos.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
În acest caz, de fapt, ne-am
ar putea do-- să facem acest 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Deci, dacă vrem să umblăm prin cu
acest exemplu, suntem acum aici.

1662
01:11:31,970 --> 01:11:32,740
Aceasta este sortat.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Acest lucru este nesortate.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Rece?

1667
01:11:39,860 --> 01:11:46,620
Deci i este egal cu 2, deci
elementul nostru este egal cu 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Și j noastră este egal cu 2.

1670
01:11:52,270 --> 01:12:00,620
Așa că ne-am uita prin și noi
spune, OK, este matrice j minus una

1671
01:12:00,620 --> 01:12:03,470
mai mare decât elementul
care ne uitam la?

1672
01:12:03,470 --> 01:12:05,540
Iar răspunsul este da, corect?

1673
01:12:05,540 --> 01:12:11,275
4 este mai mare de 3 și j
este 2, astfel încât acest cod execută.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Și acum ce facem o serie de
2, deci chiar aici, le schimb.

1676
01:12:18,550 --> 01:12:25,620
Deci, noi spunem doar, OK, matrice
la 2 este acum va fi de 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Și j este de gând să egaleze
j minus 1, care este 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Asta e oribil, dar
voi prins ideea.

1681
01:12:37,200 --> 01:12:38,360
J este acum egal cu 1.

1682
01:12:38,360 --> 01:12:44,360
Și matrice j este doar de gând să fie
egală cu elementul nostru, care a fost de 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Am șters ceva ce nu-mi trebuie
au sau ceva miswrote,

1685
01:12:48,570 --> 01:12:49,910
dar voi prins ideea.

1686
01:12:49,910 --> 01:12:50,640
>> Se muta la n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Și apoi, dacă acest lucru ar fi, ar fi bucla
din nou și s-ar spune, OK, j este 1 acum.

1689
01:12:57,960 --> 01:13:00,665
Și matrice j minus 1 este acum 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Este mai mică de 2 elementul nostru?

1692
01:13:03,760 --> 01:13:04,540
Nu?

1693
01:13:04,540 --> 01:13:07,970
Asta înseamnă că ne-am
introduce acest element

1694
01:13:07,970 --> 01:13:10,110
în locul corect în oferta noastră sortat.

1695
01:13:10,110 --> 01:13:14,400
Atunci putem lua acest lucru și spunem,
OK, oferta noastră este sortat aici.

1696
01:13:14,400 --> 01:13:19,940
Și ar fi nevoie de acest număr de 6 și de a fi
cum ar fi, OK, este de 6 la mai puțin de acest număr?

1697
01:13:19,940 --> 01:13:20,480
Nu?

1698
01:13:20,480 --> 01:13:21,080
Rece.

1699
01:13:21,080 --> 01:13:22,680
Suntem bine.

1700
01:13:22,680 --> 01:13:23,530
>> Fă-o din nou.

1701
01:13:23,530 --> 01:13:24,740
Noi spunem 7.

1702
01:13:24,740 --> 01:13:29,010
Este mai puțin de 7 la sfârșitul
din oferta noastră sortate?

1703
01:13:29,010 --> 01:13:29,520
Nu.

1704
01:13:29,520 --> 01:13:30,430
Deci, suntem bine.

1705
01:13:30,430 --> 01:13:32,760
Deci, acest lucru ar fi sortate.

1706
01:13:32,760 --> 01:13:38,610
Practic toate acest lucru nu
Este o spune decolare

1707
01:13:38,610 --> 01:13:42,060
primul element al
matrice dumneavoastră nesortate,

1708
01:13:42,060 --> 01:13:46,010
da seama unde se duce
în matrice ta sortat.

1709
01:13:46,010 --> 01:13:48,780
Și aceasta are doar grijă
de swap-uri pentru a face asta.

1710
01:13:48,780 --> 01:13:51,300
Ești practic doar schimbarea
până când este în locul potrivit.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Imaginea vizuală este că ești
în mișcare totul de a face asta.

1713
01:13:56,990 --> 01:13:59,420
>> Deci e ca și cum jumătate bubble sort-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Check out studiu 50.

1716
01:14:03,420 --> 01:14:06,000
Am foarte recomandăm să încercați
pentru a coda acest lucru pe cont propriu.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Dacă aveți probleme sau doriți să
a se vedea mostre de cod pentru un fel de introducere,

1719
01:14:12,450 --> 01:14:13,750
vă rog să-mi spuneți.

1720
01:14:13,750 --> 01:14:14,500
Eu sunt mereu în jurul valorii de.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Deci, cel mai rău caz de execuție
și cel mai bun caz rulare.

1723
01:14:20,200 --> 01:14:30,700
După cum ați văzut tip din tabelul I deja
ți-a arătat, e atât n pătrat și n.

1724
01:14:30,700 --> 01:14:35,590
>> Deci, un fel de a merge în afara a ceea ce am discutat
despre felul cu noastre anterioare, cel mai rău

1725
01:14:35,590 --> 01:14:38,760
rulare caz este că, dacă
este complet nesortate,

1726
01:14:38,760 --> 01:14:42,530
trebuie să ne comparăm toate aceste n ori.

1727
01:14:42,530 --> 01:14:47,020
Noi facem o mulțime de comparații
pentru că dacă e în ordine inversă,

1728
01:14:47,020 --> 01:14:50,360
vom spune, OK, acest
este același, acest lucru este bun,

1729
01:14:50,360 --> 01:14:54,650
iar acesta va trebui să fie comparate
față de prima care urmează să fie mutat înapoi.

1730
01:14:54,650 --> 01:14:56,710
Și cum vom ajunge spre
coada, avem

1731
01:14:56,710 --> 01:14:59,440
pentru a compara, compara, și
compara împotriva a tot.

1732
01:14:59,440 --> 01:15:03,030
>> Deci, se termină prin a fi
aproximativ n pătrat.

1733
01:15:03,030 --> 01:15:09,510
Dacă este corect, atunci
spune, OK, 2, ești bun.

1734
01:15:09,510 --> 01:15:11,330
3, esti față de 2.

1735
01:15:11,330 --> 01:15:12,310
Esti bun.

1736
01:15:12,310 --> 01:15:14,150
4, pe care tocmai ați compara cu coada.

1737
01:15:14,150 --> 01:15:14,990
Esti bun.

1738
01:15:14,990 --> 01:15:17,140
6, compara cu coada, ești bine.

1739
01:15:17,140 --> 01:15:20,870
Deci, pentru fiecare punct în cazul în care este deja
sortate, faci o comparație.

1740
01:15:20,870 --> 01:15:22,320
Deci, e doar n.

1741
01:15:22,320 --> 01:15:26,840
Și pentru că avem o execuție cel mai bun caz
de n și un caz de execuție cel mai rău de n-

1742
01:15:26,840 --> 01:15:28,680
pătrat, nu avem nici o execuție de așteptat,.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Este doar depinde de
haos de pe lista noastră de acolo.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Și din nou, o altă
grafic și o altă masă.

1747
01:15:39,530 --> 01:15:41,170
Deci, diferențele dintre soiuri.

1748
01:15:41,170 --> 01:15:44,180
Mă duc să briza prin, eu
simt ca am vorbit pe larg

1749
01:15:44,180 --> 01:15:46,570
cu privire la modul în care acestea tot felul
de varia și link-ul împreună.

1750
01:15:46,570 --> 01:15:50,564
Deci, Merge sort este ultima
Eu vă va plictisesc cu voi.

1751
01:15:50,564 --> 01:15:52,105
Avem o imagine destul de colorat.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Deci, îmbinare fel este un algoritm recursiv.

1754
01:15:56,040 --> 01:15:59,910
Deci, nu știu voi ce
o funcție recursivă este?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Oricine vrea să spun?

1757
01:16:03,320 --> 01:16:04,739
Vrei să încerci?

1758
01:16:04,739 --> 01:16:07,280
Deci, o functie recursiva este doar
o funcție care se numește.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Deci, dacă voi sunt familiarizați
cu șirul lui Fibonacci,

1761
01:16:11,590 --> 01:16:15,670
care este considerat recursiv pentru că
luați cele două precedent

1762
01:16:15,670 --> 01:16:17,530
și adăugați-le împreună
pentru a obține o următoare.

1763
01:16:17,530 --> 01:16:21,440
Așa că recursiv, întotdeauna mă gândesc
de recursivitate ca ca o spirală

1764
01:16:21,440 --> 01:16:24,430
deci esti la fel ca în spirală în jos în ea.

1765
01:16:24,430 --> 01:16:27,150
Dar e doar o funcție
care se numește.

1766
01:16:27,150 --> 01:16:32,660
>> Și, de fapt, foarte repede am
vă pot arăta cum arată.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Așa că recursiv aici, dacă ne uităm, aceasta este
modul recursiv pentru a rezuma pe o matrice.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Deci, tot ceea ce facem este
avem funcția sumă

1771
01:16:47,880 --> 01:16:52,210
suma care ia o dimensiune și o serie.

1772
01:16:52,210 --> 01:16:55,210
Și dacă observați, dimensiune
diminuări de către o de fiecare dată.

1773
01:16:55,210 --> 01:17:00,365
Și tot ce face este dacă x este egal cu
zero-- astfel încât în ​​cazul în care dimensiunea de matrice

1774
01:17:00,365 --> 01:17:02,710
este egal cu zero-- revine la zero.

1775
01:17:02,710 --> 01:17:10,440
>> În caz contrar, rezumă acest
ultimul element al tabloului,

1776
01:17:10,440 --> 01:17:14,790
și apoi ia o sumă de
restul de matrice.

1777
01:17:14,790 --> 01:17:17,555
Deci, e doar o rupere jos
problemă ce mai mici.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Pe scurt, recursivitate,
funcție care se numește.

1780
01:17:21,890 --> 01:17:25,740
Dacă asta e tot ce ai de acest lucru,
asta e ceea ce o functie recursiva este.

1781
01:17:25,740 --> 01:17:29,870
Dacă luați 51, veți primi foarte,
foarte confortabil cu recursivitate.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
E foarte misto.

1784
01:17:32,370 --> 01:17:34,660
Ea a făcut sens la fel ca
3 AM o noapte afară.

1785
01:17:34,660 --> 01:17:37,900
Și am fost ca, de ce
niciodată nu am folosi acest lucru?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Deci, pentru îmbinare fel, practic
ceea ce va face este că e

1788
01:17:42,430 --> 01:17:45,620
O să-l rupe în jos și-l
în jos până când este elemente doar de o persoană.

1789
01:17:45,620 --> 01:17:47,570
Singurele elemente sunt ușor pentru a sorta.

1790
01:17:47,570 --> 01:17:48,070
Vedem că.

1791
01:17:48,070 --> 01:17:50,760
Dacă aveți un element, e
deja luate în considerare sortat.

1792
01:17:50,760 --> 01:17:53,800
Deci, pe o intrare de n elemente,
dacă n este mai mică de 2,

1793
01:17:53,800 --> 01:17:58,120
a reveni doar pentru că mijloacele
e 0 sau 1 după cum am văzut.

1794
01:17:58,120 --> 01:18:00,050
Acestea sunt considerate elemente sortate.

1795
01:18:00,050 --> 01:18:02,170
>> În caz contrar, rupe în două.

1796
01:18:02,170 --> 01:18:06,336
Sortare în prima jumătate a anului, sortare a doua
jumătate, iar apoi îmbinați-le împreună.

1797
01:18:06,336 --> 01:18:07,460
De ce se numește îmbinare fel.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Deci avem aici ne vom sorta aceste.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Așa că am ține cu ei
până la dimensiunea matrice este 1.

1802
01:18:17,210 --> 01:18:20,790
Deci, atunci când este 1, doar ne vom întoarce
pentru că aceasta este o matrice sortat,

1803
01:18:20,790 --> 01:18:23,940
și aceasta este o matrice sortat, și asta e
o gamă sortat, suntem sortate toți.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Deci, atunci ceea ce facem este noi
începe comasarea lor împreună.

1806
01:18:29,420 --> 01:18:31,820
>> Deci, modul în care se poate
cred despre fuziune este

1807
01:18:31,820 --> 01:18:36,240
doar să eliminați mai mici
număr de fiecare dintre sub matricelor

1808
01:18:36,240 --> 01:18:38,330
și doar adăuga la matrice a apărut.

1809
01:18:38,330 --> 01:18:44,290
Deci, dacă te uiți aici, când ne-am
aceste seturi avem 4, 6, și 1.

1810
01:18:44,290 --> 01:18:47,280
Când vrem să fuzioneze acestora,
ne uităm la aceste primele două

1811
01:18:47,280 --> 01:18:50,730
și spunem, OK, 1 este mai mic,
merge în față.

1812
01:18:50,730 --> 01:18:54,330
4 și 6, nu e nimic pentru comparare
l, doar eticheta de pe până la capăt.

1813
01:18:54,330 --> 01:18:58,020
>> Când ne-am combina aceste două, ne-am
să ia cea mai mică dintre acestea două,

1814
01:18:58,020 --> 01:18:59,310
asa ca e 1.

1815
01:18:59,310 --> 01:19:01,690
Și acum vom lua
mai mic de aceste două, așa 2.

1816
01:19:01,690 --> 01:19:03,330
Micșorează dintre acestea două, trei.

1817
01:19:03,330 --> 01:19:06,260
Mai mic de aceste două, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Deci, esti doar trăgând de pe acestea.

1819
01:19:08,630 --> 01:19:11,210
Și pentru că am
fost sortate în prealabil,

1820
01:19:11,210 --> 01:19:14,300
trebuie doar un singur
Compară de fiecare dată acolo.

1821
01:19:14,300 --> 01:19:19,610
Deci, mai mult cod aici, reprezentare doar.

1822
01:19:19,610 --> 01:19:24,410
Deci, tu încep de la mijloc și
tu sortare stânga și dreapta

1823
01:19:24,410 --> 01:19:26,180
și apoi doar să îmbinați cele.

1824
01:19:26,180 --> 01:19:30,080
>> Și nu avem cod
pentru a intra aici.

1825
01:19:30,080 --> 01:19:34,110
Dar, din nou, dacă te duci pe
studia 50, va fi acolo.

1826
01:19:34,110 --> 01:19:36,860
În caz contrar, vin să vorbești cu mine
dacă ești încă confuz.

1827
01:19:36,860 --> 01:19:42,340
Deci, lucru misto aici este faptul că cel mai bun caz,
cel mai rău caz, și de execuție de așteptat

1828
01:19:42,340 --> 01:19:46,250
sunt toate în log n, care
este mult mai bine decât ne-am

1829
01:19:46,250 --> 01:19:48,000
văzut pentru restul de felul noastre.

1830
01:19:48,000 --> 01:19:51,840
Am văzut n patrat
și ceea ce suntem de fapt

1831
01:19:51,840 --> 01:19:54,380
ajunge aici este n log n, care este mare.

1832
01:19:54,380 --> 01:19:55,830
>> Uită-te la cât de mult mai bine, care este.

1833
01:19:55,830 --> 01:19:56,780
O curbă frumos.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Deci, mult mai eficient.

1836
01:20:00,120 --> 01:20:03,510
Daca ai putea vreodată, utilizarea îmbinare fel.

1837
01:20:03,510 --> 01:20:04,810
Se va economisi timp.

1838
01:20:04,810 --> 01:20:07,670
Apoi, din nou, așa cum am spus, în cazul în care
ești în această regiune mai mic,

1839
01:20:07,670 --> 01:20:09,480
ea nu face asta
de mult de o diferență.

1840
01:20:09,480 --> 01:20:11,360
Ai până la mii
și mii de intrări,

1841
01:20:11,360 --> 01:20:13,318
vrei cu siguranta un
algoritm mai eficient.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Și, din nou, masa noastră minunat de toate
felul asta voi învățat astăzi.

1844
01:20:19,400 --> 01:20:21,157
>> Deci, eu știu că a fost o zi dens.

1845
01:20:21,157 --> 01:20:23,490
Acest lucru nu este neapărat de gând
pentru a vă ajuta cu PSET ta.

1846
01:20:23,490 --> 01:20:28,250
Dar eu vreau doar să facă o declarație de renunțare
această secțiune nu este doar despre psets.

1847
01:20:28,250 --> 01:20:31,240
Toate acest material este corect
joc pentru examenele tale.

1848
01:20:31,240 --> 01:20:35,430
Și, de asemenea, dacă faci continua cu CS,
acestea sunt fundamentale într-adevăr importante

1849
01:20:35,430 --> 01:20:37,870
care le-ar trebui să știi.

1850
01:20:37,870 --> 01:20:41,700
Deci, câteva zile va fi o
puțin mai mult PSET ajutor,

1851
01:20:41,700 --> 01:20:44,600
dar câteva săptămâni va fi
conținut mult mai real

1852
01:20:44,600 --> 01:20:46,600
care nu poate părea super-
util pentru tine acum,

1853
01:20:46,600 --> 01:20:51,215
dar îți promit, dacă veți continua
pe va fi foarte, foarte util.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Deci asta e pentru secțiunea.

1856
01:20:54,250 --> 01:20:55,250
Jos pentru firul.

1857
01:20:55,250 --> 01:20:56,570
Am făcut-o într-un minut.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Dar acolo te duci.

1860
01:20:58,970 --> 01:21:01,240
Și voi avea gogoși sau bomboane.

1861
01:21:01,240 --> 01:21:03,464
Este cineva alergic la
ceva, apropo?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Ouă și lapte.

1864
01:21:05,890 --> 01:21:08,120
Deci, gogoși sunt un nu?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Bine.

1868
01:21:10,770 --> 01:21:12,120
Ciocolata nu?

1869
01:21:12,120 --> 01:21:12,620
Explozii stelare.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts sunt bune.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Vom avea
Accelerarea săptămâna viitoare atunci.

1874
01:21:17,045 --> 01:21:18,240
Asta e ceea ce voi primi.

1875
01:21:18,240 --> 01:21:19,690
Voi avea o săptămână mare.

1876
01:21:19,690 --> 01:21:20,460
Citește spec ta.

1877
01:21:20,460 --> 01:21:22,130
>> Lasă-mă să știu dacă aveți întrebări.

1878
01:21:22,130 --> 01:21:25,300
PSET două clase ar trebui să fie
la tine de joi.

1879
01:21:25,300 --> 01:21:28,320
Dacă aveți orice întrebări
despre cum am sortat ceva

1880
01:21:28,320 --> 01:21:32,250
sau de ce am clasificate ceva modul în care am
a, vă rugăm să mi e-mail, vin să vorbească cu mine.

1881
01:21:32,250 --> 01:21:34,210
Sunt un pic acest nebun
săptămână, dar îți promit

1882
01:21:34,210 --> 01:21:36,340
Voi răspunde în continuare în termen de 24 de ore.

1883
01:21:36,340 --> 01:21:38,240
Deci, au o săptămână mare, toată lumea.

1884
01:21:38,240 --> 01:21:40,090
Mult noroc pe PSET ta.

1885
01:21:40,090 --> 01:21:41,248