1
00:00:00,000 --> 00:00:03,332
>> [Zenelejátszási]

2
00:00:03,332 --> 00:00:06,490
>> ANDI Peng: Üdvözöljük héten 3 szakasz.

3
00:00:06,490 --> 00:00:09,550
Köszi, srácok, minden jön
hogy ez a korábbi kezdési időpont ma.

4
00:00:09,550 --> 00:00:11,466
Van egy szép, kis
intim csoport ma.

5
00:00:11,466 --> 00:00:14,570
Így remélhetőleg sikerülni fog
befejezni, talán korai,

6
00:00:14,570 --> 00:00:15,780
Egy kicsit korai még ma.

7
00:00:15,780 --> 00:00:22,057
Olyan gyorsan, csak néhány
bejelentések a napirenden ma.

8
00:00:22,057 --> 00:00:23,890
Mielőtt belevágnánk, mi vagyunk
fog csak megy át

9
00:00:23,890 --> 00:00:28,910
néhány rövid logisztikai kérdések, PSET
kérdésekre, kikérdez, ilyesmi.

10
00:00:28,910 --> 00:00:30,250
És akkor majd zuhanásra.

11
00:00:30,250 --> 00:00:34,710
Majd egy nyomkövető nevű GDB
kezdeni leleplezése a kódot, amely David

12
00:00:34,710 --> 00:00:36,550
kifejtette előadást a minap.

13
00:00:36,550 --> 00:00:39,420
Átnézzük a négyféle fajta.

14
00:00:39,420 --> 00:00:42,310
Átnézzük őket elég gyorsan
hiszen ők elég intenzív.

15
00:00:42,310 --> 00:00:45,710
De tudom, hogy minden diák és
forráskód mindig online.

16
00:00:45,710 --> 00:00:50,810
Szóval nyugodtan, a átolvasás, hogy
menj vissza, és nézd meg ezt.

17
00:00:50,810 --> 00:00:53,930
>> Elmegyünk keresztül
aszimptotikus jelölés, amely

18
00:00:53,930 --> 00:00:55,944
csak egy divatos módon
mondván, hogy "runtimes"

19
00:00:55,944 --> 00:00:58,360
ahol már a nagy O, amelyek
David kifejtette előadásában.

20
00:00:58,360 --> 00:01:01,550
És mi is az Omega, amely
az alsó határ idejét.

21
00:01:01,550 --> 00:01:06,450
És fogunk beszélni egy kicsit
mélyreható vonatkozóan, hogyan ezek a munkák.

22
00:01:06,450 --> 00:01:10,160
És végül, megyünk át a bináris keresés,
mert sok van, akik már

23
00:01:10,160 --> 00:01:15,190
pillantott meg psets valószínűleg tudja, hogy
ezt a kérdést, hogy ez a PSET.

24
00:01:15,190 --> 00:01:17,470
Szóval akkor minden boldog
hogy fedezze ezt ma.

25
00:01:17,470 --> 00:01:20,610
>> És végül, egy a
szakaszban visszajelzést, én valóban

26
00:01:20,610 --> 00:01:23,000
bal körülbelül 15 percen át
A végén, hogy csak megy át

27
00:01:23,000 --> 00:01:27,730
logisztikai pset3, bármilyen kérdése,
talán egy kicsit útmutatást, ha úgy tetszik,

28
00:01:27,730 --> 00:01:28,990
mielőtt elkezdjük a programozást.

29
00:01:28,990 --> 00:01:30,890
Úgyhogy próbáljuk átvészelni
az anyag elég gyorsan.

30
00:01:30,890 --> 00:01:33,880
És akkor mi is eltölteni egy kis időt
figyelembe több kérdés az PSET.

31
00:01:33,880 --> 00:01:35,230
OKÉ.

32
00:01:35,230 --> 00:01:39,570
>> Gyorsan, így csak néhány
bejelentések, mielőtt elkezdjük a mai napon.

33
00:01:39,570 --> 00:01:45,410
Először is, szívesen teszi
keresztül két a psets.

34
00:01:45,410 --> 00:01:49,432
Vettem egy pillantást your-- igen, mielőtt
kap egy tapsot, hogy az egyik.

35
00:01:49,432 --> 00:01:51,140
Igazából, én nagyon,
nagyon lenyűgözött.

36
00:01:51,140 --> 00:01:55,800
Én osztályozzák az első PSET srácok
a múlt héten, és a srácok tette hihetetlen.

37
00:01:55,800 --> 00:01:58,290
>> Stílus volt pont
mellett néhány megjegyzést.

38
00:01:58,290 --> 00:02:00,660
Győződjön meg róla, hogy mindig
kommentálva a kódot.

39
00:02:00,660 --> 00:02:03,040
De a psets voltak a kérdésben.

40
00:02:03,040 --> 00:02:05,549
És csak így tovább.

41
00:02:05,549 --> 00:02:08,090
És ez jó a gréder, hogy
láthatjuk, hogy a srácok üzembe

42
00:02:08,090 --> 00:02:10,704
annyi erőfeszítést az Ön stílusát
és a design a kódban

43
00:02:10,704 --> 00:02:12,120
az, hogy szeretnénk, hogy lásd.

44
00:02:12,120 --> 00:02:16,450
Úgyhogy halad végig hálámat
a többi TAS.

45
00:02:16,450 --> 00:02:19,210
>> Azonban van egy
Néhány kikérdez kérdések

46
00:02:19,210 --> 00:02:22,010
Csak azt akarom, hogy menjen át, hogy
tenné mind az életem

47
00:02:22,010 --> 00:02:24,900
és egy csomó más
TA "él egy kicsit könnyebb.

48
00:02:24,900 --> 00:02:28,220
Először is, azt vettem észre ezt
már week-- hányan

49
00:02:28,220 --> 00:02:32,301
már fut a check50
A kód elküldése előtt?

50
00:02:32,301 --> 00:02:32,800
OKÉ.

51
00:02:32,800 --> 00:02:36,690
Tehát mindenkinek meg kell csinálni check50,
because-- egy secret-- valójában

52
00:02:36,690 --> 00:02:41,540
fuss check50 részeként a korrektség
szkriptek tesztelésére a kódot.

53
00:02:41,540 --> 00:02:45,480
Tehát, ha a kód hiányában
check50, minden valószínűség szerint,

54
00:02:45,480 --> 00:02:47,570
ez valószínűleg a
nem a check is.

55
00:02:47,570 --> 00:02:49,320
Néha srácok
a helyes válaszokat.

56
00:02:49,320 --> 00:02:52,200
Mint, a kapzsi, néhány
Önnek joga van a számok,

57
00:02:52,200 --> 00:02:53,960
Ön csak nyomtassa ki valami extra.

58
00:02:53,960 --> 00:02:55,940
És, hogy extra dolgokat
valójában nem az ellenőrzés,

59
00:02:55,940 --> 00:02:58,440
mert a számítógép nem
Tényleg tudom mi a keres.

60
00:02:58,440 --> 00:03:00,981
És ez így lesz, csak végigmenni,
látni, hogy a kimenet nem

61
00:03:00,981 --> 00:03:03,810
egyezik azzal, amit várunk a válasz
lenni, és jelölje meg a baj.

62
00:03:03,810 --> 00:03:06,560
>> És tudom, hogy történt,
néhány esetben ezen a héten.

63
00:03:06,560 --> 00:03:09,870
Így mentem vissza, és manuálisan
újraosztályozva mindenki kódot.

64
00:03:09,870 --> 00:03:12,780
A jövőben, bár,
Kérjük, győződjön meg róla,

65
00:03:12,780 --> 00:03:14,570
hogy futsz
ellenőrizze 50 a kódot.

66
00:03:14,570 --> 00:03:17,970
Mert ez egyfajta fájdalom a TA
hogy vissza kell mennie, és manuálisan újraosztályozásról

67
00:03:17,970 --> 00:03:21,197
minden egyes PSET minden
Egyetlen, kicsit hiányzott például.

68
00:03:21,197 --> 00:03:22,530
Szóval nem vette le a pontokat.

69
00:03:22,530 --> 00:03:25,210
Azt hiszem, levette talán
egy vagy két a tervezés.

70
00:03:25,210 --> 00:03:27,710
A jövőben, bár, ha
te ennek hiányában check50,

71
00:03:27,710 --> 00:03:31,330
pont kerül sor
off helyességét.

72
00:03:31,330 --> 00:03:35,020
>> Továbbá psets is
miatt pénteken délben.

73
00:03:35,020 --> 00:03:38,990
Azt hiszem, van egy hét perces
késői türelmi idő, amit kapsz.

74
00:03:38,990 --> 00:03:42,434
Per Harvard időben, ők hagyjuk
hét perc végén mindent.

75
00:03:42,434 --> 00:03:44,350
Tehát itt a Yale-en, akkor
tartsák be azt is.

76
00:03:44,350 --> 00:03:47,910
De nagyon sok, a 00:07,
ha a PSET nincs,

77
00:03:47,910 --> 00:03:49,720
ez meg fog jelölni, mint későn.

78
00:03:49,720 --> 00:03:53,160
És így amíg az jelölve
a végén, a TA-- vagyok

79
00:03:53,160 --> 00:03:54,870
még mindig lesz osztályozás a psets.

80
00:03:54,870 --> 00:03:56,760
Szóval továbbra is lát egy fokozat jelenik meg.

81
00:03:56,760 --> 00:03:58,820
Ugyanakkor tudjuk, hogy a
A végén a félév,

82
00:03:58,820 --> 00:04:02,270
minden késedelmes psets csak úgy lesz
automatikusan nullázódik a számítógép.

83
00:04:02,270 --> 00:04:04,490
>> Tesszük ezt két okból.

84
00:04:04,490 --> 00:04:09,220
Az egyik, néha megkapjuk
elnézést, mint a dékáni kifogásokat,

85
00:04:09,220 --> 00:04:10,762
később, hogy nem tud még.

86
00:04:10,762 --> 00:04:13,761
Tehát szeretném győződjön meg arról, mi a besorolási
mindent csak abban az esetben, mint én vagyok

87
00:04:13,761 --> 00:04:15,080
Hiányzik egy dékáni kifogás.

88
00:04:15,080 --> 00:04:17,000
És másodszor, tartsa
szem előtt, akkor is

89
00:04:17,000 --> 00:04:19,370
egy csepp PSET, hogy
van teljes körű pont.

90
00:04:19,370 --> 00:04:21,430
És így szeretünk évfolyam
az összes psets csak

91
00:04:21,430 --> 00:04:24,730
meggyőződni arról, hogy a szonda
és ott próbál nekik.

92
00:04:24,730 --> 00:04:29,150
Így még ha késő van, akkor még mindig
kap hitelt hatálya pontot, azt hiszem.

93
00:04:29,150 --> 00:04:33,730
>> Szóval a történet tanulsága az, hogy
Ellenőrizze, hogy a psets vannak az időben.

94
00:04:33,730 --> 00:04:38,350
És ha azok nem az időben,
tudom, hogy ez nem jó.

95
00:04:38,350 --> 00:04:41,678
Ja, mielőtt lépni, nem akárki volna
bármilyen kérdése PSET visszajelzést?

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

97
00:04:42,178 --> 00:04:43,630
>> Közönség: Azt mondtad, mi
csepp az egyik psets?

98
00:04:43,630 --> 00:04:44,296
>> ANDI Peng: Igen.

99
00:04:44,296 --> 00:04:47,050
Szóval van kilenc psets összességében
során a félév.

100
00:04:47,050 --> 00:04:50,610
És ha van elegendő mozgástér
points-- így hatálya csak,

101
00:04:50,610 --> 00:04:53,567
nagyon sok, te próbál a
probléma, te üzembe időben,

102
00:04:53,567 --> 00:04:56,150
mutatod, hogy már
bizonyította, hogy elolvasta a spec.

103
00:04:56,150 --> 00:04:57,191
Ez elég sok hatálya alá.

104
00:04:57,191 --> 00:04:59,370
És ha teljesítik
hatálya pontot, akkor

105
00:04:59,370 --> 00:05:03,360
csökkenhet a legalacsonyabb
egyet a teljes körű.

106
00:05:03,360 --> 00:05:06,790
Szóval ez az Ön előnye, hogy
töltse ki és próbálja minden PSET.

107
00:05:06,790 --> 00:05:10,320
>> Még upload-- ha egyik
őket dolgozni, töltse fel őket.

108
00:05:10,320 --> 00:05:13,711
És akkor majd remélhetőleg képesek
kapsz néhány ilyen pont vissza.

109
00:05:13,711 --> 00:05:14,210
Hűvös.

110
00:05:14,210 --> 00:05:16,780
Más kérdés?

111
00:05:16,780 --> 00:05:17,840
Nagy.

112
00:05:17,840 --> 00:05:21,960
>> Másodszor, irodai hours-- pár
gyors jegyzeteket munkaidőben.

113
00:05:21,960 --> 00:05:24,300
Tehát először jött a hét elején.

114
00:05:24,300 --> 00:05:26,909
Senki sem eddiginél
munkaidőn hétfőn.

115
00:05:26,909 --> 00:05:28,700
Christabel jött
munkaidőn tegnap este.

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

117
00:05:29,691 --> 00:05:32,190
És mit van az irodában
órán múlt éjjel, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> Közönség: Mi volt a fagylalt.

119
00:05:33,020 --> 00:05:36,160
>> ANDI Peng: Szóval ez így van, mi volt
jégkrémet munkaidőn tegnap este.

120
00:05:36,160 --> 00:05:39,390
Míg nem ígérhetem, hogy
mi lesz fagylaltot munkaidőn

121
00:05:39,390 --> 00:05:43,230
Minden héten, amit én is ígérem
az, hogy lesz egy jelentősen

122
00:05:43,230 --> 00:05:45,380
jobb tanuló TA arányt.

123
00:05:45,380 --> 00:05:47,650
Mint legális, ez olyan, mint 3-1.

124
00:05:47,650 --> 00:05:50,350
Mivel ezzel ellentétben,
Csütörtök, megvan mintegy 150

125
00:05:50,350 --> 00:05:52,830
Tényleg hangsúlyozta a gyerekek, és nem fagylaltot.

126
00:05:52,830 --> 00:05:55,360
És ez csak nem produktív bárki.

127
00:05:55,360 --> 00:05:58,730
Szóval a történet tanulsága van, korán jött
a munkaidőn és a jó dolgokat

128
00:05:58,730 --> 00:06:00,310
meg fog történni.

129
00:06:00,310 --> 00:06:02,110
>> Szintén érdemes felkészülni, hogy kérdéseket tegyenek fel.

130
00:06:02,110 --> 00:06:03,200
Tudod?

131
00:06:03,200 --> 00:06:05,420
Függetlenül attól, amit Tas én
gondolom, már azt mondja,

132
00:06:05,420 --> 00:06:10,710
mi már kezd egy pár diákok
akik jönnek csütörtökön, mint, 10:50

133
00:06:10,710 --> 00:06:15,100
mivel nem olvassa a specifikációt
hogy olyan lesz mint nekem segíteni, segítsen nekem.

134
00:06:15,100 --> 00:06:18,200
Sajnos ezen a ponton, van
Nem sokat tehetünk, hogy segítsen.

135
00:06:18,200 --> 00:06:19,590
Ezért kérjük, jöjjön a hét elején.

136
00:06:19,590 --> 00:06:22,040
Gyere már, hogy hivatali időben.

137
00:06:22,040 --> 00:06:23,350
Gyere elkészített kérdéseket feltenni.

138
00:06:23,350 --> 00:06:25,310
Győződjön meg arról, hogy Ön, mint
egy diák, van, ahol

139
00:06:25,310 --> 00:06:27,620
meg kell, hogy legyen, hogy a
TA is elvezeti Önt mentén,

140
00:06:27,620 --> 00:06:32,850
ami pedig munkaidőn
ki kell kiosztani.

141
00:06:32,850 --> 00:06:37,380
>> Másodszor, így tudom, hogy a professzorok
szeretném meglepni minket tesztek.

142
00:06:37,380 --> 00:06:39,439
Volt egy tanár azoknak
mint, yo, az úton,

143
00:06:39,439 --> 00:06:41,230
ne feledjük, hogy középtávú
Van jövő hétfőn.

144
00:06:41,230 --> 00:06:42,855
Ja, nem tudtam róla középtávú.

145
00:06:42,855 --> 00:06:45,630
Így fogok lenni, hogy a TA
emlékezteti, minden kvíz

146
00:06:45,630 --> 00:06:47,270
0--, mert tudod, mi vagyunk CS.

147
00:06:47,270 --> 00:06:50,730
Most, hogy megtettem tömbök, kapsz
miért kvíz 0, nem Quiz 1, he?

148
00:06:50,730 --> 00:06:51,320
OKÉ.

149
00:06:51,320 --> 00:06:52,490
Ó, kaptam néhány kuncog hogy az egyik.

150
00:06:52,490 --> 00:06:53,120
OKÉ.

151
00:06:53,120 --> 00:06:59,710
>> Tehát kvíz 0 lesz, október 14 ha
te vagy a hétfő-szerda részén

152
00:06:59,710 --> 00:07:02,920
és október 15. ha a
A kedd-csütörtök részt.

153
00:07:02,920 --> 00:07:05,630
Ez nem vonatkozik az
Azoknak, a Harvard

154
00:07:05,630 --> 00:07:10,350
who-- azt hiszem, mindannyian
figyelembe vetélkedők 14-én.

155
00:07:10,350 --> 00:07:13,560
>> Szóval igen, a jövő héten, ha
David, az előadás, megy,

156
00:07:13,560 --> 00:07:15,747
Igen, arról, hogy
kvíz jövő héten, akkor az összes

157
00:07:15,747 --> 00:07:17,580
nem lesz döbbenve, mert
azért jött, hogy a rész

158
00:07:17,580 --> 00:07:19,664
és tudod, hogy a
kvíz 0 jelentése két hét alatt.

159
00:07:19,664 --> 00:07:21,580
És mi lesz felülvizsgálata
ülések és mindent.

160
00:07:21,580 --> 00:07:26,360
Így nem aggódik
félek, hogy.

161
00:07:26,360 --> 00:07:29,890
Bármilyen kérdése before-- bármilyen kérdése
Egyáltalán kapcsolatos logisztikai kérdések,

162
00:07:29,890 --> 00:07:32,591
osztályozás, munkaidejében szakaszok?

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

164
00:07:33,090 --> 00:07:35,100
>> Közönség: Tehát a teszt
lesz ideje alatt előadást?

165
00:07:35,100 --> 00:07:35,766
>> ANDI Peng: Igen.

166
00:07:35,766 --> 00:07:39,460
Tehát a kvíz, azt hiszem, 60
perc allokált, hogy időréshez

167
00:07:39,460 --> 00:07:42,240
hogy akkor csak vegye
a teremben.

168
00:07:42,240 --> 00:07:44,810
Szóval nem kell bejönni
a, mondjuk, egy véletlen 07:00.

169
00:07:44,810 --> 00:07:46,140
Minden rendben van.

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

171
00:07:47,100 --> 00:07:50,060
Hűvös.

172
00:07:50,060 --> 00:07:50,840
>> Minden rendben.

173
00:07:50,840 --> 00:07:54,330
Szóval megyünk
bevezetni a koncepciót az Ön számára

174
00:07:54,330 --> 00:08:00,760
ezen a héten, hogy Dávid már egyfajta
A érintettünk előadást a múlt héten.

175
00:08:00,760 --> 00:08:02,010
Úgy hívják GDB.

176
00:08:02,010 --> 00:08:05,570
És hányan, míg
írása közben a psets,

177
00:08:05,570 --> 00:08:09,981
észrevették a nagy gombot, hogy azt mondja,
"Debug" a tetején az IDE?

178
00:08:09,981 --> 00:08:10,480
OKÉ.

179
00:08:10,480 --> 00:08:13,770
Szóval most mi lesz valójában kap, hogy felfedez
A rejtély, hogy mi az a gomb tényleg

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

181
00:08:14,270 --> 00:08:16,790
És én garantálom, hogy ez egy
szép, szép dolog.

182
00:08:16,790 --> 00:08:20,740
>> Szóval eddig, azt hiszem,
van már két dolog

183
00:08:20,740 --> 00:08:23,320
diákok már jellemzően
csinálsz, amikor hibakeresés psets.

