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

2
00:00:00,488 --> 00:00:10,800
>> [REPRODUCCIÓN DE MÚSICA]

3
00:00:10,800 --> 00:00:13,500
DAVID MALAN: Muy bien.

4
00:00:13,500 --> 00:00:14,670
Muy bien, bienvenido.

5
00:00:14,670 --> 00:00:18,120
Así que esta es la Semana 4, el comienzo
de los mismos, ya.

6
00:00:18,120 --> 00:00:21,320
¿Y te recuerdo que la semana pasada, pusimos
codificar un lado por un poco

7
00:00:21,320 --> 00:00:24,240
y empezamos a hablar un poco más
de alto nivel, por cosas como

8
00:00:24,240 --> 00:00:28,130
búsqueda y ordenación, que a pesar de
las ideas un tanto simples, son

9
00:00:28,130 --> 00:00:31,840
representante de una clase de problemas
usted comenzará a resolver todo

10
00:00:31,840 --> 00:00:34,820
a medida que empiezas a pensar en definitiva
proyectos y soluciones interesantes le

11
00:00:34,820 --> 00:00:36,760
podría tener problemas del mundo real.

12
00:00:36,760 --> 00:00:39,490
Ahora especie de burbuja fue uno de los más sencillos
este tipo de algoritmos, y que

13
00:00:39,490 --> 00:00:42,900
trabajado por tener estos pequeños números
en una lista o en un tipo de matriz de

14
00:00:42,900 --> 00:00:46,530
burbuja de su camino a la cima, y ​​el
grandes números de mover su camino hasta

15
00:00:46,530 --> 00:00:47,930
Al final de esa lista.

16
00:00:47,930 --> 00:00:50,650
>> Y recordemos que pudimos visualizar
ordenamiento de burbuja un poco

17
00:00:50,650 --> 00:00:52,310
algo como esto.

18
00:00:52,310 --> 00:00:53,640
Así que déjame ir adelante y haga clic en Iniciar.

19
00:00:53,640 --> 00:00:55,350
He preseleccionado especie de burbuja.

20
00:00:55,350 --> 00:00:58,920
Y si usted recuerda que el azul más alto
líneas representan números grandes, pequeñas

21
00:00:58,920 --> 00:01:03,300
líneas azules representan los números pequeños, como
pasamos por esto una y otra vez y

22
00:01:03,300 --> 00:01:07,680
de nuevo, la comparación de dos bares al lado de cada uno
otra de color rojo, que vamos a cambiar la

23
00:01:07,680 --> 00:01:11,010
más grande y la más pequeña, si
que están fuera de orden.

24
00:01:11,010 --> 00:01:14,150
>> Así que esto va a seguir y seguir y seguir
, y usted verá que la mayor

25
00:01:14,150 --> 00:01:16,700
elementos están haciendo su camino a la
derecha, y los elementos más pequeños son

26
00:01:16,700 --> 00:01:17,900
hacer su camino a la izquierda.

27
00:01:17,900 --> 00:01:21,380
Pero empezamos a cuantificar
la eficiencia, la

28
00:01:21,380 --> 00:01:22,970
calidad de este algoritmo.

29
00:01:22,970 --> 00:01:25,200
Y dijimos que en el peor
caso, este algoritmo tomó

30
00:01:25,200 --> 00:01:27,940
más o menos la cantidad de pasos?

31
00:01:27,940 --> 00:01:28,980
>> Así que n al cuadrado.

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

33
00:01:30,402 --> 00:01:31,650
>> AUDIENCIA: Número de elementos.

34
00:01:31,650 --> 00:01:32,790
>> DAVID MALAN: Así fue la n
número de elementos.

35
00:01:32,790 --> 00:01:33,730
Así que vamos a hacer esto con frecuencia.

36
00:01:33,730 --> 00:01:36,650
Cada vez que queremos hablar sobre el tamaño
de un problema o el tamaño de un

37
00:01:36,650 --> 00:01:39,140
entrada, o la cantidad de tiempo que tarda
para producir una salida, sólo tendremos que

38
00:01:39,140 --> 00:01:41,610
generalizada lo
la entrada es como n.

39
00:01:41,610 --> 00:01:45,970
Así que de vuelta en la semana 0, el número de páginas
en la guía telefónica era n.

40
00:01:45,970 --> 00:01:47,550
El número de estudiantes
en la habitación era n.

41
00:01:47,550 --> 00:01:49,630
Así que aquí, también, estamos siguiendo
ese patrón.

42
00:01:49,630 --> 00:01:52,800
>> Ahora n al cuadrado no es particularmente
rápido, por lo que tratamos de hacer mejor.

43
00:01:52,800 --> 00:01:55,970
Así que miramos un par de
otros algoritmos, entre los cuales

44
00:01:55,970 --> 00:01:57,690
fueron ordenación por selección.

45
00:01:57,690 --> 00:01:59,180
Así ordenación por selección fue
un poco diferente.

46
00:01:59,180 --> 00:02:03,130
Era casi más sencillo, me atrevo a decir,
por el que empecé en el inicio de la

47
00:02:03,130 --> 00:02:06,740
Lista de nuestros voluntarios y acabo de nuevo
y una y otra vez fue a través de

48
00:02:06,740 --> 00:02:10,060
la lista, arrancarse el más pequeño
elemento a la vez y ponerlo o

49
00:02:10,060 --> 00:02:13,040
ella en el principio de la lista.

50
00:02:13,040 --> 00:02:16,410
>> Pero también esto, una vez que comenzó a pensar
a través de las matemáticas y más grande

51
00:02:16,410 --> 00:02:19,860
imagen, pensé en cuántas veces
Yo iba de ida y vuelta y de vuelta

52
00:02:19,860 --> 00:02:24,090
adelante y hacia atrás, dijimos en el peor de los casos,
ordenación por selección también era qué?

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

54
00:02:24,960 --> 00:02:27,490
Ahora en el mundo real, podría
en realidad ser marginalmente más rápido.

55
00:02:27,490 --> 00:02:30,620
Porque de nuevo, yo no tengo que seguir
dar marcha atrás una vez que había ordenado la

56
00:02:30,620 --> 00:02:31,880
elementos más pequeños.

57
00:02:31,880 --> 00:02:35,090
Pero si lo pensamos muy grandes de n, y
si usted suerte de hacer la matemática como

58
00:02:35,090 --> 00:02:39,170
Lo hice en el tablero, con el n al cuadrado
menos algo, todo lo demás

59
00:02:39,170 --> 00:02:41,850
además del N al cuadrado, una vez N
se pone muy grande, ¿no

60
00:02:41,850 --> 00:02:42,850
Realmente importa tanto.

61
00:02:42,850 --> 00:02:45,470
Así como los informáticos, que tipo de
hacer la vista gorda a la más pequeña

62
00:02:45,470 --> 00:02:49,220
factores y centrarse sólo en el factor de
una expresión que se va a hacer

63
00:02:49,220 --> 00:02:50,330
la mayor diferencia.

64
00:02:50,330 --> 00:02:52,840
>> Bueno, por último, buscamos
en la ordenación por inserción.

65
00:02:52,840 --> 00:02:56,620
Y esta fue similar en espíritu, pero
en lugar de ir a través de forma iterativa y

66
00:02:56,620 --> 00:03:01,250
seleccionar el elemento de uno más pequeño a un
tiempo, en vez tomé la mano que me

67
00:03:01,250 --> 00:03:04,070
fue tratado, y decidí, todo
derecho, usted pertenece aquí.

68
00:03:04,070 --> 00:03:06,160
Luego pasé al siguiente elemento
y decidió que él o

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

70
00:03:07,470 --> 00:03:08,810
Y luego me mudé y sigue.

71
00:03:08,810 --> 00:03:11,780
Y yo fuerzas para, en el camino,
cambiar estos chicos con el fin de

72
00:03:11,780 --> 00:03:13,030
hacer espacio para ellos.

73
00:03:13,030 --> 00:03:16,880
Así que fue una especie de reversión mentales
de ordenación por selección que

74
00:03:16,880 --> 00:03:18,630
llamada ordenación por inserción.

75
00:03:18,630 --> 00:03:20,810
>> Así que estos temas que se produzca
en el mundo real.

76
00:03:20,810 --> 00:03:23,640
Hace apenas unos años, cuando un determinado
senador fue candidato a la presidencia,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, en el momento en que el director general de
Google, en realidad tuvo la oportunidad

78
00:03:27,160 --> 00:03:28,040
para entrevistarlo.

79
00:03:28,040 --> 00:03:32,010
Y pensamos que sería buena idea compartir esta YouTube
cortar para usted aquí, si pudiéramos subir

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

81
00:03:32,950 --> 00:03:39,360
>> [REPRODUCCIÓN DE VÍDEO]

82
00:03:39,360 --> 00:03:44,620
>> -Ahora, el senador, estás aquí en Google,
y me gusta pensar en la presidencia

83
00:03:44,620 --> 00:03:46,042
como una entrevista de trabajo.

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

85
00:03:47,770 --> 00:03:50,800
>> -Ahora es difícil de conseguir
un trabajo como presidente.

86
00:03:50,800 --> 00:03:52,480
Y usted va a través de
los rigores ahora.

87
00:03:52,480 --> 00:03:54,330
También es difícil de conseguir un trabajo en Google.

88
00:03:54,330 --> 00:03:59,610
Tenemos preguntas y le pedimos
nuestras preguntas de los candidatos.

89
00:03:59,610 --> 00:04:02,250
Y ésta es de Larry Schwimmer.

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

91
00:04:05,325 --> 00:04:06,400
-Ustedes piensan que estoy bromeando?

92
00:04:06,400 --> 00:04:08,750
Está justo aquí.

93
00:04:08,750 --> 00:04:12,110
¿Cuál es la forma más eficiente de
ordenar un millón de enteros de dos bits?

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

95
00:04:15,810 --> 00:04:18,260
>> -Bueno, eh -

96
00:04:18,260 --> 00:04:19,029
>> -Lo siento.

97
00:04:19,029 --> 00:04:19,745
Tal vez debería -

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

99
00:04:21,000 --> 00:04:21,470
>> -Eso no es un -

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

101
00:04:22,185 --> 00:04:25,328
>> -Creo que el ordenamiento de burbuja haría
ser el camino equivocado.

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

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

104
00:04:28,510 --> 00:04:31,211
>> -Vamos, ¿quién le dijo eso?

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

106
00:04:32,155 --> 00:04:33,350
>> [VIDEO PLAYBACK FIN]

107
00:04:33,350 --> 00:04:35,070
>> DAVID MALAN: Así que ahí lo tienen.

108
00:04:35,070 --> 00:04:39,600
Así que empezamos a cuantificar estas corriendo
veces, por así decirlo, con algo

109
00:04:39,600 --> 00:04:43,480
llamado notación asintótica, que es
sólo se refiere a nuestra especie de giro

110
00:04:43,480 --> 00:04:47,420
la vista gorda a los factores más pequeños y
sólo mirar el tiempo de funcionamiento,

111
00:04:47,420 --> 00:04:51,250
el rendimiento de estos algoritmos,
a medida que n se pone muy grande con el tiempo.

112
00:04:51,250 --> 00:04:55,110
Y por eso hemos introducido gran O. Y gran O
representado algo que pensamos

113
00:04:55,110 --> 00:04:57,000
de como un límite superior.

114
00:04:57,000 --> 00:04:59,570
Y en realidad, Barry, ¿podemos bajar
que el micrófono un poco?

115
00:04:59,570 --> 00:05:01,040
>> Pensamos que es una cota superior.

116
00:05:01,040 --> 00:05:04,710
Así que gran O de n al cuadrado significa que en
el peor de los casos, algo así como

117
00:05:04,710 --> 00:05:07,780
ordenación por selección tomaría
n al cuadrado pasos.

118
00:05:07,780 --> 00:05:10,310
O algo así como la ordenación por inserción
sería n al cuadrado pasos.

119
00:05:10,310 --> 00:05:15,150
Ahora para algo como la inserción
especie, lo que fue el peor de los casos?

120
00:05:15,150 --> 00:05:18,200
Dada una matriz, lo que es lo peor
posible escenario que le puede resultar

121
00:05:18,200 --> 00:05:20,650
hecho frente con?

122
00:05:20,650 --> 00:05:21,860
>> Es totalmente al revés, ¿no?

123
00:05:21,860 --> 00:05:24,530
Porque si es totalmente al revés,
usted tiene que hacer un montón de trabajo.

124
00:05:24,530 --> 00:05:26,420
Porque si usted es totalmente al revés,
usted va a encontrar el

125
00:05:26,420 --> 00:05:28,840
mayor elemento de aquí, aunque
pertenece allí.

126
00:05:28,840 --> 00:05:31,140
Así que vas a decir, de acuerdo, en
este momento en el tiempo, que es de aquí,

127
00:05:31,140 --> 00:05:32,310
así que lo deje en paz.

128
00:05:32,310 --> 00:05:35,425
>> Entonces te das cuenta, oh, maldita sea, tengo que
mover este elemento ligeramente más pequeño a

129
00:05:35,425 --> 00:05:36,470
la izquierda de usted.

130
00:05:36,470 --> 00:05:38,770
Entonces tengo que hacer eso de nuevo
y una y otra vez.

131
00:05:38,770 --> 00:05:41,410
Y si caminaba de ida y vuelta, que
sería una especie de sentir el desempeño de

132
00:05:41,410 --> 00:05:45,540
que algoritmo, porque constantemente estoy
arrastrando los pies a todos los demás en la

133
00:05:45,540 --> 00:05:46,510
matriz para hacer espacio para él.

134
00:05:46,510 --> 00:05:47,750
Así que ese es el peor de los casos.

135
00:05:47,750 --> 00:05:48,570
>> Por el contrario -

136
00:05:48,570 --> 00:05:50,320
y éste era un cliffhanger última vez -

137
00:05:50,320 --> 00:05:54,065
decíamos que la ordenación por inserción
era un omega de qué?

138
00:05:54,065 --> 00:05:57,530
¿Cuál es el mejor de los casos en ejecución
momento de la ordenación por inserción?

139
00:05:57,530 --> 00:05:58,520
Así que en realidad es n.

140
00:05:58,520 --> 00:06:00,980
Ese fue el espacio en blanco que dejamos
en el tablero de la última vez.

141
00:06:00,980 --> 00:06:03,160
>> Y es el omega de n porque ¿por qué?

142
00:06:03,160 --> 00:06:06,630
Pues bien, en el mejor de los casos, lo que es
ordenación por inserción va a ser entregado?

143
00:06:06,630 --> 00:06:09,830
Bueno, una lista que está completamente ordenada
Ya, un mínimo de trabajo para hacer.

144
00:06:09,830 --> 00:06:12,460
Pero lo que es bueno de ordenación por inserción
es que, ya que comienza aquí y

145
00:06:12,460 --> 00:06:15,340
Decide, oh, eres el número
uno, ustedes pertenecen aquí.

