1
00:00:00,000 --> 00:00:11,100
>> [Musik Spela]

2
00:00:11,100 --> 00:00:11,490
>> DAVID J. MALAN: Okej.

3
00:00:11,490 --> 00:00:12,170
Så välkommen tillbaka.

4
00:00:12,170 --> 00:00:15,180
Detta är CS50, och är
I slutet av vecka tre.

5
00:00:15,180 --> 00:00:17,770
>> Så minns under de senaste veckorna,
Vi har spenderat en hel del

6
00:00:17,770 --> 00:00:20,820
tid på C, på programmering, på syntax.

7
00:00:20,820 --> 00:00:24,680
Och det är helt normalt, om du fortfarande
kämpar med Problem Set 2, för att vara

8
00:00:24,680 --> 00:00:25,950
banka huvudet mot väggen.

9
00:00:25,950 --> 00:00:28,310
Det är kryptiskt utseende felmeddelanden
och buggar som du

10
00:00:28,310 --> 00:00:29,220
kan inte riktigt jaga.

11
00:00:29,220 --> 00:00:32,310
Därför, vara säker, att på bara en
några veckor kommer du att se tillbaka på

12
00:00:32,310 --> 00:00:35,930
saker som Caesar, och [? V-Genair,?]
kanske Crack, och

13
00:00:35,930 --> 00:00:40,050
inse hur långt du har kommit
under en kort tidsperiod.

14
00:00:40,050 --> 00:00:43,670
Så om det är någon tröst,
hänga där för nu.

15
00:00:43,670 --> 00:00:46,610
>> Men i dag börjar vi att övergången
till saker högre nivå.

16
00:00:46,610 --> 00:00:49,820
Och vi börjar ta för givet att
ni vet hur man programmerar, eller vid

17
00:00:49,820 --> 00:00:52,090
minst en begynnande
att komfort nivå.

18
00:00:52,090 --> 00:00:56,520
Och vi kommer att börja fundera över hur vi kan
gå om att utforma programmen mer

19
00:00:56,520 --> 00:00:57,440
effektivt.

20
00:00:57,440 --> 00:01:01,090
Hur vi kan gå om att optimera
effektivisera våra algoritmer, och

21
00:01:01,090 --> 00:01:03,110
generellt lösa mer
intressanta problem.

22
00:01:03,110 --> 00:01:06,850
Och börjar ta för givet att,
om vi ville, vi kunde koda upp någon

23
00:01:06,850 --> 00:01:08,350
av de exempel vi har i åtanke.

24
00:01:08,350 --> 00:01:11,430
Så idag, rör vi inte tangentbordet
för någon form av kod.

25
00:01:11,430 --> 00:01:15,150
Det kommer att bli mycket högre nivå, och
slutligen, om problemlösning.

26
00:01:15,150 --> 00:01:20,490
>> Så för att komma till den punkten, låt mig föreslå
att följande sju

27
00:01:20,490 --> 00:01:24,290
rektanglarna representerar sju dörrar, bakom
vilket är en hel massa

28
00:01:24,290 --> 00:01:26,340
siffror, bland vilka är antalet 50.

29
00:01:26,340 --> 00:01:30,470
Låt mig projicera detta på detta
Skärmen här också.

30
00:01:30,470 --> 00:01:36,770
Och föreslå att vi behöver en frivillig till
hjälpa till att hitta mig ett nummer framför

31
00:01:36,770 --> 00:01:38,140
Internet här för att se.

32
00:01:38,140 --> 00:01:40,755
Kom upp, i rosa.

33
00:01:40,755 --> 00:01:43,050
Okej.

34
00:01:43,050 --> 00:01:43,930
Vad är ditt namn?

35
00:01:43,930 --> 00:01:44,850
>> JENNIFER: [OHÖRBAR]

36
00:01:44,850 --> 00:01:45,170
>> DAVID J. MALAN: Förlåt?

37
00:01:45,170 --> 00:01:45,860
>> JENNIFER: Jennifer.

38
00:01:45,860 --> 00:01:46,390
>> DAVID J. MALAN: Jennifer.

39
00:01:46,390 --> 00:01:46,980
Okej, Jennifer.

40
00:01:46,980 --> 00:01:47,630
Trevligt att träffas.

41
00:01:47,630 --> 00:01:48,370
Kom upp.

42
00:01:48,370 --> 00:01:52,430
Så dessa är här sju dörrar, och vad
Jag vill att du ska göra för oss här,

43
00:01:52,430 --> 00:01:56,560
framför allt av dina klasskamrater,
är att hitta oss numret, 50.

44
00:01:56,560 --> 00:02:00,860
För att hitta ett nummer, kan du kika in bakom
någon av dessa dörrar genom att helt enkelt knacka

45
00:02:00,860 --> 00:02:03,030
på en av dörrarna, och det
kommer att avslöja dess nummer.

46
00:02:03,030 --> 00:02:06,080
Och låt oss se hur snabbt du
hittar oss numret, 50.

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15.

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16.

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50.

53
00:02:16,530 --> 00:02:17,350
Snyggt gjort.

54
00:02:17,350 --> 00:02:18,040
Okej.

55
00:02:18,040 --> 00:02:19,906
Applåd för Jennifer.

56
00:02:19,906 --> 00:02:21,530
>> [Applåder]

57
00:02:21,530 --> 00:02:22,320
>> Okej.

58
00:02:22,320 --> 00:02:25,254
Så vad var din strategi för
hitta numret, 50?

59
00:02:25,254 --> 00:02:27,222
>> JENNIFER: Um, tänkte jag kanske om -

60
00:02:27,222 --> 00:02:27,714
[OHÖRBAR]

61
00:02:27,714 --> 00:02:28,206
>> DAVID J. MALAN: Åh.

62
00:02:28,206 --> 00:02:29,630
Ge det en sekund.

63
00:02:29,630 --> 00:02:32,420
Så var din strategi för
hitta numret, 50?

64
00:02:32,420 --> 00:02:34,760
>> JENNIFER: Så jag bara börja på
börjar se vad det första numret

65
00:02:34,760 --> 00:02:38,590
var, och då tänkte jag, kanske om
de är sorterade, ska jag bara hålla

66
00:02:38,590 --> 00:02:39,970
knacka högre upp?

67
00:02:39,970 --> 00:02:40,140
>> David J. MALAN: OK.

68
00:02:40,140 --> 00:02:42,910
Och vi verkar ha hittat
att vara fallet.

69
00:02:42,910 --> 00:02:45,670
Även om, låt oss dra tillbaka skikten
bara lite, och du vill gå

70
00:02:45,670 --> 00:02:47,640
framåt och avslöja de andra dörrarna
du kunde ha valt?

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> JENNIFER: Åh, kära.

73
00:02:51,712 --> 00:02:53,128
>> DAVID J. MALAN: Ah.

74
00:02:53,128 --> 00:02:54,280
>> JENNIFER: Så jag hade tur.

75
00:02:54,280 --> 00:02:55,270
>> DAVID J. MALAN: Så du hade tur.

76
00:02:55,270 --> 00:02:55,710
Okej.

77
00:02:55,710 --> 00:02:56,795
Så inte illa.

78
00:02:56,795 --> 00:02:58,750
Men det är en intressant
insikt, rätt?

79
00:02:58,750 --> 00:03:01,870
Om du antar, och du fick,
faktiskt, lite tur där.

80
00:03:01,870 --> 00:03:05,350
Men om du antar att siffrorna var
sorteras, kan du vara mer exakt

81
00:03:05,350 --> 00:03:08,750
om hur det påverkade
ditt beteende?

82
00:03:08,750 --> 00:03:11,715
>> JENNIFER: Så om de sorteras, jag
tänkte minsta till största.

83
00:03:11,715 --> 00:03:11,970
>> David J. MALAN: OK.

84
00:03:11,970 --> 00:03:15,260
>> JENNIFER: Eller om det slutade
riktigt stora, då största till den minsta.

85
00:03:15,260 --> 00:03:15,540
>> David J. MALAN: OK.

86
00:03:15,540 --> 00:03:18,170
Så största till den minsta, eller
minsta till största.

87
00:03:18,170 --> 00:03:21,990
Men låt mig föreslå, antar att du hade
fått otur, och antar att de

88
00:03:21,990 --> 00:03:26,840
var inte, i själva verket, sorteras, hur många av
dessa dörrar kanske du har haft att kika

89
00:03:26,840 --> 00:03:28,590
bakom i det värsta fallet?

90
00:03:28,590 --> 00:03:29,860
>> JENNIFER: Alla av dem.

91
00:03:29,860 --> 00:03:30,420
>> DAVID J. MALAN: Alla av dem.

92
00:03:30,420 --> 00:03:31,740
Så låt oss generalisera det som n.

93
00:03:31,740 --> 00:03:34,790
Det råkar vara 7, men låt oss mer
generellt säga att det finns n dörrar på

94
00:03:34,790 --> 00:03:35,650
skärmen här.

95
00:03:35,650 --> 00:03:40,110
Så i värsta fall, skulle du ha
att titta bakom 7 dörrar eller n dörrar.

96
00:03:40,110 --> 00:03:44,140
Och så det här är egentligen, det är lite av
lycka idag, men det är verkligen en linjär

97
00:03:44,140 --> 00:03:46,440
algoritm av slag, även om du
var typ av hoppa runt.

98
00:03:46,440 --> 00:03:47,080
Är det rättvist?

99
00:03:47,080 --> 00:03:47,500
>> JENNIFER: Yeah.

100
00:03:47,500 --> 00:03:50,000
>> DAVID J. MALAN: Nåväl, låt mig se om din
strategisk förändring om jag flyttar oss till

101
00:03:50,000 --> 00:03:52,190
vår andra exempel här med
7 olika dörrar.

102
00:03:52,190 --> 00:03:55,240
Samma nummer, men detta
tid de är sorterade.

103
00:03:55,240 --> 00:03:58,350
Vad är din strategi här kommer att bli,
försöker sätta ur ditt sinne vad

104
00:03:58,350 --> 00:03:59,310
de andra siffrorna var -

105
00:03:59,310 --> 00:03:59,930
>> JENNIFER: OK.

106
00:03:59,930 --> 00:04:02,290
>> DAVID J. MALAN: - tidigare?

107
00:04:02,290 --> 00:04:03,180
>> JENNIFER: Låt oss börja
med den första.

108
00:04:03,180 --> 00:04:03,540
>> DAVID J. MALAN: Okej.

109
00:04:03,540 --> 00:04:05,190
Börja med den första.

110
00:04:05,190 --> 00:04:05,960
4.

111
00:04:05,960 --> 00:04:08,810
Nu var du ska gå, och varför?

112
00:04:08,810 --> 00:04:10,040
>> JENNIFER: 4 är verkligen liten.

113
00:04:10,040 --> 00:04:12,500
Så om de är sort kanske minsta
till störst, bör det

114
00:04:12,500 --> 00:04:13,290
vara dubbelt så, och -.

115
00:04:13,290 --> 00:04:13,670
>> David J. MALAN: OK.

116
00:04:13,670 --> 00:04:15,990
Låt oss se, som du tror?

117
00:04:15,990 --> 00:04:19,050
>> JENNIFER: Pröva den sista.

118
00:04:19,050 --> 00:04:19,500
Trevligt.

119
00:04:19,500 --> 00:04:20,880
>> DAVID J. MALAN: Mycket snyggt gjort.

120
00:04:20,880 --> 00:04:21,860
Okej.

121
00:04:21,860 --> 00:04:23,010
>> [Applåder]

122
00:04:23,010 --> 00:04:24,310
>> David J. MALAN: OK.

123
00:04:24,310 --> 00:04:26,790
Så du faktiskt gör detta
fruktansvärt, eftersom du är

124
00:04:26,790 --> 00:04:27,700
gör det mycket bra.

125
00:04:27,700 --> 00:04:31,150
Vilket lämnar oss inte
göra vissa punkter.

126
00:04:31,150 --> 00:04:32,565
Så låt oss försöka rulla tillbaka hit.

127
00:04:32,565 --> 00:04:34,560
>> JENNIFER: OK.

128
00:04:34,560 --> 00:04:35,980
>> DAVID J. MALAN: Mycket bra
gjort ändå.

129
00:04:35,980 --> 00:04:39,060
Så du började i början,
du såg att det var 4, då du

130
00:04:39,060 --> 00:04:40,240
flyttas till slutet.

131
00:04:40,240 --> 00:04:42,320
Men antar att du inte tur
det, och antar att 50

132
00:04:42,320 --> 00:04:42,890
var någon annanstans.

133
00:04:42,890 --> 00:04:46,190
Vad din tredje steget har varit?

134
00:04:46,190 --> 00:04:47,680
>> JENNIFER: Gå tillbaka till början.

135
00:04:47,680 --> 00:04:48,320
>> DAVID J. MALAN: Gå tillbaka
till början.

136
00:04:48,320 --> 00:04:51,320
OK, så du skulle har rört
denna dörr, som var 8.

137
00:04:51,320 --> 00:04:51,660
Okej.

138
00:04:51,660 --> 00:04:52,650
Så det är inte 50.

139
00:04:52,650 --> 00:04:55,380
Var skulle du ha sett nästa?

140
00:04:55,380 --> 00:04:56,720
>> JENNIFER: Om jag inte
vet de sorteras.

141
00:04:56,720 --> 00:04:57,005
>> DAVID J. MALAN: Rätt.

142
00:04:57,005 --> 00:04:58,490
Tja, om du visste
de sorteras -

143
00:04:58,490 --> 00:04:58,700
>> JENNIFER: Åh, visste, ja.

144
00:04:58,700 --> 00:05:00,910
>> DAVID J. MALAN: - men du gjorde inte
vet var 50 var ännu?

145
00:05:00,910 --> 00:05:01,785
>> JENNIFER: Fortsätt bara.

146
00:05:01,785 --> 00:05:02,130
>> DAVID J. MALAN: Okej.

