1
00:00:00,000 --> 00:00:11,100

2
00:00:11,100 --> 00:00:12,300
>> SPEAKER 1: Hey mindenki!

3
00:00:12,300 --> 00:00:13,890
Üdv újra a szakasz.

4
00:00:13,890 --> 00:00:17,480
Örülök, hogy ilyen sokan itt is,
és mindenki, aki figyel az interneten.

5
00:00:17,480 --> 00:00:18,760

6
00:00:18,760 --> 00:00:20,920
Szóval, mint mindig szívesen vissza.

7
00:00:20,920 --> 00:00:24,360
Remélem, hogy mindannyian egy szép
hétvége, tele pihenés, kikapcsolódás.

8
00:00:24,360 --> 00:00:26,026
Gyönyörű volt tegnap.

9
00:00:26,026 --> 00:00:27,525
Szóval, remélem, tetszett a szabadban.

10
00:00:27,525 --> 00:00:28,840

11
00:00:28,840 --> 00:00:30,610
>> Tehát először egy pár bejelentések.

12
00:00:30,610 --> 00:00:31,920

13
00:00:31,920 --> 00:00:32,700
Osztályozás.

14
00:00:32,700 --> 00:00:37,350
Szóval, a legtöbb akkor ütött egy
e-mailbe nekem a Scratch Pset,

15
00:00:37,350 --> 00:00:39,920
valamint az osztályozási Pset 1.

16
00:00:39,920 --> 00:00:41,000

17
00:00:41,000 --> 00:00:42,220
Szóval, csak egy pár dolgot.

18
00:00:42,220 --> 00:00:45,150
Ügyeljen arra, hogy a check50 style50.

19
00:00:45,150 --> 00:00:47,250
Ezek célja, hogy
források srácok,

20
00:00:47,250 --> 00:00:50,660
hogy megbizonyosodjon arról, hogy kapsz
annyi pontot, amennyit csak tudsz

21
00:00:50,660 --> 00:00:52,390
anélkül, hogy feleslegesen elveszítik.

22
00:00:52,390 --> 00:00:54,407
Szóval, a dolgok, mint a stílus
nagyon fontos.

23
00:00:54,407 --> 00:00:55,740
Mi lesz, hogy vegye le azt.

24
00:00:55,740 --> 00:00:58,115
Néhányan talán már
észrevette, hogy az Ön Pset.

25
00:00:58,115 --> 00:00:58,920

26
00:00:58,920 --> 00:01:01,450
És check50 csak egy
nagyon egyszerű módja annak, hogy

27
00:01:01,450 --> 00:01:05,050
hogy mi valójában mit vissza
vissza kell küldenie a felhasználó,

28
00:01:05,050 --> 00:01:06,690
és hogy minden működik megfelelően.

29
00:01:06,690 --> 00:01:08,690

30
00:01:08,690 --> 00:01:12,040
>> A második megjegyzés, győződjön meg róla,
feltölteni dolgokat a megfelelő mappába.

31
00:01:12,040 --> 00:01:14,470
Ez teszi az életem csak egy
kicsit nehezebb

32
00:01:14,470 --> 00:01:18,836
ha feltölt Pset 2 az 1 Pset
mert amikor én letölteni a dolgokat,

33
00:01:18,836 --> 00:01:20,085
nem helyesen letölteni.

34
00:01:20,085 --> 00:01:21,690

35
00:01:21,690 --> 00:01:24,560
És tudom, hogy ez egy kicsit rozoga
rendszerben kell szokni,

36
00:01:24,560 --> 00:01:26,950
de csak szuper
óvatos, ha csak nekem,

37
00:01:26,950 --> 00:01:30,080
így amikor kapok e-mailt
A mint 2:00 és én vagyok osztályozás.

38
00:01:30,080 --> 00:01:33,710
Ha nem okoz azt kell nézni
körül a Pset.

39
00:01:33,710 --> 00:01:34,440
Cool.

40
00:01:34,440 --> 00:01:37,270
>> Tudom, hogy korán van, de én
Teljesen kapott levették őr

41
00:01:37,270 --> 00:01:40,800
egy esszé, ami miatt ezen a héten pénteken, hogy
tanáraim voltak, mint, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Ne feledje, hogy egy
esszé esedékes pénteken.

43
00:01:42,550 --> 00:01:45,780
Szóval, tudom, hogy senki sem szereti
gondolni midterms,

44
00:01:45,780 --> 00:01:50,620
de az első kvíz október 15-én,
amely október kezd ezen a héten.

45
00:01:50,620 --> 00:01:53,290
Szóval, lehet, hogy előbb
a vártnál minden.

46
00:01:53,290 --> 00:01:57,510
Annak érdekében, hogy te nem dobták ki őr, ha
Azért említem a jövő heti rész, hogy jaj,

47
00:01:57,510 --> 00:02:00,560
A kvíz a jövő héten, azt hittem,
Adnék egy kicsit

48
00:02:00,560 --> 00:02:01,500
A heads-up most.

49
00:02:01,500 --> 00:02:02,970

50
00:02:02,970 --> 00:02:04,660
>> Tehát a probléma beállítva, három szám.

51
00:02:04,660 --> 00:02:07,070
Hogy az emberek olvasni a
spec a kíváncsiság?

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
OK.

54
00:02:09,199 --> 00:02:10,229
Van egy pár.

55
00:02:10,229 --> 00:02:12,320
Kicsit le az utolsó
héten, de ez rendben van.

56
00:02:12,320 --> 00:02:13,650
Tudom, hogy gyönyörű out.

57
00:02:13,650 --> 00:02:15,120

58
00:02:15,120 --> 00:02:16,660
Így kitörni.

59
00:02:16,660 --> 00:02:21,010
Határozottan után kap tenni
Ma olvastam a spec legalább

60
00:02:21,010 --> 00:02:25,240
próbálja meg, mint letölteni
elosztás kód és futás

61
00:02:25,240 --> 00:02:27,430
mint az első eredeti
dolog, hogy kérjük, hogy.

62
00:02:27,430 --> 00:02:28,681

63
00:02:28,681 --> 00:02:32,590
Mert mi használ
eloszlás kód és a könyvtár

64
00:02:32,590 --> 00:02:36,790
hogy mi már csak using-- --It csak
a második alkalom, hogy megtette ezt Pset,

65
00:02:36,790 --> 00:02:38,650
őrült dolog történhet
az a készülék,

66
00:02:38,650 --> 00:02:41,370
és meg akarja találni, hogy
ki most versus később.

67
00:02:41,370 --> 00:02:45,570
>> Mert ha ez a csütörtök este, vagy ez
Szerda este, és valamilyen oknál fogva

68
00:02:45,570 --> 00:02:48,912
a készülék csak nem
szeretné futtatni a könyvtár

69
00:02:48,912 --> 00:02:50,620
vagy forgalmazásával
kódot, hogy eszközök

70
00:02:50,620 --> 00:02:52,309
akkor nem is kezdeni ezzel a kódolás.

71
00:02:52,309 --> 00:02:54,100
Mert nem tudja ellenőrizni
hogy ha működik.

72
00:02:54,100 --> 00:02:55,975
Ön nem lesz képes
hogy ha lefordítja.

73
00:02:55,975 --> 00:03:00,500
Azt akarod, hogy vigyázzon az ilyen korán
A hét, amikor is e-mailt nekem

74
00:03:00,500 --> 00:03:03,100
vagy az egyik a másik TF,
és kapunk a fix.

75
00:03:03,100 --> 00:03:05,410
Mivel ezek olyan kérdések,
hogy fognak megállítani

76
00:03:05,410 --> 00:03:07,120
attól, hogy valódi előrelépés.

77
00:03:07,120 --> 00:03:10,055
Ez nem olyan, mint egy hiba, hogy
akkor csak ilyen átugorják.

78
00:03:10,055 --> 00:03:10,712

79
00:03:10,712 --> 00:03:13,420
Ha problémái vannak a
készülék vagy forgalmazási kódot,

80
00:03:13,420 --> 00:03:16,211
szeretné, hogy kap, hogy a meghozandó
érdekel az inkább előbb, mint utóbb.

81
00:03:16,211 --> 00:03:20,410
Tehát akkor is, ha nem fog ténylegesen
elkezdeni kódolni, töltse le az elosztás

82
00:03:20,410 --> 00:03:24,040
kód, olvassa el a spec, győződjön meg róla,
minden működik ott.

83
00:03:24,040 --> 00:03:25,134
OK?

84
00:03:25,134 --> 00:03:27,675
Ha tudod csak csinálni, én
Megígérem életetek könnyebb lesz.

85
00:03:27,675 --> 00:03:28,800

86
00:03:28,800 --> 00:03:31,410
És akkor valószínűleg megy
csinálni most jobb?

87
00:03:31,410 --> 00:03:32,100
OK.

88
00:03:32,100 --> 00:03:33,950
Tehát bármilyen kérdése van?

89
00:03:33,950 --> 00:03:35,850
Minden logisztikai dolgokat?

90
00:03:35,850 --> 00:03:36,910
Mindenki jó?

91
00:03:36,910 --> 00:03:38,270
OK.

92
00:03:38,270 --> 00:03:41,700
>> Fontos azoknak a
Ön a szobában és az online.

93
00:03:41,700 --> 00:03:45,437
Megyek próbál váltani
között PowerPoint a készülék

94
00:03:45,437 --> 00:03:47,270
mert megyünk
hogy csinál valami kódolás

95
00:03:47,270 --> 00:03:53,630
Ma a népszerű kereslet az anonim
javaslat szavazás küldtem ki a múlt héten.

96
00:03:53,630 --> 00:03:55,480
Szóval, mi lesz ennek valami kódolás.

97
00:03:55,480 --> 00:03:57,800
Tehát, ha ti is akar
hogy indítsa el a készülék,

98
00:03:57,800 --> 00:04:02,910
és akkor már megvan egy e-mailt
tőlem, egy minta fájlt.

99
00:04:02,910 --> 00:04:04,310
Kérjük, hogy erre.

100
00:04:04,310 --> 00:04:07,340
>> Szóval, fogunk beszélni
GDB, ami a debugger.

101
00:04:07,340 --> 00:04:09,970
Ez fog segíteni
fajta kitalálni, hogy hol

102
00:04:09,970 --> 00:04:11,860
a dolgok rosszul a kódban.

103
00:04:11,860 --> 00:04:15,370
Ez tényleg csak egy módja, hogy lépést
át a kódot, ez történik,

104
00:04:15,370 --> 00:04:19,100
és képesnek kell lennie, hogy nyomtassa ki a változók
vagy, hogy mi történik valójában

105
00:04:19,100 --> 00:04:22,980
a motorháztető alatt verseket a programot
éppen fut, ez olyan, mint hibás,

106
00:04:22,980 --> 00:04:25,030
és te, mint, fogalmam sincs,
mi történt itt.

107
00:04:25,030 --> 00:04:26,730
Nem tudom, mit nem sikerült a sort.

108
00:04:26,730 --> 00:04:29,040
Nem tudom, hol rontottam el.

109
00:04:29,040 --> 00:04:31,280
Szóval, GDB fog segíteni neked ebben.

110
00:04:31,280 --> 00:04:35,240
Továbbá, ha úgy dönt, hogy
tovább igen, és megteszi a 61.,

111
00:04:35,240 --> 00:04:38,430
ez tényleg, igazán meg
legjobb barátom, mert azt lehet mondani,

112
00:04:38,430 --> 00:04:40,840
mert megyek át az osztályban.

113
00:04:40,840 --> 00:04:43,620
>> Fogunk nézni bináris
keresés, amely, ha a srácok eszébe jut

114
00:04:43,620 --> 00:04:47,540
a nagy telefonkönyv példa
látvány az osztályból.

115
00:04:47,540 --> 00:04:50,620
Mi lesz azt végrehajtó, és
séta, hogy egy kicsit,

116
00:04:50,620 --> 00:04:54,650
aztán megyünk keresztül négy
fajtájára, amelyek Bubble,

117
00:04:54,650 --> 00:04:56,285
Selection, beszúrás, és egyesítése.

118
00:04:56,285 --> 00:04:57,830

119
00:04:57,830 --> 00:04:58,330
Cool.

120
00:04:58,330 --> 00:05:00,390
Szóval, GDB mint említettem, egy debugger.

121
00:05:00,390 --> 00:05:01,400

122
00:05:01,400 --> 00:05:09,370
És ezek a fajta nagy
dolgok, a nagy funkciók és parancsok

123
00:05:09,370 --> 00:05:13,240
hogy használja GDB belül, és én járni
Ön egy demo azt egy másik.

124
00:05:13,240 --> 00:05:15,360
>> Szóval, ez nem csak
fog maradni elvont.

125
00:05:15,360 --> 00:05:18,000
Megpróbálom, és ez a konkrét
lehetséges a srácok.

126
00:05:18,000 --> 00:05:19,870
Szóval, szünet.

127
00:05:19,870 --> 00:05:22,200
Ez lesz vagy legyen szünet
mint például, néhány szám, amely

128
00:05:22,200 --> 00:05:26,900
jelentése sor a programban,
vagy nevet adhat a funkciót.

129
00:05:26,900 --> 00:05:30,150
Tehát, ha mondjuk a fő szünet,
akkor megáll a legfontosabb,

130
00:05:30,150 --> 00:05:32,400
és hagyom, hogy ezt a funkciót séta.

131
00:05:32,400 --> 00:05:36,350
>> Hasonlóképpen, ha van valamilyen külső
úgy működnek, mint a Csere vagy Cube,

132
00:05:36,350 --> 00:05:38,450
néztük meg a múlt héten.

133
00:05:38,450 --> 00:05:41,780
Ha azt mondod, csak egyet is megront e,
amikor a programot, hogy üt,

134
00:05:41,780 --> 00:05:44,290
ez lesz várni, hogy
mondani, hogy mi a teendő.

135
00:05:44,290 --> 00:05:47,860
Mielőtt majd csak végre, így
ténylegesen beléphet a funkció

136
00:05:47,860 --> 00:05:49,020
meg, hogy mi folyik itt.

137
00:05:49,020 --> 00:05:50,370

138
00:05:50,370 --> 00:05:53,515
Szóval, Next, csak átugorja a
következő sorba megy át funkciókat.

139
00:05:53,515 --> 00:05:54,730

140
00:05:54,730 --> 00:05:55,560
Step.

141
00:05:55,560 --> 00:05:56,810
Ezek mind apró elvont.

142
00:05:56,810 --> 00:06:00,530
Szóval, én csak fog futni rajtuk,
de látni fogod őket használat a második.

143
00:06:00,530 --> 00:06:01,810
>> Lépjen be a funkciót.

144
00:06:01,810 --> 00:06:04,170
Szóval mint mondtam,
mint a Swap, akkor

145
00:06:04,170 --> 00:06:07,110
lehetővé teszi, hogy valóban, mintha te
mint fizikailag léptető belül,

146
00:06:07,110 --> 00:06:10,990
akkor rendetlenség azokat a változókat, nyomtatás
ki, mik ezek, hogy mi folyik itt.

147
00:06:10,990 --> 00:06:12,140

148
00:06:12,140 --> 00:06:14,830
Listája a szó szoros értelmében csak nyomtatni
ki a környező kódot.

149
00:06:14,830 --> 00:06:17,570
Tehát, ha a fajta elfelejteni
hol van a programban,

150
00:06:17,570 --> 00:06:19,880
vagy te kíváncsi
mi folyik körülötte,

151
00:06:19,880 --> 00:06:23,790
ez csak nyomtassa ki a szegmens
A, mint öt vagy hat sor körül.

152
00:06:23,790 --> 00:06:26,080
Szóval, lehet kapni orientált
arról, hogy hol vannak.

153
00:06:26,080 --> 00:06:27,230

154
00:06:27,230 --> 00:06:28,650
>> Nyomtatás néhány változó.

155
00:06:28,650 --> 00:06:34,590
Tehát, ha a kulcs, mint
Caesar, hogy akkor nézd meg.

156
00:06:34,590 --> 00:06:36,220
Azt lehet mondani, nyomtatás Key bármikor.

157
00:06:36,220 --> 00:06:40,070
Azt fogja mondani, hogy mi az érték, így
hogy talán valahol az út mentén,

158
00:06:40,070 --> 00:06:42,070
Ön felülírta a kulcsot.

159
00:06:42,070 --> 00:06:45,495
Tudod valójában mondani, hogy azért, mert
akkor valóban megfigyelhető, hogy az érték.

160
00:06:45,495 --> 00:06:46,500

161
00:06:46,500 --> 00:06:48,780
>> A helyiek, csak nyomtat
meg a helyi változókat.

162
00:06:48,780 --> 00:06:53,120
Szóval, bármikor maga egy hurok,
és te csak azt szeretném látni, mint, oh.

163
00:06:53,120 --> 00:06:54,270
Mi az én?

164
00:06:54,270 --> 00:06:57,020
Mi ez a kulcs érték
hogy én inicializálni itt?

165
00:06:57,020 --> 00:06:58,537
Mi az az üzenet, ezen a ponton?

166
00:06:58,537 --> 00:07:00,370
Ez csak nyomtatni minden
e, úgy, hogy

167
00:07:00,370 --> 00:07:04,330
Nem kell külön-külön
mondjuk, I. Print Nyomtatás üzenet.

168
00:07:04,330 --> 00:07:04,970
Print Key.

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
És akkor Display.

171
00:07:07,700 --> 00:07:10,370
Mi az, hogy nem, mint te
menj végig a programot,

172
00:07:10,370 --> 00:07:13,980
akkor csak győződjön meg róla, hogy ez az
megjelenítése néhány bizonyos változó

173
00:07:13,980 --> 00:07:14,780
minden pontján.

174
00:07:14,780 --> 00:07:17,160
Úgy, hogy ez also-- --it
egyfajta parancsikon ahol

175
00:07:17,160 --> 00:07:19,530
nem kell, hogy menj, mint, oh.

176
00:07:19,530 --> 00:07:23,150
Print vagy Print Key I. Ez csak
automatikusan megcsinálja helyetted.

177
00:07:23,150 --> 00:07:25,959
>> Szóval, hogy mi megyünk
hogy milyen ez megy.

178
00:07:25,959 --> 00:07:28,000
Fogom próbálni és switch
át a készüléket.

179
00:07:28,000 --> 00:07:30,200

180
00:07:30,200 --> 00:07:31,271
Lássuk, meg tudom csinálni ezt.

181
00:07:31,271 --> 00:07:31,770
All.

182
00:07:31,770 --> 00:07:40,970

183
00:07:40,970 --> 00:07:42,370
Mi csak úgy a tükör is.

184
00:07:42,370 --> 00:07:44,530
Nincs semmi őrült
az én laptop egyébként.

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
OK.

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
Ez kell, hogy legyen ez.

189
00:08:01,054 --> 00:08:01,795
Ez annyira apró.

190
00:08:01,795 --> 00:08:03,730

191
00:08:03,730 --> 00:08:05,120
Lássuk, ha képes erre.

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> OK.

194
00:08:10,940 --> 00:08:15,305
Alice nyilvánvalóan küzd
itt egy kicsit,

195
00:08:15,305 --> 00:08:17,995
de mi lesz akkor a momento.

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
OK.

198
00:08:22,020 --> 00:08:25,900
Mi csak növekedni fog ez.

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
OK.

201
00:08:29,380 --> 00:08:31,679
Lehet mindenki milyen látni, hogy?

202
00:08:31,679 --> 00:08:32,470
Talán egy kicsit?

203
00:08:32,470 --> 00:08:33,594
Tudom, hogy ez egy kicsit kicsi.

204
00:08:33,594 --> 00:08:34,570

