1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> Palestrante: Todo ben, esta é CS50.

3
00:00:14,910 --> 00:00:19,020
Isto é o fin de semana de tres, e, se
non teña aproveitado xa,

4
00:00:19,020 --> 00:00:21,790
sei que haberá xantar
este venres, como de costume, onde

5
00:00:21,790 --> 00:00:25,430
pode gozar dunha boa conversa
e alimentos en Fire and Ice

6
00:00:25,430 --> 00:00:27,980
con algúns dos CS50 de
funcionarios e compañeiros.

7
00:00:27,980 --> 00:00:30,170
Enfrontamento esta URL aquí.

8
00:00:30,170 --> 00:00:33,420
>> Agora podes lembrar, ou
pode en breve estar familiarizado con,

9
00:00:33,420 --> 00:00:35,970
estas cousas aquí, que
se dan ao final

10
00:00:35,970 --> 00:00:37,850
do semestre para moitas clases.

11
00:00:37,850 --> 00:00:40,870
O chamado exame de libros azuis, en que
escribir as súas respostas para os exames.

12
00:00:40,870 --> 00:00:44,240
Agora eu teño aquí 26, tales
libros azuis, en cada un deles

13
00:00:44,240 --> 00:00:47,580
está escrito un nome, de A a Z. E
en realidade, os nomes son tan sinxelo, A

14
00:00:47,580 --> 00:00:50,490
a Z. E unha das
os obxectivos en man hoxe

15
00:00:50,490 --> 00:00:53,910
será para seguir o que
comezamos o luns, que non é

16
00:00:53,910 --> 00:00:57,830
tanto mirar o código, pero realmente
mirando para ideas e resolución de problemas.

17
00:00:57,830 --> 00:01:00,170
Un dos obxectivos e
promesas deste curso

18
00:01:00,170 --> 00:01:02,985
é ensinalo a pensar máis
coidado, máis metodicamente,

19
00:01:02,985 --> 00:01:05,400
e para resolver os problemas de forma máis eficiente.

20
00:01:05,400 --> 00:01:09,526
E, de feito, podemos facer o que realmente
sen sequera tocar unha liña de código.

21
00:01:09,526 --> 00:01:12,150
Entón, eu teño un par de elefantes
aquí hoxe, laranxa e azul,

22
00:01:12,150 --> 00:01:15,780
se puidésemos obter un voluntario,
quizais de máis atrás do que o habitual.

23
00:01:15,780 --> 00:01:18,070
Que tal alí mesmo, imos alí abaixo.

24
00:01:18,070 --> 00:01:24,180
O obxectivo do que será a
axudar máis administrar este exame aquí.

25
00:01:24,180 --> 00:01:24,935
Cal é o seu nome?

26
00:01:24,935 --> 00:01:25,768
>> Audiencia: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
Palestrante: Mary Beth, imos cara arriba.

28
00:01:27,560 --> 00:01:29,560
Déixeme incorporarse o micrófono aquí para vostede.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Pracer en coñece-lo.

31
00:01:32,880 --> 00:01:34,005
>> Audiencia: Pracer en coñece-lo.

32
00:01:34,005 --> 00:01:36,790
Palestrante: Todo ben, entón eu teño
aquí libros azul da a Z,

33
00:01:36,790 --> 00:01:41,680
e eu vou finxir que
Eu teño un dos alumnos,

34
00:01:41,680 --> 00:01:45,770
e eles están benvida nun tanto aleatoriamente
ao final dun bloque de exame tres horas,

35
00:01:45,770 --> 00:01:49,400
entón eles están acabando nalgúns
orde semi-aleatoria así.

36
00:01:49,400 --> 00:01:54,510
Agora o seu traballo en só un momento que vai
para ser-- este é realmente como se

37
00:01:54,510 --> 00:01:56,820
entregados ao final
a clase, o máis probable.

38
00:01:56,820 --> 00:02:01,120
O seu traballo agora vai ser, moi
simplemente, para clasificar estes libros azuis para nós

39
00:02:01,120 --> 00:02:05,220
de A a Z.

40
00:02:05,220 --> 00:02:08,400
>> Audiencia: Oh, iso é
vai levar para sempre.

41
00:02:08,400 --> 00:02:13,747
>> Orador: E imos ver
como fai iso, sen presión.

42
00:02:13,747 --> 00:02:15,330
Audiencia: Non, ningunha presión nin nada.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> Orador: E para divertirse,
imos poñer un temporizador.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> Audiencia: moi divertido, moi divertido.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> Palestrante: podo soster o micrófono para ti.

49
00:02:38,574 --> 00:02:40,240
Todo ben, nós só dobrou a nosa velocidade.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Entón, nese medio tempo, deixe-me poñer o que hai de
será a pregunta de Mary Beth

52
00:02:49,060 --> 00:02:51,540
é o que se está facendo, como está
vai sobre como solucionar isto?

53
00:02:51,540 --> 00:02:54,040
E, de feito, non pode ter
Xa penso en algo

54
00:02:54,040 --> 00:02:57,440
tan sinxelo como cando escolle
ata 26 libros como este,

55
00:02:57,440 --> 00:02:59,350
que ten un talento natural
ordenando a eles.

56
00:02:59,350 --> 00:03:01,335
Cal é o proceso
que realmente utiliza?

57
00:03:01,335 --> 00:03:03,770
É moi aleatorio só
escoller o primeiro que ve

58
00:03:03,770 --> 00:03:05,250
e poñelas no seu lugar?

59
00:03:05,250 --> 00:03:09,680
Vostede primeiro mover as súas mans en torno
Buscando un logo mirando B?

60
00:03:09,680 --> 00:03:11,722
Vostede dar un ollo a un
par deles mosaico

61
00:03:11,722 --> 00:03:14,680
e só dicir, agarde un minuto, isto
Non é certo, e, a continuación, cambiar a orde?

62
00:03:14,680 --> 00:03:16,960
Xa vimos o luns
que hai unha serie de formas

63
00:03:16,960 --> 00:03:22,140
no que podemos facelo, e
en realidade, como estamos preto do final aquí,

64
00:03:22,140 --> 00:03:26,360
Eu tomaría nota posible
que Mary Beth está facendo.

65
00:03:26,360 --> 00:03:30,040
Temos algunhas pilas parecer, un
maior, tres menores.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> Audiencia: Estou ordenándolles
cando eu atopar dúas cartas

68
00:03:36,415 --> 00:03:39,540
que sei que están xuntos nunha secuencia,
Eu poñer-los xuntos para que eu non

69
00:03:39,540 --> 00:03:42,915
ten que preocuparse en manter
o control de unha liña enteira de libros.

70
00:03:42,915 --> 00:03:45,706
É só, oh, A é o primeiro,
Eu teño esa pila aquí.

71
00:03:45,706 --> 00:03:47,580
Palestrante: Entón, case como
de pezas de puzzle que

72
00:03:47,580 --> 00:03:49,860
ten a forma correcta para
combinar-se un co outro.

73
00:03:49,860 --> 00:03:51,026
Audiencia: Moi bonito, si.

74
00:03:51,026 --> 00:03:55,320
Palestrante: OK, excelente.

75
00:03:55,320 --> 00:03:59,850
E agora cada un destes
pilas é presuntamente ordenado?

76
00:03:59,850 --> 00:04:00,990
>> Audiencia: Yeah.

77
00:04:00,990 --> 00:04:09,900
>> Palestrante: Todo ben, de A a Z. Todos
seguro, parabéns, fixo iso.

78
00:04:09,900 --> 00:04:11,461
Ten a súa elección.

79
00:04:11,461 --> 00:04:11,960
Azul?

80
00:04:11,960 --> 00:04:13,530
Todo ben, grazas por iso.

81
00:04:13,530 --> 00:04:16,679
Entón Mary Beth propúxose
que a súa visión era,

82
00:04:16,679 --> 00:04:19,720
pero o que é outra visión como
pode ir sobre como clasificar esas cousas?

83
00:04:19,720 --> 00:04:21,130
O que tería feito?

84
00:04:21,130 --> 00:04:24,060
A maior cantidade de bater sería
un minuto e 50 segundos ou menos,

85
00:04:24,060 --> 00:04:26,039
máis os que eu esquezo de contar.

86
00:04:26,039 --> 00:04:27,080
O que tería feito?

87
00:04:27,080 --> 00:04:27,579
Si?

88
00:04:27,579 --> 00:04:28,735
Audiencia: Tome a pila.

89
00:04:28,735 --> 00:04:29,776
Comezar desde o principio.

90
00:04:29,776 --> 00:04:32,284
Comprobe os seus papeis.

91
00:04:32,284 --> 00:04:36,586
E se o de arriba é maior
do que, quizais, son,

92
00:04:36,586 --> 00:04:38,980
o fondo é
superior, a continuación, desactiva-los.

93
00:04:38,980 --> 00:04:41,300
>> Palestrante: OK, así que comezar
na parte superior e na parte inferior,

94
00:04:41,300 --> 00:04:43,716
e, a continuación, traballar o seu camiño
dentro dese xeito, cambiando-os?

95
00:04:43,716 --> 00:04:46,580
OK, entón un pouco semellante
en espírito de bubble sort,

96
00:04:46,580 --> 00:04:49,160
pero escoller os extremos
non os pares adxacentes.

97
00:04:49,160 --> 00:04:52,080
Pero o curto que é que hai
certamente unha morea de formas diferentes

98
00:04:52,080 --> 00:04:54,210
poderíamos facelo, e
francamente, creo que tipo de

99
00:04:54,210 --> 00:04:55,700
adoptou algunhas enfoques, non?

100
00:04:55,700 --> 00:05:00,567
Vostede fixo unha especie de catro pilas ordenadas, e
entón efectivamente fundiuse los xuntos.

101
00:05:00,567 --> 00:05:02,650
E iso é, atrévome a dicir, outra
técnica completamente.

102
00:05:02,650 --> 00:05:06,950
Non tratalo como unha gran pila,
vostede divide o problema en catro quadriláteros,

103
00:05:06,950 --> 00:05:09,820
se o desexa, e despois de algunha maneira
fundiuse los ao final.

104
00:05:09,820 --> 00:05:13,410
>> Entón, imos considerar, en definitiva,
De que outra forma poderiamos facelo.

105
00:05:13,410 --> 00:05:15,860
Nós formalizou a noción
de bubble sort última vez,

106
00:05:15,860 --> 00:05:18,780
e recordo bubble sort foi un
algoritmo que visualizamos

107
00:05:18,780 --> 00:05:22,640
con oito dos seus compañeiros aquí enriba,
aparentemente aleatoria clasificados en primeiro lugar.

108
00:05:22,640 --> 00:05:26,110
E nós, entón, decidiu pares, se
dous elementos están fóra de orde,

109
00:05:26,110 --> 00:05:26,950
simplemente trocalos.

110
00:05:26,950 --> 00:05:28,930
Entón, catro e dous son
obviamente, fóra de orde,

111
00:05:28,930 --> 00:05:31,080
entón eses dous compañeiros
cambiar de posición.

112
00:05:31,080 --> 00:05:35,390
E, entón, repetido con catro e seis,
logo, seis e oito, en cada iteración,

113
00:05:35,390 --> 00:05:36,980
movendo á dereita.

114
00:05:36,980 --> 00:05:42,590
>> Así, dado oito persoas, cantos pares
comparacións que fixen durante a camiñada de

115
00:05:42,590 --> 00:05:45,220
esquerda a dereita nun tal iteración?

116
00:05:45,220 --> 00:05:48,410
Cantas comparacións?

117
00:05:48,410 --> 00:05:49,197
Sete, non?

