1
00:00:00,000 --> 00:00:11,100
>> [Přehrávání hudby]

2
00:00:11,100 --> 00:00:11,490
>> David J. Malan: Dobře.

3
00:00:11,490 --> 00:00:12,170
Tak vítej zpět.

4
00:00:12,170 --> 00:00:15,180
To je CS50, a je
Konec týdne tři.

5
00:00:15,180 --> 00:00:17,770
>> Takže připomínají v posledních několika týdnech,
jsme strávili docela dost

6
00:00:17,770 --> 00:00:20,820
čas na C, na programování, na syntaxi.

7
00:00:20,820 --> 00:00:24,680
A to je docela normální, pokud jste ještě
zápasí s problémovými Set 2, se

8
00:00:24,680 --> 00:00:25,950
bouchání hlavou proti zdi.

9
00:00:25,950 --> 00:00:28,310
Je to tajemné vypadající chybové zprávy
a chyby, které

10
00:00:28,310 --> 00:00:29,220
nelze zcela honit.

11
00:00:29,220 --> 00:00:32,310
Vzhledem k tomu, být jisti, že právě
Doba pár týdnů budete ohlížet na

12
00:00:32,310 --> 00:00:35,930
věci jako Caesara a [? V-genair,?]
možná i Crack a

13
00:00:35,930 --> 00:00:40,050
uvědomit si, jak daleko jste přišli
v krátkém časovém období.

14
00:00:40,050 --> 00:00:43,670
Takže jestli je to nějaká útěcha,
vydrž teď.

15
00:00:43,670 --> 00:00:46,610
>> V současné době se však začneme přechod
na věci vyšší úrovně.

16
00:00:46,610 --> 00:00:49,820
A začneme brát za samozřejmost, že
vy víte, jak programovat, nebo

17
00:00:49,820 --> 00:00:52,090
nejméně počátky
že úroveň pohodlí.

18
00:00:52,090 --> 00:00:56,520
A začneme uvažovat o tom, jak můžeme
jít o navrhování programů více

19
00:00:56,520 --> 00:00:57,440
efektivně.

20
00:00:57,440 --> 00:01:01,090
Jak můžeme jít o optimalizaci
Účinnost našich algoritmů a

21
00:01:01,090 --> 00:01:03,110
obecně více řešení
zajímavé problémy.

22
00:01:03,110 --> 00:01:06,850
A začínají brát za samozřejmost, že
kdybychom chtěli, mohli bychom kódu vzestupně každý

23
00:01:06,850 --> 00:01:08,350
z příkladů, které máme na mysli.

24
00:01:08,350 --> 00:01:11,430
Takže dnes jsme se nedotýkejte klávesnice
pro jakékoli formě kódu.

25
00:01:11,430 --> 00:01:15,150
To bude mnohem vyšší úroveň, a
nakonec, o řešení problémů.

26
00:01:15,150 --> 00:01:20,490
>> Takže se dostat do tohoto bodu, dovolte mi navrhnout
že následující sedm

27
00:01:20,490 --> 00:01:24,290
obdélníky představují sedm dveře, za
které jsou celá parta

28
00:01:24,290 --> 00:01:26,340
čísla, mezi nimiž je číslo 50.

29
00:01:26,340 --> 00:01:30,470
Dovolte mi, abych to promítnout na tomto
displej i zde.

30
00:01:30,470 --> 00:01:36,770
A navrhnout, že potřebujeme dobrovolníka
pomůže mi najít číslo před

31
00:01:36,770 --> 00:01:38,140
internet zde.

32
00:01:38,140 --> 00:01:40,755
Pojďte nahoru, v růžové.

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

34
00:01:43,050 --> 00:01:43,930
Jak se jmenujete?

35
00:01:43,930 --> 00:01:44,850
>> JENNIFER: [neslyšitelné]

36
00:01:44,850 --> 00:01:45,170
>> David J. Malan: Je nám líto?

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
Dobře, Jennifer.

40
00:01:46,980 --> 00:01:47,630
Rád Vás vidím.

41
00:01:47,630 --> 00:01:48,370
Pojď nahoru.

42
00:01:48,370 --> 00:01:52,430
Tak to zde je sedm dveří, a to, co
Chtěl bych, abys pro nás,

43
00:01:52,430 --> 00:01:56,560
v přední části všech vašich spolužáků,
se k nám dostanete číslo, 50.

44
00:01:56,560 --> 00:02:00,860
Chcete-li najít číslo, můžete nahlédnout za
některé z těchto dveří pouhým poklepáním

45
00:02:00,860 --> 00:02:03,030
na jedné straně dveří, a to
odhalí jeho číslo.

46
00:02:03,030 --> 00:02:06,080
A podívejme se, jak rychle se
Najdete u nás číslo, 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
Dobrá práce.

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

55
00:02:18,040 --> 00:02:19,906
Potlesk pro Jennifer.

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

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

58
00:02:22,320 --> 00:02:25,254
Tak jaká byla vaše strategie pro
najít číslo 50?

59
00:02:25,254 --> 00:02:27,222
>> JENNIFER: Hm, myslela jsem, že pokud -

60
00:02:27,222 --> 00:02:27,714
[Neslyšitelný]

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

62
00:02:28,206 --> 00:02:29,630
Dejte mu jednu sekundu.

63
00:02:29,630 --> 00:02:32,420
Tak byla vaše strategie pro
najít číslo 50?

64
00:02:32,420 --> 00:02:34,760
>> JENNIFER: Tak jsem se začít na
začíná vidět, co první číslo

65
00:02:34,760 --> 00:02:38,590
byl, a pak jsem si myslel, možná, pokud
oni jsou řazeny, budu jen držet

66
00:02:38,590 --> 00:02:39,970
klepnutím výš?

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

68
00:02:40,140 --> 00:02:42,910
A zdá se, že našli
že tomu tak je.

69
00:02:42,910 --> 00:02:45,670
I když, pojďme Sloupněte vrstvy
jen trochu, a vy chcete jít

70
00:02:45,670 --> 00:02:47,640
dopředu a odhalit další dveře
si mohl vybrat?

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

72
00:02:50,400 --> 00:02:51,712
>> JENNIFER: Ach jo.

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

74
00:02:53,128 --> 00:02:54,280
>> JENNIFER: Tak jsem měl štěstí.

75
00:02:54,280 --> 00:02:55,270
>> David J. Malan: Takže máš štěstí.

76
00:02:55,270 --> 00:02:55,710
Dobrá.

77
00:02:55,710 --> 00:02:56,795
Takže to není špatné.

78
00:02:56,795 --> 00:02:58,750
Ale to je zajímavé,
pohled, ne?

79
00:02:58,750 --> 00:03:01,870
Máte-li předpokládat, a vy jste se,
opravdu, trochu štěstí tam.

80
00:03:01,870 --> 00:03:05,350
Ale pokud se předpokládá, že tato čísla
tříděny, můžete být přesnější

81
00:03:05,350 --> 00:03:08,750
jak který ovlivnil
vaše chování?

82
00:03:08,750 --> 00:03:11,715
>> JENNIFER: Takže pokud by byly roztříděny, jsem
si myslel, že nejmenší k největší.

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

84
00:03:11,970 --> 00:03:15,260
>> JENNIFER: Nebo, pokud to skončilo jako bytí
opravdu velké, pak největší k nejmenší.

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

86
00:03:15,540 --> 00:03:18,170
Takže největší k nejmenší, nebo
nejmenší k největší.

87
00:03:18,170 --> 00:03:21,990
Ale dovolte mi navrhnout, že byste měli
dostali nešťastný, a předpokládáme, že

88
00:03:21,990 --> 00:03:26,840
nebyla ve skutečnosti, třídění, kolik
ty dveře by jste měli nahlédnout

89
00:03:26,840 --> 00:03:28,590
pozadu v tomto nejhorším případě?

90
00:03:28,590 --> 00:03:29,860
>> JENNIFER: Všechny z nich.

91
00:03:29,860 --> 00:03:30,420
>> David J. Malan: Všechny z nich.

92
00:03:30,420 --> 00:03:31,740
Takže pojďme se zobecnit, že pro n.

93
00:03:31,740 --> 00:03:34,790
Tam se stane být 7, ale pojďme se více
se obecně říci, že je to n dveře na

94
00:03:34,790 --> 00:03:35,650
screen zde.

95
00:03:35,650 --> 00:03:40,110
Takže v nejhorším případě, měli byste
nahlédnout za dveře, 7 nebo N dveří.

96
00:03:40,110 --> 00:03:44,140
A tak to je opravdu, je to trochu
štěstí dnes, ale je to opravdu lineární

97
00:03:44,140 --> 00:03:46,440
algoritmus druhů, i když jste
milý přeskočení kolem.

98
00:03:46,440 --> 00:03:47,080
Je to fér?

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

100
00:03:47,500 --> 00:03:50,000
>> David J. Malan: No, dovolte mi, zda váš
strategie změny, když nás posunou

101
00:03:50,000 --> 00:03:52,190
náš druhý příklad zde
7 různých dveře.

102
00:03:52,190 --> 00:03:55,240
Stejná čísla, ale
čas jsou řazeny.

103
00:03:55,240 --> 00:03:58,350
Jaká je vaše strategie zde bude,
snaží dát ze své mysli, co

104
00:03:58,350 --> 00:03:59,310
jiná čísla byla -

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

106
00:03:59,930 --> 00:04:02,290
>> David J. Malan: - dřív?

107
00:04:02,290 --> 00:04:03,180
>> JENNIFER: Začněme
s prvním.

108
00:04:03,180 --> 00:04:03,540
>> David J. Malan: Dobře.

109
00:04:03,540 --> 00:04:05,190
Začněte s první.

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

111
00:04:05,960 --> 00:04:08,810
Nyní, kam jít, a proč?

112
00:04:08,810 --> 00:04:10,040
>> JENNIFER: 4 je opravdu malá.

113
00:04:10,040 --> 00:04:12,500
Takže když tak trochu možná nejmenší
po největší, měla by být

114
00:04:12,500 --> 00:04:13,290
se dvakrát, a -.

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

116
00:04:13,670 --> 00:04:15,990
Pojďme se podívat, které si myslíte?

117
00:04:15,990 --> 00:04:19,050
>> JENNIFER: Zkuste ten poslední.

118
00:04:19,050 --> 00:04:19,500
Pěkný.

119
00:04:19,500 --> 00:04:20,880
>> David J. Malan: Velmi pěkně udělal.

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

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

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

123
00:04:24,310 --> 00:04:26,790
Takže jste vlastně děláš
hrozně, protože jsi

124
00:04:26,790 --> 00:04:27,700
dělá to velmi dobře.

125
00:04:27,700 --> 00:04:31,150
Což nám dává schopen
provést určité body.

126
00:04:31,150 --> 00:04:32,565
Zkusme se vrátit zpátky.

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

128
00:04:34,560 --> 00:04:35,980
>> David J. Malan: Velmi dobře
práce, nicméně.

129
00:04:35,980 --> 00:04:39,060
Takže jste začal na začátku,
jsi viděl, že to bylo 4, pak

130
00:04:39,060 --> 00:04:40,240
přesunut na konec.

131
00:04:40,240 --> 00:04:42,320
Ale předpokládejme, že jste neměli štěstí
tam, a předpokládejme, 50

132
00:04:42,320 --> 00:04:42,890
někde jinde.

133
00:04:42,890 --> 00:04:46,190
Co si Třetím krokem bylo?

134
00:04:46,190 --> 00:04:47,680
>> JENNIFER: Vraťte se zpět na začátek.

135
00:04:47,680 --> 00:04:48,320
>> David J. Malan: Jít zpět
na začátek.

136
00:04:48,320 --> 00:04:51,320
OK, takže byste se na to dotkl
tyto dveře, což bylo 8..

137
00:04:51,320 --> 00:04:51,660
Dobrá.

138
00:04:51,660 --> 00:04:52,650
Takže to není 50.

139
00:04:52,650 --> 00:04:55,380
Kam by jste se podíval dál?

140
00:04:55,380 --> 00:04:56,720
>> JENNIFER: Pokud jsem to neudělal
vědí, že řazeny.

141
00:04:56,720 --> 00:04:57,005
>> David J. Malan: Správně.

142
00:04:57,005 --> 00:04:58,490
No, pokud jste vědět
byly zařazeny -

143
00:04:58,490 --> 00:04:58,700
>> JENNIFER: Jo, to vím, jo.

144
00:04:58,700 --> 00:05:00,910
>> David J. Malan - ale ne
vědět, kde 50 byl ještě?

145
00:05:00,910 --> 00:05:01,785
>> JENNIFER: Jen pokračuj.

146
00:05:01,785 --> 00:05:02,130
>> David J. Malan: Dobře.

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

148
00:05:02,520 --> 00:05:03,800
Jen tak dál.

149
00:05:03,800 --> 00:05:05,270
OK, že mohu pracovat.

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

151
00:05:05,610 --> 00:05:07,210
>> David J. Malan: Teď, když jste jen
bude dál, jaký je váš

152
00:05:07,210 --> 00:05:09,680
Algoritmus připadající couval do.

153
00:05:09,680 --> 00:05:10,740
>> JENNIFER: Lineární -.

154
00:05:10,740 --> 00:05:11,820
>> David J. Malan: Je to tak trochu lineární.

155
00:05:11,820 --> 00:05:13,480
Ale dovolte mi navrhnout, ať
mi, abych dal na místě.

156
00:05:13,480 --> 00:05:14,900
Dovolte mi, abych aktualizujte stránku.

