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

2
00:00:11,904 --> 00:00:12,910
>> PROFESSOR: Tudo bem.

3
00:00:12,910 --> 00:00:16,730
Este é CS50 e este é
o final de semana três.

4
00:00:16,730 --> 00:00:20,230
Então, nós estamos aqui hoje, não em Sanders
Theater, em vez de Weidner Library.

5
00:00:20,230 --> 00:00:23,170
Dentro dos quais é um estúdio
conhecido como Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
ou digamos Estúdio H, ou deve
nós dizer-- se você gostou que piada,

7
00:00:28,310 --> 00:00:30,540
é, na verdade, a partir de
colega, Mark, em linha,

8
00:00:30,540 --> 00:00:32,420
que sugeriu tanto via Twitter.

9
00:00:32,420 --> 00:00:34,270
Agora, o que é legal sobre
estar aqui em um estúdio

10
00:00:34,270 --> 00:00:38,410
é que eu estou cercado por estes do verde
paredes, uma tela verde ou chromakey,

11
00:00:38,410 --> 00:00:43,290
por assim dizer, o que significa que de CS50
equipe de produção, sem saber para mim

12
00:00:43,290 --> 00:00:47,380
agora, poderia estar colocando
me mais em qualquer lugar do mundo,

13
00:00:47,380 --> 00:00:48,660
por bem ou por mal.

14
00:00:48,660 --> 00:00:51,800
>> Agora, o que temos pela frente, conjunto de problemas
dois está em suas mãos para esta semana,

15
00:00:51,800 --> 00:00:53,830
mas com conjunto de problemas
três da próxima semana,

16
00:00:53,830 --> 00:00:56,600
você será desafiado com
a chamada de jogo 15,

17
00:00:56,600 --> 00:00:58,960
um favor de partido antiga que
você pode se lembrar de receber

18
00:00:58,960 --> 00:01:02,030
como uma criança que tem um grupo inteiro
de números que pode deslizar para cima, para baixo,

19
00:01:02,030 --> 00:01:05,790
esquerda e direita, e há um gap
dentro do quebra-cabeça, no qual você

20
00:01:05,790 --> 00:01:07,840
pode realmente deslizar as peças de quebra-cabeça.

21
00:01:07,840 --> 00:01:11,150
Em última análise, você receber essa
quebra-cabeça em alguma ordem semi aleatório,

22
00:01:11,150 --> 00:01:12,940
e o objectivo é a
classificá-lo de cima para baixo,

23
00:01:12,940 --> 00:01:16,310
esquerda para a direita, a partir de um
todo o caminho até a 15.

24
00:01:16,310 --> 00:01:19,360
>> Infelizmente, a aplicação
você terá em mãos

25
00:01:19,360 --> 00:01:21,590
vai ser software
base, não fisicamente.

26
00:01:21,590 --> 00:01:25,280
Você está realmente vai ter que escrever
código com o qual um estudante ou usuário pode

27
00:01:25,280 --> 00:01:26,760
jogar o jogo de 15.

28
00:01:26,760 --> 00:01:29,030
E, de fato, em que o hacker
edição do jogo de 15,

29
00:01:29,030 --> 00:01:32,155
você vai ser um desafio para implementar,
não apenas o jogo desta velha escola

30
00:01:32,155 --> 00:01:35,010
jogo, mas sim a solução
disso, a implementação de modo deus,

31
00:01:35,010 --> 00:01:38,280
por assim dizer, que realmente
resolve o enigma para o ser humano,

32
00:01:38,280 --> 00:01:41,080
fornecendo-lhes dica,
depois dica, depois dica.

33
00:01:41,080 --> 00:01:42,280
Então, mais sobre isso na próxima semana.

34
00:01:42,280 --> 00:01:43,720
Mas isso é o que está por vir.

35
00:01:43,720 --> 00:01:47,610
>> Por agora lembrar que no início desta semana
tivemos este momento de angústia, se quiserem,

36
00:01:47,610 --> 00:01:52,560
pelo que o melhor que estávamos fazendo triagem
wise foi um limite superior de grande o de n

37
00:01:52,560 --> 00:01:53,210
quadrado.

38
00:01:53,210 --> 00:01:56,520
Em outras palavras, bubble sort,
tipo de seleção, ordenação por inserção,

39
00:01:56,520 --> 00:01:59,120
todos eles, enquanto diferente
na sua implementação,

40
00:01:59,120 --> 00:02:03,480
transformou em um n ao quadrado que funciona
tempo no pior caso.

41
00:02:03,480 --> 00:02:06,010
E nós geralmente assumem que
o pior caso para classificar

42
00:02:06,010 --> 00:02:08,814
é aquele que seus inputs
são completamente para trás.

43
00:02:08,814 --> 00:02:11,980
E, de fato, levou bastante a poucos passos
para implementar cada um desses algoritmos.

44
00:02:11,980 --> 00:02:15,110
>> Agora no final da aula
recall, nós comparamos bubble sort

45
00:02:15,110 --> 00:02:19,390
contra a espécie de selecção contra uma outra
que chamamos de merge sort na época,

46
00:02:19,390 --> 00:02:22,120
e proponho que ele está tomando
vantagem de uma lição de semana

47
00:02:22,120 --> 00:02:24,060
zero, dividir e conquistar.

48
00:02:24,060 --> 00:02:28,810
E de alguma forma alcançar algum tipo de
logarítmica tempo de funcionamento, em última análise,

49
00:02:28,810 --> 00:02:31,024
em vez de algo
isso é puramente quadrática.

50
00:02:31,024 --> 00:02:33,440
E não é bastante logarítmica,
é um pouco mais do que isso.

51
00:02:33,440 --> 00:02:36,520
Mas se você se lembra de classe,
foi muito, muito mais rápido.

52
00:02:36,520 --> 00:02:38,210
Vamos dar uma olhada onde paramos.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Bubble sort contra seleção
tipo contra merge sort.

55
00:02:45,370 --> 00:02:47,700
Agora eles estão todos correndo, em
teoria, ao mesmo tempo.

56
00:02:47,700 --> 00:02:50,510
A CPU está sendo executado na mesma velocidade.

57
00:02:50,510 --> 00:02:54,990
Mas você pode sentir como chato isso
está indo muito rapidamente para se tornar,

58
00:02:54,990 --> 00:02:58,790
e quão rápido, quando injetamos
um pouco de algoritmos de semana de zero,

59
00:02:58,790 --> 00:03:00,080
podemos acelerar as coisas.

60
00:03:00,080 --> 00:03:01,630
>> Assim, tipo marca parece incrível.

61
00:03:01,630 --> 00:03:05,220
Como podemos aproveitá-lo, a fim
para ordenar os números mais rapidamente.

62
00:03:05,220 --> 00:03:07,140
Bem, vamos pensar de volta
para um ingrediente que nós

63
00:03:07,140 --> 00:03:10,380
teve de volta na semana zero, que de
procurando por alguém em uma lista telefônica,

64
00:03:10,380 --> 00:03:12,380
e lembrar que a
pseudocódigo que nos propusemos,

65
00:03:12,380 --> 00:03:14,560
através do qual podemos encontrar
alguém como Mike Smith,

66
00:03:14,560 --> 00:03:16,310
parecia um pouco algo como isto.

67
00:03:16,310 --> 00:03:20,820
>> Agora, dê uma olhada em particular
na linha 7 e 8, e 10 e 11,

68
00:03:20,820 --> 00:03:25,240
que induzem a esse ciclo, pelo que mantivemos
voltar para a linha 3 novamente, e novamente,

69
00:03:25,240 --> 00:03:26,520
e de novo.

70
00:03:26,520 --> 00:03:31,790
Mas acontece que podemos ver
esse algoritmo, aqui em pseudocódigo,

71
00:03:31,790 --> 00:03:33,620
um pouco mais de forma holística.

72
00:03:33,620 --> 00:03:35,960
Na verdade, o que estou procurando
a aqui na tela,

73
00:03:35,960 --> 00:03:41,180
é um algoritmo para a busca de
Mike Smith entre alguns conjunto de páginas.

74
00:03:41,180 --> 00:03:45,520
E, de fato, podemos simplificar esta
algoritmo nessas linhas 7 e 8,

75
00:03:45,520 --> 00:03:49,860
e 10 e 11 a apenas dizer isto,
que eu tenho apresentado aqui em amarelo.

76
00:03:49,860 --> 00:03:52,210
Em outras palavras, se o Mike
Smith é no início do livro,

77
00:03:52,210 --> 00:03:55,004
nós não precisa especificar passo
a passo agora como ir encontrá-lo.

78
00:03:55,004 --> 00:03:56,920
Não temos para especificar
voltar para a linha 3,

79
00:03:56,920 --> 00:03:58,960
por quê nós não apenas em vez disso,
digamos, mais geralmente,

80
00:03:58,960 --> 00:04:01,500
procurar Mike no
metade esquerda do livro.

81
00:04:01,500 --> 00:04:03,960
>> Por outro lado, se o Mike é
na verdade, no final do livro,

82
00:04:03,960 --> 00:04:07,540
por que não podemos apenas citar pesquisa unquote
para Mike na metade direita do livro.

83
00:04:07,540 --> 00:04:11,030
Em outras palavras, por que não acabamos
tipo de punt para nós mesmos dizendo:

84
00:04:11,030 --> 00:04:13,130
procurar Mike neste
subconjunto do livro,

85
00:04:13,130 --> 00:04:16,279
e deixá-lo para a nossa existente
algoritmo para nos dizer

86
00:04:16,279 --> 00:04:18,750
como a busca de Mike em
que a metade esquerda do livro.

87
00:04:18,750 --> 00:04:20,750
Em outras palavras, o nosso
algoritmo funciona se é

88
00:04:20,750 --> 00:04:24,670
um livro de telefone desta espessura, desta
espessura, ou qualquer espessura que seja.

89
00:04:24,670 --> 00:04:27,826
Assim, podemos de forma recursiva
definir este algoritmo.

90
00:04:27,826 --> 00:04:29,950
Em outras palavras, no
tela aqui, é um algoritmo

91
00:04:29,950 --> 00:04:33,130
para a busca de Mike Smith
entre as páginas de um livro de telefone.

92
00:04:33,130 --> 00:04:37,410
Assim, na linha 7 e 10, vamos
apenas dizer exatamente isso.

93
00:04:37,410 --> 00:04:40,250
E eu uso este termo num momento
atrás, e de fato, recursão

94
00:04:40,250 --> 00:04:42,450
é a palavra de ordem, por enquanto,
e é este processo

95
00:04:42,450 --> 00:04:47,210
de fazer algo por alguma forma cíclica
usando o código que você já tem,

96
00:04:47,210 --> 00:04:49,722
e chamando-o de novo,
e mais uma vez, e novamente.

97
00:04:49,722 --> 00:04:51,930
Agora ele vai ser importante
que de alguma forma inferior

