1
00:00:00,000 --> 00:00:11,100
>> [Glazba svira]

2
00:00:11,100 --> 00:00:11,490
>> David J. Malan: U redu.

3
00:00:11,490 --> 00:00:12,170
Dakle, dobrodošao natrag.

4
00:00:12,170 --> 00:00:15,180
Ovo CS50, a je
Kraj tjedna tri.

5
00:00:15,180 --> 00:00:17,770
>> Dakle, sjećam se u proteklih nekoliko tjedana,
smo provodili dosta

6
00:00:17,770 --> 00:00:20,820
Vrijeme na C, na programiranju, o sintaksi.

7
00:00:20,820 --> 00:00:24,680
I to je sasvim normalno, ako si još uvijek
bori s Problem Set 2, kako bi se

8
00:00:24,680 --> 00:00:25,950
lupanje glavom o zid.

9
00:00:25,950 --> 00:00:28,310
To je zagonetan izgleda poruka o pogrešci
i greške koje ste

10
00:00:28,310 --> 00:00:29,220
Ne mogu sasvim loviti.

11
00:00:29,220 --> 00:00:32,310
Zato, budite uvjereni, da je u samo
nekoliko tjedana da li ću se osvrnuti na

12
00:00:32,310 --> 00:00:35,930
stvari poput Cezara, i [? V-genair,?]
možda čak Crack, a

13
00:00:35,930 --> 00:00:40,050
shvatite koliko daleko ste došli
u kratkom vremenskom razdoblju.

14
00:00:40,050 --> 00:00:43,670
Dakle, ako je to neka utjeha,
drži se za sada.

15
00:00:43,670 --> 00:00:46,610
>> Danas, međutim, možemo početi tranziciju
na višu razinu stvari.

16
00:00:46,610 --> 00:00:49,820
I mi početi uzimati zdravo za gotovo da je
ti dečki znaju kako programirati, ili na

17
00:00:49,820 --> 00:00:52,090
Najmanje počeci
Ta razina.

18
00:00:52,090 --> 00:00:56,520
A počet ćemo razmisliti o tome kako možemo
ići o izradi programa više

19
00:00:56,520 --> 00:00:57,440
učinkovito.

20
00:00:57,440 --> 00:01:01,090
Kako možemo ići o optimizaciji
Učinkovitost naših algoritama i

21
00:01:01,090 --> 00:01:03,110
općenito rješavanjem više
zanimljivi problemi.

22
00:01:03,110 --> 00:01:06,850
I počinju da uzimaju zdravo za gotovo da je,
ako smo htjeli, mogli smo kod do bilo

23
00:01:06,850 --> 00:01:08,350
od primjera imamo na umu.

24
00:01:08,350 --> 00:01:11,430
Tako danas, mi ne dirajte tipkovnicu
za bilo koji oblik koda.

25
00:01:11,430 --> 00:01:15,150
To će biti puno viša razina, a
u konačnici, o rješavanju problema.

26
00:01:15,150 --> 00:01:20,490
>> Dakle, doći do te točke, neka mi predloži
da slijedećih sedam

27
00:01:20,490 --> 00:01:24,290
pravokutnici predstavljaju sedam vrata, iza
koja se cijela hrpa

28
00:01:24,290 --> 00:01:26,340
brojeva, među kojima je broj 50.

29
00:01:26,340 --> 00:01:30,470
Dopustite mi da ovo projekt na ovu
Zaslon i ovdje.

30
00:01:30,470 --> 00:01:36,770
I predložiti da trebamo dobrovoljca u
pomoći mi pronaći broj ispred

31
00:01:36,770 --> 00:01:38,140
Internet ovdje vidjeti.

32
00:01:38,140 --> 00:01:40,755
Dođi gore, u ružičastom.

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

34
00:01:43,050 --> 00:01:43,930
Koje je tvoje ime?

35
00:01:43,930 --> 00:01:44,850
>> JENNIFER: [nečujno]

36
00:01:44,850 --> 00:01:45,170
>> David J. Malan: Žao mi?

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
U redu, Jennifer.

40
00:01:46,980 --> 00:01:47,630
Drago mi je.

41
00:01:47,630 --> 00:01:48,370
Dođi gore.

42
00:01:48,370 --> 00:01:52,430
Dakle, to ovdje su sedam vrata, a što
Volio bih da to učiniti za nas ovdje,

43
00:01:52,430 --> 00:01:56,560
pred svim svojim kolegama,
se nalaze nam broj, 50.

44
00:01:56,560 --> 00:02:00,860
Kako pronaći broj, možete zaviriti iza
bilo koji od ovih vrata jednostavnim dodirom

45
00:02:00,860 --> 00:02:03,030
na jednom od vrata, i to
će otkriti svoj broj.

46
00:02:03,030 --> 00:02:06,080
I neka je vidjeti kako brzo ste
možete nas naći broj, 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
Lijepo učinili.

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

55
00:02:18,040 --> 00:02:19,906
Aplauz za Jennifer.

56
00:02:19,906 --> 00:02:21,530
>> [PLJESAK]

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

58
00:02:22,320 --> 00:02:25,254
Dakle, ono što je vaša strategija za
pronalaženje broja, 50?

59
00:02:25,254 --> 00:02:27,222
>> JENNIFER: Hm, mislio sam da možda ako -

60
00:02:27,222 --> 00:02:27,714
[Nečujno]

61
00:02:27,714 --> 00:02:28,206
>> David J. Malan: Oh.

62
00:02:28,206 --> 00:02:29,630
Daj ga jedan drugi.

63
00:02:29,630 --> 00:02:32,420
Tako je vaša strategija za
pronalaženje broja, 50?

64
00:02:32,420 --> 00:02:34,760
>> JENNIFER: Pa sam početi na
počinju vidjeti što prvi broj

65
00:02:34,760 --> 00:02:38,590
je, a onda sam pomislio, možda, ako
oni su razvrstani, ja ću samo držati

66
00:02:38,590 --> 00:02:39,970
prislušni viši?

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

68
00:02:40,140 --> 00:02:42,910
I mi se čini da su našli
da je to slučaj.

69
00:02:42,910 --> 00:02:45,670
Iako, neka je guliti natrag slojeve
Samo malo, a želite ići

70
00:02:45,670 --> 00:02:47,640
naprijed i otkriti druge vrata
mogli ste odabrali?

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

72
00:02:50,400 --> 00:02:51,712
>> JENNIFER: O, Bože.

73
00:02:51,712 --> 00:02:53,128
>> David J. Malan: Ah.

74
00:02:53,128 --> 00:02:54,280
>> JENNIFER: Tako sam se posrećilo.

75
00:02:54,280 --> 00:02:55,270
>> David J. Malan: Znači li se posrećilo.

76
00:02:55,270 --> 00:02:55,710
U redu.

77
00:02:55,710 --> 00:02:56,795
Dakle, nije loše.

78
00:02:56,795 --> 00:02:58,750
No, to je zanimljiva
Uvid, zar ne?

79
00:02:58,750 --> 00:03:01,870
Ako ste pretpostavili, a vi je dobiti,
Doista, malo sretan tamo.

80
00:03:01,870 --> 00:03:05,350
Ali ako pretpostavlja da su brojevi bili su
razvrstani, može li se preciznije

81
00:03:05,350 --> 00:03:08,750
kako to utječe
vaše ponašanje?

82
00:03:08,750 --> 00:03:11,715
>> JENNIFER: Pa, ako su razvrstani, sam
Mislio najmanjih do najvećih.

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

84
00:03:11,970 --> 00:03:15,260
>> JENNIFER: Ili ako je to zavrsilo se
stvarno velik, a zatim po veličini na najmanji.

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

86
00:03:15,540 --> 00:03:18,170
Dakle, najveće do najmanje, ili
Najmanji do najvećeg.

87
00:03:18,170 --> 00:03:21,990
No, dopustite mi predlažemo, pretpostavimo da je
dobivši nesretni, a pretpostavljam da su oni

88
00:03:21,990 --> 00:03:26,840
nisu, u stvari, razvrstani, koliko
ta vrata možda ste morali zaviriti

89
00:03:26,840 --> 00:03:28,590
iza u tom najgorem slučaju?

90
00:03:28,590 --> 00:03:29,860
>> JENNIFER: Sve od njih.

91
00:03:29,860 --> 00:03:30,420
>> David J. Malan: Sve od njih.

92
00:03:30,420 --> 00:03:31,740
Tako ćemo generalizirati da kao n.

93
00:03:31,740 --> 00:03:34,790
Tu se dogoditi da bude 7, ali neka se više
općenito reći postoji n vrata na

94
00:03:34,790 --> 00:03:35,650
Zaslon ovdje.

95
00:03:35,650 --> 00:03:40,110
Dakle, u najgorem slučaju, da bi se
gledati iza sedam vrata, ili n vrata.

96
00:03:40,110 --> 00:03:44,140
I tako ovo je stvarno, to je malo
Sreća i danas, ali to je stvarno linearno

97
00:03:44,140 --> 00:03:46,440
Algoritam sorti, iako
bili vrsta preskakanja okolo.

98
00:03:46,440 --> 00:03:47,080
Je li to pošteno?

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

100
00:03:47,500 --> 00:03:50,000
>> David J. Malan: Pa, da vidim ako je vaš
strategija mijenja se ako sam pokrenuti da

101
00:03:50,000 --> 00:03:52,190
Naš drugi primjer ovdje s
7 različitih vrata.

102
00:03:52,190 --> 00:03:55,240
Iste brojeve, ali to
Vrijeme su razvrstani.

103
00:03:55,240 --> 00:03:58,350
Koja je vaša strategija ovdje će biti,
pokušavaju staviti izvan vašeg uma ono

104
00:03:58,350 --> 00:03:59,310
ostali su brojevi -

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

106
00:03:59,930 --> 00:04:02,290
>> David J. Malan: - ranije?

107
00:04:02,290 --> 00:04:03,180
>> JENNIFER: Počnimo
sa prvom.

108
00:04:03,180 --> 00:04:03,540
>> David J. Malan: U redu.

109
00:04:03,540 --> 00:04:05,190
Počnite s prvom.

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

111
00:04:05,960 --> 00:04:08,810
Sada, gdje ćete ići, i zašto?

112
00:04:08,810 --> 00:04:10,040
>> JENNIFER: 4 je stvarno mali.

113
00:04:10,040 --> 00:04:12,500
Dakle, ako oni su vrsta možda i najmanji
Najveći se, što bi trebao

114
00:04:12,500 --> 00:04:13,290
se dva puta, i -.

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

116
00:04:13,670 --> 00:04:15,990
Da vidimo, što mislite?

117
00:04:15,990 --> 00:04:19,050
>> JENNIFER: Pokušajte zadnji.

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

119
00:04:19,500 --> 00:04:20,880
>> David J. Malan: Vrlo lijepo učinio.

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

121
00:04:21,860 --> 00:04:23,010
>> [PLJESAK]

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

123
00:04:24,310 --> 00:04:26,790
Dakle, što zapravo radiš
strašno, jer si

124
00:04:26,790 --> 00:04:27,700
to radi jako dobro.

125
00:04:27,700 --> 00:04:31,150
Koji nas ostavlja u stanju
napraviti određene točke.

126
00:04:31,150 --> 00:04:32,565
Tako ćemo pokušati vratiti ovdje.

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

128
00:04:34,560 --> 00:04:35,980
>> David J. Malan: Vrlo dobro
učinili, svejedno.

129
00:04:35,980 --> 00:04:39,060
Tako da je počeo od početka,
vidjeli ste da je 4, onda

130
00:04:39,060 --> 00:04:40,240
premještena u kraju.

131
00:04:40,240 --> 00:04:42,320
Ali pretpostavimo da nije posreći
postoji, i pretpostavimo 50

132
00:04:42,320 --> 00:04:42,890
bio je negdje drugdje.

133
00:04:42,890 --> 00:04:46,190
Koji vam je treći korak bio?

134
00:04:46,190 --> 00:04:47,680
>> JENNIFER: Vratite se na početak.

135
00:04:47,680 --> 00:04:48,320
>> David J. Malan: Vratite
na početak.

136
00:04:48,320 --> 00:04:51,320
U redu, tako da bi ste dotaknu
ova vrata, što je 8.

137
00:04:51,320 --> 00:04:51,660
U redu.

138
00:04:51,660 --> 00:04:52,650
Dakle, to nije 50.

139
00:04:52,650 --> 00:04:55,380
Gdje bi ste gledali sljedeće?

140
00:04:55,380 --> 00:04:56,720
>> JENNIFER: Ako nisam
znaju oni razvrstani.

141
00:04:56,720 --> 00:04:57,005
>> David J. Malan: Točno.

142
00:04:57,005 --> 00:04:58,490
Pa, ako nisi znao
su razvrstani -

143
00:04:58,490 --> 00:04:58,700
>> JENNIFER: Oh, znao, da.

144
00:04:58,700 --> 00:05:00,910
>> David J. Malan: - ali nije
znam gdje je još 50?

145
00:05:00,910 --> 00:05:01,785
>> JENNIFER: Samo nastavi.

146
00:05:01,785 --> 00:05:02,130
>> David J. Malan: U redu.

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

148
00:05:02,520 --> 00:05:03,800
Imajte ide.

149
00:05:03,800 --> 00:05:05,270
OK, da mogu raditi.

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

151
00:05:05,610 --> 00:05:07,210
>> David J. Malan: Sada, ako ste samo
će zadržati ide, ono što je vaš

152
00:05:07,210 --> 00:05:09,680
Algoritam devolving podlogom u.

153
00:05:09,680 --> 00:05:10,740
>> JENNIFER: linearno -.

154
00:05:10,740 --> 00:05:11,820
>> David J. Malan: To je vrsta linearne.

155
00:05:11,820 --> 00:05:13,480
No, dopustite mi da predloži, neka
ja mu na licu mjesta.

156
00:05:13,480 --> 00:05:14,900
Dopustite mi da osvježite stranicu.

