1
00:00:00,000 --> 00:00:03,332
>> [Música tocando]

2
00:00:03,332 --> 00:00:06,490
>> ANDI Pengo: Benvido á semana 3 da sección.

3
00:00:06,490 --> 00:00:09,550
Grazas, rapaces, para todo o que vén
a esta data de inicio máis cedo hoxe.

4
00:00:09,550 --> 00:00:11,466
Temos unha nice, pouco
grupo íntimo hoxe.

5
00:00:11,466 --> 00:00:14,570
Polo tanto, esperamos que nós imos chegar a
acabado quizais antes,

6
00:00:14,570 --> 00:00:15,780
un pouco máis cedo hoxe.

7
00:00:15,780 --> 00:00:22,057
Entón, rapidamente, só algúns
anuncios para a axenda de hoxe.

8
00:00:22,057 --> 00:00:23,890
Antes de comezar, estamos
indo a ir un pouco máis

9
00:00:23,890 --> 00:00:28,910
algunhas breves cuestións loxísticas, pset
preguntas, interrogue, cousas así.

10
00:00:28,910 --> 00:00:30,250
E entón nós imos mergullo na dereita.

11
00:00:30,250 --> 00:00:34,710
Imos usar un depurador chamado GDB
comezar a desbancar o noso código, que David

12
00:00:34,710 --> 00:00:36,550
explicou en rolda o outro día.

13
00:00:36,550 --> 00:00:39,420
Nós falaremos sobre os catro tipos de tipos.

14
00:00:39,420 --> 00:00:42,310
Nós imos pasar por riba deles moi rapidamente
xa que son moi intensivos.

15
00:00:42,310 --> 00:00:45,710
Pero sei que todo diapositivas e
código fonte están sempre en liña.

16
00:00:45,710 --> 00:00:50,810
Entón, Sinto-se a liberdade, na súa lectura, a
volver e un ollo niso.

17
00:00:50,810 --> 00:00:53,930
>> Nós imos pasar por
notación asintótica, que

18
00:00:53,930 --> 00:00:55,944
é só un xeito elegante
de dicir "tempos de execución",

19
00:00:55,944 --> 00:00:58,360
onde temos a gran O que
David explicou en rolda.

20
00:00:58,360 --> 00:01:01,550
E tamén temos Omega, que
é o tempo de execución límite inferior.

21
00:01:01,550 --> 00:01:06,450
E imos falar un pouco máis
en profundidade acerca de como os traballos.

22
00:01:06,450 --> 00:01:10,160
E, finalmente, imos pasar por riba de busca binaria,
porque moitos de vostedes que xa teñen

23
00:01:10,160 --> 00:01:15,190
mirou para os seus Serie de exercicios probablemente sabe que
que é un tema que está no seu pset.

24
00:01:15,190 --> 00:01:17,470
Entón vai ser feliz todos
que nós Cubrimos iso hoxe.

25
00:01:17,470 --> 00:01:20,610
>> E, por último, á súa
o producto sección, realmente

26
00:01:20,610 --> 00:01:23,000
deixou uns 15 minutos a
fin de ir un pouco máis

27
00:01:23,000 --> 00:01:27,730
loxística de pset3, dúbidas,
quizais un pouco de orientación, se quere,

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

29
00:01:28,990 --> 00:01:30,890
Entón, imos tentar pasar
o material moi rapidamente.

30
00:01:30,890 --> 00:01:33,880
E entón podemos pasar algún tempo
tendo máis preguntas ao pset.

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

32
00:01:35,230 --> 00:01:39,570
>> Rapidamente, así que só algúns
anuncios antes de comezar hoxe.

33
00:01:39,570 --> 00:01:45,410
En primeiro lugar, benvido a facer
Lo través de dous dos seus Serie de exercicios.

34
00:01:45,410 --> 00:01:49,432
Eu dei un ollo ao your-- Si, imos
obter unha salva de palmas para que un.

35
00:01:49,432 --> 00:01:51,140
En realidade, eu estaba realmente,
realmente impresionado.

36
00:01:51,140 --> 00:01:55,800
I clasificado o primeiro pset para vós
a semana pasada e que vostedes fixeron incrible.

37
00:01:55,800 --> 00:01:58,290
>> Estilo estaba no punto
ademais de algúns comentarios.

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

39
00:02:00,660 --> 00:02:03,040
Pero os seus Serie de exercicios foron no punto.

40
00:02:03,040 --> 00:02:05,549
E mantelo.

41
00:02:05,549 --> 00:02:08,090
E é bo para o alumno a
ver que vostedes están poñendo

42
00:02:08,090 --> 00:02:10,704
en tanto esforzo no seu estilo
eo seu proxecto no seu código

43
00:02:10,704 --> 00:02:12,120
que queremos para ti ver.

44
00:02:12,120 --> 00:02:16,450
Entón, eu estou pasando ao longo da miña gratitude
para o resto dos TAS.

45
00:02:16,450 --> 00:02:19,210
>> Con todo, hai un
algunhas preguntas Debrief

46
00:02:19,210 --> 00:02:22,010
Eu só quero pasar por riba dese
faría tanto a miña vida

47
00:02:22,010 --> 00:02:24,900
e unha morea de outros
TAS "vive un pouco máis fácil.

48
00:02:24,900 --> 00:02:28,220
En primeiro lugar, eu teño notado iso
pasado week-- cantos de vós

49
00:02:28,220 --> 00:02:32,301
xa están a funcionar en check50
seu código antes de enviar?

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

51
00:02:32,800 --> 00:02:36,690
Entón, todos deben estar facendo check50,
porque-- un secret-- realmente

52
00:02:36,690 --> 00:02:41,540
executar check50 como parte da nosa corrección
scripts para probar o seu código.

53
00:02:41,540 --> 00:02:45,480
Polo tanto, se o seu código está fallando
check50, con toda probabilidade,

54
00:02:45,480 --> 00:02:47,570
probablemente vai
falla noso check tamén.

55
00:02:47,570 --> 00:02:49,320
Ás veces, vostedes
ter as respostas correctas.

56
00:02:49,320 --> 00:02:52,200
Como, en ganancioso, algúns dos
tes os números correctos,

57
00:02:52,200 --> 00:02:53,960
só imprimir algún material extra.

58
00:02:53,960 --> 00:02:55,940
E ese material extra
realmente falla a verificación,

59
00:02:55,940 --> 00:02:58,440
porque o ordenador non fai
realmente sabe o que está a procurar.

60
00:02:58,440 --> 00:03:00,981
E así ela só vai percorrer,
ver que a súa saída non

61
00:03:00,981 --> 00:03:03,810
corresponden ao que esperamos que a resposta
para ser, e marcalo é incorrecto.

62
00:03:03,810 --> 00:03:06,560
>> E sei que pasou en
algúns dos seus casos esta semana.

63
00:03:06,560 --> 00:03:09,870
Entón, eu fun para atrás e manualmente
Reclassificados código de todos.

64
00:03:09,870 --> 00:03:12,780
No futuro, porén,
por favor, por favor, asegúrese

65
00:03:12,780 --> 00:03:14,570
que está executando
comprobar 50 no seu código.

66
00:03:14,570 --> 00:03:17,970
Porque é un tipo de dor ao TA
ter que volver e manualmente regrade

67
00:03:17,970 --> 00:03:21,197
cada pset único para cada
instancia única, pouco perdida.

68
00:03:21,197 --> 00:03:22,530
Así que non aproveitar os puntos.

69
00:03:22,530 --> 00:03:25,210
Creo que eu tirei quizais
un ou dous para o proxecto.

70
00:03:25,210 --> 00:03:27,710
No futuro, aínda que, se
está fallando check50,

71
00:03:27,710 --> 00:03:31,330
Os puntos serán tomadas
off para corrección.

72
00:03:31,330 --> 00:03:35,020
>> Ademais, son Serie de exercicios
debido venres ao mediodía.

73
00:03:35,020 --> 00:03:38,990
Eu creo que hai unha de sete minutos
período de carencia tarde que lle damos.

74
00:03:38,990 --> 00:03:42,434
Por tempo de Harvard, eles están autorizados a
ser de sete minutos de atraso para todo.

75
00:03:42,434 --> 00:03:44,350
Entón, aquí en Yale, imos
unirse a iso tamén.

76
00:03:44,350 --> 00:03:47,910
Pero practicamente, ás 12:07,
se o seu non está na pset,

77
00:03:47,910 --> 00:03:49,720
que vai ser marcado como final.

78
00:03:49,720 --> 00:03:53,160
E así, mentres está marcado
tan tarde, o TA-- son

79
00:03:53,160 --> 00:03:54,870
aínda vai ser Grading seus Serie de exercicios.

80
00:03:54,870 --> 00:03:56,760
Entón, aínda ver un grao aparecer.

81
00:03:56,760 --> 00:03:58,820
Con todo, sabemos que a
o final do semestre,

82
00:03:58,820 --> 00:04:02,270
todas Serie de exercicios final será só
zerada automaticamente polo ordenador.

83
00:04:02,270 --> 00:04:04,490
>> Facemos isto por dúas razóns.

84
00:04:04,490 --> 00:04:09,220
Un deles, ás veces ficamos
desculpado, como desculpas de Dean,

85
00:04:09,220 --> 00:04:10,762
máis tarde que eu non sei sobre iso aínda.

86
00:04:10,762 --> 00:04:13,761
Por iso, quere ter a certeza de que estamos clasificación
todo só no caso, como, eu son

87
00:04:13,761 --> 00:04:15,080
falta a escusa dun reitor.

88
00:04:15,080 --> 00:04:17,000
E en segundo lugar, Lembre
mente, tamén se pode

89
00:04:17,000 --> 00:04:19,370
soltar un pset que
ten puntos ámbito completo.

90
00:04:19,370 --> 00:04:21,430
E así nos gusta de grao
todos os seus Serie de exercicios só

91
00:04:21,430 --> 00:04:24,730
para asegurarse de que o seu ámbito de
alí e estás eles.

92
00:04:24,730 --> 00:04:29,150
Así, mesmo se é tarde, aínda
obter crédito para puntos de ámbito, eu creo.

93
00:04:29,150 --> 00:04:33,730
>> Entón moral da historia é, torná-
se dos seus Serie de exercicios están en dentro do prazo.

94
00:04:33,730 --> 00:04:38,350
E no caso de que non están en en tempo,
sei que non é grande.

95
00:04:38,350 --> 00:04:41,678
Si, antes de seguir adiante, alguén ten
calquera dúbida sobre o producto pset?

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

97
00:04:42,178 --> 00:04:43,630
>> Audiencia: Vostede dixo que
pode soltar unha das Serie de exercicios?

98
00:04:43,630 --> 00:04:44,296
>> ANDI Pengo: Si.

99
00:04:44,296 --> 00:04:47,050
Polo tanto, hai nove Serie de exercicios xeral
ao longo do semestre.

100
00:04:47,050 --> 00:04:50,610
E se ten alcance
points-- tan ámbito é xusto,

101
00:04:50,610 --> 00:04:53,567
moi ben, que estás a
problema, está poñendo o tempo,

102
00:04:53,567 --> 00:04:56,150
está amosando que ten
demostrada leu o spec.

103
00:04:56,150 --> 00:04:57,191
Iso é moi fermoso ámbito.

104
00:04:57,191 --> 00:04:59,370
E se está cumprindo
Os puntos de alcance, nós

105
00:04:59,370 --> 00:05:03,360
pode soltar o menor
un fóra de alcance global.

106
00:05:03,360 --> 00:05:06,790
Entón esta é a súa vantaxe para
cubrir e tentar todo pset.

107
00:05:06,790 --> 00:05:10,320
>> Mesmo se ningún dos upload--
Los traballar, subir de todos eles.

108
00:05:10,320 --> 00:05:13,711
E entón esperamos ser capaces de
darlle algúns destes puntos de volta.

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

110
00:05:14,210 --> 00:05:16,780
Algunha pregunta?

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

112
00:05:17,840 --> 00:05:21,960
>> En segundo lugar, oficina horas-- algúns
notas rápidas sobre o horario de oficina.

113
00:05:21,960 --> 00:05:24,300
Entón, primeiro, entrar no inicio da semana.

114
00:05:24,300 --> 00:05:26,909
Ninguén está sempre en
o horario de oficina os luns.

115
00:05:26,909 --> 00:05:28,700
Christabel veu a
o horario de oficina na noite pasada.

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

117
00:05:29,691 --> 00:05:32,190
E o que temos na oficina
horas na noite pasada, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> Audiencia: Tivemos sorbete.

119
00:05:33,020 --> 00:05:36,160
>> ANDI Pengo: Entón, iso é certo, tivemos
sorbete no horario de oficina na noite pasada.

120
00:05:36,160 --> 00:05:39,390
Mentres eu non podo prometer-lle que
teremos sorbete no horario de oficina

121
00:05:39,390 --> 00:05:43,230
cada semana, o que podo prometer-lle
é que haberá un aumento significativamente

122
00:05:43,230 --> 00:05:45,380
mellor relación de alumnos por TA.

123
00:05:45,380 --> 00:05:47,650
Como lexítimo, é como 3-1.

124
00:05:47,650 --> 00:05:50,350
Considerando que, contrastan coa que
Xoves, ten preto de 150

125
00:05:50,350 --> 00:05:52,830
realmente estrés nenos e non sorbete.

126
00:05:52,830 --> 00:05:55,360
E non é só produtivo para ninguén.

127
00:05:55,360 --> 00:05:58,730
Entón moral da historia é, chegou cedo
para as horas de expediente e cousas boas

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

129
00:06:00,310 --> 00:06:02,110
>> Ademais, veña preparado para facer preguntas.

130
00:06:02,110 --> 00:06:03,200
Ti sabes?

131
00:06:03,200 --> 00:06:05,420
Independentemente do que tas, I
pensan, teñen que chegou a dicir,

132
00:06:05,420 --> 00:06:10,710
recibimos un par de estudantes
que entran en xoves, como, 10:50

133
00:06:10,710 --> 00:06:15,100
non ler a especificación
sendo como me axude, me axude.

134
00:06:15,100 --> 00:06:18,200
Por desgraza, neste punto, non hai
Non moito que podemos facer para axudar.

135
00:06:18,200 --> 00:06:19,590
Entón, por favor, veña a principios da semana.

136
00:06:19,590 --> 00:06:22,040
Chegue antes para o horario de oficina.

137
00:06:22,040 --> 00:06:23,350
Veña preparado para facer preguntas.

138
00:06:23,350 --> 00:06:25,310
Asegúrese de que, como
un estudante, onde son

139
00:06:25,310 --> 00:06:27,620
ten que ser para que o
TAS poden oriente-lo xunto,

140
00:06:27,620 --> 00:06:32,850
que é o que o horario de oficina
debe ser asignado para.

141
00:06:32,850 --> 00:06:37,380
>> En segundo lugar, entón eu sei profesores
quere sorprender cos probas.

142
00:06:37,380 --> 00:06:39,439
Eu tiña un profesor quen
como, yo, por certo,

143
00:06:39,439 --> 00:06:41,230
lembre que intercalar
tes vindeiro luns.

144
00:06:41,230 --> 00:06:42,855
Si, eu non sei nada sobre iso intercalar.

145
00:06:42,855 --> 00:06:45,630
Entón, eu estou indo ser que TA
que recorda todo o que proba

146
00:06:45,630 --> 00:06:47,270
0-- porque, xa sabe, somos CS.

147
00:06:47,270 --> 00:06:50,730
Agora que temos matrices feito, comeza
por iso que é proba 0, non quiz-1, eh?

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

149
00:06:51,320 --> 00:06:52,490
Oh, eu teño algunhas risadas sobre iso.

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

151
00:06:53,120 --> 00:06:59,710
>> Entón cuestionario 0 será 14 de outubro se
está na sección de luns a mércores

152
00:06:59,710 --> 00:07:02,920
e 15 de outubro, se está en
a sección de martes a xoves.

153
00:07:02,920 --> 00:07:05,630
Isto non se aplica para
aqueles de vostedes en Harvard

154
00:07:05,630 --> 00:07:10,350
who-- Eu creo que vai ser todo
tendo súas probas o día 14.

155
00:07:10,350 --> 00:07:13,560
>> Entón, si, a próxima semana, se
David, en charla, vai,

156
00:07:13,560 --> 00:07:15,747
si, entón con iso
proba a próxima semana, todos vostedes

157
00:07:15,747 --> 00:07:17,580
non quedará impresionado porque
veu á sección

158
00:07:17,580 --> 00:07:19,664
e vostede sabe que o seu
0 proba é en dúas semanas.

159
00:07:19,664 --> 00:07:21,580
E teremos avaliación
sesións e todo máis.

160
00:07:21,580 --> 00:07:26,360
Así, non se preocupa
estar con medo por iso.

161
00:07:26,360 --> 00:07:29,890
Todas as preguntas antes-- dúbidas
en todas as cuestións loxísticas relativas,

162
00:07:29,890 --> 00:07:32,591
clasificación, o horario de oficina, seccións?

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

164
00:07:33,090 --> 00:07:35,100
>> Audiencia: Entón a proba é
será durante a charla?

165
00:07:35,100 --> 00:07:35,766
>> ANDI Pengo: Si.

166
00:07:35,766 --> 00:07:39,460
Entón o quiz, eu creo, é 60
minutos asignados en que período de tempo

167
00:07:39,460 --> 00:07:42,240
que só vai tomar
na clase.

168
00:07:42,240 --> 00:07:44,810
Entón non ten que vir en
en, tipo, un aleatoria 19:00.

169
00:07:44,810 --> 00:07:46,140
É todo de bo.

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

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

172
00:07:50,060 --> 00:07:50,840
>> Todo ben.

173
00:07:50,840 --> 00:07:54,330
Entón, nós estamos indo a
introducir un concepto para ti

174
00:07:54,330 --> 00:08:00,760
esta semana que David xa tipo
de abordou en charla a semana pasada.

175
00:08:00,760 --> 00:08:02,010
É chamado de GDB.

176
00:08:02,010 --> 00:08:05,570
E como moitos de vostedes, mentres en
o curso de escribir as súas Serie de exercicios,

177
00:08:05,570 --> 00:08:09,981
notar un gran botón que di
"Debug" na parte superior do seu IDE?

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

179
00:08:10,480 --> 00:08:13,770
Entón agora imos realmente comezar a desenterrar
o misterio do que aquel botón, en realidade,

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

181
00:08:14,270 --> 00:08:16,790
E eu asegura que, é unha
bonito, cousa linda.

182
00:08:16,790 --> 00:08:20,740
>> Entón, ata agora, creo
houbo dúas cousas

