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

2
00:00:11,904 --> 00:00:12,910
>> PROFESOR: Todo ben.

3
00:00:12,910 --> 00:00:16,730
Este é CS50 e este é
o fin de semana tres.

4
00:00:16,730 --> 00:00:20,230
Entón, nós estamos aquí hoxe, non en Sanders
Theater, en vez de Weidner Library.

5
00:00:20,230 --> 00:00:23,170
Dentro dos cales é un estudo
coñecido como Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
ou digamos Estudo H, ou debe
nós dizer-- se lle gusta que broma,

7
00:00:28,310 --> 00:00:30,540
é, en realidade, a partir de
compañeiro, Mark, en liña,

8
00:00:30,540 --> 00:00:32,420
que suxeriu tanto vía Twitter.

9
00:00:32,420 --> 00:00:34,270
Agora, o que é legal sobre
estar aquí nun estudo

10
00:00:34,270 --> 00:00:38,410
é que eu estou rodeado por estes do verde
paredes, unha pantalla verde ou chromakey,

11
00:00:38,410 --> 00:00:43,290
por así dicir, o que significa que de CS50
equipo de produción, sen saber para min

12
00:00:43,290 --> 00:00:47,380
agora, podería estar poñendo
me máis en calquera lugar do mundo,

13
00:00:47,380 --> 00:00:48,660
para mellor ou para peor.

14
00:00:48,660 --> 00:00:51,800
>> Agora, o que temos por diante, conxunto de problemas
dous está nas súas mans para esta semana,

15
00:00:51,800 --> 00:00:53,830
pero con xogo de problemas
tres da semana que vén,

16
00:00:53,830 --> 00:00:56,600
será desafiado con
a chamada de xogo 15,

17
00:00:56,600 --> 00:00:58,960
un favor de partido vello que
pode lembrar de recibir

18
00:00:58,960 --> 00:01:02,030
como un neno que ten un grupo enteiro
de números que pode desprazar cara arriba, abaixo,

19
00:01:02,030 --> 00:01:05,790
esquerda e dereita, e hai un gap
dentro do puzzle, no que

20
00:01:05,790 --> 00:01:07,840
realmente desprazar as pezas de puzzle.

21
00:01:07,840 --> 00:01:11,150
En definitiva, recibe esta
puzzle nalgunha orde semi chou,

22
00:01:11,150 --> 00:01:12,940
eo obxectivo é a
clasificalos lo de arriba abaixo,

23
00:01:12,940 --> 00:01:16,310
esquerda a dereita, a partir dun
todo o camiño ata a 15.

24
00:01:16,310 --> 00:01:19,360
>> Desafortunadamente, a aplicación
terá en mans

25
00:01:19,360 --> 00:01:21,590
será software
base, non fisicamente.

26
00:01:21,590 --> 00:01:25,280
Está realmente vai ter que escribir
código co que un estudante ou usuario pode

27
00:01:25,280 --> 00:01:26,760
xogar o xogo de 15.

28
00:01:26,760 --> 00:01:29,030
E, de feito, en que o hacker
edición do xogo de 15,

29
00:01:29,030 --> 00:01:32,155
vai ser un desafío para aplicar,
non só o xogo desta vella escola

30
00:01:32,155 --> 00:01:35,010
xogo, mais si a solución
diso, a posta en marcha de xeito deus,

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

32
00:01:38,280 --> 00:01:41,080
dando-lles información,
despois información, despois información.

33
00:01:41,080 --> 00:01:42,280
Entón, máis sobre iso a próxima semana.

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

35
00:01:43,720 --> 00:01:47,610
>> Por agora lembrar que a principios desta semana
tivemos este momento de angustia, se quixeren,

36
00:01:47,610 --> 00:01:52,560
polo que o mellor que estabamos facendo selección
wise foi un límite superior de grande n

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

38
00:01:53,210 --> 00:01:56,520
Noutras palabras, bubble sort,
tipo de selección, ordenación por inserción,

39
00:01:56,520 --> 00:01:59,120
todos eles, mentres diferente
na súa implantación,

40
00:01:59,120 --> 00:02:03,480
converteu nun n ao cadrado que funciona
tempo no peor caso.

41
00:02:03,480 --> 00:02:06,010
E nós xeralmente asumen que
o peor caso para clasificar

42
00:02:06,010 --> 00:02:08,814
é aquel que os seus inputs
son completamente cara atrás.

43
00:02:08,814 --> 00:02:11,980
E, de feito, levou bastante a poucos pasos
para aplicar cada un deses algoritmos.

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

45
00:02:15,110 --> 00:02:19,390
contra a especie de selección contra outra
que chamamos merge sort na época,

46
00:02:19,390 --> 00:02:22,120
e propoño que está tomando
vantaxe de unha lección de semana

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

48
00:02:24,060 --> 00:02:28,810
E de algunha maneira alcanzar algún tipo de
logarítmica tempo de funcionamento, en definitiva,

49
00:02:28,810 --> 00:02:31,024
en vez de algo
iso é puramente cuadrática.

50
00:02:31,024 --> 00:02:33,440
E non é moi logarítmica,
é un pouco máis do que iso.

51
00:02:33,440 --> 00:02:36,520
Pero se se lembra de clase,
foi moito máis rápido.

52
00:02:36,520 --> 00:02:38,210
Imos dar un ollo onde paramos.

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

54
00:02:41,880 --> 00:02:45,370
>> Bubble sort contra selección
tipo contra merge sort.

55
00:02:45,370 --> 00:02:47,700
Agora están todos correndo, en
teoría, ao mesmo tempo.

56
00:02:47,700 --> 00:02:50,510
A CPU está en execución na mesma velocidade.

57
00:02:50,510 --> 00:02:54,990
Pero pode sentir como aburrido iso
vai moi rápido para facer,

58
00:02:54,990 --> 00:02:58,790
e quão rápido cando injetamos
un pouco de algoritmos de semana de cero,

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

60
00:03:00,080 --> 00:03:01,630
>> Así, tipo marca parece incrible.

61
00:03:01,630 --> 00:03:05,220
Como podemos aproveitala lo, a fin
para ordenar os números máis rapidamente.

62
00:03:05,220 --> 00:03:07,140
Ben, imos pensar de volta
para un ingrediente que

63
00:03:07,140 --> 00:03:10,380
tivo de volta na semana cero, que de
buscar alguén nunha lista telefónica,

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

65
00:03:12,380 --> 00:03:14,560
a través do cal podemos atopar
alguén como Mike Smith,

66
00:03:14,560 --> 00:03:16,310
parecía un pouco algo así.

67
00:03:16,310 --> 00:03:20,820
>> Agora, bótalle un ollo en particular
na liña 7 e 8, e 10 e 11,

68
00:03:20,820 --> 00:03:25,240
que inducen a ese ciclo, polo que mantivemos
voltar á liña 3 de novo, e de novo,

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

70
00:03:26,520 --> 00:03:31,790
Pero resulta que vemos
ese algoritmo, aquí en pseudocódigo,

71
00:03:31,790 --> 00:03:33,620
un pouco máis de forma holística.

72
00:03:33,620 --> 00:03:35,960
En realidade, o que estou buscando
a aquí na pantalla,

73
00:03:35,960 --> 00:03:41,180
é un algoritmo para a busca de
Mike Smith entre algúns conxunto de páxinas.

74
00:03:41,180 --> 00:03:45,520
E, de feito, podemos simplificar esta
algoritmo nesas liñas 7 e 8,

75
00:03:45,520 --> 00:03:49,860
e 10 e 11 a só dicir isto,
que eu teño presentado aquí en amarelo.

76
00:03:49,860 --> 00:03:52,210
Noutras palabras, se o Mike
Smith é o inicio do libro,

77
00:03:52,210 --> 00:03:55,004
nós non precisa especificar paso
a paso agora como ir atopalo.

78
00:03:55,004 --> 00:03:56,920
Non temos para especificar
voltar á liña 3,

79
00:03:56,920 --> 00:03:58,960
por que nós non só no seu lugar,
digamos, máis xeralmente,

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

81
00:04:01,500 --> 00:04:03,960
>> Por outra banda, se o Mike é
de feito, ao final do libro,

82
00:04:03,960 --> 00:04:07,540
por que non podemos só citar investigación unquote
para Mike na metade dereita do libro.

83
00:04:07,540 --> 00:04:11,030
Noutras palabras, por que non acabamos
tipo de punt para nós mesmos dicindo:

84
00:04:11,030 --> 00:04:13,130
buscar Mike neste
subconxunto do libro,

85
00:04:13,130 --> 00:04:16,279
e deixar para o noso existente
algoritmo para dicir

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

87
00:04:18,750 --> 00:04:20,750
Noutras palabras, o noso
algoritmo funciona se é

88
00:04:20,750 --> 00:04:24,670
un libro de teléfono desta espesor, esta
espesor, ou calquera espesor que sexa.

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

90
00:04:27,826 --> 00:04:29,950
Noutras palabras, o
pantalla aquí, é un algoritmo

91
00:04:29,950 --> 00:04:33,130
para a busca de Mike Smith
entre as páxinas dun libro de teléfono.

92
00:04:33,130 --> 00:04:37,410
Así, na liña 7 e 10, imos
só dicir exactamente iso.

93
00:04:37,410 --> 00:04:40,250
E eu uso este término nun momento
atrás, e de feito, recursão

94
00:04:40,250 --> 00:04:42,450
é a palabra de orde, de momento,
e é este proceso

