1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Sección 3 - Más Cómodo]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [Esta es CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Así que la primera pregunta es extrañamente redactada.

5
00:00:12,700 --> 00:00:17,480
GDB le permite "depurar" un programa, sino, más específicamente, ¿qué vamos hacer?

6
00:00:17,480 --> 00:00:22,590
Voy a responder a eso, y yo no sé qué es exactamente lo esperado,

7
00:00:22,590 --> 00:00:27,910
así que supongo que es algo a lo largo de las líneas de deja paso a paso

8
00:00:27,910 --> 00:00:31,540
caminar a través del programa, interactuar con ella, las variables del cambio, hacer todas estas cosas -

9
00:00:31,540 --> 00:00:34,270
básicamente completamente controlar la ejecución de un programa

10
00:00:34,270 --> 00:00:38,410
e inspeccionar cualquier parte dada de la ejecución del programa.

11
00:00:38,410 --> 00:00:43,030
Así que esas funciones le permiten depurar las cosas.

12
00:00:43,030 --> 00:00:44,830
Bien.

13
00:00:44,830 --> 00:00:50,520
¿Por qué la búsqueda binaria que requieren un arreglo pueden ordenar?

14
00:00:50,520 --> 00:00:53,360
¿Quién quiere responder a eso?

15
00:00:56,120 --> 00:01:00,070
[Estudiante] Porque no funciona si no está ordenada. Sí >>. [Risas]

16
00:01:00,070 --> 00:01:04,910
Si no está ordenado, entonces es imposible que dividirlo por la mitad

17
00:01:04,910 --> 00:01:07,850
y saber que todo a la izquierda es menor y todo a la derecha

18
00:01:07,850 --> 00:01:10,490
es mayor que el valor medio.

19
00:01:10,490 --> 00:01:12,790
Así que tiene que ser resuelto.

20
00:01:12,790 --> 00:01:14,170
Bien.

21
00:01:14,170 --> 00:01:17,570
¿Por qué es una especie de burbuja en O del cuadrado n?

22
00:01:17,570 --> 00:01:23,230
¿Hay alguien que primero quiere dar una muy rápida visión general de alto nivel de burbuja qué tipo es?

23
00:01:25,950 --> 00:01:33,020
[Estudiante] Es, básicamente, a través de cada elemento y compruebe los elementos primeros.

24
00:01:33,020 --> 00:01:37,150
Si están fuera de donde cambiarlos, luego de comprobar los elementos próximos y así sucesivamente.

25
00:01:37,150 --> 00:01:40,770
Al llegar a la final, entonces usted sabe que el mayor elemento se coloca en el extremo,

26
00:01:40,770 --> 00:01:42,750
por lo que ignorar aquel entonces sigues pasando,

27
00:01:42,750 --> 00:01:48,490
y cada vez que tiene que comprobar un elemento menos hasta que se haga ningún cambio. Sí >>.

28
00:01:48,490 --> 00:01:58,470
Se llama tipo burbuja, porque si le da la vuelta el conjunto de su lado por lo que es arriba y hacia abajo, vertical,

29
00:01:58,470 --> 00:02:03,100
a continuación, los valores grandes se hunden hasta el fondo y los valores pequeños se burbuja hasta la parte superior.

30
00:02:03,100 --> 00:02:05,210
Esa es la forma en que obtuvo su nombre.

31
00:02:05,210 --> 00:02:08,220
Y sí, que acaba de pasar.

32
00:02:08,220 --> 00:02:11,190
Sigues yendo a través de la matriz, cambiando el valor mayor

33
00:02:11,190 --> 00:02:14,040
para obtener los valores más grandes para la parte inferior.

34
00:02:14,040 --> 00:02:17,500
>> ¿Por qué es O cuadrado de n?

35
00:02:18,690 --> 00:02:24,620
En primer lugar, ¿alguien quiere decir eso que es de O n al cuadrado?

36
00:02:24,620 --> 00:02:28,760
[Estudiante] Debido a que para cada carrera se va n veces.

37
00:02:28,760 --> 00:02:32,100
Sólo se puede estar seguro de que usted ha tomado el elemento más grande hasta el fondo,

38
00:02:32,100 --> 00:02:35,230
entonces usted tiene que repetir eso para tantos elementos. Sí >>.

39
00:02:35,230 --> 00:02:41,800
Así que tenga en cuenta lo grande O significa y qué grandes medios Omega.

40
00:02:41,800 --> 00:02:50,560
El O grande es como el límite superior de lo lento que en realidad se puede ejecutar.

41
00:02:50,560 --> 00:02:58,990
Así que decir que es de O n al cuadrado, no es de O n o de lo que sería capaz de ejecutar

42
00:02:58,990 --> 00:03:02,640
en el tiempo lineal, pero es O de n cubos

43
00:03:02,640 --> 00:03:06,390
porque está limitada por O de n cubos.

44
00:03:06,390 --> 00:03:12,300
Si está acotado por O cuadrado de n, entonces es acotada también por n en cubos.

45
00:03:12,300 --> 00:03:20,280
Por lo tanto, es n al cuadrado, y en el caso peor absoluto que no puede hacer mejor que cuadrada n,

46
00:03:20,280 --> 00:03:22,830
que es por eso que es O de n al cuadrado.

47
00:03:22,830 --> 00:03:31,200
Así que para ver las matemáticas leve en la forma en que viene a ser n al cuadrado,

48
00:03:31,200 --> 00:03:40,530
si tenemos cinco cosas en nuestra lista, por primera vez cómo los swaps muchos podríamos potencialmente necesitan para tomar

49
00:03:40,530 --> 00:03:47,170
con el fin de conseguir esto? Que en realidad sólo -

50
00:03:47,170 --> 00:03:52,040
Cómo swaps muchos vamos a tener que hacer en la primera ejecución de la ordenación de burbuja a través de la matriz?

51
00:03:52,040 --> 00:03:53,540
[Estudiante] n - 1. Sí >>.

52
00:03:53,540 --> 00:03:58,340
>> Si hay 5 elementos, vamos a tener que hacer n - 1.

53
00:03:58,340 --> 00:04:01,100
Luego, en la segunda como swaps muchos vamos a tener que hacer?

54
00:04:01,100 --> 00:04:03,440
[Estudiante] n - 2. Sí >>.

55
00:04:03,440 --> 00:04:11,640
Y la tercera va a ser n - 3 y, a continuación por conveniencia escribiré los dos últimos

56
00:04:11,640 --> 00:04:15,270
como entonces vamos a tener que hacer 2 swaps y swaps 1.

57
00:04:15,270 --> 00:04:19,899
Supongo que el último puede o no puede necesitar realmente a suceder.

58
00:04:19,899 --> 00:04:22,820
Se trata de un intercambio? No se.

59
00:04:22,820 --> 00:04:26,490
Así que estas son las cantidades totales de swaps o por lo menos comparaciones que tienen que hacer.

60
00:04:26,490 --> 00:04:29,910
Incluso si usted no intercambia, usted todavía necesita para comparar los valores.

61
00:04:29,910 --> 00:04:33,910
Así que hay n - 1 comparaciones en la primera pasada a través de la matriz.

62
00:04:33,910 --> 00:04:42,050
Si reorganiza estas cosas, vamos a realmente hacer seis cosas para apilar las cosas muy bien,

63
00:04:42,050 --> 00:04:44,790
y luego voy a hacer 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Así que reorganizar estas sumas, queremos ver cómo muchas comparaciones que hacemos

65
00:04:49,910 --> 00:04:52,700
en el algoritmo completo.

66
00:04:52,700 --> 00:04:56,550
Así que si traemos a estos chicos por aquí,

67
00:04:56,550 --> 00:05:07,470
entonces estamos siendo sólo suma comparaciones sin embargo muchos no lo eran.

68
00:05:07,470 --> 00:05:13,280
Pero si sumamos estos y sumamos estos y sumamos estos,

69
00:05:13,280 --> 00:05:18,130
que sigue siendo el mismo problema. Acabamos de resumir esos grupos en particular.

70
00:05:18,130 --> 00:05:22,400
>> Así que ahora estamos sumando los 3 n. No se trata sólo de 3 n.

71
00:05:22,400 --> 00:05:27,650
Siempre va a ser n / 2 n de.

72
00:05:27,650 --> 00:05:29,430
Así que aquí sucede que tiene 6.

73
00:05:29,430 --> 00:05:34,830
Si tuviéramos 10 cosas, entonces podríamos hacer esta agrupación para 5 pares diferentes de cosas

74
00:05:34,830 --> 00:05:37,180
y terminar con n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Así que siempre vas a obtener n / 2 n, y por lo que este lo vamos a apuntar a n al cuadrado / 2.

76
00:05:45,840 --> 00:05:48,890
Y así, a pesar de ser el factor de la media, que pasa a ser en

77
00:05:48,890 --> 00:05:54,190
por el hecho de que a través de cada iteración en la matriz se comparan menos 1

78
00:05:54,190 --> 00:05:58,040
así es como conseguimos el sobre 2, pero sigue siendo n al cuadrado.

79
00:05:58,040 --> 00:06:01,650
No me importa el factor constante de la mitad.

80
00:06:01,650 --> 00:06:07,760
Así que un montón de grandes cosas O como esto se basa en un solo tipo de hacer esta clase de matemáticas,

81
00:06:07,760 --> 00:06:12,260
haciendo sumas aritméticas y cosas serie geométrica,

82
00:06:12,260 --> 00:06:17,750
pero la mayoría de ellos en este curso son bastante sencillos.

83
00:06:17,750 --> 00:06:19,290
Bien.

84
00:06:19,290 --> 00:06:24,430
¿Por qué es la ordenación por inserción en Omega de n? ¿Qué omega decir?

85
00:06:24,430 --> 00:06:27,730
[Dos estudiantes que hablan a la vez - ininteligible] >> Yeah.

86
00:06:27,730 --> 00:06:30,630
Omega se puede considerar como el límite inferior.

87
00:06:30,630 --> 00:06:36,550
>> Así que no importa qué tan eficiente es su algoritmo de ordenación por inserción es,

88
00:06:36,550 --> 00:06:41,810
independientemente de la lista que se pasa adentro, siempre hay que comparar al menos n cosas

89
00:06:41,810 --> 00:06:44,620
o tiene que iterar n cosas.

90
00:06:44,620 --> 00:06:47,280
¿Por qué es eso?

91
00:06:47,280 --> 00:06:51,190
[Estudiante] Porque si la lista ya está ordenado, y luego a través de la primera iteración

92
00:06:51,190 --> 00:06:54,080
sólo se puede garantizar que el primer elemento es el menor,

93
00:06:54,080 --> 00:06:56,490
y la segunda iteración sólo se pueden garantizar las dos primeras son

94
00:06:56,490 --> 00:07:00,010
porque no saben que el resto de la lista está ordenada. Sí >>.

95
00:07:00,010 --> 00:07:08,910
Si usted pasa en una lista completamente ordenados, por lo menos tienes que ir a través de todos los elementos

96
00:07:08,910 --> 00:07:12,180
para ver que nada necesita ser movido alrededor.

97
00:07:12,180 --> 00:07:14,720
Así que pasando por encima de la lista y diciendo oh, esto ya está clasificado,

98
00:07:14,720 --> 00:07:18,240
es imposible que usted sepa que está ordenados hasta que marque cada elemento

99
00:07:18,240 --> 00:07:20,660
para ver de que están en el orden establecido.

100
00:07:20,660 --> 00:07:25,290
Así que el límite inferior de la ordenación por inserción es Omega de n.

101
00:07:25,290 --> 00:07:28,210
¿Qué es el peor de los casos el tiempo de funcionamiento de tipo fusión,

102
00:07:28,210 --> 00:07:31,390
peor caso es O grandes otra vez?

103
00:07:31,390 --> 00:07:37,660
Así que en el peor de los casos, ¿cómo ordenar fusión correr?

104
00:07:42,170 --> 00:07:43,690
[Estudiante] N log n. Sí >>.

105
00:07:43,690 --> 00:07:49,990
Los más rápidos algoritmos generales de ordenación son n log n. No se puede hacer mejor.

106
00:07:51,930 --> 00:07:55,130
>> Hay casos especiales, y si tenemos tiempo hoy - pero probablemente no verán -

107
00:07:55,130 --> 00:07:59,330
pudimos ver uno que lo haga mejor que n log n.

108
00:07:59,330 --> 00:08:04,050
Pero en el caso general, no se puede hacer nada mejor que n log n.

109
00:08:04,050 --> 00:08:09,680
Y combinar especie pasa a ser el que usted debe saber para este curso que es n log n.

110
00:08:09,680 --> 00:08:13,260
Y por lo que en realidad va a ser la aplicación de dicho hoy.

111
00:08:13,260 --> 00:08:18,070
Y, por último, en no más de tres frases, ¿cómo funciona la selección de clase?

112
00:08:18,070 --> 00:08:20,370
¿Alguien quiere contestar, y yo te cuente sus penas

113
00:08:20,370 --> 00:08:22,390
porque si usted se pasa de 3 -

114
00:08:25,530 --> 00:08:28,330
¿Alguien recuerda tipo de selección?

115
00:08:31,280 --> 00:08:37,809
Tipo de selección es por lo general bastante fácil de recordar sólo por el nombre.

116
00:08:37,809 --> 00:08:45,350
Usted acaba de recorrer el array, encontrar lo que es el valor más grande o más pequeño -

117
00:08:45,350 --> 00:08:47,290
el orden que le toque lavar pulg

118
00:08:47,290 --> 00:08:50,750
Así que digamos que estamos ordenar de menor a mayor.

119
00:08:50,750 --> 00:08:55,250
Usted iterar sobre la matriz, en busca de lo que es el elemento mínimo,

120
00:08:55,250 --> 00:08:59,750
selecciónelo y, a continuación, sólo cambiar lo que está en el primer lugar.

121
00:08:59,750 --> 00:09:04,090
Y luego, en la segunda pasada a través de la matriz, busque el elemento mínimo de nuevo,

122
00:09:04,090 --> 00:09:07,490
selecciónelo y, a continuación, intercambiarlo con lo que está en la segunda posición.

123
00:09:07,490 --> 00:09:10,650
Así que sólo estamos escogiendo y seleccionando los valores mínimos

124
00:09:10,650 --> 00:09:16,050
y su inserción en la parte frontal de la matriz hasta que se ordena.

125
00:09:19,210 --> 00:09:21,560
Las preguntas sobre eso?

126
00:09:21,560 --> 00:09:25,710
>> Estos inevitablemente aparecen en los formularios que tienen que llenar cuando usted está presentando el conjunto de procesadores.

127
00:09:29,010 --> 00:09:32,360
Estos son, básicamente, las respuestas a ellos.

128
00:09:32,360 --> 00:09:34,230
Bien, ahora codificación problemas.

129
00:09:34,230 --> 00:09:40,140
Ya he enviado por correo electrónico - ¿Nadie conseguir que el correo electrónico? Bien.

130
00:09:40,140 --> 00:09:46,630
Ya he enviado por correo electrónico el espacio que vamos a utilizar,

131
00:09:46,630 --> 00:09:52,120
y si haces click en mi nombre - así que creo que voy a estar en el fondo

132
00:09:52,120 --> 00:09:57,170
debido a la r hacia atrás - pero si haces click en mi nombre verás dos revisiones.

133
00:09:57,170 --> 00:10:02,650
Revisión 1 va a ser que ya copiar y pegar el código en los espacios

134
00:10:02,650 --> 00:10:06,900
por lo que la búsqueda va a tener que poner en práctica.

135
00:10:06,900 --> 00:10:10,540
Y Revisión 2 será lo tipo que ponemos en práctica después de eso.

136
00:10:10,540 --> 00:10:15,770
Así que usted puede hacer clic en mi Revisión 1 y trabajar desde allí.

137
00:10:17,350 --> 00:10:22,060
Y ahora queremos implementar la búsqueda binaria.

138
00:10:22,060 --> 00:10:26,470
>> ¿Alguien quiere dar sólo un pseudocódigo de alto nivel explicación

139
00:10:26,470 --> 00:10:31,440
de lo que vamos a tener que hacer para la búsqueda? Si.

140
00:10:31,440 --> 00:10:36,170
[Estudiante] Usted acaba de tomar el centro de la matriz y ver si lo que estás buscando

141
00:10:36,170 --> 00:10:38,650
es menor que o más que eso.

142
00:10:38,650 --> 00:10:41,080
Y si es menos, vas a la parte que es menos,

143
00:10:41,080 --> 00:10:44,750
y si es más, te vas a la media que es más y repetir hasta que usted acaba de conseguir una cosa.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Yeah.

145
00:10:46,570 --> 00:10:51,320
Tenga en cuenta que nuestra matriz de números ya está ordenado,

146
00:10:51,320 --> 00:10:57,190
y por lo que significa que podemos tomar ventaja de eso y pudimos comprobar en primer lugar,

147
00:10:57,190 --> 00:11:00,390
bien, estoy buscando el número 50.

148
00:11:00,390 --> 00:11:03,720
Para que pueda entrar en el centro.

149
00:11:03,720 --> 00:11:07,380
Medio es difícil de definir, cuando es un número par de cosas,

150
00:11:07,380 --> 00:11:10,820
pero digamos que siempre vamos a truncar a la mitad.

151
00:11:10,820 --> 00:11:14,420
Así que aquí tenemos 8 cosas, por lo que la media sería de 16.

152
00:11:14,420 --> 00:11:17,330
Estoy buscando a 50, así que 50 es mayor que 16.

153
00:11:17,330 --> 00:11:21,310
Así que ahora, básicamente, puede tratar mi matriz como estos elementos.

154
00:11:21,310 --> 00:11:23,450
Puedo tirar todo a partir de 16 años.

155
00:11:23,450 --> 00:11:27,440
Ahora mi matriz es sólo estos 4 elementos, y lo repito.

156
00:11:27,440 --> 00:11:31,910
Así que quiero encontrar el medio más, que va a ser 42.

157
00:11:31,910 --> 00:11:34,730
42 es menor que 50, por lo que puedo tirar estos dos elementos.

158
00:11:34,730 --> 00:11:36,890
Este es mi arsenal restante.

159
00:11:36,890 --> 00:11:38,430
Voy a encontrar el medio de nuevo.

160
00:11:38,430 --> 00:11:42,100
Supongo que 50 era un mal ejemplo porque siempre estaba tirando cosas a la izquierda,

161
00:11:42,100 --> 00:11:48,280
pero en la misma medida, si estoy buscando algo

162
00:11:48,280 --> 00:11:52,100
y es menor que el elemento que estoy mirando,

163
00:11:52,100 --> 00:11:55,080
entonces voy a tirar todo a la derecha.

164
00:11:55,080 --> 00:11:58,150
Así que ahora tenemos que aplicar eso.

165
00:11:58,150 --> 00:12:02,310
Tenga en cuenta que tenemos que pasar de tamaño.

166
00:12:02,310 --> 00:12:06,730
No podemos también deben codificar tamaño.

167
00:12:06,730 --> 00:12:11,640
Así que si nos deshacemos de que # define -

168
00:12:19,630 --> 00:12:21,430
Bien.

169
00:12:21,430 --> 00:12:27,180
¿Cómo puedo averiguar muy bien cuál es el tamaño de la matriz de números en la actualidad es?

170
00:12:27,180 --> 00:12:30,950
>> ¿Cuántos elementos hay en la matriz números?

171
00:12:30,950 --> 00:12:33,630
[Estudiantes] Los números, paréntesis,. Longitud?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Eso no existe en C.

173
00:12:36,600 --> 00:12:38,580
Necesidad. Longitud.

174
00:12:38,580 --> 00:12:42,010
Las matrices no tienen propiedades, por lo que no hay ninguna propiedad de las matrices de longitud

175
00:12:42,010 --> 00:12:45,650
que sólo le dará el tiempo que pasa a ser.

176
00:12:48,180 --> 00:12:51,620
[Estudiante] Ver la cantidad de memoria que tiene y dividir por la cantidad - >> Yeah.

177
00:12:51,620 --> 00:12:55,810
Entonces, ¿cómo podemos saber cuánta memoria tiene? >> [Estudiante] sizeof. >> Sí, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof es el operador que va a devolver el tamaño de la matriz de números.

179
00:13:01,680 --> 00:13:10,060
Y eso va a ser enteros sin embargo hay muchas veces el tamaño de un entero

180
00:13:10,060 --> 00:13:14,050
ya que es la cantidad de memoria que está realmente tomando.

181
00:13:14,050 --> 00:13:17,630
Así que si desea que el número de cosas en la matriz,

182
00:13:17,630 --> 00:13:20,560
entonces voy a querer dividir por el tamaño de un entero.

183
00:13:22,820 --> 00:13:26,010
Bien. Así que me permite pasar de tamaño aquí.

184
00:13:26,010 --> 00:13:29,430
¿Por qué tengo que pasar en tamaño después de todo?

185
00:13:29,430 --> 00:13:38,570
¿Por qué no puedo hacer aquí int size = sizeof (pajar) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
¿Por qué no funciona?

187
00:13:41,490 --> 00:13:44,470
[Estudiante] No es una variable global.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack existe y estamos pasando en números como pajar,

189
00:13:51,540 --> 00:13:54,700
y esto es una especie de presagio de lo que vendrá. Si.

190
00:13:54,700 --> 00:14:00,170
[Estudiante] Haystack es sólo la referencia a la misma, por lo que volvería lo grande que es de referencia.

191
00:14:00,170 --> 00:14:02,150
Si.

192
00:14:02,150 --> 00:14:09,000
Dudo que en la conferencia que ha visto la pila todavía realmente, ¿verdad?

193
00:14:09,000 --> 00:14:11,270
Hemos hablado sobre ello.

194
00:14:11,270 --> 00:14:16,090
Así que la pila es donde todas las variables se van a almacenar.

195
00:14:16,090 --> 00:14:19,960
>> Cualquier memoria que está asignada para las variables locales va en la pila,

196
00:14:19,960 --> 00:14:24,790
y cada función tiene su propio espacio en la pila, su propio marco de pila es lo que se llama.

197
00:14:24,790 --> 00:14:31,590
Así que tiene su principal marco de pila, y dentro de ella va a existir esta matriz números,

198
00:14:31,590 --> 00:14:34,270
y que va a ser de tamaño sizeof (números).

199
00:14:34,270 --> 00:14:38,180
Va a tener el tamaño de los números dividido por el tamaño de los elementos,

200
00:14:38,180 --> 00:14:42,010
sino que todas las vidas dentro de marco de pila principal.

201
00:14:42,010 --> 00:14:45,190
Cuando llamamos a la búsqueda, búsqueda obtiene su propio marco de pila,

202
00:14:45,190 --> 00:14:48,840
su propio espacio para almacenar todas sus variables locales.

203
00:14:48,840 --> 00:14:56,420
Pero estos argumentos - así pajar no es una copia de esta matriz completa.

204
00:14:56,420 --> 00:15:00,990
No entregamos en todo el conjunto como una copia en la búsqueda.

205
00:15:00,990 --> 00:15:04,030
Apenas pasa una referencia a la matriz.

206
00:15:04,030 --> 00:15:11,470
Así búsqueda puede acceder a estos números a través de esta referencia.

207
00:15:11,470 --> 00:15:17,100
Es todavía el acceso a las cosas que viven en el interior del marco de pila principal,

208
00:15:17,100 --> 00:15:22,990
pero en el fondo, cuando lleguemos a los punteros, que debe ser breve,

209
00:15:22,990 --> 00:15:24,980
esto es lo que los punteros son.

210
00:15:24,980 --> 00:15:29,400
Los punteros son sólo referencias a las cosas, y se puede utilizar punteros para acceder a las cosas

211
00:15:29,400 --> 00:15:32,030
que se encuentran en los marcos de pila otras cosas.

212
00:15:32,030 --> 00:15:37,660
Así que, aunque el número es local principal, todavía puede acceder a él a través de este puntero.

213
00:15:37,660 --> 00:15:41,770
Pero ya que es simplemente un puntero y es sólo una referencia,

214
00:15:41,770 --> 00:15:45,040
sizeof (pajar) sólo devuelve el tamaño de la misma referencia.

215
00:15:45,040 --> 00:15:47,950
No devuelve el tamaño de lo que está señalando.

216
00:15:47,950 --> 00:15:51,110
No devuelve el tamaño real de los números.

217
00:15:51,110 --> 00:15:55,660
Y para que esto no va a funcionar como se desea.

218
00:15:55,660 --> 00:15:57,320
>> Las preguntas sobre eso?

219
00:15:57,320 --> 00:16:03,250
Los punteros se habrá ido en detalle mucho más sangriento en las semanas por venir.

220
00:16:06,750 --> 00:16:13,740
Y esta es la razón por un montón de cosas que se ven, la mayoría de las cosas o las cosas de orden de búsqueda,

221
00:16:13,740 --> 00:16:16,990
son casi todos vamos a tener que tomar el tamaño real de la matriz,

222
00:16:16,990 --> 00:16:20,440
porque en C, no tenemos idea de lo que el tamaño de la matriz es.

223
00:16:20,440 --> 00:16:22,720
¡Tienes que pasar manualmente pulg

224
00:16:22,720 --> 00:16:27,190
Y no se puede pasar manualmente en toda la matriz, ya que está de paso en la referencia

225
00:16:27,190 --> 00:16:30,390
y no se puede obtener el tamaño de la referencia.

226
00:16:30,390 --> 00:16:32,300
Bien.

227
00:16:32,300 --> 00:16:38,160
Así que ahora queremos poner en práctica lo que se ha explicado anteriormente.

228
00:16:38,160 --> 00:16:41,530
Puede trabajar en él durante un minuto,

229
00:16:41,530 --> 00:16:45,250
y usted no tiene que preocuparse de conseguir todo perfectamente 100% de trabajo.

230
00:16:45,250 --> 00:16:51,410
Sólo tiene que escribir el pseudocódigo medio de cómo creo que debería funcionar.

231
00:16:52,000 --> 00:16:53,630
Bien.

232
00:16:53,630 --> 00:16:56,350
No hay necesidad de estar completamente terminado con esto.

233
00:16:56,350 --> 00:17:02,380
Pero, ¿alguien se sienta cómodo con lo que tengo hasta ahora,

234
00:17:02,380 --> 00:17:05,599
como algo que podemos trabajar de forma conjunta?

235
00:17:05,599 --> 00:17:09,690
¿Alguien quiere ser voluntario? O escogerán aleatoriamente.

236
00:17:12,680 --> 00:17:18,599
No tiene que ser justo por cualquier medida, sino algo que puede modificar en un estado de trabajo.

237
00:17:18,599 --> 00:17:20,720
[Estudiante] Claro. >> Okay.

238
00:17:20,720 --> 00:17:27,220
Así se puede ahorrar la revisión haciendo clic en el pequeño icono Guardar.

239
00:17:27,220 --> 00:17:29,950
Usted es Ramya, ¿verdad? >> [Estudiante] Yeah. >> [Bowden] Bueno.

240
00:17:29,950 --> 00:17:35,140
Así que ahora puedo ver su revisión y todo el mundo puede levantar la revisión.

241
00:17:35,140 --> 00:17:38,600
Y aquí tenemos - Está bien.

242
00:17:38,600 --> 00:17:43,160
Así fue con Ramya la solución recursiva, que es definitivamente una solución válida.

243
00:17:43,160 --> 00:17:44,970
Hay dos maneras que usted puede hacer este problema.

244
00:17:44,970 --> 00:17:48,060
Usted puede hacerlo iterativamente o recursivamente.

245
00:17:48,060 --> 00:17:53,860
La mayoría de los problemas que encuentre que se puede hacer de forma recursiva también puede realizarse iterativamente.

246
00:17:53,860 --> 00:17:58,510
Así que aquí lo hemos hecho de forma recursiva.

247
00:17:58,510 --> 00:18:03,730
>> ¿Alguien quiere definir lo que significa hacer una función recursiva?

248
00:18:07,210 --> 00:18:08,920
[Estudiante] Cuando se tiene una función propia llamada

249
00:18:08,920 --> 00:18:13,470
y luego llamar a sí mismo hasta que salga con verdadero y cierto. Sí >>.

250
00:18:13,470 --> 00:18:17,680
Una función recursiva es una función que se llama a sí misma.

251
00:18:17,680 --> 00:18:24,140
Hay tres cosas importantes que una función recursiva debe tener.

252
00:18:24,140 --> 00:18:27,310
La primera es, obviamente, se llama a sí misma.

253
00:18:27,310 --> 00:18:29,650
El segundo es el caso base.

254
00:18:29,650 --> 00:18:33,390
Así que en algún punto la función tiene que dejar de llamar a sí mismo,

255
00:18:33,390 --> 00:18:35,610
y eso es lo que el caso base es para.

256
00:18:35,610 --> 00:18:43,860
Así que aquí sabemos que debemos dejar, debemos renunciar a nuestra búsqueda

257
00:18:43,860 --> 00:18:48,150
cuando el inicio es igual a extremo - y vamos a repasar lo que eso significa.

258
00:18:48,150 --> 00:18:52,130
Pero, finalmente, la última cosa que es importante para las funciones recursivas:

259
00:18:52,130 --> 00:18:59,250
las funciones de alguna manera debe abordar la causa base.

260
00:18:59,250 --> 00:19:04,140
Al igual que si usted no está realmente actualizar nada cuando usted hace la llamada recursiva en segundo lugar,

261
00:19:04,140 --> 00:19:07,880
si usted está literalmente a la llamada a la función de nuevo con los mismos argumentos

262
00:19:07,880 --> 00:19:10,130
y no hay variables globales han cambiado ni nada,

263
00:19:10,130 --> 00:19:14,430
usted nunca alcanzará el caso base, en cuyo caso eso es malo.

264
00:19:14,430 --> 00:19:17,950
Será una repetición infinita y un desbordamiento de pila.

265
00:19:17,950 --> 00:19:24,330
Pero aquí vemos que la actualización está ocurriendo desde que se inicia la actualización + final / 2,

266
00:19:24,330 --> 00:19:28,180
estamos actualizando el argumento final aquí, estamos actualizando el argumento de inicio aquí.

267
00:19:28,180 --> 00:19:32,860
Así, en todas las llamadas recursivas estamos actualizando algo. Bien.

268
00:19:32,860 --> 00:19:38,110
¿Quieres que nos guiará a través de su solución? >> Claro.

269
00:19:38,110 --> 00:19:44,270
Estoy usando SearchHelp de modo que cada vez que hago esta llamada de función

270
00:19:44,270 --> 00:19:47,910
Tengo el principio de donde yo estoy buscando en la matriz y el fin

271
00:19:47,910 --> 00:19:49,380
de donde yo estoy buscando la matriz.

272
00:19:49,380 --> 00:19:55,330
>> A cada paso, donde se dice que es el elemento central, que es inicio + final / 2,

273
00:19:55,330 --> 00:19:58,850
que es igual a lo que estamos buscando?

274
00:19:58,850 --> 00:20:04,650
Y si es así, entonces que lo encontramos, y supongo que se pasa a los niveles de recursividad.

275
00:20:04,650 --> 00:20:12,540
Y si eso no es cierto, entonces se comprueba si el valor medio de la matriz es demasiado grande,

276
00:20:12,540 --> 00:20:19,320
en cuyo caso nos fijamos en la mitad izquierda de la matriz por va desde el comienzo hasta el índice medio.

277
00:20:19,320 --> 00:20:22,710
Y otra cosa que hacemos la media final.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Bueno.

279
00:20:24,740 --> 00:20:27,730
Eso parece bien.

280
00:20:27,730 --> 00:20:36,640
Está bien, así que un par de cosas, y de hecho, esto es una cosa muy alto nivel

281
00:20:36,640 --> 00:20:41,270
que usted nunca tendrá que saber para este curso, pero es cierto.

282
00:20:41,270 --> 00:20:46,080
Las funciones recursivas, que siempre se oye que son un mal negocio

283
00:20:46,080 --> 00:20:51,160
porque si se llama a sí mismo de forma recursiva demasiadas veces, se obtiene desbordamiento de pila

284
00:20:51,160 --> 00:20:54,990
ya que, como he dicho antes, cada función tiene su propio marco de pila.

285
00:20:54,990 --> 00:20:59,500
Así que cada llamada de la función recursiva obtiene su propio marco de pila.

286
00:20:59,500 --> 00:21:04,140
Así que si usted hace 1.000 llamadas recursivas, se obtiene 1.000 marcos de pila,

287
00:21:04,140 --> 00:21:08,390
y rápidamente le llevará a tener marcos de pila demasiadas cosas y acaba de romper.

288
00:21:08,390 --> 00:21:13,480
Por eso es que las funciones recursivas son generalmente malos.

289
00:21:13,480 --> 00:21:19,370
Pero hay un subconjunto de las funciones recursivas agradable llamado cola de funciones recursivas,

290
00:21:19,370 --> 00:21:26,120
y este pasa a ser un ejemplo de uno en el que si el compilador nota esto

291
00:21:26,120 --> 00:21:29,920
y debe ser, creo - en Clang si se le pasa la bandera-O2

292
00:21:29,920 --> 00:21:33,250
entonces se dará cuenta de esto es la cola recursiva y hacer las cosas bien.

293
00:21:33,250 --> 00:21:40,050
>> Se volverá a utilizar el mismo marco de pila y otra vez para cada llamada recursiva.

294
00:21:40,050 --> 00:21:47,010
Y ya que estás utilizando el mismo marco de pila, usted no tiene que preocuparse acerca de

295
00:21:47,010 --> 00:21:51,690
nunca apilar desbordante, y al mismo tiempo, como dijiste antes,

296
00:21:51,690 --> 00:21:56,380
donde una vez que regrese cierto, entonces hay que devolver todo lo de estos marcos de pila

297
00:21:56,380 --> 00:22:01,740
y la llamada del 10 al SearchHelp tiene que regresar a los días 9, tiene que regresar a la 8a.

298
00:22:01,740 --> 00:22:05,360
Así que no es necesario que ocurra cuando las funciones son cola recursiva.

299
00:22:05,360 --> 00:22:13,740
Y así, lo que hace que esta función recursiva de cola es un aviso de que para cualquier llamada de atención a searchHelp

300
00:22:13,740 --> 00:22:18,470
la llamada recursiva que está haciendo es lo que está regresando.

301
00:22:18,470 --> 00:22:25,290
Así, en la primera llamada a SearchHelp, que sea inmediatamente devolver false,

302
00:22:25,290 --> 00:22:29,590
inmediatamente devolver true, o se hace una llamada recursiva a SearchHelp

303
00:22:29,590 --> 00:22:33,810
donde lo que estamos regresando es lo que esa llamada está regresando.

304
00:22:33,810 --> 00:22:51,560
Y no podríamos hacer esto si lo hiciéramos algo como int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
sólo algunos cambios al azar.

306
00:22:55,440 --> 00:23:01,470
>> Así que ahora esta llamada recursiva, esta int x = SearchHelp llamada recursiva,

307
00:23:01,470 --> 00:23:05,740
ya no es la cola recursiva, ya que en realidad tiene que volver

308
00:23:05,740 --> 00:23:10,400
de nuevo a un marco de pila anterior para que esa llamada previa a la función

309
00:23:10,400 --> 00:23:13,040
A continuación, puede hacer algo con el valor de retorno.

310
00:23:13,040 --> 00:23:22,190
Así que esto no es la cola recursiva, pero lo que teníamos antes es bien cola recursiva. Si.

311
00:23:22,190 --> 00:23:27,000
[Estudiante] ¿No debería el caso de la segunda base se comprueba en primer lugar

312
00:23:27,000 --> 00:23:30,640
porque podría haber una situación en la que cuando se le pasa el argumento

313
00:23:30,640 --> 00:23:35,770
ha empezar = fin, sino que son el valor de la aguja.

314
00:23:35,770 --> 00:23:47,310
La pregunta fue ¿no podemos correr en el caso extremo es el valor de aguja

315
00:23:47,310 --> 00:23:52,000
o empezar = fin, apropiadamente, inicie final =

316
00:23:52,000 --> 00:23:59,480
y no se han comprobado que determinado valor, sin embargo,

317
00:23:59,480 --> 00:24:03,910
a continuación, iniciar + final / 2 es sólo va a ser el mismo valor.

318
00:24:03,910 --> 00:24:07,890
Pero ya hemos vuelto falso y que en realidad nunca comprobado el valor.

319
00:24:07,890 --> 00:24:14,240
Así que al menos, en la primera convocatoria, si el tamaño es 0, entonces queremos devolver false.

320
00:24:14,240 --> 00:24:17,710
Pero si el tamaño es 1, entonces comienzo no va a terminar igual,

321
00:24:17,710 --> 00:24:19,820
y vamos a comprobar al menos el único elemento.

322
00:24:19,820 --> 00:24:26,750
Pero creo que tienes razón en que puede terminar en un caso en el inicio + final / 2,

323
00:24:26,750 --> 00:24:31,190
inicio termina siendo la misma que inicio + final / 2,

324
00:24:31,190 --> 00:24:35,350
pero nunca hemos hecho el check ese elemento.

325
00:24:35,350 --> 00:24:44,740
>> Así que si buscamos en primer lugar es el elemento central del valor que estamos buscando,

326
00:24:44,740 --> 00:24:47,110
entonces puede regresar inmediatamente verdad.

327
00:24:47,110 --> 00:24:50,740
Porque si son iguales, entonces no hay razón para continuar

328
00:24:50,740 --> 00:24:58,440
ya que sólo vamos a actualizar a un caso en el que nos encontramos en una matriz de un solo elemento.

329
00:24:58,440 --> 00:25:01,110
Si ese elemento no es el que estamos buscando,

330
00:25:01,110 --> 00:25:03,530
entonces todo lo que está mal. Si.

331
00:25:03,530 --> 00:25:08,900
[Estudiante] El caso es que ya que el tamaño es más grande que el número de elementos en la matriz,

332
00:25:08,900 --> 00:25:13,070
ya hay un offset - >> Lo mismo ocurrirá con el tamaño -

333
00:25:13,070 --> 00:25:19,380
[Estudiante] Di si la matriz era de tamaño 0, entonces el SearchHelp realmente comprobar pajar de 0

334
00:25:19,380 --> 00:25:21,490
en la primera llamada.

335
00:25:21,490 --> 00:25:25,300
La matriz tiene un tamaño 0, por lo que el 0 es - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Hay otra cosa que - puede ser bueno. Vamos a pensar.

337
00:25:30,750 --> 00:25:40,120
Así que si la matriz con 10 elementos y el del medio que vamos a revisar es el índice de 5,

338
00:25:40,120 --> 00:25:45,700
por lo que estamos comprobando 5, y digamos que el valor es menor.

339
00:25:45,700 --> 00:25:50,720
Así que estamos tirando todo por la borda a partir del 5 en adelante.

340
00:25:50,720 --> 00:25:54,030
Así que empieza a + final / 2 va a ser nuestro nuevo final,

341
00:25:54,030 --> 00:25:57,450
así que sí, que siempre va a estar más allá del final de la matriz.

342
00:25:57,450 --> 00:26:03,570
Si se trata de un caso si era par o impar, entonces podríamos comprobar, por ejemplo, 4,

343
00:26:03,570 --> 00:26:05,770
pero todavía estamos desperdiciando -

344
00:26:05,770 --> 00:26:13,500
Así que sí, al final siempre va a estar más allá del final real de la matriz.

345
00:26:13,500 --> 00:26:18,350
De modo que los elementos que nos estamos centrando, final siempre va a ser el que después de eso.

346
00:26:18,350 --> 00:26:24,270
Y así, si hace arranque termina nunca igual, estamos en una matriz de tamaño 0.

347
00:26:24,270 --> 00:26:35,600
>> La otra cosa que estaba pensando es que estamos actualizando el principio hasta el final se inicio + / 2,

348
00:26:35,600 --> 00:26:44,020
por lo que este es el caso que estoy teniendo problemas con, por dónde empezar + final / 2

349
00:26:44,020 --> 00:26:46,820
es el elemento que está comprobando.

350
00:26:46,820 --> 00:26:58,150
Vamos a decir que tuvimos esta matriz de 10 elementos. Lo que sea.

351
00:26:58,150 --> 00:27:03,250
Así que empieza a + final / 2 va a ser algo así como éste,

352
00:27:03,250 --> 00:27:07,060
y si ese no es el valor, digamos que desea actualizar.

353
00:27:07,060 --> 00:27:10,060
El valor es mayor, por lo que desee ver en esta mitad de la matriz.

354
00:27:10,060 --> 00:27:15,910
Entonces, ¿cómo estamos actualizando principio, estamos actualizando principio para ser ahora este elemento.

355
00:27:15,910 --> 00:27:23,790
Pero esto todavía puede funcionar, o por lo menos, puede hacer start + final / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Estudiante] No es necesario que se comience final + [inaudible] >> Si.