184
00:08:23,320 --> 00:08:27,635
Az egyik, hogy vagy hozzá
printf () - így minden pár sort,

185
00:08:27,635 --> 00:08:29,760
Hozzáteszik egy printf () -
Ó, mi ez a változó?

186
00:08:29,760 --> 00:08:32,551
Ó, mi ez a változó now--
és akkor milyen láthatjuk a fejlődést

187
00:08:32,551 --> 00:08:33,940
a kód futása közben.

188
00:08:33,940 --> 00:08:37,030
Vagy a második módszer a gyerekek tennie,
hogy csak írni az egészet

189
00:08:37,030 --> 00:08:38,610
és aztán megy, mint ez a végén.

190
00:08:38,610 --> 00:08:39,970
Remélhetőleg ez működik.

191
00:08:39,970 --> 00:08:44,851
Garantálom neked, GDB jobb
mint e két módszer.

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

193
00:08:45,350 --> 00:08:46,980
Szóval ez lesz az új legjobb barátja.

194
00:08:46,980 --> 00:08:51,780
Mert ez egy szép dolog
amely vizuálisan megjeleníti mind

195
00:08:51,780 --> 00:08:54,850
mi a kód csinál
egy meghatározott ponthoz

196
00:08:54,850 --> 00:08:57,486
valamint mi az összes
változók könyv,

197
00:08:57,486 --> 00:08:59,610
mint hogy milyen értékeket vallanak,
ezen a bizonyos pontot.

198
00:08:59,610 --> 00:09:02,670
És így, akkor tényleg
töréspont a kódban.

199
00:09:02,670 --> 00:09:04,350
Akkor végigmenni sorról sorra.

200
00:09:04,350 --> 00:09:07,324
És GDB csak meg a
te, meg az Ön számára,

201
00:09:07,324 --> 00:09:09,490
mi az összes változót
vannak, mit csinálnak,

202
00:09:09,490 --> 00:09:10,656
mi folyik a kódot.

203
00:09:10,656 --> 00:09:13,240
És oly módon, hogy ez
így sokkal könnyebb látni

204
00:09:13,240 --> 00:09:17,120
mi történik helyett printf-nek
vagy leírom a kimutatásokban.

205
00:09:17,120 --> 00:09:19,160
>> Tehát mi nem egy példa erre később.

206
00:09:19,160 --> 00:09:20,660
Szóval ez úgy tűnik, egy kicsit elvont.

207
00:09:20,660 --> 00:09:23,490
Semmi gond, mi intézzük példákat.

208
00:09:23,490 --> 00:09:29,170
És így lényegében a három legnagyobb,
A leggyakrabban használt funkciókat, amelyekre szüksége lehet GDB

209
00:09:29,170 --> 00:09:32,500
Melyek a következő, átlépni,
és belép a gombok.

210
00:09:32,500 --> 00:09:34,860
Megyek feje fölött
ott, igazából most.

211
00:09:34,860 --> 00:09:40,930
>> Szóval lehet, srácok mindannyian látni, hogy
vagy kell nagyítani egy kicsit?

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

213
00:09:43,220 --> 00:09:44,470
A hátsó, látod ezt?

214
00:09:44,470 --> 00:09:45,730
Kell nagyítás?

215
00:09:45,730 --> 00:09:46,480
Csak egy kicsit?

216
00:09:46,480 --> 00:09:49,390
OK, hűvös.

217
00:09:49,390 --> 00:09:50,280
Ott vagyunk.

218
00:09:50,280 --> 00:09:50,960
OKÉ.

219
00:09:50,960 --> 00:09:57,000
>> Szóval van itt, én
végrehajtás kapzsi.

220
00:09:57,000 --> 00:10:01,430
És bár sok srácok írt
kapzsi while ciklus form--, hogy

221
00:10:01,430 --> 00:10:04,890
egy tökéletesen elfogadható módja
it-- másik módja az, hogy az, hogy egyszerűen

222
00:10:04,890 --> 00:10:06,280
osztja a modulo.

223
00:10:06,280 --> 00:10:09,290
Mert akkor lehet a
értéket, és ezt követően a maradékot.

224
00:10:09,290 --> 00:10:11,150
És akkor csak
add össze az egészet.

225
00:10:11,150 --> 00:10:13,390
Vajon a logikája, hogy mit csinálok
Itt értelme mindenkinek,

226
00:10:13,390 --> 00:10:14,117
mielőtt elkezdjük?

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

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

229
00:10:17,980 --> 00:10:18,710
Hűvös.

230
00:10:18,710 --> 00:10:19,210
Nagy.

231
00:10:19,210 --> 00:10:21,290
Ez egy nagyon szexi darab
kód, azt mondanám.

232
00:10:21,290 --> 00:10:23,502
Mint mondtam, David, a
előadás, egy idő után,

233
00:10:23,502 --> 00:10:25,960
akkor minden újra látni kódot
mint valamit, ami szép.

234
00:10:25,960 --> 00:10:29,950
És néha, ha látni szép
kód, ez egy ilyen csodálatos érzés.

235
00:10:29,950 --> 00:10:35,410
>> Így azonban, miközben ez a kód nagyon
szép, hogy nem működik megfelelően.

236
00:10:35,410 --> 00:10:37,750
Szóval futni check50 ezen.

237
00:10:37,750 --> 00:10:39,440
Ellenőrizze 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
Ez pset2?

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

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

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

244
00:10:50,970 --> 00:10:52,890
OKÉ.

245
00:10:52,890 --> 00:10:53,900
Szóval mi fut check50.

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

247
00:11:01,550 --> 00:11:07,170
>> És ahogy ti is láthatja,
ez ennek hiányában egy-két esetben.

248
00:11:07,170 --> 00:11:10,165
És néhányan közületek, a
Természetesen csinál a problémát készletek,

249
00:11:10,165 --> 00:11:11,110
Ön, mint, ah, miért nem működik.

250
00:11:11,110 --> 00:11:13,318
Miért van az, dolgozik egy
értékeket, de nem mások?

251
00:11:13,318 --> 00:11:17,760
Nos, a GDB fog, hogy segítsen kitalálni
hogy miért ezeket a ráfordításokat nem működik.

252
00:11:17,760 --> 00:11:18,320
>> OKÉ.

253
00:11:18,320 --> 00:11:21,640
Tehát lássuk, az egyik
ellenőrzéseket voltam ennek hiányában a check50

254
00:11:21,640 --> 00:11:24,920
volt a bemeneti értéke 0,41.

255
00:11:24,920 --> 00:11:27,830
Tehát a helyes válasz, hogy
akkor kapok egy 4.

256
00:11:27,830 --> 00:11:33,090
De ahelyett, amit én kinyomtatásával
a 3-n, ami helytelen.

257
00:11:33,090 --> 00:11:36,190
Úgyhogy csak fuss kézzel is, csak
győződjön meg arról, hogy check50 dolgozik.

258
00:11:36,190 --> 00:11:36,940
Csináljuk ./greedy.

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

260
00:11:40,130 --> 00:11:43,340
Hoppá, azt kell, hogy kapzsi.

261
00:11:43,340 --> 00:11:43,840
Ott vagyunk.

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

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

264
00:11:46,950 --> 00:11:47,670
>> Mennyibe kerül tartozott?

265
00:11:47,670 --> 00:11:49,550
Csináljuk 0.41.

266
00:11:49,550 --> 00:11:52,590
És igen, azt látjuk itt
hogy ez kimenetre 3

267
00:11:52,590 --> 00:11:55,160
ha a helyes választ,
sőt, kell 4.

268
00:11:55,160 --> 00:12:01,460
Úgyhogy adja GDB, és nézzük meg
mehet a rögzítés ez a probléma.

269
00:12:01,460 --> 00:12:03,992
>> Tehát az első lépés a
Mindig hibakeresés a kódot

270
00:12:03,992 --> 00:12:05,950
az, hogy hozzanak egy töréspont,
vagy az a pont, ahol

271
00:12:05,950 --> 00:12:09,079
szeretné, hogy a számítógép vagy a
debugger kezdeni a.

272
00:12:09,079 --> 00:12:11,120
Tehát, ha nem igazán
tudom, mi a probléma,

273
00:12:11,120 --> 00:12:14,670
Általában, a tipikus dolog, amit szeretnénk
tennie, hogy állítsa meg töréspont a fő.

274
00:12:14,670 --> 00:12:18,520
Tehát, ha ti is látni ezt
piros gombot ott,

275
00:12:18,520 --> 00:12:22,860
Ja, én voltam beállításával
típuspontjának a fő funkciója.

276
00:12:22,860 --> 00:12:24,130
Rákattintok, hogy.

277
00:12:24,130 --> 00:12:26,130
>> És akkor mehet akár én Debug gombra.

278
00:12:26,130 --> 00:12:27,036
Elütöttem a gombot.

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

280
00:12:31,710 --> 00:12:36,555
Hadd kicsinyítéshez ha tudok.

281
00:12:36,555 --> 00:12:38,020
Ott vagyunk.

282
00:12:38,020 --> 00:12:40,730
Tehát van itt, a panel jobb oldalán.

283
00:12:40,730 --> 00:12:43,680
Sajnálom, srácok, a hátsó, akkor
Nem igazán lehet látni igazán jól.

284
00:12:43,680 --> 00:12:49,090
De lényegében minden,
ez a jobb oldali panelen csinál

285
00:12:49,090 --> 00:12:53,130
figyelemmel kísérése, mind a kiemelt
vonal, amely a sorban a kód

286
00:12:53,130 --> 00:12:56,640
hogy a számítógép jelenleg futó,
valamint az összes változó

287
00:12:56,640 --> 00:12:57,600
itt lenn.

288
00:12:57,600 --> 00:13:00,487
>> Szóval megvan cent, érme, n,
minden bejelentett különböző dolgokra

289
00:13:00,487 --> 00:13:01,070
ezen a ponton.

290
00:13:01,070 --> 00:13:04,850
Nem kell aggódni, mert van valójában nem
inicializálni őket, hogy minden változó tartalom.

291
00:13:04,850 --> 00:13:07,200
Így a számítógép, a
számítógép csak látta,

292
00:13:07,200 --> 00:13:14,376
ó, 32767 volt az utoljára használt funkció
Az, hogy tárhely a gépemen.

293
00:13:14,376 --> 00:13:16,000
És ez az, ahol cent jelenleg.

294
00:13:16,000 --> 00:13:19,360
De nem, hogy ha egyszer futtatja a kódot,
kell válnia inicializált.

295
00:13:19,360 --> 00:13:24,110
>> Szóval menjünk át, sorról
vonal, mi folyik itt.

296
00:13:24,110 --> 00:13:25,350
OKÉ.

297
00:13:25,350 --> 00:13:29,400
Tehát itt van a három
gombok, hogy én csak magyarázta.

298
00:13:29,400 --> 00:13:34,090
Megvan a játék, vagy a Run funkció,
gombot, akkor a lépés több mint gombot,

299
00:13:34,090 --> 00:13:36,600
és akkor is a lépés a gombot.

300
00:13:36,600 --> 00:13:41,260
, És lényegében, mind a három
ezek csak menj át a kódot

301
00:13:41,260 --> 00:13:42,690
és különböző dolgokat.

302
00:13:42,690 --> 00:13:45,680
>> Így általában, ha éppen a hibakeresés,
mi nem akarjuk, hogy csak hit játék,

303
00:13:45,680 --> 00:13:47,930
mert Play csak fuss
A kód a végét.

304
00:13:47,930 --> 00:13:49,070
És akkor valójában nem
tudom, mi a bajod

305
00:13:49,070 --> 00:13:51,432
van, hacsak nem állítod, több töréspont.

306
00:13:51,432 --> 00:13:53,890
Ha több töréspont,
akkor csak automatikusan

307
00:13:53,890 --> 00:13:56,030
futnak egyik töréspont,
A következő, a következő.

308
00:13:56,030 --> 00:13:58,030
De ebben az esetben mi már
Csak, hogy az egyik, mert

309
00:13:58,030 --> 00:13:59,970
akar dolgozni az utat
fentről lefelé lefelé.

310
00:13:59,970 --> 00:14:04,830
Mi is így fogjuk figyelmen kívül hagyni azt a gombot
most a célra a program.

311
00:14:04,830 --> 00:14:08,230
>> Tehát a lépés több mint funkció csak
lépések alatt minden egyvonalas

312
00:14:08,230 --> 00:14:11,510
és megmondja, hogy mi
A futó programok.

313
00:14:11,510 --> 00:14:14,630
A lépés a funkció megy
a tényleges funkciója

314
00:14:14,630 --> 00:14:16,000
ez a sor kódot.

315
00:14:16,000 --> 00:14:19,070
Így például, mint a printf (),
hogy egy olyan funkció, ugye?

316
00:14:19,070 --> 00:14:21,980
Ha akartam fizikailag lépést
a printf () függvény,

317
00:14:21,980 --> 00:14:25,610
Én valóban bemegy a darab
kód ahol a printf () írta és látni

318
00:14:25,610 --> 00:14:26,730
mi folyik ott.

319
00:14:26,730 --> 00:14:29,924
>> De általában azt feltételezzük, hogy
A kód, amit kapsz működik.

320
00:14:29,924 --> 00:14:31,340
Feltételezzük, hogy a printf () dolgozik.

321
00:14:31,340 --> 00:14:33,170
Azt feltételezzük, hogy GetInt () dolgozik.

322
00:14:33,170 --> 00:14:35,170
Tehát nincs szükség
belép ezeket a funkciókat.

323
00:14:35,170 --> 00:14:37,170
De ha van funkciók
saját maga által írt

324
00:14:37,170 --> 00:14:39,060
hogy az ellenőrizni kívánt
hogy mi folyik itt,

325
00:14:39,060 --> 00:14:41,200
amit szeretne lépni
be ezt a tisztséget.

326
00:14:41,200 --> 00:14:43,940
>> Akkor most mi csak megy
átlépni ezt a kódrészletet.

327
00:14:43,940 --> 00:14:44,485
Tehát lássuk.

328
00:14:44,485 --> 00:14:46,547
Ó, nyomtatás, "Ó hai, hogyan
sok változás áll fenn? "

329
00:14:46,547 --> 00:14:47,130
Nem érdekel minket.

330
00:14:47,130 --> 00:14:49,830
Tudjuk, hogy ez működik,
így átlépni azt.

331
00:14:49,830 --> 00:14:53,290
>> Tehát n, ami a mi úszó, hogy
mi már initialized-- vagy declared--

332
00:14:53,290 --> 00:14:56,810
akár a tetején, mi most
egyenlő, hogy a GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Úgyhogy átlépni ezt.

334
00:14:57,810 --> 00:14:59,580
És látjuk a
alsó itt, a program

335
00:14:59,580 --> 00:15:03,360
arra ösztönöz, hogy adjon meg egy értéket.

336
00:15:03,360 --> 00:15:08,580
Úgyhogy bemeneti értéket akarunk
kipróbálni itt, ami 0,41.

337
00:15:08,580 --> 00:15:09,160
Nagy.

338
00:15:09,160 --> 00:15:12,780
>> Tehát most n-- srácok lásd
Itt, a bottom-- ez

339
00:15:12,780 --> 00:15:15,140
stored-- mert
Nem kerek mégis, ez

340
00:15:15,140 --> 00:15:19,540
alatt az, mint a hatalmas
úszó, amely 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
ami elég közel van a
célokra, most, hogy 0,41.

342
00:15:22,550 --> 00:15:26,090
És aztán majd meglátjuk később, mint mi
tovább átlépve a program,

343
00:15:26,090 --> 00:15:29,850
után itt, n vált
lekerekített és cent lett 41.

344
00:15:29,850 --> 00:15:30,350
Nagy.

345
00:15:30,350 --> 00:15:32,230
Tehát tudjuk, hogy mi a kerekítés dolgozik.

346
00:15:32,230 --> 00:15:34,700
Tudjuk, hogy mi van a
megfelelő számú cent,

347
00:15:34,700 --> 00:15:36,990
így tudjuk, hogy ez
nem igazán a probléma.

348
00:15:36,990 --> 00:15:40,050
>> Tehát továbbra is lépve
tovább ebben a programban.

349
00:15:40,050 --> 00:15:40,900
Mi megy itt.

350
00:15:40,900 --> 00:15:46,139
És így, miután ezt a kódsort, mi
tudnia kell, hogy hány negyedévben már.

351
00:15:46,139 --> 00:15:46,680
Mi átlépni.

352
00:15:46,680 --> 00:15:52,040
És látod mi, sőt, egy
negyedévben mert már levontuk 25

353
00:15:52,040 --> 00:15:53,790
a mi kezdeti értéke 41.

354
00:15:53,790 --> 00:15:55,890
És mi van a 16 bal a mi cent.

355
00:15:55,890 --> 00:15:58,830
>> Mindenki érti, hogyan
A program átlépve

356
00:15:58,830 --> 00:16:02,980
és miért cent mára 16
és miért most, érmék vált 1?

357
00:16:02,980 --> 00:16:04,610
Mindenki követő logika?

358
00:16:04,610 --> 00:16:05,110
Hűvös.

359
00:16:05,110 --> 00:16:07,860
Tehát ahogy ezen a ponton, a
programban dolgozik, ugye?

360
00:16:07,860 --> 00:16:09,797
Tudjuk, hogy csinál pontosan
mi akarjuk.

361
00:16:09,797 --> 00:16:11,880
És valójában nem
kell kinyomtatni, jaj, mit

362
00:16:11,880 --> 00:16:14,430
van cent ezen a ponton,
mi érméket ezen a ponton.

363
00:16:14,430 --> 00:16:17,170
>> Továbbra is folyik a programon keresztül.

364
00:16:17,170 --> 00:16:18,100
Átlép.

365
00:16:18,100 --> 00:16:18,620
Hűvös.

366
00:16:18,620 --> 00:16:19,700
Mi megy át Dimes.

367
00:16:19,700 --> 00:16:20,200
Nagy.

368
00:16:20,200 --> 00:16:22,367
Látjuk, hogy ez hozott
off 0,10 $ egy fillért sem.

369
00:16:22,367 --> 00:16:23,450
És most van két érmét.

370
00:16:23,450 --> 00:16:25,260
Így van.

371
00:16:25,260 --> 00:16:31,555
>> Mi megy át fillérekért, és azt látjuk,
hogy megvan maradt cent.

372
00:16:31,555 --> 00:16:32,680
Hmm, ez furcsa.

373
00:16:32,680 --> 00:16:37,540
Akár itt a programot, azt kellett volna
hogy levonjuk én fillérekért.

374
00:16:37,540 --> 00:16:39,400
Talán csak nem voltam
csinálja vonal jobb.

375
00:16:39,400 --> 00:16:42,190
És sajnos, láthatjuk
Itt, mert tudjuk,

376
00:16:42,190 --> 00:16:44,360
hogy fokozzák
vonalakon keresztül 32 és 33,

377
00:16:44,360 --> 00:16:50,560
ez az, ahol a programunk
helytelenül volt változók futni.

378
00:16:50,560 --> 00:16:55,136
Így meg tudjuk nézni és látni, ó,
Én kivonva cent itt,

379
00:16:55,136 --> 00:16:57,010
de nem vagyok ténylegesen
hozzátéve, hogy az én érme értékét.

380
00:16:57,010 --> 00:16:57,860
Én vagyok hozzá, hogy cent.

381
00:16:57,860 --> 00:17:00,234
És nem akarom felvenni
cent, szeretném hozzátenni, hogy érméket.

382
00:17:00,234 --> 00:17:05,420
Tehát, ha változtatni kell, érmék,
mi van egy munkaprogramot.

383
00:17:05,420 --> 00:17:06,730
Tudok futni check50.

384
00:17:06,730 --> 00:17:11,063
Tudod csak lépjen ki a GDB jobb
Itt majd futtassa check50 újra.

385
00:17:11,063 --> 00:17:11,938
Én is csak ezt.

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

387
00:17:14,822 --> 00:17:18,480
Azt kell, hogy kapzsi.

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

389
00:17:19,940 --> 00:17:22,819
És itt, ez a nyomtatás
ki a helyes választ.

390
00:17:22,819 --> 00:17:26,569
>> Tehát ahogy ti is látni, GDB
egy igazán hatékony eszköz

