1
00:00:00,000 --> 00:00:11,904
>> [REPRODUCCIÓN DE MÚSICA]

2
00:00:11,904 --> 00:00:12,910
>> PROFESOR: Muy bien.

3
00:00:12,910 --> 00:00:16,730
Esto es CS50 y esto es
Al final de la tercera semana.

4
00:00:16,730 --> 00:00:20,230
Así que estamos aquí hoy, no en Sanders
Teatro, en lugar de Weidner Biblioteca.

5
00:00:20,230 --> 00:00:23,170
En el interior de los cuales es un estudio
conocido como Hauser de estudio,

6
00:00:23,170 --> 00:00:28,310
o mejor dicho Estudio H, o irán
que decir-- si te gustó la broma,

7
00:00:28,310 --> 00:00:30,540
en realidad es de
compañero, Mark, en línea,

8
00:00:30,540 --> 00:00:32,420
quien sugirió tanto a través de Twitter.

9
00:00:32,420 --> 00:00:34,270
Ahora lo bueno de
estar aquí en un estudio

10
00:00:34,270 --> 00:00:38,410
es que estoy rodeado de estos de verde
paredes, una pantalla verde o chromakey,

11
00:00:38,410 --> 00:00:43,290
por así decirlo, lo que significa que CS50 de
equipo de producción, sin yo saberlo

12
00:00:43,290 --> 00:00:47,380
en este momento, podría ser poner
más me cualquier parte del mundo,

13
00:00:47,380 --> 00:00:48,660
Para bien o para mal.

14
00:00:48,660 --> 00:00:51,800
>> Ahora lo que se avecina, establece problema
dos es en sus manos para esta semana,

15
00:00:51,800 --> 00:00:53,830
pero con el problema de establecer
de tres esta semana que viene,

16
00:00:53,830 --> 00:00:56,600
serás retado con
el llamado juego de 15,

17
00:00:56,600 --> 00:00:58,960
un viejo partido a favor de que
se puede recordar que recibe

18
00:00:58,960 --> 00:01:02,030
como un niño que tiene un montón
de números que se pueden deslizar hacia arriba, abajo,

19
00:01:02,030 --> 00:01:05,790
izquierda y derecha, y hay una brecha
dentro del rompecabezas, en el que

20
00:01:05,790 --> 00:01:07,840
puede deslizarse en realidad esas piezas del rompecabezas.

21
00:01:07,840 --> 00:01:11,150
En última instancia recibe este
rompecabezas en algún orden semi aleatoria,

22
00:01:11,150 --> 00:01:12,940
y el objetivo es
ordenarla, de arriba abajo,

23
00:01:12,940 --> 00:01:16,310
izquierda a derecha, de un
todo el camino a través de 15.

24
00:01:16,310 --> 00:01:19,360
>> Desafortunadamente, la implementación
tendrás a la mano

25
00:01:19,360 --> 00:01:21,590
va a ser el software
basado, no físicamente.

26
00:01:21,590 --> 00:01:25,280
Usted está en realidad va a tener que escribir
código con el que un estudiante o usuario lata

27
00:01:25,280 --> 00:01:26,760
jugar el juego de los 15.

28
00:01:26,760 --> 00:01:29,030
Y de hecho, en el hacker
edición del juego de 15,

29
00:01:29,030 --> 00:01:32,155
usted será un desafío para poner en práctica,
no sólo el juego de esta vieja escuela

30
00:01:32,155 --> 00:01:35,010
juego, sino más bien la resolución
de ello, la aplicación de modo de dios,

31
00:01:35,010 --> 00:01:38,280
por así decirlo, que de hecho
resuelve el rompecabezas para el ser humano,

32
00:01:38,280 --> 00:01:41,080
poniendo a su pista,
después de pista, después toque.

33
00:01:41,080 --> 00:01:42,280
Así que más en que la próxima semana.

34
00:01:42,280 --> 00:01:43,720
Pero eso es lo que nos espera.

35
00:01:43,720 --> 00:01:47,610
>> Por ahora recordar que a principios de esta semana
hemos tenido este melodrama, si se quiere,

36
00:01:47,610 --> 00:01:52,560
por lo que el mejor que estábamos haciendo la clasificación
sabia era una cota superior de grande o de n

37
00:01:52,560 --> 00:01:53,210
al cuadrado.

38
00:01:53,210 --> 00:01:56,520
En otras palabras, ordenamiento de burbuja,
ordenación por selección, ordenación por inserción,

39
00:01:56,520 --> 00:01:59,120
todos ellos, mientras diferente
en su aplicación,

40
00:01:59,120 --> 00:02:03,480
degenerado en un cuadrado n corriendo
tiempo en el peor de los casos.

41
00:02:03,480 --> 00:02:06,010
Y por lo general, suponemos que
el peor de los casos para la clasificación

42
00:02:06,010 --> 00:02:08,814
es uno que sus entradas
son completamente al revés.

43
00:02:08,814 --> 00:02:11,980
Y, de hecho, le tomó unos cuantos pasos
para poner en práctica cada uno de los algoritmos.

44
00:02:11,980 --> 00:02:15,110
>> Ahora en el final de la clase
revocatorio, comparamos ordenamiento de burbuja

45
00:02:15,110 --> 00:02:19,390
contra la ordenación por selección contra otro
que llamamos de combinación de clase en el momento,

46
00:02:19,390 --> 00:02:22,120
y yo propongo que está tomando
ventaja de una lección de la semana

47
00:02:22,120 --> 00:02:24,060
cero, divide y vencerás.

48
00:02:24,060 --> 00:02:28,810
Y de alguna manera lograr algún tipo de
logarítmica tiempo de funcionamiento en última instancia,

49
00:02:28,810 --> 00:02:31,024
en lugar de algo
eso es puramente cuadrática.

50
00:02:31,024 --> 00:02:33,440
Y no es bastante logarítmica,
que es un poco más que eso.

51
00:02:33,440 --> 00:02:36,520
Pero si usted recuerda de la clase,
era mucho, mucho más rápido.

52
00:02:36,520 --> 00:02:38,210
Echemos un vistazo a donde lo dejamos.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Burbuja tipo contra la selección
tipo de combinación frente especie.

55
00:02:45,370 --> 00:02:47,700
Ahora están todos corriendo, en
teoría, al mismo tiempo.

56
00:02:47,700 --> 00:02:50,510
La CPU está funcionando a la misma velocidad.

57
00:02:50,510 --> 00:02:54,990
Pero se puede sentir lo aburrido esto
va muy rápidamente para convertirse,

58
00:02:54,990 --> 00:02:58,790
y la rapidez, cuando inyectamos
un poco de algoritmos semana de cero,

59
00:02:58,790 --> 00:03:00,080
podemos acelerar las cosas.

60
00:03:00,080 --> 00:03:01,630
>> Así especie marca se ve increíble.

61
00:03:01,630 --> 00:03:05,220
¿Cómo podemos aprovechar que, con el fin
para ordenar los números más rápidamente.

62
00:03:05,220 --> 00:03:07,140
Bueno vamos a pensar en volver
a un ingrediente que

63
00:03:07,140 --> 00:03:10,380
tenía de vuelta en semanas cero, el de
buscando a alguien en una guía telefónica,

64
00:03:10,380 --> 00:03:12,380
y recordar que el
pseudocódigo que propusimos,

65
00:03:12,380 --> 00:03:14,560
a través del cual podemos encontrar
alguien como Mike Smith,

66
00:03:14,560 --> 00:03:16,310
parecía un poco algo como esto.

67
00:03:16,310 --> 00:03:20,820
>> Ahora echa un vistazo en particular,
en la línea 7 y 8, y 10 y 11,

68
00:03:20,820 --> 00:03:25,240
que inducen ese bucle, en el que mantuvimos
que se remonta a la línea 3 de nuevo, y otra vez,

69
00:03:25,240 --> 00:03:26,520
y otra vez.

70
00:03:26,520 --> 00:03:31,790
Pero resulta que podemos ver
este algoritmo, aquí en pseudocódigo,

71
00:03:31,790 --> 00:03:33,620
un poco más de manera integral.

72
00:03:33,620 --> 00:03:35,960
De hecho, lo que estoy buscando
por lo que aquí en la pantalla,

73
00:03:35,960 --> 00:03:41,180
es un algoritmo para la búsqueda de
Mike Smith, entre un conjunto de páginas.

74
00:03:41,180 --> 00:03:45,520
Y de hecho, podríamos simplificar este
algoritmo en esas líneas 7 y 8,

75
00:03:45,520 --> 00:03:49,860
y 10 y 11 a sólo decir esto,
que he presentado aquí en amarillo.

76
00:03:49,860 --> 00:03:52,210
En otras palabras, si Mike
Smith es anterior en el libro,

77
00:03:52,210 --> 00:03:55,004
no necesitamos especificar paso
a paso ahora cómo ir a buscarlo.

78
00:03:55,004 --> 00:03:56,920
No tenemos que especificar
para volver a la línea 3,

79
00:03:56,920 --> 00:03:58,960
¿Por qué no simplemente en su lugar,
por ejemplo, más en general,

80
00:03:58,960 --> 00:04:01,500
buscar Mike en el
media izquierda del libro.

81
00:04:01,500 --> 00:04:03,960
>> A la inversa, si Mike es
en realidad más adelante en el libro,

82
00:04:03,960 --> 00:04:07,540
¿por qué no acabamos de citar búsqueda fin de la cita
Mike en la mitad derecha del libro.

83
00:04:07,540 --> 00:04:11,030
En otras palabras, ¿por qué no lo hacemos sólo
especie de batea a nosotros mismos diciendo:

84
00:04:11,030 --> 00:04:13,130
buscar Mike en este
subconjunto del libro,

85
00:04:13,130 --> 00:04:16,279
y dejar que nuestros actuales
algoritmo que nos diga

86
00:04:16,279 --> 00:04:18,750
cómo buscar Mike en
que la mitad izquierda del libro.

87
00:04:18,750 --> 00:04:20,750
En otras palabras, nuestra
algoritmo funciona ya sea

88
00:04:20,750 --> 00:04:24,670
una libreta de teléfonos de este espesor, de esta
espesor, o cualquier espesor que sea.

89
00:04:24,670 --> 00:04:27,826
Así que lo que podamos de forma recursiva
definir este algoritmo.

90
00:04:27,826 --> 00:04:29,950
En otras palabras, en el
pantalla de aquí, es un algoritmo

91
00:04:29,950 --> 00:04:33,130
para la búsqueda de Mike Smith
entre las páginas de un libro de teléfono.

92
00:04:33,130 --> 00:04:37,410
Así, en la línea 7 y 10, vamos a
a decir exactamente eso.

93
00:04:37,410 --> 00:04:40,250
Y utilizo este término un momento
Hace, y de hecho, la recursión

94
00:04:40,250 --> 00:04:42,450
es la palabra de moda, por ahora,
y es este proceso

95
00:04:42,450 --> 00:04:47,210
de hacer algo cíclico de alguna manera
utilizando el código que ya tiene,

