1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Música tocando]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Todo ben.

4
00:00:13,500 --> 00:00:14,670
Todo ben, benvido de volta.

5
00:00:14,670 --> 00:00:18,120
Polo tanto, esta é a Semana 4, o inicio
º, xa.

6
00:00:18,120 --> 00:00:21,320
E vai lembrar que, a semana pasada, poñemos
código de lado por un pouco

7
00:00:21,320 --> 00:00:24,240
e comezamos a falar un pouco máis
de alto nivel, sobre cousas como

8
00:00:24,240 --> 00:00:28,130
investigación e clasificación, que aínda
ideas son simples, pouco

9
00:00:28,130 --> 00:00:31,840
representativo dunha clase de problemas
vai comezar a resolver particularmente

10
00:00:31,840 --> 00:00:34,820
como comezar a pensar en último
proxectos e solucións interesantes que

11
00:00:34,820 --> 00:00:36,760
pode ter de problemas do mundo real.

12
00:00:36,760 --> 00:00:39,490
Agora bubble sort é un dos máis simple
tales algoritmos, e

13
00:00:39,490 --> 00:00:42,900
Traballou por estes pequenos números
nunha lista ou nun tipo conxunto de

14
00:00:42,900 --> 00:00:46,530
burbulla seu camiño ata o cumio, eo
grandes números mover o seu camiño ata

15
00:00:46,530 --> 00:00:47,930
o final da lista.

16
00:00:47,930 --> 00:00:50,650
>> E lembrar que puidésemos ver
bubble sort algo

17
00:00:50,650 --> 00:00:52,310
algo así.

18
00:00:52,310 --> 00:00:53,640
Entón deixe-me ir adiante e prema en Inicio.

19
00:00:53,640 --> 00:00:55,350
Eu xa pre-seleccionado bubble sort.

20
00:00:55,350 --> 00:00:58,920
E se lembrar que o azul máis alto
liñas representan números grandes, pequenas

21
00:00:58,920 --> 00:01:03,300
liñas azuis representan pequenos números, como
pasamos por iso de novo e de novo e

22
00:01:03,300 --> 00:01:07,680
unha vez máis, comparando dúas barras de mosaico
outra en vermello, imos cambiar o

23
00:01:07,680 --> 00:01:11,010
maior eo menor se
están fóra de orde.

24
00:01:11,010 --> 00:01:14,150
>> Entón, que vai continuar e ir
, E podes ver que a maior

25
00:01:14,150 --> 00:01:16,700
elementos están facendo o seu camiño cara ao
dereito, e os elementos menores son

26
00:01:16,700 --> 00:01:17,900
facendo o seu camiño cara á esquerda.

27
00:01:17,900 --> 00:01:21,380
Pero empezamos a cuantificar
a eficiencia, a

28
00:01:21,380 --> 00:01:22,970
calidade deste algoritmo.

29
00:01:22,970 --> 00:01:25,200
E nós dixemos que, no peor
caso, este algoritmo levou

30
00:01:25,200 --> 00:01:27,940
aproximadamente cantos pasos?

31
00:01:27,940 --> 00:01:28,980
>> Entón n ao cadrado.

32
00:01:28,980 --> 00:01:30,402
E o que era n?

33
00:01:30,402 --> 00:01:31,650
>> Audiencia: Número de elementos.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Entón n foi o
número de elementos.

35
00:01:32,790 --> 00:01:33,730
E así imos facelo moitas veces.

36
00:01:33,730 --> 00:01:36,650
Cada vez que quero falar sobre o tamaño
dun problema ou o tamaño dun

37
00:01:36,650 --> 00:01:39,140
entrada, ou a cantidade de tempo que leva
para producir unha saída, imos

38
00:01:39,140 --> 00:01:41,610
xeneralizada o que
a entrada é como n.

39
00:01:41,610 --> 00:01:45,970
Entón, de volta na Semana 0, o número de páxinas
na lista telefónica foi n.

40
00:01:45,970 --> 00:01:47,550
O número de estudantes
na sala foi n.

41
00:01:47,550 --> 00:01:49,630
Entón, aquí, tamén, que estamos seguindo
ese estándar.

42
00:01:49,630 --> 00:01:52,800
>> Agora n ao cadrado non é especialmente
rápido, entón intentamos facer mellor.

43
00:01:52,800 --> 00:01:55,970
E así, nós miramos un par de
outros algoritmos, entre os que

44
00:01:55,970 --> 00:01:57,690
foron selección especie.

45
00:01:57,690 --> 00:01:59,180
Así, a selección especie foi
un pouco diferente.

46
00:01:59,180 --> 00:02:03,130
Era case máis sinxelo, atrévome a dicir,
cal I iniciada o comezo do

47
00:02:03,130 --> 00:02:06,740
Lista dos nosos voluntarios e eu de novo
e outra vez pasou por

48
00:02:06,740 --> 00:02:10,060
Na lista, arrincar a menor
elemento de cada vez e poñelas ou

49
00:02:10,060 --> 00:02:13,040
ela no comezo da lista.

50
00:02:13,040 --> 00:02:16,410
>> Pero iso, tamén, xa que empezamos a pensar
a través da matemática e maior

51
00:02:16,410 --> 00:02:19,860
imaxe, penso en cantas veces
Eu estaba indo cara atrás e cara adiante e cara atrás

52
00:02:19,860 --> 00:02:24,090
e cara atrás, nós dixemos, no peor caso,
selección especie, tamén, era o que?

53
00:02:24,090 --> 00:02:24,960
n ao cadrado.

54
00:02:24,960 --> 00:02:27,490
Agora, no mundo real, pode
en realidade, ser lixeiramente máis rápido.

55
00:02:27,490 --> 00:02:30,620
Porque unha vez máis, eu non teño que manter
retroceso, xa que eu ordenara a

56
00:02:30,620 --> 00:02:31,880
pequenos elementos.

57
00:02:31,880 --> 00:02:35,090
Pero se pensamos moi grande n, e
se tipo de facer a matemática como

58
00:02:35,090 --> 00:02:39,170
Eu fixen no taboleiro, co n ao cadrado
menos algo, o resto

59
00:02:39,170 --> 00:02:41,850
ademais do n ao cadrado, xa que non
queda moi grande, non

60
00:02:41,850 --> 00:02:42,850
realmente importa tanto.

61
00:02:42,850 --> 00:02:45,470
Así como os científicos da computación, que especie de
pechar os ollos a menor

62
00:02:45,470 --> 00:02:49,220
factores e concentrarse só no factor de
unha expresión que vai facer

63
00:02:49,220 --> 00:02:50,330
a maior diferenza.

64
00:02:50,330 --> 00:02:52,840
>> Ben, finalmente, nós miramos
a ordenación por inserción.

65
00:02:52,840 --> 00:02:56,620
E este foi semellante en espírito, pero
en vez de pasar por iterativa e

66
00:02:56,620 --> 00:03:01,250
seleccionar o menor elemento dun
tempo, en vez tomou a man que me

67
00:03:01,250 --> 00:03:04,070
foi tratado, e eu decidimos, o único
seguro, vostede pertence aquí.

68
00:03:04,070 --> 00:03:06,160
Logo, mudei-me para o seguinte elemento
e decidiu que el ou

69
00:03:06,160 --> 00:03:07,470
ela pertencía aquí.

70
00:03:07,470 --> 00:03:08,810
E entón seguín adiante e continuar.

71
00:03:08,810 --> 00:03:11,780
E eu podería para, ao longo do camiño,
cambiar estes faces, a fin de

72
00:03:11,780 --> 00:03:13,030
dar espazo para eles.

73
00:03:13,030 --> 00:03:16,880
Así, foi unha especie de troco mentais
de selección tipo que

74
00:03:16,880 --> 00:03:18,630
chamado ordenación por inserción.

75
00:03:18,630 --> 00:03:20,810
>> Entón, eses temas para ocorrer
no mundo real.

76
00:03:20,810 --> 00:03:23,640
Só uns anos, cando un determinado
senador estaba concorrendo á presidencia,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, no momento en que o CEO de
Google, en realidade, tiven a oportunidade

78
00:03:27,160 --> 00:03:28,040
entrevistalo.

79
00:03:28,040 --> 00:03:32,010
E nós pensamos en compartir ese YouTube
clip para vostede aquí, se puidésemos transformar-se

80
00:03:32,010 --> 00:03:32,950
o volume.

81
00:03:32,950 --> 00:03:39,360
>> [REPRODUCIÓN]

82
00:03:39,360 --> 00:03:44,620
>> -Agora, o senador, está aquí en Google,
e me gusta de pensar na presidencia

83
00:03:44,620 --> 00:03:46,042
como unha entrevista de emprego.

84
00:03:46,042 --> 00:03:47,770
>> [Risas]

85
00:03:47,770 --> 00:03:50,800
>> -Agora é difícil conseguir
un posto como presidente.

86
00:03:50,800 --> 00:03:52,480
E está pasando
os rigores agora.

87
00:03:52,480 --> 00:03:54,330
Tamén é difícil conseguir un emprego en Google.

88
00:03:54,330 --> 00:03:59,610
Temos preguntas e pedimos
Os nosos candidatos preguntas.

89
00:03:59,610 --> 00:04:02,250
E este é de Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Risas]

91
00:04:05,325 --> 00:04:06,400
-Vostedes pensan que eu estou a xogar?

92
00:04:06,400 --> 00:04:08,750
É aquí mesmo.

93
00:04:08,750 --> 00:04:12,110
Cal é o xeito máis eficaz para
ordenar un millón de números enteiros de dous bits?

94
00:04:12,110 --> 00:04:15,810
>> [Risas]

95
00:04:15,810 --> 00:04:18,260
>> -Ben, uh -

96
00:04:18,260 --> 00:04:19,029
>> -Sinto moito.

97
00:04:19,029 --> 00:04:19,745
Quizais devêssemos -

98
00:04:19,745 --> 00:04:21,000
>> -Non, non, non, non, non.

99
00:04:21,000 --> 00:04:21,470
>> -Iso non é unha -

100
00:04:21,470 --> 00:04:22,185
Aceptar.

101
00:04:22,185 --> 00:04:25,328
>> -Creo que o bubble sort sería
ser o camiño mal.

102
00:04:25,328 --> 00:04:26,792
>> [Risas]

103
00:04:26,792 --> 00:04:28,510
>> [Aclamacións e aplausos]

104
00:04:28,510 --> 00:04:31,211
>> -Imos, que lle dixo iso?

105
00:04:31,211 --> 00:04:32,155
Aceptar.

106
00:04:32,155 --> 00:04:33,350
>> [FIN reprodución de vídeo]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Entón tes iso.

108
00:04:35,070 --> 00:04:39,600
Entón comezamos a cuantificar estes execución
veces, por así dicir, con algo

109
00:04:39,600 --> 00:04:43,480
chamado notación asintótica, que é
só referíndose a nosa especie de transformar

110
00:04:43,480 --> 00:04:47,420
os ollos para estes factores menores e
só mirando para o tempo de execución,

111
00:04:47,420 --> 00:04:51,250
a actuación destes algoritmos,
como n queda moi grande co paso do tempo.

112
00:04:51,250 --> 00:04:55,110
E así, nós introducimos gran O. e Big O
representaba algo que pensabamos

113
00:04:55,110 --> 00:04:57,000
como un límite superior.

114
00:04:57,000 --> 00:04:59,570
E, de feito, Barry, podemos diminuír
que o micrófono un pouco?

115
00:04:59,570 --> 00:05:01,040
>> Pensamos que isto é un límite superior.

116
00:05:01,040 --> 00:05:04,710
Tan grande S de n significa que, en cadrado
peor dos casos, algo así como

117
00:05:04,710 --> 00:05:07,780
selección tipo levaría
n pasos cadrado.

118
00:05:07,780 --> 00:05:10,310
Ou algo parecido a ordenación por inserción
sería n pasos cadrado.

119
00:05:10,310 --> 00:05:15,150
Agora, para algo así como a inserción
tipo, cal foi o peor caso?

120
00:05:15,150 --> 00:05:18,200
Dado un array, que é o peor
escenario posible, que se pode atopar

121
00:05:18,200 --> 00:05:20,650
se depara con?

122
00:05:20,650 --> 00:05:21,860
>> É completamente para atrás, non?

123
00:05:21,860 --> 00:05:24,530
Porque si é totalmente cara atrás,
ten que facer unha chea de traballo.

124
00:05:24,530 --> 00:05:26,420
Porque se está totalmente cara atrás,
vai atopar o

125
00:05:26,420 --> 00:05:28,840
maior elemento aquí, aínda que
pertence alí.

126
00:05:28,840 --> 00:05:31,140
Entón vai dicir, todo ben, a
Neste momento, vostede pertence aquí,

127
00:05:31,140 --> 00:05:32,310
así que deixar só.

128
00:05:32,310 --> 00:05:35,425
>> Entón entende, oh, droga, eu teño que
mover este elemento lixeiramente menor para

129
00:05:35,425 --> 00:05:36,470
á esquerda de ti.

130
00:05:36,470 --> 00:05:38,770
Entón eu teño que facelo de novo
e de novo e de novo.

131
00:05:38,770 --> 00:05:41,410
E se eu andei para atrás e para adiante, vostede
clasificar de sentir o rendemento dos

132
00:05:41,410 --> 00:05:45,540
que o algoritmo, xa que constantemente son
barallar todos os outros para abaixo na

133
00:05:45,540 --> 00:05:46,510
matriz para facer o cuarto para el.

134
00:05:46,510 --> 00:05:47,750
Entón ese é o peor caso.

135
00:05:47,750 --> 00:05:48,570
>> Por outra banda -

136
00:05:48,570 --> 00:05:50,320
e iso foi un cliffhanger última vez -

137
00:05:50,320 --> 00:05:54,065
dixemos que a ordenación por inserción
era un omega de que?

138
00:05:54,065 --> 00:05:57,530
Cal é o mellor caso running
momento da inserción do tipo?

139
00:05:57,530 --> 00:05:58,520
Entón, en realidade é n.

140
00:05:58,520 --> 00:06:00,980
Ese era o baleiro que deixou
no marco da última vez.

141
00:06:00,980 --> 00:06:03,160
>> E é omega de n por por que?

142
00:06:03,160 --> 00:06:06,630
Pois ben, no mellor caso, o que se
ordenación por inserción será entregado?

143
00:06:06,630 --> 00:06:09,830
Ben, a lista que está completamente resolto
xa, o mínimo de traballo para facer.

144
00:06:09,830 --> 00:06:12,460
Pero o que é interesante sobre a ordenación por inserción
é que, xa que comeza aquí e