391
00:17:26,569 --> 00:17:29,940
amikor már annyira kód
folyik, és annyi változó

392
00:17:29,940 --> 00:17:32,510
hogy nehéz számunkra, mint
egy ember, hogy nyomon követni.

393
00:17:32,510 --> 00:17:35,360
A számítógép, a GDB
debugger, amely képes

394
00:17:35,360 --> 00:17:37,020
nyomon követni mindent.

395
00:17:37,020 --> 00:17:40,480
Tudom, a Visionaire, srácok valószínűleg
Lehet, hogy a hit néhány szegmentációs hiba

396
00:17:40,480 --> 00:17:43,150
mert futottak
a határokat a tömb.

397
00:17:43,150 --> 00:17:46,510
A példában Caesar, ez
Pontosan azt, amit idehaza.

398
00:17:46,510 --> 00:17:50,060
>> Így elfelejtettem, hogy ellenőrizze a
mi lenne, ha én

399
00:17:50,060 --> 00:17:52,510
nem volt két parancssori paramétereket.

400
00:17:52,510 --> 00:17:53,880
Csak nem ebbe az ellenőrzést.

401
00:17:53,880 --> 00:17:57,380
És így ha futok Debug-- állítottam
én töréspontot ott.

402
00:17:57,380 --> 00:17:58,055
Futok Debug.

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

404
00:18:15,880 --> 00:18:16,550
>> OKÉ.

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

406
00:18:17,050 --> 00:18:20,350
Tehát tulajdonképpen, GDB kellett volna
hogy azt mondta nekem, hogy

407
00:18:20,350 --> 00:18:22,300
volt szegmentációs hiba van.

408
00:18:22,300 --> 00:18:24,883
Nem tudom, mi folyik
ott, de amikor futott,

409
00:18:24,883 --> 00:18:25,590
ez működött.

410
00:18:25,590 --> 00:18:29,410
Amikor futtatja sornyi kódot keresztül, és
GDB talán csak hirtelen kilép rád,

411
00:18:29,410 --> 00:18:31,540
felmegy, és megnézzük, mi a piros hiba.

412
00:18:31,540 --> 00:18:33,930
Ez megmondom, hé, te
Volt egy szegmentációs hiba,

413
00:18:33,930 --> 00:18:38,550
ami azt jelenti, hogy a megnyitni kívánt
térben egy tömbben, hogy nem létezik.

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

415
00:18:39,050 --> 00:18:43,280
>> Tehát a következő probléma
beállítani ezen a héten, srácok

416
00:18:43,280 --> 00:18:45,600
Valószínűleg sok
változók lebeg.

417
00:18:45,600 --> 00:18:48,560
Ugye nem lesz biztos benne, mi
jelentenek ezek egy bizonyos ponton.

418
00:18:48,560 --> 00:18:53,560
Tehát GDB valóban segít kitalálni
hogy mi mindannyian egyenlő

419
00:18:53,560 --> 00:18:55,940
és hogy képes látni, hogy vizuálisan.

420
00:18:55,940 --> 00:19:01,995
Ha valaki világos, hogy mi
sem, hogy dolgozik?

421
00:19:01,995 --> 00:19:02,495
Hűvös.

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

423
00:19:10,121 --> 00:19:10,620
Minden rendben.

424
00:19:10,620 --> 00:19:14,260
Így azután, hogy vagyunk
fog merülni jobbra

425
00:19:14,260 --> 00:19:17,562
figyelembe négy különböző
típusú fajta erre a hétre.

426
00:19:17,562 --> 00:19:19,520
Hányan vagytok, első
Az összes, mielőtt elkezdjük,

427
00:19:19,520 --> 00:19:23,020
Elolvastam a teljes specifikáció pset3?

428
00:19:23,020 --> 00:19:23,824
OKÉ.

429
00:19:23,824 --> 00:19:24,740
Büszke vagyok a srácok.

430
00:19:24,740 --> 00:19:29,110
Ez olyan, mintha a fele az osztályban, ami
lényegesen több, mint a múltkor.

431
00:19:29,110 --> 00:19:33,950
>> Szóval ez jó, mert amikor
beszélünk a tartalmat

432
00:19:33,950 --> 00:19:36,170
A lecture-- vagy sajnálom,
A section-- szeretem

433
00:19:36,170 --> 00:19:38,210
kapcsolódnak egy csomó, hogy
vissza, amit a PSET van

434
00:19:38,210 --> 00:19:40,210
és hogyan szeretné
végre, hogy a PSET.

435
00:19:40,210 --> 00:19:42,400
Tehát, ha jön, amelynek
olvassa a specifikációt, akkor az

436
00:19:42,400 --> 00:19:45,510
sokkal könnyebb az Ön számára, hogy megértsék
mit beszélek, amikor azt mondom,

437
00:19:45,510 --> 00:19:48,720
ó hé, ez lehet egy igazán
jó hely, hogy végre ez a fajta.

438
00:19:48,720 --> 00:19:52,870
Tehát azok, akik elolvasták a
spec tudom, hogy részeként a PSET,

439
00:19:52,870 --> 00:19:54,900
fogsz kell
levelet típusú sort.

440
00:19:54,900 --> 00:19:58,670
Tehát ez lehet nagyon hasznos
Egy csomó van ma.

441
00:19:58,670 --> 00:20:01,760
>> Szóval majd elindul,
Lényegében, a legegyszerűbb típus

442
00:20:01,760 --> 00:20:04,580
A sort, a kiválasztási sorrend.

443
00:20:04,580 --> 00:20:06,800
A tipikus algoritmus
hogyan megyünk erről

444
00:20:06,800 --> 00:20:10,460
is-- Dávid ment át ezeket mind
előadás, úgyhogy gyorsan mozognak

445
00:20:10,460 --> 00:20:13,900
here-- alapvetően, akkor
Van egy sor értékek.

446
00:20:13,900 --> 00:20:17,170
És akkor megtalálja a
legkisebb szétválogatás nélküli értéke

447
00:20:17,170 --> 00:20:20,200
és akkor cseréld azt az értéket
Az első nem válogatott értéket.

448
00:20:20,200 --> 00:20:22,700
Aztán csak folyamatos ismétlése
a többi a lista.

449
00:20:22,700 --> 00:20:25,740
>> És itt egy vizuális magyarázat
Az, hogy hogyan fog működni.

450
00:20:25,740 --> 00:20:30,460
Így például, ha voltunk kezdeni
egy sor öt elem, index

451
00:20:30,460 --> 00:20:35,910
0-4, 3, 5, 2, 6, és 4 értékeket
helyezni a array-- most így,

452
00:20:35,910 --> 00:20:38,530
mi csak fog vállalni
hogy ezek mind nem válogatott

453
00:20:38,530 --> 00:20:41,130
mert még nem tesztelték másképp.

454
00:20:41,130 --> 00:20:44,130
>> Szóval, hogy a válogatott a fajta lenne
a munka, hogy ez az első

455
00:20:44,130 --> 00:20:46,800
végigmenni a teljes
A szétválogatás nélkül tömb.

456
00:20:46,800 --> 00:20:49,120
Úgy vedd ki a legkisebb értéket.

457
00:20:49,120 --> 00:20:51,750
Ebben az esetben a 3, jobbra
Most, a legkisebb.

458
00:20:51,750 --> 00:20:52,680
Egyre 5.

459
00:20:52,680 --> 00:20:55,620
Nem, 5 nem nagyobb than--
vagy sajnálom, nem kevesebb than-- 3.

460
00:20:55,620 --> 00:20:57,779
Így a minimális érték még mindig 3.

461
00:20:57,779 --> 00:20:58,695
És akkor kapsz 2.

462
00:20:58,695 --> 00:21:00,990
A számítógép látja, ó, 2. kevesebb, mint 3.

463
00:21:00,990 --> 00:21:02,750
2 most kell lennie a minimum érték.

464
00:21:02,750 --> 00:21:06,630
És így 2-swap, hogy első érték.

465
00:21:06,630 --> 00:21:10,702
>> Tehát miután egy menetben, akkor valóban látni
hogy a 2. és a 3. felcserélődnek.

466
00:21:10,702 --> 00:21:13,910
És mi csak folytatódni fog csinál
ez ismét a többi a tömb.

467
00:21:13,910 --> 00:21:17,660
Szóval megyünk, csak végigmenni
Az elmúlt négy indexek a tömb.

468
00:21:17,660 --> 00:21:20,670
Meglátjuk, hogy a 3.
A következő minimális értéket.

469
00:21:20,670 --> 00:21:23,240
Mi is így fogjuk cserélni, hogy a 4.

470
00:21:23,240 --> 00:21:26,900
És akkor mi csak fog tartani
fut át, amíg végül, akkor

471
00:21:26,900 --> 00:21:33,730
eljut egy rendezett tömbben, ahol
2, 3, 4, 5, és 6. minden rendezve.

472
00:21:33,730 --> 00:21:37,530
Mindenki érti a logikát
hogyan válogatott egyfajta működik?

473
00:21:37,530 --> 00:21:39,669
>> Csak van valami
egy minimális értéket.

474
00:21:39,669 --> 00:21:41,210
Te követi nyomon a mi az.

475
00:21:41,210 --> 00:21:45,170
És ha találsz, akkor cseréld
az első érték a array--

476
00:21:45,170 --> 00:21:48,740
vagy, nem az első value--
A következő érték a tömbben.

477
00:21:48,740 --> 00:21:50,150
Hűvös.

478
00:21:50,150 --> 00:21:55,460
>> Tehát ahogy ti egyfajta
láttam egy pillantás,

479
00:21:55,460 --> 00:21:58,450
fogunk pszeudókód ezt.

480
00:21:58,450 --> 00:22:02,510
Tehát, ha a srácok a hátsó szeretné
csoportot alkotnak, mindenki az asztalnál

481
00:22:02,510 --> 00:22:06,170
alkothat egy kicsit partnere, megyek
adni nektek, mint három perc

482
00:22:06,170 --> 00:22:08,190
hogy csak beszélni keresztül
A logika, angol,

483
00:22:08,190 --> 00:22:14,161
Az, hogy hogyan lehet, hogy végre
pszeudokódja, hogy írjon egy kiválasztási sorrend.

484
00:22:14,161 --> 00:22:14,910
És ott van a cukorkát.

485
00:22:14,910 --> 00:22:16,118
Kérlek, gyere fel és kap édességet.

486
00:22:16,118 --> 00:22:19,520
Ha a hátsó, és szeretné
édességet, tudok dobni édességet rád.

487
00:22:19,520 --> 00:22:22,850
Igazából nem you-- hűvös.

488
00:22:22,850 --> 00:22:23,552
Oh bocsánat.

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

490
00:22:26,751 --> 00:22:27,250
OKÉ.

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

492
00:25:23,880 --> 00:25:27,140
>> Tehát, ha szeretnénk, mint
egy osztály, írási pszeudokódja

493
00:25:27,140 --> 00:25:30,466
hogyan lehetne megközelíteni
ezt a problémát, csak nyugodtan.

494
00:25:30,466 --> 00:25:32,340
Megyek körül, és,
annak érdekében, kérdezze csoportok

495
00:25:32,340 --> 00:25:35,065
A következő sor
mit kell tennünk.

496
00:25:35,065 --> 00:25:37,840
Tehát, ha akartok kezdeni
is, mi az első dolog,

497
00:25:37,840 --> 00:25:40,600
a teendő, ha akarsz
végre egy módja annak, hogy megoldja ezt a programot

498
00:25:40,600 --> 00:25:43,480
szelektíven rendezni egy listát?

499
00:25:43,480 --> 00:25:46,349
Nézzük csak feltételezni tudjuk
van egy tömbben, rendben?

500
00:25:46,349 --> 00:25:49,088
>> Közönség: Azt akarod, hogy egyfajta
fajta [hallhatatlan], hogy te

501
00:25:49,088 --> 00:25:50,420
fut át ​​az egész tömböt.

502
00:25:50,420 --> 00:25:51,128
>> ANDI Peng: Jobb.

503
00:25:51,128 --> 00:25:54,100
Szóval fogsz szeretné iterációkhoz
keresztül minden helyet, igaz?

504
00:25:54,100 --> 00:26:05,490
Olyan nagy.

505
00:26:05,490 --> 00:26:08,600
Ha akartok, hogy nekem a
következő line-- igen, hátul.

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

507
00:26:11,414 --> 00:26:13,290
>> Közönség: Nézd meg őket
mindezt a legkisebb.

508
00:26:13,290 --> 00:26:14,248
>> ANDI Peng: Tessék.

509
00:26:14,248 --> 00:26:17,438
Ezért szeretnénk, hogy menjen át, és ellenőrizze, hogy
mi a minimális érték, ugye?

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

511
00:26:22,110 --> 00:26:24,840
Megyek rövidítésére, hogy a "min."

512
00:26:24,840 --> 00:26:27,658
Mit akartok csinálni után
megtalálta a minimális értéket?

513
00:26:27,658 --> 00:26:28,533
>> Közönség: [hallható]

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

515
00:26:29,942 --> 00:26:33,150
ANDI Peng: Szóval fogsz akar
kapcsolja az első tömb,

516
00:26:33,150 --> 00:26:33,650
ugye?

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

518
00:26:45,120 --> 00:26:46,850
Ez az elején, én fogok mondani.

519
00:26:46,850 --> 00:26:47,220
Minden rendben.

520
00:26:47,220 --> 00:26:50,386
Tehát most, hogy már cserélték az első
Egy, mit akarsz csinálni utána?

521
00:26:50,386 --> 00:26:54,840
Tehát most már tudjuk, hogy ez itt
kell lennie a legkisebb érték, ugye?

522
00:26:54,840 --> 00:26:58,310
Akkor van egy további pihenésre
a tömb ez nem válogatott.

523
00:26:58,310 --> 00:27:01,569
Szóval mit akarsz itt csinálni, ha
srácok akar adni nekem a következő sorban?

524
00:27:01,569 --> 00:27:04,610
Közönség: Tehát azt szeretnénk, hogy ismételget
keresztül a többi a tömb.

525
00:27:04,610 --> 00:27:05,276
ANDI Peng: Igen.

526
00:27:05,276 --> 00:27:09,857
És így mit iterációjával keresztül
fajta jelenti azt valószínűleg szükséged?

527
00:27:09,857 --> 00:27:10,440
Milyen típusú of--

528
00:27:10,440 --> 00:27:12,057
>> Közönség: Ó, egy újabb változó?

529
00:27:12,057 --> 00:27:13,890
ANDI Peng: Valószínűleg
a másik a loop, ugye?

530
00:27:13,890 --> 00:27:28,914
Szóval valószínűleg akarnak
iterációkhoz through-- nagy.

531
00:27:28,914 --> 00:27:31,830
És akkor fogsz visszatérni, és
valószínűleg ellenőrizni a minimális újra,

532
00:27:31,830 --> 00:27:32,100
ugye?

533
00:27:32,100 --> 00:27:34,975
És te fogsz ismételgetni
ezt, mert a hurkok csak megy

534
00:27:34,975 --> 00:27:36,010
hogy folyamatosan fut, ugye?

535
00:27:36,010 --> 00:27:39,190
>> Tehát ahogy ti is látni, mi
Van egy általános pszeudokódja

536
00:27:39,190 --> 00:27:41,480
Az, hogy hogyan akarjuk ezt a programot, hogy az.

537
00:27:41,480 --> 00:27:46,646
Ez hajtogat itt, mit teszünk
tipikusan kell írni a kódunkat

538
00:27:46,646 --> 00:27:49,270
ha azt akarjuk, hogy halad végig egy
tömb, milyen struktúrában?

539
00:27:49,270 --> 00:27:51,030
Azt hiszem Christabel
Már mondtam ilyet.

540
00:27:51,030 --> 00:27:51,500
>> Közönség: A hurok.

541
00:27:51,500 --> 00:27:52,160
>> ANDI Peng: egy ciklusban?

542
00:27:52,160 --> 00:27:52,770
Pontosan.

543
00:27:52,770 --> 00:27:56,060
Tehát valószínűleg ez
lesz egy ciklusban.

544
00:27:56,060 --> 00:27:59,240
Mi a csekk itt fog jelenti?

545
00:27:59,240 --> 00:28:02,536
Általában, ha azt szeretnénk, hogy ellenőrizze
ha valami olyasmi else--

546
00:28:02,536 --> 00:28:03,270
>> Közönség: Ha.

547
00:28:03,270 --> 00:28:06,790
>> ANDI Peng: Egy ha, ugye?

548
00:28:06,790 --> 00:28:10,790
És akkor a swap Itt fogunk
megy át később, mert Dávid

549
00:28:10,790 --> 00:28:12,770
ment keresztül, hogy előadást is.

550
00:28:12,770 --> 00:28:14,580
És akkor a második hajtogat implies--

551
00:28:14,580 --> 00:28:15,120
>> Közönség: Egy másik hurok.

552
00:28:15,120 --> 00:28:16,745
>> ANDI Peng: --another a hurok, pontosan.

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

554
00:28:19,870 --> 00:28:22,000
Tehát, ha keresünk
Ebben rendesen, mi

555
00:28:22,000 --> 00:28:24,680
Láthatjuk, hogy mi vagyunk talán
Szükségem lesz egy beágyazott hurok

556
00:28:24,680 --> 00:28:28,330
A feltételes utasítás ott
majd a tényleges kódrészletet, ami

557
00:28:28,330 --> 00:28:31,360
majd cserélni az értékeket.

558
00:28:31,360 --> 00:28:35,980
Szóval már csak általában írásos
Egy pszeudokódja kódot itt.

559
00:28:35,980 --> 00:28:38,910
És akkor mi történt valójában
fizikailag, mint osztály,

560
00:28:38,910 --> 00:28:40,700
megpróbálja végrehajtani ezt ma.

561
00:28:40,700 --> 00:28:42,486
Menjünk vissza ebbe 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
Miért van ez nem-- ez van.

565
00:28:51,754 --> 00:28:52,253
OKÉ.

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

567
00:28:55,834 --> 00:28:57,500
Sajnáljuk, hadd próbálja nagyítás egy kicsit.

568
00:28:57,500 --> 00:28:59,310
Ott vagyunk.

569
00:28:59,310 --> 00:29:05,060
Minden csinálok itt van már létre
A program a "kiválasztás / sort.c."

570
00:29:05,060 --> 00:29:10,860
Létrehoztam egy sor kilenc
értékek, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Jelenleg csak tudsz
lásd, azok rendezetlen.

572
00:29:14,370 --> 00:29:17,880
n lesz a számot,
megmondja, hogy az összeg az értékek

573
00:29:17,880 --> 00:29:18,920
üzenetünk van a tömbben.

574
00:29:18,920 --> 00:29:20,670
Ebben az esetben már kilenc értékeket.

575
00:29:20,670 --> 00:29:23,760
És én most kaptam egy hurok itt
hogy kiírja a szétválogatás nélkül tömb.

576
00:29:23,760 --> 00:29:28,370
>> És a végén, én is kaptam egy részére
hurok, hogy mindig csak ki újra.

577
00:29:28,370 --> 00:29:32,070
Tehát elméletileg, ha ez a program
helyesen működik, a végén,

578
00:29:32,070 --> 00:29:35,670
látnod kell egy nyomtatott for ciklus
amelyben az 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 egyaránt helyesen annak érdekében.

580
00:29:39,310 --> 00:29:43,410
>> Tehát van a pszeudokódja itt.

581
00:29:43,410 --> 00:29:46,090
Akar valaki az alábbiakra: Én csak
megyek kérni volunteers--

582
00:29:46,090 --> 00:29:49,540
mondja meg pontosan, hogy mit kell megadnia, ha
akarunk, először csak ismételget

583
00:29:49,540 --> 00:29:52,840
az elején ez a tömb?

584
00:29:52,840 --> 00:29:55,204
Mi a kódsort vagyok
Valószínűleg szükségem lesz itt?

585
00:29:55,204 --> 00:29:56,990
>> Közönség: [hallható]

586
00:29:56,990 --> 00:29:59,010
>> ANDI Peng: Igen, úgy érzi,
Ingyenes alábbiakra: bocs, akkor

587
00:29:59,010 --> 00:30:02,318
Nem kell állni up-- érzést
szabadon emelje fel a hangját egy kicsit.

