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

2
00:00:11,270 --> 00:00:14,910
>> Vorbitor: Bine, acest lucru este CS50.

3
00:00:14,910 --> 00:00:19,020
Acesta este sfârșitul de săptămână trei, iar în cazul în care
nu au profitat deja,

4
00:00:19,020 --> 00:00:21,790
știu că nu va fi masa de pranz
vineri, ca de obicei, în cazul în care

5
00:00:21,790 --> 00:00:25,430
vă puteți bucura de conversație bună
și alimente la Fire and Ice

6
00:00:25,430 --> 00:00:27,980
cu unele dintre lui CS50
personal și colegii de clasă.

7
00:00:27,980 --> 00:00:30,170
Mergeți la acest URL aici.

8
00:00:30,170 --> 00:00:33,420
>> Acum, vă amintiți, sau te
poate fi în curând familiarizat cu,

9
00:00:33,420 --> 00:00:35,970
aceste lucruri de aici, care
sunt date la sfârșitul

10
00:00:35,970 --> 00:00:37,850
semestrului pentru mai multe clase.

11
00:00:37,850 --> 00:00:40,870
Așa-numitele examen de cărți albastre, în care
scrii răspunsurile tale la examene.

12
00:00:40,870 --> 00:00:44,240
Acum am aici 26 astfel de
cărți albastre, pe fiecare dintre ele

13
00:00:44,240 --> 00:00:47,580
este scris un nume, de la A la Z. Și
într-adevăr, numele sunt atât de simple, A

14
00:00:47,580 --> 00:00:50,490
prin Z. Și unul din
obiectivele de la mână astăzi

15
00:00:50,490 --> 00:00:53,910
va fi de a continua ceea ce
am început luni, care nu este

16
00:00:53,910 --> 00:00:57,830
atât de mult se uită la cod, dar într-adevăr
uita la idei și de rezolvare a problemelor.

17
00:00:57,830 --> 00:01:00,170
Unul dintre obiectivele și
promisiuni de acest curs

18
00:01:00,170 --> 00:01:02,985
este să te învețe să gândească mai mult
cu atenție, mai metodic,

19
00:01:02,985 --> 00:01:05,400
și pentru a rezolva problemele mai eficient.

20
00:01:05,400 --> 00:01:09,526
Și într-adevăr, putem face asta într-adevăr
fără chiar a atinge o linie de cod.

21
00:01:09,526 --> 00:01:12,150
Deci, am o pereche de elefanți
aici astăzi, portocaliu și albastru,

22
00:01:12,150 --> 00:01:15,780
dacă am putea obține un voluntar,
Poate din spate mai departe decât de obicei.

23
00:01:15,780 --> 00:01:18,070
Ce zici de acolo, haide jos.

24
00:01:18,070 --> 00:01:24,180
Scopul care va fi de
ajuta plus administra acest examen aici.

25
00:01:24,180 --> 00:01:24,935
Care e numele tău?

26
00:01:24,935 --> 00:01:25,768
>> Audiența: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
Vorbitor: Mary Beth, haide sus.

28
00:01:27,560 --> 00:01:29,560
Lasă-mă să microfonul aici pentru tine.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Mă bucur să te cunosc.

31
00:01:32,880 --> 00:01:34,005
>> Audiența: Mă bucur să te cunosc.

32
00:01:34,005 --> 00:01:36,790
Vorbitor: Bine, așa că am
aici carti albastru de la A la Z,

33
00:01:36,790 --> 00:01:41,680
și am de gând să mă prefac că
Am unul dintre elevi,

34
00:01:41,680 --> 00:01:45,770
și vin în oarecum la întâmplare
la sfârșitul unui bloc de trei examene ore,

35
00:01:45,770 --> 00:01:49,400
astfel încât acestea sunt încheie până în unele
Pentru semi-aleatorie ca asta.

36
00:01:49,400 --> 00:01:54,510
Acum, de locuri de muncă într-o clipă se întâmplă
a fi-- aceasta este de fapt cum au ajuns

37
00:01:54,510 --> 00:01:56,820
transformat în la sfârșitul
clasa, cel mai probabil.

38
00:01:56,820 --> 00:02:01,120
Treaba ta acum va fi, destul de
pur și simplu, pentru a sorta aceste cărți albastre pentru noi

39
00:02:01,120 --> 00:02:05,220
de la A la Z.

40
00:02:05,220 --> 00:02:08,400
>> Audiența: Oh, acesta este
de gând să ia pentru totdeauna.

41
00:02:08,400 --> 00:02:13,747
>> SPEAKER: Și vom urmări
cum sa faci acest lucru, nici o presiune.

42
00:02:13,747 --> 00:02:15,330
Audiența: Nu, nici o presiune sau nimic.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> SPEAKER: Și pentru distracție,
hai sa pus un timer.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> Audiența: atât de distractiv, atât de distractiv.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> SPEAKER: Pot ține microfonul pentru tine.

49
00:02:38,574 --> 00:02:40,240
Bine, tocmai am dublat viteza noastră.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Deci, în același timp, lasă-mă să pun ce-i
va fi întrebarea de Mary Beth

52
00:02:49,060 --> 00:02:51,540
este ceea ce face ea, cum este
ea merge cu privire la rezolvarea acestei?

53
00:02:51,540 --> 00:02:54,040
Și, de fapt, nu s-ar putea avea
gândit vreodată despre ceva

54
00:02:54,040 --> 00:02:57,440
atât de simplu ca atunci când te iau
up 26 cărți de acest gen,

55
00:02:57,440 --> 00:02:59,350
care au un naturale
prin care se dispune pentru a le.

56
00:02:59,350 --> 00:03:01,335
Ce este procesul de
pe care le folosesc de fapt?

57
00:03:01,335 --> 00:03:03,770
Este destul de aleatoriu doar
alege primul cel pe care îl vedeți

58
00:03:03,770 --> 00:03:05,250
și punerea sa în locul ei?

59
00:03:05,250 --> 00:03:09,680
Nu vă deplasați mai întâi pe mâini în jurul
Cauti un apoi caută B?

60
00:03:09,680 --> 00:03:11,722
Ai arunca o privire la o
pereche de partea lor prin lateral

61
00:03:11,722 --> 00:03:14,680
și doar spun, așteptați un minut, acest
nu este corect, iar apoi schimba ordinea?

62
00:03:14,680 --> 00:03:16,960
Am văzut deja pe luni
că există o serie de moduri

63
00:03:16,960 --> 00:03:22,140
în care putem face acest lucru, și
într-adevăr, așa cum ne apropiem de sfârșit aici,

64
00:03:22,140 --> 00:03:26,360
Mi-ar lua notă, probabil,
de ce Mary Beth face.

65
00:03:26,360 --> 00:03:30,040
Avem câteva grămezi se pare, o
unul mai mare, de trei mai mici.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> Audiența: Eu le comanda
când am găsi două scrisori

68
00:03:36,415 --> 00:03:39,540
că știu că sunt împreună într-o secvență,
Le-am pus împreună, astfel încât să nu

69
00:03:39,540 --> 00:03:42,915
trebuie să vă faceți griji cu privire la menținerea
cale de un șir întreg de cărți.

70
00:03:42,915 --> 00:03:45,706
E doar, oh, A este primul,
Am o stivă de aici.

71
00:03:45,706 --> 00:03:47,580
Vorbitor: Deci, aproape ca
o piese de puzzle care

72
00:03:47,580 --> 00:03:49,860
au forma potrivită pentru a
se potrivesc unele cu altele.

73
00:03:49,860 --> 00:03:51,026
Audiența: Destul de mult, da.

74
00:03:51,026 --> 00:03:55,320
Vorbitor: Bine, excelent.

75
00:03:55,320 --> 00:03:59,850
Și acum fiecare dintre acestea
piloți sunt sortate probabil?

76
00:03:59,850 --> 00:04:00,990
>> Audiența: Da.

77
00:04:00,990 --> 00:04:09,900
>> Vorbitor: Bine, de la A la Z. Toate
drept, felicitări, ai făcut-o.

78
00:04:09,900 --> 00:04:11,461
Ai alegerea ta.

79
00:04:11,461 --> 00:04:11,960
Albastru?

80
00:04:11,960 --> 00:04:13,530
Bine, vă mulțumesc pentru asta.

81
00:04:13,530 --> 00:04:16,679
Deci, Mary Beth a propus
ce abordare ei a fost,

82
00:04:16,679 --> 00:04:19,720
dar ceea ce este o altă abordare modul în care
s-ar putea merge cu privire la sortarea aceste lucruri?

83
00:04:19,720 --> 00:04:21,130
Ce-ai fi făcut?

84
00:04:21,130 --> 00:04:24,060
Recordul de a bate ar fi fost
un minut și 50 de secunde sau cam asa ceva,

85
00:04:24,060 --> 00:04:26,039
plus cei care am uitat să numere.

86
00:04:26,039 --> 00:04:27,080
Ce-ai fi făcut?

87
00:04:27,080 --> 00:04:27,579
Da?

88
00:04:27,579 --> 00:04:28,735
Audiența: Ia stiva.

89
00:04:28,735 --> 00:04:29,776
Începe de la început.

90
00:04:29,776 --> 00:04:32,284
Verifică actele.

91
00:04:32,284 --> 00:04:36,586
Și dacă cel de sus este mai mare
decât, poate, ele sunt,

92
00:04:36,586 --> 00:04:38,980
cel de jos este
mai mare, apoi trece-le.

93
00:04:38,980 --> 00:04:41,300
>> Vorbitor: OK, deci începând cu
în partea de sus și de jos,

94
00:04:41,300 --> 00:04:43,716
și apoi de lucru-ți de drum
interior de genul asta, schimbarea ei?

95
00:04:43,716 --> 00:04:46,580
OK, deci un pic asemănător
în spirit de bule de sortare,

96
00:04:46,580 --> 00:04:49,160
dar alegerea extreme
Nu perechile adiacente.

97
00:04:49,160 --> 00:04:52,080
Dar pe termen scurt de ea este că nu există
cu siguranță o grămadă de moduri diferite

98
00:04:52,080 --> 00:04:54,210
am putea face acest lucru, și
sincer, eu te cred un fel de

99
00:04:54,210 --> 00:04:55,700
a adoptat câteva abordări, corect?

100
00:04:55,700 --> 00:05:00,567
Ai făcut un fel de patru piloți sortate, și
apoi le-au fuzionat în mod eficient împreună.

101
00:05:00,567 --> 00:05:02,650
Și asta e, îndrăznesc să spun, un alt
tehnica cu totul.

102
00:05:02,650 --> 00:05:06,950
Nu l-ai trata ca pe o mare grămadă,
tu divizat problema în patru quad-uri,

103
00:05:06,950 --> 00:05:09,820
dacă vreți, și apoi într-un fel
le fuzionat în cele din urmă.

104
00:05:09,820 --> 00:05:13,410
>> Deci, haideți să considerăm, în cele din urmă,
cum altfel am putea face acest lucru.

105
00:05:13,410 --> 00:05:15,860
Am formalizat notiunea
de bule fel ultimul timp,

106
00:05:15,860 --> 00:05:18,780
și bule fel de rechemare a fost un
algoritm care ne-am vizualizat

107
00:05:18,780 --> 00:05:22,640
cu opt dintre colegii dvs. aici,
aparent sortate aleatoriu la început.

108
00:05:22,640 --> 00:05:26,110
Și ne-am hotărât apoi pe perechi, dacă
două elemente sunt în ordine,

109
00:05:26,110 --> 00:05:26,950
pur și simplu a le schimba.

110
00:05:26,950 --> 00:05:28,930
Deci, patru și două sunt
în mod evident, în ordine,

111
00:05:28,930 --> 00:05:31,080
astfel încât cele două colegii de clasă
a schimbat locul.

112
00:05:31,080 --> 00:05:35,390
Și apoi am repetat cu patru și șase,
apoi șase și opt, pe fiecare iterație,

113
00:05:35,390 --> 00:05:36,980
se deplasează spre dreapta.

114
00:05:36,980 --> 00:05:42,590
>> Deci, având opt oameni, pe perechi câte
comparații am făcut în timp ce mersul pe jos de la

115
00:05:42,590 --> 00:05:45,220
stânga la dreapta într-o astfel de iterație?

116
00:05:45,220 --> 00:05:48,410
Câte comparații?

