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

2
00:00:03,332 --> 00:00:06,490
>> ANDI Peng: Bienvenidos a la semana 3 de la sección.

3
00:00:06,490 --> 00:00:09,550
Gracias, chicos, para todos viene
a esta hora de inicio el día de hoy.

4
00:00:09,550 --> 00:00:11,466
Tenemos un bonito y pequeño
grupo íntimo hoy.

5
00:00:11,466 --> 00:00:14,570
Así que espero que vamos a llegar a
acabado, tal vez, temprano,

6
00:00:14,570 --> 00:00:15,780
un poco temprano hoy.

7
00:00:15,780 --> 00:00:22,057
Así que rápidamente, sólo algunas
anuncios para el orden del día de hoy.

8
00:00:22,057 --> 00:00:23,890
Antes de empezar, estamos
va a ir sobre

9
00:00:23,890 --> 00:00:28,910
algunos problemas logísticos breves, pset
preguntas, interrogar, cosas así.

10
00:00:28,910 --> 00:00:30,250
Y luego vamos a bucear en derecho.

11
00:00:30,250 --> 00:00:34,710
Vamos a utilizar un depurador GDB de llamada
comenzar desacreditando nuestro código, que David

12
00:00:34,710 --> 00:00:36,550
explicó en conferencia el otro día.

13
00:00:36,550 --> 00:00:39,420
Vamos a repasar los cuatro tipos de clases.

14
00:00:39,420 --> 00:00:42,310
Vamos a ir sobre ellos con bastante rapidez
ya que son muy intensivos.

15
00:00:42,310 --> 00:00:45,710
Pero saber que todas las diapositivas y
código fuente son siempre en línea.

16
00:00:45,710 --> 00:00:50,810
Así que no dude, en su lectura, a
volver atrás y echar un vistazo a eso.

17
00:00:50,810 --> 00:00:53,930
>> Iremos a través
notación asintótica, que

18
00:00:53,930 --> 00:00:55,944
es sólo una forma elegante
de decir "los tiempos de ejecución"

19
00:00:55,944 --> 00:00:58,360
donde tenemos la gran O, lo que
David explicó en conferencia.

20
00:00:58,360 --> 00:01:01,550
Y también tenemos Omega, que
es el tiempo de ejecución de límite inferior.

21
00:01:01,550 --> 00:01:06,450
Y hablaremos un poco más
en profundidad con respecto a cómo los trabajos.

22
00:01:06,450 --> 00:01:10,160
Y por último, vamos a repasar búsqueda binaria,
porque muchos de ustedes que ya tienen

23
00:01:10,160 --> 00:01:15,190
miró a sus conjuntos de procesadores probablemente saber que
esa es una pregunta que está en su conjunto de procesadores.

24
00:01:15,190 --> 00:01:17,470
Así que todos estaremos felices
que cubrimos esto hoy.

25
00:01:17,470 --> 00:01:20,610
>> Y por último, por su
sección de comentarios, en realidad

26
00:01:20,610 --> 00:01:23,000
la izquierda a unos 15 minutos a
Al final sólo repasar

27
00:01:23,000 --> 00:01:27,730
logística de pset3, cualquier pregunta,
tal vez un poco de orientación, si se quiere,

28
00:01:27,730 --> 00:01:28,990
antes de empezar la programación.

29
00:01:28,990 --> 00:01:30,890
Así que vamos a tratar de conseguir a través de
el material con bastante rapidez.

30
00:01:30,890 --> 00:01:33,880
Y luego podemos pasar algún tiempo
teniendo más preguntas para el conjunto de procesadores.

31
00:01:33,880 --> 00:01:35,230
OK.

32
00:01:35,230 --> 00:01:39,570
>> Rápidamente, por lo que sólo unos pocos
anuncios antes de empezar hoy.

33
00:01:39,570 --> 00:01:45,410
En primer lugar, recepción para hacer
a través de dos de sus conjuntos de procesadores.

34
00:01:45,410 --> 00:01:49,432
Eché un vistazo al tu-- Sí, vamos a
conseguir un aplauso para ese.

35
00:01:49,432 --> 00:01:51,140
En realidad, yo estaba muy,
realmente impresionados.

36
00:01:51,140 --> 00:01:55,800
Yo califiqué el primer conjunto de procesadores para ustedes
semana y últimos chicos hicieron increíble.

37
00:01:55,800 --> 00:01:58,290
>> Estilo estaba en punto
además de algunos comentarios.

38
00:01:58,290 --> 00:02:00,660
Asegúrese de que está siempre
comentando su código.

39
00:02:00,660 --> 00:02:03,040
Pero sus conjuntos de procesadores estaban a punto.

40
00:02:03,040 --> 00:02:05,549
Y sigue así.

41
00:02:05,549 --> 00:02:08,090
Y es bueno para el grado de
veo que ustedes están poniendo

42
00:02:08,090 --> 00:02:10,704
en tanto esfuerzo en su estilo
y su diseño en su código

43
00:02:10,704 --> 00:02:12,120
que nos gustaría para que usted vea.

44
00:02:12,120 --> 00:02:16,450
Así que estoy pasando por mi gratitud
para el resto de las AATT.

45
00:02:16,450 --> 00:02:19,210
>> Sin embargo, hay una
algunas preguntas Debrief

46
00:02:19,210 --> 00:02:22,010
Sólo quiero ir más que
haría que tanto mi vida

47
00:02:22,010 --> 00:02:24,900
y un montón de la otra
TA 'vive un poco más fácil.

48
00:02:24,900 --> 00:02:28,220
En primer lugar, me he dado cuenta de esto
pasado week-- ¿cuántos de ustedes

49
00:02:28,220 --> 00:02:32,301
han estado funcionando en check50
su código antes de enviar?

50
00:02:32,301 --> 00:02:32,800
OK.

51
00:02:32,800 --> 00:02:36,690
Así que todo el mundo debería estar haciendo check50,
porque-- un secreto-- realidad

52
00:02:36,690 --> 00:02:41,540
ejecutar check50 como parte de nuestra corrección
guiones para probar el código.

53
00:02:41,540 --> 00:02:45,480
Así que si su código está fallando
check50, con toda probabilidad,

54
00:02:45,480 --> 00:02:47,570
que probablemente va a
fracasar el proceso de registro también.

55
00:02:47,570 --> 00:02:49,320
A veces los chicos
tener las respuestas correctas.

56
00:02:49,320 --> 00:02:52,200
Al igual que, en codiciosos, algunos de
usted tiene los números correctos,

57
00:02:52,200 --> 00:02:53,960
que acaba de imprimir algunas cosas extra.

58
00:02:53,960 --> 00:02:55,940
Y ese material extra
en realidad no pasa la verificación,

59
00:02:55,940 --> 00:02:58,440
porque el equipo no
realmente sabe lo que está buscando.

60
00:02:58,440 --> 00:03:00,981
Y así se acaba de ejecutar a través de,
ver que su salida no

61
00:03:00,981 --> 00:03:03,810
igualaremos lo que esperamos la respuesta
ser, y marcar que es un error.

62
00:03:03,810 --> 00:03:06,560
>> Y sé que sucedió en
algunos de sus casos de esta semana.

63
00:03:06,560 --> 00:03:09,870
Así que volví y manual
clasificado de nuevo código de todos.

64
00:03:09,870 --> 00:03:12,780
En el futuro, sin embargo,
por favor, por favor, asegúrese

65
00:03:12,780 --> 00:03:14,570
que se está ejecutando
comprobar 50 en tu código.

66
00:03:14,570 --> 00:03:17,970
Debido a que es una especie de dolor para la TA
a tener que volver atrás y manualmente reclasificar

67
00:03:17,970 --> 00:03:21,197
cada conjunto de procesadores única para cada
único, ejemplo poco perdido.

68
00:03:21,197 --> 00:03:22,530
Así que no me quito ningún punto.

69
00:03:22,530 --> 00:03:25,210
Creo que me quité quizá
uno o dos para el diseño.

70
00:03:25,210 --> 00:03:27,710
En el futuro, aunque, si
usted está fallando check50,

71
00:03:27,710 --> 00:03:31,330
se tomarán puntos
apagado para la corrección.

72
00:03:31,330 --> 00:03:35,020
>> Además, son conjuntos de procesadores
debido viernes a mediodía.

73
00:03:35,020 --> 00:03:38,990
Creo que hay un niño de siete minutos
período de gracia finales que le demos.

74
00:03:38,990 --> 00:03:42,434
Por tiempo de Harvard, que se les permita
siete minutos tarde a todo.

75
00:03:42,434 --> 00:03:44,350
Así que aquí en Yale, vamos a
adherirse a eso también.

76
00:03:44,350 --> 00:03:47,910
Pero más o menos, a las 12:07,
si su conjunto de procesadores no se encuentra en,

77
00:03:47,910 --> 00:03:49,720
que va a ser marcado como tarde.

78
00:03:49,720 --> 00:03:53,160
Y así, mientras se marca
lo más tarde, el TA-- estoy

79
00:03:53,160 --> 00:03:54,870
todavía va a ser la clasificación de sus conjuntos de procesadores.

80
00:03:54,870 --> 00:03:56,760
Así que usted todavía ve aparecer un grado.

81
00:03:56,760 --> 00:03:58,820
Sin embargo, saber que en
Al final del semestre,

82
00:03:58,820 --> 00:04:02,270
todos los conjuntos de procesadores finales serán sólo
puesto a cero automáticamente por el ordenador.

83
00:04:02,270 --> 00:04:04,490
>> Hacemos esto por dos razones.

84
00:04:04,490 --> 00:04:09,220
Uno, a veces obtenemos
excusado, como excusas de Dean,

85
00:04:09,220 --> 00:04:10,762
más adelante que yo no sé nada todavía.

86
00:04:10,762 --> 00:04:13,761
Así que nos gusta asegurarnos de que estamos clasificación
todo por si acaso, como, estoy

87
00:04:13,761 --> 00:04:15,080
falta la excusa de un decano.

88
00:04:15,080 --> 00:04:17,000
Y en segundo lugar, tener en
mente, usted puede todavía

89
00:04:17,000 --> 00:04:19,370
excluir a un conjunto de procesadores que
tiene puntos de alcance completo.

90
00:04:19,370 --> 00:04:21,430
Y así nos gusta grado
todos los conjuntos de procesadores solo

91
00:04:21,430 --> 00:04:24,730
para asegurarse de que su ámbito de aplicación
allí y usted los está tratando.

92
00:04:24,730 --> 00:04:29,150
Así que incluso si es tarde, se le sigue
obtener crédito para los puntos de alcance, creo.

93
00:04:29,150 --> 00:04:33,730
>> Así moraleja de la historia es, hacer
Asegúrese de que sus conjuntos de procesadores están en el tiempo.

94
00:04:33,730 --> 00:04:38,350
Y si no están en el tiempo,
Sabe que no es grande.

95
00:04:38,350 --> 00:04:41,678
Sí, antes de pasar, ¿alguien tiene
cualquier pregunta con respecto retroalimentación pset?

96
00:04:41,678 --> 00:04:42,178
Sí.

97
00:04:42,178 --> 00:04:43,630
>> AUDIENCIA: ¿Has dicho que
puede caer uno de los conjuntos de procesadores?

98
00:04:43,630 --> 00:04:44,296
>> ANDI Peng: Sí.

99
00:04:44,296 --> 00:04:47,050
Así que hay nueve conjuntos de procesadores general
en el transcurso del semestre.

100
00:04:47,050 --> 00:04:50,610
Y si usted tiene alcance
points-- lo alcance es justo,

101
00:04:50,610 --> 00:04:53,567
más o menos, se le intenta la
problema, estás poniendo en el tiempo,

102
00:04:53,567 --> 00:04:56,150
se le muestra que usted tiene
demostrado que hayas leído la especificación.

103
00:04:56,150 --> 00:04:57,191
Eso es más o menos alcance.

104
00:04:57,191 --> 00:04:59,370
Y si usted está cumpliendo
puntos de alcance, que

105
00:04:59,370 --> 00:05:03,360
puede caer más bajo
uno fuera de alcance completo.

106
00:05:03,360 --> 00:05:06,790
Así que eso es en su ventaja para
completar y probar cada conjunto de procesadores.

107
00:05:06,790 --> 00:05:10,320
>> Incluso upload-- si ninguno de
ellos trabajan, subirlos todos.

108
00:05:10,320 --> 00:05:13,711
Y luego vamos a ojalá seamos capaces de
le dará algunos de esos puntos atrás.

109
00:05:13,711 --> 00:05:14,210
Guay.

110
00:05:14,210 --> 00:05:16,780
¿Alguna otra pregunta?

111
00:05:16,780 --> 00:05:17,840
Excelente.

112
00:05:17,840 --> 00:05:21,960
>> En segundo lugar, la oficina horas-- unos pocos
notas rápidas sobre las horas de oficina.

113
00:05:21,960 --> 00:05:24,300
Así que primero, llegar temprano en la semana.

114
00:05:24,300 --> 00:05:26,909
Nadie está nunca en
horario de oficina los lunes.

115
00:05:26,909 --> 00:05:28,700
Christabel vino a
las horas de oficina de la noche anterior.

116
00:05:28,700 --> 00:05:29,691
Sí, Christabel.

117
00:05:29,691 --> 00:05:32,190
¿Y qué nos tenemos en la oficina
horas de anoche, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> AUDIENCIA: Teníamos helado.

119
00:05:33,020 --> 00:05:36,160
>> ANDI Peng: Así que está bien, tuvimos
helado en horario de oficina anoche.

120
00:05:36,160 --> 00:05:39,390
Aunque no puedo prometer que
tendremos helado en horario de oficina

121
00:05:39,390 --> 00:05:43,230
cada semana, lo que puedo prometerte
es que habrá una significativamente

122
00:05:43,230 --> 00:05:45,380
mejor proporción de estudiantes por TA.

123
00:05:45,380 --> 00:05:47,650
Al igual que fiar, es como tres a uno.

124
00:05:47,650 --> 00:05:50,350
Considerando que, contrastar eso con
Jueves, tienes alrededor de 150

125
00:05:50,350 --> 00:05:52,830
muy estresada niños y no helado.

126
00:05:52,830 --> 00:05:55,360
Y no es sólo productiva para cualquier persona.

127
00:05:55,360 --> 00:05:58,730
Así moraleja de la historia es, llegar temprano
a las horas de oficina y las cosas buenas

128
00:05:58,730 --> 00:06:00,310
pasará.

129
00:06:00,310 --> 00:06:02,110
>> También, venga preparado para hacer preguntas.

130
00:06:02,110 --> 00:06:03,200
¿Sabes?

131
00:06:03,200 --> 00:06:05,420
Independientemente de lo que los TA, me
pensar, he estado diciendo,

132
00:06:05,420 --> 00:06:10,710
hemos estado recibiendo un par de estudiantes
que vienen en el jueves en, como, 10:50

133
00:06:10,710 --> 00:06:15,100
no haber leído la especificación
siendo así que me ayude, que me ayude.

134
00:06:15,100 --> 00:06:18,200
Desafortunadamente en ese punto, no hay
no hay mucho que podamos hacer para ayudarle.

135
00:06:18,200 --> 00:06:19,590
Así que por favor venga a principios de la semana.

136
00:06:19,590 --> 00:06:22,040
Venga temprano para las horas de oficina.

137
00:06:22,040 --> 00:06:23,350
Venga preparado para hacer preguntas.

138
00:06:23,350 --> 00:06:25,310
Asegúrese de que usted, como
un estudiante, son donde

139
00:06:25,310 --> 00:06:27,620
tiene que ser para que el
TA puede guiarlo a lo largo,

140
00:06:27,620 --> 00:06:32,850
que es lo que las horas de oficina
debe ser asignado para.

141
00:06:32,850 --> 00:06:37,380
>> En segundo lugar, por lo que sé profesores
gustaría sorprendernos con pruebas.

142
00:06:37,380 --> 00:06:39,439
Tuve un profesor de los
como, yo, por cierto,

143
00:06:39,439 --> 00:06:41,230
recordar que de mitad de período
usted tiene el próximo lunes.

144
00:06:41,230 --> 00:06:42,855
Sí, yo no sé nada de eso de mitad de período.

145
00:06:42,855 --> 00:06:45,630
Así que voy a ser que TA
que recuerda todo lo que prueba

146
00:06:45,630 --> 00:06:47,270
0-- porque, ya sabes, estamos CS.

147
00:06:47,270 --> 00:06:50,730
Ahora que hemos matrices done, se obtiene
por qué es prueba 0, no interrogar a 1, ¿eh?

148
00:06:50,730 --> 00:06:51,320
OK.

149
00:06:51,320 --> 00:06:52,490
Oh, tengo algunas risas en esa.

150
00:06:52,490 --> 00:06:53,120
OK.

151
00:06:53,120 --> 00:06:59,710
>> Así concurso 0 será el 14 de octubre, si
usted está en la sección de lunes a miércoles

152
00:06:59,710 --> 00:07:02,920
y 15 de octubre, si usted está en
la sección de martes a jueves.

153
00:07:02,920 --> 00:07:05,630
Esto no se aplica para los
aquellos de ustedes en Harvard

154
00:07:05,630 --> 00:07:10,350
que-- Creo que todos podrás
tomar sus exámenes en la 14a.

155
00:07:10,350 --> 00:07:13,560
>> Así que sí, la próxima semana, si
David, en la conferencia, se va,

156
00:07:13,560 --> 00:07:15,747
sí, así que en eso
prueba la próxima semana, a todos

157
00:07:15,747 --> 00:07:17,580
no será sorprendido porque
usted vino a la sección

158
00:07:17,580 --> 00:07:19,664
y usted sabe que su
concurso 0 es en dos semanas.

159
00:07:19,664 --> 00:07:21,580
Y tendremos opinión
sesiones y todo.

160
00:07:21,580 --> 00:07:26,360
Así que no te preocupes por
tener miedo por eso.

161
00:07:26,360 --> 00:07:29,890
Cualquier pregunta antes-- alguna pregunta
en todas las cuestiones logísticas relativas,

162
00:07:29,890 --> 00:07:32,591
clasificación, las horas de oficina, secciones?

163
00:07:32,591 --> 00:07:33,090
Sí.

164
00:07:33,090 --> 00:07:35,100
>> AUDIENCIA: Así que la prueba es
va a ser durante la conferencia?

165
00:07:35,100 --> 00:07:35,766
>> ANDI Peng: Sí.

166
00:07:35,766 --> 00:07:39,460
Así que la prueba, creo, es 60
minutos asignados en ese intervalo de tiempo

167
00:07:39,460 --> 00:07:42,240
que usted acaba de tomar
en la sala de conferencias.

168
00:07:42,240 --> 00:07:44,810
Así que usted no tiene que venir en
en, como, un azar 19:00.

169
00:07:44,810 --> 00:07:46,140
Está todo bien.

170
00:07:46,140 --> 00:07:47,100
Sí.

171
00:07:47,100 --> 00:07:50,060
Guay.

172
00:07:50,060 --> 00:07:50,840
>> Correcto.

173
00:07:50,840 --> 00:07:54,330
Así que vamos a
introducir un concepto para usted

174
00:07:54,330 --> 00:08:00,760
esta semana que David ya tiene clase
del tocado en la conferencia de la semana pasada.

175
00:08:00,760 --> 00:08:02,010
Se llama GDB.

176
00:08:02,010 --> 00:08:05,570
¿Y cuántos de ustedes, mientras que en
el curso de la escritura de sus conjuntos de procesadores,

177
00:08:05,570 --> 00:08:09,981
han notado un gran botón que dice
"Depuración" en la parte superior de su IDE?

178
00:08:09,981 --> 00:08:10,480
OK.

179
00:08:10,480 --> 00:08:13,770
Así que ahora vamos a realmente lleguemos a descubrir
el misterio de lo que en realidad botón