183
00:08:20,740 --> 00:08:23,320
os alumnos foron tipicamente
facendo cando depuración Serie de exercicios.

184
00:08:23,320 --> 00:08:27,635
Un deles, eles quere engadir
printf () - polo que cada poucas liñas,

185
00:08:27,635 --> 00:08:29,760
eles engadir nun printf () -
Oh, o que é esa variable?

186
00:08:29,760 --> 00:08:32,551
Oh, o que é esa variable agora--
e tipo de ver a progresión

187
00:08:32,551 --> 00:08:33,940
do seu código como é executado.

188
00:08:33,940 --> 00:08:37,030
Ou o segundo método é facer os nenos
que simplemente escribir a cousa toda

189
00:08:37,030 --> 00:08:38,610
e despois ir como este ao final.

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

191
00:08:39,970 --> 00:08:44,851
Eu asegura que, o mellor GDB
de ambos os métodos.

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

193
00:08:45,350 --> 00:08:46,980
Polo tanto, este será o seu novo mellor amigo.

194
00:08:46,980 --> 00:08:51,780
Porque é unha cousa bonita
monitores que tanto visualmente

195
00:08:51,780 --> 00:08:54,850
o que o seu código está facendo
nun punto específico

196
00:08:54,850 --> 00:08:57,486
así como o que todo o seu
variables están levando,

197
00:08:57,486 --> 00:08:59,610
como cales son os seus valores,
nese punto específico.

198
00:08:59,610 --> 00:09:02,670
E, deste xeito, pode realmente
definir puntos de interrupción no seu código.

199
00:09:02,670 --> 00:09:04,350
Pode realizar a través de liña por liña.

200
00:09:04,350 --> 00:09:07,324
GDB e só terá para
ti, exhibido para ti,

201
00:09:07,324 --> 00:09:09,490
que todas as variables
están, o que están facendo,

202
00:09:09,490 --> 00:09:10,656
o que está a suceder no código.

203
00:09:10,656 --> 00:09:13,240
E, de tal xeito, que é
moito máis fácil de ver

204
00:09:13,240 --> 00:09:17,120
o que está a suceder no canto de printf-ing
ou escribir para abaixo súas declaracións.

205
00:09:17,120 --> 00:09:19,160
>> Entón, imos facer un exemplo diso máis tarde.

206
00:09:19,160 --> 00:09:20,660
Entón, iso parece un pouco abstracto.

207
00:09:20,660 --> 00:09:23,490
Non te preocupes, nós imos facer exemplos.

208
00:09:23,490 --> 00:09:29,170
E así, esencialmente, as tres grandes,
funcións máis usadas que precisa en GDB

209
00:09:29,170 --> 00:09:32,500
son os próximos, Pasa,
e Póñase en botóns.

210
00:09:32,500 --> 00:09:34,860
Vou de cabeza
hai, en realidade, no momento.

211
00:09:34,860 --> 00:09:40,930
>> Entón vostedes todos poden ver que
ou eu debería ampliar un pouco?

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

213
00:09:43,220 --> 00:09:44,470
Na parte de atrás, pode ver iso?

214
00:09:44,470 --> 00:09:45,730
Debo facer zoom?

215
00:09:45,730 --> 00:09:46,480
Só un pouquiño?

216
00:09:46,480 --> 00:09:49,390
OK, legal.

217
00:09:49,390 --> 00:09:50,280
Alí imos nós.

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

219
00:09:50,960 --> 00:09:57,000
>> Entón, eu teño, aquí, a miña
implantación para ganancioso.

220
00:09:57,000 --> 00:10:01,430
E mentres unha morea de vostedes escribiu
ganancioso en loop while que form--

221
00:10:01,430 --> 00:10:04,890
é un xeito perfectamente aceptable para facer
ele-- outra forma de facelo é simplemente

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

223
00:10:06,280 --> 00:10:09,290
Porque entón pode que o seu
valor e, a continuación, ter o seu restante.

224
00:10:09,290 --> 00:10:11,150
E entón podes só
engadir lo todos xuntos.

225
00:10:11,150 --> 00:10:13,390
Será que a lóxica do que eu estou facendo
aquí ter sentido para todos,

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

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

228
00:10:16,760 --> 00:10:17,980
Tipo de?

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

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

231
00:10:19,210 --> 00:10:21,290
É unha peza moi sexy
de código, eu diría.

232
00:10:21,290 --> 00:10:23,502
Como dixen, David, en
charla, despois dun tempo,

233
00:10:23,502 --> 00:10:25,960
todo o que vai comezar a ver código
como algo que é bonito.

234
00:10:25,960 --> 00:10:29,950
E ás veces cando ve fermosa
código, é unha sensación marabillosa.

235
00:10:29,950 --> 00:10:35,410
>> Entón, con todo, mentres este código é moi
bonito, non funciona correctamente.

236
00:10:35,410 --> 00:10:37,750
Entón, imos correr check50 sobre este asunto.

237
00:10:37,750 --> 00:10:39,440
Consulte 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
É que pset2?

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

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
Aceptar.

245
00:10:52,890 --> 00:10:53,900
Entón corremos check50.

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

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

248
00:11:07,170 --> 00:11:10,165
E para algúns de vós, no
curso de facer os seus conxuntos de problemas,

249
00:11:10,165 --> 00:11:11,110
vostede é como, ah, por que non funciona.

250
00:11:11,110 --> 00:11:13,318
Por que é traballar para algúns
valores, pero non para outros?

251
00:11:13,318 --> 00:11:17,760
Ben, GDB vai axudar a figura
por que esas entradas non estaban funcionando.

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

253
00:11:18,320 --> 00:11:21,640
Entón imos ver, un dos
cheques que estaba fallando en check50

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

255
00:11:24,920 --> 00:11:27,830
Polo tanto, a resposta correcta que
ten que estar recibindo é un 4.

256
00:11:27,830 --> 00:11:33,090
Pero en vez diso o que estou imprimindo
é o 3-N, que é correcta.

257
00:11:33,090 --> 00:11:36,190
Entón imos realizar isto manualmente, só
asegúrese de que check50 funciona.

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

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

260
00:11:40,130 --> 00:11:43,340
Uups, eu teño que facer ganancioso.

261
00:11:43,340 --> 00:11:43,840
Alí imos nós.

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

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

264
00:11:46,950 --> 00:11:47,670
>> Canto é debido?

265
00:11:47,670 --> 00:11:49,550
Imos facer 0,41.

266
00:11:49,550 --> 00:11:52,590
E si, vemos aquí
que é a saída 3

267
00:11:52,590 --> 00:11:55,160
cando a resposta correcta,
de feito, debe ser de 4.

268
00:11:55,160 --> 00:12:01,460
Entón, imos entrar GDB e ver como nós
pode ir sobre como corrixir este problema.

269
00:12:01,460 --> 00:12:03,992
>> Así, o primeiro paso na
sempre depuración do código

270
00:12:03,992 --> 00:12:05,950
é establecer un punto de interrupción,
ou un punto no que

271
00:12:05,950 --> 00:12:09,079
quere que o ordenador ou o
depurador para comezar a ollar para.

272
00:12:09,079 --> 00:12:11,120
Entón, se realmente non
sabe cal é o seu problema,

273
00:12:11,120 --> 00:12:14,670
Normalmente, a cousa típica queremos
facer é establecer o noso punto de interrupción na principal.

274
00:12:14,670 --> 00:12:18,520
Entón, se vostedes poden ver iso
botón vermello alí mesmo,

275
00:12:18,520 --> 00:12:22,860
Si, iso foi me establecendo un
breakpoint para a función principal.

276
00:12:22,860 --> 00:12:24,130
Eu prema iso.

277
00:12:24,130 --> 00:12:26,130
>> E entón eu podo ir ata o meu botón Debug.

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

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

280
00:12:31,710 --> 00:12:36,555
Déixeme zoom out se poida.

281
00:12:36,555 --> 00:12:38,020
Alí imos nós.

282
00:12:38,020 --> 00:12:40,730
Polo tanto, temos, aquí, un panel da dereita.

283
00:12:40,730 --> 00:12:43,680
Sinto moito, persoal na parte de atrás, vostede
non pode realmente ver moi ben.

284
00:12:43,680 --> 00:12:49,090
Pero, esencialmente, todo
este panel dereita está facendo

285
00:12:49,090 --> 00:12:53,130
é manter o control de ambos destaque
A liña, que é a liña de código

286
00:12:53,130 --> 00:12:56,640
que o ordenador está en execución,
así como todas as súas variables

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

288
00:12:57,600 --> 00:13:00,487
>> Entón tes centavos, moedas, n,
todos declararon a cousas distintas

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

290
00:13:01,070 --> 00:13:04,850
Non te preocupes, porque non temos, en realidade,
iniciar a eles a calquera variables aínda.

291
00:13:04,850 --> 00:13:07,200
Así, no seu ordenador, o seu
ordenador só está a ver,

292
00:13:07,200 --> 00:13:14,376
Oh, 32767 foi a última función utilizada
de que o espazo de memoria no meu ordenador.

293
00:13:14,376 --> 00:13:16,000
E así que é onde actualmente é centavos.

294
00:13:16,000 --> 00:13:19,360
Pero non que unha vez que realizar o código,
debe chegar a ser iniciado.

295
00:13:19,360 --> 00:13:24,110
>> Entón, imos pasar por, liña por
liña, o que está a suceder aquí.

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

297
00:13:25,350 --> 00:13:29,400
Entón, aquí están os tres
botóns que eu só explicada.

298
00:13:29,400 --> 00:13:34,090
Ten o Play, ou a función Run,
botón, ten a Paso sobre o botón,

299
00:13:34,090 --> 00:13:36,600
e tamén ten o botón Step Into.

300
00:13:36,600 --> 00:13:41,260
E esencialmente, os tres
eles só pasar polo seu código

301
00:13:41,260 --> 00:13:42,690
e facer cousas distintas.

302
00:13:42,690 --> 00:13:45,680
>> Entón, normalmente, cando está depurando,
nós non queremos é só usar Play,

303
00:13:45,680 --> 00:13:47,930
porque o xogo só funcionará
seu código para o fin de todo.

304
00:13:47,930 --> 00:13:49,070
E entón non vai realmente
sei que o seu problema

305
00:13:49,070 --> 00:13:51,432
é a menos que definir varios puntos de interrupción.

306
00:13:51,432 --> 00:13:53,890
Se establecer varios puntos de interrupción,
Ela só vai automaticamente

307
00:13:53,890 --> 00:13:56,030
executado desde un punto de interrupción,
ao seguinte, para o próximo.

308
00:13:56,030 --> 00:13:58,030
Pero neste caso temos
só que un, porque

309
00:13:58,030 --> 00:13:59,970
quere traballar o noso camiño
arriba abaixo abaixo.

310
00:13:59,970 --> 00:14:04,830
Entón, imos ignorar ese botón
agora para os fins deste programa.

311
00:14:04,830 --> 00:14:08,230
>> Así, o Paso sobre a función só
etapas, ao longo de cada liña única

312
00:14:08,230 --> 00:14:11,510
e dille o que
o ordenador está facendo.

313
00:14:11,510 --> 00:14:14,630
O Paso en función vai
para a función real

314
00:14:14,630 --> 00:14:16,000
que está na súa liña de código.

315
00:14:16,000 --> 00:14:19,070
Así, por exemplo, como printf (),
que é unha función, non?

316
00:14:19,070 --> 00:14:21,980
Se eu quixese fisicamente paso
para a función printf (),

317
00:14:21,980 --> 00:14:25,610
Gustaríame realmente ir ao anaco de
código onde printf () foi escrito e vexa

318
00:14:25,610 --> 00:14:26,730
o que está a suceder alí.

319
00:14:26,730 --> 00:14:29,924
>> Pero, normalmente, asumimos que
o código que nós dámoslle traballa.

320
00:14:29,924 --> 00:14:31,340
Asumimos o printf () funciona.

321
00:14:31,340 --> 00:14:33,170
Asumimos que GetInt () funciona.

322
00:14:33,170 --> 00:14:35,170
Polo tanto, non hai necesidade de
paso a estas funcións.

323
00:14:35,170 --> 00:14:37,170
Pero se hai funcións
que escribe en

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

325
00:14:39,060 --> 00:14:41,200
ía querer paso
en que a función.

326
00:14:41,200 --> 00:14:43,940
>> Entón, agora nós só estamos indo
de pasar por riba este anaco de código.

327
00:14:43,940 --> 00:14:44,485
Entón imos ver.

328
00:14:44,485 --> 00:14:46,547
Oh, impresión, "Oh hai, como
moita cambio é debido? "

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

330
00:14:47,130 --> 00:14:49,830
Sabemos que está a traballar,
por iso, pasar por riba dela.

331
00:14:49,830 --> 00:14:53,290
>> Entón n, que é o noso flotador que
temos initialized-- ou declared--

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

333
00:14:56,810 --> 00:14:57,810
Entón, imos pasar por riba diso.

334
00:14:57,810 --> 00:14:59,580
E vemos no
inferior aquí, o programa

335
00:14:59,580 --> 00:15:03,360
está me levando para introducir un valor.

336
00:15:03,360 --> 00:15:08,580
Entón entrada de deixar o valor que queremos
para probar aquí, que é 0,41.

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

338
00:15:09,160 --> 00:15:12,780
>> Entón agora n-- facer vostedes ver
aquí, no bottom-- é

339
00:15:12,780 --> 00:15:15,140
stored-- porque
non arredondados, é

340
00:15:15,140 --> 00:15:19,540
almacenados neste xigante como
flotador que é 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
que é preto o suficiente para o noso
propósitos, agora, para 0,41.

342
00:15:22,550 --> 00:15:26,090
E entón nós imos ver máis adiante, como nós
seguir pisando sobre o programa,

343
00:15:26,090 --> 00:15:29,850
despois aquí, n converteuse
redondeado e centavos converteuse en 41.

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

345
00:15:30,350 --> 00:15:32,230
Entón, nós sabemos que o traballo do noso redondeo.

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

347
00:15:34,700 --> 00:15:36,990
polo que sabemos que iso é
non é realmente o problema.

348
00:15:36,990 --> 00:15:40,050
>> Entón, nós seguimos pisando
en neste programa.

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

350
00:15:40,900 --> 00:15:46,139
E así, despois desta liña de código,
Debes saber cantos cuartos que temos.

351
00:15:46,139 --> 00:15:46,680
Nós pasar por riba.

352
00:15:46,680 --> 00:15:52,040
E ve o que facemos, de feito, ten un
trimestre porque temos subtraído 25

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

354
00:15:53,790 --> 00:15:55,890
E nós temos 16 esquerda nosos centavos.

355
00:15:55,890 --> 00:15:58,830
>> Será que todo o mundo entender como
estexa percorrendo

356
00:15:58,830 --> 00:16:02,980
e por centavos, pasou a ser 16
e por que, agora, as moedas tornouse un?

357
00:16:02,980 --> 00:16:04,610
Todos están seguindo esta lóxica?

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

359
00:16:05,110 --> 00:16:07,860
Así, a partir deste punto, o
de traballo do programa, non?

360
00:16:07,860 --> 00:16:09,797
Sabemos que está facendo exactamente
o que quere que sexa.

361
00:16:09,797 --> 00:16:11,880
E nós non o fixo, en realidade,
ten que imprimir, oh, o que

362
00:16:11,880 --> 00:16:14,430
é centavos, neste punto,
o que é moedas neste momento.

363
00:16:14,430 --> 00:16:17,170
>> Seguimos a atravesar o programa.

364
00:16:17,170 --> 00:16:18,100
Pasar por riba.

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

366
00:16:18,620 --> 00:16:19,700
Nós pasar por riba de moedas de dez centavos.

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

368
00:16:20,200 --> 00:16:22,367
Vemos que é tomado
fóra de $ 0,10 para un centavo.

369
00:16:22,367 --> 00:16:23,450
E agora temos dúas moedas.

370
00:16:23,450 --> 00:16:25,260
Isto é correcto.

371
00:16:25,260 --> 00:16:31,555
>> Nós pasar por riba de moedas de un centavo e vemos
que temos dabondo centavos.

372
00:16:31,555 --> 00:16:32,680
Hmm, iso é raro.

373
00:16:32,680 --> 00:16:37,540
Ata aquí no programa, eu debería
ter subtraído meus tostões.

374
00:16:37,540 --> 00:16:39,400
Poida que eu só non foi
facendo este dereito liña.

375
00:16:39,400 --> 00:16:42,190
E, por desgraza, pode ver
aquí, porque sabemos

376
00:16:42,190 --> 00:16:44,360
que estamos pisando
a través das liñas 32 e 33,

377
00:16:44,360 --> 00:16:50,560
que é onde o noso programa
impropiamente tivo variables executado.

378
00:16:50,560 --> 00:16:55,136
Así, podemos ollar para ver, oh,
Estou subtraindo centavos aquí,

379
00:16:55,136 --> 00:16:57,010
pero eu non son realmente
engadindo a miña valor da moeda.

380
00:16:57,010 --> 00:16:57,860
Eu estou engadindo ao centavos.

381
00:16:57,860 --> 00:17:00,234
E eu non quero engadir
centavos, quero engadir a moedas.

382
00:17:00,234 --> 00:17:05,420
Entón, se nós cambiar isto para moedas,
temos un programa de traballo.

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

384
00:17:06,730 --> 00:17:11,063
Pode simplemente saír do GDB dereita
aquí e despois executar check50 novo.

385
00:17:11,063 --> 00:17:11,938
Eu podería só facer.

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

387
00:17:14,822 --> 00:17:18,480
Teño que facer ganancioso.

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

389
00:17:19,940 --> 00:17:22,819
E aquí, é impresión
a resposta correcta.

390
00:17:22,819 --> 00:17:26,569
>> Entón, como podedes ver, GDB
é unha ferramenta moi poderosa

391
00:17:26,569 --> 00:17:29,940
para cando temos tanto código
pasando e tantas variables

392
00:17:29,940 --> 00:17:32,510
que é difícil para nós, como
un ser humano, para acompañar.

393
00:17:32,510 --> 00:17:35,360
O ordenador, o GDB
depurador, ten a capacidade

394
00:17:35,360 --> 00:17:37,020
manter o control de todo.

395
00:17:37,020 --> 00:17:40,480
Sei, en Visionaire, vostedes probablemente
pode atinxir algúns fallos de segmentación

396
00:17:40,480 --> 00:17:43,150
porque estaba executando
fóra dos límites da súa matriz.

397
00:17:43,150 --> 00:17:46,510
No exemplo de César, que é
exactamente o que eu teño aplicado aquí.

