1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Sección 3 - máis cómodo]

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

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

4
00:00:07,310 --> 00:00:12,700
>> Entón, a primeira pregunta é estrañamente formulada.

5
00:00:12,700 --> 00:00:17,480
GDB permite "depurar" un programa, pero, máis especificamente, que é o que imos facer?

6
00:00:17,480 --> 00:00:22,590
Vou responder esa, e eu non sei o que é o esperado,

7
00:00:22,590 --> 00:00:27,910
entón eu estou supondo que é algo ao longo das liñas de el permite que paso a paso

8
00:00:27,910 --> 00:00:31,540
andar a través do programa, interactuar con el, as variables de cambio, facer todas estas cousas -

9
00:00:31,540 --> 00:00:34,270
basicamente controlar completamente a execución dun programa

10
00:00:34,270 --> 00:00:38,410
e inspeccionar calquera determinada parte da execución do programa.

11
00:00:38,410 --> 00:00:43,030
Entón, eses recursos permiten que depurar as cousas.

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

13
00:00:44,830 --> 00:00:50,520
Por que a procura binaria require que unha matriz ser clasificados?

14
00:00:50,520 --> 00:00:53,360
Quen quere responder a iso?

15
00:00:56,120 --> 00:01:00,070
[Alumno] Porque non funciona se non é clasificado. Si >>. [Risas]

16
00:01:00,070 --> 00:01:04,910
Se non é resolto, entón é imposible para división lo ao medio

17
00:01:04,910 --> 00:01:07,850
e saber que todo a esquerda é menos e todo á dereita

18
00:01:07,850 --> 00:01:10,490
é maior que o valor medio.

19
00:01:10,490 --> 00:01:12,790
Por iso, debe ser ordenada.

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

21
00:01:14,170 --> 00:01:17,570
Por que é unha especie de burbulla en O de n ao cadrado?

22
00:01:17,570 --> 00:01:23,230
Alguén primeiro quero dar unha moi rápida visión xeral de alto nivel de que tipo burbulla é?

23
00:01:25,950 --> 00:01:33,020
[Alumno] Vostede basicamente pasar por cada elemento e comprobar os elementos primeiros.

24
00:01:33,020 --> 00:01:37,150
Se eles están fóra de onde troca-los, despois de comprobar os elementos seguintes, e así por diante.

25
00:01:37,150 --> 00:01:40,770
Cando chegar ao final, entón vostede sabe que o maior elemento colócase ao final,

26
00:01:40,770 --> 00:01:42,750
así ignorar que un, entón continuar pasando,

27
00:01:42,750 --> 00:01:48,490
e cada vez que ten que comprobar un elemento menos ata que non facer cambios. Si >>.

28
00:01:48,490 --> 00:01:58,470
É chamado especie de burbulla, porque se virar a matriz de lado así que é de arriba para abaixo, vertical,

29
00:01:58,470 --> 00:02:03,100
a continuación, os grandes valores que van para o fondo e os pequenos valores vai borbulhar ata o cumio.

30
00:02:03,100 --> 00:02:05,210
É así que ten o seu nome.

31
00:02:05,210 --> 00:02:08,220
E si, acaba de pasar.

32
00:02:08,220 --> 00:02:11,190
Vostede segue pasando pola matriz, trocando o valor maior

33
00:02:11,190 --> 00:02:14,040
para obter os maiores valores para o fondo.

34
00:02:14,040 --> 00:02:17,500
>> Por que é o n ao cadrado?

35
00:02:18,690 --> 00:02:24,620
En primeiro lugar, alguén quere dicir por iso que é o n ao cadrado?

36
00:02:24,620 --> 00:02:28,760
[Alumno] Por cada carreira vai n veces.

37
00:02:28,760 --> 00:02:32,100
Só podes estar seguro de que teña tido o maior elemento de todo o camiño,

38
00:02:32,100 --> 00:02:35,230
entón tes que repetir que para tantos elementos. Si >>.

39
00:02:35,230 --> 00:02:41,800
Polo tanto, teña presente o que significa e gran Que significa Omega grandes.

40
00:02:41,800 --> 00:02:50,560
O O gran é como o límite superior sobre o quão lento el realmente pode ser executado.

41
00:02:50,560 --> 00:02:58,990
Entón, dicindo que é o n ao cadrado, non é o de n ou el sería capaz de executar

42
00:02:58,990 --> 00:03:02,640
no tempo lineal, pero é de O n cubed

43
00:03:02,640 --> 00:03:06,390
porque é delimitada por O de n en cubos.

44
00:03:06,390 --> 00:03:12,300
Se é limitado por O de n ao cadrado, é limitada tamén polo n cubos.

45
00:03:12,300 --> 00:03:20,280
Por iso, é n ao cadrado e, no peor caso absoluta que non pode facer mellor que n ao cadrado,

46
00:03:20,280 --> 00:03:22,830
é por iso que é o n ao cadrado.

47
00:03:22,830 --> 00:03:31,200
Entón, para ver de matemáticas discreta en como ven sendo n ao cadrado,

48
00:03:31,200 --> 00:03:40,530
se temos cinco cousas na nosa lista, a primeira vez que o número de swaps poderiamos potencialmente cómpre facer

49
00:03:40,530 --> 00:03:47,170
a fin de obter isto? Imos realmente só -

50
00:03:47,170 --> 00:03:52,040
Cantos swaps que imos ter que facer na primeira carreira da especie de burbulla a través da matriz?

51
00:03:52,040 --> 00:03:53,540
[Alumno] n - 1. Si >>.

52
00:03:53,540 --> 00:03:58,340
>> Se hai 5 elementos, imos ter que facer n - 1.

53
00:03:58,340 --> 00:04:01,100
A continuación, no segundo cantas swaps que imos ter que facer?

54
00:04:01,100 --> 00:04:03,440
[Estudante] n - 2. Si >>.

55
00:04:03,440 --> 00:04:11,640
E o terceiro vai ser n - 3, e logo para o barrio vou escribir os dous últimos

56
00:04:11,640 --> 00:04:15,270
como entón imos ter que facer dous swaps e un de intercambio.

57
00:04:15,270 --> 00:04:19,899
Eu creo que o último pode ou non pode realmente precisan pasar.

58
00:04:19,899 --> 00:04:22,820
É un intercambio? Eu non sei.

59
00:04:22,820 --> 00:04:26,490
Polo tanto, estas son as cantidades totais de swaps ou polo menos comparacións que ten que facer.

60
00:04:26,490 --> 00:04:29,910
Mesmo se non cambiar, aínda que comparar os valores.

61
00:04:29,910 --> 00:04:33,910
Entón, existen n - 1 comparacións na primeira carreira a través da matriz.

62
00:04:33,910 --> 00:04:42,050
Se reorganizar isto, imos realmente facer seis cousas así que as cousas se comportan ben,

63
00:04:42,050 --> 00:04:44,790
e entón eu vou facer 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Entón, só tes que reorganizar estes importes, que queremos ver cantas comparacións facemos

65
00:04:49,910 --> 00:04:52,700
no algoritmo enteiro.

66
00:04:52,700 --> 00:04:56,550
Entón, se nós traemos estes faces aquí abaixo,

67
00:04:56,550 --> 00:05:07,470
entón aínda estamos só sumando comparacións con todo eran.

68
00:05:07,470 --> 00:05:13,280
Pero resumir estes e sumamos estes e sumamos estes,

69
00:05:13,280 --> 00:05:18,130
aínda é o mesmo problema. Nós só sumar eses grupos particulares.

70
00:05:18,130 --> 00:05:22,400
>> Entón agora estamos sumando 3 n da. Non é só de 3 n.

71
00:05:22,400 --> 00:05:27,650
É sempre vai ser n / 2 n é.

72
00:05:27,650 --> 00:05:29,430
Entón, aquí acontece que temos 6.

73
00:05:29,430 --> 00:05:34,830
Se tivésemos 10 cousas, entón nós poderíamos facelo de agrupación para 5 pares distintos de cousas

74
00:05:34,830 --> 00:05:37,180
e acabar con n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Entón, está sempre indo para obter N / 2 N, e así por iso, imos anotar-lo para n ao cadrado / 2.

76
00:05:45,840 --> 00:05:48,890
E por iso mesmo que é o factor da metade, o que pasa a entrar en

77
00:05:48,890 --> 00:05:54,190
debido ao feito de que en cada iteração sobre a matriz compararmos un a menos

78
00:05:54,190 --> 00:05:58,040
entón é así que temos a máis de 2, pero aínda é n ao cadrado.

79
00:05:58,040 --> 00:06:01,650
Nós non nos importamos co factor constante dun media.

80
00:06:01,650 --> 00:06:07,760
Entón, unha morea de cousas O grande como este se basea en só un tipo de facer este tipo de matemáticas,

81
00:06:07,760 --> 00:06:12,260
facer contas de aritmética e outras cousas serie xeométrica,

82
00:06:12,260 --> 00:06:17,750
pero a maioría deles neste curso son moi sinxelo.

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

84
00:06:19,290 --> 00:06:24,430
Por que é tipo de inserción no Omega de n? O que o omega significa?

85
00:06:24,430 --> 00:06:27,730
[Dous alumnos falan ao mesmo tempo - inintelixibles] si. >>

86
00:06:27,730 --> 00:06:30,630
Omega pode pensar como o límite inferior.

87
00:06:30,630 --> 00:06:36,550
>> Polo tanto, non importa o quão eficaz o seu algoritmo de ordenación por inserción e,

88
00:06:36,550 --> 00:06:41,810
independentemente da lista que se transmite, el sempre ten que comparar polo menos n cousas

89
00:06:41,810 --> 00:06:44,620
ou ten que iterar n cousas.

90
00:06:44,620 --> 00:06:47,280
Por que isto?

91
00:06:47,280 --> 00:06:51,190
[Alumno] Porque a lista xa está clasificado, a continuación, a través iteração o primeiro

92
00:06:51,190 --> 00:06:54,080
só pode garantir que o primeiro elemento é o mínimo,

93
00:06:54,080 --> 00:06:56,490
ea segunda iteração só pode garantir os dous primeiros son

94
00:06:56,490 --> 00:07:00,010
porque non sabe o que o resto da lista está ordenada. Si >>.

95
00:07:00,010 --> 00:07:08,910
Se pasar a unha lista completamente clasificados, como mínimo ten que pasar por riba de todos os elementos

96
00:07:08,910 --> 00:07:12,180
para ver que nada ten que ser movidos.

97
00:07:12,180 --> 00:07:14,720
Entón, pasando por riba da lista e dicir oh, iso xa está clasificado,

98
00:07:14,720 --> 00:07:18,240
é imposible para ti saber que está clasificada ata que verifique cada elemento

99
00:07:18,240 --> 00:07:20,660
para ver que están en orde de clasificación.

100
00:07:20,660 --> 00:07:25,290
Así, o límite inferior é Omega tipo de inserción de n.

101
00:07:25,290 --> 00:07:28,210
Cal é o peor caso de tempo de funcionamento merge sort,

102
00:07:28,210 --> 00:07:31,390
O peor caso de ser grande de novo?

103
00:07:31,390 --> 00:07:37,660
Así, no peor caso, como é que merge sort correr?

104
00:07:42,170 --> 00:07:43,690
[Estudante] N log n. Si >>.

105
00:07:43,690 --> 00:07:49,990
Os máis rápidos algoritmos de clasificación xeral son n log n. Vostede non pode facer mellor.

106
00:07:51,930 --> 00:07:55,130
>> Hai casos especiais, e se temos tempo de hoxe - pero probablemente won't -

107
00:07:55,130 --> 00:07:59,330
podemos ver un que fai mellor que n log n.