157
00:05:14,900 --> 00:05:17,120
stejné číslo, stejné uspořádání,
Stejné dveře.

158
00:05:17,120 --> 00:05:21,350
Ale si vzpomenu na ten první den v
třídy, když vytrhl telefonní seznam ve

159
00:05:21,350 --> 00:05:25,480
poloviny, tak nějak, a to, co bylo
naše strategie tam?

160
00:05:25,480 --> 00:05:26,450
>> JENNIFER: Začněte u středu.

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

162
00:05:26,690 --> 00:05:27,610
Takže začít v polovině.

163
00:05:27,610 --> 00:05:28,790
Tak pojďme dál a simulovat to.

164
00:05:28,790 --> 00:05:30,720
Začněte u středu
ukázat, že dveře.

165
00:05:30,720 --> 00:05:31,660
Takže číslo 16.

166
00:05:31,660 --> 00:05:35,290
Takže to, co by udělal silný chlap,
který trhal telefonní seznam na polovinu,

167
00:05:35,290 --> 00:05:38,450
se dostanete do další hádat?

168
00:05:38,450 --> 00:05:39,400
>> JENNIFER: Jdi v této polovině.

169
00:05:39,400 --> 00:05:41,700
>> David J. Malan: A proč na pravé straně?

170
00:05:41,700 --> 00:05:43,900
>> JENNIFER: Pokud by byly nějak nejmenší
po největší, pak by měla být 50

171
00:05:43,900 --> 00:05:44,720
na tento účel.

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

173
00:05:44,920 --> 00:05:45,390
Naprosto rozumné.

174
00:05:45,390 --> 00:05:48,380
Tak jako telefonní seznam, můžete jít do
právo na rozdíl od levé straně, ale zde

175
00:05:48,380 --> 00:05:49,500
je klíčem stánek s jídlem.

176
00:05:49,500 --> 00:05:53,930
Nyní můžete vyhodit, nebo odtrhnout,
polovina tohoto problému, takže vám nebude

177
00:05:53,930 --> 00:05:55,970
s 7 dveří, ale ve skutečnosti se jen tři.

178
00:05:55,970 --> 00:05:57,870
Což je zhruba polovina
Velikost problému.

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

180
00:05:58,350 --> 00:06:01,890
Takže teď, co byste si
provedeno po přechodu ne?

181
00:06:01,890 --> 00:06:05,870
>> JENNIFER: Takže 16 je ještě docela malý,
vzhledem k 50, takže možná se budu snažit,

182
00:06:05,870 --> 00:06:06,700
podobně, je tento.

183
00:06:06,700 --> 00:06:07,890
>> David J. Malan: Dobře.

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

185
00:06:08,720 --> 00:06:10,830
Dobře, tak teď to, co je vaše
instinkt ti?

186
00:06:10,830 --> 00:06:12,100
>> JENNIFER: Mohu vyhodit
to a pak už jen -

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

188
00:06:12,360 --> 00:06:14,212
Dobrá, můžete zahodit
levá polovina tam.

189
00:06:14,212 --> 00:06:14,890
>> JENNIFER: - vyberte jeden.

190
00:06:14,890 --> 00:06:15,530
>> David J. Malan: A pravdu.

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

192
00:06:15,760 --> 00:06:17,820
>> David J. Malan: Takže i když je to těžké
vidět snad, když je tu jen

193
00:06:17,820 --> 00:06:21,320
7 dveří, přemýšlet o tom, teď,
konzistence

194
00:06:21,320 --> 00:06:22,620
Algoritmus stačí aplikovat.

195
00:06:22,620 --> 00:06:24,510
V předchozím případě, jste
štěstí, což bylo skvělé.

196
00:06:24,510 --> 00:06:26,540
Ale jste použít heuristiku,
Řekl bych, že.

197
00:06:26,540 --> 00:06:29,150
Můžete použít třídění vašich instinktů, a
věděl, že řazeny, jestli je to dost

198
00:06:29,150 --> 00:06:31,600
malá na začátku, samozřejmě, máme
jít víc doprava.

199
00:06:31,600 --> 00:06:34,990
Ale v jistém smyslu, máš štěstí,
protože možná to bylo číslo 100,

200
00:06:34,990 --> 00:06:36,220
a možná i 50 byl více ve středu.

201
00:06:36,220 --> 00:06:37,910
Možná, že 50 je ještě tady.

202
00:06:37,910 --> 00:06:40,960
>> Ale to, co jsi udělal trochu jinak
Tentokrát byl jsi udělal to samé

203
00:06:40,960 --> 00:06:42,150
znovu a znovu.

204
00:06:42,150 --> 00:06:45,310
A já bych tvrdit, že to, co jste právě
to, i když vliv na telefonu

205
00:06:45,310 --> 00:06:48,100
Kniha příklad, je něco mnohem
více algoritmické a mnohem

206
00:06:48,100 --> 00:06:49,930
méně speciální pouzdrem.

207
00:06:49,930 --> 00:06:51,620
Mnohem méně instinktivní.

208
00:06:51,620 --> 00:06:57,160
Takže na konci dne, jak by
můžete popsat účinnost

209
00:06:57,160 --> 00:07:00,530
První algoritmus, kde se stala
zleva doprava, ve srovnání

210
00:07:00,530 --> 00:07:03,430
Druhý algoritmus tady?

211
00:07:03,430 --> 00:07:06,460
>> JENNIFER: tohle by měl, stejně jako, možná
polovinu času, nebo dokonce více, jo.

212
00:07:06,460 --> 00:07:07,320
>> David J. Malan: OK, možná ještě víc.

213
00:07:07,320 --> 00:07:10,150
Pojďme se tlačit trochu víc na to.

214
00:07:10,150 --> 00:07:13,030
Co se opravdu, pokud budeme pokračovat v této
logika, rozhodně polovinu

215
00:07:13,030 --> 00:07:15,830
doba chodu tohoto druhého algoritmu
by zahodili polovinu

216
00:07:15,830 --> 00:07:18,470
čísla, ale co budeme dělat na příští
iterace, když Jennifer odhalil

217
00:07:18,470 --> 00:07:20,615
druhé číslo?

218
00:07:20,615 --> 00:07:22,830
>> Jsme na polovinu počtu dveří znovu.

219
00:07:22,830 --> 00:07:25,270
A pak to, co jsme udělali po tom, je-li
tam bylo více vrata na hraní?

220
00:07:25,270 --> 00:07:27,520
Rádi bychom snížit je, a znovu,
a znovu a znovu.

221
00:07:27,520 --> 00:07:30,420
A to bylo jen jako vy všichni
vstávání v prvním týdnu

222
00:07:30,420 --> 00:07:33,000
třídy, polovina z vás sedět, polovina
z vás sedět, polovina z vás

223
00:07:33,000 --> 00:07:35,440
sedět, dokud jeden osamělý
duše stála.

224
00:07:35,440 --> 00:07:39,050
A my jsme řekli, že doba chodu
, že počet kroků Stačilo

225
00:07:39,050 --> 00:07:40,430
na pořadí, co?

226
00:07:40,430 --> 00:07:41,230
>> SPEAKER 1: [neslyšitelné]

227
00:07:41,230 --> 00:07:43,970
>> David J. Malan: Takže log základna 2 n,
nebo jen jednodušeji, přihlaste n.

228
00:07:43,970 --> 00:07:45,060
Takže něco logaritmická.

229
00:07:45,060 --> 00:07:48,380
A graf nebyl přímka
že právě dostal horší a horší, to bylo

230
00:07:48,380 --> 00:07:52,490
tento zajímavý křivka, která ne
tak zle v průběhu času.

231
00:07:52,490 --> 00:07:53,910
Takže pojďme se držet na této myšlence.

232
00:07:53,910 --> 00:07:54,690
Poděkujme Jennifer.

233
00:07:54,690 --> 00:07:56,150
Díky moc za účast nahoru.

234
00:07:56,150 --> 00:07:57,400
A jeden s.

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

236
00:08:00,170 --> 00:08:02,925
Žádné stolní lampy dnes, ale
přece mají CS50 stres koule.

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

238
00:08:03,420 --> 00:08:04,410
>> David J. Malan: Tak jo, tady.

239
00:08:04,410 --> 00:08:06,545
Děkuji za vynaložení
stres tady.

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

241
00:08:07,350 --> 00:08:10,620
Tak uvidíme, když ne teď
formalizovat to trochu víc.

242
00:08:10,620 --> 00:08:14,820
Takže znovu, co jsme právě udělali, bylo
v podstatě totéž jako my

243
00:08:14,820 --> 00:08:16,660
v tomto prvním týdnu.

244
00:08:16,660 --> 00:08:23,780
Ale spíše než nakonec jen s lineární
algoritmus, které je znázorněno

245
00:08:23,780 --> 00:08:27,210
dříve jako tento přímce,
kdy, když dáme ještě jednu dveře

246
00:08:27,210 --> 00:08:29,610
obrazovka, pak by Jennifer
musel se dívat, potenciálně

247
00:08:29,610 --> 00:08:30,600
za jeden další dveře.

248
00:08:30,600 --> 00:08:33,490
Pokud dáme dvě dveře, mohla by mít
aby se za další dvě dveře.

249
00:08:33,490 --> 00:08:35,990
>> A tak, že se tento lineární
vztah mezi velikostí

250
00:08:35,990 --> 00:08:39,059
problém na, řekněme, x-osy a
množství času, které trvá

251
00:08:39,059 --> 00:08:40,440
řešení na y.

252
00:08:40,440 --> 00:08:43,330
Ale obraz byl jsem narážel na
dříve byla tato zelená linka.

253
00:08:43,330 --> 00:08:45,970
Zelená záměrně, protože
to prostě cítil lépe.

254
00:08:45,970 --> 00:08:49,790
Teoreticky algoritmus, když jsme to udělali
s telefonního seznamu, když jsme to udělali

255
00:08:49,790 --> 00:08:52,420
s vámi počítat sebe, a
V druhém případě, kdy právě Jennifer

256
00:08:52,420 --> 00:08:55,250
udělal to tady, to bylo něco
o zásadně lepší.

257
00:08:55,250 --> 00:08:57,180
Vzhledem k tomu, že to není jen dvakrát tak rychle.

258
00:08:57,180 --> 00:08:58,870
Nebylo to ani čtyřikrát rychle.

259
00:08:58,870 --> 00:09:03,290
To bylo zcela závislé na tom, co
velikost vstupu bylo, pokud jde o to, kolik

260
00:09:03,290 --> 00:09:05,220
kroky, které nakonec trvalo.

261
00:09:05,220 --> 00:09:08,040
>> A tak to jednoduchá myšlenka, že jsme všichni vzali
za samozřejmost, se v telefonním seznamu,

262
00:09:08,040 --> 00:09:10,200
dokument může být rovněž použita
něco jako tohle.

263
00:09:10,200 --> 00:09:12,380
A to by mohlo být více uvolněně
známý jako, jak byste si mohli

264
00:09:12,380 --> 00:09:13,940
představit, rozděl a panuj.

265
00:09:13,940 --> 00:09:16,390
Ne na rozdíl od toho, co jsme udělali, samozřejmě,
s telefonního seznamu.

266
00:09:16,390 --> 00:09:18,300
>> Ale pseudokódu, odvolání, to bylo.

267
00:09:18,300 --> 00:09:21,800
Tak jsme se to udělat znovu, ale vzpomínám
že první týden, všichni z nás vstal

268
00:09:21,800 --> 00:09:25,140
a polovina z vás se posadil, polovina
si sedl, polovina z vás se posadil.

269
00:09:25,140 --> 00:09:29,280
Že algoritmus byl implementován v
trochu podvádění způsobem, že to

270
00:09:29,280 --> 00:09:32,870
Nebylo to jen jeden z mnou počítat,
Podstatnější je, že efektivněji.

271
00:09:32,870 --> 00:09:35,830
V tomto případě jsem se využití
sekundární zdroj.

272
00:09:35,830 --> 00:09:39,470
Něco, více procesory, více mozek,
více chytrých lidí ve

273
00:09:39,470 --> 00:09:42,740
pokoj byl mi pomohl dostat se z něčeho
lineární něco

274
00:09:42,740 --> 00:09:45,190
logaritmická, z něčeho
červené na něco zeleného.

275
00:09:45,190 --> 00:09:48,650
>> Ale v tomto případě, může Jennifer sama
zásadně zlepšit na

276
00:09:48,650 --> 00:09:52,370
výkon její první algoritmus,
Znovu jsem přemýšlel o něco těžší.

277
00:09:52,370 --> 00:09:56,650
A teď, když přijde čas na provedení
tyto věci, přijít na to,

278
00:09:56,650 --> 00:10:00,670
jaké řádky kódu můžete psát jako
že můžete opakovat znovu a

279
00:10:00,670 --> 00:10:03,350
znovu a znovu, tak nějak
v cyklické módě.

280
00:10:03,350 --> 00:10:06,370
Protože nebudete mít
luxusní, stejně jako Jennifer to na první pohled, na

281
00:10:06,370 --> 00:10:10,460
jen spoustu IFS a říkají,
hmm, je-li to první číslo 4,

282
00:10:10,460 --> 00:10:11,800
dovolte mi, abych skok celou cestu až do konce.

283
00:10:11,800 --> 00:10:14,180
Ooh, pokud toto číslo je příliš velká,
dovolte mi, abych pohybovat libovolně zpět

284
00:10:14,180 --> 00:10:15,220
na druhý prvek.

285
00:10:15,220 --> 00:10:18,210
Zjistíte, že to bude hodně
těžší formalizovat, co my lidé

