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

2
00:00:00,488 --> 00:00:10,800
>> [Reproducció de música]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Molt bé.

4
00:00:13,500 --> 00:00:14,670
Bé, benvinguts de nou.

5
00:00:14,670 --> 00:00:18,120
Així que aquesta és la Setmana 4, el començament
dels mateixos, ja.

6
00:00:18,120 --> 00:00:21,320
I et recordo que la setmana passada, hem posat
codificar a un costat per una mica

7
00:00:21,320 --> 00:00:24,240
i vam començar a parlar una mica més
d'alt nivell, sobre coses com

8
00:00:24,240 --> 00:00:28,130
recerca i ordenació, que encara
les idees són una mica simples,

9
00:00:28,130 --> 00:00:31,840
representant d'una classe de problemes
vostè començarà a resoldre tot

10
00:00:31,840 --> 00:00:34,820
a mesura que comences a pensar en definitiva
projectes i solucions interessants que

11
00:00:34,820 --> 00:00:36,760
podria tenir a problemes del món real.

12
00:00:36,760 --> 00:00:39,490
Ara mena de bombolla va ser un dels més senzills
aquest tipus d'algorismes, i

13
00:00:39,490 --> 00:00:42,900
treballat per tenir aquests petits nombres
en una llista o en un tipus gamma de

14
00:00:42,900 --> 00:00:46,530
bombolla del seu camí al cim, i el
grans nombres de moure el seu camí a

15
00:00:46,530 --> 00:00:47,930
al final de la llista.

16
00:00:47,930 --> 00:00:50,650
>> I recordem que vam poder visualitzar
mena de bombolla una mica

17
00:00:50,650 --> 00:00:52,310
alguna cosa com això.

18
00:00:52,310 --> 00:00:53,640
Així que permetin-me anar endavant i feu clic a Inicia.

19
00:00:53,640 --> 00:00:55,350
He preseleccionat mena de bombolla.

20
00:00:55,350 --> 00:00:58,920
I si vostè recorda que el blau més alt
línies representen nombres grans, petites

21
00:00:58,920 --> 00:01:03,300
línies blaves representen els nombres petits, com
passem per això una i altra vegada i

22
00:01:03,300 --> 00:01:07,680
de nou, la comparació de dos bars al costat de cadascun
una altra de color vermell, que canviarem la

23
00:01:07,680 --> 00:01:11,010
més gran i la més petita, si
que estan fora d'ordre.

24
00:01:11,010 --> 00:01:14,150
>> Així que això va a seguir i seguir i seguir
encès, i vostè veurà que la major

25
00:01:14,150 --> 00:01:16,700
elements estan fent el seu camí a la
dreta, i els elements més petits són

26
00:01:16,700 --> 00:01:17,900
fer el seu camí a l'esquerra.

27
00:01:17,900 --> 00:01:21,380
Però comencem a quantificar
l'eficiència, la

28
00:01:21,380 --> 00:01:22,970
qualitat d'aquest algorisme.

29
00:01:22,970 --> 00:01:25,200
I vam dir que en el pitjor
cas, aquest algorisme es

30
00:01:25,200 --> 00:01:27,940
més o menys la quantitat de passos?

31
00:01:27,940 --> 00:01:28,980
>> Per tant n quadrat.

32
00:01:28,980 --> 00:01:30,402
¿I què era n?

33
00:01:30,402 --> 00:01:31,650
>> AUDIÈNCIA: Nombre d'elements.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Així va ser la n
nombre d'elements.

35
00:01:32,790 --> 00:01:33,730
Així que anem a fer això amb freqüència.

36
00:01:33,730 --> 00:01:36,650
Cada vegada que volem parlar sobre la mida
d'un problema o la mida d'un

37
00:01:36,650 --> 00:01:39,140
d'entrada, o la quantitat de temps que triga
per produir una sortida, només haurem de

38
00:01:39,140 --> 00:01:41,610
generalitzat el
l'entrada és com n.

39
00:01:41,610 --> 00:01:45,970
Així que de nou en la setmana 0, el nombre de pàgines
a la guia telefònica era n.

40
00:01:45,970 --> 00:01:47,550
El nombre d'estudiants
A l'habitació hi havia n.

41
00:01:47,550 --> 00:01:49,630
Així que aquí, també, estem seguint
aquest patró.

42
00:01:49,630 --> 00:01:52,800
>> Ara n quadrat no és particularment
ràpid, pel que tractem de fer millor.

43
00:01:52,800 --> 00:01:55,970
I així vam veure un parell de
altres algoritmes, entre els quals

44
00:01:55,970 --> 00:01:57,690
eren ordenació per selecció.

45
00:01:57,690 --> 00:01:59,180
Així que va ser una mena de selecció
una mica diferent.

46
00:01:59,180 --> 00:02:03,130
Gairebé era més simple, m'atreveixo a dir,
pel que vaig començar al principi de la

47
00:02:03,130 --> 00:02:06,740
Llista dels nostres voluntaris i jo de nou
i una i altra vegada va ser a través de

48
00:02:06,740 --> 00:02:10,060
la llista, arrencar-se el més petit
element alhora i el va deixar o

49
00:02:10,060 --> 00:02:13,040
ella al principi de la llista.

50
00:02:13,040 --> 00:02:16,410
>> Però això, també, un cop que vam començar a pensar
a través de les matemàtiques i més gran

51
00:02:16,410 --> 00:02:19,860
imatge, va pensar en quantes vegades
Jo anava d'anada i tornada i tornada

52
00:02:19,860 --> 00:02:24,090
endavant i cap enrere, vam dir en el pitjor dels casos,
ordenació per selecció, també, va ser que?

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

54
00:02:24,960 --> 00:02:27,490
Ara, en el món real, podria
en realitat ser marginalment més ràpid.

55
00:02:27,490 --> 00:02:30,620
Perquè de nou, jo no he de seguir
fer marxa enrere una vegada que havia ordenat la

56
00:02:30,620 --> 00:02:31,880
elements més petits.

57
00:02:31,880 --> 00:02:35,090
Però si pensem en gran n, i
si una espècie de fer la matemàtica com

58
00:02:35,090 --> 00:02:39,170
Ho vaig fer en el tauler, amb el núm quadrat
una mica menys, tota la resta

59
00:02:39,170 --> 00:02:41,850
a més de la núm quadrat, un cop n
es posa molt gran, no

60
00:02:41,850 --> 00:02:42,850
Realment importa tant.

61
00:02:42,850 --> 00:02:45,470
Així com els informàtics, que tipus de
fer els ulls grossos als més petits

62
00:02:45,470 --> 00:02:49,220
factors i se centren només en el factor d'
una expressió que es va a fer

63
00:02:49,220 --> 00:02:50,330
la diferència més gran.

64
00:02:50,330 --> 00:02:52,840
>> Bé, finalment, busquem
en l'ordenació per inserció.

65
00:02:52,840 --> 00:02:56,620
I aquesta va ser similar en esperit, però
en lloc d'anar a través de manera iterativa i

66
00:02:56,620 --> 00:03:01,250
seleccionar l'element més petit d'un en un
temps, lloc va prendre la mà que em

67
00:03:01,250 --> 00:03:04,070
va ser tractat, i vaig decidir, tot
bé, és el teu lloc.

68
00:03:04,070 --> 00:03:06,160
Després vaig passar a la següent element
i va decidir que ell o

69
00:03:06,160 --> 00:03:07,470
pertanyia aquí.

70
00:03:07,470 --> 00:03:08,810
I després em vaig mudar i segueix.

71
00:03:08,810 --> 00:03:11,780
I potser, en el camí,
canviar aquests nois per tal de

72
00:03:11,780 --> 00:03:13,030
fer espai per a ells.

73
00:03:13,030 --> 00:03:16,880
Així que va ser una mena de reversió mentals
d'ordenació per selecció que

74
00:03:16,880 --> 00:03:18,630
anomenada ordenació per inserció.

75
00:03:18,630 --> 00:03:20,810
>> Així que aquests temes que es produeixi
en el món real.

76
00:03:20,810 --> 00:03:23,640
Fa tot just uns anys, quan un determinat
senador va ser candidat a la presidència,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, en el moment en el director general d'
Google, en realitat va tenir l'oportunitat

78
00:03:27,160 --> 00:03:28,040
per entrevistar-lo.

79
00:03:28,040 --> 00:03:32,010
I pensem que seria bona idea compartir aquesta YouTube
tallar per a vostè aquí, si poguéssim pujar

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

81
00:03:32,950 --> 00:03:39,360
>> [REPRODUIR VIDEO]

82
00:03:39,360 --> 00:03:44,620
>> -Ara, el senador, ets aquí a Google,
i m'agrada pensar en la presidència

83
00:03:44,620 --> 00:03:46,042
com una entrevista de treball.

84
00:03:46,042 --> 00:03:47,770
>> [El]

85
00:03:47,770 --> 00:03:50,800
>> -Ara que és difícil d'aconseguir
un treball com a president.

86
00:03:50,800 --> 00:03:52,480
I vostè va a través d'
els rigors ara.

87
00:03:52,480 --> 00:03:54,330
També és difícil aconseguir una feina a Google.

88
00:03:54,330 --> 00:03:59,610
Tenim preguntes i li demanem
les nostres preguntes dels candidats.

89
00:03:59,610 --> 00:04:02,250
I aquesta és de Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [El]

91
00:04:05,325 --> 00:04:06,400
-Vostès pensen que estic fent broma?

92
00:04:06,400 --> 00:04:08,750
Sou aquí mateix.

93
00:04:08,750 --> 00:04:12,110
Quina és la forma més eficient de
ordenar un milió d'enters de pacotilla?

94
00:04:12,110 --> 00:04:15,810
>> [El]

95
00:04:15,810 --> 00:04:18,260
>> -Bé, uh -

96
00:04:18,260 --> 00:04:19,029
>> -Ho sento.

97
00:04:19,029 --> 00:04:19,745
Potser hauria -

98
00:04:19,745 --> 00:04:21,000
>> -No, no, no, no, no.

99
00:04:21,000 --> 00:04:21,470
>> -Això no és un -

100
00:04:21,470 --> 00:04:22,185
D'acord.

101
00:04:22,185 --> 00:04:25,328
>> -Crec que l'ordenament de bombolla seria
ser el camí equivocat.

102
00:04:25,328 --> 00:04:26,792
>> [El]

103
00:04:26,792 --> 00:04:28,510
>> [Vítores i aplaudiments]

104
00:04:28,510 --> 00:04:31,211
>> -Anem, que li va dir això?

105
00:04:31,211 --> 00:04:32,155
D'acord.

106
00:04:32,155 --> 00:04:33,350
>> [FI REPRODUCCIÓ DE VÍDEO]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Així que aquí ho tenen.

108
00:04:35,070 --> 00:04:39,600
Així que vam començar a quantificar aquestes corrent
vegades, per dir-ho, amb una mica

109
00:04:39,600 --> 00:04:43,480
anomenat notació asimptòtica, que és
només es refereix a la nostra espècie de gir

110
00:04:43,480 --> 00:04:47,420
els ulls grossos als factors més petits i
només mirar el temps d'execució,

111
00:04:47,420 --> 00:04:51,250
el rendiment d'aquests algoritmes,
que n es fa molt gran amb el temps.

112
00:04:51,250 --> 00:04:55,110
I així hem introduït gran O. i Big O
representava alguna cosa que pensem

113
00:04:55,110 --> 00:04:57,000
d'com un límit superior.

114
00:04:57,000 --> 00:04:59,570
I, de fet, Barry, podem baixar
que el micròfon una mica?

115
00:04:59,570 --> 00:05:01,040
>> Pensem en això és un límit superior.

116
00:05:01,040 --> 00:05:04,710
Així gran O de n mitjans quadrat que en
el pitjor dels casos, una mena

117
00:05:04,710 --> 00:05:07,780
ordenació per selecció prendria
n passos quadrat.

118
00:05:07,780 --> 00:05:10,310
O alguna cosa així com l'ordenació per inserció
faria n passos quadrat.

119
00:05:10,310 --> 00:05:15,150
Ara per a alguna cosa com la inserció
espècie, que va ser el pitjor dels casos?

120
00:05:15,150 --> 00:05:18,200
Donat un vector que, quina és la pitjor
possible escenari que podria trobar

121
00:05:18,200 --> 00:05:20,650
fet front amb?

122
00:05:20,650 --> 00:05:21,860
>> És totalment al revés, no?

123
00:05:21,860 --> 00:05:24,530
Perquè si és totalment al revés,
vostè ha de fer un munt de treball.

124
00:05:24,530 --> 00:05:26,420
Perquè si vostè és completament al revés,
vostè va a trobar el

125
00:05:26,420 --> 00:05:28,840
element més important aquí, tot i que
pertany allà.

126
00:05:28,840 --> 00:05:31,140
Així que vas a dir, d'acord, en
aquest moment en el temps, que és d'aquí,

127
00:05:31,140 --> 00:05:32,310
així que el deixa sol.

128
00:05:32,310 --> 00:05:35,425
>> Llavors t'adones, oh, maleïda sigui, he de
moure aquest element una mica més petit que

129
00:05:35,425 --> 00:05:36,470
l'esquerra de vostè.

130
00:05:36,470 --> 00:05:38,770
Llavors he de fer-ho de nou
i una i altra vegada.

131
00:05:38,770 --> 00:05:41,410
I si caminava d'anada i tornada, que
que classe de sensació l'exercici de

132
00:05:41,410 --> 00:05:45,540
que l'algorisme, perquè constantment estic
arrossegant a tots els altres en la

133
00:05:45,540 --> 00:05:46,510
matriu per fer espai per a això.

134
00:05:46,510 --> 00:05:47,750
Així que aquest és el pitjor dels casos.

135
00:05:47,750 --> 00:05:48,570
>> Per contra -

136
00:05:48,570 --> 00:05:50,320
i això va ser un cliffhanger última vegada -

137
00:05:50,320 --> 00:05:54,065
vam dir que l'ordenació per inserció
era un omega de què?

138
00:05:54,065 --> 00:05:57,530
Quin és el millor dels casos funcionament
moment de l'ordenació per inserció?

139
00:05:57,530 --> 00:05:58,520
Així que en realitat n.

140
00:05:58,520 --> 00:06:00,980
Aquest va ser l'espai en blanc que deixem
al tauler de l'última vegada.

141
00:06:00,980 --> 00:06:03,160
>> I és l'omega de n perquè ¿per què?

142
00:06:03,160 --> 00:06:06,630
Doncs bé, en el millor dels casos, el que és
ordenació per inserció és entregat?