118
00:05:49,197 --> 00:05:51,405
Porque se hai oito
persoas, pero ten o par

119
00:05:51,405 --> 00:05:53,880
eles e continúa movéndose
un salto cara á dereita,

120
00:05:53,880 --> 00:05:56,060
non vai ter oito
comparacións, porque non pode comparar

121
00:05:56,060 --> 00:05:59,226
un elemento contra si, é que sería
basta ser inútil, así que ten sete.

122
00:05:59,226 --> 00:06:01,290
Ou, máis xeralmente, se
temos n persoas, nós

123
00:06:01,290 --> 00:06:04,300
facer N menos 1 comparacións
con bubble sort.

124
00:06:04,300 --> 00:06:08,150
>> Entón, imos considerar agora como bo ou
malo bubble sort realmente era, e intentar

125
00:06:08,150 --> 00:06:13,570
darnos vocabulario con
que a algoritmos crítica como esta,

126
00:06:13,570 --> 00:06:14,430
e logo a nosa.

127
00:06:14,430 --> 00:06:16,970
Entón, o primeiro paso a través
bubble sort, por primeira vez

128
00:06:16,970 --> 00:06:20,909
Eu andei a partir de esquerda a dereita na
escenario, me n menos 1 comparacións tomou.

129
00:06:20,909 --> 00:06:22,950
E iso vai ser o meu
unidade de medida, non?

130
00:06:22,950 --> 00:06:26,170
Eu era unha especie de falar e camiñar,
un tanto rapidamente, un tanto lento,

131
00:06:26,170 --> 00:06:29,300
así contando meu número de segundos
non é particularmente revelador,

132
00:06:29,300 --> 00:06:32,260
pero a conta do número de
operacións que fixen o luns,

133
00:06:32,260 --> 00:06:35,900
comparando dúas persoas, que se sente
como unha agradable unidade de medida.

134
00:06:35,900 --> 00:06:40,980
>> Entón n menos 1 pasos por primeira vez,
Pero entón o que pasou despois diso?

135
00:06:40,980 --> 00:06:46,610
Cal é a única cabeza dunha soa vez
a través dunha lista de outra forma non ordenada?

136
00:06:46,610 --> 00:06:49,840
Que me pode dicir sobre o elemento
que foi todo o camiño ata alí?

137
00:06:49,840 --> 00:06:51,300
Si?

138
00:06:51,300 --> 00:06:52,870
Ese foi o maior elemento, non?

139
00:06:52,870 --> 00:06:55,710
O número oito, aínda que ela
comezou aquí, cada vez que eu

140
00:06:55,710 --> 00:06:57,860
comparar a contra
un veciño, ela mantivo

141
00:06:57,860 --> 00:07:00,480
burbullas-se para a dereita
lado da lista.

142
00:07:00,480 --> 00:07:02,710
E, de feito, que é onde
o algoritmo recibe o seu nome.

143
00:07:02,710 --> 00:07:07,630
>> Agora por esa lóxica, cantas comparacións
eu vou facer o segundo tempo

144
00:07:07,630 --> 00:07:09,800
Fago que pase de esquerda a dereita?

145
00:07:09,800 --> 00:07:10,730
n menos 2, non?

146
00:07:10,730 --> 00:07:14,297
Sería só perdendo meu tempo se eu
manter comparando oito contra alguén

147
00:07:14,297 --> 00:07:16,630
máis porque xa sabemos
ela estaba no lugar seguro.

148
00:07:16,630 --> 00:07:19,760
Entón, iso é un pouco de un
optimización, de xeito que o seguinte paso

149
00:07:19,760 --> 00:07:23,899
será máis n menos dúas etapas,
onde n é o número de persoas.

150
00:07:23,899 --> 00:07:26,940
Agora podes tipo de extrapolar, mesmo
se non é un científico da computación,

151
00:07:26,940 --> 00:07:27,680
como iso termina.

152
00:07:27,680 --> 00:07:31,259
Ao final deste algoritmo, presuntamente
ten só unha comparación esquerda.

153
00:07:31,259 --> 00:07:33,800
Ten que tipo de resolver o
inicio da lista, no caso de dous

154
00:07:33,800 --> 00:07:36,540
e un está fóra de orde
e debe ser un e dous,

155
00:07:36,540 --> 00:07:40,330
de xeito que este encoste na
ademais dunha comparación final.

156
00:07:40,330 --> 00:07:44,500
>> Agora, o punto, punto, punto tipo de ondas é
mans en algúns dos detalles máis suculentas,

157
00:07:44,500 --> 00:07:46,452
pero imos só ir adiante e simplificar.

158
00:07:46,452 --> 00:07:48,660
Se se lembrar de alta
escola, francamente, moitos de vostedes

159
00:07:48,660 --> 00:07:50,340
tiñan libros de matemáticas que tiñan
unha folla de fraude pouco

160
00:07:50,340 --> 00:07:52,550
na portada ou a
tapa traseira que mostre

161
00:07:52,550 --> 00:07:56,400
somatórios que series como
Esta última análise, sumou.

162
00:07:56,400 --> 00:07:59,600
No caso xeral, se ten un
variable como n, e de feito este,

163
00:07:59,600 --> 00:08:01,634
Se mirou para a súa
libro de matemáticas vella escola,

164
00:08:01,634 --> 00:08:04,050
vería que iso realmente
engádese a esta suma aquí,

165
00:08:04,050 --> 00:08:07,970
n veces n menos 1 todo dividido por 2.

166
00:08:07,970 --> 00:08:11,172
Entón, por agora, déixeme só estipular
iso é verdade, entón nun acto de fe,

167
00:08:11,172 --> 00:08:12,880
iso é o que isto resume
ata, e puidemos

168
00:08:12,880 --> 00:08:14,341
probar que, nun caso máis xeral.

169
00:08:14,341 --> 00:08:15,590
Pero agora imos ampliar iso.

170
00:08:15,590 --> 00:08:19,920
Entón, imos multiplicar tanto, o que se
n ao cadrado, menos n, todo dividido por 2.

171
00:08:19,920 --> 00:08:23,200
Isto é realmente n ao cadrado,
dividido por 2, menos n máis de 2,

172
00:08:23,200 --> 00:08:25,010
de xeito que é todo bo e interesante.

173
00:08:25,010 --> 00:08:27,060
Pero o que acontece se nós
agora plugin un valor?

174
00:08:27,060 --> 00:08:29,724
Supoña que eu non tiña oito
persoas, pero din que un millón.

175
00:08:29,724 --> 00:08:31,890
E un millón só porque
que é un número moi grande,

176
00:08:31,890 --> 00:08:34,039
imos chamar iso e ver o que acontece.

177
00:08:34,039 --> 00:08:39,039
Entón, se eu chamar un millón para que a fórmula
Eu estou indo a obter un millón de cadrado,

178
00:08:39,039 --> 00:08:42,868
dividido por 2, menos unha
millóns, dividido por dous.

179
00:08:42,868 --> 00:08:44,159
Agora, o que é que isto vai ser igual?

180
00:08:44,159 --> 00:08:47,354
Así, 500 millóns, menos 500.000.

181
00:08:47,354 --> 00:08:49,270
E se eu realmente facer
que a matemática, isto significa que

182
00:08:49,270 --> 00:08:53,920
que a clasificación dun millón
persoas co tipo de burbulla

183
00:08:53,920 --> 00:09:01,800
me pode levar 499999500000
etapas ou comparacións, ao final,

184
00:09:01,800 --> 00:09:02,900
nós só estamos extrapolando.

185
00:09:02,900 --> 00:09:06,860
>> Que se sente moi lento, pero francamente
medición dunha entrada especial

186
00:09:06,860 --> 00:09:09,160
así, non é tan revelador.

187
00:09:09,160 --> 00:09:14,050
Pero en realidade, ela suxire que como n
convértese en maior e máis grande, este algoritmo

188
00:09:14,050 --> 00:09:16,280
tipo de sente peor e
peor, é que realmente

189
00:09:16,280 --> 00:09:20,450
comezar a sentir a dor do que
exponenciação, que n ao cadrado,

190
00:09:20,450 --> 00:09:21,770
que engade-se moi rápido.

191
00:09:21,770 --> 00:09:25,340
E este detalle non é
perdido nas persoas, en realidade,

192
00:09:25,340 --> 00:09:29,640
hai uns anos, un certo senador que foi
campaña, sentou-se a unha entrevista

193
00:09:29,640 --> 00:09:32,180
con Eric de Google
Schmidt, CEO na época,

194
00:09:32,180 --> 00:09:36,380
e foi desafiado cunha pregunta
así como nós estamos explorando actualmente.

195
00:09:36,380 --> 00:09:38,468
Imos dar un ollo.

196
00:09:38,468 --> 00:09:45,280
>> [REPRODUCIÓN]

197
00:09:45,280 --> 00:09:48,560
>> Senador, está aquí
en Google, e eu gusto

198
00:09:48,560 --> 00:09:53,382
pensar na presidencia
como unha entrevista de emprego.

199
00:09:53,382 --> 00:09:56,434
Agora, é difícil conseguir
un traballo como presidente,

200
00:09:56,434 --> 00:09:58,100
e está pasando os rigores agora.

201
00:09:58,100 --> 00:10:01,860
Tamén é difícil conseguir un emprego en Google.

202
00:10:01,860 --> 00:10:05,490
Temos preguntas, e nós
nosas preguntas candidatos,

203
00:10:05,490 --> 00:10:09,770
e este é de Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
O que-- vostedes pensan que eu son
broma, é aquí mesmo.

205
00:10:14,760 --> 00:10:17,930
Cal é o xeito máis eficiente de
clasificar un millón de enteiros de 32 bits?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> Estou moi, maybe--

209
00:10:25,200 --> 00:10:27,400
>> Non, non, non.

210
00:10:27,400 --> 00:10:30,700
Eu creo que o bubble sort
sería o camiño mal.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> Imos, que lle dixo iso?

213
00:10:38,180 --> 00:10:40,590
Eu non vin ordenador
ciencia no seu fondo.

214
00:10:40,590 --> 00:10:42,130
>> -Temos Nosos espías dentro.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -OK, Imos pedir un diferente
pregunta da entrevista.

217
00:10:48,444 --> 00:10:49,300
>> [FIN REPRODUCIÓN DE VIDEO]

218
00:10:49,300 --> 00:10:52,290
>> Palestrante: Entón, falando
números específicos, aínda que

219
00:10:52,290 --> 00:10:53,890
Non vai ser tan útil.

220
00:10:53,890 --> 00:10:56,810
Non é unha lección de vida que burbulla
tipo, dado un millón de entradas,

221
00:10:56,810 --> 00:10:58,590
pode levar ata 500 millóns etapas.

222
00:10:58,590 --> 00:11:01,120
Realmente non pode xeneralizar
moi eficaz sempre que

223
00:11:01,120 --> 00:11:03,560
e tomar boas decisións de deseño
ao escribir programas.

224
00:11:03,560 --> 00:11:07,070
Entón, imos concentrar en como aínda
podemos simplificar este resultado.

225
00:11:07,070 --> 00:11:11,780
>> Entón, eu teño resaltado en amarelo aquí
o resultado n cadrado dividido por dous,

226
00:11:11,780 --> 00:11:14,330
así un millón cadrado
dividido por dous, e despois

227
00:11:14,330 --> 00:11:16,710
Eu destacou que
a resposta final foi

228
00:11:16,710 --> 00:11:20,180
xa que fóra subtraído n dividido por 2.

229
00:11:20,180 --> 00:11:24,850
E a alegación de que eu vou facer agora é,
quen diaños lle importa se restar off