117
00:05:48,410 --> 00:05:49,197
Seven, nu?

118
00:05:49,197 --> 00:05:51,405
Pentru că dacă există opt
oameni, dar aveți o pereche

119
00:05:51,405 --> 00:05:53,880
le și păstrați-vă în mișcare
un hop la dreapta,

120
00:05:53,880 --> 00:05:56,060
tu nu vei avea opt
comparații pentru că nu se poate compara

121
00:05:56,060 --> 00:05:59,226
un element împotriva ei însăși, sau că ar fi
doar să fie lipsită de sens, astfel încât să aveți șapte.

122
00:05:59,226 --> 00:06:01,290
Sau, mai general, în cazul în
avem n oameni, ne-am

123
00:06:01,290 --> 00:06:04,300
face n minus 1 comparații
cu bule de sortare.

124
00:06:04,300 --> 00:06:08,150
>> Deci, haideți să considerăm acum cât de bun sau
bubble rău fel de fapt a fost, și încercați

125
00:06:08,150 --> 00:06:13,570
pentru a ne da vocabular cu
care a algoritmi critici, cum ar fi acest lucru,

126
00:06:13,570 --> 00:06:14,430
și, în curând propriul nostru.

127
00:06:14,430 --> 00:06:16,970
Deci, prima trecere prin
bubble sort, pentru prima dată

128
00:06:16,970 --> 00:06:20,909
M-am dus de la stânga la dreapta peste
etapă, mi-a luat n minus 1 comparații.

129
00:06:20,909 --> 00:06:22,950
Și care va fi mea
unitate de măsură, nu?

130
00:06:22,950 --> 00:06:26,170
Am fost un fel de a vorbi și vă plimbați,
oarecum rapid, oarecum lent,

131
00:06:26,170 --> 00:06:29,300
astfel de numărare numărul meu de secunde
nu este deosebit de spus,

132
00:06:29,300 --> 00:06:32,260
dar numărarea
operații care le-am făcut, luni,

133
00:06:32,260 --> 00:06:35,900
compararea a două persoane, care se simte
ca o unitate de frumos de măsură.

134
00:06:35,900 --> 00:06:40,980
>> Deci, n minus 1 pașii pentru prima dată,
dar apoi ce sa întâmplat după aceea?

135
00:06:40,980 --> 00:06:46,610
Care este unul din susul o singură trecere
printr-o listă de altfel nesortate?

136
00:06:46,610 --> 00:06:49,840
Ce-mi poți spune despre elementul
care a fost tot drumul de acolo?

137
00:06:49,840 --> 00:06:51,300
Da?

138
00:06:51,300 --> 00:06:52,870
Asta a fost cel mai mare element, nu?

139
00:06:52,870 --> 00:06:55,710
Numărul opt, chiar dacă ea
a început aici, de fiecare dată când

140
00:06:55,710 --> 00:06:57,860
în comparație ei împotriva
un vecin, ea a păstrat

141
00:06:57,860 --> 00:07:00,480
barbotare spre dreapta
în partea stângă a listei.

142
00:07:00,480 --> 00:07:02,710
Și într-adevăr, acolo
algoritmul devine numele său.

143
00:07:02,710 --> 00:07:07,630
>> Acum, prin care logica, cât de multe comparații
Trebuie sa fac pe a doua oară

144
00:07:07,630 --> 00:07:09,800
Eu fac că trece de la stânga la dreapta?

145
00:07:09,800 --> 00:07:10,730
n minus 2, corect?

146
00:07:10,730 --> 00:07:14,297
Ar fi doar pierd timpul dacă am
păstra compararea opt împotriva cuiva

147
00:07:14,297 --> 00:07:16,630
altfel pentru ca stim deja
ea a fost la locul potrivit.

148
00:07:16,630 --> 00:07:19,760
Deci, asta e un pic de o
optimizare, astfel încât următoarea trecere

149
00:07:19,760 --> 00:07:23,899
va fi plus n minus două etape,
unde n este numărul de persoane.

150
00:07:23,899 --> 00:07:26,940
Acum puteți fel de extrapola, chiar
dacă nu ești un om de știință de calculator,

151
00:07:26,940 --> 00:07:27,680
cum se termină.

152
00:07:27,680 --> 00:07:31,259
La finalul acestui algoritm, probabil
ai doar o comparație a plecat.

153
00:07:31,259 --> 00:07:33,800
Trebuie să fixați un fel de
începând din lista de la caz două

154
00:07:33,800 --> 00:07:36,540
și unul este în ordine
și ar trebui să fie una și două,

155
00:07:36,540 --> 00:07:40,330
astfel încât aceasta la fund afară la
plus 1 comparație finală.

156
00:07:40,330 --> 00:07:44,500
>> Acum, punct, punct, punct fel de valuri este
mâinile la unele dintre cele mai juicier detalii,

157
00:07:44,500 --> 00:07:46,452
dar hai să mergem mai departe și de a simplifica.

158
00:07:46,452 --> 00:07:48,660
Dacă vă amintiți de la mare
școală, sincer, o mulțime de tine

159
00:07:48,660 --> 00:07:50,340
au avut carti de matematica care au avut
o foaie de ieftin mic

160
00:07:50,340 --> 00:07:52,550
pe capacul frontal sau
capacul din spate care ți-a arătat

161
00:07:52,550 --> 00:07:56,400
somații ce serie, cum ar fi
aceasta în cele din urmă a adăugat până la.

162
00:07:56,400 --> 00:07:59,600
În cazul general, dacă aveți o
variabilă ca n, și într-adevăr aceasta,

163
00:07:59,600 --> 00:08:01,634
dacă te-ai uitat la dumneavoastră
carte de matematica școală veche,

164
00:08:01,634 --> 00:08:04,050
ați vedea că acest fapt
adaugă până la această sumă aici,

165
00:08:04,050 --> 00:08:07,970
n ori n minus 1 tot împărțit la 2.

166
00:08:07,970 --> 00:08:11,172
Deci, de acum lasă-mă să prevadă
acest lucru este adevărat, așa pe un salt de credință,

167
00:08:11,172 --> 00:08:12,880
asta e ceea ce rezumă acest
până la, și ne-am putea

168
00:08:12,880 --> 00:08:14,341
dovedi că într-un caz mai general.

169
00:08:14,341 --> 00:08:15,590
Dar acum să se extindă acest lucru.

170
00:08:15,590 --> 00:08:19,920
Așa că haideți să multiplica acest lucru, astfel încât este
n patrat, n minus, toate împărțit la 2.

171
00:08:19,920 --> 00:08:23,200
Asta este într-adevăr n pătrat,
împărțit la 2, minus n peste 2,

172
00:08:23,200 --> 00:08:25,010
asa ca asta e tot frumos și interesant.

173
00:08:25,010 --> 00:08:27,060
Dar ce se întâmplă dacă
acum plug-in-o valoare?

174
00:08:27,060 --> 00:08:29,724
Să presupunem că eu nu am avut opt
oameni, dar spun un milion.

175
00:08:29,724 --> 00:08:31,890
Și un milion doar pentru că
este un număr destul de mare,

176
00:08:31,890 --> 00:08:34,039
să conectați că în și vedem ce se întâmplă.

177
00:08:34,039 --> 00:08:39,039
Deci, dacă am conectați un milion în care formula
Am de gând pentru a obține un milion de pătrat,

178
00:08:39,039 --> 00:08:42,868
împărțit la 2, minus o
milioane, împărțit la 2.

179
00:08:42,868 --> 00:08:44,159
Acum, ce care merge la egal?

180
00:08:44,159 --> 00:08:47,354
Deci 500 de miliarde, minus 500.000.

181
00:08:47,354 --> 00:08:49,270
Și dacă de fapt, nu
că matematica afară, că mijloacele

182
00:08:49,270 --> 00:08:53,920
că sortarea un milion
oameni cu genul bubble

183
00:08:53,920 --> 00:09:01,800
mi-ar putea lua 499999500000
trepte sau comparații în cele din urmă,

184
00:09:01,800 --> 00:09:02,900
suntem doar extrapolarea.

185
00:09:02,900 --> 00:09:06,860
>> Că se simte destul de lent, dar sincer
măsurarea unul special de intrare

186
00:09:06,860 --> 00:09:09,160
in acest fel, nu este tot ceea ce spun.

187
00:09:09,160 --> 00:09:14,050
Dar, într-adevăr aceasta nu sugereaza ca n
devine mai mare și mai mare, acest algoritm

188
00:09:14,050 --> 00:09:16,280
un fel de se simte mai rău și
mai rău, sau chiar

189
00:09:16,280 --> 00:09:20,450
începe să se simtă durerea pe care
exponentiala, că n pătrat,

190
00:09:20,450 --> 00:09:21,770
care se adaugă destul de repede.

191
00:09:21,770 --> 00:09:25,340
Si acest detaliu nu este
pierdut pe oameni, de fapt

192
00:09:25,340 --> 00:09:29,640
în urmă cu câțiva ani un anumit senator care a fost
campanie, se așeză pentru un interviu

193
00:09:29,640 --> 00:09:32,180
cu Eric Google
Schmidt, CEO la momentul respectiv,

194
00:09:32,180 --> 00:09:36,380
și a fost provocat de o întrebare
la fel ca explorăm astăzi.

195
00:09:36,380 --> 00:09:38,468
Să aruncăm o privire.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEO PLAYBACK]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, Tu ești aici
la Google, și-mi place

198
00:09:48,560 --> 00:09:53,382
să se gândească la președinția
ca un interviu de angajare.

199
00:09:53,382 --> 00:09:56,434
Acum, este greu pentru a obține
un loc de muncă în calitate de președinte,

200
00:09:56,434 --> 00:09:58,100
și te duci prin rigorile acum.

201
00:09:58,100 --> 00:10:01,860
Este, de asemenea, greu pentru a obține un loc de muncă la Google.

202
00:10:01,860 --> 00:10:05,490
Avem întrebări, și noi
cere candidaților întrebările noastre,

203
00:10:05,490 --> 00:10:09,770
iar aceasta este de la Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
Ce-- voi că eu sunt
glumesc, e chiar aici.

205
00:10:14,760 --> 00:10:17,930
Care este cel mai eficient mod de a
a sorta un milion de numere întregi pe 32 de biți?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> Îmi pare rău, Poate--

209
00:10:25,200 --> 00:10:27,400
>> Nu, nu, nu.

210
00:10:27,400 --> 00:10:30,700
Cred că genul bubble
ar fi în mod greșit de a merge.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> Haide, care l-a spus asta?

213
00:10:38,180 --> 00:10:40,590
N-am văzut calculator
știința în fundal.

214
00:10:40,590 --> 00:10:42,130
>> -Avem Spionii noștri acolo.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -Bine, Să ceară un alt
întrebare interviu.

217
00:10:48,444 --> 00:10:49,300
>> [END VIDEO PLAYBACK]

218
00:10:49,300 --> 00:10:52,290
>> SPEAKER: Deci, vorbim despre
anumite numere, deși,

219
00:10:52,290 --> 00:10:53,890
nu va fi tot ceea ce util.

220
00:10:53,890 --> 00:10:56,810
Nu este o lectie de viata care cu bule
fel, având în vedere un milion de intrări,

221
00:10:56,810 --> 00:10:58,590
s-ar putea să ia cât mai multe 500 de miliarde de pași.

222
00:10:58,590 --> 00:11:01,120
Nu poti generaliza într-adevăr
prea eficient din care

223
00:11:01,120 --> 00:11:03,560
și să ia decizii de proiectare bune
atunci când scrieți programe.

224
00:11:03,560 --> 00:11:07,070
Așa că haideți să ne concentrăm totuși asupra modului
am putea simplifica acest rezultat.

225
00:11:07,070 --> 00:11:11,780
>> Așa că m-am evidențiat în galben aici
rezultatul n pătrat împărțit la 2,

226
00:11:11,780 --> 00:11:14,330
astfel încât un milion la pătrat
împărțit la 2, și apoi

227
00:11:14,330 --> 00:11:16,710
Am subliniat ce
răspunsul final a fost

228
00:11:16,710 --> 00:11:20,180
odată ce scade off n împărțit la 2.

229
00:11:20,180 --> 00:11:24,850
Și afirmația am de gând să fac acum este,
Cui îi pasă naiba dacă scădem off