357
00:27:27,850 --> 00:27:33,240
Ya hemos comprobado este elemento y sé que no es la que estamos buscando.

358
00:27:33,240 --> 00:27:36,800
Así que no es necesario actualizar principio para ser este elemento.

359
00:27:36,800 --> 00:27:39,560
Sólo podemos saltar y actualizar empezar a ser este elemento.

360
00:27:39,560 --> 00:27:46,060
¿Y hay alguna vez un caso, vamos a decir, que esto fuera final,

361
00:27:46,060 --> 00:27:53,140
así entonces empezar sería esto, inicie + final / 2 sería esto,

362
00:27:53,140 --> 00:28:00,580
empezar final + - Sí, creo que puede terminar en una recursión infinita.

363
00:28:00,580 --> 00:28:12,690
Vamos a decir que es una matriz de tamaño 2 o una matriz de tamaño 1. Creo que esto va a funcionar.

364
00:28:12,690 --> 00:28:19,490
Así en la actualidad, es que inicio y final elemento es 1 más allá de ella.

365
00:28:19,490 --> 00:28:24,110
De modo que el elemento que vamos a comprobar es éste,

366
00:28:24,110 --> 00:28:29,400
y luego, cuando nos ponemos al día de inicio, estamos actualizando principio para ser 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
que nos va a terminar de nuevo con arranque siendo este elemento.