588
00:30:02,318 --> 00:30:08,190
>> Közönség: Az int i értéke 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI Peng: Igen, jó.

590
00:30:10,690 --> 00:30:15,220
>> Közönség: i-nél kisebb tömb hossza.

591
00:30:15,220 --> 00:30:19,630
>> ANDI Peng: Szóval tartsd
bánja itt, mert

592
00:30:19,630 --> 00:30:23,060
Nem kell, hogy a funkció
azt mondja, a hossza a tömb,

593
00:30:23,060 --> 00:30:25,790
már van egy
értéket, amely tárolja, hogy.

594
00:30:25,790 --> 00:30:27,920
Jobb?

595
00:30:27,920 --> 00:30:31,010
A másik dolog, hogy tartsa
A mind-- egy tömbben

596
00:30:31,010 --> 00:30:33,940
Kilenc értékek, melyek az indexek?

597
00:30:33,940 --> 00:30:38,720
Mondjuk úgy, hogy ez a tömb volt, 0-3.

598
00:30:38,720 --> 00:30:41,500
Látod, hogy az utolsó
index tulajdonképpen 3.

599
00:30:41,500 --> 00:30:45,530
Ez nem 4, bár van
négy tömb elemeinek.

600
00:30:45,530 --> 00:30:49,866
>> Tehát itt, van, hogy nagyon óvatosnak kell
A mi helyzetünk a hossza

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

602
00:30:50,490 --> 00:30:51,948
>> Közönség: Nem lenne n mínusz 1?

603
00:30:51,948 --> 00:30:54,440
ANDI Peng: Ez lesz
n mínusz 1, pontosan.

604
00:30:54,440 --> 00:30:57,379
Van ennek értelme, miért
ez n mínusz 1, mindenki?

605
00:30:57,379 --> 00:30:58,920
Ez azért van, mert a tömbök nulla indexelt.

606
00:30:58,920 --> 00:31:02,010
Kezdik 0 és fuss n-ig mínusz 1.

607
00:31:02,010 --> 00:31:03,210
Igen, ez egy kicsit trükkös.

608
00:31:03,210 --> 00:31:03,730
OKÉ.

609
00:31:03,730 --> 00:31:05,929
És akkor--

610
00:31:05,929 --> 00:31:08,054
Közönség: Isnt'1, hogy
már gondoskodott ellenére,

611
00:31:08,054 --> 00:31:11,400
ha csak nem azt mondja, "kisebb vagy
egyenlő ", és csak azt mondom," kevesebb, mint? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI Peng: Ez egy
nagyon jó kérdés.

613
00:31:13,108 --> 00:31:13,630
Szóval igen.

614
00:31:13,630 --> 00:31:17,410
Hanem, az is, hogy vagyunk
végrehajtása ellenőrzésének jogát,

615
00:31:17,410 --> 00:31:19,120
meg kell összehasonlítani két érték.

616
00:31:19,120 --> 00:31:21,009
Szóval tényleg akar
hagyja a "hogy" üres.

617
00:31:21,009 --> 00:31:23,050
Mert ha összehasonlítjuk
ez, hogy nem fogod

618
00:31:23,050 --> 00:31:25,530
Van valami után
összehasonlítani, ugye?

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

620
00:31:27,460 --> 00:31:29,297
Tehát i ++.

621
00:31:29,297 --> 00:31:30,380
Adjuk hozzá a zárójelben.

622
00:31:30,380 --> 00:31:30,880
Hoppá.

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

624
00:31:33,950 --> 00:31:34,710
Nagy.

625
00:31:34,710 --> 00:31:39,117
Így már a kezdet
a mi külső hurok.

626
00:31:39,117 --> 00:31:41,450
Tehát most akkor ehhez
létrehozunk egy változót tartása

627
00:31:41,450 --> 00:31:43,085
pályán a legkisebb érték, ugye?

628
00:31:43,085 --> 00:31:45,751
Tudja valaki akar adni nekem a
kódsort tenne ilyet?

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

630
00:31:48,700 --> 00:31:53,570
Mire van szükségünk, ha megyünk
hogy a tárolni kívánt valamit?

631
00:31:53,570 --> 00:31:55,047
>> Jobb.

632
00:31:55,047 --> 00:31:57,630
Talán jobb név, hogy
lenne be-- "temp" teljesen works--

633
00:31:57,630 --> 00:32:00,655
Talán egy találóan elnevezett lenne,
ha azt akarjuk, a legkisebb value--

634
00:32:00,655 --> 00:32:01,624
>> Közönség: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI Peng: min, ott megyünk.

636
00:32:02,790 --> 00:32:05,230
min lenne jó.

637
00:32:05,230 --> 00:32:08,340
És így van, mit tegyünk
akarjuk inicializálni azt?

638
00:32:08,340 --> 00:32:09,620
Ez egy kicsit trükkös.

639
00:32:09,620 --> 00:32:13,580
Mert most a
elején ez a tömb,

640
00:32:13,580 --> 00:32:15,730
Ön még nem nézett semmit, ugye?

641
00:32:15,730 --> 00:32:19,200
Tehát mi, automatikusan, ha
mi csak a i értéke 0,

642
00:32:19,200 --> 00:32:22,302
mit akarunk inicializálni
Első minimális értéket?

643
00:32:22,302 --> 00:32:22,802
Közönség: i.

644
00:32:22,802 --> 00:32:24,790
ANDI Peng: i, pontosan.

645
00:32:24,790 --> 00:32:27,040
Christabel, miért akarjuk
inicializálása hogy én?

646
00:32:27,040 --> 00:32:28,510
>> Közönség: mert jól,
kezdünk 0.

647
00:32:28,510 --> 00:32:31,660
Szóval azért, mert nincs mit összehasonlítani
azt a minimális lesz a vége, hogy 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI Peng: Pontosan.

649
00:32:32,451 --> 00:32:34,400
Így hát pontosan így van.

650
00:32:34,400 --> 00:32:36,780
Mert mi van valójában nem
nézett semmit,

651
00:32:36,780 --> 00:32:38,680
nem tudjuk, mi a legkisebb érték.

652
00:32:38,680 --> 00:32:41,960
Azt akarjuk, hogy csak inicializálni azt
i, amelyek jelenleg, itt van.

653
00:32:41,960 --> 00:32:44,750
És ahogy továbbra is
lejjebb ez a tömb,

654
00:32:44,750 --> 00:32:48,122
majd meglátjuk, hogy az egyes
További át, i megnöveli.

655
00:32:48,122 --> 00:32:49,830
És így ezen a ponton,
i valószínűleg lesz

656
00:32:49,830 --> 00:32:52,329
azt szeretnék, hogy a minimális,
mert lesz bármi

657
00:32:52,329 --> 00:32:54,520
a kezdet A szétválogatás nélkül tömb.

658
00:32:54,520 --> 00:32:55,270
Hűvös.

659
00:32:55,270 --> 00:32:58,720
>> Tehát most szeretné adni
egy for ciklus itt ez

660
00:32:58,720 --> 00:33:03,225
fog halad végig a
szétválogatás nélküli, vagy a többi ezt a tömböt.

661
00:33:03,225 --> 00:33:05,808
Akar valaki adjon nekem egy
kódsort tenne ilyet?

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

663
00:33:08,870 --> 00:33:11,330
Hint-- mi kell ide?

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

665
00:33:17,320 --> 00:33:18,820
Mi fog menni ez a for ciklus?

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

667
00:33:19,465 --> 00:33:21,590
Közönség: Szóval mi lenne akar
eltérő egész szám,

668
00:33:21,590 --> 00:33:25,080
mert kifutunk át a többi
A tömb helyett i, így talán

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

670
00:33:25,760 --> 00:33:27,301
>> ANDI Peng: Igen, j hangzik nekem.

671
00:33:27,301 --> 00:33:27,850
Eredmény?

672
00:33:27,850 --> 00:33:33,930
>> Közönség: Szóval lenne i + 1, mert
kezded a következő érték.

673
00:33:33,930 --> 00:33:40,395
És akkor a end-- így ismét, j
n-nél kisebb mínusz 1, majd j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI Peng: Nagy.

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

676
00:33:48,510 --> 00:33:52,750
>> És akkor itt fogunk akarni
hogy ellenőrizze, hogy ha a feltétel teljesül,

677
00:33:52,750 --> 00:33:53,250
ugye?

678
00:33:53,250 --> 00:33:55,740
Mivel azt szeretnénk, hogy
változtatni a minimális érték

679
00:33:55,740 --> 00:33:58,700
Ha ez valóban kisebb, mint amit
te hasonlítsa össze, ugye?

680
00:33:58,700 --> 00:34:01,146
Akkor most mit akarnak itt?

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

682
00:34:04,160 --> 00:34:04,897
Ellenőrizze, hogy.

683
00:34:04,897 --> 00:34:06,730
Milyen típusú nyilatkozatot
fogunk valószínűleg lesz

684
00:34:06,730 --> 00:34:08,389
ti szeretné használni, ha
szeretné ellenőrizni valamit?

685
00:34:08,389 --> 00:34:09,360
>> Közönség: if.

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

687
00:34:10,485 --> 00:34:13,155
Szóval if-- és mi lesz
a feltétellel, hogy azt akarjuk belül

688
00:34:13,155 --> 00:34:13,988
a mi if?

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

690
00:34:18,255 --> 00:34:22,960
>> KÖZÖNSÉG: Ha a j értékének
kevesebb, mint az értéke én--

691
00:34:22,960 --> 00:34:24,600
>> ANDI Peng: Pontosan.

692
00:34:24,600 --> 00:34:27,480
Tehát if-- így ez a tömb az úgynevezett "array".

693
00:34:27,480 --> 00:34:27,980
Nagy.

694
00:34:27,980 --> 00:34:30,465
Tehát, ha array-- mi volt ez?

695
00:34:30,465 --> 00:34:31,090
Mondd újra.

696
00:34:31,090 --> 00:34:39,590
>> Közönség: Ha array-j kevesebb, mint
array-i, akkor mi lenne változtatni a min.

697
00:34:39,590 --> 00:34:41,590
Így a min lenne j.

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

699
00:34:44,590 --> 00:34:47,249
>> ANDI Peng: Van ennek értelme?

700
00:34:47,249 --> 00:34:48,670
OKÉ.

701
00:34:48,670 --> 00:34:52,929
És most itt lent, mi valójában
kívánja megvalósítani a swap, ugye?

702
00:34:52,929 --> 00:34:58,285
Szóval emlékszem, az előadás, hogy Dávid, amikor
akart cserélni the-- mi volt

703
00:34:58,285 --> 00:34:59,996
it-- narancslevet és milk--

704
00:34:59,996 --> 00:35:01,150
>> Közönség: Ez volt a bruttó.

705
00:35:01,150 --> 00:35:02,816
>> ANDI Peng: Igen, ez a fajta bruttó.

706
00:35:02,816 --> 00:35:05,310
De ez egy nagyon jó
koncepciót bemutató ideje.

707
00:35:05,310 --> 00:35:08,430
Szóval szerintem az értékeidet itt.

708
00:35:08,430 --> 00:35:10,794
Van egy sor
min, egy sor I,

709
00:35:10,794 --> 00:35:12,460
vagy bármi akartuk cserélni itt.

710
00:35:12,460 --> 00:35:15,310
És valószínűleg nem tudod öntsük őket
egymást ugyanabban az időben, jobb?

711
00:35:15,310 --> 00:35:17,180
Szóval mi megyünk
hogy létre kell hozni ide

712
00:35:17,180 --> 00:35:19,126
annak érdekében, hogy a csere az értékeket helyesen?

713
00:35:19,126 --> 00:35:19,820
>> Közönség: Egy átmeneti változó.

714
00:35:19,820 --> 00:35:21,370
>> ANDI Peng: Egy átmeneti változó.

715
00:35:21,370 --> 00:35:22,570
Tehát lássuk int temp.

716
00:35:22,570 --> 00:35:25,681
Lásd, ez lenne a jobb
ideje az alábbiakra: hé, mi volt ez?

717
00:35:25,681 --> 00:35:26,180
OKÉ.

718
00:35:26,180 --> 00:35:29,800
Tehát ez lett volna jobb
ideje, hogy nevét a változó "temp".

719
00:35:29,800 --> 00:35:30,730
Tehát lássuk int temp.

720
00:35:30,730 --> 00:35:32,563
Mit fogunk
beállított hőmérséklet egyenlő itt?

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

722
00:35:34,752 --> 00:35:35,335
Közönség: Min?

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

724
00:35:38,508 --> 00:35:39,716
ANDI Peng: Ez egy kicsit trükkös.

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

726
00:35:43,110 --> 00:35:44,880
Ez valójában nem számít a végén.

727
00:35:44,880 --> 00:35:47,690
Nem számít, milyen
érdekében úgy dönt, hogy ráköltözni

728
00:35:47,690 --> 00:35:50,862
amíg még van róla Ön
nyomon követését, amit csere.

729
00:35:50,862 --> 00:35:52,250
>> Közönség: Ez lehet tömb-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI Peng: Igen, csináljuk tömb-i.

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

732
00:35:55,950 --> 00:35:59,305
És akkor mi a következő sort
A kód azt akarjuk, hogy itt?

733
00:35:59,305 --> 00:36:00,680
Közönség: tömb-i értéke tömb-j.

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

735
00:36:07,154 --> 00:36:08,070
ANDI Peng: És végül?

736
00:36:08,070 --> 00:36:12,070
Közönség: tömb-j egyenlő tömb-i.

737
00:36:12,070 --> 00:36:14,525
Közönség: Vagy tömb-j egyenlők
array-temp-- vagy, temp.

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
Úgyhogy futtatni ezt és látni
ha ez működni fog.

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

742
00:36:37,520 --> 00:36:39,335
Hol van ez a helyzet?

743
00:36:39,335 --> 00:36:40,210
Ó, ez a probléma.

744
00:36:40,210 --> 00:36:44,320
Lásd a 40. sor, mi vagyunk
akarják használni tömb-j?

745
00:36:44,320 --> 00:36:47,022
De hol j csak létezik?

746
00:36:47,022 --> 00:36:48,402
>> Közönség: A for ciklus.

747
00:36:48,402 --> 00:36:49,110
ANDI Peng: Jobb.

748
00:36:49,110 --> 00:36:51,730
Szóval mit fogunk kell csinálni?

749
00:36:51,730 --> 00:36:53,170
>> Közönség: Határozza meg ezen kívül the--

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

751
00:36:57,777 --> 00:37:00,610
Közönség: Igen, azt hiszem ezt
arra, hogy más, ha a nyilatkozatot, ugye?

752
00:37:00,610 --> 00:37:05,230
Szóval, mint, ha a minimum--
Rendben, hadd gondolkozzam.

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

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Srácok, próbálja
hogy vessen egy pillantást Nézzünk

755
00:37:09,990 --> 00:37:11,270
lásd, mi valami, amit tehetünk itt?

756
00:37:11,270 --> 00:37:11,811
>> Közönség: OK.

757
00:37:11,811 --> 00:37:15,900
Tehát, ha a minimális nem egyenlő
j-- így ha a minimum még én--

758
00:37:15,900 --> 00:37:17,570
akkor nem kell cserélni.

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

760
00:37:22,450 --> 00:37:24,712
>> ANDI Peng: Van, hogy az egyenlő i?

761
00:37:24,712 --> 00:37:25,920
Mit akarsz mondani itt?

762
00:37:25,920 --> 00:37:30,494
>> Közönség: Vagy igen, ha a
legalább nem egyenlő i, igen.

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
Nos, hogy megoldja, milyen, a problémáinkat.

766
00:37:42,040 --> 00:37:47,265
De ez még nem oldja meg a
probléma, hogy mi történik, ha j-- óta j

767
00:37:47,265 --> 00:37:49,890
nem létezik rajta kívül, mi
Mit akarunk csinálni vele?

768
00:37:49,890 --> 00:37:50,698
Kijelentem, hogy ezen kívül?

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

770
00:37:59,410 --> 00:38:02,730
Próbáljuk futtatása.

771
00:38:02,730 --> 00:38:04,435
UH Oh.

772
00:38:04,435 --> 00:38:06,200
A sorrend nem működik.

773
00:38:06,200 --> 00:38:10,060
>> Mint látható, a kezdeti
tömb volt ezeket az értékeket.

774
00:38:10,060 --> 00:38:14,800
És utána kellett volna
volt 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Nem működik.

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

777
00:38:16,030 --> 00:38:17,184
Mit csináljunk?

778
00:38:17,184 --> 00:38:17,850
Közönség: Debug.

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

780
00:38:21,787 --> 00:38:23,370
ANDI Peng: Rendben, próbáljuk ezt.

781
00:38:23,370 --> 00:38:25,030
Mi lehet a hibakeresés.

782
00:38:25,030 --> 00:38:26,042
Zoom out egy kicsit.

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

784
00:38:31,177 --> 00:38:33,656
Állítsunk a töréspontot.

785
00:38:33,656 --> 00:38:37,280
Menjünk az általam elvártnál OK.

786
00:38:37,280 --> 00:38:40,444
>> Szóval, mert mi már tudjuk, hogy
E sorok, 15 és 22.,

787
00:38:40,444 --> 00:38:43,610
vannak working-- mert minden, amit csinálok, az
Csak iterációjával keresztül, és printing--

788
00:38:43,610 --> 00:38:45,406
Én is megy előre, és hagyja, hogy.

789
00:38:45,406 --> 00:38:47,280
Kezdjük a 25. sortól.

790
00:38:47,280 --> 00:38:48,712
OOP, hadd megszabadulni, hogy.

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

792
00:38:51,598 --> 00:38:54,057
>> Közönség: Tehát a töréspont a
ahol a hibakeresés indul?

793
00:38:54,057 --> 00:38:54,890
ANDI Peng: Vagy megáll.

794
00:38:54,890 --> 00:38:55,670
Közönség: Vagy megáll.

795
00:38:55,670 --> 00:38:55,930
ANDI Peng: Igen.

796
00:38:55,930 --> 00:38:58,640
Beállíthatjuk, több töréspont és
ez is csak ugrani az egyik a másik.

797
00:38:58,640 --> 00:39:01,590
De ebben az esetben nem tudjuk
ahol a hiba történik.

798
00:39:01,590 --> 00:39:03,780
Szóval mi csak szeretnénk
indul fentről lefelé.

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

800
00:39:05,020 --> 00:39:05,550
OKÉ.

801
00:39:05,550 --> 00:39:08,460
>> Tehát ez a sor itt, lépnénk.

802
00:39:08,460 --> 00:39:11,499
Láthatjuk itt lent,
megvan egy tömbben.

803
00:39:11,499 --> 00:39:13,290
Azok az értékek
amelyek a tömbben.

804
00:39:13,290 --> 00:39:16,360
Látod, hogy milyen index 0, akkor
megfelel a value-- ó,

805
00:39:16,360 --> 00:39:17,526
Én fogom próbálni a nagyításhoz.

806
00:39:17,526 --> 00:39:20,650
Sajnálom, de ez nagyon nehéz
hogy see-- a tömb indexe 0,

807
00:39:20,650 --> 00:39:24,090
van egy értéke 4 és
majd így tovább, és így tovább.

808
00:39:24,090 --> 00:39:25,670
Megvan a lokális változók.

809
00:39:25,670 --> 00:39:28,570
Most éppen egyenlő
0, ami azt akarjuk, hogy legyen.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> És így maradjunk átlépett.

812
00:39:33,690 --> 00:39:36,850
A minimális egyenlő 0,
ami azt is szeretnénk, hogy legyen.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
És akkor mi meg a másodikat
hurok, ha tömb-j jelentése kevesebb, mint tömb-I,

815
00:39:45,560 --> 00:39:46,380
amelyeknek nem volt.

816
00:39:46,380 --> 00:39:48,130
Szóval láttad, hogyan
hogy átugorja az?

817
00:39:48,130 --> 00:39:52,430
>> Közönség: Tehát ha a ha
minimum, minden hogy-- ne, hogy

818
00:39:52,430 --> 00:39:55,424
belsejében az első for ciklust?

819
00:39:55,424 --> 00:39:57,340
ANDI Peng: Nem, mert
továbbra is szeretné kipróbálni.