205
00:08:34,570 --> 00:08:37,530
Nem lehet elég kitalálni,
hogyan lehet ezt a nagyobb.

206
00:08:37,530 --> 00:08:38,350
Ha valaki tudja.

207
00:08:38,350 --> 00:08:40,309
Tudja valaki, hogyan kell tenni a nagyobb?

208
00:08:40,309 --> 00:08:40,932
OK.

209
00:08:40,932 --> 00:08:42,140
Fogunk roll vele.

210
00:08:42,140 --> 00:08:45,801
Nem számít egyébként, mert ez csak
hogy a kód, amit a srácok kellene

211
00:08:45,801 --> 00:08:46,300
van.

212
00:08:46,300 --> 00:08:48,310
>> Mi a fontosabb
a terminál itt.

213
00:08:48,310 --> 00:08:52,840

214
00:08:52,840 --> 00:08:58,690
És mi van itt Miért olyan kicsi?

215
00:08:58,690 --> 00:09:02,325

216
00:09:02,325 --> 00:09:02,825
Beállítások.

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
Oh.

219
00:09:08,420 --> 00:09:09,500
Igaz Ike.

220
00:09:09,500 --> 00:09:10,880
Hogy ez?

221
00:09:10,880 --> 00:09:11,770
Onnan.

222
00:09:11,770 --> 00:09:19,370

223
00:09:19,370 --> 00:09:21,810
Ez jobb mindenkinek?

224
00:09:21,810 --> 00:09:22,525
OK ,.

225
00:09:22,525 --> 00:09:23,025
Cool.

226
00:09:23,025 --> 00:09:25,830

227
00:09:25,830 --> 00:09:28,220
>> Tudod, amikor az ember a CS
osztály technikai nehézségek

228
00:09:28,220 --> 00:09:32,971
a fajta részének a--
Nos, nézzük törölje ezt.

229
00:09:32,971 --> 00:09:33,470
OK.

230
00:09:33,470 --> 00:09:38,060
Szóval, itt a rész,
ami volt itt.

231
00:09:38,060 --> 00:09:40,830
Caesar egy futtatható fájl.

232
00:09:40,830 --> 00:09:41,800
Szóval tette.

233
00:09:41,800 --> 00:09:46,370
Szóval, az egyik dolog, hogy észre a GDB
hogy csak akkor működik, futtatható fájlokat.

234
00:09:46,370 --> 00:09:48,040
Szóval, nem tudja futtatni a dotsy.

235
00:09:48,040 --> 00:09:50,532
Meg kell, hogy valóban tenni
arról, hogy a kód lefordul,

236
00:09:50,532 --> 00:09:51,865
és hogy ténylegesen futni.

237
00:09:51,865 --> 00:09:52,970

238
00:09:52,970 --> 00:09:56,186
>> Szóval, győződjön meg arról, hogy ha nem
lefordítani,, hogy a program,

239
00:09:56,186 --> 00:09:57,810
így ilyen fut át ​​rajta.

240
00:09:57,810 --> 00:10:04,590
Így kezdeni GDB, minden, amit csinál,
Gloria típusú GDB, és majd csak a

241
00:10:04,590 --> 00:10:06,250
fájl, amit akar.

242
00:10:06,250 --> 00:10:08,240
Mindig elgépelt Caesar.

243
00:10:08,240 --> 00:10:11,730
De azt szeretnénk, hogy győződjön meg arról,
mivel ez egy végrehajtható,

244
00:10:11,730 --> 00:10:14,210
ti a pont, hogy a vaku
azt jelenti, hogy mész

245
00:10:14,210 --> 00:10:19,240
futtatni CSI fogsz végre
ezt fájlokat akár a debugger.

246
00:10:19,240 --> 00:10:19,910
OK.

247
00:10:19,910 --> 00:10:22,885
Szóval, akkor, kapsz
ez a fajta halandzsa.

248
00:10:22,885 --> 00:10:24,250

249
00:10:24,250 --> 00:10:25,750
Csak egész dolgot debugger.

250
00:10:25,750 --> 00:10:28,200
Nem igazán kell
aggódni, hogy most.

251
00:10:28,200 --> 00:10:31,460
És mint látod, itt van ez a
nyitott parens, GDP, közeli parens,

252
00:10:31,460 --> 00:10:34,690
és csak hasonít
a parancssor, ugye?

253
00:10:34,690 --> 00:10:37,010
>> Szóval, mit akarunk do--
--So, Az első dolog,

254
00:10:37,010 --> 00:10:39,570
az, akarunk választani
Egy hely, ahol törni.

255
00:10:39,570 --> 00:10:42,332
Szóval, van egy bug
ebben Caesar programban

256
00:10:42,332 --> 00:10:44,290
hogy bemutatom, hogy
fogjuk megtudni.

257
00:10:44,290 --> 00:10:45,330

258
00:10:45,330 --> 00:10:56,350
Ez mi ez az tart a bemenet
Barfoo minden sapkák, és valamilyen oknál fogva

259
00:10:56,350 --> 00:11:01,950
ez nem változik A. Csak hagy
egyedül, minden mást a helyes,

260
00:11:01,950 --> 00:11:03,980
de a második levél
Egy változatlan marad.

261
00:11:03,980 --> 00:11:07,120
Szóval, megyünk próbálni, és
rájönni, hogy miért van ez.

262
00:11:07,120 --> 00:11:10,440
Tehát az első dolog, amit általában
akar csinálni, amikor kezdődik GDB

263
00:11:10,440 --> 00:11:12,010
hogy kitaláljuk, hol törni.

264
00:11:12,010 --> 00:11:14,956
>> Így Caesar egy nagyon rövid programot.

265
00:11:14,956 --> 00:11:16,330
Csak egy funkció, igaz?

266
00:11:16,330 --> 00:11:18,520
Mi volt a funkciója Caesar?

267
00:11:18,520 --> 00:11:19,590

268
00:11:19,590 --> 00:11:24,350
Csak egy függvény, Main jobb?

269
00:11:24,350 --> 00:11:26,490
Main függvény
az összes programot.

270
00:11:26,490 --> 00:11:29,230
Ha nem rendelkezik Main, talán
egy kicsit aggódott most,

271
00:11:29,230 --> 00:11:31,000
de remélem, mindannyian Main ott.

272
00:11:31,000 --> 00:11:34,150
Szóval, mit tehetünk az, hogy mi is
csak szünet Main, csak úgy.

273
00:11:34,150 --> 00:11:35,190
Szóval, azt mondja, rendben van.

274
00:11:35,190 --> 00:11:37,430
Mi meg a töréspont ott.

275
00:11:37,430 --> 00:11:42,870
>> Szóval, most a dolog, hogy emlékezzen, Caesar
vesz egy parancssori argumentum helyes

276
00:11:42,870 --> 00:11:45,150
és mi nem történt meg, hogy sehol sem.

277
00:11:45,150 --> 00:11:47,560
Szóval, mit csinálsz, amikor
valóban megy futni

278
00:11:47,560 --> 00:11:51,540
A program olyan program, amely maga
futó GDB igénylő parancssorban

279
00:11:51,540 --> 00:11:55,010
érvek fogsz bemenet
amikor először kezdi fut.

280
00:11:55,010 --> 00:11:59,280
Szóval, ebben az esetben, mi
Fuss egy kulcsfontosságú a három.

281
00:11:59,280 --> 00:12:00,770

282
00:12:00,770 --> 00:12:02,040
És ez valóban indul.

283
00:12:02,040 --> 00:12:08,480
>> Tehát, ha úgy látja, itt van
Ha a RC nem egyenlő 2.

284
00:12:08,480 --> 00:12:12,210
Tehát, ha a srácok mind
a fájl, hogy én küldtem ki fel

285
00:12:12,210 --> 00:12:15,100
látni fogod, hogy ez olyan, mint a
első sorban a fő funkciója, ugye?

286
00:12:15,100 --> 00:12:17,890
Ez ellenőrzi, hogy ha van
a megfelelő számú érvet.

287
00:12:17,890 --> 00:12:20,620
Tehát, ha kíváncsi
ha RC helyes,

288
00:12:20,620 --> 00:12:23,250
meg tudod csinálni valamit, mint Print RC.

289
00:12:23,250 --> 00:12:24,380

290
00:12:24,380 --> 00:12:28,640
RC kettő, ami
amit vártunk, nem?

291
00:12:28,640 --> 00:12:32,010
>> Szóval, mehetünk Next,
és tovább folytatódik.

292
00:12:32,010 --> 00:12:33,200
Szóval, van néhány kulcsfontosságú ott.

293
00:12:33,200 --> 00:12:34,260

294
00:12:34,260 --> 00:12:37,090
És ki is nyomtathatja a legfontosabb
hogy megbizonyosodjon arról, hogy ez helyes.

295
00:12:37,090 --> 00:12:38,380

296
00:12:38,380 --> 00:12:39,500
Érdekes.

297
00:12:39,500 --> 00:12:41,210
Nem elég, amit vártunk.

298
00:12:41,210 --> 00:12:44,810
Szóval, az egyik dolog, hogy észre
A GDB is, ez

299
00:12:44,810 --> 00:12:49,000
hogy nem, amíg ténylegesen hit
Ezután, hogy a vonal, amit csak látott

300
00:12:49,000 --> 00:12:50,720
ténylegesen végrehajtásra.

301
00:12:50,720 --> 00:12:53,870
Így, ebben az esetben a kulcs
nem rendeltek még.

302
00:12:53,870 --> 00:12:57,050
Szóval, kulcs némi szemét érték
hogy látod alul.

303
00:12:57,050 --> 00:13:03,680
Negatív $ 120-- --It egymilliárd
és valami furcsa dolgokat?

304
00:13:03,680 --> 00:13:05,340
Ez nem a kulcs, hogy mi várható.

305
00:13:05,340 --> 00:13:10,720
De ha megüt a Tovább gombra, majd
próbálja Print gomb, ez három.

306
00:13:10,720 --> 00:13:11,710
>> Mindenki látja, hogy?

307
00:13:11,710 --> 00:13:13,780
Tehát, ha kap valamit
hogy te, mint várni.

308
00:13:13,780 --> 00:13:15,540
Ez teljesen
rossz, és én nem tudom

309
00:13:15,540 --> 00:13:20,150
hogy ez fog történni, mert minden, amit akarok
tennie, hogy rendelni egy számot, egy változó,

310
00:13:20,150 --> 00:13:22,900
próbáld ütő Ezután próbálja nyomtatás
újra, és nézd meg, hogy működik.

311
00:13:22,900 --> 00:13:27,830
Mert ez csak akkor fog végrehajtani, és
valójában rendelni valami után

312
00:13:27,830 --> 00:13:29,340
megüt a Tovább gombra.

313
00:13:29,340 --> 00:13:30,336
Értelme mindenki?

314
00:13:30,336 --> 00:13:30,836
Uh huh?

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Ha a véletlen
szám mit jelent?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: Ez csak véletlen.

317
00:13:34,790 --> 00:13:35,710
Ez csak szemét.

318
00:13:35,710 --> 00:13:38,320
Ez csak valami, hogy a
számítógép véletlenszerűen rendelni.

319
00:13:38,320 --> 00:13:39,721

320
00:13:39,721 --> 00:13:40,220
Cool.

321
00:13:40,220 --> 00:13:45,760
Szóval, most már mozoghat, és így
most itt van ez a sima szöveg getString.

322
00:13:45,760 --> 00:13:48,600
Szóval, hadd vezessen mi
fog történni, amikor elérünk Next itt.

323
00:13:48,600 --> 00:13:51,320
A GDB fajta eltűnik, ugye?

324
00:13:51,320 --> 00:13:55,720
Ennek oka, hogy getString
most végrehajtó, ugye?

325
00:13:55,720 --> 00:14:01,460
Tehát, amikor láttuk, egyszerű szöveges értéke
GetString, nyitott parens és parens,

326
00:14:01,460 --> 00:14:04,380
és elérünk Next, amely
ténylegesen elvégzett most.

327
00:14:04,380 --> 00:14:06,580
Szóval, ez vár
minket bemenet valamit.

328
00:14:06,580 --> 00:14:13,560
>> Szóval, fogunk bemeneti élelmiszer, amely
mi ez hiányában ahogy mondtam

329
00:14:13,560 --> 00:14:18,020
és hogy csak azt mondja, hogy ez az
kész végrehajtó, hogy a zárt

330
00:14:18,020 --> 00:14:19,980
konzol azt jelenti, hogy
kilépő ki, hogy a hurok.

331
00:14:19,980 --> 00:14:21,170

332
00:14:21,170 --> 00:14:25,420
Szóval, mi is megüt gombra, és most, ahogy vagyok
Biztos, hogy minden ismerős Caesar,

333
00:14:25,420 --> 00:14:27,260
ez az, amit ez a vonal fog tenni.

334
00:14:27,260 --> 00:14:32,030
Ez Internethez I értéke 0, N =
Strlen, sima szöveg, majd a

335
00:14:32,030 --> 00:14:33,960
Én kevesebb, mint n, én, plusz, plusz.

336
00:14:33,960 --> 00:14:35,210
Mi ez a hurok fog csinálni?

337
00:14:35,210 --> 00:14:37,900

338
00:14:37,900 --> 00:14:39,160
Nyissa meg az üzenetet.

339
00:14:39,160 --> 00:14:39,770
Cool.

340
00:14:39,770 --> 00:14:41,330
Szóval, kezdjük csinálja.

341
00:14:41,330 --> 00:14:47,210
>> Tehát, amennyiben ez a feltétel
egyezik, a mi első?

342
00:14:47,210 --> 00:14:52,250
Ha ez a B, akkor az egyszerű szöveges I. Mi
kaphat információt a helyiek.

343
00:14:52,250 --> 00:14:53,610

344
00:14:53,610 --> 00:14:57,970
Így, én nulla, és ha nem hat, amely
várunk, és a legfontosabb az a három.

345
00:14:57,970 --> 00:14:59,227
Minden, ami van értelme, igaz?

346
00:14:59,227 --> 00:15:01,310
Ezek a számok mind
pontosan mit kell lenniük.

347
00:15:01,310 --> 00:15:02,590

348
00:15:02,590 --> 00:15:03,870
Szóval, hum?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Van
véletlen számok az enyém.

350
00:15:05,620 --> 00:15:09,156

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: Nos, azt check-- --we
lehet beszélgetni, hogy a második.

352
00:15:12,030 --> 00:15:14,110

353
00:15:14,110 --> 00:15:15,750
De legyen szerzés ez.

354
00:15:15,750 --> 00:15:17,700

355
00:15:17,700 --> 00:15:20,130
Tehát, ha van egy főváros
B az első,

356
00:15:20,130 --> 00:15:22,080
ezt a feltételt kell elkapni, igaz?

357
00:15:22,080 --> 00:15:27,120
Tehát, ha megüt Ezután látjuk
hogy ez valóban végrehajtja ha.

358
00:15:27,120 --> 00:15:29,220
Mert ha a következő
mellett a kódot,

359
00:15:29,220 --> 00:15:33,460
ezt a sort itt, ahol az egyszerű szöveges I
helyébe e számtani,

360
00:15:33,460 --> 00:15:35,720
csak ha végrehajtja a ha
feltétel helyes helyes?

361
00:15:35,720 --> 00:15:36,905

362
00:15:36,905 --> 00:15:40,240
>> GDB csak akkor fog mutatni
dolgok valójában végrehajtó.

363
00:15:40,240 --> 00:15:45,140
Tehát, ha ez a Ha a feltétel nem teljesül, akkor
Csak megy ugorjon a következő sorra.

364
00:15:45,140 --> 00:15:46,540
OK?

365
00:15:46,540 --> 00:15:48,510
Szóval, van, hogy.

366
00:15:48,510 --> 00:15:51,171
Ez azt jelenti, hogy konzol
zárt ki, hogy a hurok most.

367
00:15:51,171 --> 00:15:52,420
Szóval, ez lesz újrakezdeni.

368
00:15:52,420 --> 00:15:54,760

369
00:15:54,760 --> 00:15:56,280
Csak úgy.

370
00:15:56,280 --> 00:15:59,120
Szóval, hogy be tudjuk szerezni info
a mi helyiek itt,

371
00:15:59,120 --> 00:16:02,575
és azt látjuk, hogy az első
levél változott, ugye?

372
00:16:02,575 --> 00:16:05,150
Ez most az E, mint amilyennek lennie kellene.

373
00:16:05,150 --> 00:16:07,360
Szóval, mi is tovább.

374
00:16:07,360 --> 00:16:08,500
>> És mi van erre az ellenőrzésre.

375
00:16:08,500 --> 00:16:09,916
És ezt az ellenőrzést kell dolgoznia, igaz?

376
00:16:09,916 --> 00:16:12,570
Ez A. Meg kell változtatni
három betű előre.

377
00:16:12,570 --> 00:16:14,320

378
00:16:14,320 --> 00:16:16,530
De ha azt veszi észre, mi
kap valami más.

379
00:16:16,530 --> 00:16:17,580

380
00:16:17,580 --> 00:16:22,860
Tehát ebben az esetben itt, elkapta
, és így ezt a sort végre,

381
00:16:22,860 --> 00:16:28,620
amely a módosított B.
De ebben az esetben is,

382
00:16:28,620 --> 00:16:32,860
van, hogy csak kihagytam,
és elment a [? L Siff. ?]

383
00:16:32,860 --> 00:16:34,660
Tehát valami folyik ott.

384
00:16:34,660 --> 00:16:37,780
Ez azt mondja ki, hogy,
tudjuk, hogy meg kell fogni itt,

385
00:16:37,780 --> 00:16:39,200
de ez nem.

386
00:16:39,200 --> 00:16:42,210
Tud valaki, hogy mi a
probléma van a sorban?

387
00:16:42,210 --> 00:16:45,380

388
00:16:45,380 --> 00:16:46,969
Ez egy nagyon percenként dolog.

389
00:16:46,969 --> 00:16:48,510
És azt is nézd meg a kódot.

390
00:16:48,510 --> 00:16:49,980

391
00:16:49,980 --> 00:16:54,940
Ez is line-- felejtsd el, amit vonal is
A there-- de a [hallható].

392
00:16:54,940 --> 00:16:55,480
Igen?

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: ez a több, mint
oldalon, ha elolvassa azt a könyvet.

394
00:16:58,639 --> 00:16:59,430
SPEAKER 1: Pontosan.

395
00:16:59,430 --> 00:17:02,620
Szóval, a debugger nem tudta megmondani
te, de a debugger

396
00:17:02,620 --> 00:17:05,880
lehetne még le, hogy a vonal
amelyről tudja, hogy nem működik.

397
00:17:05,880 --> 00:17:09,319
És néha, amikor különösen
később a félévben, amikor a

398
00:17:09,319 --> 00:17:12,910
van dolgunk, a száz, a
száz pár sornyi kódot, és

399
00:17:12,910 --> 00:17:16,190
Nem tudom, hol van ennek hiányában,
ez egy nagyszerű módja annak, hogy csináld.

400
00:17:16,190 --> 00:17:17,900

401
00:17:17,900 --> 00:17:18,989
Szóval, mi megtaláltuk a hibát.

402
00:17:18,989 --> 00:17:21,530
Meg tudod oldani, hogy a fájlban,
és akkor lehet futni újra,

403
00:17:21,530 --> 00:17:23,029
és minden tökéletesen fog működni.

404
00:17:23,029 --> 00:17:24,970

405
00:17:24,970 --> 00:17:30,590
És a legnagyobb dolog
ez úgy tűnik, mint, OK.

406
00:17:30,590 --> 00:17:31,090
Igen.

407
00:17:31,090 --> 00:17:31,370
Cool.

408
00:17:31,370 --> 00:17:32,744
Azt tudta, hogy mit keres.

