1
00:00:00,000 --> 00:00:11,904
>> [Muziek]

2
00:00:11,904 --> 00:00:12,910
>> Hoogleraar: Oké.

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

4
00:00:16,730 --> 00:00:20,230
Dus we zijn hier vandaag niet in Sanders
Theater, in plaats daarvan in Weidner bibliotheek.

5
00:00:20,230 --> 00:00:23,170
De binnenkant van die is een studio
bekend als Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
of zullen we zeggen Studio H, of zal
we say-- als je die grap genoten,

7
00:00:28,310 --> 00:00:30,540
het is eigenlijk uit
klasgenoot, Mark, online,

8
00:00:30,540 --> 00:00:32,420
die zo veel via Twitter voorgesteld.

9
00:00:32,420 --> 00:00:34,270
Nu wat is cool over
dat hier in een studio

10
00:00:34,270 --> 00:00:38,410
is dat ik omringd door deze groene
muren, een groen scherm of chromakey,

11
00:00:38,410 --> 00:00:43,290
zo te zeggen, wat betekent dat CS50's
productie team, buiten het medeweten van mij

12
00:00:43,290 --> 00:00:47,380
nu, zou kunnen zetten
mij het meest overal in de wereld,

13
00:00:47,380 --> 00:00:48,660
in voor-en tegenspoed.

14
00:00:48,660 --> 00:00:51,800
>> Nu wat ons te wachten, probleem stellen
twee is in uw handen voor deze week,

15
00:00:51,800 --> 00:00:53,830
maar met een probleem stellen
drie komende week,

16
00:00:53,830 --> 00:00:56,600
u zal worden uitgedaagd met
de zogenaamde spelletje 15,

17
00:00:56,600 --> 00:00:58,960
een oude partij gunst die
je zou herinneren ontvangen

18
00:00:58,960 --> 00:01:02,030
als een kind dat een hele hoop heeft
nummers die kan schuiven omhoog, omlaag,

19
00:01:02,030 --> 00:01:05,790
links en rechts, en er is een hiaat
binnen de puzzel, waarin u

20
00:01:05,790 --> 00:01:07,840
daadwerkelijk kan schuiven die puzzelstukjes.

21
00:01:07,840 --> 00:01:11,150
Uiteindelijk u deze ontvangen
puzzel in sommige semi willekeurige volgorde,

22
00:01:11,150 --> 00:01:12,940
en het doel is om
sorteren het, van boven naar beneden,

23
00:01:12,940 --> 00:01:16,310
links naar rechts, van de ene
helemaal tot en met 15.

24
00:01:16,310 --> 00:01:19,360
>> Helaas, de implementatie
je hebt bij de hand

25
00:01:19,360 --> 00:01:21,590
gaat software
gebaseerd, niet fysiek.

26
00:01:21,590 --> 00:01:25,280
Je eigenlijk gaat te hebben om te schrijven
code waarmee een student of gebruiker

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

28
00:01:26,760 --> 00:01:29,030
En inderdaad, in de hacker
editie van het spel van 15,

29
00:01:29,030 --> 00:01:32,155
je zult een uitdaging om uit te voeren,
niet alleen het spelen van deze oude school

30
00:01:32,155 --> 00:01:35,010
spel, maar het oplossen
ervan, implementeren god mode,

31
00:01:35,010 --> 00:01:38,280
zogezegd, die eigenlijk
lost het raadsel van de mens,

32
00:01:38,280 --> 00:01:41,080
door hen te voorzien hint,
na hint, hint na.

33
00:01:41,080 --> 00:01:42,280
Zodat meer daarover volgende week.

34
00:01:42,280 --> 00:01:43,720
Maar dat is wat ons te wachten.

35
00:01:43,720 --> 00:01:47,610
>> Voor nu herinneren dat eerder deze week
we hadden deze cliffhanger, als je wil,

36
00:01:47,610 --> 00:01:52,560
waarbij het beste wat we aan het doen waren sortering
verstandig was een bovengrens van grote o n

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

38
00:01:53,210 --> 00:01:56,520
Met andere woorden, bubble sort,
selectie sort, insertion sort,

39
00:01:56,520 --> 00:01:59,120
allemaal, terwijl andere
in de uitvoering ervan,

40
00:01:59,120 --> 00:02:03,480
overgedragen in een n kwadraat running
tijd in het slechtste geval.

41
00:02:03,480 --> 00:02:06,010
En wij over het algemeen aannemen dat
het ergste geval is voor het sorteren

42
00:02:06,010 --> 00:02:08,814
is er een die uw input
helemaal naar achteren.

43
00:02:08,814 --> 00:02:11,980
En inderdaad, het duurde een paar stappen
uitvoering elk van deze algoritmen.

44
00:02:11,980 --> 00:02:15,110
>> Nu aan het einde van de les
recall, vergeleken we bubble sort

45
00:02:15,110 --> 00:02:19,390
tegen selectie sorteren tegen een andere
dat we geroepen merge soort op het moment,

46
00:02:19,390 --> 00:02:22,120
en ik stel voor dat het nemen van
voordeel van een les van week

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

48
00:02:24,060 --> 00:02:28,810
En een of andere manier het bereiken van een soort
logaritmische looptijd uiteindelijk,

49
00:02:28,810 --> 00:02:31,024
in plaats van iets
dat is puur kwadratisch.

50
00:02:31,024 --> 00:02:33,440
En het is niet helemaal logaritmische,
het is een beetje meer dan dat.

51
00:02:33,440 --> 00:02:36,520
Maar als je te herinneren van de klas,
het was veel, veel sneller.

52
00:02:36,520 --> 00:02:38,210
Laten we eens een kijkje nemen op waar we gebleven.

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

54
00:02:41,880 --> 00:02:45,370
>> Bubble sort versus selectie
sort versus merge sort.

55
00:02:45,370 --> 00:02:47,700
Nu zijn ze alle lopende, in
theorie tegelijkertijd.

56
00:02:47,700 --> 00:02:50,510
De CPU draait op dezelfde snelheid.

57
00:02:50,510 --> 00:02:54,990
Maar je kunt voelen hoe saai dit
zeer snel gaat worden,

58
00:02:54,990 --> 00:02:58,790
en hoe snel, toen we injecteren
een beetje van de week nullen algoritmen,

59
00:02:58,790 --> 00:03:00,080
kunnen we sneller dingen.

60
00:03:00,080 --> 00:03:01,630
>> Dus mark soort ziet er geweldig uit.

61
00:03:01,630 --> 00:03:05,220
Hoe kunnen we profiteren van het, met het oog
om nummers sneller afstand.

62
00:03:05,220 --> 00:03:07,140
Nou laten we terugdenken
een ingrediënt dat we

63
00:03:07,140 --> 00:03:10,380
hadden terug in week nul, die van de
op zoek naar iemand in een telefoonboek,

64
00:03:10,380 --> 00:03:12,380
en herinneren eraan dat de
pseudocode die wij voorgesteld,

65
00:03:12,380 --> 00:03:14,560
via welke we kunnen vinden
iemand als Mike Smith,

66
00:03:14,560 --> 00:03:16,310
keek een beetje zoiets als dit.

67
00:03:16,310 --> 00:03:20,820
>> Neem nu een kijkje in het bijzonder
op regel 7 en 8, en 10 en 11,

68
00:03:20,820 --> 00:03:25,240
die deze lus induceren, waarbij we hielden
terug naar lijn 3 gaan opnieuw, en opnieuw,

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

70
00:03:26,520 --> 00:03:31,790
Maar het blijkt dat we kunnen bekijken
Dit algoritme hier in pseudocode,

71
00:03:31,790 --> 00:03:33,620
een beetje meer holistisch.

72
00:03:33,620 --> 00:03:35,960
In feite, wat ik zoek
bij hier op het scherm,

73
00:03:35,960 --> 00:03:41,180
is een algoritme voor het zoeken naar
Mike Smith bij sommige set van pagina's.

74
00:03:41,180 --> 00:03:45,520
En inderdaad, we kunnen dit vereenvoudigen
algoritme die lijnen 7 en 8,

75
00:03:45,520 --> 00:03:49,860
en 10 en 11 om alleen deze te zeggen,
die ik hier in het geel heb gepresenteerd.

76
00:03:49,860 --> 00:03:52,210
Met andere woorden, indien Mike
Smith is eerder in het boek,

77
00:03:52,210 --> 00:03:55,004
we hoeven niet te stap te specificeren
stap nu hoe om te gaan hem te vinden.

78
00:03:55,004 --> 00:03:56,920
We hoeven niet te specificeren
om terug te gaan naar lijn 3,

79
00:03:56,920 --> 00:03:58,960
waarom doen we niet alleen in plaats daarvan,
zeggen, meer algemeen,

80
00:03:58,960 --> 00:04:01,500
zoek Mike in de
linker helft van het boek.

81
00:04:01,500 --> 00:04:03,960
>> Omgekeerd, als Mike is
eigenlijk later in het boek,

82
00:04:03,960 --> 00:04:07,540
waarom doen we niet zomaar citeren unquote zoekopdracht
voor Mike in de rechter helft van het boek.

83
00:04:07,540 --> 00:04:11,030
Met andere woorden, waarom gewoon doen we niet
soort punter om onszelf te zeggen,

84
00:04:11,030 --> 00:04:13,130
zoek Mike in deze
deelverzameling van het boek,

85
00:04:13,130 --> 00:04:16,279
en laat het aan onze bestaande
algoritme om ons te vertellen

86
00:04:16,279 --> 00:04:18,750
hoe om te zoeken naar Mike in
dat de linker helft van het boek.

87
00:04:18,750 --> 00:04:20,750
Met andere woorden, onze
algoritme werkt of het nu

88
00:04:20,750 --> 00:04:24,670
een telefoonboek van deze dikte, van deze
dikte of elke dikte dan ook.

89
00:04:24,670 --> 00:04:27,826
Dus we kunnen recursief
definieert dit algoritme.

90
00:04:27,826 --> 00:04:29,950
Met andere woorden, de
scherm hier, is een algoritme

91
00:04:29,950 --> 00:04:33,130
voor het zoeken naar Mike Smith
tussen de bladzijden van een telefoonboek.

92
00:04:33,130 --> 00:04:37,410
Dus in de lijn 7 en 10, laten we
gewoon zeggen precies dat.

93
00:04:37,410 --> 00:04:40,250
En ik gebruik deze term een ​​moment
geleden, en inderdaad, recursie

94
00:04:40,250 --> 00:04:42,450
is het modewoord voor nu,
en het is dit proces

95
00:04:42,450 --> 00:04:47,210
iets cyclisch te doen door een of andere manier
met behulp van code die je al hebt,