157
00:05:14,900 --> 00:05:17,120
Isti broj, isti raspored,
ista vrata.

158
00:05:17,120 --> 00:05:21,350
Ali sjetim tog prvog dana u
Klasa kad smo poderao telefonski imenik u

159
00:05:21,350 --> 00:05:25,480
polovice, vrsta, a što je
Naša strategija postoji?

160
00:05:25,480 --> 00:05:26,450
>> JENNIFER: Start na sredini.

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

162
00:05:26,690 --> 00:05:27,610
Dakle, početi na sredini.

163
00:05:27,610 --> 00:05:28,790
Dakle, idemo naprijed i da simuliraju.

164
00:05:28,790 --> 00:05:30,720
Start na sredini,
otkrivajući ta vrata.

165
00:05:30,720 --> 00:05:31,660
Dakle, broj 16.

166
00:05:31,660 --> 00:05:35,290
Pa što bi jak čovjek učinio,
koji je poderao telefonskog imenika na pola,

167
00:05:35,290 --> 00:05:38,450
doći do sljedeću pogodak?

168
00:05:38,450 --> 00:05:39,400
>> JENNIFER: Idi u ovom polugodištu.

169
00:05:39,400 --> 00:05:41,700
>> David J. Malan: A zašto udesno?

170
00:05:41,700 --> 00:05:43,900
>> JENNIFER: Ako su najmanja vrsta
do najvećih, tada 50 bi trebao biti

171
00:05:43,900 --> 00:05:44,720
u tom kraju.

172
00:05:44,720 --> 00:05:44,920
>> David J. Malan: Dobro.

173
00:05:44,920 --> 00:05:45,390
Totalno razumna.

174
00:05:45,390 --> 00:05:48,380
Dakle, poput telefonskog imenika, idete
pravo, za razliku od lijevo, ali ovdje

175
00:05:48,380 --> 00:05:49,500
je ključ takeaway.

176
00:05:49,500 --> 00:05:53,930
Sada možete baciti, ili se otkinuti,
polovica tog problema, ostavljajući vas ne

177
00:05:53,930 --> 00:05:55,970
sa 7 vrata, ali stvarno sa samo tri.

178
00:05:55,970 --> 00:05:57,870
Koji je otprilike polovica
Veličina problema.

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

180
00:05:58,350 --> 00:06:01,890
Pa sad što bi
učinjeno nakon što desno?

181
00:06:01,890 --> 00:06:05,870
>> JENNIFER: Dakle, 16 je još uvijek prilično mali,
u odnosu na 50, pa možda ću pokušati,

182
00:06:05,870 --> 00:06:06,700
kao što je, ovaj jedan.

183
00:06:06,700 --> 00:06:07,890
>> David J. Malan: U redu.

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

185
00:06:08,720 --> 00:06:10,830
U redu, tako da sada Koja je tvoja
Instinkt ti govori?

186
00:06:10,830 --> 00:06:12,100
>> JENNIFER: Ja mogu baciti
to i onda samo -

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

188
00:06:12,360 --> 00:06:14,212
Dobro, možete baciti
lijeva polovica postoji.

189
00:06:14,212 --> 00:06:14,890
>> JENNIFER: - pokupiti ovaj jedan.

190
00:06:14,890 --> 00:06:15,530
>> David J. Malan: I u pravu.

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

192
00:06:15,760 --> 00:06:17,820
>> David J. Malan: Dakle, iako je teško
vidjeti možda, kad postoji samo

193
00:06:17,820 --> 00:06:21,320
7 vrata, razmišljati o tome, sada,
konzistentnost

194
00:06:21,320 --> 00:06:22,620
Algoritam samo primjenjivati.

195
00:06:22,620 --> 00:06:24,510
U prethodnom slučaju, jesi
posreći, što je super.

196
00:06:24,510 --> 00:06:26,540
Ali jesi koristiti heuristički,
Ja bih rekao.

197
00:06:26,540 --> 00:06:29,150
Možete koristiti neku vrstu svoje instinkte, a
znajući to riješeno, ako je lijepa

198
00:06:29,150 --> 00:06:31,600
mali na početku, očito, mi smo
Moram ići više u desno.

199
00:06:31,600 --> 00:06:34,990
No, u nekom smislu, imaš sreće,
jer možda je to bio broj 100,

200
00:06:34,990 --> 00:06:36,220
a možda je 50 više u sredini.

201
00:06:36,220 --> 00:06:37,910
Možda je čak 50 ovamo.

202
00:06:37,910 --> 00:06:40,960
>> No, ono što je malo drugačije
ovaj put bio, što nije ista stvar

203
00:06:40,960 --> 00:06:42,150
opet i opet.

204
00:06:42,150 --> 00:06:45,310
I ja bih rekao da je ono što ste upravo
je, doduše pod utjecajem telefonu

205
00:06:45,310 --> 00:06:48,100
Knjiga primjer, nešto mnogo
više algoritamski, i još mnogo

206
00:06:48,100 --> 00:06:49,930
manje posebna proučavao.

207
00:06:49,930 --> 00:06:51,620
Mnogo manje instinktivno.

208
00:06:51,620 --> 00:06:57,160
Dakle, na kraju dana, kako bi se
vam opisati učinkovitost

209
00:06:57,160 --> 00:07:00,530
Prvi algoritam, gdje je otišao
slijeva nadesno, u odnosu na

210
00:07:00,530 --> 00:07:03,430
Drugi algoritam ovdje?

211
00:07:03,430 --> 00:07:06,460
>> JENNIFER: Ovo treba, kao što je, možda
prepoloviti vrijeme, ili čak i više, da.

212
00:07:06,460 --> 00:07:07,320
>> David J. Malan: OK, možda čak i više.

213
00:07:07,320 --> 00:07:10,150
Idemo gurnuti malo teže na to.

214
00:07:10,150 --> 00:07:13,030
Što je stvarno, ako nastavljamo ovaj
Logika, svakako prepolovljena

215
00:07:13,030 --> 00:07:15,830
vrijeme rada s ovom drugom algoritma
bacajući daleko polovicu

216
00:07:15,830 --> 00:07:18,470
brojeve, ali ono što smo radili na sljedeći
iteracija, kada je Jennifer otkrila

217
00:07:18,470 --> 00:07:20,615
drugi broj?

218
00:07:20,615 --> 00:07:22,830
>> Mi prepolovili broj vrata ponovno.

219
00:07:22,830 --> 00:07:25,270
I onda što smo učinili nakon toga, ako je
bilo je više vrata da se igraju s?

220
00:07:25,270 --> 00:07:27,520
Mi bi ih prepoloviti, i opet,
i opet, i opet.

221
00:07:27,520 --> 00:07:30,420
A to je baš kao i vama svima
stojeći u prvom tjednu

222
00:07:30,420 --> 00:07:33,000
klase, polovica što je sjeo, poluvrijeme
od vas sjeo, pola tebi

223
00:07:33,000 --> 00:07:35,440
sjeo, dok se jedan usamljeni
Duša je stajao.

224
00:07:35,440 --> 00:07:39,050
A mi je rekao da je vrijeme rada
da je broj koraka to je bio

225
00:07:39,050 --> 00:07:40,430
po nalogu što?

226
00:07:40,430 --> 00:07:41,230
>> ZVUČNI 1: [nečujno]

227
00:07:41,230 --> 00:07:43,970
>> David J. Malan: Dakle log baze 2 n,
ili jednostavno više jednostavno, prijavite n.

228
00:07:43,970 --> 00:07:45,060
Tako nešto logaritamska.

229
00:07:45,060 --> 00:07:48,380
A graf nije bio ravna crta
da je upravo dobio gore i gore, bilo je

230
00:07:48,380 --> 00:07:52,490
Ova zanimljiva krivulja koja nije
dobiti tako loše tijekom vremena.

231
00:07:52,490 --> 00:07:53,910
Tako ćemo zadržati na ovoj ideji.

232
00:07:53,910 --> 00:07:54,690
Neka je hvala Jennifer.

233
00:07:54,690 --> 00:07:56,150
Hvala što ste došli na gore.

234
00:07:56,150 --> 00:07:57,400
I, jedna sek.

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

236
00:08:00,170 --> 00:08:02,925
Nema stolne lampe danas, ali mi
nemam CS50 stres loptice.

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

238
00:08:03,420 --> 00:08:04,410
>> David J. Malan: U redu, ovdje.

239
00:08:04,410 --> 00:08:06,545
Hvala izvrgava
Stres se ovdje.

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

241
00:08:07,350 --> 00:08:10,620
Dakle, neka je vidjeti ako ne možemo sada
formalizirati to malo više.

242
00:08:10,620 --> 00:08:14,820
Pa opet, ono što smo upravo učinio je
u biti ista stvar kao što smo učinili

243
00:08:14,820 --> 00:08:16,660
u tom prvom tjednu.

244
00:08:16,660 --> 00:08:23,780
No, umjesto da kraj sa samo linearno
algoritam, koji mi je prikazano

245
00:08:23,780 --> 00:08:27,210
prije što je ovaj ravnoj liniji,
pri čemu, ako smo stavili još jednu vrata

246
00:08:27,210 --> 00:08:29,610
Zaslon, a zatim bi se Jennifer
su morali gledati, potencijalno,

247
00:08:29,610 --> 00:08:30,600
Iza još jednog vrata.

248
00:08:30,600 --> 00:08:33,490
Ako stavimo još dva vrata, ona može imati
gledati iza još dva vrata.

249
00:08:33,490 --> 00:08:35,990
>> I tako, bilo je to linearno
odnos između veličine

250
00:08:35,990 --> 00:08:39,059
Problem na, recimo, x-osi, a
Vrijeme koje je potrebno da

251
00:08:39,059 --> 00:08:40,440
riješiti na y.

252
00:08:40,440 --> 00:08:43,330
Ali slika sam je aludirajući
ranije je to zelena linija.

253
00:08:43,330 --> 00:08:45,970
Zelena namjerno, jer
to samo osjećao bolje.

254
00:08:45,970 --> 00:08:49,790
U teoriji, algoritam, kad smo to učinili
s telefonskom imeniku, kad smo to učinili

255
00:08:49,790 --> 00:08:52,420
s vama računajući jedni druge, i
u drugom slučaju, kada je Jennifer samo

256
00:08:52,420 --> 00:08:55,250
Uspjeli ovdje gore, to je neka vrsta
od temelja bolje.

257
00:08:55,250 --> 00:08:57,180
Budući da to nije bila samo dva puta brže.

258
00:08:57,180 --> 00:08:58,870
Nije bilo čak četiri puta brže.

259
00:08:58,870 --> 00:09:03,290
To je u potpunosti ovisi o tome što
veličina ulaza je, kako mnogi

260
00:09:03,290 --> 00:09:05,220
korake koji je u konačnici uzeo.

261
00:09:05,220 --> 00:09:08,040
>> I tako ova jednostavna ideja da smo svi uzeo
zdravo za gotovo s telefonskom imeniku,

262
00:09:08,040 --> 00:09:10,200
može se isto tako primijeniti
za ovako nešto.

263
00:09:10,200 --> 00:09:12,380
A to bi moglo biti više ležerno
poznat kao, kao što ste mogli

264
00:09:12,380 --> 00:09:13,940
zamislite, podijeli pa vladaj.

265
00:09:13,940 --> 00:09:16,390
Nije za razliku od onoga što smo učinili, naravno,
s telefonskom imeniku.

266
00:09:16,390 --> 00:09:18,300
>> Ali pseudocode, podsjetimo, bio je to.

267
00:09:18,300 --> 00:09:21,800
Dakle, nećemo to učiniti opet, ali sjećam
da je prvi tjedan, sve nas je ustao

268
00:09:21,800 --> 00:09:25,140
a onda polovica vas sjeo, polovica
da sjedne, polovica vas sjeo.

269
00:09:25,140 --> 00:09:29,280
Taj algoritam je implementiran u
bitni za varanje način, da je

270
00:09:29,280 --> 00:09:32,870
nije bio samo jedan od mene brojanje,
temelja, učinkovitije.

271
00:09:32,870 --> 00:09:35,830
U tom slučaju, bio sam uložio
sekundarni izvor.

272
00:09:35,830 --> 00:09:39,470
Na neki način, više procesora, više mozak,
više pametnih ljudi u

273
00:09:39,470 --> 00:09:42,740
Soba su mi pomogli doći na nešto
linearno na nešto

274
00:09:42,740 --> 00:09:45,190
logaritamska, od nečega
red da nešto zeleno.

275
00:09:45,190 --> 00:09:48,650
>> No, u ovom slučaju, Jennifer sami mogu
bitno poboljšati

276
00:09:48,650 --> 00:09:52,370
izvedba njezina prvog algoritma strane,
opet, samo razmišljam malo teže.

277
00:09:52,370 --> 00:09:56,650
I sada, kada dođe vrijeme za provedbu
te stvari, figuring out

278
00:09:56,650 --> 00:10:00,670
ono linija koda možete pisati kao
da ih možete ponoviti i

279
00:10:00,670 --> 00:10:03,350
opet, i opet, vrsta
u petlje način.

280
00:10:03,350 --> 00:10:06,370
Zato što ne ideš imati
luksuz, kao što je Jennifer u početku,

281
00:10:06,370 --> 00:10:10,460
Samo imaju cijelu hrpu oklijevanja i reći,
hmm, ako je ovo prvi broj je 4,

282
00:10:10,460 --> 00:10:11,800
neka mi skočiti sve do kraja.

283
00:10:11,800 --> 00:10:14,180
Ooh, ako taj broj je prevelika,
dopustite mi da se presele natrag proizvoljno

284
00:10:14,180 --> 00:10:15,220
na drugi element.

285
00:10:15,220 --> 00:10:18,210
Naći ćete da će to biti puno
teže formalizirati ono što mi ljudi

286
00:10:18,210 --> 00:10:21,270
uzeti zdravo za gotovo, kao vrlo razuman
heuristika, ali računalo je samo

