1
00:00:00,000 --> 00:00:11,904
>> [MUSIK SPELA]

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

3
00:00:12,910 --> 00:00:16,730
Detta är CS50 och det är
I slutet av vecka tre.

4
00:00:16,730 --> 00:00:20,230
Så vi är här i dag, inte i Sanders
Teater, i stället i Weidner Library.

5
00:00:20,230 --> 00:00:23,170
Inuti vilken är en studio
känd som Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
eller ska vi säga Studio H, eller skall
Vi säga-- om du gillade det skämtet,

7
00:00:28,310 --> 00:00:30,540
det är faktiskt från
klasskamrat, Mark, på nätet,

8
00:00:30,540 --> 00:00:32,420
som föreslog lika mycket via Twitter.

9
00:00:32,420 --> 00:00:34,270
Nu vad är hett om
att vara här i en studio

10
00:00:34,270 --> 00:00:38,410
är att jag är omgiven av dessa gröna
väggar, en grön skärm eller chromakey,

11
00:00:38,410 --> 00:00:43,290
så att säga, vilket innebär att CS50: s
produktion team, okänt för mig

12
00:00:43,290 --> 00:00:47,380
just nu, skulle kunna vara att sätta
mig mest var som helst i världen,

13
00:00:47,380 --> 00:00:48,660
på gott och ont.

14
00:00:48,660 --> 00:00:51,800
>> Nu vad som väntar, problem set
två är i dina händer den här veckan,

15
00:00:51,800 --> 00:00:53,830
men med problem set
tre den kommande veckan,

16
00:00:53,830 --> 00:00:56,600
Du kommer att utmanas med
den så kallade omgång 15,

17
00:00:56,600 --> 00:00:58,960
en gammal partyfavör att
du kanske minns mottagande

18
00:00:58,960 --> 00:01:02,030
som ett barn som har en hel drös
av siffror som kan glida uppåt, nedåt,

19
00:01:02,030 --> 00:01:05,790
vänster och höger, och det finns ett gap
inom pusslet, i vilken du

20
00:01:05,790 --> 00:01:07,840
kan faktiskt dra dessa pusselbitar.

21
00:01:07,840 --> 00:01:11,150
I slutändan får du här
pussel i vissa semi slumpmässig ordning,

22
00:01:11,150 --> 00:01:12,940
och målet är att
sortera, uppifrån och ned,

23
00:01:12,940 --> 00:01:16,310
vänster till höger, från en
hela vägen upp genom 15.

24
00:01:16,310 --> 00:01:19,360
>> Tyvärr, genomförandet
du har till hands

25
00:01:19,360 --> 00:01:21,590
kommer att vara mjukvara
baserad, inte fysiskt.

26
00:01:21,590 --> 00:01:25,280
Du faktiskt kommer att behöva skriva
kod som en student eller användare kan

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

28
00:01:26,760 --> 00:01:29,030
Och i själva verket i hacker
utgåvan av spelet 15,

29
00:01:29,030 --> 00:01:32,155
du kommer att bli en utmaning att genomföra,
inte bara spela i denna gamla skolan

30
00:01:32,155 --> 00:01:35,010
spel, utan snarare att lösa
det, genomföra gud läge

31
00:01:35,010 --> 00:01:38,280
så att säga, som faktiskt
löser pusslet för människan,

32
00:01:38,280 --> 00:01:41,080
genom att ge dem tips,
efter ledtråd efter ledtråd.

33
00:01:41,080 --> 00:01:42,280
Så mer om det nästa vecka.

34
00:01:42,280 --> 00:01:43,720
Men det är vad som väntar.

35
00:01:43,720 --> 00:01:47,610
>> För nu påminna om att tidigare i veckan
Vi hade denna cliffhanger, om man så vill,

36
00:01:47,610 --> 00:01:52,560
varvid det bästa vi gjorde sortering
klokt var en övre gräns för stora o n

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

38
00:01:53,210 --> 00:01:56,520
Med andra ord, bubbelsortering,
val Sortera, insättningssortering,

39
00:01:56,520 --> 00:01:59,120
alla av dem, medan olika
i genomförandet,

40
00:01:59,120 --> 00:02:03,480
decentraliserade in en n kvadrat kör
tid i allra värsta fall.

41
00:02:03,480 --> 00:02:06,010
Och vi i allmänhet anta att
det värsta fallet för sortering

42
00:02:06,010 --> 00:02:08,814
är en som ingångarna
är helt bakåt.

43
00:02:08,814 --> 00:02:11,980
Och faktiskt, det tog en hel del steg
att genomföra vart och ett av dessa algoritmer.

44
00:02:11,980 --> 00:02:15,110
>> Nu i slutet av klass
minns, jämförde vi bubbelsortering

45
00:02:15,110 --> 00:02:19,390
mot val Sortera mot en annan
som vi kallade merge sort på den tiden,

46
00:02:19,390 --> 00:02:22,120
och jag föreslår att det tar
Fördelen med en lektion från vecka

47
00:02:22,120 --> 00:02:24,060
noll, söndra och härska.

48
00:02:24,060 --> 00:02:28,810
Och på något sätt att uppnå någon form av
logaritmisk gångtid slutändan

49
00:02:28,810 --> 00:02:31,024
i stället för något
det är rent kvadratisk.

50
00:02:31,024 --> 00:02:33,440
Och det är inte helt logaritmisk,
Det är lite mer än så.

51
00:02:33,440 --> 00:02:36,520
Men om du minns från klass,
det var mycket, mycket snabbare.

52
00:02:36,520 --> 00:02:38,210
Låt oss ta en titt på där vi slutade.

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

54
00:02:41,880 --> 00:02:45,370
>> Bubbelsortering kontra urval
sortera kontra merge sort.

55
00:02:45,370 --> 00:02:47,700
Nu är alla kör i
teori, samtidigt.

56
00:02:47,700 --> 00:02:50,510
Processorn körs med samma hastighet.

57
00:02:50,510 --> 00:02:54,990
Men du kan känna hur tråkigt detta
är mycket snabbt kommer att bli,

58
00:02:54,990 --> 00:02:58,790
och hur snabbt, när vi injicerar
en bit av vecka noll algoritmer,

59
00:02:58,790 --> 00:03:00,080
kan vi snabba upp saker och ting.

60
00:03:00,080 --> 00:03:01,630
>> Så märke sort ser fantastisk.

61
00:03:01,630 --> 00:03:05,220
Hur kan vi utnyttja det, för
att sortera siffror snabbare.

62
00:03:05,220 --> 00:03:07,140
Nå, låt oss tänka tillbaka
en ingrediens som vi

63
00:03:07,140 --> 00:03:10,380
hade tillbaka i vecka noll, som
söka efter någon i en telefonbok,

64
00:03:10,380 --> 00:03:12,380
och påminna om att
pseudokod som vi föreslog,

65
00:03:12,380 --> 00:03:14,560
via vilken vi kan hitta
någon som Mike Smith,

66
00:03:14,560 --> 00:03:16,310
såg lite ungefär så här.

67
00:03:16,310 --> 00:03:20,820
>> Nu tar en titt i synnerhet
vid linje 7 och 8, och 10 och 11,

68
00:03:20,820 --> 00:03:25,240
som inducerar den slingan, där vi höll
gå tillbaka till linje 3 igen, och igen,

69
00:03:25,240 --> 00:03:26,520
och igen.

70
00:03:26,520 --> 00:03:31,790
Men det visar sig att vi kan visa
denna algoritm, här i pseudokod,

71
00:03:31,790 --> 00:03:33,620
lite mer holistiskt.

72
00:03:33,620 --> 00:03:35,960
I själva verket, vad jag letar
till här på skärmen,

73
00:03:35,960 --> 00:03:41,180
är en algoritm för att söka efter
Mike Smith bland några uppsättning sidor.

74
00:03:41,180 --> 00:03:45,520
Och faktiskt, vi kunde förenkla denna
algoritmen i dessa linjer 7 och 8,

75
00:03:45,520 --> 00:03:49,860
och 10 och 11 för att bara säga detta,
som jag har lagt fram här i gult.

76
00:03:49,860 --> 00:03:52,210
Med andra ord, om Mike
Smith är tidigare i boken,

77
00:03:52,210 --> 00:03:55,004
vi behöver inte ange steg
steg nu hur man ska gå hitta honom.

78
00:03:55,004 --> 00:03:56,920
Vi behöver inte ange
att gå tillbaka till linje 3,

79
00:03:56,920 --> 00:03:58,960
varför vi inte bara i stället,
säg, mer generellt,

80
00:03:58,960 --> 00:04:01,500
söka för Mike i
vänstra halvan av boken.

81
00:04:01,500 --> 00:04:03,960
>> Omvänt, om Mike är
faktiskt senare i boken,

82
00:04:03,960 --> 00:04:07,540
varför inte vi bara citera unquote sökning
för Mike i den högra halvan av boken.

83
00:04:07,540 --> 00:04:11,030
Med andra ord, varför inte vi bara
sorts punt till oss och sade:

84
00:04:11,030 --> 00:04:13,130
söka för Mike i det här
delmängd av boken,

85
00:04:13,130 --> 00:04:16,279
och lämna den till vår befintliga
algoritm för att berätta

86
00:04:16,279 --> 00:04:18,750
hur man söker efter Mike
att vänstra halvan av boken.

87
00:04:18,750 --> 00:04:20,750
Med andra ord, vår
algoritmen fungerar oavsett om det är

88
00:04:20,750 --> 00:04:24,670
en telefonbok med denna tjocklek, i detta
tjocklek, eller vilken som helst tjocklek som helst.

89
00:04:24,670 --> 00:04:27,826
Så vi kan rekursivt
definiera denna algoritm.

90
00:04:27,826 --> 00:04:29,950
Med andra ord, på den
skärm här är en algoritm

91
00:04:29,950 --> 00:04:33,130
för att söka efter Mike Smith
bland sidorna i en telefonbok.

92
00:04:33,130 --> 00:04:37,410
Så i linje 7 och 10, låt oss
bara säga just detta.

93
00:04:37,410 --> 00:04:40,250
Och jag använder denna term ett ögonblick
sedan, och faktiskt, rekursion

94
00:04:40,250 --> 00:04:42,450
är modeord för tillfället,
och det är denna process

95
00:04:42,450 --> 00:04:47,210
att göra något cyklisk av somehow
med hjälp av kod som du redan har,

96
00:04:47,210 --> 00:04:49,722
och kalla det igen,
och igen, och igen.

