1
00:00:00,000 --> 00:00:11,904
>> [REPRODUCCIÓ DE MÚSICA]

2
00:00:11,904 --> 00:00:12,910
>> PROFESSOR: Molt bé.

3
00:00:12,910 --> 00:00:16,730
Això és CS50 i això és
Al final de la tercera setmana.

4
00:00:16,730 --> 00:00:20,230
Així que estem aquí avui, no en Sanders
Teatre, en lloc de Weidner Biblioteca.

5
00:00:20,230 --> 00:00:23,170
A l'interior dels quals és un estudi
conegut com Hauser d'estudi,

6
00:00:23,170 --> 00:00:28,310
o millor dit Estudi H, o aniran
que dir-- si et va agradar la broma,

7
00:00:28,310 --> 00:00:30,540
en realitat és de
company, Mark, en línia,

8
00:00:30,540 --> 00:00:32,420
qui va suggerir tant a través de Twitter.

9
00:00:32,420 --> 00:00:34,270
Ara el bo de
ser aquí en un estudi

10
00:00:34,270 --> 00:00:38,410
és que estic envoltat d'aquests de verd
parets, una pantalla verda o chromakey,

11
00:00:38,410 --> 00:00:43,290
per així dir-ho, el que significa que CS50 de
equip de producció, sense jo saber-ho

12
00:00:43,290 --> 00:00:47,380
en aquest moment, podria ser posar
més em qualsevol part del món,

13
00:00:47,380 --> 00:00:48,660
per bé o per mal.

14
00:00:48,660 --> 00:00:51,800
>> Ara el que s'acosta, estableix problema
2 és a les seves mans per a aquesta setmana,

15
00:00:51,800 --> 00:00:53,830
però amb el problema d'establir
de tres aquesta setmana que ve,

16
00:00:53,830 --> 00:00:56,600
seràs reptat amb
l'anomenat joc de 15,

17
00:00:56,600 --> 00:00:58,960
un vell partit a favor que
es pot recordar que rep

18
00:00:58,960 --> 00:01:02,030
com un nen que té un munt
de nombres que es poden lliscar cap amunt, avall,

19
00:01:02,030 --> 00:01:05,790
esquerra i dreta, i hi ha una bretxa
dins del trencaclosques, en què

20
00:01:05,790 --> 00:01:07,840
pot lliscar en realitat aquestes peces del trencaclosques.

21
00:01:07,840 --> 00:01:11,150
En última instància rep aquest
trencaclosques en algun ordre semi aleatòria,

22
00:01:11,150 --> 00:01:12,940
i l'objectiu és
ordenar-la, de dalt a baix,

23
00:01:12,940 --> 00:01:16,310
esquerra a dreta, d'un
tot el camí a través de 15.

24
00:01:16,310 --> 00:01:19,360
>> Desafortunadament, la implementació
tindràs a la mà

25
00:01:19,360 --> 00:01:21,590
serà el programari
basat, no físicament.

26
00:01:21,590 --> 00:01:25,280
Vostè està en realitat va a haver d'escriure
codi amb el qual un estudiant o usuari llauna

27
00:01:25,280 --> 00:01:26,760
jugar el joc dels 15.

28
00:01:26,760 --> 00:01:29,030
I de fet, en el hacker
edició del joc de 15,

29
00:01:29,030 --> 00:01:32,155
vostè serà un desafiament per posar en pràctica,
no només el joc d'aquesta vella escola

30
00:01:32,155 --> 00:01:35,010
joc, sinó més aviat la resolució
d'això, l'aplicació de manera de déu,

31
00:01:35,010 --> 00:01:38,280
per així dir-ho, que de fet
resol el trencaclosques per a l'ésser humà,

32
00:01:38,280 --> 00:01:41,080
posant a la seva pista,
després de pista, a continuació, toqueu.

33
00:01:41,080 --> 00:01:42,280
Així que més que la setmana que ve.

34
00:01:42,280 --> 00:01:43,720
Però això és el que ens espera.

35
00:01:43,720 --> 00:01:47,610
>> Per ara recordar que a principis d'aquesta setmana
hem tingut aquest melodrama, si es vol,

36
00:01:47,610 --> 00:01:52,560
de manera que el millor que estàvem fent la classificació
sàvia era una fita superior de gran o de n

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

38
00:01:53,210 --> 00:01:56,520
En altres paraules, ordenament de bombolla,
ordenació per selecció, ordenació per inserció,

39
00:01:56,520 --> 00:01:59,120
tots ells, mentre diferent
en la seva aplicació,

40
00:01:59,120 --> 00:02:03,480
degenerat en un quadrat n corrent
temps en el pitjor dels casos.

41
00:02:03,480 --> 00:02:06,010
I en general, suposem que
el pitjor dels casos per a la classificació

42
00:02:06,010 --> 00:02:08,814
és un que les seves entrades
són completament a l'inrevés.

43
00:02:08,814 --> 00:02:11,980
I, de fet, li va prendre uns quants passos
per posar en pràctica cada un dels algoritmes.

44
00:02:11,980 --> 00:02:15,110
>> Ara al final de la classe
revocatori, comparem ordenament de bombolla

45
00:02:15,110 --> 00:02:19,390
contra l'ordenació per selecció contra un altre
que anomenem de combinació de classe en el moment,

46
00:02:19,390 --> 00:02:22,120
i jo proposo que està prenent
avantatge d'una lliçó de la setmana

47
00:02:22,120 --> 00:02:24,060
zero, divideix i venceràs.

48
00:02:24,060 --> 00:02:28,810
I d'alguna manera aconseguir algun tipus de
logarítmica temps de funcionament en última instància,

49
00:02:28,810 --> 00:02:31,024
en lloc d'alguna cosa
això és purament quadràtica.

50
00:02:31,024 --> 00:02:33,440
I no és prou logarítmica,
que és una mica més que això.

51
00:02:33,440 --> 00:02:36,520
Però si vostè recorda de la classe,
era molt, molt més ràpid.

52
00:02:36,520 --> 00:02:38,210
Fem una ullada a on ho vam deixar.

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

54
00:02:41,880 --> 00:02:45,370
>> Bombolla tipus contra la selecció
tipus de combinació front espècie.

55
00:02:45,370 --> 00:02:47,700
Ara estan tots corrent, en
teoria, al mateix temps.

56
00:02:47,700 --> 00:02:50,510
La CPU està funcionant a la mateixa velocitat.

57
00:02:50,510 --> 00:02:54,990
Però es pot sentir el avorrit això
va molt ràpidament per convertir-se,

58
00:02:54,990 --> 00:02:58,790
i la rapidesa, quan injectem
una mica d'algoritmes setmana de zero,

59
00:02:58,790 --> 00:03:00,080
podem accelerar les coses.

60
00:03:00,080 --> 00:03:01,630
>> Així espècie marca es veu increïble.

61
00:03:01,630 --> 00:03:05,220
Com podem aprofitar que, per tal
per ordenar els nombres més ràpidament.

62
00:03:05,220 --> 00:03:07,140
Bé anem a pensar en tornar
a un ingredient que

63
00:03:07,140 --> 00:03:10,380
tenia de tornada en setmanes zero, el de
buscant a algú en una guia telefònica,

64
00:03:10,380 --> 00:03:12,380
i recordar que el
pseudo-codi que vam proposar,

65
00:03:12,380 --> 00:03:14,560
a través del qual podem trobar
algú com Mike Smith,

66
00:03:14,560 --> 00:03:16,310
semblava una mica alguna cosa com això.

67
00:03:16,310 --> 00:03:20,820
>> Ara fa una ullada en particular,
en la línia 7 i 8, i 10 i 11,

68
00:03:20,820 --> 00:03:25,240
que indueixen aquest bucle, en el qual vam mantenir
que es remunta a la línia 3 de nou, i una altra,

69
00:03:25,240 --> 00:03:26,520
i una altra.

70
00:03:26,520 --> 00:03:31,790
Però resulta que podem veure
aquest algoritme, aquí a pseudocodi,

71
00:03:31,790 --> 00:03:33,620
una mica més de manera integral.

72
00:03:33,620 --> 00:03:35,960
De fet, el que estic buscant
pel que aquí a la pantalla,

73
00:03:35,960 --> 00:03:41,180
és un algoritme per a la recerca de
Mike Smith, entre un conjunt de pàgines.

74
00:03:41,180 --> 00:03:45,520
I de fet, podríem simplificar aquest
algoritme en aquestes línies 7 i 8,

75
00:03:45,520 --> 00:03:49,860
i 10 i 11 a només dir això,
que he presentat aquí en groc.

76
00:03:49,860 --> 00:03:52,210
En altres paraules, si Mike
Smith és anterior en el llibre,

77
00:03:52,210 --> 00:03:55,004
no necessitem especificar pas
a pas ara com anar a buscar.

78
00:03:55,004 --> 00:03:56,920
No hem d'especificar
per tornar a la línia 3,

79
00:03:56,920 --> 00:03:58,960
Per què no simplement en el seu lloc,
per exemple, més en general,

80
00:03:58,960 --> 00:04:01,500
buscar Mike en el
mitjana esquerra del llibre.

81
00:04:01,500 --> 00:04:03,960
>> Al revés, si Mike és
en realitat més endavant en el llibre,

82
00:04:03,960 --> 00:04:07,540
¿Per què no acabem de citar recerca cap de la cita
Mike en la meitat dreta del llibre.

83
00:04:07,540 --> 00:04:11,030
En altres paraules, per què no ho fem només
espècie de batea a nosaltres mateixos dient:

84
00:04:11,030 --> 00:04:13,130
buscar Mike en aquest
subconjunt del llibre,

85
00:04:13,130 --> 00:04:16,279
i deixar que els nostres actuals
algoritme que ens digui

86
00:04:16,279 --> 00:04:18,750
com buscar Mike en
que la meitat esquerra del llibre.

87
00:04:18,750 --> 00:04:20,750
En altres paraules, la nostra
algoritme funciona ja sigui

88
00:04:20,750 --> 00:04:24,670
una llibreta de telèfons d'aquest gruix, d'aquesta
gruix, o qualsevol espessor que sigui.

89
00:04:24,670 --> 00:04:27,826
Així que el que puguem de manera recursiva
definir aquest algorisme.

90
00:04:27,826 --> 00:04:29,950
En altres paraules, en el
pantalla d'aquí, és un algoritme

91
00:04:29,950 --> 00:04:33,130
per a la recerca de Mike Smith
entre les pàgines d'un llibre de telèfon.

92
00:04:33,130 --> 00:04:37,410
Així, en la línia 7 i 10, anem a
a dir exactament això.

93
00:04:37,410 --> 00:04:40,250
I utilitzo aquest terme un moment
Fa, i de fet, la recursió

