1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> SPEAKER: Okay, det her er CS50.

3
00:00:14,910 --> 00:00:19,020
Det er i slutningen af ​​uge tre, og hvis
du ikke har benyttet sig allerede,

4
00:00:19,020 --> 00:00:21,790
ved, at der vil være frokost
denne fredag ​​som sædvanlig, hvor

5
00:00:21,790 --> 00:00:25,430
du kan nyde god samtale
og fødevarer på Fire and Ice

6
00:00:25,430 --> 00:00:27,980
med nogle af CS50 s
personale og klassekammerater.

7
00:00:27,980 --> 00:00:30,170
Hovedet til denne webadresse her.

8
00:00:30,170 --> 00:00:33,420
>> Nu kan du huske, eller du
kan snart være bekendt med,

9
00:00:33,420 --> 00:00:35,970
disse ting her, som
er givet i slutningen

10
00:00:35,970 --> 00:00:37,850
af semestret for mange klasser.

11
00:00:37,850 --> 00:00:40,870
Såkaldte eksamen blå bøger, hvor
du skriver dine svar eksamener.

12
00:00:40,870 --> 00:00:44,240
Nu har jeg her 26 sådan
blå bøger, på hver af dem

13
00:00:44,240 --> 00:00:47,580
er skrevet et navn, en A til Z. Og
faktisk navnene er så simpelt, A

14
00:00:47,580 --> 00:00:50,490
gennem Z. Og en af
målene ved hånden i dag

15
00:00:50,490 --> 00:00:53,910
vil være at fortsætte det,
vi startede i mandags, hvilket ikke er

16
00:00:53,910 --> 00:00:57,830
så meget at kigge på koden, men virkelig
ser på ideer og problemløsning.

17
00:00:57,830 --> 00:01:00,170
Et af målene og
løfter om dette kursus

18
00:01:00,170 --> 00:01:02,985
er at lære dig at tænke mere
omhyggeligt, mere metodisk,

19
00:01:02,985 --> 00:01:05,400
og til at løse problemer mere effektivt.

20
00:01:05,400 --> 00:01:09,526
Og ja, vi kan gøre, der virkelig
uden selv at røre en linje kode.

21
00:01:09,526 --> 00:01:12,150
Så jeg har et par elefanter
op her i dag, orange og blå,

22
00:01:12,150 --> 00:01:15,780
hvis vi kunne få en frivillig,
måske fra længere tilbage end normalt.

23
00:01:15,780 --> 00:01:18,070
Hvad med lige der, kom ned.

24
00:01:18,070 --> 00:01:24,180
Målet, som vil være til
hjælpe plus administrere denne eksamen her.

25
00:01:24,180 --> 00:01:24,935
Hvad er dit navn?

26
00:01:24,935 --> 00:01:25,768
>> Publikum: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
SPEAKER: Mary Beth, kom op.

28
00:01:27,560 --> 00:01:29,560
Lad mig få mikrofonen her for dig.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Rart at møde dig.

31
00:01:32,880 --> 00:01:34,005
>> Publikum: Rart at møde dig.

32
00:01:34,005 --> 00:01:36,790
SPEAKER: Okay, så jeg har
her blå bøger A til Z,

33
00:01:36,790 --> 00:01:41,680
og jeg har tænkt mig at foregive, at
Jeg har en af ​​de studerende,

34
00:01:41,680 --> 00:01:45,770
og de kommer i lidt tilfældigt
ved slutningen af ​​en tre timers prøve blok,

35
00:01:45,770 --> 00:01:49,400
så de er ender i nogle
semi-tilfældig rækkefølge som denne.

36
00:01:49,400 --> 00:01:54,510
Nu er din opgave på bare et øjeblik går
at være-- dette er faktisk, hvordan de får

37
00:01:54,510 --> 00:01:56,820
slået i slutningen af
klassen, mest sandsynlige.

38
00:01:56,820 --> 00:02:01,120
Dit job nu kommer til at være helt
simpelthen, at sortere disse blå bøger til os

39
00:02:01,120 --> 00:02:05,220
fra A til Z.

40
00:02:05,220 --> 00:02:08,400
>> PUBLIKUM: Åh, det er
kommer til at tage for evigt.

41
00:02:08,400 --> 00:02:13,747
>> SPEAKER: Og vi vil se
som du gør dette, ingen pres.

42
00:02:13,747 --> 00:02:15,330
PUBLIKUM: Nej, ingen pres eller noget.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> SPEAKER: Og for sjov,
lad os sætte en timer.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> PUBLIKUM: Så meget sjov, så meget sjov.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> SPEAKER: Jeg kan holde mikrofonen for dig.

49
00:02:38,574 --> 00:02:40,240
Okay, vi har lige fordoblet vores hastighed.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Så i mellemtiden, lad mig stille, hvad der er
vil være spørgsmålet om Mary Beth

52
00:02:49,060 --> 00:02:51,540
er, hvad hun laver, hvordan er
hun går om at løse dette?

53
00:02:51,540 --> 00:02:54,040
Og i virkeligheden, har du måske ikke
nogensinde tænkt over noget

54
00:02:54,040 --> 00:02:57,440
så simpelt som når du vælger
op 26 bøger som denne,

55
00:02:57,440 --> 00:02:59,350
som har en naturlig
bestilling til dem.

56
00:02:59,350 --> 00:03:01,335
Hvad er den proces,
at du rent faktisk bruge?

57
00:03:01,335 --> 00:03:03,770
Er det temmelig tilfældigt bare
plukke den første, du ser

58
00:03:03,770 --> 00:03:05,250
og sætte det på sin plads?

59
00:03:05,250 --> 00:03:09,680
Har du først flytte dine hænder rundt
Leder du efter en så søger B?

60
00:03:09,680 --> 00:03:11,722
Har du tage et kig på en
par af dem side om side

61
00:03:11,722 --> 00:03:14,680
og bare sige, vent et øjeblik, dette
er ikke rigtigt, og så bytte den rækkefølge?

62
00:03:14,680 --> 00:03:16,960
Vi så allerede på mandag
at der er en række måder

63
00:03:16,960 --> 00:03:22,140
hvor vi kan gøre dette, og
ja da vi nær slutningen her,

64
00:03:22,140 --> 00:03:26,360
Jeg ville tage til efterretning måske
af, hvad Mary Beth gør.

65
00:03:26,360 --> 00:03:30,040
Vi har et par bunker synes det, en
større en, tre mindre.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> Publikum: Jeg beordrer dem
når jeg finder to bogstaver

68
00:03:36,415 --> 00:03:39,540
at jeg ved, er sammen i en sekvens,
Jeg satte dem sammen, så jeg ikke

69
00:03:39,540 --> 00:03:42,915
nødt til at bekymre sig om at holde
spor af en hel række af bøger.

70
00:03:42,915 --> 00:03:45,706
Det er bare, åh, A er det første,
Jeg har denne stak her.

71
00:03:45,706 --> 00:03:47,580
SPEAKER: Så, næsten som
et puslespil stykker,

72
00:03:47,580 --> 00:03:49,860
har den rigtige form til
passer sammen med hinanden.

73
00:03:49,860 --> 00:03:51,026
PUBLIKUM: Temmelig meget, ja.

74
00:03:51,026 --> 00:03:55,320
SPEAKER: OK, fremragende.

75
00:03:55,320 --> 00:03:59,850
Og nu hver af disse
bunker formentlig sorteret?

76
00:03:59,850 --> 00:04:00,990
>> Publikum: Ja.

77
00:04:00,990 --> 00:04:09,900
>> SPEAKER: Okay, A til Z. Alle
højre, tillykke, du gjorde det.

78
00:04:09,900 --> 00:04:11,461
Du har dit valg.

79
00:04:11,461 --> 00:04:11,960
Blue?

80
00:04:11,960 --> 00:04:13,530
Okay, tak for det.

81
00:04:13,530 --> 00:04:16,679
Så Mary Beth har foreslået
hvad hendes tilgang var,

82
00:04:16,679 --> 00:04:19,720
men hvad er en anden tilgang, hvordan du
måske gå om sortering disse ting?

83
00:04:19,720 --> 00:04:21,130
Hvad ville du have gjort?

84
00:04:21,130 --> 00:04:24,060
Pladen at slå ville have været
et minut og 50 sekunder eller deromkring,

85
00:04:24,060 --> 00:04:26,039
plus dem, jeg glemte at tælle.

86
00:04:26,039 --> 00:04:27,080
Hvad ville du have gjort?

87
00:04:27,080 --> 00:04:27,579
Ja?

88
00:04:27,579 --> 00:04:28,735
PUBLIKUM: Tag stakken.

89
00:04:28,735 --> 00:04:29,776
Start fra begyndelsen.

90
00:04:29,776 --> 00:04:32,284
Tjek dine papirer.

91
00:04:32,284 --> 00:04:36,586
Og hvis den øverste er højere
end, måske, de er,

92
00:04:36,586 --> 00:04:38,980
den nederste er
højere, og derefter skifte dem.

93
00:04:38,980 --> 00:04:41,300
>> SPEAKER: OK, så starter
ved toppen og bunden,

94
00:04:41,300 --> 00:04:43,716
og derefter arbejde din vej
indad sådan, bytte dem?

95
00:04:43,716 --> 00:04:46,580
OK, så en lidt lignende
i ånden at boble sortere,

96
00:04:46,580 --> 00:04:49,160
men at vælge ekstremer
ikke de tilstødende par.

97
00:04:49,160 --> 00:04:52,080
Men korte af det er, at der er
sikkert en masse forskellige måder

98
00:04:52,080 --> 00:04:54,210
vi kunne gøre dette, og
helt ærligt, jeg tror, ​​du slags

99
00:04:54,210 --> 00:04:55,700
vedtaget et par tilgange, right?

100
00:04:55,700 --> 00:05:00,567
Du gjorde slags fire sorterede bunker, og
så effektivt fusioneret dem sammen.

101
00:05:00,567 --> 00:05:02,650
Og det er, daresay, en anden
teknik helt.

102
00:05:02,650 --> 00:05:06,950
Du har ikke behandle det som en stor bunke,
du delte problemet i fire quads,

103
00:05:06,950 --> 00:05:09,820
hvis du vil, og derefter en eller anden måde
fusioneret dem i sidste ende.

104
00:05:09,820 --> 00:05:13,410
>> Så lad os overveje, i sidste ende,
hvordan vi ellers kan gøre dette.

105
00:05:13,410 --> 00:05:15,860
Vi formaliseret begrebet
boble slags sidste gang,

106
00:05:15,860 --> 00:05:18,780
og boble sortere tilbagekaldelse var en
algoritme, vi visualiseret

107
00:05:18,780 --> 00:05:22,640
med otte af dine klassekammerater op her,
tilsyneladende tilfældigt sorteres først.

108
00:05:22,640 --> 00:05:26,110
Og vi besluttede derefter parvis, hvis
to elementer er ude af drift,

109
00:05:26,110 --> 00:05:26,950
simpelthen bytte dem.

110
00:05:26,950 --> 00:05:28,930
Så fire og to er
naturligvis ud af orden,

111
00:05:28,930 --> 00:05:31,080
Så dem to klassekammerater
skiftet position.

112
00:05:31,080 --> 00:05:35,390
Og så har vi gentaget med fire og seks,
derefter seks og otte på hver iteration

113
00:05:35,390 --> 00:05:36,980
bevæger sig til højre.

114
00:05:36,980 --> 00:05:42,590
>> Så givet otte personer, hvor mange parvise
sammenligninger gjorde jeg, mens du går fra

115
00:05:42,590 --> 00:05:45,220
venstre til højre i en sådan iteration?

116
00:05:45,220 --> 00:05:48,410
Hvor mange sammenligninger?

117
00:05:48,410 --> 00:05:49,197
Syv, right?

118
00:05:49,197 --> 00:05:51,405
For hvis der er otte
mennesker, men du har parret