145
00:06:12,460 --> 00:06:15,340
decide, oh, que é o número
un, vostede pertence aquí.

146
00:06:15,340 --> 00:06:16,970
Oh, o que unha boa fortuna.

147
00:06:16,970 --> 00:06:17,740
>> Vostede é o número dous.

148
00:06:17,740 --> 00:06:19,030
Tamén pertenzo aquí.

149
00:06:19,030 --> 00:06:21,010
Número tres, mellor aínda,
vostede pertence aquí.

150
00:06:21,010 --> 00:06:25,210
Así que se chega ao final da
pseudocódigo lista, por inserción de tipo

151
00:06:25,210 --> 00:06:28,010
que atravesou verbalmente
última vez, está feito.

152
00:06:28,010 --> 00:06:32,790
Pero a selección tipo, pola contra,
continúe a facer o que?

153
00:06:32,790 --> 00:06:35,260
>> Continúe a lista
novo e de novo e de novo.

154
00:06:35,260 --> 00:06:39,160
Porque o coñecemento clave que só había
unha vez que mirou para todo o camiño para a

155
00:06:39,160 --> 00:06:42,500
final da lista pode estar seguro
que o elemento que foi seleccionado

156
00:06:42,500 --> 00:06:45,560
de feito o menor elemento actualmente.

157
00:06:45,560 --> 00:06:48,920
Entón, estas diferentes modelos mentais final
cedendo algúns moi real-world

158
00:06:48,920 --> 00:06:53,130
diferenzas para nós, así como estes
diferenzas asintótica teóricas.

159
00:06:53,130 --> 00:06:56,910
>> Entón, só para recapitular, entón, gran O de n
cadrado, vimos algúns como

160
00:06:56,910 --> 00:06:58,350
algoritmos ata agora.

161
00:06:58,350 --> 00:06:59,580
Big O de n?

162
00:06:59,580 --> 00:07:02,870
¿Que é un algoritmo que podería
pode dicir para ser grande de n?

163
00:07:02,870 --> 00:07:06,930
No peor dos casos, leva
unha serie lineal de pasos.

164
00:07:06,930 --> 00:07:07,810
>> OK, procura lineal.

165
00:07:07,810 --> 00:07:10,470
E no peor caso, onde está o
elemento que está a buscar cando

166
00:07:10,470 --> 00:07:12,950
aplicación de busca lineal?

167
00:07:12,950 --> 00:07:14,680
>> OK, no peor caso,
non o é alí.

168
00:07:14,680 --> 00:07:17,000
Ou o segundo peor caso é
todo o camiño ao final, o que é

169
00:07:17,000 --> 00:07:18,880
máis-ou-menos unha diferenza dunha etapa.

170
00:07:18,880 --> 00:07:21,180
Así, ao final do día,
podemos dicir que é lineal.

171
00:07:21,180 --> 00:07:23,910
Big O de n sería de procura lineal,
porque, no peor caso, o

172
00:07:23,910 --> 00:07:26,610
elemento non está alí ou é
todo o camiño ao final.

173
00:07:26,610 --> 00:07:29,370
>> Ben, O gran de rexistro de n.

174
00:07:29,370 --> 00:07:32,760
Nós non falamos en detalles sobre
isto, pero xa vin iso antes.

175
00:07:32,760 --> 00:07:36,840
Que é executado no chamado logarítmica
tempo, no peor dos casos?

176
00:07:36,840 --> 00:07:38,500
>> Si, investigación de modo binario.

177
00:07:38,500 --> 00:07:42,930
E busca binaria no peor caso
Pode que o elemento en algún lugar

178
00:07:42,930 --> 00:07:45,640
no medio, ou nalgún lugar
no interior da matriz.

179
00:07:45,640 --> 00:07:48,040
Pero só atopalo xa que
dividir a lista pola metade, en

180
00:07:48,040 --> 00:07:48,940
metade, pola metade, pola metade.

181
00:07:48,940 --> 00:07:50,200
E, a continuación, listo, el está alí.

182
00:07:50,200 --> 00:07:52,500
Ou aínda, peor caso,
non o é alí.

183
00:07:52,500 --> 00:07:56,770
Pero non sabe que el non está alí
ata que especie de chegar a ese último

184
00:07:56,770 --> 00:08:00,470
baixo para a maioría dos elementos de reducir á metade
e reducir á metade e reducir á metade.

185
00:08:00,470 --> 00:08:01,400
>> Big O de 1.

186
00:08:01,400 --> 00:08:03,540
Para que puidésemos gran O de 2, O gran de 3.

187
00:08:03,540 --> 00:08:06,260
Sempre que sexa só un número constante,
Nós só unha especie de só simplificar

188
00:08:06,260 --> 00:08:07,280
que tan grande de unha.

189
00:08:07,280 --> 00:08:10,440
Aínda que se realista, hai que
2 ou ata 100 pasos, se é un

190
00:08:10,440 --> 00:08:13,680
número constante de pasos,
que acabamos de dicir gran O de 1.

191
00:08:13,680 --> 00:08:15,930
¿Que é un algoritmo que se
en gran O de 1?

192
00:08:15,930 --> 00:08:18,350
>> Audiencia: Atopar a lonxitude
dunha variable.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Buscar o
lonxitude dunha variable?

194
00:08:21,090 --> 00:08:23,870
>> Audiencia: Non, a lonxitude
se xa está clasificada.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Xenial.

196
00:08:24,160 --> 00:08:27,850
OK, así que atopar a lonxitude de algo
O longo de que algo, como

197
00:08:27,850 --> 00:08:30,020
unha matriz, é almacenada algunha variable.

198
00:08:30,020 --> 00:08:33,380
Porque pode só ler a variable,
ou imprimir a variable, ou

199
00:08:33,380 --> 00:08:34,960
xeralmente só acceder a esta variable.

200
00:08:34,960 --> 00:08:37,299
E listo, que leva tempo constante.

201
00:08:37,299 --> 00:08:38,909
>> Por outra banda, creo que volve a cero.

202
00:08:38,909 --> 00:08:42,460
Debería na primeira semana de C,
chamando só printf e impresión

203
00:08:42,460 --> 00:08:46,240
algo na pantalla é sen dúbida
constante de tempo, porque só leva

204
00:08:46,240 --> 00:08:50,880
un certo número de ciclos de CPU para amosar
que o texto na pantalla.

205
00:08:50,880 --> 00:08:52,720
Ou esperar - non é?

206
00:08:52,720 --> 00:08:56,430
De que outra forma poderiamos modelar o
desempeño do printf?

207
00:08:56,430 --> 00:09:00,420
Será que alguén quere desacordo, que
quizais non sexa o tempo realmente constante?

208
00:09:00,420 --> 00:09:03,600
En que sentido pode printf funciona
tempo, en realidade, a impresión dunha corda

209
00:09:03,600 --> 00:09:05,580
pantalla, ser algo
agás constante.

210
00:09:05,580 --> 00:09:07,860
>> Audiencia: [inaudível].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Yeah.

212
00:09:08,230 --> 00:09:09,300
Por iso, depende da nosa perspectiva.

213
00:09:09,300 --> 00:09:13,390
Se nós realmente creo que a entrada
printf como a cadea, e

214
00:09:13,390 --> 00:09:16,380
polo tanto, podemos medir o tamaño dese
entrada pola súa lonxitude - entón imos chamarlle

215
00:09:16,380 --> 00:09:17,780
que a lonxitude n, así como -

216
00:09:17,780 --> 00:09:21,990
sen dúbida printf é a propia gran O de n
porque vai levalo n pasos

217
00:09:21,990 --> 00:09:24,750
para imprimir cada unha das n
caracteres, probabelmente.

218
00:09:24,750 --> 00:09:27,730
Polo menos na medida en que asumimos
que quizais está usando un lazo for

219
00:09:27,730 --> 00:09:28,560
debaixo do capó.

220
00:09:28,560 --> 00:09:30,860
>> Pero teriamos que mirar para iso
Código para entender mellor.

221
00:09:30,860 --> 00:09:33,650
E, de feito, xa que vostedes empecen
analizar os seus propios algoritmos, vai

222
00:09:33,650 --> 00:09:34,900
literalmente facer exactamente isto.

223
00:09:34,900 --> 00:09:37,765
Especie de globo ocular seu código e pensar
sobre - todo ben, eu teño ese lazo

224
00:09:37,765 --> 00:09:41,870
aquí ou eu teño lazos aniñados aquí,
que vai facer n cousas n veces,

225
00:09:41,870 --> 00:09:46,050
e pode clasificar de razón o seu camiño
a través do código, aínda que sexa

226
00:09:46,050 --> 00:09:47,980
pseudocódigo e non o código real.

227
00:09:47,980 --> 00:09:49,730
>> Así que sobre omega de n ao cadrado?

228
00:09:49,730 --> 00:09:53,582
O que era un algoritmo que no mellor
caso, aínda levou n pasos cadrados?

229
00:09:53,582 --> 00:09:54,014
Si?

230
00:09:54,014 --> 00:09:54,880
>> Audiencia: [inaudível].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Entón selección especie.

232
00:09:55,900 --> 00:09:59,150
Debido a este problema moi reducida
ao feito de que unha vez máis, eu non sei

233
00:09:59,150 --> 00:10:02,600
Eu atopei o actual máis pequena ata
Eu chequei todos os elementos danado.

234
00:10:02,600 --> 00:10:08,050
Así omega de, digamos, n,
só veu con un.

235
00:10:08,050 --> 00:10:09,300
Ordenación por inserción.

236
00:10:09,300 --> 00:10:12,370
Se a lista pasa a ser clasificada
xa, no mellor dos casos, só temos

237
00:10:12,370 --> 00:10:15,090
para facer un paso a través dela,
ao momento en que ten por seguro.

238
00:10:15,090 --> 00:10:17,890
E, a continuación, que se pode dicir
ser lineal, con certeza.

239
00:10:17,890 --> 00:10:20,570
>> Que tal omega de 1?

240
00:10:20,570 --> 00:10:23,790
O que, no mellor dos casos, pode levar
un número constante de pasos?

241
00:10:23,790 --> 00:10:27,220
Busca de xeito lineal, se só ter sorte
eo elemento que está a buscar

242
00:10:27,220 --> 00:10:31,000
é ao comezo da lista,
se este é o lugar onde está comezando o seu

243
00:10:31,000 --> 00:10:33,070
lineal transversal desta lista.

244
00:10:33,070 --> 00:10:35,180
>> E iso é verdade dun
serie de cousas.

245
00:10:35,180 --> 00:10:37,660
Por exemplo, aínda binario
investigación é omega de 1.

246
00:10:37,660 --> 00:10:40,310
Porque se queda moi danado
sorte e smack-DAB no medio

247
00:10:40,310 --> 00:10:42,950
súa matriz é o número
estás buscando?

248
00:10:42,950 --> 00:10:45,730
Así, pode ter sorte alí, tamén.

249
00:10:45,730 --> 00:10:49,190
>> Este, por último, omega de n log n.

250
00:10:49,190 --> 00:10:52,573
Entón n log n, nós realmente non
falar aínda, pero -

251
00:10:52,573 --> 00:10:53,300
>> Audiencia: merge sort?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: merge sort.

253
00:10:53,960 --> 00:10:56,920
Ese foi o gancho da última vez,
onde propuxemos, e nós amosamos

254
00:10:56,920 --> 00:10:58,600
visual, que existen algoritmos.

255
00:10:58,600 --> 00:11:02,470
E unha especie de só un deses fundir
algoritmo que é fundamentalmente máis rápido

256
00:11:02,470 --> 00:11:03,450
que algúns deses outros caras.

257
00:11:03,450 --> 00:11:07,800
De feito, fundir curto é non só no
mellor caso n log n, no peor

258
00:11:07,800 --> 00:11:09,460
caso n log n.

259
00:11:09,460 --> 00:11:14,540
E cando ten esa coincidencia de
omega e grandes O ser a mesma cousa?

260
00:11:14,540 --> 00:11:17,310
De feito, podemos describir isto como o que é
chamado theta, aínda que sexa un

261
00:11:17,310 --> 00:11:18,220
pouco menos común.

262
00:11:18,220 --> 00:11:21,730
Pero iso significa só que os dous límites,
neste caso, son as mesmas.

263
00:11:21,730 --> 00:11:25,770
>> Entón, merge sort, o que iso
realmente se resumen a para nós?

264
00:11:25,770 --> 00:11:27,000
Ben, lembre a motivación.

265
00:11:27,000 --> 00:11:30,340
Déixame sacar-se outra animación que
non mirar por última vez.

266
00:11:30,340 --> 00:11:33,390
Este, mesma idea, pero
é un pouco máis grande.

267
00:11:33,390 --> 00:11:36,160
E eu estou indo a ir adiante e apuntar
primeiro - temos ordenación por inserción en

268
00:11:36,160 --> 00:11:39,410
esquina superior esquerda, a continuación, a selección de clasificación,
bubble sort, a par doutros tipos -

269
00:11:39,410 --> 00:11:42,670
shell e rápidos - que non falamos
aproximadamente, e heap e merge sort.

270
00:11:42,670 --> 00:11:47,090
>> Así, polo menos, tratar de centrar os seus ollos en
os tres principais da esquerda e logo

271
00:11:47,090 --> 00:11:49,120
merge sort cando clic
esta frecha verde.

272
00:11:49,120 --> 00:11:51,900
Pero eu vou deixar todos eles executados, só para
darlle un sentido da diversidade de

273
00:11:51,900 --> 00:11:53,980
algoritmos que existen no mundo.

274
00:11:53,980 --> 00:11:56,180
Vou deixar esta carreira
por só uns segundos.

275
00:11:56,180 --> 00:11:59,640
E se concentrar os seus ollos - seleccione un
algoritmo, centrar-lo por só un

276
00:11:59,640 --> 00:12:02,970
segundo - vai comezar a ver o
estándar que é de execución.

277
00:12:02,970 --> 00:12:04,530
>> Merge sort, previo aviso, está feito.

278
00:12:04,530 --> 00:12:06,430
Heap especie, tipo rápido, shell -

279
00:12:06,430 --> 00:12:09,480
así parece que introduciu a tres
peores algoritmos a semana pasada.

280
00:12:09,480 --> 00:12:12,960
Pero iso é bo que estamos aquí hoxe para
mirar merge sort, que é un dos

281
00:12:12,960 --> 00:12:16,500
o máis fácil é mirar, aínda
aínda que probablemente ha dobrar túa mente