94
00:04:40,250 --> 00:04:42,450
és la paraula de moda, per ara,
i és aquest procés

95
00:04:42,450 --> 00:04:47,210
de fer alguna cosa cíclic d'alguna manera
utilitzant el codi que ja té,

96
00:04:47,210 --> 00:04:49,722
i dir que és nou,
i una altra, i una altra.

97
00:04:49,722 --> 00:04:51,930
Ara que va a ser important
que d'alguna manera inferior

98
00:04:51,930 --> 00:04:53,821
fora, i no facis això infinitament llarg.

99
00:04:53,821 --> 00:04:56,070
Altrament, anem a
tenen de fet un bucle infinit.

100
00:04:56,070 --> 00:04:59,810
Però anem a veure si podem demanar prestada aquesta idea
d'un recursivitat, fer alguna cosa nova

101
00:04:59,810 --> 00:05:03,600
i una vegada i una altra, per resoldre
el problema de classificació a través de combinació

102
00:05:03,600 --> 00:05:05,900
Ordena, tota la manera més eficient.

103
00:05:05,900 --> 00:05:06,970
>> Així que li dono combinar tipus.

104
00:05:06,970 --> 00:05:07,920
Anem a fer una ullada.

105
00:05:07,920 --> 00:05:10,850
Així que aquí és pseudocodi, amb
que podríem aplicar la classificació,

106
00:05:10,850 --> 00:05:12,640
l'ús d'aquest algorisme anomenat fusió tipus.

107
00:05:12,640 --> 00:05:13,880
I és simplement això.

108
00:05:13,880 --> 00:05:15,940
A l'entrada de n elements,
en altres paraules, si vostè és

109
00:05:15,940 --> 00:05:18,830
donada n elements i nombres i
cartes o el que la entrada és,

110
00:05:18,830 --> 00:05:22,430
si et donen n elements, si
n és menor que 2, simplement tornar.

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

112
00:05:22,930 --> 00:05:26,430
Perquè si n és menor que 2, que
vol dir que la meva llista d'elements

113
00:05:26,430 --> 00:05:30,446
és qualsevol de mida 0 o 1, i
en tots dos casos trivials,

114
00:05:30,446 --> 00:05:31,570
la llista ja està ordenat.

115
00:05:31,570 --> 00:05:32,810
Si no hi ha una llista, és ordenada.

116
00:05:32,810 --> 00:05:35,185
I si hi ha una llista de longitud
1, és òbviament ordenat.

117
00:05:35,185 --> 00:05:38,280
Així que l'algoritme només necessita
realment fer alguna cosa interessant,

118
00:05:38,280 --> 00:05:40,870
si tenim dos o més
elements donats a nosaltres.

119
00:05:40,870 --> 00:05:42,440
Així que donem una ullada a la màgia llavors.

120
00:05:42,440 --> 00:05:47,500
Else ordenar la meitat esquerra dels elements,
a continuació, ordenar la meitat dreta dels elements,

121
00:05:47,500 --> 00:05:49,640
després fusionar les meitats ordenats.

122
00:05:49,640 --> 00:05:52,440
I el que és classe de ment flexió
aquí, és que realment no em

123
00:05:52,440 --> 00:05:56,190
semblen que han dit
res encara, oi?

124
00:05:56,190 --> 00:05:59,560
Tot el que he dit és, donada una llista de
n elements, ordenar la meitat esquerra,

125
00:05:59,560 --> 00:06:01,800
llavors la meitat dreta, a continuació,
fusionar les meitats ordenats,

126
00:06:01,800 --> 00:06:03,840
però on és l'ingredient secret real?

127
00:06:03,840 --> 00:06:05,260
On és l'algoritme?

128
00:06:05,260 --> 00:06:09,150
Doncs resulta que aquestes dues línies
primer, ordenar l'esquerra de la meitat dels elements,

129
00:06:09,150 --> 00:06:13,970
i tipus adequat mitjà d'elements,
són crides recursives, per així dir-ho.

130
00:06:13,970 --> 00:06:16,120
>> Després de tot, en aquest
punt en el temps, he

131
00:06:16,120 --> 00:06:18,950
un algoritme amb el qual
ordenar un munt d'elements?

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

133
00:06:19,450 --> 00:06:20,620
És just aquí.

134
00:06:20,620 --> 00:06:25,180
És aquí a la pantalla, i
així que puc utilitzar aquest mateix conjunt de mesures

135
00:06:25,180 --> 00:06:28,500
per ordenar la meitat esquerra,
com puc la meitat dreta.

136
00:06:28,500 --> 00:06:30,420
I, en efecte, de nou, una vegada i una altra.

137
00:06:30,420 --> 00:06:34,210
Així que d'alguna manera o altra, i que aviat
veure això, la màgia de la combinació de tipus

138
00:06:34,210 --> 00:06:37,967
està incrustat en aquest mateix definitiva
línia, la fusió de les meitats ordenades.

139
00:06:37,967 --> 00:06:39,300
I això sembla bastant intuïtiu.

140
00:06:39,300 --> 00:06:41,050
Vostè pren dues meitats, i tu,
d'alguna manera, unir-los,

141
00:06:41,050 --> 00:06:43,260
i anem a veure això
concretament en un moment.

142
00:06:43,260 --> 00:06:45,080
>> Però aquest és un algoritme complet.

143
00:06:45,080 --> 00:06:46,640
I anem a veure exactament per què.

144
00:06:46,640 --> 00:06:50,912
Bé suposem que ens donen aquests mateixos
08:00 elements aquí a la pantalla, un

145
00:06:50,912 --> 00:06:53,120
a través de vuit, però són
per tal aparentment a l'atzar.

146
00:06:53,120 --> 00:06:55,320
I l'objectiu que ens ocupa és
per ordenar aquests elements.

147
00:06:55,320 --> 00:06:58,280
Bé, com puc anar sobre
Ho podeu, de nou,

148
00:06:58,280 --> 00:07:00,407
ordenament per barreja, segons aquest pseudocodi?

149
00:07:00,407 --> 00:07:02,740
I de nou, arrelar això en
la seva ment, només per un moment.

150
00:07:02,740 --> 00:07:05,270
El primer cas és força
trivial, si és menys de 2,

151
00:07:05,270 --> 00:07:07,060
simplement tornar, no hi ha feina per fer.

152
00:07:07,060 --> 00:07:09,290
Així que en realitat hi ha només tres
mesures per mantenir molt en compte.

153
00:07:09,290 --> 00:07:11,081
Un cop més, i una altra vegada, estic
voldrà tenir

154
00:07:11,081 --> 00:07:13,980
per ordenar la meitat esquerra,
ordenar la meitat dreta,

155
00:07:13,980 --> 00:07:15,890
i després una vegada la seva
dues meitats estan ordenats,

156
00:07:15,890 --> 00:07:18,710
Vull unir-los
en una llista ordenada.

157
00:07:18,710 --> 00:07:19,940
Així que tingues-ho en compte.

158
00:07:19,940 --> 00:07:21,310
>> Així que aquí està la llista original.

159
00:07:21,310 --> 00:07:23,510
Anem a tractar això com una
matriu, com vam començar a

160
00:07:23,510 --> 00:07:25,800
en la segona setmana, que és un
bloc contigu de memòria.

161
00:07:25,800 --> 00:07:28,480
En aquest cas, que conté vuit
números, esquena amb esquena amb esquena.

162
00:07:28,480 --> 00:07:30,700
I ara anem a aplicar fusió tipus.

163
00:07:30,700 --> 00:07:33,300
Així que primer vull ordenar
la meitat esquerra d'aquesta llista,

164
00:07:33,300 --> 00:07:37,370
i deixar de, per tant,
centrar-se en 4, 8, 6, i 2.

165
00:07:37,370 --> 00:07:41,000
>> Ara, com faig per
ordenar una llista de grandària de 4?

166
00:07:41,000 --> 00:07:45,990
Bé he de considerar ara
la classificació de l'esquerra de la meitat esquerra.

167
00:07:45,990 --> 00:07:47,720
Un cop més, anem a retrocedir per un moment.

168
00:07:47,720 --> 00:07:51,010
Si el pseudocodi és això,
i em donen 8 elements,

169
00:07:51,010 --> 00:07:53,230
8 és òbviament major
que o igual a 2.

170
00:07:53,230 --> 00:07:54,980
Així que amb el primer cas no s'aplica.

171
00:07:54,980 --> 00:07:58,120
Així que per classificar 08:00 elements, jo primer
ordenar la meitat esquerra d'elements,

172
00:07:58,120 --> 00:08:01,930
llavors puc ordenar la meitat dreta, després em fusiono
les dues meitats ordenades, cadascuna de la mida de 4.

173
00:08:01,930 --> 00:08:02,470
D'ACORD.

174
00:08:02,470 --> 00:08:07,480
>> Però si el que m'has dit, ordenar la
meitat esquerra, que ara és de mida 4,

175
00:08:07,480 --> 00:08:09,350
Com puc ordenar el medi queda?

176
00:08:09,350 --> 00:08:11,430
Bé, si tinc una
d'entrada de quatre elements,

177
00:08:11,430 --> 00:08:14,590
Jo primer ordenar l'esquerra
dos, i després tots dos a la dreta,

178
00:08:14,590 --> 00:08:16,210
i després unir-los.

179
00:08:16,210 --> 00:08:18,700
Així que de nou, es torna una mica
d'una ment de flexió joc aquí,

180
00:08:18,700 --> 00:08:21,450
perquè, classe de, que
recordar on vostè està en la història,

181
00:08:21,450 --> 00:08:23,620
però al final del dia,
donat qualsevol nombre d'elements,

182
00:08:23,620 --> 00:08:25,620
que primer vol ordenar la
mitjà esquerre, després la meitat dreta,

183
00:08:25,620 --> 00:08:26,661
després unir-los.

184
00:08:26,661 --> 00:08:28,630
Anem a començar a fer exactament això.

185
00:08:28,630 --> 00:08:30,170
Aquí hi ha l'entrada de vuit elements.

186
00:08:30,170 --> 00:08:31,910
Ara estem veient la meitat esquerra aquí.

187
00:08:31,910 --> 00:08:33,720
Com puc ordenar quatre elements?

188
00:08:33,720 --> 00:08:35,610
Bé, jo primer ordenar el medi esquerra.

189
00:08:35,610 --> 00:08:37,720
Ara, com puc ordenar el medi queda?

190
00:08:37,720 --> 00:08:39,419
Bé m'han donat dos elements.

191
00:08:39,419 --> 00:08:41,240
Així que anem a ordenar aquests dos elements.

192
00:08:41,240 --> 00:08:44,540
2 és major o
igual a 2, és clar.

193
00:08:44,540 --> 00:08:46,170
Així que el primer cas no s'aplica.

