1
00:00:00,000 --> 00:00:11,100
>> [Música tocando]

2
00:00:11,100 --> 00:00:11,490
>> DAVID J. Malan: Todo ben.

3
00:00:11,490 --> 00:00:12,170
Entón Benvido de volta.

4
00:00:12,170 --> 00:00:15,180
É dicir CS50, e é o
o fin de semana tres.

5
00:00:15,180 --> 00:00:17,770
>> Entón, lembra nas últimas semanas,
estamos gastan un pouco de

6
00:00:17,770 --> 00:00:20,820
tempo en C, en programación, en sintaxe.

7
00:00:20,820 --> 00:00:24,680
E é moi normal, se aínda está
loitando co conxunto de problemas 2, para ser

8
00:00:24,680 --> 00:00:25,950
bater a súa cabeza contra a parede.

9
00:00:25,950 --> 00:00:28,310
É mensaxes de erro enigmáticas para o futuro
e os erros que

10
00:00:28,310 --> 00:00:29,220
non pode perseguir.

11
00:00:29,220 --> 00:00:32,310
Porque, pode estar seguro, que en só un
tempo de algunhas semanas vai ollar cara atrás

12
00:00:32,310 --> 00:00:35,930
cousas como César, e [? V-genair,?]
quizais ata de crack, e

13
00:00:35,930 --> 00:00:40,050
entender o quão lonxe chegou
nun curto período de tempo.

14
00:00:40,050 --> 00:00:43,670
Entón, se isto serve de consolo,
colgar alí por un tempo.

15
00:00:43,670 --> 00:00:46,610
>> Hoxe, con todo, comezan a transición
para cousas de máis alto nivel.

16
00:00:46,610 --> 00:00:49,820
E comezamos a dar por feito que
Vostedes saben programar, ou polo

17
00:00:49,820 --> 00:00:52,090
menos o inicio
que o nivel de confort.

18
00:00:52,090 --> 00:00:56,520
E imos comezar a considerar como podemos
ir sobre a creación de programas máis

19
00:00:56,520 --> 00:00:57,440
eficaz.

20
00:00:57,440 --> 00:01:01,090
Como podemos ir sobre como optimizar o
eficiencia dos algoritmos e

21
00:01:01,090 --> 00:01:03,110
adoita ser a solución máis
problemas interesantes.

22
00:01:03,110 --> 00:01:06,850
E comezando a tomar por certo que,
se quixésemos, poderiamos codificar calquera

23
00:01:06,850 --> 00:01:08,350
dos exemplos que temos en mente.

24
00:01:08,350 --> 00:01:11,430
Entón, hoxe, non tocar o teclado
a calquera forma de código.

25
00:01:11,430 --> 00:01:15,150
Vai ser nivel moito máis elevado, e
en última instancia, sobre a resolución de problemas.

26
00:01:15,150 --> 00:01:20,490
>> Entón, para chegar a ese punto, deixe-me propor
que os seguintes sete

27
00:01:20,490 --> 00:01:24,290
rectángulos representan sete portas, detrás
que son unha morea de

28
00:01:24,290 --> 00:01:26,340
números, entre os cales está o número 50.

29
00:01:26,340 --> 00:01:30,470
Déixeme proxectar este neste
pantalla aquí tamén.

30
00:01:30,470 --> 00:01:36,770
E propoñer que necesitamos un voluntario para
me axudar a atopar un número diante

31
00:01:36,770 --> 00:01:38,140
Internet aquí para ver.

32
00:01:38,140 --> 00:01:40,755
Imos para arriba, en cor rosa.

33
00:01:40,755 --> 00:01:43,050
Todo ben.

34
00:01:43,050 --> 00:01:43,930
Cal é o seu nome?

35
00:01:43,930 --> 00:01:44,850
>> Jennifer: [inaudível]

36
00:01:44,850 --> 00:01:45,170
>> DAVID J. Malan: Sentímolo?

37
00:01:45,170 --> 00:01:45,860
>> Jennifer: Jennifer.

38
00:01:45,860 --> 00:01:46,390
>> DAVID J. Malan: Jennifer.

39
00:01:46,390 --> 00:01:46,980
Todo ben, Jennifer.

40
00:01:46,980 --> 00:01:47,630
Pracer en coñece lo.

41
00:01:47,630 --> 00:01:48,370
Imos para arriba.

42
00:01:48,370 --> 00:01:52,430
Entón, eses aquí son sete portas, e que
Quere facer para nós aquí,

43
00:01:52,430 --> 00:01:56,560
diante de todos os seus compañeiros,
é atopar-nos o número, 50.

44
00:01:56,560 --> 00:02:00,860
Para atopar un número, pode espreitar detrás
calquera destas portas simplemente tocando

45
00:02:00,860 --> 00:02:03,030
nunha das portas, e
revela o seu número.

46
00:02:03,030 --> 00:02:06,080
E imos ver como rápido
pode atopar-nos o número, 50.

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15.

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16.

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50.

53
00:02:16,530 --> 00:02:17,350
Ben feito.

54
00:02:17,350 --> 00:02:18,040
Todo ben.

55
00:02:18,040 --> 00:02:19,906
Salva de palmas para Jennifer.

56
00:02:19,906 --> 00:02:21,530
>> [Aplausos]

57
00:02:21,530 --> 00:02:22,320
>> Todo ben.

58
00:02:22,320 --> 00:02:25,254
Entón, cal foi a súa estratexia para
atopar o número, o 50?

59
00:02:25,254 --> 00:02:27,222
>> Jennifer: Hum, eu penso que quizais se -

60
00:02:27,222 --> 00:02:27,714
[Inaudível]

61
00:02:27,714 --> 00:02:28,206
>> DAVID J. Malan: Oh

62
00:02:28,206 --> 00:02:29,630
Dele un segundo.

63
00:02:29,630 --> 00:02:32,420
Así foi a súa estratexia para
atopar o número, o 50?

64
00:02:32,420 --> 00:02:34,760
>> Jennifer: Entón, eu só comezar no
empezando a ver que o primeiro número

65
00:02:34,760 --> 00:02:38,590
era, e entón eu penso, se cadra se
están clasificadas, vou seguir

66
00:02:38,590 --> 00:02:39,970
tocando máis alto?

67
00:02:39,970 --> 00:02:40,140
>> DAVID J. Malan: Aceptar.

68
00:02:40,140 --> 00:02:42,910
E parece ter atopado
que sexa este o caso.

69
00:02:42,910 --> 00:02:45,670
Aínda que, imos pelar as capas
só un pouco, e quere ir

70
00:02:45,670 --> 00:02:47,640
adiante e revelar as outras portas
podería ter escollido?

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> Jennifer: Oh, querida.

73
00:02:51,712 --> 00:02:53,128
>> DAVID J. Malan: Ah.

74
00:02:53,128 --> 00:02:54,280
>> Jennifer: Entón eu só teño sorte.

75
00:02:54,280 --> 00:02:55,270
>> DAVID J. Malan: Entón vostede tivo sorte.

76
00:02:55,270 --> 00:02:55,710
Todo ben.

77
00:02:55,710 --> 00:02:56,795
Entón, non é malo.

78
00:02:56,795 --> 00:02:58,750
Pero iso é un interesante
insight, non?

79
00:02:58,750 --> 00:03:01,870
Se asumiu, e conseguiu,
en realidade, un pouco de sorte alí.

80
00:03:01,870 --> 00:03:05,350
Pero se do principio de que as cifras eran
clasificadas, pode ser máis preciso

81
00:03:05,350 --> 00:03:08,750
de como iso influenciou
o seu comportamento?

82
00:03:08,750 --> 00:03:11,715
>> Jennifer: Entón, se eles foron ordenados, eu
penso que quizais menor ao maior.

83
00:03:11,715 --> 00:03:11,970
>> DAVID J. Malan: Aceptar.

84
00:03:11,970 --> 00:03:15,260
>> Jennifer: Ou se iso acabou sendo
realmente grande, entón maior a menor.

85
00:03:15,260 --> 00:03:15,540
>> DAVID J. Malan: Aceptar.

86
00:03:15,540 --> 00:03:18,170
Entón maior a menor, ou
menor ao maior.

87
00:03:18,170 --> 00:03:21,990
Pero déixeme propoñer, supoñamos que tiña
obtido de azar, e supoñer que

88
00:03:21,990 --> 00:03:26,840
non foron, de feito, clasificado, cantos
aquelas portas que podería ter para espiar

89
00:03:26,840 --> 00:03:28,590
atrás en que o peor caso?

90
00:03:28,590 --> 00:03:29,860
>> Jennifer: Todos eles.

91
00:03:29,860 --> 00:03:30,420
>> David J. Malan: Todos eles.

92
00:03:30,420 --> 00:03:31,740
Entón imos xeneralizar que, como n.

93
00:03:31,740 --> 00:03:34,790
Non pasa a ser 7, pero imos máis
xeralmente din que hai n portas no

94
00:03:34,790 --> 00:03:35,650
pantalla aquí.

95
00:03:35,650 --> 00:03:40,110
Así, no peor caso, que tería que
para ollar cara atrás sete portas, ou n portas.

96
00:03:40,110 --> 00:03:44,140
E así, este realmente é, é un pouco de
sorte hoxe, pero é realmente un lineal

97
00:03:44,140 --> 00:03:46,440
algoritmo do tipo, aínda que
eran unha especie de saltar arredor.

98
00:03:46,440 --> 00:03:47,080
Iso é xusto?

99
00:03:47,080 --> 00:03:47,500
>> Jennifer: Yeah.

100
00:03:47,500 --> 00:03:50,000
>> DAVID J. Malan: Ben, deixe-me ver se o
cambios de estratexia, se nos moven

101
00:03:50,000 --> 00:03:52,190
noso segundo exemplo aquí con
7 portas distintas.

102
00:03:52,190 --> 00:03:55,240
Os mesmos números, pero esta
xa que son clasificados.

103
00:03:55,240 --> 00:03:58,350
Cal é a súa estratexia aquí vai ser,
intentando borrar da súa mente o que

104
00:03:58,350 --> 00:03:59,310
os outros números foron -

105
00:03:59,310 --> 00:03:59,930
>> Jennifer: Aceptar.

106
00:03:59,930 --> 00:04:02,290
>> DAVID J. Malan - máis cedo?

107
00:04:02,290 --> 00:04:03,180
>> Jennifer: Imos comezar
co primeiro.

108
00:04:03,180 --> 00:04:03,540
>> DAVID J. Malan: Todo ben.

109
00:04:03,540 --> 00:04:05,190
Comeza o primeiro.

110
00:04:05,190 --> 00:04:05,960
4.

111
00:04:05,960 --> 00:04:08,810
Agora, onde vai pasar, e por que?

112
00:04:08,810 --> 00:04:10,040
>> Jennifer: 4 é moi pequeno.

113
00:04:10,040 --> 00:04:12,500
Entón, se son unha especie quizais menor
a maior, que debería

114
00:04:12,500 --> 00:04:13,290
ser o dobre, e -.

115
00:04:13,290 --> 00:04:13,670
>> DAVID J. Malan: Aceptar.

116
00:04:13,670 --> 00:04:15,990
A ver, o que pensas?

117
00:04:15,990 --> 00:04:19,050
>> Jennifer: Proba a última.

118
00:04:19,050 --> 00:04:19,500
Niza.

119
00:04:19,500 --> 00:04:20,880
>> DAVID J. Malan: Moi ben feito.

120
00:04:20,880 --> 00:04:21,860
Todo ben.

121
00:04:21,860 --> 00:04:23,010
>> [Aplausos]

122
00:04:23,010 --> 00:04:24,310
>> DAVID J. Malan: Aceptar.

123
00:04:24,310 --> 00:04:26,790
Entón, en realidade está a facer iso
horrible, porque é

124
00:04:26,790 --> 00:04:27,700
facelo moi ben.

125
00:04:27,700 --> 00:04:31,150
O que nos deixa sen poder
facer determinados puntos.

126
00:04:31,150 --> 00:04:32,565
Entón, imos tratar de reverter aquí.

127
00:04:32,565 --> 00:04:34,560
>> Jennifer: Aceptar.

128
00:04:34,560 --> 00:04:35,980
>> DAVID J. Malan: Moi ben
feito, con todo.

129
00:04:35,980 --> 00:04:39,060
Entón comezou o principio,
viu que tiña 4 anos, entón

130
00:04:39,060 --> 00:04:40,240
desprazada cara ao final.

131
00:04:40,240 --> 00:04:42,320
Pero supoñamos que non ten sorte
alí, e supoño que o 50

132
00:04:42,320 --> 00:04:42,890
estaba noutro lugar.

133
00:04:42,890 --> 00:04:46,190
Cal é a súa terceira etapa ser?

134
00:04:46,190 --> 00:04:47,680
>> Jennifer: Voltar para o comezo.

135
00:04:47,680 --> 00:04:48,320
>> DAVID J. Malan: Volva
ao principio.

136
00:04:48,320 --> 00:04:51,320
OK, entón tería tocado
esta porta, o cal foi de 8.

137
00:04:51,320 --> 00:04:51,660
Todo ben.

138
00:04:51,660 --> 00:04:52,650
Entón, iso non é 50.

139
00:04:52,650 --> 00:04:55,380
Onde é que mirou ao lado?

140
00:04:55,380 --> 00:04:56,720
>> Jennifer: Se eu non fixen
saben que clasificados.

141
00:04:56,720 --> 00:04:57,005
>> DAVID J. Malan: Correcto.

142
00:04:57,005 --> 00:04:58,490
Ben, se soubese
foron clasificadas -

143
00:04:58,490 --> 00:04:58,700
>> Jennifer: Ah, sabía, si.

144
00:04:58,700 --> 00:05:00,910
>> DAVID J. Malan: - pero non fixo
sabe onde 50 foi aínda?

145
00:05:00,910 --> 00:05:01,785
>> Jennifer: Só continuar.

146
00:05:01,785 --> 00:05:02,130
>> DAVID J. Malan: Todo ben.

147
00:05:02,130 --> 00:05:02,520
Aceptar.