286
00:10:18,210 --> 00:10:21,270
brát za samozřejmost, za velmi rozumné
heuristiky, ale počítač je jen

287
00:10:21,270 --> 00:10:23,260
dělat to, co řeknete to udělat.

288
00:10:23,260 --> 00:10:25,280
>> Teď to má velmi zajímavé
důsledky.

289
00:10:25,280 --> 00:10:29,950
Tento graf je druh chtěl nějak
přemoci vizuálně, ale uvědomte si, kde

290
00:10:29,950 --> 00:10:32,230
je přímka v tomto grafu?

291
00:10:32,230 --> 00:10:35,330
Kde je lineární graf
které nazýváme n?

292
00:10:35,330 --> 00:10:37,580
No, je to trochu směrem ke spodní části
obrázku, ne?

293
00:10:37,580 --> 00:10:40,500
Takže všechno, co jsme udělali je, že jsme si trochu
oddálení na ose x a

294
00:10:40,500 --> 00:10:44,780
osa y pokusit se získat smysl toho, co
jiné typy křivek vypadat.

295
00:10:44,780 --> 00:10:47,760
>> A specifika matematické
výrazy dnes nebude záležet, aby

296
00:10:47,760 --> 00:10:52,440
moc, ale zjistíte, že je tu spousta
algoritmy, které jsou mnohem horší, než

297
00:10:52,440 --> 00:10:53,470
něco, co je lineární.

298
00:10:53,470 --> 00:10:55,410
Opravdu, n kostičky vypadá dost špatně.

299
00:10:55,410 --> 00:10:58,400
2 na n vypadá dost špatně.
n na druhou vypadá dost špatně.

300
00:10:58,400 --> 00:11:01,630
A uvidíme, co někteří z těch,
může být ve skutečnosti dnes.

301
00:11:01,630 --> 00:11:05,430
A log n necítí tak špatné, ale
lepší než n je základ log 2 n.

302
00:11:05,430 --> 00:11:08,080
Ale víte, to by bylo ještě
více ohromující, pokud Jennifer, nebo pokud my,

303
00:11:08,080 --> 00:11:12,910
že první týden, přišel s
něco, co je log log n.

304
00:11:12,910 --> 00:11:15,880
>> Takže jinými slovy, je to celá
Rozsah možných řešení

305
00:11:15,880 --> 00:11:18,570
problémy, ale i zde si všimněte,
co se bude dít.

306
00:11:18,570 --> 00:11:22,910
Když jsem se vzdálíte, které z těchto křivek
bude ukázat, že je absolutní

307
00:11:22,910 --> 00:11:26,630
Nejhorší z těch, na obrazovce teď?

308
00:11:26,630 --> 00:11:28,680
Tak n kostičky vypadá docela
špatně v tuto chvíli.

309
00:11:28,680 --> 00:11:32,470
Ale pokud se oddálit a vidět víc
x a osy y, kdo bude

310
00:11:32,470 --> 00:11:34,550
dominují nakonec?

311
00:11:34,550 --> 00:11:37,120
Takže to vlastně Ukazuje se, že 2 až
n, a můžete to vyřešit jen tím,

312
00:11:37,120 --> 00:11:39,990
zapojením některých stále větší
čísla, a uvidíte, že 2 až

313
00:11:39,990 --> 00:11:42,070
n, ve skutečnosti, se zvětšuje mnohem rychleji.

314
00:11:42,070 --> 00:11:45,530
Pokud opravdu vzdálíte, pro 2 až
n algoritmus absolutně nic.

315
00:11:45,530 --> 00:11:48,170
Myslím, že to bude trvat
docela dost času na

316
00:11:48,170 --> 00:11:49,460
počítač k chrlit přes.

317
00:11:49,460 --> 00:11:52,500
>> Ale uvidíte v průběhu času, a to zejména
s budoucími základní problémové okruhy a dokonce

318
00:11:52,500 --> 00:11:55,600
závěrečných prací, je vaše data
soubor dostane velký, dobře?

319
00:11:55,600 --> 00:11:58,300
I v první verzi Facebooku,
jako počet přátel, a

320
00:11:58,300 --> 00:12:01,840
Počet registrovaných uživatelů má velký,
můžete nějak telefonu jej a

321
00:12:01,840 --> 00:12:05,530
implementovat něco s lineárním vyhledávání
nebo velmi jednoduché třídění

322
00:12:05,530 --> 00:12:07,030
algoritmus, jak uvidíme dnes.

323
00:12:07,030 --> 00:12:09,280
Musíte začít přemýšlet těžší
a těžší o těchto problémech.

324
00:12:09,280 --> 00:12:12,070
A druhy problémů místech, jako je
Facebook a Google a Microsoft,

325
00:12:12,070 --> 00:12:16,350
a jiní pracují na přesně ty
druh velkého datového druhu otázek

326
00:12:16,350 --> 00:12:18,530
stále častěji v těchto dnech.

327
00:12:18,530 --> 00:12:18,900
>> Dobrá.

328
00:12:18,900 --> 00:12:23,800
Takže úspěch Jennifer v tom druhém
algoritmus, upřímně řečeno, ona překvapivě

329
00:12:23,800 --> 00:12:26,110
také poprvé, ale pojďme
napsat, že jak štěstí tak, že jsme

330
00:12:26,110 --> 00:12:27,000
může tento bod.

331
00:12:27,000 --> 00:12:30,970
V druhém případě se zadlužuje
algoritmus, který znovu a

332
00:12:30,970 --> 00:12:34,670
znovu, ale vzala za samozřejmost
jistý předpoklad, že smíme

333
00:12:34,670 --> 00:12:39,370
ní, ale ona využívány některé detaily
Podruhé, že neměla

334
00:12:39,370 --> 00:12:39,840
poprvé.

335
00:12:39,840 --> 00:12:41,800
Což je to, co?

336
00:12:41,800 --> 00:12:43,050
>> To, že byl seznam seřazen.

337
00:12:43,050 --> 00:12:46,350
Aby, jakmile byl přiřazen seznam, jsme
tvrdí, že Jennifer byl schopen udělat

338
00:12:46,350 --> 00:12:47,480
zásadně lepší.

339
00:12:47,480 --> 00:12:51,450
7 dveří, ano, není to zajímavé,
Předpokládejme však, že to, že jsme 7000000 dveře.

340
00:12:51,450 --> 00:12:54,080
Přihlásit n je určitě
provádět mnohem

341
00:12:54,080 --> 00:12:55,610
rychleji v dlouhodobém horizontu.

342
00:12:55,610 --> 00:12:58,880
Ale musela mít
Dveře řazeny pro ni.

343
00:12:58,880 --> 00:13:02,320
Teď jsem si dovolil dělat, že
předem na obrazovce počítače

344
00:13:02,320 --> 00:13:05,160
tady, ale předpokládám, že Jennifer
Musel to udělat sama?

345
00:13:05,160 --> 00:13:10,120
Předpokládejme, že dveře v otázce
zastoupeny data v databázi, nebo

346
00:13:10,120 --> 00:13:14,260
přátelé registrovaní na Facebook, nebo
všechny webové stránky na internetu, které

347
00:13:14,260 --> 00:13:16,880
různé webové stránky, může být nutné
k indexu nebo prohledávat.

348
00:13:16,880 --> 00:13:20,940
>> Předpokládejme, že jste právě měl surová data
nastavení a bylo ponecháno na vás, nebo

349
00:13:20,940 --> 00:13:23,010
Jennifer k tomu, že třídění?

350
00:13:23,010 --> 00:13:26,950
To spíše vyžaduje, abychom odpověď
otázka, no, kolik času

351
00:13:26,950 --> 00:13:31,080
by trvalo Jennifer, nebo dokonce mě,
třídit ty čísla předem, aby

352
00:13:31,080 --> 00:13:32,680
že by mohla využít, že?

353
00:13:32,680 --> 00:13:32,880
Je to tak?

354
00:13:32,880 --> 00:13:36,620
Vzhledem k tomu, důsledky, samozřejmě, je
pokud mi trvá docela dlouho, než třídění

355
00:13:36,620 --> 00:13:40,800
čísla, které to zajímá, že tě sakra
můžete najít číslo jako 50 tak rychle,

356
00:13:40,800 --> 00:13:44,850
stejně jako v případě, Jennifer, pokud se více než
ohromen množství celkového času

357
00:13:44,850 --> 00:13:46,920
trvalo třídění věci předem?

358
00:13:46,920 --> 00:13:49,320
>> Tak uvidíme, jestli nemůžeme
namalovat obraz tady.

359
00:13:49,320 --> 00:13:51,370
Mám celá parta větší důraz
koule, je-li, že pomáhá

360
00:13:51,370 --> 00:13:52,270
prolomit ledy zde.

361
00:13:52,270 --> 00:13:55,690
A pokud vám to nebude vadit, my
Potřebujete sedm dobrovolníka -

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
Takže nemáme utrácet
na stolních lampách, zdá se.

365
00:13:59,250 --> 00:13:59,690
Dobrá.

366
00:13:59,690 --> 00:14:01,530
Tak co ty dva vpředu.

367
00:14:01,530 --> 00:14:04,160
Jak se o vás dva kluci v zádech.

368
00:14:04,160 --> 00:14:04,870
Tak to je čtyři.

369
00:14:04,870 --> 00:14:09,890
Jak se o vás před
pět, šest a sedm.

370
00:14:09,890 --> 00:14:10,320
Přesně tam.

371
00:14:10,320 --> 00:14:13,260
Váš přítel se ukázal ven,
tak dostanete cenu.

372
00:14:13,260 --> 00:14:13,700
>> Dobrá.

373
00:14:13,700 --> 00:14:14,410
Pojď nahoru.

374
00:14:14,410 --> 00:14:17,120
A proč jsme si
kluci pojď sem.

375
00:14:17,120 --> 00:14:18,960
Chystám se vám každé číslo.

376
00:14:18,960 --> 00:14:22,150
A do toho pusťte a zařídit sami
shodně s tím, co je

377
00:14:22,150 --> 00:14:25,180
zobrazen na obrazovce.

378
00:14:25,180 --> 00:14:26,530
>> [Přechodová Hlasy]

379
00:14:26,530 --> 00:14:28,160
>> David J. Malan: OOP, je mi líto.

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

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

382
00:14:32,180 --> 00:14:32,750
Tak, jdeme na to.

383
00:14:32,750 --> 00:14:34,180
Číslo pět.

384
00:14:34,180 --> 00:14:35,136
Číslo šest.

385
00:14:35,136 --> 00:14:37,770
Jedna, dvě, tři, čtyři,
pět, šest, sedm.

386
00:14:37,770 --> 00:14:39,410
Oh, to je trapné.

387
00:14:39,410 --> 00:14:41,210
>> SPEAKER 2: Budu jen dostat -.

388
00:14:41,210 --> 00:14:41,900
>> David J. Malan: dobrý obchod.

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

390
00:14:43,130 --> 00:14:44,611
Děkuji vám za účast.

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

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

393
00:14:48,580 --> 00:14:48,860
Dobrá.

394
00:14:48,860 --> 00:14:51,970
Takže máme čtyři, dva, šest,
jeden, tři, sedm, pět.

395
00:14:51,970 --> 00:14:56,010
Perfektní takže máme sedm dobrovolníků
, kteří zde jsou stejné šířky, aby

396
00:14:56,010 --> 00:14:57,430
Pole, které hrajeme
s dříve.

397
00:14:57,430 --> 00:14:59,470
A já jsem si vybral sedm důvodů
že bude jen

398
00:14:59,470 --> 00:15:00,840
výhodné v trochu.

399
00:15:00,840 --> 00:15:04,400
A já jdu navrhnout, že první
třídíme těchto sedm dobrovolníků.

400
00:15:04,400 --> 00:15:06,786
Pokud byste chtěli, první,
pozdravit ačkoli.

401
00:15:06,786 --> 00:15:08,970
Vzhledem k tomu bude
nevhodné několik minut.

402
00:15:08,970 --> 00:15:10,370
Představte se.

403
00:15:10,370 --> 00:15:10,980
>> GRACE: Ahoj, já jsem milost.

404
00:15:10,980 --> 00:15:14,190
Jsem ve druháku na Leverett domu.

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

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

407
00:15:15,620 --> 00:15:16,920
Jsem v prváku na svaru.

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

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

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

411
00:15:21,040 --> 00:15:22,300
Jsem junior v Cabot.

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

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

414
00:15:25,980 --> 00:15:29,090
Jsem v prváku na Matthews.

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

416
00:15:29,550 --> 00:15:32,816
Jsem v prváku na Greenough.

417
00:15:32,816 --> 00:15:33,700
>> MIKE: Já jsem Mike.

418
00:15:33,700 --> 00:15:37,360
Jsem v prváku na Grays.

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

420
00:15:37,990 --> 00:15:40,313
Jsem ve druháku na Leverett.

421
00:15:40,313 --> 00:15:41,300
>> David J. Malan: Výborný.

422
00:15:41,300 --> 00:15:41,850
Dobrá.

423
00:15:41,850 --> 00:15:44,190
No, děkuji všem našim
Dobrovolníci zde tak daleko.

424
00:15:44,190 --> 00:15:47,110
A výzva na dosah ruky teď se děje
bude třídit z těchto kluci, ale pak

425
00:15:47,110 --> 00:15:50,250
budeme muset trošku přemýšlet
těžké o tom, jak efektivně jsme vlastně

426
00:15:50,250 --> 00:15:51,110
seřazené.

427
00:15:51,110 --> 00:15:52,580
Takže pojďme se nejprve zkusit.

