1
00:00:00,000 --> 00:00:11,904
>> [Speel van musiek]

2
00:00:11,904 --> 00:00:12,910
>> PROFESSOR: Alle reg.

3
00:00:12,910 --> 00:00:16,730
Dit is CS50, en dit is
die einde van die week drie.

4
00:00:16,730 --> 00:00:20,230
So ons is hier vandag nie in Sanders
Teater, plaas in Weidner Biblioteek.

5
00:00:20,230 --> 00:00:23,170
Binnekant van wat is 'n ateljee
bekend as Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
of sal ons sê Studio H, of moet
ons say-- as jy dit grap geniet,

7
00:00:28,310 --> 00:00:30,540
dit is eintlik van
klasmaat, Mark, online,

8
00:00:30,540 --> 00:00:32,420
wat soveel via Twitter voorgestel.

9
00:00:32,420 --> 00:00:34,270
Nou wat is koel oor
hier is in 'n ateljee

10
00:00:34,270 --> 00:00:38,410
is dat ek omring deur hierdie groen
mure, 'n groen skerm of chromakey,

11
00:00:38,410 --> 00:00:43,290
om so te praat, wat beteken dat CS50 se
produksie span, buite my

12
00:00:43,290 --> 00:00:47,380
nou, kan wees om
my die meeste enige plek in die wêreld,

13
00:00:47,380 --> 00:00:48,660
vir 'n beter of vir slegter.

14
00:00:48,660 --> 00:00:51,800
>> Nou wat voorlê, probleem stel
twee is in jou hande vir hierdie week,

15
00:00:51,800 --> 00:00:53,830
maar met die probleem sit
drie hierdie komende week,

16
00:00:53,830 --> 00:00:56,600
sal jy uitgedaag word met
die sogenaamde game van 15,

17
00:00:56,600 --> 00:00:58,960
'n ou partytjie guns wat
u sal onthou ontvang

18
00:00:58,960 --> 00:01:02,030
as 'n kind wat 'n hele klomp het
getalle wat kan gly op, af,

19
00:01:02,030 --> 00:01:05,790
links en regs, en daar is een gaping
binne die legkaart, waarin jy

20
00:01:05,790 --> 00:01:07,840
eintlik kan gly diegene stukke van die legkaart.

21
00:01:07,840 --> 00:01:11,150
Uiteindelik jy dit ontvang
legkaart in sommige semi ewekansige volgorde,

22
00:01:11,150 --> 00:01:12,940
en die doel is om
sorteer dit, bo na onder,

23
00:01:12,940 --> 00:01:16,310
links na regs, van die een
al die pad deur 15.

24
00:01:16,310 --> 00:01:19,360
>> Ongelukkig is die implementering
jy het in die hand

25
00:01:19,360 --> 00:01:21,590
gaan wees sagteware
gebaseer is, nie fisies.

26
00:01:21,590 --> 00:01:25,280
Jy eintlik gaan hê om te skryf
kode met wat 'n student of gebruiker kan

27
00:01:25,280 --> 00:01:26,760
speel die spel van die 15.

28
00:01:26,760 --> 00:01:29,030
En in die feit, in die hacker
uitgawe van spel van 15,

29
00:01:29,030 --> 00:01:32,155
jy sal 'n uitdaging om te implementeer,
nie net die speel van hierdie ou skool

30
00:01:32,155 --> 00:01:35,010
spel nie, maar eerder die oplossing
dit, implementering god af,

31
00:01:35,010 --> 00:01:38,280
om so te praat, wat eintlik
los die legkaart vir die mens,

32
00:01:38,280 --> 00:01:41,080
deur hulle te voorsien met 'n wenk,
ná wenk, ná wenk.

33
00:01:41,080 --> 00:01:42,280
Sodat meer op dat die volgende week.

34
00:01:42,280 --> 00:01:43,720
Maar dit is wat voorlê.

35
00:01:43,720 --> 00:01:47,610
>> Vir nou onthou dat vroeër hierdie week
ons het hierdie fotonische lewe, as jy wil,

36
00:01:47,610 --> 00:01:52,560
waardeur die beste wat ons besig was om te sorteer
wyse was 'n bogrens van die groot o van n

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

38
00:01:53,210 --> 00:01:56,520
Met ander woorde, borrelsortering,
seleksie soort, voeg soort,

39
00:01:56,520 --> 00:01:59,120
almal van hulle, terwyl verskillende
in die implementering daarvan,

40
00:01:59,120 --> 00:02:03,480
afgewentel in 'n N kwadraat hardloop
keer in die heel ergste geval.

41
00:02:03,480 --> 00:02:06,010
En ons in die algemeen aanvaar dat
die heel ergste geval vir sortering

42
00:02:06,010 --> 00:02:08,814
is die een wat jou insette
is heeltemal agteruit.

43
00:02:08,814 --> 00:02:11,980
En inderdaad, dit het 'n hele paar stappe
te implementeer elkeen van daardie algoritmes.

44
00:02:11,980 --> 00:02:15,110
>> En aan die einde van die klas
Onthou, ons vergelyk borrelsortering

45
00:02:15,110 --> 00:02:19,390
teen seleksie soort teen mekaar
dat ons geroep merge soort op die oomblik,

46
00:02:19,390 --> 00:02:22,120
en ek stel voor dat dit neem
voordeel van 'n les uit week

47
00:02:22,120 --> 00:02:24,060
nul, verdeel en oorwin.

48
00:02:24,060 --> 00:02:28,810
En een of ander manier 'n soort van die bereiking van
logaritmiese looptyd uiteindelik

49
00:02:28,810 --> 00:02:31,024
in plaas van iets
dit is suiwer kwadratiese.

50
00:02:31,024 --> 00:02:33,440
En dit is nie heeltemal logaritmiese,
dit is 'n bietjie meer as dit.

51
00:02:33,440 --> 00:02:36,520
Maar as jy onthou uit die klas,
dit was baie, baie vinniger.

52
00:02:36,520 --> 00:02:38,210
Kom ons neem 'n blik op waar ons opgehou het.

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

54
00:02:41,880 --> 00:02:45,370
>> Borrel soort versus seleksie
sorteer versus merge soort.

55
00:02:45,370 --> 00:02:47,700
Nou is hulle almal hardloop, in
teorie, op dieselfde tyd.

56
00:02:47,700 --> 00:02:50,510
Die SVE loop teen dieselfde spoed.

57
00:02:50,510 --> 00:02:54,990
Maar jy kan voel hoe vervelig dit
is baie vinnig gaan word,

58
00:02:54,990 --> 00:02:58,790
en net hoe vinnig, wanneer ons spuit
'n bietjie van die week se zero algoritmes,

59
00:02:58,790 --> 00:03:00,080
kan ons vinniger dinge op.

60
00:03:00,080 --> 00:03:01,630
>> So merk soort lyk amazing.

61
00:03:01,630 --> 00:03:05,220
Hoe kan ons dit hefboom, ten einde
om getalle vinniger te sorteer.

62
00:03:05,220 --> 00:03:07,140
Wel, laat ons terugdink
om 'n bestanddeel wat ons

63
00:03:07,140 --> 00:03:10,380
het terug in week nul, dié van
soek vir iemand in 'n telefoon boek,

64
00:03:10,380 --> 00:03:12,380
en onthou dat die
pseudokode dat ons voorgestel

65
00:03:12,380 --> 00:03:14,560
via wat ons kan vind
iemand soos Mike Smith,

66
00:03:14,560 --> 00:03:16,310
kyk 'n bietjie iets soos hierdie.

67
00:03:16,310 --> 00:03:20,820
>> Nou neem 'n blik in die besonder
op reël 7 en 8, en 10 en 11,

68
00:03:20,820 --> 00:03:25,240
wat daardie lus veroorsaak, waardeur ons gehou
terug na lyn 3 gaan weer en weer,

69
00:03:25,240 --> 00:03:26,520
en weer.

70
00:03:26,520 --> 00:03:31,790
Maar dit blyk dat ons kan sien
hierdie algoritme, hier in pseudokode,

71
00:03:31,790 --> 00:03:33,620
'n bietjie meer holisties.

72
00:03:33,620 --> 00:03:35,960
In werklikheid, wat ek soek
om hier op die skerm,

73
00:03:35,960 --> 00:03:41,180
is 'n algoritme vir die soek vir
Mike Smith onder sommige stel bladsye.

74
00:03:41,180 --> 00:03:45,520
En inderdaad, kan ons dit vereenvoudig
algoritme in die lyne 7 en 8,

75
00:03:45,520 --> 00:03:49,860
en 10 en 11 tot net dit te sê,
wat ek hier in geel het aangebied.

76
00:03:49,860 --> 00:03:52,210
Met ander woorde, as Mike
Smith is vroeër in die boek,

77
00:03:52,210 --> 00:03:55,004
Ons hoef nie te stap spesifiseer
stap nou hoe om te gaan hom kry.

78
00:03:55,004 --> 00:03:56,920
Ons hoef nie te spesifiseer
om terug te gaan na lyn 3,

79
00:03:56,920 --> 00:03:58,960
hoekom doen ons nie net plaas,
sê, meer algemeen,

80
00:03:58,960 --> 00:04:01,500
soek Mike in die
links helfte van die boek.

81
00:04:01,500 --> 00:04:03,960
>> Omgekeerd, indien Mike is
eintlik later in die boek,

82
00:04:03,960 --> 00:04:07,540
Daarom het ons nie net te haal unquote search
vir Mike in die regter helfte van die boek.

83
00:04:07,540 --> 00:04:11,030
Met ander woorde, hoekom doen net ons nie
soort liewer onsself sê,

84
00:04:11,030 --> 00:04:13,130
soek Mike in hierdie
subset van die boek,

85
00:04:13,130 --> 00:04:16,279
en laat dit aan ons bestaande
algoritme om ons te vertel

86
00:04:16,279 --> 00:04:18,750
hoe om te soek vir Mike in
wat links die helfte van die boek.

87
00:04:18,750 --> 00:04:20,750
Met ander woorde, ons
algoritme werk of dit nou

88
00:04:20,750 --> 00:04:24,670
'n telefoon boek van hierdie dikte, van hierdie
dikte, of enige dikte hoegenaamd nie.

89
00:04:24,670 --> 00:04:27,826
Sodat ons kan rekursief
definieer hierdie algoritme.

90
00:04:27,826 --> 00:04:29,950
Met ander woorde, die
skerm hier, is 'n algoritme

91
00:04:29,950 --> 00:04:33,130
vir die soek vir Mike Smith
onder die bladsye van 'n telefoon boek.

92
00:04:33,130 --> 00:04:37,410
So in reël 7 en 10, laat
net sê presies dit.

93
00:04:37,410 --> 00:04:40,250
En ek gebruik die term 'n oomblik
gelede, en inderdaad, rekursie

94
00:04:40,250 --> 00:04:42,450
is die modewoord vir nou,
en dit is hierdie proses

95
00:04:42,450 --> 00:04:47,210
van iets sikliese doen deur een of ander manier
die gebruik van kode wat jy reeds het,

96
00:04:47,210 --> 00:04:49,722
en weer 'n beroep nie,
en weer en weer.