287
00:10:21,270 --> 00:10:23,260
će učiniti ono što vam reći da to učinite.

288
00:10:23,260 --> 00:10:25,280
>> Sada to ima vrlo zanimljiv
implikacije.

289
00:10:25,280 --> 00:10:29,950
Ovaj graf je vrsta značilo svojevrsno
preplaviti vizualno, ali obavijest, u kojoj

290
00:10:29,950 --> 00:10:32,230
je ravna crta u ovom grafu?

291
00:10:32,230 --> 00:10:35,330
Gdje je linearni graf
koje zovemo n?

292
00:10:35,330 --> 00:10:37,580
Pa, to je vrsta prema dnu
ove slike, zar ne?

293
00:10:37,580 --> 00:10:40,500
Dakle, sve što smo učinili je da smo vrsta
zumirana se na x-osi i

294
00:10:40,500 --> 00:10:44,780
y-os pokušati dobiti osjećaj za ono što
druge vrste krivulja izgledati.

295
00:10:44,780 --> 00:10:47,760
>> I specifičnosti matematička
Izrazi danas neće biti važno, tako

296
00:10:47,760 --> 00:10:52,440
mnogo, ali primijetiti da postoji puno
algoritama koji su daleko lošiji od

297
00:10:52,440 --> 00:10:53,470
nešto što je linearno.

298
00:10:53,470 --> 00:10:55,410
Doista, n kubu izgleda prilično loše.

299
00:10:55,410 --> 00:10:58,400
2 do n izgleda prilično loše.
n na kvadrat izgleda prilično loše.

300
00:10:58,400 --> 00:11:01,630
Pa ćemo vidjeti što neki od onih
Možda u stvarnosti danas.

301
00:11:01,630 --> 00:11:05,430
I log n ne osjećam tako loše, ali
bolje od n je baza 2 log n.

302
00:11:05,430 --> 00:11:08,080
Ali, znate, to bi bilo još
više iznenađujuće ako je Jennifer, ili ako smo mi,

303
00:11:08,080 --> 00:11:12,910
da je prvi tjedan, je došao gore sa
nešto što je dnevnik log n.

304
00:11:12,910 --> 00:11:15,880
>> Dakle, drugim riječima, postoji cijela ova
Raspon mogućih rješenja

305
00:11:15,880 --> 00:11:18,570
problemima, ali čak i ovdje, obavijest
što će se dogoditi.

306
00:11:18,570 --> 00:11:22,910
Kad sam udaljavanje, koja je od ovih krivulja
će dokazati da bude apsolutna

307
00:11:22,910 --> 00:11:26,630
Najgore od one na zaslonu sada?

308
00:11:26,630 --> 00:11:28,680
Dakle, n kubu izgleda prilično
loše u ovom trenutku.

309
00:11:28,680 --> 00:11:32,470
Ali, ako smo smanjili i vidjeti više
x i y-os, tko će

310
00:11:32,470 --> 00:11:34,550
dominiraju u konačnici?

311
00:11:34,550 --> 00:11:37,120
Dakle, to je zapravo ispada da se dvije
n, a možete to shvatiti samo

312
00:11:37,120 --> 00:11:39,990
uključivanjem u nekim sve veći
brojeva, i vidjet ćete da je 2 do

313
00:11:39,990 --> 00:11:42,070
n, dapače, dobiva veći mnogo brže.

314
00:11:42,070 --> 00:11:45,530
Ako smo stvarno smanjivanje, a dvije se
n algoritam apsolutno sranje.

315
00:11:45,530 --> 00:11:48,170
Mislim da će ovo potrajati
vrlo malo vremena za

316
00:11:48,170 --> 00:11:49,460
Računalo gubitaka kroz.

317
00:11:49,460 --> 00:11:52,500
>> No, vidjet ćete s vremenom, pogotovo
budućih problema seta, pa čak i

318
00:11:52,500 --> 00:11:55,600
Konačni projekti, vaši podatci
set dobiva veliki, u redu?

319
00:11:55,600 --> 00:11:58,300
Čak iu prvoj verziji Facebooka,
kao i broj prijatelja, a

320
00:11:58,300 --> 00:12:01,840
Broj registriranih korisnika dobio veliki,
možete sortirati od telefon, i

321
00:12:01,840 --> 00:12:05,530
provesti nešto s linearnim pretraživanje,
ili vrlo jednostavan za sortiranje

322
00:12:05,530 --> 00:12:07,030
algoritam, kao što ćemo vidjeti danas.

323
00:12:07,030 --> 00:12:09,280
Morate početi razmišljati teže
i teže o tim problemima.

324
00:12:09,280 --> 00:12:12,070
A vrste problema mjestima kao što su
Facebook i Google i Microsoft,

325
00:12:12,070 --> 00:12:16,350
i drugi rade na upravo tih
vrsta podataka velikom vrstom pitanja

326
00:12:16,350 --> 00:12:18,530
sve više ovih dana.

327
00:12:18,530 --> 00:12:18,900
>> U redu.

328
00:12:18,900 --> 00:12:23,800
Tako Jennifer uspjeh u tom trenutku
Algoritam, iskreno, ona je nevjerojatno

329
00:12:23,800 --> 00:12:26,110
i prvi put, ali neka je
napisati što se zove sreća, tako da smo

330
00:12:26,110 --> 00:12:27,000
Možete napraviti ovu točku.

331
00:12:27,000 --> 00:12:30,970
U drugom slučaju, ona je iskoristio
algoritam koji je ponovio i opet

332
00:12:30,970 --> 00:12:34,670
opet, ali je uzeo zdravo za gotovo
sigurno pretpostavka da smo dopustili

333
00:12:34,670 --> 00:12:39,370
joj, ali ona iskorištava neke pojedinosti
Drugi put da ona nije imala

334
00:12:39,370 --> 00:12:39,840
prvi put.

335
00:12:39,840 --> 00:12:41,800
Koji je što?

336
00:12:41,800 --> 00:12:43,050
>> Taj popis je riješeno.

337
00:12:43,050 --> 00:12:46,350
Dakle, čim je popis sortiran, mi
Jennifer tvrdi da je u mogućnosti to učiniti

338
00:12:46,350 --> 00:12:47,480
bitno bolje.

339
00:12:47,480 --> 00:12:51,450
7 vrata, da, nije li to zanimljivo,
, ali ga pretpostavljam da smo 7 milijuna vrata.

340
00:12:51,450 --> 00:12:54,080
Prijavite n definitivno ide
obaviti još mnogo, mnogo

341
00:12:54,080 --> 00:12:55,610
brže u dugoj vožnji.

342
00:12:55,610 --> 00:12:58,880
Ali ona je morala imati
Vrata sortirani prema njoj.

343
00:12:58,880 --> 00:13:02,320
Sada sam uzeo slobodu da radi
Unaprijed na zaslonu računala

344
00:13:02,320 --> 00:13:05,160
ovdje, ali pretpostavljam da je Jennifer
to morao sebe?

345
00:13:05,160 --> 00:13:10,120
Pretpostavimo da su vrata u pitanju
zastupljeni podaci u bazi podataka, ili

346
00:13:10,120 --> 00:13:14,260
Prijatelji registrirane za Facebook, ili
Bilo koje web stranice na internetu koje

347
00:13:14,260 --> 00:13:16,880
razne web stranice možda ćete morati
na indeksu ili tražiti više.

348
00:13:16,880 --> 00:13:20,940
>> Pretpostavimo da ste upravo imali sirovih podataka
postavljanje i to je lijevo za vas, ili za

349
00:13:20,940 --> 00:13:23,010
Jennifer to učiniti sortiranje?

350
00:13:23,010 --> 00:13:26,950
To je, naprotiv, zahtijeva da smo odgovor
Pitanje, dakle, koliko vremena

351
00:13:26,950 --> 00:13:31,080
bi uzeli Jennifer, ili čak i ja,
sortirati one brojeve unaprijed, tako

352
00:13:31,080 --> 00:13:32,680
da bi ona mogla iskoristiti to?

353
00:13:32,680 --> 00:13:32,880
Točno?

354
00:13:32,880 --> 00:13:36,620
Zbog implikacija, naravno,
ako to traje mi dosta vremena za sortiranje

355
00:13:36,620 --> 00:13:40,800
brojevi, koji su kritički brine da vas
Možete naći broj kao 50 tako brzo,

356
00:13:40,800 --> 00:13:44,850
kao u slučaju Jennifer, ako smo više od
svladan količinu ukupnog vremena

357
00:13:44,850 --> 00:13:46,920
to je sortiranje stvari unaprijed?

358
00:13:46,920 --> 00:13:49,320
>> Tako ćemo vidjeti, ako ne možemo
bojite sliku ovdje.

359
00:13:49,320 --> 00:13:51,370
Imam cijela hrpa više stresa
loptice, ako to pomaže

360
00:13:51,370 --> 00:13:52,270
razbiti led ovdje.

361
00:13:52,270 --> 00:13:55,690
A ako ne bi smetalo, mi
potrebno sedam volontera -

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

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

364
00:13:57,240 --> 00:13:59,250
Dakle, mi ne moramo trošiti
na stol svjetiljke, čini se.

365
00:13:59,250 --> 00:13:59,690
U redu.

366
00:13:59,690 --> 00:14:01,530
Dakle, o tome vas dvoje ispred.

367
00:14:01,530 --> 00:14:04,160
Kako vam dva dečki u leđa.

368
00:14:04,160 --> 00:14:04,870
Dakle, to je četvrta.

369
00:14:04,870 --> 00:14:09,890
Kako vam se ispred
pet, šest i sedam.

370
00:14:09,890 --> 00:14:10,320
Točno tamo.

371
00:14:10,320 --> 00:14:13,260
Vaš prijatelj vas je istaknuo,
tako da ćete dobiti nagradu.

372
00:14:13,260 --> 00:14:13,700
>> U redu.

373
00:14:13,700 --> 00:14:14,410
Dođi gore.

374
00:14:14,410 --> 00:14:17,120
A zašto ne bismo imati što
dečki dolaze ovamo.

375
00:14:17,120 --> 00:14:18,960
Ja ću vam dati svaki broj.

376
00:14:18,960 --> 00:14:22,150
I ići naprijed i sami organizirati
identično onome što je

377
00:14:22,150 --> 00:14:25,180
prikazan na zaslonu.

378
00:14:25,180 --> 00:14:26,530
>> [Pridodati glasovima]

379
00:14:26,530 --> 00:14:28,160
>> David J. Malan: OOP, ispričavam se.

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

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

382
00:14:32,180 --> 00:14:32,750
Pa, ovdje mi ići.

383
00:14:32,750 --> 00:14:34,180
Broj pet.

384
00:14:34,180 --> 00:14:35,136
Broj šest.

385
00:14:35,136 --> 00:14:37,770
Jedan, dva, tri, četiri,
pet, šest, sedam.

386
00:14:37,770 --> 00:14:39,410
Oh, ovo je nezgodno.

387
00:14:39,410 --> 00:14:41,210
>> ZVUČNI 2: Ja ću samo dobiti -.

388
00:14:41,210 --> 00:14:41,900
>> David J. Malan: Dobar posao.

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

390
00:14:43,130 --> 00:14:44,611
Hvala na sudjelovanju.

391
00:14:44,611 --> 00:14:47,200
>> [PLJESAK]

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

393
00:14:48,580 --> 00:14:48,860
U redu.

394
00:14:48,860 --> 00:14:51,970
Dakle, imamo četiri, dva, šest,
jedan, tri, sedam, pet.

395
00:14:51,970 --> 00:14:56,010
Usavršiti tako da imamo sedam volontera
ovdje koji su jednaki u širini

396
00:14:56,010 --> 00:14:57,430
Niz koju igramo
s ranije.

397
00:14:57,430 --> 00:14:59,470
I sam izabrao sedam razloga
koja će biti samo

398
00:14:59,470 --> 00:15:00,840
povoljno u malo.

399
00:15:00,840 --> 00:15:04,400
I ja ću predložiti da se prva
Mi smo vrsta tih sedam volontera.

400
00:15:04,400 --> 00:15:06,786
Ako želite, prvo,
pozdraviti, iako.

401
00:15:06,786 --> 00:15:08,970
Budući da je ovo će biti
nespretan nekoliko minuta.

402
00:15:08,970 --> 00:15:10,370
Predstavite sebe.

403
00:15:10,370 --> 00:15:10,980
>> GRACE: Bok, ja sam Grace.

404
00:15:10,980 --> 00:15:14,190
Ja sam student u Leverett House.

405
00:15:14,190 --> 00:15:14,620
>> BRANSON: Hi.

406
00:15:14,620 --> 00:15:15,620
Ja sam Branson.

407
00:15:15,620 --> 00:15:16,920
Ja sam brucoš na vara.

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

409
00:15:19,755 --> 00:15:20,230
>> Gabe: Hi.

410
00:15:20,230 --> 00:15:21,040
Ja sam Gabe.

411
00:15:21,040 --> 00:15:22,300
Ja sam junior u Cabot.

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

413
00:15:24,826 --> 00:15:25,980
>> NEIL: Ja sam Neil.

414
00:15:25,980 --> 00:15:29,090
Ja sam brucoš na Matthews.

415
00:15:29,090 --> 00:15:29,550
>> JASON: Ja sam Jason.

416
00:15:29,550 --> 00:15:32,816
Ja sam brucoš na Greenough.

417
00:15:32,816 --> 00:15:33,700
>> MIKE: Ja sam Mike.

418
00:15:33,700 --> 00:15:37,360
Ja sam brucoš na Grays.

419
00:15:37,360 --> 00:15:37,990
>> JESS: Ja sam Jess.

420
00:15:37,990 --> 00:15:40,313
Ja sam student u Leverett.

421
00:15:40,313 --> 00:15:41,300
>> David J. Malan: Izvrsno.

422
00:15:41,300 --> 00:15:41,850
U redu.

