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

2
00:00:00,488 --> 00:00:10,800
>> [Přehrávání hudby]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Dobře.

4
00:00:13,500 --> 00:00:14,670
Dobře, vítej zpět.

5
00:00:14,670 --> 00:00:18,120
Tak tohle je 4. týden, začátek
této smlouvy, již.

6
00:00:18,120 --> 00:00:21,320
A budete připomenout, že minulý týden, dáme
kód stranou pro jen trochu

7
00:00:21,320 --> 00:00:24,240
a začali jsme mluvit trochu víc
na vysoké úrovni, o věci, jako je

8
00:00:24,240 --> 00:00:28,130
vyhledávání a řazení, které, ač
poněkud jednoduché nápady, jsou

9
00:00:28,130 --> 00:00:31,840
zástupce skupiny problémů
si začne řešit zejména

10
00:00:31,840 --> 00:00:34,820
jak začnete přemýšlet o finále
projekty a zajímavé řešení, které

11
00:00:34,820 --> 00:00:36,760
Možná budete muset reálných problémů.

12
00:00:36,760 --> 00:00:39,490
Nyní bublina druh byl jeden z nejjednodušších
Takové algoritmy, a to

13
00:00:39,490 --> 00:00:42,900
pracoval tím, že tyto malé množství
v seznamu nebo v poli typu

14
00:00:42,900 --> 00:00:46,530
bublina svou cestu až na vrchol, a
vysoká čísla pohybovat jejich cestu až do

15
00:00:46,530 --> 00:00:47,930
konec tohoto seznamu.

16
00:00:47,930 --> 00:00:50,650
>> A připomínají, že bychom mohli představit
bubble sort trochu

17
00:00:50,650 --> 00:00:52,310
něco takového.

18
00:00:52,310 --> 00:00:53,640
Tak mě nech jít dál a klepněte na tlačítko Spustit.

19
00:00:53,640 --> 00:00:55,350
Jsem předvybrány bublina třídění.

20
00:00:55,350 --> 00:00:58,920
A pokud si vzpomínám, že vyšší modrá
čáry představují velká čísla, malé

21
00:00:58,920 --> 00:01:03,300
Modré čáry představují malé množství, jako
projdeme to znovu a znovu a

22
00:01:03,300 --> 00:01:07,680
Znovu, porovnat dvě tabulky vedle sebe
další v červené barvě, jdeme k výměně

23
00:01:07,680 --> 00:01:11,010
největší a nejmenší, pokud
jsou mimo provoz.

24
00:01:11,010 --> 00:01:14,150
>> Takže to bude pokračovat dál a dál a jít
na, a uvidíte, že čím větší

25
00:01:14,150 --> 00:01:16,700
prvky dělají jejich cestu k
Dobře, a menší prvky jsou

26
00:01:16,700 --> 00:01:17,900
aby jejich cestu na levé straně.

27
00:01:17,900 --> 00:01:21,380
Ale začali jsme kvantifikovat
účinnost,

28
00:01:21,380 --> 00:01:22,970
Kvalita tohoto algoritmu.

29
00:01:22,970 --> 00:01:25,200
A my jsme řekli, že v nejhorším
případ, tento algoritmus se

30
00:01:25,200 --> 00:01:27,940
zhruba, kolik kroků?

31
00:01:27,940 --> 00:01:28,980
>> Tak n na druhou.

32
00:01:28,980 --> 00:01:30,402
A co bylo n?

33
00:01:30,402 --> 00:01:31,650
>> DIVÁKŮ: Počet prvků.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Takže n byl
počet prvků.

35
00:01:32,790 --> 00:01:33,730
A tak jsme si to často.

36
00:01:33,730 --> 00:01:36,650
Kdykoliv chceme mluvit o velikosti
o problému nebo velikost

37
00:01:36,650 --> 00:01:39,140
vstup, nebo množství času, které trvá
produkovat výstup, budeme jen

38
00:01:39,140 --> 00:01:41,610
zobecnit, co
vstup je pro n.

39
00:01:41,610 --> 00:01:45,970
Takže zpátky v týdnu 0, počet stran
v telefonním seznamu bylo n.

40
00:01:45,970 --> 00:01:47,550
Počet studentů
v místnosti n.

41
00:01:47,550 --> 00:01:49,630
Takže i zde sledujeme
že vzor.

42
00:01:49,630 --> 00:01:52,800
>> Nyní n na druhou není zvláště
rychle, takže jsme se snažili udělat lépe.

43
00:01:52,800 --> 00:01:55,970
A tak jsme se podívali na pár
další algoritmy, z nichž

44
00:01:55,970 --> 00:01:57,690
byl výběr sort.

45
00:01:57,690 --> 00:01:59,180
Takže výběr byl druh
trochu jiný.

46
00:01:59,180 --> 00:02:03,130
Bylo to skoro jednodušší, troufám si říci,
kdy jsem začal na začátku

47
00:02:03,130 --> 00:02:06,740
Seznam našich dobrovolníků a já jen znovu
a znovu a znovu procházel

48
00:02:06,740 --> 00:02:10,060
seznam, vyloupnutí nejmenší
prvek v čase a dávat jej nebo

49
00:02:10,060 --> 00:02:13,040
ji na začátku seznamu.

50
00:02:13,040 --> 00:02:16,410
>> Ale i to, když jsme začali uvažovat
přes matematiku a větší

51
00:02:16,410 --> 00:02:19,860
obraz, myslel na to, kolikrát
Byl jsem tam a zpět a zpět

52
00:02:19,860 --> 00:02:24,090
a tam jsme si řekli, v nejhorším případě,
Výběr druhu, byla taky co?

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

54
00:02:24,960 --> 00:02:27,490
Nyní, v reálném světě, mohou se
ve skutečnosti mírně rychlejší.

55
00:02:27,490 --> 00:02:30,620
Vzhledem k tomu, znovu jsem nemusel držet
backtracking, jakmile jsem řazeny

56
00:02:30,620 --> 00:02:31,880
nejmenší prvky.

57
00:02:31,880 --> 00:02:35,090
Ale pokud si myslíme, že o velké n,
pokud si trochu udělat z matematiky jako

58
00:02:35,090 --> 00:02:39,170
Já jsem na desce s n na druhou
minus něco, vše ostatní

59
00:02:39,170 --> 00:02:41,850
kromě n na druhou, jakmile n
dostane opravdu velký, není

60
00:02:41,850 --> 00:02:42,850
opravdu záležet.

61
00:02:42,850 --> 00:02:45,470
Takže jak počítačových vědců, jsme tak nějak
přimhouřit oko menší

62
00:02:45,470 --> 00:02:49,220
faktory a soustředit se pouze na faktoru v
výraz, který to bude dělat

63
00:02:49,220 --> 00:02:50,330
největší rozdíl.

64
00:02:50,330 --> 00:02:52,840
>> No, nakonec jsme se zaměřili
při vkládání druhu.

65
00:02:52,840 --> 00:02:56,620
A to byl podobný v duchu, ale
spíše než jít přes opakované a

66
00:02:56,620 --> 00:03:01,250
vyberte nejmenší prvek jeden na
Tentokrát jsem místo toho vzal za ruku, že jsem

67
00:03:01,250 --> 00:03:04,070
byla řešena, a rozhodl jsem se, všechno
Dobře, sem patří.

68
00:03:04,070 --> 00:03:06,160
Pak jsem se přesunul na další prvek
a rozhodl, že on nebo

69
00:03:06,160 --> 00:03:07,470
patřila zde.

70
00:03:07,470 --> 00:03:08,810
A pak jsem se přesunul dál a dál.

71
00:03:08,810 --> 00:03:11,780
A mohl bych se, po cestě,
přesunout tyto lidi, aby se

72
00:03:11,780 --> 00:03:13,030
aby pro ně prostor.

73
00:03:13,030 --> 00:03:16,880
Takže to bylo něco jako duševní zvrat
výběrového druhu, který jsme

74
00:03:16,880 --> 00:03:18,630
volal vložení řazení.

75
00:03:18,630 --> 00:03:20,810
>> Takže tato témata se objevují
v reálném světě.

76
00:03:20,810 --> 00:03:23,640
Ještě před několika lety, kdy určité
Senátor se ucházel o prezidenta,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, v době, kdy generální ředitel
Google, skutečně možnost

78
00:03:27,160 --> 00:03:28,040
aby ho vyslechnout.

79
00:03:28,040 --> 00:03:32,010
A my jsme si řekli, že sdílet YouTube
klip pro tebe, kdyby se nám podařilo otočit až

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

81
00:03:32,950 --> 00:03:39,360
>> [PŘEHRÁVÁNÍ]

82
00:03:39,360 --> 00:03:44,620
>> -Teď, senátor, jste zde na Google,
a já jsem rád, že předsednictví

83
00:03:44,620 --> 00:03:46,042
jako pohovoru.

84
00:03:46,042 --> 00:03:47,770
>> [Smích]

85
00:03:47,770 --> 00:03:50,800
>> -Teď je to těžké se dostat
práce jako prezident.

86
00:03:50,800 --> 00:03:52,480
A ty teď procházíš
ztuhlost nyní.

87
00:03:52,480 --> 00:03:54,330
Je to také těžké získat práci v Google.

88
00:03:54,330 --> 00:03:59,610
Máme na otázky a ptáme
Naši kandidáti otázky.

89
00:03:59,610 --> 00:04:02,250
A tohle je od Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Smích]

91
00:04:05,325 --> 00:04:06,400
-Myslíte si, že si dělám legraci?

92
00:04:06,400 --> 00:04:08,750
Je to tady.

93
00:04:08,750 --> 00:04:12,110
Jaký je nejúčinnější způsob, jak
seřadit milion dvě bit celé číslo?

94
00:04:12,110 --> 00:04:15,810
>> [Smích]

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

96
00:04:18,260 --> 00:04:19,029
>> Je mi líto.

97
00:04:19,029 --> 00:04:19,745
Možná, že bychom měli -

98
00:04:19,745 --> 00:04:21,000
>> Ne, ne, ne, ne, ne.

99
00:04:21,000 --> 00:04:21,470
>> -To není -

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

101
00:04:22,185 --> 00:04:25,328
>> -Myslím, že bublina druhu by
je špatný způsob, jak jít.

102
00:04:25,328 --> 00:04:26,792
>> [Smích]

103
00:04:26,792 --> 00:04:28,510
>> [Fandění a potlesk]

104
00:04:28,510 --> 00:04:31,211
>> -No tak, kdo mu to?

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

106
00:04:32,155 --> 00:04:33,350
>> [END PŘEHRÁVÁNÍ]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Tak tady to máte.

108
00:04:35,070 --> 00:04:39,600
Takže jsme začali kvantifikovat běh
krát, abych tak řekl, s něčím

109
00:04:39,600 --> 00:04:43,480
tzv. asymptotické notace, která je
jen s odkazem na náš druh soustružení

110
00:04:43,480 --> 00:04:47,420
slepé oko k těm menším faktorů a
jen při pohledu na dobu provozu,

111
00:04:47,420 --> 00:04:51,250
výkon těchto algoritmů,
jako n dostane opravdu velký v průběhu času.

112
00:04:51,250 --> 00:04:55,110
A tak jsme zavedli velký O. a velký O
představoval něco, co jsme si mysleli,

113
00:04:55,110 --> 00:04:57,000
jako horní mez.

114
00:04:57,000 --> 00:04:59,570
A skutečně, Barry, můžeme snížit
než mic trochu?

115
00:04:59,570 --> 00:05:01,040
>> Mysleli jsme si, ze je to horní mez.

116
00:05:01,040 --> 00:05:04,710
Tak velký O prostředků n mocnin, že
nejhorší případ, něco jako

117
00:05:04,710 --> 00:05:07,780
Výběr sort by se
n čtvercová kroky.

118
00:05:07,780 --> 00:05:10,310
Nebo něco podobného vložení druhu
by n na druhou kroky.

119
00:05:10,310 --> 00:05:15,150
Nyní něco jako vložení
sort, co bylo nejhorší?

120
00:05:15,150 --> 00:05:18,200
Vzhledem k tomu, pole, co je to nejhorší
možný scénář, že byste mohli najít

121
00:05:18,200 --> 00:05:20,650
sám tváří v tvář?

122
00:05:20,650 --> 00:05:21,860
>> Je to úplně obráceně, ne?

123
00:05:21,860 --> 00:05:24,530
Protože jestli je to úplně dozadu,
co musíte udělat spoustu práce.

124
00:05:24,530 --> 00:05:26,420
Protože pokud jste úplně dozadu,
budete si

125
00:05:26,420 --> 00:05:28,840
největší prvkem je zde, a to i když
patří tam.

126
00:05:28,840 --> 00:05:31,140
Takže se chystáte říct, jo, na
tento okamžik v čase, patříte sem,

127
00:05:31,140 --> 00:05:32,310
takže nechat to být.

128
00:05:32,310 --> 00:05:35,425
>> Pak si uvědomíte, oh, sakra, musím
přesunout o něco menší element

129
00:05:35,425 --> 00:05:36,470
nalevo od vás.

130
00:05:36,470 --> 00:05:38,770
Pak jsem to dělat znovu
a znovu a znovu.

131
00:05:38,770 --> 00:05:41,410
A když jsem šel tam a zpět, je
by se nějak cítit výkon

132
00:05:41,410 --> 00:05:45,540
že algoritmus, protože stále jsem
míchání všichni ostatní v

133
00:05:45,540 --> 00:05:46,510
pole, aby se prostor pro to.

134
00:05:46,510 --> 00:05:47,750
Tak to je nejhorší.

135
00:05:47,750 --> 00:05:48,570
>> Naproti tomu -

136
00:05:48,570 --> 00:05:50,320
a to byl cliffhanger poslední době -

137
00:05:50,320 --> 00:05:54,065
jsme si řekli, že vložení třídění
byla omega čeho?

138
00:05:54,065 --> 00:05:57,530
Jaký je nejlepší-case běh
čas vložení druhu?

139
00:05:57,530 --> 00:05:58,520
Takže je to vlastně n.

140
00:05:58,520 --> 00:06:00,980
To byl prázdný, že jsme opustili
na desce naposledy.

141
00:06:00,980 --> 00:06:03,160
>> A je to omega n, protože proč?

142
00:06:03,160 --> 00:06:06,630
No, v tom nejlepším případě to, co je
vložení třídění bude předána?

143
00:06:06,630 --> 00:06:09,830
No, seznam, který je zcela řazeny
již minimální práci dělat.

144
00:06:09,830 --> 00:06:12,460
Ale to, co je hezké o vložení druhu
je to, že z důvodu, že zde začíná a