97
00:04:49,722 --> 00:04:51,930
Nou gaan dit belangrik wees
dat ons een of ander manier onder

98
00:04:51,930 --> 00:04:53,821
uit en dit nie doen nie oneindig lank.

99
00:04:53,821 --> 00:04:56,070
Is anders gaan ons
het inderdaad 'n oneindige lus.

100
00:04:56,070 --> 00:04:59,810
Maar laat ons kyk of ons hierdie idee kan leen
van 'n rekursie, weer iets doen

101
00:04:59,810 --> 00:05:03,600
en weer en weer, op te los
die sortering probleem via merge

102
00:05:03,600 --> 00:05:05,900
soort, al hoe meer doeltreffend.

103
00:05:05,900 --> 00:05:06,970
>> So ek gee jou soort saam te smelt.

104
00:05:06,970 --> 00:05:07,920
Kom ons neem 'n blik.

105
00:05:07,920 --> 00:05:10,850
So hier is pseudokode, met
wat ons kan implementeer sorteer,

106
00:05:10,850 --> 00:05:12,640
die gebruik van hierdie algoritme genoem merge soort.

107
00:05:12,640 --> 00:05:13,880
En dit is eenvoudig hierdie.

108
00:05:13,880 --> 00:05:15,940
Op insette van n elemente,
Met ander woorde, as jy

109
00:05:15,940 --> 00:05:18,830
gegee N elemente en getalle en
letters of wat ook al die insette is,

110
00:05:18,830 --> 00:05:22,430
as jy gegee N elemente, indien
N is minder as 2, net terug te keer.

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

112
00:05:22,930 --> 00:05:26,430
Want as N is minder as 2, wat
beteken dat my lys van elemente

113
00:05:26,430 --> 00:05:30,446
is een van die grootte 0 of 1, en
in beide van die triviale gevalle

114
00:05:30,446 --> 00:05:31,570
die lys is reeds gesorteer.

115
00:05:31,570 --> 00:05:32,810
As daar geen lys, is dit gesorteer.

116
00:05:32,810 --> 00:05:35,185
En as daar is 'n lys van die lengte
1, is dit natuurlik gesorteer.

117
00:05:35,185 --> 00:05:38,280
So die algoritme moet net
regtig iets interessant te doen,

118
00:05:38,280 --> 00:05:40,870
As ons twee of meer
elemente wat aan ons gegee.

119
00:05:40,870 --> 00:05:42,440
So laat ons kyk na die magie dan.

120
00:05:42,440 --> 00:05:47,500
Anders sorteer die linker helfte van die elemente,
dan sorteer die regter helfte van elemente,

121
00:05:47,500 --> 00:05:49,640
dan saam te smelt die gesorteer helftes.

122
00:05:49,640 --> 00:05:52,440
En wat is soort van gedagte buig
hier, is dat ek nie regtig

123
00:05:52,440 --> 00:05:56,190
lyk om jou gesê het
niks net nog nie, reg?

124
00:05:56,190 --> 00:05:59,560
Al wat ek gesê het is, 'n lys van
N elemente, sorteer die linker helfte,

125
00:05:59,560 --> 00:06:01,800
dan die regter helfte, dan
saamsmelt die gesorteer helftes,

126
00:06:01,800 --> 00:06:03,840
maar waar is die werklike geheime kruie?

127
00:06:03,840 --> 00:06:05,260
Waar is die algoritme?

128
00:06:05,260 --> 00:06:09,150
Wel dit blyk dat die twee lyne
eerste, sorteer gelaat helfte van elemente,

129
00:06:09,150 --> 00:06:13,970
en sorteer regter helfte van elemente,
is rekursiewe oproepe, om so te praat.

130
00:06:13,970 --> 00:06:16,120
>> Na alles, op hierdie
punt in die tyd, het ek

131
00:06:16,120 --> 00:06:18,950
'n algoritme waarmee
sorteer n hele klomp van elemente?

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

133
00:06:19,450 --> 00:06:20,620
Dit is reg hier.

134
00:06:20,620 --> 00:06:25,180
Dit is reg hier op die skerm, en
sodat ek kan dieselfde stel stappe gebruik

135
00:06:25,180 --> 00:06:28,500
aan die linkerkant half sorteer,
as ek kan die regter helfte.

136
00:06:28,500 --> 00:06:30,420
En inderdaad, weer en weer.

137
00:06:30,420 --> 00:06:34,210
So een of ander manier, en ons sal gou
sien dit, die magie van merge soort

138
00:06:34,210 --> 00:06:37,967
ingebed in daardie finale
lyn, die samesmelting van die gesorteerde helftes.

139
00:06:37,967 --> 00:06:39,300
En dit lyk redelik intuïtief.

140
00:06:39,300 --> 00:06:41,050
Jy neem twee helftes, en jy,
een of ander manier, saam te smelt hulle saam,

141
00:06:41,050 --> 00:06:43,260
en ons sal sien
konkreet in 'n oomblik.

142
00:06:43,260 --> 00:06:45,080
>> Maar dit is 'n volledige algoritme.

143
00:06:45,080 --> 00:06:46,640
En laat ons sien presies hoekom.

144
00:06:46,640 --> 00:06:50,912
Wel dink dat ons hierdie selfde is gegee
agt elemente hier op die skerm, die een

145
00:06:50,912 --> 00:06:53,120
deur agt, maar hulle is
in skynbaar ewekansige volgorde.

146
00:06:53,120 --> 00:06:55,320
En die doel aan die hand is
om hierdie elemente te sorteer.

147
00:06:55,320 --> 00:06:58,280
Wel, hoe kan ek gaan
om dit te doen deur gebruik te maak, weer,

148
00:06:58,280 --> 00:07:00,407
saamsmelt soort, soos per die pseudokode?

149
00:07:00,407 --> 00:07:02,740
En weer, ingeworteld dit in
jou gedagtes, want net 'n oomblik.

150
00:07:02,740 --> 00:07:05,270
Die eerste geval is redelik
triviale, as dit is minder as 2,

151
00:07:05,270 --> 00:07:07,060
net terug, daar is geen werk wat gedoen moet word.

152
00:07:07,060 --> 00:07:09,290
So regtig daar is net drie
stappe om werklik in gedagte te hou.

153
00:07:09,290 --> 00:07:11,081
Weer en weer, ek is
gaan wil hê

154
00:07:11,081 --> 00:07:13,980
aan die linkerkant half sorteer,
sorteer die regter helfte,

155
00:07:13,980 --> 00:07:15,890
en dan weer hul
twee helftes is gesorteer,

156
00:07:15,890 --> 00:07:18,710
Ek wil vir hulle saam te smelt
in een gesorteerde lys.

157
00:07:18,710 --> 00:07:19,940
So hou dit in gedagte.

158
00:07:19,940 --> 00:07:21,310
>> So hier is die oorspronklike lys.

159
00:07:21,310 --> 00:07:23,510
Kom ons hanteer dit as 'n
skikking, as ons begin om

160
00:07:23,510 --> 00:07:25,800
in week twee, wat is 'n
aangrensende blok van die geheue.

161
00:07:25,800 --> 00:07:28,480
In hierdie geval, met agt
getalle, rug aan rug aan rug.

162
00:07:28,480 --> 00:07:30,700
En laat ons nou aansoek merge soort.

163
00:07:30,700 --> 00:07:33,300
So ek wil eers te sorteer
die linker helfte van hierdie lys,

164
00:07:33,300 --> 00:07:37,370
en laat ons dus
fokus op 4, 8, 6, en 2.

165
00:07:37,370 --> 00:07:41,000
>> Nou hoe gaan ek te werk
sorteer 'n lys van die grootte 4?

166
00:07:41,000 --> 00:07:45,990
Wel, ek het nou oorweeg
sorteer die linkerkant van die linker helfte.

167
00:07:45,990 --> 00:07:47,720
Weereens, laat ons rewind vir net 'n oomblik.

168
00:07:47,720 --> 00:07:51,010
As die pseudokode is dit,
en ek het agt elemente,

169
00:07:51,010 --> 00:07:53,230
8 is natuurlik groter
as of gelyk aan 2.

170
00:07:53,230 --> 00:07:54,980
So met die eerste geval is nie van toepassing.

171
00:07:54,980 --> 00:07:58,120
So agt elemente te sorteer, ek eerste
sorteer die linker helfte van die elemente

172
00:07:58,120 --> 00:08:01,930
dan het ek sorteer die regter helfte, dan smelt ek
Die twee helftes gesorteer, elke grootte 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Maar as jy my net vertel het, sorteer die
linkerhelfte, wat nou van die grootte 4,

175
00:08:07,480 --> 00:08:09,350
hoe kan ek die linkerkant half sorteer?

176
00:08:09,350 --> 00:08:11,430
Wel, as ek 'n
insette van vier elemente,

177
00:08:11,430 --> 00:08:14,590
Ek het eers sorteer links
twee, dan is die regte twee

178
00:08:14,590 --> 00:08:16,210
en dan het ek hulle saam te smelt.

179
00:08:16,210 --> 00:08:18,700
So weer, raak dit 'n bietjie
van 'n gedagte buig spel hier,

180
00:08:18,700 --> 00:08:21,450
omdat jy, soort, moet
onthou waar jy is in die storie,

181
00:08:21,450 --> 00:08:23,620
maar aan die einde van die dag,
gegee 'n aantal van die elemente,

182
00:08:23,620 --> 00:08:25,620
jy eers wil die sorteer
linkerhelfte, dan die regter helfte,

183
00:08:25,620 --> 00:08:26,661
dan saam te smelt hulle saam.

184
00:08:26,661 --> 00:08:28,630
Kom ons begin om presies dit te doen.

185
00:08:28,630 --> 00:08:30,170
Hier is die insette van agt elemente.

186
00:08:30,170 --> 00:08:31,910
Nou is ons op soek na die linker helfte hier.

187
00:08:31,910 --> 00:08:33,720
Hoe sorteer ek vier elemente?

188
00:08:33,720 --> 00:08:35,610
Wel, ek eerste sorteer links helfte.

189
00:08:35,610 --> 00:08:37,720
Nou hoe kan ek die linkerkant half sorteer?

190
00:08:37,720 --> 00:08:39,419
Wel, ek het gegee is twee elemente.

191
00:08:39,419 --> 00:08:41,240
So laat sorteer hierdie twee elemente.

192
00:08:41,240 --> 00:08:44,540
2 groter as of
gelyk aan 2, natuurlik.

193
00:08:44,540 --> 00:08:46,170
Sodat eerste geval nie van toepassing nie.

194
00:08:46,170 --> 00:08:49,010
>> So ek het nou aan die linkerkant sorteer
helfte van hierdie twee elemente.

195
00:08:49,010 --> 00:08:50,870
Die linker helfte, natuurlik, is net 4.

196
00:08:50,870 --> 00:08:54,020
So hoe kan ek 'n lys van 'n element te sorteer?

197
00:08:54,020 --> 00:08:57,960
Wel nou, wat spesiale basis geval
up top, om so te praat, is van toepassing.

