1
00:00:00,000 --> 00:00:11,904
>> [Predvaja glasba]

2
00:00:11,904 --> 00:00:12,910
>> Profesor: V redu.

3
00:00:12,910 --> 00:00:16,730
To je CS50 in to je
Konec tritedenskega.

4
00:00:16,730 --> 00:00:20,230
Tako da smo danes tu, ne v Sanders
Gledališče, namesto v Weidner knjižnici.

5
00:00:20,230 --> 00:00:23,170
Znotraj katerega je studio
znan kot Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
ali pa bomo rekli, Studio H, ali se
smo say-- če ste uživali to šala,

7
00:00:28,310 --> 00:00:30,540
to je pravzaprav od
sošolec, Mark, online,

8
00:00:30,540 --> 00:00:32,420
ki je predlagal kar prek Twitterja.

9
00:00:32,420 --> 00:00:34,270
Zdaj, kaj je kul
da je tukaj v studiu

10
00:00:34,270 --> 00:00:38,410
je, da sem obkrožena s ti zeleno
stene, zelen zaslon ali chromakey,

11
00:00:38,410 --> 00:00:43,290
tako rekoč, kar pomeni, da CS50 je
produkcijska ekipa, nevede, da me

12
00:00:43,290 --> 00:00:47,380
zdaj, bi bilo dajanje
Najbolj me kjerkoli na svetu,

13
00:00:47,380 --> 00:00:48,660
za boljše ali slabše.

14
00:00:48,660 --> 00:00:51,800
>> Zdaj, kaj je pred nami, problem določiti
dve je v vaših rokah za ta teden,

15
00:00:51,800 --> 00:00:53,830
vendar s problemom nastavljena
tri ta prihajajoči teden,

16
00:00:53,830 --> 00:00:56,600
vas bo izpodbijala z
tako imenovana igra 15,

17
00:00:56,600 --> 00:00:58,960
stara uslugo stranka, ki
boste morda odpoklic prejema

18
00:00:58,960 --> 00:01:02,030
kot otrok, ki ima cel kup
številk, ki se lahko drsijo gor, dol,

19
00:01:02,030 --> 00:01:05,790
levo in desno, in tam je ena vrzel
v sestavljanki, v kateri ste

20
00:01:05,790 --> 00:01:07,840
lahko dejansko slide teh kosov sestavljanke.

21
00:01:07,840 --> 00:01:11,150
Konec koncev ste prejeli to
puzzle v neki napol naključnem vrstnem redu,

22
00:01:11,150 --> 00:01:12,940
in je cilj
ga rešiti, vrha do dna,

23
00:01:12,940 --> 00:01:16,310
leve proti desni, od enega
vse tja do 15.

24
00:01:16,310 --> 00:01:19,360
>> Na žalost, izvajanje
boste imeli pri roki

25
00:01:19,360 --> 00:01:21,590
se bo programska oprema
temelji, ne fizično.

26
00:01:21,590 --> 00:01:25,280
Ste dejansko dogaja, da imajo za pisanje
koda, s katero študent ali uporabnik lahko

27
00:01:25,280 --> 00:01:26,760
igrajo igro 15.

28
00:01:26,760 --> 00:01:29,030
In v resnici, v hacker
izdaja igri 15,

29
00:01:29,030 --> 00:01:32,155
boste izziv za izvajanje,
ne samo igranje te stare šole

30
00:01:32,155 --> 00:01:35,010
Igra, ampak Reševanje
nje, izvajanje način boga,

31
00:01:35,010 --> 00:01:38,280
tako rekoč, da dejansko
rešuje uganko za človeka,

32
00:01:38,280 --> 00:01:41,080
tako da jim s pridihom,
po namigu, po navdihu.

33
00:01:41,080 --> 00:01:42,280
Torej, več o tem naslednji teden.

34
00:01:42,280 --> 00:01:43,720
Ampak to je tisto, kar je pred nami.

35
00:01:43,720 --> 00:01:47,610
>> Za zdaj opozarjajo, da je v začetku tega tedna
smo imeli to Cliffhanger, če hočete,

36
00:01:47,610 --> 00:01:52,560
pri čemer je najboljše, kar so počeli sortiranje
pametno je bila zgornja meja velik o n

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

38
00:01:53,210 --> 00:01:56,520
Z drugimi besedami, bubble razvrščanje,
Izbor vrste, vstavljanje razvrščanje,

39
00:01:56,520 --> 00:01:59,120
vsi od njih, so različni
pri njihovem izvajanju,

40
00:01:59,120 --> 00:02:03,480
prenesena v N kvadrat teče
čas v zelo najslabšem primeru.

41
00:02:03,480 --> 00:02:06,010
In smo na splošno predpostavljamo, da
zelo najslabšem primeru za sortiranje

42
00:02:06,010 --> 00:02:08,814
je tista, ki vaše vhodi
so popolnoma nazaj.

43
00:02:08,814 --> 00:02:11,980
In res, je trajalo kar nekaj korakov
izvajati vsako od teh algoritmov.

44
00:02:11,980 --> 00:02:15,110
>> Zdaj pa na samem koncu razreda
odpoklic, smo primerjali mehurček vrste

45
00:02:15,110 --> 00:02:19,390
proti izbora vrste proti eni drugi
da smo poklicali zlivanjem v času,

46
00:02:19,390 --> 00:02:22,120
in predlagam, da se ob
Prednost lekcijo iz tedna

47
00:02:22,120 --> 00:02:24,060
nič, deli in vladaj.

48
00:02:24,060 --> 00:02:28,810
In nekako doseči nekakšno
logaritemsko čas teče na koncu,

49
00:02:28,810 --> 00:02:31,024
namesto nečesa
to je zgolj kvadratna.

50
00:02:31,024 --> 00:02:33,440
In to ni čisto logaritmična,
to je malo več kot to.

51
00:02:33,440 --> 00:02:36,520
Ampak, če se spomnimo iz razreda,
je bilo veliko, veliko hitreje.

52
00:02:36,520 --> 00:02:38,210
Oglejmo si oglejte kjer smo končali.

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

54
00:02:41,880 --> 00:02:45,370
>> Bubble vrsta versus izbor
nekako v primerjavi z zlivanjem.

55
00:02:45,370 --> 00:02:47,700
Zdaj pa oni vse teče, v
Teorija, istočasno.

56
00:02:47,700 --> 00:02:50,510
CPU teče z enako hitrostjo.

57
00:02:50,510 --> 00:02:54,990
Ampak lahko začutite, kako dolgočasno je to
se zelo hitro dogaja, da postanejo

58
00:02:54,990 --> 00:02:58,790
in kako hitro, ko smo injicirali
malo algoritmov Tedensko Zero je,

59
00:02:58,790 --> 00:03:00,080
bomo lahko pospešili stvari.

60
00:03:00,080 --> 00:03:01,630
>> Torej znamka nekako izgleda neverjetno.

61
00:03:01,630 --> 00:03:05,220
Kako ga lahko izkoristite, da
hitreje razvrstiti številke.

62
00:03:05,220 --> 00:03:07,140
No dajmo razmišljati nazaj
za sestavino, da smo

63
00:03:07,140 --> 00:03:10,380
moral nazaj v ničelno tednu, to je
išče nekoga v imeniku,

64
00:03:10,380 --> 00:03:12,380
in opozarjajo, da je
psevdokoda da smo predlagali,

65
00:03:12,380 --> 00:03:14,560
prek katerega bomo lahko ugotovili,
nekdo kot Mike Smith,

66
00:03:14,560 --> 00:03:16,310
pogledal malo kaj takega.

67
00:03:16,310 --> 00:03:20,820
>> Zdaj pa si oglejte še zlasti
na liniji 7 in 8, ter 10 in 11,

68
00:03:20,820 --> 00:03:25,240
ki povzročijo, da se zanka, pri čemer smo ohranili
vrača v vrstico 3 znova in znova,

69
00:03:25,240 --> 00:03:26,520
in spet.

70
00:03:26,520 --> 00:03:31,790
Vendar se je izkazalo, da smo si lahko ogledajo
Ta algoritem, tukaj v psevdokoda,

71
00:03:31,790 --> 00:03:33,620
malo bolj celostno.

72
00:03:33,620 --> 00:03:35,960
V bistvu, kaj iščem
na tukaj na zaslonu,

73
00:03:35,960 --> 00:03:41,180
je algoritem za iskanje
Mike Smith med nekaterimi niza strani.

74
00:03:41,180 --> 00:03:45,520
In res, da bi lahko to poenostavili
Algoritem v teh vrsticah 7 in 8,

75
00:03:45,520 --> 00:03:49,860
10 in 11, da samo to povem,
ki sem predstavljena tukaj v rumeno.

76
00:03:49,860 --> 00:03:52,210
Z drugimi besedami, če Mike
Smith je že v knjigi,

77
00:03:52,210 --> 00:03:55,004
nam ni treba navesti korak
za korakom, zdaj, kako iti ga našli.

78
00:03:55,004 --> 00:03:56,920
Nimamo navesti
da se vrnete na liniji 3,

79
00:03:56,920 --> 00:03:58,960
Zakaj ne bi samo namesto,
recimo, bolj splošno,

80
00:03:58,960 --> 00:04:01,500
iskanje Mike v
leva polovica knjige.

81
00:04:01,500 --> 00:04:03,960
>> Nasprotno pa, če je Mike
dejansko kasneje v knjigi,

82
00:04:03,960 --> 00:04:07,540
zakaj ne bomo samo citiram konec citata iskanje
za mikrofon desni polovici knjige.

83
00:04:07,540 --> 00:04:11,030
Z drugimi besedami, zakaj ne bomo samo
nekako punt, da sami pravijo,

84
00:04:11,030 --> 00:04:13,130
iskanje Mike v tem
podmnožica knjige,

85
00:04:13,130 --> 00:04:16,279
in pustite, da naše obstoječe
algoritem, da nam pove

86
00:04:16,279 --> 00:04:18,750
kako iskati za mikrofon
da je leva polovica knjige.

87
00:04:18,750 --> 00:04:20,750
Z drugimi besedami, naši
Algoritem deluje ali je

88
00:04:20,750 --> 00:04:24,670
telefonski imenik te debeline, od tega
debelina, ali katere koli debeline whatsoever.

89
00:04:24,670 --> 00:04:27,826
Tako smo lahko rekurzivno
opredeliti ta algoritem.

90
00:04:27,826 --> 00:04:29,950
Z drugimi besedami, na
Zaslon tukaj, je algoritem

91
00:04:29,950 --> 00:04:33,130
za iskanje Mike Smith
Med straneh telefonskega imenika.

92
00:04:33,130 --> 00:04:37,410
Torej, v skladu 7 in 10, dajmo
samo reči točno to.

93
00:04:37,410 --> 00:04:40,250
In uporabljam ta izraz trenutek
nazaj, in res, rekurzija