428
00:15:52,580 --> 00:15:55,970
Vy můžete vidět navzájem čísla
jen tím, v rozích.

429
00:15:55,970 --> 00:15:59,380
Nestyď se a trvat několik sekund a
řadit sami od nejmenší na

430
00:15:59,380 --> 00:16:01,240
vlevo největší na pravé straně.

431
00:16:01,240 --> 00:16:02,490
Přejít.

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
Dobře.

435
00:16:08,030 --> 00:16:09,370
To bylo opravdu zatraceně rychle.

436
00:16:09,370 --> 00:16:14,040
Teď tady někdo, co to bylo algoritmus
že tito lidé aplikovat?

437
00:16:14,040 --> 00:16:14,900
>> SPEAKER 1: od nejméně po největší.

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

439
00:16:15,000 --> 00:16:18,070
Alespoň největší je opravdu nějak
objektivní, ale nejsem si jistý, že to

440
00:16:18,070 --> 00:16:18,890
opravdu algoritmus.

441
00:16:18,890 --> 00:16:21,810
Alespoň největší neříká
mě krok-za-krokem, co dělat.

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

443
00:16:22,833 --> 00:16:24,083
>> SPEAKER 1: [neslyšitelné]

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
Takže pokud uvidíte osoba menší než
Vaše telefonní číslo, pak se přesuňte na

447
00:16:28,920 --> 00:16:29,680
právo z nich.

448
00:16:29,680 --> 00:16:32,800
Tak to je nyní stále více expresivní,
spíš algoritmu, protože

449
00:16:32,800 --> 00:16:35,410
Dá se říci,, je-li to, pak je to.

450
00:16:35,410 --> 00:16:37,050
Takže máme nějaký
podmíněné konstrukce.

451
00:16:37,050 --> 00:16:39,700
A tihle kluci zřejmě k tomu, že některé
časy, protože někteří z vás přestěhoval trochu

452
00:16:39,700 --> 00:16:40,420
na dálku.

453
00:16:40,420 --> 00:16:43,410
Takže tam byl pravděpodobně nějaký druh
opakování děje v jejich myslích.

454
00:16:43,410 --> 00:16:44,610
>> Ale pojďme se snaží formalizovat, že.

455
00:16:44,610 --> 00:16:47,540
Pokud jste mohli obnovit zpět
na ně toto ujednání.

456
00:16:47,540 --> 00:16:50,650
Uvidíme, jestli se nemůžeme formalizovat tento
bit, a pak položit otázku, jen

457
00:16:50,650 --> 00:16:51,580
jak efektivní je to?

458
00:16:51,580 --> 00:16:54,220
Samozřejmě, že když budeme dělat to pomaleji,
to bude mít pocit, jako dobrý

459
00:16:54,220 --> 00:16:57,210
algoritmus, ale uvidíme, jestli to půjde
dát naše prsty na přesných krocích.

460
00:16:57,210 --> 00:16:58,670
>> Takže vy dva jsou čtyři a dva.

461
00:16:58,670 --> 00:17:01,020
Nebo si správné nebo nesprávné, aby?

462
00:17:01,020 --> 00:17:01,900
Je zřejmé nesprávné.

463
00:17:01,900 --> 00:17:02,710
Tak jsme vyměnili.

464
00:17:02,710 --> 00:17:05,170
Teď jdu oddálit
tady a říkají čtyř až šesti.

465
00:17:05,170 --> 00:17:06,240
Jste správné nebo nesprávné?

466
00:17:06,240 --> 00:17:06,599
>> GABE: Správně.

467
00:17:06,599 --> 00:17:07,180
>> David J. Malan: Správně.

468
00:17:07,180 --> 00:17:08,300
Šest a jedna?

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

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

471
00:17:09,630 --> 00:17:10,490
Tak to je dva swapy.

472
00:17:10,490 --> 00:17:11,710
Šest a tři?

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

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

475
00:17:13,000 --> 00:17:13,930
Šest a sedm?

476
00:17:13,930 --> 00:17:14,630
Vypadá to dobře.

477
00:17:14,630 --> 00:17:15,396
Sedm a pět?

478
00:17:15,396 --> 00:17:16,150
>> JESS: [neslyšitelné]

479
00:17:16,150 --> 00:17:17,089
>> David J. Malan: OK, vyměnit.

480
00:17:17,089 --> 00:17:19,770
A třídit.

481
00:17:19,770 --> 00:17:19,980
Dobrá.

482
00:17:19,980 --> 00:17:21,440
Takže samozřejmě není, že jo?

483
00:17:21,440 --> 00:17:22,470
Takže tam bylo více děje.

484
00:17:22,470 --> 00:17:24,920
Ale opravdu, tito lidé, a to i
jen instinktivně.

485
00:17:24,920 --> 00:17:25,450
stále v pohybu.

486
00:17:25,450 --> 00:17:27,710
Neměli zastavit, jakmile se
opraven jeden problém.

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

488
00:17:27,839 --> 00:17:29,390
Opravdu, budu mít
udělat stejnou věc.

489
00:17:29,390 --> 00:17:32,720
Budu muset nějak zádech vzad
na začátku tohoto problému,

490
00:17:32,720 --> 00:17:35,630
nebo na začátku této řady
lidé, začněme volat jim.

491
00:17:35,630 --> 00:17:38,366
>> A teď, co by můj algoritmus
Na druhém průchodu bude?

492
00:17:38,366 --> 00:17:39,220
>> SPEAKER 1: To je totéž.

493
00:17:39,220 --> 00:17:39,940
>> David J. Malan: To je totéž.

494
00:17:39,940 --> 00:17:41,460
A to já začínám mít ráda, ne?

495
00:17:41,460 --> 00:17:44,720
Jakmile si můžete najít sami dělat
totéž znovu a znovu, je to

496
00:17:44,720 --> 00:17:47,890
stále více jako algoritmus,
a méně lidský instinkt.

497
00:17:47,890 --> 00:17:48,680
>> Takže teď je to tady zase.

498
00:17:48,680 --> 00:17:49,870
Dva a čtyři?

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

500
00:17:50,220 --> 00:17:51,050
Čtyři a jedna?

501
00:17:51,050 --> 00:17:53,380
Ah, byla opravdu někteří
práce je třeba ještě udělat.

502
00:17:53,380 --> 00:17:53,620
Pro a tři?

503
00:17:53,620 --> 00:17:54,572
Dobře.

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

505
00:17:56,000 --> 00:17:58,380
Šest a pět?

506
00:17:58,380 --> 00:17:59,470
Šest a sedm?

507
00:17:59,470 --> 00:18:00,970
OK, teď, hotovo.

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

509
00:18:01,550 --> 00:18:02,710
Musím se vrátit.

510
00:18:02,710 --> 00:18:05,130
>> Takže teď znovu, tohle děláme
trochu záměrně.

511
00:18:05,130 --> 00:18:08,700
A teď je tu jen jeden mozek
provádění tohoto algoritmu.

512
00:18:08,700 --> 00:18:10,290
Jeden CPU, chcete-li.

513
00:18:10,290 --> 00:18:13,090
A upřímně řečeno, to je jediný zdroj
budeme mít přístup.

514
00:18:13,090 --> 00:18:16,280
A jakmile jsme se vrátit ke klávesnici
a něco jako C v našem

515
00:18:16,280 --> 00:18:19,600
likvidace, budeme jen psát program
který může dělat jednu věc najednou.

516
00:18:19,600 --> 00:18:22,900
Vzhledem k tomu, tito lidé před chvílí jsme
pákový efekt, jejich kolektivní inteligenčního

517
00:18:22,900 --> 00:18:24,180
jako jste udělali v týdnu nulu.

518
00:18:24,180 --> 00:18:24,980
Takže pojďme v tom pokračovat.

519
00:18:24,980 --> 00:18:26,260
>> Dva a.

520
00:18:26,260 --> 00:18:26,945
Dva a tři.

521
00:18:26,945 --> 00:18:27,460
Tři a čtyři.

522
00:18:27,460 --> 00:18:28,310
Čtyři a pět.

523
00:18:28,310 --> 00:18:28,620
Pět a šest.

524
00:18:28,620 --> 00:18:30,510
Šest a sedm.

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

526
00:18:31,880 --> 00:18:34,560
Takže jsem, ale dovolte mi, abych hrát
ďáblova advokáta.

527
00:18:34,560 --> 00:18:37,950
Musím se trochu počítače, který právě
udělal průchod této řady

528
00:18:37,950 --> 00:18:40,225
lidí, vím, že jsem udělal?

529
00:18:40,225 --> 00:18:40,670
>> Reproduktor 1: Ne

530
00:18:40,670 --> 00:18:41,050
>> David J. Malan: Tak proč?

531
00:18:41,050 --> 00:18:46,900
Co bych měl udělat, aby se
k závěru, rozhodně, že jsem to udělal?

532
00:18:46,900 --> 00:18:48,230
Pravděpodobně jeden průchod.

533
00:18:48,230 --> 00:18:48,430
Je to tak?

534
00:18:48,430 --> 00:18:51,760
Protože vím, že od předchozí
průchod je, že jsem opravil chybu.

535
00:18:51,760 --> 00:18:53,920
A to znamená, možná je tu
ještě jedna chyba

536
00:18:53,920 --> 00:18:54,840
že musím opravit.

537
00:18:54,840 --> 00:18:58,680
Tak jsem se můľete být jisti pouze tím, převíjení a
pak kontrola, jeden dva, a dva

538
00:18:58,680 --> 00:19:00,940
tři, tři a čtyři, čtyři a pět,
pět a šest, šest a sedm.

539
00:19:00,940 --> 00:19:02,510
OK, teď jsem žádnou práci.

540
00:19:02,510 --> 00:19:05,990
>> Mohu si určitě vzpomenou, že jsem žádný
pracovat s něčím jako proměnné,

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

542
00:19:06,975 --> 00:19:12,490
Nazvěme to swapy, swapy a pokud je 0, když jsem
sem, a začala na 0, pak

543
00:19:12,490 --> 00:19:15,520
Já bych prostě hloupé jít dál
tam a zpět, kontrola znovu a

544
00:19:15,520 --> 00:19:16,450
znovu a znovu, že jo?

545
00:19:16,450 --> 00:19:18,450
Vzhledem k tomu, uvíznete v některých
druh nekonečné smyčce.

546
00:19:18,450 --> 00:19:21,250
Takže jakmile tam je 0 swapy,
můžeme konstatovat, že tato

547
00:19:21,250 --> 00:19:23,810
algoritmus je opravdu kompletní.

548
00:19:23,810 --> 00:19:25,400
>> Nyní se pojďme dát jméno na toto téma.

549
00:19:25,400 --> 00:19:28,930
Algoritmus, který navrhuji, abychom jen
implementuje, je něco, co nazývá bubble

550
00:19:28,930 --> 00:19:32,800
druh, známý jako taková v tom smyslu, že
čísla, která jsou větší druh

551
00:19:32,800 --> 00:19:37,990
bublina cestu až na vrchol, nebo se
na konec řady čísel.

552
00:19:37,990 --> 00:19:40,270
Ale jak efektivní byl tento algoritmus?

553
00:19:40,270 --> 00:19:44,600
Kolik kroků jsem musel fyzicky
Vezměte si například, třídit tyto

554
00:19:44,600 --> 00:19:45,850
sedm lidí?

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

556
00:19:48,560 --> 00:19:49,550
>> Čtyři až pět?

557
00:19:49,550 --> 00:19:51,420
OK, příliš mnoho je v konečném důsledku
bude odpověď.

558
00:19:51,420 --> 00:19:54,960
Ale i pak, konkrétní číslo
není ani tak zajímavé.

559
00:19:54,960 --> 00:19:56,670
Pojďme zobecnit ji jako n.

560
00:19:56,670 --> 00:20:00,520
Takže kdybych n lidi tady, a oni
byli, tak nějak, v náhodném pořadí na

561
00:20:00,520 --> 00:20:02,180
na začátku, v tomto původním pořadí.

562
00:20:02,180 --> 00:20:04,910
No, kolik kroků jsem měl
aby se v prvním průchodu?

563
00:20:04,910 --> 00:20:09,810
To byl jeden, dva, tři, čtyři, pět,
šest, a jsou sedm lidí, tak

564
00:20:09,810 --> 00:20:13,670
to je sedm, šest -, takže je n
minus jeden pár poprvé.

565
00:20:13,670 --> 00:20:16,280
>> Nyní, kolik kroků jsem měl
vzít, když jsem přetočil?

566
00:20:16,280 --> 00:20:19,310
No, mohli bychom dokonce zdvojnásobit, že pokud
jsme opravdu chtěli, ale teď jsem

567
00:20:19,310 --> 00:20:22,300
Jen řeknu, jo,
další n minus 1.

568
00:20:22,300 --> 00:20:25,240
Tak n mínus jedna je dostane
nepříjemné sledovat, takže se pojďme

569
00:20:25,240 --> 00:20:26,400
Hned za mírně.

570
00:20:26,400 --> 00:20:27,770
Takže 2n kroků.

571
00:20:27,770 --> 00:20:29,310
Takže 14 schodů, dávat nebo brát.

572
00:20:29,310 --> 00:20:31,930
>> Kolikrát jsem se
krok příště?

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

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

575
00:20:34,510 --> 00:20:37,920
A nyní, v nejhorším případě pro
instance, by kolikrát mám

576
00:20:37,920 --> 00:20:41,730
šel tam a zpět, tam a zpět,
provádění tohoto algoritmu, vyměňovat

577
00:20:41,730 --> 00:20:44,620
lidé na každém průchodu, asi?

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