143
00:06:06,630 --> 00:06:09,830
Bé, una llista que molt ordenada
Ja, un mínim de treball que fer.

144
00:06:09,830 --> 00:06:12,460
Però el que és bo d'ordenació per inserció
és que, ja que comença aquí i

145
00:06:12,460 --> 00:06:15,340
decideix, oh, ets l'
un, pertanyen aquí.

146
00:06:15,340 --> 00:06:16,970
Oh, quina bona fortuna.

147
00:06:16,970 --> 00:06:17,740
>> Vostè és el número dos.

148
00:06:17,740 --> 00:06:19,030
També pertanyo a aquest lloc.

149
00:06:19,030 --> 00:06:21,010
Número tres, millor encara,
pertanys aquí.

150
00:06:21,010 --> 00:06:25,210
Tan aviat com s'arriba al final de la
pseudocodi llista, per la inserció d'una espècie

151
00:06:25,210 --> 00:06:28,010
que vam entrar per verbalment
última vegada, ja està fet.

152
00:06:28,010 --> 00:06:32,790
Però ordenació per selecció, per contra,
vaig seguir fent què?

153
00:06:32,790 --> 00:06:35,260
>> Va seguir el seu camí a través de la llista
una i altra vegada i una altra.

154
00:06:35,260 --> 00:06:39,160
A causa de que la idea clau que només havia
una vegada que has mirat tot el camí a la

155
00:06:39,160 --> 00:06:42,500
final de la llista pot estar segur
que l'element seleccionat es

156
00:06:42,500 --> 00:06:45,560
de fet, l'element actualment més petit.

157
00:06:45,560 --> 00:06:48,920
Així que aquests models diferents finals mentals
cedint alguna cosa al món real molt

158
00:06:48,920 --> 00:06:53,130
diferències per a nosaltres, així com els
diferències teòriques asimptòtiques.

159
00:06:53,130 --> 00:06:56,910
>> Així que per resumir, llavors, gran O de n
quadrat, hem vist uns quants,

160
00:06:56,910 --> 00:06:58,350
algoritmes fins ara.

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

162
00:06:59,580 --> 00:07:02,870
Què és un algoritme que podria
dir que és gran O de n?

163
00:07:02,870 --> 00:07:06,930
En el pitjor dels casos, es necessita
una sèrie lineal de passos.

164
00:07:06,930 --> 00:07:07,810
>> Acceptar, cerca lineal.

165
00:07:07,810 --> 00:07:10,470
I en el pitjor dels casos, on és el
element que està buscant quan

166
00:07:10,470 --> 00:07:12,950
l'aplicació de cerca lineal?

167
00:07:12,950 --> 00:07:14,680
>> Acceptar, en el pitjor dels casos,
que ni tan sols existeix.

168
00:07:14,680 --> 00:07:17,000
O en el segon pitjor dels casos, és
tot el camí a l'extrem, que és

169
00:07:17,000 --> 00:07:18,880
de més o menys una diferència d'un sol pas.

170
00:07:18,880 --> 00:07:21,180
Així que al final del dia,
podem dir que és lineal.

171
00:07:21,180 --> 00:07:23,910
Big O de n seria recerca lineal,
causa que en el pitjor dels casos, la

172
00:07:23,910 --> 00:07:26,610
element ni tan sols existeix o és
fins arribar al final.

173
00:07:26,610 --> 00:07:29,370
>> Bé, gran O de registre de n.

174
00:07:29,370 --> 00:07:32,760
No parlem en detall sobre
això, però hem vist això abans.

175
00:07:32,760 --> 00:07:36,840
El que s'executa en l'anomenada logarítmica
temps, en el pitjor dels casos?

176
00:07:36,840 --> 00:07:38,500
>> Sí, cerca de manera binari.

177
00:07:38,500 --> 00:07:42,930
I recerca binària en el pitjor dels casos
podria tenir l'element en algun lloc

178
00:07:42,930 --> 00:07:45,640
el mitjà, o en algun lloc
en cas de fallida.

179
00:07:45,640 --> 00:07:48,040
Però només es troba un cop
dividir la llista en dues, en

180
00:07:48,040 --> 00:07:48,940
un mitjà, en un medi, en un mitjà.

181
00:07:48,940 --> 00:07:50,200
I voilà, aquí està.

182
00:07:50,200 --> 00:07:52,500
O, de nou, pitjor dels casos,
que ni tan sols existeix.

183
00:07:52,500 --> 00:07:56,770
Però vostè no sap que no hi és
fins que arribi a aquest tipus de passat

184
00:07:56,770 --> 00:08:00,470
baix majoria dels elements de reduir a la meitat
i reduir a la meitat, i reduir a la meitat.

185
00:08:00,470 --> 00:08:01,400
>> Big O d'1.

186
00:08:01,400 --> 00:08:03,540
Així que vam poder gran O de 2, O gran de 3.

187
00:08:03,540 --> 00:08:06,260
Cada vegada que vols és simplement un nombre constant,
que només una mena de just simplificar

188
00:08:06,260 --> 00:08:07,280
que, com a gran O d'1.

189
00:08:07,280 --> 00:08:10,440
Encara que si realista, pren
2 o fins i tot 100 passos, si és un

190
00:08:10,440 --> 00:08:13,680
nombre constant de passos,
ens limitem a dir gran O d'1.

191
00:08:13,680 --> 00:08:15,930
Què és un algoritme que és
en gran O d'1?

192
00:08:15,930 --> 00:08:18,350
>> AUDIÈNCIA: Trobar la longitud
d'una variable.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Trobar el
longitud d'una variable?

194
00:08:21,090 --> 00:08:23,870
>> AUDIÈNCIA: No, la longitud
si ja està solucionat.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Good.

196
00:08:24,160 --> 00:08:27,850
Acceptar, de manera que trobar la longitud d'una mica
si la longitud d'alguna cosa que, igual

197
00:08:27,850 --> 00:08:30,020
una matriu, s'emmagatzema en una variable.

198
00:08:30,020 --> 00:08:33,380
Com que només pot llegir la variable,
o imprimir la variable o

199
00:08:33,380 --> 00:08:34,960
només en general accedir a aquesta variable.

200
00:08:34,960 --> 00:08:37,299
I voila, que porta temps constant.

201
00:08:37,299 --> 00:08:38,909
>> Per contra, pensar de nou a l'altura.

202
00:08:38,909 --> 00:08:42,460
Penseu en la primera setmana de C,
cridar simplement printf i impressió

203
00:08:42,460 --> 00:08:46,240
alguna cosa a la pantalla és, sens dubte
constant de temps, ja que només es necessita

204
00:08:46,240 --> 00:08:50,880
un nombre de cicles de CPU per mostrar
que el text a la pantalla.

205
00:08:50,880 --> 00:08:52,720
O esperar - o sí?

206
00:08:52,720 --> 00:08:56,430
Com si no podríem modelar el
exercici de printf?

207
00:08:56,430 --> 00:09:00,420
Algú voldria estar en desacord, que
potser no és el temps realment constant?

208
00:09:00,420 --> 00:09:03,600
En quin sentit podria printf s'està executant
temps, en realitat la impressió d'una cadena en

209
00:09:03,600 --> 00:09:05,580
la pantalla, sigui alguna cosa
que no sigui constant.

210
00:09:05,580 --> 00:09:07,860
>> AUDIÈNCIA: [inaudible].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Si.

212
00:09:08,230 --> 00:09:09,300
Així que depèn de la nostra perspectiva.

213
00:09:09,300 --> 00:09:13,390
Si realment pensem en l'entrada
printf com la cadena, i

214
00:09:13,390 --> 00:09:16,380
per tant, es mesura la grandària d'aquest
d'entrada per la seva longitud - així que anem a trucar

215
00:09:16,380 --> 00:09:17,780
que la longitud n, així -

216
00:09:17,780 --> 00:09:21,990
sens dubte, printf és propi Big O de n
perquè va a portar n passos

217
00:09:21,990 --> 00:09:24,750
per imprimir cadascun dels n
personatges, molt probablement.

218
00:09:24,750 --> 00:09:27,730
Almenys en la mesura que assumim
que potser es tracta d'utilitzar un bucle for

219
00:09:27,730 --> 00:09:28,560
sota de la caputxa.

220
00:09:28,560 --> 00:09:30,860
>> Però hauríem de mirar aquest
codi per entendre-ho millor.

221
00:09:30,860 --> 00:09:33,650
I, de fet, un cop que vostès comencin a
l'anàlisi dels seus propis algoritmes, vostè

222
00:09:33,650 --> 00:09:34,900
literalment fer precisament això.

223
00:09:34,900 --> 00:09:37,765
Una espècie de globus ocular seu codi i pensar
Quant a - bé, jo tinc aquest bucle

224
00:09:37,765 --> 00:09:41,870
aquí o que tenen una combinació de bucles niats aquí,
que farà les coses n n vegades,

225
00:09:41,870 --> 00:09:46,050
i es pot ordenar de la raó a la seva manera
a través del codi, encara que és

226
00:09:46,050 --> 00:09:47,980
pseudocodi i no el codi real.

227
00:09:47,980 --> 00:09:49,730
>> Què passa amb l'omega de n al quadrat?

228
00:09:49,730 --> 00:09:53,582
El que era un algoritme que en el millor
cas, encara va trigar n passos quadrat?

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

230
00:09:54,014 --> 00:09:54,880
>> AUDIÈNCIA: [inaudible].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Així ordenació per selecció.

232
00:09:55,900 --> 00:09:59,150
Perquè en aquest problema realment reduït
al fet que una vegada més, no ho sé

233
00:09:59,150 --> 00:10:02,600
He trobat el corrent més petita fins
He comprovat tots els elements maleït.

234
00:10:02,600 --> 00:10:08,050
Així omega de, per exemple, n,
Acaba d'arribar amb un.

235
00:10:08,050 --> 00:10:09,300
L'ordenació per inserció.

236
00:10:09,300 --> 00:10:12,370
Si la llista passa a ser ordenats
Ja, en el millor dels casos només tenim

237
00:10:12,370 --> 00:10:15,090
per fer un passi a través d'ell,
moment en què estem segurs.

238
00:10:15,090 --> 00:10:17,890
I a continuació, que es podria dir
ser lineal, sens dubte.

239
00:10:17,890 --> 00:10:20,570
>> Què passa amb l'omega d'1?

240
00:10:20,570 --> 00:10:23,790
Quin és, en el millor dels casos, pot trigar
un nombre constant de passos?

241
00:10:23,790 --> 00:10:27,220
Recerca de Llavors lineal, si vostè acaba de tenir sort
i l'element que està buscant

242
00:10:27,220 --> 00:10:31,000
és just al principi de la llista,
si això és on vostè està començant el seu

243
00:10:31,000 --> 00:10:33,070
lineals de recorregut de la llista.

244
00:10:33,070 --> 00:10:35,180
>> I aquest és el cas d'un
nombre de coses.

245
00:10:35,180 --> 00:10:37,660
Per exemple, fins i tot binari
recerca és l'omega d'1.

246
00:10:37,660 --> 00:10:40,310
Perquè el que si vostè aconsegueix realment maleït
sort i just-DAB al centre de

247
00:10:40,310 --> 00:10:42,950
la matriu és el nombre
que està buscant?

248
00:10:42,950 --> 00:10:45,730
Així que vostè pot tenir sort allà, també.

249
00:10:45,730 --> 00:10:49,190
>> Aquest, finalment, l'omega de n log n.

250
00:10:49,190 --> 00:10:52,573
Llavors n log n, no ho vam fer realment
parlar encara, però -

251
00:10:52,573 --> 00:10:53,300
>> AUDIÈNCIA: Combinar tipus?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: Merge espècie.

253
00:10:53,960 --> 00:10:56,920
Aquest va ser el drama de suspens de l'última vegada,
on ens vam proposar, i mostrem

254
00:10:56,920 --> 00:10:58,600
visualment, que hi ha algorismes.

255
00:10:58,600 --> 00:11:02,470
I combinar espècie de només un d'aquests
algoritme que és fonamentalment més ràpid

256
00:11:02,470 --> 00:11:03,450
que alguns d'aquests altres tipus.

257
00:11:03,450 --> 00:11:07,800
De fet, combinar curta és no només en el
millor dels casos n log n, en el pitjor dels casos

258
00:11:07,800 --> 00:11:09,460
cas n log n.

259
00:11:09,460 --> 00:11:14,540
I quan vostè té aquesta coincidència de
omega i grans O és el mateix?

260
00:11:14,540 --> 00:11:17,310
De fet, podem descriure com el que és
anomenada theta, encara que és un

261
00:11:17,310 --> 00:11:18,220
poc menys comú.

262
00:11:18,220 --> 00:11:21,730
Però això només significa que els dos límits,
en aquest cas, són els mateixos.

263
00:11:21,730 --> 00:11:25,770
>> Així fusionar espècie, el que fa
realment es redueixen a per nosaltres?

264
00:11:25,770 --> 00:11:27,000
Bé, recordar la motivació.

265
00:11:27,000 --> 00:11:30,340
Déjame treure a una altra animació que
no ens fixem en l'última vegada.

266
00:11:30,340 --> 00:11:33,390
Aquest, mateixa idea, però
que és una mica més gran.

267
00:11:33,390 --> 00:11:36,160
I jo seguiré endavant i assenyalar
primer - tenim l'ordenació per inserció en

268
00:11:36,160 --> 00:11:39,410
dalt a l'esquerra, a continuació, ordenació per selecció,
mena de bombolla, un parell d'altres tipus -

269
00:11:39,410 --> 00:11:42,670
petxina i ràpida - que no hem parlat
aproximadament, i el munt i combinar estil.

270
00:11:42,670 --> 00:11:47,090
>> Així, almenys, intentar enfocar els seus ulls en
els tres primers de l'esquerra i després

271
00:11:47,090 --> 00:11:49,120
fusionar espècie quan faig clic
la fletxa verda.

272
00:11:49,120 --> 00:11:51,900
Però vaig a deixar que tots ells funcionen, només per
li donarà una idea de la diversitat de

273
00:11:51,900 --> 00:11:53,980
algoritmes que hi ha al món.

274
00:11:53,980 --> 00:11:56,180
Vaig a deixar que aquest termini
per tan sols uns segons.

275
00:11:56,180 --> 00:11:59,640
I si et enfoques els teus ulls - triar una
algorisme, se centren en ell només per un

276
00:11:59,640 --> 00:12:02,970
segon - vostè començarà a veure el
patró que està aplicació.

277
00:12:02,970 --> 00:12:04,530
>> Combinar classe, avís, es fa.