282
00:12:16,500 --> 00:12:17,490
só un pouquiño.

283
00:12:17,490 --> 00:12:21,130
Aquí podemos ver o que
selección especie é unha merda.

284
00:12:21,130 --> 00:12:24,600
>> Pero, por outra banda, é
moi fácil de aplicar.

285
00:12:24,600 --> 00:12:28,160
E quizais a I Set 3, que é un dos
algoritmos que escolleu para aplicar

286
00:12:28,160 --> 00:12:28,960
para a edición estándar.

287
00:12:28,960 --> 00:12:30,970
Perfectamente ben, perfectamente correcto.

288
00:12:30,970 --> 00:12:35,210
>> Pero, de novo, como n se fai grande, se
decide aplicar un algoritmo máis rápido

289
00:12:35,210 --> 00:12:39,020
como merge sort, as probabilidades son en grande e
insumos maiores, o código é só

290
00:12:39,020 --> 00:12:39,800
vai executar máis rápido.

291
00:12:39,800 --> 00:12:41,090
O seu sitio vai funcionar mellor.

292
00:12:41,090 --> 00:12:42,650
Os seus usuarios están indo a ser feliz.

293
00:12:42,650 --> 00:12:45,280
E por iso hai estes efectos
de que realmente dar

294
00:12:45,280 --> 00:12:47,350
nos algún pensamento máis profundo.

295
00:12:47,350 --> 00:12:49,990
>> Entón, imos dar un ollo ao que funden
especie é realmente todo.

296
00:12:49,990 --> 00:12:52,992
O legal é que a fusión
tipo é só iso.

297
00:12:52,992 --> 00:12:56,300
É dicir, unha vez máis, o que chamamos
pseudocódigo, ser pseudocódigo

298
00:12:56,300 --> 00:12:57,720
Inglés-como sintaxe.

299
00:12:57,720 --> 00:12:59,890
E a simplicidade é
especie de fascinante.

300
00:12:59,890 --> 00:13:02,840
>> Entón, na entrada de n elementos - para que
significa só que, aquí está un array.

301
00:13:02,840 --> 00:13:04,000
Ten cousas n nel.

302
00:13:04,000 --> 00:13:05,370
Isto é todo o que estamos dicindo aquí.

303
00:13:05,370 --> 00:13:07,560
>> Se n é menor que 2, o regreso.

304
00:13:07,560 --> 00:13:08,640
Entón, iso é só o caso trivial.

305
00:13:08,640 --> 00:13:12,580
Se n é menor que 2, a continuación, é obviamente
1 ou 0, caso en que a cousa

306
00:13:12,580 --> 00:13:14,780
xa está clasificado ou non existe,
polo que só volver.

307
00:13:14,780 --> 00:13:15,900
Non hai nada que facer.

308
00:13:15,900 --> 00:13:18,360
Entón, iso é un caso sinxelo de arrincar fóra.

309
00:13:18,360 --> 00:13:20,110
>> En caso contrario, temos tres etapas.

310
00:13:20,110 --> 00:13:23,650
Ordenar a metade esquerda dos elementos, tipo
a metade dereita dos elementos,

311
00:13:23,650 --> 00:13:26,650
e logo mesturar as dúas metades ordenada.

312
00:13:26,650 --> 00:13:29,400
O que é interesante aquí é que
Eu son o tipo de punting, non?

313
00:13:29,400 --> 00:13:32,300
Hai unha especie de definición circular
para ese algoritmo.

314
00:13:32,300 --> 00:13:35,986
En que sentido é este algoritmo
circular definición?

315
00:13:35,986 --> 00:13:37,850
>> Audiencia: [inaudível].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Si, o meu algoritmo de ordenación,
dous dos seus pasos son "especie

317
00:13:41,670 --> 00:13:44,640
algo. "E así que levanta a
cuestión, ben, o que vou usar

318
00:13:44,640 --> 00:13:46,460
para clasificar a metade esquerda
ea metade dereita?

319
00:13:46,460 --> 00:13:49,600
E a beleza aquí é que, a pesar de
unha vez máis, esta é a alucinante

320
00:13:49,600 --> 00:13:54,030
parte potencialmente, pode utilizar mesmo
algoritmo para clasificar a metade esquerda.

321
00:13:54,030 --> 00:13:54,700
>> Pero agarde un minuto.

322
00:13:54,700 --> 00:13:57,070
Cando dixo para clasificar a
metade esquerda, cales son os dous

323
00:13:57,070 --> 00:13:58,240
pasos será o próximo?

324
00:13:58,240 --> 00:14:00,550
Imos resolver a metade esquerda da
media esquerda e á dereita

325
00:14:00,550 --> 00:14:01,420
a metade da metade esquerda.

326
00:14:01,420 --> 00:14:04,430
Caramba, como fago para clasificar os dous
metades, ou en cuartos, agora?

327
00:14:04,430 --> 00:14:05,260
>> Pero iso é OK.

328
00:14:05,260 --> 00:14:07,830
Temos un algoritmo de clasificación aquí.

329
00:14:07,830 --> 00:14:10,660
E aínda que se pode preocuparse en
por primeira vez esta é unha especie de infinito

330
00:14:10,660 --> 00:14:12,780
loop, é un ciclo que nunca
vai acabar - que vai

331
00:14:12,780 --> 00:14:15,770
acabar dunha vez o que pasa?

332
00:14:15,770 --> 00:14:16,970
Xa que non é inferior a 2.

333
00:14:16,970 --> 00:14:19,180
Que finalmente vai pasar,
porque se continúa e reducir á metade

334
00:14:19,180 --> 00:14:23,020
reducir á metade en reducir á metade destas metades, con certeza
finalmente, vai acabar

335
00:14:23,020 --> 00:14:25,350
con só 1 ou 0 elementos.

336
00:14:25,350 --> 00:14:28,500
En que punto, este algoritmo
di que está feito.

337
00:14:28,500 --> 00:14:31,020
>> Polo tanto, a verdadeira maxia neste
algoritmo parece estar en

338
00:14:31,020 --> 00:14:33,470
ese paso final, a fusión.

339
00:14:33,470 --> 00:14:37,190
Esta idea simple, só fusión de dous
cousas, que é o que finalmente vai

340
00:14:37,190 --> 00:14:40,920
que nos permiten clasificar unha matriz de,
digamos, oito elementos.

341
00:14:40,920 --> 00:14:44,410
Entón, eu teño oito bolas de estrés up
aquí, oito anacos de papel, e unha

342
00:14:44,410 --> 00:14:45,500
Google Glass -

343
00:14:45,500 --> 00:14:46,140
que eu teño que manter.

344
00:14:46,140 --> 00:14:46,960
>> [Risas]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Se puidésemos ter oito
voluntarios, e imos ver se podemos

346
00:14:48,970 --> 00:14:51,430
xogar iso, entón.

347
00:14:51,430 --> 00:14:52,500
Guau, Aceptar.

348
00:14:52,500 --> 00:14:53,565
Ciencia da computación está quedando divertido.

349
00:14:53,565 --> 00:14:54,320
Todo ben.

350
00:14:54,320 --> 00:14:57,770
Entón, que tal lle tres,
maior man alí enriba.

351
00:14:57,770 --> 00:14:58,580
Catro na parte de atrás.

352
00:14:58,580 --> 00:15:02,220
E como a nós imos facer
tres nesa liña?

353
00:15:02,220 --> 00:15:03,390
E catro diante.

354
00:15:03,390 --> 00:15:04,920
Entón oito, imos para arriba.

355
00:15:04,920 --> 00:15:12,060
>> [Risas]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: En realidade eu son
Non sei o que é.

357
00:15:13,450 --> 00:15:14,810
Son as bolas de estrés?

358
00:15:14,810 --> 00:15:16,510
As lámpadas de mesa?

359
00:15:16,510 --> 00:15:18,650
O material?

360
00:15:18,650 --> 00:15:19,680
Internet?

361
00:15:19,680 --> 00:15:20,160
>> Aceptar.

362
00:15:20,160 --> 00:15:21,310
Entón imos para arriba.

363
00:15:21,310 --> 00:15:22,310
Quen quere -

364
00:15:22,310 --> 00:15:23,570
seguen aparecendo.

365
00:15:23,570 --> 00:15:24,240
Imos ver.

366
00:15:24,240 --> 00:15:26,460
E iso pon vostede no lugar -

367
00:15:26,460 --> 00:15:27,940
está nunha situación.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, agarde un minuto.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - Oh, bo.

370
00:15:30,760 --> 00:15:31,310
Todo ben, estamos ben.

371
00:15:31,310 --> 00:15:35,130
Todo ben, entón todos teñen asento,
pero non no vidro de Google.

372
00:15:35,130 --> 00:15:36,475
Deixe-me facer cola estes anteriormente.

373
00:15:36,475 --> 00:15:37,115
Cal é o seu nome?

374
00:15:37,115 --> 00:15:37,440
>> MICHELLE: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID Malan: Michelle?

376
00:15:38,090 --> 00:15:42,000
Todo ben, comeza a ollar como
o geek, se está todo OK.

377
00:15:42,000 --> 00:15:44,625
Ben, eu tamén, supoño,
só por un momento.

378
00:15:44,625 --> 00:15:45,875
Todo ben, espera.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Estamos tentando chegar a un
caso de uso a Google de vidro, e nós

381
00:15:50,950 --> 00:15:53,750
penso que sería divertido facer só
iso cando a xente está no escenario.

382
00:15:53,750 --> 00:15:57,120
Imos gravar o mundo
a partir da súa perspectiva.

383
00:15:57,120 --> 00:15:58,410
Todo ben.

384
00:15:58,410 --> 00:15:59,830
Non probablemente Google pretendía.

385
00:15:59,830 --> 00:16:02,260
Todo ben, se non me importa de empregar
tanto para os próximos minutos difíciles,

386
00:16:02,260 --> 00:16:03,150
que sería marabilloso.

387
00:16:03,150 --> 00:16:08,620
>> Todo ben, entón temos aquí un conxunto de
elementos, e que a matriz, segundo a

388
00:16:08,620 --> 00:16:11,480
anacos de papel nesas persoas '
mans, está actualmente sen clasificación.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Oh, isto é tan estraño.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: É practicamente aleatoria.

391
00:16:12,810 --> 00:16:15,760
E, en só un momento, imos tratar
para aplicar especie se funden

392
00:16:15,760 --> 00:16:17,950
e ver onde ese insight clave.

393
00:16:17,950 --> 00:16:21,970
E o truco aquí con merge sort é
algo que non asumiron aínda.

394
00:16:21,970 --> 00:16:24,030
Nós realmente necesita dalgún
espazo adicional.

395
00:16:24,030 --> 00:16:26,650
Entón, o que será especialmente
interesante sobre iso é que estes

396
00:16:26,650 --> 00:16:29,270
caras van moverse un pouco
pouco, porque eu estou indo supor que

397
00:16:29,270 --> 00:16:31,880
hai un conxunto extra de espazo,
dicir, detrás deles.

398
00:16:31,880 --> 00:16:34,570
>> Entón, se eles están detrás da súa cadeira,
que é a matriz secundaria.

399
00:16:34,570 --> 00:16:36,960
Se eles están sentados aquí, iso é
a matriz primaria.

400
00:16:36,960 --> 00:16:40,170
Pero este é un recurso que temos
non aproveitados ata agora, coa burbulla

401
00:16:40,170 --> 00:16:42,040
tipo, coa selección de tipo,
coa ordenación por inserción.

402
00:16:42,040 --> 00:16:44,600
Teña en conta que, a semana pasada, todo o mundo
tipo de embaralhar no lugar.

403
00:16:44,600 --> 00:16:46,840
Eles non usan calquera memoria adicional.

404
00:16:46,840 --> 00:16:49,310
Fixemos espazo para a xente por
movemento de persoas en todo.

405
00:16:49,310 --> 00:16:50,580
>> Polo tanto, esta é unha visión de clave, tamén.

406
00:16:50,580 --> 00:16:53,410
Hai ese trade-off, en xeral, en
informática, de recursos.

407
00:16:53,410 --> 00:16:55,800
Se quere acelerar algo
como o tempo, vai

408
00:16:55,800 --> 00:16:56,900
ten que pagar un prezo.

409
00:16:56,900 --> 00:17:00,750
E un destes prezos é moitas veces
espazo, a cantidade de memoria ou disco

410
00:17:00,750 --> 00:17:01,700
espazo en disco que está a usar.

411
00:17:01,700 --> 00:17:03,640
Ou, francamente, a cantidade
programador de tempo.

412
00:17:03,640 --> 00:17:06,700
Canto tempo lle leva, o ser humano,
para realmente implementar un pouco máis

413
00:17:06,700 --> 00:17:07,829
algoritmo complicado.

414
00:17:07,829 --> 00:17:09,760
Pero, polo de hoxe, o trade-off
é tempo e espazo.

415
00:17:09,760 --> 00:17:11,930
>> Entón, se vostedes puidesen só soster o seu
números para que poidamos ver que é

416
00:17:11,930 --> 00:17:15,839
de feito correspondente 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Excelente.

418
00:17:16,599 --> 00:17:19,520
Entón eu vou tentar orquestrar
cousas, se vostedes poden só

419
00:17:19,520 --> 00:17:21,800
seguir miña liderado aquí.

420
00:17:21,800 --> 00:17:26,650
>> Entón, eu estou indo a aplicar, en primeiro lugar, o
primeiro paso do pseudocódigo, que é

421
00:17:26,650 --> 00:17:29,440
na entrada de n elementos, se non for
inferior a 2, despois de volver.

422
00:17:29,440 --> 00:17:31,370
Obviamente, que non fai
aplica-se, polo tanto, seguir adiante.

423
00:17:31,370 --> 00:17:33,340
Así clasificar a metade esquerda dos elementos.

424
00:17:33,340 --> 00:17:36,220
Entón iso significa que eu vou centrar a miña
atención por un momento sobre estes

425
00:17:36,220 --> 00:17:37,310
catro caras aquí.

426
00:17:37,310 --> 00:17:39,774
Todo ben, o que podo facer no próximo?

427
00:17:39,774 --> 00:17:40,570
>> Audiencia: clasificar a metade esquerda.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Entón agora eu teño que clasificar
a metade dereita destes caras.

429
00:17:42,780 --> 00:17:45,580
Porque unha vez máis, asumir para si a
obxectivo é clasificar a metade esquerda.

430
00:17:45,580 --> 00:17:46,440
Como fai iso?

431
00:17:46,440 --> 00:17:49,140
Só ten que seguir as instrucións, mesmo
que estamos a facer iso de novo.

