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

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Vítejte na týden 3 oddílu.

3
00:00:06,490 --> 00:00:09,550
Díky, kluci, pro všechny přicházející
do tohoto dřívějšího startu čas dnes.

4
00:00:09,550 --> 00:00:11,466
Máme pěkný, malý
intimní skupina dnes.

5
00:00:11,466 --> 00:00:14,570
Takže doufejme, že se dostaneme
povrch, možná brzy,

6
00:00:14,570 --> 00:00:15,780
trochu brzo dnes.

7
00:00:15,780 --> 00:00:22,057
Tak rychle, jen některé
Oznámení pro pořadu dnešního dne.

8
00:00:22,057 --> 00:00:23,890
Než začneme, my jsme
bude prostě jít přes

9
00:00:23,890 --> 00:00:28,910
několik krátkých logistické problémy, pset
Otázky, Rozprava, takové věci.

10
00:00:28,910 --> 00:00:30,250
A pak budeme ponor přímo.

11
00:00:30,250 --> 00:00:34,710
Budeme používat debugger s názvem GDB na
začít odhalovat náš kód, který David

12
00:00:34,710 --> 00:00:36,550
vysvětleno v přednášce na druhý den.

13
00:00:36,550 --> 00:00:39,420
Půjdeme přes čtyři typy druhů.

14
00:00:39,420 --> 00:00:42,310
Půjdeme přes ně docela rychle
protože jsou to docela náročné.

15
00:00:42,310 --> 00:00:45,710
Ale vím, že všechny snímky a
Zdrojový kód je vždy on-line.

16
00:00:45,710 --> 00:00:50,810
Tak neváhejte, ve Vašem pročtení, aby
vrátit a podívat se na to.

17
00:00:50,810 --> 00:00:53,930
>> Projdeme
asymptotické notace, který

18
00:00:53,930 --> 00:00:55,944
je jen ozdobný způsob, jak
říkat "runtime"

19
00:00:55,944 --> 00:00:58,360
kde máme velký O, který
David je vysvětleno v přednášce.

20
00:00:58,360 --> 00:01:01,550
A máme i Omega, který
je dolní mez runtime.

21
00:01:01,550 --> 00:01:06,450
A budeme mluvit trochu víc
do hloubky o tom, jak tyto práce.

22
00:01:06,450 --> 00:01:10,160
A konečně, půjdeme přes binární vyhledávání,
protože mnoho z vás, kteří již

23
00:01:10,160 --> 00:01:15,190
Podíval se na své psets pravděpodobně víte, že
to je otázka, která je ve vaší pset.

24
00:01:15,190 --> 00:01:17,470
Takže budete všichni rádi
že budeme povídat to dnes.

25
00:01:17,470 --> 00:01:20,610
>> A konečně, podle vašich
oddíl zpětná vazba, jsem vlastně

26
00:01:20,610 --> 00:01:23,000
odešel asi 15 minut při
konec prostě jít přes

27
00:01:23,000 --> 00:01:27,730
logistika pset3, nějaké otázky,
možná trochu poradenství, chcete-li,

28
00:01:27,730 --> 00:01:28,990
Než začneme programování.

29
00:01:28,990 --> 00:01:30,890
Takže pojďme se pokusit se dostat přes
materiál docela rychle.

30
00:01:30,890 --> 00:01:33,880
A pak můžeme strávit nějaký čas
přičemž další otázky pro pset.

31
00:01:33,880 --> 00:01:35,230
DOBŘE.

32
00:01:35,230 --> 00:01:39,570
>> Rychle, takže jen pár
oznámení Než začneme dnes.

33
00:01:39,570 --> 00:01:45,410
Za prvé, vítejte k tomu,
to prostřednictvím dvou svých psets.

34
00:01:45,410 --> 00:01:49,432
Jsem se podívat na your-- jo, pojďme
získat potlesk pro tento jeden.

35
00:01:49,432 --> 00:01:51,140
Vlastně, byl jsem opravdu,
opravdu ohromen.

36
00:01:51,140 --> 00:01:55,800
Tříděné jsem první pset pro vás
Minulý týden a vy jste udělali neuvěřitelný.

37
00:01:55,800 --> 00:01:58,290
>> Styl byl na místě
kromě několika komentářů.

38
00:01:58,290 --> 00:02:00,660
Ujistěte se, že jste vždy
komentování váš kód.

39
00:02:00,660 --> 00:02:03,040
Ale vaše psets byli na místě.

40
00:02:03,040 --> 00:02:05,549
A tak dál.

41
00:02:05,549 --> 00:02:08,090
A to je dobré pro srovnávač na
vidět, že kluci jsou uvedení

42
00:02:08,090 --> 00:02:10,704
v jak hodně úsilí ve vašem stylu
a váš návrh v kódu

43
00:02:10,704 --> 00:02:12,120
že bychom chtěli pro vás vidět.

44
00:02:12,120 --> 00:02:16,450
Takže jsem šel po mé vděčnosti
pro zbytek TA.

45
00:02:16,450 --> 00:02:19,210
>> Existují však
Několik otázek Rozprava

46
00:02:19,210 --> 00:02:22,010
Já jen chci jít přes to
by se i můj život

47
00:02:22,010 --> 00:02:24,900
a mnoho jiný
TA "život trochu jednodušší.

48
00:02:24,900 --> 00:02:28,220
Za prvé, jsem si všiml
minulost week-- kolik z vás

49
00:02:28,220 --> 00:02:32,301
Byly běží na check50
váš kód Před odesláním?

50
00:02:32,301 --> 00:02:32,800
DOBŘE.

51
00:02:32,800 --> 00:02:36,690
Takže každý by měl dělat check50,
protože-- secret-- jsme vlastně

52
00:02:36,690 --> 00:02:41,540
běžet check50 jako součást našeho správnosti
skripty pro testování kódu.

53
00:02:41,540 --> 00:02:45,480
Takže pokud váš kód selhává
check50, se vší pravděpodobností,

54
00:02:45,480 --> 00:02:47,570
to asi bude
selhat naši kontrolu stejně.

55
00:02:47,570 --> 00:02:49,320
Někdy vy
mají správné odpovědi.

56
00:02:49,320 --> 00:02:52,200
Stejně jako v chamtivý, některé
máte správné číslo,

57
00:02:52,200 --> 00:02:53,960
stačí vytisknout nějaké extra věci.

58
00:02:53,960 --> 00:02:55,940
A to navíc věc
skutečně selže šek,

59
00:02:55,940 --> 00:02:58,440
protože počítač není
Opravdu víte, co to hledá.

60
00:02:58,440 --> 00:03:00,981
A tak to bude jen projít,
vidět, že váš výstup není

61
00:03:00,981 --> 00:03:03,810
odpovídat tomu, co očekáváme odpověď
být, a označit je to špatně.

62
00:03:03,810 --> 00:03:06,560
>> A já vím, že se stalo v
některé z vašich případů tento týden.

63
00:03:06,560 --> 00:03:09,870
Tak jsem se vrátil a ručně
deklasován kód každého.

64
00:03:09,870 --> 00:03:12,780
V budoucnu však,
prosím, ujistěte se,

65
00:03:12,780 --> 00:03:14,570
že utíkáš
zkontrolovat 50 na vašem kódu.

66
00:03:14,570 --> 00:03:17,970
Vzhledem k tomu, že je to tak trochu bolesti CK
muset vrátit zpět a ručně přeřazení do jiné třídy

67
00:03:17,970 --> 00:03:21,197
každý pset pro každého
svobodný, malý minul instance.

68
00:03:21,197 --> 00:03:22,530
Takže jsem neměl vzlétnout žádné body.

69
00:03:22,530 --> 00:03:25,210
Myslím, že jsem si vzal volno možná
jeden nebo dva pro design.

70
00:03:25,210 --> 00:03:27,710
V budoucnu i když, pokud
jste nedaří check50,

71
00:03:27,710 --> 00:03:31,330
budou přijata body
off správnost.

72
00:03:31,330 --> 00:03:35,020
>> Kromě toho, jsou psets
vzhledem pátek v poledne.

73
00:03:35,020 --> 00:03:38,990
Myslím, že je to sedm minut
pozdní doba odkladu, že jsme dát.

74
00:03:38,990 --> 00:03:42,434
Per Harvard času, oni mají dovoleno
bylo sedm minut pozdě na všechno.

75
00:03:42,434 --> 00:03:44,350
Tak tady na Yale, budeme
držet se, že stejně.

76
00:03:44,350 --> 00:03:47,910
Ale docela hodně, na 12:07,
pokud vaše pset není,

77
00:03:47,910 --> 00:03:49,720
to bude označen jako pozdě.

78
00:03:49,720 --> 00:03:53,160
A tak, když je označena
jak pozdě, TA-- já jsem

79
00:03:53,160 --> 00:03:54,870
Stále bude třídění vaše psets.

80
00:03:54,870 --> 00:03:56,760
Takže budete stále vidět stupeň objevit.

81
00:03:56,760 --> 00:03:58,820
Nicméně, vím, že se na
konec semestru,

82
00:03:58,820 --> 00:04:02,270
všechny pozdní psets bude jen
automaticky vynulována počítačem.

83
00:04:02,270 --> 00:04:04,490
>> Děláme to ze dvou důvodů.

84
00:04:04,490 --> 00:04:09,220
Jednou, někdy dostaneme
omluvila, jako výmluvy děkana

85
00:04:09,220 --> 00:04:10,762
později, že nevím o dosud.

86
00:04:10,762 --> 00:04:13,761
Tak jsme rádi, aby se ujistil, že jsme třídění
vše jen v případě, stejně jako, že jsem

87
00:04:13,761 --> 00:04:15,080
Chybí děkana výmluvu.

88
00:04:15,080 --> 00:04:17,000
A za druhé, mějte na
mysl, stále se můžete

89
00:04:17,000 --> 00:04:19,370
odpojit jednoho pset že
má plné šíři bodů.

90
00:04:19,370 --> 00:04:21,430
A tak jsme rádi stupeň
všechny vaše psets jen

91
00:04:21,430 --> 00:04:24,730
aby se ujistil, že váš prostor je
tam a vy je zkoušet.

92
00:04:24,730 --> 00:04:29,150
Takže i když je to pozdě, budete stále
získat úvěr na působnosti bodů, myslím.

93
00:04:29,150 --> 00:04:33,730
>> Takže morální příběhu je, aby
že vaše psets jsou v on-včas.

94
00:04:33,730 --> 00:04:38,350
A pokud nejsou v on-včas,
vím, že to není velký.

95
00:04:38,350 --> 00:04:41,678
Jo, než jsem jít dál, nemá někdo mít
Jakékoliv dotazy týkající pset zpětnou vazbu?

96
00:04:41,678 --> 00:04:42,178
To jo.

97
00:04:42,178 --> 00:04:43,630
>> Diváků: Věděli jste, že jsme
mohou klesnout jeden z psets?

98
00:04:43,630 --> 00:04:44,296
>> ANDI PENG: Jo.

99
00:04:44,296 --> 00:04:47,050
Takže je tu devět psets celkově
v průběhu semestru.

100
00:04:47,050 --> 00:04:50,610
A pokud máte prostor
points-- takže rozsah je jen,

101
00:04:50,610 --> 00:04:53,567
docela hodně, jste pokusem o
Problém, jste uvedení v čase,

102
00:04:53,567 --> 00:04:56,150
se vám ukazují, že jste
prokázal, že jste četl spec.

103
00:04:56,150 --> 00:04:57,191
To je docela velký prostor.

104
00:04:57,191 --> 00:04:59,370
A pokud jste se plní
rozsah bodů, my

105
00:04:59,370 --> 00:05:03,360
mohou klesnout nejnižší
jedním z plného rozsahu.

106
00:05:03,360 --> 00:05:06,790
Tak to je ve svůj prospěch, aby
dokončit a zkusit každý pset.

107
00:05:06,790 --> 00:05:10,320
>> I upload-- pokud žádný z
je pracovat, je nahrát všechny.

108
00:05:10,320 --> 00:05:13,711
A pak budeme snad moci
aby vám některé z těchto bodů zpět.

109
00:05:13,711 --> 00:05:14,210
Bezva.

110
00:05:14,210 --> 00:05:16,780
Nějaké další otázky?

111
00:05:16,780 --> 00:05:17,840
Skvělý.

112
00:05:17,840 --> 00:05:21,960
>> Za druhé, kancelář hours-- pár
rychlé poznámky o úředních hodinách.

113
00:05:21,960 --> 00:05:24,300
Takže nejprve, přijde na začátku týdne.

114
00:05:24,300 --> 00:05:26,909
Nikdo není nikdy v
úřední hodiny na pondělí.

115
00:05:26,909 --> 00:05:28,700
Christabel přišel
úřední hodiny minulou noc.

116
00:05:28,700 --> 00:05:29,691
Jo, Christabel.

117
00:05:29,691 --> 00:05:32,190
A to, co jsme se v kanceláři
hodiny v noci, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> Diváků: Měli jsme zmrzlinu.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Tak to je v pořádku, měli jsme
zmrzlina v úředních hodinách minulou noc.

120
00:05:36,160 --> 00:05:39,390
I když nemůžu slíbit, že
budeme mít zmrzlinu na úřední hodiny

121
00:05:39,390 --> 00:05:43,230
každý týden, co jsem vám slíbit,
je to, že tam bude významně

122
00:05:43,230 --> 00:05:45,380
lepší studentka poměr TA.

123
00:05:45,380 --> 00:05:47,650
Stejně jako legitimní, je to jako tři ku jedné.

124
00:05:47,650 --> 00:05:50,350
Vzhledem k tomu, že kontrast s
Čtvrtek, máte asi 150

125
00:05:50,350 --> 00:05:52,830
opravdu zdůraznil, děti a žádnou zmrzlinu.

126
00:05:52,830 --> 00:05:55,360
A to prostě není produktivní pro nikoho.

127
00:05:55,360 --> 00:05:58,730
Takže Ponaučení z příběhu je, přijde brzy
na pracovní dobu a dobrých věcí

128
00:05:58,730 --> 00:06:00,310
se stane.

129
00:06:00,310 --> 00:06:02,110
>> Také, přijďte připraveni klást otázky.

130
00:06:02,110 --> 00:06:03,200
Ty víš?

131
00:06:03,200 --> 00:06:05,420
Bez ohledu na to, co TA, já
myslím, říkali,

132
00:06:05,420 --> 00:06:10,710
jsme se dostat pár studentů
kteří přijdou na čtvrtek v, jako, 10:50

133
00:06:10,710 --> 00:06:15,100
ne po přečtení spec
bytí jako pomoz mi, pomoz mi.

134
00:06:15,100 --> 00:06:18,200
Bohužel v tomto bodě, je tu
není moc, co můžeme udělat, aby vám pomohl.

135
00:06:18,200 --> 00:06:19,590
Tak přijďte na začátku týdne.

136
00:06:19,590 --> 00:06:22,040
Přijďte brzy na úřední hodiny.

137
00:06:22,040 --> 00:06:23,350
Přijďte připraveni klást otázky.

138
00:06:23,350 --> 00:06:25,310
Ujistěte se, že vás, jako
student, jsou místa, kde

139
00:06:25,310 --> 00:06:27,620
musíte být tak, že
TA může vás spolu,

140
00:06:27,620 --> 00:06:32,850
což je to, co úřední hodiny
by měly být přiděleny pro.

141
00:06:32,850 --> 00:06:37,380
>> Za druhé, takže vím, že profesory
rád, aby nás překvapil s testy.

142
00:06:37,380 --> 00:06:39,439
Měl jsem profesora ty
jako, yo, mimochodem,

143
00:06:39,439 --> 00:06:41,230
pamatujte, že v polovině období
Máte příští pondělí.

144
00:06:41,230 --> 00:06:42,855
Jo, jsem nevěděl o tom střednědobém horizontu.

145
00:06:42,855 --> 00:06:45,630
Takže já budu, že TA
která vám připomíná, všichni, že kvíz

146
00:06:45,630 --> 00:06:47,270
0-- protože, víte, že jsme CS.

147
00:06:47,270 --> 00:06:50,730
Teď, když jsme udělali pole, dostanete
proč je to kvíz 0, ne kvíz 1, eh?

148
00:06:50,730 --> 00:06:51,320
DOBŘE.

149
00:06:51,320 --> 00:06:52,490
Oh, dostal jsem nějaké smích na tomto jeden.

150
00:06:52,490 --> 00:06:53,120
DOBŘE.

151
00:06:53,120 --> 00:06:59,710
>> Takže kvíz 0 bude 14.října, pokud
jste v sekci pondělí středa

152
00:06:59,710 --> 00:07:02,920
15. října, pokud jste v
sekce úterý čtvrtek.

153
00:07:02,920 --> 00:07:05,630
To neplatí pro
ti z vás na Harvardu

154
00:07:05,630 --> 00:07:10,350
who-- Myslím, že budete všichni
přičemž vaše kvízy na 14..

155
00:07:10,350 --> 00:07:13,560
>> Tak jo, příští týden, pokud
David, v přednášce, jde,

156
00:07:13,560 --> 00:07:15,747
jo, tak o tom
kvíz příští týden, vy všichni

157
00:07:15,747 --> 00:07:17,580
nebude v šoku, protože
jste přišli na části

158
00:07:17,580 --> 00:07:19,664
a víte, že vaše
kvíz 0 je za dva týdny.

159
00:07:19,664 --> 00:07:21,580
A budeme mít kontrolu
zasedání a všechno.

160
00:07:21,580 --> 00:07:26,360
Takže žádné obavy o
se bát za to.

161
00:07:26,360 --> 00:07:29,890
Jakékoliv dotazy before-- dotazy
ve všech otázkách týkajících se logistických,

162
00:07:29,890 --> 00:07:32,591
třídění, úřední hodiny, profily?

163
00:07:32,591 --> 00:07:33,090
To jo.

164
00:07:33,090 --> 00:07:35,100
>> Diváků: Takže je kvíz
bude v průběhu přednášky?

165
00:07:35,100 --> 00:07:35,766
>> ANDI PENG: Jo.

166
00:07:35,766 --> 00:07:39,460
Takže kvízu, myslím si, je 60
minut přidělené v tomto časovém úseku

167
00:07:39,460 --> 00:07:42,240
že budete jen vzít
v přednáškovém sále.

168
00:07:42,240 --> 00:07:44,810
Takže nemusíte přijít
o, stejně jako, náhodný 7:00 PM.

169
00:07:44,810 --> 00:07:46,140
Je to všechno dobré.

170
00:07:46,140 --> 00:07:47,100
To jo.

171
00:07:47,100 --> 00:07:50,060
Bezva.

172
00:07:50,060 --> 00:07:50,840
>> Dobře.

173
00:07:50,840 --> 00:07:54,330
Takže budeme
zavést koncept pro vás

174
00:07:54,330 --> 00:08:00,760
tento týden, že David má již druh
z dotkla v přednášce minulý týden.

175
00:08:00,760 --> 00:08:02,010
Říká se tomu GDB.

176
00:08:02,010 --> 00:08:05,570
A kolik z vás, zatímco v
průběh psaní psets,

177
00:08:05,570 --> 00:08:09,981
zaznamenali velké tlačítko, které říká,
"Debug" v horní části vašeho IDE?

178
00:08:09,981 --> 00:08:10,480
DOBŘE.