94
00:04:40,250 --> 00:04:42,450
je buzzword za zdaj,
in to je ta proces

95
00:04:42,450 --> 00:04:47,210
delaš nekaj cikličnega jih nekako
s pomočjo kode, ki jo že imate,

96
00:04:47,210 --> 00:04:49,722
in ga ponovno kliče,
in znova in znova.

97
00:04:49,722 --> 00:04:51,930
Zdaj se dogaja, da je pomembno
da smo nekako dno

98
00:04:51,930 --> 00:04:53,821
ven, in ne to, da neskončno dolgo.

99
00:04:53,821 --> 00:04:56,070
V nasprotnem primeru bomo
imajo res neskončno zanko.

100
00:04:56,070 --> 00:04:59,810
Ampak poglejmo, če lahko sposodim to idejo
iz rekurzije, spet delaš nekaj

101
00:04:59,810 --> 00:05:03,600
in znova in znova, rešiti
problem sortiranje preko spajanja

102
00:05:03,600 --> 00:05:05,900
razvrščanje, toliko bolj učinkovito.

103
00:05:05,900 --> 00:05:06,970
>> Zato sem vam zlivanjem.

104
00:05:06,970 --> 00:05:07,920
Oglejmo pogled.

105
00:05:07,920 --> 00:05:10,850
Torej, tukaj je psevdokoda, s
ki bi ga lahko izvaja sortiranje,

106
00:05:10,850 --> 00:05:12,640
uporabo tega algoritem imenovan zlivanjem.

107
00:05:12,640 --> 00:05:13,880
In to je zelo preprosto je to.

108
00:05:13,880 --> 00:05:15,940
Na vhodu n elementov,
z drugimi besedami, če ste

109
00:05:15,940 --> 00:05:18,830
glede n elementi in številke in
črke ali karkoli je vhod,

110
00:05:18,830 --> 00:05:22,430
če si dal n elementi, če
n je najmanj 2, samo vrnitev.

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

112
00:05:22,930 --> 00:05:26,430
Ker če je n manj kot 2, da
pomeni, da je moj seznam elementov

113
00:05:26,430 --> 00:05:30,446
je eden od velikosti 0 ali 1, in
v obeh nepomembnih primerih

114
00:05:30,446 --> 00:05:31,570
seznam je že urejeno.

115
00:05:31,570 --> 00:05:32,810
Če ne obstaja seznam, je to urejeno.

116
00:05:32,810 --> 00:05:35,185
In če je seznam dolžine
1, to je očitno razporejene.

117
00:05:35,185 --> 00:05:38,280
Torej algoritem potrebuje le
res kaj zanimivega,

118
00:05:38,280 --> 00:05:40,870
Če imamo dva ali več
elementi, ki nam.

119
00:05:40,870 --> 00:05:42,440
Zato si oglejmo čarobno takrat.

120
00:05:42,440 --> 00:05:47,500
Else razvrstiti levo polovico elementov,
nato razvrstite desni polovici elementov,

121
00:05:47,500 --> 00:05:49,640
spojite razvrščeni polovic.

122
00:05:49,640 --> 00:05:52,440
In kaj je nekako uma upogibanje
tukaj, je, da sem v resnici ne

123
00:05:52,440 --> 00:05:56,190
Zdi se, da ti je povedal
karkoli samo še, kajne?

124
00:05:56,190 --> 00:05:59,560
Vse sem rekel je, glede na seznam
n elementi, razvrstiti levo polovico,

125
00:05:59,560 --> 00:06:01,800
nato desno polovico, nato
združiti razvrščeni polovic,

126
00:06:01,800 --> 00:06:03,840
kje pa je dejanska skrivnost omako?

127
00:06:03,840 --> 00:06:05,260
Kje je algoritem?

128
00:06:05,260 --> 00:06:09,150
No, izkaže se, da teh dveh vrsticah
Prvi, sortiranje levo polovico elementov,

129
00:06:09,150 --> 00:06:13,970
in nekako desno polovico elementov,
so rekurzivne klice, tako rekoč.

130
00:06:13,970 --> 00:06:16,120
>> Konec koncev, na to
točka v času, moram

131
00:06:16,120 --> 00:06:18,950
algoritem, s katerim bi
razvrstiti cel kup elementov?

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

133
00:06:19,450 --> 00:06:20,620
To je prav tukaj.

134
00:06:20,620 --> 00:06:25,180
To je prav tukaj na zaslonu, in
tako da sem lahko uporabite isti niz korakov

135
00:06:25,180 --> 00:06:28,500
razvrstiti levo polovico,
kot sem lahko desno polovico.

136
00:06:28,500 --> 00:06:30,420
In res, spet in spet.

137
00:06:30,420 --> 00:06:34,210
Torej, tako ali drugače, in bomo kmalu
glej to čarobno zlivanjem

138
00:06:34,210 --> 00:06:37,967
je vdelana s tem, da zelo končni
črta, ki združuje urejen polovic.

139
00:06:37,967 --> 00:06:39,300
In da se zdi precej intuitivno.

140
00:06:39,300 --> 00:06:41,050
Vzameš dve polovici, in vas,
nekako, jih združiti skupaj,

141
00:06:41,050 --> 00:06:43,260
in bomo videli
konkretno v trenutku.

142
00:06:43,260 --> 00:06:45,080
>> Ampak to je popolna algoritem.

143
00:06:45,080 --> 00:06:46,640
In poglejmo, zakaj točno.

144
00:06:46,640 --> 00:06:50,912
No, domnevam, da smo zaradi teh istih
osem elementi tukaj na zaslonu, ena

145
00:06:50,912 --> 00:06:53,120
skozi osem, ampak oni
v navidezno naključnem vrstnem redu.

146
00:06:53,120 --> 00:06:55,320
In cilj pri roki, je
razvrstiti te elemente.

147
00:06:55,320 --> 00:06:58,280
No, kako se lahko lotim
to počne s pomočjo, še enkrat,

148
00:06:58,280 --> 00:07:00,407
zlivanjem, glede na to psevdokoda?

149
00:07:00,407 --> 00:07:02,740
In spet, Okorio to
tvoj um, samo za trenutek.

150
00:07:02,740 --> 00:07:05,270
Prvi primer je precej
nepomembno, če je manj kot 2,

151
00:07:05,270 --> 00:07:07,060
pravkar vrnil, ni dela, da je treba storiti.

152
00:07:07,060 --> 00:07:09,290
Torej res obstaja le tri
koraki, da bo res v mislih.

153
00:07:09,290 --> 00:07:11,081
Spet in spet sem
dogaja, da želijo imeti

154
00:07:11,081 --> 00:07:13,980
razvrstiti levo polovico,
razvrstiti desno polovico,

155
00:07:13,980 --> 00:07:15,890
in nato enkrat na njihovo
Polovici so razporejene,

156
00:07:15,890 --> 00:07:18,710
Hočem, da jih združi skupaj
v eno sortirane seznamu.

157
00:07:18,710 --> 00:07:19,940
Tako da se vodijo v mislih.

158
00:07:19,940 --> 00:07:21,310
>> Torej, tukaj je prvotni seznam.

159
00:07:21,310 --> 00:07:23,510
Oglejmo obravnava to kot
matrika, kot smo začeli

160
00:07:23,510 --> 00:07:25,800
v dveh tednih, ki je
sosednje blok pomnilnika.

161
00:07:25,800 --> 00:07:28,480
V tem primeru, ki vsebuje osem
številke, back to back to back.

162
00:07:28,480 --> 00:07:30,700
In kaj je zdaj uporabljajo zlivanjem.

163
00:07:30,700 --> 00:07:33,300
Tako sem najprej želeli razvrstiti
leva polovica tega seznama

164
00:07:33,300 --> 00:07:37,370
In da zato,
osredotočajo na 4, 8, 6, in 2.

165
00:07:37,370 --> 00:07:41,000
>> Zdaj, kako naj grem o
sortiranje seznam velikosti 4?

166
00:07:41,000 --> 00:07:45,990
No, moram premisliti
sortiranje levi levi polovici.

167
00:07:45,990 --> 00:07:47,720
Še enkrat, kaj je nazaj za trenutek.

168
00:07:47,720 --> 00:07:51,010
Če psevdokoda je to,
in sem dal osem elementov,

169
00:07:51,010 --> 00:07:53,230
8 je seveda večja
od ali enak 2.

170
00:07:53,230 --> 00:07:54,980
Torej s prvi primer ne velja.

171
00:07:54,980 --> 00:07:58,120
Torej, da razvrstite osem elementov, sem najprej
razvrstiti levo polovico elementov,

172
00:07:58,120 --> 00:08:01,930
Nato sem razvrstiti desno polovico, nato pa sem se združita
dve razporejene polovici, vsaka velikosti 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Ampak, če ste pravkar mi je povedal, razvrstite
leva polovica, ki je sedaj velikosti 4,

175
00:08:07,480 --> 00:08:09,350
kako razvrstiti levo polovico?

176
00:08:09,350 --> 00:08:11,430
No, če Imam
vložek iz štirih elementov,

177
00:08:11,430 --> 00:08:14,590
Sem najprej razvrstiti levo
dva, nato desno dva,

178
00:08:14,590 --> 00:08:16,210
in potem sem jih združi skupaj.

179
00:08:16,210 --> 00:08:18,700
Torej spet postane nekoliko
iz uma upogibanje igre tukaj,

180
00:08:18,700 --> 00:08:21,450
ker tebe, vrsta, moral
spomnite, kje ste v zgodbi,

181
00:08:21,450 --> 00:08:23,620
vendar ob koncu dneva,
dati poljubno število elementov,

182
00:08:23,620 --> 00:08:25,620
boste najprej želeli razvrstite
levo polovico, nato desno polovico,

183
00:08:25,620 --> 00:08:26,661
nato pa jih združiti skupaj.

184
00:08:26,661 --> 00:08:28,630
Začnimo storiti točno to.

185
00:08:28,630 --> 00:08:30,170
Tukaj je vhod iz osmih elementov.

186
00:08:30,170 --> 00:08:31,910
Zdaj smo iskali na levi polovici tukaj.

187
00:08:31,910 --> 00:08:33,720
Kako rešiti štiri elemente?

188
00:08:33,720 --> 00:08:35,610
Pa sem levo polovico najprej razvrstiti.

189
00:08:35,610 --> 00:08:37,720
Zdaj kako razvrstiti levo polovico?

190
00:08:37,720 --> 00:08:39,419
No, jaz sem dobila dva elementa.

191
00:08:39,419 --> 00:08:41,240
Torej, kaj je rešiti teh dveh elementov.

192
00:08:41,240 --> 00:08:44,540
2 je večja ali
enak 2, seveda.

193
00:08:44,540 --> 00:08:46,170
Tako da prvi primer ne velja.

194
00:08:46,170 --> 00:08:49,010
>> Tako da sem zdaj razvrstiti levo
polovica teh dveh elementov.