432
00:17:49,140 --> 00:17:50,160
Así clasificar a metade esquerda.

433
00:17:50,160 --> 00:17:52,030
Agora estou clasificando estas dúas caras.

434
00:17:52,030 --> 00:17:53,563
O que vén a continuación?

435
00:17:53,563 --> 00:17:54,510
>> Audiencia: clasificar a metade esquerda.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: clasificar a metade esquerda.

437
00:17:55,460 --> 00:18:00,680
Entón, agora estes, este lugar aquí,
é unha lista de tamaño 1.

438
00:18:00,680 --> 00:18:01,365
E cal é o seu nome?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESA Daisy: Princesa Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princesa Daisy está aquí.

441
00:18:03,690 --> 00:18:07,470
E así ela xa está clasificado porque
a lista é de tamaño 1.

442
00:18:07,470 --> 00:18:09,490
¿Que podo facer na seguinte?

443
00:18:09,490 --> 00:18:13,680
OK, volver, porque esa lista é de
tamaño 1, que é inferior a 2.

444
00:18:13,680 --> 00:18:14,320
Entón cal é o seguinte paso?

445
00:18:14,320 --> 00:18:17,490
E agora ten que tipo de
volver atrás na súa mente.

446
00:18:17,490 --> 00:18:19,340
>> Ordenar a metade dereita, o que é -

447
00:18:19,340 --> 00:18:19,570
cal é o seu nome?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID Malan: Linda.

450
00:18:20,980 --> 00:18:23,210
E entón, o que facemos agora que
temos unha lista de tamaño 1?

451
00:18:23,210 --> 00:18:24,440
>> Audiencia: Return.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: Coidado.

453
00:18:24,760 --> 00:18:29,540
Volvemos primeiro, e agora o terceiro
etapa - e se eu tipo de representa-lo por

454
00:18:29,540 --> 00:18:33,490
asumindo os dous asentos agora, agora eu
ten que xuntar estes dous elementos.

455
00:18:33,490 --> 00:18:35,530
Entón, agora, por desgraza, os elementos
están fóra de orde.

456
00:18:35,530 --> 00:18:39,920
Pero é aí que o proceso de fusión
comeza a ser atractivo.

457
00:18:39,920 --> 00:18:42,410
>> Entón, se vostedes poderían erguer-se para só
un momento, eu vou ter que vostede, nun

458
00:18:42,410 --> 00:18:44,170
momento, para o paso detrás da súa cadeira.

459
00:18:44,170 --> 00:18:46,480
E si Linda, porque é 2
menor que 4, polo que non

460
00:18:46,480 --> 00:18:48,130
chega preto en primeiro lugar?

461
00:18:48,130 --> 00:18:48,690
Quede aí.

462
00:18:48,690 --> 00:18:50,520
Entón, Linda, que chega preto por primeira vez.

463
00:18:50,520 --> 00:18:53,820
>> Agora, en realidade, se é só unha matriz
poderiamos levala en tempo real

464
00:18:53,820 --> 00:18:55,360
dende esta materia a este punto.

465
00:18:55,360 --> 00:18:57,770
Entón, imaxine que tomou algunha constante
un número de pasos.

466
00:18:57,770 --> 00:18:58,480
E agora -

467
00:18:58,480 --> 00:19:01,490
pero precisamos poñelas
o primeiro lugar aquí.

468
00:19:01,490 --> 00:19:03,930
>> E agora, se puidese vir por aí,
así, imos

469
00:19:03,930 --> 00:19:06,300
estar no lugar dous.

470
00:19:06,300 --> 00:19:09,120
E aínda que este se sente como se fose
tomando un tempo, o que é bo é agora

471
00:19:09,120 --> 00:19:14,710
que a metade esquerda da
metade esquerda agora está clasificada.

472
00:19:14,710 --> 00:19:18,010
Entón, cal foi o seguinte paso, agora
retroceder aínda máis na historia?

473
00:19:18,010 --> 00:19:18,980
>> Audiencia: A metade dereita.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: clasificar a metade dereita.

475
00:19:19,900 --> 00:19:21,320
Entón, vós ten que facelo, tamén.

476
00:19:21,320 --> 00:19:23,510
Entón, se pode erguer-se
só por un momento?

477
00:19:23,510 --> 00:19:25,192
E cal é o seu nome?

478
00:19:25,192 --> 00:19:25,540
>> Jess: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID Malan: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, entón Jess é agora a esquerda
a metade da metade dereita.

481
00:19:29,720 --> 00:19:31,400
E así é unha lista de tamaño 1.

482
00:19:31,400 --> 00:19:32,380
Está claro clasificados.

483
00:19:32,380 --> 00:19:33,070
E o seu nome?

484
00:19:33,070 --> 00:19:33,630
>> MICHELLE: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle é, obviamente,
unha lista de tamaño 1.

486
00:19:35,340 --> 00:19:36,050
Ela xa está clasificada.

487
00:19:36,050 --> 00:19:38,690
Entón, agora a maxia acontece,
o proceso de fusión.

488
00:19:38,690 --> 00:19:39,790
Entón, quen vai vir en primeiro lugar?

489
00:19:39,790 --> 00:19:41,560
Obviamente, a Michelle.

490
00:19:41,560 --> 00:19:43,280
Entón, se podería vir en torno de volta.

491
00:19:43,280 --> 00:19:47,090
O espazo que temos dispoñible para ela agora
está ben atrás nesta materia aquí.

492
00:19:47,090 --> 00:19:51,580
E agora, se puidese volver, así como,
temos agora, para ser claro, dous

493
00:19:51,580 --> 00:19:53,810
metades, cada unha de tamaño 2 -

494
00:19:53,810 --> 00:19:57,090
e só por mor da representación, se
podería facer un pouco de espazo -

495
00:19:57,090 --> 00:19:59,780
un deixou metade aquí, un
metade aquí.

496
00:19:59,780 --> 00:20:01,160
>> Retroceder aínda máis na historia.

497
00:20:01,160 --> 00:20:02,270
Cal é o seguinte paso?

498
00:20:02,270 --> 00:20:03,030
>> Audiencia: Unir.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Polo tanto, agora temos que mesturar.

500
00:20:04,160 --> 00:20:07,490
Entón, OK, entón agora, por sorte, nos
só liberou catro cadeiras.

501
00:20:07,490 --> 00:20:11,480
Entón, usei o dobre da memoria, pero
podemos dar flip-flop entre

502
00:20:11,480 --> 00:20:12,330
dúas matrices.

503
00:20:12,330 --> 00:20:14,190
Entón, cal é o número que vir primeiro?

504
00:20:14,190 --> 00:20:14,850
Entón, Michelle, obviamente.

505
00:20:14,850 --> 00:20:16,680
Entón, volve cara
o seu lugar aquí.

506
00:20:16,680 --> 00:20:19,120
E, a continuación, o número 2 é obviamente
Logo, así que vir aquí.

507
00:20:19,120 --> 00:20:21,520
Número 4, número 6.

508
00:20:21,520 --> 00:20:23,390
E unha vez máis, aínda que non haxa unha
pouco de andar implicado,

509
00:20:23,390 --> 00:20:26,010
realmente, estas poderían ocorrer inmediatamente,
, Movendo unha -

510
00:20:26,010 --> 00:20:26,880
OK, así xogado.

511
00:20:26,880 --> 00:20:28,350
>> [Risas]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: E agora estamos
en moi boa forma.

513
00:20:29,680 --> 00:20:34,910
A metade esquerda da totalidade
entrada xa foi resolto.

514
00:20:34,910 --> 00:20:37,370
Todo ben, entón estes faces tiñan
a vantaxe de que a miña -

515
00:20:37,370 --> 00:20:40,340
como se rematar todas as nenas na
á esquerda e todos os nenos do lado dereito?

516
00:20:40,340 --> 00:20:42,450
>> OK, entón caras "virar agora.

517
00:20:42,450 --> 00:20:44,680
Entón eu non vou levalo a través
estes pasos.

518
00:20:44,680 --> 00:20:46,550
A ver se podemos reaplicar
mesmo pseudocódigo.

519
00:20:46,550 --> 00:20:50,050
Se quere ir adiante e levantarse,
e vós, déixeme darlle o micrófono.

520
00:20:50,050 --> 00:20:52,990
Vexa se non pode replicar o que
que fixemos aquí en

521
00:20:52,990 --> 00:20:53,880
outro extremo da lista.

522
00:20:53,880 --> 00:20:59,530
Quen precisa falar primeiro,
baseado no algoritmo?

523
00:20:59,530 --> 00:21:03,210
Entón explique o que está facendo antes de
de facer calquera movementos do pé.

524
00:21:03,210 --> 00:21:05,930
>> COLUMNA 1: Todo ben, entón desde
Eu son a metade esquerda da

525
00:21:05,930 --> 00:21:07,790
metade esquerda, eu volvo.

526
00:21:07,790 --> 00:21:08,730
Non?

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Xenial.

528
00:21:09,250 --> 00:21:10,350
>> COLUMNA 1: E entón -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Quen fai
o micrófono ir ao seguinte?

530
00:21:11,800 --> 00:21:12,920
>> COLUMNA 1: número seguinte.

531
00:21:12,920 --> 00:21:14,720
>> COLUMNA 2: Entón, eu son a metade dereita
da metade esquerda do

532
00:21:14,720 --> 00:21:17,830
metade esquerda, e eu atrás.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Xenial.

534
00:21:18,050 --> 00:21:18,550
Atrás.

535
00:21:18,550 --> 00:21:21,855
Entón, agora, cal é o próximo a vostedes dous?

536
00:21:21,855 --> 00:21:23,740
>> COLUMNA 2: Queremos ver quen é máis pequeno.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Exactamente.

538
00:21:24,200 --> 00:21:24,940
Queremos fundir.

539
00:21:24,940 --> 00:21:27,590
O espazo que imos usar para fundir
vostede, aínda que sexan

540
00:21:27,590 --> 00:21:30,250
obviamente, xa clasificado, imos
a continuación o mesmo algoritmo.

541
00:21:30,250 --> 00:21:31,560
Entón, quen vai primeiro?

542
00:21:31,560 --> 00:21:35,720
Entón, 3, e logo, 7.

543
00:21:35,720 --> 00:21:38,570
E agora o micrófono vai
para estes faces, OK?

544
00:21:38,570 --> 00:21:43,590
>> COLUMNA 3: Entón, eu son a metade dereita do
metade esquerda e meu n é inferior a

545
00:21:43,590 --> 00:21:45,048
1, entón eu só vou pasar -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Xenial.

547
00:21:46,380 --> 00:21:49,450
>> COLUMNA 4: Eu son a metade dereita do
metade dereita do lado dereito, e eu son

548
00:21:49,450 --> 00:21:51,740
tamén unha persoa, polo que estou
vai volver.

549
00:21:51,740 --> 00:21:52,990
Entón, agora que se funden.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> COLUMNA 3: Entón imos voltar.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Entón vai para a parte de atrás.

553
00:21:57,160 --> 00:21:59,200
Entón, 5 vai en primeiro lugar, a continuación, 8.

554
00:21:59,200 --> 00:22:01,240
E agora público, que é o
paso temos que volver agora

555
00:22:01,240 --> 00:22:02,200
voltar en nosas mentes?

556
00:22:02,200 --> 00:22:02,940
>> Audiencia: Unir.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: Fusión media esquerda e dereita
a metade da metade esquerda inicio.

558
00:22:07,270 --> 00:22:08,840
Entón, agora -

559
00:22:08,840 --> 00:22:10,520
e só para deixar isto claro,
facer un pouco de espazo

560
00:22:10,520 --> 00:22:11,690
entre vostedes dous.

561
00:22:11,690 --> 00:22:13,800
Polo tanto, agora que é as dúas listas,
esquerda e dereita.

562
00:22:13,800 --> 00:22:18,320
Entón, como imos agora unirse a vostedes en
a primeira fila de asentos de novo?

563
00:22:18,320 --> 00:22:19,600
>> 3 vai por primeira vez.

564
00:22:19,600 --> 00:22:20,850
Entón, 5, obviamente.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Logo, 7, e agora 8.

567
00:22:27,330 --> 00:22:28,710
OK, e agora estamos?

568
00:22:28,710 --> 00:22:29,650
>> Audiencia: Non fixo.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Non fixo, porque
Obviamente, hai unha única etapa restante.

570
00:22:32,440 --> 00:22:35,720
Pero, de novo, a razón que eu estou usando esta
xerga como "retroceder na súa mente"

571
00:22:35,720 --> 00:22:37,160
é por iso é realmente
o que está pasando.

572
00:22:37,160 --> 00:22:39,610
Estamos pasando por todas esas etapas,
pero nós somos unha especie de pausa para un

573
00:22:39,610 --> 00:22:42,480
momento, o mergullo máis profundo na
algoritmo, parando por un momento,

574
00:22:42,480 --> 00:22:45,840
mergullo máis fondo no algoritmo, e
agora temos a sorte de retroceso na nosa

575
00:22:45,840 --> 00:22:49,430
mentes e desfacer todas esas capas
que temos unha especie de poñer en espera.

576
00:22:49,430 --> 00:22:51,790
>> Polo tanto, agora temos dúas listas de tamaño 4.

577
00:22:51,790 --> 00:22:54,790
Se vós puidesen erguer-se unha última vez
e facer un pouco de espazo aquí para

578
00:22:54,790 --> 00:22:57,230
facer claro que esta é a esquerda
metade do orixinal, o

579
00:22:57,230 --> 00:22:58,620
metade dereita do orixinal.

580
00:22:58,620 --> 00:23:01,060
Quen é o primeiro número que
cómpre tirar na parte de atrás?

581
00:23:01,060 --> 00:23:01,870
Michelle, claro.

582
00:23:01,870 --> 00:23:03,230
>> Entón poñemos Michelle aquí.

583
00:23:03,230 --> 00:23:05,080
E quen ten o número 2?

584
00:23:05,080 --> 00:23:06,440
Número 2 vén na parte de atrás tamén.

585
00:23:06,440 --> 00:23:07,800
Número 3?

586
00:23:07,800 --> 00:23:08,510
Excelente.

587
00:23:08,510 --> 00:23:16,570
Número 4, número 5, número 6,
o número 7, e o número 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, polo que parecía moi
de pasos, con certeza.

589
00:23:18,850 --> 00:23:22,390
Pero agora imos ver se non podemos confirmar
tipo de intuitivamente que este

590
00:23:22,390 --> 00:23:26,190
algoritmo fundamental, especialmente no que
n queda moi grande, como xa vimos

