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

2
00:00:00,488 --> 00:00:10,800
>> [Musik Spela]

3
00:00:10,800 --> 00:00:13,500
DAVID MALAN: Okej.

4
00:00:13,500 --> 00:00:14,670
Okej, välkommen tillbaka.

5
00:00:14,670 --> 00:00:18,120
Så detta är Vecka 4, inledningen
detta, redan.

6
00:00:18,120 --> 00:00:21,320
Och du kommer ihåg att förra veckan, satte vi
koda åt sidan för bara en liten bit

7
00:00:21,320 --> 00:00:24,240
och vi började prata lite mer
hög nivå, om saker som

8
00:00:24,240 --> 00:00:28,130
sökning och sortering, som dock
något enkla idéer, är

9
00:00:28,130 --> 00:00:31,840
representant för en klass av problem
du kommer att börja lösa särskilt

10
00:00:31,840 --> 00:00:34,820
när du börjar tänka på final
projekt och intressanta lösningar du

11
00:00:34,820 --> 00:00:36,760
kanske måste verkliga problem.

12
00:00:36,760 --> 00:00:39,490
Nu bubbla sortera var en av de enklaste
dessa algoritmer, och det

13
00:00:39,490 --> 00:00:42,900
arbetat med att ha dessa små siffror
i en lista eller i en matris typ av

14
00:00:42,900 --> 00:00:46,530
bubbla sig upp till toppen, och
stora siffrorna flyttar sig ner till

15
00:00:46,530 --> 00:00:47,930
I slutet av denna lista.

16
00:00:47,930 --> 00:00:50,650
>> Och minns att vi kunde visualisera
bubbla sortera lite

17
00:00:50,650 --> 00:00:52,310
ungefär så här.

18
00:00:52,310 --> 00:00:53,640
Så låt mig gå vidare och klicka på Start.

19
00:00:53,640 --> 00:00:55,350
Jag har förvalt bubbla sortera.

20
00:00:55,350 --> 00:00:58,920
Och om ni minns att den högre blå
linjerna representerar stora siffror, små

21
00:00:58,920 --> 00:01:03,300
blå linjerna representerar små siffror, som
Vi går igenom det här igen och igen och

22
00:01:03,300 --> 00:01:07,680
igen, jämföra två barer bredvid varje
andra i rött, vi kommer att byta

23
00:01:07,680 --> 00:01:11,010
största och den minsta om
de är i ordning.

24
00:01:11,010 --> 00:01:14,150
>> Så det här kommer att gå på och gå på och gå
på, och du kommer att se att större

25
00:01:14,150 --> 00:01:16,700
element gör sig till
höger, och de mindre delarna är

26
00:01:16,700 --> 00:01:17,900
på väg till vänster.

27
00:01:17,900 --> 00:01:21,380
Men vi började att kvantifiera
effektiviteten, den

28
00:01:21,380 --> 00:01:22,970
kvaliteten på denna algoritm.

29
00:01:22,970 --> 00:01:25,200
Och vi sa att i värsta
fall, tog denna algoritm

30
00:01:25,200 --> 00:01:27,940
ungefär hur många steg?

31
00:01:27,940 --> 00:01:28,980
>> Så n kvadrat.

32
00:01:28,980 --> 00:01:30,402
Och vad var n?

33
00:01:30,402 --> 00:01:31,650
>> Publik: Antal element.

34
00:01:31,650 --> 00:01:32,790
>> DAVID MALAN: So n var
antal element.

35
00:01:32,790 --> 00:01:33,730
Och så ska vi göra det ofta.

36
00:01:33,730 --> 00:01:36,650
Varje gång vi vill tala om storleken
av ett problem eller storleken på ett

37
00:01:36,650 --> 00:01:39,140
ingång, eller hur lång tid det tar
producera utskrifter, vi ska bara

38
00:01:39,140 --> 00:01:41,610
generaliserad oavsett
ingången är såsom n.

39
00:01:41,610 --> 00:01:45,970
Så tillbaka i vecka 0, antalet sidor
i telefonboken var n..

40
00:01:45,970 --> 00:01:47,550
Antalet studenter
i rummet var n.

41
00:01:47,550 --> 00:01:49,630
Så även här, vi följer
det mönstret.

42
00:01:49,630 --> 00:01:52,800
>> Nu n kvadrat är inte särskilt
snabbt, så vi har försökt att göra bättre.

43
00:01:52,800 --> 00:01:55,970
Och så tittade vi på ett par
andra algoritmer, bland vilka

44
00:01:55,970 --> 00:01:57,690
var val sort.

45
00:01:57,690 --> 00:01:59,180
Så val sortera var
lite annorlunda.

46
00:01:59,180 --> 00:02:03,130
Det var nästan enklare, jag vågar säga,
där jag började i början av

47
00:02:03,130 --> 00:02:06,740
Listan över våra volontärer och jag bara igen
och igen och igen gick igenom

48
00:02:06,740 --> 00:02:10,060
listan, plockning ut den minsta
element i taget och sätta honom eller

49
00:02:10,060 --> 00:02:13,040
henne i början av listan.

50
00:02:13,040 --> 00:02:16,410
>> Men även detta, när vi började fundera
genom matte och större

51
00:02:16,410 --> 00:02:19,860
bild, tänkte på hur många gånger
Jag gick fram och tillbaka och tillbaka

52
00:02:19,860 --> 00:02:24,090
och tillbaka, sa vi i värsta fall,
selection sort, också var vad?

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

54
00:02:24,960 --> 00:02:27,490
Nu i den verkliga världen, kanske det
faktiskt vara marginellt snabbare.

55
00:02:27,490 --> 00:02:30,620
Eftersom igen, det gjorde jag inte hålla
backa när jag hade sorterat

56
00:02:30,620 --> 00:02:31,880
minsta beståndsdel.

57
00:02:31,880 --> 00:02:35,090
Men om vi tänker mycket stort N, och
om du sorts göra ut matten som

58
00:02:35,090 --> 00:02:39,170
Jag gjorde i styrelsen, med n kvadrat
minus någonting, allt annat

59
00:02:39,170 --> 00:02:41,850
förutom n kvadrat, när n
blir riktigt stor, inte

60
00:02:41,850 --> 00:02:42,850
verkligen betyder så mycket.

61
00:02:42,850 --> 00:02:45,470
Så som datavetare, sorterar vi om
blundar för de mindre

62
00:02:45,470 --> 00:02:49,220
faktorer och bara fokusera på de faktorer i
ett uttryck som kommer att göra

63
00:02:49,220 --> 00:02:50,330
den största skillnaden.

64
00:02:50,330 --> 00:02:52,840
>> Nåväl, slutligen, såg vi
vid insättning sort.

65
00:02:52,840 --> 00:02:56,620
Och det var i samma anda, men
snarare än att gå igenom iterativt och

66
00:02:56,620 --> 00:03:01,250
välja det minsta elementet en i
tid, tog jag istället handen som jag

67
00:03:01,250 --> 00:03:04,070
behandlades, och jag bestämde mig, alla
rätt, hör du här.

68
00:03:04,070 --> 00:03:06,160
Sedan jag flyttade till nästa element
och bestämde att han eller

69
00:03:06,160 --> 00:03:07,470
hon tillhörde här.

70
00:03:07,470 --> 00:03:08,810
Och sedan jag flyttade och på.

71
00:03:08,810 --> 00:03:11,780
Och jag fick till, längs vägen,
skifta dessa killar för att

72
00:03:11,780 --> 00:03:13,030
göra plats för dem.

73
00:03:13,030 --> 00:03:16,880
Så det var typ av mentala omsvängning
av urvalet sortera som vi

74
00:03:16,880 --> 00:03:18,630
kallas insättning sort.

75
00:03:18,630 --> 00:03:20,810
>> Så dessa ämnen att uppstå
i den verkliga världen.

76
00:03:20,810 --> 00:03:23,640
För bara några år sedan, när en viss
senator kördes för president,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, vid den tidpunkt då VD
Google, faktiskt haft möjlighet

78
00:03:27,160 --> 00:03:28,040
att intervjua honom.

79
00:03:28,040 --> 00:03:32,010
Och vi trodde vi skulle dela denna YouTube
klipp för dig här, om vi kunde vända upp

80
00:03:32,010 --> 00:03:32,950
volymen.

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

82
00:03:39,360 --> 00:03:44,620
>> -Nu, senator, du är här på Google,
och jag gillar att tänka på ordförandeskapet

83
00:03:44,620 --> 00:03:46,042
som en anställningsintervju.

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

85
00:03:47,770 --> 00:03:50,800
>> -Nu är det svårt att få
ett jobb som president.

86
00:03:50,800 --> 00:03:52,480
Och du går igenom
stelhet nu.

87
00:03:52,480 --> 00:03:54,330
Det är också svårt att få ett jobb på Google.

88
00:03:54,330 --> 00:03:59,610
Vi har frågor och vi ber
Våra kandidater frågor.

89
00:03:59,610 --> 00:04:02,250
Och den här är från Larry Schwimmer.

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

91
00:04:05,325 --> 00:04:06,400
-Ni tror jag skojar?

92
00:04:06,400 --> 00:04:08,750
Det är just här.

93
00:04:08,750 --> 00:04:12,110
Vad är det mest effektiva sättet att
sortera en miljon två-bitars heltal?

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

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

96
00:04:18,260 --> 00:04:19,029
>> -Jag är ledsen.

97
00:04:19,029 --> 00:04:19,745
Kanske vi borde -

98
00:04:19,745 --> 00:04:21,000
>> -Nej, nej, nej, nej, nej.

99
00:04:21,000 --> 00:04:21,470
>> -Det är inte en -

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

101
00:04:22,185 --> 00:04:25,328
>> -Jag tror att bubblan sort skulle
vara fel väg att gå.

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

103
00:04:26,792 --> 00:04:28,510
>> [Jublar och applåder]

104
00:04:28,510 --> 00:04:31,211
>> -Kom igen, som berättade det här?

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

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

107
00:04:33,350 --> 00:04:35,070
>> DAVID MALAN: Så där har ni det.

108
00:04:35,070 --> 00:04:39,600
Så vi började att kvantifiera dessa körs
gånger, så att säga, med något

109
00:04:39,600 --> 00:04:43,480
kallas asymptotisk notation, vilket är
bara hänvisa till vår typ av svarvning

110
00:04:43,480 --> 00:04:47,420
blunda för dessa mindre faktorer och
bara titta på gångtid,

111
00:04:47,420 --> 00:04:51,250
utförandet av dessa algoritmer,
som n blir riktigt stort över tiden.

112
00:04:51,250 --> 00:04:55,110
Och så vi introducerade big O. Och big O
representerade något som vi trodde

113
00:04:55,110 --> 00:04:57,000
av som en övre gräns.

114
00:04:57,000 --> 00:04:59,570
Och faktiskt, Barry, kan vi sänka
än mic lite?

115
00:04:59,570 --> 00:05:01,040
>> Vi trodde att detta är en övre gräns.

116
00:05:01,040 --> 00:05:04,710
Så stort O i n kvadrat innebär att i
värsta fall, något som

117
00:05:04,710 --> 00:05:07,780
selection sort skulle ta
n kvadrat steg.

118
00:05:07,780 --> 00:05:10,310
Eller något liknande insättning sortera
skulle n kvadrat steg.

119
00:05:10,310 --> 00:05:15,150
Nu till något liknande insättning
Sortera, vad var det värsta?

120
00:05:15,150 --> 00:05:18,200
Givet en matris, är vad det värsta
möjligt scenario som du kanske hitta

121
00:05:18,200 --> 00:05:20,650
dig inför?

122
00:05:20,650 --> 00:05:21,860
>> Det är helt bakåt, höger?

123
00:05:21,860 --> 00:05:24,530
För om det är helt bakåt,
du måste göra en hel del arbete.

124
00:05:24,530 --> 00:05:26,420
För om du är helt bakåt,
du kommer att hitta den

125
00:05:26,420 --> 00:05:28,840
största delen här, även om
det hör hemma där nere.

126
00:05:28,840 --> 00:05:31,140
Så du kommer att säga, okej, vid
denna tidpunkt, hör du här,

127
00:05:31,140 --> 00:05:32,310
så du lämnar den ensam.

128
00:05:32,310 --> 00:05:35,425
>> Då inser du, åh, fan, jag måste
flytta denna något mindre inslag

129
00:05:35,425 --> 00:05:36,470
vänster om dig.

130
00:05:36,470 --> 00:05:38,770
Då måste jag göra det igen
och igen och igen.

131
00:05:38,770 --> 00:05:41,410
Och om jag gick fram och tillbaka, du
skulle sorts känsla prestanda

132
00:05:41,410 --> 00:05:45,540
denna algoritm, eftersom tiden är jag
blanda alla andra nere i

133
00:05:45,540 --> 00:05:46,510
array för att göra plats för den.

134
00:05:46,510 --> 00:05:47,750
Så det är det värsta fallet.

135
00:05:47,750 --> 00:05:48,570
>> Däremot -

136
00:05:48,570 --> 00:05:50,320
och detta var en cliffhanger förra gången -

137
00:05:50,320 --> 00:05:54,065
Vi sade att införandet sort
var en omega av vad?

138
00:05:54,065 --> 00:05:57,530
Vad är det bästa tänkbara löpning
insättandet sort?

139
00:05:57,530 --> 00:05:58,520
Så det är faktiskt n.

140
00:05:58,520 --> 00:06:00,980
Det var tomt som vi lämnade
på tavlan förra gången.

141
00:06:00,980 --> 00:06:03,160
>> Och det är omega n eftersom varför?

142
00:06:03,160 --> 00:06:06,630
Tja, i allra bästa fall, vad är
insättning sort ska lämnas?

143
00:06:06,630 --> 00:06:09,830
Tja, en lista som är helt sorteras
redan, minimalt arbete att göra.

144
00:06:09,830 --> 00:06:12,460
Men vad är snyggt om införande sort
är att eftersom det börjar här och

145
00:06:12,460 --> 00:06:15,340
beslutar, åh, är du numret
en, hör du här.

146
00:06:15,340 --> 00:06:16,970
Åh, vilken lycka.

147
00:06:16,970 --> 00:06:17,740
>> Du är nummer två.

148
00:06:17,740 --> 00:06:19,030
Du hör även hit.