96
00:04:47,210 --> 00:04:49,722
y decir que es nuevo,
y otra vez, y otra vez.

97
00:04:49,722 --> 00:04:51,930
Ahora que va a ser importante
que de alguna manera inferior

98
00:04:51,930 --> 00:04:53,821
fuera, y no hagas eso infinitamente largo.

99
00:04:53,821 --> 00:04:56,070
De lo contrario, vamos a
tienen de hecho un bucle infinito.

100
00:04:56,070 --> 00:04:59,810
Pero vamos a ver si podemos pedir prestada esta idea
de un recursividad, hacer algo nuevo

101
00:04:59,810 --> 00:05:03,600
y una y otra vez, para resolver
el problema de clasificación a través de combinación

102
00:05:03,600 --> 00:05:05,900
Ordena, toda la manera más eficiente.

103
00:05:05,900 --> 00:05:06,970
>> Así que le doy combinar tipo.

104
00:05:06,970 --> 00:05:07,920
Echemos un vistazo.

105
00:05:07,920 --> 00:05:10,850
Así que aquí es pseudocódigo, con
que podríamos aplicar la clasificación,

106
00:05:10,850 --> 00:05:12,640
el uso de este algoritmo llamado fusión tipo.

107
00:05:12,640 --> 00:05:13,880
Y es simplemente esto.

108
00:05:13,880 --> 00:05:15,940
En la entrada de n elementos,
en otras palabras, si usted es

109
00:05:15,940 --> 00:05:18,830
dada n elementos y números y
cartas o lo que la entrada es,

110
00:05:18,830 --> 00:05:22,430
si te dan n elementos, si
n es menor que 2, simplemente volver.

111
00:05:22,430 --> 00:05:22,930
¿Correcto?

112
00:05:22,930 --> 00:05:26,430
Porque si n es menor que 2, que
significa que mi lista de elementos

113
00:05:26,430 --> 00:05:30,446
es cualquiera de tamaño 0 o 1, y
en ambos casos triviales,

114
00:05:30,446 --> 00:05:31,570
la lista ya está ordenado.

115
00:05:31,570 --> 00:05:32,810
Si no hay una lista, es ordenada.

116
00:05:32,810 --> 00:05:35,185
Y si hay una lista de longitud
1, es obviamente ordenado.

117
00:05:35,185 --> 00:05:38,280
Así que el algoritmo sólo necesita
realmente hacer algo interesante,

118
00:05:38,280 --> 00:05:40,870
si tenemos dos o más
elementos dados a nosotros.

119
00:05:40,870 --> 00:05:42,440
Así que echemos un vistazo a la magia entonces.

120
00:05:42,440 --> 00:05:47,500
Else ordenar la mitad izquierda de los elementos,
a continuación, ordenar la mitad derecha de los elementos,

121
00:05:47,500 --> 00:05:49,640
luego fusionar las mitades ordenados.

122
00:05:49,640 --> 00:05:52,440
Y lo que es clase de mente flexión
aquí, es que realmente no me

123
00:05:52,440 --> 00:05:56,190
parecen que han dicho
nada todavía, ¿verdad?

124
00:05:56,190 --> 00:05:59,560
Todo lo que he dicho es, dada una lista de
n elementos, ordenar la mitad izquierda,

125
00:05:59,560 --> 00:06:01,800
entonces la mitad derecha, a continuación,
fusionar las mitades ordenados,

126
00:06:01,800 --> 00:06:03,840
pero ¿dónde está el ingrediente secreto real?

127
00:06:03,840 --> 00:06:05,260
¿Dónde está el algoritmo?

128
00:06:05,260 --> 00:06:09,150
Pues resulta que esas dos líneas
primero, ordenar la izquierda de la mitad de los elementos,

129
00:06:09,150 --> 00:06:13,970
y tipo adecuado medio de elementos,
son llamadas recursivas, por así decirlo.

130
00:06:13,970 --> 00:06:16,120
>> Después de todo, en este
punto en el tiempo, ¿tengo

131
00:06:16,120 --> 00:06:18,950
un algoritmo con el cual
ordenar un montón de elementos?

132
00:06:18,950 --> 00:06:19,450
Sí.

133
00:06:19,450 --> 00:06:20,620
Es justo aquí.

134
00:06:20,620 --> 00:06:25,180
Es aquí en la pantalla, y
así que puedo usar ese mismo conjunto de medidas

135
00:06:25,180 --> 00:06:28,500
para ordenar la mitad izquierda,
como puedo la mitad derecha.

136
00:06:28,500 --> 00:06:30,420
Y, en efecto, de nuevo, una y otra vez.

137
00:06:30,420 --> 00:06:34,210
Así que de alguna manera u otra, y que pronto
ver esto, la magia de la combinación de tipo

138
00:06:34,210 --> 00:06:37,967
está incrustado en ese mismo definitiva
línea, la fusión de las mitades ordenadas.

139
00:06:37,967 --> 00:06:39,300
Y eso parece bastante intuitivo.

140
00:06:39,300 --> 00:06:41,050
Usted toma dos mitades, y tú,
de alguna manera, unirlos,

141
00:06:41,050 --> 00:06:43,260
y vamos a ver esto
concretamente en un momento.

142
00:06:43,260 --> 00:06:45,080
>> Pero este es un algoritmo completo.

143
00:06:45,080 --> 00:06:46,640
Y vamos a ver exactamente por qué.

144
00:06:46,640 --> 00:06:50,912
Bueno supongamos que nos dan estos mismos
ocho elementos aquí en la pantalla, uno

145
00:06:50,912 --> 00:06:53,120
a través de ocho, pero son
con el fin aparentemente al azar.

146
00:06:53,120 --> 00:06:55,320
Y el objetivo que nos ocupa es
para ordenar estos elementos.

147
00:06:55,320 --> 00:06:58,280
Bueno, ¿cómo puedo ir sobre
hacerlo utilizando, de nuevo,

148
00:06:58,280 --> 00:07:00,407
ordenamiento por mezcla, según este pseudocódigo?

149
00:07:00,407 --> 00:07:02,740
Y de nuevo, arraigar esto en
su mente, sólo por un momento.

150
00:07:02,740 --> 00:07:05,270
El primer caso es bastante
trivial, si es menos de 2,

151
00:07:05,270 --> 00:07:07,060
simplemente volver, no hay trabajo por hacer.

152
00:07:07,060 --> 00:07:09,290
Así que en realidad hay sólo tres
medidas para mantener muy en cuenta.

153
00:07:09,290 --> 00:07:11,081
Una vez más, y otra vez, estoy
va a querer tener

154
00:07:11,081 --> 00:07:13,980
para ordenar la mitad izquierda,
ordenar la mitad derecha,

155
00:07:13,980 --> 00:07:15,890
y luego una vez su
dos mitades están ordenados,

156
00:07:15,890 --> 00:07:18,710
Quiero unirlos
en una lista ordenada.

157
00:07:18,710 --> 00:07:19,940
Así que tenlo en mente.

158
00:07:19,940 --> 00:07:21,310
>> Así que aquí está la lista original.

159
00:07:21,310 --> 00:07:23,510
Vamos a tratar esto como una
matriz, como empezamos a

160
00:07:23,510 --> 00:07:25,800
en la segunda semana, que es un
bloque contiguo de memoria.

161
00:07:25,800 --> 00:07:28,480
En este caso, que contiene ocho
números, espalda con espalda con espalda.

162
00:07:28,480 --> 00:07:30,700
Y ahora vamos a aplicar fusión tipo.

163
00:07:30,700 --> 00:07:33,300
Así que primero quiero ordenar
la mitad izquierda de esta lista,

164
00:07:33,300 --> 00:07:37,370
y dejar de, por lo tanto,
centrarse en 4, 8, 6, y 2.

165
00:07:37,370 --> 00:07:41,000
>> Ahora, ¿cómo hago para
ordenar una lista de tamaño de 4?

166
00:07:41,000 --> 00:07:45,990
Bueno tengo que considerar ahora
la clasificación de la izquierda de la mitad izquierda.

167
00:07:45,990 --> 00:07:47,720
Una vez más, vamos a retroceder por un momento.

168
00:07:47,720 --> 00:07:51,010
Si el pseudocódigo es esto,
y me dan ocho elementos,

169
00:07:51,010 --> 00:07:53,230
8 es obviamente mayor
que o igual a 2.

170
00:07:53,230 --> 00:07:54,980
Así que con el primer caso no se aplica.

171
00:07:54,980 --> 00:07:58,120
Así que para clasificar ocho elementos, yo primero
ordenar la mitad izquierda de elementos,

172
00:07:58,120 --> 00:08:01,930
entonces puedo ordenar la mitad derecha, luego me fusiono
las dos mitades ordenadas, cada una del tamaño de 4.

173
00:08:01,930 --> 00:08:02,470
OK.

174
00:08:02,470 --> 00:08:07,480
>> Pero si lo que me has dicho, ordenar la
mitad izquierda, que ahora es de tamaño 4,

175
00:08:07,480 --> 00:08:09,350
¿Cómo puedo ordenar el medio queda?

176
00:08:09,350 --> 00:08:11,430
Bueno, si tengo una
de entrada de cuatro elementos,

177
00:08:11,430 --> 00:08:14,590
Yo primero ordenar la izquierda
dos, y luego los dos a la derecha,

178
00:08:14,590 --> 00:08:16,210
y luego unirlos.

179
00:08:16,210 --> 00:08:18,700
Así que de nuevo, se vuelve un poco
de una mente de flexión juego aquí,

180
00:08:18,700 --> 00:08:21,450
porque, clase de, que
recordar dónde usted está en la historia,

181
00:08:21,450 --> 00:08:23,620
pero al final del día,
dado cualquier número de elementos,

182
00:08:23,620 --> 00:08:25,620
que primero desea ordenar la
medio izquierdo, luego la mitad derecha,

183
00:08:25,620 --> 00:08:26,661
luego unirlos.

184
00:08:26,661 --> 00:08:28,630
Vamos a empezar a hacer exactamente eso.

185
00:08:28,630 --> 00:08:30,170
Aquí está la entrada de ocho elementos.

186
00:08:30,170 --> 00:08:31,910
Ahora estamos viendo la mitad izquierda aquí.

187
00:08:31,910 --> 00:08:33,720
¿Cómo puedo ordenar cuatro elementos?

188
00:08:33,720 --> 00:08:35,610
Bueno, yo primero ordenar el medio izquierdo.

189
00:08:35,610 --> 00:08:37,720
Ahora, ¿cómo puedo ordenar el medio queda?

190
00:08:37,720 --> 00:08:39,419
Bueno me han dado dos elementos.

191
00:08:39,419 --> 00:08:41,240
Así que vamos a ordenar estos dos elementos.

192
00:08:41,240 --> 00:08:44,540
2 es mayor o
igual a 2, por supuesto.

193
00:08:44,540 --> 00:08:46,170
Así que el primer caso no se aplica.

194
00:08:46,170 --> 00:08:49,010
>> Así que ahora tengo que ordenar la izquierda
medio de estos dos elementos.

