1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Redarea muzicii]

3
00:00:10,800 --> 00:00:13,500
DAVID MALAN: În regulă.

4
00:00:13,500 --> 00:00:14,670
Bine, bine ai revenit.

5
00:00:14,670 --> 00:00:18,120
Deci, aceasta este Săptămâna 4, la început
acestuia, deja.

6
00:00:18,120 --> 00:00:21,320
Și veți aminti că săptămâna trecută, am pus
cod deoparte pentru doar un pic

7
00:00:21,320 --> 00:00:24,240
și am început să vorbim un pic mai mult
la nivel înalt, despre lucruri cum ar fi

8
00:00:24,240 --> 00:00:28,130
căutarea și sortarea, care, deși
idei oarecum simple, sunt

9
00:00:28,130 --> 00:00:31,840
reprezentant al unei clase de probleme
va începe să rezolve în special

10
00:00:31,840 --> 00:00:34,820
cum începi să te gândești finală
proiecte și soluții interesante pe care le

11
00:00:34,820 --> 00:00:36,760
ar putea avea probleme din lumea reală.

12
00:00:36,760 --> 00:00:39,490
Acum, un fel balon a fost una dintre cele mai simple
astfel de algoritmi, și

13
00:00:39,490 --> 00:00:42,900
lucrate de a avea aceste numere mici
într-o listă sau într-un fel serie de

14
00:00:42,900 --> 00:00:46,530
bule modul lor de până la partea de sus, și
numere mari muta drumul lor până la

15
00:00:46,530 --> 00:00:47,930
la sfârșitul acestei liste.

16
00:00:47,930 --> 00:00:50,650
>> Și amintesc că am putea vizualiza
bubble fel un pic

17
00:00:50,650 --> 00:00:52,310
ceva de genul asta.

18
00:00:52,310 --> 00:00:53,640
Așa că lasă-mă să merg mai departe și faceți clic pe Start.

19
00:00:53,640 --> 00:00:55,350
Am preselectate fel bule.

20
00:00:55,350 --> 00:00:58,920
Și dacă vă amintiți că albastru inalt
Liniile reprezintă numere mari, mici,

21
00:00:58,920 --> 00:01:03,300
liniile albastre reprezintă un număr mic, ca
trecem prin asta din nou și din nou și

22
00:01:03,300 --> 00:01:07,680
din nou, compararea a două bare de lângă fiecare
altele în roșu, vom schimba

23
00:01:07,680 --> 00:01:11,010
cel mai mare și cel mai mic în cazul în care
ele sunt în ordine.

24
00:01:11,010 --> 00:01:14,150
>> Deci, acest lucru va continua și du-te pe și du-te
pe, și veți vedea că mai mare

25
00:01:14,150 --> 00:01:16,700
Elementele fac drumul lor spre
dreapta, iar elementele sunt mai mici

26
00:01:16,700 --> 00:01:17,900
face drumul lor spre stânga.

27
00:01:17,900 --> 00:01:21,380
Dar am început să cuantifice
eficiența,

28
00:01:21,380 --> 00:01:22,970
Calitatea acestui algoritm.

29
00:01:22,970 --> 00:01:25,200
Și am spus că, în cel mai rău
caz, acest algoritm luat

30
00:01:25,200 --> 00:01:27,940
aproximativ câți pași?

31
00:01:27,940 --> 00:01:28,980
>> Deci, n pătrat.

32
00:01:28,980 --> 00:01:30,402
Și ce a fost n?

33
00:01:30,402 --> 00:01:31,650
>> Audiența: Numărul de elemente.

34
00:01:31,650 --> 00:01:32,790
>> DAVID MALAN: Deci, n fost
număr de elemente.

35
00:01:32,790 --> 00:01:33,730
Și așa vom face acest lucru de multe ori.

36
00:01:33,730 --> 00:01:36,650
În orice moment vrem să vorbim despre dimensiunea
a unei probleme sau dimensiunea unei

37
00:01:36,650 --> 00:01:39,140
de intrare, sau cantitatea de timp este nevoie
pentru a produce ieșire, vom doar

38
00:01:39,140 --> 00:01:41,610
generalizată indiferent de
intrare este ca n.

39
00:01:41,610 --> 00:01:45,970
Deci, înapoi în Săptămâna 0, pagini numărul
în cartea de telefon a fost n.

40
00:01:45,970 --> 00:01:47,550
Numărul de studenți
în cameră a fost n.

41
00:01:47,550 --> 00:01:49,630
Deci, aici, de asemenea, suntem în urma
ca model.

42
00:01:49,630 --> 00:01:52,800
>> Acum n pătrat nu este deosebit
repede, așa că am încercat să facem mai bine.

43
00:01:52,800 --> 00:01:55,970
Și așa ne-am uitat la o pereche de
alte algoritmi, printre care

44
00:01:55,970 --> 00:01:57,690
au fost un fel de selecție.

45
00:01:57,690 --> 00:01:59,180
Deci, un fel de selecție a fost
un pic diferit.

46
00:01:59,180 --> 00:02:03,130
Era aproape simplu, îndrăznesc să spun,
prin care am început la începutul

47
00:02:03,130 --> 00:02:06,740
Lista de voluntarii noștri și am din nou
și din nou și din nou a trecut printr-

48
00:02:06,740 --> 00:02:10,060
lista, smulgeau cel mai mic
Elementul la un moment dat și punerea lui sau

49
00:02:10,060 --> 00:02:13,040
ei la începutul listei.

50
00:02:13,040 --> 00:02:16,410
>> Dar acest lucru, de asemenea, odată ce am început să mă gândesc
prin matematica și mai mare

51
00:02:16,410 --> 00:02:19,860
imagine, gândit de câte ori
Am fost de gând înainte și înapoi și înapoi

52
00:02:19,860 --> 00:02:24,090
și mai departe, am spus în cel mai rău caz,
un fel de selecție, de asemenea, ceea ce a fost?

53
00:02:24,090 --> 00:02:24,960
n patrat.

54
00:02:24,960 --> 00:02:27,490
Acum, în lumea reală, s-ar putea
de fapt, să fie marginal mai repede.

55
00:02:27,490 --> 00:02:30,620
Pentru că din nou, nu am avut de a păstra
revenire odată ce am sortat

56
00:02:30,620 --> 00:02:31,880
mai mici elemente.

57
00:02:31,880 --> 00:02:35,090
Dar dacă ne gândim foarte mare n, și
Dacă aveți un fel de face din matematica ca

58
00:02:35,090 --> 00:02:39,170
Am făcut-o de pe bord, cu pătrate n
ceva minus, orice altceva

59
00:02:39,170 --> 00:02:41,850
Pe langa n pătrat, o dată n
devine foarte mare, nu

60
00:02:41,850 --> 00:02:42,850
într-adevăr contează la fel de mult.

61
00:02:42,850 --> 00:02:45,470
Deci, ca oameni de știință de calculator, am un fel de
închide ochii la cel mai mic

62
00:02:45,470 --> 00:02:49,220
factori și să se concentreze doar pe factorul de
o expresie care va face

63
00:02:49,220 --> 00:02:50,330
cea mai mare diferenta.

64
00:02:50,330 --> 00:02:52,840
>> Ei bine, în cele din urmă, ne-am uitat
la fel de inserție.

65
00:02:52,840 --> 00:02:56,620
Și acest lucru a fost similară în spirit, dar
mai degrabă decât trece prin iterativ și

66
00:02:56,620 --> 00:03:01,250
selectați mai mic element unul la un
timp, am luat în schimb de o parte că am

67
00:03:01,250 --> 00:03:04,070
a fost ocupat, și am decis, toate
Bine, e aici.

68
00:03:04,070 --> 00:03:06,160
Apoi am trecut la urmatorul element
și a decis că el sau

69
00:03:06,160 --> 00:03:07,470
ea aparținea aici.

70
00:03:07,470 --> 00:03:08,810
Și apoi m-am mutat pe și de pe.

71
00:03:08,810 --> 00:03:11,780
Și eu s-ar putea să, de-a lungul drum,
schimba astia, în scopul de a

72
00:03:11,780 --> 00:03:13,030
face loc pentru ei.

73
00:03:13,030 --> 00:03:16,880
Astfel că a fost un fel de inversare mentale
de fel de selecție pe care le

74
00:03:16,880 --> 00:03:18,630
numit un fel de inserare.

75
00:03:18,630 --> 00:03:20,810
>> Astfel încât aceste subiecte să apară
în lumea reală.

76
00:03:20,810 --> 00:03:23,640
În urmă cu doar câțiva ani, atunci când o anumită
Senatorul a fost de funcționare pentru președinte,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, în momentul în care CEO-ul de
Google, de fapt a avut ocazia

78
00:03:27,160 --> 00:03:28,040
să-l interviu.

79
00:03:28,040 --> 00:03:32,010
Și ne-am gândit împărtășesc această YouTube
clip pentru tine aici, dacă am putea întoarce

80
00:03:32,010 --> 00:03:32,950
volum.

81
00:03:32,950 --> 00:03:39,360
>> [Redare video]

82
00:03:39,360 --> 00:03:44,620
>> -Acum, senator, esti aici de la Google,
și îmi place să cred că a Președinției

83
00:03:44,620 --> 00:03:46,042
ca un interviu de angajare.

84
00:03:46,042 --> 00:03:47,770
>> [Râsete]

85
00:03:47,770 --> 00:03:50,800
>> -Acum, este greu pentru a obține
un loc de muncă în calitate de președinte.

86
00:03:50,800 --> 00:03:52,480
Și te duci prin
rigorile acum.

87
00:03:52,480 --> 00:03:54,330
Este, de asemenea, greu pentru a obține un loc de muncă la Google.

88
00:03:54,330 --> 00:03:59,610
Avem întrebări și vom cere
noastre întrebări candidaților.

89
00:03:59,610 --> 00:04:02,250
Și aceasta este de la Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Râsete]

91
00:04:05,325 --> 00:04:06,400
-Voi credeți că glumesc?

92
00:04:06,400 --> 00:04:08,750
Este chiar aici.

93
00:04:08,750 --> 00:04:12,110
Care este cel mai eficient mod de a
sorta un milion de numere întregi de doi bani?

94
00:04:12,110 --> 00:04:15,810
>> [Râsete]

95
00:04:15,810 --> 00:04:18,260
>> -Ei bine, uh -

96
00:04:18,260 --> 00:04:19,029
>> -Îmi pare rău.

97
00:04:19,029 --> 00:04:19,745
Poate ar trebui -

98
00:04:19,745 --> 00:04:21,000
>> -Nu, nu, nu, nu, nu.

99
00:04:21,000 --> 00:04:21,470
>> -Asta nu-i o -

100
00:04:21,470 --> 00:04:22,185
OK.

101
00:04:22,185 --> 00:04:25,328
>> -Cred că genul bubble ar fi
fie în mod greșit de a merge.

102
00:04:25,328 --> 00:04:26,792
>> [Râsete]

103
00:04:26,792 --> 00:04:28,510
>> [Urale și aplauze]

104
00:04:28,510 --> 00:04:31,211
>> -Haide, care l-a spus asta?

105
00:04:31,211 --> 00:04:32,155
OK.

106
00:04:32,155 --> 00:04:33,350
>> [END redare video]

107
00:04:33,350 --> 00:04:35,070
>> DAVID MALAN: Deci nu-l ai.

108
00:04:35,070 --> 00:04:39,600
Așa că am început să cuantifice aceste funcționare
ori, ca să spunem așa, cu ceva

109
00:04:39,600 --> 00:04:43,480
numită notația asimptotică, care este
doar referindu-se la fel nostru de a transforma

110
00:04:43,480 --> 00:04:47,420
ochii la aceste elemente mai mici și
doar uita la timpul de execuție,

111
00:04:47,420 --> 00:04:51,250
performanța acestor algoritmi,
când n devine foarte mare în timp.

112
00:04:51,250 --> 00:04:55,110
Și așa am introdus de mare O. Și Big O
a reprezentat ceva ce ne-am gandit

113
00:04:55,110 --> 00:04:57,000
a ca o limită superioară.

114
00:04:57,000 --> 00:04:59,570
Și, de fapt, Barry, putem reduce
decât MIC un pic?

115
00:04:59,570 --> 00:05:01,040
>> Ne-am gândit acest lucru este o limită superioară.

116
00:05:01,040 --> 00:05:04,710
Deci Big O de n mijloace pătrat care, în
cel mai rău caz, ceva de genul

117
00:05:04,710 --> 00:05:07,780
un fel de selecție va avea
n pași pătrat.

118
00:05:07,780 --> 00:05:10,310
Sau ceva de genul fel de inserare
ar fi n pași pătrat.

119
00:05:10,310 --> 00:05:15,150
Acum, pentru ceva de genul inserare
un fel, ceea ce a fost cel mai rău caz?

120
00:05:15,150 --> 00:05:18,200
Având în vedere o gamă largă, ceea ce e cel mai rău
posibil scenariu pe care le-ar putea găsi

121
00:05:18,200 --> 00:05:20,650
te confruntă cu?

122
00:05:20,650 --> 00:05:21,860
>> Este complet invers, nu?

123
00:05:21,860 --> 00:05:24,530
Pentru că dacă e complet invers,
ce trebuie să faci o mulțime de muncă.

124
00:05:24,530 --> 00:05:26,420
Pentru că dacă ești complet înapoi,
ai de gând să găsească

125
00:05:26,420 --> 00:05:28,840
Cel mai mare element de aici, chiar dacă
acesta face parte acolo.

126
00:05:28,840 --> 00:05:31,140
Deci, ai de gând să spui, bine, la
acest moment în timp, vă aparțin aici,

127
00:05:31,140 --> 00:05:32,310
astfel încât să-l lase în pace.

128
00:05:32,310 --> 00:05:35,425
>> Apoi îți dai seama, oh, la naiba, trebuie să
muta acest element ușor mai mici la

129
00:05:35,425 --> 00:05:36,470
stânga de tine.

130
00:05:36,470 --> 00:05:38,770
Atunci am să fac asta din nou
și din nou și din nou.

131
00:05:38,770 --> 00:05:41,410
Și dacă am mers înainte și înapoi, te
ar fi un fel de simt performanței

132
00:05:41,410 --> 00:05:45,540
că algoritmul, pentru că mereu sunt eu
amestecarea oricine altcineva în

133
00:05:45,540 --> 00:05:46,510
matrice pentru a face loc pentru ea.

134
00:05:46,510 --> 00:05:47,750
Deci, asta e cel mai rau caz.

135
00:05:47,750 --> 00:05:48,570
>> Prin contrast -

136
00:05:48,570 --> 00:05:50,320
și acest lucru a fost un Cliffhanger ultima dată -

137
00:05:50,320 --> 00:05:54,065
am spus că un fel de inserție
a fost un omega de ce?

138
00:05:54,065 --> 00:05:57,530
Ce-i de rulare cel mai bun caz
timp de fel de insertie?

139
00:05:57,530 --> 00:05:58,520
Deci, de fapt n.

140
00:05:58,520 --> 00:06:00,980
Care a fost martor că am plecat
pe placa de ultima dată.

141
00:06:00,980 --> 00:06:03,160
>> Și e omega de n, deoarece de ce?

142
00:06:03,160 --> 00:06:06,630
Ei bine, în cel mai bun caz, ceea ce este
un fel de inserție va fi predat?

143
00:06:06,630 --> 00:06:09,830
Ei bine, o lista care este complet sortat
deja, lucrarea minimă a face.

144
00:06:09,830 --> 00:06:12,460
Dar ceea ce este elegant, despre un fel de inserție
este că, deoarece începe aici și

145
00:06:12,460 --> 00:06:15,340
decide, oh, esti numărul
unul, vă aparțin aici.