409
00:17:32,744 --> 00:17:34,910
Szóval, tudta, mit kell tennie.

410
00:17:34,910 --> 00:17:39,021
>> GDB lehet szuper hasznos, mert
kinyomtathatja az összes ezeket a dolgokat, amit

411
00:17:39,021 --> 00:17:39,520
nem.

412
00:17:39,520 --> 00:17:41,160
Ez sokkal hasznosabb, mint a printf.

413
00:17:41,160 --> 00:17:43,440
Hányan használ
mint printf

414
00:17:43,440 --> 00:17:46,200
kitalálni, hogy hol a hiba volt, ugye?

415
00:17:46,200 --> 00:17:48,450
Szóval, ezzel, akkor nem
kell menj vissza,

416
00:17:48,450 --> 00:17:51,139
és mint kommentálja a
Printf, vagy megjegyzésbe,

417
00:17:51,139 --> 00:17:52,930
és kitalálni, mit
kell nyomtatni.

418
00:17:52,930 --> 00:17:55,670
Ez valójában csak lehetővé teszi, hogy
menj végig, nyomtassa ki a dolgok

419
00:17:55,670 --> 00:18:00,000
ahogy mész át, így, akkor
megfigyelni, hogyan változik a valós idejű,

420
00:18:00,000 --> 00:18:02,190
mint a program fut.

421
00:18:02,190 --> 00:18:04,390
>> És ez nem fog egy kicsit
kicsit megszokni.

422
00:18:04,390 --> 00:18:07,850
Én nagyon ajánlom csak ilyen
Az, hogy egy kicsit csalódott vele

423
00:18:07,850 --> 00:18:08,930
jobb most.

424
00:18:08,930 --> 00:18:13,450
Ha kiad egy óra alatt a
a jövő héten a tanulás, hogyan kell használni GDB,

425
00:18:13,450 --> 00:18:16,140
akkor mentse magát
annyi időt később.

426
00:18:16,140 --> 00:18:18,750
És szó szerint. Elmondjuk
ezt az ember minden évben,

427
00:18:18,750 --> 00:18:23,890
és emlékszem, mikor vettem a
osztály, olyan volt, mint, én minden rendben lesz.

428
00:18:23,890 --> 00:18:24,700
Nem.

429
00:18:24,700 --> 00:18:27,030
Pset 6 jött, és én
mint, fogok tanulni

430
00:18:27,030 --> 00:18:29,500
hogyan kell használni GDB mert én nem
tudja, mi folyik itt.

431
00:18:29,500 --> 00:18:32,940
>> Tehát, ha rászánja az időt, így
használja a kisebb programok

432
00:18:32,940 --> 00:18:35,697
hogy te lesz
dolgozik, mint a munka

433
00:18:35,697 --> 00:18:37,530
keresztül valami hasonló
Visionare, mint ez.

434
00:18:37,530 --> 00:18:38,800

435
00:18:38,800 --> 00:18:42,850
Vagy ha azt szeretnénk, extra gyakorlat, biztos vagyok benne,
Tudtam felér hibás programok

436
00:18:42,850 --> 00:18:45,300
az Ön számára, hogy hibakeresést, ha szeretne.

437
00:18:45,300 --> 00:18:49,300
>> De ha egy kis időt, hogy
megszoktam, csak a játék körül vele,

438
00:18:49,300 --> 00:18:50,550
ez tényleg megéri.

439
00:18:50,550 --> 00:18:52,591
És ez valóban az egyik
azokat a dolgokat, amit csak

440
00:18:52,591 --> 00:18:57,340
meg kell próbálni, és a kezed piszkos
be, mielőtt igazán értem.

441
00:18:57,340 --> 00:19:02,090
Én tényleg csak megértette egyszer
Kellett túlbonyolított vele,

442
00:19:02,090 --> 00:19:08,170
és ez sokkal szebb, ha egy ötlet
hogyan debug inkább előbb, mint utóbb.

443
00:19:08,170 --> 00:19:08,850
OK.

444
00:19:08,850 --> 00:19:09,625
Cool.

445
00:19:09,625 --> 00:19:12,960
Tudom, hogy ez olyan, mint
egy gyorstalpaló GDB,

446
00:19:12,960 --> 00:19:16,400
és én biztosan dolgozni kezd
ezeket nézni nagyobb legközelebb.

447
00:19:16,400 --> 00:19:17,590

448
00:19:17,590 --> 00:19:18,280
Cool.

449
00:19:18,280 --> 00:19:20,390
>> Tehát, ha megyünk vissza a PowerPoint.

450
00:19:20,390 --> 00:19:27,194

451
00:19:27,194 --> 00:19:28,110
Fog ez működni?

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
AWH.

454
00:19:30,210 --> 00:19:31,101
Igen.

455
00:19:31,101 --> 00:19:31,600
OK.

456
00:19:31,600 --> 00:19:35,480
Tehát, ha valaha is szüksége a
azok megint ott van a listán.

457
00:19:35,480 --> 00:19:37,160

458
00:19:37,160 --> 00:19:40,830
Szóval bináris keresés, amely mindenki
emlékszik a nagy látvány Dávid

459
00:19:40,830 --> 00:19:42,259
rippelés telefonkönyvek felét.

460
00:19:42,259 --> 00:19:44,050
Én nem igazán kap a
telefonkönyv többé,

461
00:19:44,050 --> 00:19:46,530
mert mint ahol ugye
kap telefonkönyvek manapság?

462
00:19:46,530 --> 00:19:48,220
Én tényleg nem tudom.

463
00:19:48,220 --> 00:19:49,840

464
00:19:49,840 --> 00:19:50,590
A bináris keresés.

465
00:19:50,590 --> 00:19:52,464
Tudja valaki emlékszik
hogyan bináris keresés működik?

466
00:19:52,464 --> 00:19:54,380

467
00:19:54,380 --> 00:19:55,220
Bárki, aki egyáltalán?

468
00:19:55,220 --> 00:19:56,325
Igen?

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Tudod, amikor
megnézi, amelynek a felét

470
00:19:58,283 --> 00:20:01,146
az lenne, hogy alapul,
és megszabadulni a másik felét.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1. Pontosan.

472
00:20:01,896 --> 00:20:06,290
Szóval, bináris keresés, ez a fajta a--
--we hívjuk, hogy oszd meg és uralkodj.

473
00:20:06,290 --> 00:20:09,170
Szóval, mit fogsz csinálni a
akkor meg a közepén,

474
00:20:09,170 --> 00:20:11,990
és látni fogod, ha az megfelel
amit keres.

475
00:20:11,990 --> 00:20:15,420
És ha nem, akkor próbálja
kitalálni, ez fog hagyni

476
00:20:15,420 --> 00:20:16,450
fele vagy a jobb felét.

477
00:20:16,450 --> 00:20:19,325
Szóval, ez lehet, ha keres
valamit, ami betűrendbe,

478
00:20:19,325 --> 00:20:20,720
látod, oh.

479
00:20:20,720 --> 00:20:22,750
Vajon Allison elé M?

480
00:20:22,750 --> 00:20:23,250
Igen.

481
00:20:23,250 --> 00:20:25,030
Szóval, megyünk
nézd meg az első félidőben.

482
00:20:25,030 --> 00:20:26,450
>> Vagy lehet, mint a számok.

483
00:20:26,450 --> 00:20:28,830
Bármi, amit tud
összehasonlítani, lehet válogatni.

484
00:20:28,830 --> 00:20:29,920

485
00:20:29,920 --> 00:20:31,260
Használhatja bináris keresés.

486
00:20:31,260 --> 00:20:32,340

487
00:20:32,340 --> 00:20:37,455
Szóval, valaki emlékszik erre
grafikon, vagy mi ez?

488
00:20:37,455 --> 00:20:39,520
Ez Aszimptotikus komplexitás.

489
00:20:39,520 --> 00:20:42,830
Szóval, ez a grafikon csak
leírja, hogy mennyi ideig

490
00:20:42,830 --> 00:20:46,230
úgy, hogy megoldja a problémát
növeli a néhány dolog

491
00:20:46,230 --> 00:20:47,090
hogy használ.

492
00:20:47,090 --> 00:20:51,260
>> Szóval, van N, amely a lineáris idő.

493
00:20:51,260 --> 00:20:54,560
Ha N több mint két, ami valamivel
jobb, még mindig nő szuper gyors.

494
00:20:54,560 --> 00:20:58,360
És akkor már be, ami
amit mi úgy bináris keresés.

495
00:20:58,360 --> 00:21:03,630
Ha azt vesszük észre, mivel a probléma
lesz sokkal és sokkal nagyobb,

496
00:21:03,630 --> 00:21:06,600
a szükséges időt, hogy megoldja azt
nem igazán növeli, hogy sok.

497
00:21:06,600 --> 00:21:09,010
Ez olyan, mint hasonló
itt az elején.

498
00:21:09,010 --> 00:21:10,060
Te, mint, OK.

499
00:21:10,060 --> 00:21:13,000
Bármi, itt nem igazán
számít, melyik az általunk használt,

500
00:21:13,000 --> 00:21:16,220
de akkor kap arra, hogy egy millió, milliárd.

501
00:21:16,220 --> 00:21:20,010
Megpróbálod megtalálni some-- --you're
megpróbálja megtalálni a tűt a szénakazalban.

502
00:21:20,010 --> 00:21:21,550
>> Azt hiszem, szeretné ezt a problémát.

503
00:21:21,550 --> 00:21:25,850
Azt akarjuk, hogy ez a komplexitás, nem
lineáris, mert minden, amit

504
00:21:25,850 --> 00:21:30,049
tudni, hogy a kereső segítségével lesz
minden egyes tű, dolog széna,

505
00:21:30,049 --> 00:21:31,340
próbál keresni a tűt.

506
00:21:31,340 --> 00:21:34,730
És ez nem túl szórakoztató véleményem.

507
00:21:34,730 --> 00:21:35,500
Szeretem gyorsan.

508
00:21:35,500 --> 00:21:36,620
Szeretem hatékony.

509
00:21:36,620 --> 00:21:40,450
És szorgalmas diákok akkor
fiúk, tudod a munka okosabb,

510
00:21:40,450 --> 00:21:43,010
Nem nehezebb típusú dolog, hogy vagy
lehet, hogy ezeket az algoritmusokat.

511
00:21:43,010 --> 00:21:45,110

512
00:21:45,110 --> 00:21:47,910
>> Szóval, megyünk sétálni
keresztül csak egy gyors példa.

513
00:21:47,910 --> 00:21:51,090
Szerintem nektek kellett volna
a kezét bináris keresés,

514
00:21:51,090 --> 00:21:54,352
de ha valaki egy kicsit
fuzzy, szeretnék megerősíteni azt,

515
00:21:54,352 --> 00:21:56,310
megyünk csak megy
egy példán keresztül itt.

516
00:21:56,310 --> 00:21:59,490
Szóval, keresünk, ha
A tömb hét.

517
00:21:59,490 --> 00:22:00,540

518
00:22:00,540 --> 00:22:06,010
>> Szóval, az első dolog, amit tehetünk,
nézd középen, ugye?

519
00:22:06,010 --> 00:22:09,340
És azt is meg leszel kódolás
Binary Keresés csak a második.

520
00:22:09,340 --> 00:22:11,310
Szóval, lesz móka.

521
00:22:11,310 --> 00:22:13,710
Így néz ki a
középső kis tömbök 3.

522
00:22:13,710 --> 00:22:15,501
Van 3 egyenlő 7?

523
00:22:15,501 --> 00:22:16,000
Hát nem.

524
00:22:16,000 --> 00:22:18,670

525
00:22:18,670 --> 00:22:19,550
Ez hat.

526
00:22:19,550 --> 00:22:21,480
Szóval, ez kevesebb, mint
vagy nagyobb, mint hét?

527
00:22:21,480 --> 00:22:23,080

528
00:22:23,080 --> 00:22:23,960
Kevesebb, mint.

529
00:22:23,960 --> 00:22:24,570
Igen.

530
00:22:24,570 --> 00:22:25,170
Szép munka fiúk.

531
00:22:25,170 --> 00:22:25,569

532
00:22:25,569 --> 00:22:27,360
Úgy érzem, olyan, mint én kellene
Van cukorka, mert

533
00:22:27,360 --> 00:22:29,460
szeretné, hogy dobja ki a yard.

534
00:22:29,460 --> 00:22:30,270
Ez az, amit én fogok csinálni a jövő héten.

535
00:22:30,270 --> 00:22:31,436
Ez fogja srácok éles.

536
00:22:31,436 --> 00:22:32,560

537
00:22:32,560 --> 00:22:34,690
>> Szóval, dobja el, hogy
első felében, ugye?

538
00:22:34,690 --> 00:22:35,670
alatti volt.

539
00:22:35,670 --> 00:22:39,325
tudjuk, hogy mindent
az, hogy a bal oldali

540
00:22:39,325 --> 00:22:41,700
lesz kisebb, mint amit
mi valójában keresnek.

541
00:22:41,700 --> 00:22:43,491
Szóval, nem kell, hogy
figyelni rá.

542
00:22:43,491 --> 00:22:45,120
Csak felejtsd el.

543
00:22:45,120 --> 00:22:48,720
Szóval, most nézzük meg a jobb oldalon,
és nézzük meg középen ott,

544
00:22:48,720 --> 00:22:50,510
és most már kilenc.

545
00:22:50,510 --> 00:22:55,510
Szóval, 9. ez-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Nagyobb, mint amit mi
keresnek, igaz?

547
00:22:57,470 --> 00:22:59,860
Szóval, megyünk dobni
el minden jobbra.

548
00:22:59,860 --> 00:23:00,970

549
00:23:00,970 --> 00:23:01,940
Mint azt.

550
00:23:01,940 --> 00:23:03,700
Most minden mi maradt egy.

551
00:23:03,700 --> 00:23:07,760
Így ellenőrizni, ez egy milyen
keresünk? az.

552
00:23:07,760 --> 00:23:08,970
Azt találtuk, amit akartunk.

553
00:23:08,970 --> 00:23:10,440

554
00:23:10,440 --> 00:23:11,690
Szóval kész.

555
00:23:11,690 --> 00:23:12,550
Keresés a bilineáris.

556
00:23:12,550 --> 00:23:15,740
>> És ha azt veszi észre, mi
pedig hét bemenetek ott.

557
00:23:15,740 --> 00:23:24,320
Csak elvitt minket mint háromszor,
de ha csinálsz, mint egy milliárd

558
00:23:24,320 --> 00:23:28,190
tudjátok, hogy hány lépést is lenne
hozni, ha volt négymilliárd dolgokat?

559
00:23:28,190 --> 00:23:29,940

560
00:23:29,940 --> 00:23:30,455
Minden találgatások?

561
00:23:30,455 --> 00:23:32,286

562
00:23:32,286 --> 00:23:33,960
Ez a 32.

563
00:23:33,960 --> 00:23:37,110
32 lépés, hogy talál valamit
egy négymilliárd

564
00:23:37,110 --> 00:23:39,650
elem tömb miatt hatáskörének kettő.

565
00:23:39,650 --> 00:23:43,550
Tehát kettő 32, hogy négymilliárd.

566
00:23:43,550 --> 00:23:50,430
>> Szóval, elég őrült, hogy hogyan, hogy még mindig belül
mint egy viszonylag kis számú lépést

567
00:23:50,430 --> 00:23:52,650
találni valamit
négymilliárd elemekkel.

568
00:23:52,650 --> 00:23:55,730
Szóval ez a megjegyzés, vagyunk
majd ezt a kódot

569
00:23:55,730 --> 00:23:58,950
így ti is valójában
milyen látni, hogy ez hogyan működik.

570
00:23:58,950 --> 00:24:01,520
Rendben, így ti is kódot.

571
00:24:01,520 --> 00:24:04,100
Én hagyom, hogy a srácok
beszélni egy kicsit.

572
00:24:04,100 --> 00:24:07,970
Ismerd meg az embereket körülötted, ami
amit valaki akart az utolsó szakasz.

573
00:24:07,970 --> 00:24:10,280
>> Így megismerik az emberek körülötted.

574
00:24:10,280 --> 00:24:11,305
Beszéljen egy kicsit.

575
00:24:11,305 --> 00:24:12,580

576
00:24:12,580 --> 00:24:15,730
És minden, amit akarok tőled
srácok most csak

577
00:24:15,730 --> 00:24:17,575
megpróbál létrehozni egy vázlatot pszeudokódja.

578
00:24:17,575 --> 00:24:18,075
OK?

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
Hú.

581
00:24:21,325 --> 00:24:23,320

582
00:24:23,320 --> 00:24:29,520
Csak azt szeretném tőletek van te
csak úgy, hogy töltse ki ezt, miközben az esetben.

583
00:24:29,520 --> 00:24:32,170
Szóval már meg ezeket a felső
és alsó határ, amely

584
00:24:32,170 --> 00:24:35,250
képviseli a kezdet
és vége a tömb.

585
00:24:35,250 --> 00:24:40,440
És fogsz ténylegesen
hurkolt és kitalálni

586
00:24:40,440 --> 00:24:42,470
mit csinálunk ebben a while ciklus.

587
00:24:42,470 --> 00:24:45,810
>> Tehát, ha a szám out-- van
egy tipp there-- mik az esetek

588
00:24:45,810 --> 00:24:46,640
hogy mi van itt?

589
00:24:46,640 --> 00:24:48,100

590
00:24:48,100 --> 00:24:51,560
Tehát, ha azt szeretnénk, hogy kitaláljuk, a
esetben, akkor azokat pszeudokódja

591
00:24:51,560 --> 00:24:53,350
és akkor majd tényleg kódot őket.

592
00:24:53,350 --> 00:24:55,330
És ez lesz, én
gondolom, remélhetőleg ez lesz

593
00:24:55,330 --> 00:24:56,788
egy kicsit könnyebb, mint gondolnád.

594
00:24:56,788 --> 00:24:57,554

595
00:24:57,554 --> 00:25:00,220
Mert ez nem olyan sok kódot,
valójában, ami nagyon klassz.

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> Mm-hm?

598
00:25:35,018 --> 00:25:35,893
>> Diák: [hallható]?

599
00:25:35,893 --> 00:25:36,984

600
00:25:36,984 --> 00:25:37,650
OKTATÓ: Igen.

601
00:25:37,650 --> 00:25:38,595
Volt valami
megtalálni a közepén.

602
00:25:38,595 --> 00:25:39,552
>> Diák: Így tudjuk használni azt.

603
00:25:39,552 --> 00:25:39,770
OK.

604
00:25:39,770 --> 00:25:40,603
>> OKTATÓ: Tökéletes.

605
00:25:40,603 --> 00:25:42,950
Szóval ez az első dolog, amit tennie kell.

606
00:25:42,950 --> 00:25:44,330
Így találja a közepén.

607
00:25:44,330 --> 00:25:45,415

608
00:25:45,415 --> 00:25:45,915
Nagy.

609
00:25:45,915 --> 00:25:47,770

610
00:25:47,770 --> 00:25:55,010
Szóval van egy ötletem, hogyan lehet
ténylegesen meg középen kódot?

611
00:25:55,010 --> 00:25:55,980
>> Diák: Igen.

612
00:25:55,980 --> 00:25:57,000
n több mint 2?

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
OKTATÓ: Tehát n több mint 2.

615
00:25:59,500 --> 00:26:05,170
Tehát az egyik dolog, hogy emlékezzen, hogy
A felső és alsó határ változik.

616
00:26:05,170 --> 00:26:08,110
Tartjuk a szűkítő rész
a tömb keresünk a.

617
00:26:08,110 --> 00:26:11,970
Tehát n több mint 2 csak akkor működik,
Az első dolog, amit tenni.