108
00:07:59,330 --> 00:08:04,050
Pero, no caso xeral, non pode facer mellor que n log n.

109
00:08:04,050 --> 00:08:09,680
E merge sort pasa a ser o que debes saber para este curso que é n log n.

110
00:08:09,680 --> 00:08:13,260
E así imos realmente ser de execución que hoxe.

111
00:08:13,260 --> 00:08:18,070
E, finalmente, en non máis que tres frases, como funciona o tipo de selección?

112
00:08:18,070 --> 00:08:20,370
Alguén quere responder, e eu vou contar as súas frases

113
00:08:20,370 --> 00:08:22,390
porque se pasar por riba de 3 -

114
00:08:25,530 --> 00:08:28,330
Alguén se lembra tipo de selección?

115
00:08:31,280 --> 00:08:37,809
Tipo de selección é xeralmente moi fácil de lembrar só do nome.

116
00:08:37,809 --> 00:08:45,350
Só iterar sobre a matriz, atopar o que o maior valor é menor ou -

117
00:08:45,350 --> 00:08:47,290
orde que está clasificando dentro

118
00:08:47,290 --> 00:08:50,750
Entón, imos dicir que estamos clasificación da menor á maior.

119
00:08:50,750 --> 00:08:55,250
Vostede iterar sobre a matriz, ollando para o que o elemento mínimo é,

120
00:08:55,250 --> 00:08:59,750
selecciona-lo, e despois é só troca-lo o que está en primeiro lugar.

121
00:08:59,750 --> 00:09:04,090
E entón, na segunda pasaxe sobre a matriz, busque o elemento mínimo de novo,

122
00:09:04,090 --> 00:09:07,490
selecciona-lo, e despois troca-lo o que está na segunda posición.

123
00:09:07,490 --> 00:09:10,650
Entón, estamos só escollendo os valores mínimos

124
00:09:10,650 --> 00:09:16,050
e inserindo-os na fronte da matriz ata que sexa ordenada.

125
00:09:19,210 --> 00:09:21,560
Preguntas sobre iso?

126
00:09:21,560 --> 00:09:25,710
>> Isto inevitablemente aparecen nas formas que ten que cubrir cando está enviando o pset.

127
00:09:29,010 --> 00:09:32,360
Estes son, basicamente, as respostas a estes.

128
00:09:32,360 --> 00:09:34,230
Ok, entón agora codificación problemas.

129
00:09:34,230 --> 00:09:40,140
Eu xa enviado mediante correo-e - Será que ninguén obter ese e-mail? Okay.

130
00:09:40,140 --> 00:09:46,630
Eu xa enviou por correo-e o espazo que imos utilizar,

131
00:09:46,630 --> 00:09:52,120
e se fai clic no meu nome - entón eu creo que vou estar no fondo

132
00:09:52,120 --> 00:09:57,170
por mor do r atrás - pero se fai clic no meu nome que vai ver dúas revisións.

133
00:09:57,170 --> 00:10:02,650
Revisión 1 vai ser xa copiou e colou o código en espazos

134
00:10:02,650 --> 00:10:06,900
a cousa de busca terá que aplicar.

135
00:10:06,900 --> 00:10:10,540
Revisión 2 e será a cousa tipo que imos aplicar despois diso.

136
00:10:10,540 --> 00:10:15,770
Así, pode facer clic no meu Revisión 1 e traballar a partir de aí.

137
00:10:17,350 --> 00:10:22,060
E agora queremos aplicar busca binaria.

138
00:10:22,060 --> 00:10:26,470
>> Alguén quere só dar unha explicación de alto nivel pseudocódigo

139
00:10:26,470 --> 00:10:31,440
de que nós imos ter que facer para investigacións? Si

140
00:10:31,440 --> 00:10:36,170
[Estudante] Vostede acaba de tomar a metade da matriz para ver o que está a buscar

141
00:10:36,170 --> 00:10:38,650
é menor que ou maior que iso.

142
00:10:38,650 --> 00:10:41,080
E se é menos, vai para a metade que é menos

143
00:10:41,080 --> 00:10:44,750
e é máis, vai para a metade que é máis e repetir iso ata, é só incorporarse unha cousa.

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

145
00:10:46,570 --> 00:10:51,320
Teña en conta que a nosa matriz de números xa está clasificado,

146
00:10:51,320 --> 00:10:57,190
e así que significa que podemos sacar proveito diso e podemos comprobar primeiro,

147
00:10:57,190 --> 00:11:00,390
ben, eu estou ollando para o número 50.

148
00:11:00,390 --> 00:11:03,720
Entón eu podo ir para o medio.

149
00:11:03,720 --> 00:11:07,380
Medio é difícil de definir cando é un número par de cousas,

150
00:11:07,380 --> 00:11:10,820
pero imos só dicir que sempre truncar para o medio.

151
00:11:10,820 --> 00:11:14,420
Polo tanto, temos aquí oito cousas, de xeito que o medio sería 16.

152
00:11:14,420 --> 00:11:17,330
Estou na procura de 50, polo que 50 é maior que 16.

153
00:11:17,330 --> 00:11:21,310
Entón agora podo tratar a miña matriz basicamente como estes elementos.

154
00:11:21,310 --> 00:11:23,450
Eu podo tirar todo de máis 16.

155
00:11:23,450 --> 00:11:27,440
Agora a miña matriz é só estes catro elementos, e repito.

156
00:11:27,440 --> 00:11:31,910
Entón eu quero atopar o medio novo, que vai a ser 42.

157
00:11:31,910 --> 00:11:34,730
42 é menor que 50, entón eu podo tirar estes dous elementos.

158
00:11:34,730 --> 00:11:36,890
Esta é a miña matriz resto.

159
00:11:36,890 --> 00:11:38,430
Eu vou atopar o medio de novo.

160
00:11:38,430 --> 00:11:42,100
Eu creo que 50 foi un mal exemplo, porque eu estaba sempre botando fóra as cousas á esquerda,

161
00:11:42,100 --> 00:11:48,280
pero pola mesma medida, se eu estou buscando algo

162
00:11:48,280 --> 00:11:52,100
e é menos que o elemento Actualmente estou mirando,

163
00:11:52,100 --> 00:11:55,080
entón eu vou tirar todo á dereita.

164
00:11:55,080 --> 00:11:58,150
Entón agora necesitamos aplicar iso.

165
00:11:58,150 --> 00:12:02,310
Teña en conta que temos que pasar de tamaño.

166
00:12:02,310 --> 00:12:06,730
Non podemos tamén debe duro código de tamaño.

167
00:12:06,730 --> 00:12:11,640
Entón, se librar dese # define -

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

169
00:12:21,430 --> 00:12:27,180
Como podo moi ben imaxinar o que o tamaño da matriz de números, actualmente, é?

170
00:12:27,180 --> 00:12:30,950
>> Cantos elementos están na matriz de números?

171
00:12:30,950 --> 00:12:33,630
[Alumno] Números, soportes. Lonxitude?

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

173
00:12:36,600 --> 00:12:38,580
Precisa. Lonxitude.

174
00:12:38,580 --> 00:12:42,010
Matrices non teñen propiedades, por iso non hai propiedade de lonxitude de matrices

175
00:12:42,010 --> 00:12:45,650
que só vai dar-lle todo o tempo que pasa a ser.

176
00:12:48,180 --> 00:12:51,620
[Estudante] Ver a cantidade de memoria que ten e dividir por canto - Si >>

177
00:12:51,620 --> 00:12:55,810
Entón, como podemos ver canta memoria ten? >> [Alumno] Sizeof. >> Si, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof é o operador que vai voltar o tamaño da matriz de números.

179
00:13:01,680 --> 00:13:10,060
E iso vai ser enteiros con todo, hai moitas veces o tamaño dun enteiro

180
00:13:10,060 --> 00:13:14,050
xa que é a cantidade de memoria que está realmente tomando-se.

181
00:13:14,050 --> 00:13:17,630
Entón, se eu queira que o número de cousas na matriz,

182
00:13:17,630 --> 00:13:20,560
entón eu vou querer dividir o tamaño dun enteiro.

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

184
00:13:26,010 --> 00:13:29,430
Por qué me teño pasar en tamaño a todos?

185
00:13:29,430 --> 00:13:38,570
Por que non podo simplemente facer aquí int tamaño = sizeof (palheiro) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Por que iso non funciona?

187
00:13:41,490 --> 00:13:44,470
[Alumno] Non é unha variable global.

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

189
00:13:51,540 --> 00:13:54,700
e esta é unha especie de prenúncio do que está por vir. Si

190
00:13:54,700 --> 00:14:00,170
[Alumno] Haystack é só a referencia a el, por iso sería volver como gran referencia que é.

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

192
00:14:02,150 --> 00:14:09,000
Eu dubido que na charla que xa viu a pila aínda moi, non?

193
00:14:09,000 --> 00:14:11,270
Acaba de falar sobre iso.

194
00:14:11,270 --> 00:14:16,090
Así, a pila é onde todas as súas variables van ser gardados.

195
00:14:16,090 --> 00:14:19,960
>> Calquera memoria que está asignado para as variables locais vai na pila,

196
00:14:19,960 --> 00:14:24,790
e cada función recibe o seu propio espazo na pila, o seu cadro de pila propia é o que se chama.

197
00:14:24,790 --> 00:14:31,590
Entón principal ten o seu cadro de pila, e dentro del vai existir esa matriz de números,

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

199
00:14:34,270 --> 00:14:38,180
Vai ter o tamaño de números separados por tamaño dos elementos,

200
00:14:38,180 --> 00:14:42,010
pero que todas as vidas dentro do cadro principal de pila.

201
00:14:42,010 --> 00:14:45,190
Cando chamamos de busca, investigación recibe o seu cadro de pila propia,

202
00:14:45,190 --> 00:14:48,840
o seu propio espazo para almacenar todas as súas variables locais.

203
00:14:48,840 --> 00:14:56,420
Pero estes argumentos - así palheiro non é unha copia desta matriz enteira.

204
00:14:56,420 --> 00:15:00,990
Non pasamos en toda a matriz como unha copia en investigación.

205
00:15:00,990 --> 00:15:04,030
El só pasa unha referencia a esta matriz.

206
00:15:04,030 --> 00:15:11,470
Entón investigación pode acceder estes números a través desta referencia.

207
00:15:11,470 --> 00:15:17,100
Aínda está accedendo as cousas que viven dentro da estrutura principal da pila,

208
00:15:17,100 --> 00:15:22,990
pero, basicamente, cando chegamos aos punteiros, que debe ser en breve,

209
00:15:22,990 --> 00:15:24,980
Isto é o que os punteiros son.

210
00:15:24,980 --> 00:15:29,400
Os punteiros son só referencias a cousas, e pode usar punteiros para acceder as cousas

211
00:15:29,400 --> 00:15:32,030
que están en cadros de outras cousas "pila.

212
00:15:32,030 --> 00:15:37,660
Así, aínda que os números e lugar para o principal, que aínda pode acceder a través deste punteiro.

213
00:15:37,660 --> 00:15:41,770
Pero xa que é só un punteiro e é só unha referencia,

214
00:15:41,770 --> 00:15:45,040
sizeof (palheiro) retorna só o tamaño da propia referencia.

215
00:15:45,040 --> 00:15:47,950
Non retorna o tamaño da cousa que está a apuntar.

216
00:15:47,950 --> 00:15:51,110
Non retorna o tamaño real dos números.

217
00:15:51,110 --> 00:15:55,660
E iso non vai funcionar como queremos que el.

218
00:15:55,660 --> 00:15:57,320
>> Preguntas sobre iso?

219
00:15:57,320 --> 00:16:03,250
Punteiros será ir en detallados significativamente máis sanguento a semana que vén.