194
00:08:46,170 --> 00:08:49,010
>> Així que ara he de ordenar l'esquerra
mitjà d'aquests dos elements.

195
00:08:49,010 --> 00:08:50,870
La meitat esquerra, per descomptat, és a 4.

196
00:08:50,870 --> 00:08:54,020
Llavors, com puc ordenar una llista d'un element?

197
00:08:54,020 --> 00:08:57,960
Ara bé, aquest cas base especial
a la part alta, per així dir-ho, s'aplica.

198
00:08:57,960 --> 00:09:01,470
1 és menor que 2, i el meu
llista és precisament de mida 1.

199
00:09:01,470 --> 00:09:02,747
Així que em torno.

200
00:09:02,747 --> 00:09:03,580
Jo no faig res.

201
00:09:03,580 --> 00:09:06,770
I de fet, mira el que tinc
fet, 4 ja està ordenat.

202
00:09:06,770 --> 00:09:09,220
Igual que ja estic
parcialment reeixit aquí.

203
00:09:09,220 --> 00:09:11,750
>> Ara que sembla una mica estúpid
a reclamar, però és cert.

204
00:09:11,750 --> 00:09:13,700
4 és una llista de tamany 1.

205
00:09:13,700 --> 00:09:15,090
Ja està solucionat.

206
00:09:15,090 --> 00:09:16,270
Això és la meitat esquerra.

207
00:09:16,270 --> 00:09:18,010
Ara puc ordenar la meitat dreta.

208
00:09:18,010 --> 00:09:22,310
El meu entrada és un element, 8
De la mateixa manera, ja ordenats.

209
00:09:22,310 --> 00:09:25,170
Estúpid, també, però de nou,
aquest principi bàsic

210
00:09:25,170 --> 00:09:28,310
va a permetre que construïm ara
a la part superior d'aquest èxit.

211
00:09:28,310 --> 00:09:32,260
4 ordenats, 8 s'ordena, ara
¿Quin va ser l'últim pas?

212
00:09:32,260 --> 00:09:35,330
Així que el tercer i últim pas, qualsevol
temps estàs ordenar una llista, el record,

213
00:09:35,330 --> 00:09:38,310
era fusionar les dues meitats,
l'esquerra i la dreta.

214
00:09:38,310 --> 00:09:39,900
Així que farem exactament això.

215
00:09:39,900 --> 00:09:41,940
El meu mitjana esquerra és, per descomptat, 4.

216
00:09:41,940 --> 00:09:43,310
El meu meitat dreta és 8.

217
00:09:43,310 --> 00:09:44,100
>> Així que anem a fer això.

218
00:09:44,100 --> 00:09:46,410
En primer lloc vaig a assignar
una mica de memòria addicional,

219
00:09:46,410 --> 00:09:48,680
que vaig a represento aquí,
com s'acaba d'una matriu secundària,

220
00:09:48,680 --> 00:09:49,660
això és prou gran per a això.

221
00:09:49,660 --> 00:09:52,243
Però es pot imaginar que s'estén
aquest rectangle tota la longitud,

222
00:09:52,243 --> 00:09:53,290
si necessitem més tard.

223
00:09:53,290 --> 00:09:58,440
Com prenc 4 i 8, i es fusionen
aquestes dues llistes de tamany 1 en conjunt?

224
00:09:58,440 --> 00:10:00,270
Aquí, també, bastant simple.

225
00:10:00,270 --> 00:10:03,300
4 ve primer, després ve 8.

226
00:10:03,300 --> 00:10:07,130
Perquè si vull ordenar la
mitjà esquerre, després la meitat dreta,

227
00:10:07,130 --> 00:10:09,900
i després fusionar aquestes dues meitats
junts, en forma ordenada,

228
00:10:09,900 --> 00:10:11,940
4 ve primer, després ve 8.

229
00:10:11,940 --> 00:10:15,810
>> Així que sembla que estem fent progressos, fins i tot
encara que no he fet cap treball real.

230
00:10:15,810 --> 00:10:17,800
Però recorda on som en la història.

231
00:10:17,800 --> 00:10:19,360
Originalment fa vuit elements.

232
00:10:19,360 --> 00:10:21,480
Classifiquem la meitat esquerra, que és 4.

233
00:10:21,480 --> 00:10:24,450
Llavors ens ho van solucionar la meitat esquerra
de la meitat esquerra, que era 2.

234
00:10:24,450 --> 00:10:25,270
I aquí anem.

235
00:10:25,270 --> 00:10:26,920
Hem acabat amb aquest pas.

236
00:10:26,920 --> 00:10:29,930
>> Així que si hem van solucionar el
mitjana de 2 vam ser, ara nosaltres

237
00:10:29,930 --> 00:10:32,130
ha d'ordenar la meitat dreta de 2.

238
00:10:32,130 --> 00:10:35,710
Així que la meitat dreta de 2 és
aquests dos valors aquí, 6 i 2.

239
00:10:35,710 --> 00:10:40,620
Així que anem a prendre ara una entrada de grandària
2, i ordenar la meitat esquerra, i després

240
00:10:40,620 --> 00:10:42,610
la meitat dreta, i després
unir-los.

241
00:10:42,610 --> 00:10:45,722
Bé, com puc ordenar una llista de mida
1, que conté només el número 6?

242
00:10:45,722 --> 00:10:46,430
Jo ja he acabat.

243
00:10:46,430 --> 00:10:48,680
S'ordena aquesta llista de tamany 1.

244
00:10:48,680 --> 00:10:52,140
>> Com puc ordenar una altra llista de
mida 1, l'anomenada mitjana dreta.

245
00:10:52,140 --> 00:10:54,690
Bé, també, ja està solucionat.

246
00:10:54,690 --> 00:10:56,190
El número 2 és l'únic.

247
00:10:56,190 --> 00:11:00,160
Així que ara tinc dues meitats, esquerra i
bé, he de unir-los.

248
00:11:00,160 --> 00:11:01,800
Permetin-me dono una mica d'espai extra.

249
00:11:01,800 --> 00:11:05,580
I posar 2 en allà,
a continuació, 6 de allà, d'aquesta manera

250
00:11:05,580 --> 00:11:10,740
ordenar la llista, esquerra i dreta,
i la fusió junts, en última instància.

251
00:11:10,740 --> 00:11:12,160
Així que estic en una mica millor forma.

252
00:11:12,160 --> 00:11:16,250
No he acabat, perquè és evident 4, 8, 2,
6 no és l'ordenament final que vull.

253
00:11:16,250 --> 00:11:20,640
Però ara tinc dues llistes de mida 2, que
haver-hi dos, respectivament, estat ordenats.

254
00:11:20,640 --> 00:11:24,580
Així que ara si es rebobina en la seva ment de
ull, ¿on ens deixa això?

255
00:11:24,580 --> 00:11:28,520
Vaig començar amb vuit elements, llavors jo
retallat cap avall a la meitat esquerra de 4,

256
00:11:28,520 --> 00:11:31,386
a continuació, la meitat esquerra de 2, i
llavors la meitat dreta de 2,

257
00:11:31,386 --> 00:11:34,510
Vaig acabar, per tant, la classificació de l'esquerra
mitjana de 2, i la meitat dreta de 2,

258
00:11:34,510 --> 00:11:37,800
¿Quin és el tercer i últim pas aquí?

259
00:11:37,800 --> 00:11:41,290
He de fusionar
dues llistes de mida 2.

260
00:11:41,290 --> 00:11:42,040
Així que seguirem endavant.

261
00:11:42,040 --> 00:11:43,940
I a la pantalla aquí, donar
em una mica de memòria addicional,

262
00:11:43,940 --> 00:11:47,170
encara que tècnicament, noto que tinc
té un munt d'espai en blanc sobre de la tapa

263
00:11:47,170 --> 00:11:47,670
allà.

264
00:11:47,670 --> 00:11:50,044
Si vull ser especialment
espai eficient savi,

265
00:11:50,044 --> 00:11:52,960
Jo només podia començar a moure els elements
endavant i enrere, amunt i avall.

266
00:11:52,960 --> 00:11:55,460
Però només per la claredat visual,
Vaig a posar-ho baix,

267
00:11:55,460 --> 00:11:56,800
per mantenir les coses agradables i netes.

268
00:11:56,800 --> 00:11:58,150
>> Així que tinc dues llistes de mida 2.

269
00:11:58,150 --> 00:11:59,770
La primera llista té 4 i 8.

270
00:11:59,770 --> 00:12:01,500
La segona llista té 2 i 6.

271
00:12:01,500 --> 00:12:03,950
Anem a fusionar els
junts en forma ordenada.

272
00:12:03,950 --> 00:12:09,910
2, per descomptat, és el primer,
després 4, després 6, llavors 8.

273
00:12:09,910 --> 00:12:12,560
I ara sembla que estem aconseguint
en algun lloc interessant.

274
00:12:12,560 --> 00:12:15,720
Medi Ara he ordenada de la
llista, i casualment, és

275
00:12:15,720 --> 00:12:18,650
tots els nombres parells, però això
és, de fet, només una coincidència.

276
00:12:18,650 --> 00:12:22,220
I ara he ordenat l'esquerra
mitjà, per la qual cosa és 2, 4, 6 i 8.

277
00:12:22,220 --> 00:12:23,430
Res està fora d'ordre.

278
00:12:23,430 --> 00:12:24,620
Que se sent com el progrés.

279
00:12:24,620 --> 00:12:26,650
>> Ara se sent com si hagués
estat parlant sempre ara,

280
00:12:26,650 --> 00:12:29,850
així que el que queda per veure si això
algoritme és, de fet, més eficient.

281
00:12:29,850 --> 00:12:31,766
Però anem a través
super metòdicament.

282
00:12:31,766 --> 00:12:34,060
Un ordinador, per descomptat,
ho faria així.

283
00:12:34,060 --> 00:12:34,840
Llavors, ¿on som?

284
00:12:34,840 --> 00:12:36,180
Comencem amb vuit elements.

285
00:12:36,180 --> 00:12:37,840
Em vaig classificar la meitat esquerra de 4.

286
00:12:37,840 --> 00:12:39,290
Em sembla que fer amb això.

287
00:12:39,290 --> 00:12:42,535
Així que ara el següent pas és
ordenar la meitat dreta de 4.

288
00:12:42,535 --> 00:12:44,410
I aquesta part podem anar
a través d'una mica més de

289
00:12:44,410 --> 00:12:47,140
ràpidament, encara que vostè és
benvinguts a rebobinar o pausar, just

290
00:12:47,140 --> 00:12:49,910
pensar a través d'ell en
el seu propi ritme, però el

291
00:12:49,910 --> 00:12:53,290
que tenim ara és una oportunitat per
fer el mateix algoritme exacte de les quatre