146
00:06:15,340 --> 00:06:16,970
Oh, ce noroc.

147
00:06:16,970 --> 00:06:17,740
>> Tu ești numărul doi.

148
00:06:17,740 --> 00:06:19,030
De asemenea, ti-e locul aici.

149
00:06:19,030 --> 00:06:21,010
Numărul trei, chiar mai bine,
vă aparțin aici.

150
00:06:21,010 --> 00:06:25,210
De îndată ce se ajunge la sfârșitul
pseudocod lista, pe inserție fel de

151
00:06:25,210 --> 00:06:28,010
că ne-am plimbat prin verbal
ultima dată, sa terminat.

152
00:06:28,010 --> 00:06:32,790
Dar un fel de selecție, prin contrast,
continuat să fac ce?

153
00:06:32,790 --> 00:06:35,260
>> Continuat prin lista
din nou și din nou și din nou.

154
00:06:35,260 --> 00:06:39,160
Deoarece perspectiva cheie nu a fost numai
După ce am uitat tot drumul de a

155
00:06:39,160 --> 00:06:42,500
sfârșitul listei poți fi sigur
că elementul selectat a fost

156
00:06:42,500 --> 00:06:45,560
într-adevăr, cel mai mic în prezent elementul.

157
00:06:45,560 --> 00:06:48,920
Deci, aceste diferite modele sfârșitul mentale
la cedarea unor foarte real lume

158
00:06:48,920 --> 00:06:53,130
diferențe pentru noi, precum și aceste
Diferențele teoretice asimptotice.

159
00:06:53,130 --> 00:06:56,910
>> Deci, doar pentru recapitulare, apoi, Big O de n
pătrat, am văzut o astfel de câteva

160
00:06:56,910 --> 00:06:58,350
algoritmi de până acum.

161
00:06:58,350 --> 00:06:59,580
Big O de n?

162
00:06:59,580 --> 00:07:02,870
Ce este un algoritm care ar putea
fi spus să fie Big O de n?

163
00:07:02,870 --> 00:07:06,930
În cel mai rău caz, este nevoie de
un număr liniar de pași.

164
00:07:06,930 --> 00:07:07,810
>> OK, căutare liniară.

165
00:07:07,810 --> 00:07:10,470
Și în cel mai rău caz, în cazul în care este
Elementul sunteți în căutarea pentru atunci când

166
00:07:10,470 --> 00:07:12,950
aplicarea căutare liniară?

167
00:07:12,950 --> 00:07:14,680
>> OK, în cel mai rău caz,
nu e chiar acolo.

168
00:07:14,680 --> 00:07:17,000
Sau, în al doilea cel mai rău caz, e
tot drumul în cele din urmă, care este

169
00:07:17,000 --> 00:07:18,880
plus-sau-minus o diferență cu o singură etapă.

170
00:07:18,880 --> 00:07:21,180
Deci, la sfârșitul zilei,
putem spune că e liniar.

171
00:07:21,180 --> 00:07:23,910
Big O de n-ar fi de căutare liniară,
deoarece în cel mai rău caz,

172
00:07:23,910 --> 00:07:26,610
Elementul nu e chiar acolo sau este
tot drumul la final.

173
00:07:26,610 --> 00:07:29,370
>> Ei bine, Big O de jurnal de n.

174
00:07:29,370 --> 00:07:32,760
Nu am vorbit în detaliu despre
acest lucru, dar am văzut acest lucru înainte.

175
00:07:32,760 --> 00:07:36,840
Ceea ce se execută în așa-numitele logaritmică
timp, în cel mai rău caz?

176
00:07:36,840 --> 00:07:38,500
>> Da, de căutare, astfel binar.

177
00:07:38,500 --> 00:07:42,930
Și binar de căutare în cel mai rău caz
ar putea avea elementul undeva în

178
00:07:42,930 --> 00:07:45,640
la mijloc, sau undeva
în interiorul matrice.

179
00:07:45,640 --> 00:07:48,040
Dar vi se pare doar o dată ce
împărți lista în jumătate, în

180
00:07:48,040 --> 00:07:48,940
jumătate, în jumătate, în jumătate.

181
00:07:48,940 --> 00:07:50,200
Și apoi voila, e acolo.

182
00:07:50,200 --> 00:07:52,500
Sau din nou, cel mai rău caz,
nu e chiar acolo.

183
00:07:52,500 --> 00:07:56,770
Dar tu nu știi că nu e acolo
până când un fel de a ajunge la ultima

184
00:07:56,770 --> 00:08:00,470
-cele mai de jos elemente prin înjumătățirea
și reducerea la jumătate și înjumătățirea.

185
00:08:00,470 --> 00:08:01,400
>> O mare de 1.

186
00:08:01,400 --> 00:08:03,540
Deci, am putea Big O de 2, Big O de 3.

187
00:08:03,540 --> 00:08:06,260
Oricand vrei doar un număr constant,
am doar un fel de doar simplifica

188
00:08:06,260 --> 00:08:07,280
că la fel de mare de O 1.

189
00:08:07,280 --> 00:08:10,440
Chiar dacă în cazul realist, este nevoie de
2 sau chiar 100 de pași, dacă este un

190
00:08:10,440 --> 00:08:13,680
număr constant de pași,
spunem doar Big O de 1.

191
00:08:13,680 --> 00:08:15,930
Ce este un algoritm care este
în Big O de 1?

192
00:08:15,930 --> 00:08:18,350
>> Audiența: Găsirea lungimea
a unei variabile.

193
00:08:18,350 --> 00:08:21,090
>> DAVID MALAN: Găsirea
Lungimea unei variabile?

194
00:08:21,090 --> 00:08:23,870
>> Audiența: Nu, lungimea
în cazul în care este deja sortate.

195
00:08:23,870 --> 00:08:24,160
>> DAVID MALAN: Bine.

196
00:08:24,160 --> 00:08:27,850
OK, astfel încât găsirea lungimea de ceva
dacă lungimea de acel ceva, cum ar fi

197
00:08:27,850 --> 00:08:30,020
o matrice, este stocat în unele variabile.

198
00:08:30,020 --> 00:08:33,380
Pentru că puteți citi doar variabila,
sau imprima variabila, sau

199
00:08:33,380 --> 00:08:34,960
doar acces în general, că variabila.

200
00:08:34,960 --> 00:08:37,299
Și voila, care ia timp constant.

201
00:08:37,299 --> 00:08:38,909
>> Prin contrast, cred că înapoi la zero.

202
00:08:38,909 --> 00:08:42,460
Gandeste-te la prima săptămână a C,
apel doar printf și imprimare

203
00:08:42,460 --> 00:08:46,240
ceva de pe ecran este, fără îndoială,
constanta de timp, deoarece este nevoie doar de

204
00:08:46,240 --> 00:08:50,880
un număr de cicluri de CPU pentru a arăta
că textul de pe ecran.

205
00:08:50,880 --> 00:08:52,720
Sau așteptați - nu-i așa?

206
00:08:52,720 --> 00:08:56,430
Cum altfel am putea modela
performanța de printf?

207
00:08:56,430 --> 00:09:00,420
Ar dori cineva să nu sunt de acord, că
Poate că nu e timp foarte constanta?

208
00:09:00,420 --> 00:09:03,600
În ce sens s-ar putea printf se scurge
timp, imprimarea de fapt un șir pe

209
00:09:03,600 --> 00:09:05,580
ecran, fie ceva
altele decât constanta.

210
00:09:05,580 --> 00:09:07,860
>> Audiența: [inaudibil].

211
00:09:07,860 --> 00:09:08,230
>> DAVID MALAN: Da.

212
00:09:08,230 --> 00:09:09,300
Deci, depinde de punctul nostru de vedere.

213
00:09:09,300 --> 00:09:13,390
Dacă am de fapt, cred că de intrare a
printf ca fiind șir, și

214
00:09:13,390 --> 00:09:16,380
Prin urmare, măsura dimensiunea de care
intrare prin lungimea sa - deci sa-i spunem

215
00:09:16,380 --> 00:09:17,780
ca lungime n, precum și -

216
00:09:17,780 --> 00:09:21,990
fără îndoială, printf este ea însăși Big O de n
pentru că o să te n pașii luați

217
00:09:21,990 --> 00:09:24,750
pentru a imprima fiecare dintre cei n
personaje, cel mai probabil.

218
00:09:24,750 --> 00:09:27,730
Cel puțin în măsura în care le presupune
Poate că este folosind o buclă

219
00:09:27,730 --> 00:09:28,560
sub capota.

220
00:09:28,560 --> 00:09:30,860
>> Dar ne-ar trebui să te uiți la asta
cod pentru a înțelege mai bine.

221
00:09:30,860 --> 00:09:33,650
Și într-adevăr, odată ce voi începe
analiza propriile algoritmi, vei

222
00:09:33,650 --> 00:09:34,900
literalmente face doar asta.

223
00:09:34,900 --> 00:09:37,765
Un fel de globului ocular codul și cred
despre - în regulă, am această buclă

224
00:09:37,765 --> 00:09:41,870
aici sau am un bucle imbricate aici,
care va face n lucruri de n ori,

225
00:09:41,870 --> 00:09:46,050
și se pot sorta de motiv drum
prin cod, chiar dacă este

226
00:09:46,050 --> 00:09:47,980
pseudocod și nu codul actual.

227
00:09:47,980 --> 00:09:49,730
>> Deci, ce despre omega n pătrat?

228
00:09:49,730 --> 00:09:53,582
Ce a fost un algoritm care, în cel mai bun
caz, încă n luat măsuri pătrat?

229
00:09:53,582 --> 00:09:54,014
Da?

230
00:09:54,014 --> 00:09:54,880
>> Audiența: [inaudibil].

231
00:09:54,880 --> 00:09:55,900
>> DAVID MALAN: Deci, un fel de selecție.

232
00:09:55,900 --> 00:09:59,150
Pentru că în această problemă redus într-adevăr
la faptul că, din nou, eu nu știu

233
00:09:59,150 --> 00:10:02,600
Am gasit cel mai mic curent până
Am verificat toate elementele darn.

234
00:10:02,600 --> 00:10:08,050
Deci omega de, să zicem, n, noi
tocmai a venit cu un singur.

235
00:10:08,050 --> 00:10:09,300
Un fel de inserare.

236
00:10:09,300 --> 00:10:12,370
Dacă lista se întâmplă să fie sortate
deja, în cel mai bun caz avem doar

237
00:10:12,370 --> 00:10:15,090
pentru a face o trecere prin ea,
moment în care suntem siguri.

238
00:10:15,090 --> 00:10:17,890
Și atunci care ar putea fi spus
să fie liniar, pentru sigur.

239
00:10:17,890 --> 00:10:20,570
>> Ce zici de omega 1?

240
00:10:20,570 --> 00:10:23,790
Ceea ce, în cel mai bun caz, s-ar putea să ia
un număr constant de pași?

241
00:10:23,790 --> 00:10:27,220
Căutare atât de liniar, dacă ai noroc
și elementul ce căutați

242
00:10:27,220 --> 00:10:31,000
este chiar la începutul listei,
în cazul în care este în cazul în care sunteți incepand dvs.

243
00:10:31,000 --> 00:10:33,070
liniar traversarea acestei liste.

244
00:10:33,070 --> 00:10:35,180
>> Și acest lucru este valabil de un
număr de lucruri.

245
00:10:35,180 --> 00:10:37,660
De exemplu, chiar binar
căutare este de omega 1.

246
00:10:37,660 --> 00:10:40,310
Pentru că ce dacă aveți într-adevăr darn
noroc și jart-DAB în mijlocul

247
00:10:40,310 --> 00:10:42,950
matrice este numărul
ce căutați?

248
00:10:42,950 --> 00:10:45,730
Deci, puteți obține noroc acolo, de asemenea.

249
00:10:45,730 --> 00:10:49,190
>> Acesta, în cele din urmă, omega de log n.

250
00:10:49,190 --> 00:10:52,573
Deci, n log n, nu am făcut într-adevăr
vorbesc despre încă, dar -

251
00:10:52,573 --> 00:10:53,300
>> Audiența: Merge fel?

252
00:10:53,300 --> 00:10:53,960
>> DAVID MALAN: Merge fel.

253
00:10:53,960 --> 00:10:56,920
Asta a fost Cliffhanger de ultima dată,
unde ne-am propus, și am arătat

254
00:10:56,920 --> 00:10:58,600
vizual, că există algoritmi.

255
00:10:58,600 --> 00:11:02,470
Și un fel de doar un astfel de îmbinare
algoritm care este fundamental mai rapid

256
00:11:02,470 --> 00:11:03,450
decât unele dintre aceste alți tipi.

257
00:11:03,450 --> 00:11:07,800
De fapt, îmbinare scurt este nu numai în
cel mai bun caz, n n jurnal, în cel mai rău

258
00:11:07,800 --> 00:11:09,460
cazul n n jurnal.

259
00:11:09,460 --> 00:11:14,540
Iar atunci când aveți această coincidență de
omega și mari O fi același lucru?

260
00:11:14,540 --> 00:11:17,310
Putem descrie de fapt, că în ceea ce-i
numit theta, deși este un

261
00:11:17,310 --> 00:11:18,220
mai puțin frecvente.

262
00:11:18,220 --> 00:11:21,730
Dar asta înseamnă că doar cele două limite,
în acest caz, sunt aceleași.

263
00:11:21,730 --> 00:11:25,770
>> Deci fuzioneze fel, ceea ce face acest lucru
într-adevăr se reduce la pentru noi?

264
00:11:25,770 --> 00:11:27,000
Ei bine, amintesc de motivație.

265
00:11:27,000 --> 00:11:30,340
Permiteți-mi să trag un alt animație care
nu ne-am uita la ultima dată.

266
00:11:30,340 --> 00:11:33,390
Aceasta, aceeași idee, dar
este un pic mai mare.

267
00:11:33,390 --> 00:11:36,160
Și am de gând să merg mai departe și subliniază
Primul - avem un fel de inserție pe

268
00:11:36,160 --> 00:11:39,410
stânga sus, apoi un fel de selecție,
fel balon, o serie de alte tipuri -

269
00:11:39,410 --> 00:11:42,670
coajă și rapid - pe care nu am vorbit
despre, și heap și îmbinarea fel.

270
00:11:42,670 --> 00:11:47,090
>> Deci, cel puțin să încerce să se concentreze ochii pe
primele trei din partea stângă și apoi

271
00:11:47,090 --> 00:11:49,120
fuzioneze fel atunci când fac clic
acest săgeată verde.

272
00:11:49,120 --> 00:11:51,900
Dar voi lăsa toate acestea alerga, doar pentru a
vă dau un sentiment al diversității

273
00:11:51,900 --> 00:11:53,980
algoritmi care există în lume.

274
00:11:53,980 --> 00:11:56,180
Am de gând să lase acest termen
pentru doar câteva secunde.

275
00:11:56,180 --> 00:11:59,640
Și dacă te concentrezi ochii - alege o
algoritm, se concentreze pe ea pentru doar o

276
00:11:59,640 --> 00:12:02,970
secunde - veți începe să vedeți
model care este de punere în aplicare.

277
00:12:02,970 --> 00:12:04,530
>> Merge fel, notificare, se face.

278
00:12:04,530 --> 00:12:06,430
Sort Heap, un fel rapid, coajă -

279
00:12:06,430 --> 00:12:09,480
deci se pare că am introdus trei
mai grave algoritmi de săptămâna trecută.

280
00:12:09,480 --> 00:12:12,960
Dar asta e bine că suntem aici, astăzi, pentru a
uita-te la îmbinare fel, care este unul dintre

281
00:12:12,960 --> 00:12:16,500
cele mai ușor este să se uite la, chiar
deși, probabil, va indoi mintea ta