146
00:06:15,340 --> 00:06:16,970
¡Oh, qué buena fortuna.

147
00:06:16,970 --> 00:06:17,740
>> Usted es el número dos.

148
00:06:17,740 --> 00:06:19,030
También perteneces aquí.

149
00:06:19,030 --> 00:06:21,010
Número tres, mejor aún,
perteneces aquí.

150
00:06:21,010 --> 00:06:25,210
Tan pronto como se llega al final de la
lista, por la ordenación por inserción es pseudocódigo

151
00:06:25,210 --> 00:06:28,010
que caminamos a través verbalmente
la última vez, ya está hecho.

152
00:06:28,010 --> 00:06:32,790
Pero ordenación por selección, por el contrario,
mantenido haciendo qué?

153
00:06:32,790 --> 00:06:35,260
>> Siguió su camino a través de la lista
una y otra vez y otra vez.

154
00:06:35,260 --> 00:06:39,160
Porque la idea clave que sólo había
una vez que has mirado todo el camino a la

155
00:06:39,160 --> 00:06:42,500
final de la lista puede estar seguro
que el elemento que ha seleccionado se

156
00:06:42,500 --> 00:06:45,560
de hecho el elemento actualmente más pequeño.

157
00:06:45,560 --> 00:06:48,920
Así que estos diferentes modelos mentales terminan
cediendo algunos muy real

158
00:06:48,920 --> 00:06:53,130
diferencias para nosotros, así como ellos
asintóticas diferencias teóricas.

159
00:06:53,130 --> 00:06:56,910
>> Así que para recapitular, pues, gran O de n
cuadrado, hemos visto unos pocos,

160
00:06:56,910 --> 00:06:58,350
algoritmos hasta ahora.

161
00:06:58,350 --> 00:06:59,580
Gran O del n?

162
00:06:59,580 --> 00:07:02,870
¿Qué es un algoritmo que podría
decirse que gran O de n?

163
00:07:02,870 --> 00:07:06,930
En el peor de los casos, se necesita
una serie lineal de pasos.

164
00:07:06,930 --> 00:07:07,810
>> Aceptar, búsqueda lineal.

165
00:07:07,810 --> 00:07:10,470
Y en el peor de los casos, ¿dónde está el
elemento que está buscando cuando

166
00:07:10,470 --> 00:07:12,950
la aplicación de búsqueda lineal?

167
00:07:12,950 --> 00:07:14,680
>> Aceptar, en el peor de los casos,
ni siquiera existe.

168
00:07:14,680 --> 00:07:17,000
O en el segundo peor de los casos, es
todo el camino al final, que es

169
00:07:17,000 --> 00:07:18,880
más-o-menos una diferencia de un solo paso.

170
00:07:18,880 --> 00:07:21,180
Así que al final de la día,
podemos decir que es lineal.

171
00:07:21,180 --> 00:07:23,910
Big O de n seria búsqueda lineal,
porque en el peor de los casos, la

172
00:07:23,910 --> 00:07:26,610
elemento ni siquiera existe o que es
todo el camino al final.

173
00:07:26,610 --> 00:07:29,370
>> Bueno, gran O de registro de n.

174
00:07:29,370 --> 00:07:32,760
No hablamos en detalle sobre
esto, pero hemos visto esto antes.

175
00:07:32,760 --> 00:07:36,840
¿Qué pasa en la llamada logarítmica
tiempo, en el peor de los casos?

176
00:07:36,840 --> 00:07:38,500
>> Sí, por lo que la búsqueda binaria.

177
00:07:38,500 --> 00:07:42,930
Y la búsqueda binaria en el peor de los casos
podría tener el elemento en algún lugar

178
00:07:42,930 --> 00:07:45,640
el medio, o en algún lugar
dentro de la matriz.

179
00:07:45,640 --> 00:07:48,040
Pero sólo se encuentra una vez que
dividir la lista en dos, en

180
00:07:48,040 --> 00:07:48,940
un medio, en un medio, en un medio.

181
00:07:48,940 --> 00:07:50,200
Y luego voila, está ahí.

182
00:07:50,200 --> 00:07:52,500
O, de nuevo, peor de los casos,
ni siquiera existe.

183
00:07:52,500 --> 00:07:56,770
Pero usted no sabe que no está allí
hasta que se llegue a esa especie de última

184
00:07:56,770 --> 00:08:00,470
abajo hacia la mayoría de los elementos de reducir a la mitad
y reducir a la mitad y la reducción a la mitad.

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

186
00:08:01,400 --> 00:08:03,540
Así que pudimos gran O de 2, gran O de 3.

187
00:08:03,540 --> 00:08:06,260
Cada vez que quieres es simplemente un número constante,
que sólo una especie de sólo simplificamos

188
00:08:06,260 --> 00:08:07,280
que, como gran O de 1.

189
00:08:07,280 --> 00:08:10,440
Aunque si de manera realista, toma
2 o incluso 100 pasos, si se trata de un

190
00:08:10,440 --> 00:08:13,680
número constante de pasos,
nos limitamos a decir gran O de 1.

191
00:08:13,680 --> 00:08:15,930
¿Qué es un algoritmo que es
en gran O de 1?

192
00:08:15,930 --> 00:08:18,350
>> AUDIENCIA: Encontrar la longitud
de una variable.

193
00:08:18,350 --> 00:08:21,090
>> DAVID MALAN: Encontrar el
longitud de una variable?

194
00:08:21,090 --> 00:08:23,870
>> AUDIENCIA: No, la longitud
si ya está solucionado.

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

196
00:08:24,160 --> 00:08:27,850
Aceptar, por lo que encontrar la longitud de algo
si la longitud de que algo, como

197
00:08:27,850 --> 00:08:30,020
una matriz, se almacena en una variable.

198
00:08:30,020 --> 00:08:33,380
Debido a que sólo se puede leer la variable,
o imprimir la variable o

199
00:08:33,380 --> 00:08:34,960
sólo en general acceder a esa variable.

200
00:08:34,960 --> 00:08:37,299
Y voila, eso toma tiempo constante.

201
00:08:37,299 --> 00:08:38,909
>> Por el contrario, piense de nuevo a cero.

202
00:08:38,909 --> 00:08:42,460
Piense de nuevo a la primera semana de C,
llamando simplemente printf e impresión

203
00:08:42,460 --> 00:08:46,240
algo en la pantalla es sin duda
constante de tiempo, ya que sólo se necesita

204
00:08:46,240 --> 00:08:50,880
cierto número de ciclos de CPU para mostrar
que el texto en la pantalla.

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

206
00:08:52,720 --> 00:08:56,430
¿Cómo más podríamos modelar el
rendimiento de printf?

207
00:08:56,430 --> 00:09:00,420
¿Alguien quisiera estar en desacuerdo, que
tal vez no es realmente constante de tiempo?

208
00:09:00,420 --> 00:09:03,600
¿En qué correr el poderío de printf sentido
tiempo, en realidad la impresión de una cadena en

209
00:09:03,600 --> 00:09:05,580
la pantalla, sea algo
que no sea constante.

210
00:09:05,580 --> 00:09:07,860
>> AUDIENCIA: [inaudible].

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

212
00:09:08,230 --> 00:09:09,300
Así que depende de nuestra perspectiva.

213
00:09:09,300 --> 00:09:13,390
Si realmente pensamos en la entrada
printf como la cadena y

214
00:09:13,390 --> 00:09:16,380
Por lo tanto, medimos el tamaño de ese
de entrada por su longitud - así que vamos a llamar

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

216
00:09:17,780 --> 00:09:21,990
podría decirse que, printf es en sí misma gran O de n
porque va a llevarte n pasos

217
00:09:21,990 --> 00:09:24,750
para imprimir cada uno de los N
caracteres, más probable.

218
00:09:24,750 --> 00:09:27,730
Al menos en la medida en que suponemos
que tal vez se trata de utilizar un bucle for

219
00:09:27,730 --> 00:09:28,560
debajo de la capucha.

220
00:09:28,560 --> 00:09:30,860
>> Pero tendríamos que mirar ese
código para entenderlo mejor.

221
00:09:30,860 --> 00:09:33,650
Y, en efecto, una vez que ustedes empezar
el análisis de sus propios algoritmos, usted

222
00:09:33,650 --> 00:09:34,900
literalmente hacer precisamente eso.

223
00:09:34,900 --> 00:09:37,765
Una especie de globo ocular de su código y pensar
sobre - todo bien, tengo este bucle

224
00:09:37,765 --> 00:09:41,870
aquí o tengo bucles anidados aquí,
eso va a hacer las cosas n n veces,

225
00:09:41,870 --> 00:09:46,050
y se puede ordenar de razonar su camino
a través del código, incluso si es

226
00:09:46,050 --> 00:09:47,980
pseudocódigo y código no real.

227
00:09:47,980 --> 00:09:49,730
>> ¿Qué pasa con el omega de n al cuadrado?

228
00:09:49,730 --> 00:09:53,582
¿Qué era un algoritmo que, en el mejor
caso, todavía tardó n al cuadrado pasos?

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

230
00:09:54,014 --> 00:09:54,880
>> AUDIENCIA: [inaudible].

231
00:09:54,880 --> 00:09:55,900
>> DAVID MALAN: Así ordenación por selección.

232
00:09:55,900 --> 00:09:59,150
Porque en ese problema realmente reducida
al hecho de que una vez más, no lo sé

233
00:09:59,150 --> 00:10:02,600
He encontrado la corriente más pequeña hasta
He comprobado todos los elementos maldito.

234
00:10:02,600 --> 00:10:08,050
Así omega de, por ejemplo, n, que
sólo se le ocurrió una.

235
00:10:08,050 --> 00:10:09,300
La ordenación por inserción.

236
00:10:09,300 --> 00:10:12,370
Si la lista pasa a ser ordenados
Ya, en el mejor de los casos sólo tenemos

237
00:10:12,370 --> 00:10:15,090
para hacer un pase a través de él,
momento en el que estamos seguros.

238
00:10:15,090 --> 00:10:17,890
Y luego de que se puede decir
a ser lineal, sin duda.

239
00:10:17,890 --> 00:10:20,570
>> ¿Qué pasa con el omega de 1?

240
00:10:20,570 --> 00:10:23,790
¿Cuál es, en el mejor de los casos, podría tomar
un número constante de pasos?

241
00:10:23,790 --> 00:10:27,220
Así que la búsqueda lineal, si usted acaba de tener suerte
y el elemento que está buscando

242
00:10:27,220 --> 00:10:31,000
es justo al principio de la lista,
si es ahí donde usted está comenzando su

243
00:10:31,000 --> 00:10:33,070
recorrido lineal de esa lista.

244
00:10:33,070 --> 00:10:35,180
>> Y esto es verdad de un
número de cosas.

245
00:10:35,180 --> 00:10:37,660
Por ejemplo, incluso binario
búsqueda es el omega de 1.

246
00:10:37,660 --> 00:10:40,310
Porque lo que si usted consigue realmente maldito
suerte y justo-DAB en el centro de

247
00:10:40,310 --> 00:10:42,950
la matriz es el número
que está buscando?

248
00:10:42,950 --> 00:10:45,730
Así que usted puede tener suerte allí, también.

249
00:10:45,730 --> 00:10:49,190
>> Éste, por último, el omega de n log n.

250
00:10:49,190 --> 00:10:52,573
Entonces n log n, no lo hicimos realmente
hablar todavía, pero -

251
00:10:52,573 --> 00:10:53,300
>> AUDIENCIA: Combinar tipo?

252
00:10:53,300 --> 00:10:53,960
>> DAVID MALAN: Combinar especie.

253
00:10:53,960 --> 00:10:56,920
Ese fue el drama de suspenso de la última vez,
donde nos propusimos, y nos mostramos

254
00:10:56,920 --> 00:10:58,600
visualmente, que hay algoritmos.

255
00:10:58,600 --> 00:11:02,470
Y combinar especie de sólo uno de estos
algoritmo que es fundamentalmente más rápido

256
00:11:02,470 --> 00:11:03,450
que algunos de estos otros tipos.

257
00:11:03,450 --> 00:11:07,800
De hecho, fusionar corta es no sólo en el
mejor de los casos n log n, en el peor de los casos

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

259
00:11:09,460 --> 00:11:14,540
Y cuando usted tiene esta coincidencia de
omega y gran O de ser la misma cosa?

260
00:11:14,540 --> 00:11:17,310
De hecho, podemos describir eso como lo que es
llamada theta, aunque es un

261
00:11:17,310 --> 00:11:18,220
poco menos común.

262
00:11:18,220 --> 00:11:21,730
Pero eso sólo significa que los dos límites,
en este caso, son la misma.

263
00:11:21,730 --> 00:11:25,770
>> Así fusionar especie, lo que hace este
realmente se reducen a por nosotros?

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

265
00:11:27,000 --> 00:11:30,340
Déjame sacar otra animación que
que no nos fijamos en la última vez.

266
00:11:30,340 --> 00:11:33,390
Éste, misma idea, pero
que es un poco más grande.

267
00:11:33,390 --> 00:11:36,160
Y yo voy a seguir adelante y señalar
primero - tenemos la ordenación por inserción en

268
00:11:36,160 --> 00:11:39,410
la parte superior izquierda, a continuación, ordenación por selección,
ordenamiento de burbuja, un par de otros tipos -

269
00:11:39,410 --> 00:11:42,670
Shell y rápida - que no hemos hablado
aproximadamente, y el montón y fusionar especie.

270
00:11:42,670 --> 00:11:47,090
>> Así, al menos, tratar de enfocar sus ojos en
los tres primeros de la izquierda y luego

271
00:11:47,090 --> 00:11:49,120
fusionar especie cuando hago clic en
esta flecha verde.

272
00:11:49,120 --> 00:11:51,900
Pero voy a dejar que todos ellos corren, sólo para
le dará una idea de la diversidad de

273
00:11:51,900 --> 00:11:53,980
algoritmos que existen en el mundo.

274
00:11:53,980 --> 00:11:56,180
Voy a dejar que este plazo
por tan sólo unos segundos.

275
00:11:56,180 --> 00:11:59,640
Y si te enfocas tus ojos - elegir una
algoritmo, se centran en ella sólo por un

276
00:11:59,640 --> 00:12:02,970
segundo - usted comenzará a ver el
patrón que está la aplicación.

277
00:12:02,970 --> 00:12:04,530
>> Combinar clase, aviso, se hace.

278
00:12:04,530 --> 00:12:06,430
Pila de clasificación, ordenación rápida, cáscara -

279
00:12:06,430 --> 00:12:09,480
por lo que parece que presentamos los tres
peores algoritmos de semana pasado.

280
00:12:09,480 --> 00:12:12,960
Pero eso es bueno que estamos aquí hoy para
mira merge sort, el cual es uno de

281
00:12:12,960 --> 00:12:16,500
los más fáciles es a la vista, incluso
aunque probablemente se doblará tu mente

