1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Muziek]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Oke.

4
00:00:13,500 --> 00:00:14,670
Oke, welkom terug.

5
00:00:14,670 --> 00:00:18,120
Dus dit is Week 4, het begin
daarvan, reeds.

6
00:00:18,120 --> 00:00:21,320
En je zult zien dat vorige week herinneren, we zetten
coderen gereserveerd voor slechts een klein beetje

7
00:00:21,320 --> 00:00:24,240
en we begonnen te praten een beetje meer
hoog niveau, over zaken als

8
00:00:24,240 --> 00:00:28,130
zoeken en sorteren, die, hoewel
ietwat simpele ideeën, zijn

9
00:00:28,130 --> 00:00:31,840
vertegenwoordiger van een categorie problemen
je zult beginnen te bijzonder lossen

10
00:00:31,840 --> 00:00:34,820
als je begint te denken over het uiteindelijke
projecten en interessante oplossingen die u

11
00:00:34,820 --> 00:00:36,760
zou kunnen hebben om echte problemen.

12
00:00:36,760 --> 00:00:39,490
Nu bubble sort was een van de eenvoudigste
dergelijke algoritmen, en

13
00:00:39,490 --> 00:00:42,900
gewerkt door het hebben van deze kleine aantallen
in een lijst of in een array soort

14
00:00:42,900 --> 00:00:46,530
bubble hun weg naar de top, en de
grote aantallen bewegen hun weg naar

15
00:00:46,530 --> 00:00:47,930
het einde van die lijst.

16
00:00:47,930 --> 00:00:50,650
>> En herinner me dat we konden visualiseren
bubble sort een beetje

17
00:00:50,650 --> 00:00:52,310
zoiets als dit.

18
00:00:52,310 --> 00:00:53,640
Dus laat me ga je gang en klik op Start.

19
00:00:53,640 --> 00:00:55,350
Ik heb bubble sort voorgeselecteerd.

20
00:00:55,350 --> 00:00:58,920
En als u zich herinneren dat het langer blauw
lijnen stellen grote aantallen, kleine

21
00:00:58,920 --> 00:01:03,300
blauwe lijnen geven kleine aantallen, zoals
we gaan door dit opnieuw en opnieuw en

22
00:01:03,300 --> 00:01:07,680
opnieuw vergelijken van twee staven naast elkaar
andere in rood, gaan we de swap

23
00:01:07,680 --> 00:01:11,010
grootste en de kleinste indien
ze zijn niet in orde.

24
00:01:11,010 --> 00:01:14,150
>> Dus dit zal gaan en gaan en gaan
op, en je zult zien dat het voor een uitvergroting

25
00:01:14,150 --> 00:01:16,700
elementen maken hun weg naar de
rechts, en de kleinere elementen zijn

26
00:01:16,700 --> 00:01:17,900
maken hun weg naar links.

27
00:01:17,900 --> 00:01:21,380
Maar we begonnen te kwantificeren
efficiëntere,

28
00:01:21,380 --> 00:01:22,970
kwaliteit van dit algoritme.

29
00:01:22,970 --> 00:01:25,200
En we zeiden dat in het ergste
geval dit algoritme nam

30
00:01:25,200 --> 00:01:27,940
ruwweg hoeveel stappen?

31
00:01:27,940 --> 00:01:28,980
>> Zo n kwadraat.

32
00:01:28,980 --> 00:01:30,402
En wat was n?

33
00:01:30,402 --> 00:01:31,650
>> PUBLIEK: Aantal elementen.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Zo n was de
aantal elementen.

35
00:01:32,790 --> 00:01:33,730
En dus zullen we dit vaak.

36
00:01:33,730 --> 00:01:36,650
Elke keer als we willen praten over de grootte
van een probleem of de grootte van een

37
00:01:36,650 --> 00:01:39,140
ingang of de hoeveelheid tijd die het kost
om output te produceren, zullen we gewoon

38
00:01:39,140 --> 00:01:41,610
gegeneraliseerde wat
de ingang is zo n.

39
00:01:41,610 --> 00:01:45,970
Dus terug in week 0, het aantal pagina's
in het telefoonboek was n.

40
00:01:45,970 --> 00:01:47,550
Het aantal studenten
in de kamer was n.

41
00:01:47,550 --> 00:01:49,630
Dus ook hier, we volgen
dat patroon.

42
00:01:49,630 --> 00:01:52,800
>> Nu n kwadraat is niet bijzonder
snel, dus we probeerden het beter te doen.

43
00:01:52,800 --> 00:01:55,970
En dus hebben we gekeken naar een paar
andere algoritmen, waaronder

44
00:01:55,970 --> 00:01:57,690
waren selectie sorteren.

45
00:01:57,690 --> 00:01:59,180
Dus selectie sorteren was
een beetje anders.

46
00:01:59,180 --> 00:02:03,130
Het was bijna eenvoudiger, ik durf te zeggen,
waarbij ik begon aan het begin van de

47
00:02:03,130 --> 00:02:06,740
overzicht van onze vrijwilligers en ik gewoon weer
en opnieuw en opnieuw ging door

48
00:02:06,740 --> 00:02:10,060
de lijst, plukken uit de kleinste
element in een tijd en zetten hem of

49
00:02:10,060 --> 00:02:13,040
haar aan het begin van de lijst.

50
00:02:13,040 --> 00:02:16,410
>> Maar ook dit keer begonnen we te denken
door de wiskunde en groter

51
00:02:16,410 --> 00:02:19,860
beeld, dacht na over hoe vaak
Ik werd heen en weer en weer terug

52
00:02:19,860 --> 00:02:24,090
en weer, we zeiden in het ergste geval,
selectie sorteren was ook wat?

53
00:02:24,090 --> 00:02:24,960
n kwadraat.

54
00:02:24,960 --> 00:02:27,490
Nu in de echte wereld, is het misschien
eigenlijk marginaal sneller.

55
00:02:27,490 --> 00:02:30,620
Want nogmaals, ik heb niet moeten blijven
backtracking zodra ik had naargelang de

56
00:02:30,620 --> 00:02:31,880
kleinste elementen.

57
00:02:31,880 --> 00:02:35,090
Maar als we denken aan zeer grote n, en
als je soort te doen uit de wiskunde als

58
00:02:35,090 --> 00:02:39,170
Ik heb op het bord, met de n kwadraat
minus iets, alles anders

59
00:02:39,170 --> 00:02:41,850
Naast de n kwadraat, zodra n
wordt echt groot, niet

60
00:02:41,850 --> 00:02:42,850
echt zo veel uit.

61
00:02:42,850 --> 00:02:45,470
Dus als informatici, we soort van
oogluikend naar de kleinere

62
00:02:45,470 --> 00:02:49,220
factoren en aandacht alleen op de factor
een uitdrukking die gaat om

63
00:02:49,220 --> 00:02:50,330
het grootste verschil.

64
00:02:50,330 --> 00:02:52,840
>> Nou, ten slotte, hebben we gekeken
bij insertion sort.

65
00:02:52,840 --> 00:02:56,620
En dit was in dezelfde geest, maar
in plaats van te gaan door iteratief en

66
00:02:56,620 --> 00:03:01,250
selecteer het kleinste element een voor een
tijd, in plaats daarvan nam ik de hand die ik

67
00:03:01,250 --> 00:03:04,070
werd behandeld, en ik besloot, alle
rechts, je hoort hier.

68
00:03:04,070 --> 00:03:06,160
Daarna verhuisde ik naar het volgende element
en besloot dat hij of

69
00:03:06,160 --> 00:03:07,470
Ze behoorde hier.

70
00:03:07,470 --> 00:03:08,810
En toen bewoog ik op en op.

71
00:03:08,810 --> 00:03:11,780
En ik zou aan, langs de weg,
verschuiven deze jongens om

72
00:03:11,780 --> 00:03:13,030
maak ruimte voor hen.

73
00:03:13,030 --> 00:03:16,880
Dus dat was een soort van de mentale ommekeer
van selectie soort dat we

74
00:03:16,880 --> 00:03:18,630
riep insertion sort.

75
00:03:18,630 --> 00:03:20,810
>> Dus deze onderwerpen voor te komen
in de echte wereld.

76
00:03:20,810 --> 00:03:23,640
Gewoon een paar jaar geleden, toen een zekere
senator voor voorzitter liep,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, op het moment dat de CEO van
Google, in feite de gelegenheid gehad

78
00:03:27,160 --> 00:03:28,040
om hem te interviewen.

79
00:03:28,040 --> 00:03:32,010
En we dachten dat we zouden dit YouTube delen
clip voor u hier, als we zouden kunnen opduiken

80
00:03:32,010 --> 00:03:32,950
het volume.

81
00:03:32,950 --> 00:03:39,360
>> [VIDEO AFSPELEN]

82
00:03:39,360 --> 00:03:44,620
>> -Nu, Senator, je bent hier bij Google,
en ik denk graag dat het voorzitterschap

83
00:03:44,620 --> 00:03:46,042
als een sollicitatiegesprek.

84
00:03:46,042 --> 00:03:47,770
>> [Lachen]

85
00:03:47,770 --> 00:03:50,800
>> -Nu is het moeilijk te krijgen
een baan als president.

86
00:03:50,800 --> 00:03:52,480
En je gaat door
de ontberingen nu.

87
00:03:52,480 --> 00:03:54,330
Het is ook moeilijk om een ​​baan bij Google te krijgen.

88
00:03:54,330 --> 00:03:59,610
Wij hebben vragen en wij vragen
onze kandidaten vragen.

89
00:03:59,610 --> 00:04:02,250
En deze is van Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Lachen]

91
00:04:05,325 --> 00:04:06,400
-Jullie denken dat ik een grapje maak?

92
00:04:06,400 --> 00:04:08,750
Het is hier.

93
00:04:08,750 --> 00:04:12,110
Wat is de meest efficiënte manier om
sorteren een miljoen twee-bits gehele getallen?

94
00:04:12,110 --> 00:04:15,810
>> [Lachen]

95
00:04:15,810 --> 00:04:18,260
>> -Nou, uh -

96
00:04:18,260 --> 00:04:19,029
>> Het spijt me.

97
00:04:19,029 --> 00:04:19,745
Misschien moeten we -

98
00:04:19,745 --> 00:04:21,000
>> -Nee, nee, nee, nee, nee.

99
00:04:21,000 --> 00:04:21,470
>> -Dat is niet een -

100
00:04:21,470 --> 00:04:22,185
OK.

101
00:04:22,185 --> 00:04:25,328
>> -Ik denk dat de bubble sort zou
zijn de verkeerde weg te gaan.

102
00:04:25,328 --> 00:04:26,792
>> [Lachen]

103
00:04:26,792 --> 00:04:28,510
>> [Gejuich en applaus]

104
00:04:28,510 --> 00:04:31,211
>> -Kom op, die hem dit verteld?

105
00:04:31,211 --> 00:04:32,155
OK.

106
00:04:32,155 --> 00:04:33,350
>> [END VIDEO AFSPELEN]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Dus daar heb je het.

108
00:04:35,070 --> 00:04:39,600
Dus we begonnen te kwantificeren deze bedrijfskosten
tijden, om zo te zeggen, met iets

109
00:04:39,600 --> 00:04:43,480
genoemd asymptotische notatie, hetgeen
alleen over onze soort te draaien

110
00:04:43,480 --> 00:04:47,420
een oogje op die kleinere factoren en
alleen kijken naar de looptijd,

111
00:04:47,420 --> 00:04:51,250
de uitvoering van deze algoritmen,
zo n krijgt echt grote tijd.

112
00:04:51,250 --> 00:04:55,110
En dus hebben we geïntroduceerd grote O. En big O
vertegenwoordigd iets dat we dachten

113
00:04:55,110 --> 00:04:57,000
van als een bovengrens.

114
00:04:57,000 --> 00:04:59,570
En eigenlijk, Barry, kunnen we verlagen
dan de microfoon een beetje?

115
00:04:59,570 --> 00:05:01,040
>> We dachten dat dit is een bovengrens.

116
00:05:01,040 --> 00:05:04,710
Zo groot O van n kwadraat betekent dat in
het ergste geval, zoiets als

117
00:05:04,710 --> 00:05:07,780
selectie sorteren zou nemen
n kwadraat stappen.

118
00:05:07,780 --> 00:05:10,310
Of iets als insertion sort
zou n kwadraat stappen.

119
00:05:10,310 --> 00:05:15,150
Nu voor iets als inbrengen
sorteren, wat het ergste geval was?

120
00:05:15,150 --> 00:05:18,200
Gegeven een array, wat is het ergste
mogelijke scenario dat je zou kunnen vinden

121
00:05:18,200 --> 00:05:20,650
je geconfronteerd wordt met?

122
00:05:20,650 --> 00:05:21,860
>> Het is volledig achteruit, toch?

123
00:05:21,860 --> 00:05:24,530
Want als het helemaal naar achteren,
moet je een heleboel werk te doen.

124
00:05:24,530 --> 00:05:26,420
Want als je helemaal naar achter bent,
je gaat naar het vinden

125
00:05:26,420 --> 00:05:28,840
grootste element hier, hoewel
het behoort daar beneden.

126
00:05:28,840 --> 00:05:31,140
Dus je gaat zeggen, oke, op
dit moment in de tijd, hier u behoort,

127
00:05:31,140 --> 00:05:32,310
zodat je hem met rust laat.

128
00:05:32,310 --> 00:05:35,425
>> Dan besef je, oh, damn, ik moet
verplaats deze iets kleiner element aan

129
00:05:35,425 --> 00:05:36,470
links van u.

130
00:05:36,470 --> 00:05:38,770
Dan moet ik dat opnieuw doen
en weer.

131
00:05:38,770 --> 00:05:41,410
En als ik liep heen en weer, je
zou soort van voelen de prestaties van

132
00:05:41,410 --> 00:05:45,540
dat algoritme, omdat steeds ben ik
schuifelen iedereen die in de

133
00:05:45,540 --> 00:05:46,510
array om ruimte te maken voor het.

134
00:05:46,510 --> 00:05:47,750
Dus dat is het ergste geval.

135
00:05:47,750 --> 00:05:48,570
>> Daarentegen -

136
00:05:48,570 --> 00:05:50,320
en dit was een cliffhanger vorige keer -

137
00:05:50,320 --> 00:05:54,065
zeiden we dat insertion sort
was een omega van wat?

138
00:05:54,065 --> 00:05:57,530
Wat is de best-case running
tijd van insertion sort?

139
00:05:57,530 --> 00:05:58,520
Dus het is eigenlijk n.

140
00:05:58,520 --> 00:06:00,980
Dat was het leeg dat we vertrokken
op het bord vorige keer.

141
00:06:00,980 --> 00:06:03,160
>> En het is omega van n want waarom?

142
00:06:03,160 --> 00:06:06,630
Nou, in het beste geval, wat is
insertion sort gaat worden overhandigd?

143
00:06:06,630 --> 00:06:09,830
Nou ja, een lijst die volledig is naargelang
al, een minimum aan werk te doen.