591
00:23:26,190 --> 00:23:29,170
coas animacións, é
fundamentalmente máis rápido.

592
00:23:29,170 --> 00:23:33,400
Entón, eu reivindico este algoritmo, no peor
caso, e mesmo no mellor dos casos,

593
00:23:33,400 --> 00:23:36,160
é grande de n log n veces.

594
00:23:36,160 --> 00:23:39,160
É dicir, hai algún aspecto deste
algoritmo que leva n pasos, pero

595
00:23:39,160 --> 00:23:43,110
hai outro aspecto en algún lugar
iteración, que Looping, que

596
00:23:43,110 --> 00:23:44,410
leva log n pasos.

597
00:23:44,410 --> 00:23:49,154
Podemos poñer o dedo sobre o que os
dous números están referindo?

598
00:23:49,154 --> 00:23:51,320
Ben, onde -

599
00:23:51,320 --> 00:23:54,160
o micrófono para onde ir?

600
00:23:54,160 --> 00:23:58,660
>> COLUMNA 1: Será que o rexistro n ser
rompendo connosco en dous -

601
00:23:58,660 --> 00:23:59,630
dividindo por dous, esencialmente.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Exactamente.

603
00:24:00,120 --> 00:24:03,000
Cada vez que podemos ver en calquera algoritmo, polo tanto,
agora, non foi ese patrón de

604
00:24:03,000 --> 00:24:04,200
divisoria, dividindo, dividindo.

605
00:24:04,200 --> 00:24:05,700
E é normalmente reducida
a algo que é

606
00:24:05,700 --> 00:24:07,100
logarítmica, base 2 log.

607
00:24:07,100 --> 00:24:10,180
Pero realmente pode ser calquera cousa,
pero log base 2.

608
00:24:10,180 --> 00:24:11,330
>> Agora, o que dicir do n?

609
00:24:11,330 --> 00:24:14,550
Podo ver que tipo de dividido ti
homes - divididos ti, divididos ti,

610
00:24:14,550 --> 00:24:15,910
divididos ti, divididos ti.

611
00:24:15,910 --> 00:24:18,760
Onde é que o fin vén?

612
00:24:18,760 --> 00:24:19,810
>> Polo tanto, é a fusión.

613
00:24:19,810 --> 00:24:20,610
Porque pensar niso.

614
00:24:20,610 --> 00:24:25,420
Cando mestura oito persoas en conxunto,
en que a metade deles son un conxunto de catro

615
00:24:25,420 --> 00:24:27,770
ea outra metade é outra
conxunto de catro, como vai

616
00:24:27,770 --> 00:24:28,820
sobre como facer a fusión?

617
00:24:28,820 --> 00:24:30,830
Ben, vostedes fixeron iso
moi intuitiva.

618
00:24:30,830 --> 00:24:34,140
>> Pero se en vez fixen un pouco máis
metodicamente, eu podería ter apuntado para

619
00:24:34,140 --> 00:24:38,090
a persoa máis á esquerda por primeira vez coa miña esquerda
man, sinalou a persoa máis á esquerda

620
00:24:38,090 --> 00:24:42,080
de que a metade coa miña man dereita, e
só posteriormente pasou pola

621
00:24:42,080 --> 00:24:46,990
lista, apuntando a menor elemento
cada vez, movendo o dedo sobre e

622
00:24:46,990 --> 00:24:48,970
sobre cando sexa necesario ao longo da lista.

623
00:24:48,970 --> 00:24:51,890
Pero o que é importante sobre esta fusión
proceso é que eu estou comparando estes pares

624
00:24:51,890 --> 00:24:53,460
de elementos.

625
00:24:53,460 --> 00:24:57,270
A partir da metade da dereita e da esquerda
metade, estou nunca xa retroceso.

626
00:24:57,270 --> 00:25:00,570
>> Así, o propio merge está tomando
non máis que n pasos.

627
00:25:00,570 --> 00:25:03,250
E cantas veces eu tiven
para facer que a fusión?

628
00:25:03,250 --> 00:25:07,150
Ben, non máis que n, e nós só
viu que, coa fusión final.

629
00:25:07,150 --> 00:25:13,120
E por iso, se fai algo que leva
rexistro veces n pasos n, ou viceversa,

630
00:25:13,120 --> 00:25:15,210
que vai nos n log n veces dar.

631
00:25:15,210 --> 00:25:16,310
>> E por que é mellor?

632
00:25:16,310 --> 00:25:19,600
Ben, se xa coñecemos rexistro
n é mellor que n - non?

633
00:25:19,600 --> 00:25:22,590
Vimos en busca binaria, o libro de teléfono
exemplo, log n foi definitivamente

634
00:25:22,590 --> 00:25:23,760
mellor que o lineal.

635
00:25:23,760 --> 00:25:28,420
Entón iso significa que n log n veces é
sempre mellor que n veces outro

636
00:25:28,420 --> 00:25:30,390
n, aka n ao cadrado.

637
00:25:30,390 --> 00:25:32,400
E iso é o que finalmente se sente.

638
00:25:32,400 --> 00:25:34,928
>> Tan grande salva de palmas, se
puidésemos, para estes faces.

639
00:25:34,928 --> 00:25:38,920
>> [Aplausos]

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: E os seus regalos de despedida -
pode manter os números,

641
00:25:41,550 --> 00:25:44,010
se desexa.

642
00:25:44,010 --> 00:25:45,620
E o seu agasallo de despedida, como de costume.

643
00:25:45,620 --> 00:25:47,290
Ah, e nós enviarémosche
a metragem, Michelle.

644
00:25:47,290 --> 00:25:48,343
Grazas.

645
00:25:48,343 --> 00:25:49,250
Todo ben.

646
00:25:49,250 --> 00:25:50,400
Sirva-se dunha pelota de estrés.

647
00:25:50,400 --> 00:25:54,110
>> E déixeme puxar arriba, con todo,
noso amigo Rob Bowden para ofrecer

648
00:25:54,110 --> 00:25:59,520
perspectiva un pouco diferente deste,
sempre que pode pensar sobre estes

649
00:25:59,520 --> 00:26:01,280
etapas que acontecen en algo
xeito diferente.

650
00:26:01,280 --> 00:26:04,750
En realidade, o set-up para o que Rob está a piques
para amosar asume que temos

651
00:26:04,750 --> 00:26:09,030
feito a división do
gran lista en oito pequenas listas,

652
00:26:09,030 --> 00:26:10,570
cada un de tamaño 1.

653
00:26:10,570 --> 00:26:13,350
>> Entón, nós estamos cambiando o pseudocódigo a
pouco só a sorte de chegar ao

654
00:26:13,350 --> 00:26:15,320
idea central de como a fusión obras.

655
00:26:15,320 --> 00:26:17,600
Pero o tempo de funcionamento do que
está a piques de facer aínda é

656
00:26:17,600 --> 00:26:19,110
será o mesmo.

657
00:26:19,110 --> 00:26:23,540
E, de novo, o set-up aquí é que é
iniciado con oito listas de tamaño 1.

658
00:26:23,540 --> 00:26:27,730
Entón perdeu a parte onde el é
realmente fixo o rexistro n, n log, log n

659
00:26:27,730 --> 00:26:31,205
división da entrada.

660
00:26:31,205 --> 00:26:32,120
>> [REPRODUCIÓN]

661
00:26:32,120 --> 00:26:33,615
>> -Iso é todo por un paso.

662
00:26:33,615 --> 00:26:38,270
Para a segunda etapa, de xeito repetido
pares de listas de mala directa.

663
00:26:38,270 --> 00:26:39,210
>> DAVID Malan: Hm.

664
00:26:39,210 --> 00:26:41,270
Só audio está chegando
fóra do meu ordenador.

665
00:26:41,270 --> 00:26:42,520
Imos tentar iso de novo.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Just arbitrariamente escoller cal -
agora temos catro listas.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Saber antes.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Alí imos nós.

671
00:26:53,040 --> 00:27:00,510
>> Mesclando-108 e 15, terminais
coa lista de 15, 108.

672
00:27:00,510 --> 00:27:07,170
Fundir 50 e 4, temos
acabar con 4, 50.

673
00:27:07,170 --> 00:27:12,990
Mesclando 8 e 42, que
acabar con 8, 42.

674
00:27:12,990 --> 00:27:19,970
E fusión 23 e 16, nos
acabar con 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Agora todas as nosas listas son de tamaño 2.

676
00:27:23,270 --> 00:27:26,690
Observe-se que cada un dos
catro listas é clasificado.

677
00:27:26,690 --> 00:27:29,450
Así, podemos comezar a fundirse
pares de listas de novo.

678
00:27:29,450 --> 00:27:38,420
Mesclando 15 e 108 e 4 e 50, que
tire primeiro a 4, logo a 15, logo

679
00:27:38,420 --> 00:27:41,500
a 50, logo a 108.

680
00:27:41,500 --> 00:27:50,610
Mesclando 8, 42 e 16, 23, primeiro tomar
a 8, a continuación, a 16, logo a 23,

681
00:27:50,610 --> 00:27:52,700
logo a 42.

682
00:27:52,700 --> 00:27:57,600
>> Polo tanto, agora temos só dúas listas de tamaño
4, cada un dos cales é clasificado.

683
00:27:57,600 --> 00:28:01,170
Entón, agora nós mesturar estas dúas listas.

684
00:28:01,170 --> 00:28:11,835
En primeiro lugar, tomamos a 4, despois tomamos o
8, así que tomamos o 15, entón con 16 anos, logo

685
00:28:11,835 --> 00:28:19,456
23, despois 42, despois 50, despois 108.

686
00:28:19,456 --> 00:28:19,872
>> [FIN reprodución de vídeo]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Unha vez máis, o aviso previo, nunca
tocado un determinado vaso máis do que xa

688
00:28:23,430 --> 00:28:24,860
tras avanzar alén dela.

689
00:28:24,860 --> 00:28:26,200
Así, el nunca repetir.

690
00:28:26,200 --> 00:28:29,850
Polo que sempre está movendo cara ao lado,
e é aí onde temos o noso n.

691
00:28:29,850 --> 00:28:33,290
>> Por que non deixar me puxar arriba unha animación
que vimos anteriormente, pero esta vez

692
00:28:33,290 --> 00:28:35,110
incidir só sobre merge sort.

693
00:28:35,110 --> 00:28:38,030
Déixeme ir adiante e facer zoom
en nesta aquí.

694
00:28:38,030 --> 00:28:42,530
Primeiro déixeme escoller unha entrada aleatoria,
ampliar iso, e pode clasificar de ver

695
00:28:42,530 --> 00:28:46,600
o que nós tomamos para concedida, anteriormente,
merge sort está realmente facendo.

696
00:28:46,600 --> 00:28:50,330
>> Entón, teña en conta que obter esas metades ou
estes cuartos ou estes oitavos de

697
00:28:50,330 --> 00:28:53,140
problema que, de súpeto,
comezar a tomar boa forma.

698
00:28:53,140 --> 00:28:57,070
E entón, finalmente, ve a
o fin que Bam,

699
00:28:57,070 --> 00:28:58,860
todo é mezclado xuntos.

700
00:28:58,860 --> 00:29:01,690
>> Entón, estas son só tres diferentes
asume a mesma idea.

701
00:29:01,690 --> 00:29:05,980
Pero o insight clave, así como dividir
e conquistar na primeira clase,

702
00:29:05,980 --> 00:29:10,640
foi que decidimos dividir dalgún xeito
o problema en algo grande, en

703
00:29:10,640 --> 00:29:14,760
algo tipo de idéntico en espírito,
pero máis pequenos e pequenas

704
00:29:14,760 --> 00:29:15,660
e menores.

705
00:29:15,660 --> 00:29:18,420
>> Agora outra forma divertida de clasificar de pensar
sobre estes, a pesar de que non é

706
00:29:18,420 --> 00:29:20,520
vai darlle o mesmo intuitiva
entendemento, é

707
00:29:20,520 --> 00:29:21,640
a seguinte animación.

708
00:29:21,640 --> 00:29:25,400
Polo tanto, este é un vídeo de alguén xuntos
que asociado distinto

709
00:29:25,400 --> 00:29:29,970
sons coas varias operacións para
ordenación por inserción, por merge sort, e

710
00:29:29,970 --> 00:29:31,150
por un par de outros.

711
00:29:31,150 --> 00:29:32,330
Entón, nun momento, eu vou bater Play.

712
00:29:32,330 --> 00:29:33,600
Trátase de un minuto de duración.

713
00:29:33,600 --> 00:29:37,410
E aínda que aínda pode ver a
patróns pasando, neste momento pode

714
00:29:37,410 --> 00:29:41,420
tamén escoitar como estes algoritmos son
realizar de xeito diferente e con

715
00:29:41,420 --> 00:29:43,950
un pouco diferentes patróns.

716
00:29:43,950 --> 00:29:45,830
>> Esta é a ordenación por inserción.

717
00:29:45,830 --> 00:29:50,400
>> [Tons XOGO]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: El novo está intentando
para introducir cada elemento

719
00:29:52,400 --> 00:29:52,900
para onde ela pertence.

720
00:29:52,900 --> 00:29:54,628
Este é bubble sort.

721
00:29:54,628 --> 00:30:10,097
>> [Tons XOGO]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: E pode clasificar de sensación
como relativamente pouco traballo que está a facer

723
00:30:13,630 --> 00:30:15,834
en cada paso.

724
00:30:15,834 --> 00:30:20,470
Isto é o aburrimento parece.

725
00:30:20,470 --> 00:30:21,472
>> [Tons XOGO]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Esta é a selección de tipo,
onde se selecciona o elemento que queremos por

727
00:30:25,222 --> 00:30:28,845
pasando por unha e outra vez e outra vez
e poñelas no inicio.

728
00:30:28,845 --> 00:30:37,674
>> [Tons XOGO]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Este é o merge sort, que
realmente pode comezar a sentir-se.

730
00:30:43,970 --> 00:30:51,810
>> [Tons XOGO]

731
00:30:51,810 --> 00:30:54,770
>> [Risas]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Algo chamado gnome
tipo, que non mirei.

733
00:30:58,395 --> 00:31:13,630
>> [Tons XOGO]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Entón déixeme ver, agora,
distraído como espera, segundo a

735
00:31:17,910 --> 00:31:21,110
música, se podo escorregar algo
pouco de matemáticas aquí.

736
00:31:21,110 --> 00:31:24,850
Polo tanto, hai unha cuarta forma que pudermos
pensar sobre o que quere dicir que estes