282
00:12:16,500 --> 00:12:17,490
doar un pic.

283
00:12:17,490 --> 00:12:21,130
Aici putem vedea cât de mult
un fel de selecție e de rahat.

284
00:12:21,130 --> 00:12:24,600
>> Dar, pe de alta parte, este
foarte usor de implementat.

285
00:12:24,600 --> 00:12:28,160
Și poate pentru Set P 3, care este unul din
algoritmi ai ales să pună în aplicare

286
00:12:28,160 --> 00:12:28,960
pentru ediția standard.

287
00:12:28,960 --> 00:12:30,970
Foarte bine, perfect corect.

288
00:12:30,970 --> 00:12:35,210
>> Dar, din nou, ca n devine mare, dacă aveți
alege să pună în aplicare un algoritm mai rapid

289
00:12:35,210 --> 00:12:39,020
ca fuzioneze fel, șansele sunt în mai mare și
intrări mai mari, codul este doar

290
00:12:39,020 --> 00:12:39,800
va alerga mai repede.

291
00:12:39,800 --> 00:12:41,090
Site-ul dvs. va merge mai bine.

292
00:12:41,090 --> 00:12:42,650
Utilizatorii vor fi mai fericit.

293
00:12:42,650 --> 00:12:45,280
Și astfel există aceste efecte
de fapt, oferindu-

294
00:12:45,280 --> 00:12:47,350
ne unele gândit mai profund.

295
00:12:47,350 --> 00:12:49,990
>> Deci, haideți să aruncăm o privire la ceea ce merge
un fel este de fapt despre toate.

296
00:12:49,990 --> 00:12:52,992
Lucrul interesant este faptul că fuzionarea
fel este doar aceasta.

297
00:12:52,992 --> 00:12:56,300
Acest lucru este, din nou, ceea ce am numit
pseudocod, fiind pseudocod

298
00:12:56,300 --> 00:12:57,720
Engleză-ca sintaxa.

299
00:12:57,720 --> 00:12:59,890
Și simplitatea este
un fel de fascinant.

300
00:12:59,890 --> 00:13:02,840
>> Deci pe intrarea de n elemente - astfel încât
înseamnă doar, aici e un tablou.

301
00:13:02,840 --> 00:13:04,000
Are lucruri n în ea.

302
00:13:04,000 --> 00:13:05,370
Asta e tot ce spui acolo.

303
00:13:05,370 --> 00:13:07,560
>> Daca n este mai mic de 2, întoarce.

304
00:13:07,560 --> 00:13:08,640
Deci, asta e doar cazul trivial.

305
00:13:08,640 --> 00:13:12,580
Dacă n este mai mică de 2, atunci evident e
1 sau 0, caz în care lucru

306
00:13:12,580 --> 00:13:14,780
este deja sortat sau inexistente,
Deci, doar reveni.

307
00:13:14,780 --> 00:13:15,900
Nu e nimic de făcut.

308
00:13:15,900 --> 00:13:18,360
Deci, asta e un caz simplu de a smulge.

309
00:13:18,360 --> 00:13:20,110
>> Altfel, avem trei etape.

310
00:13:20,110 --> 00:13:23,650
Sorta jumătatea stângă a elementelor, un fel
jumătatea din dreapta a elementelor,

311
00:13:23,650 --> 00:13:26,650
și apoi îmbinați reprize sortate.

312
00:13:26,650 --> 00:13:29,400
Ceea ce este interesant aici este faptul că
Sunt un fel de punting, nu?

313
00:13:29,400 --> 00:13:32,300
Există un fel de definiție circulară
la acest algoritm.

314
00:13:32,300 --> 00:13:35,986
În ce sens este acest algoritm
circulară definiție?

315
00:13:35,986 --> 00:13:37,850
>> Audiența: [inaudibil].

316
00:13:37,850 --> 00:13:41,670
>> DAVID MALAN: Da, algoritmul meu de sortare,
două dintre măsurile sale sunt "un fel

317
00:13:41,670 --> 00:13:44,640
ceva. "Si astfel încât imploră
întrebare, ei bine, ce am de gând să utilizeze

318
00:13:44,640 --> 00:13:46,460
pentru a sorta jumătatea stângă
și jumătatea din dreapta?

319
00:13:46,460 --> 00:13:49,600
Și frumusețea aici este că, chiar dacă
din nou, acest lucru este mintea-îndoire

320
00:13:49,600 --> 00:13:54,030
parte potențial, puteți utiliza aceeași
algoritm pentru a sorta jumătatea stângă.

321
00:13:54,030 --> 00:13:54,700
>> Dar stai un minut.

322
00:13:54,700 --> 00:13:57,070
Când ți se spune pentru a sorta
jumătatea stângă, care sunt cele două

323
00:13:57,070 --> 00:13:58,240
pași va fi următorul?

324
00:13:58,240 --> 00:14:00,550
Vom sorta jumătatea stângă a
jumătatea din stânga și din dreapta

325
00:14:00,550 --> 00:14:01,420
jumătate din jumătatea stângă.

326
00:14:01,420 --> 00:14:04,430
La naiba, cum pot sorta pe cei doi
jumătăți, sau sferturi, acum?

327
00:14:04,430 --> 00:14:05,260
>> Dar e în regulă.

328
00:14:05,260 --> 00:14:07,830
Avem un algoritm de sortare aici.

329
00:14:07,830 --> 00:14:10,660
Și chiar dacă s-ar putea face griji, la
Primul este un fel de infinit

330
00:14:10,660 --> 00:14:12,780
bucla, este un ciclu care este niciodată
va termina - este de gând să

331
00:14:12,780 --> 00:14:15,770
pune capăt o dată ce se întâmplă?

332
00:14:15,770 --> 00:14:16,970
Odată n este mai mic de 2.

333
00:14:16,970 --> 00:14:19,180
Care în cele din urmă se va întâmpla,
pentru că dacă vă păstrați reducerea la jumătate și

334
00:14:19,180 --> 00:14:23,020
reducerea la jumătate de înjumătățire aceste reprize, cu siguranță
în cele din urmă ai de gând să se încheie

335
00:14:23,020 --> 00:14:25,350
cu doar 1 sau 0 elemente.

336
00:14:25,350 --> 00:14:28,500
La ce punct, acest algoritm
spune că ești terminat.

337
00:14:28,500 --> 00:14:31,020
>> Deci, adevărata magie în acest
Algoritmul pare să fie în

338
00:14:31,020 --> 00:14:33,470
acest pas final, care fuzionează.

339
00:14:33,470 --> 00:14:37,190
Această idee simplă doar fuzionează două
lucruri, asta e ceea ce se întâmplă în cele din urmă

340
00:14:37,190 --> 00:14:40,920
pentru a ne permite să rezolve o serie de,
să zicem, opt elemente.

341
00:14:40,920 --> 00:14:44,410
Deci, am opt mai multe bile de stres sus
aici, opt bucăți de hârtie, și unul

342
00:14:44,410 --> 00:14:45,500
Google Glass -

343
00:14:45,500 --> 00:14:46,140
care pot sa pastrez.

344
00:14:46,140 --> 00:14:46,960
>> [Râsete]

345
00:14:46,960 --> 00:14:48,970
>> DAVID MALAN: Dacă am putea avea opt
voluntari, și să vedem dacă putem

346
00:14:48,970 --> 00:14:51,430
juca acest lucru, așa.

347
00:14:51,430 --> 00:14:52,500
Wow, OK.

348
00:14:52,500 --> 00:14:53,565
Informatica devine distractiv.

349
00:14:53,565 --> 00:14:54,320
Bine.

350
00:14:54,320 --> 00:14:57,770
Deci, cum despre tine trei,
Cea mai mare parte acolo.

351
00:14:57,770 --> 00:14:58,580
Patru în spate.

352
00:14:58,580 --> 00:15:02,220
Și cum despre vă vom face
trei în acest rând?

353
00:15:02,220 --> 00:15:03,390
Și patru în față.

354
00:15:03,390 --> 00:15:04,920
Deci, opt, haide sus.

355
00:15:04,920 --> 00:15:12,060
>> [Râsete]

356
00:15:12,060 --> 00:15:13,450
>> DAVID MALAN: Sunt de fapt
Nu sunt sigur ce este.

357
00:15:13,450 --> 00:15:14,810
Este bile de stres?

358
00:15:14,810 --> 00:15:16,510
Lămpile de birou?

359
00:15:16,510 --> 00:15:18,650
Materialul?

360
00:15:18,650 --> 00:15:19,680
Internetul?

361
00:15:19,680 --> 00:15:20,160
>> OK.

362
00:15:20,160 --> 00:15:21,310
Deci, vin pe sus.

363
00:15:21,310 --> 00:15:22,310
Cine ar dori -

364
00:15:22,310 --> 00:15:23,570
continua sa vina sus.

365
00:15:23,570 --> 00:15:24,240
Să vedem.

366
00:15:24,240 --> 00:15:26,460
Și acest lucru vă pune în locația -

367
00:15:26,460 --> 00:15:27,940
sunteți într-o locație.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, așteptați un minut.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - oh, bine.

370
00:15:30,760 --> 00:15:31,310
În regulă, suntem bine.

371
00:15:31,310 --> 00:15:35,130
În regulă, deci toată lumea are un loc,
dar nu pe sticlă Google.

372
00:15:35,130 --> 00:15:36,475
Lasă-mă să coadă astea.

373
00:15:36,475 --> 00:15:37,115
Care e numele tău?

374
00:15:37,115 --> 00:15:37,440
>> MICHELLE: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID MALAN: Michelle?

376
00:15:38,090 --> 00:15:42,000
Bine, ai să arate ca
tocilar, dacă e în regulă.

377
00:15:42,000 --> 00:15:44,625
Ei bine, eu nu prea, cred,
pentru doar o clipă.

378
00:15:44,625 --> 00:15:45,875
În regulă, așteptare.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Am fost încercarea de a veni cu un
caz de utilizare pentru Google Glass, iar noi

381
00:15:50,950 --> 00:15:53,750
gandit ca ar fi distractiv de a face doar
acest lucru atunci când oamenii sunt pe scena.

382
00:15:53,750 --> 00:15:57,120
Vom înregistra lumea
din punctul lor de vedere.

383
00:15:57,120 --> 00:15:58,410
Bine.

384
00:15:58,410 --> 00:15:59,830
Nu este, probabil, ceea ce Google destinate.

385
00:15:59,830 --> 00:16:02,260
Bine, dacă nu te superi poartă
acest lucru pentru următorii minute incomode,

386
00:16:02,260 --> 00:16:03,150
care ar fi minunat.

387
00:16:03,150 --> 00:16:08,620
>> În regulă, deci avem aici o serie de
elemente, și care matrice, conform

388
00:16:08,620 --> 00:16:11,480
bucăți de hârtie din acesti oameni "
mâini, este în prezent nesortat.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Oh, asta e așa de ciudat.

390
00:16:12,050 --> 00:16:12,810
>> DAVID MALAN: Este destul de mult la întâmplare.

391
00:16:12,810 --> 00:16:15,760
Și într-o clipă, vom încerca
pentru punerea în aplicare a fuziona fel împreună

392
00:16:15,760 --> 00:16:17,950
și a vedea în cazul în care perspectiva cheie este.

393
00:16:17,950 --> 00:16:21,970
Și truc aici cu îmbinare fel este
ceva ce nu ne-am asumat încă.

394
00:16:21,970 --> 00:16:24,030
Avem de fapt nevoie de
spațiu suplimentar.

395
00:16:24,030 --> 00:16:26,650
Deci, ce se întâmplă să fie deosebit de
interesant despre acest lucru este faptul că acestea

396
00:16:26,650 --> 00:16:29,270
baieti sunt de gând să se miște un pic
bit, pentru că am de gând să presupunem că

397
00:16:29,270 --> 00:16:31,880
există o serie suplimentară de spațiu,
spune, chiar în spatele lor.

398
00:16:31,880 --> 00:16:34,570
>> Deci, dacă ei sunt în spatele scaunului lor,
că este matrice secundar.

399
00:16:34,570 --> 00:16:36,960
Dacă sunt așezați aici, că e
matrice primar.

400
00:16:36,960 --> 00:16:40,170
Dar aceasta este o resursă pe care o avem
nu de indatorare pana acum cu bule

401
00:16:40,170 --> 00:16:42,040
fel, cu un fel de selecție,
cu fel de insertie.

402
00:16:42,040 --> 00:16:44,600
Recall săptămâna trecută, toată lumea doar
fel de amestecate în loc.

403
00:16:44,600 --> 00:16:46,840
Ei nu au folosit nici o memorie suplimentară.

404
00:16:46,840 --> 00:16:49,310
Am făcut cameră pentru persoane cu
oamenii se deplasează în jurul.

405
00:16:49,310 --> 00:16:50,580
>> Deci, aceasta este o perspectiva cheie, de asemenea.

406
00:16:50,580 --> 00:16:53,410
E un compromis, în general, în
informatică, de resurse.

407
00:16:53,410 --> 00:16:55,800
Dacă doriți să accelereze ceva
ca timp, ai de gând să

408
00:16:55,800 --> 00:16:56,900
trebuie să plătească un preț.

409
00:16:56,900 --> 00:17:00,750
Iar una dintre aceste prețuri este foarte des
spațiu, cantitatea de memorie sau hard-

410
00:17:00,750 --> 00:17:01,700
spațiu pe disc pe care îl utilizați.

411
00:17:01,700 --> 00:17:03,640
Sau, sincer, suma
de timp programator.

412
00:17:03,640 --> 00:17:06,700
Cât de mult timp este nevoie de tine, om,
să pună în aplicare de fapt, unele mai mult

413
00:17:06,700 --> 00:17:07,829
algoritm complicat.

414
00:17:07,829 --> 00:17:09,760
Dar pentru ziua de azi, trade-off
este timp și spațiu.

415
00:17:09,760 --> 00:17:11,930
>> Deci, dacă voi putea ține doar în sus dvs.
Numerele astfel încât să putem vedea că ești

416
00:17:11,930 --> 00:17:15,839
într-adevăr, de potrivire 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Excelent.

418
00:17:16,599 --> 00:17:19,520
Așa că am de gând să încerc să orchestreze
lucruri, dacă voi putea doar

419
00:17:19,520 --> 00:17:21,800
urmeze exemplul meu aici.

420
00:17:21,800 --> 00:17:26,650
>> Așa că am de gând să pună în aplicare, în primul rând,
Primul pas al pseudocod, care este

421
00:17:26,650 --> 00:17:29,440
pe intrarea de n elemente, dacă n este
mai puțin de 2, apoi să se întoarcă.

422
00:17:29,440 --> 00:17:31,370
Evident, că nu
aplică, așa că am muta pe.

423
00:17:31,370 --> 00:17:33,340
Deci sorta jumătatea stângă a elementelor.

424
00:17:33,340 --> 00:17:36,220
Asta înseamnă că am de gând să se concentreze meu
atenție pentru o clipă la aceste

425
00:17:36,220 --> 00:17:37,310
patru tipi aici.

426
00:17:37,310 --> 00:17:39,774
Bine, ce fac viitoare fac?

427
00:17:39,774 --> 00:17:40,570
>> Audiența: Sortarea jumătatea stângă.

428
00:17:40,570 --> 00:17:42,780
>> DAVID MALAN: Deci, acum trebuie să-și rezolve
jumătatea din stânga a acestor baieti.

429
00:17:42,780 --> 00:17:45,580
Pentru ca din nou, presupune să te
Scopul este de a sorta jumătatea stângă.

430
00:17:45,580 --> 00:17:46,440
Cum faci asta?

431
00:17:46,440 --> 00:17:49,140
Doar urmați instrucțiunile, chiar
deși noi o facem din nou.