145
00:06:12,460 --> 00:06:15,340
rozhodne, oh, ty jsi číslo
jeden, patříš sem.

146
00:06:15,340 --> 00:06:16,970
Ach, to je štěstí.

147
00:06:16,970 --> 00:06:17,740
>> Ty jsi číslo dvě.

148
00:06:17,740 --> 00:06:19,030
Také sem patří.

149
00:06:19,030 --> 00:06:21,010
Číslo tři, ještě lepší,
Patříš sem.

150
00:06:21,010 --> 00:06:25,210
Jakmile se dostane na konec
Seznam, na vkládacího SORT v pseudokódu

151
00:06:25,210 --> 00:06:28,010
že jsme procházeli slovně
Minule se to dělá.

152
00:06:28,010 --> 00:06:32,790
Ale výběr druhu, naopak,
stále dělá co?

153
00:06:32,790 --> 00:06:35,260
>> Dál v seznamu
znovu a znovu a znovu.

154
00:06:35,260 --> 00:06:39,160
Protože Klíčovou myšlenkou bylo jen
jakmile jste se podíval až do

155
00:06:39,160 --> 00:06:42,500
konec seznamu si můžete být jisti,
že prvek vyberete byla

156
00:06:42,500 --> 00:06:45,560
ve skutečnosti v současné době nejmenší prvek.

157
00:06:45,560 --> 00:06:48,920
Tak to různé mentální modely konec
up dávat některé velmi reálný svět

158
00:06:48,920 --> 00:06:53,130
rozdíly u nás, ale i v těchto
teoretické asymptotické rozdíly.

159
00:06:53,130 --> 00:06:56,910
>> Takže jen shrnout, pak velký O n
čtvercový, viděli jsme několik takových

160
00:06:56,910 --> 00:06:58,350
algoritmy tak daleko.

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

162
00:06:59,580 --> 00:07:02,870
Co je to algoritmus, který by
se říci, že velký O n?

163
00:07:02,870 --> 00:07:06,930
V nejhorším případě to trvá
lineární počet kroků.

164
00:07:06,930 --> 00:07:07,810
>> OK, lineární hledání.

165
00:07:07,810 --> 00:07:10,470
A v nejhorším případě, kdy je
prvek, který hledáte, pokud

166
00:07:10,470 --> 00:07:12,950
použití lineární hledání?

167
00:07:12,950 --> 00:07:14,680
>> OK, v nejhorším případě,
to není ani tam.

168
00:07:14,680 --> 00:07:17,000
Nebo v druhém nejhorším případě je to
úplně na konci, který je

169
00:07:17,000 --> 00:07:18,880
plus nebo mínus jeden krok rozdíl.

170
00:07:18,880 --> 00:07:21,180
Takže na konci dne,
můžeme říci, že je lineární.

171
00:07:21,180 --> 00:07:23,910
Velký O n by být lineární vyhledávání,
proto, že v nejhorším případě,

172
00:07:23,910 --> 00:07:26,610
prvek není to ani tam, nebo je to
úplně na konci.

173
00:07:26,610 --> 00:07:29,370
>> No, velký O log n.

174
00:07:29,370 --> 00:07:32,760
Nemluvili jsme velmi podrobně o
, ale my jsme viděli předtím.

175
00:07:32,760 --> 00:07:36,840
Co probíhá v tzv. logaritmický
čas, v nejhorším případě?

176
00:07:36,840 --> 00:07:38,500
>> Jo, binární vyhledávání.

177
00:07:38,500 --> 00:07:42,930
A binární hledání v nejhorším případě
může mít prvek někde

178
00:07:42,930 --> 00:07:45,640
střední, nebo někde
uvnitř pole.

179
00:07:45,640 --> 00:07:48,040
Ale najdete jen jednou vás
rozdělit seznam na polovinu, v roce

180
00:07:48,040 --> 00:07:48,940
poloviny, na polovinu, na polovinu.

181
00:07:48,940 --> 00:07:50,200
A pak ejhle, je to tam.

182
00:07:50,200 --> 00:07:52,500
Nebo znovu, v nejhorším případě,
to není ani tam.

183
00:07:52,500 --> 00:07:56,770
Ale vy nevíte, že to tam není
dokud se nějak dostat, že poslední

184
00:07:56,770 --> 00:08:00,470
zdola většina prvků podle polovinu
a polovinu a snížit.

185
00:08:00,470 --> 00:08:01,400
>> Velký O z 1.

186
00:08:01,400 --> 00:08:03,540
Tak bychom mohli o velký O 2, O 3 velké.

187
00:08:03,540 --> 00:08:06,260
Kdykoliv budete chtít jen konstantní počet,
jsme tak nějak prostě zjednodušit

188
00:08:06,260 --> 00:08:07,280
že tak velkou O. 1.

189
00:08:07,280 --> 00:08:10,440
I když, pokud realisticky, je potřeba
2, nebo dokonce 100 stupňů, pokud je to

190
00:08:10,440 --> 00:08:13,680
konstantní počet kroků,
řekneme velký O z 1.

191
00:08:13,680 --> 00:08:15,930
Co je to algoritmus, který je
ve velkém O. 1?

192
00:08:15,930 --> 00:08:18,350
>> DIVÁKŮ: Hledání délku
proměnné.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Hledání
délka proměnné?

194
00:08:21,090 --> 00:08:23,870
>> DIVÁKŮ: Ne, délka
pokud je již řazeno.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Dobrý.

196
00:08:24,160 --> 00:08:27,850
OK, takže najít délku něco
v případě, že délka tohoto něčeho, jako je

197
00:08:27,850 --> 00:08:30,020
pole, je uložen v nějaké proměnné.

198
00:08:30,020 --> 00:08:33,380
Protože můžete jen číst proměnnou,
nebo vytisknout proměnnou nebo

199
00:08:33,380 --> 00:08:34,960
jen obecně přístup k této proměnné.

200
00:08:34,960 --> 00:08:37,299
A voila, že trvá konstantní čas.

201
00:08:37,299 --> 00:08:38,909
>> Naopak, myslím, že zpět do nuly.

202
00:08:38,909 --> 00:08:42,460
Vzpomeňte si na první týden v C,
volání jen printf a tisk

203
00:08:42,460 --> 00:08:46,240
něco na obrazovce, je pravděpodobně
konstantní čas, protože to prostě trvá

204
00:08:46,240 --> 00:08:50,880
určitý počet CPU cyklů ukázat
tento text na obrazovce.

205
00:08:50,880 --> 00:08:52,720
Nebo čekat - je to tak?

206
00:08:52,720 --> 00:08:56,430
Jak jinak bychom mohli modelovat
výkon printf?

207
00:08:56,430 --> 00:09:00,420
By někdo chtěl nesouhlasit, že
Možná to opravdu není konstantní čas?

208
00:09:00,420 --> 00:09:03,600
V jakém smyslu by printf běží
čas, ve skutečnosti tiskne řetězec na

209
00:09:03,600 --> 00:09:05,580
na obrazovce, bude něco
jiné než konstantní.

210
00:09:05,580 --> 00:09:07,860
>> DIVÁKŮ: [neslyšitelné].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Jo.

212
00:09:08,230 --> 00:09:09,300
Takže to závisí na naší perspektivě.

213
00:09:09,300 --> 00:09:13,390
Pokud jsme vlastně myslet na vstup do
printf jako řetězec, a

214
00:09:13,390 --> 00:09:16,380
Proto měříme velikost, která
Vstup jeho délkou - tak říkejme

215
00:09:16,380 --> 00:09:17,780
že délka n i -

216
00:09:17,780 --> 00:09:21,990
pravděpodobně, printf je samo o sobě velký O n
, protože to bude trvat n kroky

217
00:09:21,990 --> 00:09:24,750
tisknout každý z těchto n
znaky, s největší pravděpodobností.

218
00:09:24,750 --> 00:09:27,730
Alespoň do té míry, že předpokládáme,
že možná to pomocí smyčky for

219
00:09:27,730 --> 00:09:28,560
pod kapotou.

220
00:09:28,560 --> 00:09:30,860
>> Ale budeme muset podívat na to
kód pochopit lépe.

221
00:09:30,860 --> 00:09:33,650
A skutečně, jakmile jste začít
analyzovat své vlastní algoritmy, budete

222
00:09:33,650 --> 00:09:34,900
doslova dělat jen to.

223
00:09:34,900 --> 00:09:37,765
Druh oka kódu a myslím,
o - v pořádku, mám tuto smyčku

224
00:09:37,765 --> 00:09:41,870
zde nebo mám vnořené smyčky zde
že bude dělat věci n n-krát,

225
00:09:41,870 --> 00:09:46,050
a můžete seřadit rozumu cestu
prostřednictvím kódu, i když je to

226
00:09:46,050 --> 00:09:47,980
pseudokódu, a ne skutečný kód.

227
00:09:47,980 --> 00:09:49,730
>> A co omega-n na druhou?

228
00:09:49,730 --> 00:09:53,582
Co byl algoritmus, který v nejlepším
případ, trvalo ještě n na druhou kroky?

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

230
00:09:54,014 --> 00:09:54,880
>> DIVÁKŮ: [neslyšitelné].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Takže výběr sort.

232
00:09:55,900 --> 00:09:59,150
Vzhledem k tomu, v tomto problému velmi snížena
k tomu, že opět nevím

233
00:09:59,150 --> 00:10:02,600
Našel jsem nejmenší proud, dokud
Zkontroloval jsem všechny zatraceně prvky.

234
00:10:02,600 --> 00:10:08,050
Tak omega, řekněme, n, se
Přišel s jedním.

235
00:10:08,050 --> 00:10:09,300
Vložení sort.

236
00:10:09,300 --> 00:10:12,370
Je-li seznam se stane být řazeny
již v nejlepším případě budeme muset

237
00:10:12,370 --> 00:10:15,090
aby jeden průchod přes to,
na kterém místě jsme si jisti.

238
00:10:15,090 --> 00:10:17,890
A pak by se dalo říci
být lineární, pro jistotu.

239
00:10:17,890 --> 00:10:20,570
>> Co je Omega 1?

240
00:10:20,570 --> 00:10:23,790
Co, v nejlepším případě, může trvat
konstantní počet kroků?

241
00:10:23,790 --> 00:10:27,220
Takže lineární vyhledávání, pokud jste právě štěstí
a prvek, který hledáte

242
00:10:27,220 --> 00:10:31,000
je hned na začátku seznamu,
jestli je to to, kam spuštění

243
00:10:31,000 --> 00:10:33,070
lineární průchod z tohoto seznamu.

244
00:10:33,070 --> 00:10:35,180
>> A to je pravda
řada věcí.

245
00:10:35,180 --> 00:10:37,660
Například, i binární
hledání omegou 1.

246
00:10:37,660 --> 00:10:40,310
Protože co když opravdu zatraceně
štěstí a plácnutí DAB uprostřed

247
00:10:40,310 --> 00:10:42,950
vaše pole je číslo
jste hledali?

248
00:10:42,950 --> 00:10:45,730
Takže můžete mít štěstí tam, stejně.

249
00:10:45,730 --> 00:10:49,190
>> Ten konečně, omega n log n.

250
00:10:49,190 --> 00:10:52,573
Tak n log n, my jsme opravdu
mluvit o tom, ještě ne, ale -

251
00:10:52,573 --> 00:10:53,300
>> DIVÁKŮ: Sloučit druh?

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

253
00:10:53,960 --> 00:10:56,920
To byl cliffhanger poslední době,
kde jsme navrhli, a ukázali jsme

254
00:10:56,920 --> 00:10:58,600
vizuálně, že existují algoritmy.

255
00:10:58,600 --> 00:11:02,470
A sloučit druh jen jeden takový
algoritmus, který je v podstatě rychlejší

256
00:11:02,470 --> 00:11:03,450
než některé z těchto ostatních kluků.

257
00:11:03,450 --> 00:11:07,800
Ve skutečnosti, je krátký spojit nejen
nejlepším případě n log n, v nejhorším

258
00:11:07,800 --> 00:11:09,460
Případ n log n.

259
00:11:09,460 --> 00:11:14,540
A když máte tuto koincidenci
omega a velké O je totéž?

260
00:11:14,540 --> 00:11:17,310
Můžeme vlastně popisovat to jako to, co je
tzv. theta, když je to

261
00:11:17,310 --> 00:11:18,220
trochu méně časté.

262
00:11:18,220 --> 00:11:21,730
Ale to znamená jen dvě meze,
V tomto případě, jsou stejné.

263
00:11:21,730 --> 00:11:25,770
>> Takže sloučit druh, co to
Opravdu se redukuje na pro nás?

264
00:11:25,770 --> 00:11:27,000
No, vzpomínám motivaci.

265
00:11:27,000 --> 00:11:30,340
Dovolte mi, abych vytáhnout další animaci, která
jsme se nedíval na minule.

266
00:11:30,340 --> 00:11:33,390
Ten, stejný nápad, ale
je to trochu větší.

267
00:11:33,390 --> 00:11:36,160
A já jdu dál a poukázat na
První - máme kurzor na druh

268
00:11:36,160 --> 00:11:39,410
vlevo nahoře, pak výběr třídění,
bublina třídění, pár dalších druhů -

269
00:11:39,410 --> 00:11:42,670
shell a rychle - že jsme spolu nemluvili
o, a halda a sloučit druh.

270
00:11:42,670 --> 00:11:47,090
>> Tak se alespoň pokusit zaměřit svůj pohled na
první tři vlevo a pak

271
00:11:47,090 --> 00:11:49,120
sloučit druh, když kliknu
tato zelená šipka.

272
00:11:49,120 --> 00:11:51,900
Ale nechám všechny z nich spustit, jen aby
dá vám pocit rozmanitosti

273
00:11:51,900 --> 00:11:53,980
algoritmy, které existují ve světě.

274
00:11:53,980 --> 00:11:56,180
Chystám se nechat to běžet
jen na pár vteřin.

275
00:11:56,180 --> 00:11:59,640
A pokud se soustředíte vaše oči - vyberte si
algoritmus, soustředit se na to jen za

276
00:11:59,640 --> 00:12:02,970
sekund - Začnete vidět
vzor, ​​který to provádí.

277
00:12:02,970 --> 00:12:04,530
>> Merge sort, oznámení, je hotovo.

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

279
00:12:06,430 --> 00:12:09,480
takže se zdá, jsme představili tři
nejhorší algoritmy minulý týden.

280
00:12:09,480 --> 00:12:12,960
Ale to je dobře, že jsme tady dnes
se na druhu korespondence, který je jedním z