149
00:06:19,030 --> 00:06:21,010
Nummer tre, ännu bättre,
du hör hemma här.

150
00:06:21,010 --> 00:06:25,210
Så snart det blir till slut
lista, per insättning sortera s pseudokod

151
00:06:25,210 --> 00:06:28,010
att vi gick igenom muntligt
förra gången, är det gjort.

152
00:06:28,010 --> 00:06:32,790
Men urvalet sortera, däremot,
hålls gör vad?

153
00:06:32,790 --> 00:06:35,260
>> Hålls gå igenom listan
igen och igen och igen.

154
00:06:35,260 --> 00:06:39,160
Eftersom den viktigaste insikten fanns bara
När du har tittat hela vägen till

155
00:06:39,160 --> 00:06:42,500
slutet av listan kan du vara säker
att elementet du valde var

156
00:06:42,500 --> 00:06:45,560
verkligen för närvarande minsta elementet.

157
00:06:45,560 --> 00:06:48,920
Så dessa olika mentala modeller slut
upp ger några mycket verkliga

158
00:06:48,920 --> 00:06:53,130
skillnader för oss, liksom dessa
teoretiska asymptotiska skillnader.

159
00:06:53,130 --> 00:06:56,910
>> Så bara för att sammanfatta, då, big O n
kvadrat, har vi sett några sådana

160
00:06:56,910 --> 00:06:58,350
algoritmer hittills.

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

162
00:06:59,580 --> 00:07:02,870
Vad är en algoritm som kunde
sägas vara stort O n?

163
00:07:02,870 --> 00:07:06,930
I värsta fall, tar det
en linjär antal steg.

164
00:07:06,930 --> 00:07:07,810
>> OK, linjär sökning.

165
00:07:07,810 --> 00:07:10,470
Och i värsta fall, där är
element som du letar efter när

166
00:07:10,470 --> 00:07:12,950
tillämpa linjär sökning?

167
00:07:12,950 --> 00:07:14,680
>> OK, i värsta fall,
det är inte ens där.

168
00:07:14,680 --> 00:07:17,000
Eller i den näst värsta fall är det
hela vägen i slutet, vilket är

169
00:07:17,000 --> 00:07:18,880
plus-eller-minus en en-stegs skillnad.

170
00:07:18,880 --> 00:07:21,180
Så i slutet av dagen,
Vi kan säga att det är linjärt.

171
00:07:21,180 --> 00:07:23,910
Big O n skulle vara linjär sökning,
eftersom det i det värsta fallet, den

172
00:07:23,910 --> 00:07:26,610
elementet är inte ens där eller det är
hela vägen i slutet.

173
00:07:26,610 --> 00:07:29,370
>> Tja, stort O i log n.

174
00:07:29,370 --> 00:07:32,760
Vi pratade inte i detalj om
detta, men vi har sett det här förut.

175
00:07:32,760 --> 00:07:36,840
Vad körs i så kallad logaritmisk
tid, i värsta fall?

176
00:07:36,840 --> 00:07:38,500
>> Ja, så binär sökning.

177
00:07:38,500 --> 00:07:42,930
Och binär sökning i värsta fall
kan ha elementet någonstans i

178
00:07:42,930 --> 00:07:45,640
mitten, eller någonstans
inuti arrayen.

179
00:07:45,640 --> 00:07:48,040
Men du bara hitta det när du
dela upp listan på mitten, i

180
00:07:48,040 --> 00:07:48,940
hälften, på mitten, på mitten.

181
00:07:48,940 --> 00:07:50,200
Och sedan voila, det är där.

182
00:07:50,200 --> 00:07:52,500
Eller igen, värsta fall,
det är inte ens där.

183
00:07:52,500 --> 00:07:56,770
Men du vet inte att det inte finns
tills du sorts nå det sista

184
00:07:56,770 --> 00:08:00,470
nedersta elementen genom att halvera
och halvera och halvera.

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

186
00:08:01,400 --> 00:08:03,540
Så vi kunde stora O 2, big O 3.

187
00:08:03,540 --> 00:08:06,260
När som helst du vill ha bara ett konstant antal,
sorterar vi bara om just förenkla

188
00:08:06,260 --> 00:08:07,280
att så stor O 1.

189
00:08:07,280 --> 00:08:10,440
Även om om realistiskt, tar det
2 eller till och med 100 steg, om det är en

190
00:08:10,440 --> 00:08:13,680
konstant antal steg,
vi säger bara Big O 1.

191
00:08:13,680 --> 00:08:15,930
Vad är en algoritm som är
i stort O i 1?

192
00:08:15,930 --> 00:08:18,350
>> Publik: Hitta längden
av en variabel.

193
00:08:18,350 --> 00:08:21,090
>> DAVID MALAN: Hitta
längden av en variabel?

194
00:08:21,090 --> 00:08:23,870
>> Publiken: Nej, längden
om den redan är sorterade.

195
00:08:23,870 --> 00:08:24,160
>> DAVID MALAN: Bra.

196
00:08:24,160 --> 00:08:27,850
OK, så att hitta längden på något
om längden av att något, som

197
00:08:27,850 --> 00:08:30,020
en array, är lagrad i någon variabel.

198
00:08:30,020 --> 00:08:33,380
Eftersom du kan bara läsa variabeln,
eller skriva ut variabeln, eller

199
00:08:33,380 --> 00:08:34,960
bara allmänt komma åt den variabeln.

200
00:08:34,960 --> 00:08:37,299
Och voila, som tar konstant tid.

201
00:08:37,299 --> 00:08:38,909
>> Däremot tänker tillbaka till noll.

202
00:08:38,909 --> 00:08:42,460
Tänk tillbaka till den första veckan i C,
ringer bara printf och skriva

203
00:08:42,460 --> 00:08:46,240
något på skärmen är utan tvekan
konstant tid, eftersom det tar bara

204
00:08:46,240 --> 00:08:50,880
några antal CPU-cykler för att visa
att text på skärmen.

205
00:08:50,880 --> 00:08:52,720
Eller vänta - gör det?

206
00:08:52,720 --> 00:08:56,430
Hur annars kan vi modellera
prestanda för printf?

207
00:08:56,430 --> 00:09:00,420
Skulle någon vilja att vara oense, att
kanske är det inte riktigt konstant tid?

208
00:09:00,420 --> 00:09:03,600
I vilken mening kan printf körs
tid, faktiskt skriver ut en sträng på

209
00:09:03,600 --> 00:09:05,580
skärmen, vara något
annat än konstant.

210
00:09:05,580 --> 00:09:07,860
>> Publik: [OHÖRBAR].

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

212
00:09:08,230 --> 00:09:09,300
Så det beror på vårt perspektiv.

213
00:09:09,300 --> 00:09:13,390
Om vi ​​tänker faktiskt hos insignalen till
printf som den sträng, och

214
00:09:13,390 --> 00:09:16,380
Därför mäter vi storleken på det
ingång genom sin längd - så låt oss kalla

215
00:09:16,380 --> 00:09:17,780
att längden n samt -

216
00:09:17,780 --> 00:09:21,990
utan tvekan, printf är själv stor O n
eftersom det kommer att ta dig n steg

217
00:09:21,990 --> 00:09:24,750
att skriva ut varje av dessa n
tecken, mest sannolikt.

218
00:09:24,750 --> 00:09:27,730
Åtminstone i den utsträckning som vi antar
som kanske är det med hjälp av en for-loop

219
00:09:27,730 --> 00:09:28,560
under huven.

220
00:09:28,560 --> 00:09:30,860
>> Men vi skulle behöva titta på det
Kod för att förstå det bättre.

221
00:09:30,860 --> 00:09:33,650
Och faktiskt, när ni börjar
analysera dina egna algoritmer, kommer du

222
00:09:33,650 --> 00:09:34,900
bokstavligen göra just det.

223
00:09:34,900 --> 00:09:37,765
Sortera på ögongloben din kod och tror
om - okej, jag har denna slinga

224
00:09:37,765 --> 00:09:41,870
här eller jag har en nästlade loopar här,
som kommer att göra n saker N gånger,

225
00:09:41,870 --> 00:09:46,050
och du kan sortera förnuftets väg
igenom koden, även om det är

226
00:09:46,050 --> 00:09:47,980
pseudokod och inte faktiska koden.

227
00:09:47,980 --> 00:09:49,730
>> Så vad om omega n kvadrat?

228
00:09:49,730 --> 00:09:53,582
Vad var en algoritm som i bästa
fall fortfarande tog n kvadrat steg?

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

230
00:09:54,014 --> 00:09:54,880
>> Publik: [OHÖRBAR].

231
00:09:54,880 --> 00:09:55,900
>> DAVID MALAN: So urval sort.

232
00:09:55,900 --> 00:09:59,150
På grund av att problemet verkligen reduceras
det faktum att igen, jag vet inte

233
00:09:59,150 --> 00:10:02,600
Jag har hittat den nuvarande minsta tills
Jag har kollat ​​alla jäkla element.

234
00:10:02,600 --> 00:10:08,050
Så omega av, säg, N, vi
bara kom upp med en.

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

236
00:10:09,300 --> 00:10:12,370
Om listan råkar vara sorteras
redan, i bästa fall har vi bara

237
00:10:12,370 --> 00:10:15,090
för att göra en passage genom den,
då vi är säkra.

238
00:10:15,090 --> 00:10:17,890
Och sedan som kan sägas
vara linjär, for sure.

239
00:10:17,890 --> 00:10:20,570
>> Hur är omega av 1?

240
00:10:20,570 --> 00:10:23,790
Vad, i bästa fall, kan ta
ett konstant antal steg?

241
00:10:23,790 --> 00:10:27,220
Så linjär sökning, om du får bara tur
och elementet du söker

242
00:10:27,220 --> 00:10:31,000
är precis i början av listan,
om det är där du börjar ditt

243
00:10:31,000 --> 00:10:33,070
linjär förflyttning av den listan.

244
00:10:33,070 --> 00:10:35,180
>> Och detta är sant för en
antal saker.

245
00:10:35,180 --> 00:10:37,660
Till exempel, även binära
sökning är omega av 1.

246
00:10:37,660 --> 00:10:40,310
För vad om du får riktigt jäkla
tur och smack-dab i mitten av

247
00:10:40,310 --> 00:10:42,950
din array är antalet
du letar efter?

248
00:10:42,950 --> 00:10:45,730
Så du kan ha tur där, liksom.

249
00:10:45,730 --> 00:10:49,190
>> Denna en slutligen omega av n log n.

250
00:10:49,190 --> 00:10:52,573
Så n log n, det gjorde vi inte riktigt
prata om ännu, men -

251
00:10:52,573 --> 00:10:53,300
>> Publik: Merge sort?

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

253
00:10:53,960 --> 00:10:56,920
Det var cliffhanger förra gången,
där vi föreslog, och vi visade

254
00:10:56,920 --> 00:10:58,600
visuellt, att det finns algoritmer.

255
00:10:58,600 --> 00:11:02,470
Och slå samman liksom bara en sådan
algoritm som är fundamentalt snabbare

256
00:11:02,470 --> 00:11:03,450
än vissa av dessa andra killar.

257
00:11:03,450 --> 00:11:07,800
I själva verket, slå ihop kort är inte bara i
bästa fall n log, i värsta

258
00:11:07,800 --> 00:11:09,460
För n n log.

259
00:11:09,460 --> 00:11:14,540
Och när du har detta sammanträffande av
omega och stora O är samma sak?

260
00:11:14,540 --> 00:11:17,310
Vi kan faktiskt beskriva det som det är
kallas theta, även om det är en

261
00:11:17,310 --> 00:11:18,220
lite mindre vanligt.

262
00:11:18,220 --> 00:11:21,730
Men det betyder bara de två gränserna,
i detta fall är desamma.

263
00:11:21,730 --> 00:11:25,770
>> Så sammanfoga sort, vad har detta
verkligen koka ner till för oss?

264
00:11:25,770 --> 00:11:27,000
Tja, minns motivationen.

265
00:11:27,000 --> 00:11:30,340
Låt mig dra upp en annan animation som
vi inte titta på förra gången.

266
00:11:30,340 --> 00:11:33,390
Detta en, samma idé, men
det är lite större.

267
00:11:33,390 --> 00:11:36,160
Och jag ska gå vidare och påpeka
först - vi har insättning Sortera på

268
00:11:36,160 --> 00:11:39,410
längst upp till vänster, och sedan välja sortera,
Bubble sort, ett par andra typer -

269
00:11:39,410 --> 00:11:42,670
skal och snabb - att vi inte har pratat
om, och heap och sammanfoga sort.

270
00:11:42,670 --> 00:11:47,090
>> Så åtminstone försöka att fokusera ögonen på
den översta tre till vänster och sedan

271
00:11:47,090 --> 00:11:49,120
sammanfoga sort när jag klickar
denna gröna pilen.

272
00:11:49,120 --> 00:11:51,900
Men jag ska låta dem alla springa, bara för att
ger dig en känsla av mångfalden av

273
00:11:51,900 --> 00:11:53,980
algoritmer som finns i världen.

274
00:11:53,980 --> 00:11:56,180
Jag kommer att låta denna körning
för bara några sekunder.

275
00:11:56,180 --> 00:11:59,640
Och om du fokuserar dina ögon - välj ett
algoritm, fokusera på det för bara ett

276
00:11:59,640 --> 00:12:02,970
sekunder - du kommer att börja se
mönster som det är att genomföra.

277
00:12:02,970 --> 00:12:04,530
>> Merge sort, varsel, görs.

278
00:12:04,530 --> 00:12:06,430
Heap sort, snabbt sortera, shell -

279
00:12:06,430 --> 00:12:09,480
så det verkar vi introducerade tre
värsta algoritmer förra veckan.

280
00:12:09,480 --> 00:12:12,960
Men det är bra att vi är här i dag för att
titta på merge sortera, är där en av

281
00:12:12,960 --> 00:12:16,500
de lättare dem är att titta på, även
även om det förmodligen kommer att böja din hjärna

282
00:12:16,500 --> 00:12:17,490
bara lite.

283
00:12:17,490 --> 00:12:21,130
Här kan vi se precis hur mycket
val Sortera suger.

284
00:12:21,130 --> 00:12:24,600
>> Men på baksidan, det är
verkligen lätt att genomföra.