278
00:12:04,530 --> 00:12:06,430
Pila de classificació, ordenació ràpida, closca -

279
00:12:06,430 --> 00:12:09,480
pel que sembla que presentem els tres
pitjors algoritmes de setmana passat.

280
00:12:09,480 --> 00:12:12,960
Però això és bo que estem aquí avui per
mira fusió espècie, que és un

281
00:12:12,960 --> 00:12:16,500
els més fàcils és a la vista, fins i tot
encara que probablement es doblarà la teva ment

282
00:12:16,500 --> 00:12:17,490
només una mica.

283
00:12:17,490 --> 00:12:21,130
Aquí podem veure fins a quin punt
ordenació per selecció és una merda.

284
00:12:21,130 --> 00:12:24,600
>> Però d'altra banda, és
molt fàcil d'implementar.

285
00:12:24,600 --> 00:12:28,160
I potser per P 3 setembre, que és una de les
algoritmes que va triar per implementar

286
00:12:28,160 --> 00:12:28,960
per a l'edició estàndard.

287
00:12:28,960 --> 00:12:30,970
Perfectament bé, tota la raó.

288
00:12:30,970 --> 00:12:35,210
>> Però una vegada més, a mesura que n es fa gran, si
triar aplicar un algoritme més ràpid

289
00:12:35,210 --> 00:12:39,020
com fusionar espècie, les probabilitats són de major i
entrades més grans, el seu codi és

290
00:12:39,020 --> 00:12:39,800
va a córrer més ràpid.

291
00:12:39,800 --> 00:12:41,090
El seu lloc web funcionarà millor.

292
00:12:41,090 --> 00:12:42,650
Els usuaris van a ser més feliç.

293
00:12:42,650 --> 00:12:45,280
I així hi ha aquests efectes
de la realitat, donant

294
00:12:45,280 --> 00:12:47,350
nosaltres una mica més profund pensament.

295
00:12:47,350 --> 00:12:49,990
>> Així que donem una ullada al que fusionar
tipus és realment tot.

296
00:12:49,990 --> 00:12:52,992
El millor és que fusionar
tipus és només això.

297
00:12:52,992 --> 00:12:56,300
Això és, un cop més, el que hem anomenat
pseudocodi, ser pseudocodi

298
00:12:56,300 --> 00:12:57,720
Sintaxi Anglès-like.

299
00:12:57,720 --> 00:12:59,890
I la simplicitat és
mena de fascinant.

300
00:12:59,890 --> 00:13:02,840
>> Així que a l'entrada de n elements - de manera que
Només vol dir, això és una matriu.

301
00:13:02,840 --> 00:13:04,000
Té n coses en ella.

302
00:13:04,000 --> 00:13:05,370
Això és tot el que estem dient no.

303
00:13:05,370 --> 00:13:07,560
>> Si n és menor que 2, tornar.

304
00:13:07,560 --> 00:13:08,640
Així que això és només el cas trivial.

305
00:13:08,640 --> 00:13:12,580
Si n és menor que 2, llavors, evidentment, és
1 o 0, en aquest cas la cosa

306
00:13:12,580 --> 00:13:14,780
ja està ordenat o inexistent,
així que tornar.

307
00:13:14,780 --> 00:13:15,900
No hi ha res a fer.

308
00:13:15,900 --> 00:13:18,360
Així que això és un cas senzill d'arrencar.

309
00:13:18,360 --> 00:13:20,110
>> Si no, tenim tres passos.

310
00:13:20,110 --> 00:13:23,650
Ordenar la meitat esquerra dels elements, més o menys
la meitat dreta dels elements,

311
00:13:23,650 --> 00:13:26,650
i després combinar les meitats ordenades.

312
00:13:26,650 --> 00:13:29,400
El que és interessant aquí és que
Sóc una mena de batea, oi?

313
00:13:29,400 --> 00:13:32,300
Hi ha una espècie de definició circular
a aquest algorisme.

314
00:13:32,300 --> 00:13:35,986
En quin sentit és l'algoritme de
circular definició?

315
00:13:35,986 --> 00:13:37,850
>> AUDIÈNCIA: [inaudible].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Sí, el meu algorisme de classificació,
dues de les seves mesures són "una espècie

317
00:13:41,670 --> 00:13:44,640
alguna cosa ". Així que ens porta a la
pregunta, bé, què vaig a utilitzar

318
00:13:44,640 --> 00:13:46,460
per ordenar la meitat esquerra
i la meitat dreta?

319
00:13:46,460 --> 00:13:49,600
I la bellesa aquí és que encara que
de nou, aquesta és la ment-flexió

320
00:13:49,600 --> 00:13:54,030
part potencialment, pot utilitzar la mateixa
algorisme per ordenar la meitat esquerra.

321
00:13:54,030 --> 00:13:54,700
>> Però espereu un minut.

322
00:13:54,700 --> 00:13:57,070
Quan et diuen que ordenar la
mitjà esquerre, quins són els dos

323
00:13:57,070 --> 00:13:58,240
mesures seran el següent?

324
00:13:58,240 --> 00:14:00,550
El arreglarem la meitat esquerra de la
la meitat esquerra i la dreta

325
00:14:00,550 --> 00:14:01,420
la meitat de la meitat esquerra.

326
00:14:01,420 --> 00:14:04,430
Maleïda sigui, com puc ordenar els dos
meitats o quarts, ara?

327
00:14:04,430 --> 00:14:05,260
>> Però això està bé.

328
00:14:05,260 --> 00:14:07,830
Tenim un algorisme de classificació aquí.

329
00:14:07,830 --> 00:14:10,660
I encara que és possible que preocupar-se en
primer es tracta d'una espècie d'infinit

330
00:14:10,660 --> 00:14:12,780
bucle, és un cicle que mai és
va a acabar - que va a

331
00:14:12,780 --> 00:14:15,770
acabar d'una vegada el que passa?

332
00:14:15,770 --> 00:14:16,970
Un cop n és menor que 2.

333
00:14:16,970 --> 00:14:19,180
Que amb el temps passarà,
perquè si segueixes reduir a la meitat i

334
00:14:19,180 --> 00:14:23,020
reduir a la meitat en reduir a la meitat aquestes meitats, segurament
finalment va a acabar

335
00:14:23,020 --> 00:14:25,350
amb només 1 o 0 elements.

336
00:14:25,350 --> 00:14:28,500
En aquest moment, aquest algorisme
diu que ja està.

337
00:14:28,500 --> 00:14:31,020
>> Així que la veritable màgia d'aquesta
algorisme sembla estar en

338
00:14:31,020 --> 00:14:33,470
el pas final, la fusió.

339
00:14:33,470 --> 00:14:37,190
Aquesta simple idea només la fusió de dues
coses, això és el que està passant en última instància,

340
00:14:37,190 --> 00:14:40,920
que ens permeti ordenar una matriu de,
diguem, vuit elements.

341
00:14:40,920 --> 00:14:44,410
Així que tinc vuit més boles de la tensió de fins a
Aquí, vuit fulles de paper, i una

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

343
00:14:45,500 --> 00:14:46,140
que he de complir.

344
00:14:46,140 --> 00:14:46,960
>> [El]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Si poguéssim prendre 08:00
voluntaris, i veurem si podem

346
00:14:48,970 --> 00:14:51,430
jugar a això, així que.

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

348
00:14:52,500 --> 00:14:53,565
La informàtica és cada vegada divertit.

349
00:14:53,565 --> 00:14:54,320
Està bé.

350
00:14:54,320 --> 00:14:57,770
Així que hi ha de vosaltres 3,
major part allà.

351
00:14:57,770 --> 00:14:58,580
Quatre a la part posterior.

352
00:14:58,580 --> 00:15:02,220
¿I que farem que
tres a la fila?

353
00:15:02,220 --> 00:15:03,390
I quatre a la part davantera.

354
00:15:03,390 --> 00:15:04,920
Així que 8, anem amunt.

355
00:15:04,920 --> 00:15:12,060
>> [El]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Estic realment
no estic segur del que és.

357
00:15:13,450 --> 00:15:14,810
Són les boles de la tensió?

358
00:15:14,810 --> 00:15:16,510
Els llums d'escriptori?

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

360
00:15:18,650 --> 00:15:19,680
L'Internet?

361
00:15:19,680 --> 00:15:20,160
>> D'acord.

362
00:15:20,160 --> 00:15:21,310
Així que anem cap amunt.

363
00:15:21,310 --> 00:15:22,310
Qui vol -

364
00:15:22,310 --> 00:15:23,570
segueixen arribant.

365
00:15:23,570 --> 00:15:24,240
Anem a veure.

366
00:15:24,240 --> 00:15:26,460
I això et posa en el lloc -

367
00:15:26,460 --> 00:15:27,940
vostè està en una ubicació.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, espera un minut.

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

370
00:15:30,760 --> 00:15:31,310
Bé, estem bé.

371
00:15:31,310 --> 00:15:35,130
Molt bé, així que cada un té un seient,
però no en el vidre de Google.

372
00:15:35,130 --> 00:15:36,475
Déjame fer cua aquests.

373
00:15:36,475 --> 00:15:37,115
Com et dius?

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
Molt bé, s'arriba a semblar-
el geek, si això està bé.

377
00:15:42,000 --> 00:15:44,625
Bé, jo també, suposo,
només per un moment.

378
00:15:44,625 --> 00:15:45,875
D'acord, espera.

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

380
00:15:48,510 --> 00:15:50,950
Hem estat tractant d'arribar a un
cas d'ús de Google Glass, i

381
00:15:50,950 --> 00:15:53,750
va pensar que seria divertit per fer
això quan la gent està a l'escenari.

382
00:15:53,750 --> 00:15:57,120
Anem a gravar el món
des de la seva perspectiva.

383
00:15:57,120 --> 00:15:58,410
Està bé.

384
00:15:58,410 --> 00:15:59,830
No és probablement el que pretén Google.

385
00:15:59,830 --> 00:16:02,260
Bé, si no t'importa portar
això per als pròxims incòmodes minuts,

386
00:16:02,260 --> 00:16:03,150
això seria meravellós.

387
00:16:03,150 --> 00:16:08,620
>> Molt bé, així que tenim aquí una gran varietat de
elements, i que de matriu, com per la

388
00:16:08,620 --> 00:16:11,480
trossos de paper en aquestes persones "
mans, està actualment classificat.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Oh, això és molt estrany.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: És més o menys a l'atzar.

391
00:16:12,810 --> 00:16:15,760
I en un moment, tractarem
implementar fusionar espècie junts

392
00:16:15,760 --> 00:16:17,950
i veure a on idea clau és.

393
00:16:17,950 --> 00:16:21,970
I el truc aquí és una espècie de combinació
cosa que encara no hem assumit.

394
00:16:21,970 --> 00:16:24,030
En realitat necessitem una mica de
espai addicional.

395
00:16:24,030 --> 00:16:26,650
Llavors, què va a ser especialment
interessant d'això és que aquests

396
00:16:26,650 --> 00:16:29,270
nois van a moure una mica
poc, perquè jo vaig a assumir que

397
00:16:29,270 --> 00:16:31,880
hi ha un conjunt addicional d'espai,
dir, just darrere d'ells.

398
00:16:31,880 --> 00:16:34,570
>> Així que si estan darrere de la seva cadira,
que és la matriu secundària.

399
00:16:34,570 --> 00:16:36,960
Si estan asseguts aquí, això és
la matriu primària.

400
00:16:36,960 --> 00:16:40,170
Però aquest és un recurs que tenim
no aprofitat fins ara amb la bombolla

401
00:16:40,170 --> 00:16:42,040
espècie, amb la selecció de gènere,
amb l'ordenació per inserció.

402
00:16:42,040 --> 00:16:44,600
Recordem la setmana passada, tothom
tipus de baralla en el seu lloc.

403
00:16:44,600 --> 00:16:46,840
Ells no fan servir la memòria addicional.

404
00:16:46,840 --> 00:16:49,310
Vam habitació per a persones amb
moure a la gent al voltant.

405
00:16:49,310 --> 00:16:50,580
>> Així que aquesta és una idea clau, també.

406
00:16:50,580 --> 00:16:53,410
Hi ha un trade-off, en general, en
ciències de la computació, dels recursos.

407
00:16:53,410 --> 00:16:55,800
Per accelerar una mica
com el temps, vas a

408
00:16:55,800 --> 00:16:56,900
haver de pagar un preu.

409
00:16:56,900 --> 00:17:00,750
I un d'aquests preus és molt sovint
l'espai, la quantitat de memòria o disc

410
00:17:00,750 --> 00:17:01,700
espai de disc que utilitzeu.

411
00:17:01,700 --> 00:17:03,640
O bé, francament, la quantitat
de temps del programador.

412
00:17:03,640 --> 00:17:06,700
Quant de temps li pren, l'ésser humà,
per realment posar en pràctica una mica més

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

414
00:17:07,829 --> 00:17:09,760
Però per ara, la compensació
és el temps i l'espai.

415
00:17:09,760 --> 00:17:11,930
>> Així que si vostès poguessin acaba de celebrar el
números perquè puguem veure que ets

416
00:17:11,930 --> 00:17:15,839
de fet a joc 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Excel · lent.

418
00:17:16,599 --> 00:17:19,520
Així que vaig a tractar d'orquestrar
coses, si vostès poden simplement

419
00:17:19,520 --> 00:17:21,800
segueix-me aquí.

420
00:17:21,800 --> 00:17:26,650
>> Així que em vaig a posar en pràctica, en primer lloc, la
primer pas de la pseudocodi, que és

421
00:17:26,650 --> 00:17:29,440
a l'entrada de n elements, si n és
menys de 2, i després tornar.

422
00:17:29,440 --> 00:17:31,370
Òbviament, això no
s'apliquen, pel que seguim endavant.

423
00:17:31,370 --> 00:17:33,340
Així ordenar la meitat esquerra dels elements.

424
00:17:33,340 --> 00:17:36,220
Així que això significa que em vaig a centrar la meva
atenció per un moment sobre aquestes

425
00:17:36,220 --> 00:17:37,310
quatre nois aquí.

426
00:17:37,310 --> 00:17:39,774
D'acord, què he de fer al costat?

427
00:17:39,774 --> 00:17:40,570
>> AUDIÈNCIA: Ordenar la meitat esquerra.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Així que ara he de ordenar
la meitat esquerra d'aquests nois.

429
00:17:42,780 --> 00:17:45,580
Perquè de nou, suposem que vostè la
objectiu és ordenar la meitat esquerra.

430
00:17:45,580 --> 00:17:46,440
Com fer això?

431
00:17:46,440 --> 00:17:49,140
Només has de seguir les instruccions, fins i tot
encara que estem fent de nou.