398
00:17:46,510 --> 00:17:50,060
>> Entón, eu esquezo de comprobar a
o que acontecería se eu

399
00:17:50,060 --> 00:17:52,510
non ter dous argumentos de liña de comandos.

400
00:17:52,510 --> 00:17:53,880
Eu só non poñer nesa selección.

401
00:17:53,880 --> 00:17:57,380
E así se eu executar Debug-- eu definir
o meu punto de interrupción para a dereita alí.

402
00:17:57,380 --> 00:17:58,055
Eu corro Debug.

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

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

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

406
00:18:17,050 --> 00:18:20,350
Entón, en realidade, era suposto GDB
ter me dixo que non

407
00:18:20,350 --> 00:18:22,300
Foi hai un fallo de segmento.

408
00:18:22,300 --> 00:18:24,883
Non sei o que estaba acontecendo
alí mesmo, pero cando eu execute,

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

410
00:18:25,590 --> 00:18:29,410
Cando fai liñas de código mediante e
GDB pode de súpeto deixar en ti,

411
00:18:29,410 --> 00:18:31,540
ir cara arriba e mira o que o erro é vermello.

412
00:18:31,540 --> 00:18:33,930
Só pode dicir-lle, hey,
tivo un fallo de segmentación,

413
00:18:33,930 --> 00:18:38,550
o que significa que intentou acceder
espazo nunha matriz que non existía.

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

415
00:18:39,050 --> 00:18:43,280
>> Así, o próximo problema
definir esta semana, vostedes

416
00:18:43,280 --> 00:18:45,600
probablemente vai ter unha chea de
variables flotando.

417
00:18:45,600 --> 00:18:48,560
Non vai estar seguro de que
todos eles significan nun determinado punto.

418
00:18:48,560 --> 00:18:53,560
Entón GDB vai realmente axudar en descubrir
o que están todos igualando

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

420
00:18:55,940 --> 00:19:01,995
Alguén está confuso sobre como
calquera que estaba a traballar?

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

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

423
00:19:10,121 --> 00:19:10,620
Todo ben.

424
00:19:10,620 --> 00:19:14,260
Entón, despois diso, estamos
vai mergullo na dereita

425
00:19:14,260 --> 00:19:17,562
en son catro diferentes
tipo de tipo para esta semana.

426
00:19:17,562 --> 00:19:19,520
Como moitos de vostedes, en primeiro lugar
de todo, antes de comezar,

427
00:19:19,520 --> 00:19:23,020
lin toda a especificación para pset3?

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

429
00:19:23,824 --> 00:19:24,740
Estou orgulloso de vós.

430
00:19:24,740 --> 00:19:29,110
Isto é como a metade da clase, que
é significativamente máis que a última vez.

431
00:19:29,110 --> 00:19:33,950
>> Entón, iso é óptimo, porque cando
falamos sobre o contido

432
00:19:33,950 --> 00:19:36,170
en lecture-- ou desculpe,
en section-- me gusta

433
00:19:36,170 --> 00:19:38,210
para relacionar unha morea de que
ao seu que o pset é

434
00:19:38,210 --> 00:19:40,210
e como quere
aplicar tanto no seu pset.

435
00:19:40,210 --> 00:19:42,400
Entón, se vén tendo
ler a especificación, que vai

436
00:19:42,400 --> 00:19:45,510
ser moito máis doado para ti entender
o que eu estou falando de como digo,

437
00:19:45,510 --> 00:19:48,720
oh hey, iso pode ser un realmente
bo lugar para aplicar este tipo.

438
00:19:48,720 --> 00:19:52,870
Así, aqueles de vostedes que leron o
especs saber que, como parte da súa pset,

439
00:19:52,870 --> 00:19:54,900
vai ter que
escribir un tipo de especie.

440
00:19:54,900 --> 00:19:58,670
Entón, iso pode ser moi útil
para unha morea de ti hoxe.

441
00:19:58,670 --> 00:20:01,760
>> Entón, imos comezar con,
Esencialmente, o tipo máis simple

442
00:20:01,760 --> 00:20:04,580
do tipo, o tipo de selección.

443
00:20:04,580 --> 00:20:06,800
O algoritmo típico para
como iríamos facer isto

444
00:20:06,800 --> 00:20:10,460
é-- David pasou por todas de
charla, entón eu vou moverse rapidamente ao longo

445
00:20:10,460 --> 00:20:13,900
aqui-- é esencialmente, ten
ten unha matriz de valores.

446
00:20:13,900 --> 00:20:17,170
E entón atopar o
menor valor sen clasificar

447
00:20:17,170 --> 00:20:20,200
e cambiar ese valor con
o primeiro valor indiferenciados.

448
00:20:20,200 --> 00:20:22,700
E entón simplemente seguir repetir
co resto da súa lista.

449
00:20:22,700 --> 00:20:25,740
>> E aquí está unha explicación visual
de como funciona isto.

450
00:20:25,740 --> 00:20:30,460
Así, por exemplo, se tivésemos de comezar
cunha serie de cinco elementos, índice

451
00:20:30,460 --> 00:20:35,910
0 a 4, con 3, 5, 2, 6 e 4 valores
colocado no array-- entón agora,

452
00:20:35,910 --> 00:20:38,530
nós só estamos indo a asumir
que todos son indiferenciados

453
00:20:38,530 --> 00:20:41,130
porque non proba o contrario.

454
00:20:41,130 --> 00:20:44,130
>> Entón, como unha especie de selección faría
traballo é que ía primeiro

455
00:20:44,130 --> 00:20:46,800
executado a través da totalidade
da matriz indiferenciados.

456
00:20:46,800 --> 00:20:49,120
El escollía o menor valor.

457
00:20:49,120 --> 00:20:51,750
Neste caso, 3, dereita
agora, é o menor.

458
00:20:51,750 --> 00:20:52,680
El está a 5.

459
00:20:52,680 --> 00:20:55,620
Non, 5 non é maior than--
ou desculpe, non é menos than-- 3.

460
00:20:55,620 --> 00:20:57,779
Así, o valor mínimo é aínda 3.

461
00:20:57,779 --> 00:20:58,695
E entón comeza a 2.

462
00:20:58,695 --> 00:21:00,990
O ordenador ve, oh, 2 é inferior a 3.

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

464
00:21:02,750 --> 00:21:06,630
E así 2 swaps que o primeiro valor.

465
00:21:06,630 --> 00:21:10,702
>> Entón, despois de un pase, nós realmente ver
que os 2 e os 3 son trocados.

466
00:21:10,702 --> 00:21:13,910
E nós só estamos indo a seguir fazê-
este novo co resto da matriz.

467
00:21:13,910 --> 00:21:17,660
Entón, nós estamos indo só para percorrer
os últimos catro índices da matriz.

468
00:21:17,660 --> 00:21:20,670
Imos ver o que é 3
o valor mínimo seguinte.

469
00:21:20,670 --> 00:21:23,240
Entón imos cambiar isto con 4.

470
00:21:23,240 --> 00:21:26,900
E entón nós só estamos indo a mantê-
que atravesa ata que, finalmente,

471
00:21:26,900 --> 00:21:33,730
chegar a unha matriz clasificada en que
2, 3, 4, 5, e 6 son todos clasificados.

472
00:21:33,730 --> 00:21:37,530
Será que todo o mundo entender a lóxica
de como unha especie de selección funciona?

473
00:21:37,530 --> 00:21:39,669
>> Só ten algún tipo
dun valor mínimo.

474
00:21:39,669 --> 00:21:41,210
Está mantendo o control de o que é.

475
00:21:41,210 --> 00:21:45,170
E sempre que atopalo, vostede trocalo
co primeiro valor na array--

476
00:21:45,170 --> 00:21:48,740
ou non o primeiro value--
o seguinte valor na matriz.

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

478
00:21:50,150 --> 00:21:55,460
>> Entón, como vostedes tipo de
viu dun breve reflexo,

479
00:21:55,460 --> 00:21:58,450
imos Pseudocódigo iso.

480
00:21:58,450 --> 00:22:02,510
Entón, se vostedes nas costas quere
formar un grupo, todo nunha mesa

481
00:22:02,510 --> 00:22:06,170
pode formar un pequeno compañeiro, eu vou
para dar a vostedes como tres minutos

482
00:22:06,170 --> 00:22:08,190
só para falar a través
a lóxica, en inglés,

483
00:22:08,190 --> 00:22:14,161
de como podemos ser capaces de aplicar
pseudocódigo para escribir unha especie de selección.

484
00:22:14,161 --> 00:22:14,910
E hai doces.

485
00:22:14,910 --> 00:22:16,118
Por favor, veña para arriba e obter doces.

486
00:22:16,118 --> 00:22:19,520
Se é na parte de atrás e quere
doces, podo xogaba caramelos en ti.

487
00:22:19,520 --> 00:22:22,850
En realidade, facer legal vocę--.

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

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

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

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

492
00:25:23,880 --> 00:25:27,140
>> Entón, se nós queremos, como
unha clase, escrita pseudocódigo

493
00:25:27,140 --> 00:25:30,466
por canto se podería achegar
este problema, só Sinto-se libre.

494
00:25:30,466 --> 00:25:32,340
Vou só ir ao redor e,
a fin, peza aos grupos

495
00:25:32,340 --> 00:25:35,065
á seguinte liña de
o que deberiamos estar facendo.

496
00:25:35,065 --> 00:25:37,840
Entón, se vostedes queren comezar
fóra, que é o primeiro

497
00:25:37,840 --> 00:25:40,600
Que facer cando estás
aplicar unha forma de solucionar este programa

498
00:25:40,600 --> 00:25:43,480
selectivamente para clasificar a lista?

499
00:25:43,480 --> 00:25:46,349
Nós só supor que
teño unha matriz, todo ben?

500
00:25:46,349 --> 00:25:49,088
>> Audiencia: Quere crear algúns
tipo de [inaudível] que é

501
00:25:49,088 --> 00:25:50,420
que atravesa toda a súa matriz.

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

503
00:25:51,128 --> 00:25:54,100
Entón vai querer facer unha iteración
a través de cada espazo, non?

504
00:25:54,100 --> 00:26:05,490
Entón, gran.

505
00:26:05,490 --> 00:26:08,600
Se vós queredes darme o
preto linha-- si, na parte de atrás.

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

507
00:26:11,414 --> 00:26:13,290
>> Audiencia: Verifique-
todo para o menor.

508
00:26:13,290 --> 00:26:14,248
>> ANDI Pengo: Alí imos nós.

509
00:26:14,248 --> 00:26:17,438
Por iso, queremos pasar e comprobar a
ver que o valor mínimo é, non?

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

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

512
00:26:24,840 --> 00:26:27,658
O que vostedes queren facer despois
atopou o valor mínimo?

513
00:26:27,658 --> 00:26:28,533
>> Audiencia: [inaudível]

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

515
00:26:29,942 --> 00:26:33,150
ANDI Pengo: Entón vai querer
liga-lo co primeiro dese array,

516
00:26:33,150 --> 00:26:33,650
non?

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

518
00:26:45,120 --> 00:26:46,850
Ese é o comezo, eu vou dicir.

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

520
00:26:47,220 --> 00:26:50,386
Polo tanto, agora que xa cambiou o primeiro
un, o que quere facer despois diso?

521
00:26:50,386 --> 00:26:54,840
Polo tanto, agora sabemos que este aquí
debe ser o menor valor, non?

522
00:26:54,840 --> 00:26:58,310
Entón tes un descanso adicional
da matriz que é indiferenciado.

523
00:26:58,310 --> 00:27:01,569
Entón, o que quere facer aquí, se
caras queren darme a seguinte liña?

524
00:27:01,569 --> 00:27:04,610
Audiencia: Entón quere facer unha iteración
a través do resto da matriz.

525
00:27:04,610 --> 00:27:05,276
ANDI Pengo: Si.

526
00:27:05,276 --> 00:27:09,857
E entón o que iterado
tipo de implicar probablemente imos ter?

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

528
00:27:10,440 --> 00:27:12,057
>> Audiencia: Oh, unha variable adicional?

529
00:27:12,057 --> 00:27:13,890
ANDI Pengo: Probablemente
outro loop for, non?

530
00:27:13,890 --> 00:27:28,914
Entón, nós estamos probablemente vai querer
iterado through-- grande.

531
00:27:28,914 --> 00:27:31,830
E entón vai volver e
probablemente comprobar o mínimo de novo,

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

533
00:27:32,100 --> 00:27:34,975
E vai estar repetindo
iso, porque os loops só vai

534
00:27:34,975 --> 00:27:36,010
para manter funcionando, non?

535
00:27:36,010 --> 00:27:39,190
>> Entón, como podedes ver, nós
pode ter un pseudocódigo xeral

536
00:27:39,190 --> 00:27:41,480
de como queremos que este programa para ollar.

537
00:27:41,480 --> 00:27:46,646
Este iterate aquí, que é o que nós
tipicamente que escribir no noso código

538
00:27:46,646 --> 00:27:49,270
se queremos facer unha iteración a través dun
matriz, o tipo de estrutura?

539
00:27:49,270 --> 00:27:51,030
Creo que Christabel
xa dixen que antes.

540
00:27:51,030 --> 00:27:51,500
>> Audiencia: Un lazo for.

541
00:27:51,500 --> 00:27:52,160
>> ANDI Pengo: Un loop for?

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

543
00:27:52,770 --> 00:27:56,060
Polo tanto, este é, probablemente,
vai ser un loop for.

544
00:27:56,060 --> 00:27:59,240
¿Que é un cheque aquí vai implicar?

545
00:27:59,240 --> 00:28:02,536
Normalmente, se quere comprobar
se algo é algo else--

546
00:28:02,536 --> 00:28:03,270
>> Audiencia: Se.

547
00:28:03,270 --> 00:28:06,790
>> ANDI Pengo: Un se, non?

548
00:28:06,790 --> 00:28:10,790
E entón o intercambio aquí, imos
pasar por riba máis tarde, porque David

549
00:28:10,790 --> 00:28:12,770
pasei por iso na charla tamén.

550
00:28:12,770 --> 00:28:14,580
E, a continuación, a segunda iteración implies--

551
00:28:14,580 --> 00:28:15,120
>> Audiencia: Outra loop for.

552
00:28:15,120 --> 00:28:16,745
>> ANDI Pengo: --another para loop, exactamente.

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

554
00:28:19,870 --> 00:28:22,000
Entón, se nós estamos mirando
neste correctamente,

555
00:28:22,000 --> 00:28:24,680
pode ver que estamos, probablemente,
Vai ter un lazo é aninhado

556
00:28:24,680 --> 00:28:28,330
cunha declaración condicional alí
e, a continuación, unha parte real de código que é

557
00:28:28,330 --> 00:28:31,360
indo para cambiar os valores.

558
00:28:31,360 --> 00:28:35,980
Entón eu só xeralmente escrito
un código de pseudocódigo aquí.

559
00:28:35,980 --> 00:28:38,910
E entón imos realmente
fisicamente, como unha clase,

560
00:28:38,910 --> 00:28:40,700
tentar implementar isto hoxe.

561
00:28:40,700 --> 00:28:42,486
Imos volver 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 que não-- aí está.

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

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

567
00:28:55,834 --> 00:28:57,500
Sentímolo, déixeme tentar ampliar un pouco máis.

568
00:28:57,500 --> 00:28:59,310
Alí imos nós.

569
00:28:59,310 --> 00:29:05,060
Todo o que eu estou facendo aquí é que eu creei
un programa chamado "selección / sort.c."

570
00:29:05,060 --> 00:29:10,860
Eu creei unha matriz de nove
valores, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Actualmente, como pode
ver, son non-ordenada.

572
00:29:14,370 --> 00:29:17,880
n vai ser o número que
dille a cantidade de valores

573
00:29:17,880 --> 00:29:18,920
ten na súa matriz.

574
00:29:18,920 --> 00:29:20,670
Neste caso, temos nove valores.

575
00:29:20,670 --> 00:29:23,760
E eu só teño un loop for aquí
que imprime a matriz indiferenciados.

576
00:29:23,760 --> 00:29:28,370
>> E ao final, eu tamén teño un para
loop que imprime-lo de novo.

577
00:29:28,370 --> 00:29:32,070
Entón, en teoría, se este programa
funciona correctamente, ao final,

578
00:29:32,070 --> 00:29:35,670
ten que ver un impreso para o lazo
en que 1, 2, 3, 4, 5, 6, 7, 8,

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

580
00:29:39,310 --> 00:29:43,410
>> Entón, nós temos o noso pseudocódigo aquí.

581
00:29:43,410 --> 00:29:46,090
Alguén quere para-- Eu son só
indo a ir pedir volunteers--

582
00:29:46,090 --> 00:29:49,540
me diga o que escribir se
queremos, en primeiro lugar, só unha iteración

583
00:29:49,540 --> 00:29:52,840
ata o inicio deste array?

584
00:29:52,840 --> 00:29:55,204
Cal é a liña de código que eu son
probablemente vai ter aquí?

585
00:29:55,204 --> 00:29:56,990
>> Audiencia: [inaudível]

586
00:29:56,990 --> 00:29:59,010
>> ANDI Pengo: Si, sinto
libre a-- Sentímolo, vostede

587
00:29:59,010 --> 00:30:02,318
Non ten que estar up-- sensación
libre para levantar a súa voz un pouco.

588
00:30:02,318 --> 00:30:08,190
>> Audiencia: Para int i é igual a 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI Pengo: Si, boa.

590
00:30:10,690 --> 00:30:15,220
>> Audiencia: i é menor que a lonxitude de matriz.

591
00:30:15,220 --> 00:30:19,630
>> ANDI Pengo: Entón Lembre
importa aquí, porque

592
00:30:19,630 --> 00:30:23,060
non ten unha función que
dinos a lonxitude dunha matriz,

593
00:30:23,060 --> 00:30:25,790
nós xa temos un
valor que almacena iso.

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

595
00:30:27,920 --> 00:30:31,010
Outro aspecto a ter
en mente-- nunha matriz

596
00:30:31,010 --> 00:30:33,940
de nove valores, cales son os índices?

597
00:30:33,940 --> 00:30:38,720
Nós só dicir que esta matriz era 0-3.

598
00:30:38,720 --> 00:30:41,500
Ve que a última
índice é, en realidade, tres.

599
00:30:41,500 --> 00:30:45,530
Non é 4, aínda que non haxa
catro valores na matriz.

600
00:30:45,530 --> 00:30:49,866
>> Entón aquí, temos que ter moito coidado
que a nosa condición para a lonxitude

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

602
00:30:50,490 --> 00:30:51,948
>> Audiencia: Non sería n menos 1?

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