292
00:12:53,290 --> 00:12:54,380
nombres diferents.

293
00:12:54,380 --> 00:12:57,740
>> Així que seguirem endavant, i se centren en
la meitat dreta, el que estem aquí.

294
00:12:57,740 --> 00:13:01,260
La meitat esquerra d'aquest
mig dret, i ara el

295
00:13:01,260 --> 00:13:04,560
meitat esquerra de l'esquerra
la meitat d'aquesta meitat dreta,

296
00:13:04,560 --> 00:13:08,030
i com puc ordenar una llista de mida
1 que conté només el número 1?

297
00:13:08,030 --> 00:13:09,030
Ja està fet.

298
00:13:09,030 --> 00:13:11,830
Com puc fer el mateix per a una llista
de tamany 1 que conté només 7?

299
00:13:11,830 --> 00:13:12,840
Ja està fet.

300
00:13:12,840 --> 00:13:16,790
El tercer pas d'aquest mitjà a continuació,
és fusionar aquests dos elements

301
00:13:16,790 --> 00:13:20,889
en una nova llista de mida 2, 1 i 7.

302
00:13:20,889 --> 00:13:23,180
No semblen haver fet tot
que molta feina interessant.

303
00:13:23,180 --> 00:13:24,346
Anem a veure què passa després.

304
00:13:24,346 --> 00:13:29,210
Acabo van solucionar la meitat esquerra de la
meitat dreta de la meva entrada original.

305
00:13:29,210 --> 00:13:32,360
Ara anem a ordenar la dreta
mitjà, que conté 5 i 3.

306
00:13:32,360 --> 00:13:35,740
Anem a tornar a veure a l'esquerra
mitjà, ordenats, mig dret, ordenats,

307
00:13:35,740 --> 00:13:39,120
i fusionar els dos junts,
en una mica d'espai addicional,

308
00:13:39,120 --> 00:13:41,670
3 ve primer, després ve 5.

309
00:13:41,670 --> 00:13:46,190
I ara, hem classificat el
mitjana esquerra de la meitat dreta

310
00:13:46,190 --> 00:13:49,420
del problema original, i
la meitat dreta de la meitat dreta

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

312
00:13:50,800 --> 00:13:52,480
Quina és la tercera i última etapa?

313
00:13:52,480 --> 00:13:54,854
Bé per fusionar aquestes dues meitats.

314
00:13:54,854 --> 00:13:57,020
Així que permetin-me a mi mateix una mica
espai extra, però, de nou,

315
00:13:57,020 --> 00:13:58,699
podria ser l'ús d'aquest espai fins recanvi superior.

316
00:13:58,699 --> 00:14:00,490
Però nosaltres seguirem
simple visualment.

317
00:14:00,490 --> 00:14:07,070
Permetin-me ara es fonen en 1, i
a continuació, 3, 5 i, a continuació, i després 7.

318
00:14:07,070 --> 00:14:10,740
D'aquesta manera deixant-me ara amb la
meitat dreta del problema original

319
00:14:10,740 --> 00:14:12,840
Això és perfectament ordenats.

320
00:14:12,840 --> 00:14:13,662
>> Llavors, què queda?

321
00:14:13,662 --> 00:14:16,120
Sento que segueixo dient que el
mateixes coses una i altra vegada,

322
00:14:16,120 --> 00:14:18,700
però això és un reflex de la
fet que estem utilitzant recursivitat.

323
00:14:18,700 --> 00:14:21,050
El procés d'usar una
algoritme de nou, i de nou,

324
00:14:21,050 --> 00:14:23,940
en subconjunts més petits de
el problema original.

325
00:14:23,940 --> 00:14:27,580
Així que ara tenim una esquerra ordenats
mitjà del problema original.

326
00:14:27,580 --> 00:14:30,847
Tinc un mitjà ordenat dret
del problema original.

327
00:14:30,847 --> 00:14:32,180
Quina és la tercera i última etapa?

328
00:14:32,180 --> 00:14:33,590
Oh, és la fusió.

329
00:14:33,590 --> 00:14:34,480
Així que anem a fer això.

330
00:14:34,480 --> 00:14:36,420
Anem a assignar alguns addicionals
memòria, però el meu Déu, ens

331
00:14:36,420 --> 00:14:37,503
podria posar en qualsevol lloc ara.

332
00:14:37,503 --> 00:14:40,356
Tenim molt espai disponible
per a nosaltres, però anem a mantenir les coses simples.

333
00:14:40,356 --> 00:14:42,730
En lloc d'anar cap enrere i
endavant amb la nostra memòria original,

334
00:14:42,730 --> 00:14:44,480
anem fes-ho
visualment per aquí baix,

335
00:14:44,480 --> 00:14:47,240
per acabar la fusió de la
meitat esquerra i la meitat dreta.

336
00:14:47,240 --> 00:14:49,279
>> Així que mitjançant la fusió, què he de fer?

337
00:14:49,279 --> 00:14:50,820
Vull aprofitar els elements en ordre.

338
00:14:50,820 --> 00:14:53,230
Així que mirant a la meitat esquerra,
Veig el primer número és 2.

339
00:14:53,230 --> 00:14:55,230
Miro a la meitat dreta,
Veig el primer número

340
00:14:55,230 --> 00:14:58,290
és 1, així que òbviament que
nombre Què vull arrencar,

341
00:14:58,290 --> 00:15:00,430
i posar primer a la meva llista final?

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

343
00:15:01,449 --> 00:15:02,990
Ara vull fer aquesta mateixa pregunta.

344
00:15:02,990 --> 00:15:05,040
A la meitat esquerra, tinc
encara té el número 2.

345
00:15:05,040 --> 00:15:07,490
A la meitat dreta,
Tinc el número 3.

346
00:15:07,490 --> 00:15:08,930
Quina he vull triar?

347
00:15:08,930 --> 00:15:11,760
Per descomptat, el número 2 I
Ara notar els candidats

348
00:15:11,760 --> 00:15:13,620
són 4 a l'esquerra, 3 a la dreta.

349
00:15:13,620 --> 00:15:15,020
Anem, per descomptat, triar 3.

350
00:15:15,020 --> 00:15:18,020
Ara els candidats són 4 en
l'esquerra, 5 a la dreta.

351
00:15:18,020 --> 00:15:19,460
Nosaltres, per descomptat, vam triar 4.

352
00:15:19,460 --> 00:15:21,240
6 a l'esquerra, 5 a la dreta.

353
00:15:21,240 --> 00:15:22,730
Nosaltres, per descomptat, vam triar maig.

354
00:15:22,730 --> 00:15:25,020
6 a l'esquerra, 7 a la dreta.

355
00:15:25,020 --> 00:15:29,320
Triem 6, i després
triar 7, i després vam triar agost.

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

357
00:15:30,100 --> 00:15:34,370
>> Així que un gran nombre de paraules més tard,
s'han classificat aquesta llista de vuit elements

358
00:15:34,370 --> 00:15:38,450
en una llista d'un a vuit,
això està augmentant amb cada pas,

359
00:15:38,450 --> 00:15:40,850
però quant de temps ho va fer
que ens porta a fer això.

360
00:15:40,850 --> 00:15:43,190
Bé, jo he deliberadament
coses establertes il·lustrat

361
00:15:43,190 --> 00:15:46,330
aquí, així que podem tipus de
veure o apreciar la divisió

362
00:15:46,330 --> 00:15:49,060
en la conquesta que està passant.

363
00:15:49,060 --> 00:15:52,830
>> De fet, si un mira cap enrere en el vetlla,
He deixat totes aquestes línies de punts

364
00:15:52,830 --> 00:15:55,660
en marcadors de posició, vostè pot,
classe de, vegi, en ordre invers,

365
00:15:55,660 --> 00:15:58,800
si vostè espècie de mirar cap enrere en
la història ara, la meva llista original

366
00:15:58,800 --> 00:16:00,250
és, per descomptat, de grandària 8.

367
00:16:00,250 --> 00:16:03,480
I a continuació, prèviament, estava
es tracta de dues llistes de mida 4,

368
00:16:03,480 --> 00:16:08,400
i després quatre llistes de mida 2,
i després 8 llistes de tamany 1.

369
00:16:08,400 --> 00:16:10,151
>> Llavors, què fa això,
classe de, recordar-?

370
00:16:10,151 --> 00:16:11,858
Bé, de fet, qualsevol de
els algoritmes que hem

371
00:16:11,858 --> 00:16:14,430
mirat fins al moment en què
dividir i dividir i dividir,

372
00:16:14,430 --> 00:16:19,500
seguir tenint les coses de nou, i
Novament, els resultats en aquesta idea general.

373
00:16:19,500 --> 00:16:23,100
I així hi ha alguna cosa
logarítmica passant aquí.

374
00:16:23,100 --> 00:16:26,790
I no és prou registre de n, però
hi ha un component logarítmica

375
00:16:26,790 --> 00:16:28,280
al que acabem de fer.

376
00:16:28,280 --> 00:16:31,570
>> Ara anem a considerar la forma en que realment és.

377
00:16:31,570 --> 00:16:34,481
Així que ingressi de n, de nou va ser
un gran temps de funcionament,

378
00:16:34,481 --> 00:16:36,980
quan vam fer una cosa semblant
recerca binària, ja que ara anomenem,

379
00:16:36,980 --> 00:16:40,090
l'estratègia de divideix i venceràs
a través del qual ens trobem Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Ara tècnicament.

381
00:16:41,020 --> 00:16:43,640
Això és log base 2 de n, fins i tot
encara que en la majoria de les classes de matemàtiques,

382
00:16:43,640 --> 00:16:45,770
10 és en general la base que vostè assumeix.

383
00:16:45,770 --> 00:16:48,940
Però científics de la computació gairebé sempre
pensar i parlar en termes de base 2,

384
00:16:48,940 --> 00:16:52,569
així que en general, només diem registre de
n, en lloc de logaritme en base 2 de n,

385
00:16:52,569 --> 00:16:55,110
però són exactament una i la
mateix en el món de l'ordinador

386
00:16:55,110 --> 00:16:57,234
ciència, i com un a part,
hi ha un factor constant

387
00:16:57,234 --> 00:17:01,070
diferència entre els dos, pel que és
discutible de totes maneres, per raons més formals.

388
00:17:01,070 --> 00:17:04,520
>> Però per ara, el que ens importa
sobre és aquest exemple.

389
00:17:04,520 --> 00:17:08,520
Així que anem a no prova amb l'exemple, però al
menys usar un exemple dels nombres

390
00:17:08,520 --> 00:17:10,730
a la mà com una comprovació de validesa, si es vol.

391
00:17:10,730 --> 00:17:14,510
Així que amb anterioritat la fórmula era la base de registre
2 de n, però el que és n en aquest cas.