96
00:04:47,210 --> 00:04:49,722
en opnieuw noemde het,
en opnieuw, en opnieuw.

97
00:04:49,722 --> 00:04:51,930
Nu het gaat belangrijk
dat we een of andere manier bottom

98
00:04:51,930 --> 00:04:53,821
uit, en doe dat niet oneindig lang.

99
00:04:53,821 --> 00:04:56,070
Zijn we anders gaan
inderdaad een oneindige lus.

100
00:04:56,070 --> 00:04:59,810
Maar laten we eens kijken of we dit idee kunnen lenen
van een terugkeer, weer iets te doen

101
00:04:59,810 --> 00:05:03,600
en opnieuw en opnieuw, op te lossen
het sorteren probleem via merge

102
00:05:03,600 --> 00:05:05,900
sorteren, des te efficiënter.

103
00:05:05,900 --> 00:05:06,970
>> Dus ik geef u soort samenvoegen.

104
00:05:06,970 --> 00:05:07,920
Laten we kijken.

105
00:05:07,920 --> 00:05:10,850
Dus hier is pseudocode, met
die we kunnen implementeren sorteren

106
00:05:10,850 --> 00:05:12,640
met behulp van dit algoritme genoemd merge soort.

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

108
00:05:13,880 --> 00:05:15,940
Op ingang van n elementen,
met andere woorden, als je

109
00:05:15,940 --> 00:05:18,830
gegeven n elementen en nummers en
letters of wat de ingang,

110
00:05:18,830 --> 00:05:22,430
Als je krijgt n elementen, indien
n kleiner is dan 2, gewoon terug.

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

112
00:05:22,930 --> 00:05:26,430
Want als n kleiner is dan 2, dat
betekent dat mijn lijst van elementen

113
00:05:26,430 --> 00:05:30,446
hetzij van maat 0 of 1, en
in deze beide triviale zaken

114
00:05:30,446 --> 00:05:31,570
de lijst is al opgelost.

115
00:05:31,570 --> 00:05:32,810
Als er geen lijst, is het opgelost.

116
00:05:32,810 --> 00:05:35,185
En als er een lijst van lengte
1, is het natuurlijk opgelost.

117
00:05:35,185 --> 00:05:38,280
Dus het algoritme alleen moet
echt iets interessants te doen,

118
00:05:38,280 --> 00:05:40,870
als we twee of meer
elementen aan ons gegeven.

119
00:05:40,870 --> 00:05:42,440
Dus laten we eens kijken naar de magie dan.

120
00:05:42,440 --> 00:05:47,500
Else sorteren de linkerhelft van de elementen,
vervolgens sorteren van de rechter helft van de elementen,

121
00:05:47,500 --> 00:05:49,640
Vervolgens fuseren de gesorteerde helften.

122
00:05:49,640 --> 00:05:52,440
En wat voor soort geest buigen
hier, is dat ik niet echt

123
00:05:52,440 --> 00:05:56,190
lijken te hebben verteld
alles gewoon nog niet, toch?

124
00:05:56,190 --> 00:05:59,560
Alles wat ik heb gezegd is, krijgt een lijst met
n elementen, sorteren van de linker helft,

125
00:05:59,560 --> 00:06:01,800
dan is de rechter helft, dan
fuseren de gesorteerde helften,

126
00:06:01,800 --> 00:06:03,840
maar waar is de werkelijke geheime saus?

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

128
00:06:05,260 --> 00:06:09,150
Nou, het blijkt dat die twee lijnen
eerste soort linkerhelft elementen,

129
00:06:09,150 --> 00:06:13,970
en een soort rechter helft van de elementen,
zijn recursieve oproepen, om zo te zeggen.

130
00:06:13,970 --> 00:06:16,120
>> Immers, in dit
punt in de tijd, heb ik

131
00:06:16,120 --> 00:06:18,950
een algoritme waarmee
afstand een heleboel elementen?

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

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

134
00:06:20,620 --> 00:06:25,180
Het is hier op het scherm, en
dus ik kan dat dezelfde reeks stappen gebruiken

135
00:06:25,180 --> 00:06:28,500
op de linkerhelft sorteren,
als ik kan de rechter helft.

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

137
00:06:30,420 --> 00:06:34,210
Dus een of andere manier, en we zullen binnenkort
zien, de magie van merge sort

138
00:06:34,210 --> 00:06:37,967
ingebed in die allerlaatste
lijn, het samenvoegen van de gesorteerde helften.

139
00:06:37,967 --> 00:06:39,300
En dat lijkt vrij intuïtief.

140
00:06:39,300 --> 00:06:41,050
Je neemt twee helften, en u,
een of andere manier, voeg ze samen,

141
00:06:41,050 --> 00:06:43,260
en we zullen dit zien
concreet in een moment.

142
00:06:43,260 --> 00:06:45,080
>> Maar dit is een compleet algoritme.

143
00:06:45,080 --> 00:06:46,640
En laten we precies zien waarom.

144
00:06:46,640 --> 00:06:50,912
Nou denk dat we deze zelfde zijn gegeven
acht elementen hier op het scherm, een

145
00:06:50,912 --> 00:06:53,120
door middel van acht, maar ze zijn
in schijnbaar willekeurige volgorde.

146
00:06:53,120 --> 00:06:55,320
En het doel bij de hand is
deze elementen afstand.

147
00:06:55,320 --> 00:06:58,280
Goed hoe kan ik over
doet het gebruik van, wederom,

148
00:06:58,280 --> 00:07:00,407
samenvoegen sorteren, volgens deze pseudocode?

149
00:07:00,407 --> 00:07:02,740
En nogmaals, ingrain deze in
je geest, voor slechts een moment.

150
00:07:02,740 --> 00:07:05,270
Het eerste geval is vrij
triviaal, als het minder dan 2,

151
00:07:05,270 --> 00:07:07,060
gewoon terug, er is geen werk te doen.

152
00:07:07,060 --> 00:07:09,290
Dus eigenlijk is er slechts drie
stappen om echt in gedachten te houden.

153
00:07:09,290 --> 00:07:11,081
Opnieuw, en opnieuw, ik ben
gaat willen hebben

154
00:07:11,081 --> 00:07:13,980
op de linkerhelft sorteren,
sorteren van de rechter helft,

155
00:07:13,980 --> 00:07:15,890
en dan een keer hun
twee helften worden gesorteerd,

156
00:07:15,890 --> 00:07:18,710
Ik wil hen samen te voegen
in een gesorteerde lijst.

157
00:07:18,710 --> 00:07:19,940
Dus hou dat in gedachten.

158
00:07:19,940 --> 00:07:21,310
>> Dus hier is de oorspronkelijke lijst.

159
00:07:21,310 --> 00:07:23,510
Laten we behandelen dit als een
array, zoals we begonnen

160
00:07:23,510 --> 00:07:25,800
in week twee, die een
aaneengesloten blok van het geheugen.

161
00:07:25,800 --> 00:07:28,480
In dit geval bevat acht
getallen, rug aan rug aan rug.

162
00:07:28,480 --> 00:07:30,700
En laten we nu toepassen merge soort.

163
00:07:30,700 --> 00:07:33,300
Dus ik wil eerst sorteren
de linker helft van deze lijst,

164
00:07:33,300 --> 00:07:37,370
en laten we daarom
focus op 4, 8, 6 en 2.

165
00:07:37,370 --> 00:07:41,000
>> Nu hoe ga ik over
sorteren van een lijst van maat 4?

166
00:07:41,000 --> 00:07:45,990
Nou ik moet nu overwegen
sortering links van de linkerhelft.

167
00:07:45,990 --> 00:07:47,720
Nogmaals, laten we terugspoelen voor slechts een moment.

168
00:07:47,720 --> 00:07:51,010
Als de pseudocode is dit,
en ik ben gegeven acht elementen,

169
00:07:51,010 --> 00:07:53,230
8 is uiteraard groter
dan of gelijk aan 2.

170
00:07:53,230 --> 00:07:54,980
Dus met het eerste geval niet van toepassing.

171
00:07:54,980 --> 00:07:58,120
Dus om acht elementen te sorteren, ik voor het eerst
sorteren de linkerhelft van elementen,

172
00:07:58,120 --> 00:08:01,930
dan heb ik afstand de rechter helft, dan samenvoegen I
beide gesorteerde helften, elk van afmeting 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Maar als je me net hebt verteld, sorteren
linkerhelft, die nu van maat 4,

175
00:08:07,480 --> 00:08:09,350
hoe kan ik de linker helft sorteren?

176
00:08:09,350 --> 00:08:11,430
Nou als ik een
ingang van de vier elementen,

177
00:08:11,430 --> 00:08:14,590
Ik voor het eerst te sorteren links
twee, dan is de juiste twee,

178
00:08:14,590 --> 00:08:16,210
en toen ik ze samen te voegen.

179
00:08:16,210 --> 00:08:18,700
Dus nogmaals, het wordt een beetje
van een geest buigen spel hier,

180
00:08:18,700 --> 00:08:21,450
omdat je, soort, moeten
onthouden waar je bent in het verhaal,

181
00:08:21,450 --> 00:08:23,620
maar aan het eind van de dag,
gegeven een aantal elementen,

182
00:08:23,620 --> 00:08:25,620
je eerst wilt sorteren
linkerhelft dan de rechterhelft,

183
00:08:25,620 --> 00:08:26,661
dan voeg ze samen.

184
00:08:26,661 --> 00:08:28,630
Laten we beginnen om precies dat te doen.

185
00:08:28,630 --> 00:08:30,170
Hier is de inbreng van acht elementen.

186
00:08:30,170 --> 00:08:31,910
Nu zijn we op zoek naar de linker helft hier.

187
00:08:31,910 --> 00:08:33,720
Hoe kan ik de afstand vier elementen?

188
00:08:33,720 --> 00:08:35,610
Nou ik voor het eerst afstand de linker helft.

189
00:08:35,610 --> 00:08:37,720
Nu hoe kan ik de linker helft sorteren?

190
00:08:37,720 --> 00:08:39,419
Nou ik heb gekregen twee elementen.

191
00:08:39,419 --> 00:08:41,240
Dus laten sorteren van deze twee elementen.

192
00:08:41,240 --> 00:08:44,540
2 is groter dan of
gelijk aan 2, natuurlijk.

193
00:08:44,540 --> 00:08:46,170
Zodat eerste geval niet geldt.

194
00:08:46,170 --> 00:08:49,010
>> Dus ik moet nu naar links te sorteren
helft van deze twee elementen.

195
00:08:49,010 --> 00:08:50,870
De linkerhelft, is natuurlijk slechts 4.