95
00:04:42,450 --> 00:04:47,210
de facer algo por algún cíclica
usando o código que xa ten,

96
00:04:47,210 --> 00:04:49,722
e chamando-o de novo,
e unha vez máis, e de novo.

97
00:04:49,722 --> 00:04:51,930
Agora vai ser importante
que dalgún xeito inferior

98
00:04:51,930 --> 00:04:53,821
para fóra, e non facelo infinitamente longo.

99
00:04:53,821 --> 00:04:56,070
Se non, imos
teñen, de feito un loop infinito.

100
00:04:56,070 --> 00:04:59,810
Pero imos ver se podemos prestar esa idea
dunha recursão, facendo algo novo

101
00:04:59,810 --> 00:05:03,600
e de novo e de novo, para resolver
o problema de ordenación mediante fusión

102
00:05:03,600 --> 00:05:05,900
tipo, tanto máis eficiente.

103
00:05:05,900 --> 00:05:06,970
>> Entón, eu lle merge sort.

104
00:05:06,970 --> 00:05:07,920
Imos dar un ollo.

105
00:05:07,920 --> 00:05:10,850
Entón aquí é pseudocódigo, con
que poderiamos aplicar a selección,

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 é simplemente iso.

108
00:05:13,880 --> 00:05:15,940
Sobre a entrada de n elementos,
noutras palabras, se está

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

110
00:05:18,830 --> 00:05:22,430
se está dado n elementos, se
n sexa inferior a 2, só volver.

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

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

113
00:05:26,430 --> 00:05:30,446
ou é de tamaño 0 ou 1, e
en ambos destes casos triviais,

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

115
00:05:31,570 --> 00:05:32,810
Se non existe unha lista, está clasificado.

116
00:05:32,810 --> 00:05:35,185
E se hai unha lista de lonxitude
1, é obviamente clasificadas.

117
00:05:35,185 --> 00:05:38,280
Así, o algoritmo que só
realmente facer algo interesante,

118
00:05:38,280 --> 00:05:40,870
se temos dous ou máis
elementos que nos deu.

119
00:05:40,870 --> 00:05:42,440
Entón, imos ollar para a maxia entón.

120
00:05:42,440 --> 00:05:47,500
Logo clasificar a metade esquerda dos elementos,
a continuación, clasificar a metade dereita de elementos,

121
00:05:47,500 --> 00:05:49,640
a continuación, mesturar as metades clasificados.

122
00:05:49,640 --> 00:05:52,440
E o que é tipo de mente dobra
aquí, é que realmente non

123
00:05:52,440 --> 00:05:56,190
parecen terlle dito
nada aínda, non?

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

125
00:05:59,560 --> 00:06:01,800
a continuación, a metade dereita, a continuación,
mesturar as metades ordenados,

126
00:06:01,800 --> 00:06:03,840
pero 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
Ben, resulta que estas dúas liñas
primeiro, a metade deixou tipo de elementos,

129
00:06:09,150 --> 00:06:13,970
e tipo certo de metade dos elementos,
son chamadas recursivas, por así dicir.

130
00:06:13,970 --> 00:06:16,120
>> A pesar de todo, neste
punto no tempo, eu teño

131
00:06:16,120 --> 00:06:18,950
un algoritmo coa que a
Ordenar unha morea de elementos?

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

133
00:06:19,450 --> 00:06:20,620
Está ben aquí.

134
00:06:20,620 --> 00:06:25,180
É aquí mesmo na pantalla, e
para que eu poida usar o mesmo conxunto de pasos

135
00:06:25,180 --> 00:06:28,500
para clasificar a metade esquerda,
como podo a metade dereita.

136
00:06:28,500 --> 00:06:30,420
E, de feito, unha vez máis, e outra vez.

137
00:06:30,420 --> 00:06:34,210
Entón, de algunha maneira ou doutra, e nós imos en breve
ver iso, a maxia de merge sort

138
00:06:34,210 --> 00:06:37,967
incorpórase en que moi definitiva
liña, a fusión das metades ordenados.

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

140
00:06:39,300 --> 00:06:41,050
Colle dúas metades, e ti,
dalgún xeito, fondo-las,

141
00:06:41,050 --> 00:06:43,260
e veremos que
concretamente en un momento.

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

143
00:06:45,080 --> 00:06:46,640
E imos ver exactamente o por que.

144
00:06:46,640 --> 00:06:50,912
Ben supoñer que estamos dando eses mesmos
oito elementos aquí na pantalla, un

145
00:06:50,912 --> 00:06:53,120
a través de oito, pero son
en orde aleatoria.

146
00:06:53,120 --> 00:06:55,320
E o obxectivo en cuestión é
para clasificar estes elementos.

147
00:06:55,320 --> 00:06:58,280
Ben, como podo ir sobre
facelo usando, de novo,

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

149
00:07:00,407 --> 00:07:02,740
E, de novo, incutir iso en
súa mente, só por un momento.

150
00:07:02,740 --> 00:07:05,270
O primeiro caso é moi
trivial, de ser inferior a 2,

151
00:07:05,270 --> 00:07:07,060
basta volver, non hai traballo por facer.

152
00:07:07,060 --> 00:07:09,290
Entón, realmente hai só tres
pasos para realmente ter en conta.

153
00:07:09,290 --> 00:07:11,081
Unha vez máis, e de novo, eu son
Vai querer ter

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

155
00:07:13,980 --> 00:07:15,890
e, a continuación, xa que a súa
dúas metades son clasificadas,

156
00:07:15,890 --> 00:07:18,710
Quero fundídelas
nunha lista ordenada.

157
00:07:18,710 --> 00:07:19,940
Polo tanto, manter isto presente.

158
00:07:19,940 --> 00:07:21,310
>> Entón aquí está a lista orixinal.

159
00:07:21,310 --> 00:07:23,510
Imos tratar isto como unha
array, coma nós comezamos a

160
00:07:23,510 --> 00:07:25,800
a semana dous, que é un
bloque contiguo de memoria.

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 imos agora aplicar merge sort.

163
00:07:30,700 --> 00:07:33,300
Entón, primeiro quero clasificar
a metade esquerda da lista,

164
00:07:33,300 --> 00:07:37,370
e imos, polo tanto,
concentrarse en 4, 8, 6, e 2.

165
00:07:37,370 --> 00:07:41,000
>> Agora, como eu vou sobre
ordenar unha lista de tamaño 4?

166
00:07:41,000 --> 00:07:45,990
Ben eu teño que considerar agora
selección esquerda da metade esquerda.

167
00:07:45,990 --> 00:07:47,720
Unha vez máis, imos retroceder por un momento.

168
00:07:47,720 --> 00:07:51,010
O pseudocódigo é iso,
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
Así, co primeiro caso non se aplica.

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

172
00:07:58,120 --> 00:08:01,930
entón eu ordenar a metade dereita, entón eu mesturar
as dúas metades, cada unha das ordenadas tamaño 4.

173
00:08:01,930 --> 00:08:02,470
Aceptar.

174
00:08:02,470 --> 00:08:07,480
>> Pero se acaba de me dicir, ordenar a
metade esquerda, que agora é de tamaño 4,

175
00:08:07,480 --> 00:08:09,350
como fago para clasificar a metade esquerda?

176
00:08:09,350 --> 00:08:11,430
Ben, se eu teño unha
entrada de catro elementos,

177
00:08:11,430 --> 00:08:14,590
I primeiro clasificar á esquerda
dous, entón os dous dereita,

178
00:08:14,590 --> 00:08:16,210
e entón eu fundín-las.

179
00:08:16,210 --> 00:08:18,700
Entón, de novo, pasa a ser un pouco
dunha mente dobra xogo aquí,

180
00:08:18,700 --> 00:08:21,450
porque, tipo, ten que
Teña en conta que onde está na historia,

181
00:08:21,450 --> 00:08:23,620
pero ao final do día,
dada calquera número de elementos,

182
00:08:23,620 --> 00:08:25,620
primeiro quere clasificar a
metade esquerda, a continuación, a metade dereita,

183
00:08:25,620 --> 00:08:26,661
logo fundín-las.

184
00:08:26,661 --> 00:08:28,630
Imos comezar a facer exactamente isto.

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

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

187
00:08:31,910 --> 00:08:33,720
¿Como clasificar catro elementos?

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

189
00:08:35,610 --> 00:08:37,720
Agora como fago para clasificar a metade esquerda?

190
00:08:37,720 --> 00:08:39,419
Ben, eu teño dado dous elementos.

191
00:08:39,419 --> 00:08:41,240
Entón, imos resolver estes dous elementos.

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

193
00:08:44,540 --> 00:08:46,170
Así que o primeiro caso non se aplica.

194
00:08:46,170 --> 00:08:49,010
>> Entón, eu agora teño que clasificar a esquerda
metade destes dous elementos.

195
00:08:49,010 --> 00:08:50,870
A metade esquerda, por suposto, está só a 4.

196
00:08:50,870 --> 00:08:54,020
Entón, como fago para clasificar a lista de elemento?

197
00:08:54,020 --> 00:08:57,960
Ben, agora, que se base especial
enriba, por así dicir, se aplica.

198
00:08:57,960 --> 00:09:01,470
1 sexa inferior a 2, eo meu
lista é realmente de tamaño 1.

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

200
00:09:02,747 --> 00:09:03,580
Eu non fago nada.