97
00:04:49,722 --> 00:04:51,930
Nu är det kommer att vara viktigt
att vi på något sätt botten

98
00:04:51,930 --> 00:04:53,821
ut, och inte göra det oändligt lång.

99
00:04:53,821 --> 00:04:56,070
Annars ska vi
har verkligen en oändlig loop.

100
00:04:56,070 --> 00:04:59,810
Men låt oss se om vi kan låna denna idé
av en rekursion, gör något igen

101
00:04:59,810 --> 00:05:03,600
och om och om igen, för att lösa
sorterings problemet via merge

102
00:05:03,600 --> 00:05:05,900
sortera, desto mer effektivt.

103
00:05:05,900 --> 00:05:06,970
>> Så jag ger dig merge sort.

104
00:05:06,970 --> 00:05:07,920
Låt oss ta en titt.

105
00:05:07,920 --> 00:05:10,850
Så här är pseudo, med
som vi skulle kunna genomföra sortering,

106
00:05:10,850 --> 00:05:12,640
att använda denna algoritm som kallas merge sort.

107
00:05:12,640 --> 00:05:13,880
Och det är helt enkelt detta.

108
00:05:13,880 --> 00:05:15,940
På ingången av n element,
Med andra ord, om du är

109
00:05:15,940 --> 00:05:18,830
givet n element och siffror och
bokstäver eller vad ingången är,

110
00:05:18,830 --> 00:05:22,430
om du har gett n element, om
n är mindre än 2, bara tillbaka.

111
00:05:22,430 --> 00:05:22,930
Höger?

112
00:05:22,930 --> 00:05:26,430
Eftersom om n är mindre än 2, som
innebär att min lista över element

113
00:05:26,430 --> 00:05:30,446
är antingen av storlek 0 eller 1, och
i båda dessa triviala fall

114
00:05:30,446 --> 00:05:31,570
listan redan sortering.

115
00:05:31,570 --> 00:05:32,810
Om det inte finns någon lista, är det sorteras.

116
00:05:32,810 --> 00:05:35,185
Och om det finns en lista över längd
1, är det självklart för sortering.

117
00:05:35,185 --> 00:05:38,280
Så algoritmen endast behöver
verkligen göra något intressant,

118
00:05:38,280 --> 00:05:40,870
om vi har två eller flera
element ges till oss.

119
00:05:40,870 --> 00:05:42,440
Så låt oss titta på den magiska sedan.

120
00:05:42,440 --> 00:05:47,500
Else sortera vänstra halvan av elementen,
sedan sortera högra halvan av element,

121
00:05:47,500 --> 00:05:49,640
sedan sammanfoga de sorterade halvor.

122
00:05:49,640 --> 00:05:52,440
Och vad är typ av sinnet böjning
här, är att jag inte riktigt

123
00:05:52,440 --> 00:05:56,190
tycks ha sagt
något ännu, eller hur?

124
00:05:56,190 --> 00:05:59,560
Allt jag har sagt är, få en lista över
n element, sortera den vänstra halvan,

125
00:05:59,560 --> 00:06:01,800
då rätt halv, sedan
sammanfoga de sorterade halvor,

126
00:06:01,800 --> 00:06:03,840
men var är den verkliga hemliga sås?

127
00:06:03,840 --> 00:06:05,260
Var är algoritmen?

128
00:06:05,260 --> 00:06:09,150
Jo det visar sig att dessa två linjer
först, typ vänstra halvan av element,

129
00:06:09,150 --> 00:06:13,970
och sortera högra halvan av element,
är rekursiva samtal, så att säga.

130
00:06:13,970 --> 00:06:16,120
>> När allt vid denna
tidpunkt, måste jag

131
00:06:16,120 --> 00:06:18,950
en algoritm med vilken till
sortera en massa element?

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

133
00:06:19,450 --> 00:06:20,620
Det är rätt här.

134
00:06:20,620 --> 00:06:25,180
Det är rätt här på skärmen, och
så jag kan använda samma uppsättning steg

135
00:06:25,180 --> 00:06:28,500
att sortera den vänstra halvan,
jag kan den högra halvan.

136
00:06:28,500 --> 00:06:30,420
Och faktiskt, igen, och igen.

137
00:06:30,420 --> 00:06:34,210
Så på något sätt eller annat, och vi ska snart
se detta, magi merge sort

138
00:06:34,210 --> 00:06:37,967
är inbäddad i det allra sista
linje, sammanslagning av sorterade halvor.

139
00:06:37,967 --> 00:06:39,300
Och det verkar ganska intuitiv.

140
00:06:39,300 --> 00:06:41,050
Du tar två halvor, och ni,
på något sätt, sammanfoga dem tillsammans,

141
00:06:41,050 --> 00:06:43,260
och vi får se här
konkret i ett ögonblick.

142
00:06:43,260 --> 00:06:45,080
>> Men detta är en komplett algoritm.

143
00:06:45,080 --> 00:06:46,640
Och låt oss se exakt varför.

144
00:06:46,640 --> 00:06:50,912
Väl antar att vi har gett dessa samma
åtta element här på skärmen, en

145
00:06:50,912 --> 00:06:53,120
till åtta, men de är
i till synes slumpmässig ordning.

146
00:06:53,120 --> 00:06:55,320
Och målet till hands är
att sortera dessa element.

147
00:06:55,320 --> 00:06:58,280
Nå hur kan jag gå om
göra det genom att använda, återigen,

148
00:06:58,280 --> 00:07:00,407
merge sort, enligt denna pseudo?

149
00:07:00,407 --> 00:07:02,740
Och återigen, ingrain detta
ditt sinne, för bara ett ögonblick.

150
00:07:02,740 --> 00:07:05,270
Det första fallet är ganska
trivialt, om det är mindre än 2,

151
00:07:05,270 --> 00:07:07,060
bara tillbaka, det finns inget arbete som skall utföras.

152
00:07:07,060 --> 00:07:09,290
Så egentligen finns det bara tre
åtgärder för att verkligen tänka på.

153
00:07:09,290 --> 00:07:11,081
Igen, och igen, jag är
kommer att vilja ha

154
00:07:11,081 --> 00:07:13,980
att sortera den vänstra halvan,
sortera den högra halv,

155
00:07:13,980 --> 00:07:15,890
och sedan när deras
två halvor är sorterade,

156
00:07:15,890 --> 00:07:18,710
Jag vill slå samman dem tillsammans
in en sorterad lista.

157
00:07:18,710 --> 00:07:19,940
Så ha det i åtanke.

158
00:07:19,940 --> 00:07:21,310
>> Så här är den ursprungliga listan.

159
00:07:21,310 --> 00:07:23,510
Låt oss behandla detta som en
array, som vi började

160
00:07:23,510 --> 00:07:25,800
i vecka två, som är en
sammanhängande block av minne.

161
00:07:25,800 --> 00:07:28,480
I detta fall, innehållande åtta
siffror, rygg mot rygg mot rygg.

162
00:07:28,480 --> 00:07:30,700
Och låt oss nu tillämpa merge sort.

163
00:07:30,700 --> 00:07:33,300
Så jag vill först sortera
den vänstra halvan av denna lista,

164
00:07:33,300 --> 00:07:37,370
och låt oss därför
fokusera på 4, 8, 6, och 2.

165
00:07:37,370 --> 00:07:41,000
>> Nu hur gör jag om
sortering en lista över storlek 4?

166
00:07:41,000 --> 00:07:45,990
Jag måste väl nu överväga
sortering vänster om den vänstra halv.

167
00:07:45,990 --> 00:07:47,720
Återigen, låt oss spola tillbaka för bara ett ögonblick.

168
00:07:47,720 --> 00:07:51,010
Om pseudokod är detta,
och jag får åtta element,

169
00:07:51,010 --> 00:07:53,230
8 är betydligt större
än eller lika med 2.

170
00:07:53,230 --> 00:07:54,980
Så med det första fallet inte gäller.

171
00:07:54,980 --> 00:07:58,120
Så för att sortera åtta element, jag först
sortera vänstra halvan av element,

172
00:07:58,120 --> 00:08:01,930
då jag sorterar den högra halvan, sedan slå ihop jag
de två sorterade halvor, var och en av storlek 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Men om du bara har berättat för mig, sortera
vänstra halvan, som nu av storlek 4,

175
00:08:07,480 --> 00:08:09,350
hur gör jag sorterar vänstra halvan?

176
00:08:09,350 --> 00:08:11,430
Tja, om jag har en
inmatning av fyra delar,

177
00:08:11,430 --> 00:08:14,590
Jag sorterar först vänster
två, sedan höger två,

178
00:08:14,590 --> 00:08:16,210
och då jag slå ihop dem tillsammans.

179
00:08:16,210 --> 00:08:18,700
Så återigen blir det en bit
av ett sinne böjning spel här,

180
00:08:18,700 --> 00:08:21,450
eftersom du, typ av, måste
kom ihåg var du är i berättelsen,

181
00:08:21,450 --> 00:08:23,620
men i slutet av dagen,
med tanke på valfritt antal element,

182
00:08:23,620 --> 00:08:25,620
du först vill sortera
vänstra halv, sedan höger halv,

183
00:08:25,620 --> 00:08:26,661
sedan sammanfoga dem tillsammans.

184
00:08:26,661 --> 00:08:28,630
Låt oss börja göra just detta.

185
00:08:28,630 --> 00:08:30,170
Här är ingången till åtta element.

186
00:08:30,170 --> 00:08:31,910
Nu är vi tittar på den vänstra halvan här.

187
00:08:31,910 --> 00:08:33,720
Hur sorterar jag fyra element?

188
00:08:33,720 --> 00:08:35,610
Jo jag först sortera vänstra halvan.

189
00:08:35,610 --> 00:08:37,720
Nu hur gör jag sorterar vänstra halvan?

190
00:08:37,720 --> 00:08:39,419
Jo jag har fått två delar.

191
00:08:39,419 --> 00:08:41,240
Så låt oss sortera dessa två element.

192
00:08:41,240 --> 00:08:44,540
2 är större än eller
lika med 2, naturligtvis.

193
00:08:44,540 --> 00:08:46,170
Så det första fallet inte är tillämpligt.

194
00:08:46,170 --> 00:08:49,010
>> Så jag har nu att sortera vänster
halv av dessa två element.

195
00:08:49,010 --> 00:08:50,870
Den vänstra halv, naturligtvis, är bara fyra.

196
00:08:50,870 --> 00:08:54,020
Så hur gör jag sortera en lista med en del?