144
00:06:09,830 --> 00:06:12,460
Maar wat is er netjes over insertion sort
is dat omdat het begint hier en

145
00:06:12,460 --> 00:06:15,340
beslist, oh, jij bent de nummer
een, je hoort hier.

146
00:06:15,340 --> 00:06:16,970
O, wat een geluk.

147
00:06:16,970 --> 00:06:17,740
>> Jij bent de nummer twee.

148
00:06:17,740 --> 00:06:19,030
Jij ook hier hoort.

149
00:06:19,030 --> 00:06:21,010
Nummer drie, nog beter,
jij hier thuis.

150
00:06:21,010 --> 00:06:25,210
Zodra het wordt om het einde van de
pseudocode lijst, per insertion sort's

151
00:06:25,210 --> 00:06:28,010
dat we liepen door mondeling
vorige keer, is het gedaan.

152
00:06:28,010 --> 00:06:32,790
Maar selectie sorteren daarentegen
bleef doen wat?

153
00:06:32,790 --> 00:06:35,260
>> Bleef gaan door de lijst
opnieuw en opnieuw en opnieuw.

154
00:06:35,260 --> 00:06:39,160
Omdat het belangrijk inzicht was er slechts
zodra je de hele weg heb gekeken naar de

155
00:06:39,160 --> 00:06:42,500
einde van de lijst kunt u er zeker van zijn
dat het element dat u gekozen was

156
00:06:42,500 --> 00:06:45,560
inderdaad nog kleinste element.

157
00:06:45,560 --> 00:06:48,920
Dus deze verschillende mentale modellen einde
up waardoor een aantal zeer reële-wereld

158
00:06:48,920 --> 00:06:53,130
verschillen voor ons, evenals deze
theoretische asymptotische verschillen.

159
00:06:53,130 --> 00:06:56,910
>> Dus gewoon om samen te vatten, dan, grote O van n
kwadraat, hebben we gezien hoe een paar van zulke

160
00:06:56,910 --> 00:06:58,350
algoritmen tot nu toe.

161
00:06:58,350 --> 00:06:59,580
Big O van n?

162
00:06:59,580 --> 00:07:02,870
Wat is een algoritme dat kon
worden gezegd dat grote O van n?

163
00:07:02,870 --> 00:07:06,930
In het ergste geval is
een lineaire aantal stappen.

164
00:07:06,930 --> 00:07:07,810
>> OK, lineair zoeken.

165
00:07:07,810 --> 00:07:10,470
En in het ergste geval, wanneer de
element dat u zoekt bij

166
00:07:10,470 --> 00:07:12,950
toepassen van lineaire zoeken?

167
00:07:12,950 --> 00:07:14,680
>> OK, in het ergste geval,
het is zelfs daar niet.

168
00:07:14,680 --> 00:07:17,000
Of in het tweede slechtste geval, het is
helemaal op het einde, dat is

169
00:07:17,000 --> 00:07:18,880
plus-of minus-een stap verschil.

170
00:07:18,880 --> 00:07:21,180
Dus aan het eind van de dag,
we kunnen zeggen dat het lineair.

171
00:07:21,180 --> 00:07:23,910
Big O van n zou lineair zoeken zijn,
omdat in het ergste geval, de

172
00:07:23,910 --> 00:07:26,610
element is ook daar niet of het is
helemaal aan het einde.

173
00:07:26,610 --> 00:07:29,370
>> Nou, big O van log van n.

174
00:07:29,370 --> 00:07:32,760
We praatten niet in detail over
dit, maar we hebben dit eerder gezien.

175
00:07:32,760 --> 00:07:36,840
Wat loopt in zogenaamde logaritmische
tijd, in het ergste geval?

176
00:07:36,840 --> 00:07:38,500
>> Ja, dus binair zoeken.

177
00:07:38,500 --> 00:07:42,930
En binaire in de worst case
kan het element ergens in zijn

178
00:07:42,930 --> 00:07:45,640
het midden, of ergens
binnen de array.

179
00:07:45,640 --> 00:07:48,040
Maar u alleen te vinden als je eenmaal
verdelen de lijst in de helft, in

180
00:07:48,040 --> 00:07:48,940
half, in half, in half.

181
00:07:48,940 --> 00:07:50,200
En dan voila, het is er.

182
00:07:50,200 --> 00:07:52,500
Of nog, het ergste geval,
het is zelfs daar niet.

183
00:07:52,500 --> 00:07:56,770
Maar je weet niet dat het er niet is
totdat je soort te bereiken dat laatste

184
00:07:56,770 --> 00:08:00,470
onderste elementen door halvering
en halveren en halveren.

185
00:08:00,470 --> 00:08:01,400
>> Big O van 1.

186
00:08:01,400 --> 00:08:03,540
Dus konden we grote O van 2, grote O van 3.

187
00:08:03,540 --> 00:08:06,260
Wanneer je maar wilt gewoon een constant aantal,
we gewoon soort van gewoon te vereenvoudigen

188
00:08:06,260 --> 00:08:07,280
dat zo groot O van 1.

189
00:08:07,280 --> 00:08:10,440
Hoewel als realistisch, duurt
2 of zelfs 100 treden, als het een

190
00:08:10,440 --> 00:08:13,680
constant aantal stappen,
we gewoon zeggen grote O van 1.

191
00:08:13,680 --> 00:08:15,930
Wat is een algoritme dat is
in grote O van 1?

192
00:08:15,930 --> 00:08:18,350
>> PUBLIEK: Het vinden van de lengte
een variabele.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Het vinden van de
lengte van een variabele?

194
00:08:21,090 --> 00:08:23,870
>> PUBLIEK: Nee, de lengte
indien deze al is opgelost.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Good.

196
00:08:24,160 --> 00:08:27,850
OK, dus het vinden van de lengte van iets
Als de lengte van dat wat, zoals

197
00:08:27,850 --> 00:08:30,020
een array, wordt opgeslagen in een aantal variabele.

198
00:08:30,020 --> 00:08:33,380
Want je kunt gewoon lezen van de variabele,
of print de variabele of

199
00:08:33,380 --> 00:08:34,960
gewoon over het algemeen toegang tot die variabele.

200
00:08:34,960 --> 00:08:37,299
En voila, dat constante tijd kost.

201
00:08:37,299 --> 00:08:38,909
>> Daarentegen denkt terug te krabben.

202
00:08:38,909 --> 00:08:42,460
Denk terug aan de eerste week van C,
gewoon printf bellen en printen

203
00:08:42,460 --> 00:08:46,240
iets op het scherm is aantoonbaar
constante tijd, want het duurt slechts

204
00:08:46,240 --> 00:08:50,880
sommige aantal CPU-cycli te tonen
dat de tekst op het scherm.

205
00:08:50,880 --> 00:08:52,720
Of wacht - doet het?

206
00:08:52,720 --> 00:08:56,430
Hoe anders kunnen we modelleren de
prestaties van printf?

207
00:08:56,430 --> 00:09:00,420
Zou iemand willen oneens, dat
misschien is het niet echt constant tijd?

208
00:09:00,420 --> 00:09:03,600
In welke zin zou printf loopt
tijd, eigenlijk het afdrukken van een snaar op

209
00:09:03,600 --> 00:09:05,580
het scherm, iets
dan constant.

210
00:09:05,580 --> 00:09:07,860
>> PUBLIEK: [onverstaanbaar].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Yeah.

212
00:09:08,230 --> 00:09:09,300
Dus het hangt af van ons perspectief.

213
00:09:09,300 --> 00:09:13,390
Als we eigenlijk denken van de input aan
printf als de string, en

214
00:09:13,390 --> 00:09:16,380
dus de grootte van dat meten we
ingang door zijn lengte - dus laten we noemen

215
00:09:16,380 --> 00:09:17,780
die lengte n, alsook -

216
00:09:17,780 --> 00:09:21,990
betwistbaar, printf is zelf grote O van n
omdat het gaat om je n stappen te ondernemen

217
00:09:21,990 --> 00:09:24,750
uit te printen elk van deze n
karakters, waarschijnlijk.

218
00:09:24,750 --> 00:09:27,730
Althans voorzover we aannemen
dat misschien is het gebruik van een lus

219
00:09:27,730 --> 00:09:28,560
onder de motorkap.

220
00:09:28,560 --> 00:09:30,860
>> Maar we zouden moeten kijken naar dat
coderen om het beter te begrijpen.

221
00:09:30,860 --> 00:09:33,650
En inderdaad, zodra jullie beginnen
het analyseren van uw eigen algoritmes, je zult

222
00:09:33,650 --> 00:09:34,900
letterlijk dat ook te doen.

223
00:09:34,900 --> 00:09:37,765
Soort oogbol uw code en denken
over - oke, ik heb deze lus

224
00:09:37,765 --> 00:09:41,870
hier of ik heb een geneste lussen hier,
dat gaat n dingen n keer, doe

225
00:09:41,870 --> 00:09:46,050
en u kunt sorteren van reden uw weg
door de code, zelfs als het

226
00:09:46,050 --> 00:09:47,980
pseudocode en niet de werkelijke code.

227
00:09:47,980 --> 00:09:49,730
>> Dus hoe zit het omega van n kwadraat?

228
00:09:49,730 --> 00:09:53,582
Wat is een algoritme dat de beste
geval, nam nog n kwadraat stappen?

229
00:09:53,582 --> 00:09:54,014
Yeah?

230
00:09:54,014 --> 00:09:54,880
>> PUBLIEK: [onverstaanbaar].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: So selectie sorteren.

232
00:09:55,900 --> 00:09:59,150
Want in dat probleem echt verminderd
aan het feit dat nogmaals, ik weet het niet

233
00:09:59,150 --> 00:10:02,600
Ik heb gevonden de huidige kleinste tot
Ik heb alle darn elementen gecontroleerd.

234
00:10:02,600 --> 00:10:08,050
Dus omega van, zeg, n, we
net kwam met een.

235
00:10:08,050 --> 00:10:09,300
Insertion sort.

236
00:10:09,300 --> 00:10:12,370
Als de lijst gebeurt te sorteren
reeds, in het beste geval hebben we alleen maar

237
00:10:12,370 --> 00:10:15,090
om een ​​doorgang te maken doorheen,
op welk punt we zeker.

238
00:10:15,090 --> 00:10:17,890
En dan dat kan worden gezegd
lineair te zijn, zeker.

239
00:10:17,890 --> 00:10:20,570
>> Hoe zit het omega van 1?

240
00:10:20,570 --> 00:10:23,790
Wat, in het beste geval, zou kunnen nemen
een constant aantal stappen?

241
00:10:23,790 --> 00:10:27,220
Zo lineair zoeken, als je gewoon geluk
en het element dat u op zoek bent

242
00:10:27,220 --> 00:10:31,000
is meteen aan het begin van de lijst,
als dat is waar je begint je

243
00:10:31,000 --> 00:10:33,070
lineaire traversal van die lijst.

244
00:10:33,070 --> 00:10:35,180
>> En dit geldt voor een
aantal dingen.

245
00:10:35,180 --> 00:10:37,660
Bijvoorbeeld, zelfs binaire
zoek is omega van 1.

246
00:10:37,660 --> 00:10:40,310
Want wat als je echt darn
geluk en smack-dab in het midden van

247
00:10:40,310 --> 00:10:42,950
de array is het aantal
u zoekt?

248
00:10:42,950 --> 00:10:45,730
Dus je kunt daar je geluk, als goed.

249
00:10:45,730 --> 00:10:49,190
>> Deze, ten slotte, omega van n log n.

250
00:10:49,190 --> 00:10:52,573
Zo n log n, we deden niet echt
praten over nog niet, maar -

251
00:10:52,573 --> 00:10:53,300
>> PUBLIEK: sorteer samenvoegen?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: Merge sort.

253
00:10:53,960 --> 00:10:56,920
Dat was de cliffhanger van de vorige keer,
waar we voorgesteld en we kwamen

254
00:10:56,920 --> 00:10:58,600
visueel, dat er algoritmen.

255
00:10:58,600 --> 00:11:02,470
En samenvoegen soort slechts een dergelijke
algoritme die fundamenteel sneller

256
00:11:02,470 --> 00:11:03,450
dan sommige van die andere jongens.

257
00:11:03,450 --> 00:11:07,800
In feite, samenvoegen kort is niet alleen in de
beste geval n log n, in het slechtste

258
00:11:07,800 --> 00:11:09,460
geval n log n.

259
00:11:09,460 --> 00:11:14,540
En als je dit samenvallen van
omega en grote O is hetzelfde ding?

260
00:11:14,540 --> 00:11:17,310
We kunnen eigenlijk omschrijven dat als wat
genaamd theta, al is het een

261
00:11:17,310 --> 00:11:18,220
iets minder vaak voor.

262
00:11:18,220 --> 00:11:21,730
Maar dat betekent dat de twee grenzen,
in dit geval zijn hetzelfde.

263
00:11:21,730 --> 00:11:25,770
>> Dus samenvoegen soort, wat betekent dit
echt neer op voor ons?

264
00:11:25,770 --> 00:11:27,000
Nou, herinneren aan de motivatie.

265
00:11:27,000 --> 00:11:30,340
Laat ik trek een andere animatie die
We keken niet naar vorige keer.

266
00:11:30,340 --> 00:11:33,390
Deze, hetzelfde idee, maar
het is een beetje groter.

267
00:11:33,390 --> 00:11:36,160
En ik ga je gang gaan en wijzen
eerste - we hebben insertion sort op

268
00:11:36,160 --> 00:11:39,410
linksboven, dan selectie sorteren,
bubble sort, een paar andere soorten -

269
00:11:39,410 --> 00:11:42,670
shell en snel - dat we niet hebben gesproken
over, en hoop en samenvoegen sorteren.

270
00:11:42,670 --> 00:11:47,090
>> Dus op zijn minst proberen om uw ogen te focussen op
de top drie aan de linkerkant en vervolgens

271
00:11:47,090 --> 00:11:49,120
merge sort als ik klik
Deze groene pijl.

272
00:11:49,120 --> 00:11:51,900
Maar ik laat ze allemaal lopen, gewoon om te
geven je een gevoel van de diversiteit van

273
00:11:51,900 --> 00:11:53,980
algoritmen die in de wereld bestaan.

274
00:11:53,980 --> 00:11:56,180
Ik ga dit te laten lopen
voor slechts een paar seconden.

275
00:11:56,180 --> 00:11:59,640
En als je je ogen richten - kies een
algoritme, gericht op het voor slechts een

276
00:11:59,640 --> 00:12:02,970
seconden - u zult beginnen om het te zien
patroon dat het uitvoering.

277
00:12:02,970 --> 00:12:04,530
>> Merge sort, bericht, wordt gedaan.

278
00:12:04,530 --> 00:12:06,430
Heap sort, snel sorteren, shell -

279
00:12:06,430 --> 00:12:09,480
dus het lijkt erop dat we de drie geïntroduceerd
slechtste algoritmen vorige week.

280
00:12:09,480 --> 00:12:12,960
Maar dat is goed, dat wij hier vandaag te
kijk naar merge sort, dat is een van