147
00:05:02,130 --> 00:05:02,520
OK.

148
00:05:02,520 --> 00:05:03,800
Keep going.

149
00:05:03,800 --> 00:05:05,270
OK, som jag kan jobba med.

150
00:05:05,270 --> 00:05:05,610
>> JENNIFER: OK.

151
00:05:05,610 --> 00:05:07,210
>> DAVID J. MALAN: Nu, om du bara
kommer att fortsätta, vad är din

152
00:05:07,210 --> 00:05:09,680
algoritm som överflyttas backat in.

153
00:05:09,680 --> 00:05:10,740
>> JENNIFER: Den linjära -.

154
00:05:10,740 --> 00:05:11,820
>> DAVID J. MALAN: Det är typ av linjärt.

155
00:05:11,820 --> 00:05:13,480
Men låt mig föreslå, låt
mig sätta på plats.

156
00:05:13,480 --> 00:05:14,900
Låt mig uppdatera sidan.

157
00:05:14,900 --> 00:05:17,120
samma nummer, samma arrangemang,
Samma dörrar.

158
00:05:17,120 --> 00:05:21,350
Men tänker tillbaka på den första dagen i
klassen när vi rev en telefonbok i

159
00:05:21,350 --> 00:05:25,480
hälften, typ av, och vad som var
vår strategi där?

160
00:05:25,480 --> 00:05:26,450
>> JENNIFER: Börja på mitten.

161
00:05:26,450 --> 00:05:26,690
>> David J. MALAN: OK.

162
00:05:26,690 --> 00:05:27,610
Så börja i mitten.

163
00:05:27,610 --> 00:05:28,790
Så låt oss gå vidare och simulera det.

164
00:05:28,790 --> 00:05:30,720
Börja i mitten av
avslöjar att dörren.

165
00:05:30,720 --> 00:05:31,660
Så antalet 16.

166
00:05:31,660 --> 00:05:35,290
Så vad skulle den starka killen har gjort,
som rev telefonboken i hälften,

167
00:05:35,290 --> 00:05:38,450
för att komma till nästa gissning?

168
00:05:38,450 --> 00:05:39,400
>> JENNIFER: Gå in här halvåret.

169
00:05:39,400 --> 00:05:41,700
>> DAVID J. MALAN: Och varför till höger?

170
00:05:41,700 --> 00:05:43,900
>> JENNIFER: Om de var slags minsta
till största, så 50 bör vara

171
00:05:43,900 --> 00:05:44,720
vid denna ände.

172
00:05:44,720 --> 00:05:44,920
>> DAVID J. MALAN: Bra.

173
00:05:44,920 --> 00:05:45,390
Helt rimliga.

174
00:05:45,390 --> 00:05:48,380
Så som en telefonbok, går du till
rätt i motsats till vänster, men här

175
00:05:48,380 --> 00:05:49,500
är nyckeln take-away.

176
00:05:49,500 --> 00:05:53,930
Du kan nu kasta bort, eller riva av,
hälften av detta problem, så att du inte

177
00:05:53,930 --> 00:05:55,970
med 7 dörrar, men egentligen med bara 3.

178
00:05:55,970 --> 00:05:57,870
Vilket är ungefär hälften av
problemets storlek.

179
00:05:57,870 --> 00:05:58,350
Okej.

180
00:05:58,350 --> 00:06:01,890
Så nu vad du skulle ha
göras efter att du går rätt?

181
00:06:01,890 --> 00:06:05,870
>> JENNIFER: Så 16 är fortfarande ganska liten,
förhållande till 50, så kanske jag ska försöka,

182
00:06:05,870 --> 00:06:06,700
liknande, här.

183
00:06:06,700 --> 00:06:07,890
>> DAVID J. MALAN: Okej.

184
00:06:07,890 --> 00:06:08,720
42.

185
00:06:08,720 --> 00:06:10,830
Okej, så nu vad är din
instinkt säger dig?

186
00:06:10,830 --> 00:06:12,100
>> JENNIFER: Jag kan kasta bort
detta och sedan bara -

187
00:06:12,100 --> 00:06:12,360
>> David J. MALAN: OK.

188
00:06:12,360 --> 00:06:14,212
Bra, kan du kasta bort
den vänstra halvan där.

189
00:06:14,212 --> 00:06:14,890
>> JENNIFER: - Välj här.

190
00:06:14,890 --> 00:06:15,530
>> DAVID J. MALAN: Och höger.

191
00:06:15,530 --> 00:06:15,760
>> JENNIFER: Yeah.

192
00:06:15,760 --> 00:06:17,820
>> DAVID J. MALAN: Så även om det är svårt
att se kanske, när det bara

193
00:06:17,820 --> 00:06:21,320
7 dörrar, tänka, nu,
samstämmigheten i

194
00:06:21,320 --> 00:06:22,620
algoritm kan tillämpas bara.

195
00:06:22,620 --> 00:06:24,510
I det förra fallet, har du
tur, som var stor.

196
00:06:24,510 --> 00:06:26,540
Men du gjorde använder en heuristisk,
Jag skulle vilja säga.

197
00:06:26,540 --> 00:06:29,150
Du använde sorts dina instinkter, och
veta om det sorteras, om det är ganska

198
00:06:29,150 --> 00:06:31,600
litet i början, naturligtvis, har vi
fick gå mer åt höger.

199
00:06:31,600 --> 00:06:34,990
Men i någon mening, fick du tur,
eftersom kanske detta var antalet 100,

200
00:06:34,990 --> 00:06:36,220
och kanske 50 var mer i mitten.

201
00:06:36,220 --> 00:06:37,910
Kanske 50 var även hit.

202
00:06:37,910 --> 00:06:40,960
>> Men vad du gjorde en lite annorlunda
denna gång var, du gjorde samma sak

203
00:06:40,960 --> 00:06:42,150
igen och igen.

204
00:06:42,150 --> 00:06:45,310
Och jag skulle vilja hävda att det du just
gjorde, om än påverkad av telefonen

205
00:06:45,310 --> 00:06:48,100
Boken exempel, är något mycket
mer algoritmisk, och mycket

206
00:06:48,100 --> 00:06:49,930
mindre speciell kapslade.

207
00:06:49,930 --> 00:06:51,620
Mycket mindre instinktiv.

208
00:06:51,620 --> 00:06:57,160
Så i slutet av dagen, hur skulle
du beskriva effektiviteten i

209
00:06:57,160 --> 00:07:00,530
första algoritmen, där du gick
vänster till höger, kontra

210
00:07:00,530 --> 00:07:03,430
andra algoritm här?

211
00:07:03,430 --> 00:07:06,460
>> JENNIFER: detta bör man, liksom, kanske
halvera tiden, eller ännu mer, ja.

212
00:07:06,460 --> 00:07:07,320
>> DAVID J. MALAN: OK, kanske ännu mer.

213
00:07:07,320 --> 00:07:10,150
Låt oss skjuta lite hårdare på det.

214
00:07:10,150 --> 00:07:13,030
Vad som verkligen, om vi fortsätter detta
logik, halverade vi definitivt

215
00:07:13,030 --> 00:07:15,830
gångtid med denna andra algoritmen
genom att kasta bort hälften av

216
00:07:15,830 --> 00:07:18,470
siffror, men vad gjorde vi på nästa
iteration, när Jennifer avslöjade

217
00:07:18,470 --> 00:07:20,615
det andra talet?

218
00:07:20,615 --> 00:07:22,830
>> Vi halverade antalet dörrar igen.

219
00:07:22,830 --> 00:07:25,270
Och vad gjorde vi efter det, om
det fanns fler dörrar att leka med?

220
00:07:25,270 --> 00:07:27,520
Vi skulle halvera dem, och igen,
och igen, och igen.

221
00:07:27,520 --> 00:07:30,420
Och det var precis som ni alla
står upp på den första veckan i

222
00:07:30,420 --> 00:07:33,000
klass, hälften av er som sitter ner, hälften
av er som sitter ner, hälften av er

223
00:07:33,000 --> 00:07:35,440
sitta ner, tills en ensam
själ stod.

224
00:07:35,440 --> 00:07:39,050
Och vi sa att gångtiden
att var antalet steg det tog

225
00:07:39,050 --> 00:07:40,430
på order av vad?

226
00:07:40,430 --> 00:07:41,230
>> Högtalare 1: [OHÖRBAR]

227
00:07:41,230 --> 00:07:43,970
>> DAVID J. MALAN: Så log bas 2 i N,
eller bara helt enkelt, logga n.

228
00:07:43,970 --> 00:07:45,060
Så något logaritmisk.

229
00:07:45,060 --> 00:07:48,380
Och grafen var inte en rak linje
som bara blev värre och värre, det var

230
00:07:48,380 --> 00:07:52,490
denna intressanta kurva som inte gjorde det
får så dåligt över tid.

231
00:07:52,490 --> 00:07:53,910
Så låt oss hålla fast vid denna idé.

232
00:07:53,910 --> 00:07:54,690
Låt oss tacka Jennifer.

233
00:07:54,690 --> 00:07:56,150
Tack så mycket för kommande vidare upp.

234
00:07:56,150 --> 00:07:57,400
Och, en sek.

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
Inga skrivbordslampor dag, men vi
har CS50 stress bollar.

237
00:08:02,925 --> 00:08:03,420
>> JENNIFER: Yay.

238
00:08:03,420 --> 00:08:04,410
>> DAVID J. MALAN: Okej, här.

239
00:08:04,410 --> 00:08:06,545
Tack för att du ådra
stress här uppe.

240
00:08:06,545 --> 00:08:07,350
Okej.

241
00:08:07,350 --> 00:08:10,620
Så låt oss se om vi kan inte nu
formalisera detta lite mer.

242
00:08:10,620 --> 00:08:14,820
Så återigen, var vad vi just gjorde
i princip samma sak som vi gjorde

243
00:08:14,820 --> 00:08:16,660
i den första veckan.

244
00:08:16,660 --> 00:08:23,780
Men snarare än att avsluta med bara en linjär
algoritm, som vi avbildade

245
00:08:23,780 --> 00:08:27,210
tidigare som denna raka linje,
varvid, om vi lägger ytterligare en dörr på

246
00:08:27,210 --> 00:08:29,610
skärmen, då Jennifer skulle
har haft att se, potentiellt,

247
00:08:29,610 --> 00:08:30,600
bakom ett mer dörr.

248
00:08:30,600 --> 00:08:33,490
Om vi ​​lägger två dörrar, kan hon ha
att titta bakom två dörrar.

249
00:08:33,490 --> 00:08:35,990
>> Och så fanns det linjära
förhållandet mellan storleken på den

250
00:08:35,990 --> 00:08:39,059
problem på, säg, x-axeln och
den tid det tar att

251
00:08:39,059 --> 00:08:40,440
lösa på y.

252
00:08:40,440 --> 00:08:43,330
Men bilden jag syftade på
tidigare var detta gröna linjen.

253
00:08:43,330 --> 00:08:45,970
Grön medvetet, eftersom
det kändes bara bättre.

254
00:08:45,970 --> 00:08:49,790
I teorin, algoritmen, när vi gjorde det
med telefonboken, när vi gjorde det

255
00:08:49,790 --> 00:08:52,420
med er räknar varandra, och
i det andra fallet, när Jennifer bara

256
00:08:52,420 --> 00:08:55,250
gjorde upp det här, var det slags
av fundamentalt bättre.

257
00:08:55,250 --> 00:08:57,180
För det var inte bara dubbelt så snabb.

258
00:08:57,180 --> 00:08:58,870
Det var inte ens fyra gånger så snabbt.

259
00:08:58,870 --> 00:09:03,290
Det var helt och hållet beroende av vad
storleken hos den inmatade var, om hur många

260
00:09:03,290 --> 00:09:05,220
åtgärder den tog slut.

261
00:09:05,220 --> 00:09:08,040
>> Och så denna enkla idé som vi alla tog
för givet med telefonboken,

262
00:09:08,040 --> 00:09:10,200
kan på liknande sätt appliceras
att något sånt här.

263
00:09:10,200 --> 00:09:12,380
Och detta kan vara mer nonchalant
kallas, som ni kanske

264
00:09:12,380 --> 00:09:13,940
föreställa, söndra och härska.

265
00:09:13,940 --> 00:09:16,390
Inte olikt vad vi gjorde, naturligtvis,
med telefonboken.

266
00:09:16,390 --> 00:09:18,300
>> Men pseudokoden, minns, var det.

267
00:09:18,300 --> 00:09:21,800
Så vi kommer inte att göra det igen, men minns
den första veckan, stod vi alla upp

268
00:09:21,800 --> 00:09:25,140
och sedan hälften av er satte sig ner, hälften av
du satt, satt hälften av er ner.

269
00:09:25,140 --> 00:09:29,280
Denna algoritm har genomförts i en
lite av en fusk sätt, i det, det

270
00:09:29,280 --> 00:09:32,870
var inte bara en av mig räkna,
fundamentalt, mer effektivt.

271
00:09:32,870 --> 00:09:35,830
I så fall, var jag utnyttja
en sekundär resurs.

272
00:09:35,830 --> 00:09:39,470
Sortera på, flera processorer, flera hjärnor,
flera smarta människor i

273
00:09:39,470 --> 00:09:42,740
Rummet var att hjälpa mig att komma från något
linjär till något

274
00:09:42,740 --> 00:09:45,190
logaritmisk, från något
röd till något grönt.

275
00:09:45,190 --> 00:09:48,650
>> Men i detta fall, Jennifer ensamt kan
grunden förbättra det

276
00:09:48,650 --> 00:09:52,370
fullgöra sitt första algoritmen med,
igen, bara tänka lite hårdare.

277
00:09:52,370 --> 00:09:56,650
Och nu, när det blir dags att genomföra
dessa saker, räkna ut

278
00:09:56,650 --> 00:10:00,670
vilka rader kod kan du skriva en sådan
att du kan upprepa dem igen, och

279
00:10:00,670 --> 00:10:03,350
igen, och igen, typ av
i en looping mode.