579
00:20:47,720 --> 00:20:50,010
Je to vlastně n na druhou, ne?

580
00:20:50,010 --> 00:20:53,000
>> Vzhledem k tomu, v nejhorším případě můžete druh
ze si o tom myslíte intuitivně,

581
00:20:53,000 --> 00:20:54,800
i když to může trvat trochu
trochu času potopit palců

582
00:20:54,800 --> 00:20:57,590
V nejhorším případě, co by tito
sedm lidí vypadal v

583
00:20:57,590 --> 00:21:00,230
podmínky smlouvy
jejich čísla?

584
00:21:00,230 --> 00:21:01,460
Zcela dozadu, ne?

585
00:21:01,460 --> 00:21:02,815
A jen simulovat to,
jak se jmenujete?

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, Miku, stačí připojit mě
zde jen jedna sekunda?

589
00:21:08,100 --> 00:21:08,880
Ve skutečnosti, no.

590
00:21:08,880 --> 00:21:10,150
Omlouváme se Mike, pojďme vzad.

591
00:21:10,150 --> 00:21:10,910
Jak se jmenujete?

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, půjdeš se
mě, jestli vám to nevadí.

595
00:21:13,750 --> 00:21:17,150
Takže budu navrhovat, jen pro
jednoduchost, že Neil je nyní v jeho

596
00:21:17,150 --> 00:21:18,510
nejhorší možný případ.

597
00:21:18,510 --> 00:21:20,720
Ale vzpomínám, jak jsem implementoval
můj algoritmus.

598
00:21:20,720 --> 00:21:24,530
Jsem porovnávání, srovnávání, porovnávání,
porovnávání, srovnávání, oh.

599
00:21:24,530 --> 00:21:26,640
Nyní tito lidé jsou mimo
provoz, tak jsem opravit.

600
00:21:26,640 --> 00:21:27,980
Takže vy vyměnit.

601
00:21:27,980 --> 00:21:31,630
Ale teď zvážit, jak moc dál
Neil nemá jít?

602
00:21:31,630 --> 00:21:32,690
Je to zhruba n.

603
00:21:32,690 --> 00:21:33,570
Víte, není to ve skutečnosti n.

604
00:21:33,570 --> 00:21:36,040
Je to jako, n mínus jedna, ale já jsem stále
rozmrzelí sledovat také trochu

605
00:21:36,040 --> 00:21:37,550
číslo, tak ať to prostě říkat n.

606
00:21:37,550 --> 00:21:42,860
>> Takže pokud Neil posune o jeden krok maximálně každý
čas a přejít Neil jeden krok,

607
00:21:42,860 --> 00:21:46,580
Musím si to opravdu nudný pas
tam a zpět, to je zhruba

608
00:21:46,580 --> 00:21:52,080
Tím, n kroků, celkem n krát,
, protože to bude pro mě

609
00:21:52,080 --> 00:21:55,820
že mnoho opatření, aby se Neil všechny
způsob, jak se tam, kam patří.

610
00:21:55,820 --> 00:21:58,620
Natož pak všichni ostatní, pokud jste
byli všichni mis-nařídil stejně.

611
00:21:58,620 --> 00:22:01,100
>> Takže říkejme bublinkové třídění n čtverců.

612
00:22:01,100 --> 00:22:04,860
Doba chodu tohoto algoritmu,
Výkon tohoto algoritmu,

613
00:22:04,860 --> 00:22:07,120
Účinnost tohoto algoritmu,
budeme jen popsat více

614
00:22:07,120 --> 00:22:08,800
obecně jako n na druhou.

615
00:22:08,800 --> 00:22:11,650
Což je pěkné, protože jsem mohl udělat
Stejný příklad s osmi lidmi, devět

616
00:22:11,650 --> 00:22:15,450
lidí, a miliony lidí, a že
Odpověď se nebude měnit.

617
00:22:15,450 --> 00:22:18,870
>> Takže pokud jste to nebude vadit, pojďme
obnovit vás tam, kde jste začali.

618
00:22:18,870 --> 00:22:22,510
A zkusme další dva přístupy a
uvidíme, jestli můžeme to udělat v zásadě

619
00:22:22,510 --> 00:22:23,820
lepší než tohle.

620
00:22:23,820 --> 00:22:27,130
Takže tentokrát, budu navrhovat
druh jiný algoritmus.

621
00:22:27,130 --> 00:22:29,950
To bylo velmi chytré nás minule,
a vy se právo na

622
00:22:29,950 --> 00:22:32,470
správné instinkty tak nějak
přehození párového.

623
00:22:32,470 --> 00:22:36,500
Ale když jsem chtěl tento přístup
jednoduše, a mým cílem je přesunout

624
00:22:36,500 --> 00:22:39,800
všechny z malých čísel tímto způsobem, a
tlačit všechny velké čísel, která

625
00:22:39,800 --> 00:22:43,030
Tak proč jsem si, že v
nejvíce naivní způsob, jak je to možné a jestli bych

626
00:22:43,030 --> 00:22:45,730
může dělat lépe, než to, co bylo
poměrně složitý algoritmus?

627
00:22:45,730 --> 00:22:46,620
>> Tak uvidíme.

628
00:22:46,620 --> 00:22:48,940
Čtyři je docela malé množství, takže jsem
nechám tě tam chvilku.

629
00:22:48,940 --> 00:22:50,610
Ooh, číslo dvě je ještě lepší.

630
00:22:50,610 --> 00:22:52,230
Takže stačí krok vpřed
na chvíli?

631
00:22:52,230 --> 00:22:55,670
To je v současné době jsem nejmenší číslované
kandidát, a budu si pamatovat

632
00:22:55,670 --> 00:22:57,000
které se, jako, proměnné.

633
00:22:57,000 --> 00:22:57,930
Ale budu držet kontrolu.

634
00:22:57,930 --> 00:22:59,890
Je tu někdo, jehož
číslo je menší?

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

636
00:23:00,460 --> 00:23:01,390
Oh, to je Neil znovu.

637
00:23:01,390 --> 00:23:04,050
>> Takže budu tlačit zpátky
nějak koncepčně.

638
00:23:04,050 --> 00:23:05,120
Neil přijde dopředu.

639
00:23:05,120 --> 00:23:08,440
A teď, proměnnou, která jsem pomocí se
sledovat, kdo má nejmenší

640
00:23:08,440 --> 00:23:11,390
číslo je aktualizován, aby obsahoval
Neil umístění.

641
00:23:11,390 --> 00:23:12,110
No, uvidíme.

642
00:23:12,110 --> 00:23:13,960
Tři, sedm, pět.

643
00:23:13,960 --> 00:23:15,590
OK, já vím, Neil byl nejmenší.

644
00:23:15,590 --> 00:23:18,110
Co je to ta nejjednodušší věc
Pro mě dělat teď?

645
00:23:18,110 --> 00:23:21,410
Nebudu ztrácet čas tím, že jen
bublající Neil jedno místo doleva.

646
00:23:21,410 --> 00:23:25,350
Proč jsem dal Neila, kde
patří, což je samozřejmě kde?

647
00:23:25,350 --> 00:23:26,160
>> Úplně na začátku.

648
00:23:26,160 --> 00:23:27,720
Takže Neil, pojď se mnou.

649
00:23:27,720 --> 00:23:28,910
A co se vlastně jmenuješ?

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

651
00:23:29,310 --> 00:23:29,710
>> David J. Malan: Milost.

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

653
00:23:29,920 --> 00:23:32,490
Takže Milost, bohužel, ty jsi
druh v cestě.

654
00:23:32,490 --> 00:23:34,290
Tak jak jsme se tento problém vyřešit?

655
00:23:34,290 --> 00:23:34,490
Je to tak?

656
00:23:34,490 --> 00:23:37,500
Pokud se jedná o pole, je tu
pouze sedm míst.

657
00:23:37,500 --> 00:23:40,830
Připomeňme, že s Robem, mluvili jsme o
deklarovat věky, a my jsme měli jen

658
00:23:40,830 --> 00:23:41,740
konečný počet věků?

659
00:23:41,740 --> 00:23:42,535
Stejná myšlenka tady.

660
00:23:42,535 --> 00:23:44,300
Máme jen konečný počet ints.

661
00:23:44,300 --> 00:23:47,590
Grace je druh v našem
způsobem, tak jak to napravit?

662
00:23:47,590 --> 00:23:49,555
>> Nejjednodušší způsob, jak je rád,
Milost, je mi líto.

663
00:23:49,555 --> 00:23:51,870
Budeš muset jít přes
tam, takže můžeme vytvořit prostor.

664
00:23:51,870 --> 00:23:55,290
Teď, když si o tom myslíte, možná
Právě jsme problém ještě horší.

665
00:23:55,290 --> 00:23:58,510
A možná jsme udělali, protože co kdyby
Milost byli na správném místě?

666
00:23:58,510 --> 00:24:01,730
Ale my víme, že to tak není, protože
jinak, byla by

667
00:24:01,730 --> 00:24:03,980
stojící dopředu místo
Neil v této době, že jo?

668
00:24:03,980 --> 00:24:05,550
Už jsme se podívala na číslo ven.

669
00:24:05,550 --> 00:24:05,770
>> Dobrá.

670
00:24:05,770 --> 00:24:09,110
Takže teď, Neil je na správném místě, a
Můžu dělat mírné optimalizaci.

671
00:24:09,110 --> 00:24:11,740
Pro příští minutu, budu ignorovat
Neil dohromady, tak, aby se

672
00:24:11,740 --> 00:24:15,280
ztrácet čas, nebo náhodně
vyměnit ho na špatném místě.

673
00:24:15,280 --> 00:24:17,805
Takže teď, jak mám najít další
prvek, který je nejmenší?

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

675
00:24:18,480 --> 00:24:20,225
To je docela dobré číslo, je-li
Chcete udělat krok vpřed a

676
00:24:20,225 --> 00:24:21,100
Budu si tě.

677
00:24:21,100 --> 00:24:21,980
Šest, není dobré.

678
00:24:21,980 --> 00:24:24,820
Čtyři, tři, sedm, pět, není dobré.

679
00:24:24,820 --> 00:24:26,800
Takže dovolte mi, abych vám pohybovat se
vaše pravé místo.

680
00:24:26,800 --> 00:24:28,470
A my jsme měli štěstí tentokrát.

681
00:24:28,470 --> 00:24:31,350
>> Teď budu ignorovat
dva kluci, a teď ještě jednu

682
00:24:31,350 --> 00:24:32,260
projít to.

683
00:24:32,260 --> 00:24:33,490
Šest, že dost malé číslo.

684
00:24:33,490 --> 00:24:34,300
Pojď dopředu.

685
00:24:34,300 --> 00:24:35,220
Oh, omlouvám se.

686
00:24:35,220 --> 00:24:37,640
Grace číslo je lepší,
tak šlápnout dopředu.

687
00:24:37,640 --> 00:24:38,260
Čtyři.

688
00:24:38,260 --> 00:24:39,120
Je nám líto, Grace.

689
00:24:39,120 --> 00:24:39,950
Vraťte se znovu.

690
00:24:39,950 --> 00:24:41,550
Číslo tři je lepší.

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

692
00:24:42,290 --> 00:24:42,720
Pět.

693
00:24:42,720 --> 00:24:43,550
A teď, co se to jmenujete?

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
Takže Jason je nyní nejmenší
prvek jsem vybrána.

697
00:24:47,050 --> 00:24:49,160
Pokud má jít?

698
00:24:49,160 --> 00:24:50,380
Takže tam, kde je šest.

699
00:24:50,380 --> 00:24:51,210
A vaše jméno je znovu?

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 v cestě.

703
00:24:53,220 --> 00:24:54,640
Co je to ta nejjednodušší věc dělat?

704
00:24:54,640 --> 00:24:58,390
Vyměňte tyto dva chlapy a pokračovat.

705
00:24:58,390 --> 00:24:59,020
Takže teď uvidíme.

706
00:24:59,020 --> 00:25:00,170
Kdo je nejmenší?

707
00:25:00,170 --> 00:25:01,030
Čtyři.

708
00:25:01,030 --> 00:25:01,990
Dovolte mi trochu podvádět.

709
00:25:01,990 --> 00:25:03,090
Pět bude nejmenší.

710
00:25:03,090 --> 00:25:05,220
Zjistil jsem další, pokud chcete krok
dopředu, co mám dělat s

711
00:25:05,220 --> 00:25:06,820
tito lidé, s Gabe?

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

713
00:25:08,450 --> 00:25:10,740
Takže teď, stále mírně mimo provoz.

714
00:25:10,740 --> 00:25:14,140
Zjistil jsem, Gabe jako nejmenší, a proto
I pop mu ven, pohybovat se kluci znovu.

715
00:25:14,140 --> 00:25:15,190
A hotovo.

716
00:25:15,190 --> 00:25:17,200
>> Takže odpověď je stejná.

717
00:25:17,200 --> 00:25:18,600
Konečný výsledek je stejný.

718
00:25:18,600 --> 00:25:22,730
, Která z těchto algoritmů
je lepší?

719
00:25:22,730 --> 00:25:23,500
Druhý, slyšel jsem.

720
00:25:23,500 --> 00:25:24,252
Proč?

721
00:25:24,252 --> 00:25:25,900
>> SPEAKER 3: Je to n kroků [neslyšitelné].

722
00:25:25,900 --> 00:25:27,600
>> David J. Malan: Je to n kroky na nejvíce.

723
00:25:27,600 --> 00:25:28,490
Zajímavý.