230
00:11:24,850 --> 00:11:30,060
un pouco máis de idade n 2 cando o primeiro
parte desta fórmula é moi grande?

231
00:11:30,060 --> 00:11:33,910
El domina o outro
prazo, n cadrado dividido por dous

232
00:11:33,910 --> 00:11:37,510
é moito maior, de xeito claro, como
n se fai grande como un millóns,

233
00:11:37,510 --> 00:11:41,450
que hai realmente unha gran diferenza no
Ao final do día entre 500 mil millóns

234
00:11:41,450 --> 00:11:45,730
e 499.999.500.000?

235
00:11:45,730 --> 00:11:46,349
Non é realmente.

236
00:11:46,349 --> 00:11:48,640
E entón o que imos
facer o que os científicos da computación é

237
00:11:48,640 --> 00:11:53,270
ignorar estes termos de orde máis baixa e
ter algo coma isto e realmente

238
00:11:53,270 --> 00:11:56,050
só para simplificar a
termo que vai importar.

239
00:11:56,050 --> 00:12:00,315
Os maiores nosos conxuntos de datos comeza, o máis grande
nosas bases de datos comeza, máis páxinas web

240
00:12:00,315 --> 00:12:02,690
temos que buscar, o máis
amigos ten en Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Como n queda maior, estamos moi
vai se preocupar coa maior

242
00:12:07,340 --> 00:12:11,560
prazo en calquera análise de
noso rendemento algoritmos.

243
00:12:11,560 --> 00:12:16,230
E eu vou dicir, xa sabe o que,
bubble sort é da orde de O grande,

244
00:12:16,230 --> 00:12:18,060
na orde de n ao cadrado.

245
00:12:18,060 --> 00:12:20,090
Non é exactamente n
cadrado, como vimos,

246
00:12:20,090 --> 00:12:22,060
pero quen realmente lle importa
sobre estes termos menores,

247
00:12:22,060 --> 00:12:24,390
e, a verdade, que realmente
importa se dividimos por 2?

248
00:12:24,390 --> 00:12:25,870
Isto é só un factor constante.

249
00:12:25,870 --> 00:12:29,480
E é de 500 millóns contra 250
millóns que realmente de un gran negocio?

250
00:12:29,480 --> 00:12:32,190
Podería só esperar un ano,
deixar meu portátil literalmente

251
00:12:32,190 --> 00:12:34,810
obter dúas veces máis rápido en hardware,
e este tipo de diferenza

252
00:12:34,810 --> 00:12:36,650
só desaparece naturalmente ao longo do tempo.

253
00:12:36,650 --> 00:12:39,300
>> O que nos interesa é
a expresión, a peza

254
00:12:39,300 --> 00:12:42,489
da expresión que vai variar
como a nosa entrada queda maior e máis grande.

255
00:12:42,489 --> 00:12:45,280
E, de feito, no mundo real,
iso é o que está pasando cada vez máis

256
00:12:45,280 --> 00:12:48,330
é as entradas para os nosos problemas e
algoritmos están quedando maiores.

257
00:12:48,330 --> 00:12:53,470
Entón, ó gran será a notación,
a notación asintótica, que acabamos de

258
00:12:53,470 --> 00:12:57,160
usar como científicos da computación para describir
o rendemento, ou o tempo de funcionamento,

259
00:12:57,160 --> 00:12:58,130
dun algoritmo.

260
00:12:58,130 --> 00:13:00,800
Para que poidamos comparar algoritmos
en computadores diferentes escritos

261
00:13:00,800 --> 00:13:04,170
por persoas diferentes, utilizando
algunha métrica fundamentalmente semellantes

262
00:13:04,170 --> 00:13:07,557
como o número de comparacións que se
facendo, ou que o número de swaps

263
00:13:07,557 --> 00:13:08,140
está facendo.

264
00:13:08,140 --> 00:13:11,910
>> O que nós non imos
conta é a cantidade de tempo

265
00:13:11,910 --> 00:13:13,981
que pasa no reloxo
tipicamente na parede.

266
00:13:13,981 --> 00:13:16,230
O que nós non imos preocuparnos
é a cantidade de memoria

267
00:13:16,230 --> 00:13:17,820
está a usar hoxe en
menos importante, aínda que iso sexa

268
00:13:17,820 --> 00:13:19,370
outro recurso que pode medir.

269
00:13:19,370 --> 00:13:23,610
Nós imos tratar basear as nosas análises
en só as operacións básicas, aquelas,

270
00:13:23,610 --> 00:13:25,930
francamente, que se pode ver máis visualmente.

271
00:13:25,930 --> 00:13:30,700
Así, con algo como gran O de n
cadrado, eu afirmo que o de n ao cadrado

272
00:13:30,700 --> 00:13:35,820
é un límite superior sobre o chamado
tempo de funcionamento do bubble sort.

273
00:13:35,820 --> 00:13:38,820
Noutras palabras, se
quería dicir que hai

274
00:13:38,820 --> 00:13:41,370
este límite de cantos
os pasos dun algoritmo pode levar,

275
00:13:41,370 --> 00:13:46,240
vai estar na gran O de n
cadrado, neste caso, un límite superior.

276
00:13:46,240 --> 00:13:49,710
>> E se eu non cambiar o
historia a non ser sobre bubble sort,

277
00:13:49,710 --> 00:13:50,910
pero sobre o límite superior.

278
00:13:50,910 --> 00:13:54,030
Pode pensar en un algoritmo
que nós miramos xa

279
00:13:54,030 --> 00:13:59,530
cuxo límite superior, máximo
medida de tempo ou de operacións,

280
00:13:59,530 --> 00:14:04,300
sería dicir ser limitado
por n, dunha función lineal,

281
00:14:04,300 --> 00:14:07,260
non un cuadrática que é curvo?

282
00:14:07,260 --> 00:14:10,780
¿Que é un algoritmo que
sempre leva máis

283
00:14:10,780 --> 00:14:12,860
do que como n pasos, ou
2n pasos ou etapas 3N?

284
00:14:12,860 --> 00:14:13,360
Si?

285
00:14:13,360 --> 00:14:15,030
>> Audiencia: Buscar o
maior número nunha lista?

286
00:14:15,030 --> 00:14:16,930
>> Palestrante: Perfecto, atopando
o maior número nunha lista.

287
00:14:16,930 --> 00:14:18,940
Se eu estou con unha lista de
persoas, por exemplo,

288
00:14:18,940 --> 00:14:21,440
cada un que está sostendo un número,
o que é o número máximo

289
00:14:21,440 --> 00:14:23,770
de pasos que debe tomar de min,
unha persoa bastante intelixente,

290
00:14:23,770 --> 00:14:27,530
para atopar o maior persoa nesa lista?

291
00:14:27,530 --> 00:14:28,100
n, non?

292
00:14:28,100 --> 00:14:31,320
Porque, no peor caso, en que
quizais o maior valor que?

293
00:14:31,320 --> 00:14:32,700
Certo, todo o camiño ao final.

294
00:14:32,700 --> 00:14:34,575
Así, no peor caso
límite superior, eu podería

295
00:14:34,575 --> 00:14:36,450
ten que ir todo o camiño
ata aquí e ser como,

296
00:14:36,450 --> 00:14:39,170
oh, aquí está o número oito,
ou o que quere que o valor é.

297
00:14:39,170 --> 00:14:41,330
Agora sería simplemente estúpido
se eu continúe indo, non?

298
00:14:41,330 --> 00:14:43,840
Á procura de máis e máis elementos
se o último deles é alí?

299
00:14:43,840 --> 00:14:45,340
Así, por suposto, n é un límite superior.

300
00:14:45,340 --> 00:14:47,420
Eu non teño de tomar
máis etapas do que iso.

301
00:14:47,420 --> 00:14:51,580
>> Entón, o que se no canto propuxen que
existen algoritmos neste mundo que

302
00:14:51,580 --> 00:14:57,750
ter un tempo de execución que se
delimitada pola gran O de rexistro n, log n?

303
00:14:57,750 --> 00:15:00,390
Onde xa vimos isto antes?

304
00:15:00,390 --> 00:15:00,890
Si?

305
00:15:00,890 --> 00:15:03,309
>> Audiencia: O problema de lista telefónica?

306
00:15:03,309 --> 00:15:04,850
Palestrante: Como o problema axenda.

307
00:15:04,850 --> 00:15:07,754
Cal foi a medida de quão
moito tempo ou cantas bágoas de TI

308
00:15:07,754 --> 00:15:10,170
me levou para atopar alguén como
Mike Smith na lista telefónica?

309
00:15:10,170 --> 00:15:13,212
Nós alegou que era log n, e
aínda que descoñecido ou que é

310
00:15:13,212 --> 00:15:15,170
algo nebuloso o que é un
logaritmo ou expoñente foi,

311
00:15:15,170 --> 00:15:17,650
lembre que log n
xeralmente refírese ao proceso,

312
00:15:17,650 --> 00:15:20,790
neste caso, a división
algo en metade, e de novo,

313
00:15:20,790 --> 00:15:25,790
e de novo, e de novo, de tal modo que
fica cada vez máis pequeno, como fai iso.

314
00:15:25,790 --> 00:15:28,470
>> Entón rexistro de n refírese, con certeza,
a exemplo do libro de teléfono,

315
00:15:28,470 --> 00:15:32,662
a procura binaria, en teoría, cando
tivo as portas virtuais no consello,

316
00:15:32,662 --> 00:15:34,370
ou cando se Sean
buscando por algo.

317
00:15:34,370 --> 00:15:37,374
Se usase a procura binaria, rexistro n
sería o límite superior da cantidade de

318
00:15:37,374 --> 00:15:38,040
tempo que leva.

319
00:15:38,040 --> 00:15:44,027
Pero os algoritmos que decorreu en
log n asumiu o detalle chave?

320
00:15:44,027 --> 00:15:45,360
Que a lista resolveuse, non?

321
00:15:45,360 --> 00:15:47,789
O seu algoritmo está mal se
súa entrada non se clasifica,

322
00:15:47,789 --> 00:15:49,830
e aínda así está a usar
algo así como procura binaria

323
00:15:49,830 --> 00:15:51,704
porque pode ir
dereito sobre o elemento

324
00:15:51,704 --> 00:15:53,600
sen entender que é de feito alí.

325
00:15:53,600 --> 00:15:55,600
>> Agora, o que iso pode significar, ó grande dun?

326
00:15:55,600 --> 00:15:59,117
Isto non quere dicir que o seu algoritmo
toma unha e só unha etapa,

327
00:15:59,117 --> 00:16:01,200
significa só que é preciso unha
número constante de pasos.

328
00:16:01,200 --> 00:16:04,060
Quizais sexa un, é posible que
10, é posible que 1000,

329
00:16:04,060 --> 00:16:07,750
pero é independente do
o tamaño do problema.

330
00:16:07,750 --> 00:16:10,850
Non importa o grande é n,
un algoritmo de tempo constante

331
00:16:10,850 --> 00:16:12,747
fai sempre o mesmo número de pasos.

332
00:16:12,747 --> 00:16:15,080
Entón, o que pode ser un algoritmo
falamos ou só

333
00:16:15,080 --> 00:16:20,418
intuitivamente que vén a vostede que
sempre é executado na chamada constante de tempo?

334
00:16:20,418 --> 00:16:20,918
Si?

335
00:16:20,918 --> 00:16:22,001
>> Audiencia: Engadir dous números.

336
00:16:22,001 --> 00:16:25,320
Palestrante: Engadir dous números,
2 máis 2 é igual a 4, feito.

337
00:16:25,320 --> 00:16:27,227
Para que poida funcionar, o que máis?

338
00:16:27,227 --> 00:16:28,560
Que tal mundo máis real, non?