196
00:08:50,870 --> 00:08:54,020
Dus hoe kan ik een lijst met één element sorteren?

197
00:08:54,020 --> 00:08:57,960
Welnu, die speciale base case
up top, om zo te zeggen, van toepassing.

198
00:08:57,960 --> 00:09:01,470
1 is dan 2, en mijn
lijst is inderdaad van grootte 1.

199
00:09:01,470 --> 00:09:02,747
Dus ik gewoon terug.

200
00:09:02,747 --> 00:09:03,580
Ik doe niets.

201
00:09:03,580 --> 00:09:06,770
En inderdaad, kijk naar wat ik heb
gedaan, wordt 4 al naargelang.

202
00:09:06,770 --> 00:09:09,220
Zoals ik ben al
gedeeltelijk succesvol hier.

203
00:09:09,220 --> 00:09:11,750
>> Nu dat lijkt soort dom
conclusie, maar het is waar.

204
00:09:11,750 --> 00:09:13,700
4 is een lijst van grootte 1.

205
00:09:13,700 --> 00:09:15,090
Het is al opgelost.

206
00:09:15,090 --> 00:09:16,270
Dat is de linker helft.

207
00:09:16,270 --> 00:09:18,010
Nu heb ik afstand de rechter helft.

208
00:09:18,010 --> 00:09:22,310
Mijn ingang is een element, 8
evenzo reeds gesorteerd.

209
00:09:22,310 --> 00:09:25,170
Dom, ook, maar nogmaals,
dit basisprincipe

210
00:09:25,170 --> 00:09:28,310
zal ons in staat stellen om nu te bouwen
op de top van dit succes.

211
00:09:28,310 --> 00:09:32,260
4 naargelang, 8 wordt gesorteerd, nu
Wat was dat laatste stap?

212
00:09:32,260 --> 00:09:35,330
Dus de derde en laatste stap, welke
keer dat je het sorteren van een lijst, recall,

213
00:09:35,330 --> 00:09:38,310
was de twee helften samen te voegen,
links en rechts.

214
00:09:38,310 --> 00:09:39,900
Dus laten we het doen precies dat.

215
00:09:39,900 --> 00:09:41,940
Mijn linkerhelft is natuurlijk 4.

216
00:09:41,940 --> 00:09:43,310
Mijn rechter helft is 8.

217
00:09:43,310 --> 00:09:44,100
>> Dus laten we dit doen.

218
00:09:44,100 --> 00:09:46,410
Eerst Ik ga wijzen
wat extra geheugen,

219
00:09:46,410 --> 00:09:48,680
die ik hier vertegenwoordig,
als slechts een secundaire array,

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

221
00:09:49,660 --> 00:09:52,243
Maar je kunt je voorstellen uitbreiding
dat de rechthoek de gehele lengte,

222
00:09:52,243 --> 00:09:53,290
als we moeten later meer.

223
00:09:53,290 --> 00:09:58,440
Hoe neem ik 4 en 8, en samenvoegen
die twee lijsten van grootte 1 bij elkaar?

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

225
00:10:00,270 --> 00:10:03,300
4 komt eerst, dan komt 8.

226
00:10:03,300 --> 00:10:07,130
Want als ik wil het sorteren
linkerhelft dan de rechterhelft,

227
00:10:07,130 --> 00:10:09,900
en dan samen te voegen die twee helften
samen, in gesorteerde volgorde,

228
00:10:09,900 --> 00:10:11,940
4 komt eerst, dan komt 8.

229
00:10:11,940 --> 00:10:15,810
>> Dus lijken we te zijn om vooruitgang te boeken, zelfs
hoewel ik niet heb gedaan elke eigenlijke werk.

230
00:10:15,810 --> 00:10:17,800
Maar vergeet niet waar we zijn in het verhaal.

231
00:10:17,800 --> 00:10:19,360
We namen oorspronkelijk acht elementen.

232
00:10:19,360 --> 00:10:21,480
We naargelang de linker helft, dat is 4.

233
00:10:21,480 --> 00:10:24,450
Vervolgens gesorteerd we de linkerhelft
van de linkerhelft, die 2 was.

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

235
00:10:25,270 --> 00:10:26,920
We zijn klaar met die stap.

236
00:10:26,920 --> 00:10:29,930
>> Dus als we hebben naargelang de
linker helft van de 2, nu zijn we

237
00:10:29,930 --> 00:10:32,130
moet de rechter helft van 2 afstand.

238
00:10:32,130 --> 00:10:35,710
Dus de rechterhelft van 2 is
deze twee waarden hier, 6 en 2.

239
00:10:35,710 --> 00:10:40,620
Dus laten we nu eens een ingang van de grootte
2, en sorteren van de linker helft, en dan

240
00:10:40,620 --> 00:10:42,610
de rechter helft, en dan
voeg ze samen.

241
00:10:42,610 --> 00:10:45,722
Nou hoe kan ik afstand een lijst van formaat
1, met daarin alleen de nummer 6?

242
00:10:45,722 --> 00:10:46,430
Ik ben al klaar.

243
00:10:46,430 --> 00:10:48,680
Die lijst van maat 1 wordt gesorteerd.

244
00:10:48,680 --> 00:10:52,140
>> Hoe kan ik een andere lijst te sorteren
size 1, de zogenaamde rechterhelft.

245
00:10:52,140 --> 00:10:54,690
Nou, het ook, al naargelang.

246
00:10:54,690 --> 00:10:56,190
De nummer 2 is alleen.

247
00:10:56,190 --> 00:11:00,160
Dus nu heb ik twee helften, links en
rechts, ik moet ze samen te voegen.

248
00:11:00,160 --> 00:11:01,800
Ik geef mezelf wat extra ruimte.

249
00:11:01,800 --> 00:11:05,580
En zet 2 daar,
dan 6 daar, waardoor

250
00:11:05,580 --> 00:11:10,740
sorteren van die lijst, links en rechts,
en het samenvoegen van het samen, uiteindelijk.

251
00:11:10,740 --> 00:11:12,160
Dus ik ben in een iets betere vorm.

252
00:11:12,160 --> 00:11:16,250
Ik ben nog niet klaar, omdat duidelijk 4, 8, 2,
6 is niet de definitieve bestelling die ik wil.

253
00:11:16,250 --> 00:11:20,640
Maar ik heb nu twee lijsten van maat 2, dat
hebben beide respectievelijk gesorteerd.

254
00:11:20,640 --> 00:11:24,580
Dus nu als je terugspoelen in je geest
oog, waar komt die ons verlaten?

255
00:11:24,580 --> 00:11:28,520
Ik ben begonnen met acht elementen, dan heb ik
whittled het neer op de linker helft van 4,

256
00:11:28,520 --> 00:11:31,386
dan is de linkerhelft van 2, en
vervolgens de rechterhelft van 2,

257
00:11:31,386 --> 00:11:34,510
Ik klaar derhalve sorteren van de linker
helft 2, en de rechterhelft van 2,

258
00:11:34,510 --> 00:11:37,800
dus wat is de derde en laatste stap hier?

259
00:11:37,800 --> 00:11:41,290
Ik moet samenvoegen
twee lijsten van maat 2.

260
00:11:41,290 --> 00:11:42,040
Dus laten we gaan vooruit.

261
00:11:42,040 --> 00:11:43,940
En op het scherm hier, geven
me wat extra geheugen,

262
00:11:43,940 --> 00:11:47,170
hoewel technisch gezien, merken dat ik heb
kreeg een heleboel lege ruimte op de top

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

264
00:11:47,670 --> 00:11:50,044
Als ik wil vooral zijn
efficiënte ruimte wijs,

265
00:11:50,044 --> 00:11:52,960
Ik kon gewoon beginnen met het verplaatsen van de elementen
heen en weer, boven en onder.

266
00:11:52,960 --> 00:11:55,460
Maar alleen voor visuele helderheid,
Ik ga het beneden te zetten,

267
00:11:55,460 --> 00:11:56,800
om dingen mooi en schoon te houden.

268
00:11:56,800 --> 00:11:58,150
>> Dus ik heb twee lijsten van maat 2.

269
00:11:58,150 --> 00:11:59,770
De eerste lijst heeft 4 en 8.

270
00:11:59,770 --> 00:12:01,500
De tweede lijst heeft 2 en 6.

271
00:12:01,500 --> 00:12:03,950
Laten we samen te voegen die
samen in gesorteerde volgorde.

272
00:12:03,950 --> 00:12:09,910
2 uiteraard voorop,
dan 4, dan 6, dan 8.

273
00:12:09,910 --> 00:12:12,560
En nu we lijken te krijgen
ergens interessant.

274
00:12:12,560 --> 00:12:15,720
Nu heb ik naargelang de helft van de
lijst, en toevallig, het is

275
00:12:15,720 --> 00:12:18,650
alle even getallen, maar
is inderdaad gewoon een toeval.

276
00:12:18,650 --> 00:12:22,220
En ik nu de linker hebben naargelang
helft, zodat het 2, 4, 6 en 8.

277
00:12:22,220 --> 00:12:23,430
Niets is buiten de orde.

278
00:12:23,430 --> 00:12:24,620
Dat voelt als vooruitgang.

279
00:12:24,620 --> 00:12:26,650
>> Nu voelt het alsof ik heb
praat nu voor altijd,

280
00:12:26,650 --> 00:12:29,850
dus wat valt nog te bezien of dit
algoritme is inderdaad efficiënter.

281
00:12:29,850 --> 00:12:31,766
Maar we gaan door
het super methodisch.

282
00:12:31,766 --> 00:12:34,060
Een computer, natuurlijk
zou doen als dat.

283
00:12:34,060 --> 00:12:34,840
Dus waar zijn we?

284
00:12:34,840 --> 00:12:36,180
We begonnen met acht elementen.

285
00:12:36,180 --> 00:12:37,840
Ik gesorteerd de linkerhelft van 4.

286
00:12:37,840 --> 00:12:39,290
Ik lijken te worden gedaan met dat.

287
00:12:39,290 --> 00:12:42,535
Nu kan de volgende stap
sorteren van de rechter helft van de 4.

288
00:12:42,535 --> 00:12:44,410
En dit deel kunnen we gaan
door een beetje

289
00:12:44,410 --> 00:12:47,140
snel, hoewel je bent
welkom om terug te spoelen of te pauzeren, gewoon

290
00:12:47,140 --> 00:12:49,910
denken over het op
uw eigen tempo, maar wat

291
00:12:49,910 --> 00:12:53,290
We hebben nu een kans om
doen precies hetzelfde algoritme op vier

292
00:12:53,290 --> 00:12:54,380
verschillende nummers.