98
00:04:51,930 --> 00:04:53,821
para fora, e não fazer isso infinitamente longo.

99
00:04:53,821 --> 00:04:56,070
Caso contrário, vamos
têm, na verdade um loop infinito.

100
00:04:56,070 --> 00:04:59,810
Mas vamos ver se podemos emprestar essa idéia
de uma recursão, fazendo algo de novo

101
00:04:59,810 --> 00:05:03,600
e de novo e de novo, para resolver
o problema de ordenação através de mesclagem

102
00:05:03,600 --> 00:05:05,900
tipo, tanto mais eficiente.

103
00:05:05,900 --> 00:05:06,970
>> Então, eu dar-lhe-merge sort.

104
00:05:06,970 --> 00:05:07,920
Vamos dar uma olhada.

105
00:05:07,920 --> 00:05:10,850
Então aqui é pseudocódigo, com
que poderíamos implementar a triagem,

106
00:05:10,850 --> 00:05:12,640
usando este algoritmo chamado merge sort.

107
00:05:12,640 --> 00:05:13,880
E é simplesmente isso.

108
00:05:13,880 --> 00:05:15,940
Sobre a entrada de n elementos,
em outras palavras, se você estiver

109
00:05:15,940 --> 00:05:18,830
dado n elementos e números e
cartas ou qualquer que seja a entrada é,

110
00:05:18,830 --> 00:05:22,430
se você está dado n elementos, se
n é inferior a 2, apenas voltar.

111
00:05:22,430 --> 00:05:22,930
Certo?

112
00:05:22,930 --> 00:05:26,430
Porque se n é inferior a 2, que
significa que a minha lista de elementos

113
00:05:26,430 --> 00:05:30,446
ou é de tamanho 0 ou 1, e
em ambos desses casos triviais,

114
00:05:30,446 --> 00:05:31,570
a lista já está classificado.

115
00:05:31,570 --> 00:05:32,810
Se não existe uma lista, está classificado.

116
00:05:32,810 --> 00:05:35,185
E se há uma lista de comprimento
1, é obviamente classificadas.

117
00:05:35,185 --> 00:05:38,280
Assim, o algoritmo precisa apenas
realmente fazer algo interessante,

118
00:05:38,280 --> 00:05:40,870
se temos dois ou mais
elementos que nos foi dado.

119
00:05:40,870 --> 00:05:42,440
Então, vamos olhar para a magia então.

120
00:05:42,440 --> 00:05:47,500
Logo classificar a metade esquerda dos elementos,
em seguida, classificar a metade direita de elementos,

121
00:05:47,500 --> 00:05:49,640
em seguida, mesclar as metades classificados.

122
00:05:49,640 --> 00:05:52,440
E o que é tipo de mente dobra
aqui, é que eu realmente não

123
00:05:52,440 --> 00:05:56,190
parecem ter-lhe dito
nada ainda, certo?

124
00:05:56,190 --> 00:05:59,560
Tudo o que eu disse é, dada uma lista de
n elementos, ordenar a metade esquerda,

125
00:05:59,560 --> 00:06:01,800
em seguida, a metade direita, em seguida,
mesclar as metades ordenados,

126
00:06:01,800 --> 00:06:03,840
mas onde está o segredo real?

127
00:06:03,840 --> 00:06:05,260
Onde está o algoritmo?

128
00:06:05,260 --> 00:06:09,150
Bem, acontece que essas duas linhas
primeiro, metade deixou tipo de elementos,

129
00:06:09,150 --> 00:06:13,970
e tipo certo de metade dos elementos,
são chamadas recursivas, por assim dizer.

130
00:06:13,970 --> 00:06:16,120
>> Apesar de tudo, neste
ponto no tempo, eu tenho

131
00:06:16,120 --> 00:06:18,950
um algoritmo com a qual a
classificar um monte de elementos?

132
00:06:18,950 --> 00:06:19,450
Sim.

133
00:06:19,450 --> 00:06:20,620
Está bem aqui.

134
00:06:20,620 --> 00:06:25,180
É aqui mesmo na tela, e
para que eu possa usar o mesmo conjunto de passos

135
00:06:25,180 --> 00:06:28,500
para classificar a metade esquerda,
como eu posso a metade direita.

136
00:06:28,500 --> 00:06:30,420
E, de fato, mais uma vez, e outra vez.

137
00:06:30,420 --> 00:06:34,210
Então, de alguma forma ou de outra, e nós vamos em breve
ver isso, a magia de merge sort

138
00:06:34,210 --> 00:06:37,967
é incorporado em que muito definitiva
linha, a fusão das metades ordenados.

139
00:06:37,967 --> 00:06:39,300
E isso parece bastante intuitivo.

140
00:06:39,300 --> 00:06:41,050
Você pega duas metades, e você,
de alguma forma, fundi-las,

141
00:06:41,050 --> 00:06:43,260
e vamos ver isso
concretamente em um momento.

142
00:06:43,260 --> 00:06:45,080
>> Mas este é um algoritmo completo.

143
00:06:45,080 --> 00:06:46,640
E vamos ver exatamente o porquê.

144
00:06:46,640 --> 00:06:50,912
Bem supor que nós estamos dando esses mesmos
oito elementos aqui na tela, um

145
00:06:50,912 --> 00:06:53,120
através de oito, mas eles são
em ordem aleatória.

146
00:06:53,120 --> 00:06:55,320
E o objetivo em questão é
para classificar estes elementos.

147
00:06:55,320 --> 00:06:58,280
Bem, como eu posso ir sobre
fazê-lo usando, novamente,

148
00:06:58,280 --> 00:07:00,407
merge sort, de acordo com este pseudo-código?

149
00:07:00,407 --> 00:07:02,740
E, novamente, incutir isso em
sua mente, apenas por um momento.

150
00:07:02,740 --> 00:07:05,270
O primeiro caso é bastante
trivial, se for inferior a 2,

151
00:07:05,270 --> 00:07:07,060
basta retornar, não há trabalho a ser feito.

152
00:07:07,060 --> 00:07:09,290
Então, realmente há apenas três
passos para realmente manter em mente.

153
00:07:09,290 --> 00:07:11,081
Mais uma vez, e de novo, eu sou
vai querer ter

154
00:07:11,081 --> 00:07:13,980
para classificar a metade esquerda,
ordenar a metade direita,

155
00:07:13,980 --> 00:07:15,890
e, em seguida, uma vez que sua
duas metades são classificadas,

156
00:07:15,890 --> 00:07:18,710
Eu quero fundi-las
em uma lista ordenada.

157
00:07:18,710 --> 00:07:19,940
Portanto, manter isso em mente.

158
00:07:19,940 --> 00:07:21,310
>> Então aqui está a lista original.

159
00:07:21,310 --> 00:07:23,510
Vamos tratar isso como uma
array, como nós começamos a

160
00:07:23,510 --> 00:07:25,800
na semana dois, que é um
bloco contíguo de memória.

161
00:07:25,800 --> 00:07:28,480
Neste caso, contendo oito
números, back to back to back.

162
00:07:28,480 --> 00:07:30,700
E vamos agora aplicar merge sort.

163
00:07:30,700 --> 00:07:33,300
Então, primeiro eu quero classificar
a metade esquerda da lista,

164
00:07:33,300 --> 00:07:37,370
e vamos, portanto,
concentrar em 4, 8, 6, e 2.

165
00:07:37,370 --> 00:07:41,000
>> Agora, como eu vou sobre
ordenar uma lista de tamanho 4?

166
00:07:41,000 --> 00:07:45,990
Bem eu tenho que considerar agora
triagem esquerda da metade esquerda.

167
00:07:45,990 --> 00:07:47,720
Mais uma vez, vamos retroceder por um momento.

168
00:07:47,720 --> 00:07:51,010
Se o pseudocódigo é isso,
e eu estou determinado oito elementos,

169
00:07:51,010 --> 00:07:53,230
8 é obviamente maior
que ou igual a 2.

170
00:07:53,230 --> 00:07:54,980
Assim, com o primeiro caso não se aplica.

171
00:07:54,980 --> 00:07:58,120
Assim, para classificar oito elementos, eu primeiro
ordenar a metade esquerda de elementos,

172
00:07:58,120 --> 00:08:01,930
então eu ordenar a metade direita, então eu mesclar
as duas metades, cada uma das ordenadas tamanho 4.

173
00:08:01,930 --> 00:08:02,470
ESTÁ BEM.

174
00:08:02,470 --> 00:08:07,480
>> Mas se você acabou de me dizer, ordenar a
metade esquerda, que agora é de tamanho 4,

175
00:08:07,480 --> 00:08:09,350
como faço para classificar a metade esquerda?

176
00:08:09,350 --> 00:08:11,430
Bem, se eu tenho uma
entrada de quatro elementos,

177
00:08:11,430 --> 00:08:14,590
I primeiro classificar à esquerda
dois, então os dois direita,

178
00:08:14,590 --> 00:08:16,210
e então eu fundi-las.

179
00:08:16,210 --> 00:08:18,700
Então, novamente, torna-se um pouco
de uma mente dobra jogo aqui,

180
00:08:18,700 --> 00:08:21,450
porque você, tipo, tem que
lembre-se onde você está na história,

181
00:08:21,450 --> 00:08:23,620
mas no final do dia,
dada qualquer número de elementos,

182
00:08:23,620 --> 00:08:25,620
primeiro você deseja classificar a
metade esquerda, em seguida, a metade direita,

183
00:08:25,620 --> 00:08:26,661
em seguida, fundi-las.

184
00:08:26,661 --> 00:08:28,630
Vamos começar a fazer exatamente isso.

185
00:08:28,630 --> 00:08:30,170
Aqui é a entrada de oito elementos.

186
00:08:30,170 --> 00:08:31,910
Agora nós estamos olhando para a metade esquerda aqui.

187
00:08:31,910 --> 00:08:33,720
Como faço para classificar quatro elementos?

188
00:08:33,720 --> 00:08:35,610
Bem, eu primeiro classificar a metade esquerda.

189
00:08:35,610 --> 00:08:37,720
Agora como faço para classificar a metade esquerda?

190
00:08:37,720 --> 00:08:39,419
Bem, eu tenho dado dois elementos.

191
00:08:39,419 --> 00:08:41,240
Então, vamos resolver estes dois elementos.

192
00:08:41,240 --> 00:08:44,540
2 é maior do que ou
igual a 2, é claro.

193
00:08:44,540 --> 00:08:46,170
Assim que o primeiro caso não se aplica.

194
00:08:46,170 --> 00:08:49,010
>> Então, eu agora tenho que classificar a esquerda
metade destes dois elementos.

195
00:08:49,010 --> 00:08:50,870
A metade esquerda, é claro, está apenas a 4.

196
00:08:50,870 --> 00:08:54,020
Então, como faço para classificar uma lista de um elemento?