281
00:12:12,960 --> 00:12:16,500
het gemakkelijker degenen is om naar te kijken, zelfs
hoewel het waarschijnlijk zal je geest buigen

282
00:12:16,500 --> 00:12:17,490
maar een klein beetje.

283
00:12:17,490 --> 00:12:21,130
Hier kunnen we zien hoeveel
selectie sorteren zuigt.

284
00:12:21,130 --> 00:12:24,600
>> Maar aan de andere kant, het is
heel eenvoudig te implementeren.

285
00:12:24,600 --> 00:12:28,160
En misschien voor P Set 3, dat is een van de
algoritmes je ervoor kiest om te implementeren

286
00:12:28,160 --> 00:12:28,960
voor de standaard editie.

287
00:12:28,960 --> 00:12:30,970
Prima, volkomen juist.

288
00:12:30,970 --> 00:12:35,210
>> Maar nogmaals, als n groot wordt, als je
kiezen voor een sneller algoritme te implementeren

289
00:12:35,210 --> 00:12:39,020
willen samenvoegen sorteren, kansen zijn in grotere en
grotere ingangen, uw code is gewoon

290
00:12:39,020 --> 00:12:39,800
gaan om sneller te lopen.

291
00:12:39,800 --> 00:12:41,090
Uw website gaat beter werken.

292
00:12:41,090 --> 00:12:42,650
Uw gebruikers zullen gelukkiger zijn.

293
00:12:42,650 --> 00:12:45,280
En dus zijn er deze effecten
van daadwerkelijk geven

294
00:12:45,280 --> 00:12:47,350
ons een diepere gedachte.

295
00:12:47,350 --> 00:12:49,990
>> Dus laten we eens kijken naar wat fuseren
soort is eigenlijk alles over.

296
00:12:49,990 --> 00:12:52,992
Het koele ding is dat fuseren
sort is gewoon dit.

297
00:12:52,992 --> 00:12:56,300
Dit is, nogmaals, wat we hebben genoemd
pseudocode pseudocode wezen

298
00:12:56,300 --> 00:12:57,720
Engels-achtige syntax.

299
00:12:57,720 --> 00:12:59,890
En de eenvoud
soort fascinerend.

300
00:12:59,890 --> 00:13:02,840
>> Dus op de input van n elementen - zodat
betekent gewoon, hier is een array.

301
00:13:02,840 --> 00:13:04,000
Het is n dingen in het kregen.

302
00:13:04,000 --> 00:13:05,370
Dat is alles wat we daar zeggen.

303
00:13:05,370 --> 00:13:07,560
>> Als n kleiner is dan 2, terugkeren.

304
00:13:07,560 --> 00:13:08,640
Dus dat is gewoon de triviale zaak.

305
00:13:08,640 --> 00:13:12,580
Als n kleiner is dan 2, dan is het uiteraard
1 of 0, waarbij de zaak

306
00:13:12,580 --> 00:13:14,780
al naargelang of niet-bestaand,
dus gewoon terug.

307
00:13:14,780 --> 00:13:15,900
Er is niets te doen.

308
00:13:15,900 --> 00:13:18,360
Dus dat is een simpel geval af te plukken.

309
00:13:18,360 --> 00:13:20,110
>> Anders, we hebben drie stappen.

310
00:13:20,110 --> 00:13:23,650
Sorteer de linkerhelft van de elementen, sorteren
de rechterhelft van de elementen,

311
00:13:23,650 --> 00:13:26,650
en dan fuseren de gesorteerde helften.

312
00:13:26,650 --> 00:13:29,400
Wat interessant is dat
Ik ben soort van punteren, toch?

313
00:13:29,400 --> 00:13:32,300
Er is een soort van een circulaire definitie
dit algoritme.

314
00:13:32,300 --> 00:13:35,986
In welke zin is dit algoritme's
definition ronde?

315
00:13:35,986 --> 00:13:37,850
>> PUBLIEK: [onverstaanbaar].

316
00:13:37,850 --> 00:13:41,670
>> DAVID MALAN: Ja, mijn sorteer-algoritme,
twee van haar stappen zijn "soort

317
00:13:41,670 --> 00:13:44,640
iets. 'En dat roept de
vraag, goed, wat ik ga gebruiken

318
00:13:44,640 --> 00:13:46,460
de linkerhelft sorteren
en de rechterhelft?

319
00:13:46,460 --> 00:13:49,600
En het mooie is dat alhoewel
nogmaals, dit is de mind-bending

320
00:13:49,600 --> 00:13:54,030
deel potentieel, kunt u gebruik maken van dezelfde
algoritme om de linkerhelft sorteren.

321
00:13:54,030 --> 00:13:54,700
>> Maar wacht eens even.

322
00:13:54,700 --> 00:13:57,070
Als je verteld om het te sorteren
linkerhelft, wat zijn de twee

323
00:13:57,070 --> 00:13:58,240
stappen heen te zijn?

324
00:13:58,240 --> 00:14:00,550
We zullen de linker helft van de gekozen afstand
linker en rechter

325
00:14:00,550 --> 00:14:01,420
helft van de linkerhelft.

326
00:14:01,420 --> 00:14:04,430
Verdomme, hoe sorteer ik die twee
helften of kwarten, nu?

327
00:14:04,430 --> 00:14:05,260
>> Maar dat is OK.

328
00:14:05,260 --> 00:14:07,830
We hebben hier een sorteer-algoritme.

329
00:14:07,830 --> 00:14:10,660
En hoewel je zou kunnen zorgen bij
eerste is dit soort van een oneindige

330
00:14:10,660 --> 00:14:12,780
lus, het is een cyclus die is nooit
gaat eindigen - het gaat om

331
00:14:12,780 --> 00:14:15,770
eindigen wanneer wat gebeurt er?

332
00:14:15,770 --> 00:14:16,970
Zodra n kleiner is dan 2.

333
00:14:16,970 --> 00:14:19,180
Die uiteindelijk gaat gebeuren,
want als je blijft halveren en

334
00:14:19,180 --> 00:14:23,020
halvering in halveren deze helften, zeker
uiteindelijk je gaat eindigen

335
00:14:23,020 --> 00:14:25,350
met slechts 1 of 0 elementen.

336
00:14:25,350 --> 00:14:28,500
Op welk punt, dit algoritme
zegt dat je klaar bent.

337
00:14:28,500 --> 00:14:31,020
>> Dus de echte magie in deze
algoritme lijkt in

338
00:14:31,020 --> 00:14:33,470
die laatste stap, het samenvoegen.

339
00:14:33,470 --> 00:14:37,190
Dat simpel idee gewoon samenvoegen van twee
dingen, dat is wat er uiteindelijk gaat

340
00:14:37,190 --> 00:14:40,920
om ons in staat om een ​​scala van sorteren,
laten we zeggen, acht elementen.

341
00:14:40,920 --> 00:14:44,410
Dus ik heb acht meer stress ballen omhoog
hier, acht stukjes papier, en een

342
00:14:44,410 --> 00:14:45,500
Google Glass -

343
00:14:45,500 --> 00:14:46,140
die ik krijg te houden.

344
00:14:46,140 --> 00:14:46,960
>> [Lachen]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Als we acht konden nemen
vrijwilligers, en laten we kijken of we kunnen

346
00:14:48,970 --> 00:14:51,430
spelen dit uit, zo.

347
00:14:51,430 --> 00:14:52,500
Wow, OK.

348
00:14:52,500 --> 00:14:53,565
Informatica wordt steeds leuk.

349
00:14:53,565 --> 00:14:54,320
Oke.

350
00:14:54,320 --> 00:14:57,770
Dus hoe zit je drie,
grootste de hand daar.

351
00:14:57,770 --> 00:14:58,580
Vier in de rug.

352
00:14:58,580 --> 00:15:02,220
En hoe zit zullen wij u doen
drie in deze rij?

353
00:15:02,220 --> 00:15:03,390
En vier aan de voorkant.

354
00:15:03,390 --> 00:15:04,920
Dus je acht, kom op maximaal.

355
00:15:04,920 --> 00:15:12,060
>> [Lachen]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Ik ben eigenlijk
niet zeker wat het is.

357
00:15:13,450 --> 00:15:14,810
Is het de stress ballen?

358
00:15:14,810 --> 00:15:16,510
De bureaulampen?

359
00:15:16,510 --> 00:15:18,650
Het materiaal?

360
00:15:18,650 --> 00:15:19,680
Het internet?

361
00:15:19,680 --> 00:15:20,160
>> OK.

362
00:15:20,160 --> 00:15:21,310
Dus kom op omhoog.

363
00:15:21,310 --> 00:15:22,310
Wie zou willen -

364
00:15:22,310 --> 00:15:23,570
blijven komen.

365
00:15:23,570 --> 00:15:24,240
Laten we eens kijken.

366
00:15:24,240 --> 00:15:26,460
En dit zet je in de locatie -

367
00:15:26,460 --> 00:15:27,940
je bent in een locatie.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, wacht even.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - oh, goed.

370
00:15:30,760 --> 00:15:31,310
Oke, we zijn goed.

371
00:15:31,310 --> 00:15:35,130
Oke, dus iedereen een zitplaats,
maar niet op de Google Glass.

372
00:15:35,130 --> 00:15:36,475
Laat me in de rij deze omhoog.

373
00:15:36,475 --> 00:15:37,115
Wat is je naam?

374
00:15:37,115 --> 00:15:37,440
>> MICHELLE: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID Malan: Michelle?

376
00:15:38,090 --> 00:15:42,000
Oke, krijg je te zien als
de geek, als dat is OK.

377
00:15:42,000 --> 00:15:44,625
Nou, ik ook doen, denk ik,
voor slechts een moment.

378
00:15:44,625 --> 00:15:45,875
Oke, standby.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
We hebben geprobeerd om te komen met een
use case voor Google Glas, en we

381
00:15:50,950 --> 00:15:53,750
vond het leuk om gewoon te doen zou zijn
dit wanneer mensen op het podium.

382
00:15:53,750 --> 00:15:57,120
We zullen de wereld opnemen
vanuit hun perspectief.

383
00:15:57,120 --> 00:15:58,410
Oke.

384
00:15:58,410 --> 00:15:59,830
Niet waarschijnlijk wat Google bedoeld.

385
00:15:59,830 --> 00:16:02,260
Oke, als je het niet erg dragen
dit voor de volgende lastige minuten,

386
00:16:02,260 --> 00:16:03,150
dat zou geweldig zijn.

387
00:16:03,150 --> 00:16:08,620
>> Oke, dus we hebben hier een scala aan
elementen, en de matrix, volgens de

388
00:16:08,620 --> 00:16:11,480
stukjes papier in deze mensen '
handen, wordt momenteel ongesorteerd.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Oh, dat is zo raar.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Het is vrij veel willekeurig.

391
00:16:12,810 --> 00:16:15,760
En in slechts een moment, we gaan proberen
te implementeren samenvoegen sorteren

392
00:16:15,760 --> 00:16:17,950
en zie waar dat belangrijk inzicht is.

393
00:16:17,950 --> 00:16:21,970
En de truc hier met merge sort is
iets dat we nog niet hebben aangenomen.

394
00:16:21,970 --> 00:16:24,030
We hebben eigenlijk een aantal
extra ruimte.

395
00:16:24,030 --> 00:16:26,650
Dus wat gaat bijzonder worden
interessante hieraan is dat deze

396
00:16:26,650 --> 00:16:29,270
jongens gaan bewegen een beetje
beetje, want ik ga ervan uit dat

397
00:16:29,270 --> 00:16:31,880
er is een extra serie van ruimte,
zeggen, vlak achter hen.

398
00:16:31,880 --> 00:16:34,570
>> Dus als ze achter hun stoel,
dat is de secundaire array.

399
00:16:34,570 --> 00:16:36,960
Als ze hier zitten, dat is
de primaire matrix.

400
00:16:36,960 --> 00:16:40,170
Maar dit is een bron die we hebben
niet tot zover leveraged met bel

401
00:16:40,170 --> 00:16:42,040
soort, met selectie sorteren,
met insertion sort.

402
00:16:42,040 --> 00:16:44,600
Vorige week herinneren, iedereen gewoon
soort schuifelde op zijn plaats.

403
00:16:44,600 --> 00:16:46,840
Ze gebruikten geen extra geheugen.

404
00:16:46,840 --> 00:16:49,310
We hebben ruimte voor mensen met
bewegende mensen rond.

405
00:16:49,310 --> 00:16:50,580
>> Dus dit is een belangrijk inzicht, ook.

406
00:16:50,580 --> 00:16:53,410
Er is deze trade-off, in het algemeen in
computer wetenschap, van middelen.

407
00:16:53,410 --> 00:16:55,800
Als je wilt versnellen iets
zoals tijd, je gaat

408
00:16:55,800 --> 00:16:56,900
een prijs moeten betalen.

409
00:16:56,900 --> 00:17:00,750
En een van die prijzen is heel vaak
ruimte, de hoeveelheid geheugen of harde

410
00:17:00,750 --> 00:17:01,700
schijfruimte die u gebruikt.

411
00:17:01,700 --> 00:17:03,640
Of, eerlijk gezegd, het bedrag
van de programmeur tijd.

412
00:17:03,640 --> 00:17:06,700
Hoeveel tijd het kost u, de mens,
om daadwerkelijk uit te voeren wat meer

413
00:17:06,700 --> 00:17:07,829
ingewikkeld algoritme.

414
00:17:07,829 --> 00:17:09,760
Maar voor vandaag, de trade-off
is tijd en ruimte.

415
00:17:09,760 --> 00:17:11,930
>> Dus als jullie gewoon kon houden je
nummers, zodat we kunnen zien dat je bent

416
00:17:11,930 --> 00:17:15,839
inderdaad bijpassende 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Excellent.

418
00:17:16,599 --> 00:17:19,520
Dus ik ga proberen te orkestreren
dingen, als jullie kunnen gewoon

419
00:17:19,520 --> 00:17:21,800
Volg hier mijn lood.

420
00:17:21,800 --> 00:17:26,650
>> Dus ik ga voeren, ten eerste, de
eerste stap van de pseudocode, die

421
00:17:26,650 --> 00:17:29,440
de input van n elementen, als n
minder dan 2, dan terug.

422
00:17:29,440 --> 00:17:31,370
Uiteraard, dat niet
van toepassing zijn, zodat we verder.

423
00:17:31,370 --> 00:17:33,340
Dus sorteren de linkerhelft van de elementen.

424
00:17:33,340 --> 00:17:36,220
Dus dat betekent dat ik ga focussen mijn
aandacht voor slechts een moment in de volgende

425
00:17:36,220 --> 00:17:37,310
vier jongens hier.

426
00:17:37,310 --> 00:17:39,774
Oke, wat moet ik nu doen?

427
00:17:39,774 --> 00:17:40,570
>> PUBLIEK: Sorteer de linker helft.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Dus nu heb ik om te sorteren
de linker helft van deze jongens.

429
00:17:42,780 --> 00:17:45,580
Want nogmaals, neem je jezelf de
doel is de linkerhelft sorteren.

430
00:17:45,580 --> 00:17:46,440
Hoe doe je dat?