737
00:31:24,850 --> 00:31:29,210
funcións para ser máis rápido que os
que xa vimos antes.

738
00:31:29,210 --> 00:31:32,470
E se está a benvida para o curso de
un fondo de matemáticas,

739
00:31:32,470 --> 00:31:36,030
realmente sabe, se cadra, xa que
pode bater un termo sobre esta técnica -

740
00:31:36,030 --> 00:31:40,400
ou sexa, a recursividade, unha función
que dalgún xeito se autodenomina.

741
00:31:40,400 --> 00:31:44,780
>> E unha vez máis, recordar que merge sort
pseudocódigo foi recursivo no sentido

742
00:31:44,780 --> 00:31:48,460
que unha das etapas do merge sort
foi chamar especie -

743
00:31:48,460 --> 00:31:49,740
que é, en si.

744
00:31:49,740 --> 00:31:52,480
Pero, por sorte, xa mantivemos
chamando tipo, ou merge sort,

745
00:31:52,480 --> 00:31:55,880
En concreto, nunha menor e menor
e unha lista pequena, finalmente

746
00:31:55,880 --> 00:32:00,005
ao fondo do pozo grazas ao que chamaremos
un caso base, o caso hard-Coded que

747
00:32:00,005 --> 00:32:04,270
dixo que se a lista é pequena, menos de 2
Neste caso, só tes que volver inmediatamente.

748
00:32:04,270 --> 00:32:07,550
Se non tivésemos ese caso especial, a
algoritmo sería nunca inferior para fóra,

749
00:32:07,550 --> 00:32:11,010
e realmente entrar nun
loop infinito verdadeiramente para sempre.

750
00:32:11,010 --> 00:32:14,330
>> Pero supoñamos que queremos agora poñer
algúns números no presente, de novo, utilizando n

751
00:32:14,330 --> 00:32:15,660
medida que o tamaño da entrada.

752
00:32:15,660 --> 00:32:18,680
E eu quería preguntar, o que é
o tempo total involucrado

753
00:32:18,680 --> 00:32:19,800
execución merge sort?

754
00:32:19,800 --> 00:32:22,960
Ou, máis xeralmente, o que é
o custo do mesmo no tempo?

755
00:32:22,960 --> 00:32:24,730
>> Ben, é moi fácil de medir isto.

756
00:32:24,730 --> 00:32:29,010
Se n é menor que 2, o tempo envolto
na clasificación de n elementos,

757
00:32:29,010 --> 00:32:30,480
onde n é 2, é 0.

758
00:32:30,480 --> 00:32:31,410
Porque só retornar.

759
00:32:31,410 --> 00:32:32,510
Non hai traballo a ser feito.

760
00:32:32,510 --> 00:32:35,660
Agora, sen dúbida, é posible que un paso ou dous
pasos para descubrir a cantidade de

761
00:32:35,660 --> 00:32:38,420
traballar, pero é preto o suficiente para que 0
Eu só vou dicir que non traballo é

762
00:32:38,420 --> 00:32:40,940
necesario se a lista é tan pequena
para ser desinteressante.

763
00:32:40,940 --> 00:32:42,580
>> Pero, neste caso, é interesante.

764
00:32:42,580 --> 00:32:47,320
O caso recursivo foi o sector de
o pseudocódigo que dixo outra cousa, tipo

765
00:32:47,320 --> 00:32:52,000
a metade esquerda, clasificar o dereito
metade, unir as dúas metades.

766
00:32:52,000 --> 00:32:55,530
Agora, por que esta expresión
representar esa gasto?

767
00:32:55,530 --> 00:32:58,690
Ben, T de n significa só que o
tempo para ordenar n elementos.

768
00:32:58,690 --> 00:33:03,070
E, a continuación, no lado dereito da
signo igual alí, o T de n dividido

769
00:33:03,070 --> 00:33:06,600
por 2 refírese ao custo de que?

770
00:33:06,600 --> 00:33:07,570
Clasificando a metade esquerda.

771
00:33:07,570 --> 00:33:10,990
O outro T de n dividido por 2 é
presuntamente, referíndose ao custo

772
00:33:10,990 --> 00:33:12,390
clasificar a metade dereita.

773
00:33:12,390 --> 00:33:14,590
>> E entón o máis n?

774
00:33:14,590 --> 00:33:15,420
É a fusión.

775
00:33:15,420 --> 00:33:19,120
Porque se ten dúas listas, unha de
tamaño n superior a 2 e outra de tamaño n

776
00:33:19,120 --> 00:33:22,580
máis de 2, ten que tocar esencialmente
cada un destes elementos, así como Rob

777
00:33:22,580 --> 00:33:24,990
tocou cada un dos vasos, e só
como se sinalou para cada un dos

778
00:33:24,990 --> 00:33:26,310
voluntarios no escenario.

779
00:33:26,310 --> 00:33:28,790
Así, n é á custa de fusión.

780
00:33:28,790 --> 00:33:31,780
>> Agora, desgraciadamente, esta fórmula
é tamén propio recursiva.

781
00:33:31,780 --> 00:33:36,390
Así se fixo a pregunta, se non é, digamos,
16, se hai 16 persoas no escenario

782
00:33:36,390 --> 00:33:40,670
ou 16 cuncas no vídeo, cantos total de
pasos que é necesario para clasificalos los

783
00:33:40,670 --> 00:33:41,550
con merge sort?

784
00:33:41,550 --> 00:33:45,790
En realidade non é unha resposta obvia,
porque agora ten a sorte de

785
00:33:45,790 --> 00:33:48,500
recursivamente responder a esta fórmula.

786
00:33:48,500 --> 00:33:51,190
>> Pero todo ben, porque déixeme propoñer
que faga o seguinte.

787
00:33:51,190 --> 00:33:56,670
O tempo implicado para clasificar ou 16 persoas
16 cuncas será representado

788
00:33:56,670 --> 00:33:58,020
xeralmente como T de 16.

789
00:33:58,020 --> 00:34:01,400
Pero o que é igual a, segundo o noso
fórmula anterior, dúas veces a cantidade

790
00:34:01,400 --> 00:34:04,780
de tempo que leva para clasificar
8 vasos máis 16.

791
00:34:04,780 --> 00:34:08,590
E, de novo, máis 16 é o momento de fusión,
E as dúas veces T de 8 é o

792
00:34:08,590 --> 00:34:10,790
tempo para resolver a metade esquerda e metade dereita.

793
00:34:10,790 --> 00:34:11,989
>> Pero, de novo, iso non é suficiente.

794
00:34:11,989 --> 00:34:13,210
Temos que mergullar máis fondo.

795
00:34:13,210 --> 00:34:16,409
Isto significa que temos que responder á
pregunta, o que é T de 8?

796
00:34:16,409 --> 00:34:19,610
Ben T de 8 está só a 2
t de 4 veces máis de 8.

797
00:34:19,610 --> 00:34:20,520
Ben, o que é T de 4?

798
00:34:20,520 --> 00:34:23,780
T de 4 está a só 2 veces T de 2 + 4.

799
00:34:23,780 --> 00:34:25,489
Ben, o que é T de 2?

800
00:34:25,489 --> 00:34:29,030
T de 2 é só 2 veces T de 1 máis 2.

801
00:34:29,030 --> 00:34:31,940
>> E, de novo, somos o tipo de conseguir
preso neste ciclo.

802
00:34:31,940 --> 00:34:34,790
Pero iso está a piques de bater ese
o chamado caso base.

803
00:34:34,790 --> 00:34:37,310
Porque o que é T 1, non podemos reclamar?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Entón, agora, por fin, podemos traballar para tras.

806
00:34:39,730 --> 00:34:44,290
>> Se T 1 é 0, agora podo volver a subir un
aliñar con este cara aquí, e podo

807
00:34:44,290 --> 00:34:46,330
Póñase 0 para T de 1.

808
00:34:46,330 --> 00:34:51,770
Entón, iso significa que é igual a 2 veces a cero,
tamén coñecido como 0, acrescido de 2.

809
00:34:51,770 --> 00:34:53,739
E, de xeito que toda a expresión é 2.

810
00:34:53,739 --> 00:34:58,740
>> Agora, se eu incorporarse o T de 2, cuxa resposta
é 2, liga-lo na liña do medio, T

811
00:34:58,740 --> 00:35:02,740
de 4, que me dá dúas veces
2 + 4, de modo 8.

812
00:35:02,740 --> 00:35:07,080
Agora ben, se eu conectar 8 a anterior
liña, que me dá dúas veces 8, 16.

813
00:35:07,080 --> 00:35:12,470
E se, a continuación, continuar co que
24, engadindo o 16 de finalmente obter un

814
00:35:12,470 --> 00:35:13,820
valor de 64.

815
00:35:13,820 --> 00:35:18,480
>> Agora que en si mesmo tipo de fala
nada para a notación n, o

816
00:35:18,480 --> 00:35:20,700
O gran, o omega que temos
falando.

817
00:35:20,700 --> 00:35:24,890
Pero verifícase que 64 é de feito
16, o tamaño da entrada,

818
00:35:24,890 --> 00:35:27,110
rexistro base 2, de 16.

819
00:35:27,110 --> 00:35:30,200
E se isto é un pouco raro, só
creo que volta, e el vai volver

820
00:35:30,200 --> 00:35:30,700
para que eventualmente.

821
00:35:30,700 --> 00:35:33,775
Se este é o rexistro base 2, é como 2
elevado para o que lle dá 16?

822
00:35:33,775 --> 00:35:36,380
Oh, iso é 4, polo que é 16 veces 4.

823
00:35:36,380 --> 00:35:39,380
>> E unha vez máis, non é un gran negocio se este
é unha especie de memoria nebulosa agora.

824
00:35:39,380 --> 00:35:43,720
Pero, polo de agora, asumir a fe
que 16 log 16 é 64.

825
00:35:43,720 --> 00:35:46,590
E así, de feito, con esta sinxela sanidade
comprobar, temos confirmada -

826
00:35:46,590 --> 00:35:48,250
pero non demostrou formalmente -

827
00:35:48,250 --> 00:35:52,800
que o tempo de execución de fusión
especie é realmente n log n.

828
00:35:52,800 --> 00:35:53,790
>> Entón, non é malo.

829
00:35:53,790 --> 00:35:57,260
É sempre mellor que o
algoritmos que vimos ata agora, e

830
00:35:57,260 --> 00:36:00,710
é porque temos panca, un,
unha técnica chamada de recursão.

831
00:36:00,710 --> 00:36:03,880
Pero o máis interesante do que iso, que
noción de dividir e conquistar.

832
00:36:03,880 --> 00:36:07,460
Unha vez máis, verdadeiramente semana 0 cousas que
ata agora é recorrente en

833
00:36:07,460 --> 00:36:08,740
forma máis convincente.

834
00:36:08,740 --> 00:36:11,750
>> Agora, un pouco de exercicio divertido, se ten
nunca fixen iso - e probablemente

835
00:36:11,750 --> 00:36:14,660
non tería porque tipo do normal
a xente non pensa para facelo.

836
00:36:14,660 --> 00:36:20,650
Pero se eu for a google.com e se
Quero aprender algo sobre

837
00:36:20,650 --> 00:36:22,356
recursão, Intro.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Risas]

840
00:36:29,058 --> 00:36:32,030
[Máis risas]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Bad broma estendendo lentamente.

842
00:36:33,385 --> 00:36:34,450
[Risas]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Só no caso, el está alí.

844
00:36:36,970 --> 00:36:38,710
Non deletrear mal,
e hai a broma.

845
00:36:38,710 --> 00:36:40,810
Todo ben.

846
00:36:40,810 --> 00:36:42,950
Explique-os persoas próximas a vostede se
el non ten moito premendo aínda.

847
00:36:42,950 --> 00:36:47,650
Pero recursão, de xeito máis xeral, refírese a
para o proceso de unha función de chamadas

848
00:36:47,650 --> 00:36:51,430
si só, ou, máis xeralmente, a división dun
problema en algo que se pode

849
00:36:51,430 --> 00:36:56,220
resoltos aos poucos, resolvendo o mesmo
problemas de representación.

850
00:36:56,220 --> 00:36:58,400
>> Ben, imos engrenaxes de cambio
só por un momento.

851
00:36:58,400 --> 00:37:00,840
Gústanos de rematar en certos cliffhangers,
entón imos comezar a definir

852
00:37:00,840 --> 00:37:05,870
a fase, durante varios minutos,
nunha idea moi simple -

853
00:37:05,870 --> 00:37:07,620
que o intercambio de dous elementos, non?

854
00:37:07,620 --> 00:37:10,040
Todos estes algoritmos que estivemos
falando sobre o último par de

855
00:37:10,040 --> 00:37:12,420
conferencias implica algún
tipo de cambio.

856
00:37:12,420 --> 00:37:14,630
Hoxe foi vistos por eles recibido
-Se das súas materias e

857
00:37:14,630 --> 00:37:18,570
camiñando por aí, pero o código, fariamos
pode ter un elemento dunha matriz

858
00:37:18,570 --> 00:37:20,370
e plop-lo noutro.

859
00:37:20,370 --> 00:37:21,880
>> Entón, como imos facelo?

860
00:37:21,880 --> 00:37:24,850
Ben, deixe-me ir adiante e escribir
un programa rápido aquí.

861
00:37:24,850 --> 00:37:31,600
Eu estou indo a ir adiante e facer
isto como a continuación.

862
00:37:31,600 --> 00:37:33,910
Imos chamar iso -

863
00:37:33,910 --> 00:37:38,070
o que queremos chamar este?

864
00:37:38,070 --> 00:37:38,650
>> En realidade, non.

865
00:37:38,650 --> 00:37:39,420
Déixeme volver atrás.

866
00:37:39,420 --> 00:37:41,220
Non quero facelo
suspense aínda.

867
00:37:41,220 --> 00:37:42,270
Vai romper a diversión.

868
00:37:42,270 --> 00:37:43,600
Imos facelo no seu lugar.

869
00:37:43,600 --> 00:37:47,430
>> Supoñamos que quero escribir un pouco
programa e que agora abraza este

870
00:37:47,430 --> 00:37:48,700
idea de recursão.

871
00:37:48,700 --> 00:37:50,370
Eu medio que teño diante de min alí.

872
00:37:50,370 --> 00:37:51,420
Vou facer o seguinte.

873
00:37:51,420 --> 00:38:00,220
>> En primeiro lugar, un rápido inclúen estándar de io.h,
, Así como unha inclusión cs50.h.

874
00:38:00,220 --> 00:38:03,200
E entón eu estou indo a ir adiante
e declarar int void main