281
00:12:12,960 --> 00:12:16,500
koncentrace je snazší je podívat se na, a to i
i když to asi bude ohýbat vaše mysl

282
00:12:16,500 --> 00:12:17,490
jen trochu.

283
00:12:17,490 --> 00:12:21,130
Zde můžeme vidět, jak moc
Výběr trochu naštve.

284
00:12:21,130 --> 00:12:24,600
>> Ale na druhou stranu, je to
velmi snadno implementovat.

285
00:12:24,600 --> 00:12:28,160
A možná pro sadu P 3, to je jedna z
algoritmy jste se rozhodli realizovat

286
00:12:28,160 --> 00:12:28,960
pro standardní verzi.

287
00:12:28,960 --> 00:12:30,970
Naprosto v pořádku, zcela správné.

288
00:12:30,970 --> 00:12:35,210
>> Ale opět, jak n se zvětší, pokud se
možnost provést rychlejší algoritmus

289
00:12:35,210 --> 00:12:39,020
chtěl sloučit druh, šance jsou větší a
větší vstupy, váš kód je jen

290
00:12:39,020 --> 00:12:39,800
bude běžet rychleji.

291
00:12:39,800 --> 00:12:41,090
Váš web bude fungovat lépe.

292
00:12:41,090 --> 00:12:42,650
Vaši uživatelé se bude šťastnější.

293
00:12:42,650 --> 00:12:45,280
A tak jsou tyto účinky
skutečně dává

294
00:12:45,280 --> 00:12:47,350
nám některé hlubší myšlenka.

295
00:12:47,350 --> 00:12:49,990
>> Takže pojďme se podívat na to, co sloučit
Třídění je vlastně vše kolem.

296
00:12:49,990 --> 00:12:52,992
Super věc je, že sloučení
Třídění je právě tento.

297
00:12:52,992 --> 00:12:56,300
To je opět to, co jsme tzv.
pseudokódu, pseudokódu bytost

298
00:12:56,300 --> 00:12:57,720
Angličtina-jako syntax.

299
00:12:57,720 --> 00:12:59,890
A jednoduchost je
druh fascinující.

300
00:12:59,890 --> 00:13:02,840
>> Takže na vstupu n prvků - tak, že
prostě znamená, tady je pole.

301
00:13:02,840 --> 00:13:04,000
Je tu n věci v něm.

302
00:13:04,000 --> 00:13:05,370
To je vše, co říkáme tam.

303
00:13:05,370 --> 00:13:07,560
>> Jestliže je n menší než 2, vrátit.

304
00:13:07,560 --> 00:13:08,640
Tak to je jen triviální případ.

305
00:13:08,640 --> 00:13:12,580
Jestliže je n menší než 2, pak samozřejmě je to
1 nebo 0, v tomto případě jde o to

306
00:13:12,580 --> 00:13:14,780
je již řazeno nebo neexistující,
takže stačí vrátit.

307
00:13:14,780 --> 00:13:15,900
Není nic dělat.

308
00:13:15,900 --> 00:13:18,360
Takže je to jednoduchý případ trhat off.

309
00:13:18,360 --> 00:13:20,110
>> Jinak máme tři kroky.

310
00:13:20,110 --> 00:13:23,650
Řazení levou polovinu prvků, třídění
pravá polovina prvků,

311
00:13:23,650 --> 00:13:26,650
a pak sloučit seřazené poloviny.

312
00:13:26,650 --> 00:13:29,400
Co je zajímavé je to, že
Jsem trochu plavit, že jo?

313
00:13:29,400 --> 00:13:32,300
Je to něco jako definice v kruhu
do tohoto algoritmu.

314
00:13:32,300 --> 00:13:35,986
V jakém smyslu je tento algoritmus je
definice kruhové?

315
00:13:35,986 --> 00:13:37,850
>> DIVÁKŮ: [neslyšitelné].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Jo, můj algoritmus třídění,
dva z jeho kroky jsou "druh

317
00:13:41,670 --> 00:13:44,640
něco. "A tak to zamlouvá
otázka, no, co budu používat

318
00:13:44,640 --> 00:13:46,460
třídit levou polovinu
i pravá polovina?

319
00:13:46,460 --> 00:13:49,600
A nejlepší je, že i když
Znovu, toto je mysl-ohýbání

320
00:13:49,600 --> 00:13:54,030
část potenciálně, můžete použít stejné
algoritmus pro třídění levou polovinu.

321
00:13:54,030 --> 00:13:54,700
>> Ale počkejte chvilku.

322
00:13:54,700 --> 00:13:57,070
Když jste řekl, třídit
levá polovina, co jsou dva

323
00:13:57,070 --> 00:13:58,240
kroky bude dál?

324
00:13:58,240 --> 00:14:00,550
Vyřešíme levou polovinu
levá polovina a právo

325
00:14:00,550 --> 00:14:01,420
polovina levé polovině.

326
00:14:01,420 --> 00:14:04,430
Sakra, jak to mám vyřešit ty dva
Půlky nebo čtvrtky, teď?

327
00:14:04,430 --> 00:14:05,260
>> Ale to je v pořádku.

328
00:14:05,260 --> 00:14:07,830
Máme třídící algoritmus zde.

329
00:14:07,830 --> 00:14:10,660
A i když byste mohli starat vůbec
Zpočátku to tak trochu nekonečný

330
00:14:10,660 --> 00:14:12,780
smyčky, je to cyklus, který nikdy
skončí - to bude

331
00:14:12,780 --> 00:14:15,770
konec jednou, co se stane?

332
00:14:15,770 --> 00:14:16,970
Jakmile n je menší než 2.

333
00:14:16,970 --> 00:14:19,180
Který nakonec se stane,
protože pokud budete mít na polovinu a

334
00:14:19,180 --> 00:14:23,020
snížit na polovinu těchto polovin, určitě
nakonec se chystáte na konec

335
00:14:23,020 --> 00:14:25,350
s jen 1 nebo 0 prvků.

336
00:14:25,350 --> 00:14:28,500
V tom okamžiku, tento algoritmus
říká, že je hotovo.

337
00:14:28,500 --> 00:14:31,020
>> Takže magie v této
algoritmus se zdá být v

338
00:14:31,020 --> 00:14:33,470
že poslední krok, slučování.

339
00:14:33,470 --> 00:14:37,190
To jednoduchá myšlenka jen sloučení dvou
věci, to je to, co nakonec bude

340
00:14:37,190 --> 00:14:40,920
které nám umožní vyřešit řadu,
řekněme, osm prvků.

341
00:14:40,920 --> 00:14:44,410
Takže mám dalších osm stresové míčky
zde osm kousky papíru, a jeden

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

343
00:14:45,500 --> 00:14:46,140
které jsem se udržet.

344
00:14:46,140 --> 00:14:46,960
>> [Smích]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Kdybychom mohli mít osm
dobrovolníků, a uvidíme, jestli to půjde

346
00:14:48,970 --> 00:14:51,430
hrát se na to, tak.

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

348
00:14:52,500 --> 00:14:53,565
Počítačová věda je stále bavit.

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

350
00:14:54,320 --> 00:14:57,770
Tak co vy tři,
Největší ruka nahoře.

351
00:14:57,770 --> 00:14:58,580
Čtyři v zádech.

352
00:14:58,580 --> 00:15:02,220
A co budeme dělat vás
tři v této řadě?

353
00:15:02,220 --> 00:15:03,390
A čtyři v přední části.

354
00:15:03,390 --> 00:15:04,920
Takže si osm, jít nahoru.

355
00:15:04,920 --> 00:15:12,060
>> [Smích]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Ve skutečnosti jsem
nejste jisti, co to je.

357
00:15:13,450 --> 00:15:14,810
Je to stresové koule?

358
00:15:14,810 --> 00:15:16,510
Na stolní lampy?

359
00:15:16,510 --> 00:15:18,650
Materiál?

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

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

362
00:15:20,160 --> 00:15:21,310
Tak pojď nahoru.

363
00:15:21,310 --> 00:15:22,310
Kdo by chtěl -

364
00:15:22,310 --> 00:15:23,570
udržet přichází.

365
00:15:23,570 --> 00:15:24,240
Pojďme se podívat.

366
00:15:24,240 --> 00:15:26,460
A to vám dává lokalitě -

367
00:15:26,460 --> 00:15:27,940
jste na místě jeden.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, počkej.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - Oh, dobře.

370
00:15:30,760 --> 00:15:31,310
Tak jo, jsme v pohodě.

371
00:15:31,310 --> 00:15:35,130
Dobře, takže všichni mají sídlo,
ale ne na sklo Google.

372
00:15:35,130 --> 00:15:36,475
Dovolte mi, abych do fronty tyto nahoru.

373
00:15:36,475 --> 00:15:37,115
Jak se jmenujete?

374
00:15:37,115 --> 00:15:37,440
>> Michelle Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID Malan: Michelle?

376
00:15:38,090 --> 00:15:42,000
V pořádku, dostanete vypadat
geek, jestli je to OK.

377
00:15:42,000 --> 00:15:44,625
No, já taky, myslím,
jen na chvíli.

378
00:15:44,625 --> 00:15:45,875
Dobře, v pohotovostním režimu.

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

380
00:15:48,510 --> 00:15:50,950
Snažili jsme se přijít s
případ použití pro Google skla a my

381
00:15:50,950 --> 00:15:53,750
si myslel, že by bylo zábavné se prostě
to když jsou lidé na jevišti.

382
00:15:53,750 --> 00:15:57,120
Budeme zaznamenávat svět
z jejich pohledu.

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

384
00:15:58,410 --> 00:15:59,830
Není asi to, co Google určen.

385
00:15:59,830 --> 00:16:02,260
Dobře, pokud vám nevadí, že na sobě
na dobu příštích nepříjemných minut,

386
00:16:02,260 --> 00:16:03,150
že by bylo báječné.

387
00:16:03,150 --> 00:16:08,620
>> Dobře, takže tady máme řadu
prvky, a že pole, podle

388
00:16:08,620 --> 00:16:11,480
kousky papíru v těchto lidech "
ruce, je v současné době netříděný.

389
00:16:11,480 --> 00:16:12,050
>> Michelle: Oh, to je tak divné.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Je to do značné míry náhodné.

391
00:16:12,810 --> 00:16:15,760
A za chvíli se budeme snažit
realizovat sloučit dohromady jakousi

392
00:16:15,760 --> 00:16:17,950
a zjistit, kde ten klíč je vhled.

393
00:16:17,950 --> 00:16:21,970
A trik tady se druhu korespondence je
něco, co jsme se dosud předpokládalo.

394
00:16:21,970 --> 00:16:24,030
Potřebujeme tedy nějaký
prostor navíc.

395
00:16:24,030 --> 00:16:26,650
Tak co to bude zejména
Zajímavé na tom je, že se jedná

396
00:16:26,650 --> 00:16:29,270
kluci budou trochu pohybovat
bit, protože budu předpokládat, že

397
00:16:29,270 --> 00:16:31,880
je tam navíc pole prostoru,
řekněme, hned za nimi.

398
00:16:31,880 --> 00:16:34,570
>> Takže pokud jsou za jejich předsedy,
to je sekundární pole.

399
00:16:34,570 --> 00:16:36,960
Pokud jste zde sídlil, to je
primární pole.

400
00:16:36,960 --> 00:16:40,170
Ale to je zdroj, který máme
nevyužívají pákový efekt, tak daleko s bublinou

401
00:16:40,170 --> 00:16:42,040
druhu, s výběrem druhu,
s vkládací druhu.

402
00:16:42,040 --> 00:16:44,600
Připomeňme si minulý týden, všichni jen
druh míchány na místě.

403
00:16:44,600 --> 00:16:46,840
Neměli používat žádnou další paměť.

404
00:16:46,840 --> 00:16:49,310
Udělali jsme prostor pro lidi tím,
pohybující se lidé kolem.

405
00:16:49,310 --> 00:16:50,580
>> Tak to je klíčový vhled taky.

406
00:16:50,580 --> 00:16:53,410
Tam je to kompromis, obecně v
výpočetní technika, zdrojů.

407
00:16:53,410 --> 00:16:55,800
Chcete-li urychlit něco
například čas, budete

408
00:16:55,800 --> 00:16:56,900
muset zaplatit cenu.

409
00:16:56,900 --> 00:17:00,750
A jedna z těchto cen je velmi často
prostor, množství paměti nebo pevného

410
00:17:00,750 --> 00:17:01,700
disku, který používáte.

411
00:17:01,700 --> 00:17:03,640
Nebo, upřímně řečeno, výše
programátor času.

412
00:17:03,640 --> 00:17:06,700
Jak dlouho to trvá vám, člověk,
skutečně realizovat některé další

413
00:17:06,700 --> 00:17:07,829
komplikovaný algoritmus.

414
00:17:07,829 --> 00:17:09,760
Ale pro dnešek, trade-off
je čas a prostor.

415
00:17:09,760 --> 00:17:11,930
>> Takže pokud jste mohl jen zvednout vaše
čísla, takže můžeme vidět, že jste

416
00:17:11,930 --> 00:17:15,839
skutečně odpovídající 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Výborný.

418
00:17:16,599 --> 00:17:19,520
Takže budu snažit organizovat
věci, může-li jste právě

419
00:17:19,520 --> 00:17:21,800
za mnou tady.

420
00:17:21,800 --> 00:17:26,650
>> Takže budu realizovat jednak
Prvním krokem tohoto pseudokódu, který je

421
00:17:26,650 --> 00:17:29,440
na vstupu prvků n, pokud je n
méně než 2, pak se vrátit.

422
00:17:29,440 --> 00:17:31,370
Je zřejmé, že není
Použít, takže jsme dál.

423
00:17:31,370 --> 00:17:33,340
Takže řadit levou polovinu prvků.

424
00:17:33,340 --> 00:17:36,220
Takže to znamená, že budu zaměřit své
pozornost na chvíli o těchto

425
00:17:36,220 --> 00:17:37,310
čtyři chlapi.

426
00:17:37,310 --> 00:17:39,774
Tak jo, co mám příště udělat?

427
00:17:39,774 --> 00:17:40,570
>> DIVÁKŮ: Řazení levou polovinu.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Takže teď musím vyřešit
Levá polovina těchto kluků.

429
00:17:42,780 --> 00:17:45,580
Protože opět předpokládejme, že na sebe na
Cílem je seřadit levou polovinu.

430
00:17:45,580 --> 00:17:46,440
Jak to děláte, že?

431
00:17:46,440 --> 00:17:49,140
Stačí sledovat instrukce, a to i
když děláme to znovu.

432
00:17:49,140 --> 00:17:50,160
Takže řadit levou polovinu.