148
00:05:02,520 --> 00:05:03,800
Continúe indo.

149
00:05:03,800 --> 00:05:05,270
OK, para que eu poida traballar.

150
00:05:05,270 --> 00:05:05,610
>> Jennifer: Aceptar.

151
00:05:05,610 --> 00:05:07,210
>> DAVID J. Malan: Agora, se está só
continuará, o que é o seu

152
00:05:07,210 --> 00:05:09,680
algoritmo que recaen apoiado en.

153
00:05:09,680 --> 00:05:10,740
>> Jennifer: o lineal -.

154
00:05:10,740 --> 00:05:11,820
>> DAVID J. Malan: É unha especie de lineal.

155
00:05:11,820 --> 00:05:13,480
Pero déixeme propoñer, imos
me poñer no lugar.

156
00:05:13,480 --> 00:05:14,900
Déixeme actualizar a páxina.

157
00:05:14,900 --> 00:05:17,120
mesmo número, o mesmo arranxo,
mesmas portas.

158
00:05:17,120 --> 00:05:21,350
Pero creo que volver a aquel primeiro día en
clase cando resgou un libro de teléfono en

159
00:05:21,350 --> 00:05:25,480
metade, máis ou menos, eo que era
nosa estratexia alí?

160
00:05:25,480 --> 00:05:26,450
>> Jennifer: Comezar polo medio.

161
00:05:26,450 --> 00:05:26,690
>> DAVID J. Malan: Aceptar.

162
00:05:26,690 --> 00:05:27,610
Polo tanto, comece no medio.

163
00:05:27,610 --> 00:05:28,790
Entón, imos adiante e simular iso.

164
00:05:28,790 --> 00:05:30,720
Comezar polo medio por
revelando que porta.

165
00:05:30,720 --> 00:05:31,660
Polo tanto, o número 16.

166
00:05:31,660 --> 00:05:35,290
Entón, o que a cara forte fixeron,
que resgou o libro de teléfono pola metade,

167
00:05:35,290 --> 00:05:38,450
para chegar ao seguinte palpite?

168
00:05:38,450 --> 00:05:39,400
>> Jennifer: Vai no semestre.

169
00:05:39,400 --> 00:05:41,700
>> DAVID J. Malan: E por que a dereita?

170
00:05:41,700 --> 00:05:43,900
>> Jennifer: No caso de que eran unha especie de menor
para o maior, entón debe ser 50

171
00:05:43,900 --> 00:05:44,720
nesa extrema.

172
00:05:44,720 --> 00:05:44,920
>> DAVID J. Malan: Xenial.

173
00:05:44,920 --> 00:05:45,390
Totalmente razoable.

174
00:05:45,390 --> 00:05:48,380
Así como un libro de teléfono, vai a
dereita, por oposición á esquerda, pero aquí

175
00:05:48,380 --> 00:05:49,500
é o principal argumento.

176
00:05:49,500 --> 00:05:53,930
Agora podes xogar fóra, ou arrincar,
semestre deste problema, deixando o non

177
00:05:53,930 --> 00:05:55,970
con 7 portas, pero realmente con só 3.

178
00:05:55,970 --> 00:05:57,870
Que é preto de metade da
dimensión do problema.

179
00:05:57,870 --> 00:05:58,350
Todo ben.

180
00:05:58,350 --> 00:06:01,890
Polo tanto, agora que tería
feito despois de que vai á dereita?

181
00:06:01,890 --> 00:06:05,870
>> Jennifer: So 16 aínda é moi pequeno,
en relación a 50, quizais por iso eu vou probar,

182
00:06:05,870 --> 00:06:06,700
como, un agasallo.

183
00:06:06,700 --> 00:06:07,890
>> DAVID J. Malan: Todo ben.

184
00:06:07,890 --> 00:06:08,720
42.

185
00:06:08,720 --> 00:06:10,830
Todo ben, entón agora o que é o seu
instinto dicindo a vostede?

186
00:06:10,830 --> 00:06:12,100
>> Jennifer: Eu podo xogar fóra
isto e, a continuación, só -

187
00:06:12,100 --> 00:06:12,360
>> DAVID J. Malan: Aceptar.

188
00:06:12,360 --> 00:06:14,212
Bo, pode xogar fóra
a metade esquerda alí.

189
00:06:14,212 --> 00:06:14,890
>> Jennifer: - escoller un.

190
00:06:14,890 --> 00:06:15,530
>> DAVID J. Malan: E a dereita.

191
00:06:15,530 --> 00:06:15,760
>> Jennifer: Yeah.

192
00:06:15,760 --> 00:06:17,820
>> DAVID J. Malan: Entón, aínda que sexa difícil
ver se cadra, cando hai só

193
00:06:17,820 --> 00:06:21,320
Sete portas, pensar, agora,
a consistencia do

194
00:06:21,320 --> 00:06:22,620
algoritmo que acaba de aplicar.

195
00:06:22,620 --> 00:06:24,510
No caso anterior, o que fixo
ter sorte, o que foi xenial.

196
00:06:24,510 --> 00:06:26,540
Pero fixo utilizar unha heurística,
Eu diría.

197
00:06:26,540 --> 00:06:29,150
Usou unha especie de seus instintos, e
saber ordenado, se é moi

198
00:06:29,150 --> 00:06:31,600
pequena en principio, obviamente, temos
ten que ir máis á dereita.

199
00:06:31,600 --> 00:06:34,990
Pero, en certo sentido, tes sorte,
porque quizais este foi o número 100,

200
00:06:34,990 --> 00:06:36,220
e quizais 50 foi máis no medio.

201
00:06:36,220 --> 00:06:37,910
Quizais 50 fose o mesmo por aquí.

202
00:06:37,910 --> 00:06:40,960
>> Pero o que fixo un pouco diferente
esta vez foi, fixo o mesmo

203
00:06:40,960 --> 00:06:42,150
unha e outra vez.

204
00:06:42,150 --> 00:06:45,310
E eu diría que o que acaba
se, aínda influenciado por teléfono

205
00:06:45,310 --> 00:06:48,100
libro exemplo, é algo moi
máis algorítmica, e moito

206
00:06:48,100 --> 00:06:49,930
menos especial casetonado.

207
00:06:49,930 --> 00:06:51,620
Moito menos instintivo.

208
00:06:51,620 --> 00:06:57,160
Así, ao final do día, como sería
que describe a eficacia do

209
00:06:57,160 --> 00:07:00,530
primeiro algoritmo, onde se
esquerda a dereita, contra o

210
00:07:00,530 --> 00:07:03,430
segundo algoritmo aquí?

211
00:07:03,430 --> 00:07:06,460
>> Jennifer: Isto débese, como, quizais
reducir á metade o tempo, ou máis, si.

212
00:07:06,460 --> 00:07:07,320
>> DAVID J. Malan: OK, quizais ata máis.

213
00:07:07,320 --> 00:07:10,150
Imos empurrar un pouco máis sobre iso.

214
00:07:10,150 --> 00:07:13,030
O que realmente si continuar esta
lóxica, nós sempre reduciu á metade o

215
00:07:13,030 --> 00:07:15,830
tempo de carreira con este segundo algoritmo
xogando fóra a metade do

216
00:07:15,830 --> 00:07:18,470
números, pero o que imos facer o próximo
iteración, cando Jennifer revelou

217
00:07:18,470 --> 00:07:20,615
o segundo número?

218
00:07:20,615 --> 00:07:22,830
>> Nós á metade o número de portas de novo.

219
00:07:22,830 --> 00:07:25,270
E entón o que fixemos tras o que, se
había máis portas para xogar?

220
00:07:25,270 --> 00:07:27,520
Queremos metade deles, e unha vez máis,
e de novo, e de novo.

221
00:07:27,520 --> 00:07:30,420
E iso era exactamente como vostedes todos
pé na primeira semana de

222
00:07:30,420 --> 00:07:33,000
clase, a metade do que sentir-se, a metade
de sentir, a metade de vós

223
00:07:33,000 --> 00:07:35,440
sentir-se, ata que un solitario
alma estaba de pé.

224
00:07:35,440 --> 00:07:39,050
E nós dixemos que o tempo de execución
tanto, o número de pasos Bastou

225
00:07:39,050 --> 00:07:40,430
na orde de que?

226
00:07:40,430 --> 00:07:41,230
>> COLUMNA 1: [inaudível]

227
00:07:41,230 --> 00:07:43,970
>> DAVID J. Malan: Entón rexistro base 2 de n,
ou só máis sinxelo, faga o login do n.

228
00:07:43,970 --> 00:07:45,060
Polo tanto, algo logarítmica.

229
00:07:45,060 --> 00:07:48,380
E a gráfica non é unha liña recta
que quedou peor e peor, foi

230
00:07:48,380 --> 00:07:52,490
interesante que esta curva non fixo
ir tan mal ao longo do tempo.

231
00:07:52,490 --> 00:07:53,910
Entón, imos manter esa idea.

232
00:07:53,910 --> 00:07:54,690
Imos dar as grazas a Jennifer.

233
00:07:54,690 --> 00:07:56,150
Moitas grazas por teren benvida enriba.

234
00:07:56,150 --> 00:07:57,400
E, un segundo.

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
Non hai mesa lámpadas hoxe, pero nós
ten CS50 bolas de estrés.

237
00:08:02,925 --> 00:08:03,420
>> Jennifer: Yay.

238
00:08:03,420 --> 00:08:04,410
>> DAVID J. Malan: Todo ben, aquí.

239
00:08:04,410 --> 00:08:06,545
Grazas por incorrer
o estrés aquí.

240
00:08:06,545 --> 00:08:07,350
Todo ben.

241
00:08:07,350 --> 00:08:10,620
Entón, imos ver se non podemos agora
formalizar esta un pouco máis.

242
00:08:10,620 --> 00:08:14,820
Entón, de novo, o que fixemos foi
esencialmente o mesmo que fixemos

243
00:08:14,820 --> 00:08:16,660
en que a primeira semana.

244
00:08:16,660 --> 00:08:23,780
Pero en vez de final con só un lineal
algoritmo, que representado

245
00:08:23,780 --> 00:08:27,210
anteriormente como esa liña recta,
polo que, se colocarmos unha porta

246
00:08:27,210 --> 00:08:29,610
pantalla, logo Jennifer tería
tiveron que mirar, potencialmente,

247
00:08:29,610 --> 00:08:30,600
detrás de unha porta.

248
00:08:30,600 --> 00:08:33,490
Se colocarmos dúas portas, un pode ter
para ollar cara atrás dúas portas.

249
00:08:33,490 --> 00:08:35,990
>> E así, houbo esa lineal
relación entre o tamaño da

250
00:08:35,990 --> 00:08:39,059
problema en, por exemplo, o eixe x, e
a cantidade de tempo que leva a

251
00:08:39,059 --> 00:08:40,440
resolver na y.

252
00:08:40,440 --> 00:08:43,330
Pero a imaxe que eu estaba aludindo
anterior era esta liña verde.

253
00:08:43,330 --> 00:08:45,970
Verde deliberadamente, porque
el só me sentín mellor.

254
00:08:45,970 --> 00:08:49,790
En teoría, o algoritmo, cando fixemos
co libro de teléfono, cando fixemos

255
00:08:49,790 --> 00:08:52,420
convosco contando os uns aos outros, e
no segundo caso, cando só Jennifer

256
00:08:52,420 --> 00:08:55,250
fixen iso aquí enriba, que era unha especie
de fundamentalmente mellor.

257
00:08:55,250 --> 00:08:57,180
Porque non foi só dúas veces máis rápido.

258
00:08:57,180 --> 00:08:58,870
Non era ata catro veces máis rápido.

259
00:08:58,870 --> 00:09:03,290
Foi totalmente dependente do que a
tamaño da entrada foi, de cantas

260
00:09:03,290 --> 00:09:05,220
pasos que finalmente levou.

261
00:09:05,220 --> 00:09:08,040
>> E así esta idea simple que todos tomamos
adquirido co libro de teléfono,

262
00:09:08,040 --> 00:09:10,200
semellante pode ser aplicado
para algo así.

263
00:09:10,200 --> 00:09:12,380
E iso pode ser máis informal
coñecida como, como pode

264
00:09:12,380 --> 00:09:13,940
imaxinar, dividir e conquistar.

265
00:09:13,940 --> 00:09:16,390
Non ao contrario do que fixemos, claro,
co libro de teléfono.

266
00:09:16,390 --> 00:09:18,300
>> Pero o pseudocódigo, aviso, foi iso.

267
00:09:18,300 --> 00:09:21,800
Polo tanto, non imos facelo de novo, pero recordar
esta primeira semana, todos nós se levantou

268
00:09:21,800 --> 00:09:25,140
e logo, a metade do que sentou-se, a metade dos
que sentou-se, a metade do que sentou.

269
00:09:25,140 --> 00:09:29,280
Este algoritmo implementado nun
pouco de unha forma de trapaça, en que, el

270
00:09:29,280 --> 00:09:32,870
Non foi só unha das me contando,
fundamentalmente, de forma máis eficiente.

271
00:09:32,870 --> 00:09:35,830
Nese caso, eu estaba panca
unha característica secundaria.

272
00:09:35,830 --> 00:09:39,470
Máis ou menos, CPUs múltiple, cerebros,
varias persoas intelixentes no

273
00:09:39,470 --> 00:09:42,740
sala estaban me axudando a comezar a partir de algo
lineal para algo

274
00:09:42,740 --> 00:09:45,190
logarítmica, de algo
vermello para algo verde.

275
00:09:45,190 --> 00:09:48,650
>> Pero, neste caso, Jennifer só pode
fundamentalmente mellorar a

276
00:09:48,650 --> 00:09:52,370
desempeño do seu primeiro algoritmo,
unha vez máis, só de pensar un pouco máis.

277
00:09:52,370 --> 00:09:56,650
E agora, cando chega a hora de aplicar
isto, descubrir

278
00:09:56,650 --> 00:10:00,670
que as liñas de código que se pode escribir como
que se pode repetir-los de novo, e