198
00:08:57,960 --> 00:09:01,470
1 is minder as 2, en my
lys is inderdaad grootte 1.

199
00:09:01,470 --> 00:09:02,747
So het ek net terug te keer.

200
00:09:02,747 --> 00:09:03,580
Ek het nie iets te doen.

201
00:09:03,580 --> 00:09:06,770
En inderdaad, kyk wat ek het
gedoen het, is reeds 4 gesorteer.

202
00:09:06,770 --> 00:09:09,220
Soos ek is reeds
gedeeltelik suksesvol hier.

203
00:09:09,220 --> 00:09:11,750
>> Nou wat blyk soort van dom
te eis nie, maar dit is waar.

204
00:09:11,750 --> 00:09:13,700
4 is 'n lys van die grootte 1.

205
00:09:13,700 --> 00:09:15,090
Dit is reeds gesorteer.

206
00:09:15,090 --> 00:09:16,270
Dit is die linker helfte.

207
00:09:16,270 --> 00:09:18,010
Nou het ek sorteer die regter helfte.

208
00:09:18,010 --> 00:09:22,310
My insette is een element, 8
Net so, reeds gesorteer.

209
00:09:22,310 --> 00:09:25,170
Dom ook, maar weer,
hierdie basiese beginsel

210
00:09:25,170 --> 00:09:28,310
gaan ons toelaat om nou te bou
op die top van dit suksesvol.

211
00:09:28,310 --> 00:09:32,260
4 gesorteer, 8 gesorteer nou
wat was die laaste stap?

212
00:09:32,260 --> 00:09:35,330
So het die derde en finale stap, enige
tyd wat jy 'n lys te sorteer, onthou,

213
00:09:35,330 --> 00:09:38,310
was om die twee helftes saam te smelt,
links en regs.

214
00:09:38,310 --> 00:09:39,900
So kom ons doen presies dit.

215
00:09:39,900 --> 00:09:41,940
My linker helfte is, natuurlik, 4.

216
00:09:41,940 --> 00:09:43,310
My reg helfte is 8.

217
00:09:43,310 --> 00:09:44,100
>> So laat dit doen.

218
00:09:44,100 --> 00:09:46,410
Eerste gaan ek ken
'n paar ekstra geheue,

219
00:09:46,410 --> 00:09:48,680
dat ek sal hier verteenwoordig,
as net 'n sekondêre skikking,

220
00:09:48,680 --> 00:09:49,660
dit is groot genoeg om hierdie te pas.

221
00:09:49,660 --> 00:09:52,243
Maar jy kan dink uitbreiding
dat reghoek die hele lengte,

222
00:09:52,243 --> 00:09:53,290
as ons moet meer later.

223
00:09:53,290 --> 00:09:58,440
Hoe kan ek dit neem 4 en 8, en voeg
daardie twee lyste van grootte 1 saam?

224
00:09:58,440 --> 00:10:00,270
Ook hier eenvoudig.

225
00:10:00,270 --> 00:10:03,300
4 kom eerste, dan kom 8.

226
00:10:03,300 --> 00:10:07,130
Want as ek wil die sorteer
linkerhelfte, dan die regter helfte,

227
00:10:07,130 --> 00:10:09,900
en dan saam te smelt die twee helftes
saam in gesorteerde volgorde,

228
00:10:09,900 --> 00:10:11,940
4 kom eerste, dan kom 8.

229
00:10:11,940 --> 00:10:15,810
>> So lyk ons ​​maak vordering, selfs
al het ek nie gedoen het nie enige werklike werk.

230
00:10:15,810 --> 00:10:17,800
Maar onthou waar ons is in die storie.

231
00:10:17,800 --> 00:10:19,360
Ons het oorspronklik agt elemente.

232
00:10:19,360 --> 00:10:21,480
Ons gesorteer links helfte, wat is 4.

233
00:10:21,480 --> 00:10:24,450
Dan gesorteer ons die linker helfte
van die linker helfte, wat 2 was.

234
00:10:24,450 --> 00:10:25,270
En hier gaan ons.

235
00:10:25,270 --> 00:10:26,920
Ons klaar met daardie stap.

236
00:10:26,920 --> 00:10:29,930
>> So as ons gesorteer die
gelaat helfte van 2, nou is ons

237
00:10:29,930 --> 00:10:32,130
het die reg om die helfte van 2 sorteer.

238
00:10:32,130 --> 00:10:35,710
So het die regter helfte van 2 is
hierdie twee waardes hier, 6 en 2.

239
00:10:35,710 --> 00:10:40,620
So laat neem nou 'n inset van grootte
2, en sorteer die linker helfte, en dan

240
00:10:40,620 --> 00:10:42,610
die regter helfte, en dan
voeg hulle saam.

241
00:10:42,610 --> 00:10:45,722
Goed hoe sorteer ek 'n lys van die grootte
1, wat net die nommer 6?

242
00:10:45,722 --> 00:10:46,430
Ek is reeds gedoen.

243
00:10:46,430 --> 00:10:48,680
Dat die lys van die grootte 1 gesorteer.

244
00:10:48,680 --> 00:10:52,140
>> Hoe kan ek 'n lys van sorteer
grootte 1, die sogenaamde reg helfte.

245
00:10:52,140 --> 00:10:54,690
Wel dit ook reeds gesorteer.

246
00:10:54,690 --> 00:10:56,190
Die nommer 2 is alleen.

247
00:10:56,190 --> 00:11:00,160
So nou het ek twee helftes, links en
reg, ek moet hulle saam te smelt.

248
00:11:00,160 --> 00:11:01,800
Kom ek gee myself 'n paar ekstra ruimte.

249
00:11:01,800 --> 00:11:05,580
En sit 2 in daar,
dan 6 daar, en sodoende

250
00:11:05,580 --> 00:11:10,740
sorteer die lys, links en regs,
en die samesmelting saam, uiteindelik.

251
00:11:10,740 --> 00:11:12,160
So ek is in 'n effens beter vorm.

252
00:11:12,160 --> 00:11:16,250
Ek is nie gedoen nie, want duidelik 4, 8, 2,
6 is nie die finale bestel wat ek wil.

253
00:11:16,250 --> 00:11:20,640
Maar ek het nou twee lyste van grootte 2, wat
albei, onderskeidelik, is gesorteer.

254
00:11:20,640 --> 00:11:24,580
So nou as jy rewind in jou gedagtes se
oog was, waar het dit ons?

255
00:11:24,580 --> 00:11:28,520
Ek het begin met agt elemente, dan sal ek
Uiteindelik is dit af na die linker helfte van 4,

256
00:11:28,520 --> 00:11:31,386
dan is die linker helfte van 2, en
dan is die regter helfte van 2,

257
00:11:31,386 --> 00:11:34,510
Ek klaar dus sorteer links
helfte van 2, en die regter helfte van 2,

258
00:11:34,510 --> 00:11:37,800
so wat is die derde en laaste stap hier?

259
00:11:37,800 --> 00:11:41,290
Ek het om saam te smelt
twee lyste van grootte 2.

260
00:11:41,290 --> 00:11:42,040
So laat ons gaan voort.

261
00:11:42,040 --> 00:11:43,940
En op die skerm hier, gee
my 'n paar ekstra geheue,

262
00:11:43,940 --> 00:11:47,170
al tegnies, sien dat Ek het
het 'n hele klomp van die leë ruimte op die top

263
00:11:47,170 --> 00:11:47,670
daar is.

264
00:11:47,670 --> 00:11:50,044
As ek wil veral wees
doeltreffende ruimte wys,

265
00:11:50,044 --> 00:11:52,960
Ek kon net begin beweeg die elemente
heen en weer, bo en onder.

266
00:11:52,960 --> 00:11:55,460
Maar net vir visuele helderheid,
Ek gaan dit hier neer te sit,

267
00:11:55,460 --> 00:11:56,800
om dinge mooi en skoon te hou.

268
00:11:56,800 --> 00:11:58,150
>> So ek het twee lyste van grootte 2.

269
00:11:58,150 --> 00:11:59,770
Die eerste lys het 4 en 8.

270
00:11:59,770 --> 00:12:01,500
Die tweede lys het 2 en 6.

271
00:12:01,500 --> 00:12:03,950
Kom ons saamsmelt diegene
saam in gesorteerde volgorde.

272
00:12:03,950 --> 00:12:09,910
2, natuurlik, kom eerste,
dan 4, dan 6, dan 8.

273
00:12:09,910 --> 00:12:12,560
En nou lyk ons ​​te wees om
iewers interessant.

274
00:12:12,560 --> 00:12:15,720
Nou het ek gesorteer helfte van die
lys, en toevallig, dit is

275
00:12:15,720 --> 00:12:18,650
al die ewe getalle nie, maar dat
is inderdaad net 'n toeval.

276
00:12:18,650 --> 00:12:22,220
En ek nou links het gesorteer
helfte, sodat dit is 2, 4, 6 en 8.

277
00:12:22,220 --> 00:12:23,430
Niks is buite orde.

278
00:12:23,430 --> 00:12:24,620
Dit voel soos die gang.

279
00:12:24,620 --> 00:12:26,650
>> Nou is dit voel soos ek het
praat nou vir ewig,

280
00:12:26,650 --> 00:12:29,850
so wat is nog te sien of dit
algoritme is inderdaad meer doeltreffend.

281
00:12:29,850 --> 00:12:31,766
Maar ons gaan deur middel van
dit super metodies.

282
00:12:31,766 --> 00:12:34,060
'N rekenaar, natuurlik,
sou dit doen soos dit.

283
00:12:34,060 --> 00:12:34,840
So waar is ons?

284
00:12:34,840 --> 00:12:36,180
Ons het begin met agt elemente.

285
00:12:36,180 --> 00:12:37,840
Ek gesorteer links helfte van 4.

286
00:12:37,840 --> 00:12:39,290
Dit lyk asof ek gedoen word met dit.

287
00:12:39,290 --> 00:12:42,535
So nou is die volgende stap is om
sorteer die regter helfte van 4.

288
00:12:42,535 --> 00:12:44,410
En hierdie deel ons kan gaan
deur 'n bietjie meer

289
00:12:44,410 --> 00:12:47,140
vinnig, maar jy is
welkom om rewind of breek, net

290
00:12:47,140 --> 00:12:49,910
dink deur dit op
jou eie pas, maar wat

291
00:12:49,910 --> 00:12:53,290
ons het nou 'n geleentheid om
doen presies dieselfde algoritme op vier

292
00:12:53,290 --> 00:12:54,380
verskillende getalle.

293
00:12:54,380 --> 00:12:57,740
>> So laat ons gaan voort, en fokus op
die regter helfte, wat ons hier is.

294
00:12:57,740 --> 00:13:01,260
Die linker helfte van daardie
reg helfte, en nou is die

295
00:13:01,260 --> 00:13:04,560
linkerhelfte van die linker
helfte van daardie reg helfte,

296
00:13:04,560 --> 00:13:08,030
en hoe kan ek sorteer 'n lys van die grootte
1 met net die nommer 1?

297
00:13:08,030 --> 00:13:09,030
Dit is reeds gedoen.