820
00:39:57,340 --> 00:40:00,329
Azt akarod, hogy csinál egy összehasonlítást minden
idő után is fut rajta.

821
00:40:00,329 --> 00:40:02,620
Nem csak azt, hogy csináld
Az első pass-through.

822
00:40:02,620 --> 00:40:05,240
Meg akarom csinálni a
minden további át újra.

823
00:40:05,240 --> 00:40:07,198
Tehát azt szeretnénk, hogy ellenőrizze a
Ön állapota belül.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Úgyhogy most megyek
folyamatosan fut át ​​itt.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Adok nektek egy tippet.

828
00:40:18,420 --> 00:40:23,910
Ez arról szól, hogy az a tény, hogy amikor
te ellenőrzi a feltételes,

829
00:40:23,910 --> 00:40:26,600
te nem ellenőrzi
A helyes index.

830
00:40:26,600 --> 00:40:32,510
Akkor most te ellenőrzése
mezőindexe j kevesebb, mint tömb

831
00:40:32,510 --> 00:40:33,970
indexe i.

832
00:40:33,970 --> 00:40:36,580
De mit csinálsz fel
az elején a for ciklus?

833
00:40:36,580 --> 00:40:38,260
Nem vagy beállítás j egyenlő i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Igen, mi is valójában
kilép a debugger itt.

836
00:40:45,415 --> 00:40:47,040
Szóval vessünk egy pillantást a pszeudokódja.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- megyünk
kezdődik az i értéke 0.

839
00:40:52,580 --> 00:40:54,760
Fogunk felmenni n mínusz 1.

840
00:40:54,760 --> 00:40:58,040
Nézzük, megvoltak, igaz ez?

841
00:40:58,040 --> 00:40:59,580
Ja, hogy igaza volt.

842
00:40:59,580 --> 00:41:02,080
>> Így aztán idebent vagyunk
létre fog hozni egy minimális értéket

843
00:41:02,080 --> 00:41:03,630
és beállíthatja az egyenlő i.

844
00:41:03,630 --> 00:41:04,950
Vajon mi az?

845
00:41:04,950 --> 00:41:06,270
Ja, csináltam.

846
00:41:06,270 --> 00:41:10,430
Most a mi belső hurok vagyunk
fog tenni j egyenlő I. n mínusz 1.

847
00:41:10,430 --> 00:41:11,950
Vajon mi az?

848
00:41:11,950 --> 00:41:15,540
Sőt, ezt tettük.

849
00:41:15,540 --> 00:41:19,922
>> Így azonban mit keresünk összehasonlítva itt?

850
00:41:19,922 --> 00:41:20,925
>> Közönség: j + 1.

851
00:41:20,925 --> 00:41:21,716
ANDI Peng: Pontosan.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
És akkor fogsz szeretné állítani
A minimális egyenlő j plusz 1 is.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Így mentem keresztül, hogy nagyon gyorsan.

856
00:41:32,640 --> 00:41:36,190
Srácok, értem
Ezért ez j + 1?

857
00:41:36,190 --> 00:41:36,890
OKÉ.

858
00:41:36,890 --> 00:41:40,700
>> Így a tömb, a
az első áthaladnak,

859
00:41:40,700 --> 00:41:44,850
a for ciklus, az int
i értéke 0, nézzük csak

860
00:41:44,850 --> 00:41:46,740
Feltételezem, hogy ez nem változott még.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Van egy sor, teljesen,
Mindössze négy szétválogatás nélküli elemek, ugye?

863
00:41:56,760 --> 00:42:00,760
Ezért szeretnénk inicializálni i értéke 0.

864
00:42:00,760 --> 00:42:03,650
És én fog csak
végigmenni ezen a hurok.

865
00:42:03,650 --> 00:42:08,560
És így az első lépés, megyünk
inicializálni egy változót a "min"

866
00:42:08,560 --> 00:42:11,245
hogy szintén egyenlő I, mert
nincs egy minimális értéket.

867
00:42:11,245 --> 00:42:12,870
Szóval ez jelenleg 0-val egyenlő is.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
És akkor mi lesz, hogy menjen át.

870
00:42:17,640 --> 00:42:19,270
És szeretnénk iterációkhoz újra.

871
00:42:19,270 --> 00:42:22,900
Most, hogy megtaláltam, amit a minimális
van, azt akarjuk, hogy halad végig

872
00:42:22,900 --> 00:42:25,190
újra látni, ha ez az összehasonlítás, az igaz?

873
00:42:25,190 --> 00:42:40,440
Tehát j, itt, folyik
egyenlő i, ami 0.

874
00:42:40,440 --> 00:42:46,320
És akkor, ha tömb j plusz, ami
az egyik, hogy a következő vége, mivel kevesebb

875
00:42:46,320 --> 00:42:49,270
mint amit a jelenlegi minimális
érték, szeretné cserélni.

876
00:42:49,270 --> 00:42:56,850
>> Tehát mondjuk, mi már
kapott, mint a, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Most éppen egyenlő
0 és j értéke 0.

878
00:43:01,610 --> 00:43:05,210
És ez a minimum érték.

879
00:43:05,210 --> 00:43:09,950
Ha tömb-j plusz én-- így ha az egyik
ez után egy keresünk

880
00:43:09,950 --> 00:43:13,450
nagyobb, mint az előtte,
ez meg fog válni a minimum.

881
00:43:13,450 --> 00:43:18,120
>> Tehát itt azt látjuk, hogy az 5.
nem kevesebb, mint hogy.

882
00:43:18,120 --> 00:43:19,730
Szóval ez lesz nem lesz 5.

883
00:43:19,730 --> 00:43:23,580
Látjuk, hogy az 1. kevesebb, mint 2, ugye?

884
00:43:23,580 --> 00:43:32,970
Tehát most már tudjuk, hogy a mi minimum
lesz az index értéke a 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Igen?

886
00:43:34,030 --> 00:43:39,170
Aztán, amikor már itt lent,
akkor csere a helyes értékeket.

887
00:43:39,170 --> 00:43:42,610
>> Tehát, ha a srácok csak úgy, a j
előtt, akkor nem nézi az egy

888
00:43:42,610 --> 00:43:43,260
utána.

889
00:43:43,260 --> 00:43:44,520
Néztek
ugyanazt az értéket, amely

890
00:43:44,520 --> 00:43:46,290
Ezért ez csak nem csinál semmit.

891
00:43:46,290 --> 00:43:49,721
Van ennek értelme mindenkinek,
Ezért szükséges, hogy plusz 1 ott?

892
00:43:49,721 --> 00:43:50,220
OKÉ.

893
00:43:50,220 --> 00:43:53,345
Most nézzük csak végigmenni úgy, hogy
arról, hogy a többi kód helyes.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Miért van ez történik?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, ez a perc itt.

898
00:44:16,364 --> 00:44:17,780
Voltunk összehasonlítjuk a rossz értéket.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Oh ne.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Ó, igen, itt lent voltunk
csere a rossz értékeket is.

903
00:44:33,482 --> 00:44:34,940
Mert kerestünk i és j.

904
00:44:34,940 --> 00:44:36,440
Ezek azok voltunk megnézni.

905
00:44:36,440 --> 00:44:39,160
Igazából akarjuk cserélni
legalább a jelenlegi minimális,

906
00:44:39,160 --> 00:44:40,550
A bármilyen kívül senki nem.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
És ahogy ti is lent
Itt van egy rendezett tömbben.

909
00:45:05,402 --> 00:45:07,110
Csak volt köze
az a tény, hogy amikor a

910
00:45:07,110 --> 00:45:09,350
voltunk ellenőrzése
értékeket kaptunk összehasonlításával,

911
00:45:09,350 --> 00:45:11,226
mi nem keresi a megfelelő értékeket.

912
00:45:11,226 --> 00:45:13,850
Néztük ugyanaz
Itt valójában nem csere is.

913
00:45:13,850 --> 00:45:17,135
Meg kell nézni az egyik mellett
hozzá, és akkor lehet cserélni.

914
00:45:17,135 --> 00:45:19,260
Szóval ez a fajta
lehallgatás kódunkat előtt.

915
00:45:19,260 --> 00:45:22,460
És mit csináltam itt mindent
A debugger volna tenni az Ön számára

916
00:45:22,460 --> 00:45:23,810
Én csak tettem a
fórumon, mert könnyebb

917
00:45:23,810 --> 00:45:26,320
hogy ahelyett,
Nagyításhoz a debugger.

918
00:45:26,320 --> 00:45:29,391
Van ennek értelme mindenki?

919
00:45:29,391 --> 00:45:29,890
Hűvös.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Minden rendben.

922
00:45:35,410 --> 00:45:41,070
Mi lehet lépni beszél
aszimptotikus jelölés, amely

923
00:45:41,070 --> 00:45:44,580
csak egy divatos szóval a
runtimes az összes ilyen fajta.

924
00:45:44,580 --> 00:45:47,650
Szóval tudom, hogy Dávid, az előadás,
érintette runtimes.

925
00:45:47,650 --> 00:45:52,124
És ment keresztül az egész vegyület
hogyan kell kiszámítani a runtimes.

926
00:45:52,124 --> 00:45:53,040
Nem kell aggódni miatta.

927
00:45:53,040 --> 00:45:54,660
Ha igazán kíváncsi
A hogyan működik,

928
00:45:54,660 --> 00:45:55,810
nyugodtan beszélni velem szakasz után.

929
00:45:55,810 --> 00:45:57,560
Mi lehet a séta
képletekkel együtt.

930
00:45:57,560 --> 00:46:00,689
De minden a srácok, hogy valóban
tudom, hogy n faragva több mint 2

931
00:46:00,689 --> 00:46:01,980
ugyanaz a dolog, mint n négyzeten.

932
00:46:01,980 --> 00:46:04,710
Mivel a legnagyobb számban,
a kitevő, nő a legjobban.

933
00:46:04,710 --> 00:46:06,590
És így a mi szempontunkból,
Minden törődünk

934
00:46:06,590 --> 00:46:09,470
az, hogy a hatalmas szám, amely egyre fejlődik.

935
00:46:09,470 --> 00:46:13,340
>> Tehát mi a legjobb esetben
futásidejű kiválasztási sorrend?

936
00:46:13,340 --> 00:46:15,830
Ha megy, hogy
végiglépkedhetünk listát

937
00:46:15,830 --> 00:46:18,712
majd halad végig
A többi, hogy a listát,

938
00:46:18,712 --> 00:46:20,420
hányszor
Fogsz valószínűleg,

939
00:46:20,420 --> 00:46:24,612
a legrosszabb case-- a
legjobb esetben sorry-- végigmenni?

940
00:46:24,612 --> 00:46:27,070
Lehet, hogy a jobb kérdés
megkérdezni, mi a legrosszabb esetben

941
00:46:27,070 --> 00:46:28,153
futásidejű kiválasztás sort.

942
00:46:28,153 --> 00:46:29,366
Közönség: n négyzeten.

943
00:46:29,366 --> 00:46:30,740
ANDI Peng: Ez n faragva, ugye.

944
00:46:30,740 --> 00:46:36,986
Tehát egy egyszerű módja annak gondol ez olyan, mint,
Önnek bármikor két egymásba ágyazott ciklusok esetében,

945
00:46:36,986 --> 00:46:38,110
ez lesz n faragva.

946
00:46:38,110 --> 00:46:40,386
Mert nem csak te
fut át ​​ismét,

947
00:46:40,386 --> 00:46:42,260
akkor vissza kell mennie
körül, és futni rajta

948
00:46:42,260 --> 00:46:44,980
ismét benne minden értéket.

949
00:46:44,980 --> 00:46:48,640
Tehát ebben az esetben, futsz n
szer n faragva, amely is-- sajnálom,

950
00:46:48,640 --> 00:46:50,505
n-szer n, ami megegyezik n faragva.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> És sort is egy kicsit
egyedülálló abban az értelemben,

953
00:46:56,360 --> 00:46:59,774
hogy nem számít, ha ezeket
értékek már sorrendben.

954
00:46:59,774 --> 00:47:01,440
Ez még mindig tart végigmenni egyébként.

955
00:47:01,440 --> 00:47:03,872
Mondjuk úgy, hogy ez a mennyiség 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Függetlenül attól, hogy ez volt a
érdekében, hogy el tudta volna fogadni végigfutott

957
00:47:07,080 --> 00:47:08,620
és még mindig ellenőrizni a minimális értéket.

958
00:47:08,620 --> 00:47:10,100
Ez lett volna a
ugyanazt az ellenőrzések számát

959
00:47:10,100 --> 00:47:12,780
minden egyes alkalommal, akkor is, ha
valójában nem nyúlj semmihez.

960
00:47:12,780 --> 00:47:16,940
>> Tehát egy ilyen esetben, a legjobb és legrosszabb
runtimes valójában egyenértékű.

961
00:47:16,940 --> 00:47:19,160
Tehát a várható futási
A kiválasztási sorrend,

962
00:47:19,160 --> 00:47:23,790
amely megnevezzük a szimbólum
théta, théta, ebben az esetben,

963
00:47:23,790 --> 00:47:24,790
lenne továbbá n négyzeten.

964
00:47:24,790 --> 00:47:26,480
Mindhárom lenne N négyzeten.

965
00:47:26,480 --> 00:47:29,653
Mindenki tisztában, hogy miért
A runtime n faragva?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Minden rendben.

968
00:47:33,980 --> 00:47:39,120
Szóval én csak fog, hogy gyorsan fut
keresztül a többi fajta.

969
00:47:39,120 --> 00:47:41,137
Az algoritmus
buborék sort-- emlékszem,

970
00:47:41,137 --> 00:47:43,220
ez volt az első,
David odament előadás.

971
00:47:43,220 --> 00:47:46,000
Lényegében lépsz
keresztül a teljes listát

972
00:47:46,000 --> 00:47:48,950
és akkor swap-- csak
hasonlítsa össze a két egy időben.

973
00:47:48,950 --> 00:47:51,350
És ha az egyik nagyobb,
mint ha csak cserélni őket.

974
00:47:51,350 --> 00:47:53,590
Tehát, ha ezek nagyobb, akkor cserélni.

975
00:47:53,590 --> 00:47:56,180
Van hivatalos itt.

976
00:47:56,180 --> 00:47:59,100
>> Szóval maradjunk annyiban, hogy volt 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Az ember azt összehasonlítani a 8 és 6.

978
00:48:00,571 --> 00:48:01,570
Meg kéne cserélni őket.

979
00:48:01,570 --> 00:48:02,610
Akkor lenne összehasonlítani a 8 és 4.

980
00:48:02,610 --> 00:48:03,609
Meg kéne cserélni őket.

981
00:48:03,609 --> 00:48:07,000
Ha cserélni a 8. és
A 2, megváltoztatni őket is.

982
00:48:07,000 --> 00:48:10,760
Tehát ilyen értelemben, láthatjuk,
játszott ki, mint egy hosszú ideig,

983
00:48:10,760 --> 00:48:13,730
milyen értékeket fajta buborék
A végén, ezért is hívják

984
00:48:13,730 --> 00:48:15,320
buborékos rendezést.

985
00:48:15,320 --> 00:48:19,950
>> Mi lenne, csak végigmenni újra
a második menetben, és a mi harmadik menetben,

986
00:48:19,950 --> 00:48:21,150
és a negyedik menetben.

987
00:48:21,150 --> 00:48:25,820
Lényegében buborékos rendezést csak fut
amíg meg nem teszik többé swap.

988
00:48:25,820 --> 00:48:31,109
Tehát ebben az értelemben, ez csak
általános pszeudokód érte.

989
00:48:31,109 --> 00:48:32,650
Semmi gond, ezek mind online.

990
00:48:32,650 --> 00:48:34,990
Nem kell, hogy ténylegesen megy át ezt.

991
00:48:34,990 --> 00:48:38,134
>> Mi csak inicializálni egy számláló
változó, amely 0-nál kezdődik.

992
00:48:38,134 --> 00:48:39,800
És halad végig az egész tömböt.

993
00:48:39,800 --> 00:48:43,420
És ha egyik érték is-- ha ez
érték nagyobb, mint ez az érték,

994
00:48:43,420 --> 00:48:44,610
fogsz cserélni őket.

995
00:48:44,610 --> 00:48:46,860
És akkor te csak
fog tartani fog.

996
00:48:46,860 --> 00:48:47,970
És te fogsz számolni.

997
00:48:47,970 --> 00:48:50,845
És csak most fog tartani ezzel
Ezalatt a számláló nagyobb

998
00:48:50,845 --> 00:48:53,345
mint 0, ami azt jelenti, hogy a
minden alkalommal meg kell cserélni,

999
00:48:53,345 --> 00:48:55,220
tudja, hogy szeretne menni
vissza, és ellenőrizze újra.

1000
00:48:55,220 --> 00:48:59,510
Azt akarod, hogy nézz, amíg nem tudja
hogy nem kell cserélni többé.

1001
00:48:59,510 --> 00:49:05,570
>> Tehát mi a legjobb és a legrosszabb
esetében runtimes a buborékos rendezést?

1002
00:49:05,570 --> 00:49:09,300
És hint-- ez valójában más
a kijelölés sort abban az értelemben,

1003
00:49:09,300 --> 00:49:11,810
hogy ezek a két válasz nem ugyanaz.

1004
00:49:11,810 --> 00:49:14,709
Gondoljon bele, mi történne
ügyben akkor, ha már válogatni.

1005
00:49:14,709 --> 00:49:16,500
És hiszem, hogy mi
történne, ha ez volt

1006
00:49:16,500 --> 00:49:18,372
abban az esetben, amelyben nem volt rendezve.

1007
00:49:18,372 --> 00:49:20,580
És akkor milyen futtatni
keresztül, hogy miért történik.

1008
00:49:20,580 --> 00:49:22,954
Adok nektek, mint, 30
másodpercig gondolni.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> OKÉ.

1011
00:49:53,540 --> 00:49:57,462
Van valakinek egy kitalálni, mi a
legrosszabb esetben futásidejű buborék rendezés?

1012
00:49:57,462 --> 00:49:57,962
Igen.

1013
00:49:57,962 --> 00:50:07,810
>> Közönség: lenne, mint n-szer
n mínusz 1, vagy valami ilyesmi?

1014
00:50:07,810 --> 00:50:10,650
Mint minden alkalommal fut,
ez csak, mint, egy csere kevesebb

1015
00:50:10,650 --> 00:50:10,960
hogy bármi is volt.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI Peng: Igen,
te teljesen igaza van.

1017
00:50:12,668 --> 00:50:15,940
És ez az az eset, amelyben a
válasz valójában sokkal összetettebb,

1018
00:50:15,940 --> 00:50:17,240
mint az, meg kell adni.

1019
00:50:17,240 --> 00:50:19,772
Szóval ez lesz run-- vagyok
fog törölni mindezt itt.

1020
00:50:19,772 --> 00:50:20,480
Mindenki jó?

1021
00:50:20,480 --> 00:50:21,869
Lehet törölni ezt?

1022
00:50:21,869 --> 00:50:22,368
OKÉ.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Fogsz végigmenni n
alkalommal először, ugye?

1025
00:50:30,320 --> 00:50:33,200
És ők fognak végigmenni
n mínusz 1 másodszor, igaz?

1026
00:50:33,200 --> 00:50:37,130
És akkor fogsz tartani
megy, n az enyém 2, satöbbi.

1027
00:50:37,130 --> 00:50:40,210
Dávid tette ezt egy előadás, ahol,
ha összeadjuk mindazokat az értékeket,

1028
00:50:40,210 --> 00:50:48,080
kapsz valamit, ami az általam elvártnál yeah--
több, mint 2, amely lényegében csak csökkenti

1029
00:50:48,080 --> 00:50:49,784
le n faragva.

1030
00:50:49,784 --> 00:50:51,700
Fogsz, hogy egy
fura frakció ott.

1031
00:50:51,700 --> 00:50:53,892
És így csak tudom, hogy
Az n-négyzet mindig

1032
00:50:53,892 --> 00:50:55,350
elsőbbséget élvez a frakció.

1033
00:50:55,350 --> 00:50:58,450
És így ebben az esetben, a legrosszabb
futásidejű lenne n faragva.

1034
00:50:58,450 --> 00:51:00,210
Ha ez csökkenő
érdekében, gondolom, akkor