195
00:08:49,010 --> 00:08:50,870
La mitad izquierda, por supuesto, está a sólo 4.

196
00:08:50,870 --> 00:08:54,020
Entonces, ¿cómo puedo ordenar una lista de un elemento?

197
00:08:54,020 --> 00:08:57,960
Ahora bien, ese caso base especial
en lo alto, por así decirlo, se aplica.

198
00:08:57,960 --> 00:09:01,470
1 es menor que 2, y mi
lista es precisamente de tamaño 1.

199
00:09:01,470 --> 00:09:02,747
Así que me vuelvo.

200
00:09:02,747 --> 00:09:03,580
Yo no hago nada.

201
00:09:03,580 --> 00:09:06,770
Y de hecho, mira lo que tengo
hecho, 4 ya está ordenado.

202
00:09:06,770 --> 00:09:09,220
Al igual que ya estoy
parcialmente exitoso aquí.

203
00:09:09,220 --> 00:09:11,750
>> Ahora que parece un poco estúpido
a reclamar, pero es cierto.

204
00:09:11,750 --> 00:09:13,700
4 es una lista de tamaño 1.

205
00:09:13,700 --> 00:09:15,090
Ya está solucionado.

206
00:09:15,090 --> 00:09:16,270
Eso es la mitad izquierda.

207
00:09:16,270 --> 00:09:18,010
Ahora puedo ordenar la mitad derecha.

208
00:09:18,010 --> 00:09:22,310
Mi entrada es un elemento, 8
Del mismo modo, ya ordenados.

209
00:09:22,310 --> 00:09:25,170
Estúpido, también, pero de nuevo,
este principio básico

210
00:09:25,170 --> 00:09:28,310
va a permitir que construyamos ahora
en la parte superior de este éxito.

211
00:09:28,310 --> 00:09:32,260
4 ordenados, 8 se ordena, ahora
¿cuál fue el último paso?

212
00:09:32,260 --> 00:09:35,330
Así que el tercer y último paso, cualquier
tiempo estás ordenar una lista, el recuerdo,

213
00:09:35,330 --> 00:09:38,310
era fusionar las dos mitades,
la izquierda y la derecha.

214
00:09:38,310 --> 00:09:39,900
Así que vamos a hacer exactamente eso.

215
00:09:39,900 --> 00:09:41,940
Mi media izquierda es, por supuesto, 4.

216
00:09:41,940 --> 00:09:43,310
Mi mitad derecha es 8.

217
00:09:43,310 --> 00:09:44,100
>> Así que vamos a hacer esto.

218
00:09:44,100 --> 00:09:46,410
En primer lugar voy a asignar
algo de memoria adicional,

219
00:09:46,410 --> 00:09:48,680
que voy a represento aquí,
como se acaba de una matriz secundaria,

220
00:09:48,680 --> 00:09:49,660
eso es lo suficientemente grande para esto.

221
00:09:49,660 --> 00:09:52,243
Pero se puede imaginar que se extiende
ese rectángulo toda la longitud,

222
00:09:52,243 --> 00:09:53,290
si necesitamos más tarde.

223
00:09:53,290 --> 00:09:58,440
¿Cómo tomo 4 y 8, y se fusionan
esas dos listas de tamaño 1 en conjunto?

224
00:09:58,440 --> 00:10:00,270
Aquí, también, bastante simple.

225
00:10:00,270 --> 00:10:03,300
4 viene primero, luego viene 8.

226
00:10:03,300 --> 00:10:07,130
Porque si quiero ordenar la
medio izquierdo, luego la mitad derecha,

227
00:10:07,130 --> 00:10:09,900
y luego fusionar esas dos mitades
juntos, en forma ordenada,

228
00:10:09,900 --> 00:10:11,940
4 viene primero, luego viene 8.

229
00:10:11,940 --> 00:10:15,810
>> Así que parece que estamos haciendo progresos, incluso
aunque no he hecho ningún trabajo real.

230
00:10:15,810 --> 00:10:17,800
Pero recuerda dónde estamos en la historia.

231
00:10:17,800 --> 00:10:19,360
Originalmente llevamos ocho elementos.

232
00:10:19,360 --> 00:10:21,480
Clasificamos la mitad izquierda, que es 4.

233
00:10:21,480 --> 00:10:24,450
Entonces nos lo solucionaron la mitad izquierda
de la mitad izquierda, que era 2.

234
00:10:24,450 --> 00:10:25,270
Y aquí vamos.

235
00:10:25,270 --> 00:10:26,920
Hemos terminado con ese paso.

236
00:10:26,920 --> 00:10:29,930
>> Así que si hemos solucionaron el
media de 2 fuimos, ahora nosotros

237
00:10:29,930 --> 00:10:32,130
tiene que ordenar la mitad derecha de 2.

238
00:10:32,130 --> 00:10:35,710
Así que la mitad derecha de 2 es
estos dos valores aquí, 6 y 2.

239
00:10:35,710 --> 00:10:40,620
Así que vamos a tomar ahora una entrada de tamaño
2, y ordenar la mitad izquierda, y luego

240
00:10:40,620 --> 00:10:42,610
la mitad derecha, y luego
unirlos.

241
00:10:42,610 --> 00:10:45,722
Bueno, ¿cómo puedo ordenar una lista de tamaño
1, que contiene sólo el número 6?

242
00:10:45,722 --> 00:10:46,430
Yo ya he terminado.

243
00:10:46,430 --> 00:10:48,680
Se ordena esa lista de tamaño 1.

244
00:10:48,680 --> 00:10:52,140
>> ¿Cómo puedo ordenar otra lista de
tamaño 1, la denominada media derecha.

245
00:10:52,140 --> 00:10:54,690
Bueno, también, ya está solucionado.

246
00:10:54,690 --> 00:10:56,190
El número 2 es el único.

247
00:10:56,190 --> 00:11:00,160
Así que ahora tengo dos mitades, izquierda y
bien, tengo que unirlos.

248
00:11:00,160 --> 00:11:01,800
Permítanme doy un poco de espacio extra.

249
00:11:01,800 --> 00:11:05,580
Y poner 2 en allí,
a continuación, 6 de allí, de ese modo

250
00:11:05,580 --> 00:11:10,740
ordenar la lista, izquierda y derecha,
y la fusión juntos, en última instancia.

251
00:11:10,740 --> 00:11:12,160
Así que estoy en un poco mejor forma.

252
00:11:12,160 --> 00:11:16,250
No he terminado, porque es evidente 4, 8, 2,
6 no es el ordenamiento final que quiero.

253
00:11:16,250 --> 00:11:20,640
Pero ahora tengo dos listas de tamaño 2, que
haber dos, respectivamente, sido ordenados.

254
00:11:20,640 --> 00:11:24,580
Así que ahora si se rebobina en su mente de
ojo, ¿dónde nos deja eso?

255
00:11:24,580 --> 00:11:28,520
Empecé con ocho elementos, entonces yo
recortado hacia abajo a la mitad izquierda de 4,

256
00:11:28,520 --> 00:11:31,386
a continuación, la mitad izquierda de 2, y
entonces la mitad derecha de 2,

257
00:11:31,386 --> 00:11:34,510
Terminé, por lo tanto, la clasificación de la izquierda
media de 2, y la mitad derecha de 2,

258
00:11:34,510 --> 00:11:37,800
¿cuál es el tercer y último paso aquí?

259
00:11:37,800 --> 00:11:41,290
Tengo que fusionar
dos listas de tamaño 2.

260
00:11:41,290 --> 00:11:42,040
Así que vamos a seguir adelante.

261
00:11:42,040 --> 00:11:43,940
Y en la pantalla aquí, dar
me algo de memoria adicional,

262
00:11:43,940 --> 00:11:47,170
aunque técnicamente, noto que tengo
tiene un montón de espacio en blanco encima de la tapa

263
00:11:47,170 --> 00:11:47,670
Ya está.

264
00:11:47,670 --> 00:11:50,044
Si quiero ser especialmente
espacio eficiente sabio,

265
00:11:50,044 --> 00:11:52,960
Yo sólo podía empezar a mover los elementos
adelante y atrás, arriba y abajo.

266
00:11:52,960 --> 00:11:55,460
Pero sólo por la claridad visual,
Voy a ponerlo abajo,

267
00:11:55,460 --> 00:11:56,800
para mantener las cosas agradables y limpias.

268
00:11:56,800 --> 00:11:58,150
>> Así que tengo dos listas de tamaño 2.

269
00:11:58,150 --> 00:11:59,770
La primera lista tiene 4 y 8.

270
00:11:59,770 --> 00:12:01,500
La segunda lista tiene 2 y 6.

271
00:12:01,500 --> 00:12:03,950
Vamos a fusionar los
juntos en forma ordenada.

272
00:12:03,950 --> 00:12:09,910
2, por supuesto, es lo primero,
luego 4, luego 6, entonces 8.

273
00:12:09,910 --> 00:12:12,560
Y ahora parece que estamos consiguiendo
en algún lugar interesante.

274
00:12:12,560 --> 00:12:15,720
Medio Ahora he ordenada de la
lista, y casualmente, es

275
00:12:15,720 --> 00:12:18,650
todos los números pares, pero eso
es, de hecho, sólo una coincidencia.

276
00:12:18,650 --> 00:12:22,220
Y ahora he ordenado la izquierda
medio, por lo que es 2, 4, 6 y 8.

277
00:12:22,220 --> 00:12:23,430
Nada está fuera de orden.

278
00:12:23,430 --> 00:12:24,620
Que se siente como el progreso.

279
00:12:24,620 --> 00:12:26,650
>> Ahora se siente como si hubiera
estado hablando siempre ahora,

280
00:12:26,650 --> 00:12:29,850
así que lo que queda por ver si esto
algoritmo es, de hecho, más eficiente.

281
00:12:29,850 --> 00:12:31,766
Pero vamos a través
super metódicamente.

282
00:12:31,766 --> 00:12:34,060
Un ordenador, por supuesto,
lo haría así.

283
00:12:34,060 --> 00:12:34,840
Entonces, ¿dónde estamos?

284
00:12:34,840 --> 00:12:36,180
Empezamos con ocho elementos.

285
00:12:36,180 --> 00:12:37,840
Me clasifiqué la mitad izquierda de 4.

286
00:12:37,840 --> 00:12:39,290
Me parece que hacer con eso.

287
00:12:39,290 --> 00:12:42,535
Así que ahora el siguiente paso es
ordenar la mitad derecha de 4.

288
00:12:42,535 --> 00:12:44,410
Y esta parte podemos ir
a través de un poco más de

289
00:12:44,410 --> 00:12:47,140
rápidamente, aunque usted es
bienvenidos a rebobinar o pausar, justo

290
00:12:47,140 --> 00:12:49,910
pensar a través de él en
su propio ritmo, pero lo

291
00:12:49,910 --> 00:12:53,290
que tenemos ahora es una oportunidad para
hacer lo mismo algoritmo exacto de las cuatro

292
00:12:53,290 --> 00:12:54,380
números diferentes.