875
00:38:03,200 --> 00:38:04,360
do xeito habitual.

876
00:38:04,360 --> 00:38:07,920
Podo entender que eu teño chamado erroneamente o ficheiro, así
déixeme engadir unha extensión c. aquí para

877
00:38:07,920 --> 00:38:09,510
que podemos recompila-lo correctamente.

878
00:38:09,510 --> 00:38:10,970
Comeza esta función.

879
00:38:10,970 --> 00:38:13,290
>> E a función que quero escribir, moito
simplemente, é o que fai a

880
00:38:13,290 --> 00:38:16,210
usuario a un número e, a continuación, engade-se
todos os números entre ese

881
00:38:16,210 --> 00:38:19,920
número e, por exemplo, 0.

882
00:38:19,920 --> 00:38:22,510
Entón, primeiro eu vou seguir adiante
e declarar int n.

883
00:38:22,510 --> 00:38:24,760
Entón eu copiar un código que
usamos por un tempo.

884
00:38:24,760 --> 00:38:26,660
Mentres algo é certo.

885
00:38:26,660 --> 00:38:28,000
Eu vou volver a iso nun momento.

886
00:38:28,000 --> 00:38:29,010
>> O que quero facer?

887
00:38:29,010 --> 00:38:33,460
Quero dicir printf positivo
enteiro por favor.

888
00:38:33,460 --> 00:38:36,130
E entón eu vou
din que non recibe obter int.

889
00:38:36,130 --> 00:38:38,800
Entón, de novo, algún código cliché
que usei antes.

890
00:38:38,800 --> 00:38:40,810
E eu vou facer iso
mentres n sexa menor que 1.

891
00:38:40,810 --> 00:38:44,120
Así, isto pode asegurar que o usuario
dáme un enteiro positivo.

892
00:38:44,120 --> 00:38:45,490
>> E agora eu vou facer o seguinte.

893
00:38:45,490 --> 00:38:51,020
Quero sumar todos os números
e entre 1 e n, ou 0 e n,

894
00:38:51,020 --> 00:38:52,570
equivalentemente, para obter a suma total.

895
00:38:52,570 --> 00:38:55,100
Así, o símbolo gran sigma
que pode lembrar.

896
00:38:55,100 --> 00:38:59,050
Entón, eu vou facelo por primeira convocatoria
unha función chamada Sigma,

897
00:38:59,050 --> 00:39:06,030
pasalo en n, e entón eu vou
printf dicir, a resposta está logo alí.

898
00:39:06,030 --> 00:39:08,180
>> Así, en breve, eu recibín e
int do usuario.

899
00:39:08,180 --> 00:39:09,280
I garantir que é positivo.

900
00:39:09,280 --> 00:39:12,700
Eu declaro unha variable chamada resposta de
tipo int e almacenar no que o retorno

901
00:39:12,700 --> 00:39:15,610
valor de Sigma, pasando n como entrada.

902
00:39:15,610 --> 00:39:17,060
E entón eu imprimir esa resposta.

903
00:39:17,060 --> 00:39:19,550
>> Por desgraza, aínda sigma soa
como algo que pode estar en

904
00:39:19,550 --> 00:39:24,040
o ficheiro math.h, a súa declaración,
iso non é certo.

905
00:39:24,040 --> 00:39:24,690
Entón, iso é OK.

906
00:39:24,690 --> 00:39:26,170
Podo aplicar iso mesmo.

907
00:39:26,170 --> 00:39:29,160
Vou aplicar unha función chamada
sigma, e iso vai levar un

908
00:39:29,160 --> 00:39:29,900
parámetro -

909
00:39:29,900 --> 00:39:32,100
imos chamalo m, só
polo que é diferente.

910
00:39:32,100 --> 00:39:35,910
E, a continuación, ata aquí, eu vou dicir,
así, se m é menor que 1 - Este é un

911
00:39:35,910 --> 00:39:38,180
programa moi desinteressante.

912
00:39:38,180 --> 00:39:41,700
Entón, eu estou indo a ir adiante e
inmediatamente devolver 0.

913
00:39:41,700 --> 00:39:45,920
El simplemente non ten sentido sumar todos
os números entre 1 e n se m

914
00:39:45,920 --> 00:39:48,470
0 é el mesmo ou negativo.

915
00:39:48,470 --> 00:39:50,900
>> E entón eu estou indo a ir adiante
e facelo moi iterativa.

916
00:39:50,900 --> 00:39:53,090
Vou facer este tipo de old-school,
e eu estou indo a ir adiante

917
00:39:53,090 --> 00:39:57,150
e dicir que eu vou
declarar unha cantidade a ser 0.

918
00:39:57,150 --> 00:39:59,630
Entón eu vou ter
un loop de int -

919
00:39:59,630 --> 00:40:02,820
e deixe-me facelo para coincidir co noso
Código de distribución, para que teña unha copia

920
00:40:02,820 --> 00:40:07,500
na casa. int i recibe 1 en ata
i é inferior ou igual a m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
E, a continuación, dentro deste loop -

923
00:40:11,430 --> 00:40:12,440
estamos case alí -

924
00:40:12,440 --> 00:40:15,810
suma queda suma máis 1.

925
00:40:15,810 --> 00:40:17,670
E entón eu vou volver a suma.

926
00:40:17,670 --> 00:40:19,420
>> Entón eu fixen iso axiña,
reconhecidamente bastante.

927
00:40:19,420 --> 00:40:22,775
Pero, de novo, a principal función é moi
simple, baseado no código temos

928
00:40:22,775 --> 00:40:23,190
escrito ata agora.

929
00:40:23,190 --> 00:40:25,610
Utiliza o loop dobre para obter unha positiva
int do usuario.

930
00:40:25,610 --> 00:40:29,870
Eu, entón, pasar esa int a unha nova función
chamado Sigma, chamando-o, unha vez máis, n.

931
00:40:29,870 --> 00:40:33,100
E eu almacenar o valor de retorno, a resposta
da caixa negra actualmente

932
00:40:33,100 --> 00:40:35,460
coñecido como Sigma, nunha variable
chamada de resposta.

933
00:40:35,460 --> 00:40:36,580
Entón eu imprimir lo.

934
00:40:36,580 --> 00:40:39,090
>> Se agora continuar a historia,
como Sigma aplicado?

935
00:40:39,090 --> 00:40:40,840
Propoño para aplicar o seguinte.

936
00:40:40,840 --> 00:40:43,560
En primeiro lugar, un pouco de verificación de erros
para asegurarse de que o usuario non é

937
00:40:43,560 --> 00:40:46,480
xogar comigo e pasando
algún valor negativo ou 0.

938
00:40:46,480 --> 00:40:49,710
Así que declarar unha variable chamada
En resumo e configuralo para 0.

939
00:40:49,710 --> 00:40:55,910
>> E agora eu comezo a pasar de i é igual a
1 todo o camiño ata e incluíndo m,

940
00:40:55,910 --> 00:41:00,130
porque quero incluír todos os
números de un a m, incluso.

941
00:41:00,130 --> 00:41:04,350
E dentro deste loop for, eu só fago
suma recibe o que é agora, máis

942
00:41:04,350 --> 00:41:08,900
valor de i.

943
00:41:08,900 --> 00:41:10,370
Ademais, o valor de i.

944
00:41:10,370 --> 00:41:14,090
>> Como un aparte, se non vin isto
antes, hai un pouco de azucre sintático

945
00:41:14,090 --> 00:41:14,870
para esta liña.

946
00:41:14,870 --> 00:41:21,120
Podo ter que volver escribir isto como máis iguais i,
só para me salvar algunhas teclas

947
00:41:21,120 --> 00:41:22,570
e mirar un pouco máis frío.

948
00:41:22,570 --> 00:41:23,140
Pero iso é todo.

949
00:41:23,140 --> 00:41:24,660
É funcionalmente o mesmo.

950
00:41:24,660 --> 00:41:26,710
>> Desafortunadamente, este código de
non vai compilar aínda.

951
00:41:26,710 --> 00:41:31,600
Se eu executar o make sigma 0, como son
I será chamado?

952
00:41:31,600 --> 00:41:33,473
O que está indo a non gustar?

953
00:41:33,473 --> 00:41:35,740
>> Audiencia: [inaudível].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Si, eu non declarar
a función encima, non?

955
00:41:37,800 --> 00:41:40,590
C é unha especie de estúpida, só na medida en que
fai o que diga a el para facer, e

956
00:41:40,590 --> 00:41:41,880
ten que facelo nesa orde.

957
00:41:41,880 --> 00:41:45,910
E entón se eu prema Intro aquí, eu vou
recibir un aviso sobre sigma implícita

958
00:41:45,910 --> 00:41:46,860
declaración.

959
00:41:46,860 --> 00:41:48,120
>> Oh, non é un problema.

960
00:41:48,120 --> 00:41:50,370
Eu podo ir ata o cumio, e podo
dicir, todo ben, agarde un minuto.

961
00:41:50,370 --> 00:41:54,240
Sigma é unha función que devolve
un int e espera un

962
00:41:54,240 --> 00:41:56,620
int como entrada, punto e coma.

963
00:41:56,620 --> 00:41:59,550
Ou eu podería poñer toda a función
anterior principal, mais en xeral, eu

964
00:41:59,550 --> 00:42:02,260
Recomendo contra iso, porque é
bo ter sempre inicio na parte superior de xeito

965
00:42:02,260 --> 00:42:06,310
pode mergullo na dereita e sabe o que é un
programa está facendo lendo principal por primeira vez.

966
00:42:06,310 --> 00:42:07,930
>> Entón, agora déixeme limpar a pantalla.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Todo parece check-out.

969
00:42:10,340 --> 00:42:11,970
Déixeme executar sigma 0.

970
00:42:11,970 --> 00:42:12,770
Entre positiva.

971
00:42:12,770 --> 00:42:15,580
Vou darlle o número
3 para mantelo simple.

972
00:42:15,580 --> 00:42:18,710
De xeito que debería darme 3
máis 2 máis 1, entón 6.

973
00:42:18,710 --> 00:42:20,750
Enter, e de feito eu fico 6.

974
00:42:20,750 --> 00:42:21,820
>> Podo facer algo grande -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Así como a tanxente, eu vou facer
algo ridículo como realmente un gran

977
00:42:27,690 --> 00:42:30,375
número, Oh, que realmente funciona -

978
00:42:30,375 --> 00:42:31,600
eh, eu non creo que iso é certo.

979
00:42:31,600 --> 00:42:32,810
Imos ver.

980
00:42:32,810 --> 00:42:34,060
Imos realmente xogar con el.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Isto é un problema.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Que está pasando?

985
00:42:44,970 --> 00:42:46,050
O código non é tan malo así.

986
00:42:46,050 --> 00:42:48,470
Aínda é lineal.

987
00:42:48,470 --> 00:42:50,810
Asubiar é un bo efecto, a pesar de todo.

988
00:42:50,810 --> 00:42:52,060
Que está pasando?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Non estou seguro se oín-lo.

991
00:42:55,620 --> 00:42:57,620
Así, verifica-se - e
é dicir como un aparte.

992
00:42:57,620 --> 00:42:59,400
Isto non é esencial para o
idea de recursão.

993
00:42:59,400 --> 00:43:02,480
Acontece que, por que eu estou tratando de
representan un número tan grande, a maioría

994
00:43:02,480 --> 00:43:06,980
Probablemente está a ser mal interpretado
por C, como un número non positivo,

995
00:43:06,980 --> 00:43:09,980
pero número negativo.

996
00:43:09,980 --> 00:43:12,690
>> Nós non falamos sobre iso, pero
Acontece que hai números negativos

997
00:43:12,690 --> 00:43:14,210
no mundo máis aló
a números positivos.

998
00:43:14,210 --> 00:43:16,290
E os medios polos que se pode
representar un número negativo

999
00:43:16,290 --> 00:43:19,530
esencialmente é, pode utilizar un
bit especial para indicar

1000
00:43:19,530 --> 00:43:20,400
positivo sobre negativo.

1001
00:43:20,400 --> 00:43:22,950
É un pouco máis complexo do que iso,
pero esa é a idea básica.

1002
00:43:22,950 --> 00:43:26,740
>> Entón, por desgraza, se C é confuso unha
deses bits como de feito o que significa,

1003
00:43:26,740 --> 00:43:30,790
Oh, este é un número negativo, o meu lazo
aquí, por exemplo, é, en realidade nunca

1004
00:43:30,790 --> 00:43:31,740
vai rematar.

1005
00:43:31,740 --> 00:43:33,850
Entón, se eu fose realmente a impresión de algo
novo e de novo, fariamos

1006
00:43:33,850 --> 00:43:34,650
ver moita cousa.

1007
00:43:34,650 --> 00:43:36,220
Pero, de novo, iso é cousa do punto.

1008
00:43:36,220 --> 00:43:38,590
Isto é realmente só unha especie de
curiosidade intelectual que nós viremos

1009
00:43:38,590 --> 00:43:39,550
voltar eventualmente.

1010
00:43:39,550 --> 00:43:43,400
Pero, por agora, esta é a correcta
implantación se asumirmos que o

1011
00:43:43,400 --> 00:43:45,970
usuario pode fornecer ints
que se encaixan dentro ints.

1012
00:43:45,970 --> 00:43:49,370
>> Pero eu afirmo que este código, a verdade,
podería facerse moito máis simple.

1013
00:43:49,370 --> 00:43:54,060
O obxectivo en cuestión é ter un número
como m e sumar todos os

1014
00:43:54,060 --> 00:43:59,510
números entre el e 1, ou, inversamente
entre 1 e el, eu afirmo

1015
00:43:59,510 --> 00:44:03,380
que podo pedir esa idea de que funden
especie tiña, que estaba tomando un problema

1016
00:44:03,380 --> 00:44:05,660
deste tamaño e dividíndose o
en algo máis pequeno.

1017
00:44:05,660 --> 00:44:09,875
Quizais nin a metade, pero menor, pero
representativamente o mesmo.

1018
00:44:09,875 --> 00:44:12,130
A mesma idea, pero un problema menor.

1019
00:44:12,130 --> 00:44:15,470
>> Entón, eu estou en realidade - déixeme salve este ficheiro
cun número de versión diferente.

1020
00:44:15,470 --> 00:44:17,670
Imos chamar esta versión
1 no canto de 0.

1021
00:44:17,670 --> 00:44:20,790
E eu afirmo que eu poida realmente
reimplementar esta neste tipo de

1022
00:44:20,790 --> 00:44:22,160
alucinante camiño.

1023
00:44:22,160 --> 00:44:23,710
>> Vou deixar parte dela só.