368
00:28:33,160 --> 00:28:36,210
>> Así que estamos comprobando el elemento mismo una y otra vez.

369
00:28:36,210 --> 00:28:43,310
Así que este es el caso en el que cada llamada recursiva en realidad debe actualizar algo.

370
00:28:43,310 --> 00:28:48,370
Así que tenemos que hacer start + final / 2 + 1, o si no hay un caso

371
00:28:48,370 --> 00:28:50,710
donde no estamos en realidad la actualización inicial.

372
00:28:50,710 --> 00:28:53,820
Todo el mundo ve eso?

373
00:28:53,820 --> 00:28:56,310
Bien.

374
00:28:56,310 --> 00:29:03,860
¿Alguien tiene alguna pregunta sobre esta solución o más comentarios?

375
00:29:05,220 --> 00:29:10,280
Bien. ¿Alguien tiene una solución iterativa que todos podamos mirar?

376
00:29:17,400 --> 00:29:20,940
¿Sabía que todos lo hacen de forma recursiva?

377
00:29:20,940 --> 00:29:25,950
O también supongo que si ella se abrió, entonces usted podría tener anulado su anterior.

378
00:29:25,950 --> 00:29:28,810
¿Se guarda automáticamente? Yo no soy positivo.

379
00:29:35,090 --> 00:29:39,130
¿Alguien ha iterativo?