195
00:08:49,010 --> 00:08:50,870
Levo polovico, seveda, je le 4.

196
00:08:50,870 --> 00:08:54,020
Torej, kako razvrstiti seznam en element?

197
00:08:54,020 --> 00:08:57,960
No sedaj, da je posebna osnovna
do vrha, tako rekoč, velja.

198
00:08:57,960 --> 00:09:01,470
1 je manj kot 2, in moj
Seznam je seveda od velikosti 1.

199
00:09:01,470 --> 00:09:02,747
Torej sem vrnil.

200
00:09:02,747 --> 00:09:03,580
Jaz ne delam ničesar.

201
00:09:03,580 --> 00:09:06,770
In res, poglej, kaj sem
storiti, 4 je že urejeno.

202
00:09:06,770 --> 00:09:09,220
Tako kot sem že
delno uspešna tukaj.

203
00:09:09,220 --> 00:09:11,750
>> Zdaj, ko se zdi nekako neumno
zahtevati, vendar je res.

204
00:09:11,750 --> 00:09:13,700
4 je seznam velikosti 1.

205
00:09:13,700 --> 00:09:15,090
To je že urejeno.

206
00:09:15,090 --> 00:09:16,270
Da je leva polovica.

207
00:09:16,270 --> 00:09:18,010
Zdaj sem desno polovico razvrstiti.

208
00:09:18,010 --> 00:09:22,310
Moj vložek je eden od elementov, 8
podobno že urejeno.

209
00:09:22,310 --> 00:09:25,170
Neumna, preveč, ampak spet,
To osnovno načelo

210
00:09:25,170 --> 00:09:28,310
se dogaja, da nam omogočajo, da sedaj gradijo
poleg tega uspešno.

211
00:09:28,310 --> 00:09:32,260
4 razporejene, 8 je razvrščen, zdaj
kaj je bilo to zadnji korak?

212
00:09:32,260 --> 00:09:35,330
Torej, tretji in zadnji korak, vsaka
ko boste sortiranje seznamu, odpoklic,

213
00:09:35,330 --> 00:09:38,310
je bil združiti dve polovici,
levo in desno.

214
00:09:38,310 --> 00:09:39,900
Torej, kaj je naredil točno to.

215
00:09:39,900 --> 00:09:41,940
Moja leva polovica je, seveda, 4.

216
00:09:41,940 --> 00:09:43,310
Moja desna polovica je 8.

217
00:09:43,310 --> 00:09:44,100
>> Torej, kaj je to.

218
00:09:44,100 --> 00:09:46,410
Najprej bom dodeliti
nekateri dodatni spomin,

219
00:09:46,410 --> 00:09:48,680
da bom predstavljajo tu,
le kot sekundarni array,

220
00:09:48,680 --> 00:09:49,660
ki je dovolj velika, da ustreza to.

221
00:09:49,660 --> 00:09:52,243
Ampak si lahko predstavljate razširitev
da pravokotnik po celotni dolžini,

222
00:09:52,243 --> 00:09:53,290
če bomo potrebovali več kasneje.

223
00:09:53,290 --> 00:09:58,440
Kako naj vzamem 4 in 8, in združitev
ti dve seznami velikosti 1 skupaj?

224
00:09:58,440 --> 00:10:00,270
Tudi tu je precej preprosta.

225
00:10:00,270 --> 00:10:03,300
4. na prvem mestu, potem pa pride 8.

226
00:10:03,300 --> 00:10:07,130
Ker če želim, da razvrstite
levo polovico, nato desno polovico,

227
00:10:07,130 --> 00:10:09,900
in nato združiti teh dveh polovic
skupaj, v urejenih namenom,

228
00:10:09,900 --> 00:10:11,940
4. na prvem mestu, potem pa pride 8.

229
00:10:11,940 --> 00:10:15,810
>> Tako se zdi, da je treba doseči napredek, čeprav
čeprav nisem storil nobenega dejanskega dela.

230
00:10:15,810 --> 00:10:17,800
Ampak ne pozabite, kje smo v zgodbi.

231
00:10:17,800 --> 00:10:19,360
Smo sprva vzel osem elementov.

232
00:10:19,360 --> 00:10:21,480
Razporejene smo levi polovici, ki je 4.

233
00:10:21,480 --> 00:10:24,450
Potem smo razporejene levo polovico
levega pol, ki je bil 2.

234
00:10:24,450 --> 00:10:25,270
In gremo.

235
00:10:25,270 --> 00:10:26,920
Mi smo storili s tem korakom.

236
00:10:26,920 --> 00:10:29,930
>> Torej, če smo razporejene
levo polovico 2, zdaj smo

237
00:10:29,930 --> 00:10:32,130
morali razvrstiti desni polovici 2.

238
00:10:32,130 --> 00:10:35,710
Torej je pravica pol 2 je
ti dve vrednosti tukaj, 6 in 2.

239
00:10:35,710 --> 00:10:40,620
Torej, kaj je zdaj traja vhod velikosti
2, in razvrstiti levo polovico, nato pa

240
00:10:40,620 --> 00:10:42,610
desno polovico, in nato
jih združiti skupaj.

241
00:10:42,610 --> 00:10:45,722
No, kako razvrstiti seznam velikosti
1, ki vsebuje samo številko 6?

242
00:10:45,722 --> 00:10:46,430
Jaz sem že naredil.

243
00:10:46,430 --> 00:10:48,680
Ta seznam velikosti 1 razporejene.

244
00:10:48,680 --> 00:10:52,140
>> Kako rešiti še en seznam
velikost 1, tako imenovani desno polovico.

245
00:10:52,140 --> 00:10:54,690
No to, preveč, je že urejeno.

246
00:10:54,690 --> 00:10:56,190
Številka 2 je sam.

247
00:10:56,190 --> 00:11:00,160
Torej, zdaj imam dve polovici, levo in
Dobro, moram, da jih združi skupaj.

248
00:11:00,160 --> 00:11:01,800
Naj sam dal nekaj dodatnega prostora.

249
00:11:01,800 --> 00:11:05,580
In dal 2 v tam,
Nato 6 tja, s čimer

250
00:11:05,580 --> 00:11:10,740
sortiranje ta seznam, levo in desno,
in ga združujejo, na koncu.

251
00:11:10,740 --> 00:11:12,160
Torej sem v nekoliko boljši formi.

252
00:11:12,160 --> 00:11:16,250
Ne bom storil, ker je jasno 4, 8, 2,
6 ni končni vrstni red, ki ga želim.

253
00:11:16,250 --> 00:11:20,640
Ampak zdaj imam dva seznama velikosti 2, ki
sta, v tem zaporedju, so razporejene.

254
00:11:20,640 --> 00:11:24,580
Torej, zdaj, če ste nazaj v tvoj um je
oko, kjer je, ki nas pusti?

255
00:11:24,580 --> 00:11:28,520
Začel sem z osem elementov, potem sem
ga whittled navzdol na levi polovici 4,

256
00:11:28,520 --> 00:11:31,386
potem levi polovici 2 in
nato desno polovico 2,

257
00:11:31,386 --> 00:11:34,510
Končal sem zato, sortiranje levo
pol 2 in desno polovico od 2,

258
00:11:34,510 --> 00:11:37,800
Torej, kaj je tretji in zadnji korak tukaj?

259
00:11:37,800 --> 00:11:41,290
Moram skupaj združiti
dva seznama velikosti 2.

260
00:11:41,290 --> 00:11:42,040
Torej, gremo naprej.

261
00:11:42,040 --> 00:11:43,940
In na zaslonu Daj
me nekateri dodatni pomnilnik,

262
00:11:43,940 --> 00:11:47,170
čeprav tehnično, opazili, da sem
imam cel kup prazen prostor do vrha

263
00:11:47,170 --> 00:11:47,670
tam.

264
00:11:47,670 --> 00:11:50,044
Če želim biti še posebej
učinkovite prostor pametno,

265
00:11:50,044 --> 00:11:52,960
Jaz lahko samo začnejo premikati elemente
naprej in nazaj, zgoraj in spodaj.

266
00:11:52,960 --> 00:11:55,460
Ampak samo za vizualno jasnosti,
Jaz grem, da ga spodaj,

267
00:11:55,460 --> 00:11:56,800
da se stvari lepo in čisto.

268
00:11:56,800 --> 00:11:58,150
>> Torej imam dva seznama velikosti 2.

269
00:11:58,150 --> 00:11:59,770
Prvi seznam je 4 in 8.

270
00:11:59,770 --> 00:12:01,500
Drugi seznam je 2 in 6.

271
00:12:01,500 --> 00:12:03,950
Oglejmo združiti tiste,
skupaj v urejenem zaporedju.

272
00:12:03,950 --> 00:12:09,910
2, seveda, na prvem mestu,
potem 4, potem 6, nato pa 8.

273
00:12:09,910 --> 00:12:12,560
In zdaj se zdi, da se pridobivanje
nekje zanimivo.

274
00:12:12,560 --> 00:12:15,720
Zdaj sem razporejene polovica
seznam, in po naključju, saj je

275
00:12:15,720 --> 00:12:18,650
vse sode številke, ampak da
je, seveda, zgolj naključje.

276
00:12:18,650 --> 00:12:22,220
In zdaj so razporejene levo
pol, tako, da je 2, 4, 6 in 8.

277
00:12:22,220 --> 00:12:23,430
Nič ni v okvari.

278
00:12:23,430 --> 00:12:24,620
Da se počuti kot napredek.

279
00:12:24,620 --> 00:12:26,650
>> Zdaj se počuti, kot da sem imel
govoril večno sedaj,

280
00:12:26,650 --> 00:12:29,850
Torej, kaj se bo pokazalo, če je to
algoritem je pravzaprav bolj učinkovito.

281
00:12:29,850 --> 00:12:31,766
Ampak gremo skozi
je super metodično.

282
00:12:31,766 --> 00:12:34,060
Računalnik seveda
bi to naredil tako.

283
00:12:34,060 --> 00:12:34,840
Torej, kje smo?

284
00:12:34,840 --> 00:12:36,180
Začeli smo z osmimi elementi.

285
00:12:36,180 --> 00:12:37,840
I razporejene levi polovici 4.

286
00:12:37,840 --> 00:12:39,290
Zdi se mi, da je treba opraviti s tem.

287
00:12:39,290 --> 00:12:42,535
Torej, zdaj naslednji korak je, da
razvrstiti desni polovici 4.

288
00:12:42,535 --> 00:12:44,410
In ta del lahko gremo
skozi malo bolj

289
00:12:44,410 --> 00:12:47,140
hitro, čeprav ste
dobrodošli nazaj ali pavza, samo

290
00:12:47,140 --> 00:12:49,910
mislim skozi njo na
svoj tempo, ampak kaj

291
00:12:49,910 --> 00:12:53,290
imamo zdaj priložnost, da se
narediti točno isto algoritem na štirih