180
00:08:13,770 --> 00:08:14,270
hace.

181
00:08:14,270 --> 00:08:16,790
Y te garantizo que, se trata de un
, hermosa cosa hermosa.

182
00:08:16,790 --> 00:08:20,740
>> Así que, hasta ahora, creo que
ha habido dos cosas

183
00:08:20,740 --> 00:08:23,320
los estudiantes han sido típicamente
haciendo al depurar conjuntos de procesadores.

184
00:08:23,320 --> 00:08:27,635
Uno de ellos, o bien añadir en
printf () - por lo que cada pocas líneas,

185
00:08:27,635 --> 00:08:29,760
agregan en un printf () -
oh, ¿qué es esta variable?

186
00:08:29,760 --> 00:08:32,551
Oh, ¿qué es esta variable ahora--
y que tipo de ver la progresión

187
00:08:32,551 --> 00:08:33,940
de su código ya que se ejecuta.

188
00:08:33,940 --> 00:08:37,030
O el segundo método que hacen los niños es
que acaba de escribir todo el asunto

189
00:08:37,030 --> 00:08:38,610
y luego ir así al final.

190
00:08:38,610 --> 00:08:39,970
Esperemos que funciona.

191
00:08:39,970 --> 00:08:44,851
Te garantizo que, GDB es mejor
que ambos de estos métodos.

192
00:08:44,851 --> 00:08:45,350
Sí.

193
00:08:45,350 --> 00:08:46,980
Así que este será su nuevo mejor amigo.

194
00:08:46,980 --> 00:08:51,780
Porque es una cosa hermosa
visualmente que muestra tanto

195
00:08:51,780 --> 00:08:54,850
lo que su código está haciendo
en un punto específico

196
00:08:54,850 --> 00:08:57,486
así como lo que la totalidad de su
variables que están llevando,

197
00:08:57,486 --> 00:08:59,610
como cuáles son sus valores,
en ese punto específico.

198
00:08:59,610 --> 00:09:02,670
Y de esta manera, usted puede realmente
establecer puntos de interrupción en el código.

199
00:09:02,670 --> 00:09:04,350
Usted puede ejecutar a través de línea por línea.

200
00:09:04,350 --> 00:09:07,324
Y BGF sólo tendrá para
usted, muestran para que usted,

201
00:09:07,324 --> 00:09:09,490
lo que todas sus variables
están, qué están haciendo,

202
00:09:09,490 --> 00:09:10,656
lo que está pasando en el código.

203
00:09:10,656 --> 00:09:13,240
Y de tal manera, que es
mucho más fácil de ver

204
00:09:13,240 --> 00:09:17,120
lo que está sucediendo en lugar de-ción printf
o escribir sus declaraciones.

205
00:09:17,120 --> 00:09:19,160
>> Así que vamos a hacer un ejemplo de esto más adelante.

206
00:09:19,160 --> 00:09:20,660
Así que esto parece un poco abstracto.

207
00:09:20,660 --> 00:09:23,490
No se preocupe, nosotros haremos ejemplos.

208
00:09:23,490 --> 00:09:29,170
Y así, en esencia, los tres más grandes,
funciones más utilizadas que necesitará en el BGF

209
00:09:29,170 --> 00:09:32,500
son la continuación, pasar por encima,
y Paso en botones.

210
00:09:32,500 --> 00:09:34,860
Voy a dirigirse
hay, en realidad, en este momento.

211
00:09:34,860 --> 00:09:40,930
>> Así se puede ver que todos los chicos
o debería acercar un poco?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
En la parte posterior, se puede ver eso?

214
00:09:44,470 --> 00:09:45,730
¿Debo hacer un zoom?

215
00:09:45,730 --> 00:09:46,480
¿Solo un poco?

216
00:09:46,480 --> 00:09:49,390
Vale, guay.

217
00:09:49,390 --> 00:09:50,280
Allá vamos.

218
00:09:50,280 --> 00:09:50,960
OK.

219
00:09:50,960 --> 00:09:57,000
>> Así que tengo, aquí, mi
aplicación de codiciosos.

220
00:09:57,000 --> 00:10:01,430
Y mientras muchos de ustedes escribió
codiciosos en bucle while form-- que

221
00:10:01,430 --> 00:10:04,890
es una manera perfectamente aceptable hacer
it-- otra manera de hacerlo es simplemente

222
00:10:04,890 --> 00:10:06,280
dividir en el módulo.

223
00:10:06,280 --> 00:10:09,290
Porque entonces usted puede tener su
valor y luego tienen el resto.

224
00:10:09,290 --> 00:10:11,150
Y entonces usted puede simplemente
añadir todo junto.

225
00:10:11,150 --> 00:10:13,390
¿La lógica de lo que estoy haciendo
aquí tiene sentido para todos,

226
00:10:13,390 --> 00:10:14,117
antes de empezar?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
¿Mas o menos?

229
00:10:17,980 --> 00:10:18,710
Guay.

230
00:10:18,710 --> 00:10:19,210
Excelente.

231
00:10:19,210 --> 00:10:21,290
Es una pieza muy sexy
del código, diría yo.

232
00:10:21,290 --> 00:10:23,502
Como he dicho, David, en
dar una conferencia, después de un tiempo,

233
00:10:23,502 --> 00:10:25,960
todos ustedes comenzará a ver código
como algo que es hermoso.

234
00:10:25,960 --> 00:10:29,950
Y a veces, cuando ves hermosa
código, es una sensación maravillosa.

235
00:10:29,950 --> 00:10:35,410
>> Así que sin embargo, mientras que este código es muy
hermoso, que no funciona correctamente.

236
00:10:35,410 --> 00:10:37,750
Así que vamos a correr check50 en esto.

237
00:10:37,750 --> 00:10:39,440
Compruebe 50 20-- oop.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
¿Es que PSet2?

241
00:10:44,990 --> 00:10:46,870
Sí.

242
00:10:46,870 --> 00:10:47,520
Oh, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
OK.

245
00:10:52,890 --> 00:10:53,900
Así corremos check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> Y como ustedes pueden ver aquí,
está fallando un par de casos.

248
00:11:07,170 --> 00:11:10,165
Y para algunos de ustedes, en el
curso de hacer sus boletines de problemas,

249
00:11:10,165 --> 00:11:11,110
usted es como, ah, ¿por qué no está funcionando.

250
00:11:11,110 --> 00:11:13,318
¿Por qué es trabajando desde hace
valores, pero no para otros?

251
00:11:13,318 --> 00:11:17,760
Bueno, GDB se va a ayudar a la figura
por qué esas entradas no estaban funcionando.

252
00:11:17,760 --> 00:11:18,320
>> OK.

253
00:11:18,320 --> 00:11:21,640
Así que vamos a ver, uno de los
cheques que estaba fallando en check50

254
00:11:21,640 --> 00:11:24,920
era el valor de entrada de 0,41.

255
00:11:24,920 --> 00:11:27,830
Así que la respuesta correcta que
que debería estar recibiendo es un 4.

256
00:11:27,830 --> 00:11:33,090
Pero en lugar de lo que estoy imprimiendo
es el 3-n, que es incorrecto.

257
00:11:33,090 --> 00:11:36,190
Así que vamos a ejecutar esto manualmente, simplemente
asegurarse de que check50 está trabajando.

258
00:11:36,190 --> 00:11:36,940
Hagamos ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Vaya, tengo que hacer codicioso.

261
00:11:43,340 --> 00:11:43,840
Allá vamos.

262
00:11:43,840 --> 00:11:44,381
Ahora ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> ¿Cuánto se le debe?

265
00:11:47,670 --> 00:11:49,550
Hagamos 0.41.

266
00:11:49,550 --> 00:11:52,590
Y sí, nos vemos aquí
que está la salida 3

267
00:11:52,590 --> 00:11:55,160
cuando la respuesta correcta,
De hecho, debería ser 4.

268
00:11:55,160 --> 00:12:01,460
Así que vamos a entrar en el BGF y veamos cómo nos
puede ir sobre la fijación de este problema.

269
00:12:01,460 --> 00:12:03,992
>> Así que el primer paso en
Siempre depurar su código

270
00:12:03,992 --> 00:12:05,950
es establecer un punto de interrupción,
o de un punto en el que

271
00:12:05,950 --> 00:12:09,079
desea que el ordenador o la
depurador para iniciar mirando.

272
00:12:09,079 --> 00:12:11,120
Así que si usted realmente no
sé cuál es tu problema,

273
00:12:11,120 --> 00:12:14,670
por lo general, lo típico queremos
hacer es configurar nuestro punto de interrupción en el principal.

274
00:12:14,670 --> 00:12:18,520
Así que si ustedes pueden ver esto
botón rojo allí,

275
00:12:18,520 --> 00:12:22,860
sí, ese era yo el establecimiento de un
punto de ruptura para la función principal.

276
00:12:22,860 --> 00:12:24,130
Hago clic en eso.

277
00:12:24,130 --> 00:12:26,130
>> Y entonces me puedo ir a mi botón de depuración.

278
00:12:26,130 --> 00:12:27,036
Golpeé ese botón.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Permítanme amplía la imagen si puedo.

281
00:12:36,555 --> 00:12:38,020
Allá vamos.

282
00:12:38,020 --> 00:12:40,730
Así que tenemos, aquí, un panel de la derecha.

283
00:12:40,730 --> 00:12:43,680
Lo siento, chicos en la parte posterior, que
en realidad no puede ver muy bien.

284
00:12:43,680 --> 00:12:49,090
Pero, en esencia, todo
este panel de la derecha está haciendo

285
00:12:49,090 --> 00:12:53,130
es no perder de vista tanto del puesto de relieve
línea, que es la línea de código

286
00:12:53,130 --> 00:12:56,640
que el equipo está ejecutando actualmente,
así como todas sus variables

287
00:12:56,640 --> 00:12:57,600
aquí abajo.

288
00:12:57,600 --> 00:13:00,487
>> Así que tienes centavos, monedas, n,
todas declarado a cosas diferentes

289
00:13:00,487 --> 00:13:01,070
en este punto.

290
00:13:01,070 --> 00:13:04,850
No se preocupe, porque en realidad no tienen
ellos inicializado a cualquier variable todavía.

291
00:13:04,850 --> 00:13:07,200
Así que en su computadora, su
equipo acaba de ver,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 fue la última función utilizada
de ese espacio de memoria en mi equipo.

293
00:13:14,376 --> 00:13:16,000
Así que ahí es donde actualmente centavos es.

294
00:13:16,000 --> 00:13:19,360
Pero nadie que una vez que se ejecuta el código,
debería convertirse inicializado.

295
00:13:19,360 --> 00:13:24,110
>> Así que vamos a ir a través, línea por
line, lo que está pasando aquí.

296
00:13:24,110 --> 00:13:25,350
OK.

297
00:13:25,350 --> 00:13:29,400
Así que aquí están los tres
botones que acabo de explicar.

298
00:13:29,400 --> 00:13:34,090
Usted tiene el juego, o la función Ejecutar,
botón, usted tiene el paso sobre el botón,

299
00:13:34,090 --> 00:13:36,600
y también tiene el Paso en botón.

300
00:13:36,600 --> 00:13:41,260
Y, esencialmente, los tres
ellos sólo van a través de su código

301
00:13:41,260 --> 00:13:42,690
y hacer cosas diferentes.

302
00:13:42,690 --> 00:13:45,680
>> Así que por lo general, cuando usted está de depuración,
nosotros no queremos simplemente pulse Play,

303
00:13:45,680 --> 00:13:47,930
porque Play basta con ejecutar
su código al final de la misma.

304
00:13:47,930 --> 00:13:49,070
Y entonces no lo hará realidad
saber cuál es su problema

305
00:13:49,070 --> 00:13:51,432
es menos que establezca múltiples puntos de interrupción.

306
00:13:51,432 --> 00:13:53,890
Si establece varios puntos de interrupción,
se acaba de forma automática

307
00:13:53,890 --> 00:13:56,030
correr de un punto de ruptura,
a la siguiente, a la siguiente.

308
00:13:56,030 --> 00:13:58,030
Pero en este caso que hemos
sólo que uno, porque

309
00:13:58,030 --> 00:13:59,970
quieren trabajar nuestro camino
de arriba hacia abajo a abajo.

310
00:13:59,970 --> 00:14:04,830
Así que vamos a ignorar ese botón
en este momento para los propósitos de este programa.

311
00:14:04,830 --> 00:14:08,230
>> Así que el paso sobre la función solo
pasos sobre cada línea

312
00:14:08,230 --> 00:14:11,510
y te dice lo que
el equipo está haciendo.

313
00:14:11,510 --> 00:14:14,630
El Paso en función va
en la función real

314
00:14:14,630 --> 00:14:16,000
eso es en su línea de código.

315
00:14:16,000 --> 00:14:19,070
Así, por ejemplo, como printf (),
que es una función, ¿no?

316
00:14:19,070 --> 00:14:21,980
Si quisiera paso físicamente
en la función printf (),

317
00:14:21,980 --> 00:14:25,610
Yo realmente entrar en el pedazo de
código donde printf () fue escrito y ver

318
00:14:25,610 --> 00:14:26,730
que esta pasando ahí.

319
00:14:26,730 --> 00:14:29,924
>> Pero por lo general, se supone que
el código que te damos funciona.

320
00:14:29,924 --> 00:14:31,340
Asumimos el printf () está trabajando.

321
00:14:31,340 --> 00:14:33,170
Suponemos que getInt () está trabajando.

322
00:14:33,170 --> 00:14:35,170
Así que no hay necesidad de
entrar en esas funciones.

323
00:14:35,170 --> 00:14:37,170
Pero si hay funciones
que escriba usted mismo

324
00:14:37,170 --> 00:14:39,060
que desea comprobar
lo que está pasando,

325
00:14:39,060 --> 00:14:41,200
usted quiere dar un paso
en esa función.

326
00:14:41,200 --> 00:14:43,940
>> Así que ahora sólo vamos
al pasar por encima de este trozo de código.

327
00:14:43,940 --> 00:14:44,485
Así que vamos a ver.

328
00:14:44,485 --> 00:14:46,547
Oh, imprimir, "Oh hai, cómo
se debió en gran cambio? "

329
00:14:46,547 --> 00:14:47,130
No nos importa.

330
00:14:47,130 --> 00:14:49,830
Sabemos que está funcionando,
así que pasar por encima de ella.

331
00:14:49,830 --> 00:14:53,290
>> Así que n, que es nuestra carroza que
que hemos initialized-- o declared--

332
00:14:53,290 --> 00:14:56,810
en la parte superior, ahora estamos
igualando que a GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Así que vamos a pasar por encima de eso.

334
00:14:57,810 --> 00:14:59,580
Y vemos en la
fondo aquí, el programa

335
00:14:59,580 --> 00:15:03,360
me está incitando a la entrada de un valor.

336
00:15:03,360 --> 00:15:08,580
Así de entrada de dejar que el valor que queremos
para probar aquí, que es 0,41.

337
00:15:08,580 --> 00:15:09,160
Excelente.

338
00:15:09,160 --> 00:15:12,780
>> Así que ahora n-- ¿Ustedes Ver
aquí, en el bottom-- es

339
00:15:12,780 --> 00:15:15,140
stored-- porque
no han redondeado sin embargo, es

340
00:15:15,140 --> 00:15:19,540
almacenada en este gigante como
flotante que es 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
que es lo suficientemente cerca de nuestro
propósitos, ahora mismo, a 0,41.

342
00:15:22,550 --> 00:15:26,090
Y luego ya veremos más adelante, a medida que
continuar pasando por encima del programa,

343
00:15:26,090 --> 00:15:29,850
después aquí, n se ha convertido en
redondeada y centavos se ha convertido en 41.

344
00:15:29,850 --> 00:15:30,350
Excelente.

345
00:15:30,350 --> 00:15:32,230
Así que sabemos que el trabajo de nuestra redondeo.

346
00:15:32,230 --> 00:15:34,700
Sabemos que tenemos la
número correcto de centavos,

347
00:15:34,700 --> 00:15:36,990
así que sabemos que eso es
no es realmente el problema.

348
00:15:36,990 --> 00:15:40,050
>> Así que seguimos paso a paso
en este programa.

349
00:15:40,050 --> 00:15:40,900
Vamos aquí.

350
00:15:40,900 --> 00:15:46,139
Y así, después de esta línea de código,
debe saber cuántos cuartos que tenemos.

351
00:15:46,139 --> 00:15:46,680
Damos un paso más.

352
00:15:46,680 --> 00:15:52,040
Y usted ver lo que hacemos, de hecho, tenemos un solo
trimestre porque hemos restamos 25

353
00:15:52,040 --> 00:15:53,790
de nuestro valor inicial de 41.

354
00:15:53,790 --> 00:15:55,890
Y tenemos 16 izquierda para nuestros centavos.

355
00:15:55,890 --> 00:15:58,830
>> ¿Todo el mundo entiende cómo
el programa está intensificando a través

356
00:15:58,830 --> 00:16:02,980
y por qué centavos ahora se ha convertido en 16
y por qué, ahora, las monedas se ha convertido en 1?

357
00:16:02,980 --> 00:16:04,610
Está todo el mundo siguiendo esa lógica?

358
00:16:04,610 --> 00:16:05,110
Guay.

359
00:16:05,110 --> 00:16:07,860
Así que a partir de este punto, el
de trabajo del programa, ¿no?

360
00:16:07,860 --> 00:16:09,797
Sabemos que está haciendo exactamente
lo que queremos que lo haga.

361
00:16:09,797 --> 00:16:11,880
Y no lo hicimos realidad
tienen que imprimir, oh, qué

362
00:16:11,880 --> 00:16:14,430
es céntimos en este punto,
lo que es las monedas en este punto.

363
00:16:14,430 --> 00:16:17,170
>> Seguimos pasando por el programa.

364
00:16:17,170 --> 00:16:18,100
Paso terminado.

365
00:16:18,100 --> 00:16:18,620
Guay.

366
00:16:18,620 --> 00:16:19,700
Repasamos monedas de diez centavos.

367
00:16:19,700 --> 00:16:20,200
Excelente.

368
00:16:20,200 --> 00:16:22,367
Vemos que se toma
de $ 0.10 para un centavo.

369
00:16:22,367 --> 00:16:23,450
Y ahora tenemos dos monedas.

370
00:16:23,450 --> 00:16:25,260
Eso es correcto.

371
00:16:25,260 --> 00:16:31,555
>> Repasamos peniques y vemos
que que nos queda más centavos.

372
00:16:31,555 --> 00:16:32,680
Hmm, eso es extraño.

373
00:16:32,680 --> 00:16:37,540
Hasta aquí, en el programa, que se suponía
haber restado mis peniques.

374
00:16:37,540 --> 00:16:39,400
Tal vez yo no estaba
haciendo que la línea derecha.

375
00:16:39,400 --> 00:16:42,190
Y por desgracia, se puede ver
aquí, porque sabemos

376
00:16:42,190 --> 00:16:44,360
que estamos pisando
a través de líneas 32 y 33,

377
00:16:44,360 --> 00:16:50,560
ahí es donde nuestro programa
inapropiadamente tuvieron las variables corren.

378
00:16:50,560 --> 00:16:55,136
Así que podemos mirar y ver, oh,
Estoy restando centavos aquí,

379
00:16:55,136 --> 00:16:57,010
pero no estoy realmente
añadir a mi valor de la moneda.

380
00:16:57,010 --> 00:16:57,860
Estoy añadiendo a centavos.

381
00:16:57,860 --> 00:17:00,234
Y yo no quiero añadir a
centavos, quiero añadir a monedas.

382
00:17:00,234 --> 00:17:05,420
Así que si cambiamos eso a monedas,
tenemos un programa de trabajo.

383
00:17:05,420 --> 00:17:06,730
Puedo correr check50.

384
00:17:06,730 --> 00:17:11,063
Usted sólo puede salir del BGF derecho
aquí y luego ejecutar check50 nuevo.