197
00:08:54,020 --> 00:08:57,960
Bem, agora, que caso base especial
em cima, por assim dizer, se aplica.

198
00:08:57,960 --> 00:09:01,470
1 é inferior a 2, e o meu
lista é realmente de tamanho 1.

199
00:09:01,470 --> 00:09:02,747
Então, eu só retornar.

200
00:09:02,747 --> 00:09:03,580
Eu não faço nada.

201
00:09:03,580 --> 00:09:06,770
E, de fato, olha o que eu tenho
feito, quatro já estão classificados.

202
00:09:06,770 --> 00:09:09,220
Como eu já estou
parcialmente bem sucedido aqui.

203
00:09:09,220 --> 00:09:11,750
>> Agora que parece uma espécie de idiota
para reclamar, mas é verdade.

204
00:09:11,750 --> 00:09:13,700
4 é uma lista de tamanho 1.

205
00:09:13,700 --> 00:09:15,090
Ele já está classificado.

206
00:09:15,090 --> 00:09:16,270
Isso é a metade esquerda.

207
00:09:16,270 --> 00:09:18,010
Agora eu ordenar a metade direita.

208
00:09:18,010 --> 00:09:22,310
Minha entrada é um elemento, 8
Da mesma forma, já classificados.

209
00:09:22,310 --> 00:09:25,170
Estúpido, também, mas, novamente,
este princípio básico

210
00:09:25,170 --> 00:09:28,310
vai permitir-nos construir agora
em cima deste com sucesso.

211
00:09:28,310 --> 00:09:32,260
4 classificado, 8 é classificado, agora
Qual foi a última etapa?

212
00:09:32,260 --> 00:09:35,330
Assim, o terceiro e último passo, qualquer
vez que você está classificando uma lista, recall,

213
00:09:35,330 --> 00:09:38,310
era fundir as duas metades,
à esquerda e à direita.

214
00:09:38,310 --> 00:09:39,900
Então, vamos fazer exatamente isso.

215
00:09:39,900 --> 00:09:41,940
Meu metade esquerda é, naturalmente, 4.

216
00:09:41,940 --> 00:09:43,310
Meu metade direita é 8.

217
00:09:43,310 --> 00:09:44,100
>> Então, vamos fazer isso.

218
00:09:44,100 --> 00:09:46,410
Primeiro eu vou para alocar
alguma memória adicional,

219
00:09:46,410 --> 00:09:48,680
que eu vou representar aqui,
como apenas uma matriz secundária,

220
00:09:48,680 --> 00:09:49,660
que é grande o suficiente para caber isso.

221
00:09:49,660 --> 00:09:52,243
Mas você pode imaginar que se estende
retângulo que todo o comprimento,

222
00:09:52,243 --> 00:09:53,290
se precisarmos de mais tarde.

223
00:09:53,290 --> 00:09:58,440
Como faço para fazer 4 e 8, e mesclar
essas duas listas de tamanho 1 juntos?

224
00:09:58,440 --> 00:10:00,270
Aqui, também, bastante simples.

225
00:10:00,270 --> 00:10:03,300
4 vem primeiro, depois vem 8.

226
00:10:03,300 --> 00:10:07,130
Porque se eu quiser classificar a
metade esquerda, em seguida, a metade direita,

227
00:10:07,130 --> 00:10:09,900
e, em seguida, mesclar essas duas metades
juntos, na ordem de classificação,

228
00:10:09,900 --> 00:10:11,940
4 vem primeiro, depois vem 8.

229
00:10:11,940 --> 00:10:15,810
>> Então, parece que estamos a fazer progressos, mesmo
embora eu não tenha feito qualquer trabalho real.

230
00:10:15,810 --> 00:10:17,800
Mas lembre-se onde estamos na história.

231
00:10:17,800 --> 00:10:19,360
Nós originalmente levou oito elementos.

232
00:10:19,360 --> 00:10:21,480
Separamos a metade esquerda, que é 4.

233
00:10:21,480 --> 00:10:24,450
Então nós ordenamos a metade esquerda
da metade esquerda, que era de 2.

234
00:10:24,450 --> 00:10:25,270
E aqui vamos nós.

235
00:10:25,270 --> 00:10:26,920
Nós somos feitos com esse passo.

236
00:10:26,920 --> 00:10:29,930
>> Então, se temos classificados o
à esquerda metade 2, agora nós

237
00:10:29,930 --> 00:10:32,130
tem que classificar a metade direita de 2.

238
00:10:32,130 --> 00:10:35,710
Assim, a metade direita 2 está
estes dois valores aqui, 6 e 2.

239
00:10:35,710 --> 00:10:40,620
Então, vamos agora dar uma entrada de tamanho
2, e ordenar a metade esquerda e, em seguida

240
00:10:40,620 --> 00:10:42,610
a metade direita, e, em seguida,
fundi-las.

241
00:10:42,610 --> 00:10:45,722
Bem como faço para classificar uma lista de tamanho
1, que contém apenas o número 6?

242
00:10:45,722 --> 00:10:46,430
Eu já estou feito.

243
00:10:46,430 --> 00:10:48,680
Essa lista de tamanho 1 é ordenada.

244
00:10:48,680 --> 00:10:52,140
>> Como faço para classificar uma outra lista de
tamanho 1, o assim chamado metade direita.

245
00:10:52,140 --> 00:10:54,690
Bem, também, já está classificado.

246
00:10:54,690 --> 00:10:56,190
O número 2 está sozinho.

247
00:10:56,190 --> 00:11:00,160
Então agora eu tenho duas metades, esquerda e
certo, eu preciso fundi-las.

248
00:11:00,160 --> 00:11:01,800
Deixe-me dar-me um pouco de espaço extra.

249
00:11:01,800 --> 00:11:05,580
E colocá-2 em lá,
em seguida, 6 de lá, assim

250
00:11:05,580 --> 00:11:10,740
classificando essa lista, esquerda e direita,
e fundindo-lo juntos, em última instância.

251
00:11:10,740 --> 00:11:12,160
Então, eu estou em um pouco melhor forma.

252
00:11:12,160 --> 00:11:16,250
Eu não sou feito, porque claramente 4, 8, 2,
6 não é a ordenação final que eu quero.

253
00:11:16,250 --> 00:11:20,640
Mas agora tenho duas listas de tamanho 2, que
ambos têm, respectivamente, foram classificadas.

254
00:11:20,640 --> 00:11:24,580
Portanto, agora se você retroceder em sua mente de
olho, onde é que isso nos deixa?

255
00:11:24,580 --> 00:11:28,520
Comecei com oito elementos, então eu
talhou-lo para baixo para a metade esquerda do 4,

256
00:11:28,520 --> 00:11:31,386
em seguida, a metade esquerda 2, e
em seguida, a metade direita da 2,

257
00:11:31,386 --> 00:11:34,510
Eu terminei, portanto, a triagem esquerda
metade de 2, e a metade direita de 2,

258
00:11:34,510 --> 00:11:37,800
então qual é o terceiro e último passo aqui?

259
00:11:37,800 --> 00:11:41,290
Eu tenho que fundir-se
duas listas de tamanho 2.

260
00:11:41,290 --> 00:11:42,040
Então, vamos em frente.

261
00:11:42,040 --> 00:11:43,940
E na tela aqui, dar-
me alguma memória adicional,

262
00:11:43,940 --> 00:11:47,170
embora tecnicamente, repare que eu tenho
tem um monte de espaço em branco em cima

263
00:11:47,170 --> 00:11:47,670
há.

264
00:11:47,670 --> 00:11:50,044
Se eu quiser ser especialmente
espaço eficiente sábio,

265
00:11:50,044 --> 00:11:52,960
Eu poderia simplesmente começar a mover os elementos
e para trás, superior e inferior.

266
00:11:52,960 --> 00:11:55,460
Mas apenas para maior clareza visual,
Vou colocá-lo lá em baixo,

267
00:11:55,460 --> 00:11:56,800
para manter as coisas agradável e limpo.

268
00:11:56,800 --> 00:11:58,150
>> Então eu tenho duas listas de tamanho 2.

269
00:11:58,150 --> 00:11:59,770
A primeira lista tem 4 e 8.

270
00:11:59,770 --> 00:12:01,500
A segunda lista tem 2 e 6.

271
00:12:01,500 --> 00:12:03,950
Vamos mesclar aqueles
juntos na ordem de classificação.

272
00:12:03,950 --> 00:12:09,910
2, é claro, vem em primeiro lugar,
em seguida, 4, 6, em seguida, em seguida, 8.

273
00:12:09,910 --> 00:12:12,560
E agora parece que estamos recebendo
em algum lugar interessante.

274
00:12:12,560 --> 00:12:15,720
Agora eu tenho metade classificadas da
lista, e coincidentemente, é

275
00:12:15,720 --> 00:12:18,650
Todos os números pares, mas isso
é, na verdade, apenas uma coincidência.

276
00:12:18,650 --> 00:12:22,220
E eu agora ter resolvido a esquerda
metade, de modo que é 2, 4, 6, e 8.

277
00:12:22,220 --> 00:12:23,430
Nada está fora de ordem.

278
00:12:23,430 --> 00:12:24,620
Que se sente como progresso.

279
00:12:24,620 --> 00:12:26,650
>> Agora parece que eu tenho
falado para sempre agora,

280
00:12:26,650 --> 00:12:29,850
Então, o que continua a ser visto se isso
algoritmo é, na verdade, mais eficiente.

281
00:12:29,850 --> 00:12:31,766
Mas estamos passando por
super metodicamente.

282
00:12:31,766 --> 00:12:34,060
Um computador, é claro,
iria fazê-lo assim.

283
00:12:34,060 --> 00:12:34,840
Então, onde estamos?

284
00:12:34,840 --> 00:12:36,180
Começamos com oito elementos.

285
00:12:36,180 --> 00:12:37,840
Separei a metade esquerda da 4.

286
00:12:37,840 --> 00:12:39,290
Eu pareço ser feito com isso.

287
00:12:39,290 --> 00:12:42,535
Portanto, agora o próximo passo é
ordenar a metade direita 4.

288
00:12:42,535 --> 00:12:44,410
E esta parte podemos ir
através de um pouco mais

289
00:12:44,410 --> 00:12:47,140
rapidamente, embora você é
bem-vindo para retroceder ou pausar, apenas

290
00:12:47,140 --> 00:12:49,910
acho que por ele em
seu próprio ritmo, mas o que

291
00:12:49,910 --> 00:12:53,290
que temos agora é uma oportunidade para
fazer o mesmo algoritmo exato em quatro

292
00:12:53,290 --> 00:12:54,380
números diferentes.

293
00:12:54,380 --> 00:12:57,740
>> Então vamos em frente, e se concentrar em
a metade direita, que estamos aqui.

294
00:12:57,740 --> 00:13:01,260
A metade esquerda do referido
metade direita, e agora o