293
00:12:54,380 --> 00:12:57,740
>> Así que vamos a seguir adelante, y se centran en
la mitad derecha, lo que estamos aquí.

294
00:12:57,740 --> 00:13:01,260
La mitad izquierda de ese
medio derecho, y ahora el

295
00:13:01,260 --> 00:13:04,560
mitad izquierda de la izquierda
la mitad de esa mitad derecha,

296
00:13:04,560 --> 00:13:08,030
y cómo puedo ordenar una lista de tamaño
1 que contiene sólo el número 1?

297
00:13:08,030 --> 00:13:09,030
Ya está hecho.

298
00:13:09,030 --> 00:13:11,830
¿Cómo puedo hacer lo mismo para una lista
de tamaño 1 que contiene sólo 7?

299
00:13:11,830 --> 00:13:12,840
Ya está hecho.

300
00:13:12,840 --> 00:13:16,790
El tercer paso de este medio a continuación,
es fusionar estos dos elementos

301
00:13:16,790 --> 00:13:20,889
en una nueva lista de tamaño 2, 1 y 7.

302
00:13:20,889 --> 00:13:23,180
No parecen haber hecho todo
que mucho trabajo interesante.

303
00:13:23,180 --> 00:13:24,346
Vamos a ver qué sucede después.

304
00:13:24,346 --> 00:13:29,210
Acabo solucionaron la mitad izquierda de la
mitad derecha de mi entrada original.

305
00:13:29,210 --> 00:13:32,360
Ahora vamos a ordenar la derecha
medio, que contiene 5 y 3.

306
00:13:32,360 --> 00:13:35,740
Vamos a volver a ver a la izquierda
medio, ordenados, medio derecho, ordenados,

307
00:13:35,740 --> 00:13:39,120
y fusionar los dos juntos,
en un poco de espacio adicional,

308
00:13:39,120 --> 00:13:41,670
3 viene primero, luego viene 5.

309
00:13:41,670 --> 00:13:46,190
Y ahora, hemos clasificado el
media izquierda de la mitad derecha

310
00:13:46,190 --> 00:13:49,420
del problema original, y
la mitad derecha de la mitad derecha

311
00:13:49,420 --> 00:13:50,800
del problema original.

312
00:13:50,800 --> 00:13:52,480
¿Cuál es la tercera y última etapa?

313
00:13:52,480 --> 00:13:54,854
Bueno para fusionar esas dos mitades.

314
00:13:54,854 --> 00:13:57,020
Así que déjame a mí mismo un poco
espacio extra, pero, de nuevo,

315
00:13:57,020 --> 00:13:58,699
podría ser el uso de ese espacio hasta repuesto superior.

316
00:13:58,699 --> 00:14:00,490
Pero nosotros vamos a seguir
simple visualmente.

317
00:14:00,490 --> 00:14:07,070
Permítanme ahora se funden en 1, y
a continuación, 3, 5 y, a continuación, y luego 7.

318
00:14:07,070 --> 00:14:10,740
De esta manera dejándome ahora con la
mitad derecha del problema original

319
00:14:10,740 --> 00:14:12,840
Eso es perfectamente ordenados.

320
00:14:12,840 --> 00:14:13,662
>> Entonces, ¿qué queda?

321
00:14:13,662 --> 00:14:16,120
Siento que sigo diciendo que el
mismas cosas una y otra vez,

322
00:14:16,120 --> 00:14:18,700
pero eso es un reflejo de la
hecho de que estamos utilizando recursividad.

323
00:14:18,700 --> 00:14:21,050
El proceso de usar una
algoritmo de nuevo, y de nuevo,

324
00:14:21,050 --> 00:14:23,940
en subconjuntos más pequeños de
el problema original.

325
00:14:23,940 --> 00:14:27,580
Así que ahora tenemos una izquierda ordenados
medio del problema original.

326
00:14:27,580 --> 00:14:30,847
Tengo un medio ordenado derecho
del problema original.

327
00:14:30,847 --> 00:14:32,180
¿Cuál es la tercera y última etapa?

328
00:14:32,180 --> 00:14:33,590
Oh, es la fusión.

329
00:14:33,590 --> 00:14:34,480
Así que vamos a hacer eso.

330
00:14:34,480 --> 00:14:36,420
Vamos a asignar algunos adicionales
memoria, pero mi Dios, nos

331
00:14:36,420 --> 00:14:37,503
podría poner en cualquier lugar ahora.

332
00:14:37,503 --> 00:14:40,356
Tenemos mucho espacio disponible
para nosotros, pero vamos a mantener las cosas simples.

333
00:14:40,356 --> 00:14:42,730
En vez de ir hacia atrás y
adelante con nuestra memoria original,

334
00:14:42,730 --> 00:14:44,480
vamos hazlo
visualmente por aquí abajo,

335
00:14:44,480 --> 00:14:47,240
para terminar la fusión de la
mitad izquierda y la mitad derecha.

336
00:14:47,240 --> 00:14:49,279
>> Así que mediante la fusión, ¿qué tengo que hacer?

337
00:14:49,279 --> 00:14:50,820
Quiero aprovechar los elementos en orden.

338
00:14:50,820 --> 00:14:53,230
Así que mirando a la mitad izquierda,
Veo el primer número es 2.

339
00:14:53,230 --> 00:14:55,230
Miro a la mitad derecha,
Veo el primer número

340
00:14:55,230 --> 00:14:58,290
es 1, así que obviamente que
número Qué quiero arrancar,

341
00:14:58,290 --> 00:15:00,430
y poner primero en mi lista final?

342
00:15:00,430 --> 00:15:01,449
Por supuesto, 1.

343
00:15:01,449 --> 00:15:02,990
Ahora quiero hacer esa misma pregunta.

344
00:15:02,990 --> 00:15:05,040
En la mitad izquierda, tengo
todavía tiene el número 2.

345
00:15:05,040 --> 00:15:07,490
En la mitad derecha,
Tengo el número 3.

346
00:15:07,490 --> 00:15:08,930
¿Cuál debo quiero elegir?

347
00:15:08,930 --> 00:15:11,760
Por supuesto, el número 2 Y
Ahora notar los candidatos

348
00:15:11,760 --> 00:15:13,620
son 4 a la izquierda, 3 a la derecha.

349
00:15:13,620 --> 00:15:15,020
Vamos, por supuesto, elegir 3.

350
00:15:15,020 --> 00:15:18,020
Ahora los candidatos son 4 en
la izquierda, 5 a la derecha.

351
00:15:18,020 --> 00:15:19,460
Nosotros, por supuesto, elegimos 4.

352
00:15:19,460 --> 00:15:21,240
6 a la izquierda, 5 a la derecha.

353
00:15:21,240 --> 00:15:22,730
Nosotros, por supuesto, elegimos 5.

354
00:15:22,730 --> 00:15:25,020
6 a la izquierda, 7 a la derecha.

355
00:15:25,020 --> 00:15:29,320
Elegimos 6, y luego
elegir 7, y luego elegimos 8.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Así que un gran número de palabras más tarde,
han clasificado esta lista de ocho elementos

358
00:15:34,370 --> 00:15:38,450
en una lista de uno a ocho,
eso está aumentando con cada paso,

359
00:15:38,450 --> 00:15:40,850
pero cuánto tiempo lo hizo
que nos lleva a hacer eso.

360
00:15:40,850 --> 00:15:43,190
Bueno, yo he deliberadamente
cosas establecidas ilustrado

361
00:15:43,190 --> 00:15:46,330
aquí, así que podemos tipo de
ver o apreciar la división

362
00:15:46,330 --> 00:15:49,060
en la conquista que está ocurriendo.

363
00:15:49,060 --> 00:15:52,830
>> De hecho, si uno mira hacia atrás en el velorio,
He dejado todas estas líneas de puntos

364
00:15:52,830 --> 00:15:55,660
en marcadores de posición, usted puede,
clase de, vea, en orden inverso,

365
00:15:55,660 --> 00:15:58,800
si usted especie de mirar hacia atrás en
la historia ahora, mi lista original

366
00:15:58,800 --> 00:16:00,250
es, por supuesto, de tamaño 8.

367
00:16:00,250 --> 00:16:03,480
Y a continuación, previamente, estaba
se trata de dos listas de tamaño 4,

368
00:16:03,480 --> 00:16:08,400
y luego cuatro listas de tamaño 2,
y luego ocho listas de tamaño 1.

369
00:16:08,400 --> 00:16:10,151
>> Entonces, ¿qué hace esto,
clase de, recordarle?

370
00:16:10,151 --> 00:16:11,858
Bueno, de hecho, cualquiera de
los algoritmos que hemos

371
00:16:11,858 --> 00:16:14,430
mirado hasta el momento en el que
dividir y dividir y dividir,

372
00:16:14,430 --> 00:16:19,500
seguir teniendo las cosas de nuevo, y
Nuevamente, los resultados en esta idea general.

373
00:16:19,500 --> 00:16:23,100
Y así hay algo
logarítmica pasando aquí.

374
00:16:23,100 --> 00:16:26,790
Y no es bastante registro de n, pero
hay un componente logarítmica

375
00:16:26,790 --> 00:16:28,280
a lo que acabamos de hacer.

376
00:16:28,280 --> 00:16:31,570
>> Ahora vamos a considerar la forma en que realmente es.

377
00:16:31,570 --> 00:16:34,481
Así que ingrese de n, de nuevo fue
un gran tiempo de funcionamiento,

378
00:16:34,481 --> 00:16:36,980
cuando hicimos algo parecido
búsqueda binaria, ya que ahora llamamos,

379
00:16:36,980 --> 00:16:40,090
la estrategia de divide y vencerás
a través del cual nos encontramos Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Ahora técnicamente.

381
00:16:41,020 --> 00:16:43,640
Eso es log base 2 de n, incluso
aunque en la mayoría de las clases de matemáticas,

382
00:16:43,640 --> 00:16:45,770
10 es por lo general la base de que usted asume.

383
00:16:45,770 --> 00:16:48,940
Pero científicos de la computación casi siempre
pensar y hablar en términos de base 2,

384
00:16:48,940 --> 00:16:52,569
así que en general, sólo decimos registro de
n, en lugar de logaritmo en base 2 de n,

385
00:16:52,569 --> 00:16:55,110
pero son exactamente una y la
mismo en el mundo del ordenador

386
00:16:55,110 --> 00:16:57,234
ciencia, y como un aparte,
hay un factor constante

387
00:16:57,234 --> 00:17:01,070
diferencia entre los dos, por lo que es
discutible de todos modos, por razones más formales.

388
00:17:01,070 --> 00:17:04,520
>> Pero por ahora, lo que nos importa
acerca es este ejemplo.

389
00:17:04,520 --> 00:17:08,520
Así que vamos a no prueba con el ejemplo, pero al
menos usar un ejemplo de los números

390
00:17:08,520 --> 00:17:10,730
a la mano como una comprobación de validez, si se quiere.

391
00:17:10,730 --> 00:17:14,510
Así que con anterioridad la fórmula era la base de registro
2 de n, pero lo que es n en este caso.