604
00:30:54,440 --> 00:30:57,379
Isto ten sentido, porque
é n menos 1, todo o mundo?

605
00:30:57,379 --> 00:30:58,920
É porque as matrices son indexados cero.

606
00:30:58,920 --> 00:31:02,010
Comezan en 0 e executar ata n menos 1.

607
00:31:02,010 --> 00:31:03,210
Si, é un pouco complicado.

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

609
00:31:03,730 --> 00:31:05,929
E logo--

610
00:31:05,929 --> 00:31:08,054
Audiencia: Isnt'1 que
xa tomado coidado, porén,

611
00:31:08,054 --> 00:31:11,400
só por non dicir "inferior ou
igual "e só dicir" menos que? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI Pengo: Isto é un
pregunta moi boa.

613
00:31:13,108 --> 00:31:13,630
Entón, si.

614
00:31:13,630 --> 00:31:17,410
Pero tamén, o xeito que somos
aplicar o dereito de comprobar,

615
00:31:17,410 --> 00:31:19,120
precisa para comparar dous valores.

616
00:31:19,120 --> 00:31:21,009
Entón realmente quere
deixar o "a" baleiro.

617
00:31:21,009 --> 00:31:23,050
Porque se comparar
este, non vai

618
00:31:23,050 --> 00:31:25,530
ten algo despois que
para comparar, non?

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

620
00:31:27,460 --> 00:31:29,297
Entón i ++.

621
00:31:29,297 --> 00:31:30,380
Imos engadir nosos soportes en.

622
00:31:30,380 --> 00:31:30,880
Whoops.

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

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

625
00:31:34,710 --> 00:31:39,117
Polo tanto, temos o inicio
do noso circuíto externo.

626
00:31:39,117 --> 00:31:41,450
Entón, agora nós probablemente quere
crear unha variable para manter

627
00:31:41,450 --> 00:31:43,085
a par de menor valor, non?

628
00:31:43,085 --> 00:31:45,751
Alguén quere me dar o
liña de código que faría iso?

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

630
00:31:48,700 --> 00:31:53,570
O que necesitamos se imos
querer almacenar algo?

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

632
00:31:55,047 --> 00:31:57,630
Quizais un nome mellor para que
sería ser-- "temp" totalmente works--

633
00:31:57,630 --> 00:32:00,655
quizais un máis apropiadamente chamado sería,
se queremos que a menor value--

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

635
00:32:01,624 --> 00:32:02,790
ANDI Pengo: min, alí imos nós.

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

637
00:32:05,230 --> 00:32:08,340
E aquí, o que
quere arrinque-lo para?

638
00:32:08,340 --> 00:32:09,620
Isto é un pouco complicado.

639
00:32:09,620 --> 00:32:13,580
Porque agora no
inicio desta matriz,

640
00:32:13,580 --> 00:32:15,730
aínda non mirou para nada, non?

641
00:32:15,730 --> 00:32:19,200
Entón, o que, automaticamente, se
estamos só no i é igual a 0,

642
00:32:19,200 --> 00:32:22,302
o que queremos para arrincar
noso primeiro valor mínimo para?

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

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

645
00:32:24,790 --> 00:32:27,040
Christabel, por que queremos
para iniciar-lo para min?

646
00:32:27,040 --> 00:32:28,510
>> Audiencia: Porque ben,
estamos empezando 0.

647
00:32:28,510 --> 00:32:31,660
Entón, por que non temos nada para comparar
que, o mínimo vai acabar sendo 0.

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

649
00:32:32,451 --> 00:32:34,400
Entón, ela é exactamente correcto.

650
00:32:34,400 --> 00:32:36,780
Porque non temos realmente
mirou para nada aínda,

651
00:32:36,780 --> 00:32:38,680
Non sabemos o que o seu valor mínimo é.

652
00:32:38,680 --> 00:32:41,960
Queremos só arrincar-lo para
i, que, actualmente, está ben aquí.

653
00:32:41,960 --> 00:32:44,750
E mentres seguimos a
baixar esa matriz,

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

655
00:32:48,122 --> 00:32:49,830
E así, nese punto,
i seguramente

656
00:32:49,830 --> 00:32:52,329
a querer ser o menos,
porque vai ser o que quere

657
00:32:52,329 --> 00:32:54,520
é o inicio da matriz sen clasificar.

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

659
00:32:55,270 --> 00:32:58,720
>> Entón, agora queremos engadir
un loop for aquí que é

660
00:32:58,720 --> 00:33:03,225
vai percorrer a
non clasificado, ou o resto da matriz.

661
00:33:03,225 --> 00:33:05,808
Alguén quere me dar un
liña de código que faría iso?

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

663
00:33:08,870 --> 00:33:11,330
Hint-- o que necesitamos aquí abaixo?

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

665
00:33:17,320 --> 00:33:18,820
O que vai facer no presente para loop?

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

667
00:33:19,465 --> 00:33:21,590
Audiencia: Entón nós quereríamos
teñen un número enteiro diferente,

668
00:33:21,590 --> 00:33:25,080
porque estamos correndo o resto
da matriz en vez do i, quizais por iso

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

670
00:33:25,760 --> 00:33:27,301
>> ANDI Pengo: Si, j soa ben para min.

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

672
00:33:27,850 --> 00:33:33,930
>> Audiencia: Entón sería eu máis 1, porque
está comezando o próximo valor.

673
00:33:33,930 --> 00:33:40,395
E, a continuación, para o end --- novo, j é
menos de n menos 1, e despois j ++.

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

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

676
00:33:48,510 --> 00:33:52,750
>> E, a continuación, aquí, imos querer
comprobar a ver se a nosa condición de ser cumprida,

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

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

679
00:33:55,740 --> 00:33:58,700
se é realmente menor que o que
está comparando-a, non?

680
00:33:58,700 --> 00:34:01,146
Entón, o que imos querer aquí?

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

682
00:34:04,160 --> 00:34:04,897
Comproba a ver.

683
00:34:04,897 --> 00:34:06,730
Que tipo de declaración
estamos probablemente vai

684
00:34:06,730 --> 00:34:08,389
ti quere empregar, se nós
querer comprobar algo?

685
00:34:08,389 --> 00:34:09,360
>> Audiencia: Unha instrución if.

686
00:34:09,360 --> 00:34:10,485
>> ANDI Pengo: Unha instrución if.

687
00:34:10,485 --> 00:34:13,155
Entón se-- eo que será
a condición de que queremos dentro

688
00:34:13,155 --> 00:34:13,988
do noso if?

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

690
00:34:18,255 --> 00:34:22,960
>> Audiencia: O valor de j
é menor que o valor de i--

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

692
00:34:24,600 --> 00:34:27,480
Entón se-- de xeito que este conxunto é chamado de "matriz".

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

694
00:34:27,980 --> 00:34:30,465
Entón, se array-- que foi iso?

695
00:34:30,465 --> 00:34:31,090
Diga iso de novo.

696
00:34:31,090 --> 00:34:39,590
>> Audiencia: Se matriz-j é menor que
matriz-i, entón poderiamos cambiar o min.

697
00:34:39,590 --> 00:34:41,590
Así, a min sería j.

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

699
00:34:44,590 --> 00:34:47,249
>> ANDI Pengo: Isto ten sentido?

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

701
00:34:48,670 --> 00:34:52,929
E agora aquí abaixo, nós, en realidade,
quere aplicar o intercambio, non?

702
00:34:52,929 --> 00:34:58,285
Así recordar, a charla, que David, cando
estaba tentando cambiar as-- o que era

703
00:34:58,285 --> 00:34:59,996
zume de laranxa ele-- e milk--

704
00:34:59,996 --> 00:35:01,150
>> Audiencia: Iso foi gross.

705
00:35:01,150 --> 00:35:02,816
>> ANDI Pengo: Si, iso foi tipo de Gross.

706
00:35:02,816 --> 00:35:05,310
Pero foi unha boa fermosa
concepto demostrando tempo.

707
00:35:05,310 --> 00:35:08,430
Entón, pense de seus valores aquí.

708
00:35:08,430 --> 00:35:10,794
Ten unha matriz
de minutos, unha serie de i,

709
00:35:10,794 --> 00:35:12,460
ou o que estabamos intentando cambiar aquí.

710
00:35:12,460 --> 00:35:15,310
E probablemente non pode derramar-los
entre eles, á vez, a dereita?

711
00:35:15,310 --> 00:35:17,180
Entón, o que imos
a necesidade de crear aquí

712
00:35:17,180 --> 00:35:19,126
a fin de cambiar os valores correctamente?

713
00:35:19,126 --> 00:35:19,820
>> Audiencia: Unha variable temporal.

714
00:35:19,820 --> 00:35:21,370
>> ANDI Pengo: Unha variable temporal.

715
00:35:21,370 --> 00:35:22,570
Entón imos facer int temporal.

716
00:35:22,570 --> 00:35:25,681
Mira, iso sería unha mellor
tempo a-- Whoa, o que foi iso?

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

718
00:35:26,180 --> 00:35:29,800
Polo tanto, esta sería unha mellor
tempo para nomear o "tempo." variable

719
00:35:29,800 --> 00:35:30,730
Entón imos facer int temporal.

720
00:35:30,730 --> 00:35:32,563
Que imos
Definir 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 Pengo: É un pouco complicado.

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

726
00:35:43,110 --> 00:35:44,880
Realmente non importa ao final.

727
00:35:44,880 --> 00:35:47,690
Non importa o que
orde que escoller para intercambiar en

728
00:35:47,690 --> 00:35:50,862
desde que está facendo certo que é
manter o control do que está cambiando.

729
00:35:50,862 --> 00:35:52,250
>> Audiencia: Podería ser gama-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI Pengo: Si, imos facer matriz-i.

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

732
00:35:55,950 --> 00:35:59,305
E entón, cal é a seguinte liña
de código que queremos ter aquí?

733
00:35:59,305 --> 00:36:00,680
Audiencia: array-i é igual a matriz de j.

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

735
00:36:07,154 --> 00:36:08,070
ANDI Pengo: E para rematar?

736
00:36:08,070 --> 00:36:12,070
Audiencia: array-j é igual a matriz-i.

737
00:36:12,070 --> 00:36:14,525
Audiencia: Ou matriz j iguais
matriz de temp-- ou, temporal.

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

739
00:36:17,135 --> 00:36:19,430
>> ANDI Pengo: Aceptar.

740
00:36:19,430 --> 00:36:21,510
Entón, imos realizar este e mira
se está indo para o traballo.

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

742
00:36:37,520 --> 00:36:39,335
Onde é que está a suceder?

743
00:36:39,335 --> 00:36:40,210
Oh, iso é un problema.

744
00:36:40,210 --> 00:36:44,320
Vexa, na liña 40, estamos
intentando usar matriz-j?

745
00:36:44,320 --> 00:36:47,022
Pero onde é que j só existen en?

746
00:36:47,022 --> 00:36:48,402
>> Audiencia: Con loop for.

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

748
00:36:49,110 --> 00:36:51,730
Entón que é o que imos facer?

749
00:36:51,730 --> 00:36:53,170
>> Audiencia: Establecer fóra as--

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

751
00:36:57,777 --> 00:37:00,610
Audiencia: É, eu creo que ten
para usar outra instrución if, non?

752
00:37:00,610 --> 00:37:05,230
Así como, se o minimum--
todo ben, déixeme pensar.

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

754
00:37:08,170 --> 00:37:09,990
>> ANDI Pengo: Caras, proba
para dar un ollo Déixanos

755
00:37:09,990 --> 00:37:11,270
Mira, o que é algo que podemos facer aquí?

756
00:37:11,270 --> 00:37:11,811
>> Audiencia: Aceptar.

757
00:37:11,811 --> 00:37:15,900
Polo tanto, se o mínimo non é igual
j-- así aínda que o mínimo é i--

758
00:37:15,900 --> 00:37:17,570
non teriamos que cambiar.

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

760
00:37:22,450 --> 00:37:24,712
>> ANDI Pengo: Será que a igualdade i?

761
00:37:24,712 --> 00:37:25,920
O que quere dicir aquí?

762
00:37:25,920 --> 00:37:30,494
>> Audiencia: Ou si, se o
mínimo non é igual a min, si.

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

764
00:37:39,627 --> 00:37:40,210
ANDI Pengo: Aceptar.

765
00:37:40,210 --> 00:37:42,040
Ben, iso resolve, tipo, os nosos problemas.

766
00:37:42,040 --> 00:37:47,265
Pero iso non resolve o
problema que acontece se j-- desde j

767
00:37:47,265 --> 00:37:49,890
non existe fóra del, o que
vostede que queremos facer con el?

768
00:37:49,890 --> 00:37:50,698
Declaralo la fóra?

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

770
00:37:59,410 --> 00:38:02,730
Imos tentar executar este.

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

772
00:38:04,435 --> 00:38:06,200
Nosa especie non funciona.

773
00:38:06,200 --> 00:38:10,060
>> Como verás, o noso principal
matriz tiña eses valores.

774
00:38:10,060 --> 00:38:14,800
E despois, debe ter
foi o 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Non funciona.

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

777
00:38:16,030 --> 00:38:17,184
O que imos facer?

778
00:38:17,184 --> 00:38:17,850
Audiencia: Debug.

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

780
00:38:21,787 --> 00:38:23,370
ANDI Pengo: Todo ben, podemos tentar iso.

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

782
00:38:25,030 --> 00:38:26,042
Aumentar un pouco.

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

784
00:38:31,177 --> 00:38:33,656
Imos definir o noso punto de interrupción.

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

786
00:38:37,280 --> 00:38:40,444
>> Entón, por que xa sabemos que
estas liñas, 15 a 22,

787
00:38:40,444 --> 00:38:43,610
son working-- porque todo o que eu estou facendo é
só iterado e printing--

788
00:38:43,610 --> 00:38:45,406
I pode ir adiante e ignorar isto.

789
00:38:45,406 --> 00:38:47,280
Imos comezar na liña 25.

790
00:38:47,280 --> 00:38:48,712
Oop, deixe-me librar diso.

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

792
00:38:51,598 --> 00:38:54,057
>> Audiencia: Entón, desde o punto de interrupción
onde a depuración comeza?

793
00:38:54,057 --> 00:38:54,890
ANDI Pengo: ou para.

794
00:38:54,890 --> 00:38:55,670
Audiencia: ou para.

795
00:38:55,670 --> 00:38:55,930
ANDI Pengo: Si.

796
00:38:55,930 --> 00:38:58,640
Podes establecer varios puntos de interrupción e
pode simplemente saltar dun a outro.

797
00:38:58,640 --> 00:39:01,590
Pero neste caso non sabemos
onde o erro está pasando.

798
00:39:01,590 --> 00:39:03,780
Entón, nós só queremos
comezar de arriba abaixo.

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

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

801
00:39:05,550 --> 00:39:08,460
>> Entón esta liña aquí, podemos intervir.

802
00:39:08,460 --> 00:39:11,499
Podes ver aquí en baixo,
temos unha matriz.

803
00:39:11,499 --> 00:39:13,290
Estes son os valores
que están na matriz.

804
00:39:13,290 --> 00:39:16,360
Ve que, como índice de 0, el
corresponde ao value-- oh,

805
00:39:16,360 --> 00:39:17,526
Vou tentar facer zoom.

806
00:39:17,526 --> 00:39:20,650
Sentímolo, é realmente difícil
para see-- na matriz índice 0,

807
00:39:20,650 --> 00:39:24,090
que ten un valor de 4 e
entón así por diante e así por diante.

808
00:39:24,090 --> 00:39:25,670
Temos as nosas variables locais.

809
00:39:25,670 --> 00:39:28,570
Agora é igual a
0, o que queremos que sexa.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> E así imos seguir percorrendo.

812
00:39:33,690 --> 00:39:36,850
O noso mínima é igual a 0,
que nós tamén queremos que sexa.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
E, entón, entrar no noso segundo para
ciclo, a matriz-j é inferior a matriz-i,

815
00:39:45,560 --> 00:39:46,380
que non era.

816
00:39:46,380 --> 00:39:48,130
Entón, se ves como
que pulou iso?

817
00:39:48,130 --> 00:39:52,430
>> Audiencia: Entón debe ser o caso
mínimo, todo isso-- que non debe

818
00:39:52,430 --> 00:39:55,424
estar dentro do primeiro para o loop?

819
00:39:55,424 --> 00:39:57,340
ANDI Pengo: Non, porque
aínda quere probar.

820
00:39:57,340 --> 00:40:00,329
Quere facer unha comparación cada
tempo, mesmo despois de pasar por ela.

821
00:40:00,329 --> 00:40:02,620
Non só quere facelo
na primeira pasaxe.

822
00:40:02,620 --> 00:40:05,240
Quere facelo con
cada paso adicional de novo.

823
00:40:05,240 --> 00:40:07,198
Entón quere comprobar a
súa condición dentro.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Entón, nós só estamos indo a
continuar executando por aquí.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Vou dar a vostedes unha información.

828
00:40:18,420 --> 00:40:23,910
Ten que ver co feito de que, cando
está comprobando a súa condicional,

829
00:40:23,910 --> 00:40:26,600
non está comprobando
ao índice correcto.

830
00:40:26,600 --> 00:40:32,510
Entón, agora está comprobando a
índice de matriz de j é inferior a matriz

831
00:40:32,510 --> 00:40:33,970
Índice de i.

832
00:40:33,970 --> 00:40:36,580
Pero o que está facendo enriba
o inicio do loop for?

833
00:40:36,580 --> 00:40:38,260
Non está definindo j igual a min?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Si, para que poidamos realmente
saír do depurador aquí.

836
00:40:45,415 --> 00:40:47,040
Entón, imos dar un ollo ao noso pseudocódigo.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- imos
comezan en i é igual a 0.

839
00:40:52,580 --> 00:40:54,760
Estamos indo para ir ata n menos 1.

840
00:40:54,760 --> 00:40:58,040
Imos comprobar si temos ese dereito?

841
00:40:58,040 --> 00:40:59,580
Si, iso era certo.

842
00:40:59,580 --> 00:41:02,080
>> Así, pois, aquí dentro, estamos
vai crear un valor mínimo

843
00:41:02,080 --> 00:41:03,630
e establecer que igual a i.

844
00:41:03,630 --> 00:41:04,950
Será que imos facelo?

845
00:41:04,950 --> 00:41:06,270
Si, fixen iso.

846
00:41:06,270 --> 00:41:10,430
Agora, no noso interior loop for, estamos
vai facer j é igual a i n menos 1.

847
00:41:10,430 --> 00:41:11,950
Será que imos facelo?