385
00:17:11,063 --> 00:17:11,938
Yo sólo podía hacer esto.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Tengo que hacer codicioso.

388
00:17:18,480 --> 00:17:19,940
0.41.

389
00:17:19,940 --> 00:17:22,819
Y aquí, es la impresión
la respuesta correcta.

390
00:17:22,819 --> 00:17:26,569
>> Así como ustedes pueden ver, el BGF
es una herramienta muy potente

391
00:17:26,569 --> 00:17:29,940
para cuando tenemos tanto código
pasando y tantas variables

392
00:17:29,940 --> 00:17:32,510
que es difícil para nosotros, como
un ser humano, no perder de vista.

393
00:17:32,510 --> 00:17:35,360
El equipo, en el BGF
depurador, tiene la capacidad

394
00:17:35,360 --> 00:17:37,020
hacer un seguimiento de todo.

395
00:17:37,020 --> 00:17:40,480
Lo sé, en Visionaire, ustedes probablemente
podría haber afectado a algunos fallos de segmentación

396
00:17:40,480 --> 00:17:43,150
debido a que se estaba ejecutando
fuera de los límites de la matriz.

397
00:17:43,150 --> 00:17:46,510
En el ejemplo de César, eso es
exactamente lo que he implementado aquí.

398
00:17:46,510 --> 00:17:50,060
>> Así que me olvidé de comprobar
¿qué pasaría si yo

399
00:17:50,060 --> 00:17:52,510
no tener dos argumentos de la línea de comandos.

400
00:17:52,510 --> 00:17:53,880
Simplemente no me pongo en el registro de entrada.

401
00:17:53,880 --> 00:17:57,380
Y así, si me quedo Debug-- configuro
mi punto de ruptura a la derecha allí.

402
00:17:57,380 --> 00:17:58,055
Corro de depuración.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> OK.

405
00:18:16,550 --> 00:18:17,050
Sí.

406
00:18:17,050 --> 00:18:20,350
Así que en realidad, el BGF se suponía
me han dicho que hay

407
00:18:20,350 --> 00:18:22,300
Fue un fallo de segmentación allí.

408
00:18:22,300 --> 00:18:24,883
No sé lo que estaba pasando
allí mismo, pero cuando me encontré con él,

409
00:18:24,883 --> 00:18:25,590
que estaba trabajando.

410
00:18:25,590 --> 00:18:29,410
Cuando se ejecuta a través de líneas de código y
BGF podría dejar de repente sobre ti,

411
00:18:29,410 --> 00:18:31,540
sube y mira lo que es el error rojo.

412
00:18:31,540 --> 00:18:33,930
Se lo diré, bueno,
tenido un fallo de segmentación,

413
00:18:33,930 --> 00:18:38,550
lo que significa que intentó acceder
espacio en una matriz que no existía.

414
00:18:38,550 --> 00:18:39,050
Sí.

415
00:18:39,050 --> 00:18:43,280
>> Así que en el siguiente problema
establezca esta semana, chicos

416
00:18:43,280 --> 00:18:45,600
probablemente tendrá una gran cantidad de
Variables flotando alrededor.

417
00:18:45,600 --> 00:18:48,560
Usted no va a estar seguro de lo que
todos ellos significan en un momento determinado.

418
00:18:48,560 --> 00:18:53,560
Así GDB realmente le ayudará a averiguar
lo que todos ellos están igualando

419
00:18:53,560 --> 00:18:55,940
y ser capaz de ver que visualmente.

420
00:18:55,940 --> 00:19:01,995
¿Hay alguien confundido sobre cómo
nada de eso estaba trabajando?

421
00:19:01,995 --> 00:19:02,495
Guay.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Correcto.

424
00:19:10,620 --> 00:19:14,260
Así que después de eso, estamos
ir a bucear en derecho

425
00:19:14,260 --> 00:19:17,562
en son cuatro diferentes
tipos de clases para esta semana.

426
00:19:17,562 --> 00:19:19,520
¿Cuántos de ustedes, primero
sobre todo, antes de empezar,

427
00:19:19,520 --> 00:19:23,020
han leído toda la especificación para pset3?

428
00:19:23,020 --> 00:19:23,824
OK.

429
00:19:23,824 --> 00:19:24,740
Estoy orgulloso de ustedes.

430
00:19:24,740 --> 00:19:29,110
Eso es como la mitad de la clase, que
es significativamente más que la última vez.

431
00:19:29,110 --> 00:19:33,950
>> Así que eso es genial, porque cuando
hablamos sobre el contenido

432
00:19:33,950 --> 00:19:36,170
en lecture-- o lo siento,
en sección- me gusta

433
00:19:36,170 --> 00:19:38,210
relacionar mucho de eso
de nuevo a lo que el conjunto de procesadores es

434
00:19:38,210 --> 00:19:40,210
y cómo desea
implementar eso en su conjunto de procesadores.

435
00:19:40,210 --> 00:19:42,400
Así que si usted viene teniendo
leer la especificación, que va a

436
00:19:42,400 --> 00:19:45,510
ser mucho más fácil para que usted entienda
lo que estoy hablando cuando digo,

437
00:19:45,510 --> 00:19:48,720
oh bueno, esto podría ser una realidad
buen lugar para poner en práctica este tipo.

438
00:19:48,720 --> 00:19:52,870
Así que aquellos de ustedes que han leído el
spec saber que, como parte de su conjunto de procesadores,

439
00:19:52,870 --> 00:19:54,900
usted va a tener que
escribir un tipo de especie.

440
00:19:54,900 --> 00:19:58,670
Así que esto puede ser muy útil
para muchos de ustedes hoy.

441
00:19:58,670 --> 00:20:01,760
>> Así que vamos a empezar con,
en esencia, el tipo más sencillo

442
00:20:01,760 --> 00:20:04,580
de género, la ordenación por selección.

443
00:20:04,580 --> 00:20:06,800
El algoritmo típico para
cómo nos gustaría ir sobre esto

444
00:20:06,800 --> 00:20:10,460
es-- David pasó por estos todos en
conferencia, así que voy a pasar rápidamente a lo largo

445
00:20:10,460 --> 00:20:13,900
aquí-- es esencialmente, que
tener una matriz de valores.

446
00:20:13,900 --> 00:20:17,170
Y luego encontrar el
menor valor sin clasificar

447
00:20:17,170 --> 00:20:20,200
y cambias ese valor con
el primer valor sin clasificar.

448
00:20:20,200 --> 00:20:22,700
Y luego te quedas con la repetición
con el resto de su lista.

449
00:20:22,700 --> 00:20:25,740
>> Y aquí está una explicación visual
de la forma en que iba a funcionar.

450
00:20:25,740 --> 00:20:30,460
Así, por ejemplo, si tuviéramos que empezar
con una serie de cinco elementos, el índice

451
00:20:30,460 --> 00:20:35,910
0 a 4, con 3, 5, 2, 6, y 4 valores
colocado en el array-- así que ahora,

452
00:20:35,910 --> 00:20:38,530
sólo vamos a asumir
que todos están sin clasificar

453
00:20:38,530 --> 00:20:41,130
porque no hemos probado lo contrario.

454
00:20:41,130 --> 00:20:44,130
>> Entonces, ¿cómo una selección tipo haría
el trabajo es que lo haría primero

455
00:20:44,130 --> 00:20:46,800
ejecutar a través de la totalidad
de la matriz sin clasificar.

456
00:20:46,800 --> 00:20:49,120
Sería seleccionar el valor más pequeño.

457
00:20:49,120 --> 00:20:51,750
En este caso, 3, a la derecha
Ahora, es el más pequeño.

458
00:20:51,750 --> 00:20:52,680
Se pone a 5.

459
00:20:52,680 --> 00:20:55,620
No, 5 no es mayor no sea:
o lo siento, no es inferior a: 3.

460
00:20:55,620 --> 00:20:57,779
Por lo tanto el valor mínimo es todavía 3.

461
00:20:57,779 --> 00:20:58,695
Y entonces se llega a 2.

462
00:20:58,695 --> 00:21:00,990
El equipo considera que, oh, 2 es inferior a 3.

463
00:21:00,990 --> 00:21:02,750
2 debe ser ahora el valor mínimo.

464
00:21:02,750 --> 00:21:06,630
Y así 2 swaps con ese primer valor.

465
00:21:06,630 --> 00:21:10,702
>> Así que después de una pasada, nosotros de hecho vemos
que el 2 y el 3 se intercambian.

466
00:21:10,702 --> 00:21:13,910
Y sólo vamos a seguir haciendo
esto de nuevo con el resto de la matriz.

467
00:21:13,910 --> 00:21:17,660
Así que vamos a simplemente ejecutar a través de
los últimos cuatro índices de la matriz.

468
00:21:17,660 --> 00:21:20,670
Veremos que 3 es
el siguiente valor mínimo.

469
00:21:20,670 --> 00:21:23,240
Así que vamos a cambiar eso con 4.

470
00:21:23,240 --> 00:21:26,900
Y entonces sólo vamos a mantener
que atraviesa hasta que, finalmente, se

471
00:21:26,900 --> 00:21:33,730
llegar a un arreglo ordenado en el que
2, 3, 4, 5, y 6 se todo Tipo.

472
00:21:33,730 --> 00:21:37,530
¿Todos entienden la lógica
de cómo funciona una selección especie?

473
00:21:37,530 --> 00:21:39,669
>> Sólo tienes algún tipo
de un valor mínimo.

474
00:21:39,669 --> 00:21:41,210
Estás hacer el seguimiento de lo que es.

475
00:21:41,210 --> 00:21:45,170
Y cada vez que lo encuentras, cambias lo
con el primer valor en el array--

476
00:21:45,170 --> 00:21:48,740
o bien, no es la primera value--
el siguiente valor en la matriz.

477
00:21:48,740 --> 00:21:50,150
Guay.

478
00:21:50,150 --> 00:21:55,460
>> Así como ustedes clase de
vio desde un breve vistazo,

479
00:21:55,460 --> 00:21:58,450
vamos a Pseudocódigo esto.

480
00:21:58,450 --> 00:22:02,510
Así que si ustedes en la parte posterior queréis
formar un grupo, todo el mundo en una mesa

481
00:22:02,510 --> 00:22:06,170
pueden formar un pequeño compañero, voy
para darle tipos como tres minutos

482
00:22:06,170 --> 00:22:08,190
simplemente hablar a través de
la lógica, en Inglés,

483
00:22:08,190 --> 00:22:14,161
de cómo podríamos ser capaces de implementar
pseudocódigo para escribir una ordenación por selección.

484
00:22:14,161 --> 00:22:14,910
Y hay dulces.

485
00:22:14,910 --> 00:22:16,118
Por favor venga y conseguir caramelos.

486
00:22:16,118 --> 00:22:19,520
Si estás en la parte de atrás y desea
dulces, puedo tirar caramelos a usted.

487
00:22:19,520 --> 00:22:22,850
En realidad, hacer fresco usted--.

488
00:22:22,850 --> 00:22:23,552
Oh, lo siento.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
OK.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Así que si nos gustaría, ya que
una clase, escribir pseudocódigo

493
00:25:27,140 --> 00:25:30,466
para cómo se podría acercarse
este problema, apenas siente libre.

494
00:25:30,466 --> 00:25:32,340
Iré a su alrededor y,
con el fin, pida grupos

495
00:25:32,340 --> 00:25:35,065
para la siguiente línea de
lo que deberíamos estar haciendo.

496
00:25:35,065 --> 00:25:37,840
Así que si ustedes quieren empezar
fuera, ¿qué es lo primero

497
00:25:37,840 --> 00:25:40,600
Qué hacer cuando usted está tratando de
poner en práctica una forma de resolver este programa

498
00:25:40,600 --> 00:25:43,480
para ordenar selectivamente una lista?

499
00:25:43,480 --> 00:25:46,349
Vamos a suponer que
tener una matriz, ¿de acuerdo?

500
00:25:46,349 --> 00:25:49,088
>> AUDIENCIA: ¿Quieres crear algunos
especie de [inaudible] que eres

501
00:25:49,088 --> 00:25:50,420
corriendo a través de toda su gama.

502
00:25:50,420 --> 00:25:51,128
>> ANDI Peng: Correcto.

503
00:25:51,128 --> 00:25:54,100
Así que vas a querer repetir
a través de cada espacio, ¿no?

504
00:25:54,100 --> 00:26:05,490
Tan estupendo.

505
00:26:05,490 --> 00:26:08,600
Si ustedes quieren que me diera el
junto line-- sí, en la parte posterior.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> AUDIENCIA: Échales
todo para los más pequeños.

508
00:26:13,290 --> 00:26:14,248
>> ANDI Peng: No vamos.

509
00:26:14,248 --> 00:26:17,438
Así que queremos ir a través y verifique
ver lo que el valor mínimo es, ¿verdad?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Voy a abreviar que a "min".

512
00:26:24,840 --> 00:26:27,658
¿Qué es lo que ustedes quieren hacer después
has encontrado el valor mínimo?

513
00:26:27,658 --> 00:26:28,533
>> AUDIENCIA: [inaudible]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI Peng: ¿Así que vas a querer
cambiar con el primero de esa serie,

516
00:26:33,150 --> 00:26:33,650
¿derecho?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
Ese es el principio, que voy a decir.

519
00:26:46,850 --> 00:26:47,220
Correcto.

520
00:26:47,220 --> 00:26:50,386
Así que ahora que ha cambiado el primero
uno, ¿qué es lo que quieres hacer después de eso?

521
00:26:50,386 --> 00:26:54,840
Así que ahora sabemos que este de aquí
debe ser el valor más pequeño, ¿no?

522
00:26:54,840 --> 00:26:58,310
Entonces usted tiene un descanso adicional
de la matriz que está sin clasificar.

523
00:26:58,310 --> 00:27:01,569
Así que lo que quiero hacer aquí, si
chicos quieren darme la siguiente línea?

524
00:27:01,569 --> 00:27:04,610
AUDIENCIA: Entonces quiere iterar
a través del resto de la matriz.

525
00:27:04,610 --> 00:27:05,276
ANDI Peng: Sí.

526
00:27:05,276 --> 00:27:09,857
Y así lo hace a través de la iteración
tipo de implicamos que probablemente necesitaremos?

527
00:27:09,857 --> 00:27:10,440
Que tipo de--

528
00:27:10,440 --> 00:27:12,057
>> AUDIENCIA: Oh, una variable adicional?

529
00:27:12,057 --> 00:27:13,890
ANDI Peng: Probablemente
otra para el bucle, ¿verdad?

530
00:27:13,890 --> 00:27:28,914
Así que probablemente vamos a querer
iterar through-- grande.

531
00:27:28,914 --> 00:27:31,830
Y luego vas a volver y
Probablemente comprobar el mínimo de nuevo,

532
00:27:31,830 --> 00:27:32,100
¿derecho?

533
00:27:32,100 --> 00:27:34,975
Y usted va a seguir repitiendo
esto, porque los bucles sólo va

534
00:27:34,975 --> 00:27:36,010
para seguir funcionando, ¿no?

535
00:27:36,010 --> 00:27:39,190
>> Así como ustedes pueden ver,
sólo tienen un pseudocódigo en general

536
00:27:39,190 --> 00:27:41,480
de cómo queremos que este programa se vea.

537
00:27:41,480 --> 00:27:46,646
Este reiterar aquí, ¿qué hacemos
normalmente necesitará escribir en nuestro código

538
00:27:46,646 --> 00:27:49,270
si queremos recorrer un
matriz, qué tipo de estructura?

539
00:27:49,270 --> 00:27:51,030
Creo que Christabel
ya se ha dicho antes.

540
00:27:51,030 --> 00:27:51,500
>> AUDIENCIA: Un bucle for.

541
00:27:51,500 --> 00:27:52,160
>> ANDI Peng: Un bucle for?

542
00:27:52,160 --> 00:27:52,770
Exactamente.

543
00:27:52,770 --> 00:27:56,060
Así que este es probablemente
Va a ser un bucle for.

544
00:27:56,060 --> 00:27:59,240
¿Qué es un cheque aquí va a entender?

545
00:27:59,240 --> 00:28:02,536
Normalmente, si desea comprobar
si algo es algo else--

546
00:28:02,536 --> 00:28:03,270
>> AUDIENCIA: Si.

547
00:28:03,270 --> 00:28:06,790
>> ANDI Peng: Un caso, ¿no?

548
00:28:06,790 --> 00:28:10,790
Y entonces el canje Aquí, vamos a
ir más tarde, porque David

549
00:28:10,790 --> 00:28:12,770
pasó por que en la conferencia también.

550
00:28:12,770 --> 00:28:14,580
Y entonces la segunda iteración implies--

551
00:28:14,580 --> 00:28:15,120
>> AUDIENCIA: Otra de bucle.

552
00:28:15,120 --> 00:28:16,745
>> ANDI Peng: --another bucle for, exactamente.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Así que si estamos buscando
en este correctamente,

555
00:28:22,000 --> 00:28:24,680
puede ver que estamos probablemente
va a necesitar un anidado bucle for

556
00:28:24,680 --> 00:28:28,330
con una sentencia condicional allí
y luego una verdadera pieza de código que es

557
00:28:28,330 --> 00:28:31,360
va a cambiar los valores.

558
00:28:31,360 --> 00:28:35,980
Así que en general, que he escrito
un código de pseudocódigo aquí.

559
00:28:35,980 --> 00:28:38,910
Y entonces estamos realmente va
físicamente, como una clase,

560
00:28:38,910 --> 00:28:40,700
tratar de aplicar esto hoy.

561
00:28:40,700 --> 00:28:42,486
Volvamos a este IDE.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> UH oh.

564
00:28:50,230 --> 00:28:51,754
¿Por qué es que no-- ahí está.

565
00:28:51,754 --> 00:28:52,253
OK.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Lo sentimos, pero voy a tratar de acercar un poco más.

568
00:28:57,500 --> 00:28:59,310
Allá vamos.

569
00:28:59,310 --> 00:29:05,060
Todo lo que estoy haciendo aquí es que he creado
un programa llamado "selección / sort.c."

570
00:29:05,060 --> 00:29:10,860
He creado una serie de nueve años
valores, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Actualmente, como pueda
ver, son desordenados.

572
00:29:14,370 --> 00:29:17,880
n va a ser el número que
le dice la cantidad de valores

573
00:29:17,880 --> 00:29:18,920
que tiene en su arsenal.

574
00:29:18,920 --> 00:29:20,670
En este caso, tenemos nueve valores.

575
00:29:20,670 --> 00:29:23,760
Y sólo tengo un bucle for aquí
que imprime la matriz sin clasificar.

576
00:29:23,760 --> 00:29:28,370
>> Y al final, yo también tengo una para
bucle que sólo imprime hacia fuera otra vez.

577
00:29:28,370 --> 00:29:32,070
Así que en teoría, si este programa
funciona correctamente, al final,

578
00:29:32,070 --> 00:29:35,670
debería ver un imprimen bucle for
en el que 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 son todo correctamente en orden.

580
00:29:39,310 --> 00:29:43,410
>> Así que tenemos nuestro pseudocódigo aquí.

581
00:29:43,410 --> 00:29:46,090
¿Alguien quiere a-- Sólo soy
va a ir pedir volunteers--

582
00:29:46,090 --> 00:29:49,540
dime exactamente qué escribir si
queremos, en primer lugar, simplemente iterar

583
00:29:49,540 --> 00:29:52,840
a través del principio de esta matriz?

584
00:29:52,840 --> 00:29:55,204
¿Cuál es la línea de código que soy
Probablemente va a necesitar aquí?

585
00:29:55,204 --> 00:29:56,990
>> AUDIENCIA: [inaudible]

586
00:29:56,990 --> 00:29:59,010
>> ANDI Peng: Sí, se siente
a-- siento libre, usted