618
00:26:11,970 --> 00:26:17,810
Így vesz a felső és alsó venni,
hogyan lehet azt kapjuk, hogy középső elem?

619
00:26:17,810 --> 00:26:20,640
Mert azt akarjuk, hogy a középső
a felső és alsó, ugye?

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
Mm-hm?

622
00:26:22,494 --> 00:26:23,369
>> Diák: [hallható].

623
00:26:23,369 --> 00:26:26,170

624
00:26:26,170 --> 00:26:28,080
>> Oktató: Tehát némi közepén.

625
00:26:28,080 --> 00:26:32,730
És ez lesz a felső plusz alsó vége 2.

626
00:26:32,730 --> 00:26:34,740

627
00:26:34,740 --> 00:26:35,690
Félelmetes.

628
00:26:35,690 --> 00:26:36,570
Ott megyünk.

629
00:26:36,570 --> 00:26:37,280
Egy sorral lejjebb.

630
00:26:37,280 --> 00:26:38,560
Vagytok az utat.

631
00:26:38,560 --> 00:26:41,400
Most, hogy megvan a
középső, mit akarunk csinálni?

632
00:26:41,400 --> 00:26:45,050

633
00:26:45,050 --> 00:26:45,900
Csak általában.

634
00:26:45,900 --> 00:26:47,734
Nem kell kódolni azt.

635
00:26:47,734 --> 00:26:48,335
Igen.

636
00:26:48,335 --> 00:26:49,210
Diák: [hallható]?

637
00:26:49,210 --> 00:27:00,310

638
00:27:00,310 --> 00:27:10,310
Oktató: Tehát plusz azért, mert te
megtalálása átlagosan két

639
00:27:10,310 --> 00:27:10,810
őket.

640
00:27:10,810 --> 00:27:11,890

641
00:27:11,890 --> 00:27:17,370
Tehát, ha úgy gondolja, rájuk, mint kedves
fokozódni oldalról,

642
00:27:17,370 --> 00:27:21,640
gondolj bele, ahogy közeledünk
A középső, kívánt ilyesmi.

643
00:27:21,640 --> 00:27:27,150
Tehát, ha úgy döntesz, mindkét oldalán a
középső, és mi, mint az 5. és a 7..

644
00:27:27,150 --> 00:27:31,440
Ha hozzá őket együtt,
kap 12, akkor ossza 2, 6.

645
00:27:31,440 --> 00:27:33,726
>> Néha nehéz
miért, hogy működik,

646
00:27:33,726 --> 00:27:35,600
de ha a munka révén
Példaként néha,

647
00:27:35,600 --> 00:27:37,962
ez segíteni fog kitalálni, ha
meg kell plusz vagy mínusz.

648
00:27:37,962 --> 00:27:38,846
Igen.

649
00:27:38,846 --> 00:27:40,830
>> Diák: [hallható]
pontosan a közepén

650
00:27:40,830 --> 00:27:43,950
ha volt egy eset, amikor
van egy csomó kisebb számok

651
00:27:43,950 --> 00:27:45,860
és mint egy nagy szám?

652
00:27:45,860 --> 00:27:49,750
>> OKTATÓ: Szóval csak annyit kell
a középső a tömb.

653
00:27:49,750 --> 00:27:53,010
Tehát, ha volt egy csomó kis számok
majd egy igazán nagy szám

654
00:27:53,010 --> 00:27:54,799
a végén, nem számít.

655
00:27:54,799 --> 00:27:56,840
Csak az számít, hogy
ők válogatni, csak

656
00:27:56,840 --> 00:27:59,339
szeretné nézni a közepén
A tömb azért, mert te még mindig

657
00:27:59,339 --> 00:28:00,700
szeletelés a problémát ketté.

658
00:28:00,700 --> 00:28:03,020

659
00:28:03,020 --> 00:28:03,680
Cool.

660
00:28:03,680 --> 00:28:06,430
Tehát most, hogy már a
középső, mit csinálunk a következő lépés?

661
00:28:06,430 --> 00:28:07,150
>> STUDENT: Hasonlítsa össze.

662
00:28:07,150 --> 00:28:08,150
Oktató: The össze.

663
00:28:08,150 --> 00:28:11,670
Így összehasonlítani középső value_wanted.

664
00:28:11,670 --> 00:28:14,300

665
00:28:14,300 --> 00:28:15,160
Cool.

666
00:28:15,160 --> 00:28:17,950
Így látod itt van
Ezt az értéket szeretnénk itt.

667
00:28:17,950 --> 00:28:22,012

668
00:28:22,012 --> 00:28:23,095
Ne feledje, ez egy tömb.

669
00:28:23,095 --> 00:28:24,100

670
00:28:24,100 --> 00:28:26,970
Tehát középső utal az index.

671
00:28:26,970 --> 00:28:29,785
Szóval akarok értékeinek közepén.

672
00:28:29,785 --> 00:28:32,380

673
00:28:32,380 --> 00:28:35,650
Ne felejtsd el, ha azt szeretné,
összehasonlítani, kettős egyenlők.

674
00:28:35,650 --> 00:28:38,250
Te egy egyenlő te
Csak megy újra ki kell jelölni,

675
00:28:38,250 --> 00:28:41,090
és akkor persze, hogy
lesz a kívánt értéket.

676
00:28:41,090 --> 00:28:42,300
Tehát nem tehetem.

677
00:28:42,300 --> 00:28:44,350
>> Így fogunk látni, ha
Az értékeket a középső

678
00:28:44,350 --> 00:28:46,460
egyenlő értéket akarunk.

679
00:28:46,460 --> 00:28:47,749

680
00:28:47,749 --> 00:28:48,790
Ne felejtsd el a fogszabályozó.

681
00:28:48,790 --> 00:28:50,520

682
00:28:50,520 --> 00:28:52,235
Dropbox elmúlnak.

683
00:28:52,235 --> 00:28:54,140

684
00:28:54,140 --> 00:28:56,200
Szóval mit tegyünk ebben az esetben?

685
00:28:56,200 --> 00:28:59,360
Ha ez az, amit akarunk visszatérni?

686
00:28:59,360 --> 00:29:01,510

687
00:29:01,510 --> 00:29:02,626
Azt akarod mondani.

688
00:29:02,626 --> 00:29:03,440
>> DIÁK: Print le.

689
00:29:03,440 --> 00:29:05,314
>> Oktató: Nos,
nem akar nyomtatni ki.

690
00:29:05,314 --> 00:29:08,220
Tehát ez egy bool itt, ezért
vissza akar térni igaz vagy hamis.

691
00:29:08,220 --> 00:29:12,280
Azt mondod, ez a szám
Egy [? RRA? ?] Tehát, ha van,

692
00:29:12,280 --> 00:29:13,788
mi csak vissza igaz.

693
00:29:13,788 --> 00:29:16,780

694
00:29:16,780 --> 00:29:17,760
Ha én is pontosan igaz.

695
00:29:17,760 --> 00:29:18,830

696
00:29:18,830 --> 00:29:20,805
>> Diák: Miért nem tér vissza nulla?

697
00:29:20,805 --> 00:29:22,930
Oktató: így lehet
vissza nulla, ha akarod.

698
00:29:22,930 --> 00:29:26,780
De ebben az esetben, mivel
a függvény a bool,

699
00:29:26,780 --> 00:29:28,962
vissza kell térnünk igaz vagy hamis.

700
00:29:28,962 --> 00:29:30,920
DIÁK: Ha
mondván: logikai kifejezés,

701
00:29:30,920 --> 00:29:33,450
lehet beállítani azt egyenlő hamis?

702
00:29:33,450 --> 00:29:39,860
Mint ha azt akarom mondani, hogy ha ez a feltétel
nem teljesül, mint a felső értéke hamis.

703
00:29:39,860 --> 00:29:42,332
Vajon megértjük, ha csak
fel hamis a másik oldalon?

704
00:29:42,332 --> 00:29:43,040
OKTATÓ: Igen.

705
00:29:43,040 --> 00:29:44,820
Tehát tulajdonképpen ha
valaha csinál valamit

706
00:29:44,820 --> 00:29:49,600
mint a felső vagy az alsó,
hogy vissza igaz vagy hamis

707
00:29:49,600 --> 00:29:53,850
és ez valóban rossz stílusban
mondjuk értéke eléri vagy valódi egyenlőségen

708
00:29:53,850 --> 00:29:54,840
egyenlő hamis.

709
00:29:54,840 --> 00:30:00,210
Azt akarod használni, hogy eredmény
mint magát a csekket.

710
00:30:00,210 --> 00:30:04,720

711
00:30:04,720 --> 00:30:05,860
Nem az, amit akartam.

712
00:30:05,860 --> 00:30:08,150

713
00:30:08,150 --> 00:30:09,240
Ez az, amit én akartam.

714
00:30:09,240 --> 00:30:13,205
Tehát abban az esetben, kérded
valami hasonló mentse ezt a c.

715
00:30:13,205 --> 00:30:16,320

716
00:30:16,320 --> 00:30:25,150
>> Tehát, ha van int main (void)
és valami ilyesmi.

717
00:30:25,150 --> 00:30:31,922
És van, ha a felső
Az egyes input és te

718
00:30:31,922 --> 00:30:33,630
kérdezi, ha meg tudod csinálni
valami ilyesmi?

719
00:30:33,630 --> 00:30:35,010

720
00:30:35,010 --> 00:30:35,679
Jobb?

721
00:30:35,679 --> 00:30:37,470
Diák: Megpróbáltam
csinálni [hallható].

722
00:30:37,470 --> 00:30:38,450
Mert ha it's--

723
00:30:38,450 --> 00:30:39,200
OKTATÓ: Így van.

724
00:30:39,200 --> 00:30:41,197
Tehát azt szeretnénk, hogy ez hamis, nem igaz?

725
00:30:41,197 --> 00:30:41,780
Diák: Igen.

726
00:30:41,780 --> 00:30:45,960
Oktató: Tehát ebben az esetben
akarjuk, hogy végre, ha ez nem igaz.

727
00:30:45,960 --> 00:30:50,510
Így a hűvös dolog, amit tennie van ez.

728
00:30:50,510 --> 00:30:52,900

729
00:30:52,900 --> 00:30:55,650
Úgy emlékszem, felkiáltás
pont tagadja a dolgokat?

730
00:30:55,650 --> 00:30:58,270
Azt mondja [hallható] azt sem.

731
00:30:58,270 --> 00:31:03,590
Tehát, ha megnézzük csak
ez a rész itt, jobb lenne, ha

732
00:31:03,590 --> 00:31:05,740
azt mondják, hogy értékeli a
hamis, ahogy jónak látja.

733
00:31:05,740 --> 00:31:06,790

734
00:31:06,790 --> 00:31:09,880
Nem hamis igaz, amely
ez azt jelenti, végre.

735
00:31:09,880 --> 00:31:11,037
Van ennek értelme?

736
00:31:11,037 --> 00:31:11,620
Diák: Igen.

737
00:31:11,620 --> 00:31:12,453
OKTATÓ: Félelmetes.

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
OK.

740
00:31:14,300 --> 00:31:16,330
Így lehet csak vissza
igaz ebben az esetben.

741
00:31:16,330 --> 00:31:20,357
Tehát most már két másik
esetek ebben az esetben.

742
00:31:20,357 --> 00:31:21,565
Melyek a két másik esetben?

743
00:31:21,565 --> 00:31:31,610

744
00:31:31,610 --> 00:31:32,900
Nézzük csak ezt így.

745
00:31:32,900 --> 00:31:40,660
Szóval kezdjük mással
ha a középső értékek

746
00:31:40,660 --> 00:31:43,230
kisebb, mint az érték akarunk.

747
00:31:43,230 --> 00:31:47,200

748
00:31:47,200 --> 00:31:52,020
Tehát mi az érték a középső kevésbé
mint az érték, amit keresünk.

749
00:31:52,020 --> 00:31:53,765

750
00:31:53,765 --> 00:31:56,720
>> Szóval, ami ugye kötött
hiszem, szeretné frissíteni?

751
00:31:56,720 --> 00:31:57,870

752
00:31:57,870 --> 00:31:58,780
Felső vagy alsó?

753
00:31:58,780 --> 00:32:01,440

754
00:32:01,440 --> 00:32:01,940
Felső?

755
00:32:01,940 --> 00:32:03,230

756
00:32:03,230 --> 00:32:06,470
Tehát melyik oldalon a tömb
fogunk vizsgálni?

757
00:32:06,470 --> 00:32:07,500
>> Diák: Az alsó.

758
00:32:07,500 --> 00:32:09,750
>> Oktató: Mi megyünk
hogy nézi a bal oldalon.

759
00:32:09,750 --> 00:32:11,120
Tehát, még ha csekély értéke kisebb.

760
00:32:11,120 --> 00:32:14,730
Így a középső érték itt
kevesebb, mint amit mi szeretnénk.

761
00:32:14,730 --> 00:32:17,202
Ezért szeretnénk, hogy a
jobb oldalán a tömbben.

762
00:32:17,202 --> 00:32:18,910
Így megyünk
frissítjük alsó korlátot.

763
00:32:18,910 --> 00:32:20,210

764
00:32:20,210 --> 00:32:23,020
Tehát mi a mi alacsonyabb hozzárendelését.

765
00:32:23,020 --> 00:32:25,221
És mit gondol az alacsonyabb legyen?

766
00:32:25,221 --> 00:32:26,304
Diák: A középső érték?

767
00:32:26,304 --> 00:32:27,446

768
00:32:27,446 --> 00:32:28,820
OKTATÓ: Tehát a középső value--

769
00:32:28,820 --> 00:32:30,136
Diák: Plusz 1.

770
00:32:30,136 --> 00:32:31,010
Oktató: --plus 1.

771
00:32:31,010 --> 00:32:32,300

772
00:32:32,300 --> 00:32:34,380
Tud valaki mondja meg, miért
van, hogy a plusz 1?

773
00:32:34,380 --> 00:32:35,730
>> Diák: [? Nem érték?]
inkább egyenlő vele.

774
00:32:35,730 --> 00:32:36,120
>> OKTATÓ: Így van.

775
00:32:36,120 --> 00:32:38,661
Mert már tudjuk, hogy
a középső érték nem egyenlő

776
00:32:38,661 --> 00:32:42,750
, és azt akarjuk, hogy kizárja azt
minden későbbi keresést.

777
00:32:42,750 --> 00:32:46,360
Ha elfelejti, hogy plusz 1, az
lesz, mint a hurok a végtelenségig.

778
00:32:46,360 --> 00:32:49,620
És akkor csak fogott egy
végtelen ciklus és akkor majd segfault

779
00:32:49,620 --> 00:32:50,370
és a dolgok rosszra fordulnak.

780
00:32:50,370 --> 00:32:54,780
Tehát, mindig győződjön meg arról, hogy te nem
beleértve az értéket, amit csak

781
00:32:54,780 --> 00:32:55,380
nézett.

782
00:32:55,380 --> 00:32:58,530
Tehát vigyázni, hogy a plusz 1.

783
00:32:58,530 --> 00:33:04,840
>> Tehát most van az utolsó állapot
amely mindig a biztonság kedvéért

784
00:33:04,840 --> 00:33:12,664
Itt ellenőrizheti, ha más érték
a középső érték nagyobb, mint a

785
00:33:12,664 --> 00:33:13,163
akarunk.

786
00:33:13,163 --> 00:33:16,260

787
00:33:16,260 --> 00:33:20,230
Ez azt jelenti, hogy azt akarjuk,
A bal felét.

788
00:33:20,230 --> 00:33:21,350

789
00:33:21,350 --> 00:33:23,260
Igen, melyik megyünk frissíteni?

790
00:33:23,260 --> 00:33:23,760
Felső.

791
00:33:23,760 --> 00:33:25,470

792
00:33:25,470 --> 00:33:26,970
És mi ez lesz egyenlő?

793
00:33:26,970 --> 00:33:31,630

794
00:33:31,630 --> 00:33:33,690
Közel mínusz 1, mert,
Természetesen szeretnénk

795
00:33:33,690 --> 00:33:38,370
hogy győződjön meg arról, hogy nem vagyunk
nézi, hogy a középső érték megint.

796
00:33:38,370 --> 00:33:41,830

797
00:33:41,830 --> 00:33:45,110
És akkor mi van ez.

798
00:33:45,110 --> 00:33:45,610
Ennyi.

799
00:33:45,610 --> 00:33:46,820
Ez minden bináris keresés.

800
00:33:46,820 --> 00:33:48,190
Ez nem olyan rossz, ugye?

801
00:33:48,190 --> 00:33:51,590
Ez olyan, mint a 10 soros
kód, fehér térben.

802
00:33:51,590 --> 00:33:57,510
Szóval nagyon erős, nagyon hasznos, akkor
legyen használja az egyik később psets.

803
00:33:57,510 --> 00:33:59,360
Lehet, hogy nem ez, hanem később.

804
00:33:59,360 --> 00:34:00,670
Így tanulni.

805
00:34:00,670 --> 00:34:01,510
Szerelem ez.

806
00:34:01,510 --> 00:34:02,980
Ez jól bánnak veled.

807
00:34:02,980 --> 00:34:05,370
Szóval nem akárki rendelkezik
kérdésre bináris keresés?

808
00:34:05,370 --> 00:34:06,196
Igen.

809
00:34:06,196 --> 00:34:09,840
>> Diák: Számít
hogy az n páros vagy páratlan?

810
00:34:09,840 --> 00:34:10,750
>> Oktató: Nem.

811
00:34:10,750 --> 00:34:18,150
Mert öntött, hogy a középső, mint
int, akkor csak azt csonkolni.

812
00:34:18,150 --> 00:34:21,600
Így marad az egész, és ez lesz
végül kereshetőség mindent.

813
00:34:21,600 --> 00:34:23,909
Szóval nem kell aggódni, hogy a.

814
00:34:23,909 --> 00:34:24,580
Mindenki jó?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Félelmetes.

817
00:34:26,850 --> 00:34:27,919
Cool.

818
00:34:27,919 --> 00:34:30,836
Szóval, srácok ezt.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Slideshow.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Tehát ahogy beszéltünk, én tudom,
David említett komplexitás runtimes.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Így a legjobb esetben ez csak
egy, mely az állandó idő.

825
00:34:50,340 --> 00:34:51,909
Tud valaki mondja meg, miért lehet?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Milyen típusú forgatókönyv jelentő?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> Diák: [hallható] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
OKTATÓ: Tehát a középső pedig a
első elemét, hogy mi jön, ugye?

833
00:35:03,830 --> 00:35:08,167
Így akár egy sor egy vagy
amit keresünk, csak

834
00:35:08,167 --> 00:35:09,750
történetesen smack dab közepén.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Szóval ez a legjobb eset.

837
00:35:13,380 --> 00:35:17,540
Ön kap a valós problémákra, valószínűleg nem
fog elérni [hallható], hogy gyakran.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Mi a helyzet a legrosszabb esetben?

840
00:35:19,750 --> 00:35:21,270
A legrosszabb esetben log n.

841
00:35:21,270 --> 00:35:25,360
És hogy köze van az egész
hatásköre két dolog, hogy én beszéltem.

842
00:35:25,360 --> 00:35:30,930
>> Így a legrosszabb esetben ez azt jelentené,
hogy mi volt, hogy vágja le a tömb

843
00:35:30,930 --> 00:35:33,270
amíg ez egy elem az egyik.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Így kellett vágja le a fél
ahányszor csak lehetséges lehetett.

846
00:35:38,930 --> 00:35:41,430
Ez miért van, mert log n
csak tartani elosztjuk kettővel.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Szóval feltevések dolgot
tudnia kell, ha valaha