339
00:16:28,560 --> 00:16:30,686
>> Audiencia: Buscar o
primeiro nunha lista.

340
00:16:30,686 --> 00:16:32,810
Palestrante: Atopando-se o primeiro
elemento nunha lista, con certeza.

341
00:16:32,810 --> 00:16:34,540
Fomos realmente falando
sobre matrices xa,

342
00:16:34,540 --> 00:16:36,540
como facelo no
primeiro elemento dunha matriz,

343
00:16:36,540 --> 00:16:40,465
non importa canto tempo a
matriz está código C?

344
00:16:40,465 --> 00:16:43,090
Acaba de usar como o soporte
notación cero, Bam, está alí.

345
00:16:43,090 --> 00:16:46,120
E, de feito matrices, como un aparte,
soporte algo xeralmente coñecido

346
00:16:46,120 --> 00:16:49,240
como de acceso aleatorio, de acceso aleatorio
memoria, porque pode literalmente

347
00:16:49,240 --> 00:16:50,284
ir a calquera só lugar.

348
00:16:50,284 --> 00:16:52,700
Podemos facelo aínda máis simple
podemos retroceder a semana de cero

349
00:16:52,700 --> 00:16:53,900
cando fixemos cero.

350
00:16:53,900 --> 00:16:59,707
Canto tempo tardou para o
dicir bloque en risco a realizar?

351
00:16:59,707 --> 00:17:00,790
Só tempo constante, non?

352
00:17:00,790 --> 00:17:03,960
Diga algo, dicir
algo, non importa

353
00:17:03,960 --> 00:17:07,359
como grandes arañazos mundo é, sempre é
terá a mesma cantidade de tempo

354
00:17:07,359 --> 00:17:08,490
simplemente dicir algo.

355
00:17:08,490 --> 00:17:11,089
>> Entón é tempo constante,
pero o que é a outra cara?

356
00:17:11,089 --> 00:17:13,030
Se isto fose superior
límites, o que se quere

357
00:17:13,030 --> 00:17:17,089
para describir os límites inferiores
dos nosos algoritmos de tempo de execución?

358
00:17:17,089 --> 00:17:19,852
Case un mellor caso
potencialmente, se quixeren,

359
00:17:19,852 --> 00:17:23,060
aínda que eses termos podería aplicarse a mellor
casos peores casos, casos de media máis

360
00:17:23,060 --> 00:17:26,359
xeralmente, pero imos centrar
en límites inferiores de forma máis xeral.

361
00:17:26,359 --> 00:17:31,920
¿Que é un algoritmo que ten
un límite inferior de n pasos,

362
00:17:31,920 --> 00:17:33,350
ou 2n pasos ou etapas 3N?

363
00:17:33,350 --> 00:17:36,241
Algúns factor de n pasos,
Cal é o límite inferior.

364
00:17:36,241 --> 00:17:36,740
Si?

365
00:17:36,740 --> 00:17:37,910
>> Audiencia: Bubble sort?

366
00:17:37,910 --> 00:17:41,610
>> Palestrante: Bubble sort leva
vostede minimamente n pasos, por que?

367
00:17:41,610 --> 00:17:42,279
Por que?

368
00:17:42,279 --> 00:17:45,320
Por que que comezan a chegar ata ti
intuitivamente, mesmo se isto acontecer non só

369
00:17:45,320 --> 00:17:46,530
aínda?

370
00:17:46,530 --> 00:17:47,030
Si?

371
00:17:47,030 --> 00:17:47,990
>> Audiencia: [inaudível].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
Palestrante: Exactamente.

374
00:17:52,360 --> 00:17:55,810
No mellor escenario posible de
bubble sort, e unha morea de algoritmos,

375
00:17:55,810 --> 00:17:58,769
se eu entregar-lle oito persoas
que xa son clasificadas,

376
00:17:58,769 --> 00:18:00,560
sería insensato
para ti, o algoritmo,

377
00:18:00,560 --> 00:18:02,202
para ir e volver
máis dunha vez, non?

378
00:18:02,202 --> 00:18:04,285
Porque así que
camiñar a través da lista de novo,

379
00:18:04,285 --> 00:18:08,090
ten que entender, oh, eu non fixen ningún
swaps, esta lista é ordenada, saia.

380
00:18:08,090 --> 00:18:09,700
Pero iso vai levar vostede n pasos.

381
00:18:09,700 --> 00:18:12,033
>> E, inversamente, o que é outra
forma de pensar sobre iso?

382
00:18:12,033 --> 00:18:15,240
Bubble sort é un omega,
por así dicir, de n,

383
00:18:15,240 --> 00:18:19,050
porque se ollar para
menos de n elementos, o que

384
00:18:19,050 --> 00:18:23,009
é a cuestión fundamental non?

385
00:18:23,009 --> 00:18:24,550
Non sabe se está resolto, certo.

386
00:18:24,550 --> 00:18:26,800
Nós os humanos poidan mirar oito
persoas e ser como, oh, é clasificado,

387
00:18:26,800 --> 00:18:28,430
que non me n pasos tomar, pero fixo.

388
00:18:28,430 --> 00:18:30,810
Os seus ollos, aínda que tipo
de ter un gran campo de visión,

389
00:18:30,810 --> 00:18:33,184
mirou para oito elementos,
mirou para oito persoas,

390
00:18:33,184 --> 00:18:34,610
iso é oito pasos de forma eficaz.

391
00:18:34,610 --> 00:18:38,612
E só se eu andase polo todo
lista que eu entendo, si, clasificada.

392
00:18:38,612 --> 00:18:41,320
Se eu deixar no medio do camiño a pensar: todo
dereito, é ben resolto, ata agora,

393
00:18:41,320 --> 00:18:42,520
cales son as posibilidades que non é ordenado?

394
00:18:42,520 --> 00:18:44,186
Iso non os dun algoritmo será correcta.

395
00:18:44,186 --> 00:18:46,250
Pode ser máis rápido, pero incorrecto.

396
00:18:46,250 --> 00:18:48,500
>> Entón, agora temos unha forma de
describindo un límite inferior,

397
00:18:48,500 --> 00:18:49,710
E canto tempo constante?

398
00:18:49,710 --> 00:18:54,565
¿Que é un algoritmo que ten unha menor
grazas no seu tempo de execución de un?

399
00:18:54,565 --> 00:18:58,350
1 paso, dous pasos, 10 pasos, pero
constante, independente de n,

400
00:18:58,350 --> 00:18:59,310
o tamaño da entrada?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Si, na parte de atrás.

403
00:19:04,600 --> 00:19:05,309
>> Audiencia: printf?

404
00:19:05,309 --> 00:19:06,183
Palestrante: ¿Que é iso?

405
00:19:06,183 --> 00:19:07,184
Audiencia: printf?

406
00:19:07,184 --> 00:19:07,850
COLUMNA: printf.

407
00:19:07,850 --> 00:19:08,400
OK, con certeza.

408
00:19:08,400 --> 00:19:10,720
Entón, é preciso un número fixo de pasos.

409
00:19:10,720 --> 00:19:13,170
E eu debería agora-- agora que
estamos a falar de código C

410
00:19:13,170 --> 00:19:16,040
e non rabuñar, algo
como din, con printf,

411
00:19:16,040 --> 00:19:17,710
debemos comezar a ter coidado.

412
00:19:17,710 --> 00:19:21,090
Porque printf leva
entrada, é unha cadea,

413
00:19:21,090 --> 00:19:23,220
e as cordas que tecnicamente ten lonxitude.

414
00:19:23,220 --> 00:19:25,530
Entón, se nós agora quere escoller
en ti, se non lle importa,

415
00:19:25,530 --> 00:19:29,430
tecnicamente poderiamos argumentar que printf
toma unha entrada de lonxitude variable,

416
00:19:29,430 --> 00:19:32,270
e, por suposto, isto pode levar máis
tempo para imprimir unha secuencia de tanto tempo,

417
00:19:32,270 --> 00:19:33,560
que este tempo.

418
00:19:33,560 --> 00:19:36,570
>> Entón, o que se consideramos só o
clasificación e investigación exemplos?

419
00:19:36,570 --> 00:19:40,450
E sobre Mike Smith no teléfono
libro, ou busca binaria máis xeral?

420
00:19:40,450 --> 00:19:42,220
No mellor dos casos, o que pode ocorrer?

421
00:19:42,220 --> 00:19:45,577
Abro o libro de teléfono e, Bam,
hai número de Mike Smith.

422
00:19:45,577 --> 00:19:46,660
Podo chamalo de inmediato.

423
00:19:46,660 --> 00:19:49,390
>> Deu un paso, quizais dúas etapas,
pero un número constante de etapas

424
00:19:49,390 --> 00:19:50,230
se eu teño sorte.

425
00:19:50,230 --> 00:19:52,570
E, francamente, nós vimos en
Luns seu compañeiro de clase

426
00:19:52,570 --> 00:19:54,710
estar moi sorte dúas veces seguidas.

427
00:19:54,710 --> 00:19:57,050
E iso era realmente constante
vez en límites inferiores

428
00:19:57,050 --> 00:20:01,280
no algoritmo en cuestión para atopar
o número 50 atrás daqueles pechado

429
00:20:01,280 --> 00:20:01,830
portas.

430
00:20:01,830 --> 00:20:06,400
>> Agora, como un aparte, se descubrir
Que tanto grande, o límite superior

431
00:20:06,400 --> 00:20:09,310
e omega, o límite inferior,
son un na mesma, que

432
00:20:09,310 --> 00:20:11,830
é a mesma fórmula en
parénteses, tamén se pode

433
00:20:11,830 --> 00:20:15,170
dicir, só que ser extravagante,
que algo está theta

434
00:20:15,170 --> 00:20:18,270
de n ou teta dalgún outro valor.

435
00:20:18,270 --> 00:20:20,661
Isto significa só que cando gran
O e omega son os mesmos.

436
00:20:20,661 --> 00:20:21,910
Agora o que pasa coa selección tipo?

437
00:20:21,910 --> 00:20:23,400
Imos usar este novo vocabulario.

438
00:20:23,400 --> 00:20:27,407
Na selección de clasificación, o que estabamos
facendo de novo, e de novo, e de novo?

439
00:20:27,407 --> 00:20:29,990
Eu estaba indo cara atrás e cara adiante a través de
da lista, buscando quen?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
O menor número.

442
00:20:34,730 --> 00:20:37,560
>> Así como moitos pasos, como
moitas comparacións fixo I

443
00:20:37,560 --> 00:20:43,250
ten que facer, a fin de descubrir quen
menor elemento na lista foi?

444
00:20:43,250 --> 00:20:44,437
n menos un, non?

445
00:20:44,437 --> 00:20:47,770
Porque se eu comezar co que eu son
dada e comezar a comparar a el ou ela,

446
00:20:47,770 --> 00:20:49,519
a continuación, el ou ela, el
ou ela, el ou ela, eu

447
00:20:49,519 --> 00:20:52,010
só pode vincular elementos
xuntos n menos 1 veces.

448
00:20:52,010 --> 00:20:55,630
Así, a selección leva especie semellante
n menos pasos 1 a primeira vez.

449
00:20:55,630 --> 00:20:59,540
>> Cantos pasos me levar a
atopar o segundo menor elemento?

450
00:20:59,540 --> 00:21:02,920
n menos 2, porque eu estou sendo idiota
se eu continuar mirando para as mesmas persoas

451
00:21:02,920 --> 00:21:06,280
de novo se eu xa o elixiu
ou ela e poñer-los no seu lugar.

452
00:21:06,280 --> 00:21:09,270
E o terceiro paso, n
menos 3, entón n menos 4.