587
00:29:59,010 --> 00:30:02,318
no tienen que soportar up-- sensación
libertad para levantar la voz un poco.

588
00:30:02,318 --> 00:30:08,190
>> AUDIENCIA: Para int i es igual 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI Peng: Sí, bueno.

590
00:30:10,690 --> 00:30:15,220
>> AUDIENCIA: i es menor que la longitud de la matriz.

591
00:30:15,220 --> 00:30:19,630
>> ANDI Peng: Así que tenga en
la mente aquí, porque nosotros

592
00:30:19,630 --> 00:30:23,060
no tienen una función que
nos dice la longitud de una matriz,

593
00:30:23,060 --> 00:30:25,790
ya tenemos una
valor que almacena eso.

594
00:30:25,790 --> 00:30:27,920
¿Correcto?

595
00:30:27,920 --> 00:30:31,010
Otra cosa a tener
en mente-- en una matriz

596
00:30:31,010 --> 00:30:33,940
de nueve valores, ¿cuáles son los índices?

597
00:30:33,940 --> 00:30:38,720
Digamos que esta matriz fue 0-3.

598
00:30:38,720 --> 00:30:41,500
Usted ve que el último
índice es en realidad 3.

599
00:30:41,500 --> 00:30:45,530
No es 4, a pesar de que hay
cuatro valores en la matriz.

600
00:30:45,530 --> 00:30:49,866
>> Así que aquí, tenemos que tener mucho cuidado
de lo que nuestra condición para la longitud

601
00:30:49,866 --> 00:30:50,490
va a ser.

602
00:30:50,490 --> 00:30:51,948
>> AUDIENCIA: ¿No sería n menos 1?

603
00:30:51,948 --> 00:30:54,440
ANDI Peng: Va
n menos 1, exactamente.

604
00:30:54,440 --> 00:30:57,379
¿Tiene sentido, ¿por qué
es n menos 1, todo el mundo?

605
00:30:57,379 --> 00:30:58,920
Es porque las matrices son indexados de cero.

606
00:30:58,920 --> 00:31:02,010
Empiezan a 0 y se ejecutan hasta n menos 1.

607
00:31:02,010 --> 00:31:03,210
Sí, es un poco complicado.

608
00:31:03,210 --> 00:31:03,730
OK.

609
00:31:03,730 --> 00:31:05,929
Y entonces--

610
00:31:05,929 --> 00:31:08,054
AUDIENCIA: Isnt'1 que
ya atendidos, sin embargo,

611
00:31:08,054 --> 00:31:11,400
por no decir "inferior o
igual a "y decir" menos? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI Peng: Esa es una
muy buena pregunta.

613
00:31:13,108 --> 00:31:13,630
Entonces sí.

614
00:31:13,630 --> 00:31:17,410
Pero también, la forma en que estamos
hacer efectivo el derecho de comprobar,

615
00:31:17,410 --> 00:31:19,120
es necesario comparar dos valores.

616
00:31:19,120 --> 00:31:21,009
Así que usted realmente quiere
salir de la "a" vacío.

617
00:31:21,009 --> 00:31:23,050
Porque si se compara
éste, no vas

618
00:31:23,050 --> 00:31:25,530
tener nada después
comparar, ¿no?

619
00:31:25,530 --> 00:31:27,460
Sí.

620
00:31:27,460 --> 00:31:29,297
Así que i ++.

621
00:31:29,297 --> 00:31:30,380
Vamos a añadir nuestros soportes en.

622
00:31:30,380 --> 00:31:30,880
¡Vaya.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Excelente.

625
00:31:34,710 --> 00:31:39,117
Así que tenemos el comienzo
de nuestro bucle exterior.

626
00:31:39,117 --> 00:31:41,450
Así que ahora que probablemente queremos
crear una variable para mantener

627
00:31:41,450 --> 00:31:43,085
pista del valor más pequeño, ¿no?

628
00:31:43,085 --> 00:31:45,751
¿Alguien quiere darme la
línea de código que haría eso?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
¿Qué necesitamos si vamos
querer almacenar algo?

631
00:31:53,570 --> 00:31:55,047
>> Correcto.

632
00:31:55,047 --> 00:31:57,630
Tal vez un mejor nombre para que
sería ser-- "temp" totalmente works--

633
00:31:57,630 --> 00:32:00,655
tal vez una más bien llamado sería,
si queremos que el value-- más pequeño

634
00:32:00,655 --> 00:32:01,624
>> AUDIENCIA: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI Peng: min, ahí vamos.

636
00:32:02,790 --> 00:32:05,230
min sería bueno.

637
00:32:05,230 --> 00:32:08,340
Y aquí, ¿qué hacemos
que inicializar a?

638
00:32:08,340 --> 00:32:09,620
Esto es un poco complicado.

639
00:32:09,620 --> 00:32:13,580
Debido a que en este momento en el
a partir de esta matriz,

640
00:32:13,580 --> 00:32:15,730
usted no ha mirado nada, ¿verdad?

641
00:32:15,730 --> 00:32:19,200
Entonces, ¿qué, de forma automática, si
estamos sólo en i es igual a 0,

642
00:32:19,200 --> 00:32:22,302
¿qué queremos para inicializar
nuestro primer valor mínimo de?

643
00:32:22,302 --> 00:32:22,802
AUDIENCIA: i.

644
00:32:22,802 --> 00:32:24,790
ANDI Peng: i, exactamente.

645
00:32:24,790 --> 00:32:27,040
Christabel, ¿por qué queremos
para inicializar a i?

646
00:32:27,040 --> 00:32:28,510
>> AUDIENCIA: Porque, bueno,
estamos empezando con 0.

647
00:32:28,510 --> 00:32:31,660
Así que porque no tenemos nada para comparar
a, el mínimo va a terminar siendo 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI Peng: Exactamente.

649
00:32:32,451 --> 00:32:34,400
Así que ella es exactamente correcto.

650
00:32:34,400 --> 00:32:36,780
Debido a que tenemos en realidad no
mirado nada todavía,

651
00:32:36,780 --> 00:32:38,680
no sabemos cuál es nuestro valor mínimo es.

652
00:32:38,680 --> 00:32:41,960
Queremos simplemente inicializar a
i, que, actualmente, es aquí.

653
00:32:41,960 --> 00:32:44,750
Y a medida que continuamos
bajar esta matriz,

654
00:32:44,750 --> 00:32:48,122
veremos que, con cada
pase adicional, i incrementos.

655
00:32:48,122 --> 00:32:49,830
Y así, en ese punto,
i probablemente va

656
00:32:49,830 --> 00:32:52,329
a querer ser el mínimo,
porque va a ser lo que sea

657
00:32:52,329 --> 00:32:54,520
es el principio de la matriz sin clasificar.

658
00:32:54,520 --> 00:32:55,270
Guay.

659
00:32:55,270 --> 00:32:58,720
>> Así que ahora queremos añadir
un bucle for aquí eso es

660
00:32:58,720 --> 00:33:03,225
va a recorrer el
sin clasificar, o el resto de esta serie.

661
00:33:03,225 --> 00:33:05,808
¿Alguien quiere darme un
línea de código que haría eso?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- ¿Qué necesitamos aquí abajo?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
¿Qué va a pasar en este bucle for?

666
00:33:18,820 --> 00:33:19,465
Sí.

667
00:33:19,465 --> 00:33:21,590
AUDIENCIA: Así que nos gustaría
tener un número entero diferente,

668
00:33:21,590 --> 00:33:25,080
porque nos estamos quedando por el resto
de la matriz en lugar de la i, así que tal vez

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> ANDI Peng: Sí, j suena bien para mí.

671
00:33:27,301 --> 00:33:27,850
Es igual?

672
00:33:27,850 --> 00:33:33,930
>> AUDIENCIA: Entonces sería i + 1, porque
estás empezando en el siguiente valor.

673
00:33:33,930 --> 00:33:40,395
Y luego a la end-- así que de nuevo, j es
menos de n menos 1, y luego j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI Peng: Grande.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> Y luego aquí, vamos a querer
para comprobar si se cumple nuestra condición,

677
00:33:52,750 --> 00:33:53,250
¿derecho?

678
00:33:53,250 --> 00:33:55,740
Porque quieres
cambiar el valor mínimo

679
00:33:55,740 --> 00:33:58,700
si en realidad es más pequeño que lo que
usted está comparando a, ¿verdad?

680
00:33:58,700 --> 00:34:01,146
Entonces, ¿qué vamos a querer en esta lista?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Compruebe.

683
00:34:04,897 --> 00:34:06,730
¿Qué tipo de declaración
estamos probablemente vamos

684
00:34:06,730 --> 00:34:08,389
ti desea utilizar si
que desee comprobar algo?

685
00:34:08,389 --> 00:34:09,360
>> AUDIENCIA: Una sentencia if.

686
00:34:09,360 --> 00:34:10,485
>> ANDI Peng: Una sentencia if.

687
00:34:10,485 --> 00:34:13,155
Así que si: y lo que va a ser
la condición que queremos en el interior

688
00:34:13,155 --> 00:34:13,988
de nuestra sentencia if?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> AUDIENCIA: Si el valor de j
es menor que el valor de i--

691
00:34:22,960 --> 00:34:24,600
>> ANDI Peng: Exactamente.

692
00:34:24,600 --> 00:34:27,480
Así que si: por lo que esta serie se llama "matriz".

693
00:34:27,480 --> 00:34:27,980
Excelente.

694
00:34:27,980 --> 00:34:30,465
Así que si array-- ¿qué fue eso?

695
00:34:30,465 --> 00:34:31,090
Repitelo.

696
00:34:31,090 --> 00:34:39,590
>> AUDIENCIA: Si array-j es menor que
matriz-i, entonces cambiaría el min.

697
00:34:39,590 --> 00:34:41,590
Así que el mínimo sería j.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI Peng: ¿Tiene sentido?

700
00:34:47,249 --> 00:34:48,670
OK.

701
00:34:48,670 --> 00:34:52,929
Y ahora aquí, en realidad
desee implementar el canje, ¿verdad?

702
00:34:52,929 --> 00:34:58,285
Así que recuerda, en la conferencia, que David, cuando
él estaba tratando de cambiar el-- lo que era

703
00:34:58,285 --> 00:34:59,996
jugo de naranja it-- y milk--

704
00:34:59,996 --> 00:35:01,150
>> AUDIENCIA: Eso era asqueroso.

705
00:35:01,150 --> 00:35:02,816
>> ANDI Peng: Sí, eso era un poco bruto.

706
00:35:02,816 --> 00:35:05,310
Pero fue una buena bonita
concepto de tiempo demostrando.

707
00:35:05,310 --> 00:35:08,430
Así que piensa en sus valores aquí.

708
00:35:08,430 --> 00:35:10,794
Tienes un array
de minutos, una gran variedad de i,

709
00:35:10,794 --> 00:35:12,460
o lo que estábamos tratando de cambiar aquí.

710
00:35:12,460 --> 00:35:15,310
Y es probable que no se puede verter en
entre sí, al mismo tiempo, ¿verdad?

711
00:35:15,310 --> 00:35:17,180
Así que, ¿qué vamos
a tener que crear aquí

712
00:35:17,180 --> 00:35:19,126
con el fin de intercambiar correctamente los valores?

713
00:35:19,126 --> 00:35:19,820
>> AUDIENCIA: Una variable temporal.

714
00:35:19,820 --> 00:35:21,370
>> ANDI Peng: Una variable temporal.

715
00:35:21,370 --> 00:35:22,570
Así que vamos a hacer int temp.

716
00:35:22,570 --> 00:35:25,681
Mira, esto sería una mejor
tiempo a-- Whoa, ¿qué fue eso?

717
00:35:25,681 --> 00:35:26,180
OK.

718
00:35:26,180 --> 00:35:29,800
Así que esto habría sido una mejor
tiempo para nombrar el "temp." variables

719
00:35:29,800 --> 00:35:30,730
Así que vamos a hacer int temp.

720
00:35:30,730 --> 00:35:32,563
¿Qué vamos a
set temp igual a aquí?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
AUDIENCIA: Min?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI Peng: Es un poco complicado.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
En realidad, no importa al final.

727
00:35:44,880 --> 00:35:47,690
No importa lo que
para que usted elija de cambiar de

728
00:35:47,690 --> 00:35:50,862
siempre y cuando usted está haciendo seguro de que eres
hacer el seguimiento de lo que estás intercambiando.

729
00:35:50,862 --> 00:35:52,250
>> AUDIENCIA: Podría ser array-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI Peng: Sí, vamos a hacer array-i.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
Y entonces ¿cuál es la siguiente línea
de código que queremos tener aquí?

733
00:35:59,305 --> 00:36:00,680
AUDIENCIA: array-i es igual array-j.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI Peng: Y por último?

736
00:36:08,070 --> 00:36:12,070
AUDIENCIA: array-j es igual array-i.

737
00:36:12,070 --> 00:36:14,525
AUDIENCIA: O array-j iguales
-array temp-- o, temp.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI Peng: OK.

740
00:36:19,430 --> 00:36:21,510
Así que vamos a ejecutar esto y ver
si se va a trabajar.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
¿Dónde está eso suceda?

743
00:36:39,335 --> 00:36:40,210
Oh, eso es un problema.

744
00:36:40,210 --> 00:36:44,320
Mira, en la línea 40, que estamos
tratando de usar matriz de j?

745
00:36:44,320 --> 00:36:47,022
Pero ¿de dónde j sólo existen en?

746
00:36:47,022 --> 00:36:48,402
>> AUDIENCIA: En el bucle for.

747
00:36:48,402 --> 00:36:49,110
ANDI Peng: Correcto.

748
00:36:49,110 --> 00:36:51,730
Entonces, ¿qué vamos a tener que hacer?

749
00:36:51,730 --> 00:36:53,170
>> AUDIENCIA: Definir fuera el--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
AUDIENCIA: Sí, supongo que tienes
utilizar otra sentencia if, ¿verdad?

752
00:37:00,610 --> 00:37:05,230
Así como, si el minimum--
bien, déjame pensar.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Chicos, tratar
para echar un vistazo de Let

755
00:37:09,990 --> 00:37:11,270
vemos, lo que es algo que podemos hacer aquí?

756
00:37:11,270 --> 00:37:11,811
>> AUDIENCIA: OK.

757
00:37:11,811 --> 00:37:15,900
Así que si el mínimo no es igual a
j-- por lo que si el mínimo es todavía yo--

758
00:37:15,900 --> 00:37:17,570
entonces no tendríamos que cambiar.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI Peng: ¿Eso igual i?

761
00:37:24,712 --> 00:37:25,920
¿Qué quiere decir aquí?

762
00:37:25,920 --> 00:37:30,494
>> AUDIENCIA: O sí, si el
mínimo no es igual a i, sí.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI Peng: OK.

765
00:37:40,210 --> 00:37:42,040
Bueno, eso resuelve, algo así, nuestros problemas.

766
00:37:42,040 --> 00:37:47,265
Pero eso todavía no resuelve el
problema de lo que sucede si j-- desde j

767
00:37:47,265 --> 00:37:49,890
no existe fuera de ella, lo que
Cómo se nos quiere hacer con él?

768
00:37:49,890 --> 00:37:50,698
Declarar fuera?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Vamos a tratar de ejecutar este.

771
00:38:02,730 --> 00:38:04,435
UH oh.

772
00:38:04,435 --> 00:38:06,200
Nuestra especie no está funcionando.

773
00:38:06,200 --> 00:38:10,060
>> Como se puede ver, nuestra inicial
matriz tenía esos valores.

774
00:38:10,060 --> 00:38:14,800
Y después que debería tener
estado en 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
No está funcionando.

776
00:38:15,530 --> 00:38:16,030
Ahh.

777
00:38:16,030 --> 00:38:17,184
¿Qué hacemos?

778
00:38:17,184 --> 00:38:17,850
AUDIENCIA: Depuración.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI Peng: Muy bien, podemos probar eso.

781
00:38:23,370 --> 00:38:25,030
Podemos depurar.

782
00:38:25,030 --> 00:38:26,042
Reducir un poco.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Vamos a poner nuestro punto de interrupción.

785
00:38:33,656 --> 00:38:37,280
Vamos como-- Aceptar.

786
00:38:37,280 --> 00:38:40,444
>> Así pues ya sabemos que
estas líneas, 15 a 22,

787
00:38:40,444 --> 00:38:43,610
se working-- porque todo lo que estoy haciendo es
simplemente iterar a través y printing--

788
00:38:43,610 --> 00:38:45,406
Puedo seguir adelante y saltar eso.

789
00:38:45,406 --> 00:38:47,280
Vamos a empezar en la línea 25.

790
00:38:47,280 --> 00:38:48,712
Oop, déjame deshacerme de eso.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> AUDIENCIA: Entonces el punto de interrupción
donde comienza la depuración?

793
00:38:54,057 --> 00:38:54,890
ANDI Peng: O paradas.

794
00:38:54,890 --> 00:38:55,670
AUDIENCIA: O paradas.

795
00:38:55,670 --> 00:38:55,930
ANDI Peng: Sí.

796
00:38:55,930 --> 00:38:58,640
Puede configurar varios puntos de interrupción y
sólo puede saltar de una a otra.

797
00:38:58,640 --> 00:39:01,590
Pero en este caso no sabemos
donde el error está sucediendo.

798
00:39:01,590 --> 00:39:03,780
Así que sólo queremos
empezar desde arriba hacia abajo.

799
00:39:03,780 --> 00:39:05,020
Sí.

800
00:39:05,020 --> 00:39:05,550
OK.

801
00:39:05,550 --> 00:39:08,460
>> Así que esta línea de aquí, podemos intervenir.

802
00:39:08,460 --> 00:39:11,499
Se puede ver aquí abajo,
tenemos una matriz.

803
00:39:11,499 --> 00:39:13,290
Esos son los valores
que se encuentran en la matriz.

804
00:39:13,290 --> 00:39:16,360
¿Ves eso, ¿cómo el índice 0, se
corresponde a la value-- oh,

805
00:39:16,360 --> 00:39:17,526
Voy a tratar de hacer un zoom.

806
00:39:17,526 --> 00:39:20,650
Lo sentimos, pero es muy difícil
a ver-- al índice de matriz 0,

807
00:39:20,650 --> 00:39:24,090
tenemos un valor de 4 y
a continuación, así sucesivamente y así sucesivamente.

808
00:39:24,090 --> 00:39:25,670
Tenemos nuestras variables locales.

809
00:39:25,670 --> 00:39:28,570
Ahora mismo i es igual a
0, lo que queremos que sea.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> Y así vamos a seguir paso a paso a través.

812
00:39:33,690 --> 00:39:36,850
Nuestra mínimo es igual a 0,
que también queremos que sea.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
Y entonces entramos en nuestro segundo para
lazo, si array-j es menor de gama-i,

815
00:39:45,560 --> 00:39:46,380
que no lo era.

816
00:39:46,380 --> 00:39:48,130
Así que ¿viste cómo
que omiten sobre eso?

817
00:39:48,130 --> 00:39:52,430
>> AUDIENCIA: Entonces, si el caso
mínimo, todo eso-- no debería que

818
00:39:52,430 --> 00:39:55,424
estar dentro de la primera bucle for?

819
00:39:55,424 --> 00:39:57,340
ANDI Peng: No, porque
usted todavía desea probar.

820
00:39:57,340 --> 00:40:00,329
¿Quieres hacer una comparación cada
tiempo, incluso después de ejecutar a través de él.

821
00:40:00,329 --> 00:40:02,620
Usted no sólo quiere hacerlo
en el primer paso.

822
00:40:02,620 --> 00:40:05,240
¿Quieres hacerlo con
cada pasada adicional de nuevo.

823
00:40:05,240 --> 00:40:07,198
¿Así que quieres comprobar
su condición interior.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Así que sólo vamos a
seguir corriendo por aquí.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Te voy a dar una pista chicos.