849
00:35:45,830 --> 00:35:48,050
fogja használni a bináris keresés.

850
00:35:48,050 --> 00:35:50,680
Az elemeket kell válogatni.

851
00:35:50,680 --> 00:35:53,890
Ezeket nem kell válogatni, mert
hogy ez az egyetlen módja annak,

852
00:35:53,890 --> 00:35:57,060
lehet tudni, ha tudja
hogy dobja ki a felét.

853
00:35:57,060 --> 00:36:00,260
>> Ha már ez a zagyva táska
a számok és azt mondod,

854
00:36:00,260 --> 00:36:05,380
OK, megyek, hogy ellenőrizze a középső
és a szám keresem

855
00:36:05,380 --> 00:36:08,510
kevesebb, mint, hogy én csak megy
hogy önkényesen dobja ki az egyik felét.

856
00:36:08,510 --> 00:36:11,130
Azt nem tudom, hogy a
számok a másik felét.

857
00:36:11,130 --> 00:36:12,655
A listát meg kell válogatni.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Is, ez lehet
megy előre egy kicsit,

860
00:36:16,560 --> 00:36:18,360
de meg kell, hogy véletlen elérésű.

861
00:36:18,360 --> 00:36:21,940
Meg kell tudni, hogy csak
megy, hogy a középső elem.

862
00:36:21,940 --> 00:36:25,110
Ha van áthalad
keresztül valami

863
00:36:25,110 --> 00:36:28,630
vagy visz extra lépéseket
eljutni, hogy a középső elem,

864
00:36:28,630 --> 00:36:31,750
ez nem log n, mert már
te hozzá több munkát bele.

865
00:36:31,750 --> 00:36:34,800
És ez, hogy egy kis
több értelme van két hét,

866
00:36:34,800 --> 00:36:37,950
de én csak egyfajta akart előszó,
adni nektek arról, hogy mi az,

867
00:36:37,950 --> 00:36:38,999
hogy jöjjön.

868
00:36:38,999 --> 00:36:40,790
De ezek a két
fontos feltételezések

869
00:36:40,790 --> 00:36:44,804
hogy szükség van a bináris listát.

870
00:36:44,804 --> 00:36:45,720
Győződjön meg róla, hogy rendezve.

871
00:36:45,720 --> 00:36:47,920
Ez a nagy egy-egy
srácok most.

872
00:36:47,920 --> 00:36:52,170
És, hogy mi mehet be
a többi a mi fajta.

873
00:36:52,170 --> 00:36:56,444
Tehát négy sorts-- buborék,
beillesztés, kiválasztás, és merge.

874
00:36:56,444 --> 00:36:57,485
Ők mindenféle klassz.

875
00:36:57,485 --> 00:37:02,860
Ha úgy dönt, hogy a srácok CS 124,
megtudhatja mindenféle fajta.

876
00:37:02,860 --> 00:37:07,575
És ha egy XKCD rajongó, ott
egy nagyon jó képregény a következőről:

877
00:37:07,575 --> 00:37:11,530
mint valójában hatástalan fajta, amit
Javasoljuk fogsz nézni.

878
00:37:11,530 --> 00:37:16,170
Ezek közül az egyik, mint a pánik fajta, amely
mint, ó, nem, vissza véletlen tömb.

879
00:37:16,170 --> 00:37:16,991
Shutdown rendszer.

880
00:37:16,991 --> 00:37:17,490
Hagyjuk.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Tehát geeky humor mindig jó.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Tehát nem mindenki emlékszik kedves
hasonló csak egy általános képet

885
00:37:25,750 --> 00:37:27,810
hogy milyen fajta buborék működik.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Emlékszel?

888
00:37:32,155 --> 00:37:32,755
>> Diák: Igen.

889
00:37:32,755 --> 00:37:33,970
>> Oktató: Hajrá.

890
00:37:33,970 --> 00:37:38,980
>> DIÁK: Szóval megy keresztül, és
ha ez nagyobb, akkor a két csere.

891
00:37:38,980 --> 00:37:39,820
>> Oktató: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Pontosan.

893
00:37:40,564 --> 00:37:41,730
Szóval csak halad végig.

894
00:37:41,730 --> 00:37:43,050
Kivárunk két számot.

895
00:37:43,050 --> 00:37:46,510
Ha az egyik előtt nagyobb
mint az utána,

896
00:37:46,510 --> 00:37:50,230
csak cserélni őket, azért, hogy a
Ily módon az összes nagyobb számban

897
00:37:50,230 --> 00:37:54,990
buborék fel vége felé a lista
és a kisebb számok buborék le.

898
00:37:54,990 --> 00:37:59,355
>> Vajon mutatni nektek a hideg
hang hatás válogatás videó?

899
00:37:59,355 --> 00:38:00,480
Ez klassz.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Szóval mint Robert csak azt mondta, az algoritmus
hogy csak végig a listán,

902
00:38:05,200 --> 00:38:07,930
csere a szomszédos értékek
ha ők nem azért.

903
00:38:07,930 --> 00:38:10,975
És akkor csak folyamatos ismétlése
amíg meg nem tesznek swap.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Szóval nem rossz, ugye?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Szóval csak egy gyors példa itt.

908
00:38:16,319 --> 00:38:18,360
Tehát ez fog rendezni
őket növekvő sorrendben.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Így, amikor átmegyünk az első
idő, nézzük a nyolc

911
00:38:23,470 --> 00:38:26,880
és hat nyilvánvalóan nem
annak érdekében, hogy azt cserélni őket.

912
00:38:26,880 --> 00:38:27,985
>> Szóval nézd meg a következőt.

913
00:38:27,985 --> 00:38:29,430
Nyolc és négy nem azért.

914
00:38:29,430 --> 00:38:30,450
Cserélni őket.

915
00:38:30,450 --> 00:38:32,530
Aztán nyolc és kettő, cserélni őket.

916
00:38:32,530 --> 00:38:33,470
Ott megyünk.

917
00:38:33,470 --> 00:38:39,519
Így aztán az első menetben, akkor
tudja, hogy a legnagyobb számban

918
00:38:39,519 --> 00:38:41,810
lesz egészen
tetején, mert ez csak

919
00:38:41,810 --> 00:38:44,210
lesz folyamatosan
nagyobb, mint minden más

920
00:38:44,210 --> 00:38:46,810
és ez csak fog buborék
fel egészen a végéig ott.

921
00:38:46,810 --> 00:38:48,226
Van ennek értelme mindenki?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Cool.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Akkor nézzük a második menetben.

926
00:38:53,920 --> 00:38:54,980
Hat és négy kapcsoló.

927
00:38:54,980 --> 00:38:55,920
Hat és két kapcsoló.

928
00:38:55,920 --> 00:38:58,700
És most van egy pár dolog, hogy.

929
00:38:58,700 --> 00:39:02,240
Tehát minden elmúlik, hogy mi
hogy a mi teljes lista

930
00:39:02,240 --> 00:39:06,320
tudjuk, hogy ilyen sok a számok
a végén lesz rendezve.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Tehát mi egy harmadik lépés,
amely az egyik csere.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
És akkor a mi negyedik
át, már nulla helyekkel.

935
00:39:15,910 --> 00:39:18,570
És tudjuk, hogy a
tömb lett rendezve.

936
00:39:18,570 --> 00:39:20,900
>> És ez a nagy
dolog buborék sort.

937
00:39:20,900 --> 00:39:23,720
Tudjuk, hogy amikor
nulla csereügyletek, hogy

938
00:39:23,720 --> 00:39:26,497
azt jelenti, hogy minden
a teljes rend.

939
00:39:26,497 --> 00:39:27,580
Elég, hogy hogyan ellenőrizzük.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Így is lesz kódolni buborék
fajta, amely szintén nem olyan rossz.

942
00:39:36,480 --> 00:39:38,120
Ezek egyike sem olyan rossz.

943
00:39:38,120 --> 00:39:40,210
Tudom, hogy úgy tűnik, egy kicsit ijesztő.

944
00:39:40,210 --> 00:39:42,124
Tudom, hogy mikor vettem
az osztály, akkor is, ha én

945
00:39:42,124 --> 00:39:44,290
tanította az osztályt
Az első alkalommal tavaly,

946
00:39:44,290 --> 00:39:46,165
Én, mint, hogyan tudom ezt megtenni?

947
00:39:46,165 --> 00:39:48,540
Annak van értelme elméletben, de
hogyan ténylegesen ezt teszik?

948
00:39:48,540 --> 00:39:51,420
Éppen ezért én is szeretnék járni
a kód veletek itt.

949
00:39:51,420 --> 00:39:54,915
Szóval van egy pszeudokódja
A srácok ezúttal.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Tehát csak ezt tartsd szem előtt,
vagyunk arról, hogy átmeneti felett.

952
00:39:58,970 --> 00:40:04,210
Tehát néhány számláló
nyomon követi a mi swapok,

953
00:40:04,210 --> 00:40:08,370
mert meg kell győződjön meg róla,
hogy mi, hogy ellenőrizték.

954
00:40:08,370 --> 00:40:11,830
És mi navigálhat az egész tömb
ahogy mi most csináltam ezt a példát.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Ha az elem előtt nagyobb, mint
Az elem után itt tartunk,

957
00:40:17,325 --> 00:40:20,760
mi cserélni őket, és mi a növedék
számláló mert amint cserélni,

958
00:40:20,760 --> 00:40:23,850
azt akarja, hogy mi tudjuk, hogy a számláló.

959
00:40:23,850 --> 00:40:26,247
Bármilyen kérdése van?

960
00:40:26,247 --> 00:40:27,580
Valami vicces tűnik itt.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
DIÁK: Ön a számláló nullára
minden alkalommal, amikor megy át a hurok?

963
00:40:32,350 --> 00:40:34,339
Ne menj
vissza nullára minden alkalommal?

964
00:40:34,339 --> 00:40:35,505
Oktató: Nem feltétlenül.

965
00:40:35,505 --> 00:40:39,710
Tehát mi történik, mi megy itt keresztül.

966
00:40:39,710 --> 00:40:43,830
Tehát nem közben, emlékszem, ez a
végrehajtja egyszer hiba nélkül.

967
00:40:43,830 --> 00:40:46,480
Így fog beállítani a
számláló nulla,

968
00:40:46,480 --> 00:40:48,070
akkor ez meg fog halad végig.

969
00:40:48,070 --> 00:40:50,590
Ahogy lépked,
naprakésszé számláló.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Mivel frissíti számláló, ha kész,
ha ez elérte a végén a tömb,

972
00:40:56,900 --> 00:41:00,830
ha a lista még nem rendezett,
számláló frissítve lett.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Tehát akkor ellenőrzi a feltételt, és
azt mondja, OK, számláló nullánál nagyobb.

975
00:41:07,150 --> 00:41:09,290
Ha így van, újra meg újra.

976
00:41:09,290 --> 00:41:14,340
Azt akarod állítani úgy, hogy ha
megy át, számláló egyenlő nullával.

977
00:41:14,340 --> 00:41:18,240
Ha valaki átmegy a rendezett
tömb, semmi nem változik,

978
00:41:18,240 --> 00:41:21,355
ez nem sikerül, és
vissza a rendezett lista.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Van ennek értelme?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
DIÁK: Ez lehet, hogy egy kicsit később.

983
00:41:26,356 --> 00:41:27,147
OKTATÓ: OK.

984
00:41:27,147 --> 00:41:28,980
Ha bármi más
kérdés, hogy jön fel.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Igen.

987
00:41:30,680 --> 00:41:33,760
>> Diák: És mi lenne a funkciója
legyen átszivatásáho elemek?

988
00:41:33,760 --> 00:41:36,900
>> Oktató: Tehát valójában írni
hogy ha megyünk most.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Cool.

991
00:41:38,300 --> 00:41:42,155
Tehát, hogy a megjegyzés, Alison megy
visszaváltani a készülék.

992
00:41:42,155 --> 00:41:43,080
Ez lesz szórakoztató.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
És mi van a mi szép
buborék fajta dolog itt.

995
00:41:47,390 --> 00:41:50,800
Szóval már megtettem kerékpározás
a tömb.

996
00:41:50,800 --> 00:41:53,030
Megvan a swapok hogy
egyenlő nullával.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Ezért szeretnénk cserélni szomszédos
elemeket, ha ők elromlott.

999
00:41:58,440 --> 00:42:03,020
Tehát az első dolog, amit meg kell
nem is halad végig a tömbben.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Szóval, mit gondolsz mi lehet, hogy
halad végig a tömb?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Van meg és az i értéke 0-ra.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Azt akarjuk, én kevésbé
mint n mínusz 1-mínusz k.

1006
00:42:22,454 --> 00:42:23,870
És leírom, hogy a második.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Tehát ez egy olyan optimalizálási itt, ahol,
emlékszem, hogy azt mondta, miután minden elmúlik,

1009
00:42:32,830 --> 00:42:36,655
a tömb, amit
tudom, hogy ez bármi on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Így aztán egy menetben is
tudjuk, hogy ez rendezve.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Miután két menetben tudjuk
hogy mindez rendezve.

1014
00:42:50,060 --> 00:42:52,750
Három menetben is
tudom, hogy van rendezve.

1015
00:42:52,750 --> 00:42:55,620
Tehát ahogy én iterációjával
a tömb itt,

1016
00:42:55,620 --> 00:43:01,090
van ez így biztos, hogy csak menjen
keresztül mi tudjuk, hogy nem válogatott.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Ez csak egy optimalizálás.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Írhatsz azt naivan csak
iterációjával át mindent,

1021
00:43:08,210 --> 00:43:09,970
ez csak tovább tart.

1022
00:43:09,970 --> 00:43:12,470
Ezzel a négy hurok ez
csak egy szép optimalizálás

1023
00:43:12,470 --> 00:43:18,460
mert tudjuk, hogy miután minden teljes
ismétlés a tömb itt,

1024
00:43:18,460 --> 00:43:24,050
mint minden teljes hurok van, tudjuk,
hogy az egyik több ilyen elem

1025
00:43:24,050 --> 00:43:25,760
lesz rendezve a végén.

1026
00:43:25,760 --> 00:43:28,294
>> Tehát nem kell aggódni ilyen.

1027
00:43:28,294 --> 00:43:29,710
Van ennek értelme mindenki?

1028
00:43:29,710 --> 00:43:30,950
Ez jó kis trükk?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Így abban az esetben, ha
vagyunk iterációjával keresztül,

1031
00:43:37,270 --> 00:43:50,590
tudjuk, hogy szeretnénk, ha szeretné ellenőrizni
array n és n + 1 rendben vannak.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Tehát itt a pszeudokód.

1035
00:43:54,600 --> 00:43:57,540
Azt akarjuk, hogy ellenőrizze, ha tömb n
és az n + 1-rendben vannak.

1036
00:43:57,540 --> 00:43:59,520
Szóval, mi van ott?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Ez lesz valami feltételes.

1039
00:44:03,120 --> 00:44:04,220
Ez lesz, ha.

1040
00:44:04,220 --> 00:44:07,066
>> Diák: Ha a tömb n
kevesebb mint tömb n + 1.

1041
00:44:07,066 --> 00:44:07,816
Oktató: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Nos, kisebb vagy nagyobb, mint.

1044
00:44:10,699 --> 00:44:11,615
Diák: Nagyobb, mint.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Aztán szeretnénk cserélni őket.

1047
00:44:17,620 --> 00:44:18,570
Pontosan.

1048
00:44:18,570 --> 00:44:23,570
Így most bejutni, mi a
mechanizmust swapping őket?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Így mentünk át ezt röviden,
egyfajta swap függvény a múlt héten.

1051
00:44:28,137 --> 00:44:29,595
Tudja valaki emlékszik, hogyan működött?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Tehát nem csak hozzárendelését, ugye?

1054
00:44:34,950 --> 00:44:36,640
Mivel egyikük eltévedni.

1055
00:44:36,640 --> 00:44:41,696
Ha azt mondtuk, A egyenlő B, majd B
egyenlő az A, mind egy hirtelen mindkettő

1056
00:44:41,696 --> 00:44:43,150
csak egyenlő B.

1057
00:44:43,150 --> 00:44:45,720
>> Tehát mi kell tennie, hogy mi
Van egy átmeneti változó, ami

1058
00:44:45,720 --> 00:44:49,055
fog tartani, míg a miénk
mi vagyunk a folyamat csere.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Szóval mi van az, hogy mi lesz néhány int
temp egyenlő to-- hozzárendelheti

1061
00:44:56,464 --> 00:44:59,130
hogy melyik kívánt, csak
győződjön meg róla, hogy nyomon követheti it--

1062
00:44:59,130 --> 00:45:01,840
így ebben az esetben fogom
hozzárendelheti tömb n + 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Annak érdekében, hogy meg fog tartani bármilyen
érték ebben a második blokk

1065
00:45:07,674 --> 00:45:08,590
hogy keresünk.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> És akkor, amit tehetünk, mehetünk
előre, és újra sor n + 1,

1068
00:45:13,240 --> 00:45:14,990
mert tudjuk,
Van, hogy a tárolt értéket.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Ez is az egyik nagy
things-- Nem tudom, ha valakinek

1071
00:45:19,270 --> 00:45:23,780
volt kérdés, ahol, ha váltani két
sornyi kódot hirtelen működnek a dolgok.

1072
00:45:23,780 --> 00:45:25,880
Rend nagyon fontos a CS.

1073
00:45:25,880 --> 00:45:29,450
Ügyeljen arra, hogy rajz
dolgok, ha lehetséges

1074
00:45:29,450 --> 00:45:31,230
hogy mi történik valójában.

1075
00:45:31,230 --> 00:45:34,256
Tehát most megyünk
hozzárendelését tömb n + 1,

1076
00:45:34,256 --> 00:45:36,005
mert tudjuk,
Van, hogy a tárolt értéket.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> És mi lehet rendelni, hogy a tömb
n vagy ebben az esetben a tömb i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Túl sok a változó.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Így most már újraosztani array i
plusz 1 egyenlő, mi van a tömb i.

1084
00:46:01,500 --> 00:46:08,240
És most mehetünk vissza, és
rendelni tömb i mi?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Valaki?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> Diák: 10.

1089
00:46:14,010 --> 00:46:14,680
>> OKTATÓ: 10.

1090
00:46:14,680 --> 00:46:15,180
Pontosan.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
És egy utolsó dolog.

1093
00:46:18,640 --> 00:46:21,840
Ha már cserélték most,
mit kell csinálni?

1094
00:46:21,840 --> 00:46:23,740
Mi az az egy dolog
hogy fog mondani

1095
00:46:23,740 --> 00:46:27,542
ha valaha is megszünteti ezt a programot?

1096
00:46:27,542 --> 00:46:29,250
Mi azt mondja, hogy
egy rendezett lista?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Ha nem végez semmilyen csereügyletek, ugye?

1099
00:46:33,750 --> 00:46:36,900
Ha a swap ügyletek egyenlő
nulla végén e.

1100
00:46:36,900 --> 00:46:42,975
Így amikor végre a csere, hiszen
Csak nem itt, szeretnénk frissíteni swap.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
És tudom, hogy ott volt a
kérdés korábban arról te is

1103
00:46:47,210 --> 00:46:49,689
használjon nulla vagy egy helyett
igaz vagy hamis.

1104
00:46:49,689 --> 00:46:50,980
És ez az, amit ez csinál itt.

1105
00:46:50,980 --> 00:46:52,750
Tehát, ez azt mondja, ha nem swap.

1106
00:46:52,750 --> 00:47:01,310
Tehát, ha a swap ügyletek nulla, ami ez-- mindig
kap az igazságok és a falses összekeveredett.