848
00:41:11,950 --> 00:41:15,540
En realidade, nós fixemos iso.

849
00:41:15,540 --> 00:41:19,922
>> Entón, con todo, o que estamos comparando aquí?

850
00:41:19,922 --> 00:41:20,925
>> Audiencia: j +1.

851
00:41:20,925 --> 00:41:21,716
ANDI Pengo: Exactamente.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
E entón vai querer definir
o mínimo igual a 1 j máis ben.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Entón eu pase por iso moi rapidamente.

856
00:41:32,640 --> 00:41:36,190
Vostedes entenden
por iso que é j + 1?

857
00:41:36,190 --> 00:41:36,890
Aceptar.

858
00:41:36,890 --> 00:41:40,700
>> Así, na súa matriz, en
súa primeira pasaxe,

859
00:41:40,700 --> 00:41:44,850
o loop for, por int
i é igual a 0, imos só

860
00:41:44,850 --> 00:41:46,740
asumir este non cambiou aínda.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Temos unha matriz de, por completo,
só catro elementos non ordenados, non?

863
00:41:56,760 --> 00:42:00,760
Por iso, queremos iniciar i igual a 0.

864
00:42:00,760 --> 00:42:03,650
E eu vai só
percorrer este loop.

865
00:42:03,650 --> 00:42:08,560
E así na primeira pasaxe, imos
para iniciar unha variable chamada "min"

866
00:42:08,560 --> 00:42:11,245
que tamén é igual a I porque
non temos un valor mínimo.

867
00:42:11,245 --> 00:42:12,870
Entón, iso é actualmente igual a 0 tamén.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
E entón nós imos pasar.

870
00:42:17,640 --> 00:42:19,270
E queremos facer unha iteración novo.

871
00:42:19,270 --> 00:42:22,900
Agora que descubrimos que o noso mínimo
é, queremos para percorrer

872
00:42:22,900 --> 00:42:25,190
de novo para ver se está comparando, non?

873
00:42:25,190 --> 00:42:40,440
Entón, j, aquí, vai
igual a I, o cal é 0.

874
00:42:40,440 --> 00:42:46,320
E, a continuación, a matriz j máis eu, que
é o que é o seguinte máis, como menos

875
00:42:46,320 --> 00:42:49,270
que o seu mínimo actual
valor é, quere cambiar.

876
00:42:49,270 --> 00:42:56,850
>> Entón, imos só dicir que temos
ten, como, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Agora, i é igual a
0 e j é igual a 0.

878
00:43:01,610 --> 00:43:05,210
E ese é o noso valor mínimo.

879
00:43:05,210 --> 00:43:09,950
Se matriz-j máis i-- polo que se o
iso é despois que nós estamos mirando para

880
00:43:09,950 --> 00:43:13,450
é maior que o anterior,
que vai chegar a ser o mínimo.

881
00:43:13,450 --> 00:43:18,120
>> Entón aquí vemos que 5
non é menos que iso.

882
00:43:18,120 --> 00:43:19,730
Entón, que vai non ser 5.

883
00:43:19,730 --> 00:43:23,580
Vemos que 1 sexa inferior a 2, non?

884
00:43:23,580 --> 00:43:32,970
Polo tanto, agora sabemos que o noso mínimo é
será o valor do índice 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Si?

886
00:43:34,030 --> 00:43:39,170
E entón cando chegar aquí,
podes cambiar os valores correctos.

887
00:43:39,170 --> 00:43:42,610
>> Entón, cando vostedes estaban só tendo o j
antes, non estaban mirando para o

888
00:43:42,610 --> 00:43:43,260
despois dela.

889
00:43:43,260 --> 00:43:44,520
Estabas buscando
o mesmo valor, que

890
00:43:44,520 --> 00:43:46,290
É por iso que, sinxelamente, non estaba facendo nada.

891
00:43:46,290 --> 00:43:49,721
Isto ten sentido para todos,
por iso que necesitamos que máis dun alí?

892
00:43:49,721 --> 00:43:50,220
Aceptar.

893
00:43:50,220 --> 00:43:53,345
Agora imos correr con el para facer
seguro de que o resto do código é correcto.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Por que é que pasa?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, é o min aquí.

898
00:44:16,364 --> 00:44:17,780
Que estaban comparando o valor incorrecto.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Oh, non.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Ah, si, aquí nós
trocando os valores errados ben.

903
00:44:33,482 --> 00:44:34,940
Porque estabamos buscando i e j.

904
00:44:34,940 --> 00:44:36,440
Estes son os que foron merecen unha visita.

905
00:44:36,440 --> 00:44:39,160
Nós realmente quere cambiar o
mínimo, o mínimo actual,

906
00:44:39,160 --> 00:44:40,550
co que o exterior é.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
E, como podedes ver a continuación
aquí temos unha matriz clasificada.

909
00:45:05,402 --> 00:45:07,110
El só tiña que ver con
o feito de que cando

910
00:45:07,110 --> 00:45:09,350
estabamos comprobando o
valores que foron comparando,

911
00:45:09,350 --> 00:45:11,226
nós non estabamos mirando para os valores correctos.

912
00:45:11,226 --> 00:45:13,850
Que estaban mirando para a mesma
aquí, non, en realidade, cambiando-lo.

913
00:45:13,850 --> 00:45:17,135
Ten que mirar para un lado
para el e, a continuación, pode cambiar.

914
00:45:17,135 --> 00:45:19,260
Entón é iso que era unha especie de
incomodando noso código antes.

915
00:45:19,260 --> 00:45:22,460
E o que eu fixen aquí é todo
o depurador podería facer para ti

916
00:45:22,460 --> 00:45:23,810
Eu só fixen isto no
tarxeta, porque é máis fácil

917
00:45:23,810 --> 00:45:26,320
para ver en vez de tratar de
para facer zoom e depurador.

918
00:45:26,320 --> 00:45:29,391
Isto ten sentido para todos?

919
00:45:29,391 --> 00:45:29,890
Legal.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Todo ben.

922
00:45:35,410 --> 00:45:41,070
Podemos pasar falar
notación asintótica, que

923
00:45:41,070 --> 00:45:44,580
é só un xeito elegante de dicir o
tempos de execución de todo tipo desas.

924
00:45:44,580 --> 00:45:47,650
Entón eu sei David, en charla,
aflorados tempos de execución.

925
00:45:47,650 --> 00:45:52,124
E pasou por toda a fórmula
de como calcular os tempos de execución.

926
00:45:52,124 --> 00:45:53,040
Non se preocupa con iso.

927
00:45:53,040 --> 00:45:54,660
Se vostede é realmente curioso
sobre como funciona isto,

928
00:45:54,660 --> 00:45:55,810
sexa a vontade para falar comigo despois sección.

929
00:45:55,810 --> 00:45:57,560
Podemos camiñar por
as fórmulas xuntos.

930
00:45:57,560 --> 00:46:00,689
Pero todos vós ten que realmente
sei é que n ao cadrado sobre 2

931
00:46:00,689 --> 00:46:01,980
é o mesmo que n ao cadrado.

932
00:46:01,980 --> 00:46:04,710
Debido ao maior número
o expoñente máis crece.

933
00:46:04,710 --> 00:46:06,590
E así para os nosos propósitos,
todos nos preocupa

934
00:46:06,590 --> 00:46:09,470
é que o número xigante que é evidente.

935
00:46:09,470 --> 00:46:13,340
>> Entón, cal é o mellor caso
runtime de selección tipo?

936
00:46:13,340 --> 00:46:15,830
Se indo para ter
para percorrer unha lista

937
00:46:15,830 --> 00:46:18,712
e entón percorrer
resto da lista,

938
00:46:18,712 --> 00:46:20,420
cantas veces son
vai probablemente

939
00:46:20,420 --> 00:46:24,612
no peor na case--
mellor caso, sorry-- percorrer?

940
00:46:24,612 --> 00:46:27,070
Quizais a mellor pregunta é
para preguntar, o que é o peor caso

941
00:46:27,070 --> 00:46:28,153
runtime de selección de clasificación.

942
00:46:28,153 --> 00:46:29,366
Audiencia: n ao cadrado.

943
00:46:29,366 --> 00:46:30,740
ANDI Pengo: É n ao cadrado, certo.

944
00:46:30,740 --> 00:46:36,986
Entón, un xeito doado de pensar niso é como,
calquera momento ten dúas noutras citas para loops,

945
00:46:36,986 --> 00:46:38,110
que vai ser n ao cadrado.

946
00:46:38,110 --> 00:46:40,386
Porque non só é vostede
que funciona a través de unha vez,

947
00:46:40,386 --> 00:46:42,260
ten que volver
volta e correr con el

948
00:46:42,260 --> 00:46:44,980
unha vez dentro de cada valor.

949
00:46:44,980 --> 00:46:48,640
Entón, nese caso, está executando n
veces n ao cadrado, que é-- sorry,

950
00:46:48,640 --> 00:46:50,505
n veces n, o que equivale n ao cadrado.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> E tipo é tamén un pouco
única no sentido

953
00:46:56,360 --> 00:46:59,774
que non importa se estes
valores xa están en orde.

954
00:46:59,774 --> 00:47:01,440
Aínda vai correr a través de calquera maneira.

955
00:47:01,440 --> 00:47:03,872
Nós só dicir que este foi de 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Independentemente de que estean ou non foi en
fin, aínda tería percorreu

957
00:47:07,080 --> 00:47:08,620
e aínda verificou o valor mínimo.

958
00:47:08,620 --> 00:47:10,100
El faría o
mesmo número de cheques

959
00:47:10,100 --> 00:47:12,780
en cada momento, aínda que
non chegou a tocar nada.

960
00:47:12,780 --> 00:47:16,940
>> Así, en tal caso, o mellor eo peor
tempos de execución son realmente equivalentes.

961
00:47:16,940 --> 00:47:19,160
Así, o tempo de execución espera
selección de tipo,

962
00:47:19,160 --> 00:47:23,790
que designamos polo símbolo
de teta, teta, neste caso,

963
00:47:23,790 --> 00:47:24,790
tamén sería n ao cadrado.

964
00:47:24,790 --> 00:47:26,480
Os tres destes serían n ao cadrado.

965
00:47:26,480 --> 00:47:29,653
Claro que todos de por
o tempo de execución é n ao cadrado?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Todo ben.

968
00:47:33,980 --> 00:47:39,120
Entón, eu estou indo só para executar rapidamente
polo resto das sortes.

969
00:47:39,120 --> 00:47:41,137
O algoritmo para
burbulla sort-- lembre,

970
00:47:41,137 --> 00:47:43,220
este foi o primeiro
David, pasando en charla.

971
00:47:43,220 --> 00:47:46,000
Esencialmente, pisa
a listaxe

972
00:47:46,000 --> 00:47:48,950
e swap-- só
comparar dous á vez.

973
00:47:48,950 --> 00:47:51,350
E se un é maior,
que acaba de trocalos.

974
00:47:51,350 --> 00:47:53,590
Entón, se estes son grandes, vostede trocaría.

975
00:47:53,590 --> 00:47:56,180
Teño oficial aquí.

976
00:47:56,180 --> 00:47:59,100
>> Entón, imos só dicir que tiña 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Ía comparar a 8 e un 6.

978
00:48:00,571 --> 00:48:01,570
Necesitará trocalos.

979
00:48:01,570 --> 00:48:02,610
Podería comparar a 8 e un 4.

980
00:48:02,610 --> 00:48:03,609
Necesitará trocalos.

981
00:48:03,609 --> 00:48:07,000
Se ten que trocar a 8 e
2, cambia-los tamén.

982
00:48:07,000 --> 00:48:10,760
Así, en tal sentido, verás,
vai fóra ao longo dun longo período de tempo,

983
00:48:10,760 --> 00:48:13,730
como o tipo de burbulla de valores
os extremos, o que é por iso que chamamos

984
00:48:13,730 --> 00:48:15,320
bubble sort.

985
00:48:15,320 --> 00:48:19,950
>> Nós só ía percorrer de novo en
nosa segunda pasaxe, ea nosa terceira paso,

986
00:48:19,950 --> 00:48:21,150
ea nosa cuarta pasaxe.

987
00:48:21,150 --> 00:48:25,820
Esencialmente, bubble sort só corre
ata que non facer máis swaps.

988
00:48:25,820 --> 00:48:31,109
Entón, nese sentido, este é só
o pseudocódigo xeral para el.

989
00:48:31,109 --> 00:48:32,650
Non te preocupes, estes serán todos liña.

990
00:48:32,650 --> 00:48:34,990
Non temos que ir realmente sobre iso.

991
00:48:34,990 --> 00:48:38,134
>> Nós só arrincar un contador
variable que comeza en 0.

992
00:48:38,134 --> 00:48:39,800
E nós iterado a través de toda a matriz.

993
00:48:39,800 --> 00:48:43,420
E se un valor é-- este
valor é maior que aquel valor,

994
00:48:43,420 --> 00:48:44,610
está indo para trocalos.

995
00:48:44,610 --> 00:48:46,860
E entón é só
continuará.

996
00:48:46,860 --> 00:48:47,970
E está indo a contar.

997
00:48:47,970 --> 00:48:50,845
E está indo só para seguir facendo
este mentres o contador é maior

998
00:48:50,845 --> 00:48:53,345
a 0, o que significa que
cada vez que ten que cambiar,

999
00:48:53,345 --> 00:48:55,220
vostede sabe que quere ir
cara atrás e comprobar de novo.

1000
00:48:55,220 --> 00:48:59,510
Quere manter a verificación ata que vostede sabe
que non ten que cambiar máis.

1001
00:48:59,510 --> 00:49:05,570
>> Entón, cales son os mellores e peores
caso tempos de execución para bubble sort?

1002
00:49:05,570 --> 00:49:09,300
E hint-- esta é realmente diferente
tipo de selección no sentido

1003
00:49:09,300 --> 00:49:11,810
que estas dúas respostas non son os mesmos.

1004
00:49:11,810 --> 00:49:14,709
Pense sobre o que acontecería en
un caso, se xa foi resolto.

1005
00:49:14,709 --> 00:49:16,500
E pensar sobre o que
que acontecería se fose

1006
00:49:16,500 --> 00:49:18,372
no caso de que non foi resolto.

1007
00:49:18,372 --> 00:49:20,580
E pode tipo de correr
través de por que isto está a suceder.

1008
00:49:20,580 --> 00:49:22,954
Vou dar a vostedes, tipo, 30
segundos para pensar sobre iso.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> Aceptar.

1011
00:49:53,540 --> 00:49:57,462
Alguén ten un palpite sobre o que o
peor caso de tempo de execución de bubble sort é?

1012
00:49:57,462 --> 00:49:57,962
Si.

1013
00:49:57,962 --> 00:50:07,810
>> Audiencia: sería, como, n veces
n menos 1 ou algo así?

1014
00:50:07,810 --> 00:50:10,650
Como cada vez que se executa,
é só como un intercambio de menos

1015
00:50:10,650 --> 00:50:10,960
que quere que fose.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI Pengo: Si, entón
está totalmente certo.

1017
00:50:12,668 --> 00:50:15,940
E este é un caso en que a súa
resposta foi realmente máis complexo

1018
00:50:15,940 --> 00:50:17,240
que o que ten que dar.

1019
00:50:17,240 --> 00:50:19,772
Entón vai para run-- son
vai borrar todo isto aquí.

1020
00:50:19,772 --> 00:50:20,480
Está todo o mundo ben?

1021
00:50:20,480 --> 00:50:21,869
Podo borrar isto?

1022
00:50:21,869 --> 00:50:22,368
Aceptar.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Vai percorrer n
veces por primeira vez, non?

1025
00:50:30,320 --> 00:50:33,200
E eles están indo a ser executado a través
n menos 1 segundo tempo, non?

1026
00:50:33,200 --> 00:50:37,130
E entón está indo a mantê-
indo, n mina 2, etcétera.

1027
00:50:37,130 --> 00:50:40,210
David fixo nunha charla, onde,
se engadiu-se todos estes valores,

1028
00:50:40,210 --> 00:50:48,080
comeza algo que é como-- yeah--
máis de 2, que, esencialmente, só reduce

1029
00:50:48,080 --> 00:50:49,784
ata n ao cadrado.

1030
00:50:49,784 --> 00:50:51,700
Está indo a obter un
fracción estraño dentro.

1031
00:50:51,700 --> 00:50:53,892
E así só sei que
a n ao cadrado sempre

1032
00:50:53,892 --> 00:50:55,350
ten precedencia sobre a fracción.

1033
00:50:55,350 --> 00:50:58,450
E así, neste caso, o peor
tempo de execución sería n ao cadrado.

1034
00:50:58,450 --> 00:51:00,210
Se fose descendente
fin, pense, vostede

1035
00:51:00,210 --> 00:51:02,530
Ten que facer un intercambio de cada vez.

1036
00:51:02,530 --> 00:51:05,170
>> Cal sería, potencialmente,
o mellor caso de tempo de execución?

1037
00:51:05,170 --> 00:51:08,580
Nós só dicir que, se a lista xa foi
en orde, o que podería ser o tempo de execución?

1038
00:51:08,580 --> 00:51:09,565
>> Audiencia: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI Pengo: É n, exactamente.

1040
00:51:10,690 --> 00:51:11,600
E por que é n?

1041
00:51:11,600 --> 00:51:13,850
Audiencia: Porque só
ten que comprobar en cada vez.

1042
00:51:13,850 --> 00:51:14,770
ANDI Pengo: Exactamente.

1043
00:51:14,770 --> 00:51:17,150
Así, no mellor execución posible,
se esta lista xa foi

1044
00:51:17,150 --> 00:51:20,270
sorted-- digamos 1, 2, 3, 4-- vostede
sería só pasar, que ía comprobar,

1045
00:51:20,270 --> 00:51:21,720
ía ver, oh, todos eles pan out.

1046
00:51:21,720 --> 00:51:22,636
Eu non tiven que cambiar.

1047
00:51:22,636 --> 00:51:23,370
Rematei.

1048
00:51:23,370 --> 00:51:26,500
Entón, nese caso, é só n
ou o número de pasos que acaba

1049
00:51:26,500 --> 00:51:29,870
tiña que comprobar na primeira lista.

1050
00:51:29,870 --> 00:51:33,990
>> E despois, xa alcanzou
tipo de inserción, onde

1051
00:51:33,990 --> 00:51:39,260
o algoritmo é esencialmente a dividir
Lo nunha parte clasificada e indiferenciados.

1052
00:51:39,260 --> 00:51:42,810
E a continuación, un por un,
os valores son indiferenciados

1053
00:51:42,810 --> 00:51:46,880
inserida na súa axeitada
posicións no inicio da lista.