423
00:15:41,850 --> 00:15:44,190
Pa, hvala ti za sve naše
Volonteri ovdje do sada.

424
00:15:44,190 --> 00:15:47,110
A izazov pri ruci sada ide
se riješiti tih dečki, ali onda

425
00:15:47,110 --> 00:15:50,250
ćemo morati razmišljati malo
teško o tome kako učinkovito smo zapravo

426
00:15:50,250 --> 00:15:51,110
ih sortirati.

427
00:15:51,110 --> 00:15:52,580
Dakle, neka prvi probati ovaj.

428
00:15:52,580 --> 00:15:55,970
Vi možete vidjeti jedni druge brojeve
samo stavljanjem oko uglova.

429
00:15:55,970 --> 00:15:59,380
Idi naprijed i uzeti nekoliko sekundi, a
sortiranje sebe na najmanji na

430
00:15:59,380 --> 00:16:01,240
lijevo najveći na desnoj strani.

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

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
Dobro.

435
00:16:08,030 --> 00:16:09,370
To je stvarno prokleto brzo.

436
00:16:09,370 --> 00:16:14,040
Sada netko ovdje, ono što je algoritam
da ti dečki primijeniti?

437
00:16:14,040 --> 00:16:14,900
>> ZVUČNI 1: barem u najvećoj.

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

439
00:16:15,000 --> 00:16:18,070
Najmanje se najveća je stvarno svojevrsni
Cilj, ali nisam sigurna da je to

440
00:16:18,070 --> 00:16:18,890
Stvarno algoritam.

441
00:16:18,890 --> 00:16:21,810
Najmanje se najveća ne govori
ja korak-po-korak što učiniti.

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

443
00:16:22,833 --> 00:16:24,083
>> ZVUČNI 1: [nečujno]

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
Dakle, ako vidite osobu manji od
vaš broj, a zatim premjestiti na

447
00:16:28,920 --> 00:16:29,680
Pravo na njih.

448
00:16:29,680 --> 00:16:32,800
Tako da sada je sve izraženiji,
više kao algoritam, jer

449
00:16:32,800 --> 00:16:35,410
mogu reći, ako je to, onda da.

450
00:16:35,410 --> 00:16:37,050
Tako imamo nekakav
uvjetni konstrukt.

451
00:16:37,050 --> 00:16:39,700
A ovi momci se činilo da to malo
puta, jer su neki od vas preselili malo

452
00:16:39,700 --> 00:16:40,420
od udaljenosti.

453
00:16:40,420 --> 00:16:43,410
Tako da je vjerojatno neka vrsta
petlje događa u njihovim glavama.

454
00:16:43,410 --> 00:16:44,610
>> No, pokušajmo se formalizirati to.

455
00:16:44,610 --> 00:16:47,540
Ako ti dečki mogli vratiti natrag
na ovom dogovoru.

456
00:16:47,540 --> 00:16:50,650
Idemo vidjeti ako ne možemo formalizirati to
pomalo, a onda postaviti pitanje, samo

457
00:16:50,650 --> 00:16:51,580
koliko je učinkovit je ovo?

458
00:16:51,580 --> 00:16:54,220
Naravno, kada smo to učinili sporije,
ona će se osjećati kao dobar

459
00:16:54,220 --> 00:16:57,210
algoritam, ali vidjet ćemo možemo li
stavimo prste o konkretnim koracima.

460
00:16:57,210 --> 00:16:58,670
>> Pa vas dvojica su četiri i dva.

461
00:16:58,670 --> 00:17:01,020
Ili ste točan ili netočan kako?

462
00:17:01,020 --> 00:17:01,900
Očito pogrešna.

463
00:17:01,900 --> 00:17:02,710
Tako smo zamijenili.

464
00:17:02,710 --> 00:17:05,170
Sada ću se odmaknuti
ovdje i reći, četiri do šest.

465
00:17:05,170 --> 00:17:06,240
Jesu li točna ili netočna?

466
00:17:06,240 --> 00:17:06,599
>> Gabe: Točno.

467
00:17:06,599 --> 00:17:07,180
>> David J. Malan: Točno.

468
00:17:07,180 --> 00:17:08,300
Šest i jedan?

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

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

471
00:17:09,630 --> 00:17:10,490
Dakle, to su dvije zamjene.

472
00:17:10,490 --> 00:17:11,710
Šest i tri?

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

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

475
00:17:13,000 --> 00:17:13,930
Šest do sedam?

476
00:17:13,930 --> 00:17:14,630
Izgleda dobro.

477
00:17:14,630 --> 00:17:15,396
Sedam i pet?

478
00:17:15,396 --> 00:17:16,150
>> JESS: [nečujno]

479
00:17:16,150 --> 00:17:17,089
>> David J. Malan: OK, zamijeniti.

480
00:17:17,089 --> 00:17:19,770
I razvrstani.

481
00:17:19,770 --> 00:17:19,980
U redu.

482
00:17:19,980 --> 00:17:21,440
Dakle, očito ne, zar ne?

483
00:17:21,440 --> 00:17:22,470
Tako da je više događa.

484
00:17:22,470 --> 00:17:24,920
Ali, doista, ovi momci, pa čak i
Jednostavno instinktivno.

485
00:17:24,920 --> 00:17:25,450
držati se kreće.

486
00:17:25,450 --> 00:17:27,710
Nisu samo zaustaviti, nakon što
ispraviti jedan problem.

487
00:17:27,710 --> 00:17:27,839
Dakle.

488
00:17:27,839 --> 00:17:29,390
Doista, ja ću imati
učiniti istu stvar.

489
00:17:29,390 --> 00:17:32,720
Ja ću morati izdvojiti od premotati natrag
do početka ovog problema,

490
00:17:32,720 --> 00:17:35,630
ili početak te niz
ljudi, počnimo ih zovete.

491
00:17:35,630 --> 00:17:38,366
>> I sad ono što bi moj algoritam
na drugom prolazu biti?

492
00:17:38,366 --> 00:17:39,220
>> ZVUČNI 1: Ista stvar.

493
00:17:39,220 --> 00:17:39,940
>> David J. Malan: Ista stvar.

494
00:17:39,940 --> 00:17:41,460
A to, ja počinjem se sviđa, zar ne?

495
00:17:41,460 --> 00:17:44,720
Čim možete pronaći sebe radiš
ista stvar opet i opet, to je

496
00:17:44,720 --> 00:17:47,890
sve više kao algoritam,
i manje ljudski instinkt.

497
00:17:47,890 --> 00:17:48,680
>> Pa sad, ovdje mi ići opet.

498
00:17:48,680 --> 00:17:49,870
Dvije i četiri?

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

500
00:17:50,220 --> 00:17:51,050
Četiri i jedan?

501
00:17:51,050 --> 00:17:53,380
Ah, bilo je doista neki
rade još treba učiniti.

502
00:17:53,380 --> 00:17:53,620
Za te tri?

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

504
00:17:54,572 --> 00:17:56,000
Četiri i šest?

505
00:17:56,000 --> 00:17:58,380
Šest i pet?

506
00:17:58,380 --> 00:17:59,470
Šest do sedam?

507
00:17:59,470 --> 00:18:00,970
OK, sada, učinio.

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

509
00:18:01,550 --> 00:18:02,710
Ja se moram vratiti.

510
00:18:02,710 --> 00:18:05,130
>> Pa sad, opet, mi smo to
malo više namjerno.

511
00:18:05,130 --> 00:18:08,700
I sada, postoji samo jedan mozak
izvršavanju ovaj algoritam.

512
00:18:08,700 --> 00:18:10,290
Jedan CPU, ako hoćete.

513
00:18:10,290 --> 00:18:13,090
I iskreno, to je jedini resurs
ćemo imati pristup.

514
00:18:13,090 --> 00:18:16,280
A kad smo se vratiti na tipkovnici
i imaju nešto poput C na našoj

515
00:18:16,280 --> 00:18:19,600
zbrinjavanje, možemo samo pišeš program
koji može učiniti jednu stvar u isto vrijeme.

516
00:18:19,600 --> 00:18:22,900
Dok, ovi momci maloprije, mi
iskoristio njihov kolektivni brainpower

517
00:18:22,900 --> 00:18:24,180
kao što ste vi učinili u tjednu nulu.

518
00:18:24,180 --> 00:18:24,980
Tako ćemo zadržati to.

519
00:18:24,980 --> 00:18:26,260
>> Dvije i jedna.

520
00:18:26,260 --> 00:18:26,945
Dvije i tri.

521
00:18:26,945 --> 00:18:27,460
Tri i četiri.

522
00:18:27,460 --> 00:18:28,310
Četiri i pet.

523
00:18:28,310 --> 00:18:28,620
Pet i šest.

524
00:18:28,620 --> 00:18:30,510
Šest do sedam.

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

526
00:18:31,880 --> 00:18:34,560
Tako sam, ali neka mi igrati
vražji odvjetnik.

527
00:18:34,560 --> 00:18:37,950
Da li sam, vrsta računala koji je upravo
napravio točno kroz ovaj niz

528
00:18:37,950 --> 00:18:40,225
ljudi, znam da sam učinio?

529
00:18:40,225 --> 00:18:40,670
>> ZVUČNI 1: Broj

530
00:18:40,670 --> 00:18:41,050
>> David J. Malan: Pa zašto?

531
00:18:41,050 --> 00:18:46,900
Ono što bih ja moram napraviti kako bi se
zaključuju odlučno da sam učinio?

532
00:18:46,900 --> 00:18:48,230
Vjerojatno još jedan pass.

533
00:18:48,230 --> 00:18:48,430
Točno?

534
00:18:48,430 --> 00:18:51,760
Jer sve što znam iz koje prethodna
pass je da sam ispraviti grešku.

535
00:18:51,760 --> 00:18:53,920
A to znači, možda postoji
Još uvijek još jedna pogreška

536
00:18:53,920 --> 00:18:54,840
da trebam ispraviti.

537
00:18:54,840 --> 00:18:58,680
Dakle, ja samo mogu biti sigurni od premotavanja, i
zatim provjeru jednog do dva, dva i

538
00:18:58,680 --> 00:19:00,940
tri, tri i četiri, četiri i pet,
pet i šest, šest i sedam.

539
00:19:00,940 --> 00:19:02,510
OK, sad sam bez posla.

540
00:19:02,510 --> 00:19:05,990
>> Ja sigurno mogu se sjetiti da sam učinio nema
raditi nešto poput varijable,

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

542
00:19:06,975 --> 00:19:12,490
Nazovite to swaps, a ako je swaps 0 Jednom sam
doći ovdje, a započela je na 0, a zatim

543
00:19:12,490 --> 00:19:15,520
Samo bi bilo glupo da ustrajem
natrag i naprijed, provjeru opet, i

544
00:19:15,520 --> 00:19:16,450
opet, i opet, zar ne?

545
00:19:16,450 --> 00:19:18,450
Budući da zapnete u nekim
vrsta beskonačnu petlju.

546
00:19:18,450 --> 00:19:21,250
Dakle, čim postoji 0 swaps,
možemo tvrditi da je ova

547
00:19:21,250 --> 00:19:23,810
Algoritam je doista potpun.

548
00:19:23,810 --> 00:19:25,400
>> Sada, neka je staviti ime na to.

549
00:19:25,400 --> 00:19:28,930
Algoritam koji sam Predlažemo jednostavno
proveden je nešto što se zove bubble

550
00:19:28,930 --> 00:19:32,800
sortiranje, poznat i kao takva u smislu da
su brojevi koji su veći vrsta

551
00:19:32,800 --> 00:19:37,990
mjehurić svoj put do vrha, odnosno do
na kraju niza brojeva.

552
00:19:37,990 --> 00:19:40,270
No, koliko je učinkovit bio ovaj algoritam?

553
00:19:40,270 --> 00:19:44,600
Koliko koraka sam fizički moraju
Uzmite, na primjer, za sortiranje tih

554
00:19:44,600 --> 00:19:45,850
Sedam ljudi?

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

556
00:19:48,560 --> 00:19:49,550
>> Četiri do pet?

557
00:19:49,550 --> 00:19:51,420
OK, previše je u konačnici
će biti odgovor.

558
00:19:51,420 --> 00:19:54,960
No, čak i tada, određeni broj
nije toliko zanimljiva.

559
00:19:54,960 --> 00:19:56,670
Neka je generalizirati ga kao n.

560
00:19:56,670 --> 00:20:00,520
Dakle, ako sam n ljude ovdje, a oni
su, na neki način, u slučajnim redoslijedom u

561
00:20:00,520 --> 00:20:02,180
počinju, u tom izvornom redoslijedu.

562
00:20:02,180 --> 00:20:04,910
Pa, koliko koraka ja imam
da se na prvom prolazu?

563
00:20:04,910 --> 00:20:09,810
To je jedan, dva, tri, četiri, pet,
šest, a oni su sedam osoba, tako

564
00:20:09,810 --> 00:20:13,670
to je sedam, šest -, tako da je n
minus jedan korake prvi put.

565
00:20:13,670 --> 00:20:16,280
>> Sada, koliko koraka ja imam
da kad sam premotao?

566
00:20:16,280 --> 00:20:19,310
Pa, mi zapravo mogli udvostručiti da ako
smo stvarno željeli, ali za sada, ja sam

567
00:20:19,310 --> 00:20:22,300
Samo ću reći, sve u redu,
još n minus 1.

568
00:20:22,300 --> 00:20:25,240
Dakle, n minus 1 će dobiti
neugodno za pratiti, pa neka je

569
00:20:25,240 --> 00:20:26,400
Samo zaokružiti nešto.

570
00:20:26,400 --> 00:20:27,770
Dakle 2n koraka.

571
00:20:27,770 --> 00:20:29,310
Dakle 14 koraka, dati ili uzeti.

572
00:20:29,310 --> 00:20:31,930
>> Koliko puta sam se
korak sljedeći put?