295
00:13:01,260 --> 00:13:04,560
metade esquerda da esquerda
metade do que a metade direita,

296
00:13:04,560 --> 00:13:08,030
e como faço para classificar uma lista de tamanho
1 contendo apenas o número 1?

297
00:13:08,030 --> 00:13:09,030
Está feito.

298
00:13:09,030 --> 00:13:11,830
Como eu faço o mesmo para uma lista
de tamanho 1 contendo apenas 7?

299
00:13:11,830 --> 00:13:12,840
Está feito.

300
00:13:12,840 --> 00:13:16,790
Passo três para metade, em seguida, esta
é para mesclar esses dois elementos

301
00:13:16,790 --> 00:13:20,889
em uma nova lista de tamanho 2, 1 e 7.

302
00:13:20,889 --> 00:13:23,180
Não parecem ter feito tudo
que muito trabalho interessante.

303
00:13:23,180 --> 00:13:24,346
Vamos ver o que acontece em seguida.

304
00:13:24,346 --> 00:13:29,210
Eu só ordenados a metade esquerda do
metade direita da minha entrada original.

305
00:13:29,210 --> 00:13:32,360
Agora vamos classificar a direita
meio, que contém 3 e 5.

306
00:13:32,360 --> 00:13:35,740
Vamos de novo olhar para a esquerda
metade, classificado, metade direita, classificado,

307
00:13:35,740 --> 00:13:39,120
e mesclar os dois juntos,
em algum espaço adicional,

308
00:13:39,120 --> 00:13:41,670
3 vem primeiro, depois vem 5.

309
00:13:41,670 --> 00:13:46,190
E agora, temos classificados o
metade esquerda da metade direita

310
00:13:46,190 --> 00:13:49,420
do problema original, e
a metade direita da metade direita

311
00:13:49,420 --> 00:13:50,800
do problema original.

312
00:13:50,800 --> 00:13:52,480
O que é a terceira e última etapa?

313
00:13:52,480 --> 00:13:54,854
Bem, para mesclar essas duas metades juntas.

314
00:13:54,854 --> 00:13:57,020
Então me deixe ter algum
espaço extra, mas, novamente, eu

315
00:13:57,020 --> 00:13:58,699
poderia estar usando aquele espaço em cima de reposição.

316
00:13:58,699 --> 00:14:00,490
Mas nós estamos indo para mantê-
o simples visualmente.

317
00:14:00,490 --> 00:14:07,070
Deixe-me agora fundem-se em um, e
em seguida, 3, 5 e, em seguida, e em seguida 7.

318
00:14:07,070 --> 00:14:10,740
Assim, me deixando agora com a
metade direita do problema original

319
00:14:10,740 --> 00:14:12,840
Isso é perfeitamente ordenadas.

320
00:14:12,840 --> 00:14:13,662
>> Então o que resta?

321
00:14:13,662 --> 00:14:16,120
Eu sinto que eu continuo dizendo a
mesmas coisas de novo, e de novo,

322
00:14:16,120 --> 00:14:18,700
mas isso é um reflexo do
fato de que estamos usando recursão.

323
00:14:18,700 --> 00:14:21,050
O processo de utilização de um
algoritmo de novo, e de novo,

324
00:14:21,050 --> 00:14:23,940
em subconjuntos mais pequenos de
o problema original.

325
00:14:23,940 --> 00:14:27,580
Então, agora tenho uma esquerda classificadas
metade do problema original.

326
00:14:27,580 --> 00:14:30,847
Eu tenho uma meia ordenada direita
do problema original.

327
00:14:30,847 --> 00:14:32,180
Qual é a terceira e última etapa?

328
00:14:32,180 --> 00:14:33,590
Oh, ele está fundindo.

329
00:14:33,590 --> 00:14:34,480
Então, vamos fazer isso.

330
00:14:34,480 --> 00:14:36,420
Vamos alocar algum adicional
memória, mas meu deus, nós

331
00:14:36,420 --> 00:14:37,503
poderia colocá-lo em qualquer lugar agora.

332
00:14:37,503 --> 00:14:40,356
Temos muito espaço disponível
para nós, mas vamos mantê-lo simples.

333
00:14:40,356 --> 00:14:42,730
Em vez de ir para trás e
adiante com nossa memória original,

334
00:14:42,730 --> 00:14:44,480
vamos fazê-lo
visualmente aqui abaixo,

335
00:14:44,480 --> 00:14:47,240
para terminar a fusão
metade esquerda e metade direita.

336
00:14:47,240 --> 00:14:49,279
>> Assim, através da fusão, o que eu preciso fazer?

337
00:14:49,279 --> 00:14:50,820
Eu quero ter os elementos em ordem.

338
00:14:50,820 --> 00:14:53,230
Então, olhando para o lado esquerdo,
Eu vejo o primeiro número é 2.

339
00:14:53,230 --> 00:14:55,230
Eu olho para a metade direita,
Eu vejo o primeiro número

340
00:14:55,230 --> 00:14:58,290
é 1, então obviamente que
número que eu quero arrancar,

341
00:14:58,290 --> 00:15:00,430
e colocar em primeiro lugar na minha lista final?

342
00:15:00,430 --> 00:15:01,449
Naturalmente, 1.

343
00:15:01,449 --> 00:15:02,990
Agora eu quero fazer a mesma pergunta.

344
00:15:02,990 --> 00:15:05,040
Na metade esquerda, eu tenho
ainda tem o número 2.

345
00:15:05,040 --> 00:15:07,490
Na metade direita,
Eu tenho o número 3.

346
00:15:07,490 --> 00:15:08,930
Qual deles eu quero escolher?

347
00:15:08,930 --> 00:15:11,760
Claro, número 2 E
Agora observe os candidatos

348
00:15:11,760 --> 00:15:13,620
4 estão à esquerda, à direita 3.

349
00:15:13,620 --> 00:15:15,020
Vamos, naturalmente, escolher três.

350
00:15:15,020 --> 00:15:18,020
Agora, os candidatos são 4 na
a esquerda, 5, à direita.

351
00:15:18,020 --> 00:15:19,460
Nós, é claro, escolher quatro.

352
00:15:19,460 --> 00:15:21,240
6, à esquerda, à direita 5.

353
00:15:21,240 --> 00:15:22,730
Nós, é claro, escolher 5.

354
00:15:22,730 --> 00:15:25,020
6 do lado esquerdo, do lado direito 7.

355
00:15:25,020 --> 00:15:29,320
Nós escolhemos seis, e então nós
escolher 7, e, em seguida, nós escolhemos 8.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Assim, um grande número de palavras mais tarde,
ter resolvido esta lista de oito elementos

358
00:15:34,370 --> 00:15:38,450
em uma lista de um a oito,
que está aumentando a cada passo,

359
00:15:38,450 --> 00:15:40,850
mas quanto tempo fez
leva-nos a fazer isso.

360
00:15:40,850 --> 00:15:43,190
Bem, eu tenho deliberadamente
coisas estabelecidas pictorially

361
00:15:43,190 --> 00:15:46,330
aqui, para que possamos tipo de
ver ou apreciar a divisão

362
00:15:46,330 --> 00:15:49,060
na conquista que está acontecendo.

363
00:15:49,060 --> 00:15:52,830
>> Na verdade, se você olhar para trás na esteira,
Eu deixei todas essas linhas pontilhadas

364
00:15:52,830 --> 00:15:55,660
em suportes do lugar, você pode,
tipo de, veja, em ordem inversa,

365
00:15:55,660 --> 00:15:58,800
se você tipo de olhar para trás em
história agora, meu lista original

366
00:15:58,800 --> 00:16:00,250
é, é claro, de tamanho 8.

367
00:16:00,250 --> 00:16:03,480
E, em seguida, anteriormente, eu estava
lidando com duas listas de tamanho 4,

368
00:16:03,480 --> 00:16:08,400
e, em seguida, quatro listas de tamanho 2,
e, em seguida, oito listas de tamanho 1.

369
00:16:08,400 --> 00:16:10,151
>> Então, o que faz isso,
tipo de, lembra?

370
00:16:10,151 --> 00:16:11,858
Bem, na verdade, qualquer de
os algoritmos Nós

371
00:16:11,858 --> 00:16:14,430
olhou, até agora, onde nós
dividir e dividir, e se dividem,

372
00:16:14,430 --> 00:16:19,500
continuo a ter as coisas novamente, e
novamente, resulta nessa idéia geral.

373
00:16:19,500 --> 00:16:23,100
E então há algo
logarítmica acontecendo aqui.

374
00:16:23,100 --> 00:16:26,790
E não é muito de log n, mas
há um componente logarítmica

375
00:16:26,790 --> 00:16:28,280
com o que acabou de fazer.

376
00:16:28,280 --> 00:16:31,570
>> Agora vamos considerar como isso realmente é.

377
00:16:31,570 --> 00:16:34,481
Então log de n, novamente foi
um grande tempo de execução,

378
00:16:34,481 --> 00:16:36,980
quando fizemos algo como
busca binária, como agora chamá-lo,

379
00:16:36,980 --> 00:16:40,090
a estratégia de dividir para conquistar
via que encontramos Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Agora tecnicamente.

381
00:16:41,020 --> 00:16:43,640
Isso é log base dois de n, mesmo
embora na maioria das classes de matemática,

382
00:16:43,640 --> 00:16:45,770
10 é geralmente a base que você assume.

383
00:16:45,770 --> 00:16:48,940
Mas cientistas da computação quase sempre
pensar e falar em termos de base 2,

384
00:16:48,940 --> 00:16:52,569
assim que nós geralmente apenas dizer log de
N, em vez de log de base 2 de N,

385
00:16:52,569 --> 00:16:55,110
mas eles são exatamente um eo
mesmo no mundo do computador

386
00:16:55,110 --> 00:16:57,234
ciência, e como um aparte,
há um fator constante

387
00:16:57,234 --> 00:17:01,070
diferença entre os dois, de modo que é
moot de qualquer maneira, por razões mais formais.

388
00:17:01,070 --> 00:17:04,520
>> Mas, por agora, o que nós nos importamos
é sobre este exemplo.

389
00:17:04,520 --> 00:17:08,520
Então não vamos provar por exemplo, mas em
menos usar um exemplo dos números

390
00:17:08,520 --> 00:17:10,730
na mão como uma verificação de sanidade, se você quiser.

391
00:17:10,730 --> 00:17:14,510
Assim, a fórmula anteriormente foi log de base
2 de N, mas o que é n neste caso.

392
00:17:14,510 --> 00:17:18,526
Eu tinha números de n originais, ou 8
do número original especificamente.

393
00:17:18,526 --> 00:17:20,359
Agora ele tem sido um pouco
enquanto, mas estou bastante

394
00:17:20,359 --> 00:17:25,300
Certifique-se que a base de log 2
do valor 8 é 3,