282
00:12:16,500 --> 00:12:17,490
sólo un poco.

283
00:12:17,490 --> 00:12:21,130
Aquí podemos ver hasta qué punto
ordenación por selección es una mierda.

284
00:12:21,130 --> 00:12:24,600
>> Pero por el otro lado, es
muy fácil de implementar.

285
00:12:24,600 --> 00:12:28,160
Y tal vez para el conjunto P 3, esa es una de las
algoritmos que eligió para implementar

286
00:12:28,160 --> 00:12:28,960
para la edición estándar.

287
00:12:28,960 --> 00:12:30,970
Perfectamente bien, perfectamente correcta.

288
00:12:30,970 --> 00:12:35,210
>> Pero una vez más, a medida que n se hace grande, si usted
optar por aplicar un algoritmo más rápido

289
00:12:35,210 --> 00:12:39,020
como la combinación de clase, las probabilidades están en mayor y
insumos de mayor tamaño, su código es sólo

290
00:12:39,020 --> 00:12:39,800
va a correr más rápido.

291
00:12:39,800 --> 00:12:41,090
Su sitio web va a funcionar mejor.

292
00:12:41,090 --> 00:12:42,650
Los usuarios van a ser más feliz.

293
00:12:42,650 --> 00:12:45,280
Y por eso hay estos efectos
de la realidad, dando

294
00:12:45,280 --> 00:12:47,350
nosotros algo más profundo que pensamos.

295
00:12:47,350 --> 00:12:49,990
>> Así que echemos un vistazo a lo que la combinación de
especie es realmente todo.

296
00:12:49,990 --> 00:12:52,992
Lo bueno es que la combinación de
especie es sólo esto.

297
00:12:52,992 --> 00:12:56,300
Esto es, una vez más, lo que hemos llamado
pseudocódigo, ser pseudocódigo

298
00:12:56,300 --> 00:12:57,720
Sintaxis similar al Inglés.

299
00:12:57,720 --> 00:12:59,890
Y la simplicidad es
especie de fascinante.

300
00:12:59,890 --> 00:13:02,840
>> Así que en la entrada de n elementos - de manera que
Sólo significa, aquí está una matriz.

301
00:13:02,840 --> 00:13:04,000
Tiene n cosas en ella.

302
00:13:04,000 --> 00:13:05,370
Eso es todo lo que estamos diciendo no.

303
00:13:05,370 --> 00:13:07,560
>> Si n es menor que 2, retorno.

304
00:13:07,560 --> 00:13:08,640
Así que eso es sólo el caso trivial.

305
00:13:08,640 --> 00:13:12,580
Si n es menor que 2, entonces obviamente es
1 o 0, en cuyo caso la cosa

306
00:13:12,580 --> 00:13:14,780
ya está ordenada o no existen,
así que volver.

307
00:13:14,780 --> 00:13:15,900
No hay nada que hacer.

308
00:13:15,900 --> 00:13:18,360
Así que eso es un caso sencillo de arrancar.

309
00:13:18,360 --> 00:13:20,110
>> Si no, tenemos tres pasos.

310
00:13:20,110 --> 00:13:23,650
Ordene la mitad izquierda de los elementos, más o menos
la mitad derecha de los elementos,

311
00:13:23,650 --> 00:13:26,650
y luego fusionar las mitades ordenados.

312
00:13:26,650 --> 00:13:29,400
Lo que es interesante aquí es que
Soy una especie de batea, ¿verdad?

313
00:13:29,400 --> 00:13:32,300
Hay una especie de definición circular
a este algoritmo.

314
00:13:32,300 --> 00:13:35,986
¿En qué sentido es este algoritmo de
circular definición?

315
00:13:35,986 --> 00:13:37,850
>> AUDIENCIA: [inaudible].

316
00:13:37,850 --> 00:13:41,670
>> DAVID MALAN: Sí, mi algoritmo de clasificación,
dos de sus pasos son "una especie

317
00:13:41,670 --> 00:13:44,640
algo ". Así que plantea la
pregunta, bueno, ¿qué voy a utilizar

318
00:13:44,640 --> 00:13:46,460
para ordenar la mitad izquierda
y la mitad derecha?

319
00:13:46,460 --> 00:13:49,600
Y la belleza es que a pesar de que
de nuevo, esta es la mente-flexión

320
00:13:49,600 --> 00:13:54,030
desprenderse potencialmente, puede utilizar la misma
algoritmo para ordenar la mitad izquierda.

321
00:13:54,030 --> 00:13:54,700
>> Pero espere un minuto.

322
00:13:54,700 --> 00:13:57,070
Cuando te dicen que ordenar la
medio izquierdo, ¿cuáles son los dos

323
00:13:57,070 --> 00:13:58,240
pasos va a ser el próximo?

324
00:13:58,240 --> 00:14:00,550
Lo arreglaremos la mitad izquierda de la
medio izquierdo y el derecho

325
00:14:00,550 --> 00:14:01,420
la mitad de la mitad izquierda.

326
00:14:01,420 --> 00:14:04,430
Maldita sea, ¿cómo puedo ordenar esos dos
mitades o cuartos, ahora?

327
00:14:04,430 --> 00:14:05,260
>> Pero eso está bien.

328
00:14:05,260 --> 00:14:07,830
Tenemos un algoritmo de clasificación aquí.

329
00:14:07,830 --> 00:14:10,660
Y aunque es posible que preocuparse en
primero se trata de una especie de infinito

330
00:14:10,660 --> 00:14:12,780
bucle, es un ciclo que nunca es
ir al final - que va a

331
00:14:12,780 --> 00:14:15,770
terminar de una vez lo que pasa?

332
00:14:15,770 --> 00:14:16,970
Una vez que n es menor que 2.

333
00:14:16,970 --> 00:14:19,180
Que con el tiempo va a pasar,
porque si sigues reducción a la mitad y

334
00:14:19,180 --> 00:14:23,020
reducir a la mitad en reducir a la mitad estas mitades, seguramente
finalmente va a terminar

335
00:14:23,020 --> 00:14:25,350
con sólo 1 o 0 elementos.

336
00:14:25,350 --> 00:14:28,500
En ese momento, este algoritmo
dice que usted está.

337
00:14:28,500 --> 00:14:31,020
>> Así que la verdadera magia de esta
algoritmo parece estar en

338
00:14:31,020 --> 00:14:33,470
ese paso final, la fusión.

339
00:14:33,470 --> 00:14:37,190
Esa simple idea sólo la fusión de dos
cosas, eso es lo que en última instancia va

340
00:14:37,190 --> 00:14:40,920
que nos permita ordenar una matriz de,
digamos, ocho elementos.

341
00:14:40,920 --> 00:14:44,410
Así que tengo ocho más bolas de la tensión de hasta
aquí, ocho trozos de papel, y un

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

343
00:14:45,500 --> 00:14:46,140
que tengo la oportunidad de mantener.

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

345
00:14:46,960 --> 00:14:48,970
>> DAVID MALAN: Si pudiéramos tomar ocho
voluntarios, y vamos a ver si podemos

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

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

348
00:14:52,500 --> 00:14:53,565
La informática es cada vez divertido.

349
00:14:53,565 --> 00:14:54,320
Está bien.

350
00:14:54,320 --> 00:14:57,770
Así que ¿qué hay de ustedes tres,
mayor a mano allí.

351
00:14:57,770 --> 00:14:58,580
Cuatro en la parte posterior.

352
00:14:58,580 --> 00:15:02,220
Y ¿qué tal si voy a hacer usted
tres en esta fila?

353
00:15:02,220 --> 00:15:03,390
Y cuatro en la parte delantera.

354
00:15:03,390 --> 00:15:04,920
Así que ocho, vamos arriba.

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

356
00:15:12,060 --> 00:15:13,450
>> DAVID MALAN: En realidad soy
no estoy seguro de lo que es.

357
00:15:13,450 --> 00:15:14,810
¿Es que las bolas de estrés?

358
00:15:14,810 --> 00:15:16,510
Lámparas del escritorio?

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

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

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

362
00:15:20,160 --> 00:15:21,310
Así que ven arriba.

363
00:15:21,310 --> 00:15:22,310
¿Quién quiere -

364
00:15:22,310 --> 00:15:23,570
siguen llegando.

365
00:15:23,570 --> 00:15:24,240
Vamos a ver.

366
00:15:24,240 --> 00:15:26,460
Y esto te pone en el lugar -

367
00:15:26,460 --> 00:15:27,940
usted está en una ubicación.

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

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

370
00:15:30,760 --> 00:15:31,310
Muy bien, estamos bien.

371
00:15:31,310 --> 00:15:35,130
Muy bien, así que cada uno tiene un asiento,
pero no en el cristal de Google.

372
00:15:35,130 --> 00:15:36,475
Permítanme hacer cola estos.

373
00:15:36,475 --> 00:15:37,115
¿Cómo te llamas?

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
Muy bien, se llega a parecerse
el friki, si eso está bien.

377
00:15:42,000 --> 00:15:44,625
Bueno, yo también, supongo,
sólo por un momento.

378
00:15:44,625 --> 00:15:45,875
Muy bien, espera.

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

380
00:15:48,510 --> 00:15:50,950
Hemos estado tratando de llegar a un
caso de uso de Google Glass, y

381
00:15:50,950 --> 00:15:53,750
pensó que sería divertido para hacer
esto cuando la gente está en el escenario.

382
00:15:53,750 --> 00:15:57,120
Vamos a grabar el mundo
desde su perspectiva.

383
00:15:57,120 --> 00:15:58,410
Está bien.

384
00:15:58,410 --> 00:15:59,830
No, probablemente lo que pretende Google.

385
00:15:59,830 --> 00:16:02,260
Muy bien, si no te importa que llevaba
esto durante los próximos minutos torpes,

386
00:16:02,260 --> 00:16:03,150
eso sería maravilloso.

387
00:16:03,150 --> 00:16:08,620
>> Muy bien, así que tenemos aquí una serie de
elementos, y esa matriz, como por la

388
00:16:08,620 --> 00:16:11,480
trozos de papel en estas personas '
las manos, se encuentra actualmente sin clasificar.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Oh, eso es tan raro.

390
00:16:12,050 --> 00:16:12,810
>> DAVID MALAN: Es más o menos al azar.

391
00:16:12,810 --> 00:16:15,760
Y en un momento, vamos a tratar
implementar merge sort juntos

392
00:16:15,760 --> 00:16:17,950
y ver a dónde idea clave es.

393
00:16:17,950 --> 00:16:21,970
Y el truco aquí con la combinación de tipo es
algo que no hemos asumido todavía.

394
00:16:21,970 --> 00:16:24,030
En realidad necesitamos un poco de
espacio adicional.

395
00:16:24,030 --> 00:16:26,650
Entonces, ¿qué va a ser particularmente
interesante de esto es que estos

396
00:16:26,650 --> 00:16:29,270
chicos van a moverse un poco
poco, porque yo voy a asumir que

397
00:16:29,270 --> 00:16:31,880
hay un conjunto adicional de espacio,
decir, justo detrás de ellos.

398
00:16:31,880 --> 00:16:34,570
>> Así que si están detrás de su silla,
esa es la matriz secundaria.

399
00:16:34,570 --> 00:16:36,960
Si están sentados aquí, eso es
la matriz primaria.

400
00:16:36,960 --> 00:16:40,170
Pero este es un recurso que tenemos
no aprovechado hasta ahora con la burbuja

401
00:16:40,170 --> 00:16:42,040
especie, con la selección de género,
con la ordenación por inserción.

402
00:16:42,040 --> 00:16:44,600
Recordemos la semana pasada, todo el mundo
tipo de baraja en su lugar.

403
00:16:44,600 --> 00:16:46,840
No usaron la memoria adicional.

404
00:16:46,840 --> 00:16:49,310
Hicimos habitación para personas con
mover a la gente alrededor.

405
00:16:49,310 --> 00:16:50,580
>> Así que esta es una idea clave, también.

406
00:16:50,580 --> 00:16:53,410
Hay un trade-off, en general, en
ciencias de la computación, de los recursos.

407
00:16:53,410 --> 00:16:55,800
Si desea acelerar algo
como el tiempo, vas a

408
00:16:55,800 --> 00:16:56,900
que tenga que pagar un precio.

409
00:16:56,900 --> 00:17:00,750
Y uno de esos precios es muy a menudo
el espacio, la cantidad de memoria o disco

410
00:17:00,750 --> 00:17:01,700
espacio de disco que está utilizando.

411
00:17:01,700 --> 00:17:03,640
O bien, francamente, la cantidad
de tiempo del programador.

412
00:17:03,640 --> 00:17:06,700
¿Cuánto tiempo le toma, el ser humano,
a aplicar en la práctica algunos más

413
00:17:06,700 --> 00:17:07,829
algoritmo complicado.

414
00:17:07,829 --> 00:17:09,760
Pero por hoy, el trade-off
es el tiempo y el espacio.

415
00:17:09,760 --> 00:17:11,930
>> Así que si ustedes pudieran acaba de celebrar su
números para que podamos ver que eres

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

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

418
00:17:16,599 --> 00:17:19,520
Así que voy a tratar de orquestar
cosas, si ustedes pueden simplemente

419
00:17:19,520 --> 00:17:21,800
seguir mi ejemplo aquí.

420
00:17:21,800 --> 00:17:26,650
>> Así que me voy a poner en práctica, en primer lugar, la
primer paso de la pseudocódigo, que es

421
00:17:26,650 --> 00:17:29,440
en la entrada de n elementos, si n es
menos de 2, y luego volver.

422
00:17:29,440 --> 00:17:31,370
Obviamente, eso no lo hace
Aplicamos, por lo que seguimos adelante.

423
00:17:31,370 --> 00:17:33,340
Así ordenar la mitad izquierda de los elementos.

424
00:17:33,340 --> 00:17:36,220
Así que eso significa que voy a centrar mi
atención por un momento sobre estas

425
00:17:36,220 --> 00:17:37,310
cuatro tipos de aquí.

426
00:17:37,310 --> 00:17:39,774
Muy bien, ¿qué es lo próximo a hacer?

427
00:17:39,774 --> 00:17:40,570
>> AUDIENCIA: Ordene la mitad izquierda.

428
00:17:40,570 --> 00:17:42,780
>> DAVID MALAN: Así que ahora tengo que ordenar
La mitad izquierda de estos chicos.

429
00:17:42,780 --> 00:17:45,580
Porque de nuevo, supongamos que usted mismo la
objetivo es ordenar la mitad izquierda.

430
00:17:45,580 --> 00:17:46,440
¿Cómo se hace eso?

431
00:17:46,440 --> 00:17:49,140
Sólo tienes que seguir las instrucciones, incluso
aunque lo estamos haciendo de nuevo.

432
00:17:49,140 --> 00:17:50,160
Así ordenar la mitad izquierda.