285
00:12:24,600 --> 00:12:28,160
Och kanske för P Set 3, det är en av de
algoritmer du valde att genomföra

286
00:12:28,160 --> 00:12:28,960
för standardversionen.

287
00:12:28,960 --> 00:12:30,970
Perfekt fina, helt korrekt.

288
00:12:30,970 --> 00:12:35,210
>> Men återigen, som n blir stor, om du
välja att genomföra en snabbare algoritm

289
00:12:35,210 --> 00:12:39,020
gillar samman sortera, oddsen är större och
större insatser, är din kod bara

290
00:12:39,020 --> 00:12:39,800
kommer att köra fortare.

291
00:12:39,800 --> 00:12:41,090
Din webbplats kommer att fungera bättre.

292
00:12:41,090 --> 00:12:42,650
Dina användare kommer att bli lyckligare.

293
00:12:42,650 --> 00:12:45,280
Och så finns dessa effekter
att faktiskt ge

294
00:12:45,280 --> 00:12:47,350
oss lite djupare tanke.

295
00:12:47,350 --> 00:12:49,990
>> Så låt oss ta en titt på vad som går samman
Sortera egentligen handlar om.

296
00:12:49,990 --> 00:12:52,992
Det häftiga är att slå ihop
Sortera är just detta.

297
00:12:52,992 --> 00:12:56,300
Detta är, återigen, vad vi har kallat
pseudokod, pseudokod varelse

298
00:12:56,300 --> 00:12:57,720
Engelsk-liknande syntax.

299
00:12:57,720 --> 00:12:59,890
Och enkelheten är
slags fascinerande.

300
00:12:59,890 --> 00:13:02,840
>> Så på inmatning av n element - så att
betyder bara, här är en array.

301
00:13:02,840 --> 00:13:04,000
Det har fått n saker i det.

302
00:13:04,000 --> 00:13:05,370
Det är allt vi säger det.

303
00:13:05,370 --> 00:13:07,560
>> Om n är mindre än 2, tillbaka.

304
00:13:07,560 --> 00:13:08,640
Så det är bara det triviala fallet.

305
00:13:08,640 --> 00:13:12,580
Om n är mindre än 2, då är det uppenbart att det är
1 eller 0, i vilket fall sak

306
00:13:12,580 --> 00:13:14,780
är redan sorterade eller obefintlig,
så bara tillbaka.

307
00:13:14,780 --> 00:13:15,900
Det finns inget att göra.

308
00:13:15,900 --> 00:13:18,360
Så det är ett enkelt fall att plocka bort.

309
00:13:18,360 --> 00:13:20,110
>> Else, har vi tre steg.

310
00:13:20,110 --> 00:13:23,650
Sortera vänstra halvan av elementen, sortera
den högra halvan av elementen,

311
00:13:23,650 --> 00:13:26,650
och sedan slå ihop de sorterade halvorna.

312
00:13:26,650 --> 00:13:29,400
Vad är intressant här är att
Jag är typ av punting, rätt?

313
00:13:29,400 --> 00:13:32,300
Det är lite av en cirkulär definition
denna algoritm.

314
00:13:32,300 --> 00:13:35,986
I vilken mening är denna algoritm är
definition cirkulär?

315
00:13:35,986 --> 00:13:37,850
>> Publik: [OHÖRBAR].

316
00:13:37,850 --> 00:13:41,670
>> DAVID MALAN: Yeah, my sorteringsalgoritm,
två av dess steg är "sort

317
00:13:41,670 --> 00:13:44,640
något. "Och så väcker
fråga, ja, vad ska jag använda

318
00:13:44,640 --> 00:13:46,460
att sortera den vänstra halvan
och den högra halvan?

319
00:13:46,460 --> 00:13:49,600
Och skönheten här är att även om
igen, detta är den kluriga

320
00:13:49,600 --> 00:13:54,030
del potentiellt, kan du använda samma
algoritm för att sortera den vänstra halvan.

321
00:13:54,030 --> 00:13:54,700
>> Men vänta en minut.

322
00:13:54,700 --> 00:13:57,070
När du berättade att sortera
vänstra halvan, vilka är de två

323
00:13:57,070 --> 00:13:58,240
steg kommer att bli nästa?

324
00:13:58,240 --> 00:14:00,550
Vi reder den vänstra halvan av
vänstra halvan och den högra

325
00:14:00,550 --> 00:14:01,420
hälften av den vänstra halvan.

326
00:14:01,420 --> 00:14:04,430
Fan, hur jag sorterar dessa två
halvor eller fjärdedelar, nu?

327
00:14:04,430 --> 00:14:05,260
>> Men det är OK.

328
00:14:05,260 --> 00:14:07,830
Vi har en sorteringsalgoritm här.

329
00:14:07,830 --> 00:14:10,660
Och även om du kanske oroa dig
först detta är typ av en oändlig

330
00:14:10,660 --> 00:14:12,780
loop, det är en cykel som aldrig
kommer att sluta - det kommer att

331
00:14:12,780 --> 00:14:15,770
sluta en gång vad som händer?

332
00:14:15,770 --> 00:14:16,970
När n är mindre än 2.

333
00:14:16,970 --> 00:14:19,180
Som så småningom kommer att hända,
eftersom om du håller halvera och

334
00:14:19,180 --> 00:14:23,020
halvera halvera dessa halvor, säkert
så småningom du kommer att sluta

335
00:14:23,020 --> 00:14:25,350
upp med bara 1 eller 0 element.

336
00:14:25,350 --> 00:14:28,500
Vid vilken punkt, denna algoritm
säger du är klar.

337
00:14:28,500 --> 00:14:31,020
>> Så den verkliga magin i denna
Algoritmen verkar vara i

338
00:14:31,020 --> 00:14:33,470
det sista steget, sammanslagning.

339
00:14:33,470 --> 00:14:37,190
Denna enkla idé bara samman två
saker, det är det som i slutändan kommer

340
00:14:37,190 --> 00:14:40,920
att tillåta oss att sortera en array av,
låt oss säga, åtta element.

341
00:14:40,920 --> 00:14:44,410
Så jag har åtta mer stress bollar upp
Här, åtta bitar av papper, och en

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

343
00:14:45,500 --> 00:14:46,140
som jag får behålla.

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

345
00:14:46,960 --> 00:14:48,970
>> DAVID MALAN: Om vi ​​kunde ta åtta
volontärer, och låt oss se om vi kan

346
00:14:48,970 --> 00:14:51,430
spela ut det här, så.

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

348
00:14:52,500 --> 00:14:53,565
Datavetenskap blir kul.

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

350
00:14:54,320 --> 00:14:57,770
Så vad sägs om dig tre,
största handen uppe.

351
00:14:57,770 --> 00:14:58,580
Fyra i ryggen.

352
00:14:58,580 --> 00:15:02,220
Och hur vi ska göra dig
tre i denna rad?

353
00:15:02,220 --> 00:15:03,390
Och fyra i fronten.

354
00:15:03,390 --> 00:15:04,920
Så du åtta, kom upp.

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

356
00:15:12,060 --> 00:15:13,450
>> DAVID MALAN: Jag är faktiskt
inte säker på vad det är.

357
00:15:13,450 --> 00:15:14,810
Är det stress bollar?

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

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

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

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

362
00:15:20,160 --> 00:15:21,310
Så kom den upp.

363
00:15:21,310 --> 00:15:22,310
Vem skulle vilja -

364
00:15:22,310 --> 00:15:23,570
fortsätter att komma upp.

365
00:15:23,570 --> 00:15:24,240
Låt oss se.

366
00:15:24,240 --> 00:15:26,460
Och detta sätter dig i plats -

367
00:15:26,460 --> 00:15:27,940
du är på plats ett.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, vänta en minut.

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

370
00:15:30,760 --> 00:15:31,310
Okej, vi är bra.

371
00:15:31,310 --> 00:15:35,130
Okej, så att alla har en plats,
men inte på Google Glass.

372
00:15:35,130 --> 00:15:36,475
Låt mig att köa upp dessa.

373
00:15:36,475 --> 00:15:37,115
Vad är ditt namn?

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
Okej, du får se ut
geeken, om det är OK.

377
00:15:42,000 --> 00:15:44,625
Tja, jag gör också, antar jag,
för bara ett ögonblick.

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

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

380
00:15:48,510 --> 00:15:50,950
Vi har försökt att komma fram till en
använda fall för Google Glass, och vi

381
00:15:50,950 --> 00:15:53,750
trodde det skulle vara kul att bara göra
detta när folk är på scenen.

382
00:15:53,750 --> 00:15:57,120
Vi kommer att spela in världen
ur deras perspektiv.

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

384
00:15:58,410 --> 00:15:59,830
Inte nog vad Google avsett.

385
00:15:59,830 --> 00:16:02,260
Okej, om ni inte har något emot att bära
detta för nästa obekväma minuter,

386
00:16:02,260 --> 00:16:03,150
det skulle vara underbart.

387
00:16:03,150 --> 00:16:08,620
>> Okej, så vi har här en rad
element, och den arrayen, som per den

388
00:16:08,620 --> 00:16:11,480
bitar av papper i dessa folks '
händer, är för närvarande osorterade.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Åh, det är så konstigt.

390
00:16:12,050 --> 00:16:12,810
>> DAVID MALAN: Det är ganska mycket slumpmässigt.

391
00:16:12,810 --> 00:16:15,760
Och på bara ett ögonblick, kommer vi att försöka
att genomföra samman sort tillsammans

392
00:16:15,760 --> 00:16:17,950
och se vart det viktigaste insikten är.

393
00:16:17,950 --> 00:16:21,970
Och tricket här med merge sort är
något som vi inte har tagit ännu.

394
00:16:21,970 --> 00:16:24,030
Vi behöver faktiskt lite
ytterligare utrymme.

395
00:16:24,030 --> 00:16:26,650
Så vad som kommer att vara särskilt
intressant med detta är att dessa

396
00:16:26,650 --> 00:16:29,270
killar kommer att flytta runt lite
lite, eftersom jag kommer att anta att

397
00:16:29,270 --> 00:16:31,880
det finns en extra uppsättning av utrymme,
säga, precis bakom dem.

398
00:16:31,880 --> 00:16:34,570
>> Så om de är bakom sin stol,
det är den sekundära arrayen.

399
00:16:34,570 --> 00:16:36,960
Om de är sittande här, det är
den primära uppsättningen.

400
00:16:36,960 --> 00:16:40,170
Men detta är en resurs som vi har
utan hävstång hittills med bubbel

401
00:16:40,170 --> 00:16:42,040
Sortera, med val sortera,
med införandet sort.

402
00:16:42,040 --> 00:16:44,600
Minns förra veckan, alla bara
slags shuffled på plats.

403
00:16:44,600 --> 00:16:46,840
De använde inte någon ytterligare minne.

404
00:16:46,840 --> 00:16:49,310
Vi gjorde plats för människor med
flytta människor runt.

405
00:16:49,310 --> 00:16:50,580
>> Så detta är en viktig insikt, alltför.

406
00:16:50,580 --> 00:16:53,410
Det är denna avvägning, i allmänhet i
datavetenskap, av resurser.

407
00:16:53,410 --> 00:16:55,800
Om du vill snabba upp något
som tid, du kommer att

408
00:16:55,800 --> 00:16:56,900
måste betala ett pris.

409
00:16:56,900 --> 00:17:00,750
Och en av dessa priser är mycket ofta
utrymme, hur mycket minne eller hård

410
00:17:00,750 --> 00:17:01,700
diskutrymme som du använder.

411
00:17:01,700 --> 00:17:03,640
Eller, ärligt talat, det belopp
av programmerare tid.

412
00:17:03,640 --> 00:17:06,700
Hur mycket tid det tar, det mänskliga,
att faktiskt genomföra några mer

413
00:17:06,700 --> 00:17:07,829
komplicerad algoritm.

414
00:17:07,829 --> 00:17:09,760
Men för idag, avvägningen
är tid och rum.

415
00:17:09,760 --> 00:17:11,930
>> Så om ni bara kunde hålla upp din
nummer så att vi kan se att du är

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

417
00:17:15,839 --> 00:17:16,599
Utmärkt.

418
00:17:16,599 --> 00:17:19,520
Så jag kommer att försöka iscensätta
saker, om ni bara kan

419
00:17:19,520 --> 00:17:21,800
följ mig här.

420
00:17:21,800 --> 00:17:26,650
>> Så jag kommer att genomföra, dels den
första steget i pseudokod, som är

421
00:17:26,650 --> 00:17:29,440
på ingången av n element, om n är
mindre än 2, och sedan tillbaka.

422
00:17:29,440 --> 00:17:31,370
Självklart gör det inte
gäller, så vi går vidare.

423
00:17:31,370 --> 00:17:33,340
Så sortera den vänstra halvan av elementen.

424
00:17:33,340 --> 00:17:36,220
Så det betyder att jag kommer att fokusera min
uppmärksamhet för ett ögonblick på dessa

425
00:17:36,220 --> 00:17:37,310
fyra killar här.

426
00:17:37,310 --> 00:17:39,774
Okej, vad ska jag göra nu?

427
00:17:39,774 --> 00:17:40,570
>> Publik: sortera vänstra halvan.

428
00:17:40,570 --> 00:17:42,780
>> DAVID MALAN: Så nu har jag att sortera
den vänstra halvan av dessa killar.

429
00:17:42,780 --> 00:17:45,580
Eftersom igen, antar att själv
Målet är att sortera den vänstra halvan.

430
00:17:45,580 --> 00:17:46,440
Hur gör du det?

431
00:17:46,440 --> 00:17:49,140
Följ bara instruktionerna, även
även om vi gör det igen.

432
00:17:49,140 --> 00:17:50,160
Så sortera den vänstra halvan.

433
00:17:50,160 --> 00:17:52,030
Nu ska jag sortera dessa två killar.

434
00:17:52,030 --> 00:17:53,563
Vad kommer härnäst?

435
00:17:53,563 --> 00:17:54,510
>> Publik: sortera vänstra halvan.

436
00:17:54,510 --> 00:17:55,460
>> DAVID MALAN: sortera vänstra halvan.

437
00:17:55,460 --> 00:18:00,680
Så nu dessa, denna plats här,
är en lista med storlek 1.

438
00:18:00,680 --> 00:18:01,365
Och vad heter du nu igen?

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 är här.