280
00:10:03,350 --> 00:10:06,370
Eftersom du inte kommer att ha
lyx, som Jennifer gjorde i början, för att

281
00:10:06,370 --> 00:10:10,460
bara ha en hel hög med ifs och säga,
hmm, om det första numret är 4,

282
00:10:10,460 --> 00:10:11,800
låt mig gå hela vägen till slutet.

283
00:10:11,800 --> 00:10:14,180
Ooh, om detta antal är för stor,
Låt mig gå godtyckligt tillbaka

284
00:10:14,180 --> 00:10:15,220
till det andra elementet.

285
00:10:15,220 --> 00:10:18,210
Du kommer att upptäcka att det kommer att bli en hel del
svårare att formalisera vad vi människor

286
00:10:18,210 --> 00:10:21,270
tar för givet så mycket rimlig
heuristik, men en dator är endast

287
00:10:21,270 --> 00:10:23,260
kommer att göra det du ber den att göra.

288
00:10:23,260 --> 00:10:25,280
>> Nu har mycket intressant
konsekvenser.

289
00:10:25,280 --> 00:10:29,950
Denna graf slags tänkt att sortera på
överväldiga visuellt, men varsel, där

290
00:10:29,950 --> 00:10:32,230
är den raka linjen i detta diagram?

291
00:10:32,230 --> 00:10:35,330
Var är den linjära grafen
som vi kallar n?

292
00:10:35,330 --> 00:10:37,580
Tja, det är typ av mot botten
av denna bild, eller hur?

293
00:10:37,580 --> 00:10:40,500
Så allt vi har gjort är att vi har slags
utzooming till x-axeln och

294
00:10:40,500 --> 00:10:44,780
y-axeln för att försöka få en känsla för vad
andra typer av kurvor ser ut.

295
00:10:44,780 --> 00:10:47,760
>> Och detaljerna i den matematiska
uttryck idag inte kommer att fråga så

296
00:10:47,760 --> 00:10:52,440
mycket, men märker att det finns en hel del
algoritmer som är långt värre än

297
00:10:52,440 --> 00:10:53,470
något som är linjär.

298
00:10:53,470 --> 00:10:55,410
I själva verket ser n kubik ganska dåligt.

299
00:10:55,410 --> 00:10:58,400
2 till n ser ganska illa.
n kvadrat ser ganska illa.

300
00:10:58,400 --> 00:11:01,630
Och vi får se vad några av dem
kan vara i verkligheten idag.

301
00:11:01,630 --> 00:11:05,430
Och log n känns inte så illa, men
bättre än n är log bas 2 n.

302
00:11:05,430 --> 00:11:08,080
Men du vet, det skulle ha varit ännu
mer fantastiskt om Jennifer, eller om vi,

303
00:11:08,080 --> 00:11:12,910
den första veckan, hade kommit med
något som är log för logaritmen för n.

304
00:11:12,910 --> 00:11:15,880
>> Så med andra ord, det är denna helhet
spektrum av möjliga lösningar på

305
00:11:15,880 --> 00:11:18,570
problem, men även här meddelandet
vad som kommer att hända.

306
00:11:18,570 --> 00:11:22,910
När jag zoomar ut, vilket av dessa kurvor
kommer att visa sig vara den absoluta

307
00:11:22,910 --> 00:11:26,630
värsta av dem på skärmen nu?

308
00:11:26,630 --> 00:11:28,680
Så n kubik ser ganska
dåligt för tillfället.

309
00:11:28,680 --> 00:11:32,470
Men om vi zooma ut och se mer av
x och y-axeln, som kommer att

310
00:11:32,470 --> 00:11:34,550
dominera slutändan?

311
00:11:34,550 --> 00:11:37,120
Så visar det sig faktiskt att två till
n, och du kan räkna ut det genom att bara

312
00:11:37,120 --> 00:11:39,990
ansluta vissa allt större
siffror, och du ser att 2 till

313
00:11:39,990 --> 00:11:42,070
n, ja, blir större mycket snabbare.

314
00:11:42,070 --> 00:11:45,530
Om vi ​​zoomar verkligen ut, en 2 till
n algoritm suger absolut.

315
00:11:45,530 --> 00:11:48,170
Jag menar att detta kommer att ta
ganska lite tid för

316
00:11:48,170 --> 00:11:49,460
dator att pressa igenom.

317
00:11:49,460 --> 00:11:52,500
>> Men du kommer att se över tid, särskilt
med framtida problem uppsättningar och även

318
00:11:52,500 --> 00:11:55,600
slutliga projekt, är din data
set blir stor, okej?

319
00:11:55,600 --> 00:11:58,300
Även i den första versionen av Facebook,
som antalet vänner, och

320
00:11:58,300 --> 00:12:01,840
Antalet registrerade användare fick stor,
Du kan sortera på telefon det i och

321
00:12:01,840 --> 00:12:05,530
genomföra något med linjär sökning,
eller en mycket enkel sortering

322
00:12:05,530 --> 00:12:07,030
algoritm, som vi får se i dag.

323
00:12:07,030 --> 00:12:09,280
Du måste börja tänka hårdare
och hårdare om dessa problem.

324
00:12:09,280 --> 00:12:12,070
Och vilka typer av problem platser som
Facebook och Google, och Microsoft,

325
00:12:12,070 --> 00:12:16,350
och andra arbetar på är exakt dessa
typ av stora uppgifter slags frågor

326
00:12:16,350 --> 00:12:18,530
alltmer dessa dagar.

327
00:12:18,530 --> 00:12:18,900
>> Okej.

328
00:12:18,900 --> 00:12:23,800
Så Jennifer framgång i den andra
algoritm, ärligt talat, det gjorde hon otroligt

329
00:12:23,800 --> 00:12:26,110
väl första gången, men låt oss
skriva det som tur så att vi

330
00:12:26,110 --> 00:12:27,000
kan göra denna punkt.

331
00:12:27,000 --> 00:12:30,970
I det andra fallet, belånade hon en
algoritm som upprepas och

332
00:12:30,970 --> 00:12:34,670
igen, men hon tog för givet en
vissa antagandet att vi får

333
00:12:34,670 --> 00:12:39,370
henne, men hon utnyttjade viss detalj
andra gången att hon inte hade

334
00:12:39,370 --> 00:12:39,840
första gången.

335
00:12:39,840 --> 00:12:41,800
Vilket var vad?

336
00:12:41,800 --> 00:12:43,050
>> Att listan sorterades.

337
00:12:43,050 --> 00:12:46,350
Så snart listan sorterades, vi
hävdar att Jennifer kunde göra

338
00:12:46,350 --> 00:12:47,480
fundamentalt bättre.

339
00:12:47,480 --> 00:12:51,450
7 dörrar, ja, är inte så intressant,
men antar att det är vi 7 miljoner dörrar.

340
00:12:51,450 --> 00:12:54,080
Log n kommer definitivt
att utföra mycket, mycket

341
00:12:54,080 --> 00:12:55,610
snabbare i det långa loppet.

342
00:12:55,610 --> 00:12:58,880
Men hon var tvungen att ha
dörrar sorteras för henne.

343
00:12:58,880 --> 00:13:02,320
Nu tog jag mig friheten att göra det
i förväg på datorskärmen

344
00:13:02,320 --> 00:13:05,160
här, men antar att Jennifer
tvungen att göra det själv?

345
00:13:05,160 --> 00:13:10,120
Antag att dörrarna i fråga
representerade data i en databas, eller

346
00:13:10,120 --> 00:13:14,260
vänner registrerats för Facebook, eller
alla webbsidor på internet som

347
00:13:14,260 --> 00:13:16,880
olika webbplatser kan behöva
att indexera eller sök över.

348
00:13:16,880 --> 00:13:20,940
>> Anta att du bara hade en rådata
in och det var kvar till dig, eller till

349
00:13:20,940 --> 00:13:23,010
Jennifer att göra det sortering?

350
00:13:23,010 --> 00:13:26,950
Det, snarare kräver att vi svarar
frågan, ja, hur mycket tid

351
00:13:26,950 --> 00:13:31,080
skulle ha tagit Jennifer, eller ens mig,
att sortera dessa siffror i förväg så

352
00:13:31,080 --> 00:13:32,680
att hon kunde dra nytta av det?

353
00:13:32,680 --> 00:13:32,880
Rätt?

354
00:13:32,880 --> 00:13:36,620
Eftersom underförstått, naturligtvis, är
om det tar mig ett tag att sortera

355
00:13:36,620 --> 00:13:40,800
numren, vem fan bryr sig om att du
kan hitta ett antal som 50 så snabbt,

356
00:13:40,800 --> 00:13:44,850
som i Jennifers fall, om vi mer än
överväldigade av mängden av tid

357
00:13:44,850 --> 00:13:46,920
det tog genom att sortera saker i förväg?

358
00:13:46,920 --> 00:13:49,320
>> Så låt oss se om vi kan inte
måla bilden här.

359
00:13:49,320 --> 00:13:51,370
Jag har en hel massa mer stress
bollar, om det hjälper

360
00:13:51,370 --> 00:13:52,270
bryta isen här.

361
00:13:52,270 --> 00:13:55,690
Och om du inte skulle ha något emot, vi
behöver sju volontär -

362
00:13:55,690 --> 00:13:57,060
på, OK.

363
00:13:57,060 --> 00:13:57,240
Wow.

364
00:13:57,240 --> 00:13:59,250
Så vi behöver inte spendera
på skrivbordslampor, verkar det.

365
00:13:59,250 --> 00:13:59,690
Okej.

366
00:13:59,690 --> 00:14:01,530
Så vad sägs om er två i fronten.

367
00:14:01,530 --> 00:14:04,160
Hur du två killar i ryggen.

368
00:14:04,160 --> 00:14:04,870
Så det är fyra.

369
00:14:04,870 --> 00:14:09,890
Hur om dig framför
fem, sex och sju.

370
00:14:09,890 --> 00:14:10,320
Just där.

371
00:14:10,320 --> 00:14:13,260
Din väns pekar ut dig,
så du får priset.

372
00:14:13,260 --> 00:14:13,700
>> Okej.

373
00:14:13,700 --> 00:14:14,410
Kom upp.

374
00:14:14,410 --> 00:14:17,120
Och varför inte vi har dig
killar Kom hit.

375
00:14:17,120 --> 00:14:18,960
Jag ska ge dig varje ett nummer.

376
00:14:18,960 --> 00:14:22,150
Och gå vidare och ordna er
identiskt med vad som är

377
00:14:22,150 --> 00:14:25,180
avbildas på skärmen.

378
00:14:25,180 --> 00:14:26,530
>> [Inplacering VOICES]

379
00:14:26,530 --> 00:14:28,160
>> DAVID J. MALAN: Oop, sorry.

380
00:14:28,160 --> 00:14:30,210
Bug.

381
00:14:30,210 --> 00:14:32,180
Okej.

382
00:14:32,180 --> 00:14:32,750
Nåväl, nu kör vi.

383
00:14:32,750 --> 00:14:34,180
Nummer fem.

384
00:14:34,180 --> 00:14:35,136
Nummer sex.

385
00:14:35,136 --> 00:14:37,770
Ett, två, tre, fyra,
fem, sex, sju.

386
00:14:37,770 --> 00:14:39,410
Åh, detta är pinsamt.

387
00:14:39,410 --> 00:14:41,210
>> Högtalare 2: Jag ska bara få ett -.

388
00:14:41,210 --> 00:14:41,900
>> DAVID J. MALAN: Bra deal.

389
00:14:41,900 --> 00:14:43,130
Okej.

390
00:14:43,130 --> 00:14:44,611
Tack för din medverkan.

391
00:14:44,611 --> 00:14:47,200
>> [Applåder]

392
00:14:47,200 --> 00:14:48,580
>> OK.

393
00:14:48,580 --> 00:14:48,860
Okej.

394
00:14:48,860 --> 00:14:51,970
Så vi har fyra, två, sex,
en, tre, sju, fem.

395
00:14:51,970 --> 00:14:56,010
Perfekt så vi har sju frivilliga
här som är lika i bredd med

396
00:14:56,010 --> 00:14:57,430
array som vi spelar
med tidigare.

397
00:14:57,430 --> 00:14:59,470
Och jag valde sju av skäl
som kommer att vara precis

398
00:14:59,470 --> 00:15:00,840
bekvämt i en liten bit.

399
00:15:00,840 --> 00:15:04,400
Och jag kommer att föreslå första att
vi sortera dessa sju frivilliga.

400
00:15:04,400 --> 00:15:06,786
Om du vill, först,
att säga hej men.

401
00:15:06,786 --> 00:15:08,970
Eftersom detta kommer att bli en
obekväma flera minuter.

402
00:15:08,970 --> 00:15:10,370
Presentera er själva.

403
00:15:10,370 --> 00:15:10,980
>> GRACE: Hej, jag är Grace.

404
00:15:10,980 --> 00:15:14,190
Jag är en sophomore i Leverett House.

405
00:15:14,190 --> 00:15:14,620
>> Branson: Hej.

406
00:15:14,620 --> 00:15:15,620
Jag Branson.

407
00:15:15,620 --> 00:15:16,920
Jag är en nybörjare i Weld.

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> GABE: Hej.

410
00:15:20,230 --> 00:15:21,040
Jag är Gabe.

411
00:15:21,040 --> 00:15:22,300
Jag är en junior i Cabot.

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> NEIL: Jag är Neil.

414
00:15:25,980 --> 00:15:29,090
Jag är en nybörjare i Matthews.

415
00:15:29,090 --> 00:15:29,550
>> JASON: Jag är Jason.

416
00:15:29,550 --> 00:15:32,816
Jag är en nybörjare i Greenough.

417
00:15:32,816 --> 00:15:33,700
>> MIKE: Jag är Mike.

418
00:15:33,700 --> 00:15:37,360
Jag är en nybörjare i Grays.