201
00:09:03,580 --> 00:09:06,770
E, de feito, mira o que eu teño
feito, catro xa están clasificados.

202
00:09:06,770 --> 00:09:09,220
Como eu xa estou
parcialmente exitoso aquí.

203
00:09:09,220 --> 00:09:11,750
>> Agora que parece unha especie de idiota
para reclamar, pero é verdade.

204
00:09:11,750 --> 00:09:13,700
4 é unha lista de tamaño 1.

205
00:09:13,700 --> 00:09:15,090
Xa está clasificado.

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

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

208
00:09:18,010 --> 00:09:22,310
Miña entrada é un elemento, 8
Do mesmo xeito, xa clasificados.

209
00:09:22,310 --> 00:09:25,170
Estúpido, tamén, pero, de novo,
este principio básico

210
00:09:25,170 --> 00:09:28,310
vai permitir-nos construír agora
enriba deste correctamente.

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

212
00:09:32,260 --> 00:09:35,330
Así, o terceiro e último paso, calquera
xa que está clasificando unha lista, recall,

213
00:09:35,330 --> 00:09:38,310
era fusionar as dúas metades,
á esquerda e á dereita.

214
00:09:38,310 --> 00:09:39,900
Entón, imos facer exactamente isto.

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

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

217
00:09:43,310 --> 00:09:44,100
>> Entón, imos facelo.

218
00:09:44,100 --> 00:09:46,410
Primeiro eu vou para reservar
algunha memoria adicional,

219
00:09:46,410 --> 00:09:48,680
que eu vou representar aquí,
como só unha matriz secundaria,

220
00:09:48,680 --> 00:09:49,660
que é grande abondo para caber iso.

221
00:09:49,660 --> 00:09:52,243
Pero pode imaxinar que se estende
rectángulo que toda a lonxitude,

222
00:09:52,243 --> 00:09:53,290
se necesitamos máis tarde.

223
00:09:53,290 --> 00:09:58,440
¿Como facer 4 e 8, e mesturar
estas dúas listas de tamaño 1 xuntos?

224
00:09:58,440 --> 00:10:00,270
Aquí, tamén, moi sinxelo.

225
00:10:00,270 --> 00:10:03,300
4 vén primeiro, despois vén 8.

226
00:10:03,300 --> 00:10:07,130
Porque se eu queira clasificar a
metade esquerda, a continuación, a metade dereita,

227
00:10:07,130 --> 00:10:09,900
e, a continuación, mesturar estas dúas metades
xuntos, na orde de clasificación,

228
00:10:09,900 --> 00:10:11,940
4 vén primeiro, despois vén 8.

229
00:10:11,940 --> 00:10:15,810
>> Entón, parece que estamos a facer avances, aínda
aínda que eu non teña feito calquera traballo real.

230
00:10:15,810 --> 00:10:17,800
Pero lembre-se onde estamos na historia.

231
00:10:17,800 --> 00:10:19,360
Nós orixinalmente 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ón nós ordenamos a metade esquerda
da metade esquerda, que era de 2.

234
00:10:24,450 --> 00:10:25,270
E aquí imos nós.

235
00:10:25,270 --> 00:10:26,920
Somos feitos con ese paso.

236
00:10:26,920 --> 00:10:29,930
>> Entón, se temos clasificados a
á esquerda metade 2, agora nós

237
00:10:29,930 --> 00:10:32,130
ten que clasificar a metade dereita de 2.

238
00:10:32,130 --> 00:10:35,710
Así, a metade dereita 2 está
estes dous valores aquí, 6 e 2.

239
00:10:35,710 --> 00:10:40,620
Entón, imos agora dar unha entrada de tamaño
2, e ordenar a metade esquerda e logo

240
00:10:40,620 --> 00:10:42,610
a metade dereita, e, a continuación,
fundín-las.

241
00:10:42,610 --> 00:10:45,722
Así como fago para clasificar a lista de tamaño
1, que contén só o número 6?

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

243
00:10:46,430 --> 00:10:48,680
Esa lista de tamaño 1 é ordenada.

244
00:10:48,680 --> 00:10:52,140
>> ¿Como clasificar outra lista de
tamaño 1, o así chamado metade dereita.

245
00:10:52,140 --> 00:10:54,690
Ben, tamén, xa está clasificado.

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

247
00:10:56,190 --> 00:11:00,160
Entón agora eu teño dúas metades, esquerda e
correcto, eu teño fundín-las.

248
00:11:00,160 --> 00:11:01,800
Deixe-me dar-me un pouco de espazo extra.

249
00:11:01,800 --> 00:11:05,580
E poñer-2 en alí,
a continuación, 6 de alí, así

250
00:11:05,580 --> 00:11:10,740
clasificando esa lista, esquerda e dereita,
e fundíndose lo xuntos, en última instancia.

251
00:11:10,740 --> 00:11:12,160
Entón, eu estou en algo mellor forma.

252
00:11:12,160 --> 00:11:16,250
Non son feito, porque claramente 4, 8, 2,
6 non é a ordenación final que quero.

253
00:11:16,250 --> 00:11:20,640
Pero agora teño dúas listas de tamaño 2, que
ambos teñen, respectivamente, foron clasificadas.

254
00:11:20,640 --> 00:11:24,580
Polo tanto, agora se retroceder na súa mente de
ollo, onde é que isto déixanos?

255
00:11:24,580 --> 00:11:28,520
Comecei con oito elementos, entón eu
tallou-lo para abaixo para a metade esquerda do 4,

256
00:11:28,520 --> 00:11:31,386
a continuación, a metade esquerda 2, e
a continuación, a metade dereita da 2,

257
00:11:31,386 --> 00:11:34,510
Eu rematar, polo tanto, a selección esquerda
metade de 2, ea metade dereita de 2,

258
00:11:34,510 --> 00:11:37,800
entón que é o terceiro e último paso aquí?

259
00:11:37,800 --> 00:11:41,290
Teño que fundir-se
dúas listas de tamaño 2.

260
00:11:41,290 --> 00:11:42,040
Entón, imos adiante.

261
00:11:42,040 --> 00:11:43,940
E na pantalla aquí, dar-
me algunha memoria adicional,

262
00:11:43,940 --> 00:11:47,170
aínda que tecnicamente, repare en que eu teño
ten unha morea de espazo en branco encima

263
00:11:47,170 --> 00:11:47,670
alí.

264
00:11:47,670 --> 00:11:50,044
Se eu queira ser especialmente
espazo eficiente sabio,

265
00:11:50,044 --> 00:11:52,960
Podería simplemente comezar a mover os elementos
e cara atrás, superior e inferior.

266
00:11:52,960 --> 00:11:55,460
Pero só para maior claridade visual,
Vou poñer-lo alí en baixo,

267
00:11:55,460 --> 00:11:56,800
para manter as cousas agradable e limpo.

268
00:11:56,800 --> 00:11:58,150
>> Entón eu teño dúas listas de tamaño 2.

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

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

271
00:12:01,500 --> 00:12:03,950
Imos mesturar os
xuntos na orde de clasificación.

272
00:12:03,950 --> 00:12:09,910
2, por suposto, ven en primeiro lugar,
a continuación, 4, 6, a continuación, a continuación, 8.

273
00:12:09,910 --> 00:12:12,560
E agora parece que estamos a recibir
nalgún lugar interesante.

274
00:12:12,560 --> 00:12:15,720
Agora eu teño a metade clasificadas da
lista, e coincidentemente, é

275
00:12:15,720 --> 00:12:18,650
Todos os números pares, pero iso
é, en realidade, só unha coincidencia.

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

277
00:12:22,220 --> 00:12:23,430
Nada está fóra de orde.

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

279
00:12:24,620 --> 00:12:26,650
>> Agora parece que teño
falado para sempre agora,

280
00:12:26,650 --> 00:12:29,850
Entón, o que segue a ser visto se iso
algoritmo é, en realidade, máis eficiente.

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

282
00:12:31,766 --> 00:12:34,060
Un ordenador, por suposto,
ía facelo así.

283
00:12:34,060 --> 00:12:34,840
Entón, ¿onde estamos?

284
00:12:34,840 --> 00:12:36,180
Comezamos con 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 parezo ser feito con iso.

287
00:12:39,290 --> 00:12:42,535
Polo tanto, agora o seguinte paso é
ordenar a metade dereita 4.

288
00:12:42,535 --> 00:12:44,410
E esta parte podemos ir
mediante un pouco máis

289
00:12:44,410 --> 00:12:47,140
rapidamente, aínda que é
Benvido a retroceder ou facer unha pausa, só

290
00:12:47,140 --> 00:12:49,910
creo que por el en
seu propio ritmo, pero o que

291
00:12:49,910 --> 00:12:53,290
que temos agora é unha oportunidade para
facer o mesmo algoritmo exacto en catro

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

293
00:12:54,380 --> 00:12:57,740
>> Entón imos adiante, e concentrarse en
a metade dereita, que estamos aquí.

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

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

296
00:13:04,560 --> 00:13:08,030
e como fago para clasificar a lista de tamaño
1 contén o número 1?

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

298
00:13:09,030 --> 00:13:11,830
Cómo fago o mesmo para unha lista
de tamaño 1 contendo só 7?

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

300
00:13:12,840 --> 00:13:16,790
Paso tres á metade, a continuación, esta
é para mesturar estes dous elementos

301
00:13:16,790 --> 00:13:20,889
nunha nova lista de tamaño 2, 1 e 7.