395
00:17:25,300 --> 00:17:29,630
e, na verdade, o que é bom sobre o que é
3 que é exactamente o número de vezes

396
00:17:29,630 --> 00:17:33,320
que você pode dividir uma lista
comprimento de 8, e novamente,

397
00:17:33,320 --> 00:17:36,160
e outra vez, até que você é deixado
com listas de apenas um tamanho.

398
00:17:36,160 --> 00:17:36,660
Certo?

399
00:17:36,660 --> 00:17:40,790
8 vai para 4, vai para 2,
vai para 1, e isso é

400
00:17:40,790 --> 00:17:43,470
reflexivo do que exatamente
imagem, tivemos apenas um momento atrás.

401
00:17:43,470 --> 00:17:47,160
Então, um pouco de sanidade verificar de onde
o logaritmo é realmente envolvidos.

402
00:17:47,160 --> 00:17:50,180
>> Então, agora, o que mais está envolvido aqui? n.

403
00:17:50,180 --> 00:17:53,440
Então, observe que cada
vez que dividir a lista,

404
00:17:53,440 --> 00:17:58,260
embora na ordem inversa na história
aqui, eu ainda estava fazendo as coisas n.

405
00:17:58,260 --> 00:18:02,320
Isso exige que a fusão etapa
Eu toco a cada um dos números,

406
00:18:02,320 --> 00:18:05,060
a fim de deslize-
a sua localização adequada.

407
00:18:05,060 --> 00:18:10,760
Assim, mesmo que a altura desta
diagrama é de tamanho de log n de n ou 3,

408
00:18:10,760 --> 00:18:13,860
Especificamente, em outras palavras,
Eu fiz três divisões aqui.

409
00:18:13,860 --> 00:18:18,800
Quanto trabalho que eu fiz na horizontal
ao longo desta carta de cada vez?

410
00:18:18,800 --> 00:18:21,110
>> Bem, eu fiz n passos de
trabalhar, porque se eu tenho

411
00:18:21,110 --> 00:18:24,080
tem quatro elementos e quatro elementos,
e eu preciso fundi-las.

412
00:18:24,080 --> 00:18:26,040
Eu preciso passar por
estes quatro e estes quatro,

413
00:18:26,040 --> 00:18:28,123
finalmente, para fundi-los
de volta em oito elementos.

414
00:18:28,123 --> 00:18:32,182
Se por outro lado eu tenho oito dedos
aqui, o que eu não faço, e oito

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Se eu tenho
tem quatro dedos aqui,

416
00:18:34,390 --> 00:18:37,380
que eu faço, quatro dedos
aqui, o que eu faço,

417
00:18:37,380 --> 00:18:40,590
então isso é o mesmo
exemplo como antes, se eu fizer

418
00:18:40,590 --> 00:18:44,010
tem oito dedos embora em
total, o que eu posso, tipo, fazer.

419
00:18:44,010 --> 00:18:47,950
Eu posso exatamente fazer aqui,
então eu posso certamente

420
00:18:47,950 --> 00:18:50,370
mesclar todas estas listas
de tamanho 1, em conjunto.

421
00:18:50,370 --> 00:18:54,050
Mas eu certamente tem que olhar
em cada elemento de uma única vez.

422
00:18:54,050 --> 00:18:59,640
Então, a altura deste processo é o log N,
a largura do presente processo, por assim dizer,

423
00:18:59,640 --> 00:19:02,490
é n, então o que nós parecemos
ter, em última instância, é

424
00:19:02,490 --> 00:19:06,470
uma duração de tamanho n vezes log n.

425
00:19:06,470 --> 00:19:08,977
>> Em outras palavras, dividimos
lista, log n vezes o,

426
00:19:08,977 --> 00:19:11,810
mas cada vez que fizemos isso, tivemos
para tocar a cada um dos elementos

427
00:19:11,810 --> 00:19:13,560
a fim de fundi-los
todos juntos, o que

428
00:19:13,560 --> 00:19:18,120
n para etapa foi, por isso temos n vezes log n,
ou como um cientista da computação diria,

429
00:19:18,120 --> 00:19:20,380
assintoticamente, que
seria a grande palavra

430
00:19:20,380 --> 00:19:22,810
para descrever o superior
vinculado em um tempo de execução,

431
00:19:22,810 --> 00:19:28,010
estamos executando em um grande o
de log n tempo, por assim dizer.

432
00:19:28,010 --> 00:19:31,510
>> Agora, isso é significativo, porque
recordar que os tempos de execução foram

433
00:19:31,510 --> 00:19:34,120
com bubble sort, e seleção
tipo e ordenação por inserção,

434
00:19:34,120 --> 00:19:38,200
e até mesmo alguns outros que existem,
n ao quadrado era onde estávamos.

435
00:19:38,200 --> 00:19:39,990
E você pode, tipo, ver este aqui.

436
00:19:39,990 --> 00:19:45,720
Se n ao quadrado é, obviamente, n vezes
n, mas aqui temos n vezes log n,

437
00:19:45,720 --> 00:19:48,770
e já sabemos a partir da semana
zero, que log n, a logarítmica,

438
00:19:48,770 --> 00:19:50,550
é melhor do que algo linear.

439
00:19:50,550 --> 00:19:52,930
Afinal, recordar a imagem
com o vermelho eo amarelo

440
00:19:52,930 --> 00:19:56,500
e as linhas verdes que tirou, a
logarítmica linha verde era muito menor.

441
00:19:56,500 --> 00:20:00,920
E, portanto, muito melhor e mais rápido
que as linhas amarelas e vermelhas em linha reta,

442
00:20:00,920 --> 00:20:05,900
n vezes log n é, de fato, melhor
que n vezes n, ou n ao quadrado.

443
00:20:05,900 --> 00:20:09,110
>> Então, parece que temos
identificou um algoritmo merge

444
00:20:09,110 --> 00:20:11,870
tipo que é executado em muito
tempo mais rápido, e na verdade,

445
00:20:11,870 --> 00:20:16,560
é por isso que, no início desta semana, quando
vimos que disputa entre bolha

446
00:20:16,560 --> 00:20:20,750
tipo, espécie de seleção, e mesclar
sort, merge sort realmente, realmente ganhou.

447
00:20:20,750 --> 00:20:23,660
E, de fato, nós não mesmo esperar
para bubble sort e seleção espécie

448
00:20:23,660 --> 00:20:24,790
terminar.

449
00:20:24,790 --> 00:20:27,410
>> Agora vamos dar uma outra passagem
para isso, a partir de um pouco mais

450
00:20:27,410 --> 00:20:31,030
perspectiva formal, apenas em
caso, isso ressoa melhor

451
00:20:31,030 --> 00:20:33,380
que maior do que o nível de discussão.

452
00:20:33,380 --> 00:20:34,880
Então aqui está o algoritmo novamente.

453
00:20:34,880 --> 00:20:36,770
Vamos nos perguntar:
o que o tempo de execução

454
00:20:36,770 --> 00:20:39,287
é deste algoritmos várias etapas?

455
00:20:39,287 --> 00:20:41,620
Vamos dividi-lo em primeiro
caso e no segundo caso.

456
00:20:41,620 --> 00:20:46,280
A SE ea outra pessoa no caso IF,
Se n for inferior a 2, apenas voltar.

457
00:20:46,280 --> 00:20:47,580
Se sente como tempo constante.

458
00:20:47,580 --> 00:20:50,970
É, tipo, como dois passos,
Se n for inferior a 2, em seguida, voltar.

459
00:20:50,970 --> 00:20:54,580
Mas, como dissemos na segunda-feira,
constante de tempo, ou grande o de 1,

460
00:20:54,580 --> 00:20:57,130
pode ser dois, três passos
passos, até 1.000 passos.

461
00:20:57,130 --> 00:20:59,870
O que importa é que é
um número constante de passos.

462
00:20:59,870 --> 00:21:03,240
Assim, o amarelo destaque pseudocódigo
aqui é executado em, vamos chamá-lo,

463
00:21:03,240 --> 00:21:04,490
constante de tempo.

464
00:21:04,490 --> 00:21:06,780
Então, mais formalmente, e
vamos a-- este

465
00:21:06,780 --> 00:21:09,910
será a extensão em que nós
formalizar este direito agora-- T de n,

466
00:21:09,910 --> 00:21:15,030
o tempo de execução de um problema
que leva n qualquer coisa como entrada,

467
00:21:15,030 --> 00:21:19,150
igualam o o de um,
Se n for menor do que 2.

468
00:21:19,150 --> 00:21:20,640
Portanto, é condicionada a isso.

469
00:21:20,640 --> 00:21:24,150
Então, para ser claro, se n for inferior a
2, temos uma lista muito curta, então

470
00:21:24,150 --> 00:21:29,151
o tempo de execução, de t n, em que n é
0 ou 1, neste caso muito específico,

471
00:21:29,151 --> 00:21:30,650
ele só vai ser de tempo constante.

472
00:21:30,650 --> 00:21:32,691
Vai levar um
passo, dois passos, que seja.

473
00:21:32,691 --> 00:21:33,950
É um número fixo de etapas.

474
00:21:33,950 --> 00:21:38,840
>> Assim, a parte suculenta certamente deve estar em
no outro caso no pseudocódigo.

475
00:21:38,840 --> 00:21:40,220
O caso MAIS.

476
00:21:40,220 --> 00:21:44,870
Ordenar metade esquerda de elementos, tipo certo
metade dos elementos, fundir metades ordenados.

477
00:21:44,870 --> 00:21:46,800
Quanto tempo dura cada uma dessas etapas tomar?

478
00:21:46,800 --> 00:21:49,780
Bem, se a corrida
tempo para resolver n elementos

479
00:21:49,780 --> 00:21:53,010
é, vamos chamá-lo muito
genericamente, T de N,

480
00:21:53,010 --> 00:21:55,500
em seguida, a triagem esquerda
metade dos elementos

481
00:21:55,500 --> 00:21:59,720
é, tipo, como dizer,
T de n dividido por 2,

482
00:21:59,720 --> 00:22:03,000
e da mesma forma classificando a metade direita
de elementos é, tipo, como dizer,

483
00:22:03,000 --> 00:22:06,974
T de N 2 dividido e, em seguida
fundindo as metades classificados.

484
00:22:06,974 --> 00:22:08,890
Bem, se eu tenho algum
número de elementos aqui,

485
00:22:08,890 --> 00:22:11,230
como quatro, e algum número
de elementos aqui, como quatro,

486
00:22:11,230 --> 00:22:14,650
e eu tenho que fundir cada um destes quatro
em, e cada um destes quatro, um

487
00:22:14,650 --> 00:22:17,160
depois o outro, de modo que
em última análise, eu tenho oito elementos.

488
00:22:17,160 --> 00:22:20,230
Ela se sente como que é grande o de n passos?