432
00:17:49,140 --> 00:17:50,160
Deci sorta jumătatea stângă.

433
00:17:50,160 --> 00:17:52,030
Acum, eu sunt de sortare acești doi tipi.

434
00:17:52,030 --> 00:17:53,563
Ce urmează?

435
00:17:53,563 --> 00:17:54,510
>> Audiența: Sortarea jumătatea stângă.

436
00:17:54,510 --> 00:17:55,460
>> DAVID MALAN: sortează jumătatea stângă.

437
00:17:55,460 --> 00:18:00,680
Deci, acum acestea, acest scaun aici,
este o listă de dimensiune 1.

438
00:18:00,680 --> 00:18:01,365
Și care e numele tău din nou?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Printesa Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID MALAN: Printesa Daisy este aici.

441
00:18:03,690 --> 00:18:07,470
Și astfel ea este deja sortate, deoarece
lista este de dimensiuni 1.

442
00:18:07,470 --> 00:18:09,490
Ce trebuie să fac viitoare?

443
00:18:09,490 --> 00:18:13,680
OK, se întoarcă, pentru că lista este de
Dimensiunea 1, care este mai mică de 2.

444
00:18:13,680 --> 00:18:14,320
Atunci, ce e următorul pas?

445
00:18:14,320 --> 00:18:17,490
Și acum trebuie să fel de
revină în mintea ta.

446
00:18:17,490 --> 00:18:19,340
>> Sorta jumătatea din dreapta, care este -

447
00:18:19,340 --> 00:18:19,570
Care e numele tău?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID MALAN: Linda.

450
00:18:20,980 --> 00:18:23,210
Și ce facem acum că
avem o listă de dimensiune 1?

451
00:18:23,210 --> 00:18:24,440
>> Audiența: retur.

452
00:18:24,440 --> 00:18:24,760
>> DAVID MALAN: grijă.

453
00:18:24,760 --> 00:18:29,540
Ne întoarcem în primul rând, iar acum a treia
pas - și dacă am un fel de-l descrie prin

454
00:18:29,540 --> 00:18:33,490
îmbrățișând cele două locuri acum, acum am
Trebuie să fuzioneze aceste două elemente.

455
00:18:33,490 --> 00:18:35,530
Deci, acum, din păcate, elementele
sunt în ordine.

456
00:18:35,530 --> 00:18:39,920
Dar asta e în cazul în care procesul de fuziune
începe să devină convingătoare.

457
00:18:39,920 --> 00:18:42,410
>> Deci, dacă voi putea sta în picioare pentru doar
o clipă, am de gând să nevoie de tine, într-un

458
00:18:42,410 --> 00:18:44,170
clipă, să-și intensifice în spatele scaunului.

459
00:18:44,170 --> 00:18:46,480
Și dacă Linda, deoarece 2 este
mai mici decât 4, de ce nu

460
00:18:46,480 --> 00:18:48,130
ai venit în jurul primul?

461
00:18:48,130 --> 00:18:48,690
Stai acolo.

462
00:18:48,690 --> 00:18:50,520
Deci, Linda, ai venit în jurul primul.

463
00:18:50,520 --> 00:18:53,820
>> Acum, în realitate, dacă e doar un tablou
am putea să o mut în timp real

464
00:18:53,820 --> 00:18:55,360
Din acest scaun la acest loc.

465
00:18:55,360 --> 00:18:57,770
Imaginați-vă că a avut unele constante
număr de pași 1.

466
00:18:57,770 --> 00:18:58,480
Și acum -

467
00:18:58,480 --> 00:19:01,490
dar avem nevoie pentru a pune în
prima locatie aici.

468
00:19:01,490 --> 00:19:03,930
>> Și acum, dacă ai putea veni în jurul,
De asemenea, vom

469
00:19:03,930 --> 00:19:06,300
fie în locație două.

470
00:19:06,300 --> 00:19:09,120
Și chiar dacă acest lucru se simte ca este
a lua un timp, ceea ce e frumos acum este

471
00:19:09,120 --> 00:19:14,710
că jumătatea din stânga a
jumătate din stânga este acum sortat.

472
00:19:14,710 --> 00:19:18,010
Deci, ce a fost următorul pas, dacă ne acum
înapoi mai departe în poveste?

473
00:19:18,010 --> 00:19:18,980
>> Audiența: Jumătatea din dreapta.

474
00:19:18,980 --> 00:19:19,900
>> DAVID MALAN: Sortarea jumătatea din dreapta.

475
00:19:19,900 --> 00:19:21,320
Deci, voi avea de a face acest lucru, de asemenea.

476
00:19:21,320 --> 00:19:23,510
Deci, dacă ai putea sta în picioare
pentru o clipă?

477
00:19:23,510 --> 00:19:25,192
Și care e numele tău?

478
00:19:25,192 --> 00:19:25,540
>> JESS: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID MALAN: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, deci Jess este acum la stânga
jumătate din jumătatea dreaptă.

481
00:19:29,720 --> 00:19:31,400
Și astfel ea este o listă de dimensiune 1.

482
00:19:31,400 --> 00:19:32,380
E evident sortate.

483
00:19:32,380 --> 00:19:33,070
Și numele tău din nou?

484
00:19:33,070 --> 00:19:33,630
>> MICHELLE: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID MALAN: Michelle este, evident,
o listă de dimensiune 1.

486
00:19:35,340 --> 00:19:36,050
Ea deja sortate.

487
00:19:36,050 --> 00:19:38,690
Deci, acum magia se întâmplă,
procesul de fuziune.

488
00:19:38,690 --> 00:19:39,790
Deci, cine o să vină mai întâi?

489
00:19:39,790 --> 00:19:41,560
Evident, Michelle.

490
00:19:41,560 --> 00:19:43,280
Deci, dacă ai putea veni în spate.

491
00:19:43,280 --> 00:19:47,090
Spatiul pe care il avem la dispozitie pentru ea acum
este chiar în spatele acest scaun aici.

492
00:19:47,090 --> 00:19:51,580
Și acum, dacă ai putea veni înapoi, de asemenea,
acum avem, să fie clar, două

493
00:19:51,580 --> 00:19:53,810
jumătăți, fiecare de mărime 2 -

494
00:19:53,810 --> 00:19:57,090
și doar de dragul descrierea lui, dacă aveți
ar putea face un pic de spațiu -

495
00:19:57,090 --> 00:19:59,780
o pe jumătate aici, o
jumătate chiar aici.

496
00:19:59,780 --> 00:20:01,160
>> Derula mai departe în poveste.

497
00:20:01,160 --> 00:20:02,270
Ce pas este următorul?

498
00:20:02,270 --> 00:20:03,030
>> Audiența: Merge.

499
00:20:03,030 --> 00:20:04,160
>> DAVID MALAN: Deci, acum avem de a fuziona.

500
00:20:04,160 --> 00:20:07,490
Deci OK, deci acum, din fericire, am
doar eliberat patru scaune.

501
00:20:07,490 --> 00:20:11,480
Deci, ne-am folosit de două ori la fel de mult de memorie, dar
ne putem da flip-flop între

502
00:20:11,480 --> 00:20:12,330
cele două matrice.

503
00:20:12,330 --> 00:20:14,190
Deci, ce număr este de a veni în primul rând?

504
00:20:14,190 --> 00:20:14,850
Deci Michelle, evident.

505
00:20:14,850 --> 00:20:16,680
Deci, vin în jurul și să ia
locul aici.

506
00:20:16,680 --> 00:20:19,120
Și apoi numărul 2 este, evident,
următor, astfel încât ai venit aici.

507
00:20:19,120 --> 00:20:21,520
Numărul 4, numărul 6.

508
00:20:21,520 --> 00:20:23,390
Și din nou, chiar dacă există o
pic de mers pe jos implicat,

509
00:20:23,390 --> 00:20:26,010
într-adevăr, acestea ar putea întâmpla instantaneu,
prin mutarea unul -

510
00:20:26,010 --> 00:20:26,880
OK, bine jucat.

511
00:20:26,880 --> 00:20:28,350
>> [Râsete]

512
00:20:28,350 --> 00:20:29,680
>> DAVID MALAN: Și acum suntem
intr-o forma destul de buna.

513
00:20:29,680 --> 00:20:34,910
Jumătatea din stânga a întregii
de intrare a fost sortate.

514
00:20:34,910 --> 00:20:37,370
În regulă, deci ăștia au avut
avantajul de a mea -

515
00:20:37,370 --> 00:20:40,340
Cum a ajuns la toate fetele de pe
a plecat și toți băieții de pe dreapta?

516
00:20:40,340 --> 00:20:42,450
>> OK, deci băieților întoarce acum.

517
00:20:42,450 --> 00:20:44,680
Deci, nu te voi plimba prin
acești pași.

518
00:20:44,680 --> 00:20:46,550
Vom vedea dacă putem aplica din nou
același pseudocod.

519
00:20:46,550 --> 00:20:50,050
Dacă doriți să mergeți mai departe și se ridice în picioare,
și voi, permiteți-mi să vă dau MIC.

520
00:20:50,050 --> 00:20:52,990
Vezi dacă nu poți reproduce ceea ce
ne-am facut aici, pe

521
00:20:52,990 --> 00:20:53,880
celălalt capăt al listei.

522
00:20:53,880 --> 00:20:59,530
Cine are nevoie să vorbească în primul rând,
pe baza algoritmului?

523
00:20:59,530 --> 00:21:03,210
Deci, explica ceea ce faci înainte
de a face orice miscari picior.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: În regulă, deci din
Sunt jumătatea stângă a

525
00:21:05,930 --> 00:21:07,790
jumătatea din stânga, mă voi întoarce.

526
00:21:07,790 --> 00:21:08,730
Dreapta?

527
00:21:08,730 --> 00:21:09,250
>> DAVID MALAN: Bine.

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: Și apoi -

529
00:21:10,350 --> 00:21:11,800
>> DAVID MALAN: Cine face
MIC du-te la următorul?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: numărul următor.

531
00:21:12,920 --> 00:21:14,720
>> DIFUZOR 2: Deci, eu sunt jumătatea din dreapta
din jumătatea stângă a

532
00:21:14,720 --> 00:21:17,830
jumătatea din stânga, și mă voi întoarce.

533
00:21:17,830 --> 00:21:18,050
>> DAVID MALAN: Bine.

534
00:21:18,050 --> 00:21:18,550
Veți reveni.

535
00:21:18,550 --> 00:21:21,855
Deci, acum ce e sus, lângă pentru voi doi?

536
00:21:21,855 --> 00:21:23,740
>> DIFUZOR 2: Vrem vedem cine e mai mic.

537
00:21:23,740 --> 00:21:24,200
>> DAVID MALAN: Exact.

538
00:21:24,200 --> 00:21:24,940
Vrem să fuzioneze.

539
00:21:24,940 --> 00:21:27,590
Spatiul pe care il vom folosi pentru a fuziona
te în, chiar dacă ele sunt

540
00:21:27,590 --> 00:21:30,250
evident sortat deja, vom
să urmeze acelasi algoritm.

541
00:21:30,250 --> 00:21:31,560
Deci, cine merge in spate prima?

542
00:21:31,560 --> 00:21:35,720
Deci 3, și apoi 7.

543
00:21:35,720 --> 00:21:38,570
Și acum MIC merge
la tipii ăștia, bine?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Deci, eu sunt jumătatea din dreapta a
jumătatea din stânga, și n mea este mai mică decât

545
00:21:43,590 --> 00:21:45,048
1, așa că eu sunt doar de gând să treacă -

546
00:21:45,048 --> 00:21:46,380
>> DAVID MALAN: Bine.

547
00:21:46,380 --> 00:21:49,450
>> DIFUZOR 4: Sunt jumătatea din dreapta a
Jumătatea din dreapta a jumătatea din dreapta, și eu sunt

548
00:21:49,450 --> 00:21:51,740
De asemenea, o singură persoană, așa că eu sunt
O să se întoarcă.

549
00:21:51,740 --> 00:21:52,990
Deci, acum am îmbinare.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Deci, ne întoarcem.

552
00:21:56,150 --> 00:21:57,160
>> DAVID MALAN: Deci, te duci în spate.

553
00:21:57,160 --> 00:21:59,200
Deci 5 trece mai întâi, apoi 8.

554
00:21:59,200 --> 00:22:01,240
Și acum public, care este
pas trebuie să înapoi acum

555
00:22:01,240 --> 00:22:02,200
înapoi în mințile noastre?

556
00:22:02,200 --> 00:22:02,940
>> Audiența: Merge.

557
00:22:02,940 --> 00:22:07,270
>> DAVID MALAN: Fuziunea jumătate la stânga și la dreapta
jumătate din jumătatea stângă originale.

558
00:22:07,270 --> 00:22:08,840
Deci, acum -

559
00:22:08,840 --> 00:22:10,520
și doar pentru a face acest lucru clar,
face un pic de spațiu

560
00:22:10,520 --> 00:22:11,690
dintre voi doi.

561
00:22:11,690 --> 00:22:13,800
Deci, acum că sunt cele două liste,
stânga și dreapta.

562
00:22:13,800 --> 00:22:18,320
Deci, cum putem acum te voi merge în
primul rand de scaune din nou?

563
00:22:18,320 --> 00:22:19,600
>> 3 merge primul.

564
00:22:19,600 --> 00:22:20,850
Apoi, 5, evident.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Apoi, 7, 8 și acum.

567
00:22:27,330 --> 00:22:28,710
OK, iar acum suntem?

568
00:22:28,710 --> 00:22:29,650
>> Audiența: nu se face.

569
00:22:29,650 --> 00:22:32,440
>> DAVID MALAN: Nu sa efectuat, deoarece
evident, nu e un pas rămas.

570
00:22:32,440 --> 00:22:35,720
Dar, din nou, motivul pentru care eu sunt, folosind acest
jargon ca "înapoi în mintea ta,"

571
00:22:35,720 --> 00:22:37,160
e pentru că e într-adevăr
ceea ce se întâmplă.

572
00:22:37,160 --> 00:22:39,610
Vom trece prin toate aceste etape,
dar noi suntem un fel de pauză pentru o

573
00:22:39,610 --> 00:22:42,480
clipă, mai adânc scufundare în
algoritm, oprindu-se pentru o clipă,

574
00:22:42,480 --> 00:22:45,840
scufundări adânc în algoritmul, și
acum avem de a sorta de înapoi în noastre

575
00:22:45,840 --> 00:22:49,430
mintea și anula toate aceste straturi
că am un fel de pus în așteptare.

576
00:22:49,430 --> 00:22:51,790
>> Deci, acum avem două liste de dimensiune 4.

577
00:22:51,790 --> 00:22:54,790
Dacă voi putea sta în picioare pentru ultima dată
și să facă un pic de spațiu aici pentru a

578
00:22:54,790 --> 00:22:57,230
face clar că acest lucru este în stânga
jumătate din original,

579
00:22:57,230 --> 00:22:58,620
jumătatea dreaptă a originalului.

580
00:22:58,620 --> 00:23:01,060
Cine e primul număr pe care le
Trebuie să trage în spate?

581
00:23:01,060 --> 00:23:01,870
Michelle, desigur.

582
00:23:01,870 --> 00:23:03,230
>> Așa că am pus Michelle aici.

583
00:23:03,230 --> 00:23:05,080
Și care are numărul 2?

584
00:23:05,080 --> 00:23:06,440
Numărul 2 vine pe spate, de asemenea.

585
00:23:06,440 --> 00:23:07,800
Numărul 3?

586
00:23:07,800 --> 00:23:08,510
Excelent.

587
00:23:08,510 --> 00:23:16,570
Numărul 4, numărul 5, numărul 6,
numărul 7, și numărul 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, deci m-am simtit ca o mulțime
de pași, pentru sigur.