1035
00:51:00,210 --> 00:51:02,530
Van, hogy egy-swap minden egyes alkalommal.

1036
00:51:02,530 --> 00:51:05,170
>> Mi lenne, potenciálisan,
A legjobb esetben futásidejű?

1037
00:51:05,170 --> 00:51:08,580
Mondjuk úgy, ha a lista már
annak érdekében, hogy mi lenne a futtató legyen?

1038
00:51:08,580 --> 00:51:09,565
>> Közönség: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI Peng: Ez n, pontosan.

1040
00:51:10,690 --> 00:51:11,600
És miért van az, n?

1041
00:51:11,600 --> 00:51:13,850
Közönség: Mert csak
van, hogy ellenőrizze az egyes egyszer.

1042
00:51:13,850 --> 00:51:14,770
ANDI Peng: Pontosan.

1043
00:51:14,770 --> 00:51:17,150
Így a lehető legjobb runtime,
Ha ez a lista már

1044
00:51:17,150 --> 00:51:20,270
sorted-- mondjuk 1, 2, 3, 4-- akkor
csak megy keresztül, akkor kérjük,

1045
00:51:20,270 --> 00:51:21,720
Ön is látni, ó, azok mind sikerülni.

1046
00:51:21,720 --> 00:51:22,636
Nem kellett cserélni.

1047
00:51:22,636 --> 00:51:23,370
Végeztem.

1048
00:51:23,370 --> 00:51:26,500
Tehát ebben az esetben, ez csak n
vagy a lépések számát csak

1049
00:51:26,500 --> 00:51:29,870
Volt, hogy ellenőrizze az első listáján.

1050
00:51:29,870 --> 00:51:33,990
>> És miután, most hit
beillesztés sort, ahol

1051
00:51:33,990 --> 00:51:39,260
Az algoritmus lényegében a szakadék
ez egy rendezett és rendezetlen része.

1052
00:51:39,260 --> 00:51:42,810
És akkor egy-egy,
A szétválogatás nélkül értékek

1053
00:51:42,810 --> 00:51:46,880
beilleszteni a megfelelő
pozíciókat a lista elején.

1054
00:51:46,880 --> 00:51:52,120
>> Így például, hogy van egy
listája 3, 5, 2, 6, 4 újra.

1055
00:51:52,120 --> 00:51:54,750
Tudjuk, hogy ez jelenleg
szétválogatás nélkül, mert most már csak

1056
00:51:54,750 --> 00:51:57,030
kezdte néztem.

1057
00:51:57,030 --> 00:52:00,610
Veszünk egy pillantást, és tudjuk, hogy
Az első érték válogatni, ugye?

1058
00:52:00,610 --> 00:52:04,190
Ha csak nézi egy sor
méretű, tudod, hogy ez válogatni.

1059
00:52:04,190 --> 00:52:08,230
>> Tehát tudjuk, hogy a
másik négy szétválogatás nélkül.

1060
00:52:08,230 --> 00:52:10,980
Mi megy keresztül, és azt látjuk, hogy értéket.

1061
00:52:10,980 --> 00:52:11,730
Menjünk vissza.

1062
00:52:11,730 --> 00:52:13,130
Lásd, hogy értéke 5?

1063
00:52:13,130 --> 00:52:14,110
Veszünk egy pillantást rá.

1064
00:52:14,110 --> 00:52:15,204
Összehasonlítjuk azzal 3.

1065
00:52:15,204 --> 00:52:17,870
Tudjuk, hogy ez nagyobb, mint
3, így tudjuk, hogy ami válogatni.

1066
00:52:17,870 --> 00:52:22,940
Tehát most már tudjuk, hogy az első két
vannak sorolva, és az utolsó három nem.

1067
00:52:22,940 --> 00:52:24,270
>> Veszünk egy pillantást 2.

1068
00:52:24,270 --> 00:52:25,720
Először ellenőrizze, hogy 5.

1069
00:52:25,720 --> 00:52:26,700
Vajon kevesebb, mint 5?

1070
00:52:26,700 --> 00:52:27,240
Ez nem.

1071
00:52:27,240 --> 00:52:29,510
Tehát meg kell tartani lenézett.

1072
00:52:29,510 --> 00:52:30,940
Akkor ellenőrizze 2 db 3.

1073
00:52:30,940 --> 00:52:31,850
Vajon kevesebb?

1074
00:52:31,850 --> 00:52:32,350
Nem.

1075
00:52:32,350 --> 00:52:35,430
Szóval tudja a 2 kell beilleszteni
az elülső és a 3. és 5.

1076
00:52:35,430 --> 00:52:38,200
mindkettőt fel kell tolta ki.

1077
00:52:38,200 --> 00:52:42,190
Ehhez ismét 6 és 4.

1078
00:52:42,190 --> 00:52:48,962
És mi csak nézz lényegében
ahol csak nézd, nézd, nézd.

1079
00:52:48,962 --> 00:52:51,170
És amíg ez a helyes
helyzetben vagyunk fajta csak

1080
00:52:51,170 --> 00:52:54,890
helyezze be a megfelelő pozícióba,
ott, ahol a nevét, ahonnan származik.

1081
00:52:54,890 --> 00:52:59,830
>> Szóval ez csak az algoritmus,
pszeudokódja önmagában egyfajta,

1082
00:52:59,830 --> 00:53:04,990
arról, hogy hogyan fogja valósítani
beiktatási sort.

1083
00:53:04,990 --> 00:53:05,954
Pszeudókód itt van.

1084
00:53:05,954 --> 00:53:06,620
Ez mind az interneten.

1085
00:53:06,620 --> 00:53:10,720
Nem gond, ha a srácok
próbálja másolni ezt le.

1086
00:53:10,720 --> 00:53:14,500
Tehát még egyszer, ugyanazt, amit question--
lenne a legjobb és a legrosszabb runtimes

1087
00:53:14,500 --> 00:53:16,120
behelyezhető sort?

1088
00:53:16,120 --> 00:53:17,750
Ez nagyon hasonlít az utolsó kérdésre.

1089
00:53:17,750 --> 00:53:20,479
Adok nektek, mint, 30
másodperc gondolni ezt is.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Akar valaki
add nekem a legrosszabb futási?

1092
00:53:50,071 --> 00:53:50,570
Igen.

1093
00:53:50,570 --> 00:53:51,490
>> Közönség: n négyzeten.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI Peng: Ez n faragva.

1095
00:53:52,573 --> 00:53:53,730
És miért van az, n faragva?

1096
00:53:53,730 --> 00:53:57,562
>> Közönség: Mert
fordított sorrendben, akkor

1097
00:53:57,562 --> 00:54:02,619
átmenni n-szer n, amely is--

1098
00:54:02,619 --> 00:54:03,660
ANDI Peng: Igen, pontosan.

1099
00:54:03,660 --> 00:54:06,610
Tehát ugyanaz, mint a buborékos rendezést.

1100
00:54:06,610 --> 00:54:08,720
Ha ez a lista a
csökkenő sorrendben, te

1101
00:54:08,720 --> 00:54:11,240
lesz, hogy ellenőrizze először egyszer.

1102
00:54:11,240 --> 00:54:13,470
És akkor minden
hozzáadott értéket, te

1103
00:54:13,470 --> 00:54:16,390
lesz, hogy ellenőrizze ellen
minden érték, ugye?

1104
00:54:16,390 --> 00:54:20,290
És így összesen, fogsz tenni
n időtöltésükkel másik n át, amely

1105
00:54:20,290 --> 00:54:21,750
N négyzeten.

1106
00:54:21,750 --> 00:54:22,860
Mi a helyzet a legjobb esetben?

1107
00:54:22,860 --> 00:54:24,360
Igen.

1108
00:54:24,360 --> 00:54:28,840
>> Közönség: n mínusz 1, mert a
elsőt már faragva.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI Peng: Szóval, közel.

1110
00:54:30,270 --> 00:54:31,850
A válasz tulajdonképpen n.

1111
00:54:31,850 --> 00:54:37,189
Mert míg az első egy
válogatni, akkor nem actually-- meg

1112
00:54:37,189 --> 00:54:38,980
mi csak lucked, a
hogy például, hogy a 2.

1113
00:54:38,980 --> 00:54:40,930
történt, hogy a legkisebb szám.

1114
00:54:40,930 --> 00:54:43,680
De ez nem lesz mindig így.

1115
00:54:43,680 --> 00:54:48,040
Ha 2 már válogatni az elején
de úgy nézel ki, és van egy 1 van,

1116
00:54:48,040 --> 00:54:49,144
Az 1 fog bump meg.

1117
00:54:49,144 --> 00:54:51,060
És ez lesz a vége
fel, hogy ütközött egyébként.

1118
00:54:51,060 --> 00:54:56,250
>> Szóval a legjobb forgatókönyv esetén,
ez valójában csak lesz n.

1119
00:54:56,250 --> 00:54:59,090
Ha 1, 2, 3,
4, 5, 6, 7, 8, te

1120
00:54:59,090 --> 00:55:00,940
fog végigmenni
hogy teljes listát egyszer

1121
00:55:00,940 --> 00:55:03,430
hogy ellenőrizze, hogy ha minden rendben.

1122
00:55:03,430 --> 00:55:07,390
Mindenki tisztában futás
szer kiválasztását is?

1123
00:55:07,390 --> 00:55:09,960
Tudom, min megyek keresztül
Ezek nagyon gyors.

1124
00:55:09,960 --> 00:55:13,330
De csak tudom, hogy ha tudod, hogy a
általános fogalmakat, akkor legyen jó.

1125
00:55:13,330 --> 00:55:16,070
OKÉ.

1126
00:55:16,070 --> 00:55:19,790
Szóval én csak adni nektek talán, mint,
Egy perc beszélni a szomszédok

1127
00:55:19,790 --> 00:55:21,890
milyen Íme, néhány
A főbb különbségek

1128
00:55:21,890 --> 00:55:23,540
E típusok között a fajta.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Átnézzük, hogy hamarosan.

1131
00:56:25,570 --> 00:56:26,444
Közönség: Ó, oké.

1132
00:56:26,444 --> 00:56:27,320
ANDI Peng: Igen.

1133
00:56:27,320 --> 00:56:28,380
OKÉ.

1134
00:56:28,380 --> 00:56:33,420
Cool, hadd hívja össze újra, mint egy osztály.

1135
00:56:33,420 --> 00:56:34,330
OKÉ.

1136
00:56:34,330 --> 00:56:37,579
Tehát ez a fajta egy
nyitott kérdések abban az értelemben,

1137
00:56:37,579 --> 00:56:39,120
hogy van sok választ rájuk.

1138
00:56:39,120 --> 00:56:40,746
És megyünk át néhány közülük röviden.

1139
00:56:40,746 --> 00:56:43,411
Csak azt akartam, hogy a srácok
gondolkodni, hogy milyen differenciált

1140
00:56:43,411 --> 00:56:44,530
mindhárom fajta.

1141
00:56:44,530 --> 00:56:47,440
És hallottam, azt is, nagy
question-- mit egyesülésről sort csinálni?

1142
00:56:47,440 --> 00:56:50,110
Nagy kérdés, mert ez az,
amit mi lefedő következő.

1143
00:56:50,110 --> 00:56:52,850
>> Így egyesül sort a
egyféle, hogy a funkciók

1144
00:56:52,850 --> 00:56:56,100
nagyon eltérően a többi fajta.

1145
00:56:56,100 --> 00:56:58,180
Ahogy ti is see--
tett Dávid csinálni demo

1146
00:56:58,180 --> 00:57:01,130
ahol már a hűvös
zajai látta, hogy merge

1147
00:57:01,130 --> 00:57:04,010
Rendezés futott, mint a végtelenül
gyorsabb, mint a másik két típusú?

1148
00:57:04,010 --> 00:57:04,510
OKÉ.

1149
00:57:04,510 --> 00:57:07,580
Szóval ez azért van, mert merge
Rendezés végrehajtja ezt a szakadék

1150
00:57:07,580 --> 00:57:11,020
és uralkodj koncepció, hogy mi már
Beszéltünk sok előadás.

1151
00:57:11,020 --> 00:57:14,550
Ebben az értelemben, hogy szeretnék dolgozni
okosabb, sem nehezebb, ha elosztjuk

1152
00:57:14,550 --> 00:57:18,120
és uralkodj problémákat, és megtörni őket
le, majd rakjuk őket,

1153
00:57:18,120 --> 00:57:19,930
jó dolgok mindig történnek.

1154
00:57:19,930 --> 00:57:21,960
>> Tehát az is, hogy egyesíteni
rendezés alapvetően működik

1155
00:57:21,960 --> 00:57:24,660
az, hogy felosztja egy
szétválogatás nélküli tömb felét.

1156
00:57:24,660 --> 00:57:26,500
És akkor ez van két fele tömbök.

1157
00:57:26,500 --> 00:57:28,220
És ez csak rendezi a két fél.

1158
00:57:28,220 --> 00:57:31,750
Ez csak folyamatosan osztjuk ketté, a
fele, a felére, amíg nincs minden rendezve

1159
00:57:31,750 --> 00:57:33,680
majd rekurzívan
olyan, hogy együtt.

1160
00:57:33,680 --> 00:57:36,550
>> Szóval ez tényleg elvont.

1161
00:57:36,550 --> 00:57:38,750
Tehát ez csak egy kis pszeudokódja.

1162
00:57:38,750 --> 00:57:41,040
Van ennek értelme
úgy, ahogy fut?

1163
00:57:41,040 --> 00:57:43,870
Szóval maradjunk annyiban, hogy van egy
tömb n elem, ugye?

1164
00:57:43,870 --> 00:57:45,450
Ha n kevesebb, mint 2, akkor vissza.

1165
00:57:45,450 --> 00:57:49,040
Mert tudod, hogy ha van
csak egy dolog, meg kell válogatni.

1166
00:57:49,040 --> 00:57:52,600
Mást, akkor rendezni a bal fele,
majd rendezni a jobb fele,

1167
00:57:52,600 --> 00:57:54,140
és akkor egyesíteni.

1168
00:57:54,140 --> 00:57:56,979
>> Tehát miközben úgy néz ki, nagyon egyszerű,
a valóságban, gondoltam, hogy ez

1169
00:57:56,979 --> 00:58:00,270
fajta nehéz. Mert te, mint
Nos, ez a fajta futó magát.

1170
00:58:00,270 --> 00:58:00,769
Jobb?

1171
00:58:00,769 --> 00:58:02,430
Ez fut magát.

1172
00:58:02,430 --> 00:58:05,479
Tehát ebben az értelemben, David megérintette
upon rekurzió osztályban.

1173
00:58:05,479 --> 00:58:07,270
És ez egy olyan fogalom,
fogunk beszélni többet.

1174
00:58:07,270 --> 00:58:11,430
Ez, hogy ez a két vonal
Itt valójában csak a program

1175
00:58:11,430 --> 00:58:13,860
mondja, hogy fut magát
A különböző bemeneti.

1176
00:58:13,860 --> 00:58:17,230
Tehát ahelyett, futni magát
A teljes egészében az n elem,

1177
00:58:17,230 --> 00:58:20,530
Ön tudja bontani a
bal fele és a jobb fele

1178
00:58:20,530 --> 00:58:22,680
majd indítsuk újra.

1179
00:58:22,680 --> 00:58:26,050
>> És akkor majd nézd meg vizuálisan,
mert én vagyok a vizuális tanuló.

1180
00:58:26,050 --> 00:58:27,270
Ez jobban működik nekem.

1181
00:58:27,270 --> 00:58:29,890
Szóval akkor nézd meg a vizuális példának.

1182
00:58:29,890 --> 00:58:36,237
>> Mondjuk van egy tömbben, hat
elemek, 3, 5, 2, 6, 4, 1, nem rendezve.

1183
00:58:36,237 --> 00:58:37,820
Rendben, van egy csomó ezen az oldalon.

1184
00:58:37,820 --> 00:58:43,179
Tehát, ha a srácok nézd meg a
első lépés itt, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
akkor hasít ketté.

1186
00:58:44,220 --> 00:58:45,976
Van 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Tudja, hogy ezek a aren't-- akkor
Nem tudom, ha ők válogatni, akár nem,

1188
00:58:48,850 --> 00:58:52,517
így folyamatosan feltörik őket, félbe,
fél, fél, míg végül,

1189
00:58:52,517 --> 00:58:53,600
Önnek csak az egyik eleme.

1190
00:58:53,600 --> 00:58:56,790
És egy elem mindig válogatni, ugye?

1191
00:58:56,790 --> 00:59:01,560
>> Tehát tudjuk, hogy a 3, 5, 2, 4, 6,
1, önmagukban vannak sorolva.

1192
00:59:01,560 --> 00:59:05,870
És most lehet őket újra együtt.

1193
00:59:05,870 --> 00:59:07,510
Tehát tudjuk, hogy a 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Azt hogy ezeket össze.

1195
00:59:08,510 --> 00:59:09,617
Tudjuk, hogy ez a rendezett.

1196
00:59:09,617 --> 00:59:10,450
A 2 még mindig ott van.

1197
00:59:10,450 --> 00:59:11,830
Mi is tesz a 4. és a 6. össze.

1198
00:59:11,830 --> 00:59:13,996
Tudjuk, hogy ami válogatni,
így teszünk, hogy össze.

1199
00:59:13,996 --> 00:59:14,940
És az 1 van.

1200
00:59:14,940 --> 00:59:18,720
>> És akkor csak nézd meg
E két félből itt.

1201
00:59:18,720 --> 00:59:21,300
Megvan a 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Akkor csak összehasonlítani a
elején mindent.

1203
00:59:23,465 --> 00:59:26,340
Mert tudod, hogy ez a rendezve
és tudod, hogy ami válogatni.

1204
00:59:26,340 --> 00:59:29,360
Szóval akkor nem is kell
összehasonlítani az 5, akkor csak összehasonlítani a 3.

1205
00:59:29,360 --> 00:59:32,070
És a 2 kisebb, mint 3, így
Tudja 2 kell menni a végén.

1206
00:59:32,070 --> 00:59:33,120
>> Ugyanaz a dolog ott.

1207
00:59:33,120 --> 00:59:34,740
Az 1 kell menni innen.

1208
00:59:34,740 --> 00:59:37,330
És akkor, amikor megy fel
E két érték együtt,

1209
00:59:37,330 --> 00:59:39,950
Tudja, hogy ez válogatni és
tudod, hogy van rendezve.

1210
00:59:39,950 --> 00:59:43,240
Így aztán az 1-es és a
2, a 1 kevesebb, mint 2.

1211
00:59:43,240 --> 00:59:45,570
Hogy megmondja, hogy az 1-
kell menni a végén ez a

1212
00:59:45,570 --> 00:59:47,480
anélkül, hogy ránézett 3 vagy 5.

1213
00:59:47,480 --> 00:59:50,100
És akkor a 4, akkor csak
ellenőrizze, hogy jól megy itt.

1214
00:59:50,100 --> 00:59:51,480
Nem kell, hogy nézd meg a 5.

1215
00:59:51,480 --> 00:59:52,570
Ugyanaz a 6.

1216
00:59:52,570 --> 00:59:55,860
Tudja, hogy a 6-- ez csak
nem kell vizsgálni.

1217
00:59:55,860 --> 00:59:57,870
>> És így ezen a módon, akkor
Csak megtakarítás magát

1218
00:59:57,870 --> 00:59:59,526
sok lépésből ha csak összehasonlítjuk.

1219
00:59:59,526 --> 01:00:02,150
Nem kell összehasonlítani minden
eleme ellen más elemeket.

1220
01:00:02,150 --> 01:00:05,230
Te csak összehasonlítani az is,
hogy meg kell összehasonlítani ellen.

1221
01:00:05,230 --> 01:00:06,870
Szóval ez a fajta elvont fogalom.

1222
01:00:06,870 --> 01:00:10,540
Nem gond, ha ez nem
nagyon üti meg a jobb még.

1223
01:00:10,540 --> 01:00:14,740
De általában, ez
hogyan merge sort működik.

1224
01:00:14,740 --> 01:00:17,750
Kérdések, gyors kérdés,
mielőtt lépni?

1225
01:00:17,750 --> 01:00:18,550
Igen.

1226
01:00:18,550 --> 01:00:22,230
>> Közönség: Szóval azt mondta, hogy vegye
a 1, majd a 4 és a 6