392
00:17:14,510 --> 00:17:18,526
Vaig tenir n nombres originals, o agost
del nombre original específicament.

393
00:17:18,526 --> 00:17:20,359
Ara que ha estat una mica
temps, però estic bastant

394
00:17:20,359 --> 00:17:25,300
Segur que log base 2
del valor 8 és 3,

395
00:17:25,300 --> 00:17:29,630
i de fet, el que és bo d'això és
que el 3 és exactament el nombre de vegades

396
00:17:29,630 --> 00:17:33,320
que es pot dividir una llista
de longitud 8 una altra vegada, i una altra,

397
00:17:33,320 --> 00:17:36,160
i una altra, fins que un es queda
amb llistes de tot just el tamany 1.

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

399
00:17:36,660 --> 00:17:40,790
8 va a 4, passa a 2,
passa a 1, i això és

400
00:17:40,790 --> 00:17:43,470
reflecteix exactament això
imatge que teníem fa un moment.

401
00:17:43,470 --> 00:17:47,160
Així que una mica de seny comprovar d'on
el logaritme està realment involucrat.

402
00:17:47,160 --> 00:17:50,180
>> Així que ara, què més està involucrat aquí? n.

403
00:17:50,180 --> 00:17:53,440
Així notar que cada
temps jo ens vam dividir la llista,

404
00:17:53,440 --> 00:17:58,260
encara que en ordre invers a la història
aquí, encara estava fent n coses.

405
00:17:58,260 --> 00:18:02,320
Aquest pas fusió requeria que
Toco cadascun dels nombres,

406
00:18:02,320 --> 00:18:05,060
per tal de lliscar en
la seva ubicació adequada.

407
00:18:05,060 --> 00:18:10,760
Així que, encara que l'altura d'aquesta
diagrama és de la mida del registre n de n o 3,

408
00:18:10,760 --> 00:18:13,860
específicament, en altres paraules,
Vaig fer tres divisions aquí.

409
00:18:13,860 --> 00:18:18,800
Quant treball vaig fer horitzontalment
al llarg d'aquest gràfic cada vegada?

410
00:18:18,800 --> 00:18:21,110
>> Bé, ho vaig fer n passos de
treballar, perquè si tinc

411
00:18:21,110 --> 00:18:24,080
té quatre elements i quatre elements,
i necessito unir-los.

412
00:18:24,080 --> 00:18:26,040
He d'anar a través de
aquests quatre i aquests quatre,

413
00:18:26,040 --> 00:18:28,123
en última instància, per a fondre
de nou en vuit elements.

414
00:18:28,123 --> 00:18:32,182
Si per contra tinc vuit dits
per aquí, que no ho faig, i de vuit

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Si tinc
té quatre dits per aquí,

416
00:18:34,390 --> 00:18:37,380
que faré, quatre dits
aquí, que jo faig,

417
00:18:37,380 --> 00:18:40,590
llavors això és la mateixa
exemple, com abans, si ho faig

418
00:18:40,590 --> 00:18:44,010
té vuit dits encara que en
total, que puc classe de, fer ,.

419
00:18:44,010 --> 00:18:47,950
Exactament el que puc fer aquí,
llavors jo sap

420
00:18:47,950 --> 00:18:50,370
fusionar totes aquestes llistes
de tamany 1 junts.

421
00:18:50,370 --> 00:18:54,050
Però sens dubte he de mirar
en cada element d'exactament una vegada.

422
00:18:54,050 --> 00:18:59,640
Per tant l'altura d'aquest procés és log n,
l'amplada d'aquest procés, per així dir-ho,

423
00:18:59,640 --> 00:19:02,490
és N, així que el que sembla
tenir, en última instància, és

424
00:19:02,490 --> 00:19:06,470
una durada de mida n vegades log n.

425
00:19:06,470 --> 00:19:08,977
>> En altres paraules, hem dividit
la llista, registre n vegades,

426
00:19:08,977 --> 00:19:11,810
però cada vegada que ho vam fer, vam tenir
tocar cada un dels elements

427
00:19:11,810 --> 00:19:13,560
per tal de fusionar-
tots junts, que

428
00:19:13,560 --> 00:19:18,120
va ser n pas, de manera que tenim n vegades log n,
o com un científic de la computació diria,

429
00:19:18,120 --> 00:19:20,380
asimptòticament, que
seria la paraula gran

430
00:19:20,380 --> 00:19:22,810
per descriure la part superior
amb destinació en un temps de funcionament,

431
00:19:22,810 --> 00:19:28,010
ens estem quedant en una gran o
de log n temps, per així dir-ho.

432
00:19:28,010 --> 00:19:31,510
>> Ara bé, això és important, perquè
recorden el que van ser els temps de funcionament

433
00:19:31,510 --> 00:19:34,120
amb la bombolla de gènere, i la selecció
ordenar i ordenació per inserció,

434
00:19:34,120 --> 00:19:38,200
i fins i tot alguns altres que existeixen,
n al quadrat era on estàvem.

435
00:19:38,200 --> 00:19:39,990
I vostè pot, una mica, veure això aquí.

436
00:19:39,990 --> 00:19:45,720
Si n al quadrat és òbviament n vegades
n, però aquí tenim n vegades log n,

437
00:19:45,720 --> 00:19:48,770
i ja sabem per setmana
zero, que log n, la logarítmica,

438
00:19:48,770 --> 00:19:50,550
és millor que alguna cosa lineal.

439
00:19:50,550 --> 00:19:52,930
Després de tot, recordar la imatge
amb el vermell i el groc

440
00:19:52,930 --> 00:19:56,500
i les línies verdes que Drew, el
línia logarítmica verda era molt menor.

441
00:19:56,500 --> 00:20:00,920
I per tant, molt millor i més ràpid
que les línies grogues i vermelles rectes,

442
00:20:00,920 --> 00:20:05,900
n vegades log n és, de fet, millor
de n vegades n o n al quadrat.

443
00:20:05,900 --> 00:20:09,110
>> Així que sembla que tenim
identificat una combinació d'algorisme

444
00:20:09,110 --> 00:20:11,870
espècie que s'executa en molt
temps més ràpid, i de fet,

445
00:20:11,870 --> 00:20:16,560
per això, a principis d'aquesta setmana, quan
vam veure que contesa entre bombolles

446
00:20:16,560 --> 00:20:20,750
Ordena, ordenació per selecció, i fusionar
Ordena, ordenament per barreja molt, molt bestiar.

447
00:20:20,750 --> 00:20:23,660
I, en efecte, que ni tan sols esperar
d'ordenament de bombolla i ordenació per selecció

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

449
00:20:24,790 --> 00:20:27,410
>> Ara anem a prendre un altre pas
en aquest, des d'una mica més

450
00:20:27,410 --> 00:20:31,030
punt de vista formal, per si
cas, això ressona millor

451
00:20:31,030 --> 00:20:33,380
que l'alt nivell de discussió.

452
00:20:33,380 --> 00:20:34,880
Així que aquí està l'algoritme de nou.

453
00:20:34,880 --> 00:20:36,770
Preguntem-nos,
el que el temps d'execució

454
00:20:36,770 --> 00:20:39,287
és d'aquest algoritmes diferents passos?

455
00:20:39,287 --> 00:20:41,620
Anem a dividir a la primera
cas i el segon cas.

456
00:20:41,620 --> 00:20:46,280
L'IF i ELSE En el cas SI,
Si N és menor que 2, simplement tornar.

457
00:20:46,280 --> 00:20:47,580
Se sent com a constant de temps.

458
00:20:47,580 --> 00:20:50,970
És, alguna cosa així, com dos passos,
Si n és inferior a 2, i després tornar.

459
00:20:50,970 --> 00:20:54,580
Però com hem dit el dilluns
constant de temps, o de l'o 1,

460
00:20:54,580 --> 00:20:57,130
poden ser dos passos, tres
passos, fins i tot 1.000 passos.

461
00:20:57,130 --> 00:20:59,870
El que importa és que és
un nombre constant de passos.

462
00:20:59,870 --> 00:21:03,240
Així que el groc ressaltat pseudocodi
aquí s'executa en, ho anem a trucar,

463
00:21:03,240 --> 00:21:04,490
constant de temps.

464
00:21:04,490 --> 00:21:06,780
Així que de manera més formal, i
anem A-- aquest

465
00:21:06,780 --> 00:21:09,910
serà el grau en què ens
formalitzar aquest dret ara-- T de n,

466
00:21:09,910 --> 00:21:15,030
el temps d'execució d'un problema
que pren n tants com a entrada,

467
00:21:15,030 --> 00:21:19,150
és igual a gran o d'un,
Si N és inferior a 2.

468
00:21:19,150 --> 00:21:20,640
Així que és condicionat a això.

469
00:21:20,640 --> 00:21:24,150
Així que per ser clars, si n és menor que
2, tenim una llista molt curta, a continuació,

470
00:21:24,150 --> 00:21:29,151
el temps d'execució, T de n, on n és
1 o 0, en aquest cas molt específic,

471
00:21:29,151 --> 00:21:30,650
és només serà la constant de temps.

472
00:21:30,650 --> 00:21:32,691
Es va a prendre 1
pas, dos passos, el que sigui.

473
00:21:32,691 --> 00:21:33,950
És un nombre fix de passos.

474
00:21:33,950 --> 00:21:38,840
>> Així que la part sucosa segurament ha d'estar en
l'altre cas en el pseudocodi.

475
00:21:38,840 --> 00:21:40,220
El cas ELSE.

476
00:21:40,220 --> 00:21:44,870
Ordenar meitat esquerra dels elements, tipus adequat
mitjà d'elements, combinar meitats ordenades.

477
00:21:44,870 --> 00:21:46,800
Quant de temps dura cada un d'aquests passos prendre?

478
00:21:46,800 --> 00:21:49,780
Bé, si el funcionament
temps per ordenar n elements

479
00:21:49,780 --> 00:21:53,010
És a dir, anem a cridar molt
genèricament, T de n,

480
00:21:53,010 --> 00:21:55,500
a continuació, la classificació de l'esquerra
mitjà dels elements

481
00:21:55,500 --> 00:21:59,720
és a dir, una mena de, com dir,
T de n dividit per 2,

482
00:21:59,720 --> 00:22:03,000
i de la mateixa manera la classificació de la meitat dreta
d'elements és, alguna cosa així, com dient:

483
00:22:03,000 --> 00:22:06,974
T de n divideix 2, i després
la fusió de les meitats ordenats.

484
00:22:06,974 --> 00:22:08,890
Bé, si tinc alguna
nombre d'elements aquí,

485
00:22:08,890 --> 00:22:11,230
com quatre, i un nombre
d'elements que aquí, igual que 4,