179
00:08:10,480 --> 00:08:13,770
Takže teď budeme skutečně dostat odkrýt
záhada, co tímto tlačítkem skutečně

180
00:08:13,770 --> 00:08:14,270
dělá.

181
00:08:14,270 --> 00:08:16,790
A já vám zaručit, je to
krásná, krásná věc.

182
00:08:16,790 --> 00:08:20,740
>> Takže až do teď, myslím, že
tam bylo dvě věci

183
00:08:20,740 --> 00:08:23,320
Studenti byli typicky
dělá při ladění psets.

184
00:08:23,320 --> 00:08:27,635
Jeden z nich, buď přidat
printf () - tak každých pár řádků,

185
00:08:27,635 --> 00:08:29,760
přidávají v printf () -
ach, co je to proměnná?

186
00:08:29,760 --> 00:08:32,551
Ach, jak je tato proměnná now--
a tak nějak vidět progresi

187
00:08:32,551 --> 00:08:33,940
z kódu, jak to běží.

188
00:08:33,940 --> 00:08:37,030
Nebo druhá metoda děti udělat, je
že stačí napsat celou věc

189
00:08:37,030 --> 00:08:38,610
a pak jít takhle na konci.

190
00:08:38,610 --> 00:08:39,970
Doufejme, že to funguje.

191
00:08:39,970 --> 00:08:44,851
Já vám zaručit, GDB je lepší
než oba z těchto metod.

192
00:08:44,851 --> 00:08:45,350
To jo.

193
00:08:45,350 --> 00:08:46,980
Takže to bude váš nový nejlepší přítel.

194
00:08:46,980 --> 00:08:51,780
Vzhledem k tomu, že je to krásná věc
který vizuálně zobrazuje oba

195
00:08:51,780 --> 00:08:54,850
co váš kód dělá
v určitém bodě

196
00:08:54,850 --> 00:08:57,486
stejně jako to, co všechny vaše
proměnné jsou účetní,

197
00:08:57,486 --> 00:08:59,610
jako to, co jejich hodnoty,
v tomto konkrétním bodě.

198
00:08:59,610 --> 00:09:02,670
A tímto způsobem, můžete si opravdu
nastavit zarážky v kódu.

199
00:09:02,670 --> 00:09:04,350
Můžete spustit přes řádek po řádku.

200
00:09:04,350 --> 00:09:07,324
A GDB budou mít jen pro
vy, zobrazí se pro vás,

201
00:09:07,324 --> 00:09:09,490
co všechny vaše proměnné
jsou, co dělají,

202
00:09:09,490 --> 00:09:10,656
co se děje v kódu.

203
00:09:10,656 --> 00:09:13,240
A takovým způsobem, že je to
tak mnohem jednodušší vidět

204
00:09:13,240 --> 00:09:17,120
co se děje, namísto printf-ing
nebo psaní se vaše prohlášení.

205
00:09:17,120 --> 00:09:19,160
>> Takže uděláme příklad později.

206
00:09:19,160 --> 00:09:20,660
Takže to vypadá trochu abstraktní.

207
00:09:20,660 --> 00:09:23,490
Žádné starosti, uděláme příklady.

208
00:09:23,490 --> 00:09:29,170
A tak v podstatě, tři největší,
nejpoužívanější funkce, které budete potřebovat v GDB

209
00:09:29,170 --> 00:09:32,500
jsou další, překročit,
a krok do tlačítek.

210
00:09:32,500 --> 00:09:34,860
Jdu přes hlavu
tam, ve skutečnosti, právě teď.

211
00:09:34,860 --> 00:09:40,930
>> Takže můžete vidět, že kluci vše
nebo bych měl přiblížit trochu?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
V zadní, můžete vidět, že?

214
00:09:44,470 --> 00:09:45,730
Mám přiblížit?

215
00:09:45,730 --> 00:09:46,480
Jen trochu?

216
00:09:46,480 --> 00:09:49,390
OK v pohodě.

217
00:09:49,390 --> 00:09:50,280
Tam jedeme.

218
00:09:50,280 --> 00:09:50,960
DOBŘE.

219
00:09:50,960 --> 00:09:57,000
>> Tak jsem si, tady, moji
implementace pro chamtivý.

220
00:09:57,000 --> 00:10:01,430
A i když spousta z vás napsal
chamtivý v while form-- že

221
00:10:01,430 --> 00:10:04,890
je naprosto přijatelný způsob, jak dělat
to-- jiný způsob, jak to udělat, je jednoduše

222
00:10:04,890 --> 00:10:06,280
rozdělit v modulo.

223
00:10:06,280 --> 00:10:09,290
Vzhledem k tomu, pak můžete mít svůj
hodnota a pak mít své zbývající.

224
00:10:09,290 --> 00:10:11,150
A pak stačí
přidat to všechno dohromady.

225
00:10:11,150 --> 00:10:13,390
Má logiku, co dělám
zde smysl pro každého,

226
00:10:13,390 --> 00:10:14,117
Než začneme?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Druh?

229
00:10:17,980 --> 00:10:18,710
Bezva.

230
00:10:18,710 --> 00:10:19,210
Skvělý.

231
00:10:19,210 --> 00:10:21,290
Je to docela sexy kus
kódu, řekl bych.

232
00:10:21,290 --> 00:10:23,502
Jak jsem řekl, David, v
přednáška, po chvíli,

233
00:10:23,502 --> 00:10:25,960
všichni začnete vidět kód
jako něco, co je krásné.

234
00:10:25,960 --> 00:10:29,950
A někdy, když vidíte, krásná
kód, je to tak nádherný pocit.

235
00:10:29,950 --> 00:10:35,410
>> Takže se však, když tento kód je velmi
krásné, že nefunguje správně.

236
00:10:35,410 --> 00:10:37,750
Takže pojďme běžet check50 na toto téma.

237
00:10:37,750 --> 00:10:39,440
Zkontrolujte, zda 50 20-- OOP.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
Je to pset2?

241
00:10:44,990 --> 00:10:46,870
To jo.

242
00:10:46,870 --> 00:10:47,520
Oh, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
DOBŘE.

245
00:10:52,890 --> 00:10:53,900
Tak jsme se spustit check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> A jak vy můžete vidět zde,
to nedaří několik případů.

248
00:11:07,170 --> 00:11:10,165
A pro některé z vás, v
Průběh dělá váš problém soupravy,

249
00:11:10,165 --> 00:11:11,110
jste jako, ehm, proč je to tak nefunguje.

250
00:11:11,110 --> 00:11:13,318
Proč to funguje pro některé
hodnoty, ale ne pro ostatní?

251
00:11:13,318 --> 00:11:17,760
No, GDB bude vám pomůže zjistit
out, proč tyto vstupy byly nefunguje.

252
00:11:17,760 --> 00:11:18,320
>> DOBŘE.

253
00:11:18,320 --> 00:11:21,640
Tak uvidíme, jeden z
Kontroly jsem byl neúspěšný v check50

254
00:11:21,640 --> 00:11:24,920
byla vstupní hodnota 0,41.

255
00:11:24,920 --> 00:11:27,830
Takže správná odpověď, že
měli byste se dostat je 4.

256
00:11:27,830 --> 00:11:33,090
Ale místo toho, co jsem vytištění
je 3-n, což je nesprávný.

257
00:11:33,090 --> 00:11:36,190
Takže pojďme stačí spustit tento ručně, jen
Ujistěte se, že check50 funguje.

258
00:11:36,190 --> 00:11:36,940
Udělejme ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Jejda, musím udělat chamtivý.

261
00:11:43,340 --> 00:11:43,840
Tam jedeme.

262
00:11:43,840 --> 00:11:44,381
Nyní ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Kolik je dluží?

265
00:11:47,670 --> 00:11:49,550
Udělejme 0,41.

266
00:11:49,550 --> 00:11:52,590
A jo, vidíme zde
že je to výstup 3

267
00:11:52,590 --> 00:11:55,160
když správná odpověď,
ve skutečnosti by mělo být 4.

268
00:11:55,160 --> 00:12:01,460
Takže pojďme vstoupit GDB a vidět, jak
může jít o tom, kterým tento problém.

269
00:12:01,460 --> 00:12:03,992
>> Takže první krok v
Vždy ladění kódu

270
00:12:03,992 --> 00:12:05,950
je nastavit zarážku,
nebo bod, na který

271
00:12:05,950 --> 00:12:09,079
Chcete v počítači nebo
debugger začít uvažovat.

272
00:12:09,079 --> 00:12:11,120
Takže pokud nemáte opravdu
víte, co je tvůj problém,

273
00:12:11,120 --> 00:12:14,670
Obvykle, typický, co chceme
udělat, je nastavit náš zarážku na hlavní.

274
00:12:14,670 --> 00:12:18,520
Takže pokud vy můžete vidět
červené tlačítko přímo tam,

275
00:12:18,520 --> 00:12:22,860
Jo, to jsem byl já nastavení
breakpoint pro hlavní funkci.

276
00:12:22,860 --> 00:12:24,130
I klikněte na to.

277
00:12:24,130 --> 00:12:26,130
>> A pak můžu jít až na mého tlačítko Debug.

278
00:12:26,130 --> 00:12:27,036
Trefil jsem ten knoflík.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Dovolte mi, abych zoom zpět, jestli můžu.

281
00:12:36,555 --> 00:12:38,020
Tam jedeme.

282
00:12:38,020 --> 00:12:40,730
Takže máme tady, panel na pravé straně.

283
00:12:40,730 --> 00:12:43,680
Je mi líto, kluci v zádech, vy
Nemůžete opravdu vidět opravdu dobře.

284
00:12:43,680 --> 00:12:49,090
Ale v podstatě všechny
toto právo panel dělá

285
00:12:49,090 --> 00:12:53,130
je sledování jak zvýrazněné
linie, což je řádek kódu

286
00:12:53,130 --> 00:12:56,640
že počítač je v současné době běží,
stejně jako všechny vaše proměnné

287
00:12:56,640 --> 00:12:57,600
tady dole.

288
00:12:57,600 --> 00:13:00,487
>> Takže jste dostali centů, mincí, n,
všechny prohlášen různé věci

289
00:13:00,487 --> 00:13:01,070
v tomto bodě.

290
00:13:01,070 --> 00:13:04,850
Žádné starosti, protože jsme vlastně
inicializuje je na všech proměnných dosud.

291
00:13:04,850 --> 00:13:07,200
Takže ve vašem počítači, vaše
Počítač je jen vidět,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 byl naposledy použitý funkce
tohoto paměťového prostoru v mém počítači.

293
00:13:14,376 --> 00:13:16,000
A tak to je, kde je v současné době centů.

294
00:13:16,000 --> 00:13:19,360
Ale ne, že jakmile se spustit kód,
by se měla stát inicializován.

295
00:13:19,360 --> 00:13:24,110
>> Takže pojďme projít, řádek
linka, co se tady děje.

296
00:13:24,110 --> 00:13:25,350
DOBŘE.

297
00:13:25,350 --> 00:13:29,400
Tak tady jsou tři
Tlačítka, které jsem právě vysvětlil.

298
00:13:29,400 --> 00:13:34,090
Máte Play, nebo funkce Run,
tlačítko, budete mít krok nad tlačítkem,

299
00:13:34,090 --> 00:13:36,600
a máte také krok do tlačítka.

300
00:13:36,600 --> 00:13:41,260
A v podstatě, všichni tři
je prostě jít přes váš kód

301
00:13:41,260 --> 00:13:42,690
a dělat různé věci.

302
00:13:42,690 --> 00:13:45,680
>> Takže obvykle, když jste ladění,
Nechceme, aby prostě zmáčknout Play,

303
00:13:45,680 --> 00:13:47,930
protože Play bude právě běží
váš kód k jeho konci.

304
00:13:47,930 --> 00:13:49,070
A pak nebudete ve skutečnosti
víte, co je tvůj problém

305
00:13:49,070 --> 00:13:51,432
je, pokud si nastavit více zarážky.

306
00:13:51,432 --> 00:13:53,890
Pokud nastavíte více zarážky,
to bude jen automaticky

307
00:13:53,890 --> 00:13:56,030
spustit z jedné zarážky,
na další, na další.

308
00:13:56,030 --> 00:13:58,030
Ale v tomto případě máme
jen, že jeden, protože my

309
00:13:58,030 --> 00:13:59,970
Chcete pracovat naši cestu
od shora dolů dolů.

310
00:13:59,970 --> 00:14:04,830
Takže budeme ignorovat ten knoflík
teď pro účely tohoto programu.

311
00:14:04,830 --> 00:14:08,230
>> Takže Krok přes funkci jen
Kroky nad každým jednu linku

312
00:14:08,230 --> 00:14:11,510
a řekne vám, co
počítač dělá.

313
00:14:11,510 --> 00:14:14,630
Step do funkce pokračuje
do skutečnou funkci

314
00:14:14,630 --> 00:14:16,000
že je na vašem řádku kódu.

315
00:14:16,000 --> 00:14:19,070
Tak například, stejně jako printf (),
že je funkce, že jo?

316
00:14:19,070 --> 00:14:21,980
Kdybych chtěl fyzicky krok
do funkce printf (),

317
00:14:21,980 --> 00:14:25,610
Já bych skutečně jít do kusu
směrovací číslo, kde printf () byl napsán a vidět

318
00:14:25,610 --> 00:14:26,730
co se tam děje.

319
00:14:26,730 --> 00:14:29,924
>> Ale obvykle, budeme předpokládat, že
kód, který dáme vám funguje.

320
00:14:29,924 --> 00:14:31,340
Předpokládáme, printf () pracuje.

321
00:14:31,340 --> 00:14:33,170
Předpokládáme, že GetInt () funguje.

322
00:14:33,170 --> 00:14:35,170
Takže není třeba
krok do těchto funkcí.

323
00:14:35,170 --> 00:14:37,170
Ale jestli je tu funkce
že píšete sami

324
00:14:37,170 --> 00:14:39,060
že chcete zkontrolovat
co se děje,

325
00:14:39,060 --> 00:14:41,200
byste chtěli kroku
do této funkce.

326
00:14:41,200 --> 00:14:43,940
>> Takže teď jsme jen tak
překročit tento kus kódu.

327
00:14:43,940 --> 00:14:44,485
Takže pojďme se podívat.

328
00:14:44,485 --> 00:14:46,547
Oh, print, "Ach hai, jak
mnoho změn je dlužen? "

329
00:14:46,547 --> 00:14:47,130
Nezajímá nás.

330
00:14:47,130 --> 00:14:49,830
Víme, že to funguje,
tak jsme krok nad ním.

331
00:14:49,830 --> 00:14:53,290
>> Takže n, což je naše float, že
máme initialized-- nebo declared--

332
00:14:53,290 --> 00:14:56,810
up na vrcholu, jsme nyní
rovnající se, že pro GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Takže pojďme krok přes to.

334
00:14:57,810 --> 00:14:59,580
A vidíme u
dno zde, program

335
00:14:59,580 --> 00:15:03,360
nabádá mě na vstup hodnotu.

336
00:15:03,360 --> 00:15:08,580
Takže pojďme Zadejte hodnotu chceme
testovat zde, což je 0,41.

337
00:15:08,580 --> 00:15:09,160
Skvělý.

338
00:15:09,160 --> 00:15:12,780
>> Takže teď n- si kluci vidět
tady, u bottom-- je to

339
00:15:12,780 --> 00:15:15,140
stored-- protože my
Zatím nejsou zaoblené, to je

340
00:15:15,140 --> 00:15:19,540
uložené v tomto jako obří
float, že je ,4099999996,

341
00:15:19,540 --> 00:15:22,550
což je dost blízko, aby naše
účely, právě teď, na 0,41.

342
00:15:22,550 --> 00:15:26,090
A pak se uvidí později, když jsme
pokračovat překročil programu,

343
00:15:26,090 --> 00:15:29,850
po tu, n se stal
zaoblené a centů stal 41.

344
00:15:29,850 --> 00:15:30,350
Skvělý.

345
00:15:30,350 --> 00:15:32,230
Takže víme, že naše zaokrouhlení má práci.

346
00:15:32,230 --> 00:15:34,700
Víme, že máme
správný počet centů,

347
00:15:34,700 --> 00:15:36,990
takže víme, že je to
není opravdu problém.

348
00:15:36,990 --> 00:15:40,050
>> Takže budeme pokračovat krokování
Na v tomto programu.

349
00:15:40,050 --> 00:15:40,900
Jdeme sem.

350
00:15:40,900 --> 00:15:46,139
A tak po tomto řádku kódu, my
by měli vědět, kolik čtvrtiny máme.

351
00:15:46,139 --> 00:15:46,680
Jsme překročit.

352
00:15:46,680 --> 00:15:52,040
A vidíte my, ve skutečnosti, mít jeden
čtvrtletí, protože jsme se odečte 25

353
00:15:52,040 --> 00:15:53,790
z naší počáteční hodnoty 41.

354
00:15:53,790 --> 00:15:55,890
A máme 16 doleva pro naše centů.

355
00:15:55,890 --> 00:15:58,830
>> Má každý pochopit, jak
Program je krokování

356
00:15:58,830 --> 00:16:02,980
a proč centů je dnes 16
a proč, teď, mince se stala 1?

357
00:16:02,980 --> 00:16:04,610
Je každý následující, že logika?

358
00:16:04,610 --> 00:16:05,110
Bezva.

359
00:16:05,110 --> 00:16:07,860
Tak, aby na tomto okamžiku
pracovní program je, že jo?

360
00:16:07,860 --> 00:16:09,797
Víme, že to dělá přesně to,
to, co chceme, aby to.

361
00:16:09,797 --> 00:16:11,880
A my ne ve skutečnosti
muset vytisknout, ach, co

362
00:16:11,880 --> 00:16:14,430
Je centů v tomto bodě,
co je mincí v tomto bodě.

363
00:16:14,430 --> 00:16:17,170
>> I nadále se prostřednictvím programu.

364
00:16:17,170 --> 00:16:18,100
Překročit.

365
00:16:18,100 --> 00:16:18,620
Bezva.

366
00:16:18,620 --> 00:16:19,700
Jdeme přes desetníky.

367
00:16:19,700 --> 00:16:20,200
Skvělý.

368
00:16:20,200 --> 00:16:22,367
Vidíme, že je to vzít
off 0,10 $ za desetník.

369
00:16:22,367 --> 00:16:23,450
A teď máme dvě mince.

370
00:16:23,450 --> 00:16:25,260
To je správně.

371
00:16:25,260 --> 00:16:31,555
>> Jdeme přes haléře a vidíme,
že jsme se dostali zbude centů.

372
00:16:31,555 --> 00:16:32,680
Hmm, to je divné.

373
00:16:32,680 --> 00:16:37,540
Tady nahoře na programu, měl jsem
k odečíst své haléře.

374
00:16:37,540 --> 00:16:39,400
Možná jsem prostě nebyl
tím, že linka práva.

375
00:16:39,400 --> 00:16:42,190
A běda, můžete vidět
tady, protože víme,

376
00:16:42,190 --> 00:16:44,360
že jsme posílení
potrubím 32 a 33,

377
00:16:44,360 --> 00:16:50,560
že je místo, kde náš program
nesprávně měl proměnných spustit.

378
00:16:50,560 --> 00:16:55,136
Takže můžeme dívat a vidět, oh,
Jsem odečtením centů tady,