220
00:16:06,750 --> 00:16:13,740
E é por iso que unha morea de cousas que ve, cousas de busca máis ou cousas de clasificación,

221
00:16:13,740 --> 00:16:16,990
están case todos indo a necesidade de ter o tamaño real da matriz,

222
00:16:16,990 --> 00:16:20,440
porque en C, non temos idea do que o tamaño da matriz é.

223
00:16:20,440 --> 00:16:22,720
Debe manualmente pasalo dentro

224
00:16:22,720 --> 00:16:27,190
E non pode manualmente pasar en toda a matriz, porque está só de paso na referencia

225
00:16:27,190 --> 00:16:30,390
e non pode obter o tamaño da referencia.

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

227
00:16:32,300 --> 00:16:38,160
Entón, agora queremos aplicar o que foi explicado antes.

228
00:16:38,160 --> 00:16:41,530
Pode traballar con el por un minuto,

229
00:16:41,530 --> 00:16:45,250
e non ten que se preocupar en obter todo perfectamente o 100% funcionando.

230
00:16:45,250 --> 00:16:51,410
Só ten que escribir o pseudocódigo metade para como pensas que debe funcionar.

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

232
00:16:53,630 --> 00:16:56,350
Non hai necesidade de facer completamente con iso aínda.

233
00:16:56,350 --> 00:17:02,380
Pero será que alguén se sinta cómodo co que, ata agora,

234
00:17:02,380 --> 00:17:05,599
como algo que pode traballar en conxunto?

235
00:17:05,599 --> 00:17:09,690
Alguén quere ser voluntario? Ou eu vou escoller aleatoriamente.

236
00:17:12,680 --> 00:17:18,599
Non ten que estar seguro de calquera medida, senón algo que pode modificar en un estado de traballo.

237
00:17:18,599 --> 00:17:20,720
[Alumno] Claro. Ok >>.

238
00:17:20,720 --> 00:17:27,220
Entón podes gardar a revisión premendo na icona Gardar pouco.

239
00:17:27,220 --> 00:17:29,950
Vostede é Ramya, non? >> [Estudante] Yeah. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
Entón agora podo ver a súa revisión e todos poden puxar arriba a revisión.

241
00:17:35,140 --> 00:17:38,600
E aquí temos - Correcto.

242
00:17:38,600 --> 00:17:43,160
Entón Ramya foi coa solución recursiva, que é sempre unha solución válida.

243
00:17:43,160 --> 00:17:44,970
Hai dúas formas que pode facer este problema.

244
00:17:44,970 --> 00:17:48,060
Podes facelo de forma iterativa ou recursivamente.

245
00:17:48,060 --> 00:17:53,860
A maioría dos problemas que atopa o que se pode facer recursivamente tamén pode ser feito de forma iterativa.

246
00:17:53,860 --> 00:17:58,510
Entón aquí temos feito isto de forma recursiva.

247
00:17:58,510 --> 00:18:03,730
>> Será que alguén quere definir o que significa facer unha función recursiva?

248
00:18:07,210 --> 00:18:08,920
[Estudante] Cando ten unha función chamar a si mesma

249
00:18:08,920 --> 00:18:13,470
e despois chamar ata que sae con certo e verdade. Si >>.

250
00:18:13,470 --> 00:18:17,680
Unha función recursiva é só unha función que chama a si mesmo.

251
00:18:17,680 --> 00:18:24,140
Hai tres cousas grandes que unha función recursiva debe ter.

252
00:18:24,140 --> 00:18:27,310
O primeiro é, obviamente, el chama a si mesmo.

253
00:18:27,310 --> 00:18:29,650
O segundo é o caso base.

254
00:18:29,650 --> 00:18:33,390
Entón, en algún momento, a función precisa deixar de chamarse,

255
00:18:33,390 --> 00:18:35,610
e iso que o caso base é.

256
00:18:35,610 --> 00:18:43,860
Entón aquí sabemos que debemos parar, debemos dar-se en nosa procura

257
00:18:43,860 --> 00:18:48,150
cando comezo iguala final - e nós falaremos sobre o que iso significa.

258
00:18:48,150 --> 00:18:52,130
Pero, finalmente, a última cousa que é importante para funcións recursivas:

259
00:18:52,130 --> 00:18:59,250
as funcións de algunha maneira abordar o caso base.

260
00:18:59,250 --> 00:19:04,140
Como se non está realmente actualizar algo cando fai a segunda chamada recursiva,

261
00:19:04,140 --> 00:19:07,880
se está literalmente só chamando a función novo cos mesmos argumentos

262
00:19:07,880 --> 00:19:10,130
e non variables globais cambiaron ou algo,

263
00:19:10,130 --> 00:19:14,430
nunca vai chegar ao caso base, caso en que iso é malo.

264
00:19:14,430 --> 00:19:17,950
Será unha recursão infinita e un estourido de pila.

265
00:19:17,950 --> 00:19:24,330
Pero aquí vemos que a actualización está a suceder desde o inicio, estamos a actualizar + final / 2,

266
00:19:24,330 --> 00:19:28,180
estamos a actualizar o argumento final aquí, estamos a actualizar o argumento start aquí.

267
00:19:28,180 --> 00:19:32,860
Así, en todas as chamadas recursivas estamos a actualizar algo. Okay.

268
00:19:32,860 --> 00:19:38,110
Quere andar connosco a través da súa solución? >> Suposto.

269
00:19:38,110 --> 00:19:44,270
Está a usar SearchHelp de xeito que cada vez que fago esta chamada de función

270
00:19:44,270 --> 00:19:47,910
Eu teño o inicio de onde eu estou buscando na matriz e ao final

271
00:19:47,910 --> 00:19:49,380
de onde eu estou mirando a matriz.

272
00:19:49,380 --> 00:19:55,330
>> A cada paso onde está dicindo que é o elemento do medio, que é de inicio + final / 2,

273
00:19:55,330 --> 00:19:58,850
que coincide co que nós estamos a buscar?

274
00:19:58,850 --> 00:20:04,650
E se é, entón, que atopamos, e eu creo que é pasado ata os niveis de recursão.

275
00:20:04,650 --> 00:20:12,540
E se iso non é verdade, entón imos comprobar ese valor medio da matriz é moi grande,

276
00:20:12,540 --> 00:20:19,320
caso en que se mira cara á parte esquerda da matriz, indo desde o inicio ata o índice medio.

277
00:20:19,320 --> 00:20:22,710
E se non, facer a media final.

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

279
00:20:24,740 --> 00:20:27,730
É unha boa idea.

280
00:20:27,730 --> 00:20:36,640
Ok, entón un par de cousas, e en realidade, iso é unha cousa moi alto nivel

281
00:20:36,640 --> 00:20:41,270
que nunca vai ter saber para este curso, pero é verdade.

282
00:20:41,270 --> 00:20:46,080
Funcións recursivas, sempre escoita que son un mal negocio

283
00:20:46,080 --> 00:20:51,160
porque se recursivamente chamar-se moitas veces, tes de estourido de pila

284
00:20:51,160 --> 00:20:54,990
unha vez que, como dixen antes, cada función recibe o seu cadro de pila propia.

285
00:20:54,990 --> 00:20:59,500
Entón, cada chamada da función recursiva obtén a súa estrutura propia pila.

286
00:20:59,500 --> 00:21:04,140
Entón, se fai mil chamadas recursivas, recibe 1.000 cadros de pila,

287
00:21:04,140 --> 00:21:08,390
e axiña levar a ter cadros de pila máis e as cousas simplemente romper.

288
00:21:08,390 --> 00:21:13,480
É por iso que funcións recursivas son xeralmente mal.

289
00:21:13,480 --> 00:21:19,370
Pero hai un subconxunto agradable de funcións recursivas chamado rabo-recursivas funcións,

290
00:21:19,370 --> 00:21:26,120
e este pasa a ser un exemplo de un que o compilador percibe iso

291
00:21:26,120 --> 00:21:29,920
e que debería, creo eu - en Clang se pasar a O2-bandeira

292
00:21:29,920 --> 00:21:33,250
a continuación, que vai entender que é rabo recursiva e facer as cousas ben.

293
00:21:33,250 --> 00:21:40,050
>> El vai reutilizar o cadro de pila, unha e outra vez para cada chamada recursiva.

294
00:21:40,050 --> 00:21:47,010
E así dende que está a usar o cadro de pila mesmo, non se preocupe

295
00:21:47,010 --> 00:21:51,690
nunca Empilhe transbordador, e, ao mesmo tempo, como dixen antes,

296
00:21:51,690 --> 00:21:56,380
onde unha vez voltar certo, entón ten que volver a todos estes cadros de pila

297
00:21:56,380 --> 00:22:01,740
ea chamada de 10 a SearchHelp ten que volver ao 9, ten que volver ao 8.

298
00:22:01,740 --> 00:22:05,360
De xeito que non precisa ocorrer cando funcións cola recursiva.

299
00:22:05,360 --> 00:22:13,740
E entón o que fai esta cola función recursiva é aviso de que, para un convite para searchHelp

300
00:22:13,740 --> 00:22:18,470
a chamada recursiva que está facendo é o que está retornando.

301
00:22:18,470 --> 00:22:25,290
Así, en primeira chamada para SearchHelp, que quere voltar inmediatamente falso,

302
00:22:25,290 --> 00:22:29,590
voltar inmediatamente certa, ou facemos unha chamada recursiva para SearchHelp

303
00:22:29,590 --> 00:22:33,810
onde o que está retornando é o que esta chamada está retornando.

304
00:22:33,810 --> 00:22:51,560
E non podería facelo se fixemos algo así como int x = SearchHelp retorno, x * 2,

305
00:22:51,560 --> 00:22:55,440
só algunha alteración aleatoria.

306
00:22:55,440 --> 00:23:01,470
>> Entón, agora chamada esta recursiva, esta int x = SearchHelp chamada recursiva,

307
00:23:01,470 --> 00:23:05,740
xa non é rabo recursiva porque en realidade non ten que devolver

308
00:23:05,740 --> 00:23:10,400
de volta para un cadro de pila anterior de xeito que a chamada anterior para a función

309
00:23:10,400 --> 00:23:13,040
Pode, entón, facer algo co valor de retorno.

310
00:23:13,040 --> 00:23:22,190
Entón iso non é rabo recursiva, pero o que tiña antes, é ben cola recursiva. Si

311
00:23:22,190 --> 00:23:27,000
[Alumno] non debe caso base segundo verificar primeiro

312
00:23:27,000 --> 00:23:30,640
porque pode haber unha situación en que, cando pasar o argumento

313
00:23:30,640 --> 00:23:35,770
comezar = fin, pero son o valor da agulla.

314
00:23:35,770 --> 00:23:47,310
A cuestión foi que non podemos executar para o caso en que o valor final é de agulla

315
00:23:47,310 --> 00:23:52,000
ou iniciar = fin, apropiadamente, comezar final =

316
00:23:52,000 --> 00:23:59,480
e realmente non teño comprobado que un valor particular, con todo,

317
00:23:59,480 --> 00:24:03,910
a continuación, iniciar + final / 2 é só vai ser o mesmo valor.

318
00:24:03,910 --> 00:24:07,890
Pero nós xa regresou falso e nós nunca realmente comprobado o valor.

319
00:24:07,890 --> 00:24:14,240
Entón, como mínimo, en primeira convocatoria, o tamaño é 0, entón queremos volver falso.

320
00:24:14,240 --> 00:24:17,710
Pero se o tamaño é 1, entón de inicio non vai acabar igual,

321
00:24:17,710 --> 00:24:19,820
e nós imos polo menos comprobar a un elemento.

