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

2
00:00:11,270 --> 00:00:14,910
>> Palestrante: Tudo bem, essa é CS50.

3
00:00:14,910 --> 00:00:19,020
Isto é o fim de semana de três, e, se
você não tenha aproveitado já,

4
00:00:19,020 --> 00:00:21,790
sei que haverá almoço
nesta sexta-feira, como de costume, onde

5
00:00:21,790 --> 00:00:25,430
você pode desfrutar de uma boa conversa
e alimentos em Fire and Ice

6
00:00:25,430 --> 00:00:27,980
com alguns dos CS50 de
funcionários e colegas.

7
00:00:27,980 --> 00:00:30,170
Confronto esta URL aqui.

8
00:00:30,170 --> 00:00:33,420
>> Agora você pode recordar, ou você
pode em breve estar familiarizado com,

9
00:00:33,420 --> 00:00:35,970
essas coisas aqui, que
são dadas no final

10
00:00:35,970 --> 00:00:37,850
do semestre para muitas classes.

11
00:00:37,850 --> 00:00:40,870
O chamado exame de livros azuis, em que
você escrever suas respostas para os exames.

12
00:00:40,870 --> 00:00:44,240
Agora eu tenho aqui 26, tais
livros azuis, em cada um deles

13
00:00:44,240 --> 00:00:47,580
está escrito um nome, de A a Z. E
na verdade, os nomes são assim tão simples, A

14
00:00:47,580 --> 00:00:50,490
a Z. E uma das
as metas em mãos hoje

15
00:00:50,490 --> 00:00:53,910
vai ser para continuar o que
começamos na segunda-feira, que não é

16
00:00:53,910 --> 00:00:57,830
tanto olhar o código, mas realmente
olhando para ideias e resolução de problemas.

17
00:00:57,830 --> 00:01:00,170
Um dos objetivos e
promessas deste curso

18
00:01:00,170 --> 00:01:02,985
é ensiná-lo a pensar mais
cuidado, mais metodicamente,

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

20
00:01:05,400 --> 00:01:09,526
E, de fato, nós podemos fazer o que realmente
sem sequer tocar uma linha de código.

21
00:01:09,526 --> 00:01:12,150
Então, eu tenho um par de elefantes
aqui hoje, laranja e azul,

22
00:01:12,150 --> 00:01:15,780
se pudéssemos obter um voluntário,
talvez de mais para trás do que o habitual.

23
00:01:15,780 --> 00:01:18,070
Que tal ali mesmo, vamos lá para baixo.

24
00:01:18,070 --> 00:01:24,180
O objetivo do que vai ser a
ajudar mais administrar este exame aqui.

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

26
00:01:24,935 --> 00:01:25,768
>> AUDIÊNCIA: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
Palestrante: Mary Beth, vamos lá para cima.

28
00:01:27,560 --> 00:01:29,560
Deixe-me pegar o microfone aqui para você.

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

30
00:01:32,172 --> 00:01:32,880
Prazer em conhecê-lo.

31
00:01:32,880 --> 00:01:34,005
>> AUDIÊNCIA: Prazer em conhecê-lo.

32
00:01:34,005 --> 00:01:36,790
Palestrante: Tudo bem, então eu tenho
aqui livros azul de A a Z,

33
00:01:36,790 --> 00:01:41,680
e eu vou fingir que
Eu tenho um dos alunos,

34
00:01:41,680 --> 00:01:45,770
e eles estão vindo em um tanto aleatoriamente
no fim de um bloco de exame três horas,

35
00:01:45,770 --> 00:01:49,400
então eles estão acabando em alguns
ordem semi-aleatória assim.

36
00:01:49,400 --> 00:01:54,510
Agora o seu trabalho em apenas um momento que vai
para ser-- este é realmente como eles se

37
00:01:54,510 --> 00:01:56,820
entregues no final
a classe, o mais provável.

38
00:01:56,820 --> 00:02:01,120
Seu trabalho agora vai ser, bastante
simplesmente, para classificar esses livros 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
>> AUDIÊNCIA: Oh, isso é
vai levar para sempre.

41
00:02:08,400 --> 00:02:13,747
>> Orador: E vamos assistir
como você faz isso, sem pressão.

42
00:02:13,747 --> 00:02:15,330
AUDIÊNCIA: Não, nenhuma pressão nem nada.

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

44
00:02:19,230 --> 00:02:23,570
>> Orador: E para se divertir,
vamos colocar um temporizador.

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

46
00:02:26,680 --> 00:02:28,700
>> AUDIÊNCIA: muito divertido, muito divertido.

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

48
00:02:36,741 --> 00:02:38,574
>> Palestrante: eu posso segurar o microfone para você.

49
00:02:38,574 --> 00:02:40,240
Tudo bem, nós apenas dobrou a nossa velocidade.

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

51
00:02:44,190 --> 00:02:49,060
Então, nesse meio tempo, deixe-me colocar o que há de
vai ser a pergunta de Mary Beth

52
00:02:49,060 --> 00:02:51,540
é o que ela está fazendo, como está
ela vai sobre como resolver isso?

53
00:02:51,540 --> 00:02:54,040
E, na verdade, você não pode ter
já pensou em algo

54
00:02:54,040 --> 00:02:57,440
tão simples como quando você escolhe
até 26 livros como este,

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

56
00:02:59,350 --> 00:03:01,335
Qual é o processo
que você realmente usa?

57
00:03:01,335 --> 00:03:03,770
É bastante aleatório apenas
escolher o primeiro que você vê

58
00:03:03,770 --> 00:03:05,250
e colocá-lo em seu lugar?

59
00:03:05,250 --> 00:03:09,680
Você primeiro mover suas mãos em torno
Procurando um em seguida, olhando para B?

60
00:03:09,680 --> 00:03:11,722
Você dar uma olhada em um
par deles lado a lado

61
00:03:11,722 --> 00:03:14,680
e apenas dizer, espere um minuto, isto
Não é certo, e, em seguida, trocar a ordem?

62
00:03:14,680 --> 00:03:16,960
Nós já vimos na segunda-feira
que há uma série de maneiras

63
00:03:16,960 --> 00:03:22,140
em que podemos fazer isso, e
na verdade, como estamos perto do final aqui,

64
00:03:22,140 --> 00:03:26,360
Eu tomaria nota talvez
do que Mary Beth está fazendo.

65
00:03:26,360 --> 00:03:30,040
Temos algumas pilhas que parece, um
maior, três menores.

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

67
00:03:33,790 --> 00:03:36,415
>> AUDIÊNCIA: Estou ordenando-lhes
quando eu encontrar duas cartas

68
00:03:36,415 --> 00:03:39,540
que eu sei que estão juntos em uma seqüência,
Eu colocá-los juntos para que eu não

69
00:03:39,540 --> 00:03:42,915
tem que se preocupar em manter
o controle de uma linha inteira de livros.

70
00:03:42,915 --> 00:03:45,706
É apenas, oh, A é o primeiro,
Eu tenho essa pilha aqui.

71
00:03:45,706 --> 00:03:47,580
Palestrante: Então, quase como
de peças de quebra-cabeça que

72
00:03:47,580 --> 00:03:49,860
tem a forma certa para
combinar-se um com o outro.

73
00:03:49,860 --> 00:03:51,026
AUDIÊNCIA: Muito bonito, sim.

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

75
00:03:55,320 --> 00:03:59,850
E agora cada um destes
pilhas é presumivelmente ordenado?

76
00:03:59,850 --> 00:04:00,990
>> AUDIÊNCIA: Yeah.

77
00:04:00,990 --> 00:04:09,900
>> Palestrante: Tudo bem, de A a Z. Todos
certo, parabéns, você fez isso.

78
00:04:09,900 --> 00:04:11,461
Você tem a sua escolha.

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

80
00:04:11,960 --> 00:04:13,530
Tudo bem, obrigado por isso.

81
00:04:13,530 --> 00:04:16,679
Então Mary Beth se propôs
que sua abordagem era,

82
00:04:16,679 --> 00:04:19,720
mas o que é uma outra abordagem como você
pode ir sobre como classificar essas coisas?

83
00:04:19,720 --> 00:04:21,130
O que você teria feito?

84
00:04:21,130 --> 00:04:24,060
O recorde de bater teria sido
um minuto e 50 segundos ou menos,

85
00:04:24,060 --> 00:04:26,039
mais os que eu esqueci de contar.

86
00:04:26,039 --> 00:04:27,080
O que você teria feito?

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

88
00:04:27,579 --> 00:04:28,735
AUDIÊNCIA: Pegue a pilha.

89
00:04:28,735 --> 00:04:29,776
Comece desde o início.

90
00:04:29,776 --> 00:04:32,284
Verifique os seus papéis.

91
00:04:32,284 --> 00:04:36,586
E se o de cima é maior
do que, talvez, eles são,

92
00:04:36,586 --> 00:04:38,980
o fundo é
superior, em seguida, desligá-los.

93
00:04:38,980 --> 00:04:41,300
>> Palestrante: OK, assim que começar
na parte superior e na parte inferior,

94
00:04:41,300 --> 00:04:43,716
e, em seguida, trabalhar o seu caminho
dentro desse jeito, trocando-os?

95
00:04:43,716 --> 00:04:46,580
OK, então um pouco semelhante
em espírito de bubble sort,

96
00:04:46,580 --> 00:04:49,160
mas escolher os extremos
não os pares adjacentes.

97
00:04:49,160 --> 00:04:52,080
Mas o curto do que é que há
certamente um monte de maneiras diferentes

98
00:04:52,080 --> 00:04:54,210
nós poderíamos fazer isso, e
francamente, acho que tipo de

99
00:04:54,210 --> 00:04:55,700
adotou algumas abordagens, certo?

100
00:04:55,700 --> 00:05:00,567
Você fez uma espécie de quatro pilhas ordenadas, e
então efetivamente fundiu-los juntos.

101
00:05:00,567 --> 00:05:02,650
E isso é, ouso dizer, uma outra
técnica completamente.

102
00:05:02,650 --> 00:05:06,950
Você não tratá-lo como uma grande pilha,
você divide o problema em quatro quadriláteros,

103
00:05:06,950 --> 00:05:09,820
se você quiser, e depois de alguma forma
fundiu-los no final.

104
00:05:09,820 --> 00:05:13,410
>> Então, vamos considerar, em última análise,
De que outra forma poderíamos fazer isso.

105
00:05:13,410 --> 00:05:15,860
Nós formalizou a noção
de bubble sort última vez,