302
00:13:20,889 --> 00:13:23,180
Non parecen ter feito todo
que moito traballo interesante.

303
00:13:23,180 --> 00:13:24,346
Imos ver que pasa a continuación.

304
00:13:24,346 --> 00:13:29,210
Só ordenados a metade esquerda do
metade dereita da miña entrada orixinal.

305
00:13:29,210 --> 00:13:32,360
Agora imos clasificar a dereita
medio, que contén 3 e 5.

306
00:13:32,360 --> 00:13:35,740
Imos de novo ollar para a esquerda
metade, clasificado, metade dereita, clasificado,

307
00:13:35,740 --> 00:13:39,120
e mesturar os dous xuntos,
nalgún espazo adicional,

308
00:13:39,120 --> 00:13:41,670
3 vén primeiro, despois vén 5.

309
00:13:41,670 --> 00:13:46,190
E agora temos clasificados a
metade esquerda da metade dereita

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

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

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

313
00:13:52,480 --> 00:13:54,854
Ben, para mesturar estas dúas metades xuntas.

314
00:13:54,854 --> 00:13:57,020
Entón me deixe ter algún
espazo extra, pero, de novo, eu

315
00:13:57,020 --> 00:13:58,699
podería estar usando aquel espazo enriba de reposición.

316
00:13:58,699 --> 00:14:00,490
Pero nós estamos indo a mantê-
o simple visual.

317
00:14:00,490 --> 00:14:07,070
Deixe-me agora fúndense en un, e
a continuación, 3, 5 e, a continuación, e logo 7.

318
00:14:07,070 --> 00:14:10,740
Así, me deixando agora coa
metade dereita do problema orixinal

319
00:14:10,740 --> 00:14:12,840
Isto é perfectamente ordenadas.

320
00:14:12,840 --> 00:14:13,662
>> Entón o que queda?

321
00:14:13,662 --> 00:14:16,120
Eu sinto que eu sigo dicindo a
mesmas cousas de novo, e de novo,

322
00:14:16,120 --> 00:14:18,700
pero iso é un reflexo do
feito de que estamos a usar recursão.

323
00:14:18,700 --> 00:14:21,050
O proceso de utilización dun
algoritmo de novo, e de novo,

324
00:14:21,050 --> 00:14:23,940
en subconxuntos máis pequenos de
o problema orixinal.

325
00:14:23,940 --> 00:14:27,580
Entón, agora teño unha esquerda clasificadas
metade do problema orixinal.

326
00:14:27,580 --> 00:14:30,847
Eu teño unha media ordenada dereita
do problema orixinal.

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

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

329
00:14:33,590 --> 00:14:34,480
Entón, imos facelo.

330
00:14:34,480 --> 00:14:36,420
Imos reservar algún adicional
memoria, pero o meu deus, nós

331
00:14:36,420 --> 00:14:37,503
podería poñer-lo en calquera lugar agora.

332
00:14:37,503 --> 00:14:40,356
Temos moito espazo dispoñible
para nós, pero imos mantelo simple.

333
00:14:40,356 --> 00:14:42,730
En vez de ir cara atrás e
adiante coa nosa memoria orixinal,

334
00:14:42,730 --> 00:14:44,480
imos facelo
visualmente aquí abaixo,

335
00:14:44,480 --> 00:14:47,240
para rematar a fusión
metade esquerda e metade dereita.

336
00:14:47,240 --> 00:14:49,279
>> Así, a través da fusión, o que eu teño que facer?

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

338
00:14:50,820 --> 00:14:53,230
Entón, ollando para o lado esquerdo,
Vexo o primeiro número é 2.

339
00:14:53,230 --> 00:14:55,230
Eu ollo para a metade dereita,
Vexo o primeiro número

340
00:14:55,230 --> 00:14:58,290
é 1, entón obviamente que
número que quero arrincar,

341
00:14:58,290 --> 00:15:00,430
e poñer en primeiro lugar na miña lista final?

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

343
00:15:01,449 --> 00:15:02,990
Agora quero facer a mesma pregunta.

344
00:15:02,990 --> 00:15:05,040
Na metade esquerda, eu teño
aínda ten o número 2.

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

346
00:15:07,490 --> 00:15:08,930
Cal deles quero escoller?

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

348
00:15:11,760 --> 00:15:13,620
4 están á esquerda, á dereita 3.

349
00:15:13,620 --> 00:15:15,020
Imos, por suposto, escoller tres.

350
00:15:15,020 --> 00:15:18,020
Agora, os candidatos son 4 en
á esquerda, 5, á dereita.

351
00:15:18,020 --> 00:15:19,460
Nós, por suposto, escoller catro.

352
00:15:19,460 --> 00:15:21,240
6, á esquerda, á dereita 5.

353
00:15:21,240 --> 00:15:22,730
Nós, por suposto, escoller 5.

354
00:15:22,730 --> 00:15:25,020
6 á esquerda, á dereita 7.

355
00:15:25,020 --> 00:15:29,320
Nós escoller seis, e entón nós
escoller 7, e, a continuación, nós escoller 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Así, un gran número de palabras máis tarde,
resolver esta lista de oito elementos

358
00:15:34,370 --> 00:15:38,450
nunha lista de un a oito,
que está aumentando cada paso,

359
00:15:38,450 --> 00:15:40,850
pero canto tempo fixo
lévanos a facelo.

360
00:15:40,850 --> 00:15:43,190
Ben, eu teño deliberadamente
cousas establecidas pictorially

361
00:15:43,190 --> 00:15:46,330
aquí, para que poidamos tipo de
ver ou apreciar a división

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

363
00:15:49,060 --> 00:15:52,830
>> En realidade, se ollar cara atrás na esteira,
Eu deixei todas esas liñas pontilhadas

364
00:15:52,830 --> 00:15:55,660
en soportes do lugar, pode,
tipo de, vexa, en orde inversa,

365
00:15:55,660 --> 00:15:58,800
se tipo de ollar cara atrás en
historia agora, meu lista orixinal

366
00:15:58,800 --> 00:16:00,250
é, por suposto, de tamaño 8.

367
00:16:00,250 --> 00:16:03,480
E, a continuación, anteriormente, eu estaba
lidando con dúas listas de tamaño 4,

368
00:16:03,480 --> 00:16:08,400
e, a continuación, catro listas de tamaño 2,
e, a continuación, oito listas de tamaño 1.

369
00:16:08,400 --> 00:16:10,151
>> Entón, o que fai iso,
tipo de, lembra?

370
00:16:10,151 --> 00:16:11,858
Ben, en realidade, calquera de
os algoritmos Nós

371
00:16:11,858 --> 00:16:14,430
mirou, ata agora, onde nós
dividir e dividir, e se dividen,

372
00:16:14,430 --> 00:16:19,500
sigo a ter as cousas de novo, e
de novo, resulta nesa idea xeral.

373
00:16:19,500 --> 00:16:23,100
E entón hai algo
logarítmica suceder aquí.

374
00:16:23,100 --> 00:16:26,790
E non é moi de rexistro n, pero
hai un compoñente logarítmica

375
00:16:26,790 --> 00:16:28,280
co que acaba de facer.

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

377
00:16:31,570 --> 00:16:34,481
Entón rexistro n, de novo foi
un gran tempo de execución,

378
00:16:34,481 --> 00:16:36,980
cando fixemos algo
busca binaria, como agora chamalo,

379
00:16:36,980 --> 00:16:40,090
a estratexia de dividir para conquistar
vía que atopamos Mike Smith.

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

381
00:16:41,020 --> 00:16:43,640
Isto é log base dous n, mesmo
aínda que na maioría das clases de matemáticas,

382
00:16:43,640 --> 00:16:45,770
10 é xeralmente a base que asume.

383
00:16:45,770 --> 00:16:48,940
Pero científicos da computación case sempre
pensar e falar en termos de base 2,

384
00:16:48,940 --> 00:16:52,569
así que nós xeralmente só dicir rexistro de
N, no canto de rexistro de base 2 de N,

385
00:16:52,569 --> 00:16:55,110
pero son exactamente un eo
mentres que no mundo do ordenador

386
00:16:55,110 --> 00:16:57,234
ciencia, e como un aparte,
hai un factor constante

387
00:16:57,234 --> 00:17:01,070
diferenza entre os dous, de xeito que é
Moot de calquera xeito, por razóns máis formais.

388
00:17:01,070 --> 00:17:04,520
>> Pero, por agora, o que nos importa
é sobre este exemplo.

389
00:17:04,520 --> 00:17:08,520
Entón non imos probar por exemplo, pero en
menos usar un exemplo dos números

390
00:17:08,520 --> 00:17:10,730
na man como unha comprobación de sanidade, se quere.

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

392
00:17:14,510 --> 00:17:18,526
Eu tiña números de n orixinais, ou 8
do número orixinal especificamente.

393
00:17:18,526 --> 00:17:20,359
Agora que foi un pouco
agora, pero estou moi

394
00:17:20,359 --> 00:17:25,300
Asegúrese de que a base de rexistro 2
do valor 8 é 3,

395
00:17:25,300 --> 00:17:29,630
e, de feito, o que é bo do que é
3 que é exactamente o número de veces

396
00:17:29,630 --> 00:17:33,320
que pode dividir unha lista
lonxitude de 8, e de novo,

397
00:17:33,320 --> 00:17:36,160
e outra vez, ata que é deixar
con listas de só un tamaño.

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

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