441
00:18:03,690 --> 00:18:07,470
Och så är hon redan sorteras, eftersom
listan är av storlek 1.

442
00:18:07,470 --> 00:18:09,490
Vad gör jag nu?

443
00:18:09,490 --> 00:18:13,680
OK, tillbaka, eftersom den listan är över
storlek 1, som är mindre än 2.

444
00:18:13,680 --> 00:18:14,320
Men vad är nästa steg?

445
00:18:14,320 --> 00:18:17,490
Och nu måste du typ av
backa i ditt sinne.

446
00:18:17,490 --> 00:18:19,340
>> Sortera den högra halvan, vilket är -

447
00:18:19,340 --> 00:18:19,570
vad är ditt namn?

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
Och så vad gör vi nu att
Vi har en lista med storlek 1?

451
00:18:23,210 --> 00:18:24,440
>> Målgrupp: Return.

452
00:18:24,440 --> 00:18:24,760
>> DAVID MALAN: Försiktig.

453
00:18:24,760 --> 00:18:29,540
Vi återvänder först, och nu den tredje
steg - och om jag slags skildra den genom

454
00:18:29,540 --> 00:18:33,490
omfamna de två sätena nu, nu har jag
behöva slå ihop dessa två element.

455
00:18:33,490 --> 00:18:35,530
Så nu tyvärr elementen
är ur funktion.

456
00:18:35,530 --> 00:18:39,920
Men det är där det överlåtande processen
börjar bli övertygande.

457
00:18:39,920 --> 00:18:42,410
>> Så om ni skulle kunna stå upp för just
ett ögonblick, jag kommer att behöva dig, i en

458
00:18:42,410 --> 00:18:44,170
ögonblick, att kliva bakom din stol.

459
00:18:44,170 --> 00:18:46,480
Och om Linda, eftersom två är
mindre än 4, varför inte

460
00:18:46,480 --> 00:18:48,130
du kommer runt först?

461
00:18:48,130 --> 00:18:48,690
Stanna där.

462
00:18:48,690 --> 00:18:50,520
Så Linda, du kommer runt först.

463
00:18:50,520 --> 00:18:53,820
>> Nu i verkligheten om det bara är en array
vi kunde bara flytta henne i realtid

464
00:18:53,820 --> 00:18:55,360
från den här stolen till denna plats.

465
00:18:55,360 --> 00:18:57,770
Så antar att tog någon konstant
antal steg 1.

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

467
00:18:58,480 --> 00:19:01,490
men vi måste sätta dig in
den första platsen här.

468
00:19:01,490 --> 00:19:03,930
>> Och nu om du kan komma runt,
liksom, vi ska

469
00:19:03,930 --> 00:19:06,300
vara i läge två.

470
00:19:06,300 --> 00:19:09,120
Och även om det känns som det är
ta en stund, vad trevligt nu är

471
00:19:09,120 --> 00:19:14,710
att den vänstra halvan av
vänstra halvan sorteras nu.

472
00:19:14,710 --> 00:19:18,010
Så vad var nästa steg, om vi nu
spola vidare i berättelsen?

473
00:19:18,010 --> 00:19:18,980
>> Publik: Höger halva.

474
00:19:18,980 --> 00:19:19,900
>> DAVID MALAN: sortera högra halvan.

475
00:19:19,900 --> 00:19:21,320
Så ni måste göra det här, liksom.

476
00:19:21,320 --> 00:19:23,510
Så om du kunde stå upp
för bara ett ögonblick?

477
00:19:23,510 --> 00:19:25,192
Och vad heter du?

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, så Jess är nu vänster
hälften av den högra halvan.

481
00:19:29,720 --> 00:19:31,400
Och så är hon en lista med storlek 1.

482
00:19:31,400 --> 00:19:32,380
Hon har uppenbarligen sorteras.

483
00:19:32,380 --> 00:19:33,070
Och ditt namn igen?

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

485
00:19:33,630 --> 00:19:35,340
>> DAVID MALAN: Michelle är uppenbarligen
en lista med storlek 1.

486
00:19:35,340 --> 00:19:36,050
Hon har redan sorterade.

487
00:19:36,050 --> 00:19:38,690
Så nu det magiska händer,
sammanslagning processen.

488
00:19:38,690 --> 00:19:39,790
Så vem ska komma först?

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

490
00:19:41,560 --> 00:19:43,280
Så om du kunde komma runt tillbaka.

491
00:19:43,280 --> 00:19:47,090
Det utrymme vi har för henne nu
är bakom denna stol här.

492
00:19:47,090 --> 00:19:51,580
Och nu om du kunde komma tillbaka också,
vi har nu, för att vara tydlig, två

493
00:19:51,580 --> 00:19:53,810
halvor, vardera av storlek 2 -

494
00:19:53,810 --> 00:19:57,090
och bara för avbildning skull, om du
kunde göra en liten bit av ett utrymme -

495
00:19:57,090 --> 00:19:59,780
en vänster halva här, en
högra halvan här.

496
00:19:59,780 --> 00:20:01,160
>> Rewind vidare i berättelsen.

497
00:20:01,160 --> 00:20:02,270
Vilket steg är nästa?

498
00:20:02,270 --> 00:20:03,030
>> Publiken: Merge.

499
00:20:03,030 --> 00:20:04,160
>> DAVID MALAN: Så nu måste vi gå samman.

500
00:20:04,160 --> 00:20:07,490
Så OK, så nu, tack och lov, vi
bara frigjort fyra stolar.

501
00:20:07,490 --> 00:20:11,480
Så vi har använt dubbelt så mycket minne, men
vi kan ge flip-floppa mellan

502
00:20:11,480 --> 00:20:12,330
de två uppsättningarna.

503
00:20:12,330 --> 00:20:14,190
Så vilket nummer är att komma först?

504
00:20:14,190 --> 00:20:14,850
Så Michelle, uppenbarligen.

505
00:20:14,850 --> 00:20:16,680
Så kom runt och ta
din plats här.

506
00:20:16,680 --> 00:20:19,120
Och då nummer 2 är uppenbarligen
nästa, så att du kommer hit.

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

508
00:20:21,520 --> 00:20:23,390
Och igen, även om det finns en
lite inblandade promenader,

509
00:20:23,390 --> 00:20:26,010
egentligen, kan dessa ske omedelbart,
genom att flytta en -

510
00:20:26,010 --> 00:20:26,880
OK, välspelad.

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

512
00:20:28,350 --> 00:20:29,680
>> DAVID MALAN: Och nu är vi
i ganska bra form.

513
00:20:29,680 --> 00:20:34,910
Den vänstra halvan av hela
ingången har nu sorterats.

514
00:20:34,910 --> 00:20:37,370
Okej, så dessa killar hade
fördelen av mitt -

515
00:20:37,370 --> 00:20:40,340
hur gick det till slut alla flickor på
vänster och alla pojkar till höger?

516
00:20:40,340 --> 00:20:42,450
>> OK, så killarnas tur nu.

517
00:20:42,450 --> 00:20:44,680
Så jag inte kommer att gå igenom
dessa steg.

518
00:20:44,680 --> 00:20:46,550
Vi ska se om vi kan återanvända
samma pseudokod.

519
00:20:46,550 --> 00:20:50,050
Om du vill gå vidare och stå upp,
och ni, låt mig ge er mic.

520
00:20:50,050 --> 00:20:52,990
Se om du inte kan replikera vad
Vi gjorde bara här på

521
00:20:52,990 --> 00:20:53,880
andra änden av listan.

522
00:20:53,880 --> 00:20:59,530
Vem behöver tala först,
baserat på algoritmen?

523
00:20:59,530 --> 00:21:03,210
Så förklara vad du gör innan
du gör några fot rörelser.

524
00:21:03,210 --> 00:21:05,930
>> Högtalare 1: Okej, så eftersom
Jag är den vänstra halvan av

525
00:21:05,930 --> 00:21:07,790
vänstra halvan, återvänder jag.

526
00:21:07,790 --> 00:21:08,730
Rätt?

527
00:21:08,730 --> 00:21:09,250
>> DAVID MALAN: Bra.

528
00:21:09,250 --> 00:21:10,350
>> Högtalare 1: Och sedan -

529
00:21:10,350 --> 00:21:11,800
>> DAVID MALAN: Vem gör
MIC gå till nästa?

530
00:21:11,800 --> 00:21:12,920
>> Högtalare 1: nästa nummer.

531
00:21:12,920 --> 00:21:14,720
>> Högtalare 2: Så jag är den högra halvan
av den vänstra halvan av

532
00:21:14,720 --> 00:21:17,830
vänstra halvan, och jag återvänder.

533
00:21:17,830 --> 00:21:18,050
>> DAVID MALAN: Bra.

534
00:21:18,050 --> 00:21:18,550
Du återvänder.

535
00:21:18,550 --> 00:21:21,855
Så nu vad är nästa för er?

536
00:21:21,855 --> 00:21:23,740
>> Högtalare 2: Vi vill se vem som är mindre.

537
00:21:23,740 --> 00:21:24,200
>> DAVID MALAN: Exakt.

538
00:21:24,200 --> 00:21:24,940
Vi vill slå samman.

539
00:21:24,940 --> 00:21:27,590
Det utrymme vi kommer att använda för att slå samman
dig in i, även om de är

540
00:21:27,590 --> 00:21:30,250
uppenbarligen sorteras redan, vi ska
att följa samma algoritm.

541
00:21:30,250 --> 00:21:31,560
Så vem går i ryggen först?

542
00:21:31,560 --> 00:21:35,720
Så 3, och därefter 7.

543
00:21:35,720 --> 00:21:38,570
Och nu mic går
dessa killar, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Så jag är den högra halvan av
vänstra halvan, och min n är mindre än

545
00:21:43,590 --> 00:21:45,048
1, så jag ska bara passera -

546
00:21:45,048 --> 00:21:46,380
>> DAVID MALAN: Bra.

547
00:21:46,380 --> 00:21:49,450
>> Högtalare 4: Jag är den högra halvan av
högra halvan av den högra halvan, och jag är

548
00:21:49,450 --> 00:21:51,740
även en person, så jag är
kommer att återvända.

549
00:21:51,740 --> 00:21:52,990
Så nu vi samman.

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

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Så vi går tillbaka.

552
00:21:56,150 --> 00:21:57,160
>> DAVID MALAN: Så du går in på baksidan.

553
00:21:57,160 --> 00:21:59,200
Så 5 går först, och sedan 8.

554
00:21:59,200 --> 00:22:01,240
Och nu publik, vilket är den
steg vi nu spola tillbaka

555
00:22:01,240 --> 00:22:02,200
tillbaka i våra sinnen?

556
00:22:02,200 --> 00:22:02,940
>> Publiken: Merge.

557
00:22:02,940 --> 00:22:07,270
>> DAVID MALAN: Sammanslagning vänstra och högra
hälften av den ursprungliga vänstra halvan.

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

559
00:22:08,840 --> 00:22:10,520
och bara för att klargöra detta,
göra lite utrymme

560
00:22:10,520 --> 00:22:11,690
mellan er två killar.

561
00:22:11,690 --> 00:22:13,800
Så nu det är de två listorna,
vänster och höger.

562
00:22:13,800 --> 00:22:18,320
Så hur sammanfoga vi nu er in
den främre stolsraden igen?

563
00:22:18,320 --> 00:22:19,600
>> 3 går först.

564
00:22:19,600 --> 00:22:20,850
Sedan 5, uppenbarligen.

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

566
00:22:23,110 --> 00:22:27,330
Sedan 7, och nu 8.

567
00:22:27,330 --> 00:22:28,710
OK, och nu är vi?

568
00:22:28,710 --> 00:22:29,650
>> Publik: Inte gjort.

569
00:22:29,650 --> 00:22:32,440
>> DAVID MALAN: Inte gjort, eftersom
självklart, det finns ett steg kvar.

570
00:22:32,440 --> 00:22:35,720
Men återigen, anledningen till att jag använder detta
jargong som "bakåt i ditt sinne,"

571
00:22:35,720 --> 00:22:37,160
det är för att det är egentligen
vad som händer.

572
00:22:37,160 --> 00:22:39,610
Vi går igenom alla dessa steg,
men vi sorts pausa för ett

573
00:22:39,610 --> 00:22:42,480
ögonblick, dyka djupare in i
algoritm, pausa för ett ögonblick,

574
00:22:42,480 --> 00:22:45,840
dykning djupare in i algoritmen, och
nu måste vi sortera av bakåt i vår

575
00:22:45,840 --> 00:22:49,430
sinnen och ångra alla dessa skikt
att vi har sorts parkeras.

576
00:22:49,430 --> 00:22:51,790
>> Så nu har vi två listor med storlek 4.

577
00:22:51,790 --> 00:22:54,790
Om ni kunde stå upp för sista gången
och göra lite utrymme här att

578
00:22:54,790 --> 00:22:57,230
göra klart att detta är den vänstra
hälften av den ursprungliga, den

579
00:22:57,230 --> 00:22:58,620
högra hälften av den ursprungliga.

580
00:22:58,620 --> 00:23:01,060
Vem är det första numret som vi
behöva dra in på baksidan?

581
00:23:01,060 --> 00:23:01,870
Michelle, förstås.

582
00:23:01,870 --> 00:23:03,230
>> Så vi satte Michelle här.

583
00:23:03,230 --> 00:23:05,080
Och vem har nummer 2?

584
00:23:05,080 --> 00:23:06,440
Nummer 2 kommer på baksidan också.

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

586
00:23:07,800 --> 00:23:08,510
Utmärkt.

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

588
00:23:16,570 --> 00:23:18,850
>> OK, så det kändes som en hel
steg, for sure.

589
00:23:18,850 --> 00:23:22,390
Men nu ska vi se om vi inte kan bekräfta
sorts intuitivt att detta

590
00:23:22,390 --> 00:23:26,190
algoritm grunden, särskilt som
n blir riktigt stora, som vi har sett

591
00:23:26,190 --> 00:23:29,170
med animationer, är
fundamentalt snabbare.

592
00:23:29,170 --> 00:23:33,400
Så jag hävdar denna algoritm i värsta
fallet och även i bästa fall

593
00:23:33,400 --> 00:23:36,160
är stor O n gånger log n.

594
00:23:36,160 --> 00:23:39,160
Det vill säga, det finns någon aspekt av denna
algoritm, som tar n steg, men