106
00:05:15,860 --> 00:05:18,780
e recordação bubble sort foi um
algoritmo que visualizamos

107
00:05:18,780 --> 00:05:22,640
com oito de seus colegas aqui em cima,
aparentemente aleatoriamente classificados em primeiro lugar.

108
00:05:22,640 --> 00:05:26,110
E nós, então, decidiu pares, se
dois elementos estão fora de ordem,

109
00:05:26,110 --> 00:05:26,950
simplesmente trocá-los.

110
00:05:26,950 --> 00:05:28,930
Então, quatro e dois são
obviamente, fora de ordem,

111
00:05:28,930 --> 00:05:31,080
então esses dois colegas
trocar de posição.

112
00:05:31,080 --> 00:05:35,390
E, então, repetido com quatro e seis,
em seguida, seis e oito, em cada iteração,

113
00:05:35,390 --> 00:05:36,980
movendo para a direita.

114
00:05:36,980 --> 00:05:42,590
>> Assim, dado oito pessoas, quantos pares
comparações que eu fiz durante a caminhada de

115
00:05:42,590 --> 00:05:45,220
esquerda para a direita em um tal iteração?

116
00:05:45,220 --> 00:05:48,410
Quantas comparações?

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

118
00:05:49,197 --> 00:05:51,405
Porque se há oito
pessoas, mas você tem o par

119
00:05:51,405 --> 00:05:53,880
eles e você continuar se movendo
um salto para a direita,

120
00:05:53,880 --> 00:05:56,060
você não vai ter oito
comparações, porque você não pode comparar

121
00:05:56,060 --> 00:05:59,226
um elemento contra si, ou que seria
basta ser inútil, então você tem sete.

122
00:05:59,226 --> 00:06:01,290
Ou, mais geralmente, se
temos n pessoas, nós

123
00:06:01,290 --> 00:06:04,300
fazer N menos 1 comparações
com bubble sort.

124
00:06:04,300 --> 00:06:08,150
>> Então, vamos considerar agora como bom ou
ruim bubble sort realmente era, e tentar

125
00:06:08,150 --> 00:06:13,570
dar-nos vocabulário com
que a algoritmos crítica como esta,

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

127
00:06:14,430 --> 00:06:16,970
Então, a primeira passagem através
bubble sort, pela primeira vez

128
00:06:16,970 --> 00:06:20,909
Eu andei a partir da esquerda para a direita na
palco, me n menos 1 comparações tomou.

129
00:06:20,909 --> 00:06:22,950
E isso vai ser meu
unidade de medida, certo?

130
00:06:22,950 --> 00:06:26,170
Eu era uma espécie de falar e caminhar,
um tanto rapidamente, um tanto lento,

131
00:06:26,170 --> 00:06:29,300
assim contando meu número de segundos
não é particularmente revelador,

132
00:06:29,300 --> 00:06:32,260
mas a contagem do número de
operações que eu fiz na segunda-feira,

133
00:06:32,260 --> 00:06:35,900
comparando duas pessoas, que se sente
como uma agradável unidade de medida.

134
00:06:35,900 --> 00:06:40,980
>> Então n menos 1 passos pela primeira vez,
Mas então o que aconteceu depois disso?

135
00:06:40,980 --> 00:06:46,610
Qual é a única cabeça de uma só vez
através de uma lista de outra forma não ordenada?

136
00:06:46,610 --> 00:06:49,840
O que você pode me dizer sobre o elemento
que foi todo o caminho até lá?

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

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

139
00:06:52,870 --> 00:06:55,710
O número oito, embora ela
começou aqui, toda vez que eu

140
00:06:55,710 --> 00:06:57,860
comparado a contra
um vizinho, ela manteve

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

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

143
00:07:02,710 --> 00:07:07,630
>> Agora por essa lógica, quantas comparações
eu vou fazer no segundo tempo

144
00:07:07,630 --> 00:07:09,800
Eu faço que passe da esquerda para a direita?

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

146
00:07:10,730 --> 00:07:14,297
Seria apenas perdendo meu tempo se eu
manter comparando oito contra alguém

147
00:07:14,297 --> 00:07:16,630
mais porque já sabemos
ela estava no lugar certo.

148
00:07:16,630 --> 00:07:19,760
Então, isso é um pouco de um
otimização, de modo que o próximo passo

149
00:07:19,760 --> 00:07:23,899
vai ser mais n menos duas etapas,
onde n é o número de pessoas.

150
00:07:23,899 --> 00:07:26,940
Agora você pode tipo de extrapolar, mesmo
se você não é um cientista da computação,

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

152
00:07:27,680 --> 00:07:31,259
No final deste algoritmo, presumivelmente
você tem apenas uma comparação esquerda.

153
00:07:31,259 --> 00:07:33,800
Você tem que tipo de corrigir o
início da lista, no caso de dois

154
00:07:33,800 --> 00:07:36,540
e um está fora de ordem
e deve ser um e dois,

155
00:07:36,540 --> 00:07:40,330
de modo que este encoste na
além de uma comparação final.

156
00:07:40,330 --> 00:07:44,500
>> Agora, o ponto, ponto, ponto tipo de ondas é
mãos em alguns dos detalhes mais suculentas,

157
00:07:44,500 --> 00:07:46,452
mas vamos apenas ir em frente e simplificar.

158
00:07:46,452 --> 00:07:48,660
Se você se lembrar de alta
escola, francamente, muitos de vocês

159
00:07:48,660 --> 00:07:50,340
tinham livros de matemática que tinham
uma folha de fraude pouco

160
00:07:50,340 --> 00:07:52,550
na capa ou a
tampa traseira que mostrei

161
00:07:52,550 --> 00:07:56,400
somatórios que séries como
Esta última análise, somou.

162
00:07:56,400 --> 00:07:59,600
No caso geral, se você tem um
variável como n, e de fato este,

163
00:07:59,600 --> 00:08:01,634
Se você olhou para sua
livro de matemática velha escola,

164
00:08:01,634 --> 00:08:04,050
você veria que isso realmente
acrescenta-se a esta soma aqui,

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

166
00:08:07,970 --> 00:08:11,172
Então, por agora, deixe-me apenas estipular
isso é verdade, então em um ato de fé,

167
00:08:11,172 --> 00:08:12,880
isso é o que isto resume
até, e pudemos

168
00:08:12,880 --> 00:08:14,341
provar que, num caso mais geral.

169
00:08:14,341 --> 00:08:15,590
Mas agora vamos expandir isso.

170
00:08:15,590 --> 00:08:19,920
Então, vamos multiplicar isso, o que é
n ao quadrado, menos n, tudo dividido por 2.

171
00:08:19,920 --> 00:08:23,200
Isso é realmente n ao quadrado,
dividido por 2, menos n mais de 2,

172
00:08:23,200 --> 00:08:25,010
de modo que é tudo bom e interessante.

173
00:08:25,010 --> 00:08:27,060
Mas o que acontece se nós
agora plug-in um valor?

174
00:08:27,060 --> 00:08:29,724
Suponha que eu não tinha oito
pessoas, mas dizem que um milhão.

175
00:08:29,724 --> 00:08:31,890
E um milhão só porque
que é um número muito grande,

176
00:08:31,890 --> 00:08:34,039
vamos ligar isso e ver o que acontece.

177
00:08:34,039 --> 00:08:39,039
Então, se eu ligar um milhão para que a fórmula
Eu estou indo para obter um milhão de quadrado,

178
00:08:39,039 --> 00:08:42,868
dividido por 2, menos uma
milhões, dividido por dois.

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

180
00:08:44,159 --> 00:08:47,354
Assim, 500 bilhões, menos 500.000.

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

182
00:08:49,270 --> 00:08:53,920
que a classificação de um milhão
pessoas com o tipo de bolha

183
00:08:53,920 --> 00:09:01,800
pode me levar 499999500000
etapas ou comparações, no final,

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

185
00:09:02,900 --> 00:09:06,860
>> Que se sente muito lento, mas francamente
medição de uma entrada especial

186
00:09:06,860 --> 00:09:09,160
assim, não é tão revelador.

187
00:09:09,160 --> 00:09:14,050
Mas na verdade, ela sugere que como n
torna-se maior e maior, este algoritmo

188
00:09:14,050 --> 00:09:16,280
tipo de sente pior e
pior, ou você realmente

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

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

191
00:09:21,770 --> 00:09:25,340
E esse detalhe não é
perdido nas pessoas, na verdade,

192
00:09:25,340 --> 00:09:29,640
há alguns anos, um certo senador que foi
campanha, sentou-se para uma entrevista

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

194
00:09:32,180 --> 00:09:36,380
e foi desafiado com uma pergunta
assim como nós estamos explorando hoje.

195
00:09:36,380 --> 00:09:38,468
Vamos dar uma olhada.

196
00:09:38,468 --> 00:09:45,280
>> [REPRODUÇÃO]

197
00:09:45,280 --> 00:09:48,560
>> Senador, você está aqui
no Google, e eu gosto

198
00:09:48,560 --> 00:09:53,382
pensar na presidência
como uma entrevista de emprego.

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

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

201
00:09:58,100 --> 00:10:01,860
Também é difícil conseguir um emprego no Google.

202
00:10:01,860 --> 00:10:05,490
Nós temos perguntas, e nós
nossas perguntas 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-- vocês acham que eu sou
brincadeira, é aqui mesmo.

205
00:10:14,760 --> 00:10:17,930
Qual é a maneira mais eficiente de
classificar um milhão de inteiros 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 muito, maybe--

209
00:10:25,200 --> 00:10:27,400
>> Não, não, não.

210
00:10:27,400 --> 00:10:30,700
Eu acho que o bubble sort
seria o caminho errado.

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

212
00:10:34,165 --> 00:10:38,180
>> Vamos, que lhe disse isso?

213
00:10:38,180 --> 00:10:40,590
Eu não vi computador
ciência em seu fundo.

214
00:10:40,590 --> 00:10:42,130
>> -Temos Nossos espiões lá dentro.

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

216
00:10:44,930 --> 00:10:48,444
>> -OK, Vamos pedir um diferente
pergunta da entrevista.

217
00:10:48,444 --> 00:10:49,300
>> [FIM REPRODUÇÃO DE VÍDEO]

218
00:10:49,300 --> 00:10:52,290
>> Palestrante: Então, falando
números específicos, embora

219
00:10:52,290 --> 00:10:53,890
Não vai ser tão útil.