400
00:17:40,790 --> 00:17:43,470
reflexivo que exactamente
imaxe, tivemos só un momento atrás.

401
00:17:43,470 --> 00:17:47,160
Entón, un pouco de cordura comprobar de onde
o logaritmo é realmente implicados.

402
00:17:47,160 --> 00:17:50,180
>> Entón, agora, o que máis está implicado aquí? n.

403
00:17:50,180 --> 00:17:53,440
Entón, teña en conta que cada
xa que dividir a lista,

404
00:17:53,440 --> 00:17:58,260
aínda que na orde inversa da historia
aquí, eu estaba facendo as cousas n.

405
00:17:58,260 --> 00:18:02,320
Isto esixe que a fusión etapa
Eu toco a cada un dos números,

406
00:18:02,320 --> 00:18:05,060
a fin de deslize-
a súa situación axeitada.

407
00:18:05,060 --> 00:18:10,760
Así, aínda que a altura desta
diagrama é de tamaño de rexistro n de n ou 3,

408
00:18:10,760 --> 00:18:13,860
En concreto, noutras palabras,
Eu fixen tres divisións aquí.

409
00:18:13,860 --> 00:18:18,800
Canto traballo que fixen na horizontal
ao longo desta carta de cada vez?

410
00:18:18,800 --> 00:18:21,110
>> Ben, eu fixen n pasos de
traballar, porque se eu teño

411
00:18:21,110 --> 00:18:24,080
ten catro elementos e catro elementos,
e eu teño fundín-las.

412
00:18:24,080 --> 00:18:26,040
Necesito pasar por
estes catro e estes catro,

413
00:18:26,040 --> 00:18:28,123
finalmente, para fundín-los
de volta en oito elementos.

414
00:18:28,123 --> 00:18:32,182
Por outra banda eu teño oito dedos
aquí, o que eu non fago, e oito

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Se eu teño
ten catro dedos aquí,

416
00:18:34,390 --> 00:18:37,380
que fago, catro dedos
aquí, o que fago,

417
00:18:37,380 --> 00:18:40,590
entón iso é o mesmo
exemplo como antes, se eu fai

418
00:18:40,590 --> 00:18:44,010
ten oito dedos aínda en
total, o que podo, tipo, facer.

419
00:18:44,010 --> 00:18:47,950
Podo exactamente facer aquí,
entón podo certamente

420
00:18:47,950 --> 00:18:50,370
mesturar todas estas listas
de tamaño 1, en conxunto.

421
00:18:50,370 --> 00:18:54,050
Pero eu certamente ten que mirar
en cada elemento dunha vez.

422
00:18:54,050 --> 00:18:59,640
Entón, a altura deste proceso é o rexistro N,
o ancho do presente proceso, por así dicir,

423
00:18:59,640 --> 00:19:02,490
é n, entón o que parecemos
ter, en última instancia, é

424
00:19:02,490 --> 00:19:06,470
unha duración de tamaño n veces rexistro n.

425
00:19:06,470 --> 00:19:08,977
>> Noutras palabras, dividimos
lista, log n veces o,

426
00:19:08,977 --> 00:19:11,810
pero cada vez que fixemos iso, tivemos
para tocar a cada un dos elementos

427
00:19:11,810 --> 00:19:13,560
a fin de fundín-los
todos xuntos, o que

428
00:19:13,560 --> 00:19:18,120
n para paso foi, polo que temos n veces log n,
ou como un científico da computación diría,

429
00:19:18,120 --> 00:19:20,380
asintótica, que
sería a gran palabra

430
00:19:20,380 --> 00:19:22,810
para describir o superior
vinculado nun tempo de execución,

431
00:19:22,810 --> 00:19:28,010
estamos executando nun grande
de rexistro n tempo, por así dicir.

432
00:19:28,010 --> 00:19:31,510
>> Agora, iso é significativo, porque
recordar que os tempos de execución foron

433
00:19:31,510 --> 00:19:34,120
con bubble sort, e selección
tipo e ordenación por inserción,

434
00:19:34,120 --> 00:19:38,200
e mesmo algúns outros que existen,
n ao cadrado era onde estabamos.

435
00:19:38,200 --> 00:19:39,990
E pode, tipo, ver este aquí.

436
00:19:39,990 --> 00:19:45,720
Se n ao cadrado é, obviamente, n veces
n, pero aquí temos n veces log n,

437
00:19:45,720 --> 00:19:48,770
e xa sabemos desde a semana
cero, que log n, a logarítmica,

438
00:19:48,770 --> 00:19:50,550
é mellor que algo lineal.

439
00:19:50,550 --> 00:19:52,930
Ao final, lembrar a imaxe
co vermello eo amarelo

440
00:19:52,930 --> 00:19:56,500
e as liñas verdes que sacou, a
logarítmica liña verde era moito menor.

441
00:19:56,500 --> 00:20:00,920
E, polo tanto, moito mellor e máis rápido
que as liñas amarelas e vermellas en liña recta,

442
00:20:00,920 --> 00:20:05,900
n veces log n é, de feito, mellor
que n veces n, ou n ao cadrado.

443
00:20:05,900 --> 00:20:09,110
>> Entón, parece que temos
identificou un algoritmo merge

444
00:20:09,110 --> 00:20:11,870
tipo que é executado en moi
tempo máis rápido, e de feito,

445
00:20:11,870 --> 00:20:16,560
é por iso que, a principios desta semana, cando
vimos que disputa entre burbulla

446
00:20:16,560 --> 00:20:20,750
tipo, especie de selección, e mesturar
sort, merge sort realmente, realmente gañou.

447
00:20:20,750 --> 00:20:23,660
E, de feito, non mesmo esperar
para bubble sort e selección especie

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

449
00:20:24,790 --> 00:20:27,410
>> Agora imos dar outra pasaxe
para iso, desde un pouco máis

450
00:20:27,410 --> 00:20:31,030
perspectiva formal, só en
caso, iso resoa mellor

451
00:20:31,030 --> 00:20:33,380
que maior que o nivel de discusión.

452
00:20:33,380 --> 00:20:34,880
Entón aquí está o algoritmo de novo.

453
00:20:34,880 --> 00:20:36,770
Imos preguntar:
o que o tempo de execución

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

455
00:20:39,287 --> 00:20:41,620
Imos división lo en primeiro
caso e no segundo caso.

456
00:20:41,620 --> 00:20:46,280
A SE ea outra persoa no caso IF,
Se n é inferior a 2, só volver.

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 dous pasos,
Se n é inferior a 2, a continuación, volver.

459
00:20:50,970 --> 00:20:54,580
Pero, como dixemos o luns,
constante de tempo, ou grande de 1,

460
00:20:54,580 --> 00:20:57,130
pode ser dous, tres pasos
pasos, ata 1.000 pasos.

461
00:20:57,130 --> 00:20:59,870
O importante é que é
un número constante de pasos.

462
00:20:59,870 --> 00:21:03,240
Así, o amarelo destaque pseudocódigo
aquí é executado en, imos chamalo,

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

464
00:21:04,490 --> 00:21:06,780
Entón, máis formalmente, e
imos a-- este

465
00:21:06,780 --> 00:21:09,910
será a extensión en que
formalizar este dereito agora-- T n,

466
00:21:09,910 --> 00:21:15,030
o tempo de execución dun problema
que leva n calquera cousa como entrada,

467
00:21:15,030 --> 00:21:19,150
igualan o o dun,
Se n é menor que 2.

468
00:21:19,150 --> 00:21:20,640
Polo tanto, é condicionada a iso.

469
00:21:20,640 --> 00:21:24,150
Entón, para ser claro, se n é inferior a
2, temos unha lista moi curta, entón

470
00:21:24,150 --> 00:21:29,151
o tempo de execución, t n, no que n é
0 ou 1, neste caso moi específico,

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

472
00:21:30,650 --> 00:21:32,691
Vai levar un
paso, dous pasos, que sexa.

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

474
00:21:33,950 --> 00:21:38,840
>> Así, a parte suculenta certamente debe estar en
no outro caso no pseudocódigo.

475
00:21:38,840 --> 00:21:40,220
O caso máis.

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
Canto tempo dura cada unha destas etapas tomar?

478
00:21:46,800 --> 00:21:49,780
Ben, a carreira
tempo para resolver n elementos

479
00:21:49,780 --> 00:21:53,010
é, imos chamalo moi
xenericamente, T de N,

480
00:21:53,010 --> 00:21:55,500
a continuación, a selección esquerda
metade dos elementos

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

482
00:21:59,720 --> 00:22:03,000
e do mesmo xeito clasificando a metade dereita
de elementos é, tipo, como dicilo,

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

484
00:22:06,974 --> 00:22:08,890
Ben, se eu teño algún
número de elementos aquí,

485
00:22:08,890 --> 00:22:11,230
como catro, e algún número
de elementos aquí, como catro,

486
00:22:11,230 --> 00:22:14,650
e eu teño que fundir cada un destes catro
en, e cada un destes catro, un

487
00:22:14,650 --> 00:22:17,160
despois o outro, de xeito que
en definitiva, eu teño oito elementos.

488
00:22:17,160 --> 00:22:20,230
Se sente como que é grande de n pasos?

489
00:22:20,230 --> 00:22:23,500
Se eu teño n dedos e cada un
ten que ser incorporado lugar,

490
00:22:23,500 --> 00:22:25,270
que é como máis n pasos.