573
00:20:31,930 --> 00:20:33,740
Pa, to je 3n.

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

575
00:20:34,510 --> 00:20:37,920
I sada, u najgorem slučaju, za
primjerice, koliko puta bi ja imam

576
00:20:37,920 --> 00:20:41,730
otišao natrag i naprijed, natrag i naprijed,
izvršavanju ovaj algoritam, zamjene

577
00:20:41,730 --> 00:20:44,620
Ljudi na svaku loptu, otprilike?

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

579
00:20:47,720 --> 00:20:50,010
To je zapravo n kvadrat, zar ne?

580
00:20:50,010 --> 00:20:53,000
>> Budući da u najgorem slučaju, možete vrsta
od razmišljati o tome intuitivno,

581
00:20:53,000 --> 00:20:54,800
iako bi to moglo potrajati malo
malo vremena kako bi potonuti u.

582
00:20:54,800 --> 00:20:57,590
U najgorem slučaju, što bi to
sedam osoba izgledala, u

583
00:20:57,590 --> 00:21:00,230
uvjeti aranžmana
od njihovih brojeva?

584
00:21:00,230 --> 00:21:01,460
Potpuno unatrag, zar ne?

585
00:21:01,460 --> 00:21:02,815
I samo za simulaciju da,
ono što je zoveš?

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, možeš li mi se pridružiti tijekom
Ovdje za samo jednu sekundu?

589
00:21:08,100 --> 00:21:08,880
Zapravo, nije.

590
00:21:08,880 --> 00:21:10,150
Žao nam je Mike, idemo natrag.

591
00:21:10,150 --> 00:21:10,910
Koje je vaše ime?

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, što dolaze s
mi, ako ti ne smeta.

595
00:21:13,750 --> 00:21:17,150
Zato ću predložiti, samo za
jednostavnost, kako Neil je sada u njegovoj

596
00:21:17,150 --> 00:21:18,510
Najgori mogući slučaj.

597
00:21:18,510 --> 00:21:20,720
Ali sjećam kako sam se provodi
moj algoritam.

598
00:21:20,720 --> 00:21:24,530
Ja sam usporedbe, usporedbe, usporedbe,
usporedbe, usporedbe, oh.

599
00:21:24,530 --> 00:21:26,640
Sada su ti dečki iz
reda, pa sam popraviti.

600
00:21:26,640 --> 00:21:27,980
Dakle, ti dečki zamijeniti.

601
00:21:27,980 --> 00:21:31,630
Ali razmislite, koliko imate dalje
Neil ne moraju ići?

602
00:21:31,630 --> 00:21:32,690
To je otprilike n.

603
00:21:32,690 --> 00:21:33,570
Znate, nije zapravo n.

604
00:21:33,570 --> 00:21:36,040
To je kao, n minus 1, ali ja sam uzimajući
nerviraju praćenje malo

605
00:21:36,040 --> 00:21:37,550
broj, pa neka je samo nazvati n.

606
00:21:37,550 --> 00:21:42,860
>> Dakle, ako Neil pomiče jedan korak maksimalno svaka
vrijeme i za pomicanje Neil jedan korak,

607
00:21:42,860 --> 00:21:46,580
Moram napraviti ovaj uistinu zahtjevan točno
naprijed i natrag, to je otprilike

608
00:21:46,580 --> 00:21:52,080
to, n koraka, ukupno n puta,
jer će me odvesti

609
00:21:52,080 --> 00:21:55,820
da je mnogo koraka kako bi dobili Neil svima
način da tamo gdje pripada.

610
00:21:55,820 --> 00:21:58,620
A kamoli svi drugi, ako ti dečki
Svi su mis-naredio kao dobro.

611
00:21:58,620 --> 00:22:01,100
>> Dakle, nazovimo mjehurić kakve n kvadratna.

612
00:22:01,100 --> 00:22:04,860
Trajanje tog algoritma,
Performanse ovog algoritma,

613
00:22:04,860 --> 00:22:07,120
Učinkovitost ovog algoritma,
samo smo se opisati više

614
00:22:07,120 --> 00:22:08,800
općenito, kao n kvadrat.

615
00:22:08,800 --> 00:22:11,650
Koji je lijepo, jer sam mogao učiniti
Isti primjer s osam, devet ljudi

616
00:22:11,650 --> 00:22:15,450
ljudi, milijun ljudi, i to
Odgovor se neće promijeniti.

617
00:22:15,450 --> 00:22:18,870
>> Dakle, ako vi ne bi smetalo, neka je
vas vratiti na mjesto gdje ste počeli.

618
00:22:18,870 --> 00:22:22,510
I pokušajmo još dva pristupa i
vidjeti ako ne možemo napraviti iz temelja

619
00:22:22,510 --> 00:22:23,820
bolje od ovoga.

620
00:22:23,820 --> 00:22:27,130
Dakle, ovaj put, ja ću predložiti
različitih vrsta algoritma.

621
00:22:27,130 --> 00:22:29,950
To je vrlo pametno od nas zadnji put,
a vi dečki su pravo na

622
00:22:29,950 --> 00:22:32,470
pravo instinkti samo vrsta
od zamjene Parne.

623
00:22:32,470 --> 00:22:36,500
Ali ako sam doista želio pristupiti ovom
jednostavno, a moj cilj je da se premjestiti

624
00:22:36,500 --> 00:22:39,800
sve od malih brojeva na ovaj način, a
gurati sve od velikih brojeva koji

625
00:22:39,800 --> 00:22:43,030
smjer, zašto ne bih to učiniti u
većina naivno mogući način i vidjeti ako ja

626
00:22:43,030 --> 00:22:45,730
može učiniti bolje od onoga što je
prilično složen algoritam?

627
00:22:45,730 --> 00:22:46,620
>> Pa ćemo vidjeti.

628
00:22:46,620 --> 00:22:48,940
Četiri je prilično mali broj, pa sam
će vas ostaviti tamo trenutak.

629
00:22:48,940 --> 00:22:50,610
Ooh, broj dva je još bolje.

630
00:22:50,610 --> 00:22:52,230
Dakle, može li samo korak naprijed
na trenutak?

631
00:22:52,230 --> 00:22:55,670
Ovo je trenutno moj najmanji numerirani
Kandidat, a ja ću se sjetiti

632
00:22:55,670 --> 00:22:57,000
da s, kao, varijable.

633
00:22:57,000 --> 00:22:57,930
Ali ću držati ček.

634
00:22:57,930 --> 00:22:59,890
Ima li netko čije
Broj je manji?

635
00:22:59,890 --> 00:23:00,460
Šest, br.

636
00:23:00,460 --> 00:23:01,390
Oh, ima Neil opet.

637
00:23:01,390 --> 00:23:04,050
>> Tako ću vas gurnuti natrag
vrsta konceptualno.

638
00:23:04,050 --> 00:23:05,120
Neil će doći naprijed.

639
00:23:05,120 --> 00:23:08,440
A sada, varijablu da sam koristeći se
pratiti tko ima najmanji

640
00:23:08,440 --> 00:23:11,390
broj obnovljen je da sadrži
Neil je položaj.

641
00:23:11,390 --> 00:23:12,110
Pa, da vidimo.

642
00:23:12,110 --> 00:23:13,960
Tri, sedam, pet.

643
00:23:13,960 --> 00:23:15,590
OK, znam da je Neil bio najmanji.

644
00:23:15,590 --> 00:23:18,110
Što je najjednostavnije
za mene to učiniti sada?

645
00:23:18,110 --> 00:23:21,410
Neću gubiti svoje vrijeme samo
mjehurića Neil jedno mjesto ulijevo.

646
00:23:21,410 --> 00:23:25,350
Zašto ne samo staviti Neila gdje je
zaposlen, što je, naravno, gdje?

647
00:23:25,350 --> 00:23:26,160
>> Skroz na početku.

648
00:23:26,160 --> 00:23:27,720
Dakle Neila, dolaze sa mnom.

649
00:23:27,720 --> 00:23:28,910
A što je zoveš?

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
Dakle, Grace, na žalost, ti si
vrsta na putu.

654
00:23:32,490 --> 00:23:34,290
Pa kako ćemo riješiti ovaj problem?

655
00:23:34,290 --> 00:23:34,490
Točno?

656
00:23:34,490 --> 00:23:37,500
Ako je ovo polje, postoji
samo sedam mjesta.

657
00:23:37,500 --> 00:23:40,830
Podsjetimo da je, s Robom, razgovarali smo o
progla dobi, a mi imali samo

658
00:23:40,830 --> 00:23:41,740
konačan broj dobi?

659
00:23:41,740 --> 00:23:42,535
Sve ideja ovdje.

660
00:23:42,535 --> 00:23:44,300
Mi samo imaju ograničen broj Ints.

661
00:23:44,300 --> 00:23:47,590
Grace je vrsta u našim
smjer, pa kako smo riješili?

662
00:23:47,590 --> 00:23:49,555
>> Najjednostavniji način je da,
Grace, ispričavam se.

663
00:23:49,555 --> 00:23:51,870
Ti ćeš morati ići preko
postoje tako da možemo napraviti mjesta.

664
00:23:51,870 --> 00:23:55,290
Sada, ako mislite o tome, možda
samo mi je problem pogoršava.

665
00:23:55,290 --> 00:23:58,510
A možda smo mi, zato što ako
Grace je na pravom mjestu?

666
00:23:58,510 --> 00:24:01,730
Ali mi znamo da nije, jer je
inače, ona bi bila

667
00:24:01,730 --> 00:24:03,980
stoji prema naprijed, umjesto
Neil u ovom trenutku, zar ne?

668
00:24:03,980 --> 00:24:05,550
Mi već provjerio njezin broj out.

669
00:24:05,550 --> 00:24:05,770
>> U redu.

670
00:24:05,770 --> 00:24:09,110
Tako sada, Neil je na pravom mjestu, i
Ja mogu napraviti blagi optimizacije.

671
00:24:09,110 --> 00:24:11,740
Za sljedeću minutu, ja ću ignorirati
Neil svi zajedno, tako da ne

672
00:24:11,740 --> 00:24:15,280
gubiti svoje vrijeme, ili slučajno
ga zamijeniti na krivom mjestu.

673
00:24:15,280 --> 00:24:17,805
Tako sada, kako ću pronaći sljedeći
element koji je najmanji?

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

675
00:24:18,480 --> 00:24:20,225
To je prilično dobar broj, ako je
želite korak naprijed i

676
00:24:20,225 --> 00:24:21,100
Ja ću vas se sjetiti.

677
00:24:21,100 --> 00:24:21,980
Šest, nije dobro.

678
00:24:21,980 --> 00:24:24,820
Četiri, tri, sedam, pet, nije dobro.

679
00:24:24,820 --> 00:24:26,800
Dakle, dopustite mi da se presele
Vaše pravo mjesto.

680
00:24:26,800 --> 00:24:28,470
I samo mi se posrećilo ovaj put.

681
00:24:28,470 --> 00:24:31,350
>> Sada, ja ću ih ignorirati
dvojica, a sada napraviti još jedan

682
00:24:31,350 --> 00:24:32,260
prolaze kroz to.

683
00:24:32,260 --> 00:24:33,490
Šest, da je prilično mali broj.

684
00:24:33,490 --> 00:24:34,300
Hajde naprijed.

685
00:24:34,300 --> 00:24:35,220
Oh, ispričavam se.

686
00:24:35,220 --> 00:24:37,640
Grace broj je bolje,
tako korak na naprijed.

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

688
00:24:38,260 --> 00:24:39,120
Žao nam je, Grace.

689
00:24:39,120 --> 00:24:39,950
Idi natrag.

690
00:24:39,950 --> 00:24:41,550
Broj tri je bolje.

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

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

693
00:24:42,720 --> 00:24:43,550
I sad ono zoveš?

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
Dakle, Jason je sada najmanji
Element sam odabrana.

697
00:24:47,050 --> 00:24:49,160
Kamo ide ići?

698
00:24:49,160 --> 00:24:50,380
Dakle, gdje je šest.

699
00:24:50,380 --> 00:24:51,210
I vaše ime je opet?

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 je na putu.

703
00:24:53,220 --> 00:24:54,640
Što je najjednostavnija stvar za napraviti?

704
00:24:54,640 --> 00:24:58,390
Zamijeni ove dvije dečki i nastaviti.

705
00:24:58,390 --> 00:24:59,020
Pa sad ćemo vidjeti.

706
00:24:59,020 --> 00:25:00,170
Tko je najmanji?

707
00:25:00,170 --> 00:25:01,030
Četiri.

708
00:25:01,030 --> 00:25:01,990
Dopustite mi samo vrsta varati.

709
00:25:01,990 --> 00:25:03,090
Pet će biti najmanja.

710
00:25:03,090 --> 00:25:05,220
Ja vam sljedeći, ako želite korak
prema naprijed, što moram učiniti sa

711
00:25:05,220 --> 00:25:06,820
ovi momci, s Gabea?

712
00:25:06,820 --> 00:25:08,450
Zamijeni opet.

713
00:25:08,450 --> 00:25:10,740
Tako sada, još uvijek malo izvan funkcije.

714
00:25:10,740 --> 00:25:14,140
Otkrio sam da se Gabe najmanji, tako
Ja ga iskočiti, pomaknite se momci više.

715
00:25:14,140 --> 00:25:15,190
I učinili.

716
00:25:15,190 --> 00:25:17,200
>> Tako da odgovor je isti.

717
00:25:17,200 --> 00:25:18,600
Krajnji rezultat je isti.

718
00:25:18,600 --> 00:25:22,730
Koja od ove dvije algoritama
je bolje?

719
00:25:22,730 --> 00:25:23,500
Drugi, čuo sam.

720
00:25:23,500 --> 00:25:24,252
Zašto?

721
00:25:24,252 --> 00:25:25,900
>> ZVUČNI 3: Prošlo n korake [nečujno].

722
00:25:25,900 --> 00:25:27,600
>> David J. Malan: To je n koraka u većini.

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