419
00:15:37,360 --> 00:15:37,990
>> JESS: Jag är Jess.

420
00:15:37,990 --> 00:15:40,313
Jag är en sophomore i Leverett.

421
00:15:40,313 --> 00:15:41,300
>> DAVID J. MALAN: Excellent.

422
00:15:41,300 --> 00:15:41,850
Okej.

423
00:15:41,850 --> 00:15:44,190
Tja, tack till alla våra
volontärer här hittills.

424
00:15:44,190 --> 00:15:47,110
Och utmaningen till hands nu går
vara att sortera dessa killar, men sedan

425
00:15:47,110 --> 00:15:50,250
vi kommer att behöva tänka lite
hårt om hur effektivt vi faktiskt

426
00:15:50,250 --> 00:15:51,110
sorterade dem.

427
00:15:51,110 --> 00:15:52,580
Så låt oss först försöka detta.

428
00:15:52,580 --> 00:15:55,970
Ni kan se varandras nummer
bara genom att placera runt hörnen.

429
00:15:55,970 --> 00:15:59,380
Gå vidare och ta ett par sekunder, och
Sortera er från minsta på

430
00:15:59,380 --> 00:16:01,240
vänster till största på höger.

431
00:16:01,240 --> 00:16:02,490
Go.

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> OK.

434
00:16:07,530 --> 00:16:08,030
Bra.

435
00:16:08,030 --> 00:16:09,370
Det var verkligen darn snabbt.

436
00:16:09,370 --> 00:16:14,040
Nu någon här, vad var algoritmen
att dessa killar tillämpas?

437
00:16:14,040 --> 00:16:14,900
>> Högtalare 1: Minsta till största.

438
00:16:14,900 --> 00:16:15,000
>> David J. MALAN: OK.

439
00:16:15,000 --> 00:16:18,070
Minst till störst är sortera riktigt av
mål, men jag är inte säker på att det är

440
00:16:18,070 --> 00:16:18,890
verkligen en algoritm.

441
00:16:18,890 --> 00:16:21,810
Minst till störst berättar inte
mig steg för steg hur man gör.

442
00:16:21,810 --> 00:16:22,833
Yeah?

443
00:16:22,833 --> 00:16:24,083
>> Högtalare 1: [OHÖRBAR]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> David J. MALAN: OK.

446
00:16:26,280 --> 00:16:28,920
Så om du ser en person som är mindre än
ditt nummer, sedan flytta till

447
00:16:28,920 --> 00:16:29,680
höger om dem.

448
00:16:29,680 --> 00:16:32,800
Så att nu börjar bli mer uttrycksfulla,
mer som en algoritm, eftersom du

449
00:16:32,800 --> 00:16:35,410
kan säga, om detta, så att.

450
00:16:35,410 --> 00:16:37,050
Så vi har någon form av
villkorlig konstruktion.

451
00:16:37,050 --> 00:16:39,700
Och killarna verkade göra att ett fåtal
gånger, eftersom vissa av er flyttat lite

452
00:16:39,700 --> 00:16:40,420
av en sträcka.

453
00:16:40,420 --> 00:16:43,410
Så det var förmodligen någon form av
looping händer i deras sinnen.

454
00:16:43,410 --> 00:16:44,610
>> Men låt oss försöka formalisera det.

455
00:16:44,610 --> 00:16:47,540
Om ni skulle kunna återställas
till detta arrangemang.

456
00:16:47,540 --> 00:16:50,650
Låt oss se om vi inte kan formalisera detta en
bit, och sedan ställa frågan, precis

457
00:16:50,650 --> 00:16:51,580
Hur effektiv är detta?

458
00:16:51,580 --> 00:16:54,220
Naturligtvis, när vi gör denna långsammare,
det kommer att kännas så bra för

459
00:16:54,220 --> 00:16:57,210
en algoritm, men låt oss se om vi kan
sätta våra fingrar på de exakta stegen.

460
00:16:57,210 --> 00:16:58,670
>> Så ni två killar är fyra och två.

461
00:16:58,670 --> 00:17:01,020
Eller du rätt eller fel beslut?

462
00:17:01,020 --> 00:17:01,900
Självklart felaktig.

463
00:17:01,900 --> 00:17:02,710
Så vi bytte.

464
00:17:02,710 --> 00:17:05,170
Nu ska jag gå åt sidan
här och säga fyra till sex.

465
00:17:05,170 --> 00:17:06,240
Är du rätt eller fel?

466
00:17:06,240 --> 00:17:06,599
>> GABE: Korrekt.

467
00:17:06,599 --> 00:17:07,180
>> DAVID J. MALAN: Rätt.

468
00:17:07,180 --> 00:17:08,300
Sex och en?

469
00:17:08,300 --> 00:17:08,609
Nope.

470
00:17:08,609 --> 00:17:09,630
Swap.

471
00:17:09,630 --> 00:17:10,490
Så det är två swappar.

472
00:17:10,490 --> 00:17:11,710
Sex och tre?

473
00:17:11,710 --> 00:17:11,980
Nope.

474
00:17:11,980 --> 00:17:13,000
Swap.

475
00:17:13,000 --> 00:17:13,930
Sex och sju?

476
00:17:13,930 --> 00:17:14,630
Ser bra ut.

477
00:17:14,630 --> 00:17:15,396
Sju och fem?

478
00:17:15,396 --> 00:17:16,150
>> JESS: [OHÖRBAR]

479
00:17:16,150 --> 00:17:17,089
>> DAVID J. MALAN: OK, byta.

480
00:17:17,089 --> 00:17:19,770
Och sorteras.

481
00:17:19,770 --> 00:17:19,980
Okej.

482
00:17:19,980 --> 00:17:21,440
Så uppenbarligen inte, eller hur?

483
00:17:21,440 --> 00:17:22,470
Så det var mer på gång.

484
00:17:22,470 --> 00:17:24,920
Men i själva verket, killarna, även
bara instinktivt.

485
00:17:24,920 --> 00:17:25,450
hålls rörliga.

486
00:17:25,450 --> 00:17:27,710
De inte bara sluta, när de
korrigerat ett problem.

487
00:17:27,710 --> 00:17:27,839
Så.

488
00:17:27,839 --> 00:17:29,390
Sannerligen, jag kommer att ha
att göra samma sak.

489
00:17:29,390 --> 00:17:32,720
Jag kommer att behöva sortera om spola tillbaka
till början av detta problem,

490
00:17:32,720 --> 00:17:35,630
eller början av denna samling av
människor, låt oss börja ringa dem.

491
00:17:35,630 --> 00:17:38,366
>> Och nu vad ska min algoritm
på det andra passet vara?

492
00:17:38,366 --> 00:17:39,220
>> Högtalare 1: Samma sak.

493
00:17:39,220 --> 00:17:39,940
>> DAVID J. MALAN: Samma sak.

494
00:17:39,940 --> 00:17:41,460
Och detta, jag börjar gilla, eller hur?

495
00:17:41,460 --> 00:17:44,720
Så snart du kan hitta dig själv att göra
samma sak om och om igen, det är

496
00:17:44,720 --> 00:17:47,890
bli mer lika en algoritm,
och mindre mänsklig instinkt.

497
00:17:47,890 --> 00:17:48,680
>> Så nu var det dags igen.

498
00:17:48,680 --> 00:17:49,870
Två och fyra?

499
00:17:49,870 --> 00:17:50,220
Nej.

500
00:17:50,220 --> 00:17:51,050
Fyra och en?

501
00:17:51,050 --> 00:17:53,380
Ah, det fanns faktiskt vissa
arbete återstår att göra.

502
00:17:53,380 --> 00:17:53,620
För och tre?

503
00:17:53,620 --> 00:17:54,572
Bra.

504
00:17:54,572 --> 00:17:56,000
Fyra och sex?

505
00:17:56,000 --> 00:17:58,380
Sex och fem?

506
00:17:58,380 --> 00:17:59,470
Sex och sju?

507
00:17:59,470 --> 00:18:00,970
OK, nu gjort.

508
00:18:00,970 --> 00:18:01,550
OK, ingen.

509
00:18:01,550 --> 00:18:02,710
Jag måste gå tillbaka.

510
00:18:02,710 --> 00:18:05,130
>> Så nu, återigen, vi gör detta
lite mer medvetet.

511
00:18:05,130 --> 00:18:08,700
Och nu finns det bara en hjärna
exekvera denna algoritm.

512
00:18:08,700 --> 00:18:10,290
En processor, om du kommer.

513
00:18:10,290 --> 00:18:13,090
Och ärligt talat, det är den enda resursen
vi kommer att ha tillgång till.

514
00:18:13,090 --> 00:18:16,280
Och när vi går tillbaka till ett tangentbord
och ha något liknande C på vår

515
00:18:16,280 --> 00:18:19,600
omhändertagande, vi skriver bara ett program
som kan göra en sak i taget.

516
00:18:19,600 --> 00:18:22,900
För killarna en stund sedan, vi
belånade sin kollektiva intelligens

517
00:18:22,900 --> 00:18:24,180
som ni gjorde i veckan noll.

518
00:18:24,180 --> 00:18:24,980
Så låt oss fortsätta att göra detta.

519
00:18:24,980 --> 00:18:26,260
>> Två och en.

520
00:18:26,260 --> 00:18:26,945
Två och tre.

521
00:18:26,945 --> 00:18:27,460
Tre och fyra.

522
00:18:27,460 --> 00:18:28,310
Fyra och fem.

523
00:18:28,310 --> 00:18:28,620
Fem och sex.

524
00:18:28,620 --> 00:18:30,510
Sex och sju.

525
00:18:30,510 --> 00:18:31,880
Klar?

526
00:18:31,880 --> 00:18:34,560
Så jag är, men låt mig spela
djävulens advokat.

527
00:18:34,560 --> 00:18:37,950
Gör jag, den typ av dator som bara
gjorde ett pass i denna samling av

528
00:18:37,950 --> 00:18:40,225
människor, vet att jag är klar?

529
00:18:40,225 --> 00:18:40,670
>> Högtalare 1: Nej

530
00:18:40,670 --> 00:18:41,050
>> DAVID J. MALAN: Så varför?

531
00:18:41,050 --> 00:18:46,900
Vad skulle jag behöva göra för att
slutsatsen beslutsamt att jag gjort?

532
00:18:46,900 --> 00:18:48,230
Förmodligen ett mer pass.

533
00:18:48,230 --> 00:18:48,430
Rätt?

534
00:18:48,430 --> 00:18:51,760
Eftersom allt jag vet från att tidigare
pass är att jag korrigerade ett misstag.

535
00:18:51,760 --> 00:18:53,920
Och det innebär, kanske det finns
ännu ett misstag

536
00:18:53,920 --> 00:18:54,840
att jag måste rätta till.

537
00:18:54,840 --> 00:18:58,680
Så jag kan bara vara säker genom att spola tillbaka, och
sedan kontrollera, 01:59, två och

538
00:18:58,680 --> 00:19:00,940
tre, tre och fyra, fyra och fem,
fem och sex, sex och sju.

539
00:19:00,940 --> 00:19:02,510
OK, nu gjorde jag inget arbete.

540
00:19:02,510 --> 00:19:05,990
>> Jag kan säkert ihåg att jag gjorde något
arbeta med något som liknar en variabel,

541
00:19:05,990 --> 00:19:06,975
gillar en int.

542
00:19:06,975 --> 00:19:12,490
Kalla det swappar, och om swappar är 0 när jag
komma hit, och det började vid 0, då

543
00:19:12,490 --> 00:19:15,520
Jag skulle bara vara dumt att hålla igång
fram och tillbaka, kontroll igen, och

544
00:19:15,520 --> 00:19:16,450
igen, och igen, eller hur?

545
00:19:16,450 --> 00:19:18,450
Eftersom du fastnar i något
slags oändlig loop.

546
00:19:18,450 --> 00:19:21,250
Så snart som det finns 0 swappar,
Vi kan hävda att detta

547
00:19:21,250 --> 00:19:23,810
algoritm är verkligen klar.

548
00:19:23,810 --> 00:19:25,400
>> Nu, låt oss sätta ett namn på det.

549
00:19:25,400 --> 00:19:28,930
Den algoritm som jag föreslår att vi bara
genomföras är något som kallas bubbla

550
00:19:28,930 --> 00:19:32,800
sortera, känd som sådan i den meningen att
de nummer som är större typ av

551
00:19:32,800 --> 00:19:37,990
bubbla sig upp till toppen, eller upp
till slutet av uppsättningen av siffror.

552
00:19:37,990 --> 00:19:40,270
Men hur effektiv var denna algoritm?

553
00:19:40,270 --> 00:19:44,600
Hur många steg hade jag fysiskt
Ta till exempel, för att sortera dessa

554
00:19:44,600 --> 00:19:45,850
sju människor?

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> Fyra till fem?

557
00:19:49,550 --> 00:19:51,420
OK, alltför många är ytterst
kommer att vara svaret.

558
00:19:51,420 --> 00:19:54,960
Men även då, det specifika numret
är inte så intressant.

559
00:19:54,960 --> 00:19:56,670
Låt oss generalisera det som n.

560
00:19:56,670 --> 00:20:00,520
Så om jag hade n folk här uppe, och de
var, liksom, i slumpmässig ordning vid

561
00:20:00,520 --> 00:20:02,180
början, i den ursprungliga ordningen.

562
00:20:02,180 --> 00:20:04,910
Nå, hur många steg jag har
att ta på första passet?

563
00:20:04,910 --> 00:20:09,810
Det var en, två, tre, fyra, fem,
sex, och de är sju personer, så

564
00:20:09,810 --> 00:20:13,670
att sju är, sex -, så det är n
minus ett steg första gången.

565
00:20:13,670 --> 00:20:16,280
>> Nu, hur många steg jag har
att ta när jag spolas tillbaka?

566
00:20:16,280 --> 00:20:19,310
Tja, skulle vi fördubbla faktiskt att om
Vi ville verkligen, men för nu, är jag