432
00:17:49,140 --> 00:17:50,160
Així ordenar la meitat esquerra.

433
00:17:50,160 --> 00:17:52,030
Ara estic classificar aquests dos nois.

434
00:17:52,030 --> 00:17:53,563
Què ve ara?

435
00:17:53,563 --> 00:17:54,510
>> AUDIÈNCIA: Ordenar la meitat esquerra.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: Ordenar la meitat esquerra.

437
00:17:55,460 --> 00:18:00,680
Així que ara aquests, aquest seient aquí,
és una llista de grandària 1.

438
00:18:00,680 --> 00:18:01,365
¿I quin és el teu nom?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESA MARGARITA: Princess Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princess Daisy és aquí.

441
00:18:03,690 --> 00:18:07,470
I pel que ja està ordenat, perquè
la llista és de grandària 1.

442
00:18:07,470 --> 00:18:09,490
Què és el pròxim que fer?

443
00:18:09,490 --> 00:18:13,680
Acceptar, tornarà, perquè aquesta llista és de
grandària 1, que és menor que 2.

444
00:18:13,680 --> 00:18:14,320
Llavors, quin és el següent pas?

445
00:18:14,320 --> 00:18:17,490
I ara has de tipus de
fer marxa enrere en la seva ment.

446
00:18:17,490 --> 00:18:19,340
>> Ordenar la meitat dreta, que és -

447
00:18:19,340 --> 00:18:19,570
Quin és el teu nom?

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

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

450
00:18:20,980 --> 00:18:23,210
I què fem ara que
tenim una llista de mida d'1?

451
00:18:23,210 --> 00:18:24,440
>> AUDIÈNCIA: Return.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: Cura.

453
00:18:24,760 --> 00:18:29,540
Tornem primer, i ara la tercera
pas - i si em mena de representar per

454
00:18:29,540 --> 00:18:33,490
que abasta els dos seients ara, ara
haver d'incorporar aquests dos elements.

455
00:18:33,490 --> 00:18:35,530
Així que ara, per desgràcia, els elements
estan fora de servei.

456
00:18:35,530 --> 00:18:39,920
Però aquí és on el procés de fusió
comença a ser convincent.

457
00:18:39,920 --> 00:18:42,410
>> Així que si vostès poguessin posar-se dempeus per només
un moment, vaig a necessitar, en un

458
00:18:42,410 --> 00:18:44,170
Actualment, amb el pas darrere de la cadira.

459
00:18:44,170 --> 00:18:46,480
I si Linda, perquè és 2
inferior a 4, per què no fer

460
00:18:46,480 --> 00:18:48,130
véns per primera vegada?

461
00:18:48,130 --> 00:18:48,690
Queda't aquí.

462
00:18:48,690 --> 00:18:50,520
Així Linda, véns primer.

463
00:18:50,520 --> 00:18:53,820
>> Ara, en realitat, si és només un conjunt
que només podia moure en temps real

464
00:18:53,820 --> 00:18:55,360
des d'aquesta cadira a aquest lloc.

465
00:18:55,360 --> 00:18:57,770
Així que imaginin que va tenir una constant
nombre de passos 1.

466
00:18:57,770 --> 00:18:58,480
I ara -

467
00:18:58,480 --> 00:19:01,490
però hem de posar en
el primer lloc aquí.

468
00:19:01,490 --> 00:19:03,930
>> I ara, si pogués entrar en raó,
així, anem a

469
00:19:03,930 --> 00:19:06,300
ser en lloc de dos.

470
00:19:06,300 --> 00:19:09,120
I malgrat això se sent com si fos
prendre un temps, el que és bo que ara és

471
00:19:09,120 --> 00:19:14,710
que la meitat esquerra de la
meitat esquerra està ordenada.

472
00:19:14,710 --> 00:19:18,010
Llavors, quin era el següent pas, si ara
retrocedir encara més en la història?

473
00:19:18,010 --> 00:19:18,980
>> AUDIÈNCIA: Meitat dreta.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: Ordenar la meitat dreta.

475
00:19:19,900 --> 00:19:21,320
Així que vostès han de fer això, també.

476
00:19:21,320 --> 00:19:23,510
Així que si vostè pot posar-se dret
per un moment?

477
00:19:23,510 --> 00:19:25,192
I quin és el teu nom?

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, així que Jess és ara l'esquerra
la meitat de la meitat dreta.

481
00:19:29,720 --> 00:19:31,400
I el que és una llista de grandària 1.

482
00:19:31,400 --> 00:19:32,380
Ella, òbviament, ordenada.

483
00:19:32,380 --> 00:19:33,070
I el teu nom?

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

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle òbviament
una llista de grandària 1.

486
00:19:35,340 --> 00:19:36,050
Ja està solucionat.

487
00:19:36,050 --> 00:19:38,690
Així que ara succeeix la màgia,
el procés de fusió.

488
00:19:38,690 --> 00:19:39,790
Llavors, qui vindrà primer?

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

490
00:19:41,560 --> 00:19:43,280
Així que si vostè pot venir a la tornada.

491
00:19:43,280 --> 00:19:47,090
L'espai que tenim disponible per a ella ara
és just darrere d'aquesta cadira aquí.

492
00:19:47,090 --> 00:19:51,580
I ara, si pogués tornar, així,
ara tenim, per ser clars, dos

493
00:19:51,580 --> 00:19:53,810
meitats, cadascuna de mida 2 -

494
00:19:53,810 --> 00:19:57,090
i simplement per l'amor de la representació, si
podria fer una mica d'un espai -

495
00:19:57,090 --> 00:19:59,780
una esquerra mig aquí, un
mitjà aquí.

496
00:19:59,780 --> 00:20:01,160
>> Rebobine més en la història.

497
00:20:01,160 --> 00:20:02,270
Quin és el pas següent?

498
00:20:02,270 --> 00:20:03,030
>> AUDIÈNCIA: Combina.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Així que ara hem de combinar.

500
00:20:04,160 --> 00:20:07,490
Així que bé, així que ara, gràcies a Déu, ens
simplement alliberat quatre cadires.

501
00:20:07,490 --> 00:20:11,480
Per això hem utilitzat el doble de memòria, però
podem donar flip-tirar-entre

502
00:20:11,480 --> 00:20:12,330
les dues matrius.

503
00:20:12,330 --> 00:20:14,190
Llavors, quin és el nombre de venir primer?

504
00:20:14,190 --> 00:20:14,850
Així que Michelle, òbviament.

505
00:20:14,850 --> 00:20:16,680
Així que veuen al seu voltant i prendre
seu seient aquí.

506
00:20:16,680 --> 00:20:19,120
I a continuació, el número 2 és òbviament
següent, per la que vénen aquí.

507
00:20:19,120 --> 00:20:21,520
Número 4, número 6.

508
00:20:21,520 --> 00:20:23,390
I de nou, tot i que hi ha una
poc de caminar involucrats,

509
00:20:23,390 --> 00:20:26,010
Realment, aquests podrien ocórrer instantàniament,
movent un -

510
00:20:26,010 --> 00:20:26,880
Bé, ben jugat.

511
00:20:26,880 --> 00:20:28,350
>> [El]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: I ara estem
en molt bona forma.

513
00:20:29,680 --> 00:20:34,910
La meitat esquerra de la totalitat
d'entrada ja ha estat solucionat.

514
00:20:34,910 --> 00:20:37,370
Bé, pel que aquests nois tenien
l'avantatge de la meva -

515
00:20:37,370 --> 00:20:40,340
Com s'acaben totes les noies a la
a l'esquerra i tots els nois de la dreta?

516
00:20:40,340 --> 00:20:42,450
>> OK, així que nois tornen ara.

517
00:20:42,450 --> 00:20:44,680
Així que no vaig a caminar a través d'
aquests passos.

518
00:20:44,680 --> 00:20:46,550
Anem a veure si podem tornar a aplicar
la mateixa pseudocodi.

519
00:20:46,550 --> 00:20:50,050
Si vols seguir endavant i posar-se dempeus,
i vostès, et vaig a donar el micròfon.

520
00:20:50,050 --> 00:20:52,990
A veure si no es pot reproduir el que
que acabem de fer aquí a la

521
00:20:52,990 --> 00:20:53,880
altre extrem de la llista.

522
00:20:53,880 --> 00:20:59,530
Qui ha de parlar en primer lloc,
basat en l'algoritme?

523
00:20:59,530 --> 00:21:03,210
Així que expliqui el que està fent abans de
realitzar qualsevol moviment del peu.

524
00:21:03,210 --> 00:21:05,930
>> ALTAVEU 1: D'acord, ja
Jo sóc la meitat esquerra de la

525
00:21:05,930 --> 00:21:07,790
mitjà esquerre, torno.

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

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Good.

528
00:21:09,250 --> 00:21:10,350
>> ALTAVEU 1: I llavors -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Qui fa
el micro passi a la següent?

530
00:21:11,800 --> 00:21:12,920
>> ALTAVEU 1: nombre següent.

531
00:21:12,920 --> 00:21:14,720
>> ALTAVEU 2: Així que estic a la meitat dreta
de la meitat esquerra de la

532
00:21:14,720 --> 00:21:17,830
mitjà esquerre, i torni.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Good.

534
00:21:18,050 --> 00:21:18,550
Tornarà.

535
00:21:18,550 --> 00:21:21,855
¿I ara què és el que segueix per a vostès?

536
00:21:21,855 --> 00:21:23,740
>> ALTAVEU 2: Volem veure qui és més petit.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Exactament.

538
00:21:24,200 --> 00:21:24,940
Volem combinar.

539
00:21:24,940 --> 00:21:27,590
L'espai que utilitzarem per combinar
que en, encara que són

540
00:21:27,590 --> 00:21:30,250
òbviament ordenat ja, anem
seguir el mateix algorisme.

541
00:21:30,250 --> 00:21:31,560
Llavors, qui va en primera volta?

542
00:21:31,560 --> 00:21:35,720
Així que 3, i després 7.

543
00:21:35,720 --> 00:21:38,570
I ara el micròfon es
a aquests nois, d'acord?

544
00:21:38,570 --> 00:21:43,590
>> ALTAVEU 3: Així que sóc la meitat dreta de la
la meitat esquerra, i el meu n és menor que

545
00:21:43,590 --> 00:21:45,048
1, així que només vaig a passar -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Good.

547
00:21:46,380 --> 00:21:49,450
>> ALTAVEU 4: Jo sóc la meitat dreta de la
la meitat dreta de la part dreta, i estic

548
00:21:49,450 --> 00:21:51,740
També una persona, així que estic
tornarà.

549
00:21:51,740 --> 00:21:52,990
Així que ara ens fusionem.

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

551
00:21:55,140 --> 00:21:56,150
>> ALTAVEU 3: Llavors tornem.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Així que anar a la part posterior.

553
00:21:57,160 --> 00:21:59,200
5 Així va primer, després 8.

554
00:21:59,200 --> 00:22:01,240
I ara públic, que és el
un pas que hem de retrocedir ara

555
00:22:01,240 --> 00:22:02,200
una còpia en les nostres ments?

556
00:22:02,200 --> 00:22:02,940
>> AUDIÈNCIA: Combina.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: La fusió de la meitat esquerra i dreta
meitat de la meitat esquerra de l'original.

558
00:22:07,270 --> 00:22:08,840
Així que ara -

559
00:22:08,840 --> 00:22:10,520
i només per deixar-ho clar,
fer una mica d'espai

560
00:22:10,520 --> 00:22:11,690
entre vosaltres dos.

561
00:22:11,690 --> 00:22:13,800
Així que ara que són les dues llistes,
esquerra i dreta.

562
00:22:13,800 --> 00:22:18,320
Llavors, com ara fusionem nois a
la primera fila de seients de nou?

563
00:22:18,320 --> 00:22:19,600
>> 3 va primer.

564
00:22:19,600 --> 00:22:20,850
5 Per això, òbviament.

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

566
00:22:23,110 --> 00:22:27,330
A continuació, 7, 8 i ara.

567
00:22:27,330 --> 00:22:28,710
Bé, i ara que som?

568
00:22:28,710 --> 00:22:29,650
>> AUDIÈNCIA: No realitzat.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: No realitzat, perquè
Òbviament, hi ha un pas que queda.

570
00:22:32,440 --> 00:22:35,720
Però, de nou, la raó per la que estic fent servir aquesta
l'argot com "rebobinar en la seva ment,"

571
00:22:35,720 --> 00:22:37,160
és perquè això és realment
el que està succeint.

572
00:22:37,160 --> 00:22:39,610
Anem a través de tots aquests passos,
però som una mena de pausa per a una

573
00:22:39,610 --> 00:22:42,480
Actualment, el busseig profund al
algoritme, fent una pausa per un moment,

574
00:22:42,480 --> 00:22:45,840
busseig més profund en l'algorisme, i
Ara tenim a una mena de retrocés en la nostra

575
00:22:45,840 --> 00:22:49,430
ment i desfer totes aquestes capes
que hem espècie de posada en espera.

576
00:22:49,430 --> 00:22:51,790
>> Així que ara tenim dues llistes de mida 4.

577
00:22:51,790 --> 00:22:54,790
Si vostès poguessin posar-se dempeus un cop més
i fer una mica d'espai per

578
00:22:54,790 --> 00:22:57,230
deixar clar que es tracta de l'esquerra
la meitat de l'original, la

579
00:22:57,230 --> 00:22:58,620
la meitat dreta de l'original.

580
00:22:58,620 --> 00:23:01,060
Qui és el primer número que
hagi de tirar a la part posterior?

581
00:23:01,060 --> 00:23:01,870
Michelle, és clar.

582
00:23:01,870 --> 00:23:03,230
>> Per això, vam posar Michelle aquí.

583
00:23:03,230 --> 00:23:05,080
I qui té el número 2?

584
00:23:05,080 --> 00:23:06,440
Número 2 ve a la part posterior també.

585
00:23:06,440 --> 00:23:07,800
Número 3?

586
00:23:07,800 --> 00:23:08,510
Excel · lent.

587
00:23:08,510 --> 00:23:16,570
Número 4, número 5, número 6,
número 7, i el número 8.

588
00:23:16,570 --> 00:23:18,850
>> Bé, així que em vaig sentir com un munt
de passos, segur.

589
00:23:18,850 --> 00:23:22,390
Però ara anem a veure si no podem confirmar
espècie de intuïtivament que aquest

590
00:23:22,390 --> 00:23:26,190
algorisme fonamentalment, en particular pel que
n es fa molt gran, com hem vist

591
00:23:26,190 --> 00:23:29,170
amb les animacions, és
fonamentalment més ràpid.