431
00:17:46,440 --> 00:17:49,140
Volg gewoon de instructies, zelfs
maar we doen het weer.

432
00:17:49,140 --> 00:17:50,160
Zo sorteert de linker helft.

433
00:17:50,160 --> 00:17:52,030
Nu ben ik sorteer deze twee jongens.

434
00:17:52,030 --> 00:17:53,563
Wat komt er nu?

435
00:17:53,563 --> 00:17:54,510
>> PUBLIEK: Sorteer de linker helft.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: Sorteer de linker helft.

437
00:17:55,460 --> 00:18:00,680
Dus nu deze, deze stoel hier,
is een lijst van maat 1.

438
00:18:00,680 --> 00:18:01,365
En hoe heet je ook alweer?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Princess Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princess Daisy is hier.

441
00:18:03,690 --> 00:18:07,470
En dus is ze al naargelang, omdat
de lijst is van grootte 1.

442
00:18:07,470 --> 00:18:09,490
Wat moet ik nu doen?

443
00:18:09,490 --> 00:18:13,680
OK, terug te keren, want die lijst is van
size 1, die kleiner is dan 2.

444
00:18:13,680 --> 00:18:14,320
Wat is dan de volgende stap?

445
00:18:14,320 --> 00:18:17,490
En nu moet je soort van
backtrack in je geest.

446
00:18:17,490 --> 00:18:19,340
>> Sorteer de rechterhelft, die -

447
00:18:19,340 --> 00:18:19,570
wat is je naam?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID Malan: Linda.

450
00:18:20,980 --> 00:18:23,210
En dus wat doen we nu, dat doen
We hebben een lijst van maat 1?

451
00:18:23,210 --> 00:18:24,440
>> PUBLIEK: Return.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: Voorzichtig.

453
00:18:24,760 --> 00:18:29,540
We keren terug eerste, en nu de derde
stap - en als ik het soort uitbeelden deze door

454
00:18:29,540 --> 00:18:33,490
het omarmen van de twee zetels nu, nu ik
moeten deze twee elementen samen te voegen.

455
00:18:33,490 --> 00:18:35,530
Dus nu helaas elementen
zijn niet in orde.

456
00:18:35,530 --> 00:18:39,920
Maar dat is waar de fuserende proces
begint te dwingend te krijgen.

457
00:18:39,920 --> 00:18:42,410
>> Dus als jullie omhoog kon staan ​​voor slechts
een moment, ik ga je nodig hebt, in een

458
00:18:42,410 --> 00:18:44,170
ogenblik, naar stap achter je stoel.

459
00:18:44,170 --> 00:18:46,480
Als Linda, omdat 2
kleiner dan 4, waarom niet

460
00:18:46,480 --> 00:18:48,130
je rond komt eerst?

461
00:18:48,130 --> 00:18:48,690
Blijf daar.

462
00:18:48,690 --> 00:18:50,520
Dus Linda, rond komt u eerst.

463
00:18:50,520 --> 00:18:53,820
>> Nu in werkelijkheid is het maar een array
we konden haar gewoon bewegen in real-time

464
00:18:53,820 --> 00:18:55,360
van deze stoel naar deze plek.

465
00:18:55,360 --> 00:18:57,770
Dus stel dat een aantal constante nam
aantal stappen 1.

466
00:18:57,770 --> 00:18:58,480
En nu -

467
00:18:58,480 --> 00:19:01,490
maar we moeten u in
de eerste plaats hier.

468
00:19:01,490 --> 00:19:03,930
>> En nu als je rond kon komen,
als goed, we gaan

469
00:19:03,930 --> 00:19:06,300
in plaats twee.

470
00:19:06,300 --> 00:19:09,120
En ook al voelt dit als het is
het nemen van een tijdje, wat is er nu leuk is

471
00:19:09,120 --> 00:19:14,710
dat de linkerhelft van de
linkerhelft wordt nu gesorteerd.

472
00:19:14,710 --> 00:19:18,010
Dus wat is de volgende stap, als we nu
terugspoelen verder in het verhaal?

473
00:19:18,010 --> 00:19:18,980
>> PUBLIEK: Rechter helft.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: Sorteer de rechter helft.

475
00:19:19,900 --> 00:19:21,320
Dus jullie moeten dit doen, als goed.

476
00:19:21,320 --> 00:19:23,510
Dus als je zou kunnen opstaan
voor slechts een moment?

477
00:19:23,510 --> 00:19:25,192
En wat is je naam?

478
00:19:25,192 --> 00:19:25,540
>> JESS: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID Malan: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, dus Jess is nu de linker
helft van de rechterhelft.

481
00:19:29,720 --> 00:19:31,400
En dus ze is een lijst van maat 1.

482
00:19:31,400 --> 00:19:32,380
Ze is blijkbaar opgelost.

483
00:19:32,380 --> 00:19:33,070
En je naam ook alweer?

484
00:19:33,070 --> 00:19:33,630
>> MICHELLE: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle is uiteraard
Een lijst van grootte 1.

486
00:19:35,340 --> 00:19:36,050
Ze is al naargelang.

487
00:19:36,050 --> 00:19:38,690
Dus nu de magie gebeurt,
het samenvoegen proces.

488
00:19:38,690 --> 00:19:39,790
Dus wie gaat eerst komt?

489
00:19:39,790 --> 00:19:41,560
Uiteraard Michelle.

490
00:19:41,560 --> 00:19:43,280
Dus als je rond kon terugkomen.

491
00:19:43,280 --> 00:19:47,090
De ruimte die we beschikbaar hebben voor haar nu
ligt pal achter deze stoel hier.

492
00:19:47,090 --> 00:19:51,580
En nu als je terug kon komen als goed,
hebben we nu, om duidelijk te zijn, twee

493
00:19:51,580 --> 00:19:53,810
helften, elk van grootte 2 -

494
00:19:53,810 --> 00:19:57,090
en net omwille van uitbeelding's, als je
kon een beetje een ruimte te maken -

495
00:19:57,090 --> 00:19:59,780
de ene helft hier linksaf, een
rechterhelft hier.

496
00:19:59,780 --> 00:20:01,160
>> Rewind verder in het verhaal.

497
00:20:01,160 --> 00:20:02,270
Welke stap is de volgende?

498
00:20:02,270 --> 00:20:03,030
>> PUBLIEK: samenvoegen.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Dus nu moeten we fuseren.

500
00:20:04,160 --> 00:20:07,490
Dus OK, dus nu, gelukkig, we
net vrijgekomen vier stoelen.

501
00:20:07,490 --> 00:20:11,480
Dus we hebben twee keer gebruikt zoveel geheugen, maar
kunnen we flip-floppen geven tussen

502
00:20:11,480 --> 00:20:12,330
de twee arrays.

503
00:20:12,330 --> 00:20:14,190
Dus welk nummer is de eerste plaats komen?

504
00:20:14,190 --> 00:20:14,850
Dus Michelle, uiteraard.

505
00:20:14,850 --> 00:20:16,680
Dus kom rond en nemen
uw stoel hier.

506
00:20:16,680 --> 00:20:19,120
En dan nummer 2 is uiteraard
volgende, zodat u hier komt.

507
00:20:19,120 --> 00:20:21,520
Nummer 4, nummer 6.

508
00:20:21,520 --> 00:20:23,390
En nogmaals, ook al is er een
beetje wandelen betrokken,

509
00:20:23,390 --> 00:20:26,010
echt, deze kan direct gebeuren,
by moving -

510
00:20:26,010 --> 00:20:26,880
OK, goed gespeeld.

511
00:20:26,880 --> 00:20:28,350
>> [Lachen]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: En nu zijn we
in vrij goede vorm.

513
00:20:29,680 --> 00:20:34,910
De linker helft van de gehele
ingang is nu gesorteerd.

514
00:20:34,910 --> 00:20:37,370
Oke, dus deze jongens had
het voordeel van mijn -

515
00:20:37,370 --> 00:20:40,340
hoe is het uiteindelijk alle meisjes op de
links en alle jongens aan de rechterkant?

516
00:20:40,340 --> 00:20:42,450
>> OK, dus jongens 'nu draaien.

517
00:20:42,450 --> 00:20:44,680
Dus zal ik je niet lopen door
deze stappen.

518
00:20:44,680 --> 00:20:46,550
We zullen zien of we kunnen opnieuw
hetzelfde pseudocode.

519
00:20:46,550 --> 00:20:50,050
Als je vooruit wilt gaan en opstaan,
en jullie, laat me je de microfoon.

520
00:20:50,050 --> 00:20:52,990
Kijk of je niet kan repliceren wat
We deden gewoon hier op de

521
00:20:52,990 --> 00:20:53,880
andere einde van de lijst.

522
00:20:53,880 --> 00:20:59,530
Wie heeft als eerste het woord,
gebaseerd op het algoritme?

523
00:20:59,530 --> 00:21:03,210
Dus uitleggen wat je doet voordat
je maakt elke voetbewegingen.

524
00:21:03,210 --> 00:21:05,930
>> LUIDSPREKER 1: Oke, dus sinds
Ik ben de linkerhelft van de

525
00:21:05,930 --> 00:21:07,790
linkerhelft, keer ik terug.

526
00:21:07,790 --> 00:21:08,730
Rechts?

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Good.

528
00:21:09,250 --> 00:21:10,350
>> LUIDSPREKER 1: En dan -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Wie doet
de microfoon naar de volgende?

530
00:21:11,800 --> 00:21:12,920
>> LUIDSPREKER 1: Volgende nummer.

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2: Dus ik ben de rechter helft
van de linkerhelft van de

532
00:21:14,720 --> 00:21:17,830
linkerhelft, en ik terug.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Good.

534
00:21:18,050 --> 00:21:18,550
U keert terug.

535
00:21:18,550 --> 00:21:21,855
Dus nu wat is de volgende voor jullie twee?

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2: We willen zien wie er kleiner.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Precies.

538
00:21:24,200 --> 00:21:24,940
Wij willen fuseren.

539
00:21:24,940 --> 00:21:27,590
De ruimte die we gaan gebruiken om te fuseren
u in, ook al zijn ze

540
00:21:27,590 --> 00:21:30,250
uiteraard al naargelang, we gaan
op hetzelfde algoritme te volgen.

541
00:21:30,250 --> 00:21:31,560
Dus die gaat in de rug eerste?

542
00:21:31,560 --> 00:21:35,720
Dus 3, en vervolgens 7.

543
00:21:35,720 --> 00:21:38,570
En nu de microfoon gaat
naar deze jongens, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Dus ik ben de rechter helft van de
linkerhelft en mijn n kleiner is dan

545
00:21:43,590 --> 00:21:45,048
1, dus ik ga gewoon door te geven -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Good.

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4: Ik ben de rechter helft van de
rechterhelft van de rechter helft, en ik ben

548
00:21:49,450 --> 00:21:51,740
Ook een persoon, dus ik ben
gaan om terug te keren.

549
00:21:51,740 --> 00:21:52,990
Dus nu we fuseren.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Dus we gaan terug.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Dus jullie gaan in de rug.

553
00:21:57,160 --> 00:21:59,200
Dus 5 gaat als eerste, daarna 8.

554
00:21:59,200 --> 00:22:01,240
Nu doelgroep, de
stappen we nu moeten terugspoelen

555
00:22:01,240 --> 00:22:02,200
terug in onze geest?

556
00:22:02,200 --> 00:22:02,940
>> PUBLIEK: samenvoegen.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: samenvoegen linker helft en rechts
de helft van de oorspronkelijke linkerhelft.

558
00:22:07,270 --> 00:22:08,840
Dus nu -

559
00:22:08,840 --> 00:22:10,520
en alleen maar om dit duidelijk te maken,
maak een beetje ruimte

560
00:22:10,520 --> 00:22:11,690
tussen jullie twee.

561
00:22:11,690 --> 00:22:13,800
Dus nu is dat de twee lijsten,
links en rechts.

562
00:22:13,800 --> 00:22:18,320
Dus hoe kunnen we nu samen te voegen jullie in
de voorste rij stoelen weer?

563
00:22:18,320 --> 00:22:19,600
>> 3 gaat eerst.

564
00:22:19,600 --> 00:22:20,850
Dan 5, uiteraard.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Dan 7, en nu 8.

567
00:22:27,330 --> 00:22:28,710
OK, en nu zijn we?

568
00:22:28,710 --> 00:22:29,650
>> PUBLIEK: Niet uitgevoerd.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Niet gedaan, omdat
natuurlijk, er is een stap overgebleven.

570
00:22:32,440 --> 00:22:35,720
Maar nogmaals, de reden dat ik met behulp van deze
jargon als 'rewind in je geest, "

571
00:22:35,720 --> 00:22:37,160
het is want dat is echt
wat er gebeurt.

572
00:22:37,160 --> 00:22:39,610
We gaan door al deze stappen,
maar we zijn soort pauzeren voor een

573
00:22:39,610 --> 00:22:42,480
Momenteel duiken dieper in de
algoritme, pauzeren voor een moment,

574
00:22:42,480 --> 00:22:45,840
duiken dieper in het algoritme, en
nu hebben we te sorteren van terugspoelen in onze

575
00:22:45,840 --> 00:22:49,430
geesten en ongedaan al deze lagen
dat we soort van in de wacht gezet.

576
00:22:49,430 --> 00:22:51,790
>> Dus nu hebben we twee lijsten van grootte 4.

577
00:22:51,790 --> 00:22:54,790
Als jullie omhoog kon staan ​​een laatste keer
en maak een beetje ruimte hier aan

578
00:22:54,790 --> 00:22:57,230
duidelijk dat dit de linker
helft van de oorspronkelijke, de

579
00:22:57,230 --> 00:22:58,620
rechterhelft van het origineel.

580
00:22:58,620 --> 00:23:01,060
Wie is het eerste nummer dat we
moeten trekken in de rug?

581
00:23:01,060 --> 00:23:01,870
Michelle, natuurlijk.

582
00:23:01,870 --> 00:23:03,230
>> Dus hebben we Michelle hier.

583
00:23:03,230 --> 00:23:05,080
En wie heeft nummer 2?

584
00:23:05,080 --> 00:23:06,440
Nummer 2 komt op de rug ook.

585
00:23:06,440 --> 00:23:07,800
Nummer 3?

586
00:23:07,800 --> 00:23:08,510
Excellent.

587
00:23:08,510 --> 00:23:16,570
Nummer 4, nummer 5, nummer 6,
nummer 7, en nummer 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, dus het voelde als een stuk
stappen, zeker.

589
00:23:18,850 --> 00:23:22,390
Maar laten we nu eens kijken of we niet kunnen bevestigen
soort intuïtief dat deze

590
00:23:22,390 --> 00:23:26,190
algoritme fundamenteel, in het bijzonder als
n wordt echt groot, zoals we hebben gezien

591
00:23:26,190 --> 00:23:29,170
met de animaties, is
fundamenteel sneller.

592
00:23:29,170 --> 00:23:33,400
Dus ik beweer dit algoritme, in het slechtste
case en zelfs in het beste geval,