220
00:10:53,890 --> 00:10:56,810
Não é uma lição de vida que bolha
tipo, dado um milhão de entradas,

221
00:10:56,810 --> 00:10:58,590
pode levar até 500 bilhões etapas.

222
00:10:58,590 --> 00:11:01,120
Você realmente não pode generalizar
muito eficazmente desde que

223
00:11:01,120 --> 00:11:03,560
e tomar boas decisões de design
ao escrever programas.

224
00:11:03,560 --> 00:11:07,070
Então, vamos nos concentrar em como embora
podemos simplificar este resultado.

225
00:11:07,070 --> 00:11:11,780
>> Então, eu tenho realçado em amarelo aqui
o resultado de n quadrado dividido por dois,

226
00:11:11,780 --> 00:11:14,330
assim um milhão quadrado
dividido por dois, e depois

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
uma vez que fora subtraído n dividido por 2.

229
00:11:20,180 --> 00:11:24,850
E a alegação de que eu vou fazer agora é,
quem diabos se importa se você subtrair off

230
00:11:24,850 --> 00:11:30,060
um pouco mais de idade n 2 quando o primeiro
parte desta fórmula é muito maior?

231
00:11:30,060 --> 00:11:33,910
Ele domina o outro
prazo, n quadrado dividido por dois

232
00:11:33,910 --> 00:11:37,510
é muito maior, de forma clara, como
n se torna grande como um milhões,

233
00:11:37,510 --> 00:11:41,450
que há realmente uma grande diferença no
No final do dia entre 500 mil milhões

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

235
00:11:45,730 --> 00:11:46,349
Não é realmente.

236
00:11:46,349 --> 00:11:48,640
E então o que vamos
fazer o que os cientistas da computação é

237
00:11:48,640 --> 00:11:53,270
ignorar esses termos de ordem mais baixa e
ter algo parecido com isso e realmente

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

239
00:11:56,050 --> 00:12:00,315
Os maiores nossos conjuntos de dados começa, o maior
nossas bases de dados começa, mais páginas da web

240
00:12:00,315 --> 00:12:02,690
temos que procurar, o mais
amigos você tem no Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Como n fica maior, estamos muito
vai se preocupar com a maior

242
00:12:07,340 --> 00:12:11,560
prazo em qualquer análise de
nosso desempenho algoritmos.

243
00:12:11,560 --> 00:12:16,230
E eu vou dizer, você sabe o que,
bubble sort é da ordem de O grande,

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

245
00:12:18,060 --> 00:12:20,090
Não é exatamente n
quadrado, como vimos,

246
00:12:20,090 --> 00:12:22,060
mas quem realmente se importa
sobre esses termos menores,

247
00:12:22,060 --> 00:12:24,390
e, francamente, que realmente
se importa se dividirmos por 2?

248
00:12:24,390 --> 00:12:25,870
Isso é apenas um fator constante.

249
00:12:25,870 --> 00:12:29,480
E é de 500 bilhões contra 250
bilhões que realmente de um grande negócio?

250
00:12:29,480 --> 00:12:32,190
Eu poderia apenas esperar um ano,
deixar meu laptop literalmente

251
00:12:32,190 --> 00:12:34,810
obter duas vezes mais rápido em hardware,
e esse tipo de diferença

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

253
00:12:36,650 --> 00:12:39,300
>> O que nos interessa é
a expressão, a peça

254
00:12:39,300 --> 00:12:42,489
da expressão que vai variar
como nossa entrada fica maior e maior.

255
00:12:42,489 --> 00:12:45,280
E, de fato, no mundo real,
isso é o que está acontecendo cada vez mais

256
00:12:45,280 --> 00:12:48,330
é as entradas para os nossos problemas e
algoritmos estão ficando maiores.

257
00:12:48,330 --> 00:12:53,470
Então, ó grande vai ser a notação,
a notação assintótica, que acabamos de

258
00:12:53,470 --> 00:12:57,160
usar como cientistas da computação para descrever
o desempenho, ou o tempo de funcionamento,

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

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

261
00:13:00,800 --> 00:13:04,170
por pessoas diferentes, usando
alguma métrica fundamentalmente semelhantes

262
00:13:04,170 --> 00:13:07,557
como o número de comparações que você é
fazendo, ou talvez o número de swaps

263
00:13:07,557 --> 00:13:08,140
você está fazendo.

264
00:13:08,140 --> 00:13:11,910
>> O que nós não vamos
contagem é a quantidade de tempo

265
00:13:11,910 --> 00:13:13,981
que passa no relógio
tipicamente na parede.

266
00:13:13,981 --> 00:13:16,230
O que nós não vamos nos preocupar
é sobre a quantidade de memória

267
00:13:16,230 --> 00:13:17,820
você está usando hoje em
menos importante, embora isso seja

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 vamos tentar basear nossas análises
em apenas as operações básicas, aquelas,

270
00:13:23,610 --> 00:13:25,930
francamente, que você pode ver mais visualmente.

271
00:13:25,930 --> 00:13:30,700
Assim, com algo como grande O de n
quadrado, eu afirmo que O de n ao quadrado

272
00:13:30,700 --> 00:13:35,820
é um limite superior sobre o chamado
tempo de funcionamento do bubble sort.

273
00:13:35,820 --> 00:13:38,820
Em outras palavras, se
queria afirmar que há

274
00:13:38,820 --> 00:13:41,370
este limite de quantos
as etapas de um algoritmo pode levar,

275
00:13:41,370 --> 00:13:46,240
ele vai estar no grande O de n
quadrado, neste caso, um limite superior.

276
00:13:46,240 --> 00:13:49,710
>> E se eu não mudar o
história a não ser sobre bubble sort,

277
00:13:49,710 --> 00:13:50,910
mas sobre o limite superior.

278
00:13:50,910 --> 00:13:54,030
Você pode pensar em um algoritmo
que nós olhamos já

279
00:13:54,030 --> 00:13:59,530
cujo limite superior, máximo
medida de tempo ou de operações,

280
00:13:59,530 --> 00:14:04,300
seria dito ser limitado
por n, de uma função linear,

281
00:14:04,300 --> 00:14:07,260
não um quadrática que é curvo?

282
00:14:07,260 --> 00:14:10,780
O que é um algoritmo que
sempre leva mais

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

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

285
00:14:13,360 --> 00:14:15,030
>> AUDIÊNCIA: Encontrar o
maior número em uma lista?

286
00:14:15,030 --> 00:14:16,930
>> Palestrante: Perfeito, encontrando
o maior número em uma lista.

287
00:14:16,930 --> 00:14:18,940
Se eu estou com uma lista de
pessoas, por exemplo,

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

289
00:14:21,440 --> 00:14:23,770
de passos que deve tomar de mim,
uma pessoa razoavelmente inteligente,

290
00:14:23,770 --> 00:14:27,530
para encontrar o maior pessoa nessa lista?

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

292
00:14:28,100 --> 00:14:31,320
Porque, no pior caso, em que
talvez o maior valor ser?

293
00:14:31,320 --> 00:14:32,700
Certo, todo o caminho no final.

294
00:14:32,700 --> 00:14:34,575
Assim, no pior caso
limite superior, eu poderia

295
00:14:34,575 --> 00:14:36,450
tem que ir todo o caminho
até aqui e ser como,

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

297
00:14:39,170 --> 00:14:41,330
Agora seria simplesmente estúpido
se eu continuei indo, certo?

298
00:14:41,330 --> 00:14:43,840
À procura de mais e mais elementos
se o último deles é ali?

299
00:14:43,840 --> 00:14:45,340
Assim, certamente, n é um limite superior.

300
00:14:45,340 --> 00:14:47,420
Eu não preciso de tomar
mais etapas do que isso.

301
00:14:47,420 --> 00:14:51,580
>> Então, o que se em vez propus que
existem algoritmos neste mundo que

302
00:14:51,580 --> 00:14:57,750
ter um tempo de execução que é
delimitada pela grande O de log n, log n?

303
00:14:57,750 --> 00:15:00,390
Onde já vimos isso antes?

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

305
00:15:00,890 --> 00:15:03,309
>> AUDIÊNCIA: No problema de lista telefônica?

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

307
00:15:04,850 --> 00:15:07,754
Qual foi a medida de quão
muito tempo ou quantas lágrimas de TI

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

309
00:15:10,170 --> 00:15:13,212
Nós alegou que era log n, e
mesmo que desconhecido ou que é

310
00:15:13,212 --> 00:15:15,170
um pouco nebuloso o que é um
logaritmo ou expoente foi,

311
00:15:15,170 --> 00:15:17,650
lembre-se que log n
geralmente refere-se ao processo,

312
00:15:17,650 --> 00:15:20,790
neste caso, a divisão
algo em metade, e novamente,

313
00:15:20,790 --> 00:15:25,790
e de novo, e de novo, de tal modo que ele
fica cada vez mais pequeno, como você faz isso.

314
00:15:25,790 --> 00:15:28,470
>> Então log de n refere-se, com certeza,
a exemplo do livro de telefone,

315
00:15:28,470 --> 00:15:32,662
a busca binária, em teoria, quando
teve as portas virtuais no conselho,

316
00:15:32,662 --> 00:15:34,370
ou quando foi Sean
procurando por algo.

317
00:15:34,370 --> 00:15:37,374
Se ele tivesse usado a busca binária, log n
seria o limite superior da quantidade de

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

319
00:15:38,040 --> 00:15:44,027
Mas os algoritmos que decorreu em
log n assumiu o detalhe chave?

320
00:15:44,027 --> 00:15:45,360
Que a lista foi resolvido, certo?

321
00:15:45,360 --> 00:15:47,789
Seu algoritmo é errado se
sua entrada não é classificada,

322
00:15:47,789 --> 00:15:49,830
e ainda assim você estiver usando
algo como busca binária

323
00:15:49,830 --> 00:15:51,704
porque você pode saltar
direito sobre o elemento

324
00:15:51,704 --> 00:15:53,600
sem perceber que é de fato lá.

325
00:15:53,600 --> 00:15:55,600
>> Agora, o que isso pode significar, ó grande de um?

326
00:15:55,600 --> 00:15:59,117
Isto não significa que o seu algoritmo
toma uma e apenas uma etapa,

327
00:15:59,117 --> 00:16:01,200
significa apenas que é preciso uma
número constante de passos.

328
00:16:01,200 --> 00:16:04,060
Talvez seja um, talvez seja
10, talvez seja 1000,

329
00:16:04,060 --> 00:16:07,750
mas é independente do
o tamanho do problema.