197
00:08:54,020 --> 00:08:57,960
Nåja, det speciella basfallet
där uppe, så att säga, är tillämpligt.

198
00:08:57,960 --> 00:09:01,470
1 är mindre än 2, och min
Listan är verkligen storlek 1.

199
00:09:01,470 --> 00:09:02,747
Så jag återvänder bara.

200
00:09:02,747 --> 00:09:03,580
Jag gör ingenting.

201
00:09:03,580 --> 00:09:06,770
Och faktiskt, titta på vad jag har
gjort, är fyra redan sortering.

202
00:09:06,770 --> 00:09:09,220
Som jag är redan
delvis framgångsrik här.

203
00:09:09,220 --> 00:09:11,750
>> Nu verkar vara lite dum
krav, men det är sant.

204
00:09:11,750 --> 00:09:13,700
4 är en lista över storlek 1.

205
00:09:13,700 --> 00:09:15,090
Det är redan för sortering.

206
00:09:15,090 --> 00:09:16,270
Det är den vänstra halvan.

207
00:09:16,270 --> 00:09:18,010
Nu har jag sorterar den högra halvan.

208
00:09:18,010 --> 00:09:22,310
Min ingång är ett element, 8
På samma sätt som redan sortering.

209
00:09:22,310 --> 00:09:25,170
Dum, också, men återigen,
denna grundläggande princip

210
00:09:25,170 --> 00:09:28,310
kommer att tillåta oss att nu bygga
ovanpå detta framgångsrikt.

211
00:09:28,310 --> 00:09:32,260
4 sorterade, 8 sorteras nu
Vad var det sista steget?

212
00:09:32,260 --> 00:09:35,330
Så den tredje och sista steget, någon
gång du sorterar en lista, återkallelse,

213
00:09:35,330 --> 00:09:38,310
var att slå samman de två halvorna,
vänster och höger.

214
00:09:38,310 --> 00:09:39,900
Så låt oss göra just detta.

215
00:09:39,900 --> 00:09:41,940
Min vänstra halvan är, naturligtvis, 4.

216
00:09:41,940 --> 00:09:43,310
Min högra halvan är 8.

217
00:09:43,310 --> 00:09:44,100
>> Så låt oss göra detta.

218
00:09:44,100 --> 00:09:46,410
Först ska jag fördela
lite extra minne,

219
00:09:46,410 --> 00:09:48,680
att jag företräder här,
som bara en sekundär uppsättning,

220
00:09:48,680 --> 00:09:49,660
som är tillräckligt stor för att passa detta.

221
00:09:49,660 --> 00:09:52,243
Men du kan tänka dig att utvidga
rektangeln hela längden,

222
00:09:52,243 --> 00:09:53,290
om vi behöver mer senare.

223
00:09:53,290 --> 00:09:58,440
Hur tar jag 4 och 8, och sammanfoga
dessa två listor med storlek 1 tillsammans?

224
00:09:58,440 --> 00:10:00,270
Även här, ganska enkel.

225
00:10:00,270 --> 00:10:03,300
4 kommer först, sedan kommer 8.

226
00:10:03,300 --> 00:10:07,130
För om jag vill sortera
vänstra halv, sedan höger halv,

227
00:10:07,130 --> 00:10:09,900
och sedan slå ihop dessa två halvor
tillsammans, i sorterad ordning,

228
00:10:09,900 --> 00:10:11,940
4 kommer först, sedan kommer 8.

229
00:10:11,940 --> 00:10:15,810
>> Så vi verkar vara att göra framsteg, även
även om jag inte har gjort något egentliga arbetet.

230
00:10:15,810 --> 00:10:17,800
Men kom ihåg var vi befinner oss i berättelsen.

231
00:10:17,800 --> 00:10:19,360
Vi tog ursprungligen åtta element.

232
00:10:19,360 --> 00:10:21,480
Vi sorterade den vänstra halvan, vilket är 4.

233
00:10:21,480 --> 00:10:24,450
Sedan vi sorterade den vänstra halvan
av den vänstra halvan, vilket var 2.

234
00:10:24,450 --> 00:10:25,270
Och nu kör vi.

235
00:10:25,270 --> 00:10:26,920
Vi är klar med detta steg.

236
00:10:26,920 --> 00:10:29,930
>> Så om vi har sorteras
vänstra halvan av två, nu är vi

237
00:10:29,930 --> 00:10:32,130
måste sortera den högra halvan av två.

238
00:10:32,130 --> 00:10:35,710
Så den högra halvan av 2
dessa två värden här, 6 och 2.

239
00:10:35,710 --> 00:10:40,620
Så låt oss nu ta en ingång storlek
2, och sortera den vänstra halvan, och sedan

240
00:10:40,620 --> 00:10:42,610
den högra halv, och sedan
slås ihop dem.

241
00:10:42,610 --> 00:10:45,722
Nå hur gör jag sortera en lista med storlek
1, innehåller bara antalet 6?

242
00:10:45,722 --> 00:10:46,430
Jag är redan gjort.

243
00:10:46,430 --> 00:10:48,680
Den förteckningen över storleken 1 sorteras.

244
00:10:48,680 --> 00:10:52,140
>> Hur sorterar jag en annan lista över
storlek 1, den så kallade högra halv.

245
00:10:52,140 --> 00:10:54,690
Jo det är också redan sortering.

246
00:10:54,690 --> 00:10:56,190
Antalet 2 är ensam.

247
00:10:56,190 --> 00:11:00,160
Så nu har jag två halvor, vänster och
Okej, jag måste slå samman dem tillsammans.

248
00:11:00,160 --> 00:11:01,800
Låt mig ge mig själv lite extra utrymme.

249
00:11:01,800 --> 00:11:05,580
Och satte 2 där,
då 6 där, och därigenom

250
00:11:05,580 --> 00:11:10,740
sortering denna förteckning, vänster och höger,
och slå samman det tillsammans, i slutändan.

251
00:11:10,740 --> 00:11:12,160
Så jag är i något bättre form.

252
00:11:12,160 --> 00:11:16,250
Jag är inte klar, eftersom klart 4, 8, 2,
6 är inte den slutgiltiga beställning som jag vill.

253
00:11:16,250 --> 00:11:20,640
Men jag har nu två listor med storlek 2, att
har båda, respektive sorterats.

254
00:11:20,640 --> 00:11:24,580
Så nu om du spola tillbaka i ditt sinne
öga, där kom det lämnar oss?

255
00:11:24,580 --> 00:11:28,520
Jag började med åtta element, så jag
sållat det ner till den vänstra halvan av 4,

256
00:11:28,520 --> 00:11:31,386
sedan den vänstra halvan av två, och
sedan den högra halvan av två,

257
00:11:31,386 --> 00:11:34,510
Jag slutade därför sortering vänster
halv av 2, och den högra halvan av två,

258
00:11:34,510 --> 00:11:37,800
så vad är det tredje och sista steget här?

259
00:11:37,800 --> 00:11:41,290
Jag måste gå samman
två listor med storlek 2.

260
00:11:41,290 --> 00:11:42,040
Så låt oss gå vidare.

261
00:11:42,040 --> 00:11:43,940
Och på skärmen här, ge
mig lite extra minne,

262
00:11:43,940 --> 00:11:47,170
men tekniskt, märker att jag har
fick en hel del tomt utrymme där uppe

263
00:11:47,170 --> 00:11:47,670
där.

264
00:11:47,670 --> 00:11:50,044
Om jag vill vara särskilt
effektiva ytor klokt,

265
00:11:50,044 --> 00:11:52,960
Jag kunde bara börja flytta elementen
fram och tillbaka, topp och botten.

266
00:11:52,960 --> 00:11:55,460
Men bara för visuell skärpa,
Jag kommer att lägga ner nedan,

267
00:11:55,460 --> 00:11:56,800
att hålla saker fin och ren.

268
00:11:56,800 --> 00:11:58,150
>> Så jag har två listor med storlek 2.

269
00:11:58,150 --> 00:11:59,770
Den första listan har 4 och 8.

270
00:11:59,770 --> 00:12:01,500
Den andra listan har 2 och 6.

271
00:12:01,500 --> 00:12:03,950
Låt oss slå ihop dem
tillsammans i sorterad ordning.

272
00:12:03,950 --> 00:12:09,910
2 naturligtvis kommer först,
sedan 4, sedan 6, sedan 8.

273
00:12:09,910 --> 00:12:12,560
Och nu verkar vi vara att få
någonstans intressant.

274
00:12:12,560 --> 00:12:15,720
Nu har jag sorterat hälften av
lista, och av en tillfällighet, det är

275
00:12:15,720 --> 00:12:18,650
alla jämna nummer, men att
är faktiskt bara en tillfällighet.

276
00:12:18,650 --> 00:12:22,220
Och jag har nu sorteras vänster
hälften, så att det är 2, 4, 6, och 8.

277
00:12:22,220 --> 00:12:23,430
Ingenting är i ordning.

278
00:12:23,430 --> 00:12:24,620
Det känns som pågår.

279
00:12:24,620 --> 00:12:26,650
>> Nu känns det som om jag har
pratat evigt nu,

280
00:12:26,650 --> 00:12:29,850
så vad återstår att se om detta
algoritm är faktiskt mer effektiv.

281
00:12:29,850 --> 00:12:31,766
Men vi går igenom
det super metodiskt.

282
00:12:31,766 --> 00:12:34,060
En dator, naturligtvis,
skulle göra det så.

283
00:12:34,060 --> 00:12:34,840
Så var är vi?

284
00:12:34,840 --> 00:12:36,180
Vi började med åtta element.

285
00:12:36,180 --> 00:12:37,840
Jag sorterade den vänstra halvan av fyra.

286
00:12:37,840 --> 00:12:39,290
Jag verkar vara klar med det.

287
00:12:39,290 --> 00:12:42,535
Så nu nästa steg är att
sortera den högra halvan av fyra.

288
00:12:42,535 --> 00:12:44,410
Och denna del kan vi gå
genom lite mer

289
00:12:44,410 --> 00:12:47,140
snabbt, även om du är
Välkommen att spola tillbaka eller pausa, bara

290
00:12:47,140 --> 00:12:49,910
tänka igenom det på
din egen takt, men vad

291
00:12:49,910 --> 00:12:53,290
vi har nu är en möjlighet att
göra exakt samma algoritm på fyra

292
00:12:53,290 --> 00:12:54,380
olika nummer.