567
00:20:19,310 --> 00:20:22,300
bara kommer att säga, okej,
en annan n minus 1.

568
00:20:22,300 --> 00:20:25,240
Så n minus 1 kommer att få
irriterande att hålla reda på, så låt oss

569
00:20:25,240 --> 00:20:26,400
bara runda upp något.

570
00:20:26,400 --> 00:20:27,770
Så 2n steg.

571
00:20:27,770 --> 00:20:29,310
Så 14 steg, ge eller ta.

572
00:20:29,310 --> 00:20:31,930
>> Hur många gånger har jag tar
ett steg nästa gång?

573
00:20:31,930 --> 00:20:33,740
Tja, det är 3n.

574
00:20:33,740 --> 00:20:34,510
egentligen.

575
00:20:34,510 --> 00:20:37,920
Och nu, i värsta fall, för
exempel, hur många gånger jag har

576
00:20:37,920 --> 00:20:41,730
gått fram och tillbaka, fram och tillbaka,
exekvera denna algoritm, byta

577
00:20:41,730 --> 00:20:44,620
personer på varje pass, ungefär?

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
Det är faktiskt n kvadrat, rätt?

580
00:20:50,010 --> 00:20:53,000
>> För i värsta fall, du kan typ
av tycker om detta intuitivt,

581
00:20:53,000 --> 00:20:54,800
även om det kan ta lite
lite tid att sjunka in

582
00:20:54,800 --> 00:20:57,590
I värsta fall, vad skulle dessa
sju personer har sett ut, i

583
00:20:57,590 --> 00:21:00,230
termer av arrangemanget
av deras nummer?

584
00:21:00,230 --> 00:21:01,460
Helt bakåt, höger?

585
00:21:01,460 --> 00:21:02,815
Och bara för att simulera det,
vad var ditt namn igen?

586
00:21:02,815 --> 00:21:03,360
>> MIKE: Mike.

587
00:21:03,360 --> 00:21:03,640
>> DAVID J. MALAN: Mike?

588
00:21:03,640 --> 00:21:08,100
OK, Mike, kan du gå med bara mig över
här bara en sekund?

589
00:21:08,100 --> 00:21:08,880
Nej, faktiskt inte.

590
00:21:08,880 --> 00:21:10,150
Ledsen Mike, låt oss spola tillbaka.

591
00:21:10,150 --> 00:21:10,910
Vad är ditt namn igen?

592
00:21:10,910 --> 00:21:11,180
>> NEIL: Neil.

593
00:21:11,180 --> 00:21:11,640
>> DAVID J. MALAN: Neil.

594
00:21:11,640 --> 00:21:13,750
OK, Neil, kommer du med
mig, om ni inte har något emot.

595
00:21:13,750 --> 00:21:17,150
Så jag kommer att föreslå, bara för
enkelhet, att Neil är nu i hans

596
00:21:17,150 --> 00:21:18,510
värsta möjliga fall.

597
00:21:18,510 --> 00:21:20,720
Men minns hur jag genomfört
min algoritm.

598
00:21:20,720 --> 00:21:24,530
Jag jämför, jämföra, jämföra,
jämföra, jämföra, oh.

599
00:21:24,530 --> 00:21:26,640
Nu är killarna ute
av ordning, så jag fixa.

600
00:21:26,640 --> 00:21:27,980
Så ni byta.

601
00:21:27,980 --> 00:21:31,630
Men tänk nu, hur mycket längre
har Neil åka?

602
00:21:31,630 --> 00:21:32,690
Det är ungefär n.

603
00:21:32,690 --> 00:21:33,570
Du vet, det är faktiskt inte n.

604
00:21:33,570 --> 00:21:36,040
Det är som, n minus 1, men jag får
irriterad hålla reda på den lilla

605
00:21:36,040 --> 00:21:37,550
nummer, så låt oss bara kalla det n.

606
00:21:37,550 --> 00:21:42,860
>> Så om Neil flyttar ett steg maximalt varje
tid, och att flytta Neil ett steg,

607
00:21:42,860 --> 00:21:46,580
Jag måste göra det här riktigt tråkiga pass
fram och tillbaka, är detta ungefär

608
00:21:46,580 --> 00:21:52,080
gör detta, n steg, totalt n gånger,
eftersom det kommer att ta mig

609
00:21:52,080 --> 00:21:55,820
att många åtgärder för att få Neil alla
vägen till där han hör hemma.

610
00:21:55,820 --> 00:21:58,620
Låt bara alla andra om ni
var alla mis-beställda också.

611
00:21:58,620 --> 00:22:01,100
>> Så låt oss kalla bubbla sortera n kvadrat.

612
00:22:01,100 --> 00:22:04,860
Gångtiden för denna algoritm, den
utförandet av denna algoritm, den

613
00:22:04,860 --> 00:22:07,120
effektiviteten i denna algoritm,
vi ska bara beskriva mer

614
00:22:07,120 --> 00:22:08,800
generellt såsom n squared.

615
00:22:08,800 --> 00:22:11,650
Vilket är trevligt, eftersom jag kunde göra det
samma exempel med åtta personer, nio

616
00:22:11,650 --> 00:22:15,450
människor, en miljon människor, och det
Svaret kommer inte att förändras.

617
00:22:15,450 --> 00:22:18,870
>> Så om ni inte skulle ha något emot, låt oss
återställa dig till där du började.

618
00:22:18,870 --> 00:22:22,510
Och låt oss försöka två andra metoder och
se om vi inte kan göra grunden

619
00:22:22,510 --> 00:22:23,820
bättre än så här.

620
00:22:23,820 --> 00:22:27,130
Så den här gången kommer jag att föreslå
ett slags annan algoritm.

621
00:22:27,130 --> 00:22:29,950
Det var väldigt smart av oss förra gången,
och ni var rätt att ha

622
00:22:29,950 --> 00:22:32,470
rätt instinkter bara typ
att byta parvis.

623
00:22:32,470 --> 00:22:36,500
Men om jag ville verkligen att närma sig denna
enkelt, och mitt mål är att flytta

624
00:22:36,500 --> 00:22:39,800
alla de små siffrorna på detta sätt, och
skjuta alla de stora siffrorna som

625
00:22:39,800 --> 00:22:43,030
Förresten, varför inte jag göra just det i
mest naivt sätt och se om jag

626
00:22:43,030 --> 00:22:45,730
kan göra bättre än vad som var en
ganska komplex algoritm?

627
00:22:45,730 --> 00:22:46,620
>> Så låt oss se.

628
00:22:46,620 --> 00:22:48,940
Fyra är ett ganska litet antal, så jag är
kommer att lämna dig där ögonblicket.

629
00:22:48,940 --> 00:22:50,610
Ooh, är nummer två ännu bättre.

630
00:22:50,610 --> 00:22:52,230
Så kan du bara steg framåt
för ett ögonblick?

631
00:22:52,230 --> 00:22:55,670
Detta är för närvarande min minsta numrerade
kandidat, och jag kommer att minnas

632
00:22:55,670 --> 00:22:57,000
att med vilja, en variabel.

633
00:22:57,000 --> 00:22:57,930
Men jag kommer att hålla kontroll.

634
00:22:57,930 --> 00:22:59,890
Finns det någon vars
Antalet är mindre?

635
00:22:59,890 --> 00:23:00,460
Six, nr.

636
00:23:00,460 --> 00:23:01,390
Åh, det är Neil igen.

637
00:23:01,390 --> 00:23:04,050
>> Så jag kommer att skjuta dig tillbaka
slags konceptuellt.

638
00:23:04,050 --> 00:23:05,120
Neil kommer att träda fram.

639
00:23:05,120 --> 00:23:08,440
Och nu, den variabel som jag använder till
hålla reda på vem som har den minsta

640
00:23:08,440 --> 00:23:11,390
numret uppdateras för att innehålla
Neils läge.

641
00:23:11,390 --> 00:23:12,110
Nåväl, låt oss se.

642
00:23:12,110 --> 00:23:13,960
Tre, sju, fem.

643
00:23:13,960 --> 00:23:15,590
OK, vet jag Neil var den minsta.

644
00:23:15,590 --> 00:23:18,110
Vad är det enklaste sak
för mig att göra nu?

645
00:23:18,110 --> 00:23:21,410
Jag tänker inte slösa bort min tid genom att bara
bubblande Neil en plats till vänster.

646
00:23:21,410 --> 00:23:25,350
Varför inte jag satte bara Neil där han
tillhör, vilket naturligtvis var?

647
00:23:25,350 --> 00:23:26,160
>> Hela vägen från början.

648
00:23:26,160 --> 00:23:27,720
Så Neil, kom med mig.

649
00:23:27,720 --> 00:23:28,910
Och vad var ditt namn igen?

650
00:23:28,910 --> 00:23:29,310
>> GRACE: Grace.

651
00:23:29,310 --> 00:23:29,710
>> DAVID J. MALAN: Grace.

652
00:23:29,710 --> 00:23:29,920
OK.

653
00:23:29,920 --> 00:23:32,490
Så Grace, tyvärr, du är
typ av i vägen.

654
00:23:32,490 --> 00:23:34,290
Så hur löser vi detta problem?

655
00:23:34,290 --> 00:23:34,490
Rätt?

656
00:23:34,490 --> 00:23:37,500
Om detta är en array, det finns
endast sju platser.

657
00:23:37,500 --> 00:23:40,830
Minns att, med Rob, vi talade om
förklara åldrar, och vi hade bara en

658
00:23:40,830 --> 00:23:41,740
ändligt antal åldrar?

659
00:23:41,740 --> 00:23:42,535
Samma idé här.

660
00:23:42,535 --> 00:23:44,300
Vi har bara ett ändligt antal ints.

661
00:23:44,300 --> 00:23:47,590
Grace är typ av i vår
sätt, så hur vi fixar?

662
00:23:47,590 --> 00:23:49,555
>> Det enklaste sättet är som,
Nåd, sorry.

663
00:23:49,555 --> 00:23:51,870
Du kommer att behöva gå över
det så vi kan få plats.

664
00:23:51,870 --> 00:23:55,290
Nu, om du tycker om det här, kanske
Vi gjorde bara problemet värre.

665
00:23:55,290 --> 00:23:58,510
Och kanske vi gjorde, eftersom det som om
Grace var på rätt ställe?

666
00:23:58,510 --> 00:24:01,730
Men vi vet att hon inte, eftersom
annars skulle hon ha varit

667
00:24:01,730 --> 00:24:03,980
stående framåt istället för
Neil vid denna tid, eller hur?

668
00:24:03,980 --> 00:24:05,550
Vi har redan kollat ​​hennes nummer ut.

669
00:24:05,550 --> 00:24:05,770
>> Okej.

670
00:24:05,770 --> 00:24:09,110
Så nu är Neil på rätt plats, och
Jag kan göra en liten optimering.

671
00:24:09,110 --> 00:24:11,740
För nästa minut, jag kommer att ignorera
Neil alla tillsammans, för att inte

672
00:24:11,740 --> 00:24:15,280
slösa sin tid, eller oavsiktligt
byta honom till fel ställe.

673
00:24:15,280 --> 00:24:17,805
Så nu, hur jag hitta nästa
element som är minsta?

674
00:24:17,805 --> 00:24:18,480
Två.

675
00:24:18,480 --> 00:24:20,225
Det är ett ganska bra antal, om
du vill kliva fram och

676
00:24:20,225 --> 00:24:21,100
Jag kommer ihåg dig.

677
00:24:21,100 --> 00:24:21,980
Sex, inte bra.

678
00:24:21,980 --> 00:24:24,820
Fyra, tre, sju, fem, inte bra.

679
00:24:24,820 --> 00:24:26,800
Så låt mig flytta dig till
din rätt ställe.

680
00:24:26,800 --> 00:24:28,470
Och vi hade bara tur den här gången.

681
00:24:28,470 --> 00:24:31,350
>> Nu kommer jag att ignorera dessa
två killar, och nu gör något mer

682
00:24:31,350 --> 00:24:32,260
passera genom denna.

683
00:24:32,260 --> 00:24:33,490
Sex, att ett ganska litet antal.

684
00:24:33,490 --> 00:24:34,300
Kom fram.

685
00:24:34,300 --> 00:24:35,220
Åh, förlåt.

686
00:24:35,220 --> 00:24:37,640
Graces nummer är bättre,
så trampa på framåt.

687
00:24:37,640 --> 00:24:38,260
Fyra.

688
00:24:38,260 --> 00:24:39,120
Tyvärr, Grace.

689
00:24:39,120 --> 00:24:39,950
Gå tillbaka igen.

690
00:24:39,950 --> 00:24:41,550
Nummer tre är bättre.

691
00:24:41,550 --> 00:24:42,290
Seven.

692
00:24:42,290 --> 00:24:42,720
Fem.

693
00:24:42,720 --> 00:24:43,550
Och nu vad heter du nu igen?

694
00:24:43,550 --> 00:24:44,000
>> JASON: Jason.

695
00:24:44,000 --> 00:24:44,420
>> DAVID J. MALAN: Jason.

696
00:24:44,420 --> 00:24:47,050
Så Jason är nu den minsta
inslag som jag har valt.

697
00:24:47,050 --> 00:24:49,160
Vart ska han gå?

698
00:24:49,160 --> 00:24:50,380
Så där sex är.

699
00:24:50,380 --> 00:24:51,210
Och ditt namn är nytt?

700
00:24:51,210 --> 00:24:51,710
>> GABE: Gabe.

701
00:24:51,710 --> 00:24:52,340
>> DAVID J. MALAN: Gabe.

702
00:24:52,340 --> 00:24:53,220
Gabe är i vägen.

703
00:24:53,220 --> 00:24:54,640
Vad är det lättaste att göra?

704
00:24:54,640 --> 00:24:58,390
Byt dessa två killar och fortsätta.

705
00:24:58,390 --> 00:24:59,020
Så nu ska vi se.

706
00:24:59,020 --> 00:25:00,170
Vem är den minsta?