595
00:23:39,160 --> 00:23:43,110
det finns en annan aspekt någonstans i
denna iteration, att kretsa, som

596
00:23:43,110 --> 00:23:44,410
tar log n steg.

597
00:23:44,410 --> 00:23:49,154
Kan vi sätta fingret på vad de
två siffror hänvisar till?

598
00:23:49,154 --> 00:23:51,320
Tja, där -

599
00:23:51,320 --> 00:23:54,160
där skulle micken gå?

600
00:23:54,160 --> 00:23:58,660
>> Högtalare 1: Skulle log n vara
bryta oss upp i två -

601
00:23:58,660 --> 00:23:59,630
dividera med två, i huvudsak.

602
00:23:59,630 --> 00:24:00,120
>> DAVID MALAN: Exakt.

603
00:24:00,120 --> 00:24:03,000
Varje gång vi ser i någon algoritm därmed
långt, det har varit detta mönster av

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

605
00:24:04,200 --> 00:24:05,700
Och det är oftast minskas
till något som är

606
00:24:05,700 --> 00:24:07,100
logaritmisk, log bas 2.

607
00:24:07,100 --> 00:24:10,180
Men det skulle verkligen vara något,
men log bas 2.

608
00:24:10,180 --> 00:24:11,330
>> Nu vad om n?

609
00:24:11,330 --> 00:24:14,550
Jag kan se att vi typ av delat er
killar - delat dig, uppdelat dig,

610
00:24:14,550 --> 00:24:15,910
delat dig, uppdelat dig.

611
00:24:15,910 --> 00:24:18,760
Var kommer utgången från?

612
00:24:18,760 --> 00:24:19,810
>> Så det är en sammanslagning.

613
00:24:19,810 --> 00:24:20,610
Eftersom tänka på det.

614
00:24:20,610 --> 00:24:25,420
När du sammanfogar åtta personer tillsammans,
varigenom hälften av dem är en uppsättning av fyra

615
00:24:25,420 --> 00:24:27,770
och den andra hälften är en annan
uppsättning av fyra, hur du går

616
00:24:27,770 --> 00:24:28,820
om att göra en sammanslagning?

617
00:24:28,820 --> 00:24:30,830
Tja, gjorde ni det
ganska intuitivt.

618
00:24:30,830 --> 00:24:34,140
>> Men om jag istället gjorde det lite mer
metodiskt, kanske jag har pekat på

619
00:24:34,140 --> 00:24:38,090
den vänstra personen först med min vänstra
handen, pekade på den vänstra personen

620
00:24:38,090 --> 00:24:42,080
av att hälften med min högra hand, och
precis därefter gick genom

621
00:24:42,080 --> 00:24:46,990
listan, pekar på det minsta elementet
varje gång, flytta fingret över och

622
00:24:46,990 --> 00:24:48,970
över som behövs hela listan.

623
00:24:48,970 --> 00:24:51,890
Men vad är nyckeln om denna sammanslagning
Processen är jag jämföra dessa par

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

625
00:24:53,460 --> 00:24:57,270
Från den högra halvan och från vänster
hälften, jag har aldrig en gång backa.

626
00:24:57,270 --> 00:25:00,570
>> Så sammanfogningen själv tar
inte mer än n steg.

627
00:25:00,570 --> 00:25:03,250
Och hur många gånger har jag har
att göra det ihop?

628
00:25:03,250 --> 00:25:07,150
Tja, inte mer än N, och vi bara
såg att den slutliga sammanfogningen.

629
00:25:07,150 --> 00:25:13,120
Och så om du gör något som tar
log n steg n gånger, eller vice versa,

630
00:25:13,120 --> 00:25:15,210
det kommer att ge oss n gånger log n.

631
00:25:15,210 --> 00:25:16,310
>> Och varför är det bättre?

632
00:25:16,310 --> 00:25:19,600
Tja, om vi vet redan att log
n är bättre än N - rätt?

633
00:25:19,600 --> 00:25:22,590
Vi såg i binär sökning, telefonboken
exempel var log n definitivt

634
00:25:22,590 --> 00:25:23,760
bättre än linjär.

635
00:25:23,760 --> 00:25:28,420
Så det betyder att n gånger log n är
definitivt bättre än n gånger en annan

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

637
00:25:30,390 --> 00:25:32,400
Och det är vad vi i slutändan känner.

638
00:25:32,400 --> 00:25:34,928
>> Så stor applåd, om
vi kunde, för killarna.

639
00:25:34,928 --> 00:25:38,920
>> [Applåder]

640
00:25:38,920 --> 00:25:41,550
>> DAVID MALAN: Och dina gåvor avsked -
du kan hålla tal,

641
00:25:41,550 --> 00:25:44,010
om du skulle vilja.

642
00:25:44,010 --> 00:25:45,620
Och din avskedsgåva, som vanligt.

643
00:25:45,620 --> 00:25:47,290
Åh, och vi kommer att skicka dig
filmen, Michelle.

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

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

646
00:25:49,250 --> 00:25:50,400
Hjälp dig själv till en stress boll.

647
00:25:50,400 --> 00:25:54,110
>> Och låt mig dra upp, under tiden,
vår vän Rob Bowden att erbjuda

648
00:25:54,110 --> 00:25:59,520
något annorlunda perspektiv på detta,
eftersom du kan tänka på dessa

649
00:25:59,520 --> 00:26:01,280
steg sker i en något
annat sätt.

650
00:26:01,280 --> 00:26:04,750
I själva verket, den set-up för vad Rob handlar om
att visa oss utgår från att vi har

651
00:26:04,750 --> 00:26:09,030
redan gjort uppdelningen av
stor lista i åtta små listor,

652
00:26:09,030 --> 00:26:10,570
varje storlek 1.

653
00:26:10,570 --> 00:26:13,350
>> Så vi ändrar pseudokoden en
lite bara för att sortera av få på

654
00:26:13,350 --> 00:26:15,320
grundidé om hur det överlåtande fungerar.

655
00:26:15,320 --> 00:26:17,600
Men speltid för vad
han är på väg att göra är fortfarande

656
00:26:17,600 --> 00:26:19,110
kommer att vara samma.

657
00:26:19,110 --> 00:26:23,540
Och återigen, är set-up här att han är
börjat med åtta listor med storlek 1.

658
00:26:23,540 --> 00:26:27,730
Så du har missat den delen där han är
faktiskt gjort log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
dividera på ingången.

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

661
00:26:32,120 --> 00:26:33,615
>> -Det är det för steg ett.

662
00:26:33,615 --> 00:26:38,270
För två steg, upprepade
samman par av listor.

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

664
00:26:39,210 --> 00:26:41,270
Endast ljud kommer
ur min dator.

665
00:26:41,270 --> 00:26:42,520
Låt oss prova det här igen.

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

667
00:26:45,330 --> 00:26:48,310
>> -Just godtyckligt välja vilka -
Nu har vi fyra listor.

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

669
00:26:51,590 --> 00:26:52,120
Läs innan.

670
00:26:52,120 --> 00:26:53,040
>> DAVID MALAN: Det gå vi.

671
00:26:53,040 --> 00:27:00,510
>> -Sammanslagningen 108 och 15, slutar vi
upp med listan 15, 108.

672
00:27:00,510 --> 00:27:07,170
Sammanslagning 50 och 4, vi
sluta med 4, 50.

673
00:27:07,170 --> 00:27:12,990
Sammanslagning 8 och 42, vi
sluta med 8, 42.

674
00:27:12,990 --> 00:27:19,970
Och sammanslagning 23 och 16, vi
sluta med 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Nu är alla våra listor är av storlek 2.

676
00:27:23,270 --> 00:27:26,690
Lägg märke till att var och en av
fyra listor sorteras.

677
00:27:26,690 --> 00:27:29,450
Så vi kan börja sammanslagning
par listorna igen.

678
00:27:29,450 --> 00:27:38,420
Sammanslagning 15 och 108 och 4 och 50, vi
först ta 4, sedan 15, sedan

679
00:27:38,420 --> 00:27:41,500
den 50, sedan 108.

680
00:27:41,500 --> 00:27:50,610
Sammanslagning 8, 42 och 16, 23, tar vi först
den 8, sedan 16, sedan 23,

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

682
00:27:52,700 --> 00:27:57,600
>> Så nu har vi bara två listor med storlek
4, är var och en sorteras.

683
00:27:57,600 --> 00:28:01,170
Så nu vi samman dessa två listor.

684
00:28:01,170 --> 00:28:11,835
Först tar vi 4, då vi tar
8, sedan tar vi det 15, sedan 16, sedan

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

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

687
00:28:19,872 --> 00:28:23,430
>> DAVID MALAN: Igen, varsel, aldrig han
rörde en viss kopp mer än en gång

688
00:28:23,430 --> 00:28:24,860
efter att avancera bortom det.

689
00:28:24,860 --> 00:28:26,200
Så han aldrig upprepa.

690
00:28:26,200 --> 00:28:29,850
Så han alltid flytta åt sidan,
och det är där vi fick vår n..

691
00:28:29,850 --> 00:28:33,290
>> Varför inte låta mig dra upp en animation
som vi såg tidigare, men den här gången

692
00:28:33,290 --> 00:28:35,110
fokusera enbart på merge sort.

693
00:28:35,110 --> 00:28:38,030
Låt mig gå vidare och zooma
in på detta här.

694
00:28:38,030 --> 00:28:42,530
Först låt mig välja en slumpmässig indata,
förstärka detta, och du kan sortera på se

695
00:28:42,530 --> 00:28:46,600
vad vi tog för givet, tidigare,
sammanfoga Sortera faktiskt gör.

696
00:28:46,600 --> 00:28:50,330
>> Så märker att du får dessa halvor eller
dessa kvartal eller dessa åttondelar av

697
00:28:50,330 --> 00:28:53,140
problem som helt plötsligt
börjar ta god form.

698
00:28:53,140 --> 00:28:57,070
Och slutligen, ser du på
slutet att bam,

699
00:28:57,070 --> 00:28:58,860
allt slås ihop.

700
00:28:58,860 --> 00:29:01,690
>> Så dessa är bara tre olika
tar på samma idé.

701
00:29:01,690 --> 00:29:05,980
Men den viktigaste insikten, precis som klyftan
och erövra i den allra första klassen,

702
00:29:05,980 --> 00:29:10,640
var att vi bestämde att på något sätt dela
problemet till något stort, till

703
00:29:10,640 --> 00:29:14,760
något slags identiska i anden,
men mindre och mindre och mindre

704
00:29:14,760 --> 00:29:15,660
och mindre.

705
00:29:15,660 --> 00:29:18,420
>> Nu ett annat roligt sätt att sortera om tro
om dessa, även om det inte är

706
00:29:18,420 --> 00:29:20,520
kommer att ge dig samma intuitiva
förståelse, är

707
00:29:20,520 --> 00:29:21,640
Följande animation.

708
00:29:21,640 --> 00:29:25,400
Så det här är en video någon sätta ihop
den associerad annorlunda

709
00:29:25,400 --> 00:29:29,970
ljud med de olika verksamheterna för
insättning sortera, för merge sort, och

710
00:29:29,970 --> 00:29:31,150
ett par andra.

711
00:29:31,150 --> 00:29:32,330
Så i ett ögonblick, jag ska träffa Play.

712
00:29:32,330 --> 00:29:33,600
Det handlar om en minut lång.

713
00:29:33,600 --> 00:29:37,410
Och även om du kan fortfarande se
mönster som händer, den här gången kan du

714
00:29:37,410 --> 00:29:41,420
också höra hur dessa algoritmer är
utför olika sätt och med

715
00:29:41,420 --> 00:29:43,950
något olika mönster.

716
00:29:43,950 --> 00:29:45,830
>> Detta är införandet sort.

717
00:29:45,830 --> 00:29:50,400
>> [TONER SPELA]

718
00:29:50,400 --> 00:29:52,400
>> DAVID MALAN: Det igen försöker
att infoga varje element

719
00:29:52,400 --> 00:29:52,900
in där det hör hemma.

720
00:29:52,900 --> 00:29:54,628
Detta är bubbla sortera.

721
00:29:54,628 --> 00:30:10,097
>> [TONER SPELA]

722
00:30:10,097 --> 00:30:13,630
>> DAVID MALAN: Och du kan sortera på känsla
hur relativt lite arbete det gör

723
00:30:13,630 --> 00:30:15,834
på varje steg.

724
00:30:15,834 --> 00:30:20,470
Detta är vad TRÅKIGHET låter som.

725
00:30:20,470 --> 00:30:21,472
>> [TONER SPELA]

726
00:30:21,472 --> 00:30:25,222
>> DAVID MALAN: Detta är selection sort,
där vi väljer det element vi vill genom

727
00:30:25,222 --> 00:30:28,845
går igenom igen och igen och igen
och sätta det i början.

728
00:30:28,845 --> 00:30:37,674
>> [TONER SPELA]

729
00:30:37,674 --> 00:30:43,970
>> DAVID MALAN: Detta är samman sort, vilket
du kan verkligen börja känna.

730
00:30:43,970 --> 00:30:51,810
>> [TONER SPELA]

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

732
00:30:54,770 --> 00:30:58,395
>> DAVID MALAN: Något som kallas GNOME
Sortera, vilket vi inte har tittat på.

733
00:30:58,395 --> 00:31:13,630
>> [TONER SPELA]

734
00:31:13,630 --> 00:31:17,910
>> DAVID MALAN: Så låt mig se, nu,
distraherad när du förhoppningsvis är av

735
00:31:17,910 --> 00:31:21,110
musik, om jag kan glida lite
bit av matematik i här.

736
00:31:21,110 --> 00:31:24,850
Så det finns en fjärde sätt att vi kan
tänka på vad det innebär dessa

737
00:31:24,850 --> 00:31:29,210
funktioner för att vara snabbare än de
som vi har sett tidigare.

738
00:31:29,210 --> 00:31:32,470
Och om du kommer på kursen från
en matematik bakgrund, du

739
00:31:32,470 --> 00:31:36,030
faktiskt vet kanske redan att du
kan smälla en term på denna teknik -

740
00:31:36,030 --> 00:31:40,400
nämligen rekursion, en funktion
som kallar sig av någon anledning.