453
00:21:09,270 --> 00:21:11,020
Vimos este estándar
antes, e de feito

454
00:21:11,020 --> 00:21:13,460
selección especie semellante
ten un límite superior

455
00:21:13,460 --> 00:21:16,210
de n ao cadrado, se facemos o que suma.

456
00:21:16,210 --> 00:21:19,790
Cal é o seu límite inferior, a selección tipo?

457
00:21:19,790 --> 00:21:25,350
Como mínimo, o tempo de verificación debe
tipo tomar, como definido o luns?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Propoñer dúas opcións.

460
00:21:30,490 --> 00:21:32,360
Quizais sexa n, como antes.

461
00:21:32,360 --> 00:21:35,040
Quizais sexa n ao cadrado, como
é agora como o límite superior.

462
00:21:35,040 --> 00:21:35,874
>> Audiencia: n ao cadrado.

463
00:21:35,874 --> 00:21:36,664
Palestrante: n ao cadrado.

464
00:21:36,664 --> 00:21:37,368
Por que?

465
00:21:37,368 --> 00:21:40,060
>> Audiencia: Porque ten
definir [inaudível].

466
00:21:40,060 --> 00:21:41,510
>> Palestrante: Exactamente.

467
00:21:41,510 --> 00:21:45,077
Polo menos mentres eu definido selección especie
era moi inxenuo, siga indo,

468
00:21:45,077 --> 00:21:46,160
atopar o menor elemento.

469
00:21:46,160 --> 00:21:47,770
Vaia unha vez máis, atopar o menor elemento.

470
00:21:47,770 --> 00:21:49,490
Vaia unha vez máis, atopar o menor elemento.

471
00:21:49,490 --> 00:21:51,700
Non hai ningún tipo de
optimización alí que

472
00:21:51,700 --> 00:21:54,350
pode deixar-me abortar despois
só n ou máis etapas.

473
00:21:54,350 --> 00:21:57,080
Así, de feito, a selección
tipo, omega de n ao cadrado.

474
00:21:57,080 --> 00:22:00,667
>> Que tal tipo de inserción, onde tirei
que me foi dado, e entón eu estatelou lo

475
00:22:00,667 --> 00:22:01,750
ou ela no lugar seguro?

476
00:22:01,750 --> 00:22:04,958
Entón eu continúe a segunda persoa,
estatelou lle no lugar seguro.

477
00:22:04,958 --> 00:22:07,910
Entón, a próxima persoa, se estatelou
el ou ela no lugar seguro.

478
00:22:07,910 --> 00:22:10,537
Teña en conta que isto é moi
lineal, por así dicir.

479
00:22:10,537 --> 00:22:12,620
Eu son unha liña recta, eu son
non indo e volvendo,

480
00:22:12,620 --> 00:22:16,080
Nunca mirar atrás, realmente, pero
o que está pasando cando inserir-lo

481
00:22:16,080 --> 00:22:20,302
ou ela ao comezo do
lista como fixemos o luns?

482
00:22:20,302 --> 00:22:21,010
O que está pasando?

483
00:22:21,010 --> 00:22:21,510
Si?

484
00:22:21,510 --> 00:22:23,122
Audiencia: [inaudível].

485
00:22:23,122 --> 00:22:24,830
Palestrante: Si, iso
foi a captura, non?

486
00:22:24,830 --> 00:22:26,746
Pode lembrar de
seus compañeiros de clase, se eles

487
00:22:26,746 --> 00:22:29,670
estaban facendo calquera movemento con
seus pés, que era unha operación.

488
00:22:29,670 --> 00:22:33,610
Polo tanto, se había tres persoas aquí e
a nova persoa pertencía camiño ata alí,

489
00:22:33,610 --> 00:22:37,360
nunha longa fase como esta, con certeza, el
ou podería só ir ata o final.

490
00:22:37,360 --> 00:22:40,074
Pero se estamos a pensar nun
ordenador e unha matriz de memoria,

491
00:22:40,074 --> 00:22:41,990
esas persoas van
ter para barallar máis

492
00:22:41,990 --> 00:22:43,260
para dar espazo para esa persoa.

493
00:22:43,260 --> 00:22:46,930
E así que n menos un shufflings,
n menos 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
menos 3 shufflings é só unha especie de
pasando detrás de min, non na miña fronte

495
00:22:50,660 --> 00:22:52,710
como antes, nalgún sentido.

499
00:22:52,557 --> 00:22:54,640
Agora, como unha banda, e como
podes ver en liña

500
00:22:54,640 --> 00:22:57,699
se comezar a bisbilhotar sobre
tipos, hai tantos diferentes

501
00:22:57,699 --> 00:22:59,490
aí, algúns deles
mellor que os outros.

502
00:22:59,490 --> 00:23:02,200
De feito, é unha bogosort
ese é o tipo de diversión para ollar cara arriba.

503
00:23:02,200 --> 00:23:06,650
Bogosort leva un conxunto de
números ou dicir un baralla de cartas,

504
00:23:06,650 --> 00:23:09,870
embaralha-los aleatoriamente, e
comproba se están ordenados.

505
00:23:09,870 --> 00:23:12,130
E se non, fai iso de novo.

506
00:23:12,130 --> 00:23:14,140
E se non, fai iso de novo.

507
00:23:14,140 --> 00:23:15,440
Se non, fai iso de novo.

508
00:23:15,440 --> 00:23:17,060
Incrible estúpido.

509
00:23:17,060 --> 00:23:19,520
>> E, de feito, se ler
como o artigo da Wikipedia,

510
00:23:19,520 --> 00:23:21,200
seu apelido é medio parvo.

511
00:23:21,200 --> 00:23:25,180
Será finalmente traballar,
espero que, co tempo,

512
00:23:25,180 --> 00:23:28,240
pero que a cantidade de tempo
pode levar algún tempo.

513
00:23:28,240 --> 00:23:31,650
Entón, se eu puidese, imos acelerar as cousas
-se co exemplo de Mary Beth anteriormente,

514
00:23:31,650 --> 00:23:35,150
por máis algúns elementos,
pero dous procesadores.

515
00:23:35,150 --> 00:23:37,100
Dúas persoas, se
non me importaría de me xuntar.

516
00:23:37,100 --> 00:23:40,972
Como preto de 1 por aquí, e
imos vai-- ninguén alí?

517
00:23:40,972 --> 00:23:41,722
Ninguén alí?

518
00:23:41,722 --> 00:23:42,221
Está ben.

519
00:23:42,221 --> 00:23:44,190
Vostede co negro
camisa, si, imos alí abaixo.

520
00:23:44,190 --> 00:23:45,000
Todo ben, cal é o seu nome?

521
00:23:45,000 --> 00:23:45,720
>> Audiencia: Peter.

522
00:23:45,720 --> 00:23:46,100
>> Palestrante: ¿Que é iso?

523
00:23:46,100 --> 00:23:46,766
>> Audiencia: Peter.

524
00:23:46,766 --> 00:23:49,450
Palestrante: Peter, David, pracer de coñece-lo.

525
00:23:49,450 --> 00:23:53,670
Todo ben, temos Peter aquí, se
quere vir á mesa por aquí.

526
00:23:53,670 --> 00:23:54,550
E cal o seu nome?

527
00:23:54,550 --> 00:23:55,216
>> Audiencia: Elena.

528
00:23:55,216 --> 00:23:55,970
Palestrante: Elena.

529
00:23:55,970 --> 00:23:57,030
OK, pracer de coñece-lo.

530
00:23:57,030 --> 00:23:58,060
Elena atender Peter.

531
00:23:58,060 --> 00:23:59,170
Peter, Elena.

532
00:23:59,170 --> 00:24:02,290
E necesitamos Andrew
aquí tamén, por favor.

533
00:24:02,290 --> 00:24:06,107
E o reto vai
ser para ordenar un baralla de cartas.

534
00:24:06,107 --> 00:24:08,190
E se non familiar, deck
de tarxetas debe finalmente

535
00:24:08,190 --> 00:24:11,064
ser clasificado un pouco algo como
este, onde faremos os clubs, a continuación,

536
00:24:11,064 --> 00:24:13,660
as espadas, a continuación, os corazóns e
diamantes, de ace como un,

537
00:24:13,660 --> 00:24:15,570
todo o camiño ata o rei.

538
00:24:15,570 --> 00:24:20,890
>> As cartas que eu estou indo darlle
van ser 52 en cantidade.

539
00:24:20,890 --> 00:24:23,160
Imos semellante
xa que, en só un momento.

540
00:24:23,160 --> 00:24:26,410
Imos xogar Andrew
na pantalla aquí,

541
00:24:26,410 --> 00:24:28,170
, Co fin de ver como fai iso.

542
00:24:28,170 --> 00:24:31,070
E para que todo isto
é aínda máis visible,

543
00:24:31,070 --> 00:24:33,490
Estes son as tarxetas que recibín na Amazonia.

544
00:24:33,490 --> 00:24:42,861
Entón, eles xa están aleatoriamente
clasificado, e nós estamos indo ao tempo que.

545
00:24:42,861 --> 00:24:44,610
E nós imos
mantelo real esta vez,

546
00:24:44,610 --> 00:24:47,820
entón imos tentar preme-lo
porque se non isto vai ser entediante

547
00:24:47,820 --> 00:24:48,460
rapidamente.

548
00:24:48,460 --> 00:24:53,860
Se puidese proceder para clasificar 52
elementos entre si a través de algúns medios, agora.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> E unha vez máis, como podemos ver estes
caras fan o que, ao final

551
00:25:07,180 --> 00:25:10,200
producirá un evidente
resultado, pense realmente

552
00:25:10,200 --> 00:25:12,962
como están a facer iso cada,
como pode describilo.

553
00:25:12,962 --> 00:25:15,045
Porque unha vez máis, estas son
todos os procesos, algoritmos

554
00:25:15,045 --> 00:25:17,090
que nós tomamos para concedida como un ser humano.

555
00:25:17,090 --> 00:25:22,349
Pero xa debería ter tido por moito tempo
intuición, moito antes de ti mesmo

556
00:25:22,349 --> 00:25:24,390
pensou en tomar un
ciencia da computación clase ti

557
00:25:24,390 --> 00:25:27,223
podería ter a intuición con
que para resolver problemas como este.

558
00:25:27,223 --> 00:25:29,560
Pero unha vez que recoñece
os patróns e comezar

559
00:25:29,560 --> 00:25:32,407
para formalizar as medidas coas que
está resolvendo estes problemas,

560
00:25:32,407 --> 00:25:35,490
vai descubrir que pode resolver moi
máis interesante e máis complexo

561
00:25:35,490 --> 00:25:39,190
problemas rapidamente.

562
00:25:39,190 --> 00:25:42,351
Entón, alguén do público, o que é
polo menos un elemento do algoritmo

563
00:25:42,351 --> 00:25:43,350
que están a usar aquí?

564
00:25:43,350 --> 00:25:44,275
>> Audiencia: [inaudível]

565
00:25:44,275 --> 00:25:45,150
Palestrante: ¿Que é iso?

566
00:25:45,150 --> 00:25:47,062
Audiencia: por exemplo.

567
00:25:47,062 --> 00:25:47,770
Palestrante: por exemplo.

568
00:25:47,770 --> 00:25:50,630
Entón, primeiro se aglomeram
todos os diamantes xuntos

569
00:25:50,630 --> 00:25:52,560
Parece que todo
corazóns xuntos parecer,

570
00:25:52,560 --> 00:25:56,520
e así por diante, sen respecto
para os números sobre as tarxetas.