486
00:22:11,230 --> 00:22:14,650
i he de combinar cada un d'aquests quatre
a, i cadascuna d'aquestes quatre a, un

487
00:22:14,650 --> 00:22:17,160
després de l'altra, de manera que
en última instància, tinc 8 elements.

488
00:22:17,160 --> 00:22:20,230
Se sent com que és gran o de n passos?

489
00:22:20,230 --> 00:22:23,500
Si tinc n dits i cadascuna de
ells ha de ser fusionat al seu lloc,

490
00:22:23,500 --> 00:22:25,270
això és com un altre n passos.

491
00:22:25,270 --> 00:22:27,360
>> Així que de fet formulaically,
podem expressar això,

492
00:22:27,360 --> 00:22:29,960
encara que una mica espantadís al principi
vista, però és una cosa

493
00:22:29,960 --> 00:22:31,600
que captura exactament aquesta lògica.

494
00:22:31,600 --> 00:22:35,710
El temps d'execució, T de n, si n
és més gran que o igual a 2.

495
00:22:35,710 --> 00:22:42,500
En aquest cas, el cas ELSE, és T de n
dividit per 2, a més de T de N dividit per 2,

496
00:22:42,500 --> 00:22:45,320
més gran o de n, alguns
nombre de passos lineal,

497
00:22:45,320 --> 00:22:51,630
potser exactament n, potser 2 cops
n, però és més o menys, l'ordre de n.

498
00:22:51,630 --> 00:22:54,060
Així que, també, és la forma en què pot
expressar aquesta formulaically.

499
00:22:54,060 --> 00:22:56,809
Ara no vas a saber això a menys
que ha gravat en la seva ment,

500
00:22:56,809 --> 00:22:58,710
o busqueu-les al
llom d'un llibre de text, que

501
00:22:58,710 --> 00:23:00,501
podria tenir una mica
full de trucs al final,

502
00:23:00,501 --> 00:23:03,940
però això és, de fet, va
ens donen una gran o de n log n,

503
00:23:03,940 --> 00:23:06,620
perquè la recurrència que
que estem veient aquí a la pantalla,

504
00:23:06,620 --> 00:23:09,550
si realment ho va fer a terme, amb
un nombre infinit d'exemples,

505
00:23:09,550 --> 00:23:13,000
o ho vas fer formulaically, ho faria
veure que això, perquè aquesta fórmula

506
00:23:13,000 --> 00:23:17,100
si mateix és recursiu amb t de
n per alguna cosa a la dreta,

507
00:23:17,100 --> 00:23:21,680
i t de n per l'esquerra, això pot
en realitat ser expressada, en última instància,

508
00:23:21,680 --> 00:23:24,339
tan gran de costat n log n.

509
00:23:24,339 --> 00:23:26,130
Si no està convençut, això és
bé per ara, només

510
00:23:26,130 --> 00:23:28,960
pren en la fe, que és, de fet,
el que condueix a la recurrència,

511
00:23:28,960 --> 00:23:31,780
però això és només una mica més d'un
enfocament matemàtic a la recerca

512
00:23:31,780 --> 00:23:36,520
en el moment d'execució de la fusió espècie
basat en el seu pseudocodi sol.

513
00:23:36,520 --> 00:23:39,030
>> Ara anem a fer una mica d'un
respir de tot això,

514
00:23:39,030 --> 00:23:41,710
i fer una ullada a una
certa exsenador, qui

515
00:23:41,710 --> 00:23:44,260
podria semblar una mica familiar,
qui es va asseure amb Eric de Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, fa algun temps, per a una entrevista
a l'escenari, davant d'un munt

517
00:23:48,410 --> 00:23:53,710
de les persones, parlar en última instància sobre
un tema, que és bastant ja familiar.

518
00:23:53,710 --> 00:23:54,575
Anem a fer una ullada.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Ara el senador,
vostè està aquí a Google,

521
00:24:03,890 --> 00:24:09,490
i m'agrada pensar en el
presidència com una entrevista de treball.

522
00:24:09,490 --> 00:24:11,712
Ara és difícil aconseguir una feina com a president.

523
00:24:11,712 --> 00:24:12,670
PRESIDENT OBAMA: Correcte.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: I tu ets
va a fer [inaudible] ara.

525
00:24:13,940 --> 00:24:15,523
També és difícil d'aconseguir una feina a Google.

526
00:24:15,523 --> 00:24:17,700
PRESIDENT OBAMA: Correcte.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Tenim preguntes,
i li demanem a les nostres preguntes dels candidats,

528
00:24:21,330 --> 00:24:24,310
i aquest és de Larry Schwimmer.

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

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: Què?

531
00:24:27,005 --> 00:24:28,130
Vostès pensen que estic fent broma?

532
00:24:28,130 --> 00:24:30,590
És just aquí.

533
00:24:30,590 --> 00:24:33,490
Quina és la forma més eficient de
ordenar un milió 32 bits sencers?

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

535
00:24:37,560 --> 00:24:38,979
>> PRESIDENT OBAMA: Bueno--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: En ocasions,
potser em sento, maybe--

537
00:24:41,020 --> 00:24:42,750
PRESIDENT OBAMA: No, no,
no, no, no, jo think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Això no és it--

539
00:24:43,240 --> 00:24:45,430
PRESIDENT OBAMA: I
pensar, crec que la bombolla

540
00:24:45,430 --> 00:24:46,875
tipus seria el camí equivocat.

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

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Anem.

543
00:24:50,535 --> 00:24:52,200
Qui li va dir això?

544
00:24:52,200 --> 00:24:54,020
D'ACORD.

545
00:24:54,020 --> 00:24:55,590
Jo no vaig fer la informàtica en--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDENT OBAMA: Tenim
van donar els nostres espies en aquest país.

547
00:24:58,986 --> 00:24:59,860
PROFESSOR: Molt bé.

548
00:24:59,860 --> 00:25:03,370
Anem a deixar darrere de nosaltres ara
món teòric d'algoritmes

549
00:25:03,370 --> 00:25:06,520
en l'anàlisi asimptòtic
dels mateixos, i tornar a alguns temes

550
00:25:06,520 --> 00:25:09,940
des de la setmana zero i un, i inici
per eliminar algunes rodes d'entrenament,

551
00:25:09,940 --> 00:25:10,450
si es vol.

552
00:25:10,450 --> 00:25:13,241
Així que vostè realment entén
en última instància, a partir de zero, el que és

553
00:25:13,241 --> 00:25:16,805
passant per sota de la campana, quan
escriure, compilar i executar programes.

554
00:25:16,805 --> 00:25:19,680
Recordem, en particular, que es tractava de
el primer programa en C miràvem,

555
00:25:19,680 --> 00:25:22,840
un programa canònica, simple
de tipus, en termes relatius,

556
00:25:22,840 --> 00:25:24,620
on, imprimeix, Hello World.

557
00:25:24,620 --> 00:25:27,610
I recordo que li vaig dir, el procés
que el codi font passa a través de

558
00:25:27,610 --> 00:25:28,430
és exactament això.

559
00:25:28,430 --> 00:25:31,180
Vostè pren el seu codi font, passa
a través d'un compilador, com Clang,

560
00:25:31,180 --> 00:25:34,650
i fora ve codi objecte, que
podria tenir aquest aspecte, zeros i uns

561
00:25:34,650 --> 00:25:37,880
que la CPU de l'ordinador, el centre
unitat de processament o el cervell,

562
00:25:37,880 --> 00:25:39,760
en última instància, entén.

563
00:25:39,760 --> 00:25:42,460
>> Resulta que aquesta és una
mica d'una simplificació excessiva,

564
00:25:42,460 --> 00:25:44,480
que ara estem en un
posició de separar

565
00:25:44,480 --> 00:25:46,720
per entendre el que realment ha estat
passant per sota de la campana

566
00:25:46,720 --> 00:25:48,600
cada vegada que s'executa
Clang, o més generalment,

567
00:25:48,600 --> 00:25:53,040
cada vegada que realitzi un programa,
utilitzant Marca i CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
En particular, coses per l'estil
aquest es genera primer,

569
00:25:56,760 --> 00:25:58,684
la primera vegada que compila el programa.

570
00:25:58,684 --> 00:26:00,600
En altres paraules, quan es
portar al seu codi font

571
00:26:00,600 --> 00:26:04,390
i compilar-lo, ¿què és primer
sent enviada per Clang

572
00:26:04,390 --> 00:26:06,370
és alguna cosa conegut com codi assemblador.

573
00:26:06,370 --> 00:26:08,990
I, de fet, es veu exactament com aquest.

574
00:26:08,990 --> 00:26:11,170
>> Vaig córrer una ordre al
línia d'ordres anterior.

575
00:26:11,170 --> 00:26:16,260
Hola.c Clang capitals tauler s,
i això crea un arxiu

576
00:26:16,260 --> 00:26:19,490
per a mi anomenats hello.s,
dins dels quals eren exactament

577
00:26:19,490 --> 00:26:22,290
aquests continguts, i una mica més
dalt i una mica més avall,

578
00:26:22,290 --> 00:26:25,080
però m'he posat la més sucosa
informació aquí, a la pantalla.

579
00:26:25,080 --> 00:26:29,190
I si et fixes bé, veuràs
almenys un parell de paraules clau familiars.

580
00:26:29,190 --> 00:26:31,330
Tenim principal a la part superior.

581
00:26:31,330 --> 00:26:35,140
Hem printf al centre.

582
00:26:35,140 --> 00:26:38,670
I també tenim hola món
barra invertida n entre cometes baix baix.

583
00:26:38,670 --> 00:26:42,450
>> I tota la resta aquí
és molt instruccions de baix nivell

584
00:26:42,450 --> 00:26:45,500
que la CPU de l'ordinador entén.

585
00:26:45,500 --> 00:26:50,090
Instruccions de CPU que es mouen de memòria
voltant, que les cadenes de càrrega de la memòria,

586
00:26:50,090 --> 00:26:52,750
i en última instància, d'impressió
coses a la pantalla.

587
00:26:52,750 --> 00:26:56,780
Ara el que passa encara que després
es genera el codi de muntatge?

588
00:26:56,780 --> 00:26:59,964
En última instància, ho fa, de fet,
Encara generar codi objecte.

589
00:26:59,964 --> 00:27:02,630
Però els passos que tenen realment
estat succeint sota de la campana

590
00:27:02,630 --> 00:27:04,180
mirar una mica de la mateixa família.

591
00:27:04,180 --> 00:27:08,390
El codi font es converteix en codi assemblador,
que després es converteix en codi objecte,

592
00:27:08,390 --> 00:27:11,930
i les paraules clau aquí és que,
en compilar el codi font,

593
00:27:11,930 --> 00:27:16,300
terme ve codi assemblador, i després
al col·locar el seu codi en assemblador,