230
00:11:24,850 --> 00:11:30,060
un pic de n vechi de peste 2, atunci când primul
o parte din această formulă este mult mai mare?

231
00:11:30,060 --> 00:11:33,910
Acesta domina pe celalalt
termen, n la patrat impartit la 2

232
00:11:33,910 --> 00:11:37,510
este mult mai mare, în mod clar, ca
n devine mare ca un milion,

233
00:11:37,510 --> 00:11:41,450
că există într-adevăr o mare diferență la
sfârșitul zilei între 500 de miliarde

234
00:11:41,450 --> 00:11:45,730
și 499999500000?

235
00:11:45,730 --> 00:11:46,349
Nu chiar.

236
00:11:46,349 --> 00:11:48,640
Și așa cum vom
face ca oamenii de stiinta de calculator este

237
00:11:48,640 --> 00:11:53,270
ignora aceste condiții de ordin inferior și
ia ceva de genul asta și într-adevăr

238
00:11:53,270 --> 00:11:56,050
doar se simplifica la
termen care va conta.

239
00:11:56,050 --> 00:12:00,315
Cele mai mari Seturile noastre de date a obține, cu atât mai mare
bazele noastre de date ajunge, mai multe pagini web

240
00:12:00,315 --> 00:12:02,690
avem de a căuta, cu atât mai mult
prietenii aveti pe Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Ca n devine mai mare, suntem într-adevăr
O să aibă grijă de cel mai mare

242
00:12:07,340 --> 00:12:11,560
Termenul în orice astfel de analiză a
performanța noastră algoritmi.

243
00:12:11,560 --> 00:12:16,230
Și am de gând să spun, știi ce,
bubble sort este pe ordinea de mare O,

244
00:12:16,230 --> 00:12:18,060
de ordinul a n pătrat.

245
00:12:18,060 --> 00:12:20,090
Nu e chiar n
pătrat cum am văzut,

246
00:12:20,090 --> 00:12:22,060
dar cui îi pasă cu adevărat
despre acei termeni mai mici,

247
00:12:22,060 --> 00:12:24,390
și sincer, care într-adevăr
îi pasă dacă vom împărți cu 2?

248
00:12:24,390 --> 00:12:25,870
Asta e doar un factor constant.

249
00:12:25,870 --> 00:12:29,480
Și este 500 de miliarde, comparativ cu 250
miliarde de adevărat că mare lucru?

250
00:12:29,480 --> 00:12:32,190
Aș putea aștepta doar un an,
lasa laptop-ul meu propriu

251
00:12:32,190 --> 00:12:34,810
obține de două ori mai repede în hardware,
și că un fel de diferență

252
00:12:34,810 --> 00:12:36,650
doar dispare în mod natural în timp.

253
00:12:36,650 --> 00:12:39,300
>> Ce ne pasă este
expresia, partea

254
00:12:39,300 --> 00:12:42,489
expresiei care va varia
ca intrare noastră devine mai mare și mai mare.

255
00:12:42,489 --> 00:12:45,280
Și, într-adevăr, în lumea reală,
asta e ceea ce se întâmplă din ce în ce

256
00:12:45,280 --> 00:12:48,330
Este intrările la problemele noastre și
algoritmi sunt ce mai mare.

257
00:12:48,330 --> 00:12:53,470
Atat de mare O va fi notația,
notația asimptotică, că ne-am

258
00:12:53,470 --> 00:12:57,160
utilizați ca oamenii de stiinta de calculator pentru a descrie
de performanță, sau timpul de execuție,

259
00:12:57,160 --> 00:12:58,130
unui algoritm.

260
00:12:58,130 --> 00:13:00,800
Astfel încât să putem compara algoritmi
pe computere diferite scrise

261
00:13:00,800 --> 00:13:04,170
de diferite persoane, prin utilizarea
unele metric fundamental similară

262
00:13:04,170 --> 00:13:07,557
cum ar fi numărul de comparații esti
a face, sau poate că numărul de swap-uri

263
00:13:07,557 --> 00:13:08,140
faci.

264
00:13:08,140 --> 00:13:11,910
>> Ceea ce nu vom
număr este cantitatea de timp

265
00:13:11,910 --> 00:13:13,981
care trece pe ceas
pe peretele de obicei.

266
00:13:13,981 --> 00:13:16,230
Ceea ce nu vom să vă faceți griji
despre este cât de mult de memorie

267
00:13:16,230 --> 00:13:17,820
pe care îl utilizați în prezent la
în ultimul rând, deși asta e

268
00:13:17,820 --> 00:13:19,370
o altă resursă am putea măsura.

269
00:13:19,370 --> 00:13:23,610
Vom încerca să-și bazeze analizele noastre
doar pe operațiunile de bază, cele,

270
00:13:23,610 --> 00:13:25,930
sincer, pe care le puteți vedea mai vizual.

271
00:13:25,930 --> 00:13:30,700
Deci, cu ceva de genul O mare de n
pătrat, eu susțin că O de n la patrat

272
00:13:30,700 --> 00:13:35,820
este o limită superioară pe așa-numitele
timp de bule tip de funcționare.

273
00:13:35,820 --> 00:13:38,820
Cu alte cuvinte, dacă
a vrut să pretindă că nu există

274
00:13:38,820 --> 00:13:41,370
această limită superioară de cât de multe
pașii unui algoritm s-ar putea lua,

275
00:13:41,370 --> 00:13:46,240
ea va fi în O mare de n
pătrat în acest caz, o limită superioară.

276
00:13:46,240 --> 00:13:49,710
>> Ce dacă în loc să schimb
Povestea a fi nu despre bubble sort,

277
00:13:49,710 --> 00:13:50,910
dar despre acest limită superioară.

278
00:13:50,910 --> 00:13:54,030
Vă puteți gândi la un algoritm
că ne-am uitat la deja

279
00:13:54,030 --> 00:13:59,530
a cărui limită superioară, maxim
măsura de timp sau operațiuni,

280
00:13:59,530 --> 00:14:04,300
ar fi spus să fie delimitate
de n, o funcție liniară,

281
00:14:04,300 --> 00:14:07,260
nu una de gradul doi care este curbat?

282
00:14:07,260 --> 00:14:10,780
Ce este un algoritm care
Intotdeauna este nevoie de nu mai mult

283
00:14:10,780 --> 00:14:12,860
decât ca n trepte, sau
Pași 2n, sau etape 3n?

284
00:14:12,860 --> 00:14:13,360
Da?

285
00:14:13,360 --> 00:14:15,030
>> Audiența: Găsirea
cel mai mare număr într-o listă?

286
00:14:15,030 --> 00:14:16,930
>> Vorbitor: Perfect, găsirea
cel mai mare număr într-o listă.

287
00:14:16,930 --> 00:14:18,940
Dacă am dat o listă de
oameni, de exemplu,

288
00:14:18,940 --> 00:14:21,440
fiecare dintre care deține un număr,
ceea ce este numărul maxim

289
00:14:21,440 --> 00:14:23,770
de măsuri ar trebui să mă ia,
o persoană rezonabil inteligent,

290
00:14:23,770 --> 00:14:27,530
pentru a găsi cea mai mare persoană în această listă?

291
00:14:27,530 --> 00:14:28,100
n, corect?

292
00:14:28,100 --> 00:14:31,320
Pentru că, în cel mai rău caz, în cazul în care
ar putea fi cea mai mare valoare?

293
00:14:31,320 --> 00:14:32,700
Corect, tot drumul de la sfârșitul.

294
00:14:32,700 --> 00:14:34,575
Deci, în cel mai rău caz
limita superioară, s-ar putea

295
00:14:34,575 --> 00:14:36,450
trebuie să meargă până la capăt
aici și să fie ca,

296
00:14:36,450 --> 00:14:39,170
oh, aici e numărul opt,
sau orice care valoare este.

297
00:14:39,170 --> 00:14:41,330
Acum, ar fi o prostie
dacă am continuat drumul, nu?

298
00:14:41,330 --> 00:14:43,840
Privind pentru mai multe și mai multe elemente
în cazul în care ultimul dintre ei este acolo?

299
00:14:43,840 --> 00:14:45,340
Deci cu siguranță, n este o limită superioară.

300
00:14:45,340 --> 00:14:47,420
Nu am nevoie să ia
mai multe etape decât atât.

301
00:14:47,420 --> 00:14:51,580
>> Deci, ceea ce, dacă în schimb am propus ca
există algoritmi în această lume care

302
00:14:51,580 --> 00:14:57,750
au un timp de funcționare care este
delimitată de O mare de log n, log n?

303
00:14:57,750 --> 00:15:00,390
În cazul în care am văzut acest lucru înainte?

304
00:15:00,390 --> 00:15:00,890
Da?

305
00:15:00,890 --> 00:15:03,309
>> Audiența: În problema cartea de telefon?

306
00:15:03,309 --> 00:15:04,850
SPEAKER: Ca problema cartea de telefon.

307
00:15:04,850 --> 00:15:07,754
Care a fost măsura de modul în care
mult timp sau cât de multe lacrimi IT

308
00:15:07,754 --> 00:15:10,170
Mi-a luat pentru a găsi pe cineva ca
Mike Smith în cartea de telefon?

309
00:15:10,170 --> 00:15:13,212
Am pretins că a fost log n, și
chiar dacă necunoscut sau este

310
00:15:13,212 --> 00:15:15,170
un pic neclar ce o
logaritm sau exponent a fost,

311
00:15:15,170 --> 00:15:17,650
amintesc doar că log n
în general, se referă la procesul,

312
00:15:17,650 --> 00:15:20,790
în acest caz, de divizare
ceva în jumătate din nou, și din nou,

313
00:15:20,790 --> 00:15:25,790
și din nou, și din nou, astfel încât să
devine din ce în ce mic ca sa faci asta.

314
00:15:25,790 --> 00:15:28,470
>> Deci, jurnal de n se referă, sigur,
de exemplu cartea de telefon,

315
00:15:28,470 --> 00:15:32,662
a binar de căutare în teorie, când ne-am
a avut ușile virtuale de pe bord,

316
00:15:32,662 --> 00:15:34,370
sau când Sean a fost
căutând ceva.

317
00:15:34,370 --> 00:15:37,374
Dacă ar fi folosit binar de căutare, log n
ar fi limita superioară a de cât de mult

318
00:15:37,374 --> 00:15:38,040
timp care ia.

319
00:15:38,040 --> 00:15:44,027
Dar aceste algoritmi, care a fugit în
log n asumat ceea ce detaliu cheie?

320
00:15:44,027 --> 00:15:45,360
Aceasta lista a fost sortate, nu?

321
00:15:45,360 --> 00:15:47,789
Algoritmul tau este greșit dacă
datele introduse nu sunt sortate,

322
00:15:47,789 --> 00:15:49,830
și totuși îl utilizați
ceva de genul binar de căutare

323
00:15:49,830 --> 00:15:51,704
pentru că s-ar putea sari
drept asupra elementului

324
00:15:51,704 --> 00:15:53,600
fără să realizeze că e într-adevăr acolo.

325
00:15:53,600 --> 00:15:55,600
>> Acum, ceea ce ar putea însemna aceasta, O mare de unul?

326
00:15:55,600 --> 00:15:59,117
Acest lucru nu înseamnă că algoritmul dvs.
ia unul și numai un singur pas,

327
00:15:59,117 --> 00:16:01,200
aceasta înseamnă doar este nevoie de o
număr constant de pași.

328
00:16:01,200 --> 00:16:04,060
Poate e un, poate e
10, poate e 1000,

329
00:16:04,060 --> 00:16:07,750
dar este independent de
dimensiunea problemei.

330
00:16:07,750 --> 00:16:10,850
Nu contează cât de mare n este,
un algoritm de timp constant

331
00:16:10,850 --> 00:16:12,747
are întotdeauna același număr de pași.

332
00:16:12,747 --> 00:16:15,080
Deci, ceea ce ar putea fi un algoritm
am vorbit despre sau doar

333
00:16:15,080 --> 00:16:20,418
intuitiv care vine la tine că
întotdeauna se execută în așa-numita constanta de timp?

334
00:16:20,418 --> 00:16:20,918
Da?

335
00:16:20,918 --> 00:16:22,001
>> Audiența: Adăugați două numere.