1024
00:44:23,710 --> 00:44:27,710
Vou dicir se m é menor
que ou mesmo igual a 0 -

1025
00:44:27,710 --> 00:44:29,280
Eu só vou ser un pouco
esta vez máis anal

1026
00:44:29,280 --> 00:44:30,520
coa miña comprobación de erros -

1027
00:44:30,520 --> 00:44:33,190
Eu estou indo a ir adiante e voltar 0.

1028
00:44:33,190 --> 00:44:34,490
Este é arbitraria.

1029
00:44:34,490 --> 00:44:37,500
Estou simplemente decidir se o usuario
dáme un número negativo, eu son

1030
00:44:37,500 --> 00:44:41,490
retornando 0, e eles deben ler
a documentación máis de preto.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
entender o que eu vou facer.

1033
00:44:44,070 --> 00:44:49,260
Máis eu vou volver m plus -

1034
00:44:49,260 --> 00:44:51,010
o que é de sigma m?

1035
00:44:51,010 --> 00:44:56,710
Ben, sigma de m máis m menos 1,
m menos dous, ademais de menos de 3 m.

1036
00:44:56,710 --> 00:44:58,030
Non quero escribir todo isto para fóra.

1037
00:44:58,030 --> 00:44:59,120
Por que non só punto?

1038
00:44:59,120 --> 00:45:05,080
Recursively me chamar con algo
problema menor, punto e coma,

1039
00:45:05,080 --> 00:45:06,840
e chamalo un día?

1040
00:45:06,840 --> 00:45:07,040
>> Non?

1041
00:45:07,040 --> 00:45:10,980
Agora, aquí, tamén, que pode sentir ou preocuparse
que este é un loop infinito que eu son

1042
00:45:10,980 --> 00:45:15,450
inducindo, polo cal estou aplicando
sigma chamando Sigma.

1043
00:45:15,450 --> 00:45:20,342
Pero iso é perfectamente normal, porque eu
pensou en fronte unha agregou que falas?

1044
00:45:20,342 --> 00:45:22,600
>> Audiencia: [inaudível].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23 a 26, que
é o meu caso condición.

1046
00:45:25,430 --> 00:45:28,390
Porque o que é bo sobre o
subtracción aquí, porque eu teño

1047
00:45:28,390 --> 00:45:31,180
entregando sigma problemas menores, menor
problemas menores - non é

1048
00:45:31,180 --> 00:45:31,870
a metade do tamaño.

1049
00:45:31,870 --> 00:45:34,380
É só un pequeno paso máis pequeno,
pero iso é OK.

1050
00:45:34,380 --> 00:45:38,050
Porque, finalmente, imos traballar
noso camiño ata a 1 ou 0.

1051
00:45:38,050 --> 00:45:41,630
E xa que se loita 0, Sigma non é
vai chamar-se máis.

1052
00:45:41,630 --> 00:45:43,590
Devolverá inmediatamente 0.

1053
00:45:43,590 --> 00:45:47,960
>> Así, o efecto, se este tipo de vento
na súa mente, é engadir máis m

1054
00:45:47,960 --> 00:45:52,740
menos 1 m, máis M menos 2, máis M menos
3, ademais de punto, punto, punto, m menos

1055
00:45:52,740 --> 00:45:57,820
m, acabou dándolle 0, eo
efecto é en definitiva, para engadir todos

1056
00:45:57,820 --> 00:45:59,070
esas cousas xuntas.

1057
00:45:59,070 --> 00:46:02,380
Entón, nós non temos, co recursão,
resolveu o problema que

1058
00:46:02,380 --> 00:46:03,470
non podería resolver antes.

1059
00:46:03,470 --> 00:46:06,840
Efectivamente, esta versión de 0, e todo
problema ata a data, foi resoltas

1060
00:46:06,840 --> 00:46:09,980
con só usando loops ou mentres
loops ou construcións semellantes.

1061
00:46:09,980 --> 00:46:13,150
>> Pero recursão, atrévome a dicir, ofrécenos
unha forma diferente de pensar

1062
00:46:13,150 --> 00:46:17,010
problemas, na que se pode tomar un
problema, división lo de algo

1063
00:46:17,010 --> 00:46:22,340
un tanto grande para algo un tanto
máis pequeno, eu afirmo que podemos resolver-lo

1064
00:46:22,340 --> 00:46:26,040
quizais un pouco máis elegante en termos
do deseño, con menos código,

1065
00:46:26,040 --> 00:46:30,980
e quizais mesmo resolver problemas que
ser máis difícil, a medida que vai finalmente

1066
00:46:30,980 --> 00:46:33,280
ver, a solución puramente iterativa.

1067
00:46:33,280 --> 00:46:35,980
>> Pero o suspense que fixen
quero deixar-nos o foi tanto.

1068
00:46:35,980 --> 00:46:40,720
Déixeme ir adiante e abrir
un arquivo dende -

1069
00:46:40,720 --> 00:46:44,300
De feito, déixeme ir e
facelo moi rápido.

1070
00:46:44,300 --> 00:46:46,875
Déixeme ir adiante e propoñer
a continuación.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Entre o código de hoxe é esta imaxe aquí.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Este aquí, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Polo tanto, este é un pequeno programa estúpido que
Eu chicoteado ata que as demandas a facer

1076
00:47:06,260 --> 00:47:06,940
a continuación.

1077
00:47:06,940 --> 00:47:10,140
Na principal, declara por primeira vez un
int chamada xe atribúe a el

1078
00:47:10,140 --> 00:47:11,100
o valor de 1.

1079
00:47:11,100 --> 00:47:13,520
A continuación, el declara un int y e
atribúe o valor 2.

1080
00:47:13,520 --> 00:47:15,310
A continuación, el amosa o que x e y é.

1081
00:47:15,310 --> 00:47:17,781
A continuación, el di, troco, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> A continuación, el di ser chamado dunha función
chamado intercambio, pasando en xe

1083
00:47:21,670 --> 00:47:24,290
y, a idea de que é o que esperamos
x e y volverá

1084
00:47:24,290 --> 00:47:25,620
diferente, o contrario.

1085
00:47:25,620 --> 00:47:27,110
A continuación, el trocou reclamar!

1086
00:47:27,110 --> 00:47:28,420
cun signo de admiración.

1087
00:47:28,420 --> 00:47:30,190
A continuación, el imprime xe y.

1088
00:47:30,190 --> 00:47:33,480
>> Pero resulta que esa mesma
demostración simple abaixo

1089
00:47:33,480 --> 00:47:35,570
aquí é realmente buggy.

1090
00:47:35,570 --> 00:47:38,870
Aínda que eu estou declarando unha temporal
variable e, temporalmente, poñendo un en

1091
00:47:38,870 --> 00:47:42,010
, Entón eu estou reafectação
un valor de b -

1092
00:47:42,010 --> 00:47:45,080
que se sente razoable, porque eu teño
salva unha copia dun de temperatura.

1093
00:47:45,080 --> 00:47:48,410
Entón eu actualizar b a igual
o que estaba na temperatura.

1094
00:47:48,410 --> 00:47:51,610
Este tipo de xogo shell de mover un
en b eb nun empregando esta

1095
00:47:51,610 --> 00:47:54,360
medio-home chamado temperatura sente
perfectamente razoable.

1096
00:47:54,360 --> 00:47:57,270
>> Pero eu afirmo que cando executar este
código, como eu vou facer agora -

1097
00:47:57,270 --> 00:47:59,490
déixeme ir adiante e pegalo aquí.

1098
00:47:59,490 --> 00:48:01,995
Vou chamar esta noswap.c.

1099
00:48:01,995 --> 00:48:05,630
E, como o nome suxire, este non é
Será un programa correcto.

1100
00:48:05,630 --> 00:48:09,460
Fai noswap. / Con intercambio.

1101
00:48:09,460 --> 00:48:12,110
x é 1, y é 2, troco, trocados.

1102
00:48:12,110 --> 00:48:14,220
x é 1, y é 2.

1103
00:48:14,220 --> 00:48:16,920
É fundamentalmente mal, aínda
aínda que isto parece perfectamente

1104
00:48:16,920 --> 00:48:17,730
razoable para min.

1105
00:48:17,730 --> 00:48:21,330
E hai unha razón, pero non estamos
vai revelar a razón aínda.

1106
00:48:21,330 --> 00:48:24,610
>> De momento, a segunda suspense que eu quería
para deixar con iso, un

1107
00:48:24,610 --> 00:48:27,120
anuncio das sortes sobre os códigos de cupón.

1108
00:48:27,120 --> 00:48:31,590
A nosa innovación con días de atraso este ano
provocou un número non-trivial

1109
00:48:31,590 --> 00:48:33,830
de preguntas, o que se
non a nosa intención.

1110
00:48:33,830 --> 00:48:36,590
A intención destes códigos de cupón,
en que, se fai parte do problema

1111
00:48:36,590 --> 00:48:39,850
establecer cedo, obtendo así un día extra,
Foi realmente para axudar vostedes axudan

1112
00:48:39,850 --> 00:48:42,420
se comezar cedo, tipo
de por animar ti.

1113
00:48:42,420 --> 00:48:44,880
Nos axuda a distribuír a carga en toda
o horario de oficina, para que mellor

1114
00:48:44,880 --> 00:48:45,740
é unha especie de gaña-gañou.

1115
00:48:45,740 --> 00:48:48,860
>> Desafortunadamente, creo que as miñas instrucións
non ser, ata a data, moi clara, de xeito

1116
00:48:48,860 --> 00:48:52,230
Volvín esta semana e actualizada
especificación no máis grande, máis ousado texto para

1117
00:48:52,230 --> 00:48:53,600
explicar balas como estas.

1118
00:48:53,600 --> 00:48:56,900
E só para dicir iso máis publicamente, por
estándar, conxuntos de problemas son debidos xoves

1119
00:48:56,900 --> 00:48:58,400
ao mediodía, segundo o programa.

1120
00:48:58,400 --> 00:49:02,030
Se comezar cedo, terminando en parte
o problema de definir ata o mércores ás 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, a parte que se relaciona cun cupón
código, a idea é que pode estenderse

1122
00:49:05,170 --> 00:49:07,710
O prazo para a
P definido ata o venres.

1123
00:49:07,710 --> 00:49:10,890
Ou sexa, pouco fóra unha pequena parte do P
definida en relación ao que normalmente é o

1124
00:49:10,890 --> 00:49:13,200
maior problema, e compra
se un día extra.

1125
00:49:13,200 --> 00:49:15,190
Unha vez máis, queda pensar
o conxunto de problemas, fai que

1126
00:49:15,190 --> 00:49:16,380
o expediente máis cedo.

1127
00:49:16,380 --> 00:49:20,670
Pero o problema aínda é o código de cupón
obrigados, mesmo se non envialo.

1128
00:49:20,670 --> 00:49:23,340
>> Pero o máis convincente é este.

1129
00:49:23,340 --> 00:49:26,520
(Sussurro) E esas persoas deixando
pronto van arrepentir.

1130
00:49:26,520 --> 00:49:28,620
Como son as persoas na terraza.

1131
00:49:28,620 --> 00:49:32,510
Pido desculpas por adiantado para as persoas en
a terraza, por razóns que serán

1132
00:49:32,510 --> 00:49:33,920
claro en só un momento.

1133
00:49:33,920 --> 00:49:37,050
>> Entón, temos a sorte de ter un dos
Ex xefe compañeiros de ensino do CS50 en

1134
00:49:37,050 --> 00:49:39,302
unha empresa chamada dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Teñen moi xenerosamente doou un
código de cupón aquí para iso moito espazo,

1136
00:49:45,500 --> 00:49:48,180
que é a partir do
usuais 2 gigabytes.

1137
00:49:48,180 --> 00:49:51,740
Entón o que eu penso que estaba a facer nesta
nota final é facer un pouco de unha oferta,

1138
00:49:51,740 --> 00:49:55,380
polo cal, en só un momento, imos revelar
o gañador e que ten un cupón

1139
00:49:55,380 --> 00:49:57,980
código que pode, entón, ir ao seu
sitio web, escriba-a, e listo, obter un

1140
00:49:57,980 --> 00:50:01,370
moito máis espazo para a súa Dropbox
aparello e para os seus arquivos persoais.

1141
00:50:01,370 --> 00:50:05,690
>> E en primeiro lugar, que quere participar
neste deseño?

1142
00:50:05,690 --> 00:50:09,630
OK, agora que o fai aínda máis divertido.

1143
00:50:09,630 --> 00:50:14,010
A persoa que recibe este 25 gigabytes
código de cupón - o que está lonxe

1144
00:50:14,010 --> 00:50:16,150
máis atractivo do que o falecido
días de hoxe, se cadra -

1145
00:50:16,150 --> 00:50:20,620
é aquel que está sentado enriba dun
asento do banco baixo a cal existe

1146
00:50:20,620 --> 00:50:21,620
que o código do cupón.

1147
00:50:21,620 --> 00:50:23,480
Agora podes ollar por baixo
seu asento.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [REPRODUCIÓN]

1150
00:50:29,680 --> 00:50:31,620
>> -Un, dous, tres.

1151
00:50:31,620 --> 00:50:35,015
>> [Gritando]

1152
00:50:35,015 --> 00:50:35,985
>> -Vostede gañou un coche!

1153
00:50:35,985 --> 00:50:36,670
Vostede gañou un coche!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Veremos
vostede na Mércores.

1155
00:50:37,970 --> 00:50:38,904
>> -Vostede gañou un coche!

1156
00:50:38,904 --> 00:50:39,371
Vostede gañou un coche!

1157
00:50:39,371 --> 00:50:40,305
Vostede gañou un coche!

1158
00:50:40,305 --> 00:50:41,706
Vostede gañou un coche!

1159
00:50:41,706 --> 00:50:43,107
Vostede gañou un coche!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: persoas Terraza, veñen
aquí abaixo para adiante,

1161
00:50:45,530 --> 00:50:46,866
onde temos extras.

1162
00:50:46,866 --> 00:50:50,282
>> -Todo o mundo ten un coche!

1163
00:50:50,282 --> 00:50:52,234
Todo o mundo queda un coche!

1164
00:50:52,234 --> 00:50:52,722
>> [FIN reprodución de vídeo]

1165
00:50:52,722 --> 00:50:54,590
>> Narrador: Na seguinte CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> COLUMNA 5: Oh meu Deus caramba caramba caramba
caramba caramba caramba caramba caramba caramba -

1167
00:51:00,374 --> 00:51:02,106
>> [XOGOS ukelele]