1107
00:47:01,310 --> 00:47:03,960
Azt akarják, hogy értékelje
az igaz, és ez nem az.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Tehát, ha ez nulla, akkor az hamis.

1110
00:47:09,630 --> 00:47:12,560
Ha tagadja meg a
[? bumm?] lesz igaz.

1111
00:47:12,560 --> 00:47:13,975
Akkor ezt a sort végrehajtja.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Igazság és hamis és
nullák megőrülnek.

1114
00:47:17,370 --> 00:47:20,690
Csak ha lassan járni
rajta akkor van értelme.

1115
00:47:20,690 --> 00:47:23,320
De ez az, amit ez a kis
kis kód itt nem.

1116
00:47:23,320 --> 00:47:26,490
Tehát ez ellenőrzi, hogy
tettünk semmi swap.

1117
00:47:26,490 --> 00:47:30,054
Tehát, ha ez valami mellett
nulla, akkor lesz hamis

1118
00:47:30,054 --> 00:47:31,970
és az egész dolog
megy végre újra.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Cool?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> DIÁK: Mit csinál szünet?

1123
00:47:36,000 --> 00:47:38,990
>> OKTATÓ: szünet csak
tör téged a hurok.

1124
00:47:38,990 --> 00:47:41,570
Így ebben az esetben is lenne
csakúgy, mint a végén a program

1125
00:47:41,570 --> 00:47:43,828
és akkor csak
már a rendezett lista.

1126
00:47:43,828 --> 00:47:44,536
STUDENT: Csodálatos.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
Oktató: Sajnálom?

1129
00:47:49,010 --> 00:47:52,110
Diák: Mert mi korábban
használt írott 1 felett írott nulla

1130
00:47:52,110 --> 00:47:54,170
bemutatni, hogy ha
hogy működni fog-e vagy sem.

1131
00:47:54,170 --> 00:47:54,878
>> OKTATÓ: Igen.

1132
00:47:54,878 --> 00:47:56,410
Így vissza nulla vagy 1.

1133
00:47:56,410 --> 00:47:58,950
Ebben az esetben, mert nem vagyunk valójában
csinál semmit a funkciója,

1134
00:47:58,950 --> 00:48:00,150
mi csak szeretnénk azt megtörni.

1135
00:48:00,150 --> 00:48:02,680
Nem igazán érdekli.

1136
00:48:02,680 --> 00:48:06,960
A fék is jó, ha
ez használt kitörésre

1137
00:48:06,960 --> 00:48:10,710
A négy hurok és feltételeket, amelyek
ha nem akarjuk megtartani végrehajtó.

1138
00:48:10,710 --> 00:48:12,110
Csak viszi ki őket.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Ez egy kicsit árnyalatot dolog.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Úgy érzem, van
sok kézzel integetett,

1143
00:48:18,445 --> 00:48:19,740
mint megtudhatja ilyen hamar.

1144
00:48:19,740 --> 00:48:20,955
>> De fogsz tanulni ezt hamarosan.

1145
00:48:20,955 --> 00:48:21,500
Ígérem.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Tehát nem mindenki kap buborék sort?

1149
00:48:24,840 --> 00:48:25,550
Nem rossz.

1150
00:48:25,550 --> 00:48:31,910
Halad végig, csere dolgok egy
temp változó, és készen is van ott?

1151
00:48:31,910 --> 00:48:32,960
Cool.

1152
00:48:32,960 --> 00:48:34,080
Félelmetes.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Vissza a PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Bármilyen kérdése általában
Ezekről eddig?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Cool.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> Diák: [hallható] int main általában.

1162
00:48:45,279 --> 00:48:46,695
Van, hogy, hogy ez?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> OKTATÓ: Szóval mi csak keresünk
éppen az aktuális rendezési algoritmus.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Ha már belül
mint egy nagyobb program,

1167
00:48:56,350 --> 00:48:57,891
akkor van egy int main valahol.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Attól függően, hogy hol
ezt algoritmust,

1170
00:49:02,880 --> 00:49:05,860
ez határozza meg, mi a
által visszaadott azt.

1171
00:49:05,860 --> 00:49:09,960
De a mi esetünkben, mi szigorúan
megnézzük, hogyan működik ez valójában

1172
00:49:09,960 --> 00:49:11,300
halad végig egy tömböt.

1173
00:49:11,300 --> 00:49:12,570
Tehát ne aggódj emiatt.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Így beszéltünk legjobb esetben, és
legrosszabb forgatókönyv bináris keresés.

1176
00:49:19,830 --> 00:49:22,470
Ezért is fontos, hogy
hogy minden a mi fajta.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Szóval, mit gondolsz a legrosszabb
esetében runtime buborék sort?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Srácok, emlékszel?

1181
00:49:30,700 --> 00:49:31,784
>> DIÁK: N mínusz 1.

1182
00:49:31,784 --> 00:49:32,700
OKTATÓ: N mínusz 1.

1183
00:49:32,700 --> 00:49:35,070
Annak érdekében, hogy azt jelenti, hogy
n mínusz 1 összehasonlítást.

1184
00:49:35,070 --> 00:49:40,060
Tehát az egyik dolog, hogy észre is
hogy az első ismétlés,

1185
00:49:40,060 --> 00:49:43,360
megyünk keresztül, összehasonlítjuk
ezek two-- szóval ez 1.

1186
00:49:43,360 --> 00:49:46,685
Ez a két, három, négy.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Így aztán egy iteráció mi
Már négy összehasonlítást.

1189
00:49:55,050 --> 00:49:58,230
Amikor beszélek runtime és n.

1190
00:49:58,230 --> 00:50:04,680
N jelentése az összehasonlítások száma
függvényében, hogy hány elem

1191
00:50:04,680 --> 00:50:05,570
van.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Így megy át, van négy.

1194
00:50:08,860 --> 00:50:11,780
A következő alkalommal, amikor tudod, hogy mi nem
kell intézni.

1195
00:50:11,780 --> 00:50:15,140
Összevetjük a két,
E két, ez a két,

1196
00:50:15,140 --> 00:50:20,050
és ha nem volt, hogy optimalizálás
a négy hurok, hogy én írtam,

1197
00:50:20,050 --> 00:50:22,750
akkor lehet összehasonlítani az itt egyébként.

1198
00:50:22,750 --> 00:50:26,170
Szóval kellett volna
végigmenni a tömb

1199
00:50:26,170 --> 00:50:34,380
, és n összehasonlítást n
idő, mert minden alkalommal, amikor

1200
00:50:34,380 --> 00:50:36,670
fuss keresztül mi fajta egy dolog.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> És minden alkalommal, amikor fut át
a tömb teszünk n összehasonlítást.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Így a runtime az,
tulajdonképpen n négyzet, amely

1205
00:50:46,330 --> 00:50:48,400
sokkal rosszabb a mi
log végén, mert azt

1206
00:50:48,400 --> 00:50:51,965
azt jelenti, hogy ha volt négy
milliárd elemek, akkor

1207
00:50:51,965 --> 00:50:55,260
fog minket négymilliárd
négyzetes helyett 32.

1208
00:50:55,260 --> 00:51:01,240
Tehát nem a legjobb runtime,
de néhány dolgot,

1209
00:51:01,240 --> 00:51:04,610
tudod, ha belül
egy bizonyos tartományon elemek

1210
00:51:04,610 --> 00:51:06,540
buborék sort lehet jól használható.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Szóval most mi a legjobb esetben futásidejű?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
Diák: Zero?

1215
00:51:14,940 --> 00:51:16,420
Vagy 1?

1216
00:51:16,420 --> 00:51:18,140
>> OKTATÓ: Tehát 1 lenne
az egyik összehasonlítás.

1217
00:51:18,140 --> 00:51:19,114
Right.

1218
00:51:19,114 --> 00:51:20,002
>> DIÁK: N mínusz 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> Oktató: Szóval, igen.

1221
00:51:22,320 --> 00:51:22,990
Tehát n mínusz 1.

1222
00:51:22,990 --> 00:51:26,510
Amikor van egy koncepció, mint n
mínusz 1, hajlamosak vagyunk csak csepp le

1223
00:51:26,510 --> 00:51:31,680
és mi csak mondjuk n azért, mert van
hogy összehasonlítsák az egyes these-- minden pár.

1224
00:51:31,680 --> 00:51:36,470
Így lenne n mínusz 1, amelyhez
mi lenne, csak mondjuk kb n.

1225
00:51:36,470 --> 00:51:39,280
Amikor foglalkozó runtime,
minden a közelíti.

1226
00:51:39,280 --> 00:51:43,860
Mindaddig, amíg a kitevő
helyes, te nagyon jó.

1227
00:51:43,860 --> 00:51:45,700
>> Így is foglalkozni vele.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Úgy, hogy a legjobb esetben n, amely
azt jelenti, hogy a lista már rendezett,

1230
00:51:51,780 --> 00:51:54,320
és minden, amit tennie, hogy végigmenni
és ellenőrizze, hogy ez rendezett.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Cool.

1233
00:51:56,855 --> 00:51:57,355
Rendben van.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Szóval mint látod itt, mi
Csak még egy kis grafikon.

1236
00:52:01,920 --> 00:52:02,660
Így n négyzeten.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Fun.

1239
00:52:05,120 --> 00:52:09,730
Sokkal rosszabb, mint n, mint látjuk, és
sokkal, de sokkal rosszabb, mint a log 2n.

1240
00:52:09,730 --> 00:52:12,060
És akkor is kap a napló naplók.

1241
00:52:12,060 --> 00:52:18,020
És veszel 124, bejutni
mint log csillag, ami olyan, mint egy őrült.

1242
00:52:18,020 --> 00:52:20,172
Tehát, ha érdekel,
keresési napló csillag.

1243
00:52:20,172 --> 00:52:20,880
Ez a fajta szórakozás.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Így van ez a nagy táblázat.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Csak egy heads-up, ez a
Csodálatos, hogy a diagram

1248
00:52:28,720 --> 00:52:31,350
a középtávú mert
hosszú kérdezni ezeket elvékonyodik.

1249
00:52:31,350 --> 00:52:36,090
Tehát csak a heads-up, ezt a
félidős a szép puskát

1250
00:52:36,090 --> 00:52:36,616
ott.

1251
00:52:36,616 --> 00:52:37,990
Szóval csak nézett bubble sort.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Legrosszabb eset, n faragva, legjobb esetben, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
És megyünk, hogy nézd meg a többiek.

1256
00:52:44,950 --> 00:52:47,940
>> És mint látható, az egyetlen
az egyik, hogy valóban jól

1257
00:52:47,940 --> 00:52:50,910
a merge sort, amit kapsz, hogy miért.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Így fogunk menni a
következő here-- kiválasztás sort.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Tudja valaki emlékszik, hogyan
kiválasztás sort dolgozott?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Megy ez.

1264
00:53:05,700 --> 00:53:08,210
>> Diák: Alapvetően megy át
megrendelés és hozzon létre egy új listát.

1265
00:53:08,210 --> 00:53:11,001
És ahogy te olyan elemek
a, tedd őket a megfelelő helyre

1266
00:53:11,001 --> 00:53:11,750
Az új listában.

1267
00:53:11,750 --> 00:53:14,040
>> Oktató: Annak érdekében, hogy a hangok
inkább beillesztés sort.

1268
00:53:14,040 --> 00:53:15,040
De te nagyon közel van.

1269
00:53:15,040 --> 00:53:15,915
Nagyon hasonló.

1270
00:53:15,915 --> 00:53:17,440
Még én is őket néha összekeveredett.

1271
00:53:17,440 --> 00:53:18,981
Mielőtt ez a rész volt, mint én, várjon.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Szóval, mit akarsz
tennie kiválasztás sort,

1275
00:53:24,141 --> 00:53:25,890
ahogy lehet gondolni
róla, és az út

1276
00:53:25,890 --> 00:53:30,140
Azt, hogy biztos, hogy megpróbál, hogy nem kap
őket összekeverednek, ez megy át

1277
00:53:30,140 --> 00:53:33,280
és kiválasztja a
legkisebb számot és

1278
00:53:33,280 --> 00:53:36,070
teszi, hogy az elején a lista.

1279
00:53:36,070 --> 00:53:37,730
A swap azt, hogy az első helyen.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Ők valójában egy példa számomra.

1282
00:53:45,370 --> 00:53:46,540
Félelmetes.

1283
00:53:46,540 --> 00:53:50,130
Tehát csak egy módja annak, hogy gondolni it-- kiválasztás
sort, válassza ki a legkisebb érték.

1284
00:53:50,130 --> 00:53:51,940
És megyünk
fuss egy példán keresztül

1285
00:53:51,940 --> 00:53:55,320
Azt hiszem, hogy segíteni fog, mert
Azt hiszem, látvány mindig segít.

1286
00:53:55,320 --> 00:53:58,510
Tehát elindul valami
hogy teljesen nem válogatott.

1287
00:53:58,510 --> 00:54:00,730
Red lesz válogatás nélkül,
zöld lesz rendezve.

1288
00:54:00,730 --> 00:54:02,190
Ez minden értelme a második.

1289
00:54:02,190 --> 00:54:08,950
>> Így megy keresztül, és mi folyamatosan léptetjük
az elejétől a végéig.

1290
00:54:08,950 --> 00:54:12,320
És azt mondjuk, rendben van, 2
a legkisebb szám.

1291
00:54:12,320 --> 00:54:15,680
Szóval megy, hogy a 2. és megyünk
mozgatni, hogy az első a mi tömb

1292
00:54:15,680 --> 00:54:17,734
mert a
legkisebb szám van.

1293
00:54:17,734 --> 00:54:19,150
Szóval, ez az, amit ez csinál itt.

1294
00:54:19,150 --> 00:54:20,820
Ez csak fog cserélni a két.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Tehát most már a rendezve
rész és egy rendezetlen rész.

1297
00:54:25,450 --> 00:54:27,810
És mi a jó emlékezni
szelekciós sort

1298
00:54:27,810 --> 00:54:30,690
a mi csak adja
a nem válogatott rész.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> A rendezett rész hagyod egyedül.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> Diák: Hogyan tudja, mi a
a legkisebb, ha összevetjük azt

1303
00:54:38,452 --> 00:54:39,868
minden más értéket a tömbben.

1304
00:54:39,868 --> 00:54:41,250
Oktató: Ez nem összehasonlítani.

1305
00:54:41,250 --> 00:54:42,041
Szeretjük kihagytam.

1306
00:54:42,041 --> 00:54:43,850
Ez csak általános, átfogó.

1307
00:54:43,850 --> 00:54:44,831
Igen.

1308
00:54:44,831 --> 00:54:47,205
Amikor írunk a kódot vagyok
Biztosan lesz még elégedett.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
De tárolja az első
elem, mint a legkisebb.

1311
00:54:53,030 --> 00:54:56,110
Összehasonlítani és
azt mondják, OK, ez kisebb?

1312
00:54:56,110 --> 00:54:56,660
Igen.

1313
00:54:56,660 --> 00:54:57,460
Tartsd meg.

1314
00:54:57,460 --> 00:54:58,640
Itt van ez a kisebb?

1315
00:54:58,640 --> 00:54:59,660
Nem?

1316
00:54:59,660 --> 00:55:02,510
>> Ez a legkisebb,
újra ki kell jelölni, hogy az érték.

1317
00:55:02,510 --> 00:55:06,340
És akkor sokkal boldogabb
mikor megyünk át a kódot.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Így megy át, cseréljük, így aztán
nézzük ezt nem válogatott rész.

1320
00:55:13,970 --> 00:55:15,810
Szóval majd válassza ki a három.

1321
00:55:15,810 --> 00:55:18,890
Mi megy, hogy azt a
a végén a mi rendezett rész.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
És mi csak fog tartani csinál
hogy csinálja, és csinálja.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Szóval ez a mi fajta pszeudokódja itt.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Majd kódot fel itt egy másik.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
De csak valami járni
keresztül egy magas szinten.

1330
00:55:37,270 --> 00:55:40,275
Fogsz menni
i értéke 0 és n mínusz 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Ez egy másik optimalizálás.

1333
00:55:43,530 --> 00:55:45,020
Ne aggódj túl sokat róla.

1334
00:55:45,020 --> 00:55:46,620
Szóval mint mondtál.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Ahogy Jacob mondott, hogyan is
nyomon követni, hogy mi a minimum?

1337
00:55:54,406 --> 00:55:55,030
Honnan tudjuk?

1338
00:55:55,030 --> 00:55:57,060
Meg kell összehasonlítani
minden listánkon.

1339
00:55:57,060 --> 00:55:59,600
>> Tehát minimum értéke i.

1340
00:55:59,600 --> 00:56:03,870
Ez csak azt mondom, ebben az esetben
Az index a legkisebb érték.

1341
00:56:03,870 --> 00:56:07,660
Akkor ez lesz a halad végig
és megy a j értéke i + 1.

1342
00:56:07,660 --> 00:56:11,420
Így már tudjuk, hogy
ez az első elem.

1343
00:56:11,420 --> 00:56:13,240
Nem kell, hogy hasonlítsa össze magát.

1344
00:56:13,240 --> 00:56:16,970
Így kezd hasonlítsa össze a következő
amely ezért ez az i + 1-től n-

1345
00:56:16,970 --> 00:56:20,110
mínusz 1, ami a
végén a tömb ott.

1346
00:56:20,110 --> 00:56:25,090
És mi azt mondtuk, ha tömbbel
j értéke kisebb, mint a tömb perc,

1347
00:56:25,090 --> 00:56:29,200
akkor átrendelhet ahol
a minimum indexek.

1348
00:56:29,200 --> 00:56:37,470
>> És ha perc nem egyenlő, az i
oda, ahol voltunk vissza ide.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Tehát, mint amikor először tette ezt.

1351
00:56:41,790 --> 00:56:49,310
Ebben az esetben ez kezdődik
nulla, akkor a végén, hogy kettő.

1352
00:56:49,310 --> 00:56:53,010
Tehát min nem egyenlő i a végén.

1353
00:56:53,010 --> 00:56:55,720
Ez tudatja velünk, hogy
meg kell cserélni őket.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Úgy érzem magam, mint egy konkrét példa
segít sokkal több, mint ez.

1356
00:57:00,470 --> 00:57:04,970
Úgyhogy ezt a kódot fel srácok
most, és azt hiszem, jobb lesz.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Fajta hajlamosak így működik, hogy a
ez gyakran jobb, csak látni őket.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Szóval, mit akarunk csinálni az
először akarjuk, hogy a legkisebb

1361
00:57:17,280 --> 00:57:19,890
elem pozícióját a tömbben.

1362
00:57:19,890 --> 00:57:21,280
Pontosan az, amit Jacob mondott.

1363
00:57:21,280 --> 00:57:23,090
Meg kell tárolni, hogy valahogy.

1364
00:57:23,090 --> 00:57:25,900
Így fogunk kezdeni itt
iterációjával át a tömböt.

1365
00:57:25,900 --> 00:57:28,970
Fogjuk mondani, hogy a mi
először egy csak kezdeni.

1366
00:57:28,970 --> 00:57:38,308
Tehát megy, hogy int
legkisebb egyenlő tömbbel i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Tehát az egyik dolog, amit észre, minden
amikor ez a ciklus végrehajtja,

1369
00:57:45,050 --> 00:57:48,550
kezdjük egy lépéssel távolabb.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Ha elkezdünk megnézzük ezt.

1372
00:57:57,440 --> 00:58:00,840
A következő alkalommal, amikor halad végig,
mi kezdve ezt

1373
00:58:00,840 --> 00:58:02,680
rendeli, a legkisebb érték.

1374
00:58:02,680 --> 00:58:10,450
Tehát nagyon hasonlít a buborék rendezés
ahol tudjuk, hogy miután egy menetben,