392
00:17:14,510 --> 00:17:18,526
Tuve n números originales, o 8
del número original específicamente.

393
00:17:18,526 --> 00:17:20,359
Ahora que ha sido un poco
tiempo, pero estoy bastante

394
00:17:20,359 --> 00:17:25,300
Seguro que log base 2
del valor 8 es 3,

395
00:17:25,300 --> 00:17:29,630
y de hecho, lo que es bueno de esto es
que el 3 es exactamente el número de veces

396
00:17:29,630 --> 00:17:33,320
que se puede dividir una lista
de longitud 8 otra vez, y otra vez,

397
00:17:33,320 --> 00:17:36,160
y otra vez, hasta que uno se queda
con listas de apenas el tamaño 1.

398
00:17:36,160 --> 00:17:36,660
¿Correcto?

399
00:17:36,660 --> 00:17:40,790
8 va a 4, pasa a 2,
pasa a 1, y eso es

400
00:17:40,790 --> 00:17:43,470
refleja exactamente eso
imagen que teníamos hace un momento.

401
00:17:43,470 --> 00:17:47,160
Así que un poco de cordura comprobar de dónde
el logaritmo está realmente involucrado.

402
00:17:47,160 --> 00:17:50,180
>> Así que ahora, ¿qué más está involucrado aquí? n.

403
00:17:50,180 --> 00:17:53,440
Así notar que cada
tiempo yo nos dividimos la lista,

404
00:17:53,440 --> 00:17:58,260
aunque en orden inverso en la historia
aquí, todavía estaba haciendo n cosas.

405
00:17:58,260 --> 00:18:02,320
Ese paso fusión requería que
Toco cada uno de los números,

406
00:18:02,320 --> 00:18:05,060
con el fin de deslizarse en
su ubicación adecuada.

407
00:18:05,060 --> 00:18:10,760
Así que, aunque la altura de esta
diagrama es del tamaño del registro n de n o 3,

408
00:18:10,760 --> 00:18:13,860
específicamente, en otras palabras,
Hice tres divisiones aquí.

409
00:18:13,860 --> 00:18:18,800
¿Cuánto trabajo hice horizontalmente
a lo largo de este gráfico cada vez?

410
00:18:18,800 --> 00:18:21,110
>> Bueno, lo hice n pasos de
trabajar, porque si tengo

411
00:18:21,110 --> 00:18:24,080
tiene cuatro elementos y cuatro elementos,
y necesito unirlos.

412
00:18:24,080 --> 00:18:26,040
Tengo que ir a través de
estos cuatro y estos cuatro,

413
00:18:26,040 --> 00:18:28,123
en última instancia, para fundirlas
de nuevo en ocho elementos.

414
00:18:28,123 --> 00:18:32,182
Si por el contrario tengo ocho dedos
por aquí, que no lo hago, y de ocho

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Si tengo
tiene cuatro dedos por aquí,

416
00:18:34,390 --> 00:18:37,380
que voy a hacer, cuatro dedos
aquí, que yo hago,

417
00:18:37,380 --> 00:18:40,590
entonces eso es la misma
ejemplo, como antes, si lo hago

418
00:18:40,590 --> 00:18:44,010
tiene ocho dedos aunque en
total, que puedo clase de, hacer,.

419
00:18:44,010 --> 00:18:47,950
Exactamente lo que puedo hacer aquí,
entonces yo sabe

420
00:18:47,950 --> 00:18:50,370
fusionar todas estas listas
de tamaño 1 juntos.

421
00:18:50,370 --> 00:18:54,050
Pero sin duda tengo que mirar
en cada elemento de exactamente una vez.

422
00:18:54,050 --> 00:18:59,640
Por lo tanto la altura de este proceso es log n,
la anchura de este proceso, por así decirlo,

423
00:18:59,640 --> 00:19:02,490
es N, así que lo que parece
tener, en última instancia, es

424
00:19:02,490 --> 00:19:06,470
una duración de tamaño n veces log n.

425
00:19:06,470 --> 00:19:08,977
>> En otras palabras, hemos dividido
la lista, registro n veces,

426
00:19:08,977 --> 00:19:11,810
pero cada vez que lo hicimos, tuvimos
tocar cada uno de los elementos

427
00:19:11,810 --> 00:19:13,560
con el fin de fusionarlos
todos juntos, que

428
00:19:13,560 --> 00:19:18,120
fue n paso, por lo que tenemos n veces log n,
o como un científico de la computación diría,

429
00:19:18,120 --> 00:19:20,380
asintóticamente, que
sería la palabra grande

430
00:19:20,380 --> 00:19:22,810
para describir la parte superior
con destino en un tiempo de funcionamiento,

431
00:19:22,810 --> 00:19:28,010
nos estamos quedando en una gran o
de log n tiempo, por así decirlo.

432
00:19:28,010 --> 00:19:31,510
>> Ahora bien, esto es importante, porque
recuerdan lo que fueron los tiempos de funcionamiento

433
00:19:31,510 --> 00:19:34,120
con la burbuja de género, y la selección
ordenar y ordenación por inserción,

434
00:19:34,120 --> 00:19:38,200
e incluso algunos otros que existen,
n al cuadrado era donde estábamos.

435
00:19:38,200 --> 00:19:39,990
Y usted puede, un poco, ver esto aquí.

436
00:19:39,990 --> 00:19:45,720
Si n al cuadrado es obviamente n veces
n, pero aquí tenemos n veces log n,

437
00:19:45,720 --> 00:19:48,770
y ya sabemos por semana
cero, que log n, la logarítmica,

438
00:19:48,770 --> 00:19:50,550
es mejor que algo lineal.

439
00:19:50,550 --> 00:19:52,930
Después de todo, recordar la imagen
con el rojo y el amarillo

440
00:19:52,930 --> 00:19:56,500
y las líneas verdes que Drew, el
línea logarítmica verde era mucho menor.

441
00:19:56,500 --> 00:20:00,920
Y por lo tanto, mucho mejor y más rápido
que las líneas amarillas y rojas rectas,

442
00:20:00,920 --> 00:20:05,900
n veces log n es, de hecho, mejor
de n veces n o n al cuadrado.

443
00:20:05,900 --> 00:20:09,110
>> Así que parece que tenemos
identificado una combinación de algoritmo

444
00:20:09,110 --> 00:20:11,870
especie que se ejecuta en mucho
tiempo más rápido, y de hecho,

445
00:20:11,870 --> 00:20:16,560
por eso, a principios de esta semana, cuando
vimos que contienda entre burbujas

446
00:20:16,560 --> 00:20:20,750
Ordena, ordenación por selección, y fusionar
Ordena, ordenamiento por mezcla muy, muy ganado.

447
00:20:20,750 --> 00:20:23,660
Y, en efecto, que ni siquiera esperar
de ordenamiento de burbuja y ordenación por selección

448
00:20:23,660 --> 00:20:24,790
acabar.

449
00:20:24,790 --> 00:20:27,410
>> Ahora vamos a tomar otro paso
en este, desde un poco más

450
00:20:27,410 --> 00:20:31,030
punto de vista formal, por si
caso, esto resuena mejor

451
00:20:31,030 --> 00:20:33,380
que el alto nivel de discusión.

452
00:20:33,380 --> 00:20:34,880
Así que aquí está el algoritmo de nuevo.

453
00:20:34,880 --> 00:20:36,770
Preguntémonos,
lo que el tiempo de ejecución

454
00:20:36,770 --> 00:20:39,287
es de este algoritmos diferentes pasos?

455
00:20:39,287 --> 00:20:41,620
Vamos a dividir en la primera
caso y el segundo caso.

456
00:20:41,620 --> 00:20:46,280
El IF y ELSE En el caso SI,
Si N es menor que 2, simplemente volver.

457
00:20:46,280 --> 00:20:47,580
Se siente como constante de tiempo.

458
00:20:47,580 --> 00:20:50,970
Es, algo así, como dos pasos,
Si n es inferior a 2, y luego volver.

459
00:20:50,970 --> 00:20:54,580
Pero como hemos dicho el lunes
constante de tiempo, o del o de 1,

460
00:20:54,580 --> 00:20:57,130
pueden ser dos pasos, tres
pasos, incluso 1.000 pasos.

461
00:20:57,130 --> 00:20:59,870
Lo que importa es que es
un número constante de pasos.

462
00:20:59,870 --> 00:21:03,240
Así que el amarillo resaltado pseudocódigo
aquí se ejecuta en, lo vamos a llamar,

463
00:21:03,240 --> 00:21:04,490
constante de tiempo.

464
00:21:04,490 --> 00:21:06,780
Así que de manera más formal, y
vamos a-- este

465
00:21:06,780 --> 00:21:09,910
será el grado en que nos
formalizar este derecho ahora-- T de n,

466
00:21:09,910 --> 00:21:15,030
el tiempo de ejecución de un problema
que toma n tantos como entrada,

467
00:21:15,030 --> 00:21:19,150
es igual a grande o de uno,
Si N es menor que 2.

468
00:21:19,150 --> 00:21:20,640
Así que es condicionado a eso.

469
00:21:20,640 --> 00:21:24,150
Así que para ser claros, si n es menor que
2, tenemos una lista muy corta, a continuación,

470
00:21:24,150 --> 00:21:29,151
el tiempo de ejecución, T de n, donde n es
1 o 0, en este caso muy específico,

471
00:21:29,151 --> 00:21:30,650
es sólo va a ser la constante de tiempo.

472
00:21:30,650 --> 00:21:32,691
Se va a tomar uno
paso, dos pasos, lo que sea.

473
00:21:32,691 --> 00:21:33,950
Es un número fijo de pasos.

474
00:21:33,950 --> 00:21:38,840
>> Así que la parte jugosa seguramente debe estar en
el otro caso en el pseudocódigo.

475
00:21:38,840 --> 00:21:40,220
El caso ELSE.

476
00:21:40,220 --> 00:21:44,870
Ordenar mitad izquierda de los elementos, tipo adecuado
medio de elementos, combinar mitades ordenadas.

477
00:21:44,870 --> 00:21:46,800
¿Cuánto tiempo dura cada uno de esos pasos tomar?

478
00:21:46,800 --> 00:21:49,780
Bueno, si el funcionamiento
tiempo para ordenar n elementos

479
00:21:49,780 --> 00:21:53,010
Es decir, vamos a llamarlo muy
genéricamente, T de n,

480
00:21:53,010 --> 00:21:55,500
a continuación, la clasificación de la izquierda
medio de los elementos

481
00:21:55,500 --> 00:21:59,720
es decir, una especie de, como decir,
T de n dividido por 2,

482
00:21:59,720 --> 00:22:03,000
y del mismo modo la clasificación de la mitad derecha
de elementos es, algo así, como diciendo:

483
00:22:03,000 --> 00:22:06,974
T de n divide 2, y luego
la fusión de las mitades ordenados.

484
00:22:06,974 --> 00:22:08,890
Bueno, si tengo alguna
número de elementos aquí,

485
00:22:08,890 --> 00:22:11,230
como cuatro, y un número
de elementos que aquí, al igual que cuatro,