298
00:13:09,030 --> 00:13:11,830
Hoe kan ek dieselfde vir 'n lys te doen
grootte 1 bevat net 7?

299
00:13:11,830 --> 00:13:12,840
Dit is reeds gedoen.

300
00:13:12,840 --> 00:13:16,790
Stap drie vir hierdie half dan
is om hierdie twee elemente saam te voeg

301
00:13:16,790 --> 00:13:20,889
in 'n nuwe lys van grootte 2, 1 en 7.

302
00:13:20,889 --> 00:13:23,180
Lyk nie al gedoen het
dat baie interessante werk.

303
00:13:23,180 --> 00:13:24,346
Kom ons kyk wat gebeur volgende.

304
00:13:24,346 --> 00:13:29,210
Ek het net gesorteer links die helfte van die
regter helfte van my oorspronklike insette.

305
00:13:29,210 --> 00:13:32,360
Nou laat sorteer die regte
helfte, wat 5 en 3 bevat.

306
00:13:32,360 --> 00:13:35,740
Kom ons kyk weer na die links
helfte, gesorteer, reg helfte, gesorteer,

307
00:13:35,740 --> 00:13:39,120
en voeg die twee saam,
in 'n paar ekstra ruimte,

308
00:13:39,120 --> 00:13:41,670
3 kom eerste, dan kom 5.

309
00:13:41,670 --> 00:13:46,190
En so nou het ons die gesorteer
links helfte van die regter helfte

310
00:13:46,190 --> 00:13:49,420
van die oorspronklike probleem, en
die regter helfte van die regter helfte

311
00:13:49,420 --> 00:13:50,800
van die oorspronklike probleem.

312
00:13:50,800 --> 00:13:52,480
Wat is die derde en finale stap?

313
00:13:52,480 --> 00:13:54,854
Wel om die twee helftes saam te smelt.

314
00:13:54,854 --> 00:13:57,020
So laat ek myself kry 'n paar
ekstra ruimte, maar, weer, ek

315
00:13:57,020 --> 00:13:58,699
kan wees dat die gebruik van vrye ruimte op die top.

316
00:13:58,699 --> 00:14:00,490
Maar ons gaan hou
dit eenvoudig visueel.

317
00:14:00,490 --> 00:14:07,070
Laat my saamsmelt nou 1, en
dan 3, en dan 5, en dan 7.

318
00:14:07,070 --> 00:14:10,740
Daardeur laat my nou met die
regter helfte van die oorspronklike probleem

319
00:14:10,740 --> 00:14:12,840
dit is perfek gesorteer.

320
00:14:12,840 --> 00:14:13,662
>> So, wat bly?

321
00:14:13,662 --> 00:14:16,120
Ek voel soos ek sê hou die
dieselfde dinge weer en weer,

322
00:14:16,120 --> 00:14:18,700
maar dit is 'n weerspieëling van die
feit dat ons gebruik rekursie.

323
00:14:18,700 --> 00:14:21,050
Die proses van die gebruik van 'n
algoritme weer en weer,

324
00:14:21,050 --> 00:14:23,940
op kleiner onderafdelings van
die oorspronklike probleem.

325
00:14:23,940 --> 00:14:27,580
So ek nou 'n links gesorteer
die helfte van die oorspronklike probleem.

326
00:14:27,580 --> 00:14:30,847
Ek het 'n reg gesorteer helfte
van die oorspronklike probleem.

327
00:14:30,847 --> 00:14:32,180
Wat is die derde en laaste stap?

328
00:14:32,180 --> 00:14:33,590
O, dit is die samesmelting.

329
00:14:33,590 --> 00:14:34,480
So laat dit te doen.

330
00:14:34,480 --> 00:14:36,420
Kom ons wys 'n paar ekstra
geheue, maar my God, ons

331
00:14:36,420 --> 00:14:37,503
kan dit oral nou sit.

332
00:14:37,503 --> 00:14:40,356
Ons het so baie ruimte beskikbaar
aan ons, maar ons sal dit eenvoudig te hou.

333
00:14:40,356 --> 00:14:42,730
In plaas van om terug te gaan en
saam met ons oorspronklike geheue,

334
00:14:42,730 --> 00:14:44,480
laat ons net dit doen
visueel af hier onder,

335
00:14:44,480 --> 00:14:47,240
om te voltooi die samesmelting van die
linkerhelfte en die regter helfte.

336
00:14:47,240 --> 00:14:49,279
>> So deur die samesmelting, wat moet ek doen?

337
00:14:49,279 --> 00:14:50,820
Ek wil die elemente in orde.

338
00:14:50,820 --> 00:14:53,230
So kyk na die linker helfte,
Ek sien die eerste getal is 2.

339
00:14:53,230 --> 00:14:55,230
Ek kyk na die regter helfte,
Ek sien die eerste getal

340
00:14:55,230 --> 00:14:58,290
is 1, so natuurlik wat
aantal wil ek uitpluk,

341
00:14:58,290 --> 00:15:00,430
en eerste in my finale lys?

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

343
00:15:01,449 --> 00:15:02,990
Nou wil ek dieselfde vraag vra.

344
00:15:02,990 --> 00:15:05,040
Op die linker helfte, ek het
nog steeds die nommer 2.

345
00:15:05,040 --> 00:15:07,490
Op die regte helfte,
Ek het die nommer 3.

346
00:15:07,490 --> 00:15:08,930
Watter een wil ek kies?

347
00:15:08,930 --> 00:15:11,760
Natuurlik, nommer 2 En
Let nou op die kandidate

348
00:15:11,760 --> 00:15:13,620
4 aan die linkerkant, 3 aan die regterkant.

349
00:15:13,620 --> 00:15:15,020
Kom ons, natuurlik, kies 3.

350
00:15:15,020 --> 00:15:18,020
Nou is die kandidate op 4
links, 5 aan die regterkant.

351
00:15:18,020 --> 00:15:19,460
Ons, natuurlik, kies 4.

352
00:15:19,460 --> 00:15:21,240
6 aan die linkerkant, 5 aan die regterkant.

353
00:15:21,240 --> 00:15:22,730
Ons, natuurlik, kies 5.

354
00:15:22,730 --> 00:15:25,020
6 aan die linkerkant, 7 aan die regterkant.

355
00:15:25,020 --> 00:15:29,320
Ons kies 6, en dan sal ons
kies 7, en dan kies ons 8.

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

357
00:15:30,100 --> 00:15:34,370
>> So 'n groot aantal woorde later, het ons
hierdie lys van agt elemente gesorteer

358
00:15:34,370 --> 00:15:38,450
in 'n lys van die een deur agt,
dit is die verhoging met elke stap,

359
00:15:38,450 --> 00:15:40,850
maar hoeveel tyd het
dit ons neem om dit te doen.

360
00:15:40,850 --> 00:15:43,190
Wel, ek het doelbewus
gelê dinge uit picturaal

361
00:15:43,190 --> 00:15:46,330
hier, sodat ons kan soort van
sien of waardeer die afdeling

362
00:15:46,330 --> 00:15:49,060
verower wat alreeds gebeur.

363
00:15:49,060 --> 00:15:52,830
>> Inderdaad as jy terug kyk op die nasleep,
Ek het al hierdie stippellyne gelaat

364
00:15:52,830 --> 00:15:55,660
in houers plek, jy kan,
soort, sien, in omgekeerde volgorde,

365
00:15:55,660 --> 00:15:58,800
as jy soort van terug kyk in
geskiedenis nou, my oorspronklike lys

366
00:15:58,800 --> 00:16:00,250
is, natuurlik, grootte 8.

367
00:16:00,250 --> 00:16:03,480
En dan voorheen, was ek
met twee lyste van grootte 4,

368
00:16:03,480 --> 00:16:08,400
en dan vier lyste van grootte 2,
en dan agt lyste van grootte 1.

369
00:16:08,400 --> 00:16:10,151
>> So, wat dit doen,
soort, herinner u aan?

370
00:16:10,151 --> 00:16:11,858
Wel, wel, enige van
die algoritmes ons het

371
00:16:11,858 --> 00:16:14,430
gekyk dusver waar ons
verdeel, en verdeel, en verdeel,

372
00:16:14,430 --> 00:16:19,500
hou met dinge weer en
weer lei tot hierdie algemene idee.

373
00:16:19,500 --> 00:16:23,100
En dus is daar iets
logaritmiese hier aangaan nie.

374
00:16:23,100 --> 00:16:26,790
En dit is nie heeltemal log van n, maar
daar is 'n logaritmiese komponent

375
00:16:26,790 --> 00:16:28,280
wat ons net gedoen het.

376
00:16:28,280 --> 00:16:31,570
>> Nou laat ons kyk hoe dit eintlik is.

377
00:16:31,570 --> 00:16:34,481
So teken van n, was weer
'n groot loop van tyd,

378
00:16:34,481 --> 00:16:36,980
wanneer ons het iets soos
binêre soek, soos ons nou noem,

379
00:16:36,980 --> 00:16:40,090
die Verdeel en oorwin strategie
via wat ons gevind Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Nou tegnies.

381
00:16:41,020 --> 00:16:43,640
Dit is log basis 2 van n, selfs
maar in die meeste wiskunde klasse,

382
00:16:43,640 --> 00:16:45,770
10 is gewoonlik die basis dat jy aanvaar.

383
00:16:45,770 --> 00:16:48,940
Maar die rekenaar wetenskaplikes byna altyd
dink en praat in terme van die basis 2,

384
00:16:48,940 --> 00:16:52,569
sodat ons oor die algemeen net log van sê
n, in plaas van log basis 2 van n,

385
00:16:52,569 --> 00:16:55,110
maar hulle is presies een en die
dieselfde in die wêreld van die rekenaar

386
00:16:55,110 --> 00:16:57,234
wetenskap, en as 'n eenkant,
daar is 'n konstante faktor

387
00:16:57,234 --> 00:17:01,070
verskil tussen die twee, so dit is
akademiese vraag in elk geval, vir meer formele redes.

388
00:17:01,070 --> 00:17:04,520
>> Maar vir nou, wat ons omgee
oor is hierdie voorbeeld.

389
00:17:04,520 --> 00:17:08,520
So laat ons nie te bewys deur byvoorbeeld nie, maar op
minste gebruik 'n voorbeeld van die getalle

390
00:17:08,520 --> 00:17:10,730
aan die hand as 'n gesonde verstand tjek, as jy wil.

391
00:17:10,730 --> 00:17:14,510
So voorheen die formule was log basis
2 van n, maar wat is n in hierdie geval.

392
00:17:14,510 --> 00:17:18,526
Ek het n oorspronklike nommers, of 8
van oorspronklike getal spesifiek.

393
00:17:18,526 --> 00:17:20,359
Nou is dit 'n bietjie was
rukkie, maar ek is redelik

394
00:17:20,359 --> 00:17:25,300
seker dat log basis 2
van die waarde 8 is 3,

395
00:17:25,300 --> 00:17:29,630
en inderdaad, wat is lekker oor wat
wat 3 is presies die aantal kere

396
00:17:29,630 --> 00:17:33,320
dat jy 'n lys kan verdeel
lengte van 8 weer en weer,