1054
00:51:46,880 --> 00:51:52,120
>> Así, por exemplo, temos unha
Lista de 3, 5, 2, 6, 4 de novo.

1055
00:51:52,120 --> 00:51:54,750
Sabemos que é actualmente
indiferenciados porque temos só

1056
00:51:54,750 --> 00:51:57,030
comecei a ollar para el.

1057
00:51:57,030 --> 00:52:00,610
Imos dar un ollo e sabemos que
o primeiro valor é ordenada, non?

1058
00:52:00,610 --> 00:52:04,190
Se vostede está só mirando para unha variedade de
tamaño un, xa sabe que está clasificada.

1059
00:52:04,190 --> 00:52:08,230
>> Entón sabemos que o
outros catro son indiferenciados.

1060
00:52:08,230 --> 00:52:10,980
Pasamos por e vemos ese valor.

1061
00:52:10,980 --> 00:52:11,730
Imos volver.

1062
00:52:11,730 --> 00:52:13,130
Mira que o valor de 5?

1063
00:52:13,130 --> 00:52:14,110
Imos dar un ollo niso.

1064
00:52:14,110 --> 00:52:15,204
Nós comparalos-lo a 3.

1065
00:52:15,204 --> 00:52:17,870
Sabemos que é maior que
3, polo que sabemos que isto está clasificado.

1066
00:52:17,870 --> 00:52:22,940
Polo tanto, sabemos que os dous primeiros
son clasificadas e os tres últimos non son.

1067
00:52:22,940 --> 00:52:24,270
>> Imos dar un ollo a dous.

1068
00:52:24,270 --> 00:52:25,720
Primeiro imos comprobar iso con cinco.

1069
00:52:25,720 --> 00:52:26,700
É menos que 5?

1070
00:52:26,700 --> 00:52:27,240
Non é.

1071
00:52:27,240 --> 00:52:29,510
Entón temos que estar mirando cara a abaixo.

1072
00:52:29,510 --> 00:52:30,940
A continuación, comprobar 2 off 3.

1073
00:52:30,940 --> 00:52:31,850
É menos que?

1074
00:52:31,850 --> 00:52:32,350
Non.

1075
00:52:32,350 --> 00:52:35,430
Entón, vostede sabe a 2 ten que ser inserido
na parte de diante e 3 e 5

1076
00:52:35,430 --> 00:52:38,200
ambos teñen que ser empurrados para fóra.

1077
00:52:38,200 --> 00:52:42,190
Faino novo con 6 e 4.

1078
00:52:42,190 --> 00:52:48,962
E nós só manter a verificación, esencialmente,
onde pode comprobar, comprobación, verificación.

1079
00:52:48,962 --> 00:52:51,170
E ata que sexa na dereita
posición, que tipo de só

1080
00:52:51,170 --> 00:52:54,890
introduza o na posición correcta,
que é onde o nome veu.

1081
00:52:54,890 --> 00:52:59,830
>> Entón, iso é só o algoritmo,
pseudocódigo per se, tipo,

1082
00:52:59,830 --> 00:53:04,990
en como iríamos aplicar
un tipo de inserción.

1083
00:53:04,990 --> 00:53:05,954
Pseudocódigo é aquí.

1084
00:53:05,954 --> 00:53:06,620
É todo en liña.

1085
00:53:06,620 --> 00:53:10,720
Non te preocupes se vostedes son
intentando copiar este abaixo.

1086
00:53:10,720 --> 00:53:14,500
Entón unha vez máis, aínda que question--
sería a mellor e peor tempos de execución

1087
00:53:14,500 --> 00:53:16,120
para inserción tipo?

1088
00:53:16,120 --> 00:53:17,750
É moi semellante á última pregunta.

1089
00:53:17,750 --> 00:53:20,479
Vou dar a vostedes, tipo, 30
segundos para pensar sobre iso tamén.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> Aceptar Alguén quere
dáme o peor tempo de execución?

1092
00:53:50,071 --> 00:53:50,570
Si.

1093
00:53:50,570 --> 00:53:51,490
>> Audiencia: n ao cadrado.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI Pengo: É n ao cadrado.

1095
00:53:52,573 --> 00:53:53,730
E por que n ao cadrado?

1096
00:53:53,730 --> 00:53:57,562
>> Audiencia: Porque en
orde inversa, ten

1097
00:53:57,562 --> 00:54:02,619
pasar por n veces n, que é--

1098
00:54:02,619 --> 00:54:03,660
ANDI Pengo: Si, exactamente.

1099
00:54:03,660 --> 00:54:06,610
Entón, aínda que na bubble sort.

1100
00:54:06,610 --> 00:54:08,720
Se esta lista está
orde decrecente, es

1101
00:54:08,720 --> 00:54:11,240
terá que comprobar primeiro posto.

1102
00:54:11,240 --> 00:54:13,470
E, a continuación, con toda
valor adicional, está

1103
00:54:13,470 --> 00:54:16,390
terá que comprobar se contra
cada valor único, non?

1104
00:54:16,390 --> 00:54:20,290
E así por completo, está indo facer
un n veces pasar outro n pasou, e que

1105
00:54:20,290 --> 00:54:21,750
n é cadrado.

1106
00:54:21,750 --> 00:54:22,860
E sobre o mellor caso?

1107
00:54:22,860 --> 00:54:24,360
Si.

1108
00:54:24,360 --> 00:54:28,840
>> Audiencia: n menos 1, xa que o
primeiro xa é elevado ao cadrado.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI Pengo: Entón, pechar.

1110
00:54:30,270 --> 00:54:31,850
A resposta é, en realidade, n.

1111
00:54:31,850 --> 00:54:37,189
Porque mentres a primeira é
clasificadas, non pode Actually --- lo

1112
00:54:37,189 --> 00:54:38,980
nós só tivemos sorte, en
Nese exemplo que dous

1113
00:54:38,980 --> 00:54:40,930
pasou a ser o menor número.

1114
00:54:40,930 --> 00:54:43,680
Pero isto non sempre será así.

1115
00:54:43,680 --> 00:54:48,040
Se 2 xa está clasificado no inicio
pero mira e hai un un aquí,

1116
00:54:48,040 --> 00:54:49,144
o 1 vai bater-lo.

1117
00:54:49,144 --> 00:54:51,060
E iso vai acabar
sendo chocar de calquera maneira.

1118
00:54:51,060 --> 00:54:56,250
>> Así, no mellor dos casos,
é realmente só vai ser n.

1119
00:54:56,250 --> 00:54:59,090
Se ten 1, 2, 3,
4, 5, 6, 7, 8, está

1120
00:54:59,090 --> 00:55:00,940
vai percorrer
que lista enteira xa

1121
00:55:00,940 --> 00:55:03,430
para comprobar a ver se está todo ben.

1122
00:55:03,430 --> 00:55:07,390
Claro que todos na carreira
tempos de selección tamén?

1123
00:55:07,390 --> 00:55:09,960
Sei que estou pasando
estes realmente rápido.

1124
00:55:09,960 --> 00:55:13,330
Pero só sei que se sabe o
conceptos xerais, ten que ser bo.

1125
00:55:13,330 --> 00:55:16,070
Aceptar.

1126
00:55:16,070 --> 00:55:19,790
Entón eu vou dar a vostedes quizais, como,
un minuto para falar cos seus veciños

1127
00:55:19,790 --> 00:55:21,890
sobre o que son só algunhas
das principais diferenzas

1128
00:55:21,890 --> 00:55:23,540
entre estes tipos de tipos.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Nós falaremos sobre iso en breve.

1131
00:56:25,570 --> 00:56:26,444
Audiencia: Oh, Aceptar.

1132
00:56:26,444 --> 00:56:27,320
ANDI Pengo: Si.

1133
00:56:27,320 --> 00:56:28,380
Aceptar.

1134
00:56:28,380 --> 00:56:33,420
Cool, imos reunir de novo coa clase.

1135
00:56:33,420 --> 00:56:34,330
Aceptar.

1136
00:56:34,330 --> 00:56:37,579
Polo tanto, este foi un tipo de
pregunta aberta cara

1137
00:56:37,579 --> 00:56:39,120
que hai moitas respostas a elas.

1138
00:56:39,120 --> 00:56:40,746
E nós imos pasar por riba de algúns deles brevemente.

1139
00:56:40,746 --> 00:56:43,411
Eu só quería que obteña caras
pensar sobre o que diferenciou

1140
00:56:43,411 --> 00:56:44,530
os tres tipos de tipos.

1141
00:56:44,530 --> 00:56:47,440
E oín, tamén, unha gran
question-- o que merge sort facer?

1142
00:56:47,440 --> 00:56:50,110
Boa pregunta, porque iso
o que estamos cubrindo seguinte.

1143
00:56:50,110 --> 00:56:52,850
>> Así é o merge sort
un tipo que funciona

1144
00:56:52,850 --> 00:56:56,100
moi diferente dos outros tipos.

1145
00:56:56,100 --> 00:56:58,180
Como podedes see--
David fixo aquela demo

1146
00:56:58,180 --> 00:57:01,130
onde tiña todo o legal
ruídos de ver como mesturar

1147
00:57:01,130 --> 00:57:04,010
tipo foi, como, infinitamente
máis rápido que os outros dous tipos?

1148
00:57:04,010 --> 00:57:04,510
Aceptar.

1149
00:57:04,510 --> 00:57:07,580
Entón, iso é debido a fusión
tipo aplica esa división

1150
00:57:07,580 --> 00:57:11,020
e conquistar concepto que temos
falou sobre unha morea na charla.

1151
00:57:11,020 --> 00:57:14,550
Neste sentido que nos gusta de traballar
máis intelixente, non máis difícil, cando divide

1152
00:57:14,550 --> 00:57:18,120
e conquistar problemas, e rompe-las
abaixo, e, a continuación, poñelos xuntos,

1153
00:57:18,120 --> 00:57:19,930
cousas boas sempre acontecen.

1154
00:57:19,930 --> 00:57:21,960
>> Así, a forma que se funden
tipo esencialmente funciona

1155
00:57:21,960 --> 00:57:24,660
é que divide un
matriz sen clasificar á metade.

1156
00:57:24,660 --> 00:57:26,500
E entón el ten dúas metades de matrices.

1157
00:57:26,500 --> 00:57:28,220
E só clasifica estas dúas metades.

1158
00:57:28,220 --> 00:57:31,750
El só segue dividindo á metade, en
metade, polo medio ata que todo está clasificada

1159
00:57:31,750 --> 00:57:33,680
e, a continuación, de forma recursiva
pon todo iso xunto.

1160
00:57:33,680 --> 00:57:36,550
>> Entón iso é moi abstracto.

1161
00:57:36,550 --> 00:57:38,750
Polo tanto, este é só un pouco de pseudocódigo.

1162
00:57:38,750 --> 00:57:41,040
Isto ten sentido en
o xeito no que está en execución?

1163
00:57:41,040 --> 00:57:43,870
Entón, imos só dicir que ten un
matriz de n elementos, non?

1164
00:57:43,870 --> 00:57:45,450
Se n é inferior a 2, pode voltar.

1165
00:57:45,450 --> 00:57:49,040
Porque sabe que, se hai
só unha cousa, debe ser clasificado.

1166
00:57:49,040 --> 00:57:52,600
Senón, clasificar a metade esquerda,
e entón clasificar a metade dereita,

1167
00:57:52,600 --> 00:57:54,140
e entón fundirse.

1168
00:57:54,140 --> 00:57:56,979
>> Así, mentres que parece realmente fácil,
en realidade, a pensar que é

1169
00:57:56,979 --> 00:58:00,270
tipo de difícil. Porque é como,
ben, este é o tipo de execución en si.

1170
00:58:00,270 --> 00:58:00,769
Non?

1171
00:58:00,769 --> 00:58:02,430
Funciona en si.

1172
00:58:02,430 --> 00:58:05,479
Entón, nese sentido, David tocou
sobre a recursividade en clase.

1173
00:58:05,479 --> 00:58:07,270
E iso é un concepto
imos falar máis.

1174
00:58:07,270 --> 00:58:11,430
É que este, estas dúas liñas
aquí, en realidade, é só o programa

1175
00:58:11,430 --> 00:58:13,860
dicindo que sexa executado en si
con entrada diferente.

1176
00:58:13,860 --> 00:58:17,230
Entón en vez de executar-se con
a totalidade de n elementos,

1177
00:58:17,230 --> 00:58:20,530
pode rompe-lo para abaixo na
metade esquerda e metade dereita

1178
00:58:20,530 --> 00:58:22,680
e, a continuación, executa-lo de novo.

1179
00:58:22,680 --> 00:58:26,050
>> E entón nós imos ollalo visualmente,
porque son un aprendiz visual.

1180
00:58:26,050 --> 00:58:27,270
Funciona mellor para min.

1181
00:58:27,270 --> 00:58:29,890
Entón, imos ollar para un exemplo visual aquí.

1182
00:58:29,890 --> 00:58:36,237
>> Imos dicir que temos unha matriz, seis
elementos, 3, 5, 2, 6, 4, 1, non clasificados.

1183
00:58:36,237 --> 00:58:37,820
Todo ben, hai moita cousa nesta páxina.

1184
00:58:37,820 --> 00:58:43,179
Entón, se podedes mirar o
primeiro paso aquí, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
podes división lo ao medio.

1186
00:58:44,220 --> 00:58:45,976
Ten 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Vostede sabe que estes aren't-- vostede
Non sei se eles están ou non clasificados,

1188
00:58:48,850 --> 00:58:52,517
para que manteña dobres-as, polo medio,
no medio, á metade, ata que finalmente,

1189
00:58:52,517 --> 00:58:53,600
só ten un elemento.

1190
00:58:53,600 --> 00:58:56,790
E un elemento sempre clasificada, non?

1191
00:58:56,790 --> 00:59:01,560
>> Entón, nós sabemos que 3, 5, 2, 4, 6,
1, por si só, son clasificadas.

1192
00:59:01,560 --> 00:59:05,870
E agora podemos xunto a eles de novo.

1193
00:59:05,870 --> 00:59:07,510
Entón, nós sabemos a 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Poñemos estes xuntos.

1195
00:59:08,510 --> 00:59:09,617
Sabemos que é clasificada.

1196
00:59:09,617 --> 00:59:10,450
Os 2 aínda está alí.

1197
00:59:10,450 --> 00:59:11,830
Podemos poñer o 4 eo 6 xuntos.

1198
00:59:11,830 --> 00:59:13,996
Sabemos que isto está clasificado,
por iso, poñer isto en conxunto.

1199
00:59:13,996 --> 00:59:14,940
E a 1 existe.

1200
00:59:14,940 --> 00:59:18,720
>> E entón simplemente ollar para
estas dúas metades dereita aquí.

1201
00:59:18,720 --> 00:59:21,300
Ten a 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Pode simplemente comparar o
comezo de todo.

1203
00:59:23,465 --> 00:59:26,340
Porque sabe que isto é separado
e vostede sabe que isto está clasificado.

1204
00:59:26,340 --> 00:59:29,360
Entón non ten que mesmo
comparar a 5, que acaba de comparar a 3.

1205
00:59:29,360 --> 00:59:32,070
E o 2 é inferior a 3, así
vostede sabe que 2 debe ir ao final.

1206
00:59:32,070 --> 00:59:33,120
>> O mesmo por alí.

1207
00:59:33,120 --> 00:59:34,740
A 1 debe ir aquí.

1208
00:59:34,740 --> 00:59:37,330
E entón, cando vai para poñer
estes dous valores,

1209
00:59:37,330 --> 00:59:39,950
vostede sabe que isto é separado e
vostede sabe que que está clasificada.

1210
00:59:39,950 --> 00:59:43,240
Entón a 1 eo
2, o 1 sexa inferior a 2.

1211
00:59:43,240 --> 00:59:45,570
Isto dille que o 1
debe percorrer a finais desta

1212
00:59:45,570 --> 00:59:47,480
sen sequera ollar para 3 ou 5.

1213
00:59:47,480 --> 00:59:50,100
E entón a 4, pode só
vaia, que vai cara a dereita aquí.

1214
00:59:50,100 --> 00:59:51,480
Non ten que mirar para o 5.

1215
00:59:51,480 --> 00:59:52,570
Mesmo co 6.

1216
00:59:52,570 --> 00:59:55,860
Vostede sabe que a 6-- só
Non ten que ser ollado.

1217
00:59:55,860 --> 00:59:57,870
>> E así, desa forma, é
salvándose só

1218
00:59:57,870 --> 00:59:59,526
unha morea de pasos cando está comparando.

1219
00:59:59,526 --> 01:00:02,150
Non ten que comparar cada
elemento contra outros elementos.

1220
01:00:02,150 --> 01:00:05,230
Só comparar contra os
que precisa para comparar contra.

1221
01:00:05,230 --> 01:00:06,870
Entón, ese é o tipo de un concepto abstracto.

1222
01:00:06,870 --> 01:00:10,540
Non te preocupes se non é
bastante baterlle aínda dereita.

1223
01:00:10,540 --> 01:00:14,740
Pero, xeralmente, este é
como unha especie de fusión funciona.

1224
01:00:14,740 --> 01:00:17,750
Preguntas, preguntas rápidas,
antes de seguir adiante?

1225
01:00:17,750 --> 01:00:18,550
Si.

1226
01:00:18,550 --> 01:00:22,230
>> Audiencia: Entón dixo que se toma
a 1, e logo a 4, eo 6

1227
01:00:22,230 --> 01:00:23,860
e poñer-los en.

1228
01:00:23,860 --> 01:00:26,800
Polo tanto, non son non son those--
ollar para eles

1229
01:00:26,800 --> 01:00:28,544
como elementos separados, e non como o todo?

1230
01:00:28,544 --> 01:00:29,210
ANDI Pengo: Si.

1231
01:00:29,210 --> 01:00:32,020
Entón, o que está pasando
é que, basicamente,

1232
01:00:32,020 --> 01:00:33,650
está creando unha nova matriz.

1233
01:00:33,650 --> 01:00:36,690
Entón vostede sabe que, aquí, eu teño
dúas matrices de tamaño 3, non?

1234
01:00:36,690 --> 01:00:39,600
Entón, vostede sabe que a miña matriz clasificada
ten que ter seis elementos.

1235
01:00:39,600 --> 01:00:42,270
Entón acaba de crear unha
nova cantidade de memoria.

1236
01:00:42,270 --> 01:00:44,270
Entón é tipo como de
sendo unha perda de memoria,

1237
01:00:44,270 --> 01:00:46,186
pero iso non importa
porque é tan pequeno.

1238
01:00:46,186 --> 01:00:48,590
Entón mira para o 1
e mira para o 2.