119
00:05:51,405 --> 00:05:53,880
dem, og du holder bevægelse
en hop til højre,

120
00:05:53,880 --> 00:05:56,060
du kommer ikke til at have otte
sammenligninger, fordi du kan ikke sammenligne

121
00:05:56,060 --> 00:05:59,226
et element mod sig selv, eller det ville
bare være meningsløst, så du har syv.

122
00:05:59,226 --> 00:06:01,290
Eller mere generelt, hvis
vi har n mennesker, vi

123
00:06:01,290 --> 00:06:04,300
gøre n minus 1 sammenligninger
med boble slags.

124
00:06:04,300 --> 00:06:08,150
>> Så lad os nu overveje, hvor god eller
dårlig boble sortere faktisk var, og prøv

125
00:06:08,150 --> 00:06:13,570
at give os selv ordforråd med
som til kritik algoritmer som denne,

126
00:06:13,570 --> 00:06:14,430
og snart vores egen.

127
00:06:14,430 --> 00:06:16,970
Så den første passage gennem
boble sortere, første gang

128
00:06:16,970 --> 00:06:20,909
Jeg gik fra venstre til højre på tværs af
stadium, tog mig n minus 1 sammenligninger.

129
00:06:20,909 --> 00:06:22,950
Og det kommer til at være min
måleenhed, right?

130
00:06:22,950 --> 00:06:26,170
Jeg var slags taler og spadsereture,
noget hurtigt, lidt langsom,

131
00:06:26,170 --> 00:06:29,300
så tælle mit antal sekunder
er ikke specielt at fortælle,

132
00:06:29,300 --> 00:06:32,260
men at tælle antallet af
operationer, som jeg gjorde i mandags,

133
00:06:32,260 --> 00:06:35,900
sammenligne to mennesker, der føler sig
ligesom en nice måleenhed.

134
00:06:35,900 --> 00:06:40,980
>> Så n minus 1 trin for første gang,
men hvad skete der efter det?

135
00:06:40,980 --> 00:06:46,610
Hvad er den ene på hovedet af en pass
gennem en ellers usorteret liste?

136
00:06:46,610 --> 00:06:49,840
Hvad kan du fortælle mig om elementet
der var hele vejen derovre?

137
00:06:49,840 --> 00:06:51,300
Ja?

138
00:06:51,300 --> 00:06:52,870
Det var den største element, right?

139
00:06:52,870 --> 00:06:55,710
Nummer otte, selvom hun
startede her, hver gang jeg

140
00:06:55,710 --> 00:06:57,860
sammenlignet hende imod
en nabo, hun holdt

141
00:06:57,860 --> 00:07:00,480
bobler op til højre
side af listen.

142
00:07:00,480 --> 00:07:02,710
Og ja, det er her,
algoritmen får sit navn.

143
00:07:02,710 --> 00:07:07,630
>> Nu ved denne logik, hvor mange sammenligninger
behøver jeg gøre på anden gang

144
00:07:07,630 --> 00:07:09,800
Jeg gør, at bolden fra venstre mod højre?

145
00:07:09,800 --> 00:07:10,730
n minus 2, højre?

146
00:07:10,730 --> 00:07:14,297
Det ville bare være spild af min tid, hvis jeg
holde sammenligne otte mod nogen

147
00:07:14,297 --> 00:07:16,630
andet fordi vi allerede kender
Hun var på det rigtige sted.

148
00:07:16,630 --> 00:07:19,760
Så det er lidt af en
optimering, så den næste linie

149
00:07:19,760 --> 00:07:23,899
vil være plus n minus to trin,
hvor n er antallet af personer.

150
00:07:23,899 --> 00:07:26,940
Nu kan du slags ekstrapolere, selv
hvis du ikke er en datalog,

151
00:07:26,940 --> 00:07:27,680
hvordan det ender.

152
00:07:27,680 --> 00:07:31,259
Ved afslutningen af ​​denne algoritme, formentlig
du har bare en sammenligning venstre.

153
00:07:31,259 --> 00:07:33,800
Du er nødt til at slags fastsætte
starten af ​​listen i tilfælde to

154
00:07:33,800 --> 00:07:36,540
og en er ude af drift
og bør være et og to,

155
00:07:36,540 --> 00:07:40,330
så dette når bunden på
plus 1 endelige sammenligning.

156
00:07:40,330 --> 00:07:44,500
>> Nu prik, prik, prik slags bølger, det er
hænder på nogle af de juicier detaljer

157
00:07:44,500 --> 00:07:46,452
men lad os bare gå videre og forenkle.

158
00:07:46,452 --> 00:07:48,660
Hvis du husker fra høj
skole, helt ærligt, en masse af jer

159
00:07:48,660 --> 00:07:50,340
havde matematik bøger, der havde
lidt bedrager ark

160
00:07:50,340 --> 00:07:52,550
på forsiden eller
bagsiden, der viste dig

161
00:07:52,550 --> 00:07:56,400
hvad serien summationer som
dette i sidste ende lægges op til.

162
00:07:56,400 --> 00:07:59,600
I det generelle tilfælde, hvis du har en
variabel ligesom n, og faktisk denne ene,

163
00:07:59,600 --> 00:08:01,634
hvis du har kigget på din
old school matematik bog,

164
00:08:01,634 --> 00:08:04,050
vil du se, at dette faktisk
tilføjer op til dette beløb her,

165
00:08:04,050 --> 00:08:07,970
n gange n minus 1 alle divideres med 2.

166
00:08:07,970 --> 00:08:11,172
Så lad mig nu bare fastsætte
dette er sandt, så på et spring af tro,

167
00:08:11,172 --> 00:08:12,880
det er, hvad dette opsummerer
op til, og vi kunne

168
00:08:12,880 --> 00:08:14,341
bevise, at en mere generelle tilfælde.

169
00:08:14,341 --> 00:08:15,590
Men lad os nu udvide denne ud.

170
00:08:15,590 --> 00:08:19,920
Så lad os multipliceres ud, så det er
n kvadreret minus n, alle divideres med 2.

171
00:08:19,920 --> 00:08:23,200
Det er virkelig n kvadreret,
divideret med 2, minus n over 2,

172
00:08:23,200 --> 00:08:25,010
så det er alle nice og interessant.

173
00:08:25,010 --> 00:08:27,060
Men hvad sker der, hvis vi
nu plug-in en værdi?

174
00:08:27,060 --> 00:08:29,724
Antag jeg ikke har otte
folk, men siger en million.

175
00:08:29,724 --> 00:08:31,890
Og en million bare fordi
det er en temmelig stor antal,

176
00:08:31,890 --> 00:08:34,039
lad os sætte det i og se hvad der sker.

177
00:08:34,039 --> 00:08:39,039
Så hvis jeg sætte en million ind i denne formel
Jeg har tænkt mig at få en million kvadreret,

178
00:08:39,039 --> 00:08:42,868
divideret med 2, minus en
millioner, divideres med 2.

179
00:08:42,868 --> 00:08:44,159
Hvad er nu det kommer til at være lig?

180
00:08:44,159 --> 00:08:47,354
Så 500 milliarder, minus 500.000.

181
00:08:47,354 --> 00:08:49,270
Og hvis jeg rent faktisk gør
at matematik, betyder

182
00:08:49,270 --> 00:08:53,920
at sortere en million
folk med boblen slags

183
00:08:53,920 --> 00:09:01,800
kan tage mig 499999500000
trin eller sammenligninger i sidste ende,

184
00:09:01,800 --> 00:09:02,900
vi bare ekstrapolere.

185
00:09:02,900 --> 00:09:06,860
>> Det føles temmelig langsomme, men helt ærligt
måle en bestemt indgang

186
00:09:06,860 --> 00:09:09,160
som dette, er det ikke alle, der fortæller.

187
00:09:09,160 --> 00:09:14,050
Men faktisk det antyder, at n
bliver større og større, denne algoritme

188
00:09:14,050 --> 00:09:16,280
slags føles værre og
værre, eller du virkelig

189
00:09:16,280 --> 00:09:20,450
begynder at føle smerten ved det
eksponentiation, at n kvadreret,

190
00:09:20,450 --> 00:09:21,770
som tilføjer op temmelig hurtigt.

191
00:09:21,770 --> 00:09:25,340
Og denne detalje er ikke
tabt på mennesker, i virkeligheden

192
00:09:25,340 --> 00:09:29,640
for nogle år siden en vis senator, der var
kampagner, sad til et interview

193
00:09:29,640 --> 00:09:32,180
med Googles Eric
Schmidt, administrerende direktør på det tidspunkt,

194
00:09:32,180 --> 00:09:36,380
og blev udfordret med et spørgsmål
ligesom vi udforsker i dag.

195
00:09:36,380 --> 00:09:38,468
Lad os tage et kig.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEOAFSPILNING]

197
00:09:45,280 --> 00:09:48,560
>> Senator, du er her
på Google, og jeg kan lide

198
00:09:48,560 --> 00:09:53,382
at tænke på formandskabet
som en jobsamtale.

199
00:09:53,382 --> 00:09:56,434
Nu er det svært at få
et job som præsident,

200
00:09:56,434 --> 00:09:58,100
og du går igennem strabadserne nu.

201
00:09:58,100 --> 00:10:01,860
Det er også svært at få et job hos Google.

202
00:10:01,860 --> 00:10:05,490
Vi har spørgsmål, og vi
spørger vores kandidater spørgsmål,

203
00:10:05,490 --> 00:10:09,770
og dette er fra Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
Hvad-- du fyre tror jeg
kidding, det er lige her.

205
00:10:14,760 --> 00:10:17,930
Hvad er den mest effektive måde at
sortere en million 32-bit heltal?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> Jae--

208
00:10:24,350 --> 00:10:25,200
>> Jeg er ked af, maybe--

209
00:10:25,200 --> 00:10:27,400
>> Nej, nej, nej.

210
00:10:27,400 --> 00:10:30,700
Jeg tror boblen slags
ville være den forkerte vej at gå.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> Kom nu, der fortalte ham det?

213
00:10:38,180 --> 00:10:40,590
Jeg kunne ikke se computer
videnskab i din baggrund.

214
00:10:40,590 --> 00:10:42,130
>> -Vi Fik vores spioner derinde.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -OK, Lad os bede en anden
interview spørgsmål.

217
00:10:48,444 --> 00:10:49,300
>> [END VIDEO PLAYBACK]

218
00:10:49,300 --> 00:10:52,290
>> SPEAKER: Så taler om
bestemte numre selv,

219
00:10:52,290 --> 00:10:53,890
kommer ikke til at være alt det nyttigt.

220
00:10:53,890 --> 00:10:56,810
Det er ikke et liv lektion, boble
art, givet en million indgange,

221
00:10:56,810 --> 00:10:58,590
kan tage så mange som 500 milliarder trin.

222
00:10:58,590 --> 00:11:01,120
Du kan ikke rigtig generalisere
også effektivt fra at

223
00:11:01,120 --> 00:11:03,560
og gøre gode design beslutninger
når du skriver programmer.

224
00:11:03,560 --> 00:11:07,070
Så lad os fokusere dog på, hvordan
vi måske forenkle dette resultat.

225
00:11:07,070 --> 00:11:11,780
>> Så jeg har markeret med gult her
resultatet af n squared divideres med 2,

226
00:11:11,780 --> 00:11:14,330
så en million kvadreret
divideret med 2 og derefter

227
00:11:14,330 --> 00:11:16,710
Jeg har fremhævet, hvad
det ultimative svar var

228
00:11:16,710 --> 00:11:20,180
når vi trækkes væk n divideres med 2.

229
00:11:20,180 --> 00:11:24,850
Og påstanden jeg har tænkt mig at gøre nu, er,
hvem dælen bekymrer sig hvis du trækker ud

230
00:11:24,850 --> 00:11:30,060
lidt gammel n over 2, da den første
en del af denne formel er så meget større?