589
00:23:18,850 --> 00:23:22,390
Dar acum să vedem dacă nu putem confirma
un fel de intuitiv ca aceasta

590
00:23:22,390 --> 00:23:26,190
Algoritmul fundamental, în special în ceea
n devine foarte mare, așa cum am văzut

591
00:23:26,190 --> 00:23:29,170
cu animații, este
fundamental repede.

592
00:23:29,170 --> 00:23:33,400
Deci, eu susțin acest algoritm, în cel mai rău
caz și chiar și în cel mai bun caz,

593
00:23:33,400 --> 00:23:36,160
este mare O, de n ori log n.

594
00:23:36,160 --> 00:23:39,160
Că este, există un aspect al acestei
algoritm care are n trepte, dar

595
00:23:39,160 --> 00:23:43,110
există un alt aspect undeva în
că iterație, care looping, care

596
00:23:43,110 --> 00:23:44,410
ia log n pasi.

597
00:23:44,410 --> 00:23:49,154
Putem pune degetul pe ceea ce cei
două numere se referă la?

598
00:23:49,154 --> 00:23:51,320
Ei bine, în cazul în care -

599
00:23:51,320 --> 00:23:54,160
Unde MIC merge?

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1: Ar n log fi
de rupere-ne în sus, în două -

601
00:23:58,660 --> 00:23:59,630
împărțirea la doi, în esență.

602
00:23:59,630 --> 00:24:00,120
>> DAVID MALAN: Exact.

603
00:24:00,120 --> 00:24:03,000
Orice timp vom vedea în orice algoritm astfel
în prezent, nu a fost acest model de

604
00:24:03,000 --> 00:24:04,200
divizare, divizare, divizare.

605
00:24:04,200 --> 00:24:05,700
Și este de obicei redus
a ceva care este

606
00:24:05,700 --> 00:24:07,100
logaritmică, jurnal de bază 2.

607
00:24:07,100 --> 00:24:10,180
Dar ar putea fi într-adevăr nimic,
dar jurnal de bază 2.

608
00:24:10,180 --> 00:24:11,330
>> Acum, ce putem spune despre n?

609
00:24:11,330 --> 00:24:14,550
Văd că am un fel de tine divizat
baieti - te divizat, te divizat,

610
00:24:14,550 --> 00:24:15,910
ai împărțit, tu divizat.

611
00:24:15,910 --> 00:24:18,760
În cazul în care se termină provin de la?

612
00:24:18,760 --> 00:24:19,810
>> Deci, este fuziunea.

613
00:24:19,810 --> 00:24:20,610
Deoarece cred despre el.

614
00:24:20,610 --> 00:24:25,420
Când îmbinați opt oameni împreună,
prin care jumătate din ele sunt un set de patru

615
00:24:25,420 --> 00:24:27,770
iar cealaltă jumătate sunt încă
set de patru, cum te duci

616
00:24:27,770 --> 00:24:28,820
despre a face fuziunea?

617
00:24:28,820 --> 00:24:30,830
Ei bine, ați făcut-o
destul de intuitiv.

618
00:24:30,830 --> 00:24:34,140
>> Dar, dacă am făcut-o în schimb un pic mai mult
metodic, aș fi arătat la

619
00:24:34,140 --> 00:24:38,090
persoana cea mai din stânga primul cu stânga mea
parte, a subliniat la persoana din stânga

620
00:24:38,090 --> 00:24:42,080
din care jumătate cu mâna dreaptă, și
doar ulterior plimbat prin

621
00:24:42,080 --> 00:24:46,990
lista, arătând la cel mai mic element
de fiecare dată, se deplasează degetul meu de peste si

622
00:24:46,990 --> 00:24:48,970
peste cum este necesar în întreaga listă.

623
00:24:48,970 --> 00:24:51,890
Dar ceea ce este esențial despre această fuziune
Procesul este am comparat aceste perechi

624
00:24:51,890 --> 00:24:53,460
de elemente.

625
00:24:53,460 --> 00:24:57,270
Din jumătatea dreaptă și pe partea stângă,
jumătate, eu nu o dată backtracking.

626
00:24:57,270 --> 00:25:00,570
>> Astfel încât fuziunea în sine este de a lua
nu mai mult de n pași.

627
00:25:00,570 --> 00:25:03,250
Și cum de multe ori am avea
pentru a face ca fuziunea?

628
00:25:03,250 --> 00:25:07,150
Ei bine, nu mai mult de N, și ne-am
a văzut că cu îmbinare finală.

629
00:25:07,150 --> 00:25:13,120
Și dacă faci ceva care are
log n pasi n ori, sau invers,

630
00:25:13,120 --> 00:25:15,210
o să ne n ori log n da.

631
00:25:15,210 --> 00:25:16,310
>> Și de ce este asta mai bine?

632
00:25:16,310 --> 00:25:19,600
Ei bine, dacă știm deja că log
n este mai bună decât n - dreapta?

633
00:25:19,600 --> 00:25:22,590
Am văzut în căutare binară, cartea de telefon
de exemplu, log n a fost cu siguranta

634
00:25:22,590 --> 00:25:23,760
mai bine decât liniară.

635
00:25:23,760 --> 00:25:28,420
Asta înseamnă că n ori log n este
cu siguranta mai bine decât de n ori un alt

636
00:25:28,420 --> 00:25:30,390
n, AKA n pătrat.

637
00:25:30,390 --> 00:25:32,400
Și asta este ceea ce în cele din urmă am simt.

638
00:25:32,400 --> 00:25:34,928
>> Atât de mare rundă de aplauze, în cazul în care
am putea, pentru tipii ăștia.

639
00:25:34,928 --> 00:25:38,920
>> [Aplauze]

640
00:25:38,920 --> 00:25:41,550
>> DAVID MALAN: Și darurile voastre despărțire -
s-ar putea păstra numerele,

641
00:25:41,550 --> 00:25:44,010
dacă doriți.

642
00:25:44,010 --> 00:25:45,620
Și darul tău despărțire, ca de obicei.

643
00:25:45,620 --> 00:25:47,290
Oh, și vă vom trimite
imagini, Michelle.

644
00:25:47,290 --> 00:25:48,343
Mulțumesc.

645
00:25:48,343 --> 00:25:49,250
Bine.

646
00:25:49,250 --> 00:25:50,400
Serviți-vă la o minge de stres.

647
00:25:50,400 --> 00:25:54,110
>> Și lasă-mă să trageți în sus, în același timp,
prietenul nostru Rob Bowden de a oferi

648
00:25:54,110 --> 00:25:59,520
perspectivă oarecum diferită pe aceasta,
deoarece vă puteți gândi la aceste

649
00:25:59,520 --> 00:26:01,280
pași se întâmplă într-o oarecum
mod diferit.

650
00:26:01,280 --> 00:26:04,750
De fapt, set-up pentru ceea ce este Rob despre
să ne arate presupune că ne-am

651
00:26:04,750 --> 00:26:09,030
deja făcut până împărțirea a
Lista mare în opt liste mici,

652
00:26:09,030 --> 00:26:10,570
fiecare dintre mărimea 1.

653
00:26:10,570 --> 00:26:13,350
>> Deci, suntem schimbarea pseudocod o
pic doar pentru a sorta de a obține de la

654
00:26:13,350 --> 00:26:15,320
Ideea de bază de modul în care funcționează fuziunea.

655
00:26:15,320 --> 00:26:17,600
Dar timpul de funcționare a ceea ce
e pe cale să facă este încă

656
00:26:17,600 --> 00:26:19,110
va fi la fel.

657
00:26:19,110 --> 00:26:23,540
Și din nou, set-up aici este că el este
a început cu opt liste de dimensiune 1.

658
00:26:23,540 --> 00:26:27,730
Deci ai ratat partea în care e
de fapt făcut log n, n log, log n

659
00:26:27,730 --> 00:26:31,205
împărțirea de intrare.

660
00:26:31,205 --> 00:26:32,120
>> [Redare video]

661
00:26:32,120 --> 00:26:33,615
>> -Asta pentru pas cuiva.

662
00:26:33,615 --> 00:26:38,270
Pentru pasul doi, în mod repetat,
fuzioneze perechi de liste.

663
00:26:38,270 --> 00:26:39,210
>> DAVID MALAN: Hm.

664
00:26:39,210 --> 00:26:41,270
Numai audio vine
din computerul meu.

665
00:26:41,270 --> 00:26:42,520
Să încercăm din nou.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Doar arbitrar alege care -
acum avem patru liste.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Aflați mai înainte.

670
00:26:52,120 --> 00:26:53,040
>> DAVID MALAN: Acolo mergem.

671
00:26:53,040 --> 00:27:00,510
>> -Fuziunea 108 și 15, ajungem
cu lista de 15, 108.

672
00:27:00,510 --> 00:27:07,170
Fuzionarea 50 și 4, am
termina cu 4, 50.

673
00:27:07,170 --> 00:27:12,990
Fuzionarea 8 și 42, am
termina cu 8, 42.

674
00:27:12,990 --> 00:27:19,970
Și fuzionează 23 și 16, am
termina cu 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Acum, toate listele noastre sunt de dimensiuni 2.

676
00:27:23,270 --> 00:27:26,690
Observați că fiecare din
patru liste sunt sortate.

677
00:27:26,690 --> 00:27:29,450
Astfel încât să putem începe fuziunea
perechi de liste din nou.

678
00:27:29,450 --> 00:27:38,420
Fuzionarea 15 și 108 și 4 și 50, am
Primul ia 4, apoi 15, apoi

679
00:27:38,420 --> 00:27:41,500
50, apoi 108.

680
00:27:41,500 --> 00:27:50,610
Fuzionarea 8, 42 și 16, 23, vom lua
8, apoi 16, apoi 23,

681
00:27:50,610 --> 00:27:52,700
apoi 42.

682
00:27:52,700 --> 00:27:57,600
>> Așa că acum avem doar două liste de dimensiuni
4, fiecare dintre care este sortat.

683
00:27:57,600 --> 00:28:01,170
Deci, acum ne uni aceste două liste.

684
00:28:01,170 --> 00:28:11,835
În primul rând, vom lua 4, apoi vom lua
8, atunci vom lua 15, apoi 16, apoi

685
00:28:11,835 --> 00:28:19,456
23, apoi 42, apoi 50, apoi 108.

686
00:28:19,456 --> 00:28:19,872
>> [END redare video]

687
00:28:19,872 --> 00:28:23,430
>> DAVID MALAN: Din nou, notificare, el nu
atins un anumit cupa mai mult de o dată

688
00:28:23,430 --> 00:28:24,860
după avansarea dincolo de ea.

689
00:28:24,860 --> 00:28:26,200
Deci, el nu a mai repeta.

690
00:28:26,200 --> 00:28:29,850
Deci, el este mereu în mișcare la o parte,
și că este în cazul în care ne-am n noastră.

691
00:28:29,850 --> 00:28:33,290
>> De ce nu permiteți-mi trage o animație
că am văzut mai devreme, dar de data aceasta

692
00:28:33,290 --> 00:28:35,110
concentrându-se doar pe îmbinare fel.

693
00:28:35,110 --> 00:28:38,030
Lasă-mă să merg mai departe și zoom
în acest aici.

694
00:28:38,030 --> 00:28:42,530
În primul rând permiteți-mi să aleagă o intrare aleator,
amplifica aceasta, și se pot sorta a vedea

695
00:28:42,530 --> 00:28:46,600
ceea ce am luat de la sine, mai devreme,
fuzioneze fel este, de fapt face.

696
00:28:46,600 --> 00:28:50,330
>> Astfel observa că veți obține aceste jumătăți sau
aceste trimestre sau acestea optimi de

697
00:28:50,330 --> 00:28:53,140
Problema care dintr-o dată
începe să ia formă bună.

698
00:28:53,140 --> 00:28:57,070
Și apoi în cele din urmă, veți vedea la
la sfârșit că bam,

699
00:28:57,070 --> 00:28:58,860
totul este fuzionat împreună.

700
00:28:58,860 --> 00:29:01,690
>> Deci, acestea sunt doar trei diferite
ia pe aceeasi idee.

701
00:29:01,690 --> 00:29:05,980
Dar perspectiva cheie, la fel ca decalajul
și cuceri în prima clasă,

702
00:29:05,980 --> 00:29:10,640
a fost că ne-am decis să împartă cumva
problema în ceva mare, în

703
00:29:10,640 --> 00:29:14,760
ceva fel de identice în spirit,
dar mai mici și mai mici și mai mici

704
00:29:14,760 --> 00:29:15,660
și mai mici.

705
00:29:15,660 --> 00:29:18,420
>> Acum, un alt mod distractiv de a sorta de cred
despre acestea, chiar dacă nu este

706
00:29:18,420 --> 00:29:20,520
gând să vă dau același intuitiv
înțelegere, este

707
00:29:20,520 --> 00:29:21,640
animația următoare.

708
00:29:21,640 --> 00:29:25,400
Deci, acesta este un video de cineva a pus împreună
ca asociat diferite

709
00:29:25,400 --> 00:29:29,970
sunete cu diversele operațiuni de
un fel de inserție, de îmbinare fel, și

710
00:29:29,970 --> 00:29:31,150
pentru un cuplu de alții.

711
00:29:31,150 --> 00:29:32,330
Deci, într-un moment, am de gând să lovit redare.

712
00:29:32,330 --> 00:29:33,600
Este vorba despre un minut.

713
00:29:33,600 --> 00:29:37,410
Și chiar dacă puteți vedea în continuare
modele întâmplă, de data aceasta puteți

714
00:29:37,410 --> 00:29:41,420
De asemenea, auzi cum aceste algoritmi sunt
efectuarea în mod diferit și cu

715
00:29:41,420 --> 00:29:43,950
oarecum diferite modele.

716
00:29:43,950 --> 00:29:45,830
>> Aceasta este un fel de inserare.

717
00:29:45,830 --> 00:29:50,400
>> [TONURI DE JOC]

718
00:29:50,400 --> 00:29:52,400
>> DAVID MALAN: Se încearcă din nou
pentru a insera fiecare element

719
00:29:52,400 --> 00:29:52,900
în cazul în care acesta face parte.

720
00:29:52,900 --> 00:29:54,628
Aceasta este un fel balon.

721
00:29:54,628 --> 00:30:10,097
>> [TONURI DE JOC]

722
00:30:10,097 --> 00:30:13,630
>> DAVID MALAN: Și tu poți un fel de simt
cât de relativ putina munca se face

723
00:30:13,630 --> 00:30:15,834
pe fiecare pas.

724
00:30:15,834 --> 00:30:20,470
Aceasta este ceea ce plictiseala suna.

725
00:30:20,470 --> 00:30:21,472
>> [TONURI DE JOC]

726
00:30:21,472 --> 00:30:25,222
>> DAVID MALAN: Aceasta este un fel de selecție,
în cazul în care vom selecta elementul ne-o dorim de

727
00:30:25,222 --> 00:30:28,845
trece prin din nou și din nou și din nou
și-l pune la început.

728
00:30:28,845 --> 00:30:37,674
>> [TONURI DE JOC]

729
00:30:37,674 --> 00:30:43,970
>> DAVID MALAN: Aceasta este îmbinarea fel, care
puteți începe cu adevărat să se simtă.

730
00:30:43,970 --> 00:30:51,810
>> [TONURI DE JOC]

731
00:30:51,810 --> 00:30:54,770
>> [Râsete]

732
00:30:54,770 --> 00:30:58,395
>> DAVID MALAN: Ceva numit gnome
fel, care nu ne-am uitat la.

733
00:30:58,395 --> 00:31:13,630
>> [TONURI DE JOC]