571
00:25:56,520 --> 00:26:00,900
E agora aparecen, por exemplo,
sendo os por número.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Moi bo.

574
00:26:08,910 --> 00:26:12,370
>> Todo ben, entón o que vai
ser o paso final, entón aquí?

575
00:26:12,370 --> 00:26:16,950
Unha vez que temos catro naipes clasificadas, o que
facer o que necesitamos facer para as catro pilas

576
00:26:16,950 --> 00:26:20,059
, A fin de alcanzar un
clasificadas convén, pura e simplemente?

577
00:26:20,059 --> 00:26:21,350
Entón, necesitamos mesturar-los de novo.

578
00:26:21,350 --> 00:26:25,160
>> Polo tanto, hai unha idea interesante que
de novo, atrévome a dicir, é moi intuitivo mesmo

579
00:26:25,160 --> 00:26:28,140
se nunca podería esbofeteado
este tipo de etiqueta nel.

580
00:26:28,140 --> 00:26:31,900
Esta noción fundamental de división
o problema non en metade deste tempo,

581
00:26:31,900 --> 00:26:33,410
pero, polo menos, en catro anacos.

582
00:26:33,410 --> 00:26:36,810
Resolvendo practicamente
problemas fundamentalmente idénticos

583
00:26:36,810 --> 00:26:40,480
illadamente uns dos outros,
e entón fundir os resultados.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
E, excelente, feito.

586
00:26:50,140 --> 00:26:52,140
Todo ben, unha gran rolda
de aplausos, se puidésemos.

587
00:26:52,140 --> 00:26:56,480
>> [Aplausos]

588
00:26:56,480 --> 00:26:59,740
>> Palestrante: Eu non teño idea o que vai
ver con iso, pero aquí vai.

589
00:26:59,740 --> 00:27:01,690
Moitas grazas.

590
00:27:01,690 --> 00:27:04,660
Entón imos ver, dous minutos
e oito segundos;

591
00:27:04,660 --> 00:27:07,490
se desexa desafiar os seus amigos.

592
00:27:07,490 --> 00:27:12,160
O que entón vai
ser un sacar este

593
00:27:12,160 --> 00:27:13,830
que podemos aproveitar de forma máis xeral?

594
00:27:13,830 --> 00:27:16,080
Ben, creo que volta a
este conxunto de números,

595
00:27:16,080 --> 00:27:19,060
e creo que volta agora a algúns dos
pseudocódigo escribimos no pasado,

596
00:27:19,060 --> 00:27:22,080
e este foi o pseudocódigo para
resolver o problema da lista telefónica.

597
00:27:22,080 --> 00:27:25,150
Nestas circunstancias, en pseudocódigo I
enumerou unha forma máis metódica

598
00:27:25,150 --> 00:27:28,400
de describir como eu fixen un moi intuitiva
algoritmo humano de dividir o teléfono

599
00:27:28,400 --> 00:27:31,650
libro pola metade, repetir, repetir, repetir,
ata eu atopar alguén como Mike Smith,

600
00:27:31,650 --> 00:27:33,790
se é de feito no libro de teléfono.

601
00:27:33,790 --> 00:27:37,610
>> Pero eu medio que usei o que eu vou chamar
unha visión moi iterativo aquí,

602
00:27:37,610 --> 00:27:42,160
en particular aviso liña 8 e liña 11.

603
00:27:42,160 --> 00:27:46,750
Estas son evidencias dunha iterativo
visión, unha visión looping,

604
00:27:46,750 --> 00:27:49,040
porque é exactamente
o comportamento que inducen.

605
00:27:49,040 --> 00:27:52,910
Estas liñas tanto dicir ir
liña de tres, e pode tipo de

606
00:27:52,910 --> 00:27:55,140
pensar que, na súa
ollo da mente como un loop.

607
00:27:55,140 --> 00:27:59,080
Está dicindo a vostede para volverse para o paso
tres e repetir, de novo, e de novo,

608
00:27:59,080 --> 00:28:00,010
e de novo.

609
00:28:00,010 --> 00:28:04,410
>> Pero o que se aproveitar unha idea clave
aquí que non por última vez,

610
00:28:04,410 --> 00:28:10,280
e simplificar a liña 8 e
liña 11 e os seus veciños

611
00:28:10,280 --> 00:28:12,840
como só iso, en amarelo.

612
00:28:12,840 --> 00:28:16,480
Non é, fundamentalmente, acurtando
pseudocódigo moito,

613
00:28:16,480 --> 00:28:20,530
pero está cambiando fundamentalmente
a natureza do meu algoritmo.

614
00:28:20,530 --> 00:28:24,220
O que eu digo agora
no paso 7, no paso 10,

615
00:28:24,220 --> 00:28:29,140
é a procura de Mike
do mesmo xeito exacta,

616
00:28:29,140 --> 00:28:31,580
pero só na parte esquerda
metade ou metade dereita.

617
00:28:31,580 --> 00:28:33,420
>> Así, noutras palabras, se
Eu comezar a partir dunha etapa,

618
00:28:33,420 --> 00:28:36,150
incorporarse libro de teléfono, aberto a través
do libro de teléfono, ollar os nomes,

619
00:28:36,150 --> 00:28:39,010
Se Smith está entre
O nome de, chamar Mike, o máis

620
00:28:39,010 --> 00:28:44,340
Se Smith é anterior no libro, paso sete
buscar Mike na metade esquerda do libro.

621
00:28:44,340 --> 00:28:47,130
Pero este tipo de sente como
iso está me deixando colgado, non?

622
00:28:47,130 --> 00:28:49,240
En amarelo, é unha
instrución, pero como fago

623
00:28:49,240 --> 00:28:51,870
buscar o Mike no esquerdo
metade do libro de teléfono?

624
00:28:51,870 --> 00:28:54,210
Onde é que eu teño unha
algoritmo co que eu

625
00:28:54,210 --> 00:28:57,100
Pode procurar por alguén como Mike Smith?

626
00:28:57,100 --> 00:28:58,980
Ben, iso está nos mirando na cara.

627
00:28:58,980 --> 00:29:03,090
Podo literalmente usar exactamente o mesmo
programa vai efectivamente ata o cumio

628
00:29:03,090 --> 00:29:06,490
de novo e re-execución
as mesmas liñas de código.

629
00:29:06,490 --> 00:29:10,610
>> Así, aínda que este debe sentir-se
como un pouco de unha definición cíclico

630
00:29:10,610 --> 00:29:13,480
onde está a responder a alguén é
Pregunta por só unha especie de preguntar

631
00:29:13,480 --> 00:29:15,990
a mesma pregunta de novo,
por que, por que, por que?

632
00:29:15,990 --> 00:29:21,580
A realidade é porque temos codificado
un par de liñas especiais, rango 4,

633
00:29:21,580 --> 00:29:25,320
que é un caso, e paso 12, que
é efectivamente outro ramo,

634
00:29:25,320 --> 00:29:30,120
porque temos esas medidas paliativas,
este algoritmo pode rematar se

635
00:29:30,120 --> 00:29:32,050
atopar Mike, ou se non o facemos.

636
00:29:32,050 --> 00:29:36,810
Pero no paso 7 e 10 agora temos
o que imos chamar de un algoritmo recursivo.

637
00:29:36,810 --> 00:29:40,420
E recursão é de feito unha idea poderosa
iso é un pouco de mente dobra en principio,

638
00:29:40,420 --> 00:29:42,500
que agora podemos aplicar a seguinte.

639
00:29:42,500 --> 00:29:46,600
>> Merge sort será o último tipo que
miramos, polo menos na clase formalmente.

640
00:29:46,600 --> 00:29:50,040
E é fundamentalmente diferente
daqueles tres últimos, e, por suposto,

641
00:29:50,040 --> 00:29:52,140
catro últimos se inclúen bogosort.

642
00:29:52,140 --> 00:29:54,810
Aquí está o pseudocódigo para merge sort.

643
00:29:54,810 --> 00:30:00,170
Cando a entrada de n elementos, entón dado
unha matriz de tamaño n, se n é inferior a 2,

644
00:30:00,170 --> 00:30:01,040
volver.

645
00:30:01,040 --> 00:30:03,610
Entón, por que eu teño que
verificación de sanidade en primeiro lugar?

646
00:30:03,610 --> 00:30:09,477
Cal é a implicación se eu entregar-lle
unha matriz cuxa lonxitude n sexa inferior a 2?

647
00:30:09,477 --> 00:30:11,060
El xa está clasificado, obviamente, non é?

648
00:30:11,060 --> 00:30:13,640
Como a lista ten tanto
un elemento, o que é trivial

649
00:30:13,640 --> 00:30:15,180
clasificadas por que é
o único que existe.

650
00:30:15,180 --> 00:30:18,138
Ou, é de tamaño cero, o que significa
non hai nada para resolver, por iso, natureza

651
00:30:18,138 --> 00:30:18,720
el é clasificado.

652
00:30:18,720 --> 00:30:20,410
Só hai nada de malo alí.

653
00:30:20,410 --> 00:30:22,310
Entón, ese é o noso chamado caso base.

654
00:30:22,310 --> 00:30:24,440
>> Isto é semellante en espírito
ao que fixemos con Mike.

655
00:30:24,440 --> 00:30:26,023
Se Mike no libro de teléfono, chame el.

656
00:30:26,023 --> 00:30:27,740
Se non está alí, renuncia.

657
00:30:27,740 --> 00:30:31,240
É un chamado proceso de base, para asegurarse
este algoritmo, ao final do día

658
00:30:31,240 --> 00:30:33,540
deixará en determinadas circunstancias.

659
00:30:33,540 --> 00:30:37,890
>> Pero aquí está o salto de fe agora, máis,
ordenar a metade esquerda dos elementos,

660
00:30:37,890 --> 00:30:39,740
logo clasificar o dereito
metade dos elementos,

661
00:30:39,740 --> 00:30:41,189
e logo mesturar as metades clasificados.

662
00:30:41,189 --> 00:30:43,230
E aquí é onde se sente
como estamos amarelando.

663
00:30:43,230 --> 00:30:46,900
Pedinlle para clasificar
n elementos, e eu son

664
00:30:46,900 --> 00:30:50,712
dicindo: OK, faino por clasificación
á esquerda e á selección da dereita.

665
00:30:50,712 --> 00:30:52,420
Pero eu digo unha
outra cousa, e esta

666
00:30:52,420 --> 00:30:55,530
é o tema central parece
na intuición, ata agora,

667
00:30:55,530 --> 00:30:57,380
hai esta terceira etapa de fusión.

668
00:30:57,380 --> 00:31:00,430
Que aínda
Parece tan burro en espírito,

669
00:31:00,430 --> 00:31:02,320
como só mesturar cousas
xuntos, parece

670
00:31:02,320 --> 00:31:05,380
ser un paso fundamental para o
reasemblaxe de dous problemas que

671
00:31:05,380 --> 00:31:07,330
foron divididos en última instancia, á metade.

672
00:31:07,330 --> 00:31:12,090
>> Entón, merge sort, imos facelo, se
humor me, con máis dunha demostración,

673
00:31:12,090 --> 00:31:14,730
só para que teñamos algunha
números de traballar.

674
00:31:14,730 --> 00:31:19,470
Podo cambiar oito estrés
bolas para oito persoas?

675
00:31:19,470 --> 00:31:29,320
Todo ben, que tal vos tres, vostedes catro
nesta sección, cinco, seis, e imos

676
00:31:29,320 --> 00:31:30,720
non 7, 8, imos cara arriba.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK, si Aceptar.

679
00:31:36,520 --> 00:31:38,640
Minus 8, alí imos nós, máis 1.

680
00:31:38,640 --> 00:31:39,150
Excelente.