1239
01:00:48,590 --> 01:00:50,770
E vostede sabe que o 1 sexa inferior a 2.

1240
01:00:50,770 --> 01:00:53,840
Entón vostede sabe que un debe ir
o inicio de todo isto.

1241
01:00:53,840 --> 01:00:55,850
>> Non precisa aínda de
ollar para a 3 e 5 a.

1242
01:00:55,850 --> 01:00:57,400
Entón vostede sabe que un vai alí.

1243
01:00:57,400 --> 01:00:59,300
Entón basicamente cortar a 1.

1244
01:00:59,300 --> 01:01:00,370
É, tipo, morto para nós.

1245
01:01:00,370 --> 01:01:03,690
Entón só temos 2,
3, 5, e, a continuación, 4 e 6.

1246
01:01:03,690 --> 01:01:06,270
E entón vostede sabe que,
comparar a 4 ea 2,

1247
01:01:06,270 --> 01:01:07,560
Oh, o 2 debe ir máis alá.

1248
01:01:07,560 --> 01:01:09,685
Entón plop a 2 para abaixo, corte-lo.

1249
01:01:09,685 --> 01:01:12,060
Entón, polo que só ten a 3
eo 5 no 4 e 6 a.

1250
01:01:12,060 --> 01:01:14,650
E continúa cortando-off
ata que colocalos na matriz.

1251
01:01:14,650 --> 01:01:17,110
>> Audiencia: Entón é só sempre
comparando o [inaudível]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI Pengo: Exactamente.

1253
01:01:17,710 --> 01:01:19,590
Entón, nese sentido, é
só comparando, esencialmente,

1254
01:01:19,590 --> 01:01:21,240
un número contra o outro número.

1255
01:01:21,240 --> 01:01:22,990
E porque sabe
que está clasificada, vostede

1256
01:01:22,990 --> 01:01:24,350
Non ten que ollar a través de
todos os números.

1257
01:01:24,350 --> 01:01:25,870
Vostede só ten que ollar para o primeiro.

1258
01:01:25,870 --> 01:01:27,582
E entón podes só plop
Los abaixo, porque sabe

1259
01:01:27,582 --> 01:01:29,640
pertencen a onde se deben de pertencer.

1260
01:01:29,640 --> 01:01:31,030
Si.

1261
01:01:31,030 --> 01:01:32,920
Boa pregunta.

1262
01:01:32,920 --> 01:01:35,290
>> E, a continuación, se algún de vós
son un pouco ambicioso,

1263
01:01:35,290 --> 01:01:38,660
Sinto-se a liberdade de ollar para este código.

1264
01:01:38,660 --> 01:01:40,680
Esta é realmente a
implantación física

1265
01:01:40,680 --> 01:01:42,150
de como ía escribir merge sort.

1266
01:01:42,150 --> 01:01:44,070
E podes ver, é moi curto.

1267
01:01:44,070 --> 01:01:46,310
Pero as ideas detrás
que son moi complexas.

1268
01:01:46,310 --> 01:01:50,865
Entón, se pensas vontade de deseñar iso
na súa lección de casa esta noite, Sinto-se libre para.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> Aceptar.

1271
01:01:54,740 --> 01:01:58,070
Entón David tamén pasou por iso na charla.

1272
01:01:58,070 --> 01:02:00,660
O que é o mellor caso
tempos de execución, peores tempos de execución de caso,

1273
01:02:00,660 --> 01:02:05,680
e os tempos de execución esperadas merge sort?

1274
01:02:05,680 --> 01:02:07,260
Un par de segundos para pensar.

1275
01:02:07,260 --> 01:02:11,198
Iso é moi difícil, pero o tipo de
intuitiva se pensar sobre iso.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Todo ben.

1278
01:02:23,054 --> 01:02:25,269
>> Audiencia: É o peor caso n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI Pengo: Exactamente.

1280
01:02:26,060 --> 01:02:29,380
E por que é n log n.

1281
01:02:29,380 --> 01:02:32,230
>> Audiencia: Non é porque
faise máis rápido de forma exponencial,

1282
01:02:32,230 --> 01:02:35,390
polo que é como unha función que
en vez de simplemente ser n

1283
01:02:35,390 --> 01:02:37,529
cadrado ou algo así?

1284
01:02:37,529 --> 01:02:38,320
ANDI Pengo: Exactamente.

1285
01:02:38,320 --> 01:02:40,750
Así, a razón pola que o
runtime sobre iso é log n

1286
01:02:40,750 --> 01:02:44,310
n é porque-- o que é vostede
facendo en todos estes pasos de?

1287
01:02:44,310 --> 01:02:46,190
Só está cortando-o ao medio, non?

1288
01:02:46,190 --> 01:02:48,750
E así, cando estamos facendo o
rexistro, todo o que está facendo

1289
01:02:48,750 --> 01:02:53,150
está dividindo un problema no medio,
polo medio, na metade, en máis metades.

1290
01:02:53,150 --> 01:02:56,430
E, nese sentido, pode tipo
de eliminar o modelo lineal

1291
01:02:56,430 --> 01:02:57,510
que temos que chegou a empregar.

1292
01:02:57,510 --> 01:03:00,254
Porque cando chop
cousas pola metade, é un rexistro.

1293
01:03:00,254 --> 01:03:02,420
Isto é só a matemática
xeito de representalo.

1294
01:03:02,420 --> 01:03:06,310
>> E entón, finalmente, ao final, é
só facendo unha última pasaxe

1295
01:03:06,310 --> 01:03:07,930
para poñer todos eles en orde, non?

1296
01:03:07,930 --> 01:03:10,330
E por iso, se só ten que
comprobar unha cousa, que é n.

1297
01:03:10,330 --> 01:03:13,420
E entón está tipo de
multiplicando os dous xuntos.

1298
01:03:13,420 --> 01:03:17,660
Entón, é como ten que Final
vaia n abaixo aquí cun rexistro de n

1299
01:03:17,660 --> 01:03:18,390
aquí enriba.

1300
01:03:18,390 --> 01:03:21,060
E se multiplicar
eles, que é n log n.

1301
01:03:21,060 --> 01:03:26,100
>> E así o mellor eo peor caso
caso e espera son todos n log n.

1302
01:03:26,100 --> 01:03:27,943
Tamén como outro tipo.

1303
01:03:27,943 --> 01:03:30,090
É como especie selección
no sentido de que

1304
01:03:30,090 --> 01:03:32,131
Non importa o que o seu
lista é, el só vai

1305
01:03:32,131 --> 01:03:34,801
para facer o mesmo en cada momento.

1306
01:03:34,801 --> 01:03:35,300
Aceptar.

1307
01:03:35,300 --> 01:03:39,950
Entón, como podedes ver, aínda que
tipo que temos ido through-- n

1308
01:03:39,950 --> 01:03:41,660
cadrado, non é moi eficiente.

1309
01:03:41,660 --> 01:03:47,060
E mesmo ese log n n é
non é o máis eficiente.

1310
01:03:47,060 --> 01:03:49,720
Se vostedes son curiosos,
hai mecanismos de ordenación

1311
01:03:49,720 --> 01:03:54,310
que son tan eficaces que son
case esencialmente plana en tempo de execución.

1312
01:03:54,310 --> 01:03:55,420
>> Ten un pouco de rexistro n.

1313
01:03:55,420 --> 01:03:58,190
Ten algunha rexistro log n de.

1314
01:03:58,190 --> 01:04:00,330
Non toque sobre eles
nesta clase agora.

1315
01:04:00,330 --> 01:04:02,663
Pero se vostedes están curiosos,
Sinto-se libre para Google, o que é

1316
01:04:02,663 --> 01:04:04,392
os mecanismos de selección máis eficientes.

1317
01:04:04,392 --> 01:04:06,350
Non sei, hai
algúns realmente divertido,

1318
01:04:06,350 --> 01:04:09,860
como-- hai algúns realmente
máis divertido que as persoas fan.

1319
01:04:09,860 --> 01:04:12,210
E quere saber como
Nunca pensei niso.

1320
01:04:12,210 --> 01:04:15,730
Entón, Google, se ten algunha reposición
tempo, en, cales son algunhas formas divertidas

1321
01:04:15,730 --> 01:04:17,730
que así como pessoas--
eficientes persoas ways--

1322
01:04:17,730 --> 01:04:20,371
foron capaces de aplicar os tipos.

1323
01:04:20,371 --> 01:04:20,870
Aceptar.

1324
01:04:20,870 --> 01:04:22,880
E aquí está un pouco gráfico útil.

1325
01:04:22,880 --> 01:04:26,850
Sei que todos vostedes, antes de que proba 0,
estará no seu cuarto, probablemente, intentando

1326
01:04:26,850 --> 01:04:27,960
para memorizar que.

1327
01:04:27,960 --> 01:04:30,940
Entón, iso é bo alí para vós.

1328
01:04:30,940 --> 01:04:37,120
Só non esqueza a lóxica que made--
por que estas cifras estaban ocorrendo.

1329
01:04:37,120 --> 01:04:39,870
Se está sempre perdido, pode facer
se sabe o que tipo son.

1330
01:04:39,870 --> 01:04:40,820
E pode realizar a través
los na súa mente

1331
01:04:40,820 --> 01:04:42,903
para descubrir por que os
respostas son esas respostas.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Todo ben.

1334
01:04:47,600 --> 01:04:49,680
Entón, nós estamos indo a ir
en fin, para a investigación.

1335
01:04:49,680 --> 01:04:51,638
Porque, como aqueles de vostedes
que leron o pset,

1336
01:04:51,638 --> 01:04:55,175
investigación tamén forma parte da
problema desta semana define.

1337
01:04:55,175 --> 01:04:57,300
Lle será solicitada a aplicar
dous tipos de investigación.

1338
01:04:57,300 --> 01:05:00,070
Un deles é unha investigación lineal e
é unha investigación binaria.

1339
01:05:00,070 --> 01:05:01,760
>> Así, a procura lineal é moi fácil.

1340
01:05:01,760 --> 01:05:04,070
Só quere buscar elemento
dunha lista para ver se obtelo.

1341
01:05:04,070 --> 01:05:05,444
Só ten para percorrer.

1342
01:05:05,444 --> 01:05:08,170
E se é igual a algo,
pode simplemente devolve-lo, non?

1343
01:05:08,170 --> 01:05:10,890
Pero o que somos máis
interesado en falar

1344
01:05:10,890 --> 01:05:14,550
é a procura binaria, á dereita, que é a
dividir e conquistar mecanismo que

1345
01:05:14,550 --> 01:05:18,190
David estaba demostrando en conferencia.

1346
01:05:18,190 --> 01:05:20,810
>> Teña en conta que o exemplo do libro de teléfono
que segue traendo á tona,

1347
01:05:20,810 --> 01:05:23,960
o que medio que se esforzou
un pouco sobre o ano pasado,

1348
01:05:23,960 --> 01:05:27,530
onde dividir o problema á metade,
ao medio, polo medio, unha e outra vez,

1349
01:05:27,530 --> 01:05:30,730
ata atopar o que estás buscando?

1350
01:05:30,730 --> 01:05:33,727
E ten o
runtime que ben.

1351
01:05:33,727 --> 01:05:35,810
E podes ver, é
significativamente máis eficiente

1352
01:05:35,810 --> 01:05:39,080
do que calquera outro tipo de investigación.

1353
01:05:39,080 --> 01:05:41,880
>> Así, a forma que nós ía sobre
execución dunha investigación binaria

1354
01:05:41,880 --> 01:05:46,510
é, se nós tivésemos unha matriz,
índice de 0 a 6, sete elementos,

1355
01:05:46,510 --> 01:05:49,790
podemos ollar no medio, direita--
Sentímolo, se a nosa pregunta first--

1356
01:05:49,790 --> 01:05:53,840
se queremos facer a pregunta de, fai
a matriz conter o elemento de 7,

1357
01:05:53,840 --> 01:05:56,840
Obviamente, sendo o ser humano, e tendo
tales unha pequena variedade, é fácil para nós

1358
01:05:56,840 --> 01:05:58,210
para dicir si.

1359
01:05:58,210 --> 01:06:05,750
Pero o xeito de aplicar un binario
busca sería a de mirar no medio.

1360
01:06:05,750 --> 01:06:08,020
>> Sabemos que o índice 3 é
no medio, porque

1361
01:06:08,020 --> 01:06:09,270
sei que hai sete elementos.

1362
01:06:09,270 --> 01:06:10,670
O 7 dividido por 2?

1363
01:06:10,670 --> 01:06:12,850
Pode cortar ese extra 1.

1364
01:06:12,850 --> 01:06:14,850
Ten tres no medio.

1365
01:06:14,850 --> 01:06:17,590
Entón é matriz de 3 igual a 7?

1366
01:06:17,590 --> 01:06:18,900
Non é, non?

1367
01:06:18,900 --> 01:06:21,050
Pero podemos facer un par de cheques.

1368
01:06:21,050 --> 01:06:25,380
É gama de 3 a 7 ou menos
3 é de matriz maior que 7?

1369
01:06:25,380 --> 01:06:27,240
>> E sabemos que é inferior a 7.

1370
01:06:27,240 --> 01:06:30,259
Entón, nós sabemos que, oh, debe
non estar na metade esquerda.

1371
01:06:30,259 --> 01:06:32,300
Sabemos que debe ser
na metade dereita, non?

1372
01:06:32,300 --> 01:06:34,662
Así, podemos só cortar a metade do array.

1373
01:06:34,662 --> 01:06:36,370
Nós nin sequera teñen que
máis ollar para ela.

1374
01:06:36,370 --> 01:06:38,711
Porque sabemos que
metade do noso problema--

1375
01:06:38,711 --> 01:06:41,210
sabemos que a resposta está
a metade dereita do noso problema.

1376
01:06:41,210 --> 01:06:42,580
Polo tanto, basta ollar para iso agora.

1377
01:06:42,580 --> 01:06:44,860
>> Entón, agora miramos para o
medio do que restou.

1378
01:06:44,860 --> 01:06:46,880
Este índice 5.

1379
01:06:46,880 --> 01:06:50,200
Nós facemos a mesma verificación de novo
e vemos que é menor.

1380
01:06:50,200 --> 01:06:52,050
Entón, nós miramos á esquerda do que iso.

1381
01:06:52,050 --> 01:06:53,430
E entón vemos que cheque.

1382
01:06:53,430 --> 01:06:57,600
É o valor da matriz en
índice 4 igual a 7?

1383
01:06:57,600 --> 01:06:58,260
É.

1384
01:06:58,260 --> 01:07:03,580
Así, podemos volver certo, porque
atopamos o valor da nosa lista.

1385
01:07:03,580 --> 01:07:06,738
Será que a forma que eu atravesei
que ten sentido para todos?

1386
01:07:06,738 --> 01:07:08,760
Aceptar.

1387
01:07:08,760 --> 01:07:11,670
Vou dar a vostedes quizais, como,
tres, catro minutos para descubrir

1388
01:07:11,670 --> 01:07:13,270
Pseudocódigo como este no.

1389
01:07:13,270 --> 01:07:18,070
>> Entón imaxine eu lle pedín para escribir
chamado función search () que retornaron

1390
01:07:18,070 --> 01:07:20,640
un valor, un valor booleano,
iso era verdade ou false-- como,

1391
01:07:20,640 --> 01:07:22,970
certo se atopou a
valor, falso se non fixo.

1392
01:07:22,970 --> 01:07:25,230
E entón estaba
pasou por valor ti

1393
01:07:25,230 --> 01:07:28,410
busca en valores, que
é o array-- Oh, eu sempre poñer

1394
01:07:28,410 --> 01:07:29,410
que no lugar incorrecto.

1395
01:07:29,410 --> 01:07:29,580
Aceptar.

1396
01:07:29,580 --> 01:07:31,829
En calquera caso, que debe ter
foi á dereita de valores.

1397
01:07:31,829 --> 01:07:36,280
E, a continuación, int n é o número
de elementos desa matriz.

1398
01:07:36,280 --> 01:07:39,430
Como ía sobre o intento
Pseudocódigo para este problema en?

1399
01:07:39,430 --> 01:07:41,630
Vou dar a vostedes como
tres minutos para facelo.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Non, eu creo que hai only--
si, hai un aquí enriba.

1402
01:08:02,595 --> 01:08:03,261
Audiencia: Podo?

1403
01:08:03,261 --> 01:08:04,388
ANDI Pengo: Si, eu teño ti.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
É que traballar?

1406
01:08:11,050 --> 01:08:12,290
OK, legal.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> Aceptar.

1409
01:10:44,720 --> 01:10:47,630
Todos os mozos certos, somos
vai control-lo.

1410
01:10:47,630 --> 01:10:49,730
Aceptar.

1411
01:10:49,730 --> 01:10:54,020
Entón asumir que temos esta linda
pouco matriz con valores de n na mesma.

1412
01:10:54,020 --> 01:10:55,170
Non deseñar as liñas.

1413
01:10:55,170 --> 01:10:58,649
Pero como é que imos sobre
intentando escribir isto?

1414
01:10:58,649 --> 01:11:00,440
Alguén quere
dáme a primeira liña?

1415
01:11:00,440 --> 01:11:02,814
Se quere me dar o
primeira liña deste pseudocódigo.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> Audiencia: [inaudível]

1418
01:11:08,430 --> 01:11:10,138
Audiencia: Vostede vai querer
iterado through--

1419
01:11:10,138 --> 01:11:11,094
Audiencia: Só un para loop?

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 Pengo: Entón, este é un pouco complicado.

1423
01:11:17,780 --> 01:11:23,130
Pense about-- quere
para continuar executando ese loop

1424
01:11:23,130 --> 01:11:27,950
unha e outra vez ata cando?

1425
01:11:27,950 --> 01:11:30,819
>> Audiencia: Ata o [inaudível]
valor que é igual ao valor.

1426
01:11:30,819 --> 01:11:31,610
ANDI Pengo: Exactamente.

1427
01:11:31,610 --> 01:11:33,900
Entón pode realmente só write--
podemos incluso simplifica-lo máis.

1428
01:11:33,900 --> 01:11:35,630
Podemos só facer un loop while, non?

1429
01:11:35,630 --> 01:11:39,380
Entón podes só ter loop--
sabemos que é un tempo.

1430
01:11:39,380 --> 01:11:42,850
Pero, por agora, eu vou
para dicir "lazo" - a través do que?

1431
01:11:42,850 --> 01:11:46,640
Lazo que é until--
nosa condición terminando?

1432
01:11:46,640 --> 01:11:47,510
Creo que oín-lo.