330
00:16:07,750 --> 00:16:10,850
Não importa quão grande é n,
um algoritmo de tempo constante

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

332
00:16:12,747 --> 00:16:15,080
Então, o que pode ser um algoritmo
falamos ou apenas

333
00:16:15,080 --> 00:16:20,418
intuitivamente que vem a você que
sempre é executado na chamada constante de tempo?

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

335
00:16:20,918 --> 00:16:22,001
>> AUDIÊNCIA: Adicionar dois números.

336
00:16:22,001 --> 00:16:25,320
Palestrante: Adicionar dois números,
2 mais 2 é igual a 4, feito.

337
00:16:25,320 --> 00:16:27,227
Para que possa funcionar, o que mais?

338
00:16:27,227 --> 00:16:28,560
Que tal mundo mais real, certo?

339
00:16:28,560 --> 00:16:30,686
>> AUDIÊNCIA: Encontrar o
primeira coisa em uma lista.

340
00:16:30,686 --> 00:16:32,810
Palestrante: Encontrando-se o primeiro
elemento em uma lista, com certeza.

341
00:16:32,810 --> 00:16:34,540
Fomos realmente falando
sobre matrizes já,

342
00:16:34,540 --> 00:16:36,540
como fazê-lo no
primeiro elemento de uma matriz,

343
00:16:36,540 --> 00:16:40,465
não importa quanto tempo a
matriz está em código C?

344
00:16:40,465 --> 00:16:43,090
Você acabou de usar como o suporte
notação zero, bam, você está lá.

345
00:16:43,090 --> 00:16:46,120
E, de fato matrizes, como um aparte,
suporte algo geralmente conhecido

346
00:16:46,120 --> 00:16:49,240
como de acesso aleatório, de acesso aleatório
memória, porque você pode literalmente

347
00:16:49,240 --> 00:16:50,284
saltar para qualquer um só lugar.

348
00:16:50,284 --> 00:16:52,700
Nós podemos fazer isso ainda mais simples
podemos retroceder a semana de zero

349
00:16:52,700 --> 00:16:53,900
quando fizemos zero.

350
00:16:53,900 --> 00:16:59,707
Quanto tempo demorou para o
dizer bloco em risco a executar?

351
00:16:59,707 --> 00:17:00,790
Apenas tempo constante, certo?

352
00:17:00,790 --> 00:17:03,960
Diga alguma coisa, dizer
alguma coisa, não importa

353
00:17:03,960 --> 00:17:07,359
como grandes arranhões mundo é, é sempre
vai ter a mesma quantidade de tempo

354
00:17:07,359 --> 00:17:08,490
simplesmente dizer algo.

355
00:17:08,490 --> 00:17:11,089
>> Então é tempo constante,
mas o que é o outro lado?

356
00:17:11,089 --> 00:17:13,030
Se isso fosse superior
limites, o que se quer

357
00:17:13,030 --> 00:17:17,089
para descrever os limites inferiores
dos nossos algoritmos de tempo de execução?

358
00:17:17,089 --> 00:17:19,852
Quase um melhor caso
potencialmente, se quiserem,

359
00:17:19,852 --> 00:17:23,060
embora esses termos poderia se aplicar a melhor
casos, piores casos, casos de média mais

360
00:17:23,060 --> 00:17:26,359
geralmente, mas vamos focar
em limites inferiores de forma mais geral.

361
00:17:26,359 --> 00:17:31,920
O que é um algoritmo que tem
um limite inferior de n passos,

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

363
00:17:33,350 --> 00:17:36,241
Alguns fator de n passos,
que é o seu limite inferior.

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

365
00:17:36,740 --> 00:17:37,910
>> AUDIÊNCIA: Bubble sort?

366
00:17:37,910 --> 00:17:41,610
>> Palestrante: Bubble sort leva
você minimamente n passos, por quê?

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

368
00:17:42,279 --> 00:17:45,320
Por que que começam a vir até você
intuitivamente, mesmo se isso acontecer não apenas

369
00:17:45,320 --> 00:17:46,530
ainda?

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

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

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

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

374
00:17:52,360 --> 00:17:55,810
No melhor cenário possível de
bubble sort, e um monte de algoritmos,

375
00:17:55,810 --> 00:17:58,769
se eu entregar-lhe oito pessoas
que já são classificadas,

376
00:17:58,769 --> 00:18:00,560
seria insensato
para você, o algoritmo,

377
00:18:00,560 --> 00:18:02,202
para ir e voltar
mais de uma vez, certo?

378
00:18:02,202 --> 00:18:04,285
Porque assim que você
caminhar através da lista uma vez,

379
00:18:04,285 --> 00:18:08,090
você deve perceber, oh, eu não fiz nenhum
swaps, esta lista é ordenada, saia.

380
00:18:08,090 --> 00:18:09,700
Mas isso vai levar você n passos.

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

382
00:18:12,033 --> 00:18:15,240
Bubble sort é um omega,
por assim dizer, de n,

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

384
00:18:19,050 --> 00:18:23,009
é a questão fundamental não?

385
00:18:23,009 --> 00:18:24,550
Você não sabe se ele está resolvido, certo.

386
00:18:24,550 --> 00:18:26,800
Nós os seres humanos possam olhar para oito
pessoas e ser como, oh, ele é classificado,

387
00:18:26,800 --> 00:18:28,430
que não me n passos tomar, mas ele fez.

388
00:18:28,430 --> 00:18:30,810
Seus olhos, mesmo que você tipo
de ter um grande campo de visão,

389
00:18:30,810 --> 00:18:33,184
você olhou para oito elementos,
você olhou para oito pessoas,

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

391
00:18:34,610 --> 00:18:38,612
E só se eu andasse pelo todo
lista que eu percebo, sim, classificada.

392
00:18:38,612 --> 00:18:41,320
Se eu parar no meio do caminho pensando: tudo
direito, é bem resolvido, até agora,

393
00:18:41,320 --> 00:18:42,520
quais são as chances que não é ordenado?

394
00:18:42,520 --> 00:18:44,186
Isso não os de um algoritmo vai ser correto.

395
00:18:44,186 --> 00:18:46,250
Pode ser mais rápido, mas incorreto.

396
00:18:46,250 --> 00:18:48,500
>> Então, agora nós temos uma maneira de
descrevendo um limite inferior,

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

398
00:18:49,710 --> 00:18:54,565
O que é um algoritmo que tem uma menor
obrigado em seu tempo de execução de um?

399
00:18:54,565 --> 00:18:58,350
1 passo, dois passos, 10 passos, mas
constante, independente de n,

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

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

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

403
00:19:04,600 --> 00:19:05,309
>> AUDIÊNCIA: printf?

404
00:19:05,309 --> 00:19:06,183
Palestrante: O que é isso?

405
00:19:06,183 --> 00:19:07,184
AUDIÊNCIA: printf?

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

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

408
00:19:08,400 --> 00:19:10,720
Então, é preciso um número fixo de passos.

409
00:19:10,720 --> 00:19:13,170
E eu deveria agora-- agora que
estamos falando de código C

410
00:19:13,170 --> 00:19:16,040
e não arranhar, algo
como dizem, com printf,

411
00:19:16,040 --> 00:19:17,710
devemos começar a ter cuidado.

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

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

414
00:19:23,220 --> 00:19:25,530
Então, se nós agora quer escolher
em você, se você não se importa,

415
00:19:25,530 --> 00:19:29,430
tecnicamente poderíamos argumentar que printf
toma uma entrada de comprimento variável,

416
00:19:29,430 --> 00:19:32,270
e, certamente, isso pode levar mais
tempo para imprimir uma seqüência de tanto tempo,

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

418
00:19:33,560 --> 00:19:36,570
>> Então, o que se considerarmos apenas o
classificação e pesquisa exemplos?

419
00:19:36,570 --> 00:19:40,450
E sobre Mike Smith no telefone
livro, ou busca binária mais geral?

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

421
00:19:42,220 --> 00:19:45,577
Abro o livro de telefone e, bam,
há número de Mike Smith.

422
00:19:45,577 --> 00:19:46,660
Posso chamá-lo de imediato.

423
00:19:46,660 --> 00:19:49,390
>> Deu um passo, talvez duas etapas,
mas um número constante de etapas

424
00:19:49,390 --> 00:19:50,230
se eu tenho sorte.

425
00:19:50,230 --> 00:19:52,570
E, francamente, nós vimos em
Segunda-feira seu colega de classe

426
00:19:52,570 --> 00:19:54,710
ficar bastante sorte duas vezes seguidas.

427
00:19:54,710 --> 00:19:57,050
E isso era realmente constante
vez em limites inferiores

428
00:19:57,050 --> 00:20:01,280
no algoritmo em questão para encontrar
o número 50 atrás daqueles fechado

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

430
00:20:01,830 --> 00:20:06,400
>> Agora, como um aparte, se você descobrir
O que tanto grande, o limite superior

431
00:20:06,400 --> 00:20:09,310
e omega, o limite inferior,
são um na mesma, que

432
00:20:09,310 --> 00:20:11,830
é a mesma fórmula em
parênteses, você também pode

433
00:20:11,830 --> 00:20:15,170
dizer, apenas que ser extravagante,
que algo está em theta

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

435
00:20:18,270 --> 00:20:20,661
Isso significa apenas que quando grande
O e omega são os mesmos.

436
00:20:20,661 --> 00:20:21,910
Agora o que acontece com a seleção tipo?

437
00:20:21,910 --> 00:20:23,400
Vamos usar esse novo vocabulário.

438
00:20:23,400 --> 00:20:27,407
Na seleção de classificação, o que estávamos
fazendo de novo, e de novo, e de novo?

439
00:20:27,407 --> 00:20:29,990
Eu estava indo para trás e para frente através de
da lista, à procura de quem?

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
>> Assim como muitos passos, como
muitas comparações fez I

443
00:20:37,560 --> 00:20:43,250
tem que fazer, a fim de descobrir quem
o menor elemento na lista foi?

444
00:20:43,250 --> 00:20:44,437
n menos um, certo?

445
00:20:44,437 --> 00:20:47,770
Porque se eu começar com o que eu sou
dada e eu começar a comparar a ele ou ela,

446
00:20:47,770 --> 00:20:49,519
em seguida, ele ou ela, ele
ou ela, ele ou ela, eu

447
00:20:49,519 --> 00:20:52,010
só pode emparelhar elementos
juntos n menos 1 vezes.