336
00:16:22,001 --> 00:16:25,320
SPEAKER: Adăugați două numere,
2 plus 2 egal 4, terminat.

337
00:16:25,320 --> 00:16:27,227
Deci, care ar putea lucra, ce altceva?

338
00:16:27,227 --> 00:16:28,560
Cum despre lumea mai real, da?

339
00:16:28,560 --> 00:16:30,686
>> Audiența: Găsirea
primul lucru într-o listă.

340
00:16:30,686 --> 00:16:32,810
SPEAKER: Găsirea primul
element dintr-o listă, sigur.

341
00:16:32,810 --> 00:16:34,540
Am fost de fapt vorbesc
despre tablouri deja,

342
00:16:34,540 --> 00:16:36,540
cum a face tu a lua de la
primul element dintr-o matrice,

343
00:16:36,540 --> 00:16:40,465
indiferent de cât de mult
matrice este în cod C?

344
00:16:40,465 --> 00:16:43,090
Tocmai ai folosi ca suportul
notație de zero, bam, tu esti acolo.

345
00:16:43,090 --> 00:16:46,120
Și într-adevăr, tablouri, ca o parte,
suport ceva cunoscut în general

346
00:16:46,120 --> 00:16:49,240
ca acces aleator, cu acces aleator
memorie, pentru că puteți pur și simplu

347
00:16:49,240 --> 00:16:50,284
sări la un singur loc.

348
00:16:50,284 --> 00:16:52,700
Putem face acest lucru chiar mai mult, pur și simplu
putem derula la săptămână la zero

349
00:16:52,700 --> 00:16:53,900
când am făcut Scratch.

350
00:16:53,900 --> 00:16:59,707
Cât timp a durat pentru
spune bloc în Scratch pentru a executa?

351
00:16:59,707 --> 00:17:00,790
Doar constantă de timp, nu?

352
00:17:00,790 --> 00:17:03,960
Spune ceva, spune
ceva, nu contează

353
00:17:03,960 --> 00:17:07,359
cum zgârieturi mari mondial este, este întotdeauna
de gând să ia aceeași cantitate de timp

354
00:17:07,359 --> 00:17:08,490
a spune pur și simplu ceva.

355
00:17:08,490 --> 00:17:11,089
>> Deci, asta e constanta de timp,
dar ceea ce este de cealaltă parte?

356
00:17:11,089 --> 00:17:13,030
În cazul în care a fost superior
limite, dacă vrem

357
00:17:13,030 --> 00:17:17,089
pentru a descrie limitele inferioare
a algoritmilor de funcționare timp?

358
00:17:17,089 --> 00:17:19,852
Aproape un cel mai bun caz
potențial, dacă vreți,

359
00:17:19,852 --> 00:17:23,060
deși acești termeni ar putea aplica cel mai bine
cazuri, mai grave cazuri, cazuri medie, mai

360
00:17:23,060 --> 00:17:26,359
în general, dar să ne concentrăm
pe limite mai mici, mai general.

361
00:17:26,359 --> 00:17:31,920
Ce este un algoritm care are
o limită inferioară de n pași,

362
00:17:31,920 --> 00:17:33,350
sau etape 2n, sau etape 3n?

363
00:17:33,350 --> 00:17:36,241
Unele factor de n pași,
care este mai mic de legat.

364
00:17:36,241 --> 00:17:36,740
Da?

365
00:17:36,740 --> 00:17:37,910
>> Audiența: Bubble fel?

366
00:17:37,910 --> 00:17:41,610
>> SPEAKER: Bubble sort ia
tu n minim trepte, de ce?

367
00:17:41,610 --> 00:17:42,279
De ce este asta?

368
00:17:42,279 --> 00:17:45,320
De ce ar trebui ca început să vină la tine
intuitiv, chiar dacă o face doar

369
00:17:45,320 --> 00:17:46,530
încă?

370
00:17:46,530 --> 00:17:47,030
Da?

371
00:17:47,030 --> 00:17:47,990
>> Audiența: [inaudibil].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
SPEAKER: Exact.

374
00:17:52,360 --> 00:17:55,810
În cel mai bun scenariu posibil de
bule fel, și o mulțime de algoritmi,

375
00:17:55,810 --> 00:17:58,769
dacă am mână opt persoane
care sunt deja sortate,

376
00:17:58,769 --> 00:18:00,560
ar fi o prostie
pentru tine, algoritmul,

377
00:18:00,560 --> 00:18:02,202
pentru a merge înainte și înapoi
mai mult de o dată, nu?

378
00:18:02,202 --> 00:18:04,285
Pentru că de îndată ce
de mers pe jos prin lista dată,

379
00:18:04,285 --> 00:18:08,090
ar trebui să realizeze, oh, am făcut nici o
swap-uri, această listă este sortată, ieșire.

380
00:18:08,090 --> 00:18:09,700
Dar asta nu te va lua n pași.

381
00:18:09,700 --> 00:18:12,033
>> Și invers, ceea ce este un alt
mod de gândire despre el?

382
00:18:12,033 --> 00:18:15,240
Bubble sort este un omega,
ca să spunem așa, de n,

383
00:18:15,240 --> 00:18:19,050
pentru că dacă te uiți la
mai puțin de n elemente, ceea ce

384
00:18:19,050 --> 00:18:23,009
este problema fundamentală acolo?

385
00:18:23,009 --> 00:18:24,550
Nu știi dacă e sortate, chiar.

386
00:18:24,550 --> 00:18:26,800
Noi, oamenii, s-ar putea privire la opt
oameni și să fie ca, oh, e sortate,

387
00:18:26,800 --> 00:18:28,430
că nu m-n pași iau, dar a făcut-o.

388
00:18:28,430 --> 00:18:30,810
Ochii tăi, chiar daca natură
a avea un domeniu mare de vizibilitate,

389
00:18:30,810 --> 00:18:33,184
te-ai uitat la opt elemente,
te-ai uitat la opt persoane,

390
00:18:33,184 --> 00:18:34,610
E opt trepte în mod eficient.

391
00:18:34,610 --> 00:18:38,612
Și numai dacă am mers prin toată
Lista nu îmi dau seama, da, sortate.

392
00:18:38,612 --> 00:18:41,320
Dacă mă opresc la jumătatea drumului de gândire, toate
drept, e destul de sortat până acum,

393
00:18:41,320 --> 00:18:42,520
care sunt sansele nu e sortate?

394
00:18:42,520 --> 00:18:44,186
Asta nu algoritmi va fi corect.

395
00:18:44,186 --> 00:18:46,250
S-ar putea fi mai rapid, dar incorect.

396
00:18:46,250 --> 00:18:48,500
>> Deci, acum avem un fel de
descrie o limite inferioare,

397
00:18:48,500 --> 00:18:49,710
și ce despre constanta de timp?

398
00:18:49,710 --> 00:18:54,565
Ce este un algoritm care are o mai mică
legat pe timp de funcționare de unul?

399
00:18:54,565 --> 00:18:58,350
1 pas, 2 trepte, 10 pași, dar
constantă, independent de n,

400
00:18:58,350 --> 00:18:59,310
mărimea de intrare?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Da, în spate.

403
00:19:04,600 --> 00:19:05,309
>> Audiența: printf?

404
00:19:05,309 --> 00:19:06,183
SPEAKER: Ce-i asta?

405
00:19:06,183 --> 00:19:07,184
Audiența: printf?

406
00:19:07,184 --> 00:19:07,850
SPEAKER: printf.

407
00:19:07,850 --> 00:19:08,400
OK, sigur.

408
00:19:08,400 --> 00:19:10,720
Deci, este nevoie de un număr fix de pași.

409
00:19:10,720 --> 00:19:13,170
Și ar trebui să acum-- acum că
vorbim despre cod C

410
00:19:13,170 --> 00:19:16,040
și nu Scratch, ceva
ca să zicem, cu printf,

411
00:19:16,040 --> 00:19:17,710
noi ar trebui să înceapă să se atent.

412
00:19:17,710 --> 00:19:21,090
Pentru ca printf ia
de intrare, este un șir de caractere,

413
00:19:21,090 --> 00:19:23,220
și siruri de caractere nu au punct de vedere tehnic lungime.

414
00:19:23,220 --> 00:19:25,530
Deci, dacă acum ne-o dorim pentru a alege
pe tine, dacă nu te superi,

415
00:19:25,530 --> 00:19:29,430
punct de vedere tehnic am putea argumenta că printf
se ia o intrare de lungime variabilă,

416
00:19:29,430 --> 00:19:32,270
și cu siguranță ar putea dura mai mult
timp pentru a imprima un șir atât de mult,

417
00:19:32,270 --> 00:19:33,560
decât acest timp.

418
00:19:33,560 --> 00:19:36,570
>> Deci, ceea ce, dacă luăm în considerare doar
sortarea și căutarea exemple?

419
00:19:36,570 --> 00:19:40,450
Ce despre Mike Smith în telefon
carte, sau binar de căutare, mai general?

420
00:19:40,450 --> 00:19:42,220
În cel mai bun caz, ceea ce s-ar putea întâmpla?

421
00:19:42,220 --> 00:19:45,577
Am deschis cartea de telefon și, bam,
există numărul lui Mike Smith.

422
00:19:45,577 --> 00:19:46,660
Pot să-l sun imediat.

423
00:19:46,660 --> 00:19:49,390
>> A luat un pas, poate doi pași,
dar un număr constant de pași

424
00:19:49,390 --> 00:19:50,230
dacă am avut noroc.

425
00:19:50,230 --> 00:19:52,570
Și sincer, am văzut pe
Luni colegul tău

426
00:19:52,570 --> 00:19:54,710
obține destul de norocos de două ori la rând.

427
00:19:54,710 --> 00:19:57,050
Și asta a fost, într-adevăr constant
timp într-o limite inferioare

428
00:19:57,050 --> 00:20:01,280
pe algoritmul în cauză pentru a găsi
numărul 50 în spatele celor închis

429
00:20:01,280 --> 00:20:01,830
usi.

430
00:20:01,830 --> 00:20:06,400
>> Acum, ca o paranteza, dacă veți descoperi
că atât de mare O, marginea superioară,

431
00:20:06,400 --> 00:20:09,310
și omega, limita inferioară,
sunt una în același, că

432
00:20:09,310 --> 00:20:11,830
este aceeași formulă în
paranteze, puteți, de asemenea

433
00:20:11,830 --> 00:20:15,170
spune, doar pentru a fi de lux,
că ceva este în theta

434
00:20:15,170 --> 00:20:18,270
de n sau teta de o alta valoare.

435
00:20:18,270 --> 00:20:20,661
Asta înseamnă că, atunci când mare
O și omega sunt aceleași.

436
00:20:20,661 --> 00:20:21,910
Acum, ce zici de selecție fel?

437
00:20:21,910 --> 00:20:23,400
Să folosim acest nou vocabular.

438
00:20:23,400 --> 00:20:27,407
În selecție fel, ceea ce am fost noi
face din nou, și din nou, și din nou?

439
00:20:27,407 --> 00:20:29,990
Am fost de gând înainte și înapoi prin
lista, în căutarea pentru cine?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
Cel mai mic număr.

442
00:20:34,730 --> 00:20:37,560
>> Deci, cum de multe etape, cum
mai multe comparații am făcut

443
00:20:37,560 --> 00:20:43,250
trebuie să facă, în scopul de a da seama cine
cel mai mic element din listă a fost?

444
00:20:43,250 --> 00:20:44,437
n minus 1, corect?

445
00:20:44,437 --> 00:20:47,770
Pentru că dacă am începe cu cel pe care îl am
dat și eu încep el sau ea a comparat,

446
00:20:47,770 --> 00:20:49,519
atunci el sau ea, l-
sau ei, el sau ea, eu

447
00:20:49,519 --> 00:20:52,010
poate asocia numai elemente
împreună n minus 1 de ori.

448
00:20:52,010 --> 00:20:55,630
Deci selecție are un fel similar
n minus 1 pașii pentru prima dată.

449
00:20:55,630 --> 00:20:59,540
>> Câți pași nu-l mă ducă la
găsi de-al doilea mai mic element?

450
00:20:59,540 --> 00:21:02,920
n minus 2, pentru că eu sunt prost fiind
dacă mă tot uitam la aceiasi oameni