380
00:29:39,130 --> 00:29:42,430
Podemos caminar a través de ella juntos si no.

381
00:29:46,080 --> 00:29:48,100
La idea va a ser el mismo.

382
00:30:00,260 --> 00:30:02,830
Solución iterativa.

383
00:30:02,830 --> 00:30:07,140
Vamos a querer hacer básicamente la misma idea

384
00:30:07,140 --> 00:30:16,530
dónde queremos llevar la cuenta del nuevo final de la matriz y el nuevo comienzo de la matriz

385
00:30:16,530 --> 00:30:18,510
y hacer eso una y otra vez.

386
00:30:18,510 --> 00:30:22,430
Y si lo que estamos hacer el seguimiento de como el inicio y el final nunca se cruzan,

387
00:30:22,430 --> 00:30:29,020
entonces nosotros no lo encontramos y nos puede devolver false.

388
00:30:29,020 --> 00:30:37,540
Entonces, ¿cómo puedo hacer eso? Alguien tiene sugerencias o código para que yo tire hacia arriba?

389
00:30:42,190 --> 00:30:47,450
[Estudiante] Hacer un bucle while. Sí >>.

390
00:30:47,450 --> 00:30:49,450
Usted va a querer hacer un bucle.

391
00:30:49,450 --> 00:30:51,830
>> ¿Usted tiene un código que podría tirar para arriba, o lo que se le va a sugerir?

392
00:30:51,830 --> 00:30:56,340
[Estudiante] Creo que sí. >> Está bien. Esto hace las cosas más fáciles. ¿Cuál era su nombre?

393
00:30:56,340 --> 00:30:57,890
[Estudiante] Lucas.

394
00:31:00,140 --> 00:31:04,190
Revisión 1. Bien.

395
00:31:04,190 --> 00:31:13,200
Menor es lo que llamamos comenzar antes.

396
00:31:13,200 --> 00:31:17,080
Hasta no es exactamente lo que llamábamos antes de final.

397
00:31:17,080 --> 00:31:22,750
En realidad, está ahora al final de la matriz. Es un elemento que debemos considerar.

398
00:31:22,750 --> 00:31:26,890
Así bajo es 0, arriba es el tamaño de la matriz - 1,

399
00:31:26,890 --> 00:31:34,780
y ahora estamos bucle, y la comprobación se -

400
00:31:34,780 --> 00:31:37,340
Supongo que se puede caminar a través de él.

401
00:31:37,340 --> 00:31:41,420
¿Cuál fue su pensamiento a través de esto? Camina con nosotros a través de su código.

402
00:31:41,420 --> 00:31:49,940
[Estudiante] Claro. Fíjese en el valor pajar en el centro y compararla con la aguja.

403
00:31:49,940 --> 00:31:58,520
Así que si es mayor que su aguja, entonces usted quiere - ¡Oh, en realidad, debería ser al revés.

404
00:31:58,520 --> 00:32:05,180
Usted va a querer tirar la mitad derecha, por lo que sí, que debe ser el camino.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Así que esto debe ser menos? ¿Es eso lo que dijiste? >> [Estudiante] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Bueno. Menos.

407
00:32:10,390 --> 00:32:15,700
Así que si lo que estamos viendo es más pequeño que lo que queremos,

408
00:32:15,700 --> 00:32:19,410
entonces sí, queremos tirar la mitad izquierda,

409
00:32:19,410 --> 00:32:22,210
lo que significa que estamos actualizando todo lo que estamos considerando

410
00:32:22,210 --> 00:32:26,610
moviendo bajo a la derecha de la matriz.

411
00:32:26,610 --> 00:32:30,130
Esto se ve bien.

412
00:32:30,130 --> 00:32:34,550
Creo que tiene el mismo problema que hemos dicho en el anterior,

413
00:32:34,550 --> 00:32:49,760
donde si baja es 0 y hasta es 1, entonces bajo hasta + / 2 se va a establecer a ser lo mismo otra vez.

414
00:32:49,760 --> 00:32:53,860
>> E incluso si ese no es el caso, todavía es más eficiente por lo menos

415
00:32:53,860 --> 00:32:57,630
a tiro de lejos el elemento que acabamos de ver que sabemos que está mal.

416
00:32:57,630 --> 00:33:03,240
Así que bajo + arriba / 2 + 1 - >> [estudiante] Eso debería ser al contrario.

417
00:33:03,240 --> 00:33:05,900
[Bowden] O esto debería ser - 1 y el otro debe ser + 1.

418
00:33:05,900 --> 00:33:09,580
[Estudiante] Y debe haber un doble signo igual. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Estudiante] Yeah.

420
00:33:14,540 --> 00:33:15,910
Bien.

421
00:33:15,910 --> 00:33:21,280
Y, por último, ahora que tenemos este 1 + - 1 cosa,

422
00:33:21,280 --> 00:33:31,520
es que - puede que no sea - es siempre posible bajo para terminar con un valor mayor de hasta?

423
00:33:35,710 --> 00:33:40,320
Creo que la única forma en que puede suceder - ¿Es posible? >> [Estudiante] No lo sé.

424
00:33:40,320 --> 00:33:45,220
Pero si se pone truncada y luego se hace menos que 1 y luego - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Estudiante] Es, posiblemente, llegar en mal estado.

426
00:33:49,700 --> 00:33:53,940
Creo que debería ser bueno sólo porque

427
00:33:53,940 --> 00:33:58,800
para que termine inferior tendrían que ser igual, creo.

428
00:33:58,800 --> 00:34:03,070
Pero si son iguales, entonces no habría hecho el bucle while para empezar

429
00:34:03,070 --> 00:34:06,670
y nos habría devuelto el valor. Así que creo que estamos bien ahora.

430
00:34:06,670 --> 00:34:11,530
Observe que aunque este problema ya no es recursivo,