231
00:11:30,060 --> 00:11:33,910
Det dominerer den anden
sigt n kvadreret divideret med 2

232
00:11:33,910 --> 00:11:37,510
er så meget større, klart, som
n bliver stor som en million,

233
00:11:37,510 --> 00:11:41,450
der er der virkelig en stor forskel på
slutningen af ​​dag mellem 500 milliarder

234
00:11:41,450 --> 00:11:45,730
og 499.999.500.000?

235
00:11:45,730 --> 00:11:46,349
Ikke rigtig.

236
00:11:46,349 --> 00:11:48,640
Og så hvad vi kommer til at
gøre som dataloger er

237
00:11:48,640 --> 00:11:53,270
ignorere disse lavere ordens led og
tage noget som dette og virkelig

238
00:11:53,270 --> 00:11:56,050
bare forenkle det til
begreb, der kommer til at ligegyldigt.

239
00:11:56,050 --> 00:12:00,315
De større vores datasæt får, jo større
vores databaser får, jo flere websider

240
00:12:00,315 --> 00:12:02,690
vi nødt til at søge, jo mere
venner du har på Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Som n bliver større, er vi virkelig
kommer til at bekymre sig om den største

242
00:12:07,340 --> 00:12:11,560
sigt i en sådan analyse af
vores algoritmer ydeevne.

243
00:12:11,560 --> 00:12:16,230
Og jeg har tænkt mig at sige, ved du hvad,
boble slags er på rækkefølgen af ​​store O,

244
00:12:16,230 --> 00:12:18,060
af størrelsesordenen n potens.

245
00:12:18,060 --> 00:12:20,090
Det er ikke ligefrem n
kvadreret, som vi har set,

246
00:12:20,090 --> 00:12:22,060
men hvem virkelig bekymrer
om disse mindre vilkår,

247
00:12:22,060 --> 00:12:24,390
og helt ærligt, der virkelig
bekymrer sig hvis vi dividere med 2?

248
00:12:24,390 --> 00:12:25,870
Det er bare en konstant faktor.

249
00:12:25,870 --> 00:12:29,480
Og er 500 milliarder versus 250
milliarder virkelig så stor en deal?

250
00:12:29,480 --> 00:12:32,190
Jeg kunne bare vente et år
lad min laptop bogstaveligt

251
00:12:32,190 --> 00:12:34,810
få dobbelt så hurtigt i hardware,
og den slags forskel

252
00:12:34,810 --> 00:12:36,650
bare går væk naturligt over tid.

253
00:12:36,650 --> 00:12:39,300
>> Hvad vi bekymrer os om, er
Udtrykket den del

254
00:12:39,300 --> 00:12:42,489
af det udtryk, der kommer til at variere
som vores input bliver større og større.

255
00:12:42,489 --> 00:12:45,280
Og ja, i den virkelige verden,
det er hvad der sker i stigende grad

256
00:12:45,280 --> 00:12:48,330
er input til vores problemer og
algoritmer bliver større.

257
00:12:48,330 --> 00:12:53,470
Så stor O vil være den notation,
den asymptotiske notation, at vi bare

258
00:12:53,470 --> 00:12:57,160
bruge som dataloger til at beskrive
ydeevne, eller køretiden,

259
00:12:57,160 --> 00:12:58,130
af en algoritme.

260
00:12:58,130 --> 00:13:00,800
For at vi kan sammenligne algoritmer
på forskellige computere skriftlige

261
00:13:00,800 --> 00:13:04,170
af forskellige mennesker, ved hjælp af
nogle fundamentalt lignende metrisk

262
00:13:04,170 --> 00:13:07,557
ligesom antallet af sammenligninger, du er
gør, eller måske antallet af swaps

263
00:13:07,557 --> 00:13:08,140
du laver.

264
00:13:08,140 --> 00:13:11,910
>> Hvad vi ikke kommer til at
tæller er den mængde tid

265
00:13:11,910 --> 00:13:13,981
der passerer på uret
på væggen typisk.

266
00:13:13,981 --> 00:13:16,230
Hvad vi ikke kommer til at bekymre sig
om, er, hvor meget hukommelse

267
00:13:16,230 --> 00:13:17,820
du bruger i dag på
mindste, selv om det er

268
00:13:17,820 --> 00:13:19,370
en anden ressource, vi kan måle.

269
00:13:19,370 --> 00:13:23,610
Vi vil forsøge at basere vores analyser
på netop de grundlæggende operationer, dem,

270
00:13:23,610 --> 00:13:25,930
helt ærligt, at du kan se mest visuelt.

271
00:13:25,930 --> 00:13:30,700
Så med noget stort O n
kvadreret, jeg hævder, at O ​​n kvadreret

272
00:13:30,700 --> 00:13:35,820
er en øvre grænse for den såkaldte
køretid boble slags.

273
00:13:35,820 --> 00:13:38,820
Med andre ord, hvis du
ønskede at hævde, at der er

274
00:13:38,820 --> 00:13:41,370
denne øvre grænse for, hvor mange
skridt en algoritme kan tage,

275
00:13:41,370 --> 00:13:46,240
det kommer til at være i den store O af n
kvadreret i dette tilfælde en øvre grænse.

276
00:13:46,240 --> 00:13:49,710
>> Hvad hvis jeg i stedet skifte
historie ikke at være omkring boble sortere,

277
00:13:49,710 --> 00:13:50,910
men om denne øvre grænse.

278
00:13:50,910 --> 00:13:54,030
Kan du tænke på en algoritme
at vi har kigget på allerede

279
00:13:54,030 --> 00:13:59,530
hvis øvre grænse, maksimum
måle tid eller operationer,

280
00:13:59,530 --> 00:14:04,300
ville siges at være afgrænset
med n, en lineær funktion,

281
00:14:04,300 --> 00:14:07,260
ikke en kvadratisk en, der er buet?

282
00:14:07,260 --> 00:14:10,780
Hvad er en algoritme, der
altid tager ikke mere

283
00:14:10,780 --> 00:14:12,860
end lignende n trin, eller
2n trin eller 3n Steps?

284
00:14:12,860 --> 00:14:13,360
Ja?

285
00:14:13,360 --> 00:14:15,030
>> PUBLIKUM: at finde den
højeste antal på en liste?

286
00:14:15,030 --> 00:14:16,930
>> SPEAKER: Perfekt, finde
det største antal på en liste.

287
00:14:16,930 --> 00:14:18,940
Hvis jeg får en liste over
folk for eksempel,

288
00:14:18,940 --> 00:14:21,440
hver, der holder et nummer,
hvad der er det maksimale antal

289
00:14:21,440 --> 00:14:23,770
skridt det skal tage mig,
et rimeligt smart person,

290
00:14:23,770 --> 00:14:27,530
at finde den største person i det liste?

291
00:14:27,530 --> 00:14:28,100
n, right?

292
00:14:28,100 --> 00:14:31,320
Fordi der i værste tilfælde, hvor
måske den største værdi være?

293
00:14:31,320 --> 00:14:32,700
Højre, hele vejen i slutningen.

294
00:14:32,700 --> 00:14:34,575
Så i værste fald
øvre grænse, kan jeg

295
00:14:34,575 --> 00:14:36,450
nødt til at gå hele vejen
herover og være ligesom,

296
00:14:36,450 --> 00:14:39,170
åh, her er nummer otte,
eller hvad denne værdi er.

297
00:14:39,170 --> 00:14:41,330
Nu vil det bare være dumt
hvis jeg holdt hen, ikke?

298
00:14:41,330 --> 00:14:43,840
Leder du efter flere og flere elementer
hvis den sidste af dem er derovre?

299
00:14:43,840 --> 00:14:45,340
Så sikkert, n er en øvre grænse.

300
00:14:45,340 --> 00:14:47,420
Jeg behøver ikke at tage
flere trin end det.

301
00:14:47,420 --> 00:14:51,580
>> Så hvad nu hvis jeg i stedet foreslået, at
der er algoritmer i denne verden,

302
00:14:51,580 --> 00:14:57,750
har en køretid, der er
afgrænset af store O log n log n?

303
00:14:57,750 --> 00:15:00,390
Hvor har vi set det før?

304
00:15:00,390 --> 00:15:00,890
Ja?

305
00:15:00,890 --> 00:15:03,309
>> Publikum: I telefonbogen problemet?

306
00:15:03,309 --> 00:15:04,850
SPEAKER: Ligesom telefonbogen problemet.

307
00:15:04,850 --> 00:15:07,754
Hvad var mål for, hvor
meget tid eller hvor mange tårer it

308
00:15:07,754 --> 00:15:10,170
Tog mig med at finde en person som
Mike Smith i telefonbogen?

309
00:15:10,170 --> 00:15:13,212
Vi hævdede det var logn, og
selvom ukendt, eller det er det

310
00:15:13,212 --> 00:15:15,170
lidt diset, hvad en
logaritmen eller eksponent var

311
00:15:15,170 --> 00:15:17,650
bare huske, at log n
generelt henviser til den proces,

312
00:15:17,650 --> 00:15:20,790
i dette tilfælde, at opdele
noget i halve igen, og igen,

313
00:15:20,790 --> 00:15:25,790
og igen og igen, således at det
får stadig mindre, som du gør det.

314
00:15:25,790 --> 00:15:28,470
>> Så log af n henviser til, sikker,
til telefonbogen eksempel,

315
00:15:28,470 --> 00:15:32,662
til søgning binær i teorien, når vi
havde de virtuelle døre på tavlen,

316
00:15:32,662 --> 00:15:34,370
eller når var Sean
søger efter noget.

317
00:15:34,370 --> 00:15:37,374
Hvis han havde brugt binær søgning, log n
ville være den øvre grænse for, hvor meget

318
00:15:37,374 --> 00:15:38,040
tid, der tager.

319
00:15:38,040 --> 00:15:44,027
Men de algoritmer, der kørte i
log n antaget hvad nøgle detalje?

320
00:15:44,027 --> 00:15:45,360
At listen blev sorteret, right?

321
00:15:45,360 --> 00:15:47,789
Din algoritme er forkert, hvis
Deres input er ikke sorteret,

322
00:15:47,789 --> 00:15:49,830
og alligevel du bruger
noget binær søgning

323
00:15:49,830 --> 00:15:51,704
fordi du måske hoppe
lige over elementet

324
00:15:51,704 --> 00:15:53,600
uden at vide det er faktisk der.

325
00:15:53,600 --> 00:15:55,600
>> Nu, hvad kan dette betyde, store O i en?

326
00:15:55,600 --> 00:15:59,117
Dette betyder ikke, at din algoritme
tager en og kun et trin,

327
00:15:59,117 --> 00:16:01,200
det betyder bare, det tager en
konstant antal trin.

328
00:16:01,200 --> 00:16:04,060
Måske er det 1, måske er det
10, måske er det 1.000,

329
00:16:04,060 --> 00:16:07,750
men det er uafhængigt af
størrelsen af ​​problemet.

330
00:16:07,750 --> 00:16:10,850
Ligegyldigt hvor stor n er,
en konstant tid algoritme

331
00:16:10,850 --> 00:16:12,747
altid har samme antal trin.

332
00:16:12,747 --> 00:16:15,080
Så hvad kunne være en algoritme
vi har talt om eller bare

333
00:16:15,080 --> 00:16:20,418
intuitivt, der kommer til dig, at
altid kører i såkaldt konstant tid?

334
00:16:20,418 --> 00:16:20,918
Ja?

335
00:16:20,918 --> 00:16:22,001
>> Publikum: Læg to numre.

336
00:16:22,001 --> 00:16:25,320
SPEAKER: Add to tal,
2 plus 2 er lig med 4, gjort.

337
00:16:25,320 --> 00:16:27,227
Så der kan arbejde, hvad ellers?

338
00:16:27,227 --> 00:16:28,560
Hvad med mere virkelige verden, ikke?