451
00:21:02,920 --> 00:21:06,280
din nou, în cazul în care l-am ales deja
sau ei și le-a pus în locul lor.

452
00:21:06,280 --> 00:21:09,270
Și a treia etapă, n
minus 3, atunci n minus 4.

453
00:21:09,270 --> 00:21:11,020
Am văzut acest model
înainte, și într-adevăr

454
00:21:11,020 --> 00:21:13,460
selecție fel similar
a legat un superior

455
00:21:13,460 --> 00:21:16,210
de n pătrat dacă facem aia de sumare.

456
00:21:16,210 --> 00:21:19,790
Ce este limita inferioară, selecție fel ei?

457
00:21:19,790 --> 00:21:25,350
Minim, cât de mult timp de selecție trebuie să
fel ia, așa cum l-am definit pe luni?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Propune două opțiuni.

460
00:21:30,490 --> 00:21:32,360
Poate e n, la fel ca înainte.

461
00:21:32,360 --> 00:21:35,040
Poate e n patrat, așa cum se
este acum ca marginea superioară.

462
00:21:35,040 --> 00:21:35,874
>> Audiența: n patrat.

463
00:21:35,874 --> 00:21:36,664
SPEAKER: n patrat.

464
00:21:36,664 --> 00:21:37,368
De ce?

465
00:21:37,368 --> 00:21:40,060
>> Audiența: Pentru că ai
pentru a defini [neauzit].

466
00:21:40,060 --> 00:21:41,510
>> SPEAKER: Exact.

467
00:21:41,510 --> 00:21:45,077
Cel puțin așa cum am definit selecție fel
a fost destul de naiv, continua,

468
00:21:45,077 --> 00:21:46,160
găsi cel mai mic element.

469
00:21:46,160 --> 00:21:47,770
Du-te din nou, a găsi cel mai mic element.

470
00:21:47,770 --> 00:21:49,490
Du-te din nou, a găsi cel mai mic element.

471
00:21:49,490 --> 00:21:51,700
Nu e nici un fel de
optimizare acolo că

472
00:21:51,700 --> 00:21:54,350
s-ar putea să-mi abandona după
doar n sau cam asa ceva pași.

473
00:21:54,350 --> 00:21:57,080
Deci, într-adevăr, selecție
fel, omega de n la patrat.

474
00:21:57,080 --> 00:22:00,667
>> Ce fel de inserție, unde am luat
cine a fost dat, iar apoi l-am plopped

475
00:22:00,667 --> 00:22:01,750
sau ei în locul potrivit?

476
00:22:01,750 --> 00:22:04,958
Apoi am procedat la persoana a doua,
el sau ea se trânti în locul potrivit.

477
00:22:04,958 --> 00:22:07,910
Apoi, următoarea persoană, trânti
el sau ea în locul potrivit.

478
00:22:07,910 --> 00:22:10,537
Observați că acest lucru este foarte
liniar, ca să spunem așa.

479
00:22:10,537 --> 00:22:12,620
Sunt o linie dreaptă, eu sunt
Nu merge înainte și înapoi,

480
00:22:12,620 --> 00:22:16,080
N-am mai uita înapoi într-adevăr, dar
ceea ce se întâmplă atunci când l-am insera

481
00:22:16,080 --> 00:22:20,302
sau ei în începutul de
lista așa cum am făcut-o luni?

482
00:22:20,302 --> 00:22:21,010
Ce se întâmplă?

483
00:22:21,010 --> 00:22:21,510
Da?

484
00:22:21,510 --> 00:22:23,122
Audiența: [inaudibil].

485
00:22:23,122 --> 00:22:24,830
Vorbitor: Da,
a fost captura, corect?

486
00:22:24,830 --> 00:22:26,746
S-ar putea aminti de
colegii dumneavoastră, în cazul în care

487
00:22:26,746 --> 00:22:29,670
s-au a face orice mișcare cu
picioarele lor, că a fost o operație.

488
00:22:29,670 --> 00:22:33,610
Deci, dacă au fost trei oameni aici și
noua persoana a apartinut mod acolo,

489
00:22:33,610 --> 00:22:37,360
pe o scenă mult timp ca aceasta, sigur, el
sau ea ar putea merge chiar până la capăt.

490
00:22:37,360 --> 00:22:40,074
Dar dacă ne gândim la o
calculator și o serie de memorie,

491
00:22:40,074 --> 00:22:41,990
aceste persoane vor
să aibă de a amesteca peste

492
00:22:41,990 --> 00:22:43,260
pentru a face loc pentru acea persoană.

493
00:22:43,260 --> 00:22:46,930
Și astfel încât n minus 1 shufflings,
n minus 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
minus 3 shufflings este doar un fel de
întâmplă în spatele meu, nu în fața mea

495
00:22:50,660 --> 00:22:52,710
ca și mai înainte, într-un sens.

499
00:22:52,557 --> 00:22:54,640
Acum, ca o paranteza, și ca
este posibil să fi văzut on-line

500
00:22:54,640 --> 00:22:57,699
dacă începe să bagi în jurul despre
felul, există atât de multe altele diferite

501
00:22:57,699 --> 00:22:59,490
acolo, unele dintre ele
mai bine decât altele.

502
00:22:59,490 --> 00:23:02,200
Într-adevăr, este unul bogosort
că e un fel de distractiv să se uite în sus.

503
00:23:02,200 --> 00:23:06,650
Bogosort ia un set de
numere sau spune un pachet de cărți,

504
00:23:06,650 --> 00:23:09,870
le amesteca la întâmplare, și
verifică dacă acestea sunt clasificate în funcție.

505
00:23:09,870 --> 00:23:12,130
Și dacă nu, o face din nou.

506
00:23:12,130 --> 00:23:14,140
Și dacă nu, o face din nou.

507
00:23:14,140 --> 00:23:15,440
Dacă nu, o face din nou.

508
00:23:15,440 --> 00:23:17,060
Incredibil de prost.

509
00:23:17,060 --> 00:23:19,520
>> Și, într-adevăr, dacă ai citit
ca articolul din Wikipedia,

510
00:23:19,520 --> 00:23:21,200
porecla ei este un fel de prost.

511
00:23:21,200 --> 00:23:25,180
Acesta va funcționa în cele din urmă,
sperăm, dat fiind suficient timp,

512
00:23:25,180 --> 00:23:28,240
dar acea cantitate de timp
ar putea dura ceva timp.

513
00:23:28,240 --> 00:23:31,650
Deci, dacă aș putea, hai sa lucruri de viteză
de la exemplul Mary Beth lui mai devreme,

514
00:23:31,650 --> 00:23:35,150
de a avea ceva mai multe elemente,
dar mai mult de două procesoare.

515
00:23:35,150 --> 00:23:37,100
Doi oameni, dacă
nu m-ar deranja alaturi de mine.

516
00:23:37,100 --> 00:23:40,972
Ce zici de o aici, și
Să go-- nimeni pe acolo?

517
00:23:40,972 --> 00:23:41,722
Nimeni de acolo?

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
Tu cu negru
cămașă, da, vin pe jos.

520
00:23:44,190 --> 00:23:45,000
Bine, care e numele tău?

521
00:23:45,000 --> 00:23:45,720
>> Audiența: Peter.

522
00:23:45,720 --> 00:23:46,100
>> SPEAKER: Ce-i asta?

523
00:23:46,100 --> 00:23:46,766
>> Audiența: Peter.

524
00:23:46,766 --> 00:23:49,450
Vorbitor: Peter, David, mă bucur să te cunosc.

525
00:23:49,450 --> 00:23:53,670
În regulă, avem Peter aici, dacă
Vrei să vii pe masa aici.

526
00:23:53,670 --> 00:23:54,550
Și cum te cheamă?

527
00:23:54,550 --> 00:23:55,216
>> Audiența: Elena.

528
00:23:55,216 --> 00:23:55,970
SPEAKER: Elena.

529
00:23:55,970 --> 00:23:57,030
OK, mă bucur să te cunosc.

530
00:23:57,030 --> 00:23:58,060
Elena întâlni Peter.

531
00:23:58,060 --> 00:23:59,170
Peter, Elena.

532
00:23:59,170 --> 00:24:02,290
Și vom avea nevoie de Andrew
până aici, de asemenea, vă rog.

533
00:24:02,290 --> 00:24:06,107
Iar provocarea se întâmplă
să fie pentru a sorta un pachet de cărți.

534
00:24:06,107 --> 00:24:08,190
Și dacă nefamiliare, punte
de carduri ar trebui în cele din urmă

535
00:24:08,190 --> 00:24:11,064
fi sortate ceva ca
aceasta în cazul în care vom face cluburilor, apoi

536
00:24:11,064 --> 00:24:13,660
de pică, apoi inimile și
diamante, de la as fi unul,

537
00:24:13,660 --> 00:24:15,570
tot drumul până la rege.

538
00:24:15,570 --> 00:24:20,890
>> Cardurile am de gând să vă dau
vor fi 52 în cantitate.

539
00:24:20,890 --> 00:24:23,160
Vom similar
tu timp, într-o clipă.

540
00:24:23,160 --> 00:24:26,410
Vom arunca Andrew
pe ecran aici,

541
00:24:26,410 --> 00:24:28,170
astfel încât să privesc cum faci acest lucru.

542
00:24:28,170 --> 00:24:31,070
Si pentru ca toate acestea
este cu atât mai vizibil,

543
00:24:31,070 --> 00:24:33,490
acestea sunt cărțile am primit pe Amazon.

544
00:24:33,490 --> 00:24:42,861
Deci, ele sunt deja la întâmplare
sortate, iar noi te vom cronometra.

545
00:24:42,861 --> 00:24:44,610
Și vom
păstrați-l real, de data aceasta,

546
00:24:44,610 --> 00:24:47,820
așa că vom încerca să te presez
pentru că în caz contrar aceasta va primi plictisitor

547
00:24:47,820 --> 00:24:48,460
repede.

548
00:24:48,460 --> 00:24:53,860
Dacă ai putea continua să sortați 52
elemente împreună prin intermediul unor mijloace, acum.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> Și, din nou, ca ne uitam acestea
baieti fac ceea ce, în cele din urmă

551
00:25:07,180 --> 00:25:10,200
se va produce o evidentă
urmare, cred că într-adevăr despre

552
00:25:10,200 --> 00:25:12,962
cum acestea sunt fiecare o face,
cum s-ar putea descrie.

553
00:25:12,962 --> 00:25:15,045
Pentru că din nou, acestea sunt
toate procesele, algoritmi

554
00:25:15,045 --> 00:25:17,090
pe care le ia pentru a acordat ca un om.

555
00:25:17,090 --> 00:25:22,349
Dar ai avut, probabil, mult timp
intuiție, cu mult înainte de tine, chiar

556
00:25:22,349 --> 00:25:24,390
gândit de a lua o
tu clasă de informatică

557
00:25:24,390 --> 00:25:27,223
ar fi avut intuiția cu
care pentru a rezolva problemele de acest gen.

558
00:25:27,223 --> 00:25:29,560
Dar, odată ce recunoaște
modele și începe

559
00:25:29,560 --> 00:25:32,407
pentru a formaliza pașii cu care
te rezolvarea acestor probleme,

560
00:25:32,407 --> 00:25:35,490
veți găsi pe care le poate rezolva mult
mai interesant și mult mai complex

561
00:25:35,490 --> 00:25:39,190
Probleme rapid.

562
00:25:39,190 --> 00:25:42,351
Deci, cineva din public, ceea ce este
cel puțin un element al algoritmului

563
00:25:42,351 --> 00:25:43,350
pe care le utilizați aici?

564
00:25:43,350 --> 00:25:44,275
>> Audiența: [inaudibil]

565
00:25:44,275 --> 00:25:45,150
SPEAKER: Ce-i asta?

566
00:25:45,150 --> 00:25:47,062
Audiența: Prin costum.

567
00:25:47,062 --> 00:25:47,770
SPEAKER: Prin costum.

568
00:25:47,770 --> 00:25:50,630
Deci, în primul rând ei se grupează
toate diamantele împreună

569
00:25:50,630 --> 00:25:52,560
se pare, tot de la
inimile împreună, se pare,

570
00:25:52,560 --> 00:25:56,520
și așa mai departe, fără respectarea
pentru numerele de pe carduri.

571
00:25:56,520 --> 00:26:00,900
Și acum apar, de exemplu,
să fie sortarea acestea în număr.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Foarte bine.