292
00:12:53,290 --> 00:12:54,380
različne številke.

293
00:12:54,380 --> 00:12:57,740
>> Torej, gremo naprej in se osredotočiti na
desna polovica, ki smo tukaj.

294
00:12:57,740 --> 00:13:01,260
Leva polovica da
desno polovico, in zdaj

295
00:13:01,260 --> 00:13:04,560
leva polovica levi
polovica tega desni polovici,

296
00:13:04,560 --> 00:13:08,030
in kako razvrstiti seznam velikosti
1 vsebuje samo številko 1?

297
00:13:08,030 --> 00:13:09,030
To je že storila.

298
00:13:09,030 --> 00:13:11,830
Kako naj storijo enako za seznam
z velikostjo 1, ki vsebuje samo 7?

299
00:13:11,830 --> 00:13:12,840
To je že storila.

300
00:13:12,840 --> 00:13:16,790
Tretji korak za to pol potem
je združevanje teh dveh elementov

301
00:13:16,790 --> 00:13:20,889
v nov seznam velikosti 2, 1 in 7.

302
00:13:20,889 --> 00:13:23,180
Ne zdi, da so storili vse,
da je precej zanimivo delo.

303
00:13:23,180 --> 00:13:24,346
Poglejmo, kaj se zgodi naslednje.

304
00:13:24,346 --> 00:13:29,210
Pravkar sem razporejene na levi polovici
Desna polovica mojega prvotnega vhoda.

305
00:13:29,210 --> 00:13:32,360
Zdaj pa razvrstiti pravico
pol, ki vsebuje 5 in 3.

306
00:13:32,360 --> 00:13:35,740
Poglejmo še enkrat poglej na levi strani
pol, razporejene, z desno polovico, razporejene,

307
00:13:35,740 --> 00:13:39,120
in združitev teh dveh skupaj,
v nekaj dodatnega prostora,

308
00:13:39,120 --> 00:13:41,670
3 na prvem mestu, potem pa pride 5.

309
00:13:41,670 --> 00:13:46,190
In tako zdaj smo razporejene
levi polovici desni polovici

310
00:13:46,190 --> 00:13:49,420
prvotnega problema,
Desna polovica desni polovici

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

312
00:13:50,800 --> 00:13:52,480
Kaj je tretji in zadnji korak?

313
00:13:52,480 --> 00:13:54,854
No, da se združijo teh dveh polovic skupaj.

314
00:13:54,854 --> 00:13:57,020
Zato mi dovolite, omisliti nekaj
dodaten prostor, toda spet sem

315
00:13:57,020 --> 00:13:58,699
bi lahko z uporabo tega rezervnega prostora do vrha.

316
00:13:58,699 --> 00:14:00,490
Ampak bomo obdržati
preprosto vizualno.

317
00:14:00,490 --> 00:14:07,070
Dovolite mi, da se združijo v zdaj 1, in
nato 3, nato pa 5, nato 7.

318
00:14:07,070 --> 00:14:10,740
S tem me je pustil zdaj z
desno polovico originalnega problema

319
00:14:10,740 --> 00:14:12,840
ki je popolnoma urejeno.

320
00:14:12,840 --> 00:14:13,662
>> Torej, kaj ostane?

321
00:14:13,662 --> 00:14:16,120
Počutim se, kot da sem obdržati pravijo
iste stvari znova in znova,

322
00:14:16,120 --> 00:14:18,700
ampak to je odbojni od
Dejstvo, da smo s pomočjo rekurzijo.

323
00:14:18,700 --> 00:14:21,050
Postopek uporabe
Algoritem znova in znova,

324
00:14:21,050 --> 00:14:23,940
na manjše podskupine
prvotna problem.

325
00:14:23,940 --> 00:14:27,580
Torej sem sedaj levi razporejene
polovico prvotnega problema.

326
00:14:27,580 --> 00:14:30,847
Imam pravico urejen polovico
prvotnega problema.

327
00:14:30,847 --> 00:14:32,180
Kaj je tretji in zadnji korak?

328
00:14:32,180 --> 00:14:33,590
Oh, to je združitev.

329
00:14:33,590 --> 00:14:34,480
Torej, kaj je to.

330
00:14:34,480 --> 00:14:36,420
Oglejmo dodeliti nekatere dodatne
spomin, ampak moj bog, smo

331
00:14:36,420 --> 00:14:37,503
bi ga kjerkoli zdaj.

332
00:14:37,503 --> 00:14:40,356
Imamo toliko prostora na voljo
za nas, ampak bomo to bo enostavno.

333
00:14:40,356 --> 00:14:42,730
Namesto da bi šel nazaj in
tja s svojo izvorno spomin,

334
00:14:42,730 --> 00:14:44,480
kaj je samo to
vizualno tukaj spodaj,

335
00:14:44,480 --> 00:14:47,240
do konca gor združitvijo
levo polovico in desno polovico.

336
00:14:47,240 --> 00:14:49,279
>> Torej z združitvijo, kaj moram storiti?

337
00:14:49,279 --> 00:14:50,820
Želim, da bi elemente v redu.

338
00:14:50,820 --> 00:14:53,230
Tako je videti na levi polovici,
Vidim, da je prva številka je 2.

339
00:14:53,230 --> 00:14:55,230
Gledam desni polovici,
Vidim prvo številko

340
00:14:55,230 --> 00:14:58,290
1, tako da je očitno, ki
številka ne želim, da izderi

341
00:14:58,290 --> 00:15:00,430
in dal najprej v moji končni seznam?

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

343
00:15:01,449 --> 00:15:02,990
Zdaj pa bi rad vprašal to isto vprašanje.

344
00:15:02,990 --> 00:15:05,040
Na levi polovici, sem imel
Še vedno imam številko 2.

345
00:15:05,040 --> 00:15:07,490
Na desni polovici,
Imam številko 3.

346
00:15:07,490 --> 00:15:08,930
Kateri želim izbrati?

347
00:15:08,930 --> 00:15:11,760
Seveda, številka 2 In
zdaj opazili kandidate

348
00:15:11,760 --> 00:15:13,620
so 4 na levi, 3 na desni strani.

349
00:15:13,620 --> 00:15:15,020
Poglejmo, seveda, izberite 3.

350
00:15:15,020 --> 00:15:18,020
Zdaj kandidati so 4 na
levo, 5 na desni strani.

351
00:15:18,020 --> 00:15:19,460
Mi, seveda izbere 4.

352
00:15:19,460 --> 00:15:21,240
6 na levi strani, 5 na desni strani.

353
00:15:21,240 --> 00:15:22,730
Mi, seveda izbere 5.

354
00:15:22,730 --> 00:15:25,020
6 na levi strani, 7 na desni strani.

355
00:15:25,020 --> 00:15:29,320
Bomo izbrali 6, nato pa smo
izbrati 7, nato pa smo izbrali 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Tako veliko število besed, kasneje smo
so razporejene ta seznam osmih elementov

358
00:15:34,370 --> 00:15:38,450
v seznamu enega do osem,
da se povečuje z vsakim korakom,

359
00:15:38,450 --> 00:15:40,850
ampak koliko časa si
da nas bo, da to storim.

360
00:15:40,850 --> 00:15:43,190
No Sem namenoma
Laid stvari slikovno

361
00:15:43,190 --> 00:15:46,330
tukaj, tako da lahko nekako
videti ali cenijo delitev

362
00:15:46,330 --> 00:15:49,060
pri osvajanju, ki se je dogajalo.

363
00:15:49,060 --> 00:15:52,830
>> Pravzaprav, če se ozremo na sedmini,
Sem pustil vse te pikčastih črt

364
00:15:52,830 --> 00:15:55,660
V imetnikov mestu, lahko,
vrsta, glej v obratnem vrstnem redu,

365
00:15:55,660 --> 00:15:58,800
če ste nekako se ozremo v
Zgodovina sedaj, moj prvotni seznam

366
00:15:58,800 --> 00:16:00,250
je seveda velikosti 8.

367
00:16:00,250 --> 00:16:03,480
In potem že prej, sem bil
ki se ukvarjajo z dvema seznamov velikosti 4,

368
00:16:03,480 --> 00:16:08,400
in nato štiri liste velikosti 2,
in nato osem seznami velikosti 1.

369
00:16:08,400 --> 00:16:10,151
>> Torej, kaj je to,
vrsta, vas spominja?

370
00:16:10,151 --> 00:16:11,858
No, dejansko je katerakoli
algoritmi, ki smo jih

371
00:16:11,858 --> 00:16:14,430
pogledal tako daleč, kjer smo
razkorak, in razkorak, in razkorak,

372
00:16:14,430 --> 00:16:19,500
da ima stvari še enkrat, in
spet kaže v tej splošni ideji.

373
00:16:19,500 --> 00:16:23,100
In tako je nekaj
logaritemsko dogaja.

374
00:16:23,100 --> 00:16:26,790
In to ni čisto log n, vendar
tam je logaritemsko komponenta

375
00:16:26,790 --> 00:16:28,280
s tem, kar smo pravkar končali.

376
00:16:28,280 --> 00:16:31,570
>> Zdaj pa razmisli, kako je v resnici.

377
00:16:31,570 --> 00:16:34,481
Torej log n, spet je bil
veliko časa teče,

378
00:16:34,481 --> 00:16:36,980
ko smo naredili nekaj podobnega
dvojiško iskanje, kot smo zdaj pravijo,

379
00:16:36,980 --> 00:16:40,090
razkorak in vladaj strategije
prek katere smo ugotovili, Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Zdaj tehnično.

381
00:16:41,020 --> 00:16:43,640
To je dnevnik lokaciji 2 n, celo
čeprav v večini matematike razrede,

382
00:16:43,640 --> 00:16:45,770
10 je običajno osnova, ki jo prevzemajo.

383
00:16:45,770 --> 00:16:48,940
Ampak računalniški znanstveniki skoraj vedno
razmišljati in govoriti v smislu osnove 2,

384
00:16:48,940 --> 00:16:52,569
tako da smo na splošno samo reči dnevnik
n, namesto log baze 2 n,

385
00:16:52,569 --> 00:16:55,110
ampak oni so natanko eno in
Enako v svetu računalniku

386
00:16:55,110 --> 00:16:57,234
znanost in kot prahi,
tam je konstanten faktor

387
00:16:57,234 --> 00:17:01,070
Razlika med njima, tako da je
nepotreben vseeno, za več formalnih razlogov.

388
00:17:01,070 --> 00:17:04,520
>> Ampak za zdaj, kaj nam je mar
o je ta primer.

389
00:17:04,520 --> 00:17:08,520
Torej naj ne izkaže z zgledom, temveč na
vsaj uporabite zgled številk

390
00:17:08,520 --> 00:17:10,730
pri roki kot preverjanje razumnosti, če hočete.

391
00:17:10,730 --> 00:17:14,510
Torej prej formula je log baza
2 n, ampak kaj je n v tem primeru.