741
00:31:40,400 --> 00:31:44,780
>> Och igen, minns att merge sort
pseudokod var rekursiv i den meningen

742
00:31:44,780 --> 00:31:48,460
att en av merge sort fotspår
var att ringa sort -

743
00:31:48,460 --> 00:31:49,740
som i sig själv.

744
00:31:49,740 --> 00:31:52,480
Men tack och lov, eftersom vi höll
ringer sortera, eller slå samman sortera,

745
00:31:52,480 --> 00:31:55,880
specifikt, på en mindre och mindre
och mindre lista, så småningom vi

746
00:31:55,880 --> 00:32:00,005
bottnat tack vare vad vi kallar
ett basfall, den hårdkodade fall som

747
00:32:00,005 --> 00:32:04,270
sade om listan är liten, mindre än 2
i så fall, bara omedelbart återvända.

748
00:32:04,270 --> 00:32:07,550
Om vi ​​inte har den där speciella fall
algoritm skulle aldrig bottna,

749
00:32:07,550 --> 00:32:11,010
och du skulle verkligen komma in i en
oändlig loop verkligen evigt.

750
00:32:11,010 --> 00:32:14,330
>> Men antag att vi ville nu sätta
några siffror på detta, återigen, med n

751
00:32:14,330 --> 00:32:15,660
som storleken på den ingående.

752
00:32:15,660 --> 00:32:18,680
Och jag ville fråga dig, vad är
den totala tid som krävs för

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

754
00:32:19,800 --> 00:32:22,960
Eller mer generellt, vad är
kostnaden för det i tid?

755
00:32:22,960 --> 00:32:24,730
>> Jo det är ganska lätt att mäta det.

756
00:32:24,730 --> 00:32:29,010
Om n är mindre än 2, den tid det tar
i sortering n element,

757
00:32:29,010 --> 00:32:30,480
där n är 2, är 0.

758
00:32:30,480 --> 00:32:31,410
Eftersom vi tillbaka bara.

759
00:32:31,410 --> 00:32:32,510
Det finns inget arbete att göra.

760
00:32:32,510 --> 00:32:35,660
Nu vågar jag påstå, det är kanske ett steg eller två
steg för att räkna ut mängden

761
00:32:35,660 --> 00:32:38,420
arbete, men det är tillräckligt nära 0 som
Jag kommer bara att säga nej arbetet är

762
00:32:38,420 --> 00:32:40,940
krävs om listan är så liten
vara ointressant.

763
00:32:40,940 --> 00:32:42,580
>> Men det här fallet är intressant.

764
00:32:42,580 --> 00:32:47,320
Den rekursiva fallet var den gren av
pseudokoden att nämnda annat, sortera

765
00:32:47,320 --> 00:32:52,000
den vänstra halvan, sortera rätt
hälften, slå ihop de två halvorna.

766
00:32:52,000 --> 00:32:55,530
Nu varför detta uttryck
representerar denna kostnad?

767
00:32:55,530 --> 00:32:58,690
Tja, betyder T n bara
tid att sortera n element.

768
00:32:58,690 --> 00:33:03,070
Och sedan på den högra sidan av
likhetstecken där, delade T n

769
00:33:03,070 --> 00:33:06,600
av 2 hänvisar till kostnaden för vad?

770
00:33:06,600 --> 00:33:07,570
Sortering den vänstra halvan.

771
00:33:07,570 --> 00:33:10,990
Den andra T från n delat med två är
förmodligen med hänvisning till kostnaden för

772
00:33:10,990 --> 00:33:12,390
sortera den högra halvan.

773
00:33:12,390 --> 00:33:14,590
>> Och sedan plus n?

774
00:33:14,590 --> 00:33:15,420
Är en sammanslagning.

775
00:33:15,420 --> 00:33:19,120
För om du har två listor, en för
storlek n över 2 och ett annat av storlek n

776
00:33:19,120 --> 00:33:22,580
över 2, måste du i huvudsak beröra
vart och ett av dessa element, precis som Rob

777
00:33:22,580 --> 00:33:24,990
berörde alla kopparna, och bara
som vi pekade på var och en av

778
00:33:24,990 --> 00:33:26,310
volontärer på scenen.

779
00:33:26,310 --> 00:33:28,790
Så n är på bekostnad av sammanslagning.

780
00:33:28,790 --> 00:33:31,780
>> Nu tyvärr, denna formel
är också i sig rekursiv.

781
00:33:31,780 --> 00:33:36,390
Så om ställde frågan, om n är, säg,
16, om det finns 16 personer på scenen

782
00:33:36,390 --> 00:33:40,670
eller 16 koppar i videon, hur många totalt
steg tar det att sortera dem

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

784
00:33:41,550 --> 00:33:45,790
Det är faktiskt inte ett självklart svar,
eftersom du nu har att sortera av

785
00:33:45,790 --> 00:33:48,500
rekursivt besvara denna formel.

786
00:33:48,500 --> 00:33:51,190
>> Men det är OK, eftersom låt mig föreslå
att vi gör följande.

787
00:33:51,190 --> 00:33:56,670
Den tid det tar att sortera 16 personer eller
16 koppar kommer att vara representerade

788
00:33:56,670 --> 00:33:58,020
generellt som T 16.

789
00:33:58,020 --> 00:34:01,400
Men det är lika, enligt vår
föregående formel, två gånger så mycket

790
00:34:01,400 --> 00:34:04,780
tid det tar att sortera
8 koppar plus 16.

791
00:34:04,780 --> 00:34:08,590
Och återigen, är plus 16 tiden att gå samman,
och två gånger T av 8 är den

792
00:34:08,590 --> 00:34:10,790
tid att sortera vänstra och högra halvan.

793
00:34:10,790 --> 00:34:11,989
>> Men återigen, är detta inte tillräckligt.

794
00:34:11,989 --> 00:34:13,210
Vi måste dyka in djupare.

795
00:34:13,210 --> 00:34:16,409
Detta innebär att vi måste svara på
Frågan, vad är T på 8?

796
00:34:16,409 --> 00:34:19,610
Jo T av 8 är bara 2
gånger T 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
Tja, vad är T 4?

798
00:34:20,520 --> 00:34:23,780
T 4 är bara 2 gånger T om 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
Tja, vad är T 2?

800
00:34:25,489 --> 00:34:29,030
T 2 är bara 2 ggr T av 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> Och återigen, vi är typ att få
fastnat i denna cykel.

802
00:34:31,940 --> 00:34:34,790
Men det handlar om att träffa den
sk basfall.

803
00:34:34,790 --> 00:34:37,310
För vad är T 1, vi påstår?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Så nu äntligen, kan vi arbeta bakåt.

806
00:34:39,730 --> 00:34:44,290
>> Om T 1 är 0, kan jag nu gå tillbaka upp en
linje till den här killen här, och jag kan

807
00:34:44,290 --> 00:34:46,330
plug in 0 för T 1.

808
00:34:46,330 --> 00:34:51,770
Så det betyder att det är lika med 2 gånger noll,
annars känd som 0, plus 2.

809
00:34:51,770 --> 00:34:53,739
Och så att hela uttrycket är 2.

810
00:34:53,739 --> 00:34:58,740
>> Nu om jag tar T 2, vars svar
är 2, anslut den till den mellersta raden, T

811
00:34:58,740 --> 00:35:02,740
av 4, ger det mig 2 gånger
2 plus 4, så 8.

812
00:35:02,740 --> 00:35:07,080
Om jag ansluter sedan i 8 till föregående
line, ger det mig 2 gånger 8, 16.

813
00:35:07,080 --> 00:35:12,470
Och om vi fortsätter sedan att med
24, lägga i 16, får vi äntligen en

814
00:35:12,470 --> 00:35:13,820
värde av 64.

815
00:35:13,820 --> 00:35:18,480
>> Nu det i och för sig sorts talar
ingenting till N notation, den

816
00:35:18,480 --> 00:35:20,700
stort O, den omega som vi har
pratat om.

817
00:35:20,700 --> 00:35:24,890
Men det visar sig att 64 verkligen är
16, storleken av den ingående,

818
00:35:24,890 --> 00:35:27,110
log bas 2 av 16.

819
00:35:27,110 --> 00:35:30,200
Och om detta är en liten främmande, bara
tänker tillbaka, och det kommer tillbaka

820
00:35:30,200 --> 00:35:30,700
till dig så småningom.

821
00:35:30,700 --> 00:35:33,775
Om detta är log bas 2, det är som två
upphöjt till vad som ger dig 16?

822
00:35:33,775 --> 00:35:36,380
Åh, det är 4, så det är 16 gånger 4.

823
00:35:36,380 --> 00:35:39,380
>> Och återigen, det är inte en stor sak om detta
är en slags dimmig minne nu.

824
00:35:39,380 --> 00:35:43,720
Men för nu, ta på tro
att 16 log 16 är 64.

825
00:35:43,720 --> 00:35:46,590
Och så faktiskt, med denna enkla förstånd
kolla, har vi bekräftat -

826
00:35:46,590 --> 00:35:48,250
men inte visat formellt -

827
00:35:48,250 --> 00:35:52,800
att gångtiden för Merge
sort är verkligen n log n.

828
00:35:52,800 --> 00:35:53,790
>> Så inte illa.

829
00:35:53,790 --> 00:35:57,260
Det är definitivt bättre än den
algoritmer vi har sett hittills, och

830
00:35:57,260 --> 00:36:00,710
Det beror på att vi har belånade, en,
en teknik som kallas rekursion.

831
00:36:00,710 --> 00:36:03,880
Men mer intressant än så, att
begreppet dela och erövra.

832
00:36:03,880 --> 00:36:07,460
Igen, verkligen vecka 0 saker som
redan nu är återkommande i ett

833
00:36:07,460 --> 00:36:08,740
mer övertygande sätt.

834
00:36:08,740 --> 00:36:11,750
>> Nu en rolig liten övning, om du har
aldrig gjort detta - och du förmodligen

835
00:36:11,750 --> 00:36:14,660
inte skulle ha, eftersom slags normal
folk tror inte att göra detta.

836
00:36:14,660 --> 00:36:20,650
Men om jag går till google.com och om
Jag vill lära sig något om

837
00:36:20,650 --> 00:36:22,356
rekursion, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [SKRATT]

840
00:36:29,058 --> 00:36:32,030
[Mera skratt]

841
00:36:32,030 --> 00:36:33,385
DAVID MALAN: Bad joke sakta sprider sig.

842
00:36:33,385 --> 00:36:34,450
[SKRATT]

843
00:36:34,450 --> 00:36:36,970
DAVID MALAN: Just i fallet, det är där.

844
00:36:36,970 --> 00:36:38,710
Jag visste inte stava det fel,
och det är skämt.

845
00:36:38,710 --> 00:36:40,810
Okej.

846
00:36:40,810 --> 00:36:42,950
Förklara det för människor bredvid dig om
Det har inte riktigt klickat ännu.

847
00:36:42,950 --> 00:36:47,650
Men rekursion, mer allmänt, hänvisar
till processen för en funktion ringer

848
00:36:47,650 --> 00:36:51,430
själv, eller mer allmänt, dela ett
problem till något som kan vara

849
00:36:51,430 --> 00:36:56,220
lösas styckevis genom att lösa identiska
representativa problem.

850
00:36:56,220 --> 00:36:58,400
>> Nåväl, låt oss växla
för bara ett ögonblick.

851
00:36:58,400 --> 00:37:00,840
Vi vilja avsluta på vissa cliffhangers,
så låt oss börja att ställa

852
00:37:00,840 --> 00:37:05,870
scenen, i flera minuter,
på en mycket enkel idé -

853
00:37:05,870 --> 00:37:07,620
som att byta två element, eller hur?

854
00:37:07,620 --> 00:37:10,040
Alla dessa algoritmer vi har varit
talar om de senaste par

855
00:37:10,040 --> 00:37:12,420
föreläsningar innebära några
slags byte.

856
00:37:12,420 --> 00:37:14,630
Idag var visualiseras genom dem få
upp ur sina stolar och

857
00:37:14,630 --> 00:37:18,570
gå runt, men i kod, skulle vi
bara ta ett element från en array

858
00:37:18,570 --> 00:37:20,370
och plopp det i en annan.

859
00:37:20,370 --> 00:37:21,880
>> Så hur går vi om att göra detta?

860
00:37:21,880 --> 00:37:24,850
Nåväl, låt mig gå vidare och skriva
en snabb program här.

861
00:37:24,850 --> 00:37:31,600
Jag kommer att gå vidare och göra
detta som följande.

862
00:37:31,600 --> 00:37:33,910
Låt oss kalla detta -

863
00:37:33,910 --> 00:37:38,070
vad vill vi att kalla den här?

864
00:37:38,070 --> 00:37:38,650
>> Nej, faktiskt inte.

865
00:37:38,650 --> 00:37:39,420
Låt mig bakåt.

866
00:37:39,420 --> 00:37:41,220
Jag vill inte göra det
cliffhanger ännu.

867
00:37:41,220 --> 00:37:42,270
Det kommer att förstöra det roliga.

868
00:37:42,270 --> 00:37:43,600
Låt oss göra detta istället.

869
00:37:43,600 --> 00:37:47,430
>> Antag att jag vill skriva ett litet
program och som omfattar nu detta

870
00:37:47,430 --> 00:37:48,700
idén om rekursion.

871
00:37:48,700 --> 00:37:50,370
Jag slags fick framför mig där.

872
00:37:50,370 --> 00:37:51,420
Jag kommer att göra följande.

873
00:37:51,420 --> 00:38:00,220
>> Först en snabb inkludera i standarden io.h,
liksom en include av cs50.h.

874
00:38:00,220 --> 00:38:03,200
Och då jag ska gå vidare
och förklara int main void

875
00:38:03,200 --> 00:38:04,360
på vanligt sätt.

876
00:38:04,360 --> 00:38:07,920
Jag insåg att jag har misnamed filen, så
Låt mig bara lägga till en. c förlängning här så

877
00:38:07,920 --> 00:38:09,510
att vi kan sammanställa det ordentligt.

878
00:38:09,510 --> 00:38:10,970
Börja här funktionen.

879
00:38:10,970 --> 00:38:13,290
>> Och den funktionen jag vill skriva, ganska
helt enkelt, är en som ber

880
00:38:13,290 --> 00:38:16,210
användaren för ett nummer och sedan lägger upp
alla nummer mellan att