448
00:20:52,010 --> 00:20:55,630
Assim, a seleção leva espécie semelhante
n menos passos 1 a primeira vez.

449
00:20:55,630 --> 00:20:59,540
>> Quantos passos ele me levar para
encontrar o segundo menor elemento?

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

451
00:21:02,920 --> 00:21:06,280
novamente se eu já o escolheu
ou ela e colocá-los em seu lugar.

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

453
00:21:09,270 --> 00:21:11,020
Vimos este padrão
antes, e de facto

454
00:21:11,020 --> 00:21:13,460
seleção espécie semelhante
tem um limite superior

455
00:21:13,460 --> 00:21:16,210
de n ao quadrado, se fizermos o que soma.

456
00:21:16,210 --> 00:21:19,790
Qual é o seu limite inferior, a seleção tipo?

457
00:21:19,790 --> 00:21:25,350
No mínimo, quanto tempo de seleção deve
tipo tomar, como definido na segunda-feira?

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

459
00:21:29,370 --> 00:21:30,490
Propor duas opções.

460
00:21:30,490 --> 00:21:32,360
Talvez seja n, como antes.

461
00:21:32,360 --> 00:21:35,040
Talvez seja n ao quadrado, como
é agora como o limite superior.

462
00:21:35,040 --> 00:21:35,874
>> AUDIÊNCIA: n ao quadrado.

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

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

465
00:21:37,368 --> 00:21:40,060
>> AUDIÊNCIA: Porque você tem
definir [inaudível].

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

467
00:21:41,510 --> 00:21:45,077
Pelo menos enquanto eu definido seleção espécie
era muito ingênuo, continue indo,

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

469
00:21:46,160 --> 00:21:47,770
Vá mais uma vez, encontrar o menor elemento.

470
00:21:47,770 --> 00:21:49,490
Vá mais uma vez, encontrar o menor elemento.

471
00:21:49,490 --> 00:21:51,700
Não há nenhum tipo de
otimização lá que

472
00:21:51,700 --> 00:21:54,350
pode deixar-me abortar depois
apenas n ou mais etapas.

473
00:21:54,350 --> 00:21:57,080
Assim, de facto, a selecção
tipo, omega de n ao quadrado.

474
00:21:57,080 --> 00:22:00,667
>> Que tal tipo de inserção, onde tirei
que me foi dado, e então eu estatelou-lo

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

476
00:22:01,750 --> 00:22:04,958
Então eu continuei a segunda pessoa,
estatelou-lhe no lugar certo.

477
00:22:04,958 --> 00:22:07,910
Então, a próxima pessoa, se estatelou
ele ou ela no lugar certo.

478
00:22:07,910 --> 00:22:10,537
Observe que isso é muito
linear, por assim dizer.

479
00:22:10,537 --> 00:22:12,620
Eu sou uma linha reta, eu sou
não indo e voltando,

480
00:22:12,620 --> 00:22:16,080
Eu nunca olhar para trás, realmente, mas
o que está acontecendo quando eu inseri-lo

481
00:22:16,080 --> 00:22:20,302
ou ela no início do
lista como fizemos na segunda-feira?

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

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

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

485
00:22:23,122 --> 00:22:24,830
Palestrante: Sim, isso
foi a captura, certo?

486
00:22:24,830 --> 00:22:26,746
Você pode se lembrar de
seus colegas de classe, se eles

487
00:22:26,746 --> 00:22:29,670
estavam fazendo qualquer movimento com
seus pés, que era uma operação.

488
00:22:29,670 --> 00:22:33,610
Portanto, se havia três pessoas aqui e
a nova pessoa pertencia caminho até lá,

489
00:22:33,610 --> 00:22:37,360
em uma longa fase como esta, com certeza, ele
ou ela poderia apenas ir até o fim.

490
00:22:37,360 --> 00:22:40,074
Mas, se estamos pensando em um
computador e uma matriz de memória,

491
00:22:40,074 --> 00:22:41,990
essas pessoas vão
ter para baralhar mais

492
00:22:41,990 --> 00:22:43,260
para dar espaço para essa pessoa.

493
00:22:43,260 --> 00:22:46,930
E assim que n menos um shufflings,
n menos 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
menos 3 shufflings é apenas uma espécie de
acontecendo atrás de mim, não na minha frente

495
00:22:50,660 --> 00:22:52,710
como antes, em algum sentido.

499
00:22:52,557 --> 00:22:54,640
Agora, como um lado, e como
você pode ter visto on-line

500
00:22:54,640 --> 00:22:57,699
se você começar a bisbilhotar sobre
tipos, há tantos diferentes

501
00:22:57,699 --> 00:22:59,490
lá fora, alguns deles
melhor do que os outros.

502
00:22:59,490 --> 00:23:02,200
De facto, é uma bogosort
esse é o tipo de diversão para olhar para cima.

503
00:23:02,200 --> 00:23:06,650
Bogosort leva um conjunto de
números ou dizer um baralho de cartas,

504
00:23:06,650 --> 00:23:09,870
embaralha-los aleatoriamente, e
verifica se eles estão ordenados.

505
00:23:09,870 --> 00:23:12,130
E se não, faz isso de novo.

506
00:23:12,130 --> 00:23:14,140
E se não, faz isso de novo.

507
00:23:14,140 --> 00:23:15,440
Se não, faz isso de novo.

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

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

510
00:23:19,520 --> 00:23:21,200
seu apelido é meio estúpido.

511
00:23:21,200 --> 00:23:25,180
Será eventualmente trabalhar,
espero que, com o tempo,

512
00:23:25,180 --> 00:23:28,240
mas que a quantidade de tempo
pode levar algum tempo.

513
00:23:28,240 --> 00:23:31,650
Então, se eu pudesse, vamos acelerar as coisas
-se com o exemplo de Mary Beth anteriormente,

514
00:23:31,650 --> 00:23:35,150
por ter mais alguns elementos,
mas mais dois processadores.

515
00:23:35,150 --> 00:23:37,100
Duas pessoas, se você
não me importaria de me juntar.

516
00:23:37,100 --> 00:23:40,972
Como cerca de 1 por aqui, e
vamos vai-- ninguém ali?

517
00:23:40,972 --> 00:23:41,722
Ninguém ali?

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

519
00:23:42,221 --> 00:23:44,190
Você com o preto
camisa, sim, vamos lá para baixo.

520
00:23:44,190 --> 00:23:45,000
Tudo bem, qual é o seu nome?

521
00:23:45,000 --> 00:23:45,720
>> AUDIÊNCIA: Peter.

522
00:23:45,720 --> 00:23:46,100
>> Palestrante: O que é isso?

523
00:23:46,100 --> 00:23:46,766
>> AUDIÊNCIA: Peter.

524
00:23:46,766 --> 00:23:49,450
Palestrante: Peter, David, prazer em conhecê-lo.

525
00:23:49,450 --> 00:23:53,670
Tudo bem, temos Peter aqui, se você
quer vir para a mesa por aqui.

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

527
00:23:54,550 --> 00:23:55,216
>> AUDIÊNCIA: Elena.

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

529
00:23:55,970 --> 00:23:57,030
OK, prazer em conhecê-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 precisamos de Andrew
aqui também, por favor.

533
00:24:02,290 --> 00:24:06,107
E o desafio vai
ser para ordenar um baralho de cartas.

534
00:24:06,107 --> 00:24:08,190
E se não familiar, deck
de cartões deve finalmente

535
00:24:08,190 --> 00:24:11,064
ser classificado um pouco algo como
este, onde vamos fazer os clubes, em seguida,

536
00:24:11,064 --> 00:24:13,660
as espadas, em seguida, os corações e
diamantes, de ace como um,

537
00:24:13,660 --> 00:24:15,570
todo o caminho até ao rei.

538
00:24:15,570 --> 00:24:20,890
>> As cartas que eu estou indo dar-lhe
vão ser 52 em quantidade.

539
00:24:20,890 --> 00:24:23,160
Vamos semelhante
vez que, em apenas um momento.

540
00:24:23,160 --> 00:24:26,410
Vamos jogar Andrew
na tela aqui,

541
00:24:26,410 --> 00:24:28,170
, de modo a ver como você faz isso.

542
00:24:28,170 --> 00:24:31,070
E de modo a que tudo isso
é ainda mais visível,

543
00:24:31,070 --> 00:24:33,490
Estes são os cartões que recebi na Amazônia.

544
00:24:33,490 --> 00:24:42,861
Então, eles já estão aleatoriamente
classificado, e nós estamos indo para o tempo que você.

545
00:24:42,861 --> 00:24:44,610
E nós vamos
mantê-lo real desta vez,

546
00:24:44,610 --> 00:24:47,820
então vamos tentar pressioná-lo
porque caso contrário isso vai ser entediante

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

548
00:24:48,460 --> 00:24:53,860
Se você pudesse proceder para classificar 52
elementos entre si através de alguns meios, agora.

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

550
00:25:04,710 --> 00:25:07,180
>> E mais uma vez, como vemos estes
caras fazem o que, no final

551
00:25:07,180 --> 00:25:10,200
vai produzir um óbvio
resultado, pense realmente

552
00:25:10,200 --> 00:25:12,962
como eles estão fazendo isso cada,
como você pode descrevê-lo.

553
00:25:12,962 --> 00:25:15,045
Porque mais uma vez, estas são
todos os processos, algoritmos

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

555
00:25:17,090 --> 00:25:22,349
Mas você já deve ter tido por muito tempo
intuição, muito antes de você mesmo

556
00:25:22,349 --> 00:25:24,390
pensou em tomar um
ciência da computação classe você

557
00:25:24,390 --> 00:25:27,223
poderia ter tido a intuição com
que para resolver problemas como este.

558
00:25:27,223 --> 00:25:29,560
Mas uma vez que você reconhece
os padrões e começar

559
00:25:29,560 --> 00:25:32,407
para formalizar as medidas com as quais
você está resolvendo esses problemas,

560
00:25:32,407 --> 00:25:35,490
você vai descobrir que você pode resolver muito
mais interessante e muito mais complexo

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

562
00:25:39,190 --> 00:25:42,351
Então, alguém da platéia, o que é
pelo menos um elemento do algoritmo

563
00:25:42,351 --> 00:25:43,350
que eles estão usando aqui?

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

565
00:25:44,275 --> 00:25:45,150
Palestrante: O que é isso?

566
00:25:45,150 --> 00:25:47,062
AUDIÊNCIA: por exemplo.

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