828
00:40:18,420 --> 00:40:23,910
Tiene que ver con el hecho de que cuando
usted está comprobando su condicional,

829
00:40:23,910 --> 00:40:26,600
usted no está comprobando
para el índice correcto.

830
00:40:26,600 --> 00:40:32,510
Así que ahora usted está comprobando
índice de matriz de j es menos de matriz

831
00:40:32,510 --> 00:40:33,970
Índice de i.

832
00:40:33,970 --> 00:40:36,580
Pero, ¿qué estás haciendo para arriba en
el principio del bucle for?

833
00:40:36,580 --> 00:40:38,260
¿No estás configurando j igual a i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Sí, por lo que puede en realidad
salir del depurador aquí.

836
00:40:45,415 --> 00:40:47,040
Así que echemos un vistazo a nuestra pseudocódigo.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
Para-- vamos a
comenzará a las i es igual a 0.

839
00:40:52,580 --> 00:40:54,760
Vamos a ir hasta n menos 1.

840
00:40:54,760 --> 00:40:58,040
Vamos a ver, qué tenemos ese derecho?

841
00:40:58,040 --> 00:40:59,580
Sí, eso era correcto.

842
00:40:59,580 --> 00:41:02,080
>> Así que aquí dentro, estamos
va a crear un valor mínimo

843
00:41:02,080 --> 00:41:03,630
y establecer que igual a i.

844
00:41:03,630 --> 00:41:04,950
¿Hicimos eso?

845
00:41:04,950 --> 00:41:06,270
Sí, lo hizo.

846
00:41:06,270 --> 00:41:10,430
Ahora en nuestro interior para bucle, estamos
va a hacer j es igual a i n menos 1.

847
00:41:10,430 --> 00:41:11,950
¿Hicimos eso?

848
00:41:11,950 --> 00:41:15,540
De hecho, lo hicimos.

849
00:41:15,540 --> 00:41:19,922
>> Así que, sin embargo, ¿qué estamos comparando aquí?

850
00:41:19,922 --> 00:41:20,925
>> AUDIENCIA: j más 1.

851
00:41:20,925 --> 00:41:21,716
ANDI Peng: Exactamente.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
Y entonces usted va a querer establecer
su mínima igual a j plus 1 también.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Así que me fui a través de esa realidad rápidamente.

856
00:41:32,640 --> 00:41:36,190
¿Entienden ustedes
por qué es j más 1?

857
00:41:36,190 --> 00:41:36,890
OK.

858
00:41:36,890 --> 00:41:40,700
>> Así que en su conjunto, en
el primer paso a través,

859
00:41:40,700 --> 00:41:44,850
el bucle for, por int
i es igual a 0, vamos a

860
00:41:44,850 --> 00:41:46,740
asume esto no se ha cambiado todavía.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Tenemos una gran variedad de, por completo,
sólo cuatro elementos no ordenados, ¿verdad?

863
00:41:56,760 --> 00:42:00,760
Así que queremos inicializar i igual a 0.

864
00:42:00,760 --> 00:42:03,650
Y me va a acaba
ejecutar este bucle.

865
00:42:03,650 --> 00:42:08,560
Y así, en la primera pasada, vamos
para inicializar una variable llamada "min"

866
00:42:08,560 --> 00:42:11,245
que también es igual a i, porque
no tenemos un valor mínimo.

867
00:42:11,245 --> 00:42:12,870
Así que esa es actualmente igual a 0 también.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
Y luego vamos a pasar.

870
00:42:17,640 --> 00:42:19,270
Y queremos repetir otra vez.

871
00:42:19,270 --> 00:42:22,900
Ahora que hemos encontrado lo que nuestro mínima
Es decir, queremos recorrer

872
00:42:22,900 --> 00:42:25,190
de nuevo para ver si se trata de comparar, ¿verdad?

873
00:42:25,190 --> 00:42:40,440
Así j, aquí, se va
a la igualdad de i, que es 0.

874
00:42:40,440 --> 00:42:46,320
Y luego, si arsenal j plus i, que
es el que está al lado otra vez, como menos

875
00:42:46,320 --> 00:42:49,270
de lo que su mínimo actual
valor es, que desea intercambiar.

876
00:42:49,270 --> 00:42:56,850
>> Así que vamos a decir que hemos
tiene, como, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
En este momento, i es igual a
0 y j es igual a 0.

878
00:43:01,610 --> 00:43:05,210
Y ese es nuestro valor mínimo.

879
00:43:05,210 --> 00:43:09,950
Si variedad j-plus yo-- por lo que si el
eso es después de la que estamos viendo

880
00:43:09,950 --> 00:43:13,450
es mayor que la anterior,
que va a convertirse en el mínimo.

881
00:43:13,450 --> 00:43:18,120
>> Así que aquí vemos que 5
no es menos que eso.

882
00:43:18,120 --> 00:43:19,730
Así que va a estar 5.

883
00:43:19,730 --> 00:43:23,580
Vemos que 1 es menor que 2, ¿verdad?

884
00:43:23,580 --> 00:43:32,970
Así que ahora que sabemos que nuestro mínimo es
va a ser el valor del índice en 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
¿Sí?

886
00:43:34,030 --> 00:43:39,170
Y luego cuando llegas aquí,
usted puede cambiar los valores correctos.

887
00:43:39,170 --> 00:43:42,610
>> Así que cuando ustedes simplemente tuvieron la j
antes, no estaban buscando en el

888
00:43:42,610 --> 00:43:43,260
después de.

889
00:43:43,260 --> 00:43:44,520
Estabas mirando
el mismo valor, el cual

890
00:43:44,520 --> 00:43:46,290
es por eso que no estaba haciendo nada.

891
00:43:46,290 --> 00:43:49,721
¿Eso tiene sentido para todos,
por eso necesitamos que más 1 allí?

892
00:43:49,721 --> 00:43:50,220
OK.

893
00:43:50,220 --> 00:43:53,345
Ahora vamos a ejecutar a través de él para hacer
Asegúrese de que el resto del código es correcto.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
¿Por qué es que eso suceda?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, es el mínimo aquí.

898
00:44:16,364 --> 00:44:17,780
Estábamos comparando el valor incorrecto.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Oh no.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Ah, sí, aquí estábamos
el canje de los valores erróneos también.

903
00:44:33,482 --> 00:44:34,940
Debido a que estábamos buscando en i y j.

904
00:44:34,940 --> 00:44:36,440
Esos son los que nos marchábamos.

905
00:44:36,440 --> 00:44:39,160
En realidad, queremos cambiar la
mínimo, el mínimo actual,

906
00:44:39,160 --> 00:44:40,550
con lo que el exterior es.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
Y como ustedes pueden ver abajo
aquí, tenemos un arreglo ordenado.

909
00:45:05,402 --> 00:45:07,110
Simplemente tenía que ver con
el hecho de que cuando

910
00:45:07,110 --> 00:45:09,350
nos íbamos el
valores que estábamos comparando,

911
00:45:09,350 --> 00:45:11,226
que no estábamos buscando en los valores correctos.

912
00:45:11,226 --> 00:45:13,850
Estábamos buscando en el mismo
aquí, en realidad no es el canje.

913
00:45:13,850 --> 00:45:17,135
Usted tiene que mirar el uno al lado
a él y luego se puede cambiar.

914
00:45:17,135 --> 00:45:19,260
Así que eso es lo que era una especie de
molestando nuestro código antes.

915
00:45:19,260 --> 00:45:22,460
Y lo que hice aquí lo es todo
el depurador podría haber hecho para ti

916
00:45:22,460 --> 00:45:23,810
Yo sólo lo hizo en el
tablero, porque es más fácil

917
00:45:23,810 --> 00:45:26,320
para ver en lugar de tratar
para acercar el depurador.

918
00:45:26,320 --> 00:45:29,391
¿Eso tiene sentido para todo el mundo?

919
00:45:29,391 --> 00:45:29,890
Guay.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Correcto.

922
00:45:35,410 --> 00:45:41,070
Podemos pasar a hablar de
notación asintótica, que

923
00:45:41,070 --> 00:45:44,580
es sólo una forma elegante de decir la
tiempos de ejecución de todos estos tipos.

924
00:45:44,580 --> 00:45:47,650
Así que sé David, en la conferencia,
referido a los tiempos de ejecución.

925
00:45:47,650 --> 00:45:52,124
Y se fue por toda la fórmula
de cómo calcular los tiempos de ejecución.

926
00:45:52,124 --> 00:45:53,040
No te preocupes por eso.

927
00:45:53,040 --> 00:45:54,660
Si usted es realmente curioso
sobre cómo funciona,

928
00:45:54,660 --> 00:45:55,810
no dude en hablar conmigo después de la sección.

929
00:45:55,810 --> 00:45:57,560
Podemos caminar a través de
las fórmulas juntos.

930
00:45:57,560 --> 00:46:00,689
Pero todos ustedes tienen para realmente
saber es que n al cuadrado más de 2

931
00:46:00,689 --> 00:46:01,980
es lo mismo que n al cuadrado.

932
00:46:01,980 --> 00:46:04,710
Debido a que el número más grande,
el exponente, más crece.

933
00:46:04,710 --> 00:46:06,590
Y así, para nuestros propósitos,
todos nos preocupamos por

934
00:46:06,590 --> 00:46:09,470
es ese número gigante que está creciendo.

935
00:46:09,470 --> 00:46:13,340
>> Entonces, ¿cuál es el mejor de los casos
tiempo de ejecución de la ordenación por selección?

936
00:46:13,340 --> 00:46:15,830
Si usted va a tener
para recorrer una lista

937
00:46:15,830 --> 00:46:18,712
y luego recorrer
el resto de la lista,

938
00:46:18,712 --> 00:46:20,420
¿cuántas veces se
usted va a probablemente,

939
00:46:20,420 --> 00:46:24,612
en el peor de caso-- en el
mejor de los casos, sorry-- ejecutar a través de?

940
00:46:24,612 --> 00:46:27,070
Tal vez la mejor pregunta es
preguntar, ¿cuál es el peor de los casos

941
00:46:27,070 --> 00:46:28,153
tiempo de ejecución de la ordenación por selección.

942
00:46:28,153 --> 00:46:29,366
AUDIENCIA: n al cuadrado.

943
00:46:29,366 --> 00:46:30,740
ANDI Peng: Ha n al cuadrado, derecha.

944
00:46:30,740 --> 00:46:36,986
Así que una manera fácil de pensar en esto es como,
cualquier momento tienes dos anidado para los bucles,

945
00:46:36,986 --> 00:46:38,110
que va a ser n al cuadrado.

946
00:46:38,110 --> 00:46:40,386
Porque no sólo es usted
corriendo a través una vez más,

947
00:46:40,386 --> 00:46:42,260
usted tiene que volver
vuelta y correr a través de él

948
00:46:42,260 --> 00:46:44,980
una vez en el interior de cada valor.

949
00:46:44,980 --> 00:46:48,640
Así que en ese caso, se está ejecutando n
tiempos n al cuadrado, que éstos: lo siento,

950
00:46:48,640 --> 00:46:50,505
n veces n, que es igual a n al cuadrado.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Y especie es también un poco
único en el sentido

953
00:46:56,360 --> 00:46:59,774
que no importa si éstos
valores ya están en orden.

954
00:46:59,774 --> 00:47:01,440
Todavía va a ejecutar a través de todos modos.

955
00:47:01,440 --> 00:47:03,872
Digamos que este fue de 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Independientemente de si era o no en
fin, todavía habría corrió a través de

957
00:47:07,080 --> 00:47:08,620
y todavía comprobado el valor mínimo.

958
00:47:08,620 --> 00:47:10,100
Habría hecho el
mismo número de cheques

959
00:47:10,100 --> 00:47:12,780
cada vez, incluso si
en realidad no tocar nada.

960
00:47:12,780 --> 00:47:16,940
>> Así pues, en tal caso, el mejor y el peor
tiempos de ejecución son en realidad equivalentes.

961
00:47:16,940 --> 00:47:19,160
Así que el tiempo de ejecución esperado
de ordenación por selección,

962
00:47:19,160 --> 00:47:23,790
que designamos por el símbolo
de theta, theta, en este caso,

963
00:47:23,790 --> 00:47:24,790
también sería n al cuadrado.

964
00:47:24,790 --> 00:47:26,480
Los tres de ellos serían n al cuadrado.

965
00:47:26,480 --> 00:47:29,653
Está claro por qué todo el mundo
la duración es n al cuadrado?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Correcto.

968
00:47:33,980 --> 00:47:39,120
Así que sólo voy a correr rápidamente
por el resto de los géneros.

969
00:47:39,120 --> 00:47:41,137
El algoritmo para
burbuja sort-- recuerde,

970
00:47:41,137 --> 00:47:43,220
esta fue la primera
David se acercó en la conferencia.

971
00:47:43,220 --> 00:47:46,000
Esencialmente, usted camina
a través de la lista entera

972
00:47:46,000 --> 00:47:48,950
y que acaba de swap--
comparar los dos a la vez.

973
00:47:48,950 --> 00:47:51,350
Y si uno es mayor,
lo que sólo les intercambiar.

974
00:47:51,350 --> 00:47:53,590
Así que si éstos son mayores, que cambiaría.

975
00:47:53,590 --> 00:47:56,180
Tengo oficial aquí.

976
00:47:56,180 --> 00:47:59,100
>> Así que vamos a decir que tenía 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Se podría comparar el 8 y un 6.

978
00:48:00,571 --> 00:48:01,570
Usted necesitaría para intercambiarlas.

979
00:48:01,570 --> 00:48:02,610
Se podría comparar el 8 y un 4.

980
00:48:02,610 --> 00:48:03,609
Usted necesitaría para intercambiarlas.

981
00:48:03,609 --> 00:48:07,000
Si tiene que cambiar el 8 y
el 2, cambie ellos también.

982
00:48:07,000 --> 00:48:10,760
Así pues, en tal sentido, se puede ver,
jugado a cabo durante un largo período de tiempo,

983
00:48:10,760 --> 00:48:13,730
cómo los valores de tipo de burbuja
los extremos, lo cual es por eso que lo llaman

984
00:48:13,730 --> 00:48:15,320
ordenamiento de burbuja.

985
00:48:15,320 --> 00:48:19,950
>> Nos gustaría simplemente ejecutar a través de nuevo en
nuestra segunda pasada, y nuestro tercer paso,

986
00:48:19,950 --> 00:48:21,150
y nuestro cuarto pase.

987
00:48:21,150 --> 00:48:25,820
Esencialmente, burbuja especie sólo se ejecuta
hasta que no haga más swaps.

988
00:48:25,820 --> 00:48:31,109
Así que en ese sentido, esto es sólo
el pseudocódigo general para ello.

989
00:48:31,109 --> 00:48:32,650
No se preocupe, éstos serán todos en línea.

990
00:48:32,650 --> 00:48:34,990
No tenemos que ir realmente sobre esto.

991
00:48:34,990 --> 00:48:38,134
>> Acabamos inicializamos un contador
variable que comienza en 0.

992
00:48:38,134 --> 00:48:39,800
Y recorrer toda la matriz.

993
00:48:39,800 --> 00:48:43,420
Y si un valor es-- si esto
valor es mayor que ese valor,

994
00:48:43,420 --> 00:48:44,610
vas para intercambiarlas.

995
00:48:44,610 --> 00:48:46,860
Y entonces no eres más que
va a seguir adelante.

996
00:48:46,860 --> 00:48:47,970
Y vas a contar.

997
00:48:47,970 --> 00:48:50,845
Y sólo vamos a seguir haciendo
esto mientras que el contador es mayor

998
00:48:50,845 --> 00:48:53,345
que 0, lo que significa que
cada vez que tiene que cambiar,

999
00:48:53,345 --> 00:48:55,220
usted sabe que quiere ir
espalda y puedes volver a intentarlo.

1000
00:48:55,220 --> 00:48:59,510
Usted quiere mantener la comprobación hasta que usted sepa
que usted no tiene que cambiar ya.

1001
00:48:59,510 --> 00:49:05,570
>> Entonces, ¿qué son los mejores y peores
caso los motores de ejecución de ordenamiento de burbuja?

1002
00:49:05,570 --> 00:49:09,300
Y hint-- esto es realmente diferente
desde la selección del tipo en el sentido

1003
00:49:09,300 --> 00:49:11,810
que estas dos respuestas no son iguales.

1004
00:49:11,810 --> 00:49:14,709
Piense en lo que sucedería en
un caso si ya se solucionó.

1005
00:49:14,709 --> 00:49:16,500
Y pensar en lo
Qué pasaría si fuera

1006
00:49:16,500 --> 00:49:18,372
en el caso en el que no se solucionó.

1007
00:49:18,372 --> 00:49:20,580
Y usted puede clase de correr
a través de por qué está sucediendo.

1008
00:49:20,580 --> 00:49:22,954
Te voy a dar los chicos, como, 30
segundo para pensar en eso.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> OK.

1011
00:49:53,540 --> 00:49:57,462
¿Alguien tiene una pista sobre lo que el
peor de los casos el tiempo de ejecución de la burbuja de tipo es?

1012
00:49:57,462 --> 00:49:57,962
Sí.

1013
00:49:57,962 --> 00:50:07,810
>> AUDIENCIA: ¿Sería, como, n veces
n menos 1 o algo así?

1014
00:50:07,810 --> 00:50:10,650
Al igual que, cada vez que se ejecuta,
es sólo, como, uno de intercambio menos

1015
00:50:10,650 --> 00:50:10,960
que todo lo que era.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI Peng: Sí, así
usted es del todo acertada.

1017
00:50:12,668 --> 00:50:15,940
Y este es un caso en el que el
respuesta era en realidad más compleja

1018
00:50:15,940 --> 00:50:17,240
que el que tenemos que dar.

1019
00:50:17,240 --> 00:50:19,772
Así que va a run-- estoy
va a borrar todo esto aquí.

1020
00:50:19,772 --> 00:50:20,480
¿Es bueno todo el mundo?

1021
00:50:20,480 --> 00:50:21,869
¿Puedo borrar esto?

1022
00:50:21,869 --> 00:50:22,368
OK.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Usted va a ejecutar a través de n
veces la primera vez, ¿verdad?

1025
00:50:30,320 --> 00:50:33,200
Y ellos van a ejecutar a través de
n menos 1 la segunda vez, ¿verdad?

1026
00:50:33,200 --> 00:50:37,130
Y luego vas a mantener
va, n mina 2, etcétera.

1027
00:50:37,130 --> 00:50:40,210
David hizo esto en una conferencia, en el que,
si se ha añadido a todos esos valores,

1028
00:50:40,210 --> 00:50:48,080
usted consigue algo que es como-- yeah--
más de 2, lo que reduce esencialmente sólo

1029
00:50:48,080 --> 00:50:49,784
hacia abajo para n al cuadrado.

1030
00:50:49,784 --> 00:50:51,700
Usted va a obtener una
fracción raro ahí.

1031
00:50:51,700 --> 00:50:53,892
Y así, sólo sé que
el n al cuadrado siempre

1032
00:50:53,892 --> 00:50:55,350
tiene prioridad sobre la fracción.

1033
00:50:55,350 --> 00:50:58,450
Y así, en este caso, lo peor
tiempo de ejecución sería n al cuadrado.

1034
00:50:58,450 --> 00:51:00,210
Si fue en descenso
orden, creo, que

1035
00:51:00,210 --> 00:51:02,530
tener que hacer un intercambio cada vez.

1036
00:51:02,530 --> 00:51:05,170
>> ¿Cuál sería, potencialmente,
el mejor tiempo de ejecución caso?

1037
00:51:05,170 --> 00:51:08,580
Digamos, si la lista ya estaba
con el fin, ¿cuál sería el tiempo de ejecución?

1038
00:51:08,580 --> 00:51:09,565
>> AUDIENCIA: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI Peng: Es n, exactamente.