681
00:31:39,150 --> 00:31:42,000
Todos veñen a dereita enriba, imos
rapidamente darlle números.

682
00:31:42,000 --> 00:31:50,800
O número dous, número tres, número catro,
número cinco, seis, sete, e oito.

683
00:31:50,800 --> 00:31:52,140
Eu fixen oito correctamente esta vez.

684
00:31:52,140 --> 00:31:56,390
>> OK, entón vai adiante se puidese, e
imos clasificar en orde orixinal

685
00:31:56,390 --> 00:31:59,810
que tivemos onte que parecía
así, se non se importar.

686
00:31:59,810 --> 00:32:03,620
E imos facelo diante da táboa.

687
00:32:03,620 --> 00:32:06,510
Todo ben, entón merge sort.

688
00:32:06,510 --> 00:32:08,820
Este é o lugar onde vai
para chegar ben interesante,

689
00:32:08,820 --> 00:32:12,800
porque parece que estou me dando
moito menos información hoxe.

690
00:32:12,800 --> 00:32:15,149
>> Así fundir tipo en primeiro lugar
na entrada de n elementos,

691
00:32:15,149 --> 00:32:18,440
e é, obviamente, non inferior a dous, é
oito, entón eu teño un pouco máis de traballo para facer.

692
00:32:18,440 --> 00:32:21,140
Entón, agora nós mentalmente como unha clase
están na outra filial,

693
00:32:21,140 --> 00:32:22,540
o que significa que tres pasos.

694
00:32:22,540 --> 00:32:25,017
En primeiro lugar, teño que resolver o
metade esquerda dos elementos.

695
00:32:25,017 --> 00:32:26,350
Entón como é que eu vou facer iso?

696
00:32:26,350 --> 00:32:28,950
Ben, eu estou indo para o tipo de
dividir mentalmente a lista aquí,

697
00:32:28,950 --> 00:32:30,700
non ten que
mover fisicamente, e estou

698
00:32:30,700 --> 00:32:33,180
vai centrar-se só na
metade esquerda dos elementos aquí.

699
00:32:33,180 --> 00:32:36,770
Entón, como fago para clasificar
unha lista agora do tamaño de catro?

700
00:32:36,770 --> 00:32:38,730
Cal é o meu algoritmo?

701
00:32:38,730 --> 00:32:42,580
Primeiro eu verifico é n inferior a dous, non,
para que eu continúe para o bloque máis novo.

702
00:32:42,580 --> 00:32:43,900
Ordenar deixou metade de elementos.

703
00:32:43,900 --> 00:32:45,608
>> Polo tanto, agora de novo, mental,
e é aí onde

704
00:32:45,608 --> 00:32:49,550
ten que acumular unha morea de
historia mental, se quere.

705
00:32:49,550 --> 00:32:51,940
Agora estou clasificando á esquerda
a metade do lado esquerdo.

706
00:32:51,940 --> 00:32:57,000
Todo ben, entón agora eu chamo o meu mesmo merge
algoritmo de clasificación, é n inferior a dous?

707
00:32:57,000 --> 00:33:00,590
Non, é dous, entón eu teño que clasificar
a metade da esquerda, e á metade dereita.

708
00:33:00,590 --> 00:33:02,042
Entón, imos alí, ordenar a metade esquerda.

709
00:33:02,042 --> 00:33:03,750
Por que non só
dar un paso adiante.

710
00:33:03,750 --> 00:33:04,415
Cal é o seu nome?

711
00:33:04,415 --> 00:33:04,860
>> Audiencia: Darren.

712
00:33:04,860 --> 00:33:05,260
>> Palestrante: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan deu un paso á fronte.

714
00:33:06,040 --> 00:33:06,748
>> Audiencia: Darren.

715
00:33:06,748 --> 00:33:09,000
Palestrante: Darren, feito.

716
00:33:09,000 --> 00:33:10,090
Vostede dixo Darren ou Dan?

717
00:33:10,090 --> 00:33:10,550
>> Audiencia: Darren.

718
00:33:10,550 --> 00:33:11,216
>> Palestrante: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren ten intensificado
adiante e que é agora clasificada.

720
00:33:14,422 --> 00:33:16,130
E iso é case unha
reivindicación inane, non?

721
00:33:16,130 --> 00:33:18,862
Realmente non parece estar a acadar
nada, pero imos seguir.

722
00:33:18,862 --> 00:33:20,820
Agora déixeme ordenar a dereita
metade dos elementos.

723
00:33:20,820 --> 00:33:21,200
Cal é o seu nome?

724
00:33:21,200 --> 00:33:21,690
>> Audiencia: Lucas.

725
00:33:21,690 --> 00:33:22,273
>> Palestrante: Lucas.

726
00:33:22,273 --> 00:33:23,400
Imos, un paso adiante.

727
00:33:23,400 --> 00:33:25,640
Feito, eu classifiquei Lucas.

728
00:33:25,640 --> 00:33:28,570
A metade esquerda é agora clasificado e
a metade da dereita é agora clasificada,

729
00:33:28,570 --> 00:33:30,770
pero, de novo, hai un paso clave aquí.

730
00:33:30,770 --> 00:33:32,940
O que eu teño que facer o próximo?

731
00:33:32,940 --> 00:33:33,941
Unir as metades clasificados.

732
00:33:33,941 --> 00:33:36,648
Agora imos ter só
todo atrás e para adiante deste xeito,

733
00:33:36,648 --> 00:33:38,620
porque eu medio que teño
un espazo de borrador.

734
00:33:38,620 --> 00:33:40,411
É case como se estes
caras están sobre unha mesa,

735
00:33:40,411 --> 00:33:42,460
e eu teño un espazo
para mover los en.

736
00:33:42,460 --> 00:33:44,170
Entón eu vou para mesturar
vostedes mirando

737
00:33:44,170 --> 00:33:45,960
na metade esquerda e o da metade dereita.

738
00:33:45,960 --> 00:33:48,740
E que, obviamente, ven en primeiro lugar,
metade esquerda ou metade dereita?

739
00:33:48,740 --> 00:33:52,710
Entón metade dereita, entón imos mover Lucas sobre
aquí a posición orixinal de Darren.

740
00:33:52,710 --> 00:33:57,640
E agora fundir a súa metade esquerda en,
Darren vai mover á dereita alí.

741
00:33:57,640 --> 00:33:59,750
>> Entón, parece que case
un efecto bubble sort,

742
00:33:59,750 --> 00:34:02,482
pero o meu algoritmo fundamental
moi diferente esta vez.

743
00:34:02,482 --> 00:34:04,815
Pero agora é onde as cousas están un
pouco aburrido, porque

744
00:34:04,815 --> 00:34:06,810
ten que rebobinar mental
onde foi que eu parei.

745
00:34:06,810 --> 00:34:09,893
Acaba fundiu as metades ordenada,
o que significa que eu estou onde no meu algoritmo?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Teño que clasificar a metade dereita, non?

748
00:34:13,770 --> 00:34:15,910
>> Se volver, literalmente
no vídeo, vai

749
00:34:15,910 --> 00:34:18,339
ver que chegamos a este
punto de Luke e Darren

750
00:34:18,339 --> 00:34:21,370
clasificando á esquerda
a metade do lado esquerdo.

751
00:34:21,370 --> 00:34:23,430
Logo, fundiu os
metades ordenadas, que

752
00:34:23,430 --> 00:34:27,941
significa que o seguinte paso é o tipo
metade dereita da metade esquerda.

753
00:34:27,941 --> 00:34:29,649
Todo ben, entón imos
facelo máis rápido.

754
00:34:29,649 --> 00:34:33,282
Todo ben, seis, eu vou reclamar
está agora resolto, imos para adiante.

755
00:34:33,282 --> 00:34:33,990
Cal é o seu nome?

756
00:34:33,990 --> 00:34:34,589
>> Audiencia: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> Palestrante: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano está clasificada.

759
00:34:36,010 --> 00:34:36,450
E cal o seu nome?

760
00:34:36,450 --> 00:34:37,080
>> Audiencia: Alex.

761
00:34:37,080 --> 00:34:38,379
>> Palestrante: Alex está clasificada.

762
00:34:38,379 --> 00:34:40,750
Media esquerda, media dereita,
cal é o paso final?

763
00:34:40,750 --> 00:34:41,250
Unir.

764
00:34:41,250 --> 00:34:44,310
Moi trivial, polo que estou
vai fundir en seis,

765
00:34:44,310 --> 00:34:46,930
dar un paso atrás,
oito, dar un paso atrás.

766
00:34:46,930 --> 00:34:49,530
E agora entender iso é
un takeaway útil, o que

767
00:34:49,530 --> 00:34:53,930
é agora feito sobre a metade esquerda da
lista, independentemente de como empezamos?

768
00:34:53,930 --> 00:34:55,090
Está clasificada.

769
00:34:55,090 --> 00:34:57,750
>> Agora non está clasificada en
o gran esquema das cousas,

770
00:34:57,750 --> 00:35:00,250
pero ela é ordenada independentemente
da outra metade.

771
00:35:00,250 --> 00:35:04,100
Agora, o que paso son eu en manterse
rebobinar como a historia comezou?

772
00:35:04,100 --> 00:35:05,680
Agora eu teño que clasificar a metade dereita.

773
00:35:05,680 --> 00:35:07,630
Polo tanto, agora estamos no camiño de volta
o comezo da historia,

774
00:35:07,630 --> 00:35:08,921
e imos facelo máis rápido.

775
00:35:08,921 --> 00:35:11,320
Entón eu vou para clasificar a
metade dereita da lista enteira.

776
00:35:11,320 --> 00:35:13,060
Cal é o seguinte paso?

777
00:35:13,060 --> 00:35:15,840
Ordena a metade esquerda da metade dereita.

778
00:35:15,840 --> 00:35:18,715
Ordena a metade esquerda da
a metade esquerda da metade dereita.

779
00:35:18,715 --> 00:35:19,590
E cal o seu nome?

780
00:35:19,590 --> 00:35:20,230
>> Audiencia: Omar.

781
00:35:20,230 --> 00:35:21,970
>> Palestrante: Omar, un paso adiante, feito.

782
00:35:21,970 --> 00:35:22,860
A metade esquerda está clasificada.

783
00:35:22,860 --> 00:35:23,330
E cal o seu nome?

784
00:35:23,330 --> 00:35:23,820
>> Audiencia: Chris.

785
00:35:23,820 --> 00:35:25,620
>> Palestrante: Chris, dar un paso
á fronte, está agora clasificada.

786
00:35:25,620 --> 00:35:27,010
Cal é a clave paso agora?

787
00:35:27,010 --> 00:35:27,510
Unir.

788
00:35:27,510 --> 00:35:30,509
Entón, un vai fusionarse en lugar
aquí, se puidese dar un paso atrás,

789
00:35:30,509 --> 00:35:32,930
e tres vai
dar un paso atrás, se funden.

790
00:35:32,930 --> 00:35:38,080
Así, a metade esquerda da
metade dereita, agora está resolto.

791
00:35:38,080 --> 00:35:41,747
Francamente, este algoritmo se sente como nós
están gastan moito máis tempo do que antes,

792
00:35:41,747 --> 00:35:44,830
pero se non o fixo en tempo real, imos
ver o que os delivery será.

793
00:35:44,830 --> 00:35:47,970
Agora estou aquí, non
a metade do lado dereito,

794
00:35:47,970 --> 00:35:50,170
déixeme ir adiante e resolver a metade esquerda.

795
00:35:50,170 --> 00:35:51,482
Paso adiante, o que é o seu nome?

796
00:35:51,482 --> 00:35:52,190
Audiencia: Ramsey.