339
00:16:28,560 --> 00:16:30,686
>> PUBLIKUM: at finde den
første ting på en liste.

340
00:16:30,686 --> 00:16:32,810
SPEAKER: at finde den første
element i en liste, sikker.

341
00:16:32,810 --> 00:16:34,540
Vi har faktisk talt
om arrays allerede

342
00:16:34,540 --> 00:16:36,540
hvordan får du på
første element i et array,

343
00:16:36,540 --> 00:16:40,465
uanset hvor længe den
array er i C-kode?

344
00:16:40,465 --> 00:16:43,090
Du skal bare bruge ligesom beslaget
nul notation, bam, du er der.

345
00:16:43,090 --> 00:16:46,120
Og ja arrays, som en sidebemærkning,
støtte noget almindeligt kendt

346
00:16:46,120 --> 00:16:49,240
tilfældig adgang, random access
hukommelse, fordi du kan bogstavelig talt

347
00:16:49,240 --> 00:16:50,284
springe til en hvilken som helst sted.

348
00:16:50,284 --> 00:16:52,700
Vi kan gøre det endnu mere enkelt
vi kan spole tilbage til uge nul

349
00:16:52,700 --> 00:16:53,900
når vi gjorde Scratch.

350
00:16:53,900 --> 00:16:59,707
Hvor lang tid tog det for
sige blok i Scratch til at udføre?

351
00:16:59,707 --> 00:17:00,790
Bare konstant tid, ikke?

352
00:17:00,790 --> 00:17:03,960
Sig noget, siger
noget, betyder det ikke noget

353
00:17:03,960 --> 00:17:07,359
Hvor stor Ridser verden er, er det altid
kommer til at tage den samme mængde tid

354
00:17:07,359 --> 00:17:08,490
simpelthen at sige noget.

355
00:17:08,490 --> 00:17:11,089
>> Så det er konstant tid,
men hvad er flip side?

356
00:17:11,089 --> 00:17:13,030
Hvis det var øvre
grænser, hvad hvis vi vil

357
00:17:13,030 --> 00:17:17,089
at beskrive de nedre grænser
af vores algoritmer køretid?

358
00:17:17,089 --> 00:17:19,852
Næsten en bedste fald
potentielt, om man vil,

359
00:17:19,852 --> 00:17:23,060
om disse vilkår kunne gælde for bedst
sager, værste tilfælde, gennemsnitlige tilfælde mere

360
00:17:23,060 --> 00:17:26,359
generelt, men lad os bare fokusere
på nedre grænser mere generelt.

361
00:17:26,359 --> 00:17:31,920
Hvad er en algoritme, der har
en nedre grænse af n trin,

362
00:17:31,920 --> 00:17:33,350
eller 2n trin eller 3n Steps?

363
00:17:33,350 --> 00:17:36,241
Nogle faktor n trin,
det er dens nedre grænse.

364
00:17:36,241 --> 00:17:36,740
Ja?

365
00:17:36,740 --> 00:17:37,910
>> PUBLIKUM: boble slags?

366
00:17:37,910 --> 00:17:41,610
>> SPEAKER: boble slags tager
du minimalt n trin, hvorfor?

367
00:17:41,610 --> 00:17:42,279
Hvorfor er det?

368
00:17:42,279 --> 00:17:45,320
Hvorfor skulle der begynder at komme til dig
intuitivt, selv om det ikke bare

369
00:17:45,320 --> 00:17:46,530
endnu?

370
00:17:46,530 --> 00:17:47,030
Ja?

371
00:17:47,030 --> 00:17:47,990
>> Publikum: [uhørligt].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
SPEAKER: Præcis.

374
00:17:52,360 --> 00:17:55,810
I det bedst mulige scenario
boble slags, og en masse af algoritmer,

375
00:17:55,810 --> 00:17:58,769
hvis jeg giver dig otte personer
som allerede er sorteret,

376
00:17:58,769 --> 00:18:00,560
det ville være tåbeligt
for dig, den algoritme,

377
00:18:00,560 --> 00:18:02,202
at gå frem og tilbage
mere end én gang, ikke?

378
00:18:02,202 --> 00:18:04,285
Fordi så snart du
gå gennem listen én gang,

379
00:18:04,285 --> 00:18:08,090
du bør indse, åh, gjorde jeg ikke
swaps, er denne liste sorteres, exit.

380
00:18:08,090 --> 00:18:09,700
Men det kommer til at tage dig n trin.

381
00:18:09,700 --> 00:18:12,033
>> Og omvendt, hvad er en anden
måde at tænke om det?

382
00:18:12,033 --> 00:18:15,240
Bubble slags er en omega,
så at sige, af n,

383
00:18:15,240 --> 00:18:19,050
fordi hvis man ser på
færre end n elementer, hvad

384
00:18:19,050 --> 00:18:23,009
er det grundlæggende spørgsmål der?

385
00:18:23,009 --> 00:18:24,550
Du ved ikke, om det er sorteret, højre.

386
00:18:24,550 --> 00:18:26,800
Vi mennesker måske blik på otte
mennesker og være ligesom, åh, det er sorteret,

387
00:18:26,800 --> 00:18:28,430
som ikke tage mig n trin, men det gjorde.

388
00:18:28,430 --> 00:18:30,810
Dine øjne, selvom du slags
af har et stort synsfelt,

389
00:18:30,810 --> 00:18:33,184
du kiggede på otte elementer,
du kiggede på otte personer,

390
00:18:33,184 --> 00:18:34,610
der er otte trin effektivt.

391
00:18:34,610 --> 00:18:38,612
Og kun hvis jeg går gennem hele
liste gør jeg indser, ja, sorteres.

392
00:18:38,612 --> 00:18:41,320
Hvis jeg stopper halvvejs tænker alle
højre, det er temmelig sorteres hidtil,

393
00:18:41,320 --> 00:18:42,520
Hvad er oddsene det ikke sorteres?

394
00:18:42,520 --> 00:18:44,186
Det algoritmer vil ikke være korrekt.

395
00:18:44,186 --> 00:18:46,250
Kunne være hurtigere, men forkert.

396
00:18:46,250 --> 00:18:48,500
>> Så nu har vi en måde at
beskriver en nedre grænser,

397
00:18:48,500 --> 00:18:49,710
og hvad med konstant tid?

398
00:18:49,710 --> 00:18:54,565
Hvad er en algoritme, der har en lavere
bundet på sin køretid på én?

399
00:18:54,565 --> 00:18:58,350
1 trin 2 trin, 10 trin, men
konstant, uafhængig af n

400
00:18:58,350 --> 00:18:59,310
størrelsen af ​​input?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Ja, i ryggen.

403
00:19:04,600 --> 00:19:05,309
>> Publikum: printf?

404
00:19:05,309 --> 00:19:06,183
SPEAKER: Hvad er det?

405
00:19:06,183 --> 00:19:07,184
Publikum: printf?

406
00:19:07,184 --> 00:19:07,850
SPEAKER: printf.

407
00:19:07,850 --> 00:19:08,400
OK, helt sikkert.

408
00:19:08,400 --> 00:19:10,720
Så det tager et fast antal trin.

409
00:19:10,720 --> 00:19:13,170
Og jeg skulle nu-- nu,
vi taler om C-kode

410
00:19:13,170 --> 00:19:16,040
og ikke Scratch, noget
ligesom sige, med printf,

411
00:19:16,040 --> 00:19:17,710
vi skal begynde at få forsigtig.

412
00:19:17,710 --> 00:19:21,090
Fordi printf tager
input, det er en streng,

413
00:19:21,090 --> 00:19:23,220
og strygere har teknisk har længde.

414
00:19:23,220 --> 00:19:25,530
Så hvis vi nu ønsker at plukke
på dig, hvis du ikke har noget imod,

415
00:19:25,530 --> 00:19:29,430
teknisk kunne vi argumentere for, at printf
tager en variabel længde-indgang,

416
00:19:29,430 --> 00:19:32,270
og sikkert det kan tage mere
tid til at udskrive en streng denne lange,

417
00:19:32,270 --> 00:19:33,560
end denne lange.

418
00:19:33,560 --> 00:19:36,570
>> Så hvad nu hvis vi betragter bare
sortering og søgning eksempler?

419
00:19:36,570 --> 00:19:40,450
Hvad med Mike Smith i telefonen
bog, eller binær søgning mere generelt?

420
00:19:40,450 --> 00:19:42,220
I bedste fald, hvad der kan ske?

421
00:19:42,220 --> 00:19:45,577
Jeg åbne telefonbogen, og bam,
der er Mike Smiths nummer.

422
00:19:45,577 --> 00:19:46,660
Jeg kan ringe til ham med det samme.

423
00:19:46,660 --> 00:19:49,390
>> Tog et skridt, måske to trin,
men et konstant antal af trin

424
00:19:49,390 --> 00:19:50,230
hvis jeg fik heldig.

425
00:19:50,230 --> 00:19:52,570
Og helt ærligt, vi så på
Mandag din klassekammerat

426
00:19:52,570 --> 00:19:54,710
få ganske heldig to gange i træk.

427
00:19:54,710 --> 00:19:57,050
Og det var faktisk konstant
tid i et nedre grænser

428
00:19:57,050 --> 00:20:01,280
på algoritmen pågældende til at finde
nummer 50 bag de lukkede

429
00:20:01,280 --> 00:20:01,830
døre.

430
00:20:01,830 --> 00:20:06,400
>> Nu, som en sidebemærkning, hvis du opdager
at både store O, den øvre grænse,

431
00:20:06,400 --> 00:20:09,310
og omega, den nedre grænse,
er en i samme,

432
00:20:09,310 --> 00:20:11,830
er den samme formel
parenteser, kan du også

433
00:20:11,830 --> 00:20:15,170
sige, bare for at være smarte,
at noget er i theta

434
00:20:15,170 --> 00:20:18,270
n eller theta af en anden værdi.

435
00:20:18,270 --> 00:20:20,661
Det betyder bare, når store
O og omega er de samme.

436
00:20:20,661 --> 00:20:21,910
Nu hvad udvælgelse slags?

437
00:20:21,910 --> 00:20:23,400
Lad os bruge denne nye ordforråd.

438
00:20:23,400 --> 00:20:27,407
I udvælgelsen sortere, hvad vi var
gør igen og igen, og igen?

439
00:20:27,407 --> 00:20:29,990
Jeg gik frem og tilbage gennem
listen, på udkig efter hvem?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
Det mindste antal.

442
00:20:34,730 --> 00:20:37,560
>> Så hvordan mange trin, hvordan
mange sammenligninger gjorde jeg

443
00:20:37,560 --> 00:20:43,250
nødt til at gøre for at finde ud af hvem
det mindste element i listen var?

444
00:20:43,250 --> 00:20:44,437
n minus 1, højre?

445
00:20:44,437 --> 00:20:47,770
Fordi hvis jeg bare starte med det ene er jeg
givet, og jeg begynder at sammenligne ham eller hende,

446
00:20:47,770 --> 00:20:49,519
så ham eller hende, ham
eller hende, ham eller hende, jeg

447
00:20:49,519 --> 00:20:52,010
kan kun parre elementer
sammen n minus 1 gange.

448
00:20:52,010 --> 00:20:55,630
Så udvælgelse sortere på samme måde tager
n minus 1 trin første gang.

449
00:20:55,630 --> 00:20:59,540
>> Hvor mange skridt tager det mig til
finde den næstmindste element?

450
00:20:59,540 --> 00:21:02,920
n minus 2, fordi jeg er dum
hvis jeg bliver ved med at kigge på de samme mennesker

451
00:21:02,920 --> 00:21:06,280
igen, hvis jeg allerede har valgt ham
eller hende, og sætte dem i deres sted.

452
00:21:06,280 --> 00:21:09,270
Og det tredje trin, n
minus 3 og derefter n minus 4.