1227
01:00:22,230 --> 01:00:23,860
és tedd őket.

1228
01:00:23,860 --> 01:00:26,800
Tehát nem those-- nem
Ön nézi őket

1229
01:00:26,800 --> 01:00:28,544
különálló elemként, nem olyan az egész?

1230
01:00:28,544 --> 01:00:29,210
ANDI Peng: Igen.

1231
01:00:29,210 --> 01:00:32,020
Szóval, mi történik
az, hogy alapvetően

1232
01:00:32,020 --> 01:00:33,650
létrehoz egy új tömböt.

1233
01:00:33,650 --> 01:00:36,690
Szóval tudom, hogy itt, van
Két tömbök mérete 3, ugye?

1234
01:00:36,690 --> 01:00:39,600
Szóval tudom, hogy én rendezett tömbben
szüksége van hat elemet.

1235
01:00:39,600 --> 01:00:42,270
Szóval csak létre
Új memória mennyisége.

1236
01:00:42,270 --> 01:00:44,270
Szóval maga olyan, mint
hogy pazarló memória,

1237
01:00:44,270 --> 01:00:46,186
de ez nem számít
mert annyira kicsi.

1238
01:00:46,186 --> 01:00:48,590
Szóval nézd meg a 1
és akkor nézd meg a 2.

1239
01:00:48,590 --> 01:00:50,770
És tudod, hogy az 1 kevesebb, mint 2.

1240
01:00:50,770 --> 01:00:53,840
Szóval tudom, hogy 1 kell menni
az elején az összes ilyen.

1241
01:00:53,840 --> 01:00:55,850
>> Nem is kell, hogy
megnézi az a 3. és az 5.

1242
01:00:55,850 --> 01:00:57,400
Szóval tudod 1 odamegy.

1243
01:00:57,400 --> 01:00:59,300
Akkor alapvetően levágja az 1.

1244
01:00:59,300 --> 01:01:00,370
Ez, mint a halott nekünk.

1245
01:01:00,370 --> 01:01:03,690
Ezután már csak 2,
3, 5, majd a 4. és 6..

1246
01:01:03,690 --> 01:01:06,270
És akkor tudod, hogy te
hasonlítsa össze a 4, és a 2,

1247
01:01:06,270 --> 01:01:07,560
ó, a 2 kell menni oda.

1248
01:01:07,560 --> 01:01:09,685
Szóval puff a 2 le, akkor vágja le.

1249
01:01:09,685 --> 01:01:12,060
Szóval akkor csak azt a 3
és az 5, a 4 és a 6.

1250
01:01:12,060 --> 01:01:14,650
És csak folyamatosan darabolás le
amíg meg őket a tömbben.

1251
01:01:14,650 --> 01:01:17,110
>> Közönség: Szóval te csak mindig
összehasonlítjuk az [hallhatatlan]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI Peng: Pontosan.

1253
01:01:17,710 --> 01:01:19,590
Tehát ebben az értelemben, te
Csak összehasonlítva lényegében

1254
01:01:19,590 --> 01:01:21,240
Egy szám a másik ellen számát.

1255
01:01:21,240 --> 01:01:22,990
És mert tudja,
hogy ez válogatni, akkor

1256
01:01:22,990 --> 01:01:24,350
Nem kell, hogy nézze át
Az összes szám.

1257
01:01:24,350 --> 01:01:25,870
Csak meg kell nézni az elsőt.

1258
01:01:25,870 --> 01:01:27,582
És akkor csak puff
le őket, mert tudja,

1259
01:01:27,582 --> 01:01:29,640
tartoznak, ha kell tartozni.

1260
01:01:29,640 --> 01:01:31,030
Igen.

1261
01:01:31,030 --> 01:01:32,920
Jó kérdés.

1262
01:01:32,920 --> 01:01:35,290
>> És akkor, ha valakinek
egy kicsit ambiciózusabb,

1263
01:01:35,290 --> 01:01:38,660
nyugodtan nézd meg ezt a kódot.

1264
01:01:38,660 --> 01:01:40,680
Ez tulajdonképpen a
fizikai megvalósítása

1265
01:01:40,680 --> 01:01:42,150
Az, hogy hogyan fog írni merge sort.

1266
01:01:42,150 --> 01:01:44,070
És láthatjuk, hogy nagyon rövid.

1267
01:01:44,070 --> 01:01:46,310
De az ötletek mögött
ez elég bonyolult.

1268
01:01:46,310 --> 01:01:50,865
Tehát, ha úgy érzed, rajz ezt ki
a házi feladatot ma este, nyugodtan.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> OKÉ.

1271
01:01:54,740 --> 01:01:58,070
Így Dávid is ment át ezt az előadást.

1272
01:01:58,070 --> 01:02:00,660
Melyek a legjobb esetben
runtimes, legrosszabb esetben runtimes,

1273
01:02:00,660 --> 01:02:05,680
és a várható futási időt a merge sort?

1274
01:02:05,680 --> 01:02:07,260
Egy pár másodperc gondolni.

1275
01:02:07,260 --> 01:02:11,198
Ez elég nehéz, de ilyen
intuitív, ha belegondolsz.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Minden rendben.

1278
01:02:23,054 --> 01:02:25,269
>> Közönség: a legrosszabb esetben n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI Peng: Pontosan.

1280
01:02:26,060 --> 01:02:29,380
És miért van az, n log n.

1281
01:02:29,380 --> 01:02:32,230
>> Közönség: Hát nem azért, mert
válik exponenciálisan gyorsabb,

1282
01:02:32,230 --> 01:02:35,390
így, mint a függvénye, hogy
ahelyett, hogy csak egyszerűen csak n

1283
01:02:35,390 --> 01:02:37,529
faragva, vagy valami?

1284
01:02:37,529 --> 01:02:38,320
ANDI Peng: Pontosan.

1285
01:02:38,320 --> 01:02:40,750
Tehát az ok, amiért a
futásidejű ezen n log

1286
01:02:40,750 --> 01:02:44,310
n because-- mi vagy te
Ennek mindezen lépések?

1287
01:02:44,310 --> 01:02:46,190
Te csak aprítás félbe, ugye?

1288
01:02:46,190 --> 01:02:48,750
És így, amikor csináljuk a
jelentkezzen, mindent, amit csinál

1289
01:02:48,750 --> 01:02:53,150
elosztjuk a probléma a felére,
fél, fél, több részre.

1290
01:02:53,150 --> 01:02:56,430
És ebben az értelemben, akkor milyen
A megszünteti a lineáris modell

1291
01:02:56,430 --> 01:02:57,510
hogy a korábban használt.

1292
01:02:57,510 --> 01:03:00,254
Mert ha karaj
dolgokat fele, ez egy napló.

1293
01:03:00,254 --> 01:03:02,420
Ez csak a matematikai
módja képviselője.

1294
01:03:02,420 --> 01:03:06,310
>> És végül, a végén, akkor
csak hogy egy utolsó áthaladnak

1295
01:03:06,310 --> 01:03:07,930
hogy mindet annak érdekében, ugye?

1296
01:03:07,930 --> 01:03:10,330
És így ha csak meg kell
ellenőrizze egy dolog, ami n.

1297
01:03:10,330 --> 01:03:13,420
És így te ilyen
megszorozzuk a kettő együtt.

1298
01:03:13,420 --> 01:03:17,660
Tehát ez olyan, mint neked, hogy a végső
ellenőrizze az N idelent egy log n

1299
01:03:17,660 --> 01:03:18,390
itt, fent.

1300
01:03:18,390 --> 01:03:21,060
És ha megszorozzuk
őket, ami n log n.

1301
01:03:21,060 --> 01:03:26,100
>> És így a legjobb és legrosszabb
ügyben, és várhatóan mind n log n.

1302
01:03:26,100 --> 01:03:27,943
Ez is, mint egy másik fajta.

1303
01:03:27,943 --> 01:03:30,090
Ez olyan, mint kiválasztási sorrend
abban az értelemben, hogy

1304
01:03:30,090 --> 01:03:32,131
Nem számít, milyen a
lista, akkor csak megy

1305
01:03:32,131 --> 01:03:34,801
hogy nem ugyanaz a dolog minden egyes alkalommal.

1306
01:03:34,801 --> 01:03:35,300
OKÉ.

1307
01:03:35,300 --> 01:03:39,950
Tehát ahogy ti is látni, annak ellenére,
A fajta, hogy eljutottunk addig through-- n

1308
01:03:39,950 --> 01:03:41,660
faragva, ez nem túl hatékony.

1309
01:03:41,660 --> 01:03:47,060
És még ez n log n
nem a leghatékonyabb.

1310
01:03:47,060 --> 01:03:49,720
Ha a srácok kíváncsi,
van egyfajta mechanizmusok

1311
01:03:49,720 --> 01:03:54,310
hogy olyan hatékonyak, hogy ők
Szinte alapvetően sík futásidőben.

1312
01:03:54,310 --> 01:03:55,420
>> Van néhány log n években.

1313
01:03:55,420 --> 01:03:58,190
Van néhány log log n években.

1314
01:03:58,190 --> 01:04:00,330
Mi nem érintem őket
Ebben az osztályban most.

1315
01:04:00,330 --> 01:04:02,663
De ha a fiúk kíváncsi,
nyugodtan google, mi

1316
01:04:02,663 --> 01:04:04,392
a leghatékonyabb válogatás mechanizmusokat.

1317
01:04:04,392 --> 01:04:06,350
Nem tudom, vannak
néhány igazán vicces is,

1318
01:04:06,350 --> 01:04:09,860
általam elvártnál van néhány igazán
vicces is, hogy az emberek.

1319
01:04:09,860 --> 01:04:12,210
És vajon hogyan
valaha is gondoltam.

1320
01:04:12,210 --> 01:04:15,730
Tehát a Google, ha van egy kis tartalék
idő szerint, mik vicces módon

1321
01:04:15,730 --> 01:04:17,730
hogy people-- valamint
hatékony ways-- emberek

1322
01:04:17,730 --> 01:04:20,371
lett volna képes végrehajtani fajta.

1323
01:04:20,371 --> 01:04:20,870
OKÉ.

1324
01:04:20,870 --> 01:04:22,880
És itt van, csak egy praktikus kis táblázatot.

1325
01:04:22,880 --> 01:04:26,850
Tudom, mindannyian, előtte kvíz 0,
lesz a szobádban valószínűleg megpróbál

1326
01:04:26,850 --> 01:04:27,960
megjegyeznünk, hogy.

1327
01:04:27,960 --> 01:04:30,940
Szóval ez szép ott a srácok.

1328
01:04:30,940 --> 01:04:37,120
Csak ne felejtsük el a logikát, hogy made--
Ezért ezeket a számokat is előforduló.

1329
01:04:37,120 --> 01:04:39,870
Ha mindig elvész, csak hogy
Biztosan tudom, mi a fajtákat.

1330
01:04:39,870 --> 01:04:40,820
És akkor végigmenni
ezek a fejedben

1331
01:04:40,820 --> 01:04:42,903
kitalálni, hogy miért
válaszok ezeket a válaszokat.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Minden rendben.

1334
01:04:47,600 --> 01:04:49,680
Mi is így fogjuk mozgatni
A végül a keresést.

1335
01:04:49,680 --> 01:04:51,638
Mert, mint azoknak,
akik elolvasták a PSET,

1336
01:04:51,638 --> 01:04:55,175
keresés is része
e heti probléma határozza.

1337
01:04:55,175 --> 01:04:57,300
Meg fogjuk kérni, hogy végre
kétféle keresést.

1338
01:04:57,300 --> 01:05:00,070
Az egyik egy lineáris keresés és
egy bináris keresés.

1339
01:05:00,070 --> 01:05:01,760
>> Tehát a lineáris keresés meglehetősen egyszerű.

1340
01:05:01,760 --> 01:05:04,070
Csak azt akarom, hogy keressen elem
Egy lista, hogy ha kap ez.

1341
01:05:04,070 --> 01:05:05,444
Csak meg kell halad végig.

1342
01:05:05,444 --> 01:05:08,170
És ha az egyenlő valamit,
akkor csak vissza, ugye?

1343
01:05:08,170 --> 01:05:10,890
De az, hogy mi vagyunk a legtöbb
Érdekel beszél

1344
01:05:10,890 --> 01:05:14,550
bináris keresés, jobb, ami a
oszd meg és uralkodj mechanizmust, amely

1345
01:05:14,550 --> 01:05:18,190
David volt, bizonyítja az előadás.

1346
01:05:18,190 --> 01:05:20,810
>> Ne feledje, a telefonkönyvben például
hogy ő tartja nevelő,

1347
01:05:20,810 --> 01:05:23,960
Az egyik, hogy azt a fajta küzdött
egy kicsit az elmúlt évben,

1348
01:05:23,960 --> 01:05:27,530
ahol ossza meg a problémát a felére,
fél, fél, újra és újra,

1349
01:05:27,530 --> 01:05:30,730
amíg meg nem találja, amit keres?

1350
01:05:30,730 --> 01:05:33,727
És megvan a
futásidejében hogy is.

1351
01:05:33,727 --> 01:05:35,810
És láthatjuk, hogy
jelentősen hatékonyabbá

1352
01:05:35,810 --> 01:05:39,080
mint bármilyen más típusú keresést.

1353
01:05:39,080 --> 01:05:41,880
>> Tehát az is, hogy mi járna el
végrehajtási bináris kereső

1354
01:05:41,880 --> 01:05:46,510
van, ha volt egy tömb,
index 0-6, hét elem,

1355
01:05:46,510 --> 01:05:49,790
tudjuk meg a közepén, right--
Sajnálom, ha a kérdésünkre first--

1356
01:05:49,790 --> 01:05:53,840
ha meg akarjuk feltenni a kérdést az, nem
a tömb tartalmazza az elem a 7,

1357
01:05:53,840 --> 01:05:56,840
Nyilvánvaló, hogy az emberek, és miután
Egy ilyen kis tömb, így könnyű a számunkra

1358
01:05:56,840 --> 01:05:58,210
igent mondani.

1359
01:05:58,210 --> 01:06:05,750
De a módja a bináris
Keresés lenne, hogy nézd közepén.

1360
01:06:05,750 --> 01:06:08,020
>> Tudjuk, hogy a mutató 3
a középső, mert mi

1361
01:06:08,020 --> 01:06:09,270
tudom, már csak hét elem.

1362
01:06:09,270 --> 01:06:10,670
Mit 7 osztva 2?

1363
01:06:10,670 --> 01:06:12,850
Akkor vágjunk le, hogy extra 1.

1364
01:06:12,850 --> 01:06:14,850
Megvan 3 a közepén.

1365
01:06:14,850 --> 01:06:17,590
Tehát tömb 3 egyenlő 7?

1366
01:06:17,590 --> 01:06:18,900
Nem, nem igaz?

1367
01:06:18,900 --> 01:06:21,050
De tehetünk egy pár ellenőrzések.

1368
01:06:21,050 --> 01:06:25,380
Van tömb 3 kevesebb, mint 7, vagy
a tömb 3 nagyobb, mint 7?

1369
01:06:25,380 --> 01:06:27,240
>> És tudjuk, hogy ez kevesebb, mint 7.

1370
01:06:27,240 --> 01:06:30,259
Tehát tudjuk, hogy, jaj, akkor azt
nem lehet a bal felét.

1371
01:06:30,259 --> 01:06:32,300
Tudjuk, hogy meg kell
a jobb fele, ugye?

1372
01:06:32,300 --> 01:06:34,662
Szóval mi csak levágja a felét a tömbben.

1373
01:06:34,662 --> 01:06:36,370
Nem is kell, hogy
nézd meg többé.

1374
01:06:36,370 --> 01:06:38,711
Mert tudjuk, hogy
fele a problem--

1375
01:06:38,711 --> 01:06:41,210
tudjuk, hogy a válasz
a jobb fele a mi problémánk.

1376
01:06:41,210 --> 01:06:42,580
Szóval csak nézd meg, hogy most.

1377
01:06:42,580 --> 01:06:44,860
>> Így most nézzük meg a
közepén, ami megmaradt.

1378
01:06:44,860 --> 01:06:46,880
Hogy index 5.

1379
01:06:46,880 --> 01:06:50,200
Mi nem ugyanaz a csekket
Úgy látjuk, hogy ez kisebb.

1380
01:06:50,200 --> 01:06:52,050
Így néz ki a bal oldalon, hogy.

1381
01:06:52,050 --> 01:06:53,430
És akkor azt látjuk, hogy a bejelentkezés.

1382
01:06:53,430 --> 01:06:57,600
A tömb érték
index 4 egyenlő 7?

1383
01:06:57,600 --> 01:06:58,260
Ez.

1384
01:06:58,260 --> 01:07:03,580
Így tudunk visszatérni igaz, mert
megtaláltuk az értéket a listánkon.

1385
01:07:03,580 --> 01:07:06,738
Vajon az út mentem keresztül
Van ennek valami értelme, hogy mindenki?

1386
01:07:06,738 --> 01:07:08,760
OKÉ.

1387
01:07:08,760 --> 01:07:11,670
Adok nektek talán, mint,
Három, négy perc kitalálni

1388
01:07:11,670 --> 01:07:13,270
hogyan pszeudókód ezt.

1389
01:07:13,270 --> 01:07:18,070
>> Így elképzelhető, kértem, hogy levelet
nevű függvény kereső (), hogy vissza

1390
01:07:18,070 --> 01:07:20,640
érték, egy logikai érték,
hogy igaz-e vagy false-- mint,

1391
01:07:20,640 --> 01:07:22,970
Igaz, ha megtalálták a
érték, hamis, ha nem.

1392
01:07:22,970 --> 01:07:25,230
És akkor volt
telt az érték, amit

1393
01:07:25,230 --> 01:07:28,410
kerestek be értékeket, amelyek
a array-- ó, én határozottan fel

1394
01:07:28,410 --> 01:07:29,410
hogy a rossz helyen.

1395
01:07:29,410 --> 01:07:29,580
OKÉ.

1396
01:07:29,580 --> 01:07:31,829
Egyébként, hogy legyen
volt, hogy a jobb értékeket.

1397
01:07:31,829 --> 01:07:36,280
És aztán int n a szám
Az elemek ebben a tömbben.

1398
01:07:36,280 --> 01:07:39,430
Hogyan megy megpróbálni
hogy pszeudókód, hogy a problémát?

1399
01:07:39,430 --> 01:07:41,630
Adok nektek tetszik
Három perc alatt megtenni.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Nem, azt hiszem, van only--
Igen, van még egy egészen itt.

1402
01:08:02,595 --> 01:08:03,261
Közönség: Can I?

1403
01:08:03,261 --> 01:08:04,388
ANDI Peng: Igen, hoztam neked.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Az, hogy a munkát?

1406
01:08:11,050 --> 01:08:12,290
OK, hűvös.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> OKÉ.

1409
01:10:44,720 --> 01:10:47,630
Rendben srácok vagyunk
fog fékezni azt.

1410
01:10:47,630 --> 01:10:49,730
OKÉ.

1411
01:10:49,730 --> 01:10:54,020
Tehát feltételezzük, megvan ez a szép
kis tömb n értékeket is.

1412
01:10:54,020 --> 01:10:55,170
Én nem a vonalak.

1413
01:10:55,170 --> 01:10:58,649
De hogyan érjük el
próbál írni?

1414
01:10:58,649 --> 01:11:00,440
Akar valaki
hogy nekem az első sorban?

1415
01:11:00,440 --> 01:11:02,814
Ha azt szeretnénk, hogy nekem a
első sorban ennek pszeudokódja.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> Közönség: [hallható]

1418
01:11:08,430 --> 01:11:10,138
Közönség: Az ember azt szeretné,
iterációkhoz through--

1419
01:11:10,138 --> 01:11:11,094
Közönség: Csak egy újabb hurok?

1420
01:11:11,094 --> 01:11:11,760
Közönség: --for.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI Peng: Szóval ez az ember egy kicsit trükkös.

1423
01:11:17,780 --> 01:11:23,130
Gondolj about-- szeretne
tartani fut ez a hurok

1424
01:11:23,130 --> 01:11:27,950
újra és újra, amíg mikor?

1425
01:11:27,950 --> 01:11:30,819
>> Közönség: Amíg a [hallhatatlan]
érték egyenlő az értékkel.