293
00:12:54,380 --> 00:12:57,740
>> Så låt oss gå vidare och fokusera på
den högra halvan, som vi är här.

294
00:12:57,740 --> 00:13:01,260
Den vänstra halvan av det
högra halv, och nu

295
00:13:01,260 --> 00:13:04,560
vänstra halv av den vänstra
hälften av det högra halvan,

296
00:13:04,560 --> 00:13:08,030
och hur jag sortera en lista med storlek
1 innehåller bara antalet 1?

297
00:13:08,030 --> 00:13:09,030
Det är redan gjort.

298
00:13:09,030 --> 00:13:11,830
Hur gör jag samma sak för en lista
storlek 1 innehåller bara 7?

299
00:13:11,830 --> 00:13:12,840
Det är redan gjort.

300
00:13:12,840 --> 00:13:16,790
Steg tre för Halv sedan
är att slå samman dessa två element

301
00:13:16,790 --> 00:13:20,889
till en ny förteckning över storlek 2, 1 och 7.

302
00:13:20,889 --> 00:13:23,180
Inte tycks ha gjort allt
så mycket intressant arbete.

303
00:13:23,180 --> 00:13:24,346
Låt oss se vad som händer härnäst.

304
00:13:24,346 --> 00:13:29,210
Jag sorterade bara den vänstra halvan av
högra halvan av min original- ingång.

305
00:13:29,210 --> 00:13:32,360
Nu ska vi sortera rätt
hälften, som innehåller 5 och 3.

306
00:13:32,360 --> 00:13:35,740
Låt oss återigen titta på vänster
halv, sorteras, högra halv, sorteras,

307
00:13:35,740 --> 00:13:39,120
och slå ihop dessa två tillsammans,
i någon extra utrymme,

308
00:13:39,120 --> 00:13:41,670
3 kommer först, sedan kommer 5.

309
00:13:41,670 --> 00:13:46,190
Och så nu har vi sorterat
vänstra halvan av den högra halv

310
00:13:46,190 --> 00:13:49,420
av det ursprungliga problemet, och
den högra halvan av den högra halv

311
00:13:49,420 --> 00:13:50,800
av det ursprungliga problemet.

312
00:13:50,800 --> 00:13:52,480
Vad är den tredje och sista steg?

313
00:13:52,480 --> 00:13:54,854
Jo för att slå samman de två halvorna.

314
00:13:54,854 --> 00:13:57,020
Så låt mig få mig lite
extra utrymme, men, återigen, jag

315
00:13:57,020 --> 00:13:58,699
skulle kunna vara att använda det lediga utrymme där uppe.

316
00:13:58,699 --> 00:14:00,490
Men vi kommer att hålla
det enkelt visuellt.

317
00:14:00,490 --> 00:14:07,070
Låt mig samman i nu 1, och
sedan tre och sedan fem, och sedan 7.

318
00:14:07,070 --> 00:14:10,740
Därmed lämnar mig nu med
högra halvan av det ursprungliga problemet

319
00:14:10,740 --> 00:14:12,840
som är perfekt för sortering.

320
00:14:12,840 --> 00:14:13,662
>> Så vad återstår?

321
00:14:13,662 --> 00:14:16,120
Jag känner att jag håller säger
samma saker igen och igen,

322
00:14:16,120 --> 00:14:18,700
men det är reflekterande av
Att vi använder rekursion.

323
00:14:18,700 --> 00:14:21,050
Processen med att använda en
algoritm igen, och igen,

324
00:14:21,050 --> 00:14:23,940
på mindre delmängder av
det ursprungliga problemet.

325
00:14:23,940 --> 00:14:27,580
Så jag har nu en vänster sorteras
halv av det ursprungliga problemet.

326
00:14:27,580 --> 00:14:30,847
Jag har en rätt sorterad halv
av det ursprungliga problemet.

327
00:14:30,847 --> 00:14:32,180
Vad är det tredje och sista steget?

328
00:14:32,180 --> 00:14:33,590
Åh, det är en sammanslagning.

329
00:14:33,590 --> 00:14:34,480
Så låt oss göra det.

330
00:14:34,480 --> 00:14:36,420
Låt oss anslå några ytterligare
minne, men min Gud, vi

331
00:14:36,420 --> 00:14:37,503
kunde sätta det någonstans nu.

332
00:14:37,503 --> 00:14:40,356
Vi har så mycket utrymme
för oss, men vi kommer att hålla det enkelt.

333
00:14:40,356 --> 00:14:42,730
Istället för att gå tillbaka och
fram med vår ursprungliga minne,

334
00:14:42,730 --> 00:14:44,480
låt oss bara göra det
visuellt här nere nedan

335
00:14:44,480 --> 00:14:47,240
till slut upp en sammanslagning av
vänstra halvan och den högra halvan.

336
00:14:47,240 --> 00:14:49,279
>> Så genom att slå samman, vad behöver jag göra?

337
00:14:49,279 --> 00:14:50,820
Jag vill ta elementen i ordning.

338
00:14:50,820 --> 00:14:53,230
Så titta på den vänstra halvan,
Jag ser första siffran är 2.

339
00:14:53,230 --> 00:14:55,230
Jag tittar på den högra halvan,
Jag ser det första numret

340
00:14:55,230 --> 00:14:58,290
är en, så självklart som
Antalet vill jag rycka ut,

341
00:14:58,290 --> 00:15:00,430
och sätts i första rummet i min slutliga listan?

342
00:15:00,430 --> 00:15:01,449
Naturligtvis, en.

343
00:15:01,449 --> 00:15:02,990
Nu vill jag ställa samma fråga.

344
00:15:02,990 --> 00:15:05,040
På den vänstra halvan, jag har
fortfarande fick nummer 2.

345
00:15:05,040 --> 00:15:07,490
På höger halv,
Jag har siffran 3.

346
00:15:07,490 --> 00:15:08,930
Som man vill jag välja?

347
00:15:08,930 --> 00:15:11,760
Naturligtvis, nummer 2 och
Nu märker kandidaterna

348
00:15:11,760 --> 00:15:13,620
är 4 till vänster, 3 på höger sida.

349
00:15:13,620 --> 00:15:15,020
Låt oss, naturligtvis välja 3.

350
00:15:15,020 --> 00:15:18,020
Nu kandidaterna är 4 på
vänster, 5 höger.

351
00:15:18,020 --> 00:15:19,460
Vi, naturligtvis, välj 4.

352
00:15:19,460 --> 00:15:21,240
6 till vänster, 5 höger.

353
00:15:21,240 --> 00:15:22,730
Vi, naturligtvis, välj 5.

354
00:15:22,730 --> 00:15:25,020
6 till vänster, 7 till höger.

355
00:15:25,020 --> 00:15:29,320
Vi väljer 6, och då är vi
välja 7, och sedan väljer vi åtta.

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

357
00:15:30,100 --> 00:15:34,370
>> Så ett stort antal ord senare, vi
har sorterat denna lista över åtta element

358
00:15:34,370 --> 00:15:38,450
i en förteckning över en till åtta,
som är ökande med varje steg,

359
00:15:38,450 --> 00:15:40,850
men hur mycket tid gjorde
det tar oss att göra det.

360
00:15:40,850 --> 00:15:43,190
Jo jag har medvetet
lagda saker ut pictorially

361
00:15:43,190 --> 00:15:46,330
här, så att vi kan typ av
se eller uppskatta divisionen

362
00:15:46,330 --> 00:15:49,060
i erövrande som har hänt.

363
00:15:49,060 --> 00:15:52,830
>> I själva verket om du tittar tillbaka på spåren,
Jag har lämnat alla dessa prickade linjer

364
00:15:52,830 --> 00:15:55,660
i platshållare, kan du,
typ av, se, i omvänd ordning,

365
00:15:55,660 --> 00:15:58,800
om du typ av ser tillbaka i
historia nu, min ursprungliga listan

366
00:15:58,800 --> 00:16:00,250
är naturligtvis storlek 8.

367
00:16:00,250 --> 00:16:03,480
Och sedan tidigare, var jag
arbetar med två listor med storlek 4,

368
00:16:03,480 --> 00:16:08,400
och sedan fyra listor över storlek 2,
och sedan åtta listor med storlek 1.

369
00:16:08,400 --> 00:16:10,151
>> Så vad gör detta,
typ av, påminna dig om?

370
00:16:10,151 --> 00:16:11,858
Jo, faktiskt, något av
de algoritmer vi ve

371
00:16:11,858 --> 00:16:14,430
tittat på hittills där vi
klyftan, och dela och dela,

372
00:16:14,430 --> 00:16:19,500
hålla med saker igen, och
igen, resulterar i denna allmänna idé.

373
00:16:19,500 --> 00:16:23,100
Och så det finns något
logaritmisk pågår här.

374
00:16:23,100 --> 00:16:26,790
Och det är inte riktigt log n, men
det finns en logaritmisk komponent

375
00:16:26,790 --> 00:16:28,280
vad vi just har gjort.

376
00:16:28,280 --> 00:16:31,570
>> Låt oss nu överväga hur det egentligen är.

377
00:16:31,570 --> 00:16:34,481
Så log n, återigen var
en stor gångtid,

378
00:16:34,481 --> 00:16:36,980
när vi gjorde något liknande
binär sökning, som vi nu kallar det,

379
00:16:36,980 --> 00:16:40,090
klyftan och erövra strategi
via vilken vi hittade Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Nu tekniskt.

381
00:16:41,020 --> 00:16:43,640
Det är log bas 2 av n, även
men i de flesta matematiska klasser,

382
00:16:43,640 --> 00:16:45,770
10 är vanligtvis basen att du tar.

383
00:16:45,770 --> 00:16:48,940
Men datavetare nästan alltid
tänka och tala i termer av basen 2,

384
00:16:48,940 --> 00:16:52,569
så vi vanligtvis bara säga logg över
n, i stället för log bas 2 av n,

385
00:16:52,569 --> 00:16:55,110
men de är exakt en och
Samma i världen av datorn

386
00:16:55,110 --> 00:16:57,234
vetenskap, och som en sidoreplik,
det finns en konstant faktor

387
00:16:57,234 --> 00:17:01,070
skillnaden mellan de två, så det är
omtvistad ändå, för mer formella skäl.

388
00:17:01,070 --> 00:17:04,520
>> Men nu, vad vi bryr
om är detta exempel.

389
00:17:04,520 --> 00:17:08,520
Så låt oss inte bevisa med gott exempel, men
stone använda ett exempel på siffrorna