322
00:24:19,820 --> 00:24:26,750
Pero eu creo que está certo en que pode acabar nun caso onde comezar + final / 2,

323
00:24:26,750 --> 00:24:31,190
inicio acaba sendo o mesmo que de inicio + final / 2,

324
00:24:31,190 --> 00:24:35,350
pero nós nunca realmente comprobado ese elemento.

325
00:24:35,350 --> 00:24:44,740
>> Entón, se nós primeiro comprobar que o elemento do medio o valor que está a buscar,

326
00:24:44,740 --> 00:24:47,110
entón podemos voltar inmediatamente certo.

327
00:24:47,110 --> 00:24:50,740
Máis se son iguais, non hai sentido en continuar

328
00:24:50,740 --> 00:24:58,440
xa que estamos indo só para actualizar a un caso en que estamos en unha matriz de elementos único.

329
00:24:58,440 --> 00:25:01,110
Se ese elemento único non é o que estamos a buscar,

330
00:25:01,110 --> 00:25:03,530
entón está todo mal. Si

331
00:25:03,530 --> 00:25:08,900
[Estudante] O problema é que unha vez que o tamaño é realmente maior que o número de elementos na matriz,

332
00:25:08,900 --> 00:25:13,070
Xa existe un desprazamento - >> Entón vai tamaño -

333
00:25:13,070 --> 00:25:19,380
[Alumno] Dicir a matriz foi tamaño 0, entón o SearchHelp vai realmente comprobar palheiro de 0

334
00:25:19,380 --> 00:25:21,490
na primeira chamada.

335
00:25:21,490 --> 00:25:25,300
A matriz ten tamaño 0, de modo que o 0 é - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Hai outra cousa que - que podería ser bo. Imos pensar.

337
00:25:30,750 --> 00:25:40,120
Entón, se a matriz tiña 10 elementos e un medio que imos comprobar se o índice de 5,

338
00:25:40,120 --> 00:25:45,700
por iso estamos comprobando 5, e imos dicir que o valor é menor.

339
00:25:45,700 --> 00:25:50,720
Entón, nós estamos xogando todo fóra de 5 en diante.

340
00:25:50,720 --> 00:25:54,030
Entón comeza a + final / 2 vai ser o noso novo fin,

341
00:25:54,030 --> 00:25:57,450
Entón, si, el sempre vai estar máis aló do fin da matriz.

342
00:25:57,450 --> 00:26:03,570
Se é un caso era par ou impar, entón poderiamos comprobar, por exemplo, 4,

343
00:26:03,570 --> 00:26:05,770
pero aínda estamos xogando fóra -

344
00:26:05,770 --> 00:26:13,500
Entón, si, o fin é sempre vai ser ademais do fin real da matriz.

345
00:26:13,500 --> 00:26:18,350
Así, os elementos que estamos focando, final é sempre vai ser o un despois.

346
00:26:18,350 --> 00:26:24,270
E así se fai sempre comezo final igual, estamos nunha matriz de tamaño 0.

347
00:26:24,270 --> 00:26:35,600
>> A outra cousa que eu estaba a pensar que estamos a actualizar inicio para comezar a ser + final / 2,

348
00:26:35,600 --> 00:26:44,020
por iso este é o caso que eu estou a ter problemas con onde comezar + final / 2

349
00:26:44,020 --> 00:26:46,820
é o elemento que estamos comprobando.

350
00:26:46,820 --> 00:26:58,150
Imos dicir que tivemos esa matriz de 10 elementos. Calquera que sexa.

351
00:26:58,150 --> 00:27:03,250
Entón comeza a + final / 2 vai ser algo así como este,

352
00:27:03,250 --> 00:27:07,060
e se iso non é o valor, digamos que quere actualizar.

353
00:27:07,060 --> 00:27:10,060
O valor é maior, por iso queremos mirar para esta metade da matriz.

354
00:27:10,060 --> 00:27:15,910
Entón, como estamos a actualizar inicio, estamos a actualizar inicio para agora ser ese elemento.

355
00:27:15,910 --> 00:27:23,790
Pero iso aínda pode traballar, ou polo menos, pode facer start + final / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Alumno] Non precisa ser comezar final + [inaudível] >> Yeah.

357
00:27:27,850 --> 00:27:33,240
Nós xa comprobada este elemento e sei que non é o que estamos a buscar.

358
00:27:33,240 --> 00:27:36,800
Polo tanto, non é necesario actualizar inicio para este elemento.

359
00:27:36,800 --> 00:27:39,560
Podemos simplemente ignore-lo e actualizar comezar a ser este elemento.

360
00:27:39,560 --> 00:27:46,060
E sempre hai un caso, imos dicir que este fose final,

361
00:27:46,060 --> 00:27:53,140
así, entón comezar sería iso, inicie + final / 2 sería este,

362
00:27:53,140 --> 00:28:00,580
comezar a final + - Si, eu creo que pode acabar en recursão infinita.

363
00:28:00,580 --> 00:28:12,690
Imos dicir que é só unha matriz de tamaño 2 ou unha matriz de tamaño 1. Eu creo que iso vai funcionar.

364
00:28:12,690 --> 00:28:19,490
Así, actualmente, é que inicio e fin elemento é un alá.

365
00:28:19,490 --> 00:28:24,110
Así, o elemento que imos comprobar é este,

366
00:28:24,110 --> 00:28:29,400
e entón, cando actualizamos inicio, estamos a actualizar inicio para ser 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
que vai acabar nos de volta con saída sendo este elemento.

368
00:28:33,160 --> 00:28:36,210
>> Entón, nós estamos comprobando o mesmo elemento e outra vez.

369
00:28:36,210 --> 00:28:43,310
Polo tanto, este é o caso en que cada chamada recursiva que realmente actualizar algo.

370
00:28:43,310 --> 00:28:48,370
Entón, necesitamos facer start + final / 2 + 1, ou ben hai un caso

371
00:28:48,370 --> 00:28:50,710
onde non estamos realmente actualizar inicio.

372
00:28:50,710 --> 00:28:53,820
Todo o mundo ve isto?

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

374
00:28:56,310 --> 00:29:03,860
Alguén ten preguntas sobre esta solución ou comentarios máis?

375
00:29:05,220 --> 00:29:10,280
Okay. Alguén ten unha solución iterativa que todos podemos mirar?

376
00:29:17,400 --> 00:29:20,940
Será que todos nós facemos iso recursivamente?

377
00:29:20,940 --> 00:29:25,950
Ou eu tamén creo que se abre o seu, entón vostede pode ter substituído o seu anterior.

378
00:29:25,950 --> 00:29:28,810
Será que gardar automaticamente? Eu non son positivos.

379
00:29:35,090 --> 00:29:39,130
Alguén ten iterativo?

380
00:29:39,130 --> 00:29:42,430
Podemos camiñar con el xunto, se non.

381
00:29:46,080 --> 00:29:48,100
A idea de que vai ser o mesmo.

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

383
00:30:02,830 --> 00:30:07,140
Nós imos querer facer basicamente a mesma idea

384
00:30:07,140 --> 00:30:16,530
onde queremos seguir o novo fin da matriz e do novo comezo da matriz

385
00:30:16,530 --> 00:30:18,510
e facelo máis e máis.

386
00:30:18,510 --> 00:30:22,430
E se o que estamos mantendo o control de como o inicio eo fin non se cruzan,

387
00:30:22,430 --> 00:30:29,020
entón non atopalo e podemos voltar falso.

388
00:30:29,020 --> 00:30:37,540
Entón, como podo facer iso? Alguén ten suxerencias ou código para me puxar arriba?

389
00:30:42,190 --> 00:30:47,450
[Alumno] Fai un loop while. Si >>.

390
00:30:47,450 --> 00:30:49,450
Vai querer facer un loop.

391
00:30:49,450 --> 00:30:51,830
>> Será que ten o código que eu podería tirar cara arriba, ou o que estaba indo a suxerir?

392
00:30:51,830 --> 00:30:56,340
[Alumno] Coido que si. >> Todo ben. Isto fai as cousas máis fáciles. Cal era o seu nome?

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

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

395
00:31:04,190 --> 00:31:13,200
Baixo é o que chamamos comezar antes.

396
00:31:13,200 --> 00:31:17,080
Se non é o que chamamos final antes.

397
00:31:17,080 --> 00:31:22,750
En realidade, o fin agora dentro da matriz. É un elemento que debemos considerar.

398
00:31:22,750 --> 00:31:26,890
Tan baixa é 0, se é o tamaño da matriz - 1,

399
00:31:26,890 --> 00:31:34,780
e agora estamos looping, e estamos comprobando -

400
00:31:34,780 --> 00:31:37,340
Eu creo que pode andar por ela.

401
00:31:37,340 --> 00:31:41,420
Cal foi o seu pensamento por iso? Ande connosco a través do seu código.

402
00:31:41,420 --> 00:31:49,940
[Alumno] Claro. Vexa o valor palheiro no medio e comparalos-lo con agulla.

403
00:31:49,940 --> 00:31:58,520
Entón, se é maior que a agulla, entón quere - Oh, en realidade, que debe ser para atrás.

404
00:31:58,520 --> 00:32:05,180
Vai querer tirar a metade dereita, e entón si, que debe ser o camiño.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Polo tanto, este debe ser menos? É iso que dixo? >> [Estudante] Yeah.

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

407
00:32:10,390 --> 00:32:15,700
Entón, o que estamos vendo é menor que o que queremos,

408
00:32:15,700 --> 00:32:19,410
entón si, queremos tirar a metade esquerda,

409
00:32:19,410 --> 00:32:22,210
o que significa que estamos a actualizar todo o que estamos considerando

410
00:32:22,210 --> 00:32:26,610
movendo baixo á dereita da matriz.

411
00:32:26,610 --> 00:32:30,130
Este parece ser bo.

412
00:32:30,130 --> 00:32:34,550
Eu creo que ten o mesmo problema que nós dixemos que o anterior,

413
00:32:34,550 --> 00:32:49,760
onde se baixa é 0 e no 1, entón baixo a + / 2 vai definir ata que a mesma cousa de novo.

414
00:32:49,760 --> 00:32:53,860
>> E mesmo se ese non é o caso, é aínda máis eficiente como mínimo

415
00:32:53,860 --> 00:32:57,630
só para xogar fora o elemento que só mirou para que sabemos que é malo.

416
00:32:57,630 --> 00:33:03,240
Entón baixo + arriba / 2 + 1 - >> [alumno], que debería ser o contrario.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Ou este debe ser - 1 e outro debe ser + 1.

418
00:33:05,900 --> 00:33:09,580
[Alumno] E non debe ser un dobre signo igual. >> [Bowden] Yeah.

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

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

421
00:33:15,910 --> 00:33:21,280
E, finalmente, agora que temos este 1 + - 1 cousa,

422
00:33:21,280 --> 00:33:31,520
é - non pode ser - é sempre posible para abaixo para acabar con un valor maior que para arriba?

423
00:33:35,710 --> 00:33:40,320
Eu creo que a única forma que pode ocorrer - É posíbel? >> [Alumno] non sei.

424
00:33:40,320 --> 00:33:45,220
Pero se queda truncado e logo recibe menos que 1 e despois - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Alumno] Sería posiblemente ficar confuso.

426
00:33:49,700 --> 00:33:53,940
Eu creo que debe ser bo só porque

427
00:33:53,940 --> 00:33:58,800
para que acabe menor que tería que ser igual, eu creo.

428
00:33:58,800 --> 00:34:03,070
Pero se son iguais, non tería feito o loop while para comezar

429
00:34:03,070 --> 00:34:06,670
e nós só tería devolto o valor. Entón, eu creo que estamos ben agora.