392
00:17:14,510 --> 00:17:18,526
Imel sem n originalne številke, ali 8
od prvotne številko posebej.

393
00:17:18,526 --> 00:17:20,359
Zdaj je že malo
medtem, ampak sem precej

394
00:17:20,359 --> 00:17:25,300
prepričani, da je log baza 2
vrednosti 8 je 3,

395
00:17:25,300 --> 00:17:29,630
in seveda, kar je lepo, pa, da je
da 3 je ravno kolikokrat

396
00:17:29,630 --> 00:17:33,320
da lahko razdelite seznam
dolžine 8 znova in znova,

397
00:17:33,320 --> 00:17:36,160
in spet, dokler ste zapustili
sezname samo velikosti 1.

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

399
00:17:36,660 --> 00:17:40,790
8 gre do 4, gre 2,
gre za 1, in to je

400
00:17:40,790 --> 00:17:43,470
odražajo točno to
picture smo imeli pred nekaj trenutki.

401
00:17:43,470 --> 00:17:47,160
Torej malo sanity check, kje
logaritem dejansko gre.

402
00:17:47,160 --> 00:17:50,180
>> Torej, zdaj je kaj tukaj vpleten? n.

403
00:17:50,180 --> 00:17:53,440
Tako opazili, da se vsak
Tokrat sem razdelila seznam,

404
00:17:53,440 --> 00:17:58,260
čeprav v obratnem vrstnem redu v zgodovini
tukaj, sem bil še vedno počne n stvari.

405
00:17:58,260 --> 00:18:02,320
Ta korak je združitev potrebna, da
Dotaknem vsak od številk,

406
00:18:02,320 --> 00:18:05,060
da se ga potisnite
njeno primerno lokacijo.

407
00:18:05,060 --> 00:18:10,760
Torej, čeprav je višina tega
diagram je z velikostjo log n n ali 3,

408
00:18:10,760 --> 00:18:13,860
Natančneje, z drugimi besedami,
Naredil sem tri divizije tukaj.

409
00:18:13,860 --> 00:18:18,800
Koliko dela sem naredil horizontalno
ob tem grafikonu vsakič?

410
00:18:18,800 --> 00:18:21,110
>> No, sem n korake
delati, ker če sem

411
00:18:21,110 --> 00:18:24,080
dobil štiri elemente in štiri elemente,
in moram, da jih združi skupaj.

412
00:18:24,080 --> 00:18:26,040
Moram iti skozi
te štiri in te štiri,

413
00:18:26,040 --> 00:18:28,123
nazadnje, da jih združi
nazaj na osem elementov.

414
00:18:28,123 --> 00:18:32,182
Če nasprotno Imam osem prstov
tukaj, kar jaz ne, in osem

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- če sem
dobil štiri prste tukaj,

416
00:18:34,390 --> 00:18:37,380
ki sem ga naredil, štiri prste
sem, ki sem jo naredil,

417
00:18:37,380 --> 00:18:40,590
potem je to isto
na primer kot prej, če naredim

418
00:18:40,590 --> 00:18:44,010
imajo osem prstov, čeprav v
skupaj, kar sem lahko, vrsta, storite.

419
00:18:44,010 --> 00:18:47,950
Ne morem točno tukaj storiti,
potem sem lahko zagotovo

420
00:18:47,950 --> 00:18:50,370
združitev vseh teh seznamov
velikosti 1 skupaj.

421
00:18:50,370 --> 00:18:54,050
Ampak jaz zagotovo morali pogledati
v vsakem elementu natanko enkrat.

422
00:18:54,050 --> 00:18:59,640
Torej je višina tega procesa je log n,
širina tega procesa, tako rekoč

423
00:18:59,640 --> 00:19:02,490
je n, torej tisto, kar se zdi,
da imajo, navsezadnje, je

424
00:19:02,490 --> 00:19:06,470
teče čas velikosti n krat log n.

425
00:19:06,470 --> 00:19:08,977
>> Z drugimi besedami, smo razdelili
seznam, log n-krat,

426
00:19:08,977 --> 00:19:11,810
ampak vsakič, ko smo naredili, da smo imeli
na dotik vsak od elementov

427
00:19:11,810 --> 00:19:13,560
da bi se ju združi
vse skupaj, kar

428
00:19:13,560 --> 00:19:18,120
je n korak, tako da imamo n krat log n,
ali kot bi računalniški znanstvenik reči,

429
00:19:18,120 --> 00:19:20,380
asimptotično, ki
bi bila velika beseda

430
00:19:20,380 --> 00:19:22,810
opisati zgornji
vezan na čas teče,

431
00:19:22,810 --> 00:19:28,010
smo se izvajajo v Big O
log n časa, tako rekoč.

432
00:19:28,010 --> 00:19:31,510
>> Zdaj je to pomembno, ker
spomniti, kaj so tekoči časi

433
00:19:31,510 --> 00:19:34,120
z mehurček vrste in izbor
razvrščanje in vstavljanje razvrščanje,

434
00:19:34,120 --> 00:19:38,200
in še nekaj drugih, ki obstajajo,
n kvadrat je bilo, kje smo bili na.

435
00:19:38,200 --> 00:19:39,990
In lahko, vrsta, videti tukaj.

436
00:19:39,990 --> 00:19:45,720
Če je n kvadrat očitno n-krat
n, ampak tukaj smo n-krat log n,

437
00:19:45,720 --> 00:19:48,770
in smo že vedeli iz tedna
nič, da log n, logaritemsko,

438
00:19:48,770 --> 00:19:50,550
je boljše kot nekaj, kar linearno.

439
00:19:50,550 --> 00:19:52,930
Konec koncev, se spomni sliko
z rdečo in rumeno

440
00:19:52,930 --> 00:19:56,500
in zelene črte, da smo pripravili, The
zelena logaritemsko linija je bila precej nižja.

441
00:19:56,500 --> 00:20:00,920
In zato je veliko bolje in hitreje
od ravne rumenimi in rdečimi črtami,

442
00:20:00,920 --> 00:20:05,900
n-krat log n je namreč bolje,
kot n-krat n ali n kvadrat.

443
00:20:05,900 --> 00:20:09,110
>> Tako se zdi, da imajo
Identificirali algoritem spajanje

444
00:20:09,110 --> 00:20:11,870
vrste, ki teče v veliko
krajši čas, in res,

445
00:20:11,870 --> 00:20:16,560
to je zato, v začetku tega tedna, ko se
smo videli, da je tekmovanje med mehurček

446
00:20:16,560 --> 00:20:20,750
razvrščanje, izbira vrste in združiti
razvrščanje, urejanje z zlivanjem res, res zmagal.

447
00:20:20,750 --> 00:20:23,660
In res, nismo še počakati
za mehurček vrste in izbire vrste

448
00:20:23,660 --> 00:20:24,790
končati.

449
00:20:24,790 --> 00:20:27,410
>> Sedaj vzemimo eno drugo točno
na to, od nekoliko bolj

450
00:20:27,410 --> 00:20:31,030
formalni vidik, samo v
primeru to odmeva bolje

451
00:20:31,030 --> 00:20:33,380
od tega višjo razpravo ravni.

452
00:20:33,380 --> 00:20:34,880
Torej, tukaj je algoritem znova.

453
00:20:34,880 --> 00:20:36,770
Naj vprašam sebe,
kaj čas teče

454
00:20:36,770 --> 00:20:39,287
je to algoritmi različne korake?

455
00:20:39,287 --> 00:20:41,620
Naj ga razdelite na prvi
primera in v drugem primeru.

456
00:20:41,620 --> 00:20:46,280
IF in ELSE V primeru IF,
Če je n manj kot 2, samo vrnitev.

457
00:20:46,280 --> 00:20:47,580
Počutim se kot konstantni čas.

458
00:20:47,580 --> 00:20:50,970
To je, nekako tako kot dveh korakih,
Če je n manj kot 2, nato vrne.

459
00:20:50,970 --> 00:20:54,580
Ampak kot smo rekli v ponedeljek,
konstanten čas, ali pa velik o po 1,

460
00:20:54,580 --> 00:20:57,130
lahko dva koraka, tri
koraki, celo 1.000 korakov.

461
00:20:57,130 --> 00:20:59,870
Kar je pomembno, je, da je
konstantno število korakov.

462
00:20:59,870 --> 00:21:03,240
Torej rumeno poudarjena psevdokoda
tukaj teče v, imenovali jo bomo,

463
00:21:03,240 --> 00:21:04,490
konstantna čas.

464
00:21:04,490 --> 00:21:06,780
Torej bolj formalno in
bomo to-- to

465
00:21:06,780 --> 00:21:09,910
bo obseg, v katerem smo
formalizira ta pravico now-- T n,

466
00:21:09,910 --> 00:21:15,030
čas problem teče
da je n somethings kot vhod,

467
00:21:15,030 --> 00:21:19,150
enako velik o enega,
ČE je n manj kot 2.

468
00:21:19,150 --> 00:21:20,640
Torej je odvisna od tega.

469
00:21:20,640 --> 00:21:24,150
Torej, da bo jasno, če je n manj kot
2, imamo zelo kratek seznam, nato pa

470
00:21:24,150 --> 00:21:29,151
čas teče, T n, kjer je n
1 ali 0, v tem posebnem primeru,

471
00:21:29,151 --> 00:21:30,650
to je le, da bo konstantna čas.

472
00:21:30,650 --> 00:21:32,691
To se dogaja, da imajo eno
korak, dva koraka, karkoli.

473
00:21:32,691 --> 00:21:33,950
To je določeno število korakov.

474
00:21:33,950 --> 00:21:38,840
>> Torej mora sočno del zagotovo v
drugi primer v psevdokoda.

475
00:21:38,840 --> 00:21:40,220
Primer drugega.

476
00:21:40,220 --> 00:21:44,870
Razvrsti leva polovica elementov, nekako desno
polovica elementov, spajanje Urejeni polovic.

477
00:21:44,870 --> 00:21:46,800
Kako dolgo traja vsak od teh korakov trajalo?

478
00:21:46,800 --> 00:21:49,780
No, če je tek
Čas je, da n elemente razvrstiti

479
00:21:49,780 --> 00:21:53,010
je, dajmo ga pokličete zelo
generično, T n,

480
00:21:53,010 --> 00:21:55,500
nato sortiranje levo
polovica elementov

481
00:21:55,500 --> 00:21:59,720
je, nekako, kot bi rekli,
T n deliti z 2,

482
00:21:59,720 --> 00:22:03,000
in podobno razvrščanje desni polovici
elementov je, nekako, kot bi rekli,

483
00:22:03,000 --> 00:22:06,974
T n razdeljena 2 in nato
združitvijo razvrščeni polovic.

484
00:22:06,974 --> 00:22:08,890
No, če imam nekaj
število elementov tod

485
00:22:08,890 --> 00:22:11,230
kot štiri, in nekaj več
elementov tod kot štiri,