707
00:25:00,170 --> 00:25:01,030
Fyra.

708
00:25:01,030 --> 00:25:01,990
Låt mig bara typ av fusk.

709
00:25:01,990 --> 00:25:03,090
Fem kommer att bli det minsta.

710
00:25:03,090 --> 00:25:05,220
Jag hittar nästa, om du vill öka
framåt, vad jag har att göra med

711
00:25:05,220 --> 00:25:06,820
dessa killar, med Gabe?

712
00:25:06,820 --> 00:25:08,450
Swap igen.

713
00:25:08,450 --> 00:25:10,740
Så nu, fortfarande något i ordning.

714
00:25:10,740 --> 00:25:14,140
Jag hittade Gabe vara den minsta, så
Jag hoppar ut honom, flyttar er över.

715
00:25:14,140 --> 00:25:15,190
Och gjort.

716
00:25:15,190 --> 00:25:17,200
>> Så svaret är detsamma.

717
00:25:17,200 --> 00:25:18,600
Slutresultatet är detsamma.

718
00:25:18,600 --> 00:25:22,730
Vilken av dessa två algoritmer
är bättre?

719
00:25:22,730 --> 00:25:23,500
Den andra, hörde jag.

720
00:25:23,500 --> 00:25:24,252
Varför?

721
00:25:24,252 --> 00:25:25,900
>> SPEAKER 3: Det n steg [OHÖRBAR].

722
00:25:25,900 --> 00:25:27,600
>> DAVID J. MALAN: Det är n steg som mest.

723
00:25:27,600 --> 00:25:28,490
Intressant.

724
00:25:28,490 --> 00:25:30,610
Så är det dock?

725
00:25:30,610 --> 00:25:33,630
Så hur har jag hitta den
minsta elementet?

726
00:25:33,630 --> 00:25:37,060
Hur många steg jag måste ta
den finner det minsta elementet?

727
00:25:37,060 --> 00:25:39,220
Jag hade en ser hela vägen
i slutet, eller hur?

728
00:25:39,220 --> 00:25:41,530
För i det värsta fallet, vilken
Om Neil var här?

729
00:25:41,530 --> 00:25:45,700
Så bara hitta det minsta elementet
tar mig n steg, eller n minus 1.

730
00:25:45,700 --> 00:25:46,100
Men, OK.

731
00:25:46,100 --> 00:25:46,980
Så fixa Neil.

732
00:25:46,980 --> 00:25:48,740
Kom ihåg att, en minut eller så sedan.

733
00:25:48,740 --> 00:25:51,680
>> Men hur gjorde jag hitta nästa
minsta elementet?

734
00:25:51,680 --> 00:25:54,830
Det är n minus 1, eller n minus 2 riktigt,
från antalet steg.

735
00:25:54,830 --> 00:25:55,440
Så OK.

736
00:25:55,440 --> 00:25:57,390
Så jag gjorde N minus 2.

737
00:25:57,390 --> 00:25:57,600
Okej.

738
00:25:57,600 --> 00:25:59,130
Så det känns lite bättre.

739
00:25:59,130 --> 00:25:59,730
Okej.

740
00:25:59,730 --> 00:26:03,270
Hur många steg nästa gång
hitta nummer tre?

741
00:26:03,270 --> 00:26:04,420
Så n minus 4.

742
00:26:04,420 --> 00:26:07,670
Så det minskar, ett färre
steg på varje iteration.

743
00:26:07,670 --> 00:26:08,740
Så det här känns bättre, eller hur?

744
00:26:08,740 --> 00:26:13,450
Om förra gången det var ungefär n gånger n,
denna gång är det N minus 1, plus N minus

745
00:26:13,450 --> 00:26:16,500
2, plus n minus 3, plus n
minus 4, punkt, punkt, punkt.

746
00:26:16,500 --> 00:26:18,750
Men om du minns från din high school
läroböcker, den lilla fuska

747
00:26:18,750 --> 00:26:24,380
plåt på baksidan som har formler, om
du lägger upp denna serie av siffror,

748
00:26:24,380 --> 00:26:31,280
vad som är det totala antalet steg
kommer att vara att jag tar här?

749
00:26:31,280 --> 00:26:36,580
>> Detta är en av dem, gillar, n minus
1, gånger n, delat med 2.

750
00:26:36,580 --> 00:26:39,040
Så låt mig se om jag kan dra
upp detta för bara ett ögonblick.

751
00:26:39,040 --> 00:26:42,230
Och återigen, jag slags avrundning vissa
siffror bara för att hålla våra liv enkla,

752
00:26:42,230 --> 00:26:47,830
men som jag minns det, det är något som om
Jag gör n minus ett ting, då n minus

753
00:26:47,830 --> 00:26:53,570
2, sedan N minus 3, är det ungefär
något sådant över 2, och om jag

754
00:26:53,570 --> 00:26:55,510
multiplicera detta ut, det är
faktiskt n kvadrat.

755
00:26:55,510 --> 00:26:58,940
Det är inte mår så bra.
n minus n över 2.

756
00:26:58,940 --> 00:27:00,350
>> Men här är en sak.

757
00:27:00,350 --> 00:27:03,720
I datavetenskap, när problemen
börjar bli intressant är när n

758
00:27:03,720 --> 00:27:04,700
blir riktigt stor.

759
00:27:04,700 --> 00:27:08,110
Och när n blir riktigt stor, vilket av
dessa värden kommer att dominera alla

760
00:27:08,110 --> 00:27:09,750
av de andra?

761
00:27:09,750 --> 00:27:10,990
Det är typ av n kvadrat, rätt?

762
00:27:10,990 --> 00:27:13,340
Ja, dividera med 2 är ganska bra.

763
00:27:13,340 --> 00:27:16,740
Men om du pratar om miljarder
bitar av data, eller biljoner

764
00:27:16,740 --> 00:27:18,700
bitar av data, ok, så
du är dubbelt så snabbt.

765
00:27:18,700 --> 00:27:22,440
Men vem bryr sig egentligen om det stora antal,
Om denna faktor är vad som får

766
00:27:22,440 --> 00:27:23,040
större och större.

767
00:27:23,040 --> 00:27:25,990
Och säkert är det mer av
en skillnad än den här killen.

768
00:27:25,990 --> 00:27:29,120
Så även om ni har rätt, det
andra algoritmen, vi kallar det

769
00:27:29,120 --> 00:27:32,970
selection sort, är, i den verkliga världen, en
lite snabbare potentiellt, eftersom jag är

770
00:27:32,970 --> 00:27:35,360
tar färre och färre
steg varje gång.

771
00:27:35,360 --> 00:27:37,340
>> Det är egentligen inte i grunden snabbare.

772
00:27:37,340 --> 00:27:41,430
För om vi spelar faktiskt detta för
stora värden på N, vid slutet av

773
00:27:41,430 --> 00:27:44,750
dagen, för tillräckligt stora n, det är fortfarande
kommer att kännas ganska långsam.

774
00:27:44,750 --> 00:27:46,770
Nåväl, låt mig ta ett
sista passet på det.

775
00:27:46,770 --> 00:27:48,920
Det är vad jag skulle kalla
selection sort.

776
00:27:48,920 --> 00:27:51,040
Kan ni återställa er
en sista gång?

777
00:27:51,040 --> 00:27:53,550
Och i det senare fallet, jag kommer
att föreslå något

778
00:27:53,550 --> 00:27:54,970
kallas insättning sort.

779
00:27:54,970 --> 00:27:57,470
Insertion sort är, konceptuellt,
lite annorlunda.

780
00:27:57,470 --> 00:28:00,980
>> Hellre än att gå fram och tillbaka och
välja det minsta elementet, jag

781
00:28:00,980 --> 00:28:05,030
bara kommer att ta itu med vart och ett av dessa
killar som jag möter dem, och sätt

782
00:28:05,030 --> 00:28:06,850
dem i deras rätta plats.

783
00:28:06,850 --> 00:28:10,160
Så jag ska bara börja med Grace,
och jag ser att hon är nummer fyra.

784
00:28:10,160 --> 00:28:11,720
Var hör nummer fyra?

785
00:28:11,720 --> 00:28:14,940
Jag har inte börjat sortera någonting,
så Grace får stanna där.

786
00:28:14,940 --> 00:28:18,355
Och nu ska jag hävda, om du kunde
ta ett steg till höger, här

787
00:28:18,355 --> 00:28:21,650
min sorterad lista, detta är mitt
osorterad återstående lista.

788
00:28:21,650 --> 00:28:23,260
Så nu ska jag gå nästa,
och vad heter du nu igen?

789
00:28:23,260 --> 00:28:23,700
>> Branson: Branson.

790
00:28:23,700 --> 00:28:24,150
>> DAVID J. MALAN: Branson.

791
00:28:24,150 --> 00:28:25,375
Så Branson är nummer två.

792
00:28:25,375 --> 00:28:27,490
Så jag kommer att ta dig
ut för ett ögonblick.

793
00:28:27,490 --> 00:28:30,940
Och nu, där du hör hemma
i denna samling?

794
00:28:30,940 --> 00:28:32,360
Så till höger om nåd.

795
00:28:32,360 --> 00:28:35,670
Så återigen, vi slags göra
Grace gör en hel del arbete här.

796
00:28:35,670 --> 00:28:37,290
Var placerar vi dig?

797
00:28:37,290 --> 00:28:40,120
Så vi kommer att glida dig till
vänster, och sätt Branson där.

798
00:28:40,120 --> 00:28:41,680
Men nu har jag hävdar att
ni är klar.

799
00:28:41,680 --> 00:28:43,240
Men varsel, jag använder inte extra utrymme.

800
00:28:43,240 --> 00:28:45,130
Det är fortfarande två element
här, 5 hit.

801
00:28:45,130 --> 00:28:47,910
Total array storlek är 7, så jag är
inte fusk, okej?

802
00:28:47,910 --> 00:28:51,950
>> Så nu har vi, med Gabe här,
nummer sex, där du hör hemma?

803
00:28:51,950 --> 00:28:52,650
Du hade tur igen.

804
00:28:52,650 --> 00:28:53,820
Så du får bo där.

805
00:28:53,820 --> 00:28:57,210
Bara ta en liten steg åt höger
bara för att klargöra att du är sorterad.

806
00:28:57,210 --> 00:29:00,520
Och nu har vi Neil igen, antal
en, var ska du gå?

807
00:29:00,520 --> 00:29:03,540
Och nu är där vi börjar se att
denna algoritm, men den första

808
00:29:03,540 --> 00:29:05,950
anblicken känns ganska smart, titta
vad är på väg att hända.

809
00:29:05,950 --> 00:29:07,370
Om du kunde kliva fram.

810
00:29:07,370 --> 00:29:09,260
>> Var vill vi sätta Neil?

811
00:29:09,260 --> 00:29:11,830
Så uppenbarligen här, så hur
får vi Neil dit?

812
00:29:11,830 --> 00:29:12,970
Låt oss göra detta steg-för-steg.

813
00:29:12,970 --> 00:29:15,620
Gabe, där behöver du gå?

814
00:29:15,620 --> 00:29:19,590
Japp, så ta ett stort steg,
eller två halva steg för att göra

815
00:29:19,590 --> 00:29:20,820
ett steg över det.

816
00:29:20,820 --> 00:29:21,750
Grace, där du går?

817
00:29:21,750 --> 00:29:22,510
Bra.

818
00:29:22,510 --> 00:29:23,500
Så ännu ett steg.

819
00:29:23,500 --> 00:29:24,960
Och slutligen, Branson?

820
00:29:24,960 --> 00:29:25,460
Ett annat steg.

821
00:29:25,460 --> 00:29:27,190
Och nu kan vi sätta Neil på plats.

822
00:29:27,190 --> 00:29:28,440
>> Så nu, fortsätter denna logik.

823
00:29:28,440 --> 00:29:32,420
Även om vi inte är skiftande Neil
över och över och över, för att sätta honom

824
00:29:32,420 --> 00:29:36,420
där han går, i värsta fall, den
nästa nummer vi kan stöta kunde

825
00:29:36,420 --> 00:29:42,220
vara antalet, säg, det fanns ett antal
noll, då vi kommer att flytta alla

826
00:29:42,220 --> 00:29:42,730
dessa killar.

827
00:29:42,730 --> 00:29:44,950
Antag att det finns ett antal, negativ
en, då måste vi flytta

828
00:29:44,950 --> 00:29:46,080
alla dessa killar.

829
00:29:46,080 --> 00:29:48,500
Så vi är egentligen bara typ av vändning
problemet runt, så att vi är

830
00:29:48,500 --> 00:29:52,620
överföra kostnader från den
urvalsprocess så införingen

831
00:29:52,620 --> 00:29:56,930
process, så att ni bara hade
att flytta ungefär n minus något

832
00:29:56,930 --> 00:29:57,940
antal steg.

833
00:29:57,940 --> 00:30:01,200
Och att antalet steg kommer bara
att öka när jag väljer fler nummer,

834
00:30:01,200 --> 00:30:04,730
om jag måste hålla prejar er
tillbaka, och tillbaka, och tillbaka.

835
00:30:04,730 --> 00:30:08,320
>> Så det tråkiga är nu alla dessa
algoritmer är n kvadrat.

836
00:30:08,320 --> 00:30:10,570
Låt oss gå vidare och tack vare dessa
killar, och visualisera dessa lite

837
00:30:10,570 --> 00:30:11,090
annorlunda.

838
00:30:11,090 --> 00:30:12,312
Mycket bra gjort.

839
00:30:12,312 --> 00:30:14,120
>> [Applåder]

840
00:30:14,120 --> 00:30:15,030
>> Okej.

841
00:30:15,030 --> 00:30:16,280
Där du går.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Tack för -

844
00:30:18,470 --> 00:30:19,190
>> Branson: [OHÖRBAR] hålla tal.

845
00:30:19,190 --> 00:30:21,990
>> DAVID J. MALAN: Nej, du får
hålla tal också.