279
00:10:00,670 --> 00:10:03,350
de novo, e de novo, unha especie de
nunha forma de looping.

280
00:10:03,350 --> 00:10:06,370
Porque non vai ter a
luxo, como Jennifer fixo nun primeiro momento, a

281
00:10:06,370 --> 00:10:10,460
só ten unha morea de IFS e dicir:
hmm, se este primeiro número é 4,

282
00:10:10,460 --> 00:10:11,800
déixeme ir todo o camiño ata o final.

283
00:10:11,800 --> 00:10:14,180
Ooh, se ese número é moi grande,
déixeme pasar cara atrás de forma arbitraria

284
00:10:14,180 --> 00:10:15,220
ao segundo elemento.

285
00:10:15,220 --> 00:10:18,210
Verá que vai ser moi
máis difícil de formalizar o que nós, seres humanos

286
00:10:18,210 --> 00:10:21,270
tomar para concedida como moi razoable
heurística, pero un ordenador é só

287
00:10:21,270 --> 00:10:23,260
vai facer o que diga a el para facer.

288
00:10:23,260 --> 00:10:25,280
>> Agora, isto ten moi interesante
implicacións.

289
00:10:25,280 --> 00:10:29,950
Esta gráfica é unha especie de significado para clasificar de
sobrecargar visualmente, aínda que o aviso previo, onde

290
00:10:29,950 --> 00:10:32,230
é a recta neste gráfico?

291
00:10:32,230 --> 00:10:35,330
Onde está o gráfico lineal
que chamamos n?

292
00:10:35,330 --> 00:10:37,580
Ben, é unha especie de para o fondo
da imaxe, non?

293
00:10:37,580 --> 00:10:40,500
Entón, todo o que fixemos é que teño a sorte de
zoom out para o eixo x ea

294
00:10:40,500 --> 00:10:44,780
eixo-y para tratar de obter unha noción do que
outros tipos de curvas parecen.

295
00:10:44,780 --> 00:10:47,760
>> E as particularidades da matemática
expresións, hoxe, non importa a

296
00:10:47,760 --> 00:10:52,440
moito, pero entender que hai unha gran cantidade de
algoritmos que son moito peores que

297
00:10:52,440 --> 00:10:53,470
algo que é lineal.

298
00:10:53,470 --> 00:10:55,410
En realidade, n cubos parece moi malo.

299
00:10:55,410 --> 00:10:58,400
2 ao n parece moi malo.
n ao cadrado parece moi malo.

300
00:10:58,400 --> 00:11:01,630
E imos ver o que algúns deses
se pode, na realidade de hoxe.

301
00:11:01,630 --> 00:11:05,430
E log n non se sente tan mal, pero
mellor que n é o rexistro de base 2 do n.

302
00:11:05,430 --> 00:11:08,080
Pero vostede sabe, el sería aínda
máis sorprendente se Jennifer, ou se,

303
00:11:08,080 --> 00:11:12,910
esta primeira semana, xurdiu con
algo que é rexistro de rexistro de n.

304
00:11:12,910 --> 00:11:15,880
>> Polo tanto, noutras palabras, non hai toda esta
gama de posibles solucións para

305
00:11:15,880 --> 00:11:18,570
problemas, pero, mesmo aquí, o aviso
o que vai ocorrer.

306
00:11:18,570 --> 00:11:22,910
Cando diminuír o zoom, cal destas curvas
vai probar ser o absoluto

307
00:11:22,910 --> 00:11:26,630
peor os que están na pantalla agora?

308
00:11:26,630 --> 00:11:28,680
Entón n cubos parece moi
mal no momento.

309
00:11:28,680 --> 00:11:32,470
Pero se diminuír o zoom para ver máis
xe eixo-y, que vai

310
00:11:32,470 --> 00:11:34,550
dominar en última instancia?

311
00:11:34,550 --> 00:11:37,120
Entón, el realmente se que 2 a
n, e pode descubrir que só por

312
00:11:37,120 --> 00:11:39,990
conectar nalgún cada vez maior
números, e verás que 2 ao

313
00:11:39,990 --> 00:11:42,070
n, de feito, moito máis rápido se fai maior.

314
00:11:42,070 --> 00:11:45,530
Se realmente diminuír o zoom, a 2 ao
n algoritmo absolutamente unha merda.

315
00:11:45,530 --> 00:11:48,170
Quero dicir que iso vai levar
un pouco de tempo para a

316
00:11:48,170 --> 00:11:49,460
ordenador para axitar completamente.

317
00:11:49,460 --> 00:11:52,500
>> Pero vai ver ao longo do tempo, sobre todo
con conxuntos de problemas futuros, e mesmo

318
00:11:52,500 --> 00:11:55,600
proxectos finais, e os seus datos
conxunto se fai grande, non?

319
00:11:55,600 --> 00:11:58,300
Mesmo na primeira versión de Facebook,
como o número de amigos, eo

320
00:11:58,300 --> 00:12:01,840
número de usuarios rexistrados ten gran
pode clasificar de teléfono-lo e

321
00:12:01,840 --> 00:12:05,530
aplicar algo con procura lineal,
ou unha clasificación moi sinxelo

322
00:12:05,530 --> 00:12:07,030
algoritmo, como veremos hoxe.

323
00:12:07,030 --> 00:12:09,280
Ten que comezar a pensar máis
e máis sobre estes problemas.

324
00:12:09,280 --> 00:12:12,070
E os tipos de problemas locais como
Facebook e Google e Microsoft,

325
00:12:12,070 --> 00:12:16,350
e outros, traballar é exactamente estes
tipo de datos gran tipo de preguntas

326
00:12:16,350 --> 00:12:18,530
cada vez máis nos días de hoxe.

327
00:12:18,530 --> 00:12:18,900
>> Todo ben.

328
00:12:18,900 --> 00:12:23,800
Así, o éxito de Jennifer, en que a segunda
algoritmo, a verdade, ela fixo incrible

329
00:12:23,800 --> 00:12:26,110
ben o primeiro tempo, pero imos
escribilo como sorte, para que

330
00:12:26,110 --> 00:12:27,000
pode facer neste momento.

331
00:12:27,000 --> 00:12:30,970
No segundo caso, ela panca un
algoritmo que repetiu de novo e

332
00:12:30,970 --> 00:12:34,670
de novo, pero ela levou para concedida unha
correcta suposición de que permitimos

333
00:12:34,670 --> 00:12:39,370
, Pero explotado algún detalle o
segunda vez que ela non ten o

334
00:12:39,370 --> 00:12:39,840
primeira vez.

335
00:12:39,840 --> 00:12:41,800
Que era o que?

336
00:12:41,800 --> 00:12:43,050
>> Que a lista foi clasificada.

337
00:12:43,050 --> 00:12:46,350
Así, logo que a lista foi resolto, nós
afirman que Jennifer era capaz de facer

338
00:12:46,350 --> 00:12:47,480
fundamentalmente mellor.

339
00:12:47,480 --> 00:12:51,450
Sete portas, si, non é tan interesante,
pero creo que estamos 7.000.000 portas.

340
00:12:51,450 --> 00:12:54,080
Sesión de n está indo definitivamente
para realizar moi, moi

341
00:12:54,080 --> 00:12:55,610
máis rápido no longo prazo.

342
00:12:55,610 --> 00:12:58,880
Pero ela tiña que ter a
portas clasificadas para ela.

343
00:12:58,880 --> 00:13:02,320
Agora, eu tomei a liberdade de facer o que
con antelación na pantalla do ordenador

344
00:13:02,320 --> 00:13:05,160
aquí, pero creo que Jennifer
tiven que facelo soa?

345
00:13:05,160 --> 00:13:10,120
Supoñamos que as portas se trate
datos representados nunha base de datos, ou

346
00:13:10,120 --> 00:13:14,260
amigos rexistrados para Facebook, ou
todas as páxinas web en internet que

347
00:13:14,260 --> 00:13:16,880
varios sitios pode ter
ao índice ou investigación sobre.

348
00:13:16,880 --> 00:13:20,940
>> Supoña que acaba de ter un conxunto de datos en bruto
definir e se deixou para ti, ou para

349
00:13:20,940 --> 00:13:23,010
Jennifer facelo de selección?

350
00:13:23,010 --> 00:13:26,950
Que, ao contrario, esixe que nós respondemos
o tema, así como, canto tempo

351
00:13:26,950 --> 00:13:31,080
levaría Jennifer, ou mesmo de min,
para ordenar os números con antelación para

352
00:13:31,080 --> 00:13:32,680
que podería sacar proveito diso?

353
00:13:32,680 --> 00:13:32,880
Non?

354
00:13:32,880 --> 00:13:36,620
Porque a implicación, claro, é
se me leva moito tempo para clasificar

355
00:13:36,620 --> 00:13:40,800
as cifras, quen diaños lle importa que
pode atopar un número como 50 tan rápido,

356
00:13:40,800 --> 00:13:44,850
como no caso de Jennifer, máis de
esmagada a cantidade de tempo total

357
00:13:44,850 --> 00:13:46,920
tardou, clasificando as cousas con antelación?

358
00:13:46,920 --> 00:13:49,320
>> Entón, imos ver se a xente non pode
pintar a imaxe aquí.

359
00:13:49,320 --> 00:13:51,370
Eu teño unha morea máis estrés
esfera, se iso axuda

360
00:13:51,370 --> 00:13:52,270
romper o xeo aquí.

361
00:13:52,270 --> 00:13:55,690
E se non se importar, nós
precisa sete voluntarios -

362
00:13:55,690 --> 00:13:57,060
on, Aceptar.

363
00:13:57,060 --> 00:13:57,240
Guau.

364
00:13:57,240 --> 00:13:59,250
Entón, non ten que gastar
en lámpadas de mesa, ao parecer.

365
00:13:59,250 --> 00:13:59,690
Todo ben.

366
00:13:59,690 --> 00:14:01,530
Así como sobre vostedes dous diante.

367
00:14:01,530 --> 00:14:04,160
Que tal vostedes dous nas costas.

368
00:14:04,160 --> 00:14:04,870
Entón, iso é catro.

369
00:14:04,870 --> 00:14:09,890
Como sobre ti diante
cinco, seis e sete.

370
00:14:09,890 --> 00:14:10,320
Ben alí.

371
00:14:10,320 --> 00:14:13,260
O seu amigo está a apuntar para fóra,
co fin de obter o premio.

372
00:14:13,260 --> 00:14:13,700
>> Todo ben.

373
00:14:13,700 --> 00:14:14,410
Imos para arriba.

374
00:14:14,410 --> 00:14:17,120
E por que non telo
caras vén aquí.

375
00:14:17,120 --> 00:14:18,960
Vou darlle cada un número.

376
00:14:18,960 --> 00:14:22,150
E vai adiante e organizar-se
de forma idéntica ao que está

377
00:14:22,150 --> 00:14:25,180
representado na pantalla.

378
00:14:25,180 --> 00:14:26,530
>> [Interpondo voces]

379
00:14:26,530 --> 00:14:28,160
>> DAVID J. Malan: Oop, sorry.

380
00:14:28,160 --> 00:14:30,210
Bug

381
00:14:30,210 --> 00:14:32,180
Todo ben.

382
00:14:32,180 --> 00:14:32,750
Ben, aquí imos nós.

383
00:14:32,750 --> 00:14:34,180
Número cinco.

384
00:14:34,180 --> 00:14:35,136
Número seis.

385
00:14:35,136 --> 00:14:37,770
Un, dous, tres, catro,
cinco, seis, sete.

386
00:14:37,770 --> 00:14:39,410
Oh, iso é raro.

387
00:14:39,410 --> 00:14:41,210
>> COLUMNA 2: Vou coller un -.

388
00:14:41,210 --> 00:14:41,900
>> DAVID J. Malan: Bo negocio.

389
00:14:41,900 --> 00:14:43,130
Todo ben.

390
00:14:43,130 --> 00:14:44,611
Grazas por participar.

391
00:14:44,611 --> 00:14:47,200
>> [Aplausos]

392
00:14:47,200 --> 00:14:48,580
>> Aceptar.

393
00:14:48,580 --> 00:14:48,860
Todo ben.

394
00:14:48,860 --> 00:14:51,970
Polo tanto, temos catro, dous, seis,
un, tres, sete, cinco.

395
00:14:51,970 --> 00:14:56,010
Mellorar iso temos sete voluntarios
aquí que son iguais á anchura do

396
00:14:56,010 --> 00:14:57,430
matriz que estamos xogando
co anterior.

397
00:14:57,430 --> 00:14:59,470
E eu escollín sete por razóns
que será só

398
00:14:59,470 --> 00:15:00,840
conveniente un pouco.

399
00:15:00,840 --> 00:15:04,400
E eu vou propor por primeira vez que
nós clasificar estes sete voluntarios.

400
00:15:04,400 --> 00:15:06,786
Se quere, en primeiro lugar,
para dicir Ola aínda.

401
00:15:06,786 --> 00:15:08,970
Xa que este será un
embaraçosas varios minutos.

402
00:15:08,970 --> 00:15:10,370
Apresente-se.

403
00:15:10,370 --> 00:15:10,980
>> GRACE: Ola, eu son Grace.

404
00:15:10,980 --> 00:15:14,190
Eu son un estudante de segundo ano en Leverett House.

405
00:15:14,190 --> 00:15:14,620
>> Branson: Hi

406
00:15:14,620 --> 00:15:15,620
Estou Branson.

407
00:15:15,620 --> 00:15:16,920
Eu son un calouro na Weld.

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> Gabe: Oi

410
00:15:20,230 --> 00:15:21,040
Estou Gabe.

411
00:15:21,040 --> 00:15:22,300
Eu son un Júnior na Cabot.

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> NEIL: Eu son Neil.

414
00:15:25,980 --> 00:15:29,090
Eu son un calouro na Matthews.

415
00:15:29,090 --> 00:15:29,550
>> Jason: Eu son Jason.

416
00:15:29,550 --> 00:15:32,816
Eu son un calouro na Greenough.