594
00:27:16,300 --> 00:27:17,800
terme ve codi objecte.

595
00:27:17,800 --> 00:27:20,360
>> Ara Clang és super sofisticat,
com molts dels compiladors,

596
00:27:20,360 --> 00:27:23,151
i ho fa de tots aquests passos
junts, i no necessàriament

597
00:27:23,151 --> 00:27:25,360
sortida de qualsevol intermedi
arxius que encara es poden veure.

598
00:27:25,360 --> 00:27:28,400
Simplement compila les coses,
que és el terme general que

599
00:27:28,400 --> 00:27:30,000
descriu tot aquest procés.

600
00:27:30,000 --> 00:27:32,000
Però si realment vols
per ser concret, no hi ha

601
00:27:32,000 --> 00:27:34,330
molt més que fer allà també.

602
00:27:34,330 --> 00:27:38,860
>> Però també considerarem ara que fins i tot
aquest programa super simple, hello.c,

603
00:27:38,860 --> 00:27:40,540
anomenat una funció.

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

605
00:27:41,870 --> 00:27:46,900
Però jo no vaig escriure printf, de fet,
que ve amb c, per així dir-ho.

606
00:27:46,900 --> 00:27:51,139
És un recordatori que la funció és
declarada en io.h estàndard, que

607
00:27:51,139 --> 00:27:53,180
és un arxiu de capçalera, que
és un tema que va en realitat

608
00:27:53,180 --> 00:27:55,780
submergir-se en més profunditat en poc temps.

609
00:27:55,780 --> 00:27:58,000
No obstant això, un arxiu de capçalera és
normalment acompanyats

610
00:27:58,000 --> 00:28:02,920
per un arxiu de codi, arxiu de codi font, per la qual
de la mateixa manera que hi ha io.h. estàndard

611
00:28:02,920 --> 00:28:05,930
>> Fa algun temps, algú,
o d'algú, també va escriure

612
00:28:05,930 --> 00:28:11,040
un arxiu anomenat io.c norma, en
que les definicions reals,

613
00:28:11,040 --> 00:28:15,220
o implementacions de printf,
i raïms d'altres funcions,

614
00:28:15,220 --> 00:28:16,870
són en realitat escrit.

615
00:28:16,870 --> 00:28:22,140
Així que tenint en compte que, si tenim en compte que té
aquí a l'esquerra, hello.c, que quan

616
00:28:22,140 --> 00:28:26,250
compilat, ens dóna hello.s, fins i tot si
Clang no molesta estalvi en un lloc

617
00:28:26,250 --> 00:28:31,360
podem veure-ho, i que el codi de muntatge
obté acoblament en hello.o, que

618
00:28:31,360 --> 00:28:34,630
és, de fet, el nom per defecte
donat cada vegada que es compila la font

619
00:28:34,630 --> 00:28:39,350
codificar en codi objecte, però no són
a punt per executar-però,

620
00:28:39,350 --> 00:28:41,460
perquè un altre pas
ha de succeir, i té

621
00:28:41,460 --> 00:28:44,440
vingut succeint en els últims
setmana, potser sense saber-ho tu.

622
00:28:44,440 --> 00:28:47,290
>> Específicament en algun lloc
en CS50 IDE, i això,

623
00:28:47,290 --> 00:28:49,870
també, serà una mica d'un
simplificació excessiva per un moment,

624
00:28:49,870 --> 00:28:54,670
hi ha, o va ser en un altre temps,
un arxiu anomenat io.c estàndard,

625
00:28:54,670 --> 00:28:58,440
que algú compilat en
io.s estàndard o l'equivalent,

626
00:28:58,440 --> 00:29:02,010
que algú acobla llavors
en io.o estàndard,

627
00:29:02,010 --> 00:29:04,600
o resulta en una
lleugerament diferent arxiu

628
00:29:04,600 --> 00:29:07,220
format que pot tenir un diferent
extensió d'arxiu per complet,

629
00:29:07,220 --> 00:29:11,720
però en teoria i conceptualment, exactament
aquests passos van haver de passar en alguna forma.

630
00:29:11,720 --> 00:29:14,060
És a dir, que ara
quan estic escrivint un programa,

631
00:29:14,060 --> 00:29:17,870
hello.c, que amb prou feines diu, hola món,
i estic fent servir el codi d'una altra persona

632
00:29:17,870 --> 00:29:22,480
com printf, que era una vegada un
temps, en un arxiu anomenat io.c estàndard,

633
00:29:22,480 --> 00:29:26,390
llavors d'alguna manera he de portar al meu
codi objecte, les meves zeros i uns,

634
00:29:26,390 --> 00:29:29,260
i l'objecte d'aquesta persona
codi, o zeros i uns,

635
00:29:29,260 --> 00:29:34,970
i d'alguna manera enllaçar junts en
un arxiu final, anomenada hola, que

636
00:29:34,970 --> 00:29:38,070
té tots els zeros i
els de la meva funció principal,

637
00:29:38,070 --> 00:29:40,830
i tots els zeros
i els de printf.

638
00:29:40,830 --> 00:29:44,900
>> I, en efecte, que el passat procés és
trucada, la vinculació del seu codi objecte.

639
00:29:44,900 --> 00:29:47,490
La sortida dels quals
és un arxiu executable.

640
00:29:47,490 --> 00:29:49,780
Així que per ser justos, al
final del dia, res

641
00:29:49,780 --> 00:29:52,660
ha canviat des de la setmana un, quan
primer va començar compilar programes.

642
00:29:52,660 --> 00:29:55,200
De fet, tot això ha estat
passant per sota de la caputxa,

643
00:29:55,200 --> 00:29:57,241
però ara estem en una posició
on puguem realment

644
00:29:57,241 --> 00:29:58,794
esmicolar aquests diversos passos.

645
00:29:58,794 --> 00:30:00,710
I, de fet, al final
del dia, encara estem

646
00:30:00,710 --> 00:30:04,480
esquerra amb zeros i uns, que
és en realitat un gran segue ara

647
00:30:04,480 --> 00:30:08,620
a una altra capacitat de C, que
nosaltres no hem hagut d'aprofitar més probable

648
00:30:08,620 --> 00:30:11,250
fins a la data, coneguda com a operadors bit a bit.

649
00:30:11,250 --> 00:30:15,220
En altres paraules, fins al moment, en qualsevol moment ens hem
tractat amb dades en C o variables en C,

650
00:30:15,220 --> 00:30:17,660
hem tingut coses com
caràcters i carrosses i complements

651
00:30:17,660 --> 00:30:21,990
i anhela i dobles i similars, però
tots aquests són almenys vuit bits.

652
00:30:21,990 --> 00:30:25,550
Hem això mai ser capaços de
manipular bits individuals,

653
00:30:25,550 --> 00:30:28,970
tot i que un bit individual, ens
saben, pot representar un 0 i un 1.

654
00:30:28,970 --> 00:30:32,640
Ara resulta que en C,
pot obtenir accés als bits individuals,

655
00:30:32,640 --> 00:30:35,530
si coneix la sintaxi,
amb la qual per arribar-hi.

656
00:30:35,530 --> 00:30:38,010
>> Així que anem a fer una ullada
a operadors bit a bit.

657
00:30:38,010 --> 00:30:41,700
Així fotografiats aquí hi ha alguns símbols que
hem, classe de, classe de, vist abans.

658
00:30:41,700 --> 00:30:45,580
Veig una i comercial, vertical
bar, i alguns altres també,

659
00:30:45,580 --> 00:30:49,430
i recordar que signe ampersand
és una cosa que hem vist abans.

660
00:30:49,430 --> 00:30:54,060
L'operador lògic AND, on has
dos d'ells junts, o la lògica OR

661
00:30:54,060 --> 00:30:56,300
operador, en la qual
tenir dues barres verticals.

662
00:30:56,300 --> 00:31:00,550
Operadors bit a bit, que anem a
veure operar en bits de forma individual,

663
00:31:00,550 --> 00:31:03,810
només ha d'utilitzar un sol signe, un
barra vertical única, el símbol d'intercalació

664
00:31:03,810 --> 00:31:06,620
que ve a continuació, la petita
accent i, després a l'esquerra

665
00:31:06,620 --> 00:31:08,990
suport deixar suport o
claudàtor dret escaire dret.

666
00:31:08,990 --> 00:31:10,770
Cadascun d'ells tenen diferents significats.

667
00:31:10,770 --> 00:31:11,950
>> De fet, anem a fer una ullada.

668
00:31:11,950 --> 00:31:16,560
Anem a la vella escola d'avui, i l'ús
una pantalla tàctil d'antany,

669
00:31:16,560 --> 00:31:18,002
conegut com un tauler blanc.

670
00:31:18,002 --> 00:31:19,710
I aquest tauler blanc
ens va a permetre

671
00:31:19,710 --> 00:31:27,360
per expressar alguns símbols bastant simples,
o més aviat algunes fórmules bastant simples,

672
00:31:27,360 --> 00:31:29,560
que podem llavors en última instància,
palanquejament, per tal

673
00:31:29,560 --> 00:31:33,230
accedir a la persona
bits dins d'un programa C.

674
00:31:33,230 --> 00:31:34,480
En altres paraules, farem això.

675
00:31:34,480 --> 00:31:37,080
Primer parlem de
moment en signe,

676
00:31:37,080 --> 00:31:39,560
que és l'operador AND.

677
00:31:39,560 --> 00:31:42,130
En altres paraules, això és
un operador que permet

678
00:31:42,130 --> 00:31:45,930
que jo tingui una variable de l'esquerra
Típicament, i una variable de la dreta,

679
00:31:45,930 --> 00:31:50,640
o un valor individual, que si I
junts, em dóna un resultat final.

680
00:31:50,640 --> 00:31:51,560
Llavors, què puc dir?

681
00:31:51,560 --> 00:31:54,840
Si en un programa, que té una variable
que emmagatzema un d'aquests valors,

682
00:31:54,840 --> 00:31:58,000
o anem a mantenir simple, i just
escrigui zeros i uns de forma individual,

683
00:31:58,000 --> 00:32:00,940
així és com funciona l'operador de signe.

684
00:32:00,940 --> 00:32:06,400
0 0 I comercial serà igual a 0.

685
00:32:06,400 --> 00:32:07,210
Ara per què és això?

686
00:32:07,210 --> 00:32:09,291
>> És molt similar a
Expressions booleanes,

687
00:32:09,291 --> 00:32:10,540
que hem discutit fins ara.

688
00:32:10,540 --> 00:32:15,800
Si vostè pensa que després de tot, el 0 és
falsa, 0 és falsa, falsa i fals

689
00:32:15,800 --> 00:32:18,720
és, com hem discutit
lògicament, també falsa.