486
00:22:11,230 --> 00:22:14,650
y tengo que combinar cada uno de estos cuatro
en, y cada una de estas cuatro en, uno

487
00:22:14,650 --> 00:22:17,160
después de la otra, de modo que
en última instancia, tengo ocho elementos.

488
00:22:17,160 --> 00:22:20,230
Se siente como que es grande o de n pasos?

489
00:22:20,230 --> 00:22:23,500
Si tengo n dedos y cada una de
ellos tiene que ser fusionado en su lugar,

490
00:22:23,500 --> 00:22:25,270
eso es como otro n pasos.

491
00:22:25,270 --> 00:22:27,360
>> Así que de hecho formulaically,
podemos expresar esto,

492
00:22:27,360 --> 00:22:29,960
aunque un poco asustadizo al principio
vista, pero es algo

493
00:22:29,960 --> 00:22:31,600
que captura exactamente esa lógica.

494
00:22:31,600 --> 00:22:35,710
El tiempo de ejecución, T de n, si n
es mayor que o igual a 2.

495
00:22:35,710 --> 00:22:42,500
En este caso, el caso ELSE, es T de n
dividido por 2, además de T de N dividido por 2,

496
00:22:42,500 --> 00:22:45,320
más grande o de n, algunos
número de pasos lineal,

497
00:22:45,320 --> 00:22:51,630
tal vez exactamente n, tal vez 2 veces
n, pero es más o menos, el orden de n.

498
00:22:51,630 --> 00:22:54,060
Así que, también, es la forma en que puede
expresar esta formulaically.

499
00:22:54,060 --> 00:22:56,809
Ahora no vas a saber esto a menos
que ha grabado en su mente,

500
00:22:56,809 --> 00:22:58,710
o búsquelo en la
lomo de un libro de texto, que

501
00:22:58,710 --> 00:23:00,501
podría tener un poco
hoja de trucos al final,

502
00:23:00,501 --> 00:23:03,940
pero esto es, de hecho, va a
nos dan una gran o de n log n,

503
00:23:03,940 --> 00:23:06,620
porque la recurrencia que
que estamos viendo aquí en la pantalla,

504
00:23:06,620 --> 00:23:09,550
si realmente lo hizo a cabo, con
un número infinito de ejemplos,

505
00:23:09,550 --> 00:23:13,000
o lo hiciste formulaically, lo haría
ver que esto, porque esta fórmula

506
00:23:13,000 --> 00:23:17,100
sí mismo es recursivo, con t de
n por algo a la derecha,

507
00:23:17,100 --> 00:23:21,680
y t de n por la izquierda, esto puede
en realidad ser expresada, en última instancia,

508
00:23:21,680 --> 00:23:24,339
tan grande de lado n log n.

509
00:23:24,339 --> 00:23:26,130
Si no está convencido, eso es
bien por ahora, sólo

510
00:23:26,130 --> 00:23:28,960
toma en la fe, que es, de hecho,
lo que conduce a la recurrencia,

511
00:23:28,960 --> 00:23:31,780
pero esto es sólo un poco más de un
enfoque matemático a la búsqueda

512
00:23:31,780 --> 00:23:36,520
en el momento de ejecución de la fusión especie
basado en su pseudocódigo solo.

513
00:23:36,520 --> 00:23:39,030
>> Ahora vamos a echar un poco de un
respiro de todo eso,

514
00:23:39,030 --> 00:23:41,710
y echar un vistazo a una
cierta ex senador, quien

515
00:23:41,710 --> 00:23:44,260
podría parecer un poco familiar,
quien se sentó con Eric de Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, hace algún tiempo, para una entrevista
en el escenario, delante de un montón

517
00:23:48,410 --> 00:23:53,710
de las personas, hablar en última instancia acerca de
un tema, que es bastante ya familiar.

518
00:23:53,710 --> 00:23:54,575
Echemos un vistazo.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Ahora el senador,
usted está aquí en Google,

521
00:24:03,890 --> 00:24:09,490
y me gusta pensar en el
presidencia como una entrevista de trabajo.

522
00:24:09,490 --> 00:24:11,712
Ahora es difícil conseguir un trabajo como presidente.

523
00:24:11,712 --> 00:24:12,670
PRESIDENTE OBAMA: Correcto.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Y tú eres
va a hacer [inaudible] ahora.

525
00:24:13,940 --> 00:24:15,523
También es difícil de conseguir un trabajo en Google.

526
00:24:15,523 --> 00:24:17,700
PRESIDENTE OBAMA: Correcto.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Tenemos preguntas,
y le pedimos a nuestras preguntas de los candidatos,

528
00:24:21,330 --> 00:24:24,310
y éste es de Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> PRESIDENTE OBAMA: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: ¿Qué?

531
00:24:27,005 --> 00:24:28,130
Ustedes piensan que estoy bromeando?

532
00:24:28,130 --> 00:24:30,590
Es justo aquí.

533
00:24:30,590 --> 00:24:33,490
¿Cuál es la forma más eficiente de
ordenar un millón 32 bits enteros?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> PRESIDENTE OBAMA: Bueno--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: En ocasiones,
tal vez me siento, maybe--

537
00:24:41,020 --> 00:24:42,750
PRESIDENTE OBAMA: No, no,
no, no, no, yo think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Eso no es it--

539
00:24:43,240 --> 00:24:45,430
PRESIDENTE OBAMA: I
pensar, creo que la burbuja

540
00:24:45,430 --> 00:24:46,875
tipo sería el camino equivocado.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Vamos.

543
00:24:50,535 --> 00:24:52,200
¿Quién le dijo eso?

544
00:24:52,200 --> 00:24:54,020
OK.

545
00:24:54,020 --> 00:24:55,590
Yo no hice la informática en--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDENTE OBAMA: Tenemos
dieron nuestros espías en ese país.

547
00:24:58,986 --> 00:24:59,860
PROFESOR: Muy bien.

548
00:24:59,860 --> 00:25:03,370
Vamos a dejar detrás de nosotros ahora
mundo teórico de algoritmos

549
00:25:03,370 --> 00:25:06,520
en el análisis asintótico
de los mismos, y volver a algunos temas

550
00:25:06,520 --> 00:25:09,940
desde la semana cero y uno, e inicio
para eliminar algunas ruedas de entrenamiento,

551
00:25:09,940 --> 00:25:10,450
si se quiere.

552
00:25:10,450 --> 00:25:13,241
Así que usted realmente entiende
en última instancia, a partir de cero, lo que es

553
00:25:13,241 --> 00:25:16,805
pasando por debajo de la campana, cuando
escribir, compilar y ejecutar programas.

554
00:25:16,805 --> 00:25:19,680
Recordemos, en particular, que se trataba de
el primer programa en C mirábamos,

555
00:25:19,680 --> 00:25:22,840
un programa canónica, simple
de tipo, en términos relativos,

556
00:25:22,840 --> 00:25:24,620
en donde, imprime, Hello World.

557
00:25:24,620 --> 00:25:27,610
Y recuerdo que le dije, el proceso
que el código fuente pasa a través de

558
00:25:27,610 --> 00:25:28,430
es exactamente esto.

559
00:25:28,430 --> 00:25:31,180
Usted toma su código fuente, pasa
a través de un compilador, como Clang,

560
00:25:31,180 --> 00:25:34,650
y fuera viene código objeto, que
podría tener este aspecto, ceros y unos

561
00:25:34,650 --> 00:25:37,880
que la CPU de la computadora, el centro
unidad de procesamiento o el cerebro,

562
00:25:37,880 --> 00:25:39,760
en última instancia, entiende.

563
00:25:39,760 --> 00:25:42,460
>> Resulta que esa es una
poco de una simplificación excesiva,

564
00:25:42,460 --> 00:25:44,480
que ahora estamos en un
posición de separar

565
00:25:44,480 --> 00:25:46,720
para entender lo que realmente ha sido
pasando por debajo de la campana

566
00:25:46,720 --> 00:25:48,600
cada vez que se ejecuta
Clang, o más generalmente,

567
00:25:48,600 --> 00:25:53,040
cada vez que realice un programa,
utilizando Marca y CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
En particular, cosas por el estilo
este se genera primero,

569
00:25:56,760 --> 00:25:58,684
la primera vez que compila el programa.

570
00:25:58,684 --> 00:26:00,600
En otras palabras, cuando se
llevar a su código fuente

571
00:26:00,600 --> 00:26:04,390
y compilarlo, ¿qué es primero
siendo enviada por Clang

572
00:26:04,390 --> 00:26:06,370
es algo conocido como código ensamblador.

573
00:26:06,370 --> 00:26:08,990
Y, de hecho, se ve exactamente como este.

574
00:26:08,990 --> 00:26:11,170
>> Corrí un comando en el
línea de comandos anterior.

575
00:26:11,170 --> 00:26:16,260
Hola.c Clang capitales tablero s,
y esto crea un archivo

576
00:26:16,260 --> 00:26:19,490
para mí llamados hello.s,
dentro de los cuales eran exactamente

577
00:26:19,490 --> 00:26:22,290
estos contenidos, y un poco más
arriba y un poco más abajo,

578
00:26:22,290 --> 00:26:25,080
pero me he puesto la más jugosa
información aquí, en la pantalla.

579
00:26:25,080 --> 00:26:29,190
Y si te fijas bien, verás
al menos un par de palabras clave familiares.

580
00:26:29,190 --> 00:26:31,330
Tenemos principal en la parte superior.

581
00:26:31,330 --> 00:26:35,140
Hemos printf en el centro.

582
00:26:35,140 --> 00:26:38,670
Y también tenemos hola mundo
barra invertida n entre comillas abajo abajo.

583
00:26:38,670 --> 00:26:42,450
>> Y todo lo demás aquí
es muy instrucciones de bajo nivel

584
00:26:42,450 --> 00:26:45,500
que la CPU de la computadora entiende.

585
00:26:45,500 --> 00:26:50,090
Instrucciones de CPU que se mueven de memoria
alrededor, que las cadenas de carga de la memoria,

586
00:26:50,090 --> 00:26:52,750
y en última instancia, de impresión
cosas en la pantalla.

587
00:26:52,750 --> 00:26:56,780
Ahora lo que sucede aunque después
se genera el código de montaje?

588
00:26:56,780 --> 00:26:59,964
En última instancia, lo hace, de hecho,
Todavía generar código objeto.

589
00:26:59,964 --> 00:27:02,630
Pero los pasos que tienen realmente
estado sucediendo debajo de la campana

590
00:27:02,630 --> 00:27:04,180
mirar un poco de la misma familia.

591
00:27:04,180 --> 00:27:08,390
El código fuente se convierte en código ensamblador,
que luego se convierte en código objeto,

592
00:27:08,390 --> 00:27:11,930
y las palabras clave aquí es que,
al compilar el código fuente,

593
00:27:11,930 --> 00:27:16,300
cabo viene código ensamblador, y después
al colocar su código en ensamblador,

594
00:27:16,300 --> 00:27:17,800
cabo viene código objeto.