417
00:15:32,816 --> 00:15:33,700
>> MIKE: Eu son Mike.

418
00:15:33,700 --> 00:15:37,360
Eu son un calouro na Grays.

419
00:15:37,360 --> 00:15:37,990
>> Jess: Eu son Jess.

420
00:15:37,990 --> 00:15:40,313
Eu son un estudante de segundo ano en Leverett.

421
00:15:40,313 --> 00:15:41,300
>> DAVID J. Malan: Excelente.

422
00:15:41,300 --> 00:15:41,850
Todo ben.

423
00:15:41,850 --> 00:15:44,190
Ben, grazas a todos os nosos
voluntarios aquí ata agora.

424
00:15:44,190 --> 00:15:47,110
E o reto na man agora vai
ser a de clasificar estes faces, pero, a continuación,

425
00:15:47,110 --> 00:15:50,250
imos ter que pensar un pouco
moito sobre como realmente eficiente

426
00:15:50,250 --> 00:15:51,110
clasificou.

427
00:15:51,110 --> 00:15:52,580
Entón, imos primeiro tentar iso.

428
00:15:52,580 --> 00:15:55,970
Podedes ver os números uns dos outros
só por poñer en torno aos cantos.

429
00:15:55,970 --> 00:15:59,380
Dalle levar varios segundos, e
tipo-vos do menor na

430
00:15:59,380 --> 00:16:01,240
esquerda a maior da dereita.

431
00:16:01,240 --> 00:16:02,490
Ir

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> Aceptar.

434
00:16:07,530 --> 00:16:08,030
Bo

435
00:16:08,030 --> 00:16:09,370
Iso foi moi danado rápido.

436
00:16:09,370 --> 00:16:14,040
Agora, alguén aquí, cal foi o algoritmo
que estes faces aplicada?

437
00:16:14,040 --> 00:16:14,900
>> COLUMNA 1: Polo menos a máis grande.

438
00:16:14,900 --> 00:16:15,000
>> DAVID J. Malan: Aceptar.

439
00:16:15,000 --> 00:16:18,070
Polo menos a máis grande é realmente unha especie de
obxectivo, pero eu non estou seguro que é

440
00:16:18,070 --> 00:16:18,890
realmente un algoritmo.

441
00:16:18,890 --> 00:16:21,810
Polo menos a maior non di
me paso a paso o que facer.

442
00:16:21,810 --> 00:16:22,833
Si?

443
00:16:22,833 --> 00:16:24,083
>> COLUMNA 1: [inaudível]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> DAVID J. Malan: Aceptar.

446
00:16:26,280 --> 00:16:28,920
Entón, se ve unha persoa menor que
seu número, entón moverse para

447
00:16:28,920 --> 00:16:29,680
o dereito deles.

448
00:16:29,680 --> 00:16:32,800
Así que agora está quedando cada vez máis significativo,
máis como un algoritmo, porque

449
00:16:32,800 --> 00:16:35,410
pódese dicir, se iso, entón aquilo.

450
00:16:35,410 --> 00:16:37,050
Entón temos algún tipo de
construción condicional.

451
00:16:37,050 --> 00:16:39,700
E eses caras parecían facer que algúns
veces, porque algúns de vós cambiaron un pouco

452
00:16:39,700 --> 00:16:40,420
dunha distancia.

453
00:16:40,420 --> 00:16:43,410
Entón, houbo presuntamente algún tipo de
Looping suceder nas súas mentes.

454
00:16:43,410 --> 00:16:44,610
>> Pero imos intentar formalizar isto.

455
00:16:44,610 --> 00:16:47,540
Se vós puidesen recuperar
a este arranxo.

456
00:16:47,540 --> 00:16:50,650
A ver se non podemos formalizar esta unha
pouco, e, a continuación, facer a pregunta, só

457
00:16:50,650 --> 00:16:51,580
quão eficiente é esa?

458
00:16:51,580 --> 00:16:54,220
Claro que, cando facemos iso de forma máis lenta,
vai se sentir tan ben de

459
00:16:54,220 --> 00:16:57,210
un algoritmo, pero imos ver se podemos
poñer os dedos sobre os pasos precisos.

460
00:16:57,210 --> 00:16:58,670
>> Entón, vostedes dous son catro e dous.

461
00:16:58,670 --> 00:17:01,020
Ou orde correcta ou incorrecta?

462
00:17:01,020 --> 00:17:01,900
Obviamente incorrecta.

463
00:17:01,900 --> 00:17:02,710
Entón nós trocamos.

464
00:17:02,710 --> 00:17:05,170
Agora estou indo a mover de lado
aquí e dicir: 4-6.

465
00:17:05,170 --> 00:17:06,240
Está correcta ou incorrecta?

466
00:17:06,240 --> 00:17:06,599
>> Gabe: Correcto.

467
00:17:06,599 --> 00:17:07,180
>> DAVID J. Malan: Correcto.

468
00:17:07,180 --> 00:17:08,300
Seis e un?

469
00:17:08,300 --> 00:17:08,609
Non.

470
00:17:08,609 --> 00:17:09,630
Intercambia.

471
00:17:09,630 --> 00:17:10,490
Entón, iso é dous swaps.

472
00:17:10,490 --> 00:17:11,710
Seis e tres anos?

473
00:17:11,710 --> 00:17:11,980
Non.

474
00:17:11,980 --> 00:17:13,000
Intercambia.

475
00:17:13,000 --> 00:17:13,930
Seis e sete?

476
00:17:13,930 --> 00:17:14,630
Parece bo.

477
00:17:14,630 --> 00:17:15,396
Sete e cinco?

478
00:17:15,396 --> 00:17:16,150
>> Jess: [inaudível]

479
00:17:16,150 --> 00:17:17,089
>> DAVID J. Malan: OK, troque.

480
00:17:17,089 --> 00:17:19,770
E clasificados.

481
00:17:19,770 --> 00:17:19,980
Todo ben.

482
00:17:19,980 --> 00:17:21,440
Entón, obviamente, non, non?

483
00:17:21,440 --> 00:17:22,470
Entón alí estaba máis a suceder.

484
00:17:22,470 --> 00:17:24,920
Pero, en realidade, eses faces, aínda
só instintivamente.

485
00:17:24,920 --> 00:17:25,450
continuou movendo.

486
00:17:25,450 --> 00:17:27,710
Eles non parar, xa que
corrixido un problema.

487
00:17:27,710 --> 00:17:27,839
Así.

488
00:17:27,839 --> 00:17:29,390
En realidade, eu vou ter
para facer o mesmo.

489
00:17:29,390 --> 00:17:32,720
Vou ter a sorte de retroceder cara atrás
para o inicio deste problema,

490
00:17:32,720 --> 00:17:35,630
ou no inicio da presente de matriz
persoal, imos comezar a chamalos.

491
00:17:35,630 --> 00:17:38,366
>> E agora, o que debe o meu algoritmo
na segunda pasaxe será?

492
00:17:38,366 --> 00:17:39,220
>> COLUMNA 1: o mesmo.

493
00:17:39,220 --> 00:17:39,940
>> DAVID J. Malan: Mesma cousa.

494
00:17:39,940 --> 00:17:41,460
E iso, eu estou empezando a gustar, non?

495
00:17:41,460 --> 00:17:44,720
Así que pode atopar-se facendo
o mesmo unha e outra vez, iso é

496
00:17:44,720 --> 00:17:47,890
tornándose máis como un algoritmo,
instinto e menos humana.

497
00:17:47,890 --> 00:17:48,680
>> Entón, agora, aquí imos nós de novo.

498
00:17:48,680 --> 00:17:49,870
Dous e catro?

499
00:17:49,870 --> 00:17:50,220
Non

500
00:17:50,220 --> 00:17:51,050
Catro e un?

501
00:17:51,050 --> 00:17:53,380
Ah, houbo de feito algunhas
traballo aínda por facer.

502
00:17:53,380 --> 00:17:53,620
Por e tres?

503
00:17:53,620 --> 00:17:54,572
Bo

504
00:17:54,572 --> 00:17:56,000
Catro e seis?

505
00:17:56,000 --> 00:17:58,380
Seis e cinco?

506
00:17:58,380 --> 00:17:59,470
Seis e sete?

507
00:17:59,470 --> 00:18:00,970
OK, agora, feito.

508
00:18:00,970 --> 00:18:01,550
OK, non.

509
00:18:01,550 --> 00:18:02,710
Teño que volver.

510
00:18:02,710 --> 00:18:05,130
>> Entón, agora, unha vez máis, estamos a facer iso
algo máis deliberadamente.

511
00:18:05,130 --> 00:18:08,700
E agora, hai só un cerebro
executar este algoritmo.

512
00:18:08,700 --> 00:18:10,290
Unha CPU, se quere.

513
00:18:10,290 --> 00:18:13,090
E, francamente, este é o único recurso
imos ter acceso.

514
00:18:13,090 --> 00:18:16,280
E unha vez que voltar a un teclado
e ter algo así como C no noso

515
00:18:16,280 --> 00:18:19,600
disposición, estamos só escribindo un programa
que pode facer unha cousa de cada vez.

516
00:18:19,600 --> 00:18:22,900
Considerando que, estes faces hai un momento, nos
panca a súa intelixencia colectiva

517
00:18:22,900 --> 00:18:24,180
como vostedes fixeron a semana cero.

518
00:18:24,180 --> 00:18:24,980
Entón, imos seguir facendo iso.

519
00:18:24,980 --> 00:18:26,260
>> Dous e un.

520
00:18:26,260 --> 00:18:26,945
Dous e tres.

521
00:18:26,945 --> 00:18:27,460
Tres e catro.

522
00:18:27,460 --> 00:18:28,310
Catro e cinco.

523
00:18:28,310 --> 00:18:28,620
Cinco e seis.

524
00:18:28,620 --> 00:18:30,510
Seis e sete.

525
00:18:30,510 --> 00:18:31,880
Feito?

526
00:18:31,880 --> 00:18:34,560
Entón, eu estou, pero deixe-me xogar
avogado do diaño.

527
00:18:34,560 --> 00:18:37,950
Eu, o tipo de ordenador que só
fixo un pase por este conxunto de

528
00:18:37,950 --> 00:18:40,225
persoas, sabe que eu son feito?

529
00:18:40,225 --> 00:18:40,670
>> COLUMNA 1: Non

530
00:18:40,670 --> 00:18:41,050
>> DAVID J. Malan: Entón por que?

531
00:18:41,050 --> 00:18:46,900
O que eu teño que facer, a fin de
completar decisivamente que estou facendo?

532
00:18:46,900 --> 00:18:48,230
Probablemente unha pasaxe.

533
00:18:48,230 --> 00:18:48,430
Non?

534
00:18:48,430 --> 00:18:51,760
Por todo o que sei de que anterior
pase é que resolve un erro.

535
00:18:51,760 --> 00:18:53,920
E isto significa, é posible que haxa
aínda outro erro

536
00:18:53,920 --> 00:18:54,840
que eu teño corrixir.

537
00:18:54,840 --> 00:18:58,680
Entón eu só podo estar seguro de rebobinagem, e
logo, alomenos, 1-2, e dous

538
00:18:58,680 --> 00:19:00,940
tres, tres e catro, catro e cinco,
cinco e seis, seis e sete.

539
00:19:00,940 --> 00:19:02,510
OK, agora eu fixen ningún traballo.

540
00:19:02,510 --> 00:19:05,990
>> Podo certamente me lembro que fixen non
traballar con algo así como unha variable,

541
00:19:05,990 --> 00:19:06,975
como un int.

542
00:19:06,975 --> 00:19:12,490
Chamalo swaps, e swaps é 0 xa que eu
chegar ata aquí, e empezou a 0, entón

543
00:19:12,490 --> 00:19:15,520
Quere só de ser estúpido para continuar
adiante e cara atrás, comprobando de novo, e

544
00:19:15,520 --> 00:19:16,450
de novo, e de novo, non?

545
00:19:16,450 --> 00:19:18,450
Porque queda preso en algún
especie de loop infinito.

546
00:19:18,450 --> 00:19:21,250
Así, logo que hai 0 swaps,
podemos afirmar que esta

547
00:19:21,250 --> 00:19:23,810
algoritmo é realmente completa.

548
00:19:23,810 --> 00:19:25,400
>> Agora, imos poñer un nome sobre o tema.

549
00:19:25,400 --> 00:19:28,930
O algoritmo que propoño nós só
aplicado é unha cousa chamada burbulla

550
00:19:28,930 --> 00:19:32,800
tipo, coñecida como tal na medida en que
os números que son maiores do tipo de

551
00:19:32,800 --> 00:19:37,990
burbulla seu camiño ata o cumio, ou
para o fin da serie de números.

552
00:19:37,990 --> 00:19:40,270
Pero quão eficaz foi ese algoritmo?

553
00:19:40,270 --> 00:19:44,600
Cantos pasos que teño físicamente para
ter, por exemplo, para clasificar estas

554
00:19:44,600 --> 00:19:45,850
sete seres humanos?

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> De catro a cinco anos?

557
00:19:49,550 --> 00:19:51,420
OK, moitos é en última instancia
será a resposta.

558
00:19:51,420 --> 00:19:54,960
Pero, aínda así, o número específico
non é tan interesante.

559
00:19:54,960 --> 00:19:56,670
Imos xeneralizar como n.

560
00:19:56,670 --> 00:20:00,520
Entón, se eu tivese n persoas aquí enriba, e
foron, dalgún xeito, en orde aleatoria no

561
00:20:00,520 --> 00:20:02,180
comezando, en que orde orixinal.

562
00:20:02,180 --> 00:20:04,910
Ben, cantos pasos eu tiña
para asumir a primeira paso?

563
00:20:04,910 --> 00:20:09,810
Era un, dous, tres, catro, cinco,
seis, e son sete persoas, de xeito

564
00:20:09,810 --> 00:20:13,670
que é sete, seis -, de xeito que non
menos os pasos dunha primeira vez.

565
00:20:13,670 --> 00:20:16,280
>> Agora, cantos pasos eu tiña
tomando cando rebobinado?