1040
00:51:10,690 --> 00:51:11,600
Y ¿por qué es n?

1041
00:51:11,600 --> 00:51:13,850
AUDIENCIA: Debido a que usted acaba de
tendrá que comprobar en cada vez.

1042
00:51:13,850 --> 00:51:14,770
ANDI Peng: Exactamente.

1043
00:51:14,770 --> 00:51:17,150
Así pues, en la mejor ejecución posible,
si esta lista ya estaba

1044
00:51:17,150 --> 00:51:20,270
sorted-- digamos 1, 2, 3, 4-- usted
acaba de pasar, que le echa,

1045
00:51:20,270 --> 00:51:21,720
verías, oh, todos ellos resultan.

1046
00:51:21,720 --> 00:51:22,636
Yo no tenía que cambiar.

1047
00:51:22,636 --> 00:51:23,370
He terminado.

1048
00:51:23,370 --> 00:51:26,500
Así que en ese caso, es sólo n
o el número de pasos que acaba de

1049
00:51:26,500 --> 00:51:29,870
tuvo que comprobar en la primera lista.

1050
00:51:29,870 --> 00:51:33,990
>> Y después, ahora golpeamos
ordenación por inserción, donde

1051
00:51:33,990 --> 00:51:39,260
el algoritmo es esencialmente divide
en una parte ordenada y sin clasificar.

1052
00:51:39,260 --> 00:51:42,810
Y entonces uno por uno,
los valores no clasificados son

1053
00:51:42,810 --> 00:51:46,880
insertado en su apropiada
posiciones en el principio de la lista.

1054
00:51:46,880 --> 00:51:52,120
>> Así, por ejemplo, tenemos una
Lista de 3, 5, 2, 6, 4 de nuevo.

1055
00:51:52,120 --> 00:51:54,750
Sabemos que es actualmente
sin clasificar porque acabamos de

1056
00:51:54,750 --> 00:51:57,030
comenzado mirarlo.

1057
00:51:57,030 --> 00:52:00,610
Echamos un vistazo y sabemos que
el primer valor se ordena, ¿verdad?

1058
00:52:00,610 --> 00:52:04,190
Si sólo está buscando en una serie de
tamaño de uno, usted sabe que está ordenada.

1059
00:52:04,190 --> 00:52:08,230
>> Así que sabemos que el
otros cuatro son sin clasificar.

1060
00:52:08,230 --> 00:52:10,980
Vamos a través y vemos ese valor.

1061
00:52:10,980 --> 00:52:11,730
Volvamos.

1062
00:52:11,730 --> 00:52:13,130
Ver que el valor de 5?

1063
00:52:13,130 --> 00:52:14,110
Echamos un vistazo.

1064
00:52:14,110 --> 00:52:15,204
Comparamos a 3.

1065
00:52:15,204 --> 00:52:17,870
Sabemos que es mayor que
3, por lo que sabemos que eso está solucionado.

1066
00:52:17,870 --> 00:52:22,940
Así que ahora sabemos que los dos primeros
se ordenan y los tres últimos no lo son.

1067
00:52:22,940 --> 00:52:24,270
>> Echamos un vistazo a 2.

1068
00:52:24,270 --> 00:52:25,720
En primer lugar, comprobamos con 5.

1069
00:52:25,720 --> 00:52:26,700
¿Es menor que 5?

1070
00:52:26,700 --> 00:52:27,240
No lo es.

1071
00:52:27,240 --> 00:52:29,510
Así que tenemos que seguir mirando hacia abajo.

1072
00:52:29,510 --> 00:52:30,940
Luego de comprobar 2 de 3.

1073
00:52:30,940 --> 00:52:31,850
¿Es menor que?

1074
00:52:31,850 --> 00:52:32,350
No.

1075
00:52:32,350 --> 00:52:35,430
Así que ya sabes un 2 tiene que ser insertado
en la parte delantera y 3 y 5

1076
00:52:35,430 --> 00:52:38,200
ambos tienen que ser expulsados.

1077
00:52:38,200 --> 00:52:42,190
Haga esto de nuevo con 6 y 4.

1078
00:52:42,190 --> 00:52:48,962
Y nosotros sólo seguimos comprobando en esencia,
donde acabamos de comprobar, verificar, comprobar.

1079
00:52:48,962 --> 00:52:51,170
Y hasta que esté en la derecha
posición, tipo de solo

1080
00:52:51,170 --> 00:52:54,890
insertarlo en la posición correcta,
que es donde el nombre del vino.

1081
00:52:54,890 --> 00:52:59,830
>> Así que eso es sólo el algoritmo,
pseudocódigo per se, una especie de,

1082
00:52:59,830 --> 00:53:04,990
sobre cómo íbamos a poner en práctica
un tipo de inserción.

1083
00:53:04,990 --> 00:53:05,954
Pseudocódigo está aquí.

1084
00:53:05,954 --> 00:53:06,620
Todo está en línea.

1085
00:53:06,620 --> 00:53:10,720
No se preocupe si ustedes son
tratando de copiar esto.

1086
00:53:10,720 --> 00:53:14,500
Así que una vez más, lo mismo pregunta--
sería el mejor y el peor de los tiempos de ejecución

1087
00:53:14,500 --> 00:53:16,120
para la ordenación por inserción?

1088
00:53:16,120 --> 00:53:17,750
Es muy similar a la última pregunta.

1089
00:53:17,750 --> 00:53:20,479
Te voy a dar los chicos, como, 30
segundo para pensar en esto también.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK ¿Alguien quiere
dame el peor tiempo de ejecución?

1092
00:53:50,071 --> 00:53:50,570
Sí.

1093
00:53:50,570 --> 00:53:51,490
>> AUDIENCIA: n al cuadrado.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI Peng: Ha n al cuadrado.

1095
00:53:52,573 --> 00:53:53,730
Y ¿por qué es n al cuadrado?

1096
00:53:53,730 --> 00:53:57,562
>> AUDIENCIA: Porque en
orden inverso, usted tiene

1097
00:53:57,562 --> 00:54:02,619
que pasar por n veces n, de que éstos:

1098
00:54:02,619 --> 00:54:03,660
ANDI Peng: Sí, exactamente.

1099
00:54:03,660 --> 00:54:06,610
Así mismo que en el ordenamiento de burbuja.

1100
00:54:06,610 --> 00:54:08,720
Si esta lista está en
orden descendente, eres

1101
00:54:08,720 --> 00:54:11,240
va a tener que comprobar primero una vez.

1102
00:54:11,240 --> 00:54:13,470
Y a continuación, con cada
valor adicional, usted es

1103
00:54:13,470 --> 00:54:16,390
va a tener que comprobar que en contra
cada valor único, ¿no?

1104
00:54:16,390 --> 00:54:20,290
Y así, en conjunto, que vas a hacer
un momento n pasar a otro n pasan, que

1105
00:54:20,290 --> 00:54:21,750
está n al cuadrado.

1106
00:54:21,750 --> 00:54:22,860
¿Y el mejor de los casos?

1107
00:54:22,860 --> 00:54:24,360
Sí.

1108
00:54:24,360 --> 00:54:28,840
>> AUDIENCIA: n menos 1, ya que el
primero ya se eleva al cuadrado.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI Peng: Así, cerca.

1110
00:54:30,270 --> 00:54:31,850
La respuesta es en realidad n.

1111
00:54:31,850 --> 00:54:37,189
Porque si bien la primera es
ordenados, puede que no se actually--

1112
00:54:37,189 --> 00:54:38,980
sólo tuvimos suerte, en
ese ejemplo, que 2

1113
00:54:38,980 --> 00:54:40,930
pasó a ser el número más pequeño.

1114
00:54:40,930 --> 00:54:43,680
Pero eso no siempre será el caso.

1115
00:54:43,680 --> 00:54:48,040
Si 2 ya está ordenado en un principio
pero te ves y hay un 1 aquí,

1116
00:54:48,040 --> 00:54:49,144
el 1 va a topar.

1117
00:54:49,144 --> 00:54:51,060
Y que va a terminar
siendo golpeado de todos modos.

1118
00:54:51,060 --> 00:54:56,250
>> Así que en el mejor de los casos,
en realidad es sólo va a ser n.

1119
00:54:56,250 --> 00:54:59,090
Si usted tiene 1, 2, 3,
4, 5, 6, 7, 8, eres

1120
00:54:59,090 --> 00:55:00,940
va a ejecutar a través de
esa lista toda vez

1121
00:55:00,940 --> 00:55:03,430
comprobar para ver si todo está bien.

1122
00:55:03,430 --> 00:55:07,390
Están todos claro en funcionamiento
tiempos de la selección así?

1123
00:55:07,390 --> 00:55:09,960
Sé que estoy pasando
estos realmente rápido.

1124
00:55:09,960 --> 00:55:13,330
Pero sólo sé que si se conoce el
conceptos generales, debe ser bueno.

1125
00:55:13,330 --> 00:55:16,070
OK.

1126
00:55:16,070 --> 00:55:19,790
Así que sólo te daré chicos tal vez, como,
un minuto para hablar con sus vecinos

1127
00:55:19,790 --> 00:55:21,890
en lo que son sólo algunas
de las principales diferencias

1128
00:55:21,890 --> 00:55:23,540
entre estos tipos de clases.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Vamos a repasar que pronto.

1131
00:56:25,570 --> 00:56:26,444
AUDIENCIA: ¡Oh, OK.

1132
00:56:26,444 --> 00:56:27,320
ANDI Peng: Sí.

1133
00:56:27,320 --> 00:56:28,380
OK.

1134
00:56:28,380 --> 00:56:33,420
Fresco, vamos nuevamente las como clase.

1135
00:56:33,420 --> 00:56:34,330
OK.

1136
00:56:34,330 --> 00:56:37,579
Así que esto era una especie de
pregunta abierta en el sentido

1137
00:56:37,579 --> 00:56:39,120
que hay un montón de respuestas a ellos.

1138
00:56:39,120 --> 00:56:40,746
Y vamos a repasar algunos de ellos brevemente.

1139
00:56:40,746 --> 00:56:43,411
Yo sólo quería conseguir que los chicos
pensando en lo diferenciado

1140
00:56:43,411 --> 00:56:44,530
los tres tipos de clases.

1141
00:56:44,530 --> 00:56:47,440
Y oí, también, una gran
pregunta-- ¿qué ordenamiento por mezcla hacer?

1142
00:56:47,440 --> 00:56:50,110
Muy buena pregunta, porque eso es
lo que estamos cubriendo siguiente.

1143
00:56:50,110 --> 00:56:52,850
>> Así ordenamiento por mezcla es la
un tipo que funciona

1144
00:56:52,850 --> 00:56:56,100
muy diferente a los otros tipos.

1145
00:56:56,100 --> 00:56:58,180
Como ustedes pueden ver--
hizo David esa demo

1146
00:56:58,180 --> 00:57:01,130
donde tenía todo el fresco
ruidos de ver cómo se fusionan

1147
00:57:01,130 --> 00:57:04,010
especie corrió, como, infinitamente
más rápido que los otros dos tipos?

1148
00:57:04,010 --> 00:57:04,510
OK.

1149
00:57:04,510 --> 00:57:07,580
Así que eso es debido a la fusión
clase implementa esa brecha

1150
00:57:07,580 --> 00:57:11,020
y conquistar el concepto que hemos
hablado mucho en conferencia.

1151
00:57:11,020 --> 00:57:14,550
En ese sentido que nos gusta trabajar
más inteligente, no más difícil, cuando se divide

1152
00:57:14,550 --> 00:57:18,120
y conquistar problemas, y romperlos
abajo, y luego ponerlos juntos,

1153
00:57:18,120 --> 00:57:19,930
buenas cosas siempre suceden.

1154
00:57:19,930 --> 00:57:21,960
>> Así que la forma en que se fusionan
trabaja especie esencialmente

1155
00:57:21,960 --> 00:57:24,660
es que se divide una
array sin ordenar a la mitad.

1156
00:57:24,660 --> 00:57:26,500
Y entonces tiene dos mitades de matrices.

1157
00:57:26,500 --> 00:57:28,220
Y simplemente ordena esas dos mitades.

1158
00:57:28,220 --> 00:57:31,750
Simplemente sigue dividiendo a la mitad, en
media, en medio hasta que todo se ordena

1159
00:57:31,750 --> 00:57:33,680
y luego recursivamente
pone todo junto.

1160
00:57:33,680 --> 00:57:36,550
>> Así que eso es muy abstracto.

1161
00:57:36,550 --> 00:57:38,750
Así que esto es sólo un poco de pseudocódigo.

1162
00:57:38,750 --> 00:57:41,040
¿Eso tiene sentido en
la forma en que se está ejecutando?

1163
00:57:41,040 --> 00:57:43,870
Así que digamos que usted tiene una
arreglo de n elementos, ¿verdad?

1164
00:57:43,870 --> 00:57:45,450
Si n es menor que 2, puede volver.

1165
00:57:45,450 --> 00:57:49,040
Porque usted sabe que si hay
sólo una cosa, debe ser ordenada.

1166
00:57:49,040 --> 00:57:52,600
Si no, se ordena la mitad izquierda,
y luego ordenar la mitad derecha,

1167
00:57:52,600 --> 00:57:54,140
y luego combinar.

1168
00:57:54,140 --> 00:57:56,979
>> Así, mientras que se ve muy fácil,
en la realidad, pensando en que es

1169
00:57:56,979 --> 00:58:00,270
un poco difícil. Porque usted es como,
bueno, eso es algo que se ejecuta en sí mismo.

1170
00:58:00,270 --> 00:58:00,769
¿Correcto?

1171
00:58:00,769 --> 00:58:02,430
Se ejecuta en sí mismo.

1172
00:58:02,430 --> 00:58:05,479
Así que en ese sentido, David tocó
sobre la recursividad en clase.

1173
00:58:05,479 --> 00:58:07,270
Y eso es un concepto
hablaremos más.

1174
00:58:07,270 --> 00:58:11,430
Es que esto, estas dos líneas
aquí, en realidad es sólo el programa

1175
00:58:11,430 --> 00:58:13,860
diciendo que se ejecute en sí
con diferente entrada.

1176
00:58:13,860 --> 00:58:17,230
Así que en lugar de correr en sí con
la totalidad de n elementos,

1177
00:58:17,230 --> 00:58:20,530
se puede descomponer en el
mitad izquierda y la mitad derecha

1178
00:58:20,530 --> 00:58:22,680
y luego ejecutarlo nuevamente.

1179
00:58:22,680 --> 00:58:26,050
>> Y luego vamos a ver visualmente,
porque soy un aprendiz visual.

1180
00:58:26,050 --> 00:58:27,270
Funciona mejor para mí.

1181
00:58:27,270 --> 00:58:29,890
Así que vamos a ver un ejemplo visual aquí.

1182
00:58:29,890 --> 00:58:36,237
>> Digamos que tenemos una matriz, de seis
elementos, 3, 5, 2, 6, 4, 1, no ordenados.

1183
00:58:36,237 --> 00:58:37,820
Muy bien, hay mucho en esta página.

1184
00:58:37,820 --> 00:58:43,179
Así que si ustedes pueden mirar el
primer paso aquí, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
se puede dividir por la mitad.

1186
00:58:44,220 --> 00:58:45,976
Usted tiene 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Usted sabe que estos aren't-- usted
no sé si están ordenados o no,

1188
00:58:48,850 --> 00:58:52,517
por lo que mantener su desglose, en medio,
en medio, en medio, hasta que finalmente,

1189
00:58:52,517 --> 00:58:53,600
sólo tiene un elemento.

1190
00:58:53,600 --> 00:58:56,790
Y un elemento siempre está ordenada, ¿verdad?

1191
00:58:56,790 --> 00:59:01,560
>> Así que sabemos que 3, 5, 2, 4, 6,
1, por sí mismos, son ordenados.

1192
00:59:01,560 --> 00:59:05,870
Y ahora podemos volver a ponerlos juntos.

1193
00:59:05,870 --> 00:59:07,510
Así sabemos que el 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Ponemos las juntas.

1195
00:59:08,510 --> 00:59:09,617
Sabemos que es ordenada.

1196
00:59:09,617 --> 00:59:10,450
Los 2 sigue allí.

1197
00:59:10,450 --> 00:59:11,830
Podemos poner el 4 y el 6 juntos.

1198
00:59:11,830 --> 00:59:13,996
Sabemos que eso se solucionó,
así que pusimos que juntos.

1199
00:59:13,996 --> 00:59:14,940
Y el 1 es allí.

1200
00:59:14,940 --> 00:59:18,720
>> Y entonces usted acaba de ver
estas dos mitades aquí.

1201
00:59:18,720 --> 00:59:21,300
Usted tiene el 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Sólo puede comparar la
a partir de todo.

1203
00:59:23,465 --> 00:59:26,340
Porque usted sabe que esto está ordenada
y usted sabe que eso está solucionado.

1204
00:59:26,340 --> 00:59:29,360
Así que usted ni siquiera tiene que
comparar el 5, que acaba de comparar el 3.

1205
00:59:29,360 --> 00:59:32,070
Y el 2 es menor que 3, por lo
sabes 2 deben ir al final.

1206
00:59:32,070 --> 00:59:33,120
>> Lo mismo allí.

1207
00:59:33,120 --> 00:59:34,740
El 1 debe ir aquí.

1208
00:59:34,740 --> 00:59:37,330
Y luego cuando se va a poner
esos dos valores juntos,

1209
00:59:37,330 --> 00:59:39,950
usted sabe que esto está ordenada y
usted sabe que lo que se solucionó.

1210
00:59:39,950 --> 00:59:43,240
Así entonces el 1 y el
2, el 1 es menor que 2.

1211
00:59:43,240 --> 00:59:45,570
Eso te dice que el 1
debe ir en el final de este

1212
00:59:45,570 --> 00:59:47,480
sin mirar siquiera a 3 o 5.

1213
00:59:47,480 --> 00:59:50,100
Y luego el 4, sólo puede
cheque, que va a la derecha aquí.

1214
00:59:50,100 --> 00:59:51,480
Usted no tiene que mirar el 5.

1215
00:59:51,480 --> 00:59:52,570
Lo mismo con el 6.

1216
00:59:52,570 --> 00:59:55,860
Usted sabe que el 6-- sólo
no necesita ser mirado.

1217
00:59:55,860 --> 00:59:57,870
>> Y así, de esa manera, usted es
simplemente ahorrándose

1218
00:59:57,870 --> 00:59:59,526
una gran cantidad de pasos cuando usted está comparando.

1219
00:59:59,526 --> 01:00:02,150
Usted no tiene que comparar cada
elemento contra otros elementos.

1220
01:00:02,150 --> 01:00:05,230
Usted acaba de comparar contra los
que usted necesita para comparar contra.

1221
01:00:05,230 --> 01:00:06,870
Así que eso es algo de un concepto abstracto.

1222
01:00:06,870 --> 01:00:10,540
No se preocupe si no es
bastante golpear su derecha todavía.

1223
01:00:10,540 --> 01:00:14,740
Pero, en general, esto es
cómo una combinación de tipo funciona.

1224
01:00:14,740 --> 01:00:17,750
Preguntas, preguntas rápidas,
antes de pasar?

1225
01:00:17,750 --> 01:00:18,550
Sí.

1226
01:00:18,550 --> 01:00:22,230
>> AUDIENCIA: Entonces usted dice que usted toma
el 1, y luego el 4 y el 6

1227
01:00:22,230 --> 01:00:23,860
y ponerlos en.

1228
01:00:23,860 --> 01:00:26,800
Así que no son those-- no están
que mirarlos

1229
01:00:26,800 --> 01:00:28,544
como elementos separados, no como el todo?

1230
01:00:28,544 --> 01:00:29,210
ANDI Peng: Sí.

1231
01:00:29,210 --> 01:00:32,020
Así que lo que está pasando
es que, básicamente,