592
00:23:29,170 --> 00:23:33,400
Així que jo pretenc que aquest algorisme, en el pitjor
cas i fins i tot en el millor dels casos,

593
00:23:33,400 --> 00:23:36,160
és un gran O de n log n vegades.

594
00:23:36,160 --> 00:23:39,160
És a dir, que hi ha algun aspecte d'aquest
algorisme que pren n passos, però

595
00:23:39,160 --> 00:23:43,110
hi ha un altre aspecte en algun lloc
aquesta iteració, que bucle, que

596
00:23:43,110 --> 00:23:44,410
porta registre de n passos.

597
00:23:44,410 --> 00:23:49,154
Podem posar el nostre dit en el que els
dos nombres es refereixen?

598
00:23:49,154 --> 00:23:51,320
Bé, on -

599
00:23:51,320 --> 00:23:54,160
¿A on va el micròfon?

600
00:23:54,160 --> 00:23:58,660
>> ALTAVEU 1: La sessió núm ser
nosaltres trencar en dos -

601
00:23:58,660 --> 00:23:59,630
dividir per dos, essencialment.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Exactament.

603
00:24:00,120 --> 00:24:03,000
Cada vegada que veiem en qualsevol algoritme així
ara, no hi ha hagut aquest patró de

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

605
00:24:04,200 --> 00:24:05,700
I es redueix típicament
a alguna cosa que és

606
00:24:05,700 --> 00:24:07,100
logarítmica, log base 2.

607
00:24:07,100 --> 00:24:10,180
Però el que realment podria ser qualsevol cosa,
però entrar base 2.

608
00:24:10,180 --> 00:24:11,330
>> Ara, què passa amb el núm?

609
00:24:11,330 --> 00:24:14,550
Puc veure que tipus de què dividim
nois - es divideix, es divideixen,

610
00:24:14,550 --> 00:24:15,910
que divideix, es divideix.

611
00:24:15,910 --> 00:24:18,760
D'on ve el final de la?

612
00:24:18,760 --> 00:24:19,810
>> Així que és la fusió.

613
00:24:19,810 --> 00:24:20,610
A causa a pensar-hi.

614
00:24:20,610 --> 00:24:25,420
En combinar vuit persones a conjunt,
pel que la meitat d'ells són un conjunt de quatre

615
00:24:25,420 --> 00:24:27,770
i l'altra meitat són una altra
conjunt de quatre, com anar

616
00:24:27,770 --> 00:24:28,820
de fer la fusió?

617
00:24:28,820 --> 00:24:30,830
Bé, vostès van fer que
bastant intuïtiva.

618
00:24:30,830 --> 00:24:34,140
>> Però si per contra el vaig fer una mica més
metòdicament, hauria assenyalat a

619
00:24:34,140 --> 00:24:38,090
la persona més a l'esquerra primer amb l'esquerra
part, va assenyalar a la persona més a l'esquerra

620
00:24:38,090 --> 00:24:42,080
d'aquest mitjà amb la mà dreta, i
només posteriorment va caminar a través de la

621
00:24:42,080 --> 00:24:46,990
llista, assenyalant l'element més petit
cada vegada, movent el dit una i

622
00:24:46,990 --> 00:24:48,970
més quan sigui necessari en la llista.

623
00:24:48,970 --> 00:24:51,890
Però el que és clau sobre aquesta fusió
procés és que estic comparant aquestes parelles

624
00:24:51,890 --> 00:24:53,460
dels elements.

625
00:24:53,460 --> 00:24:57,270
A partir de la meitat dreta i des de l'esquerra,
mitjà, estic fent marxa enrere ni una sola vegada.

626
00:24:57,270 --> 00:25:00,570
>> Així la pròpia fusió està prenent
no més de n passos.

627
00:25:00,570 --> 00:25:03,250
I quantes vegades he de
fer que la fusió?

628
00:25:03,250 --> 00:25:07,150
Bé, no més de n, i només
va veure que amb la fusió final.

629
00:25:07,150 --> 00:25:13,120
I pel que si vostè fa alguna cosa que té
log n passos n vegades, o viceversa,

630
00:25:13,120 --> 00:25:15,210
que ens va de vegades n log n donar.

631
00:25:15,210 --> 00:25:16,310
>> ¿I per què és això millor?

632
00:25:16,310 --> 00:25:19,600
Bé, si ja sabem que log
n és millor que n - a la dreta?

633
00:25:19,600 --> 00:25:22,590
Vam veure en la recerca binària, l'agenda
exemple, log n era definitivament

634
00:25:22,590 --> 00:25:23,760
millor que lineal.

635
00:25:23,760 --> 00:25:28,420
Així que significa n vegades registre n és
definitivament millor que n vegades una altra

636
00:25:28,420 --> 00:25:30,390
n, AKA n al quadrat.

637
00:25:30,390 --> 00:25:32,400
I això és el que en última instància sentim.

638
00:25:32,400 --> 00:25:34,928
>> Així que gran aplaudiment, si
vam poder, per a aquests nois.

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

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: I els seus regals de comiat -
vostè pot mantenir els números,

641
00:25:41,550 --> 00:25:44,010
si vol.

642
00:25:44,010 --> 00:25:45,620
I el teu regal de comiat, com sempre.

643
00:25:45,620 --> 00:25:47,290
Ah, i li enviarem
les imatges, Michelle.

644
00:25:47,290 --> 00:25:48,343
Gràcies.

645
00:25:48,343 --> 00:25:49,250
Està bé.

646
00:25:49,250 --> 00:25:50,400
Podrà gaudir d'una pilota antiestrès.

647
00:25:50,400 --> 00:25:54,110
>> I m'ho dius a mi tiri cap amunt, mentrestant,
nostre amic Rob Bowden per oferir

648
00:25:54,110 --> 00:25:59,520
alguna cosa diferent perspectiva sobre això,
ja que es pot pensar en aquests

649
00:25:59,520 --> 00:26:01,280
passos que ocorren en un cert
diferent manera.

650
00:26:01,280 --> 00:26:04,750
De fet, la posada a punt per al que Rob tracta d'
per mostrar suposa que hem

651
00:26:04,750 --> 00:26:09,030
ha fet fins a la divisió del
gran llista en vuit llistes petites,

652
00:26:09,030 --> 00:26:10,570
cada un tamany 1.

653
00:26:10,570 --> 00:26:13,350
>> Així que estem canviant el pseudocodi 01:00
poc acaba d'ordenar d'arribar a la

654
00:26:13,350 --> 00:26:15,320
idea central de com la fusió d'obres.

655
00:26:15,320 --> 00:26:17,600
Però el temps d'execució del
està a punt de fer és encara

656
00:26:17,600 --> 00:26:19,110
serà la mateixa.

657
00:26:19,110 --> 00:26:23,540
I de nou, la posada a punt aquí és que és
començat amb vuit llistes de grandària 1.

658
00:26:23,540 --> 00:26:27,730
Així que t'has perdut la part en la qual està
realment es fa el registre núm, log n, log n

659
00:26:27,730 --> 00:26:31,205
divisòria de l'entrada.

660
00:26:31,205 --> 00:26:32,120
>> [REPRODUIR VIDEO]

661
00:26:32,120 --> 00:26:33,615
>> -Això és tot pel pas un.

662
00:26:33,615 --> 00:26:38,270
En el segon pas, en diverses ocasions
barreja parells de llistes.

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

664
00:26:39,210 --> 00:26:41,270
Només àudio ve
fora del meu ordinador.

665
00:26:41,270 --> 00:26:42,520
Anem a intentar novament.

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

667
00:26:45,330 --> 00:26:48,310
>> -Només arbitràriament triar què -
Ara tenim quatre llistes.

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

669
00:26:51,590 --> 00:26:52,120
Aprèn abans.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Això és.

671
00:26:53,040 --> 00:27:00,510
>> -La fusió de 108 i 15, ens trobem
amb la llista de 15, 108.

672
00:27:00,510 --> 00:27:07,170
La fusió de 50 i 4, que
acabar amb 4, 50.

673
00:27:07,170 --> 00:27:12,990
La fusió de 8 i 42, que
acabar amb 8, 42.

674
00:27:12,990 --> 00:27:19,970
I la fusió de 23 i 16, que
acabar amb 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Ara totes les nostres llistes són de mida 2.

676
00:27:23,270 --> 00:27:26,690
Tingueu en compte que cada un dels
quatre llistes desplegables s'ordenen.

677
00:27:26,690 --> 00:27:29,450
Així que podem començar a fusionar
parells de llistes de nou.

678
00:27:29,450 --> 00:27:38,420
La fusió de 15 i 108 i 4 i 50, que
primer prendre la 4, la 15, llavors

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

680
00:27:41,500 --> 00:27:50,610
La fusió de 8, 42 i 16, 23, primer agafem
el 8, a continuació, la 16, a continuació, la 23,

681
00:27:50,610 --> 00:27:52,700
a continuació, la 42.

682
00:27:52,700 --> 00:27:57,600
>> Així que ara tenim només dues llistes de mida
4, cadascun dels quals està ordenada.

683
00:27:57,600 --> 00:28:01,170
Així que ara ens unim aquestes dues llistes.

684
00:28:01,170 --> 00:28:11,835
En primer lloc, prenem el 4, després es pren la
8, i després prenem el 15, i després 16, després

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

686
00:28:19,456 --> 00:28:19,872
>> [FI REPRODUCCIÓ DE VÍDEO]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Novament, avís, mai
tocat un got donat més d'una vegada

688
00:28:23,430 --> 00:28:24,860
després d'avançar més enllà d'ella.

689
00:28:24,860 --> 00:28:26,200
Així que mai es repeteix.

690
00:28:26,200 --> 00:28:29,850
Així que sempre s'està movent cap a un costat,
i aquí és on tenim el nostre n.

691
00:28:29,850 --> 00:28:33,290
>> Per què no em deixa pujo una animació
que hem vist abans, però aquest cop

692
00:28:33,290 --> 00:28:35,110
centrar-se només en una mena de combinació.

693
00:28:35,110 --> 00:28:38,030
Déjame anar per davant i zoom
en això aquí.

694
00:28:38,030 --> 00:28:42,530
Primer deixeu-me triar una entrada a l'atzar,
magnificar això, i vostè pot ordenar de veure

695
00:28:42,530 --> 00:28:46,600
el que prenem per fet, abans,
fusionar espècie està fent.

696
00:28:46,600 --> 00:28:50,330
>> Així que adonar-se que vostè aconsegueix aquestes meitats o
aquests quarts oa vuitens d'aquests el

697
00:28:50,330 --> 00:28:53,140
problema que, de sobte,
començar a prendre bona forma.

698
00:28:53,140 --> 00:28:57,070
I, finalment, que es veu en
el final que bam,

699
00:28:57,070 --> 00:28:58,860
tot es van fusionar.

700
00:28:58,860 --> 00:29:01,690
>> Així que aquests són només tres diferents
realitza en la mateixa idea.

701
00:29:01,690 --> 00:29:05,980
Però la idea clau, igual que divideix
i vèncer en la primera classe,

702
00:29:05,980 --> 00:29:10,640
va ser que vam decidir dividir d'alguna manera
el problema en alguna cosa gran, en

703
00:29:10,640 --> 00:29:14,760
una mica espècie d'idèntic esperit,
però més petit i més petits i més petits

704
00:29:14,760 --> 00:29:15,660
i més petits.

705
00:29:15,660 --> 00:29:18,420
>> Ara una altra divertida manera de classificar de pensar
d'aquests, tot i que no és

706
00:29:18,420 --> 00:29:20,520
va a donar el mateix intuïtiva
comprensió, és

707
00:29:20,520 --> 00:29:21,640
la següent animació.

708
00:29:21,640 --> 00:29:25,400
Així que aquest és un vídeo que algú armar
l'associada diferent

709
00:29:25,400 --> 00:29:29,970
sons amb les diverses operacions de
ordenació per inserció, per fusió d'ordenació i

710
00:29:29,970 --> 00:29:31,150
per un parell dels altres.

711
00:29:31,150 --> 00:29:32,330
Així que en un moment, em vaig a pegar Play.

712
00:29:32,330 --> 00:29:33,600
Es tracta d'un minut de durada.

713
00:29:33,600 --> 00:29:37,410
I tot i que encara es pot veure la
patrons passant, aquest cop es pot

714
00:29:37,410 --> 00:29:41,420
També escoltar com aquests algorismes són
realitzar de manera diferent i amb

715
00:29:41,420 --> 00:29:43,950
una mica diferents patrons.

716
00:29:43,950 --> 00:29:45,830
>> Aquesta és l'ordenació per inserció.

717
00:29:45,830 --> 00:29:50,400
>> [TONS QUE JUGUEN]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Novament està tractant
per inserir cada element

719
00:29:52,400 --> 00:29:52,900
a on ha d'estar.

720
00:29:52,900 --> 00:29:54,628
Es tracta d'una mena de bombolla.

721
00:29:54,628 --> 00:30:10,097
>> [TONS QUE JUGUEN]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: I es pot ordenar de sensació
el relativament poca feina que està fent

723
00:30:13,630 --> 00:30:15,834
en cada pas.

724
00:30:15,834 --> 00:30:20,470
Això és el que sona com avorriment.

725
00:30:20,470 --> 00:30:21,472
>> [TONS QUE JUGUEN]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Es tracta d'una espècie de selecció,
on seleccionem l'element que volem per

727
00:30:25,222 --> 00:30:28,845
passant una i altra vegada i una altra
i posar-lo al principi.

728
00:30:28,845 --> 00:30:37,674
>> [TONS QUE JUGUEN]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Es tracta de fusionar espècie, que
vostè realment pot començar a sentir.

730
00:30:43,970 --> 00:30:51,810
>> [TONS QUE JUGUEN]

731
00:30:51,810 --> 00:30:54,770
>> [El]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Una mica anomenat GNOME
espècie, que no hem mirat.

733
00:30:58,395 --> 00:31:13,630
>> [TONS QUE JUGUEN]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Així que anem a veure, ara,
distret mentre esperem és el

735
00:31:17,910 --> 00:31:21,110
música, si puc ficar una mica
mica de matemàtiques aquí.

736
00:31:21,110 --> 00:31:24,850
Així que hi ha una quarta forma que podem
pensar en el que significa això

737
00:31:24,850 --> 00:31:29,210
funcions per ser més ràpid que els
que hem vist abans.

738
00:31:29,210 --> 00:31:32,470
I si vindràs al llarg de
un fons de les matemàtiques, que

739
00:31:32,470 --> 00:31:36,030
realment saben potser ja que
pot bufetejar un terme en aquesta tècnica -