491
00:22:25,270 --> 00:22:27,360
>> Entón, en realidade, como unha fórmula,
podemos expresar isto,

492
00:22:27,360 --> 00:22:29,960
aínda que un pouco assustadoramente en primeiro
vista, pero é algo

493
00:22:29,960 --> 00:22:31,600
que capta exactamente esa lóxica.

494
00:22:31,600 --> 00:22:35,710
O tempo de execución, T n, n IF
é maior que ou igual a 2.

495
00:22:35,710 --> 00:22:42,500
Neste caso, o caso MÁIS, é T n
dividido por dous, ademais de T n dividido por 2,

496
00:22:42,500 --> 00:22:45,320
máis grande de n, algúns
lineal número de pasos,

497
00:22:45,320 --> 00:22:51,630
quizais precisamente n, quizais 2 veces
n, pero é máis ou menos, a orde de n.

498
00:22:51,630 --> 00:22:54,060
De xeito que, tamén, é como podemos
expresar isto como unha fórmula.

499
00:22:54,060 --> 00:22:56,809
Agora non sabería que a menos
gravou na súa mente,

500
00:22:56,809 --> 00:22:58,710
ou buscalo no
traseira dun libro, que

501
00:22:58,710 --> 00:23:00,501
podería ter un pouco
Cabula ao final,

502
00:23:00,501 --> 00:23:03,940
pero que é, de feito, vai
ofrécenos un grande n log n,

503
00:23:03,940 --> 00:23:06,620
porque a recorrencia que
está a ver aquí na pantalla,

504
00:23:06,620 --> 00:23:09,550
se realmente fixo iso para fóra, con
un número infinito de exemplos,

505
00:23:09,550 --> 00:23:13,000
ou fixo iso como unha fórmula, faría
ver que esta, porque esta fórmula

506
00:23:13,000 --> 00:23:17,100
en si é recursivo, con t de
n sobre algo á dereita,

507
00:23:17,100 --> 00:23:21,680
e t de N ao longo do lado esquerdo, pode
de feito, ser expresado, en definitiva,

508
00:23:21,680 --> 00:23:24,339
tan grande para ir de rexistro n n.

509
00:23:24,339 --> 00:23:26,130
Se non está convencido, iso é
ben por agora, só

510
00:23:26,130 --> 00:23:28,960
asumir a fe, que é, de feito,
o que leva a que a recorrencia,

511
00:23:28,960 --> 00:23:31,780
pero este é só un pouco máis dun
visión matemática para ollar

512
00:23:31,780 --> 00:23:36,520
o tempo de execución de merge sort
con base só na súa pseudocódigo.

513
00:23:36,520 --> 00:23:39,030
>> Agora imos dar un pouco de
respiradoiros de todo isto,

514
00:23:39,030 --> 00:23:41,710
e dar un ollo a un
seguro ex senador, que

515
00:23:41,710 --> 00:23:44,260
pode parecer un pouco familiarizado,
que sentou-se con Eric de Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, hai algún tempo, para unha entrevista
no escenario, diante dun grupo enteiro

517
00:23:48,410 --> 00:23:53,710
de persoas, falando en definitiva, sobre
un tema que é moi agora familiar.

518
00:23:53,710 --> 00:23:54,575
Imos dar un ollo.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Agora o senador,
está aquí en Google,

521
00:24:03,890 --> 00:24:09,490
e eu gusto de pensar no
Presidencia como unha entrevista de emprego.

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

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

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: E vostede é
fará [inaudível] agora.

525
00:24:13,940 --> 00:24:15,523
Tamén é difícil conseguir un emprego en Google.

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

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Temos preguntas,
e pedimos as nosas preguntas 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: Aceptar.

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

531
00:24:27,005 --> 00:24:28,130
Vostedes pensan que estou a xogar?

532
00:24:28,130 --> 00:24:30,590
Está ben aquí.

533
00:24:30,590 --> 00:24:33,490
Cal é o xeito máis eficaz de
clasificar un millón de 32 bits enteiros?

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 veces,
quizais eu sinto moito, maybe--

537
00:24:41,020 --> 00:24:42,750
PRESIDENTE OBAMA: Non, non,
non, non, non, eu penso--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Isto non é ele--

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

540
00:24:45,430 --> 00:24:46,875
tipo sería o camiño mal a continuación.

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

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Imos alí.

543
00:24:50,535 --> 00:24:52,200
Quen lle dixo iso?

544
00:24:52,200 --> 00:24:54,020
Aceptar.

545
00:24:54,020 --> 00:24:55,590
Eu non fixen a ciencia da computación on--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDENTE OBAMA: Temos
temos os nosos espías dentro.

547
00:24:58,986 --> 00:24:59,860
PROFESOR: Todo ben.

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

549
00:25:03,370 --> 00:25:06,520
na análise asintótica
do mesmo, e voltar para algúns tópicos

550
00:25:06,520 --> 00:25:09,940
desde a semana cero e un, e de inicio
para eliminar algunhas rodinhas,

551
00:25:09,940 --> 00:25:10,450
se quere.

552
00:25:10,450 --> 00:25:13,241
Para que realmente comprender
en definitiva, a partir de cero, o que é

553
00:25:13,241 --> 00:25:16,805
pasando baixo o capó, cando
escribir, compilar e executar programas.

554
00:25:16,805 --> 00:25:19,680
Teña en conta que, en particular, que este era
o primeiro programa C nós miramos,

555
00:25:19,680 --> 00:25:22,840
un programa canónica, simple
das sortes, en concepto falando,

556
00:25:22,840 --> 00:25:24,620
en que, imprime, Ola Mundo.

557
00:25:24,620 --> 00:25:27,610
E lembro que eu dixen, o proceso
que o código fonte atravesa

558
00:25:27,610 --> 00:25:28,430
é exactamente iso.

559
00:25:28,430 --> 00:25:31,180
Colle o seu código fonte, pasar
Lo través dun compilador, como Clang,

560
00:25:31,180 --> 00:25:34,650
e sae código obxecto, que
pode parecer como este, ceros e uns

561
00:25:34,650 --> 00:25:37,880
que a CPU do ordenador central
unidade de procesamento ou cerebro,

562
00:25:37,880 --> 00:25:39,760
en definitiva, entende.

563
00:25:39,760 --> 00:25:42,460
>> Acontece que isto é unha
pouco de unha simplificación,

564
00:25:42,460 --> 00:25:44,480
que estamos agora nun
posición de provocar unha separación

565
00:25:44,480 --> 00:25:46,720
para entender o que está realmente foi
pasando baixo o capó

566
00:25:46,720 --> 00:25:48,600
cada vez que executa
Tinido, ou, máis xeralmente,

567
00:25:48,600 --> 00:25:53,040
cada vez que fai un programa,
Fai uso e CF 50 IDE.

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

569
00:25:56,760 --> 00:25:58,684
cando compilar seu programa.

570
00:25:58,684 --> 00:26:00,600
Noutras palabras, cando
levar o seu código fonte

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

572
00:26:04,390 --> 00:26:06,370
é algo coñecido como código de montaxe.

573
00:26:06,370 --> 00:26:08,990
E, de feito, parece exactamente como este.

574
00:26:08,990 --> 00:26:11,170
>> Corre un comando no
liña de comandos anterior.

575
00:26:11,170 --> 00:26:16,260
Hello.c Clang de capital trazo s,
e iso creou un ficheiro

576
00:26:16,260 --> 00:26:19,490
para min chamados hello.s,
no interior dos cales foron exactamente

577
00:26:19,490 --> 00:26:22,290
estes contidos, e un pouco máis
arriba e un pouco máis abaixo,

578
00:26:22,290 --> 00:26:25,080
pero eu coloque o juiciest
información aquí na pantalla.

579
00:26:25,080 --> 00:26:29,190
E se ollar de preto, podes ver
polo menos algunhas palabras clave 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 abaixo no medio.

582
00:26:35,140 --> 00:26:38,670
E tamén temos Ola mundo
barra invertida n entre comiñas continuación.

583
00:26:38,670 --> 00:26:42,450
>> E todo o demais aquí
é instrucións de nivel moi 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
Instrucións da CPU que se moven de memoria
arredor, que secuencias de carga de memoria,

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

587
00:26:52,750 --> 00:26:56,780
Agora o que pasa aínda despois
este código assembly xérase?

588
00:26:56,780 --> 00:26:59,964
En última instancia, fai, de feito,
aínda xerar código obxecto.

589
00:26:59,964 --> 00:27:02,630
Pero os pasos que teñen realmente
vén acontecendo debaixo do capó

590
00:27:02,630 --> 00:27:04,180
mirar un pouco máis como este.

591
00:27:04,180 --> 00:27:08,390
O código fonte tórnase o código de montaxe,
que entón se fai código obxecto,

592
00:27:08,390 --> 00:27:11,930
e as palabras clave aquí é que,
cando compilar o código fonte,

593
00:27:11,930 --> 00:27:16,300
vén para fóra do código de montaxe, e, a continuación,
cando montar o código da montaxe,

594
00:27:16,300 --> 00:27:17,800
fóra vén código obxecto.

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

596
00:27:20,360 --> 00:27:23,151
e fai todas estas etapas
xuntos, e fai non necesariamente

597
00:27:23,151 --> 00:27:25,360
saída de calquera intermediario
arquivos que vostede mesmo pode ver.

598
00:27:25,360 --> 00:27:28,400
El só compila as cousas,
que é o termo xeral que