881
00:38:16,210 --> 00:38:19,920
antal och, säg, 0.

882
00:38:19,920 --> 00:38:22,510
Så först ska jag gå vidare
och förklara int n.

883
00:38:22,510 --> 00:38:24,760
Då jag kopierar någon kod som
vi har använt på ett tag.

884
00:38:24,760 --> 00:38:26,660
Medan något är sant.

885
00:38:26,660 --> 00:38:28,000
Jag ska återkomma till det om en stund.

886
00:38:28,000 --> 00:38:29,010
>> Vad vill jag göra?

887
00:38:29,010 --> 00:38:33,460
Jag vill säga printf positiv
heltal behaga.

888
00:38:33,460 --> 00:38:36,130
Och sedan ska jag
säga n blir få int.

889
00:38:36,130 --> 00:38:38,800
Så återigen, vissa standardtext kod
som vi har använt tidigare.

890
00:38:38,800 --> 00:38:40,810
Och jag kommer att göra detta
medan n är mindre än 1.

891
00:38:40,810 --> 00:38:44,120
Så detta kommer att säkerställa att användaren
ger mig ett positivt heltal.

892
00:38:44,120 --> 00:38:45,490
>> Och nu ska jag göra följande.

893
00:38:45,490 --> 00:38:51,020
Jag vill lägga upp alla nummer
mellan 1 och och n, eller 0 och n,

894
00:38:51,020 --> 00:38:52,570
ekvivalent, för att få den totala summan.

895
00:38:52,570 --> 00:38:55,100
Så den stora sigma symbolen
som ni kanske minns.

896
00:38:55,100 --> 00:38:59,050
Så jag kommer att göra detta genom att först ringa
en funktion som kallas sigma,

897
00:38:59,050 --> 00:39:06,030
passerar den i N, och sedan kommer jag att
säger printf, är svaret rätt där.

898
00:39:06,030 --> 00:39:08,180
>> Så kort sagt, jag och
int från användaren.

899
00:39:08,180 --> 00:39:09,280
Jag se till att det är positivt.

900
00:39:09,280 --> 00:39:12,700
Jag deklarerar en variabel som heter svar på
typen int och butik i det returen

901
00:39:12,700 --> 00:39:15,610
Värdet av sigma, passerar i n som indata.

902
00:39:15,610 --> 00:39:17,060
Och då ska jag skriva ut det svaret.

903
00:39:17,060 --> 00:39:19,550
>> Tyvärr, trots att sigma låter
som något som kan vara i

904
00:39:19,550 --> 00:39:24,040
den math.h filen, sin förklaring,
det är faktiskt inte.

905
00:39:24,040 --> 00:39:24,690
Så det är OK.

906
00:39:24,690 --> 00:39:26,170
Jag kan genomföra detta själv.

907
00:39:26,170 --> 00:39:29,160
Jag kommer att genomföra en funktion som kallas
sigma, och det kommer att ta ett

908
00:39:29,160 --> 00:39:29,900
parameter -

909
00:39:29,900 --> 00:39:32,100
låt oss bara kalla det m, precis
så det är annorlunda.

910
00:39:32,100 --> 00:39:35,910
Och sedan upp här, jag kommer att säga,
väl, om m är mindre än 1 - detta är en

911
00:39:35,910 --> 00:39:38,180
mycket ointressant program.

912
00:39:38,180 --> 00:39:41,700
Så jag kommer att gå vidare och
omedelbart returnera 0.

913
00:39:41,700 --> 00:39:45,920
Det bara inte vettigt att lägga upp alla
talen mellan 1 och m om m

914
00:39:45,920 --> 00:39:48,470
själv är 0 eller negativ.

915
00:39:48,470 --> 00:39:50,900
>> Och då jag ska gå vidare
och gör detta mycket iterativt.

916
00:39:50,900 --> 00:39:53,090
Jag kommer att göra denna typ av old-school,
och jag ska gå vidare

917
00:39:53,090 --> 00:39:57,150
och säga att jag ska
deklarera en summa för att vara 0.

918
00:39:57,150 --> 00:39:59,630
Sedan kommer jag att ha
en for-loop för int -

919
00:39:59,630 --> 00:40:02,820
och låt mig göra det för att matcha våra
distributionen kod, så att du har en kopia

920
00:40:02,820 --> 00:40:07,500
hemma. int i får 1 på upp till
i är mindre än eller lika med m.

921
00:40:07,500 --> 00:40:09,430
I plus plus.

922
00:40:09,430 --> 00:40:11,430
Och sedan insidan av denna för loop -

923
00:40:11,430 --> 00:40:12,440
Vi är nästan där -

924
00:40:12,440 --> 00:40:15,810
summan blir summa plus 1.

925
00:40:15,810 --> 00:40:17,670
Och sedan ska jag tillbaka summan.

926
00:40:17,670 --> 00:40:19,420
>> Så jag gjorde det snabbt,
ganska visserligen.

927
00:40:19,420 --> 00:40:22,775
Men återigen, är den viktigaste funktionen pretty
okomplicerad, baserad på kod som vi har

928
00:40:22,775 --> 00:40:23,190
skrivit hittills.

929
00:40:23,190 --> 00:40:25,610
Använder dubbla loop för att få en positiv
int från användaren.

930
00:40:25,610 --> 00:40:29,870
Jag passerar då att int till en ny funktion
heter sigma, kalla det, återigen, n..

931
00:40:29,870 --> 00:40:33,100
Och jag lagrar returvärdet, svaret
från den svarta lådan för tillfället

932
00:40:33,100 --> 00:40:35,460
känd som sigma, i en variabel
kallas svar.

933
00:40:35,460 --> 00:40:36,580
Då jag skriver ut det.

934
00:40:36,580 --> 00:40:39,090
>> Om vi ​​nu fortsätter berättelsen,
hur är sigma genomförs?

935
00:40:39,090 --> 00:40:40,840
Jag föreslår att genomföra följande.

936
00:40:40,840 --> 00:40:43,560
Först, en liten bit av felkontroll
att se till att användaren inte är

937
00:40:43,560 --> 00:40:46,480
jävlas med mig och går i
några negativa eller 0 värde.

938
00:40:46,480 --> 00:40:49,710
Då ska jag deklarera en variabel som heter
sammanfatta och ställa den till 0.

939
00:40:49,710 --> 00:40:55,910
>> Och nu börjar jag att flytta från i lika
1 hela vägen upp till och med m,

940
00:40:55,910 --> 00:41:00,130
eftersom jag vill inkludera alla
siffror från ett till m, allomfattande.

941
00:41:00,130 --> 00:41:04,350
Och inne i denna för slinga, gör jag bara
Summan blir vad det är nu, plus

942
00:41:04,350 --> 00:41:08,900
värdet av i.

943
00:41:08,900 --> 00:41:10,370
Plus värdet av jag.

944
00:41:10,370 --> 00:41:14,090
>> Som en parentes, om du inte har sett denna
innan, det finns några syntaktiska socker

945
00:41:14,090 --> 00:41:14,870
för denna linje.

946
00:41:14,870 --> 00:41:21,120
Jag kan skriva om detta som plus lika i,
bara för att rädda mig själv några enkla knapptryckningar

947
00:41:21,120 --> 00:41:22,570
och se lite svalare.

948
00:41:22,570 --> 00:41:23,140
Men det är allt.

949
00:41:23,140 --> 00:41:24,660
Det är funktionellt samma sak.

950
00:41:24,660 --> 00:41:26,710
>> Tyvärr, denna kod är
inte gå att kompilera ännu.

951
00:41:26,710 --> 00:41:31,600
Om jag kör make sigma 0, hur am
Jag kommer att bli utskälld?

952
00:41:31,600 --> 00:41:33,473
Vad kommer det att inte vilja?

953
00:41:33,473 --> 00:41:35,740
>> Publik: [OHÖRBAR].

954
00:41:35,740 --> 00:41:37,800
>> DAVID MALAN: Ja, det gjorde jag inte förklara
funktionen uppe, eller hur?

955
00:41:37,800 --> 00:41:40,590
C är ganska dumt, eftersom det endast
gör vad du säger åt den att göra, och du

956
00:41:40,590 --> 00:41:41,880
måste göra det i den ordningen.

957
00:41:41,880 --> 00:41:45,910
Och så om jag slår in här, kommer jag att
få en varning om sigma implicita

958
00:41:45,910 --> 00:41:46,860
deklaration.

959
00:41:46,860 --> 00:41:48,120
>> Åh, inte ett problem.

960
00:41:48,120 --> 00:41:50,370
Jag kan gå upp till toppen, och jag kan
säga, okej, vänta en minut.

961
00:41:50,370 --> 00:41:54,240
Sigma är en funktion som returnerar
en int och det förväntar sig en

962
00:41:54,240 --> 00:41:56,620
int som indata, semikolon.

963
00:41:56,620 --> 00:41:59,550
Eller jag kunde sätta hela funktionen
över huvud, men i allmänhet, skulle jag

964
00:41:59,550 --> 00:42:02,260
rekommenderar mot detta, eftersom det är
trevligt att alltid ha stora upptill så

965
00:42:02,260 --> 00:42:06,310
du kan dyka rätt in och vet vad en
Programmet gör genom att läsa på först.

966
00:42:06,310 --> 00:42:07,930
>> Så nu låt mig rensa skärmen.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Allt verkar kolla.

969
00:42:10,340 --> 00:42:11,970
Låt mig köra sigma 0.

970
00:42:11,970 --> 00:42:12,770
Positiv inter.

971
00:42:12,770 --> 00:42:15,580
Jag ska ge det numret
3 för att hålla det enkelt.

972
00:42:15,580 --> 00:42:18,710
Så det borde ge mig 3
plus 2 plus en, så 6.

973
00:42:18,710 --> 00:42:20,750
Enter, och faktiskt jag får 6.

974
00:42:20,750 --> 00:42:21,820
>> Jag kan göra något större -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Precis som en tangent, kommer jag att göra
något löjligt som en riktigt stor

977
00:42:27,690 --> 00:42:30,375
nummer, Oh, som faktiskt fungerade -

978
00:42:30,375 --> 00:42:31,600
eh, jag tror inte det är rätt.

979
00:42:31,600 --> 00:42:32,810
Låt oss se.

980
00:42:32,810 --> 00:42:34,060
Låt oss verkligen bråka med den.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Det är ett problem.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Vad är det som händer?

985
00:42:44,970 --> 00:42:46,050
Koden är inte så illa.

986
00:42:46,050 --> 00:42:48,470
Det är fortfarande linjär.

987
00:42:48,470 --> 00:42:50,810
Whistling är en god effekt, men.

988
00:42:50,810 --> 00:42:52,060
Vad är det som händer?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Inte säker på om jag hörde det.

991
00:42:55,620 --> 00:42:57,620
Så visar det sig - och
Detta är som en parentes.

992
00:42:57,620 --> 00:42:59,400
Detta är inte kärnan till
idén om rekursion.

993
00:42:59,400 --> 00:43:02,480
Det visar sig, eftersom jag försöker
representera ett så stort antal, de flesta

994
00:43:02,480 --> 00:43:06,980
sannolikt det är att misstolkas
av C som ett inte positivt tal,

995
00:43:06,980 --> 00:43:09,980
men negativt tal.

996
00:43:09,980 --> 00:43:12,690
>> Vi har inte pratat om det här, men det
visar sig att det finns negativa tal

997
00:43:12,690 --> 00:43:14,210
i världen förutom
till positiva tal.

998
00:43:14,210 --> 00:43:16,290
Och de medel genom vilka du kan
representera ett negativt tal

999
00:43:16,290 --> 00:43:19,530
huvudsak, använder du en
speciell bit för att indikera

1000
00:43:19,530 --> 00:43:20,400
positivt över negativ.

1001
00:43:20,400 --> 00:43:22,950
Det är lite mer komplicerat än så,
men det är den grundläggande idén.

1002
00:43:22,950 --> 00:43:26,740
>> Så tyvärr, om c är förvirrande en
av dessa bitar som verkligen betyder,

1003
00:43:26,740 --> 00:43:30,790
åh, är detta ett negativt tal, min loop
här, till exempel, är faktiskt aldrig

1004
00:43:30,790 --> 00:43:31,740
kommer att upphöra.

1005
00:43:31,740 --> 00:43:33,850
Så om jag faktiskt skriva något
om och om igen, skulle vi

1006
00:43:33,850 --> 00:43:34,650
se en hel del.

1007
00:43:34,650 --> 00:43:36,220
Men återigen, detta är förutom punkten.

1008
00:43:36,220 --> 00:43:38,590
Detta är egentligen bara en sorts
intellektuell nyfikenhet som vi kommer

1009
00:43:38,590 --> 00:43:39,550
tillbaka till så småningom.

1010
00:43:39,550 --> 00:43:43,400
Men för nu, är detta en riktig
genomförande om vi antar att den

1011
00:43:43,400 --> 00:43:45,970
användaren kommer att tillhandahålla ints
som passar inom ints.

1012
00:43:45,970 --> 00:43:49,370
>> Men jag hävdar att denna kod, ärligt talat,
skulle kunna göras så mycket mer enkelt.

1013
00:43:49,370 --> 00:43:54,060
Om målet till hands är att ta ett antal
som m och lägg upp allt

1014
00:43:54,060 --> 00:43:59,510
siffror mellan det och en, eller omvänt
mellan 1 och det, hävdar jag

1015
00:43:59,510 --> 00:44:03,380
att jag kan låna den här idén att slå samman
Sortera hade, som ägde ett problem

1016
00:44:03,380 --> 00:44:05,660
av denna storlek och dividera det
till något mindre.

1017
00:44:05,660 --> 00:44:09,875
Kanske inte hälften, men mindre, men
representativt samma.

1018
00:44:09,875 --> 00:44:12,130
Samma idé, men ett mindre problem.

1019
00:44:12,130 --> 00:44:15,470
>> Så jag är faktiskt - låt mig spara den här filen
med en annan version nummer.

1020
00:44:15,470 --> 00:44:17,670
Vi kallar denna version
1 stället för 0.

1021
00:44:17,670 --> 00:44:20,790
Och jag hävdar att jag kan faktiskt
reimplement detta i denna typ av

1022
00:44:20,790 --> 00:44:22,160
kluriga sätt.