431
00:34:11,530 --> 00:34:17,400
el mismo tipo de ideas se aplican en el que podemos ver cómo esto tan fácilmente se presta

432
00:34:17,400 --> 00:34:23,659
a una solución recursiva por el hecho de que estamos sólo la actualización de los índices de una y otra vez,

433
00:34:23,659 --> 00:34:29,960
estamos haciendo el problema más pequeño, nos estamos centrando en un subconjunto de la matriz.

434
00:34:29,960 --> 00:34:40,860
[Estudiante] Si baja es 0 y hasta es 1, los dos estarían 0 + 1/2, que iría a 0,

435
00:34:40,860 --> 00:34:44,429
y entonces uno sería + 1, uno sería - 1.

436
00:34:47,000 --> 00:34:50,870
[Estudiante] ¿Dónde estamos comprobando la igualdad?

437
00:34:50,870 --> 00:34:55,100
Al igual que si el medio es realmente aguja?

438
00:34:55,100 --> 00:34:58,590
No estamos actualmente haciendo eso? Oh!

439
00:35:00,610 --> 00:35:02,460
Si es -

440
00:35:05,340 --> 00:35:13,740
Sí. No podemos limitarnos a hacer la prueba aquí porque digamos que la primera mitad -

441
00:35:13,740 --> 00:35:16,430
[Estudiante] De hecho, es como no tirar el encuadernado.

442
00:35:16,430 --> 00:35:20,220
Así que si usted lanza lejos el límite, usted tiene que comprobar primero o lo que sea.

443
00:35:20,220 --> 00:35:23,350
Ah. Si. >> [Estudiante] Yeah.

444
00:35:23,350 --> 00:35:29,650
Así que ahora que hemos tirado la que actualmente mirado,

445
00:35:29,650 --> 00:35:33,260
lo que significa que ahora tenemos que tener también

446
00:35:33,260 --> 00:35:44,810
if (pajar [(baja + hasta) / 2] == aguja), entonces se puede volver realidad.

447
00:35:44,810 --> 00:35:52,070
Y si me pongo más o simplemente si, significa literalmente la misma cosa

448
00:35:52,070 --> 00:35:57,110
porque esto habría vuelto realidad.

449
00:35:57,110 --> 00:36:01,450
Así que voy a poner otro si, pero no importa.

450
00:36:01,450 --> 00:36:10,440
>> Así que si esta cosa, de lo contrario esto, y esto es una cosa común que hago

451
00:36:10,440 --> 00:36:14,340
donde incluso si es el caso en el que todo está bien aquí,

452
00:36:14,340 --> 00:36:22,780
como bajo no puede ser nunca superior a la pata, no es digno de razonamiento acerca de si eso es cierto.

453
00:36:22,780 --> 00:36:28,010
Así que usted puede también decir mientras baja es menor o igual a

454
00:36:28,010 --> 00:36:30,720
o mientras bajo es menor que

455
00:36:30,720 --> 00:36:35,300
por lo que si es que alguna vez sucede igual o menor a dejarla pasar,

456
00:36:35,300 --> 00:36:40,130
entonces podemos salir de este bucle.

457
00:36:41,410 --> 00:36:44,630
Preguntas, inquietudes, comentarios?

458
00:36:47,080 --> 00:36:49,270
Bien. Esto se ve bien.

459
00:36:49,270 --> 00:36:52,230
Ahora queremos hacer una especie.

460
00:36:52,230 --> 00:37:04,030
Si vamos a mi segunda revisión, vemos estos mismos números,

461
00:37:04,030 --> 00:37:07,550
pero ahora ya no están en orden.

462
00:37:07,550 --> 00:37:12,840
Y queremos implementar utilizando cualquier tipo algoritmo en O de n log n.

463
00:37:12,840 --> 00:37:17,240
Entonces, ¿qué algoritmo crees que deberíamos aplicar aquí? >> [Estudiante] tipo de mezcla.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Combinar tipo es O (n log n), así que eso es lo que vamos a hacer.

465
00:37:23,810 --> 00:37:26,680
Y el problema va a ser bastante similar,

466
00:37:26,680 --> 00:37:31,920
donde se presta fácilmente a una solución recursiva.

467
00:37:31,920 --> 00:37:35,580
También podemos llegar a una solución iterativa si queremos,

468
00:37:35,580 --> 00:37:42,540
pero recursión será más fácil aquí y debemos hacer recursividad.

469
00:37:45,120 --> 00:37:49,530
Supongo que tendremos una caminata por tipo de mezcla en primer lugar,

470
00:37:49,530 --> 00:37:54,280
aunque hay un video precioso sobre tipo de combinación ya. [Risas]

471
00:37:54,280 --> 00:37:59,780
Así merge sort hay - me estoy perdiendo gran parte de este trabajo.

472
00:37:59,780 --> 00:38:02,080
Oh, sólo hay una izquierda.

473
00:38:02,080 --> 00:38:03,630
Así se fusionan.

474
00:38:08,190 --> 00:38:12,470
Oh, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Bien.

476
00:38:29,910 --> 00:38:33,460
Merge toma dos matrices independientes.

477
00:38:33,460 --> 00:38:36,780
Individualmente esas dos matrices son ambos ordenados.

478
00:38:36,780 --> 00:38:40,970
Así esta matriz, 1, 3, 5, ordenados. Esta matriz, 0, 2, 4, ordenados.

479
00:38:40,970 --> 00:38:46,710
Ahora, ¿qué combinación debe hacer es combinarlos en una sola matriz que es a su vez ordenados.

480
00:38:46,710 --> 00:38:57,130
Por eso queremos una matriz de tamaño 6 que va a tener estos elementos dentro de ella

481
00:38:57,130 --> 00:38:59,390
de forma ordenada.

482
00:38:59,390 --> 00:39:03,390
>> Y así podemos aprovechar el hecho de que estos dos conjuntos se ordenan

483
00:39:03,390 --> 00:39:06,800
hacerlo en un tiempo lineal,

484
00:39:06,800 --> 00:39:13,510
sentido del tiempo lineal si esta matriz es x tamaño y ésta es y tamaño,

485
00:39:13,510 --> 00:39:20,970
entonces el algoritmo total debe ser O (x + y). Bien.

486
00:39:20,970 --> 00:39:23,150
Así sugerencias.

487
00:39:23,150 --> 00:39:26,030
[Estudiante] Podríamos empezar por la izquierda?

488
00:39:26,030 --> 00:39:30,150
Así que voy a poner el 0 abajo primero y luego el 1 y luego aquí estás en el 2.

489
00:39:30,150 --> 00:39:33,320
Así que es algo así como tiene una ficha que se mueve hacia la derecha. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Para ambos conjuntos si sólo se centran en el elemento más a la izquierda.

491
00:39:41,070 --> 00:39:43,530
Debido a que ambos conjuntos se ordenan, se sabe que estos dos elementos

492
00:39:43,530 --> 00:39:46,920
son los elementos más pequeños, ya sea en matriz.

493
00:39:46,920 --> 00:39:53,500
Así que eso significa que 1 de los 2 elementos deben ser el elemento más pequeño de nuestra gama combinada.

494
00:39:53,500 --> 00:39:58,190
Lo que pasa es que el más pequeño es el de la derecha esta vez.

495
00:39:58,190 --> 00:40:02,580
Así que tomamos 0, insertarlo en la izquierda, porque 0 es menor que 1,

496
00:40:02,580 --> 00:40:08,210
así que 0, la inserta en nuestra posición, y luego actualizamos esta

497
00:40:08,210 --> 00:40:12,070
a centrarnos ahora en el primer elemento.

498
00:40:12,070 --> 00:40:14,570
Y ahora lo repetimos.

499
00:40:14,570 --> 00:40:20,670
Así que ahora comparamos 2 y 1. 1 es más pequeña, así que vamos a insertar 1.

500
00:40:20,670 --> 00:40:25,300
Actualizamos este puntero para apuntar a este chico.

501
00:40:25,300 --> 00:40:33,160
Ahora tenemos que hacerlo de nuevo, así que 2. Esto actualizará, comparar estos 2, 3.

502
00:40:33,160 --> 00:40:37,770
Esto actualiza, luego 4 y 5.

503
00:40:37,770 --> 00:40:42,110
Así que es de mezcla.

504
00:40:42,110 --> 00:40:49,010
>> Debe ser bastante obvio que es el tiempo lineal ya que sólo tiene que ir a través de cada elemento de una vez.

505
00:40:49,010 --> 00:40:55,980
Y ese es el paso más importante para la implementación especie de mezcla está haciendo esto.

506
00:40:55,980 --> 00:40:59,330
Y no es tan difícil.

507
00:40:59,330 --> 00:41:15,020
Un par de cosas de que preocuparse es que vamos a decir que nos fusión 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
En este caso, terminan en el escenario en el que éste va a ser más pequeño,

509
00:41:30,930 --> 00:41:36,160
luego actualizamos este puntero, éste va a ser más pequeños, actualizar esto,

510
00:41:36,160 --> 00:41:41,280
éste es más pequeño, y ahora usted tiene que reconocer

511
00:41:41,280 --> 00:41:44,220
cuando realmente has quedado sin elementos para comparar.

512
00:41:44,220 --> 00:41:49,400
Puesto que ya hemos utilizado este arsenal entero,

513
00:41:49,400 --> 00:41:55,190
todo este conjunto ahora se acaba de insertar en aquí.

514
00:41:55,190 --> 00:42:02,040
Así que si alguna vez llegas a tener el punto de que uno de nuestros arrays está totalmente fusionado ya,

515
00:42:02,040 --> 00:42:06,510
entonces simplemente tomar todos los elementos de la otra matriz e insertarlos en el final de la matriz.

516
00:42:06,510 --> 00:42:13,630
Así que sólo se puede insertar 4, 5, 6. Bien.

517
00:42:13,630 --> 00:42:18,070
Eso es una cosa a tener en cuenta.

518
00:42:22,080 --> 00:42:26,120
Implementación que debe ser el paso 1.

519
00:42:26,120 --> 00:42:32,600
Combinar ordenar luego en base a eso, es 2 pasos, 2 pasos tontos.

520
00:42:38,800 --> 00:42:42,090
Vamos a dar a esta matriz.

521
00:42:57,920 --> 00:43:05,680
Así merge sort, el paso 1 es romper la matriz recursivamente en dos mitades.

522
00:43:05,680 --> 00:43:09,350
Así que dividir este conjunto en dos mitades.

523
00:43:09,350 --> 00:43:22,920
Ahora tenemos 4, 15, 16, 50 y 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Y ahora lo hacemos de nuevo y nos separamos estos en dos mitades.

525
00:43:25,800 --> 00:43:27,530
Yo sólo voy a hacer en este lado.

526
00:43:27,530 --> 00:43:34,790
Así 4, 15 y 16, 50.

527
00:43:34,790 --> 00:43:37,440
Haríamos lo mismo aquí.

528
00:43:37,440 --> 00:43:40,340
Y ahora lo dividimos por la mitad otra vez.

529
00:43:40,340 --> 00:43:51,080
Y tenemos 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Así que ese es nuestro caso base.

531
00:43:53,170 --> 00:44:00,540
Una vez que las matrices son de tamaño 1, entonces se detiene con la división en dos mitades.

532
00:44:00,540 --> 00:44:03,190
>> Ahora, ¿qué hacemos con esto?

533
00:44:03,190 --> 00:44:15,730
Terminamos esto también se dividen en 8, 23, 42, y 108.

534
00:44:15,730 --> 00:44:24,000
Así que ahora que estamos en este momento, ahora paso dos de tipo de combinación es simplemente la fusión de pares para las listas.

535
00:44:24,000 --> 00:44:27,610
Así que queremos fusionar estos. Acabamos de llamar a fusionarse.

536
00:44:27,610 --> 00:44:31,410
Sabemos fusión volverá éstos en el orden establecido.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Ahora queremos unir estos, y que devolverá una lista con los registros en orden,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Nos fusionamos aquellos - que no puedo escribir - 8, 23 y 42, 108.

541
00:44:57,380 --> 00:45:02,890
Así que tenemos pares fusionados vez.

542
00:45:02,890 --> 00:45:05,140
Ahora sólo nos queda unir de nuevo.

543
00:45:05,140 --> 00:45:10,130
Tenga en cuenta que cada una de estas listas se ordenan por sí misma,

544
00:45:10,130 --> 00:45:15,220
y entonces solo puede combinar estas listas para obtener una lista de tamaño 4, que se clasifica