593
00:23:33,400 --> 00:23:36,160
is big O van n keer log n.

594
00:23:36,160 --> 00:23:39,160
Dat is, er is een aspect van deze
algoritme dat n stappen neemt, maar

595
00:23:39,160 --> 00:23:43,110
er is een ander aspect ergens in
dat iteratie, die looping, dat

596
00:23:43,110 --> 00:23:44,410
neemt log n stappen.

597
00:23:44,410 --> 00:23:49,154
Kunnen we onze vinger op wat die
twee nummers verwijzen naar?

598
00:23:49,154 --> 00:23:51,320
Nou, waar -

599
00:23:51,320 --> 00:23:54,160
waar ging de microfoon te gaan?

600
00:23:54,160 --> 00:23:58,660
>> LUIDSPREKER 1: Zou het log n zijn
breken ons in twee -

601
00:23:58,660 --> 00:23:59,630
delen door twee, in hoofdzaak.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Precies.

603
00:24:00,120 --> 00:24:03,000
Elke keer zien we in elk algoritme dus
ver, er is dit patroon van

604
00:24:03,000 --> 00:24:04,200
verdelen, verdelen, verdelen.

605
00:24:04,200 --> 00:24:05,700
En het is meestal beperkt
naar iets dat

606
00:24:05,700 --> 00:24:07,100
logaritmische, log basis 2.

607
00:24:07,100 --> 00:24:10,180
Maar het kan echt van alles zijn,
maar log base 2.

608
00:24:10,180 --> 00:24:11,330
>> Nu wat over de n?

609
00:24:11,330 --> 00:24:14,550
Ik kan zien dat we soort van verdeelde u
jongens - verdeelde u, verdeeld u,

610
00:24:14,550 --> 00:24:15,910
onderverdeeld u, verdeeld u.

611
00:24:15,910 --> 00:24:18,760
Waar komt het einde vandaan?

612
00:24:18,760 --> 00:24:19,810
>> Dus het is de samenvoeging.

613
00:24:19,810 --> 00:24:20,610
Omdat er over nadenkt.

614
00:24:20,610 --> 00:24:25,420
Als je acht mensen bij elkaar fuseren,
waarbij de helft van hen zijn een reeks van vier

615
00:24:25,420 --> 00:24:27,770
en de andere helft een andere
set van vier, hoe ga je

616
00:24:27,770 --> 00:24:28,820
over het doen van de fusie?

617
00:24:28,820 --> 00:24:30,830
Nou, jullie deden het
vrij intuïtief.

618
00:24:30,830 --> 00:24:34,140
>> Maar als ik in plaats daarvan deed het een beetje meer
methodisch, ik zou hebben gewezen op

619
00:24:34,140 --> 00:24:38,090
de meest linkse persoon voor het eerst met mijn linker
hand, gericht op de meest linkse persoon

620
00:24:38,090 --> 00:24:42,080
van dat half met mijn rechterhand, en
gewoon vervolgens liep door de

621
00:24:42,080 --> 00:24:46,990
lijst, wijzend op het kleinste element
elke keer, beweegt mijn vinger over en

622
00:24:46,990 --> 00:24:48,970
dan zo nodig de hele lijst.

623
00:24:48,970 --> 00:24:51,890
Maar wat is belangrijk over deze samenvoeging
proces is Ik vergelijk deze paren

624
00:24:51,890 --> 00:24:53,460
elementen.

625
00:24:53,460 --> 00:24:57,270
Uit de rechterhelft en van links
half, ben ik niet een keer backtracking.

626
00:24:57,270 --> 00:25:00,570
>> Dus de merge zelf neemt
niet meer dan n stappen.

627
00:25:00,570 --> 00:25:03,250
En hoeveel keer had ik
aan dat samenvoegen doen?

628
00:25:03,250 --> 00:25:07,150
Nou ja, niet meer dan n, en we gewoon
zag dat bij de uiteindelijke samenvoegen.

629
00:25:07,150 --> 00:25:13,120
En dus als je iets dat neemt doen
log n stappen n keer, of vice versa,

630
00:25:13,120 --> 00:25:15,210
Het gaat ons n keer log n geven.

631
00:25:15,210 --> 00:25:16,310
>> En waarom is dit beter?

632
00:25:16,310 --> 00:25:19,600
Nou, als we al weten dat log
n is beter dan n - toch?

633
00:25:19,600 --> 00:25:22,590
We zagen in binary search, het telefoonboek
Bijvoorbeeld, log n was zeker

634
00:25:22,590 --> 00:25:23,760
beter dan lineair.

635
00:25:23,760 --> 00:25:28,420
Dus dat betekent dat n keer log n is
zeker beter dan n keer een andere

636
00:25:28,420 --> 00:25:30,390
n, AKA n kwadraat.

637
00:25:30,390 --> 00:25:32,400
En dat is wat we uiteindelijk voelen.

638
00:25:32,400 --> 00:25:34,928
>> Zo groot applaus, indien
we konden, voor deze jongens.

639
00:25:34,928 --> 00:25:38,920
>> [Applaus]

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: En je afscheid geschenken -
je kan houden van de nummers,

641
00:25:41,550 --> 00:25:44,010
als je zou willen.

642
00:25:44,010 --> 00:25:45,620
En je afscheidscadeau, zoals gewoonlijk.

643
00:25:45,620 --> 00:25:47,290
Oh, en we sturen u
de beelden, Michelle.

644
00:25:47,290 --> 00:25:48,343
Dank u.

645
00:25:48,343 --> 00:25:49,250
Oke.

646
00:25:49,250 --> 00:25:50,400
Help jezelf aan een stressbal.

647
00:25:50,400 --> 00:25:54,110
>> En laat mij trekken, in de tussentijd,
onze vriend Rob Bowden te bieden

648
00:25:54,110 --> 00:25:59,520
enigszins andere kijk op deze,
omdat je kunt denken over deze

649
00:25:59,520 --> 00:26:01,280
stappen gebeurt in een enigszins
andere manier.

650
00:26:01,280 --> 00:26:04,750
In feite is de set-up voor wat Rob gaat over
om ons te tonen ervan uit dat we hebben

651
00:26:04,750 --> 00:26:09,030
al gedaan de verdeling van de
grote lijst in acht kleine lijsten,

652
00:26:09,030 --> 00:26:10,570
elk van maat 1.

653
00:26:10,570 --> 00:26:13,350
>> Dus we veranderen de pseudocode een
beetje gewoon om een ​​soort van te krijgen op de

654
00:26:13,350 --> 00:26:15,320
kern idee van hoe het samenvoegen werkt.

655
00:26:15,320 --> 00:26:17,600
Maar de looptijd van wat
hij is ongeveer te doen is nog

656
00:26:17,600 --> 00:26:19,110
naar dezelfde te zijn.

657
00:26:19,110 --> 00:26:23,540
En nogmaals, de set-up hier is dat hij
begonnen met acht lijsten van grootte 1.

658
00:26:23,540 --> 00:26:27,730
Dus je hebt het deel waar hij is gemist
eigenlijk gedaan de log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
delen van het ingangssignaal.

660
00:26:31,205 --> 00:26:32,120
>> [VIDEO AFSPELEN]

661
00:26:32,120 --> 00:26:33,615
>> -Dat is het voor stap een.

662
00:26:33,615 --> 00:26:38,270
Voor stap twee, herhaaldelijk
samenvoegen paren van lijsten.

663
00:26:38,270 --> 00:26:39,210
>> DAVID Malan: Hm.

664
00:26:39,210 --> 00:26:41,270
Alleen audio komt eraan
uit mijn computer.

665
00:26:41,270 --> 00:26:42,520
Laten we proberen dit opnieuw.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Just willekeurig kiezen welke -
nu hebben we vier lijsten.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Leren voordat.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Daar gaan we.

671
00:26:53,040 --> 00:27:00,510
>> -Samenvoegen 108 en 15, eindigen we
met de lijst 15, 108.

672
00:27:00,510 --> 00:27:07,170
Samenvoegen 50 en 4, we
eindigen met 4, 50.

673
00:27:07,170 --> 00:27:12,990
Samenvoegen van 8 en 42, we
eindigen met 8, 42.

674
00:27:12,990 --> 00:27:19,970
En samenvoegen 23 en 16, we
eindigen met 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Nu al onze lijsten zijn van grootte 2.

676
00:27:23,270 --> 00:27:26,690
Merk op dat elk van de
vier lijsten wordt gesorteerd.

677
00:27:26,690 --> 00:27:29,450
Zodat we kunnen beginnen met het samenvoegen
paren van lijsten weer.

678
00:27:29,450 --> 00:27:38,420
Samenvoegen 15 en 108 en 4 en 50, we
eerst neemt de 4, dan is het 15, dan

679
00:27:38,420 --> 00:27:41,500
de 50, dan 108.

680
00:27:41,500 --> 00:27:50,610
Samenvoegen van 8, 42 en 16, 23, nemen we eerst
De 8, dan is de 16 dan de 23,

681
00:27:50,610 --> 00:27:52,700
dan de 42.

682
00:27:52,700 --> 00:27:57,600
>> Dus nu hebben we slechts twee lijsten van omvang
4, die elk gesorteerd.

683
00:27:57,600 --> 00:28:01,170
Dus nu we samenvoegen van deze twee lijsten.

684
00:28:01,170 --> 00:28:11,835
Eerst nemen we de 4, dan nemen we de
8, dan nemen we de 15, dan 16, dan

685
00:28:11,835 --> 00:28:19,456
23, dan 42, dan 50, dan 108.

686
00:28:19,456 --> 00:28:19,872
>> [END VIDEO AFSPELEN]

687
00:28:19,872 --> 00:28:23,430
>> DAVID MALAN: Nogmaals, aankondiging, hij nooit
raakte een gegeven cup meer dan een keer

688
00:28:23,430 --> 00:28:24,860
na oprukkende daarbuiten.

689
00:28:24,860 --> 00:28:26,200
Dus hij is nooit te herhalen.

690
00:28:26,200 --> 00:28:29,850
Dus hij is altijd in beweging naar de zijkant,
en dat is waar we onze n.

691
00:28:29,850 --> 00:28:33,290
>> Waarom laat me omhoog te trekken een animatie
dat we eerder zagen, maar deze keer

692
00:28:33,290 --> 00:28:35,110
alleen gericht op merge sort.

693
00:28:35,110 --> 00:28:38,030
Laat me ga je gang en zoomen
op deze hier.

694
00:28:38,030 --> 00:28:42,530
Laat me eerst kiezen voor een willekeurige ingang,
vergroot deze, en u kunt sorteren van zien

695
00:28:42,530 --> 00:28:46,600
wat we vanzelfsprekend vonden, eerder,
merge sort is werkelijk te doen.

696
00:28:46,600 --> 00:28:50,330
>> Dus merken dat je deze helften of
deze wijken of deze achtste van de

697
00:28:50,330 --> 00:28:53,140
probleem dat ineens
beginnen om een ​​goede vorm te krijgen.

698
00:28:53,140 --> 00:28:57,070
En dan tot slot, zie je bij
het einde dat bam,

699
00:28:57,070 --> 00:28:58,860
alles is samengevoegd.

700
00:28:58,860 --> 00:29:01,690
>> Dus dit zijn slechts drie verschillende
neemt hetzelfde idee.

701
00:29:01,690 --> 00:29:05,980
Maar het belangrijkste inzicht, net als divide
en veroveren in de eerste klasse,

702
00:29:05,980 --> 00:29:10,640
was dat we besloten om een ​​of andere manier te verdelen
het probleem in iets groots, in

703
00:29:10,640 --> 00:29:14,760
iets soort identiek in de geest,
maar kleiner en kleiner

704
00:29:14,760 --> 00:29:15,660
en kleiner.

705
00:29:15,660 --> 00:29:18,420
>> Nu nog een leuke manier om een ​​soort van denken
over deze, ook al is het niet

706
00:29:18,420 --> 00:29:20,520
ga je dezelfde intuïtieve
begrip, is

707
00:29:20,520 --> 00:29:21,640
de volgende animatie.

708
00:29:21,640 --> 00:29:25,400
Dus dit is een video iemand in elkaar gezet
die verschillende bijbehorende

709
00:29:25,400 --> 00:29:29,970
geluiden met de verschillende activiteiten voor
insertion sort, voor merge sort, en

710
00:29:29,970 --> 00:29:31,150
voor een paar anderen.

711
00:29:31,150 --> 00:29:32,330
Dus in een moment, ik ga Play raken.

712
00:29:32,330 --> 00:29:33,600
Het is ongeveer een minuut lang.

713
00:29:33,600 --> 00:29:37,410
En hoewel je nog steeds kunt zien de
patronen gebeurt, dit keer kun je

714
00:29:37,410 --> 00:29:41,420
ook horen hoe deze algoritmen zijn
anders en met het uitvoeren van

715
00:29:41,420 --> 00:29:43,950
enigszins verschillende patronen.

716
00:29:43,950 --> 00:29:45,830
>> Dit is insertion sort.

717
00:29:45,830 --> 00:29:50,400
>> [TONEN AFSPELEN]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Het weer is proberen
aan elk element invoegen

719
00:29:52,400 --> 00:29:52,900
naar waar het hoort.

720
00:29:52,900 --> 00:29:54,628
Dit is bubble sort.

721
00:29:54,628 --> 00:30:10,097
>> [TONEN AFSPELEN]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: En u kunt sorteren van gevoel
hoe relatief weinig werk het doet

723
00:30:13,630 --> 00:30:15,834
op elke stap.

724
00:30:15,834 --> 00:30:20,470
Dit is wat verveling klinkt.

725
00:30:20,470 --> 00:30:21,472
>> [TONEN AFSPELEN]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Dit is selectie sorteren,
waar we selecteert u het element willen we door

727
00:30:25,222 --> 00:30:28,845
doorlopen en opnieuw en opnieuw
en zetten het in het begin.

728
00:30:28,845 --> 00:30:37,674
>> [TONEN AFSPELEN]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Dit is merge sort, die
kan je echt beginnen te voelen.

730
00:30:43,970 --> 00:30:51,810
>> [TONEN AFSPELEN]

731
00:30:51,810 --> 00:30:54,770
>> [Lachen]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Iets genaamd gnome
soort, die we niet hebben gekeken.

733
00:30:58,395 --> 00:31:13,630
>> [TONEN AFSPELEN]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Dus laat me zien, nu,
afgeleid zoals je hopelijk zijn door de

735
00:31:17,910 --> 00:31:21,110
muziek, als ik een beetje kan glijden
beetje wiskunde in hier.

736
00:31:21,110 --> 00:31:24,850
Dus er is een vierde manier die we kunnen
denken over wat het betekent deze

737
00:31:24,850 --> 00:31:29,210
functies om sneller dan degenen zijn
dat we al eerder gezien.

738
00:31:29,210 --> 00:31:32,470
En als je komt in de loop van
een wiskunde achtergrond, je

739
00:31:32,470 --> 00:31:36,030
eigenlijk weet misschien al dat je
kan een term klap op deze techniek -