433
00:17:50,160 --> 00:17:52,030
Teď jsem třídění tihle dva.

434
00:17:52,030 --> 00:17:53,563
Co bude následovat?

435
00:17:53,563 --> 00:17:54,510
>> DIVÁKŮ: Řazení levou polovinu.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: Řazení levou polovinu.

437
00:17:55,460 --> 00:18:00,680
Takže teď ty, toto sedadlo zde
je seznam velikosti 1.

438
00:18:00,680 --> 00:18:01,365
A co že se to jmenuješ?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Princess Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Princezna Daisy je tady.

441
00:18:03,690 --> 00:18:07,470
A tak je již řazeno, protože
Seznam je velikosti 1.

442
00:18:07,470 --> 00:18:09,490
Co mám dělat další?

443
00:18:09,490 --> 00:18:13,680
OK, návrat, protože tento seznam je
velikost 1, který je menší než 2.

444
00:18:13,680 --> 00:18:14,320
Tak co je další krok?

445
00:18:14,320 --> 00:18:17,490
A teď jste si na druh
ustoupit ve vaší mysli.

446
00:18:17,490 --> 00:18:19,340
>> Řazení pravou polovinu, což je -

447
00:18:19,340 --> 00:18:19,570
Jak se jmenujete?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID Malan: Linda.

450
00:18:20,980 --> 00:18:23,210
A tak to, co budeme dělat teď,
máme seznam o velikosti 1?

451
00:18:23,210 --> 00:18:24,440
>> DIVÁKŮ: Návrat.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: Opatrně.

453
00:18:24,760 --> 00:18:29,540
Vrátíme se první, a nyní třetí
krok - a když jsem se trochu popsat ji

454
00:18:29,540 --> 00:18:33,490
zahrnuje dvě místa teď, teď jsem
mají sloučit tyto dva prvky.

455
00:18:33,490 --> 00:18:35,530
Takže teď bohužel prvky
jsou mimo provoz.

456
00:18:35,530 --> 00:18:39,920
Ale to je místo, kde proces sloučení
začíná být přesvědčivé.

457
00:18:39,920 --> 00:18:42,410
>> Takže pokud jste mohl postavit jen za
Okamžik, budu tě potřebuju, v

458
00:18:42,410 --> 00:18:44,170
okamžik, krok za svého křesla.

459
00:18:44,170 --> 00:18:46,480
A pokud Linda, protože 2 je
menší než 4, proč ne

460
00:18:46,480 --> 00:18:48,130
Přijedete kolem první?

461
00:18:48,130 --> 00:18:48,690
Zůstaň tam.

462
00:18:48,690 --> 00:18:50,520
Takže Linda, přijdete asi první.

463
00:18:50,520 --> 00:18:53,820
>> Nyní ve skutečnosti, pokud je to jen pole
jsme mohli jen přesunout ji v reálném čase

464
00:18:53,820 --> 00:18:55,360
z tohoto křesla tomto místě.

465
00:18:55,360 --> 00:18:57,770
Tak si představte, že se nějaká konstanta
počet kroků 1.

466
00:18:57,770 --> 00:18:58,480
A teď -

467
00:18:58,480 --> 00:19:01,490
ale musíme dát do
Na prvním místě je zde.

468
00:19:01,490 --> 00:19:03,930
>> A teď, pokud byste mohli přijít kolem,
stejně, budeme

469
00:19:03,930 --> 00:19:06,300
být v místě dvou.

470
00:19:06,300 --> 00:19:09,120
A i když to pocit, že je to
přičemž na chvíli, co je pěkné je nyní

471
00:19:09,120 --> 00:19:14,710
že levá polovina
levá polovina je nyní řazeny.

472
00:19:14,710 --> 00:19:18,010
Takže jaký byl další krok, když jsme teď
převinout dále v příběhu?

473
00:19:18,010 --> 00:19:18,980
>> Diváků: Pravá polovina.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: Třídit pravou polovinu.

475
00:19:19,900 --> 00:19:21,320
Takže vy musíte udělat to stejně.

476
00:19:21,320 --> 00:19:23,510
Takže pokud byste mohli postavit
jen na chvíli?

477
00:19:23,510 --> 00:19:25,192
A Jak se jmenujete?

478
00:19:25,192 --> 00:19:25,540
>> JESS: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID Malan: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, takže Jess je nyní vlevo
polovina pravé polovině.

481
00:19:29,720 --> 00:19:31,400
A tak je seznam velikosti 1.

482
00:19:31,400 --> 00:19:32,380
Ona samozřejmě řazeny.

483
00:19:32,380 --> 00:19:33,070
A jmenujete?

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

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle je samozřejmě
Seznam velikosti 1.

486
00:19:35,340 --> 00:19:36,050
Už je třídit.

487
00:19:36,050 --> 00:19:38,690
Takže teď magie stane,
proces sloučení.

488
00:19:38,690 --> 00:19:39,790
Takže kdo přijde jako první?

489
00:19:39,790 --> 00:19:41,560
Je zřejmé, Michelle.

490
00:19:41,560 --> 00:19:43,280
Takže pokud jste přišel zadem.

491
00:19:43,280 --> 00:19:47,090
Prostor máme k dispozici pro ni teď
je hned za téhle židli zde.

492
00:19:47,090 --> 00:19:51,580
A teď, když se může vrátit také,
nyní máme, aby bylo jasno, dva

493
00:19:51,580 --> 00:19:53,810
poloviny, každá o velikosti 2 -

494
00:19:53,810 --> 00:19:57,090
a jen pro zobrazení jeho zájmu, pokud
by mohlo být trochu prostoru -

495
00:19:57,090 --> 00:19:59,780
zbyla polovina tady, jeden
Pravá polovina zde.

496
00:19:59,780 --> 00:20:01,160
>> Rewind dále v příběhu.

497
00:20:01,160 --> 00:20:02,270
Co krok dál?

498
00:20:02,270 --> 00:20:03,030
>> Diváků: Sloučit.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Takže teď musíme spojit.

500
00:20:04,160 --> 00:20:07,490
Takže OK, takže teď, naštěstí jsme
právě uvolnil čtyři židle.

501
00:20:07,490 --> 00:20:11,480
Takže jsme použili dvakrát tolik paměti, ale
můžeme dát flip-flopu mezi

502
00:20:11,480 --> 00:20:12,330
dvě pole.

503
00:20:12,330 --> 00:20:14,190
Takže, jaké číslo je na prvním místě?

504
00:20:14,190 --> 00:20:14,850
Takže Michelle, samozřejmě.

505
00:20:14,850 --> 00:20:16,680
Tak pojď se kolem sebe a vzít
vaše sídlo zde.

506
00:20:16,680 --> 00:20:19,120
A pak číslo 2 je zřejmě
Dále, pokud jste sem přišel.

507
00:20:19,120 --> 00:20:21,520
Číslo 4, číslo 6.

508
00:20:21,520 --> 00:20:23,390
A opět, i když je
trochu chůze zapojen,

509
00:20:23,390 --> 00:20:26,010
Opravdu, mohly by stát okamžitě,
pohybem jednoho -

510
00:20:26,010 --> 00:20:26,880
OK, dobře hrál.

511
00:20:26,880 --> 00:20:28,350
>> [Smích]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: A teď jsme
v dobrém stavu.

513
00:20:29,680 --> 00:20:34,910
Levá polovina celého
Vstup byl nyní řazeny.

514
00:20:34,910 --> 00:20:37,370
Dobře, takže tito lidé měli
Výhodou mého -

515
00:20:37,370 --> 00:20:40,340
jak to skončí všechny holky na
doleva a všichni kluci na pravé straně?

516
00:20:40,340 --> 00:20:42,450
>> OK, takže kluci 'se nyní.

517
00:20:42,450 --> 00:20:44,680
Nebudu vás provede
tyto kroky.

518
00:20:44,680 --> 00:20:46,550
Uvidíme, jestli se nám podaří znovu
stejný pseudokódu.

519
00:20:46,550 --> 00:20:50,050
Chcete-li jít dopředu a vstát,
a vy, dovolte mi, abych vám mikrofon.

520
00:20:50,050 --> 00:20:52,990
Uvidíme, jestli nemůže replikovat to, co
Prostě jsme tady na

521
00:20:52,990 --> 00:20:53,880
Druhý konec seznamu.

522
00:20:53,880 --> 00:20:59,530
Kdo potřebuje mluvit jako první,
na základě algoritmu?

523
00:20:59,530 --> 00:21:03,210
Takže vysvětlit, co děláte, než
provedete nohy pohyby.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: Dobře, takže od té doby
Jsem Levá polovina

525
00:21:05,930 --> 00:21:07,790
levá polovina, vrátím.

526
00:21:07,790 --> 00:21:08,730
Je to tak?

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Dobrý.

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: A pak -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Kdo
mic jít dál?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: Další číslo.

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2: Tak jsem pravá polovina
na levé polovině

532
00:21:14,720 --> 00:21:17,830
levá polovina, a já jsem se vrátit.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Dobrý.

534
00:21:18,050 --> 00:21:18,550
Vrátíte se.

535
00:21:18,550 --> 00:21:21,855
Takže teď, co je další pro vás dva?

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2: Chceme zjistit, kdo je menší.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Přesně tak.

538
00:21:24,200 --> 00:21:24,940
Chceme spojit.

539
00:21:24,940 --> 00:21:27,590
Prostor budeme používat ke sloučení
vás do, i když jsou

540
00:21:27,590 --> 00:21:30,250
samozřejmě řazeny už jdeme
podle stejného algoritmu.

541
00:21:30,250 --> 00:21:31,560
Tak kdo jede zpět jako první?

542
00:21:31,560 --> 00:21:35,720
Takže 3 a potom 7..

543
00:21:35,720 --> 00:21:38,570
A teď jde mic
na ty chlapy, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Takže jsem pravá polovina
levá polovina, a moje je n menší než

545
00:21:43,590 --> 00:21:45,048
1, takže jsem jen tak projít -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Dobrý.

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4: Jsem pravá polovina
pravá polovina pravé polovině, a já jsem

548
00:21:49,450 --> 00:21:51,740
také jeden člověk, takže jsem
chystá k návratu.

549
00:21:51,740 --> 00:21:52,990
Takže teď jsme sloučit.

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

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Tak jdeme zpátky.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Takže jdete do zad.

553
00:21:57,160 --> 00:21:59,200
Takže 5 jde první, a pak 8.

554
00:21:59,200 --> 00:22:01,240
A teď publikum, což je
krok musíme se přetočit

555
00:22:01,240 --> 00:22:02,200
zpět v našich myslích?

556
00:22:02,200 --> 00:22:02,940
>> Diváků: Sloučit.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: Sloučení levé a pravé poloviny
polovinu původního levé polovině.

558
00:22:07,270 --> 00:22:08,840
Takže teď -

559
00:22:08,840 --> 00:22:10,520
a jen proto, aby to bylo jasné,
aby trochu prostoru

560
00:22:10,520 --> 00:22:11,690
mezi vámi dva kluci.

561
00:22:11,690 --> 00:22:13,800
Takže teď, že to jsou dva seznamy,
doleva a doprava.

562
00:22:13,800 --> 00:22:18,320
Tak jak jsme se spojit ty lidi do
Přední řada sedadel znovu?

563
00:22:18,320 --> 00:22:19,600
>> 3. jde první.

564
00:22:19,600 --> 00:22:20,850
Pak 5, samozřejmě.

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

566
00:22:23,110 --> 00:22:27,330
Potom 7, 8 a teď.

567
00:22:27,330 --> 00:22:28,710
OK, a teď jsme?

568
00:22:28,710 --> 00:22:29,650
>> Diváků: nedělá.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Není udělal, protože
samozřejmě, je tu jeden krok zbývá.

570
00:22:32,440 --> 00:22:35,720
Ale znovu, důvod, proč jsem pomocí tohoto
žargonu jako "dozadu ve vaší mysli,"

571
00:22:35,720 --> 00:22:37,160
je to proto, že je opravdu
co se děje.

572
00:22:37,160 --> 00:22:39,610
Jedeme přes všechny tyto kroky,
ale my jsme trochu odmlčel

573
00:22:39,610 --> 00:22:42,480
moment, potápění hlouběji do
algoritmus, zastavil se na okamžik,

574
00:22:42,480 --> 00:22:45,840
potápění hlouběji do algoritmu a
teď musíme nějak dozadu v našem

575
00:22:45,840 --> 00:22:49,430
mysl a vrátit zpět všechny tyto vrstvy
že jsme trochu přidržen.

576
00:22:49,430 --> 00:22:51,790
>> Takže teď máme dva seznamy velikosti 4.

577
00:22:51,790 --> 00:22:54,790
Pokud jste mohl postavit jeden poslední čas
a aby se trochu prostoru zde

578
00:22:54,790 --> 00:22:57,230
bylo zřejmé, že se jedná o levou
polovina z originálu,

579
00:22:57,230 --> 00:22:58,620
Pravá polovina originálu.

580
00:22:58,620 --> 00:23:01,060
Kdo je první číslo, které jsme
musí vytáhnout na zadní?

581
00:23:01,060 --> 00:23:01,870
Michelle samozřejmě.

582
00:23:01,870 --> 00:23:03,230
>> Takže jsme dali Michelle zde.

583
00:23:03,230 --> 00:23:05,080
A kdo má číslo 2?

584
00:23:05,080 --> 00:23:06,440
Číslo 2 je na zadní straně stejně.

585
00:23:06,440 --> 00:23:07,800
Číslo 3?

586
00:23:07,800 --> 00:23:08,510
Výborný.

587
00:23:08,510 --> 00:23:16,570
Č. 4, č. 5, č. 6,
číslo 7 a č. 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, tak to připadalo jako hodně
kroků, pro jistotu.

589
00:23:18,850 --> 00:23:22,390
Ale teď uvidíme, jestli nemůžeme potvrdit,
nějak intuitivně, že tento

590
00:23:22,390 --> 00:23:26,190
algoritmus zásadně, zejména pokud
n dostane opravdu velký, jak jsme viděli

591
00:23:26,190 --> 00:23:29,170
s animací, je
zásadně rychlejší.

592
00:23:29,170 --> 00:23:33,400
Takže tvrdím, tento algoritmus, v nejhorším
případ a dokonce v nejlepším případě,

593
00:23:33,400 --> 00:23:36,160
je velký O n žurnál n krát.

594
00:23:36,160 --> 00:23:39,160
To znamená, že tam je nějaký aspekt tohoto
Algoritmus, který má n kroků, ale

595
00:23:39,160 --> 00:23:43,110
je tu další aspekt, někde
že iterace, že smyčky, že