545
00:45:15,220 --> 00:45:19,990
y fusionar estas dos listas para obtener una lista de tamaño 4, que está ordenada.

546
00:45:19,990 --> 00:45:25,710
Y, por último, podemos fusionar esos dos listas de tamaño 4 para obtener una lista de tamaños de 8, que está ordenada.

547
00:45:25,710 --> 00:45:34,030
Así que a ver que esto es general n log n, ya vimos que merge es lineal,

548
00:45:34,030 --> 00:45:40,390
así que cuando nos enfrentamos a la fusión de estos, así como el costo total de fusión

549
00:45:40,390 --> 00:45:43,410
para estas dos listas está a sólo 2 porque -

550
00:45:43,410 --> 00:45:49,610
O bien, es de S n, n pero aquí es sólo estos dos elementos, por lo que es 2.

551
00:45:49,610 --> 00:45:52,850
Y estos 2 será 2 y estos 2 será 2 y estos 2 será 2,

552
00:45:52,850 --> 00:45:58,820
así que a través de todas las fusiones que tenemos que hacer, terminamos haciendo n.

553
00:45:58,820 --> 00:46:03,210
Al igual que 2 + 2 + 2 + 2 es 8, que es N,

554
00:46:03,210 --> 00:46:08,060
por lo que el coste de la combinación de este conjunto es n.

555
00:46:08,060 --> 00:46:10,810
Y lo mismo aquí.

556
00:46:10,810 --> 00:46:16,980
Vamos a combinar estos 2, entonces estos 2, y de forma individual esta fusión se llevará a cuatro operaciones,

557
00:46:16,980 --> 00:46:23,610
esta fusión se llevará a cuatro operaciones, pero una vez más, entre todos ellos,

558
00:46:23,610 --> 00:46:29,030
terminamos la fusión n las cosas en conjunto, por lo que este paso toma n.

559
00:46:29,030 --> 00:46:33,670
Y así, cada nivel tiene n elementos se fusionaron.

560
00:46:33,670 --> 00:46:36,110
>> Y ¿Cuántos niveles hay?

561
00:46:36,110 --> 00:46:40,160
En cada nivel, nuestra matriz crece en tamaño 2.

562
00:46:40,160 --> 00:46:44,590
Aquí nuestras matrices son de tamaño 1, aquí son de tamaño 2, aquí son de tamaño 4,

563
00:46:44,590 --> 00:46:46,470
y, por último, son de tamaño 8.

564
00:46:46,470 --> 00:46:56,450
Así que ya que se duplica, va a haber un total de log n de estos niveles.

565
00:46:56,450 --> 00:47:02,090
Así que con log n niveles, cada nivel individual teniendo n total de operaciones,

566
00:47:02,090 --> 00:47:05,720
obtenemos un log n n algoritmo.

567
00:47:05,720 --> 00:47:07,790
¿Preguntas?

568
00:47:08,940 --> 00:47:13,320
¿La gente ya se ha avanzado en la forma de aplicar esto?

569
00:47:13,320 --> 00:47:18,260
¿Hay alguien ya en un estado en el que sólo puede levantar su código?

570
00:47:20,320 --> 00:47:22,260
Me puede dar un minuto.

571
00:47:24,770 --> 00:47:27,470
Este va a ser más larga.

572
00:47:27,470 --> 00:47:28,730
Recomiendo altamente recurrentes -

573
00:47:28,730 --> 00:47:30,510
Usted no tiene que hacer recursividad para fusión

574
00:47:30,510 --> 00:47:33,750
porque para hacer recursividad para merge, vas a tener que pasar un montón de diferentes tamaños.

575
00:47:33,750 --> 00:47:37,150
Se puede, pero es molesto.

576
00:47:37,150 --> 00:47:43,720
Pero recursividad para ordenar en sí es bastante fácil.

577
00:47:43,720 --> 00:47:49,190
Simplemente llame especie literalmente en la mitad izquierda, más o menos en la mitad derecha. Bien.

578
00:47:51,770 --> 00:47:54,860
¿Alguien tiene algo que pueda levantar ya?

579
00:47:54,860 --> 00:47:57,540
O si no voy a dar un minuto.

580
00:47:58,210 --> 00:47:59,900
Bien.

581
00:47:59,900 --> 00:48:02,970
¿Alguien tiene algo que podamos trabajar?

582
00:48:05,450 --> 00:48:09,680
De lo que sólo tendremos que trabajar con esto y luego expandirse desde allí.

583
00:48:09,680 --> 00:48:14,050
>> Cualquier persona que tenga más de esto que yo puedo levantar?

584
00:48:14,050 --> 00:48:17,770
[Estudiante] Yeah. Usted puede levantar la mía. >> Está bien.

585
00:48:17,770 --> 00:48:19,730
¡Sí!

586
00:48:22,170 --> 00:48:25,280
[Estudiante] Había un montón de condiciones. >> Oh, dispara. ¿Puede usted -

587
00:48:25,280 --> 00:48:28,110
[Estudiante] Tengo que guardarlo. Sí >>.

588
00:48:32,420 --> 00:48:35,730
Así lo hicimos hacer la fusión por separado.

589
00:48:35,730 --> 00:48:38,570
Oh, pero no es tan malo.

590
00:48:39,790 --> 00:48:41,650
Bien.

591
00:48:41,650 --> 00:48:47,080
Así clase en sí es simplemente llamar mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Explícanos qué mergeSortHelp hace.

593
00:48:49,530 --> 00:48:55,700
[Estudiante] MergeSortHelp prácticamente hace los dos pasos principales:

594
00:48:55,700 --> 00:49:01,270
que es clasificar cada medio de la matriz y, a continuación para fusionar los dos.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Está bien, dame un segundo.

596
00:49:10,850 --> 00:49:13,210
Creo que esto - >> [estudiante] Necesito -

597
00:49:17,100 --> 00:49:19,400
Si. Me estoy perdiendo algo.

598
00:49:19,400 --> 00:49:23,100
En combinación, me doy cuenta de que tengo que crear una nueva matriz

599
00:49:23,100 --> 00:49:26,530
porque yo no podía hacerlo en su lugar. Sí >>. No se puede. Corregir.

600
00:49:26,530 --> 00:49:28,170
[Estudiante] Por lo tanto, crear una nueva matriz.

601
00:49:28,170 --> 00:49:31,510
Me olvidé al final de fusionarse para volver a cambiar.

602
00:49:31,510 --> 00:49:34,490
Bien. Necesitamos una nueva matriz.

603
00:49:34,490 --> 00:49:41,000
En tipo de mezcla, esto es casi siempre cierto.

604
00:49:41,000 --> 00:49:44,340
Una parte del coste de un algoritmo mejor en cuanto a tiempo

605
00:49:44,340 --> 00:49:47,310
es casi siempre la necesidad de usar la memoria un poco más.

606
00:49:47,310 --> 00:49:51,570
Así que aquí, no importa lo que hagas merge sort,

607
00:49:51,570 --> 00:49:54,780
que inevitablemente tendría que utilizar algo de memoria extra.

608
00:49:54,780 --> 00:49:58,240
Él o ella creó una nueva matriz.

609
00:49:58,240 --> 00:50:03,400
Y luego dicen que al final sólo tenemos que copiar nueva matriz en la matriz original.

610
00:50:03,400 --> 00:50:04,830
[Estudiante] Creo que sí, sí.

611
00:50:04,830 --> 00:50:08,210
No sé si eso funciona en términos de conteo por referencia o lo que sea -

612
00:50:08,210 --> 00:50:11,650
Sí, va a trabajar. >> [Estudiante] Bueno.

613
00:50:20,620 --> 00:50:24,480
¿Ha intentado ejecutar este? >> [Estudiante] No, todavía no. >> Okay.

614
00:50:24,480 --> 00:50:28,880
Trate de ejecutarlo, y luego voy a hablar de eso por un segundo.

615
00:50:28,880 --> 00:50:35,200
[Estudiante] Necesito tener todos los prototipos de funciones y todo, sin embargo, ¿no?

616
00:50:37,640 --> 00:50:40,840
Los prototipos de función. Oh, te refieres a - sí.

617
00:50:40,840 --> 00:50:43,040
Ordenar llama mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Así que para suerte de llamar mergeSortHelp, mergeSortHelp deberán haber sido definido

619
00:50:47,390 --> 00:50:56,370
antes de ordenar o sólo tenemos el prototipo. Sólo tienes que copiar y pegar eso.

620
00:50:56,370 --> 00:50:59,490
Y del mismo modo, mergeSortHelp llama fusión,

621
00:50:59,490 --> 00:51:03,830
pero fusión no se ha definido todavía, así que podemos dejar saber mergeSortHelp

622
00:51:03,830 --> 00:51:08,700
que eso es lo que va a fusionar verá así, y eso es todo.

623
00:51:09,950 --> 00:51:15,730
Así mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Tenemos un problema aquí donde tenemos ningún caso base.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp es recursivo, por lo que cualquier función recursiva

626
00:51:38,110 --> 00:51:42,610
va a necesitar algún tipo de caso base para saber cuándo parar de forma recursiva se hace llamar.

627
00:51:42,610 --> 00:51:45,590
¿Cuál es nuestro caso base va a estar aquí? Si.

628
00:51:45,590 --> 00:51:49,110
[Estudiante] Si el tamaño es 1? >> [Bowden] Sí.

629
00:51:49,110 --> 00:51:56,220
Así que, como vimos allí, nos detuvimos arrays división

630
00:51:56,220 --> 00:52:01,850
una vez que llegamos en matrices de tamaño 1, lo que inevitablemente se están ordenadas.

631
00:52:01,850 --> 00:52:09,530
Así que si el tamaño es igual a 1, sabemos que la serie ya está ordenado,

632
00:52:09,530 --> 00:52:12,970
por lo que sólo puede volver.

633
00:52:12,970 --> 00:52:16,880
>> Tenga en cuenta que es nula, por lo que no devuelve nada especial, simplemente volver.

634
00:52:16,880 --> 00:52:19,580
Bien. Así que ese es nuestro caso base.

635
00:52:19,580 --> 00:52:27,440
Supongo que nuestro caso base también podría ser si nos toca ser la fusión de una matriz de tamaño 0,

636
00:52:27,440 --> 00:52:30,030
es probable que desee detener en algún momento,

637
00:52:30,030 --> 00:52:33,610
por lo que sólo puede decir tamaño de menos de 2 o menos de o igual a 1

638
00:52:33,610 --> 00:52:37,150
a fin de que esto funcionará para cualquier matriz ahora.

639
00:52:37,150 --> 00:52:38,870
Bien.

640
00:52:38,870 --> 00:52:42,740
Así que ese es nuestro caso base.

641
00:52:42,740 --> 00:52:45,950
Ahora, ¿quieres que nos guiará a través de fusión?

642
00:52:45,950 --> 00:52:49,140
¿Qué significan todos estos casos?

643
00:52:49,140 --> 00:52:54,480
Hasta aquí, sólo estamos haciendo la misma idea, la -

644
00:52:56,970 --> 00:53:02,470
[Estudiante] Necesito que me pasa tamaño con todas las llamadas mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
He añadido un tamaño como principal adicional y no está ahí, como el tamaño / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, tamaño / 2, tamaño / 2. >> [Estudiante] Sí, y también en la función anterior también.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Aquí? >> [Estudiante] Just tamaño. >> [Bowden] Oh. Tamaño, el tamaño? >> [Estudiante] Yeah.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Bueno.

649
00:53:23,010 --> 00:53:26,580
Déjame pensar por un segundo.

650
00:53:26,580 --> 00:53:28,780
No nos encontramos con un problema?

651
00:53:28,780 --> 00:53:33,690
Siempre estamos tratando la izquierda como 0. >> [Estudiante] No.

652
00:53:33,690 --> 00:53:36,340
Eso está mal también. Lo siento. Debe ser inicio. Si.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Bueno. Me gusta más.

654
00:53:39,230 --> 00:53:43,880
Y final. Bien.

655
00:53:43,880 --> 00:53:47,200
Así que ahora quieres que nos guiará a través de fusión? >> [Estudiante] Bueno.

656
00:53:47,200 --> 00:53:52,150
Estoy caminando a través de esta nueva matriz que he creado.

657
00:53:52,150 --> 00:53:57,420
Su tamaño es el tamaño de la porción de la matriz que queremos ser ordenados