740
00:31:36,030 --> 00:31:40,400
namelijk recursie, een functie
dat een of andere manier noemt zichzelf.

741
00:31:40,400 --> 00:31:44,780
>> En nogmaals, herinneren dat merge sort
pseudocode was recursieve in de zin

742
00:31:44,780 --> 00:31:48,460
dat een van de stappen merge sort's
was te sorteren noemen -

743
00:31:48,460 --> 00:31:49,740
dat is, zelf.

744
00:31:49,740 --> 00:31:52,480
Maar gelukkig, want we hielden
bellen sorteren of samenvoegen sorteren,

745
00:31:52,480 --> 00:31:55,880
specifiek, op een steeds kleinere
en kleinere lijst, we uiteindelijk

746
00:31:55,880 --> 00:32:00,005
dieptepunt dankzij wat wij zullen noemen
een basisscenario, de hard-coded geval dat

747
00:32:00,005 --> 00:32:04,270
zei dat als de lijst is klein, minder dan 2
in dat geval gewoon direct terug.

748
00:32:04,270 --> 00:32:07,550
Als we niet hebben dat speciaal geval, de
algoritme zou nooit bodem uit,

749
00:32:07,550 --> 00:32:11,010
en je zou inderdaad krijgen in een
oneindige lus echt voor altijd.

750
00:32:11,010 --> 00:32:14,330
>> Maar stel dat we wilden nu zetten
sommige nummers op dit, opnieuw, met behulp van n

751
00:32:14,330 --> 00:32:15,660
de grootte van de ingang.

752
00:32:15,660 --> 00:32:18,680
En ik wilde u vragen, wat is
de totale tijd die betrokken zijn bij

753
00:32:18,680 --> 00:32:19,800
lopende merge sort?

754
00:32:19,800 --> 00:32:22,960
Of meer in het algemeen, wat is
de kosten in tijd?

755
00:32:22,960 --> 00:32:24,730
>> Nou het is vrij eenvoudig te meten dat.

756
00:32:24,730 --> 00:32:29,010
Als n kleiner is dan 2, de tijd die
in het sorteren van n elementen,

757
00:32:29,010 --> 00:32:30,480
waarin n 2 is 0.

758
00:32:30,480 --> 00:32:31,410
Omdat we gewoon terug.

759
00:32:31,410 --> 00:32:32,510
Er is geen werk te doen.

760
00:32:32,510 --> 00:32:35,660
Nu misschien wel, misschien is het een stap of twee
stappen te achterhalen van de hoeveelheid

761
00:32:35,660 --> 00:32:38,420
werken, maar het is dicht genoeg bij 0 dat
Ik ga gewoon zeggen dat geen werk is

762
00:32:38,420 --> 00:32:40,940
vereist als de lijst is zo klein
worden oninteressant.

763
00:32:40,940 --> 00:32:42,580
>> Maar dit geval is interessant.

764
00:32:42,580 --> 00:32:47,320
Het recursieve geval was de tak van
de pseudocode die anders al zei, sorteren

765
00:32:47,320 --> 00:32:52,000
de linkerhelft, sorteren rechts
helft, fuseren de twee helften.

766
00:32:52,000 --> 00:32:55,530
Nu waarom doet deze uitdrukking
vertegenwoordigen dat kosten?

767
00:32:55,530 --> 00:32:58,690
Nou, T van n betekent alleen de
tijd om n elementen te sorteren.

768
00:32:58,690 --> 00:33:03,070
En dan aan de rechterzijde van de
gelijk-teken daar, de T van n verdeeld

769
00:33:03,070 --> 00:33:06,600
met 2 verwijst naar de kosten van wat?

770
00:33:06,600 --> 00:33:07,570
Het sorteren van de linkerhelft.

771
00:33:07,570 --> 00:33:10,990
De andere T n gedeeld door 2 is
waarschijnlijk verwijst naar de kosten

772
00:33:10,990 --> 00:33:12,390
sorteren van de rechterhelft.

773
00:33:12,390 --> 00:33:14,590
>> En dan de plus n?

774
00:33:14,590 --> 00:33:15,420
Wordt de samenvoeging.

775
00:33:15,420 --> 00:33:19,120
Want als je twee lijsten, een van
size n meer dan 2 en een ander van grootte n

776
00:33:19,120 --> 00:33:22,580
meer dan 2, moet je wezen raken
elk van deze elementen, net als Rob

777
00:33:22,580 --> 00:33:24,990
aangeraakt elk van de cups, en gewoon
zoals we reeds bij elk van de

778
00:33:24,990 --> 00:33:26,310
vrijwilligers op het podium.

779
00:33:26,310 --> 00:33:28,790
Dus n is ten koste van het samenvoegen.

780
00:33:28,790 --> 00:33:31,780
>> Nu helaas, deze formule
Ook zelf recursief.

781
00:33:31,780 --> 00:33:36,390
Dus als de vraag, als n, zeg,
16, als er 16 mensen op het podium

782
00:33:36,390 --> 00:33:40,670
of 16 bekers in de video, hoeveel totaal
stappen duurt het om ze te sorteren

783
00:33:40,670 --> 00:33:41,550
met merge sort?

784
00:33:41,550 --> 00:33:45,790
Het is eigenlijk niet een duidelijk antwoord,
want nu heb je om een ​​soort van

785
00:33:45,790 --> 00:33:48,500
recursief antwoord op deze formule.

786
00:33:48,500 --> 00:33:51,190
>> Maar dat is OK, want laat me voorstellen
dat we het volgende doen.

787
00:33:51,190 --> 00:33:56,670
De tijd die gemoeid is met 16 personen sorteren of
16 cups zal worden vertegenwoordigd

788
00:33:56,670 --> 00:33:58,020
algemeen als T 16.

789
00:33:58,020 --> 00:34:01,400
Maar dat gelijk, volgens onze
previous formule 2 keer de hoeveelheid

790
00:34:01,400 --> 00:34:04,780
van de tijd die het kost om te sorteren
8 kopjes plus 16.

791
00:34:04,780 --> 00:34:08,590
En nogmaals, plus 16 is het tijd om te fuseren,
en tweemaal T 8 is de

792
00:34:08,590 --> 00:34:10,790
tijd om linkerhelft en rechterhelft te sorteren.

793
00:34:10,790 --> 00:34:11,989
>> Maar nogmaals, dit is niet genoeg.

794
00:34:11,989 --> 00:34:13,210
We hebben om te duiken in dieper.

795
00:34:13,210 --> 00:34:16,409
Dit betekent dat we de antwoorden
vraag, wat is T van 8?

796
00:34:16,409 --> 00:34:19,610
Nou T van 8 ligt op slechts 2
tijden T van 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
Nou, wat is T van 4?

798
00:34:20,520 --> 00:34:23,780
T van 4 is slechts 2 keer T van 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
Nou, wat is T van 2?

800
00:34:25,489 --> 00:34:29,030
T van 2 is slechts 2 keer T van 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> En nogmaals, we zijn soort van krijgen
vast in deze cyclus.

802
00:34:31,940 --> 00:34:34,790
Maar het is over te raken dat
zogenaamde basisscenario.

803
00:34:34,790 --> 00:34:37,310
Want wat is T van 1, hebben we beweren?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Dus nu eindelijk, kunnen we terug te werken.

806
00:34:39,730 --> 00:34:44,290
>> Als T van 1 is 0, kan ik nu weer terug ga een
lijn om deze man hier, en ik kan

807
00:34:44,290 --> 00:34:46,330
plug in 0 voor T van 1.

808
00:34:46,330 --> 00:34:51,770
Dus dat betekent dat gelijk is aan 2 maal nul,
ook wel bekend als 0, plus 2.

809
00:34:51,770 --> 00:34:53,739
En dus dat hele uitdrukking is 2.

810
00:34:53,739 --> 00:34:58,740
>> Nu als ik de T van 2, waarvan het antwoord
is 2, steek hem in de middelste lijn, T

811
00:34:58,740 --> 00:35:02,740
van 4, dat geeft me 2 keer
2 plus 4, dus 8.

812
00:35:02,740 --> 00:35:07,080
Als ik vervolgens de stekker in 8 op de vorige
lijn, dat geeft me 2 keer 8, 16.

813
00:35:07,080 --> 00:35:12,470
En als we dan verder dat met de
24, het toevoegen van 16, eindelijk krijgen we een

814
00:35:12,470 --> 00:35:13,820
waarde van 64.

815
00:35:13,820 --> 00:35:18,480
>> Nu dat op zich soort spreekt
niets met de notatie n, de

816
00:35:18,480 --> 00:35:20,700
big O, de omega dat we hebben
het over.

817
00:35:20,700 --> 00:35:24,890
Maar het blijkt dat 64 inderdaad
16, de sterkte van het ingangssignaal,

818
00:35:24,890 --> 00:35:27,110
log basis 2 van 16.

819
00:35:27,110 --> 00:35:30,200
En als dit een beetje bekend, maar
denk terug, en het zal terugkomen

820
00:35:30,200 --> 00:35:30,700
tot je uiteindelijk.

821
00:35:30,700 --> 00:35:33,775
Als dit log base 2, het is net als 2
verhoogd tot het wat geeft je 16?

822
00:35:33,775 --> 00:35:36,380
Oh, dat is 4, dus het is 16 keer 4.

823
00:35:36,380 --> 00:35:39,380
>> En nogmaals, het is geen big deal als deze
is een soort van wazige herinnering nu.

824
00:35:39,380 --> 00:35:43,720
Maar voor nu, nemen op geloof
dat 16 log 16 is 64.

825
00:35:43,720 --> 00:35:46,590
En dus inderdaad, met deze eenvoudige gezond verstand
controleren, hebben we bevestigd -

826
00:35:46,590 --> 00:35:48,250
maar niet formeel bewezen -

827
00:35:48,250 --> 00:35:52,800
dat de looptijd van de merge
soort is inderdaad n log n.

828
00:35:52,800 --> 00:35:53,790
>> Dus niet slecht.

829
00:35:53,790 --> 00:35:57,260
Het is zeker beter dan de
algoritmen die we tot nu toe gezien, en

830
00:35:57,260 --> 00:36:00,710
het is omdat we leveraged, een,
een techniek genaamd recursie.

831
00:36:00,710 --> 00:36:03,880
Maar interessanter dan dat, dat
notie van het verdelen en veroveren.

832
00:36:03,880 --> 00:36:07,460
Nogmaals, echt week 0 spul dat
zelfs nu is terugkerend in een

833
00:36:07,460 --> 00:36:08,740
meer dwingende manier.

834
00:36:08,740 --> 00:36:11,750
>> Nu een leuke kleine oefening, als je hebt
nooit gedaan - en u waarschijnlijk

835
00:36:11,750 --> 00:36:14,660
niet, omdat soort normale
mensen denken niet om dit te doen.

836
00:36:14,660 --> 00:36:20,650
Maar als ik naar google.com en als
Ik wil iets leren over

837
00:36:20,650 --> 00:36:22,356
recursie, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Lachen]

840
00:36:29,058 --> 00:36:32,030
[Meer gelach]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Slechte grap langzaam verspreiden.

842
00:36:33,385 --> 00:36:34,450
[Lachen]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Just in case, het is er.

844
00:36:36,970 --> 00:36:38,710
Ik heb niet spellen het verkeerd,
en er is de grap.

845
00:36:38,710 --> 00:36:40,810
Oke.

846
00:36:40,810 --> 00:36:42,950
Uitleggen aan de mensen naast u als
het is niet helemaal klikte gewoon nog niet.

847
00:36:42,950 --> 00:36:47,650
Maar recursie, meer algemeen, verwijst
het proces van een functie oproepen

848
00:36:47,650 --> 00:36:51,430
zelf, of meer algemeen, splitsen van een
probleem in iets dat kan worden

849
00:36:51,430 --> 00:36:56,220
fragmentarisch opgelost door het oplossen van identieke
vertegenwoordiger van problemen.

850
00:36:56,220 --> 00:36:58,400
>> Nou, laten we verandering versnellingen
voor slechts een moment.

851
00:36:58,400 --> 00:37:00,840
We willen eindigen op bepaalde momenten van angst,
dus laten we beginnen op te zetten

852
00:37:00,840 --> 00:37:05,870
het podium, voor enkele minuten,
op een zeer eenvoudig idee -

853
00:37:05,870 --> 00:37:07,620
dat van ruilen twee elementen, toch?

854
00:37:07,620 --> 00:37:10,040
Al deze algoritmes we geweest
te praten over de afgelopen paar

855
00:37:10,040 --> 00:37:12,420
lezingen omvatten een aantal
soort swapping.

856
00:37:12,420 --> 00:37:14,630
Vandaag werd gevisualiseerd door ze te verkrijgen
op uit hun stoelen en

857
00:37:14,630 --> 00:37:18,570
rond te lopen, maar in de code, zouden we
neem dan gewoon een element van de ene array

858
00:37:18,570 --> 00:37:20,370
en plop in een ander.

859
00:37:20,370 --> 00:37:21,880
>> Dus hoe kunnen we dat doen?

860
00:37:21,880 --> 00:37:24,850
Nou, laat me ga je gang en schrijf
snel een programma hier.

861
00:37:24,850 --> 00:37:31,600
Ik ga om te gaan en te doen
dit als volgt.

862
00:37:31,600 --> 00:37:33,910
Laten we noemen dit -

863
00:37:33,910 --> 00:37:38,070
wat willen we met deze ene bellen?

864
00:37:38,070 --> 00:37:38,650
>> Eigenlijk niet.

865
00:37:38,650 --> 00:37:39,420
Laat me terug te spoelen.

866
00:37:39,420 --> 00:37:41,220
Ik wil niet dat doen
cliffhanger nog.

867
00:37:41,220 --> 00:37:42,270
Het zal de pret niet drukken.

868
00:37:42,270 --> 00:37:43,600
Laten we dit doen in plaats daarvan.

869
00:37:43,600 --> 00:37:47,430
>> Stel dat ik wil een beetje schrijven
programma en die omarmt nu dit

870
00:37:47,430 --> 00:37:48,700
idee van recursie.

871
00:37:48,700 --> 00:37:50,370
Ik soort heb er voor mezelf.

872
00:37:50,370 --> 00:37:51,420
Ik ga het volgende doen.

873
00:37:51,420 --> 00:38:00,220
>> Ten eerste, een snelle bevatten standaard io.H,
alsmede een include van cs50.h.

874
00:38:00,220 --> 00:38:03,200
En dan ga ik om verder te gaan
en verklaren int main nietig

875
00:38:03,200 --> 00:38:04,360
op de gebruikelijke wijze.

876
00:38:04,360 --> 00:38:07,920
Ik besefte dat ik heb het bestand verkeerde naam, dus
laat ik voeg gewoon een. c extensie hier dus

877
00:38:07,920 --> 00:38:09,510
dat we het goed kunnen compileren.

878
00:38:09,510 --> 00:38:10,970
Start deze functie uit.

879
00:38:10,970 --> 00:38:13,290
>> En de functie ik wil schrijven, heel
gewoon, is er een die vraagt ​​de