1232
01:00:32,020 --> 01:00:33,650
están creando una nueva gama de la marca.

1233
01:00:33,650 --> 01:00:36,690
Así que ya sabes que, aquí, tengo
dos matrices de tamaño 3, ¿verdad?

1234
01:00:36,690 --> 01:00:39,600
Así que ya sabes que mi matriz ordenada
necesita tener seis elementos.

1235
01:00:39,600 --> 01:00:42,270
Así que usted acaba de crear una
nueva cantidad de memoria.

1236
01:00:42,270 --> 01:00:44,270
Así que usted es algo así como
siendo un desperdicio de la memoria,

1237
01:00:44,270 --> 01:00:46,186
pero eso no importa
porque es muy pequeña.

1238
01:00:46,186 --> 01:00:48,590
Así que nos fijamos en el 1
y nos fijamos en el 2.

1239
01:00:48,590 --> 01:00:50,770
Y usted sabe que el 1 es inferior a 2.

1240
01:00:50,770 --> 01:00:53,840
Así que ya sabes que 1 debe ir en
el comienzo de todo eso.

1241
01:00:53,840 --> 01:00:55,850
>> Ni siquiera necesita
mirar el 3 y el 5.

1242
01:00:55,850 --> 01:00:57,400
Así que ya sabes 1 va allí.

1243
01:00:57,400 --> 01:00:59,300
Entonces, básicamente, cortar el 1.

1244
01:00:59,300 --> 01:01:00,370
Es, como, muerto para nosotros.

1245
01:01:00,370 --> 01:01:03,690
Entonces sólo tenemos 2,
3, 5, y luego 4 y 6.

1246
01:01:03,690 --> 01:01:06,270
Y entonces usted sabe eso,
comparar el 4 y el 2,

1247
01:01:06,270 --> 01:01:07,560
oh, el 2 debe entrar ahí.

1248
01:01:07,560 --> 01:01:09,685
Así que usted plop del 2 abajo, usted taja apagado.

1249
01:01:09,685 --> 01:01:12,060
Entonces sólo tiene el 3
y el 5 en el 4 y el 6.

1250
01:01:12,060 --> 01:01:14,650
Y te quedas picado fuera
hasta que se los pone en la matriz.

1251
01:01:14,650 --> 01:01:17,110
>> AUDIENCIA: Entonces, no eres más que siempre
comparando el [inaudible]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI Peng: Exactamente.

1253
01:01:17,710 --> 01:01:19,590
Así que en ese sentido, usted es
simplemente comparando, en esencia,

1254
01:01:19,590 --> 01:01:21,240
un número contra el otro número.

1255
01:01:21,240 --> 01:01:22,990
Y porque sabes
que ha ordenado, que

1256
01:01:22,990 --> 01:01:24,350
no tienen que mirar a través de
todos los números.

1257
01:01:24,350 --> 01:01:25,870
Sólo tienes que mirar a la primera.

1258
01:01:25,870 --> 01:01:27,582
Y entonces usted puede simplemente plop
hacia abajo, porque sabes

1259
01:01:27,582 --> 01:01:29,640
pertenecen donde tienen que pertenecer.

1260
01:01:29,640 --> 01:01:31,030
Sí.

1261
01:01:31,030 --> 01:01:32,920
Buena pregunta.

1262
01:01:32,920 --> 01:01:35,290
>> Y a continuación, si alguno de ustedes
son un poco ambicioso,

1263
01:01:35,290 --> 01:01:38,660
no dude en mirar este código.

1264
01:01:38,660 --> 01:01:40,680
Esto es en realidad la
implementación física

1265
01:01:40,680 --> 01:01:42,150
de cómo escribiríamos fusión tipo.

1266
01:01:42,150 --> 01:01:44,070
Y usted puede ver, es muy corto.

1267
01:01:44,070 --> 01:01:46,310
Pero las ideas que hay detrás
que son bastante complejos.

1268
01:01:46,310 --> 01:01:50,865
Así que si tienes ganas de dibujar esto
en su tarea esta noche, no dude en.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> OK.

1271
01:01:54,740 --> 01:01:58,070
David también se acercó esto en conferencia.

1272
01:01:58,070 --> 01:02:00,660
¿Cuáles son el mejor caso
tiempos de ejecución, peores tiempos de ejecución de casos,

1273
01:02:00,660 --> 01:02:05,680
y los tiempos de ejecución previstos de fusión tipo?

1274
01:02:05,680 --> 01:02:07,260
Un par de segundos para pensar.

1275
01:02:07,260 --> 01:02:11,198
Esto es bastante difícil, pero un poco
intuitiva si se piensa en ello.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Correcto.

1278
01:02:23,054 --> 01:02:25,269
>> AUDIENCIA: Es el peor de los casos n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI Peng: Exactamente.

1280
01:02:26,060 --> 01:02:29,380
Y ¿por qué es n log n.

1281
01:02:29,380 --> 01:02:32,230
>> AUDIENCIA: ¿No es porque
se convierte en exponencialmente más rápido,

1282
01:02:32,230 --> 01:02:35,390
así que es como una función de la que
en lugar de simplemente ser n

1283
01:02:35,390 --> 01:02:37,529
cuadrado o algo así?

1284
01:02:37,529 --> 01:02:38,320
ANDI Peng: Exactamente.

1285
01:02:38,320 --> 01:02:40,750
Así que la razón por qué el
tiempo de ejecución en este registro es n

1286
01:02:40,750 --> 01:02:44,310
n es porque-- lo estás
haciendo en todos estos pasos?

1287
01:02:44,310 --> 01:02:46,190
No eres más que cortar por la mitad, ¿no?

1288
01:02:46,190 --> 01:02:48,750
Y así, cuando estamos haciendo
registro, todo lo que está haciendo

1289
01:02:48,750 --> 01:02:53,150
se dividir un problema en un medio,
en medio, en un medio, en más de mitades.

1290
01:02:53,150 --> 01:02:56,430
Y en ese sentido, puede especie
de eliminar el modelo lineal

1291
01:02:56,430 --> 01:02:57,510
que hemos estado usando.

1292
01:02:57,510 --> 01:03:00,254
Porque cuando picar
cosas de la media, que es un registro.

1293
01:03:00,254 --> 01:03:02,420
Eso es sólo la matemática
manera de representarlo.

1294
01:03:02,420 --> 01:03:06,310
>> Y, finalmente, al final, eres
sólo hacer un último pase a través

1295
01:03:06,310 --> 01:03:07,930
poner todo en orden, ¿no?

1296
01:03:07,930 --> 01:03:10,330
Y por lo que si usted sólo tiene que
comprobar una cosa, eso es n.

1297
01:03:10,330 --> 01:03:13,420
Y por lo que es clase de
multiplicando los dos juntos.

1298
01:03:13,420 --> 01:03:17,660
Así que es como si tuvieras esa final
comprobar N aquí con un registro de n

1299
01:03:17,660 --> 01:03:18,390
aquí arriba.

1300
01:03:18,390 --> 01:03:21,060
Y si se multiplica
ellos, eso es n log n.

1301
01:03:21,060 --> 01:03:26,100
>> Y así, el mejor de los casos y lo peor
caso y espera que se todo n log n.

1302
01:03:26,100 --> 01:03:27,943
Es también como otra especie.

1303
01:03:27,943 --> 01:03:30,090
Es como una especie de selección
en el sentido de que

1304
01:03:30,090 --> 01:03:32,131
no importa lo que su
lista es, que sólo va

1305
01:03:32,131 --> 01:03:34,801
a hacer lo mismo cada vez.

1306
01:03:34,801 --> 01:03:35,300
OK.

1307
01:03:35,300 --> 01:03:39,950
Así como ustedes pueden ver, a pesar de que
los géneros que nos hemos ido through-- n

1308
01:03:39,950 --> 01:03:41,660
cuadrado, no es muy eficiente.

1309
01:03:41,660 --> 01:03:47,060
E incluso este n log n es
no es el más eficiente.

1310
01:03:47,060 --> 01:03:49,720
Si ustedes son curiosos,
hay mecanismos de ordenación

1311
01:03:49,720 --> 01:03:54,310
que son tan eficientes que son
casi esencialmente plano en tiempo de ejecución.

1312
01:03:54,310 --> 01:03:55,420
>> Tienes algún log n de.

1313
01:03:55,420 --> 01:03:58,190
Tienes algún registro de log n de.

1314
01:03:58,190 --> 01:04:00,330
No tocamos sobre ellos
en esta clase en este momento.

1315
01:04:00,330 --> 01:04:02,663
Pero si ustedes son curiosos,
no dude en google, lo que es

1316
01:04:02,663 --> 01:04:04,392
los mecanismos de clasificación más eficiente.

1317
01:04:04,392 --> 01:04:06,350
No sé, hay
algunos realmente divertidos,

1318
01:04:06,350 --> 01:04:09,860
como-- hay algo de verdad
los divertidos que la gente hace.

1319
01:04:09,860 --> 01:04:12,210
Y uno se pregunta cómo
Alguna vez has pensado en eso.

1320
01:04:12,210 --> 01:04:15,730
Así google, si tienes algo de repuesto
tiempo, en adelante, ¿cuáles son algunas maneras divertidas

1321
01:04:15,730 --> 01:04:17,730
que personas--, así como
personas ways-- eficientes

1322
01:04:17,730 --> 01:04:20,371
han sido capaces de poner en práctica las clases.

1323
01:04:20,371 --> 01:04:20,870
OK.

1324
01:04:20,870 --> 01:04:22,880
Y aquí es sólo un poco de práctica tabla.

1325
01:04:22,880 --> 01:04:26,850
Sé que todos ustedes, antes de esa prueba 0,
estará en su habitación, probablemente tratando

1326
01:04:26,850 --> 01:04:27,960
memorizar eso.

1327
01:04:27,960 --> 01:04:30,940
Así que eso es bueno ahí para ustedes.

1328
01:04:30,940 --> 01:04:37,120
Pero no se olvide la lógica que made--
¿por qué esos números estaban ocurriendo.

1329
01:04:37,120 --> 01:04:39,870
Si siempre estás perdido, simplemente hacer
Asegúrese de saber lo que los tipos son.

1330
01:04:39,870 --> 01:04:40,820
Y se puede ejecutar a través de
en tu mente

1331
01:04:40,820 --> 01:04:42,903
averiguar por qué los
respuestas son esas respuestas.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Correcto.

1334
01:04:47,600 --> 01:04:49,680
Así que vamos a mover
en, por último, a la búsqueda.

1335
01:04:49,680 --> 01:04:51,638
Porque como los de usted
que han leído el conjunto de procesadores,

1336
01:04:51,638 --> 01:04:55,175
la búsqueda es también parte de
El problema de esta semana pone.

1337
01:04:55,175 --> 01:04:57,300
Se le pedirá a aplicar
dos tipos de búsquedas.

1338
01:04:57,300 --> 01:05:00,070
Se trata de una búsqueda lineal y
uno es una búsqueda binaria.

1339
01:05:00,070 --> 01:05:01,760
>> Así que la búsqueda lineal es bastante fácil.

1340
01:05:01,760 --> 01:05:04,070
Lo que desea es buscar elementos
de una lista para ver si usted lo consigue.

1341
01:05:04,070 --> 01:05:05,444
Sólo tienes que recorrer.

1342
01:05:05,444 --> 01:05:08,170
Y si es igual a algo,
usted puede devolverlo, ¿verdad?

1343
01:05:08,170 --> 01:05:10,890
Pero el que estamos más
interesado en hablar de

1344
01:05:10,890 --> 01:05:14,550
es la búsqueda binaria, la derecha, que es el
dividir y conquistar mecanismo que

1345
01:05:14,550 --> 01:05:18,190
David estaba demostrando en la conferencia.

1346
01:05:18,190 --> 01:05:20,810
>> Recuerde el ejemplo guía de teléfonos
que sigue la educación de,

1347
01:05:20,810 --> 01:05:23,960
la que él luchó tipo de
un poco en este último año,

1348
01:05:23,960 --> 01:05:27,530
donde se divide el problema en el medio,
en medio, en medio, una y otra vez,

1349
01:05:27,530 --> 01:05:30,730
hasta encontrar lo que estás buscando?

1350
01:05:30,730 --> 01:05:33,727
Y tienes la
tiempo de ejecución de eso también.

1351
01:05:33,727 --> 01:05:35,810
Y usted puede ver, es
significativamente más eficiente

1352
01:05:35,810 --> 01:05:39,080
que cualquier otro tipo de búsqueda.

1353
01:05:39,080 --> 01:05:41,880
>> Así que la forma en que íbamos a ir sobre
la implementación de una búsqueda binaria

1354
01:05:41,880 --> 01:05:46,510
Es decir, si teníamos una matriz,
índice de 0 a 6, siete elementos,

1355
01:05:46,510 --> 01:05:49,790
podemos mirar en el medio, derecha-
lo siento, si nuestra pregunta primero--

1356
01:05:49,790 --> 01:05:53,840
si queremos hacer la pregunta de, ¿tiene
la matriz contiene el elemento de 7,

1357
01:05:53,840 --> 01:05:56,840
obviamente, siendo los seres humanos, y que tiene
como un pequeño arsenal, es fácil para nosotros

1358
01:05:56,840 --> 01:05:58,210
decir sí.

1359
01:05:58,210 --> 01:06:05,750
Pero la manera de implementar un binario
Búsqueda sería buscar en el medio.

1360
01:06:05,750 --> 01:06:08,020
>> Sabemos que el índice 3 es
el medio, ya que

1361
01:06:08,020 --> 01:06:09,270
saben que hay siete elementos.

1362
01:06:09,270 --> 01:06:10,670
¿Cuál 7 dividido por 2?

1363
01:06:10,670 --> 01:06:12,850
Usted puede cortar ese extra 1.

1364
01:06:12,850 --> 01:06:14,850
Tienes 3 en el medio.

1365
01:06:14,850 --> 01:06:17,590
Así que es conjunto de 3 igual a 7?

1366
01:06:17,590 --> 01:06:18,900
¿No está bien?

1367
01:06:18,900 --> 01:06:21,050
Pero podemos hacer un par de cheques.

1368
01:06:21,050 --> 01:06:25,380
Es gama de 3 a menos de 7 o
es gama de 3 mayor que 7?

1369
01:06:25,380 --> 01:06:27,240
>> Y sabemos que es menos de 7.

1370
01:06:27,240 --> 01:06:30,259
Así que sabemos que, oh, debe
no estar en la mitad izquierda.

1371
01:06:30,259 --> 01:06:32,300
Sabemos que debe ser
en la mitad derecha, ¿no?

1372
01:06:32,300 --> 01:06:34,662
Así que sólo podemos cortar la mitad de la matriz.

1373
01:06:34,662 --> 01:06:36,370
Ni siquiera tenemos que
verlo nunca más.

1374
01:06:36,370 --> 01:06:38,711
Porque sabemos que
la mitad de nuestro problema--

1375
01:06:38,711 --> 01:06:41,210
sabemos que la respuesta está en
la mitad derecha de nuestro problema.

1376
01:06:41,210 --> 01:06:42,580
Así que sólo nos fijamos en eso ahora.

1377
01:06:42,580 --> 01:06:44,860
>> Así que ahora nos fijamos en el
medio de lo que queda.

1378
01:06:44,860 --> 01:06:46,880
Ese índice 5.

1379
01:06:46,880 --> 01:06:50,200
Hacemos lo mismo cheque de nuevo
y vemos que es más pequeño.

1380
01:06:50,200 --> 01:06:52,050
Así que miramos a la izquierda de eso.

1381
01:06:52,050 --> 01:06:53,430
Y entonces vemos que cheque.

1382
01:06:53,430 --> 01:06:57,600
Es el valor de la matriz en
índice de 4 igual a 7?

1383
01:06:57,600 --> 01:06:58,260
Es.

1384
01:06:58,260 --> 01:07:03,580
Así que podemos devolver cierto, porque
encontramos el valor en nuestra lista.

1385
01:07:03,580 --> 01:07:06,738
¿La manera en que yo pasé por
Eso tiene sentido para todo el mundo?

1386
01:07:06,738 --> 01:07:08,760
OK.

1387
01:07:08,760 --> 01:07:11,670
Te voy a dar chicos tal vez, como,
tres, cuatro minutos para averiguar

1388
01:07:11,670 --> 01:07:13,270
cómo esto en pseudocódigo.

1389
01:07:13,270 --> 01:07:18,070
>> Así que imagino que te pedí que escribir una
función llamada de búsqueda () que devuelve

1390
01:07:18,070 --> 01:07:20,640
un valor, un valor booleano,
eso era cierto o false-- como,

1391
01:07:20,640 --> 01:07:22,970
cierto si usted encontró el
valor, false si no lo hiciste.

1392
01:07:22,970 --> 01:07:25,230
Y entonces eras
aprobada en el valor que

1393
01:07:25,230 --> 01:07:28,410
estabas buscando en valores, que
es la array-- oh, definitivamente puse

1394
01:07:28,410 --> 01:07:29,410
que en el lugar equivocado.

1395
01:07:29,410 --> 01:07:29,580
OK.

1396
01:07:29,580 --> 01:07:31,829
De todas formas, eso debería tener
estado a la derecha de los valores.

1397
01:07:31,829 --> 01:07:36,280
Y luego int n es el número
de elementos en la matriz.

1398
01:07:36,280 --> 01:07:39,430
¿Cómo haría usted para tratar
pseudocódigo para ese problema en?

1399
01:07:39,430 --> 01:07:41,630
Te voy a dar a tipos como
tres minutos para hacer eso.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
No, creo que hay only--
sí, hay uno justo aquí.

1402
01:08:02,595 --> 01:08:03,261
AUDIENCIA: ¿Puedo?

1403
01:08:03,261 --> 01:08:04,388
ANDI Peng: Sí, lo tienes.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
¿Es que el trabajo?

1406
01:08:11,050 --> 01:08:12,290
Vale, guay.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> OK.

1409
01:10:44,720 --> 01:10:47,630
Todas las personas adecuadas, estamos
va a frenar en.

1410
01:10:47,630 --> 01:10:49,730
OK.

1411
01:10:49,730 --> 01:10:54,020
Así que suponemos que tenemos esta hermosa
pequeña matriz con n valores en el mismo.

1412
01:10:54,020 --> 01:10:55,170
Yo no dibujar las líneas.

1413
01:10:55,170 --> 01:10:58,649
Pero ¿cómo podemos ir sobre
tratando de escribir esto?

1414
01:10:58,649 --> 01:11:00,440
¿Alguien quiere
dame la primera línea?

1415
01:11:00,440 --> 01:11:02,814
Si quiere darme la
primera línea de este pseudocódigo.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> AUDIENCIA: [inaudible]

1418
01:11:08,430 --> 01:11:10,138
AUDIENCIA: Lo que quiere
iterar through--

1419
01:11:10,138 --> 01:11:11,094
AUDIENCIA: Sólo otro bucle for?

1420
01:11:11,094 --> 01:11:11,760
AUDIENCIA: --para.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI Peng: Así que éste es un poco complicado.

1423
01:11:17,780 --> 01:11:23,130
Piense sobre-- desea
para seguir funcionando este bucle

1424
01:11:23,130 --> 01:11:27,950
una y otra vez hasta cuándo?

1425
01:11:27,950 --> 01:11:30,819
>> AUDIENCIA: Hasta el [inaudible]
valor es igual a ese valor.

1426
01:11:30,819 --> 01:11:31,610
ANDI Peng: Exactamente.

1427
01:11:31,610 --> 01:11:33,900
Así que usted puede en realidad sólo write--
incluso podemos simplificarlo más.

1428
01:11:33,900 --> 01:11:35,630
Sólo podemos hacer un bucle while, ¿verdad?

1429
01:11:35,630 --> 01:11:39,380
Así que usted puede simplemente tener loop--
sabemos que se trata de un tiempo.