1426
01:11:30,819 --> 01:11:31,610
ANDI Peng: Pontosan.

1427
01:11:31,610 --> 01:11:33,900
Így valójában csak write--
mi is egyszerűsíti, hogy tovább.

1428
01:11:33,900 --> 01:11:35,630
Mi is csak nem egy while ciklus, ugye?

1429
01:11:35,630 --> 01:11:39,380
Így csak azt loop--
Tudjuk, hogy ez egy darabig.

1430
01:11:39,380 --> 01:11:42,850
De most, megyek
mondani, hogy "hurok" - a mi?

1431
01:11:42,850 --> 01:11:46,640
Hurok until-- mi
mi végződő állapota?

1432
01:11:46,640 --> 01:11:47,510
Azt hiszem, hallottam.

1433
01:11:47,510 --> 01:11:48,530
Hallottam, hogy valaki mondani.

1434
01:11:48,530 --> 01:11:51,255
>> Közönség: Értékek egyenlő közepén.

1435
01:11:51,255 --> 01:11:52,255
ANDI Peng: Mondd újra.

1436
01:11:52,255 --> 01:11:54,470
Közönség: Vagy, amíg a
értéke maga keresett

1437
01:11:54,470 --> 01:11:58,470
az egyenlő a középső érték.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI Peng: Mi van, ha nem ott?

1439
01:12:00,280 --> 01:12:03,113
Mi van, ha az érték, amit keres
A valójában nem ez a tömb?

1440
01:12:03,113 --> 01:12:05,890
Közönség: Visszatér 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI Peng: De mit akarunk
loop-ig, ha olyan az állapota?

1442
01:12:08,850 --> 01:12:09,350
Igen.

1443
01:12:09,350 --> 01:12:11,239
>> Közönség: Amíg csak egy van az érték?

1444
01:12:11,239 --> 01:12:13,530
ANDI Peng: Tudod hurok
until-- úgy tudja, hogy te

1445
01:12:13,530 --> 01:12:15,714
Lesz egy maximális érték, ugye?

1446
01:12:15,714 --> 01:12:18,130
És tudod, hogy fogsz
hogy egy perc értéket, nem igaz?

1447
01:12:18,130 --> 01:12:20,379
Mert azt is, hogy valami
Elfelejtettem mondani, mielőtt,

1448
01:12:20,379 --> 01:12:22,640
hogy valamit, ami
kritikusan bináris keresés

1449
01:12:22,640 --> 01:12:24,182
az, hogy a tömb már rendezve.

1450
01:12:24,182 --> 01:12:26,973
Mert nincs módja a
ez, ha ők csak a véletlen értékeket.

1451
01:12:26,973 --> 01:12:29,190
Nem tudom, ha az ember
nagyobb, mint a másik, ugye?

1452
01:12:29,190 --> 01:12:32,720
>> Szóval tudom, hogy a max és
Ön perc itt, ugye?

1453
01:12:32,720 --> 01:12:35,590
Ha lesz kiigazításáról
A max a perc, és a mid--

1454
01:12:35,590 --> 01:12:38,470
nézzük csak feltételezik, hogy a
közepén érték jobb here--

1455
01:12:38,470 --> 01:12:43,910
fogsz alapvetően
hurok, amíg a minimum

1456
01:12:43,910 --> 01:12:47,510
körülbelül ugyanaz, mint a max, jobbra, vagy
ha a max nem ugyanaz, mint a min.

1457
01:12:47,510 --> 01:12:48,040
Jobb?

1458
01:12:48,040 --> 01:12:51,340
Mert ha ez megtörténik, akkor tudjuk, hogy
amit végül elérje ugyanazt az értéket.

1459
01:12:51,340 --> 01:12:59,135
Tehát azt szeretnénk, hogy hurkot, amíg a min
kevesebb vagy egyenlő, mint az alábbiakra: Hoppá,

1460
01:12:59,135 --> 01:13:01,510
nem kevesebb, mint vagy egyenlő,
A másik út around-- max.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Tudta, hogy van értelme?

1463
01:13:16,160 --> 01:13:18,810
Vettem egy pár próbálkozás, hogy ezt a jogot.

1464
01:13:18,810 --> 01:13:21,869
De hurok, amíg a maximális érték
lényegében szinte kevesebb

1465
01:13:21,869 --> 01:13:23,410
vagy egyenlő, mint a minimális, ugye?

1466
01:13:23,410 --> 01:13:25,201
Ez az, amikor tudod,
hogy már közeledett.

1467
01:13:25,201 --> 01:13:29,290
Közönség: Ha azt a maximális
értéke kevesebb, mint a minimális?

1468
01:13:29,290 --> 01:13:31,040
ANDI Peng: Ha megtartja
kiigazítva, amely

1469
01:13:31,040 --> 01:13:32,380
mi megyünk
hogy csinál ebben.

1470
01:13:32,380 --> 01:13:33,460
Ennek van értelme?

1471
01:13:33,460 --> 01:13:35,750
Minimális és maximális csak
egészek, hogy mi valószínűleg

1472
01:13:35,750 --> 01:13:39,260
fog létrehozni kívánt tartani
követni, ahol keresünk.

1473
01:13:39,260 --> 01:13:41,790
Mivel a tömb létezik
függetlenül attól, hogy mit csinálunk.

1474
01:13:41,790 --> 01:13:45,030
Mint, nem vagyunk fizikailag
darabolás le a tömböt, ugye?

1475
01:13:45,030 --> 01:13:47,261
Mi csak beállító
ahol keresünk.

1476
01:13:47,261 --> 01:13:48,136
Ennek van értelme?

1477
01:13:48,136 --> 01:13:48,472
>> Közönség: Igen.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI Peng: OK.

1479
01:13:49,110 --> 01:13:57,090
Tehát ha ez a feltétele a hurok,
mit akarunk belül ez a hurok?

1480
01:13:57,090 --> 01:13:58,700
Mit fogunk kell akarnak csinálni?

1481
01:13:58,700 --> 01:14:02,390
Tehát most, megvan
max és min, igaz,

1482
01:14:02,390 --> 01:14:04,962
Valószínűleg készítette fel valahol.

1483
01:14:04,962 --> 01:14:07,170
Fogunk érdemes
találni egy középső, ugye?

1484
01:14:07,170 --> 01:14:08,450
Hogyan fogjuk, hogy
képes megtalálni a közepén?

1485
01:14:08,450 --> 01:14:09,491
Mi a mathematical--

1486
01:14:09,491 --> 01:14:11,079
Közönség: Max plusz min osztva 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI Peng: Pontosan.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Ennek van értelme?

1490
01:14:21,620 --> 01:14:25,780
És srácok, miért vagyunk
Nem csak use-- miért tette ezt

1491
01:14:25,780 --> 01:14:27,850
ahelyett, hogy csak n osztva 2?

1492
01:14:27,850 --> 01:14:30,310
Ez azért van, mert n értéke
hogy fog ugyanaz marad.

1493
01:14:30,310 --> 01:14:30,979
Jobb?

1494
01:14:30,979 --> 01:14:34,020
De ahogy igazítanunk a minimális és
maximum értékek, ők fognak változni.

1495
01:14:34,020 --> 01:14:36,040
És ennek eredményeként, a mi középső
meg fog változni is.

1496
01:14:36,040 --> 01:14:37,873
Szóval ezért szeretnénk
Ehhez itt.

1497
01:14:37,873 --> 01:14:38,510
OKÉ.

1498
01:14:38,510 --> 01:14:41,600
>> És akkor, most, hogy
találtunk our-- igen.

1499
01:14:41,600 --> 01:14:44,270
>> Közönség: Csak egy gyors question--
amikor azt mondja, min és max,

1500
01:14:44,270 --> 01:14:46,410
vagyunk feltételezve, hogy
ez már válogatni?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI Peng: Igen, ez valóban egy
előfeltétele a bináris keresés,

1502
01:14:48,400 --> 01:14:49,816
hogy van, hogy tudom, hogy válogatni.

1503
01:14:49,816 --> 01:14:53,660
Ezért van az a fajta, írsz a
probléma elé a bináris keresés.

1504
01:14:53,660 --> 01:14:55,910
OKÉ.

1505
01:14:55,910 --> 01:14:58,876
Most, hogy tudjuk, hol a középpont
van, mit akarsz itt csinálni?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> Közönség: Azt akarjuk összehasonlítani
hogy a másikat.

1508
01:15:04,319 --> 01:15:05,110
ANDI Peng: Pontosan.

1509
01:15:05,110 --> 01:15:12,280
Szóval lesz összehasonlítani
közép érték, ugye?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
És mit mond
minket, amikor összehasonlítani?

1512
01:15:18,670 --> 01:15:22,226
Mit akarunk csinálni utána?

1513
01:15:22,226 --> 01:15:25,389
>> Közönség: Ha az érték nagyobb
mint a közepén, azt akarjuk, hogy vágja le.

1514
01:15:25,389 --> 01:15:26,180
ANDI Peng: Pontosan.

1515
01:15:26,180 --> 01:15:33,940
Tehát, ha az érték nagyobb
mint a közepén vagyunk

1516
01:15:33,940 --> 01:15:36,550
akarnak változtatni ezen
minimum és maxes, ugye?

1517
01:15:36,550 --> 01:15:38,980
Mit akarunk változtatni?

1518
01:15:38,980 --> 01:15:42,145
Tehát, ha tudjuk, hogy az érték valahol
itt, mit is változtatni?

1519
01:15:42,145 --> 01:15:44,758
Azt akarjuk, hogy megváltoztassuk a
minimális legyen közepéig, igaz?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
És akkor még, ha ez ebben a
fele, mit akarunk változtatni?

1522
01:15:54,292 --> 01:15:55,306
>> Közönség: Az Ön maximális.

1523
01:15:55,306 --> 01:15:55,972
ANDI Peng: Igen.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
És akkor te csak megy
tartani hurok, ugye?

1526
01:16:04,680 --> 01:16:08,920
Mert most, miután az egyik ismétlés
keresztül, van egy max itt.

1527
01:16:08,920 --> 01:16:10,760
És akkor újraszámolja a közepén.

1528
01:16:10,760 --> 01:16:11,990
És akkor össze lehet hasonlítani.

1529
01:16:11,990 --> 01:16:14,766
És te fogsz tartani fog
amíg a perc, és a maxes

1530
01:16:14,766 --> 01:16:15,890
lényegében konvergens.

1531
01:16:15,890 --> 01:16:17,890
És ez az, amikor tudod, hogy
you hit a vége.

1532
01:16:17,890 --> 01:16:20,280
És akár már megtalálta
vagy még nem ezen a ponton.

1533
01:16:20,280 --> 01:16:23,170
>> Van ennek értelme mindenki?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
OKÉ.

1536
01:16:26,770 --> 01:16:27,900
Ez is nagyon fontos,
mert akkor már

1537
01:16:27,900 --> 01:16:29,760
hogy megírjam ezt a kódot ma este.

1538
01:16:29,760 --> 01:16:32,660
De a srácok egy nagyon jó
értelemben, hogy mit kell tennie,

1539
01:16:32,660 --> 01:16:34,051
ami jó.

1540
01:16:34,051 --> 01:16:34,550
OKÉ.

1541
01:16:34,550 --> 01:16:38,840
Tehát van hét
perc van hátra részt.

1542
01:16:38,840 --> 01:16:43,170
Így fogunk beszélni
ez PSET, hogy mi fog csinálni.

1543
01:16:43,170 --> 01:16:46,410
Tehát a PSET van osztva két részre.

1544
01:16:46,410 --> 01:16:50,230
Az első félidő során
végrehajtása találni

1545
01:16:50,230 --> 01:16:54,210
amelyben írsz egy lineáris keresés, a
bináris keresés, és a rendezési algoritmus.

1546
01:16:54,210 --> 01:16:56,690
>> Tehát ez az első
időt egy PSET, ahol

1547
01:16:56,690 --> 01:17:00,050
mi lesz így a srácok az úgynevezett
elosztási kód, amely a kód

1548
01:17:00,050 --> 01:17:02,740
hogy már előre megírt,
de csak maradt néhány darab ki

1549
01:17:02,740 --> 01:17:04,635
Ön számára, hogy befejezze az írás.

1550
01:17:04,635 --> 01:17:07,510
Szóval srácok, ha megnézed ezt
kódot, akkor lehet, hogy tényleg félek.

1551
01:17:07,510 --> 01:17:08,630
Ha csak tetszik, ahh, én
Nem tudom, hogy mit csinál,

1552
01:17:08,630 --> 01:17:11,670
Nem tudom, tetszik, hogy úgy tűnik,
olyan bonyolult, ahh, kikapcsolódásra.

1553
01:17:11,670 --> 01:17:12,170
Oké.

1554
01:17:12,170 --> 01:17:12,930
Olvassa el a spec.

1555
01:17:12,930 --> 01:17:16,920
A spec elmagyarázza Önnek, pontosan
mi minden program csinálnak.

1556
01:17:16,920 --> 01:17:20,560
>> Például generate.c egy olyan program
hogy jön a PSET.

1557
01:17:20,560 --> 01:17:24,060
Ugye nem kell hozzányúlni, de
meg kell értenie, hogy mit csinál.

1558
01:17:24,060 --> 01:17:28,550
És generate.c, minden csinál van
sem véletlen szám generálás

1559
01:17:28,550 --> 01:17:32,400
vagy lehet, hogy ez egy mag, mint egy
Előre megbeszélt számot tart,

1560
01:17:32,400 --> 01:17:34,140
és ez generál több számot.

1561
01:17:34,140 --> 01:17:37,170
Szóval van egy sajátos módja
végre generate.c amelyben

1562
01:17:37,170 --> 01:17:42,760
szeretne, csak egy csomó számok
Önnek, hogy tesztelje a más módszerekkel tovább.

1563
01:17:42,760 --> 01:17:45,900
>> Tehát, ha akarta, a
Például, tesztelje a lelet,

1564
01:17:45,900 --> 01:17:48,970
amit szeretne futni generate.c,
generál egy csomó számot,

1565
01:17:48,970 --> 01:17:50,880
majd futtassa a segítők funkciót.

1566
01:17:50,880 --> 01:17:53,930
Az Ön segítők feladata, ahol te
fizikailag kódot írni.

1567
01:17:53,930 --> 01:17:59,330
És gondolom, segítők, mint egy könyvtár fájl
írsz, hogy find hív.

1568
01:17:59,330 --> 01:18:02,950
És így belüli helpers.c, akkor
do keresés és válogatás.

1569
01:18:02,950 --> 01:18:06,500
>> És akkor fogsz lényegében
Csak őket együtt.

1570
01:18:06,500 --> 01:18:10,350
A specifikáció megmondja, hogyan kell
tedd, hogy a parancssorban.

1571
01:18:10,350 --> 01:18:14,880
És akkor képes lesz arra, hogy tesztelje vagy
Nem a sort és a keresési dolgozik.

1572
01:18:14,880 --> 01:18:15,870
Hűvös.

1573
01:18:15,870 --> 01:18:18,720
Valaki már elkezdődött és
felmerült problémák és kérdések

1574
01:18:18,720 --> 01:18:20,520
nekik van most ezzel?

1575
01:18:20,520 --> 01:18:21,020
OKÉ.

1576
01:18:21,020 --> 01:18:21,476
>> Közönség: Várj.

1577
01:18:21,476 --> 01:18:21,932
Kérdésem van.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI Peng: Igen.

1579
01:18:22,844 --> 01:18:28,390
>> Közönség: Szóval elkezdtem
A lineáris keresés helpers.c

1580
01:18:28,390 --> 01:18:29,670
és ez nem igazán működik.

1581
01:18:29,670 --> 01:18:34,590
De aztán később megtudtam mi csak
kell törölni, és nem bináris keresés.

1582
01:18:34,590 --> 01:18:36,991
Tehát nem mindegy, ha ez nem működik?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI Peng: Rövid válasz: nem.

1585
01:18:41,510 --> 01:18:42,642
De mivel mi vagyunk nem--

1586
01:18:42,642 --> 01:18:44,350
Közönség: De senki
ténylegesen ellenőrzi.

1587
01:18:44,350 --> 01:18:46,058
ANDI Peng: soha nem vagyunk
fog látni.

1588
01:18:46,058 --> 01:18:49,590
De akkor érdemes tenni
arról a keresést dolgozik.

1589
01:18:49,590 --> 01:18:51,700
Mert ha a lineáris
keresés nem működik,

1590
01:18:51,700 --> 01:18:54,410
akkor jó esélye van a bináris
keresés nem fog működni is.

1591
01:18:54,410 --> 01:18:56,646
Mert van hasonló
logika mind a ketten.

1592
01:18:56,646 --> 01:18:58,020
És nem, ez nem igazán számít.

1593
01:18:58,020 --> 01:19:01,300
Tehát az egyetlenek, akkor kapcsolja
A sort a bináris keresés.

1594
01:19:01,300 --> 01:19:02,490
Igen.

1595
01:19:02,490 --> 01:19:06,610
>> És azt is, sok gyerek volt
megpróbálnád fordítani helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Te valójában nem engedélyezettek
erre, mert helpers.c

1597
01:19:09,550 --> 01:19:11,200
Nincsenek fő funkciója.

1598
01:19:11,200 --> 01:19:13,550
És ezért csak akkor
ténylegesen összeállítása

1599
01:19:13,550 --> 01:19:18,670
generál és megtalálni, mert megtalálják hívások
helpers.c és a funkciók benne.

1600
01:19:18,670 --> 01:19:20,790
Szóval, ami hibakeresés
A fájdalom a seggét.

1601
01:19:20,790 --> 01:19:22,422
De ez az, amit tennünk kell.

1602
01:19:22,422 --> 01:19:23,880
Közönség: Csak, hogy minden, ugye?

1603
01:19:23,880 --> 01:19:27,290
ANDI Peng: Tudod csak
hogy minden is, igen.

1604
01:19:27,290 --> 01:19:28,060
OKÉ.

1605
01:19:28,060 --> 01:19:32,570
Szóval ennyi szempontjából milyen
A PSET azt kéri, hogy mindenki tegye.

1606
01:19:32,570 --> 01:19:35,160
Ha bármilyen kérdésed van, nyugodtan
kérdezz meg szakasz után.

1607
01:19:35,160 --> 01:19:37,580
Én itt leszek, Mert mint 20 perc.

1608
01:19:37,580 --> 01:19:40,500
>> És igen, a PSET a
nem is olyan rossz.

1609
01:19:40,500 --> 01:19:41,680
Srácok jónak kell lennie.

1610
01:19:41,680 --> 01:19:43,250
Ezek, csak követniük.

1611
01:19:43,250 --> 01:19:47,840
Valami van értelme a logikus, hogy mi
történniük kellene, és akkor rendben lesz.

1612
01:19:47,840 --> 01:19:48,690
Ne legyen túl félek.

1613
01:19:48,690 --> 01:19:50,220
Van egy csomó kód
Már írt ott.

1614
01:19:50,220 --> 01:19:53,011
Ne legyen túl félek, ha nem
megérteni, mi minden jelent.

1615
01:19:53,011 --> 01:19:54,749
Ha ez a sok, ez teljesen rendben van.

1616
01:19:54,749 --> 01:19:55,790
És jönnek munkaidőben.

1617
01:19:55,790 --> 01:19:57,520
Segítünk, hogy egy pillantást.

1618
01:19:57,520 --> 01:20:00,810
>> Közönség: Az extra
funkciók, ne nézzük ezeket fel?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI Peng: Igen, ezek a kódot.

1620
01:20:03,417 --> 01:20:05,750
A játékban 15, fele
ez már írt neked.

1621
01:20:05,750 --> 01:20:09,310
Tehát ezek a függvények
Már a kódot.

1622
01:20:09,310 --> 01:20:12,020
Ja.

1623
01:20:12,020 --> 01:20:12,520
Minden rendben.

1624
01:20:12,520 --> 01:20:14,000
Nos, sok szerencsét.

1625
01:20:14,000 --> 01:20:15,180
Ez egy undorító nap.

1626
01:20:15,180 --> 01:20:19,370
Így remélhetőleg nektek nem érzem túl
Rosszul bent és kódolás.

1627
01:20:19,370 --> 01:20:22,133