740
00:31:36,030 --> 00:31:40,400
a saber, la recursió, una funció
que crida alguna manera en si.

741
00:31:40,400 --> 00:31:44,780
>> I un cop més, recordar que tipus de mescla
pseudocodi era recursiu, en el sentit

742
00:31:44,780 --> 00:31:48,460
que un dels passos de merge sort
va ser cridar a una espècie -

743
00:31:48,460 --> 00:31:49,740
que és, en si.

744
00:31:49,740 --> 00:31:52,480
Però gràcies a Déu, perquè ens mantenien
trucar a ordenar o combinar estil,

745
00:31:52,480 --> 00:31:55,880
específicament, en una més petita i més petita
i la llista més petita, al final

746
00:31:55,880 --> 00:32:00,005
tocat fons, gràcies al que anomenarem
un cas base, el cas no modificable que

747
00:32:00,005 --> 00:32:04,270
va dir que si la llista és petita, menys de 2
en aquest cas, torna immediatament.

748
00:32:04,270 --> 00:32:07,550
Si no tinguéssim aquest cas especial, el
algoritme mai tocaria fons,

749
00:32:07,550 --> 00:32:11,010
i vostè realment entrar en un
bucle infinit veritablement sempre.

750
00:32:11,010 --> 00:32:14,330
>> Però suposem que volem posar ara
alguns números sobre això, de nou, usant n

751
00:32:14,330 --> 00:32:15,660
com la mida de l'entrada.

752
00:32:15,660 --> 00:32:18,680
I jo volia preguntar, quin és
el temps total involucrat en

753
00:32:18,680 --> 00:32:19,800
corrent merge tipus?

754
00:32:19,800 --> 00:32:22,960
O en termes més generals, quin és
el cost de la mateixa en el temps?

755
00:32:22,960 --> 00:32:24,730
>> Bé, és bastant fàcil de mesurar això.

756
00:32:24,730 --> 00:32:29,010
Si n és menor que 2, el temps involucrat
en la classificació de n elements,

757
00:32:29,010 --> 00:32:30,480
on n és 2, és 0.

758
00:32:30,480 --> 00:32:31,410
A causa que acabem de tornar.

759
00:32:31,410 --> 00:32:32,510
No hi ha feina per fer.

760
00:32:32,510 --> 00:32:35,660
Ara podria dir-se que, potser és un pas o dos
mesures per esbrinar la quantitat de

761
00:32:35,660 --> 00:32:38,420
funciona, però és prou a prop de 0 que
Jo només vaig a dir que no hi ha feina

762
00:32:38,420 --> 00:32:40,940
necessari si la llista és tan petit
ser poc interessant.

763
00:32:40,940 --> 00:32:42,580
>> Però aquest cas és interessant.

764
00:32:42,580 --> 00:32:47,320
El cas recurrent va ser la branca de
el pseudocodi que va dir una altra cosa, més o menys

765
00:32:47,320 --> 00:32:52,000
la meitat esquerra, ordenar el dret
mitjà, unir les dues meitats.

766
00:32:52,000 --> 00:32:55,530
Ara, per què aquesta expressió
representa aquesta despesa?

767
00:32:55,530 --> 00:32:58,690
Bé, T de n només significa la
temps per ordenar n elements.

768
00:32:58,690 --> 00:33:03,070
I després a la part dreta de la
signe igual allà, la T de n divideix

769
00:33:03,070 --> 00:33:06,600
pel 2 es refereix al cost del que?

770
00:33:06,600 --> 00:33:07,570
Classificació de la meitat esquerra.

771
00:33:07,570 --> 00:33:10,990
L'altre T de n dividit per 2 és
presumiblement referint-se al cost de

772
00:33:10,990 --> 00:33:12,390
ordenar la meitat dreta.

773
00:33:12,390 --> 00:33:14,590
>> I llavors el més n?

774
00:33:14,590 --> 00:33:15,420
És la fusió.

775
00:33:15,420 --> 00:33:19,120
Perquè si vostè té dues llistes, una de
grandària n més de 2 i una altra de grandària n

776
00:33:19,120 --> 00:33:22,580
més de 2, ha de tocar l'essència
cadascun d'aquests elements, igual que Rob

777
00:33:22,580 --> 00:33:24,990
tocat cadascuna de les copes, i només
com hem assenyalat en cada un dels

778
00:33:24,990 --> 00:33:26,310
voluntaris a l'escenari.

779
00:33:26,310 --> 00:33:28,790
Per tant n és la despesa de fusió.

780
00:33:28,790 --> 00:33:31,780
>> Ara, per desgràcia, aquesta fórmula
és també en si recursiva.

781
00:33:31,780 --> 00:33:36,390
Així que si va fer la pregunta, si n és, per exemple,
16, si hi ha 16 persones a l'escenari

782
00:33:36,390 --> 00:33:40,670
o 16 tasses al vídeo, el nombre total de
passos es necessiten per ordenar

783
00:33:40,670 --> 00:33:41,550
amb mescla tipus?

784
00:33:41,550 --> 00:33:45,790
En realitat no és una resposta òbvia,
perquè ara vostè ha d'ordenar d'

785
00:33:45,790 --> 00:33:48,500
recursivament respondre a aquesta fórmula.

786
00:33:48,500 --> 00:33:51,190
>> Però això està bé, perquè permetin-me proposar
que fem el següent.

787
00:33:51,190 --> 00:33:56,670
El temps necessari per ordenar 16 persones o
16 tasses serà representat

788
00:33:56,670 --> 00:33:58,020
generalment com T de 16.

789
00:33:58,020 --> 00:34:01,400
Però això és igual, d'acord amb la nostra
fórmula anterior, 2 vegades la quantitat

790
00:34:01,400 --> 00:34:04,780
de temps que es necessita per ordenar
8 tasses de més 16.

791
00:34:04,780 --> 00:34:08,590
I de nou, més 16 és el moment d'unir,
i el doble de T de 8 és el

792
00:34:08,590 --> 00:34:10,790
temps per ordenar a meitat esquerra i la meitat dreta.

793
00:34:10,790 --> 00:34:11,989
>> Però de nou, això no és suficient.

794
00:34:11,989 --> 00:34:13,210
Hem de bussejar més profundament.

795
00:34:13,210 --> 00:34:16,409
Això vol dir que hem de respondre a la
pregunta, quin és T de 8?

796
00:34:16,409 --> 00:34:19,610
Bé T de 8 és a 2
temps T de 4 i de 8.

797
00:34:19,610 --> 00:34:20,520
Bé, què hi ha de la T 4?

798
00:34:20,520 --> 00:34:23,780
T de 4 està a 2 hores de la T2 més 4.

799
00:34:23,780 --> 00:34:25,489
Bé, quin és T de 2?

800
00:34:25,489 --> 00:34:29,030
T 2 està a només 2 vegades T d'1 més 2.

801
00:34:29,030 --> 00:34:31,940
>> I de nou, estem com aconseguir
atrapat en aquest cicle.

802
00:34:31,940 --> 00:34:34,790
Però està a punt d'arribar a aquest
anomenat cas base.

803
00:34:34,790 --> 00:34:37,310
Perquè el que és T 1, ens diem?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Així que ara, finalment, es pot treballar cap enrere.

806
00:34:39,730 --> 00:34:44,290
>> Si T 1 és 0, ara puc pujar una
alinear aquest tipus aquí, i no puc

807
00:34:44,290 --> 00:34:46,330
endoll 0 per T d'1.

808
00:34:46,330 --> 00:34:51,770
Així que això significa que és igual a 2 vegades zero,
també coneguda com 0, més 2.

809
00:34:51,770 --> 00:34:53,739
I tota aquesta expressió és 2.

810
00:34:53,739 --> 00:34:58,740
>> Ara bé, si em prenc el T de 2, la resposta
és 2, connecteu-lo a la línia mitjana, T

811
00:34:58,740 --> 00:35:02,740
de 4, això em dóna 2 cops
2 més 4, pel que 8.

812
00:35:02,740 --> 00:35:07,080
Doncs, jo connecto 8 a l'anterior
line, que em dóna 2 cops 8, 16.

813
00:35:07,080 --> 00:35:12,470
I si després seguim que amb l'
24, l'addició de 16, per fi tenim un

814
00:35:12,470 --> 00:35:13,820
valor de 64.

815
00:35:13,820 --> 00:35:18,480
>> Ara que en i per si mateixa espècie de parla
res a la notació n, la

816
00:35:18,480 --> 00:35:20,700
O gran, els àcids grassos omega que hem
estat parlant.

817
00:35:20,700 --> 00:35:24,890
Però resulta que el 64 és de fet
16, la mida de l'entrada,

818
00:35:24,890 --> 00:35:27,110
log base 2 de 16.

819
00:35:27,110 --> 00:35:30,200
I si això és una mica estrany, simplement
Penseu de nou, i es tornarà

820
00:35:30,200 --> 00:35:30,700
per al temps.

821
00:35:30,700 --> 00:35:33,775
Si això és log base 2, és com 2
elevat a la que li dóna 16?

822
00:35:33,775 --> 00:35:36,380
Oh, això és 4, pel que és 16 vegades 4.

823
00:35:36,380 --> 00:35:39,380
>> I de nou, no és un gran problema si aquest
és una espècie de vague record ara.

824
00:35:39,380 --> 00:35:43,720
Però per ara, assumir la fe
que el 16 log 16 és 64.

825
00:35:43,720 --> 00:35:46,590
I així, de fet, amb aquest simple seny
comprovar, hem confirmat -

826
00:35:46,590 --> 00:35:48,250
però no demostrat formalment -

827
00:35:48,250 --> 00:35:52,800
que el temps de funcionament de la fusió
espècie és de fet n log n.

828
00:35:52,800 --> 00:35:53,790
>> Així que no està malament.

829
00:35:53,790 --> 00:35:57,260
És definitivament millor que el
algorismes que hem vist fins ara, i

830
00:35:57,260 --> 00:36:00,710
és perquè hem aprofitat, un,
una tècnica anomenada recursió.

831
00:36:00,710 --> 00:36:03,880
Però més interessant que això, que
idea de dividir i conquerir.

832
00:36:03,880 --> 00:36:07,460
Un cop més, realment setmanes 0 coses que
fins i tot ara es repeteixi en un

833
00:36:07,460 --> 00:36:08,740
manera més convincent.

834
00:36:08,740 --> 00:36:11,750
>> Ara una mica d'exercici divertit, si vostè té
mai ha fet això - i és probable que

835
00:36:11,750 --> 00:36:14,660
No hi hauria, doncs una espècie de normalitat
la gent no pensa fer-ho.

836
00:36:14,660 --> 00:36:20,650
Però si vaig a google.com i si
Vull aprendre alguna cosa sobre

837
00:36:20,650 --> 00:36:22,356
recursivitat, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [El]

840
00:36:29,058 --> 00:36:32,030
[Més rialles]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Bad broma estenent lentament.

842
00:36:33,385 --> 00:36:34,450
[El]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Per si de cas, que hi és.

844
00:36:36,970 --> 00:36:38,710
Jo no ho lletregi malament,
i aquí està la broma.

845
00:36:38,710 --> 00:36:40,810
Està bé.

846
00:36:40,810 --> 00:36:42,950
Explicar a la gent costat de vostè si
Però no ha fet clic al moment.

847
00:36:42,950 --> 00:36:47,650
Però recursió, més en general, es refereix
per al procés d'una funció de trucada

848
00:36:47,650 --> 00:36:51,430
en si, o més en general, la divisió d'un
problema en alguna cosa que pot ser

849
00:36:51,430 --> 00:36:56,220
resolt poc a poc mitjançant la resolució d'idèntic
problemes representatius.

850
00:36:56,220 --> 00:36:58,400
>> Bé, anem a canviar els engranatges
només per un moment.

851
00:36:58,400 --> 00:37:00,840
Ens agradaria acabar amb certs melodrames,
així que anem a començar a configurar

852
00:37:00,840 --> 00:37:05,870
l'escenari, durant diversos minuts,
en una idea molt simple -

853
00:37:05,870 --> 00:37:07,620
el d'intercanvi de dos elements, no?

854
00:37:07,620 --> 00:37:10,040
Tots aquests algorismes que hem estat
parlant dels últims dos

855
00:37:10,040 --> 00:37:12,420
conferències impliquen algun
tipus d'intercanvi.

856
00:37:12,420 --> 00:37:14,630
Avui en dia es va visualitzar per ells aconseguir
dalt de les seves cadires i

857
00:37:14,630 --> 00:37:18,570
caminant, però en el codi, ho faríem
simplement prendre un element d'un array

858
00:37:18,570 --> 00:37:20,370
i plop en un altre.

859
00:37:20,370 --> 00:37:21,880
>> Llavors, com farem això?

860
00:37:21,880 --> 00:37:24,850
Bé, deixa seguir endavant i escriure
un programa ràpid aquí.

861
00:37:24,850 --> 00:37:31,600
Vaig a seguir endavant i fer
això com el següent.

862
00:37:31,600 --> 00:37:33,910
Diguem que això -

863
00:37:33,910 --> 00:37:38,070
Què volem cridar aquest?

864
00:37:38,070 --> 00:37:38,650
>> En realitat, no.

865
00:37:38,650 --> 00:37:39,420
Permetin-me rebobinat.

866
00:37:39,420 --> 00:37:41,220
Jo no vull fer això
melodrama encara.

867
00:37:41,220 --> 00:37:42,270
Es espatllar la diversió.

868
00:37:42,270 --> 00:37:43,600
Anem a fer-ho al seu lloc.

869
00:37:43,600 --> 00:37:47,430
>> Suposem que vull escriure una mica
programa i que ara abasta la

870
00:37:47,430 --> 00:37:48,700
idea de recursivitat.

871
00:37:48,700 --> 00:37:50,370
Jo com que tinc davant de mi mateix allà.

872
00:37:50,370 --> 00:37:51,420
Vaig a fer el següent.

873
00:37:51,420 --> 00:38:00,220
>> Primer, una ràpida inclouen de sèrie io.h,
així com un include de cs50.h.

874
00:38:00,220 --> 00:38:03,200
I després vaig a seguir endavant
i declarar void main int

875
00:38:03,200 --> 00:38:04,360
en la forma habitual.

876
00:38:04,360 --> 00:38:07,920
Em vaig adonar que he mal anomenat l'arxiu, per la qual cosa
permetin-me afegir una extensió c. aquí, així

877
00:38:07,920 --> 00:38:09,510
que podem compilar correctament.

878
00:38:09,510 --> 00:38:10,970
Inicieu aquesta funció.