379
00:16:55,136 --> 00:16:57,010
ale já nejsem ve skutečnosti
přidat do mého hodnotou mince.

380
00:16:57,010 --> 00:16:57,860
Jsem přidání do centů.

381
00:16:57,860 --> 00:17:00,234
A já nechci přidat do
centů, chci přidat do mincí.

382
00:17:00,234 --> 00:17:05,420
Takže když jsme se změnit na mince,
máme pracovní program.

383
00:17:05,420 --> 00:17:06,730
Můžu běžet check50.

384
00:17:06,730 --> 00:17:11,063
Stačí si jen opustíte GDB práva
tady a spusťte check50 znovu.

385
00:17:11,063 --> 00:17:11,938
Mohl bych to udělat.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Musím udělat chamtivý.

388
00:17:18,480 --> 00:17:19,940
0.41.

389
00:17:19,940 --> 00:17:22,819
A tady je to tisk
out správnou odpověď.

390
00:17:22,819 --> 00:17:26,569
>> Tak jako vy můžete vidět, GDB
je opravdu mocný nástroj

391
00:17:26,569 --> 00:17:29,940
protože když máme tolik kód
děje, a tak mnoho proměnných

392
00:17:29,940 --> 00:17:32,510
že je to pro nás těžké, jak
člověk, sledovat.

393
00:17:32,510 --> 00:17:35,360
Počítač, v GDB
debugger, má schopnost

394
00:17:35,360 --> 00:17:37,020
udržovat přehled o všem.

395
00:17:37,020 --> 00:17:40,480
Já vím, v Visionaire, vy pravděpodobně
mohl zasáhnout některé segmentace chyby

396
00:17:40,480 --> 00:17:43,150
protože jste používali
mimo hranice svého pole.

397
00:17:43,150 --> 00:17:46,510
V příkladu Caesara, to je
přesně to, co jsem zde provedena.

398
00:17:46,510 --> 00:17:50,060
>> Tak jsem zapomněl zkontrolovat
co by se mohlo stát, kdyby mi

399
00:17:50,060 --> 00:17:52,510
neměl dva argumenty příkazového řádku.

400
00:17:52,510 --> 00:17:53,880
Jen jsem to dát do této kontroly.

401
00:17:53,880 --> 00:17:57,380
A tak, když jsem běžet Debug-- nastavím
můj bod přerušení tam doprava.

402
00:17:57,380 --> 00:17:58,055
Běžím ladění.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> DOBŘE.

405
00:18:16,550 --> 00:18:17,050
To jo.

406
00:18:17,050 --> 00:18:20,350
Takže vlastně, GDB měl
se mi tam řekl,

407
00:18:20,350 --> 00:18:22,300
Byla to chyba, tam segmentace.

408
00:18:22,300 --> 00:18:24,883
Já nevím, co se děje
právě tam, ale když jsem běžel,

409
00:18:24,883 --> 00:18:25,590
že to funguje.

410
00:18:25,590 --> 00:18:29,410
Při spuštění řádků kódu a přes
GDB mohl jen náhle skončit na vás,

411
00:18:29,410 --> 00:18:31,540
jít nahoru a podívat se, co je červená chyba je.

412
00:18:31,540 --> 00:18:33,930
To vám řeknu, Hej,
měl poruchu segmentaci,

413
00:18:33,930 --> 00:18:38,550
což znamená, že jste se pokusili o přístup
prostory v poli, které neexistuje.

414
00:18:38,550 --> 00:18:39,050
To jo.

415
00:18:39,050 --> 00:18:43,280
>> Takže další problém
Nastavte tento týden, vy

416
00:18:43,280 --> 00:18:45,600
bude pravděpodobně mít hodně
Proměnné plovoucí kolem.

417
00:18:45,600 --> 00:18:48,560
Vy nebudete být jisti, co
všichni na mysli v určitém okamžiku.

418
00:18:48,560 --> 00:18:53,560
Takže GDB vám opravdu pomůže v přemýšlením
co oni jsou všichni rovná

419
00:18:53,560 --> 00:18:55,940
a jsou schopni vidět, že vizuálně.

420
00:18:55,940 --> 00:19:01,995
Je někdo zmatený o tom, jak
něco z toho pracuje?

421
00:19:01,995 --> 00:19:02,495
Bezva.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Dobře.

424
00:19:10,620 --> 00:19:14,260
Takže po tom, my jsme
bude potápět doprava

425
00:19:14,260 --> 00:19:17,562
do jsou čtyři různé
typy druhů pro tento týden.

426
00:19:17,562 --> 00:19:19,520
Jak mnozí z vás, nejprve
ze všeho, než začneme,

427
00:19:19,520 --> 00:19:23,020
Přečetl celý spec pro pset3?

428
00:19:23,020 --> 00:19:23,824
DOBŘE.

429
00:19:23,824 --> 00:19:24,740
Jsem hrdý na vás kluci.

430
00:19:24,740 --> 00:19:29,110
To je jako polovina třídy, která
je výrazně více než minule.

431
00:19:29,110 --> 00:19:33,950
>> Tak to je skvělé, protože když
mluvíme o obsahu

432
00:19:33,950 --> 00:19:36,170
v lecture-- nebo líto,
v section-- se mi líbí

433
00:19:36,170 --> 00:19:38,210
týkat hodně který
zpět na to, co je pset

434
00:19:38,210 --> 00:19:40,210
a jak chcete
implementovat, že ve vašem pset.

435
00:19:40,210 --> 00:19:42,400
Takže pokud přijdete s
číst spec, to bude

436
00:19:42,400 --> 00:19:45,510
bylo mnohem snazší pro vás pochopit
co mluvím, když říkám,

437
00:19:45,510 --> 00:19:48,720
oh hej, mohlo by to být opravdu
dobré místo k provedení tohoto druhu.

438
00:19:48,720 --> 00:19:52,870
Takže ti z vás, kteří si přečíst
spec vědí, že, jako součást vašeho pset,

439
00:19:52,870 --> 00:19:54,900
budete muset
napsat typ druhu.

440
00:19:54,900 --> 00:19:58,670
Takže to může být velmi užitečné
pro mnoho z vás dnes.

441
00:19:58,670 --> 00:20:01,760
>> Takže budeme začít s,
v podstatě, nejvíce jednoduchý typ

442
00:20:01,760 --> 00:20:04,580
Sort, výběr třídění.

443
00:20:04,580 --> 00:20:06,800
Typický algoritmus pro
jak bychom jít o to

444
00:20:06,800 --> 00:20:10,460
je-- David prošel to vše v
přednáška, tak jsem si rychle pohybovat podél

445
00:20:10,460 --> 00:20:13,900
here-- je v podstatě, vy
mají celou řadu hodnot.

446
00:20:13,900 --> 00:20:17,170
A pak najdete podrobnosti
Nejmenší hodnota netříděný

447
00:20:17,170 --> 00:20:20,200
a zaměňovat tuto hodnotu s
První netříděný hodnota.

448
00:20:20,200 --> 00:20:22,700
A pak si jen stále opakovat
se zbytkem vašeho seznamu.

449
00:20:22,700 --> 00:20:25,740
>> A tady je vizuální vysvětlení
o tom, jak to by mohlo fungovat.

450
00:20:25,740 --> 00:20:30,460
Tak například, když jsme byli na začátek
s řadou pěti elementů, index

451
00:20:30,460 --> 00:20:35,910
0 až 4, s 3, 5, 2, 6, a 4 Hodnoty
umístěny v array-- tak právě teď,

452
00:20:35,910 --> 00:20:38,530
my jen tak předpokládat,
že jsou všichni netříděný

453
00:20:38,530 --> 00:20:41,130
proto, že nebyly testovány jinak.

454
00:20:41,130 --> 00:20:44,130
>> Tak, jak se výběr druhu by
Práce je to, že by jako první

455
00:20:44,130 --> 00:20:46,800
projít celek
z netříděného pole.

456
00:20:46,800 --> 00:20:49,120
To by vybrat nejmenší hodnotu.

457
00:20:49,120 --> 00:20:51,750
V tomto případě, 3, pravá
Nyní, je nejmenší.

458
00:20:51,750 --> 00:20:52,680
To dostane až 5.

459
00:20:52,680 --> 00:20:55,620
Ne, 5 není větší than--
nebo líto, není menší than-- 3.

460
00:20:55,620 --> 00:20:57,779
Takže minimální hodnota je stále 3.

461
00:20:57,779 --> 00:20:58,695
A pak se dostanete na 2.

462
00:20:58,695 --> 00:21:00,990
Počítač vidí, oh, 2 je menší než 3.

463
00:21:00,990 --> 00:21:02,750
2 nyní musí být minimální hodnota.

464
00:21:02,750 --> 00:21:06,630
A tak 2 swapy s tímto prvním hodnotou.

465
00:21:06,630 --> 00:21:10,702
>> Takže po jednom průchodu, můžeme skutečně vidět
že 2 a 3 jsou prohozeny.

466
00:21:10,702 --> 00:21:13,910
A my jsme jen tak v tom pokračovat
To opět se zbytkem pole.

467
00:21:13,910 --> 00:21:17,660
Takže budeme jen projít
poslední čtyři indexy pole.

468
00:21:17,660 --> 00:21:20,670
Uvidíme, že 3 je
další minimální hodnota.

469
00:21:20,670 --> 00:21:23,240
Takže jdeme na swap, který se 4.

470
00:21:23,240 --> 00:21:26,900
A pak jsme to jen tak, aby
běh přes dokud ne, nakonec, vy

471
00:21:26,900 --> 00:21:33,730
dostat se do tříděného pole, v němž
2, 3, 4, 5, a 6 jsou všechny seřazeny.

472
00:21:33,730 --> 00:21:37,530
Rozumějí logiku
o tom, jak výběr třídění funguje?

473
00:21:37,530 --> 00:21:39,669
>> Prostě mít nějaký
na minimální hodnotu.

474
00:21:39,669 --> 00:21:41,210
Jste sledování, co to je.

475
00:21:41,210 --> 00:21:45,170
A když ji najdete, je zaměňovat
s první hodnotou v array--

476
00:21:45,170 --> 00:21:48,740
nebo, není první value--
další hodnota v matici.

477
00:21:48,740 --> 00:21:50,150
Bezva.

478
00:21:50,150 --> 00:21:55,460
>> Takže jak kluci druh
Viděl z krátké zahlédl,

479
00:21:55,460 --> 00:21:58,450
jdeme pseudocode to.

480
00:21:58,450 --> 00:22:02,510
Takže pokud vy vzadu chtějí
tvoří skupinu, všichni u stolu

481
00:22:02,510 --> 00:22:06,170
mohou tvořit trochu partnera, jdu
dát se vám bude líbit tři minuty

482
00:22:06,170 --> 00:22:08,190
jen probrat
logika, v angličtině,

483
00:22:08,190 --> 00:22:14,161
o tom, jak bychom mohli být schopni implementovat
pseudokód napsat výběrem Třídit.

484
00:22:14,161 --> 00:22:14,910
A je tu bonbón.

485
00:22:14,910 --> 00:22:16,118
Prosím, přijít a dostat bonbóny.

486
00:22:16,118 --> 00:22:19,520
Pokud jste do zad a chcete
cukroví, můžu hodit cukroví na vás.

487
00:22:19,520 --> 00:22:22,850
Ve skutečnosti, dělat vás-- chladu.

488
00:22:22,850 --> 00:22:23,552
Promiň.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
DOBŘE.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Takže pokud bychom chtěli, as
třída, zápis pseudokód

493
00:25:27,140 --> 00:25:30,466
na to, jak by se dalo přistupovat
tento problém, stačí klidně.

494
00:25:30,466 --> 00:25:32,340
Budu prostě jít kolem a,
v pořádku, zeptejte se skupiny

495
00:25:32,340 --> 00:25:35,065
na další řádek
Co bychom měli dělat.

496
00:25:35,065 --> 00:25:37,840
Takže pokud vy chcete začít
off, co je první věc,

497
00:25:37,840 --> 00:25:40,600
dělat, když se snažíte
provádět způsob, jak vyřešit tento program

498
00:25:40,600 --> 00:25:43,480
selektivně seřadit seznam?

499
00:25:43,480 --> 00:25:46,349
Pojďme jen předpokládat, my
mají celou řadu, v pořádku?

500
00:25:46,349 --> 00:25:49,088
>> Diváků: Chcete vytvořit některé
druh [neslyšitelný], že jste

501
00:25:49,088 --> 00:25:50,420
běh přes celé tvé pole.

502
00:25:50,420 --> 00:25:51,128
>> ANDI PENG: Správně.

503
00:25:51,128 --> 00:25:54,100
Takže budete chtít opakovat
přes všechny prostoru, je to tak?

504
00:25:54,100 --> 00:26:05,490
Tak dobré.

505
00:26:05,490 --> 00:26:08,600
Chtějí-li si kluci mi dát
další line-- jo, do zad.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> Publikum: Podívejte se na ně
vše pro nejmenší.

508
00:26:13,290 --> 00:26:14,248
>> ANDI PENG: Jdeme na to.

509
00:26:14,248 --> 00:26:17,438
Takže chceme projít a zkontrolovat,
vidět, co je minimální hodnota, že jo?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Chystám se zkrátit, že na "min."

512
00:26:24,840 --> 00:26:27,658
Co vy chcete dělat po
jste našli minimální hodnotu?

513
00:26:27,658 --> 00:26:28,533
>> Diváků: [Neslyšitelné]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Takže vy budete chtít
spínač je s prvním z tohoto pole,

516
00:26:33,150 --> 00:26:33,650
v pořádku?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
To je začátek, budu říkat.

519
00:26:46,850 --> 00:26:47,220
Dobře.

520
00:26:47,220 --> 00:26:50,386
Takže teď, že jste vyměnili první
člověk, co chcete dělat po tom?

521
00:26:50,386 --> 00:26:54,840
Takže teď víme, že tohle tady
musí být nejmenší hodnota, je to tak?

522
00:26:54,840 --> 00:26:58,310
Pak budete mít další odpočinek
matice, která je netříděný.

523
00:26:58,310 --> 00:27:01,569
Takže to, co chcete dělat tady, pokud máte
kluci chtějí, aby mi další řádek?

524
00:27:01,569 --> 00:27:04,610
Diváků: Takže chcete iteraci
po zbytek pole.

525
00:27:04,610 --> 00:27:05,276
ANDI PENG: Jo.

526
00:27:05,276 --> 00:27:09,857
A tak to, co dělá iterace
druh znamenat pravděpodobně budeme potřebovat?

527
00:27:09,857 --> 00:27:10,440
Jaký typ of--

528
00:27:10,440 --> 00:27:12,057
>> Publikum: Oh, další proměnná?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Pravděpodobně
další pro smyčce, je to tak?

530
00:27:13,890 --> 00:27:28,914
Takže jsme pravděpodobně bude chtít
přecházet through-- skvěle.

531
00:27:28,914 --> 00:27:31,830
A pak jste se vrátit a
Pravděpodobně zkontrolovat minimální znovu,

532
00:27:31,830 --> 00:27:32,100
v pořádku?

533
00:27:32,100 --> 00:27:34,975
A ty budeš stále opakovat
to, protože smyček jen tak

534
00:27:34,975 --> 00:27:36,010
zachovat systémem, ne?

535
00:27:36,010 --> 00:27:39,190
>> Tak jako vy můžete vidět, my
Jen mají obecnou pseudocode

536
00:27:39,190 --> 00:27:41,480
o tom, jak chceme, aby tento program vypadat.

537
00:27:41,480 --> 00:27:46,646
Tento iterate tady, co máme
typicky muset napsat do našeho kódu

538
00:27:46,646 --> 00:27:49,270
chceme-li iterovat prostřednictvím
pole, jaký typ konstrukce?

539
00:27:49,270 --> 00:27:51,030
Myslím si, že Christabel
již řekl dříve.

540
00:27:51,030 --> 00:27:51,500
>> Diváků: A pro smyčce.

541
00:27:51,500 --> 00:27:52,160
>> ANDI PENG: A pro smyčce?

542
00:27:52,160 --> 00:27:52,770
Přesně tak.

543
00:27:52,770 --> 00:27:56,060
Takže je to pravděpodobně
Bude to pro smyčku.

544
00:27:56,060 --> 00:27:59,240
Co je to šek tady bude znamenat?

545
00:27:59,240 --> 00:28:02,536
Obvykle, pokud chcete zkontrolovat
jestliže něco je něco else--

546
00:28:02,536 --> 00:28:03,270
>> Diváků: Pokud.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: if, že jo?

548
00:28:06,790 --> 00:28:10,790
A pak odkládací tady, budeme
projít později, protože David

549
00:28:10,790 --> 00:28:12,770
prošel, že v přednášce stejně.

550
00:28:12,770 --> 00:28:14,580
A pak druhá iterate implies--

551
00:28:14,580 --> 00:28:15,120
>> Diváků: Dalším pro smyčce.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another pro smyčce, přesně tak.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Takže pokud se díváme
na to správně,

555
00:28:22,000 --> 00:28:24,680
je vidět, že jsme pravděpodobně
bude potřebovat vnořené pro smyčce

556
00:28:24,680 --> 00:28:28,330
s podmíněného příkazu v tu
a pak skutečný kus kódu, který je

557
00:28:28,330 --> 00:28:31,360
chystá vyměnit hodnot.

558
00:28:31,360 --> 00:28:35,980
Tak jsem právě obecně psaný
kód zde pseudokód.

559
00:28:35,980 --> 00:28:38,910
A pak jsme to vlastně bude
fyzicky, jako třída,

560
00:28:38,910 --> 00:28:40,700
pokusit se realizovat to dnes.

561
00:28:40,700 --> 00:28:42,486
Vraťme se do tohoto IDE.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Uh-oh.

564
00:28:50,230 --> 00:28:51,754
Proč je to ne-- je to tak.

565
00:28:51,754 --> 00:28:52,253
DOBŘE.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Omlouváme se, ale dovolte mi, abych se snaží přiblížit trochu víc.

568
00:28:57,500 --> 00:28:59,310
Tam jedeme.

569
00:28:59,310 --> 00:29:05,060
Všechno, co dělám tady je, které jsem vytvořil
program s názvem "výběr / sort.c."

570
00:29:05,060 --> 00:29:10,860
Jsem vytvořil řadu devíti
hodnoty, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
V současné době, jak můžete
vidět, že jsou neuspořádané.

572
00:29:14,370 --> 00:29:17,880
n bude číslo, které
vám řekne množství hodnot

573
00:29:17,880 --> 00:29:18,920
máte v poli.

574
00:29:18,920 --> 00:29:20,670
V tomto případě jsme mají devět hodnoty.

575
00:29:20,670 --> 00:29:23,760
A já jsem právě dostal na smyčku zde
že vytiskne netříděného pole.

576
00:29:23,760 --> 00:29:28,370
>> A na závěr, jsem se také dostal na
smyčky, že právě tiskne to znovu.

577
00:29:28,370 --> 00:29:32,070
Takže teoreticky, je-li tento program
pracuje správně, na konci,

578
00:29:32,070 --> 00:29:35,670
měli byste vidět tištěný pro smyčce
, ve kterém 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 jsou správně, aby.

580
00:29:39,310 --> 00:29:43,410
>> Takže máme naši pseudocode zde.

581
00:29:43,410 --> 00:29:46,090
Má někdo chtěl to-- jsem jen
jít požádat o volunteers--