486
00:22:11,230 --> 00:22:14,650
in moram združiti vsaki od teh štirih
V, in vsak od teh štirje, eno

487
00:22:14,650 --> 00:22:17,160
Po drugi strani, tako da
končno imam osem elementov.

488
00:22:17,160 --> 00:22:20,230
Zdi se mi, da je to velik o n korakov?

489
00:22:20,230 --> 00:22:23,500
Če imam n prste in vsak od
jih je treba združiti v mestu,

490
00:22:23,500 --> 00:22:25,270
to je tako kot drugi n korakih.

491
00:22:25,270 --> 00:22:27,360
>> Torej res formulaically,
bomo lahko to izraziti,

492
00:22:27,360 --> 00:22:29,960
čeprav malo strašljivo na prvi
pogled, vendar pa je nekaj

493
00:22:29,960 --> 00:22:31,600
da zajame točno to logiko.

494
00:22:31,600 --> 00:22:35,710
Čas teče, T n, če je n
je večja ali enaka 2.

495
00:22:35,710 --> 00:22:42,500
V tem primeru, v primeru drugega, je T n
deliti z 2, plus T N deliti z 2,

496
00:22:42,500 --> 00:22:45,320
plus velik o n, nekateri
linearna število korakov,

497
00:22:45,320 --> 00:22:51,630
morda ravno n, morda 2 krat
n, ampak to je približno, da bi n.

498
00:22:51,630 --> 00:22:54,060
Tako da, preveč, je, kako smo lahko
formulaically izraziti to.

499
00:22:54,060 --> 00:22:56,809
Zdaj pa ne bi vedel, če tega
ste jo zabeležili v tvoji glavi,

500
00:22:56,809 --> 00:22:58,710
ali ga poiščete v
nazaj učbenika, ki

501
00:22:58,710 --> 00:23:00,501
morda malo
goljufija stanja na koncu,

502
00:23:00,501 --> 00:23:03,940
ampak to je, seveda, bo
da nam veliko o n log n,

503
00:23:03,940 --> 00:23:06,620
ker je ponovitev da
ste tukaj videli na zaslonu,

504
00:23:06,620 --> 00:23:09,550
če ste dejansko to storil, da bodo z
neskončno število primerov,

505
00:23:09,550 --> 00:23:13,000
ali ste to storili formulaically, bi si
vidim, da je to, ker to formulo

506
00:23:13,000 --> 00:23:17,100
sama rekurzivno, s t
n čez nekaj na desni strani,

507
00:23:17,100 --> 00:23:21,680
in t N nad na levi strani, to lahko
dejansko se je izrazil, navsezadnje,

508
00:23:21,680 --> 00:23:24,339
tako velika go n log n.

509
00:23:24,339 --> 00:23:26,130
Če ni prepričan, da je
Globa za zdaj, samo

510
00:23:26,130 --> 00:23:28,960
sprejeti na veri, da je to, res,
kaj to ponovitev vodi,

511
00:23:28,960 --> 00:23:31,780
ampak to je samo malo bolj za
matematični pristop k iščejo

512
00:23:31,780 --> 00:23:36,520
ob zlivanjem teče
na podlagi svoje psevdokoda sam.

513
00:23:36,520 --> 00:23:39,030
>> Zdaj pa si malo
odzračevalni od vseh, da

514
00:23:39,030 --> 00:23:41,710
in vzemite si na
nekateri nekdanji senator, ki je

515
00:23:41,710 --> 00:23:44,260
Morda poglej malo pozna,
ki je sedel z Googlovim Ericom

516
00:23:44,260 --> 00:23:48,410
Schmidt, pred nekaj časa za razgovor
na odru, pred cel kup

517
00:23:48,410 --> 00:23:53,710
ljudi, ki govori o koncu
tema, ki je zelo zdaj pozna.

518
00:23:53,710 --> 00:23:54,575
Oglejmo pogled.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Zdaj Senator,
ste tukaj na Googlu,

521
00:24:03,890 --> 00:24:09,490
in mi je všeč, da razmišljajo od
predsedstvo kot razgovor za službo.

522
00:24:09,490 --> 00:24:11,712
Zdaj je težko dobiti službo kot predsednik.

523
00:24:11,712 --> 00:24:12,670
Predsednik Obama: Right.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: In vi ste
naredili [neslišno] zdaj.

525
00:24:13,940 --> 00:24:15,523
Prav tako je težko dobiti službo pri Googlu.

526
00:24:15,523 --> 00:24:17,700
Predsednik Obama: Right.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Imamo vprašanja,
in naprošamo naše kandidatov vprašanja,

528
00:24:21,330 --> 00:24:24,310
in to je eden od Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> Predsednik Obama: OK.

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

531
00:24:27,005 --> 00:24:28,130
Mislita, da sem hecam?

532
00:24:28,130 --> 00:24:30,590
To je prav tukaj.

533
00:24:30,590 --> 00:24:33,490
Kaj je najbolj učinkovit način za
razvrstiti milijon 32 bitnih celih števil?

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

535
00:24:37,560 --> 00:24:38,979
>> Predsednik Obama: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Včasih,
Mogoče mi je žal, maybe--

537
00:24:41,020 --> 00:24:42,750
Predsednik Obama: Ne, ne,
ne, ne, ne, jaz think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: To ni it--

539
00:24:43,240 --> 00:24:45,430
Predsednik Obama: I
mislim, mislim, da je mehurček

540
00:24:45,430 --> 00:24:46,875
nekako bi bila napačna pot.

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

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

543
00:24:50,535 --> 00:24:52,200
Kdo mu je to povedal?

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

545
00:24:54,020 --> 00:24:55,590
Nisem storil računalništvo on--

546
00:24:55,590 --> 00:24:58,986
>> Predsednik Obama: Smo jih
dobil svoje vohune tam.

547
00:24:58,986 --> 00:24:59,860
Profesor: V redu.

548
00:24:59,860 --> 00:25:03,370
Pustimo za nami zdaj
Teoretični svet algoritmov

549
00:25:03,370 --> 00:25:06,520
v asimptotskega analizo
Pogodbe, in se vrniti v nekaterih temah

550
00:25:06,520 --> 00:25:09,940
od tedna nič in ena, in na začetku
odstraniti nekaj koles za usposabljanje,

551
00:25:09,940 --> 00:25:10,450
če hočete.

552
00:25:10,450 --> 00:25:13,241
Tako da boste zares razumeli
v končni fazi od tal navzgor, kar je

553
00:25:13,241 --> 00:25:16,805
dogaja pod pokrovom, ko vas
pisanje, sestavljanje in izvajanje programov.

554
00:25:16,805 --> 00:25:19,680
Spomnimo se zlasti, da je bila ta
prvi program C smo pogledal,

555
00:25:19,680 --> 00:25:22,840
kanonični, preprost program
z menoj, relativno gledano,

556
00:25:22,840 --> 00:25:24,620
pri čemer se natisne, Hello World.

557
00:25:24,620 --> 00:25:27,610
In opozarjajo, da sem rekel, proces
da je izvorna koda gre skozi

558
00:25:27,610 --> 00:25:28,430
je točno to.

559
00:25:28,430 --> 00:25:31,180
Vzameš svojo izvorno kodo, mimo
je skozi prevajalnik, kot Jek,

560
00:25:31,180 --> 00:25:34,650
in ven pride objektno kodo, ki
morda videti takole ničel in enic

561
00:25:34,650 --> 00:25:37,880
da CPU računalnika, centralno
procesna enota ali možganov,

562
00:25:37,880 --> 00:25:39,760
končno razume.

563
00:25:39,760 --> 00:25:42,460
>> Izkazalo se je, da je, da je
malo pretirano poenostavljanje,

564
00:25:42,460 --> 00:25:44,480
da smo zdaj v
Položaj narazen draži

565
00:25:44,480 --> 00:25:46,720
razumeti, kaj je res bilo
dogaja pod pokrovom

566
00:25:46,720 --> 00:25:48,600
vsakič, ko zaženete
Jek, ali bolj na splošno,

567
00:25:48,600 --> 00:25:53,040
vsakič, ko bo program,
uporabo Znamka in CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Še posebej, stvari, kot so
To je prva ustvarila,

569
00:25:56,760 --> 00:25:58,684
ko ste prvič pripravijo svoj program.

570
00:25:58,684 --> 00:26:00,600
Z drugimi besedami, ko vas
vzemite izvorno kodo

571
00:26:00,600 --> 00:26:04,390
in ga prevesti, kaj je prva
se jih dobi na izhodu Jek

572
00:26:04,390 --> 00:26:06,370
je nekaj, kar je znano kot assemblerju.

573
00:26:06,370 --> 00:26:08,990
In v resnici, je videti natanko tako kot je ta.

574
00:26:08,990 --> 00:26:11,170
>> Sem tekel ukaz v
ukazni vrstici prej.

575
00:26:11,170 --> 00:26:16,260
Jek Dash prestolnice s hello.c,
in to ustvaril datoteko

576
00:26:16,260 --> 00:26:19,490
za mene imenovanih hello.s,
znotraj katerega so bili natančno

577
00:26:19,490 --> 00:26:22,290
te vsebine, in malo več
Zgoraj in malo bolj spodaj,

578
00:26:22,290 --> 00:26:25,080
vendar sem dal juiciest
informacije tukaj na zaslonu.

579
00:26:25,080 --> 00:26:29,190
In če pogledate pozorno, boste videli,
vsaj nekaj seznanjeni s ključnimi besedami.

580
00:26:29,190 --> 00:26:31,330
Imamo glavni na vrhu.

581
00:26:31,330 --> 00:26:35,140
Imamo printf navzdol po sredini.

582
00:26:35,140 --> 00:26:38,670
In imamo tudi zdravo svet
poševnica nazaj n v narekovajih spodaj navzdol.

583
00:26:38,670 --> 00:26:42,450
>> In vse ostalo tukaj
je navodila zelo nizki ravni

584
00:26:42,450 --> 00:26:45,500
da CPU računalnika razume.

585
00:26:45,500 --> 00:26:50,090
CPU navodila, ki se premikajo spomin
okoli, da obremenitve strune iz spomina,

586
00:26:50,090 --> 00:26:52,750
in končno, print
stvari na zaslonu.

587
00:26:52,750 --> 00:26:56,780
Zdaj, kaj se zgodi, čeprav po
ta skupščina koda se generira?

588
00:26:56,780 --> 00:26:59,964
Konec koncev, kaj ne, res,
še vedno ustvarjajo objektno kodo.

589
00:26:59,964 --> 00:27:02,630
Toda koraki, ki imajo res
se dogaja pod pokrovom

590
00:27:02,630 --> 00:27:04,180
poglej malo več, kot je ta.

591
00:27:04,180 --> 00:27:08,390
Izvorna koda postane montažo kodo,
ki nato postane objekt številka,