430
00:34:06,670 --> 00:34:11,530
Nótese que, aínda que este problema xa non é recursivo,

431
00:34:11,530 --> 00:34:17,400
o mesmo tipo de ideas aplicar onde podemos ver como iso tan facilmente se presta

432
00:34:17,400 --> 00:34:23,659
a unha solución recursiva polo feito de que nós estamos só actualización dos índices e outra vez,

433
00:34:23,659 --> 00:34:29,960
estamos facendo o problema cada vez menor, estamos concentrando en un subconxunto da matriz.

434
00:34:29,960 --> 00:34:40,860
[Estudante] baixo é 0 e no 1, ambos estarían 0 + 1/2, que ía a 0,

435
00:34:40,860 --> 00:34:44,429
e, a continuación, un sería + 1, pode-se ser - 1.

436
00:34:47,000 --> 00:34:50,870
[Alumno] Onde estamos comprobando a igualdade?

437
00:34:50,870 --> 00:34:55,100
Como se o medio é realmente agulla?

438
00:34:55,100 --> 00:34:58,590
Non estamos facendo actualmente isto? Oh!

439
00:35:00,610 --> 00:35:02,460
Se isto é -

440
00:35:05,340 --> 00:35:13,740
Si Non podemos simplemente facer a proba aquí porque imos dicir que a primeira metade -

441
00:35:13,740 --> 00:35:16,430
[Alumno] É realmente como non tirar o límite.

442
00:35:16,430 --> 00:35:20,220
Entón, se tirar o salto, ten que comprobar primeiro ou o que quere.

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

444
00:35:23,350 --> 00:35:29,650
Polo tanto, agora temos xogado fóra o que actualmente mirou,

445
00:35:29,650 --> 00:35:33,260
o que significa que nós agora precisamos ter

446
00:35:33,260 --> 00:35:44,810
if (palheiro [(+ abaixo) / 2] == agulla), entón podemos voltar true.

447
00:35:44,810 --> 00:35:52,070
E se eu poñer máis ou só se, significa literalmente o mesmo

448
00:35:52,070 --> 00:35:57,110
porque este tería retornado verdade.

449
00:35:57,110 --> 00:36:01,450
Entón, eu vou poñer máis, pero iso non importa.

450
00:36:01,450 --> 00:36:10,440
>> Entón, máis se iso, máis iso, e iso é unha cousa común que fago

451
00:36:10,440 --> 00:36:14,340
onde incluso se é o caso, onde todo é bo aquí,

452
00:36:14,340 --> 00:36:22,780
como baixo non pode ser maior que se non é o razoamento que paga a pena saber se iso é verdade.

453
00:36:22,780 --> 00:36:28,010
Así, pode dicir mentres abaixo é menor que ou igual a

454
00:36:28,010 --> 00:36:30,720
ou mentres baixo é inferior a

455
00:36:30,720 --> 00:36:35,300
por iso, se son sempre iguais ou baixa acontece a pasar-se,

456
00:36:35,300 --> 00:36:40,130
entón podemos romper este ciclo.

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

458
00:36:47,080 --> 00:36:49,270
Okay. Este parece ser bo.

459
00:36:49,270 --> 00:36:52,230
Agora queremos facer tipo.

460
00:36:52,230 --> 00:37:04,030
Ou tamén a miña segunda revisión, vemos eses mesmos números,

461
00:37:04,030 --> 00:37:07,550
pero agora eles non están máis en orde de clasificación.

462
00:37:07,550 --> 00:37:12,840
E nós queremos aplicar ordenación usando calquera algoritmo en O de n log n.

463
00:37:12,840 --> 00:37:17,240
Así que o algoritmo que pensas que debe aplicar aquí? >> [Alumno] tipo Merge.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Merge sort é O (n log n), de xeito que é o que imos facer.

465
00:37:23,810 --> 00:37:26,680
E o problema vai ser moi semellante,

466
00:37:26,680 --> 00:37:31,920
onde se presta facilmente a unha solución recursiva.

467
00:37:31,920 --> 00:37:35,580
Tamén podemos chegar a unha solución iterativa, se quere,

468
00:37:35,580 --> 00:37:42,540
pero recursão será máis fácil aquí e nós temos que facer a recursividade.

469
00:37:45,120 --> 00:37:49,530
Creo que imos camiñar por merge sort primeiro,

470
00:37:49,530 --> 00:37:54,280
aínda que haxa un vídeo bonito en merge sort xa. [Risas]

471
00:37:54,280 --> 00:37:59,780
Entón, merge sort existen - Estou perdendo moito deste traballo.

472
00:37:59,780 --> 00:38:02,080
Oh, hai só unha esquerda.

473
00:38:02,080 --> 00:38:03,630
Entón, se funden.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge leva dúas matrices distintas.

477
00:38:33,460 --> 00:38:36,780
Individualmente as dúas matrices son ambos clasificados.

478
00:38:36,780 --> 00:38:40,970
Entón, esa matriz, 1, 3, 5, clasificados. Esta matriz, 0, 2, 4, clasificados.

479
00:38:40,970 --> 00:38:46,710
Agora, o que debe facer é mesturar combina-los nunha única matriz que é en si clasificados.

480
00:38:46,710 --> 00:38:57,130
Entón, nós queremos unha matriz de tamaño 6, que vai ter eses elementos dentro del

481
00:38:57,130 --> 00:38:59,390
en orde de clasificación.

482
00:38:59,390 --> 00:39:03,390
>> E así podemos aproveitar do feito de que estas dúas matrices son clasificadas

483
00:39:03,390 --> 00:39:06,800
facelo en tempo lineal,

484
00:39:06,800 --> 00:39:13,510
significado de tempo lineal esa matriz é x tamaño e este é y tamaño,

485
00:39:13,510 --> 00:39:20,970
entón o algoritmo total debe ser o (x + y). Okay.

486
00:39:20,970 --> 00:39:23,150
Así suxestións.

487
00:39:23,150 --> 00:39:26,030
[Alumno] Poderiamos comezar a partir da esquerda?

488
00:39:26,030 --> 00:39:30,150
Entón vai poñer a 0 para abaixo primeiro e despois a 1 e, a continuación, aquí está no 2.

489
00:39:30,150 --> 00:39:33,320
Entón é tipo de como ten unha guía que se está movendo cara a dereita. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Para ambas as matrices concentrarse só no elemento máis á esquerda.

491
00:39:41,070 --> 00:39:43,530
Porque ambas as matrices son clasificadas, sabemos que eses dous elementos

492
00:39:43,530 --> 00:39:46,920
son os máis pequenos elementos nun array.

493
00:39:46,920 --> 00:39:53,500
Entón isto significa que un deses dous elementos debe ser o menor elemento na nosa matriz resultante da fusión.

494
00:39:53,500 --> 00:39:58,190
O que pasa é que o menor é o tempo este dereito.

495
00:39:58,190 --> 00:40:02,580
Entón, tomamos 0, introduce o á esquerda porque 0 é menor que 1,

496
00:40:02,580 --> 00:40:08,210
así que tomar 0, inserir-lo na nosa primeira posición, e despois actualizar esta

497
00:40:08,210 --> 00:40:12,070
para concentrarse en primeiro elemento.

498
00:40:12,070 --> 00:40:14,570
E agora imos repetir.

499
00:40:14,570 --> 00:40:20,670
Entón agora nós comparar 2 e 1. 1 é menor, polo que imos inserir unha.

500
00:40:20,670 --> 00:40:25,300
Nós actualizar este punteiro para apuntar para este cara.

501
00:40:25,300 --> 00:40:33,160
Agora imos facelo de novo, entón 2. Isto actualizar, comparar estes 2, 3.

502
00:40:33,160 --> 00:40:37,770
Isto actualiza, despois 4 e 5.

503
00:40:37,770 --> 00:40:42,110
De xeito que é de mesclagem.

504
00:40:42,110 --> 00:40:49,010
>> Que debe ser bastante obvio que é o tempo lineal, xa que só tes que ir en cada elemento dunha vez.

505
00:40:49,010 --> 00:40:55,980
E ese é o maior paso para a implantación de merge sort está facendo iso.

506
00:40:55,980 --> 00:40:59,330
E non é tan difícil.

507
00:40:59,330 --> 00:41:15,020
Algunhas cousas para se preocupar e imos dicir que foron fusión 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Neste caso, imos acabar no escenario onde este vai ser menor,

509
00:41:30,930 --> 00:41:36,160
entón nós actualizamos este punteiro, este vai ser menor, actualizar esta,

510
00:41:36,160 --> 00:41:41,280
este é menor, e agora ten que recoñecer

511
00:41:41,280 --> 00:41:44,220
cando realmente ficar sen elementos para comparar.

512
00:41:44,220 --> 00:41:49,400
Unha vez que xa utilizaron este matriz enteira,

513
00:41:49,400 --> 00:41:55,190
todo nesta matriz é agora só inserido aquí.

514
00:41:55,190 --> 00:42:02,040
Entón, se nós nunca executar para o punto onde unha das nosas matrices é completamente fundidas xa,

515
00:42:02,040 --> 00:42:06,510
entón simplemente tomar todos os elementos da matriz que non e inserir-las no fin do array.

516
00:42:06,510 --> 00:42:13,630
Así, podemos só engadir 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Iso é unha cousa a observar.

518
00:42:22,080 --> 00:42:26,120
De aplicación que debe ser o paso 1.

519
00:42:26,120 --> 00:42:32,600
Mesturar clasificar, entón con base niso, que é dúas etapas, dúas etapas de bobos.

520
00:42:38,800 --> 00:42:42,090
Imos dar esa matriz.

521
00:42:57,920 --> 00:43:05,680
Entón, merge sort, etapa 1 é recursivamente romper a matriz en metades.

522
00:43:05,680 --> 00:43:09,350
Entón, dividir esa matriz en metades.

523
00:43:09,350 --> 00:43:22,920
Temos, agora, 4, 15, 16, 50 e 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
E agora nós facelo de novo e nós dividimos estas en metades.

525
00:43:25,800 --> 00:43:27,530
Eu só vou facer iso deste lado.

526
00:43:27,530 --> 00:43:34,790
Entón, 4, 15 e 16, 50.

527
00:43:34,790 --> 00:43:37,440
Queremos facer o mesmo aquí.

528
00:43:37,440 --> 00:43:40,340
E agora nós dividídelo en dúas metades de novo.

529
00:43:40,340 --> 00:43:51,080
E nós temos 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Entón, ese é o noso caso base.

531
00:43:53,170 --> 00:44:00,540
Unha vez que as matrices son de tamaño 1, entón imos parar coa división en dúas metades.

532
00:44:00,540 --> 00:44:03,190
>> Agora o que imos facer con iso?

533
00:44:03,190 --> 00:44:15,730
Imos acabar isto tamén se dividen en 8, 23, 42 e 108.

534
00:44:15,730 --> 00:44:24,000
Entón, agora que estamos neste momento, agora o segundo paso merge sort é só fusión pares para as listas.

535
00:44:24,000 --> 00:44:27,610
Entón, nós queremos unir estes. Nós só chamar fundir.

536
00:44:27,610 --> 00:44:31,410
Sabemos fusión volverá estes en orde de clasificación.

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

538
00:44:33,920 --> 00:44:41,440
Agora, queremos xuntar estas, e que vai voltar unha lista con aqueles en orde de clasificación,

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

540
00:44:44,160 --> 00:44:57,380
Quedamos os - Eu non podo escribir - 8, 23 e 42, 108.

541
00:44:57,380 --> 00:45:02,890
Polo tanto, temos pares incorporadas unha vez.

542
00:45:02,890 --> 00:45:05,140
Agora só fundir de novo.