595
00:27:17,800 --> 00:27:20,360
>> Ahora Clang es super sofisticado,
como muchos de los compiladores,

596
00:27:20,360 --> 00:27:23,151
y lo hace de todos estos pasos
juntos, y no necesariamente

597
00:27:23,151 --> 00:27:25,360
salida de cualquier intermedio
archivos que aún se pueden ver.

598
00:27:25,360 --> 00:27:28,400
Simplemente compila las cosas,
que es el término general que

599
00:27:28,400 --> 00:27:30,000
describe todo este proceso.

600
00:27:30,000 --> 00:27:32,000
Pero si realmente quieres
para ser concreto, no hay

601
00:27:32,000 --> 00:27:34,330
mucho más que hacer allí también.

602
00:27:34,330 --> 00:27:38,860
>> Pero también vamos a considerar ahora que incluso
ese programa super simple, hello.c,

603
00:27:38,860 --> 00:27:40,540
llamado una función.

604
00:27:40,540 --> 00:27:41,870
Pidió printf.

605
00:27:41,870 --> 00:27:46,900
Pero yo no escribí printf, de hecho,
que viene con c, por así decirlo.

606
00:27:46,900 --> 00:27:51,139
Es un recordatorio de que la función es
declarada en io.h estándar, que

607
00:27:51,139 --> 00:27:53,180
es un archivo de cabecera, que
es un tema que va en realidad

608
00:27:53,180 --> 00:27:55,780
sumergirse en mayor profundidad en poco tiempo.

609
00:27:55,780 --> 00:27:58,000
Sin embargo, un archivo de cabecera es
normalmente acompañados

610
00:27:58,000 --> 00:28:02,920
por un archivo de código, archivo de código fuente, por lo
al igual que existe io.h. estándar

611
00:28:02,920 --> 00:28:05,930
>> Hace algún tiempo, alguien,
o de alguien, también escribió

612
00:28:05,930 --> 00:28:11,040
un archivo llamado io.c norma, en
que las definiciones reales,

613
00:28:11,040 --> 00:28:15,220
o implementaciones de printf,
y racimos de otras funciones,

614
00:28:15,220 --> 00:28:16,870
son en realidad escrito.

615
00:28:16,870 --> 00:28:22,140
Así que teniendo en cuenta que, si tenemos en cuenta que tiene
aquí a la izquierda, hello.c, que cuando

616
00:28:22,140 --> 00:28:26,250
compilado, nos da hello.s, incluso si
Clang no molesta ahorro en un lugar

617
00:28:26,250 --> 00:28:31,360
podemos verlo, y que el código de montaje
obtiene ensamblado en hello.o, que

618
00:28:31,360 --> 00:28:34,630
es, de hecho, el nombre por defecto
dado cada vez que se compila la fuente

619
00:28:34,630 --> 00:28:39,350
codificar en código objeto, pero no son
listo para ejecutarlo sin embargo,

620
00:28:39,350 --> 00:28:41,460
porque otro paso
tiene que suceder, y tiene

621
00:28:41,460 --> 00:28:44,440
venido sucediendo en los últimos
semana, quizá sin saberlo tú.

622
00:28:44,440 --> 00:28:47,290
>> Específicamente en alguna parte
en CS50 IDE, y esto,

623
00:28:47,290 --> 00:28:49,870
también, será un poco de un
simplificación excesiva por un momento,

624
00:28:49,870 --> 00:28:54,670
hay, o fue en otro tiempo,
un archivo llamado io.c estándar,

625
00:28:54,670 --> 00:28:58,440
que alguien compilado en
io.s estándar o el equivalente,

626
00:28:58,440 --> 00:29:02,010
que alguien ensambla entonces
en io.o estándar,

627
00:29:02,010 --> 00:29:04,600
o resulta en una
ligeramente diferente archivo

628
00:29:04,600 --> 00:29:07,220
formato que puede tener un diferente
extensión de archivo por completo,

629
00:29:07,220 --> 00:29:11,720
pero en teoría y conceptualmente, exactamente
esos pasos tuvieron que pasar en alguna forma.

630
00:29:11,720 --> 00:29:14,060
Es decir, que ahora
cuando estoy escribiendo un programa,

631
00:29:14,060 --> 00:29:17,870
hello.c, que apenas dice, hola mundo,
y estoy usando el código de otra persona

632
00:29:17,870 --> 00:29:22,480
como printf, que era una vez un
tiempo, en un archivo llamado io.c estándar,

633
00:29:22,480 --> 00:29:26,390
entonces de alguna manera tengo que llevar a mi
código objeto, mis ceros y unos,

634
00:29:26,390 --> 00:29:29,260
y el objeto de esa persona
código, o ceros y unos,

635
00:29:29,260 --> 00:29:34,970
y de alguna manera enlazar juntos en
un archivo final, llamada hola, que

636
00:29:34,970 --> 00:29:38,070
tiene todos los ceros y
los de mi función principal,

637
00:29:38,070 --> 00:29:40,830
y todos los ceros
y los de printf.

638
00:29:40,830 --> 00:29:44,900
>> Y, en efecto, que el pasado proceso es
llamada, la vinculación de su código objeto.

639
00:29:44,900 --> 00:29:47,490
La salida de los cuales
es un archivo ejecutable.

640
00:29:47,490 --> 00:29:49,780
Así que para ser justos, en el
final del día, nada

641
00:29:49,780 --> 00:29:52,660
ha cambiado desde la semana uno, cuando
primero comenzó compilar programas.

642
00:29:52,660 --> 00:29:55,200
De hecho, todo esto ha sido
pasando por debajo de la capucha,

643
00:29:55,200 --> 00:29:57,241
pero ahora estamos en una posición
donde podamos realmente

644
00:29:57,241 --> 00:29:58,794
desmenuzar estos varios pasos.

645
00:29:58,794 --> 00:30:00,710
Y, de hecho, al final
del día, todavía estamos

646
00:30:00,710 --> 00:30:04,480
izquierda con ceros y unos, que
es en realidad un gran segue ahora

647
00:30:04,480 --> 00:30:08,620
a otra capacidad de C, que
nosotros no hemos tenido que aprovechar más probable

648
00:30:08,620 --> 00:30:11,250
hasta la fecha, conocida como operadores bit a bit.

649
00:30:11,250 --> 00:30:15,220
En otras palabras, hasta el momento, en cualquier momento nos hemos
tratado con datos en C o variables en C,

650
00:30:15,220 --> 00:30:17,660
hemos tenido cosas como
caracteres y carrozas y complementos

651
00:30:17,660 --> 00:30:21,990
y anhela y dobles y similares, pero
todos esos son al menos ocho bits.

652
00:30:21,990 --> 00:30:25,550
Hemos embargo nunca sido capaces de
manipular bits individuales,

653
00:30:25,550 --> 00:30:28,970
a pesar de que un bit individual, nos
saben, puede representar un 0 y un 1.

654
00:30:28,970 --> 00:30:32,640
Ahora resulta que en C,
puede obtener acceso a los bits individuales,

655
00:30:32,640 --> 00:30:35,530
si conoce la sintaxis,
con la que para llegar a ellos.

656
00:30:35,530 --> 00:30:38,010
>> Así que vamos a echar un vistazo
a operadores bit a bit.

657
00:30:38,010 --> 00:30:41,700
Así fotografiados aquí hay algunos símbolos que
hemos, clase de, clase de, visto antes.

658
00:30:41,700 --> 00:30:45,580
Veo una y comercial, vertical
bar, y algunos otros también,

659
00:30:45,580 --> 00:30:49,430
y recordar que signo ampersand
es algo que hemos visto antes.

660
00:30:49,430 --> 00:30:54,060
El operador lógico AND, donde tienes
dos de ellos juntos, o la lógica OR

661
00:30:54,060 --> 00:30:56,300
operador, en la que
tener dos barras verticales.

662
00:30:56,300 --> 00:31:00,550
Operadores bit a bit, que vamos a
ver operar en bits de forma individual,

663
00:31:00,550 --> 00:31:03,810
sólo tiene que utilizar un solo signo, un
barra vertical única, el símbolo de intercalación

664
00:31:03,810 --> 00:31:06,620
que viene a continuación, la pequeña
tilde y, luego a la izquierda

665
00:31:06,620 --> 00:31:08,990
soporte dejó soporte o
corchete derecho escuadra derecha.

666
00:31:08,990 --> 00:31:10,770
Cada uno de ellos tienen diferentes significados.

667
00:31:10,770 --> 00:31:11,950
>> De hecho, vamos a echar un vistazo.

668
00:31:11,950 --> 00:31:16,560
Vamos a la vieja escuela de hoy, y el uso
una pantalla táctil de antaño,

669
00:31:16,560 --> 00:31:18,002
conocido como un tablero blanco.

670
00:31:18,002 --> 00:31:19,710
Y este tablero blanco
nos va a permitir

671
00:31:19,710 --> 00:31:27,360
para expresar algunos símbolos bastante simples,
o más bien algunas fórmulas bastante simples,

672
00:31:27,360 --> 00:31:29,560
que podemos entonces en última instancia,
apalancamiento, con el fin

673
00:31:29,560 --> 00:31:33,230
acceder a la persona
bits dentro de un programa C.

674
00:31:33,230 --> 00:31:34,480
En otras palabras, vamos a hacer esto.

675
00:31:34,480 --> 00:31:37,080
Primero hablemos de
momento en signo,

676
00:31:37,080 --> 00:31:39,560
que es el operador AND.

677
00:31:39,560 --> 00:31:42,130
En otras palabras, esto es
un operador que permite

678
00:31:42,130 --> 00:31:45,930
que yo tenga una variable de la izquierda
Típicamente, y una variable de la derecha,

679
00:31:45,930 --> 00:31:50,640
o un valor individual, que si Y
juntos, me da un resultado final.

680
00:31:50,640 --> 00:31:51,560
Entonces, ¿qué puedo decir?

681
00:31:51,560 --> 00:31:54,840
Si en un programa, que tiene una variable
que almacena uno de estos valores,

682
00:31:54,840 --> 00:31:58,000
o vamos a mantenerlo simple, y justo
escriba ceros y unos de forma individual,

683
00:31:58,000 --> 00:32:00,940
así es como funciona el operador de signo.

684
00:32:00,940 --> 00:32:06,400
0 0 Y comercial va a ser igual a 0.

685
00:32:06,400 --> 00:32:07,210
Ahora ¿por qué es eso?

686
00:32:07,210 --> 00:32:09,291
>> Es muy similar a
Expresiones booleanas,

687
00:32:09,291 --> 00:32:10,540
que hemos discutido hasta ahora.

688
00:32:10,540 --> 00:32:15,800
Si usted piensa que después de todo, el 0 es
falsa, 0 es falsa, falsa y falso

689
00:32:15,800 --> 00:32:18,720
es, como hemos discutido
lógicamente, también falsa.

690
00:32:18,720 --> 00:32:20,270
Así obtenemos 0 aquí también.

691
00:32:20,270 --> 00:32:24,390
Si usted toma 0 ampersand
1, así que, también,