568
00:25:47,770 --> 00:25:50,630
Então, primeiro eles se aglomeram
todos os diamantes juntos

569
00:25:50,630 --> 00:25:52,560
Parece que todos os
corações juntos que parece,

570
00:25:52,560 --> 00:25:56,520
e assim por diante, sem respeito
para os números sobre os cartões.

571
00:25:56,520 --> 00:26:00,900
E agora eles aparecem, por exemplo,
a ser os por número.

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

573
00:26:06,870 --> 00:26:08,910
Muito bom.

574
00:26:08,910 --> 00:26:12,370
>> Tudo bem, então o que vai
ser o passo final, então aqui?

575
00:26:12,370 --> 00:26:16,950
Uma vez que temos quatro naipes classificadas, o que
fazer o que precisamos fazer para as quatro pilhas

576
00:26:16,950 --> 00:26:20,059
, a fim de alcançar um
classificadas convés, pura e simplesmente?

577
00:26:20,059 --> 00:26:21,350
Então, precisamos mesclá-los novamente.

578
00:26:21,350 --> 00:26:25,160
>> Portanto, há uma idéia interessante que
novamente, ouso dizer, é muito intuitivo mesmo

579
00:26:25,160 --> 00:26:28,140
se você nunca poderia ter esbofeteado
esse tipo de rótulo nele.

580
00:26:28,140 --> 00:26:31,900
Esta noção fundamental de divisão
o problema não em metade deste tempo,

581
00:26:31,900 --> 00:26:33,410
mas, pelo menos, em quatro pedaços.

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

583
00:26:36,810 --> 00:26:40,480
isoladamente uns dos outros,
e então 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
Tudo bem, uma grande rodada
de aplausos, se pudéssemos.

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

588
00:26:56,480 --> 00:26:59,740
>> Palestrante: Eu não tenho idéia o que você vai
ver com isso, mas aqui vai.

589
00:26:59,740 --> 00:27:01,690
Muito obrigado.

590
00:27:01,690 --> 00:27:04,660
Então vamos ver, dois minutos
e oito segundos;

591
00:27:04,660 --> 00:27:07,490
se você gostaria de desafiar os seus amigos.

592
00:27:07,490 --> 00:27:12,160
O que então vai
ser um tirar este

593
00:27:12,160 --> 00:27:13,830
que podemos aproveitar de forma mais geral?

594
00:27:13,830 --> 00:27:16,080
Bem, acho que volta para
esse conjunto de números,

595
00:27:16,080 --> 00:27:19,060
e acho que volta agora a alguns dos
pseudocódigo nós escrevemos no passado,

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 circunstâncias, em pseudocódigo I
enumerou uma maneira mais metódica

598
00:27:25,150 --> 00:27:28,400
de descrever como eu fiz um muito intuitivo
algoritmo humano de dividir o telefone

599
00:27:28,400 --> 00:27:31,650
livro pela metade, repetir, repetir, repetir,
até eu encontrar alguém como Mike Smith,

600
00:27:31,650 --> 00:27:33,790
se ele é de fato no livro de telefone.

601
00:27:33,790 --> 00:27:37,610
>> Mas eu meio que usei o que eu vou chamar
uma abordagem muito iterativo aqui,

602
00:27:37,610 --> 00:27:42,160
em particular aviso linha 8 e linha 11.

603
00:27:42,160 --> 00:27:46,750
Essas são evidências de uma iterativo
abordagem, uma abordagem looping,

604
00:27:46,750 --> 00:27:49,040
porque é exatamente
o comportamento que eles induzem.

605
00:27:49,040 --> 00:27:52,910
Essas linhas tanto dizer ir para
linha de três, e você pode tipo de

606
00:27:52,910 --> 00:27:55,140
pensar que, em sua
olho da mente como sendo um loop.

607
00:27:55,140 --> 00:27:59,080
Ele está dizendo a você para voltar-se para a etapa
três e repetir, de novo, e de novo,

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

609
00:28:00,010 --> 00:28:04,410
>> Mas o que se aproveitar uma idéia-chave
aqui que nós não pela última vez,

610
00:28:04,410 --> 00:28:10,280
e simplificar a linha 8 e
linha 11 e seus vizinhos

611
00:28:10,280 --> 00:28:12,840
como apenas isso, em amarelo.

612
00:28:12,840 --> 00:28:16,480
Não é, fundamentalmente, encurtando
pseudocódigo muito,

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

614
00:28:20,530 --> 00:28:24,220
O que eu estou dizendo agora
no passo 7, na etapa 10,

615
00:28:24,220 --> 00:28:29,140
é a busca de Mike
da mesma forma exata,

616
00:28:29,140 --> 00:28:31,580
mas apenas no lado esquerdo
metade ou metade direita.

617
00:28:31,580 --> 00:28:33,420
>> Assim, em outras palavras, se
Eu começar a partir de uma etapa,

618
00:28:33,420 --> 00:28:36,150
pegar livro de telefone, aberto a meio
do livro de telefone, olhar para os nomes,

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

620
00:28:39,010 --> 00:28:44,340
Se Smith é anterior no livro, passo sete
procurar Mike na metade esquerda do livro.

621
00:28:44,340 --> 00:28:47,130
Mas esse tipo de sente como
isso está me deixando pendurado, certo?

622
00:28:47,130 --> 00:28:49,240
Em amarelo, é uma
instrução, mas como faço

623
00:28:49,240 --> 00:28:51,870
procurar o Mike no esquerdo
metade do livro de telefone?

624
00:28:51,870 --> 00:28:54,210
Onde é que eu tenho uma
algoritmo com o qual eu

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

626
00:28:57,100 --> 00:28:58,980
Bem, isso está nos olhando na cara.

627
00:28:58,980 --> 00:29:03,090
Eu posso literalmente usar exatamente o mesmo
programa vai efetivamente até o topo

628
00:29:03,090 --> 00:29:06,490
novamente e re-execução
as mesmas linhas de código.

629
00:29:06,490 --> 00:29:10,610
>> Assim, mesmo que este deve sentir-se
como um pouco de uma definição cíclico

630
00:29:10,610 --> 00:29:13,480
onde você está respondendo a alguém é
Pergunta por apenas uma espécie de perguntar

631
00:29:13,480 --> 00:29:15,990
a mesma pergunta novamente,
como por que, por que, por quê?

632
00:29:15,990 --> 00:29:21,580
A realidade é porque temos codificado
um par de linhas especiais, escalão 4,

633
00:29:21,580 --> 00:29:25,320
que é um caso, e passo 12, que
é efetivamente um outro ramo,

634
00:29:25,320 --> 00:29:30,120
porque temos essas medidas paliativas,
este algoritmo irá terminar se

635
00:29:30,120 --> 00:29:32,050
encontrar Mike, ou se não o fizermos.

636
00:29:32,050 --> 00:29:36,810
Mas na etapa 7 e 10 agora, temos
o que vamos chamar de um algoritmo recursivo.

637
00:29:36,810 --> 00:29:40,420
E recursão é de fato uma idéia poderosa
isso é um pouco de mente dobra no início,

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
olharmos para, pelo menos na classe formalmente.

640
00:29:46,600 --> 00:29:50,040
E é fundamentalmente diferente
daqueles três últimos, e, certamente,

641
00:29:50,040 --> 00:29:52,140
quatro últimos se incluem bogosort.

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

643
00:29:54,810 --> 00:30:00,170
Quando a entrada de n elementos, então dado
uma matriz de tamanho n, se n é inferior a 2,

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

645
00:30:01,040 --> 00:30:03,610
Então, por que eu tenho que
verificação de sanidade em primeiro lugar?

646
00:30:03,610 --> 00:30:09,477
Qual é a implicação se eu entregar-lhe
uma matriz cujo comprimento n seja inferior a 2?

647
00:30:09,477 --> 00:30:11,060
Ele já está classificado, obviamente, não é?

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

649
00:30:13,640 --> 00:30:15,180
classificadas porque é
a única coisa que existe.

650
00:30:15,180 --> 00:30:18,138
Ou, é de tamanho zero, o que significa
não há nada para resolver, por isso, natureza

651
00:30:18,138 --> 00:30:18,720
ele é classificado.

652
00:30:18,720 --> 00:30:20,410
Apenas há nada de errado lá.

653
00:30:20,410 --> 00:30:22,310
Então, esse é o nosso chamado caso base.

654
00:30:22,310 --> 00:30:24,440
>> Isto é semelhante em espírito
ao que fizemos com Mike.

655
00:30:24,440 --> 00:30:26,023
Se Mike no livro de telefone, ligue para ele.

656
00:30:26,023 --> 00:30:27,740
Se ele não estiver lá, desista.

657
00:30:27,740 --> 00:30:31,240
É um chamado processo de base, para se certificar
este algoritmo, no final do dia

658
00:30:31,240 --> 00:30:33,540
vai parar em determinadas circunstâncias.

659
00:30:33,540 --> 00:30:37,890
>> Mas aqui está o salto de fé agora, mais,
ordenar a metade esquerda dos elementos,

660
00:30:37,890 --> 00:30:39,740
em seguida, classificar o direito
metade dos elementos,

661
00:30:39,740 --> 00:30:41,189
e em seguida, mesclar as metades classificados.

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

663
00:30:43,230 --> 00:30:46,900
Pedi-lhe para classificar
n elementos, e eu sou

664
00:30:46,900 --> 00:30:50,712
dizendo: OK, faça isso por classificação
a esquerda e para a triagem da direita.

665
00:30:50,712 --> 00:30:52,420
Mas eu estou dizendo uma
outra coisa, e esta

666
00:30:52,420 --> 00:30:55,530
é o tema central parece
na intuição, até agora,

667
00:30:55,530 --> 00:30:57,380
há esta terceira etapa de fusão.

668
00:30:57,380 --> 00:31:00,430
Que embora
Parece tão burro em espírito,

669
00:31:00,430 --> 00:31:02,320
como apenas mesclar coisas
juntos, parece

670
00:31:02,320 --> 00:31:05,380
ser um passo fundamental para o
remontagem de dois problemas que

671
00:31:05,380 --> 00:31:07,330
foram divididos em última instância, pela metade.

672
00:31:07,330 --> 00:31:12,090
>> Então, merge sort, vamos fazer isso, se você
humor me, com mais uma demonstração,

673
00:31:12,090 --> 00:31:14,730
apenas para que tenhamos alguma
números de trabalhar.

674
00:31:14,730 --> 00:31:19,470
Posso trocar oito estresse
bolas para oito pessoas?