846
00:30:21,990 --> 00:30:23,440
Okej.

847
00:30:23,440 --> 00:30:24,100
Snyggt gjort.

848
00:30:24,100 --> 00:30:25,300
Okej.

849
00:30:25,300 --> 00:30:30,510
Så låt oss se om vi inte kan nu sammanfatta
snabbare, och mer visuellt,

850
00:30:30,510 --> 00:30:33,410
exakt vad som hände
Här följer.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Jag kommer att gå vidare
och dra upp Firefox.

853
00:30:38,770 --> 00:30:41,310
Vi ska länka denna demonstration
på kursens hemsida.

854
00:30:41,310 --> 00:30:43,870
Java är lite irriterande att få arbeta
i vissa webbläsare dessa dagar.

855
00:30:43,870 --> 00:30:46,760
Så om du vill spela med det här hemma,
inser du kanske behöver använda Firefox

856
00:30:46,760 --> 00:30:47,990
att få det att fungera.

857
00:30:47,990 --> 00:30:50,440
Och vad jag ska göra med detta
Demonstrationen är följande.

858
00:30:50,440 --> 00:30:54,875
>> Längst ner, har jag en hel drös med
menyalternativ, inklusive en start och en

859
00:30:54,875 --> 00:30:55,840
stopp-knappen.

860
00:30:55,840 --> 00:30:59,450
Också, som en parentes, det verkar vara en
bugg i dessa program, där du

861
00:30:59,450 --> 00:31:03,720
kan faktiskt inte se starten eller stoppa
knappen om du inte håller Kommando eller Alt

862
00:31:03,720 --> 00:31:06,560
plus och zooma in, vilket märkligt
visar fler knappar.

863
00:31:06,560 --> 00:31:09,090
Så bara FYI om du spelar
med detta hemma.

864
00:31:09,090 --> 00:31:12,870
Nu ska jag klicka på Start på bara ett
ögonblick, efter att ha angett en fördröjning,

865
00:31:12,870 --> 00:31:16,810
gillar, 200 millisekunder här, precis
så att vi kan se vad som händer.

866
00:31:16,810 --> 00:31:20,180
>> Så jag hävdar att detta är en visualisering
av den första algoritmen

867
00:31:20,180 --> 00:31:23,730
killarna gjorde, bubbla sortera, varigenom
vi bytte folk parvisa.

868
00:31:23,730 --> 00:31:27,490
Den viktigaste insikten att denna visualisering
är att höjden av staplarna

869
00:31:27,490 --> 00:31:30,510
representerar storleken på talet.

870
00:31:30,510 --> 00:31:32,210
Så högre stapel, desto
Ju högre siffra.

871
00:31:32,210 --> 00:31:33,680
Kortare baren, lägre tal.

872
00:31:33,680 --> 00:31:38,630
Och om du märker, vi går igenom
den första variant av denna algoritm,

873
00:31:38,630 --> 00:31:42,620
byta stora och små siffror, så att
det lilla antalet kommer först och

874
00:31:42,620 --> 00:31:44,280
det stora numret går till höger.

875
00:31:44,280 --> 00:31:48,770
>> Och så fort vi får i slutet av arrayen
av många fler siffror än sju, vi

876
00:31:48,770 --> 00:31:49,900
kommer att gå tillbaka till början.

877
00:31:49,900 --> 00:31:51,140
Och förutse detta.

878
00:31:51,140 --> 00:31:54,860
Längst till vänster, är den lilla killen går
att byta åt sidan, och detta

879
00:31:54,860 --> 00:31:56,010
processen upprepas.

880
00:31:56,010 --> 00:31:59,450
Nu denna visualisering blir snabbt
tråkigt, så låt mig gå vidare och sluta

881
00:31:59,450 --> 00:32:04,170
det, ändra fördröjningen något mycket
snabbare bara för att få nu, en känsla för

882
00:32:04,170 --> 00:32:05,060
denna algoritm.

883
00:32:05,060 --> 00:32:07,840
>> Så även om jag har sped upp det, är detta
som att uppgradera min processor, köpa

884
00:32:07,840 --> 00:32:08,580
en ny dator.

885
00:32:08,580 --> 00:32:12,980
Jag har inte i grunden förändrat mitt
algoritm, men du kan faktiskt se mer

886
00:32:12,980 --> 00:32:16,800
tydligare än med människor, att den stora
siffror bubblar upp till toppen,

887
00:32:16,800 --> 00:32:20,900
och de små siffrorna bubblar
ner till botten.

888
00:32:20,900 --> 00:32:22,390
Och nu denna sak sorteras här.

889
00:32:22,390 --> 00:32:25,260
Och i förbigående, på torgen, det finns
bara några bokföring där till

890
00:32:25,260 --> 00:32:28,010
hjälpa dig att räkna hur många jämförelser,
eller hur många swappar har

891
00:32:28,010 --> 00:32:28,950
faktiskt gjorts.

892
00:32:28,950 --> 00:32:30,750
>> Nåväl, låt oss prova en av
de andra vi såg.

893
00:32:30,750 --> 00:32:37,116
Låt mig klicka på bubblan sort här, och
låt mig välja, och hela denna webbsida

894
00:32:37,116 --> 00:32:38,936
är en liten buggy.

895
00:32:38,936 --> 00:32:41,155
Låt oss acceptera risken
och köra den igen.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Där vi går.

898
00:32:45,030 --> 00:32:47,180
Så låt oss göra urvalet sortera.

899
00:32:47,180 --> 00:32:49,140
Jag vet inte varför menyn
visas där borta.

900
00:32:49,140 --> 00:32:54,070
Låt oss zooma in för att fixa det
bugg, ändra detta till 50.

901
00:32:54,070 --> 00:32:56,020
Ah, låt oss faktiskt göra
som mycket snabbare.

902
00:32:56,020 --> 00:32:59,160
Fem millisekunder eller så, och Start.

903
00:32:59,160 --> 00:33:00,470
>> Så detta är valet sort.

904
00:33:00,470 --> 00:33:03,070
Så återigen, tänka på vad vi
gjorde med människorna här uppe.

905
00:33:03,070 --> 00:33:08,490
Vi gick igenom arrayen och valda
det minsta elementet igen,

906
00:33:08,490 --> 00:33:09,250
och igen, och igen.

907
00:33:09,250 --> 00:33:11,110
Nu hävdar jag att var fortfarande ganska dåligt.

908
00:33:11,110 --> 00:33:15,010
Det var fortfarande n kvadrat, ge eller ta,
men det var, i den verkliga världen, lite

909
00:33:15,010 --> 00:33:18,280
snabbare, eftersom jag verkligen tar
något färre steg varje gång.

910
00:33:18,280 --> 00:33:19,800
Men vi talar bara vad?

911
00:33:19,800 --> 00:33:21,830
Kanske 40 eller så stänger här?

912
00:33:21,830 --> 00:33:23,200
Vi pratar inte 40 miljoner.

913
00:33:23,200 --> 00:33:27,430
Så det är inte klart helt för mig att
var verkligen en betydande vinst.

914
00:33:27,430 --> 00:33:32,530
>> Låt mig nu gå tillbaka och ändra till vårt
tredje algoritm, som väljer

915
00:33:32,530 --> 00:33:33,180
insättning sort.

916
00:33:33,180 --> 00:33:36,380
Och nu är det verkligen buggig eftersom
Menyn egentligen inte borde vara där nere.

917
00:33:36,380 --> 00:33:40,840
Så nu ska vi rulla tillbaka upp hit
och starta denna algoritm.

918
00:33:40,840 --> 00:33:43,270
Whoop, starta och stoppa.

919
00:33:43,270 --> 00:33:47,160
Så här en typ av har en ganska mönster
till det, vilket vi återigen

920
00:33:47,160 --> 00:33:50,240
sätter människorna, eller i
detta fall, barerna i

921
00:33:50,240 --> 00:33:52,620
deras lämplig plats.

922
00:33:52,620 --> 00:33:55,430
Och det är redan gjort innan
Jag vände mig om.

923
00:33:55,430 --> 00:33:58,940
Men här också, i teorin,
fortfarande n kvadrat.

924
00:33:58,940 --> 00:34:01,430
>> Så låt oss se om vi inte kan sammanfatta
dessa enligt följande.

925
00:34:01,430 --> 00:34:04,750
Jag ska gå vidare och bara för att ge
oss slags ett gemensamt sätt att tala

926
00:34:04,750 --> 00:34:08,489
om dessa saker, låt mig presentera
bara en bit av notation här.

927
00:34:08,489 --> 00:34:12,480
Du är på väg att se något som kallas big
O, eftersom det är bokstavligen en stor

928
00:34:12,480 --> 00:34:16,320
O. Och detta är ett sätt att en dator
vetenskapsman eller en matematiker ens använder

929
00:34:16,320 --> 00:34:19,230
att beskriva den gångtid
av någon algoritm.

930
00:34:19,230 --> 00:34:21,400
Hur många steg tar det egentligen?

931
00:34:21,400 --> 00:34:25,080
>> Nu ska jag skämma ut mig med
min handstil här på bara ett ögonblick.

932
00:34:25,080 --> 00:34:29,020
Men låt mig gå vidare och säga att
detta kommer att bli stort O hit.

933
00:34:29,020 --> 00:34:33,610
Och låt mig presentera en annan
symbol, en huvudstad omega.

934
00:34:33,610 --> 00:34:37,080
Omega kommer att vara det motsatta,
huvudsak av stora O. big O

935
00:34:37,080 --> 00:34:40,790
medel, i värsta fall, hur mycket tid
kanske någon algoritm tar, i

936
00:34:40,790 --> 00:34:43,480
termer av n, omega tillfalla
vara hur mycket tid kan det ge

937
00:34:43,480 --> 00:34:45,409
tar i bästa fall.

938
00:34:45,409 --> 00:34:48,090
Och vi får se vad vi menar med
bästa fall på bara ett ögonblick.

939
00:34:48,090 --> 00:34:49,940
>> Så låt oss börja något enkelt.

940
00:34:49,940 --> 00:34:54,719
Låt mig börja med en linjär sökning.

941
00:34:54,719 --> 00:34:55,679
Så inte sortering.

942
00:34:55,679 --> 00:34:58,000
Vi kallar denna linjär sökning.

943
00:34:58,000 --> 00:35:01,140
Och nu, gör lite
bord ur detta.

944
00:35:01,140 --> 00:35:06,600
Och nu, i fallet med linjär sökning,
i värsta fall, hur många steg är

945
00:35:06,600 --> 00:35:11,770
det kommer att ta mig för att hitta en
antal godtyckliga val?

946
00:35:11,770 --> 00:35:14,540
Och det finns n totala dörrar
eller n totala antalet.

947
00:35:14,540 --> 00:35:15,940
Worst case.

948
00:35:15,940 --> 00:35:18,800
Hur många steg kommer jag att behöva
vidta för att hitta numret 50 i en array

949
00:35:18,800 --> 00:35:20,830
av n dörrar?

950
00:35:20,830 --> 00:35:21,410
Och varför?

951
00:35:21,410 --> 00:35:23,680
Eftersom det kan vara allt
sätt över på änden.

952
00:35:23,680 --> 00:35:27,120
Så mycket som Jennifer mötte, den
nummer 50 var hela vägen över, så i

953
00:35:27,120 --> 00:35:30,760
värsta fall linjär sökning
är stort O n, ska vi säga.

954
00:35:30,760 --> 00:35:33,430
>> Hur är det bästa fallet,
om du får verkligen lycklig?

955
00:35:33,430 --> 00:35:36,200
Det kommer bara att ta ett steg,
eller ett konstant antal steg.

956
00:35:36,200 --> 00:35:37,830
Så vi ska beskriva det som 1.

957
00:35:37,830 --> 00:35:39,010
Så detta är ganska bra.

958
00:35:39,010 --> 00:35:41,210
Nu tänk om vi gjorde något
gillar binär sökning?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
Så binär sökning, i värsta
fall, tog hur mycket tid?

961
00:35:47,846 --> 00:35:49,250
>> [Inplacering VOICES]

962
00:35:49,250 --> 00:35:51,310
>> DAVID J. MALAN: Så egentligen, jag
hörde det på ett par ställen.

963
00:35:51,310 --> 00:35:56,390
Så det logg faktiskt n, ge eller ta,
för som vi delar upp listan i hälften

964
00:35:56,390 --> 00:36:00,730
igen, och igen, och igen, vi kan
att hitta, slutligen, värde,

965
00:36:00,730 --> 00:36:04,750
om det är det, men det finns en hake.

966
00:36:04,750 --> 00:36:08,590
Vad är antagandet att vi måste
tar för givet för binär sökning?

967
00:36:08,590 --> 00:36:09,700
Det måste sorteras.

968
00:36:09,700 --> 00:36:12,770
Det är inte sorterats, kan du dela upp saken
i hälften och om igen, och du

969
00:36:12,770 --> 00:36:15,490
kan gå till vänster, och du kan gå rätt, och
du kan gå till vänster och höger, men du är

970
00:36:15,490 --> 00:36:18,070
kommer inte att hitta elementet om
listan inte är sorterad, eftersom

971
00:36:18,070 --> 00:36:18,790
du kanske missar det.

972
00:36:18,790 --> 00:36:22,120
Eftersom din heuristik, för att gå åt vänster
eller höger kommer att vara bristfällig, om det är

973
00:36:22,120 --> 00:36:23,420
faktiskt inte sorteras.

974
00:36:23,420 --> 00:36:26,110
Så det finns en slags dold kostnad
till med något sånt här.

975
00:36:26,110 --> 00:36:29,250
>> Nu, låt oss gå in i vår sortering
algoritmer söker inte -

976
00:36:29,250 --> 00:36:31,140
Åh, faktiskt Låt oss gå i detta ämne.

977
00:36:31,140 --> 00:36:33,190
Binary sökning i bästa fall?

978
00:36:33,190 --> 00:36:36,290
Det är också en om det bara råkar vara
i den mycket mitten av arrayen, eller