582
00:29:46,090 --> 00:29:49,540
řekni mi přesně, co mám psát, pokud
Chceme-li, jako první, jen opakovat

583
00:29:49,540 --> 00:29:52,840
prostřednictvím začátku tohoto pole?

584
00:29:52,840 --> 00:29:55,204
Jaký je řádek kódu, že jsem
pravděpodobně bude potřebovat tady?

585
00:29:55,204 --> 00:29:56,990
>> Diváků: [Neslyšitelné]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Jo, pocit
zdarma to-- Je nám líto,

587
00:29:59,010 --> 00:30:02,318
Nemusíte se stát up-- pocit
zatím zvýšit váš hlas trochu.

588
00:30:02,318 --> 00:30:08,190
>> Obecenstvo: pro int i rovná 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI PENG: Jo, dobrý.

590
00:30:10,690 --> 00:30:15,220
>> Diváků: i je menší než délka pole.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Takže mějte na
mysl tady, protože jsme

592
00:30:19,630 --> 00:30:23,060
nemají funkci, která
us říká, že délka pole,

593
00:30:23,060 --> 00:30:25,790
už máme
hodnota, která ukládá, že.

594
00:30:25,790 --> 00:30:27,920
Je to tak?

595
00:30:27,920 --> 00:30:31,010
Další věc, kterou mějte
v mind-- v poli

596
00:30:31,010 --> 00:30:33,940
devíti hodnot, jaké jsou indexy?

597
00:30:33,940 --> 00:30:38,720
Řekněme, že to pole bylo 0 až 3.

598
00:30:38,720 --> 00:30:41,500
Vidíte, že poslední
index je ve skutečnosti 3.

599
00:30:41,500 --> 00:30:45,530
Není to 4, i když tam je
čtyři hodnoty v poli.

600
00:30:45,530 --> 00:30:49,866
>> Takže tady, musíme být velmi opatrní
na to, co naše podmínky pro délku

601
00:30:49,866 --> 00:30:50,490
bude.

602
00:30:50,490 --> 00:30:51,948
>> Diváků: Nebylo by to n mínus 1?

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: Jde to
n minus 1, přesně tak.

604
00:30:54,440 --> 00:30:57,379
Dává to smysl, proč
to je n minus 1, všichni?

605
00:30:57,379 --> 00:30:58,920
Je to proto, že pole jsou nula-indexovány.

606
00:30:58,920 --> 00:31:02,010
Začnou na 0 a provozovat až n minus 1.

607
00:31:02,010 --> 00:31:03,210
Jo, je to trochu složitější.

608
00:31:03,210 --> 00:31:03,730
DOBŘE.

609
00:31:03,730 --> 00:31:05,929
A pak--

610
00:31:05,929 --> 00:31:08,054
Publikum: Isnt'1 že
již postaráno i když,

611
00:31:08,054 --> 00:31:11,400
pouhým neříká "menší než nebo
rovno "a jen řekl:" méně než? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: To je
opravdu dobrá otázka.

613
00:31:13,108 --> 00:31:13,630
Ano, ano.

614
00:31:13,630 --> 00:31:17,410
Ale také způsob, jakým jsme
provádění kontroly právo,

615
00:31:17,410 --> 00:31:19,120
je třeba porovnat dvě hodnoty.

616
00:31:19,120 --> 00:31:21,009
Takže jste vlastně chcete
nechte "na" prázdný.

617
00:31:21,009 --> 00:31:23,050
Vzhledem k tomu, pokud si porovnat
tohle, vy nebudete

618
00:31:23,050 --> 00:31:25,530
nic po něm
porovnat, že jo?

619
00:31:25,530 --> 00:31:27,460
To jo.

620
00:31:27,460 --> 00:31:29,297
Takže i ++.

621
00:31:29,297 --> 00:31:30,380
Pojďme přidat naše držáky.

622
00:31:30,380 --> 00:31:30,880
Jejda.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Skvělý.

625
00:31:34,710 --> 00:31:39,117
Takže máme začátek
naší vnější smyčky.

626
00:31:39,117 --> 00:31:41,450
Takže teď pravděpodobně chtít
vytvořit proměnnou pro vedení

627
00:31:41,450 --> 00:31:43,085
Trať nejmenší hodnotu, je to tak?

628
00:31:43,085 --> 00:31:45,751
Má někdo chtěl mi dát
řádek kódu, který by to dělal?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Co budeme potřebovat, pokud jdeme
chtít uložit něco?

631
00:31:53,570 --> 00:31:55,047
>> Správně.

632
00:31:55,047 --> 00:31:57,630
Možná, že lepší název pro to
by be-- "temp" zcela works--

633
00:31:57,630 --> 00:32:00,655
možná více příhodně pojmenovaný by bylo,
pokud chceme, aby nejmenší value--

634
00:32:00,655 --> 00:32:01,624
>> Diváků: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: min, tam jdeme.

636
00:32:02,790 --> 00:32:05,230
min by bylo dobré.

637
00:32:05,230 --> 00:32:08,340
A tak tady to, co my
Chcete inicializovat ji?

638
00:32:08,340 --> 00:32:09,620
To je trochu složitější.

639
00:32:09,620 --> 00:32:13,580
Protože právě teď u
začátek tohoto pole,

640
00:32:13,580 --> 00:32:15,730
jste se podíval na cokoliv, že jo?

641
00:32:15,730 --> 00:32:19,200
Tak co, automaticky, pokud
jsme jen na i rovná 0,

642
00:32:19,200 --> 00:32:22,302
to, co chceme inicializovat
naše první minimální hodnota to?

643
00:32:22,302 --> 00:32:22,802
Diváků: i.

644
00:32:22,802 --> 00:32:24,790
ANDI PENG: i, přesně tak.

645
00:32:24,790 --> 00:32:27,040
Christabel, proč chceme,
inicializovat to i?

646
00:32:27,040 --> 00:32:28,510
>> Publikum: Vzhledem k tomu, no,
začínáme s 0.

647
00:32:28,510 --> 00:32:31,660
Takže, protože máme s čím srovnávat
to je minimální skončí na 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI PENG: Přesně tak.

649
00:32:32,451 --> 00:32:34,400
Takže ona je přesně to pravé.

650
00:32:34,400 --> 00:32:36,780
Protože máme vlastně
přesto se podíval na cokoliv,

651
00:32:36,780 --> 00:32:38,680
nevíme, co naše minimální hodnota je.

652
00:32:38,680 --> 00:32:41,960
Chceme jen inicializovat ji
i, která v současné době, je tady.

653
00:32:41,960 --> 00:32:44,750
A jak budeme pokračovat
přesunout dolů toto pole,

654
00:32:44,750 --> 00:32:48,122
uvidíme, že s každým
Další průchod, i zvýší.

655
00:32:48,122 --> 00:32:49,830
A tak se v tomto bodě,
i se pravděpodobně bude

656
00:32:49,830 --> 00:32:52,329
že chtějí být minimální,
protože to bude cokoliv

657
00:32:52,329 --> 00:32:54,520
je začátek netříděného pole.

658
00:32:54,520 --> 00:32:55,270
Bezva.

659
00:32:55,270 --> 00:32:58,720
>> Takže teď chcete přidat
smyčky for tady to je

660
00:32:58,720 --> 00:33:03,225
bude iterovat
netříděný, nebo zbytek tohoto pole.

661
00:33:03,225 --> 00:33:05,808
Má někdo chtěl mi dát
řádek kódu, který by to dělal?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- co potřebujeme tady dole?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Co se děje jít to pro smyčce?

666
00:33:18,820 --> 00:33:19,465
To jo.

667
00:33:19,465 --> 00:33:21,590
Diváků: Tak jsme chtěli
mají jiný celé číslo,

668
00:33:21,590 --> 00:33:25,080
proto, že jsme běží přes zbytek
matice namísto I, možná

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Jo, j zní dobře.

671
00:33:27,301 --> 00:33:27,850
Rovná?

672
00:33:27,850 --> 00:33:33,930
>> Diváků: Takže by bylo i plus 1, protože
začínáte na další hodnotu.

673
00:33:33,930 --> 00:33:40,395
A pak se to znovu end--, j je
méně než n mínus 1 a poté j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI PENG: Skvělé.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> A pak tady, budeme chtít
zkontrolovat, zda je splněna podmínka naše,

677
00:33:52,750 --> 00:33:53,250
v pořádku?

678
00:33:53,250 --> 00:33:55,740
Vzhledem k tomu, že chcete
změnit minimální hodnotu

679
00:33:55,740 --> 00:33:58,700
pokud je to ve skutečnosti menší, než to, co
jste přirovnal ji k, ne?

680
00:33:58,700 --> 00:34:01,146
Takže to, co budeme chtít v tu?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Zkontrolujte.

683
00:34:04,897 --> 00:34:06,730
Jaký typ prohlášení
jsme pravděpodobně bude

684
00:34:06,730 --> 00:34:08,389
ti chcete použít, kdybychom
chcete zkontrolovat něco?

685
00:34:08,389 --> 00:34:09,360
>> Diváků: if.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: if.

687
00:34:10,485 --> 00:34:13,155
Tak if-- a co to bude
podmínka, že chceme dovnitř

688
00:34:13,155 --> 00:34:13,988
naší if?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> AUDIENCE: V případě, že hodnota j
je menší než hodnota já-

691
00:34:22,960 --> 00:34:24,600
>> ANDI PENG: Přesně tak.

692
00:34:24,600 --> 00:34:27,480
Tak if-- tak toto pole se nazývá "pole."

693
00:34:27,480 --> 00:34:27,980
Skvělý.

694
00:34:27,980 --> 00:34:30,465
Takže pokud array-- co to bylo?

695
00:34:30,465 --> 00:34:31,090
Zopakuj to.

696
00:34:31,090 --> 00:34:39,590
>> Diváků: Pokud je pole-j je menší než
array-i, pak bychom změnit min.

697
00:34:39,590 --> 00:34:41,590
Takže min by j.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Dává to smysl?

700
00:34:47,249 --> 00:34:48,670
DOBŘE.

701
00:34:48,670 --> 00:34:52,929
A teď tady dole, jsme vlastně
chtějí realizovat swap, že jo?

702
00:34:52,929 --> 00:34:58,285
Takže vzpomínáte, v přednášce, že David, když
se snažil vyměnit the-- to, co bylo

703
00:34:58,285 --> 00:34:59,996
to-- pomerančový džus a milk--

704
00:34:59,996 --> 00:35:01,150
>> Diváků: To bylo hrubé.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Jo, to bylo docela hrubý.

706
00:35:02,816 --> 00:35:05,310
Ale byl to docela dobrý
koncept demonstrovat čas.

707
00:35:05,310 --> 00:35:08,430
Takže myslíte, že z vašich hodnot zde.

708
00:35:08,430 --> 00:35:10,794
Máte pole
min, řada i,

709
00:35:10,794 --> 00:35:12,460
nebo co jsme se pokoušeli vyměnit zde.

710
00:35:12,460 --> 00:35:15,310
A ty asi nelze nalít je do
navzájem ve stejnou dobu, že?

711
00:35:15,310 --> 00:35:17,180
Tak co s tím budeme
muset vytvořit zde

712
00:35:17,180 --> 00:35:19,126
aby správně vyměnit hodnoty?

713
00:35:19,126 --> 00:35:19,820
>> Diváků: dočasné proměnné.

714
00:35:19,820 --> 00:35:21,370
>> ANDI PENG: dočasné proměnné.

715
00:35:21,370 --> 00:35:22,570
Takže pojďme dělat int temp.

716
00:35:22,570 --> 00:35:25,681
Vidíš, to bude lepší
čas to-- hej, co to bylo?

717
00:35:25,681 --> 00:35:26,180
DOBŘE.

718
00:35:26,180 --> 00:35:29,800
Takže by to bylo lepší
čas pojmenovat proměnnou "Temp."

719
00:35:29,800 --> 00:35:30,730
Takže pojďme dělat int temp.

720
00:35:30,730 --> 00:35:32,563
Co budeme
SET TEMP rovnou tady?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
Publikum: Min?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI PENG: Je to trochu složitější.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
Ve skutečnosti nezáleží na tom, do konce roku.

727
00:35:44,880 --> 00:35:47,690
Nezáleží na tom, co
Pořadí se rozhodnete vyměnit v

728
00:35:47,690 --> 00:35:50,862
tak dlouho, jak budete dělat jistý, že jste
sledování, co jste swapování.

729
00:35:50,862 --> 00:35:52,250
>> Diváků: Mohlo by to být array-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Jo, pojďme dělat pole-I.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
A co pak je další řádek
kódu chceme mít tady?

733
00:35:59,305 --> 00:36:00,680
Diváků: array-i rovná array-J.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: A konečně?

736
00:36:08,070 --> 00:36:12,070
Diváků: array-j se rovná array-i.

737
00:36:12,070 --> 00:36:14,525
Diváků: Nebo array-j rovná
array-temp-- nebo teplota.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI PENG: OK.

740
00:36:19,430 --> 00:36:21,510
Takže pojďme běžet to a uvidíme,
jestli to bude fungovat.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Tam, kde se děje, že?

743
00:36:39,335 --> 00:36:40,210
Oh, to je problém.

744
00:36:40,210 --> 00:36:44,320
Viz, na lince 40, my jsme
se snaží používat pole-J?

745
00:36:44,320 --> 00:36:47,022
Ale kde j existují pouze v?

746
00:36:47,022 --> 00:36:48,402
>> Publikum: V cyklu for.

747
00:36:48,402 --> 00:36:49,110
ANDI PENG: Správně.

748
00:36:49,110 --> 00:36:51,730
Tak co s tím budeme muset udělat?

749
00:36:51,730 --> 00:36:53,170
>> Diváků: Definovat to venku the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
Publikum: Jo, myslím, že máš
použít jiný if, že jo?

752
00:37:00,610 --> 00:37:05,230
Tak, jako v případě, že minimum--
v pořádku, nechte mě přemýšlet.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI peng: Kluci, zkuste
se podívat Pojďme

755
00:37:09,990 --> 00:37:11,270
viz, co se něco, co můžeme dělat?

756
00:37:11,270 --> 00:37:11,811
>> Diváků: OK.

757
00:37:11,811 --> 00:37:15,900
Takže v případě, že minimální nerovná
j-- takže v případě, že minimum je stále já--

758
00:37:15,900 --> 00:37:17,570
pak bychom nemuseli vyměnit.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Znamená to, že rovné i?

761
00:37:24,712 --> 00:37:25,920
Co chceš říct tady?

762
00:37:25,920 --> 00:37:30,494
>> Publikum: Nebo jo, v případě, že
Minimální není rovno i, jo.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI PENG: OK.

765
00:37:40,210 --> 00:37:42,040
No, to řeší, druh, naše problémy.

766
00:37:42,040 --> 00:37:47,265
Ale to stále ještě neřeší
problém z toho, co se stane, když j-- od j

767
00:37:47,265 --> 00:37:49,890
neexistuje mimo něj, co
si chceme s tím dělat?

768
00:37:49,890 --> 00:37:50,698
Deklarovat to venku?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Pojďme zkusit spustit tento.

771
00:38:02,730 --> 00:38:04,435
Uh-oh.

772
00:38:04,435 --> 00:38:06,200
Náš druh nefunguje.

773
00:38:06,200 --> 00:38:10,060
>> Jak vidíte, naše původní
array měl tyto hodnoty.

774
00:38:10,060 --> 00:38:14,800
A potom by měl mít
byl v 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Nefunguje to.

776
00:38:15,530 --> 00:38:16,030
Ahh.

777
00:38:16,030 --> 00:38:17,184
Co děláme?

778
00:38:17,184 --> 00:38:17,850
Diváků: Debug.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: Dobře, můžeme to zkusit.

781
00:38:23,370 --> 00:38:25,030
Můžeme ladit.

782
00:38:25,030 --> 00:38:26,042
Oddálení trochu.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Vydejme naši zarážku.

785
00:38:33,656 --> 00:38:37,280
Pojďme jako-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Takže proto, že už víme, že
tyto řádky, 15 až 22,

787
00:38:40,444 --> 00:38:43,610
jsou working-- protože všechno, co dělám, je
Jen iterace a printing--

788
00:38:43,610 --> 00:38:45,406
Můžu jít dopředu a vynechat to.

789
00:38:45,406 --> 00:38:47,280
Začněme na řádku 25.

790
00:38:47,280 --> 00:38:48,712
OOP, dovolte mi, abych se zbavit toho.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> Diváků: Takže je zarážka
kde začíná ladění?

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: Or zastaví.

794
00:38:54,890 --> 00:38:55,670
Diváků: Or zastaví.

795
00:38:55,670 --> 00:38:55,930
ANDI PENG: Jo.

796
00:38:55,930 --> 00:38:58,640
Můžete nastavit více zarážky a
to může jen skočit z jednoho na druhého.

797
00:38:58,640 --> 00:39:01,590
Ale v tomto případě nevíme,
kde je tato chyba děje.

798
00:39:01,590 --> 00:39:03,780
Tak jsme se jen chcete
začít od shora dolů.

799
00:39:03,780 --> 00:39:05,020
Jo.

800
00:39:05,020 --> 00:39:05,550
DOBŘE.

801
00:39:05,550 --> 00:39:08,460
>> Takže tato linka tady, můžeme zasáhnout.

802
00:39:08,460 --> 00:39:11,499
Můžete vidět tady dole,
máme pole.

803
00:39:11,499 --> 00:39:13,290
To jsou hodnoty
které jsou v poli.

804
00:39:13,290 --> 00:39:16,360
Vidíte, že, jak se index 0, to
odpovídá value-- oh,

805
00:39:16,360 --> 00:39:17,526
Budu se snažit přiblížit.

806
00:39:17,526 --> 00:39:20,650
Omlouváme se, ale je to opravdu těžké
na see-- na indexu pole 0,

807
00:39:20,650 --> 00:39:24,090
máme hodnotu 4 a
pak tak dále a tak dále.

808
00:39:24,090 --> 00:39:25,670
Máme lokální proměnné.

809
00:39:25,670 --> 00:39:28,570
Právě teď jsem se rovná
0, což chceme, aby to bylo.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> A tak se pojďme držet krokování.

812
00:39:33,690 --> 00:39:36,850
Naše minimum je rovno 0,
což také chceme, aby to bylo.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
A pak jsme se vstoupit na náš druhý pro
smyčky, pokud array-j je menší než pole-i,

815
00:39:45,560 --> 00:39:46,380
což nebylo.

816
00:39:46,380 --> 00:39:48,130
Takže jste vidět, jak
že přeskočil, že?

817
00:39:48,130 --> 00:39:52,430
>> Diváků: Takže pokud by v případě,
minimum, vše that-- ne že by to

818
00:39:52,430 --> 00:39:55,424
být uvnitř prvního cyklu for?

819
00:39:55,424 --> 00:39:57,340
ANDI PENG: Ne, protože
si přesto chcete testovat.

820
00:39:57,340 --> 00:40:00,329
Chcete udělat srovnání každý
čas, dokonce i po spuštění přes to.

821
00:40:00,329 --> 00:40:02,620
Nemusíte jen chci, aby to
na první promítání.

822
00:40:02,620 --> 00:40:05,240
Chcete-li to s
každý další zase průchod.