453
00:21:09,270 --> 00:21:11,020
Vi har set dette mønster
før, og faktisk

454
00:21:11,020 --> 00:21:13,460
udvælgelse sortere på samme måde
har en øvre grænse

455
00:21:13,460 --> 00:21:16,210
n kvadreret hvis vi gør op, at summation.

456
00:21:16,210 --> 00:21:19,790
Hvad er dens nedre grænse, udvælgelse slags?

457
00:21:19,790 --> 00:21:25,350
Minimalt, hvor meget tid skal udvælgelsen
sortere tage, som vi definerede det på mandag?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Foreslå to muligheder.

460
00:21:30,490 --> 00:21:32,360
Måske er det n, som før.

461
00:21:32,360 --> 00:21:35,040
Måske er det n kvadreret, da det
er nu som den øvre grænse.

462
00:21:35,040 --> 00:21:35,874
>> PUBLIKUM: n potens.

463
00:21:35,874 --> 00:21:36,664
SPEAKER: n potens.

464
00:21:36,664 --> 00:21:37,368
Hvorfor?

465
00:21:37,368 --> 00:21:40,060
>> Publikum: Fordi du har
at definere [uhørligt].

466
00:21:40,060 --> 00:21:41,510
>> SPEAKER: Præcis.

467
00:21:41,510 --> 00:21:45,077
Mindst lige så jeg definerede udvælgelse slags
det var temmelig naiv, holde i gang,

468
00:21:45,077 --> 00:21:46,160
finde det mindste element.

469
00:21:46,160 --> 00:21:47,770
Gå igen, finde det mindste element.

470
00:21:47,770 --> 00:21:49,490
Gå igen, finde det mindste element.

471
00:21:49,490 --> 00:21:51,700
Der er ingen form for
optimering i der,

472
00:21:51,700 --> 00:21:54,350
kunne lade mig afbryde efter
bare n eller så trin.

473
00:21:54,350 --> 00:21:57,080
Så ja, udvælgelse
sortere, omega n potens.

474
00:21:57,080 --> 00:22:00,667
>> Hvad med indsættelse slags, hvor jeg tog
hvem jeg fik, og så smed jeg ham

475
00:22:00,667 --> 00:22:01,750
eller hende i det rigtige sted?

476
00:22:01,750 --> 00:22:04,958
Derefter fortsatte jeg til den anden person,
smed ham eller hende i det rigtige sted.

477
00:22:04,958 --> 00:22:07,910
Så den næste person, smed
ham eller hende i det rigtige sted.

478
00:22:07,910 --> 00:22:10,537
Bemærk at dette er meget
lineære, så at sige.

479
00:22:10,537 --> 00:22:12,620
Jeg er en lige linje, er jeg
ikke gå frem og tilbage,

480
00:22:12,620 --> 00:22:16,080
Jeg har aldrig ser tilbage virkelig, men
hvad der sker, når jeg sætter ham

481
00:22:16,080 --> 00:22:20,302
eller hende ind i begyndelsen af
listen som vi gjorde på mandag?

482
00:22:20,302 --> 00:22:21,010
Hvad sker der?

483
00:22:21,010 --> 00:22:21,510
Ja?

484
00:22:21,510 --> 00:22:23,122
Publikum: [uhørligt].

485
00:22:23,122 --> 00:22:24,830
SPEAKER: Ja, det
var fangsten, right?

486
00:22:24,830 --> 00:22:26,746
Du husker muligvis fra
dine klassekammerater, hvis de

487
00:22:26,746 --> 00:22:29,670
gjorde enhver bevægelse med
deres fødder, det var en operation.

488
00:22:29,670 --> 00:22:33,610
Så hvis der var tre mennesker her og
den nye person tilhørte vej derovre,

489
00:22:33,610 --> 00:22:37,360
på en lang scene som denne, sikker, han
eller hun kunne bare gå til den bitre ende.

490
00:22:37,360 --> 00:22:40,074
Men hvis vi tænker på en
computer og en vifte af hukommelse,

491
00:22:40,074 --> 00:22:41,990
disse mennesker går
nødt til at blande i

492
00:22:41,990 --> 00:22:43,260
at gøre plads til denne person.

493
00:22:43,260 --> 00:22:46,930
Og så at n minus 1 shufflings,
n minus 2 shufflings n

494
00:22:46,930 --> 00:22:50,660
minus 3 shufflings er lige slags
sker bag mig, ikke foran mig

495
00:22:50,660 --> 00:22:52,710
som før, i en vis forstand.

499
00:22:52,557 --> 00:22:54,640
Nu som en sidebemærkning, og som
du måske har set online

500
00:22:54,640 --> 00:22:57,699
hvis du begynder at rode rundt omkring
sorterer, der er så mange forskellige dem

501
00:22:57,699 --> 00:22:59,490
derude, nogle af dem
bedre end andre.

502
00:22:59,490 --> 00:23:02,200
Faktisk bogosort er en
det er lidt sjovt at se op.

503
00:23:02,200 --> 00:23:06,650
Bogosort tager et sæt af
tal eller sige et spil kort,

504
00:23:06,650 --> 00:23:09,870
tilfældigt blander dem, og
kontrollerer, om de er sorteret.

505
00:23:09,870 --> 00:23:12,130
Og hvis ikke, gør det igen.

506
00:23:12,130 --> 00:23:14,140
Og hvis ikke, gør det igen.

507
00:23:14,140 --> 00:23:15,440
Hvis ikke, gør det igen.

508
00:23:15,440 --> 00:23:17,060
Utrolig dumt.

509
00:23:17,060 --> 00:23:19,520
>> Og ja, hvis du læse
ligesom Wikipedia-artikel,

510
00:23:19,520 --> 00:23:21,200
sit øgenavn er dum slags.

511
00:23:21,200 --> 00:23:25,180
Det vil i sidste ende arbejde,
forhåbentlig givet tilstrækkelig tid,

512
00:23:25,180 --> 00:23:28,240
men at mængden af ​​tid
kunne tage temmelig lang tid.

513
00:23:28,240 --> 00:23:31,650
Så hvis jeg kunne, lad os fremskynde tingene
op fra Mary Beth eksempel tidligere,

514
00:23:31,650 --> 00:23:35,150
ved at have et par flere elementer,
men to processorer.

515
00:23:35,150 --> 00:23:37,100
To mennesker, hvis du
ville ikke have noget imod at tilslutte mig.

516
00:23:37,100 --> 00:23:40,972
Hvordan omkring 1 herovre, og
lad os go-- ingen derovre?

517
00:23:40,972 --> 00:23:41,722
Ingen derovre?

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
Du med den sorte
skjorte, ja, kom nu ned.

520
00:23:44,190 --> 00:23:45,000
Okay, hvad er dit navn?

521
00:23:45,000 --> 00:23:45,720
>> Publikum: Peter.

522
00:23:45,720 --> 00:23:46,100
>> SPEAKER: Hvad er det?

523
00:23:46,100 --> 00:23:46,766
>> Publikum: Peter.

524
00:23:46,766 --> 00:23:49,450
SPEAKER: Peter, David, rart at møde dig.

525
00:23:49,450 --> 00:23:53,670
Okay, vi har Peter her, hvis du
ønsker at komme på bordet herovre.

526
00:23:53,670 --> 00:23:54,550
Og hvad er dit navn?

527
00:23:54,550 --> 00:23:55,216
>> Publikum: Elena.

528
00:23:55,216 --> 00:23:55,970
SPEAKER: Elena.

529
00:23:55,970 --> 00:23:57,030
OK, rart at møde dig.

530
00:23:57,030 --> 00:23:58,060
Elena mødes Peter.

531
00:23:58,060 --> 00:23:59,170
Peter Elena.

532
00:23:59,170 --> 00:24:02,290
Og vi har brug for Andrew
heroppe så godt, tak.

533
00:24:02,290 --> 00:24:06,107
Og din udfordring går
at være at sortere et spil kort.

534
00:24:06,107 --> 00:24:08,190
Og hvis uvant, dæk
kort skal i sidste ende

535
00:24:08,190 --> 00:24:11,064
sorteres lidt noget lignende
dette, hvor vi vil gøre klubberne, så

536
00:24:11,064 --> 00:24:13,660
de spader, så hjerter og
diamanter, fra es som én,

537
00:24:13,660 --> 00:24:15,570
hele vejen op til kongen.

538
00:24:15,570 --> 00:24:20,890
>> De kort, jeg har tænkt mig at give dig
vil være 52 i mængde.

539
00:24:20,890 --> 00:24:23,160
Vi kommer til på samme måde
gang du, på bare et øjeblik.

540
00:24:23,160 --> 00:24:26,410
Vi kommer til at kaste Andrew
op på skærmen her,

541
00:24:26,410 --> 00:24:28,170
så at se på som du gør dette.

542
00:24:28,170 --> 00:24:31,070
Og så, at alt dette
er desto mere synlige,

543
00:24:31,070 --> 00:24:33,490
det er de kort, jeg fik på Amazon.

544
00:24:33,490 --> 00:24:42,861
Så de er allerede tilfældigt
sorteret, og vi vil gang du.

545
00:24:42,861 --> 00:24:44,610
Og vi vil
holde det reelle denne gang,

546
00:24:44,610 --> 00:24:47,820
så vi vil forsøge at lægge pres på dig
fordi ellers vil det få kedelige

547
00:24:47,820 --> 00:24:48,460
hurtigt.

548
00:24:48,460 --> 00:24:53,860
Hvis du kunne gå til at sortere 52
elementer sammen via nogle midler, nu.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> Og igen, som vi ser disse
fyre gør, hvad der i sidste ende

551
00:25:07,180 --> 00:25:10,200
vil producere en indlysende
resultat, så tænk virkelig

552
00:25:10,200 --> 00:25:12,962
hvordan de hver gør det,
hvordan du kan beskrive det.

553
00:25:12,962 --> 00:25:15,045
Fordi igen, disse er
alle processer, algoritmer

554
00:25:15,045 --> 00:25:17,090
at vi tager for givet som et menneske.

555
00:25:17,090 --> 00:25:22,349
Men du har sikkert længe haft
intuition, længe før du selv

556
00:25:22,349 --> 00:25:24,390
tænkt på at tage et
datalogi klasse du

557
00:25:24,390 --> 00:25:27,223
kunne have haft intuitionen med
som at løse problemer som dette.

558
00:25:27,223 --> 00:25:29,560
Men når du genkende
mønstrene og begynde

559
00:25:29,560 --> 00:25:32,407
at formalisere de skridt, med hvilke
du at løse disse problemer,

560
00:25:32,407 --> 00:25:35,490
du opdage, at du kan løse meget
mere interessant og meget mere kompleks

561
00:25:35,490 --> 00:25:39,190
problemer hurtigt.

562
00:25:39,190 --> 00:25:42,351
Så nogen fra publikum, hvad er
mindst et element af algoritmen

563
00:25:42,351 --> 00:25:43,350
at de bruger her?

564
00:25:43,350 --> 00:25:44,275
>> Publikum: [uhørligt]

565
00:25:44,275 --> 00:25:45,150
SPEAKER: Hvad er det?

566
00:25:45,150 --> 00:25:47,062
Publikum: efter kulør.

567
00:25:47,062 --> 00:25:47,770
SPEAKER: efter kulør.

568
00:25:47,770 --> 00:25:50,630
Så først de clustering
alle de diamanter sammen

569
00:25:50,630 --> 00:25:52,560
det synes alle
hjerter sammen det ser ud,

570
00:25:52,560 --> 00:25:56,520
og så videre, uden hensyn
til numrene på kortene.

571
00:25:56,520 --> 00:26:00,900
Og nu de ser, for eksempel,
at sortere dem efter antal.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Meget godt.

574
00:26:08,910 --> 00:26:12,370
>> Okay, så hvad der kommer til
være det sidste skridt så her?