433
00:17:50,160 --> 00:17:52,030
Ahora estoy clasificar estos dos chicos.

434
00:17:52,030 --> 00:17:53,563
¿Qué viene ahora?

435
00:17:53,563 --> 00:17:54,510
>> AUDIENCIA: Ordene la mitad izquierda.

436
00:17:54,510 --> 00:17:55,460
>> DAVID MALAN: Ordene la mitad izquierda.

437
00:17:55,460 --> 00:18:00,680
Así que ahora éstos, este asiento aquí,
es una lista de tamaño 1.

438
00:18:00,680 --> 00:18:01,365
¿Y cuál es tu nombre?

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 está aquí.

441
00:18:03,690 --> 00:18:07,470
Y así que ella ya está ordenado, porque
la lista es de tamaño 1.

442
00:18:07,470 --> 00:18:09,490
¿Qué debo hacer al lado?

443
00:18:09,490 --> 00:18:13,680
Aceptar, volverá, porque esa lista es de
tamaño 1, que es menor que 2.

444
00:18:13,680 --> 00:18:14,320
Entonces ¿cuál es el siguiente paso?

445
00:18:14,320 --> 00:18:17,490
Y ahora tienes que tipo de
dar marcha atrás en su mente.

446
00:18:17,490 --> 00:18:19,340
>> Ordene la mitad derecha, que es -

447
00:18:19,340 --> 00:18:19,570
¿cuál es tu nombre?

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

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

450
00:18:20,980 --> 00:18:23,210
Y así, ¿qué hacemos ahora que
tenemos una lista de tamaño de 1?

451
00:18:23,210 --> 00:18:24,440
>> AUDIENCIA: Retorno.

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

453
00:18:24,760 --> 00:18:29,540
Volvemos primero, y ahora el tercero
paso - y si me tipo de representarlo por

454
00:18:29,540 --> 00:18:33,490
que abarca los dos asientos ahora, ahora yo
tienen que fusionar estos dos elementos.

455
00:18:33,490 --> 00:18:35,530
Así que ahora, lamentablemente, los elementos
están fuera de orden.

456
00:18:35,530 --> 00:18:39,920
Pero ahí es donde el proceso de fusión
empieza a ser convincente.

457
00:18:39,920 --> 00:18:42,410
>> Así que si ustedes pudieran ponerse de pie por sólo
un momento, voy a necesitar, en un

458
00:18:42,410 --> 00:18:44,170
momento, con el paso detrás de su silla.

459
00:18:44,170 --> 00:18:46,480
Y si Linda, porque es 2
menor que 4, ¿por qué no

460
00:18:46,480 --> 00:18:48,130
vienes por primera vez?

461
00:18:48,130 --> 00:18:48,690
Quédate ahí.

462
00:18:48,690 --> 00:18:50,520
Así que Linda, tú vienes alrededor primero.

463
00:18:50,520 --> 00:18:53,820
>> Ahora, en realidad, si es sólo un arreglo
pudiéramos moverla en tiempo real

464
00:18:53,820 --> 00:18:55,360
desde esta silla a este lugar.

465
00:18:55,360 --> 00:18:57,770
Así que imaginen que tuvo alguna constante
número de pasos 1.

466
00:18:57,770 --> 00:18:58,480
Y ahora -

467
00:18:58,480 --> 00:19:01,490
pero tenemos que poner en
el primer lugar aquí.

468
00:19:01,490 --> 00:19:03,930
>> Y ahora si pudiera entrar en razón,
así, vamos a

469
00:19:03,930 --> 00:19:06,300
estar en lugar de dos.

470
00:19:06,300 --> 00:19:09,120
Y a pesar de esto se siente como si fuera
tomar un tiempo, lo que es bueno ahora es

471
00:19:09,120 --> 00:19:14,710
que la mitad izquierda de la
medio izquierdo está ordenada ahora.

472
00:19:14,710 --> 00:19:18,010
Entonces, ¿cuál era el siguiente paso, si ahora
retroceder aún más en la historia?

473
00:19:18,010 --> 00:19:18,980
>> AUDIENCIA: Mitad derecha.

474
00:19:18,980 --> 00:19:19,900
>> DAVID MALAN: Ordene la mitad derecha.

475
00:19:19,900 --> 00:19:21,320
Así que ustedes tienen que hacer esto, también.

476
00:19:21,320 --> 00:19:23,510
Así que si usted puede ponerse de pie
por un momento?

477
00:19:23,510 --> 00:19:25,192
¿Y cuál es tu nombre?

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, así que Jess es ahora la izquierda
la mitad de la mitad derecha.

481
00:19:29,720 --> 00:19:31,400
Y por eso ella es una lista de tamaño 1.

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

483
00:19:32,380 --> 00:19:33,070
Y tu nombre?

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

485
00:19:33,630 --> 00:19:35,340
>> DAVID MALAN: Michelle obviamente
una lista de tamaño 1.

486
00:19:35,340 --> 00:19:36,050
Ella ya está solucionado.

487
00:19:36,050 --> 00:19:38,690
Así que ahora sucede la magia,
el proceso de fusión.

488
00:19:38,690 --> 00:19:39,790
Entonces, ¿quién va a venir primero?

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

490
00:19:41,560 --> 00:19:43,280
Así que si pudieras venir a la vuelta.

491
00:19:43,280 --> 00:19:47,090
El espacio que tenemos disponible para ella ahora
es justo detrás de esta silla aquí.

492
00:19:47,090 --> 00:19:51,580
Y ahora si pudiera volver, así,
ahora tenemos, para ser claros, dos

493
00:19:51,580 --> 00:19:53,810
mitades, cada una de tamaño 2 -

494
00:19:53,810 --> 00:19:57,090
y simplemente por el amor de la representación, si
podría hacer un poco de un espacio -

495
00:19:57,090 --> 00:19:59,780
una mitad izquierda aquí, uno
medio aquí.

496
00:19:59,780 --> 00:20:01,160
>> Rebobinar aún más en la historia.

497
00:20:01,160 --> 00:20:02,270
Lo que paso es el siguiente?

498
00:20:02,270 --> 00:20:03,030
>> AUDIENCIA: Combinar.

499
00:20:03,030 --> 00:20:04,160
>> DAVID MALAN: Así que ahora tenemos que fusionar.

500
00:20:04,160 --> 00:20:07,490
Así que bien, así que ahora, gracias a Dios, que nos
simplemente liberado cuatro sillas.

501
00:20:07,490 --> 00:20:11,480
Para ello hemos utilizado el doble de memoria, pero
podemos dar oscilando entre

502
00:20:11,480 --> 00:20:12,330
las dos matrices.

503
00:20:12,330 --> 00:20:14,190
Así que el número está por venir primero?

504
00:20:14,190 --> 00:20:14,850
Así que Michelle, obviamente.

505
00:20:14,850 --> 00:20:16,680
Así que ven alrededor y tomar
su asiento aquí.

506
00:20:16,680 --> 00:20:19,120
Y a continuación, el número 2 es, obviamente,
siguiente, por lo que vienen 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
Y de nuevo, a pesar de que hay una
poco de caminar involucrados,

509
00:20:23,390 --> 00:20:26,010
Realmente, estos podrían ocurrir al instante,
moviendo uno -

510
00:20:26,010 --> 00:20:26,880
Bien, bien jugado.

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

512
00:20:28,350 --> 00:20:29,680
>> DAVID MALAN: Y ahora estamos
en muy buena forma.

513
00:20:29,680 --> 00:20:34,910
La mitad izquierda de la entera
de entrada ya ha sido solucionado.

514
00:20:34,910 --> 00:20:37,370
Muy bien, por lo que estos chicos tenía
la ventaja de mi -

515
00:20:37,370 --> 00:20:40,340
¿cómo se terminan todas las chicas de la
a la izquierda y todos los chicos de la derecha?

516
00:20:40,340 --> 00:20:42,450
>> Aceptar, por lo que a su vez chicos ahora.

517
00:20:42,450 --> 00:20:44,680
Así que no voy a caminar a través de
estos pasos.

518
00:20:44,680 --> 00:20:46,550
Vamos a ver si somos capaces de volver a aplicar
la misma pseudocódigo.

519
00:20:46,550 --> 00:20:50,050
Si quieres seguir adelante y ponerse de pie,
y ustedes, te voy a dar el micrófono.

520
00:20:50,050 --> 00:20:52,990
A ver si no se puede replicar lo
que acabamos de hacer aquí en la

521
00:20:52,990 --> 00:20:53,880
otro extremo de la lista.

522
00:20:53,880 --> 00:20:59,530
¿Quién tiene que hablar en primer lugar,
basado en el algoritmo?

523
00:20:59,530 --> 00:21:03,210
Así que explique lo que está haciendo antes de
usted hace cualquier movimiento del pie.

524
00:21:03,210 --> 00:21:05,930
>> ALTAVOZ 1: Muy bien, entonces ya
Yo soy la mitad izquierda de la

525
00:21:05,930 --> 00:21:07,790
medio izquierdo, vuelvo.

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

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

528
00:21:09,250 --> 00:21:10,350
>> ALTAVOZ 1: Y entonces -

529
00:21:10,350 --> 00:21:11,800
>> DAVID MALAN: ¿Quién hace
el micro pase a la siguiente?

530
00:21:11,800 --> 00:21:12,920
>> ALTAVOZ 1: número siguiente.

531
00:21:12,920 --> 00:21:14,720
>> ALTAVOZ 2: Así que estoy en la mitad derecha
de la mitad izquierda de la

532
00:21:14,720 --> 00:21:17,830
medio izquierdo, y vuelva.

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

534
00:21:18,050 --> 00:21:18,550
Volverá.

535
00:21:18,550 --> 00:21:21,855
¿Y ahora qué es lo que sigue para ustedes dos?

536
00:21:21,855 --> 00:21:23,740
>> ALTAVOZ 2: Queremos ver quién es el más pequeño.

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

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

539
00:21:24,940 --> 00:21:27,590
El espacio que vamos a utilizar para combinar
que en, aunque son

540
00:21:27,590 --> 00:21:30,250
obviamente ya ordenados, vamos
para seguir el mismo algoritmo.

541
00:21:30,250 --> 00:21:31,560
Entonces, ¿quién va en la espalda por primera vez?

542
00:21:31,560 --> 00:21:35,720
Así 3, y luego 7.

543
00:21:35,720 --> 00:21:38,570
Y ahora el micrófono va
a estos chicos, ¿de acuerdo?

544
00:21:38,570 --> 00:21:43,590
>> ALTAVOZ 3: ¿Así que soy la mitad derecha de la
medio izquierdo, y mi n es menor que

545
00:21:43,590 --> 00:21:45,048
1, así que sólo voy a pasar -

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

547
00:21:46,380 --> 00:21:49,450
>> ALTAVOZ 4: Yo soy la mitad derecha de la
mitad derecha de la mitad derecha, y estoy

548
00:21:49,450 --> 00:21:51,740
También una persona, así que estoy
va a volver.

549
00:21:51,740 --> 00:21:52,990
Así que ahora nos fusionamos.

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

551
00:21:55,140 --> 00:21:56,150
>> ALTAVOZ 3: Así que volvemos.

552
00:21:56,150 --> 00:21:57,160
>> DAVID MALAN: ¿Así que ir a la parte trasera.

553
00:21:57,160 --> 00:21:59,200
Así 5 va primero, a continuación, 8.

554
00:21:59,200 --> 00:22:01,240
Y ahora la audiencia, que es la
paso que tenemos que ahora rebobinar

555
00:22:01,240 --> 00:22:02,200
de nuevo en nuestras mentes?

556
00:22:02,200 --> 00:22:02,940
>> AUDIENCIA: Combinar.

557
00:22:02,940 --> 00:22:07,270
>> DAVID MALAN: La fusión de la mitad izquierda y derecha
la mitad de la mitad izquierda originales.

558
00:22:07,270 --> 00:22:08,840
Así que ahora -

559
00:22:08,840 --> 00:22:10,520
y acaba de dejar esto en claro,
hacer un poco de espacio

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

561
00:22:11,690 --> 00:22:13,800
Así que ahora que es las dos listas,
izquierda y derecha.

562
00:22:13,800 --> 00:22:18,320
Entonces, ¿cómo ahora fusionamos ustedes en
la primera fila de asientos de nuevo?

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

564
00:22:19,600 --> 00:22:20,850
Luego 5, obviamente.

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

566
00:22:23,110 --> 00:22:27,330
Luego 7, y ahora 8.

567
00:22:27,330 --> 00:22:28,710
Bueno, y ahora que somos?

568
00:22:28,710 --> 00:22:29,650
>> AUDIENCIA: No realizado.

569
00:22:29,650 --> 00:22:32,440
>> DAVID MALAN: No realizado, porque
Obviamente, hay un paso restante.

570
00:22:32,440 --> 00:22:35,720
Pero, de nuevo, la razón por la que estoy usando esta
la jerga como "rebobinar en su mente,"

571
00:22:35,720 --> 00:22:37,160
es porque eso es realmente
lo que está sucediendo.

572
00:22:37,160 --> 00:22:39,610
Estamos pasando por todos estos pasos,
pero estamos especie de pausa para una

573
00:22:39,610 --> 00:22:42,480
momento, el buceo profundo en el
algoritmo, haciendo una pausa por un momento,

574
00:22:42,480 --> 00:22:45,840
buceo más profundo en el algoritmo, y
ahora tenemos que retroceder casi en nuestra

575
00:22:45,840 --> 00:22:49,430
mentes y deshacer todas estas capas
que hemos especie de puesta en espera.

576
00:22:49,430 --> 00:22:51,790
>> Así que ahora tenemos dos listas de tamaño 4.

577
00:22:51,790 --> 00:22:54,790
Si ustedes pudieran ponerse de pie una vez más
y hacer un poco de espacio para

578
00:22:54,790 --> 00:22:57,230
dejar claro que esta es la izquierda
la mitad de la original, la

579
00:22:57,230 --> 00:22:58,620
mitad derecha de la original.

580
00:22:58,620 --> 00:23:01,060
¿Quién es el primer número que
tenga que tirar en la parte de atrás?

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

582
00:23:01,870 --> 00:23:03,230
>> Por eso, pusimos Michelle aquí.

583
00:23:03,230 --> 00:23:05,080
¿Y quién tiene el número 2?

584
00:23:05,080 --> 00:23:06,440
Número 2 viene en la parte posterior también.

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

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

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

588
00:23:16,570 --> 00:23:18,850
>> Bien, así que me sentí como un montón
de pasos, seguro.

589
00:23:18,850 --> 00:23:22,390
Pero ahora vamos a ver si no podemos confirmar
tipo de intuitivamente que este

590
00:23:22,390 --> 00:23:26,190
algoritmo fundamental, especialmente en lo que
n se hace muy grande, como hemos visto

591
00:23:26,190 --> 00:23:29,170
con las animaciones, es
fundamentalmente más rápido.