1023
00:44:22,160 --> 00:44:23,710
>> Jag kommer att lämna en del av den ensam.

1024
00:44:23,710 --> 00:44:27,710
Jag kommer att säga om m är mindre
än eller till och med lika med 0 -

1025
00:44:27,710 --> 00:44:29,280
Jag kommer bara att vara lite
mer anal denna gång

1026
00:44:29,280 --> 00:44:30,520
med min felkontroll -

1027
00:44:30,520 --> 00:44:33,190
Jag ska gå vidare och returnera 0.

1028
00:44:33,190 --> 00:44:34,490
Detta är godtycklig.

1029
00:44:34,490 --> 00:44:37,500
Jag bara helt enkelt avgöra om användaren
ger mig ett negativt tal, jag

1030
00:44:37,500 --> 00:44:41,490
återvänder 0, och de borde ha läst
dokumentationen närmare.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
märker vad jag ska göra.

1033
00:44:44,070 --> 00:44:49,260
Else kommer jag att återvända m plus -

1034
00:44:49,260 --> 00:44:51,010
vad som är sigma av m?

1035
00:44:51,010 --> 00:44:56,710
Tja, sigma av m plus m minus 1,
plus m minus 2, plus m minus 3.

1036
00:44:56,710 --> 00:44:58,030
Jag vill inte skriva allt detta ut.

1037
00:44:58,030 --> 00:44:59,120
Varför gör jag inte bara punt?

1038
00:44:59,120 --> 00:45:05,080
Rekursivt kalla mig själv med en något
mindre problem, semikolon,

1039
00:45:05,080 --> 00:45:06,840
och kallar det en dag?

1040
00:45:06,840 --> 00:45:07,040
>> Rätt?

1041
00:45:07,040 --> 00:45:10,980
Nu även här, kanske du känner eller oroa
att detta är en oändlig slinga som jag är

1042
00:45:10,980 --> 00:45:15,450
inducerande, där jag genomför
sigma genom att ringa sigma.

1043
00:45:15,450 --> 00:45:20,342
Men det är helt OK, eftersom jag
tänkte framåt en extra vilka linjer?

1044
00:45:20,342 --> 00:45:22,600
>> Publik: [OHÖRBAR].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID MALAN: 23 till 26, vilket
är min om tillstånd.

1046
00:45:25,430 --> 00:45:28,390
För vad är trevligt om
subtraktion här, eftersom jag håller

1047
00:45:28,390 --> 00:45:31,180
handing sigma mindre problem, mindre
problem, mindre - det är inte

1048
00:45:31,180 --> 00:45:31,870
halva storleken.

1049
00:45:31,870 --> 00:45:34,380
Det är bara en baby steg mindre,
men det är OK.

1050
00:45:34,380 --> 00:45:38,050
Eftersom så småningom kommer vi att arbeta
vår väg ner till 1 eller 0.

1051
00:45:38,050 --> 00:45:41,630
Och när vi slog 0, Sigma inte
kommer att kalla sig själv längre.

1052
00:45:41,630 --> 00:45:43,590
Det kommer att omedelbart återvända 0.

1053
00:45:43,590 --> 00:45:47,960
>> Så effekten, om du slags vind här
upp i ditt sinne, är att lägga m plus

1054
00:45:47,960 --> 00:45:52,740
m minus 1, plus m minus 2, plus m minus
3, plus dot, dot, dot, m minus

1055
00:45:52,740 --> 00:45:57,820
m, så småningom ge dig 0, och
Effekten är i slutändan att lägga alla

1056
00:45:57,820 --> 00:45:59,070
dessa saker tillsammans.

1057
00:45:59,070 --> 00:46:02,380
Så vi har inte, med rekursion,
löst problemet som vi

1058
00:46:02,380 --> 00:46:03,470
kunde inte lösa innan.

1059
00:46:03,470 --> 00:46:06,840
Faktum version 0 av detta, och varje
Problemet hittills har varit lösbar

1060
00:46:06,840 --> 00:46:09,980
med att bara använda loopar eller medan
öglor eller liknande konstruktioner.

1061
00:46:09,980 --> 00:46:13,150
>> Men rekursion, vågar jag säga, ger oss
ett annorlunda sätt att tänka

1062
00:46:13,150 --> 00:46:17,010
problem, vilket om vi kan ta en
problem, dela upp det från något

1063
00:46:17,010 --> 00:46:22,340
något stort till något något
mindre, hävdar jag att vi kan lösa det

1064
00:46:22,340 --> 00:46:26,040
kanske lite mer elegant i termer
av konstruktionen, med mindre kod,

1065
00:46:26,040 --> 00:46:30,980
och kanske även löser problem som skulle
vara svårare, eftersom vi kommer så småningom

1066
00:46:30,980 --> 00:46:33,280
se, lösa rent iterativt.

1067
00:46:33,280 --> 00:46:35,980
>> Men cliffhanger som jag gjorde
vill lämna oss på var det här.

1068
00:46:35,980 --> 00:46:40,720
Låt mig gå vidare och öppna
upp en fil från -

1069
00:46:40,720 --> 00:46:44,300
faktiskt, låt mig gå och
göra detta riktigt snabbt.

1070
00:46:44,300 --> 00:46:46,875
Låt mig gå vidare och föreslå
följande.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Bland dagens kod är denna fil här.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Detta här, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Så detta är ett dumt litet program som
Jag piskade upp som påstår sig göra

1076
00:47:06,260 --> 00:47:06,940
följande.

1077
00:47:06,940 --> 00:47:10,140
I huvud, deklarerar det först en
int kallade x och tilldelar den

1078
00:47:10,140 --> 00:47:11,100
värdet 1.

1079
00:47:11,100 --> 00:47:13,520
Sen deklarerar en int y och
tilldelar den värdet 2.

1080
00:47:13,520 --> 00:47:15,310
Sedan den skriver ut vad x och y är.

1081
00:47:15,310 --> 00:47:17,781
Sedan står det, byta, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Sedan den påstår att anropa en funktion
kallad swap, passerar i x-och

1083
00:47:21,670 --> 00:47:24,290
y, en idé som är det förhoppningsvis
x och y kommer tillbaka

1084
00:47:24,290 --> 00:47:25,620
annorlunda, motsatsen.

1085
00:47:25,620 --> 00:47:27,110
Sen hävdar bytt!

1086
00:47:27,110 --> 00:47:28,420
med ett utropstecken.

1087
00:47:28,420 --> 00:47:30,190
Sen skriver ut x och y.

1088
00:47:30,190 --> 00:47:33,480
>> Men det visar sig att denna mycket
enkel demonstration ned

1089
00:47:33,480 --> 00:47:35,570
här är faktiskt buggy.

1090
00:47:35,570 --> 00:47:38,870
Även om jag förklara en tillfällig
variabel och tillfälligt sätta en i

1091
00:47:38,870 --> 00:47:42,010
det, då jag omplacera
ett värde på b -

1092
00:47:42,010 --> 00:47:45,080
vilket känns rimligt, eftersom jag har
sparat en kopia av ett i temp.

1093
00:47:45,080 --> 00:47:48,410
Då jag uppdaterar b till lika
oavsett var i temp.

1094
00:47:48,410 --> 00:47:51,610
Denna typ av skal spel att flytta en
till b och b till ett med hjälp av denna

1095
00:47:51,610 --> 00:47:54,360
medelålders man som heter temp känns
helt rimligt.

1096
00:47:54,360 --> 00:47:57,270
>> Men jag hävdar att när jag kör det här
kod, som jag gör nu -

1097
00:47:57,270 --> 00:47:59,490
låt mig gå vidare och klistra in här.

1098
00:47:59,490 --> 00:48:01,995
Jag kallar detta noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Och som namnet antyder, är detta inte
kommer att vara ett korrekt program.

1100
00:48:05,630 --> 00:48:09,460
Gör noswap. / Ingen swap.

1101
00:48:09,460 --> 00:48:12,110
x är 1, är y 2, byta, bytte.

1102
00:48:12,110 --> 00:48:14,220
x är 1, y är 2.

1103
00:48:14,220 --> 00:48:16,920
Detta är fundamentalt fel, även
men detta verkar perfekt

1104
00:48:16,920 --> 00:48:17,730
rimligt för mig.

1105
00:48:17,730 --> 00:48:21,330
Och det finns en anledning, men vi är inte
kommer att avslöja orsaken ännu.

1106
00:48:21,330 --> 00:48:24,610
>> För nu den andra cliffhanger jag ville
att lämna dig med detta, en

1107
00:48:24,610 --> 00:48:27,120
tillkännagivandet av slag på rabattkoder.

1108
00:48:27,120 --> 00:48:31,590
Vår innovation med sena dagar i år
har framkallat en icke-trivial antalet

1109
00:48:31,590 --> 00:48:33,830
frågor, vilket var
inte vår avsikt.

1110
00:48:33,830 --> 00:48:36,590
Avsikten med dessa kupong koder,
där om du gör en del av problemet

1111
00:48:36,590 --> 00:48:39,850
ställa tidigt, och därmed få en extra dag,
var verkligen att hjälpa er hjälp

1112
00:48:39,850 --> 00:48:42,420
själv börjar tidigt, sortera
av genom incentivizing dig.

1113
00:48:42,420 --> 00:48:44,880
Hjälper oss att fördela belastningen över
kontorstid bättre så att

1114
00:48:44,880 --> 00:48:45,740
Det är typ av win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Tyvärr tror jag mina instruktioner
har inte varit hittills, mycket tydligt, så

1116
00:48:48,860 --> 00:48:52,230
Jag gick tillbaka i helgen och uppdaterade
spec i större, djärvare text till

1117
00:48:52,230 --> 00:48:53,600
förklara kulor som dessa.

1118
00:48:53,600 --> 00:48:56,900
Och bara för att säga det mer allmänt, genom
standard, problemsamlingar beror torsdag

1119
00:48:56,900 --> 00:48:58,400
vid middagstid, per kursplanen.

1120
00:48:58,400 --> 00:49:02,030
Om du börjar tidigt, avslutar en del av
problemet fastställts av onsdag kl 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, den del som hänför sig till en kupong
kod, är tanken att du kan förlänga

1122
00:49:05,170 --> 00:49:07,710
din deadline för
P satt fram till fredag.

1123
00:49:07,710 --> 00:49:10,890
Det vill säga, lite av en liten del av P
in i förhållande till vad som normalt är den

1124
00:49:10,890 --> 00:49:13,200
större problem, och du köper
själv en extra dag.

1125
00:49:13,200 --> 00:49:15,190
Återigen blir det du tänker
problemet set, får du

1126
00:49:15,190 --> 00:49:16,380
kontorstid förr.

1127
00:49:16,380 --> 00:49:20,670
Men kupongkod problemet är fortfarande
krävs, även om du inte skickar in den.

1128
00:49:20,670 --> 00:49:23,340
>> Men mer fängslande är här.

1129
00:49:23,340 --> 00:49:26,520
(TEATERVISKNING) Och de folk som lämnar
tidigt är gonna ångra det.

1130
00:49:26,520 --> 00:49:28,620
Så är de folk på balkongen.

1131
00:49:28,620 --> 00:49:32,510
Jag ber om ursäkt i förväg till folk på
balkongen av skäl som kommer att vara

1132
00:49:32,510 --> 00:49:33,920
klart på bara ett ögonblick.

1133
00:49:33,920 --> 00:49:37,050
>> Så vi är lyckligt lottade att ha en av
CS50: s tidigare chef Undervisning Fellows vid

1134
00:49:37,050 --> 00:49:39,302
ett företag som heter dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
De har mycket generöst donerat en
kupongkod här för mycket utrymme,

1136
00:49:45,500 --> 00:49:48,180
som är upp från
vanliga 2 gigabyte.

1137
00:49:48,180 --> 00:49:51,740
Så vad jag trodde vi skulle göra på detta
sista anmärkning är att göra lite av en giveaway,

1138
00:49:51,740 --> 00:49:55,380
varigenom på bara ett ögonblick, kommer vi att avslöja
vinnaren och som har en kupong

1139
00:49:55,380 --> 00:49:57,980
kod som du sedan kan gå till deras
hemsida, skriv in det i, och voila, få en

1140
00:49:57,980 --> 00:50:01,370
hel del mer Dropbox utrymme för din
apparaten och för dina personliga filer.

1141
00:50:01,370 --> 00:50:05,690
>> Och först, vem skulle vilja delta
i denna ritning?

1142
00:50:05,690 --> 00:50:09,630
OK, nu som gör det ännu roligare.

1143
00:50:09,630 --> 00:50:14,010
Den person som tar emot denna 25-gigabyte
kupongkod - vilket är långt

1144
00:50:14,010 --> 00:50:16,150
mer övertygande än den sena
dagar nu, kanske -

1145
00:50:16,150 --> 00:50:20,620
är den som sitter på toppen av en
sittdyna under vilken det finns

1146
00:50:20,620 --> 00:50:21,620
denna kupongkod.

1147
00:50:21,620 --> 00:50:23,480
Du kan nu titta under
din sittdyna.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [VIDEO SPELA]

1150
00:50:29,680 --> 00:50:31,620
>> -Ett, två, tre.

1151
00:50:31,620 --> 00:50:35,015
>> [SCREAMING]

1152
00:50:35,015 --> 00:50:35,985
>> -Du får en bil!

1153
00:50:35,985 --> 00:50:36,670
Du får en bil!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID MALAN: Vi får se
du på onsdag.

1155
00:50:37,970 --> 00:50:38,904
>> -Du får en bil!

1156
00:50:38,904 --> 00:50:39,371
Du får en bil!

1157
00:50:39,371 --> 00:50:40,305
Du får en bil!

1158
00:50:40,305 --> 00:50:41,706
Du får en bil!

1159
00:50:41,706 --> 00:50:43,107
Du får en bil!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID MALAN: Balkong folks, kom
här nere till fronten,

1161
00:50:45,530 --> 00:50:46,866
där vi har extra.

1162
00:50:46,866 --> 00:50:50,282
>> -Alla får en bil!

1163
00:50:50,282 --> 00:50:52,234
Alla får en bil!

1164
00:50:52,234 --> 00:50:52,722
>> [END VIDEOAVSPELNING]

1165
00:50:52,722 --> 00:50:54,590
>> Berättare: Vid nästa 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]