566
00:20:16,280 --> 00:20:19,310
Ben, poderíamos dobrar este se
Nós realmente queriamos, pero por agora, estou

567
00:20:19,310 --> 00:20:22,300
só vou dicir, todo ben,
outro n menos 1.

568
00:20:22,300 --> 00:20:25,240
Así, o n menos un se ve
irritante para seguir, así que imos

569
00:20:25,240 --> 00:20:26,400
só redondear lixeiramente.

570
00:20:26,400 --> 00:20:27,770
Entón 2n pasos.

571
00:20:27,770 --> 00:20:29,310
Entón, 14 etapas, máis ou menos.

572
00:20:29,310 --> 00:20:31,930
>> Cantas veces eu tomo
un paso da seguinte visita?

573
00:20:31,930 --> 00:20:33,740
Ben, é 3N.

574
00:20:33,740 --> 00:20:34,510
realmente.

575
00:20:34,510 --> 00:20:37,920
E agora, no peor dos casos, por
exemplo, cantas veces eu tería

576
00:20:37,920 --> 00:20:41,730
ir para atrás e cara adiante, cara atrás e cara adiante,
executar este algoritmo, cambiando

577
00:20:41,730 --> 00:20:44,620
persoas en cada paso, máis ou menos?

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
Realmente n ao cadrado, non?

580
00:20:50,010 --> 00:20:53,000
>> Porque, no peor dos casos, pode tipo
de pensar sobre iso de forma intuitiva,

581
00:20:53,000 --> 00:20:54,800
aínda que levar un pouco
pouco de tempo para afundir-se dentro

582
00:20:54,800 --> 00:20:57,590
No peor dos casos, o que sería iso
sete persoas parecía, en

583
00:20:57,590 --> 00:21:00,230
termos do acordo
dos seus números?

584
00:21:00,230 --> 00:21:01,460
Totalmente para atrás, non?

585
00:21:01,460 --> 00:21:02,815
E só para simular que,
cal era o seu nome?

586
00:21:02,815 --> 00:21:03,360
>> MIKE: Mike.

587
00:21:03,360 --> 00:21:03,640
>> DAVID J. Malan: Mike?

588
00:21:03,640 --> 00:21:08,100
OK, Mike, pode simplemente engadir-me ao longo
aquí por só un segundo?

589
00:21:08,100 --> 00:21:08,880
En realidade, non.

590
00:21:08,880 --> 00:21:10,150
Sentímolo Mike, imos retroceder.

591
00:21:10,150 --> 00:21:10,910
Cal é o seu nome?

592
00:21:10,910 --> 00:21:11,180
>> NEIL: Neil.

593
00:21:11,180 --> 00:21:11,640
>> DAVID J. Malan: Neil.

594
00:21:11,640 --> 00:21:13,750
OK, Neil, que vén con
me, se non lle importa.

595
00:21:13,750 --> 00:21:17,150
Entón eu vou propoñer, só para
simplicidade, que Neil está agora no seu

596
00:21:17,150 --> 00:21:18,510
peor caso posible.

597
00:21:18,510 --> 00:21:20,720
Pero lembre-se como eu apliquei
meu algoritmo.

598
00:21:20,720 --> 00:21:24,530
Estou comparando, comparando, comparando,
comparando, comparando, oh.

599
00:21:24,530 --> 00:21:26,640
Agora, estes faces están fóra
de orde, así que eu resolver.

600
00:21:26,640 --> 00:21:27,980
Entón vós trocar.

601
00:21:27,980 --> 00:21:31,630
Pero considere agora, canto máis lonxe
Neil Non ten que ir?

602
00:21:31,630 --> 00:21:32,690
É máis ou menos n.

603
00:21:32,690 --> 00:21:33,570
Vostede sabe, non é, en realidade, n.

604
00:21:33,570 --> 00:21:36,040
É como se, n menos 1, pero estou quedando
irritado manter o control do pequeno

605
00:21:36,040 --> 00:21:37,550
número, entón imos chamalo de n.

606
00:21:37,550 --> 00:21:42,860
>> Entón, se Neil move un paso máximo de cada
tempo, e para desprazarse Neil un paso,

607
00:21:42,860 --> 00:21:46,580
Eu teño que facer este paso realmente tedioso
e cara atrás, é dicir máis ou menos

608
00:21:46,580 --> 00:21:52,080
Facendo isto, n pasos, dun total de n veces,
porque me vai levar

609
00:21:52,080 --> 00:21:55,820
que moitos pasos para chegar Neil todo
o camiño cara a onde el pertence.

610
00:21:55,820 --> 00:21:58,620
Deixade todo o mundo se vostedes
foron todos mis-ordenada, ben.

611
00:21:58,620 --> 00:22:01,100
>> Entón, imos chamar bubble sort n ao cadrado.

612
00:22:01,100 --> 00:22:04,860
O tempo de execución deste algoritmo, o
desempeño deste algoritmo, o

613
00:22:04,860 --> 00:22:07,120
eficiencia deste algoritmo,
imos só describir máis

614
00:22:07,120 --> 00:22:08,800
xeralmente como n ao cadrado.

615
00:22:08,800 --> 00:22:11,650
Que é bo, porque eu podería facer o
mesmo exemplo, con oito persoas, nove

616
00:22:11,650 --> 00:22:15,450
persoas, un millón de persoas, e iso
resposta non vai cambiar.

617
00:22:15,450 --> 00:22:18,870
>> Entón, se vostedes non lle importaría, imos
axustar-lo para onde comezou.

618
00:22:18,870 --> 00:22:22,510
E imos tratar outras dúas enfoques e
ver se non podemos facer fundamentalmente

619
00:22:22,510 --> 00:22:23,820
mellor que este.

620
00:22:23,820 --> 00:22:27,130
Entón, esta vez, vou propoñer
unha especie de algoritmo diferente.

621
00:22:27,130 --> 00:22:29,950
Iso foi moi intelixente de nós a última vez,
e vostedes estaban certos de ter a

622
00:22:29,950 --> 00:22:32,470
instintos seguros de só unha especie
de intercambio de parellas.

623
00:22:32,470 --> 00:22:36,500
Pero se realmente quería abordar este
simplemente, e meu obxectivo é mover-se

624
00:22:36,500 --> 00:22:39,800
todos os números de pequenos deste xeito, e
empurrar todos os grandes números que

625
00:22:39,800 --> 00:22:43,030
Así, por que non podo facer iso só no
máis inxenua maneira posible e ver se eu

626
00:22:43,030 --> 00:22:45,730
pode facer mellor que o que era un
algoritmo bastante complexo?

627
00:22:45,730 --> 00:22:46,620
>> Entón imos ver.

628
00:22:46,620 --> 00:22:48,940
Catro é un número moi pequeno, polo que estou
vai deixar lo alí momento.

629
00:22:48,940 --> 00:22:50,610
Ooh, o número dous é aínda mellor.

630
00:22:50,610 --> 00:22:52,230
Entón podes só un paso adiante
por un momento?

631
00:22:52,230 --> 00:22:55,670
Este é actualmente o meu menor numerado
solicitante, e eu vou lembrar

632
00:22:55,670 --> 00:22:57,000
que con, tipo, unha variable.

633
00:22:57,000 --> 00:22:57,930
Pero eu vou manter a verificación.

634
00:22:57,930 --> 00:22:59,890
Hai alguén cuxa
número é menor?

635
00:22:59,890 --> 00:23:00,460
Seis, non.

636
00:23:00,460 --> 00:23:01,390
Oh, hai Neil novo.

637
00:23:01,390 --> 00:23:04,050
>> Entón eu vou empurra-lo de volta
tipo de conceptualmente.

638
00:23:04,050 --> 00:23:05,120
Neil virá para adiante.

639
00:23:05,120 --> 00:23:08,440
E agora, a variable que eu estou a usar para
seguir o que ten o menor

640
00:23:08,440 --> 00:23:11,390
número é actualizado para conter
Localización de Neil.

641
00:23:11,390 --> 00:23:12,110
Ben, imos ver.

642
00:23:12,110 --> 00:23:13,960
Tres, sete, cinco.

643
00:23:13,960 --> 00:23:15,590
OK, sei que Neil era menor.

644
00:23:15,590 --> 00:23:18,110
Cal é a cousa máis sinxela
para eu facer agora?

645
00:23:18,110 --> 00:23:21,410
Non vou perder o meu tempo por só
Neil burbulla un lugar cara á esquerda.

646
00:23:21,410 --> 00:23:25,350
Por que non podo simplemente poñer Neil onde
pertence, o que é, por suposto, onde?

647
00:23:25,350 --> 00:23:26,160
>> Todo o camiño no inicio.

648
00:23:26,160 --> 00:23:27,720
Entón Neil, veña comigo.

649
00:23:27,720 --> 00:23:28,910
E cal era o seu nome?

650
00:23:28,910 --> 00:23:29,310
>> GRACE: Grace.

651
00:23:29,310 --> 00:23:29,710
>> DAVID J. Malan: Grace.

652
00:23:29,710 --> 00:23:29,920
Aceptar.

653
00:23:29,920 --> 00:23:32,490
Entón, Graza, por desgraza, está
tipo de no camiño.

654
00:23:32,490 --> 00:23:34,290
Entón, como imos solucionar este problema?

655
00:23:34,290 --> 00:23:34,490
Non?

656
00:23:34,490 --> 00:23:37,500
Se esta é unha matriz, non hai
só sete localidades.

657
00:23:37,500 --> 00:23:40,830
Lembre que, con Rob, falamos de
declarando as idades, e que só tiña un

658
00:23:40,830 --> 00:23:41,740
número finito de idades?

659
00:23:41,740 --> 00:23:42,535
A mesma idea aquí.

660
00:23:42,535 --> 00:23:44,300
Temos só un número finito de enteiros.

661
00:23:44,300 --> 00:23:47,590
Graza é unha especie de no noso
xeito, entón como é que imos resolver?

662
00:23:47,590 --> 00:23:49,555
>> O xeito máis sinxelo é así,
Graza, desculpe.

663
00:23:49,555 --> 00:23:51,870
Vai ter que pasar por riba de
alí para que poidamos facer o cuarto.

664
00:23:51,870 --> 00:23:55,290
Agora, se pensar sobre iso, é posible que
nós só empeorou o problema.

665
00:23:55,290 --> 00:23:58,510
E quizais nós fixemos, xa que o que se
Graza estaban no lugar seguro?

666
00:23:58,510 --> 00:24:01,730
Pero sabemos que non é porque
se non, ela sería

667
00:24:01,730 --> 00:24:03,980
pé á fronte en vez de
Neil neste momento, non?

668
00:24:03,980 --> 00:24:05,550
Xa checo o número para fóra.

669
00:24:05,550 --> 00:24:05,770
>> Todo ben.

670
00:24:05,770 --> 00:24:09,110
Entón, agora, Neil está no lugar seguro, e
Podo facer unha pequena optimización.

671
00:24:09,110 --> 00:24:11,740
Ao seguinte minuto, eu vou pasar por alto
Neil todos xuntos, co fin de non

672
00:24:11,740 --> 00:24:15,280
desperdiçar seu tempo, ou accidentalmente
troca-lo para o lugar incorrecto.

673
00:24:15,280 --> 00:24:17,805
Entón, agora, como fago para o seguinte
elemento que é menor?

674
00:24:17,805 --> 00:24:18,480
Dous.

675
00:24:18,480 --> 00:24:20,225
Isto é un número moi bo, se
quere dar un paso adiante e

676
00:24:20,225 --> 00:24:21,100
Vou lembrar de ti.

677
00:24:21,100 --> 00:24:21,980
Seis, non é bo.

678
00:24:21,980 --> 00:24:24,820
Catro, tres, sete, cinco, non é bo.

679
00:24:24,820 --> 00:24:26,800
Entón deixe-me leva-lo para
o seu lugar seguro.

680
00:24:26,800 --> 00:24:28,470
E nós só temos sorte esta vez.

681
00:24:28,470 --> 00:24:31,350
>> Agora, eu vou pasar por alto estes
dúas caras, e agora facer unha

682
00:24:31,350 --> 00:24:32,260
pasar por iso.

683
00:24:32,260 --> 00:24:33,490
Six, que un número moi pequeno.

684
00:24:33,490 --> 00:24:34,300
Imos adiante.

685
00:24:34,300 --> 00:24:35,220
Oh, desculpe.

686
00:24:35,220 --> 00:24:37,640
Número de Grace é mellor,
para pisar para adiante.

687
00:24:37,640 --> 00:24:38,260
Four.

688
00:24:38,260 --> 00:24:39,120
Sentímolo, Grace.

689
00:24:39,120 --> 00:24:39,950
Volver de novo.

690
00:24:39,950 --> 00:24:41,550
O número tres é mellor.

691
00:24:41,550 --> 00:24:42,290
Sete.

692
00:24:42,290 --> 00:24:42,720
Cinco.

693
00:24:42,720 --> 00:24:43,550
E agora, cal é o seu nome?

694
00:24:43,550 --> 00:24:44,000
>> Jason: Jason.

695
00:24:44,000 --> 00:24:44,420
>> DAVID J. Malan: Jason.

696
00:24:44,420 --> 00:24:47,050
Así Jason é agora menor
elemento que seleccionei.

697
00:24:47,050 --> 00:24:49,160
Onde está indo?

698
00:24:49,160 --> 00:24:50,380
Entón, onde seis é.

699
00:24:50,380 --> 00:24:51,210
E o seu nome é novo?

700
00:24:51,210 --> 00:24:51,710
>> Gabe: Gabe.

701
00:24:51,710 --> 00:24:52,340
>> DAVID J. Malan: Gabe.

702
00:24:52,340 --> 00:24:53,220
Gabe é o camiño.

703
00:24:53,220 --> 00:24:54,640
Cal é a cousa máis fácil de facer?

704
00:24:54,640 --> 00:24:58,390
Intercambia estes dous caras e continuar.

705
00:24:58,390 --> 00:24:59,020
Entón, agora imos ver.