823
00:40:05,240 --> 00:40:07,198
Takže vy chcete zkontrolovat
Váš zdravotní stav uvnitř.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Takže jsme jen tak
udržují v provozu tudy.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Dám vám kluci nápovědu.

828
00:40:18,420 --> 00:40:23,910
To má co do činění s tím, že při
máte kontrolu svůj podmíněný,

829
00:40:23,910 --> 00:40:26,600
nejste kontrolu
pro správné indexu.

830
00:40:26,600 --> 00:40:32,510
Takže teď jste kontrola
index pole j je menší než pole

831
00:40:32,510 --> 00:40:33,970
index i.

832
00:40:33,970 --> 00:40:36,580
Ale to, co děláš se na
počátku pro smyčky?

833
00:40:36,580 --> 00:40:38,260
Nejsi nastavení j rovnající se i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Jo, takže můžeme vlastně
ukončete ladicí zde.

836
00:40:45,415 --> 00:40:47,040
Takže pojďme se podívat na naši pseudokódu.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- jdeme
začátek i rovná 0.

839
00:40:52,580 --> 00:40:54,760
Chystáme se jít až na n minus 1.

840
00:40:54,760 --> 00:40:58,040
Pojďme zjistit, jsme mít toto právo?

841
00:40:58,040 --> 00:40:59,580
Jo, že měl pravdu.

842
00:40:59,580 --> 00:41:02,080
>> Takže tady uvnitř, my jsme
bude vytvořit minimální hodnotu

843
00:41:02,080 --> 00:41:03,630
a nastavit, aby se rovná i.

844
00:41:03,630 --> 00:41:04,950
Věděli jsme to udělat?

845
00:41:04,950 --> 00:41:06,270
Jo, to udělal.

846
00:41:06,270 --> 00:41:10,430
Nyní v našem vnitřním pro smyčce, my jsme
dělat j rovná i na n minus 1.

847
00:41:10,430 --> 00:41:11,950
Věděli jsme to udělat?

848
00:41:11,950 --> 00:41:15,540
Skutečně, my jsme dělali to.

849
00:41:15,540 --> 00:41:19,922
>> Tak Avšak to, co jsme porovnávání tady?

850
00:41:19,922 --> 00:41:20,925
>> Diváků: j plus 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Přesně tak.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
A pak budete chtít nastavit
vaše minimální rovná j plus 1 i.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Tak jsem šel přes to opravdu rychle.

856
00:41:32,640 --> 00:41:36,190
Myslíte si kluci pochopili
proč je to j plus 1?

857
00:41:36,190 --> 00:41:36,890
DOBŘE.

858
00:41:36,890 --> 00:41:40,700
>> Takže ve vašem poli, v
vaše první průchod,

859
00:41:40,700 --> 00:41:44,850
Váš pro smyčce, pro int
i = 0, ať to prostě

860
00:41:44,850 --> 00:41:46,740
Předpokládám, že to ještě nebyl změněn.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Máme řadu, zcela,
jen čtyři netříděné prvky, ne?

863
00:41:56,760 --> 00:42:00,760
Takže chceme inicializovat i rovná 0.

864
00:42:00,760 --> 00:42:03,650
A já se chystá právě
projít této smyčky.

865
00:42:03,650 --> 00:42:08,560
A tak se v prvním průchodu, jdeme
inicializovat proměnnou s názvem "min"

866
00:42:08,560 --> 00:42:11,245
že také se rovná i, protože
nemáme minimální hodnotu.

867
00:42:11,245 --> 00:42:12,870
Tak, že je v současné době rovno 0 i.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
A pak budeme projít.

870
00:42:17,640 --> 00:42:19,270
A my chceme, aby se znovu opakovat.

871
00:42:19,270 --> 00:42:22,900
Teď, když jsme našli to, co náš minimální
je, chceme iterovat

872
00:42:22,900 --> 00:42:25,190
znovu vidět, jestli je to srovnání, je to tak?

873
00:42:25,190 --> 00:42:40,440
Tak j, tady, se děje
na rovné i, což je 0.

874
00:42:40,440 --> 00:42:46,320
A pak, pokud array j a i, který
je ten, který je další nad, as méně

875
00:42:46,320 --> 00:42:49,270
než to, co aktuální minimum
je hodnota, které chcete vyměnit.

876
00:42:49,270 --> 00:42:56,850
>> Takže řekněme, že máme
má, stejně jako, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Právě teď, i je rovno
0 a j je rovno 0.

878
00:43:01,610 --> 00:43:05,210
A to je náš minimální hodnota.

879
00:43:05,210 --> 00:43:09,950
Pokud je pole-j a já-, takže v případě, že jednou
to je po jednom díváme

880
00:43:09,950 --> 00:43:13,450
je větší než ten před tím,
to bude stát minimum.

881
00:43:13,450 --> 00:43:18,120
>> Takže tady vidíme, že 5
není menší než to.

882
00:43:18,120 --> 00:43:19,730
Takže to bude nebýt 5.

883
00:43:19,730 --> 00:43:23,580
Vidíme, že 1 je menší než 2, ne?

884
00:43:23,580 --> 00:43:32,970
Takže teď víme, že naše minimum je
bude hodnota indexu při 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
To jo?

886
00:43:34,030 --> 00:43:39,170
A pak, když se dostanete sem,
můžete vyměnit správné hodnoty.

887
00:43:39,170 --> 00:43:42,610
>> Takže když vy jste byli jen mít j
Než jste se nedívali na jednom

888
00:43:42,610 --> 00:43:43,260
po něm.

889
00:43:43,260 --> 00:43:44,520
Vy jste při pohledu na
stejná hodnota, která

890
00:43:44,520 --> 00:43:46,290
je důvod, proč to prostě nic nedělám.

891
00:43:46,290 --> 00:43:49,721
Znamená to, že smysl pro každého,
Proto jsme potřebovali, aby plus 1 tam?

892
00:43:49,721 --> 00:43:50,220
DOBŘE.

893
00:43:50,220 --> 00:43:53,345
Nyní stačí spustit přes něj, aby se
Ujistěte se, že zbytek je kód správný.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Proč se děje, že?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ach, to je min tady.

898
00:44:16,364 --> 00:44:17,780
Byli jsme porovnání nesprávnou hodnotu.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Ale ne.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Ach jo, tady dole jsme byli
vymění nesprávné hodnoty stejně.

903
00:44:33,482 --> 00:44:34,940
Protože jsme se dívali na i a j.

904
00:44:34,940 --> 00:44:36,440
To jsou ty, které jsme kontrolovali.

905
00:44:36,440 --> 00:44:39,160
Vlastně chceme swap
minimum, současná minimální,

906
00:44:39,160 --> 00:44:40,550
s tím, co jeden venku je.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
A jak vy můžete vidět dolů
tady, máme seřazené pole.

909
00:45:05,402 --> 00:45:07,110
Je to prostě musel udělat s
skutečnost, že, když

910
00:45:07,110 --> 00:45:09,350
jsme byli zaškrtnutím
Hodnoty jsme porovnávání

911
00:45:09,350 --> 00:45:11,226
jsme se nedívali na správných hodnotách.

912
00:45:11,226 --> 00:45:13,850
Dívali jsme se na stejné jednom
tady, ne ve skutečnosti ji vyměnit.

913
00:45:13,850 --> 00:45:17,135
Musíte se podívat na ten příští
k ní a pak můžete vyměnit.

914
00:45:17,135 --> 00:45:19,260
Takže to je to, co bylo docela
Před odposlouchávání náš kód.

915
00:45:19,260 --> 00:45:22,460
A to, co tady udělal jsem všechno, co je
ladicí program mohl udělat pro tebe

916
00:45:22,460 --> 00:45:23,810
Jen jsem to udělal na
deska, protože je to jednodušší,

917
00:45:23,810 --> 00:45:26,320
vidět, spíše než se snažit
přiblížíte debuggeru.

918
00:45:26,320 --> 00:45:29,391
Znamená to, že smysl pro všechny?

919
00:45:29,391 --> 00:45:29,890
Bezva.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Dobře.

922
00:45:35,410 --> 00:45:41,070
Můžeme přejít k mluvit o
asymptotické notace, který

923
00:45:41,070 --> 00:45:44,580
je jen fantazie způsob, jak říkat
runtimes všech těchto druhů.

924
00:45:44,580 --> 00:45:47,650
Takže vím, Davida, v přednášce,
dotkla runtime.

925
00:45:47,650 --> 00:45:52,124
A šel přes celý vzorce
o tom, jak vypočítat doby chodu.

926
00:45:52,124 --> 00:45:53,040
Žádné obavy o tom.

927
00:45:53,040 --> 00:45:54,660
Pokud jste opravdu zvědavý
na, jak to funguje,

928
00:45:54,660 --> 00:45:55,810
neváhejte se mnou mluvit po bodu.

929
00:45:55,810 --> 00:45:57,560
Můžeme projít
formule dohromady.

930
00:45:57,560 --> 00:46:00,689
Ale vy všichni kluci mají opravdu
vím, je, že n na druhou nad 2

931
00:46:00,689 --> 00:46:01,980
je totéž jako n na druhou.

932
00:46:01,980 --> 00:46:04,710
Vzhledem k tomu, největšího počtu,
exponent, roste nejvíce.

933
00:46:04,710 --> 00:46:06,590
A tak se pro naše účely,
vše se staráme o

934
00:46:06,590 --> 00:46:09,470
je to, že obří číslo, které roste.

935
00:46:09,470 --> 00:46:13,340
>> Takže to, co je nejlepší případ
runtime výběrového druhu?

936
00:46:13,340 --> 00:46:15,830
Pokud se chystáte mít
iterovat seznamem

937
00:46:15,830 --> 00:46:18,712
a pak iterovat
zbytek tohoto seznamu,

938
00:46:18,712 --> 00:46:20,420
kolikrát jsou
budete pravděpodobně,

939
00:46:20,420 --> 00:46:24,612
v nejhorším case-- v
nejlepším případě, sorry-- proběhnout?

940
00:46:24,612 --> 00:46:27,070
Možná lepší otázka je
se zeptat, co je nejhorší případ

941
00:46:27,070 --> 00:46:28,153
runtime výběrového druhu.

942
00:46:28,153 --> 00:46:29,366
Diváků: n na druhou.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: Je to n na druhou, vpravo.

944
00:46:30,740 --> 00:46:36,986
Tak snadný způsob, jak myslet, je to jako,
kdykoliv budete mít dvou vnořených pro smyčky,

945
00:46:36,986 --> 00:46:38,110
to bude n druhou.

946
00:46:38,110 --> 00:46:40,386
Protože jsou nejen vám
protéká opět,

947
00:46:40,386 --> 00:46:42,260
musíte se vrátit
kolem a skrz ní procházejí

948
00:46:42,260 --> 00:46:44,980
opět dovnitř pro každou hodnotu.

949
00:46:44,980 --> 00:46:48,640
Takže v tomto případě, vedete n
časy n na druhou, což je-- líto,

950
00:46:48,640 --> 00:46:50,505
n krát n, který se rovná n na druhou.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> A druh je také trochu
unikátní v tom smyslu

953
00:46:56,360 --> 00:46:59,774
že nemá-li tyto nevadí
hodnoty jsou již v pořádku.

954
00:46:59,774 --> 00:47:01,440
Je to stále bude proběhnout tak jako tak.

955
00:47:01,440 --> 00:47:03,872
Řekněme, že to bylo 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Bez ohledu na to, zda to bylo v
pořádek, to ještě by proběhl

957
00:47:07,080 --> 00:47:08,620
a ještě zkontroloval minimální hodnotu.

958
00:47:08,620 --> 00:47:10,100
To by dělali
Stejný počet kontrol

959
00:47:10,100 --> 00:47:12,780
pokaždé, i když je
dělal ne vlastně se ničeho dotknout.

960
00:47:12,780 --> 00:47:16,940
>> Takže v tomto případě, že nejlepší a nejhorší
runtime jsou skutečně rovnocenné.

961
00:47:16,940 --> 00:47:19,160
Takže očekávané runtime
výběrového druhu,

962
00:47:19,160 --> 00:47:23,790
které označujeme symbolem
of theta, theta, v tomto případě,

963
00:47:23,790 --> 00:47:24,790
by také bylo n druhou.

964
00:47:24,790 --> 00:47:26,480
Všichni tři z nich by se n druhou.

965
00:47:26,480 --> 00:47:29,653
Je každý jasné, proč
runtime je n na druhou?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Dobře.

968
00:47:33,980 --> 00:47:39,120
Takže já jsem prostě jít rychle spouštět
přes zbytek druhů.

969
00:47:39,120 --> 00:47:41,137
Algoritmus pro
bublina sort-- pamatovat,

970
00:47:41,137 --> 00:47:43,220
to byl první
David přešel na přednášce.

971
00:47:43,220 --> 00:47:46,000
V podstatě si krok
celý seznam

972
00:47:46,000 --> 00:47:48,950
a vy jste právě swap--
Porovnat dvě najednou.

973
00:47:48,950 --> 00:47:51,350
A jestliže jeden je větší,
než jste právě je vyměnit.

974
00:47:51,350 --> 00:47:53,590
Takže pokud jsou větší, měli byste vyměnit.

975
00:47:53,590 --> 00:47:56,180
Mám oficiální tady.

976
00:47:56,180 --> 00:47:59,100
>> Takže řekněme, že jste měli 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Vy byste porovnat 8 a 6.

978
00:48:00,571 --> 00:48:01,570
Vy byste třeba je vyměnit.

979
00:48:01,570 --> 00:48:02,610
Ty by se porovnávat 8 a 4.

980
00:48:02,610 --> 00:48:03,609
Vy byste třeba je vyměnit.

981
00:48:03,609 --> 00:48:07,000
Pokud musíte vyměnit 8 a
je 2, změna je také.

982
00:48:07,000 --> 00:48:10,760
Takže v tom smyslu, můžete vidět,
odehrávající se po dlouhou dobu,

983
00:48:10,760 --> 00:48:13,730
jak hodnoty druh bublinu
konce, což je důvod, proč říkáme

984
00:48:13,730 --> 00:48:15,320
bublinkové řazení.

985
00:48:15,320 --> 00:48:19,950
>> Rádi bychom jen projít znovu
náš druhý průchod, a naše třetí průchod,

986
00:48:19,950 --> 00:48:21,150
a náš čtvrtém průchodu.

987
00:48:21,150 --> 00:48:25,820
V podstatě, bublinkové řazení právě běží
dokud neprovedete žádné další swapy.

988
00:48:25,820 --> 00:48:31,109
Takže v tomto smyslu, je to jen
obecný pseudokód pro něj.

989
00:48:31,109 --> 00:48:32,650
Žádné starosti, to všechno bude on-line.

990
00:48:32,650 --> 00:48:34,990
Nemusíme se vlastně jít přes tento.

991
00:48:34,990 --> 00:48:38,134
>> Právě jsme inicializovat čítač
proměnná, která začíná na 0 ° C.

992
00:48:38,134 --> 00:48:39,800
A my iterovat celé pole.

993
00:48:39,800 --> 00:48:43,420
A pokud jedna hodnota je--, pokud to
hodnota je větší než tato hodnota,

994
00:48:43,420 --> 00:48:44,610
budete se je vyměnit.

995
00:48:44,610 --> 00:48:46,860
A pak jste jen
bude pokračovat.

996
00:48:46,860 --> 00:48:47,970
A budete počítat.

997
00:48:47,970 --> 00:48:50,845
A vy jen tak, aby dělal
to, když probíhá měření, je větší

998
00:48:50,845 --> 00:48:53,345
než 0, což znamená, že
pokaždé, budete muset vyměnit,

999
00:48:53,345 --> 00:48:55,220
víte, že chcete jít
zpět a znovu zkontrolujte.

1000
00:48:55,220 --> 00:48:59,510
Chcete zachovat kontrolu, dokud nebudete vědět
že vy nemusíte vyměnit ještě.

1001
00:48:59,510 --> 00:49:05,570
>> Takže jaké jsou nejlepší a nejhorší
pouzdro běhové moduly pro bubble druhu?

1002
00:49:05,570 --> 00:49:09,300
A hint-- je to vlastně liší
od výběru druhu v tom smyslu,

1003
00:49:09,300 --> 00:49:11,810
že tyto dvě odpovědi nejsou stejné.

1004
00:49:11,810 --> 00:49:14,709
Přemýšlejte o tom, co by se stalo v
případ, pokud to bylo již seřazeny.

1005
00:49:14,709 --> 00:49:16,500
A přemýšlet o tom, co
by se stalo, kdyby to bylo

1006
00:49:16,500 --> 00:49:18,372
v případě, ve kterém nebyla seřazeny.

1007
00:49:18,372 --> 00:49:20,580
A můžete trochu spustit
přes proč se to děje.

1008
00:49:20,580 --> 00:49:22,954
Dám ti kluci, jako, 30
sekund o tom přemýšlet.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> DOBŘE.

1011
00:49:53,540 --> 00:49:57,462
Má někdo uhodnout, co je
Nejhorší případ runtime bublinkové druhu je?

1012
00:49:57,462 --> 00:49:57,962
To jo.

1013
00:49:57,962 --> 00:50:07,810
>> Diváků: Bylo by to, jako, n krát
n minus 1, nebo něco takového?

1014
00:50:07,810 --> 00:50:10,650
Stejně jako pokaždé, když běží,
je to jen, jako, jeden méně odkládací

1015
00:50:10,650 --> 00:50:10,960
že to, co to bylo.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Jo, tak
máš naprostou pravdu.

1017
00:50:12,668 --> 00:50:15,940
A to je případ, kdy vaše
Odpověď byla ve skutečnosti mnohem složitější

1018
00:50:15,940 --> 00:50:17,240
než je ta, kterou je třeba dát.

1019
00:50:17,240 --> 00:50:19,772
Takže to bude run-- Jsem
chystá vymazat všechno tady.

1020
00:50:19,772 --> 00:50:20,480
Jsou všichni dobře?

1021
00:50:20,480 --> 00:50:21,869
Mohu vymazat to?

1022
00:50:21,869 --> 00:50:22,368
DOBŘE.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Budete projít n
Časy se poprvé, že?

1025
00:50:30,320 --> 00:50:33,200
A jdou projít
n minus 1 podruhé, je to tak?

1026
00:50:33,200 --> 00:50:37,130
A pak budete mít
děje, n Mine 2, a tak dále.

1027
00:50:37,130 --> 00:50:40,210
David to udělal v přednášce, kde,
Pokud jste přidali všechny tyto hodnoty,

1028
00:50:40,210 --> 00:50:48,080
dostanete něco, co je jako-- yeah--
nad 2, který v podstatě jen snižuje

1029
00:50:48,080 --> 00:50:49,784
až n na druhou.

1030
00:50:49,784 --> 00:50:51,700
Budeš se dostat
divný frakce tam.

1031
00:50:51,700 --> 00:50:53,892
A tak jen vím, že
n na druhou vždy

1032
00:50:53,892 --> 00:50:55,350
má přednost před frakce.

1033
00:50:55,350 --> 00:50:58,450
A tak v tomto případě, nejhorší
runtime by n druhou.

1034
00:50:58,450 --> 00:51:00,210
Pokud by to bylo v sestupném
objednávka, myslet si,

1035
00:51:00,210 --> 00:51:02,530
muset udělat swap pokaždé.

1036
00:51:02,530 --> 00:51:05,170
>> Jaký by měl být, potenciálně,
nejlepším případě runtime?