675
00:31:19,470 --> 00:31:29,320
Tudo bem, que tal vocês três, vocês quatro
nesta seção, cinco, seis, e vamos

676
00:31:29,320 --> 00:31:30,720
não 7, 8, vamos para cima.

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

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

679
00:31:36,520 --> 00:31:38,640
Minus 8, lá vamos nós, mais 1.

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

681
00:31:39,150 --> 00:31:42,000
Todos vêm a direita em cima, vamos
rapidamente lhe dar números.

682
00:31:42,000 --> 00:31:50,800
O número dois, número três, número quatro,
número cinco, seis, sete, e oito.

683
00:31:50,800 --> 00:31:52,140
Eu fiz oito corretamente desta vez.

684
00:31:52,140 --> 00:31:56,390
>> OK, então vá em frente se você pudesse, e
vamos classificar na ordem original

685
00:31:56,390 --> 00:31:59,810
que tivemos ontem que parecia
assim, se você não se importar.

686
00:31:59,810 --> 00:32:03,620
E vamos fazê-lo na frente da tabela.

687
00:32:03,620 --> 00:32:06,510
Tudo bem, então merge sort.

688
00:32:06,510 --> 00:32:08,820
Este é o lugar onde ele vai
para chegar bem interessante,

689
00:32:08,820 --> 00:32:12,800
porque parece que estou me dando
muito menos informação hoje.

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

691
00:32:15,149 --> 00:32:18,440
e é, obviamente, não inferior a dois, é
oito, então eu tenho um pouco mais de trabalho para fazer.

692
00:32:18,440 --> 00:32:21,140
Então, agora nós mentalmente como uma classe
estão agora na outra filial,

693
00:32:21,140 --> 00:32:22,540
o que significa que três passos.

694
00:32:22,540 --> 00:32:25,017
Primeiro, tenho de resolver o
metade esquerda dos elementos.

695
00:32:25,017 --> 00:32:26,350
Então como é que eu vou fazer isso?

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

697
00:32:28,950 --> 00:32:30,700
você não tem que
mover fisicamente, e estou

698
00:32:30,700 --> 00:32:33,180
vai centrar-se apenas na
metade esquerda dos elementos aqui.

699
00:32:33,180 --> 00:32:36,770
Então, como eu faço para classificar
uma lista agora do tamanho de quatro?

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

701
00:32:38,730 --> 00:32:42,580
Primeiro eu verifico é n inferior a dois, não,
para que eu prossiga para o bloco mais novo.

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

703
00:32:43,900 --> 00:32:45,608
>> Portanto, agora de novo, mentalmente,
e é aí que

704
00:32:45,608 --> 00:32:49,550
você tem que acumular um monte de
história mental, se você quiser.

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

706
00:32:51,940 --> 00:32:57,000
Tudo bem, então agora eu chamo o meu mesmo merge
algoritmo de classificação, é n inferior a dois?

707
00:32:57,000 --> 00:33:00,590
Não, é dois, então eu tenho que classificar
a metade da esquerda, e a metade direita.

708
00:33:00,590 --> 00:33:02,042
Então, vamos lá, ordenar a metade esquerda.

709
00:33:02,042 --> 00:33:03,750
Por que você não apenas
dar um passo a frente.

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

711
00:33:04,415 --> 00:33:04,860
>> AUDIÊNCIA: Darren.

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

713
00:33:05,260 --> 00:33:06,040
Dan deu um passo a frente.

714
00:33:06,040 --> 00:33:06,748
>> AUDIÊNCIA: Darren.

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

716
00:33:09,000 --> 00:33:10,090
Você disse Darren ou Dan?

717
00:33:10,090 --> 00:33:10,550
>> AUDIÊNCIA: Darren.

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

719
00:33:11,216 --> 00:33:14,422
OK, Darren tem intensificado
a frente e que é agora classificada.

720
00:33:14,422 --> 00:33:16,130
E isso é quase uma
reivindicação inane, certo?

721
00:33:16,130 --> 00:33:18,862
Eu realmente não parece estar a atingir
nada, mas vamos continuar.

722
00:33:18,862 --> 00:33:20,820
Agora deixe-me ordenar a direita
metade dos elementos.

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

724
00:33:21,200 --> 00:33:21,690
>> AUDIÊNCIA: Lucas.

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

726
00:33:22,273 --> 00:33:23,400
Vamos lá, um passo à frente.

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 classificado e
a metade da direita é agora classificada,

729
00:33:28,570 --> 00:33:30,770
mas, novamente, há um passo-chave aqui.

730
00:33:30,770 --> 00:33:32,940
O que eu preciso fazer no próximo?

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

732
00:33:33,941 --> 00:33:36,648
Agora vamos ter apenas
todos trás e para a frente desta maneira,

733
00:33:36,648 --> 00:33:38,620
porque eu meio que preciso
algum espaço de rascunho.

734
00:33:38,620 --> 00:33:40,411
É quase como se estes
caras estão sobre uma mesa,

735
00:33:40,411 --> 00:33:42,460
e eu preciso de algum espaço
para movê-los em.

736
00:33:42,460 --> 00:33:44,170
Então eu vou para mesclar
vocês olhando

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

738
00:33:45,960 --> 00:33:48,740
E que, obviamente, vem em primeiro lugar,
metade esquerda ou metade direita?

739
00:33:48,740 --> 00:33:52,710
Então metade direita, então vamos mover Lucas sobre
aqui a posição original de Darren.

740
00:33:52,710 --> 00:33:57,640
E agora fundir a sua metade esquerda em,
Darren vai mover para a direita lá.

741
00:33:57,640 --> 00:33:59,750
>> Então, parece que quase
um efeito bubble sort,

742
00:33:59,750 --> 00:34:02,482
mas o meu algoritmo fundamental
muito diferente desta vez.

743
00:34:02,482 --> 00:34:04,815
Mas agora é onde as coisas ficam um
pouco chato, porque você

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

745
00:34:06,810 --> 00:34:09,893
Acabei fundiu as metades ordenadas,
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
Eu tenho que classificar a metade direita, certo?

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

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

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

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

752
00:34:23,430 --> 00:34:27,941
significa que o próximo passo é o tipo
metade direita da metade esquerda.

753
00:34:27,941 --> 00:34:29,649
Tudo bem, então vamos
fazer isso mais rapidamente.

754
00:34:29,649 --> 00:34:33,282
Tudo bem, seis, eu vou reclamar
você está agora resolvido, vamos para a frente.

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

756
00:34:33,990 --> 00:34:34,589
>> AUDIÊNCIA: Adriano.

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

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

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

760
00:34:36,450 --> 00:34:37,080
>> AUDIÊNCIA: Alex.

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

762
00:34:38,379 --> 00:34:40,750
Meia esquerda, meia direita,
qual é o passo final?

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

764
00:34:41,250 --> 00:34:44,310
Muito trivial, por isso estou
vai fundir em seis,

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

766
00:34:46,930 --> 00:34:49,530
E agora perceber isso é
um takeaway útil, o que

767
00:34:49,530 --> 00:34:53,930
é agora verdade sobre a metade esquerda da
lista, independentemente da forma como começamos?

768
00:34:53,930 --> 00:34:55,090
Ele está classificada.

769
00:34:55,090 --> 00:34:57,750
>> Agora ele não está classificada em
o grande esquema das coisas,

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

771
00:35:00,250 --> 00:35:04,100
Agora, o que passo sou eu em se manter
rebobinar como a história começou?

772
00:35:04,100 --> 00:35:05,680
Agora eu tenho que classificar a metade direita.

773
00:35:05,680 --> 00:35:07,630
Portanto, agora estamos no caminho de volta
o começo da história,

774
00:35:07,630 --> 00:35:08,921
e vamos fazer isso mais rapidamente.

775
00:35:08,921 --> 00:35:11,320
Então eu vou para classificar a
metade direita da lista inteira.

776
00:35:11,320 --> 00:35:13,060
Qual é o próximo passo?

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

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

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

780
00:35:19,590 --> 00:35:20,230
>> AUDIÊNCIA: Omar.

781
00:35:20,230 --> 00:35:21,970
>> Palestrante: Omar, um passo à frente, feito.

782
00:35:21,970 --> 00:35:22,860
Metade esquerda está classificada.

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

784
00:35:23,330 --> 00:35:23,820
>> AUDIÊNCIA: Chris.

785
00:35:23,820 --> 00:35:25,620
>> Palestrante: Chris, dar um passo
para a frente, você está agora classificada.

786
00:35:25,620 --> 00:35:27,010
Qual é a chave passo agora?

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

788
00:35:27,510 --> 00:35:30,509
Então, um vai se fundir em lugar
aqui, se você pudesse dar um passo para trás,

789
00:35:30,509 --> 00:35:32,930
e três vai
dar um passo atrás, se fundem.

790
00:35:32,930 --> 00:35:38,080
Assim, a metade esquerda da
metade direita, agora está resolvido.

791
00:35:38,080 --> 00:35:41,747
Francamente, este algoritmo se sente como nós
estão gastando muito mais tempo do que antes,

792
00:35:41,747 --> 00:35:44,830
mas se não fez isso em tempo real, vamos
ver o que os delivery vai ser.

793
00:35:44,830 --> 00:35:47,970
Agora estou aqui, certo
a metade do lado direito,

794
00:35:47,970 --> 00:35:50,170
deixe-me ir em frente e resolver a metade esquerda.

795
00:35:50,170 --> 00:35:51,482
Passo em frente, o que é o seu nome?

796
00:35:51,482 --> 00:35:52,190
AUDIÊNCIA: Ramsey.

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

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

799
00:35:53,570 --> 00:35:54,200
>> AUDIÊNCIA: Marina.

800
00:35:54,200 --> 00:35:57,033
>> Palestrante: Marina está agora classificada como
Bem, se você der um passo para a frente.

801
00:35:57,033 --> 00:36:00,690
Chave passo aqui agora é fundir, eu sou
vai arrancar das minhas duas listas,

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

803
00:36:01,720 --> 00:36:05,150
Cinco vai vir em primeiro lugar,
e sete vai vir em seguida.

804
00:36:05,150 --> 00:36:06,410
E, novamente, isso é proposital.

805
00:36:06,410 --> 00:36:08,535
O fato de que eles estão levando
passos para a frente e para trás

806
00:36:08,535 --> 00:36:12,997
é utilizado para representar que não podemos
fazer esse algoritmo no lugar com a mesma facilidade