724
00:25:28,490 --> 00:25:30,610
Tako je to ipak?

725
00:25:30,610 --> 00:25:33,630
Pa kako mi je bilo
najmanji element?

726
00:25:33,630 --> 00:25:37,060
Koliko koraka sam uzeti
pronaći najmanji element?

727
00:25:37,060 --> 00:25:39,220
Imao sam izgleda skroz
na kraju, zar ne?

728
00:25:39,220 --> 00:25:41,530
Budući da u tom najgorem slučaju, ono što
Neil ako su ovamo?

729
00:25:41,530 --> 00:25:45,700
Dakle, samo nalaz najmanji element
vodi me n koraka, ili n minus jedan.

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

731
00:25:46,100 --> 00:25:46,980
Dakle riješili Neila.

732
00:25:46,980 --> 00:25:48,740
Zapamtite da, otprilike minutu prije.

733
00:25:48,740 --> 00:25:51,680
>> Ali kako sam pronaći sljedeći
najmanji element?

734
00:25:51,680 --> 00:25:54,830
To je n minus 1, odnosno n minus 2 stvarno,
od broja koraka.

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

736
00:25:55,440 --> 00:25:57,390
Pa sam si n minus dva.

737
00:25:57,390 --> 00:25:57,600
U redu.

738
00:25:57,600 --> 00:25:59,130
Tako da se osjeća malo bolje.

739
00:25:59,130 --> 00:25:59,730
U redu.

740
00:25:59,730 --> 00:26:03,270
Koliko korake sljedeći put
pronaći broj tri?

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

742
00:26:04,420 --> 00:26:07,670
Dakle, to smanjuje, jedan manje
korak na svakoj iteraciji.

743
00:26:07,670 --> 00:26:08,740
Dakle, to ne osjećate bolje, zar ne?

744
00:26:08,740 --> 00:26:13,450
Ukoliko zadnji put je to bilo otprilike n puta n,
ovaj put je n minus 1, plus minus n

745
00:26:13,450 --> 00:26:16,500
2, te n minus 3 ili n
minus 4, točka, točka, točka.

746
00:26:16,500 --> 00:26:18,750
No, ako se sjećaš iz srednje škole
udžbenici, malo podvaliti

747
00:26:18,750 --> 00:26:24,380
List na stražnjoj strani koja je formula, ako
zbrojite ovaj niz brojeva,

748
00:26:24,380 --> 00:26:31,280
Što je ukupan broj koraka
će biti da sam se ovdje?

749
00:26:31,280 --> 00:26:36,580
>> Ovo je jedan od onih koji, kao, n minus
1, n puta, podijeljeno s dva.

750
00:26:36,580 --> 00:26:39,040
Dakle, dopustite mi da vidim mogu povući
to se samo na trenutak.

751
00:26:39,040 --> 00:26:42,230
I opet, ja sam vrsta zaokruživanja neke
Brojevi samo da bi naš život lakšim,

752
00:26:42,230 --> 00:26:47,830
ali koliko se sjećam, to je nešto kao i ako
Ja n minus 1 stvari, a zatim n minus

753
00:26:47,830 --> 00:26:53,570
2, a zatim n minus 3, to je otprilike
ovako nešto više od 2, a ako sam

754
00:26:53,570 --> 00:26:55,510
pomnožite ovo, to je
zapravo n trgu.

755
00:26:55,510 --> 00:26:58,940
To se ne osjeća baš dobro.
n minus n preko 2.

756
00:26:58,940 --> 00:27:00,350
>> Ali ovdje je stvar.

757
00:27:00,350 --> 00:27:03,720
U računalnoj znanosti, kad su problemi
početi da biste dobili zanimljiv je kad n

758
00:27:03,720 --> 00:27:04,700
dobiva stvarno velika.

759
00:27:04,700 --> 00:27:08,110
A kada je n dobiva stvarno velika, što je
ove vrijednosti će dominirati sve

760
00:27:08,110 --> 00:27:09,750
od drugih?

761
00:27:09,750 --> 00:27:10,990
To je vrsta od n na kvadrat, zar ne?

762
00:27:10,990 --> 00:27:13,340
Da, podijeli s dva je prilično dobra.

763
00:27:13,340 --> 00:27:16,740
Ali ako govorimo o milijardama
komada podataka, ili bilijunima

764
00:27:16,740 --> 00:27:18,700
dijelovi podataka, ok, pa
ti si dva puta brže.

765
00:27:18,700 --> 00:27:22,440
No, tko je zapravo briga ako tim velikim brojem,
ako je taj faktor je ono što dobiva

766
00:27:22,440 --> 00:27:23,040
veći i veći.

767
00:27:23,040 --> 00:27:25,990
I sigurno, to čini više od
Razlika od ovog momka.

768
00:27:25,990 --> 00:27:29,120
Dakle, iako ste vi u pravu,
Drugi algoritam, mi ćemo ga zvati

769
00:27:29,120 --> 00:27:32,970
Izbor sortiranje, je, u stvarnom svijetu,
malo brže potencijalno, jer sam

770
00:27:32,970 --> 00:27:35,360
uzimajući sve manje i manje
korake svaki put.

771
00:27:35,360 --> 00:27:37,340
>> To zapravo nije bitno brži.

772
00:27:37,340 --> 00:27:41,430
Jer, ako smo zapravo igrati ovo za
velike vrijednosti n, na kraju

773
00:27:41,430 --> 00:27:44,750
dan, za dovoljno veliki n, to je još uvijek
ide da se osjećaju prilično sporo.

774
00:27:44,750 --> 00:27:46,770
Pa, neka mi se jedan
Posljednji pass na to.

775
00:27:46,770 --> 00:27:48,920
To je ono što bih nazvao
Izbor sortiranje.

776
00:27:48,920 --> 00:27:51,040
Možete li sebe resetirati
zadnji put?

777
00:27:51,040 --> 00:27:53,550
I u ovom posljednjem slučaju, idem
predložiti nešto

778
00:27:53,550 --> 00:27:54,970
naziva unosa vrsta.

779
00:27:54,970 --> 00:27:57,470
Ubacivanje neka vrsta bića, konceptualno,
malo drugačiji.

780
00:27:57,470 --> 00:28:00,980
>> Umjesto da ide naprijed i natrag, a
odabirom najmanji element, sam

781
00:28:00,980 --> 00:28:05,030
Samo će se nositi sa svakom od tih
Dečki kao što sam ih susrećemo, i umetnite

782
00:28:05,030 --> 00:28:06,850
ih u njihovom ispravnom mjestu.

783
00:28:06,850 --> 00:28:10,160
Dakle, samo ću početi s Grace,
i ja vidim da je ona broj četiri.

784
00:28:10,160 --> 00:28:11,720
Odakle broj četiri pripadaju?

785
00:28:11,720 --> 00:28:14,940
Ja nisam počeo ništa sortiranja,
Grace tako dobiva ostati tamo.

786
00:28:14,940 --> 00:28:18,355
A sada ću tvrditi, ako bi
poduzeti korak da je vaše pravo, to

787
00:28:18,355 --> 00:28:21,650
moj razvrstani popis, ovo je moj
nerazvrstani preostali popis.

788
00:28:21,650 --> 00:28:23,260
Dakle, sad ću nastaviti sljedeći,
i ono zoveš?

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
Dakle Branson je broj dva.

792
00:28:25,375 --> 00:28:27,490
Dakle, ja ću vas odvesti
se na trenutak.

793
00:28:27,490 --> 00:28:30,940
A sada, gdje si ti
u tom polju?

794
00:28:30,940 --> 00:28:32,360
Dakle, desno od Milosti.

795
00:28:32,360 --> 00:28:35,670
Pa opet, mi smo vrsta izradu
Grace napraviti puno posla ovdje.

796
00:28:35,670 --> 00:28:37,290
Gdje smo vas?

797
00:28:37,290 --> 00:28:40,120
Tako ćemo vas pomaknite se
lijevo, i umetnite Branson postoji.

798
00:28:40,120 --> 00:28:41,680
Ali sada tvrdim da
ti dečki su učinili.

799
00:28:41,680 --> 00:28:43,240
No, obavijest, ne koristim dodatni prostor.

800
00:28:43,240 --> 00:28:45,130
To je još uvijek 2 elementa
Ovdje, 5 ovamo.

801
00:28:45,130 --> 00:28:47,910
Ukupna veličina polja je 7, tako da sam
ne vara, u redu?

802
00:28:47,910 --> 00:28:51,950
>> Tako sada imamo, s Gabea ovdje,
broj šest, gdje si ti?

803
00:28:51,950 --> 00:28:52,650
Imaš sreću ponovno.

804
00:28:52,650 --> 00:28:53,820
Tako ćete dobiti ostati tamo.

805
00:28:53,820 --> 00:28:57,210
Dovoljno je uzeti lagani korak prema desno
samo da bi jasno da ste razvrstani.

806
00:28:57,210 --> 00:29:00,520
I sada imamo Neila opet, broj
jedan, gdje idete?

807
00:29:00,520 --> 00:29:03,540
A sada je mjesto gdje ćemo početi vidjeti da
ovaj algoritam, iako se na prvi

808
00:29:03,540 --> 00:29:05,950
pogled, osjeća prilično pametna, gledanje
što će se dogoditi.

809
00:29:05,950 --> 00:29:07,370
Ako bi korak naprijed.

810
00:29:07,370 --> 00:29:09,260
>> Gdje želimo staviti Neila?

811
00:29:09,260 --> 00:29:11,830
Dakle, očito ovdje, pa kako
ćemo dobiti Neila postoji?

812
00:29:11,830 --> 00:29:12,970
Učinimo ovaj korak-po-korak.

813
00:29:12,970 --> 00:29:15,620
Gabe, gdje trebate ići?

814
00:29:15,620 --> 00:29:19,590
Yep, tako da se jedan veliki korak,
ili dvije polovice koraci kako bi

815
00:29:19,590 --> 00:29:20,820
jedan korak tamo.

816
00:29:20,820 --> 00:29:21,750
Grace, gdje idete?

817
00:29:21,750 --> 00:29:22,510
Dobro.

818
00:29:22,510 --> 00:29:23,500
Tako je još jedan korak.

819
00:29:23,500 --> 00:29:24,960
I na kraju, Branson?

820
00:29:24,960 --> 00:29:25,460
Još jedan korak.

821
00:29:25,460 --> 00:29:27,190
I sada možemo staviti na mjesto Neila.

822
00:29:27,190 --> 00:29:28,440
>> Pa sad, i dalje tu logiku.

823
00:29:28,440 --> 00:29:32,420
Iako mi se ne prebacuje Neilu
više, i više, i više, da ga stavi

824
00:29:32,420 --> 00:29:36,420
gdje ide, u najgorem slučaju,
Sljedeći broj ćemo naići mogli

825
00:29:36,420 --> 00:29:42,220
se broj, kažu, bilo je broj
nuli, onda ćemo pomaknuti sve

826
00:29:42,220 --> 00:29:42,730
ovi momci.

827
00:29:42,730 --> 00:29:44,950
Pretpostavimo da je broj negativan
jedan, onda ćemo morati prebaciti

828
00:29:44,950 --> 00:29:46,080
svi ovi dečki.

829
00:29:46,080 --> 00:29:48,500
Tako smo zapravo samo vrsta flipping
Problem oko, kao da smo

830
00:29:48,500 --> 00:29:52,620
prijenos trošak od
postupak odabira tako umetanje

831
00:29:52,620 --> 00:29:56,930
proces, tako da vi samo imali
premjestiti otprilike n minus nešto

832
00:29:56,930 --> 00:29:57,940
Broj koraka.

833
00:29:57,940 --> 00:30:01,200
I da je broj koraka samo ide
povećati kao što sam odabir više brojeva,

834
00:30:01,200 --> 00:30:04,730
ako moram držati guranje momci
natrag, i natrag, i natrag.

835
00:30:04,730 --> 00:30:08,320
>> Tako tužno Sada je sve to
algoritme su n na kvadrat.

836
00:30:08,320 --> 00:30:10,570
Idemo naprijed, a zahvaljujući tim
Dečki, i zamišljati ove malo

837
00:30:10,570 --> 00:30:11,090
drugačije.

838
00:30:11,090 --> 00:30:12,312
Vrlo dobro učinio.

839
00:30:12,312 --> 00:30:14,120
>> [PLJESAK]

840
00:30:14,120 --> 00:30:15,030
>> U redu.

841
00:30:15,030 --> 00:30:16,280
Izvoli.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Hvala -

844
00:30:18,470 --> 00:30:19,190
>> BRANSON: [nečujno] držati brojeve.

845
00:30:19,190 --> 00:30:21,990
>> David J. Malan: Ne, vi svibanj
zadržati brojeve, kao dobro.

846
00:30:21,990 --> 00:30:23,440
U redu.

847
00:30:23,440 --> 00:30:24,100
Lijepo učinili.

848
00:30:24,100 --> 00:30:25,300
U redu.

849
00:30:25,300 --> 00:30:30,510
Dakle, neka je vidjeti ako sad ne možemo sumirati
brže i više vizualno,

850
00:30:30,510 --> 00:30:33,410
točno što se dogodilo
Ovdje su kako slijedi.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Ja ću ići naprijed
i povucite prema gore Firefox.

853
00:30:38,770 --> 00:30:41,310
Mi ćemo povezati ovaj prosvjed
na stazi stranicama.

854
00:30:41,310 --> 00:30:43,870
Java je malo neugodno da se radi
u nekim preglednicima ovih dana.

855
00:30:43,870 --> 00:30:46,760
Dakle, ako ne igraju s tim kod kuće,
shvatite da ćete morati koristiti Firefox

856
00:30:46,760 --> 00:30:47,990
da se to radi.

857
00:30:47,990 --> 00:30:50,440
A ono što ću učiniti s ovim
Demonstracija je sljedeće.