1037
00:51:05,170 --> 00:51:08,580
Řekněme, v případě, že seznam byl již
v pořádku, co by runtime být?

1038
00:51:08,580 --> 00:51:09,565
>> Diváků: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: Je to n, přesně tak.

1040
00:51:10,690 --> 00:51:11,600
A proč je to n?

1041
00:51:11,600 --> 00:51:13,850
Diváků: Protože jste právě
muset zkontrolovat každý jednou.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Přesně tak.

1043
00:51:14,770 --> 00:51:17,150
Takže v tom nejlepším možném běhu,
Pokud tento seznam byl již

1044
00:51:17,150 --> 00:51:20,270
sorted-- řekněme 1, 2, 3, 4-- vy
by jen projít, měli byste zkontrolovat,

1045
00:51:20,270 --> 00:51:21,720
byste vidět, oh, všichni vyjít.

1046
00:51:21,720 --> 00:51:22,636
Nemusel jsem se vyměnit.

1047
00:51:22,636 --> 00:51:23,370
Jsem hotov.

1048
00:51:23,370 --> 00:51:26,500
Takže v tomto případě, je to jen n
nebo počet kroků, které právě

1049
00:51:26,500 --> 00:51:29,870
musel zkontrolovat v prvním seznamu.

1050
00:51:29,870 --> 00:51:33,990
>> A poté, co jsme nyní hit
insertion sort, kde

1051
00:51:33,990 --> 00:51:39,260
algoritmus je v podstatě rozdělit
to do tříděného i netříděného část.

1052
00:51:39,260 --> 00:51:42,810
A pak jeden po druhém,
netříděného hodnoty

1053
00:51:42,810 --> 00:51:46,880
vloženy do jejich vhodné
pozice v začátku seznamu.

1054
00:51:46,880 --> 00:51:52,120
>> Tak například, máme
Seznam 3, 5, 2, 6, 4 znovu.

1055
00:51:52,120 --> 00:51:54,750
Víme, že je to v současné době
netříděný proto, že jsme prostě

1056
00:51:54,750 --> 00:51:57,030
začal na to dívat.

1057
00:51:57,030 --> 00:52:00,610
Jsme se podívat, a my víme, že
První hodnota je tříděn, že jo?

1058
00:52:00,610 --> 00:52:04,190
Pokud jste jen při pohledu na řadu
velikost jednoho, víte, že je to třídit.

1059
00:52:04,190 --> 00:52:08,230
>> Takže víme, že
další čtyři jsou netříděný.

1060
00:52:08,230 --> 00:52:10,980
Procházíme a vidíme, že hodnoty.

1061
00:52:10,980 --> 00:52:11,730
Pojďme zpátky.

1062
00:52:11,730 --> 00:52:13,130
Vidíte tu hodnotu 5?

1063
00:52:13,130 --> 00:52:14,110
Podíváme se na to.

1064
00:52:14,110 --> 00:52:15,204
My porovnat ji s 3.

1065
00:52:15,204 --> 00:52:17,870
Víme, že to je větší než
3, takže víme, že to je třídit.

1066
00:52:17,870 --> 00:52:22,940
Takže víme, že první dva
jsou řazeny a poslední tři nejsou.

1067
00:52:22,940 --> 00:52:24,270
>> Jsme se podívat na 2.

1068
00:52:24,270 --> 00:52:25,720
První jsme zkontrolovat s 5.

1069
00:52:25,720 --> 00:52:26,700
Je to méně než 5?

1070
00:52:26,700 --> 00:52:27,240
Není.

1071
00:52:27,240 --> 00:52:29,510
Takže musíme hledat dál dolů.

1072
00:52:29,510 --> 00:52:30,940
Pak můžete zkontrolovat 2 VYP 3.

1073
00:52:30,940 --> 00:52:31,850
Je to méně než?

1074
00:52:31,850 --> 00:52:32,350
Ne.

1075
00:52:32,350 --> 00:52:35,430
Takže víte, 2 musí být vložena
Na přední a 3 a 5

1076
00:52:35,430 --> 00:52:38,200
oba mají být vytlačen.

1077
00:52:38,200 --> 00:52:42,190
Udělejte to opět s 6 a 4.

1078
00:52:42,190 --> 00:52:48,962
A my jsme prostě udržet kontrolu v podstatě,
kde jsme jen zkontrolovat, zkontrolovat, zkontrolovat.

1079
00:52:48,962 --> 00:52:51,170
A dokud to je v právu
postavení, jsme trochu prostě

1080
00:52:51,170 --> 00:52:54,890
vložte ji do správné polohy,
což je místo, kde název pochází.

1081
00:52:54,890 --> 00:52:59,830
>> Tak to je jen algoritmus,
pseudokód per se, druh,

1082
00:52:59,830 --> 00:53:04,990
o tom, jak bychom realizovat
inzerce třídění.

1083
00:53:04,990 --> 00:53:05,954
Pseudokód je tady.

1084
00:53:05,954 --> 00:53:06,620
Je to všechno online.

1085
00:53:06,620 --> 00:53:10,720
Žádné starosti, jestli vy jste
se snaží kopírovat to dolů.

1086
00:53:10,720 --> 00:53:14,500
Takže ještě jednou, co stejný question--
by bylo nejlepší a nejhorší runtime

1087
00:53:14,500 --> 00:53:16,120
vkládání druhu?

1088
00:53:16,120 --> 00:53:17,750
Je to velmi podobné na poslední otázku.

1089
00:53:17,750 --> 00:53:20,479
Dám ti kluci, jako, 30
sekund přemýšlet o tom stejně.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Má někdo chtěl
dej mi nejhorší runtime?

1092
00:53:50,071 --> 00:53:50,570
To jo.

1093
00:53:50,570 --> 00:53:51,490
>> Diváků: n na druhou.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI PENG: Je to n na druhou.

1095
00:53:52,573 --> 00:53:53,730
A proč je to n na druhou?

1096
00:53:53,730 --> 00:53:57,562
>> Publikum: Protože v
obráceném pořadí, máte

1097
00:53:57,562 --> 00:54:02,619
projít n n časy, což je--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Jo, přesně tak.

1099
00:54:03,660 --> 00:54:06,610
Takže to samé jako v bublině druhu.

1100
00:54:06,610 --> 00:54:08,720
Pokud tento seznam je v
sestupném pořadí, ty jsi

1101
00:54:08,720 --> 00:54:11,240
bude muset zkontrolovat první jednou.

1102
00:54:11,240 --> 00:54:13,470
A pak se s každým
další hodnotu, že jste

1103
00:54:13,470 --> 00:54:16,390
muset podívat se na to proti
každý hodnota, je to tak?

1104
00:54:16,390 --> 00:54:20,290
A tak úplně, budete dělat
an časy n přihrávka další n pasu, který

1105
00:54:20,290 --> 00:54:21,750
n je na druhou.

1106
00:54:21,750 --> 00:54:22,860
A co nejlepším případě?

1107
00:54:22,860 --> 00:54:24,360
To jo.

1108
00:54:24,360 --> 00:54:28,840
>> Diváků: n minus 1, protože
První z nich je již na druhou.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Tak blízko.

1110
00:54:30,270 --> 00:54:31,850
Odpověď je vlastně n.

1111
00:54:31,850 --> 00:54:37,189
Vzhledem k tomu, přičemž první z nich je
řazeny, nemusí to actually--

1112
00:54:37,189 --> 00:54:38,980
jsme prostě kliku, v
že příklad, že 2

1113
00:54:38,980 --> 00:54:40,930
se stalo, že je nejmenší číslo.

1114
00:54:40,930 --> 00:54:43,680
Ale to není tak být vždy.

1115
00:54:43,680 --> 00:54:48,040
V případě 2 se již seřazena na začátku
ale vypadáš, a tam je 1 tady,

1116
00:54:48,040 --> 00:54:49,144
1 bude to rána.

1117
00:54:49,144 --> 00:54:51,060
A to skončí
bytí naražený tak jako tak.

1118
00:54:51,060 --> 00:54:56,250
>> Takže v nejlepším případě,
je to vlastně jen bude n.

1119
00:54:56,250 --> 00:54:59,090
Máte-li 1, 2, 3,
4, 5, 6, 7, 8, ty jsi

1120
00:54:59,090 --> 00:55:00,940
se projít
že celý seznam jednou

1121
00:55:00,940 --> 00:55:03,430
zkontrolovat, zda je vše v pořádku.

1122
00:55:03,430 --> 00:55:07,390
Je každý jasno v chodu
časy výběru stejně?

1123
00:55:07,390 --> 00:55:09,960
Já vím, že jsem procházel
ty opravdu rychle.

1124
00:55:09,960 --> 00:55:13,330
Ale vím, že pokud víte,
obecné koncepty, měli byste být dobře.

1125
00:55:13,330 --> 00:55:16,070
DOBŘE.

1126
00:55:16,070 --> 00:55:19,790
Tak jsem si jen dát kluci možná, stejně jako,
minutu se poraďte se svým sousedům

1127
00:55:19,790 --> 00:55:21,890
o tom, co to jsou jen některé
z hlavních rozdílů

1128
00:55:21,890 --> 00:55:23,540
mezi těmito typy druhů.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Půjdeme přes to brzy.

1131
00:56:25,570 --> 00:56:26,444
Publikum: Oh, OK.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Jo.

1133
00:56:27,320 --> 00:56:28,380
DOBŘE.

1134
00:56:28,380 --> 00:56:33,420
Cool, pojďme znovu sejdou jako třída.

1135
00:56:33,420 --> 00:56:34,330
DOBŘE.

1136
00:56:34,330 --> 00:56:37,579
Takže to bylo docela
otevřená otázka v tom smyslu,

1137
00:56:37,579 --> 00:56:39,120
že je tu spousta odpovědí na ně.

1138
00:56:39,120 --> 00:56:40,746
A půjdeme přes některé z nich stručně.

1139
00:56:40,746 --> 00:56:43,411
Chtěl jsem, aby vám kluci
přemýšlet o tom, co diferencované

1140
00:56:43,411 --> 00:56:44,530
všechny tři typy druhů.

1141
00:56:44,530 --> 00:56:47,440
A já jsem slyšel také, velký
question-- co merge sort dělat?

1142
00:56:47,440 --> 00:56:50,110
Výborná otázka, protože to je
to, co jsme pokrývat další.

1143
00:56:50,110 --> 00:56:52,850
>> Tak sloučit sort
člověk druh, který funguje

1144
00:56:52,850 --> 00:56:56,100
velmi odlišně od ostatních druhů.

1145
00:56:56,100 --> 00:56:58,180
Jak vy můžete see--
David udělal, že demo

1146
00:56:58,180 --> 00:57:01,130
kde měl všechno v pohodě
zvuky když vidí, jak sloučit

1147
00:57:01,130 --> 00:57:04,010
třídění běžel, jako, nekonečně
rychleji, než ostatní dva typy?

1148
00:57:04,010 --> 00:57:04,510
DOBŘE.

1149
00:57:04,510 --> 00:57:07,580
Tak to je proto, že sloučení
třídit implementuje, které rozdělují

1150
00:57:07,580 --> 00:57:11,020
a podmanit si představu, že jsme
mluvil o hodně v přednášce.

1151
00:57:11,020 --> 00:57:14,550
V tom smyslu, že jsme chtěli pracovat
chytřejší, ne těžší, když jste rozdělit

1152
00:57:14,550 --> 00:57:18,120
a podmanit si problémy, a rozdělují je
dolů, a pak dát dohromady,

1153
00:57:18,120 --> 00:57:19,930
dobré věci se vždycky stane.

1154
00:57:19,930 --> 00:57:21,960
>> Tak tak, že sloučení
sort v podstatě funguje

1155
00:57:21,960 --> 00:57:24,660
je, že se rozděluje
netříděné pole na polovinu.

1156
00:57:24,660 --> 00:57:26,500
A pak to má dvě poloviny polí.

1157
00:57:26,500 --> 00:57:28,220
A to jen třídí tyto dvě poloviny.

1158
00:57:28,220 --> 00:57:31,750
Je to prostě pořád dělení na polovinu, v
polovina, v polovině dokud vše je řazen

1159
00:57:31,750 --> 00:57:33,680
a pak rekurzivně
dává to všechno dohromady.

1160
00:57:33,680 --> 00:57:36,550
>> Tak to je opravdu abstraktní.

1161
00:57:36,550 --> 00:57:38,750
Tak to je jen trochu pseudokódu.

1162
00:57:38,750 --> 00:57:41,040
Znamená to, že smysl v
jak to běží?

1163
00:57:41,040 --> 00:57:43,870
Takže řekněme, že máte
pole n elementy, že jo?

1164
00:57:43,870 --> 00:57:45,450
Pokud n je menší než 2, můžete se vrátit.

1165
00:57:45,450 --> 00:57:49,040
Vzhledem k tomu, víte, že jestli existuje
jen jedna věc, musí být řazeny.

1166
00:57:49,040 --> 00:57:52,600
Else, řadit levou polovinu,
a pak řadit pravou polovinu,

1167
00:57:52,600 --> 00:57:54,140
a pak sloučit.

1168
00:57:54,140 --> 00:57:56,979
>> Takže zatímco to vypadá velmi jednoduché,
ve skutečnosti, přemýšlel o tom to

1169
00:57:56,979 --> 00:58:00,270
trochu obtížné. Vzhledem k tomu, že jste rád,
No, to je trochu běh na sebe.

1170
00:58:00,270 --> 00:58:00,769
Je to tak?

1171
00:58:00,769 --> 00:58:02,430
Je to běh na sebe.

1172
00:58:02,430 --> 00:58:05,479
Takže v tomto smyslu, David dotkl
při rekurzi ve třídě.

1173
00:58:05,479 --> 00:58:07,270
A to je pojem
budeme mluvit o víc.

1174
00:58:07,270 --> 00:58:11,430
Je to, že toto, tyto dvě linky
Zde, ve skutečnosti je jen program

1175
00:58:11,430 --> 00:58:13,860
říkat, aby se spouštěl sám
s různým vstupem.

1176
00:58:13,860 --> 00:58:17,230
Takže spíše než běžet sebe s
celistvost n elementy,

1177
00:58:17,230 --> 00:58:20,530
můžete zlomit to do
levou polovinu a pravá polovina

1178
00:58:20,530 --> 00:58:22,680
a spusťte jej znovu.

1179
00:58:22,680 --> 00:58:26,050
>> A pak se podíváme na to vizuálně,
proto, že jsem vizuální žák.

1180
00:58:26,050 --> 00:58:27,270
Funguje to pro mě lepší.

1181
00:58:27,270 --> 00:58:29,890
Takže se podíváme na vizuální příklad zde.

1182
00:58:29,890 --> 00:58:36,237
>> Řekněme, že máme celou řadu, šest
prvky, 3, 5, 2, 6, 4, 1, nejsou tříděny.

1183
00:58:36,237 --> 00:58:37,820
Dobře, je tu hodně na této stránce.

1184
00:58:37,820 --> 00:58:43,179
Takže pokud vy můžete podívat na
První krok se zde, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
můžete rozdělit jej na polovinu.

1186
00:58:44,220 --> 00:58:45,976
Máte 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Víte, že tyto aren't-- vás
Nevím, jestli jsou řazeny, nebo ne,

1188
00:58:48,850 --> 00:58:52,517
takže si udržet lámání je dolů, na polovinu,
na polovinu, na polovinu, až nakonec,

1189
00:58:52,517 --> 00:58:53,600
máte jen jeden prvek.

1190
00:58:53,600 --> 00:58:56,790
A jeden prvek je vždy řazeny, že jo?

1191
00:58:56,790 --> 00:59:01,560
>> Takže víme, že 3, 5, 2, 4, 6,
1 samy o sobě, jsou seřazeny.

1192
00:59:01,560 --> 00:59:05,870
A teď můžeme dát je dohromady.

1193
00:59:05,870 --> 00:59:07,510
Takže víme, na 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Dali jsme dohromady ty.

1195
00:59:08,510 --> 00:59:09,617
Víme, že je to třídit.

1196
00:59:09,617 --> 00:59:10,450
Na 2 je tam pořád.

1197
00:59:10,450 --> 00:59:11,830
Můžeme dát 4 a 6 dohromady.

1198
00:59:11,830 --> 00:59:13,996
Víme, že to je seřazena,
tak jsme dali, že společně.

1199
00:59:13,996 --> 00:59:14,940
A 1 je tam.

1200
00:59:14,940 --> 00:59:18,720
>> A pak se stačí podívat se na
tyto dvě poloviny tady.

1201
00:59:18,720 --> 00:59:21,300
Máte 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Jen si můžete porovnat
začátek všeho.

1203
00:59:23,465 --> 00:59:26,340
Vzhledem k tomu, víte, že to je řazen
a víte, že to je třídit.

1204
00:59:26,340 --> 00:59:29,360
Takže vy nemusíte ani na
porovnat 5, stačí porovnat 3.

1205
00:59:29,360 --> 00:59:32,070
A 2 je menší než 3, takže
Víte 2 musí jít na konci.

1206
00:59:32,070 --> 00:59:33,120
>> Totéž tam.

1207
00:59:33,120 --> 00:59:34,740
1 musí jít sem.

1208
00:59:34,740 --> 00:59:37,330
A pak, když jdete dát
tyto dvě hodnoty dohromady,

1209
00:59:37,330 --> 00:59:39,950
víte, že to je seřazena a
víte, že je tříděn.

1210
00:59:39,950 --> 00:59:43,240
Takže pak 1 a
2 je 1 je menší než 2.

1211
00:59:43,240 --> 00:59:45,570
To vám řekne, že 1
by měl jít na konci tohoto

1212
00:59:45,570 --> 00:59:47,480
aniž by při pohledu na 3 nebo 5.

1213
00:59:47,480 --> 00:59:50,100
A pak na 4, můžete jen
zkontrolujte, že jde přímo tady.

1214
00:59:50,100 --> 00:59:51,480
Nemusíte se podívat na 5.

1215
00:59:51,480 --> 00:59:52,570
Totéž se 6.

1216
00:59:52,570 --> 00:59:55,860
Víte, že to prostě 6--
nemusí být díval.

1217
00:59:55,860 --> 00:59:57,870
>> A tak se tímto způsobem, jste
jen ukládání sami

1218
00:59:57,870 --> 00:59:59,526
hodně kroků, když jste porovnávání.

1219
00:59:59,526 --> 01:00:02,150
Nemusíte porovnat každý
prvek s jinými prvky.

1220
01:00:02,150 --> 01:00:05,230
Právě jste porovnat proti těm,
že musíte porovnat ji proti.

1221
01:00:05,230 --> 01:00:06,870
Tak to je trochu abstraktní pojem.

1222
01:00:06,870 --> 01:00:10,540
Žádné starosti, pokud to není
docela tě bít ještě v pořádku.

1223
01:00:10,540 --> 01:00:14,740
Ale obecně, to je
jak sloučení třídění funguje.

1224
01:00:14,740 --> 01:00:17,750
Otázky, rychlých otázek,
Než jsem se přesunout na?

1225
01:00:17,750 --> 01:00:18,550
To jo.

1226
01:00:18,550 --> 01:00:22,230
>> Diváků: Takže jste řekl, že jste užil
polohách 1, a pak 4 a 6

1227
01:00:22,230 --> 01:00:23,860
a dát je do.