706
00:24:59,020 --> 00:25:00,170
Quen é o máis pequeno?

707
00:25:00,170 --> 00:25:01,030
Four.

708
00:25:01,030 --> 00:25:01,990
Déixeme só un tipo de fraude.

709
00:25:01,990 --> 00:25:03,090
Cinco será menor.

710
00:25:03,090 --> 00:25:05,220
Creo que o próximo si, quere pisar
á fronte, o que eu teño que ver coa

711
00:25:05,220 --> 00:25:06,820
estes faces, con Gabe?

712
00:25:06,820 --> 00:25:08,450
Intercambia novo.

713
00:25:08,450 --> 00:25:10,740
Entón, agora, aínda un pouco fóra de orde.

714
00:25:10,740 --> 00:25:14,140
Eu atopei Gabe a ser menor, entón
Eu pop-lo, movelo máis caras.

715
00:25:14,140 --> 00:25:15,190
E feito.

716
00:25:15,190 --> 00:25:17,200
>> Así resposta é a mesma.

717
00:25:17,200 --> 00:25:18,600
O resultado final é o mesmo.

718
00:25:18,600 --> 00:25:22,730
Cal destes dous algoritmos
é mellor?

719
00:25:22,730 --> 00:25:23,500
A segunda, escoitei.

720
00:25:23,500 --> 00:25:24,252
Por que?

721
00:25:24,252 --> 00:25:25,900
>> COLUMNA 3: é n pasos [inaudível].

722
00:25:25,900 --> 00:25:27,600
>> DAVID J. Malan: É n pasos, como máximo.

723
00:25:27,600 --> 00:25:28,490
Interesante.

724
00:25:28,490 --> 00:25:30,610
Así é que?

725
00:25:30,610 --> 00:25:33,630
Así como eu atopar o
menor elemento?

726
00:25:33,630 --> 00:25:37,060
Cantos pasos que eu teño que tomar
a atopar o menor elemento?

727
00:25:37,060 --> 00:25:39,220
Eu tiña un ollar todo o camiño
ao final, non?

728
00:25:39,220 --> 00:25:41,530
Porque en que o peor caso, o que
Neil se foron por aquí?

729
00:25:41,530 --> 00:25:45,700
Entón, só tes que atopar o menor elemento
me n pasos, ou non menos 1 leva.

730
00:25:45,700 --> 00:25:46,100
Pero Aceptar.

731
00:25:46,100 --> 00:25:46,980
Entón resolver Neil.

732
00:25:46,980 --> 00:25:48,740
Lembre que, aproximadamente un minuto.

733
00:25:48,740 --> 00:25:51,680
>> Pero como é que o seguinte
menor elemento?

734
00:25:51,680 --> 00:25:54,830
É n menos 1, ou n menos 2 realmente,
a partir do número de pasos.

735
00:25:54,830 --> 00:25:55,440
Entón Aceptar.

736
00:25:55,440 --> 00:25:57,390
Entón eu fixen n menos 2.

737
00:25:57,390 --> 00:25:57,600
Todo ben.

738
00:25:57,600 --> 00:25:59,130
Así que se sente un pouco mellor.

739
00:25:59,130 --> 00:25:59,730
Todo ben.

740
00:25:59,730 --> 00:26:03,270
Cantos pasos a próxima vez
atopar o número tres?

741
00:26:03,270 --> 00:26:04,420
Así, n menos 4.

742
00:26:04,420 --> 00:26:07,670
Entón está diminuíndo, unha a menos
pisar en cada iteración.

743
00:26:07,670 --> 00:26:08,740
Polo tanto, este non se sentir mellor, non?

744
00:26:08,740 --> 00:26:13,450
Se a última vez que foi máis ou menos n veces n,
esta vez é menos n 1, máis n menos

745
00:26:13,450 --> 00:26:16,500
2, ademais de n menos 3, máis n
menos 4, punto, punto, punto.

746
00:26:16,500 --> 00:26:18,750
Pero se se lembra da súa escola
libros de texto, a pequena fraude

747
00:26:18,750 --> 00:26:24,380
folla na parte de atrás que ten fórmulas, se
sumar esta serie de números,

748
00:26:24,380 --> 00:26:31,280
que é o número total de pasos
será que eu levo aquí?

749
00:26:31,280 --> 00:26:36,580
>> Este é un destes, tipo, n menos
1, n veces, divididos por 2.

750
00:26:36,580 --> 00:26:39,040
Entón deixe-me ver se podo tirar
isto por só un momento.

751
00:26:39,040 --> 00:26:42,230
E de novo, eu son o tipo de redondeo algúns
números só para manter a nosa vida simple,

752
00:26:42,230 --> 00:26:47,830
pero se ben me lembra, é algo así como se
Eu n menos unha cousas, entón n menos

753
00:26:47,830 --> 00:26:53,570
2, entón n menos 3, é máis ou menos
algo parecido con iso máis de 2, e se eu

754
00:26:53,570 --> 00:26:55,510
multiplicar tanto, é
realmente praza n.

755
00:26:55,510 --> 00:26:58,940
Que non está sentindo moi ben.
n n menos dous.

756
00:26:58,940 --> 00:27:00,350
>> Pero aquí está a cousa.

757
00:27:00,350 --> 00:27:03,720
En ciencia da computación, cando os problemas
comezan a estar interesantes é cando n

758
00:27:03,720 --> 00:27:04,700
queda moi grande.

759
00:27:04,700 --> 00:27:08,110
E cando n queda moi grande, o que de
estes valores vai dominar todo

760
00:27:08,110 --> 00:27:09,750
dos outros?

761
00:27:09,750 --> 00:27:10,990
El é o tipo de n ao cadrado, non?

762
00:27:10,990 --> 00:27:13,340
Si, dividíndose por dous é moi bo.

763
00:27:13,340 --> 00:27:16,740
Pero se está a falar de millóns
de anacos de datos, ou billóns de

764
00:27:16,740 --> 00:27:18,700
anacos de datos, ok, entón
está dúas veces máis rápido.

765
00:27:18,700 --> 00:27:22,440
Pero quen realmente lle importa se ese gran número,
Se ese factor é o que recibe

766
00:27:22,440 --> 00:27:23,040
cada vez maior.

767
00:27:23,040 --> 00:27:25,990
E, por suposto, fai máis de
unha diferenza que este cara.

768
00:27:25,990 --> 00:27:29,120
Así, aínda que vostedes están certos, o
segundo algoritmo, imos chamalo

769
00:27:29,120 --> 00:27:32,970
selección de tipo, é, no mundo real, un
pouco máis rápido, potencialmente, porque eu son

770
00:27:32,970 --> 00:27:35,360
tomando cada vez menos
pasos de cada vez.

771
00:27:35,360 --> 00:27:37,340
>> Realmente non é fundamentalmente máis rápido.

772
00:27:37,340 --> 00:27:41,430
Porque se realmente xogar isto para
grandes valores de n, a finais do

773
00:27:41,430 --> 00:27:44,750
o día, grande abondo para n, aínda é
vai sentir-se moi lento.

774
00:27:44,750 --> 00:27:46,770
Ben, deixe-me tirar unha
último paso por aí.

775
00:27:46,770 --> 00:27:48,920
Iso é o que eu chamaría
selección especie.

776
00:27:48,920 --> 00:27:51,040
Podedes reiniciar-se
unha última vez?

777
00:27:51,040 --> 00:27:53,550
E neste último caso, eu vou
propoñer algo

778
00:27:53,550 --> 00:27:54,970
chamado ordenación por inserción.

779
00:27:54,970 --> 00:27:57,470
Ordenación por inserción ser, conceptualmente,
un pouco diferente.

780
00:27:57,470 --> 00:28:00,980
>> En vez de ir cara atrás e cara adiante e
seleccionar o menor elemento, eu son

781
00:28:00,980 --> 00:28:05,030
só indo para tratar con cada unha delas
caras como eu atopalos, e insira

782
00:28:05,030 --> 00:28:06,850
los no seu lugar correcto.

783
00:28:06,850 --> 00:28:10,160
Entón, eu só vou comezar con Graza,
e eu vexo que é o número catro.

784
00:28:10,160 --> 00:28:11,720
Onde é que o número catro pertence?

785
00:28:11,720 --> 00:28:14,940
Non comece nada de selección,
entón Grace comeza a estar alí.

786
00:28:14,940 --> 00:28:18,355
E agora vou reclamar, se puidese
dar un paso á dereita, este

787
00:28:18,355 --> 00:28:21,650
miña lista ordenada, esa é a miña
lista resto indiferenciados.

788
00:28:21,650 --> 00:28:23,260
Entón agora eu vou continuar a seguir,
e cal é o seu nome?

789
00:28:23,260 --> 00:28:23,700
>> Branson:.

790
00:28:23,700 --> 00:28:24,150
>> DAVID J. Malan: Branson.

791
00:28:24,150 --> 00:28:25,375
Entón Branson é o número dous.

792
00:28:25,375 --> 00:28:27,490
Entón, eu vou leva-lo
por un momento.

793
00:28:27,490 --> 00:28:30,940
E agora, onde pertence
neste array?

794
00:28:30,940 --> 00:28:32,360
Así, para o dereito de gracia.

795
00:28:32,360 --> 00:28:35,670
Entón, de novo, somos o tipo de facer
Graza facer unha chea de traballo aquí.

796
00:28:35,670 --> 00:28:37,290
Onde é que imos poñer-lo?

797
00:28:37,290 --> 00:28:40,120
Entón, nós estamos indo para desprazar-lo para o
á esquerda, e introducir Branson alí.

798
00:28:40,120 --> 00:28:41,680
Pero agora eu afirmo que
vostedes están feitos.

799
00:28:41,680 --> 00:28:43,240
Mais repare, eu non estou a usar o espazo extra.

800
00:28:43,240 --> 00:28:45,130
É aínda dous elementos
aquí, cinco alí.

801
00:28:45,130 --> 00:28:47,910
Tamaño total do conxunto é de 7, polo que estou
non enganar, todo ben?

802
00:28:47,910 --> 00:28:51,950
>> Polo tanto, agora temos, con Gabe aquí, o
número seis, onde pertence?

803
00:28:51,950 --> 00:28:52,650
Tivo sorte de novo.

804
00:28:52,650 --> 00:28:53,820
Entón, comeza a estar alí.

805
00:28:53,820 --> 00:28:57,210
Só un lixeiro paso cara á dereita
só para deixar claro que está clasificado.

806
00:28:57,210 --> 00:29:00,520
E agora temos Neil de novo, o número de
un, onde vai?

807
00:29:00,520 --> 00:29:03,540
E agora é o lugar onde nós imos comezar a ver que
este algoritmo, que en primeiro

808
00:29:03,540 --> 00:29:05,950
vista, séntese moi intelixente, asista
que está a piques de acontecer.

809
00:29:05,950 --> 00:29:07,370
Se puidese avanzar.

810
00:29:07,370 --> 00:29:09,260
>> Onde queremos poñer Neil?

811
00:29:09,260 --> 00:29:11,830
Entón, obviamente, aquí, así como
obtemos Neil alí?

812
00:29:11,830 --> 00:29:12,970
Imos facelo paso a paso.

813
00:29:12,970 --> 00:29:15,620
Gabe, onde ten que ir?

814
00:29:15,620 --> 00:29:19,590
Si, así que tomar un gran paso,
ou dúas medias-medidas para facer

815
00:29:19,590 --> 00:29:20,820
un paso por alí.

816
00:29:20,820 --> 00:29:21,750
Graza, onde vai?

817
00:29:21,750 --> 00:29:22,510
Bo

818
00:29:22,510 --> 00:29:23,500
Así, outra etapa.

819
00:29:23,500 --> 00:29:24,960
E, finalmente, Branson?

820
00:29:24,960 --> 00:29:25,460
Outro paso.

821
00:29:25,460 --> 00:29:27,190
E agora podemos poñer Neil no lugar.

822
00:29:27,190 --> 00:29:28,440
>> Entón, agora, seguir esa lóxica.

823
00:29:28,440 --> 00:29:32,420
Aínda que non están cambiando Neil
máis, e máis, e máis, para poñelas

824
00:29:32,420 --> 00:29:36,420
onde pasa, no peor caso, o
seguinte número podemos atopar podería

825
00:29:36,420 --> 00:29:42,220
ser o número, por exemplo, houbo un número
cero, entón imos cambiar todo

826
00:29:42,220 --> 00:29:42,730
estes faces.

827
00:29:42,730 --> 00:29:44,950
Supoñamos que hai un número negativo
un, entón temos que cambiar

828
00:29:44,950 --> 00:29:46,080
todos estes caras.

829
00:29:46,080 --> 00:29:48,500
Entón, nós estamos realmente só unha especie de inversión
o problema ao redor, de xeito que estamos

830
00:29:48,500 --> 00:29:52,620
transferir o gasto do
de xeito que o proceso de selección de inserción

831
00:29:52,620 --> 00:29:56,930
proceso, de xeito que vostedes só tiña
para mover uns n menos algo

832
00:29:56,930 --> 00:29:57,940
número de pasos.

833
00:29:57,940 --> 00:30:01,200
E ese número de pasos é só ir
aumentar a medida que eu escoller máis números,

834
00:30:01,200 --> 00:30:04,730
se eu tivera que estar empurrando vostedes
cara atrás, e volta, e volta.

835
00:30:04,730 --> 00:30:08,320
>> Entón, a cousa máis triste é agora todo isto
algoritmos son n ao cadrado.

836
00:30:08,320 --> 00:30:10,570
Imos adiante e, grazas a estes
caras, e visualiza-las un pouco

837
00:30:10,570 --> 00:30:11,090
diferente.

838
00:30:11,090 --> 00:30:12,312
Moi ben feito.

839
00:30:12,312 --> 00:30:14,120
>> [Aplausos]

840
00:30:14,120 --> 00:30:15,030
>> Todo ben.

841
00:30:15,030 --> 00:30:16,280
Alí vai.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Grazas por -

844
00:30:18,470 --> 00:30:19,190
>> Branson: [inaudível] manter os números.