397
00:17:33,320 --> 00:17:36,160
en weer totdat jy links is
met lyste van net 1 grote.

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

399
00:17:36,660 --> 00:17:40,790
8 gaan 4, gaan na 2,
gaan na 1, en dit is

400
00:17:40,790 --> 00:17:43,470
weerspieël presies dit
prentjie wat ons het net 'n oomblik gelede.

401
00:17:43,470 --> 00:17:47,160
So 'n bietjie gesonde verstand gaan oor waar
die logaritme is eintlik betrokke is.

402
00:17:47,160 --> 00:17:50,180
>> So nou, wat anders is hier betrokke? n.

403
00:17:50,180 --> 00:17:53,440
So sien dat elke
tyd wat ek verdeel die lys,

404
00:17:53,440 --> 00:17:58,260
al is dit in omgekeerde volgorde in die geskiedenis
hier, ek is nog steeds n dinge doen.

405
00:17:58,260 --> 00:18:02,320
Dit samesmelting stap vereis dat
Ek raak elke een van die getalle,

406
00:18:02,320 --> 00:18:05,060
ten einde dit te skuif in
sy toepaslike plek.

407
00:18:05,060 --> 00:18:10,760
So selfs al is die hoogte van hierdie
diagram is van die grootte log N van N of 3,

408
00:18:10,760 --> 00:18:13,860
spesifiek, met ander woorde,
Ek het hier drie afdelings.

409
00:18:13,860 --> 00:18:18,800
Hoeveel werk het ek gedoen horisontaal
langs hierdie grafiek elke keer?

410
00:18:18,800 --> 00:18:21,110
>> Wel, ek het n stappe van
werk, want as ek het

411
00:18:21,110 --> 00:18:24,080
het vier elemente en vier elemente,
en ek nodig het om hulle saam te smelt.

412
00:18:24,080 --> 00:18:26,040
Ek nodig het om te gaan deur
hierdie vier en hierdie vier,

413
00:18:26,040 --> 00:18:28,123
uiteindelik tot hulle saamsmelt
terug in agt elemente.

414
00:18:28,123 --> 00:18:32,182
As omgekeerd ek agt vingers het
hier, wat ek nie doen nie, en agt

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- as ek
het vier vingers hier,

416
00:18:34,390 --> 00:18:37,380
wat ek doen, vier vingers
hier, wat ek doen,

417
00:18:37,380 --> 00:18:40,590
dan is dit dieselfde
byvoorbeeld as voorheen, as ek dit doen

418
00:18:40,590 --> 00:18:44,010
het agt vingers al in
totaal, wat ek kan, soort, te doen.

419
00:18:44,010 --> 00:18:47,950
Ek kan presies doen hier,
Dan kan ek beslis

420
00:18:47,950 --> 00:18:50,370
saamsmelt al hierdie lyste
grootte 1 saam.

421
00:18:50,370 --> 00:18:54,050
Maar ek het beslis te kyk
by elke element presies een keer.

422
00:18:54,050 --> 00:18:59,640
So het die hoogte van hierdie proses is log n,
die breedte van hierdie proses, om so te praat,

423
00:18:59,640 --> 00:19:02,490
is N, so wat ons lyk
om uiteindelik is

424
00:19:02,490 --> 00:19:06,470
'n lopende tyd van grootte n keer inteken n.

425
00:19:06,470 --> 00:19:08,977
>> Met ander woorde, ons verdeel
die lys, log N tye,

426
00:19:08,977 --> 00:19:11,810
maar elke keer het ons dit gedoen het, het ons
aan elkeen van die elemente raak

427
00:19:11,810 --> 00:19:13,560
ten einde hulle saamsmelt
almal saam, wat

428
00:19:13,560 --> 00:19:18,120
is N stap, so ons het n keer inteken n,
of as 'n rekenaar wetenskaplike sou sê,

429
00:19:18,120 --> 00:19:20,380
asimptoties, wat
sou die groot woord

430
00:19:20,380 --> 00:19:22,810
na die boonste beskryf
gebind op 'n lopende tyd

431
00:19:22,810 --> 00:19:28,010
ons hardloop in 'n groot o
log N tyd, so te praat.

432
00:19:28,010 --> 00:19:31,510
>> Nou is dit belangrik, want
onthou wat die loop tye was

433
00:19:31,510 --> 00:19:34,120
met borrelsortering, en seleksie
soort, en voeg soort,

434
00:19:34,120 --> 00:19:38,200
en selfs 'n paar ander wat bestaan,
N kwadraat was waar ons was op.

435
00:19:38,200 --> 00:19:39,990
En jy kan, soort, kyk hierdie hier.

436
00:19:39,990 --> 00:19:45,720
As n vierkant is natuurlik n keer
N, maar hier het ons n keer inteken n,

437
00:19:45,720 --> 00:19:48,770
en ons weet reeds van week
nul, dat log n, die logaritmiese,

438
00:19:48,770 --> 00:19:50,550
is beter as iets lineêre.

439
00:19:50,550 --> 00:19:52,930
Na alles, onthou die prentjie
met die rooi en die geel

440
00:19:52,930 --> 00:19:56,500
en die groen lyne wat ons het, is die
groen logaritmiese lyn was baie laer.

441
00:19:56,500 --> 00:20:00,920
En dus baie beter en vinniger
as die reguit geel en rooi lyne,

442
00:20:00,920 --> 00:20:05,900
N tye aanteken N is inderdaad 'n beter
as n keer n, of n vierkant.

443
00:20:05,900 --> 00:20:09,110
>> So lyk ons ​​het
geïdentifiseer n algoritme merge

444
00:20:09,110 --> 00:20:11,870
soort wat in baie loop
vinniger tyd, en inderdaad,

445
00:20:11,870 --> 00:20:16,560
dit is hoekom, het vroeër hierdie week, toe
het ons gesien dat kompetisie tussen borrel

446
00:20:16,560 --> 00:20:20,750
soort, seleksie soort, en voeg
sorteer saamsmelt soort regtig, regtig gewen het.

447
00:20:20,750 --> 00:20:23,660
En inderdaad, ons het nie eens wag
vir borrelsortering en seleksie soort

448
00:20:23,660 --> 00:20:24,790
om klaar te maak.

449
00:20:24,790 --> 00:20:27,410
>> Nou laat neem een ​​ander pass
na hierdie, van 'n effens meer

450
00:20:27,410 --> 00:20:31,030
formele perspektief, net in
geval, dit resoneer beter

451
00:20:31,030 --> 00:20:33,380
as dit 'n hoër vlak bespreking.

452
00:20:33,380 --> 00:20:34,880
So hier is die algoritme weer.

453
00:20:34,880 --> 00:20:36,770
Kom ons vra onsself,
wat die loop van die tyd

454
00:20:36,770 --> 00:20:39,287
is van hierdie algoritmes verskillende stappe?

455
00:20:39,287 --> 00:20:41,620
Kom ons verdeel dit in die eerste
geval en die tweede geval.

456
00:20:41,620 --> 00:20:46,280
Die IF en die anders in die geval as,
INDIEN N is minder as 2, net terug te keer.

457
00:20:46,280 --> 00:20:47,580
Voel soos konstante tyd.

458
00:20:47,580 --> 00:20:50,970
Dit is, soort, soos twee stappe,
INDIEN N is minder as 2, dan terug.

459
00:20:50,970 --> 00:20:54,580
Maar soos ons sê op Maandag,
konstante tyd, of 'n groot o van 1,

460
00:20:54,580 --> 00:20:57,130
kan twee stappe, drie
stappe, selfs 1000 stappe.

461
00:20:57,130 --> 00:20:59,870
Wat belangrik is, is dat dit
'n konstante aantal stappe.

462
00:20:59,870 --> 00:21:03,240
So die geel uitgelig pseudokode
hier loop in, ons sal dit noem,

463
00:21:03,240 --> 00:21:04,490
konstante tyd.

464
00:21:04,490 --> 00:21:06,780
Sodat meer formeel en
ons gaan aan- hierdie

465
00:21:06,780 --> 00:21:09,910
sal die mate waarin ons
formaliseer hierdie reg now-- T van n,

466
00:21:09,910 --> 00:21:15,030
die loop van die tyd van 'n probleem
wat neem N Iets as insette,

467
00:21:15,030 --> 00:21:19,150
gelyk groot o een,
INDIEN N is minder as 2.

468
00:21:19,150 --> 00:21:20,640
So dit is op voorwaarde dat.

469
00:21:20,640 --> 00:21:24,150
So duidelik, as n minder as
2, ons het 'n baie kort lys, dan

470
00:21:24,150 --> 00:21:29,151
die loop van die tyd, T van n, waar n
1 of 0, in hierdie baie spesifieke geval,

471
00:21:29,151 --> 00:21:30,650
dit is net gaan om te konstante tyd.

472
00:21:30,650 --> 00:21:32,691
Dit gaan om een ​​te neem
stap, twee stappe, wat ook al.

473
00:21:32,691 --> 00:21:33,950
Dit is 'n vaste aantal stappe.

474
00:21:33,950 --> 00:21:38,840
>> So het die sappige deel sekerlik in
die ander geval in die pseudokode.

475
00:21:38,840 --> 00:21:40,220
Die NÓG geval.

476
00:21:40,220 --> 00:21:44,870
Sorteer links helfte van elemente, sorteer reg
helfte van elemente, saamsmelt gesorteerde helftes.

477
00:21:44,870 --> 00:21:46,800
Hoe lank elk van dié stappe te neem?

478
00:21:46,800 --> 00:21:49,780
Wel, as die bestuur
tyd om n elemente te sorteer

479
00:21:49,780 --> 00:21:53,010
is, kom ons noem dit baie
generies, T van n,

480
00:21:53,010 --> 00:21:55,500
dan sorteer die linker
helfte van die elemente

481
00:21:55,500 --> 00:21:59,720
is, soort, soos om te sê,
T van N gedeel deur 2,

482
00:21:59,720 --> 00:22:03,000
en insgelyks sorteer die regter helfte
elemente is, soort, soos om te sê,

483
00:22:03,000 --> 00:22:06,974
T van N verdeel 2, en dan
die samesmelting van die gesorteer helftes.

484
00:22:06,974 --> 00:22:08,890
Wel, as ek het 'n paar
aantal elemente hier

485
00:22:08,890 --> 00:22:11,230
soos vier en 'n paar nommer
elemente hier, soos vier

486
00:22:11,230 --> 00:22:14,650
en ek het aan elk van hierdie vier saamsmelt
in, en elk van hierdie vier in een

487
00:22:14,650 --> 00:22:17,160
na die ander, sodat
Ek het uiteindelik agt elemente.

488
00:22:17,160 --> 00:22:20,230
Dit voel soos dit is 'n groot o van n stappe?

489
00:22:20,230 --> 00:22:23,500
As ek n vingers en elk van het
hulle moet saamgevoeg word in plek is,

490
00:22:23,500 --> 00:22:25,270
dit is soos 'n ander n stappe.

491
00:22:25,270 --> 00:22:27,360
>> So inderdaad formulaically,
kan ons dit uit te druk,