1228
01:00:23,860 --> 01:00:26,800
Takže nejsou those-- nejsou
Díváte se na ně

1229
01:00:26,800 --> 01:00:28,544
jako samostatné prvky, ne jako celku?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Jo.

1231
01:00:29,210 --> 01:00:32,020
Takže to, co se děje
je to, že jste v podstatě

1232
01:00:32,020 --> 01:00:33,650
vytvářejí zcela nové pole.

1233
01:00:33,650 --> 01:00:36,690
Takže víte, že tady, mám
dvě pole o velikosti 3, ne?

1234
01:00:36,690 --> 01:00:39,600
Takže víte, že můj tříděného array
musí mít šest prvků.

1235
01:00:39,600 --> 01:00:42,270
Takže si stačí vytvořit
nová množství paměti.

1236
01:00:42,270 --> 01:00:44,270
Takže jste něco jako
že plýtvání paměti,

1237
01:00:44,270 --> 01:00:46,186
ale to nevadí,
protože je to tak malý.

1238
01:00:46,186 --> 01:00:48,590
Takže se podívat na 1
a se podíváte na 2.

1239
01:00:48,590 --> 01:00:50,770
A víte, že 1 je menší než 2.

1240
01:00:50,770 --> 01:00:53,840
Takže víte, že 1 by měl jít do
počátek všech z nich.

1241
01:00:53,840 --> 01:00:55,850
>> Nemusíte ani potřeba
podívejte se na 3 a 5.

1242
01:00:55,850 --> 01:00:57,400
Takže víte 1 je tam.

1243
01:00:57,400 --> 01:00:59,300
Pak jste v podstatě useknu na 1.

1244
01:00:59,300 --> 01:01:00,370
Je to, jako, mrtvý k nám.

1245
01:01:00,370 --> 01:01:03,690
Pak jsme prostě 2,
3, 5, a pak se 4 a 6.

1246
01:01:03,690 --> 01:01:06,270
A pak víte, že, vás
porovnat 4 a 2,

1247
01:01:06,270 --> 01:01:07,560
Ach, ta 2 by mělo jít tam.

1248
01:01:07,560 --> 01:01:09,685
Takže jste plop na 2 dolů, si nakrájíme ho.

1249
01:01:09,685 --> 01:01:12,060
Takže stačí mít 3
a 5 v 4 a 6.

1250
01:01:12,060 --> 01:01:14,650
A vy jste jen držet sekání ho
dokud se dát je v poli.

1251
01:01:14,650 --> 01:01:17,110
>> Diváků: Takže jste jen vždy
porovnání [neslyšitelných]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Přesně tak.

1253
01:01:17,710 --> 01:01:19,590
Takže v tomto smyslu, že jste
jen porovnání, v podstatě,

1254
01:01:19,590 --> 01:01:21,240
jedno číslo proti jiné číslo.

1255
01:01:21,240 --> 01:01:22,990
A protože víte,
že to řazeny, vás

1256
01:01:22,990 --> 01:01:24,350
Nemusíte se dívat skrz
všechna čísla.

1257
01:01:24,350 --> 01:01:25,870
Stačí se jen podívat na první z nich.

1258
01:01:25,870 --> 01:01:27,582
A pak se můžete jen plop
je dolů, protože víte,

1259
01:01:27,582 --> 01:01:29,640
oni patří tam, kam potřebují patřit.

1260
01:01:29,640 --> 01:01:31,030
To jo.

1261
01:01:31,030 --> 01:01:32,920
Dobrá otázka.

1262
01:01:32,920 --> 01:01:35,290
>> A pak, pokud někdo z vás
jsou trochu ambiciózní,

1263
01:01:35,290 --> 01:01:38,660
neváhejte se podívat na tento kód.

1264
01:01:38,660 --> 01:01:40,680
To je vlastně
fyzická realizace

1265
01:01:40,680 --> 01:01:42,150
o tom, jak bychom napsat merge sort.

1266
01:01:42,150 --> 01:01:44,070
A můžete vidět, že je to velmi krátká.

1267
01:01:44,070 --> 01:01:46,310
Ale nápady za
to jsou docela složité.

1268
01:01:46,310 --> 01:01:50,865
Takže pokud máte pocit, jako kreslení na to
ve své domácí úkoly dnes večer, neváhejte.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> DOBŘE.

1271
01:01:54,740 --> 01:01:58,070
Tak i David přešel toto v přednášce.

1272
01:01:58,070 --> 01:02:00,660
Jaké jsou nejlepší věc
runtime, nejhorší případ runtimes,

1273
01:02:00,660 --> 01:02:05,680
a očekávané runtimes korespondence druhu?

1274
01:02:05,680 --> 01:02:07,260
Pár vteřin přemýšlet.

1275
01:02:07,260 --> 01:02:11,198
To je docela těžké, ale druh
intuitivní, pokud si myslíte o tom.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Dobře.

1278
01:02:23,054 --> 01:02:25,269
>> Diváků: Je nejhorší případ n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Přesně tak.

1280
01:02:26,060 --> 01:02:29,380
A proč je to n log n.

1281
01:02:29,380 --> 01:02:32,230
>> Diváků: Není to proto, že
se stává exponenciálně rychlejší,

1282
01:02:32,230 --> 01:02:35,390
takže je to jako funkci, která
ne jen prostě být n

1283
01:02:35,390 --> 01:02:37,529
na druhou, nebo tak něco?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Přesně tak.

1285
01:02:38,320 --> 01:02:40,750
Takže důvod, proč
runtime v této oblasti je n log

1286
01:02:40,750 --> 01:02:44,310
n je protože-- to, co jste
dělá ve všech těchto kroků?

1287
01:02:44,310 --> 01:02:46,190
Jenom sekání jej v polovině, že jo?

1288
01:02:46,190 --> 01:02:48,750
A tak, když děláme
log, vše, co to dělá

1289
01:02:48,750 --> 01:02:53,150
rozděluje problém na polovinu,
na polovinu, na polovinu, ve více poloviny.

1290
01:02:53,150 --> 01:02:56,430
A v tomto smyslu, můžete druh
z eliminovat lineární model

1291
01:02:56,430 --> 01:02:57,510
že jsme používali.

1292
01:02:57,510 --> 01:03:00,254
Protože když si nakrájíme
věci v polovině, je to protokol.

1293
01:03:00,254 --> 01:03:02,420
To je jen matematický
způsob, jak reprezentovat to.

1294
01:03:02,420 --> 01:03:06,310
>> A pak konečně, na konci, jste
jen aby jeden poslední průchod

1295
01:03:06,310 --> 01:03:07,930
dát všechny z nich v pořádku, ne?

1296
01:03:07,930 --> 01:03:10,330
A tak, když stačí, aby
zkontrolovat jednu věc, to je n.

1297
01:03:10,330 --> 01:03:13,420
A tak jste trochu
vynásobením dva spolu.

1298
01:03:13,420 --> 01:03:17,660
Takže je to jako, že máš, že konečné
zkontrolujte, zda n tady s log n

1299
01:03:17,660 --> 01:03:18,390
tady.

1300
01:03:18,390 --> 01:03:21,060
A pokud se množit
je, že je n log n.

1301
01:03:21,060 --> 01:03:26,100
>> A tak to nejlepší a nejhorší případ
případ, a očekává, že jsou všichni n log n.

1302
01:03:26,100 --> 01:03:27,943
Je to také jako jiného druhu.

1303
01:03:27,943 --> 01:03:30,090
Je to jako výběr druhu
v tom smyslu, že

1304
01:03:30,090 --> 01:03:32,131
Nezáleží na tom, jaké jsou vaše
Seznam je, je to jen bude

1305
01:03:32,131 --> 01:03:34,801
se udělat totéž pokaždé.

1306
01:03:34,801 --> 01:03:35,300
DOBŘE.

1307
01:03:35,300 --> 01:03:39,950
Tak jako vy můžete vidět, i když
že druhy, které jsme pryč through-- n

1308
01:03:39,950 --> 01:03:41,660
čtvercový, to není moc efektivní.

1309
01:03:41,660 --> 01:03:47,060
A i to n log n je
není nejúčinnější.

1310
01:03:47,060 --> 01:03:49,720
Jestliže vy jste zvědaví,
tam je řazení mechanismy,

1311
01:03:49,720 --> 01:03:54,310
že jsou tak účinné, že jsou
Téměř v podstatě byt v běhu.

1312
01:03:54,310 --> 01:03:55,420
>> Máte nějaký protokol n je.

1313
01:03:55,420 --> 01:03:58,190
Máte nějaké log log n je.

1314
01:03:58,190 --> 01:04:00,330
My nedotýkejte se na ně
v této třídě právě teď.

1315
01:04:00,330 --> 01:04:02,663
Ale pokud vy jste zvědaví,
neváhejte google, co je

1316
01:04:02,663 --> 01:04:04,392
nejvýkonnější třídicí mechanismy.

1317
01:04:04,392 --> 01:04:06,350
Já nevím, existují
někteří z nich opravdu k smíchu,

1318
01:04:06,350 --> 01:04:09,860
jako-- tam je nějaké opravdu
legrační ty, které lidé dělají.

1319
01:04:09,860 --> 01:04:12,210
A vy jste věděl, jak by
vůbec nenapadlo.

1320
01:04:12,210 --> 01:04:15,730
Takže google, pokud máte trochu volného
čas, na to, co jsou některé vtipné způsoby,

1321
01:04:15,730 --> 01:04:17,730
že people-- jakož i
efektivní ways-- lidé

1322
01:04:17,730 --> 01:04:20,371
byli schopni realizovat nejrůznější.

1323
01:04:20,371 --> 01:04:20,870
DOBŘE.

1324
01:04:20,870 --> 01:04:22,880
A tady je jen šikovný malý graf.

1325
01:04:22,880 --> 01:04:26,850
Vím, že vás všechny, před tímto kvízu 0,
bude ve vašem pokoji pravděpodobně snaží

1326
01:04:26,850 --> 01:04:27,960
zapamatovat to.

1327
01:04:27,960 --> 01:04:30,940
Tak to je hezké tam pro vás.

1328
01:04:30,940 --> 01:04:37,120
Jen nezapomeňte na logiku, která made--
proč tyto čísla byla vyskytující.

1329
01:04:37,120 --> 01:04:39,870
Pokud jste vždy prohrál, jen aby
jisti, že víte, co druhy jsou.

1330
01:04:39,870 --> 01:04:40,820
A můžete projít
je ve vaší mysli

1331
01:04:40,820 --> 01:04:42,903
přijít na to, proč ti,
Odpovědi jsou tyto odpovědi.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Dobře.

1334
01:04:47,600 --> 01:04:49,680
Takže budeme pohybovat
na, konečně, na vyhledávání.

1335
01:04:49,680 --> 01:04:51,638
Vzhledem k tomu, jak ti z vás,
kteří po přečtení pset,

1336
01:04:51,638 --> 01:04:55,175
Vyhledávání je také součástí
tento týden problém sady.

1337
01:04:55,175 --> 01:04:57,300
Budete vyzváni k implementaci
dva typy vyhledávání.

1338
01:04:57,300 --> 01:05:00,070
Jedním z nich je lineární vyhledávání a
jeden je binární vyhledávání.

1339
01:05:00,070 --> 01:05:01,760
>> Takže lineární hledání je poměrně snadné.

1340
01:05:01,760 --> 01:05:04,070
Jen chcete hledat prvek
ze seznamu, zda jste to.

1341
01:05:04,070 --> 01:05:05,444
Musíte jen iterovat.

1342
01:05:05,444 --> 01:05:08,170
A když se rovná něco,
stačí vrátit, ne?

1343
01:05:08,170 --> 01:05:10,890
Ale ten, který jsme nejvíce
zájem mluvit o

1344
01:05:10,890 --> 01:05:14,550
je binární vyhledávání, vpravo, což je
rozděl a panuj mechanismus, který

1345
01:05:14,550 --> 01:05:18,190
David demonstroval v přednášce.

1346
01:05:18,190 --> 01:05:20,810
>> Vzpomeňte si na telefonní seznam příklad
že se stále vychovávat,

1347
01:05:20,810 --> 01:05:23,960
ten, že se druh snažil
trochu na tento poslední rok,

1348
01:05:23,960 --> 01:05:27,530
kde rozdělit problém na polovinu,
na polovinu, na polovinu, znovu a znovu,

1349
01:05:27,530 --> 01:05:30,730
dokud nenajdete to, co hledáte?

1350
01:05:30,730 --> 01:05:33,727
A vy jste dostal
runtime of že stejně.

1351
01:05:33,727 --> 01:05:35,810
A můžete vidět, je to
významně účinnější

1352
01:05:35,810 --> 01:05:39,080
než jakýkoli jiný typ vyhledávání.

1353
01:05:39,080 --> 01:05:41,880
>> Takže způsob, jakým bychom jít o
provádění binárního vyhledávání

1354
01:05:41,880 --> 01:05:46,510
je, pokud bychom měli pole,
index 0 až 6, sedm prvky,

1355
01:05:46,510 --> 01:05:49,790
se můžeme podívat ve středu, right--
Omlouvám se, pokud náš dotaz first--

1356
01:05:49,790 --> 01:05:53,840
chceme-li položit otázku, dělá
pole obsahují prvek 7,

1357
01:05:53,840 --> 01:05:56,840
Je zřejmé, že jsou lidi, a mající
taková malá pole, je to pro nás snadné

1358
01:05:56,840 --> 01:05:58,210
říct ano.

1359
01:05:58,210 --> 01:06:05,750
Ale způsob realizovat binární
Hledání by se podívat do středu.

1360
01:06:05,750 --> 01:06:08,020
>> Víme, že index 3
prostřední, protože my

1361
01:06:08,020 --> 01:06:09,270
vím, je jich tam sedm prvky.

1362
01:06:09,270 --> 01:06:10,670
Jaké 7 děleno 2?

1363
01:06:10,670 --> 01:06:12,850
Můžete utnout, které navíc 1.

1364
01:06:12,850 --> 01:06:14,850
Máte 3 ve středu.

1365
01:06:14,850 --> 01:06:17,590
Tak je pole 3 rovna 7?

1366
01:06:17,590 --> 01:06:18,900
To není, že jo?

1367
01:06:18,900 --> 01:06:21,050
Ale můžeme udělat pár kontrol.

1368
01:06:21,050 --> 01:06:25,380
Je pole 3 menší než 7, nebo
je pole 3 větší než 7?

1369
01:06:25,380 --> 01:06:27,240
>> A my víme, že je to méně než 7.

1370
01:06:27,240 --> 01:06:30,259
Takže víme, že, oh, to musí
nemusí být v levé polovině.

1371
01:06:30,259 --> 01:06:32,300
Víme, že to musí být
v pravé polovině, že jo?

1372
01:06:32,300 --> 01:06:34,662
Takže můžeme jen utnout polovinu pole.

1373
01:06:34,662 --> 01:06:36,370
Nemáme dokonce ani
podívej se na to ještě.

1374
01:06:36,370 --> 01:06:38,711
Protože víme, že
polovina naší problem--

1375
01:06:38,711 --> 01:06:41,210
víme, že odpověď je v
pravá polovina našeho problému.

1376
01:06:41,210 --> 01:06:42,580
Tak jsme se jen podívat na to teď.

1377
01:06:42,580 --> 01:06:44,860
>> Takže teď jsme se podívat na
Uprostřed toho, co zbylo.

1378
01:06:44,860 --> 01:06:46,880
To index 5.

1379
01:06:46,880 --> 01:06:50,200
Děláme stejnou kontrolu znovu
a vidíme, že je to menší.

1380
01:06:50,200 --> 01:06:52,050
Takže se podíváme na levé straně to.

1381
01:06:52,050 --> 01:06:53,430
A pak vidíme, ten šek.

1382
01:06:53,430 --> 01:06:57,600
Je hodnota pole v
index 4 rovna 7?

1383
01:06:57,600 --> 01:06:58,260
To je.

1384
01:06:58,260 --> 01:07:03,580
Takže se můžeme vrátit pravda, protože
jsme zjistili, že hodnotu v našem seznamu.

1385
01:07:03,580 --> 01:07:06,738
Má tak, jak jsem šel přes
že smysl pro všechny?

1386
01:07:06,738 --> 01:07:08,760
DOBŘE.

1387
01:07:08,760 --> 01:07:11,670
Dám ti kluci možná, stejně jako,
tři, čtyři minuty přijít na to,

1388
01:07:11,670 --> 01:07:13,270
jak se to v pseudokódu.

1389
01:07:13,270 --> 01:07:18,070
>> Tak si představte jsem vás požádal, abyste napsat
Funkce tzv search (), který se vrátil

1390
01:07:18,070 --> 01:07:20,640
hodnotu, logickou hodnotu,
to byla pravda nebo false-- podobně,

1391
01:07:20,640 --> 01:07:22,970
true, pokud jste našli
hodnota, false, pokud jste to neudělali.

1392
01:07:22,970 --> 01:07:25,230
A pak jste byli
prošel v hodnoty, kterou

1393
01:07:25,230 --> 01:07:28,410
Hledali do hodnot, které
je array-- oh, rozhodně jsem dal

1394
01:07:28,410 --> 01:07:29,410
že na špatném místě.

1395
01:07:29,410 --> 01:07:29,580
DOBŘE.

1396
01:07:29,580 --> 01:07:31,829
Tak jako tak, že by měl mít
bylo na pravé straně hodnot.

1397
01:07:31,829 --> 01:07:36,280
A pak int n je číslo
prvků v tomto poli.

1398
01:07:36,280 --> 01:07:39,430
Jak byste jít o snaze
pseudokódu tento problém v?

1399
01:07:39,430 --> 01:07:41,630
Dám se vám bude líbit
tři minuty na to.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Ne, myslím, že je only--
jo, je tu ještě jedna přímo tady.

1402
01:08:02,595 --> 01:08:03,261
Diváků: Mohu?

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Jo, mám tě.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Je to pracovní?

1406
01:08:11,050 --> 01:08:12,290
OK v pohodě.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> DOBŘE.

1409
01:10:44,720 --> 01:10:47,630
Tak jo chlapi, my jsme
bude udržet na uzdě ho.

1410
01:10:47,630 --> 01:10:49,730
DOBŘE.

1411
01:10:49,730 --> 01:10:54,020
Takže předpokládáme, máme tento krásný
malá pole s n hodnot v něm.

1412
01:10:54,020 --> 01:10:55,170
Nechtěl jsem kreslit čáry.

1413
01:10:55,170 --> 01:10:58,649
Ale jak bychom jít o
snaží psát to?

1414
01:10:58,649 --> 01:11:00,440
Má někdo chtěl
dej mi první řádek?

1415
01:11:00,440 --> 01:11:02,814
Chcete-li mi dát
První řádek tohoto pseudokódu.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> Diváků: [Neslyšitelné]

1418
01:11:08,430 --> 01:11:10,138
Diváků: byste chtěli
přecházet through--

1419
01:11:10,138 --> 01:11:11,094
Diváků: Jen další pro smyčce?

1420
01:11:11,094 --> 01:11:11,760
Diváků: --for.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Tak tohle je trochu složitější.

1423
01:11:17,780 --> 01:11:23,130
Myslíš, že about-- chcete
se udržují v provozu této smyčky

1424
01:11:23,130 --> 01:11:27,950
znovu a znovu, do kdy?