293
00:12:54,380 --> 00:12:57,740
>> Dus laten we doorgaan, en zich richten op
de rechter helft, die we hier zijn.

294
00:12:57,740 --> 00:13:01,260
De linkerhelft van deze
rechter helft, en nu de

295
00:13:01,260 --> 00:13:04,560
linkerhelft van de linker
de helft van die rechter helft,

296
00:13:04,560 --> 00:13:08,030
en hoe kan ik afstand een lijst van formaat
1 bevat alleen de nummer 1?

297
00:13:08,030 --> 00:13:09,030
Het is al gedaan.

298
00:13:09,030 --> 00:13:11,830
Hoe kan ik hetzelfde voor een lijst te doen
van grootte 1 met slechts 7?

299
00:13:11,830 --> 00:13:12,840
Het is al gedaan.

300
00:13:12,840 --> 00:13:16,790
Stap drie voor deze helft dan
is om deze twee elementen samen te voegen

301
00:13:16,790 --> 00:13:20,889
in een nieuwe lijst van maat 2, 1 en 7.

302
00:13:20,889 --> 00:13:23,180
Lijken niet al te hebben gedaan
dat veel interessant werk.

303
00:13:23,180 --> 00:13:24,346
Laten we eens kijken wat er daarna gebeurt.

304
00:13:24,346 --> 00:13:29,210
Ik naargelang de linker helft van de
rechterhelft van mijn originele inbreng.

305
00:13:29,210 --> 00:13:32,360
Laten we nu de juiste afstand
half, welke 5 en 3 bevat.

306
00:13:32,360 --> 00:13:35,740
Laten we opnieuw kijken naar de linkerzijde
half, gesorteerd, rechter helft, gesorteerd,

307
00:13:35,740 --> 00:13:39,120
en het samenvoegen van deze twee samen,
in een aantal extra ruimte,

308
00:13:39,120 --> 00:13:41,670
3 komt eerst, dan komt 5.

309
00:13:41,670 --> 00:13:46,190
En nu, we hebben naargelang de
linkerhelft van de rechterhelft

310
00:13:46,190 --> 00:13:49,420
van het oorspronkelijke probleem, en
de rechterhelft van de rechterhelft

311
00:13:49,420 --> 00:13:50,800
van het oorspronkelijke probleem.

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

313
00:13:52,480 --> 00:13:54,854
Nou die twee helften samen te voegen.

314
00:13:54,854 --> 00:13:57,020
Dus laat me mezelf nog wat
extra ruimte, maar, nogmaals, ik

315
00:13:57,020 --> 00:13:58,699
zou kunnen zijn het gebruik van die extra ruimte boven.

316
00:13:58,699 --> 00:14:00,490
Maar we gaan houden
het simpel visueel.

317
00:14:00,490 --> 00:14:07,070
Laat me samenvoegen nu 1, en
dan 3, en vervolgens 5 en daarna 7.

318
00:14:07,070 --> 00:14:10,740
Daarbij waardoor ik nu met de
rechterhelft van het oorspronkelijke probleem

319
00:14:10,740 --> 00:14:12,840
dat is perfect opgelost.

320
00:14:12,840 --> 00:14:13,662
>> Dus wat blijft?

321
00:14:13,662 --> 00:14:16,120
Ik voel me alsof ik blijf zeggen dat de
dezelfde dingen opnieuw, en opnieuw,

322
00:14:16,120 --> 00:14:18,700
maar dat is een afspiegeling is van de
feit dat we met behulp van recursie.

323
00:14:18,700 --> 00:14:21,050
Het proces van het gebruik van een
algoritme opnieuw, en opnieuw,

324
00:14:21,050 --> 00:14:23,940
op kleinere subsets van
het oorspronkelijke probleem.

325
00:14:23,940 --> 00:14:27,580
Dus ik heb nu een linker naargelang
de helft van het oorspronkelijke probleem.

326
00:14:27,580 --> 00:14:30,847
Ik heb het recht gesorteerde half
van het oorspronkelijke probleem.

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

328
00:14:32,180 --> 00:14:33,590
Oh, het samenvoegen.

329
00:14:33,590 --> 00:14:34,480
Dus laten we dat doen.

330
00:14:34,480 --> 00:14:36,420
Laten we wijzen een aantal extra
geheugen, maar mijn god, we

331
00:14:36,420 --> 00:14:37,503
kan het overal nu zetten.

332
00:14:37,503 --> 00:14:40,356
We hebben zo veel ruimte beschikbaar
voor ons, maar we zullen het simpel te houden.

333
00:14:40,356 --> 00:14:42,730
In plaats van terug te gaan en
weer met onze oorspronkelijke geheugen,

334
00:14:42,730 --> 00:14:44,480
laten we gewoon doen
visueel neer hieronder,

335
00:14:44,480 --> 00:14:47,240
tot het einde van het samenvoegen van de
linkerhelft en de rechterhelft.

336
00:14:47,240 --> 00:14:49,279
>> Dus door het samenvoegen, wat moet ik doen?

337
00:14:49,279 --> 00:14:50,820
Ik wil de elementen te nemen om.

338
00:14:50,820 --> 00:14:53,230
Dus kijkt naar de linkerhelft,
Ik zie het eerste nummer is 2.

339
00:14:53,230 --> 00:14:55,230
Ik kijk naar de rechter helft,
Ik zie het eerste nummer

340
00:14:55,230 --> 00:14:58,290
1 is dus duidelijk welke
nummer wil ik rukken uit,

341
00:14:58,290 --> 00:15:00,430
en op de eerste plaats in mijn definitieve lijst?

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

343
00:15:01,449 --> 00:15:02,990
Nu wil ik diezelfde vraag.

344
00:15:02,990 --> 00:15:05,040
Op de linkerhelft, ik heb
nog steeds de nummer 2.

345
00:15:05,040 --> 00:15:07,490
Op de rechterhelft,
Ik heb het nummer 3.

346
00:15:07,490 --> 00:15:08,930
Die men wil ik kiezen?

347
00:15:08,930 --> 00:15:11,760
Natuurlijk, nummer 2 en
Nu merkt de kandidaten

348
00:15:11,760 --> 00:15:13,620
zijn 4 links, 3 rechts.

349
00:15:13,620 --> 00:15:15,020
Laten we, natuurlijk, kiezen uit 3.

350
00:15:15,020 --> 00:15:18,020
Nu de kandidaten zijn 4 op
links, 5 rechts.

351
00:15:18,020 --> 00:15:19,460
We natuurlijk kiezen 4.

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

353
00:15:21,240 --> 00:15:22,730
Wij, natuurlijk, kiezen 5.

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

355
00:15:25,020 --> 00:15:29,320
We kiezen voor 6, en toen we
kiezen 7, en dan kiezen we voor 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Dus een groot aantal woorden later, we
deze lijst van acht elementen hebben naargelang

358
00:15:34,370 --> 00:15:38,450
in een lijst van een tot acht,
dat is toeneemt met elke stap,

359
00:15:38,450 --> 00:15:40,850
maar hoeveel tijd deed
het ons om dat te doen.

360
00:15:40,850 --> 00:15:43,190
Nou ik heb bewust
laid dingen uit picturaal

361
00:15:43,190 --> 00:15:46,330
hier, zodat we kunnen soort
zien of te genieten van de divisie

362
00:15:46,330 --> 00:15:49,060
in verovering dat er gebeurt.

363
00:15:49,060 --> 00:15:52,830
>> Inderdaad als je kijkt terug op het spoor,
Ik heb al deze stippellijnen links

364
00:15:52,830 --> 00:15:55,660
in plaats houders, kunt u,
soort, zie, in omgekeerde volgorde,

365
00:15:55,660 --> 00:15:58,800
als je soort terugkijken in
geschiedenis nu, mijn oorspronkelijke lijst

366
00:15:58,800 --> 00:16:00,250
is uiteraard van groot 8.

367
00:16:00,250 --> 00:16:03,480
En dan voorheen, ik was
maken met twee lijsten van maat 4,

368
00:16:03,480 --> 00:16:08,400
en vervolgens vier lijsten van maat 2,
en dan acht lijsten van grootte 1.

369
00:16:08,400 --> 00:16:10,151
>> Dus wat dit doet,
soort, herinneren aan?

370
00:16:10,151 --> 00:16:11,858
Nou, inderdaad, een van
de algoritmes we hebben

371
00:16:11,858 --> 00:16:14,430
bekeken dusver waar we
kloof, en delen, en delen,

372
00:16:14,430 --> 00:16:19,500
houden met de dingen weer, en
weer resulteert in deze gedachte.

373
00:16:19,500 --> 00:16:23,100
En dus is er iets
logaritmische hier aan de hand.

374
00:16:23,100 --> 00:16:26,790
En het is niet helemaal log van n, maar
er is een logaritmische component

375
00:16:26,790 --> 00:16:28,280
met wat we net hebben gedaan.

376
00:16:28,280 --> 00:16:31,570
>> Laten we nu eens kijken hoe dat eigenlijk is.

377
00:16:31,570 --> 00:16:34,481
Dus log n, was weer
een geweldige looptijd,

378
00:16:34,481 --> 00:16:36,980
toen we iets dergelijks
binary search, zoals we nu noemen,

379
00:16:36,980 --> 00:16:40,090
de verdeel en heers strategie
via welke we Mike Smith.

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

381
00:16:41,020 --> 00:16:43,640
Dat is log basis 2 van n, zelfs
hoewel in de meeste wiskunde klassen,

382
00:16:43,640 --> 00:16:45,770
10 is meestal de basis die je aanneemt.

383
00:16:45,770 --> 00:16:48,940
Maar informatici bijna altijd
denken en spreken in termen van de basis 2,

384
00:16:48,940 --> 00:16:52,569
dus we meestal gewoon log van zeggen
n, in plaats van log base 2 van n,

385
00:16:52,569 --> 00:16:55,110
maar ze zijn precies een en
hetzelfde in de wereld van computer

386
00:16:55,110 --> 00:16:57,234
wetenschap, en als een terzijde,
er is een constante factor

387
00:16:57,234 --> 00:17:01,070
verschil tussen de twee, zodat het
moot toch, voor meer formele redenen.

388
00:17:01,070 --> 00:17:04,520
>> Maar voor nu, wat we de zorg
is over dit voorbeeld.

389
00:17:04,520 --> 00:17:08,520
Dus laten we niet bewijzen door bijvoorbeeld, maar op
z'n minst een voorbeeld van de aantallen

390
00:17:08,520 --> 00:17:10,730
bij de hand als een sanity check, als je wil.

391
00:17:10,730 --> 00:17:14,510
Dus eerder de formule was log base
2 van n, maar wat is aangegeven in dit geval.