724
00:25:28,490 --> 00:25:30,610
Tak to je když?

725
00:25:30,610 --> 00:25:33,630
Tak jak jsem nenašel
nejmenší prvek?

726
00:25:33,630 --> 00:25:37,060
Kolik kroků jsem vzít
najít nejmenší prvek?

727
00:25:37,060 --> 00:25:39,220
Jsem se dívat celou cestu
na konci, ne?

728
00:25:39,220 --> 00:25:41,530
Vzhledem k tomu, že v nejhorším případě, co
pokud Neil byl tady?

729
00:25:41,530 --> 00:25:45,700
Takže stačí najít nejmenší prvek
mě bere n kroky, nebo n mínus jedna.

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

731
00:25:46,100 --> 00:25:46,980
Takže opravit Neila.

732
00:25:46,980 --> 00:25:48,740
Pamatujte si, že minutu nebo tak dávno.

733
00:25:48,740 --> 00:25:51,680
>> Ale jak jsem našel další
nejmenší prvek?

734
00:25:51,680 --> 00:25:54,830
Je to n mínus 1 nebo n minus 2 opravdu,
z počtu kroků.

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

736
00:25:55,440 --> 00:25:57,390
Tak jsem se n mínus 2.

737
00:25:57,390 --> 00:25:57,600
Dobrá.

738
00:25:57,600 --> 00:25:59,130
Tak, že se cítí o něco lépe.

739
00:25:59,130 --> 00:25:59,730
Dobrá.

740
00:25:59,730 --> 00:26:03,270
Kolik kroků příště
najít číslo tři?

741
00:26:03,270 --> 00:26:04,420
Tak n mínus 4.

742
00:26:04,420 --> 00:26:07,670
Takže to klesá, jeden méně
krok na každé iteraci.

743
00:26:07,670 --> 00:26:08,740
Tak to se cítit lépe, ne?

744
00:26:08,740 --> 00:26:13,450
Pokud poslední době to bylo zhruba n krát n,
tentokrát je to n mínus jedna plus mínus n

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

746
00:26:16,500 --> 00:26:18,750
Ale pokud si vzpomínám z vaší vysoké škole
učebnice, trochu podvádět

747
00:26:18,750 --> 00:26:24,380
list na zadní straně, který má vzorce, pokud
sečtete tuto řadu čísel,

748
00:26:24,380 --> 00:26:31,280
Jaký je celkový počet kroků
bude, že jsem se tady?

749
00:26:31,280 --> 00:26:36,580
>> To je jeden z těch, jako, n minus
1, n krát, děleno 2.

750
00:26:36,580 --> 00:26:39,040
Tak se ukažte, jestli můžu vytáhnout
to se jen na chvíli.

751
00:26:39,040 --> 00:26:42,230
A opět jsem trochu zaokrouhlování některých
čísla jen aby náš život jednoduchý,

752
00:26:42,230 --> 00:26:47,830
ale pokud si vzpomínám, je to něco, jako kdyby
Já n mínus jedna věci, pak n minus

753
00:26:47,830 --> 00:26:53,570
2, pak n mínus tři, to je zhruba
něco takového po 2, a když jsem

754
00:26:53,570 --> 00:26:55,510
násobit na to, že je
ve skutečnosti n náměstí.

755
00:26:55,510 --> 00:26:58,940
To se necítí moc dobře.
n n minus na 2.

756
00:26:58,940 --> 00:27:00,350
>> Ale tady je to věc.

757
00:27:00,350 --> 00:27:03,720
Ve vědě o počítačích, když se problémy
začít být zajímavé, je-li n

758
00:27:03,720 --> 00:27:04,700
dostane opravdu velký.

759
00:27:04,700 --> 00:27:08,110
A když n se opravdu velké, což z
Tyto hodnoty se chystá ovládnout všechny

760
00:27:08,110 --> 00:27:09,750
z ostatních?

761
00:27:09,750 --> 00:27:10,990
Je to tak trochu na n na druhou, ne?

762
00:27:10,990 --> 00:27:13,340
Ano, dělení 2 je docela dobrý.

763
00:27:13,340 --> 00:27:16,740
Ale pokud mluvíme o miliardách
z kusů dat, nebo bilionech

764
00:27:16,740 --> 00:27:18,700
části dat, OK, tak
jste dvakrát tak rychle.

765
00:27:18,700 --> 00:27:22,440
Ale kdo opravdu zajímá, jestli ten velký počet,
Je-li tento faktor je, co se bude

766
00:27:22,440 --> 00:27:23,040
větší a větší.

767
00:27:23,040 --> 00:27:25,990
A jistě, to dělá více
rozdíl, než toho chlapa.

768
00:27:25,990 --> 00:27:29,120
Takže i když jste pravdu,
Druhý algoritmus, budeme nazývat

769
00:27:29,120 --> 00:27:32,970
výběr druhu, je v reálném světě,
trochu rychlejší potenciálně, protože jsem

770
00:27:32,970 --> 00:27:35,360
s méně a méně
kroky pokaždé.

771
00:27:35,360 --> 00:27:37,340
>> Ve skutečnosti to není zásadně rychleji.

772
00:27:37,340 --> 00:27:41,430
Protože pokud budeme skutečně hrát to ven
velké hodnoty n, na konci

773
00:27:41,430 --> 00:27:44,750
den, po dobu dost velký n, je to stále
bude cítit docela pomalý.

774
00:27:44,750 --> 00:27:46,770
No, dovolte mi, abych jednu
poslední průchod na to.

775
00:27:46,770 --> 00:27:48,920
To je to, co bych nazval
Výběr sort.

776
00:27:48,920 --> 00:27:51,040
Může vás obnovit sami
jednou naposledy?

777
00:27:51,040 --> 00:27:53,550
A v tomto posledním případě, jdu
navrhnout něco

778
00:27:53,550 --> 00:27:54,970
volal vložení řazení.

779
00:27:54,970 --> 00:27:57,470
Vložení druh bytí, koncepčně,
trochu jinak.

780
00:27:57,470 --> 00:28:00,980
>> Spíše než jít tam a zpět
výběrem nejmenší prvek, jsem

781
00:28:00,980 --> 00:28:05,030
jen tak vypořádat s každou z nich
kluci, jak jsem se s nimi setkat, a vložte

782
00:28:05,030 --> 00:28:06,850
je do jejich správné místo.

783
00:28:06,850 --> 00:28:10,160
Tak jsem jen tak začít s Grace,
a vidím, že je to číslo čtyři.

784
00:28:10,160 --> 00:28:11,720
Kde se číslo čtyři patří?

785
00:28:11,720 --> 00:28:14,940
Jsem se začala třídit nic,
Milost tak dostane zůstat tady.

786
00:28:14,940 --> 00:28:18,355
A teď budu tvrdit, kdybys mohl
krok na pravé straně, to

787
00:28:18,355 --> 00:28:21,650
můj řazeny seznam, to je moje
netříděného zbývající seznam.

788
00:28:21,650 --> 00:28:23,260
Takže teď budu pokračovat dál,
a co se to jmenujete?

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
Takže Branson je číslo dvě.

792
00:28:25,375 --> 00:28:27,490
Takže budu tě vzít
se na chvíli zamyslel.

793
00:28:27,490 --> 00:28:30,940
A teď, kam patří
v tomto poli?

794
00:28:30,940 --> 00:28:32,360
Takže na pravé milosti.

795
00:28:32,360 --> 00:28:35,670
Takže znovu, jsme druh výroby
Milost udělat hodně práce tady.

796
00:28:35,670 --> 00:28:37,290
Kde jsme tě?

797
00:28:37,290 --> 00:28:40,120
Takže budeme klouzat vás
vlevo, a vložte tam Branson.

798
00:28:40,120 --> 00:28:41,680
Ale teď tvrdí, že
jste hotovi.

799
00:28:41,680 --> 00:28:43,240
Ale oznámení, nebudu používat extra prostor.

800
00:28:43,240 --> 00:28:45,130
Je to stále dva elementy
zde 5. sem.

801
00:28:45,130 --> 00:28:47,910
Celková velikost pole je 7, takže jsem
nepodvádí, v pořádku?

802
00:28:47,910 --> 00:28:51,950
>> Takže teď máme s Gabe zde
číslo šest, kam patří?

803
00:28:51,950 --> 00:28:52,650
Máš štěstí znovu.

804
00:28:52,650 --> 00:28:53,820
Takže jste si zůstat tady.

805
00:28:53,820 --> 00:28:57,210
Jen se mírný krok na pravé straně
jen aby bylo jasné, že jste řazeny.

806
00:28:57,210 --> 00:29:00,520
A teď máme Neil opět číslo
jedno, kam půjdeš?

807
00:29:00,520 --> 00:29:03,540
A teď je tam, kde začneme vidět, že
Tento algoritmus, i když na první

808
00:29:03,540 --> 00:29:05,950
pohled, se cítí docela chytrá, sledovat
co se stane.

809
00:29:05,950 --> 00:29:07,370
Pokud byste mohli krok vpřed.

810
00:29:07,370 --> 00:29:09,260
>> Kde chceme dát Neila?

811
00:29:09,260 --> 00:29:11,830
Je tedy jasné, tady, tak jak
se dostaneme Neila tam?

812
00:29:11,830 --> 00:29:12,970
Pojďme udělat tento krok-za-krokem.

813
00:29:12,970 --> 00:29:15,620
Gabe, kde budete muset jít?

814
00:29:15,620 --> 00:29:19,590
Jo, tak se jeden velký krok,
nebo dvě poloviny-kroky, aby

815
00:29:19,590 --> 00:29:20,820
jeden krok tam.

816
00:29:20,820 --> 00:29:21,750
Milost, kam jít?

817
00:29:21,750 --> 00:29:22,510
Dobře.

818
00:29:22,510 --> 00:29:23,500
Takže další krok.

819
00:29:23,500 --> 00:29:24,960
A konečně, Branson?

820
00:29:24,960 --> 00:29:25,460
Dalším krokem.

821
00:29:25,460 --> 00:29:27,190
A nyní můžeme dát Neila na místo.

822
00:29:27,190 --> 00:29:28,440
>> Takže teď, i nadále tuto logiku.

823
00:29:28,440 --> 00:29:32,420
I když nejsme přesouvá Neil
nad, a přes, a přes, aby ho

824
00:29:32,420 --> 00:29:36,420
kde jde, v nejhorším případě,
další číslo můžeme setkat mohli

825
00:29:36,420 --> 00:29:42,220
je číslo, řekněme, že se řada
nula, pak se budeme přesouvat všechny

826
00:29:42,220 --> 00:29:42,730
tihle kluci.

827
00:29:42,730 --> 00:29:44,950
Předpokládejme, že existuje celá řada, negativní
jeden, pak musíme posunout

828
00:29:44,950 --> 00:29:46,080
všechny tyto lidi.

829
00:29:46,080 --> 00:29:48,500
Takže jsme opravdu jen tak proletí
problém asi tak, že jsme

830
00:29:48,500 --> 00:29:52,620
převedení náklady z
Výběrové řízení tak vložení

831
00:29:52,620 --> 00:29:56,930
proces tak, že jste prostě musel
pohybovat zhruba n mínus něco

832
00:29:56,930 --> 00:29:57,940
počet kroků.

833
00:29:57,940 --> 00:30:01,200
A to počet kroků je teprve ve chvíli,
zvýšit, když jsem vybrat více čísel,

834
00:30:01,200 --> 00:30:04,730
když budu muset držet strkat kluci
zpět, a zpět, a zpět.

835
00:30:04,730 --> 00:30:08,320
>> Tak smutné, teď je všechno z nich
algoritmy jsou n na druhou.

836
00:30:08,320 --> 00:30:10,570
Pojďme dál a díky těmto
kluci, a vizualizovat tyto trochu

837
00:30:10,570 --> 00:30:11,090
jinak.

838
00:30:11,090 --> 00:30:12,312
Velmi dobře.

839
00:30:12,312 --> 00:30:14,120
>> [APPLAUSE]

840
00:30:14,120 --> 00:30:15,030
>> Dobrá.

841
00:30:15,030 --> 00:30:16,280
Tady to je.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Díky za -

844
00:30:18,470 --> 00:30:19,190
>> BRANSON: [neslyšitelné] držet čísla.

845
00:30:19,190 --> 00:30:21,990
>> David J. Malan: Ne, můžete
držet čísla stejně.

846
00:30:21,990 --> 00:30:23,440
Dobrá.

847
00:30:23,440 --> 00:30:24,100
Dobrá práce.

848
00:30:24,100 --> 00:30:25,300
Dobrá.

849
00:30:25,300 --> 00:30:30,510
Tak uvidíme, jestli nemůžeme nyní shrnout
rychleji a více vizuálně,

850
00:30:30,510 --> 00:30:33,410
přesně to, co se právě stalo
zde takto.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Chystám se jít dopředu
a vytáhněte Firefox.

853
00:30:38,770 --> 00:30:41,310
Budeme odkaz na tuto demonstraci
na hřišti internetových stránkách.

854
00:30:41,310 --> 00:30:43,870
Java je trochu nepříjemné, aby se pracovní
v některých prohlížečích v těchto dnech.

855
00:30:43,870 --> 00:30:46,760
Takže pokud nechcete hrát s tím doma,
Uvědomuji si, může být nutné používat Firefox

856
00:30:46,760 --> 00:30:47,990
aby si to práci.

857
00:30:47,990 --> 00:30:50,440
A co budu dělat s tím
ukázka je následující.

858
00:30:50,440 --> 00:30:54,875
>> Na dně, mám spoustu
možnosti nabídky, včetně začátku a