1425
01:11:27,950 --> 01:11:30,819
>> Diváků: Do [neslyšitelných]
hodnota se rovná této hodnotě.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Přesně tak.

1427
01:11:31,610 --> 01:11:33,900
Takže můžete vlastně jen write--
můžeme ještě zjednodušit ji víc.

1428
01:11:33,900 --> 01:11:35,630
Můžeme jen dělat while, že jo?

1429
01:11:35,630 --> 01:11:39,380
Takže můžete mít jen loop--
víme, že je to za to.

1430
01:11:39,380 --> 01:11:42,850
Ale právě teď, jdu
říkat "smyčka" - tím, co?

1431
01:11:42,850 --> 01:11:46,640
Loop until-- co je
náš ukončení stavu?

1432
01:11:46,640 --> 01:11:47,510
Myslím, že jsem to slyšela.

1433
01:11:47,510 --> 01:11:48,530
Slyšel jsem, někdo to říct.

1434
01:11:48,530 --> 01:11:51,255
>> Diváků: Hodnoty se rovná střed.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: Řekni to znovu.

1436
01:11:52,255 --> 01:11:54,470
Publikum: Anebo, dokud se
Hodnota, kterou hledáte

1437
01:11:54,470 --> 01:11:58,470
k je rovna střední hodnotě.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Co když to není tam?

1439
01:12:00,280 --> 01:12:03,113
Co když je hodnota hledáte
pro není vlastně v tomto poli?

1440
01:12:03,113 --> 01:12:05,890
Diváků: Vrátíte 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Ale to, co chceme
smyčky, až když máme stav?

1442
01:12:08,850 --> 01:12:09,350
To jo.

1443
01:12:09,350 --> 01:12:11,239
>> Diváků: Dokud je tu jen jedna hodnota?

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: Můžete smyčka
until-- takže víte, že jste

1445
01:12:13,530 --> 01:12:15,714
bude mít maximální hodnotu, je to tak?

1446
01:12:15,714 --> 01:12:18,130
A víte, že budete
mít hodnotu min, že jo?

1447
01:12:18,130 --> 01:12:20,379
Vzhledem k tomu také, to je něco,
Zapomněl jsem říci předtím,

1448
01:12:20,379 --> 01:12:22,640
že něco, co je
kriticky binární vyhledávání

1449
01:12:22,640 --> 01:12:24,182
je, že vaše pole je již řazeno.

1450
01:12:24,182 --> 01:12:26,973
Protože neexistuje žádný způsob, jak dělat
, pokud jsou to jen náhodné hodnoty.

1451
01:12:26,973 --> 01:12:29,190
Nevíte, pokud je to
větší než ostatní, ne?

1452
01:12:29,190 --> 01:12:32,720
>> Takže víte, že vaše maximální a
Vaše min tady, ne?

1453
01:12:32,720 --> 01:12:35,590
Pokud bude nastavení
Váš max ve vašich minut a mid--

1454
01:12:35,590 --> 01:12:38,470
ať to jen předpokládat
střední hodnota je správné here--

1455
01:12:38,470 --> 01:12:43,910
budete v podstatě
smyčka dokud je minimum

1456
01:12:43,910 --> 01:12:47,510
zhruba stejný jako max, vpravo, nebo
pokud vaše maximální není stejný jako min.

1457
01:12:47,510 --> 01:12:48,040
Je to tak?

1458
01:12:48,040 --> 01:12:51,340
Vzhledem k tomu, když se to stane, víte, že
že jste nakonec narazila na stejnou hodnotu.

1459
01:12:51,340 --> 01:12:59,135
Takže chcete, aby smyčce, dokud vaší min
je menší nebo roven to-- oops,

1460
01:12:59,135 --> 01:13:01,510
ne méně než nebo rovno,
na druhou stranu around-- Max.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Věděli, že smysl?

1463
01:13:16,160 --> 01:13:18,810
Vzal jsem několik pokusů dostat toto právo.

1464
01:13:18,810 --> 01:13:21,869
Ale smyčka, dokud vaše maximální hodnoty
je v podstatě téměř nižší

1465
01:13:21,869 --> 01:13:23,410
než nebo rovna vaší minimum, že jo?

1466
01:13:23,410 --> 01:13:25,201
To je, když víte,
že jste se sblížil.

1467
01:13:25,201 --> 01:13:29,290
Diváků: Pokud by vaše maximální
hodnota byla nižší, než je minimum?

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Pokud se budete držet
upraví jej, což

1469
01:13:31,040 --> 01:13:32,380
je to, co se chystáme
je třeba dělat v tomto.

1470
01:13:32,380 --> 01:13:33,460
Dává to smysl?

1471
01:13:33,460 --> 01:13:35,750
Minimální a max jsou jen
celá čísla, že jsme pravděpodobně

1472
01:13:35,750 --> 01:13:39,260
bude chtít vytvořit, aby
trať, kde se díváme.

1473
01:13:39,260 --> 01:13:41,790
Vzhledem k tomu, pole existuje
bez ohledu na to, co děláme.

1474
01:13:41,790 --> 01:13:45,030
Stejně jako, nejsme ve skutečnosti fyzicky
sekání mimo pole, ne?

1475
01:13:45,030 --> 01:13:47,261
Jsme jen nastavení
kde se díváme.

1476
01:13:47,261 --> 01:13:48,136
Dává to smysl?

1477
01:13:48,136 --> 01:13:48,472
>> Diváků: Jo.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Takže pokud to je podmínka pro naše smyčku,
to, co chceme v této smyčky?

1480
01:13:57,090 --> 01:13:58,700
Co budeme se chtít dělat?

1481
01:13:58,700 --> 01:14:02,390
Takže teď, máme
max a min, pravý,

1482
01:14:02,390 --> 01:14:04,962
pravděpodobně vytvořil tady někde.

1483
01:14:04,962 --> 01:14:07,170
Budeme chtít
najít střední, že jo?

1484
01:14:07,170 --> 01:14:08,450
Jak jsme bude
schopen najít uprostřed?

1485
01:14:08,450 --> 01:14:09,491
Co je mathematical--

1486
01:14:09,491 --> 01:14:11,079
Diváků: Max a min děleným 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Přesně tak.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Dává to smysl?

1490
01:14:21,620 --> 01:14:25,780
A to vy, proč bychom
nebyl jen use--, proč jsme to udělali

1491
01:14:25,780 --> 01:14:27,850
místo toho dělá jen n děleno 2?

1492
01:14:27,850 --> 01:14:30,310
Je to proto, že n je hodnota
že to bude zůstat stejné.

1493
01:14:30,310 --> 01:14:30,979
Je to tak?

1494
01:14:30,979 --> 01:14:34,020
Ale jak jsme přizpůsobit naši minimum a
maximální hodnoty, se chystají změnit.

1495
01:14:34,020 --> 01:14:36,040
A jako výsledek, naše middle
bude příliš měnit.

1496
01:14:36,040 --> 01:14:37,873
Takže to je důvod, proč chceme,
to udělat tady.

1497
01:14:37,873 --> 01:14:38,510
DOBŘE.

1498
01:14:38,510 --> 01:14:41,600
>> A pak, že teď
jsme našli our-- jo.

1499
01:14:41,600 --> 01:14:44,270
>> Diváků: Jen rychlý question--
když říkáte, min a max,

1500
01:14:44,270 --> 01:14:46,410
jsme za předpokladu, že
to je již řazeno?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Jo, to je vlastně
Předpokladem pro binární vyhledávání,

1502
01:14:48,400 --> 01:14:49,816
že musíte vědět, že to třídit.

1503
01:14:49,816 --> 01:14:53,660
Což je důvod, proč třídit, píšete ve vašem
problém nastavit před binárního vyhledávání.

1504
01:14:53,660 --> 01:14:55,910
DOBŘE.

1505
01:14:55,910 --> 01:14:58,876
Takže teď, když víme, kde naše střed
je, co chceš dělat?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> Diváků: Chceme porovnat
že do druhé.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Přesně tak.

1509
01:15:05,110 --> 01:15:12,280
Takže budete porovnávat
střední hodnotě, že jo?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
A co to říct
nás, když jsme porovnat?

1512
01:15:18,670 --> 01:15:22,226
Co chceme dělat potom?

1513
01:15:22,226 --> 01:15:25,389
>> Diváků: Je-li hodnota větší
než poloviny, chceme snížit ji.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Přesně tak.

1515
01:15:26,180 --> 01:15:33,940
Takže pokud je tato hodnota větší
než polovině, my jsme

1516
01:15:33,940 --> 01:15:36,550
bude chtít změnit tyto
minimální a maxes, že jo?

1517
01:15:36,550 --> 01:15:38,980
Co chceme změnit?

1518
01:15:38,980 --> 01:15:42,145
Takže pokud víme, že hodnota je někde
tady to, co dělat, ti, změnit?

1519
01:15:42,145 --> 01:15:44,758
Chceme změnit naše
Minimální být střední, že jo?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
A pak ještě, pokud je to v tomto
polovina, co chceme změnit?

1522
01:15:54,292 --> 01:15:55,306
>> Diváků: Vaše maximální.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Jo.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
A pak jste jen tak
aby looping, že jo?

1526
01:16:04,680 --> 01:16:08,920
Protože teď, po jednom průchodu
díky, máte max sem.

1527
01:16:08,920 --> 01:16:10,760
A pak můžete přepočítat v polovině.

1528
01:16:10,760 --> 01:16:11,990
A pak si můžete porovnat.

1529
01:16:11,990 --> 01:16:14,766
A budete dál
dokud min a maxes

1530
01:16:14,766 --> 01:16:15,890
mají v podstatě konvergované.

1531
01:16:15,890 --> 01:16:17,890
A to je, když víte, že
že jste narazila na konec.

1532
01:16:17,890 --> 01:16:20,280
A to buď jste ho našli
nebo nemáte v tomto bodě.

1533
01:16:20,280 --> 01:16:23,170
>> Má to smysl, aby všechny?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
DOBŘE.

1536
01:16:26,770 --> 01:16:27,900
To je docela důležité,
protože budete mít

1537
01:16:27,900 --> 01:16:29,760
psát to v kódu večer.

1538
01:16:29,760 --> 01:16:32,660
Ale vy máte docela dobrý
smysl pro to, co byste měli dělat,

1539
01:16:32,660 --> 01:16:34,051
což je dobré.

1540
01:16:34,051 --> 01:16:34,550
DOBŘE.

1541
01:16:34,550 --> 01:16:38,840
Takže máme asi sedm
minut levé části.

1542
01:16:38,840 --> 01:16:43,170
Takže budeme hovořit o
tento pset, že budeme dělat.

1543
01:16:43,170 --> 01:16:46,410
Takže pset je rozdělena na dvě poloviny.

1544
01:16:46,410 --> 01:16:50,230
První polovina se týká
provádění find

1545
01:16:50,230 --> 01:16:54,210
ve kterém píšete lineární hledání, je
binární vyhledávání a třídění algoritmus.

1546
01:16:54,210 --> 01:16:56,690
>> Tak toto je první
tentokrát v pset kde

1547
01:16:56,690 --> 01:17:00,050
budeme dávat vám kluci, co se nazývá
Distribuce kód, což je kód

1548
01:17:00,050 --> 01:17:02,740
že jsme pre-psaný,
ale právě opustil několik kousků off

1549
01:17:02,740 --> 01:17:04,635
pro vás až do konce psaní.

1550
01:17:04,635 --> 01:17:07,510
Takže vás kluci, když se podíváte na to
kód, byste mohli dostat opravdu strach.

1551
01:17:07,510 --> 01:17:08,630
Pokud jste stejně jako já, ach,
Nevím, co to dělá,

1552
01:17:08,630 --> 01:17:11,670
Já nevím, stejně jako, že se zdá
tak složité, ehm, relaxovat.

1553
01:17:11,670 --> 01:17:12,170
Je to v pohodě.

1554
01:17:12,170 --> 01:17:12,930
Přečtěte si spec.

1555
01:17:12,930 --> 01:17:16,920
Spec vám vysvětlí přesně
Co všechny tyto programy dělají.

1556
01:17:16,920 --> 01:17:20,560
>> Například, generate.c je program
že přijde s pset.

1557
01:17:20,560 --> 01:17:24,060
Nemusíte skutečně se ho dotknout, ale
měli byste pochopit, co to dělá.

1558
01:17:24,060 --> 01:17:28,550
A generate.c, vše, co dělá, je
buď generování náhodných čísel

1559
01:17:28,550 --> 01:17:32,400
nebo si můžete dát semeno, jako když
předem domluvené číslo, které je zapotřebí,

1560
01:17:32,400 --> 01:17:34,140
a to generuje více čísel.

1561
01:17:34,140 --> 01:17:37,170
Takže tam je specifický způsob, jak
implementovat generate.c ve kterém

1562
01:17:37,170 --> 01:17:42,760
stačí udělat spoustu čísel
pro vás otestovat své jiné metody na.

1563
01:17:42,760 --> 01:17:45,900
>> Takže pokud byste chtěli, pro
Příkladem, otestujte nález,

1564
01:17:45,900 --> 01:17:48,970
budete chtít spustit generate.c,
generují spoustu čísel,

1565
01:17:48,970 --> 01:17:50,880
a pak spustit funkci pomocníků.

1566
01:17:50,880 --> 01:17:53,930
Váš pomocníci funkce je místo, kde jste
vlastně fyzicky psaní kódu.

1567
01:17:53,930 --> 01:17:59,330
A myslet pomocníků jako soubor knihovny
píšete, že nález volá.

1568
01:17:59,330 --> 01:18:02,950
A tak se v rámci helpers.c, budete
dělat vyhledávání a řazení.

1569
01:18:02,950 --> 01:18:06,500
>> A pak budete v podstatě
stačí dát je všechny dohromady.

1570
01:18:06,500 --> 01:18:10,350
Spec vám poradí, jak se
dát, že na příkazovém řádku.

1571
01:18:10,350 --> 01:18:14,880
A budete moci vyzkoušet, zda
není váš třídit a hledat pracují.

1572
01:18:14,880 --> 01:18:15,870
Bezva.

1573
01:18:15,870 --> 01:18:18,720
Má už někdo začal a
setkávalo s problémy nebo dotazy

1574
01:18:18,720 --> 01:18:20,520
mají právě teď s tím?

1575
01:18:20,520 --> 01:18:21,020
DOBŘE.

1576
01:18:21,020 --> 01:18:21,476
>> Diváků: Počkejte.

1577
01:18:21,476 --> 01:18:21,932
Mám otázku.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Jo.

1579
01:18:22,844 --> 01:18:28,390
>> Diváků: Tak jsem začal dělat
lineární hledání v helpers.c

1580
01:18:28,390 --> 01:18:29,670
a to nebylo opravdu funguje.

1581
01:18:29,670 --> 01:18:34,590
Ale později jsem zjistil, že jsme právě
musíš ji smazat a udělat binární vyhledávání.

1582
01:18:34,590 --> 01:18:36,991
Takže to je jedno, jestli to nebude fungovat?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: Krátká odpověď zní ne.

1585
01:18:41,510 --> 01:18:42,642
Ale protože jsme ne--

1586
01:18:42,642 --> 01:18:44,350
Diváků: Ale nikdo
ve skutečnosti kontrola.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Jsme Nikdy
jde vidět, že.

1588
01:18:46,058 --> 01:18:49,590
Ale pravděpodobně budete chtít, aby se
jisti, že vaše hledání funguje.

1589
01:18:49,590 --> 01:18:51,700
Protože pokud vaše lineární
Hledání nefunguje,

1590
01:18:51,700 --> 01:18:54,410
pak je šance jsou vaše binární
vyhledávání nebude fungovat stejně.

1591
01:18:54,410 --> 01:18:56,646
Protože máte podobnou
Logika v obou z nich.

1592
01:18:56,646 --> 01:18:58,020
A ne, to opravdu nezáleží.

1593
01:18:58,020 --> 01:19:01,300
Takže pouze ty, které budete zase
v jsou třídit a binární vyhledávání.

1594
01:19:01,300 --> 01:19:02,490
To jo.

1595
01:19:02,490 --> 01:19:06,610
>> A také, spousta dětí bylo
snaží se sestavit helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Nejste vlastně dovoleno
to udělat, protože helpers.c

1597
01:19:09,550 --> 01:19:11,200
nemá hlavní funkci.

1598
01:19:11,200 --> 01:19:13,550
A tak byste měli pouze
být ve skutečnosti kompilace

1599
01:19:13,550 --> 01:19:18,670
vytvoření a najít, protože najít hovory
helpers.c a funkce v ní.

1600
01:19:18,670 --> 01:19:20,790
Takže to dělá ladění
jako osina v zadku.

1601
01:19:20,790 --> 01:19:22,422
Ale to je to, co musíme udělat.

1602
01:19:22,422 --> 01:19:23,880
Diváků: Jen Uděláte všechno, že jo?

1603
01:19:23,880 --> 01:19:27,290
ANDI PENG: stačí
dělat všechno stejně, jo.

1604
01:19:27,290 --> 01:19:28,060
DOBŘE.

1605
01:19:28,060 --> 01:19:32,570
Tak to je, pokud jde o to, co
pset žádá, abyste všichni dělat.

1606
01:19:32,570 --> 01:19:35,160
Máte-li jakékoli dotazy, pocit
zdarma a zeptejte se mě po bodu.

1607
01:19:35,160 --> 01:19:37,580
Budu tady, stejně jako, 20 minut.

1608
01:19:37,580 --> 01:19:40,500
>> A ano, je to pset
opravdu není tak špatné.

1609
01:19:40,500 --> 01:19:41,680
Měli byste být v pořádku.

1610
01:19:41,680 --> 01:19:43,250
Ty, jen řídit se pokyny.

1611
01:19:43,250 --> 01:19:47,840
Druh mají pocit, logicky, co
Děje se to, a budete v pohodě.

1612
01:19:47,840 --> 01:19:48,690
Nebuďte příliš velký strach.

1613
01:19:48,690 --> 01:19:50,220
Je tu spousta kódu
již psali zde.

1614
01:19:50,220 --> 01:19:53,011
Nebuďte příliš velký strach, pokud nemáte
pochopit, co to všechno znamená.

1615
01:19:53,011 --> 01:19:54,749
Pokud je to hodně, je to naprosto v pořádku.

1616
01:19:54,749 --> 01:19:55,790
A přišel úřední hodiny.

1617
01:19:55,790 --> 01:19:57,520
Pomůžeme vám se podívat.

1618
01:19:57,520 --> 01:20:00,810
>> Diváků: S extra
funkce, se podíváme na ty?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Jo, ty, které jsou v kódu.

1620
01:20:03,417 --> 01:20:05,750
Ve hře 15 polovina
je to už napsal pro tebe.

1621
01:20:05,750 --> 01:20:09,310
Takže tyto funkce jsou
již v kódu.

1622
01:20:09,310 --> 01:20:12,020
Jo.

1623
01:20:12,020 --> 01:20:12,520
Dobře.

1624
01:20:12,520 --> 01:20:14,000
No, hodně štěstí.

1625
01:20:14,000 --> 01:20:15,180
Je to nechutné den.

1626
01:20:15,180 --> 01:20:19,370
Takže doufejme, že vy se necítí příliš
špatného na tom, zůstat uvnitř a kódování.

1627
01:20:19,370 --> 01:20:22,133