543
00:45:05,140 --> 00:45:10,130
Teña en conta que cada unha destas listas é clasificada en si,

544
00:45:10,130 --> 00:45:15,220
e entón podemos só mesturar estas listas para obter unha lista de tamaño 4, que se clasifica

545
00:45:15,220 --> 00:45:19,990
e mesturar estas dúas listas para obter unha lista de tamaño 4, que está clasificada.

546
00:45:19,990 --> 00:45:25,710
E, finalmente, podemos mesturar estas dúas listas de tamaño 4 para obter unha lista de tamaño 8, que está clasificada.

547
00:45:25,710 --> 00:45:34,030
Entón, a ver que este é global n log n, xa vimos que mesclagem é lineal,

548
00:45:34,030 --> 00:45:40,390
Entón, cando estamos lidando con a unión destes, así como o custo global de fusión

549
00:45:40,390 --> 00:45:43,410
para estas dúas listas é só 2 porque -

550
00:45:43,410 --> 00:45:49,610
Ou ben, é o de n, pero n aquí é só eses dous elementos, por iso é 2.

551
00:45:49,610 --> 00:45:52,850
E estes dous será 2 e estes dous será 2 e estes 2 vai ser 2,

552
00:45:52,850 --> 00:45:58,820
así en todas as fusións que temos que facer, acabamos facendo n.

553
00:45:58,820 --> 00:46:03,210
Como 2 + 2 + 2 + 2 é de 8, que é n,

554
00:46:03,210 --> 00:46:08,060
de xeito que o custo de fusión neste conxunto é n.

555
00:46:08,060 --> 00:46:10,810
E entón o mesmo aquí.

556
00:46:10,810 --> 00:46:16,980
Imos xuntar estas dúas, entón estes dous e, individualmente, esta fusión terá catro operacións,

557
00:46:16,980 --> 00:46:23,610
esta fusión terá catro operacións, pero, unha vez máis, entre todos eles,

558
00:46:23,610 --> 00:46:29,030
acabamos fusión n cousas totais, e por iso este paso leva n.

559
00:46:29,030 --> 00:46:33,670
E así cada nivel ten n elementos a seren reunidos.

560
00:46:33,670 --> 00:46:36,110
>> E cantos son os niveis?

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

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

563
00:46:44,590 --> 00:46:46,470
e, finalmente, son de tamaño 8.

564
00:46:46,470 --> 00:46:56,450
Entón, unha vez que está dobrando, non van ser un total de log n destes niveis.

565
00:46:56,450 --> 00:47:02,090
Así, co rexistro de n niveis, cada nivel individual, tendo n total de operacións,

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

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

568
00:47:08,940 --> 00:47:13,320
Xa as persoas xa fixeron progresos sobre como implementar isto?

569
00:47:13,320 --> 00:47:18,260
Será que alguén xa nun estado onde eu só podo tirar para arriba o seu código?

570
00:47:20,320 --> 00:47:22,260
Eu podo darlle un minuto.

571
00:47:24,770 --> 00:47:27,470
Este vai ser máis longo.

572
00:47:27,470 --> 00:47:28,730
Eu recomendo se repiten -

573
00:47:28,730 --> 00:47:30,510
Non ten que facer recursão para fusión

574
00:47:30,510 --> 00:47:33,750
porque para facer recursão para mesclagem, vai ter que pasar por unha chea de diferentes tamaños.

575
00:47:33,750 --> 00:47:37,150
Pode, pero é irritante.

576
00:47:37,150 --> 00:47:43,720
Pero recursão para clasificar-se é moi doado.

577
00:47:43,720 --> 00:47:49,190
Só literalmente chamar especie na metade esquerda, tipo na metade dereita. Okay.

578
00:47:51,770 --> 00:47:54,860
Alguén ten algunha cousa que podo tirar para arriba aínda?

579
00:47:54,860 --> 00:47:57,540
Ou entón eu vou dar un minuto.

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

581
00:47:59,900 --> 00:48:02,970
Alguén ten algo que podemos traballar?

582
00:48:05,450 --> 00:48:09,680
Ou entón nós imos traballar con iso e, a continuación, ampliar a partir de aí.

583
00:48:09,680 --> 00:48:14,050
>> Alguén ten máis que iso que podo tirar para arriba?

584
00:48:14,050 --> 00:48:17,770
[Estudante] Yeah. Podes puxar a miña. >> Todo ben.

585
00:48:17,770 --> 00:48:19,730
Si!

586
00:48:22,170 --> 00:48:25,280
[Alumno] Había unha serie de condicións. >> Oh, tirar. Pode -

587
00:48:25,280 --> 00:48:28,110
[Estudante] Eu teño que salvalo. Si >>.

588
00:48:32,420 --> 00:48:35,730
Entón nós fixemos a fusión por separado.

589
00:48:35,730 --> 00:48:38,570
Ah, pero non é tan malo así.

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

591
00:48:41,650 --> 00:48:47,080
Entón tipo é en si só chamando mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Explique-nos o que mergeSortHelp fai.

593
00:48:49,530 --> 00:48:55,700
[Alumno] MergeSortHelp practicamente fai as dúas etapas principais,

594
00:48:55,700 --> 00:49:01,270
que é o de clasificar cada metade da matriz e, a continuación, para fundir os dous.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Ok, entón me dea un segundo.

596
00:49:10,850 --> 00:49:13,210
Eu creo que iso - >> [alumno] eu teño -

597
00:49:17,100 --> 00:49:19,400
Si Eu estou sentindo falta de algo.

598
00:49:19,400 --> 00:49:23,100
Na fusión, podo entender que eu teño para crear unha nova matriz

599
00:49:23,100 --> 00:49:26,530
porque eu non podería facelo no lugar. Si >>. Vostede non pode. Corrixir.

600
00:49:26,530 --> 00:49:28,170
[Estudante] Entón eu crear unha nova matriz.

601
00:49:28,170 --> 00:49:31,510
Esquecín o meu a finais de fundir a re-cambiar.

602
00:49:31,510 --> 00:49:34,490
Okay. Necesitamos unha nova matriz.

603
00:49:34,490 --> 00:49:41,000
En merge sort, iso é case sempre certo.

604
00:49:41,000 --> 00:49:44,340
Parte do custo dun algoritmo de mellor en termos de tempo

605
00:49:44,340 --> 00:49:47,310
é case sempre a necesidade de usar a memoria un pouco máis.

606
00:49:47,310 --> 00:49:51,570
Entón, aquí, non importa como facer merge sort,

607
00:49:51,570 --> 00:49:54,780
vostede inevitablemente ten que utilizar un pouco de memoria extra.

608
00:49:54,780 --> 00:49:58,240
El ou ela creou unha nova matriz.

609
00:49:58,240 --> 00:50:03,400
E entón vostede di, ao final, só precisa copiar nova matriz para a matriz orixinal.

610
00:50:03,400 --> 00:50:04,830
[Estudante] Coido que si.

611
00:50:04,830 --> 00:50:08,210
Eu non sei se isto funciona en termos de contador de referencia ou o que sexa -

612
00:50:08,210 --> 00:50:11,650
Si, vai funcionar. >> [Alumno] Okay.

613
00:50:20,620 --> 00:50:24,480
Será que intente realizar isto? >> [Alumno] Non, aínda non. Ok >>.

614
00:50:24,480 --> 00:50:28,880
Probe executa-lo, e entón eu vou falar sobre iso por un segundo.

615
00:50:28,880 --> 00:50:35,200
[Alumno] Eu preciso ter todos os prototipos de función e todo, non?

616
00:50:37,640 --> 00:50:40,840
Os prototipos de función. Ah, quere dicir como - Si

617
00:50:40,840 --> 00:50:43,040
Ordenar está chamando mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Entón, para que tipo de chamar mergeSortHelp, mergeSortHelp debe ser definido

619
00:50:47,390 --> 00:50:56,370
antes tipo ou só necesitamos do prototipo. Basta copiar e pegar isto.

620
00:50:56,370 --> 00:50:59,490
E do mesmo xeito, mergeSortHelp está chamando fundir,

621
00:50:59,490 --> 00:51:03,830
pero mesclagem non foi definido aínda, entón nós podemos só deixar mergeSortHelp saber

622
00:51:03,830 --> 00:51:08,700
que é iso que vai fundir a aparencia, e que é iso.

623
00:51:09,950 --> 00:51:15,730
Entón mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Temos un problema aquí, onde temos ningún caso base.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp é recursiva, calquera función recursiva

626
00:51:38,110 --> 00:51:42,610
Vai ter algún tipo de caso base para saber cando deixar de chamar recursivamente si.

627
00:51:42,610 --> 00:51:45,590
O que é o noso caso base vai ser aquí? Si

628
00:51:45,590 --> 00:51:49,110
[Estudante] Se o tamaño é 1? >> [Bowden] Si

629
00:51:49,110 --> 00:51:56,220
Entón, como se viu alí, paramos matrices de división

630
00:51:56,220 --> 00:52:01,850
Unha vez que temos en matrices de tamaño 1, que inevitablemente están clasificados si.

631
00:52:01,850 --> 00:52:09,530
Entón, se o tamaño é igual a 1, sabemos que a matriz xa está clasificado,

632
00:52:09,530 --> 00:52:12,970
para que poidamos voltar só.

633
00:52:12,970 --> 00:52:16,880
>> Teña en conta que é baleiro, de modo que non voltar nada especial, só devolver.

634
00:52:16,880 --> 00:52:19,580
Okay. Entón, ese é o noso caso base.

635
00:52:19,580 --> 00:52:27,440
Eu creo que o noso caso base tamén podería ser se ocorrer de ser fusión dunha matriz de tamaño 0,

636
00:52:27,440 --> 00:52:30,030
Nós probablemente quere deixar nalgún momento,

637
00:52:30,030 --> 00:52:33,610
Así, podemos dicir tamaño inferior a 2 ou inferior ou igual a 1

638
00:52:33,610 --> 00:52:37,150
de xeito que iso vai funcionar para calquera matriz agora.

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

640
00:52:38,870 --> 00:52:42,740
Entón, ese é o noso caso base.

641
00:52:42,740 --> 00:52:45,950
Agora se quere andar connosco a través fusión?

642
00:52:45,950 --> 00:52:49,140
O que todos estes casos significa?

643
00:52:49,140 --> 00:52:54,480
Ata aquí, nós estamos só facendo a mesma idea, o -

644
00:52:56,970 --> 00:53:02,470
[Estudante] Eu teño estar pasando tamaño, con todas as chamadas mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Eu engade tamaño como unha primaria adicional e que non está aí, como o tamaño / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, tamaño / 2, tamaño / 2. >> [Estudante] É, e tamén na función anterior, así.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Aquí? >> [Alumno] Só o tamaño. >> [Bowden] Oh Tamaño, tamaño? >> [Estudante] Yeah.

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

649
00:53:23,010 --> 00:53:26,580
Deixe-me pensar por un segundo.

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

651
00:53:28,780 --> 00:53:33,690
Estamos sempre tratar a esquerda como 0. >> [Alumno] Non

652
00:53:33,690 --> 00:53:36,340
Isto é malo tamén. Sentímolo. Debe ser partida. Si

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Gústame que mellor.

654
00:53:39,230 --> 00:53:43,880
E fin. Okay.

655
00:53:43,880 --> 00:53:47,200
Entón agora quere andar connosco a través fusión? >> [Alumno] Okay.

656
00:53:47,200 --> 00:53:52,150
Eu só estou pasando esta nova matriz que eu creei.

657
00:53:52,150 --> 00:53:57,420
O seu tamaño é o tamaño da parte da matriz que queremos ser clasificados

658
00:53:57,420 --> 00:54:03,460
e tentando atopar o elemento que eu debería poñer na etapa nova matriz.