845
00:30:19,190 --> 00:30:21,990
>> DAVID J. Malan: Non, pode
manter os números así.

846
00:30:21,990 --> 00:30:23,440
Todo ben.

847
00:30:23,440 --> 00:30:24,100
Ben feito.

848
00:30:24,100 --> 00:30:25,300
Todo ben.

849
00:30:25,300 --> 00:30:30,510
Entón imos ver se non podemos agora resumir
máis rápido e máis visual

850
00:30:30,510 --> 00:30:33,410
exactamente o que pasou
aquí como segue.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Eu estou indo a ir adiante
tire superior Firefox.

853
00:30:38,770 --> 00:30:41,310
Imos chamar esa demostración
na páxina web do curso.

854
00:30:41,310 --> 00:30:43,870
Java é un pouco aburrido para comezar a traballar
nalgúns navegadores estes días.

855
00:30:43,870 --> 00:30:46,760
Entón, se xogar con iso na casa,
entender que pode ter usar Firefox

856
00:30:46,760 --> 00:30:47,990
para facelo funcionar.

857
00:30:47,990 --> 00:30:50,440
E o que eu vou facer con este
demostración é o seguinte.

858
00:30:50,440 --> 00:30:54,875
>> No fondo, eu teño unha morea de
opcións de menú, incluíndo un comezo e un

859
00:30:54,875 --> 00:30:55,840
botón de parar.

860
00:30:55,840 --> 00:30:59,450
Ademais, como unha banda, parece haber un
erro nestes programas, no que

861
00:30:59,450 --> 00:31:03,720
non pode realmente ver o partido ou parada
botón, a menos que manteña Mando ou Alt

862
00:31:03,720 --> 00:31:06,560
máis e zoom in, que curiosamente
mostra máis botóns.

863
00:31:06,560 --> 00:31:09,090
Polo tanto, só FYI, se xogar
con iso na casa.

864
00:31:09,090 --> 00:31:12,870
Agora eu vou facer clic en Inicio, en só un
momento, despois dun atraso de especificar,

865
00:31:12,870 --> 00:31:16,810
como, a 200 milésimas de segundo aquí, só
para que poidamos ver o que acontece.

866
00:31:16,810 --> 00:31:20,180
>> Entón, eu afirmo que esta é unha vista
do primeiro algoritmo

867
00:31:20,180 --> 00:31:23,730
estes faces fixeron, bubble sort, no que
nós trocamos persoas por pares.

868
00:31:23,730 --> 00:31:27,490
O insight fundamental para esta visualización
é que a altura das barras

869
00:31:27,490 --> 00:31:30,510
representa o tamaño do número.

870
00:31:30,510 --> 00:31:32,210
Así, o máis alto do bar, o
Canto maior sexa o número.

871
00:31:32,210 --> 00:31:33,680
Máis curto da barra, menor o número.

872
00:31:33,680 --> 00:31:38,630
E se observar, estamos pasando por
a primeira iteración do algoritmo,

873
00:31:38,630 --> 00:31:42,620
cambio de pequenos e grandes números, de xeito que
o número pequeno ven en primeiro lugar e

874
00:31:42,620 --> 00:31:44,280
o gran número vai á dereita.

875
00:31:44,280 --> 00:31:48,770
>> E así chegamos ao final dun array
de moitos máis números que sete, estamos

876
00:31:48,770 --> 00:31:49,900
vai volver ao principio.

877
00:31:49,900 --> 00:31:51,140
E anticipar iso.

878
00:31:51,140 --> 00:31:54,860
Na extrema esquerda, que o rapaz está a suceder
para cambiar para o lado, e isto

879
00:31:54,860 --> 00:31:56,010
proceso se repite.

880
00:31:56,010 --> 00:31:59,450
Agora esa visualización fica rapidamente
aburrido, entón deixe-me ir adiante e deixar

881
00:31:59,450 --> 00:32:04,170
, Cambie o atraso algo moi
máis rápido só para comezar agora, unha sensación de

882
00:32:04,170 --> 00:32:05,060
este algoritmo.

883
00:32:05,060 --> 00:32:07,840
>> Así, aínda que eu aceleraba-se, este é
como actualizar meu procesador, a mercar

884
00:32:07,840 --> 00:32:08,580
un novo ordenador.

885
00:32:08,580 --> 00:32:12,980
Non cambiaron fundamentalmente a miña
algoritmo, pero realmente pode ver máis

886
00:32:12,980 --> 00:32:16,800
claramente do que cos humanos, que a gran
números están burbullas ata o cumio,

887
00:32:16,800 --> 00:32:20,900
e os números pequenos están burbulla
cara á parte inferior.

888
00:32:20,900 --> 00:32:22,390
E agora esta cousa aquí clasificados.

889
00:32:22,390 --> 00:32:25,260
E, como un aparte, nas prazas, hai
só algunhas Escrituração alí para

890
00:32:25,260 --> 00:32:28,010
axudar a contar cantas comparacións,
ou cantos swaps teñen

891
00:32:28,010 --> 00:32:28,950
realmente se fixo.

892
00:32:28,950 --> 00:32:30,750
>> Ben, imos tentar unha das
os outros que vimos.

893
00:32:30,750 --> 00:32:37,116
Déixeme prema o bubble sort aquí, e
déixeme escoller, e esta páxina enteira

894
00:32:37,116 --> 00:32:38,936
é un pouco buggy.

895
00:32:38,936 --> 00:32:41,155
Imos aceptar o risco
e executa-lo de novo.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Alí imos nós.

898
00:32:45,030 --> 00:32:47,180
Entón imos facer a selección tipo.

899
00:32:47,180 --> 00:32:49,140
Non sei por que o menú
aparece por alí.

900
00:32:49,140 --> 00:32:54,070
Imos zoom para solucionar isto
erro, cambiar isto para 50.

901
00:32:54,070 --> 00:32:56,020
Ah, imos realmente facer
moito máis rápido.

902
00:32:56,020 --> 00:32:59,160
Cinco milisegundos ou menos, e comezar.

903
00:32:59,160 --> 00:33:00,470
>> Polo tanto, esta é a selección de tipo.

904
00:33:00,470 --> 00:33:03,070
Entón, de novo, pensar sobre o que
fixo os seres humanos aquí.

905
00:33:03,070 --> 00:33:08,490
Nós fomos a través da matriz e seleccionados
o elemento máis pequeno, de novo,

906
00:33:08,490 --> 00:33:09,250
e de novo, e de novo.

907
00:33:09,250 --> 00:33:11,110
Agora eu afirmo que aínda era moi malo.

908
00:33:11,110 --> 00:33:15,010
Foi aínda n ao cadrado, máis ou menos,
pero foi, no mundo real, un pouco

909
00:33:15,010 --> 00:33:18,280
máis rápido, por que eu estaba realmente tomando
algo menos pasos de cada vez.

910
00:33:18,280 --> 00:33:19,800
Pero estamos só falando o que?

911
00:33:19,800 --> 00:33:21,830
Quizais 40 ou máis bares aquí?

912
00:33:21,830 --> 00:33:23,200
Non estamos a falar de 40 millóns.

913
00:33:23,200 --> 00:33:27,430
Polo tanto, non é totalmente claro para min que
era de feito unha ganancia significativo.

914
00:33:27,430 --> 00:33:32,530
>> Déixeme agora volver atrás e cambiar a nosa
terceiro algoritmo, que foi seleccionado

915
00:33:32,530 --> 00:33:33,180
ordenación por inserción.

916
00:33:33,180 --> 00:33:36,380
E agora é realmente de buggy, xa que o
menú non debería estar alí.

917
00:33:36,380 --> 00:33:40,840
Entón, agora imos rolar para atrás ata aquí
e iniciar este algoritmo.

918
00:33:40,840 --> 00:33:43,270
Whoopi, comezar e parar.

919
00:33:43,270 --> 00:33:47,160
Así, este tipo de ten un estándar moi
a ela, no que estamos unha vez máis

920
00:33:47,160 --> 00:33:50,240
inserindo os seres humanos, ou en
Neste caso, as barras en

921
00:33:50,240 --> 00:33:52,620
a súa situación axeitada.

922
00:33:52,620 --> 00:33:55,430
E el xa fixo antes
Eu me virei.

923
00:33:55,430 --> 00:33:58,940
Pero este, tamén, en teoría,
aínda n ao cadrado.

924
00:33:58,940 --> 00:34:01,430
>> Entón imos ver se non podemos resumir
estes como segue.

925
00:34:01,430 --> 00:34:04,750
Eu estou indo a ir adiante e só para dar
nós tipo de un xeito común de falar

926
00:34:04,750 --> 00:34:08,489
sobre isto, deixe-me presentar
só un pouco de notación aquí.

927
00:34:08,489 --> 00:34:12,480
Está a piques de ver unha cousa chamada gran
Ó, por que é, literalmente, unha gran

928
00:34:12,480 --> 00:34:16,320
O. e esta é unha forma que un ordenador
científico ou un matemático aínda usa

929
00:34:16,320 --> 00:34:19,230
para describir o tempo de execución
dun algoritmo.

930
00:34:19,230 --> 00:34:21,400
Cantos pasos realmente tomar?

931
00:34:21,400 --> 00:34:25,080
>> Agora eu vou avergoñar con
miña carta aquí en só un momento.

932
00:34:25,080 --> 00:34:29,020
Pero déixeme ir adiante e dicir que
iso vai ser gran por aquí ó.

933
00:34:29,020 --> 00:34:33,610
E deixe-me presentar outro
símbolo, un omega capital.

934
00:34:33,610 --> 00:34:37,080
Omega será o contrario,
esencialmente, de gran O. Considerando que a gran O

935
00:34:37,080 --> 00:34:40,790
significa, no peor dos casos, a cantidade de tempo
pode levar algún algoritmo, en

936
00:34:40,790 --> 00:34:43,480
termos de n, omega vai
ser canto tempo podería

937
00:34:43,480 --> 00:34:45,409
tomar no mellor dos casos.

938
00:34:45,409 --> 00:34:48,090
E imos ver o que se entende por
mellor dos casos, en só un momento.

939
00:34:48,090 --> 00:34:49,940
>> Entón, imos comezar algo sinxelo.

940
00:34:49,940 --> 00:34:54,719
Déixeme comezar por unha procura linear.

941
00:34:54,719 --> 00:34:55,679
Polo tanto, non a clasificación.

942
00:34:55,679 --> 00:34:58,000
Imos chamar esa procura lineal.

943
00:34:58,000 --> 00:35:01,140
E agora, facer un pouco de
mesa de fóra desa.

944
00:35:01,140 --> 00:35:06,600
E agora, no caso da investigación lineal,
no peor caso, cantos pasos se

945
00:35:06,600 --> 00:35:11,770
vai me levar para atopar unha
número de elección arbitraria?

946
00:35:11,770 --> 00:35:14,540
E hai n portas totais
ou n cifras totais.

947
00:35:14,540 --> 00:35:15,940
Peor caso.

948
00:35:15,940 --> 00:35:18,800
Cantos pasos vou ter que
tomar para atopar o número 50 en unha matriz

949
00:35:18,800 --> 00:35:20,830
de n portas?

950
00:35:20,830 --> 00:35:21,410
E por que?

951
00:35:21,410 --> 00:35:23,680
Porque pode ser o único
camiño para o final.

952
00:35:23,680 --> 00:35:27,120
Tanto como Jennifer atopa, o
número 50 foi todo o camiño, polo que,

953
00:35:27,120 --> 00:35:30,760
o peor procura lineal caso
é grande de n, imos dicir.

954
00:35:30,760 --> 00:35:33,430
>> E canto mellor dos casos,
se ten moita sorte?

955
00:35:33,430 --> 00:35:36,200
Só vai dar un paso,
ou un número constante de pasos.

956
00:35:36,200 --> 00:35:37,830
Entón, imos describir isto como un.

957
00:35:37,830 --> 00:35:39,010
Entón, iso é moi bo.

958
00:35:39,010 --> 00:35:41,210
Agora o que se fixo algo
como busca binária?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
Investigación de modo binario, no peor
caso, levou canto tempo?

961
00:35:47,846 --> 00:35:49,250
>> [Interpondo voces]

962
00:35:49,250 --> 00:35:51,310
>> DAVID J. Malan: Entón, en realidade, eu
escoitei nalgúns lugares.

963
00:35:51,310 --> 00:35:56,390
Entón, é realmente entrar n, máis ou menos,
porque, coma nós dividimos a lista ao medio

964
00:35:56,390 --> 00:36:00,730
de novo, e de novo, e de novo, somos capaces
para atopar, por fin, o valor,

965
00:36:00,730 --> 00:36:04,750
se el está aí, pero hai unha pegadinha.

966
00:36:04,750 --> 00:36:08,590
Cal é a suposición de que temos que
ter concedido para a procura binaria?

967
00:36:08,590 --> 00:36:09,700
Ten que ser resolto.

968
00:36:09,700 --> 00:36:12,770
Non está resolto, pode dividir a cousa
polo medio de novo e de novo, e

969
00:36:12,770 --> 00:36:15,490
pode ir á esquerda, e pode ir á dereita, e
pode ir á esquerda e á dereita, pero é

970
00:36:15,490 --> 00:36:18,070
Non vai atopar o elemento que
a lista non está ordenada porque

971
00:36:18,070 --> 00:36:18,790
pode perde-la.

972
00:36:18,790 --> 00:36:22,120
Porque a súa heurística, para ir á esquerda
ou á dereita será fallo, se é

973
00:36:22,120 --> 00:36:23,420
en realidade, non clasificados.

974
00:36:23,420 --> 00:36:26,110
Polo tanto, hai unha especie de custo oculto
para usar algo así.

975
00:36:26,110 --> 00:36:29,250
>> Agora, imos para a nosa clasificación
algoritmos non busca -

976
00:36:29,250 --> 00:36:31,140
Oh, realmente imos entrar en branco.

977
00:36:31,140 --> 00:36:33,190
Busca binaria no mellor dos casos?

978
00:36:33,190 --> 00:36:36,290
É tamén un caso só pasa de ser
ben no medio da matriz, ou