390
00:17:08,520 --> 00:17:10,730
till hands som en sanity check, om ni så vill.

391
00:17:10,730 --> 00:17:14,510
Så tidigare formeln var log bas
2 n, men vad är n i detta fall.

392
00:17:14,510 --> 00:17:18,526
Jag hade n originalnummer, eller 8
av ursprungliga antalet specifikt.

393
00:17:18,526 --> 00:17:20,359
Nu har det gått lite
tag, men jag är ganska

394
00:17:20,359 --> 00:17:25,300
Se till att log bas 2
av värdet 8 är 3,

395
00:17:25,300 --> 00:17:29,630
och faktiskt, vad är trevligt om det är
att 3 är exakt det antal gånger

396
00:17:29,630 --> 00:17:33,320
att du kan dela upp en lista
med längden 8 igen, och igen,

397
00:17:33,320 --> 00:17:36,160
och igen, tills du är kvar
med listor över bara storlek 1.

398
00:17:36,160 --> 00:17:36,660
Höger?

399
00:17:36,660 --> 00:17:40,790
8 går till 4, går till 2,
går till ett, och det är

400
00:17:40,790 --> 00:17:43,470
reflekterande av just detta
bild vi hade bara en stund sedan.

401
00:17:43,470 --> 00:17:47,160
Så lite förnuft kontrollera om var
logaritmen är faktiskt inblandad.

402
00:17:47,160 --> 00:17:50,180
>> Så nu, vad är inblandad här? n.

403
00:17:50,180 --> 00:17:53,440
Så märker att varje
tid jag dela listan,

404
00:17:53,440 --> 00:17:58,260
om än i omvänd ordning i historien
här, jag var fortfarande gör n saker.

405
00:17:58,260 --> 00:18:02,320
Det sammanslagning steg krävs att
Jag rör var och en av numren,

406
00:18:02,320 --> 00:18:05,060
För att dra det till
dess lämplig plats.

407
00:18:05,060 --> 00:18:10,760
Så även om höjden av detta
diagram är storlek log n n eller 3,

408
00:18:10,760 --> 00:18:13,860
specifikt, med andra ord,
Jag gjorde tre divisioner här.

409
00:18:13,860 --> 00:18:18,800
Hur mycket arbete gjorde jag horisontellt
längs denna tabell varje gång?

410
00:18:18,800 --> 00:18:21,110
>> Tja, jag gjorde n stegen
arbete, för om jag har

411
00:18:21,110 --> 00:18:24,080
fick fyra element och fyra element,
och jag måste slå samman dem tillsammans.

412
00:18:24,080 --> 00:18:26,040
Jag behöver gå igenom
dessa fyra och dessa fyra,

413
00:18:26,040 --> 00:18:28,123
i slutändan att slå ihop dem
tillbaka in i åtta delar.

414
00:18:28,123 --> 00:18:32,182
Om omvänt Jag har åtta fingrar
hit, som jag inte, och åtta

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Om jag har
fick fyra fingrar hit,

416
00:18:34,390 --> 00:18:37,380
som jag gör, fyra fingrar
hit, som jag gör,

417
00:18:37,380 --> 00:18:40,590
då det är samma
exempel som förut, om jag gör

418
00:18:40,590 --> 00:18:44,010
har åtta fingrar men i
Totalt, som jag kan, typ av, gör.

419
00:18:44,010 --> 00:18:47,950
Jag kan exakt göra här,
då kan jag säkert

420
00:18:47,950 --> 00:18:50,370
slå ihop alla dessa listor
storlek 1 tillsammans.

421
00:18:50,370 --> 00:18:54,050
Men jag har verkligen att se
vid varje element exakt en gång.

422
00:18:54,050 --> 00:18:59,640
Så höjden av denna process är log n,
bredden av denna process, så att säga,

423
00:18:59,640 --> 00:19:02,490
är n, så vad vi verkar
att ha, i slutändan, är

424
00:19:02,490 --> 00:19:06,470
en gångtid av storlek n gånger log n.

425
00:19:06,470 --> 00:19:08,977
>> Med andra ord, delade vi
listan, log n gånger,

426
00:19:08,977 --> 00:19:11,810
men varje gång vi gjorde det, hade vi
beröra var och en av elementen

427
00:19:11,810 --> 00:19:13,560
för att slå ihop dem
alla tillsammans, vilket

428
00:19:13,560 --> 00:19:18,120
N steg, så vi har n gånger log n,
eller som en datavetare skulle säga,

429
00:19:18,120 --> 00:19:20,380
asymptotiskt, vilket
skulle vara den stora ord

430
00:19:20,380 --> 00:19:22,810
för att beskriva den övre
bunden på en gångtid,

431
00:19:22,810 --> 00:19:28,010
Vi kör i en stor o
av log n tid, så att säga.

432
00:19:28,010 --> 00:19:31,510
>> Nu är betydande, eftersom
ihåg vad de löpande tiderna var

433
00:19:31,510 --> 00:19:34,120
med bubbelsortering och urval
sortera och insättningssortering,

434
00:19:34,120 --> 00:19:38,200
och även några andra som finns,
n kvadrat var där vi var på.

435
00:19:38,200 --> 00:19:39,990
Och du kan typ av se det här.

436
00:19:39,990 --> 00:19:45,720
Om n kvadrat är uppenbarligen n gånger
n, men här har vi n gånger log n,

437
00:19:45,720 --> 00:19:48,770
och vi vet redan från vecka
noll, att log n, den logaritmiska,

438
00:19:48,770 --> 00:19:50,550
är bättre än något linjärt.

439
00:19:50,550 --> 00:19:52,930
När allt kommer omkring, minns bilden
med den röda och den gula

440
00:19:52,930 --> 00:19:56,500
och de gröna linjerna som vi drog, den
grön logaritmisk linjen var mycket lägre.

441
00:19:56,500 --> 00:20:00,920
Och därför, mycket bättre och snabbare
än de raka gula och röda linjer,

442
00:20:00,920 --> 00:20:05,900
n gånger log n är verkligen bättre
än n gånger n eller n kvadrat.

443
00:20:05,900 --> 00:20:09,110
>> Så verkar vi ha
identifierat en algoritm merge

444
00:20:09,110 --> 00:20:11,870
sortera som körs i mycket
snabbare tid, och faktiskt,

445
00:20:11,870 --> 00:20:16,560
det är därför, tidigare i veckan, då
Vi såg att tävlingen mellan bubbla

446
00:20:16,560 --> 00:20:20,750
sort, val av sort, och sammanfoga
sort, merge sort verkligen, verkligen vunnit.

447
00:20:20,750 --> 00:20:23,660
Och faktiskt, vi inte ens vänta
för bubbelsortering och val Sortera

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

449
00:20:24,790 --> 00:20:27,410
>> Nu ska vi ta en annan pass
på detta, från en något mer

450
00:20:27,410 --> 00:20:31,030
formell perspektiv, precis
fall resonans detta bättre

451
00:20:31,030 --> 00:20:33,380
än högre diskussionsnivå.

452
00:20:33,380 --> 00:20:34,880
Så här är algoritmen igen.

453
00:20:34,880 --> 00:20:36,770
Låt oss fråga oss själva,
vad gångtid

454
00:20:36,770 --> 00:20:39,287
är detta algoritmer olika steg?

455
00:20:39,287 --> 00:20:41,620
Låt oss dela upp det i den första
fallet och det andra fallet.

456
00:20:41,620 --> 00:20:46,280
IF och annat i IF fallet
Om n är mindre än 2, bara tillbaka.

457
00:20:46,280 --> 00:20:47,580
Känns som konstant tid.

458
00:20:47,580 --> 00:20:50,970
Det är, typ av, liksom två steg,
Om n är mindre än 2, sedan tillbaka.

459
00:20:50,970 --> 00:20:54,580
Men som vi sade på måndagen,
konstant tid, eller stora o av 1,

460
00:20:54,580 --> 00:20:57,130
kan vara två steg, tre
steg, även 1000 steg.

461
00:20:57,130 --> 00:20:59,870
Det viktiga är att det är
ett konstant antal steg.

462
00:20:59,870 --> 00:21:03,240
Så gula markerade pseudo
Här körs i, vi kallar det,

463
00:21:03,240 --> 00:21:04,490
konstant tid.

464
00:21:04,490 --> 00:21:06,780
Så mer formellt, och
vi kommer att-- detta

465
00:21:06,780 --> 00:21:09,910
kommer att vara i vilken utsträckning vi
formalisera denna rätt now-- T n,

466
00:21:09,910 --> 00:21:15,030
körtiden för ett problem
som tar n things som indata,

467
00:21:15,030 --> 00:21:19,150
lika stor o av en,
Om n är mindre än 2.

468
00:21:19,150 --> 00:21:20,640
Så det är villkorat av att.

469
00:21:20,640 --> 00:21:24,150
Så för att vara tydlig, IF n är mindre än
2, har vi en mycket kort lista, sedan

470
00:21:24,150 --> 00:21:29,151
drifttid, T från n, där n är
1 eller 0, i detta mycket specifika fall,

471
00:21:29,151 --> 00:21:30,650
det bara kommer att vara konstant tid.

472
00:21:30,650 --> 00:21:32,691
Det kommer att ta ett
steg, två steg, vad som helst.

473
00:21:32,691 --> 00:21:33,950
Det är ett fast antal steg.

474
00:21:33,950 --> 00:21:38,840
>> Så saftigt delen måste ju vara i
det andra fallet i pseudo.

475
00:21:38,840 --> 00:21:40,220
Else fallet.

476
00:21:40,220 --> 00:21:44,870
Sortera vänstra halvan av element, sortera rätt
hälften av element, slå samman sorterade halvor.

477
00:21:44,870 --> 00:21:46,800
Hur lång tid tar var och en av dessa åtgärder ta?

478
00:21:46,800 --> 00:21:49,780
Tja, om driften
tid att sortera n element

479
00:21:49,780 --> 00:21:53,010
är, låt oss kalla det mycket
generiskt, T av n,

480
00:21:53,010 --> 00:21:55,500
sedan sortera vänster
halv av elementen

481
00:21:55,500 --> 00:21:59,720
är, typ av, som att säga,
T n dividerat med 2,

482
00:21:59,720 --> 00:22:03,000
och på liknande sätt att sortera den högra halv
element är, typ av, som att säga,

483
00:22:03,000 --> 00:22:06,974
T n delas 2, och sedan
sammanslagning av de sorterade halvor.

484
00:22:06,974 --> 00:22:08,890
Tja, om jag har några
antal element här,