807
00:36:12,997 --> 00:36:15,830
como bubble sort, e seleção de tipo,
e inserção tipo em que apenas

808
00:36:15,830 --> 00:36:16,960
manteve trocando pessoas.

809
00:36:16,960 --> 00:36:19,940
Eu literalmente precisa de um tipo
de papel de rascunho em que

810
00:36:19,940 --> 00:36:21,827
para colocar essas pessoas
enquanto eu faço a fusão,

811
00:36:21,827 --> 00:36:23,410
e então eu posso colocá-los de volta no lugar.

812
00:36:23,410 --> 00:36:27,260
E isso é fundamental, porque eu estou usando um
novo recurso, o espaço, não apenas tempo.

813
00:36:27,260 --> 00:36:28,270
>> OK, isso é incrível.

814
00:36:28,270 --> 00:36:32,050
Metade esquerda é classificado, a metade direita é
, agora que a chave fusão etapa de classificação.

815
00:36:32,050 --> 00:36:33,450
Como é que eu vou mesclar essa?

816
00:36:33,450 --> 00:36:35,470
Então, se você seguir o meu
mão esquerda e mão direita,

817
00:36:35,470 --> 00:36:38,930
Eu vou apontar a minha mão esquerda
na metade esquerda, a mão direita

818
00:36:38,930 --> 00:36:42,680
na metade direita, e agora eu tenho que
decidir passo a passo quem se fundir em.

819
00:36:42,680 --> 00:36:44,650
Que, obviamente, vem em primeiro lugar?

820
00:36:44,650 --> 00:36:45,150
Número um.

821
00:36:45,150 --> 00:36:47,327
Então venha para cá,
aqui está o nosso bloco de rascunho.

822
00:36:47,327 --> 00:36:49,910
Então, agora o número um, e aviso
o que vou fazer com a minha mão direita,

823
00:36:49,910 --> 00:36:54,152
Vou passar a minha mão direita
passar por cima ao ponto número três,

824
00:36:54,152 --> 00:36:55,860
e agora eu tenho que fazer
a mesma decisão.

825
00:36:55,860 --> 00:36:58,387
E, na verdade, ficar bem na
frente de Luke aqui se você pudesse,

826
00:36:58,387 --> 00:36:59,720
porque este é o nosso bloco de rascunho.

827
00:36:59,720 --> 00:37:00,610
Então, quem vem a seguir?

828
00:37:00,610 --> 00:37:05,000
Temos Luke com o número dois
ou Chris com o número três.

829
00:37:05,000 --> 00:37:07,460
Obviamente Luke, número
dois, para que você venha aqui.

830
00:37:07,460 --> 00:37:11,270
>> Mas minha mão esquerda agora vai
ser incrementado para apontar para Darren,

831
00:37:11,270 --> 00:37:15,160
e aqui está a chave tirar com
fusão, eu vou continuar fazendo isso,

832
00:37:15,160 --> 00:37:17,340
Obviamente, se você tipo
de seguir a lógica.

833
00:37:17,340 --> 00:37:19,670
Mas minhas mãos nunca são
indo para ir para trás,

834
00:37:19,670 --> 00:37:23,861
o que significa que eu estou sempre apenas movendo-se para
esquerda com o meu processo de fusão,

835
00:37:23,861 --> 00:37:26,360
e que vai ser a chave para
nossa análise em apenas um momento.

836
00:37:26,360 --> 00:37:27,859
>> Então agora vamos terminar isso rapidamente.

837
00:37:27,859 --> 00:37:31,650
Então, três vem a seguir,
depois quatro vem a seguir,

838
00:37:31,650 --> 00:37:38,750
e agora vem a seguir cinco, depois seis,
e sete, e, finalmente, oito.

839
00:37:38,750 --> 00:37:42,960
Parece que o algoritmo mais lento
ainda, mas não se realmente

840
00:37:42,960 --> 00:37:45,510
executá-lo, ao mesmo tipo
de velocidade de clock, por assim

841
00:37:45,510 --> 00:37:48,106
dizer, com a mesma
tique-taque do relógio como antes.

842
00:37:48,106 --> 00:37:48,605
Por quê?

843
00:37:48,605 --> 00:37:51,100
Bem, Vamos dar uma
olhar para o resultado final.

844
00:37:51,100 --> 00:37:56,990
>> Vamos voltar aqui, deixe-me
puxe uma demonstração visual

845
00:37:56,990 --> 00:37:59,030
do que acabamos de fazer.

846
00:37:59,030 --> 00:38:06,110
Aproximar-se aqui, neste
página aqui, dizendo Firefox

847
00:38:06,110 --> 00:38:08,200
que queremos fila
até neste campo, vamos

848
00:38:08,200 --> 00:38:11,260
dizer bubble sort, com o qual
agora estamos bem familiarizados,

849
00:38:11,260 --> 00:38:14,130
tipo de selecção, que é outra
bastante um simples,

850
00:38:14,130 --> 00:38:18,250
e agora merge sort de hoje, que
será o nosso clímax final.

851
00:38:18,250 --> 00:38:21,530
A razão que levou muito mais tempo
aqui com os seres humanos e me verbalmente é,

852
00:38:21,530 --> 00:38:23,480
obviamente, eu estou explicando cada passo.

853
00:38:23,480 --> 00:38:26,920
Mas se você simplesmente executar este, muito
como fizemos bubble sort e seleção

854
00:38:26,920 --> 00:38:30,890
tipo, não só visualmente, relógio
o quanto de forma mais eficiente

855
00:38:30,890 --> 00:38:33,330
essa alavancagem de
divisão e conquista

856
00:38:33,330 --> 00:38:39,150
pode ser, quando aplicado a um conjunto de dados que é
nem mesmo tamanho oito, mas mesmo muito,

857
00:38:39,150 --> 00:38:39,970
muito maior.

858
00:38:39,970 --> 00:38:44,585
Eu dou-lhe merge sort, lado a
lado com estes outros algoritmos.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Isso vai ficar doloroso
rapidamente, eo final

861
00:38:58,530 --> 00:39:00,890
não é particularmente climático,
eles simplesmente acabar ordenados.

862
00:39:00,890 --> 00:39:05,280
Mas a chave tirar é que
Veja o quanto mais rápido merge sort

863
00:39:05,280 --> 00:39:08,110
era, a menos que você acha que eu sou
apenas uma espécie de mexer com você.

864
00:39:08,110 --> 00:39:13,100
Se fizermos isso uma última vez,
Vamos recarregar isso, vamos voltar

865
00:39:13,100 --> 00:39:14,960
e escolha bubble sort,
e apenas por diversão,

866
00:39:14,960 --> 00:39:17,330
Vamos escolher a inserção
tipo, apenas para uma boa medida.

867
00:39:17,330 --> 00:39:20,020
E desta vez, mais uma vez, vamos
escolher merge sort e vamos

868
00:39:20,020 --> 00:39:21,595
realmente executar estes lado a lado.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> E não é, na verdade, um golpe de sorte.

871
00:39:26,930 --> 00:39:31,140
O que eu fiz de forma eficaz é que eu tenho
repartiram a minha entrada no meio, mais uma vez,

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 há apenas tantas vezes você pode
dividir sua entrada em metades, esquerda

874
00:39:35,590 --> 00:39:36,240
e à direita.

875
00:39:36,240 --> 00:39:39,425
Qual é a fórmula que continuo vendo
que descreve a divisão em 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
>> AUDIÊNCIA: Log n.

878
00:39:41,890 --> 00:39:42,760
>> Palestrante: Log n.

879
00:39:42,760 --> 00:39:46,300
Mas depois há um outro grande passo,
este algoritmo não é log n passos.

880
00:39:46,300 --> 00:39:48,992
Se só foram log n passos,
estaríamos no mesmo problema

881
00:39:48,992 --> 00:39:51,200
como antes, onde não podemos ser
Certifique-se que está tudo resolvido.

882
00:39:51,200 --> 00:39:54,480
Você tem que olhar minimamente n elementos
para ter certeza de n elementos são ordenados,

883
00:39:54,480 --> 00:39:55,950
caso contrário, é um salto de fé.

884
00:39:55,950 --> 00:39:59,810
>> Então é log minimamente n passos, mas
o que acontece com este passo chave fusão

885
00:39:59,810 --> 00:40:04,370
onde eu fundiu minha metade esquerda e direita
meio e atravessou o palco?

886
00:40:04,370 --> 00:40:06,980
Quantos passos é que se fundir?

887
00:40:06,980 --> 00:40:10,150
É n, mas não o fiz apenas
mesclar o tempo final.

888
00:40:10,150 --> 00:40:15,089
Em cada uma dessas chamadas aninhadas, em cada
dessas fusões aninhados, eu ainda classificadas.

889
00:40:15,089 --> 00:40:18,380
Eu fundiu esses dois caras, então estes dois
caras, então esses dois caras e assim por diante.

890
00:40:18,380 --> 00:40:19,955
>> Então eu fiz a fusão de novo, e de novo.

891
00:40:19,955 --> 00:40:20,580
Quantas vezes?

892
00:40:20,580 --> 00:40:23,510
Então toda vez que eu dividia o
lista pela metade, eu fiz uma mesclagem.

893
00:40:23,510 --> 00:40:25,460
Divida a lista ao meio, fazer uma mesclagem.

894
00:40:25,460 --> 00:40:28,570
Portanto, se a divisão a lista
pode ser feito de log n vezes,

895
00:40:28,570 --> 00:40:33,880
e em última análise, a fusão tem n
etapas, o que pode ser agora o superior

896
00:40:33,880 --> 00:40:37,000
encadernado pela execução
tempo do nosso algoritmo?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> E, de fato, é o que
nós conseguimos aqui.

899
00:40:40,560 --> 00:40:44,650
Então, a sensação que você vê quando visualmente
essas três coisas correm lado a lado

900
00:40:44,650 --> 00:40:47,930
n é quadrado contra n
quadrado contra o registro n n.

901
00:40:47,930 --> 00:40:51,010
Que fundamentalmente nós vamos ver,
Não só, mas hoje em dia, no futuro,

902
00:40:51,010 --> 00:40:52,760
é muito mais rápido.

903
00:40:52,760 --> 00:40:56,010
Uma salva de palmas para esses caras,
Eu vou recompensá-los com bolas de stress.

904
00:40:56,010 --> 00:41:00,260
Vamos encerrar aqui hoje, e
vamos vê-lo na segunda-feira.

905
00:41:00,260 --> 00:41:02,255