489
00:22:20,230 --> 00:22:23,500
Se eu tenho n dedos e cada um
eles tem que ser incorporada lugar,

490
00:22:23,500 --> 00:22:25,270
que é como mais n passos.

491
00:22:25,270 --> 00:22:27,360
>> Então, na verdade, como uma fórmula,
podemos expressar isso,

492
00:22:27,360 --> 00:22:29,960
embora um pouco assustadoramente em primeiro
vista, mas é algo

493
00:22:29,960 --> 00:22:31,600
que capta exatamente essa lógica.

494
00:22:31,600 --> 00:22:35,710
O tempo de execução, T de n, n IF
é maior do que ou igual a 2.

495
00:22:35,710 --> 00:22:42,500
Neste caso, o caso MAIS, é T de n
dividido por dois, além de T n dividido por 2,

496
00:22:42,500 --> 00:22:45,320
mais grande o de n, alguns
linear número de passos,

497
00:22:45,320 --> 00:22:51,630
talvez exatamente n, talvez 2 vezes
n, mas é mais ou menos, a ordem de n.

498
00:22:51,630 --> 00:22:54,060
De modo que, também, é como podemos
expressar isso como uma fórmula.

499
00:22:54,060 --> 00:22:56,809
Agora você não saberia isso a menos
você gravou em sua mente,

500
00:22:56,809 --> 00:22:58,710
ou procurá-lo no
traseira de um livro, que

501
00:22:58,710 --> 00:23:00,501
poderia ter um pouco
cábula no final,

502
00:23:00,501 --> 00:23:03,940
mas este é, de fato, vai
dá-nos um grande o de n log n,

503
00:23:03,940 --> 00:23:06,620
porque a recorrência que
você está vendo aqui na tela,

504
00:23:06,620 --> 00:23:09,550
se você realmente fez isso para fora, com
um número infinito de exemplos,

505
00:23:09,550 --> 00:23:13,000
ou você fez isso como uma fórmula, você faria
ver que esta, porque esta fórmula

506
00:23:13,000 --> 00:23:17,100
em si é recursivo, com t de
n sobre algo à direita,

507
00:23:17,100 --> 00:23:21,680
e t de N ao longo do lado esquerdo, isto pode
na verdade, ser expresso, em última análise,

508
00:23:21,680 --> 00:23:24,339
tão grande para ir de log n n.

509
00:23:24,339 --> 00:23:26,130
Se não está convencido, isso é
bem por agora, apenas

510
00:23:26,130 --> 00:23:28,960
assumir a fé, que é, de fato,
o que leva a que a recorrência,

511
00:23:28,960 --> 00:23:31,780
mas este é apenas um pouco mais de um
abordagem matemática para olhar

512
00:23:31,780 --> 00:23:36,520
no tempo de execução de merge sort
com base apenas na sua pseudocódigo.

513
00:23:36,520 --> 00:23:39,030
>> Agora vamos dar um pouco de
respiradouro de tudo isso,

514
00:23:39,030 --> 00:23:41,710
e dar uma olhada em um
certo ex-senador, que

515
00:23:41,710 --> 00:23:44,260
pode parecer um pouco familiarizado,
que sentou-se com Eric do Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, há algum tempo, para uma entrevista
no palco, na frente de um grupo inteiro

517
00:23:48,410 --> 00:23:53,710
de pessoas, falando em última análise, sobre
um tópico, que é bastante agora familiar.

518
00:23:53,710 --> 00:23:54,575
Vamos dar uma olhada.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Agora o senador,
você está aqui no Google,

521
00:24:03,890 --> 00:24:09,490
e eu gosto de pensar no
Presidência como uma entrevista de emprego.

522
00:24:09,490 --> 00:24:11,712
Agora é difícil conseguir um emprego como presidente.

523
00:24:11,712 --> 00:24:12,670
PRESIDENTE OBAMA: Certo.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: E você é
vai fazer [inaudível] agora.

525
00:24:13,940 --> 00:24:15,523
Também é difícil conseguir um emprego no Google.

526
00:24:15,523 --> 00:24:17,700
PRESIDENTE OBAMA: Certo.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Temos perguntas,
e pedimos nossas perguntas candidatos,

528
00:24:21,330 --> 00:24:24,310
e este é de Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> PRESIDENTE OBAMA: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: O quê?

531
00:24:27,005 --> 00:24:28,130
Vocês pensam que estou brincando?

532
00:24:28,130 --> 00:24:30,590
Está bem aqui.

533
00:24:30,590 --> 00:24:33,490
Qual é a maneira mais eficiente de
classificar um milhão de 32 bits inteiros?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> PRESIDENTE OBAMA: bom--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Às vezes,
talvez eu sinto muito, maybe--

537
00:24:41,020 --> 00:24:42,750
PRESIDENTE OBAMA: Não, não,
não, não, não, eu penso--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Isso não é ele--

539
00:24:43,240 --> 00:24:45,430
PRESIDENTE OBAMA: I
acho, eu acho que a bolha

540
00:24:45,430 --> 00:24:46,875
tipo seria o caminho errado a seguir.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Vamos lá.

543
00:24:50,535 --> 00:24:52,200
Quem lhe disse isso?

544
00:24:52,200 --> 00:24:54,020
ESTÁ BEM.

545
00:24:54,020 --> 00:24:55,590
Eu não fiz a ciência da computação on--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDENTE OBAMA: Nós temos
temos os nossos espiões lá dentro.

547
00:24:58,986 --> 00:24:59,860
PROFESSOR: Tudo bem.

548
00:24:59,860 --> 00:25:03,370
Vamos deixar atrás de nós agora o
mundo teórica de algoritmos

549
00:25:03,370 --> 00:25:06,520
na análise assintótica
da mesma, e retornar para alguns tópicos

550
00:25:06,520 --> 00:25:09,940
a partir da semana zero e um, e de início
para remover algumas rodinhas,

551
00:25:09,940 --> 00:25:10,450
Se você for.

552
00:25:10,450 --> 00:25:13,241
Para que você realmente entender
em última análise, a partir do zero, o que é

553
00:25:13,241 --> 00:25:16,805
acontecendo debaixo do capô, quando você
escrever, compilar e executar programas.

554
00:25:16,805 --> 00:25:19,680
Lembre-se, em particular, que este era
o primeiro programa C nós olhamos,

555
00:25:19,680 --> 00:25:22,840
um programa canônica, simples
das sortes, relativamente falando,

556
00:25:22,840 --> 00:25:24,620
em que, imprime, Olá Mundo.

557
00:25:24,620 --> 00:25:27,610
E lembro que eu disse, o processo
que o código fonte atravessa

558
00:25:27,610 --> 00:25:28,430
é exatamente isso.

559
00:25:28,430 --> 00:25:31,180
Você pega o seu código-fonte, passar
-lo através de um compilador, como Clang,

560
00:25:31,180 --> 00:25:34,650
e sai código objeto, que
pode parecer como este, zeros e uns

561
00:25:34,650 --> 00:25:37,880
que a CPU do computador central
unidade de processamento ou cérebro,

562
00:25:37,880 --> 00:25:39,760
em última análise, entende.

563
00:25:39,760 --> 00:25:42,460
>> Acontece que isso é uma
pouco de uma simplificação,

564
00:25:42,460 --> 00:25:44,480
que estamos agora em um
posição de provocar uma separação

565
00:25:44,480 --> 00:25:46,720
para entender o que está realmente sido
acontecendo debaixo do capô

566
00:25:46,720 --> 00:25:48,600
cada vez que você executa
Tinido, ou, mais geralmente,

567
00:25:48,600 --> 00:25:53,040
cada vez que você faz um programa,
Faça uso e CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Em particular, o material como
este é gerado primeiro,

569
00:25:56,760 --> 00:25:58,684
quando você compilar seu programa.

570
00:25:58,684 --> 00:26:00,600
Em outras palavras, quando
levar o seu código-fonte

571
00:26:00,600 --> 00:26:04,390
e compilá-lo, o que é primeiro
sendo emitido por Clang

572
00:26:04,390 --> 00:26:06,370
é algo conhecido como código de montagem.

573
00:26:06,370 --> 00:26:08,990
E, de fato, ele parece exatamente como este.

574
00:26:08,990 --> 00:26:11,170
>> Corri um comando no
linha de comando anterior.

575
00:26:11,170 --> 00:26:16,260
Hello.c Clang de capital traço s,
e isso criou um arquivo

576
00:26:16,260 --> 00:26:19,490
para mim chamados hello.s,
no interior dos quais foram exactamente

577
00:26:19,490 --> 00:26:22,290
estes conteúdos, e um pouco mais
acima e um pouco mais abaixo,

578
00:26:22,290 --> 00:26:25,080
mas eu coloquei o juiciest
informações aqui na tela.

579
00:26:25,080 --> 00:26:29,190
E se você olhar de perto, você verá
pelo menos algumas palavras-chave familiares.

580
00:26:29,190 --> 00:26:31,330
Temos principal na parte superior.

581
00:26:31,330 --> 00:26:35,140
Temos printf para baixo no meio.

582
00:26:35,140 --> 00:26:38,670
E também temos Olá mundo
barra invertida n entre aspas abaixo.

583
00:26:38,670 --> 00:26:42,450
>> E tudo o mais aqui
é instruções de nível muito baixo

584
00:26:42,450 --> 00:26:45,500
que a CPU do computador entende.

585
00:26:45,500 --> 00:26:50,090
Instruções da CPU que se movem de memória
ao redor, que seqüências de carga de memória,

586
00:26:50,090 --> 00:26:52,750
e, finalmente, imprimir
as coisas na tela.

587
00:26:52,750 --> 00:26:56,780
Agora o que acontece embora depois
este código assembly é gerado?

588
00:26:56,780 --> 00:26:59,964
Em última instância, você faz, de fato,
ainda gerar código objeto.

589
00:26:59,964 --> 00:27:02,630
Mas os passos que têm realmente
vem acontecendo debaixo do capô

590
00:27:02,630 --> 00:27:04,180
olhar um pouco mais como este.

591
00:27:04,180 --> 00:27:08,390
O código fonte torna-se o código de montagem,
que então se torna código objeto,

592
00:27:08,390 --> 00:27:11,930
e as palavras-chave aqui são de que,
quando você compilar o código fonte,

593
00:27:11,930 --> 00:27:16,300
vem para fora do código de montagem, e, em seguida,
quando você montar o seu código de montagem,

594
00:27:16,300 --> 00:27:17,800
fora vem código objeto.

595
00:27:17,800 --> 00:27:20,360
>> Agora Clang é super sofisticado,
como um monte de compiladores,

596
00:27:20,360 --> 00:27:23,151
e ele faz todas essas etapas
juntos, e ele faz não necessariamente

597
00:27:23,151 --> 00:27:25,360
saída de qualquer intermediário
arquivos que você mesmo pode ver.