658
00:53:57,420 --> 00:54:03,460
y tratando de encontrar el elemento que debo poner en la etapa de nueva matriz.

659
00:54:03,460 --> 00:54:10,140
Así que para hacer eso, primero estoy comprobando si la mitad izquierda de la matriz sigue teniendo elementos más,

660
00:54:10,140 --> 00:54:14,260
y si no es así, entonces hay que bajar a la condición de cosa, que sólo dice

661
00:54:14,260 --> 00:54:20,180
bien, debe estar en la matriz derecha, y vamos a poner eso en el índice actual de newArray.

662
00:54:20,180 --> 00:54:27,620
>> Y a continuación, de lo contrario, estoy comprobando si el lado derecho de la matriz también es terminado,

663
00:54:27,620 --> 00:54:30,630
en cuyo caso sólo hay que poner en la izquierda.

664
00:54:30,630 --> 00:54:34,180
Eso no podría ser en realidad necesario. No estoy seguro.

665
00:54:34,180 --> 00:54:40,970
Pero de todos modos, los otros dos controles que los dos son más pequeñas en la izquierda o la derecha.

666
00:54:40,970 --> 00:54:49,770
Y también en cada caso, estoy incrementando cualquiera que incrementar marcador de posición.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Bueno.

668
00:54:52,040 --> 00:54:53,840
Eso se ve bien.

669
00:54:53,840 --> 00:54:58,800
¿Alguien tiene algún comentario o inquietud o preguntas?

670
00:55:00,660 --> 00:55:07,720
Así que los cuatro casos que tenemos que hacer las cosas en sólo ser - o parece que cinco -

671
00:55:07,720 --> 00:55:13,100
pero debemos tener en cuenta si la matriz de la izquierda se ha quedado sin cosas que tenemos que unir,

672
00:55:13,100 --> 00:55:16,390
si la matriz de la derecha se ha quedado sin cosas que tenemos que fusionar -

673
00:55:16,390 --> 00:55:18,400
Estoy apuntando a nada.

674
00:55:18,400 --> 00:55:21,730
Así que si la matriz de la izquierda se ha quedado sin cosas o la matriz de la derecha se ha quedado sin cosas.

675
00:55:21,730 --> 00:55:24,320
Se trata de dos casos.

676
00:55:24,320 --> 00:55:30,920
También tenemos el caso trivial de que la cosa izquierda es menor que lo correcto.

677
00:55:30,920 --> 00:55:33,910
Entonces queremos elegir lo izquierdo.

678
00:55:33,910 --> 00:55:37,630
Esos son los casos.

679
00:55:37,630 --> 00:55:40,990
Así que esto estaba bien, así que eso es todo.

680
00:55:40,990 --> 00:55:46,760
Matriz de la izquierda. Es 1, 2, 3. Bien. Así que sí, esas son las cuatro cosas que puede ser que desee hacer.

681
00:55:50,350 --> 00:55:54,510
Y no vamos a ir a través de una solución iterativa.

682
00:55:54,510 --> 00:55:55,980
Yo no recomendaría -

683
00:55:55,980 --> 00:56:03,070
Unir tipo es un ejemplo de una función que es a la vez no cola recursiva,

684
00:56:03,070 --> 00:56:07,040
no es fácil de hacer cola recursiva,

685
00:56:07,040 --> 00:56:13,450
pero también no es muy fácil de hacer iterativo.

686
00:56:13,450 --> 00:56:16,910
Esto es muy fácil.

687
00:56:16,910 --> 00:56:19,170
Esta implementación del tipo de mezcla,

688
00:56:19,170 --> 00:56:22,140
fusionar, no importa lo que hagas, vas a construir combinación.

689
00:56:22,140 --> 00:56:29,170
>> Así fusionar tipo construido en la cima de fusión recursiva es sólo estas tres líneas.

690
00:56:29,170 --> 00:56:34,700
Iterativamente, es más molesto y más difícil de pensar.

691
00:56:34,700 --> 00:56:41,860
Pero nótese que no es recursivo cola desde mergeSortHelp - cuando se llama a sí misma -

692
00:56:41,860 --> 00:56:46,590
que todavía tiene que hacer las cosas después de esta llamada recursiva.

693
00:56:46,590 --> 00:56:50,830
Así que este marco de pila debe seguir existiendo incluso después de llamar a esto.

694
00:56:50,830 --> 00:56:54,170
Y luego, cuando se llama a esto, el marco de pila debe seguir existiendo

695
00:56:54,170 --> 00:56:57,780
porque incluso después de esa llamada, todavía tenemos que combinar.

696
00:56:57,780 --> 00:57:01,920
Y es trivial para hacer esta cola recursiva.

697
00:57:04,070 --> 00:57:06,270
¿Preguntas?

698
00:57:08,300 --> 00:57:09,860
Está bien.

699
00:57:09,860 --> 00:57:13,400
Así que volviendo a ordenar - oh, hay dos cosas que quiero mostrarte. Bien.

700
00:57:13,400 --> 00:57:17,840
Volviendo a la clase, vamos a hacer esto rápidamente.

701
00:57:17,840 --> 00:57:21,030
O buscar. Ordenar? Sort. Si.

702
00:57:21,030 --> 00:57:22,730
Volviendo a los comienzos de la especie.

703
00:57:22,730 --> 00:57:29,870
Queremos crear un algoritmo que ordena la matriz mediante cualquier algoritmo

704
00:57:29,870 --> 00:57:33,660
en O de n.

705
00:57:33,660 --> 00:57:40,860
Entonces, ¿cómo es esto posible? ¿Alguien tiene alguna especie de -

706
00:57:40,860 --> 00:57:44,300
Me dio a entender antes de -

707
00:57:44,300 --> 00:57:48,300
Si estamos a punto de mejorar a partir de n log n a O de n,

708
00:57:48,300 --> 00:57:51,450
hemos mejorado nuestro algoritmo en cuanto a tiempo,

709
00:57:51,450 --> 00:57:55,250
lo que significa que vamos a tener que hacer para compensar eso?

710
00:57:55,250 --> 00:57:59,520
[Estudiante] Space. Sí >>. Vamos a estar usando más espacio.

711
00:57:59,520 --> 00:58:04,490
Y ni siquiera sólo más espacio, es exponencialmente más espacio.

712
00:58:04,490 --> 00:58:14,320
Así que creo que este tipo de algoritmo es algo pseudo polinomio pseudo -

713
00:58:14,320 --> 00:58:18,980
pseudo - No puedo recordar. Pseudo algo.

714
00:58:18,980 --> 00:58:22,210
Pero es porque tenemos que utilizar tanto espacio

715
00:58:22,210 --> 00:58:28,610
que se puede lograr, pero no realista.

716
00:58:28,610 --> 00:58:31,220
>> ¿Y cómo se consigue esto?

717
00:58:31,220 --> 00:58:36,810
Podemos lograr esto si te garantizamos que cualquier elemento particular de la matriz

718
00:58:36,810 --> 00:58:39,600
está por debajo de un cierto tamaño.

719
00:58:42,070 --> 00:58:44,500
Así que vamos a decir que el tamaño es de 200,

720
00:58:44,500 --> 00:58:48,130
cualquier elemento de una matriz se encuentra por debajo del tamaño 200.

721
00:58:48,130 --> 00:58:51,080
Y esto es realmente muy realista.

722
00:58:51,080 --> 00:58:58,660
Usted puede fácilmente tener una matriz que ya sabes todo lo que contiene

723
00:58:58,660 --> 00:59:00,570
va a ser menor que cierto número.

724
00:59:00,570 --> 00:59:07,400
Al igual que si usted tiene algún vector absolutamente masivo o algo

725
00:59:07,400 --> 00:59:11,810
pero ya sabes que todo va a estar entre 0 y 5,

726
00:59:11,810 --> 00:59:14,790
entonces va a ser mucho más rápida de hacer esto.

727
00:59:14,790 --> 00:59:17,930
Y la envolvente en cualquiera de los elementos es 5,

728
00:59:17,930 --> 00:59:21,980
por lo que este límite, que es la cantidad de memoria que va a utilizar.

729
00:59:21,980 --> 00:59:26,300
Así que el límite es 200.

730
00:59:26,300 --> 00:59:32,960
En teoría no siempre es un salto desde un número entero sólo puede ser de hasta 4 millones de dólares,

731
00:59:32,960 --> 00:59:40,600
pero eso es poco realista ya que entonces estaríamos utilizando el espacio

732
00:59:40,600 --> 00:59:44,400
del orden de 4 mil millones. Así que eso es poco realista.

733
00:59:44,400 --> 00:59:47,060
Pero aquí vamos a decir que nuestro límite es de 200.

734
00:59:47,060 --> 00:59:59,570
El truco para hacerlo en O de n es que hagamos otra matriz denominada cargos de tamaño OBLIGADO.

735
00:59:59,570 --> 01:00:10,470
Así que en realidad, se trata de un acceso directo - Yo en realidad no sé si Clang hace esto.

736
01:00:11,150 --> 01:00:15,330
Pero en GCC como mínimo - Clang estoy suponiendo que también lo hace -

737
01:00:15,330 --> 01:00:18,180
esto sólo inicializar la matriz completa para ser 0.