659
00:54:03,460 --> 00:54:10,140
Entón, para facelo, primeiro eu estou comprobando a metade esquerda da matriz segue a ter máis elementos,

660
00:54:10,140 --> 00:54:14,260
e se iso non acontecer, entón vai para abaixo para que a condición máis, que só di

661
00:54:14,260 --> 00:54:20,180
Todo ben, debe estar no dereito de matriz, e imos poñer isto no índice actual de newArray.

662
00:54:20,180 --> 00:54:27,620
>> E entón, doutro xeito, eu estou comprobando o lado dereito da matriz tamén está rematado,

663
00:54:27,620 --> 00:54:30,630
caso en que eu só poñer na esquerda.

664
00:54:30,630 --> 00:54:34,180
Isto pode non ser realmente necesario. Non estou seguro.

665
00:54:34,180 --> 00:54:40,970
Pero de calquera xeito, a verificación de outros dous cal dos dous son menores na esquerda ou na dereita.

666
00:54:40,970 --> 00:54:49,770
E tamén, en cada caso, estou incrementando o que incrementar espazo reservado.

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

668
00:54:52,040 --> 00:54:53,840
Isto parece bo.

669
00:54:53,840 --> 00:54:58,800
Alguén ten comentarios ou preguntas ou preguntas?

670
00:55:00,660 --> 00:55:07,720
Así, os catro casos que temos que levar as cousas en só sendo - ou parece que cinco -

671
00:55:07,720 --> 00:55:13,100
pero temos que considerar a matriz de esquerda non ten máis cousas que necesitamos fundir,

672
00:55:13,100 --> 00:55:16,390
o dereito de matriz non ten máis cousas que precisamos unir -

673
00:55:16,390 --> 00:55:18,400
Estou apuntando para o nada.

674
00:55:18,400 --> 00:55:21,730
Entón, a matriz de esquerda non ten máis cousas ou o dereito de matriz non ten máis cousas.

675
00:55:21,730 --> 00:55:24,320
Estes son dous casos.

676
00:55:24,320 --> 00:55:30,920
Necesitamos tamén dun caso trivial de se a cousa esquerdo é menor que as cousas ben.

677
00:55:30,920 --> 00:55:33,910
Entón, nós queremos elixir a cousa esquerdo.

678
00:55:33,910 --> 00:55:37,630
Estes son os casos.

679
00:55:37,630 --> 00:55:40,990
Entón iso era certo, entón é iso.

680
00:55:40,990 --> 00:55:46,760
Matriz esquerda. E 1, 2, 3. Okay. Entón, si, esas son as catro cousas que pode querer facer.

681
00:55:50,350 --> 00:55:54,510
E nós non imos pasar por enriba dunha solución iterativa.

682
00:55:54,510 --> 00:55:55,980
Eu non recomenda -

683
00:55:55,980 --> 00:56:03,070
Fundir tipo é un exemplo dunha función que é ao mesmo tempo non a cola recursiva,

684
00:56:03,070 --> 00:56:07,040
non é fácil facer que a cola recursiva,

685
00:56:07,040 --> 00:56:13,450
pero tampouco é moi fácil facelo interactivo.

686
00:56:13,450 --> 00:56:16,910
Isto é moi fácil.

687
00:56:16,910 --> 00:56:19,170
Esta implementación do merge sort,

688
00:56:19,170 --> 00:56:22,140
funden, non importa o que fai, está indo para a construción de mesclagem.

689
00:56:22,140 --> 00:56:29,170
>> Entón, merge sort construída encima de mesturar recursivamente é só estas tres liñas.

690
00:56:29,170 --> 00:56:34,700
Iterativamente, é máis aburrido e máis difícil de pensar.

691
00:56:34,700 --> 00:56:41,860
Pero teña en conta que non é rabo recursiva dende mergeSortHelp - cando se chama a si mesma -

692
00:56:41,860 --> 00:56:46,590
aínda cómpre facer as cousas tras esta chamada retorna recursivas.

693
00:56:46,590 --> 00:56:50,830
Polo tanto, este cadro de pila debe continuar a existir mesmo tras chamar iso.

694
00:56:50,830 --> 00:56:54,170
E entón, cando chama iso, o cadro de pila debe continuar a existir

695
00:56:54,170 --> 00:56:57,780
porque, mesmo despois que a chamada, aínda necesitamos mesturar.

696
00:56:57,780 --> 00:57:01,920
E iso non é trivial para facer este rabo recursiva.

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

698
00:57:08,300 --> 00:57:09,860
Todo ben.

699
00:57:09,860 --> 00:57:13,400
Entón, volvendo a clasificar - Oh, hai dúas cousas que quero amosar. Okay.

700
00:57:13,400 --> 00:57:17,840
Volvendo ao tipo, imos facelo rápido.

701
00:57:17,840 --> 00:57:21,030
Ou investigación. Tipo? Ordenar. Si

702
00:57:21,030 --> 00:57:22,730
Volvendo aos inicios da especie.

703
00:57:22,730 --> 00:57:29,870
Queremos crear un algoritmo que ordena a matriz usando calquera algoritmo

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

705
00:57:33,660 --> 00:57:40,860
Entón, como iso é posible? Alguén ten calquera tipo de -

706
00:57:40,860 --> 00:57:44,300
Suxerín antes -

707
00:57:44,300 --> 00:57:48,300
Se estamos a piques de mellorar a partir de n log n a O de n,

708
00:57:48,300 --> 00:57:51,450
temos mellorado o noso algoritmo en termos de tempo,

709
00:57:51,450 --> 00:57:55,250
o que significa que imos precisar facer para compensar iso?

710
00:57:55,250 --> 00:57:59,520
[Alumno] Espazo. Si >>. Nós imos estar usando máis espazo.

711
00:57:59,520 --> 00:58:04,490
E nin sequera só espazo, é exponencialmente máis espazo.

712
00:58:04,490 --> 00:58:14,320
Entón eu creo que este tipo de algoritmo é algo pseudo, pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - Eu non me lembro. Pseudo algo.

714
00:58:18,980 --> 00:58:22,210
Pero é porque necesitamos empregar tanto espazo

715
00:58:22,210 --> 00:58:28,610
que isto pode ser conseguido, pero non realista.

716
00:58:28,610 --> 00:58:31,220
>> E como imos conseguir isto?

717
00:58:31,220 --> 00:58:36,810
Podemos alcanzar iso garantir que algún determinado elemento da matriz

718
00:58:36,810 --> 00:58:39,600
é inferior a un determinado tamaño.

719
00:58:42,070 --> 00:58:44,500
Entón imos só dicir que o tamaño é de 200,

720
00:58:44,500 --> 00:58:48,130
calquera elemento dunha matriz é debaixo do tamaño 200.

721
00:58:48,130 --> 00:58:51,080
E iso é realmente moi realista.

722
00:58:51,080 --> 00:58:58,660
Pode moi facilmente ter unha matriz que sabe todo na mesma

723
00:58:58,660 --> 00:59:00,570
vai ser menor que o número.

724
00:59:00,570 --> 00:59:07,400
Como se ten algún vector absolutamente enorme ou algo

725
00:59:07,400 --> 00:59:11,810
pero xa sabe que todo vai estar entre 0 e 5,

726
00:59:11,810 --> 00:59:14,790
a continuación, que vai ser moito máis rápido para facelo.

727
00:59:14,790 --> 00:59:17,930
E o límite de calquera dos elementos é de 5,

728
00:59:17,930 --> 00:59:21,980
así que este límite, que é a cantidade de memoria que vai estar usando.

729
00:59:21,980 --> 00:59:26,300
Así, o límite é de 200.

730
00:59:26,300 --> 00:59:32,960
En teoría, sempre hai un límite desde un enteiro só pode ser de ata 4 millóns,

731
00:59:32,960 --> 00:59:40,600
pero iso é irreal, desde entón, estaría usando o espazo

732
00:59:40,600 --> 00:59:44,400
da orde de 4000 millóns. Entón, iso é irreal.

733
00:59:44,400 --> 00:59:47,060
Pero aquí imos dicir que o noso límite é 200.

734
00:59:47,060 --> 00:59:59,570
O truco para facelo en O de n é que facer unha outra matriz chamada conta de tamaño vinculado.

735
00:59:59,570 --> 01:00:10,470
Entón, en realidade, este é un atallo para - Eu realmente non sei se Clang fai iso.

736
01:00:11,150 --> 01:00:15,330
Pero no GCC, como mínimo - Clang asumindo estou fai iso tamén -

737
01:00:15,330 --> 01:00:18,180
iso só vai arrincar a matriz enteira para ser 0s.