858
00:30:50,440 --> 00:30:54,875
>> Na dnu, imam cijelu hrpu
opcije izbornika, uključujući početak i

859
00:30:54,875 --> 00:30:55,840
stop.

860
00:30:55,840 --> 00:30:59,450
Također, kao na stranu, čini se da postoji
bug u ovim programima, pri čemu se

861
00:30:59,450 --> 00:31:03,720
zapravo ne može vidjeti početak ili zaustavljanje
Gumb ukoliko ne držite Command ili Alt

862
00:31:03,720 --> 00:31:06,560
plus i zumiranje, koji znatiželjno
pokazuje više gumba.

863
00:31:06,560 --> 00:31:09,090
Dakle, samo za Vašu informaciju, ako igrate
uz to kod kuće.

864
00:31:09,090 --> 00:31:12,870
Sada ću kliknite Start u samo
Trenutak, nakon navođenja kašnjenje,

865
00:31:12,870 --> 00:31:16,810
kao što je, 200 milisekundi ovdje, samo
tako da možemo vidjeti što se događa.

866
00:31:16,810 --> 00:31:20,180
>> Dakle, ja tvrdim da je to vizualizacija
prvog algoritma

867
00:31:20,180 --> 00:31:23,730
ovi momci su napravili, bubble sortiranje, pri čemu
Zamijenili smo ljude pair-mudar.

868
00:31:23,730 --> 00:31:27,490
Ključni uvid na ovu vizualizaciju
je da je visina od traka

869
00:31:27,490 --> 00:31:30,510
predstavlja veličinu broja.

870
00:31:30,510 --> 00:31:32,210
Dakle jači bar,
veći broj.

871
00:31:32,210 --> 00:31:33,680
Kraći bar, manji broj.

872
00:31:33,680 --> 00:31:38,630
A ako primjetite, idemo kroz
prva iteracija ovog algoritma

873
00:31:38,630 --> 00:31:42,620
zamjene velike i male brojeve, tako da je
Mali broj je na prvom mjestu, a

874
00:31:42,620 --> 00:31:44,280
Veliki broj ide na desno.

875
00:31:44,280 --> 00:31:48,770
>> I čim smo dobili kraj niza
mnogih više od sedam brojeva, mi smo

876
00:31:48,770 --> 00:31:49,900
će se vratiti na početak.

877
00:31:49,900 --> 00:31:51,140
I to predvidjeti.

878
00:31:51,140 --> 00:31:54,860
Na daleko lijevo, da mali dečko ide
mijenjati u stranu, a to

879
00:31:54,860 --> 00:31:56,010
proces se ponavlja.

880
00:31:56,010 --> 00:31:59,450
Sada je to vizualizacija brzo dobiva
dosadna, pa neka mi ići naprijed i zaustaviti

881
00:31:59,450 --> 00:32:04,170
da, promijenite nešto odgode mnogo
brži samo da bi sada, osjećaj za

882
00:32:04,170 --> 00:32:05,060
ovaj algoritam.

883
00:32:05,060 --> 00:32:07,840
>> Dakle, iako sam ga ubrzao, ovo je
kao i nadogradnju moje procesor, kupnje

884
00:32:07,840 --> 00:32:08,580
novo računalo.

885
00:32:08,580 --> 00:32:12,980
Nisam iz temelja promijenilo moj
algoritam, ali doista može vidjeti više

886
00:32:12,980 --> 00:32:16,800
jasnije nego s ljudima, da je velika
brojevi mjehurića do vrha,

887
00:32:16,800 --> 00:32:20,900
a mali broj se mjehurića
do dna.

888
00:32:20,900 --> 00:32:22,390
A sada ovo ovdje izdvojiti.

889
00:32:22,390 --> 00:32:25,260
I kao stranu, na trgovima, postoji
samo su neka knjigovodstvo tamo

890
00:32:25,260 --> 00:32:28,010
vam pomoći brojati koliko usporedbe,
ili koliko imaju swaps

891
00:32:28,010 --> 00:32:28,950
zapravo učinjeno.

892
00:32:28,950 --> 00:32:30,750
>> Pa, pokušajmo jedan od
ostali smo vidjeli.

893
00:32:30,750 --> 00:32:37,116
Dopustite mi da kliknete na balon vrste ovdje, a
dopustite mi da odaberem, a cijela ova web stranica

894
00:32:37,116 --> 00:32:38,936
je malo lud.

895
00:32:38,936 --> 00:32:41,155
Hajdemo prihvatiti rizik
te ga ponovno pokrenuti.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Tamo idemo.

898
00:32:45,030 --> 00:32:47,180
Tako ćemo napraviti odabir vrsta.

899
00:32:47,180 --> 00:32:49,140
Ne znam zašto se izbornik
pojavljuje tamo.

900
00:32:49,140 --> 00:32:54,070
Idemo zoom u to popraviti
bug, to promijeni do 50 godina.

901
00:32:54,070 --> 00:32:56,020
Ah, neka je zapravo
da je puno brže.

902
00:32:56,020 --> 00:32:59,160
Pet milisekundi ili tako, i početi.

903
00:32:59,160 --> 00:33:00,470
>> Dakle, ovo je neka vrsta odabira.

904
00:33:00,470 --> 00:33:03,070
Pa opet, razmišljati o tome što smo
učinio s ljudima ovdje.

905
00:33:03,070 --> 00:33:08,490
Prošli smo kroz niz i odabrana
najmanji element opet,

906
00:33:08,490 --> 00:33:09,250
i opet, i opet.

907
00:33:09,250 --> 00:33:11,110
Sada sam tvrde da je još uvijek prilično loše.

908
00:33:11,110 --> 00:33:15,010
To je još uvijek n kvadrat, dati ili uzeti,
ali to je, u stvarnom svijetu, malo

909
00:33:15,010 --> 00:33:18,280
brže, jer sam doista bio vodeći
nešto manje korake svaki put.

910
00:33:18,280 --> 00:33:19,800
No, mi samo pričamo što?

911
00:33:19,800 --> 00:33:21,830
Možda 40 ili tako bar ovdje?

912
00:33:21,830 --> 00:33:23,200
Mi ne govorimo 40 milijuna kuna.

913
00:33:23,200 --> 00:33:27,430
Dakle, to nije potpuno mi je jasno da
bio je doista značajan dobitak.

914
00:33:27,430 --> 00:33:32,530
>> Dopustite mi sada vratiti i promijeniti u našim
Treći algoritam, koji je odabir

915
00:33:32,530 --> 00:33:33,180
umetanja sortiranje.

916
00:33:33,180 --> 00:33:36,380
I sad je stvarno lud, jer
Izbornik stvarno ne bi trebao biti tamo.

917
00:33:36,380 --> 00:33:40,840
Dakle, sada ćemo pomicanje natrag ovdje
i početi ovaj algoritam.

918
00:33:40,840 --> 00:33:43,270
Poklič, pokretanje i zaustavljanje.

919
00:33:43,270 --> 00:33:47,160
Dakle, to je jedna vrsta ima lijepu uzorak
na njega, pri čemu smo opet

920
00:33:47,160 --> 00:33:50,240
umetanjem ljude, ili u
ovaj slučaj, lokali u

921
00:33:50,240 --> 00:33:52,620
njihovo odgovarajuće mjesto.

922
00:33:52,620 --> 00:33:55,430
A to je već učinjeno prije
Okrenula sam se.

923
00:33:55,430 --> 00:33:58,940
No, i ova je također, u teoriji,
Još uvijek je n kvadrat.

924
00:33:58,940 --> 00:34:01,430
>> Dakle, neka je vidjeti ako ne možemo sumirati
to na sljedeći način.

925
00:34:01,430 --> 00:34:04,750
Ja ću ići naprijed i samo dati
nas vrsta zajedničkog način govori

926
00:34:04,750 --> 00:34:08,489
o ovim stvarima, neka mi predstaviti
Samo malo zapis ovdje.

927
00:34:08,489 --> 00:34:12,480
Vi ste o kako bi vidjeli nešto što se zove big
O, jer je doslovce velika

928
00:34:12,480 --> 00:34:16,320
O. I to je način na koji računalo
znanstvenik ili matematičar i koristi

929
00:34:16,320 --> 00:34:19,230
opisati vrijeme rada
nekog algoritma.

930
00:34:19,230 --> 00:34:21,400
Koliko koraka to zapravo potrajati?

931
00:34:21,400 --> 00:34:25,080
>> Sada ću se ja sramotiti s
moj rukopis ovdje u samo trenutak.

932
00:34:25,080 --> 00:34:29,020
No, dopustite mi da ide naprijed i reći da
to će biti velika O ovamo.

933
00:34:29,020 --> 00:34:33,610
I neka mi predstaviti jedan drugi
simbol, glavni omega.

934
00:34:33,610 --> 00:34:37,080
Omega će biti suprotno,
u biti, od velikog O. dok velike O

935
00:34:37,080 --> 00:34:40,790
znači, u najgorem slučaju, koliko vremena
Možda su neki algoritam se, u

936
00:34:40,790 --> 00:34:43,480
Uvjeti n, omega će
se koliko vremena može ga

937
00:34:43,480 --> 00:34:45,409
se u najboljem slučaju.

938
00:34:45,409 --> 00:34:48,090
A vidjet ćemo što podrazumijevamo pod
Najbolji slučaj u samo trenutak.

939
00:34:48,090 --> 00:34:49,940
>> Dakle, krenimo nešto jednostavno.

940
00:34:49,940 --> 00:34:54,719
Dopustite mi da započnem s linearnim pretraživanje.

941
00:34:54,719 --> 00:34:55,679
Dakle, ne sortiranja.

942
00:34:55,679 --> 00:34:58,000
Nazvat ćemo ovo linearno pretraživanje.

943
00:34:58,000 --> 00:35:01,140
I sada, da malo
tablici iz ovoga.

944
00:35:01,140 --> 00:35:06,600
I sada, u slučaju linearne pretraživanja,
u najgorem slučaju, koliko koraka je

945
00:35:06,600 --> 00:35:11,770
je da će me odvesti pronaći
broj proizvoljnog izbora?

946
00:35:11,770 --> 00:35:14,540
I tu je n ukupni vrata
ili n ukupni broj.

947
00:35:14,540 --> 00:35:15,940
Najgori slučaj.

948
00:35:15,940 --> 00:35:18,800
Koliko koraka ću morati
poduzeti kako bi pronašli broj 50 u niz

949
00:35:18,800 --> 00:35:20,830
od n vrata?

950
00:35:20,830 --> 00:35:21,410
A zašto?

951
00:35:21,410 --> 00:35:23,680
Jer to bi moglo biti sve
put preko na kraju.

952
00:35:23,680 --> 00:35:27,120
Toliko poput Jennifer naišao,
Broj 50 je bio skroz, tako da u

953
00:35:27,120 --> 00:35:30,760
najgorem slučaju linearno pretraživanje
je velika O n, mi ćemo reći.

954
00:35:30,760 --> 00:35:33,430
>> Što o najboljem slučaju,
ako se stvarno sretan?

955
00:35:33,430 --> 00:35:36,200
To samo ide uzeti jedan korak,
ili stalna broj koraka.

956
00:35:36,200 --> 00:35:37,830
Tako ćemo opisuju to kao jedan.

957
00:35:37,830 --> 00:35:39,010
Dakle, ovo je prilično dobra.

958
00:35:39,010 --> 00:35:41,210
Sad što ako mi je nešto
kao binarna?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
Dakle, binarna, u najgorem
slučaj, uzeo koliko vremena?

961
00:35:47,846 --> 00:35:49,250
>> [Pridodati glasovima]

962
00:35:49,250 --> 00:35:51,310
>> David J. Malan: Pa zapravo, ja
ga čuli za par mjesta.

963
00:35:51,310 --> 00:35:56,390
Dakle, to je zapravo log n, više ili manje,
jer kao što smo podijeliti na pola popis

964
00:35:56,390 --> 00:36:00,730
opet, i opet, i opet, mi smo u mogućnosti
naći, u konačnici, vrijednost,

965
00:36:00,730 --> 00:36:04,750
Ako je tamo, ali postoji kvaka.

966
00:36:04,750 --> 00:36:08,590
Što je pretpostavka da moramo
uzeti zdravo za gotovo binarni potrazi?

967
00:36:08,590 --> 00:36:09,700
To mora biti riješeno.

968
00:36:09,700 --> 00:36:12,770
Nije riješeno, možete podijeliti stvar
na pola opet i opet, a vi

969
00:36:12,770 --> 00:36:15,490
može ići lijevo, a možete ići desno, a
možete ići lijevo i desno, ali ti si

970
00:36:15,490 --> 00:36:18,070
Ne ide pronaći element ako je
Popis nije riješeno, jer je

971
00:36:18,070 --> 00:36:18,790
možda ga propustiti.

972
00:36:18,790 --> 00:36:22,120
Zbog svoje heurističkim, za idući lijeva
ili desno će biti manjkav, ako je to

973
00:36:22,120 --> 00:36:23,420
istina, nije riješeno.

974
00:36:23,420 --> 00:36:26,110
Tako da postoji neka vrsta skrivenih troškova
na korištenje ovako nešto.

975
00:36:26,110 --> 00:36:29,250
>> Sada, idemo u našu sortiranje
algoritmi ne traži -

976
00:36:29,250 --> 00:36:31,140
Oh, zapravo, idemo u tom prazninom.

977
00:36:31,140 --> 00:36:33,190
Binary search u najboljem slučaju?

978
00:36:33,190 --> 00:36:36,290
To je također jedna ako se to dogodi samo da bude
u samom središtu polja, ili

979
00:36:36,290 --> 00:36:37,810
Sredina u telefonskom imeniku.

980
00:36:37,810 --> 00:36:39,710
Sada ćemo napraviti balon vrsta.

981
00:36:39,710 --> 00:36:42,570
Pa opet, sada ulazimo
vrste, a ne na traženje.