596
00:23:43,110 --> 00:23:44,410
trvá log n kroků.

597
00:23:44,410 --> 00:23:49,154
Může dáme prst na to, co ti
dvě čísla jsou na mysli?

598
00:23:49,154 --> 00:23:51,320
No, kde -

599
00:23:51,320 --> 00:23:54,160
Kde mic jít?

600
00:23:54,160 --> 00:23:58,660
>> Reproduktor 1: Mělo by log n je
lámání nás do dvou -

601
00:23:58,660 --> 00:23:59,630
dělení dvěma, v podstatě.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Přesně tak.

603
00:24:00,120 --> 00:24:03,000
Kdykoliv vidíme v každém algoritmu tedy
Zatím tam byl tento vzor

604
00:24:03,000 --> 00:24:04,200
dělení, dělení, dělení.

605
00:24:04,200 --> 00:24:05,700
A je to typicky snížen
na něco, co je

606
00:24:05,700 --> 00:24:07,100
logaritmická, log základ 2.

607
00:24:07,100 --> 00:24:10,180
Ale mohlo by to být opravdu cokoliv,
ale přihlásit základ 2.

608
00:24:10,180 --> 00:24:11,330
>> Teď, co o n?

609
00:24:11,330 --> 00:24:14,550
Vidím, že jsme trochu rozdělit vás
kluci - dělí vás dělí vás,

610
00:24:14,550 --> 00:24:15,910
dělí vás dělí vás.

611
00:24:15,910 --> 00:24:18,760
Kde se konec pochází?

612
00:24:18,760 --> 00:24:19,810
>> Takže je to sloučení.

613
00:24:19,810 --> 00:24:20,610
Protože o tom přemýšlet.

614
00:24:20,610 --> 00:24:25,420
Při sloučení osm lidí dohromady,
přičemž polovina z nich je sada čtyř

615
00:24:25,420 --> 00:24:27,770
a druhá polovina jsou další
sada čtyř, jak se vám jít

616
00:24:27,770 --> 00:24:28,820
o tom sloučení?

617
00:24:28,820 --> 00:24:30,830
No, vy jste to udělal
poměrně intuitivně.

618
00:24:30,830 --> 00:24:34,140
>> Ale kdybych to dělal místo toho trochu víc
metodicky, možná jsem již uvedl v

619
00:24:34,140 --> 00:24:38,090
vlevo osoba nejprve po mé levici
ruku, ukázal na levém osoby

620
00:24:38,090 --> 00:24:42,080
této poloviny se mé pravici, a
jen následně prošel

621
00:24:42,080 --> 00:24:46,990
Seznam a ukázal na nejmenší prvek
pokaždé, pohybující se přes můj prst a

622
00:24:46,990 --> 00:24:48,970
více než v případě potřeby v celém seznamu.

623
00:24:48,970 --> 00:24:51,890
Ale co je klíčové o tomto sloučení
proces jsem porovnání těchto párů

624
00:24:51,890 --> 00:24:53,460
prvků.

625
00:24:53,460 --> 00:24:57,270
Z pravé poloviny a zleva
poloviny, jsem ani jednou couvat.

626
00:24:57,270 --> 00:25:00,570
>> Takže sloučení sám je při
ne více než n kroků.

627
00:25:00,570 --> 00:25:03,250
A kolikrát to mám
k tomu, že sloučení?

628
00:25:03,250 --> 00:25:07,150
No, ne více než n, a my jsme
viděl, že s konečnou sloučení.

629
00:25:07,150 --> 00:25:13,120
A tak, pokud děláte něco, co trvá
log n kroků n-krát, nebo naopak,

630
00:25:13,120 --> 00:25:15,210
to nám dá n log n krát.

631
00:25:15,210 --> 00:25:16,310
>> A proč je to lepší?

632
00:25:16,310 --> 00:25:19,600
No, když už víme, že protokol
n je lepší než n - P?

633
00:25:19,600 --> 00:25:22,590
Viděli jsme v binárním vyhledávání v telefonním seznamu
Například log n rozhodně

634
00:25:22,590 --> 00:25:23,760
lepší než lineární.

635
00:25:23,760 --> 00:25:28,420
Tak, že znamená, že n-krát log n je
rozhodně lepší než n krát jiný

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

637
00:25:30,390 --> 00:25:32,400
A to je to, co jsme nakonec pocit.

638
00:25:32,400 --> 00:25:34,928
>> Tak velký potlesk, když
Mohli bychom tyto lidi.

639
00:25:34,928 --> 00:25:38,920
>> [APPLAUSE]

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: A vaše rozloučení dárky -
můžete držet čísla,

641
00:25:41,550 --> 00:25:44,010
pokud byste chtěli.

642
00:25:44,010 --> 00:25:45,620
A váš dar na rozloučenou, jako obvykle.

643
00:25:45,620 --> 00:25:47,290
Jo, a my vám rádi zašleme
záběry, Michelle.

644
00:25:47,290 --> 00:25:48,343
Děkuju.

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

646
00:25:49,250 --> 00:25:50,400
Poslužte stresu míč.

647
00:25:50,400 --> 00:25:54,110
>> A dovolte mi vytáhnout, do té doby,
náš přítel Rob Bowden nabídnout

648
00:25:54,110 --> 00:25:59,520
poněkud odlišný pohled na to,
protože si můžete myslet o těchto

649
00:25:59,520 --> 00:26:01,280
kroky se dějí v poněkud
odlišným způsobem.

650
00:26:01,280 --> 00:26:04,750
Ve skutečnosti, set-up, co Rob je asi
aby nám ukázal, předpokládá, že máme

651
00:26:04,750 --> 00:26:09,030
již provádí dělení na
velký seznam do osmi menších seznamů,

652
00:26:09,030 --> 00:26:10,570
každý z velikosti 1.

653
00:26:10,570 --> 00:26:13,350
>> Takže Měníme pseudokódu
trochu, jen aby nějak dostat

654
00:26:13,350 --> 00:26:15,320
Základní myšlenkou, jak se sloučení práce.

655
00:26:15,320 --> 00:26:17,600
Ale doba chodu co
se chystá udělat, je stále

656
00:26:17,600 --> 00:26:19,110
bude stejná.

657
00:26:19,110 --> 00:26:23,540
A opět, set-up je, že je
začala s osmi seznamů velikosti 1.

658
00:26:23,540 --> 00:26:27,730
Takže jste vynechal tu část, kde je to
vlastně udělal log n, log n log n,

659
00:26:27,730 --> 00:26:31,205
dělení vstupu.

660
00:26:31,205 --> 00:26:32,120
>> [PŘEHRÁVÁNÍ]

661
00:26:32,120 --> 00:26:33,615
>> -A je to pro krok jedna.

662
00:26:33,615 --> 00:26:38,270
Na druhém kroku, a to opakovaně
spojí dva seznamy.

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

664
00:26:39,210 --> 00:26:41,270
Pouze zvuk přichází
z mého počítače.

665
00:26:41,270 --> 00:26:42,520
Zkusme to znovu.

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

667
00:26:45,330 --> 00:26:48,310
>> -Jen libovolně vybrat, které -
Nyní máme čtyři seznamy.

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

669
00:26:51,590 --> 00:26:52,120
Naučte předtím.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Tak jdeme.

671
00:26:53,040 --> 00:27:00,510
>> Sloučení-108 a 15, jsme se nakonec
s seznam 15, 108.

672
00:27:00,510 --> 00:27:07,170
Sloučení 50 a 4, se
skončit s 4, 50.

673
00:27:07,170 --> 00:27:12,990
Sloučení 8 a 42, se
skončit s 8, 42.

674
00:27:12,990 --> 00:27:19,970
A sloučení 23 a 16, se
skončit s 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Nyní jsou všechny naše seznamy jsou o velikosti 2.

676
00:27:23,270 --> 00:27:26,690
Všimněte si, že každý z
čtyři seznamy se třídí.

677
00:27:26,690 --> 00:27:29,450
Takže můžeme začít sloučení
páry opět kompletní seznam.

678
00:27:29,450 --> 00:27:38,420
Sloučení 15 a 108 a 4 a 50, se
první se na 4, pak 15, pak

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

680
00:27:41,500 --> 00:27:50,610
Sloučení 8, 42 a 16, 23, nejprve se
8, pak 16, pak 23,

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

682
00:27:52,700 --> 00:27:57,600
>> Takže teď máme jen dva seznamy velikosti
4, z nichž každý je tříděn.

683
00:27:57,600 --> 00:28:01,170
Takže teď jsme sloučit tyto dva seznamy.

684
00:28:01,170 --> 00:28:11,835
Nejprve vezmeme 4, pak se
8, pak budeme mít 15, pak 16, pak

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

686
00:28:19,456 --> 00:28:19,872
>> [END PŘEHRÁVÁNÍ]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Opět, oznámení, nikdy
dotkl dané šálek více než jednou

688
00:28:23,430 --> 00:28:24,860
po postupuje za ní.

689
00:28:24,860 --> 00:28:26,200
Takže nikdy opakovat.

690
00:28:26,200 --> 00:28:29,850
Takže je vždy v pohybu do strany,
a to je, kde jsme dostali náš n.

691
00:28:29,850 --> 00:28:33,290
>> Proč ne, dejte mi vytáhnout jednu animaci
které jsme viděli dříve, ale tentokrát

692
00:28:33,290 --> 00:28:35,110
zaměřuje pouze na druhu korespondence.

693
00:28:35,110 --> 00:28:38,030
Nech mě jít dopředu a zoom
do toho tady.

694
00:28:38,030 --> 00:28:42,530
Nejprve mi dovolte, abych si vybrat náhodný vstup,
zvětšit to, a můžete nějak vidět

695
00:28:42,530 --> 00:28:46,600
to, co jsme považovali za samozřejmé, dříve,
sloučit druh skutečně dělá.

696
00:28:46,600 --> 00:28:50,330
>> Tak zjistíte, že vám tyto poloviny nebo
Tyto čtvrtí nebo ty osminy

697
00:28:50,330 --> 00:28:53,140
problém, který se z ničeho nic
začnou mít dobrou formu.

698
00:28:53,140 --> 00:28:57,070
A nakonec, uvidíte na
velmi konec, který bam,

699
00:28:57,070 --> 00:28:58,860
vše je spojil.

700
00:28:58,860 --> 00:29:01,690
>> Tak to jsou jen tři různé
se na stejnou myšlenku.

701
00:29:01,690 --> 00:29:05,980
Ale hlavní pohled, stejně jako rozdělení
a podmanit si hned v první třídě,

702
00:29:05,980 --> 00:29:10,640
bylo to, že jsme se rozhodli nějak rozdělit
problém do něčeho velkého, do

703
00:29:10,640 --> 00:29:14,760
něco trochu identické v duchu,
ale menší a menší a menší

704
00:29:14,760 --> 00:29:15,660
a menší.

705
00:29:15,660 --> 00:29:18,420
>> Nyní další zábavný způsob, jak nějak myslet
o nich, i když to není

706
00:29:18,420 --> 00:29:20,520
bude vám stejně intuitivní
porozumění, je

707
00:29:20,520 --> 00:29:21,640
Následující animace.

708
00:29:21,640 --> 00:29:25,400
Tak tohle je video někdo dát dohromady
jaké jsou spojeny různé

709
00:29:25,400 --> 00:29:29,970
zvuků s různými operacemi
vložení druhu, pro druh korespondence a

710
00:29:29,970 --> 00:29:31,150
na pár dalších.

711
00:29:31,150 --> 00:29:32,330
Takže ve chvíli, jdu zasáhnout Play.

712
00:29:32,330 --> 00:29:33,600
Je to asi minutu dlouhý.

713
00:29:33,600 --> 00:29:37,410
A i když stále můžete vidět
vzory děje, tentokrát si můžete

714
00:29:37,410 --> 00:29:41,420
také slyšet, jak tyto algoritmy jsou
provádění odlišně a s

715
00:29:41,420 --> 00:29:43,950
poněkud různé vzory.

716
00:29:43,950 --> 00:29:45,830
>> To je druh vložení.

717
00:29:45,830 --> 00:29:50,400
>> [TÓNY PŘEHRÁVÁNÍ]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Opět se snaží
vložit každý prvek

719
00:29:52,400 --> 00:29:52,900
na tam, kam patří.

720
00:29:52,900 --> 00:29:54,628
To je bublina druh.

721
00:29:54,628 --> 00:30:10,097
>> [TÓNY PŘEHRÁVÁNÍ]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: A můžete tak nějak pocit
jak relativně málo práce to dělá

723
00:30:13,630 --> 00:30:15,834
na každém kroku.

724
00:30:15,834 --> 00:30:20,470
To je to, co zní jako nudnost.

725
00:30:20,470 --> 00:30:21,472
>> [TÓNY PŘEHRÁVÁNÍ]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Toto je výběr druhu,
kde vyberte element, který chceme do

727
00:30:25,222 --> 00:30:28,845
prochází znovu a znovu a znovu
a uvedení na začátku.

728
00:30:28,845 --> 00:30:37,674
>> [TÓNY PŘEHRÁVÁNÍ]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Toto je sloučit druh, který
můžete opravdu začít cítit.

730
00:30:43,970 --> 00:30:51,810
>> [TÓNY PŘEHRÁVÁNÍ]

731
00:30:51,810 --> 00:30:54,770
>> [Smích]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Něco s názvem gnome
třídění, které jsme se podíval na.

733
00:30:58,395 --> 00:31:13,630
>> [TÓNY PŘEHRÁVÁNÍ]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Tak se ukažte, teď,
roztržitý, jak jste snad jsou ve

735
00:31:17,910 --> 00:31:21,110
hudba, jestli můžu sklouznout trochu
Trocha matematiky zde.

736
00:31:21,110 --> 00:31:24,850
Takže tam je čtvrtý způsob, který můžeme
přemýšlet o tom, co to znamená, že tyto

737
00:31:24,850 --> 00:31:29,210
funkcí, které jsou rychlejší než ty
že jsme neviděli.

738
00:31:29,210 --> 00:31:32,470
A pokud jedete na kurzu od
matematika pozadí, můžete

739
00:31:32,470 --> 00:31:36,030
vlastně víte, možná už, že jste
může plácnout termín na této technice -

740
00:31:36,030 --> 00:31:40,400
to rekurze, funkce
že tak nějak volá sama sebe.

741
00:31:40,400 --> 00:31:44,780
>> A opět připomenout, že druh korespondence
pseudokódu byl rekurzivní v tom smyslu,

742
00:31:44,780 --> 00:31:48,460
že jeden z Merge sort v krocích
nazval druh -