797
00:35:52,190 --> 00:35:53,210
Palestrante: Ramsey está clasificada.

798
00:35:53,210 --> 00:35:53,570
Cal é o seu nome?

799
00:35:53,570 --> 00:35:54,200
>> Audiencia: Marina.

800
00:35:54,200 --> 00:35:57,033
>> Palestrante: Marina está clasificada como
Ben, se der un paso á fronte.

801
00:35:57,033 --> 00:36:00,690
Clave paso aquí agora é fundir, eu son
vai arrincar das miñas dúas listas,

802
00:36:00,690 --> 00:36:01,720
esquerda e dereita.

803
00:36:01,720 --> 00:36:05,150
Cinco vai vir en primeiro lugar,
e sete vai vir axiña.

804
00:36:05,150 --> 00:36:06,410
E, de novo, iso é proposital.

805
00:36:06,410 --> 00:36:08,535
O feito de que están levando
pasos para adiante e cara atrás

806
00:36:08,535 --> 00:36:12,997
emprégase para representar que non podemos
facer ese algoritmo no lugar coa mesma facilidade

807
00:36:12,997 --> 00:36:15,830
como bubble sort, e selección de tipo,
e inserción tipo en que só

808
00:36:15,830 --> 00:36:16,960
mantivo cambiando persoas.

809
00:36:16,960 --> 00:36:19,940
Eu literalmente ten que un tipo
de papel de borrador en que

810
00:36:19,940 --> 00:36:21,827
para poñer esas persoas
mentres fago a fusión,

811
00:36:21,827 --> 00:36:23,410
e entón eu podo poñer-los de volta no lugar.

812
00:36:23,410 --> 00:36:27,260
E iso é fundamental, porque eu estou usando un
nova función, o espazo, non só tempo.

813
00:36:27,260 --> 00:36:28,270
>> OK, iso é incrible.

814
00:36:28,270 --> 00:36:32,050
A metade esquerda é clasificado, a metade dereita é
, Agora que a clave fusión etapa de clasificación.

815
00:36:32,050 --> 00:36:33,450
Como é que eu vou mesturar esa?

816
00:36:33,450 --> 00:36:35,470
Entón, se seguir o meu
man esquerda e man dereita,

817
00:36:35,470 --> 00:36:38,930
Vou apuntar a miña man esquerda
na metade esquerda, man dereita

818
00:36:38,930 --> 00:36:42,680
na metade dereita, e agora eu teño que
decidir paso a paso que se fundir en.

819
00:36:42,680 --> 00:36:44,650
Que, por suposto, ven en primeiro lugar?

820
00:36:44,650 --> 00:36:45,150
Número un.

821
00:36:45,150 --> 00:36:47,327
Entón veña para aquí,
aquí está o noso bloque de borrador.

822
00:36:47,327 --> 00:36:49,910
Entón, agora o número un, e previo
o que vou facer coa miña man dereita,

823
00:36:49,910 --> 00:36:54,152
Vou pasar a miña man dereita
pasar por riba ao punto número tres,

824
00:36:54,152 --> 00:36:55,860
e agora eu teño que facer
a mesma decisión.

825
00:36:55,860 --> 00:36:58,387
E, de feito, estar ben na
cabeza de Luke aquí se puidese,

826
00:36:58,387 --> 00:36:59,720
porque este é o noso bloque de borrador.

827
00:36:59,720 --> 00:37:00,610
Entón, quen vén a continuación?

828
00:37:00,610 --> 00:37:05,000
Temos Luke co número dous
ou Chris co número tres.

829
00:37:05,000 --> 00:37:07,460
Obviamente Luke, número
dous, para que veña aquí.

830
00:37:07,460 --> 00:37:11,270
>> Pero a miña man esquerda agora vai
ser incrementado para ligar a Darren,

831
00:37:11,270 --> 00:37:15,160
e aquí está a clave aproveitar con
fusión, eu vou continuar a facer iso,

832
00:37:15,160 --> 00:37:17,340
Obviamente, se tipo
de seguir a lóxica.

833
00:37:17,340 --> 00:37:19,670
Pero as mans nunca son
indo a ir cara atrás,

834
00:37:19,670 --> 00:37:23,861
o que significa que eu estou sempre só movendo-se a
esquerda co meu proceso de fusión,

835
00:37:23,861 --> 00:37:26,360
e que será a clave para
nosa análise en só un momento.

836
00:37:26,360 --> 00:37:27,859
>> Entón agora imos rematar isto rapidamente.

837
00:37:27,859 --> 00:37:31,650
Entón, tres vén a seguir,
despois catro vén a seguir,

838
00:37:31,650 --> 00:37:38,750
e agora vén a continuación cinco, despois seis,
e sete, e finalmente oito.

839
00:37:38,750 --> 00:37:42,960
Parece que o algoritmo máis lento
aínda, pero non se realmente

840
00:37:42,960 --> 00:37:45,510
executa-lo, ao mesmo tipo
de velocidade de reloxo, por así

841
00:37:45,510 --> 00:37:48,106
dicir, coa mesma
tique-taque do reloxo como antes.

842
00:37:48,106 --> 00:37:48,605
Por que?

843
00:37:48,605 --> 00:37:51,100
Ben, Imos dar un
mirar para o resultado final.

844
00:37:51,100 --> 00:37:56,990
>> Imos volver aquí, déixeme
puxe unha demostración visual

845
00:37:56,990 --> 00:37:59,030
que acabamos de facer.

846
00:37:59,030 --> 00:38:06,110
Achegar-se aquí, neste
páxina aquí, dicindo Firefox

847
00:38:06,110 --> 00:38:08,200
que queremos cola
ata neste campo, imos

848
00:38:08,200 --> 00:38:11,260
dicir bubble sort, co cal
agora estamos ben familiarizados,

849
00:38:11,260 --> 00:38:14,130
tipo de selección, que é outra
bastante un simple,

850
00:38:14,130 --> 00:38:18,250
e agora merge sort de hoxe, que
será o noso clímax final.

851
00:38:18,250 --> 00:38:21,530
A razón que levou moito máis tempo
aquí cos seres humanos e me verbalmente é,

852
00:38:21,530 --> 00:38:23,480
obviamente, eu estou explicando cada paso.

853
00:38:23,480 --> 00:38:26,920
Pero se simplemente executar este, moi
como fixemos bubble sort e selección

854
00:38:26,920 --> 00:38:30,890
tipo, non só visualmente, reloxo
o que de forma máis eficiente

855
00:38:30,890 --> 00:38:33,330
esta alavancagem de
división e conquista

856
00:38:33,330 --> 00:38:39,150
se pode, cando aplicado a un conxunto de datos que é
nin mesmo tamaño oito, pero aínda moito,

857
00:38:39,150 --> 00:38:39,970
moito maior.

858
00:38:39,970 --> 00:38:44,585
Eu doulle merge sort, lado a
lado con estes outros algoritmos.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Isto vai estar doloroso
rapidamente, eo final

861
00:38:58,530 --> 00:39:00,890
non é particularmente climático,
eles simplemente acabar ordenados.

862
00:39:00,890 --> 00:39:05,280
Pero a clave sacar é que
Mira o que máis rápido merge sort

863
00:39:05,280 --> 00:39:08,110
era, a menos que pensas que eu son
só unha especie de xogar con vostede.

864
00:39:08,110 --> 00:39:13,100
Se facemos iso unha última vez,
Imos actualizar isto, imos volver

865
00:39:13,100 --> 00:39:14,960
e escolle bubble sort,
e só por diversión,

866
00:39:14,960 --> 00:39:17,330
Imos escoller a inserción
tipo, só para unha boa medida.

867
00:39:17,330 --> 00:39:20,020
E esta vez, unha vez máis, imos
escoller merge sort e imos

868
00:39:20,020 --> 00:39:21,595
realmente realizar estes mosaico.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> E non é, en realidade, un golpe de sorte.

871
00:39:26,930 --> 00:39:31,140
O que eu fixen de forma eficaz é que eu teño
repartiron a miña entrada no medio, unha vez máis,

872
00:39:31,140 --> 00:39:32,240
e de novo, e de novo.

873
00:39:32,240 --> 00:39:35,590
E hai só tantas veces pode
partir a entrada en metades, esquerda

874
00:39:35,590 --> 00:39:36,240
e á dereita.

875
00:39:36,240 --> 00:39:39,425
Cal é a fórmula que sigo vendo
que describe a división en metade

876
00:39:39,425 --> 00:39:41,050
de novo, e de novo, e de novo, e de novo?

877
00:39:41,050 --> 00:39:41,890
>> Audiencia: Log n.

878
00:39:41,890 --> 00:39:42,760
>> Palestrante: Log n.

879
00:39:42,760 --> 00:39:46,300
Pero despois hai outro gran paso,
este algoritmo non é log n pasos.

880
00:39:46,300 --> 00:39:48,992
Se só foron log n pasos,
estariamos no mesmo problema

881
00:39:48,992 --> 00:39:51,200
como antes, onde non podemos ser
Asegúrese de que está todo resolto.

882
00:39:51,200 --> 00:39:54,480
Ten que ollar minimamente n elementos
para estar seguro de n elementos son ordenados,

883
00:39:54,480 --> 00:39:55,950
pola contra, é un salto de fe.

884
00:39:55,950 --> 00:39:59,810
>> Entón é rexistro minimamente n pasos, pero
o que pasa con este paso clave fusión

885
00:39:59,810 --> 00:40:04,370
onde fundiu miña metade esquerda e dereita
medio e atravesou o escenario?

886
00:40:04,370 --> 00:40:06,980
Cantos pasos é que fundirse?

887
00:40:06,980 --> 00:40:10,150
É n, pero non o fixen só
mesturar o tempo final.

888
00:40:10,150 --> 00:40:15,089
En cada unha destas chamadas noutras citas, en cada
destas fusións aniñados, eu aínda clasificadas.

889
00:40:15,089 --> 00:40:18,380
Eu fundiuse eses dúas caras, entón estes dous
caras, entón eses dous caras e así por diante.

890
00:40:18,380 --> 00:40:19,955
>> Entón eu fixen a fusión de novo, e de novo.

891
00:40:19,955 --> 00:40:20,580
Cantas veces?

892
00:40:20,580 --> 00:40:23,510
Entón cada vez que eu dividía o
lista pola metade, eu fixen unha mesclagem.

893
00:40:23,510 --> 00:40:25,460
Débeda a lista ao medio, facer unha mesclagem.

894
00:40:25,460 --> 00:40:28,570
Polo tanto, se a división Árbore
se pode facer de rexistro n veces,

895
00:40:28,570 --> 00:40:33,880
e en definitiva, a fusión ten n
etapas, o que se pode agora o superior

896
00:40:33,880 --> 00:40:37,000
Encadernado pola execución
tempo do noso algoritmo?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> E, de feito, é o que
nós conseguimos aquí.

899
00:40:40,560 --> 00:40:44,650
Entón, a sensación que ve cando visualmente
estas tres cousas corren mosaico

900
00:40:44,650 --> 00:40:47,930
n é cadrado contra n
cadrado contra o rexistro n n.

901
00:40:47,930 --> 00:40:51,010
Que fundamentalmente nos veremos,
Non só, pero hoxe en día, no futuro,

902
00:40:51,010 --> 00:40:52,760
é moito máis rápido.

903
00:40:52,760 --> 00:40:56,010
Unha salva de palmas para estes faces,
Vou recompensa-los con bolas de estrés.

904
00:40:56,010 --> 00:41:00,260
Imos pechar aquí hoxe, e
imos velo na luns.

905
00:41:00,260 --> 00:41:02,255