485
00:22:08,890 --> 00:22:11,230
liknande fyra, och något antal
av element här, som fyra,

486
00:22:11,230 --> 00:22:14,650
och jag måste slå samman var och en av dessa fyra
i, och var och en av dessa fyra i en

487
00:22:14,650 --> 00:22:17,160
efter den andra, så att
i slutändan har jag åtta element.

488
00:22:17,160 --> 00:22:20,230
Det känns som det är stor o av n steg?

489
00:22:20,230 --> 00:22:23,500
Om jag har n fingrar och var och en av
dem måste slås samman på plats,

490
00:22:23,500 --> 00:22:25,270
det är som en annan n steg.

491
00:22:25,270 --> 00:22:27,360
>> Så faktiskt formulaically,
Vi kan uttrycka detta,

492
00:22:27,360 --> 00:22:29,960
om än lite läskigt i början
blick, men det är något

493
00:22:29,960 --> 00:22:31,600
som fångar just denna logik.

494
00:22:31,600 --> 00:22:35,710
Gångtiden, T n, om n
är större än eller lika med 2.

495
00:22:35,710 --> 00:22:42,500
I detta fall, ELSE fallet, T är av n
dividerad med två, plus T från N delat med 2,

496
00:22:42,500 --> 00:22:45,320
plus stora o n, en del
linjär antal steg,

497
00:22:45,320 --> 00:22:51,630
kanske exakt n, kanske 2 gånger
n, men det är ungefär, ordning n.

498
00:22:51,630 --> 00:22:54,060
Så att är också hur vi kan
uttrycka detta formulaically.

499
00:22:54,060 --> 00:22:56,809
Nu skulle du inte vet detta om
du har spelat in det i ditt sinne,

500
00:22:56,809 --> 00:22:58,710
eller slå upp det i
baksidan av en lärobok, som

501
00:22:58,710 --> 00:23:00,501
kanske har lite
fusklapp i slutet,

502
00:23:00,501 --> 00:23:03,940
men detta är verkligen kommer att
ge oss en stor o n log n

503
00:23:03,940 --> 00:23:06,620
eftersom återfall som
du ser här på skärmen,

504
00:23:06,620 --> 00:23:09,550
om du faktiskt gjorde det, med
ett oändligt antal exempel,

505
00:23:09,550 --> 00:23:13,000
eller om du gjorde det formulaically, skulle du
se att detta, eftersom denna formel

506
00:23:13,000 --> 00:23:17,100
själv är rekursiv, med t från
n över något till höger,

507
00:23:17,100 --> 00:23:21,680
och t n vänsterkanten, kan detta
faktiskt skall uttryckas, i slutändan,

508
00:23:21,680 --> 00:23:24,339
så stor taget om n log n.

509
00:23:24,339 --> 00:23:26,130
Om inte övertygad, det är
bra för nu, bara

510
00:23:26,130 --> 00:23:28,960
ta på tro, att det är, faktiskt,
vad som återkommande leder till,

511
00:23:28,960 --> 00:23:31,780
men detta är bara lite mer av en
matematisk metod att titta

512
00:23:31,780 --> 00:23:36,520
vid gångtid merge sort
baserat på dess pseudokod ensam.

513
00:23:36,520 --> 00:23:39,030
>> Nu ska vi ta en bit av en
paus från allt detta,

514
00:23:39,030 --> 00:23:41,710
och ta en titt på en
vissa tidigare senator, som

515
00:23:41,710 --> 00:23:44,260
kanske ser lite bekant,
som satte sig ner med Googles Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, för en tid sedan, för en intervju
på scenen, framför en hel drös

517
00:23:48,410 --> 00:23:53,710
människor, talar slutligen om
ett ämne, det är ganska nu bekant.

518
00:23:53,710 --> 00:23:54,575
Låt oss ta en titt.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Nu Senator,
du är här på Google,

521
00:24:03,890 --> 00:24:09,490
och jag gillar att tänka på
ordförandeskapet som en anställningsintervju.

522
00:24:09,490 --> 00:24:11,712
Nu är det svårt att få ett jobb som president.

523
00:24:11,712 --> 00:24:12,670
PRESIDENT OBAMA: Rätt.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Och du är
kommer att göra [OHÖRBAR] nu.

525
00:24:13,940 --> 00:24:15,523
Det är också svårt att få jobb på Google.

526
00:24:15,523 --> 00:24:17,700
PRESIDENT OBAMA: Rätt.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Vi har frågor,
och vi ber våra kandidater frågor,

528
00:24:21,330 --> 00:24:24,310
och detta är från 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: Vad?

531
00:24:27,005 --> 00:24:28,130
Ni tror att jag skojar?

532
00:24:28,130 --> 00:24:30,590
Det är rätt här.

533
00:24:30,590 --> 00:24:33,490
Vad är det mest effektiva sättet att
sortera en miljon 32 bitars heltal?

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: Ibland
kanske jag är ledsen, maybe--

537
00:24:41,020 --> 00:24:42,750
PRESIDENT OBAMA: Nej, nej,
nej, nej, nej, jag think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Det är inte det--

539
00:24:43,240 --> 00:24:45,430
PRESIDENT OBAMA: I
tror, ​​jag tror att bubblan

540
00:24:45,430 --> 00:24:46,875
sort skulle vara fel väg att gå.

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

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

543
00:24:50,535 --> 00:24:52,200
Som berättade detta?

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

545
00:24:54,020 --> 00:24:55,590
Jag gjorde inte datavetenskap on--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDENT OBAMA: Vi har
fick våra spioner där.

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

548
00:24:59,860 --> 00:25:03,370
Låt oss lämna bakom oss nu
teoretisk värld av algoritmer

549
00:25:03,370 --> 00:25:06,520
i asymptotiska analys
därav, och återgå till vissa ämnen

550
00:25:06,520 --> 00:25:09,940
från vecka noll och ett, och start
att ta bort några stödhjul,

551
00:25:09,940 --> 00:25:10,450
om du vill.

552
00:25:10,450 --> 00:25:13,241
Så att du verkligen förstår
i slutändan från grunden, vad är

553
00:25:13,241 --> 00:25:16,805
pågår under huven, när du
skriva, kompilera och exekvera program.

554
00:25:16,805 --> 00:25:19,680
Minns i synnerhet att detta var
den första C-programmet vi tittat på,

555
00:25:19,680 --> 00:25:22,840
en kanonisk, enkelt program
av slag, relativt sett,

556
00:25:22,840 --> 00:25:24,620
där det skrivs, Hello World.

557
00:25:24,620 --> 00:25:27,610
Och minns att jag sa, processen
att källkoden går igenom

558
00:25:27,610 --> 00:25:28,430
är just detta.

559
00:25:28,430 --> 00:25:31,180
Du tar din källkod, passera
det genom en kompilator, som Clang,

560
00:25:31,180 --> 00:25:34,650
och ut kommer objektkod, att
kan se ut så här, nollor och ettor

561
00:25:34,650 --> 00:25:37,880
att datorns processor, central
behandlingsenhet eller hjärnan,

562
00:25:37,880 --> 00:25:39,760
i slutändan förstår.

563
00:25:39,760 --> 00:25:42,460
>> Det visar sig att det är en
lite av en förenkling,

564
00:25:42,460 --> 00:25:44,480
att vi är nu i en
ståndpunkt att retas isär

565
00:25:44,480 --> 00:25:46,720
att förstå vad som verkligen varit
pågår under huven

566
00:25:46,720 --> 00:25:48,600
varje gång du kör
Klang, eller mer generellt,

567
00:25:48,600 --> 00:25:53,040
varje gång du gör ett program,
med hjälp av fabrikat och CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Framför allt sånt
detta först genereras,

569
00:25:56,760 --> 00:25:58,684
när du först kompilera ditt program.

570
00:25:58,684 --> 00:26:00,600
Med andra ord, när man
ta din källkod

571
00:26:00,600 --> 00:26:04,390
och kompilera den, vad är först
matas ut av klang

572
00:26:04,390 --> 00:26:06,370
är något som kallas montering kod.

573
00:26:06,370 --> 00:26:08,990
Och i själva verket ser det precis som här.

574
00:26:08,990 --> 00:26:11,170
>> Jag körde ett kommando på
kommandoraden tidigare.

575
00:26:11,170 --> 00:26:16,260
Klang streck kapital s hej.c,
och detta skapade en fil

576
00:26:16,260 --> 00:26:19,490
för mig kallade hello.s,
inuti vilken var exakt

577
00:26:19,490 --> 00:26:22,290
dessa halter, och lite mer
ovan och lite mer nedan,

578
00:26:22,290 --> 00:26:25,080
men jag har lagt mediebranschen
information här på skärmen.

579
00:26:25,080 --> 00:26:29,190
Och om du tittar noga ser du
åtminstone ett par bekanta sökord.

580
00:26:29,190 --> 00:26:31,330
Vi har huvud upptill.

581
00:26:31,330 --> 00:26:35,140
Vi har printf ner i mitten.

582
00:26:35,140 --> 00:26:38,670
Och vi har också hallå världen
bakstreck n inom citationstecken ner nedan.

583
00:26:38,670 --> 00:26:42,450
>> Och allt annat här
är instruktionerna mycket låg nivå

584
00:26:42,450 --> 00:26:45,500
att datorns processor förstår.

585
00:26:45,500 --> 00:26:50,090
CPU instruktioner som rör minne
runt, att last strängar från minnet,

586
00:26:50,090 --> 00:26:52,750
och i slutändan, print
saker på skärmen.

587
00:26:52,750 --> 00:26:56,780
Nu vad som händer men efter
denna assemblerkod genereras?

588
00:26:56,780 --> 00:26:59,964
I slutändan, tror du verkligen,
fortfarande genererar objektkod.

589
00:26:59,964 --> 00:27:02,630
Men de åtgärder som verkligen har
pågått under huven

590
00:27:02,630 --> 00:27:04,180
ser lite mer om detta.

591
00:27:04,180 --> 00:27:08,390
Källkod blir assemblerkod,
som sedan blir objektkod,

592
00:27:08,390 --> 00:27:11,930
och de avgörande orden här är att,
när du kompilerar källkoden,

593
00:27:11,930 --> 00:27:16,300
ut kommer assemblerkod, och sedan
när du monterar din assemblerkod,

594
00:27:16,300 --> 00:27:17,800
ut kommer objektkod.

595
00:27:17,800 --> 00:27:20,360
>> Nu Clang är super sofistikerad,
som en hel del kompilatorer,