979
00:36:36,290 --> 00:36:37,810
mitt i telefonboken.

980
00:36:37,810 --> 00:36:39,710
Nu ska vi göra bubble sort.

981
00:36:39,710 --> 00:36:42,570
Så återigen, nu vi in ​​i
sorterar, inte de söker.

982
00:36:42,570 --> 00:36:47,220
>> I värsta fall, hur många steg vi
fordran bubbla sortera kommer att ta?

983
00:36:47,220 --> 00:36:48,410
n kvadrat.

984
00:36:48,410 --> 00:36:49,200
Så jag kommer att dra det.

985
00:36:49,200 --> 00:36:51,710
Ooh, ser min handstil ännu värre
när det är beräknat att stora.

986
00:36:51,710 --> 00:36:52,510
Okej.

987
00:36:52,510 --> 00:36:53,570
Så det är n kvadrat.

988
00:36:53,570 --> 00:36:59,460
Och i bästa fall av bubbla sortera,
hur många steg kommer det att ta?

989
00:36:59,460 --> 00:37:00,980
1, hörde jag.

990
00:37:00,980 --> 00:37:01,760
>> SPEAKER 1: n.

991
00:37:01,760 --> 00:37:03,286
>> DAVID J. MALAN: n, hörde jag.

992
00:37:03,286 --> 00:37:04,200
>> TALARE 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> DAVID J. MALAN: 2, hörde jag.

994
00:37:05,010 --> 00:37:06,670
Hör jag 3?

995
00:37:06,670 --> 00:37:07,080
Okej.

996
00:37:07,080 --> 00:37:11,390
Så jag har hört en, n, 2, men låt oss plocka
isär åtminstone den första av dessa

997
00:37:11,390 --> 00:37:12,330
förslag, 1.

998
00:37:12,330 --> 00:37:15,370
Det är inte en dålig instinkt, eftersom det
slags följer ett mönster här.

999
00:37:15,370 --> 00:37:19,670
Men om det tar bara 1 steg, hur i
världen kunde jag hävda att listan

1000
00:37:19,670 --> 00:37:22,900
sorteras, för om jag bara får
att ta ett steg, hur många element

1001
00:37:22,900 --> 00:37:25,230
kunde jag kolla faktiskt att vara säker?

1002
00:37:25,230 --> 00:37:28,270
Tja, bara 1, vilket innebär att det finns n
minus ett element som kan vara av

1003
00:37:28,270 --> 00:37:31,310
ordning, och jag tänker bara på tron ​​efter
tittar på en faktor som

1004
00:37:31,310 --> 00:37:31,850
sak sorteras.

1005
00:37:31,850 --> 00:37:33,930
Så 1 är inte korrekt här.

1006
00:37:33,930 --> 00:37:35,710
Så minimalt, hur många
har jag att titta på?

1007
00:37:35,710 --> 00:37:36,680
>> [Inplacering VOICES]

1008
00:37:36,680 --> 00:37:40,160
>> DAVID J. MALAN: n minus 1, eller egentligen,
n, eftersom jag måste titta på varje

1009
00:37:40,160 --> 00:37:42,190
inslag för att säkerställa att
det är inte i ordning.

1010
00:37:42,190 --> 00:37:44,750
Men återigen, vi sorterar av vågen vår
händerna på de mindre siffror och

1011
00:37:44,750 --> 00:37:47,100
anta att, såsom n blir stora, de är
ointressant ändå.

1012
00:37:47,100 --> 00:37:48,380
Så det är bubbla sortera.

1013
00:37:48,380 --> 00:37:49,830
Och nu, låt oss göra de två sistnämnda.

1014
00:37:49,830 --> 00:37:53,520
Urval sortera, och sedan kommer vi
göra insättning sort.

1015
00:37:53,520 --> 00:37:57,160
Och då kommer vi att blåsa ditt
sinnen med något mycket

1016
00:37:57,160 --> 00:37:58,926
bättre än alla dessa.

1017
00:37:58,926 --> 00:38:00,410
Okej.

1018
00:38:00,410 --> 00:38:04,700
>> Vad är det värsta fallet kör
tidpunkten för valet sort?

1019
00:38:04,700 --> 00:38:05,680
>> Högtalare 4: n kvadrat.

1020
00:38:05,680 --> 00:38:06,710
>> DAVID J. MALAN: n square, jag hör.

1021
00:38:06,710 --> 00:38:09,790
Men varför n kvadrat, intuitivt?

1022
00:38:09,790 --> 00:38:11,170
>> Högtalare 4: Eftersom vi bara gjorde det.

1023
00:38:11,170 --> 00:38:12,260
>> DAVID J. MALAN: Eftersom vi bara gjorde det.

1024
00:38:12,260 --> 00:38:12,550
OK.

1025
00:38:12,550 --> 00:38:13,380
Bra svar.

1026
00:38:13,380 --> 00:38:16,660
Men intuitivt, varför är urvalet
sortera n kvadrat?

1027
00:38:16,660 --> 00:38:18,980
Vad hade vi att göra
om och om igen?

1028
00:38:18,980 --> 00:38:22,570
Vi var tvungna att hålla skanna igenom, är
dig det minsta, du är den

1029
00:38:22,570 --> 00:38:24,020
minsta, är du det minsta.

1030
00:38:24,020 --> 00:38:27,480
Och beviljats, kunde vi ta n
steg, då n minus 1, och sedan n minus 2.

1031
00:38:27,480 --> 00:38:30,700
Men om du sorts lägga dem alla upp,
eller ta det på tro att jag har lagt

1032
00:38:30,700 --> 00:38:34,810
upp dem i förväg, får vi ungefär n
kvadrat minus några mindre tal.

1033
00:38:34,810 --> 00:38:36,730
Så jag kommer att kalla denna n kvadrat.

1034
00:38:36,730 --> 00:38:39,530
Men med val Sortera på bästa
fall, hur många steg är det

1035
00:38:39,530 --> 00:38:40,632
kommer att ta mig?

1036
00:38:40,632 --> 00:38:41,840
>> SPEAKER 5: [OHÖRBAR]

1037
00:38:41,840 --> 00:38:44,350
>> DAVID J. MALAN: Det är tyvärr
fortfarande n kvadrat, rätt?

1038
00:38:44,350 --> 00:38:49,590
För om jag väljer det minsta
element, och vi hade sju personer här,

1039
00:38:49,590 --> 00:38:53,280
Jag bara vet, när jag får till mycket
Därför att jag har hittat den minsta

1040
00:38:53,280 --> 00:38:55,670
nummer, oavsett var han eller
Hon kan ha varit.

1041
00:38:55,670 --> 00:38:58,820
Men hur hittar jag nästa
minsta antal?

1042
00:38:58,820 --> 00:39:00,160
Jag måste göra ett annat pass.

1043
00:39:00,160 --> 00:39:04,810
Så i bästa fall, vad är det
ingång till val Sortera?

1044
00:39:04,810 --> 00:39:07,830
Det är en redan Sortera listan, nummer ett,
nummer två, nummer tre, nummer fyra.

1045
00:39:07,830 --> 00:39:08,600
Men jag är en dator.

1046
00:39:08,600 --> 00:39:10,190
Jag kan bara titta på en
sak i taget.

1047
00:39:10,190 --> 00:39:12,465
Jag kan inte sortera om att ta ett steg
tillbaka som en människa och säga,

1048
00:39:12,465 --> 00:39:14,030
ooh, ser detta korrekt.

1049
00:39:14,030 --> 00:39:17,580
>> Jag kan bara döma riktighet i
urvalet sortera genom att välja

1050
00:39:17,580 --> 00:39:18,370
minsta antalet.

1051
00:39:18,370 --> 00:39:21,390
Men även om jag hittar nummer ett första,
om jag inte vet något annat om

1052
00:39:21,390 --> 00:39:24,460
de andra numren, vilket jag inte gör, allt jag
vet att jag har gått i arv en array

1053
00:39:24,460 --> 00:39:27,930
eller en uppsättning av dörrar som är bak
siffror, det enda sättet jag vet att en

1054
00:39:27,930 --> 00:39:28,680
var det minsta?

1055
00:39:28,680 --> 00:39:32,440
Om jag får hela vägen här och inser,
fan, var en verkligen de minsta.

1056
00:39:32,440 --> 00:39:34,870
>> Men hur avgör jag då att
två är den näst minsta?

1057
00:39:34,870 --> 00:39:38,350
Genom att göra samma ineffektivitet
igen och igen.

1058
00:39:38,350 --> 00:39:42,210
Så slutligen, med införande sortera,
hur, i värsta fall,

1059
00:39:42,210 --> 00:39:44,990
vi säger att det fungerar?

1060
00:39:44,990 --> 00:39:49,100
Det är för n kvadrat.

1061
00:39:49,100 --> 00:39:53,020
Och hur är den bästa fall?

1062
00:39:53,020 --> 00:39:56,282
Vi lämnar det som en cliffhanger.

1063
00:39:56,282 --> 00:40:00,090
Vi ska fylla i den tomma nästa gång,
men låt mig först föreslå att vi

1064
00:40:00,090 --> 00:40:02,620
fundamentalt bättre än
alla dessa, okej?

1065
00:40:02,620 --> 00:40:05,220
>> Så tänk själv vad insättning
Sortera kommer att bli.

1066
00:40:05,220 --> 00:40:06,910
Tja, var det inte mycket dramatisk,
eftersom jag är den enda

1067
00:40:06,910 --> 00:40:08,970
som såg förändringen.

1068
00:40:08,970 --> 00:40:09,620
Wow.

1069
00:40:09,620 --> 00:40:10,420
OK.

1070
00:40:10,420 --> 00:40:12,615
Så här har vi en något
annan demonstration.

1071
00:40:12,615 --> 00:40:16,580
Om jag zooma in här, ser du att på
vänster har vi bubbla sortera, i

1072
00:40:16,580 --> 00:40:20,740
mitten har vi urvalet sortera och på
längst till höger, har vi något vi

1073
00:40:20,740 --> 00:40:23,380
har inte tittat på ännu
kallas samman sort.

1074
00:40:23,380 --> 00:40:26,080
Men fundera över vad vi har varit
gör här hittills idag.

1075
00:40:26,080 --> 00:40:29,200
När Jennifer först kom upp på scenen,
Vi gick igenom matris med tal

1076
00:40:29,200 --> 00:40:33,750
igen, och igen, med linjär sökning,
och vi fick linjär gångtid, big O

1077
00:40:33,750 --> 00:40:35,100
på n, så att säga.

1078
00:40:35,100 --> 00:40:41,000
>> När vi betraktar nu den första veckan i
klass, när vi hade söndra och härska,

1079
00:40:41,000 --> 00:40:43,740
och vi hade telefonboken riva,
och Jennifer, och vi kollektivt

1080
00:40:43,740 --> 00:40:47,500
belånade att viktiga insikter, som var att
upprepa dig om och om igen genom

1081
00:40:47,500 --> 00:40:50,930
på något sätt kasta bort, kasta bort,
kasta bort, hälften av problemet, eller

1082
00:40:50,930 --> 00:40:55,320
allmänhet, dividera ett problem i halv,
och sedan behandling av mindre bit av

1083
00:40:55,320 --> 00:40:59,630
problemet som begreppsmässigt likvärdiga
till den andra, gjorde vi på något sätt

1084
00:40:59,630 --> 00:41:00,910
fundamentalt bättre.

1085
00:41:00,910 --> 00:41:04,720
Men med bubbla sortera, med val
Sortera, med införande sortera, vi har kanske

1086
00:41:04,720 --> 00:41:06,560
inga sådana insikter som Jennifer gjorde.

1087
00:41:06,560 --> 00:41:10,220
Vi ganska mycket bara gick tillbaka och
fram en hel massa gånger, och vi

1088
00:41:10,220 --> 00:41:12,650
tweaked saker lite, byta
i denna ordning, kanske

1089
00:41:12,650 --> 00:41:13,730
infoga eller markera.

1090
00:41:13,730 --> 00:41:16,950
Men i slutet av dagen, gjorde jag en hel del
av obekväma promenader fram och tillbaka.

1091
00:41:16,950 --> 00:41:21,160
Vi gjorde inte riktigt utnyttja något
smarta som Jennifer tyckte att dividera

1092
00:41:21,160 --> 00:41:22,040
och erövra.

1093
00:41:22,040 --> 00:41:25,620
>> Så sammanfoga sortera, däremot, som vi
kommer inte se förrän nästa vecka, det kommer

1094
00:41:25,620 --> 00:41:29,540
att utnyttja denna nyckel idé genom att dividera
ingången, och sedan halvera, och sedan

1095
00:41:29,540 --> 00:41:30,580
halvera, och sedan halvera.

1096
00:41:30,580 --> 00:41:34,590
Och på varje iteration av denna slinga,
sortera den vänstra halvan, och den högra

1097
00:41:34,590 --> 00:41:38,200
hälften, sedan den vänstra halvan av vänstra halvan,
och den högra halvan av den vänstra, sedan

1098
00:41:38,200 --> 00:41:40,990
den vänstra halvan av den högra halvan, och
den högra halvan av den högra halvan.

1099
00:41:40,990 --> 00:41:42,840
Och upprepa igen och igen.

1100
00:41:42,840 --> 00:41:46,170
>> Så du ser det här visuellt, men detta
är vad som väntar oss nästa vecka.

1101
00:41:46,170 --> 00:41:49,760
Och i allmänhet, när vi tänker lite
lite hårdare på sådana problem.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Vi har n kvadrat till vänster, n
kvadrat i mitten, och n

1104
00:41:57,970 --> 00:41:59,400
log n till höger.

1105
00:41:59,400 --> 00:42:00,590
Så det är ditt riktiga cliffhanger.

1106
00:42:00,590 --> 00:42:02,040
Vi ses på måndag.

1107
00:42:02,040 --> 00:42:05,163
>> [Applåder]