575
00:26:12,370 --> 00:26:16,950
Når vi har fire sorterede dragter, hvad
skal vi gøre for at de fire bunker

576
00:26:16,950 --> 00:26:20,059
for at opnå en
sorteres dæk, simpelthen?

577
00:26:20,059 --> 00:26:21,350
Så vi er nødt til at flette dem igen.

578
00:26:21,350 --> 00:26:25,160
>> Så der er en interessant idé, som
igen, daresay, er meget intuitiv selv

579
00:26:25,160 --> 00:26:28,140
hvis du aldrig kunne have slået
den slags mærkat på det.

580
00:26:28,140 --> 00:26:31,900
Denne grundlæggende opfattelse af at dividere
problemet ikke i halvdelen af ​​denne tid,

581
00:26:31,900 --> 00:26:33,410
men i det mindste i fire stykker.

582
00:26:33,410 --> 00:26:36,810
Løsning temmelig meget
fundamentalt identiske problemer

583
00:26:36,810 --> 00:26:40,480
i isolering af hinanden,
og derefter sammenlægge resultaterne.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
Og fremragende, gjort.

586
00:26:50,140 --> 00:26:52,140
Okay, en stor rund
bifald, hvis vi kunne.

587
00:26:52,140 --> 00:26:56,480
>> [Applaus]

588
00:26:56,480 --> 00:26:59,740
>> SPEAKER: Jeg har ingen idé om, hvad du vil
gøre med disse, men her du går.

589
00:26:59,740 --> 00:27:01,690
Tak så meget.

590
00:27:01,690 --> 00:27:04,660
Så lad os se, to minutters
og for otte sekunder,

591
00:27:04,660 --> 00:27:07,490
Hvis du gerne vil udfordre dine venner.

592
00:27:07,490 --> 00:27:12,160
Hvad er så gå til
være en tage væk fra dette

593
00:27:12,160 --> 00:27:13,830
at vi kan udnytte mere generelt?

594
00:27:13,830 --> 00:27:16,080
Nå, tænker tilbage på
denne række af tal,

595
00:27:16,080 --> 00:27:19,060
og tænker tilbage nu til nogle af de
pseudokode vi har skrevet tidligere,

596
00:27:19,060 --> 00:27:22,080
og dette var pseudokode til
løse telefonbogen problemet.

597
00:27:22,080 --> 00:27:25,150
Hvorved i pseudokode I
opregnet en mere metodisk

598
00:27:25,150 --> 00:27:28,400
beskrive, hvordan jeg gjorde en meget intuitiv
humant algoritme dividere telefonen

599
00:27:28,400 --> 00:27:31,650
bog i halve, gentag, gentag, gentag,
indtil jeg finder en som Mike Smith,

600
00:27:31,650 --> 00:27:33,790
hvis han virkelig er i telefonbogen.

601
00:27:33,790 --> 00:27:37,610
>> Men jeg slags brugt, hvad jeg vil kalde
en meget iterativ tilgang her,

602
00:27:37,610 --> 00:27:42,160
særlig meddelelse linje 8 og linie 11.

603
00:27:42,160 --> 00:27:46,750
Det er tegn på en iterativ
tilgang, en looping tilgang,

604
00:27:46,750 --> 00:27:49,040
fordi det er præcis
adfærd de inducerer.

605
00:27:49,040 --> 00:27:52,910
Disse linjer begge sige gå til
linje tre, og du kan slags

606
00:27:52,910 --> 00:27:55,140
tænke på det i din
indre øje som en løkke.

607
00:27:55,140 --> 00:27:59,080
Det fortæller dig at gå tilbage op til trin
tre og gentage igen og igen,

608
00:27:59,080 --> 00:28:00,010
og igen.

609
00:28:00,010 --> 00:28:04,410
>> Men hvad nu, hvis vi udnytter en central idé
her, vi gjorde ikke sidste gang,

610
00:28:04,410 --> 00:28:10,280
og forenkle linje 8 og
linie 11 og deres naboer

611
00:28:10,280 --> 00:28:12,840
som netop dette, i gult.

612
00:28:12,840 --> 00:28:16,480
Det er ikke fundamentalt afkorte
pseudokoden meget,

613
00:28:16,480 --> 00:28:20,530
men det er fundamentalt at ændre
arten af ​​min algoritme.

614
00:28:20,530 --> 00:28:24,220
Hvad jeg nu siger
i trin 7, i trin 10,

615
00:28:24,220 --> 00:28:29,140
er at søge efter Mike
på præcis samme måde,

616
00:28:29,140 --> 00:28:31,580
men kun i den venstre
halvdelen eller højre halvdel.

617
00:28:31,580 --> 00:28:33,420
>> Så med andre ord, hvis
Jeg starter fra trin et,

618
00:28:33,420 --> 00:28:36,150
afhente telefonbog, åben for midten
af telefonbogen, se på navnene,

619
00:28:36,150 --> 00:28:39,010
hvis Smith er blandt
hedder, kalder Mike, ellers

620
00:28:39,010 --> 00:28:44,340
hvis Smith er tidligere i bogen, trin syv
søge efter Mike i venstre halvdel af bogen.

621
00:28:44,340 --> 00:28:47,130
Men den slags føles
det forlader mig hængende, ikke?

622
00:28:47,130 --> 00:28:49,240
I gul, er en
instruktion, men hvordan gør jeg

623
00:28:49,240 --> 00:28:51,870
søge efter Mike i venstre
halvdelen af ​​telefonbogen?

624
00:28:51,870 --> 00:28:54,210
Hvor har jeg en
algoritme, som jeg

625
00:28:54,210 --> 00:28:57,100
kan søge efter en som Mike Smith?

626
00:28:57,100 --> 00:28:58,980
Tja, det er stirrer os i ansigtet.

627
00:28:58,980 --> 00:29:03,090
Jeg kan bogstaveligt talt bruge den nøjagtige samme
program effektivt går op til toppen

628
00:29:03,090 --> 00:29:06,490
igen og re-drift
de samme linjer kode.

629
00:29:06,490 --> 00:29:10,610
>> Så selv om dette skulle føle
som lidt af en cyklisk definition

630
00:29:10,610 --> 00:29:13,480
hvor du svarer en persons
spørgsmål ved bare slags spørger

631
00:29:13,480 --> 00:29:15,990
det samme spørgsmål igen,
ligesom hvorfor, hvorfor, hvorfor?

632
00:29:15,990 --> 00:29:21,580
Virkeligheden er, fordi vi hårdt har kodet
et par af særlige linjer, trin 4,

633
00:29:21,580 --> 00:29:25,320
der er en hvis, og trin 12, som
er reelt en anden gren,

634
00:29:25,320 --> 00:29:30,120
fordi vi har disse lappeløsninger,
denne algoritme vil ophøre, hvis vi

635
00:29:30,120 --> 00:29:32,050
finde Mike, eller hvis vi ikke gør det.

636
00:29:32,050 --> 00:29:36,810
Men i trin 7 og 10 nu, vi har
hvad vi vil kalde en rekursiv algoritme.

637
00:29:36,810 --> 00:29:40,420
Og rekursion er faktisk en kraftfuld idé
det er en lille sind bøjning først,

638
00:29:40,420 --> 00:29:42,500
at vi nu kan anvende som følger.

639
00:29:42,500 --> 00:29:46,600
>> Flet slags vil være den sidste slags,
vi ser på, i det mindste i klassen formelt.

640
00:29:46,600 --> 00:29:50,040
Og det er fundamentalt anderledes
fra de sidste tre, og bestemt

641
00:29:50,040 --> 00:29:52,140
sidste fire, hvis vi inkluderer bogosort.

642
00:29:52,140 --> 00:29:54,810
Her er pseudokode til sammenfletningen slags.

643
00:29:54,810 --> 00:30:00,170
Når på input af n elementer, så givet
et array af størrelse n hvis n er mindre end 2,

644
00:30:00,170 --> 00:30:01,040
tilbage.

645
00:30:01,040 --> 00:30:03,610
Så hvorfor har jeg det
tilregnelighed tjek først?

646
00:30:03,610 --> 00:30:09,477
Hvad er konsekvenserne, hvis jeg giver dig
et array, hvis længde n er mindre end 2?

647
00:30:09,477 --> 00:30:11,060
Det er allerede sorteret, naturligvis, ikke?

648
00:30:11,060 --> 00:30:13,640
Fordi listen har enten
et element, som er trivielt

649
00:30:13,640 --> 00:30:15,180
sorteres, fordi det er
det eneste der.

650
00:30:15,180 --> 00:30:18,138
Eller, det er en størrelse nul, hvilket betyder,
der er intet at sortere, så ved naturen

651
00:30:18,138 --> 00:30:18,720
det er sorteret.

652
00:30:18,720 --> 00:30:20,410
Der er bare ikke noget galt der.

653
00:30:20,410 --> 00:30:22,310
Så det er vores såkaldt base case.

654
00:30:22,310 --> 00:30:24,440
>> Det er ens i ånden
til hvad vi gjorde med Mike.

655
00:30:24,440 --> 00:30:26,023
Hvis Mike i telefonbogen, ringe til ham.

656
00:30:26,023 --> 00:30:27,740
Hvis han ikke er der, give op.

657
00:30:27,740 --> 00:30:31,240
Det er en såkaldt base case, for at sikre
denne algoritme i slutningen af ​​dagen

658
00:30:31,240 --> 00:30:33,540
vil stoppe i visse omstændigheder.

659
00:30:33,540 --> 00:30:37,890
>> Men her er det spring af tro nu, ellers,
sortere den venstre halvdel af elementerne,

660
00:30:37,890 --> 00:30:39,740
derefter sortere det rigtige
halvdelen af ​​de elementer,

661
00:30:39,740 --> 00:30:41,189
og derefter flette de sorterede halvdele.

662
00:30:41,189 --> 00:30:43,230
Og her er hvor det føles
ligesom vi copping ud.

663
00:30:43,230 --> 00:30:46,900
Jeg har bedt dig om at sortere
n elementer, og jeg er

664
00:30:46,900 --> 00:30:50,712
sige, OK, det ved at sortere
venstre og sortering højre.

665
00:30:50,712 --> 00:30:52,420
Men jeg siger en
andre ting, og det

666
00:30:52,420 --> 00:30:55,530
er det centralt tema ser det ud
i intuition hidtil,

667
00:30:55,530 --> 00:30:57,380
der er denne tredje trin for at fusionere.

668
00:30:57,380 --> 00:31:00,430
Hvilke selvom det
synes så dum i ånden,

669
00:31:00,430 --> 00:31:02,320
ligesom bare flette tingene
sammen, ser det ud til

670
00:31:02,320 --> 00:31:05,380
at være et vigtigt skridt hen imod
samling af to problemer,

671
00:31:05,380 --> 00:31:07,330
blev opdelt i sidste ende i halve.

672
00:31:07,330 --> 00:31:12,090
>> Så fusionere sortere, lad os gøre det, hvis du vil
humor mig, med en mere demonstration,

673
00:31:12,090 --> 00:31:14,730
bare så vi har nogle
numre til at arbejde med.

674
00:31:14,730 --> 00:31:19,470
Kan jeg udveksle otte stress
kugler til otte personer?

675
00:31:19,470 --> 00:31:29,320
Okay, hvad med dig tre, du fire
i dette afsnit, fem, seks, og lad os

676
00:31:29,320 --> 00:31:30,720
gør 7, 8, kom op.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK, ja OK.

679
00:31:36,520 --> 00:31:38,640
Minus 8, der går vi, plus 1.

680
00:31:38,640 --> 00:31:39,150
Fremragende.

681
00:31:39,150 --> 00:31:42,000
Okay kom op, lad os
hurtigt give dig tal.

682
00:31:42,000 --> 00:31:50,800
Nummer to, nummer tre, nummer fire,
nummer fem, seks, syv og otte.

683
00:31:50,800 --> 00:31:52,140
Jeg gjorde otte rigtigt denne gang.