596
00:27:20,360 --> 00:27:23,151
och det gör alla dessa steg
tillsammans, och det gör inte nödvändigtvis

597
00:27:23,151 --> 00:27:25,360
utgång någon mellanliggande
filer som du även kan se.

598
00:27:25,360 --> 00:27:28,400
Det sammanställer bara saker,
vilket är den allmänna term som

599
00:27:28,400 --> 00:27:30,000
beskriver hela denna process.

600
00:27:30,000 --> 00:27:32,000
Men om du verkligen vill
att vara särskilt, det finns

601
00:27:32,000 --> 00:27:34,330
mycket mer händer där liksom.

602
00:27:34,330 --> 00:27:38,860
>> Men låt oss också tänka nu att även
det super enkelt program, hej.c,

603
00:27:38,860 --> 00:27:40,540
kallas en funktion.

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

605
00:27:41,870 --> 00:27:46,900
Men jag ville inte skriva printf, ja,
som kommer med c, så att säga.

606
00:27:46,900 --> 00:27:51,139
Det är en funktion återkallelse som är
deklarerats i standard io.h, som

607
00:27:51,139 --> 00:27:53,180
är en header-fil, som
är ett ämne vi faktiskt

608
00:27:53,180 --> 00:27:55,780
dyka in i mer djup snart.

609
00:27:55,780 --> 00:27:58,000
Men en header-fil är
typiskt åtföljs

610
00:27:58,000 --> 00:28:02,920
med en kod fil, källkod fil, så
ungefär som det finns standard io.h.

611
00:28:02,920 --> 00:28:05,930
>> Någon gång sedan, någon,
eller någons, skrev också

612
00:28:05,930 --> 00:28:11,040
en fil som heter standard io.c i
vilket den faktiska definitioner,

613
00:28:11,040 --> 00:28:15,220
eller implementeringar av printf,
och klasar av andra funktioner,

614
00:28:15,220 --> 00:28:16,870
faktiskt skrivs.

615
00:28:16,870 --> 00:28:22,140
Så med tanke på att om vi överväga att ha
Här till vänster, hej.c, att när

616
00:28:22,140 --> 00:28:26,250
sammanställt, ger oss hello.s, även om
Clang inte bry besparing på en plats

617
00:28:26,250 --> 00:28:31,360
Vi kan se det, och att assemblerkod
blir monteras hello.o, vilket

618
00:28:31,360 --> 00:28:34,630
är faktiskt standardnamnet
med tanke på när du kompilera källkod

619
00:28:34,630 --> 00:28:39,350
koda till objektkod, men är inte
helt redo att köra det ännu,

620
00:28:39,350 --> 00:28:41,460
eftersom ytterligare ett steg
måste ske, och har

621
00:28:41,460 --> 00:28:44,440
pågått under de senaste få
veckor, kanske okänt för dig.

622
00:28:44,440 --> 00:28:47,290
>> Specifikt någonstans
i CS50 IDE, och detta,

623
00:28:47,290 --> 00:28:49,870
också kommer att vara lite av en
förenkling för ett ögonblick,

624
00:28:49,870 --> 00:28:54,670
Det finns, eller var på en tid,
en fil som heter standard io.c,

625
00:28:54,670 --> 00:28:58,440
att någon sammanställs i
standard io.s eller motsvarande,

626
00:28:58,440 --> 00:29:02,010
att någon sedan monteras
till standard io.o,

627
00:29:02,010 --> 00:29:04,600
eller det visar sig i en
något annorlunda fil

628
00:29:04,600 --> 00:29:07,220
format som kan ha en annan
fil förlängning helt och hållet,

629
00:29:07,220 --> 00:29:11,720
men i teori och begrepps exakt
dessa åtgärder måste ske i någon form.

630
00:29:11,720 --> 00:29:14,060
Vilket betyder att, som nu
när jag skriver ett program,

631
00:29:14,060 --> 00:29:17,870
hej.c, som bara säger hej världen,
och jag använder någon annans kod

632
00:29:17,870 --> 00:29:22,480
som printf, som en gång var på en
tid, i en fil som heter standard io.c,

633
00:29:22,480 --> 00:29:26,390
sedan på något sätt måste jag ta min
objekt kod, mina ettor och nollor,

634
00:29:26,390 --> 00:29:29,260
och den personens objekt
kod, eller ettor och nollor,

635
00:29:29,260 --> 00:29:34,970
och på något sätt koppla ihop dem till
en slutlig fil, som heter hello, att

636
00:29:34,970 --> 00:29:38,070
har alla nollor och
de från min huvudsakliga funktion,

637
00:29:38,070 --> 00:29:40,830
och alla nollor
och sådana för printf.

638
00:29:40,830 --> 00:29:44,900
>> Och faktiskt är det sista process
kallas, länka din objektkod.

639
00:29:44,900 --> 00:29:47,490
Vars utgång
är en körbar fil.

640
00:29:47,490 --> 00:29:49,780
Så i rättvisans namn, vid
slutet av dagen, ingenting

641
00:29:49,780 --> 00:29:52,660
har förändrats sedan vecka ett, när vi
började sammanställa program.

642
00:29:52,660 --> 00:29:55,200
I själva verket allt detta har varit
händer under huven,

643
00:29:55,200 --> 00:29:57,241
men nu är vi i en position
där vi kan faktiskt

644
00:29:57,241 --> 00:29:58,794
retas isär dessa olika steg.

645
00:29:58,794 --> 00:30:00,710
Och faktiskt, i slutet
av dagen, är vi fortfarande

646
00:30:00,710 --> 00:30:04,480
vänster med nollor och ettor, som
är faktiskt ett bra segue nu

647
00:30:04,480 --> 00:30:08,620
till en annan kapacitet C, som
Vi har inte behövt utnyttja troligen

648
00:30:08,620 --> 00:30:11,250
hittills känd som bitvisa operatörer.

649
00:30:11,250 --> 00:30:15,220
Med andra ord, hittills, när vi har
behandlas med data i C eller variabler i C,

650
00:30:15,220 --> 00:30:17,660
vi har haft saker som
tecken och flyter och ins

651
00:30:17,660 --> 00:30:21,990
och längtar och dubblar och liknande, men
alla av dessa är åtminstone åtta bitar.

652
00:30:21,990 --> 00:30:25,550
Vi har aldrig ännu inte kunnat
manipulera enskilda bitar,

653
00:30:25,550 --> 00:30:28,970
även om en individuell bit, vi
vet, kan representera en 0 och en en.

654
00:30:28,970 --> 00:30:32,640
Nu visar det sig att i C, du
kan få tillgång till enskilda bitar,

655
00:30:32,640 --> 00:30:35,530
om du känner till syntaxen,
som man kan komma åt dem.

656
00:30:35,530 --> 00:30:38,010
>> Så låt oss ta en titt
vid bitvisa operatörer.

657
00:30:38,010 --> 00:30:41,700
Så bilden här är några symboler som
vi har, typ av, sorts, sett förut.

658
00:30:41,700 --> 00:30:45,580
Jag ser ett et-tecken, ett vertikalt
bar, och några andra också,

659
00:30:45,580 --> 00:30:49,430
och påminna om att et-et-tecken
är något vi har sett förut.

660
00:30:49,430 --> 00:30:54,060
Den logiska AND, där du har
två av dem tillsammans, eller den logiska ELLER

661
00:30:54,060 --> 00:30:56,300
operatör, där du
har två vertikala streck.

662
00:30:56,300 --> 00:31:00,550
Bitvisa operatörer, som vi kan
se arbeta på bitar individuellt,

663
00:31:00,550 --> 00:31:03,810
bara använda en enda et-tecken, en
enda vertikal bar, cirkumflex symbol

664
00:31:03,810 --> 00:31:06,620
kommer nästa, den lilla
tilde, och sedan vänster

665
00:31:06,620 --> 00:31:08,990
fäste vänster fäste, eller
höger konsol höger konsol.

666
00:31:08,990 --> 00:31:10,770
Var och en av dessa har olika betydelser.

667
00:31:10,770 --> 00:31:11,950
>> I själva verket, låt oss ta en titt.

668
00:31:11,950 --> 00:31:16,560
Låt oss gå old school idag och användning
en pekskärm från förr,

669
00:31:16,560 --> 00:31:18,002
känd som en whiteboard.

670
00:31:18,002 --> 00:31:19,710
Och detta whiteboard
kommer att tillåta oss

671
00:31:19,710 --> 00:31:27,360
att uttrycka några ganska enkla symboler,
eller snarare några ganska enkla formler,

672
00:31:27,360 --> 00:31:29,560
att vi kan sedan slutligen
hävstångseffekt, i syfte

673
00:31:29,560 --> 00:31:33,230
att få tillgång till enskilda
bitar inom ett C-program.

674
00:31:33,230 --> 00:31:34,480
Med andra ord, låt oss göra detta.

675
00:31:34,480 --> 00:31:37,080
Låt oss först tala för en
ögonblick om et-tecken,

676
00:31:37,080 --> 00:31:39,560
vilket är bitvis och operatör.

677
00:31:39,560 --> 00:31:42,130
Med andra ord är detta
en operatör som tillåter

678
00:31:42,130 --> 00:31:45,930
mig att ha en vänster variabel
typiskt, och en höger variabel,

679
00:31:45,930 --> 00:31:50,640
eller ett enskilt värde, att om vi OCH
dem tillsammans, ger mig ett slutresultat.

680
00:31:50,640 --> 00:31:51,560
Så vad menar jag?

681
00:31:51,560 --> 00:31:54,840
Om det i ett program, har du en variabel
som lagrar en av dessa värden,

682
00:31:54,840 --> 00:31:58,000
eller låt oss hålla det enkelt, och bara
skriva ut nollor och ettor individuellt,

683
00:31:58,000 --> 00:32:00,940
här är hur et-operatören arbetar.

684
00:32:00,940 --> 00:32:06,400
0 ampersand 0 kommer att motsvara 0.

685
00:32:06,400 --> 00:32:07,210
Nu varför är det?

686
00:32:07,210 --> 00:32:09,291
>> Det är mycket lik
Booleska uttryck,

687
00:32:09,291 --> 00:32:10,540
att vi har diskuterat hittills.

688
00:32:10,540 --> 00:32:15,800
Om du tror trots allt, 0 är
falskt, 0 är falsk, falsk och falskt

689
00:32:15,800 --> 00:32:18,720
är, som vi har diskuterat
logiskt, också falskt.