592
00:23:29,170 --> 00:23:33,400
Así que yo reclamo este algoritmo, en el peor de los casos
caso e incluso en el mejor de los casos,

593
00:23:33,400 --> 00:23:36,160
es gran O de n veces log n.

594
00:23:36,160 --> 00:23:39,160
Es decir, hay algún aspecto de este
algoritmo que toma n pasos, pero

595
00:23:39,160 --> 00:23:43,110
hay otro aspecto en algún lugar
esa iteración, que bucle, que

596
00:23:43,110 --> 00:23:44,410
tiene registro de n pasos.

597
00:23:44,410 --> 00:23:49,154
¿Podemos poner nuestro dedo en lo que los
dos números se refieren?

598
00:23:49,154 --> 00:23:51,320
Bueno, donde -

599
00:23:51,320 --> 00:23:54,160
¿dónde el micrófono ir?

600
00:23:54,160 --> 00:23:58,660
>> ALTAVOZ 1: ¿El log n ser
nosotros romper en dos -

601
00:23:58,660 --> 00:23:59,630
dividiendo por dos, esencialmente.

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

603
00:24:00,120 --> 00:24:03,000
Cada vez que vemos en cualquier algoritmo de este modo
ahora, no ha habido este patrón de

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

605
00:24:04,200 --> 00:24:05,700
Y se reduce típicamente
a algo que es

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

607
00:24:07,100 --> 00:24:10,180
Pero podría realmente ser cualquier cosa,
pero log base 2.

608
00:24:10,180 --> 00:24:11,330
>> Ahora ¿qué pasa con el n?

609
00:24:11,330 --> 00:24:14,550
Puedo ver que tipo de que dividimos
chicos - que haya dividido, dividido ti,

610
00:24:14,550 --> 00:24:15,910
que divide, que dividido.

611
00:24:15,910 --> 00:24:18,760
¿De dónde viene el final viene?

612
00:24:18,760 --> 00:24:19,810
>> Así que es la fusión.

613
00:24:19,810 --> 00:24:20,610
Debido a pensar en ello.

614
00:24:20,610 --> 00:24:25,420
Cuando combina ocho personas juntas,
por el que la mitad de ellos son un conjunto de cuatro

615
00:24:25,420 --> 00:24:27,770
y la otra mitad son otra
un conjunto de cuatro, ¿cómo ir

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

617
00:24:28,820 --> 00:24:30,830
Bueno, ustedes hicieron que
bastante intuitiva.

618
00:24:30,830 --> 00:24:34,140
>> Pero si en vez hice un poco más
metódicamente, podría haber señalado en

619
00:24:34,140 --> 00:24:38,090
la primera persona de la izquierda con mi izquierda
mano, apuntando a la persona más a la izquierda

620
00:24:38,090 --> 00:24:42,080
de ese medio con mi mano derecha, y
sólo posteriormente caminó a través de la

621
00:24:42,080 --> 00:24:46,990
lista, señalando el elemento más pequeño
cada vez, moviendo el dedo una y

622
00:24:46,990 --> 00:24:48,970
el control como sea necesario en la lista.

623
00:24:48,970 --> 00:24:51,890
Pero lo que es clave sobre esta fusión
proceso es que estoy comparando estos pares

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

625
00:24:53,460 --> 00:24:57,270
Desde la mitad derecha y de la izquierda
medio, estoy dando marcha atrás ni una sola vez.

626
00:24:57,270 --> 00:25:00,570
>> Así la propia fusión está tomando
no más de n pasos.

627
00:25:00,570 --> 00:25:03,250
¿Y cuántas veces te tengo
hacer que la fusión?

628
00:25:03,250 --> 00:25:07,150
Bueno, no más de n, y acabamos de
vio que con la fusión final.

629
00:25:07,150 --> 00:25:13,120
Y por lo que si usted hace algo que toma
log n pasos n veces, o viceversa,

630
00:25:13,120 --> 00:25:15,210
que va a darnos n log n veces.

631
00:25:15,210 --> 00:25:16,310
>> ¿Y por qué es esto mejor?

632
00:25:16,310 --> 00:25:19,600
Bueno, si ya sabemos que log
n es mejor que n - a la derecha?

633
00:25:19,600 --> 00:25:22,590
Vimos en la búsqueda binaria, la guía de teléfonos
ejemplo, log n era definitivamente

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

635
00:25:23,760 --> 00:25:28,420
Así que eso significa n veces log n es
definitivamente mejor que n veces otra

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

637
00:25:30,390 --> 00:25:32,400
Y eso es lo que en última instancia sentimos.

638
00:25:32,400 --> 00:25:34,928
>> Así que gran aplauso, si
pudiéramos, para estos chicos.

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

640
00:25:38,920 --> 00:25:41,550
>> DAVID MALAN: ¿Y sus regalos de despedida -
guardéis los números,

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

642
00:25:44,010 --> 00:25:45,620
Y su regalo de despedida, como siempre.

643
00:25:45,620 --> 00:25:47,290
Ah, y le enviaremos
el material de archivo, Michelle.

644
00:25:47,290 --> 00:25:48,343
Gracias.

645
00:25:48,343 --> 00:25:49,250
Está bien.

646
00:25:49,250 --> 00:25:50,400
Podrá disfrutar de una bola de la tensión.

647
00:25:50,400 --> 00:25:54,110
>> Y déjame tire hacia arriba, mientras tanto,
nuestro amigo Rob Bowden para ofrecer

648
00:25:54,110 --> 00:25:59,520
algo diferente perspectiva sobre esto,
ya que se puede pensar en estos

649
00:25:59,520 --> 00:26:01,280
pasos que suceden de forma un tanto
diferente manera.

650
00:26:01,280 --> 00:26:04,750
De hecho, la puesta a punto para lo que acerca de Rob
para mostrarnos asume que hemos

651
00:26:04,750 --> 00:26:09,030
ha hecho la división de la
gran lista en ocho listas pequeñas,

652
00:26:09,030 --> 00:26:10,570
cada uno de tamaño 1.

653
00:26:10,570 --> 00:26:13,350
>> Así que estamos cambiando el pseudocódigo un
poco sólo para obtener una especie de en el

654
00:26:13,350 --> 00:26:15,320
idea central de cómo funciona la fusión.

655
00:26:15,320 --> 00:26:17,600
Pero el tiempo de ejecución de lo
está a punto de hacer es todavía

656
00:26:17,600 --> 00:26:19,110
va a ser la misma.

657
00:26:19,110 --> 00:26:23,540
Y otra vez, la puesta a punto aquí es que él es
comenzado con ocho listas de tamaño 1.

658
00:26:23,540 --> 00:26:27,730
Así que te has perdido la parte donde él es
realmente se hace el registro de n, log n, log n

659
00:26:27,730 --> 00:26:31,205
divisoria de la entrada.

660
00:26:31,205 --> 00:26:32,120
>> [REPRODUCCIÓN DE VÍDEO]

661
00:26:32,120 --> 00:26:33,615
>> -Esto es todo por el paso uno.

662
00:26:33,615 --> 00:26:38,270
Para el segundo paso, en varias ocasiones
combinar pares de listas.

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

664
00:26:39,210 --> 00:26:41,270
Sólo audio está llegando
fuera de mi ordenador.

665
00:26:41,270 --> 00:26:42,520
Vamos a intentar de nuevo.

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

667
00:26:45,330 --> 00:26:48,310
>> -Sólo tiene que elegir de forma arbitraria que -
Ahora tenemos cuatro listas.

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

669
00:26:51,590 --> 00:26:52,120
Aprenda antes.

670
00:26:52,120 --> 00:26:53,040
>> DAVID MALAN: Eso es.

671
00:26:53,040 --> 00:27:00,510
>> -La fusión de 108 y 15, se acaba
con la lista de 15, 108.

672
00:27:00,510 --> 00:27:07,170
La fusión de 50 y 4, nos
terminar con 4, 50.

673
00:27:07,170 --> 00:27:12,990
La fusión de 8 y 42, que
terminar con 8, 42.

674
00:27:12,990 --> 00:27:19,970
Y la fusión de 23 y 16, que
terminar con 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Ahora todas nuestras listas son de tamaño 2.

676
00:27:23,270 --> 00:27:26,690
Observe que cada uno de los
cuatro listas se ordenan.

677
00:27:26,690 --> 00:27:29,450
Así que podemos comenzar la fusión
pares de listas de nuevo.

678
00:27:29,450 --> 00:27:38,420
La fusión de 15 y 108 y 4 y 50, nos
saca primero la 4, la 15, entonces

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

680
00:27:41,500 --> 00:27:50,610
La fusión de 8, 42 y 16, 23, primero echamos
el 8, a continuación, la 16, entonces el 23,

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

682
00:27:52,700 --> 00:27:57,600
>> Así que ahora tenemos sólo dos listas de tamaño
4, cada uno de los cuales está ordenada.

683
00:27:57,600 --> 00:28:01,170
Así que ahora nos fusionamos estas dos listas.

684
00:28:01,170 --> 00:28:11,835
En primer lugar, tomamos el 4, luego tomamos el
8, luego tomamos el 15, luego 16, luego

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

686
00:28:19,456 --> 00:28:19,872
>> [VIDEO PLAYBACK FIN]

687
00:28:19,872 --> 00:28:23,430
>> DAVID MALAN: De nuevo, aviso, que nunca
tocado un vaso dado más de una vez

688
00:28:23,430 --> 00:28:24,860
después de avanzar más allá de ella.

689
00:28:24,860 --> 00:28:26,200
Así que nunca repetir.

690
00:28:26,200 --> 00:28:29,850
Así que siempre se está moviendo hacia un lado,
y ahí es donde tenemos nuestro n.

691
00:28:29,850 --> 00:28:33,290
>> ¿Por qué no me deja subo una animación
que hemos visto antes, pero esta vez

692
00:28:33,290 --> 00:28:35,110
centrarse sólo en la combinación de tipo.

693
00:28:35,110 --> 00:28:38,030
Déjame ir por delante y el zoom
en esto aquí.

694
00:28:38,030 --> 00:28:42,530
Primero permitirme elegir una entrada al azar,
magnificar esto, y usted puede ver una especie de

695
00:28:42,530 --> 00:28:46,600
lo que tomamos por sentado, antes,
fusionar especie está haciendo realidad.

696
00:28:46,600 --> 00:28:50,330
>> Así cuenta de que usted consigue estas mitades o
estos cuartos o en estos octavos de la

697
00:28:50,330 --> 00:28:53,140
problema que, de repente,
empezar a tomar buena forma.

698
00:28:53,140 --> 00:28:57,070
Y, por último, que se ve en
el final que bam,

699
00:28:57,070 --> 00:28:58,860
todo se fusionaron.

700
00:28:58,860 --> 00:29:01,690
>> Así que estos son sólo tres diferentes
toma en la misma idea.

701
00:29:01,690 --> 00:29:05,980
Pero la idea clave, al igual que dividir
y vencer en la primera clase,

702
00:29:05,980 --> 00:29:10,640
fue que decidimos dividir de alguna manera
el problema en algo grande, en

703
00:29:10,640 --> 00:29:14,760
algo especie de idéntico espíritu,
pero más pequeña y más pequeña y más pequeña

704
00:29:14,760 --> 00:29:15,660
y más pequeño.

705
00:29:15,660 --> 00:29:18,420
>> Ahora otra divertida forma de una especie de pensar
acerca de estos, a pesar de que no es

706
00:29:18,420 --> 00:29:20,520
va a dar el mismo intuitiva
comprensión, es

707
00:29:20,520 --> 00:29:21,640
la siguiente animación.

708
00:29:21,640 --> 00:29:25,400
Así que este es un video que alguien armó
la asociada diferente

709
00:29:25,400 --> 00:29:29,970
sonidos con las diversas operaciones para
ordenación por inserción, por la combinación de clase y

710
00:29:29,970 --> 00:29:31,150
por un par de los demás.

711
00:29:31,150 --> 00:29:32,330
Así que en un momento, me voy a pegar en Reproducir.

712
00:29:32,330 --> 00:29:33,600
Se trata de un minuto de duración.

713
00:29:33,600 --> 00:29:37,410
Y a pesar de que todavía se puede ver la
patrones pasando, esta vez se puede

714
00:29:37,410 --> 00:29:41,420
También escuchar cómo estos algoritmos son
realizar de manera diferente y con

715
00:29:41,420 --> 00:29:43,950
algo diferentes patrones.

716
00:29:43,950 --> 00:29:45,830
>> Esta es la ordenación por inserción.

717
00:29:45,830 --> 00:29:50,400
>> [REPRODUCCIÓN DE TONOS]

718
00:29:50,400 --> 00:29:52,400
>> DAVID MALAN: De nuevo está tratando
para insertar cada elemento

719
00:29:52,400 --> 00:29:52,900
en donde debe estar.

720
00:29:52,900 --> 00:29:54,628
Se trata de una especie de burbuja.

721
00:29:54,628 --> 00:30:10,097
>> [REPRODUCCIÓN DE TONOS]

722
00:30:10,097 --> 00:30:13,630
>> DAVID MALAN: Y usted puede sentir una especie de
lo relativamente poco trabajo que está haciendo

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

724
00:30:15,834 --> 00:30:20,470
Esto es lo que suena como el aburrimiento.

725
00:30:20,470 --> 00:30:21,472
>> [REPRODUCCIÓN DE TONOS]

726
00:30:21,472 --> 00:30:25,222
>> DAVID MALAN: Se trata de una especie de selección,
donde seleccionamos el elemento que queremos por

727
00:30:25,222 --> 00:30:28,845
pasando una y otra vez y otra vez
y ponerlo al principio.

728
00:30:28,845 --> 00:30:37,674
>> [REPRODUCCIÓN DE TONOS]

729
00:30:37,674 --> 00:30:43,970
>> DAVID MALAN: Esto se merge sort, que
usted realmente puede comenzar a sentir.

730
00:30:43,970 --> 00:30:51,810
>> [REPRODUCCIÓN DE TONOS]

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

732
00:30:54,770 --> 00:30:58,395
>> DAVID MALAN: Algo llamado gnome
especie, que no hemos mirado.

733
00:30:58,395 --> 00:31:13,630
>> [REPRODUCCIÓN DE TONOS]

734
00:31:13,630 --> 00:31:17,910
>> DAVID MALAN: Así que vamos a ver, ahora,
distraído mientras espero es por el

735
00:31:17,910 --> 00:31:21,110
música, si puedo meter un poco
poco de matemáticas aquí.

736
00:31:21,110 --> 00:31:24,850
Así que hay una cuarta forma de que podamos
pensar en lo que significa esto

737
00:31:24,850 --> 00:31:29,210
funciones para ser más rápido que los
que hemos visto antes.

738
00:31:29,210 --> 00:31:32,470
Y si vas a venir en el curso de
un fondo de matemáticas, que