692
00:32:24,390 --> 00:32:29,890
va a ser 0, porque para esto
la expresión de la izquierda para ser verdad o 1,

693
00:32:29,890 --> 00:32:32,360
que tendría que ser verdadero y cierto.

694
00:32:32,360 --> 00:32:36,320
Pero aquí tenemos falsa
y verdadero, o 0 y 1.

695
00:32:36,320 --> 00:32:42,000
Ahora, de nuevo, si tenemos 1 ampersand
0, eso también va a ser 0,

696
00:32:42,000 --> 00:32:47,240
y si tenemos 1 ampersand 1,
finalmente tenemos un 1 bit.

697
00:32:47,240 --> 00:32:50,340
En otras palabras, no estamos haciendo
algo interesante con este operador

698
00:32:50,340 --> 00:32:51,850
por el momento, este operador signo.

699
00:32:51,850 --> 00:32:53,780
Es el operador AND.

700
00:32:53,780 --> 00:32:57,290
Pero estos son los ingredientes
a través del cual podemos hacer

701
00:32:57,290 --> 00:32:59,240
cosas interesantes, como pronto veremos.

702
00:32:59,240 --> 00:33:02,790
>> Ahora vamos a ver sólo la única
barra vertical por aquí a la derecha.

703
00:33:02,790 --> 00:33:06,710
Si tengo un bit 0 y yo
O con el bit a bit

704
00:33:06,710 --> 00:33:11,030
Operador OR, otro bit 0,
eso va a darme 0.

705
00:33:11,030 --> 00:33:17,540
Si tomo un bit 0 y O con
un bit 1, a continuación, voy a conseguir 1.

706
00:33:17,540 --> 00:33:19,830
Y, de hecho, sólo por
claridad, me dejó ir hacia atrás,

707
00:33:19,830 --> 00:33:23,380
de modo que mis barras verticales
no se confunden con 1 de.

708
00:33:23,380 --> 00:33:26,560
Permítanme reescribir todos
mi 1 es un poco más

709
00:33:26,560 --> 00:33:32,700
claramente, de modo que nos vemos la próxima, si
han un 1 o 0, eso va a ser un 1,

710
00:33:32,700 --> 00:33:39,060
y si tengo un 1 O 1 que,
también, va a ser un 1.

711
00:33:39,060 --> 00:33:42,900
Así se puede ver, lógicamente, que la O
operador se comporta de manera muy diferente.

712
00:33:42,900 --> 00:33:48,070
Esto me da 0 O 0 0 me da, pero
cualquier otra combinación me da 1.

713
00:33:48,070 --> 00:33:52,480
Siempre y cuando tengo un 1 en el
fórmula, el resultado va a ser 1.

714
00:33:52,480 --> 00:33:55,580
>> En contraste con la Y
operador, el signo,

715
00:33:55,580 --> 00:34:00,940
sólo si tengo dos de 1 en la
ecuación, puedo realmente conseguir un 1.

716
00:34:00,940 --> 00:34:02,850
Ahora hay algunos otros
operadores también.

717
00:34:02,850 --> 00:34:04,810
Uno de ellos es un poco más complicado.

718
00:34:04,810 --> 00:34:07,980
Así que déjame ir adelante y borrar
esto para liberar algo de espacio.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
Y vamos a echar un vistazo a la
símbolo de intercalación, por un momento.

721
00:34:16,460 --> 00:34:18,210
Esto es típicamente un
carácter que se pueda escribir

722
00:34:18,210 --> 00:34:21,420
en su celebración de teclado Mayús y
entonces uno de los números encima de la de EE.UU.

723
00:34:21,420 --> 00:34:22,250
teclado.

724
00:34:22,250 --> 00:34:26,190
>> Así que esta es la exclusiva
Operador OR, OR exclusiva.

725
00:34:26,190 --> 00:34:27,790
Así que acabamos de ver el operador OR.

726
00:34:27,790 --> 00:34:29,348
Este es el exclusivo operador OR.

727
00:34:29,348 --> 00:34:30,639
¿Qué es realmente la diferencia?

728
00:34:30,639 --> 00:34:34,570
Bueno vamos a ver en la fórmula,
y utilizar esto como ingredientes en última instancia.

729
00:34:34,570 --> 00:34:37,690
0 0 XOR.

730
00:34:37,690 --> 00:34:39,650
Voy a decir es siempre 0.

731
00:34:39,650 --> 00:34:41,400
Esa es la definición de XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 va a ser 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 va a ser 1,
y 1 XOR 1 va a ser?

734
00:34:58,810 --> 00:34:59,890
¿Equivocado?

735
00:34:59,890 --> 00:35:00,520
¿O derecha?

736
00:35:00,520 --> 00:35:01,860
No lo sé.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Ahora, ¿qué está pasando aquí?

739
00:35:04,700 --> 00:35:06,630
Bueno pensar en el
nombre de este operador.

740
00:35:06,630 --> 00:35:09,980
Exclusiva O, por lo que el
nombre, tipo de, sugiere,

741
00:35:09,980 --> 00:35:13,940
la respuesta sólo va a ser
un 1 si las entradas son exclusivos,

742
00:35:13,940 --> 00:35:15,560
exclusivamente diferente.

743
00:35:15,560 --> 00:35:18,170
Así que aquí las entradas son los
mismo, por lo que la salida es 0.

744
00:35:18,170 --> 00:35:20,700
Aquí las entradas son la
mismo, por lo que la salida es 0.

745
00:35:20,700 --> 00:35:25,640
Aquí están las salidas son diferentes,
son exclusivos, por lo que la salida es 1.

746
00:35:25,640 --> 00:35:28,190
Así que es muy similar a la
Y, es muy similar,

747
00:35:28,190 --> 00:35:32,760
o mejor dicho, que es muy similar a la
O, pero sólo de manera exclusiva.

748
00:35:32,760 --> 00:35:36,210
Éste ya no es un 1,
porque tenemos dos de 1,

749
00:35:36,210 --> 00:35:38,621
y no exclusivamente, sólo uno de ellos.

750
00:35:38,621 --> 00:35:39,120
Correcto.

751
00:35:39,120 --> 00:35:40,080
¿Qué pasa con los demás?

752
00:35:40,080 --> 00:35:44,220
Bueno, la tilde, por su parte, es
realmente agradable y sencilla, gracias a Dios.

753
00:35:44,220 --> 00:35:46,410
Y este es un unario
operador, lo que significa

754
00:35:46,410 --> 00:35:50,400
que se aplica a una sola entrada,
un operando, por así decirlo.

755
00:35:50,400 --> 00:35:51,800
No a una izquierda y una derecha.

756
00:35:51,800 --> 00:35:56,050
En otras palabras, si usted toma tilde de
0, la respuesta será la opuesta.

757
00:35:56,050 --> 00:35:59,710
Y si se toma tilde de 1, el
respuesta allí será el opuesto.

758
00:35:59,710 --> 00:36:02,570
Así que el operador tilde es
una forma de negar un poco,

759
00:36:02,570 --> 00:36:06,000
o voltear un poco de
0 a 1, o de 1 a 0.

760
00:36:06,000 --> 00:36:09,820
>> Y eso nos deja finalmente
con sólo dos operadores finales,

761
00:36:09,820 --> 00:36:13,840
El llamado desviación a la izquierda, y la
el llamado operador de desplazamiento a la derecha.

762
00:36:13,840 --> 00:36:16,620
Echemos un vistazo a cómo los trabajos.

763
00:36:16,620 --> 00:36:20,780
El operador de desplazamiento a la izquierda, por escrito
con dos escuadras por el estilo,

764
00:36:20,780 --> 00:36:22,110
funciona como sigue.

765
00:36:22,110 --> 00:36:27,390
Si mi entrada, o mi operando, a la izquierda
operador de desplazamiento es, sencillamente, un 1.

766
00:36:27,390 --> 00:36:33,750
Y entonces digo que la computadora
desviación a la izquierda que 1, dicen siete lugares,

767
00:36:33,750 --> 00:36:37,150
el resultado es como si
tomar ese 1, y moverlo

768
00:36:37,150 --> 00:36:40,160
siete lugares más a la
izquierda, y por defecto,

769
00:36:40,160 --> 00:36:42,270
vamos a suponer que
el espacio a la derecha

770
00:36:42,270 --> 00:36:44,080
va a ser rellenado con ceros.

771
00:36:44,080 --> 00:36:50,316
En otras palabras, 1 izquierda turno 7 va
que me diera que 1, seguido de 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 ceros.

773
00:36:54,060 --> 00:36:57,380
Así que en cierto modo, le permite
tomar un número pequeño como 1,

774
00:36:57,380 --> 00:37:00,740
y claramente que sea mucho
mucho, mucho más grande de esta manera,

775
00:37:00,740 --> 00:37:06,460
pero en realidad estamos yendo a ver
enfoques más inteligentes para que

776
00:37:06,460 --> 00:37:08,080
en su lugar, así,

777
00:37:08,080 --> 00:37:08,720
>> Correcto.

778
00:37:08,720 --> 00:37:10,060
Eso es todo para la semana tres.

779
00:37:10,060 --> 00:37:11,400
Nos vemos la próxima vez.

780
00:37:11,400 --> 00:37:12,770
Este fue CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [REPRODUCCIÓN DE MÚSICA]

783
00:37:22,243 --> 00:37:25,766
>> ALTAVOZ 1: Estaba en la merienda
bar comiendo un helado con chocolate caliente.

784
00:37:25,766 --> 00:37:28,090
Lo tenía todo en su rostro.

785
00:37:28,090 --> 00:37:30,506
Lleva que el chocolate como una barba

786
00:37:30,506 --> 00:37:31,756
ALTAVOZ 2: ¿Qué estás haciendo?

787
00:37:31,756 --> 00:37:32,422
ALTAVOZ 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
¿Qué?

789
00:37:33,500 --> 00:37:36,800
>> ALTAVOZ 2: ¿Acabas de doble inmersión?

790
00:37:36,800 --> 00:37:38,585
Hace doble sumergido el chip.

791
00:37:38,585 --> 00:37:39,460
ALTAVOZ 3: Perdone.

792
00:37:39,460 --> 00:37:44,440
ALTAVOZ 2: Usted sumergido el chip, que
tomó un bocado, y sumergido de nuevo.

793
00:37:44,440 --> 00:37:44,940
ALTAVOZ 3:

794
00:37:44,940 --> 00:37:48,440
ALTAVOZ 2: Así que eso es como poner
a su derecha la boca entera en el dip.

795
00:37:48,440 --> 00:37:52,400
La próxima vez que usted toma un chip,
simplemente sumergir una vez, y acabar con ella.

796
00:37:52,400 --> 00:37:53,890
>> ALTAVOZ 3: ¿Sabes qué, Dan?

797
00:37:53,890 --> 00:37:58,006
Usted sumerge la forma en que desea que echar mano.

798
00:37:58,006 --> 00:38:01,900
Voy a mojar la manera que yo quiero que echar mano.

799
00:38:01,900 --> 00:38:03,194