734
00:31:13,630 --> 00:31:17,910
>> DAVID MALAN: Deci, lasă-mă să văd, acum,
distras în timp ce sperăm sunt de

735
00:31:17,910 --> 00:31:21,110
muzica, dacă pot aluneca un pic
bit de matematica aici.

736
00:31:21,110 --> 00:31:24,850
Deci, există un al patrulea mod în care putem
cred despre ceea ce înseamnă acestea

737
00:31:24,850 --> 00:31:29,210
funcții să fie mai rapid decât cele
pe care le-am văzut înainte.

738
00:31:29,210 --> 00:31:32,470
Și dacă vii la cursul de
un fundal matematică, te

739
00:31:32,470 --> 00:31:36,030
de fapt, știți probabil deja că
poate palmă un termen pe aceasta tehnica -

740
00:31:36,030 --> 00:31:40,400
anume recursivitate, o funcție
care se numește cumva.

741
00:31:40,400 --> 00:31:44,780
>> Și din nou, reamintească faptul că un fel îmbinare
pseudocod a fost recursiv, în sensul

742
00:31:44,780 --> 00:31:48,460
că una dintre etapele de îmbinare sortare lui
a fost de a apela un fel -

743
00:31:48,460 --> 00:31:49,740
care este, ea însăși.

744
00:31:49,740 --> 00:31:52,480
Dar, din fericire, pentru că ne-am păstrat
de asteptare fel, sau fuziona fel,

745
00:31:52,480 --> 00:31:55,880
în mod specific, pe o mici și mai mici
și lista mai mici, cele din urmă am

746
00:31:55,880 --> 00:32:00,005
fund datorită ceea ce vom numi
un caz de bază, în cazul hard-coded care

747
00:32:00,005 --> 00:32:04,270
spus dacă lista este mic, mai puțin de 2
în acest caz, doar reveni imediat.

748
00:32:04,270 --> 00:32:07,550
Dacă nu am avea acest caz special,
Algoritmul nu ar fund afară,

749
00:32:07,550 --> 00:32:11,010
și v-ar lua într-adevăr într-o
buclă infinită cu adevărat pentru totdeauna.

750
00:32:11,010 --> 00:32:14,330
>> Dar să presupunem că am vrut să pun acum
unele numere pe aceasta, din nou, folosind n

751
00:32:14,330 --> 00:32:15,660
ca mărimea de intrare.

752
00:32:15,660 --> 00:32:18,680
Și am vrut să te întreb, ce-i
timpul total implicate în

753
00:32:18,680 --> 00:32:19,800
rulare fel merge?

754
00:32:19,800 --> 00:32:22,960
Sau, mai general, ceea ce este
Costul ei în timp?

755
00:32:22,960 --> 00:32:24,730
>> Ei bine, este destul de ușor să evalueze.

756
00:32:24,730 --> 00:32:29,010
Daca n este mai mic de 2, timpul implicat
în sortarea n elemente,

757
00:32:29,010 --> 00:32:30,480
în cazul în care n este 2, este 0.

758
00:32:30,480 --> 00:32:31,410
Pentru că ne-am întoarce.

759
00:32:31,410 --> 00:32:32,510
Nu e nici o lucrare de făcut.

760
00:32:32,510 --> 00:32:35,660
Acum, fără îndoială, poate e cu un pas sau doi
pași pentru a afla suma de

761
00:32:35,660 --> 00:32:38,420
de lucru, dar e destul de aproape de 0, care
Mă duc să spun nici o lucrare este

762
00:32:38,420 --> 00:32:40,940
necesar dacă lista este atât de mic
să fie neinteresante.

763
00:32:40,940 --> 00:32:42,580
>> Dar acest caz este interesant.

764
00:32:42,580 --> 00:32:47,320
Cazul recursiv a fost ramura de
pseudocod care a spus altceva, un fel

765
00:32:47,320 --> 00:32:52,000
jumătatea din stânga, sorta dreapta
jumătate, fuzionarea celor două jumătăți.

766
00:32:52,000 --> 00:32:55,530
Acum de ce face acest lucru expresie
reprezinta acea cheltuiala?

767
00:32:55,530 --> 00:32:58,690
Ei bine, T n înseamnă doar
timp pentru a sorta n elemente.

768
00:32:58,690 --> 00:33:03,070
Și apoi pe partea dreaptă a
semnul egalității acolo, T de n divizat

769
00:33:03,070 --> 00:33:06,600
de 2 se referă la costul de ce?

770
00:33:06,600 --> 00:33:07,570
Sortarea jumătatea stângă.

771
00:33:07,570 --> 00:33:10,990
Alte T de n împărțit la 2 este
probabil cu referire la costul

772
00:33:10,990 --> 00:33:12,390
sorta jumătatea din dreapta.

773
00:33:12,390 --> 00:33:14,590
>> Și apoi n plus?

774
00:33:14,590 --> 00:33:15,420
Este fuziunea.

775
00:33:15,420 --> 00:33:19,120
Pentru că dacă aveți două liste, una dintre
Dimensiunea n peste 2 și un alt de dimensiune n

776
00:33:19,120 --> 00:33:22,580
peste 2, trebuie să atingeți în esență,
fiecare dintre aceste elemente, la fel ca Rob

777
00:33:22,580 --> 00:33:24,990
a atins fiecare dintre cupe, și doar
așa cum am arătat la fiecare dintre

778
00:33:24,990 --> 00:33:26,310
voluntari pe scena.

779
00:33:26,310 --> 00:33:28,790
Deci, n este în detrimentul de a fuziona.

780
00:33:28,790 --> 00:33:31,780
>> Acum, din păcate, această formulă
Este, de asemenea, în sine recursiv.

781
00:33:31,780 --> 00:33:36,390
Deci, dacă a pus întrebarea, dacă n este, spune,
16, în cazul în care există 16 de oameni de pe scena

782
00:33:36,390 --> 00:33:40,670
sau 16 Cupe la film, câte totală
măsuri este nevoie pentru a le sorta

783
00:33:40,670 --> 00:33:41,550
cu îmbinare fel?

784
00:33:41,550 --> 00:33:45,790
Nu este de fapt un răspuns evident,
pentru că acum aveți pentru a sorta de

785
00:33:45,790 --> 00:33:48,500
răspunde recursiv această formulă.

786
00:33:48,500 --> 00:33:51,190
>> Dar asta e bine, pentru că lasă-mă să propună
ce facem următoarele.

787
00:33:51,190 --> 00:33:56,670
Timpul necesar pentru a sorta 16 de persoane sau
16 Cupe va fi reprezentat

788
00:33:56,670 --> 00:33:58,020
în general, ca T de 16.

789
00:33:58,020 --> 00:34:01,400
Dar care este egală, în conformitate cu nostru
formula precedentă, de 2 ori valoarea

790
00:34:01,400 --> 00:34:04,780
de timp este nevoie pentru a sorta
8 Cupe plus 16.

791
00:34:04,780 --> 00:34:08,590
Și din nou, plus 16 este timpul să fuzioneze,
și două ori T din 8 este

792
00:34:08,590 --> 00:34:10,790
timp pentru a sorta jumătatea stângă și jumătate dreapta.

793
00:34:10,790 --> 00:34:11,989
>> Dar, din nou, acest lucru nu este suficient.

794
00:34:11,989 --> 00:34:13,210
Trebuie să se scufunde mai adânc.

795
00:34:13,210 --> 00:34:16,409
Acest lucru înseamnă că trebuie să răspundă la
întrebarea, ce este T de 8?

796
00:34:16,409 --> 00:34:19,610
Ei bine, T de 8 este la doar 2
ori T de 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
Ei bine, ce-i T de 4?

798
00:34:20,520 --> 00:34:23,780
T 4 este de doar 2 ori T de 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
Ei bine, ce-i T de 2?

800
00:34:25,489 --> 00:34:29,030
T de 2 este de doar 2 ori T din 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> Și din nou, suntem un fel de a obține
blocat în acest ciclu.

802
00:34:31,940 --> 00:34:34,790
Dar este pe cale de a lovi că
așa-numitul caz de bază.

803
00:34:34,790 --> 00:34:37,310
Pentru că ce-i T de 1, am pretinde?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Așa că acum, în sfârșit, putem lucra invers.

806
00:34:39,730 --> 00:34:44,290
>> Dacă T din 1 este 0, eu pot merge acum înapoi o
alinia la acest tip de aici, și eu pot

807
00:34:44,290 --> 00:34:46,330
conectați la 0 pentru T de 1.

808
00:34:46,330 --> 00:34:51,770
Deci, ceea ce înseamnă că este egală cu de 2 ori la zero,
altfel cunoscut ca 0, plus 2.

809
00:34:51,770 --> 00:34:53,739
Și astfel încât expresia întreg este 2.

810
00:34:53,739 --> 00:34:58,740
>> Acum, dacă mă iau de T 2, al carei raspuns
este de 2, conectați-l în linia de mijloc, T

811
00:34:58,740 --> 00:35:02,740
de 4, care îmi dă de 2 ori
2 plus 4, deci 8.

812
00:35:02,740 --> 00:35:07,080
Dacă atunci am conectați la 8 la precedenta
linie, care îmi dă de 2 ori 8, 16.

813
00:35:07,080 --> 00:35:12,470
Și dacă vom continua apoi că, odată cu
24, adăugând în 16, vom obține în final o

814
00:35:12,470 --> 00:35:13,820
valoare de 64.

815
00:35:13,820 --> 00:35:18,480
>> Acum, că, în sine, un fel de vorbește
nimic la n notație,

816
00:35:18,480 --> 00:35:20,700
Big O, omega care le-am
vorbit despre.

817
00:35:20,700 --> 00:35:24,890
Dar se pare că 64 este într-adevăr
16, mărimea de intrare,

818
00:35:24,890 --> 00:35:27,110
jurnal de bază 2 din 16.

819
00:35:27,110 --> 00:35:30,200
Și dacă acest lucru este un pic nefamiliar, doar
cred că înapoi, și va veni înapoi

820
00:35:30,200 --> 00:35:30,700
pentru tine în cele din urmă.

821
00:35:30,700 --> 00:35:33,775
Dacă aceasta este baza log 2, e ca si cum 2
ridicat la ceea ce vă oferă 16?

822
00:35:33,775 --> 00:35:36,380
Oh, e 4, deci este de 16 ori 4.

823
00:35:36,380 --> 00:35:39,380
>> Și din nou, nu e mare lucru, dacă acest lucru
este un fel de amintire încețoșată acum.

824
00:35:39,380 --> 00:35:43,720
Dar pentru acum, să ia în credință
că 16 log 16 este de 64.

825
00:35:43,720 --> 00:35:46,590
Și astfel, într-adevăr, cu acest bun-simț simplu
verifica, am confirmat -

826
00:35:46,590 --> 00:35:48,250
dar nu s-au dovedit în mod formal -

827
00:35:48,250 --> 00:35:52,800
că timpul de funcționare a merge
fel este într-adevăr n log.

828
00:35:52,800 --> 00:35:53,790
>> Deci, nu rău.

829
00:35:53,790 --> 00:35:57,260
Este cu siguranta mai bine decat
algoritmi care le-am văzut până acum, și

830
00:35:57,260 --> 00:36:00,710
e pentru că am de indatorare, unul,
o tehnica numita recursivitate.

831
00:36:00,710 --> 00:36:03,880
Dar mai interesant decât atât, că
noțiunea de divizare și cucerirea.

832
00:36:03,880 --> 00:36:07,460
Din nou, cu adevărat saptamana 0 chestia asta
chiar acum este recurente într-o

833
00:36:07,460 --> 00:36:08,740
mod mult mai convingător.

834
00:36:08,740 --> 00:36:11,750
>> Acum, un exercițiu pic de distracție, dacă ați
nu făcut acest lucru - și, probabil,

835
00:36:11,750 --> 00:36:14,660
nu ar trebui, din cauza fel de normale
oamenii nu cred că pentru a face acest lucru.

836
00:36:14,660 --> 00:36:20,650
Dar, dacă mă duc la google.com și dacă
Vreau să învăț ceva despre

837
00:36:20,650 --> 00:36:22,356
recursivitate, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Râsete]

840
00:36:29,058 --> 00:36:32,030
[Mai multe râsete]

841
00:36:32,030 --> 00:36:33,385
DAVID MALAN: Bad glumă răspândirea încet.

842
00:36:33,385 --> 00:36:34,450
[Râsete]

843
00:36:34,450 --> 00:36:36,970
DAVID MALAN: Doar în cazul în care, e acolo.

844
00:36:36,970 --> 00:36:38,710
Nu am scrie greșit,
și nu e de glumă.

845
00:36:38,710 --> 00:36:40,810
Bine.

846
00:36:40,810 --> 00:36:42,950
Explicați-l la oamenii de lângă tine dacă
ea nu a destul de apasat încă.

847
00:36:42,950 --> 00:36:47,650
Dar recursivitate, în general, se referă
la procesul de o funcție asteptare

848
00:36:47,650 --> 00:36:51,430
în sine, sau, mai general, împărțind-o
Problema in ceva ce poate fi

849
00:36:51,430 --> 00:36:56,220
rezolvate treptat prin rezolvarea identice
probleme reprezentative.

850
00:36:56,220 --> 00:36:58,400
>> Ei bine, hai sa unelte schimbare
pentru doar o clipă.

851
00:36:58,400 --> 00:37:00,840
Ne place să se încheie la anumite clipe,
Să începem de a stabili

852
00:37:00,840 --> 00:37:05,870
etapă, timp de câteva minute,
pe o idee foarte simplă -

853
00:37:05,870 --> 00:37:07,620
că de pompare două elemente, nu?

854
00:37:07,620 --> 00:37:10,040
Toate aceste algoritmi am fost
vorbesc despre ultimii

855
00:37:10,040 --> 00:37:12,420
prelegeri implica unele
un fel de pompare.

856
00:37:12,420 --> 00:37:14,630
Astăzi a fost vizualizat de ei obtinerea
afară din scaunele lor și

857
00:37:14,630 --> 00:37:18,570
de mers pe jos în jurul, dar în cod, ne-ar
ia doar un element dintr-o matrice

858
00:37:18,570 --> 00:37:20,370
și plop-l într-un alt.

859
00:37:20,370 --> 00:37:21,880
>> Deci, cum putem merge despre a face acest lucru?

860
00:37:21,880 --> 00:37:24,850
Ei bine, lasă-mă să merg mai departe și scrie
un program de rapid aici.

861
00:37:24,850 --> 00:37:31,600
Am de gând să merg mai departe și de a face
aceasta ar fi următoarele.

862
00:37:31,600 --> 00:37:33,910
Să numim asta -

863
00:37:33,910 --> 00:37:38,070
ceea ce vrem să numim asta?

864
00:37:38,070 --> 00:37:38,650
>> De fapt, nu.

865
00:37:38,650 --> 00:37:39,420
Lasă-mă înapoi.

866
00:37:39,420 --> 00:37:41,220
Nu vreau să fac asta
Cliffhanger încă.

867
00:37:41,220 --> 00:37:42,270
Acesta va strica distractia.

868
00:37:42,270 --> 00:37:43,600
Să facem acest lucru în schimb.

869
00:37:43,600 --> 00:37:47,430
>> Să presupunem că vreau să scriu un pic
program și care îmbrățișează acum această

870
00:37:47,430 --> 00:37:48,700
Ideea de recursivitate.

871
00:37:48,700 --> 00:37:50,370
Am facut un fel de ajuns înainte de mine acolo.

872
00:37:50,370 --> 00:37:51,420
Am de gând să faceți următoarele.

873
00:37:51,420 --> 00:38:00,220
>> În primul rând, o scurtă includ standard io.h,
precum și o includ de cs50.h.