859
00:30:54,875 --> 00:30:55,840
tlačítko stop.

860
00:30:55,840 --> 00:30:59,450
Také, jako stranou, se zdá, že
chyba v těchto programech, přičemž si

861
00:30:59,450 --> 00:31:03,720
nemůže skutečně vidět start nebo zastavení
tlačítko, pokud budete držet příkazu nebo Alt

862
00:31:03,720 --> 00:31:06,560
plus a zoom, který zvědavě
zobrazuje více tlačítek.

863
00:31:06,560 --> 00:31:09,090
Takže jen FYI, pokud budete hrát
s tím doma.

864
00:31:09,090 --> 00:31:12,870
Teď jdu na tlačítko Start v právě
Okamžik, po zadání zpoždění,

865
00:31:12,870 --> 00:31:16,810
jako, 200 milisekund, prostě
takže můžeme vidět, co se stane.

866
00:31:16,810 --> 00:31:20,180
>> Takže tvrdím, že je to vizualizace
prvního algoritmu

867
00:31:20,180 --> 00:31:23,730
tito lidé udělali, bublinková třídění, přičemž
jsme vyměnili lidi párová.

868
00:31:23,730 --> 00:31:27,490
Klíčovou myšlenkou tohoto vizualizace
je, že výška sloupců

869
00:31:27,490 --> 00:31:30,510
představuje velikost čísla.

870
00:31:30,510 --> 00:31:32,210
Takže vyšší je sloupec,
Čím vyšší je číslo.

871
00:31:32,210 --> 00:31:33,680
Kratší bar, menší číslo.

872
00:31:33,680 --> 00:31:38,630
A pokud si všimnete, jedeme přes
První iterace tohoto algoritmu,

873
00:31:38,630 --> 00:31:42,620
vyměňovat velké i malé množství, takže
malý počet je na prvním místě a

874
00:31:42,620 --> 00:31:44,280
Velké množství jde na pravé straně.

875
00:31:44,280 --> 00:31:48,770
>> A jakmile se dostaneme na konec pole
mnoho více než sedm čísel, jsme

876
00:31:48,770 --> 00:31:49,900
jít zpět na začátek.

877
00:31:49,900 --> 00:31:51,140
A to předvídat.

878
00:31:51,140 --> 00:31:54,860
Na zcela vlevo, ten malý kluk se děje
swap na stranu, a to

879
00:31:54,860 --> 00:31:56,010
proces se opakuje.

880
00:31:56,010 --> 00:31:59,450
Nyní je tato vizualizace rychle dostane
nuda, tak nechte mě jít dopředu a zastavte se

881
00:31:59,450 --> 00:32:04,170
, změnit zpoždění něco mnohem
rychleji jen proto, aby teď, cit pro

882
00:32:04,170 --> 00:32:05,060
Tento algoritmus.

883
00:32:05,060 --> 00:32:07,840
>> Takže i když jsem spěchal nahoru, je to
jako upgrade můj procesor, nákup

884
00:32:07,840 --> 00:32:08,580
nový počítač.

885
00:32:08,580 --> 00:32:12,980
Jsem zásadně nezměnil můj
algoritmus, ale můžete opravdu vidět víc

886
00:32:12,980 --> 00:32:16,800
jasně než s lidmi, že velký
Čísla vyvěrá na vrchol,

887
00:32:16,800 --> 00:32:20,900
a malá čísla vyvěrá
až na dno.

888
00:32:20,900 --> 00:32:22,390
A teď tohle, co zde řazeny.

889
00:32:22,390 --> 00:32:25,260
A stranou, na náměstích, je tu
jen některé účetnictví tam

890
00:32:25,260 --> 00:32:28,010
pomůže spočítat, kolik srovnání,
nebo kolik swapy mají

891
00:32:28,010 --> 00:32:28,950
skutečně provedeno.

892
00:32:28,950 --> 00:32:30,750
>> Dobře, pojďme vyzkoušet jednu z
ostatní jsme viděli.

893
00:32:30,750 --> 00:32:37,116
Dovolte mi, abych klikněte na bubliny druhu zde, a
zvolím, a celá tato webová stránka

894
00:32:37,116 --> 00:32:38,936
je trochu buggy.

895
00:32:38,936 --> 00:32:41,155
Pojďme přijmout riziko
a spusťte jej znovu.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Tam jdeme.

898
00:32:45,030 --> 00:32:47,180
Tak jdem na výběr druhu.

899
00:32:47,180 --> 00:32:49,140
Nevím, proč menu
objeví se tam.

900
00:32:49,140 --> 00:32:54,070
Pojďme přiblížení napravit
chyba, změnit na 50 let.

901
00:32:54,070 --> 00:32:56,020
Ach, pojďme skutečně
o to rychleji.

902
00:32:56,020 --> 00:32:59,160
Pět milisekund nebo tak, a začít.

903
00:32:59,160 --> 00:33:00,470
>> Tak to je výběr druh.

904
00:33:00,470 --> 00:33:03,070
Takže znovu, myslím, že o tom, co
dělal s lidmi tady.

905
00:33:03,070 --> 00:33:08,490
Šli jsme přes pole a vybrané
nejmenší prvek znovu,

906
00:33:08,490 --> 00:33:09,250
a znovu a znovu.

907
00:33:09,250 --> 00:33:11,110
Teď tvrdí, že je stále dost špatný.

908
00:33:11,110 --> 00:33:15,010
To bylo ještě n čtvercový, dávat nebo brát,
ale to bylo v reálném světě, trochu

909
00:33:15,010 --> 00:33:18,280
rychlejší, protože jsem byl opravdu s
o něco méně kroků pokaždé.

910
00:33:18,280 --> 00:33:19,800
Ale mluvíme jen co?

911
00:33:19,800 --> 00:33:21,830
Možná 40 nebo tak, bary tady?

912
00:33:21,830 --> 00:33:23,200
Nemluvíme 40 milionů.

913
00:33:23,200 --> 00:33:27,430
Takže to není úplně jasné, že
byl opravdu značný zisk.

914
00:33:27,430 --> 00:33:32,530
>> Dovolte mi, abych se vrátit a změnit k našemu
Třetí algoritmus, který byl zvolte

915
00:33:32,530 --> 00:33:33,180
vložení sort.

916
00:33:33,180 --> 00:33:36,380
A teď je to opravdu buggy, protože
Nabídka opravdu by neměl být tam dole.

917
00:33:36,380 --> 00:33:40,840
Takže teď budeme listovat sem
a začít tento algoritmus.

918
00:33:40,840 --> 00:33:43,270
Pokřik, spuštění a zastavení.

919
00:33:43,270 --> 00:33:47,160
Takže to jeden druhů má pěkný vzor
na to, kdy jsme znovu

920
00:33:47,160 --> 00:33:50,240
vložení lidi, nebo v
V tomto případě, bary do

921
00:33:50,240 --> 00:33:52,620
jejich vhodné umístění.

922
00:33:52,620 --> 00:33:55,430
A to již udělal před
Otočil jsem se.

923
00:33:55,430 --> 00:33:58,940
Ale tenhle taky, teoreticky,
je stále n na druhou.

924
00:33:58,940 --> 00:34:01,430
>> Tak uvidíme, jestli nemůžeme shrnout
Tyto takto.

925
00:34:01,430 --> 00:34:04,750
Chystám se jít dopředu a jen proto, aby
nám trochu běžným způsobem mluví

926
00:34:04,750 --> 00:34:08,489
o těchto věcech, dovolte mi představit
jen trochu notace zde.

927
00:34:08,489 --> 00:34:12,480
Chystáte se vidět něco, co nazývá velký
O, protože je to doslova velký

928
00:34:12,480 --> 00:34:16,320
O. A to je tak, že počítač
vědec nebo matematik dokonce používá

929
00:34:16,320 --> 00:34:19,230
popsat provozní dobu
nějakého algoritmu.

930
00:34:19,230 --> 00:34:21,400
Kolik kroků to vlastně trvá?

931
00:34:21,400 --> 00:34:25,080
>> Teď jdu do rozpaků jsem se
můj rukopis tu za chvíli.

932
00:34:25,080 --> 00:34:29,020
Ale dovolte mi jít dál a říct, že
to bude velký O sem.

933
00:34:29,020 --> 00:34:33,610
A dovolte, abych vám představil jeden další
symbol, kapitál omega.

934
00:34:33,610 --> 00:34:37,080
Omega bude naopak,
v podstatě z velké O. vzhledem k tomu velké O

935
00:34:37,080 --> 00:34:40,790
znamená, v nejhorším případě, kolik času
může nějaký algoritmus přijmout,

936
00:34:40,790 --> 00:34:43,480
Podmínky n omega bude
se, kolik času mohlo by to

937
00:34:43,480 --> 00:34:45,409
se v nejlepším případě.

938
00:34:45,409 --> 00:34:48,090
A uvidíme, co máme na mysli
nejlepším případě za chvíli.

939
00:34:48,090 --> 00:34:49,940
>> Tak začněme něco jednoduchého.

940
00:34:49,940 --> 00:34:54,719
Dovolte mi začít s lineárním vyhledávání.

941
00:34:54,719 --> 00:34:55,679
Takže není třídění.

942
00:34:55,679 --> 00:34:58,000
Nazveme to lineární hledání.

943
00:34:58,000 --> 00:35:01,140
A nyní, aby se trochu
tabulka z toho.

944
00:35:01,140 --> 00:35:06,600
A nyní, v případě lineárního vyhledávání
v nejhorším případě sledovat, kolik kroků je

945
00:35:06,600 --> 00:35:11,770
bude trvat mě,
počet libovolné volby?

946
00:35:11,770 --> 00:35:14,540
A je tu celkem n dveře
nebo n celkový počet.

947
00:35:14,540 --> 00:35:15,940
Nejhorší případ.

948
00:35:15,940 --> 00:35:18,800
Kolik kroků budu muset
se najít číslo 50 v poli

949
00:35:18,800 --> 00:35:20,830
dveří n?

950
00:35:20,830 --> 00:35:21,410
A proč?

951
00:35:21,410 --> 00:35:23,680
Vzhledem k tomu, že to může být všechno
cesta přes na konec.

952
00:35:23,680 --> 00:35:27,120
Takže stejně jako Jennifer se setkal,
Číslo 50 bylo celou cestu, tak v

953
00:35:27,120 --> 00:35:30,760
v nejhorším případě lineární hledání
je velký O n, budeme říkat.

954
00:35:30,760 --> 00:35:33,430
>> A co nejlepším případě,
pokud máte opravdu štěstí?

955
00:35:33,430 --> 00:35:36,200
Je to jen tak, aby se jeden krok,
nebo stálý počet kroků.

956
00:35:36,200 --> 00:35:37,830
Takže budeme popisovat to jako jeden.

957
00:35:37,830 --> 00:35:39,010
Tak to je docela dobrý.

958
00:35:39,010 --> 00:35:41,210
Teď, co kdybychom udělali něco
jako binární vyhledávání?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
Takže binární vyhledávání, v nejhorším
případ, vzal kolik času?

961
00:35:47,846 --> 00:35:49,250
>> [Přechodová Hlasy]

962
00:35:49,250 --> 00:35:51,310
>> David J. Malan: Takže vlastně jsem
slyšel za pár místech.

963
00:35:51,310 --> 00:35:56,390
Takže je to vlastně log n, dávat nebo brát,
protože jak rozdělit seznam na dvě poloviny

964
00:35:56,390 --> 00:36:00,730
znovu a znovu, a znovu, jsme schopni
najít, nakonec, je tato hodnota,

965
00:36:00,730 --> 00:36:04,750
jestli je to tam, ale je zde jeden háček.

966
00:36:04,750 --> 00:36:08,590
Jaký je předpoklad, že musíme
brát za samozřejmost, pro binární vyhledávání?

967
00:36:08,590 --> 00:36:09,700
Musí být tříděny.

968
00:36:09,700 --> 00:36:12,770
Je to netřídí, můžete rozdělit věc
na polovinu znovu a znovu, a vy

969
00:36:12,770 --> 00:36:15,490
může jít vlevo, a můžete jít vpravo, a
můžete jít doleva a doprava, ale vy jste

970
00:36:15,490 --> 00:36:18,070
nenajde prvek, pokud
seznam není seřazen, protože

971
00:36:18,070 --> 00:36:18,790
můžete si ho ujít.

972
00:36:18,790 --> 00:36:22,120
Protože vaše heuristiky pro přechod vlevo
nebo doprava se bude vadný, pokud je to

973
00:36:22,120 --> 00:36:23,420
opravdu nejsou seřazeny.

974
00:36:23,420 --> 00:36:26,110
Takže je tu jakýsi skryté náklady
s použitím něco takového.

975
00:36:26,110 --> 00:36:29,250
>> Teď pojďme do našeho třídění
algoritmy nehledal -

976
00:36:29,250 --> 00:36:31,140
oh, vlastně jdeme v tomto prázdné.

977
00:36:31,140 --> 00:36:33,190
Binární hledání v nejlepším případě?

978
00:36:33,190 --> 00:36:36,290
Je to také jedno, pokud to jen se stane být
v samém středu pole, nebo

979
00:36:36,290 --> 00:36:37,810
uprostřed telefonního seznamu.

980
00:36:37,810 --> 00:36:39,710
Nyní se pojďme dělat bubliny druhu.

981
00:36:39,710 --> 00:36:42,570
Takže znovu, teď se vstupem do
druhy, nikoli hledání.

982
00:36:42,570 --> 00:36:47,220
>> V nejhorším případě, kolik kroků to jsme
tvrzení bublina trochu to bude trvat?