599
00:27:28,400 --> 00:27:30,000
describe todo este proceso.

600
00:27:30,000 --> 00:27:32,000
Pero se o quere
para ser determinado, non hai

601
00:27:32,000 --> 00:27:34,330
moito máis a suceder alí tamén.

602
00:27:34,330 --> 00:27:38,860
>> Pero imos considerar agora que mesmo
este programa super sinxelo, hello.c,

603
00:27:38,860 --> 00:27:40,540
chamado dunha función.

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

605
00:27:41,870 --> 00:27:46,900
Pero eu non quería escribir printf, de feito,
que vén con c, por así dicir.

606
00:27:46,900 --> 00:27:51,139
É un recall función que é
declarou io.h estándar, que

607
00:27:51,139 --> 00:27:53,180
é un ficheiro de cabeceira, que
é un tema que imos realmente

608
00:27:53,180 --> 00:27:55,780
mergullo máis fondo antes de tempo.

609
00:27:55,780 --> 00:27:58,000
Pero un ficheiro de cabeceira é
tipicamente acompañada

610
00:27:58,000 --> 00:28:02,920
por un ficheiro de código, arquivo de código fonte, así
moi parecido existe io.h. estándar

611
00:28:02,920 --> 00:28:05,930
>> Hai algún tempo, alguén,
ou de alguén, tamén escribiu

612
00:28:05,930 --> 00:28:11,040
un arquivo chamado io.c estándar, en
que a configuración efectivas,

613
00:28:11,040 --> 00:28:15,220
ou implementacións de printf,
e acios de outras funcións,

614
00:28:15,220 --> 00:28:16,870
son realmente escrito.

615
00:28:16,870 --> 00:28:22,140
Así, dado que, se considerar ter
aquí á esquerda, ola.c, que cando

616
00:28:22,140 --> 00:28:26,250
compilado, dános hello.s, aínda que
Clang non se incomoda de aforro nun lugar

617
00:28:26,250 --> 00:28:31,360
podemos velo, e que o código de montaxe
fica montada hello.o, que

618
00:28:31,360 --> 00:28:34,630
é, en realidade, o nome predeterminado
dado sempre que compilar fonte

619
00:28:34,630 --> 00:28:39,350
código en código obxecto, pero non son
completamente listo para executa-lo aínda,

620
00:28:39,350 --> 00:28:41,460
porque un paso
ten que pasar, e ten

621
00:28:41,460 --> 00:28:44,440
vén acontecendo nos últimos
semanas, quizais sen o seu coñecemento.

622
00:28:44,440 --> 00:28:47,290
>> Especialmente en algún lugar
CS50 en IDE, e este,

623
00:28:47,290 --> 00:28:49,870
tamén, vai ser un pouco de un
simplificación excesiva por un momento,

624
00:28:49,870 --> 00:28:54,670
non é, ou foi enriba dun tempo,
un arquivo chamado io.c estándar,

625
00:28:54,670 --> 00:28:58,440
que alguén compilados
io.s estándar ou equivalente,

626
00:28:58,440 --> 00:29:02,010
alguén que, a continuación, montar
en io.o estándar,

627
00:29:02,010 --> 00:29:04,600
ou se ve nun
arquivo lixeiramente diferente

628
00:29:04,600 --> 00:29:07,220
formato que pode ter un diferente
extensión de arquivo completo,

629
00:29:07,220 --> 00:29:11,720
pero, en teoría e conceptualmente, exactamente
estes pasos tiña que ocorrer de algunha maneira.

630
00:29:11,720 --> 00:29:14,060
O que significa dicir, que agora
cando estou escribindo un programa,

631
00:29:14,060 --> 00:29:17,870
hello.c, que só di: Ola mundo,
e eu estou usando o código de outra persoa

632
00:29:17,870 --> 00:29:22,480
como printf, que foi unha vez enriba dun
tempo, nun ficheiro chamado io.c estándar,

633
00:29:22,480 --> 00:29:26,390
a continuación, de algunha maneira eu teño que tomar a miña
código obxecto, meus ceros e uns,

634
00:29:26,390 --> 00:29:29,260
e obxecto da persoa
código, ou ceros e uns,

635
00:29:29,260 --> 00:29:34,970
e dalgunha forma obrigar-los xuntos
un arquivo final, chamado Ola, que

636
00:29:34,970 --> 00:29:38,070
ten todos os ceros e
os da miña función principal,

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

638
00:29:40,830 --> 00:29:44,900
>> E, de feito, este último proceso é
chamada, conectar o seu código obxecto.

639
00:29:44,900 --> 00:29:47,490
A saída dos cales
é un ficheiro executábel.

640
00:29:47,490 --> 00:29:49,780
Entón, na xustiza, na
final do día, nada

641
00:29:49,780 --> 00:29:52,660
cambiou desde unha semana, cando
primeiro comezou a compilar programas.

642
00:29:52,660 --> 00:29:55,200
Efectivamente, todo isto foi
pasando baixo o capó,

643
00:29:55,200 --> 00:29:57,241
pero agora estamos nunha posición
onde podemos realmente

644
00:29:57,241 --> 00:29:58,794
desmembrar esas varias etapas.

645
00:29:58,794 --> 00:30:00,710
E, de feito, a finais
do día, aínda somos

646
00:30:00,710 --> 00:30:04,480
á esquerda con ceros e uns, que
é realmente unha boa segue agora

647
00:30:04,480 --> 00:30:08,620
a outra capacidade de C, que
nós non tivemos a alavancar máis probable

648
00:30:08,620 --> 00:30:11,250
ata a data, coñecida como operadores bit a bit.

649
00:30:11,250 --> 00:30:15,220
Noutras palabras, ata o momento, en calquera momento temos
tratadas con datos variables en C ou C,

650
00:30:15,220 --> 00:30:17,660
tivemos cousas como
caracteres e Carrozas e ins

651
00:30:17,660 --> 00:30:21,990
e ansia e dobres e similares, pero
todos estes son, polo menos, oito bits.

652
00:30:21,990 --> 00:30:25,550
Temos aínda non foi capaz de
manipular bits individuais,

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

654
00:30:28,970 --> 00:30:32,640
Agora parece que en C, que
pode ter acceso a bits individuais,

655
00:30:32,640 --> 00:30:35,530
se sabe a sintaxe,
co cal se chegar a eles.

656
00:30:35,530 --> 00:30:38,010
>> Entón, imos dar un ollo
en operadores bit a bit.

657
00:30:38,010 --> 00:30:41,700
Entón, retratado aquí están algúns símbolos que
temos, tipo de, máis ou menos, visto antes.

658
00:30:41,700 --> 00:30:45,580
Eu vexo un e comercial, vertical
bar, e algúns outros tamén,

659
00:30:45,580 --> 00:30:49,430
e recordar que ampersand ampersand
é algo que vimos antes.

660
00:30:49,430 --> 00:30:54,060
O operador lóxico AND, onde ten
dous deles en conxunto, ou o OU lóxico

661
00:30:54,060 --> 00:30:56,300
operador, onde
ten dúas barras verticais.

662
00:30:56,300 --> 00:31:00,550
Operadores bit a bit, o que nós imos
vexa operar en anacos individualmente,

663
00:31:00,550 --> 00:31:03,810
non necesitará empregar un único e comercial, un
única barra vertical, o símbolo de acento circunflexo

664
00:31:03,810 --> 00:31:06,620
vén a continuación, a pequena
til, e despois á esquerda

665
00:31:06,620 --> 00:31:08,990
paréntese esquerdo soporte, ou
soporte dereito paréntese dereito.

666
00:31:08,990 --> 00:31:10,770
Cada un deles teñen significados diferentes.

667
00:31:10,770 --> 00:31:11,950
>> De feito, imos dar un ollo.

668
00:31:11,950 --> 00:31:16,560
Imos vella escola hoxe, e uso
unha pantalla táctil de outrora,

669
00:31:16,560 --> 00:31:18,002
coñecido como un cadro branco.

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

671
00:31:19,710 --> 00:31:27,360
para expresar algúns símbolos moi sinxelo,
ou mellor, algúns fórmulas moi sinxelo,

672
00:31:27,360 --> 00:31:29,560
que, a continuación, en definitiva, podemos
alavancagem, a fin

673
00:31:29,560 --> 00:31:33,230
para acceder individuo
bits dentro dun programa C.

674
00:31:33,230 --> 00:31:34,480
Noutras palabras, imos facelo.

675
00:31:34,480 --> 00:31:37,080
Imos primeiro falar para un
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
Noutras palabras, esta é
un operador que permite

678
00:31:42,130 --> 00:31:45,930
me para ter unha variable á esquerda
normalmente, e unha variable da man dereita,

679
00:31:45,930 --> 00:31:50,640
ou un valor individual, que se nos Correo
xuntos, me dá un resultado final.

680
00:31:50,640 --> 00:31:51,560
Entón o que quero dicir?

681
00:31:51,560 --> 00:31:54,840
Se nun programa, ten unha variable
que almacena un deses valores,

682
00:31:54,840 --> 00:31:58,000
ou imos mantelo simple, e só
escriba ceros e uns individualmente,

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

684
00:32:00,940 --> 00:32:06,400
0 0 comercial vai igual a 0.

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

686
00:32:07,210 --> 00:32:09,291
>> É moi semellante ao
As expresións booleanas,

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