739
00:31:32,470 --> 00:31:36,030
realmente saben tal vez ya que
puede abofetear a un término en esta técnica -

740
00:31:36,030 --> 00:31:40,400
a saber, la recursión, una función
que de alguna manera se hace llamar.

741
00:31:40,400 --> 00:31:44,780
>> Y una vez más, recordemos que fusionar especie
pseudocódigo era recursivo, en el sentido

742
00:31:44,780 --> 00:31:48,460
que uno de los pasos de combinación de ordenar
era llamar especie -

743
00:31:48,460 --> 00:31:49,740
que es, en sí.

744
00:31:49,740 --> 00:31:52,480
Pero, por suerte, porque nos mantenían
llamando a ordenar o combinar especie,

745
00:31:52,480 --> 00:31:55,880
específicamente, en una más pequeña y más pequeña
y una lista más pequeña, al final

746
00:31:55,880 --> 00:32:00,005
tocado fondo, gracias a lo que llamaremos
un caso base, el caso no modificable que

747
00:32:00,005 --> 00:32:04,270
dijo que si la lista es pequeña, menos de 2
en ese caso, simplemente volver inmediatamente.

748
00:32:04,270 --> 00:32:07,550
Si no tuviéramos ese caso especial, el
algoritmo haría nunca tocar fondo,

749
00:32:07,550 --> 00:32:11,010
y que sería de hecho entrar en un
bucle infinito de verdad para siempre.

750
00:32:11,010 --> 00:32:14,330
>> Pero supongamos que queremos ahora poner
algunos números en esta, de nuevo, usando N

751
00:32:14,330 --> 00:32:15,660
como el tamaño de la entrada.

752
00:32:15,660 --> 00:32:18,680
Y yo quería preguntarte, ¿cuál es
el tiempo total involucrado en

753
00:32:18,680 --> 00:32:19,800
funcionando fusionar tipo?

754
00:32:19,800 --> 00:32:22,960
O en términos más generales, ¿cuál es
el costo de la misma en el tiempo?

755
00:32:22,960 --> 00:32:24,730
>> Bueno, es muy fácil de medir eso.

756
00:32:24,730 --> 00:32:29,010
Si n es menor que 2, el tiempo involucrado
en la clasificación de n elementos,

757
00:32:29,010 --> 00:32:30,480
donde n es 2, es 0.

758
00:32:30,480 --> 00:32:31,410
Porque simplemente devolvemos.

759
00:32:31,410 --> 00:32:32,510
No hay trabajo por hacer.

760
00:32:32,510 --> 00:32:35,660
Ahora podría decirse que, tal vez es un paso o dos
medidas para averiguar la cantidad de

761
00:32:35,660 --> 00:32:38,420
trabajo, pero es lo suficientemente cerca de 0 que
Yo sólo voy a decir que no es el trabajo

762
00:32:38,420 --> 00:32:40,940
requerido si la lista es tan pequeño
a ser poco interesante.

763
00:32:40,940 --> 00:32:42,580
>> Pero este caso es interesante.

764
00:32:42,580 --> 00:32:47,320
El caso recursivo fue la rama de
el pseudocódigo que dijo otra cosa, una especie

765
00:32:47,320 --> 00:32:52,000
la mitad izquierda, ordenar el derecho
medio, combinar las dos mitades.

766
00:32:52,000 --> 00:32:55,530
Ahora ¿por qué esta expresión
representar a ese gasto?

767
00:32:55,530 --> 00:32:58,690
Bueno, T de n sólo significa la
tiempo para ordenar n elementos.

768
00:32:58,690 --> 00:33:03,070
Y a continuación, en el lado derecho de la
signo igual allí, la T de n divide

769
00:33:03,070 --> 00:33:06,600
por 2 se refiere al costo de lo que?

770
00:33:06,600 --> 00:33:07,570
Clasificación de la mitad izquierda.

771
00:33:07,570 --> 00:33:10,990
El otro T de n dividido por 2 es
presumiblemente en referencia al coste de

772
00:33:10,990 --> 00:33:12,390
ordenar la mitad derecha.

773
00:33:12,390 --> 00:33:14,590
>> Y entonces el más n?

774
00:33:14,590 --> 00:33:15,420
Es la fusión.

775
00:33:15,420 --> 00:33:19,120
Porque si usted tiene dos listas, una de
tamaño n sobre 2 y otra de tamaño n

776
00:33:19,120 --> 00:33:22,580
más de 2, tiene que tocar la esencia
cada uno de esos elementos, al igual que Rob

777
00:33:22,580 --> 00:33:24,990
tocado cada una de las copas, y apenas
como hemos señalado en cada uno de los

778
00:33:24,990 --> 00:33:26,310
voluntarios en el escenario.

779
00:33:26,310 --> 00:33:28,790
Así que n es el gasto de la fusión.

780
00:33:28,790 --> 00:33:31,780
>> Ahora, por desgracia, esta fórmula
También es en sí mismo recursiva.

781
00:33:31,780 --> 00:33:36,390
Así que si la pregunta, si n es, por ejemplo,
16, si hay 16 personas en el escenario

782
00:33:36,390 --> 00:33:40,670
o 16 tazas en el video, el número de total de
pasos toma para ordenarlos

783
00:33:40,670 --> 00:33:41,550
con la combinación de clase?

784
00:33:41,550 --> 00:33:45,790
En realidad no es una respuesta obvia,
porque ahora usted tiene que ordenar de

785
00:33:45,790 --> 00:33:48,500
recursivamente responder a esta fórmula.

786
00:33:48,500 --> 00:33:51,190
>> Pero está bien, porque permítanme proponer
lo que hacemos lo siguiente.

787
00:33:51,190 --> 00:33:56,670
El tiempo necesario para ordenar 16 personas o
16 copas va a ser representado

788
00:33:56,670 --> 00:33:58,020
generalmente como T de 16.

789
00:33:58,020 --> 00:34:01,400
Pero eso es igual, de acuerdo con nuestra
fórmula anterior, 2 veces la cantidad

790
00:34:01,400 --> 00:34:04,780
de tiempo que se necesita para ordenar
8 tazas de más 16.

791
00:34:04,780 --> 00:34:08,590
Y de nuevo, más 16 es el momento de unir,
y los dos tiempos T de 8 es el

792
00:34:08,590 --> 00:34:10,790
tiempo para ordenar a la mitad izquierda y la mitad derecha.

793
00:34:10,790 --> 00:34:11,989
>> Pero de nuevo, esto no es suficiente.

794
00:34:11,989 --> 00:34:13,210
Tenemos que bucear más profundo.

795
00:34:13,210 --> 00:34:16,409
Esto significa que tenemos que responder a la
pregunta, ¿cuál es T de 8?

796
00:34:16,409 --> 00:34:19,610
Bueno T de 8 está a sólo 2
tiempos T de 4 y de 8.

797
00:34:19,610 --> 00:34:20,520
Bueno, ¿cuál es T, de 4?

798
00:34:20,520 --> 00:34:23,780
T, de 4 a solo 2 veces T de 2 más 4.

799
00:34:23,780 --> 00:34:25,489
Bueno, ¿cuál es T de 2?

800
00:34:25,489 --> 00:34:29,030
T de 2 se encuentra a sólo 2 veces T de 1 más 2.

801
00:34:29,030 --> 00:34:31,940
>> Y de nuevo, estamos como llegar
atrapado en este ciclo.

802
00:34:31,940 --> 00:34:34,790
Pero está a punto de golpear ese
así llamado caso base.

803
00:34:34,790 --> 00:34:37,310
Porque lo que es T, de 1, nos decimos?

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

805
00:34:37,810 --> 00:34:39,730
Así que ahora, finalmente, podemos trabajar hacia atrás.

806
00:34:39,730 --> 00:34:44,290
>> Si T de 1 es 0, ahora puedo subir un
alinear a este tipo de aquí, y no puedo

807
00:34:44,290 --> 00:34:46,330
enchufar 0 para T de 1.

808
00:34:46,330 --> 00:34:51,770
Así que eso significa que es igual a 2 veces cero,
conocido de otra manera como 0, más 2.

809
00:34:51,770 --> 00:34:53,739
Y por lo que toda esa expresión es 2.

810
00:34:53,739 --> 00:34:58,740
>> Ahora bien, si me tomo el T de 2, cuya respuesta
es 2, conéctelo a la línea media, T

811
00:34:58,740 --> 00:35:02,740
de 4, eso me da 2 veces
2 plus 4, por lo que 8.

812
00:35:02,740 --> 00:35:07,080
Pues si yo conecto a 8 a la anterior
line, que me da 2 veces 8, 16.

813
00:35:07,080 --> 00:35:12,470
Y si luego seguimos que con la
24, la adición de 16, por fin tenemos un

814
00:35:12,470 --> 00:35:13,820
valor de 64.

815
00:35:13,820 --> 00:35:18,480
>> Ahora que en sí misma especie de habla
nada a la notación n, la

816
00:35:18,480 --> 00:35:20,700
gran O, la omega que hemos
estado hablando.

817
00:35:20,700 --> 00:35:24,890
Pero resulta que el 64 es de hecho
16, el tamaño de la entrada,

818
00:35:24,890 --> 00:35:27,110
log base 2 de 16.

819
00:35:27,110 --> 00:35:30,200
Y si esto es un poco extraño, simplemente
Piense de nuevo, y se va a volver

820
00:35:30,200 --> 00:35:30,700
que es muy probable.

821
00:35:30,700 --> 00:35:33,775
Si esto es log base 2, es como 2
elevada a la que le da 16?

822
00:35:33,775 --> 00:35:36,380
Oh, eso es 4, por lo que es 16 veces 4.

823
00:35:36,380 --> 00:35:39,380
>> Y de nuevo, no es un gran problema si este
es una especie de vago recuerdo ahora.

824
00:35:39,380 --> 00:35:43,720
Pero por ahora, asumir la fe
que el 16 de registro 16 es 64.

825
00:35:43,720 --> 00:35:46,590
Y así, de hecho, con este simple cordura
comprobar, hemos confirmado -

826
00:35:46,590 --> 00:35:48,250
pero no demostrado formalmente -

827
00:35:48,250 --> 00:35:52,800
que el tiempo de ejecución de merge
especie es de hecho n log n.

828
00:35:52,800 --> 00:35:53,790
>> Así que no está mal.

829
00:35:53,790 --> 00:35:57,260
Es definitivamente mejor que el
algoritmos que hemos visto hasta ahora, y

830
00:35:57,260 --> 00:36:00,710
es porque hemos aprovechado, uno,
una técnica llamada recursión.

831
00:36:00,710 --> 00:36:03,880
Pero más interesante que eso, que
noción de dividir y conquistar.

832
00:36:03,880 --> 00:36:07,460
Una vez más, verdaderamente semana 0 cosas que
incluso ahora se repite en un

833
00:36:07,460 --> 00:36:08,740
manera más convincente.

834
00:36:08,740 --> 00:36:11,750
>> Ahora un poco de ejercicio divertido, si usted tiene
nunca hecho esto - y es probable que

835
00:36:11,750 --> 00:36:14,660
no tendría, pues una especie de normalidad
la gente no piensa hacerlo.

836
00:36:14,660 --> 00:36:20,650
Pero si voy a google.com y si
Quiero aprender algo acerca de

837
00:36:20,650 --> 00:36:22,356
recursividad, Intro.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Risas]

840
00:36:29,058 --> 00:36:32,030
[Más risas]

841
00:36:32,030 --> 00:36:33,385
DAVID MALAN: Bad broma lentamente extienda.

842
00:36:33,385 --> 00:36:34,450
[Risas]

843
00:36:34,450 --> 00:36:36,970
DAVID MALAN: Por si acaso, que está ahí.

844
00:36:36,970 --> 00:36:38,710
Yo no lo deletree mal,
y ahí está la broma.

845
00:36:38,710 --> 00:36:40,810
Está bien.

846
00:36:40,810 --> 00:36:42,950
Explicar a la gente a tu lado si
bastante no ha hecho clic en el momento.

847
00:36:42,950 --> 00:36:47,650
Pero recursión, de manera más general, se refiere
para el proceso de una llamada función

848
00:36:47,650 --> 00:36:51,430
en sí, o más en general, la división de un
problema en algo que puede ser

849
00:36:51,430 --> 00:36:56,220
resuelto por partes resolviendo idéntica
problemas de representación.

850
00:36:56,220 --> 00:36:58,400
>> Bueno, vamos a cambiar los engranajes
sólo por un momento.

851
00:36:58,400 --> 00:37:00,840
Nos gusta para terminar en ciertos melodramas,
así que vamos a empezar a establecer

852
00:37:00,840 --> 00:37:05,870
el escenario, durante varios minutos,
en una idea muy simple -

853
00:37:05,870 --> 00:37:07,620
el de intercambio de dos elementos, ¿verdad?

854
00:37:07,620 --> 00:37:10,040
Todos estos algoritmos hemos estado
hablando de los últimos dos

855
00:37:10,040 --> 00:37:12,420
conferencias implican algún
tipo de intercambio.

856
00:37:12,420 --> 00:37:14,630
Hoy en día se visualizó por ellos conseguir
arriba de sus sillas y

857
00:37:14,630 --> 00:37:18,570
caminando por ahí, pero en el código, lo haríamos
simplemente tomar un elemento de un array

858
00:37:18,570 --> 00:37:20,370
y plop en otro.

859
00:37:20,370 --> 00:37:21,880
>> Entonces, ¿cómo hacemos para hacer esto?

860
00:37:21,880 --> 00:37:24,850
Bueno, déjame seguir adelante y escribir
un programa rápido aquí.

861
00:37:24,850 --> 00:37:31,600
Voy a seguir adelante y hacer
esto como la siguiente.

862
00:37:31,600 --> 00:37:33,910
Llamemos a esto -

863
00:37:33,910 --> 00:37:38,070
¿qué queremos llamar este?

864
00:37:38,070 --> 00:37:38,650
>> En realidad, no.

865
00:37:38,650 --> 00:37:39,420
Permítanme rebobinar.

866
00:37:39,420 --> 00:37:41,220
Yo no quiero hacer eso
Cliffhanger todavía.

867
00:37:41,220 --> 00:37:42,270
Será estropear la diversión.

868
00:37:42,270 --> 00:37:43,600
Vamos a hacer esto en su lugar.

869
00:37:43,600 --> 00:37:47,430
>> Supongamos que yo quiero escribir un poco
programa y que ahora abarca este

870
00:37:47,430 --> 00:37:48,700
idea de recursividad.

871
00:37:48,700 --> 00:37:50,370
Yo como que tengo delante de mí mismo allí.

872
00:37:50,370 --> 00:37:51,420
Voy a hacer lo siguiente.

873
00:37:51,420 --> 00:38:00,220
>> Primero, una rápida incluyen de io.h estándar,
así como incluir de cs50.h.