598
00:27:25,360 --> 00:27:28,400
Ele só compila as coisas,
que é o termo geral que

599
00:27:28,400 --> 00:27:30,000
descreve todo este processo.

600
00:27:30,000 --> 00:27:32,000
Mas se você realmente quer
para ser determinado, não há

601
00:27:32,000 --> 00:27:34,330
muito mais acontecendo lá também.

602
00:27:34,330 --> 00:27:38,860
>> Mas vamos também considerar agora que mesmo
esse programa super simples, hello.c,

603
00:27:38,860 --> 00:27:40,540
chamado de uma função.

604
00:27:40,540 --> 00:27:41,870
Apelou printf.

605
00:27:41,870 --> 00:27:46,900
Mas eu não queria escrever printf, de fato,
que vem com c, por assim dizer.

606
00:27:46,900 --> 00:27:51,139
É um recall função que é
declarou em io.h padrão, que

607
00:27:51,139 --> 00:27:53,180
é um arquivo de cabeçalho, que
é um tema que vamos realmente

608
00:27:53,180 --> 00:27:55,780
mergulhar em mais profundidade antes de tempo.

609
00:27:55,780 --> 00:27:58,000
Mas um arquivo de cabeçalho é
tipicamente acompanhada

610
00:27:58,000 --> 00:28:02,920
por um arquivo de código, arquivo de código fonte, de modo
muito parecido existe io.h. padrão

611
00:28:02,920 --> 00:28:05,930
>> Há algum tempo atrás, alguém,
ou de alguém, também escreveu

612
00:28:05,930 --> 00:28:11,040
um arquivo chamado io.c padrão, em
que as definições efectivas,

613
00:28:11,040 --> 00:28:15,220
ou implementações de printf,
e cachos de outras funções,

614
00:28:15,220 --> 00:28:16,870
são realmente escrito.

615
00:28:16,870 --> 00:28:22,140
Assim, dado que, se considerar ter
aqui à esquerda, ola.c, que quando

616
00:28:22,140 --> 00:28:26,250
compilado, nos dá hello.s, mesmo se
Clang não se incomode de poupança em um lugar

617
00:28:26,250 --> 00:28:31,360
podemos vê-lo, e que o código de montagem
fica montada em hello.o, que

618
00:28:31,360 --> 00:28:34,630
é, na verdade, o nome padrão
dado sempre que você compilar fonte

619
00:28:34,630 --> 00:28:39,350
código em código objeto, mas não são
completamente pronto para executá-lo ainda,

620
00:28:39,350 --> 00:28:41,460
porque mais um passo
tem que acontecer, e tem

621
00:28:41,460 --> 00:28:44,440
vem acontecendo durante os últimos
semanas, talvez sem o seu conhecimento.

622
00:28:44,440 --> 00:28:47,290
>> Especificamente em algum lugar
CS50 em IDE, e este,

623
00:28:47,290 --> 00:28:49,870
também, vai ser um pouco de um
simplificação excessiva por um momento,

624
00:28:49,870 --> 00:28:54,670
não é, ou foi em cima de um tempo,
um arquivo chamado io.c padrão,

625
00:28:54,670 --> 00:28:58,440
que alguém compilados em
io.s padrão ou o equivalente,

626
00:28:58,440 --> 00:29:02,010
alguém que, em seguida, montado
em io.o padrão,

627
00:29:02,010 --> 00:29:04,600
ou se vê em um
arquivo ligeiramente diferente

628
00:29:04,600 --> 00:29:07,220
formato que pode ter um diferente
extensão de arquivo completo,

629
00:29:07,220 --> 00:29:11,720
mas, em teoria e conceitualmente, exatamente
esses passos tinha que acontecer de alguma forma.

630
00:29:11,720 --> 00:29:14,060
O que significa dizer, que agora
quando estou escrevendo um programa,

631
00:29:14,060 --> 00:29:17,870
hello.c, que apenas diz: Olá mundo,
e eu estou usando o código de outra pessoa

632
00:29:17,870 --> 00:29:22,480
como printf, que foi uma vez em cima de um
tempo, em um arquivo chamado io.c padrão,

633
00:29:22,480 --> 00:29:26,390
em seguida, de alguma forma eu tenho que tomar minha
código objeto, meus zeros e uns,

634
00:29:26,390 --> 00:29:29,260
e objeto dessa pessoa
código, ou zeros e uns,

635
00:29:29,260 --> 00:29:34,970
e de alguma forma vincular-los juntos em
um arquivo final, chamado Olá, que

636
00:29:34,970 --> 00:29:38,070
tem todos os zeros e
os de minha função principal,

637
00:29:38,070 --> 00:29:40,830
e todos os zeros
e aqueles para printf.

638
00:29:40,830 --> 00:29:44,900
>> E, de fato, esse último processo é
chamada, ligar o seu código objeto.

639
00:29:44,900 --> 00:29:47,490
A saída dos quais
é um arquivo executável.

640
00:29:47,490 --> 00:29:49,780
Então, na justiça, na
final do dia, nada

641
00:29:49,780 --> 00:29:52,660
mudou desde uma semana, quando nós
primeiro começou a compilar programas.

642
00:29:52,660 --> 00:29:55,200
Com efeito, tudo isto tem sido
acontecendo debaixo do capô,

643
00:29:55,200 --> 00:29:57,241
mas agora estamos em uma posição
onde podemos realmente

644
00:29:57,241 --> 00:29:58,794
desmembrar essas várias etapas.

645
00:29:58,794 --> 00:30:00,710
E, de fato, no final
do dia, nós ainda somos

646
00:30:00,710 --> 00:30:04,480
à esquerda com zeros e uns, que
é realmente uma ótima segue agora

647
00:30:04,480 --> 00:30:08,620
a outra capacidade de C, que
nós não tivemos a alavancar mais provável

648
00:30:08,620 --> 00:30:11,250
até à data, conhecida como operadores bit a bit.

649
00:30:11,250 --> 00:30:15,220
Em outras palavras, até o momento, a qualquer hora nós temos
tratadas com dados variáveis ​​em C ou em C,

650
00:30:15,220 --> 00:30:17,660
nós tivemos coisas como
caracteres e carros alegóricos e ins

651
00:30:17,660 --> 00:30:21,990
e anseia e duplas e similares, mas
todos esses são, pelo menos, oito bits.

652
00:30:21,990 --> 00:30:25,550
Temos ainda nunca foi capaz de
manipular bits individuais,

653
00:30:25,550 --> 00:30:28,970
mesmo que um bit individual, nós
sabe, pode representar um 0 e um 1.

654
00:30:28,970 --> 00:30:32,640
Agora verifica-se que em C, você
pode ter acesso a bits individuais,

655
00:30:32,640 --> 00:30:35,530
se você souber a sintaxe,
com o qual se chegar a eles.

656
00:30:35,530 --> 00:30:38,010
>> Então, vamos dar uma olhada
em operadores bit a bit.

657
00:30:38,010 --> 00:30:41,700
Então, retratado aqui estão alguns símbolos que
nós temos, tipo de, mais ou menos, visto antes.

658
00:30:41,700 --> 00:30:45,580
Eu vejo um e comercial, vertical
bar, e alguns outros também,

659
00:30:45,580 --> 00:30:49,430
e lembrar que ampersand ampersand
é algo que temos visto antes.

660
00:30:49,430 --> 00:30:54,060
O operador lógico AND, onde você tem
dois deles em conjunto, ou o OU lógico

661
00:30:54,060 --> 00:30:56,300
operador, onde você
tem duas barras verticais.

662
00:30:56,300 --> 00:31:00,550
Operadores bit a bit, o que nós vamos
veja operar em pedaços individualmente,

663
00:31:00,550 --> 00:31:03,810
basta usar um único e comercial, um
única barra vertical, o símbolo de acento circunflexo

664
00:31:03,810 --> 00:31:06,620
vem em seguida, a pequena
til, e depois à esquerda

665
00:31:06,620 --> 00:31:08,990
colchete esquerdo suporte, ou
suporte direito colchete direito.

666
00:31:08,990 --> 00:31:10,770
Cada um deles têm significados diferentes.

667
00:31:10,770 --> 00:31:11,950
>> Na verdade, vamos dar uma olhada.

668
00:31:11,950 --> 00:31:16,560
Vamos velha escola hoje, e uso
uma tela de toque de outrora,

669
00:31:16,560 --> 00:31:18,002
conhecido como um quadro branco.

670
00:31:18,002 --> 00:31:19,710
E este quadro branco
vai nos permitir

671
00:31:19,710 --> 00:31:27,360
para expressar alguns símbolos bastante simples,
ou melhor, alguns fórmulas bastante simples,

672
00:31:27,360 --> 00:31:29,560
que, em seguida, em última análise, nós podemos
alavancagem, a fim

673
00:31:29,560 --> 00:31:33,230
para acessar indivíduo
bits dentro de um programa C.

674
00:31:33,230 --> 00:31:34,480
Em outras palavras, vamos fazer isso.

675
00:31:34,480 --> 00:31:37,080
Vamos primeiro falar para um
momento sobre ampersand,

676
00:31:37,080 --> 00:31:39,560
que é o bit a bit operador AND.

677
00:31:39,560 --> 00:31:42,130
Em outras palavras, esta é
um operador que permite

678
00:31:42,130 --> 00:31:45,930
me para ter uma variável do lado esquerdo
normalmente, e uma variável da mão direita,

679
00:31:45,930 --> 00:31:50,640
ou um valor individual, que se nós E
los juntos, me dá um resultado final.

680
00:31:50,640 --> 00:31:51,560
Então o que eu quero dizer?

681
00:31:51,560 --> 00:31:54,840
Se em um programa, você tem uma variável
que armazena um desses valores,

682
00:31:54,840 --> 00:31:58,000
ou vamos mantê-lo simples, e apenas
escreva zeros e uns individualmente,

683
00:31:58,000 --> 00:32:00,940
aqui está como o operador E comercial funciona.

684
00:32:00,940 --> 00:32:06,400
0 0 comercial está indo igual a 0.

685
00:32:06,400 --> 00:32:07,210
Agora, por que é isso?

686
00:32:07,210 --> 00:32:09,291
>> É muito semelhante ao
As expressões booleanas,

687
00:32:09,291 --> 00:32:10,540
que temos discutido até agora.

688
00:32:10,540 --> 00:32:15,800
Se você acha que depois de tudo, o 0 é
false, 0 é falso, falso e falso

689
00:32:15,800 --> 00:32:18,720
é, como já discutimos
logicamente, também falsa.

690
00:32:18,720 --> 00:32:20,270
Então, nós temos 0 aqui também.

691
00:32:20,270 --> 00:32:24,390
Se você tomar 0 e comercial
1, bem que, também,

692
00:32:24,390 --> 00:32:29,890
vai ser 0, porque para isso
expressão à esquerda para ser verdade ou 1,