879
00:38:10,970 --> 00:38:13,290
>> I la funció que vull escriure, bastant
simplement, és un que demana al

880
00:38:13,290 --> 00:38:16,210
usuari un número i després s'afegeix
tots els números entre els quals

881
00:38:16,210 --> 00:38:19,920
nombre i, per exemple, 0.

882
00:38:19,920 --> 00:38:22,510
Així que primer vaig a seguir endavant
i declarar n int.

883
00:38:22,510 --> 00:38:24,760
A continuació copio un codi que
hem utilitzat durant algun temps.

884
00:38:24,760 --> 00:38:26,660
Mentre que alguna cosa és cert.

885
00:38:26,660 --> 00:38:28,000
Vaig a tornar a això en un moment.

886
00:38:28,000 --> 00:38:29,010
>> Què vull fer?

887
00:38:29,010 --> 00:38:33,460
Vull dir printf positiu
sencer per favor.

888
00:38:33,460 --> 00:38:36,130
I després vaig a
dir n es fa arribar int.

889
00:38:36,130 --> 00:38:38,800
Així que de nou, una mica de codi repetitiu
que hem utilitzat abans.

890
00:38:38,800 --> 00:38:40,810
I jo faré això
mentre que n és menor que 1.

891
00:38:40,810 --> 00:38:44,120
Així que això assegurarà que l'usuari
em dóna un nombre enter positiu.

892
00:38:44,120 --> 00:38:45,490
>> I ara vaig a fer el següent.

893
00:38:45,490 --> 00:38:51,020
Vull sumar tots els números
entre 1 i i n, o 0 i n,

894
00:38:51,020 --> 00:38:52,570
equivalent, per obtenir la suma total.

895
00:38:52,570 --> 00:38:55,100
Per tant el símbol sigma gran
que es pot recordar.

896
00:38:55,100 --> 00:38:59,050
Així que vaig a fer això per primera convocatòria
una funció anomenada sigma,

897
00:38:59,050 --> 00:39:06,030
passant a n, i després em vaig a
printf dir, la resposta està aquí.

898
00:39:06,030 --> 00:39:08,180
>> Així que en resum, ho entenc i
int des de l'usuari.

899
00:39:08,180 --> 00:39:09,280
Em asseguro que és positiu.

900
00:39:09,280 --> 00:39:12,700
Declaro una trucada resposta variable
tipus int i emmagatzemar en ella el retorn

901
00:39:12,700 --> 00:39:15,610
valor de sigma, passant núm com a entrada.

902
00:39:15,610 --> 00:39:17,060
I llavors em imprimeixo la resposta.

903
00:39:17,060 --> 00:39:19,550
>> Desafortunadament, tot i que sona sigma
com una cosa que podria estar en

904
00:39:19,550 --> 00:39:24,040
l'arxiu math.h, la seva declaració,
en realitat no és.

905
00:39:24,040 --> 00:39:24,690
Així que això està bé.

906
00:39:24,690 --> 00:39:26,170
Puc aplicar això a mi mateix.

907
00:39:26,170 --> 00:39:29,160
Vaig a posar en pràctica una funció anomenada
sigma, i va a prendre una

908
00:39:29,160 --> 00:39:29,900
paràmetre -

909
00:39:29,900 --> 00:39:32,100
Anem a trucar a que m, just
pel que és diferent.

910
00:39:32,100 --> 00:39:35,910
I després aquí, jo vaig a dir,
així, si m és menor que 1 - aquesta és una

911
00:39:35,910 --> 00:39:38,180
programa molt interessant.

912
00:39:38,180 --> 00:39:41,700
Així que seguiré endavant i
tornar immediatament 0.

913
00:39:41,700 --> 00:39:45,920
Simplement no té sentit sumar tots
els números entre 1 i m si m

914
00:39:45,920 --> 00:39:48,470
és en si mateixa 0 o negatiu.

915
00:39:48,470 --> 00:39:50,900
>> I després vaig a seguir endavant
i fer-ho molt iterativa.

916
00:39:50,900 --> 00:39:53,090
Vaig a fer aquest tipus de la vella escola,
i jo seguiré endavant

917
00:39:53,090 --> 00:39:57,150
i dir que vaig a
declarar una suma igual a 0.

918
00:39:57,150 --> 00:39:59,630
Llavors em vaig a tenir
un bucle de int -

919
00:39:59,630 --> 00:40:02,820
i m'ho dius a mi fer perquè coincideixi amb la nostra
codi de distribució, pel que té una còpia

920
00:40:02,820 --> 00:40:07,500
a la llar. int i s'obté en un màxim d'1
i és menor que o igual a m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
I dins d'aquest cicle for -

923
00:40:11,430 --> 00:40:12,440
ja gairebé estem allà -

924
00:40:12,440 --> 00:40:15,810
suma s'afegeix més 1.

925
00:40:15,810 --> 00:40:17,670
I després vaig a tornar la suma.

926
00:40:17,670 --> 00:40:19,420
>> Així que vaig fer això ràpidament,
molt cert.

927
00:40:19,420 --> 00:40:22,775
Però, de nou, la funció principal és bastant
senzill, basat en el codi que hem

928
00:40:22,775 --> 00:40:23,190
escrit fins ara.

929
00:40:23,190 --> 00:40:25,610
Utilitza el llaç dual per aconseguir un resultat positiu
int des de l'usuari.

930
00:40:25,610 --> 00:40:29,870
Després pas que int a una nova funció
anomenat sigma, cridant, de nou, n.

931
00:40:29,870 --> 00:40:33,100
I guardo el valor de retorn, la resposta
en el quadre negre actualment

932
00:40:33,100 --> 00:40:35,460
conegut com sigma, en una variable
anomenada resposta.

933
00:40:35,460 --> 00:40:36,580
Després ho imprimeixo.

934
00:40:36,580 --> 00:40:39,090
>> Si ara continuarem la història,
com s'implementa sigma?

935
00:40:39,090 --> 00:40:40,840
Em proposo aplicar la següent.

936
00:40:40,840 --> 00:40:43,560
Primer, una mica de comprovació d'errors
per assegurar-se que l'usuari no és

937
00:40:43,560 --> 00:40:46,480
jugant amb mi i passant
un valor negatiu o 0.

938
00:40:46,480 --> 00:40:49,710
Llavors em declaro una variable anomenada
resumir i posar-lo a 0.

939
00:40:49,710 --> 00:40:55,910
>> I ara començo a passar d'i és igual
1 tot el camí fins i incloent m,

940
00:40:55,910 --> 00:41:00,130
perquè vull incloure tota la
nombres de l'u al m, ambdós inclosos.

941
00:41:00,130 --> 00:41:04,350
I dins d'aquest bucle for, acabo de fer
se suma el que ara és, a més de la

942
00:41:04,350 --> 00:41:08,900
valor de i.

943
00:41:08,900 --> 00:41:10,370
A més, el valor d'i.

944
00:41:10,370 --> 00:41:14,090
>> Com acotació al marge, si no has vist aquesta
abans, hi ha una mica de sucre sintàctica

945
00:41:14,090 --> 00:41:14,870
per aquesta línia.

946
00:41:14,870 --> 00:41:21,120
Puc reescriure això com més iguala I,
només per salvar-me a mi mateix unes poques tecles

947
00:41:21,120 --> 00:41:22,570
i mirar una mica més fresc.

948
00:41:22,570 --> 00:41:23,140
Però això és tot.

949
00:41:23,140 --> 00:41:24,660
És funcionalment el mateix.

950
00:41:24,660 --> 00:41:26,710
>> Per desgràcia, aquest codi de
no va a compilar encara.

951
00:41:26,710 --> 00:41:31,600
Si em quedo fer sigma 0, ho sóc
Em va a cridar a?

952
00:41:31,600 --> 00:41:33,473
Què va a li agrada?

953
00:41:33,473 --> 00:41:35,740
>> AUDIÈNCIA: [inaudible].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Sí, jo no declaro
la funció al capdamunt, no?

955
00:41:37,800 --> 00:41:40,590
C és una mica estúpid, només en aquest
fa el que vostè li diu que faci, i vostè

956
00:41:40,590 --> 00:41:41,880
cal fer-ho en aquest ordre.

957
00:41:41,880 --> 00:41:45,910
I així, si colpeig Introduïu aquí, jo vaig a
rebrà una advertència sobre sigma implícita

958
00:41:45,910 --> 00:41:46,860
declaració.

959
00:41:46,860 --> 00:41:48,120
>> Oh, no és un problema.

960
00:41:48,120 --> 00:41:50,370
Puc pujar al cim, i puc
dir, està bé, espera un minut.

961
00:41:50,370 --> 00:41:54,240
Sigma és una funció que retorna
un enter i s'espera una

962
00:41:54,240 --> 00:41:56,620
int com a entrada, punt i coma.

963
00:41:56,620 --> 00:41:59,550
O podria posar tota la funció
per sobre de principal, però en general, m'agradaria

964
00:41:59,550 --> 00:42:02,260
recomanen contra això, perquè és
bo tenir sempre principal a la part superior per

965
00:42:02,260 --> 00:42:06,310
es pot bussejar en dret i saber el que és un
programa està fent mitjançant la lectura principal primer.

966
00:42:06,310 --> 00:42:07,930
>> Així que ara anem a netejar la pantalla.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Tot sembla anar a la sortida.

969
00:42:10,340 --> 00:42:11,970
Déjame córrer sigma 0.

970
00:42:11,970 --> 00:42:12,770
Entre Positiu.

971
00:42:12,770 --> 00:42:15,580
Vaig a donar-li el nombre
3 Per fer-ho simple.

972
00:42:15,580 --> 00:42:18,710
Així que em de donar 3
més 2 més 1, pel que 6.

973
00:42:18,710 --> 00:42:20,750
Entrar, i de fet tinc 6.

974
00:42:20,750 --> 00:42:21,820
>> Puc fer alguna cosa més gran -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Així com una tangent, jo faré
alguna cosa ridícul com una molt gran

977
00:42:27,690 --> 00:42:30,375
nombre, Oh, que realment va funcionar -

978
00:42:30,375 --> 00:42:31,600
eh, jo no crec que això sigui correcte.

979
00:42:31,600 --> 00:42:32,810
Anem a veure.

980
00:42:32,810 --> 00:42:34,060
Anem realment et metes amb ella.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Això és un problema.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Què està passant?

985
00:42:44,970 --> 00:42:46,050
El codi no és tan dolent.

986
00:42:46,050 --> 00:42:48,470
Segueix sent lineal.

987
00:42:48,470 --> 00:42:50,810
Xiular és un bon efecte, però.

988
00:42:50,810 --> 00:42:52,060
Què està passant?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> No estic segur si he sentit.

991
00:42:55,620 --> 00:42:57,620
Així que resulta - i
això és com un part.

992
00:42:57,620 --> 00:42:59,400
Aquest no és el nucli de la
idea de recursivitat.

993
00:42:59,400 --> 00:43:02,480
Resulta, doncs estic intentant
representar un nombre tan gran, més

994
00:43:02,480 --> 00:43:06,980
probablement està sent mal interpretat
per C com un nombre no positiva,

995
00:43:06,980 --> 00:43:09,980
però el nombre negatiu.

996
00:43:09,980 --> 00:43:12,690
>> No hem parlat d'això, però és
Resulta que hi ha números negatius

997
00:43:12,690 --> 00:43:14,210
en el món, a més
als números positius.

998
00:43:14,210 --> 00:43:16,290
I els mitjans pels quals es pot
representar un nombre negatiu

999
00:43:16,290 --> 00:43:19,530
essencialment, s'utilitza una
mica especial per indicar

1000
00:43:19,530 --> 00:43:20,400
positiu en negatiu.

1001
00:43:20,400 --> 00:43:22,950
És una mica més complex que això,
però aquesta és la idea bàsica.

1002
00:43:22,950 --> 00:43:26,740
>> Així que, lamentablement, si C és confusa 01:00
d'aquests bits com en realitat vol dir,

1003
00:43:26,740 --> 00:43:30,790
oh, aquest és un nombre negatiu, el meu llaç
aquí, per exemple, és en realitat mai

1004
00:43:30,790 --> 00:43:31,740
va a acabar.

1005
00:43:31,740 --> 00:43:33,850
Així que si jo fos realment una mica d'impressió
una i altra vegada, sense

1006
00:43:33,850 --> 00:43:34,650
veure molt.

1007
00:43:34,650 --> 00:43:36,220
Però, de nou, aquest és el punt.

1008
00:43:36,220 --> 00:43:38,590
Això és en realitat una mena de
curiositat intel · lectual que vindrem

1009
00:43:38,590 --> 00:43:39,550
enrere per finalment.

1010
00:43:39,550 --> 00:43:43,400
Però per ara, es tracta d'una correcta
aplicació si suposem que el

1011
00:43:43,400 --> 00:43:45,970
consulta, donarà complerta ints
que caben dins d'ints.

1012
00:43:45,970 --> 00:43:49,370
>> Però jo sostinc que aquest codi, francament,
es podria fer molt més simple.

1013
00:43:49,370 --> 00:43:54,060
Si l'objectiu que ens ocupa és prendre un nombre
com m i sumar tots els

1014
00:43:54,060 --> 00:43:59,510
nombres entre ella i 1, o per contra
entre 1 i que, reclam

1015
00:43:59,510 --> 00:44:03,380
que puc demanar prestat la idea de fusionar
tipus tenia, que estava tenint un problema

1016
00:44:03,380 --> 00:44:05,660
d'aquesta mida i dividint
en una mica més petit.

1017
00:44:05,660 --> 00:44:09,875
Potser no mitjà, però més petit, però
de manera representativa del mateix.

1018
00:44:09,875 --> 00:44:12,130
La mateixa idea, però un problema menor.

1019
00:44:12,130 --> 00:44:15,470
>> Així que estic realment - m'ho dius guardar aquest arxiu
amb un nombre de versió diferent.

1020
00:44:15,470 --> 00:44:17,670
Anem a trucar a aquesta versió
1 en lloc de 0.

1021
00:44:17,670 --> 00:44:20,790
I jo puc dir que en realitat
tornar a implementar això en aquest tipus de

1022
00:44:20,790 --> 00:44:22,160
endimoniada manera.

1023
00:44:22,160 --> 00:44:23,710
>> Vaig a deixar part del seu compte.

1024
00:44:23,710 --> 00:44:27,710
Vaig a dir que si m és menor
que o fins i tot igual a 0 -

1025
00:44:27,710 --> 00:44:29,280
Jo només vaig a ser una mica
més anal aquest moment