492
00:22:27,360 --> 00:22:29,960
hoewel 'n bietjie op die eerste scarily
oogopslag, maar dit is iets

493
00:22:29,960 --> 00:22:31,600
wat vang presies dit logika.

494
00:22:31,600 --> 00:22:35,710
Die loop van die tyd, T van n, as n
groter as of gelyk aan 2.

495
00:22:35,710 --> 00:22:42,500
In hierdie geval, die NÓG geval, is T van N
gedeel deur 2, plus T van N gedeel deur 2,

496
00:22:42,500 --> 00:22:45,320
plus groot o van N, sommige
lineêre aantal stappe,

497
00:22:45,320 --> 00:22:51,630
Miskien presies n, miskien 2 keer
N, maar dit is 'n harde orde van n.

498
00:22:51,630 --> 00:22:54,060
Sodat, ook, is hoe ons kan
druk hierdie formulaically.

499
00:22:54,060 --> 00:22:56,809
Nou wil jy dit nie weet nie, tensy
jy dit aangeteken in jou gedagtes,

500
00:22:56,809 --> 00:22:58,710
of kyk dit in die
rug van 'n handboek, wat

501
00:22:58,710 --> 00:23:00,501
dalk 'n bietjie te hê
oneerlik vel aan die einde,

502
00:23:00,501 --> 00:23:03,940
maar dit is inderdaad gaan
gee ons 'n groot o van n log n,

503
00:23:03,940 --> 00:23:06,620
omdat die herhaling wat
jy hier sien op die skerm,

504
00:23:06,620 --> 00:23:09,550
as jy eintlik het dit uit met
'n oneindige aantal voorbeelde,

505
00:23:09,550 --> 00:23:13,000
of jy dit gedoen het formulaically, sou jy
sien dat dit, want hierdie formule

506
00:23:13,000 --> 00:23:17,100
self is rekursiewe, met t van
N oor iets aan die regterkant,

507
00:23:17,100 --> 00:23:21,680
en t van N oor aan die linkerkant, kan dit
eintlik uitgedruk, uiteindelik,

508
00:23:21,680 --> 00:23:24,339
so groot gaan van N log n.

509
00:23:24,339 --> 00:23:26,130
Indien nie oortuig nie, dis
boete vir nou, net

510
00:23:26,130 --> 00:23:28,960
op die geloof, sodat dit is, inderdaad,
wat dit herhaling lei tot,

511
00:23:28,960 --> 00:23:31,780
maar dit is net 'n bietjie meer van 'n
wiskundige benadering tot soek

512
00:23:31,780 --> 00:23:36,520
by die loop tyd van merge soort
gebaseer op sy pseudokode alleen.

513
00:23:36,520 --> 00:23:39,030
>> Nou laat ons neem 'n bietjie van 'n
blaaskans van alles,

514
00:23:39,030 --> 00:23:41,710
en neem 'n blik op 'n
sekere voormalige senator wat

515
00:23:41,710 --> 00:23:44,260
kan kyk 'n bietjie bekend,
wat gaan sit het met Google se Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, 'n geruime tyd gelede, vir 'n onderhoud
op die verhoog, in die voorkant van 'n hele klomp

517
00:23:48,410 --> 00:23:53,710
mense, praat uiteindelik oor
'n onderwerp, dis nogal nou reeds bekende.

518
00:23:53,710 --> 00:23:54,575
Kom ons neem 'n blik.

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

520
00:24:01,020 --> 00:24:03,890
>> ERIC SCHMIDT: Nou Senator,
jy hier is op Google,

521
00:24:03,890 --> 00:24:09,490
en ek wil om te dink van die
presidentskap as 'n werksonderhoud.

522
00:24:09,490 --> 00:24:11,712
Nou is dit moeilik om 'n werk te kry as president.

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

524
00:24:12,670 --> 00:24:13,940
ERIC SCHMIDT: En jy is
nou gaan doen [onhoorbaar].

525
00:24:13,940 --> 00:24:15,523
Dit is ook moeilik om 'n werk te kry by Google.

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

527
00:24:17,700 --> 00:24:21,330
>> ERIC SCHMIDT: Ons het vrae,
en ons vra ons kandidate vrae,

528
00:24:21,330 --> 00:24:24,310
en hierdie een is van 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: Wat?

531
00:24:27,005 --> 00:24:28,130
Julle dink ek grap?

532
00:24:28,130 --> 00:24:30,590
Dit is reg hier.

533
00:24:30,590 --> 00:24:33,490
Wat is die mees doeltreffende manier om
sorteer 'n miljoen 32 bit heelgetalle?

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

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

536
00:24:38,979 --> 00:24:41,020
ERIC SCHMIDT: Soms
miskien is ek jammer, maybe--

537
00:24:41,020 --> 00:24:42,750
President Obama: Nee, nee,
nee, nee, nee, ek think--

538
00:24:42,750 --> 00:24:43,240
ERIC SCHMIDT: Dit is nie it--

539
00:24:43,240 --> 00:24:45,430
President Obama: Ek
dink, ek dink die borrel

540
00:24:45,430 --> 00:24:46,875
soort sou die verkeerde manier om te gaan.

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

542
00:24:49,619 --> 00:24:50,535
ERIC SCHMIDT: Kom op.

543
00:24:50,535 --> 00:24:52,200
Wat hom dit vertel het?

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

545
00:24:54,020 --> 00:24:55,590
Ek het nie die rekenaarwetenskap on--

546
00:24:55,590 --> 00:24:58,986
>> President Obama: Ons het
het ons spioene in daar.

547
00:24:58,986 --> 00:24:59,860
PROFESSOR: Alle reg.

548
00:24:59,860 --> 00:25:03,370
Kom ons laat ons nou die agter
teoretiese wêreld van algoritmes

549
00:25:03,370 --> 00:25:06,520
in die asimptotiese analise
daarvan, en terug te keer na 'n paar onderwerpe

550
00:25:06,520 --> 00:25:09,940
van week nul en een, en begin
om 'n paar opleiding wiele te verwyder,

551
00:25:09,940 --> 00:25:10,450
as jy wil.

552
00:25:10,450 --> 00:25:13,241
Sodat jy werklik verstaan
uiteindelik van die grond af, wat is

553
00:25:13,241 --> 00:25:16,805
gaan op onder die kap, wanneer jy
skryf, saamstel, en uit te voer programme.

554
00:25:16,805 --> 00:25:19,680
Onthou in die besonder, dat dit
die eerste C-program het ons gekyk na,

555
00:25:19,680 --> 00:25:22,840
'n kanoniese, eenvoudige program
van spesies, relatief gesproke,

556
00:25:22,840 --> 00:25:24,620
waarin, dit druk, Hello World.

557
00:25:24,620 --> 00:25:27,610
En onthou dat ek gesê het, die proses
dat bronkode gaan deur

558
00:25:27,610 --> 00:25:28,430
is presies hierdie.

559
00:25:28,430 --> 00:25:31,180
Jy neem jou bronkode, slaag
dit deur 'n samesteller, soos klang,

560
00:25:31,180 --> 00:25:34,650
en kom uit voorwerp kode, wat
kan lyk soos hierdie, nulle en ene

561
00:25:34,650 --> 00:25:37,880
dat die verwerker, sentrale
verwerking van eenheid of brein,

562
00:25:37,880 --> 00:25:39,760
uiteindelik verstaan.

563
00:25:39,760 --> 00:25:42,460
>> Dit blyk dat dit is 'n
bietjie van 'n oorvereenvoudiging,

564
00:25:42,460 --> 00:25:44,480
dat ons nou in 'n
posisie om uitmekaar te terg

565
00:25:44,480 --> 00:25:46,720
om te verstaan ​​wat regtig
gaan op onder die kap

566
00:25:46,720 --> 00:25:48,600
elke keer as jy hardloop
Klang, of meer algemeen,

567
00:25:48,600 --> 00:25:53,040
elke keer as jy 'n program te maak,
gebruik van Maak en CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
In die besonder, dinge soos
dit is die eerste keer gegenereer word,

569
00:25:56,760 --> 00:25:58,684
wanneer jy eers jou program saam te stel.

570
00:25:58,684 --> 00:26:00,600
Met ander woorde, wanneer jy
neem jou bronkode

571
00:26:00,600 --> 00:26:04,390
en stel dit wat is die eerste
word outputted deur klang

572
00:26:04,390 --> 00:26:06,370
is iets wat bekend staan ​​as die gemeente-kode.

573
00:26:06,370 --> 00:26:08,990
En in die feit, dit lyk presies soos hierdie.

574
00:26:08,990 --> 00:26:11,170
>> Ek hardloop 'n opdrag aan die
command line vroeër.

575
00:26:11,170 --> 00:26:16,260
Klang Dash kapitaal s hello.c,
en dit het 'n lêer

576
00:26:16,260 --> 00:26:19,490
vir my geroep hello.s,
binnekant van wat presies was

577
00:26:19,490 --> 00:26:22,290
hierdie inhoud, en 'n bietjie meer
bo en 'n bietjie meer hieronder

578
00:26:22,290 --> 00:26:25,080
maar ek het die sappigste sit
inligting wat hier op die skerm.

579
00:26:25,080 --> 00:26:29,190
En as jy mooi kyk, sal jy sien
ten minste 'n paar bekende sleutelwoorde.

580
00:26:29,190 --> 00:26:31,330
Ons het groot op top.

581
00:26:31,330 --> 00:26:35,140
Ons het in die middel printf.

582
00:26:35,140 --> 00:26:38,670
En ons het ook hello world
backslash N in aanhalingstekens down hieronder.

583
00:26:38,670 --> 00:26:42,450
>> En alles anders in hier
is instruksies baie lae vlak

584
00:26:42,450 --> 00:26:45,500
dat die verwerker verstaan.

585
00:26:45,500 --> 00:26:50,090
CPU instruksies wat geheue beweeg
rond, dat die vrag snare van die geheue,

586
00:26:50,090 --> 00:26:52,750
en uiteindelik, druk
dinge op die skerm.

587
00:26:52,750 --> 00:26:56,780
Nou wat gebeur nadat hulle
hierdie vergadering kode gegenereer?

588
00:26:56,780 --> 00:26:59,964
Uiteindelik, jy doen, inderdaad,
steeds genereer voorwerp kode.

589
00:26:59,964 --> 00:27:02,630
Maar die stappe wat regtig
is aan die gang onder die enjinkap

590
00:27:02,630 --> 00:27:04,180
kyk 'n bietjie meer soos hierdie.

591
00:27:04,180 --> 00:27:08,390
Bronkode word vergadering kode,
wat dan voorwerp kode,

592
00:27:08,390 --> 00:27:11,930
en die operatiewe woord hier is dat
wanneer jy jou bronkode te stel,

593
00:27:11,930 --> 00:27:16,300
kom uit die gemeente-kode, en dan
wanneer jy jou gemeente-kode vergader,

594
00:27:16,300 --> 00:27:17,800
kom uit voorwerp kode.

595
00:27:17,800 --> 00:27:20,360
>> Nou klang is super gesofistikeerde,
soos 'n baie opstellers,