979
00:36:36,290 --> 00:36:37,810
no medio da lista telefónica.

980
00:36:37,810 --> 00:36:39,710
Agora imos facer o bubble sort.

981
00:36:39,710 --> 00:36:42,570
Entón, de novo, agora estamos entrando na
tipo, e non as enquisas.

982
00:36:42,570 --> 00:36:47,220
>> No peor dos casos, cantos pasos que fixemos
reivindicación bubble sort vai levar?

983
00:36:47,220 --> 00:36:48,410
n ao cadrado.

984
00:36:48,410 --> 00:36:49,200
Entón eu vou aproveitar iso.

985
00:36:49,200 --> 00:36:51,710
Ooh, miña letra parece aínda peor
cando está previsto que grande.

986
00:36:51,710 --> 00:36:52,510
Todo ben.

987
00:36:52,510 --> 00:36:53,570
Entón iso n ao cadrado.

988
00:36:53,570 --> 00:36:59,460
E, no mellor dos casos de bubble sort,
cantos pasos é que vai tomar?

989
00:36:59,460 --> 00:37:00,980
1, escoitei.

990
00:37:00,980 --> 00:37:01,760
>> COLUMNA 1: n.

991
00:37:01,760 --> 00:37:03,286
>> DAVID J. Malan: n, eu oín.

992
00:37:03,286 --> 00:37:04,200
>> COLUMNA 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> DAVID J. Malan: 2, escoitei.

994
00:37:05,010 --> 00:37:06,670
Escoito 3?

995
00:37:06,670 --> 00:37:07,080
Todo ben.

996
00:37:07,080 --> 00:37:11,390
Entón escoitei 1, n, 2, pero imos escoller
ademais de polo menos a primeira desas

997
00:37:11,390 --> 00:37:12,330
suxestións, 1.

998
00:37:12,330 --> 00:37:15,370
Non é un mal instinto, porque
tipo de segue un estándar aquí.

999
00:37:15,370 --> 00:37:19,670
Pero se só ten un paso, como no
o mundo que eu podería reclamar que a lista

1000
00:37:19,670 --> 00:37:22,900
é ordenada, porque se eu estou só permitida
tomar un paso, cantos elementos

1001
00:37:22,900 --> 00:37:25,230
En realidade, eu podería comprobar a estar seguro?

1002
00:37:25,230 --> 00:37:28,270
Ben, só un, o que significa que hai n
menos un elementos que poderían estar fóra de

1003
00:37:28,270 --> 00:37:31,310
orde, e eu só vou na fe despois
mirando para un elemento que o

1004
00:37:31,310 --> 00:37:31,850
cousa está clasificada.

1005
00:37:31,850 --> 00:37:33,930
Entón 1 non é correcto aquí.

1006
00:37:33,930 --> 00:37:35,710
Así, minimamente, cantos
que eu teño que mirar?

1007
00:37:35,710 --> 00:37:36,680
>> [Interpondo voces]

1008
00:37:36,680 --> 00:37:40,160
>> DAVID J. Malan: n menos 1, ou realmente,
n, porque eu preciso ollar para cada

1009
00:37:40,160 --> 00:37:42,190
elemento para asegurarse de que
non está fóra de orde.

1010
00:37:42,190 --> 00:37:44,750
Pero, de novo, nós imos resolver de onda nosa
mans en números menores e

1011
00:37:44,750 --> 00:37:47,100
supoñer que, a medida que n se fai grande, son
desinteressante calquera maneira.

1012
00:37:47,100 --> 00:37:48,380
Entón, iso é bubble sort.

1013
00:37:48,380 --> 00:37:49,830
E agora, imos facer estes dous últimos.

1014
00:37:49,830 --> 00:37:53,520
Tipo de selección, e despois imos
facer ordenación por inserción.

1015
00:37:53,520 --> 00:37:57,160
E entón vai explotar a súa
mente con algo moi

1016
00:37:57,160 --> 00:37:58,926
mellor que todos estes.

1017
00:37:58,926 --> 00:38:00,410
Todo ben.

1018
00:38:00,410 --> 00:38:04,700
>> Cal é o peor caso en execución
momento da selección tipo?

1019
00:38:04,700 --> 00:38:05,680
>> COLUMNA 4: n ao cadrado.

1020
00:38:05,680 --> 00:38:06,710
>> DAVID J. Malan: n cadrado, estou escoitando.

1021
00:38:06,710 --> 00:38:09,790
Pero por que non ao cadrado, intuitivamente?

1022
00:38:09,790 --> 00:38:11,170
>> COLUMNA 4: Porque só fixen iso.

1023
00:38:11,170 --> 00:38:12,260
>> DAVID J. Malan: Por nós só fixen iso.

1024
00:38:12,260 --> 00:38:12,550
Aceptar.

1025
00:38:12,550 --> 00:38:13,380
Boa resposta.

1026
00:38:13,380 --> 00:38:16,660
Pero intuitivamente, por que é a selección
tipo n ao cadrado?

1027
00:38:16,660 --> 00:38:18,980
O que temos que facer
unha e outra vez?

1028
00:38:18,980 --> 00:38:22,570
Tivemos que manter a dixitalización a través, son
vostede o máis pequeno, é o

1029
00:38:22,570 --> 00:38:24,020
máis pequeno, é o máis pequeno.

1030
00:38:24,020 --> 00:38:27,480
E concedido, fomos capaces de tomar n
pasos, entón n menos 1, entón n menos 2.

1031
00:38:27,480 --> 00:38:30,700
Pero se especie de engadir todos aqueles por riba,
ou leva-la na fe que eu engade

1032
00:38:30,700 --> 00:38:34,810
Los con antelación, temos preto de n
cadrado menos algúns números menores.

1033
00:38:34,810 --> 00:38:36,730
Entón, eu vou chamar a este n ao cadrado.

1034
00:38:36,730 --> 00:38:39,530
Pero, coa selección de tipo no mellor
caso, cantos pasos se

1035
00:38:39,530 --> 00:38:40,632
me vai levar?

1036
00:38:40,632 --> 00:38:41,840
>> COLUMNA 5: [inaudível]

1037
00:38:41,840 --> 00:38:44,350
>> DAVID J. Malan: É, por desgraza,
aínda n ao cadrado, non?

1038
00:38:44,350 --> 00:38:49,590
Porque se eu estou escollendo menor
elemento, e tivemos sete persoas aquí,

1039
00:38:49,590 --> 00:38:53,280
Eu só sei que, cando chegar ao moi
final, que eu atope a menor

1040
00:38:53,280 --> 00:38:55,670
número, onde queira
ela pode ser.

1041
00:38:55,670 --> 00:38:58,820
Pero como fago para o seguinte
menor número?

1042
00:38:58,820 --> 00:39:00,160
Teño que facer outra pasaxe.

1043
00:39:00,160 --> 00:39:04,810
Así, no mellor dos casos, o que é o
de entrada para a selección tipo?

1044
00:39:04,810 --> 00:39:07,830
É unha lista xa especie, número un,
número dous, número tres, número catro.

1045
00:39:07,830 --> 00:39:08,600
Pero eu son un ordenador.

1046
00:39:08,600 --> 00:39:10,190
Só podo ollar a un
cousa de cada vez.

1047
00:39:10,190 --> 00:39:12,465
Non podo clasificar de dar un paso
de volta como un ser humano e dicir:

1048
00:39:12,465 --> 00:39:14,030
Ooh, iso parece correcto.

1049
00:39:14,030 --> 00:39:17,580
>> Só podo xulgar correcto en
selección especie, seleccionando o

1050
00:39:17,580 --> 00:39:18,370
menor número.

1051
00:39:18,370 --> 00:39:21,390
Pero aínda que eu atopar o número un en primeiro lugar,
se eu non sei nada sobre

1052
00:39:21,390 --> 00:39:24,460
os outros números, o que eu non fago, todo o que eu
sei que teño sido entregada unha matriz

1053
00:39:24,460 --> 00:39:27,930
ou un conxunto de portas de atrás, que son
números, o único xeito que sei que un

1054
00:39:27,930 --> 00:39:28,680
foi o máis pequeno?

1055
00:39:28,680 --> 00:39:32,440
Se eu chegar ata aquí e entender,
caramba, unha era de feito o máis pequeno.

1056
00:39:32,440 --> 00:39:34,870
>> Pero como fago para, entón, determinar que
dous é a seguinte menor?

1057
00:39:34,870 --> 00:39:38,350
Ao facer o mesmo ineficiencia
unha e outra vez.

1058
00:39:38,350 --> 00:39:42,210
Entón, finalmente, coa ordenación por inserción,
como, no peor dos casos,

1059
00:39:42,210 --> 00:39:44,990
se dicimos que el executa?

1060
00:39:44,990 --> 00:39:49,100
Tamén é n ao cadrado.

1061
00:39:49,100 --> 00:39:53,020
E que tal co mellor caso?

1062
00:39:53,020 --> 00:39:56,282
Imos deixar isto como un cliffhanger.

1063
00:39:56,282 --> 00:40:00,090
Imos encher ese baleiro a próxima vez,
pero primeiro deixe-me propor que

1064
00:40:00,090 --> 00:40:02,620
fundamentalmente facer mellor que
todo isto, non?

1065
00:40:02,620 --> 00:40:05,220
>> Entón, pense por si mesmo que a inserción
tipo vai ser.

1066
00:40:05,220 --> 00:40:06,910
Ben, iso non era moi dramática,
porque eu son o único

1067
00:40:06,910 --> 00:40:08,970
que viu o cambio.

1068
00:40:08,970 --> 00:40:09,620
Guau.

1069
00:40:09,620 --> 00:40:10,420
Aceptar.

1070
00:40:10,420 --> 00:40:12,615
Entón aquí temos algo
demostración diferente.

1071
00:40:12,615 --> 00:40:16,580
Se eu aumentar o zoom aquí, vai ver que en
Á esquerda temos bubble sort, no

1072
00:40:16,580 --> 00:40:20,740
medio temos a selección de clasificación, e en
a extrema dereita, temos algo que

1073
00:40:20,740 --> 00:40:23,380
non mirei aínda
chamado merge sort.

1074
00:40:23,380 --> 00:40:26,080
Pero considerada o que fomos
facendo aquí, ata agora, hoxe.

1075
00:40:26,080 --> 00:40:29,200
Cando Jennifer veu por primeira vez enriba do escenario,
pasamos a matriz de números

1076
00:40:29,200 --> 00:40:33,750
de novo, e de novo, coa procura lineal,
e temos tempo de execución lineal, grande

1077
00:40:33,750 --> 00:40:35,100
de n, por así dicir.

1078
00:40:35,100 --> 00:40:41,000
>> Cando consideramos agora a primeira semana de
clase cando tiñamos dividir e conquistar,

1079
00:40:41,000 --> 00:40:43,740
e nós tiñamos o libro de teléfono lacrimejamento,
e Jennifer, e colectivamente

1080
00:40:43,740 --> 00:40:47,500
panca ese insight fundamental, que era
repetirse unha e outra vez por

1081
00:40:47,500 --> 00:40:50,930
algunha forma de xogar fóra, xogando fóra,
xogar fora, a metade do problema, ou

1082
00:40:50,930 --> 00:40:55,320
Xeralmente, dividindo-se un problema no medio,
e despois tratar o anaco menor de

1083
00:40:55,320 --> 00:40:59,630
o problema como conceptualmente equivalente
a outra, que dalgún xeito fixo

1084
00:40:59,630 --> 00:41:00,910
fundamentalmente mellor.

1085
00:41:00,910 --> 00:41:04,720
Pero co bubble sort, coa selección
tipo, con ordenación por inserción, temos pode

1086
00:41:04,720 --> 00:41:06,560
ningún destes insights que Jennifer fixo.

1087
00:41:06,560 --> 00:41:10,220
Nós practicamente só andou cara atrás e
ante un grupo enteiro de veces, e nós

1088
00:41:10,220 --> 00:41:12,650
cousas revolto un pouco, cambiando
por esta orde, quizais

1089
00:41:12,650 --> 00:41:13,730
inserir ou seleccionar.

1090
00:41:13,730 --> 00:41:16,950
Pero ao final do día, eu fixen unha morea
de andar torpe e cara atrás.

1091
00:41:16,950 --> 00:41:21,160
Non realmente aproveitar algo
intelixente como Jennifer gusta dividindo

1092
00:41:21,160 --> 00:41:22,040
e conquistador.

1093
00:41:22,040 --> 00:41:25,620
>> Así tipo fundir, pola contra, que
non vai ver ata a próxima semana, que vai

1094
00:41:25,620 --> 00:41:29,540
para alavancar a idea clave, dividindo
de entrada e, a continuación, reducir á metade e logo

1095
00:41:29,540 --> 00:41:30,580
reducir á metade, a continuación, reducir á metade.

1096
00:41:30,580 --> 00:41:34,590
E, en cada iteración do bucle de que,
clasificando a metade esquerda e á dereita

1097
00:41:34,590 --> 00:41:38,200
a metade, a continuación, a metade esquerda da metade esquerda,
ea metade dereita da esquerda e logo

1098
00:41:38,200 --> 00:41:40,990
a metade esquerda da metade dereita, e
a metade dereita da metade dereita.

1099
00:41:40,990 --> 00:41:42,840
E repetindo unha e outra vez.

1100
00:41:42,840 --> 00:41:46,170
>> Entón, vai ver que visualmente, pero esta
é o que nos espera a próxima semana.

1101
00:41:46,170 --> 00:41:49,760
E, en xeral, cando pensamos un pouco
pouco máis difícil en calquera problema deste tipo.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Nós n ao cadrado da esquerda, n
cadrado no medio, e n

1104
00:41:57,970 --> 00:41:59,400
log n da dereita.

1105
00:41:59,400 --> 00:42:00,590
Polo tanto, non hai o suspenso real.

1106
00:42:00,590 --> 00:42:02,040
Vemo-nos o luns.

1107
00:42:02,040 --> 00:42:05,163
>> [Aplausos]