592
00:27:08,390 --> 00:27:11,930
in operativne besede so tukaj, da se
ko zbere svojo izvorno kodo,

593
00:27:11,930 --> 00:27:16,300
ven pride montažo kodo in nato
ko si sestavite svoj sklop kodo,

594
00:27:16,300 --> 00:27:17,800
ven pride objektno kodo.

595
00:27:17,800 --> 00:27:20,360
>> Zdaj Jek je super prefinjen,
kot veliko prevajalniki,

596
00:27:20,360 --> 00:27:23,151
in to ne vse od teh korakov
skupaj, in to ne nujno

597
00:27:23,151 --> 00:27:25,360
izhod katerokoli vmesno
datoteke, ki jih lahko tudi vidite.

598
00:27:25,360 --> 00:27:28,400
Samo sestavlja stvari,
ki je splošni izraz, ki

599
00:27:28,400 --> 00:27:30,000
opisuje ta celoten proces.

600
00:27:30,000 --> 00:27:32,000
Ampak, če si zares želite
da je zlasti tam

601
00:27:32,000 --> 00:27:34,330
veliko več dogaja tudi tam.

602
00:27:34,330 --> 00:27:38,860
>> Ampak kaj je razmisliti tudi zdaj, da tudi
da je super preprost program, hello.c,

603
00:27:38,860 --> 00:27:40,540
imenuje funkcija.

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

605
00:27:41,870 --> 00:27:46,900
Ampak nisem napisal printf, res,
ki prihaja s c, če se tako izrazim.

606
00:27:46,900 --> 00:27:51,139
To je funkcija odpoklic, ki je
prijavljeni v standardnem io.h, ki

607
00:27:51,139 --> 00:27:53,180
Datoteka je glava, ki
je tema, da bomo dejansko

608
00:27:53,180 --> 00:27:55,780
potopite v večjo globino pred dolgo.

609
00:27:55,780 --> 00:27:58,000
Ampak datoteka glave je
običajno spremlja

610
00:27:58,000 --> 00:28:02,920
s kodno dokumentacije, izvorne kode datoteko, tako
podobno kot obstaja standardni io.h.

611
00:28:02,920 --> 00:28:05,930
>> Včasih nazaj, je nekdo,
ali nekoga, tudi napisal

612
00:28:05,930 --> 00:28:11,040
datoteka imenuje standardni io.c, v
ki dejansko opredelitve,

613
00:28:11,040 --> 00:28:15,220
ali izvedbe printf,
in grozde drugih funkcij,

614
00:28:15,220 --> 00:28:16,870
dejansko napisal.

615
00:28:16,870 --> 00:28:22,140
Torej, glede na to, če menimo, da je ob
tukaj na levo, hello.c, da ko

616
00:28:22,140 --> 00:28:26,250
zbrani, nam daje hello.s, četudi
Zvoka ne moti varčevanje v mestu

617
00:28:26,250 --> 00:28:31,360
smo lahko videli, in da je montaža koda
dobi sestavljeni v hello.o, ki

618
00:28:31,360 --> 00:28:34,630
je res, privzeto ime
saj vsakič, ko zbere vir

619
00:28:34,630 --> 00:28:39,350
kodo v kodi, vendar niso
povsem pripravljen, da ga še izvršiti,

620
00:28:39,350 --> 00:28:41,460
ker drugi korak
se mora zgoditi, in ima

621
00:28:41,460 --> 00:28:44,440
je dogajalo v zadnjih nekaj
tednov, morda nevede za vas.

622
00:28:44,440 --> 00:28:47,290
>> Natančneje nekje
v CS50 IDE, in to,

623
00:28:47,290 --> 00:28:49,870
preveč, bo malo
poenostavljanje za trenutek,

624
00:28:49,870 --> 00:28:54,670
je, ali je bila na času,
datoteka z imenom standardni io.c,

625
00:28:54,670 --> 00:28:58,440
da nekdo prevedena v
Standardne io.s ali enakovredno,

626
00:28:58,440 --> 00:29:02,010
da je potem nekdo sestavil
v standardni io.o,

627
00:29:02,010 --> 00:29:04,600
ali pa se izkaže v
nekoliko drugačen datoteka

628
00:29:04,600 --> 00:29:07,220
oblika, ki ima lahko drugačen
datoteka končnico v celoti,

629
00:29:07,220 --> 00:29:11,720
ampak v teoriji in konceptualno, točno
ti koraki se je moralo zgoditi v neki obliki.

630
00:29:11,720 --> 00:29:14,060
Se pravi, da je zdaj
ko pišem program,

631
00:29:14,060 --> 00:29:17,870
hello.c, da samo pravi, zdravo svet,
in jaz sem z uporabo kode nekoga drugega

632
00:29:17,870 --> 00:29:22,480
kot printf, ki je bila Nekoč
Čas, v datoteko imenovano standardno io.c,

633
00:29:22,480 --> 00:29:26,390
potem nekako moram, da mi vzamejo
kodi, moji ničel in enic,

634
00:29:26,390 --> 00:29:29,260
in te osebe objekt
zakonika ali ničel in enic,

635
00:29:29,260 --> 00:29:34,970
in jih nekako povezati v
eno končno datoteko, ki se imenuje zdravo, da

636
00:29:34,970 --> 00:29:38,070
ima vse ničle in
tisti iz moje glavno funkcijo,

637
00:29:38,070 --> 00:29:40,830
in vse ničle
in tisti, za printf.

638
00:29:40,830 --> 00:29:44,900
>> In res, da je prejšnji postopek
imenovana, ki povezuje vaše objektno kodo.

639
00:29:44,900 --> 00:29:47,490
Katerega izhod
je izvršljiva datoteka.

640
00:29:47,490 --> 00:29:49,780
Torej, v pravičnosti v spodnjem
konec dneva, nič

641
00:29:49,780 --> 00:29:52,660
se je spremenilo od enega tedna, ko smo
prvič začeli pripravo programov.

642
00:29:52,660 --> 00:29:55,200
Dejansko, vse to je
dogaja pod pokrovom motorja,

643
00:29:55,200 --> 00:29:57,241
zdaj pa smo v položaju,
kjer bomo lahko dejansko

644
00:29:57,241 --> 00:29:58,794
draži narazen teh različnih korakov.

645
00:29:58,794 --> 00:30:00,710
In res, na koncu
dneva, smo še vedno

646
00:30:00,710 --> 00:30:04,480
Z leve ničel in enic, ki
je pravzaprav velik segue zdaj

647
00:30:04,480 --> 00:30:08,620
drugemu zmožnostjo C, da
smo niso imeli vzvoda najverjetneje

648
00:30:08,620 --> 00:30:11,250
do datuma, ki je znana kot operaterji bitni.

649
00:30:11,250 --> 00:30:15,220
Z drugimi besedami, tako daleč, kadarkoli smo jih
ukvarjal s podatki v C ali spremenljivke v C,

650
00:30:15,220 --> 00:30:17,660
smo imeli stvari, kot so
črke in boje in ins

651
00:30:17,660 --> 00:30:21,990
in hrepeni in dvojice in podobno, vendar
vsi od teh so vsaj osem bitov.

652
00:30:21,990 --> 00:30:25,550
Mi smo še nikoli ni bila sposobna
manipulacijo posameznih bitov,

653
00:30:25,550 --> 00:30:28,970
četudi posamezni bit, smo
Veš, lahko predstavlja 0 in 1.

654
00:30:28,970 --> 00:30:32,640
Zdaj se je izkazalo, da je v C, si
lahko dobite dostop do posameznih bitov,

655
00:30:32,640 --> 00:30:35,530
če veste sintakse,
s katerimi bi dobili na njih.

656
00:30:35,530 --> 00:30:38,010
>> Torej, vzemimo si oglejte
na operaterje bitni.

657
00:30:38,010 --> 00:30:41,700
Torej, na sliki tukaj je nekaj znakov, ki
smo, vrsta, vrsta, videl prej.

658
00:30:41,700 --> 00:30:45,580
Vidim 'in' znak, vertikalni
bar, in še nekateri drugi, kot tudi,

659
00:30:45,580 --> 00:30:49,430
in opozarjajo, da ampersand 'znak
je nekaj, kar smo videli prej.

660
00:30:49,430 --> 00:30:54,060
Logični IN operator, kjer imate
dva izmed njih skupaj, ali logični ALI

661
00:30:54,060 --> 00:30:56,300
operater, kjer vas
imajo dve navpični palici.

662
00:30:56,300 --> 00:31:00,550
Bitni operaterji, ki bomo
glej delujejo na bitih posamično,

663
00:31:00,550 --> 00:31:03,810
Samo uporabite eno 'znak, A
single navpična vrstica je strešica simbol

664
00:31:03,810 --> 00:31:06,620
pride zraven, malo
Tilda, in nato levo

665
00:31:06,620 --> 00:31:08,990
nosilec levi nosilec, ali
Pravica nosilec desno držalo.

666
00:31:08,990 --> 00:31:10,770
Vsak od njih ima različne pomene.

667
00:31:10,770 --> 00:31:11,950
>> V resnici pa si oglejte.

668
00:31:11,950 --> 00:31:16,560
Pojdimo stara šola danes in uporaba
zaslon na dotik iz minulih dni,

669
00:31:16,560 --> 00:31:18,002
znan kot belo ploščo.

670
00:31:18,002 --> 00:31:19,710
In ta beli svet
se dogaja, da nam omogočajo

671
00:31:19,710 --> 00:31:27,360
izraziti nekaj dokaj preprostih simbolov,
oziroma nekaj dokaj enostavne formule,

672
00:31:27,360 --> 00:31:29,560
da bomo lahko potem na koncu
vzvod, da bi

673
00:31:29,560 --> 00:31:33,230
dostop do posameznika
bitov znotraj programa C.

674
00:31:33,230 --> 00:31:34,480
Z drugimi besedami, kaj je to.

675
00:31:34,480 --> 00:31:37,080
Poglejmo najprej pogovor za
moment okoli ampersand,

676
00:31:37,080 --> 00:31:39,560
ki je bitni IN operater.

677
00:31:39,560 --> 00:31:42,130
Z drugimi besedami, to je
operater, ki omogoča

678
00:31:42,130 --> 00:31:45,930
mi je, da imajo spremenljivke LEVI
tipično in spremenljivi desna,

679
00:31:45,930 --> 00:31:50,640
ali posamezna vrednost, da če smo IN
jih skupaj, mi daje končni rezultat.

680
00:31:50,640 --> 00:31:51,560
Torej, kaj mislim?

681
00:31:51,560 --> 00:31:54,840
Če je v programu, morate spremenljivko
da shranjuje eno od teh vrednosti,

682
00:31:54,840 --> 00:31:58,000
ali pa naj bo enostavno, in samo
izpišite ničel in enic posamično,

683
00:31:58,000 --> 00:32:00,940
tukaj je, kako upravljavec ampersand deluje.