693
00:32:29,890 --> 00:32:32,360
seria necessário para ser verdade e verdade.

694
00:32:32,360 --> 00:32:36,320
Mas aqui temos false
e verdadeira, ou 0 e 1.

695
00:32:36,320 --> 00:32:42,000
Agora, novamente, se temos um E comercial
0, que, também, vai ser 0,

696
00:32:42,000 --> 00:32:47,240
e se tivermos um e comercial 1,
finalmente temos um bit 1.

697
00:32:47,240 --> 00:32:50,340
Portanto, em outras palavras, nós não estamos fazendo
nada de interessante com este operador

698
00:32:50,340 --> 00:32:51,850
ainda, este operador comercial.

699
00:32:51,850 --> 00:32:53,780
É o bit a bit operador AND.

700
00:32:53,780 --> 00:32:57,290
Mas estes são os ingredientes
através do qual nós podemos fazer

701
00:32:57,290 --> 00:32:59,240
coisas interessantes, como veremos em breve.

702
00:32:59,240 --> 00:33:02,790
>> Agora vamos olhar apenas o único
barra vertical até aqui, à direita.

703
00:33:02,790 --> 00:33:06,710
Se eu tiver um bit 0 e I
OR-o com, o bit a bit

704
00:33:06,710 --> 00:33:11,030
OR operador, outro bit 0,
que vai me dar 0.

705
00:33:11,030 --> 00:33:17,540
Se eu tomar um bit 0 e OR-lo com
um bit 1, então eu estou indo para obter um.

706
00:33:17,540 --> 00:33:19,830
E, de fato, apenas para
clareza, deixe-me voltar,

707
00:33:19,830 --> 00:33:23,380
de modo que minhas barras verticais
não são confundidos com 1s.

708
00:33:23,380 --> 00:33:26,560
Deixe-me reescrever todos
meu 1 é um pouco mais

709
00:33:26,560 --> 00:33:32,700
claramente, para que possamos ver ao lado, se eu
ter um 1 ou 0, que vai ser um 1,

710
00:33:32,700 --> 00:33:39,060
e se eu tiver um 1 ou 1 que,
também, vai ser um 1.

711
00:33:39,060 --> 00:33:42,900
Assim você pode ver que a lógica OR
operador se comporta de maneira muito diferente.

712
00:33:42,900 --> 00:33:48,070
Isto dá-me OU 0 0 0 me dá, mas
cada outra combinação dá-me uma.

713
00:33:48,070 --> 00:33:52,480
Então, enquanto eu tiver um 1 no
fórmula, o resultado será uma.

714
00:33:52,480 --> 00:33:55,580
>> Em contraste com a E
operador, o comercial,

715
00:33:55,580 --> 00:34:00,940
só se eu tenho dois números 1 no
equação, eu realmente obter um 1.

716
00:34:00,940 --> 00:34:02,850
Agora há alguns outros
operadores também.

717
00:34:02,850 --> 00:34:04,810
Um deles é um pouco mais complicado.

718
00:34:04,810 --> 00:34:07,980
Então deixe-me ir em frente e apagar
esta para libertar algum espaço.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
E vamos dar uma olhada no
símbolo de acento circunflexo, por apenas um momento.

721
00:34:16,460 --> 00:34:18,210
Este é tipicamente um
personagem que você pode digitar

722
00:34:18,210 --> 00:34:21,420
em seu teclado e segurando Shift
em seguida, um dos números em cima de seu EUA

723
00:34:21,420 --> 00:34:22,250
teclado.

724
00:34:22,250 --> 00:34:26,190
>> Então este é o exclusivo
Operador OU, OU exclusivo.

725
00:34:26,190 --> 00:34:27,790
Então, nós apenas viu o operador OR.

726
00:34:27,790 --> 00:34:29,348
Este é o OR exclusivo do operador.

727
00:34:29,348 --> 00:34:30,639
O que é realmente a diferença?

728
00:34:30,639 --> 00:34:34,570
Bem, vamos apenas olhar para a fórmula,
e usar isto como ingredientes em última instância.

729
00:34:34,570 --> 00:34:37,690
0 XOR 0.

730
00:34:37,690 --> 00:34:39,650
Eu vou dizer é sempre 0.

731
00:34:39,650 --> 00:34:41,400
Essa é a definição de XOR.

732
00:34:41,400 --> 00:34:47,104
XOR 0 1 vai ser 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 vai ser 1,
e um XOR 1 vai ser?

734
00:34:58,810 --> 00:34:59,890
Errado?

735
00:34:59,890 --> 00:35:00,520
Ou não é?

736
00:35:00,520 --> 00:35:01,860
Eu não sei.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Agora, o que está acontecendo aqui?

739
00:35:04,700 --> 00:35:06,630
Bem, pense sobre o
nome deste operador.

740
00:35:06,630 --> 00:35:09,980
OU exclusivo, de modo a
nome, tipo, sugere,

741
00:35:09,980 --> 00:35:13,940
a resposta só vai ser
1 se as entradas são exclusivas,

742
00:35:13,940 --> 00:35:15,560
exclusivamente diferente.

743
00:35:15,560 --> 00:35:18,170
Então, aqui estão as entradas do
mesma, de modo que a saída é 0.

744
00:35:18,170 --> 00:35:20,700
Aqui as entradas são o
mesma, de modo que a saída é 0.

745
00:35:20,700 --> 00:35:25,640
Aqui estão as saídas são diferentes, eles
são exclusivos, e então a saída é 1.

746
00:35:25,640 --> 00:35:28,190
Portanto, é muito semelhante ao
E, é muito semelhante,

747
00:35:28,190 --> 00:35:32,760
ou melhor, é muito semelhante ao
OU, mas apenas de uma forma exclusiva.

748
00:35:32,760 --> 00:35:36,210
Este não é um 1,
porque temos dois de 1,

749
00:35:36,210 --> 00:35:38,621
e não exclusivamente, apenas um deles.

750
00:35:38,621 --> 00:35:39,120
Tudo certo.

751
00:35:39,120 --> 00:35:40,080
E os outros?

752
00:35:40,080 --> 00:35:44,220
Bem o til, entretanto, é
realmente agradável e simples, felizmente.

753
00:35:44,220 --> 00:35:46,410
E esta é uma unary
operador, o que significa

754
00:35:46,410 --> 00:35:50,400
é aplicado a apenas uma entrada,
um operando, por assim dizer.

755
00:35:50,400 --> 00:35:51,800
Não a um esquerdo e um direito.

756
00:35:51,800 --> 00:35:56,050
Em outras palavras, se você tomar til de
0, a resposta será o oposto.

757
00:35:56,050 --> 00:35:59,710
E se você tomar til de 1, o
resposta haverá o oposto.

758
00:35:59,710 --> 00:36:02,570
Assim, o operador til é
uma forma de negar um pouco,

759
00:36:02,570 --> 00:36:06,000
ou virar um pouco de
0 a 1, ou de 1 a 0.

760
00:36:06,000 --> 00:36:09,820
>> E isso deixa-nos, finalmente,
com apenas dois operadores finais,

761
00:36:09,820 --> 00:36:13,840
o chamado deslocamento para a esquerda, e o
o chamado operador de deslocamento para a direita.

762
00:36:13,840 --> 00:36:16,620
Vamos dar uma olhada em como os trabalhos.

763
00:36:16,620 --> 00:36:20,780
O operador de deslocamento para a esquerda, por escrito
com dois colchetes como essa,

764
00:36:20,780 --> 00:36:22,110
opera como se segue.

765
00:36:22,110 --> 00:36:27,390
Se a minha entrada, ou a minha operando, à esquerda
operador de deslocamento é simplesmente um 1.

766
00:36:27,390 --> 00:36:33,750
E eu, em seguida, dizer ao computador para
desvio à esquerda que uma, digamos sete lugares,

767
00:36:33,750 --> 00:36:37,150
o resultado é como se eu
tomar essa 1, e movê-lo

768
00:36:37,150 --> 00:36:40,160
sete lugares mais à
esquerda e, por padrão,

769
00:36:40,160 --> 00:36:42,270
vamos supor que
o espaço à direita

770
00:36:42,270 --> 00:36:44,080
vai ser preenchido com zeros.

771
00:36:44,080 --> 00:36:50,316
Em outras palavras, uma mudança deixou 7 vai
para me dar que 1, seguido por 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 zeros.

773
00:36:54,060 --> 00:36:57,380
Então, de certa forma, ele permite que você
ter um número pequeno como 1,

774
00:36:57,380 --> 00:37:00,740
e torná-lo muito claramente
muito, muito maior, desta forma,

775
00:37:00,740 --> 00:37:06,460
mas nós estamos indo realmente para ver
abordagens mais inteligentes para ele

776
00:37:06,460 --> 00:37:08,080
Em vez disso, como bem,

777
00:37:08,080 --> 00:37:08,720
>> Tudo certo.

778
00:37:08,720 --> 00:37:10,060
É isso por três semanas.

779
00:37:10,060 --> 00:37:11,400
Vamos vê-lo na próxima vez.

780
00:37:11,400 --> 00:37:12,770
Este foi CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [Música tocando]

783
00:37:22,243 --> 00:37:25,766
>> COLUNA 1: Ele estava no snack-
bar comendo um sundae de chocolate.

784
00:37:25,766 --> 00:37:28,090
Ele tinha tudo sobre o seu rosto.

785
00:37:28,090 --> 00:37:30,506
Ele está vestindo que o chocolate como uma barba

786
00:37:30,506 --> 00:37:31,756
COLUNA 2: O que você está fazendo?

787
00:37:31,756 --> 00:37:32,422
COLUNA 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
O quê?

789
00:37:33,500 --> 00:37:36,800
>> COLUNA 2: Você acabou de duplo mergulho?

790
00:37:36,800 --> 00:37:38,585
Você dupla mergulhou o chip.

791
00:37:38,585 --> 00:37:39,460
COLUNA 3: Desculpe-me.

792
00:37:39,460 --> 00:37:44,440
COLUNA 2: Você mergulhou o chip, você
deu uma mordida, e você mergulhou novamente.

793
00:37:44,440 --> 00:37:44,940
COLUNA 3:

794
00:37:44,940 --> 00:37:48,440
COLUNA 2: Assim que é como colocar
todo o seu direito boca no mergulho.

795
00:37:48,440 --> 00:37:52,400
Da próxima vez que você tomar um chip,
apenas mergulhá-lo uma vez, e terminá-la.

796
00:37:52,400 --> 00:37:53,890
>> COLUNA 3: Você sabe o que, Dan?

797
00:37:53,890 --> 00:37:58,006
Você mergulha a maneira que você quiser mergulhar.

798
00:37:58,006 --> 00:38:01,900
Vou mergulhar a maneira que eu quero mergulhar.

799
00:38:01,900 --> 00:38:03,194