690
00:32:18,720 --> 00:32:20,270
Så vi får 0 här.

691
00:32:20,270 --> 00:32:24,390
Om du tar 0-tecken
1, väl det också,

692
00:32:24,390 --> 00:32:29,890
kommer att bli 0, eftersom det för detta
vänster för uttryck att vara sant eller ett,

693
00:32:29,890 --> 00:32:32,360
det skulle behöva vara sant och sant.

694
00:32:32,360 --> 00:32:36,320
Men här har vi falskt
och sann, eller 0 och 1.

695
00:32:36,320 --> 00:32:42,000
Nu igen, om vi har en et-tecken
0, det också, kommer att vara 0,

696
00:32:42,000 --> 00:32:47,240
och om vi har en et-tecken 1,
Slutligen har vi en 1 bit.

697
00:32:47,240 --> 00:32:50,340
Så med andra ord, vi gör inte
något intressant med denna operatör

698
00:32:50,340 --> 00:32:51,850
ännu, denna et-operatör.

699
00:32:51,850 --> 00:32:53,780
Det är bitvis och operatör.

700
00:32:53,780 --> 00:32:57,290
Men dessa är ingredienserna
via vilken vi kan göra

701
00:32:57,290 --> 00:32:59,240
intressanta saker, som vi snart kommer att se.

702
00:32:59,240 --> 00:33:02,790
>> Låt oss nu titta på bara en enda
lodrätt streck över här till höger.

703
00:33:02,790 --> 00:33:06,710
Om jag har en 0 bit och jag
ELLER det med, bitvis

704
00:33:06,710 --> 00:33:11,030
OR operatör, en annan 0 bit,
som kommer att ge mig 0.

705
00:33:11,030 --> 00:33:17,540
Om jag tar en 0 bit och OR det med
1 bit, så jag kommer att få en.

706
00:33:17,540 --> 00:33:19,830
Och i själva verket bara för
klarhet, låt mig gå tillbaka,

707
00:33:19,830 --> 00:33:23,380
så att mina vertikala streck
inte förväxlas med 1: or.

708
00:33:23,380 --> 00:33:26,560
Låt mig skriva alla
min 1 är lite mer

709
00:33:26,560 --> 00:33:32,700
tydligt, så att vi nästa ser, om jag
har en 1 eller 0, som kommer att vara en 1,

710
00:33:32,700 --> 00:33:39,060
och om jag har en 1 eller en som,
Även kommer att bli en 1.

711
00:33:39,060 --> 00:33:42,900
Så du kan se logiskt att de yttersta randområdena
operatör fungerar mycket annorlunda.

712
00:33:42,900 --> 00:33:48,070
Detta ger mig 0 ELLER 0 ger mig 0, men
varannan kombination ger mig en.

713
00:33:48,070 --> 00:33:52,480
Så länge jag har en 1 i
formel, är resultatet kommer att bli en.

714
00:33:52,480 --> 00:33:55,580
>> Till skillnad från OCH
operatör, et-tecknet,

715
00:33:55,580 --> 00:34:00,940
bara om jag har två 1: or i
ekvation, jag faktiskt få en 1.

716
00:34:00,940 --> 00:34:02,850
Nu finns det några andra
operatörer samt.

717
00:34:02,850 --> 00:34:04,810
En av dem är lite mer engagerade.

718
00:34:04,810 --> 00:34:07,980
Så låt mig gå vidare och radera
detta för att frigöra utrymme.

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

720
00:34:13,020 --> 00:34:16,460
Och låt oss ta en titt på
cirkumflex symbol, för bara ett ögonblick.

721
00:34:16,460 --> 00:34:18,210
Detta är typiskt en
tecken kan du skriva

722
00:34:18,210 --> 00:34:21,420
på tangentbordet innehav Skift och
då ett av numren ovanpå din USA

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

724
00:34:22,250 --> 00:34:26,190
>> Så det här är den exklusiva
OR operatör, exklusivt ELLER.

725
00:34:26,190 --> 00:34:27,790
Så vi såg bara operatorn OR.

726
00:34:27,790 --> 00:34:29,348
Detta är den exklusiva OR-opera.

727
00:34:29,348 --> 00:34:30,639
Vad är egentligen skillnaden?

728
00:34:30,639 --> 00:34:34,570
Nåväl låt oss titta bara på formeln
och använda detta som ingredienser i slutändan.

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

730
00:34:37,690 --> 00:34:39,650
Jag kommer att säga är alltid 0.

731
00:34:39,650 --> 00:34:41,400
Det är definitionen av XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 kommer att bli en.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 kommer att vara 1,
och en XOR 1 kommer att bli?

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

735
00:34:59,890 --> 00:35:00,520
Eller höger?

736
00:35:00,520 --> 00:35:01,860
Jag vet inte.

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

738
00:35:02,810 --> 00:35:04,700
Nu vad som händer här?

739
00:35:04,700 --> 00:35:06,630
Väl tänka på
namn på denna operatör.

740
00:35:06,630 --> 00:35:09,980
Exklusiv ELLER, så som den
Namn, Typ av, antyder,

741
00:35:09,980 --> 00:35:13,940
Svaret kommer bara att bli
1 om ingångarna är exklusiva,

742
00:35:13,940 --> 00:35:15,560
uteslutande annorlunda.

743
00:35:15,560 --> 00:35:18,170
Så här ingångarna är
samma, så utsignalen är 0.

744
00:35:18,170 --> 00:35:20,700
Här ingångarna är
samma, så utsignalen är 0.

745
00:35:20,700 --> 00:35:25,640
Här är utgångarna är annorlunda, de
är exklusiva, och så produktionen är ett.

746
00:35:25,640 --> 00:35:28,190
Så det är mycket lik
OCH det är mycket likt,

747
00:35:28,190 --> 00:35:32,760
eller snarare det är mycket lik
OR, men endast i ett exklusivt sätt.

748
00:35:32,760 --> 00:35:36,210
Denna en inte längre är en 1,
eftersom vi har två 1: or,

749
00:35:36,210 --> 00:35:38,621
och inte uteslutande, bara en av dem.

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

751
00:35:39,120 --> 00:35:40,080
Vad händer med de andra?

752
00:35:40,080 --> 00:35:44,220
Väl tilde, under tiden, är
faktiskt trevligt och enkelt, tack och lov.

753
00:35:44,220 --> 00:35:46,410
Och detta är en unär
operatör, vilket innebär

754
00:35:46,410 --> 00:35:50,400
det appliceras på endast en ingång,
en operand, så att säga.

755
00:35:50,400 --> 00:35:51,800
Inte en vänster och en höger.

756
00:35:51,800 --> 00:35:56,050
Med andra ord, om du tar tilde av
0, kommer svaret vara det motsatta.

757
00:35:56,050 --> 00:35:59,710
Och om du tar tilde 1, den
svar kommer det att vara det motsatta.

758
00:35:59,710 --> 00:36:02,570
Så tilde operatören
ett sätt att förneka en bit,

759
00:36:02,570 --> 00:36:06,000
eller vända en bit från
0 till ett, eller en till 0.

760
00:36:06,000 --> 00:36:09,820
>> Och det lämnar oss slutligen
med bara två sista operatörer,

761
00:36:09,820 --> 00:36:13,840
den så kallade vänsterskift, och
s.k. högerskift operatör.

762
00:36:13,840 --> 00:36:16,620
Låt oss ta en titt på hur de arbetet.

763
00:36:16,620 --> 00:36:20,780
Den vänstra skift operatör skrivna
med två fästvinklar som detta,

764
00:36:20,780 --> 00:36:22,110
fungerar på följande sätt.

765
00:36:22,110 --> 00:36:27,390
Om min ingång, eller min operand, till vänster
skift operatör är helt enkelt en 1.

766
00:36:27,390 --> 00:36:33,750
Och jag då tala om för datorn att
vänster skift som en, säger sju platser,

767
00:36:33,750 --> 00:36:37,150
Resultatet är som om jag
ta det ett, och flytta den

768
00:36:37,150 --> 00:36:40,160
sju platser över till
vänster, och som standard,

769
00:36:40,160 --> 00:36:42,270
vi kommer att anta att
utrymmet till höger

770
00:36:42,270 --> 00:36:44,080
kommer att vara stoppade med nollor.

771
00:36:44,080 --> 00:36:50,316
Med andra ord, en vänster skift 7 går
att ge mig att 1, följt av 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Så på ett sätt, och hjälper dig att
ta ett litet antal som 1,

774
00:36:57,380 --> 00:37:00,740
och tydligt gör det mycket
mycket, mycket större på detta sätt,

775
00:37:00,740 --> 00:37:06,460
men vi faktiskt kommer att se
mer smarta metoder för det

776
00:37:06,460 --> 00:37:08,080
i stället, liksom,

777
00:37:08,080 --> 00:37:08,720
>> Okej.

778
00:37:08,720 --> 00:37:10,060
Det var allt för vecka tre.

779
00:37:10,060 --> 00:37:11,400
Vi kommer att se dig nästa gång.

780
00:37:11,400 --> 00:37:12,770
Detta var CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [MUSIK SPELA]

783
00:37:22,243 --> 00:37:25,766
>> TALARE 1: Han var på snack
bar äta en hot fudge fruktglass.

784
00:37:25,766 --> 00:37:28,090
Han hade hela ansiktet.

785
00:37:28,090 --> 00:37:30,506
Han bär den choklad som ett skägg

786
00:37:30,506 --> 00:37:31,756
TALARE 2: Vad gör du?

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

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

789
00:37:33,500 --> 00:37:36,800
>> TALARE 2: Har du bara double dip?

790
00:37:36,800 --> 00:37:38,585
Du doppade dubbla chipet.

791
00:37:38,585 --> 00:37:39,460
TALARE 3: Ursäkta mig.

792
00:37:39,460 --> 00:37:44,440
TALARE 2: Du doppade chip, du
tog en tugga, och du doppade igen.

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

794
00:37:44,940 --> 00:37:48,440
TALARE 2: Så det är som att sätta
hela din mun mitt i dip.

795
00:37:48,440 --> 00:37:52,400
Nästa gång du tar ett chip,
bara doppa det en gång, och avsluta det.

796
00:37:52,400 --> 00:37:53,890
>> TALARE 3: Vet du vad, Dan?

797
00:37:53,890 --> 00:37:58,006
Du doppa det sätt som du vill att doppa.

798
00:37:58,006 --> 00:38:01,900
Jag ska doppa det sätt som jag vill att doppa.

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