874
00:38:00,220 --> 00:38:03,200
Și apoi am de gând să merg mai departe
și declare nul int main

875
00:38:03,200 --> 00:38:04,360
în mod obișnuit.

876
00:38:04,360 --> 00:38:07,920
Am realizat că am greșit în botezarea dosar, astfel încât
permiteți-mi să adăugați o C extensie. aici atât de

877
00:38:07,920 --> 00:38:09,510
că putem compila în mod corespunzător.

878
00:38:09,510 --> 00:38:10,970
Începe această funcție.

879
00:38:10,970 --> 00:38:13,290
>> Și funcția vreau să scriu, destul de
pur și simplu, este una care cere

880
00:38:13,290 --> 00:38:16,210
utilizator pentru un număr și apoi se adaugă în sus
toate numerele dintre care

881
00:38:16,210 --> 00:38:19,920
numărul și, să zicem, 0.

882
00:38:19,920 --> 00:38:22,510
Deci, în primul rând am de gând să merg mai departe
și declare n int.

883
00:38:22,510 --> 00:38:24,760
Apoi am copia un cod care
am folosit pentru un timp.

884
00:38:24,760 --> 00:38:26,660
În timp ce ceva este adevărat.

885
00:38:26,660 --> 00:38:28,000
Voi reveni la faptul că într-o clipă.

886
00:38:28,000 --> 00:38:29,010
>> Ce vreau să fac?

887
00:38:29,010 --> 00:38:33,460
Vreau să spun printf pozitiv
întreg rog.

888
00:38:33,460 --> 00:38:36,130
Și apoi am de gând să
spune n se obține Int.

889
00:38:36,130 --> 00:38:38,800
Deci, din nou, un cod șabloane
pe care le-am folosit înainte.

890
00:38:38,800 --> 00:38:40,810
Și am de gând să facă acest lucru
în timp ce n este mai mic de 1.

891
00:38:40,810 --> 00:38:44,120
Deci, acest lucru va asigura că utilizatorul
dă-mi un număr întreg pozitiv.

892
00:38:44,120 --> 00:38:45,490
>> Și acum am de gând să faceți următoarele.

893
00:38:45,490 --> 00:38:51,020
Vreau să adune toate numerele
între 1 și n și, sau 0 și n,

894
00:38:51,020 --> 00:38:52,570
echivalent, pentru a obține suma totală.

895
00:38:52,570 --> 00:38:55,100
Deci, mare simbolul Sigma
pe care le-ar putea aminti.

896
00:38:55,100 --> 00:38:59,050
Așa că am de gând să fac acest lucru de prima convocare
o funcție numită sigma,

897
00:38:59,050 --> 00:39:06,030
trecând-o în n, iar apoi am de gând să
spune printf, raspunsul este chiar acolo.

898
00:39:06,030 --> 00:39:08,180
>> Deci, pe scurt, mă și
int de la utilizator.

899
00:39:08,180 --> 00:39:09,280
Eu asigura că este pozitiv.

900
00:39:09,280 --> 00:39:12,700
Declar o variabilă numită răspuns de
tip int și se păstrează într-o retur

901
00:39:12,700 --> 00:39:15,610
Valoarea Sigma, trece in n ca intrare.

902
00:39:15,610 --> 00:39:17,060
Și apoi am imprima acest răspuns.

903
00:39:17,060 --> 00:39:19,550
>> Din păcate, chiar dacă Sigma suna
ca ceva care ar putea fi în

904
00:39:19,550 --> 00:39:24,040
fișierul math.h, declarația sa,
de fapt nu este.

905
00:39:24,040 --> 00:39:24,690
Deci, asta e OK.

906
00:39:24,690 --> 00:39:26,170
Pot pune în aplicare această eu.

907
00:39:26,170 --> 00:39:29,160
Am de gând să pună în aplicare o funcție numită
Sigma, și se va lua o

908
00:39:29,160 --> 00:39:29,900
parametru -

909
00:39:29,900 --> 00:39:32,100
să-i zicem doar m, doar
așa că este diferit.

910
00:39:32,100 --> 00:39:35,910
Și apoi aici, am de gând să spun,
bine, dacă m este mai mică de 1 - aceasta este o

911
00:39:35,910 --> 00:39:38,180
program foarte neinteresant.

912
00:39:38,180 --> 00:39:41,700
Așa că am de gând să merg mai departe și
reveni imediat 0.

913
00:39:41,700 --> 00:39:45,920
Pur si simplu nu are sens pentru a aduna toate
numere intre 1 si m, dacă m

914
00:39:45,920 --> 00:39:48,470
este ea însăși 0 sau negativ.

915
00:39:48,470 --> 00:39:50,900
>> Și apoi am de gând să merg mai departe
și de a face acest lucru foarte iterativ.

916
00:39:50,900 --> 00:39:53,090
Am de gând să fac acest fel de old-school,
și am de gând să merg mai departe

917
00:39:53,090 --> 00:39:57,150
și să spun că am de gând să
declara o sumă să fie 0.

918
00:39:57,150 --> 00:39:59,630
Apoi, am de gând să aibă
o pentru buclă de Int -

919
00:39:59,630 --> 00:40:02,820
și lasă-mă să o fac pentru a se potrivi noastre
Codul de distribuție, astfel încât să aibă o copie

920
00:40:02,820 --> 00:40:07,500
la domiciliu. int i se 1 la până la
i este mai mică sau egală cu m.

921
00:40:07,500 --> 00:40:09,430
I, plus, plus.

922
00:40:09,430 --> 00:40:11,430
Și apoi în interiorul acestei pentru buclă -

923
00:40:11,430 --> 00:40:12,440
suntem aproape acolo -

924
00:40:12,440 --> 00:40:15,810
suma devine sumă, plus 1.

925
00:40:15,810 --> 00:40:17,670
Și apoi am de gând să returneze suma.

926
00:40:17,670 --> 00:40:19,420
>> Așa că am făcut acest lucru mai repede,
destul Desigur.

927
00:40:19,420 --> 00:40:22,775
Dar, din nou, funcția principală e destul de
simplu, bazat pe cod ne-am

928
00:40:22,775 --> 00:40:23,190
scris până acum.

929
00:40:23,190 --> 00:40:25,610
Utilizează dublu bucla pentru a obține un rezultat pozitiv
int de la utilizator.

930
00:40:25,610 --> 00:40:29,870
Apoi trec ca int pentru o nouă funcție
numita Sigma, numindu-l, din nou, n.

931
00:40:29,870 --> 00:40:33,100
Și am stoca valoarea returnata, răspunsul
de la cutia neagră în prezent

932
00:40:33,100 --> 00:40:35,460
cunoscut ca sigma, într-o variabilă
numit răspuns.

933
00:40:35,460 --> 00:40:36,580
Apoi am imprima.

934
00:40:36,580 --> 00:40:39,090
>> Dacă vom continua acum povestea,
modul în care este pusă în aplicare Sigma?

935
00:40:39,090 --> 00:40:40,840
Eu propun să pună în aplicare după cum urmează.

936
00:40:40,840 --> 00:40:43,560
În primul rând, un pic de eroare de verificare
pentru a vă asigura că utilizatorul nu este

937
00:40:43,560 --> 00:40:46,480
încurcați cu mine și trece în
o valoare negativă sau 0.

938
00:40:46,480 --> 00:40:49,710
Apoi am declara o variabilă numită
suma și setați-l la 0.

939
00:40:49,710 --> 00:40:55,910
>> Și acum încep să se miște de la I este egal
1 tot drumul până la și inclusiv m,

940
00:40:55,910 --> 00:41:00,130
pentru că vreau să includă toate
Numerele de la unu la m, inclusiv.

941
00:41:00,130 --> 00:41:04,350
Iar în interiorul acestei pentru buclă, eu doar fac
suma devine orice este acum, plus

942
00:41:04,350 --> 00:41:08,900
valoarea lui I.

943
00:41:08,900 --> 00:41:10,370
Plus valoarea de i.

944
00:41:10,370 --> 00:41:14,090
>> Ca o paranteza, dacă nu ați văzut acest lucru
înainte, există unele zahăr sintactic

945
00:41:14,090 --> 00:41:14,870
pentru această linie.

946
00:41:14,870 --> 00:41:21,120
Pot să rescrie acest lucru ca pe plus i egali,
doar pentru a mă salva câteva apăsări de taste

947
00:41:21,120 --> 00:41:22,570
și să se uite un pic mai rece.

948
00:41:22,570 --> 00:41:23,140
Dar asta e tot.

949
00:41:23,140 --> 00:41:24,660
Este funcțional acelasi lucru.

950
00:41:24,660 --> 00:41:26,710
>> Din păcate, acest cod de
nu va compila încă.

951
00:41:26,710 --> 00:41:31,600
Dacă I ​​a alerga fac Sigma 0, cum am
Am de gând să se țipe la?

952
00:41:31,600 --> 00:41:33,473
Ce va să nu vrea?

953
00:41:33,473 --> 00:41:35,740
>> Audiența: [inaudibil].

954
00:41:35,740 --> 00:41:37,800
>> DAVID MALAN: Da, nu am declarat
funcția de ridicare de sus, dreapta?

955
00:41:37,800 --> 00:41:40,590
C este un fel de prost, în sensul că numai
face ceea ce spune să facă, și tu

956
00:41:40,590 --> 00:41:41,880
trebuie să se facă în ordinea asta.

957
00:41:41,880 --> 00:41:45,910
Și așa, dacă am lovit Introduceți aici, am de gând să
primi un avertisment cu privire la Sigma implicită

958
00:41:45,910 --> 00:41:46,860
declarație.

959
00:41:46,860 --> 00:41:48,120
>> Oh, nu o problemă.

960
00:41:48,120 --> 00:41:50,370
Eu pot merge până la partea de sus, și pot
spun, bine, stai un minut.

961
00:41:50,370 --> 00:41:54,240
Sigma este o funcție care returnează
un întreg și se așteaptă o

962
00:41:54,240 --> 00:41:56,620
Int ca intrare, punct și virgulă.

963
00:41:56,620 --> 00:41:59,550
Sau am putea pune întreaga funcția
sus principală, dar, în general, aș

964
00:41:59,550 --> 00:42:02,260
recomanda împotriva că, deoarece este
frumos de a avea întotdeauna principal în partea de sus, astfel

965
00:42:02,260 --> 00:42:06,310
puteți arunca cu capul în dreapta și știu ce o
Programul face prin citirea principală întâi.

966
00:42:06,310 --> 00:42:07,930
>> Deci, acum, permiteți-mi clar pe ecran.

967
00:42:07,930 --> 00:42:09,330
Remake-ul Sigma 0.

968
00:42:09,330 --> 00:42:10,340
Totul pare pentru a verifica.

969
00:42:10,340 --> 00:42:11,970
Permiteți-mi să ruleze Sigma 0.

970
00:42:11,970 --> 00:42:12,770
Printre pozitiv.

971
00:42:12,770 --> 00:42:15,580
Voi da numărul
3 să-l păstrați simplu.

972
00:42:15,580 --> 00:42:18,710
Așa că ar trebui să-mi dea 3
plus 2 plus 1, deci 6.

973
00:42:18,710 --> 00:42:20,750
Introduceți, și într-adevăr am lua 6.

974
00:42:20,750 --> 00:42:21,820
>> Pot să fac ceva mai mare -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
La fel ca o tangentă, am de gând să fac
ceva ridicol ca un foarte mare

977
00:42:27,690 --> 00:42:30,375
număr, Oh, care de fapt a lucrat afară -

978
00:42:30,375 --> 00:42:31,600
eh, eu nu cred că e bine.

979
00:42:31,600 --> 00:42:32,810
Să vedem.

980
00:42:32,810 --> 00:42:34,060
Să adevăr te pui cu el.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Asta-i o problemă.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Ce se întâmplă?

985
00:42:44,970 --> 00:42:46,050
Codul nu e așa de rău.

986
00:42:46,050 --> 00:42:48,470
Este încă liniar.

987
00:42:48,470 --> 00:42:50,810
Fluierat este un efect bun, totuși.

988
00:42:50,810 --> 00:42:52,060
Ce se întâmplă?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Nu sunt sigur dacă am auzit-o.

991
00:42:55,620 --> 00:42:57,620
Deci, se dovedește - și
aceasta este ca o paranteză.

992
00:42:57,620 --> 00:42:59,400
Acest lucru nu este de bază pentru a
Ideea de recursivitate.

993
00:42:59,400 --> 00:43:02,480
Se pare, pentru că am încercat să
reprezintă un astfel de număr mare, mai

994
00:43:02,480 --> 00:43:06,980
probabil acesta fiind interpretat greșit
prin C sub forma unui număr pozitiv nu,

995
00:43:06,980 --> 00:43:09,980
dar număr negativ.

996
00:43:09,980 --> 00:43:12,690
>> Nu am vorbit despre acest lucru, dar
pare că există numere negative

997
00:43:12,690 --> 00:43:14,210
în lume, în plus
să numere pozitive.

998
00:43:14,210 --> 00:43:16,290
Și mijloacele prin care se poate
reprezintă un număr negativ

999
00:43:16,290 --> 00:43:19,530
în esență, este, folosiți un
bit special pentru a indica

1000
00:43:19,530 --> 00:43:20,400
pozitiv pe negativ.

1001
00:43:20,400 --> 00:43:22,950
Este un pic mai complex decât atât,
dar asta e ideea de bază.

1002
00:43:22,950 --> 00:43:26,740
>> Deci, din păcate, în cazul în care C este confuz unul
din aceste biți ca de fapt ceea ce înseamnă,

1003
00:43:26,740 --> 00:43:30,790
oh, acest lucru este un număr negativ, bucla mea
aici, de exemplu, este de fapt niciodată

1004
00:43:30,790 --> 00:43:31,740
va termina.

1005
00:43:31,740 --> 00:43:33,850
Deci, dacă am fost de fapt de imprimare ceva
din nou și din nou, ne-ar

1006
00:43:33,850 --> 00:43:34,650
vedea un întreg lot.

1007
00:43:34,650 --> 00:43:36,220
Dar, din nou, acest lucru este în afară de punctul.

1008
00:43:36,220 --> 00:43:38,590
Aceasta este de fapt doar un fel de
curiozitate intelectuală care vom veni

1009
00:43:38,590 --> 00:43:39,550
înapoi în cele din urmă.

1010
00:43:39,550 --> 00:43:43,400
Dar pentru acum, aceasta este o corectă
punerea în aplicare, dacă presupunem că

1011
00:43:43,400 --> 00:43:45,970
utilizatorul va furniza int
care se potrivesc în int.

1012
00:43:45,970 --> 00:43:49,370
>> Dar eu susțin că acest cod, sincer,
ar putea fi realizat atât de mult mai simplu.

1013
00:43:49,370 --> 00:43:54,060
În cazul în care obiectivul la îndemână este de a lua un număr
ca m și aduna toate

1014
00:43:54,060 --> 00:43:59,510
numere între ea și 1, sau invers
între 1 și-l, eu pretind

1015
00:43:59,510 --> 00:44:03,380
că pot împrumuta această idee că merge
sortare a avut, care a fost de a lua o problemă

1016
00:44:03,380 --> 00:44:05,660
de această dimensiune și împărțind-o
în ceva mai mic.

1017
00:44:05,660 --> 00:44:09,875
Poate că nu jumătate, dar mai mici, dar
reprezentativ la fel.

1018
00:44:09,875 --> 00:44:12,130
Aceeași idee, dar o problemă mai mică.

1019
00:44:12,130 --> 00:44:15,470
>> Deci, eu sunt de fapt - lasă-mă să salvați acest fișier
cu un număr de versiune diferit.

1020
00:44:15,470 --> 00:44:17,670
Vom numi această versiune
1 în loc de 0.