574
00:26:08,910 --> 00:26:12,370
>> Bine, deci ce se întâmplă la
fi ultimul pas, atunci aici?

575
00:26:12,370 --> 00:26:16,950
După ce vom avea patru costume sortate, ceea ce
avem nevoie pentru a face la cele patru piloți

576
00:26:16,950 --> 00:26:20,059
pentru a realiza o
clasificate în funcție de punte, pur și simplu?

577
00:26:20,059 --> 00:26:21,350
Deci, avem nevoie pentru a le îmbina din nou.

578
00:26:21,350 --> 00:26:25,160
>> Deci, există o idee interesantă care
din nou, îndrăznesc să spun, este foarte intuitiv chiar

579
00:26:25,160 --> 00:26:28,140
daca nu s-ar fi pălmuit
acest tip de eticheta pe ea.

580
00:26:28,140 --> 00:26:31,900
Această noțiune fundamentală de divizare
problema nu în jumătate de data aceasta,

581
00:26:31,900 --> 00:26:33,410
dar cel puțin în patru bucăți.

582
00:26:33,410 --> 00:26:36,810
Rezolvarea destul de mult
Probleme fundamental identice

583
00:26:36,810 --> 00:26:40,480
izolat unul de celălalt,
și apoi fuzionarea rezultatele.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
Și, excelent, terminat.

586
00:26:50,140 --> 00:26:52,140
Bine, o rundă de mare
de aplauze, dacă am putea.

587
00:26:52,140 --> 00:26:56,480
>> [Aplauze]

588
00:26:56,480 --> 00:26:59,740
>> Difuzor: Nu am nici o idee despre ceea ce veți
face cu acestea, dar aici te duci.

589
00:26:59,740 --> 00:27:01,690
Vă mulțumesc foarte mult.

590
00:27:01,690 --> 00:27:04,660
Deci, hai sa vedem, la doua minute
și opt secunde,

591
00:27:04,660 --> 00:27:07,490
dacă doriți să conteste prietenii tăi.

592
00:27:07,490 --> 00:27:12,160
Ce apoi se va
fie o ia de la această

593
00:27:12,160 --> 00:27:13,830
că ne putem mobiliza mai mult, în general?

594
00:27:13,830 --> 00:27:16,080
Ei bine, cred că înapoi la
această matrice de numere,

595
00:27:16,080 --> 00:27:19,060
și cred că înapoi acum la unele dintre cele mai
pseudocod am scris in trecut,

596
00:27:19,060 --> 00:27:22,080
iar acest lucru a fost Pseudocodul pentru
rezolvarea problemei cartea de telefon.

597
00:27:22,080 --> 00:27:25,150
Din ce în pseudocod I
enumerat un mod mai metodic

598
00:27:25,150 --> 00:27:28,400
de a descrie cum am facut-o foarte intuitiv
Algoritmul uman de împărțire a telefonului

599
00:27:28,400 --> 00:27:31,650
carte în jumătate, repeta, repeta, repeta,
până găsesc pe cineva ca Mike Smith,

600
00:27:31,650 --> 00:27:33,790
dacă el este într-adevăr în cartea de telefon.

601
00:27:33,790 --> 00:27:37,610
>> Dar am un fel de folosit ceea ce voi numi
o abordare foarte iterativ aici,

602
00:27:37,610 --> 00:27:42,160
în aviz special linia 8 si linia 11.

603
00:27:42,160 --> 00:27:46,750
Acestea sunt dovezi ale unei iterativ
abordare, o abordare looping,

604
00:27:46,750 --> 00:27:49,040
pentru că exact
comportamentul ei induce.

605
00:27:49,040 --> 00:27:52,910
Aceste linii ambele spun du-te la
fel linie de trei, și puteți de

606
00:27:52,910 --> 00:27:55,140
cred că de la dvs.
ochii minții lui ca fiind o buclă.

607
00:27:55,140 --> 00:27:59,080
Acesta îți spune să te întorci până la pasul
trei și se repetă, din nou, și din nou,

608
00:27:59,080 --> 00:28:00,010
și din nou.

609
00:28:00,010 --> 00:28:04,410
>> Dar dacă ne folosim o idee cheie
aici că am făcut nu ultima oară,

610
00:28:04,410 --> 00:28:10,280
și simplifica linia 8 și
linia 11 și vecinii lor

611
00:28:10,280 --> 00:28:12,840
ca doar acest lucru, în galben.

612
00:28:12,840 --> 00:28:16,480
Nu este fundamental scurtarea
Pseudocodul foarte mult,

613
00:28:16,480 --> 00:28:20,530
dar este fundamental în schimbare
natura algoritmul meu.

614
00:28:20,530 --> 00:28:24,220
Ceea ce vreau să spun acum
în etapa 7, în etapa 10,

615
00:28:24,220 --> 00:28:29,140
este de a căuta pentru Mike
în același mod exact,

616
00:28:29,140 --> 00:28:31,580
dar doar în partea stângă
jumătate sau jumătatea din dreapta.

617
00:28:31,580 --> 00:28:33,420
>> Cu alte cuvinte, dacă
Am început de la pasul unu,

618
00:28:33,420 --> 00:28:36,150
ridica cartea de telefon, deschis la mijloc
din cartea de telefon, uita-te la nume,

619
00:28:36,150 --> 00:28:39,010
dacă Smith este unul dintre
numele lui, suna Mike, altfel

620
00:28:39,010 --> 00:28:44,340
dacă Smith este mai devreme în carte, pas șapte
căuta Mike la jumătate din stânga a cărții.

621
00:28:44,340 --> 00:28:47,130
Dar acest tip de se simte ca
ea mă părăsește agățat, nu?

622
00:28:47,130 --> 00:28:49,240
In galben, este un
instrucțiuni, dar cum nu am

623
00:28:49,240 --> 00:28:51,870
cauta Mike în stânga
jumătate din cartea de telefon?

624
00:28:51,870 --> 00:28:54,210
În cazul în care nu am un
algoritm cu care am

625
00:28:54,210 --> 00:28:57,100
Puteți căuta pe cineva ca Mike Smith?

626
00:28:57,100 --> 00:28:58,980
Ei bine, ne-a mirat în față.

627
00:28:58,980 --> 00:29:03,090
Eu pot folosi literalmente exact la fel
Programul va efectiv până la partea de sus

628
00:29:03,090 --> 00:29:06,490
din nou și re-alergare
aceleași linii de cod.

629
00:29:06,490 --> 00:29:10,610
>> Deci, chiar dacă acest lucru ar trebui să se simtă
ca un pic de o definiție ciclic

630
00:29:10,610 --> 00:29:13,480
în cazul în care răspunzi cuiva
întrebare cu doar un fel de a cere

631
00:29:13,480 --> 00:29:15,990
aceeași întrebare din nou,
cum ar fi de ce, de ce, de ce?

632
00:29:15,990 --> 00:29:21,580
Realitatea este că ne-am codat greu
o pereche de linii speciale, etapa 4,

633
00:29:21,580 --> 00:29:25,320
care este un dacă, și 12, care
este efectiv o altă ramură,

634
00:29:25,320 --> 00:29:30,120
pentru că avem aceste măsuri masura provizoare,
acest algoritm va termina dacă vom

635
00:29:30,120 --> 00:29:32,050
găsi Mike, sau dacă nu o facem.

636
00:29:32,050 --> 00:29:36,810
Dar, în pasul 7 și 10 acum, ne-am
ceea ce vom numi un algoritm recursiv.

637
00:29:36,810 --> 00:29:40,420
Și recursivitate este într-adevăr o idee puternic
că e un pic mintea îndoire la început,

638
00:29:40,420 --> 00:29:42,500
pe care le putem aplica acum, după cum urmează.

639
00:29:42,500 --> 00:29:46,600
>> Merge fel va fi ultima genul asta
ne uităm la, cel puțin în clasa oficial.

640
00:29:46,600 --> 00:29:50,040
Și este fundamental diferit
de la cei trecut trei, și, desigur,

641
00:29:50,040 --> 00:29:52,140
Ultima patru dacă includem bogosort.

642
00:29:52,140 --> 00:29:54,810
Iată Pseudocodul pentru îmbinare fel.

643
00:29:54,810 --> 00:30:00,170
Când la intrare de n elemente, astfel încât dat
o matrice de dimensiune n, în cazul în care n este mai mic de 2,

644
00:30:00,170 --> 00:30:01,040
reveni.

645
00:30:01,040 --> 00:30:03,610
Deci, de ce nu am că
bun-simț verificați mai întâi?

646
00:30:03,610 --> 00:30:09,477
Care este implicarea, dacă am mână
o matrice a cărui lungime n este mai mic de 2?

647
00:30:09,477 --> 00:30:11,060
Este deja sortate, în mod evident, nu?

648
00:30:11,060 --> 00:30:13,640
Deoarece lista are fie
un element, care este trivial

649
00:30:13,640 --> 00:30:15,180
clasificate în funcție pentru că e
singurul lucru acolo.

650
00:30:15,180 --> 00:30:18,138
Sau, este de dimensiunea zero, ceea ce înseamnă
nu e nimic pentru a sorta, astfel de natură

651
00:30:18,138 --> 00:30:18,720
este sortat.

652
00:30:18,720 --> 00:30:20,410
Nu este nimic în neregulă acolo.

653
00:30:20,410 --> 00:30:22,310
Deci, asta e așa-numitul caz noastră de bază.

654
00:30:22,310 --> 00:30:24,440
>> Aceasta este similară în spirit
pentru ceea ce am făcut cu Mike.

655
00:30:24,440 --> 00:30:26,023
Dacă lui Mike în cartea de telefon, suna-l.

656
00:30:26,023 --> 00:30:27,740
Dacă nu e acolo, renunta.

657
00:30:27,740 --> 00:30:31,240
Este o așa-numită caz ​​de bază, pentru a se asigura
acest algoritm, la sfârșitul zilei

658
00:30:31,240 --> 00:30:33,540
va opri în anumite circumstanțe.

659
00:30:33,540 --> 00:30:37,890
>> Dar aici e un salt de credință acum, altceva,
sorta jumătatea stângă a elementelor,

660
00:30:37,890 --> 00:30:39,740
apoi sorta dreapta
jumătate a elementelor,

661
00:30:39,740 --> 00:30:41,189
și apoi îmbinați jumătățile sortate.

662
00:30:41,189 --> 00:30:43,230
Și aici e în cazul în care se simte
ca și cum am tocmit afară.

663
00:30:43,230 --> 00:30:46,900
Te-am rugat să sortați
n elemente, și eu sunt

664
00:30:46,900 --> 00:30:50,712
zis, OK, nu prin sortarea
partea stângă și sortarea dreapta.

665
00:30:50,712 --> 00:30:52,420
Dar eu spun una
alt lucru, și aceasta

666
00:30:52,420 --> 00:30:55,530
este tema cheie se pare
în intuiția până acum,

667
00:30:55,530 --> 00:30:57,380
există acest al treilea pas de fuziune.

668
00:30:57,380 --> 00:31:00,430
Care chiar dacă
Pare atât de prost în spirit,

669
00:31:00,430 --> 00:31:02,320
ca fuzioneze doar lucrurile
împreună, se pare

670
00:31:02,320 --> 00:31:05,380
pentru a fi un pas cheie spre
reasamblare a două probleme care

671
00:31:05,380 --> 00:31:07,330
au fost împărțiți în cele din urmă la jumătate.

672
00:31:07,330 --> 00:31:12,090
>> Deci fuzioneze fel, să facem acest lucru, dacă veți
umor mine, cu mai mult de o demonstrație,

673
00:31:12,090 --> 00:31:14,730
doar astfel încât să avem o anumită
numere de a lucra cu.

674
00:31:14,730 --> 00:31:19,470
Pot să schimb opt stres
bile pentru opt persoane?

675
00:31:19,470 --> 00:31:29,320
Bine, ce zici tu trei, patru te
în această secțiune, cinci, șase, și să

676
00:31:29,320 --> 00:31:30,720
Nu 7, 8, haide sus.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK, da OK.

679
00:31:36,520 --> 00:31:38,640
Minus 8, acolo mergem, plus 1.

680
00:31:38,640 --> 00:31:39,150
Excelent.