874
00:38:00,220 --> 00:38:03,200
Y luego voy a seguir adelante
y 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
Me di cuenta de que he mal llamado el archivo, por lo que
permítanme añadir una. extensión c aquí, así

877
00:38:07,920 --> 00:38:09,510
que podemos compilarlo correctamente.

878
00:38:09,510 --> 00:38:10,970
Inicie esta función.

879
00:38:10,970 --> 00:38:13,290
>> Y la función que quiero escribir, bastante
simplemente, es la que pide a la

880
00:38:13,290 --> 00:38:16,210
usuario un número y luego se suma
todos los números entre los que

881
00:38:16,210 --> 00:38:19,920
número y, por ejemplo, 0.

882
00:38:19,920 --> 00:38:22,510
Así que primero voy a seguir adelante
y declarar int n.

883
00:38:22,510 --> 00:38:24,760
A continuación copio un código que
que hemos utilizado durante un tiempo.

884
00:38:24,760 --> 00:38:26,660
Mientras que algo es verdadero.

885
00:38:26,660 --> 00:38:28,000
Voy a volver a eso en un momento.

886
00:38:28,000 --> 00:38:29,010
>> ¿Qué quiero hacer?

887
00:38:29,010 --> 00:38:33,460
Quiero decir printf positivo
entero por favor.

888
00:38:33,460 --> 00:38:36,130
Y luego voy a
dicen que n se hace llegar int.

889
00:38:36,130 --> 00:38:38,800
Así que de nuevo, un poco de código repetitivo
que hemos utilizado antes.

890
00:38:38,800 --> 00:38:40,810
Y yo voy a hacer esto
mientras que n es menor que 1.

891
00:38:40,810 --> 00:38:44,120
Así que esto asegurará que el usuario
me da un número entero positivo.

892
00:38:44,120 --> 00:38:45,490
>> Y ahora voy a hacer lo siguiente.

893
00:38:45,490 --> 00:38:51,020
Quiero sumar todos los números
entre 1 y y n, o 0 y n,

894
00:38:51,020 --> 00:38:52,570
equivalente, para obtener la suma total.

895
00:38:52,570 --> 00:38:55,100
Así el símbolo Sigma grande
que se puede recordar.

896
00:38:55,100 --> 00:38:59,050
Así que voy a hacer esto por primera convocatoria
una función llamada Sigma,

897
00:38:59,050 --> 00:39:06,030
pasándolo n, y luego me voy a
printf decir, la respuesta está ahí.

898
00:39:06,030 --> 00:39:08,180
>> Así que en resumen, lo entiendo y
int del usuario.

899
00:39:08,180 --> 00:39:09,280
Me aseguro de que es positivo.

900
00:39:09,280 --> 00:39:12,700
Declaro una respuesta variable llamada de
tipo int y almacenar en ella el retorno

901
00:39:12,700 --> 00:39:15,610
valor de sigma, pasando n como entrada.

902
00:39:15,610 --> 00:39:17,060
Y luego imprimo esa respuesta.

903
00:39:17,060 --> 00:39:19,550
>> Desafortunadamente, a pesar de que los sonidos sigma
como algo que pudiera estar en

904
00:39:19,550 --> 00:39:24,040
el archivo math.h, su declaración,
en realidad no es.

905
00:39:24,040 --> 00:39:24,690
Así que eso está bien.

906
00:39:24,690 --> 00:39:26,170
Puedo aplicar esto a mí mismo.

907
00:39:26,170 --> 00:39:29,160
Voy a implementar una función llamada
sigma, y ​​que va a tomar un

908
00:39:29,160 --> 00:39:29,900
parámetro -

909
00:39:29,900 --> 00:39:32,100
vamos a llamarlo m, justo
por lo que es diferente.

910
00:39:32,100 --> 00:39:35,910
Y luego aquí, yo voy a decir,
bueno, si m es inferior a 1 - esto es un

911
00:39:35,910 --> 00:39:38,180
programa muy interesante.

912
00:39:38,180 --> 00:39:41,700
Así que voy a seguir adelante y
volver inmediatamente 0.

913
00:39:41,700 --> 00:39:45,920
Simplemente no tiene sentido sumar todos
los números entre 1 y m si m

914
00:39:45,920 --> 00:39:48,470
es en sí mismo 0 o negativo.

915
00:39:48,470 --> 00:39:50,900
>> Y luego voy a seguir adelante
y hacer esto muy iterativa.

916
00:39:50,900 --> 00:39:53,090
Voy a hacer este tipo de la vieja escuela,
y yo voy a seguir adelante

917
00:39:53,090 --> 00:39:57,150
y decir que voy a
declarar una suma a ser 0.

918
00:39:57,150 --> 00:39:59,630
Entonces voy a tener
un bucle de int -

919
00:39:59,630 --> 00:40:02,820
y déjame hacer para que coincida con nuestra
código de distribución, por lo que tiene una copia

920
00:40:02,820 --> 00:40:07,500
en el hogar. int i Obtiene 1 en un máximo de
i es 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
Y luego dentro de este ciclo for -

923
00:40:11,430 --> 00:40:12,440
ya casi estamos allí -

924
00:40:12,440 --> 00:40:15,810
suma se suma más 1.

925
00:40:15,810 --> 00:40:17,670
Y luego voy a devolver la suma.

926
00:40:17,670 --> 00:40:19,420
>> Así que hice esto de manera rápida,
bastante cierto.

927
00:40:19,420 --> 00:40:22,775
Pero, de nuevo, la función principal es bastante
sencillo, basado en el código que hemos

928
00:40:22,775 --> 00:40:23,190
escrito hasta la fecha.

929
00:40:23,190 --> 00:40:25,610
Utiliza el bucle dual para conseguir un resultado positivo
int del usuario.

930
00:40:25,610 --> 00:40:29,870
Luego paso que int a una nueva función
llamado sigma, llamándolo, de nuevo, n.

931
00:40:29,870 --> 00:40:33,100
Y guardo el valor de retorno, la respuesta
Del cuadro negro en la actualidad

932
00:40:33,100 --> 00:40:35,460
conocido como Sigma, en una variable
llamada respuesta.

933
00:40:35,460 --> 00:40:36,580
Luego lo imprimo.

934
00:40:36,580 --> 00:40:39,090
>> Si ahora seguimos la historia,
cómo se implementa sigma?

935
00:40:39,090 --> 00:40:40,840
Propongo para implementar de la siguiente manera.

936
00:40:40,840 --> 00:40:43,560
En primer lugar, un poco de comprobación de errores
para asegurarse de que el usuario no está

937
00:40:43,560 --> 00:40:46,480
jugando conmigo y pasando
otros negativos o valor 0.

938
00:40:46,480 --> 00:40:49,710
Entonces me declaro una variable llamada
suma y ponerlo a 0.

939
00:40:49,710 --> 00:40:55,910
>> Y ahora empiezo a pasar de iguales i
1 todo el camino hasta e incluyendo m,

940
00:40:55,910 --> 00:41:00,130
porque quiero incluir toda la
los números de uno a través de m, inclusive.

941
00:41:00,130 --> 00:41:04,350
Y dentro de este bucle, acabo de hacer
suma consigue lo que sea ahora, además de la

942
00:41:04,350 --> 00:41:08,900
valor de i.

943
00:41:08,900 --> 00:41:10,370
Además, el valor de i.

944
00:41:10,370 --> 00:41:14,090
>> Como acotación al margen, si no has visto esta
antes, hay un poco de azúcar sintáctico

945
00:41:14,090 --> 00:41:14,870
para esta línea.

946
00:41:14,870 --> 00:41:21,120
Puedo reescribir esto como plus iguala i,
sólo para salvarme a mí mismo unas pocas teclas

947
00:41:21,120 --> 00:41:22,570
y mirar un poco más fresco.

948
00:41:22,570 --> 00:41:23,140
Pero eso es todo.

949
00:41:23,140 --> 00:41:24,660
Es funcionalmente lo mismo.

950
00:41:24,660 --> 00:41:26,710
>> Por desgracia, este código es
no va a compilar todavía.

951
00:41:26,710 --> 00:41:31,600
Si ejecuto make sigma 0, ¿cómo soy
Me va a gritar en?

952
00:41:31,600 --> 00:41:33,473
¿Qué va a le gusta?

953
00:41:33,473 --> 00:41:35,740
>> AUDIENCIA: [inaudible].

954
00:41:35,740 --> 00:41:37,800
>> DAVID MALAN: Sí, yo no declaro
parte superior de la función, ¿no?

955
00:41:37,800 --> 00:41:40,590
C es un poco estúpido, ya que sólo
Hace lo que usted diga que haga, y usted

956
00:41:40,590 --> 00:41:41,880
hay que hacerlo en ese orden.

957
00:41:41,880 --> 00:41:45,910
Y así, si golpeo Ingrese aquí, yo voy a
recibirá una advertencia sobre sigma implícita

958
00:41:45,910 --> 00:41:46,860
declaración.

959
00:41:46,860 --> 00:41:48,120
>> Oh, no es un problema.

960
00:41:48,120 --> 00:41:50,370
Puedo subir a la cima, y ​​puedo
por ejemplo, está bien, espera un minuto.

961
00:41:50,370 --> 00:41:54,240
Sigma es una función que devuelve
un entero y se espera una

962
00:41:54,240 --> 00:41:56,620
int como entrada, punto y coma.

963
00:41:56,620 --> 00:41:59,550
O podría poner toda la función
por encima de principal, pero en general, me gustaría

964
00:41:59,550 --> 00:42:02,260
Recomiendo en contra de eso, porque es
agradable tener siempre principal en la parte superior para

965
00:42:02,260 --> 00:42:06,310
usted puede bucear en derecho y saber lo que un
El programa de hacer mediante la lectura principal primero.

966
00:42:06,310 --> 00:42:07,930
>> Así que ahora quiero borrar la pantalla.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Todo parece ir a la salida.

969
00:42:10,340 --> 00:42:11,970
Déjame correr sigma 0.

970
00:42:11,970 --> 00:42:12,770
Entre Positivo.

971
00:42:12,770 --> 00:42:15,580
Voy a darle el número
3 para que sea sencillo.

972
00:42:15,580 --> 00:42:18,710
Así que me debe dar 3
más 2 más 1, por lo que 6.

973
00:42:18,710 --> 00:42:20,750
Entrar, y de hecho me da 6.

974
00:42:20,750 --> 00:42:21,820
>> Puedo hacer algo más grande -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Así como una tangente, yo voy a hacer
algo ridículo como una muy grande

977
00:42:27,690 --> 00:42:30,375
número, Oh, que realmente funcionó -

978
00:42:30,375 --> 00:42:31,600
eh, yo no creo que eso sea correcto.

979
00:42:31,600 --> 00:42:32,810
Vamos a ver.

980
00:42:32,810 --> 00:42:34,060
Vamos realmente meterse con él.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Eso es un problema.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
¿Qué está pasando?

985
00:42:44,970 --> 00:42:46,050
El código no es tan malo.

986
00:42:46,050 --> 00:42:48,470
Todavía es lineal.

987
00:42:48,470 --> 00:42:50,810
Silbar es un buen efecto, sin embargo.

988
00:42:50,810 --> 00:42:52,060
¿Qué está pasando?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> No estoy seguro si lo escuché.

991
00:42:55,620 --> 00:42:57,620
Así que resulta - y
esto es como un aparte.

992
00:42:57,620 --> 00:42:59,400
Este no es el núcleo de la
idea de recursividad.

993
00:42:59,400 --> 00:43:02,480
Resulta que, porque yo estoy tratando de
representan un número tan grande, la mayoría

994
00:43:02,480 --> 00:43:06,980
probablemente está siendo mal interpretado
por C como un número no positiva,

995
00:43:06,980 --> 00:43:09,980
pero el número negativo.

996
00:43:09,980 --> 00:43:12,690
>> No hemos hablado de esto, pero es
Resulta que hay números negativos

997
00:43:12,690 --> 00:43:14,210
en el mundo, además de
a números positivos.

998
00:43:14,210 --> 00:43:16,290
Y el medio por el cual usted puede
representar un número negativo

999
00:43:16,290 --> 00:43:19,530
en esencia, es decir, se utiliza uno
poco especial para indicar

1000
00:43:19,530 --> 00:43:20,400
positivo en negativo.

1001
00:43:20,400 --> 00:43:22,950
Es un poco más complejo que eso,
pero esa es la idea básica.

1002
00:43:22,950 --> 00:43:26,740
>> Así que, lamentablemente, si C es uno confuso
de esos bits como en realidad lo que significa,

1003
00:43:26,740 --> 00:43:30,790
oh, este es un número negativo, mi lazo
aquí, por ejemplo, es en realidad nunca

1004
00:43:30,790 --> 00:43:31,740
va a terminar.

1005
00:43:31,740 --> 00:43:33,850
Así que si yo fuera realmente algo de impresión
una y otra vez, lo haríamos

1006
00:43:33,850 --> 00:43:34,650
ver un montón.

1007
00:43:34,650 --> 00:43:36,220
Pero, de nuevo, este es el punto.

1008
00:43:36,220 --> 00:43:38,590
Esto es en realidad una especie de
curiosidad intelectual que vendremos

1009
00:43:38,590 --> 00:43:39,550
de nuevo a la larga.

1010
00:43:39,550 --> 00:43:43,400
Pero por ahora, esto es una correcta
aplicación si suponemos que el

1011
00:43:43,400 --> 00:43:45,970
usuario proporcionará ints
que encajan dentro de ints.

1012
00:43:45,970 --> 00:43:49,370
>> Pero yo sostengo que este código, francamente,
que se podría hacer mucho más sencilla.

1013
00:43:49,370 --> 00:43:54,060
Si la meta actual es tomar un número
como m y sumar todos los

1014
00:43:54,060 --> 00:43:59,510
los números entre éste y 1, o por el contrario
entre 1 y que, me dicen

1015
00:43:59,510 --> 00:44:03,380
que puedo pedir prestada esta idea de que fusionar
ordenar tenido, que estaba teniendo un problema

1016
00:44:03,380 --> 00:44:05,660
de este tamaño y dividiéndolo
en algo más pequeño.

1017
00:44:05,660 --> 00:44:09,875
Quizás no es un medio, pero más pequeño, pero
de manera representativa del mismo.

1018
00:44:09,875 --> 00:44:12,130
La misma idea, pero un problema menor.

1019
00:44:12,130 --> 00:44:15,470
>> Así que estoy realmente - me deja guardar este archivo
con un número de versión diferente.

1020
00:44:15,470 --> 00:44:17,670
Vamos a llamar a esta versión
1 en lugar de 0.

1021
00:44:17,670 --> 00:44:20,790
Y pretender que puedo realmente
volver a implementar esto en este tipo de

1022
00:44:20,790 --> 00:44:22,160
endiablada manera.

1023
00:44:22,160 --> 00:44:23,710
>> Voy a dejar parte de su cuenta.