743
00:31:48,460 --> 00:31:49,740
to znamená, že sama o sobě.

744
00:31:49,740 --> 00:31:52,480
Ale naštěstí, protože jsme si nechali
volání třídit, nebo sloučit druh,

745
00:31:52,480 --> 00:31:55,880
specificky, na menší a menší
a menší seznam, nakonec jsme

746
00:31:55,880 --> 00:32:00,005
dna díky, co budeme nazývat
referenční případ, pevně platí, že

747
00:32:00,005 --> 00:32:04,270
řekl, že pokud je seznam je malý, menší než 2
V takovém případě si okamžitě vrátí.

748
00:32:04,270 --> 00:32:07,550
Pokud bychom neměli mít tento zvláštní případ,
Algoritmus by nikdy dna,

749
00:32:07,550 --> 00:32:11,010
a vy byste opravdu dostat do
nekonečná smyčka opravdu navždy.

750
00:32:11,010 --> 00:32:14,330
>> Ale předpokládejme, že jsme chtěli, aby se dal
některá čísla na to, opět za použití n

751
00:32:14,330 --> 00:32:15,660
jako velikost vstupu.

752
00:32:15,660 --> 00:32:18,680
A chtěl jsem se vás zeptat, co je
celkový čas účastní

753
00:32:18,680 --> 00:32:19,800
spuštění hromadné korespondence druh?

754
00:32:19,800 --> 00:32:22,960
Nebo obecněji, co je
náklady na něj v čase?

755
00:32:22,960 --> 00:32:24,730
>> No, je to docela snadné změřit to.

756
00:32:24,730 --> 00:32:29,010
Jestliže je n menší než 2, času potřebného pro
v třídění n prvků,

757
00:32:29,010 --> 00:32:30,480
kde n je 2, je 0.

758
00:32:30,480 --> 00:32:31,410
Protože jsme prostě vrátit.

759
00:32:31,410 --> 00:32:32,510
Neexistuje žádná práce je třeba udělat.

760
00:32:32,510 --> 00:32:35,660
Nyní pravděpodobně, možná je to jeden krok nebo dva
kroky, aby zjistili množství

761
00:32:35,660 --> 00:32:38,420
práce, ale je to dost blízko 0, že
Jen jsem chtěl říct, ne práce

762
00:32:38,420 --> 00:32:40,940
vyžaduje-li seznam je tak malý,
být nezajímavé.

763
00:32:40,940 --> 00:32:42,580
>> Ale v tomto případě je zajímavé.

764
00:32:42,580 --> 00:32:47,320
Rekurzivní případ byl obor
pseudokódu, který řekl jinde, třídění

765
00:32:47,320 --> 00:32:52,000
levá polovina, třídit právo
poloviny, sloučit dvě poloviny.

766
00:32:52,000 --> 00:32:55,530
A teď, proč se tento výraz
představují, že náklady?

767
00:32:55,530 --> 00:32:58,690
No, T n jen znamená,
Doba třídit n prvků.

768
00:32:58,690 --> 00:33:03,070
A pak na pravé straně
rovnítko tam, T n dělí

769
00:33:03,070 --> 00:33:06,600
o 2 odkazuje na cenu co?

770
00:33:06,600 --> 00:33:07,570
Řazení levou polovinu.

771
00:33:07,570 --> 00:33:10,990
Druhý T n děleno 2 je
pravděpodobně se odkazovat na náklady

772
00:33:10,990 --> 00:33:12,390
seřadit pravou polovinu.

773
00:33:12,390 --> 00:33:14,590
>> A pak n a?

774
00:33:14,590 --> 00:33:15,420
Je sloučení.

775
00:33:15,420 --> 00:33:19,120
Vzhledem k tomu, máte-li dva seznamy, jeden z
velikosti n na 2 a další velikosti n

776
00:33:19,120 --> 00:33:22,580
více než 2, máte v podstatě dotýkat
každý z těchto prvků, stejně jako Rob

777
00:33:22,580 --> 00:33:24,990
dotkl každého z košíčků, a jen
jak jsme upozornili na každé

778
00:33:24,990 --> 00:33:26,310
Dobrovolníci na jevišti.

779
00:33:26,310 --> 00:33:28,790
Tak n je náklad sloučení.

780
00:33:28,790 --> 00:33:31,780
>> Teď bohužel, tento vzorec
je také sám rekurzivní.

781
00:33:31,780 --> 00:33:36,390
Takže pokud se ptal, je-li n je, řekněme,
16, v případě, že je 16 lidí na jevišti

782
00:33:36,390 --> 00:33:40,670
nebo 16 šálků na video, kolik celkem
kroky je potřeba, aby třídit

783
00:33:40,670 --> 00:33:41,550
Pomocí Seřadit korespondence?

784
00:33:41,550 --> 00:33:45,790
Je to vlastně není jasná odpověď,
protože teď budete muset nějak

785
00:33:45,790 --> 00:33:48,500
rekurzivně odpovědět na tento vzorec.

786
00:33:48,500 --> 00:33:51,190
>> Ale to je v pořádku, protože mi dovolte navrhnout,
co děláme následující.

787
00:33:51,190 --> 00:33:56,670
Času potřebného pro třídění nebo 16 lidí
16 šálků se bude zastoupen

788
00:33:56,670 --> 00:33:58,020
obecně jako T ze dne 16..

789
00:33:58,020 --> 00:34:01,400
Ale to se rovná, podle našich
předchozí vzorec, 2 násobek částky

790
00:34:01,400 --> 00:34:04,780
čas potřebný k řazení
8 šálků plus 16.

791
00:34:04,780 --> 00:34:08,590
A opět, a 16 je čas spojit,
a dvakrát T ze dne 8. je

792
00:34:08,590 --> 00:34:10,790
Doba třídit levou polovinu a pravé poloviny.

793
00:34:10,790 --> 00:34:11,989
>> Ale znovu, to nestačí.

794
00:34:11,989 --> 00:34:13,210
Musíme se do toho ponořit hlouběji.

795
00:34:13,210 --> 00:34:16,409
To znamená, že musíme odpovědět
otázka, co je t 8?

796
00:34:16,409 --> 00:34:19,610
No T z 8 se nachází jen 2
Časy T z 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
No, co se t 4?

798
00:34:20,520 --> 00:34:23,780
T 4 je jen 2 krát T z 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
No, co je t 2?

800
00:34:25,489 --> 00:34:29,030
T 2 je jen 2 krát T z 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> A opět jsme trochu dostat
uvízl v tomto cyklu.

802
00:34:31,940 --> 00:34:34,790
Ale je to o tom, že zasáhnout
tzv. referenční případ.

803
00:34:34,790 --> 00:34:37,310
Protože to, co je t 1, jsme se tvrdí?

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

805
00:34:37,810 --> 00:34:39,730
Takže teď konečně můžeme pracovat pozpátku.

806
00:34:39,730 --> 00:34:44,290
>> Je-li T 1 je 0, teď mohu vrátit do jednoho
linky na toho chlapa tady, a mohu

807
00:34:44,290 --> 00:34:46,330
zapojte 0 pro T z 1..

808
00:34:46,330 --> 00:34:51,770
Takže to znamená, že se rovná 2 krát nula,
jinak známý jako 0, + 2.

809
00:34:51,770 --> 00:34:53,739
A tak, že celý výraz je 2..

810
00:34:53,739 --> 00:34:58,740
>> Teď, když jsem si na T 2, jejichž odpověď
je 2, zapojte jej do prostřední řady, T

811
00:34:58,740 --> 00:35:02,740
ze dne 4., že mi dává 2 krát
2 a 4, tak 8..

812
00:35:02,740 --> 00:35:07,080
Když jsem pak připojíte 8 na předchozí
linka, která mi dává 2 krát 8, 16.

813
00:35:07,080 --> 00:35:12,470
A pokud budeme pokračovat, že se
24, tím, že do 16 let, se konečně dostat

814
00:35:12,470 --> 00:35:13,820
hodnota 64.

815
00:35:13,820 --> 00:35:18,480
>> Teď, když sám o sobě trochu mluví
nic k zápisu n,

816
00:35:18,480 --> 00:35:20,700
velký O, omega, že máme
o tom mluvili.

817
00:35:20,700 --> 00:35:24,890
Ale ukazuje se, že 64 je opravdu
16, velikost vstupu,

818
00:35:24,890 --> 00:35:27,110
přihlásit základnu 2 16 let.

819
00:35:27,110 --> 00:35:30,200
A pokud je to trochu neznámá, stejně
vzpomínat, a to vrátím

820
00:35:30,200 --> 00:35:30,700
vám nakonec.

821
00:35:30,700 --> 00:35:33,775
Pokud je to log základ 2, je to jako 2
zvýšil na to, co vám dává 16?

822
00:35:33,775 --> 00:35:36,380
Oh, to je 4, takže je to 16 krát 4.

823
00:35:36,380 --> 00:35:39,380
>> A opět, není to velký problém, pokud to
je trochu mlhavé paměti teď.

824
00:35:39,380 --> 00:35:43,720
Ale teď, se na základě víry
že 16 protokolu 16 je 64.

825
00:35:43,720 --> 00:35:46,590
A tak se skutečně s tímto jednoduchým zdravého rozumu
Zkontrolujte, jsme potvrzena -

826
00:35:46,590 --> 00:35:48,250
ale ukázalo formálně -

827
00:35:48,250 --> 00:35:52,800
že doba chodu sloučení
Třídění je opravdu n log n.

828
00:35:52,800 --> 00:35:53,790
>> Takže to není špatné.

829
00:35:53,790 --> 00:35:57,260
Je to určitě lepší, než
algoritmy jsme viděli doposud, a

830
00:35:57,260 --> 00:36:00,710
je to proto, že jsme zadlužuje, jedním,
techniku ​​zvanou rekurze.

831
00:36:00,710 --> 00:36:03,880
Ale zajímavější než to, že
Pojem dělení a dobývání.

832
00:36:03,880 --> 00:36:07,460
Opět platí, že opravdu věci, které týden 0
i dnes se opakující v

833
00:36:07,460 --> 00:36:08,740
přesvědčivější způsobem.

834
00:36:08,740 --> 00:36:11,750
>> Teď trochu legrace cvičení, pokud jste
nikdy nedělal - a pravděpodobně

835
00:36:11,750 --> 00:36:14,660
by neměl, protože jaksi normální
lidé si nemyslím, že to udělat.

836
00:36:14,660 --> 00:36:20,650
Ale když jdu do google.com, a pokud
Chci se dozvědět něco o

837
00:36:20,650 --> 00:36:22,356
rekurze, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Smích]

840
00:36:29,058 --> 00:36:32,030
[Další smích]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Bad joke pomalu šíří.

842
00:36:33,385 --> 00:36:34,450
[Smích]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Jen v případě, že tam je.

844
00:36:36,970 --> 00:36:38,710
Nechtěl jsem to špatně píše,
a tam je ten vtip.

845
00:36:38,710 --> 00:36:40,810
Dobrá.

846
00:36:40,810 --> 00:36:42,950
Vysvětlete lidem vedle vás, jestli
to není zcela kliknul jen zatím.

847
00:36:42,950 --> 00:36:47,650
Ale rekurze, obecně se odkazuje
do procesu a volání funkcí

848
00:36:47,650 --> 00:36:51,430
sama o sobě, nebo obecněji, dělení
problém do něčeho, co může být

849
00:36:51,430 --> 00:36:56,220
řeší po částech při řešení shodné
reprezentativní problémy.

850
00:36:56,220 --> 00:36:58,400
>> Dobře, pojďme přeřadit
jen na chvíli.

851
00:36:58,400 --> 00:37:00,840
Rádi bychom skončit na určitých cliffhangers,
takže pojďme začít s nastavením

852
00:37:00,840 --> 00:37:05,870
fázi, po dobu několika minut,
na velmi jednoduchém nápadu -

853
00:37:05,870 --> 00:37:07,620
to prohození dvou prvků, ne?

854
00:37:07,620 --> 00:37:10,040
Všechny tyto algoritmy jsme byli
mluví o posledních pár

855
00:37:10,040 --> 00:37:12,420
Přednášky zahrnují některé
druh vyměňovat.

856
00:37:12,420 --> 00:37:14,630
Dnes to bylo vizualizovat jejich získávání
se ze svých židlí a

857
00:37:14,630 --> 00:37:18,570
chodí, ale v kódu, bychom
jen se prvek z jednoho pole

858
00:37:18,570 --> 00:37:20,370
a plop to do druhého.

859
00:37:20,370 --> 00:37:21,880
>> Tak jak jsme se jít asi dělá?

860
00:37:21,880 --> 00:37:24,850
No, dovolte mi jít dál a psát
rychlý program zde.

861
00:37:24,850 --> 00:37:31,600
Chystám se jít dál a dělat
to je například následující.

862
00:37:31,600 --> 00:37:33,910
Řekněme to -

863
00:37:33,910 --> 00:37:38,070
Co chceme volat tohle?

864
00:37:38,070 --> 00:37:38,650
>> Ve skutečnosti, no.

865
00:37:38,650 --> 00:37:39,420
Nech mě dozadu.

866
00:37:39,420 --> 00:37:41,220
Nechci k tomu, že
cliffhanger ještě.

867
00:37:41,220 --> 00:37:42,270
To bude kazit zábavu.

868
00:37:42,270 --> 00:37:43,600
Pojďme na to místo.

869
00:37:43,600 --> 00:37:47,430
>> Dejme tomu, že chci napsat něco
program, a nyní zahrnuje tento

870
00:37:47,430 --> 00:37:48,700
Myšlenka rekurze.

871
00:37:48,700 --> 00:37:50,370
Tak nějak jsem se dostal před sebe tam.

872
00:37:50,370 --> 00:37:51,420
Chystám se provést následující kroky.

873
00:37:51,420 --> 00:38:00,220
>> Za prvé, je rychlý standardní io.h,
stejně jako patří v cs50.h.

874
00:38:00,220 --> 00:38:03,200
A pak budu pokračovat
a prohlásit za neplatné int main

875
00:38:03,200 --> 00:38:04,360
obvyklým způsobem.

876
00:38:04,360 --> 00:38:07,920
Uvědomil jsem si, jsem nesprávně pojmenovaný soubor, takže
dovolte mi přidat. c příponu, takže zde

877
00:38:07,920 --> 00:38:09,510
že můžeme sestavit správně.

878
00:38:09,510 --> 00:38:10,970
Spusťte tuto funkci vypnout.

879
00:38:10,970 --> 00:38:13,290
>> A funkce chci napsat, docela
Jednoduše řečeno, je ten, který žádá