1026
00:44:29,280 --> 00:44:30,520
amb el meu comprovació d'errors -

1027
00:44:30,520 --> 00:44:33,190
Vaig a seguir endavant i tornar 0.

1028
00:44:33,190 --> 00:44:34,490
Aquest és arbitrària.

1029
00:44:34,490 --> 00:44:37,500
Estic simplement decidint si l'usuari
em dóna un nombre negatiu, estic

1030
00:44:37,500 --> 00:44:41,490
retornant un 0, i que hauria d'haver llegit
la documentació de més de prop.

1031
00:44:41,490 --> 00:44:42,170
>> Altres vendes -

1032
00:44:42,170 --> 00:44:44,070
compte del que faré.

1033
00:44:44,070 --> 00:44:49,260
La resta vaig a tornar m plus -

1034
00:44:49,260 --> 00:44:51,010
el que és sigma de m?

1035
00:44:51,010 --> 00:44:56,710
Bé, sigma de m + d menys 1,
més minus m 2, més almenys 3 m.

1036
00:44:56,710 --> 00:44:58,030
Jo no vull escriure tot això.

1037
00:44:58,030 --> 00:44:59,120
Per què no acaba d'aclarir?

1038
00:44:59,120 --> 00:45:05,080
Recurrentment em truqui amb una mica
problema més petit, punt i coma,

1039
00:45:05,080 --> 00:45:06,840
i en diuen un dia?

1040
00:45:06,840 --> 00:45:07,040
>> Cert?

1041
00:45:07,040 --> 00:45:10,980
Ara, també, es pot sentir o preocupar
que aquest és un bucle infinit que sóc

1042
00:45:10,980 --> 00:45:15,450
induir, pel que m'estic posant en pràctica
sigma trucant sigma.

1043
00:45:15,450 --> 00:45:20,342
Però això és perfectament correcte, perquè
pensament per davant un afegit que les línies?

1044
00:45:20,342 --> 00:45:22,600
>> AUDIÈNCIA: [inaudible].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23 a 26, que
si és la meva condició.

1046
00:45:25,430 --> 00:45:28,390
Perquè el bo de la
resta aquí, perquè he guardat

1047
00:45:28,390 --> 00:45:31,180
repartint sigma problemes més petits, més petita
problemes, més petit - no és

1048
00:45:31,180 --> 00:45:31,870
la meitat de la mida.

1049
00:45:31,870 --> 00:45:34,380
És només un petit pas més petit,
però això està bé.

1050
00:45:34,380 --> 00:45:38,050
Perquè al final, anem a treballar
el nostre camí a 1 o 0.

1051
00:45:38,050 --> 00:45:41,630
I una vegada que arribem a 0, sigma no és
passant a cridar més.

1052
00:45:41,630 --> 00:45:43,590
Es va a tornar immediatament 0.

1053
00:45:43,590 --> 00:45:47,960
>> Així que l'efecte, si aquest tipus de vent
en la seva ment, és afegir m més

1054
00:45:47,960 --> 00:45:52,740
m menys 1, més m menys 2, més m menys
3, a més de punt, punt, punt, m menys

1055
00:45:52,740 --> 00:45:57,820
m, amb el temps que li dóna 0 i la
efecte és en última instància, per afegir tots

1056
00:45:57,820 --> 00:45:59,070
aquestes coses juntes.

1057
00:45:59,070 --> 00:46:02,380
Així que no tenim, amb la recursivitat,
resolt el problema que

1058
00:46:02,380 --> 00:46:03,470
no podria resoldre abans.

1059
00:46:03,470 --> 00:46:06,840
En efecte, la versió 0 d'aquest, i cada
problema fins a la data, ha estat solucionable

1060
00:46:06,840 --> 00:46:09,980
amb només l'ús de bucles o mentre
bucles o construccions similars.

1061
00:46:09,980 --> 00:46:13,150
>> No obstant això, la recursivitat, m'atreveixo a dir, ens dóna
una manera diferent de pensar sobre

1062
00:46:13,150 --> 00:46:17,010
problemes, pel que si ens poden donar un
problema, el divideix d'alguna cosa

1063
00:46:17,010 --> 00:46:22,340
alguna cosa gran en una cosa una mica
més petita, afirmo que podem solucionar

1064
00:46:22,340 --> 00:46:26,040
potser una mica més elegant en termes
del disseny, amb menys codi,

1065
00:46:26,040 --> 00:46:30,980
i potser resoldre els problemes que
ser més difícil, ja que finalment va a

1066
00:46:30,980 --> 00:46:33,280
veure, la solució purament iterativament.

1067
00:46:33,280 --> 00:46:35,980
>> Però el drama de suspens que vaig fer
vol deixar-nos en aquesta era.

1068
00:46:35,980 --> 00:46:40,720
Deixin-me seguir endavant i obrir
un arxiu des de -

1069
00:46:40,720 --> 00:46:44,300
En realitat, em va deixar anar i
fer això molt ràpid.

1070
00:46:44,300 --> 00:46:46,875
Deixin-me seguir endavant i proposo
el següent.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Entri el codi d'avui és l'arxiu aquí.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Aquest d'aquí, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Així que això és una mica estúpid programa que
Vaig treure fins que pretén fer

1076
00:47:06,260 --> 00:47:06,940
el següent.

1077
00:47:06,940 --> 00:47:10,140
En el principal, primer declara una
int anomenada X i li assigna

1078
00:47:10,140 --> 00:47:11,100
el valor d'1.

1079
00:47:11,100 --> 00:47:13,520
Llavors es declara una i int i
assigna el valor 2.

1080
00:47:13,520 --> 00:47:15,310
Després s'imprimeix el que és x i y.

1081
00:47:15,310 --> 00:47:17,781
Després diu, intercanvi, punt punt punt.

1082
00:47:17,781 --> 00:47:21,670
>> Llavors es diu que està cridant a una funció
anomenada swap, passant x i

1083
00:47:21,670 --> 00:47:24,290
i, la idea que és que s'espera que
x i i tornaran

1084
00:47:24,290 --> 00:47:25,620
diferent, el contrari.

1085
00:47:25,620 --> 00:47:27,110
Llavors diuen va canviar!

1086
00:47:27,110 --> 00:47:28,420
amb un signe d'exclamació.

1087
00:47:28,420 --> 00:47:30,190
Després s'imprimeix x i y.

1088
00:47:30,190 --> 00:47:33,480
>> Però resulta que aquesta mateixa
simple demostració baix

1089
00:47:33,480 --> 00:47:35,570
aquí és en realitat errors.

1090
00:47:35,570 --> 00:47:38,870
Encara estic declarant un temporal
variable i posar temporalment en una

1091
00:47:38,870 --> 00:47:42,010
, Llavors jo estic reassignant
1 el valor de b -

1092
00:47:42,010 --> 00:47:45,080
que se sent raonable, perquè he
guardat una còpia d'una de temp.

1093
00:47:45,080 --> 00:47:48,410
Llavors puc actualitzar b a la igualtat de
el que estava en temp.

1094
00:47:48,410 --> 00:47:51,610
Aquest tipus de joc de la closca de moure una
en b & b en una a través d'aquest

1095
00:47:51,610 --> 00:47:54,360
mitjà-home anomenat temp sent
perfectament raonable.

1096
00:47:54,360 --> 00:47:57,270
>> Però jo sostinc que quan executo aquest
codi, ja que vaig a fer ara -

1097
00:47:57,270 --> 00:47:59,490
m'ho dius a mi anar endavant i enganxar-lo aquí.

1098
00:47:59,490 --> 00:48:01,995
Vaig a trucar a aquest noswap.c.

1099
00:48:01,995 --> 00:48:05,630
I com el seu nom indica, no és
serà un programa correcte.

1100
00:48:05,630 --> 00:48:09,460
Feu noswap. / No swap.

1101
00:48:09,460 --> 00:48:12,110
x és 1, i és 2, l'intercanvi, intercanviar.

1102
00:48:12,110 --> 00:48:14,220
x és 1, i és 2.

1103
00:48:14,220 --> 00:48:16,920
Això és un error fonamental, fins i tot
encara que això sembla perfectament

1104
00:48:16,920 --> 00:48:17,730
raonable per a mi.

1105
00:48:17,730 --> 00:48:21,330
I hi ha una raó, però no estem
va a revelar la raó de moment.

1106
00:48:21,330 --> 00:48:24,610
>> Per ara el segon melodrama que volia
deixar és això, 1:00

1107
00:48:24,610 --> 00:48:27,120
anunci de tipus de bons de descompte.

1108
00:48:27,120 --> 00:48:31,590
La nostra innovació amb fins de dies aquest any
ha provocat un nombre no trivial

1109
00:48:31,590 --> 00:48:33,830
de preguntes, la qual cosa era
no és la nostra intenció.

1110
00:48:33,830 --> 00:48:36,590
La intenció d'aquests bons de descompte,
pel que si vostè fa part del problema

1111
00:48:36,590 --> 00:48:39,850
establir principis, aconseguint així un dia més,
era realment per ajudar a vostès Ajuda

1112
00:48:39,850 --> 00:48:42,420
mateix començament d'hora, més o menys
de l'incentivar vostè.

1113
00:48:42,420 --> 00:48:44,880
Ens ajuda a distribuir la càrrega entre
horari d'oficina millor perquè

1114
00:48:44,880 --> 00:48:45,740
és una espècie de guanyar-guanyar.

1115
00:48:45,740 --> 00:48:48,860
>> Per desgràcia, crec que les meves instruccions
no han estat, fins ara, molt clar, pel

1116
00:48:48,860 --> 00:48:52,230
Vaig tornar aquest cap de setmana i actualitzat
l'especificació en el més gran, més audaç per al text

1117
00:48:52,230 --> 00:48:53,600
explicar bales com aquests.

1118
00:48:53,600 --> 00:48:56,900
I per dir-ho més públicament, per
per defecte, els butlletins de problemes s'han de dijous

1119
00:48:56,900 --> 00:48:58,400
al migdia, pel pla d'estudis.

1120
00:48:58,400 --> 00:49:02,030
Si comença d'hora, acabant part de
el problema plantejat per dimecres a les 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, la part que es refereix a un cupó
codi, la idea és que es pot estendre

1122
00:49:05,170 --> 00:49:07,710
el termini per a la
P posat a divendres.

1123
00:49:07,710 --> 00:49:10,890
És a dir, poc fos una petita part de la P
establir respecte al que normalment és el

1124
00:49:10,890 --> 00:49:13,200
problema més gran, i vostè compra
mateix un dia més.

1125
00:49:13,200 --> 00:49:15,190
Un cop més, s'arriba a pensar en
el conjunt de problemes, que

1126
00:49:15,190 --> 00:49:16,380
les hores d'oficina abans.

1127
00:49:16,380 --> 00:49:20,670
Però el problema segueix sent el codi de cupó
necessari, encara que no els posis.

1128
00:49:20,670 --> 00:49:23,340
>> Però el més convincent és aquest.

1129
00:49:23,340 --> 00:49:26,520
(Xiuxiueig) I aquesta gent deixant
d'hora van a penedir.

1130
00:49:26,520 --> 00:49:28,620
Com que són les persones al balcó.

1131
00:49:28,620 --> 00:49:32,510
Demano disculpes per endavant a les persones en
la balconada per raons que seran

1132
00:49:32,510 --> 00:49:33,920
esborrar en un moment.

1133
00:49:33,920 --> 00:49:37,050
>> Així que tenim la sort de tenir un
L'excap d'ensenyament dels becaris en CS50

1134
00:49:37,050 --> 00:49:39,302
una companyia anomenada dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Tenen molt generosament donat un
codi de cupó aquí per a aquest espai,

1136
00:49:45,500 --> 00:49:48,180
que depèn de la
habituals a 2 gigabytes.

1137
00:49:48,180 --> 00:49:51,740
Així que el que jo pensava que faríem en aquest
nota final és fer una mica d'un sorteig,

1138
00:49:51,740 --> 00:49:55,380
pel que en un moment, anem a revelar
el guanyador i que té un cupó

1139
00:49:55,380 --> 00:49:57,980
codi que després es pot anar al seu
lloc web, escriure, i voila, obtenir un

1140
00:49:57,980 --> 00:50:01,370
molt més espai Dropbox per a la seva
aparell i per als seus arxius personals.

1141
00:50:01,370 --> 00:50:05,690
>> I en primer lloc, que li agradaria participar
en aquest dibuix?

1142
00:50:05,690 --> 00:50:09,630
Bé, ara que ho fa encara més divertit.

1143
00:50:09,630 --> 00:50:14,010
La persona que rep aquest 25-gigabyte
codi de descompte - que és molt

1144
00:50:14,010 --> 00:50:16,150
més convincent que el difunt
dia ara, potser -

1145
00:50:16,150 --> 00:50:20,620
és el que està assegut al cim d'una
coixí del seient per sota de la qual hi ha

1146
00:50:20,620 --> 00:50:21,620
que el codi de cupó.

1147
00:50:21,620 --> 00:50:23,480
Ara pot mirar sota
el coixí del seient.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [REPRODUIR VIDEO]

1150
00:50:29,680 --> 00:50:31,620
>> -Un, dos, tres.

1151
00:50:31,620 --> 00:50:35,015
>> [CRIDA]

1152
00:50:35,015 --> 00:50:35,985
>> -Tens un cotxe!

1153
00:50:35,985 --> 00:50:36,670
Vostè aconsegueix un cotxe!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Veurem
que dimecres.

1155
00:50:37,970 --> 00:50:38,904
>> -Tens un cotxe!

1156
00:50:38,904 --> 00:50:39,371
Vostè aconsegueix un cotxe!

1157
00:50:39,371 --> 00:50:40,305
Vostè aconsegueix un cotxe!

1158
00:50:40,305 --> 00:50:41,706
Vostè aconsegueix un cotxe!

1159
00:50:41,706 --> 00:50:43,107
Vostè aconsegueix un cotxe!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: gent Balcó, veuen
aquí baix a la part davantera,

1161
00:50:45,530 --> 00:50:46,866
on tenim extres.

1162
00:50:46,866 --> 00:50:50,282
>> -Tothom té un cotxe!

1163
00:50:50,282 --> 00:50:52,234
Tothom té un cotxe!

1164
00:50:52,234 --> 00:50:52,722
>> [FI REPRODUCCIÓ DE VÍDEO]

1165
00:50:52,722 --> 00:50:54,590
>> NARRADOR: En la següent CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> ALTAVEU 5: Oh, Déu meu Déu meu Déu meu Déu meu
caram caram caram caram caram caram -

1167
00:51:00,374 --> 00:51:02,106
>> [JOCS ukelele]