596
00:27:20,360 --> 00:27:23,151
en dit nie al hierdie stappe
bymekaar, en dit nie noodwendig

597
00:27:23,151 --> 00:27:25,360
uitset enige intermediêre
lêers wat jy kan selfs sien.

598
00:27:25,360 --> 00:27:28,400
Dit stel net dinge,
wat is die algemene term wat

599
00:27:28,400 --> 00:27:30,000
beskryf hierdie hele proses.

600
00:27:30,000 --> 00:27:32,000
Maar as jy regtig wil
besonder te wees, daar is

601
00:27:32,000 --> 00:27:34,330
'n baie meer gaan daar as well.

602
00:27:34,330 --> 00:27:38,860
>> Maar laat ons dit ook oorweeg nou dat selfs
dat super eenvoudige program, hello.c,

603
00:27:38,860 --> 00:27:40,540
genoem 'n funksie.

604
00:27:40,540 --> 00:27:41,870
Dit is dan printf.

605
00:27:41,870 --> 00:27:46,900
Maar ek het nie skryf printf, inderdaad,
wat kom met c, om so te praat.

606
00:27:46,900 --> 00:27:51,139
Dit is 'n funksie herroep wat
in die standaard io.h, verklaar wat

607
00:27:51,139 --> 00:27:53,180
is 'n kop-lêer, wat
is 'n onderwerp sal ons eintlik

608
00:27:53,180 --> 00:27:55,780
duik in meer diepte voor lank.

609
00:27:55,780 --> 00:27:58,000
Maar 'n kop lêer
tipies vergesel

610
00:27:58,000 --> 00:28:02,920
deur 'n kode lêer, bronkode lêer, sodat
baie soos daar bestaan ​​standaard io.h.

611
00:28:02,920 --> 00:28:05,930
>> Rukkie gelede het iemand,
of iemand ook geskryf

612
00:28:05,930 --> 00:28:11,040
'n lêer genaamd standaard io.c, in
wat die werklike definisies,

613
00:28:11,040 --> 00:28:15,220
of die implementering van printf,
en trosse van ander funksies,

614
00:28:15,220 --> 00:28:16,870
is eintlik geskryf.

615
00:28:16,870 --> 00:28:22,140
So gegee dat, as ons kyk na wat
hier aan die linkerkant, hello.c, dat wanneer

616
00:28:22,140 --> 00:28:26,250
saamgestel, gee ons hello.s, selfs al
Klang nie besparing pla in 'n plek

617
00:28:26,250 --> 00:28:31,360
ons kan dit sien, en dat die gemeente-kode
kry vergader in hello.o, wat

618
00:28:31,360 --> 00:28:34,630
is inderdaad die standaard naam
gegee wanneer jy bron stel

619
00:28:34,630 --> 00:28:39,350
kode in voorwerp-kode nie, maar is nie
heeltemal gereed om dit nog te voer,

620
00:28:39,350 --> 00:28:41,460
omdat 'n ander stap
het om te gebeur, en het

621
00:28:41,460 --> 00:28:44,440
gebeur het vir die afgelope paar
weke, miskien unbeknownst aan jou.

622
00:28:44,440 --> 00:28:47,290
>> Spesifiek iewers
in CS50 IDE, en dit,

623
00:28:47,290 --> 00:28:49,870
Ook sal 'n bietjie van 'n wees
oorvereenvoudiging vir 'n oomblik,

624
00:28:49,870 --> 00:28:54,670
daar is, of was op 'n tyd,
'n lêer genaamd standaard io.c,

625
00:28:54,670 --> 00:28:58,440
dat iemand saamgestel in
standaard io.s of die ekwivalent,

626
00:28:58,440 --> 00:29:02,010
dat iemand dan vergader
in standaard io.o,

627
00:29:02,010 --> 00:29:04,600
of dit blyk in 'n
effens verskillende lêer

628
00:29:04,600 --> 00:29:07,220
formaat wat 'n ander kan hê
lêer uitbreiding geheel en al,

629
00:29:07,220 --> 00:29:11,720
maar in die teorie en konseptueel, presies
daardie stappe moes gebeur in 'n vorm.

630
00:29:11,720 --> 00:29:14,060
Wat is om te sê, wat nou
wanneer ek skryf 'n program,

631
00:29:14,060 --> 00:29:17,870
hello.c, wat net sê, hello wêreld,
en ek die gebruik van kode iemand anders se

632
00:29:17,870 --> 00:29:22,480
soos printf, wat eens op 'n was
tyd, in 'n lêer met die naam standaard io.c,

633
00:29:22,480 --> 00:29:26,390
dan een of ander manier het ek my neem
voorwerp kode, my nulle en ene,

634
00:29:26,390 --> 00:29:29,260
en voorwerp daardie persoon se
kode, of nulle en ene,

635
00:29:29,260 --> 00:29:34,970
en een of ander manier hulle mekaar skakel in
een finale lêer, genaamd hello, wat

636
00:29:34,970 --> 00:29:38,070
het al die nulle en
kinders van my hoof funksie,

637
00:29:38,070 --> 00:29:40,830
en al die nulle
en een vir printf.

638
00:29:40,830 --> 00:29:44,900
>> En inderdaad, wat verlede proses is
genoem, koppel jou voorwerp kode.

639
00:29:44,900 --> 00:29:47,490
Die opbrengs van wat
is 'n uitvoerbare lêer.

640
00:29:47,490 --> 00:29:49,780
So in regverdigheid, by die
einde van die dag, niks

641
00:29:49,780 --> 00:29:52,660
het verander sedert week een, wanneer ons
eers begin die opstel van programme.

642
00:29:52,660 --> 00:29:55,200
Inderdaad, al hierdie is
gebeur onder die enjinkap,

643
00:29:55,200 --> 00:29:57,241
maar nou is ons in 'n posisie
waar ons kan eintlik

644
00:29:57,241 --> 00:29:58,794
terg uitmekaar hierdie verskillende stappe.

645
00:29:58,794 --> 00:30:00,710
En inderdaad, aan die einde
van die dag, ons is nog steeds

646
00:30:00,710 --> 00:30:04,480
links met nulle en ene, wat
is eintlik 'n groot segue nou

647
00:30:04,480 --> 00:30:08,620
na 'n ander moontlikheid van C, wat
ons het nie moes waarskynlik hefboom

648
00:30:08,620 --> 00:30:11,250
tot op datum, bekend as bis operateurs.

649
00:30:11,250 --> 00:30:15,220
Met ander woorde, tot dusver, enige tyd het ons
hanteer data in C of veranderlikes in C,

650
00:30:15,220 --> 00:30:17,660
ons het dinge gehad soos
karakters en dryf en ins

651
00:30:17,660 --> 00:30:21,990
en verlang en dubbelspel en dies meer, maar
Al wat is minstens agt stukkies.

652
00:30:21,990 --> 00:30:25,550
Ons het nog nooit in staat was om
manipuleer individuele stukkies,

653
00:30:25,550 --> 00:30:28,970
selfs al 'n individu bietjie, ons
weet, kan 'n 0 en 'n 1 verteenwoordig.

654
00:30:28,970 --> 00:30:32,640
Nou is dit blyk dat in C, jy
kan kry toegang tot individuele stukkies,

655
00:30:32,640 --> 00:30:35,530
As jy weet wat die sintaksis,
waarmee te kry op hulle.

656
00:30:35,530 --> 00:30:38,010
>> So laat ons 'n blik
by bis operateurs.

657
00:30:38,010 --> 00:30:41,700
Hier so uitgebeeld is 'n paar simbole wat
ons het, soort van, soort van, gesien nie.

658
00:30:41,700 --> 00:30:45,580
Ek sien 'n ampersand, 'n vertikale
bar, en 'n paar ander ook,

659
00:30:45,580 --> 00:30:49,430
en onthou dat ampersand ampersand
is iets wat ons voorheen gesien het.

660
00:30:49,430 --> 00:30:54,060
Die logiese EN operateur, waar jy
twee van hulle saam, of die logiese OF

661
00:30:54,060 --> 00:30:56,300
operateur, waar jy
het twee vertikale bars.

662
00:30:56,300 --> 00:31:00,550
Bis-operateurs, wat ons sal
sien werk op stukkies individueel,

663
00:31:00,550 --> 00:31:03,810
net gebruik om 'n enkele ampersand, 'n
enkele vertikale bar, die kappie simbool

664
00:31:03,810 --> 00:31:06,620
kom die volgende, die klein
tilde, en dan links

665
00:31:06,620 --> 00:31:08,990
bracket gelaat bracket, of
reg bracket reg bracket.

666
00:31:08,990 --> 00:31:10,770
Elkeen van hierdie verskillende betekenisse.

667
00:31:10,770 --> 00:31:11,950
>> In werklikheid, laat ons neem 'n blik.

668
00:31:11,950 --> 00:31:16,560
Kom ons gaan ou skool vandag, en gebruik
'n touch screen van weleer,

669
00:31:16,560 --> 00:31:18,002
bekend as 'n wit bord.

670
00:31:18,002 --> 00:31:19,710
En dit wit bord
gaan ons toelaat

671
00:31:19,710 --> 00:31:27,360
sommige redelik eenvoudige simbole uit te druk,
of liewer 'n paar redelik eenvoudige formules,

672
00:31:27,360 --> 00:31:29,560
dat ons kan dan uiteindelik
hefboom, ten einde

673
00:31:29,560 --> 00:31:33,230
om toegang tot die individuele
stukkies binne 'n C program.

674
00:31:33,230 --> 00:31:34,480
Met ander woorde, laat ons dit doen.

675
00:31:34,480 --> 00:31:37,080
Kom ons praat vir 'n eerste
oomblik oor ampersand,

676
00:31:37,080 --> 00:31:39,560
wat is die bis EN operateur.

677
00:31:39,560 --> 00:31:42,130
Met ander woorde, dit is
'n operateur wat toelaat

678
00:31:42,130 --> 00:31:45,930
my 'n linker veranderlike het
Tipies, en 'n regter veranderlike,

679
00:31:45,930 --> 00:31:50,640
of 'n individu waarde dat as ons EN
hulle saam, gee my 'n finale uitslag.

680
00:31:50,640 --> 00:31:51,560
So, wat ek bedoel?

681
00:31:51,560 --> 00:31:54,840
As in 'n program, jy het 'n veranderlike
wat winkels een van hierdie waardes,

682
00:31:54,840 --> 00:31:58,000
of laat ons hou dit eenvoudig, en net
skryf nulle en ene individueel,

683
00:31:58,000 --> 00:32:00,940
Hier is hoe die ampersand operateur werk.

684
00:32:00,940 --> 00:32:06,400
0 0 ampersand gaan gelyk 0.

685
00:32:06,400 --> 00:32:07,210
Nou hoekom is dit?

686
00:32:07,210 --> 00:32:09,291
>> Dit is baie soortgelyk aan
Boole uitdrukkings,

687
00:32:09,291 --> 00:32:10,540
dat ons tot dusver bespreek het.

688
00:32:10,540 --> 00:32:15,800
As jy dink na alles, die 0 is
valse, 0 is vals, vals en onwaar