1430
01:11:39,380 --> 01:11:42,850
Pero por ahora, me voy
decir "bucle" - a través de qué?

1431
01:11:42,850 --> 01:11:46,640
Loop until-- lo es
nuestra condición de finalización?

1432
01:11:46,640 --> 01:11:47,510
Creo que lo escuché.

1433
01:11:47,510 --> 01:11:48,530
Oí a alguien decir que.

1434
01:11:48,530 --> 01:11:51,255
>> Audiencia: Los valores equivalen a medio.

1435
01:11:51,255 --> 01:11:52,255
ANDI Peng: Dilo otra vez.

1436
01:11:52,255 --> 01:11:54,470
AUDIENCIA: O bien, hasta que el
valor que está buscando

1437
01:11:54,470 --> 01:11:58,470
por es igual al valor medio.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI Peng: ¿Y si no está ahí?

1439
01:12:00,280 --> 01:12:03,113
¿Qué pasa si el valor que está buscando
por no es en realidad en esta serie?

1440
01:12:03,113 --> 01:12:05,890
AUDIENCIA: Volverá 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI Peng: Pero, ¿qué es lo que queremos
bucle hasta si tenemos una condición?

1442
01:12:08,850 --> 01:12:09,350
Sí.

1443
01:12:09,350 --> 01:12:11,239
>> AUDIENCIA: Hasta que no haya un solo valor?

1444
01:12:11,239 --> 01:12:13,530
ANDI Peng: Usted puede recorrer
until-- así que usted sabe que usted es

1445
01:12:13,530 --> 01:12:15,714
va a tener un valor máximo, ¿no?

1446
01:12:15,714 --> 01:12:18,130
Y sabes que vas
tener un valor mínimo, ¿no?

1447
01:12:18,130 --> 01:12:20,379
Porque también, eso es algo
Me olvidé de decir antes,

1448
01:12:20,379 --> 01:12:22,640
que algo que es
crítico sobre la búsqueda binaria

1449
01:12:22,640 --> 01:12:24,182
es que la matriz ya está ordenado.

1450
01:12:24,182 --> 01:12:26,973
Porque no hay forma de hacer
esto si que son valores simplemente al azar.

1451
01:12:26,973 --> 01:12:29,190
Usted no sabe si uno es
más grande que la otra, ¿no?

1452
01:12:29,190 --> 01:12:32,720
>> Así que ya sabes que su máximo y
sus minutos están aquí, ¿verdad?

1453
01:12:32,720 --> 01:12:35,590
Si usted va a ser el ajuste
su máximo en sus minutos y los mid--

1454
01:12:35,590 --> 01:12:38,470
vamos a suponer que su
mediados valor es aquí-- derecho

1455
01:12:38,470 --> 01:12:43,910
vas a básicamente
bucle hasta su mínimo es

1456
01:12:43,910 --> 01:12:47,510
casi lo mismo que su máximo, a la derecha, o
si su máximo no es el mismo que el min.

1457
01:12:47,510 --> 01:12:48,040
¿Correcto?

1458
01:12:48,040 --> 01:12:51,340
Porque cuando eso sucede, usted sabe que
que finalmente ha golpeado el mismo valor.

1459
01:12:51,340 --> 01:12:59,135
¿Así que quieres bucle hasta el min
es menor o igual a-- perdón,

1460
01:12:59,135 --> 01:13:01,510
no menos de o igual a,
la otra forma es around-- max.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> ¿Eso tiene sentido?

1463
01:13:16,160 --> 01:13:18,810
Tomé un par de intentos para obtener ese derecho.

1464
01:13:18,810 --> 01:13:21,869
Pero bucle hasta su valor máximo
es esencialmente casi menos

1465
01:13:21,869 --> 01:13:23,410
o igual que el mínimo, ¿no?

1466
01:13:23,410 --> 01:13:25,201
Eso es cuando usted sabe
que ha convergido.

1467
01:13:25,201 --> 01:13:29,290
AUDIENCIA: ¿Cuándo su máximo
valor sea inferior al mínimo?

1468
01:13:29,290 --> 01:13:31,040
ANDI Peng: Si se mantiene
ajustándolo, que

1469
01:13:31,040 --> 01:13:32,380
es lo que nos vamos
estar haciendo en este.

1470
01:13:32,380 --> 01:13:33,460
¿Tiene sentido?

1471
01:13:33,460 --> 01:13:35,750
Mínimo y máximo son sólo
enteros que somos, probablemente,

1472
01:13:35,750 --> 01:13:39,260
va a querer crear para mantener
la pista de donde estamos buscando.

1473
01:13:39,260 --> 01:13:41,790
Debido a que existe la matriz
independientemente de lo que estamos haciendo.

1474
01:13:41,790 --> 01:13:45,030
Al igual, que no somos en realidad físicamente
cortando la matriz, ¿no?

1475
01:13:45,030 --> 01:13:47,261
Estamos ajustando
donde estamos buscando.

1476
01:13:47,261 --> 01:13:48,136
¿Tiene sentido?

1477
01:13:48,136 --> 01:13:48,472
>> AUDIENCIA: Sí.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI Peng: OK.

1479
01:13:49,110 --> 01:13:57,090
Así que si esa es la condición para nuestro bucle,
¿qué es lo que queremos dentro de este bucle?

1480
01:13:57,090 --> 01:13:58,700
¿Qué vamos a querer hacer?

1481
01:13:58,700 --> 01:14:02,390
Así que ahora mismo, tenemos
un máximo y un mínimo, a la derecha,

1482
01:14:02,390 --> 01:14:04,962
probablemente creado por aquí en alguna parte.

1483
01:14:04,962 --> 01:14:07,170
Vamos a probable que desee
encontrar un medio, ¿no?

1484
01:14:07,170 --> 01:14:08,450
¿Cómo vamos a ser
capaz de encontrar el medio?

1485
01:14:08,450 --> 01:14:09,491
¿Cuál es la mathematical--

1486
01:14:09,491 --> 01:14:11,079
AUDIENCIA: Max plus min dividido por 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI Peng: Exactamente.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
¿Tiene sentido?

1490
01:14:21,620 --> 01:14:25,780
Y es lo que ustedes veo por qué
no acaba de servicio- por qué hicimos esto

1491
01:14:25,780 --> 01:14:27,850
en lugar de hacer simplemente n dividido por 2?

1492
01:14:27,850 --> 01:14:30,310
Es porque n es un valor
eso va a seguir igual.

1493
01:14:30,310 --> 01:14:30,979
¿Correcto?

1494
01:14:30,979 --> 01:14:34,020
Pero a medida que nos adaptamos nuestra mínimo y
valores máximos, que van a cambiar.

1495
01:14:34,020 --> 01:14:36,040
Y como resultado, nuestra media
va a cambiar también.

1496
01:14:36,040 --> 01:14:37,873
Así que por eso queremos
para hacer esto aquí.

1497
01:14:37,873 --> 01:14:38,510
OK.

1498
01:14:38,510 --> 01:14:41,600
>> Y luego, ahora que
que hemos encontrado our-- sí.

1499
01:14:41,600 --> 01:14:44,270
>> AUDIENCIA: Sólo un pregunta-- rápida
cuando dices mínimo y máximo,

1500
01:14:44,270 --> 01:14:46,410
estamos asumiendo que
ya está ordenada?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI Peng: Sí, eso es en realidad un
condición previa para una búsqueda binaria,

1502
01:14:48,400 --> 01:14:49,816
que usted tiene que saber que está ordenada.

1503
01:14:49,816 --> 01:14:53,660
¿Cuál es la razón por clase, usted escribe en su
problema puesto delante de su búsqueda binaria.

1504
01:14:53,660 --> 01:14:55,910
OK.

1505
01:14:55,910 --> 01:14:58,876
Así que ahora que sabemos que nuestro punto medio
Es decir, ¿qué es lo que quieres hacer aquí?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> AUDIENCIA: Queremos comparar
que a la otra.

1508
01:15:04,319 --> 01:15:05,110
ANDI Peng: Exactamente.

1509
01:15:05,110 --> 01:15:12,280
Así que vamos a comparar
mediados de valor, ¿no?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
Y ¿qué dicen
nosotros cuando comparamos?

1512
01:15:18,670 --> 01:15:22,226
¿Qué es lo que queremos hacer después?

1513
01:15:22,226 --> 01:15:25,389
>> AUDIENCIA: Si el valor es mayor
de los mediados, queremos cortarlo.

1514
01:15:25,389 --> 01:15:26,180
ANDI Peng: Exactamente.

1515
01:15:26,180 --> 01:15:33,940
Así que si el valor es mayor
de los mediados, estamos

1516
01:15:33,940 --> 01:15:36,550
va a querer cambiar estos
Maxes mínimo y, ¿verdad?

1517
01:15:36,550 --> 01:15:38,980
¿Qué es lo que queremos cambiar?

1518
01:15:38,980 --> 01:15:42,145
Así que si conocemos el valor está en algún lugar
aquí, lo que debemos hacer para cambiar?

1519
01:15:42,145 --> 01:15:44,758
Queremos cambiar nuestra
mínima para ser mediados, ¿verdad?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
Y luego otra cosa, si es en este
medio, ¿qué es lo que queremos cambiar?

1522
01:15:54,292 --> 01:15:55,306
>> AUDIENCIA: Su máxima.

1523
01:15:55,306 --> 01:15:55,972
ANDI Peng: Sí.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
Y luego te vas
mantener bucle, ¿verdad?

1526
01:16:04,680 --> 01:16:08,920
Porque ahora, después de una iteración
a través, tienes un máximo aquí.

1527
01:16:08,920 --> 01:16:10,760
Y entonces usted puede volver a calcular una media.

1528
01:16:10,760 --> 01:16:11,990
Y entonces usted puede comparar.

1529
01:16:11,990 --> 01:16:14,766
Y vas a seguir adelante
hasta que los minutos y los Maxes

1530
01:16:14,766 --> 01:16:15,890
esencialmente han convergido.

1531
01:16:15,890 --> 01:16:17,890
Y eso es cuando se sabe que
has llegado a la final de la misma.

1532
01:16:17,890 --> 01:16:20,280
Y ya sea que lo hayas encontrado
o usted no tiene en ese punto.

1533
01:16:20,280 --> 01:16:23,170
>> ¿Tiene esto sentido para todo el mundo?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
OK.

1536
01:16:26,770 --> 01:16:27,900
Esto es muy importante,
ya que tendrá

1537
01:16:27,900 --> 01:16:29,760
escribir esto en el código de esta noche.

1538
01:16:29,760 --> 01:16:32,660
Pero ustedes tienen una muy buena
sentido de lo que debería estar haciendo,

1539
01:16:32,660 --> 01:16:34,051
lo cual es bueno.

1540
01:16:34,051 --> 01:16:34,550
OK.

1541
01:16:34,550 --> 01:16:38,840
Así que tenemos alrededor de siete
minuto sección izquierda.

1542
01:16:38,840 --> 01:16:43,170
Así que vamos a hablar de
este conjunto de procesadores que vamos a hacer.

1543
01:16:43,170 --> 01:16:46,410
Así que el conjunto de procesadores se divide en dos mitades.

1544
01:16:46,410 --> 01:16:50,230
La primera media implica
la implementación de un hallazgo

1545
01:16:50,230 --> 01:16:54,210
en el que se escribe una búsqueda lineal, un
búsqueda binaria, y un algoritmo de clasificación.

1546
01:16:54,210 --> 01:16:56,690
>> Así que esta es la primera
tiempo en un conjunto de procesadores, donde

1547
01:16:56,690 --> 01:17:00,050
estaremos dándole chicos lo que se llama
código de distribución, que es el código

1548
01:17:00,050 --> 01:17:02,740
que hemos pre-escrita,
pero sólo dejó algunas piezas fuera

1549
01:17:02,740 --> 01:17:04,635
para que usted pueda terminar de escribir.

1550
01:17:04,635 --> 01:17:07,510
Así que ustedes, si nos fijamos en este
código, es posible que se realmente asustado.

1551
01:17:07,510 --> 01:17:08,630
Si acaba gusta, ahh, yo
no saben lo que está haciendo,

1552
01:17:08,630 --> 01:17:11,670
No sé, como, eso parece
tan complicado, ahh, relajarse.

1553
01:17:11,670 --> 01:17:12,170
Esta bien.

1554
01:17:12,170 --> 01:17:12,930
Leer la especificación.

1555
01:17:12,930 --> 01:17:16,920
La especificación le explicará exactamente
lo que todos estos programas están haciendo.

1556
01:17:16,920 --> 01:17:20,560
>> Por ejemplo, es un programa generate.c
que vendrá con su conjunto de procesadores.

1557
01:17:20,560 --> 01:17:24,060
En realidad no hay que tocarlo, pero
usted debe entender lo que está haciendo.

1558
01:17:24,060 --> 01:17:28,550
Y generate.c, lo único que está haciendo es
ya sea generación de números aleatorios

1559
01:17:28,550 --> 01:17:32,400
o puede darle una semilla, como un
número preestablecido que se necesita,

1560
01:17:32,400 --> 01:17:34,140
y genera más números.

1561
01:17:34,140 --> 01:17:37,170
Así que hay una forma específica de
aplicar en el que generate.c

1562
01:17:37,170 --> 01:17:42,760
usted puede hacer un montón de números
para poner a prueba tus otros métodos sucesivamente.

1563
01:17:42,760 --> 01:17:45,900
>> Así que si usted quería, por
ejemplo, prueba de su hallazgo,

1564
01:17:45,900 --> 01:17:48,970
que se quiere ejecutar generate.c,
generar un montón de números,

1565
01:17:48,970 --> 01:17:50,880
y luego ejecutar su función de ayudantes.

1566
01:17:50,880 --> 01:17:53,930
La función de sus ayudantes es donde estás
escribir realmente físicamente código.

1567
01:17:53,930 --> 01:17:59,330
Y pensar ayudantes como un archivo de biblioteca
que está escrito que hallazgo está llamando.

1568
01:17:59,330 --> 01:18:02,950
Y así dentro helpers.c, podrás
hacer búsqueda y clasificación.

1569
01:18:02,950 --> 01:18:06,500
>> Y luego vas a esencialmente
sólo hay que poner a todos juntos.

1570
01:18:06,500 --> 01:18:10,350
La especificación le dirá cómo
puesto que en la línea de comandos.

1571
01:18:10,350 --> 01:18:14,880
Y podrás probar si o
no es su tipo y de búsqueda están trabajando.

1572
01:18:14,880 --> 01:18:15,870
Guay.

1573
01:18:15,870 --> 01:18:18,720
Alguien ha comenzado y
problemas o dudas planteadas

1574
01:18:18,720 --> 01:18:20,520
que tienen ahora con esto?

1575
01:18:20,520 --> 01:18:21,020
OK.

1576
01:18:21,020 --> 01:18:21,476
>> AUDIENCIA: Espere.

1577
01:18:21,476 --> 01:18:21,932
Tengo una pregunta.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI Peng: Sí.

1579
01:18:22,844 --> 01:18:28,390
>> AUDIENCIA: Así que empecé a hacer
la búsqueda lineal en helpers.c

1580
01:18:28,390 --> 01:18:29,670
y no fue realmente funciona.

1581
01:18:29,670 --> 01:18:34,590
Pero más tarde, me enteré de que sólo
que eliminarlo y hacer búsqueda binaria.

1582
01:18:34,590 --> 01:18:36,991
Así que qué importa si no funciona?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI Peng: Respuesta corta es no.

1585
01:18:41,510 --> 01:18:42,642
Pero ya que estamos no--

1586
01:18:42,642 --> 01:18:44,350
AUDIENCIA: Pero nadie de
realidad de cheques.

1587
01:18:44,350 --> 01:18:46,058
ANDI Peng: Nunca estamos
va a ver eso.

1588
01:18:46,058 --> 01:18:49,590
Pero es probable que desee hacer
Asegúrese de que su búsqueda está trabajando.

1589
01:18:49,590 --> 01:18:51,700
Porque si su lineal
búsqueda no funciona,

1590
01:18:51,700 --> 01:18:54,410
entonces es probable que su binario
búsqueda no va a funcionar tan bien.

1591
01:18:54,410 --> 01:18:56,646
Debido a que tiene similares
lógica en ambos.

1592
01:18:56,646 --> 01:18:58,020
Y no, no importa.

1593
01:18:58,020 --> 01:19:01,300
Así que los únicos que convertirán
en son de clasificación y búsqueda binaria.

1594
01:19:01,300 --> 01:19:02,490
Sí.

1595
01:19:02,490 --> 01:19:06,610
>> Y también, una gran cantidad de niños estaban
intentar compilar helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Usted no está realmente permitido
para hacer eso, porque helpers.c

1597
01:19:09,550 --> 01:19:11,200
no tiene una función principal.

1598
01:19:11,200 --> 01:19:13,550
Y por lo que sólo debe
ser en realidad la compilación

1599
01:19:13,550 --> 01:19:18,670
generar y encontrar, porque encontrar llamadas
helpers.c y las funciones que la integran.

1600
01:19:18,670 --> 01:19:20,790
Así que hace la depuración
un dolor en el trasero.

1601
01:19:20,790 --> 01:19:22,422
Pero eso es lo que tenemos que hacer.

1602
01:19:22,422 --> 01:19:23,880
AUDIENCIA: Usted acaba de hacer de todo, ¿no?

1603
01:19:23,880 --> 01:19:27,290
ANDI Peng: Usted puede simplemente
hacer todo así, sí.

1604
01:19:27,290 --> 01:19:28,060
OK.

1605
01:19:28,060 --> 01:19:32,570
Así que es eso en términos de lo
el conjunto de procesadores está pidiendo a todos a hacer.

1606
01:19:32,570 --> 01:19:35,160
Si usted tiene alguna pregunta,
libre de preguntarme después de la sección.

1607
01:19:35,160 --> 01:19:37,580
Voy a estar aquí por como 20 minutos.

1608
01:19:37,580 --> 01:19:40,500
>> Y sí, de el juego de parámetros
no está tan mal.

1609
01:19:40,500 --> 01:19:41,680
Ustedes deberían estar bien.

1610
01:19:41,680 --> 01:19:43,250
Estos, sólo tienes que seguir las directrices.

1611
01:19:43,250 --> 01:19:47,840
Clase de tener un sentido de, lógicamente, lo que
debería estar sucediendo y se le multa.

1612
01:19:47,840 --> 01:19:48,690
No sea demasiado asustada.

1613
01:19:48,690 --> 01:19:50,220
Hay una gran cantidad de código
ya escrito allí.

1614
01:19:50,220 --> 01:19:53,011
No sea demasiado asustado si no lo hace
entender lo que todo eso significa.

1615
01:19:53,011 --> 01:19:54,749
Si es mucho, es totalmente bien.

1616
01:19:54,749 --> 01:19:55,790
Y llegado a las horas de oficina.

1617
01:19:55,790 --> 01:19:57,520
Nosotros le ayudaremos a echar un vistazo.

1618
01:19:57,520 --> 01:20:00,810
>> AUDIENCIA: Con el extra
funciones, qué buscamos los de arriba?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI Peng: Sí, esas son en el código.

1620
01:20:03,417 --> 01:20:05,750
En el juego de 15, la mitad de
ya está escrito para usted.

1621
01:20:05,750 --> 01:20:09,310
Así que esas funciones están
Ya en el código.

1622
01:20:09,310 --> 01:20:12,020
Sí.

1623
01:20:12,020 --> 01:20:12,520
Correcto.

1624
01:20:12,520 --> 01:20:14,000
Bueno, mejor de las suertes.

1625
01:20:14,000 --> 01:20:15,180
Es un día asqueroso.

1626
01:20:15,180 --> 01:20:19,370
Así que espero que ustedes no se sienten demasiado
mal por permanecer dentro y codificación.

1627
01:20:19,370 --> 01:20:22,133