392
00:17:14,510 --> 00:17:18,526
Ik had n originele nummers, of 8
originele nummer specifiek.

393
00:17:18,526 --> 00:17:20,359
Nu is het een beetje geweest
terwijl, maar ik ben vrij

394
00:17:20,359 --> 00:17:25,300
ervoor dat log basis 2
de waarde 8 is 3,

395
00:17:25,300 --> 00:17:29,630
en inderdaad, wat is er leuk aan is dat
3 dat is precies aantal keren

396
00:17:29,630 --> 00:17:33,320
dat je een lijst kan verdelen
met een lengte van 8 opnieuw, en opnieuw,

397
00:17:33,320 --> 00:17:36,160
en weer, totdat je links bent
met lijsten van slechts 1 formaat.

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

399
00:17:36,660 --> 00:17:40,790
8 gaat naar 4, gaat naar 2,
gaat naar 1, en dat

400
00:17:40,790 --> 00:17:43,470
afspiegeling is van precies dat
foto we hadden net een moment geleden.

401
00:17:43,470 --> 00:17:47,160
Dus een beetje gezond verstand checken waar
de logaritme daadwerkelijk betrokken.

402
00:17:47,160 --> 00:17:50,180
>> Dus nu, wat is hier bij betrokken? n.

403
00:17:50,180 --> 00:17:53,440
Zo merken dat elke
keer ik deelden de lijst,

404
00:17:53,440 --> 00:17:58,260
zij het in omgekeerde volgorde in de geschiedenis
hier, ik was nog steeds n dingen te doen.

405
00:17:58,260 --> 00:18:02,320
Dat samenvoegen stap vereist dat
Ik raak ieder van de nummers,

406
00:18:02,320 --> 00:18:05,060
om het glijden
de juiste locatie.

407
00:18:05,060 --> 00:18:10,760
Dus hoewel de lengte van deze
diagram is van groot log n n of 3,

408
00:18:10,760 --> 00:18:13,860
specifiek, met andere woorden,
Ik heb hier drie divisies.

409
00:18:13,860 --> 00:18:18,800
Hoeveel werk heb ik gedaan horizontaal
langs deze grafiek elke keer?

410
00:18:18,800 --> 00:18:21,110
>> Nou, ik heb n stappen
werken, want als ik heb

411
00:18:21,110 --> 00:18:24,080
kreeg vier elementen en de vier elementen,
en ik moet ze samen te voegen.

412
00:18:24,080 --> 00:18:26,040
Ik moet om te gaan door
deze vier en deze vier,

413
00:18:26,040 --> 00:18:28,123
uiteindelijk om hen te fuseren
back in acht elementen.

414
00:18:28,123 --> 00:18:32,182
Als omgekeerd Ik acht vingers heb
hier, dat doe ik niet, en acht

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Als ik heb
kreeg vier vingers hier,

416
00:18:34,390 --> 00:18:37,380
wat ik doe, vier vingers
hier, wat ik doe,

417
00:18:37,380 --> 00:18:40,590
dan is dat hetzelfde
Bijvoorbeeld als voorheen, als ik dat doe

418
00:18:40,590 --> 00:18:44,010
hebben acht vingers al in
in totaal, wat ik kan, een soort van, doe.

419
00:18:44,010 --> 00:18:47,950
Ik kan precies doen hier,
dan kan ik zeker

420
00:18:47,950 --> 00:18:50,370
samenvoegen van al deze lijsten
van maat 1 samen.

421
00:18:50,370 --> 00:18:54,050
Maar ik hebben zeker kijken
aan elk element precies één keer.

422
00:18:54,050 --> 00:18:59,640
Zodat de hoogte van dit proces is log n,
de breedte van dit proces, zogezegd,

423
00:18:59,640 --> 00:19:02,490
n, dus wat we lijken
om, uiteindelijk, is

424
00:19:02,490 --> 00:19:06,470
een looptijd van grootte n keer log n.

425
00:19:06,470 --> 00:19:08,977
>> Met andere woorden, we verdeeld
de lijst, log n keer,

426
00:19:08,977 --> 00:19:11,810
maar elke keer dat we dat deden, hadden we
aan elk van de elementen te raken

427
00:19:11,810 --> 00:19:13,560
om ze te fuseren
allemaal samen, die

428
00:19:13,560 --> 00:19:18,120
werd n stap, dus we hebben n keer log n,
of als een computer wetenschapper zou zeggen,

429
00:19:18,120 --> 00:19:20,380
asymptotisch die
zou het grote woord

430
00:19:20,380 --> 00:19:22,810
de bovenste beschrijven
gebonden op een looptijd,

431
00:19:22,810 --> 00:19:28,010
We lopen in een grote o
log n tijd, om zo te zeggen.

432
00:19:28,010 --> 00:19:31,510
>> Nu is dit belangrijk, omdat
herinneren wat de looptijden waren

433
00:19:31,510 --> 00:19:34,120
met bel sorteren en selectie
sorteren en insertion sort,

434
00:19:34,120 --> 00:19:38,200
en zelfs een paar anderen die er bestaan,
n kwadraat was waar we waren.

435
00:19:38,200 --> 00:19:39,990
En je kunt, een soort van, zie deze hier.

436
00:19:39,990 --> 00:19:45,720
Als n kwadraat kennelijk n keer
n, maar hier hebben we n keer log n,

437
00:19:45,720 --> 00:19:48,770
en we al kennen van de week
nul, dat log n, de logaritmische,

438
00:19:48,770 --> 00:19:50,550
beter is dan iets lineair.

439
00:19:50,550 --> 00:19:52,930
Immers, herinneren aan de foto
de rode en gele

440
00:19:52,930 --> 00:19:56,500
en de groene lijnen die we trokken, de
groen logaritmische lijn was veel lager.

441
00:19:56,500 --> 00:20:00,920
En daarom, veel beter en sneller
dan de rechte gele en rode lijnen,

442
00:20:00,920 --> 00:20:05,900
n maal log n is inderdaad beter
dan n maal n of n kwadraat.

443
00:20:05,900 --> 00:20:09,110
>> Dus we lijken te hebben
geïdentificeerd een algoritme samenvoegen

444
00:20:09,110 --> 00:20:11,870
soort die in veel loopt
snellere tijd, en inderdaad,

445
00:20:11,870 --> 00:20:16,560
dat is waarom, eerder deze week, toen
zagen we dat de wedstrijd tussen bubble

446
00:20:16,560 --> 00:20:20,750
sorteren, selectie sorteren en samenvoegen
sorteren, samenvoegen soort echt, echt gewonnen.

447
00:20:20,750 --> 00:20:23,660
En inderdaad, we hebben niet eens wachten
voor de bubble sort en selectie sorteren

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

449
00:20:24,790 --> 00:20:27,410
>> Laten we nu eens een ander pas
Dit vanuit een iets

450
00:20:27,410 --> 00:20:31,030
Formeel gezien, alleen in
geval, dit resoneert beter

451
00:20:31,030 --> 00:20:33,380
dan dat hogere niveau discussie.

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

453
00:20:34,880 --> 00:20:36,770
Laten we ons afvragen,
wat de looptijd

454
00:20:36,770 --> 00:20:39,287
is van deze algoritmen verschillende stappen?

455
00:20:39,287 --> 00:20:41,620
Laten verdeel het in de eerste
geval en het tweede geval.

456
00:20:41,620 --> 00:20:46,280
De IF en de andere in het geval als,
Als n kleiner is dan 2, gewoon terug.

457
00:20:46,280 --> 00:20:47,580
Voelt als constante tijd.

458
00:20:47,580 --> 00:20:50,970
Het is, een soort van, zoals twee stappen,
IF n is minder dan 2, dan terug.

459
00:20:50,970 --> 00:20:54,580
Maar zoals we al zeiden op maandag,
constante tijd, of groot o van 1,

460
00:20:54,580 --> 00:20:57,130
kunnen twee stappen, drie
stappen, zelfs 1.000 stappen.

461
00:20:57,130 --> 00:20:59,870
Waar het om gaat is dat het
een constant aantal stappen.

462
00:20:59,870 --> 00:21:03,240
Dus de gele gemarkeerd pseudocode
hier loopt, we noemen het,

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

464
00:21:04,490 --> 00:21:06,780
Dus meer formeel en
we gaan dit to--

465
00:21:06,780 --> 00:21:09,910
de mate waarin we
formaliseren dit recht now-- T van n,

466
00:21:09,910 --> 00:21:15,030
de looptijd van een probleem
dat neemt n plussers als input,

467
00:21:15,030 --> 00:21:19,150
evenaart grote o van één,
Als n kleiner is dan 2.

468
00:21:19,150 --> 00:21:20,640
Dus het is afhankelijk van dat.

469
00:21:20,640 --> 00:21:24,150
Dus om duidelijk te zijn, als n minder dan
2, hebben we een zeer korte lijst, dan

470
00:21:24,150 --> 00:21:29,151
de looptijd, T n, waarbij n
1 of 0, in dit specifieke geval,

471
00:21:29,151 --> 00:21:30,650
het is gewoon een constante tijd.

472
00:21:30,650 --> 00:21:32,691
Het gaat om één te nemen
stap, twee stappen, wat dan ook.

473
00:21:32,691 --> 00:21:33,950
Het is een vast aantal stappen.

474
00:21:33,950 --> 00:21:38,840
>> Zodat de sappige deel moet zeker in
het andere geval in de pseudocode.

475
00:21:38,840 --> 00:21:40,220
De ELSE zaak.

476
00:21:40,220 --> 00:21:44,870
Soort linkerhelft van elementen, een soort recht
de helft van de elementen, samenvoegen gesorteerde helften.

477
00:21:44,870 --> 00:21:46,800
Hoe lang duurt elk van die stappen te ondernemen?

478
00:21:46,800 --> 00:21:49,780
Nou, als de running
tijd om n elementen te sorteren

479
00:21:49,780 --> 00:21:53,010
is, laten we noemen het zeer
algemeen, T n,

480
00:21:53,010 --> 00:21:55,500
sorteert links
de helft van de elementen

481
00:21:55,500 --> 00:21:59,720
is, een soort van, als zeggen,
T n gedeeld door 2,

482
00:21:59,720 --> 00:22:03,000
en op soortgelijke wijze sorteren van de rechterhelft
van de elementen is, een soort van, als zeggen,

483
00:22:03,000 --> 00:22:06,974
T n verdeelde 2, en
samenvoegen van de gesorteerde helften.

484
00:22:06,974 --> 00:22:08,890
Nou als ik heb wat
aantal elementen hier

485
00:22:08,890 --> 00:22:11,230
zoals vier en een getal
elementen hier, net als vier,