681
00:31:39,150 --> 00:31:42,000
Toate veni chiar pe sus, să
da repede numere.

682
00:31:42,000 --> 00:31:50,800
Numărul doi, numărul trei, numărul patru,
număr de cinci, șase, șapte, opt.

683
00:31:50,800 --> 00:31:52,140
Am făcut opt ​​corect de data asta.

684
00:31:52,140 --> 00:31:56,390
>> OK, merge atât de departe, dacă ai putea, și
Să sortate în ordinea originală

685
00:31:56,390 --> 00:31:59,810
că am avut ieri care a analizat
ca aceasta, dacă nu te superi.

686
00:31:59,810 --> 00:32:03,620
Și să o facem în fața mesei.

687
00:32:03,620 --> 00:32:06,510
În regulă, deci fuziona fel.

688
00:32:06,510 --> 00:32:08,820
Acest lucru este în cazul în care se va
pentru a obține un fel de interesant,

689
00:32:08,820 --> 00:32:12,800
pentru că mi se pare a fi oferindu-mă
atât de mult mai puține informații de astăzi.

690
00:32:12,800 --> 00:32:15,149
>> Deci fuzioneze fel în primul rând,
pe de intrare de n elemente,

691
00:32:15,149 --> 00:32:18,440
și este, evident, nu mai puțin de două, este
opt, așa că am ceva mai mult de lucru.

692
00:32:18,440 --> 00:32:21,140
Deci, acum ne-am mental ca o clasă
sunt acum în altă ramură,

693
00:32:21,140 --> 00:32:22,540
ceea ce înseamnă trei etape.

694
00:32:22,540 --> 00:32:25,017
În primul rând, trebuie să SORT
jumătate din stânga a elementelor.

695
00:32:25,017 --> 00:32:26,350
Deci, cum merg faci acest lucru?

696
00:32:26,350 --> 00:32:28,950
Ei bine, am de gând să fel de
împărți mental lista de aici,

697
00:32:28,950 --> 00:32:30,700
nu trebuie să
muta punct de vedere fizic, și eu sunt

698
00:32:30,700 --> 00:32:33,180
O să se concentreze doar pe
jumătate din stânga a elementelor de aici.

699
00:32:33,180 --> 00:32:36,770
Deci, cum să mă duc despre sortarea
o listă acum de dimensiune patru?

700
00:32:36,770 --> 00:32:38,730
Care este algoritmul meu?

701
00:32:38,730 --> 00:32:42,580
În primul rând am verificat este n mai puțin de două, nu,
așa că am proceda la blocul altceva din nou.

702
00:32:42,580 --> 00:32:43,900
Sortare lăsat jumătate de elemente.

703
00:32:43,900 --> 00:32:45,608
>> Deci, acum, din nou, mental,
și aici

704
00:32:45,608 --> 00:32:49,550
va trebui să acumuleze o mulțime de
istorie mental, dacă vreți.

705
00:32:49,550 --> 00:32:51,940
Acum, eu sunt de sortare stânga
jumătate din jumătatea stângă.

706
00:32:51,940 --> 00:32:57,000
Bine, acum eu numesc aceeași îmbinare meu
sortare algoritm, este pentru n mai puțin de doi?

707
00:32:57,000 --> 00:33:00,590
Nu, aceasta este de două, așa că trebuie să rezolve
jumătatea din stânga, și jumătatea din dreapta.

708
00:33:00,590 --> 00:33:02,042
Deci, aici vom merge, sorta jumătatea stângă.

709
00:33:02,042 --> 00:33:03,750
De ce nu doar
ia un pas înainte.

710
00:33:03,750 --> 00:33:04,415
Care e numele tău?

711
00:33:04,415 --> 00:33:04,860
>> Audiența: Darren.

712
00:33:04,860 --> 00:33:05,260
>> Difuzor: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan a făcut un pas înainte.

714
00:33:06,040 --> 00:33:06,748
>> Audiența: Darren.

715
00:33:06,748 --> 00:33:09,000
Vorbitor: Darren, făcut.

716
00:33:09,000 --> 00:33:10,090
Ai spus Darren sau Dan?

717
00:33:10,090 --> 00:33:10,550
>> Audiența: Darren.

718
00:33:10,550 --> 00:33:11,216
>> SPEAKER: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren și-a intensificat
el este acum clasificate în funcție înainte și.

720
00:33:14,422 --> 00:33:16,130
Și acest lucru este aproape o
cerere stupid, nu?

721
00:33:16,130 --> 00:33:18,862
Eu nu par într-adevăr să fie realizarea
nimic, dar hai continua.

722
00:33:18,862 --> 00:33:20,820
Acum, permiteți-mi să rezolve dreapta
jumătate a elementelor.

723
00:33:20,820 --> 00:33:21,200
Care e numele tău?

724
00:33:21,200 --> 00:33:21,690
>> Audiența: Luke.

725
00:33:21,690 --> 00:33:22,273
>> SPEAKER: Luke.

726
00:33:22,273 --> 00:33:23,400
Haide, un pas înainte.

727
00:33:23,400 --> 00:33:25,640
Adoptată, am sortat Luke.

728
00:33:25,640 --> 00:33:28,570
Jumătatea din stânga este acum clasificate în funcție și
jumătatea din dreapta este acum clasificate în funcție,

729
00:33:28,570 --> 00:33:30,770
dar din nou, nu e un pas cheie aici.

730
00:33:30,770 --> 00:33:32,940
De ce am lângă trebuie să fac?

731
00:33:32,940 --> 00:33:33,941
Merge jumătățile sortate.

732
00:33:33,941 --> 00:33:36,648
Acum vom avea doar
toți înainte și înapoi, în acest fel,

733
00:33:36,648 --> 00:33:38,620
pentru ca am un fel de nevoie
spațiu zero.

734
00:33:38,620 --> 00:33:40,411
E ca și cum acestea
Voi sunteți pe o masă,

735
00:33:40,411 --> 00:33:42,460
și am nevoie de camera
pentru a le muta în jurul pe.

736
00:33:42,460 --> 00:33:44,170
Așa că am de gând să fuzioneze
voi uitandu

737
00:33:44,170 --> 00:33:45,960
la jumătatea stângă și jumătatea din dreapta.

738
00:33:45,960 --> 00:33:48,740
Și care, evident, este pe primul loc,
jumătate stânga sau pe jumătate dreptate?

739
00:33:48,740 --> 00:33:52,710
Deci jumătate dreptate, așa că să trecem peste Luca
aici la poziția inițială Darren lui.

740
00:33:52,710 --> 00:33:57,640
Și acum să fuzioneze jumătatea lor din stânga în,
Darren se va muta acolo.

741
00:33:57,640 --> 00:33:59,750
>> Deci, se simte ca aproape
un efect balon fel,

742
00:33:59,750 --> 00:34:02,482
dar algoritmul meu fundamental,
foarte diferit de data asta.

743
00:34:02,482 --> 00:34:04,815
Dar acum este în cazul în care lucrurile devin un
putin enervant pentru ca

744
00:34:04,815 --> 00:34:06,810
Trebuie să înapoi mental
unde am plecat de pe.

745
00:34:06,810 --> 00:34:09,893
Tocmai am fuzionat jumatati sortate,
ceea ce înseamnă că sunt în cazul în care în algoritmul meu?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Trebuie să sorteze jumătatea din dreapta, nu?

748
00:34:13,770 --> 00:34:15,910
>> Daca înapoi, la propriu
pe video, veți

749
00:34:15,910 --> 00:34:18,339
vedea că am ajuns la această
punct de Luca și Darren

750
00:34:18,339 --> 00:34:21,370
de sortare stânga
jumătate din jumătatea stângă.

751
00:34:21,370 --> 00:34:23,430
Apoi ne-am unit pe cei
jumătăți sortate, care

752
00:34:23,430 --> 00:34:27,941
înseamnă că următorul pas este genul
jumătate chiar din jumătatea stângă.

753
00:34:27,941 --> 00:34:29,649
Bine, hai să
face acest lucru mult mai repede.

754
00:34:29,649 --> 00:34:33,282
În regulă, șase, am de gând să pretindă
ce sunt acum clasificate în funcție, haide înainte.

755
00:34:33,282 --> 00:34:33,990
Care e numele tău?

756
00:34:33,990 --> 00:34:34,589
>> Audiența: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> SPEAKER: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano este acum clasificate în funcție.

759
00:34:36,010 --> 00:34:36,450
Și cum te cheamă?

760
00:34:36,450 --> 00:34:37,080
>> Audiența: Alex.

761
00:34:37,080 --> 00:34:38,379
>> SPEAKER: Alex este acum clasificate în funcție.

762
00:34:38,379 --> 00:34:40,750
Jumătate la stânga, pe jumătate dreptate,
Care este pasul final?

763
00:34:40,750 --> 00:34:41,250
Merge.

764
00:34:41,250 --> 00:34:44,310
Destul de banal, așa că eu sunt
O să fuzioneze în șase,

765
00:34:44,310 --> 00:34:46,930
ia un pas înapoi,
opt, să ia un pas înapoi.

766
00:34:46,930 --> 00:34:49,530
Și acum observa acest lucru este
un Takeaway util, ceea ce

767
00:34:49,530 --> 00:34:53,930
este acum adevărat despre jumătatea din stânga a
lista, indiferent de cum am început?

768
00:34:53,930 --> 00:34:55,090
Acesta este sortat.

769
00:34:55,090 --> 00:34:57,750
>> Acum nu este sortate în
schema mare a lucrurilor,

770
00:34:57,750 --> 00:35:00,250
dar este sortată în mod independent
de cealaltă jumătate.

771
00:35:00,250 --> 00:35:04,100
Acum, ce pas sunt eu pe dacă am păstra
rebobinare cum a început povestea?

772
00:35:04,100 --> 00:35:05,680
Acum trebuie să rezolve jumătatea din dreapta.

773
00:35:05,680 --> 00:35:07,630
Deci, acum suntem mult înainte, la
începutul poveștii,

774
00:35:07,630 --> 00:35:08,921
și să facem acest lucru mai rapid.

775
00:35:08,921 --> 00:35:11,320
Așa că am de gând pentru a sorta
jumătate chiar din toata lista.

776
00:35:11,320 --> 00:35:13,060
Care este următorul pas?

777
00:35:13,060 --> 00:35:15,840
Sortarea jumătatea din stânga a jumătatea din dreapta.

778
00:35:15,840 --> 00:35:18,715
Sortarea jumătatea stângă a
jumătatea stângă a jumătatea din dreapta.

779
00:35:18,715 --> 00:35:19,590
Și cum te cheamă?

780
00:35:19,590 --> 00:35:20,230
>> Audiența: Omar.

781
00:35:20,230 --> 00:35:21,970
>> Vorbitor: Omar, un pas înainte, gata.

782
00:35:21,970 --> 00:35:22,860
Jumătate stânga este sortat.

783
00:35:22,860 --> 00:35:23,330
Și cum te cheamă?

784
00:35:23,330 --> 00:35:23,820
>> Audiența: Chris.

785
00:35:23,820 --> 00:35:25,620
>> Vorbitor: Chris, ia un pas
înainte, vă sunt acum clasificate în funcție.

786
00:35:25,620 --> 00:35:27,010
Care este pasul cheie acum?

787
00:35:27,010 --> 00:35:27,510
Merge.

788
00:35:27,510 --> 00:35:30,509
Deci, una este de gând să fuzioneze în loc
aici, dacă ai putea lua un pas înapoi,

789
00:35:30,509 --> 00:35:32,930
și trei se va
ia un pas înapoi, merge.

790
00:35:32,930 --> 00:35:38,080
Astfel, jumătatea stângă a
jumătate chiar, este acum clasificate în funcție.

791
00:35:38,080 --> 00:35:41,747
Sincer, acest algoritm se simte ca și cum am
se pierde mult mai mult timp decât înainte,

792
00:35:41,747 --> 00:35:44,830
dar dacă am făcut acest lucru în timp real, vom
vedea ce takeaways va fi.

793
00:35:44,830 --> 00:35:47,970
Acum, iată-mă, chiar
jumătate din jumătatea din dreapta,

794
00:35:47,970 --> 00:35:50,170
lasă-mă să merg mai departe și sorta jumătatea stângă.

795
00:35:50,170 --> 00:35:51,482
Un pas înainte, care e numele tău?