982
00:36:42,570 --> 00:36:47,220
>> U najgorem slučaju, koliko koraka smo učinili
tvrdnja bubble sortiranje će potrajati?

983
00:36:47,220 --> 00:36:48,410
n kvadrat.

984
00:36:48,410 --> 00:36:49,200
Tako ću se izvući da je.

985
00:36:49,200 --> 00:36:51,710
Ooo, moj rukopis izgleda još gore
kad je usmjeren da je veliki.

986
00:36:51,710 --> 00:36:52,510
U redu.

987
00:36:52,510 --> 00:36:53,570
Tako da je n kvadrat.

988
00:36:53,570 --> 00:36:59,460
I u najboljem slučaju bubble sort,
koliko koraka će to potrajati?

989
00:36:59,460 --> 00:37:00,980
1, čuo sam.

990
00:37:00,980 --> 00:37:01,760
>> ZVUČNI 1: n.

991
00:37:01,760 --> 00:37:03,286
>> David J. Malan: n, čuo sam.

992
00:37:03,286 --> 00:37:04,200
>> ZVUČNI 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> David J. Malan: 2, čuo sam.

994
00:37:05,010 --> 00:37:06,670
Da čujem 3?

995
00:37:06,670 --> 00:37:07,080
U redu.

996
00:37:07,080 --> 00:37:11,390
Tako sam čuo jednog, n, 2, ali neka je pokupiti
osim barem prvi veliki

997
00:37:11,390 --> 00:37:12,330
prijedlozi, 1.

998
00:37:12,330 --> 00:37:15,370
To nije loša instinkt, jer je to
vrsta slijedi uzorak ovdje.

999
00:37:15,370 --> 00:37:19,670
No, ako to traje samo jedan korak, kako u
Svijet bi ja tvrdim da je popis

1000
00:37:19,670 --> 00:37:22,900
je riješeno, jer ako sam se samo smijem
uzeti jedan korak, kako su mnogi elementi

1001
00:37:22,900 --> 00:37:25,230
mogao sam zapravo da provjerite?

1002
00:37:25,230 --> 00:37:28,270
Pa, samo jedan, što znači da je n
minus 1 elemenata koji bi mogli biti izvan

1003
00:37:28,270 --> 00:37:31,310
bi, a ja samo idem na vjeri nakon
gleda na jedan element koji

1004
00:37:31,310 --> 00:37:31,850
stvar je riješeno.

1005
00:37:31,850 --> 00:37:33,930
Dakle 1 nije točno ovdje.

1006
00:37:33,930 --> 00:37:35,710
Dakle, minimalno, koliko je
moram pogledati?

1007
00:37:35,710 --> 00:37:36,680
>> [Pridodati glasovima]

1008
00:37:36,680 --> 00:37:40,160
>> David J. Malan: n minus 1, ili stvarno,
n, jer moram gledati na svaku

1009
00:37:40,160 --> 00:37:42,190
elementa kako bi bili sigurni da
to nije izvan reda.

1010
00:37:42,190 --> 00:37:44,750
Ali opet, mi ćemo riješiti naše vala
Ruke u manjim brojevima i

1011
00:37:44,750 --> 00:37:47,100
Pretpostavljam da je, kao n dobiva veliki, oni su
nezanimljivo svejedno.

1012
00:37:47,100 --> 00:37:48,380
Dakle, to je neka vrsta balon.

1013
00:37:48,380 --> 00:37:49,830
A sada, idemo napraviti ta dva.

1014
00:37:49,830 --> 00:37:53,520
Izbor sortirati, a zatim ćemo
učinite unosa vrsta.

1015
00:37:53,520 --> 00:37:57,160
A onda ćemo puhati
umovi s nešto više

1016
00:37:57,160 --> 00:37:58,926
bolje od svih ovih.

1017
00:37:58,926 --> 00:38:00,410
U redu.

1018
00:38:00,410 --> 00:38:04,700
>> Što je najgori slučaj pokrenut
vrijeme odabira vrste?

1019
00:38:04,700 --> 00:38:05,680
>> ZVUČNI 4: n kvadrat.

1020
00:38:05,680 --> 00:38:06,710
>> David J. Malan: n kvadrat, čujem.

1021
00:38:06,710 --> 00:38:09,790
Ali zašto n kvadrat, intuitivno?

1022
00:38:09,790 --> 00:38:11,170
>> ZVUČNI 4: Budući da smo upravo to učinio.

1023
00:38:11,170 --> 00:38:12,260
>> David J. Malan: Jer smo upravo to učinio.

1024
00:38:12,260 --> 00:38:12,550
OK.

1025
00:38:12,550 --> 00:38:13,380
Dobar odgovor.

1026
00:38:13,380 --> 00:38:16,660
Ali intuitivno, zašto je izbor
sortiranje n na kvadrat?

1027
00:38:16,660 --> 00:38:18,980
Što moramo učiniti
opet i opet?

1028
00:38:18,980 --> 00:38:22,570
Imali smo zadržati skenirati, su
što najmanja, jesi li

1029
00:38:22,570 --> 00:38:24,020
Najmanji, ti najmanji.

1030
00:38:24,020 --> 00:38:27,480
I gotovo, bili smo u mogućnosti da se n
koraka, a zatim n minus 1, a zatim n minus 2.

1031
00:38:27,480 --> 00:38:30,700
Ali ako vrsta dodati one sve gore,
ili ga odvesti na vjeri koje sam dodao

1032
00:38:30,700 --> 00:38:34,810
ih se unaprijed, dobili smo oko n
kvadrat minus nekim manjim brojevima.

1033
00:38:34,810 --> 00:38:36,730
Pa ću nazvati ovo n na kvadrat.

1034
00:38:36,730 --> 00:38:39,530
No, s odabira vrste u najboljem
slučaj, koliko koraka je

1035
00:38:39,530 --> 00:38:40,632
da će me odvesti?

1036
00:38:40,632 --> 00:38:41,840
>> ZVUČNI 5: [nečujno]

1037
00:38:41,840 --> 00:38:44,350
>> David J. Malan: To je, nažalost
Još uvijek n kvadrat, zar ne?

1038
00:38:44,350 --> 00:38:49,590
Jer ako sam odabirom najmanji
elementa, a imali smo sedam ljudi ovdje,

1039
00:38:49,590 --> 00:38:53,280
Ja samo znam, kad sam doći do vrlo
na kraju, da sam pronašao najmanja

1040
00:38:53,280 --> 00:38:55,670
broj, gdje god on ili
je mogla biti.

1041
00:38:55,670 --> 00:38:58,820
Ali kako ću pronaći sljedeći
Najmanji broj?

1042
00:38:58,820 --> 00:39:00,160
Moram napraviti još točno.

1043
00:39:00,160 --> 00:39:04,810
Dakle, u najboljem slučaju, ono što je
Ulaz u izbor vrste?

1044
00:39:04,810 --> 00:39:07,830
To je već neka vrsta popisa, broj jedan,
broj dva, broj tri, broj četiri.

1045
00:39:07,830 --> 00:39:08,600
Ali ja sam računalo.

1046
00:39:08,600 --> 00:39:10,190
Ja se samo mogu pogledati jedan
stvar u isto vrijeme.

1047
00:39:10,190 --> 00:39:12,465
Ja se ne mogu razvrstati mjesta uzeti jedan korak
vratio kao čovjeka i kažu,

1048
00:39:12,465 --> 00:39:14,030
ooo, ovo izgleda točna.

1049
00:39:14,030 --> 00:39:17,580
>> Ja samo mogu presuditi u ispravnost
Izbor svojevrsni odabirom

1050
00:39:17,580 --> 00:39:18,370
Najmanji broj.

1051
00:39:18,370 --> 00:39:21,390
No, čak i ako nađem broj jedan prvi,
ako ja ne znam ništa drugo o

1052
00:39:21,390 --> 00:39:24,460
ostali brojevi, koji sam Ne, sve sam
znam da sam predao niz

1053
00:39:24,460 --> 00:39:27,930
ili skup vrata iza kojih se
brojevi, jedini način znam da je jedan

1054
00:39:27,930 --> 00:39:28,680
bio najmanji?

1055
00:39:28,680 --> 00:39:32,440
Ako sam se do ovdje i ostvariti,
damn, jedna je doista najmanja.

1056
00:39:32,440 --> 00:39:34,870
>> Ali kako sam onda odrediti koji
dva je sljedeća najmanja?

1057
00:39:34,870 --> 00:39:38,350
Na taj isti neučinkovitost
opet i opet.

1058
00:39:38,350 --> 00:39:42,210
Pa napokon, s ugradnjom vrste,
kako se, u najgorem slučaju,

1059
00:39:42,210 --> 00:39:44,990
Jesmo li reći to obavlja?

1060
00:39:44,990 --> 00:39:49,100
To je previše n kvadrat.

1061
00:39:49,100 --> 00:39:53,020
A što je s najboljem slučaju?

1062
00:39:53,020 --> 00:39:56,282
Ostavit ćemo to kao Cliffhanger.

1063
00:39:56,282 --> 00:40:00,090
Mi ćemo ispuniti taj prazan sljedeći put,
ali prvo neka mi predložiti da se

1064
00:40:00,090 --> 00:40:02,620
bitno bolje od
sve to, u redu?

1065
00:40:02,620 --> 00:40:05,220
>> Tako misle za sebe ono umetanja
sortiranje će biti.

1066
00:40:05,220 --> 00:40:06,910
Pa, to nije bilo vrlo dramatično,
jer ja sam samo jedan

1067
00:40:06,910 --> 00:40:08,970
da je vidio promjenu.

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
Dakle, ovdje imamo nešto
različite demonstracije.

1071
00:40:12,615 --> 00:40:16,580
Ako sam zumirati ovdje, vidjet ćete da se na
lijeva imamo mjehurić vrsta, u

1072
00:40:16,580 --> 00:40:20,740
Srednji imamo izbor vrsta, a na
desni, imamo nešto što

1073
00:40:20,740 --> 00:40:23,380
nisu gledali na još
zove spajanje vrsta.

1074
00:40:23,380 --> 00:40:26,080
No, razmislite o tome što smo bili
radiš ovdje do sada još danas.

1075
00:40:26,080 --> 00:40:29,200
Kad Jennifer prvi put došao na pozornicu,
smo prošli kroz niz brojeva

1076
00:40:29,200 --> 00:40:33,750
opet, i opet, s linearno pretraživanje,
i dobili smo linearno vrijeme rada, big O

1077
00:40:33,750 --> 00:40:35,100
n, da se tako izrazim.

1078
00:40:35,100 --> 00:40:41,000
>> Kad smo sada razmotriti prvi tjedan
klase, kada smo podijeli pa vladaj,

1079
00:40:41,000 --> 00:40:43,740
i imali smo telefonski imenik suzenje,
i Jennifer, a mi kolektivno

1080
00:40:43,740 --> 00:40:47,500
utjecati na ključna uvid, što je za
se ponoviti opet i opet

1081
00:40:47,500 --> 00:40:50,930
nekako bacanja, bacanja,
bacanja, polovica problema, ili

1082
00:40:50,930 --> 00:40:55,320
općenito, dijeljenjem problem na pola,
a zatim tretiranje manji dio

1083
00:40:55,320 --> 00:40:59,630
Problem su konceptualno odgovara
za druge, nekako smo učinili

1084
00:40:59,630 --> 00:41:00,910
bitno bolje.

1085
00:41:00,910 --> 00:41:04,720
No, s bubble sort, uz izbor
sortiranje, s ugradnjom vrste, mi smo svibanj

1086
00:41:04,720 --> 00:41:06,560
nema takvih saznanja da je Jennifer učinio.

1087
00:41:06,560 --> 00:41:10,220
Mi prilično jednostavno vratio i
naprijed cijela hrpa vremena, a mi

1088
00:41:10,220 --> 00:41:12,650
praćka stvari malo, zamjene
u tom cilju, možda

1089
00:41:12,650 --> 00:41:13,730
umetanja ili odabirom.

1090
00:41:13,730 --> 00:41:16,950
Ali na kraju dana, ja sam puno
od nezgodnom hodanjem.

1091
00:41:16,950 --> 00:41:21,160
Mi zapravo nije nešto utjecati
pametna kao što je Jennifer poput dijeljenja

1092
00:41:21,160 --> 00:41:22,040
i osvajanje.

1093
00:41:22,040 --> 00:41:25,620
>> Dakle spojiti neku, za razliku od, koji mi
neće vidjeti do sljedećeg tjedna, to se događa

1094
00:41:25,620 --> 00:41:29,540
utjecati na ključna ideja dijeljenjem
ulaz, a zatim na pola, a zatim

1095
00:41:29,540 --> 00:41:30,580
na pola, a zatim prepoloviti.

1096
00:41:30,580 --> 00:41:34,590
I na svakoj iteraciji tog petlje,
sortiranje lijevu polovicu, kao i pravo

1097
00:41:34,590 --> 00:41:38,200
pola, zatim lijevu polovicu lijeve polovice,
i desnu polovicu lijeve strane, a zatim

1098
00:41:38,200 --> 00:41:40,990
lijeva polovica desne polovice i
pravo polovice desne polovice.

1099
00:41:40,990 --> 00:41:42,840
I ponavlja opet i opet.

1100
00:41:42,840 --> 00:41:46,170
>> Dakle, vidjet ćete ovo vizualno, ali ovo
je ono što nas čeka sljedeći tjedan.

1101
00:41:46,170 --> 00:41:49,760
I općenito, kada mislimo malo
malo teže na bilo takvih problema.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Mi smo n kvadrat na lijevoj strani, n
kvadrat u sredini, a n

1104
00:41:57,970 --> 00:41:59,400
log n na desnoj strani.

1105
00:41:59,400 --> 00:42:00,590
Tako da je tvoj pravi roman u nastavcima.

1106
00:42:00,590 --> 00:42:02,040
Vidimo se u ponedjeljak.

1107
00:42:02,040 --> 00:42:05,163
>> [PLJESAK]