486
00:22:11,230 --> 00:22:14,650
Ik moet elk van deze vier samenvoegen
in, en elk van deze vier in één

487
00:22:14,650 --> 00:22:17,160
na elkaar, zodat
Uiteindelijk heb ik acht elementen.

488
00:22:17,160 --> 00:22:20,230
Het voelt alsof dat is grote o n stappen?

489
00:22:20,230 --> 00:22:23,500
Als ik n vingers en elk van hebt
ze moet worden samengevoegd in plaats,

490
00:22:23,500 --> 00:22:25,270
dat is als een andere n stappen.

491
00:22:25,270 --> 00:22:27,360
>> Dus inderdaad formulaically,
kunnen we dit uit te drukken,

492
00:22:27,360 --> 00:22:29,960
zij het een beetje scarily eerst
gezicht, maar het is iets

493
00:22:29,960 --> 00:22:31,600
dat vangt precies die logica.

494
00:22:31,600 --> 00:22:35,710
De looptijd, T n, n IF
groter of gelijk aan 2.

495
00:22:35,710 --> 00:22:42,500
In dit geval is het ELSE geval is T n
gedeeld door 2, plus T n gedeeld door 2,

496
00:22:42,500 --> 00:22:45,320
plus grote o n, sommige
lineaire aantal stappen,

497
00:22:45,320 --> 00:22:51,630
misschien precies n, misschien 2 keer
n, maar het is ruwweg, orde van n.

498
00:22:51,630 --> 00:22:54,060
Dus ook dat is hoe we kunnen
uitdrukken dit formulaically.

499
00:22:54,060 --> 00:22:56,809
Nu zou je dit niet weten, tenzij
je hebt het opgenomen in je geest,

500
00:22:56,809 --> 00:22:58,710
of zoek het op in de
rug van een leerboek, dat

501
00:22:58,710 --> 00:23:00,501
misschien een beetje hebben
cheat sheet op het einde,

502
00:23:00,501 --> 00:23:03,940
maar dit is inderdaad naar
geven ons een grote o n log n,

503
00:23:03,940 --> 00:23:06,620
omdat de herhaling dat
u hier ziet op het scherm,

504
00:23:06,620 --> 00:23:09,550
als je eigenlijk deed het uit, met
een oneindig aantal voorbeelden,

505
00:23:09,550 --> 00:23:13,000
of je het deed formulaically, zou je
zien dat dit, omdat deze formule

506
00:23:13,000 --> 00:23:17,100
zelf recursief met ton
n over iets aan de rechterkant,

507
00:23:17,100 --> 00:23:21,680
en t n op links, kan dit
in feite tot expressie worden gebracht, uiteindelijk,

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

509
00:23:24,339 --> 00:23:26,130
Als er niet van overtuigd, dat is
boete voor nu, net

510
00:23:26,130 --> 00:23:28,960
nemen over geloof, dat dat inderdaad,
wat dat herhaling leidt tot,

511
00:23:28,960 --> 00:23:31,780
maar dit is gewoon een beetje meer van een
wiskundige benadering op zoek

512
00:23:31,780 --> 00:23:36,520
op de looptijd van merge sort
gebaseerd op de pseudocode alleen.

513
00:23:36,520 --> 00:23:39,030
>> Laten we nu eens een beetje een
beluchter van dat alles,

514
00:23:39,030 --> 00:23:41,710
en een kijkje nemen op een
bepaalde voormalige senator, die

515
00:23:41,710 --> 00:23:44,260
ziet er misschien een beetje bekend,
die beneden zat met Google's Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, enige tijd geleden, voor een interview
op het podium, in de voorkant van een heleboel

517
00:23:48,410 --> 00:23:53,710
mensen, praten uiteindelijk over
een onderwerp, dat is vrij nu bekend.

518
00:23:53,710 --> 00:23:54,575
Laten we kijken.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Nu Senator,
je bent hier bij Google,

521
00:24:03,890 --> 00:24:09,490
en ik denk aan de
voorzitterschap als een sollicitatiegesprek.

522
00:24:09,490 --> 00:24:11,712
Nu is het moeilijk om een ​​baan als president krijgen.

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

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: En je bent
nu doen [onverstaanbaar].

525
00:24:13,940 --> 00:24:15,523
Het is ook moeilijk om een ​​baan te krijgen bij Google.

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

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: We hebben vragen,
en we vragen onze kandidaten vragen,

528
00:24:21,330 --> 00:24:24,310
en dit 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
Jullie denken dat ik gek?

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

533
00:24:30,590 --> 00:24:33,490
Wat is de meest efficiënte manier om
sorteren op een miljoen 32 bits gehele getallen?

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

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

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Soms,
misschien ben ik sorry, maybe--

537
00:24:41,020 --> 00:24:42,750
PRESIDENT OBAMA: Nee, nee,
nee, nee, nee, ik think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Dat is niet het--

539
00:24:43,240 --> 00:24:45,430
PRESIDENT OBAMA: I
denk, denk ik dat de zeepbel

540
00:24:45,430 --> 00:24:46,875
soort zou de verkeerde weg 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
Wie heeft hem dit verteld?

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

545
00:24:54,020 --> 00:24:55,590
Ik heb niet de computer science on--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDENT OBAMA: We hebben
kreeg onze spionnen in.

547
00:24:58,986 --> 00:24:59,860
Hoogleraar: Oké.

548
00:24:59,860 --> 00:25:03,370
Laten we achter ons nu de
theoretische wereld van algoritmen

549
00:25:03,370 --> 00:25:06,520
in de asymptotische analyse
daarvan, en terug te keren naar een aantal onderwerpen

550
00:25:06,520 --> 00:25:09,940
vanaf week nul en één, en start
wat zijwieltjes te verwijderen,

551
00:25:09,940 --> 00:25:10,450
als je wil.

552
00:25:10,450 --> 00:25:13,241
Zodat je echt begrijpt
uiteindelijk van de grond af, wat is

553
00:25:13,241 --> 00:25:16,805
gebeurt onder de motorkap, wanneer u
schrijven, compileren en uit te voeren programma's.

554
00:25:16,805 --> 00:25:19,680
Herinneren in het bijzonder, dat dit
de eerste C-programma keken we naar,

555
00:25:19,680 --> 00:25:22,840
een canoniek, eenvoudig programma
van soorten, relatief gezien,

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

557
00:25:24,620 --> 00:25:27,610
En herinner dat ik zei, het proces
dat de broncode gaat door

558
00:25:27,610 --> 00:25:28,430
is precies dit.

559
00:25:28,430 --> 00:25:31,180
U neemt uw broncode, passeren
het door een compiler, zoals Clang,

560
00:25:31,180 --> 00:25:34,650
en komt uit object code, die
kan er zo uitzien, nullen en enen

561
00:25:34,650 --> 00:25:37,880
dat de CPU van de computer, centrale
verwerkingseenheid of de hersenen,

562
00:25:37,880 --> 00:25:39,760
uiteindelijk begrijpt.

563
00:25:39,760 --> 00:25:42,460
>> Het blijkt dat dat is een
beetje een oversimplificatie,

564
00:25:42,460 --> 00:25:44,480
dat we nu in een
positie om elkaar te plagen

565
00:25:44,480 --> 00:25:46,720
om te begrijpen wat er echt geweest
gebeurt onder de motorkap

566
00:25:46,720 --> 00:25:48,600
elke keer dat u
Clang, of meer algemeen,

567
00:25:48,600 --> 00:25:53,040
elke keer dat u een programma te maken,
gebruik maken en CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
In het bijzonder, dat soort dingen
Dit is de eerste gegenereerd,

569
00:25:56,760 --> 00:25:58,684
wanneer u eerst uw programma samenstellen.

570
00:25:58,684 --> 00:26:00,600
Met andere woorden, bij
neem uw broncode

571
00:26:00,600 --> 00:26:04,390
en het compileren, wat is de eerste
wordt afgegeven door Clang

572
00:26:04,390 --> 00:26:06,370
is iets bekend als assemblage-code.

573
00:26:06,370 --> 00:26:08,990
En in feite, het ziet er precies zo.

574
00:26:08,990 --> 00:26:11,170
>> Ik liep een opdracht bij de
command line eerder.

575
00:26:11,170 --> 00:26:16,260
Clang dash hoofdstad s hello.c,
en dit creëerde een bestand

576
00:26:16,260 --> 00:26:19,490
voor mij belde hello.s,
de binnenkant van die precies waren

577
00:26:19,490 --> 00:26:22,290
deze inhoud, en een beetje
boven en iets meer dan,

578
00:26:22,290 --> 00:26:25,080
maar ik heb de sappigste gezet
Informatie hier op het scherm.

579
00:26:25,080 --> 00:26:29,190
En als je goed kijkt, zie je
minstens een paar vertrouwde trefwoorden.

580
00:26:29,190 --> 00:26:31,330
We hebben de belangrijkste bovenaan.

581
00:26:31,330 --> 00:26:35,140
We hebben in het midden printf.

582
00:26:35,140 --> 00:26:38,670
En we hebben ook hello wereld
backslash n aanhalingstekens beneden.

583
00:26:38,670 --> 00:26:42,450
>> En alles wat hier binnen
is instructies zeer laag niveau

584
00:26:42,450 --> 00:26:45,500
dat de CPU van de computer begrijpt.

585
00:26:45,500 --> 00:26:50,090
CPU aanwijzingen dat het geheugen bewegen
rond, dat de lading strijkers uit het geheugen,

586
00:26:50,090 --> 00:26:52,750
en uiteindelijk, print
dingen op het scherm.

587
00:26:52,750 --> 00:26:56,780
Wat gebeurt er als zij na
deze vergadering code wordt gegenereerd?

588
00:26:56,780 --> 00:26:59,964
Uiteindelijk, je doet, inderdaad,
nog steeds het genereren van object code.

589
00:26:59,964 --> 00:27:02,630
Maar de stappen die echt
er aan de hand onder de motorkap

590
00:27:02,630 --> 00:27:04,180
ziet er een beetje meer als dit.

591
00:27:04,180 --> 00:27:08,390
Broncode wordt assemblage-code,
die dan object code,

592
00:27:08,390 --> 00:27:11,930
en de operatieve woorden hier zijn dat,
wanneer u uw broncode te compileren,

593
00:27:11,930 --> 00:27:16,300
komt uit assemblage-code, en vervolgens
wanneer u uw assemblage-code monteren,

594
00:27:16,300 --> 00:27:17,800
buiten komt object code.

595
00:27:17,800 --> 00:27:20,360
>> Nu Clang is super geavanceerde,
als een veel compilers,