688
00:32:10,540 --> 00:32:15,800
Se pensas que despois de todo, o 0 é
false, 0 é falso, falso e falso

689
00:32:15,800 --> 00:32:18,720
é, como xa discutir
loxicamente, tamén falsa.

690
00:32:18,720 --> 00:32:20,270
Entón, nós temos 0 aquí tamén.

691
00:32:20,270 --> 00:32:24,390
Se tomar 0 e comercial
1, así que, tamén,

692
00:32:24,390 --> 00:32:29,890
será 0, porque para iso
expresión da esquerda para ser verdade ou 1,

693
00:32:29,890 --> 00:32:32,360
sería necesario para ser verdade e verdade.

694
00:32:32,360 --> 00:32:36,320
Pero aquí temos false
e certa, ou 0 e 1.

695
00:32:36,320 --> 00:32:42,000
Agora, de novo, se temos un E comercial
0, que, tamén, vai ser 0,

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

697
00:32:47,240 --> 00:32:50,340
Polo tanto, noutras palabras, non estamos facendo
nada interesante con este operador

698
00:32:50,340 --> 00:32:51,850
aínda, 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
Pero estes son os ingredientes
a través do cal podemos facer

701
00:32:57,290 --> 00:32:59,240
cousas interesantes, como veremos en breve.

702
00:32:59,240 --> 00:33:02,790
>> Agora imos ollar só o único
barra vertical ata aquí, á dereita.

703
00:33:02,790 --> 00:33:06,710
Se eu tivera un bit 0 e I
OU-o con, o bit a bit

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

705
00:33:11,030 --> 00:33:17,540
Se eu tomar un bit 0 e OU-lo con
un bit 1, entón eu estou indo a obter un.

706
00:33:17,540 --> 00:33:19,830
E, de feito, só para
claridade, déixeme volver,

707
00:33:19,830 --> 00:33:23,380
de xeito que as miñas barrotes verticais
non son confundidos con 1s.

708
00:33:23,380 --> 00:33:26,560
Déixeme reescribir todo
meu 1 é un pouco máis

709
00:33:26,560 --> 00:33:32,700
claramente, para que poidamos ver a carón, se eu
ter un 1 ou 0, que vai ser un 1,

710
00:33:32,700 --> 00:33:39,060
e se eu tivera un 1 ou 1 que,
tamén, será un 1.

711
00:33:39,060 --> 00:33:42,900
Así pode ver que a lóxica OR
operador compórtase de xeito moi diferente.

712
00:33:42,900 --> 00:33:48,070
Isto dáme OU 0 0 0 me dá, pero
cada outra combinación dáme unha.

713
00:33:48,070 --> 00:33:52,480
Entón, mentres eu tivera un 1 no
fórmula, o resultado será unha.

714
00:33:52,480 --> 00:33:55,580
>> En contraste coa E
operador, o comercial,

715
00:33:55,580 --> 00:34:00,940
só se eu teño dous números 1 no
ecuación, realmente obter un 1.

716
00:34:00,940 --> 00:34:02,850
Agora hai algúns outros
operadores tamén.

717
00:34:02,850 --> 00:34:04,810
Un deles é un pouco máis complicado.

718
00:34:04,810 --> 00:34:07,980
Entón deixe-me ir adiante e eliminar
esta para liberar algún espazo.

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

720
00:34:13,020 --> 00:34:16,460
E imos dar un ollo ao
símbolo de acento circunflexo, por só un momento.

721
00:34:16,460 --> 00:34:18,210
Este é normalmente un
personaxe que podes escribir

722
00:34:18,210 --> 00:34:21,420
no seu teclado e sostendo Shift
a continuación, un dos números enriba do seu EUA

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

724
00:34:22,250 --> 00:34:26,190
>> Entón que é o único
Operador OU OU exclusivo.

725
00:34:26,190 --> 00:34:27,790
Entón, nós só 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 diferenza?

728
00:34:30,639 --> 00:34:34,570
Ben, imos só ollar para a fórmula,
e usar isto como ingredientes en última instancia.

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

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

731
00:34:39,650 --> 00:34:41,400
Esa é a definición de XOR.

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

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

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

735
00:34:59,890 --> 00:35:00,520
Ou non é?

736
00:35:00,520 --> 00:35:01,860
Eu non sei.

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

738
00:35:02,810 --> 00:35:04,700
Agora, o que está pasando aquí?

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

740
00:35:06,630 --> 00:35:09,980
OU exclusivo, para
nome, tipo, suxire,

741
00:35:09,980 --> 00:35:13,940
a resposta só será
1 as entradas son exclusivas,

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

743
00:35:15,560 --> 00:35:18,170
Entón, aquí están as entradas do
mesma, de xeito que a saída é 0.

744
00:35:18,170 --> 00:35:20,700
Aquí as entradas son o
mesma, de xeito que a saída é 0.

745
00:35:20,700 --> 00:35:25,640
Aquí están as saídas son diferentes,
son exclusivos, e entón a saída é 1.

746
00:35:25,640 --> 00:35:28,190
Polo tanto, é moi semellante ao
E, é moi semellante,

747
00:35:28,190 --> 00:35:32,760
ou mellor, é moi semellante ao
OU, pero só de forma exclusiva.

748
00:35:32,760 --> 00:35:36,210
Este non é un 1,
porque temos dous de 1,

749
00:35:36,210 --> 00:35:38,621
e non exclusivamente, só un deles.

750
00:35:38,621 --> 00:35:39,120
Todo ben.

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

752
00:35:40,080 --> 00:35:44,220
Ben o til, mentres, é
realmente agradable e simple, por sorte.

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

754
00:35:46,410 --> 00:35:50,400
aplicarase só unha entrada,
un operando, por así dicir.

755
00:35:50,400 --> 00:35:51,800
Non a un dereito e un dereito.

756
00:35:51,800 --> 00:35:56,050
Noutras palabras, se tomar til de
0, a resposta será o contrario.

757
00:35:56,050 --> 00:35:59,710
E se tomar til de 1, o
resposta haberá o contrario.

758
00:35:59,710 --> 00:36:02,570
Así, o operador til é
unha forma de negar un pouco,

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

760
00:36:06,000 --> 00:36:09,820
>> E iso déixanos finalmente
con só dous operadores finais,

761
00:36:09,820 --> 00:36:13,840
o chamado desprazamento cara á esquerda, eo
o chamado operador de desprazamento cara á dereita.

762
00:36:13,840 --> 00:36:16,620
Imos dar un ollo a como os traballos.

763
00:36:16,620 --> 00:36:20,780
O operador de desprazamento cara á esquerda, por escrito
con dous corchetes como esta,

764
00:36:20,780 --> 00:36:22,110
opera deste xeito.

765
00:36:22,110 --> 00:36:27,390
Se a miña entrada, ou a miña operando, á esquerda
operador de desprazamento é simplemente un 1.

766
00:36:27,390 --> 00:36:33,750
E eu, a continuación, dicir ao ordenador para
desvío á esquerda que unha, digamos sete prazas,

767
00:36:33,750 --> 00:36:37,150
o resultado é como se eu
tomar esta 1, e movelo

768
00:36:37,150 --> 00:36:40,160
sete lugares máis á
esquerda e, por defecto,

769
00:36:40,160 --> 00:36:42,270
imos supor que
o espazo á dereita

770
00:36:42,270 --> 00:36:44,080
será cuberto con ceros.

771
00:36:44,080 --> 00:36:50,316
Noutras palabras, un cambio 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 ceros.

773
00:36:54,060 --> 00:36:57,380
Entón, de certa forma, permite que
ter un número pequeno como 1,

774
00:36:57,380 --> 00:37:00,740
e facelo moi claramente
moi, moi grande, deste xeito,

775
00:37:00,740 --> 00:37:06,460
pero nós estamos indo realmente para ver
enfoques máis intelixentes para el

776
00:37:06,460 --> 00:37:08,080
Pola contra, como ben,

777
00:37:08,080 --> 00:37:08,720
>> Todo ben.

778
00:37:08,720 --> 00:37:10,060
É isto por tres semanas.

779
00:37:10,060 --> 00:37:11,400
Imos velo a 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
>> COLUMNA 1: Estaba no snack-
bar comendo un sundae de chocolate.

784
00:37:25,766 --> 00:37:28,090
Tiña todo sobre o seu rostro.

785
00:37:28,090 --> 00:37:30,506
El está a levar posto que o chocolate como unha barba

786
00:37:30,506 --> 00:37:31,756
COLUMNA 2: O que está facendo?

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

788
00:37:32,422 --> 00:37:33,500
Que?

789
00:37:33,500 --> 00:37:36,800
>> COLUMNA 2: Vostede acaba de dobre mergullo?

790
00:37:36,800 --> 00:37:38,585
Vostede dobre mergullou o chip.

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

792
00:37:39,460 --> 00:37:44,440
COLUMNA 2: Vostede é dicir o chip, vostede
deu unha mordida, e mergullou novo.

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

794
00:37:44,940 --> 00:37:48,440
COLUMNA 2: Así que é como poñer
todo o seu dereito boca no mergullo.

795
00:37:48,440 --> 00:37:52,400
A próxima vez que tomar un chip,
só mergullalos lo unha vez, e remata-la.

796
00:37:52,400 --> 00:37:53,890
>> COLUMNA 3: Vostede sabe o que, Dan?

797
00:37:53,890 --> 00:37:58,006
Mergulla a forma que sexa mergullo.

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

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