880
00:38:13,290 --> 00:38:16,210
gebruiker voor een nummer en vervolgens opgeteld
alle nummers tussen die

881
00:38:16,210 --> 00:38:19,920
nummer en, zeg, 0.

882
00:38:19,920 --> 00:38:22,510
Dus eerst ga ik verder te gaan
en verklaren int n.

883
00:38:22,510 --> 00:38:24,760
Kopieer dan heb ik wat code die
we hebben gebruikt voor een tijdje.

884
00:38:24,760 --> 00:38:26,660
Terwijl er iets is waar.

885
00:38:26,660 --> 00:38:28,000
Ik kom terug naar die komen in een moment.

886
00:38:28,000 --> 00:38:29,010
>> Wat wil ik doen?

887
00:38:29,010 --> 00:38:33,460
Ik wil printf positiefs te zeggen
integer alsjeblieft.

888
00:38:33,460 --> 00:38:36,130
En dan ga ik
Zeg n krijgt krijgen int.

889
00:38:36,130 --> 00:38:38,800
Dus nogmaals, sommige standaardtekst code
dat we eerder hebben gebruikt.

890
00:38:38,800 --> 00:38:40,810
En ik ga dit doen
terwijl n kleiner is dan 1.

891
00:38:40,810 --> 00:38:44,120
Dus dit zal ervoor zorgen dat de gebruiker
geeft mij een positief geheel getal.

892
00:38:44,120 --> 00:38:45,490
>> En nu ga ik het volgende doen.

893
00:38:45,490 --> 00:38:51,020
Ik wil optellen alle nummers
1 tot en n of 0 en n,

894
00:38:51,020 --> 00:38:52,570
equivalent, met het totaal bedrag te krijgen.

895
00:38:52,570 --> 00:38:55,100
Dus de grote sigma symbool
dat je zou herinneren.

896
00:38:55,100 --> 00:38:59,050
Dus ik ga dit doen door eerst te bellen
een functie genaamd sigma,

897
00:38:59,050 --> 00:39:06,030
het passeren van het in n, en dan ga ik
zeggen printf, het antwoord is daar.

898
00:39:06,030 --> 00:39:08,180
>> Dus in het kort, krijg ik en
int van de gebruiker.

899
00:39:08,180 --> 00:39:09,280
Ik zorg ervoor dat het positieve.

900
00:39:09,280 --> 00:39:12,700
Ik verklaar een variabele genaamd antwoord van
type int en op te slaan in het het rendement

901
00:39:12,700 --> 00:39:15,610
waarde van sigma, passeren in n als invoer.

902
00:39:15,610 --> 00:39:17,060
En dan print ik dat antwoord.

903
00:39:17,060 --> 00:39:19,550
>> Helaas, alhoewel sigma klinkt
als iets dat zou kunnen zijn in

904
00:39:19,550 --> 00:39:24,040
het math.h bestand, zijn verklaring,
het is eigenlijk niet.

905
00:39:24,040 --> 00:39:24,690
Dus dat is OK.

906
00:39:24,690 --> 00:39:26,170
Ik kan dit zelf uitvoeren.

907
00:39:26,170 --> 00:39:29,160
Ik ga een functie genaamd implementeren
sigma, en het gaat om een ​​te nemen

908
00:39:29,160 --> 00:39:29,900
parameter -

909
00:39:29,900 --> 00:39:32,100
laten we noemen het m, net
dus het is anders.

910
00:39:32,100 --> 00:39:35,910
En dan hier, ik ga zeggen,
goed, indien m kleiner dan 1 - Dit is een

911
00:39:35,910 --> 00:39:38,180
zeer oninteressant programma.

912
00:39:38,180 --> 00:39:41,700
Dus ik ga om verder te gaan en
onmiddellijk 0 terug.

913
00:39:41,700 --> 00:39:45,920
Het heeft gewoon geen zin om optellen maken allemaal
de getallen tussen 1 en m als m

914
00:39:45,920 --> 00:39:48,470
is zelf 0 of negatief is.

915
00:39:48,470 --> 00:39:50,900
>> En dan ga ik om verder te gaan
en dit doet zeer iteratief.

916
00:39:50,900 --> 00:39:53,090
Ik ga dit soort old-school te doen,
en ik ga om verder te gaan

917
00:39:53,090 --> 00:39:57,150
en zeggen dat ik ga
verklaren een bedrag te zijn 0.

918
00:39:57,150 --> 00:39:59,630
Dan ga ik hebben
een lus van int -

919
00:39:59,630 --> 00:40:02,820
en laat mij het doen om onze wedstrijd
verdeelsleutel, dus je hebt een kopie

920
00:40:02,820 --> 00:40:07,500
thuis. int i krijgt 1 op maximaal
i kleiner is dan of gelijk aan m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
En dan de binnenkant van deze for loop -

923
00:40:11,430 --> 00:40:12,440
we zijn er bijna -

924
00:40:12,440 --> 00:40:15,810
sum krijgt sum plus 1.

925
00:40:15,810 --> 00:40:17,670
En dan ga ik aan de som terug te keren.

926
00:40:17,670 --> 00:40:19,420
>> Dus ik deed dit snel,
heel toegegeven.

927
00:40:19,420 --> 00:40:22,775
Maar nogmaals, de belangrijkste functie is vrij
ongecompliceerd, gebaseerd op code die we hebben

928
00:40:22,775 --> 00:40:23,190
tot nu toe geschreven.

929
00:40:23,190 --> 00:40:25,610
Maakt gebruik van de dubbele lus om een ​​positieve krijgen
int van de gebruiker.

930
00:40:25,610 --> 00:40:29,870
Toen ik pas dat int naar een nieuwe functie
genaamd sigma, noemde het, nogmaals, n.

931
00:40:29,870 --> 00:40:33,100
En ik bewaar de return waarde, het antwoord
uit de zwarte doos momenteel

932
00:40:33,100 --> 00:40:35,460
bekend als sigma, in een variabele
riep antwoord.

933
00:40:35,460 --> 00:40:36,580
Dan print ik het.

934
00:40:36,580 --> 00:40:39,090
>> Als we nu verder het verhaal,
hoe wordt sigma geïmplementeerd?

935
00:40:39,090 --> 00:40:40,840
Ik stel voor om te implementeren als volgt.

936
00:40:40,840 --> 00:40:43,560
Eerst een beetje foutcontrole
om ervoor te zorgen dat de gebruiker niet

937
00:40:43,560 --> 00:40:46,480
knoeien met mij en passeren in
aantal negatieve of 0 waarde.

938
00:40:46,480 --> 00:40:49,710
Dan verklaar ik een variabele genaamd
samenvatten en zet deze op 0.

939
00:40:49,710 --> 00:40:55,910
>> En nu begin ik te verhuizen van i gelijk
1 helemaal tot en met m,

940
00:40:55,910 --> 00:41:00,130
want ik wil alle bevatten
getallen van een tot en met m, inclusief.

941
00:41:00,130 --> 00:41:04,350
En binnenkant van deze for loop, ik doe
sum krijgt wat het nu is, plus de

942
00:41:04,350 --> 00:41:08,900
waarde van i.

943
00:41:08,900 --> 00:41:10,370
Plus de waarde van i.

944
00:41:10,370 --> 00:41:14,090
>> Even terzijde, als je dit niet hebt gezien
eerder, is er een aantal syntactische suiker

945
00:41:14,090 --> 00:41:14,870
voor deze lijn.

946
00:41:14,870 --> 00:41:21,120
Ik kan dit herschrijven als plus evenaart i,
alleen maar om mezelf te redden een paar toetsaanslagen

947
00:41:21,120 --> 00:41:22,570
en kijken een beetje koeler.

948
00:41:22,570 --> 00:41:23,140
Maar dat is alles.

949
00:41:23,140 --> 00:41:24,660
Het is functioneel hetzelfde.

950
00:41:24,660 --> 00:41:26,710
>> Helaas is deze code's
niet van plan nog te compileren.

951
00:41:26,710 --> 00:41:31,600
Als ik te maken sigma 0, hoe ben
Ik ga krijgen schreeuwde?

952
00:41:31,600 --> 00:41:33,473
Wat gaat het niet vinden?

953
00:41:33,473 --> 00:41:35,740
>> PUBLIEK: [onverstaanbaar].

954
00:41:35,740 --> 00:41:37,800
>> DAVID MALAN: Ja, heb ik niet verklaren
de functie tot boven, toch?

955
00:41:37,800 --> 00:41:40,590
C is een beetje dom, omdat het alleen
doet wat je vertellen dat het te doen, en je

956
00:41:40,590 --> 00:41:41,880
moeten het doen in die volgorde.

957
00:41:41,880 --> 00:41:45,910
En dus als ik druk op Enter hier, ik ga
krijg een waarschuwing over sigma impliciete

958
00:41:45,910 --> 00:41:46,860
verklaring.

959
00:41:46,860 --> 00:41:48,120
>> Oh, geen probleem.

960
00:41:48,120 --> 00:41:50,370
Ik kan gaan tot de top, en ik kan
zeggen, oke, wacht even.

961
00:41:50,370 --> 00:41:54,240
Sigma is een functie die terugkeert
een int en verwacht een

962
00:41:54,240 --> 00:41:56,620
int als input, puntkomma.

963
00:41:56,620 --> 00:41:59,550
Of ik kon de hele functie gezet
boven de belangrijkste, maar in het algemeen, zou ik

964
00:41:59,550 --> 00:42:02,260
afraden dat, want het is
leuk om altijd de belangrijkste aan de top dus

965
00:42:02,260 --> 00:42:06,310
kunt u rechts in duiken en weten wat een
programma doet bij eerste lezing belangrijkste.

966
00:42:06,310 --> 00:42:07,930
>> Dus nu laat ik het scherm te wissen.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Alles lijkt uit te checken.

969
00:42:10,340 --> 00:42:11,970
Laat me sigma 0 draaien.

970
00:42:11,970 --> 00:42:12,770
Positieve inter.

971
00:42:12,770 --> 00:42:15,580
Ik geef het aantal
3 om het simpel te houden.

972
00:42:15,580 --> 00:42:18,710
Zodat ik moet geven 3
plus 2 plus 1, dus 6.

973
00:42:18,710 --> 00:42:20,750
Enter, en inderdaad krijg ik 6.

974
00:42:20,750 --> 00:42:21,820
>> Ik kan iets groters doen -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Net als een tangent, ga ik doen
iets belachelijks als een echt grote

977
00:42:27,690 --> 00:42:30,375
nummer, Oh, dat werkte eigenlijk -

978
00:42:30,375 --> 00:42:31,600
eh, ik denk niet dat dat klopt.

979
00:42:31,600 --> 00:42:32,810
Laten we eens kijken.

980
00:42:32,810 --> 00:42:34,060
Laten we echt knoeien met het.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Dat is een probleem.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Wat is er gaande?

985
00:42:44,970 --> 00:42:46,050
De code is niet zo slecht.

986
00:42:46,050 --> 00:42:48,470
Het is nog steeds lineair.

987
00:42:48,470 --> 00:42:50,810
Fluiten is een goed effect, dat wel.

988
00:42:50,810 --> 00:42:52,060
Wat is er gaande?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Niet zeker of ik het hoorde.

991
00:42:55,620 --> 00:42:57,620
Dus het blijkt - en
Dit is als een terzijde.

992
00:42:57,620 --> 00:42:59,400
Dit is niet de kern van de
idee van recursie.

993
00:42:59,400 --> 00:43:02,480
Het blijkt, want ik ben op zoek naar
vertegenwoordigen zo'n groot aantal, meest

994
00:43:02,480 --> 00:43:06,980
waarschijnlijk het wordt verkeerd geïnterpreteerd
door C als niet positief getal,

995
00:43:06,980 --> 00:43:09,980
maar negatief getal.

996
00:43:09,980 --> 00:43:12,690
>> We hebben nog niet gesproken over deze, maar het
blijkt dat er negatieve getallen

997
00:43:12,690 --> 00:43:14,210
in de wereld naast
positieve getallen.

998
00:43:14,210 --> 00:43:16,290
En de wijze waarop u kunt
vertegenwoordigen een negatief getal

999
00:43:16,290 --> 00:43:19,530
in wezen een is, gebruikt u
speciale bit om aan te geven

1000
00:43:19,530 --> 00:43:20,400
positieve dan negatieve.

1001
00:43:20,400 --> 00:43:22,950
Het is een beetje ingewikkelder dan dat,
maar dat is het basisidee.

1002
00:43:22,950 --> 00:43:26,740
>> Dus helaas, als C is verwarrend ene
van die stukjes als werkelijk betekenis,

1003
00:43:26,740 --> 00:43:30,790
oh, dit is een negatief getal, mijn lus
Hier, bijvoorbeeld, eigenlijk nooit

1004
00:43:30,790 --> 00:43:31,740
gaat beëindigen.

1005
00:43:31,740 --> 00:43:33,850
Dus als ik daadwerkelijk iets af te drukken
opnieuw en opnieuw, we zouden

1006
00:43:33,850 --> 00:43:34,650
zie een heleboel.

1007
00:43:34,650 --> 00:43:36,220
Maar nogmaals, dit is naast het punt.

1008
00:43:36,220 --> 00:43:38,590
Dit is eigenlijk gewoon een soort van
intellectuele nieuwsgierigheid dat we komen

1009
00:43:38,590 --> 00:43:39,550
uiteindelijk terug.

1010
00:43:39,550 --> 00:43:43,400
Maar voor nu, dit is een correcte
implementatie als we aannemen dat de

1011
00:43:43,400 --> 00:43:45,970
gebruiker zal ints bieden
die passen binnen ints.

1012
00:43:45,970 --> 00:43:49,370
>> Maar ik beweren dat deze code, eerlijk gezegd,
kon zo veel meer eenvoudig worden gedaan.

1013
00:43:49,370 --> 00:43:54,060
Als het doel bij de hand is om een ​​aantal te nemen
zoals m en tel al van de

1014
00:43:54,060 --> 00:43:59,510
getallen tussen het en 1, of omgekeerd
tussen 1 en het, beweren I

1015
00:43:59,510 --> 00:44:03,380
dat ik dit idee dat fuseren kunt lenen
sort had, dat was het nemen van een probleem

1016
00:44:03,380 --> 00:44:05,660
van deze omvang en verdelen
in iets kleinere.

1017
00:44:05,660 --> 00:44:09,875
Misschien niet de helft, maar kleiner, maar
representatieve hetzelfde.

1018
00:44:09,875 --> 00:44:12,130
Hetzelfde idee, maar een kleiner probleem.

1019
00:44:12,130 --> 00:44:15,470
>> Dus ik ben eigenlijk - laat ik dit bestand op te slaan
met een ander versienummer.

1020
00:44:15,470 --> 00:44:17,670
We zullen deze versie noemen
1 in plaats van 0.

1021
00:44:17,670 --> 00:44:20,790
En ik beweer dat ik kan eigenlijk
herimplementeren deze in dit soort

1022
00:44:20,790 --> 00:44:22,160
breinbrekende weg.

1023
00:44:22,160 --> 00:44:23,710
>> Ik ga alleen een deel van het te verlaten.