738
01:00:18,180 --> 01:00:25,320
Entón, se eu non quere facelo, entón eu podería facer por separado for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <Bound, i + +) e conta [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Entón, agora todo é inicializar con 0.

741
01:00:35,260 --> 01:00:39,570
Eu iterar sobre a miña matriz,

742
01:00:39,570 --> 01:00:51,920
eo que eu estou facendo é que eu estou contando o número de cada un - Imos descender aquí.

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

744
01:00:55,480 --> 01:01:00,010
O que eu estou contando é o número de ocorrencias de cada un deses elementos.

745
01:01:00,010 --> 01:01:03,470
Imos realmente engadir máis un par aquí con algunhas repeticións.

746
01:01:03,470 --> 01:01:11,070
Así, o valor que temos aquí, o valor do que vai ser array [i].

747
01:01:11,070 --> 01:01:14,850
Entón val podería ser 4 ou 8 ou o que sexa.

748
01:01:14,850 --> 01:01:18,870
E agora eu estou contando cantos de que o valor que vin,

749
01:01:18,870 --> 01:01:21,230
para a conta [val] + +;

750
01:01:21,230 --> 01:01:29,430
Despois de feito isto, conta vai para algo coma 0001.

751
01:01:29,430 --> 01:01:42,190
Imos facer a conta [val] - vinculado + 1.

752
01:01:42,190 --> 01:01:48,230
>> Agora iso é só para explicar o feito de que estamos comezando de 0.

753
01:01:48,230 --> 01:01:50,850
Entón, se 200 vai ser a nosa maior número,

754
01:01:50,850 --> 01:01:54,720
entón 0-200 é 201 cousas.

755
01:01:54,720 --> 01:02:01,540
Entón, conta, que vai ollar como 00001 porque temos un 4.

756
01:02:01,540 --> 01:02:10,210
Entón nós imos ter 0001, onde imos ter un 1 no índice de 8 de conta.

757
01:02:10,210 --> 01:02:14,560
Nós imos ter a 2 no índice 23 da conta.

758
01:02:14,560 --> 01:02:17,630
Nós imos ter a 2 no índice 42 da conta.

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

760
01:02:34,270 --> 01:02:44,920
Entón num_of_item = contador [i].

761
01:02:44,920 --> 01:02:52,540
E así se num_of_item é 2, isto significa que queremos inserir o número 2 de i

762
01:02:52,540 --> 01:02:55,290
na nosa matriz de clasificación.

763
01:02:55,290 --> 01:03:02,000
Polo tanto, temos que manter o control de canto estamos lonxe na matriz.

764
01:03:02,000 --> 01:03:05,470
Entón index = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Eu só vou escribir.

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

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

768
01:03:28,580 --> 01:03:32,490
É iso o que quero? Eu creo que é o que quero.

769
01:03:35,100 --> 01:03:38,290
Si, iso parece bo. Okay.

770
01:03:38,290 --> 01:03:43,050
Así que todo o mundo entende o que o propósito da miña conta é a matriz?

771
01:03:43,050 --> 01:03:48,140
E contando o número de ocorrencias de cada un deses números.

772
01:03:48,140 --> 01:03:51,780
Entón eu estou interactuar sobre esta matriz conta

773
01:03:51,780 --> 01:03:57,190
é a posición Ith na matriz contas

774
01:03:57,190 --> 01:04:01,930
é o número de i é que debe aparecer na miña matriz de clasificación.

775
01:04:01,930 --> 01:04:06,840
É por iso que a conta de 4 vai ser un

776
01:04:06,840 --> 01:04:11,840
e conta de 8 vai ser 1, as contas de 23, vai ser 2.

777
01:04:11,840 --> 01:04:16,900
Entón é así que moitos deles quero introducir no meu array ordenado.

778
01:04:16,900 --> 01:04:19,200
Entón eu só facelo.

779
01:04:19,200 --> 01:04:28,960
Estou inserindo num_of_item i é a miña matriz de clasificación.

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

781
01:04:32,460 --> 01:04:43,100
E así unha vez máis, este é o tempo lineal xa que estamos só interactuar sobre iso unha vez máis,

782
01:04:43,100 --> 01:04:47,470
pero tamén é lineal en que este número se atopa,

783
01:04:47,470 --> 01:04:50,730
e por iso depende moito do que o seu límite é.

784
01:04:50,730 --> 01:04:53,290
Cun límite de 200, que non é tan malo.

785
01:04:53,290 --> 01:04:58,330
Se o seu límite será de 10.000, entón iso é un pouco peor,

786
01:04:58,330 --> 01:05:01,360
pero se o seu límite será 4 millóns, que é totalmente irrealista

787
01:05:01,360 --> 01:05:07,720
e esa matriz vai ter que ser de tamaño 4 millóns, o que é irreal.

788
01:05:07,720 --> 01:05:10,860
Entón é iso. Preguntas?

789
01:05:10,860 --> 01:05:13,270
[Resposta do alumno inaudível] >> Okay.

790
01:05:13,270 --> 01:05:15,710
Podo entender unha cousa, cando estabamos pasando.

791
01:05:17,980 --> 01:05:23,720
Creo que o problema estaba en Lucas e, probablemente, cada un que xa vimos.

792
01:05:23,720 --> 01:05:26,330
Eu esquezo completamente.

793
01:05:26,330 --> 01:05:31,040
O único que eu quería comentar é que cando está lidando con cousas como índices,

794
01:05:31,040 --> 01:05:38,320
nunca realmente ver iso cando está escribindo un loop,

795
01:05:38,320 --> 01:05:41,120
pero, técnicamente, sempre que está lidando con estes índices,

796
01:05:41,120 --> 01:05:45,950
ten que case sempre tratar con números enteiros sen signo.

797
01:05:45,950 --> 01:05:53,850
A razón para iso é cando está lidando con números enteiros asinados,

798
01:05:53,850 --> 01:05:56,090
por iso, se ten dous enteiros asinados e engadila los xuntos

799
01:05:56,090 --> 01:06:00,640
e eles acaban moi grande, entón acaba con un número negativo.

800
01:06:00,640 --> 01:06:03,410
Entón é iso que é estourido de enteiro.

801
01:06:03,410 --> 01:06:10,500
>> Se eu engadir 2 millóns e 1 billón, eu acabar con negativo 1 billón.

802
01:06:10,500 --> 01:06:15,480
É así que funciona en computadores enteiros.

803
01:06:15,480 --> 01:06:17,510
Así, o problema co uso -

804
01:06:17,510 --> 01:06:23,500
Isto é bo, excepto baixo pasa a ser 2 millóns e pasa a ser 1 billón,

805
01:06:23,500 --> 01:06:27,120
entón iso vai ser negativo 1 billón e, a continuación, imos dividir ese por dous

806
01:06:27,120 --> 01:06:29,730
e acabar con negativo de 500 millóns.

807
01:06:29,730 --> 01:06:33,760
Polo tanto, este é só un problema se ocorrer de estar buscando por unha matriz

808
01:06:33,760 --> 01:06:38,070
de millóns de cousas.

809
01:06:38,070 --> 01:06:44,050
Pero se + abaixo acontece a rebordar, entón iso é un problema.

810
01:06:44,050 --> 01:06:47,750
Así que facelos sen sinal, entón 2 millóns, máis 1 billón é 3 millóns.

811
01:06:47,750 --> 01:06:51,960
3.000 millóns dividido por dous é de 1,5 millóns.

812
01:06:51,960 --> 01:06:55,670
Así, logo que eles están sen sinal, todo é perfecto.

813
01:06:55,670 --> 01:06:59,900
E por iso é tamén un problema cando está escribindo o seu loops,

814
01:06:59,900 --> 01:07:03,940
e realmente, probablemente fai iso automaticamente.

815
01:07:09,130 --> 01:07:12,330
Será realmente só berrar con vostede.

816
01:07:12,330 --> 01:07:21,610
Polo tanto, se ese número é moi grande para ser só un enteiro, pero que cabería nun enteiro non asinado,

817
01:07:21,610 --> 01:07:24,970
vai berrar con vostede, é por iso que nunca executar para a cuestión.

818
01:07:29,150 --> 01:07:34,820
Podes ver que un índice non vai ser negativo,

819
01:07:34,820 --> 01:07:39,220
e así, cando está interactuando sobre unha matriz,

820
01:07:39,220 --> 01:07:43,970
case sempre pode dicir unsigned int i, pero realmente non precisa.

821
01:07:43,970 --> 01:07:47,110
As cousas están indo para o traballo practicamente tan ben.

822
01:07:48,740 --> 01:07:50,090
Okay. [Sussurra] Que hora é?

823
01:07:50,090 --> 01:07:54,020
A última cousa que eu quería amosar - e eu vou facelo moi rápido.

824
01:07:54,020 --> 01:08:03,190
Vostede sabe como nós # define para que poidamos # define MAX como 5 ou algo así?

825
01:08:03,190 --> 01:08:05,940
Non imos facer MAX. # Establece límite como 200. Iso é o que fixemos antes.

826
01:08:05,940 --> 01:08:10,380
Que define unha constante, que só vai ser copiado e pegado

827
01:08:10,380 --> 01:08:13,010
onde queira que aconteza para escribir vinculado.

828
01:08:13,010 --> 01:08:18,189
>> Así, podemos realmente facer máis con # define.

829
01:08:18,189 --> 01:08:21,170
Podemos # define funcións.

830
01:08:21,170 --> 01:08:23,410
Eles non son realmente funcións, pero imos chamalos de funcións.

831
01:08:23,410 --> 01:08:36,000
Un exemplo sería algo así como MAX (x, y) é definida como (x <y y:? X). Okay.

832
01:08:36,000 --> 01:08:40,660
Polo tanto, ten que acostumar a sintaxe do operador ternário,

833
01:08:40,660 --> 01:08:49,029
pero é menor que x y? Voltar y, outra volta x.

834
01:08:49,029 --> 01:08:54,390
Así podes ver que pode facer esta función un separado,

835
01:08:54,390 --> 01:09:01,399
ea función podería ser como bool MAX leva 2 argumentos, devolva este.

836
01:09:01,399 --> 01:09:08,340
Este é un dos máis comúns que eu vexo feito coma este. Nós os chamamos de macros.

837
01:09:08,340 --> 01:09:11,790
Esta é unha macro.

838
01:09:11,790 --> 01:09:15,859
Esta é só a sintaxe para iso.

839
01:09:15,859 --> 01:09:18,740
Podes escribir unha macro para facer o que quere.

840
01:09:18,740 --> 01:09:22,649
Vostede frecuentemente ver macros para depurar printfs e outras cousas.

841
01:09:22,649 --> 01:09:29,410
Así, un tipo de printf hai constantes especiais en C, como subliñado LIÑA subliñado,

842
01:09:29,410 --> 01:09:31,710
2 underscores LIÑA subliñado,

843
01:09:31,710 --> 01:09:37,550
e hai tamén creo que 2 underscores func. Isto pode ser iso. Algo así.

844
01:09:37,550 --> 01:09:40,880
Estas cousas será substituído co nome da función

845
01:09:40,880 --> 01:09:42,930
ou o número da liña que está.

846
01:09:42,930 --> 01:09:48,630
Frecuentemente, escribe printfs depuración que aquí podería entón só escribir

847
01:09:48,630 --> 01:09:54,260
Depuración e será impreso o número da liña e función que ocorrer de eu estar no

848
01:09:54,260 --> 01:09:57,020
que atopou que a declaración depuración.

849
01:09:57,020 --> 01:09:59,550
E tamén pode imprimir outras cousas.

850
01:09:59,550 --> 01:10:05,990
Entón, unha cousa que ten que observar é se ocorrer de eu # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
como algo como 2 * y e 2 * x.

852
01:10:11,380 --> 01:10:14,310
Así, por razón algunha, ocorrer de facelo moito.

853
01:10:14,310 --> 01:10:16,650
Entón faga unha macro.

854
01:10:16,650 --> 01:10:18,680
Esta é realmente dobres.

855
01:10:18,680 --> 01:10:23,050
Eu diría que é, facendo algo así como DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Entón, o que debe ser devolto?

857
01:10:28,840 --> 01:10:30,580
[Estudante] 12.

858
01:10:30,580 --> 01:10:34,800
Si, 12 deberán ser devoltos, e 12 e devolto.

859
01:10:34,800 --> 01:10:43,350
3 substitúese por X, 6 substitúese por y, e volvemos 2 * 6, que é 12.

860
01:10:43,350 --> 01:10:47,710
Agora, o que sobre iso? O que debe ser devolto?

861
01:10:47,710 --> 01:10:50,330
[Estudante] 14. >> Ideal, 14.

862
01:10:50,330 --> 01:10:55,290
A cuestión é que, como define o traballo de hash, lembre que é unha copia literal e pegar

863
01:10:55,290 --> 01:11:00,160
de practicamente todo, entón o que é que isto vai ser interpretado como

864
01:11:00,160 --> 01:11:11,270
3 é inferior a 1, máis 6, 2 veces 1 máis 6, 2 veces 3.

865
01:11:11,270 --> 01:11:19,780
>> Así, por esta razón, case sempre embrulhar todo entre parénteses.

866
01:11:22,180 --> 01:11:25,050
Calquera variable que case sempre embrulho en parénteses.

867
01:11:25,050 --> 01:11:29,570
Hai casos en que non ten que, como eu sei que eu non teño que facer iso aquí

868
01:11:29,570 --> 01:11:32,110
porque menos do que é practicamente sempre vai funcionar,

869
01:11:32,110 --> 01:11:34,330
a pesar de que pode ata non ser verdade.

870
01:11:34,330 --> 01:11:41,870
Se hai algo ridículo como DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
entón que vai estar substituído por 3 é igual a menos de 1 é igual a 2,

872
01:11:49,760 --> 01:11:53,460
E entón el vai facer 3 menor que 1, que igual a 2,

873
01:11:53,460 --> 01:11:55,620
o que non é o que queremos.

874
01:11:55,620 --> 01:12:00,730
Polo tanto, a fin de evitar os problemas de precedencia de operadores,

875
01:12:00,730 --> 01:12:02,870
sempre embrulho en parénteses.

876
01:12:03,290 --> 01:12:07,700
Okay. E é que, 5:30.

877
01:12:08,140 --> 01:12:12,470
Se tes algunha dúbida sobre o pset, aviso connosco.

878
01:12:12,470 --> 01:12:18,010
Debe ser divertido, ea edición hacker tamén é moito máis realista

879
01:12:18,010 --> 01:12:22,980
que a edición hacker do ano pasado, polo que esperamos que unha morea de tentar.

880
01:12:22,980 --> 01:12:26,460
O ano pasado, foi moi grande.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]