1433
01:11:47,510 --> 01:11:48,530
Oín a alguén dicir iso.

1434
01:11:48,530 --> 01:11:51,255
>> Audiencia: Valores iguala medio.

1435
01:11:51,255 --> 01:11:52,255
ANDI Pengo: Diga iso de novo.

1436
01:11:52,255 --> 01:11:54,470
Audiencia: Ou, ata o
valor que está a buscar

1437
01:11:54,470 --> 01:11:58,470
para coincide co valor medio.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI Pengo: O que se non está alí?

1439
01:12:00,280 --> 01:12:03,113
E se o valor que está a buscar
para non é realmente nesa matriz?

1440
01:12:03,113 --> 01:12:05,890
Audiencia: Vostede retorna 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI Pengo: Pero o que queremos
loop ata que se nos ten unha condición?

1442
01:12:08,850 --> 01:12:09,350
Si.

1443
01:12:09,350 --> 01:12:11,239
>> Audiencia: Ata que haxa só un valor?

1444
01:12:11,239 --> 01:12:13,530
ANDI Pengo: Pode facer un loop
until-- para que vostede sabe que é

1445
01:12:13,530 --> 01:12:15,714
terá un valor máximo, non?

1446
01:12:15,714 --> 01:12:18,130
E vostede sabe que está indo
para ter un valor min, non?

1447
01:12:18,130 --> 01:12:20,379
Porque tamén, iso é algo
Eu esquezo de dicir antes,

1448
01:12:20,379 --> 01:12:22,640
que algo que é
crítica sobre busca binaria

1449
01:12:22,640 --> 01:12:24,182
é que a súa matriz xa está clasificado.

1450
01:12:24,182 --> 01:12:26,973
Porque non hai ningunha forma de fazê-
iso se son só valores aleatorios.

1451
01:12:26,973 --> 01:12:29,190
Non sabe se é
maior que o outro, non?

1452
01:12:29,190 --> 01:12:32,720
>> Entón, vostede sabe que o seu máximo e
seus mins está aquí, non?

1453
01:12:32,720 --> 01:12:35,590
Se vai estar adaptándose
seu máximo nos seus minutos e os mid--

1454
01:12:35,590 --> 01:12:38,470
imos asumir o seu
valor medio é aqui-- dereita

1455
01:12:38,470 --> 01:12:43,910
está indo a basicamente
loop ata a súa mínima é de

1456
01:12:43,910 --> 01:12:47,510
sobre o mesmo como o seu máximo, á dereita ou
se o máximo non é o mesmo que o seu min.

1457
01:12:47,510 --> 01:12:48,040
Non?

1458
01:12:48,040 --> 01:12:51,340
Porque cando isto ocorre, xa sabe que
ti, finalmente, acadar o mesmo valor.

1459
01:12:51,340 --> 01:12:59,135
Entón quere facer un loop ata que o seu min
é inferior ou igual a-- oops,

1460
01:12:59,135 --> 01:13:01,510
non menos que ou igual a,
a outra forma é circundar-- max.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Será que isto ten sentido?

1463
01:13:16,160 --> 01:13:18,810
I levou algúns intentos para obter este dereito.

1464
01:13:18,810 --> 01:13:21,869
Pero loop ata que o seu valor máximo
é esencialmente case menos

1465
01:13:21,869 --> 01:13:23,410
ou igual a seu mínimo, non?

1466
01:13:23,410 --> 01:13:25,201
Isto é cando vostede sabe
que xa converxer.

1467
01:13:25,201 --> 01:13:29,290
Audiencia: Cando sería o seu máximo
valor pode ser inferior ao mínimo?

1468
01:13:29,290 --> 01:13:31,040
ANDI Pengo: Se mantén
axustándose o, o que

1469
01:13:31,040 --> 01:13:32,380
é o que nós estamos indo
estar facendo neste.

1470
01:13:32,380 --> 01:13:33,460
Isto ten sentido?

1471
01:13:33,460 --> 01:13:35,750
Mínimo e máximo son só
enteiros que son, probablemente,

1472
01:13:35,750 --> 01:13:39,260
Vai querer crear para manter
o control de onde nós estamos mirando.

1473
01:13:39,260 --> 01:13:41,790
Como a matriz existe
independentemente do que estamos facendo.

1474
01:13:41,790 --> 01:13:45,030
Como, non estamos fisicamente
decepar a matriz, non?

1475
01:13:45,030 --> 01:13:47,261
Estamos só axustando
onde estamos mirando.

1476
01:13:47,261 --> 01:13:48,136
Isto ten sentido?

1477
01:13:48,136 --> 01:13:48,472
>> Audiencia: É.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI Pengo: Aceptar.

1479
01:13:49,110 --> 01:13:57,090
Entón, se esa é a condición para o noso loop,
o que queremos dentro deste loop?

1480
01:13:57,090 --> 01:13:58,700
O que imos estar querendo facer?

1481
01:13:58,700 --> 01:14:02,390
Entón, agora, temos
un máximo e un mínimo, dereito,

1482
01:14:02,390 --> 01:14:04,962
Probablemente creouse aquí nalgún lugar.

1483
01:14:04,962 --> 01:14:07,170
Nós imos probablemente quere
para atopar un medio, non?

1484
01:14:07,170 --> 01:14:08,450
Como é que vai ser
capaz de atopar o medio?

1485
01:14:08,450 --> 01:14:09,491
Cal é a mathematical--

1486
01:14:09,491 --> 01:14:11,079
Audiencia: Max ademais min divididos por dous.

1487
01:14:11,079 --> 01:14:11,870
ANDI Pengo: Exactamente.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Isto ten sentido?

1490
01:14:21,620 --> 01:14:25,780
E que vós ver porque
non só use-- por que fixemos iso

1491
01:14:25,780 --> 01:14:27,850
no canto de facer só n dividido por 2?

1492
01:14:27,850 --> 01:14:30,310
É porque n é un valor
que se ve na mesma.

1493
01:14:30,310 --> 01:14:30,979
Non?

1494
01:14:30,979 --> 01:14:34,020
Pero porque axustamos nosa mínimo e
valores máximos, van cambiar.

1495
01:14:34,020 --> 01:14:36,040
E, como resultado, o noso medio
vai cambiar tamén.

1496
01:14:36,040 --> 01:14:37,873
Entón é por iso que queremos
para facelo aquí.

1497
01:14:37,873 --> 01:14:38,510
Aceptar.

1498
01:14:38,510 --> 01:14:41,600
>> E entón, agora que
atopamos our-- si.

1499
01:14:41,600 --> 01:14:44,270
>> Audiencia: Só un question-- rápida
cando di min e max,

1500
01:14:44,270 --> 01:14:46,410
asumindo que estamos
xa está clasificado?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI Pengo: Si, iso é realmente unha
condición previa para unha busca binaria,

1502
01:14:48,400 --> 01:14:49,816
que ten que saber que está clasificada.

1503
01:14:49,816 --> 01:14:53,660
É por iso que tipo, escribe no seu
conxunto de problemas antes da súa procura binaria.

1504
01:14:53,660 --> 01:14:55,910
Aceptar.

1505
01:14:55,910 --> 01:14:58,876
Polo tanto, agora que sabemos onde noso punto medio
é, o que quere facer aquí?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> Audiencia: Queremos comparar
que para o outro.

1508
01:15:04,319 --> 01:15:05,110
ANDI Pengo: Exactamente.

1509
01:15:05,110 --> 01:15:12,280
Entón está indo para comparar
mediados de valor, non?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
E que dicir iso
nós cando se comparan?

1512
01:15:18,670 --> 01:15:22,226
O que queremos facer despois?

1513
01:15:22,226 --> 01:15:25,389
>> Audiencia: Se o valor é maior
de mediados dos anos, queremos corte-lo.

1514
01:15:25,389 --> 01:15:26,180
ANDI Pengo: Exactamente.

1515
01:15:26,180 --> 01:15:33,940
Entón, se o valor é maior
de mediados dos anos, estamos

1516
01:15:33,940 --> 01:15:36,550
Vai querer cambiar esas
Maxes mínimo e, non?

1517
01:15:36,550 --> 01:15:38,980
O que queremos cambiar?

1518
01:15:38,980 --> 01:15:42,145
Entón, se sabemos o valor está nalgún lugar
aquí, o que que cambiar?

1519
01:15:42,145 --> 01:15:44,758
Queremos cambiar a nosa
mínimo a ser mid, non?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
E entón outra cousa, se é neste
metade, o que queremos cambiar?

1522
01:15:54,292 --> 01:15:55,306
>> Audiencia O seu máximo.

1523
01:15:55,306 --> 01:15:55,972
ANDI Pengo: Si.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
E entón só vai
para manter looping, non?

1526
01:16:04,680 --> 01:16:08,920
Porque agora, despois dunha iteración
través, ten un máximo aquí.

1527
01:16:08,920 --> 01:16:10,760
E entón podes recalcular un mid.

1528
01:16:10,760 --> 01:16:11,990
E entón podes comparar.

1529
01:16:11,990 --> 01:16:14,766
E está indo a seguir
ata os minutos e as Maxes

1530
01:16:14,766 --> 01:16:15,890
ter esencialmente converxentes.

1531
01:16:15,890 --> 01:16:17,890
E iso é cando vostede sabe que
bateu o fin de todo.

1532
01:16:17,890 --> 01:16:20,280
E quere vostede encontrou-
ou non ten nese momento.

1533
01:16:20,280 --> 01:16:23,170
>> Será que isto ten sentido para todos?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
Aceptar.

1536
01:16:26,770 --> 01:16:27,900
Isto é moi importante,
porque vai ter

1537
01:16:27,900 --> 01:16:29,760
para escribir isto no seu código de esta noite.

1538
01:16:29,760 --> 01:16:32,660
Pero vós teñen unha boa
sensación de que debería estar facendo,

1539
01:16:32,660 --> 01:16:34,051
o que é bo.

1540
01:16:34,051 --> 01:16:34,550
Aceptar.

1541
01:16:34,550 --> 01:16:38,840
Entón, nós temos uns sete
minutos sección esquerda.

1542
01:16:38,840 --> 01:16:43,170
Entón, nós estamos indo falar
este pset que estaremos facendo.

1543
01:16:43,170 --> 01:16:46,410
Así, o pset divídese en dúas metades.

1544
01:16:46,410 --> 01:16:50,230
A primeira parte implica
a posta en marcha dun find

1545
01:16:50,230 --> 01:16:54,210
no que escribe unha busca lineal, un
busca binaria, e un algoritmo de ordenación.

1546
01:16:54,210 --> 01:16:56,690
>> Polo tanto, este é o primeiro
tempo nun pset onde

1547
01:16:56,690 --> 01:17:00,050
estaremos dando a vostedes o que se chama
código de distribución, que é o código

1548
01:17:00,050 --> 01:17:02,740
que temos pre-escrito,
pero só deixou algunhas pezas off

1549
01:17:02,740 --> 01:17:04,635
para que termine de escribir.

1550
01:17:04,635 --> 01:17:07,510
Entón vós, cando mira para esta
código, pode ser realmente asustado.

1551
01:17:07,510 --> 01:17:08,630
Se vostede está só como, ahh, eu
non sei o que está facendo,

1552
01:17:08,630 --> 01:17:11,670
Non sei como, que parece
tan complicado, ahh, relaxarse.

1553
01:17:11,670 --> 01:17:12,170
Está ben.

1554
01:17:12,170 --> 01:17:12,930
Ler o spec.

1555
01:17:12,930 --> 01:17:16,920
A especificación pode explicar-lle exactamente
o que todos estes programas están facendo.

1556
01:17:16,920 --> 01:17:20,560
>> Por exemplo, é un programa generate.c
que virá coa súa pset.

1557
01:17:20,560 --> 01:17:24,060
Realmente non ten que tocalo, pero
ten que entender o que está facendo.

1558
01:17:24,060 --> 01:17:28,550
E generate.c, todo o que está facendo é
quere xerar números aleatorios

1559
01:17:28,550 --> 01:17:32,400
ou pode darlle unha semente, como un
número preestabelecido que leva,

1560
01:17:32,400 --> 01:17:34,140
e xera máis números.

1561
01:17:34,140 --> 01:17:37,170
Polo tanto, hai un xeito específico para
aplicar no que generate.c

1562
01:17:37,170 --> 01:17:42,760
pode só facer unha chea de números
para probar os seus outros métodos diante.

1563
01:17:42,760 --> 01:17:45,900
>> Entón, se quería, para
exemplo, probar o seu descubrimento,

1564
01:17:45,900 --> 01:17:48,970
vostede vai querer executar generate.c,
xerar unha morea de números,

1565
01:17:48,970 --> 01:17:50,880
e logo realizar a función de axudantes.

1566
01:17:50,880 --> 01:17:53,930
A súa función axudantes é onde está
realmente escribir fisicamente código.

1567
01:17:53,930 --> 01:17:59,330
E pensar axudantes como un arquivo de biblioteca
está escribindo que find está chamando.

1568
01:17:59,330 --> 01:18:02,950
E así dentro helpers.c, vai
facer investigación e clasificación.

1569
01:18:02,950 --> 01:18:06,500
>> E entón vai, esencialmente,
só poñer-los todos xuntos.

1570
01:18:06,500 --> 01:18:10,350
A especificación ha dicir-lle como
poñer isto na liña de comandos.

1571
01:18:10,350 --> 01:18:14,880
E vai ser capaz de probar ou
non o seu tipo e de investigación están a traballar.

1572
01:18:14,880 --> 01:18:15,870
Legal.

1573
01:18:15,870 --> 01:18:18,720
Alguén xa comezou e
problemas atopados ou preguntas

1574
01:18:18,720 --> 01:18:20,520
teñen agora con iso?

1575
01:18:20,520 --> 01:18:21,020
Aceptar.

1576
01:18:21,020 --> 01:18:21,476
>> Audiencia: Espera.

1577
01:18:21,476 --> 01:18:21,932
Teño unha pregunta.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI Pengo: Si.

1579
01:18:22,844 --> 01:18:28,390
>> Audiencia: Entón eu comece a facer
a procura lineal en helpers.c

1580
01:18:28,390 --> 01:18:29,670
e non foi realmente funciona.

1581
01:18:29,670 --> 01:18:34,590
Pero, a continuación, máis tarde, descubrín que acabamos
ten que borrar-lo e facer busca binaria.

1582
01:18:34,590 --> 01:18:36,991
Entón, non importa se non funciona?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI Pengo: resposta curta é non.

1585
01:18:41,510 --> 01:18:42,642
Pero xa que estamos não--

1586
01:18:42,642 --> 01:18:44,350
Audiencia: Pero ninguén de
realmente comprobar.

1587
01:18:44,350 --> 01:18:46,058
ANDI Pengo: Nunca somos
Vai ver isto.

1588
01:18:46,058 --> 01:18:49,590
Pero probablemente vai querer facer
Comproba se a súa procura funciona.

1589
01:18:49,590 --> 01:18:51,700
Porque se o seu lineal
Busca non funciona,

1590
01:18:51,700 --> 01:18:54,410
entón as posibilidades son o seu par
busca non vai funcionar tan ben.

1591
01:18:54,410 --> 01:18:56,646
Porque ten similar
lóxica en ambas.

1592
01:18:56,646 --> 01:18:58,020
E non, iso realmente non importa.

1593
01:18:58,020 --> 01:19:01,300
Entón, os únicos que vai virar
en son unha especie e busca binaria.

1594
01:19:01,300 --> 01:19:02,490
Si.

1595
01:19:02,490 --> 01:19:06,610
>> E tamén, unha morea de nenos foron
tentar compilar helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Non está realmente permitido
para facelo, porque helpers.c

1597
01:19:09,550 --> 01:19:11,200
non ten unha función principal.

1598
01:19:11,200 --> 01:19:13,550
E para que só debe
ser realmente compilando

1599
01:19:13,550 --> 01:19:18,670
xerar e atopar, porque atopar chamadas
helpers.c e as funcións dentro dela.

1600
01:19:18,670 --> 01:19:20,790
Así que fai a depuración
unha dor na bunda.

1601
01:19:20,790 --> 01:19:22,422
Pero iso é o que temos que facer.

1602
01:19:22,422 --> 01:19:23,880
Audiencia: Acaba de facer todo, non?

1603
01:19:23,880 --> 01:19:27,290
ANDI Pengo: pode só
facer todo ben, si.

1604
01:19:27,290 --> 01:19:28,060
Aceptar.

1605
01:19:28,060 --> 01:19:32,570
Entón é iso en termos do que
o pset pide que todos vostedes fagan.

1606
01:19:32,570 --> 01:19:35,160
Se ten algunha dúbida, sinta-
a liberdade de me preguntar despois sección.

1607
01:19:35,160 --> 01:19:37,580
Eu vou estar aquí para, como, 20 minutos.

1608
01:19:37,580 --> 01:19:40,500
>> E si, os PSet de
non é realmente tan malo así.

1609
01:19:40,500 --> 01:19:41,680
Vostedes deben estar OK.

1610
01:19:41,680 --> 01:19:43,250
Estes, basta seguir as orientacións.

1611
01:19:43,250 --> 01:19:47,840
Tipo de ter un sentido de, loxicamente, o que
debería estar pasando e vai estar ben.

1612
01:19:47,840 --> 01:19:48,690
Non sexa moi asustado.

1613
01:19:48,690 --> 01:19:50,220
Hai unha morea de código
xa escrito alí.

1614
01:19:50,220 --> 01:19:53,011
Non moito medo se non fai
entender o que todo isto significa.

1615
01:19:53,011 --> 01:19:54,749
Se é moito, é totalmente ben.

1616
01:19:54,749 --> 01:19:55,790
E chegar a horas de expediente.

1617
01:19:55,790 --> 01:19:57,520
Nós imos axudar a dar un ollo.

1618
01:19:57,520 --> 01:20:00,810
>> Audiencia: Coa adicional
funcións, parecemos os anteriores?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI Pengo: Si, esas son no código.

1620
01:20:03,417 --> 01:20:05,750
No xogo de 15, a metade dos
xa está escrito para ti.

1621
01:20:05,750 --> 01:20:09,310
Así, estas funcións se
xa no código.

1622
01:20:09,310 --> 01:20:12,020
Yep.

1623
01:20:12,020 --> 01:20:12,520
Todo ben.

1624
01:20:12,520 --> 01:20:14,000
Ben, mellor sorte.

1625
01:20:14,000 --> 01:20:15,180
É un día nojento.

1626
01:20:15,180 --> 01:20:19,370
Polo tanto, esperamos que vós non me sinto moi
mal por estar dentro e codificación.

1627
01:20:19,370 --> 01:20:22,133