596
00:27:20,360 --> 00:27:23,151
en het doet al deze stappen
samen, en het doet niet noodzakelijkerwijs

597
00:27:23,151 --> 00:27:25,360
uitgang enige intermediaire
bestanden die u ook kunt zien.

598
00:27:25,360 --> 00:27:28,400
Het compileert gewoon dingen,
die de algemene term die

599
00:27:28,400 --> 00:27:30,000
beschrijft dit hele proces.

600
00:27:30,000 --> 00:27:32,000
Maar als je echt wilt
bijzonder zijn, er

601
00:27:32,000 --> 00:27:34,330
veel meer aan de hand daar ook.

602
00:27:34,330 --> 00:27:38,860
>> Maar laten we ook rekening houden nu dat zelfs
dat super eenvoudig programma, hello.c,

603
00:27:38,860 --> 00:27:40,540
zogenaamde functie.

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

605
00:27:41,870 --> 00:27:46,900
Maar ik heb niet schrijven printf, inderdaad,
die wordt geleverd met c, bij wijze van spreken.

606
00:27:46,900 --> 00:27:51,139
Het is een functie recall dat is
in standaard io.h, verklaarde die

607
00:27:51,139 --> 00:27:53,180
is een header bestand, dat
is een onderwerp dat we eigenlijk

608
00:27:53,180 --> 00:27:55,780
duiken in meer diepte duurde niet lang.

609
00:27:55,780 --> 00:27:58,000
Maar een header bestand
meestal vergezeld

610
00:27:58,000 --> 00:28:02,920
door een code-bestand, broncode bestand, dus
net zoals er bestaat standaard io.h.

611
00:28:02,920 --> 00:28:05,930
>> Enige tijd geleden iemand,
of iemands, schreef ook

612
00:28:05,930 --> 00:28:11,040
een bestand met de naam standaard io.c, in
die de eigenlijke definities,

613
00:28:11,040 --> 00:28:15,220
of implementaties van printf,
en trossen van andere functies,

614
00:28:15,220 --> 00:28:16,870
daadwerkelijk geschreven.

615
00:28:16,870 --> 00:28:22,140
Dus gezien het feit dat, als we rekening houden met
hier op de linker, hello.c, dat wanneer

616
00:28:22,140 --> 00:28:26,250
gecompileerd geeft ons hello.s, zelfs indien
Clang is niet de moeite te besparen op een plaats

617
00:28:26,250 --> 00:28:31,360
kunnen we het zien, en dat de montage code
wordt samengesteld tot hello.o, waarin

618
00:28:31,360 --> 00:28:34,630
is inderdaad de standaardnaam
gegeven wanneer u de bron te compileren

619
00:28:34,630 --> 00:28:39,350
code in object code, maar zijn niet
helemaal klaar om het nog uit te voeren,

620
00:28:39,350 --> 00:28:41,460
omdat een andere stap
moet gebeuren, en heeft

621
00:28:41,460 --> 00:28:44,440
is gebeurd de afgelopen
weken, misschien buiten het medeweten van u.

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

623
00:28:47,290 --> 00:28:49,870
Ook zal een beetje een te zijn
oversimplificatie voor een moment,

624
00:28:49,870 --> 00:28:54,670
Er is, of was upon a time,
een bestand met de naam standaard io.c,

625
00:28:54,670 --> 00:28:58,440
dat iemand gecompileerd in
standaard io.s of het equivalent,

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

627
00:29:02,010 --> 00:29:04,600
of het blijkt in een
iets ander bestand

628
00:29:04,600 --> 00:29:07,220
formaat dat anders kan hebben
file extensie helemaal,

629
00:29:07,220 --> 00:29:11,720
maar in theorie en conceptueel, precies
die stappen moest gebeuren in een bepaalde vorm.

630
00:29:11,720 --> 00:29:14,060
Dat wil zeggen, dat nu
als ik het schrijven van een programma,

631
00:29:14,060 --> 00:29:17,870
hello.c, die net zegt, hello wereld,
en ik gebruik de code van iemand anders

632
00:29:17,870 --> 00:29:22,480
zoals printf, die once upon a was
tijd, in een bestand met de naam standaard io.c,

633
00:29:22,480 --> 00:29:26,390
dan een of andere manier moet ik mijn nemen
object code, mijn nullen en enen,

634
00:29:26,390 --> 00:29:29,260
en object van die persoon
code, of nullen en enen,

635
00:29:29,260 --> 00:29:34,970
en een of andere manier te koppelen samen in
een laatste bestand, genaamd hello, dat

636
00:29:34,970 --> 00:29:38,070
heeft alle nullen en
degenen van mijn belangrijkste functie,

637
00:29:38,070 --> 00:29:40,830
en alle nullen
en degenen voor printf.

638
00:29:40,830 --> 00:29:44,900
>> En inderdaad, dat laatste proces
genoemd, het koppelen van uw object code.

639
00:29:44,900 --> 00:29:47,490
Waarvan de uitgang
is een uitvoerbaar bestand.

640
00:29:47,490 --> 00:29:49,780
Dus in alle eerlijkheid, op de
Uiteindelijk, niets

641
00:29:49,780 --> 00:29:52,660
veranderd sinds één week, wanneer we
begon het samenstellen van programma's.

642
00:29:52,660 --> 00:29:55,200
Immers, dit alles is
gebeurt onder de motorkap,

643
00:29:55,200 --> 00:29:57,241
maar nu zijn we in een positie
waar we kunnen eigenlijk

644
00:29:57,241 --> 00:29:58,794
plagen elkaar deze verschillende stappen.

645
00:29:58,794 --> 00:30:00,710
En inderdaad, eind
van de dag, we zijn nog steeds

646
00:30:00,710 --> 00:30:04,480
links nullen en enen, die
is eigenlijk een geweldige Segue nu

647
00:30:04,480 --> 00:30:08,620
een ander vermogen van C, die
we niet moesten waarschijnlijk hefboomeffect

648
00:30:08,620 --> 00:30:11,250
tot op heden bekend als bitwise operators.

649
00:30:11,250 --> 00:30:15,220
Met andere woorden, tot nu toe, wanneer hebben we
behandeld data in C of variabelen in C,

650
00:30:15,220 --> 00:30:17,660
we hebben de dingen gehad, zoals
chars en praalwagens en ins

651
00:30:17,660 --> 00:30:21,990
en verlangt en tweepersoonskamers en dergelijke, maar
al die ten minste acht bits.

652
00:30:21,990 --> 00:30:25,550
We hebben nog nooit in staat geweest om
manipuleren individuele bits,

653
00:30:25,550 --> 00:30:28,970
Zelfs wanneer een individu bit, we
weet, kan een 0 en 1 vertegenwoordigen.

654
00:30:28,970 --> 00:30:32,640
Nu blijkt dat in C, u
kan toegang krijgen tot de individuele bits,

655
00:30:32,640 --> 00:30:35,530
Als jij de syntaxis,
waarmee krijgen op hen.

656
00:30:35,530 --> 00:30:38,010
>> Dus laten we eens een kijkje nemen
bij bitwise operators.

657
00:30:38,010 --> 00:30:41,700
Hier dus afgebeeld zijn enkele symbolen die
we hebben, een soort van, soort van, eerder gezien.

658
00:30:41,700 --> 00:30:45,580
Ik zie een ampersand, een verticale
bar, en enkele anderen ook,

659
00:30:45,580 --> 00:30:49,430
en herinneren eraan dat ampersand ampersand
is iets wat we eerder hebben gezien.

660
00:30:49,430 --> 00:30:54,060
De logische operator AND, waar je
twee te zamen, of de logische OR

661
00:30:54,060 --> 00:30:56,300
operator, waar u
hebben twee verticale balken.

662
00:30:56,300 --> 00:31:00,550
Bitwise operators, die we zullen
Zie werken op stukjes individueel,

663
00:31:00,550 --> 00:31:03,810
gewoon gebruik maken van een enkel teken, een
enkele verticale balk, het dakje symbool

664
00:31:03,810 --> 00:31:06,620
daarna komt, de kleine
tilde, en dan links

665
00:31:06,620 --> 00:31:08,990
beugel links beugel of
rechts beugel rechts beugel.

666
00:31:08,990 --> 00:31:10,770
Elk van deze verschillende betekenissen.

667
00:31:10,770 --> 00:31:11,950
>> In feite, laten we eens een kijkje nemen.

668
00:31:11,950 --> 00:31:16,560
Laten we gaan oude school vandaag, en het gebruik
een touch screen van weleer,

669
00:31:16,560 --> 00:31:18,002
bekend als een wit bord.

670
00:31:18,002 --> 00:31:19,710
En deze witte boord
zal ons in staat stellen

671
00:31:19,710 --> 00:31:27,360
sommige vrij eenvoudige symbolen uit te drukken,
of liever een aantal vrij eenvoudige formules,

672
00:31:27,360 --> 00:31:29,560
dat we kunnen dan uiteindelijk
leverage, teneinde

673
00:31:29,560 --> 00:31:33,230
om individuele
bits binnen een C programma.

674
00:31:33,230 --> 00:31:34,480
Met andere woorden, laten we dit doen.

675
00:31:34,480 --> 00:31:37,080
Laten we het eerste gesprek voor een
ogenblik over ampersand,

676
00:31:37,080 --> 00:31:39,560
dat is de bitsgewijze operator.

677
00:31:39,560 --> 00:31:42,130
Met andere woorden, dit
een operator die het mogelijk maakt

678
00:31:42,130 --> 00:31:45,930
me naar een linker variabele hebben
typisch, en een rechtse variabele,

679
00:31:45,930 --> 00:31:50,640
of een individuele waarde, dat als we EN
ze samen, geeft me een eindresultaat.

680
00:31:50,640 --> 00:31:51,560
Dus wat ik bedoel?

681
00:31:51,560 --> 00:31:54,840
Als in een programma, heb je een variabele
dat voorraden een van deze waarden,

682
00:31:54,840 --> 00:31:58,000
of laten we het simpel houden, en gewoon
schrijf uit nullen en enen individueel,

683
00:31:58,000 --> 00:32:00,940
hier is hoe de ampersand operator werkt.

684
00:32:00,940 --> 00:32:06,400
0 ampersand 0 gaat gelijk 0.

685
00:32:06,400 --> 00:32:07,210
Waarom is dat?

686
00:32:07,210 --> 00:32:09,291
>> Het is vergelijkbaar met
Boolean expressies,

687
00:32:09,291 --> 00:32:10,540
dat we tot nu toe hebben besproken.

688
00:32:10,540 --> 00:32:15,800
Als je denkt dat immers de 0 is
vals, 0 is vals, onjuist en onwaar