1024
00:44:23,710 --> 00:44:27,710
Ik ga zeggen als m minder
dan of gelijk aan 0 -

1025
00:44:27,710 --> 00:44:29,280
Ik ga gewoon een beetje te zijn
meer anale deze tijd

1026
00:44:29,280 --> 00:44:30,520
met mijn foutcontrole -

1027
00:44:30,520 --> 00:44:33,190
Ik ga om te gaan en terug te keren 0.

1028
00:44:33,190 --> 00:44:34,490
Dit is willekeurig.

1029
00:44:34,490 --> 00:44:37,500
Ik ben gewoon de beslissing of de gebruiker
geeft me een negatief getal, ik ben

1030
00:44:37,500 --> 00:44:41,490
terug 0, en ze moeten hebben gelezen
de documentatie nauwer.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
merken wat ik ga doen.

1033
00:44:44,070 --> 00:44:49,260
Anders ga ik terug m plus -

1034
00:44:49,260 --> 00:44:51,010
wat sigma van m?

1035
00:44:51,010 --> 00:44:56,710
Nou, sigma van m plus m minus 1,
plus minus m 2, plus m minus 3.

1036
00:44:56,710 --> 00:44:58,030
Ik wil niet dat alles uit te schrijven.

1037
00:44:58,030 --> 00:44:59,120
Waarom doe ik niet gewoon punter?

1038
00:44:59,120 --> 00:45:05,080
Recursief noem mezelf met een iets
kleiner probleem, puntkomma,

1039
00:45:05,080 --> 00:45:06,840
en noemen het een dag?

1040
00:45:06,840 --> 00:45:07,040
>> Rechts?

1041
00:45:07,040 --> 00:45:10,980
Nu ook hier, je zou voelen of zorgen
dat dit een oneindige lus, dat ben ik

1042
00:45:10,980 --> 00:45:15,450
inducerende, waarbij ik ben de uitvoering
sigma door te bellen naar sigma.

1043
00:45:15,450 --> 00:45:20,342
Maar dat is perfect OK, want ik
dacht vooruit een toegevoegde welke lijnen?

1044
00:45:20,342 --> 00:45:22,600
>> PUBLIEK: [onverstaanbaar].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23 tot 26, die
is mijn als voorwaarde.

1046
00:45:25,430 --> 00:45:28,390
Want wat er leuk is aan de
aftrekken hier, want ik houd

1047
00:45:28,390 --> 00:45:31,180
overdracht sigma kleinere problemen, kleiner
problemen, kleinere - het is niet

1048
00:45:31,180 --> 00:45:31,870
half zo groot.

1049
00:45:31,870 --> 00:45:34,380
Het is slechts een baby stap kleiner,
maar dat is OK.

1050
00:45:34,380 --> 00:45:38,050
Want uiteindelijk zullen we werken
onze weg naar 1 of 0.

1051
00:45:38,050 --> 00:45:41,630
En als we eenmaal geraakt 0, sigma is niet
gaat zich meer noemen.

1052
00:45:41,630 --> 00:45:43,590
Het gaat om direct 0 keren.

1053
00:45:43,590 --> 00:45:47,960
>> Dus het effect, als je soort van wind deze
in je geest, is het m plus voegen

1054
00:45:47,960 --> 00:45:52,740
m minus 1, plus m minus 2, plus m minus
3, plus puntje, puntje, puntje, m minus

1055
00:45:52,740 --> 00:45:57,820
m, uiteindelijk geef je 0, en de
effect uiteindelijk alle voegen

1056
00:45:57,820 --> 00:45:59,070
deze dingen samen.

1057
00:45:59,070 --> 00:46:02,380
We hebben dus niet, met recursie,
het probleem opgelost dat we

1058
00:46:02,380 --> 00:46:03,470
kon niet op te lossen voordat.

1059
00:46:03,470 --> 00:46:06,840
Inderdaad, deze versie 0 en elke
probleem tot op heden, is oplosbaar geweest

1060
00:46:06,840 --> 00:46:09,980
met alleen het gebruik van loops of tijdens
lussen of soortgelijke constructen.

1061
00:46:09,980 --> 00:46:13,150
>> Maar recursie, ik durf te zeggen, geeft ons
een andere manier van denken over

1062
00:46:13,150 --> 00:46:17,010
problemen, waarbij als we kunnen nemen een
probleem, het verdelen van iets

1063
00:46:17,010 --> 00:46:22,340
enigszins groot in iets wat
kleiner, ik beweer dat we het kunnen oplossen

1064
00:46:22,340 --> 00:46:26,040
misschien een beetje meer elegant in termen
van het ontwerp, met minder code,

1065
00:46:26,040 --> 00:46:30,980
en misschien zelfs oplossen van problemen die zouden
moeilijker, want we zullen uiteindelijk

1066
00:46:30,980 --> 00:46:33,280
zie, het oplossen van louter iteratief.

1067
00:46:33,280 --> 00:46:35,980
>> Maar de cliffhanger die ik deed
wil ons verlaten op was dit.

1068
00:46:35,980 --> 00:46:40,720
Laat me ga je gang en open
een bestand van -

1069
00:46:40,720 --> 00:46:44,300
eigenlijk, laat me gaan en
doe dit echt snel.

1070
00:46:44,300 --> 00:46:46,875
Laat ik verder gaan en stellen
de volgende.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Onder de code van vandaag is hier dit bestand.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Deze hier, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Dus dit is een stomme kleine programma dat
Ik opgezweept die aanspraken te doen

1076
00:47:06,260 --> 00:47:06,940
de volgende.

1077
00:47:06,940 --> 00:47:10,140
In de belangrijkste, voor het eerst verklaart een
int genaamd x en wijst deze

1078
00:47:10,140 --> 00:47:11,100
de waarde 1.

1079
00:47:11,100 --> 00:47:13,520
Dan verklaart het een int y en
wijst deze de waarde 2.

1080
00:47:13,520 --> 00:47:15,310
Dan print het uit wat x en y.

1081
00:47:15,310 --> 00:47:17,781
Dan zegt hij, ruilen, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Dan het beweert een functie te bellen
riep swap, passeren in x en

1083
00:47:21,670 --> 00:47:24,290
y, het idee heeft dat hopelijk
x en y zal terugkomen

1084
00:47:24,290 --> 00:47:25,620
anders, het tegenovergestelde.

1085
00:47:25,620 --> 00:47:27,110
Dan het te claimen geruild!

1086
00:47:27,110 --> 00:47:28,420
met een uitroepteken.

1087
00:47:28,420 --> 00:47:30,190
Dan print het uit x en y.

1088
00:47:30,190 --> 00:47:33,480
>> Maar het blijkt dat deze zeer
eenvoudige demonstratie neer

1089
00:47:33,480 --> 00:47:35,570
hier eigenlijk buggy.

1090
00:47:35,570 --> 00:47:38,870
Hoewel ik ben waarbij een tijdelijke
variabel en tijdelijk zetten een in

1091
00:47:38,870 --> 00:47:42,010
het, dan ben ik opnieuw toewijzen
een waarde van m. -

1092
00:47:42,010 --> 00:47:45,080
die redelijk voelt, want ik heb
opgeslagen een kopie van een in temp.

1093
00:47:45,080 --> 00:47:48,410
Toen ik b updaten om gelijke
wat was in temp.

1094
00:47:48,410 --> 00:47:51,610
Dit soort shell game van het verplaatsen van een
in b en b in een met behulp van deze

1095
00:47:51,610 --> 00:47:54,360
middle-man genaamd temp voelt
heel redelijk.

1096
00:47:54,360 --> 00:47:57,270
>> Maar ik beweer dat wanneer ik dit run
code, zoals ik nu doe -

1097
00:47:57,270 --> 00:47:59,490
laat me ga je gang en plak het in hier.

1098
00:47:59,490 --> 00:48:01,995
Ik zal dit noswap.c noemen.

1099
00:48:01,995 --> 00:48:05,630
En zoals de naam al doet vermoeden, is dit niet
gaan een correcte programma.

1100
00:48:05,630 --> 00:48:09,460
Maak noswap. / Geen swap.

1101
00:48:09,460 --> 00:48:12,110
x is 1, y 2, ruilen, verwisseld.

1102
00:48:12,110 --> 00:48:14,220
x is 1, y is 2.

1103
00:48:14,220 --> 00:48:16,920
Dit is uit den boze, zelfs
al lijkt dit volkomen

1104
00:48:16,920 --> 00:48:17,730
mij redelijk.

1105
00:48:17,730 --> 00:48:21,330
En er is een reden, maar we zijn niet
gaan naar de reden te onthullen gewoon nog niet.

1106
00:48:21,330 --> 00:48:24,610
>> Voor nu de tweede cliffhanger ik wilde
om u te verlaten met is dit, een

1107
00:48:24,610 --> 00:48:27,120
aankondiging van soorten op coupon codes.

1108
00:48:27,120 --> 00:48:31,590
Onze innovatie met late dagen van dit jaar
heeft een niet-triviale nummer uitgelokt

1109
00:48:31,590 --> 00:48:33,830
van vragen, die was
niet onze bedoeling.

1110
00:48:33,830 --> 00:48:36,590
De bedoeling van deze coupon codes,
waarbij als je een deel van het probleem

1111
00:48:36,590 --> 00:48:39,850
set vroeg, waardoor het krijgen van een extra dag,
was echt te helpen jullie helpen

1112
00:48:39,850 --> 00:48:42,420
je vroeg beginnen, sorteren
van door incentivizing u.

1113
00:48:42,420 --> 00:48:44,880
Helpt ons verdelen lading over
kantooruren beter, zodat

1114
00:48:44,880 --> 00:48:45,740
het is een soort van win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Helaas, ik denk dat mijn instructies
niet zijn, tot op heden, heel duidelijk, dus

1116
00:48:48,860 --> 00:48:52,230
Ik ging terug dit weekend en geactualiseerd
de spec in grotere, krachtiger tekst

1117
00:48:52,230 --> 00:48:53,600
verklaren kogels als deze.

1118
00:48:53,600 --> 00:48:56,900
En alleen maar om het meer publiekelijk zeggen door
Standaard probleem sets zijn te wijten donderdag

1119
00:48:56,900 --> 00:48:58,400
op de middag, per de syllabus.

1120
00:48:58,400 --> 00:49:02,030
Als je vroeg beginnen, afwerking deel van
de door woensdag vastgesteld op 0:00 probleem

1121
00:49:02,030 --> 00:49:05,170
PM, het deel dat betrekking heeft op een coupon
code, het idee is dat je kunt uitbreiden

1122
00:49:05,170 --> 00:49:07,710
uw deadline voor de
P stellen tot vrijdag.

1123
00:49:07,710 --> 00:49:10,890
Dat is, beetje uit een klein deel van de P
ingesteld ten opzichte van wat typisch is de

1124
00:49:10,890 --> 00:49:13,200
groter probleem, en je koopt
zelf een extra dag.

1125
00:49:13,200 --> 00:49:15,190
Nogmaals, het krijgt u na te denken over
het probleem set, krijgt u

1126
00:49:15,190 --> 00:49:16,380
kantoor uren eerder.

1127
00:49:16,380 --> 00:49:20,670
Maar de coupon code probleem is nog steeds
vereist, zelfs als je het niet indienen.

1128
00:49:20,670 --> 00:49:23,340
>> Maar meer dwingend is dit.

1129
00:49:23,340 --> 00:49:26,520
(STAGE WHISPER) En die mensen verlaten
vroeg zijn gonna spijt.

1130
00:49:26,520 --> 00:49:28,620
Net als de mensen op het balkon.

1131
00:49:28,620 --> 00:49:32,510
Ik verontschuldig me bij voorbaat aan de mensen op
het balkon om redenen die zullen worden

1132
00:49:32,510 --> 00:49:33,920
duidelijk in slechts een moment.

1133
00:49:33,920 --> 00:49:37,050
>> Dus we hebben het geluk om een ​​van zijn
Voormalig hoofd teaching fellows CS50's bij

1134
00:49:37,050 --> 00:49:39,302
een bedrijf genaamd dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Ze zijn zeer gul gedoneerd een
couponcode hier voor dit veel ruimte,

1136
00:49:45,500 --> 00:49:48,180
dat is een stijging van de
gebruikelijke 2 gigabyte.

1137
00:49:48,180 --> 00:49:51,740
Dus wat ik dacht dat we zouden doen op deze
laatste opmerking is wel een beetje een weggevertje,

1138
00:49:51,740 --> 00:49:55,380
waarbij in slechts een moment, zullen we onthullen
de winnaar en die heeft een coupon

1139
00:49:55,380 --> 00:49:57,980
code die u vervolgens kunt gaan naar hun
website, typt u het in, en voila, krijgen een

1140
00:49:57,980 --> 00:50:01,370
veel meer Dropbox ruimte voor uw
toestel en voor uw persoonlijke bestanden.

1141
00:50:01,370 --> 00:50:05,690
>> En de eerste, die willen deelnemen
in deze tekening?

1142
00:50:05,690 --> 00:50:09,630
OK, nu dat maakt het nog leuker.

1143
00:50:09,630 --> 00:50:14,010
De persoon die deze 25-gigabyte ontvangt
coupon code - die ver

1144
00:50:14,010 --> 00:50:16,150
dwingender dan de late
dagen nu, misschien -

1145
00:50:16,150 --> 00:50:20,620
is degene die zit op een
zitkussen waar doorheen er

1146
00:50:20,620 --> 00:50:21,620
die coupon code.

1147
00:50:21,620 --> 00:50:23,480
U kunt nu kijken eronder
uw zitkussen.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [VIDEO AFSPELEN]

1150
00:50:29,680 --> 00:50:31,620
>> -Een, twee, drie.

1151
00:50:31,620 --> 00:50:35,015
>> [SCREAMING]

1152
00:50:35,015 --> 00:50:35,985
>> -Je krijgt een auto!

1153
00:50:35,985 --> 00:50:36,670
Je krijgt een auto!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: We zullen zien
u op woensdag.

1155
00:50:37,970 --> 00:50:38,904
>> -Je krijgt een auto!

1156
00:50:38,904 --> 00:50:39,371
Je krijgt een auto!

1157
00:50:39,371 --> 00:50:40,305
Je krijgt een auto!

1158
00:50:40,305 --> 00:50:41,706
Je krijgt een auto!

1159
00:50:41,706 --> 00:50:43,107
Je krijgt een auto!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: Balkon mensen, kom
hier beneden aan de voorzijde,

1161
00:50:45,530 --> 00:50:46,866
waar we extra's.

1162
00:50:46,866 --> 00:50:50,282
>> -Iedereen krijgt een auto!

1163
00:50:50,282 --> 00:50:52,234
Iedereen krijgt een auto!

1164
00:50:52,234 --> 00:50:52,722
>> [END VIDEO AFSPELEN]

1165
00:50:52,722 --> 00:50:54,590
>> NARRATOR: Bij de volgende CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: Oh my gosh gosh gosh gosh
gosh gosh gosh gosh gosh gosh -

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE PLAYS]