880
00:38:13,290 --> 00:38:16,210
uživatel pro číslo a pak sečte
všechna čísla, která mezi

881
00:38:16,210 --> 00:38:19,920
číslo a, řekněme, 0.

882
00:38:19,920 --> 00:38:22,510
Takže v první řadě budu pokračovat
a prohlašují, int n.

883
00:38:22,510 --> 00:38:24,760
Pak jsem zkopírovat nějaký kód, který
jsme použili na chvíli.

884
00:38:24,760 --> 00:38:26,660
I když je něco pravda.

885
00:38:26,660 --> 00:38:28,000
Vrátím se k tomu za chvíli.

886
00:38:28,000 --> 00:38:29,010
>> Co chci dělat?

887
00:38:29,010 --> 00:38:33,460
Chci říci printf pozitivní
celé číslo, prosím.

888
00:38:33,460 --> 00:38:36,130
A pak budu
říci, n dostane se int.

889
00:38:36,130 --> 00:38:38,800
Takže znovu, někteří standardizovaný kód
že jsme použili předtím.

890
00:38:38,800 --> 00:38:40,810
A já jdu na to
když n je menší než 1.

891
00:38:40,810 --> 00:38:44,120
Takže to bude zajistit, že uživatel
mi dává kladné celé číslo.

892
00:38:44,120 --> 00:38:45,490
>> A teď budu dělat následující.

893
00:38:45,490 --> 00:38:51,020
Chci se sečíst všechna čísla
mezi 1 a a n, nebo 0 a n,

894
00:38:51,020 --> 00:38:52,570
ekvivalentně, aby celkový součet.

895
00:38:52,570 --> 00:38:55,100
Takže velká sigma symbol
které by vás mohly vyvolat.

896
00:38:55,100 --> 00:38:59,050
Takže budu dělat, tím prvním volání
volána funkce sigma,

897
00:38:59,050 --> 00:39:06,030
procházet skrz n, a pak budu
říkají printf, odpověď je tady.

898
00:39:06,030 --> 00:39:08,180
>> Takže ve zkratce, jsem si a
int od uživatele.

899
00:39:08,180 --> 00:39:09,280
Já se zajistilo, že je to pozitivní.

900
00:39:09,280 --> 00:39:12,700
Prohlašuji proměnnou s názvem odpověď
typ int a uložit v něm návrat

901
00:39:12,700 --> 00:39:15,610
hodnota sigma, předáním n jako vstup.

902
00:39:15,610 --> 00:39:17,060
A pak jsem vytisknout tuto odpověď.

903
00:39:17,060 --> 00:39:19,550
>> Bohužel, i když zní sigma
jako něco, co by mohlo být v

904
00:39:19,550 --> 00:39:24,040
math.h souboru, jeho prohlášení,
je to ve skutečnosti není.

905
00:39:24,040 --> 00:39:24,690
Tak to je v pořádku.

906
00:39:24,690 --> 00:39:26,170
Mohu provedení tohoto sám.

907
00:39:26,170 --> 00:39:29,160
Chystám se realizovat názvem funkce
sigma, a že to bude trvat

908
00:39:29,160 --> 00:39:29,900
parametr -

909
00:39:29,900 --> 00:39:32,100
Řekněme, že m, jen
tak to je něco jiného.

910
00:39:32,100 --> 00:39:35,910
A pak tady, budu říkat,
a, je-li m je menší než 1 - jedná se o

911
00:39:35,910 --> 00:39:38,180
velmi nezajímavý program.

912
00:39:38,180 --> 00:39:41,700
Takže budu pokračovat a
neprodleně vrátit 0.

913
00:39:41,700 --> 00:39:45,920
To prostě nedává smysl sečíst všechny
čísla mezi 1 a M, jestliže m

914
00:39:45,920 --> 00:39:48,470
je sám o sobě 0 nebo negativní.

915
00:39:48,470 --> 00:39:50,900
>> A pak budu pokračovat
a to velmi iterativně.

916
00:39:50,900 --> 00:39:53,090
Chystám se dělat takovéhle staré školy,
a já jdu do toho

917
00:39:53,090 --> 00:39:57,150
a říkají, že budu
deklarovat částku za 0.

918
00:39:57,150 --> 00:39:59,630
Pak budu mít
pro smyčce int -

919
00:39:59,630 --> 00:40:02,820
a nech mě to udělat tak, aby odpovídala Our
distribuce kód, takže máte kopii

920
00:40:02,820 --> 00:40:07,500
doma. int i dostane až na 1
i je menší než nebo rovna m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
A pak uvnitř tohoto cyklu for -

923
00:40:11,430 --> 00:40:12,440
Už jsme skoro tam -

924
00:40:12,440 --> 00:40:15,810
Součet dostane částku plus 1.

925
00:40:15,810 --> 00:40:17,670
A pak jdu vrátit částku.

926
00:40:17,670 --> 00:40:19,420
>> Tak jsem to udělal tak rychle,
docela pravda.

927
00:40:19,420 --> 00:40:22,775
Ale znovu, jehož hlavní funkcí je dost
jednoduchý, založený na kódu jsme

928
00:40:22,775 --> 00:40:23,190
napsal tak daleko.

929
00:40:23,190 --> 00:40:25,610
Používá dvojí smyčku, aby se pozitivní
int od uživatele.

930
00:40:25,610 --> 00:40:29,870
Pak jsem se projít, že int do nové funkce
tzv. sigma, volat to opět n.

931
00:40:29,870 --> 00:40:33,100
A já uložit návratovou hodnotu, odpověď
z černé skříňky v současné době

932
00:40:33,100 --> 00:40:35,460
známý jako Sigma, v proměnné
volal odpověď.

933
00:40:35,460 --> 00:40:36,580
Pak jsem vytisknout.

934
00:40:36,580 --> 00:40:39,090
>> Pokud bychom nyní pokračovat v příběhu,
jak je sigma realizován?

935
00:40:39,090 --> 00:40:40,840
Navrhuji provést takto.

936
00:40:40,840 --> 00:40:43,560
Nejprve trochu kontroly chyb
aby se ujistil, že uživatel není

937
00:40:43,560 --> 00:40:46,480
probírat se mnou a předáním
některé negativní nebo hodnota 0.

938
00:40:46,480 --> 00:40:49,710
Pak jsem deklarovat proměnnou s názvem
shrnout a nastavte ji na hodnotu 0..

939
00:40:49,710 --> 00:40:55,910
>> A teď se začne pohybovat i ze rovná
1 celou cestu až do m,

940
00:40:55,910 --> 00:41:00,130
protože chci, aby zahrnovala všechny
čísla od jedničky do m včetně.

941
00:41:00,130 --> 00:41:04,350
A uvnitř tohoto cyklu for, jsem prostě
Součet dostane, co je nyní, a

942
00:41:04,350 --> 00:41:08,900
hodnota i.

943
00:41:08,900 --> 00:41:10,370
Navíc hodnota i.

944
00:41:10,370 --> 00:41:14,090
>> Mimochodem, pokud jste to ještě neviděli
dříve, je tu nějaký syntaktický cukr

945
00:41:14,090 --> 00:41:14,870
pro tuto linku.

946
00:41:14,870 --> 00:41:21,120
Mohu přepsat jako a rovná i,
jen zachránit sebe několik klávesových zkratek

947
00:41:21,120 --> 00:41:22,570
a podívat se trochu chladnější.

948
00:41:22,570 --> 00:41:23,140
Ale to je všechno.

949
00:41:23,140 --> 00:41:24,660
Je to funkčně totéž.

950
00:41:24,660 --> 00:41:26,710
>> Bohužel, tento kód je
nebude kompilovat ještě.

951
00:41:26,710 --> 00:41:31,600
Když jsem běžet, aby sigma 0, jak pm
Budu se dostat křičel na?

952
00:41:31,600 --> 00:41:33,473
Jaké to bude nelíbí?

953
00:41:33,473 --> 00:41:35,740
>> DIVÁKŮ: [neslyšitelné].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Jo, já nepřiznal
funkce až nahoře, vpravo?

955
00:41:37,800 --> 00:41:40,590
C je tak trochu blbost, v tom, že pouze
dělá to, co řeknete to udělat, a vy

956
00:41:40,590 --> 00:41:41,880
musíte udělat to v tomto pořadí.

957
00:41:41,880 --> 00:41:45,910
A tak když jsem stiskněte klávesu Enter tady, jdu
dostat varování o sigma implicitní

958
00:41:45,910 --> 00:41:46,860
prohlášení.

959
00:41:46,860 --> 00:41:48,120
>> Oh, není problém.

960
00:41:48,120 --> 00:41:50,370
Můžu jít až na vrchol, a mohu
říkají, dobře, počkej.

961
00:41:50,370 --> 00:41:54,240
Sigma je funkce, která vrací
int a očekává, že

962
00:41:54,240 --> 00:41:56,620
int jako vstup, středníkem.

963
00:41:56,620 --> 00:41:59,550
Nebo bych mohl dát celou funkci
nad hlavní, ale obecně, tak bych

964
00:41:59,550 --> 00:42:02,260
nedoporučujeme, protože to je
hezké vždy hlavní horem, aby se

965
00:42:02,260 --> 00:42:06,310
můžete ponořit přímo a vím, co
Program dělá čtením hlavní nejdříve.

966
00:42:06,310 --> 00:42:07,930
>> Takže teď mi dovolte vyčistit obrazovku.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Vše vypadá, že check-out.

969
00:42:10,340 --> 00:42:11,970
Dovolte mi spustit sigma 0.

970
00:42:11,970 --> 00:42:12,770
Pozitivní inter.

971
00:42:12,770 --> 00:42:15,580
Dám to číslo
3, aby to jednoduché.

972
00:42:15,580 --> 00:42:18,710
Tak, že by mi 3
plus 2 plus 1, tak 6.

973
00:42:18,710 --> 00:42:20,750
Zadejte, a opravdu jsem si 6.

974
00:42:20,750 --> 00:42:21,820
>> Můžu udělat něco většího -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Stejně jako tečnu, budu dělat
něco směšné jako opravdu velký

977
00:42:27,690 --> 00:42:30,375
číslo, Oh, to skutečně dopadlo -

978
00:42:30,375 --> 00:42:31,600
eh, já si nemyslím, že je to pravda.

979
00:42:31,600 --> 00:42:32,810
Pojďme se podívat.

980
00:42:32,810 --> 00:42:34,060
Pojďme opravdu si s ním.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> To je problém.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Co se děje?

985
00:42:44,970 --> 00:42:46,050
Kód Není to tak zlé.

986
00:42:46,050 --> 00:42:48,470
Je to stále lineární.

987
00:42:48,470 --> 00:42:50,810
Pískání je dobrý účinek, ačkoli.

988
00:42:50,810 --> 00:42:52,060
Co se děje?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Není si jistý, jestli jsem to slyšel.

991
00:42:55,620 --> 00:42:57,620
Tak to dopadá - a
to je stranou.

992
00:42:57,620 --> 00:42:59,400
To není jádrem
Myšlenka rekurze.

993
00:42:59,400 --> 00:43:02,480
Ukazuje se, protože já se snažím
představují tak velké množství, většina

994
00:43:02,480 --> 00:43:06,980
pravděpodobně je to být mylně
o C, jako to kladné číslo,

995
00:43:06,980 --> 00:43:09,980
ale záporné číslo.

996
00:43:09,980 --> 00:43:12,690
>> Nemluvili jsme o tom, ale je to
Ukazuje se, že jsou záporná čísla

997
00:43:12,690 --> 00:43:14,210
ve světě navíc
do kladných čísel.

998
00:43:14,210 --> 00:43:16,290
A prostředky, které můžete
představují záporné číslo

999
00:43:16,290 --> 00:43:19,530
v podstatě je, že můžete použít jeden
speciální bit pro indikaci

1000
00:43:19,530 --> 00:43:20,400
pozitivní na negativní.

1001
00:43:20,400 --> 00:43:22,950
Je to trochu složitější, než to,
ale to je základní myšlenka.

1002
00:43:22,950 --> 00:43:26,740
>> Takže bohužel, pokud C je matoucí
z těchto bitů je ve skutečnosti znamená,

1003
00:43:26,740 --> 00:43:30,790
oh, to je záporné číslo, moje smyčka
Zde, například, je ve skutečnosti nikdy

1004
00:43:30,790 --> 00:43:31,740
bude ukončena.

1005
00:43:31,740 --> 00:43:33,850
Takže když jsem byl vlastně tisku něco
znovu a znovu, bychom

1006
00:43:33,850 --> 00:43:34,650
vidět spoustu.

1007
00:43:34,650 --> 00:43:36,220
Ale opět, to je vedle bodu.

1008
00:43:36,220 --> 00:43:38,590
To je opravdu jen jakýmsi
intelektuální zvídavost, že přijdeme

1009
00:43:38,590 --> 00:43:39,550
zpět nakonec.

1010
00:43:39,550 --> 00:43:43,400
Ale teď je to správné
Implementace pokud budeme předpokládat, že

1011
00:43:43,400 --> 00:43:45,970
uživatel bude poskytovat ints
které zapadají do ints.

1012
00:43:45,970 --> 00:43:49,370
>> Ale tvrdím, že tento kód, upřímně řečeno,
by se dalo udělat mnohem jednodušeji.

1013
00:43:49,370 --> 00:43:54,060
Je-li cílem po ruce, je přijmout řadu
jako m a sečíst všechny

1014
00:43:54,060 --> 00:43:59,510
čísla mezi ním a 1, nebo naopak
mezi 1 a, tvrdím,

1015
00:43:59,510 --> 00:44:03,380
že mohu půjčit myšlenku, že sloučení
druh měl, který byl s problémy

1016
00:44:03,380 --> 00:44:05,660
této velikosti a oddělujících
do něčeho menšího.

1017
00:44:05,660 --> 00:44:09,875
Možná ne polovina, ale menší, ale
reprezentativně stejné.

1018
00:44:09,875 --> 00:44:12,130
Stejný nápad, ale menší problém.

1019
00:44:12,130 --> 00:44:15,470
>> Takže jsem vlastně - dovolte mi, abych tento soubor uložit
s jiným číslem verze.

1020
00:44:15,470 --> 00:44:17,670
Zavoláme tuto verzi
1 místo 0.

1021
00:44:17,670 --> 00:44:20,790
A tvrdím, že jsem si vlastně
reimplement to v tomto druhu

1022
00:44:20,790 --> 00:44:22,160
mysl-ohýbání cesta.

1023
00:44:22,160 --> 00:44:23,710
>> Chystám se opustit jeho část samostatně.