689
00:32:15,800 --> 00:32:18,720
is, zoals we hebben besproken
logisch, ook vals.

690
00:32:18,720 --> 00:32:20,270
Dus krijgen we 0 hier ook.

691
00:32:20,270 --> 00:32:24,390
Als je 0 ampersand nemen
1, goed dat, ook,

692
00:32:24,390 --> 00:32:29,890
gaat worden 0, omdat bij dit
linker expressie waar of 1 zijn,

693
00:32:29,890 --> 00:32:32,360
het zou moeten waar en waar te zijn.

694
00:32:32,360 --> 00:32:36,320
Maar hier hebben we vals
en waar, of 0 en 1.

695
00:32:36,320 --> 00:32:42,000
Nu weer, als we 1 ampersand
0, dat ook zal worden 0,

696
00:32:42,000 --> 00:32:47,240
en als we 1 ampersand 1,
eindelijk hebben we een 1 bit.

697
00:32:47,240 --> 00:32:50,340
Dus met andere woorden, we zijn niet te doen
iets interessants met deze operator

698
00:32:50,340 --> 00:32:51,850
gewoon nog niet, dit ampersand operator.

699
00:32:51,850 --> 00:32:53,780
Het is de bitsgewijze operator AND.

700
00:32:53,780 --> 00:32:57,290
Maar dit zijn de ingrediënten
via welke we kunnen doen

701
00:32:57,290 --> 00:32:59,240
interessante dingen, zoals we snel zullen zien.

702
00:32:59,240 --> 00:33:02,790
>> Laten we nu eens kijken naar alleen de enkelvoudige
verticale balk hier aan de rechterkant.

703
00:33:02,790 --> 00:33:06,710
Als ik een 0-bit en ik
OR met de bitsgewijze

704
00:33:06,710 --> 00:33:11,030
OR operator, een 0 bit,
dat gaat mij 0.

705
00:33:11,030 --> 00:33:17,540
Als ik een 0-bit en OR met
een 1-bit, dan ga ik om 1.

706
00:33:17,540 --> 00:33:19,830
En inderdaad, voor
duidelijkheid, laat me terug te gaan,

707
00:33:19,830 --> 00:33:23,380
zodat mijn verticale balken
zijn niet vergis voor 1's.

708
00:33:23,380 --> 00:33:26,560
Laat me al te herschrijven
mijn 1 is een beetje meer

709
00:33:26,560 --> 00:33:32,700
duidelijk, zodat we volgend zien, als ik
hebben een 1 of 0, dat gaat een 1 te zijn,

710
00:33:32,700 --> 00:33:39,060
en als ik een 1 of 1 dat,
Ook zal een 1 zijn.

711
00:33:39,060 --> 00:33:42,900
Dus je kunt logisch zien dat de OR
exploitant gedraagt ​​zich heel anders.

712
00:33:42,900 --> 00:33:48,070
Dit geeft me 0 OF 0 geeft me 0, maar
elke andere combinatie geeft me 1.

713
00:33:48,070 --> 00:33:52,480
Zolang ik heb een 1 in de
formule, wordt het resultaat zal zijn 1.

714
00:33:52,480 --> 00:33:55,580
>> Anders dan de AND
exploitant, de ampersand,

715
00:33:55,580 --> 00:34:00,940
alleen als ik twee 1 in de
vergelijking, heb ik eigenlijk een 1 op.

716
00:34:00,940 --> 00:34:02,850
Nu is er een paar andere
exploitanten ook.

717
00:34:02,850 --> 00:34:04,810
Een van hen is een beetje meer betrokken.

718
00:34:04,810 --> 00:34:07,980
Dus laat me gaan en te wissen
Dit om ruimte vrij te maken.

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

720
00:34:13,020 --> 00:34:16,460
En laten we eens een kijkje op de
dakje symbool, voor slechts een moment.

721
00:34:16,460 --> 00:34:18,210
Dit is typisch een
teken dat u kunt typen

722
00:34:18,210 --> 00:34:21,420
op uw toetsenbord bedrijf Shift en
dan is een van de nummers boven op uw VS

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

724
00:34:22,250 --> 00:34:26,190
>> Dus dit is de exclusieve
OR operator, exclusieve OR.

725
00:34:26,190 --> 00:34:27,790
Dus we zagen de OR operator.

726
00:34:27,790 --> 00:34:29,348
Dit is de exclusieve operator OR.

727
00:34:29,348 --> 00:34:30,639
Wat is eigenlijk het verschil?

728
00:34:30,639 --> 00:34:34,570
Nou laten we gewoon kijken naar de formule,
en gebruik dit als ingrediënten uiteindelijk.

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

730
00:34:37,690 --> 00:34:39,650
Ik ga zeggen is altijd 0.

731
00:34:39,650 --> 00:34:41,400
Dat is de omschrijving van de XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 gaat worden 1.

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

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

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

736
00:35:00,520 --> 00:35:01,860
Ik weet het niet.

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

738
00:35:02,810 --> 00:35:04,700
Nu, wat is hier aan de hand?

739
00:35:04,700 --> 00:35:06,630
Goed na te denken over de
De naam van deze operator.

740
00:35:06,630 --> 00:35:09,980
Exclusive OR, teneinde de
naam, soort van, al doet vermoeden,

741
00:35:09,980 --> 00:35:13,940
het antwoord is alleen maar om te zijn
een 1 als de ingangen zijn exclusief,

742
00:35:13,940 --> 00:35:15,560
exclusief verschillend.

743
00:35:15,560 --> 00:35:18,170
Dus hier de ingangen zijn de
hetzelfde, zodat de uitgang 0.

744
00:35:18,170 --> 00:35:20,700
Hier zijn de ingangen van de
hetzelfde, zodat de uitgang 0.

745
00:35:20,700 --> 00:35:25,640
Hier zijn de uitgangen verschillend, zij
exclusief, en dus is de output 1.

746
00:35:25,640 --> 00:35:28,190
Dus het is zeer vergelijkbaar met
En, het is zeer vergelijkbaar zijn,

747
00:35:28,190 --> 00:35:32,760
of liever is vergelijkbaar met
OR, maar alleen op een exclusieve wijze.

748
00:35:32,760 --> 00:35:36,210
Dit is niet langer een 1,
want we hebben twee 1's,

749
00:35:36,210 --> 00:35:38,621
en niet uitsluitend één van hen.

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

751
00:35:39,120 --> 00:35:40,080
Hoe zit het met de anderen?

752
00:35:40,080 --> 00:35:44,220
Nou, de tilde, ondertussen, is
eigenlijk leuk en eenvoudig, gelukkig.

753
00:35:44,220 --> 00:35:46,410
En dit is een unary
operator, waardoor

754
00:35:46,410 --> 00:35:50,400
het wordt toegevoerd aan één ingang,
één operand, om zo te zeggen.

755
00:35:50,400 --> 00:35:51,800
Niet een linker en een rechter.

756
00:35:51,800 --> 00:35:56,050
Met andere woorden, als je tilde van nemen
0, zal het antwoord het tegenovergestelde.

757
00:35:56,050 --> 00:35:59,710
En als je rekening tilde van 1, de
antwoord er het tegenovergestelde zal zijn.

758
00:35:59,710 --> 00:36:02,570
Dus de tilde exploitant
een manier van ontkenning van een beetje,

759
00:36:02,570 --> 00:36:06,000
of flipping een beetje uit
0-1 of 1-0.

760
00:36:06,000 --> 00:36:09,820
>> En dat laat ons eindelijk
met slechts twee laatste exploitanten,

761
00:36:09,820 --> 00:36:13,840
de zogenaamde linkse shift, en
zogenaamde rechter shift operator.

762
00:36:13,840 --> 00:36:16,620
Laten we eens kijken naar hoe die werken.

763
00:36:16,620 --> 00:36:20,780
De linker shift operator, geschreven
met twee punthaken als dat,

764
00:36:20,780 --> 00:36:22,110
werkt als volgt.

765
00:36:22,110 --> 00:36:27,390
Indien mijn inbreng of mijn operand, links
shift exploitant is gewoon een 1.

766
00:36:27,390 --> 00:36:33,750
En ik dan vertellen dat de computer
linker verschuiving die 1, zeggen zeven plaatsen,

767
00:36:33,750 --> 00:36:37,150
het resultaat is alsof ik
neem dat 1 en verplaatsen

768
00:36:37,150 --> 00:36:40,160
zeven plaatsen naar de
links, en door gebrek,

769
00:36:40,160 --> 00:36:42,270
We gaan ervan uit dat
de ruimte aan de rechterkant

770
00:36:42,270 --> 00:36:44,080
zal worden opgevuld met nullen.

771
00:36:44,080 --> 00:36:50,316
Met andere woorden, 1 links verplaatsen 7 gaat
om me dat 1, gevolgd door 1, 2, 3,

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

773
00:36:54,060 --> 00:36:57,380
Dus in zekere zin, het laat je
neem een ​​klein aantal, zoals 1,

774
00:36:57,380 --> 00:37:00,740
en duidelijk maakt het veel
veel, veel groter in deze manier

775
00:37:00,740 --> 00:37:06,460
maar we eigenlijk gaan zien
slimmer benaderingen voor haar

776
00:37:06,460 --> 00:37:08,080
in plaats daarvan ook,

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

778
00:37:08,720 --> 00:37:10,060
Dat is het voor week drie.

779
00:37:10,060 --> 00:37:11,400
Wij zullen u de 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
>> [Muziek]

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1: Hij was bij de snack
bar eten van een hete fudge ijscoupe.

784
00:37:25,766 --> 00:37:28,090
Hij had het allemaal over zijn gezicht.

785
00:37:28,090 --> 00:37:30,506
Hij draagt ​​dat chocolade als een baard

786
00:37:30,506 --> 00:37:31,756
Luidspreker 2: Wat doe je?

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

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

789
00:37:33,500 --> 00:37:36,800
>> Luidspreker 2: Heb je net double dip?

790
00:37:36,800 --> 00:37:38,585
U doopte het dubbele van de chip.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: Neem me niet kwalijk.

792
00:37:39,460 --> 00:37:44,440
Luidspreker 2: U gedoopt de chip, u
nam een ​​hap, en je weer gedompeld.

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

794
00:37:44,940 --> 00:37:48,440
Luidspreker 2: Dus dat is als het zetten
je hele mond in het dip.

795
00:37:48,440 --> 00:37:52,400
Volgende keer dat je een chip te nemen,
maar doopt het een keer, en eindig.

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

797
00:37:53,890 --> 00:37:58,006
Je doopt de manier waarop u wilt onderdompelen.

798
00:37:58,006 --> 00:38:01,900
Ik zal de manier waarop ik wil dip dip.

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