684
00:31:52,140 --> 00:31:56,390
>> OK, så gå videre, hvis du kunne, og
lad os sortere i den oprindelige rækkefølge

685
00:31:56,390 --> 00:31:59,810
at vi havde i går, som kiggede
som dette, hvis du ikke har noget imod.

686
00:31:59,810 --> 00:32:03,620
Og lad os gøre det i foran af tabellen.

687
00:32:03,620 --> 00:32:06,510
Okay, så flette slags.

688
00:32:06,510 --> 00:32:08,820
Det er her, det går
at få slags interessant,

689
00:32:08,820 --> 00:32:12,800
fordi jeg synes at give mig
så meget mindre information dag.

690
00:32:12,800 --> 00:32:15,149
>> Så fusionere slags først
på input af n elementer,

691
00:32:15,149 --> 00:32:18,440
og er naturligvis ikke mindre end to, det er
otte, så jeg har nogle mere arbejde at gøre.

692
00:32:18,440 --> 00:32:21,140
Så nu mentalt vi som en klasse
er nu i andet filial,

693
00:32:21,140 --> 00:32:22,540
hvilket betyder tre trin.

694
00:32:22,540 --> 00:32:25,017
Først vil jeg nødt til at sortere
venstre halvdel af elementerne.

695
00:32:25,017 --> 00:32:26,350
Så hvordan kan jeg gå om at gøre dette?

696
00:32:26,350 --> 00:32:28,950
Nå, jeg har tænkt mig at slags
mentalt opdele listen her,

697
00:32:28,950 --> 00:32:30,700
du behøver ikke at
fysisk at bevæge sig, og jeg er

698
00:32:30,700 --> 00:32:33,180
går kun at fokusere på
venstre halvdel af elementerne her.

699
00:32:33,180 --> 00:32:36,770
Så hvordan kan jeg gå om sortering
en liste nu størrelse fire?

700
00:32:36,770 --> 00:32:38,730
Hvad er min algoritme?

701
00:32:38,730 --> 00:32:42,580
Først vil jeg kontrollere, er n mindre end to, nej,
så jeg går videre til andet blok igen.

702
00:32:42,580 --> 00:32:43,900
Sorter forlod halvdelen af ​​elementer.

703
00:32:43,900 --> 00:32:45,608
>> Så nu igen, mentalt
og det er her

704
00:32:45,608 --> 00:32:49,550
du er nødt til at optjene en masse
mental historie, hvis du vil.

705
00:32:49,550 --> 00:32:51,940
Nu er jeg sortering venstre
halvdelen af ​​den venstre halvdel.

706
00:32:51,940 --> 00:32:57,000
Okay, så nu kalder jeg min samme merge
sorteringsalgoritme er n mindre end to?

707
00:32:57,000 --> 00:33:00,590
Nej, det er to, så jeg er nødt til at sortere
den venstre halvdel og den højre halvdel.

708
00:33:00,590 --> 00:33:02,042
Så her vi går, sortere venstre halvdel.

709
00:33:02,042 --> 00:33:03,750
Hvorfor gør du ikke bare
tage et skridt fremad.

710
00:33:03,750 --> 00:33:04,415
Hvad er dit navn?

711
00:33:04,415 --> 00:33:04,860
>> Publikum: Darren.

712
00:33:04,860 --> 00:33:05,260
>> SPEAKER: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan har trådt frem.

714
00:33:06,040 --> 00:33:06,748
>> Publikum: Darren.

715
00:33:06,748 --> 00:33:09,000
SPEAKER: Darren, gjort.

716
00:33:09,000 --> 00:33:10,090
Sagde du Darren eller Dan?

717
00:33:10,090 --> 00:33:10,550
>> Publikum: Darren.

718
00:33:10,550 --> 00:33:11,216
>> SPEAKER: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren er trådt
frem og han nu sorteres.

720
00:33:14,422 --> 00:33:16,130
Og det er næsten en
åndsforladt krav, right?

721
00:33:16,130 --> 00:33:18,862
Jeg kan ikke rigtig synes at være at opnå
noget, men lad os fortsætte.

722
00:33:18,862 --> 00:33:20,820
Lad mig nu sortere ret
halvdelen af ​​elementerne.

723
00:33:20,820 --> 00:33:21,200
Hvad er dit navn?

724
00:33:21,200 --> 00:33:21,690
>> Publikum: Luke.

725
00:33:21,690 --> 00:33:22,273
>> SPEAKER: Luke.

726
00:33:22,273 --> 00:33:23,400
Kom, træd frem.

727
00:33:23,400 --> 00:33:25,640
Udført, har jeg ordnet Luke.

728
00:33:25,640 --> 00:33:28,570
Den venstre halvdel er nu sorteret og
højre halvdel er nu sorteret,

729
00:33:28,570 --> 00:33:30,770
men igen, der er et vigtigt skridt her.

730
00:33:30,770 --> 00:33:32,940
Hvad gør jeg næste skal gøre?

731
00:33:32,940 --> 00:33:33,941
Flet de sorterede halvdele.

732
00:33:33,941 --> 00:33:36,648
Nu vil vi bare have
alle frem og tilbage på denne måde,

733
00:33:36,648 --> 00:33:38,620
fordi jeg slags brug
nogle bunden plads.

734
00:33:38,620 --> 00:33:40,411
Det er næsten ligesom disse
fyre er på et bord,

735
00:33:40,411 --> 00:33:42,460
og jeg har brug for lidt plads
at flytte dem rundt på.

736
00:33:42,460 --> 00:33:44,170
Så jeg har tænkt mig at fusionere
jer ved at se

737
00:33:44,170 --> 00:33:45,960
på den venstre halvdel og den højre halvdel.

738
00:33:45,960 --> 00:33:48,740
Og der naturligvis kommer først,
venstre halvdel eller højre halvdel?

739
00:33:48,740 --> 00:33:52,710
Så lige halvdel, så lad os gå Luke løbet
her til Darren oprindelige holdning.

740
00:33:52,710 --> 00:33:57,640
Og nu at fusionere deres venstre halvdel i,
Darren kommer til at bevæge sig lige der.

741
00:33:57,640 --> 00:33:59,750
>> Så føles næsten
en boble slags effekt,

742
00:33:59,750 --> 00:34:02,482
men min grundlæggende algoritme,
meget anderledes denne gang.

743
00:34:02,482 --> 00:34:04,815
Men nu er, hvor tingene bliver
lidt irriterende, fordi du

744
00:34:04,815 --> 00:34:06,810
nødt til at spole tilbage mentalt
hvor har jeg forlader slukket.

745
00:34:06,810 --> 00:34:09,893
Jeg har netop fusioneret de sorterede halvdele,
hvilket betyder, at jeg er, hvor i min algoritme?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Jeg er nødt til at sortere den højre halvdel, højre?

748
00:34:13,770 --> 00:34:15,910
>> Hvis du spole tilbage, bogstaveligt
på videoen, vil du

749
00:34:15,910 --> 00:34:18,339
se, at vi fik til dette
punkt i Lukas og Darren

750
00:34:18,339 --> 00:34:21,370
ved at sortere venstre
halvdelen af ​​den venstre halvdel.

751
00:34:21,370 --> 00:34:23,430
Så vi fusionerede dem
sorterede halvdele, som

752
00:34:23,430 --> 00:34:27,941
betyder, at næste skridt er sortere
højre halvdel af den venstre halvdel.

753
00:34:27,941 --> 00:34:29,649
Okay, så lad os
gøre dette hurtigere.

754
00:34:29,649 --> 00:34:33,282
Okay, seks, vil jeg hævde,
du er nu sorteret, kom frem.

755
00:34:33,282 --> 00:34:33,990
Hvad er dit navn?

756
00:34:33,990 --> 00:34:34,589
>> Publikum: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> SPEAKER: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano er nu sorteret.

759
00:34:36,010 --> 00:34:36,450
Og hvad er dit navn?

760
00:34:36,450 --> 00:34:37,080
>> Publikum: Alex.

761
00:34:37,080 --> 00:34:38,379
>> SPEAKER: Alex er nu sorteret.

762
00:34:38,379 --> 00:34:40,750
Venstre halvdel, højre halvdel,
hvad er det sidste skridt?

763
00:34:40,750 --> 00:34:41,250
Flet.

764
00:34:41,250 --> 00:34:44,310
Temmelig triviel, så jeg er
kommer til at fusionere i seks,

765
00:34:44,310 --> 00:34:46,930
tage et skridt tilbage,
otte, tage et skridt tilbage.

766
00:34:46,930 --> 00:34:49,530
Og nu bemærke dette er
en nyttig takeaway, hvad

767
00:34:49,530 --> 00:34:53,930
nu er sandt om den venstre halvdel af
liste, uanset hvordan vi begyndte?

768
00:34:53,930 --> 00:34:55,090
Det er sorteret.

769
00:34:55,090 --> 00:34:57,750
>> Nu er det ikke sorteret i
det store arrangement med ting,

770
00:34:57,750 --> 00:35:00,250
men det er sorteret uafhængigt
på den anden halvdel.

771
00:35:00,250 --> 00:35:04,100
Nu, hvad skridt er jeg på, hvis jeg holder
tilbagespoling, hvordan historien begyndte?

772
00:35:04,100 --> 00:35:05,680
Nu er jeg nødt til at sortere den højre halvdel.

773
00:35:05,680 --> 00:35:07,630
Så nu er vi tilbage ved
I begyndelsen af ​​historien,

774
00:35:07,630 --> 00:35:08,921
og lad os gøre det hurtigere.

775
00:35:08,921 --> 00:35:11,320
Så jeg har tænkt mig at sortere
højre halvdel af hele listen.

776
00:35:11,320 --> 00:35:13,060
Hvad er næste skridt?

777
00:35:13,060 --> 00:35:15,840
Sorter venstre halvdel af den højre halvdel.

778
00:35:15,840 --> 00:35:18,715
Sorter venstre halvdel af
venstre halvdel af den højre halvdel.

779
00:35:18,715 --> 00:35:19,590
Og hvad er dit navn?

780
00:35:19,590 --> 00:35:20,230
>> Publikum: Omar.

781
00:35:20,230 --> 00:35:21,970
>> SPEAKER: Omar, gå frem, gjort.

782
00:35:21,970 --> 00:35:22,860
Venstre halvdel er sorteret.

783
00:35:22,860 --> 00:35:23,330
Og hvad er dit navn?

784
00:35:23,330 --> 00:35:23,820
>> Publikum: Chris.

785
00:35:23,820 --> 00:35:25,620
>> SPEAKER: Chris, tage et skridt
fremad, er du nu sorteres.

786
00:35:25,620 --> 00:35:27,010
Hvad er det afgørende skridt nu?

787
00:35:27,010 --> 00:35:27,510
Flet.

788
00:35:27,510 --> 00:35:30,509
Så man kommer til at fusionere på plads
her, hvis du kunne tage et skridt tilbage,

789
00:35:30,509 --> 00:35:32,930
og tre vil
tage et skridt tilbage, flette.

790
00:35:32,930 --> 00:35:38,080
Så den venstre halvdel af
højre halvdel er nu sorteret.

791
00:35:38,080 --> 00:35:41,747
Helt ærligt, denne algoritme føles som vi
spilder måde mere tid end før,

792
00:35:41,747 --> 00:35:44,830
men hvis vi gjorde dette i realtid, vil vi
se, hvad grillbarer kommer til at være.

793
00:35:44,830 --> 00:35:47,970
Nu her er jeg, lige
halvdel af den højre halvdel,

794
00:35:47,970 --> 00:35:50,170
lad mig gå videre og sortere den venstre halvdel.

795
00:35:50,170 --> 00:35:51,482
Træd frem, hvad er dit navn?

796
00:35:51,482 --> 00:35:52,190
Publikum: Ramsey.