1375
00:58:10,450 --> 00:58:11,700
Ez utóbbi elem rendezve.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
A kiválasztás sort,
ez éppen az ellenkezője.

1378
00:58:15,120 --> 00:58:18,950
>> Minden pass, tudjuk, hogy
az elsőt rendezve.

1379
00:58:18,950 --> 00:58:21,360
Miután a második lépés, a
második lesz rendezve.

1380
00:58:21,360 --> 00:58:26,470
És ahogy láttam a dia példák
a rendezett rész csak folyamatosan növekszik.

1381
00:58:26,470 --> 00:58:34,020
Tehát kitűzésében legkisebb
a tömb i, mind csinál

1382
00:58:34,020 --> 00:58:37,340
A szűkítő milyen
keresünk, így

1383
00:58:37,340 --> 00:58:40,164
számának minimalizálása
összehasonlítások tesszük.

1384
00:58:40,164 --> 00:58:41,770
Van ennek értelme mindenki?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Szüksége van rám, hogy fut át, hogy a
ismét lassabban vagy más szavakkal?

1387
00:58:46,380 --> 00:58:47,180
Örülök, hogy.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Szóval tárolása
érték ezen a ponton,

1392
00:58:55,540 --> 00:58:57,840
de mi is szeretnénk tárolni az index.

1393
00:58:57,840 --> 00:59:01,010
Így megyünk tárolni a
helyzete a legkisebb

1394
00:59:01,010 --> 00:59:02,770
egy, ami csak lesz i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Tehát most Jacob teljesül.

1397
00:59:05,440 --> 00:59:06,870
Van dolgokat tárolni.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
És most meg kell, hogy nézze át
A szétválogatás nélkül része a tömbben.

1400
00:59:11,870 --> 00:59:18,170
Tehát ebben az esetben ez a
lenne a mi válogatás nélkül.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Ez i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Szóval, mit fogunk csinálni
lesz egy hurok.

1406
00:59:30,040 --> 00:59:32,066
Ha meg kell
halad végig egy tömb,

1407
00:59:32,066 --> 00:59:33,440
elméd lehetett menni a hurok.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Így néhány int k
equals-- mit gondolunk

1410
00:59:38,090 --> 00:59:39,700
k fog egyenlő kezdeni?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Ez az, amit mi meg, mint a legkisebb
érték és szeretnénk összehasonlítani.

1413
00:59:44,766 --> 00:59:47,090
Mit akarunk összehasonlítani, hogy?

1414
00:59:47,090 --> 00:59:48,730
Ez lesz ez a következő egy, igaz?

1415
00:59:48,730 --> 00:59:53,200
Ezért szeretnénk k inicializálni kell
az i plusz 1-től indul.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> És azt akarjuk, k ebben az esetben
már méret tárolt itt,

1418
01:00:02,800 --> 01:00:03,930
így tudjuk csak használni méretét.

1419
01:00:03,930 --> 01:00:06,240
Méret, hogy a méret a tömb.

1420
01:00:06,240 --> 01:00:09,620
És mi csak szeretnénk
frissítse k által egy-egy alkalommal.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Cool.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Tehát most meg kell találni
A legkisebb elem itt.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Tehát, ha halad végig, mi
akarom mondani, ha a tömb k

1427
01:00:31,380 --> 01:00:37,080
kevesebb, mint a legkisebb value--
ez az, ahol vagyunk valójában

1428
01:00:37,080 --> 01:00:42,950
nyomon követése, hogy mi a
A legkisebb here--

1429
01:00:42,950 --> 01:00:47,740
akkor szeretnénk átminősítése
mi a legkisebb érték.

1430
01:00:47,740 --> 01:00:50,645
>> Ez azt jelenti, hogy jaj, mi
iterációjával át itt.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Bármi érték itt
nem a legkisebb dolog.

1433
01:00:53,740 --> 01:00:54,448
Nem akarjuk azt.

1434
01:00:54,448 --> 01:00:56,100
Azt akarjuk, hogy újra ki kell jelölni.

1435
01:00:56,100 --> 01:01:02,050
Tehát, ha már átcsoportosításával, mit csinál
Ön szerint lehet ezt a kódot itt?

1436
01:01:02,050 --> 01:01:04,160
Szeretnénk átminősítése
legkisebb és pozíció.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Tehát mi az a legkisebb most?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
Diák: Array k.

1441
01:01:09,130 --> 01:01:09,963
Oktató: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
És mi a helyzet most?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Mi az indexek
a legkisebb érték?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Ez csak k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Szóval tömb k, k, azok megegyeznek.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Így akartuk átminősítése azt.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Aztán miután megtaláltuk a legkisebb,
így a végén ez a for ciklus

1454
01:01:39,950 --> 01:01:45,100
Itt azt találja, amit a legkisebbek
érték, ezért csak azt cserélni.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
Ebben az esetben, mint mondjuk a mi
legkisebb érték itt.

1457
01:01:50,816 --> 01:01:51,940
Ez a legkisebb érték.

1458
01:01:51,940 --> 01:01:57,690
>> Csak azt akarjuk cserélni azt itt, ami
hogy mit swap alul

1459
01:01:57,690 --> 01:02:01,270
tette, amit most írt fel
együtt a pár perccel ezelőtt.

1460
01:02:01,270 --> 01:02:02,775
Így kell kinéznie ismerős.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
És akkor csak navigálhat
keresztül, amíg el nem éri az utat

1463
01:02:08,030 --> 01:02:13,100
a végére, ami azt jelenti, hogy
nulla elemeket, amelyek szétválogatás nélkül

1464
01:02:13,100 --> 01:02:14,800
és minden más lett rendezve.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Értelme?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Egy kicsit konkrétabban?

1469
01:02:19,280 --> 01:02:19,990
A kód segítségével?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> DIÁK: Egy méret, soha nem
igazán meghatározni, vagy megváltoztatni,

1472
01:02:26,410 --> 01:02:27,340
hogyan tudja?

1473
01:02:27,340 --> 01:02:32,380
>> Oktató: Tehát az egyik dolog, hogy
észre itt int méret.

1474
01:02:32,380 --> 01:02:35,680
Szóval azt mondja ebben sort-- fajta
egy olyan funkció, ebben case-- ez

1475
01:02:35,680 --> 01:02:40,770
kiválasztás sort, ez elmúlt
az a funkciója.

1476
01:02:40,770 --> 01:02:43,460
Tehát, ha nem telt el
az, akkor valamit csinálni

1477
01:02:43,460 --> 01:02:47,840
mint a hossza a tömb
vagy akkor halad végig

1478
01:02:47,840 --> 01:02:49,390
hogy megtalálja a hosszát.

1479
01:02:49,390 --> 01:02:52,680
De mivel ez elmúlt
-ban, akkor csak használja azt.

1480
01:02:52,680 --> 01:02:55,720
Csak feltételezik, hogy a felhasználó
adta meg egy érvényes mérete

1481
01:02:55,720 --> 01:02:57,698
valójában jelent
a mérete a tömb.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Cool?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Ha a srácok semmi baj ezekkel a
vagy többet szeretne gyakorlat kódolási fajta

1486
01:03:05,870 --> 01:03:08,050
a saját, meg kell
menj study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Ez egy eszköz.

1489
01:03:12,670 --> 01:03:15,040
Nekik van egy ellenőrző, amely
akkor valóban írni.

1490
01:03:15,040 --> 01:03:16,180
Ők pszeudokódja.

1491
01:03:16,180 --> 01:03:19,310
Ezek további videók és diák
többek között az is használom itt.

1492
01:03:19,310 --> 01:03:23,150
Tehát, ha még mindig érzi a
kicsit homályos, próbáld ki azt.

1493
01:03:23,150 --> 01:03:25,670
Mint mindig, gyere beszélj hozzám is.

1494
01:03:25,670 --> 01:03:26,320
Kérdés?

1495
01:03:26,320 --> 01:03:28,611
>> DIÁK: Azt mondod, az
méret megfelel a korábban megadottaknak?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
OKTATÓ: Igen.

1498
01:03:29,900 --> 01:03:35,570
A méret korábban meghatározott fel
itt a függvény deklaráció.

1499
01:03:35,570 --> 01:03:39,060
Szóval feltételezzük, hogy ez már átadott
a felhasználó, és az egyszerűség kedvéért,

1500
01:03:39,060 --> 01:03:41,896
fogjuk feltételezni, hogy a
felhasználó adta a megfelelő méretet.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Szóval ez a fajta kiválasztás.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Srácok, tudom, hogy tanulunk sokat ma.

1505
01:03:47,640 --> 01:03:49,710
Ez egy sűrű adatokat részben.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Tehát, hogy mi lesz
menni beillesztés sort.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Szóval mielőtt, hogy meg kell csinálni
a runtime elemzés itt.

1511
01:04:06,100 --> 01:04:10,190
Így a legjobb esetben,
óta odaítélt megmutattam

1512
01:04:10,190 --> 01:04:11,960
A tábla már
fajta adta el.

1513
01:04:11,960 --> 01:04:15,430
De a legjobb esetben futásidejű, mit gondolsz?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Minden rendezve.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N négyzeten.

1518
01:04:22,070 --> 01:04:24,780
Bárki, aki magyarázatot
miért gondolod?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> Diák: Te összehasonlítása through--

1521
01:04:30,519 --> 01:04:31,268
OKTATÓ: Így van.

1522
01:04:31,268 --> 01:04:32,540
Te összehasonlítása útján.

1523
01:04:32,540 --> 01:04:35,630
Minden iteráció, bár
mi fogásvétel- csökkentéssel ez az egyik,

1524
01:04:35,630 --> 01:04:38,950
még mindig keresi a
mindent, hogy megtalálja a legkisebb.

1525
01:04:38,950 --> 01:04:42,390
Tehát akkor is, ha a legkisebb érték
itt az elején,

1526
01:04:42,390 --> 01:04:44,710
még mindig hasonlítsa össze
szemben minden más

1527
01:04:44,710 --> 01:04:46,550
hogy megbizonyosodjon arról, hogy ez a legkisebb dolog.

1528
01:04:46,550 --> 01:04:49,820
Szóval akkor a végén fut keresztül
körülbelül n négyzeten alkalommal.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Rendben van.

1531
01:04:51,590 --> 01:04:52,785
És mi a legrosszabb esetben?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Szintén n négyzetes mert mész
hogy csinál, hogy ugyanezzel az eljárással.

1534
01:04:57,980 --> 01:05:01,670
Így ebben az esetben, a kiválasztás
sort valami

1535
01:05:01,670 --> 01:05:04,010
hogy mi is nevezzük várható runtime.

1536
01:05:04,010 --> 01:05:07,400
Így a többiek, mi csak tudjuk,
a felső és az alsó határ.

1537
01:05:07,400 --> 01:05:11,180
Attól függően, hogy a bolond
lista vagy hogy válogatás nélkül van,

1538
01:05:11,180 --> 01:05:15,350
ezek között változhat n vagy n négyzeten.

1539
01:05:15,350 --> 01:05:16,550
Nem tudjuk.

1540
01:05:16,550 --> 01:05:22,820
>> Hanem azért, mert a fajta kiválasztás ugyanaz
legrosszabb és a legjobb eset, hogy azt mondja, hogy

1541
01:05:22,820 --> 01:05:25,880
nem számít, hogy milyen típusú bemenet is
van, hogy ez teljesen

1542
01:05:25,880 --> 01:05:29,130
rendezve, vagy teljesen
fordított sorrendje, ez

1543
01:05:29,130 --> 01:05:30,740
fog tartani az azonos idő alatt.

1544
01:05:30,740 --> 01:05:33,760
Tehát ebben az esetben, ha a
emlékszem a mi asztal,

1545
01:05:33,760 --> 01:05:38,610
hogy valóban volt olyan érték,
ez a két fajta nem rendelkezik,

1546
01:05:38,610 --> 01:05:40,390
ami várható futási.

1547
01:05:40,390 --> 01:05:43,350
Tehát tudjuk, hogy ha
futunk kiválasztás sort,

1548
01:05:43,350 --> 01:05:45,380
ez garantáltan
fuss egy n négyzeten idő.

1549
01:05:45,380 --> 01:05:46,630
Nincs változékonyság létezik.

1550
01:05:46,630 --> 01:05:47,630
Ez csak várt.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
És újra, ha meg akarja tanulni
több, vegye CS 124 a tavaszi.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Rendben van.

1555
01:05:56,712 --> 01:05:57,545
Láttuk ezt.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Cool.

1558
01:05:59,030 --> 01:06:00,930
Így beillesztés sort.

1559
01:06:00,930 --> 01:06:03,330
És én talán lesz
hogy lángol át ezt.

1560
01:06:03,330 --> 01:06:05,440
Nem akarom, hogy ti kódot is.

1561
01:06:05,440 --> 01:06:06,580
Majd csak menj át rajta.

1562
01:06:06,580 --> 01:06:10,500
Tehát beillesztés sort kedves
A hasonló fajta kiválasztás

1563
01:06:10,500 --> 01:06:14,460
az, hogy mind egy rendezetlen
és rendezve része a tömb.

1564
01:06:14,460 --> 01:06:20,260
>> De mi más az, hogy
ahogy megy keresztül egy-egy,

1565
01:06:20,260 --> 01:06:24,210
mi csak megteszi szám
mellett van a mi válogatás nélkül,

1566
01:06:24,210 --> 01:06:28,507
és helyesen rendezni
a mi rendezett tömbben.

1567
01:06:28,507 --> 01:06:30,090
Nem lesz több értelme egy példát.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Tehát minden kezdődik a háztartási,
Csakúgy, mint a kiválasztás sort.

1570
01:06:35,430 --> 01:06:38,740
És fogunk rendezni ezt a
növekvő sorrendben, ahogy kellett volna.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Tehát első lépésben
vesszük az első érték

1573
01:06:43,340 --> 01:06:46,700
és azt mondjuk, OK, akkor
most a listán magad.

1574
01:06:46,700 --> 01:06:49,150
>> Mert ha van egy lista
egyedül, akkor rendezve.

1575
01:06:49,150 --> 01:06:52,460
Gratulálunk, hogy a
első elem ebben a tömbben.

1576
01:06:52,460 --> 01:06:54,800
Te már rendezve minden saját.

1577
01:06:54,800 --> 01:06:58,900
Tehát most már a rendezve
és egy rendezetlen tömb.

1578
01:06:58,900 --> 01:07:01,760
Így most, hogy az első.

1579
01:07:01,760 --> 01:07:05,600
Mi történik itt között
és az, hogy azt mondjuk,

1580
01:07:05,600 --> 01:07:08,890
OK, megyünk, hogy nézd meg a
első érték a szétválogatás nélküli tömb

1581
01:07:08,890 --> 01:07:13,270
és fogunk input hogy saját
megfelelő helyen a rendezett tömbben.

1582
01:07:13,270 --> 01:07:21,460
>> Tehát mi nem is veszünk 5 és
azt mondjuk, OK, 5 nagyobb, mint 3,

1583
01:07:21,460 --> 01:07:24,630
így csak helyezze megfelelő
a jogot, hogy a.

1584
01:07:24,630 --> 01:07:25,130
Vagyunk jó.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Akkor megyünk tovább a következőre.

1587
01:07:28,420 --> 01:07:29,720
És mi fog 2.

1588
01:07:29,720 --> 01:07:34,330
Azt mondjuk, rendben van, 2 kisebb
3-nál, így tudjuk, hogy ez

1589
01:07:34,330 --> 01:07:36,220
szükséges, hogy előtte a
előtt a lista most.

1590
01:07:36,220 --> 01:07:41,800
Mi tehát az, hogy mi nyomja a 3. és 5. lefelé
és haladunk a 2 az első nyílásba.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Szóval csak behelyezi
a megfelelő helyre kell tenni.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Akkor nézd meg
következő, és azt mondjuk, 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 nagyobb, mint
mindent a rendezett tömbben,

1596
01:07:53,620 --> 01:07:56,000
így csak címkézni azt, hogy a végén.

1597
01:07:56,000 --> 01:07:56,960
És akkor nézzük 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 kisebb, mint 6, ez kevésbé
mint 5, de ez nagyobb mint 3.

1600
01:08:03,020 --> 01:08:06,270
Szóval csak nyomja mélyen
a középső 3 és 5 közötti.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Tehát, hogy ez egy kicsit
bit konkrétabb,

1603
01:08:10,530 --> 01:08:12,280
Itt a fajta a
ötlet, hogy mi történt.

1604
01:08:12,280 --> 01:08:16,430
Tehát minden osztályozatlan elem, mi
határozza meg, ahol a rendezett rész

1605
01:08:16,430 --> 01:08:17,090
az.

1606
01:08:17,090 --> 01:08:20,680
>> Így szem előtt tartva a
válogatni és osztályozatlan,

1607
01:08:20,680 --> 01:08:26,080
van, hogy áthalad keresztül, és a szám
ki hol illik a rendezett tömbben.

1608
01:08:26,080 --> 01:08:31,460
És helyezze eltolásával a
elemek jobbra le.

1609
01:08:31,460 --> 01:08:34,910
És akkor már csak tartani
iterációjával keresztül, amíg

1610
01:08:34,910 --> 01:08:39,270
egy teljesen rendezett lista
ahol osztályozatlan most nulla

1611
01:08:39,270 --> 01:08:41,720
és rendezett veszi fel a
teljes egészében a lista.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Szóval, megint, hogy a dolgok még
Pontosabban, van pszeudokódja.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Tehát alapvetően az i
egyenlő 0-n mínusz 1,

1616
01:08:52,410 --> 01:08:54,790
hogy csak a hossza a tömb.

1617
01:08:54,790 --> 01:09:00,979
Van néhány tényező, amely az egyenlő
Az első tömb vagy az első indexek.

1618
01:09:00,979 --> 01:09:03,200
Mi meg j egyenlő.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Tehát miközben j nagyobb, mint
nulla és a tömb, j mínusz 1

1621
01:09:09,210 --> 01:09:11,660
nagyobb, mint a
elem, tehát minden, ami ezzel

1622
01:09:11,660 --> 01:09:17,479
annak biztosítása, hogy
A j képviseli igazán

1623
01:09:17,479 --> 01:09:20,010
A szétválogatás nélkül része a tömb.

1624
01:09:20,010 --> 01:09:30,745
>> Tehát miközben még mindig a dolgok
rendezni és j mínusz egy ez-- mi

1625
01:09:30,745 --> 01:09:31,840
az elem neki?

1626
01:09:31,840 --> 01:09:34,760
J soha meg itt.

1627
01:09:34,760 --> 01:09:35,677
Elég bosszantó.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Egyébként.

1630
01:09:36,689 --> 01:09:39,899
Tehát j mínusz 1, akkor ellenőrzi
az elem előtte.

1631
01:09:39,899 --> 01:09:46,460
Azt mondod, OK, ez az elem
előtt, ahol én am-- nézzük

1632
01:09:46,460 --> 01:09:47,540
valójában dolgozzon ki ezt.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Mondjuk ez
mint a mi második menetben.

1635
01:09:56,830 --> 01:09:59,525
Tehát én lesz egyenlő
1, ami itt van.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Tehát én lesz 1-gyel egyenlő.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Ez lenne a 2., 4., 5., 6., 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Rendben van.

1642
01:10:16,750 --> 01:10:20,945
Így a jelen esetben egyébként
lesz egyenlő 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
És van néhány, ami j
lesz egyenlő 1-gyel.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, j fogásvétel- csökkentéssel.

1647
01:10:30,971 --> 01:10:31,720
Ez az, ami van.

1648
01:10:31,720 --> 01:10:35,680
Így j egyenlő i, akkor mi ez
mondás, hogy ahogy haladunk előre,