738
01:00:18,180 --> 01:00:25,320
Así que si no quieres hacer eso, entonces yo podría hacer por separado for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND, i + +) y cuenta con [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Así que ahora todo se inicializa a 0.

741
01:00:35,260 --> 01:00:39,570
Yo iterar sobre mi matriz,

742
01:00:39,570 --> 01:00:51,920
y lo que estoy haciendo es que estoy contando el número de cada uno - Bajemos aquí.

743
01:00:51,920 --> 01:00:55,480
Tenemos 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Lo que estoy contando es el número de ocurrencias de cada uno de esos elementos.

745
01:01:00,010 --> 01:01:03,470
Vamos a añadir un par realmente más aquí con algunas repeticiones.

746
01:01:03,470 --> 01:01:11,070
Por lo tanto el valor que tenemos aquí, el valor de que va a ser matriz [i].

747
01:01:11,070 --> 01:01:14,850
Así val podría ser 4 o 8 o lo que sea.

748
01:01:14,850 --> 01:01:18,870
Y ahora que estoy contando cuántos de ese valor que he visto,

749
01:01:18,870 --> 01:01:21,230
así recuentos [val] + +;

750
01:01:21,230 --> 01:01:29,430
Una vez hecho esto, el recuento se va a ver algo como 0001.

751
01:01:29,430 --> 01:01:42,190
Vamos a hacer recuento de [valor] - SUJETO + 1.

752
01:01:42,190 --> 01:01:48,230
>> Ahora eso es sólo para explicar el hecho de que estamos empezando desde 0.

753
01:01:48,230 --> 01:01:50,850
Así que si 200 va a ser nuestra mayor número,

754
01:01:50,850 --> 01:01:54,720
entonces 0 a 200 es de 201 cosas.

755
01:01:54,720 --> 01:02:01,540
Así que cuenta, se verá como 00001, porque tenemos un 4.

756
01:02:01,540 --> 01:02:10,210
Entonces tendremos 0001 donde tendremos un 1 en el índice de 8 de conteo.

757
01:02:10,210 --> 01:02:14,560
Vamos a tener un 2 en el índice 23 de la cuenta.

758
01:02:14,560 --> 01:02:17,630
Vamos a tener un 2 en el índice 42 del conteo.

759
01:02:17,630 --> 01:02:21,670
Así que podemos usar la cuenta.

760
01:02:34,270 --> 01:02:44,920
Así num_of_item = cuenta [i].

761
01:02:44,920 --> 01:02:52,540
Y si es así num_of_item es 2, significa que desea insertar 2 de la serie i

762
01:02:52,540 --> 01:02:55,290
en nuestra matriz ordenada.

763
01:02:55,290 --> 01:03:02,000
Así que tenemos que hacer un seguimiento de lo lejos que estamos en la matriz.

764
01:03:02,000 --> 01:03:05,470
So = índice 0.

765
01:03:05,470 --> 01:03:09,910
Array - Voy a escribirlo.

766
01:03:16,660 --> 01:03:18,020
Cuentas -

767
01:03:19,990 --> 01:03:28,580
array [índice + +] = i;

768
01:03:28,580 --> 01:03:32,490
¿Es eso lo que quieres? Creo que eso es lo que quiero.

769
01:03:35,100 --> 01:03:38,290
Sí, esto se ve bien. Bien.

770
01:03:38,290 --> 01:03:43,050
Entonces, ¿todo el mundo entiende lo que el propósito de mi cuenta es la matriz?

771
01:03:43,050 --> 01:03:48,140
Se cuenta el número de ocurrencias de cada uno de estos números.

772
01:03:48,140 --> 01:03:51,780
Entonces estoy iterar sobre esa matriz cuenta,

773
01:03:51,780 --> 01:03:57,190
y la posición i-ésima de la matriz de los recuentos

774
01:03:57,190 --> 01:04:01,930
es el número de i es que debería aparecer en mi matriz ordenada.

775
01:04:01,930 --> 01:04:06,840
Es por eso que los recuentos de 4 va a ser un

776
01:04:06,840 --> 01:04:11,840
y los recuentos de 8 va a ser 1, los recuentos de 23 va a ser 2.

777
01:04:11,840 --> 01:04:16,900
Así es como muchos de los que desea insertar en mi matriz ordenada.

778
01:04:16,900 --> 01:04:19,200
Entonces me acaba de hacer eso.

779
01:04:19,200 --> 01:04:28,960
Estoy insertando num_of_item íes en mi matriz ordenada.

780
01:04:28,960 --> 01:04:31,670
>> ¿Preguntas?

781
01:04:32,460 --> 01:04:43,100
Y así, una vez más, este es el tiempo lineal, ya que estamos sólo iterar sobre esto una vez,

782
01:04:43,100 --> 01:04:47,470
pero también es lineal en lo que este número pasa a ser,

783
01:04:47,470 --> 01:04:50,730
por lo que en gran medida depende de lo que su límite es.

784
01:04:50,730 --> 01:04:53,290
De un salto de 200, que no es tan malo.

785
01:04:53,290 --> 01:04:58,330
Si el límite va a ser 10.000, entonces eso es un poco peor,

786
01:04:58,330 --> 01:05:01,360
pero si su límite va a ser de 4 millones de dólares, que es completamente irreal

787
01:05:01,360 --> 01:05:07,720
y este arreglo se va a tener que ser de tamaño 4 mil millones, lo cual es poco realista.

788
01:05:07,720 --> 01:05:10,860
Así que eso es todo. ¿Preguntas?

789
01:05:10,860 --> 01:05:13,270
[Respuesta de los estudiantes inaudible] >> Okay.

790
01:05:13,270 --> 01:05:15,710
Me di cuenta de otra cosa cuando estábamos pasando.

791
01:05:17,980 --> 01:05:23,720
Creo que el problema estaba en Lucas, y probablemente cada uno que hemos visto.

792
01:05:23,720 --> 01:05:26,330
Me olvidé por completo.

793
01:05:26,330 --> 01:05:31,040
Lo único que quería comentar es que cuando usted está tratando con cosas como índices,

794
01:05:31,040 --> 01:05:38,320
usted nunca realmente ver esto cuando usted está escribiendo un bucle for,

795
01:05:38,320 --> 01:05:41,120
pero técnicamente, cuando usted está tratando con estos índices,

796
01:05:41,120 --> 01:05:45,950
usted debe casi siempre tratan con números enteros sin signo.

797
01:05:45,950 --> 01:05:53,850
La razón de esto es cuando usted está tratando con enteros con signo,

798
01:05:53,850 --> 01:05:56,090
así que si usted tiene 2 enteros con signo y sumarlos

799
01:05:56,090 --> 01:06:00,640
y acaban demasiado grande, entonces usted termina con un número negativo.

800
01:06:00,640 --> 01:06:03,410
Así que eso es lo que es de desbordamiento de enteros.

801
01:06:03,410 --> 01:06:10,500
>> Si añado 2 mil millones y 1 mil millones, termino con negativo 1 mil millones.

802
01:06:10,500 --> 01:06:15,480
Así es como funciona en equipos enteros.

803
01:06:15,480 --> 01:06:17,510
Así que el problema con el uso -

804
01:06:17,510 --> 01:06:23,500
Eso está bien, excepto si baja pasa a ser de hasta 2 mil millones y pasa a ser de 1 mil millones,

805
01:06:23,500 --> 01:06:27,120
entonces esto va a ser negativo 1 mil millones y luego vamos a dividir eso por 2

806
01:06:27,120 --> 01:06:29,730
y terminar con negativo 500 millones.

807
01:06:29,730 --> 01:06:33,760
Así que esto es sólo un problema si le sucede que se busca a través de una matriz

808
01:06:33,760 --> 01:06:38,070
de miles de millones de cosas.

809
01:06:38,070 --> 01:06:44,050
Pero si baja + hasta que ocurre el desbordamiento, entonces eso es un problema.

810
01:06:44,050 --> 01:06:47,750
Tan pronto como los hacemos sin firmar, a continuación, 2 millones más mil millones es de 3 millones de dólares.

811
01:06:47,750 --> 01:06:51,960
3 mil millones dividido por 2 es de 1,5 millones de dólares.

812
01:06:51,960 --> 01:06:55,670
Así que tan pronto como estén sin firmar, todo es perfecto.

813
01:06:55,670 --> 01:06:59,900
Y eso es también un problema cuando usted está escribiendo su bucles for,

814
01:06:59,900 --> 01:07:03,940
y, de hecho, es probable que lo haga de forma automática.

815
01:07:09,130 --> 01:07:12,330
En realidad, se acaba de gritar a ti.

816
01:07:12,330 --> 01:07:21,610
Así que si este número es demasiado grande para ser justo en un entero pero cabría en un entero sin signo,

817
01:07:21,610 --> 01:07:24,970
va a gritar a ti, así que por eso nunca te llegas a tener el problema.

818
01:07:29,150 --> 01:07:34,820
Se puede ver que el índice nunca va a ser negativo,

819
01:07:34,820 --> 01:07:39,220
así que cuando usted está interactuando sobre una matriz,

820
01:07:39,220 --> 01:07:43,970
casi siempre se puede decir unsigned int i, pero que en realidad no tiene que hacerlo.

821
01:07:43,970 --> 01:07:47,110
Las cosas van a funcionar más o menos igual de bien.

822
01:07:48,740 --> 01:07:50,090
Bien. [Susurra] ¿Qué hora es?

823
01:07:50,090 --> 01:07:54,020
Lo último que quería mostrar - y yo sólo voy a hacerlo muy rápido.

824
01:07:54,020 --> 01:08:03,190
¿Sabes cómo hemos # define por lo que puede definir # MAX como 5 o algo así?

825
01:08:03,190 --> 01:08:05,940
No hagamos MAX. # Define OBLIGADO 200. Eso es lo que hicimos antes.

826
01:08:05,940 --> 01:08:10,380
Eso define una constante, que sólo va a ser copiado y pegado

827
01:08:10,380 --> 01:08:13,010
donde nos ha tocado escribir OBLIGADO.

828
01:08:13,010 --> 01:08:18,189
>> Así que en realidad puede hacer más con # define.

829
01:08:18,189 --> 01:08:21,170
Hemos # puede definir funciones.

830
01:08:21,170 --> 01:08:23,410
No son realmente funciones, pero llamaremos funciones.

831
01:08:23,410 --> 01:08:36,000
Un ejemplo podría ser algo como MAX (x, y) se define como (x <y y:? X). Bien.

832
01:08:36,000 --> 01:08:40,660
Por lo que debe acostumbrarse a la sintaxis del operador ternario,

833
01:08:40,660 --> 01:08:49,029
pero es x menor que y? Vuelva a, o regrese x.

834
01:08:49,029 --> 01:08:54,390
Así se puede ver que puede hacer esta función, por separado,

835
01:08:54,390 --> 01:09:01,399
y la función podría ser como bool MAX tiene 2 argumentos, devuelva este.

836
01:09:01,399 --> 01:09:08,340
Esta es una de las más comunes que veo hecho así. Los llamamos macros.

837
01:09:08,340 --> 01:09:11,790
Esta es una macro.

838
01:09:11,790 --> 01:09:15,859
Esto es sólo la sintaxis para ello.

839
01:09:15,859 --> 01:09:18,740
Usted puede escribir una macro para hacer lo que quieras.

840
01:09:18,740 --> 01:09:22,649
Se ven con frecuencia para depurar macros printfs y esas cosas.

841
01:09:22,649 --> 01:09:29,410
Así que un tipo de printf, hay constantes especiales en C como subrayan LÍNEA subrayado,

842
01:09:29,410 --> 01:09:31,710
2 subraya LÍNEA subrayado,

843
01:09:31,710 --> 01:09:37,550
y también hay que pensar dos guiones FUNC. Eso podría ser. Algo por el estilo.

844
01:09:37,550 --> 01:09:40,880
Esas cosas se reemplazará con el nombre de la función

845
01:09:40,880 --> 01:09:42,930
o el número de la línea que te encuentres.

846
01:09:42,930 --> 01:09:48,630
Con frecuencia, se escribe printfs depuración que aquí me podría simplemente escribir

847
01:09:48,630 --> 01:09:54,260
DEBUG y se imprimirá el número de línea y la función que me toca estar en

848
01:09:54,260 --> 01:09:57,020
que encontró que la declaración DEBUG.

849
01:09:57,020 --> 01:09:59,550
Y también se puede imprimir otras cosas.

850
01:09:59,550 --> 01:10:05,990
Así que una cosa que debes tener en cuenta es si se me ocurre para definir # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
algo así como 2 * y 2 * y x.

852
01:10:11,380 --> 01:10:14,310
Así que por razón alguna, le toca hacer mucho de eso.

853
01:10:14,310 --> 01:10:16,650
Así que lo convierten en un macro.

854
01:10:16,650 --> 01:10:18,680
Esto es realmente roto.

855
01:10:18,680 --> 01:10:23,050
Yo diría que es por hacer algo como DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Entonces, ¿cuál debe ser devuelto?

857
01:10:28,840 --> 01:10:30,580
[Estudiante] 12.

858
01:10:30,580 --> 01:10:34,800
Sí, 12 deben ser devueltos, y 12 se devuelve.

859
01:10:34,800 --> 01:10:43,350
3 es reemplazado por x, 6 es reemplazado por y, y volvemos 2 * 6, que tiene 12 años.

860
01:10:43,350 --> 01:10:47,710
Ahora, ¿qué pasa con esto? ¿Cuál debe ser devuelto?

861
01:10:47,710 --> 01:10:50,330
[Estudiante] 14. >> Idealmente, 14.

862
01:10:50,330 --> 01:10:55,290
La cuestión es que la forma de hash define el trabajo, recuerde que es una copia literal y pegar

863
01:10:55,290 --> 01:11:00,160
de casi todo, así que lo que esto va a ser interpretada como

864
01:11:00,160 --> 01:11:11,270
es 3 menos que 1 más 6, 2 veces 1 más 6, 2 veces 3.

865
01:11:11,270 --> 01:11:19,780
>> Así, por esta razón por la que casi siempre envuelven todo entre paréntesis.

866
01:11:22,180 --> 01:11:25,050
Cualquier variable que casi siempre envuelven en paréntesis.

867
01:11:25,050 --> 01:11:29,570
Hay casos en los que no tienen que, como yo sé que no es necesario hacerlo aquí

868
01:11:29,570 --> 01:11:32,110
porque menos es casi siempre sólo se va a trabajar,

869
01:11:32,110 --> 01:11:34,330
a pesar de que ni siquiera podría ser cierto.

870
01:11:34,330 --> 01:11:41,870
Si hay algo ridículo como DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
entonces eso va a quedar sustituido por 3 menos 1 es igual a igual a 2,

872
01:11:49,760 --> 01:11:53,460
y por lo que también va a hacer 3 menos que 1, es igual que 2,

873
01:11:53,460 --> 01:11:55,620
que no es lo que queremos.

874
01:11:55,620 --> 01:12:00,730
Así que para evitar cualquier problema de prioridad de operador,

875
01:12:00,730 --> 01:12:02,870
envuelva siempre entre paréntesis.

876
01:12:03,290 --> 01:12:07,700
Bien. Y eso es todo, 5:30.

877
01:12:08,140 --> 01:12:12,470
Si usted tiene alguna pregunta sobre el conjunto de procesadores, háganoslo saber.

878
01:12:12,470 --> 01:12:18,010
Debe ser divertido, y la edición pirata informático también es mucho más realista

879
01:12:18,010 --> 01:12:22,980
que la edición pirata de la del año pasado, así que esperamos que muchos de ustedes lo intente.

880
01:12:22,980 --> 01:12:26,460
El año pasado fue muy abrumador.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]