1024
00:44:23,710 --> 00:44:27,710
Chystám se říct, jestli m je méně
než nebo se může dokonce rovnat 0 -

1025
00:44:27,710 --> 00:44:29,280
Já jen bude trochu
více anální tentokrát

1026
00:44:29,280 --> 00:44:30,520
s mou kontrolu chyb -

1027
00:44:30,520 --> 00:44:33,190
Chystám se jít dopředu a vrátí 0.

1028
00:44:33,190 --> 00:44:34,490
To je libovolná.

1029
00:44:34,490 --> 00:44:37,500
Jsem prostě rozhodne, zda uživatel
mi dává záporné číslo, já jsem

1030
00:44:37,500 --> 00:44:41,490
vrací 0, a měly by Přečetl
dokumentace podrobněji.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
Všimněte si, co budu dělat.

1033
00:44:44,070 --> 00:44:49,260
Jinak se budu vracet M plus -

1034
00:44:49,260 --> 00:44:51,010
co je sigma m?

1035
00:44:51,010 --> 00:44:56,710
No, sigma M plus M minus 1,
a m mínus 2 plus minus 3 m.

1036
00:44:56,710 --> 00:44:58,030
Nechci psát všechny ty ven.

1037
00:44:58,030 --> 00:44:59,120
Proč prostě nemůžu pramice?

1038
00:44:59,120 --> 00:45:05,080
Rekurzivně volat sám s mírně
menší problém, středník,

1039
00:45:05,080 --> 00:45:06,840
a nazývat to den?

1040
00:45:06,840 --> 00:45:07,040
>> Je to tak?

1041
00:45:07,040 --> 00:45:10,980
Teď tady taky, možná máte pocit, strach nebo
že se jedná o nekonečnou smyčku, že jsem

1042
00:45:10,980 --> 00:45:15,450
vyvolávající, kdy jsem prováděcích
sigma sigma voláním.

1043
00:45:15,450 --> 00:45:20,342
Ale to je naprosto v pořádku, protože jsem
myslel dopředu přidal které řádky?

1044
00:45:20,342 --> 00:45:22,600
>> DIVÁKŮ: [neslyšitelné].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23 až 26, které
pokud je můj stav.

1046
00:45:25,430 --> 00:45:28,390
Protože to, co je hezké o
odčítání tady, protože jsem se udržet

1047
00:45:28,390 --> 00:45:31,180
rozdávají sigma menší problémy, menší
problémy, menší - to není

1048
00:45:31,180 --> 00:45:31,870
poloviční velikosti.

1049
00:45:31,870 --> 00:45:34,380
Je to jen krůček menší,
ale to je v pořádku.

1050
00:45:34,380 --> 00:45:38,050
Protože nakonec, budeme pracovat
naše cesta dolů na hodnotu 1 nebo 0.

1051
00:45:38,050 --> 00:45:41,630
A jakmile se dostaneme 0, sigma není
zavolá sám už ne.

1052
00:45:41,630 --> 00:45:43,590
Bude to okamžitě vrátí 0.

1053
00:45:43,590 --> 00:45:47,960
>> Takže efekt, pokud jste trochu větru tento
ve vaší mysli, je přidat M plus

1054
00:45:47,960 --> 00:45:52,740
m minus 1 plus minus m 2 plus minus m
3 plus tečka, tečka, tečka, m minus

1055
00:45:52,740 --> 00:45:57,820
m, která vám nakonec 0, a
účinek je nakonec přidat všechny

1056
00:45:57,820 --> 00:45:59,070
tyto věci dohromady.

1057
00:45:59,070 --> 00:46:02,380
Takže nemáme s rekurze,
vyřešit problém, že se

1058
00:46:02,380 --> 00:46:03,470
nemůže vyřešit dříve.

1059
00:46:03,470 --> 00:46:06,840
Ve skutečnosti, verze 0 tohoto, a každý
problém k dnešnímu dni, byl řešitelný

1060
00:46:06,840 --> 00:46:09,980
jen s použitím smyčky, nebo když
smyčky nebo podobné konstrukty.

1061
00:46:09,980 --> 00:46:13,150
>> Ale rekurze, troufám si říct, nám dává
jiný způsob uvažování o

1062
00:46:13,150 --> 00:46:17,010
Problémy, kterým můžeme-li se
problém, rozdělit ji z něčeho

1063
00:46:17,010 --> 00:46:22,340
poněkud velký na něco poněkud
menší, tvrdím, že můžeme vyřešit

1064
00:46:22,340 --> 00:46:26,040
možná trochu více elegantně, pokud jde
konstrukce, s méně kódu,

1065
00:46:26,040 --> 00:46:30,980
a možná i řešit problémy, které by
bude těžší, protože my budeme nakonec

1066
00:46:30,980 --> 00:46:33,280
vidět, řešení čistě iterativně.

1067
00:46:33,280 --> 00:46:35,980
>> Ale cliffhanger, že jsem
chtít nechat nás na to bylo.

1068
00:46:35,980 --> 00:46:40,720
Nech mě jít dopředu a otevřete
se soubor z -

1069
00:46:40,720 --> 00:46:44,300
vlastně, nech mě jít a
udělat opravdu rychle.

1070
00:46:44,300 --> 00:46:46,875
Nech mě jít napřed a navrhnout
následující.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Mezi dnešní kódu je tento soubor zde.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Tenhle, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Tak to je hloupý malý program, který
Prudce jsem se, že tvrdí, že to

1076
00:47:06,260 --> 00:47:06,940
následující.

1077
00:47:06,940 --> 00:47:10,140
V zásadě se nejprve deklaruje
int x volal a přiřadí ji

1078
00:47:10,140 --> 00:47:11,100
hodnota 1.

1079
00:47:11,100 --> 00:47:13,520
Pak prohlásí, int y a
přiřadí mu hodnotu 2.

1080
00:47:13,520 --> 00:47:15,310
Pak to vytiskne, co x a y je.

1081
00:47:15,310 --> 00:47:17,781
Pak říká, vyměňovat, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Pak tvrdí, že je volání funkce
tzv. swapu a předat x a

1083
00:47:21,670 --> 00:47:24,290
y, myšlenka je, že snad
x a y se vrátí

1084
00:47:24,290 --> 00:47:25,620
jinak, naopak.

1085
00:47:25,620 --> 00:47:27,110
Pak to tvrdí zaměnit!

1086
00:47:27,110 --> 00:47:28,420
s vykřičníkem.

1087
00:47:28,420 --> 00:47:30,190
Pak se vytiskne x a y.

1088
00:47:30,190 --> 00:47:33,480
>> Ale ukazuje se, že právě tato
jednoduchá demonstrace dolů

1089
00:47:33,480 --> 00:47:35,570
zde je vlastně buggy.

1090
00:47:35,570 --> 00:47:38,870
I když jsem prohlásil dočasný
variabilní a dočasně uvedení v

1091
00:47:38,870 --> 00:47:42,010
to, pak jsem přerozdělení
hodnota b -

1092
00:47:42,010 --> 00:47:45,080
které se cítí rozumné, protože jsem
uložili kopii na teplotě.

1093
00:47:45,080 --> 00:47:48,410
Pak jsem aktualizovat b rovna
vše, co bylo v temp.

1094
00:47:48,410 --> 00:47:51,610
Tento druh hazardní hru pohybující se
do b a b na použití tohoto

1095
00:47:51,610 --> 00:47:54,360
středního muž jménem temp cítí
naprosto rozumné.

1096
00:47:54,360 --> 00:47:57,270
>> Ale tvrdím, že když jsem tento příkaz
kód, jak budu dělat teď -

1097
00:47:57,270 --> 00:47:59,490
nech mě jít dopředu a vložte jej sem.

1098
00:47:59,490 --> 00:48:01,995
Zavolám tento noswap.c.

1099
00:48:01,995 --> 00:48:05,630
A jak již název napovídá, že to není
Bude to správný program.

1100
00:48:05,630 --> 00:48:09,460
Udělat noswap. / Ne swap.

1101
00:48:09,460 --> 00:48:12,110
x 1, y 2, vyměňovat, prohozeny.

1102
00:48:12,110 --> 00:48:14,220
x je 1, y je 2..

1103
00:48:14,220 --> 00:48:16,920
To je zásadní chyba, a to i
i když se to zdá naprosto

1104
00:48:16,920 --> 00:48:17,730
přiměřené ke mně.

1105
00:48:17,730 --> 00:48:21,330
A je tu důvod, ale nejsme
chystá odhalit příčinu jen zatím.

1106
00:48:21,330 --> 00:48:24,610
>> Pro tuto chvíli druhý cliffhanger jsem chtěl
nechat se je to,

1107
00:48:24,610 --> 00:48:27,120
Oznámení druhů na kupon kódů.

1108
00:48:27,120 --> 00:48:31,590
Naše inovace v pozdních dnů tento rok
vyvolalo netriviální počet

1109
00:48:31,590 --> 00:48:33,830
otázek, který byl
Není naším záměrem.

1110
00:48:33,830 --> 00:48:36,590
Záměrem těchto kupon kódů,
přičemž pokud tak učiníte část problému

1111
00:48:36,590 --> 00:48:39,850
na počátku, a tím získat další den,
Bylo to opravdu pomoci vy pomoci

1112
00:48:39,850 --> 00:48:42,420
sami začít brzy, třídit
vedlejších motivace vám.

1113
00:48:42,420 --> 00:48:44,880
Nám pomáhá distribuovat zatížení mezi
úřední hodiny tak, aby lépe

1114
00:48:44,880 --> 00:48:45,740
Je to něco win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Bohužel si myslím, že mé instrukce
nebyly do dnešního dne, velmi jasné, takže

1116
00:48:48,860 --> 00:48:52,230
Vrátil jsem se o tomto víkendu a aktualizovány
spec větší, odvážnější textu na

1117
00:48:52,230 --> 00:48:53,600
vysvětlit kulky, jako jsou tyto.

1118
00:48:53,600 --> 00:48:56,900
A právě to říci více veřejně, a
výchozí, základní problémové okruhy jsou dány čtvrtek

1119
00:48:56,900 --> 00:48:58,400
v poledne, dle sylabu.

1120
00:48:58,400 --> 00:49:02,030
Pokud začnete brzy, dokončovací část
problém nastavit ve středu v 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, ta část, která se vztahuje k kupón
kód, myšlenka je, že můžete rozšířit

1122
00:49:05,170 --> 00:49:07,710
Váš termín pro
P nastavit až do pátku.

1123
00:49:07,710 --> 00:49:10,890
To znamená, že ukousl malou část P
nastavit vůči tomu, co je obvykle

1124
00:49:10,890 --> 00:49:13,200
větší problém a koupit
si den navíc.

1125
00:49:13,200 --> 00:49:15,190
Opět platí, že vás dostane přemýšlet o tom,
Problém set, dostane vás do

1126
00:49:15,190 --> 00:49:16,380
úřední hodiny dřív.

1127
00:49:16,380 --> 00:49:20,670
Ale kuponu problém je stále
nutné, i když nemáte předloží ji.

1128
00:49:20,670 --> 00:49:23,340
>> Ale přesvědčivě to je.

1129
00:49:23,340 --> 00:49:26,520
(Šepotem) A ti lidé odchází
Již jsou toho litovat.

1130
00:49:26,520 --> 00:49:28,620
Jak jsou lidé na balkoně.

1131
00:49:28,620 --> 00:49:32,510
Omlouvám se předem na lidi na
balkon z důvodů, které budou

1132
00:49:32,510 --> 00:49:33,920
jasné, za chvíli.

1133
00:49:33,920 --> 00:49:37,050
>> Tak jsme to štěstí, že jeden z
CS50 bývalí kolegové hlava výuky na

1134
00:49:37,050 --> 00:49:39,302
společnost s názvem dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Mají velmi velkoryse darovali
kupon kód zde pro tuto tolik místa,

1136
00:49:45,500 --> 00:49:48,180
která je oproti
obvyklé 2GB.

1137
00:49:48,180 --> 00:49:51,740
Takže to, co jsem myslel, že by to na to
Poslední poznámka je to trochu prozradí,

1138
00:49:51,740 --> 00:49:55,380
přičemž za chvíli budeme odhalit
vítěz a kdo má kupón

1139
00:49:55,380 --> 00:49:57,980
kód, který pak můžete jít na jejich
webové stránky, zadejte do, a voila, získat

1140
00:49:57,980 --> 00:50:01,370
mnohem více prostoru pro vaši Dropbox
zařízení a osobních souborů.

1141
00:50:01,370 --> 00:50:05,690
>> A první, kdo by se chtěli zúčastnit
v tomto obrázku?

1142
00:50:05,690 --> 00:50:09,630
OK, teď, že je to ještě větší zábava.

1143
00:50:09,630 --> 00:50:14,010
Osoba, která obdrží tento 25-gigabyte
kupon kód - což je mnohem

1144
00:50:14,010 --> 00:50:16,150
přesvědčivější než pozdě
dny teď, možná -

1145
00:50:16,150 --> 00:50:20,620
je ten, kdo sedí na vrcholu
sedák, pod nímž je

1146
00:50:20,620 --> 00:50:21,620
že kuponu.

1147
00:50:21,620 --> 00:50:23,480
Nyní se můžete podívat pod
Váš sedák.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [PŘEHRÁVÁNÍ]

1150
00:50:29,680 --> 00:50:31,620
>> -Jeden, dva, tři.

1151
00:50:31,620 --> 00:50:35,015
>> [SCREAMING]

1152
00:50:35,015 --> 00:50:35,985
>> -Ty si auto!

1153
00:50:35,985 --> 00:50:36,670
Získáte auto!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Uvidíme
jste ve středu.

1155
00:50:37,970 --> 00:50:38,904
>> -Ty si auto!

1156
00:50:38,904 --> 00:50:39,371
Získáte auto!

1157
00:50:39,371 --> 00:50:40,305
Získáte auto!

1158
00:50:40,305 --> 00:50:41,706
Získáte auto!

1159
00:50:41,706 --> 00:50:43,107
Získáte auto!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: Balkón lidi, no
sem na přední straně,

1161
00:50:45,530 --> 00:50:46,866
kde máme navíc.

1162
00:50:46,866 --> 00:50:50,282
>> -Každý dostane auto!

1163
00:50:50,282 --> 00:50:52,234
Každý dostane auto!

1164
00:50:52,234 --> 00:50:52,722
>> [END PŘEHRÁVÁNÍ]

1165
00:50:52,722 --> 00:50:54,590
>> Vypravěč: V dalším CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: Ach můj bože bože bože bože
bože bože bože bože bože bože -

1167
00:51:00,374 --> 00:51:02,106
>> [Ukulele HRY]