689
00:32:15,800 --> 00:32:18,720
is, soos ons bespreek het
logies, ook onwaar.

690
00:32:18,720 --> 00:32:20,270
So kry ons 0 hier.

691
00:32:20,270 --> 00:32:24,390
As jy 0 ampersand neem
1, goed dat ook

692
00:32:24,390 --> 00:32:29,890
gaan wees 0, want vir hierdie
linkerkantse uitdrukking waar of 1 wees,

693
00:32:29,890 --> 00:32:32,360
dit nodig sou wees om die ware en waar te wees.

694
00:32:32,360 --> 00:32:36,320
Maar hier het ons valse
en waar is, of 0 en 1.

695
00:32:36,320 --> 00:32:42,000
Nou weer, as ons het 1 ampersand
0, wat ook gaan wees 0,

696
00:32:42,000 --> 00:32:47,240
en as ons 1 ampersand 1,
uiteindelik het ons 'n 1 bietjie.

697
00:32:47,240 --> 00:32:50,340
So met ander woorde, is ons nie te doen
iets interessant met hierdie operateur

698
00:32:50,340 --> 00:32:51,850
net nog, hierdie ampersand operateur.

699
00:32:51,850 --> 00:32:53,780
Dit is die bis EN operateur.

700
00:32:53,780 --> 00:32:57,290
Maar dit is die bestanddele
via wat kan ons doen

701
00:32:57,290 --> 00:32:59,240
interessante dinge, soos ons binnekort sal sien.

702
00:32:59,240 --> 00:33:02,790
>> Nou laat ons kyk na net die enkele
vertikale bar hier aan die regterkant.

703
00:33:02,790 --> 00:33:06,710
As ek 'n bietjie en ek 0
OF dit met die bis

704
00:33:06,710 --> 00:33:11,030
OF operateur, 'n ander 0 bietjie,
wat gaan om te gee my 0.

705
00:33:11,030 --> 00:33:17,540
As ek 'n bietjie en 0 OF dit met
'n 1 bietjie, dan gaan ek om 1 te kry.

706
00:33:17,540 --> 00:33:19,830
En in die feit, net vir
duidelikheid, laat my terug te gaan,

707
00:33:19,830 --> 00:33:23,380
sodat my vertikale bars
nie verwar 1 se.

708
00:33:23,380 --> 00:33:26,560
Laat my al herskryf
my 1 is 'n bietjie meer

709
00:33:26,560 --> 00:33:32,700
duidelik, so dat ons volgende sien, as ek
het 'n 1 OF 0, wat gaan 'n 1 te wees,

710
00:33:32,700 --> 00:33:39,060
en as ek 'n 1 OF 1 dat
Ook gaan 'n 1 te wees.

711
00:33:39,060 --> 00:33:42,900
Sodat jy kan logies sien dat die OR
operateur optree baie anders.

712
00:33:42,900 --> 00:33:48,070
Dit gee my 0 OF 0 gee my 0, maar
elke ander kombinasie gee my 1.

713
00:33:48,070 --> 00:33:52,480
So lank as wat ek een in die 1
formule, is die resultaat gaan wees 1.

714
00:33:52,480 --> 00:33:55,580
>> In teenstelling met die EN
operateur, die ampersand,

715
00:33:55,580 --> 00:34:00,940
net as ek het twee 1 in die
vergelyking, ek kry eintlik 'n 1 uit.

716
00:34:00,940 --> 00:34:02,850
Nou is daar ''n paar ander
operateurs sowel.

717
00:34:02,850 --> 00:34:04,810
Een van hulle is 'n bietjie meer betrokke.

718
00:34:04,810 --> 00:34:07,980
So laat my gaan voort en vee
hierdie om gratis 'n paar ruimte.

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

720
00:34:13,020 --> 00:34:16,460
En laat ons 'n blik op die
kappie simbool, vir net 'n oomblik.

721
00:34:16,460 --> 00:34:18,210
Dit is gewoonlik 'n
karakter wat jy kan tik

722
00:34:18,210 --> 00:34:21,420
op jou sleutelbord hou die Shift en
dan een van die getalle bo jou Amerikaanse

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

724
00:34:22,250 --> 00:34:26,190
>> So, dit is die eksklusiewe
OF operateur, eksklusiewe OF.

725
00:34:26,190 --> 00:34:27,790
So sien ons net die OR operateur.

726
00:34:27,790 --> 00:34:29,348
Dit is die uitsluitlike of operateur.

727
00:34:29,348 --> 00:34:30,639
Wat is eintlik die verskil?

728
00:34:30,639 --> 00:34:34,570
Wel, laat ons net kyk na die formule,
en gebruik dit as bestanddele uiteindelik.

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

730
00:34:37,690 --> 00:34:39,650
Ek gaan om te sê is altyd 0.

731
00:34:39,650 --> 00:34:41,400
Dit is die definisie van XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 gaan wees 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 gaan wees 1,
en 1 XOR 1 gaan wees?

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

735
00:34:59,890 --> 00:35:00,520
Of reg?

736
00:35:00,520 --> 00:35:01,860
Ek weet nie.

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

738
00:35:02,810 --> 00:35:04,700
Nou wat gaan hier aan?

739
00:35:04,700 --> 00:35:06,630
Wel dink oor die
naam van hierdie operateur.

740
00:35:06,630 --> 00:35:09,980
Eksklusiewe OF, so as die
naam, soort van, dui,

741
00:35:09,980 --> 00:35:13,940
die antwoord is net gaan wees
'n 1 as die insette is eksklusiewe,

742
00:35:13,940 --> 00:35:15,560
uitsluitlik anders.

743
00:35:15,560 --> 00:35:18,170
So hier is die insette is die
dieselfde, so die produksie is 0.

744
00:35:18,170 --> 00:35:20,700
Hier is die insette is die
dieselfde, so die produksie is 0.

745
00:35:20,700 --> 00:35:25,640
Hier is die uitgange is anders, hulle
is eksklusief, en so die produksie is 1.

746
00:35:25,640 --> 00:35:28,190
So dit is baie soortgelyk aan
En, dit is baie soortgelyk,

747
00:35:28,190 --> 00:35:32,760
of eerder dit is baie soortgelyk aan
OF, maar slegs in 'n eksklusiewe manier.

748
00:35:32,760 --> 00:35:36,210
Hierdie een is nie meer 'n 1,
want ons het twee 1 se

749
00:35:36,210 --> 00:35:38,621
en nie uitsluitlik nie, maar net een van hulle.

750
00:35:38,621 --> 00:35:39,120
Alles reg.

751
00:35:39,120 --> 00:35:40,080
Wat van die ander?

752
00:35:40,080 --> 00:35:44,220
Wel, die tilde, intussen, is
eintlik mooi en eenvoudige, gelukkig.

753
00:35:44,220 --> 00:35:46,410
En dit is 'n unêre
operateur, wat beteken

754
00:35:46,410 --> 00:35:50,400
dit toegepas word om net een insette,
een operand, om so te praat.

755
00:35:50,400 --> 00:35:51,800
Nie om 'n links en regs.

756
00:35:51,800 --> 00:35:56,050
Met ander woorde, as jy tilde neem
0, sal die antwoord die teenoorgestelde.

757
00:35:56,050 --> 00:35:59,710
En as jy tilde van 1, die
antwoord daar die teenoorgestelde wees.

758
00:35:59,710 --> 00:36:02,570
So die tilde operateur is
'n manier om die ontkenning van 'n bietjie,

759
00:36:02,570 --> 00:36:06,000
of daarby 'n bietjie uit
0-1 of 1-0.

760
00:36:06,000 --> 00:36:09,820
>> En dat ons uiteindelik verlaat
met net twee finale operateurs,

761
00:36:09,820 --> 00:36:13,840
die sogenaamde links verskuiwing en die
sogenaamde reg verskuiwing operateur.

762
00:36:13,840 --> 00:36:16,620
Kom ons neem 'n blik op hoe die werk.

763
00:36:16,620 --> 00:36:20,780
Links verskuiwing operateur, geskryf
met twee hoek tussen hakies soos dit,

764
00:36:20,780 --> 00:36:22,110
bedryf as volg.

765
00:36:22,110 --> 00:36:27,390
As my insette, of my operand, aan die linkerkant
verskuiwing operateur is eenvoudig 'n 1.

766
00:36:27,390 --> 00:36:33,750
En ek vertel dan die rekenaar
links verskuiwing wat 1, sê sewe plekke,

767
00:36:33,750 --> 00:36:37,150
die resultaat is asof ek
neem dat 1, en beweeg dit

768
00:36:37,150 --> 00:36:40,160
sewe plekke oor die
links, en by verstek,

769
00:36:40,160 --> 00:36:42,270
ons gaan om te aanvaar dat
die ruimte om die regte

770
00:36:42,270 --> 00:36:44,080
gaan word opgestopte met nulle.

771
00:36:44,080 --> 00:36:50,316
Met ander woorde, 1 links verskuiwing 7 gaan
gee my dat 1, gevolg deur 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
So op 'n manier, dit laat jou
neem 'n klein aantal soos 1,

774
00:36:57,380 --> 00:37:00,740
en maak dit baie duidelik
baie, baie groter op hierdie manier,

775
00:37:00,740 --> 00:37:06,460
maar ons is eintlik gaan om te sien
meer slim benaderings want dit

776
00:37:06,460 --> 00:37:08,080
plaas, asook,

777
00:37:08,080 --> 00:37:08,720
>> Alles reg.

778
00:37:08,720 --> 00:37:10,060
Dit is dit vir week drie.

779
00:37:10,060 --> 00:37:11,400
Ons sal jy sien die volgende keer.

780
00:37:11,400 --> 00:37:12,770
Dit was CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [Speel van musiek]

783
00:37:22,243 --> 00:37:25,766
>> Spreker 1: Hy was by die snack
bar eet 'n warm fudge sundae.

784
00:37:25,766 --> 00:37:28,090
Hy het dit alles oor sy gesig.

785
00:37:28,090 --> 00:37:30,506
Hy dra dat sjokolade soos 'n baard

786
00:37:30,506 --> 00:37:31,756
Spreker 2: Wat doen jy?

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

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

789
00:37:33,500 --> 00:37:36,800
>> Spreker 2: Het jy net dubbel dip?

790
00:37:36,800 --> 00:37:38,585
Jy gedoop dubbel die chip.

791
00:37:38,585 --> 00:37:39,460
SPREKER 3: Verskoon my.

792
00:37:39,460 --> 00:37:44,440
Spreker 2: Jy steek die chip, jy
het 'n byt, en jy weer gedoop.

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

794
00:37:44,940 --> 00:37:48,440
Spreker 2: So dit is soos om
jou hele mond reg in die dip.

795
00:37:48,440 --> 00:37:52,400
Volgende keer as jy 'n chip te neem,
net steek dit een keer, en eindig dit.

796
00:37:52,400 --> 00:37:53,890
>> SPREKER 3: Jy weet wat, Dan?

797
00:37:53,890 --> 00:37:58,006
Jy steek die pad wat jy wil om te duik.

798
00:37:58,006 --> 00:38:01,900
Ek sal die pad wat ek wil om te duik steek.

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