1021
00:44:17,670 --> 00:44:20,790
Și eu pretind că pot fapt
reimplementa acest lucru în acest fel de

1022
00:44:20,790 --> 00:44:22,160
minte-îndoire fel.

1023
00:44:22,160 --> 00:44:23,710
>> Am de gând să lase o parte din ea singur.

1024
00:44:23,710 --> 00:44:27,710
Am de gând să spun dacă m este mai puțin
mică sau chiar egală cu 0 -

1025
00:44:27,710 --> 00:44:29,280
Mă duc pentru a fi un pic
mai mult anal acest moment

1026
00:44:29,280 --> 00:44:30,520
cu verificarea mea eroare -

1027
00:44:30,520 --> 00:44:33,190
Am de gând să merg mai departe și să se întoarcă 0.

1028
00:44:33,190 --> 00:44:34,490
Aceasta este arbitrară.

1029
00:44:34,490 --> 00:44:37,500
Eu pur și simplu a decide dacă utilizatorul
dă-mi un număr negativ, eu sunt

1030
00:44:37,500 --> 00:44:41,490
întoarce 0, și ei ar fi trebuit să citească
documentația mai îndeaproape.

1031
00:44:41,490 --> 00:44:42,170
>> Altele -

1032
00:44:42,170 --> 00:44:44,070
observa ceea ce am de gând să fac.

1033
00:44:44,070 --> 00:44:49,260
Mai am de gând să se întoarcă m plus -

1034
00:44:49,260 --> 00:44:51,010
ceea ce este Sigma de m?

1035
00:44:51,010 --> 00:44:56,710
Ei bine, Sigma de m plus m minus 1,
plus minus 2 m, plus minus 3 m.

1036
00:44:56,710 --> 00:44:58,030
Nu vreau să scriu tot de asta.

1037
00:44:58,030 --> 00:44:59,120
De ce nu am punt?

1038
00:44:59,120 --> 00:45:05,080
Mă numesc recursiv cu un ușor
Problema mai mic, punct și virgulă,

1039
00:45:05,080 --> 00:45:06,840
și-l numesc o zi?

1040
00:45:06,840 --> 00:45:07,040
>> Dreapta?

1041
00:45:07,040 --> 00:45:10,980
Acum, aici, de asemenea, s-ar putea simți sau vă faceți griji
că aceasta este o buclă infinită care sunt

1042
00:45:10,980 --> 00:45:15,450
induce, prin care eu sunt de punere în aplicare
Sigma sunand la Sigma.

1043
00:45:15,450 --> 00:45:20,342
Dar asta e perfect în regulă, pentru că am
gândit înainte de a adăugat liniile care?

1044
00:45:20,342 --> 00:45:22,600
>> Audiența: [inaudibil].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID MALAN: 23 to 26, care
este meu dacă starea.

1046
00:45:25,430 --> 00:45:28,390
Pentru că ceea ce este frumos despre
scădere aici, pentru că am păstra

1047
00:45:28,390 --> 00:45:31,180
predarea probleme sigma mici, mici
probleme, mai mici - nu este

1048
00:45:31,180 --> 00:45:31,870
jumătate din dimensiunea.

1049
00:45:31,870 --> 00:45:34,380
Este doar un pas copil mic,
dar asta e OK.

1050
00:45:34,380 --> 00:45:38,050
Pentru că în cele din urmă, vom lucra
modul nostru de până la 1 sau 0.

1051
00:45:38,050 --> 00:45:41,630
Și odată ce ne-am lovit 0, sigma nu este
O să se mai numesc.

1052
00:45:41,630 --> 00:45:43,590
O să se întoarcă imediat 0.

1053
00:45:43,590 --> 00:45:47,960
>> Astfel încât efectul, dacă aveți un fel de vânt aceasta
in mintea ta, este de a adăuga m plus

1054
00:45:47,960 --> 00:45:52,740
m minus 1, plus minus 2 m, plus minus m
3, plus punct, punct, punct, m minus

1055
00:45:52,740 --> 00:45:57,820
m, în cele din urmă oferindu-vă 0, iar
Efectul este în cele din urmă să se adauge toate

1056
00:45:57,820 --> 00:45:59,070
aceste lucruri împreună.

1057
00:45:59,070 --> 00:46:02,380
Deci, nu avem, cu recursivitate,
rezolvat problema cu care ne

1058
00:46:02,380 --> 00:46:03,470
nu ar putea rezolva înainte.

1059
00:46:03,470 --> 00:46:06,840
Într-adevăr, versiunea 0 din prezenta, și fiecare
Problema la data, a fost rezolvabil

1060
00:46:06,840 --> 00:46:09,980
cu doar folosind-o pentru bucle sau în timp ce
bucle sau construcțiile similare.

1061
00:46:09,980 --> 00:46:13,150
>> Dar recursivitate, îndrăznesc să spun, ne dă
un mod diferit de gândire despre

1062
00:46:13,150 --> 00:46:17,010
probleme, prin care, dacă putem lua o
problema, împărțiți-l de la ceva

1063
00:46:17,010 --> 00:46:22,340
oarecum mare în ceva oarecum
mai mici, eu pretind că putem rezolva

1064
00:46:22,340 --> 00:46:26,040
poate un pic mai elegant din punct de vedere
de proiectare, cu mai puțin cod,

1065
00:46:26,040 --> 00:46:30,980
și poate chiar a rezolva problemele care ar
să fie mai greu, așa cum vom în cele din urmă

1066
00:46:30,980 --> 00:46:33,280
a se vedea, rezolvarea pur iterativ.

1067
00:46:33,280 --> 00:46:35,980
>> Dar Cliffhanger pe care am făcut-o
Vreau să ne lase în era aceasta.

1068
00:46:35,980 --> 00:46:40,720
Lasă-mă să merg mai departe și deschide
un fișier de la -

1069
00:46:40,720 --> 00:46:44,300
de fapt, lasă-mă să merg și
face acest lucru foarte repede.

1070
00:46:44,300 --> 00:46:46,875
Lasă-mă să merg mai departe și să propună
următor.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Printre codul de astăzi este acest fișier aici.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Acest unul aici, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Deci, acesta este un program de prost mic, care
Am bătut până ce pretenții să facă

1076
00:47:06,260 --> 00:47:06,940
următor.

1077
00:47:06,940 --> 00:47:10,140
În principal, se declară în primul rând o
Int numit x și atribuie

1078
00:47:10,140 --> 00:47:11,100
valoarea 1.

1079
00:47:11,100 --> 00:47:13,520
Apoi se declară un Y Int și
atribuie valoarea 2.

1080
00:47:13,520 --> 00:47:15,310
Apoi se imprimă ceea ce este x și y.

1081
00:47:15,310 --> 00:47:17,781
Apoi se spune, pompare, punct punct punct.

1082
00:47:17,781 --> 00:47:21,670
>> Apoi se pretinde a fi de asteptare o funcție
numit de swap, trece în x și

1083
00:47:21,670 --> 00:47:24,290
y, dintre care ideea este că sperăm
x și y vor veni înapoi

1084
00:47:24,290 --> 00:47:25,620
altfel, contrariul.

1085
00:47:25,620 --> 00:47:27,110
Apoi, ea pretinde schimbat!

1086
00:47:27,110 --> 00:47:28,420
cu un semn de exclamare.

1087
00:47:28,420 --> 00:47:30,190
Apoi se imprimă x și y.

1088
00:47:30,190 --> 00:47:33,480
>> Dar se pare că acest lucru foarte
demonstratie simpla jos

1089
00:47:33,480 --> 00:47:35,570
aici este, de fapt buggy.

1090
00:47:35,570 --> 00:47:38,870
Chiar dacă am declara o temporar
variabilă și punerea temporar o în

1091
00:47:38,870 --> 00:47:42,010
ea, apoi am realocarea
o valoare a lui b -

1092
00:47:42,010 --> 00:47:45,080
care se simte rezonabil, pentru că am
salvat o copie a unui in temp.

1093
00:47:45,080 --> 00:47:48,410
Apoi am actualiza b la egal
tot ce a fost în temp.

1094
00:47:48,410 --> 00:47:51,610
Acest tip de joc coajă de mișcare a
în b și b într-o prin folosirea acestui

1095
00:47:51,610 --> 00:47:54,360
-om de mijloc numit temp se simte
perfect rezonabil.

1096
00:47:54,360 --> 00:47:57,270
>> Dar eu susțin că atunci când am rula acest
cod, așa cum voi face acum -

1097
00:47:57,270 --> 00:47:59,490
lasă-mă să merg mai departe și lipiți-l aici.

1098
00:47:59,490 --> 00:48:01,995
Voi numi acest noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Și, după cum sugerează și numele, acest lucru nu este
Va fi un program corect.

1100
00:48:05,630 --> 00:48:09,460
Face noswap. / Nu de swap.

1101
00:48:09,460 --> 00:48:12,110
x este 1, y este 2, pompare, schimbat.

1102
00:48:12,110 --> 00:48:14,220
x este 1, y este 2.

1103
00:48:14,220 --> 00:48:16,920
Acest lucru este fundamental greșit, chiar
deși acest lucru pare perfect

1104
00:48:16,920 --> 00:48:17,730
rezonabil pentru mine.

1105
00:48:17,730 --> 00:48:21,330
Și există un motiv, dar nu suntem
de gând să dezvăluie motivul pentru care încă.

1106
00:48:21,330 --> 00:48:24,610
>> De acum doua Cliffhanger am vrut
să vă las cu este aceasta, o

1107
00:48:24,610 --> 00:48:27,120
Anunțul de felul pe coduri promoționale.

1108
00:48:27,120 --> 00:48:31,590
Inovația noastră cu întârziere de zile din acest an
a provocat un număr semnificativ

1109
00:48:31,590 --> 00:48:33,830
de întrebări, care a fost
Nu intenția noastră.

1110
00:48:33,830 --> 00:48:36,590
Intenția acestor coduri promoționale,
prin care, dacă faci parte din problemă

1111
00:48:36,590 --> 00:48:39,850
set devreme, obtinerea astfel o zi în plus,
a fost într-adevăr pentru a ajuta la voi ajuta

1112
00:48:39,850 --> 00:48:42,420
vă începe devreme, un fel
de către incentivizing tine.

1113
00:48:42,420 --> 00:48:44,880
Ne ajută să distribuie sarcina pe
orelor de lucru mai bine, astfel încât

1114
00:48:44,880 --> 00:48:45,740
Este un fel de win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Din păcate, cred că instrucțiunile mele
nu au fost, până în prezent, foarte clar, așa

1116
00:48:48,860 --> 00:48:52,230
M-am întors în acest weekend și actualizate
spec. în mare, obține un text la

1117
00:48:52,230 --> 00:48:53,600
explica gloanțe ca acestea.

1118
00:48:53,600 --> 00:48:56,900
Și doar să spun mai mult public, de
implicite, seturi de probleme sunt datorate joi

1119
00:48:56,900 --> 00:48:58,400
la prânz, pe programa.

1120
00:48:58,400 --> 00:49:02,030
Dacă începe devreme, finisare parte din
problema stabilit până miercuri la ora 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, partea care se referă la un cupon
cod, ideea este că puteți extinde

1122
00:49:05,170 --> 00:49:07,710
Termenul limită pentru
P set pana vineri.

1123
00:49:07,710 --> 00:49:10,890
Că este, cam de pe o mică parte din P
stabilit în raport cu ceea ce este de obicei

1124
00:49:10,890 --> 00:49:13,200
Problema mai mare, și de a cumpăra
vă o zi în plus.

1125
00:49:13,200 --> 00:49:15,190
Din nou, acesta devine tu gândești
Setul problema, să se

1126
00:49:15,190 --> 00:49:16,380
ore de birou mai devreme.

1127
00:49:16,380 --> 00:49:20,670
Dar problema cod promoțional este încă
necesar, chiar dacă nu-l prezinte.

1128
00:49:20,670 --> 00:49:23,340
>> Dar mai convingător este aceasta.

1129
00:49:23,340 --> 00:49:26,520
(WHISPER trepte) și acei oameni părăsesc
devreme vor regreta.

1130
00:49:26,520 --> 00:49:28,620
Ca sunt oameni pe balcon.

1131
00:49:28,620 --> 00:49:32,510
Îmi cer scuze în avans pentru cei de pe
balcon, pentru motive care vor fi

1132
00:49:32,510 --> 00:49:33,920
șterge într-o clipă.

1133
00:49:33,920 --> 00:49:37,050
>> Deci, suntem norocosi sa avem unul din
CS50 de semenii fostul predare cap la

1134
00:49:37,050 --> 00:49:39,302
o companie numita dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Ei au donat foarte generos o
cod cupon aici pentru atât de mult spațiu,

1136
00:49:45,500 --> 00:49:48,180
care este de până la
de obicei 2 gigabytes.

1137
00:49:48,180 --> 00:49:51,740
Deci, ceea ce am crezut că ne-ar face pe acest
Nota finală este sa faci un pic de un chilipir,

1138
00:49:51,740 --> 00:49:55,380
prin care într-o clipă, ne va dezvălui
câștigătorul și care are un cupon

1139
00:49:55,380 --> 00:49:57,980
cod pe care poti sa te duci apoi la lor
site-ul, introduceți-l în, și voila, pentru a primi o

1140
00:49:57,980 --> 00:50:01,370
mult mai mult spațiu Dropbox pentru dvs.
aparat și pentru fișierele personale.

1141
00:50:01,370 --> 00:50:05,690
>> Și în primul rând, care ar dori să participe
în acest desen?

1142
00:50:05,690 --> 00:50:09,630
OK, acum că o face chiar mai distractiv.

1143
00:50:09,630 --> 00:50:14,010
Persoana care primește acest 25-gigabyte
cod cupon - care este de departe

1144
00:50:14,010 --> 00:50:16,150
mai convingătoare decât la sfârșitul anilor
zile de acum, probabil -

1145
00:50:16,150 --> 00:50:20,620
este cel care este așezat pe partea de sus a unui
perna sub care nu există

1146
00:50:20,620 --> 00:50:21,620
că cod promoțional.

1147
00:50:21,620 --> 00:50:23,480
Puteti vedea acum sub
perna de siguranta.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [Redare video]

1150
00:50:29,680 --> 00:50:31,620
>> -Unu, doi, trei.

1151
00:50:31,620 --> 00:50:35,015
>> [URLET]

1152
00:50:35,015 --> 00:50:35,985
>> -Ai o masina!

1153
00:50:35,985 --> 00:50:36,670
Ai o mașină!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID MALAN: Vom vedea
vă miercuri.

1155
00:50:37,970 --> 00:50:38,904
>> -Ai o masina!

1156
00:50:38,904 --> 00:50:39,371
Ai o mașină!

1157
00:50:39,371 --> 00:50:40,305
Ai o mașină!

1158
00:50:40,305 --> 00:50:41,706
Ai o mașină!

1159
00:50:41,706 --> 00:50:43,107
Ai o mașină!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID MALAN: oameni buni balcon, vin
aici în față,

1161
00:50:45,530 --> 00:50:46,866
unde am extras.

1162
00:50:46,866 --> 00:50:50,282
>> -Toata lumea primeste o mașină!

1163
00:50:50,282 --> 00:50:52,234
Toată lumea devine o masina!

1164
00:50:52,234 --> 00:50:52,722
>> [END redare video]

1165
00:50:52,722 --> 00:50:54,590
>> NARATOR: La următoarea CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> DIFUZOR 5: Oh, Doamne Dumnezeule Doamne Dumnezeule
Doamne Doamne Doamne Doamne Doamne Dumnezeule -

1167
00:51:00,374 --> 00:51:02,106
>> [Ukelele joaca]