796
00:35:51,482 --> 00:35:52,190
Audiența: Ramsey.

797
00:35:52,190 --> 00:35:53,210
SPEAKER: Ramsey este acum clasificate în funcție.

798
00:35:53,210 --> 00:35:53,570
Care e numele tău?

799
00:35:53,570 --> 00:35:54,200
>> Audiența: Marina.

800
00:35:54,200 --> 00:35:57,033
>> SPEAKER: Marina este acum clasificate în funcție de
bine, dacă luați un pas înainte.

801
00:35:57,033 --> 00:36:00,690
Key pas aici este acum fuzioneze, eu sunt
O să smulgă de la cei doi liste,

802
00:36:00,690 --> 00:36:01,720
la stânga și la dreapta.

803
00:36:01,720 --> 00:36:05,150
Cinci este de gând să vină în primul rând,
și șapte va veni următorul.

804
00:36:05,150 --> 00:36:06,410
Și din nou, aceasta este în mod deliberat.

805
00:36:06,410 --> 00:36:08,535
Faptul că o duc
pași înainte și înapoi

806
00:36:08,535 --> 00:36:12,997
are menirea de a reprezenta că nu putem
face acest algoritm în loc de ușor

807
00:36:12,997 --> 00:36:15,830
ca bule fel, și selecție de sortare,
și inserare fel în care ne-am

808
00:36:15,830 --> 00:36:16,960
păstrat schimbarea oameni.

809
00:36:16,960 --> 00:36:19,940
Am literalmente nevoie de un fel
de hârtie zero în care

810
00:36:19,940 --> 00:36:21,827
pentru a pune acești oameni
în timp ce eu fac fuziunea,

811
00:36:21,827 --> 00:36:23,410
și apoi le pot pune la loc.

812
00:36:23,410 --> 00:36:27,260
Și asta e cheia pentru că eu sunt, folosind un
noi resurse, spatiu, nu doar timp.

813
00:36:27,260 --> 00:36:28,270
>> OK, asta e uimitor.

814
00:36:28,270 --> 00:36:32,050
Jumătate stânga este sortat, pe jumătate dreptate este
sortat, acum că cheia fuzionează pas.

815
00:36:32,050 --> 00:36:33,450
Cum am de gând să fuzioneze asta?

816
00:36:33,450 --> 00:36:35,470
Deci, dacă voi urma mea
mâna stângă și mâna dreaptă,

817
00:36:35,470 --> 00:36:38,930
Am de gând să arate mâna stângă
la jumatatea stanga, dreapta mea

818
00:36:38,930 --> 00:36:42,680
la jumătatea din dreapta, iar acum trebuie să
decidă pas cu pas care să fuzioneze în.

819
00:36:42,680 --> 00:36:44,650
Cine evident este pe primul loc?

820
00:36:44,650 --> 00:36:45,150
Numărul unu.

821
00:36:45,150 --> 00:36:47,327
Deci, vino aici,
aici e pad nostru zero.

822
00:36:47,327 --> 00:36:49,910
Deci, acum numărul unu, și notificare
ce voi face cu mâna dreaptă,

823
00:36:49,910 --> 00:36:54,152
Am de gând să se mute o mâna mea dreaptă
pas pe la punctul numărul trei,

824
00:36:54,152 --> 00:36:55,860
iar acum trebuie să facă
aceeași decizie.

825
00:36:55,860 --> 00:36:58,387
Și, de fapt sta chiar în
fata de Luca aici dacă ai putea,

826
00:36:58,387 --> 00:36:59,720
pentru că aceasta este pad noastră zero.

827
00:36:59,720 --> 00:37:00,610
Deci, cine urmeaza?

828
00:37:00,610 --> 00:37:05,000
Avem Luca cu numărul doi
sau Chris cu numărul trei.

829
00:37:05,000 --> 00:37:07,460
Evident Luca, număr
doi, așa că ai venit aici.

830
00:37:07,460 --> 00:37:11,270
>> Dar mâna stângă este acum de gând să
care crește de la punctul de la Darren,

831
00:37:11,270 --> 00:37:15,160
și aici e cheia ia cu
fuzionează, am de gând să face asta,

832
00:37:15,160 --> 00:37:17,340
evident, dacă aveți un fel
a urma logica.

833
00:37:17,340 --> 00:37:19,670
Dar mâinile mele nu sunt niciodată
merge înapoi,

834
00:37:19,670 --> 00:37:23,861
ceea ce înseamnă că sunt numai vreodată în mișcare a
a plecat cu procesul meu de fuziune,

835
00:37:23,861 --> 00:37:26,360
și care va fi cheia pentru
Analiza noastră într-o clipă.

836
00:37:26,360 --> 00:37:27,859
>> Deci, acum, să terminăm asta rapid.

837
00:37:27,859 --> 00:37:31,650
Deci, trei urmeaza,
apoi patru urmeaza,

838
00:37:31,650 --> 00:37:38,750
și acum cinci urmeaza, apoi șase,
și șapte, și apoi în cele din urmă opt.

839
00:37:38,750 --> 00:37:42,960
Se simte ca cel mai lent algoritmul
încă, dar nu dacă suntem de fapt

840
00:37:42,960 --> 00:37:45,510
rulați-l în același fel
de viteza de ceas, ca să

841
00:37:45,510 --> 00:37:48,106
vorbi, cu aceeași
ticăie ceasul ca înainte.

842
00:37:48,106 --> 00:37:48,605
De ce?

843
00:37:48,605 --> 00:37:51,100
Ei bine, haideți să aruncăm o
uita-te la rezultatul final.

844
00:37:51,100 --> 00:37:56,990
>> Să ne întoarcem aici, lasă-mă să
trage o demonstrație de vedere vizual

845
00:37:56,990 --> 00:37:59,030
din ceea ce am făcut.

846
00:37:59,030 --> 00:38:06,110
Zoom-ul aici, pe acest
Pagina de aici, spune Firefox

847
00:38:06,110 --> 00:38:08,200
care ne-o dorim să stau la coadă
în această casetă, să

848
00:38:08,200 --> 00:38:11,260
spune balon fel, cu care
acum suntem bine familiarizați,

849
00:38:11,260 --> 00:38:14,130
fel de selecție, care este un alt
destul de un simplu,

850
00:38:14,130 --> 00:38:18,250
iar acum astăzi tip merge, care
va fi sfârșit nostru culminant.

851
00:38:18,250 --> 00:38:21,530
Motivul pentru care a durat atât de mult mai mult timp
aici cu oamenii și mi-verbal este,

852
00:38:21,530 --> 00:38:23,480
evident, am explicat fiecare pas.

853
00:38:23,480 --> 00:38:26,920
Dar dacă pur și simplu executați acest lucru, mult
ca am facut un fel de bule și selecție

854
00:38:26,920 --> 00:38:30,890
fel nu numai vizual, ceas
cat de mult mai eficient

855
00:38:30,890 --> 00:38:33,330
această pârghie de
divizare și cucerirea

856
00:38:33,330 --> 00:38:39,150
poate fi aplicat pe un set de date care este
nu chiar dimensiune opt, dar chiar mai mult,

857
00:38:39,150 --> 00:38:39,970
mult mai mare.

858
00:38:39,970 --> 00:38:44,585
Eu vă dau fuzioneze fel, partea de
laterale cu aceste alți algoritmi.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Acest lucru se întâmplă pentru a obține dureros
repede, și se încheie

861
00:38:58,530 --> 00:39:00,890
nu este deosebit de culminant,
ei doar ajung sortate.

862
00:39:00,890 --> 00:39:05,280
Dar cheia ia este că
Uite cât de mult mai repede fuzioneze fel

863
00:39:05,280 --> 00:39:08,110
a fost, dacă nu crezi că sunt
doar un fel de joc cu tine.

864
00:39:08,110 --> 00:39:13,100
Dacă vom face acest lucru o dată finală,
hai sa reincarci aceasta, să mergem înapoi

865
00:39:13,100 --> 00:39:14,960
și alege bule de sortare,
și doar pentru lovituri,

866
00:39:14,960 --> 00:39:17,330
Să alegem inserare
fel, doar pentru o bună măsură.

867
00:39:17,330 --> 00:39:20,020
Și de această dată, din nou, să
alegeți Combinare fel și să

868
00:39:20,020 --> 00:39:21,595
rula de fapt acestea cot la cot.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> Și nu este vorba, de fapt, o întâmplare.

871
00:39:26,930 --> 00:39:31,140
Ce am făcut în mod eficient este de am
împărțit intrare meu la jumătate, din nou,

872
00:39:31,140 --> 00:39:32,240
și din nou, și din nou.

873
00:39:32,240 --> 00:39:35,590
Și nu e doar atât de multe ori puteți
împărți dvs. de intrare în jumătăți, stânga

874
00:39:35,590 --> 00:39:36,240
și drept.

875
00:39:36,240 --> 00:39:39,425
Care este formula pe care o tot văd
care descrie împărțirea în jumătate

876
00:39:39,425 --> 00:39:41,050
din nou, și din nou, și din nou, și din nou?

877
00:39:41,050 --> 00:39:41,890
>> Audiența: log n.

878
00:39:41,890 --> 00:39:42,760
>> SPEAKER: log n.

879
00:39:42,760 --> 00:39:46,300
Dar există un alt pas cheie,
acest algoritm nu este log n pasi.

880
00:39:46,300 --> 00:39:48,992
În cazul în care au fost conectați doar n pași,
am fi în aceeași problemă

881
00:39:48,992 --> 00:39:51,200
ca și mai înainte, unde nu putem fi
că totul e sortate.

882
00:39:51,200 --> 00:39:54,480
Trebuie sa te uiti minim la n elemente
pentru a fi sigur că n elemente sunt clasificate în funcție,

883
00:39:54,480 --> 00:39:55,950
altfel e un salt de credință.

884
00:39:55,950 --> 00:39:59,810
>> Deci, este jurnalul minim n pași, dar
ce despre acest pas cheie fuziune

885
00:39:59,810 --> 00:40:04,370
unde am fuzionat jumătate stâng și drept
jumătate și a mers pe scena?

886
00:40:04,370 --> 00:40:06,980
Câți pași este că, pentru a fuziona?

887
00:40:06,980 --> 00:40:10,150
Este n, dar n-am făcut doar
fuziona timpul final.

888
00:40:10,150 --> 00:40:15,089
Pe fiecare dintre aceste apeluri imbricate, pe fiecare
din aceste fuziuni imbricate, eu încă sortate.

889
00:40:15,089 --> 00:40:18,380
Am fuzionat aceste doi tipi, atunci aceste două
baieti, atunci aceste doi tipi și așa mai departe.

890
00:40:18,380 --> 00:40:19,955
>> Așa că m-am fuzionează din nou, și din nou.

891
00:40:19,955 --> 00:40:20,580
De câte ori?

892
00:40:20,580 --> 00:40:23,510
Deci, de fiecare dată am împărțit
Lista în jumătate, am făcut o fuziune.

893
00:40:23,510 --> 00:40:25,460
Împărțiți lista de la jumătate, face o fuziune.

894
00:40:25,460 --> 00:40:28,570
Deci, dacă împărțirea pe lista
se poate face log n ori,

895
00:40:28,570 --> 00:40:33,880
și fuziunea în cele din urmă ia n
trepte, ceea ce ar putea fi acum de sus

896
00:40:33,880 --> 00:40:37,000
legat de funcționare
timp de algoritmul nostru?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> Și într-adevăr, asta e ceea ce
am realizat aici.

899
00:40:40,560 --> 00:40:44,650
Deci, simt că voi vedea vizual atunci când
aceste trei lucruri alerga cot la cot

900
00:40:44,650 --> 00:40:47,930
este n pătrat împotriva n
pătrat împotriva n log n.

901
00:40:47,930 --> 00:40:51,010
Care fundamental vom vedea,
nu numai astăzi, ci în viitor,

902
00:40:51,010 --> 00:40:52,760
este mult, mult mai rapid.

903
00:40:52,760 --> 00:40:56,010
O rundă de aplauze pentru aceste baieti,
Eu îi va răsplăti cu bile de stres.

904
00:40:56,010 --> 00:41:00,260
Să suspenda aici astăzi, și
va vom vedea pe luni.

905
00:41:00,260 --> 00:41:02,255