983
00:36:47,220 --> 00:36:48,410
n na druhou.

984
00:36:48,410 --> 00:36:49,200
Takže budu kreslit to.

985
00:36:49,200 --> 00:36:51,710
Ooh, můj rukopis vypadá ještě hůř
když se to předpokládá, že velký.

986
00:36:51,710 --> 00:36:52,510
Dobrá.

987
00:36:52,510 --> 00:36:53,570
Tak to je n na druhou.

988
00:36:53,570 --> 00:36:59,460
A v nejlepším případě bublinkové druhu,
kolik kroků to bude trvat?

989
00:36:59,460 --> 00:37:00,980
1, slyšel jsem.

990
00:37:00,980 --> 00:37:01,760
>> Reproduktor 1: n.

991
00:37:01,760 --> 00:37:03,286
>> David J. Malan: n, slyšel jsem.

992
00:37:03,286 --> 00:37:04,200
>> SPEAKER 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> David J. Malan: 2, slyšel jsem.

994
00:37:05,010 --> 00:37:06,670
Slyším 3?

995
00:37:06,670 --> 00:37:07,080
Dobrá.

996
00:37:07,080 --> 00:37:11,390
Slyšel jsem 1, n 2, ale pojďme vybrat
od sebe alespoň první z nich

997
00:37:11,390 --> 00:37:12,330
návrhy, 1.

998
00:37:12,330 --> 00:37:15,370
Není to špatný instinkt, protože to
druh kopíruje vzor zde.

999
00:37:15,370 --> 00:37:19,670
Ale pokud to trvá jen jeden krok, jak v
svět mohl bych tvrdit, že seznam

1000
00:37:19,670 --> 00:37:22,900
je tříděn, protože když jsem povoleno pouze
aby se jeden krok, kolik prvků

1001
00:37:22,900 --> 00:37:25,230
mohl bych vlastně zkontrolujte, zda?

1002
00:37:25,230 --> 00:37:28,270
No, jen 1, což znamená, že je n
minus 1 prvků, které by mohly být z

1003
00:37:28,270 --> 00:37:31,310
pořádku, a já jsem prostě jít na víře po
při pohledu na jeden prvek, který

1004
00:37:31,310 --> 00:37:31,850
věc je seřazen.

1005
00:37:31,850 --> 00:37:33,930
Takže 1. Není opravit tady.

1006
00:37:33,930 --> 00:37:35,710
Takže minimálně, kolik
musím se podívat na?

1007
00:37:35,710 --> 00:37:36,680
>> [Přechodová Hlasy]

1008
00:37:36,680 --> 00:37:40,160
>> David J. Malan: n mínus jedna, nebo opravdu,
n, protože jsem se třeba podívat se na každý

1009
00:37:40,160 --> 00:37:42,190
prvek, aby se ujistil, že
to není mimo provoz.

1010
00:37:42,190 --> 00:37:44,750
Ale opět budeme třídit vlny našeho
ruce na menších číslech a

1011
00:37:44,750 --> 00:37:47,100
Předpokládejme, že, jak n se zvětší, jsou
nezajímavé stejně.

1012
00:37:47,100 --> 00:37:48,380
Tak to je bublina třídění.

1013
00:37:48,380 --> 00:37:49,830
A teď, pojďme se tyto dva poslední.

1014
00:37:49,830 --> 00:37:53,520
Výběr druhu, a pak budeme
dělat vložení řazení.

1015
00:37:53,520 --> 00:37:57,160
A pak se stočí svou
mysl se něco mnohem

1016
00:37:57,160 --> 00:37:58,926
lepší než všechny z nich.

1017
00:37:58,926 --> 00:38:00,410
Dobrá.

1018
00:38:00,410 --> 00:38:04,700
>> Co je nejhorší běh
Doba výběr druhu?

1019
00:38:04,700 --> 00:38:05,680
>> SPEAKER 4: n na druhou.

1020
00:38:05,680 --> 00:38:06,710
>> David J. Malan: n náměstí, slyším.

1021
00:38:06,710 --> 00:38:09,790
Ale proč n na druhou, intuitivně?

1022
00:38:09,790 --> 00:38:11,170
>> SPEAKER 4: Protože jsme právě udělali.

1023
00:38:11,170 --> 00:38:12,260
>> David J. Malan: Protože jsme právě udělali.

1024
00:38:12,260 --> 00:38:12,550
OK.

1025
00:38:12,550 --> 00:38:13,380
Dobrá odpověď.

1026
00:38:13,380 --> 00:38:16,660
Ale intuitivně, proč je výběr
řadit n na druhou?

1027
00:38:16,660 --> 00:38:18,980
Co musíme udělat,
znovu a znovu?

1028
00:38:18,980 --> 00:38:22,570
Museli jsme se držet skenováním, jsou
můžete nejmenší, jste

1029
00:38:22,570 --> 00:38:24,020
Nejmenší jsou ty nejmenší.

1030
00:38:24,020 --> 00:38:27,480
A samozřejmost, jsme byli schopni přijmout n
kroky, pak n mínus 1, pak n mínus 2.

1031
00:38:27,480 --> 00:38:30,700
Ale pokud si trochu přidat ty všechno,
nebo ji na víře, že jsem přidal

1032
00:38:30,700 --> 00:38:34,810
je s předstihem, dostaneme zhruba n
na druhou mínus některých menších čísel.

1033
00:38:34,810 --> 00:38:36,730
Takže budu volat to n na druhou.

1034
00:38:36,730 --> 00:38:39,530
Ale s výběrem druhu v nejlepším
případ sledovat, kolik kroků je

1035
00:38:39,530 --> 00:38:40,632
mě vezme?

1036
00:38:40,632 --> 00:38:41,840
>> SPEAKER 5: [neslyšitelné]

1037
00:38:41,840 --> 00:38:44,350
>> David J. Malan: Je to bohužel
Stále n na druhou, ne?

1038
00:38:44,350 --> 00:38:49,590
Protože když jsem výběrem nejmenší
prvek, a měli jsme sedm lidí tady,

1039
00:38:49,590 --> 00:38:53,280
Já jen vím, jakmile se dostanu k velmi
konec, že ​​jsem našel nejmenší

1040
00:38:53,280 --> 00:38:55,670
číslo, kde on nebo
ona může být.

1041
00:38:55,670 --> 00:38:58,820
Ale jak najdu další
nejmenší číslo?

1042
00:38:58,820 --> 00:39:00,160
Musím udělat další přihrávku.

1043
00:39:00,160 --> 00:39:04,810
Takže v nejlepším případě, jaký je
Vstup do výběru druhu?

1044
00:39:04,810 --> 00:39:07,830
Je to už trochu seznamu číslo jedna,
číslo dvě, číslo tři, číslo čtyři.

1045
00:39:07,830 --> 00:39:08,600
Ale já jsem počítač.

1046
00:39:08,600 --> 00:39:10,190
Mohu jen podívat na jeden
věc najednou.

1047
00:39:10,190 --> 00:39:12,465
Nemůžu nějak krok
zpět jako člověk a řekl:

1048
00:39:12,465 --> 00:39:14,030
ooh, to vypadá správné.

1049
00:39:14,030 --> 00:39:17,580
>> Mohu jen rozhodnout korektnost
Třídit podle výběru

1050
00:39:17,580 --> 00:39:18,370
nejmenší číslo.

1051
00:39:18,370 --> 00:39:21,390
Ale i když jsem si první číslo jedna,
jestli nevím něco o

1052
00:39:21,390 --> 00:39:24,460
jiná čísla, které nemám, všechno, co jsem
vím, že jsem podal řadu

1053
00:39:24,460 --> 00:39:27,930
nebo sada za sebou dveře, které jsou
čísla, jediný způsob, jak vím, že jedna

1054
00:39:27,930 --> 00:39:28,680
Jednalo se o nejmenší?

1055
00:39:28,680 --> 00:39:32,440
Pokud se dostanu až sem a uvědomit si,
sakra, jeden byl opravdu nejmenší.

1056
00:39:32,440 --> 00:39:34,870
>> Ale jak jsem se potom rozhodne, že
dva je další nejmenší?

1057
00:39:34,870 --> 00:39:38,350
Tím, že dělá stejnou neefektivnost
znovu a znovu.

1058
00:39:38,350 --> 00:39:42,210
Tak konečně se vložení druhu,
how, v nejhorším případě,

1059
00:39:42,210 --> 00:39:44,990
jsme se, že to provádí?

1060
00:39:44,990 --> 00:39:49,100
To také je n na druhou.

1061
00:39:49,100 --> 00:39:53,020
A co s tím nejlepším případě?

1062
00:39:53,020 --> 00:39:56,282
Necháme to jako cliffhanger.

1063
00:39:56,282 --> 00:40:00,090
Budeme vyplnit té prázdné příště,
ale nejprve mi dovolte navrhnout, abychom

1064
00:40:00,090 --> 00:40:02,620
podstatně lépe než
všechny z nich, v pořádku?

1065
00:40:02,620 --> 00:40:05,220
>> Takže myslíte, že to, co pro sebe vložení
druh to bude.

1066
00:40:05,220 --> 00:40:06,910
No, to není příliš dramatický,
protože jsem jediný

1067
00:40:06,910 --> 00:40:08,970
která viděla změnu.

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
Takže tady máme něco
různé demonstrace.

1071
00:40:12,615 --> 00:40:16,580
Kdybych přiblížit tady, uvidíte, že na
vlevo máme bubliny druh, v

1072
00:40:16,580 --> 00:40:20,740
Střední máme výběr druhu a na
krajní pravice, máme něco, co jsme

1073
00:40:20,740 --> 00:40:23,380
jsem se podíval na dosud
tzv. sloučení druhu.

1074
00:40:23,380 --> 00:40:26,080
Ale zvažte, co jsme byli
tady děláš tak daleko ještě dnes.

1075
00:40:26,080 --> 00:40:29,200
Když Jennifer poprvé přišel na pódium,
jsme šli přes pole čísel

1076
00:40:29,200 --> 00:40:33,750
znovu a znovu, s lineární vyhledávání
a my jsme dostali lineární dobu chodu, velké O

1077
00:40:33,750 --> 00:40:35,100
n, abych tak řekl.

1078
00:40:35,100 --> 00:40:41,000
>> Když jsme se nyní považují za sebou první týden
třídy, když jsme se rozděl a panuj,

1079
00:40:41,000 --> 00:40:43,740
a my jsme v telefonním seznamu slzení,
a Jennifer, a my společně

1080
00:40:43,740 --> 00:40:47,500
Klíčovou myšlenkou, že hybnou silou, která měla
opakovat se znovu a znovu

1081
00:40:47,500 --> 00:40:50,930
nějak zahodili, vyhazování,
zahodili, polovina problému, nebo

1082
00:40:50,930 --> 00:40:55,320
obecně, tak, že se problém na polovinu,
a léčbě menší kus

1083
00:40:55,320 --> 00:40:59,630
problém, koncepčně ekvivalentní
na druhé straně, se nějak

1084
00:40:59,630 --> 00:41:00,910
zásadně lepší.

1085
00:41:00,910 --> 00:41:04,720
Ale s bublinou druhu, s výběr
druhu, s vkládací druhu, máme se mohou

1086
00:41:04,720 --> 00:41:06,560
žádné takové poznatky, že Jennifer udělal.

1087
00:41:06,560 --> 00:41:10,220
Jsme skoro stejně vrátil a
tam celá parta z časů, a my

1088
00:41:10,220 --> 00:41:12,650
Upraven věci trochu, vyměňovat
v tomto pořadí, možná

1089
00:41:12,650 --> 00:41:13,730
vkládání nebo výběru.

1090
00:41:13,730 --> 00:41:16,950
Ale na konci dne, jsem hodně
trapné chůze tam a zpět.

1091
00:41:16,950 --> 00:41:21,160
Neměli jsme využít co
chytrý jako Jennifer jsem rád dělení

1092
00:41:21,160 --> 00:41:22,040
a dobývání.

1093
00:41:22,040 --> 00:41:25,620
>> Takže sloučit druh, naopak, které
neuvidí až do příštího týdne, bude to

1094
00:41:25,620 --> 00:41:29,540
se pákového efektu, který Klíčovou myšlenkou vydělením
vstup, a pak na polovinu, a pak

1095
00:41:29,540 --> 00:41:30,580
polovinu a pak polovinu.

1096
00:41:30,580 --> 00:41:34,590
A při každém opakování tohoto cyklu,
třídění levou polovinu, a právo

1097
00:41:34,590 --> 00:41:38,200
polovinu, pak Levá polovina levé poloviny,
a pravá polovina doleva, pak

1098
00:41:38,200 --> 00:41:40,990
Levá polovina v pravé polovině, a
pravá polovina v pravé polovině.

1099
00:41:40,990 --> 00:41:42,840
A opakovat znovu a znovu.

1100
00:41:42,840 --> 00:41:46,170
>> Takže budete vidět vizuálně, ale
je to, co nás čeká příští týden.

1101
00:41:46,170 --> 00:41:49,760
A vůbec, když si myslíme, že něco
trochu těžší na takový případný problém.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Máme n druhou vlevo, n
druhou v polovině, a n

1104
00:41:57,970 --> 00:41:59,400
log n na pravé straně.

1105
00:41:59,400 --> 00:42:00,590
Takže tam je váš skutečný cliffhanger.

1106
00:42:00,590 --> 00:42:02,040
Uvidíme se v pondělí.

1107
00:42:02,040 --> 00:42:05,163
>> [APPLAUSE]