797
00:35:52,190 --> 00:35:53,210
SPEAKER: Ramsey er nu sorteret.

798
00:35:53,210 --> 00:35:53,570
Hvad er dit navn?

799
00:35:53,570 --> 00:35:54,200
>> Publikum: Marina.

800
00:35:54,200 --> 00:35:57,033
>> SPEAKER: Marina er nu sorteres som
godt, hvis du tager et skridt fremad.

801
00:35:57,033 --> 00:36:00,690
Key skridt her er nu fusionere, er jeg
kommer til at plukke fra mine to lister,

802
00:36:00,690 --> 00:36:01,720
venstre og højre.

803
00:36:01,720 --> 00:36:05,150
Fem vil komme først,
og syv vil komme næste.

804
00:36:05,150 --> 00:36:06,410
Og igen, det er bevidst.

805
00:36:06,410 --> 00:36:08,535
Det faktum, at de tager
skridt frem og tilbage

806
00:36:08,535 --> 00:36:12,997
menes at repræsentere, at vi ikke kan
gøre denne algoritme på plads så let

807
00:36:12,997 --> 00:36:15,830
som boble sortere, og udvælgelse sortere,
og indsættelse slags, hvor vi bare

808
00:36:15,830 --> 00:36:16,960
holdt swapping mennesker.

809
00:36:16,960 --> 00:36:19,940
Jeg bogstaveligt talt har brug for en slags
af bunden papir, hvor

810
00:36:19,940 --> 00:36:21,827
at sætte disse folk
mens jeg gør det sammenlægning

811
00:36:21,827 --> 00:36:23,410
og så kan jeg sætte dem på plads igen.

812
00:36:23,410 --> 00:36:27,260
Og det er afgørende, fordi jeg bruger en
ny ressource, rum, ikke blot tid.

813
00:36:27,260 --> 00:36:28,270
>> OK, det er forbløffende.

814
00:36:28,270 --> 00:36:32,050
Venstre halvdel er sorteret, højre halvdel er
sorteret, nu hvor nøglen fusionerende trin.

815
00:36:32,050 --> 00:36:33,450
Hvordan skal jeg nu til at flette dette?

816
00:36:33,450 --> 00:36:35,470
Så hvis du vil følge mit
venstre hånd og højre hånd,

817
00:36:35,470 --> 00:36:38,930
Jeg har tænkt mig at pege min venstre hånd
på den venstre halvdel, min højre hånd

818
00:36:38,930 --> 00:36:42,680
på den højre halvdel, og nu har jeg til
beslutte skridt for skridt, hvem de skal fusionere i.

819
00:36:42,680 --> 00:36:44,650
Der naturligvis kommer først?

820
00:36:44,650 --> 00:36:45,150
Nummer et.

821
00:36:45,150 --> 00:36:47,327
Så kom her over,
her er vores notesblok.

822
00:36:47,327 --> 00:36:49,910
Så nu nummer et, og varsel
hvad jeg vil gøre med min højre hånd,

823
00:36:49,910 --> 00:36:54,152
Jeg har tænkt mig at flytte min højre hånd en
trin over til punkt nummer tre,

824
00:36:54,152 --> 00:36:55,860
og nu er jeg nødt til at gøre
samme afgørelse.

825
00:36:55,860 --> 00:36:58,387
Og faktisk står til højre i
foran Lukas her, hvis du kunne,

826
00:36:58,387 --> 00:36:59,720
fordi det er vores notesblok.

827
00:36:59,720 --> 00:37:00,610
Så hvem bliver det næste?

828
00:37:00,610 --> 00:37:05,000
Vi har Luke med nummer to
eller Chris med nummer tre.

829
00:37:05,000 --> 00:37:07,460
Naturligvis Luke, nummer
to, så du kommer her.

830
00:37:07,460 --> 00:37:11,270
>> Men min venstre hånd nu kommer til at
øges til at pege på Darren,

831
00:37:11,270 --> 00:37:15,160
og her er nøglen tage væk med
sammenlægning, vil jeg fortsætte med at gøre dette,

832
00:37:15,160 --> 00:37:17,340
selvfølgelig, hvis du slags
af følge logikken.

833
00:37:17,340 --> 00:37:19,670
Men mine hænder er aldrig
kommer til at gå baglæns,

834
00:37:19,670 --> 00:37:23,861
hvilket betyder, at jeg kun nogensinde flytter til
venstre med min sammenlægning proces,

835
00:37:23,861 --> 00:37:26,360
og det kommer til at være nøglen til
vores analyse på bare et øjeblik.

836
00:37:26,360 --> 00:37:27,859
>> Så lad os nu afslutte dette op hurtigt.

837
00:37:27,859 --> 00:37:31,650
Så tre kommer næste,
derefter kommer fire næste,

838
00:37:31,650 --> 00:37:38,750
og nu fem kommer næste, så seks,
og syv, og derefter endelig otte.

839
00:37:38,750 --> 00:37:42,960
Føles som den langsomste algoritme
endnu, men ikke hvis vi faktisk

840
00:37:42,960 --> 00:37:45,510
køre det på samme slags
af clock hastighed, så at

841
00:37:45,510 --> 00:37:48,106
tale, med samme
tikkende ur som før.

842
00:37:48,106 --> 00:37:48,605
Hvorfor?

843
00:37:48,605 --> 00:37:51,100
Nå, lad os tage et
se på slutresultatet.

844
00:37:51,100 --> 00:37:56,990
>> Lad os gå tilbage herovre, lad mig
trække op en demonstration visuelt

845
00:37:56,990 --> 00:37:59,030
af, hvad vi lige gjorde.

846
00:37:59,030 --> 00:38:06,110
Zoomer ind her, på dette
side her, fortæller Firefox

847
00:38:06,110 --> 00:38:08,200
at vi ønsker at stå i kø
op i denne rubrik, lad os

848
00:38:08,200 --> 00:38:11,260
sige boble slags, med hvilke
vi er nu godt bekendt,

849
00:38:11,260 --> 00:38:14,130
udvælgelse slags, som er en anden
forholdsvis ligetil,

850
00:38:14,130 --> 00:38:18,250
og nu dagens fusionere slags, som
vil være vores klimaks slutning.

851
00:38:18,250 --> 00:38:21,530
Grunden til at det tog så meget længere
her med mennesker og mig verbalt er,

852
00:38:21,530 --> 00:38:23,480
selvfølgelig, jeg forklare hvert skridt.

853
00:38:23,480 --> 00:38:26,920
Men hvis du blot udføre dette, meget
ligesom vi gjorde boble sortere og udvælgelse

854
00:38:26,920 --> 00:38:30,890
sortere ikke kun visuelt, ur
hvor meget mere effektivt

855
00:38:30,890 --> 00:38:33,330
denne gearing af
division og erobre

856
00:38:33,330 --> 00:38:39,150
kan, når den anvendes på et datasæt, der er
ikke engang størrelse otte, men selv meget,

857
00:38:39,150 --> 00:38:39,970
meget større.

858
00:38:39,970 --> 00:38:44,585
Jeg giver dig flette sortere, ved siden af
side med disse andre algoritmer.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Dette kommer til at få smertefulde
hurtigt, og slutter

861
00:38:58,530 --> 00:39:00,890
er ikke særlig klimatiske,
de bare ender sorteres.

862
00:39:00,890 --> 00:39:05,280
Men nøglen tage væk, er, at
se hvor meget hurtigere fusionere slags

863
00:39:05,280 --> 00:39:08,110
var, medmindre du tror, ​​jeg er
bare lidt for at rode med dig.

864
00:39:08,110 --> 00:39:13,100
Hvis vi gør det en sidste gang,
lad os genindlæse dette, lad os gå tilbage

865
00:39:13,100 --> 00:39:14,960
og vælg boble sortere,
og bare for sjov,

866
00:39:14,960 --> 00:39:17,330
Lad os vælge indsættelse
sortere, bare for god foranstaltning.

867
00:39:17,330 --> 00:39:20,020
Og denne gang igen, lad os
vælg Merge sortere og lad os

868
00:39:20,020 --> 00:39:21,595
faktisk køre disse side om side.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> Og det er ikke i virkeligheden et lykketræf.

871
00:39:26,930 --> 00:39:31,140
Hvad jeg har faktisk gjort, er jeg har
delte mit input i halve, igen,

872
00:39:31,140 --> 00:39:32,240
og igen og igen.

873
00:39:32,240 --> 00:39:35,590
Og der er kun så mange gange du kan
opdele dit input i to halvdele, venstre

874
00:39:35,590 --> 00:39:36,240
og højre.

875
00:39:36,240 --> 00:39:39,425
Hvad er den formel, vi bliver ved med at
der beskriver opdelingen i halve

876
00:39:39,425 --> 00:39:41,050
igen og igen, og igen og igen?

877
00:39:41,050 --> 00:39:41,890
>> PUBLIKUM: Log n.

878
00:39:41,890 --> 00:39:42,760
>> SPEAKER: log n.

879
00:39:42,760 --> 00:39:46,300
Men så er der en anden afgørende skridt,
denne algoritme er ikke log n trin.

880
00:39:46,300 --> 00:39:48,992
Hvis det kun var log n trin,
vi ville være i det samme problem

881
00:39:48,992 --> 00:39:51,200
som før, hvor vi ikke kan være
at alt er ordnet.

882
00:39:51,200 --> 00:39:54,480
Du er nødt til minimalt at se på n elementer
at være sikker på n elementer er sorteret,

883
00:39:54,480 --> 00:39:55,950
ellers er det et spring af tro.

884
00:39:55,950 --> 00:39:59,810
>> Så det er minimalt log n trin, men
hvad med denne nøgle sammenlægning trin

885
00:39:59,810 --> 00:40:04,370
hvor jeg fusionerede min venstre halvdel og højre
halvdelen og gik på tværs af scenen?

886
00:40:04,370 --> 00:40:06,980
Hvor mange skridt er, at samle?

887
00:40:06,980 --> 00:40:10,150
Det er n, men jeg gjorde ikke bare
fusionere sidste gang.

888
00:40:10,150 --> 00:40:15,089
På hver af disse indlejrede opkald på hver
af disse indlejrede fusionerer, jeg stadig sorteres.

889
00:40:15,089 --> 00:40:18,380
Jeg slået disse to fyre, så disse to
gutter, så disse to fyre og så videre.

890
00:40:18,380 --> 00:40:19,955
>> Så jeg gjorde fusionere igen og igen.

891
00:40:19,955 --> 00:40:20,580
Hvor mange gange?

892
00:40:20,580 --> 00:40:23,510
Så hver gang jeg delte
liste i halve, jeg gjorde en sammenfletning.

893
00:40:23,510 --> 00:40:25,460
Opdel listen i halve, gøre en sammenfletning.

894
00:40:25,460 --> 00:40:28,570
Så hvis dividere liste
kan gøres log n gange,

895
00:40:28,570 --> 00:40:33,880
og sammenlægning i sidste ende tager n
trin, hvad der nu er den øverste

896
00:40:33,880 --> 00:40:37,000
bundet på driften
tidspunktet for vores algoritme?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> Og ja, det er hvad
vi har opnået her.

899
00:40:40,560 --> 00:40:44,650
Så de føler, at du ser visuelt når
de tre ting køre side om side

900
00:40:44,650 --> 00:40:47,930
er n kvadreret mod n
kvadreret mod n log n.

901
00:40:47,930 --> 00:40:51,010
Der grundlæggende vil vi se,
ikke kun i dag, men i fremtiden,

902
00:40:51,010 --> 00:40:52,760
er meget, meget hurtigere.

903
00:40:52,760 --> 00:40:56,010
En runde af bifald for disse fyre,
Jeg vil belønne dem med stress bolde.

904
00:40:56,010 --> 00:41:00,260
Lad os udsætte her i dag, og
vi vil se dig på mandag.

905
00:41:00,260 --> 00:41:02,255