684
00:32:00,940 --> 00:32:06,400
0 ampersand 0 se bo enaka 0.

685
00:32:06,400 --> 00:32:07,210
Zdaj, zakaj je to?

686
00:32:07,210 --> 00:32:09,291
>> To je zelo podoben
Logični izrazi,

687
00:32:09,291 --> 00:32:10,540
da smo doslej razpravljali.

688
00:32:10,540 --> 00:32:15,800
Če menite, da po vsem, da je 0
false, 0 je napačna, napačna in lažna

689
00:32:15,800 --> 00:32:18,720
je, kot smo razpravljali
logično, tudi napačne.

690
00:32:18,720 --> 00:32:20,270
Tako smo dobili 0 tudi tukaj.

691
00:32:20,270 --> 00:32:24,390
Če ste vzeli 0 'in' znak
1, dobro, da je preveč,

692
00:32:24,390 --> 00:32:29,890
se bo 0, ker za to
levi izraz bi bilo res ali 1,

693
00:32:29,890 --> 00:32:32,360
da bi morali biti pravi in ​​resnični.

694
00:32:32,360 --> 00:32:36,320
Ampak tukaj imamo false
in res, ali 0 in 1.

695
00:32:36,320 --> 00:32:42,000
Zdaj pa še enkrat, če imamo 1 'znak
0, da je tudi se bo 0,

696
00:32:42,000 --> 00:32:47,240
in če imamo 1 'znak 1,
Končno pa imamo 1 bit.

697
00:32:47,240 --> 00:32:50,340
Torej, z drugimi besedami, ne delaš
kaj zanimivega s tem operaterjem

698
00:32:50,340 --> 00:32:51,850
samo še to ampersand operater.

699
00:32:51,850 --> 00:32:53,780
To je bitni IN operater.

700
00:32:53,780 --> 00:32:57,290
Ampak to so sestavine
preko katerega lahko storimo

701
00:32:57,290 --> 00:32:59,240
zanimivih stvari, kot bomo kmalu videli.

702
00:32:59,240 --> 00:33:02,790
>> Zdaj pa si oglejmo le enotni
navpična vrstica tukaj na desni strani.

703
00:33:02,790 --> 00:33:06,710
Če imam 0, bit in jaz
OR je z, bitni

704
00:33:06,710 --> 00:33:11,030
Operator OR, druga 0 bit,
da se dogaja, da mi 0.

705
00:33:11,030 --> 00:33:17,540
Če vzamem 0 malo in ali pa ga z
A 1 bit, potem pa grem, da bi dobili 1.

706
00:33:17,540 --> 00:33:19,830
In dejansko samo
jasnost, naj gredo nazaj,

707
00:33:19,830 --> 00:33:23,380
tako da moji navpične palice
niso zamenjali za 1 je.

708
00:33:23,380 --> 00:33:26,560
Naj znova vse
moj 1 je malo bolj

709
00:33:26,560 --> 00:33:32,700
jasno, da bomo dostavo glej če
imajo 1 ali 0, da se dogaja, da je 1,

710
00:33:32,700 --> 00:33:39,060
in če imam 1 ali 1, da,
Tudi se dogaja, da se 1.

711
00:33:39,060 --> 00:33:42,900
Tako lahko vidite, je logično, da je OR
Operater se obnaša zelo različno.

712
00:33:42,900 --> 00:33:48,070
To mi daje 0 ali 0 mi daje 0, vendar
vsaka druga kombinacija mi daje 1.

713
00:33:48,070 --> 00:33:52,480
Dokler imam eno 1 v
formula, rezultat se bo 1.

714
00:33:52,480 --> 00:33:55,580
>> V nasprotju z AND
Upravljavec, ampersand,

715
00:33:55,580 --> 00:34:00,940
samo, če imam dva 1 je v
enačba, pa sem dejansko dobil 1 out.

716
00:34:00,940 --> 00:34:02,850
Zdaj je nekaj drugega
Operaterji, kot dobro.

717
00:34:02,850 --> 00:34:04,810
Eden od njih je malo bolj vključeni.

718
00:34:04,810 --> 00:34:07,980
Torej, mi gredo naprej in izbrisati
to, da sprostite nekaj prostora.

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

720
00:34:13,020 --> 00:34:16,460
In dajmo si oglejte na
strešica simbol, samo za trenutek.

721
00:34:16,460 --> 00:34:18,210
To je tipično
Znak lahko vnesete

722
00:34:18,210 --> 00:34:21,420
na tipkovnici skladiščenju Shift in
nato pa eno izmed številk na vrhu vašega ZDA

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

724
00:34:22,250 --> 00:34:26,190
>> Torej, to je izključna
ALI operater, ekskluzivni OR.

725
00:34:26,190 --> 00:34:27,790
Torej smo pravkar videli upravljavec ali.

726
00:34:27,790 --> 00:34:29,348
To je ekskluzivni OR operator.

727
00:34:29,348 --> 00:34:30,639
Kakšna je pravzaprav razlika?

728
00:34:30,639 --> 00:34:34,570
No, kaj je samo pogled na formulo,
in to uporabi kot sestavine v končni fazi.

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

730
00:34:37,690 --> 00:34:39,650
Jaz bom rekel, je vedno 0.

731
00:34:39,650 --> 00:34:41,400
To je definicija XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 se bo 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 se bo 1,
in 1 XOR 1 se bo?

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

735
00:34:59,890 --> 00:35:00,520
Ali desno?

736
00:35:00,520 --> 00:35:01,860
Ne vem.

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

738
00:35:02,810 --> 00:35:04,700
Zdaj, kaj se dogaja tukaj?

739
00:35:04,700 --> 00:35:06,630
No, pomislite na
ime tega operaterja.

740
00:35:06,630 --> 00:35:09,980
Ekskluzivni OR, tako kot
ime, vrsta, kaže,

741
00:35:09,980 --> 00:35:13,940
Odgovor je le bo
A 1, če so vhodi izključujeta,

742
00:35:13,940 --> 00:35:15,560
izključno drugačna.

743
00:35:15,560 --> 00:35:18,170
Torej, tukaj so vhodi so
Isto tako je izhod 0.

744
00:35:18,170 --> 00:35:20,700
Tukaj vložki so
Isto tako je izhod 0.

745
00:35:20,700 --> 00:35:25,640
Tu so rezultati različni, so
ekskluzivni in tako proizvodnja je 1.

746
00:35:25,640 --> 00:35:28,190
Tako da je zelo podobna
IN, je zelo podobna,

747
00:35:28,190 --> 00:35:32,760
oziroma je zelo podoben
ALI, vendar le v ekskluzivni način.

748
00:35:32,760 --> 00:35:36,210
Tole ni več 1,
saj imamo dva 1-jev,

749
00:35:36,210 --> 00:35:38,621
in ne izključno, samo eden od njih.

750
00:35:38,621 --> 00:35:39,120
V redu.

751
00:35:39,120 --> 00:35:40,080
Kaj pa drugi?

752
00:35:40,080 --> 00:35:44,220
No tilda, medtem, je
pravzaprav lepo in preprosto, na srečo.

753
00:35:44,220 --> 00:35:46,410
In to je enočlenska
subjekt, kar pomeni,

754
00:35:46,410 --> 00:35:50,400
to je uporabljena le en vhod,
en operand, tako rekoč.

755
00:35:50,400 --> 00:35:51,800
Ni na levi in ​​desni.

756
00:35:51,800 --> 00:35:56,050
Z drugimi besedami, če ste vzeli tildo za
0, bo odgovor nasprotno.

757
00:35:56,050 --> 00:35:59,710
In če ste vzeli vijuga od 1, je
Odgovor bo nasprotno.

758
00:35:59,710 --> 00:36:02,570
Torej tilda subjekt
način negira bit,

759
00:36:02,570 --> 00:36:06,000
ali flipping malo od
0 do 1, ali 1 do 0.

760
00:36:06,000 --> 00:36:09,820
>> In da nam ostane na koncu
s samo dvema končnih subjektov,

761
00:36:09,820 --> 00:36:13,840
tako imenovani levi premik, in
tako imenovana pravica operater premik.

762
00:36:13,840 --> 00:36:16,620
Oglejmo si oglejte, kako se ti delo.

763
00:36:16,620 --> 00:36:20,780
Leve operater premik, napisano
z dvema kotnih oklepajih kot je ta,

764
00:36:20,780 --> 00:36:22,110
deluje na naslednji način.

765
00:36:22,110 --> 00:36:27,390
Če je moj vložek, ali moj operand, na levi
Operator premik je preprosto 1.

766
00:36:27,390 --> 00:36:33,750
In potem sem povedal, računalnik na
levo premik, ki 1, pravijo sedem krajev,

767
00:36:33,750 --> 00:36:37,150
Rezultat je, kot da I
da to 1, in ga premakniti

768
00:36:37,150 --> 00:36:40,160
sedem krajev več na
levo in ga privzeto,

769
00:36:40,160 --> 00:36:42,270
bomo domnevati, da
prostor na desni strani

770
00:36:42,270 --> 00:36:44,080
se bo oblazinjena z ničlami.

771
00:36:44,080 --> 00:36:50,316
Z drugimi besedami, 1 levo premik 7 se dogaja
da smo dobili mi, da 1, čemur sledi 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Torej, na nek način, to vam omogoča, da
sprejme majhno število kot 1,

774
00:36:57,380 --> 00:37:00,740
in jasno, da je veliko
še veliko večja na ta način,

775
00:37:00,740 --> 00:37:06,460
vendar smo dejansko videli
bolj pameten pristopi k njej

776
00:37:06,460 --> 00:37:08,080
Namesto tega, kot tudi,

777
00:37:08,080 --> 00:37:08,720
>> V redu.

778
00:37:08,720 --> 00:37:10,060
To je to za tri teden.

779
00:37:10,060 --> 00:37:11,400
Vam bomo videli naslednjič.

780
00:37:11,400 --> 00:37:12,770
To je CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [Predvaja glasba]

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1: Bil je na malico
bar jedo vroče polnilom kupo.

784
00:37:25,766 --> 00:37:28,090
On je vse imel čez obraz.

785
00:37:28,090 --> 00:37:30,506
On je nosil čokolado kot brado

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Kaj počneš?

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

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

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Ali ste pravkar double dip?

790
00:37:36,800 --> 00:37:38,585
Vi dvojni kratki čip.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: Oprostite.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: Ti kratki čip, si
vzel grižljaj, in si spet kratki.

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

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Torej, to je kot dajanje
vaše celotno desno usta v dip.

795
00:37:48,440 --> 00:37:52,400
Naslednjič, ko ste vzeli čip,
Samo zamoči enkrat, in ga na koncu.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3: Veš kaj, Dan?

797
00:37:53,890 --> 00:37:58,006
Vi pomočimo način, ki ga želite potopiti.

798
00:37:58,006 --> 00:38:01,900
Bom pomočimo tako da sem želite potopiti.

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