1024
00:44:23,710 --> 00:44:27,710
Voy a decir que si m es menor
que o incluso igual a 0 -

1025
00:44:27,710 --> 00:44:29,280
Yo sólo voy a ser un poco
más anal esta vez

1026
00:44:29,280 --> 00:44:30,520
con mi comprobación de errores -

1027
00:44:30,520 --> 00:44:33,190
Voy a seguir adelante y devolver 0.

1028
00:44:33,190 --> 00:44:34,490
Este es arbitraria.

1029
00:44:34,490 --> 00:44:37,500
Estoy simplemente decidiendo si el usuario
me da un número negativo, estoy

1030
00:44:37,500 --> 00:44:41,490
devolviendo un 0, y que debería haber leído
la documentación de más de cerca.

1031
00:44:41,490 --> 00:44:42,170
>> Otras ventas -

1032
00:44:42,170 --> 00:44:44,070
cuenta de lo que voy a hacer.

1033
00:44:44,070 --> 00:44:49,260
Else voy a volver m plus -

1034
00:44:49,260 --> 00:44:51,010
lo que es sigma de m?

1035
00:44:51,010 --> 00:44:56,710
Bueno, sigma de m + d menos 1,
plus minus m 2, más menos 3 m.

1036
00:44:56,710 --> 00:44:58,030
Yo no quiero escribir todo eso a cabo.

1037
00:44:58,030 --> 00:44:59,120
¿Por qué no acaba de Punt?

1038
00:44:59,120 --> 00:45:05,080
Llame recursivamente a mí mismo con un poco
más pequeño problema, punto y coma,

1039
00:45:05,080 --> 00:45:06,840
y lo llaman un día?

1040
00:45:06,840 --> 00:45:07,040
>> ¿Cierto?

1041
00:45:07,040 --> 00:45:10,980
Ahora aquí, también, se puede sentir o preocuparse
que este es un bucle infinito que estoy

1042
00:45:10,980 --> 00:45:15,450
inducir, en el que me estoy poniendo en práctica
Sigma llamando Sigma.

1043
00:45:15,450 --> 00:45:20,342
Pero eso es perfectamente correcto, porque yo
pensado por delante un qué líneas añadidas?

1044
00:45:20,342 --> 00:45:22,600
>> AUDIENCIA: [inaudible].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID MALAN: 23 a 26, que
es mi condición if.

1046
00:45:25,430 --> 00:45:28,390
Porque lo bueno de la
resta aquí, porque he guardado

1047
00:45:28,390 --> 00:45:31,180
entrega sigma problemas más pequeños, más pequeña
problemas, más pequeña - no es

1048
00:45:31,180 --> 00:45:31,870
la mitad del tamaño.

1049
00:45:31,870 --> 00:45:34,380
Es sólo un pequeño paso más pequeño,
pero eso está bien.

1050
00:45:34,380 --> 00:45:38,050
Debido a que con el tiempo, vamos a trabajar
nuestro camino a 1 o 0.

1051
00:45:38,050 --> 00:45:41,630
Y una vez que llegamos a 0, sigma no es
pasando a llamarse más.

1052
00:45:41,630 --> 00:45:43,590
Se va a volver inmediatamente 0.

1053
00:45:43,590 --> 00:45:47,960
>> Así que el efecto, si el viento esta especie de
en su mente, es añadir m más

1054
00:45:47,960 --> 00:45:52,740
m menos 1, más m menos 2, más m menos
3, además de punto, punto, punto, m menos

1055
00:45:52,740 --> 00:45:57,820
m, con el tiempo que le da 0, y el
efecto es en última instancia, para agregar todos los

1056
00:45:57,820 --> 00:45:59,070
estas cosas juntas.

1057
00:45:59,070 --> 00:46:02,380
Así que no tenemos, con la recursividad,
resuelto el problema que nos

1058
00:46:02,380 --> 00:46:03,470
no podría resolver antes.

1059
00:46:03,470 --> 00:46:06,840
De hecho, la versión 0 de este, y cada
problema hasta la fecha, ha sido solucionable

1060
00:46:06,840 --> 00:46:09,980
con sólo usar bucles o mientras
bucles o construcciones similares.

1061
00:46:09,980 --> 00:46:13,150
>> Pero la recursividad, me atrevo a decir, nos da
una manera diferente de pensar sobre

1062
00:46:13,150 --> 00:46:17,010
problemas, por lo que si podemos tomar un
problema, dividirla de algo

1063
00:46:17,010 --> 00:46:22,340
algo grande en algo un tanto
más pequeña, afirmo que podemos resolverlo

1064
00:46:22,340 --> 00:46:26,040
tal vez un poco más elegante en términos
del diseño, con menos código,

1065
00:46:26,040 --> 00:46:30,980
y tal vez incluso resolver los problemas que lo haría
ser más difícil, ya que finalmente va a

1066
00:46:30,980 --> 00:46:33,280
ver, la solución puramente de forma iterativa.

1067
00:46:33,280 --> 00:46:35,980
>> Pero el drama de suspenso que lo hice
quiere dejar a nosotros en esta era.

1068
00:46:35,980 --> 00:46:40,720
Déjenme seguir adelante y abrir
un archivo desde -

1069
00:46:40,720 --> 00:46:44,300
En realidad, me dejó ir y
hacer esto muy rápido.

1070
00:46:44,300 --> 00:46:46,875
Déjame ir adelante y propongo
el siguiente.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Entre el código de hoy es el archivo aquí.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Este de aquí, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Así que este es un pequeño programa que estúpido
Saqué hasta que pretende hacer

1076
00:47:06,260 --> 00:47:06,940
el siguiente.

1077
00:47:06,940 --> 00:47:10,140
En principal, primero declara una
int llamado x y le asigna

1078
00:47:10,140 --> 00:47:11,100
el valor de 1.

1079
00:47:11,100 --> 00:47:13,520
Entonces se declara un int y y
asigna el valor 2.

1080
00:47:13,520 --> 00:47:15,310
Luego se imprime lo que x e y es.

1081
00:47:15,310 --> 00:47:17,781
Entonces dice: intercambio, punto punto punto.

1082
00:47:17,781 --> 00:47:21,670
>> Entonces se dice que está llamando a una función
denominada swap, que pasa en x y

1083
00:47:21,670 --> 00:47:24,290
y, la idea de que es de esperar que
x e y volverá

1084
00:47:24,290 --> 00:47:25,620
diferente, lo contrario.

1085
00:47:25,620 --> 00:47:27,110
Entonces reclamo cambió!

1086
00:47:27,110 --> 00:47:28,420
con un signo de exclamación.

1087
00:47:28,420 --> 00:47:30,190
Luego imprime xe y.

1088
00:47:30,190 --> 00:47:33,480
>> Pero resulta que esta misma
simple demostración abajo

1089
00:47:33,480 --> 00:47:35,570
aquí es realmente buggy.

1090
00:47:35,570 --> 00:47:38,870
Aunque estoy declarando un temporal
variable y poner temporalmente en una

1091
00:47:38,870 --> 00:47:42,010
, entonces yo estoy reasignando
un valor de b -

1092
00:47:42,010 --> 00:47:45,080
que se siente razonable, porque he
guardado una copia de un temporal en.

1093
00:47:45,080 --> 00:47:48,410
Entonces puedo actualizar b a la igualdad de
lo que estaba en temp.

1094
00:47:48,410 --> 00:47:51,610
Este tipo de juego de la cáscara de mover un
en B y B en una mediante el uso de este

1095
00:47:51,610 --> 00:47:54,360
medio-hombre llamado temp siente
perfectamente razonable.

1096
00:47:54,360 --> 00:47:57,270
>> Pero yo sostengo que cuando ejecuto esta
código, ya que voy a hacer ahora -

1097
00:47:57,270 --> 00:47:59,490
déjame ir adelante y pegarlo aquí.

1098
00:47:59,490 --> 00:48:01,995
Voy a llamar a este noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Y como su nombre indica, este no es
va a ser un programa correcto.

1100
00:48:05,630 --> 00:48:09,460
Hacer noswap. / No swap.

1101
00:48:09,460 --> 00:48:12,110
x es 1, y es 2, el intercambio, intercambiado.

1102
00:48:12,110 --> 00:48:14,220
x es 1, Y es 2.

1103
00:48:14,220 --> 00:48:16,920
Esto es un error fundamental, incluso
aunque esto parece perfectamente

1104
00:48:16,920 --> 00:48:17,730
razonable para mí.

1105
00:48:17,730 --> 00:48:21,330
Y hay una razón, pero no estamos
va a revelar la razón por el momento.

1106
00:48:21,330 --> 00:48:24,610
>> Por ahora el segundo melodrama que quería
a dejar es esto, un

1107
00:48:24,610 --> 00:48:27,120
anuncio de tipos de bonos de descuento.

1108
00:48:27,120 --> 00:48:31,590
Nuestra innovación con los días finales de este año
ha provocado un número no trivial

1109
00:48:31,590 --> 00:48:33,830
de preguntas, que era
no nuestra intención.

1110
00:48:33,830 --> 00:48:36,590
La intención de estos bonos de descuento,
por el que si lo haces parte del problema

1111
00:48:36,590 --> 00:48:39,850
establecer temprana, consiguiendo así un día adicional,
fue realmente para ayudar a ustedes Ayuda

1112
00:48:39,850 --> 00:48:42,420
mismo comienzo temprano, más o menos
de al incentivar usted.

1113
00:48:42,420 --> 00:48:44,880
Nos ayuda a distribuir la carga entre
horario de oficina mejor para que

1114
00:48:44,880 --> 00:48:45,740
Es una especie de ganar-ganar.

1115
00:48:45,740 --> 00:48:48,860
>> Por desgracia, creo que mis instrucciones
no han sido, hasta la fecha, muy clara, por lo que

1116
00:48:48,860 --> 00:48:52,230
Volví este fin de semana y actualizado
la especificación en el más grande, más audaz para el texto

1117
00:48:52,230 --> 00:48:53,600
explicar las balas como estos.

1118
00:48:53,600 --> 00:48:56,900
Y para decirlo más públicamente, por
De forma predeterminada, los boletines de problemas se deben Jueves

1119
00:48:56,900 --> 00:48:58,400
al mediodía, por el plan de estudios.

1120
00:48:58,400 --> 00:49:02,030
Si comienza temprano, terminando parte de
el problema fijado para el miércoles a las 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, la parte que se refiere a un cupón
Código, la idea es que se puede extender

1122
00:49:05,170 --> 00:49:07,710
el plazo para la
P fijó hasta el viernes.

1123
00:49:07,710 --> 00:49:10,890
Es decir, el bit de una pequeña parte de la P
establecido en relación a lo que normalmente es el

1124
00:49:10,890 --> 00:49:13,200
mayor problema, y ​​usted compra
usted mismo un día extra.

1125
00:49:13,200 --> 00:49:15,190
Una vez más, se pone a pensar acerca de
el problema planteado, se llega a

1126
00:49:15,190 --> 00:49:16,380
las horas de oficina antes.

1127
00:49:16,380 --> 00:49:20,670
Pero el problema sigue siendo el código de cupón
necesario, incluso si usted no los pongas.

1128
00:49:20,670 --> 00:49:23,340
>> Pero lo más convincente es la siguiente.

1129
00:49:23,340 --> 00:49:26,520
(ETAPA WHISPER) Y esas personas que salen
temprano van a lamentarlo.

1130
00:49:26,520 --> 00:49:28,620
Como son las personas en el balcón.

1131
00:49:28,620 --> 00:49:32,510
Pido disculpas de antemano a la gente en
el balcón por razones que serán

1132
00:49:32,510 --> 00:49:33,920
borrar en un momento.

1133
00:49:33,920 --> 00:49:37,050
>> Así que tenemos la suerte de tener uno de
Ex becarios de enseñanza en la cabeza del CS50

1134
00:49:37,050 --> 00:49:39,302
una empresa llamada dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Ellos han donado generosamente un
código aquí cupón para este espacio,

1136
00:49:45,500 --> 00:49:48,180
que es a partir de la
habituales 2 gigabytes.

1137
00:49:48,180 --> 00:49:51,740
Así que lo que yo pensaba que íbamos a hacer en este
nota final es hacer un poco de un sorteo,

1138
00:49:51,740 --> 00:49:55,380
por lo que en un momento, vamos a revelar
el ganador y quién tiene un cupón

1139
00:49:55,380 --> 00:49:57,980
código que luego se puede ir a su
sitio web, escribirlo, y listo, conseguir un

1140
00:49:57,980 --> 00:50:01,370
mucho más espacio Dropbox para su
aparato y para sus archivos personales.

1141
00:50:01,370 --> 00:50:05,690
>> Y en primer lugar, que quiere participar
en este dibujo?

1142
00:50:05,690 --> 00:50:09,630
Bien, ahora que lo hace aún más divertido.

1143
00:50:09,630 --> 00:50:14,010
La persona que recibe este 25 gigabytes
código de descuento - que es mucho

1144
00:50:14,010 --> 00:50:16,150
más convincente que el difunto
día ahora, tal vez -

1145
00:50:16,150 --> 00:50:20,620
es el que está sentado en la parte superior de un
cojín del asiento por debajo de la cual hay

1146
00:50:20,620 --> 00:50:21,620
que el código de cupón.

1147
00:50:21,620 --> 00:50:23,480
Ahora puede mirar debajo
el cojín del asiento.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [REPRODUCCIÓN DE VÍDEO]

1150
00:50:29,680 --> 00:50:31,620
>> -Uno, dos, tres.

1151
00:50:31,620 --> 00:50:35,015
>> [GRITA]

1152
00:50:35,015 --> 00:50:35,985
>> -Usted recibe un coche!

1153
00:50:35,985 --> 00:50:36,670
Usted consigue un coche!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID MALAN: Veremos
que el miércoles.

1155
00:50:37,970 --> 00:50:38,904
>> -Usted recibe un coche!

1156
00:50:38,904 --> 00:50:39,371
Usted consigue un coche!

1157
00:50:39,371 --> 00:50:40,305
Usted consigue un coche!

1158
00:50:40,305 --> 00:50:41,706
Usted consigue un coche!

1159
00:50:41,706 --> 00:50:43,107
Usted consigue un coche!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID MALAN: gente Balcón, vienen
aquí abajo en la parte delantera,

1161
00:50:45,530 --> 00:50:46,866
donde tenemos extras.

1162
00:50:46,866 --> 00:50:50,282
>> -Todo el mundo tiene un coche!

1163
00:50:50,282 --> 00:50:52,234
Todo el mundo tiene un coche!

1164
00:50:52,234 --> 00:50:52,722
>> [VIDEO PLAYBACK FIN]

1165
00:50:52,722 --> 00:50:54,590
>> NARRADOR: En la próxima CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> ALTAVOZ 5: Oh, Dios mío Dios mío Dios mío Dios mío
caramba caramba caramba caramba caramba caramba -

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE JUEGOS]