1649
01:10:35,680 --> 01:10:37,530
mi csak így biztos
hogy nem vagyunk át

1650
01:10:37,530 --> 01:10:43,520
indexelése így amikor próbálunk
beszúrni dolgokat a rendezett lista.

1651
01:10:43,520 --> 01:10:49,850
>> Így, ha j értéke 1-gyel egyenlő, és ebben az esetben
tömb j mínusz one-- olyan kitűnő j mínusz 1

1652
01:10:49,850 --> 01:10:54,610
2 ebben case-- ha ez
nagyobb, mint az elem,

1653
01:10:54,610 --> 01:10:57,700
akkor mindez csinál
tolódik dolgokat.

1654
01:10:57,700 --> 01:11:04,790
Tehát ebben az esetben, tömb j mínusz egy
tömb nulla lenne, ami 2.

1655
01:11:04,790 --> 01:11:08,430
2 nem nagyobb, mint 4,
így ez nem hajtja végre.

1656
01:11:08,430 --> 01:11:11,460
Így a váltás nem mozdul lefelé.

1657
01:11:11,460 --> 01:11:18,790
Mi ez itt csak
mozog a rendezett tömbben le.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
Ebben az esetben valójában, mi
lehetne do-- csináljunk 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Tehát, ha mi vagyunk a séta a
Ennél a példánál vagyunk most itt.

1662
01:11:31,970 --> 01:11:32,740
Ez rendezve.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Ez nem válogatott.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
Így i értéke 2, így
mi elem egyenlő 3-mal.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
És a mi j értéke egyenlő 2.

1670
01:11:52,270 --> 01:12:00,620
Szóval nézzük át, és mi
azt mondják, OK, tömb j mínusz egy

1671
01:12:00,620 --> 01:12:03,470
nagyobb, mint az elem
hogy keresünk?

1672
01:12:03,470 --> 01:12:05,540
És a válasz igen, ugye?

1673
01:12:05,540 --> 01:12:11,275
4 nagyobb, mint 3 és j
2, így ezt a kódot végrehajtja.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Szóval, most mit teszünk egy tömbbel
2, így itt, mi cserélni őket.

1676
01:12:18,550 --> 01:12:25,620
Szóval csak azt mondom, OK, array
2 most lesz 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
És j fog egyenlő
j mínusz 1, amely az 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Ez szörnyű, de
srácok az ötlet.

1681
01:12:37,200 --> 01:12:38,360
J jelentése most 1-gyel egyenlő.

1682
01:12:38,360 --> 01:12:44,360
És tömb j csak lesz
egyenlő a mi elem, ami 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
I törölt valamit, amit nem kellene
van vagy miswrote valami,

1685
01:12:48,570 --> 01:12:49,910
de a srácok az ötlet.

1686
01:12:49,910 --> 01:12:50,640
>> A mozogni n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Aztán ha ez, akkor hurok
újra és azt mondaná, rendben, j 1 most.

1689
01:12:57,960 --> 01:13:00,665
És tömb j mínusz 1 most 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
2 kisebb, mint a mi elem?

1692
01:13:03,760 --> 01:13:04,540
Nem?

1693
01:13:04,540 --> 01:13:07,970
Ez azt jelenti, hogy 've
ki ez az elem

1694
01:13:07,970 --> 01:13:10,110
a megfelelő hely a mi rendezett tömbben.

1695
01:13:10,110 --> 01:13:14,400
Akkor ezt, és azt mondjuk,
OK, a rendezett tömbben nem itt.

1696
01:13:14,400 --> 01:13:19,940
És ez, hogy ezt a 6-os, és
mint, OK, 6 kisebb, mint ez a szám?

1697
01:13:19,940 --> 01:13:20,480
Nem?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
Jól vagyunk.

1700
01:13:22,680 --> 01:13:23,530
>> Csináld újra.

1701
01:13:23,530 --> 01:13:24,740
Azt mondjuk 7.

1702
01:13:24,740 --> 01:13:29,010
7, kevesebb, mint a végén
a mi rendezett tömb?

1703
01:13:29,010 --> 01:13:29,520
Nem.

1704
01:13:29,520 --> 01:13:30,430
Így vagyunk jól.

1705
01:13:30,430 --> 01:13:32,760
Tehát ez lenne rendezve.

1706
01:13:32,760 --> 01:13:38,610
Alapvetően mindez nem
van az mondja take

1707
01:13:38,610 --> 01:13:42,060
az első eleme
A osztályozatlan tömb,

1708
01:13:42,060 --> 01:13:46,010
kitalálni, hová megy
a rendezett tömbben.

1709
01:13:46,010 --> 01:13:48,780
És ez csak ügyel
swap erre.

1710
01:13:48,780 --> 01:13:51,300
Te alapvetően csak csere
amíg ez a jó helyen.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
A vizuális kép az, hogy te vagy
mozgó mindent le csinálja.

1713
01:13:56,990 --> 01:13:59,420
>> Szóval, ez olyan, mint fél sort buborék-szerű.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Nézd meg tanulmány 50.

1716
01:14:03,420 --> 01:14:06,000
Én nagyon ajánlom próbál
kódra ezt a saját.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Ha bármilyen kérdés vagy szeretné
lásd a minta kódot beiktatási sort,

1719
01:14:12,450 --> 01:14:13,750
kérem, tudassa velem.

1720
01:14:13,750 --> 01:14:14,500
Én mindig körül.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Így legrosszabb esetben runtime
és legjobb esetben runtime.

1723
01:14:20,200 --> 01:14:30,700
Ahogy a srác meglátta az asztalon már
mutatta meg, ez mind a négyzeten n és n.

1724
01:14:30,700 --> 01:14:35,590
>> Tehát egyfajta megy ki, hogy mit beszéltünk
körülbelül a korábbi fajta, legrosszabb

1725
01:14:35,590 --> 01:14:38,760
eset runtime az, hogy ha
ez teljesen szétválogatott,

1726
01:14:38,760 --> 01:14:42,530
meg kell összehasonlítani az összes ilyen n-szer.

1727
01:14:42,530 --> 01:14:47,020
Mi egy csomó összehasonlítás
mert ha ez fordított sorrendben,

1728
01:14:47,020 --> 01:14:50,360
fogunk mondani, OK, ez
ugyanaz, ez jó,

1729
01:14:50,360 --> 01:14:54,650
és ez lesz, hogy össze kell hasonlítani
szemben az első, hogy vissza kell másolni.

1730
01:14:54,650 --> 01:14:56,710
És ahogy megkapjuk felé
A farok végén van

1731
01:14:56,710 --> 01:14:59,440
összehasonlítani, összehasonlítani, és
összehasonlítani mindent.

1732
01:14:59,440 --> 01:15:03,030
>> Így végül is
körülbelül n négyzeten.

1733
01:15:03,030 --> 01:15:09,510
Ha ez helyes, akkor
azt mondják, OK, 2, te vagy a jó.

1734
01:15:09,510 --> 01:15:11,330
3, akkor, mint a 2.

1735
01:15:11,330 --> 01:15:12,310
Te jó.

1736
01:15:12,310 --> 01:15:14,150
4, csak összehasonlítani a farok.

1737
01:15:14,150 --> 01:15:14,990
Te jó.

1738
01:15:14,990 --> 01:15:17,140
6, hasonlítsa össze a farkát, akkor minden rendben van.

1739
01:15:17,140 --> 01:15:20,870
Így minden helyszínen, ha ez már
válogatni, még van egy összehasonlítás.

1740
01:15:20,870 --> 01:15:22,320
Tehát csak az n.

1741
01:15:22,320 --> 01:15:26,840
És mivel van egy legjobb esetben futásidejű
n és legrosszabb futási n

1742
01:15:26,840 --> 01:15:28,680
négyzet, nincs elvárt runtime.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Ez csak attól függ, a
káosz listánk van.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
És ismét egy másik
grafikon és egy asztal.

1747
01:15:39,530 --> 01:15:41,170
Tehát különbségek fajta.

1748
01:15:41,170 --> 01:15:44,180
Én csak megy keresztül szél, én
érzem, mi már beszéltünk alaposan

1749
01:15:44,180 --> 01:15:46,570
arról, hogyan minden kedves
A változó és összekapcsolni.

1750
01:15:46,570 --> 01:15:50,564
Tehát egyesülésről sort az utolsó
Fogom untatni srácok.

1751
01:15:50,564 --> 01:15:52,105
Nekünk van egy szép színes képet.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Így összeolvad sort egy rekurzív algoritmus.

1754
01:15:56,040 --> 01:15:59,910
Szóval tudjátok, mi
Egy rekurzív függvény?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Bárki, aki akar mondani?

1757
01:16:03,320 --> 01:16:04,739
Meg akarod próbálni?

1758
01:16:04,739 --> 01:16:07,280
Tehát egy rekurzív függvény csak
funkció, amely magát.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Tehát, ha a srácok ismerős
A Fibonacci-sorozat,

1761
01:16:11,590 --> 01:16:15,670
ami ítélt rekurzív mert
Ön a korábbi két

1762
01:16:15,670 --> 01:16:17,530
és add össze őket
kap a következő.

1763
01:16:17,530 --> 01:16:21,440
Szóval rekurzív, mindig azt gondolom
rekurzió, úgy, mint a spirál

1764
01:16:21,440 --> 01:16:24,430
így Ön, mint a spirál bele.

1765
01:16:24,430 --> 01:16:27,150
De ez csak egy függvény
amely magát.

1766
01:16:27,150 --> 01:16:32,660
>> És tényleg, nagyon gyorsan én
megmutatja, milyen, hogy néz ki.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Tehát itt rekurzív, ha megnézzük, ez
a rekurzív módon összefoglalni több mint egy tömb.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Tehát minden, amit tennie,
mi összeg funkcióval

1771
01:16:47,880 --> 01:16:52,210
összeg, hogy vesz egy méret és egy tömbben.

1772
01:16:52,210 --> 01:16:55,210
És ha azt veszi észre, méret
csökkenti az értéket egy-egy alkalommal.

1773
01:16:55,210 --> 01:17:00,365
És igen, ha x egyenlő
zero-- így ha a méret a tömb

1774
01:17:00,365 --> 01:17:02,710
egyenlő zero-- visszatér nullára.

1775
01:17:02,710 --> 01:17:10,440
>> Egyébként összefoglalja ezt
utolsó eleme a tömb,

1776
01:17:10,440 --> 01:17:14,790
majd vesz egy összeget
a többi tömb.

1777
01:17:14,790 --> 01:17:17,555
Szóval ez csak lebontva
kisebb és kisebb problémák.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Hosszú történet rövid, rekurzió,
funkció, amely magát.

1780
01:17:21,890 --> 01:17:25,740
Ha ez mind megvan ebből,
ez az, amit a rekurzív függvény.

1781
01:17:25,740 --> 01:17:29,870
Ha az előírtnál 51, akkor kap nagyon,
nagyon kényelmes rekurzió.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Ez nagyon klassz.

1784
01:17:32,370 --> 01:17:34,660
Volt értelme a hasonló
03:00 egy éjszaka out.

1785
01:17:34,660 --> 01:17:37,900
És én, mint, hogy miért
még soha nem használja ezt?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Tehát merge sort, alapvetően
mit fog csinálni ez az

1788
01:17:42,430 --> 01:17:45,620
fogja lebontani és törni
lefelé, amíg ez csak egy elem.

1789
01:17:45,620 --> 01:17:47,570
Az egyes elemek könnyen rendezni.

1790
01:17:47,570 --> 01:17:48,070
Látjuk, hogy.

1791
01:17:48,070 --> 01:17:50,760
Ha van egy elem, akkor
már úgy rendezett.

1792
01:17:50,760 --> 01:17:53,800
Így egy input n elemek
ha n értéke kisebb, mint 2,

1793
01:17:53,800 --> 01:17:58,120
csak azért, mert azt vissza eszközök
ez 0 vagy 1. láttunk.

1794
01:17:58,120 --> 01:18:00,050
Ezeket tekintik rendezett elemekkel.

1795
01:18:00,050 --> 01:18:02,170
>> Egyébként szünet félbe.

1796
01:18:02,170 --> 01:18:06,336
Rendezés az első felében, a második rendezni
fél, majd egyesíti őket.

1797
01:18:06,336 --> 01:18:07,460
Miért hívják merge sort.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Tehát itt fogunk rendezni ezeket.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Így tartjuk, hogy azokat
míg a tömb mérete 1.

1802
01:18:17,210 --> 01:18:20,790
Tehát, ha ez 1, akkor csak vissza
mert ez egy rendezett tömbben,

1803
01:18:20,790 --> 01:18:23,940
és ez a rendezett tömb, és ez
a rendezett tömb, mi minden rendezve.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Akkor mit teszünk, mi
indítsa összevonással együtt.

1806
01:18:29,420 --> 01:18:31,820
>> Szóval, ahogy tud
gondolj összevonása is

1807
01:18:31,820 --> 01:18:36,240
csak eltávolítani a kisebb
száma az egyes al tömbök

1808
01:18:36,240 --> 01:18:38,330
és csak hozzáfűzni azt, hogy a kialakult tömb.

1809
01:18:38,330 --> 01:18:44,290
Tehát, ha meg itt, amikor már
ezek a készletek már 4, 6, és 1.

1810
01:18:44,290 --> 01:18:47,280
Ha azt akarjuk, hogy ezeket egyesíteni,
megnézzük az első két

1811
01:18:47,280 --> 01:18:50,730
és azt mondjuk, rendben van, 1 kisebb,
megy az első.

1812
01:18:50,730 --> 01:18:54,330
4. és 6., nincs mit összehasonlítani
azt, csak jelezd a végére.

1813
01:18:54,330 --> 01:18:58,020
>> Amikor a kettőt összekapcsolják, mi csak
hogy a kisebbik a két,

1814
01:18:58,020 --> 01:18:59,310
így 1.

1815
01:18:59,310 --> 01:19:01,690
És most vesszük a
E két kisebb, így 2.

1816
01:19:01,690 --> 01:19:03,330
Kisebb a két, 3.

1817
01:19:03,330 --> 01:19:06,260
Kisebb a két, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Szóval csak húzza le ezeket.

1819
01:19:08,630 --> 01:19:11,210
És mivel ők már
szétválogatott korábban,

1820
01:19:11,210 --> 01:19:14,300
csak egy
összehasonlítás minden alkalommal.

1821
01:19:14,300 --> 01:19:19,610
Tehát több kódot itt, csak képviselet.

1822
01:19:19,610 --> 01:19:24,410
Szóval kezdődik a középső és
Ön sort a bal és a jobb

1823
01:19:24,410 --> 01:19:26,180
és akkor csak azokat egyesíteni.

1824
01:19:26,180 --> 01:19:30,080
>> És nincs kód
A merge itt.

1825
01:19:30,080 --> 01:19:34,110
De ismét, ha megy tovább
tanulmány 50, akkor lesz ott.

1826
01:19:34,110 --> 01:19:36,860
Ellenkező esetben jön talk to me
ha még mindig zavaros.

1827
01:19:36,860 --> 01:19:42,340
Szóval jó dolog az, hogy legjobb esetben,
legrosszabb esetben, és a várható futási

1828
01:19:42,340 --> 01:19:46,250
mind a log n, ami
sokkal jobb, mint voltunk

1829
01:19:46,250 --> 01:19:48,000
láttam a többi a mi fajta.

1830
01:19:48,000 --> 01:19:51,840
Láttuk n négyzeten
és amit valójában

1831
01:19:51,840 --> 01:19:54,380
hogy itt n log n, ami nagyszerű.

1832
01:19:54,380 --> 01:19:55,830
>> Nézd meg, hogy sokkal jobb, hogy van.

1833
01:19:55,830 --> 01:19:56,780
Egy ilyen szép görbe.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Így sokkal hatékonyabb.

1836
01:20:00,120 --> 01:20:03,510
Ha valaha is lehet, használat merge sort.

1837
01:20:03,510 --> 01:20:04,810
Ez időt takarít meg.

1838
01:20:04,810 --> 01:20:07,670
Aztán megint, mint már említettük, ha
te meg az e tartomány alsó

1839
01:20:07,670 --> 01:20:09,480
nem teszi azt
sok a különbség.

1840
01:20:09,480 --> 01:20:11,360
Ez akár több ezer
és több ezer bemenet,

1841
01:20:11,360 --> 01:20:13,318
akkor biztosan szeretne
hatékonyabb algoritmus.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
És ismét, a mi kedves táblázat összes
fajta, hogy a srácok ma tanult.

1844
01:20:19,400 --> 01:20:21,157
>> Szóval tudom, hogy volt egy sűrű nap.

1845
01:20:21,157 --> 01:20:23,490
Ez nem feltétlenül fog
hogy segítsen a PSET.

1846
01:20:23,490 --> 01:20:28,250
De én csak azt szeretném, hogy a felelősségi nyilatkozat
e szakasz nem csupán a psets.

1847
01:20:28,250 --> 01:20:31,240
Mindez az anyag igazságos
játék a midterms.

1848
01:20:31,240 --> 01:20:35,430
És akkor is, ha ezt továbbra is a CS,
Ezek nagyon fontos alapvető

1849
01:20:35,430 --> 01:20:37,870
hogy meg kellene tudni.

1850
01:20:37,870 --> 01:20:41,700
Szóval néhány napon belül lesz
kicsit PSET segítség,

1851
01:20:41,700 --> 01:20:44,600
de néhány hét lesz
sokkal inkább a tényleges tartalom

1852
01:20:44,600 --> 01:20:46,600
hogy nem tűnik szuper
hasznos az Ön számára most,

1853
01:20:46,600 --> 01:20:51,215
de ígérem, ha továbbra is
A lesz nagyon, nagyon hasznos.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Szóval ez a rész.

1856
01:20:54,250 --> 01:20:55,250
Le a vezeték.

1857
01:20:55,250 --> 01:20:56,570
Csináltam egy percen belül.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
De megy.

1860
01:20:58,970 --> 01:21:01,240
És lesz fánkot vagy édességet.

1861
01:21:01,240 --> 01:21:03,464
Van valaki allergiás
semmit, az úton?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Tojás és a tej.

1864
01:21:05,890 --> 01:21:08,120
Tehát egy fánk nem?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Rendben van.

1868
01:21:10,770 --> 01:21:12,120
Csokoládé nincs?

1869
01:21:12,120 --> 01:21:12,620
Starburst.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts jó.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Mi lesz, hogy
Csillagkeletkezési jövő héten majd.

1874
01:21:17,045 --> 01:21:18,240
Ez az, amit hozok.

1875
01:21:18,240 --> 01:21:19,690
Srácok, van egy nagy héten.

1876
01:21:19,690 --> 01:21:20,460
Olvassa el spec.

1877
01:21:20,460 --> 01:21:22,130
>> Hadd tudja, ha bármilyen kérdése van.

1878
01:21:22,130 --> 01:21:25,300
Pset két évfolyamon kell
ki az Ön által csütörtök.

1879
01:21:25,300 --> 01:21:28,320
Ha bármilyen kérdése van
arról, hogyan osztályozzák valami

1880
01:21:28,320 --> 01:21:32,250
vagy miért osztályozva valamit, ahogy én
nem, kérjük, írjon nekem, gyere velem beszélni.

1881
01:21:32,250 --> 01:21:34,210
Én egy kicsit őrült ez
héten, de ígérem

1882
01:21:34,210 --> 01:21:36,340
Én továbbra is válaszolni 24 órán belül.

1883
01:21:36,340 --> 01:21:38,240
Tehát van egy nagy hét, mindenki.

1884
01:21:38,240 --> 01:21:40,090
Sok szerencsét a PSET.

1885
01:21:40,090 --> 01:21:41,248