690
00:32:18,720 --> 00:32:20,270
Així obtenim 0 aquí també.

691
00:32:20,270 --> 00:32:24,390
Si vostè pren 0 ampersand
1, així que, també,

692
00:32:24,390 --> 00:32:29,890
serà 0, perquè per això
l'expressió de l'esquerra per ser veritat o 1,

693
00:32:29,890 --> 00:32:32,360
que hauria de ser veritable i cert.

694
00:32:32,360 --> 00:32:36,320
Però aquí tenim falsa
i veritable, o 0 i 1.

695
00:32:36,320 --> 00:32:42,000
Ara, de nou, si tenim 1 ampersand
0, això també serà 0,

696
00:32:42,000 --> 00:32:47,240
i si tenim 1 ampersand 1,
finalment tenim un 1 bit.

697
00:32:47,240 --> 00:32:50,340
En altres paraules, no estem fent
alguna cosa interessant amb aquest operador

698
00:32:50,340 --> 00:32:51,850
de moment, aquest operador signe.

699
00:32:51,850 --> 00:32:53,780
És l'operador AND.

700
00:32:53,780 --> 00:32:57,290
Però aquests són els ingredients
a través del qual podem fer

701
00:32:57,290 --> 00:32:59,240
coses interessants, com aviat veurem.

702
00:32:59,240 --> 00:33:02,790
>> Ara anem a veure només l'única
barra vertical per aquí a la dreta.

703
00:33:02,790 --> 00:33:06,710
Si tinc un bit 0 i jo
O amb el bit a bit

704
00:33:06,710 --> 00:33:11,030
Operador OR, un altre bit 0,
això va a donar-me 0.

705
00:33:11,030 --> 00:33:17,540
Si prenc un bit 0 i O amb
un bit 1, a continuació, vaig a aconseguir 1.

706
00:33:17,540 --> 00:33:19,830
I, de fet, només per
claredat, em va deixar anar cap enrere,

707
00:33:19,830 --> 00:33:23,380
de manera que els meus barres verticals
no es confonen amb 1 de.

708
00:33:23,380 --> 00:33:26,560
Permetin-me reescriure tots
mi 1 és una mica més

709
00:33:26,560 --> 00:33:32,700
clarament, de manera que ens veiem la propera, si
han gener 1 o 0, això serà un 1,

710
00:33:32,700 --> 00:33:39,060
i si tinc un 1 O 1, que,
també, va ser un 1.

711
00:33:39,060 --> 00:33:42,900
Així es pot veure, lògicament, que l'O
operador es comporta de manera molt diferent.

712
00:33:42,900 --> 00:33:48,070
Això em dóna 0 O 0 0 em dóna, però
qualsevol altra combinació em dóna 1.

713
00:33:48,070 --> 00:33:52,480
Sempre que tinc un 1 al
fórmula, el resultat serà 1.

714
00:33:52,480 --> 00:33:55,580
>> En contrast amb la I
operador, el signe,

715
00:33:55,580 --> 00:34:00,940
només si tinc dos d'1 en la
equació, puc realment aconseguir 1 gen.

716
00:34:00,940 --> 00:34:02,850
Ara hi ha alguns altres
operadors també.

717
00:34:02,850 --> 00:34:04,810
Un d'ells és una mica més complicat.

718
00:34:04,810 --> 00:34:07,980
Així que permetin-me anar endavant i esborrar
això per alliberar espai.

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

720
00:34:13,020 --> 00:34:16,460
I anem a fer una ullada a la
símbol d'intercalació, per un moment.

721
00:34:16,460 --> 00:34:18,210
Això és típicament un
caràcter que es pugui escriure

722
00:34:18,210 --> 00:34:21,420
en la seva celebració de teclat Maj i
llavors un dels números sobre de la dels EUA

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

724
00:34:22,250 --> 00:34:26,190
>> Així que aquesta és l'exclusiva
Operador OR, OR exclusiva.

725
00:34:26,190 --> 00:34:27,790
Així que acabem de veure l'operador OR.

726
00:34:27,790 --> 00:34:29,348
Aquest és l'exclusiu operador OR.

727
00:34:29,348 --> 00:34:30,639
Què és realment la diferència?

728
00:34:30,639 --> 00:34:34,570
Bé anem a veure a la fórmula,
i utilitzar això com a ingredients en última instància.

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

730
00:34:37,690 --> 00:34:39,650
Vaig a dir és sempre 0.

731
00:34:39,650 --> 00:34:41,400
Aquesta és la definició de XOR.

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

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 serà 1,
i 1 XOR 1 serà?

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

735
00:34:59,890 --> 00:35:00,520
O no?

736
00:35:00,520 --> 00:35:01,860
No ho sé.

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

738
00:35:02,810 --> 00:35:04,700
Ara, què està passant aquí?

739
00:35:04,700 --> 00:35:06,630
Bé pensar en el
nom d'aquest operador.

740
00:35:06,630 --> 00:35:09,980
Exclusiva O, de manera que el
nom, tipus de, suggereix,

741
00:35:09,980 --> 00:35:13,940
la resposta només serà
un 1 si les entrades són exclusius,

742
00:35:13,940 --> 00:35:15,560
exclusivament diferent.

743
00:35:15,560 --> 00:35:18,170
Així que aquí les entrades són els
mateix, de manera que la sortida és 0.

744
00:35:18,170 --> 00:35:20,700
Aquí les entrades són la
mateix, de manera que la sortida és 0.

745
00:35:20,700 --> 00:35:25,640
Aquí hi ha les sortides són diferents,
són exclusius, de manera que la sortida es 1.

746
00:35:25,640 --> 00:35:28,190
Així que és molt similar a la
I, és molt similar,

747
00:35:28,190 --> 00:35:32,760
o millor dit, que és molt similar a la
O, però només de manera exclusiva.

748
00:35:32,760 --> 00:35:36,210
Aquest ja no és un 1,
perquè tenim dos d'1,

749
00:35:36,210 --> 00:35:38,621
i no exclusivament, només un d'ells.

750
00:35:38,621 --> 00:35:39,120
Tot bé.

751
00:35:39,120 --> 00:35:40,080
¿I els altres?

752
00:35:40,080 --> 00:35:44,220
Bé, la titlla, per la seva banda, és
realment agradable i senzilla, gràcies a Déu.

753
00:35:44,220 --> 00:35:46,410
I aquest és un unari
operador, el que significa

754
00:35:46,410 --> 00:35:50,400
que s'aplica a una sola entrada,
1 operant, per així dir-ho.

755
00:35:50,400 --> 00:35:51,800
No a una esquerra i una dreta.

756
00:35:51,800 --> 00:35:56,050
En altres paraules, si vostè pren titlla de
0, la resposta serà l'oposada.

757
00:35:56,050 --> 00:35:59,710
I si es pren titlla d'1, el
resposta allà serà l'oposat.

758
00:35:59,710 --> 00:36:02,570
Així que l'operador accent és
una forma de negar una mica,

759
00:36:02,570 --> 00:36:06,000
o voltejar una mica de
0 a 1, o de 1 a 0.

760
00:36:06,000 --> 00:36:09,820
>> I això ens deixa finalment
amb només dos operadors finals,

761
00:36:09,820 --> 00:36:13,840
L'anomenat desviació a l'esquerra, i la
l'anomenat operador de desplaçament a la dreta.

762
00:36:13,840 --> 00:36:16,620
Fem una ullada a com els treballs.

763
00:36:16,620 --> 00:36:20,780
L'operador de desplaçament a l'esquerra, per escrit
amb dues esquadres per l'estil,

764
00:36:20,780 --> 00:36:22,110
funciona com segueix.

765
00:36:22,110 --> 00:36:27,390
Si la meva entrada, o el meu operant, a l'esquerra
operador de desplaçament és, senzillament, un 1.

766
00:36:27,390 --> 00:36:33,750
I llavors dic que l'ordinador
desviació a l'esquerra que 1, diuen 07:00 llocs,

767
00:36:33,750 --> 00:36:37,150
el resultat és com si
prendre aquest 1, i moure-

768
00:36:37,150 --> 00:36:40,160
07:00 llocs més a la
esquerra, i per defecte,

769
00:36:40,160 --> 00:36:42,270
anem a suposar que
l'espai a la dreta

770
00:36:42,270 --> 00:36:44,080
va ser emplenat amb zeros.

771
00:36:44,080 --> 00:36:50,316
En altres paraules, 1 esquerra torn juliol va
que em donés que 1, seguit d'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
Així que en certa manera, li permet
prendre un nombre petit com 1,

774
00:36:57,380 --> 00:37:00,740
i clarament que sigui molt
molt, molt més gran d'aquesta manera,

775
00:37:00,740 --> 00:37:06,460
però en realitat estem anant a veure
enfocaments més intel·ligents perquè

776
00:37:06,460 --> 00:37:08,080
en el seu lloc, així,

777
00:37:08,080 --> 00:37:08,720
>> Tot bé.

778
00:37:08,720 --> 00:37:10,060
Això és tot per a la setmana tres.

779
00:37:10,060 --> 00:37:11,400
Ens veiem la propera vegada.

780
00:37:11,400 --> 00:37:12,770
Aquest va ser CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [REPRODUCCIÓ DE MÚSICA]

783
00:37:22,243 --> 00:37:25,766
>> ALTAVEU 1: Estava en el berenar
bar menjant un gelat amb xocolata calenta.

784
00:37:25,766 --> 00:37:28,090
Ho tenia tot a la cara.

785
00:37:28,090 --> 00:37:30,506
Porta que la xocolata com una barba

786
00:37:30,506 --> 00:37:31,756
ALTAVEU 2: Què estàs fent?

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

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

789
00:37:33,500 --> 00:37:36,800
>> ALTAVEU 2: Acabes de doble immersió?

790
00:37:36,800 --> 00:37:38,585
Fa doble submergit el xip.

791
00:37:38,585 --> 00:37:39,460
ALTAVEU 3: Perdoni.

792
00:37:39,460 --> 00:37:44,440
ALTAVEU 2: Vostè submergit el xip, que
va prendre un mos, i submergit de nou.

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

794
00:37:44,940 --> 00:37:48,440
ALTAVEU 2: Així que això és com posar
a la seva dreta la boca sencera en el dip.

795
00:37:48,440 --> 00:37:52,400
La propera vegada que vostè pren un xip,
simplement submergir una vegada, i acabar amb ella.

796
00:37:52,400 --> 00:37:53,890
>> ALTAVEU 3: Saps què, Dan?

797
00:37:53,890 --> 00:37:58,006
Vostè submergeix la forma en què desitja que recórrer.

798
00:37:58,006 --> 00:38:01,900
Vaig a mullar la manera que jo vull que recórrer.

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